- def container_nodes(template):
- def nodelist_container_nodes(nodelist):
- nodes = []
- for node in nodelist:
- try:
- for nodelist_name in ('nodelist', 'nodelist_loop', 'nodelist_empty', 'nodelist_true', 'nodelist_false', 'nodelist_main'):
- if hasattr(node, nodelist_name):
- nodes.extend(nodelist_container_nodes(getattr(node, nodelist_name)))
- if isinstance(node, ContainerNode):
- nodes.append(node)
- elif isinstance(node, ExtendsNode):
- extended_template = node.get_parent(Context())
- if extended_template:
- nodes.extend(container_nodes(extended_template))
- elif isinstance(node, ConstantIncludeNode):
- included_template = node.template
- if included_template:
- nodes.extend(container_nodes(included_template))
- elif isinstance(node, IncludeNode):
- included_template = get_template(node.template_name.resolve(Context()))
- if included_template:
- nodes.extend(container_nodes(included_template))
- except:
- pass # fail for this node
- return nodes
- return nodelist_container_nodes(template.nodelist)
- all_nodes = container_nodes(self.django_template)
- contentlet_node_names = set([node.name for node in all_nodes if not node.references])
- contentreference_node_names = []
- contentreference_node_specs = []
- for node in all_nodes:
- if node.references and node.name not in contentreference_node_names:
- contentreference_node_specs.append((node.name, node.references))
- contentreference_node_names.append(node.name)
- return contentlet_node_names, contentreference_node_specs
-
- def __unicode__(self):
- return self.get_path(u' › ', 'name')
-
- @staticmethod
- @fattr(is_usable=True)
- def loader(template_name, template_dirs=None): # load_template_source
- try:
- template = Template.objects.get_with_path(template_name)
- except Template.DoesNotExist:
- raise TemplateDoesNotExist(template_name)
- return (template.code, template.origin)
-
- class Meta:
- app_label = 'philo'
+ # 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.
+ trailing_pathsep = False
+ if segments[-1] == '':
+ trailing_pathsep = True
+
+ # Clean out blank segments. Handles multiple consecutive pathseps.
+ while True:
+ try:
+ segments.remove('')
+ except ValueError:
+ break
+
+ # 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)
+
+ def make_query_kwargs(segments, root):
+ kwargs = {}
+ prefix = ""
+ revsegs = list(segments)
+ revsegs.reverse()
+
+ for segment in revsegs:
+ kwargs["%s%s__exact" % (prefix, field)] = segment
+ prefix += "parent__"
+
+ if prefix:
+ kwargs[prefix[:-2]] = root
+
+ return kwargs
+
+ def build_path(segments):
+ path = pathsep.join(segments)
+ if trailing_pathsep and segments and segments[-1] != '':
+ path += pathsep
+ return path
+
+ def find_obj(segments, depth, deepest_found=None):
+ if deepest_found is None:
+ deepest_level = 0
+ elif root is None:
+ deepest_level = deepest_found.get_level() + 1
+ else:
+ deepest_level = deepest_found.get_level() - root.get_level()
+ try:
+ obj = self.get(**make_query_kwargs(segments[deepest_level:depth], deepest_found or root))
+ except self.model.DoesNotExist:
+ 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
+
+ if deepest_level == depth:
+ # This should happen if nothing is found with any part of the given path.
+ if root is not None and deepest_found is None:
+ return root, build_path(segments)
+ raise
+
+ return find_obj(segments, depth, deepest_found)
+ else:
+ # Yay! Found one!
+ if root is None:
+ deepest_level = obj.get_level() + 1
+ else:
+ deepest_level = obj.get_level() - root.get_level()
+
+ # Could there be a deeper one?
+ if obj.is_leaf_node():
+ return obj, build_path(segments[deepest_level:]) 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:
+ return find_obj(segments, depth, obj)
+ except self.model.DoesNotExist:
+ # Then this was the deepest.
+ return obj, build_path(segments[deepest_level:])
+
+ 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))
git.ithinksw.org / philo.git / blobdiff