← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph_walker.py

  • Committer: Aaron Bentley
  • Date: 2007-05-27 16:15:19 UTC
  • mto: This revision was merged to the branch mainline in revision 2534.
  • Revision ID: aaron.bentley@utoronto.ca-20070527161519-noiyd4kly31xxclc
Fix minimal common ancestor algorithm for non-minimal perhipheral ancestors

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph_walker.py
68
68
        descendants are common ancestors.  (This is not quite the standard
69
69
        graph theory definition)
70
70
        """
 
71
        candidate_mca = self._find_candidate_mca(revisions)
 
72
        return self._filter_candidate_mca(candidate_mca)
 
73
 
 
74
    def _find_candidate_mca(self, revisions):
71
75
        walkers = [_AncestryWalker(r, self) for r in revisions]
72
76
        active_walkers = walkers[:]
73
77
        maybe_minimal_common = set()
74
78
        seen_ancestors = set()
75
79
        while True:
76
80
            if len(active_walkers) == 0:
77
 
                maybe_minimal_common.difference_update(seen_ancestors)
78
81
                return maybe_minimal_common
79
82
            newly_seen = set()
80
83
            new_active_walkers = []
95
98
                    for walker in walkers:
96
99
                        w_seen_ancestors = walker.find_seen_ancestors(revision)
97
100
                        walker.stop_tracing_any(w_seen_ancestors)
98
 
                        w_seen_ancestors.discard(revision)
99
 
                        seen_ancestors.update(w_seen_ancestors)
 
101
 
 
102
    def _filter_candidate_mca(self, candidate_mca):
 
103
        """Remove candidates which are ancestors of other candidates"""
 
104
        walkers = dict((c, _AncestryWalker(c, self)) for c in candidate_mca)
 
105
        active_walkers = dict(walkers)
 
106
        # skip over the actual candidate for each walker
 
107
        for walker in active_walkers.itervalues():
 
108
            walker.next()
 
109
        while len(active_walkers) > 0:
 
110
            for candidate, walker in list(active_walkers.iteritems()):
 
111
                try:
 
112
                    ancestors = walker.next()
 
113
                except StopIteration:
 
114
                    del active_walkers[candidate]
 
115
                    continue
 
116
                for ancestor in ancestors:
 
117
                    if ancestor in candidate_mca:
 
118
                        candidate_mca.remove(ancestor)
 
119
                        del walkers[ancestor]
 
120
                        if ancestor in active_walkers:
 
121
                            del active_walkers[ancestor]
 
122
                    for walker in walkers.itervalues():
 
123
                        if ancestor not in walker.seen:
 
124
                            break
 
125
                    else:
 
126
                        # if this revision was seen by all walkers, then it
 
127
                        # is a descendant of all candidates, so we can stop
 
128
                        # tracing it, and any seen ancestors
 
129
                        for walker in walkers.itervalues():
 
130
                            seen_ancestors =\
 
131
                                walker.find_seen_ancestors(ancestor)
 
132
                            walker.stop_tracing_any(seen_ancestors)
 
133
        return candidate_mca
100
134
 
101
135
    def unique_common(self, left_revision, right_revision):
102
136
        """Find a unique minimal common ancestor.