/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 breezy/_known_graph_py.py

  • Committer: Robert Collins
  • Date: 2005-10-19 10:11:57 UTC
  • mfrom: (1185.16.78)
  • mto: This revision was merged to the branch mainline in revision 1470.
  • Revision ID: robertc@robertcollins.net-20051019101157-17438d311e746b4f
merge from upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/_known_graph_py.py
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
2
 
#
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
#
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
#
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
"""Implementation of Graph algorithms when we have already loaded everything.
18
 
"""
19
 
 
20
 
from __future__ import absolute_import
21
 
 
22
 
try:
23
 
    from collections.abc import deque
24
 
except ImportError:  # python < 3.7
25
 
    from collections import deque
26
 
from . import (
27
 
    errors,
28
 
    revision,
29
 
    )
30
 
from .sixish import (
31
 
    viewitems,
32
 
    viewvalues,
33
 
    )
34
 
 
35
 
 
36
 
class _KnownGraphNode(object):
37
 
    """Represents a single object in the known graph."""
38
 
 
39
 
    __slots__ = ('key', 'parent_keys', 'child_keys', 'gdfo')
40
 
 
41
 
    def __init__(self, key, parent_keys):
42
 
        self.key = key
43
 
        self.parent_keys = parent_keys
44
 
        self.child_keys = []
45
 
        # Greatest distance from origin
46
 
        self.gdfo = None
47
 
 
48
 
    def __repr__(self):
49
 
        return '%s(%s  gdfo:%s par:%s child:%s)' % (
50
 
            self.__class__.__name__, self.key, self.gdfo,
51
 
            self.parent_keys, self.child_keys)
52
 
 
53
 
 
54
 
class _MergeSortNode(object):
55
 
    """Information about a specific node in the merge graph."""
56
 
 
57
 
    __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')
58
 
 
59
 
    def __init__(self, key, merge_depth, revno, end_of_merge):
60
 
        self.key = key
61
 
        self.merge_depth = merge_depth
62
 
        self.revno = revno
63
 
        self.end_of_merge = end_of_merge
64
 
 
65
 
 
66
 
class KnownGraph(object):
67
 
    """This is a class which assumes we already know the full graph."""
68
 
 
69
 
    def __init__(self, parent_map, do_cache=True):
70
 
        """Create a new KnownGraph instance.
71
 
 
72
 
        :param parent_map: A dictionary mapping key => parent_keys
73
 
        """
74
 
        self._nodes = {}
75
 
        # Maps {frozenset(revision_id, revision_id): heads}
76
 
        self._known_heads = {}
77
 
        self.do_cache = do_cache
78
 
        self._initialize_nodes(parent_map)
79
 
        self._find_gdfo()
80
 
 
81
 
    def _initialize_nodes(self, parent_map):
82
 
        """Populate self._nodes.
83
 
 
84
 
        After this has finished:
85
 
        - self._nodes will have an entry for every entry in parent_map.
86
 
        - ghosts will have a parent_keys = None,
87
 
        - all nodes found will also have .child_keys populated with all known
88
 
          child_keys,
89
 
        """
90
 
        nodes = self._nodes
91
 
        for key, parent_keys in viewitems(parent_map):
92
 
            if key in nodes:
93
 
                node = nodes[key]
94
 
                node.parent_keys = parent_keys
95
 
            else:
96
 
                node = _KnownGraphNode(key, parent_keys)
97
 
                nodes[key] = node
98
 
            for parent_key in parent_keys:
99
 
                try:
100
 
                    parent_node = nodes[parent_key]
101
 
                except KeyError:
102
 
                    parent_node = _KnownGraphNode(parent_key, None)
103
 
                    nodes[parent_key] = parent_node
104
 
                parent_node.child_keys.append(key)
105
 
 
106
 
    def _find_tails(self):
107
 
        return [node for node in viewvalues(self._nodes)
108
 
                if not node.parent_keys]
109
 
 
110
 
    def _find_tips(self):
111
 
        return [node for node in viewvalues(self._nodes)
112
 
                if not node.child_keys]
113
 
 
114
 
    def _find_gdfo(self):
115
 
        nodes = self._nodes
116
 
        known_parent_gdfos = {}
117
 
        pending = []
118
 
 
119
 
        for node in self._find_tails():
120
 
            node.gdfo = 1
121
 
            pending.append(node)
122
 
 
123
 
        while pending:
124
 
            node = pending.pop()
125
 
            for child_key in node.child_keys:
126
 
                child = nodes[child_key]
127
 
                if child_key in known_parent_gdfos:
128
 
                    known_gdfo = known_parent_gdfos[child_key] + 1
129
 
                    present = True
130
 
                else:
131
 
                    known_gdfo = 1
132
 
                    present = False
133
 
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
134
 
                    child.gdfo = node.gdfo + 1
135
 
                if known_gdfo == len(child.parent_keys):
136
 
                    # We are the last parent updating that node, we can
137
 
                    # continue from there
138
 
                    pending.append(child)
139
 
                    if present:
140
 
                        del known_parent_gdfos[child_key]
141
 
                else:
142
 
                    # Update known_parent_gdfos for a key we couldn't process
143
 
                    known_parent_gdfos[child_key] = known_gdfo
144
 
 
145
 
    def add_node(self, key, parent_keys):
146
 
        """Add a new node to the graph.
147
 
 
148
 
        If this fills in a ghost, then the gdfos of all children will be
149
 
        updated accordingly.
150
 
 
151
 
        :param key: The node being added. If this is a duplicate, this is a
152
 
            no-op.
153
 
        :param parent_keys: The parents of the given node.
154
 
        :return: None (should we return if this was a ghost, etc?)
155
 
        """
156
 
        nodes = self._nodes
157
 
        if key in nodes:
158
 
            node = nodes[key]
159
 
            if node.parent_keys is None:
160
 
                node.parent_keys = parent_keys
161
 
                # A ghost is being added, we can no-longer trust the heads
162
 
                # cache, so clear it
163
 
                self._known_heads.clear()
164
 
            else:
165
 
                # Make sure we compare a list to a list, as tuple != list.
166
 
                parent_keys = list(parent_keys)
167
 
                existing_parent_keys = list(node.parent_keys)
168
 
                if parent_keys == existing_parent_keys:
169
 
                    return  # Identical content
170
 
                else:
171
 
                    raise ValueError(
172
 
                        'Parent key mismatch, existing node %s'
173
 
                        ' has parents of %s not %s'
174
 
                        % (key, existing_parent_keys, parent_keys))
175
 
        else:
176
 
            node = _KnownGraphNode(key, parent_keys)
177
 
            nodes[key] = node
178
 
        parent_gdfo = 0
179
 
        for parent_key in parent_keys:
180
 
            try:
181
 
                parent_node = nodes[parent_key]
182
 
            except KeyError:
183
 
                parent_node = _KnownGraphNode(parent_key, None)
184
 
                # Ghosts and roots have gdfo 1
185
 
                parent_node.gdfo = 1
186
 
                nodes[parent_key] = parent_node
187
 
            if parent_gdfo < parent_node.gdfo:
188
 
                parent_gdfo = parent_node.gdfo
189
 
            parent_node.child_keys.append(key)
190
 
        node.gdfo = parent_gdfo + 1
191
 
        # Now fill the gdfo to all children
192
 
        # Note that this loop is slightly inefficient, in that we may visit the
193
 
        # same child (and its decendents) more than once, however, it is
194
 
        # 'efficient' in that we only walk to nodes that would be updated,
195
 
        # rather than all nodes
196
 
        # We use a deque rather than a simple list stack, to go for BFD rather
197
 
        # than DFD. So that if a longer path is possible, we walk it before we
198
 
        # get to the final child
199
 
        pending = deque([node])
200
 
        while pending:
201
 
            node = pending.popleft()
202
 
            next_gdfo = node.gdfo + 1
203
 
            for child_key in node.child_keys:
204
 
                child = nodes[child_key]
205
 
                if child.gdfo < next_gdfo:
206
 
                    # This child is being updated, we need to check its
207
 
                    # children
208
 
                    child.gdfo = next_gdfo
209
 
                    pending.append(child)
210
 
 
211
 
    def heads(self, keys):
212
 
        """Return the heads from amongst keys.
213
 
 
214
 
        This is done by searching the ancestries of each key.  Any key that is
215
 
        reachable from another key is not returned; all the others are.
216
 
 
217
 
        This operation scales with the relative depth between any two keys. It
218
 
        uses gdfo to avoid walking all ancestry.
219
 
 
220
 
        :param keys: An iterable of keys.
221
 
        :return: A set of the heads. Note that as a set there is no ordering
222
 
            information. Callers will need to filter their input to create
223
 
            order if they need it.
224
 
        """
225
 
        candidate_nodes = dict((key, self._nodes[key]) for key in keys)
226
 
        if revision.NULL_REVISION in candidate_nodes:
227
 
            # NULL_REVISION is only a head if it is the only entry
228
 
            candidate_nodes.pop(revision.NULL_REVISION)
229
 
            if not candidate_nodes:
230
 
                return frozenset([revision.NULL_REVISION])
231
 
        if len(candidate_nodes) < 2:
232
 
            # No or only one candidate
233
 
            return frozenset(candidate_nodes)
234
 
        heads_key = frozenset(candidate_nodes)
235
 
        # Do we have a cached result ?
236
 
        try:
237
 
            heads = self._known_heads[heads_key]
238
 
            return heads
239
 
        except KeyError:
240
 
            pass
241
 
        # Let's compute the heads
242
 
        seen = set()
243
 
        pending = []
244
 
        min_gdfo = None
245
 
        for node in viewvalues(candidate_nodes):
246
 
            if node.parent_keys:
247
 
                pending.extend(node.parent_keys)
248
 
            if min_gdfo is None or node.gdfo < min_gdfo:
249
 
                min_gdfo = node.gdfo
250
 
        nodes = self._nodes
251
 
        while pending:
252
 
            node_key = pending.pop()
253
 
            if node_key in seen:
254
 
                # node already appears in some ancestry
255
 
                continue
256
 
            seen.add(node_key)
257
 
            node = nodes[node_key]
258
 
            if node.gdfo <= min_gdfo:
259
 
                continue
260
 
            if node.parent_keys:
261
 
                pending.extend(node.parent_keys)
262
 
        heads = heads_key.difference(seen)
263
 
        if self.do_cache:
264
 
            self._known_heads[heads_key] = heads
265
 
        return heads
266
 
 
267
 
    def topo_sort(self):
268
 
        """Return the nodes in topological order.
269
 
 
270
 
        All parents must occur before all children.
271
 
        """
272
 
        for node in viewvalues(self._nodes):
273
 
            if node.gdfo is None:
274
 
                raise errors.GraphCycleError(self._nodes)
275
 
        pending = self._find_tails()
276
 
        pending_pop = pending.pop
277
 
        pending_append = pending.append
278
 
 
279
 
        topo_order = []
280
 
        topo_order_append = topo_order.append
281
 
 
282
 
        num_seen_parents = dict.fromkeys(self._nodes, 0)
283
 
        while pending:
284
 
            node = pending_pop()
285
 
            if node.parent_keys is not None:
286
 
                # We don't include ghost parents
287
 
                topo_order_append(node.key)
288
 
            for child_key in node.child_keys:
289
 
                child_node = self._nodes[child_key]
290
 
                seen_parents = num_seen_parents[child_key] + 1
291
 
                if seen_parents == len(child_node.parent_keys):
292
 
                    # All parents have been processed, enqueue this child
293
 
                    pending_append(child_node)
294
 
                    # This has been queued up, stop tracking it
295
 
                    del num_seen_parents[child_key]
296
 
                else:
297
 
                    num_seen_parents[child_key] = seen_parents
298
 
        # We started from the parents, so we don't need to do anymore work
299
 
        return topo_order
300
 
 
301
 
    def gc_sort(self):
302
 
        """Return a reverse topological ordering which is 'stable'.
303
 
 
304
 
        There are a few constraints:
305
 
          1) Reverse topological (all children before all parents)
306
 
          2) Grouped by prefix
307
 
          3) 'stable' sorting, so that we get the same result, independent of
308
 
             machine, or extra data.
309
 
        To do this, we use the same basic algorithm as topo_sort, but when we
310
 
        aren't sure what node to access next, we sort them lexicographically.
311
 
        """
312
 
        tips = self._find_tips()
313
 
        # Split the tips based on prefix
314
 
        prefix_tips = {}
315
 
        for node in tips:
316
 
            if node.key.__class__ is str or len(node.key) == 1:
317
 
                prefix = ''
318
 
            else:
319
 
                prefix = node.key[0]
320
 
            prefix_tips.setdefault(prefix, []).append(node)
321
 
 
322
 
        num_seen_children = dict.fromkeys(self._nodes, 0)
323
 
 
324
 
        result = []
325
 
        for prefix in sorted(prefix_tips):
326
 
            pending = sorted(prefix_tips[prefix], key=lambda n: n.key,
327
 
                             reverse=True)
328
 
            while pending:
329
 
                node = pending.pop()
330
 
                if node.parent_keys is None:
331
 
                    # Ghost node, skip it
332
 
                    continue
333
 
                result.append(node.key)
334
 
                for parent_key in sorted(node.parent_keys, reverse=True):
335
 
                    parent_node = self._nodes[parent_key]
336
 
                    seen_children = num_seen_children[parent_key] + 1
337
 
                    if seen_children == len(parent_node.child_keys):
338
 
                        # All children have been processed, enqueue this parent
339
 
                        pending.append(parent_node)
340
 
                        # This has been queued up, stop tracking it
341
 
                        del num_seen_children[parent_key]
342
 
                    else:
343
 
                        num_seen_children[parent_key] = seen_children
344
 
        return result
345
 
 
346
 
    def merge_sort(self, tip_key):
347
 
        """Compute the merge sorted graph output."""
348
 
        from breezy import tsort
349
 
        as_parent_map = dict((node.key, node.parent_keys)
350
 
                             for node in viewvalues(self._nodes)
351
 
                             if node.parent_keys is not None)
352
 
        # We intentionally always generate revnos and never force the
353
 
        # mainline_revisions
354
 
        # Strip the sequence_number that merge_sort generates
355
 
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
356
 
                for _, key, merge_depth, revno, end_of_merge
357
 
                in tsort.merge_sort(as_parent_map, tip_key,
358
 
                                    mainline_revisions=None,
359
 
                                    generate_revno=True)]
360
 
 
361
 
    def get_parent_keys(self, key):
362
 
        """Get the parents for a key
363
 
 
364
 
        Returns a list containg the parents keys. If the key is a ghost,
365
 
        None is returned. A KeyError will be raised if the key is not in
366
 
        the graph.
367
 
 
368
 
        :param keys: Key to check (eg revision_id)
369
 
        :return: A list of parents
370
 
        """
371
 
        return self._nodes[key].parent_keys
372
 
 
373
 
    def get_child_keys(self, key):
374
 
        """Get the children for a key
375
 
 
376
 
        Returns a list containg the children keys. A KeyError will be raised
377
 
        if the key is not in the graph.
378
 
 
379
 
        :param keys: Key to check (eg revision_id)
380
 
        :return: A list of children
381
 
        """
382
 
        return self._nodes[key].child_keys