/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

Rework test_script a little bit.


Don't allow someone to request a stdin request to echo.
Echo never reads from stdin, it just echos its arguments.
You use 'cat' if you want to read from stdin.

A few other fixes because the tests were using filenames
that are actually illegal on Windows, rather than just
nonexistant.


Change the exception handling for commands so that
unknown errors don't get silently squashed and then
turn into hard-to-debug errors later.

test_script now passes on Windows.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
51
51
 
52
52
    void Py_INCREF(object)
53
53
 
54
 
from collections import deque
55
54
import gc
56
55
 
57
56
from bzrlib import errors, revision
193
192
    """This is a class which assumes we already know the full graph."""
194
193
 
195
194
    cdef public object _nodes
196
 
    cdef public object _known_heads
 
195
    cdef object _known_heads
197
196
    cdef public int do_cache
198
197
 
199
198
    def __init__(self, parent_map, do_cache=True):
233
232
            node = <_KnownGraphNode>temp_node
234
233
        return node
235
234
 
236
 
    cdef _populate_parents(self, _KnownGraphNode node, parent_keys):
237
 
        cdef Py_ssize_t num_parent_keys, pos
238
 
        cdef _KnownGraphNode parent_node
239
 
 
240
 
        num_parent_keys = len(parent_keys)
241
 
        # We know how many parents, so we pre allocate the tuple
242
 
        parent_nodes = PyTuple_New(num_parent_keys)
243
 
        for pos from 0 <= pos < num_parent_keys:
244
 
            # Note: it costs us 10ms out of 40ms to lookup all of these
245
 
            #       parents, it doesn't seem to be an allocation overhead,
246
 
            #       but rather a lookup overhead. There doesn't seem to be
247
 
            #       a way around it, and that is one reason why
248
 
            #       KnownGraphNode maintains a direct pointer to the parent
249
 
            #       node.
250
 
            # We use [] because parent_keys may be a tuple or list
251
 
            parent_node = self._get_or_create_node(parent_keys[pos])
252
 
            # PyTuple_SET_ITEM will steal a reference, so INCREF first
253
 
            Py_INCREF(parent_node)
254
 
            PyTuple_SET_ITEM(parent_nodes, pos, parent_node)
255
 
            PyList_Append(parent_node.children, node)
256
 
        node.parents = parent_nodes
257
 
 
258
235
    def _initialize_nodes(self, parent_map):
259
236
        """Populate self._nodes.
260
237
 
265
242
          child keys,
266
243
        """
267
244
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
268
 
        cdef Py_ssize_t pos
 
245
        cdef Py_ssize_t pos, pos2, num_parent_keys
269
246
        cdef _KnownGraphNode node
270
247
        cdef _KnownGraphNode parent_node
271
248
 
276
253
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
277
254
            key = <object>temp_key
278
255
            parent_keys = <object>temp_parent_keys
 
256
            num_parent_keys = len(parent_keys)
279
257
            node = self._get_or_create_node(key)
280
 
            self._populate_parents(node, parent_keys)
 
258
            # We know how many parents, so we pre allocate the tuple
 
259
            parent_nodes = PyTuple_New(num_parent_keys)
 
260
            for pos2 from 0 <= pos2 < num_parent_keys:
 
261
                # Note: it costs us 10ms out of 40ms to lookup all of these
 
262
                #       parents, it doesn't seem to be an allocation overhead,
 
263
                #       but rather a lookup overhead. There doesn't seem to be
 
264
                #       a way around it, and that is one reason why
 
265
                #       KnownGraphNode maintains a direct pointer to the parent
 
266
                #       node.
 
267
                # We use [] because parent_keys may be a tuple or list
 
268
                parent_node = self._get_or_create_node(parent_keys[pos2])
 
269
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
 
270
                Py_INCREF(parent_node)
 
271
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
 
272
                PyList_Append(parent_node.children, node)
 
273
            node.parents = parent_nodes
281
274
 
282
275
    def _find_tails(self):
283
276
        cdef PyObject *temp_node
341
334
                    # anymore
342
335
                    child.seen = 0
343
336
 
344
 
    def add_node(self, key, parent_keys):
345
 
        """Add a new node to the graph.
346
 
 
347
 
        If this fills in a ghost, then the gdfos of all children will be
348
 
        updated accordingly.
349
 
        
350
 
        :param key: The node being added. If this is a duplicate, this is a
351
 
            no-op.
352
 
        :param parent_keys: The parents of the given node.
353
 
        :return: None (should we return if this was a ghost, etc?)
354
 
        """
355
 
        cdef PyObject *maybe_node
356
 
        cdef _KnownGraphNode node, parent_node, child_node
357
 
        cdef long parent_gdfo, next_gdfo
358
 
 
359
 
        maybe_node = PyDict_GetItem(self._nodes, key)
360
 
        if maybe_node != NULL:
361
 
            node = <_KnownGraphNode>maybe_node
362
 
            if node.parents is None:
363
 
                # We are filling in a ghost
364
 
                self._populate_parents(node, parent_keys)
365
 
                # We can't trust cached heads anymore
366
 
                self._known_heads.clear()
367
 
            else: # Ensure that the parent_key list matches
368
 
                existing_parent_keys = []
369
 
                for parent_node in node.parents:
370
 
                    existing_parent_keys.append(parent_node.key)
371
 
                # Make sure we use a list for the comparison, in case it was a
372
 
                # tuple, etc
373
 
                parent_keys = list(parent_keys)
374
 
                if existing_parent_keys == parent_keys:
375
 
                    # Exact match, nothing more to do
376
 
                    return
377
 
                else:
378
 
                    raise ValueError('Parent key mismatch, existing node %s'
379
 
                        ' has parents of %s not %s'
380
 
                        % (key, existing_parent_keys, parent_keys))
381
 
        else:
382
 
            node = _KnownGraphNode(key)
383
 
            PyDict_SetItem(self._nodes, key, node)
384
 
            self._populate_parents(node, parent_keys)
385
 
        parent_gdfo = 0
386
 
        for parent_node in node.parents:
387
 
            if parent_node.gdfo == -1:
388
 
                # This is a newly introduced ghost, so it gets gdfo of 1
389
 
                parent_node.gdfo = 1
390
 
            if parent_gdfo < parent_node.gdfo:
391
 
                parent_gdfo = parent_node.gdfo
392
 
        node.gdfo = parent_gdfo + 1
393
 
        # Now fill the gdfo to all children
394
 
        # Note that this loop is slightly inefficient, in that we may visit the
395
 
        # same child (and its decendents) more than once, however, it is
396
 
        # 'efficient' in that we only walk to nodes that would be updated,
397
 
        # rather than all nodes
398
 
        # We use a deque rather than a simple list stack, to go for BFD rather
399
 
        # than DFD. So that if a longer path is possible, we walk it before we
400
 
        # get to the final child
401
 
        pending = deque([node])
402
 
        pending_popleft = pending.popleft
403
 
        pending_append = pending.append
404
 
        while pending:
405
 
            node = pending_popleft()
406
 
            next_gdfo = node.gdfo + 1
407
 
            for child_node in node.children:
408
 
                if child_node.gdfo < next_gdfo:
409
 
                    # This child is being updated, we need to check its
410
 
                    # children
411
 
                    child_node.gdfo = next_gdfo
412
 
                    pending_append(child_node)
413
 
 
414
337
    def heads(self, keys):
415
338
        """Return the heads from amongst keys.
416
339
 
703
626
            self._revno_first, self._revno_second, self._revno_last,
704
627
            self.is_first_child, self.seen_by_child)
705
628
 
706
 
    cdef int has_pending_parents(self): # cannot_raise
 
629
    cdef int has_pending_parents(self):
707
630
        if self.left_pending_parent is not None or self.pending_parents:
708
631
            return 1
709
632
        return 0