Loop detection in django models

I have an model which has a many to many relationship with itself.

I want to create a validation on the model(s) which would prevent a group from being it's own subgroup, or a subgroup of it's subgroups, etc. The objective is to prevent a situation which can result in a loop / infinite recursion.

I've tried implementing this in the model clean() method as shown below.

I've also tried implementing this in the model save() method using transactions.

In both situations, I've ended up in a situation where invalid changes are (incorrectly) saved to the database, but if I attempt to make further changes to either instance, the validations detect the error, but at that point, the bad data is already in the database.

I'm wondering if this is possible, and if so, if it's possible to do so in model validations so I don't have to make sure everyone on my team remembers to call these validations from all forms they create in the future.

Without further delay, the code:

class Group(models.Model):
    name = models.CharField(max_length=200)
    sub_groups = models.ManyToManyField('self', through='SubGroup', symmetrical=False)

    def validate_no_group_loops(self, seen=None):
        if seen is None:
            seen = []
        if self.id in seen:
            raise ValidationError("LOOP DETECTED")
        seen.append(self.id)
        for sub_group in self.target.all():
            sub_group.target.validate_no_group_loops(seen)

    # I thought I would use the standard validation mechanism in the clean()
    # method, but it appears that when I recurse back to the group I started 
    # with, I do so with a query to the database which retreives the data before
    # it's been modified. I'm still not 100% sure if this is the case, but
    # regardless, it does not work.
    def clean(self):
        self.validate_no_group_loops()

    # Susp开发者_如何学Pythonecting that the problem with implementing this in clean() was that 
    # I wasn't testing the data with the pending modifications due to the 
    # repeated queries to the database, I thought that I could handle the
    # validation in save(), let the save actually put the bad data into the
    # database, and then roll back the transaction if I detect a problem.
    # This also doesn't work.
    def save(self, *args, **kwargs):
        super(Group, self).save(*args, **kwargs)
        try:
            self.validate_no_group_loops()
        except ValidationError as e:
            transaction.rollback()
            raise e
        else:
            transaction.commit()


class SubGroup(models.Model):
    VERBS = { '+': '+', '-': '-' }
    action = models.CharField(max_length=1, choices=VERBS.items(), default='+')
    source = models.ForeignKey('Group', related_name='target')
    target = models.ForeignKey('Group', related_name='source')

Thanks ahead of time for any assistance you may provide.

[edit] FYI, If you couldn't tell based on the mechanism I'm using to manage transactions, I'm currently using django 1.2 because that's what's available in the fedora EPEL repository for RHEL6. If a solution is available but it requires an upgrade to 1.3, I have no problem upgrading. I'm also using python 2.6.6 because that's what's available in RHEL6 from RedHat. I'd rather avoid a python upgrade, but I highly doubt that it's relevant.

---

Should "target." really be inside this loop in your code? It seems like that would make it skip a level.

    for sub_group in self.target.all():
        sub_group.target.validate_no_group_loops(seen)