← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

  • Committer: Martin Pool
  • Date: 2005-09-05 08:00:35 UTC
  • Revision ID: mbp@sourcefrog.net-20050905080035-e0439293f8b6b9f9
- start splitting code for xml (de)serialization away from objects
  preparatory to supporting multiple formats by a single library

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
 
from bzrlib.graph import farthest_nodes
 
19
 
20
20
 
21
21
class RevisionReference(object):
22
22
    """
228
228
    return matches
229
229
 
230
230
 
231
 
def old_common_ancestor(revision_a, revision_b, revision_source):
 
231
def common_ancestor(revision_a, revision_b, revision_source):
232
232
    """Find the ancestor common to both revisions that is closest to both.
233
233
    """
234
234
    from bzrlib.trace import mutter
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
 
    """Produce a graph of the ancestry of the specified revision.
264
 
    Return root, ancestors map, descendants map
265
 
 
266
 
    TODO: Produce graphs with the NULL revision as root, so that we can find
267
 
    a common even when trees are not branches don't represent a single line
268
 
    of descent.
269
 
    """
270
 
    ancestors = {}
271
 
    descendants = {}
272
 
    lines = [revision]
273
 
    root = None
274
 
    descendants[revision] = {}
275
 
    while len(lines) > 0:
276
 
        new_lines = set()
277
 
        for line in lines:
278
 
            try:
279
 
                rev = revision_source.get_revision(line)
280
 
                parents = [p.revision_id for p in rev.parents]
281
 
                if len(parents) == 0:
282
 
                    root = line
283
 
            except bzrlib.errors.NoSuchRevision:
284
 
                parents = None
285
 
            if parents is not None:
286
 
                for parent in parents:
287
 
                    if parent not in ancestors:
288
 
                        new_lines.add(parent)
289
 
                    if parent not in descendants:
290
 
                        descendants[parent] = {}
291
 
                    descendants[parent][line] = 1
292
 
            if parents is not None:
293
 
                ancestors[line] = set(parents)
294
 
        lines = new_lines
295
 
    assert root not in descendants[root]
296
 
    assert root not in ancestors[root]
297
 
    return root, ancestors, descendants
298
 
 
299
 
def combined_graph(revision_a, revision_b, revision_source):
300
 
    """Produce a combined ancestry graph.
301
 
    Return graph root, ancestors map, descendants map, set of common nodes"""
302
 
    root, ancestors, descendants = revision_graph(revision_a, revision_source)
303
 
    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 
304
 
                                                        revision_source)
305
 
    assert root == root_b
306
 
    common = set()
307
 
    for node, node_anc in ancestors_b.iteritems():
308
 
        if node in ancestors:
309
 
            common.add(node)
310
 
        else:
311
 
            ancestors[node] = set()
312
 
        ancestors[node].update(node_anc)
313
 
    for node, node_dec in descendants_b.iteritems():
314
 
        if node not in descendants:
315
 
            descendants[node] = set()
316
 
        descendants[node].update(node_dec)
317
 
    return root, ancestors, descendants, common
318
 
 
319
 
def common_ancestor(revision_a, revision_b, revision_source):
320
 
    root, ancestors, descendants, common = \
321
 
        combined_graph(revision_a, revision_b, revision_source)
322
 
    nodes = farthest_nodes(descendants, ancestors, root)
323
 
    for node in nodes:
324
 
        if node in common:
325
 
            return node
326
 
 
327
262
class MultipleRevisionSources(object):
328
263
    """Proxy that looks in multiple branches for revisions."""
329
264
    def __init__(self, *args):