Posts and Terms APIs allow loops in hierarchical data

[mdawaffe]

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(
                $map,
                $arbitrary_loop_member,
                true
        );
} 

/**
 * 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(
        $map,
        $start,
        $_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.

[mdawaffe]

Tweak to fix $_return_loop handling.

[mdawaffe]

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 :)

[westi]

Will review

[mdawaffe]

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

[filosofo]

Related: #15074

[ryan]

Populate ->ancestors, basic loop detection

[ryan]

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.

[mdawaffe]

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.

[mdawaffe]

PHP4 compatible version

[ryan]

[15806]

[mdawaffe]

Doc fixes

[mdawaffe]

Reopening for trivial doc fixes. Attached.

[nacin]

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

[automattor]

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