← 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-09-12 02:55:07 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050912025507-9c61cfce7dcf53c0
Reimplemented get_intervening_revisions for better scalability

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
from bzrlib.graph import farthest_nodes, node_distances, all_descendants
20
20
 
21
21
class RevisionReference(object):
22
22
    """
281
281
                if len(parents) == 0:
282
282
                    root = line
283
283
            except bzrlib.errors.NoSuchRevision:
 
284
                if line == revision:
 
285
                    raise
284
286
                parents = None
285
287
            if parents is not None:
286
288
                for parent in parents:
348
350
    Otherwise, rev_id will be the last entry.  ancestor_id will never appear.
349
351
    If ancestor_id is not an ancestor, NotAncestor will be thrown
350
352
    """
351
 
    [rev_source.get_revision(r) for r in (ancestor_id, rev_id)]
352
 
    if ancestor_id == rev_id:
353
 
        return []
354
 
    def historical_lines(line):
355
 
        """Return a tuple of historical/non_historical lines, for sorting.
356
 
        The non_historical count is negative, since non_historical lines are
357
 
        a bad thing.
358
 
        """
359
 
        good_count = 0
360
 
        bad_count = 0
361
 
        for revision in line:
362
 
            if revision in revision_history:
363
 
                good_count += 1
364
 
            else:
365
 
                bad_count -= 1
366
 
        return good_count, bad_count
367
 
    active = [[rev_id]]
368
 
    successful_lines = []
369
 
    while len(active) > 0:
370
 
        new_active = []
371
 
        for line in active:
372
 
            parent_ids = [p.revision_id for p in 
373
 
                          rev_source.get_revision(line[-1]).parents]
374
 
            for parent in parent_ids:
375
 
                line_copy = line[:]
376
 
                if parent == ancestor_id:
377
 
                    successful_lines.append(line_copy)
378
 
                else:
379
 
                    line_copy.append(parent)
380
 
                    new_active.append(line_copy)
381
 
        active = new_active
382
 
    if len(successful_lines) == 0:
383
 
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
384
 
    for line in successful_lines:
385
 
        line.reverse()
386
 
    if revision_history is not None:
387
 
        by_historical_lines = []
388
 
        for line in successful_lines:
389
 
            count = historical_lines(line)
390
 
            by_historical_lines.append((count, line))
391
 
        by_historical_lines.sort()
392
 
        if by_historical_lines[-1][0][0] > 0:
393
 
            return by_historical_lines[-1][1]
394
 
    assert len(successful_lines)
395
 
    successful_lines.sort(cmp, len)
396
 
    return successful_lines[-1]
 
353
    root, ancestors, descendants = revision_graph(rev_id, rev_source)
 
354
    if len(descendants) == 0:
 
355
        raise NoSuchRevision(rev_source, rev_id)
 
356
    if ancestor_id not in descendants:
 
357
        rev_source.get_revision(ancestor_id)
 
358
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
359
    root_descendants = all_descendants(descendants, ancestor_id)
 
360
    root_descendants.add(ancestor_id)
 
361
    if rev_id not in root_descendants:
 
362
        raise bzrlib.errors.NotAncestor(rev_id, ancestor_id)
 
363
    distances = node_distances(descendants, ancestors, ancestor_id,
 
364
                               root_descendants=root_descendants)
 
365
 
 
366
    def best_ancestor(rev_id):
 
367
        best = None
 
368
        for anc_id in ancestors[rev_id]:
 
369
            try:
 
370
                distance = distances[anc_id]
 
371
            except KeyError:
 
372
                continue
 
373
            if revision_history is not None and anc_id in revision_history:
 
374
                return anc_id
 
375
            elif best is None or distance > best[1]:
 
376
                best = (anc_id, distance)
 
377
        return best[0]
 
378
 
 
379
    next = rev_id
 
380
    path = []
 
381
    while next != ancestor_id:
 
382
        path.append(next)
 
383
        next = best_ancestor(next)
 
384
    path.reverse()
 
385
    return path