# InvalidMove: A node may not be made a child of any of its descendants.

1,560 views
Skip to first unread message

mike

unread,
Nov 15, 2010, 12:11:01 PM11/15/10
to django-mptt-dev
Dear all,

for testing purposes I set up a simple MPTT model following the
documentation. Then I created a couple of instances using the admin,
and created a method for randomly generating N instances in the tree:

=====================================

from django.db import models
from mptt.models import MPTTModel

class Concept(MPTTModel):
name = models.CharField(max_length=30)
parent = models.ForeignKey('self', null=True, blank=True,
related_name='children')

class MPTTMeta:
order_insertion_by=['name']

def __unicode__(self):
return self.name

import random

def generate_subclasses():
all_choices = list(Concept.objects.all())
for x in range(10):
current = random.choice(all_choices)
nname = str(x) + str(random.random())
new = Concept(name= nname)
new.save()
new.move_to(current)

=====================================


But each time I run this I get an error. Tried various alternative
options, but still I can't understand where the error is.... any
ideas?

*****************************************************
>>> generate_subclasses()
Traceback (most recent call last):
File "<console>", line 1, in <module>
File "/Users/code/django/projects/ideas_and_thoughts/src/ideas/../
ideas/mptt_test/models.py", line 41, in generate_subclasses
new.move_to(current)
File "/Users/code/django/projects/ideas_and_thoughts/src/ideas/../
ideas/mptt/models.py", line 401, in move_to
self._tree_manager.move_node(self, target, position)
File "/Users/code/django/projects/ideas_and_thoughts/src/ideas/mptt/
managers.py", line 257, in move_node
self._move_root_node(node, target, position)
File "/Users/code/django/projects/ideas_and_thoughts/src/ideas/mptt/
managers.py", line 789, in _move_root_node
raise InvalidMove(_('A node may not be made a child of any of its
descendants.'))
InvalidMove: A node may not be made a child of any of its descendants.

*****************************************************



Thanks in advance,

Mike





p.s.
I'm using MPTT 0.4.2 and django 1.1

Craig de Stigter

unread,
Nov 15, 2010, 2:21:31 PM11/15/10
to django-...@googlegroups.com
Hi Mike

This is a long time gotcha with django-mptt. Basically when you save a model, the tree fields get updated via a bulk update. However any stored instances already in memory don't get updated.

So when you do
               new.move_to(current)

new and current are updated with the right tree fields, but the other nodes in all_choices aren't. Then when you pick another one from the list

The other day I added a fix for the specific case of updating the parent node when inserting new nodes (see GC-17, you'll need to get the latest source from github) but I think this is impossible to fix properly for the general case you describe below.

The usual solution is to refresh the parent node from the database before adding the child:
               new.move_to(Concept.objects.get(pk=current.pk))

Alternatively it might be faster to just do a rebuild at the end to fix all the broken tree fields:
    Concept.tree.rebuild()

HTH,

Craig 

Craig de Stigter

unread,
Nov 15, 2010, 2:37:03 PM11/15/10
to django-...@googlegroups.com
In addition you could make this use less database queries by setting the parent before you save():

               new = Concept(name= nname, parent=Concept.objects.get(pk=current.pk))
               new.save()

The save() will take care of calculating the tree fields based on the parent. This means django-mptt can use insertion logic instead of move logic, which is faster and also you don't have to save() twice :)

mike

unread,
Nov 15, 2010, 2:52:06 PM11/15/10
to django-mptt-dev
Craig, thanks so much I was starting to go crazy after that problem!

The first solution you proposed works just fine:

new.move_to(Concept.objects.get(pk=current.pk))

Regarding your last comment, well that looks even better although I'm
surprised that it works. Some time ago I tried using the parent
attribute to set mptt instances but I got only weird results [I
blogged about it here: http://www.michelepasin.org/techblog/?p=318 ,
note though that I was using mptt 0.3]. As a result, I thought the
right way to do it was by using the move logic...

But wait - maybe the weird results I was getting were due to the same
reason, alas because the instances in memory don't get updated
properly? that might explain it all..

cheers

mike








On Nov 15, 7:37 pm, Craig de Stigter <craig...@gmail.com> wrote:
> In addition you could make this use less database queries by setting the
> parent before you save():
>
>                new = Concept(name= nname, parent=Concept.objects.get(pk=
>
> > current.pk))
>
>                new.save()
>
> The save() will take care of calculating the tree fields based on the
> parent. This means django-mptt can use insertion logic instead of move
> logic, which is faster and also you don't have to save() twice :)
>
> On Tue, Nov 16, 2010 at 8:21 AM, Craig de Stigter <craig...@gmail.com>wrote:
>
>
>
>
>
>
>
> > Hi Mike
>
> > This is a long time gotcha with django-mptt. Basically when you save a
> > model, the tree fields get updated via a bulk update. However any stored
> > instances already in memory don't get updated.
>
> > So when you do
>
> >>                new.move_to(current)
>
> > new and current are updated with the right tree fields, but the other nodes
> > in all_choices aren't. Then when you pick another one from the list
>
> > The other day I added a fix for the specific case of updating the parent
> > node when inserting new nodes (see GC-17<http://code.google.com/p/django-mptt/issues/detail?id=17>,
> > you'll need to get the latest source from github) but I think this is
> > impossible to fix properly for the general case you describe below.
>
> > The usual solution is to refresh the parent node from the database before
> > adding the child:
>
> >>                new.move_to(Concept.objects.get(pk=current.pk))
>
> > Alternatively it might be faster to just do a rebuild at the end to fix all
> > the broken tree fields:
>
> >>     Concept.tree.rebuild()
>
> > HTH,
>
> > Craig
>

Craig de Stigter

unread,
Nov 15, 2010, 4:08:01 PM11/15/10
to django-...@googlegroups.com
But wait - maybe the weird results I was getting were due to the same reason, alas because the instances in memory don't get updated properly? that might explain it all

Yes, I think so. Here's a ridiculously detailed explanation of the badness, in case you feel like reading ;)

From your blog:

>>> p1 = PossessionNew(possname="test11")
>>> p2 = PossessionNew(possname="test22")
>>> p3 = PossessionNew(possname="test33")
>>> p1.save()
>>> p2.save()
>>> p3.save()

Up to this point everything is fine. The nodes have these tree fields:

p1: tree_id=0, lft=0, rght=1 (correct)
p2: tree_id=1, lft=0, rght=1 (correct)
p3: tree_id=2, lft=0, rght=1 (correct)

>>> p3.parent = p2
>>> p2.parent = p1
>>> p3.save()
>>> p2.save()

When p3 gets saved, the tree fields in the db table are updated for all the nodes, but the changes don't get propagated to p1 or p2 which are already in memory.

So immediate after p3 is saved, p2 still has it's old tree fields:

p1: tree_id=0, lft=0, rght=1 (correct)
p2: tree_id=1, lft=0, rght=1 (bad - should be rght=3)
p3: tree_id=1, lft=1, rght=2 (correct)

Then p2 gets saved and it gets even worse:

p1: tree_id=0, lft=0, rght=1 (bad - should be rght=5)
p2: tree_id=0, lft=1, rght=2 (bad - should be rght=4)
p3: tree_id=1, lft=1, rght=2 (bad - should be tree_id=0, lft=2, rght=3)

This is a common gotcha with django-mptt, unfortunately I don't think it's something that can really be addressed without django #17 (which is unlikely to actually land in django IMHO)

mike

unread,
Nov 17, 2010, 1:16:04 PM11/17/10
to django-mptt-dev
Many thanks Craig, the explanation is clear and helpful. I've been
using MPTT for a while now so knowing a bit more about the way it
works is a big advantage! hope you'll keep up this good work!
cheers, m
> #17<http://code.djangoproject.com/ticket/17> (which
Reply all
Reply to author
Forward
0 new messages