← 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: Martin Pool
  • Date: 2009-09-14 01:48:28 UTC
  • mfrom: (4685 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4688.
  • Revision ID: mbp@sourcefrog.net-20090914014828-ydr9rlkdfq2sv57z
Merge news

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
18
18
"""
19
19
 
20
20
from bzrlib import (
 
21
    errors,
21
22
    revision,
22
23
    )
23
24
 
40
41
            self.parent_keys, self.child_keys)
41
42
 
42
43
 
 
44
class _MergeSortNode(object):
 
45
    """Information about a specific node in the merge graph."""
 
46
 
 
47
    __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')
 
48
 
 
49
    def __init__(self, key, merge_depth, revno, end_of_merge):
 
50
        self.key = key
 
51
        self.merge_depth = merge_depth
 
52
        self.revno = revno
 
53
        self.end_of_merge = end_of_merge
 
54
 
 
55
 
43
56
class KnownGraph(object):
44
57
    """This is a class which assumes we already know the full graph."""
45
58
 
84
97
        return [node for node in self._nodes.itervalues()
85
98
                if not node.parent_keys]
86
99
 
 
100
    def _find_tips(self):
 
101
        return [node for node in self._nodes.itervalues()
 
102
                      if not node.child_keys]
 
103
 
87
104
    def _find_gdfo(self):
88
105
        nodes = self._nodes
89
106
        known_parent_gdfos = {}
171
188
            self._known_heads[heads_key] = heads
172
189
        return heads
173
190
 
 
191
    def topo_sort(self):
 
192
        """Return the nodes in topological order.
 
193
 
 
194
        All parents must occur before all children.
 
195
        """
 
196
        for node in self._nodes.itervalues():
 
197
            if node.gdfo is None:
 
198
                raise errors.GraphCycleError(self._nodes)
 
199
        pending = self._find_tails()
 
200
        pending_pop = pending.pop
 
201
        pending_append = pending.append
 
202
 
 
203
        topo_order = []
 
204
        topo_order_append = topo_order.append
 
205
 
 
206
        num_seen_parents = dict.fromkeys(self._nodes, 0)
 
207
        while pending:
 
208
            node = pending_pop()
 
209
            if node.parent_keys is not None:
 
210
                # We don't include ghost parents
 
211
                topo_order_append(node.key)
 
212
            for child_key in node.child_keys:
 
213
                child_node = self._nodes[child_key]
 
214
                seen_parents = num_seen_parents[child_key] + 1
 
215
                if seen_parents == len(child_node.parent_keys):
 
216
                    # All parents have been processed, enqueue this child
 
217
                    pending_append(child_node)
 
218
                    # This has been queued up, stop tracking it
 
219
                    del num_seen_parents[child_key]
 
220
                else:
 
221
                    num_seen_parents[child_key] = seen_parents
 
222
        # We started from the parents, so we don't need to do anymore work
 
223
        return topo_order
 
224
 
 
225
    def gc_sort(self):
 
226
        """Return a reverse topological ordering which is 'stable'.
 
227
 
 
228
        There are a few constraints:
 
229
          1) Reverse topological (all children before all parents)
 
230
          2) Grouped by prefix
 
231
          3) 'stable' sorting, so that we get the same result, independent of
 
232
             machine, or extra data.
 
233
        To do this, we use the same basic algorithm as topo_sort, but when we
 
234
        aren't sure what node to access next, we sort them lexicographically.
 
235
        """
 
236
        tips = self._find_tips()
 
237
        # Split the tips based on prefix
 
238
        prefix_tips = {}
 
239
        for node in tips:
 
240
            if node.key.__class__ is str or len(node.key) == 1:
 
241
                prefix = ''
 
242
            else:
 
243
                prefix = node.key[0]
 
244
            prefix_tips.setdefault(prefix, []).append(node)
 
245
 
 
246
        num_seen_children = dict.fromkeys(self._nodes, 0)
 
247
 
 
248
        result = []
 
249
        for prefix in sorted(prefix_tips):
 
250
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
251
                             reverse=True)
 
252
            while pending:
 
253
                node = pending.pop()
 
254
                if node.parent_keys is None:
 
255
                    # Ghost node, skip it
 
256
                    continue
 
257
                result.append(node.key)
 
258
                for parent_key in sorted(node.parent_keys, reverse=True):
 
259
                    parent_node = self._nodes[parent_key]
 
260
                    seen_children = num_seen_children[parent_key] + 1
 
261
                    if seen_children == len(parent_node.child_keys):
 
262
                        # All children have been processed, enqueue this parent
 
263
                        pending.append(parent_node)
 
264
                        # This has been queued up, stop tracking it
 
265
                        del num_seen_children[parent_key]
 
266
                    else:
 
267
                        num_seen_children[parent_key] = seen_children
 
268
        return result
 
269
 
 
270
    def merge_sort(self, tip_key):
 
271
        """Compute the merge sorted graph output."""
 
272
        from bzrlib import tsort
 
273
        as_parent_map = dict((node.key, node.parent_keys)
 
274
                             for node in self._nodes.itervalues()
 
275
                              if node.parent_keys is not None)
 
276
        # We intentionally always generate revnos and never force the
 
277
        # mainline_revisions
 
278
        # Strip the sequence_number that merge_sort generates
 
279
        return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
 
280
                for _, key, merge_depth, revno, end_of_merge
 
281
                 in tsort.merge_sort(as_parent_map, tip_key,
 
282
                                     mainline_revisions=None,
 
283
                                     generate_revno=True)]
 
284
    
 
285
    def get_parent_keys(self, key):
 
286
        """Get the parents for a key
 
287
        
 
288
        Returns a list containg the parents keys. If the key is a ghost,
 
289
        None is returned. A KeyError will be raised if the key is not in
 
290
        the graph.
 
291
        
 
292
        :param keys: Key to check (eg revision_id)
 
293
        :return: A list of parents
 
294
        """
 
295
        return self._nodes[key].parent_keys
 
296
 
 
297
    def get_child_keys(self, key):
 
298
        """Get the children for a key
 
299
        
 
300
        Returns a list containg the children keys. A KeyError will be raised
 
301
        if the key is not in the graph.
 
302
        
 
303
        :param keys: Key to check (eg revision_id)
 
304
        :return: A list of children
 
305
        """
 
306
        return self._nodes[key].child_keys