a C g@sRdZddlZddlmZddlmZddlmZmZm Z ddl m Z m Z m Z ddlmZmZddlmZdd lmZdd lmZdd lmZmZmZd d Zd&ddZd'ddZddZGdddej j!Z"Gdddej#Z$Gddde%Z&Gddde&Z'Gddde&Z(Gddde&Z)Gd d!d!e'Z*Gd"d#d#e'Z+Gd$d%d%eZ,dS)(zMaterialized Path TreesN)reduce) serializers)models transaction connection)FQValue)ConcatSubstr) gettext_noop)NumConv)Node)InvalidMoveToDescendant PathOverflowNodeAlreadySavedcOs@|dd}|dkr$dd|S|dkr6d|Sd|S)Nvendormysqlz CONCAT({}), microsoftz + z||)popformatjoin)argskwargsrrP/var/www/lab.imftr.de/x/nb_venv/lib/python3.9/site-packages/treebeard/mp_tree.py sql_concats   rcCs|dkrd|Sd|S)NrLEN({})z LENGTH({}))r)fieldrrrr sql_lengths r cKsB|dd}d}|rd}|dkr2|s.d|}d}|j|||dS)NrzSUBSTR({field}, {pos})z SUBSTR({field}, {pos}, {length})rrz#SUBSTRING({field}, {pos}, {length}))rposlength)rr)rr!r"rrfunctionrrr sql_substr"s  r$cCs&|jdj}|jj|kr|S|SdS)a For the given model class, determine what class we should use for the nodes returned by its tree methods (such as get_children). Usually this will be trivially the same as the initial model class, but there are special cases when model inheritance is in use: * If the model extends another via multi-table inheritance, we need to use whichever ancestor originally implemented the tree behaviour (i.e. the one which defines the 'path' field). We can't use the subclass, because it's not guaranteed that the other nodes reachable from the current one will be instances of the same subclass. * If the model is a proxy model, the returned nodes should also use the proxy class. pathN)_meta get_fieldmodelZproxy_for_model)clsZ base_classrrrget_result_class.s r*cs,eZdZdZfddZde_de_ZS)MP_NodeQuerySetzc Custom queryset for the tree node manager. Needed only for the custom delete method. csNi}|ddD]T}d}tdtt|j|jD]"}||j|}||vr2d}qVq2|s|||j<qi}g} |D]\}}||j|jd} | r| |vr| d|| <|| } | r| j dkr| j d8_ | | r| t|jdqv| t|jdqvt|j} | r.| jttj| } n | j} tt| j|i|S) a Custom delete method, will remove all descendant nodes to ensure a consistent tree (no orphans) :returns: tuple of the number of objects deleted and a dictionary with the number of deletions per object type depthr%FTrr%path__startswith)order_byrangeintlenr%steplen _get_basepathitemsr, get_parentnumchildsaveis_leafappendrr*r(objectsfilterroperatoror_nonesuperr+delete)selfrrremovednodefoundr,r%parentsZtoremove parentpathparentr(qset __class__rrrCMs:    zMP_NodeQuerySet.deleteT)__name__ __module__ __qualname____doc__rCZ alters_dataZ queryset_only __classcell__rrrLrr+Fs 5r+c@seZdZdZddZdS)MP_NodeManagerz5Custom manager for nodes in a Materialized Path tree.cCst|jdS)z(Sets the custom queryset as the default.r%)r+r(r1rDrrr get_querysetszMP_NodeManager.get_querysetN)rNrOrPrQrUrrrrrSsrSc@seZdZddZdS) MP_AddHandlercCs g|_dSN)stmtsrTrrr__init__szMP_AddHandler.__init__N)rNrOrPrYrrrrrVsrVc@s0eZdZddZd ddZd dd Zd d ZdS)MP_ComplexAddMoveHandlercCs,|jd}|jD]\}}|||qdS)Nwrite)node_cls_get_database_cursorrXexecute)rDcursorsqlvalsrrr run_sql_stmtss z&MP_ComplexAddMoveHandler.run_sql_stmtsinccCs6dtjt|jjjddd|f}|g}||fS)z5:returns: The sql needed the numchild value of a nodez1UPDATE %s SET numchild=numchild%s1 WHERE path=%%s+-)rcdec)rops quote_namer*r\r&db_table)rDr%Zincdecr`rarrrget_sql_update_numchilds  z0MP_ComplexAddMoveHandler.get_sql_update_numchildNFcCs\|dks|dkrH||krH|}|} |rD|j||| n |dur|}|j|jd|j|jd|d|}|} d| | dd|}|j |j||} d} |rLt |t | krL|j |t t ||j jd} |j | |d} | | krL|rL| |krL|}|} |j | || d } |j||| g}| }|D]*}|j|krnq|||}qX||D]}||j|\}}|j||f|r||jr|d |t |d d}|j|jr|d |jt |d d|_q|rT| r@|j|| | n|j||| || fS) z Handles the reordering of nodes and branches when adding/moving nodes. :returns: A tuple containing the old path and the new path. last-siblingrightN)Z path__gteZpath__gt)leftrl first-siblingr-)rornrlr)get_last_sibling _inc_pathrXr<get_sql_newpath_in_branches get_siblingsr>r%_get_lastpos_in_pathr\ _get_pathr4r6r3r5reverse startswith)rDr!newposnewdepthtargetsiblingsoldpathZ movebranchlastnewpathZbasenumZ tempnewpathZ parentoldpathZ parentnewpathZ movesiblingsZ priorpathrFr`rarrr reorder_nodes_before_add_or_moves          $z9MP_ComplexAddMoveHandler.reorder_nodes_before_add_or_movec Cs|jd}dtjt|jjjf}|dkr6d}ntdt dd|d|d}d|fg}|t |d g}t |t |kr|dkr| d t d|dd |f| |t |d |jjgd }| |d gd|d||f} | |fS)z :returns: The sql needed to move a branch to another position. .. note:: The generated sql will only update the depth values if needed. r[z UPDATE %s SETrzCONCAT(%s, SUBSTR(path, %s))z%sr%rzpath=%sr-zdepth=/%%szWHERE path LIKE %s%z%s %s %sr)r\get_database_vendorrrgrhr*r&rirr$r4r<r extendr5r) rDr}rrZsql1ZsqlpathZsql2raZsql3r`rrrrs s$    z4MP_ComplexAddMoveHandler.get_sql_newpath_in_branches)rc)NF)rNrOrPrbrjrrsrrrrrZs   grZcs$eZdZfddZddZZS)MP_AddRootHandlerc st||_||_dSrW)rBrYr)r)rDr)rrLrrrY2s zMP_AddRootHandler.__init__cCs|j}|r&|jr&|jdi|jS|r4|}n|jddd}t|jdkrxd|jvrx|jd}|jj st dn|jfi|j}d|_ ||_ | |S)Nsorted-siblingr-instanceupdater_cached_parent_objr:)rDrrrrrr`s@       zMP_AddChildHandler.processrrrrLrrYs rcs$eZdZfddZddZZS)MP_AddSiblingHandlerc s(t||_|j|_||_||_dSrW)rBrYrFrMr\r!r)rDrFr!rrLrrrYs  zMP_AddSiblingHandler.__init__c Cs0|j|j|_t|jdkrDd|jvrD|jd}|jjsVtdn|jfi|j}|jj |_ |jdkr|j |j |}z| d }Wntyd}Yn0|durd|_n dg}}||j||jj |j|dd\}}|j||jj d}|r|j||d|||_||S) Nr-rrrrrkFrc)rFZ _prepare_pos_var_for_add_siblingr!r4rrrrr\r,get_sorted_pos_querysetrtallru IndexErrorrr6rXr<rjrbr%r:)rDrr|ryrrrIrrrrs>         zMP_AddSiblingHandler.processrrrrLrrs rcs>eZdZd fdd ZddZddZdd Zd d ZZS) MP_MoveHandlerNcs(t||_|j|_||_||_dSrW)rBrYrFrMr\r{r!)rDrFr{r!rLrrrYs  zMP_MoveHandler.__init__c Cs&|j|j|_|jj}|\}}}|j|jr@ttd||jjkr|jdks|jdvrt|jj|j jks|jdkr|jj|j jkrdS|jdkr|j |j |j}z| d}Wntyd}Yn0|durd|_||j|||j||d\}}||||dS) Nz Can't move node to a descendant.rn)rlrkrorrrkT)rFZ_prepare_pos_var_for_mover!r%update_move_to_child_varsr{is_descendant_ofrrrqZget_first_siblingrrtrrurrsanity_updates_after_moverb)rDr}rzr|ryrrrrrsF        zMP_MoveHandler.processcCs|jddkr2t|t|kr2|j|||j|}|j|}|sR|sb|rZ|rb||kr|rz|j||d|r|j||ddS)z 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 r[rrfrcN)r\rr4rXr< get_mysql_update_depth_in_branch_get_parent_path_from_pathrj)rDr}rZ oldparentpathZ newparentpathrrrrs6    z(MP_MoveHandler.sanity_updates_after_movecCs|jj}d}g}|jdvr||j}|d7}|jrNd}d|_t|jj}n |j|_dddd|j|_|j d7_ |||fS)z=Update preliminar vars in :meth:`move` when moving to a childN)z first-childz last-childz sorted-childr-rorkr) r{r,r!r;r*r\r=rArr9)rDrzryr|rJrrrrs&   z(MP_MoveHandler.update_move_to_child_varscCsP|jd}dtd|ddtjt|jjjf}|jj |dg}||fS)zn :returns: The sql needed to update the depth of all the nodes in a branch. r[UPDATE %s SET depth=r%rz/%%s WHERE path LIKE %%sr) r\rr rrgrhr*r&rir5)rDr%rr`rarrrr8s  z/MP_MoveHandler.get_mysql_update_depth_in_branch)N) rNrOrPrYrrrrrRrrrLrrs 2rc@seZdZdZdZdZgZejdddZ e Z ej ddZ d Z eZd Zed d Zed dZeddZeddZedTddZeddZedUddZeddZedVddZeddZedWd d!Zd"d#Zd$d%Zd&d'Zd(d)Z d*d+Z!d,d-Z"d.d/Z#d0d1Z$d2d3Z%d4d5Z&d6d7Z'dXd8d9Z(d:d;Z)dd?Z+d@dAZ,dYdBdCZ-dZdDdEZ.edFdGZ/edHdIZ0dJdKZ1dLdMZ2edNdOZ3edPdQZ4GdRdSdSZ5d S)[MP_Nodez:Abstract model to create your own Materialized Path Trees.Z$0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZT)runiquer)defaultr-NcCs||SrW) numconv_objZint2strr)numrrr_int2strTszMP_Node._int2strcCs||SrW)rZstr2intrrrr_str2intXszMP_Node._str2intcCs$|jdurtt|j|j|_|jSrW) numconv_obj_r r4alphabetr)rrrr\s zMP_Node.numconv_objcKst|fi|S)z Adds a root node to the tree. This method saves the node in database. The object is populated as if via: ``` obj = cls(**kwargs) ``` :raise PathOverflow: when no more root objects can be added )rr)r)rrrradd_rootbs zMP_Node.add_rootcCst|}|j}|r(|j|jd}gi}}|jjj}t d|D]}|d}|d} t t | |j } |d=|d=|d=||vr||=d|i} |r|d| |<|s| d ks|rt | t |jkr|| n6|| | d } || } d | vrg| d <| d | | || <qH|S) z/Dumps a tree branch to a python data structure.r/pythonfieldsr%r,r9datapkr-children)r*Z_get_serializable_modelr=rr>r%r&rZattnamer serializer3r4r5r<r6)r)rJZkeep_idsrKretZlnkZpk_fieldZpyobjrr%r,rrIZ parentobjrrr dump_bulkqs>      zMP_Node.dump_bulkc CsRt|}|d}ggg}}}gg}}|jD] }d}|jD]"} | |jvrF||jd}qjqF|rpq6t|j|j r||jq6z| dWn$|j y||jYq6Yn0|j t t|j|j kr||jq6|jj||jdjtd|dd|j |j dfgd } | |jkr6||jq6q6|||||fS) ah 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 r[FT path__ranger%rz/%d=%dr-)where)r*rr=rr%rr<rr4r5r8Z DoesNotExistr,r3r>_get_children_path_intervalextrar countr9) r)rZ evil_charsZ bad_steplenZorphansZ wrong_depthZwrong_numchildrFZ found_errorcharZ real_numchildrrr find_problemssB             zMP_Node.find_problemsFcCs@t|}|d}|d}dtd|ddtd|ddtj|jjf}|j |j g}| ||d|j g}|dd krd t d d |dd dtj|jji}nFdt d d |dd}d|d|}|dtj|jji}|d9}| ||ddtj|jji}| D]"}|d|dg}| ||q"|sR|rvaluesr1rr enumerategetrvr4rr_rewrite_node_pathr<)r)Z destructiveZ fix_pathsrr_r`raZsubquery node_dataZchildren_to_fix parent_pathr,rZdesired_sequenceZactual_sequenceZ max_positionitemZactual_positioniZdesired_positionZoccupantold_pathnew_pathZprevious_max_pathrrrfix_trees                   zMP_Node.fix_treecCs2|jj|djtt|tdt|dddS)Nr/r%r-r.)r=r>rr r r r4)r)rrrrrrns zMP_Node._rewrite_node_pathcCsLt|}|dur|jS|r2|jj|jdS|jj|j|jddS)z :returns: A *queryset* of nodes ordered as DFS, including the parent. If no parent is given, the entire tree is returned. Nr)r0Z depth__gter%) r*r=rr;r>rr%r,r1)r)rJrrrget_treews zMP_Node.get_treecCst|jjdddS)z;:returns: A queryset containing the root nodes in the tree.r-r,r%)r*r=r>r1rrrrget_root_nodesszMP_Node.get_root_nodesc Cst|}|d}|r2|jd}||j}d}n d}g}d}tddd|d}d |d |d tj|j j ||j ||d }| d}| ||g} d d|jD} |D]8} |fitt| | dd} | d| _| | q| S)z Helper for a very common case: get a group of siblings and the number of *descendants* in every sibling. r[r-zAND path BETWEEN %s AND %srr%1z%(subpathlen)srz5SELECT * FROM %(table)s AS t1 INNER JOIN (SELECT zi AS subpath, COUNT(1)-1 AS count FROM %(table)s WHERE depth >= %(depth)s %(extrand)s GROUP BY z0) AS t2 ON t1.path=t2.subpath ORDER BY t1.path)rZ subpathlenr,extrandcSsg|] }|dqSrr).0rrrr z7MP_Node.get_descendants_group_count..N)r*rr,rr%r$rrgrhr&rir5r]r^ descriptionrdictzipZdescendants_countr<) r)rJrr,paramsrsubpathr`r_r field_namesrrFrrrget_descendants_group_countsD          z#MP_Node.get_descendants_group_countcCs|jS)z':returns: the depth (level) of the noderrTrrr get_depthszMP_Node.get_depthcCsPt|jjj|jdd}|jdkrL||j|jd}|j||d}|S)zi :returns: A queryset of all the node's siblings, including the node itself. rr%r-r) r*rMr=r>r,r1r6r%r)rDrKrIrrrrts  zMP_Node.get_siblingscCsB|rt|jjSt|jjj|jd||jd dS)z/:returns: A queryset of all the node's childrenr-)r,rr%) r;r*rMr=rAr>r,rr%r1rTrrr get_childrens  zMP_Node.get_childrencCs2z|j|jddWSty,YdS0dS)zi :returns: The next node's sibling, or None if it was the rightmost sibling. rmrN)rtr>r%rrTrrrget_next_siblings zMP_Node.get_next_siblingcCs.|rt|jjS|j|j|jdS)zx :returns: A queryset of all the node's descendants as DFS, doesn't include the node itself r)r;r*rMr=rArexcluderrTrrrget_descendantsszMP_Node.get_descendantscCs6z|j|jddWSty0YdS0dS)zl :returns: The previous node's sibling, or None if it was the leftmost sibling. )Zpath__ltrN)rtr>r%rwrrTrrrget_prev_sibling s zMP_Node.get_prev_siblingcCs|jS)zr :returns: The number the node's children, calculated in the most efficient possible way. rrTrrrget_children_countszMP_Node.get_children_countcCsB|j|jk}|r>|jdkr>||j|jd}|o<|j|S|S)z :returns: ``True`` if the node is a sibling of another node given as an argument, else, returns ``False`` r-)r,r6r%rx)rDrFZauxrIrrr is_sibling_ofs  zMP_Node.is_sibling_ofcCs|j|jo|j|jdkS)z :returns: ``True`` is the node if a child of another node given as an argument, else, returns ``False`` r-r%rxr,rDrFrrr is_child_of(szMP_Node.is_child_ofcCs|j|jo|j|jkS)z :returns: ``True`` if the node is a descendant of another node given as an argument, else, returns ``False`` rrrrrr0szMP_Node.is_descendant_ofcKst|fi|S)a Adds a child to the node. This method saves the node in database. The object is populated as if via: ``` obj = self.__class__(**kwargs) ``` :raise PathOverflow: when no more child nodes can be added )rr)rDrrrr add_child7s zMP_Node.add_childcKst||fi|S)aD Adds a new node as a sibling to the current node object. This method saves the node in database. The object is populated as if via: ``` obj = self.__class__(**kwargs) ``` :raise PathOverflow: when the library can't make room for the node's new position )rr)rDr!rrrrrEs zMP_Node.add_siblingcCs t|jjj|jd|jdS)z4:returns: the root node for the current node object.rr.)r*rMr=rr%r5rTrrrget_rootTs zMP_Node.get_rootcCs |jdkS)z?:returns: True if the node is a root node (else, returns False)r-rrTrrris_rootYszMP_Node.is_rootcCs |jdkS)z?:returns: True if the node is a leaf node (else, returns False)rrrTrrrr;]szMP_Node.is_leafcs\rtjjSfddtdtjjddD}tjjj |d dS)z :returns: A queryset containing the current node object's ancestors, starting by the root node and descending to the parent. csg|]}jd|qSrr.)rr!rTrrrisz)MP_Node.get_ancestors..rr-N)Zpath__inr,) rr*rMr=rAr2r4r%r5r>r1)rDpathsrrTr get_ancestorsas  zMP_Node.get_ancestorscCsxtt|j|j}|dkr dSz|r,|`n|jWSWntyHYn0||j|d}t|jj j |d|_|jS)z :returns: the parent node of the current node object. Caches the result in the object itself to help in loops. r-Nr.) r3r4r%r5rAttributeErrorr6r*rMr=r)rDrr,rIrrrr8ps   zMP_Node.get_parentcCst|||S)z 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 )rr)rDr{r!rrrmovesz MP_Node.movecCs|r|d||jSdS)z;:returns: The base path of another path up to a given depthrr)r5)r)r%r,rrrr6szMP_Node._get_basepathcCs<|||d}||}d||jd|jt||S)z 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 r- {0}{1}{2}r)r6rrrr5r4)r)r%r,ZnewsteprIkeyrrrrvs  zMP_Node._get_pathcCsx||j|j dd}||}t||jkrHttd|jfd|jd|j |jd|jt||S)z<:returns: The path of the next sibling of a given node path.Nr-rrr) rr%r5rr4rrrr)rDryrrrrrrs zMP_Node._inc_pathcCs||j|j dS)z7:returns: The integer value of the last step in a path.N)rr%r5rTrrrruszMP_Node._get_lastpos_in_pathcCs|r|dt||jSdS)z*:returns: The parent path for a given pathrr)r4r5r)r%rrrrsz"MP_Node._get_parent_path_from_pathcCs(||jd|j||jd|jfS)z@:returns: An interval of all possible children paths for a node.rr)rr5rrrrrsz#MP_Node._get_children_path_intervalc@seZdZdZdZdS)z MP_Node.MetazAbstract model.TN)rNrOrPrQZabstractrrrrMetasr)NT)FF)N)N)N)F)N)6rNrOrPrQr5rrrZ CharFieldr%ZPositiveIntegerFieldr,r9ZgaprSr=r classmethodrrrrrrrrrrrrrtrrrrrrrrrrrrr;rr8rr6rvrrrurrrrrrrrEs|      * ;     D             r)N)N)-rQr? functoolsrZ django.corerZ django.dbrrrZdjango.db.modelsrrr Zdjango.db.models.functionsr r Zdjango.utils.translationr rZtreebeard.numconvr Ztreebeard.modelsrZtreebeard.exceptionsrrrrr r$r*queryZQuerySetr+ManagerrSobjectrVrZrrrrrrrrrs2       ? (55