← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: aaron.bentley at utoronto
  • Date: 2005-09-06 05:23:17 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050906052317-977d6da5f80732b4
Initial import of common-ancestor detection

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
16
16
 
17
17
 
18
18
import bzrlib.errors
19
 
 
 
19
from bzrlib.graph import farthest_node
20
20
 
21
21
class RevisionReference(object):
22
22
    """
259
259
        raise bzrlib.errors.AmbiguousBase((a_closest[0], b_closest[0]))
260
260
    return a_closest[0]
261
261
 
 
262
def revision_graph(revision, revision_source):
 
263
    ancestors = {}
 
264
    descendants = {}
 
265
    lines = [revision]
 
266
    root = None
 
267
    while len(lines) > 0:
 
268
        new_lines = set()
 
269
        for line in lines:
 
270
            try:
 
271
                rev = revision_source.get_revision(line)
 
272
                parents = [p.revision_id for p in rev.parents]
 
273
                if len(parents) == 0:
 
274
                    root = line
 
275
            except bzrlib.errors.NoSuchRevision:
 
276
                parents = []
 
277
            for parent in parents:
 
278
                if parent not in ancestors:
 
279
                    new_lines.add(parent)
 
280
                if parent not in descendants:
 
281
                    descendants[parent] = {}
 
282
                descendants[parent][line] = 1
 
283
            ancestors[line] = set(parents)
 
284
        lines = new_lines
 
285
    return root, ancestors, descendants
 
286
 
 
287
def combined_graph(revision_a, revision_b, revision_source):
 
288
    root, ancestors, descendants = revision_graph(revision_a, revision_source)
 
289
    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
 
290
                                                        revision_source)
 
291
    assert root == root_b
 
292
    common = set()
 
293
    for node, node_anc in ancestors_b.iteritems():
 
294
        if node in ancestors:
 
295
            common.add(node)
 
296
        else:
 
297
            ancestors[node] = set()
 
298
        ancestors[node].update(node_anc)
 
299
    for node, node_dec in descendants_b.iteritems():
 
300
        if node not in descendants:
 
301
            descendants[node] = set()
 
302
        ancestors[node].update(node_anc)
 
303
    return root, ancestors, descendants, common
 
304
 
 
305
def common_ancestor(revision_a, revision_b, revision_source):
 
306
    root, ancestors, descendants, common = \
 
307
        combined_graph(revision_a, revision_b, revision_source)
 
308
    nodes = farthest_node(ancestors, descendants, root)
 
309
    for node in nodes:
 
310
        if node in common:
 
311
            return node
 
312
 
262
313
class MultipleRevisionSources(object):
263
314
    """Proxy that looks in multiple branches for revisions."""
264
315
    def __init__(self, *args):