#encoding: utf-8
from UserDict import DictMixin
+from hashlib import sha1
+from django.contrib.sites.models import Site
+from django.core.cache import cache
from django.core.exceptions import ValidationError
from django.core.urlresolvers import NoReverseMatch
from django.core.validators import RegexValidator, MinValueValidator
class NavigationMapper(object, DictMixin):
"""
- The :class:`NavigationMapper` is a dictionary-like object which allows easy fetching of the root items of a navigation for a node according to a key. The fetching goes through the :class:`NavigationManager` and can thus take advantage of the navigation cache. A :class:`NavigationMapper` instance will be available on each node instance as :attr:`Node.navigation` if :mod:`~philo.contrib.shipherd` is in the :setting:`INSTALLED_APPS`
+ The :class:`NavigationMapper` is a dictionary-like object which allows easy fetching of the root items of a navigation for a node according to a key. A :class:`NavigationMapper` instance will be available on each node instance as :attr:`Node.navigation` if :mod:`~philo.contrib.shipherd` is in the :setting:`INSTALLED_APPS`
"""
def __init__(self, node):
self.node = node
+ self._cache = {}
def __getitem__(self, key):
- return Navigation.objects.get_cache_for(self.node)[key]['root_items']
-
- def keys(self):
- return Navigation.objects.get_cache_for(self.node).keys()
+ if key not in self._cache:
+ try:
+ self._cache[key] = Navigation.objects.get_for_node(self.node, key)
+ except Navigation.DoesNotExist:
+ self._cache[key] = None
+ return self._cache[key]
def navigation(self):
Node.navigation = property(navigation)
-class NavigationCacheQuerySet(models.query.QuerySet):
- """
- This subclass will trigger general cache clearing for Navigation.objects when a mass
- update or deletion is performed. As there is no convenient way to iterate over the
- changed or deleted instances, there's no way to be more precise about what gets cleared.
-
- """
- def update(self, *args, **kwargs):
- super(NavigationCacheQuerySet, self).update(*args, **kwargs)
- Navigation.objects.clear_cache()
-
- def delete(self, *args, **kwargs):
- super(NavigationCacheQuerySet, self).delete(*args, **kwargs)
- Navigation.objects.clear_cache()
-
-
class NavigationManager(models.Manager):
- """
- Since navigation on a site will be hit frequently, is relatively costly to compute, and is changed relatively infrequently, the NavigationManager maintains a cache which maps nodes to navigations.
-
- """
use_for_related = True
- _cache = {}
- def get_query_set(self):
- """
- Returns a :class:`NavigationCacheQuerySet` instance.
-
- """
- return NavigationCacheQuerySet(self.model, using=self._db)
-
- def get_cache_for(self, node, update_targets=True):
- """Returns the navigation cache for a given :class:`.Node`. If update_targets is ``True``, then :meth:`update_targets_for` will be run with the :class:`.Node`."""
- created = False
- if not self.has_cache_for(node):
- self.create_cache_for(node)
- created = True
-
- if update_targets and not created:
- self.update_targets_for(node)
-
- return self.__class__._cache[self.db][node]
-
- def has_cache_for(self, node):
- """Returns ``True`` if a cache exists for the :class:`.Node` and ``False`` otherwise."""
- return self.db in self.__class__._cache and node in self.__class__._cache[self.db]
-
- def create_cache_for(self, node):
- """This method loops through the :class:`.Node`\ s ancestors and caches all unique navigation keys."""
- ancestors = node.get_ancestors(ascending=True, include_self=True)
-
- nodes_to_cache = []
-
- for node in ancestors:
- if self.has_cache_for(node):
- cache = self.get_cache_for(node).copy()
- break
- else:
- nodes_to_cache.insert(0, node)
- else:
- cache = {}
-
- for node in nodes_to_cache:
- cache = cache.copy()
- cache.update(self._build_cache_for(node))
- self.__class__._cache.setdefault(self.db, {})[node] = cache
-
- def _build_cache_for(self, node):
- cache = {}
- tree_id_attr = NavigationItem._mptt_meta.tree_id_attr
- level_attr = NavigationItem._mptt_meta.level_attr
-
- for navigation in node.navigation_set.all():
- tree_ids = navigation.roots.values_list(tree_id_attr)
- items = list(NavigationItem.objects.filter(**{'%s__in' % tree_id_attr: tree_ids, '%s__lt' % level_attr: navigation.depth}).order_by('order', 'lft'))
+ def get_for_node(self, node, key):
+ cache_key = self._get_cache_key(node, key)
+ cached = cache.get(cache_key)
+
+ if cached is None:
+ opts = Node._mptt_meta
+ left = getattr(node, opts.left_attr)
+ right = getattr(node, opts.right_attr)
+ tree_id = getattr(node, opts.tree_id_attr)
+ kwargs = {
+ "node__%s__lte" % opts.left_attr: left,
+ "node__%s__gte" % opts.right_attr: right,
+ "node__%s" % opts.tree_id_attr: tree_id
+ }
+ navs = self.filter(key=key, **kwargs).select_related('node').order_by('-node__%s' % opts.level_attr)
+ nav = navs[0]
+ roots = nav.roots.all().select_related('target_node').order_by('order')
+ item_opts = NavigationItem._mptt_meta
+ by_pk = {}
+ tree_ids = []
- root_items = []
+ site_root_node = Site.objects.get_current().root_node
- for item in items:
- item._is_cached = True
-
- if not hasattr(item, '_cached_children'):
- item._cached_children = []
-
- if item.parent:
- # alternatively, if I don't want to force it to a list, I could keep track of
- # instances where the parent hasn't yet been met and do this step later for them.
- # delayed action.
- item.parent = items[items.index(item.parent)]
- if not hasattr(item.parent, '_cached_children'):
- item.parent._cached_children = []
- item.parent._cached_children.append(item)
- else:
- root_items.append(item)
+ for root in roots:
+ by_pk[root.pk] = root
+ tree_ids.append(getattr(root, item_opts.tree_id_attr))
+ root._cached_children = []
+ if root.target_node:
+ root.target_node.get_path(root=site_root_node)
+ root.navigation = nav
- cache[navigation.key] = {
- 'navigation': navigation,
- 'root_items': root_items,
- 'items': items
+ kwargs = {
+ '%s__in' % item_opts.tree_id_attr: tree_ids,
+ '%s__lt' % item_opts.level_attr: nav.depth,
+ '%s__gt' % item_opts.level_attr: 0
}
+ items = NavigationItem.objects.filter(**kwargs).select_related('target_node').order_by('level', 'order')
+ for item in items:
+ by_pk[item.pk] = item
+ item._cached_children = []
+ parent_pk = getattr(item, '%s_id' % item_opts.parent_attr)
+ item.parent = by_pk[parent_pk]
+ item.parent._cached_children.append(item)
+ if item.target_node:
+ item.target_node.get_path(root=site_root_node)
+
+ cached = roots
+ cache.set(cache_key, cached)
- return cache
-
- def clear_cache_for(self, node):
- """Clear the cache for the :class:`.Node` and all its descendants. The navigation for this node has probably changed, and it isn't worth it to figure out which descendants were actually affected by this."""
- if not self.has_cache_for(node):
- # Already cleared.
- return
-
- descendants = node.get_descendants(include_self=True)
- cache = self.__class__._cache[self.db]
- for node in descendants:
- cache.pop(node, None)
+ return cached
- def update_targets_for(self, node):
- """Manually updates the target nodes for the :class:`.Node`'s cache in case something's changed there. This is a less complex operation than rebuilding the :class:`.Node`'s cache."""
- caches = self.__class__._cache[self.db][node].values()
-
- target_pks = set()
-
- for cache in caches:
- target_pks |= set([item.target_node_id for item in cache['items']])
-
- # A distinct query is not strictly necessary. TODO: benchmark the efficiency
- # with/without distinct.
- targets = list(Node.objects.filter(pk__in=target_pks).distinct())
+ def _get_cache_key(self, node, key):
+ opts = Node._mptt_meta
+ left = getattr(node, opts.left_attr)
+ right = getattr(node, opts.right_attr)
+ tree_id = getattr(node, opts.tree_id_attr)
+ parent_id = getattr(node, "%s_id" % opts.parent_attr)
- for cache in caches:
- for item in cache['items']:
- if item.target_node_id:
- item.target_node = targets[targets.index(item.target_node)]
-
- def clear_cache(self):
- """Clears the manager's entire navigation cache."""
- self.__class__._cache.pop(self.db, None)
+ return sha1(unicode(left) + unicode(right) + unicode(tree_id) + unicode(parent_id) + unicode(node.pk) + unicode(key)).hexdigest()
class Navigation(Entity):
#: There is no limit to the depth of a tree of :class:`NavigationItem`\ s, but ``depth`` will limit how much of the tree will be displayed.
depth = models.PositiveSmallIntegerField(default=DEFAULT_NAVIGATION_DEPTH, validators=[MinValueValidator(1)], help_text="Defines the maximum display depth of this navigation.")
- def __init__(self, *args, **kwargs):
- super(Navigation, self).__init__(*args, **kwargs)
- self._initial_data = model_to_dict(self)
-
def __unicode__(self):
return "%s[%s]" % (self.node, self.key)
- def _has_changed(self):
- return self._initial_data != model_to_dict(self)
-
- def save(self, *args, **kwargs):
- super(Navigation, self).save(*args, **kwargs)
-
- if self._has_changed():
- Navigation.objects.clear_cache_for(self.node)
- self._initial_data = model_to_dict(self)
-
- def delete(self, *args, **kwargs):
- super(Navigation, self).delete(*args, **kwargs)
- Navigation.objects.clear_cache_for(self.node)
-
class Meta:
unique_together = ('node', 'key')
-class NavigationItemManager(TreeEntityManager):
- use_for_related = True
-
- def get_query_set(self):
- """Returns a :class:`NavigationCacheQuerySet` instance."""
- return NavigationCacheQuerySet(self.model, using=self._db)
-
-
class NavigationItem(TreeEntity, TargetURLModel):
- #: A :class:`NavigationItemManager` instance
- objects = NavigationItemManager()
-
#: A :class:`ForeignKey` to a :class:`Navigation` instance. If this is not null, then the :class:`NavigationItem` will be a root node of the :class:`Navigation` instance.
navigation = models.ForeignKey(Navigation, blank=True, null=True, related_name='roots', help_text="Be a root in this navigation tree.")
#: The text which will be displayed in the navigation. This is a :class:`CharField` instance with max length 50.
#: The order in which the :class:`NavigationItem` will be displayed.
order = models.PositiveSmallIntegerField(default=0)
- def __init__(self, *args, **kwargs):
- super(NavigationItem, self).__init__(*args, **kwargs)
- self._initial_data = model_to_dict(self)
- self._is_cached = False
-
def get_path(self, root=None, pathsep=u' › ', field='text'):
return super(NavigationItem, self).get_path(root, pathsep, field)
path = property(get_path)
# the same as the request path, check whether the target node is an ancestor
# of the requested node. If so, this is active unless the target node
# is the same as the ``host node`` for this navigation structure.
- try:
- host_node = self.get_root().navigation.node
- except AttributeError:
- pass
- else:
- if self.target_node != host_node and self.target_node.is_ancestor_of(request.node):
- return True
+ root = self
+
+ # The common case will be cached items, whose parents are cached with them.
+ while root.parent is not None:
+ root = root.parent
+
+ host_node_id = root.navigation.node_id
+ if self.target_node.pk != host_node_id and self.target_node.is_ancestor_of(request.node):
+ return True
return False
for child in self.get_children():
if child.is_active(request) or child.has_active_descendants(request):
return True
- return False
-
- def _has_changed(self):
- if model_to_dict(self) == self._initial_data:
- return False
- return True
-
- def _clear_cache(self):
- try:
- root = self.get_root()
- if self.get_level() < root.navigation.depth:
- Navigation.objects.clear_cache_for(self.get_root().navigation.node)
- except AttributeError:
- pass
-
- def save(self, *args, **kwargs):
- super(NavigationItem, self).save(*args, **kwargs)
-
- if self._has_changed():
- self._clear_cache()
-
- def delete(self, *args, **kwargs):
- super(NavigationItem, self).delete(*args, **kwargs)
- self._clear_cache()
\ No newline at end of file
+ return False
\ No newline at end of file
objects = TreeEntityManager()
parent = models.ForeignKey('self', related_name='children', null=True, blank=True)
- def get_path(self, root=None, pathsep='/', field='slug'):
+ def get_path(self, root=None, pathsep='/', field='pk', memoize=True):
"""
:param root: Only return the path since this object.
:param pathsep: The path separator to use when constructing an instance's path
:param field: The field to pull path information from for each ancestor.
+ :param memoize: Whether to use memoized results. Since, in most cases, the ancestors of a TreeEntity will not change over the course of an instance's lifetime, this defaults to ``True``.
:returns: A string representation of an object's path.
"""
if root == self:
return ''
- if root is None and self.is_root_node():
+ parent_id = getattr(self, "%s_id" % self._mptt_meta.parent_attr)
+ if getattr(root, 'pk', None) == parent_id:
return getattr(self, field, '?')
if root is not None and not self.is_descendant_of(root):
raise AncestorDoesNotExist(root)
+ if memoize:
+ memo_args = (parent_id, getattr(root, 'pk', None), pathsep, getattr(self, field, '?'))
+ try:
+ return self._path_memo[memo_args]
+ except AttributeError:
+ self._path_memo = {}
+ except KeyError:
+ pass
+
qs = self.get_ancestors(include_self=True)
if root is not None:
qs = qs.filter(**{'%s__gt' % self._mptt_meta.level_attr: root.get_level()})
- return pathsep.join([getattr(parent, field, '?') for parent in qs])
+ path = pathsep.join([getattr(parent, field, '?') for parent in qs])
+
+ if memoize:
+ self._path_memo[memo_args] = path
+
+ return path
path = property(get_path)
def get_attribute_mapper(self, mapper=None):
"""
if mapper is None:
- if self.parent:
+ if getattr(self, "%s_id" % self._mptt_meta.parent_attr):
mapper = TreeAttributeMapper
else:
mapper = AttributeMapper
objects = SlugTreeEntityManager()
slug = models.SlugField(max_length=255)
- def get_path(self, root=None, pathsep='/', field='slug'):
- return super(SlugTreeEntity, self).get_path(root, pathsep, field)
+ def get_path(self, root=None, pathsep='/', field='slug', memoize=True):
+ return super(SlugTreeEntity, self).get_path(root, pathsep, field, memoize)
path = property(get_path)
def clean(self):
- if self.parent is None:
+ if getattr(self, "%s_id" % self._mptt_meta.parent_attr) is None:
try:
self._default_manager.exclude(pk=self.pk).get(slug=self.slug, parent__isnull=True)
except self.DoesNotExist:
git.ithinksw.org / philo.git / commitdiff