[wp-trac] [WordPress Trac] #14662: Posts and Terms APIs allow loops in hierarchical data

[WordPress Trac]

#14662: Posts and Terms APIs allow loops in hierarchical data
--------------------------+-------------------------------------------------
 Reporter:  mdawaffe      |       Owner:       
     Type:  defect (bug)  |      Status:  new  
 Priority:  normal        |   Milestone:  3.1  
Component:  General       |     Version:  3.0.1
 Severity:  normal        |    Keywords:       
--------------------------+-------------------------------------------------
 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 [http://php.net/manual/class.arrayaccess.php
 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.

-- 
Ticket URL: <http://core.trac.wordpress.org/ticket/14662>
WordPress Trac <http://core.trac.wordpress.org/>
WordPress blogging software