« back to all changes in this revision
Viewing changes to bzrlib/graph_walker.py
- browse files at revision 2490.2.13
- compare with another revision
- compare with revision 6617
- download diff
- download tarball
- view history from revision 2490.2.13
- Committer: Aaron Bentley
- Date: 2007-06-08 15:03:32 UTC
- mto: This revision was merged to the branch mainline in revision 2534.
- Revision ID: abentley@panoramicfeedback.com-20070608150332-jxt1yx9hy7dmhxhv
Update distinct -> lowest, refactor, add ParentsProvider concept
added
removed
bzrlib/graph_walker.py
18
18
from bzrlib.revision import NULL_REVISION
19
19
20
20
21
class _StackedParentsProvider(object):
22
23
def __init__(self, parent_providers):
24
self._parent_providers = parent_providers
25
26
def get_parents(self, revision_ids):
27
"""
28
Find revision ids of the parents of a list of revisions
29
30
A list is returned of the same length as the input. Each entry
31
is a list of parent ids for the corresponding input revision.
32
33
[NULL_REVISION] is used as the parent of the first user-committed
34
revision. Its parent list is empty.
35
36
If the revision is not present (i.e. a ghost), None is used in place
37
of the list of parents.
38
"""
39
found = {}
40
for parents_provider in self._parent_providers:
41
parent_list = parents_provider.get_parents(
42
[r for r in revision_ids if r not in found])
43
new_found = dict((k, v) for k, v in zip(revision_ids, parent_list)
44
if v is not None)
45
found.update(new_found)
46
if len(found) == len(revision_ids):
47
break
48
return [found.get(r) for r in revision_ids]
49
50
21
51
class GraphWalker(object):
22
52
"""Provide incremental access to revision graphs.
23
53
25
55
specialize it for other repository types.
26
56
"""
27
57
28
def __init__(self, graphs):
58
def __init__(self, parents_provider):
29
59
"""Construct a GraphWalker that uses several graphs as its input
30
60
31
61
This should not normally be invoked directly, because there may be
32
62
specialized implementations for particular repository types. See
33
63
Repository.get_graph_walker()
34
64
35
Note that the input graphs *will* be altered to use NULL_REVISION as
36
their origin.
37
"""
38
self._graph = graphs
39
self._ancestors = []
40
self._descendants = []
41
for graph in graphs:
42
self._extract_data(graph)
43
44
def _extract_data(self, graph):
45
"""Convert graph to use NULL_REVISION as origin"""
46
ancestors = dict(graph.get_ancestors())
47
descendants = dict(graph.get_descendants())
48
descendants[NULL_REVISION] = {}
49
ancestors[NULL_REVISION] = []
50
for root in graph.roots:
51
descendants[NULL_REVISION][root] = 1
52
ancestors[root] = ancestors[root] + [NULL_REVISION]
53
for ghost in graph.ghosts:
54
# ghosts act as roots for the purpose of finding
55
# the longest paths from the root: any ghost *might*
56
# be directly attached to the root, so we treat them
57
# as being such.
58
# ghost now descends from NULL
59
descendants[NULL_REVISION][ghost] = 1
60
# that is it has an ancestor of NULL
61
ancestors[ghost] = [NULL_REVISION]
62
self._ancestors.append(ancestors)
63
self._descendants.append(descendants)
64
65
def distance_from_origin(self, revisions):
66
"""Determine the of the named revisions from the origin
67
68
:param revisions: The revisions to examine
69
:return: A list of revision distances. None is provided if no distance
70
could be found.
71
"""
72
distances = graph.node_distances(self._descendants[0],
73
self._ancestors[0],
74
NULL_REVISION)
75
return [distances.get(r) for r in revisions]
76
77
def distinct_common(self, *revisions):
78
"""Determine the distinct common ancestors of the provided revisions
79
80
A distinct common ancestor is a common ancestor none of whose
81
descendants are common ancestors.
65
:param parents_func: a list of objects providing a get_parents call
66
conforming to the behavior of GraphWalker.get_parents
67
"""
68
self.get_parents = parents_provider.get_parents
69
70
def find_lca(self, *revisions):
71
"""Determine the lowest common ancestors of the provided revisions
72
73
A lowest common ancestor is a common ancestor none of whose
74
descendants are common ancestors. In graphs, unlike trees, there may
75
be multiple lowest common ancestors.
82
76
83
77
This algorithm has two phases. Phase 1 identifies border ancestors,
84
and phase 2 filters border ancestors to determine distinct ancestors.
78
and phase 2 filters border ancestors to determine lowest common
79
ancestors.
85
80
86
81
In phase 1, border ancestors are identified, using a breadth-first
87
82
search starting at the bottom of the graph. Searches are stopped
88
83
whenever a node or one of its descendants is determined to be common
89
84
90
In phase 2, the border ancestors are filtered to find the distinct
85
In phase 2, the border ancestors are filtered to find the least
91
86
common ancestors. This is done by searching the ancestries of each
92
87
border ancestor.
93
88
94
Phase 2 is perfomed on the principle that a border ancestor that is not
95
an ancestor of any other border ancestor is a distinct ancestor.
89
Phase 2 is perfomed on the principle that a border ancestor that is
90
not an ancestor of any other border ancestor is a least common
91
ancestor.
96
92
97
93
Searches are stopped when they find a node that is determined to be a
98
94
common ancestor of all border ancestors, because this shows that it
105
101
ancestor of all border ancestors.
106
102
"""
107
103
border_common = self._find_border_ancestors(revisions)
108
return self._filter_candidate_dca(border_common)
104
return self._filter_candidate_lca(border_common)
109
105
110
106
def _find_border_ancestors(self, revisions):
111
107
"""Find common ancestors with at least one uncommon descendant.
118
114
"""
119
115
walkers = [_AncestryWalker(r, self) for r in revisions]
120
116
active_walkers = walkers[:]
121
maybe_distinct_common = set()
117
border_ancestors = set()
122
118
seen_ancestors = set()
123
119
while True:
124
120
if len(active_walkers) == 0:
125
return maybe_distinct_common
121
return border_ancestors
126
122
newly_seen = set()
127
123
new_active_walkers = []
128
124
for walker in active_walkers:
138
134
if revision not in walker.seen:
139
135
break
140
136
else:
141
maybe_distinct_common.add(revision)
137
border_ancestors.add(revision)
142
138
for walker in walkers:
143
w_seen_ancestors = walker.find_seen_ancestors(revision)
139
w_seen_ancestors = walker.find_seen_ancestors(
140
revision)
144
141
walker.stop_searching_any(w_seen_ancestors)
145
142
146
def _filter_candidate_dca(self, candidate_dca):
143
def _filter_candidate_lca(self, candidate_lca):
147
144
"""Remove candidates which are ancestors of other candidates.
148
145
149
146
This is done by searching the ancestries of each border ancestor. It
150
147
is perfomed on the principle that a border ancestor that is not an
151
ancestor of any other border ancestor is a distinct ancestor.
148
ancestor of any other border ancestor is a lowest common ancestor.
152
149
153
150
Searches are stopped when they find a node that is determined to be a
154
151
common ancestor of all border ancestors, because this shows that it
158
155
of the shortest path from a candidate to an ancestor common to all
159
156
candidates.
160
157
"""
161
walkers = dict((c, _AncestryWalker(c, self)) for c in candidate_dca)
158
walkers = dict((c, _AncestryWalker(c, self)) for c in candidate_lca)
162
159
active_walkers = dict(walkers)
163
160
# skip over the actual candidate for each walker
164
161
for walker in active_walkers.itervalues():
171
168
del active_walkers[candidate]
172
169
continue
173
170
for ancestor in ancestors:
174
if ancestor in candidate_dca:
175
candidate_dca.remove(ancestor)
171
if ancestor in candidate_lca:
172
candidate_lca.remove(ancestor)
176
173
del walkers[ancestor]
177
174
if ancestor in active_walkers:
178
175
del active_walkers[ancestor]
187
184
seen_ancestors =\
188
185
walker.find_seen_ancestors(ancestor)
189
186
walker.stop_searching_any(seen_ancestors)
190
return candidate_dca
191
192
def unique_common(self, left_revision, right_revision):
193
"""Find a unique distinct common ancestor.
194
195
Find distinct common ancestors. If there is no unique distinct common
196
ancestor, find the distinct common ancestors of those ancestors.
197
198
Iteration stops when a unique distinct common ancestor is found.
199
The graph origin is necessarily a unique common ancestor
187
return candidate_lca
188
189
def find_unique_lca(self, left_revision, right_revision):
190
"""Find a unique LCA.
191
192
Find lowest common ancestors. If there is no unique common
193
ancestor, find the lowest common ancestors of those ancestors.
194
195
Iteration stops when a unique lowest common ancestor is found.
196
The graph origin is necessarily a unique lowest common ancestor.
200
197
201
198
Note that None is not an acceptable substitute for NULL_REVISION.
199
in the input for this method.
202
200
"""
203
201
revisions = [left_revision, right_revision]
204
202
while True:
205
distinct = self.distinct_common(*revisions)
206
if len(distinct) == 1:
207
return distinct.pop()
208
revisions = distinct
209
210
def get_parents(self, revision):
211
"""Determine the parents of a revision"""
212
for ancestors in self._ancestors:
213
try:
214
return ancestors[revision]
215
except KeyError:
216
pass
217
else:
218
raise KeyError
203
lca = self.find_lca(*revisions)
204
if len(lca) == 1:
205
return lca.pop()
206
revisions = lca
219
207
220
208
221
209
class _AncestryWalker(object):
246
234
self._search_revisions = self._start
247
235
else:
248
236
new_search_revisions = set()
249
for revision in self._search_revisions:
250
new_search_revisions.update(p for p in
251
self._graph_walker.get_parents(revision) if p
252
not in self.seen)
237
for parents in self._graph_walker.get_parents(
238
self._search_revisions):
239
if parents is None:
240
continue
241
new_search_revisions.update(p for p in parents if
242
p not in self.seen)
253
243
self._search_revisions = new_search_revisions
254
244
if len(self._search_revisions) == 0:
255
245
raise StopIteration()
Loggerhead is a web-based interface for Breezy
Version: 2.0.1