follow

#27 bug when moving nodes

Reported by francisl 2010-07-02 (last edited unknown)

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]

Attachments

Comments and changes

1. #1 Gustavo Picon

   written 2010-07-03

   Hi francisl,

   Could you please paste your models and maybe some sample data/move operations to help me reproduce this?

   Thanks.

2. #2 Gustavo Picon

   written 2010-11-28

   • Changed status from new to on hold.
3. #3 Anonymous

   written 2011-02-01

   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).
4. #4 Anonymous

   written 2011-02-01

   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.

5. #5 Anonymous

   written 2011-02-01

   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.val1=node.val1-2
               node.save()
               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%'

6. #6 Matt Hoskins

   written 2011-02-02

   • Changed status from on hold to open.
   • Added attachment mp_tree.py-patch.
   • Added attachment tests.py-patch.

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

7. #7 Matt Hoskins

   written 2011-02-02

   • Added attachment mp_tree.py-patch.

   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.

8. #8 Gustavo Picon

   written 2011-03-21

   • Changed status from open to resolved.

   Matt,

   Amazing patch. Fixed in 1e9d1bf4953a

   Thanks!

9. #9 Anonymous

   written 2011-07-12

   Good fix. Thanks for the patch.

Verification: Please write the text from the image in the box (letters only)

Is that you, Humanoid? Is this me?

• Cancel