← 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: 2017-01-17 13:48:10 UTC
  • mfrom: (6615.3.6 merges)
  • mto: This revision was merged to the branch mainline in revision 6620.
  • Revision ID: v.ladeuil+lp@free.fr-20170117134810-j9p3lidfy6pfyfsc
Merge 2.7, resolving conflicts

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009, 2010 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
17
17
"""Implementation of Graph algorithms when we have already loaded everything.
18
18
"""
19
19
 
 
20
from __future__ import absolute_import
 
21
 
 
22
from collections import deque
20
23
from bzrlib import (
 
24
    errors,
21
25
    revision,
22
26
    )
23
27
 
40
44
            self.parent_keys, self.child_keys)
41
45
 
42
46
 
 
47
class _MergeSortNode(object):
 
48
    """Information about a specific node in the merge graph."""
 
49
 
 
50
    __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')
 
51
 
 
52
    def __init__(self, key, merge_depth, revno, end_of_merge):
 
53
        self.key = key
 
54
        self.merge_depth = merge_depth
 
55
        self.revno = revno
 
56
        self.end_of_merge = end_of_merge
 
57
 
 
58
 
43
59
class KnownGraph(object):
44
60
    """This is a class which assumes we already know the full graph."""
45
61
 
49
65
        :param parent_map: A dictionary mapping key => parent_keys
50
66
        """
51
67
        self._nodes = {}
52
 
        # Maps {sorted(revision_id, revision_id): heads}
 
68
        # Maps {frozenset(revision_id, revision_id): heads}
53
69
        self._known_heads = {}
54
70
        self.do_cache = do_cache
55
71
        self._initialize_nodes(parent_map)
84
100
        return [node for node in self._nodes.itervalues()
85
101
                if not node.parent_keys]
86
102
 
 
103
    def _find_tips(self):
 
104
        return [node for node in self._nodes.itervalues()
 
105
                      if not node.child_keys]
 
106
 
87
107
    def _find_gdfo(self):
88
108
        nodes = self._nodes
89
109
        known_parent_gdfos = {}
115
135
                    # Update known_parent_gdfos for a key we couldn't process
116
136
                    known_parent_gdfos[child_key] = known_gdfo
117
137
 
 
138
    def add_node(self, key, parent_keys):
 
139
        """Add a new node to the graph.
 
140
 
 
141
        If this fills in a ghost, then the gdfos of all children will be
 
142
        updated accordingly.
 
143
        
 
144
        :param key: The node being added. If this is a duplicate, this is a
 
145
            no-op.
 
146
        :param parent_keys: The parents of the given node.
 
147
        :return: None (should we return if this was a ghost, etc?)
 
148
        """
 
149
        nodes = self._nodes
 
150
        if key in nodes:
 
151
            node = nodes[key]
 
152
            if node.parent_keys is None:
 
153
                node.parent_keys = parent_keys
 
154
                # A ghost is being added, we can no-longer trust the heads
 
155
                # cache, so clear it
 
156
                self._known_heads.clear()
 
157
            else:
 
158
                # Make sure we compare a list to a list, as tuple != list.
 
159
                parent_keys = list(parent_keys)
 
160
                existing_parent_keys = list(node.parent_keys)
 
161
                if parent_keys == existing_parent_keys:
 
162
                    return # Identical content
 
163
                else:
 
164
                    raise ValueError('Parent key mismatch, existing node %s'
 
165
                        ' has parents of %s not %s'
 
166
                        % (key, existing_parent_keys, parent_keys))
 
167
        else:
 
168
            node = _KnownGraphNode(key, parent_keys)
 
169
            nodes[key] = node
 
170
        parent_gdfo = 0
 
171
        for parent_key in parent_keys:
 
172
            try:
 
173
                parent_node = nodes[parent_key]
 
174
            except KeyError:
 
175
                parent_node = _KnownGraphNode(parent_key, None)
 
176
                # Ghosts and roots have gdfo 1
 
177
                parent_node.gdfo = 1
 
178
                nodes[parent_key] = parent_node
 
179
            if parent_gdfo < parent_node.gdfo:
 
180
                parent_gdfo = parent_node.gdfo
 
181
            parent_node.child_keys.append(key)
 
182
        node.gdfo = parent_gdfo + 1
 
183
        # Now fill the gdfo to all children
 
184
        # Note that this loop is slightly inefficient, in that we may visit the
 
185
        # same child (and its decendents) more than once, however, it is
 
186
        # 'efficient' in that we only walk to nodes that would be updated,
 
187
        # rather than all nodes
 
188
        # We use a deque rather than a simple list stack, to go for BFD rather
 
189
        # than DFD. So that if a longer path is possible, we walk it before we
 
190
        # get to the final child
 
191
        pending = deque([node])
 
192
        while pending:
 
193
            node = pending.popleft()
 
194
            next_gdfo = node.gdfo + 1
 
195
            for child_key in node.child_keys:
 
196
                child = nodes[child_key]
 
197
                if child.gdfo < next_gdfo:
 
198
                    # This child is being updated, we need to check its
 
199
                    # children
 
200
                    child.gdfo = next_gdfo
 
201
                    pending.append(child)
 
202
 
118
203
    def heads(self, keys):
119
204
        """Return the heads from amongst keys.
120
205
 
171
256
            self._known_heads[heads_key] = heads
172
257
        return heads
173
258
 
 
259
    def topo_sort(self):
 
260
        """Return the nodes in topological order.
 
261
 
 
262
        All parents must occur before all children.
 
263
        """
 
264
        for node in self._nodes.itervalues():
 
265
            if node.gdfo is None:
 
266
                raise errors.GraphCycleError(self._nodes)
 
267
        pending = self._find_tails()
 
268
        pending_pop = pending.pop
 
269
        pending_append = pending.append
 
270
 
 
271
        topo_order = []
 
272
        topo_order_append = topo_order.append
 
273
 
 
274
        num_seen_parents = dict.fromkeys(self._nodes, 0)
 
275
        while pending:
 
276
            node = pending_pop()
 
277
            if node.parent_keys is not None:
 
278
                # We don't include ghost parents
 
279
                topo_order_append(node.key)
 
280
            for child_key in node.child_keys:
 
281
                child_node = self._nodes[child_key]
 
282
                seen_parents = num_seen_parents[child_key] + 1
 
283
                if seen_parents == len(child_node.parent_keys):
 
284
                    # All parents have been processed, enqueue this child
 
285
                    pending_append(child_node)
 
286
                    # This has been queued up, stop tracking it
 
287
                    del num_seen_parents[child_key]
 
288
                else:
 
289
                    num_seen_parents[child_key] = seen_parents
 
290
        # We started from the parents, so we don't need to do anymore work
 
291
        return topo_order
 
292
 
 
293
    def gc_sort(self):
 
294
        """Return a reverse topological ordering which is 'stable'.
 
295
 
 
296
        There are a few constraints:
 
297
          1) Reverse topological (all children before all parents)
 
298
          2) Grouped by prefix
 
299
          3) 'stable' sorting, so that we get the same result, independent of
 
300
             machine, or extra data.
 
301
        To do this, we use the same basic algorithm as topo_sort, but when we
 
302
        aren't sure what node to access next, we sort them lexicographically.
 
303
        """
 
304
        tips = self._find_tips()
 
305
        # Split the tips based on prefix
 
306
        prefix_tips = {}
 
307
        for node in tips:
 
308
            if node.key.__class__ is str or len(node.key) == 1:
 
309
                prefix = ''
 
310
            else:
 
311
                prefix = node.key[0]
 
312
            prefix_tips.setdefault(prefix, []).append(node)
 
313
 
 
314
        num_seen_children = dict.fromkeys(self._nodes, 0)
 
315
 
 
316
        result = []
 
317
        for prefix in sorted(prefix_tips):
 
318
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
319
                             reverse=True)
 
320
            while pending:
 
321
                node = pending.pop()
 
322
                if node.parent_keys is None:
 
323
                    # Ghost node, skip it
 
324
                    continue
 
325
                result.append(node.key)
 
326
                for parent_key in sorted(node.parent_keys, reverse=True):
 
327
                    parent_node = self._nodes[parent_key]
 
328
                    seen_children = num_seen_children[parent_key] + 1
 
329
                    if seen_children == len(parent_node.child_keys):
 
330
                        # All children have been processed, enqueue this parent
 
331
                        pending.append(parent_node)
 
332
                        # This has been queued up, stop tracking it
 
333
                        del num_seen_children[parent_key]
 
334
                    else:
 
335
                        num_seen_children[parent_key] = seen_children
 
336
        return result
 
337
 
 
338
    def merge_sort(self, tip_key):
 
339
        """Compute the merge sorted graph output."""
 
340
        from bzrlib import tsort
 
341
        as_parent_map = dict((node.key, node.parent_keys)
 
342
                             for node in self._nodes.itervalues()
 
343
                              if node.parent_keys is not None)
 
344
        # We intentionally always generate revnos and never force the
 
345
        # mainline_revisions
 
346
        # Strip the sequence_number that merge_sort generates
 
347
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
 
348
                for _, key, merge_depth, revno, end_of_merge
 
349
                 in tsort.merge_sort(as_parent_map, tip_key,
 
350
                                     mainline_revisions=None,
 
351
                                     generate_revno=True)]
 
352
    
 
353
    def get_parent_keys(self, key):
 
354
        """Get the parents for a key
 
355
        
 
356
        Returns a list containg the parents keys. If the key is a ghost,
 
357
        None is returned. A KeyError will be raised if the key is not in
 
358
        the graph.
 
359
        
 
360
        :param keys: Key to check (eg revision_id)
 
361
        :return: A list of parents
 
362
        """
 
363
        return self._nodes[key].parent_keys
 
364
 
 
365
    def get_child_keys(self, key):
 
366
        """Get the children for a key
 
367
        
 
368
        Returns a list containg the children keys. A KeyError will be raised
 
369
        if the key is not in the graph.
 
370
        
 
371
        :param keys: Key to check (eg revision_id)
 
372
        :return: A list of children
 
373
        """
 
374
        return self._nodes[key].child_keys