Doctrine 1
  1. Doctrine 1
  2. DC-384

Nested set API allows inconsistent trees to be created

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 1.2.1
    • Fix Version/s: 1.2.2
    • Component/s: Nested Set
    • Labels:
      None
    • Environment:
      Symfony 1.4

      Description

      First create a tree as follows:

      A
      B
      C
      D

      That is, C and D are both children of B, and B is a child of A.

      At this point our db looks as follows:

      mysql> select SLUG, LFT, RGT, LEVEL from pk_context_cms_page;
      -----------------------+

      SLUG LFT RGT LEVEL

      -----------------------+

      / 1 12 0
      /about 10 11 1
      global NULL NULL NULL
      /a 2 9 1
      /a/b 3 8 2
      /a/b/c 4 5 3
      /a/b/c/d 6 7 3

      -----------------------+
      7 rows in set (0.00 sec)

      Now, call D->moveAsLastChildOf(C). D is now a child of C.

      So far so good:

      mysql> select SLUG, LFT, RGT, LEVEL from pk_context_cms_page;
      -----------------------+

      SLUG LFT RGT LEVEL

      -----------------------+

      / 1 12 0
      /about 10 11 1
      global NULL NULL NULL
      /a 2 9 1
      /a/b 3 8 2
      /a/b/c 4 7 3
      /a/b/c/d 5 6 4

      -----------------------+
      7 rows in set (0.00 sec)

      Now, call C->moveAsLastChildOf(D). This should pull D out from under C.

      Instead the values of LFT and RGT get messed up:

      mysql> select SLUG, LFT, RGT, LEVEL from pk_context_cms_page
      -> ;
      -----------------------+

      SLUG LFT RGT LEVEL

      -----------------------+

      / 1 12 0
      /about 10 11 1
      global NULL NULL NULL
      /a 2 9 1
      /a/b 3 8 2
      /a/b/c 6 7 5
      /a/b/c/d 7 6 4

      -----------------------+
      7 rows in set (0.00 sec)

      moveAsLastChildOf should either (1) implement moving ancestors beneath their children correctly or (2) refuse to do so.

      Note: these actions were carried out as separate PHP requests.

      This is easy to reproduce by firing up the Apostrophe sandbox project, logging in as admin/admin, creating the page structure described, and then clicking the apostrophe in the upper left and then the Reorganize tool.

      Instructions to check out the current sandbox are here:

      http://www.apostrophenow.com/home/readme

      You'll need to set up databases.yml and do a build --all and a data-load, that's about it.

      Be sure to open a second tab so that you can have two views of the tree showing the initial state (C and D both as kids of B) so that you can drag D under C in the first tab and then try to drag C under D in the second tab. Otherwise the tree editor itself will block you from trying to move C under D.

      The implementation of pkContextCMS/executeTreeMove is calling moveAsLastChildOf() in both cases and doing so to the right pages. I've added logging to verify this, look for references to TREEMOVE in the frontend_log.dev file.

      We are going to add checks at the pkContextCMS level to refuse to attempt to move an ancestor beneath one of its children as a workaround, although in principle that should be possible (at least if the ancestor has no children? Not sure if it always makes sense if it does have children other than the ancestors of the new parent).

      1. nest.tgz
        7 kB
        Dan Ordille
      2. no-move-into-descendant.patch
        2 kB
        Dan Ordille

        Activity

        Hide
        Dan Ordille added a comment -

        I have attached a symfony project to demonstrate the problem. Project is using latest symfony version form 1.4 svn. Run test located in test/unit/corrupt.php

        The test creates 3 nodes A, B, and C.
        Inserts B as last child of a.
        Inserts C as last child of a.
        The nodes then have the following properties.

        Node lft rgt lvl
        A 1 6 0
        B 2 3 1
        C 5 5 1

        A is then moved as the first child of B which causes corrupted nested sets.

        Node lft rgt lvl
        A 3 6 2
        B 4 3 1
        C 4 5 1

        A is still the parent of B and C, yet its level is 2.

        This problem exists whenever a node is moved into one of its children or descendants.

        Show
        Dan Ordille added a comment - I have attached a symfony project to demonstrate the problem. Project is using latest symfony version form 1.4 svn. Run test located in test/unit/corrupt.php The test creates 3 nodes A, B, and C. Inserts B as last child of a. Inserts C as last child of a. The nodes then have the following properties. Node lft rgt lvl A 1 6 0 B 2 3 1 C 5 5 1 A is then moved as the first child of B which causes corrupted nested sets. Node lft rgt lvl A 3 6 2 B 4 3 1 C 4 5 1 A is still the parent of B and C, yet its level is 2. This problem exists whenever a node is moved into one of its children or descendants.
        Hide
        Dan Ordille added a comment -

        I created a patch that prevents moving a node into its descendants.

        I was trying to think what the ideal behavior would be in this situation, but at least this patch will prevent corruption.

        Show
        Dan Ordille added a comment - I created a patch that prevents moving a node into its descendants. I was trying to think what the ideal behavior would be in this situation, but at least this patch will prevent corruption.
        Hide
        Jonathan H. Wage added a comment -

        Thanks for the issue Tom and patch Dan. Let me know if we still have any issues remaining.

        Show
        Jonathan H. Wage added a comment - Thanks for the issue Tom and patch Dan. Let me know if we still have any issues remaining.

          People

          • Assignee:
            Jonathan H. Wage
            Reporter:
            Tom Boutell
          • Votes:
            3 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: