Make WordPress Core

Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#14662 closed defect (bug) (fixed)

Posts and Terms APIs allow loops in hierarchical data

Reported by: mdawaffe Owned by: westi
Milestone: 3.1 Priority: normal
Severity: normal Version: 3.0.1
Component: General Keywords: has-patch
Focuses: Cc:


In both the Posts API and the Terms API, you can create loops in the posts/terms hierarchy.

wp_insert_post() has some naive hierarchy loop prevention, but it only prevents a post from being its own parent, and loops of order two (post_A->post_B->post_A).

wp_update_term() offers no loop prevention at all. Indeed, from the web interface in WP 3.0.x, you can create post category loops. These loops cause the loop members to be hidden from view on wp-admin/edit-tags.php?taxonomy=category.

Attached provides a generic function to detect loops in arrays representing hirerarchical data.

 * Finds hierarchy loops in an array that maps objects to parents.
 * @since 3.1
 * @param array $map array( ID => parent_ID, ... )
 * @param $start The ID to start the loop check at
 * @return array IDs of all members of loop
function wp_find_hierarchy_loop( $map, $start ) {
        if ( !$arbitrary_loop_member =
                wp_find_hierarchy_loop_tortoise_hare( $map, $start )
                return array();

        return wp_find_hierarchy_loop_tortoise_hare(

 * Uses the "The Tortoise and the Hare" algorithm to detect loops.
 * For every step of the algorithm, the hare takes two steps
 * and the tortoise one.
 * If the hare ever laps the tortoise, there must be a loop.
 * @since 3.1
 * @param array $map array( ID => parent_ID, ... )
 * @param $start The ID to start the loop check at
 * @param bool $_return_loop Return loop members
 *             or just detect presence of loop?
 *             Only set to true if you already know the given
 *             $start is part of a loop
 *             (otherwise the returned array might include branches)
 * @return mixed scalar ID of some arbitrary member of the loop,
 *            or array of IDs of all members of loop if $_return_loop
function wp_find_hierarchy_loop_tortoise_hare(
        $_return_loop = false
) {
        // Do some stuff - see patch

To detect Post and Term hierarchy loops, the attached adds new filters to wp_insert_post() and wp_update_term(), respectively. These filters can be removed by plugins that want to allow crazy stuff for custom post types or taxonomies.

add_filter( 'wp_insert_post_parent', 'wp_check_post_hierarchy_for_loops', 10, 2 );
add_filter( 'wp_update_term_parent', 'wp_check_term_hierarchy_for_loops', 10, 3 );

Those function make use of the generic wp_find_hierarchy_loop() function, and some ArrayAccess implementors. ArrayAccess is useful since it avoids the need to load the entire hierarchy all at once, and can take advantage of any persistent object cache being use by the site.

Attachments (5)

14662.diff (9.5 KB) - added by mdawaffe 5 years ago.
14662.b.diff (9.4 KB) - added by mdawaffe 5 years ago.
Tweak to fix $_return_loop handling.
14662.2.diff (4.5 KB) - added by ryan 5 years ago.
Populate ->ancestors, basic loop detection
14662.c.diff (8.6 KB) - added by mdawaffe 5 years ago.
PHP4 compatible version
14662.3.diff (1.2 KB) - added by mdawaffe 5 years ago.
Doc fixes

Download all attachments as: .zip

Change History (17)

@mdawaffe5 years ago

@mdawaffe5 years ago

Tweak to fix $_return_loop handling.

comment:1 @scribu5 years ago

  • Cc scribu added

comment:2 @markel5 years ago

  • Cc rmarkel@… added

comment:3 @mdawaffe5 years ago

  • Milestone changed from 3.1 to Awaiting Review

My Bad. I thought 3.1 was being bumped to PHP5, but I see now that it's 3.2.

We can

  1. Push this patch to 3.2
  2. Let it sit in 3.1 and conditionally load the PHP5 stuff. This will preserve the (buggy) status quo for PHP4 users and fix the bug for PHP5 users.
  3. Rewrite for PHP4. Aesthetically unpleasing, but possible :)

comment:4 @westi5 years ago

  • Owner set to westi
  • Status changed from new to accepted

Will review

comment:5 @mdawaffe5 years ago

PS: A PHP4 rewrite is straightforward. We could use normal callbacks instead of ArrayAccess ones.

@ryan5 years ago

Populate ->ancestors, basic loop detection

comment:7 @ryan5 years ago

I started on a simple-minded patch before noticing this ticket. Basically, it adds simple loop detection to _get_post_ancestors(), makes sure ->ancestors is always populated after calling get_post(), and moves places doing their own loops to use ->ancestors. The loop detection just looks to see if an ID is repeated anywhere in the ancestry. It doesn't try to do full loop detection like Mike's patch. Mike's better detection triggered via filters could be merged in with my ancestors cleanup.

The ancestors cleanup also fixes issues like #10381 and #14329.

comment:8 @mdawaffe5 years ago

  • Keywords has-patch added

14662.c.diff is a PHP4 compatible version of 14662.b.diff. Less code but harder to grok.

Some function signatures differ between the two patches to get things working with generic callbacks. I marked the heavy lifters as @internal to indicate that the signatures may change in the future on the off chance we want to move back to a PHP5 based solution.

@mdawaffe5 years ago

PHP4 compatible version

comment:9 @ryan5 years ago

  • Milestone changed from Awaiting Review to 3.1
  • Resolution set to fixed
  • Status changed from accepted to closed

@mdawaffe5 years ago

Doc fixes

comment:10 @mdawaffe5 years ago

  • Resolution fixed deleted
  • Status changed from closed to reopened

Reopening for trivial doc fixes. Attached.

comment:11 @nacin5 years ago

  • Resolution set to fixed
  • Status changed from reopened to closed

(In [15846]) Doc fixes for wp_find_hierarchy_loop. props mdawaffe, fixes #14662.

comment:12 @automattor5 years ago

(In [15922]) Remove debugging code in wp_check_term_hierarchy_for_loops(). See #14662

Note: See TracTickets for help on using tickets.