← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Vincent Ladeuil
  • Date: 2009-06-18 19:45:24 UTC
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: v.ladeuil+lp@free.fr-20090618194524-poedor61th3op5dm
Cleanup.

* bzrlib/tests/test__known_graph.py:
(TestKnownGraph): Delete dominator tests.

* bzrlib/_known_graph_pyx.pyx: 
Cleanup all references to old version and linear dominators :-/

* bzrlib/_known_graph_py.py: 
Cleanup all references to old version and linear dominators :-/

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
17
17
"""Implementation of Graph algorithms when we have already loaded everything.
18
18
"""
19
19
 
20
 
import heapq
21
 
 
22
20
from bzrlib import (
23
21
    revision,
24
22
    )
27
25
class _KnownGraphNode(object):
28
26
    """Represents a single object in the known graph."""
29
27
 
30
 
    __slots__ = ('key', 'parent_keys', 'child_keys', 'linear_dominator',
31
 
                 'gdfo', 'ancestor_of')
 
28
    __slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
32
29
 
33
30
    def __init__(self, key, parent_keys):
34
31
        self.key = key
35
32
        self.parent_keys = parent_keys
36
33
        self.child_keys = []
37
 
        # oldest ancestor, such that no parents between here and there have >1
38
 
        # child or >1 parent.
39
 
        self.linear_dominator = None
40
34
        # Greatest distance from origin
41
35
        self.gdfo = None
42
 
        # This will become a tuple of known heads that have this node as an
43
 
        # ancestor
44
 
        self.ancestor_of = None
45
36
 
46
37
    def __repr__(self):
47
 
        return '%s(%s  gdfo:%s par:%s child:%s %s)' % (
 
38
        return '%s(%s  gdfo:%s par:%s child:%s)' % (
48
39
            self.__class__.__name__, self.key, self.gdfo,
49
 
            self.parent_keys, self.child_keys,
50
 
            self.linear_dominator)
 
40
            self.parent_keys, self.child_keys)
51
41
 
52
42
 
53
43
class KnownGraph(object):
63
53
        self._known_heads = {}
64
54
        self.do_cache = do_cache
65
55
        self._initialize_nodes(parent_map)
66
 
        self._find_linear_dominators()
67
56
        self._find_gdfo()
68
57
 
69
58
    def _initialize_nodes(self, parent_map):
100
89
                    tails.add(parent_node)
101
90
                parent_node.child_keys.append(key)
102
91
 
103
 
    def _find_linear_dominators(self):
104
 
        """For each node in the set, find any linear dominators.
105
 
 
106
 
        For any given node, the 'linear dominator' is an ancestor, such that
107
 
        all parents between this node and that one have a single parent, and a
108
 
        single child. So if A->B->C->D then B,C,D all have a linear dominator
109
 
        of A.
110
 
 
111
 
        There are two main benefits:
112
 
        1) When walking the graph, we can jump to the nearest linear dominator,
113
 
           rather than walking all of the nodes inbetween.
114
 
        2) When caching heads() results, dominators give the "same" results as
115
 
           their children. (If the dominator is a head, then the descendant is
116
 
           a head, if the dominator is not a head, then the child isn't
117
 
           either.)
118
 
        """
119
 
        def check_node(node):
120
 
            if node.parent_keys is None or len(node.parent_keys) != 1:
121
 
                # This node is either a ghost, a tail, or has multiple parents
122
 
                # It its own dominator
123
 
                node.linear_dominator = node.key
124
 
                return None
125
 
            parent_node = self._nodes[node.parent_keys[0]]
126
 
            if len(parent_node.child_keys) > 1:
127
 
                # The parent has multiple children, so *this* node is the
128
 
                # dominator
129
 
                node.linear_dominator = node.key
130
 
                return None
131
 
            # The parent is already filled in, so add and continue
132
 
            if parent_node.linear_dominator is not None:
133
 
                node.linear_dominator = parent_node.linear_dominator
134
 
                return None
135
 
            # We don't know this node, or its parent node, so start walking to
136
 
            # next
137
 
            return parent_node
138
 
 
139
 
        for node in self._nodes.itervalues():
140
 
            # The parent is not filled in, so walk until we get somewhere
141
 
            if node.linear_dominator is not None: #already done
142
 
                continue
143
 
            next_node = check_node(node)
144
 
            if next_node is None:
145
 
                # Nothing more needs to be done
146
 
                continue
147
 
            stack = []
148
 
            while next_node is not None:
149
 
                stack.append(node)
150
 
                node = next_node
151
 
                next_node = check_node(node)
152
 
            # The stack now contains the linear chain, and 'node' should have
153
 
            # been labeled
154
 
            dominator = node.linear_dominator
155
 
            while stack:
156
 
                next_node = stack.pop()
157
 
                next_node.linear_dominator = dominator
158
 
                node = next_node
159
 
 
160
92
    def _find_gdfo(self):
161
93
        nodes = self._nodes
 
94
        known_parent_gdfos = {}
162
95
        pending = []
163
 
        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
164
96
 
165
97
        for node in self._tails:
166
98
            node.gdfo = 1
167
 
            known_parent_gdfos[node.key] = 0
168
99
            pending.append(node)
169
100
 
170
101
        while pending:
182
113
                    # continue from there
183
114
                    pending.append(child)
184
115
 
185
 
    def x_find_gdfo(self):
186
 
        def find_tails():
187
 
            return [node for node in self._nodes.itervalues()
188
 
                       if not node.parent_keys]
189
 
        tails = find_tails()
190
 
        todo = []
191
 
        heappush = heapq.heappush
192
 
        heappop = heapq.heappop
193
 
        nodes = self._nodes
194
 
        for node in tails:
195
 
            node.gdfo = 1
196
 
            heappush(todo, (1, node))
197
 
        processed = 0
198
 
        while todo:
199
 
            gdfo, next = heappop(todo)
200
 
            processed += 1
201
 
            if next.gdfo is not None and gdfo < next.gdfo:
202
 
                # This node was reached from a longer path, we assume it was
203
 
                # enqued correctly with the longer gdfo, so don't continue
204
 
                # processing now
205
 
                continue
206
 
            next_gdfo = gdfo + 1
207
 
            for child_key in next.child_keys:
208
 
                child_node = nodes[child_key]
209
 
                if child_node.gdfo is None or child_node.gdfo < next_gdfo:
210
 
                    # Only enque children when all of their parents have been
211
 
                    # resolved
212
 
                    for parent_key in child_node.parent_keys:
213
 
                        # We know that 'this' parent is counted
214
 
                        if parent_key != next.key:
215
 
                            parent_node = nodes[parent_key]
216
 
                            if parent_node.gdfo is None:
217
 
                                break
218
 
                    else:
219
 
                        child_node.gdfo = next_gdfo
220
 
                        heappush(todo, (next_gdfo, child_node))
221
 
 
222
 
    def _get_dominators_to_nodes(self, candidate_nodes):
223
 
        """Get the reverse mapping from dominator_key => candidate_nodes.
224
 
 
225
 
        As a side effect, this can also remove potential candidate nodes if we
226
 
        determine that they share a dominator.
227
 
        """
228
 
        dom_to_node = {}
229
 
        keys_to_remove = []
230
 
        for node in candidate_nodes.values():
231
 
            if node.linear_dominator in dom_to_node:
232
 
                # This node already exists, resolve which node supersedes the
233
 
                # other
234
 
                other_node = dom_to_node[node.linear_dominator]
235
 
                # There should be no way that nodes sharing a dominator could
236
 
                # 'tie' for gdfo
237
 
                if other_node.gdfo > node.gdfo:
238
 
                    # The other node has this node as an ancestor
239
 
                    keys_to_remove.append(node.key)
240
 
                else:
241
 
                    # Replace the other node, and set this as the new key
242
 
                    keys_to_remove.append(other_node.key)
243
 
                    dom_to_node[node.linear_dominator] = node
244
 
            else:
245
 
                dom_to_node[node.linear_dominator] = node
246
 
        for key in keys_to_remove:
247
 
            candidate_nodes.pop(key)
248
 
        return dom_to_node
249
 
 
250
116
    def heads(self, keys):
251
117
        """Return the heads from amongst keys.
252
118
 
306
172
            self._known_heads[heads_key] = heads
307
173
        return heads
308
174
 
309
 
    def xheads(self, keys):
310
 
        """Return the heads from amongst keys.
311
 
 
312
 
        This is done by searching the ancestries of each key.  Any key that is
313
 
        reachable from another key is not returned; all the others are.
314
 
 
315
 
        This operation scales with the relative depth between any two keys. If
316
 
        any two keys are completely disconnected all ancestry of both sides
317
 
        will be retrieved.
318
 
 
319
 
        :param keys: An iterable of keys.
320
 
        :return: A set of the heads. Note that as a set there is no ordering
321
 
            information. Callers will need to filter their input to create
322
 
            order if they need it.
323
 
        """
324
 
        candidate_nodes = dict((key, self._nodes[key]) for key in keys)
325
 
        if revision.NULL_REVISION in candidate_nodes:
326
 
            # NULL_REVISION is only a head if it is the only entry
327
 
            candidate_nodes.pop(revision.NULL_REVISION)
328
 
            if not candidate_nodes:
329
 
                return set([revision.NULL_REVISION])
330
 
        if len(candidate_nodes) < 2:
331
 
            return frozenset(candidate_nodes)
332
 
        heads_key = frozenset(candidate_nodes)
333
 
        if heads_key != frozenset(keys):
334
 
            note('%s != %s', heads_key, frozenset(keys))
335
 
        try:
336
 
            heads = self._known_heads[heads_key]
337
 
            return heads
338
 
        except KeyError:
339
 
            pass # compute it ourselves
340
 
        dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
341
 
        if len(candidate_nodes) < 2:
342
 
            # We shrunk candidate_nodes and determined a new head
343
 
            return frozenset(candidate_nodes)
344
 
        dom_heads_key = None
345
 
        # Check the linear dominators of these keys, to see if we already
346
 
        # know the heads answer
347
 
        dom_heads_key = frozenset([node.linear_dominator
348
 
                                   for node in candidate_nodes.itervalues()])
349
 
        if dom_heads_key in self._known_heads:
350
 
            # map back into the original keys
351
 
            heads = self._known_heads[dom_heads_key]
352
 
            heads = frozenset([dom_to_node[key].key for key in heads])
353
 
            return heads
354
 
        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
355
 
        if self.do_cache:
356
 
            self._known_heads[heads_key] = heads
357
 
            # Cache the dominator heads
358
 
            if dom_heads_key is not None:
359
 
                dom_heads = frozenset([candidate_nodes[key].linear_dominator
360
 
                                       for key in heads])
361
 
                self._known_heads[dom_heads_key] = dom_heads
362
 
        return heads
363
 
 
364
 
    def _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
365
 
        queue = []
366
 
        to_cleanup = []
367
 
        to_cleanup_append = to_cleanup.append
368
 
        for node in candidate_nodes.itervalues():
369
 
            node.ancestor_of = (node.key,)
370
 
            queue.append((-node.gdfo, node))
371
 
            to_cleanup_append(node)
372
 
        heapq.heapify(queue)
373
 
        # These are nodes that we determined are 'common' that we are no longer
374
 
        # walking
375
 
        # Now we walk nodes until all nodes that are being walked are 'common'
376
 
        num_candidates = len(candidate_nodes)
377
 
        nodes = self._nodes
378
 
        heappop = heapq.heappop
379
 
        heappush = heapq.heappush
380
 
        while queue and len(candidate_nodes) > 1:
381
 
            _, node = heappop(queue)
382
 
            next_ancestor_of = node.ancestor_of
383
 
            if len(next_ancestor_of) == num_candidates:
384
 
                # This node is now considered 'common'
385
 
                # Make sure all parent nodes are marked as such
386
 
                for parent_key in node.parent_keys:
387
 
                    parent_node = nodes[parent_key]
388
 
                    if parent_node.ancestor_of is not None:
389
 
                        parent_node.ancestor_of = next_ancestor_of
390
 
                if node.linear_dominator != node.key:
391
 
                    parent_node = nodes[node.linear_dominator]
392
 
                    if parent_node.ancestor_of is not None:
393
 
                        parent_node.ancestor_of = next_ancestor_of
394
 
                continue
395
 
            if node.parent_keys is None:
396
 
                # This is a ghost
397
 
                continue
398
 
            # Now project the current nodes ancestor list to the parent nodes,
399
 
            # and queue them up to be walked
400
 
            # Note: using linear_dominator speeds things up quite a bit
401
 
            #       enough that we actually start to be slightly faster
402
 
            #       than the default heads() implementation
403
 
            if node.linear_dominator != node.key:
404
 
                # We are at the tip of a long linear region
405
 
                # We know that there is nothing between here and the tail
406
 
                # that is interesting, so skip to the end
407
 
                parent_keys = [node.linear_dominator]
408
 
            else:
409
 
                parent_keys = node.parent_keys
410
 
            for parent_key in parent_keys:
411
 
                if parent_key in candidate_nodes:
412
 
                    candidate_nodes.pop(parent_key)
413
 
                    if len(candidate_nodes) <= 1:
414
 
                        break
415
 
                elif parent_key in dom_to_node:
416
 
                    orig_node = dom_to_node[parent_key]
417
 
                    if orig_node is not node:
418
 
                        if orig_node.key in candidate_nodes:
419
 
                            candidate_nodes.pop(orig_node.key)
420
 
                            if len(candidate_nodes) <= 1:
421
 
                                break
422
 
                parent_node = nodes[parent_key]
423
 
                ancestor_of = parent_node.ancestor_of
424
 
                if ancestor_of is None:
425
 
                    # This node hasn't been walked yet
426
 
                    parent_node.ancestor_of = next_ancestor_of
427
 
                    # Enqueue this node
428
 
                    heappush(queue, (-parent_node.gdfo, parent_node))
429
 
                    to_cleanup_append(parent_node)
430
 
                elif ancestor_of != next_ancestor_of:
431
 
                    # Combine to get the full set of parents
432
 
                    all_ancestors = set(ancestor_of)
433
 
                    all_ancestors.update(next_ancestor_of)
434
 
                    parent_node.ancestor_of = tuple(sorted(all_ancestors))
435
 
        def cleanup():
436
 
            for node in to_cleanup:
437
 
                node.ancestor_of = None
438
 
        cleanup()
439
 
        return frozenset(candidate_nodes)