"""Materialized Path Trees""" import sys import operator if sys.version_info >= (3, 0): from functools import reduce from django.core import serializers from django.db import models, transaction, connection from django.db.models import F, Q from django.utils.translation import ugettext_noop as _ from treebeard.numconv import NumConv from treebeard.models import Node from treebeard.exceptions import InvalidMoveToDescendant, PathOverflow class MP_NodeQuerySet(models.query.QuerySet): """ Custom queryset for the tree node manager. Needed only for the customized delete method. """ def delete(self): """ Custom delete method, will remove all descendant nodes to ensure a consistent tree (no orphans) :returns: ``None`` """ # we'll have to manually run through all the nodes that are going # to be deleted and remove nodes from the list if an ancestor is # already getting removed, since that would be redundant removed = {} for node in self.order_by('depth', 'path'): found = False for depth in range(1, int(len(node.path) / node.steplen)): path = node._get_basepath(node.path, depth) if path in removed: # we are already removing a parent of this node # skip found = True break if not found: removed[node.path] = node # ok, got the minimal list of nodes to remove... # we must also remove their children # and update every parent node's numchild attribute # LOTS OF FUN HERE! parents = {} toremove = [] for path, node in removed.items(): parentpath = node._get_basepath(node.path, node.depth - 1) if parentpath: if parentpath not in parents: parents[parentpath] = node.get_parent(True) parent = parents[parentpath] if parent and parent.numchild > 0: parent.numchild -= 1 parent.save() if not node.is_leaf(): toremove.append(Q(path__startswith=node.path)) else: toremove.append(Q(path=node.path)) # Django will handle this as a SELECT and then a DELETE of # ids, and will deal with removing related objects if toremove: qset = self.model.objects.filter(reduce(operator.or_, toremove)) super(MP_NodeQuerySet, qset).delete() transaction.commit_unless_managed() class MP_NodeManager(models.Manager): """Custom manager for nodes.""" def get_query_set(self): """Sets the custom queryset as the default.""" return MP_NodeQuerySet(self.model).order_by('path') class MP_Node(Node): """Abstract model to create your own Materialized Path Trees.""" steplen = 4 alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' node_order_by = [] path = models.CharField(max_length=255, unique=True) depth = models.PositiveIntegerField() numchild = models.PositiveIntegerField(default=0) objects = MP_NodeManager() numconv_obj_ = None @classmethod def _int2str(cls, num): return cls.numconv_obj().int2str(num) @classmethod def _str2int(cls, num): return cls.numconv_obj().str2int(num) @classmethod def numconv_obj(cls): if cls.numconv_obj_ is None: cls.numconv_obj_ = NumConv(len(cls.alphabet), cls.alphabet) return cls.numconv_obj_ @classmethod def add_root(cls, **kwargs): """ Adds a root node to the tree. :raise PathOverflow: when no more root objects can be added """ # do we have a root node already? last_root = cls.get_last_root_node() if last_root and last_root.node_order_by: # there are root nodes and node_order_by has been set # delegate sorted insertion to add_sibling return last_root.add_sibling('sorted-sibling', **kwargs) if last_root: # adding the new root node as the last one newpath = cls._inc_path(last_root.path) else: # adding the first root node newpath = cls._get_path(None, 1, 1) # creating the new object newobj = cls(**kwargs) newobj.depth = 1 newobj.path = newpath # saving the instance before returning it newobj.save() transaction.commit_unless_managed() return newobj @classmethod def dump_bulk(cls, parent=None, keep_ids=True): """Dumps a tree branch to a python data structure.""" # Because of fix_tree, this method assumes that the depth # and numchild properties in the nodes can be incorrect, # so no helper methods are used qset = cls._get_serializable_model().objects.all() if parent: qset = qset.filter(path__startswith=parent.path) ret, lnk = [], {} for pyobj in serializers.serialize('python', qset): # django's serializer stores the attributes in 'fields' fields = pyobj['fields'] path = fields['path'] depth = int(len(path) / cls.steplen) # this will be useless in load_bulk del fields['depth'] del fields['path'] del fields['numchild'] if 'id' in fields: # this happens immediately after a load_bulk del fields['id'] newobj = {'data': fields} if keep_ids: newobj['id'] = pyobj['pk'] if (not parent and depth == 1) or\ (parent and len(path) == len(parent.path)): ret.append(newobj) else: parentpath = cls._get_basepath(path, depth - 1) parentobj = lnk[parentpath] if 'children' not in parentobj: parentobj['children'] = [] parentobj['children'].append(newobj) lnk[path] = newobj return ret @classmethod def find_problems(cls): """ Checks for problems in the tree structure, problems can occur when: 1. your code breaks and you get incomplete transactions (always use transactions!) 2. changing the ``steplen`` value in a model (you must :meth:`dump_bulk` first, change ``steplen`` and then :meth:`load_bulk` :returns: A tuple of five lists: 1. a list of ids of nodes with characters not found in the ``alphabet`` 2. a list of ids of nodes when a wrong ``path`` length according to ``steplen`` 3. a list of ids of orphaned nodes 4. a list of ids of nodes with the wrong depth value for their path 5. a list of ids nodes that report a wrong number of children """ evil_chars, bad_steplen, orphans = [], [], [] wrong_depth, wrong_numchild = [], [] for node in cls.objects.all(): found_error = False for char in node.path: if char not in cls.alphabet: evil_chars.append(node.pk) found_error = True break if found_error: continue if len(node.path) % cls.steplen: bad_steplen.append(node.pk) continue try: node.get_parent(True) except cls.DoesNotExist: orphans.append(node.pk) continue if node.depth != int(len(node.path) / cls.steplen): wrong_depth.append(node.pk) continue real_numchild = cls.objects.filter( path__range=cls._get_children_path_interval(node.path) ).extra( where=['LENGTH(path)/%d=%d' % (cls.steplen, node.depth + 1)] ).count() if real_numchild != node.numchild: wrong_numchild.append(node.pk) continue return evil_chars, bad_steplen, orphans, wrong_depth, wrong_numchild @classmethod def fix_tree(cls, destructive=False): """ Solves some problems that can appear when transactions are not used and a piece of code breaks, leaving the tree in an inconsistent state. The problems this method solves are: 1. Nodes with an incorrect ``depth`` or ``numchild`` values due to incorrect code and lack of database transactions. 2. "Holes" in the tree. This is normal if you move/delete nodes a lot. Holes in a tree don't affect performance, 3. Incorrect ordering of nodes when ``node_order_by`` is enabled. Ordering is enforced on *node insertion*, so if an attribute in ``node_order_by`` is modified after the node is inserted, the tree ordering will be inconsistent. :param destructive: A boolean value. If True, a more agressive fix_tree method will be attemped. If False (the default), it will use a safe (and fast!) fix approach, but it will only solve the ``depth`` and ``numchild`` nodes, it won't fix the tree holes or broken path ordering. .. warning:: Currently what the ``destructive`` method does is: 1. Backup the tree with :meth:`dump_data` 2. Remove all nodes in the tree. 3. Restore the tree with :meth:`load_data` So, even when the primary keys of your nodes will be preserved, this method isn't foreign-key friendly. That needs complex in-place tree reordering, not available at the moment (hint: patches are welcome). """ if destructive: dump = cls.dump_bulk(None, True) cls.objects.all().delete() cls.load_bulk(dump, None, True) else: cursor = cls._get_database_cursor('write') # fix the depth field # we need the WHERE to speed up postgres sql = "UPDATE %s "\ "SET depth=LENGTH(path)/%%s "\ "WHERE depth!=LENGTH(path)/%%s" % ( connection.ops.quote_name(cls._meta.db_table), ) vals = [cls.steplen, cls.steplen] cursor.execute(sql, vals) # fix the numchild field vals = ['_' * cls.steplen] # the cake and sql portability are a lie if cls.get_database_vendor('read') == 'mysql': sql = "SELECT tbn1.path, tbn1.numchild, ("\ "SELECT COUNT(1) "\ "FROM %(table)s AS tbn2 "\ "WHERE tbn2.path LIKE "\ "CONCAT(tbn1.path, %%s)) AS real_numchild "\ "FROM %(table)s AS tbn1 "\ "HAVING tbn1.numchild != real_numchild" % { 'table': connection.ops.quote_name( cls._meta.db_table)} else: subquery = "(SELECT COUNT(1) FROM %(table)s AS tbn2"\ " WHERE tbn2.path LIKE tbn1.path||%%s)" sql = ("SELECT tbn1.path, tbn1.numchild, " + subquery + " FROM %(table)s AS tbn1 WHERE tbn1.numchild != " + subquery) sql = sql % { 'table': connection.ops.quote_name(cls._meta.db_table)} # we include the subquery twice vals *= 2 cursor.execute(sql, vals) sql = "UPDATE %(table)s "\ "SET numchild=%%s "\ "WHERE path=%%s" % { 'table': connection.ops.quote_name(cls._meta.db_table)} for node_data in cursor.fetchall(): vals = [node_data[2], node_data[0]] cursor.execute(sql, vals) transaction.commit_unless_managed() @classmethod def get_tree(cls, parent=None): """ :returns: A *queryset* of nodes ordered as DFS, including the parent. If no parent is given, the entire tree is returned. """ if parent is None: # return the entire tree return cls.objects.all() if not parent.is_leaf(): return cls.objects.filter(path__startswith=parent.path, depth__gte=parent.depth) return cls.objects.filter(pk=parent.pk) @classmethod def get_root_nodes(cls): """:returns: A queryset containing the root nodes in the tree.""" return cls.objects.filter(depth=1) @classmethod def get_descendants_group_count(cls, parent=None): """ Helper for a very common case: get a group of siblings and the number of *descendants* in every sibling. """ #~ # disclaimer: this is the FOURTH implementation I wrote for this # function. I really tried to make it return a queryset, but doing so # with a *single* query isn't trivial with Django's ORM. # ok, I DID manage to make Django's ORM return a queryset here, # defining two querysets, passing one subquery in the tables parameters # of .extra() of the second queryset, using the undocumented order_by # feature, and using a HORRIBLE hack to avoid django quoting the # subquery as a table, BUT (and there is always a but) the hack didn't # survive turning the QuerySet into a ValuesQuerySet, so I just used # good old SQL. # NOTE: in case there is interest, the hack to avoid django quoting the # subquery as a table, was adding the subquery to the alias cache of # the queryset's query object: # # qset.query.quote_cache[subquery] = subquery # # If there is a better way to do this in an UNMODIFIED django 1.0, let # me know. #~ if parent: depth = parent.depth + 1 params = cls._get_children_path_interval(parent.path) extrand = 'AND path BETWEEN %s AND %s' else: depth = 1 params = [] extrand = '' sql = 'SELECT * FROM %(table)s AS t1 INNER JOIN '\ ' (SELECT '\ ' SUBSTR(path, 1, %(subpathlen)s) AS subpath, '\ ' COUNT(1)-1 AS count '\ ' FROM %(table)s '\ ' WHERE depth >= %(depth)s %(extrand)s'\ ' GROUP BY subpath) AS t2 '\ ' ON t1.path=t2.subpath '\ ' ORDER BY t1.path' % { 'table': connection.ops.quote_name(cls._meta.db_table), 'subpathlen': depth * cls.steplen, 'depth': depth, 'extrand': extrand} cursor = cls._get_database_cursor('write') cursor.execute(sql, params) ret = [] field_names = [field[0] for field in cursor.description] for node_data in cursor.fetchall(): node = cls(**dict(zip(field_names, node_data[:-2]))) node.descendants_count = node_data[-1] ret.append(node) transaction.commit_unless_managed() return ret def get_depth(self): """:returns: the depth (level) of the node""" return self.depth def get_siblings(self): """ :returns: A queryset of all the node's siblings, including the node itself. """ qset = self.__class__.objects.filter(depth=self.depth) if self.depth > 1: # making sure the non-root nodes share a parent parentpath = self._get_basepath(self.path, self.depth - 1) qset = qset.filter( path__range=self._get_children_path_interval(parentpath)) return qset def get_children(self): """:returns: A queryset of all the node's children""" if self.is_leaf(): return self.__class__.objects.none() return self.__class__.objects.filter( depth=self.depth + 1, path__range=self._get_children_path_interval(self.path) ) def get_next_sibling(self): """ :returns: The next node's sibling, or None if it was the rightmost sibling. """ try: return self.get_siblings().filter(path__gt=self.path)[0] except IndexError: return None def get_descendants(self): """ :returns: A queryset of all the node's descendants as DFS, doesn't include the node itself """ return self.__class__.get_tree(self).exclude(pk=self.pk) def get_prev_sibling(self): """ :returns: The previous node's sibling, or None if it was the leftmost sibling. """ try: return self.get_siblings().filter(path__lt=self.path).reverse()[0] except IndexError: return None def get_children_count(self): """ :returns: The number the node's children, calculated in the most efficient possible way. """ return self.numchild def is_sibling_of(self, node): """ :returns: ``True`` if the node is a sibling of another node given as an argument, else, returns ``False`` """ aux = self.depth == node.depth # Check non-root nodes share a parent only if they have the same depth if aux and self.depth > 1: # making sure the non-root nodes share a parent parentpath = self._get_basepath(self.path, self.depth - 1) return aux and node.path.startswith(parentpath) return aux def is_child_of(self, node): """ :returns: ``True`` is the node if a child of another node given as an argument, else, returns ``False`` """ return (self.path.startswith(node.path) and self.depth == node.depth + 1) def is_descendant_of(self, node): """ :returns: ``True`` if the node is a descendant of another node given as an argument, else, returns ``False`` """ return self.path.startswith(node.path) and self.depth > node.depth def add_child(self, **kwargs): """ Adds a child to the node. :raise PathOverflow: when no more child nodes can be added """ if not self.is_leaf() and self.node_order_by: # there are child nodes and node_order_by has been set # delegate sorted insertion to add_sibling self.numchild += 1 return self.get_last_child().add_sibling('sorted-sibling', **kwargs) # creating a new object newobj = self.__class__(**kwargs) newobj.depth = self.depth + 1 if not self.is_leaf(): # adding the new child as the last one newobj.path = self._inc_path(self.get_last_child().path) else: # the node had no children, adding the first child newobj.path = self._get_path(self.path, newobj.depth, 1) max_length = newobj.__class__._meta.get_field('path').max_length if len(newobj.path) > max_length: raise PathOverflow( _('The new node is too deep in the tree, try' ' increasing the path.max_length property' ' and UPDATE your database')) # saving the instance before returning it newobj.save() newobj._cached_parent_obj = self self.__class__.objects.filter(path=self.path).update(numchild=F( 'numchild')+1) # we increase the numchild value of the object in memory self.numchild += 1 transaction.commit_unless_managed() return newobj def add_sibling(self, pos=None, **kwargs): """ Adds a new node as a sibling to the current node object. :raise PathOverflow: when the library can't make room for the node's new position """ pos = self._prepare_pos_var_for_add_sibling(pos) # creating a new object newobj = self.__class__(**kwargs) newobj.depth = self.depth if pos == 'sorted-sibling': siblings = self.get_sorted_pos_queryset( self.get_siblings(), newobj) try: newpos = self._get_lastpos_in_path(siblings.all()[0].path) except IndexError: newpos = None if newpos is None: pos = 'last-sibling' else: newpos, siblings = None, [] stmts = [] _, newpath = self._move_add_sibling_aux(pos, newpos, self.depth, self, siblings, stmts, None, False) parentpath = self._get_basepath(newpath, self.depth - 1) if parentpath: stmts.append(self._get_sql_update_numchild(parentpath, 'inc')) cursor = self._get_database_cursor('write') for sql, vals in stmts: cursor.execute(sql, vals) # saving the instance before returning it newobj.path = newpath newobj.save() transaction.commit_unless_managed() return newobj def get_root(self): """:returns: the root node for the current node object.""" return self.__class__.objects.get(path=self.path[0:self.steplen]) def is_leaf(self): """:returns: True if the node is a leaf node (else, returns False)""" return self.numchild == 0 def get_ancestors(self): """ :returns: A queryset containing the current node object's ancestors, starting by the root node and descending to the parent. """ paths = [self.path[0:pos] for pos in range(0, len(self.path), self.steplen)[1:]] return self.__class__.objects.filter(path__in=paths).order_by('depth') def get_parent(self, update=False): """ :returns: the parent node of the current node object. Caches the result in the object itself to help in loops. """ depth = int(len(self.path) / self.steplen) if depth <= 1: return try: if update: del self._cached_parent_obj else: return self._cached_parent_obj except AttributeError: pass parentpath = self._get_basepath(self.path, depth - 1) self._cached_parent_obj = self.__class__.objects.get(path=parentpath) return self._cached_parent_obj def move(self, target, pos=None): """ Moves the current node and all it's descendants to a new position relative to another node. :raise PathOverflow: when the library can't make room for the node's new position """ pos = self._prepare_pos_var_for_move(pos) oldpath = self.path # initialize variables and if moving to a child, updates "move to # child" to become a "move to sibling" if possible (if it can't # be done, it means that we are adding the first child) (pos, target, newdepth, siblings, newpos) = ( self._fix_move_to_child(pos, target) ) if target.is_descendant_of(self): raise InvalidMoveToDescendant( _("Can't move node to a descendant.")) if oldpath == target.path and ( (pos == 'left') or (pos in ('right', 'last-sibling') and target.path == target.get_last_sibling().path) or (pos == 'first-sibling' and target.path == target.get_first_sibling().path)): # special cases, not actually moving the node so no need to UPDATE return if pos == 'sorted-sibling': siblings = self.get_sorted_pos_queryset( target.get_siblings(), self) try: newpos = self._get_lastpos_in_path(siblings.all()[0].path) except IndexError: newpos = None if newpos is None: pos = 'last-sibling' stmts = [] # generate the sql that will do the actual moving of nodes oldpath, newpath = self._move_add_sibling_aux(pos, newpos, newdepth, target, siblings, stmts, oldpath, True) # updates needed for mysql and children count in parents self._updates_after_move(oldpath, newpath, stmts) cursor = self._get_database_cursor('write') for sql, vals in stmts: cursor.execute(sql, vals) transaction.commit_unless_managed() @classmethod def _get_basepath(cls, path, depth): """:returns: The base path of another path up to a given depth""" if path: return path[0:depth * cls.steplen] return '' @classmethod def _get_path(cls, path, depth, newstep): """ Builds a path given some values :param path: the base path :param depth: the depth of the node :param newstep: the value (integer) of the new step """ parentpath = cls._get_basepath(path, depth - 1) key = cls._int2str(newstep) return '%s%s%s' % (parentpath, '0' * (cls.steplen - len(key)), key) @classmethod def _inc_path(cls, path): """:returns: The path of the next sibling of a given node path.""" newpos = cls._str2int(path[-cls.steplen:]) + 1 key = cls._int2str(newpos) if len(key) > cls.steplen: raise PathOverflow(_("Path Overflow from: '%s'" % (path, ))) return '%s%s%s' % (path[:-cls.steplen], '0' * (cls.steplen - len(key)), key) @classmethod def _get_lastpos_in_path(cls, path): """:returns: The integer value of the last step in a path.""" return cls._str2int(path[-cls.steplen:]) @classmethod def _get_parent_path_from_path(cls, path): """:returns: The parent path for a given path""" if path: return path[0:len(path) - cls.steplen] return '' @classmethod def _get_children_path_interval(cls, path): """:returns: An interval of all possible children paths for a node.""" return (path + cls.alphabet[0] * cls.steplen, path + cls.alphabet[-1] * cls.steplen) @classmethod def _move_add_sibling_aux(cls, pos, newpos, newdepth, target, siblings, stmts, oldpath=None, movebranch=False): """ Handles the reordering of nodes and branches when adding/moving nodes. :returns: A tuple containing the old path and the new path. """ if ( (pos == 'last-sibling') or (pos == 'right' and target == target.get_last_sibling()) ): # easy, the last node last = target.get_last_sibling() newpath = cls._inc_path(last.path) if movebranch: stmts.append(cls._get_sql_newpath_in_branches(oldpath, newpath)) else: # do the UPDATE dance if newpos is None: siblings = target.get_siblings() siblings = {'left': siblings.filter(path__gte=target.path), 'right': siblings.filter(path__gt=target.path), 'first-sibling': siblings}[pos] basenum = cls._get_lastpos_in_path(target.path) newpos = {'first-sibling': 1, 'left': basenum, 'right': basenum + 1}[pos] newpath = cls._get_path(target.path, newdepth, newpos) # If the move is amongst siblings and is to the left and there # are siblings to the right of its new position then to be on # the safe side we temporarily dump it on the end of the list tempnewpath = None if movebranch and len(oldpath) == len(newpath): parentoldpath = cls._get_basepath( oldpath, int(len(oldpath) / cls.steplen) - 1 ) parentnewpath = cls._get_basepath(newpath, newdepth - 1) if ( parentoldpath == parentnewpath and siblings and newpath < oldpath ): last = target.get_last_sibling() basenum = cls._get_lastpos_in_path(last.path) tempnewpath = cls._get_path(newpath, newdepth, basenum + 2) stmts.append(cls._get_sql_newpath_in_branches(oldpath, tempnewpath)) # Optimisation to only move siblings which need moving # (i.e. if we've got holes, allow them to compress) movesiblings = [] priorpath = newpath for node in siblings: # If the path of the node is already greater than the path # of the previous node it doesn't need shifting if node.path > priorpath: break # It does need shifting, so add to the list movesiblings.append(node) # Calculate the path that it would be moved to, as that's # the next "priorpath" priorpath = cls._inc_path(node.path) movesiblings.reverse() for node in movesiblings: # moving the siblings (and their branches) at the right of the # related position one step to the right sql, vals = cls._get_sql_newpath_in_branches(node.path, cls._inc_path( node.path)) stmts.append((sql, vals)) if movebranch: if oldpath.startswith(node.path): # if moving to a parent, update oldpath since we just # increased the path of the entire branch oldpath = vals[0] + oldpath[len(vals[0]):] if target.path.startswith(node.path): # and if we moved the target, update the object # django made for us, since the update won't do it # maybe useful in loops target.path = vals[0] + target.path[len(vals[0]):] if movebranch: # node to move if tempnewpath: stmts.append(cls._get_sql_newpath_in_branches(tempnewpath, newpath)) else: stmts.append(cls._get_sql_newpath_in_branches(oldpath, newpath)) return oldpath, newpath def _fix_move_to_child(self, pos, target): """Update preliminar vars in :meth:`move` when moving to a child""" newdepth = target.depth newpos = None siblings = [] if pos in ('first-child', 'last-child', 'sorted-child'): # moving to a child parent = target newdepth += 1 if target.is_leaf(): # moving as a target's first child newpos = 1 pos = 'first-sibling' siblings = self.__class__.objects.none() else: target = target.get_last_child() pos = {'first-child': 'first-sibling', 'last-child': 'last-sibling', 'sorted-child': 'sorted-sibling'}[pos] # this is not for save(), since if needed, will be handled with a # custom UPDATE, this is only here to update django's object, # should be useful in loops parent.numchild += 1 return pos, target, newdepth, siblings, newpos @classmethod def _updates_after_move(cls, oldpath, newpath, stmts): """ Updates the list of sql statements needed after moving nodes. 1. :attr:`depth` updates *ONLY* needed by mysql databases (*sigh*) 2. update the number of children of parent nodes """ if ( cls.get_database_vendor('write') == 'mysql' and len(oldpath) != len(newpath) ): # no words can describe how dumb mysql is # we must update the depth of the branch in a different query stmts.append(cls._get_sql_update_depth_in_branch(newpath)) oldparentpath = cls._get_parent_path_from_path(oldpath) newparentpath = cls._get_parent_path_from_path(newpath) if (not oldparentpath and newparentpath) or\ (oldparentpath and not newparentpath) or\ (oldparentpath != newparentpath): # node changed parent, updating count if oldparentpath: stmts.append(cls._get_sql_update_numchild(oldparentpath, 'dec')) if newparentpath: stmts.append(cls._get_sql_update_numchild(newparentpath, 'inc')) @classmethod def _get_sql_newpath_in_branches(cls, oldpath, newpath): """ :returns" The sql needed to move a branch to another position. .. note:: The generated sql will only update the depth values if needed. """ vendor = cls.get_database_vendor('write') sql1 = "UPDATE %s SET" % ( connection.ops.quote_name(cls._meta.db_table), ) # <3 "standard" sql if vendor == 'sqlite': # I know that the third argument in SUBSTR (LENGTH(path)) is # awful, but sqlite fails without it: # OperationalError: wrong number of arguments to function substr() # even when the documentation says that 2 arguments are valid: # http://www.sqlite.org/lang_corefunc.html sqlpath = "%s||SUBSTR(path, %s, LENGTH(path))" elif vendor == 'mysql': # hooray for mysql ignoring standards in their default # configuration! # to make || work as it should, enable ansi mode # http://dev.mysql.com/doc/refman/5.0/en/ansi-mode.html sqlpath = "CONCAT(%s, SUBSTR(path, %s))" else: sqlpath = "%s||SUBSTR(path, %s)" sql2 = ["path=%s" % (sqlpath, )] vals = [newpath, len(oldpath) + 1] if len(oldpath) != len(newpath) and vendor != 'mysql': # when using mysql, this won't update the depth and it has to be # done in another query # doesn't even work with sql_mode='ANSI,TRADITIONAL' # TODO: FIND OUT WHY?!?? right now I'm just blaming mysql sql2.append("depth=LENGTH(%s)/%%s" % (sqlpath, )) vals.extend([newpath, len(oldpath) + 1, cls.steplen]) sql3 = "WHERE path LIKE %s" vals.extend([oldpath + '%']) sql = '%s %s %s' % (sql1, ', '.join(sql2), sql3) return sql, vals @classmethod def _get_sql_update_depth_in_branch(cls, path): """ :returns: The sql needed to update the depth of all the nodes in a branch. """ # Right now this is only used by *sigh* mysql. sql = "UPDATE %s SET depth=LENGTH(path)/%%s"\ " WHERE path LIKE %%s" % ( connection.ops.quote_name(cls._meta.db_table), ) vals = [cls.steplen, path + '%'] return sql, vals @classmethod def _get_sql_update_numchild(cls, path, incdec='inc'): """:returns: The sql needed the numchild value of a node""" sql = "UPDATE %s SET numchild=numchild%s1"\ " WHERE path=%%s" % ( connection.ops.quote_name(cls._meta.db_table), {'inc': '+', 'dec': '-'}[incdec]) vals = [path] return sql, vals class Meta: """Abstract model.""" abstract = True