Show
Ignore:
Timestamp:
06/19/06 01:44:47 (2 years ago)
Author:
fguillaume
Message:

Order is now recorded and checked.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • Python/nuxeo.treedelta/trunk/src/nuxeo/treedelta/README.txt

    r46578 r46579  
    4141    >>> from nuxeo.treedelta import ADD, REMOVE, MODIFY 
    4242    >>> from nuxeo.treedelta import TreeDelta 
    43     >>> from nuxeo.treedelta import Ordering 
    4443 
    4544    >>> tree = TreeDelta([]) 
    …… 
    8382    >>> TreeDelta([(ADD, 'A'), (REMOVE, 'A'), (ADD, 'A')]) 
    8483    TreeDelta([(ADD, 'A')]) 
     84 
     85    >>> TreeDelta([(ADD, 'AB'), (REMOVE, 'AB')]) 
     86    TreeDelta([(REMOVE, 'AB')]) 
    8587 
    8688    >>> TreeDelta([(ADD, 'A'), (ADD, 'AB'), (REMOVE, 'AB')]) 
    …… 
    204206made in a row on the same node. Then, their `info` mappings are merged:: 
    205207 
    206     >>> tree = TreeDelta([(MODIFY, 'A', {'foo': 1}), 
    207     ...                       (MODIFY, 'A', {'bar': 2})]) 
    208     >>> list(tree.get()) == [(MODIFY, 'A', {'foo': 1, 'bar': 2})] 
    209     True 
     208    >>> TreeDelta([(MODIFY, 'A', {'foo': 1}), 
     209    ...            (MODIFY, 'A', {'bar': 2})]) 
     210    TreeDelta([(MODIFY, 'A', {'foo': 1, 'bar': 2})]) 
    210211 
    211212For some specific application use cases, it's possible to override the 
    …… 
    254255  a reordeing operation has been done. 
    255256 
    256 Let's see the first case of partial orderings first: 
     257Full ordering, if available, is returned when the tree is queried:: 
    257258 
    258259    >>> tree = TreeDelta([(ADD, 'A'), (ADD, 'AB'), (ADD, 'AC')]) 
    259     >>> tree 
    260     ... # doctest: +NORMALIZE_WHITESPACE 
    261     TreeDelta([(ADD, 'A', {Ordering: ['B', 'C']}), 
    262                (ADD, 'AB'), 
    263                (ADD, 'AC')]) 
     260    >>> tree.add(MODIFY, 'A', order=['C', 'B']) 
     261    >>> tree 
     262    TreeDelta([(ADD, 'A', {}, ['C', 'B']), (ADD, 'AB'), (ADD, 'AC')]) 
     263 
     264Various checks are made to ensure ordering is always sane:: 
     265 
     266    >>> tree = TreeDelta() 
     267    >>> tree.add(MODIFY, 'A', order=['B']) 
     268    >>> tree.add(REMOVE, 'ABC') 
     269    >>> tree.add(ADD, 'AB') 
     270    Traceback (most recent call last): 
     271    ... 
     272    TreeError: ADD 'AB' already in parent order 
     273 
     274    >>> tree = TreeDelta() 
     275    >>> tree.add(MODIFY, 'A', order=['B']) 
     276    >>> tree.add(MODIFY, 'A', order=['C']) 
     277    Traceback (most recent call last): 
     278    ... 
     279    TreeError: Bad reordering: ['B'] to ['C'] 
     280 
     281    >>> tree = TreeDelta() 
     282    >>> tree.add(ADD, 'AB') 
     283    >>> tree.add(MODIFY, 'A', order=['C']) 
     284    Traceback (most recent call last): 
     285    ... 
     286    TreeError: Order doesn't mention ['B'] 
     287 
     288    >>> tree = TreeDelta([(MODIFY, 'AB')]) 
     289    >>> tree.add(MODIFY, 'A', order=['C']) 
     290    Traceback (most recent call last): 
     291    ... 
     292    TreeError: Order doesn't mention ['B'] 
     293 
     294    >>> tree = TreeDelta() 
     295    >>> tree.add(MODIFY, 'A', order=['B']) 
     296    >>> tree.add(ADD, 'AB') 
     297    Traceback (most recent call last): 
     298    ... 
     299    TreeError: ADD 'AB' already in parent order 
     300 
     301    >>> tree = TreeDelta() 
     302    >>> tree.add(MODIFY, 'A', order=['B']) 
     303    >>> tree.add(REMOVE, 'AC') 
     304    Traceback (most recent call last): 
     305    ... 
     306    TreeError: REMOVE 'AC' not in parent order 
     307 

  • Python/nuxeo.treedelta/trunk/src/nuxeo/treedelta/__init__.py

    r46578 r46579  
    2323from nuxeo.treedelta.simpletreedelta import SimpleTreeDelta 
    2424from nuxeo.treedelta.treedelta import TreeError 
    25 from nuxeo.treedelta.treedelta import ADD, REMOVE, MODIFY, ORDER 
    26 from nuxeo.treedelta.treedelta import Ordering 
     25from nuxeo.treedelta.treedelta import ADD, REMOVE, MODIFY 

  • Python/nuxeo.treedelta/trunk/src/nuxeo/treedelta/tests/SIMPLE.txt

    r46577 r46579  
    208208made in a row on the same node. Then, their `info` mappings are merged:: 
    209209 
    210     >>> tree = SimpleTreeDelta([(MODIFY, 'A', {'foo': 1}), 
    211     ...                          (MODIFY, 'A', {'bar': 2})]) 
    212     >>> list(tree.get()) == [(MODIFY, 'A', {'foo': 1, 'bar': 2})] 
    213     True 
     210    >>> SimpleTreeDelta([(MODIFY, 'A', {'foo': 1}), 
     211    ...                  (MODIFY, 'A', {'bar': 2})]) 
     212    SimpleTreeDelta([(MODIFY, 'A', {'foo': 1, 'bar': 2})]) 
    214213 
    215214For some specific application use cases, it's possible to override the 

  • Python/nuxeo.treedelta/trunk/src/nuxeo/treedelta/treedelta.py

    r46578 r46579  
    4040REMOVE = 2 
    4141MODIFY = 3 
    42 ORDER = 4 
    4342# Internal to the tree representation 
    4443_SEEN = 5 
    …… 
    4847    REMOVE: 'REMOVE', 
    4948    MODIFY: 'MODIFY', 
    50     ORDER: 'ORDER', 
    5149    _SEEN: '_SEEN', 
    5250    }.get 
    53  
    54  
    55 class _Token(object): 
    56     def __init__(self, name): 
    57         self.name = name 
    58     def __repr__(self): 
    59         return self.name 
    60 Ordering = _Token('Ordering') 
    61 PartialOrdering = _Token('PartialOrdering') 
    6251 
    6352 
    …… 
    7362        self.order_total = False 
    7463        self.children = {} 
     64 
    7565    def __repr__(self): 
    7666        args = [printop(self.op)] 
    …… 
    8171        return 'Node(%s)' % ', '.join(args) 
    8272 
    83  
     73class Item(object): 
     74    """Flattened version of a Node. 
     75    """ 
     76    def __init__(self, node, path): 
     77        self.op = node.op 
     78        self.path = path 
     79        self.info = node.info.copy() 
     80        if node.order_total: 
     81            self.order = list(node.order) 
     82        else: 
     83            self.order = None 
     84 
     85    def __repr__(self): 
     86        args = [printop(self.op), repr(self.path)] 
     87        if self.order is not None: 
     88            args.append(repr(self.info)) 
     89            args.append(repr(self.order)) 
     90        elif self.info: 
     91            args.append(repr(self.info)) 
     92        return '(%s)' % ', '.join(args) 
    8493 
    8594class TreeDelta(object): 
    …… 
    8796 
    8897    An ADD is only allowed if nothing was there before. 
    89     ORDER constraints are checked. 
    9098    """ 
    9199    def __init__(self, ops=None, mergeModifyInfo=None): 
    …… 
    102110 
    103111    def __repr__(self): 
    104         ops = sorted(self.get(), key=operator.itemgetter(1)) 
    105         res = [] 
    106         for op, path, info in ops: 
    107             if not info: 
    108                 res.append('(%s, %r)' % (printop(op), path)) 
    109             else: 
    110                 res.append('(%s, %r, %r)' % (printop(op), path, info)) 
    111         return self.__class__.__name__ + '([' + ', '.join(res) + '])' 
     112        ops = sorted(self, key=lambda item: item.path) 
     113        return '%s([%s])' % (self.__class__.__name__, 
     114                             ', '.join([repr(item) for item in ops])) 
    112115 
    113116    def __nonzero__(self): 
    …… 
    126129                else: 
    127130                    jpath = path 
    128                 yield (child.op, jpath, child.info) 
    129             for stuff in self._recurse(path, child): 
    130                 yield stuff 
     131                yield Item(child, jpath) 
     132            for item in self._recurse(path, child): 
     133                yield item 
    131134 
    132135    def __iter__(self): 
    …… 
    149152            return res 
    150153 
    151     def add(self, op, path, info=None): 
     154    def add(self, op, path, info=None, order=None): 
    152155        """Do an operation on the tree. 
    153156 
    154         See `SimpleTreeDelta.op`. 
     157        ``op`` can be one of ``ADD``, ``REMOVE`` or ``MODIFY``. 
     158 
     159        ``path`` is a sequence representing a node. 
     160 
     161        ``info`` may be passed, to give additional information about a 
     162        ``MODIFY`` operation. 
     163 
     164        ``order`` may be passed to a ``MODIFY`` operation, to specify 
     165        the new order of the children of this node as a list of names. 
    155166        """ 
    156         if not path: 
    157             return TreeError("Empty path forbidden") 
     167        assert path, "Empty path forbidden" 
     168        assert order is None or op == MODIFY 
     169 
    158170        if info is None: 
    159171            info = {} 
    160         if not self._root.children and isinstance(path, basestring): 
     172 
     173        parent = self._root 
     174        in_add = False 
     175 
     176        if not parent.children and isinstance(path, basestring): 
    161177            self._path_is_string = True 
    162  
    163         parent, in_add = self._walkExcepLast(op, path) 
    164         self._lastStep(op, path, info, parent, in_add) 
    165  
    166     def _walkExcepLast(self, op, path): 
    167         """Walk until the last component of the path. 
    168  
    169         Returns (node, in_add). 
    170         """ 
    171         node = self._root 
    172         in_add = False 
    173178 
    174179        # Walk the path to our node. 
    175180        for i, name in enumerate(path[:-1]): 
    176             parent = node 
    177             node = parent.children.get(name) 
     181            children = parent.children 
     182            node = children.get(name) 
    178183            if node is not None: 
    179184                if node.op == REMOVE: 
    …… 
    192197                # Add an intermediate node 
    193198                node = Node(_SEEN) 
    194                 parent.children[name] = node 
    195  
    196         return node, in_add 
    197  
    198     def _lastStep(self, op, path, info, parent, in_add): 
     199                children[name] = node 
     200            parent = node 
     201 
    199202        # Last step 
    200203        name = path[-1] 
    …… 
    206209                    raise TreeError("ADD %r after %s %r" 
    207210                                    % (path, printop(node.op), path)) 
     211                if name in parent.order: 
     212                    raise TreeError("ADD %r already in parent order" % (path,)) 
    208213                children[name] = Node(ADD, info=info) 
     214                parent.order.append(name) 
    209215            elif op == REMOVE: 
    210216                if node.op == REMOVE: 
    211217                    raise TreeError("REMOVE %r after REMOVE %r" % (path, path)) 
     218                if parent.order_total: 
     219                    if name not in parent.order: 
     220                        # never reached because of other sanity checks? 
     221                        raise TreeError("REMOVE %r not in parent order" % 
     222                                        (path,)) 
     223                    parent.order.remove(name) 
     224                else: 
     225                    if name in parent.order: 
     226                        parent.order.remove(name) 
    212227                if in_add: 
    213228                    assert node.op == ADD # tree invariant 
    …… 
    215230                else: 
    216231                    children[name] = Node(REMOVE, info=info) 
    217             elif op == ORDER: 
    218                 XXX 
    219232            # op == MODIFY: 
    220             elif node.op == _SEEN: 
    221                 # MODIFY after _SEEN, replace op 
    222                 node.op = op 
    223                 node.info = info 
    224233            elif node.op == REMOVE: 
    225234                raise TreeError("MODIFY %r after REMOVE %r" % (path, path)) 
    226235            else: 
    227                 # MODIFY after ADD/MODIFY, merge infos 
    228                 new_info = self.mergeModifyInfo(node.info, info) 
    229                 node.info = new_info 
     236                # MODIFY after _SEEN/ADD/MODIFY 
     237                if order is not None: 
     238                    if node.order_total: 
     239                        # assert same sets 
     240                        if set(node.order) != set(order): 
     241                            raise TreeError("Bad reordering: %s to %s" % 
     242                                            (node.order, order)) 
     243                    else: 
     244                        # assert subset 
     245                        missing = set(node.order) - set(order) 
     246                        if missing: 
     247                            raise TreeError("Order doesn't mention %s" % 
     248                                            (sorted(missing),)) 
     249                        node.order_total = True 
     250                    node.order = order 
     251                    # assert: check that children are present in 'order' 
     252                    mentioned = [name for name, child in node.children.items() 
     253                                 if child.op != REMOVE] 
     254                    missing = set(mentioned) - set(order) 
     255                    if missing: 
     256                        raise TreeError("Order doesn't mention %s" % 
     257                                        (sorted(missing),)) 
     258                if node.op == _SEEN: 
     259                    # MODIFY after _SEEN, replace 
     260                    node.op = op 
     261                    node.info = info 
     262                else: 
     263                    # MODIFY after ADD/MODIFY, merge infos 
     264                    new_info = self.mergeModifyInfo(node.info, info) 
     265                    node.info = new_info 
    230266        else: 
    231267            if in_add and op != ADD: 
    232268                raise TreeError("%s %r on nonexistent node" % 
    233269                                (printop(op), path)) 
    234             children[name] = Node(op, info=info) 
    235  
    236  
     270            # Order checks 
     271            if op == ADD: 
     272                if name in parent.order: 
     273                    raise TreeError("ADD %r already in parent order" % (path,)) 
     274                parent.order.append(name) 
     275            elif op == REMOVE: 
     276                if parent.order_total: 
     277                    if name not in parent.order: 
     278                        raise TreeError("REMOVE %r not in parent order" % 
     279                                        (path,)) 
     280                    parent.order.remove(name) 
     281                else: 
     282                    if name in parent.order: 
     283                        parent.order.remove(name) 
     284            node = Node(op, info=info) 
     285            children[name] = node 
     286            if order is not None: 
     287                node.order = order 
     288                node.order_total = True