~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/reconcile.py

  • Committer: Robert Collins
  • Date: 2006-05-24 08:14:45 UTC
  • mfrom: (1725.1.1 benchmark)
  • mto: (1725.2.6 commit)
  • mto: This revision was merged to the branch mainline in revision 1729.
  • Revision ID: robertc@robertcollins.net-20060524081445-c046b4406ffc8dfa
(rbc)Merge in benchmark --lsprof-timed lsprofiling feature. (Robert Collins, Martin Pool).

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
# (C) 2005, 2006 Canonical Limited.
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
"""Reconcilers are able to fix some potential data errors in a branch."""
 
18
 
 
19
 
 
20
__all__ = ['reconcile', 'Reconciler', 'RepoReconciler', 'KnitReconciler']
 
21
 
 
22
 
 
23
import bzrlib.branch
 
24
import bzrlib.errors as errors
 
25
import bzrlib.progress
 
26
from bzrlib.trace import mutter
 
27
from bzrlib.tsort import TopoSorter
 
28
import bzrlib.ui as ui
 
29
 
 
30
 
 
31
def reconcile(dir, other=None):
 
32
    """Reconcile the data in dir.
 
33
 
 
34
    Currently this is limited to a inventory 'reweave'.
 
35
 
 
36
    This is a convenience method, for using a Reconciler object.
 
37
 
 
38
    Directly using Reconciler is recommended for library users that
 
39
    desire fine grained control or analysis of the found issues.
 
40
 
 
41
    :param other: another bzrdir to reconcile against.
 
42
    """
 
43
    reconciler = Reconciler(dir, other=other)
 
44
    reconciler.reconcile()
 
45
 
 
46
 
 
47
class Reconciler(object):
 
48
    """Reconcilers are used to reconcile existing data."""
 
49
 
 
50
    def __init__(self, dir, other=None):
 
51
        """Create a Reconciler."""
 
52
        self.bzrdir = dir
 
53
 
 
54
    def reconcile(self):
 
55
        """Perform reconciliation.
 
56
        
 
57
        After reconciliation the following attributes document found issues:
 
58
        inconsistent_parents: The number of revisions in the repository whose
 
59
                              ancestry was being reported incorrectly.
 
60
        garbage_inventories: The number of inventory objects without revisions
 
61
                             that were garbage collected.
 
62
        """
 
63
        self.pb = ui.ui_factory.nested_progress_bar()
 
64
        try:
 
65
            self._reconcile()
 
66
        finally:
 
67
            self.pb.finished()
 
68
 
 
69
    def _reconcile(self):
 
70
        """Helper function for performing reconciliation."""
 
71
        self.repo = self.bzrdir.find_repository()
 
72
        self.pb.note('Reconciling repository %s',
 
73
                     self.repo.bzrdir.root_transport.base)
 
74
        repo_reconciler = self.repo.reconcile(thorough=True)
 
75
        self.inconsistent_parents = repo_reconciler.inconsistent_parents
 
76
        self.garbage_inventories = repo_reconciler.garbage_inventories
 
77
        self.pb.note('Reconciliation complete.')
 
78
 
 
79
 
 
80
class RepoReconciler(object):
 
81
    """Reconciler that reconciles a repository.
 
82
 
 
83
    Currently this consists of an inventory reweave with revision cross-checks.
 
84
    """
 
85
 
 
86
    def __init__(self, repo, other=None, thorough=False):
 
87
        """Construct a RepoReconciler.
 
88
 
 
89
        :param thorough: perform a thorough check which may take longer but
 
90
                         will correct non-data loss issues such as incorrect
 
91
                         cached data.
 
92
        """
 
93
        self.garbage_inventories = 0
 
94
        self.inconsistent_parents = 0
 
95
        self.repo = repo
 
96
        self.thorough = thorough
 
97
 
 
98
    def reconcile(self):
 
99
        """Perform reconciliation.
 
100
        
 
101
        After reconciliation the following attributes document found issues:
 
102
        inconsistent_parents: The number of revisions in the repository whose
 
103
                              ancestry was being reported incorrectly.
 
104
        garbage_inventories: The number of inventory objects without revisions
 
105
                             that were garbage collected.
 
106
        """
 
107
        self.repo.lock_write()
 
108
        try:
 
109
            self.pb = ui.ui_factory.nested_progress_bar()
 
110
            try:
 
111
                self._reconcile_steps()
 
112
            finally:
 
113
                self.pb.finished()
 
114
        finally:
 
115
            self.repo.unlock()
 
116
 
 
117
    def _reconcile_steps(self):
 
118
        """Perform the steps to reconcile this repository."""
 
119
        self._reweave_inventory()
 
120
 
 
121
    def _reweave_inventory(self):
 
122
        """Regenerate the inventory weave for the repository from scratch.
 
123
        
 
124
        This is a smart function: it will only do the reweave if doing it 
 
125
        will correct data issues. The self.thorough flag controls whether
 
126
        only data-loss causing issues (!self.thorough) or all issues
 
127
        (self.thorough) are treated as requiring the reweave.
 
128
        """
 
129
        # local because needing to know about WeaveFile is a wart we want to hide
 
130
        from bzrlib.weave import WeaveFile, Weave
 
131
        transaction = self.repo.get_transaction()
 
132
        self.pb.update('Reading inventory data.')
 
133
        self.inventory = self.repo.get_inventory_weave()
 
134
        # the total set of revisions to process
 
135
        self.pending = set([rev_id for rev_id in self.repo._revision_store.all_revision_ids(transaction)])
 
136
 
 
137
        # mapping from revision_id to parents
 
138
        self._rev_graph = {}
 
139
        # errors that we detect
 
140
        self.inconsistent_parents = 0
 
141
        # we need the revision id of each revision and its available parents list
 
142
        self._setup_steps(len(self.pending))
 
143
        for rev_id in self.pending:
 
144
            # put a revision into the graph.
 
145
            self._graph_revision(rev_id)
 
146
        self._check_garbage_inventories()
 
147
        # if there are no inconsistent_parents and 
 
148
        # (no garbage inventories or we are not doing a thorough check)
 
149
        if (not self.inconsistent_parents and 
 
150
            (not self.garbage_inventories or not self.thorough)):
 
151
            self.pb.note('Inventory ok.')
 
152
            return
 
153
        self.pb.update('Backing up inventory...', 0, 0)
 
154
        self.repo.control_weaves.copy(self.inventory, 'inventory.backup', self.repo.get_transaction())
 
155
        self.pb.note('Backup Inventory created.')
 
156
        # asking for '' should never return a non-empty weave
 
157
        new_inventory_vf = self.repo.control_weaves.get_empty('inventory.new',
 
158
            self.repo.get_transaction())
 
159
 
 
160
        # we have topological order of revisions and non ghost parents ready.
 
161
        self._setup_steps(len(self._rev_graph))
 
162
        for rev_id in TopoSorter(self._rev_graph.items()).iter_topo_order():
 
163
            parents = self._rev_graph[rev_id]
 
164
            # double check this really is in topological order.
 
165
            unavailable = [p for p in parents if p not in new_inventory_vf]
 
166
            assert len(unavailable) == 0
 
167
            # this entry has all the non ghost parents in the inventory
 
168
            # file already.
 
169
            self._reweave_step('adding inventories')
 
170
            if isinstance(new_inventory_vf, WeaveFile):
 
171
                # It's really a WeaveFile, but we call straight into the
 
172
                # Weave's add method to disable the auto-write-out behaviour.
 
173
                # This is done to avoid a revision_count * time-to-write additional overhead on 
 
174
                # reconcile.
 
175
                new_inventory_vf._check_write_ok()
 
176
                Weave._add_lines(new_inventory_vf, rev_id, parents, self.inventory.get_lines(rev_id),
 
177
                                 None)
 
178
            else:
 
179
                new_inventory_vf.add_lines(rev_id, parents, self.inventory.get_lines(rev_id))
 
180
 
 
181
        if isinstance(new_inventory_vf, WeaveFile):
 
182
            new_inventory_vf._save()
 
183
        # if this worked, the set of new_inventory_vf.names should equal
 
184
        # self.pending
 
185
        assert set(new_inventory_vf.versions()) == self.pending
 
186
        self.pb.update('Writing weave')
 
187
        self.repo.control_weaves.copy(new_inventory_vf, 'inventory', self.repo.get_transaction())
 
188
        self.repo.control_weaves.delete('inventory.new', self.repo.get_transaction())
 
189
        self.inventory = None
 
190
        self.pb.note('Inventory regenerated.')
 
191
 
 
192
    def _setup_steps(self, new_total):
 
193
        """Setup the markers we need to control the progress bar."""
 
194
        self.total = new_total
 
195
        self.count = 0
 
196
 
 
197
    def _graph_revision(self, rev_id):
 
198
        """Load a revision into the revision graph."""
 
199
        # pick a random revision
 
200
        # analyse revision id rev_id and put it in the stack.
 
201
        self._reweave_step('loading revisions')
 
202
        rev = self.repo.get_revision_reconcile(rev_id)
 
203
        assert rev.revision_id == rev_id
 
204
        parents = []
 
205
        for parent in rev.parent_ids:
 
206
            if self._parent_is_available(parent):
 
207
                parents.append(parent)
 
208
            else:
 
209
                mutter('found ghost %s', parent)
 
210
        self._rev_graph[rev_id] = parents   
 
211
        if self._parents_are_inconsistent(rev_id, parents):
 
212
            self.inconsistent_parents += 1
 
213
            mutter('Inconsistent inventory parents: id {%s} '
 
214
                   'inventory claims %r, '
 
215
                   'available parents are %r, '
 
216
                   'unavailable parents are %r',
 
217
                   rev_id, 
 
218
                   set(self.inventory.get_parents(rev_id)),
 
219
                   set(parents),
 
220
                   set(rev.parent_ids).difference(set(parents)))
 
221
 
 
222
    def _parents_are_inconsistent(self, rev_id, parents):
 
223
        """Return True if the parents list of rev_id does not match the weave.
 
224
 
 
225
        This detect inconsistences based on the self.thorough value:
 
226
        if thorough is on, the first parent value is checked as well as ghost
 
227
        differences.
 
228
        Otherwise only the ghost differences are evaluated.
 
229
        """
 
230
        weave_parents = self.inventory.get_parents(rev_id)
 
231
        weave_missing_old_ghosts = set(weave_parents) != set(parents)
 
232
        first_parent_is_wrong = (
 
233
            len(weave_parents) and len(parents) and
 
234
            parents[0] != weave_parents[0])
 
235
        if self.thorough:
 
236
            return weave_missing_old_ghosts or first_parent_is_wrong
 
237
        else:
 
238
            return weave_missing_old_ghosts
 
239
 
 
240
    def _check_garbage_inventories(self):
 
241
        """Check for garbage inventories which we cannot trust
 
242
 
 
243
        We cant trust them because their pre-requisite file data may not
 
244
        be present - all we know is that their revision was not installed.
 
245
        """
 
246
        if not self.thorough:
 
247
            return
 
248
        inventories = set(self.inventory.versions())
 
249
        revisions = set(self._rev_graph.keys())
 
250
        garbage = inventories.difference(revisions)
 
251
        self.garbage_inventories = len(garbage)
 
252
        for revision_id in garbage:
 
253
            mutter('Garbage inventory {%s} found.', revision_id)
 
254
 
 
255
    def _parent_is_available(self, parent):
 
256
        """True if parent is a fully available revision
 
257
 
 
258
        A fully available revision has a inventory and a revision object in the
 
259
        repository.
 
260
        """
 
261
        return (parent in self._rev_graph or 
 
262
                (parent in self.inventory and self.repo.has_revision(parent)))
 
263
 
 
264
    def _reweave_step(self, message):
 
265
        """Mark a single step of regeneration complete."""
 
266
        self.pb.update(message, self.count, self.total)
 
267
        self.count += 1
 
268
 
 
269
 
 
270
class KnitReconciler(RepoReconciler):
 
271
    """Reconciler that reconciles a knit format repository.
 
272
 
 
273
    This will detect garbage inventories and remove them.
 
274
 
 
275
    Inconsistent parentage is checked for in the revision weave.
 
276
    """
 
277
 
 
278
    def _reconcile_steps(self):
 
279
        """Perform the steps to reconcile this repository."""
 
280
        if self.thorough:
 
281
            self._load_indexes()
 
282
            # knits never suffer this
 
283
            self._gc_inventory()
 
284
 
 
285
    def _load_indexes(self):
 
286
        """Load indexes for the reconciliation."""
 
287
        self.transaction = self.repo.get_transaction()
 
288
        self.pb.update('Reading indexes.', 0, 2)
 
289
        self.inventory = self.repo.get_inventory_weave()
 
290
        self.pb.update('Reading indexes.', 1, 2)
 
291
        self.revisions = self.repo._revision_store.get_revision_file(self.transaction)
 
292
        self.pb.update('Reading indexes.', 2, 2)
 
293
 
 
294
    def _gc_inventory(self):
 
295
        """Remove inventories that are not referenced from the revision store."""
 
296
        self.pb.update('Checking unused inventories.', 0, 1)
 
297
        self._check_garbage_inventories()
 
298
        self.pb.update('Checking unused inventories.', 1, 3)
 
299
        if not self.garbage_inventories:
 
300
            self.pb.note('Inventory ok.')
 
301
            return
 
302
        self.pb.update('Backing up inventory...', 0, 0)
 
303
        self.repo.control_weaves.copy(self.inventory, 'inventory.backup', self.transaction)
 
304
        self.pb.note('Backup Inventory created.')
 
305
        # asking for '' should never return a non-empty weave
 
306
        new_inventory_vf = self.repo.control_weaves.get_empty('inventory.new',
 
307
            self.transaction)
 
308
 
 
309
        # we have topological order of revisions and non ghost parents ready.
 
310
        self._setup_steps(len(self.revisions))
 
311
        for rev_id in TopoSorter(self.revisions.get_graph().items()).iter_topo_order():
 
312
            parents = self.revisions.get_parents(rev_id)
 
313
            # double check this really is in topological order.
 
314
            unavailable = [p for p in parents if p not in new_inventory_vf]
 
315
            assert len(unavailable) == 0
 
316
            # this entry has all the non ghost parents in the inventory
 
317
            # file already.
 
318
            self._reweave_step('adding inventories')
 
319
            # ugly but needed, weaves are just way tooooo slow else.
 
320
            new_inventory_vf.add_lines(rev_id, parents, self.inventory.get_lines(rev_id))
 
321
 
 
322
        # if this worked, the set of new_inventory_vf.names should equal
 
323
        # self.pending
 
324
        assert set(new_inventory_vf.versions()) == set(self.revisions.versions())
 
325
        self.pb.update('Writing weave')
 
326
        self.repo.control_weaves.copy(new_inventory_vf, 'inventory', self.transaction)
 
327
        self.repo.control_weaves.delete('inventory.new', self.transaction)
 
328
        self.inventory = None
 
329
        self.pb.note('Inventory regenerated.')
 
330
 
 
331
    def _check_garbage_inventories(self):
 
332
        """Check for garbage inventories which we cannot trust
 
333
 
 
334
        We cant trust them because their pre-requisite file data may not
 
335
        be present - all we know is that their revision was not installed.
 
336
        """
 
337
        inventories = set(self.inventory.versions())
 
338
        revisions = set(self.revisions.versions())
 
339
        garbage = inventories.difference(revisions)
 
340
        self.garbage_inventories = len(garbage)
 
341
        for revision_id in garbage:
 
342
            mutter('Garbage inventory {%s} found.', revision_id)