« back to all changes in this revision
Viewing changes to bzrlib/reconcile.py
- browse files at revision 1570.1.6
- compare with another revision
- compare with revision 4634.108.7
- download diff
- download tarball
- view history from revision 1570.1.6
- Committer: Robert Collins
- Date: 2006-02-24 13:32:45 UTC
- mto: (1587.1.1 integration)
- mto: This revision was merged to the branch mainline in revision 1588.
- Revision ID: robertc@robertcollins.net-20060224133245-7a448981e53b91f4
Update fast topological_sort to be a function and to have the topo_sort tests run against it.
- files modified:
- bzrlib/reconcile.py
added
removed
bzrlib/reconcile.py
26
26
"""
27
27
28
28
29
import os
30
31
32
29
import bzrlib.branch
30
import bzrlib.errors as errors
33
31
import bzrlib.progress
34
32
from bzrlib.trace import mutter
35
33
import bzrlib.ui as ui
49
47
reconciler.reconcile()
50
48
51
49
52
class Reconciler(object):
53
"""Reconcilers are used to reconcile existing data.
54
55
Currently this is limited to a single repository, and consists
56
of an inventory reweave with revision cross-checks.
50
def topological_sort(graph):
51
"""Topological sort a graph.
52
53
graph -- sequence of pairs of node->parents_list.
54
55
The result is a list of node names, such that all parents come before
56
their children.
57
58
Nodes at the same depth are returned in sorted order.
59
60
node identifiers can be any hashable object, and are typically strings.
57
61
"""
58
59
def __init__(self, dir):
60
self.bzrdir = dir
61
62
def reconcile(self):
63
"""Actually perform the reconciliation."""
64
self.pb = ui.ui_factory.progress_bar()
65
self.repo = self.bzrdir.open_repository()
66
self.repo.lock_write()
67
try:
68
self.pb.note('Reconciling repository %s',
69
self.repo.bzrdir.root_transport.base)
70
self._reweave_inventory()
71
finally:
72
self.repo.unlock()
73
self.pb.note('Reconciliation complete.')
74
75
def _reweave_inventory(self):
76
"""Regenerate the inventory weave for the repository from scratch."""
77
self.pb.update('Reading inventory data.')
78
self.inventory = self.repo.get_inventory_weave()
79
self.repo.control_weaves.put_weave('inventory.backup',
80
self.inventory,
81
self.repo.get_transaction())
82
self.pb.note('Backup Inventory created.')
83
# asking for '' should never return a non-empty weave
84
new_inventory = self.repo.control_weaves.get_weave_or_empty('',
85
self.repo.get_transaction())
86
62
sorter = TopoSorter()
63
sorter.sort(graph)
64
return sorter._work_queue
65
66
67
class TopoSorter(object):
68
69
def sort(self, graph):
87
70
# the total set of revisions to process
88
self.pending = set([file_id for file_id in self.repo.revision_store])
89
71
self._rev_graph = dict(graph)
72
### if debugging:
73
# self._original_graph = dict(graph)
90
74
91
75
# the current line of history being processed.
92
76
# once we add in per inventory root ids this will involve a single
93
77
# pass within the revision knit at that point.
94
# these contain respectively the revision id and the not_ghost_parents.
78
# these contain respectively the revision id in the call stack
95
79
self._rev_stack = []
96
self._parent_stack = []
80
# a set of the revisions on the stack, for cycle detection
81
self._rev_set = set()
82
# and the not_ghost_parents.
97
83
self._pending_stack = []
98
84
# actual queue to reinsert. This is a single pass queue we can use to
99
85
# regenerate the inventory versioned file, and holds
102
88
# this is a set for fast lookups of queued revisions
103
89
self._work_set = set()
104
90
# total steps = 1 read per revision + one insert into the inventory
105
self.total = len(self.pending) * 2
106
self.count = 0
107
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
91
116
92
# now we do a depth first search of the revision graph until its empty.
117
93
# this gives us a topological order across all revisions in
120
96
# At each step in the call graph we need to know which parent we are on.
121
97
# we do this by having three variables for each stack frame:
122
98
# 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
99
# current queue of parents to descend into
126
100
# (self._pending_stack)
127
101
# putting all the parents into a pending list, left to
173
147
# we are now recursing down a call stack.
174
148
# its a width first search which
175
149
176
### Useful if fiddling with this code.
150
### Useful if fiddling with this code.
177
151
### # cross check
178
152
### for index in range(len(self._work_queue)):
179
### rev = self._work_queue[index][0]
153
### rev = self._work_queue[index]
180
154
### for left_index in range(index):
181
### if rev in self._work_queue[left_index][1]:
155
### if rev in self.original_graph[self._work_queue[left_index]]:
182
156
### print "revision in parent list of earlier revision"
183
157
### import pdb;pdb.set_trace()
184
158
159
def _stack_revision(self, rev_id, parents):
160
"""Add rev_id to the pending revision stack."""
161
# detect cycles:
162
if rev_id in self._rev_set:
163
# we only supply the revisions that led to the cycle. This isn't
164
# minimal though... but it is usually a subset of the entire graph
165
# and easier to debug.
166
raise errors.GraphCycleError(self._rev_set)
167
168
self._rev_stack.append(rev_id)
169
self._rev_set.add(rev_id)
170
self._pending_stack.append(list(parents))
171
172
def _unstack_revision(self):
173
"""A revision has been completed.
174
175
The revision is added to the work queue, and the data for
176
it popped from the call stack.
177
"""
178
rev_id = self._rev_stack.pop()
179
self._rev_set.remove(rev_id)
180
self._pending_stack.pop()
181
self._work_queue.append(rev_id)
182
self._work_set.add(rev_id)
183
# and remove it from the rev graph as its now complete
184
self._rev_graph.pop(rev_id)
185
186
187
class Reconciler(object):
188
"""Reconcilers are used to reconcile existing data.
189
190
Currently this is limited to a single repository, and consists
191
of an inventory reweave with revision cross-checks.
192
"""
193
194
def __init__(self, dir):
195
self.bzrdir = dir
196
197
def reconcile(self):
198
"""Actually perform the reconciliation."""
199
self.pb = ui.ui_factory.progress_bar()
200
self.repo = self.bzrdir.open_repository()
201
self.repo.lock_write()
202
try:
203
self.pb.note('Reconciling repository %s',
204
self.repo.bzrdir.root_transport.base)
205
self._reweave_inventory()
206
finally:
207
self.repo.unlock()
208
self.pb.note('Reconciliation complete.')
209
210
def _reweave_inventory(self):
211
"""Regenerate the inventory weave for the repository from scratch."""
212
self.pb.update('Reading inventory data.')
213
self.inventory = self.repo.get_inventory_weave()
214
self.repo.control_weaves.put_weave('inventory.backup',
215
self.inventory,
216
self.repo.get_transaction())
217
self.pb.note('Backup Inventory created.')
218
# asking for '' should never return a non-empty weave
219
new_inventory = self.repo.control_weaves.get_weave_or_empty('',
220
self.repo.get_transaction())
221
222
# the total set of revisions to process
223
self.pending = set([file_id for file_id in self.repo.revision_store])
224
225
# total steps = 1 read per revision + one insert into the inventory
226
self.total = len(self.pending) * 2
227
self.count = 0
228
229
# mapping from revision_id to parents
230
self._rev_graph = {}
231
# we need the revision id of each revision and its available parents list
232
for rev_id in self.pending:
233
# put a revision into the graph.
234
self._graph_revision(rev_id)
235
236
ordered_rev_ids = topological_sort(self._rev_graph.items())
237
self._work_queue = [(rev_id, self._rev_graph[rev_id]) for
238
rev_id in ordered_rev_ids]
239
185
240
# we have topological order of revisions and non ghost parents ready.
186
241
while self._work_queue:
187
242
rev_id, parents = self._work_queue.pop(0)
218
273
mutter('found ghost %s', parent)
219
274
self._rev_graph[rev_id] = parents
220
275
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
276
def _reweave_step(self, message):
242
277
"""Mark a single step of regeneration complete."""
243
278
self.pb.update(message, self.count, self.total)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1