← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

Show diffs side-by-side

added added

removed removed

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