« back to all changes in this revision
Viewing changes to bzrlib/reconcile.py
- browse files at revision 1570.1.4
- compare with another revision
- compare with revision 1536
- download diff
- download tarball
- view history from revision 1570.1.4
- Committer: Robert Collins
- Date: 2006-02-23 14:24:48 UTC
- mto: (1587.1.1 integration)
- mto: This revision was merged to the branch mainline in revision 1588.
- Revision ID: robertc@robertcollins.net-20060223142448-be912a128be4d590
Somewhat optimised version of reconciler.
- files modified:
- bzrlib/reconcile.py
added
removed
bzrlib/reconcile.py
86
86
87
87
# the total set of revisions to process
88
88
self.pending = set([file_id for file_id in self.repo.revision_store])
89
90
89
91
# the current line of history being processed.
90
92
# once we add in per inventory root ids this will involve a single
91
93
# pass within the revision knit at that point.
92
# this contains (revision_id, not_ghost_parents) tuples.
94
# these contain respectively the revision id and the not_ghost_parents.
93
95
self._rev_stack = []
96
self._parent_stack = []
97
self._pending_stack = []
98
# actual queue to reinsert. This is a single pass queue we can use to
99
# regenerate the inventory versioned file, and holds
100
# (rev_id, non_ghost_parents) entries
101
self._work_queue = []
102
# this is a set for fast lookups of queued revisions
103
self._work_set = set()
94
104
# total steps = 1 read per revision + one insert into the inventory
95
105
self.total = len(self.pending) * 2
96
106
self.count = 0
97
107
98
# outer loop to ensure we hit every revision
99
while self.pending:
100
self._stack_revision()
101
# now we have one revision on the todo stack.
102
# try to process the tip of the stack and if we cant
103
# insert it yet queue the revision ids we need to be
104
# able to add it. Rinse and repeat until the stack is
105
# empty and then we grab another pending revision if
106
# there are any
107
while len(self._rev_stack):
108
rev_id, parents = self._rev_stack[-1]
109
unavailable = [p for p in parents if p not in new_inventory]
110
if len(unavailable) == 0:
111
# this entry can be popped off.
112
self.pb.update('regenerating', self.count, self.total)
113
self.count += 1
114
new_inventory.add(rev_id, parents, self.inventory.get(rev_id))
115
self._rev_stack.pop()
108
# mapping from revision_id to parents
109
self._rev_graph = {}
110
# we need the revision id of each revision and its available parents list
111
# we could do this on demand, but its easy to just build a graph.
112
for rev_id in self.pending:
113
# put a revision into the to-process queue
114
self._graph_revision(rev_id)
115
116
# now we do a depth first search of the revision graph until its empty.
117
# this gives us a topological order across all revisions in
118
# self._all_revisions.
119
# This is flattened to avoid deep recursion:
120
# At each step in the call graph we need to know which parent we are on.
121
# we do this by having three variables for each stack frame:
122
# revision_id being descended into (self._rev_stack)
123
# parents list for using when regenerating that revision_id's inventory
124
# (self._parent_stack)
125
# current queue of parents to descend into
126
# (self._pending_stack)
127
# putting all the parents into a pending list, left to
128
# right and processing the right most one each time. The same parent
129
# may occur at multiple places in the stack - thats fine. We check its
130
# not in the output before processing. However revisions cannot
131
# appear twice.
132
# the algorithm is roughly:
133
# for revision, parents in _rev_graph.items():
134
# if revision in self._all_revisions:
135
# continue
136
# add_revision_parents(revision, parents)
137
# def add_revision_parents(revision, parents)
138
# fpr parent in parents:
139
# add_revision_parents(parent, parent.parents)
140
# self._all_revisions.append(revision)
141
# self._all_revision_parents.appent(parents)
142
# however we tune this to visit fragmens of the graph
143
# and not double-visit entries.
144
# nevertheless the output is a
145
# self._work_queue of revisions, nonghost parents in
146
# topological order and
147
# a self._work_set which is a complete set of revisions.
148
while self._rev_graph:
149
rev_id, parents = self._rev_graph.iteritems().next()
150
# rev_id
151
self._stack_revision(rev_id, parents)
152
while self._rev_stack:
153
# loop until this call completes.
154
parents_to_visit = self._pending_stack[-1]
155
# if all parents are done, the revision is done
156
if not parents_to_visit:
157
# append the revision to the topo sorted list
158
self._unstack_revision()
116
159
else:
117
# push the needed parents onto the stack
118
for parent in unavailable:
119
self._stack_revision(parent)
160
while self._pending_stack[-1]:
161
# recurse depth first into a single parent
162
next_rev_id = self._pending_stack[-1].pop()
163
if next_rev_id in self._work_set:
164
# this parent was completed by a child on the
165
# call stack. skip it.
166
continue
167
# push it into the call stack
168
self._stack_revision(next_rev_id, self._rev_graph[next_rev_id])
169
# and do not continue processing parents until this 'call'
170
# has recursed.
171
break
172
173
# we are now recursing down a call stack.
174
# its a width first search which
175
176
### Useful if fiddling with this code.
177
### # cross check
178
### for index in range(len(self._work_queue)):
179
### rev = self._work_queue[index][0]
180
### for left_index in range(index):
181
### if rev in self._work_queue[left_index][1]:
182
### print "revision in parent list of earlier revision"
183
### import pdb;pdb.set_trace()
184
185
# we have topological order of revisions and non ghost parents ready.
186
while self._work_queue:
187
rev_id, parents = self._work_queue.pop(0)
188
# double check this really is in topological order.
189
unavailable = [p for p in parents if p not in new_inventory]
190
assert len(unavailable) == 0
191
# this entry has all the non ghost parents in the inventory
192
# file already.
193
self._reweave_step('adding inventories')
194
new_inventory.add(rev_id, parents, self.inventory.get(rev_id))
195
196
# if this worked, the set of new_inventory.names should equal
197
# self.pending
198
assert set(new_inventory.names()) == self.pending
120
199
self.pb.update('Writing weave')
121
200
self.repo.control_weaves.put_weave('inventory',
122
201
new_inventory,
124
203
self.inventory = None
125
204
self.pb.note('Inventory regenerated.')
126
205
127
def _stack_revision(self, rev_id=None):
128
"""Add rev_id to the pending revision stack."""
129
if rev_id is None:
130
# pick a random revision
131
rev_id = self.pending.pop()
132
self.pb.update('regenerating', self.count, self.total)
133
self.count += 1
206
def _graph_revision(self, rev_id):
207
"""Load a revision into the revision graph."""
208
# pick a random revision
209
# analyse revision id rev_id and put it in the stack.
210
self._reweave_step('loading revisions')
134
211
rev = self.repo.get_revision(rev_id)
135
212
assert rev.revision_id == rev_id
136
213
parents = []
139
216
parents.append(parent)
140
217
else:
141
218
mutter('found ghost %s', parent)
142
self._rev_stack.append((rev_id, parents))
143
219
self._rev_graph[rev_id] = parents
220
221
def _stack_revision(self, rev_id, parents):
222
"""Add rev_id to the pending revision stack."""
223
self._rev_stack.append(rev_id)
224
self._parent_stack.append(parents)
225
self._pending_stack.append(list(parents))
226
227
def _unstack_revision(self):
228
"""A revision has been completed.
229
230
The revision is added to the work queue, and the data for
231
it popped from the call stack.
232
"""
233
rev_id = self._rev_stack.pop()
234
parents = self._parent_stack.pop()
235
self._pending_stack.pop()
236
self._work_queue.append((rev_id, parents))
237
self._work_set.add(rev_id)
238
# and remove it from the rev graph as its now complete
239
self._rev_graph.pop(rev_id)
240
241
def _reweave_step(self, message):
242
"""Mark a single step of regeneration complete."""
243
self.pb.update(message, self.count, self.total)
244
self.count += 1
Loggerhead is a web-based interface for Breezy
Version: 2.0.1