1. Gustavo Picón
  2. django-treebeard
  3. Issues
Issue #27 resolved

bug when moving nodes

created an issue

Using the MP_Node, after I have added a couple of nodes (12), when i move them around it will raise an exception IntegrityError telling column path is not unique.

I'm using the mercurial trunk.

trace : {{{


/Library/Python/2.5/site-packages/treebeard/mp_tree.pyc in move(self, target, pos) 668 cursor = connection.cursor() 669 for sql, vals in stmts: --> 670 cursor.execute(sql, vals) 671 transaction.commit_unless_managed() 672

/Library/Python/2.5/site-packages/django/db/backends/util.pyc in execute(self, sql, params) 13 start = time() 14 try: ---> 15 return self.cursor.execute(sql, params) 16 finally: 17 stop = time()

/Library/Python/2.5/site-packages/django/db/backends/sqlite3/base.pyc in execute(self, query, params) 198 query = self.convert_query(query) 199 try: --> 200 return Database.Cursor.execute(self, query, params) 201 except Database.IntegrityError, e: 202 raise utils.IntegrityError, utils.IntegrityError(*tuple(e)), sys.exc_info()[2]


Comments (9)

  1. Anonymous

    I've hit this issue. On postgresql unique constraints are not deferred to the end of the transaction (only in 9.0 is it even possible to defer them), so they're checked straight away.

    So with MP_Node if you change the position of a child node within its list of siblings it seems you hit this issue.

    So take list of children under a parent:

    • A
    • B
    • C
    • D

    If you move, say, D:

    • A
    • D
    • B
    • C

    Then you get the error because the code tries to update the path of D use the path that B currently has (because B's paths are going to be updated in a later SQL statement) and triggers the integrity constraint.

    The only way I can see to fix this are either:

    • Remove unique=true from the definition of the path field on MP_node (which may not be possible or may not be advisable) OR
    • Do a temporary extra update step, so any path which is a new target path but which is itself going to be updated gets a temporary prefix (e.g. slap a "-" in front of the path, although if the paths equal the limit of the field size that would blow up of course, but that should be an edge case) and then they get renamed from the version with that temporary prefix. So if you're mapping 00004 to 00002 and 00002 to 00003 and 00003 to 00004 instead you'd map each to be e.g. -00004 and then remap. Alternatively you could try calculate the order of updates such that only one needs to be prefixed to get it out of the way (in this case do 00004 to -00004, rename the others in the right order to avoid conflicts, then rename the prefixed one).
  2. Anonymous

    D'oh, of course the first option I outlined wouldn't work because the later renames would catch the results of earlier renames - ignore that suggestion.

  3. Anonymous

    Test case (added as method of TestTreeSorted). Triggers the issue with MP_Node...

        def _multi_move_sortedsibling(self):
            self.sorted_model.add_root(val1=3, val2=3, desc='zxy')
            self.sorted_model.add_root(val1=1, val2=4, desc='bcd')
            self.sorted_model.add_root(val1=2, val2=5, desc='zxy')
            self.sorted_model.add_root(val1=3, val2=3, desc='abc')
            self.sorted_model.add_root(val1=4, val2=1, desc='fgh')
            self.sorted_model.add_root(val1=3, val2=3, desc='abc')
            self.sorted_model.add_root(val1=2, val2=2, desc='qwe')
            self.sorted_model.add_root(val1=3, val2=2, desc='vcx')
            root_nodes = self.sorted_model.get_root_nodes()
            target = root_nodes[0]
            for node in root_nodes[1:]:
                # because raw queries don't update django objects
                node = self.sorted_model.objects.get(pk=node.id)
                target = self.sorted_model.objects.get(pk=target.id)
                node.move(target, 'sorted-sibling')
            expected = [(0, 2, u'qwe', 1, 0),
                        (0, 5, u'zxy', 1, 0),
                        (1, 2, u'vcx', 1, 0),
                        (1, 3, u'abc', 1, 0),
                        (1, 3, u'abc', 1, 0),
                        (1, 3, u'zxy', 1, 0),
                        (1, 4, u'bcd', 1, 0),                    
                        (2, 1, u'fgh', 1, 0)]
            self.assertEqual(self.got(), expected)

    Leads to:

    IntegrityError: ERROR: duplicate key value violates unique constraint "treebeard_mp_testnodesorted_path_key" UPDATE "treebeard_mp_testnodesorted" SET path='2'||SUBSTR(path, 2) WHERE path LIKE '1%'

  4. Matt Hoskins

    Sorry for all the anonymous postings above - I've now signed up for a bitbucket account. I had a go at a patch to fix the issue, although without a deep understanding of the code I may not be doing it the most optimal way, but basically I went for the approach of detecting if there might be a collision (move to the left with the parent staying the same) and temporarily moving the branch to the end of the list of siblings to make sure it's out of the way.

    I added two tests to the test suite to try moving siblings both to the left and to the right of their current position (the tests are probably not optimal either, but they do test the code and it was the moving to the left within siblings that triggered the issue).

    See the two attached patches against 1.61 in unified diff form. Hope you don't mind me taking this issue off hold (I guess you put it on hold due to the lack of follow-up from the original reporter)!

  5. Matt Hoskins

    While doing a bit more playing with the code to handle moves (I'm writing code in my django app which allows for tree reorganising, including reordering nodes) I've seen that the MP_Node code increments the paths for children even if they don't actually need incrementing to permit the insert (i.e. if you do a lot of reorganising of nodes on a given branch you'll get big holes introduced). So I've added some code which checks the paths on the siblings to the right and only moves those that need to move to try mitigate that by closing holes to the right of the position if possible. Up to you if you think it's worth including :).

    The patch I've attached includes the earlier attempt at a fix plus this new optimisation.

  6. Log in to comment