← 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
  • Date: 2005-08-25 20:21:55 UTC
  • mfrom: (974.1.41)
  • mto: (1092.1.42) (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1178.
  • Revision ID: abentley@panoramicfeedback.com-20050825202155-fd1b58eb8867b367
Initial 'intervening revisions' implementation

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/revision.py
271
271
            except bzrlib.errors.NoSuchRevision, e:
272
272
                pass
273
273
        raise e
 
274
 
 
275
def get_intervening_revisions(ancestor_id, rev_id, rev_source, 
 
276
                              revision_history=None):
 
277
    """Find the longest line of descent from maybe_ancestor to revision.
 
278
    Revision history is followed where possible
 
279
 
 
280
    If ancestor_id == rev_id, list will be empty.
 
281
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
 
282
    If ancestor_id is not an ancestor, NotAncestor will be thrown
 
283
    """
 
284
    # This lists only the first descendant we encounter
 
285
    if ancestor_id == rev_id:
 
286
        return []
 
287
 
 
288
    def in_history(myrev):
 
289
        return revision_history is not None and myrev in revision_history
 
290
 
 
291
    def remove_broken_lines(revisions, rev_id, descendant_map):
 
292
        broken = set()
 
293
        for revision in revisions:
 
294
            cur_revision = revision
 
295
            while cur_revision != rev_id:
 
296
                cur_revision = descendant_map.get(cur_revision)
 
297
                if cur_revision is None:
 
298
                    broken.add(revision)
 
299
                    break
 
300
        return [r for r in revisions if r not in broken]
 
301
 
 
302
    def trace_ancestry():
 
303
        revisions = [rev_id]
 
304
        descendant_map = {}
 
305
        while len(revisions) > 0:
 
306
            remove_broken = False
 
307
            new_revisions = []
 
308
            for revision in revisions:
 
309
                parent_ids = [p.revision_id for p in 
 
310
                              rev_source.get_revision(revision).parents]
 
311
                for parent_id in parent_ids:
 
312
                    if parent_id == ancestor_id:
 
313
                        return revision, descendant_map
 
314
                    if descendant_map.has_key(parent_id):
 
315
                        if in_history(descendant_map[parent_id]):
 
316
                            continue
 
317
                        else:
 
318
                            remove_broken = True
 
319
                    descendant_map[parent_id] = revision
 
320
                    new_revisions.append(parent_id)
 
321
            if remove_broken:
 
322
                new_revisions = remove_broken_lines(new_revisions, rev_id,
 
323
                                                    descendant_map,)
 
324
            revisions = new_revisions
 
325
        raise Exception(revision, parent_ids)
 
326
        return None, descendant_map
 
327
 
 
328
    list_start, descendant_map = trace_ancestry()
 
329
    if list_start is None:
 
330
        raise Exception(descendant_map)
 
331
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
332
    intermediate_revisions = [list_start]
 
333
    next_revision = list_start
 
334
    while next_revision != rev_id:
 
335
        next_revision = descendant_map[next_revision]
 
336
        intermediate_revisions.append(next_revision)
 
337
    return intermediate_revisions