Initial mptt commit. Implements a much more efficient get_with_path method for TreeMa...

diff --git a/migrations/0009_auto__add_field_node_lft__add_field_node_rght__add_field_node_tree_id_.py b/migrations/0009_auto__add_field_node_lft__add_field_node_rght__add_field_node_tree_id_.py
new file mode 100644 (file)
index 0000000..a6f58fd
--- /dev/null
+++ b/migrations/0009_auto__add_field_node_lft__add_field_node_rght__add_field_node_tree_id_.py
@@ -0,0 +1,178 @@
+# encoding: utf-8
+import datetime
+from south.db import db
+from south.v2 import SchemaMigration
+from django.db import models
+
+class Migration(SchemaMigration):
+
+    def forwards(self, orm):
+        
+        # Adding field 'Node.lft'
+        db.add_column('philo_node', 'lft', self.gf('django.db.models.fields.PositiveIntegerField')(default=0, db_index=True), keep_default=False)
+
+        # Adding field 'Node.rght'
+        db.add_column('philo_node', 'rght', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False)
+
+        # Adding field 'Node.tree_id'
+        db.add_column('philo_node', 'tree_id', self.gf('django.db.models.fields.PositiveIntegerField')(default=0, db_index=True), keep_default=False)
+
+        # Adding field 'Node.level'
+        db.add_column('philo_node', 'level', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False)
+
+        # Adding field 'Template.lft'
+        db.add_column('philo_template', 'lft', self.gf('django.db.models.fields.PositiveIntegerField')(default=0, db_index=True), keep_default=False)
+
+        # Adding field 'Template.rght'
+        db.add_column('philo_template', 'rght', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False)
+
+        # Adding field 'Template.tree_id'
+        db.add_column('philo_template', 'tree_id', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False)
+
+        # Adding field 'Template.level'
+        db.add_column('philo_template', 'level', self.gf('django.db.models.fields.PositiveIntegerField')(default=1, db_index=True), keep_default=False)
+
+
+    def backwards(self, orm):
+        
+        # Deleting field 'Node.lft'
+        db.delete_column('philo_node', 'lft')
+
+        # Deleting field 'Node.rght'
+        db.delete_column('philo_node', 'rght')
+
+        # Deleting field 'Node.tree_id'
+        db.delete_column('philo_node', 'tree_id')
+
+        # Deleting field 'Node.level'
+        db.delete_column('philo_node', 'level')
+
+        # Deleting field 'Template.lft'
+        db.delete_column('philo_template', 'lft')
+
+        # Deleting field 'Template.rght'
+        db.delete_column('philo_template', 'rght')
+
+        # Deleting field 'Template.tree_id'
+        db.delete_column('philo_template', 'tree_id')
+
+        # Deleting field 'Template.level'
+        db.delete_column('philo_template', 'level')
+
+
+    models = {
+        'contenttypes.contenttype': {
+            'Meta': {'unique_together': "(('app_label', 'model'),)", 'object_name': 'ContentType', 'db_table': "'django_content_type'"},
+            'app_label': ('django.db.models.fields.CharField', [], {'max_length': '100'}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'model': ('django.db.models.fields.CharField', [], {'max_length': '100'}),
+            'name': ('django.db.models.fields.CharField', [], {'max_length': '100'})
+        },
+        'philo.attribute': {
+            'Meta': {'unique_together': "(('key', 'entity_content_type', 'entity_object_id'), ('value_content_type', 'value_object_id'))", 'object_name': 'Attribute'},
+            'entity_content_type': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'attribute_entity_set'", 'to': "orm['contenttypes.ContentType']"}),
+            'entity_object_id': ('django.db.models.fields.PositiveIntegerField', [], {}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'key': ('django.db.models.fields.CharField', [], {'max_length': '255'}),
+            'value_content_type': ('django.db.models.fields.related.ForeignKey', [], {'blank': 'True', 'related_name': "'attribute_value_set'", 'null': 'True', 'to': "orm['contenttypes.ContentType']"}),
+            'value_object_id': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'})
+        },
+        'philo.collection': {
+            'Meta': {'object_name': 'Collection'},
+            'description': ('django.db.models.fields.TextField', [], {'null': 'True', 'blank': 'True'}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'name': ('django.db.models.fields.CharField', [], {'max_length': '255'})
+        },
+        'philo.collectionmember': {
+            'Meta': {'object_name': 'CollectionMember'},
+            'collection': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'members'", 'to': "orm['philo.Collection']"}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'index': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'}),
+            'member_content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']"}),
+            'member_object_id': ('django.db.models.fields.PositiveIntegerField', [], {})
+        },
+        'philo.contentlet': {
+            'Meta': {'object_name': 'Contentlet'},
+            'content': ('philo.models.fields.TemplateField', [], {}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}),
+            'page': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'contentlets'", 'to': "orm['philo.Page']"})
+        },
+        'philo.contentreference': {
+            'Meta': {'object_name': 'ContentReference'},
+            'content_id': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'}),
+            'content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']"}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}),
+            'page': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'contentreferences'", 'to': "orm['philo.Page']"})
+        },
+        'philo.file': {
+            'Meta': {'object_name': 'File'},
+            'file': ('django.db.models.fields.files.FileField', [], {'max_length': '100'}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'mimetype': ('django.db.models.fields.CharField', [], {'max_length': '255'})
+        },
+        'philo.foreignkeyvalue': {
+            'Meta': {'object_name': 'ForeignKeyValue'},
+            'content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']", 'null': 'True', 'blank': 'True'}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'object_id': ('django.db.models.fields.PositiveIntegerField', [], {'null': 'True', 'blank': 'True'})
+        },
+        'philo.jsonvalue': {
+            'Meta': {'object_name': 'JSONValue'},
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'value': ('philo.models.fields.JSONField', [], {})
+        },
+        'philo.manytomanyvalue': {
+            'Meta': {'object_name': 'ManyToManyValue'},
+            'content_type': ('django.db.models.fields.related.ForeignKey', [], {'to': "orm['contenttypes.ContentType']", 'null': 'True', 'blank': 'True'}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'values': ('django.db.models.fields.related.ManyToManyField', [], {'symmetrical': 'False', 'to': "orm['philo.ForeignKeyValue']", 'null': 'True', 'blank': 'True'})
+        },
+        'philo.node': {
+            'Meta': {'object_name': 'Node'},
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'level': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'lft': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'parent': ('django.db.models.fields.related.ForeignKey', [], {'blank': 'True', 'related_name': "'children'", 'null': 'True', 'to': "orm['philo.Node']"}),
+            'rght': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'slug': ('django.db.models.fields.SlugField', [], {'max_length': '255', 'db_index': 'True'}),
+            'tree_id': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'view_content_type': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'node_view_set'", 'to': "orm['contenttypes.ContentType']"}),
+            'view_object_id': ('django.db.models.fields.PositiveIntegerField', [], {})
+        },
+        'philo.page': {
+            'Meta': {'object_name': 'Page'},
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'template': ('django.db.models.fields.related.ForeignKey', [], {'related_name': "'pages'", 'to': "orm['philo.Template']"}),
+            'title': ('django.db.models.fields.CharField', [], {'max_length': '255'})
+        },
+        'philo.redirect': {
+            'Meta': {'object_name': 'Redirect'},
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'status_code': ('django.db.models.fields.IntegerField', [], {'default': '302'}),
+            'target': ('django.db.models.fields.CharField', [], {'max_length': '200'})
+        },
+        'philo.tag': {
+            'Meta': {'object_name': 'Tag'},
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}),
+            'slug': ('django.db.models.fields.SlugField', [], {'unique': 'True', 'max_length': '255', 'db_index': 'True'})
+        },
+        'philo.template': {
+            'Meta': {'object_name': 'Template'},
+            'code': ('philo.models.fields.TemplateField', [], {}),
+            'documentation': ('django.db.models.fields.TextField', [], {'null': 'True', 'blank': 'True'}),
+            'id': ('django.db.models.fields.AutoField', [], {'primary_key': 'True'}),
+            'level': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'lft': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'mimetype': ('django.db.models.fields.CharField', [], {'default': "'text/html'", 'max_length': '255'}),
+            'name': ('django.db.models.fields.CharField', [], {'max_length': '255'}),
+            'parent': ('django.db.models.fields.related.ForeignKey', [], {'blank': 'True', 'related_name': "'children'", 'null': 'True', 'to': "orm['philo.Template']"}),
+            'rght': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'}),
+            'slug': ('django.db.models.fields.SlugField', [], {'max_length': '255', 'db_index': 'True'}),
+            'tree_id': ('django.db.models.fields.PositiveIntegerField', [], {'db_index': 'True'})
+        }
+    }
+
+    complete_apps = ['philo']

diff --git a/models/base.py b/models/base.py
index 03b9b54..c2c12ad 100644 (file)
--- a/models/base.py
+++ b/models/base.py
@@ -10,6 +10,7 @@ from philo.utils import ContentTypeRegistryLimiter, ContentTypeSubclassLimiter
 from philo.signals import entity_class_prepared
 from philo.validators import json_validator
 from UserDict import DictMixin
 from philo.signals import entity_class_prepared
 from philo.validators import json_validator
 from UserDict import DictMixin

+from mptt.models import MPTTModel, MPTTModelBase, MPTTOptions

 
 
 class Tag(models.Model):
 
 
 class Tag(models.Model):


@@ -279,36 +280,17 @@ class Entity(models.Model):
 class TreeManager(models.Manager):
        use_for_related_fields = True
        
 class TreeManager(models.Manager):
        use_for_related_fields = True
        

-       def roots(self):
-               return self.filter(parent__isnull=True)
-       
-       def get_branch_pks(self, root, depth=5, inclusive=True):
-               branch_pks = []
-               parent_pks = [root.pk]
-               
-               if inclusive:
-                       branch_pks.append(root.pk)
-               
-               for i in xrange(depth):
-                       child_pks = list(self.filter(parent__pk__in=parent_pks).exclude(pk__in=branch_pks).values_list('pk', flat=True))
-                       if not child_pks:
-                               break
-                       
-                       branch_pks += child_pks
-                       parent_pks = child_pks
-               
-               return branch_pks
-       
-       def get_branch(self, root, depth=5, inclusive=True):
-               return self.filter(pk__in=self.get_branch_pks(root, depth, inclusive))
-       

        def get_with_path(self, path, root=None, absolute_result=True, pathsep='/', field='slug'):
                """
        def get_with_path(self, path, root=None, absolute_result=True, pathsep='/', field='slug'):
                """

-               Returns the object with the path, unless absolute_result is set to False, in which
-               case it returns a tuple containing the deepest object found along the path, and the
-               remainder of the path after that object as a string (or None if there is no remaining
-               path). Raises a DoesNotExist exception if no object is found with the given path.
+               Given a <pathsep>-separated path, fetch the matching model of this type. If the path
+               you're searching for is known to exist, it is always faster to use absolute_result=True.
+               Unless the path depth is over ~40, in which case the high cost of the absolute query
+               makes a binary search (i.e. non-absolute) faster.

                """
                """

+               # Note: SQLite allows max of 64 tables in one join. That means the binary search will
+               # only work on paths with a max depth of 127 and the absolute fetch will only work
+               # to a max depth of (surprise!) 63. Although this could be handled, chances are your
+               # tree structure won't be that deep.

                segments = path.split(pathsep)
                
                # Check for a trailing pathsep so we can restore it later.
                segments = path.split(pathsep)
                
                # Check for a trailing pathsep so we can restore it later.


@@ -326,11 +308,13 @@ class TreeManager(models.Manager):
                # Special-case a lack of segments. No queries necessary.
                if not segments:
                        if root is not None:
                # Special-case a lack of segments. No queries necessary.
                if not segments:
                        if root is not None:

+                               if absolute_result:
+                                       return root

                                return root, None
                        else:
                                raise self.model.DoesNotExist('%s matching query does not exist.' % self.model._meta.object_name)
                
                                return root, None
                        else:
                                raise self.model.DoesNotExist('%s matching query does not exist.' % self.model._meta.object_name)
                

-               def make_query_kwargs(segments):
+               def make_query_kwargs(segments, root):

                        kwargs = {}
                        prefix = ""
                        revsegs = list(segments)
                        kwargs = {}
                        prefix = ""
                        revsegs = list(segments)


@@ -340,7 +324,12 @@ class TreeManager(models.Manager):
                                kwargs["%s%s__exact" % (prefix, field)] = segment
                                prefix += "parent__"
                        
                                kwargs["%s%s__exact" % (prefix, field)] = segment
                                prefix += "parent__"
                        

-                       kwargs[prefix[:-2]] = root
+                       if not prefix and root is not None:
+                               prefix = "parent__"
+                       
+                       if prefix:
+                               kwargs[prefix[:-2]] = root
+                       

                        return kwargs
                
                def build_path(segments):
                        return kwargs
                
                def build_path(segments):


@@ -350,85 +339,67 @@ class TreeManager(models.Manager):
                        return path
                
                def find_obj(segments, depth, deepest_found):
                        return path
                
                def find_obj(segments, depth, deepest_found):

+                       if deepest_found is None:
+                               deepest_level = 0
+                       else:
+                               deepest_level = deepest_found.get_level() + 1

                        try:
                        try:

-                               obj = self.get(**make_query_kwargs(segments[:depth]))
+                               obj = self.get(**make_query_kwargs(segments[deepest_level:depth], deepest_found))

                        except self.model.DoesNotExist:
                        except self.model.DoesNotExist:

-                               if absolute_result:
-                                       raise
+                               if not deepest_level and depth > 1:
+                                       # make sure there's a root node...
+                                       depth = 1
+                               else:
+                                       # Try finding one with half the path since the deepest find.
+                                       depth = (deepest_level + depth)/2

                                
                                

-                               depth = (deepest_found + depth)/2
-                               if deepest_found == depth:
+                               if deepest_level == depth:

                                        # This should happen if nothing is found with any part of the given path.
                                        raise
                                
                                        # This should happen if nothing is found with any part of the given path.
                                        raise
                                

-                               # Try finding one with half the path since the deepest find.

                                return find_obj(segments, depth, deepest_found)
                        else:
                                return find_obj(segments, depth, deepest_found)
                        else:

-                               # Yay! Found one! Could there be a deeper one?
-                               if absolute_result:
-                                       return obj
+                               # Yay! Found one!
+                               deepest_level = obj.get_level() + 1

                                
                                

-                               deepest_found = depth
-                               depth = (len(segments) + depth)/2
+                               # Could there be a deeper one?
+                               if obj.is_leaf_node():
+                                       return obj, build_path(segments[deepest_level:]) or None

                                
                                

-                               if deepest_found == depth:
-                                       return obj, build_path(segments[deepest_found:]) or None
+                               depth += (len(segments) - depth)/2 or len(segments) - depth
+                               
+                               if depth > deepest_level + obj.get_descendant_count():
+                                       depth = deepest_level + obj.get_descendant_count()
+                               
+                               if deepest_level == depth:
+                                       return obj, build_path(segments[deepest_level:]) or None

                                
                                try:
                                
                                try:

-                                       return find_obj(segments, depth, deepest_found)
+                                       return find_obj(segments, depth, obj)

                                except self.model.DoesNotExist:
                                except self.model.DoesNotExist:

-                                       # Then the deepest one was already found.
-                                       return obj, build_path(segments[deepest_found:])
+                                       # Then this was the deepest.
+                                       return obj, build_path(segments[deepest_level:])

                
                

-               return find_obj(segments, len(segments), 0)
+               if absolute_result:
+                       return self.get(**make_query_kwargs(segments, root))
+               
+               # Try a modified binary search algorithm. Feed the root in so that query complexity
+               # can be reduced. It might be possible to weight the search towards the beginning
+               # of the path, since short paths are more likely, but how far forward? It would
+               # need to shift depending on len(segments) - perhaps logarithmically?
+               return find_obj(segments, len(segments)/2 or len(segments), root)

 
 
 
 

-class TreeModel(models.Model):
+class TreeModel(MPTTModel):

        objects = TreeManager()
        parent = models.ForeignKey('self', related_name='children', null=True, blank=True)
        slug = models.SlugField(max_length=255)
        
        objects = TreeManager()
        parent = models.ForeignKey('self', related_name='children', null=True, blank=True)
        slug = models.SlugField(max_length=255)
        

-       def has_ancestor(self, ancestor, inclusive=False):
-               if inclusive:
-                       parent = self
-               else:
-                       parent = self.parent
-               
-               parents = []
-               
-               while parent:
-                       if parent == ancestor:
-                               return True
-                       # If we've found this parent before, the path is recursive and ancestor wasn't on it.
-                       if parent in parents:
-                               return False
-                       parents.append(parent)
-                       parent = parent.parent
-               # If ancestor is None, catch it here.
-               if parent == ancestor:
-                       return True
-               return False
-       

        def get_path(self, root=None, pathsep='/', field='slug'):
        def get_path(self, root=None, pathsep='/', field='slug'):

-               parent = self.parent
-               parents = [self]
-               
-               def compile_path(parents):
-                       return pathsep.join([getattr(parent, field, '?') for parent in parents])
-               
-               while parent and parent != root:
-                       if parent in parents:
-                               if root is not None:
-                                       raise AncestorDoesNotExist(root)
-                               parents.append(parent)
-                               return u"\u2026%s%s" % (pathsep, compile_path(parents[::-1]))
-                       parents.append(parent)
-                       parent = parent.parent
-               
-               if root is not None and parent is None:
+               if root is not None and not self.is_descendant_of(root):

                        raise AncestorDoesNotExist(root)
                
                        raise AncestorDoesNotExist(root)
                

-               return compile_path(parents[::-1])
+               return pathsep.join([getattr(parent, field, '?') for parent in list(self.get_ancestors()) + [self]])

        path = property(get_path)
        
        def __unicode__(self):
        path = property(get_path)
        
        def __unicode__(self):


@@ -439,7 +410,17 @@ class TreeModel(models.Model):
                abstract = True
 
 
                abstract = True
 
 

+class TreeEntityBase(MPTTModelBase, EntityBase):
+       def __new__(meta, name, bases, attrs):
+               attrs['_mptt_meta'] = MPTTOptions(attrs.pop('MPTTMeta', None))
+               cls = EntityBase.__new__(meta, name, bases, attrs)
+               
+               return meta.register(cls)
+
+

 class TreeEntity(Entity, TreeModel):
 class TreeEntity(Entity, TreeModel):

+       __metaclass__ = TreeEntityBase
+       

        @property
        def attributes(self):
                if self.parent:
        @property
        def attributes(self):
                if self.parent: