/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to object_store.py

Cope with ghosts, cache inventories.

Show diffs side-by-side

added added

removed removed

Lines of Context:
object_store.py
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009 Jelmer Vernooij <jelmer@samba.org>
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
16
16
 
17
17
"""Map from Git sha's to Bazaar objects."""
18
18
 
19
 
import bzrlib
20
 
 
21
 
from bzrlib import ui
22
 
 
23
 
from bzrlib.errors import NoSuchRevision
24
 
 
25
 
from bzrlib.plugins.git.mapping import (
26
 
    inventory_to_tree_and_blobs,
27
 
    revision_to_commit,
28
 
    )
29
 
from bzrlib.plugins.git.shamap import GitShaMap
30
 
 
31
19
from dulwich.objects import (
32
20
    Blob,
33
 
    )
34
 
 
35
 
 
36
 
class GitObjectConverter(object):
 
21
    Tree,
 
22
    sha_to_hex,
 
23
    )
 
24
from dulwich.object_store import (
 
25
    BaseObjectStore,
 
26
    )
 
27
 
 
28
from bzrlib import (
 
29
    debug,
 
30
    errors,
 
31
    lru_cache,
 
32
    trace,
 
33
    ui,
 
34
    urlutils,
 
35
    )
 
36
from bzrlib.revision import (
 
37
    NULL_REVISION,
 
38
    )
 
39
 
 
40
from bzrlib.plugins.git.mapping import (
 
41
    default_mapping,
 
42
    directory_to_tree,
 
43
    extract_unusual_modes,
 
44
    mapping_registry,
 
45
    )
 
46
from bzrlib.plugins.git.shamap import (
 
47
    from_repository as idmap_from_repository,
 
48
    )
 
49
 
 
50
 
 
51
def get_object_store(repo, mapping=None):
 
52
    git = getattr(repo, "_git", None)
 
53
    if git is not None:
 
54
        return git.object_store
 
55
    return BazaarObjectStore(repo, mapping)
 
56
 
 
57
 
 
58
MAX_INV_CACHE_SIZE = 50 * 1024 * 1024
 
59
 
 
60
 
 
61
class LRUInventoryCache(object):
 
62
 
 
63
    def __init__(self, repository):
 
64
        def approx_inv_size(inv):
 
65
            # Very rough estimate, 1k per inventory entry
 
66
            return len(inv) * 1024
 
67
        self.repository = repository
 
68
        self._cache = lru_cache.LRUSizeCache(max_size=MAX_INV_CACHE_SIZE,
 
69
            after_cleanup_size=None, compute_size=approx_inv_size)
 
70
 
 
71
    def get_inventory(self, revid):            
 
72
        try:
 
73
            return self._cache[revid] 
 
74
        except KeyError:
 
75
            inv = self.repository.get_inventory(revid)
 
76
            self._cache.add(revid, inv)
 
77
            return inv
 
78
 
 
79
    def get_inventories(self, revids):
 
80
        invs = dict([(k, self._cache.get(k)) for k in revids]) 
 
81
        for inv in self.repository.iter_inventories([r for r, v in invs.iteritems() if v is None]):
 
82
            invs[inv.revision_id] = inv
 
83
            self._cache.add(inv.revision_id, inv)
 
84
        return [invs[r] for r in revids]
 
85
 
 
86
    def add(self, revid, inv):
 
87
        self._cache.add(revid, inv)
 
88
 
 
89
 
 
90
class BazaarObjectStore(BaseObjectStore):
 
91
    """A Git-style object store backed onto a Bazaar repository."""
37
92
 
38
93
    def __init__(self, repository, mapping=None):
39
94
        self.repository = repository
40
95
        if mapping is None:
41
 
            self.mapping = self.repository.get_mapping()
 
96
            self.mapping = default_mapping
42
97
        else:
43
98
            self.mapping = mapping
44
 
        self._idmap = GitShaMap(self.repository._transport)
 
99
        self._idmap = idmap_from_repository(repository)
 
100
        self.start_write_group = self._idmap.start_write_group
 
101
        self.abort_write_group = self._idmap.abort_write_group
 
102
        self.commit_write_group = self._idmap.commit_write_group
 
103
        self.parent_invs_cache = LRUInventoryCache(self.repository)
45
104
 
46
 
    def _update_sha_map(self):
47
 
        all_revids = self.repository.all_revision_ids()
 
105
    def _update_sha_map(self, stop_revision=None):
48
106
        graph = self.repository.get_graph()
49
 
        present_revids = set(self._idmap.revids())
50
 
        pb = ui.ui_factory.nested_progress_bar()
51
 
        try:
52
 
            for i, revid in enumerate(graph.iter_topo_order(all_revids)):
53
 
                if revid in present_revids:
54
 
                    continue
55
 
                pb.update("updating git map", i, len(all_revids))
56
 
                self._update_sha_map_revision(revid)
57
 
        finally:
58
 
            pb.finished()
 
107
        if stop_revision is None:
 
108
            heads = graph.heads(self.repository.all_revision_ids())
 
109
        else:
 
110
            heads = set([stop_revision])
 
111
        missing_revids = self._idmap.missing_revisions(heads)
 
112
        while heads:
 
113
            parents = graph.get_parent_map(heads)
 
114
            todo = set()
 
115
            for p in parents.values():
 
116
                todo.update([x for x in p if x not in missing_revids])
 
117
            heads = self._idmap.missing_revisions(todo)
 
118
            missing_revids.update(heads)
 
119
        if NULL_REVISION in missing_revids:
 
120
            missing_revids.remove(NULL_REVISION)
 
121
        missing_revids = self.repository.has_revisions(missing_revids)
 
122
        if not missing_revids:
 
123
            return
 
124
        self.start_write_group()
 
125
        try:
 
126
            pb = ui.ui_factory.nested_progress_bar()
 
127
            try:
 
128
                for i, revid in enumerate(graph.iter_topo_order(missing_revids)):
 
129
                    trace.mutter('processing %r', revid)
 
130
                    pb.update("updating git map", i, len(missing_revids))
 
131
                    self._update_sha_map_revision(revid)
 
132
            finally:
 
133
                pb.finished()
 
134
        except:
 
135
            self.abort_write_group()
 
136
            raise
 
137
        else:
 
138
            self.commit_write_group()
 
139
 
 
140
    def __iter__(self):
 
141
        self._update_sha_map()
 
142
        return iter(self._idmap.sha1s())
 
143
 
 
144
    def _revision_to_commit(self, rev, tree_sha):
 
145
        def parent_lookup(revid):
 
146
            try:
 
147
                return self._lookup_revision_sha1(revid)
 
148
            except errors.NoSuchRevision:
 
149
                trace.warning("Ignoring ghost parent %s", revid)
 
150
                return None
 
151
        return self.mapping.export_commit(rev, tree_sha, parent_lookup)
 
152
 
 
153
    def _inventory_to_objects(self, inv, parent_invs, parent_invshamaps,
 
154
            unusual_modes):
 
155
        """Iterate over the objects that were introduced in a revision.
 
156
 
 
157
        :param inv: Inventory to process
 
158
        :param parent_invs: parent inventory SHA maps
 
159
        :param parent_invshamaps: parent inventory SHA Map
 
160
        :param unusual_modes: Unusual file modes
 
161
        :return: Yields (path, object) entries
 
162
        """
 
163
        new_trees = {}
 
164
        shamap = {}
 
165
        for path, ie in inv.entries():
 
166
            if ie.kind in ("file", "symlink"):
 
167
                for (pinv, pinvshamap) in zip(parent_invs, parent_invshamaps):
 
168
                    try:
 
169
                        pie = pinv[ie.file_id]
 
170
                    except errors.NoSuchId:
 
171
                        pass
 
172
                    else:
 
173
                        if pie.kind == ie.kind and pie.revision == ie.revision:
 
174
                            shamap[ie.file_id] = pinvshamap.lookup_blob(ie.file_id, ie.revision)
 
175
                            break
 
176
                else:
 
177
                    obj = self._get_blob(ie.file_id, ie.revision, inv=inv)
 
178
                    yield path, obj
 
179
                    shamap[ie.file_id] = obj.id
 
180
                    new_trees[urlutils.dirname(path)] = ie.parent_id
 
181
            elif ie.kind == "directory":
 
182
                for pinv in parent_invs:
 
183
                    try:
 
184
                        pie = pinv[ie.file_id]
 
185
                    except errors.NoSuchId:
 
186
                        pass
 
187
                    else:
 
188
                        if (pie.kind == ie.kind and 
 
189
                            pie.children.keys() == ie.children.keys()):
 
190
                            try:
 
191
                                shamap[ie.file_id] = pinvshamap.lookup_tree(ie.file_id)
 
192
                            except NotImplementedError:
 
193
                                pass
 
194
                            else:
 
195
                                break
 
196
                else:
 
197
                    new_trees[path] = ie.file_id
 
198
            else:
 
199
                raise AssertionError(ie.kind)
 
200
        for fid in unusual_modes:
 
201
            new_trees[inv.id2path(fid)] = inv[fid].parent_id
 
202
        
 
203
        trees = {}
 
204
        while new_trees:
 
205
            items = new_trees.items()
 
206
            new_trees = {}
 
207
            for path, file_id in items:
 
208
                parent_id = inv[file_id].parent_id
 
209
                if parent_id is not None:
 
210
                    parent_path = urlutils.dirname(path)
 
211
                    new_trees[parent_path] = parent_id
 
212
                trees[path] = file_id
 
213
 
 
214
        for path in sorted(trees.keys(), reverse=True):
 
215
            ie = inv[trees[path]]
 
216
            assert ie.kind == "directory"
 
217
            obj = directory_to_tree(ie, 
 
218
                    lambda ie: shamap[ie.file_id], unusual_modes)
 
219
            if obj is not None:
 
220
                shamap[ie.file_id] = obj.id
 
221
                yield path, obj
 
222
 
 
223
    def _revision_to_objects(self, rev, inv):
 
224
        unusual_modes = extract_unusual_modes(rev)
 
225
        present_parents = self.repository.has_revisions(rev.parent_ids)
 
226
        parent_invs = self.parent_invs_cache.get_inventories([p for p in rev.parent_ids if p in present_parents])
 
227
        parent_invshamaps = [self._idmap.get_inventory_sha_map(r) for r in rev.parent_ids if r in present_parents]
 
228
        tree_sha = None
 
229
        for path, obj in self._inventory_to_objects(inv, parent_invs,
 
230
                parent_invshamaps, unusual_modes):
 
231
            yield path, obj
 
232
            if path == "":
 
233
                tree_sha = obj.id
 
234
        if tree_sha is None:
 
235
            if not rev.parent_ids:
 
236
                tree_sha = Tree().id
 
237
            else:
 
238
                tree_sha = parent_invshamaps[0][inv.root.file_id]
 
239
        commit_obj = self._revision_to_commit(rev, tree_sha)
 
240
        try:
 
241
            foreign_revid, mapping = mapping_registry.parse_revision_id(rev.revision_id)
 
242
        except errors.InvalidRevisionId:
 
243
            pass
 
244
        else:
 
245
            if foreign_revid != commit_obj.id:
 
246
                if not "fix-shamap" in debug.debug_flags:
 
247
                    raise AssertionError("recreated git commit had different sha1: expected %s, got %s" % (foreign_revid, commit_obj.id))
 
248
        yield None, commit_obj
59
249
 
60
250
    def _update_sha_map_revision(self, revid):
61
 
        inv = self.repository.get_inventory(revid)
62
 
        objects = inventory_to_tree_and_blobs(self.repository, self.mapping, revid)
63
 
        for sha, o, path in objects:
64
 
            if path == "":
65
 
                tree_sha = sha
66
 
            ie = inv[inv.path2id(path)]
67
 
            if ie.kind in ("file", "symlink"):
68
 
                self._idmap.add_entry(sha, "blob", (ie.file_id, ie.revision))
69
 
            else:
70
 
                self._idmap.add_entry(sha, "tree", (ie.file_id, ie.revision))
71
 
        rev = self.repository.get_revision(revid)
72
 
        commit_obj = revision_to_commit(rev, tree_sha, self._idmap._parent_lookup)
73
 
        self._idmap.add_entry(commit_obj.sha().hexdigest(), "commit", (revid, tree_sha))
74
 
 
75
 
    def _get_blob(self, fileid, revision):
76
 
        text = self.repository.texts.get_record_stream([(fileid, revision)], "unordered", True).next().get_bytes_as("fulltext")
77
 
        blob = Blob()
78
 
        blob._text = text
79
 
        return blob
80
 
 
81
 
    def _get_tree(self, fileid, revid):
82
 
        raise NotImplementedError(self._get_tree)
83
 
 
84
 
    def _get_commit(self, revid, tree_sha):
85
 
        rev = self.repository.get_revision(revid)
86
 
        return revision_to_commit(rev, tree_sha, self._idmap._parent_lookup)
87
 
 
88
 
    def __getitem__(self, sha):
89
 
        # See if sha is in map
90
 
        try:
91
 
            (type, type_data) = self._idmap.lookup_git_sha(sha)
92
 
        except KeyError:
93
 
            # if not, see if there are any unconverted revisions and add them 
 
251
        rev = self.repository.get_revision(revid)
 
252
        inv = self.parent_invs_cache.get_inventory(rev.revision_id)
 
253
        commit_obj = None
 
254
        entries = []
 
255
        for path, obj in self._revision_to_objects(rev, inv):
 
256
            if obj._type == "commit":
 
257
                commit_obj = obj
 
258
            elif obj._type in ("blob", "tree"):
 
259
                file_id = inv.path2id(path)
 
260
                ie = inv[file_id]
 
261
                if obj._type == "blob":
 
262
                    revision = ie.revision
 
263
                else:
 
264
                    revision = revid
 
265
                entries.append((file_id, obj._type, obj.id, revision))
 
266
            else:
 
267
                raise AssertionError
 
268
        self._idmap.add_entries(revid, rev.parent_ids, commit_obj.id, 
 
269
            commit_obj.tree, entries)
 
270
        return commit_obj.id
 
271
 
 
272
    def _check_expected_sha(self, expected_sha, object):
 
273
        if expected_sha is None:
 
274
            return
 
275
        if len(expected_sha) == 40:
 
276
            if expected_sha != object.sha().hexdigest():
 
277
                raise AssertionError("Invalid sha for %r: %s" % (object, expected_sha))
 
278
        elif len(expected_sha) == 20:
 
279
            if expected_sha != object.sha().digest():
 
280
                raise AssertionError("Invalid sha for %r: %s" % (object, sha_to_hex(expected_sha)))
 
281
        else:
 
282
            raise AssertionError("Unknown length %d for %r" % (len(expected_sha), expected_sha))
 
283
 
 
284
    def _get_ie_object(self, entry, inv, unusual_modes):
 
285
        if entry.kind == "directory":
 
286
            return self._get_tree(entry.file_id, inv.revision_id, inv,
 
287
                unusual_modes)
 
288
        elif entry.kind == "symlink":
 
289
            return self._get_blob_for_symlink(entry.symlink_target)
 
290
        elif entry.kind == "file":
 
291
            return self._get_blob_for_file(entry.file_id, entry.revision)
 
292
        else:
 
293
            raise AssertionError("unknown entry kind '%s'" % entry.kind)
 
294
 
 
295
    def _get_blob_for_symlink(self, symlink_target, expected_sha=None):
 
296
        """Return a Git Blob object for symlink.
 
297
 
 
298
        :param symlink_target: target of symlink.
 
299
        """
 
300
        if type(symlink_target) == unicode:
 
301
            symlink_target = symlink_target.encode('utf-8')
 
302
        blob = Blob()
 
303
        blob._text = symlink_target
 
304
        self._check_expected_sha(expected_sha, blob)
 
305
        return blob
 
306
 
 
307
    def _get_blob_for_file(self, fileid, revision, expected_sha=None):
 
308
        """Return a Git Blob object from a fileid and revision stored in bzr.
 
309
 
 
310
        :param fileid: File id of the text
 
311
        :param revision: Revision of the text
 
312
        """
 
313
        blob = Blob()
 
314
        chunks = self.repository.iter_files_bytes([(fileid, revision, None)]).next()[1]
 
315
        blob._text = "".join(chunks)
 
316
        self._check_expected_sha(expected_sha, blob)
 
317
        return blob
 
318
 
 
319
    def _get_blob(self, fileid, revision, expected_sha=None, inv=None):
 
320
        """Return a Git Blob object from a fileid and revision stored in bzr.
 
321
 
 
322
        :param fileid: File id of the text
 
323
        :param revision: Revision of the text
 
324
        """
 
325
        if inv is None:
 
326
            inv = self.parent_invs_cache.get_inventory(revision)
 
327
        entry = inv[fileid]
 
328
 
 
329
        if entry.kind == 'file':
 
330
            return self._get_blob_for_file(entry.file_id, entry.revision,
 
331
                                           expected_sha=expected_sha)
 
332
        elif entry.kind == 'symlink':
 
333
            return self._get_blob_for_symlink(entry.symlink_target,
 
334
                                              expected_sha=expected_sha)
 
335
        else:
 
336
            raise AssertionError
 
337
 
 
338
    def _get_tree(self, fileid, revid, inv, unusual_modes, expected_sha=None):
 
339
        """Return a Git Tree object from a file id and a revision stored in bzr.
 
340
 
 
341
        :param fileid: fileid in the tree.
 
342
        :param revision: Revision of the tree.
 
343
        """
 
344
        invshamap = self._idmap.get_inventory_sha_map(inv.revision_id)
 
345
        def get_ie_sha1(entry):
 
346
            if entry.kind == "directory":
 
347
                return invshamap.lookup_tree(entry.file_id)
 
348
            elif entry.kind in ("file", "symlink"):
 
349
                return invshamap.lookup_blob(entry.file_id, entry.revision)
 
350
            else:
 
351
                raise AssertionError("unknown entry kind '%s'" % entry.kind)
 
352
        tree = directory_to_tree(inv[fileid], get_ie_sha1, unusual_modes)
 
353
        self._check_expected_sha(expected_sha, tree)
 
354
        return tree
 
355
 
 
356
    def get_parents(self, sha):
 
357
        """Retrieve the parents of a Git commit by SHA1.
 
358
 
 
359
        :param sha: SHA1 of the commit
 
360
        :raises: KeyError, NotCommitError
 
361
        """
 
362
        return self[sha].parents
 
363
 
 
364
    def _lookup_revision_sha1(self, revid):
 
365
        """Return the SHA1 matching a Bazaar revision."""
 
366
        if revid == NULL_REVISION:
 
367
            return "0" * 40
 
368
        try:
 
369
            return self._idmap.lookup_commit(revid)
 
370
        except KeyError:
 
371
            try:
 
372
                return mapping_registry.parse_revision_id(revid)[0]
 
373
            except errors.InvalidRevisionId:
 
374
                self._update_sha_map(revid)
 
375
                return self._idmap.lookup_commit(revid)
 
376
 
 
377
    def get_raw(self, sha):
 
378
        """Get the raw representation of a Git object by SHA1.
 
379
 
 
380
        :param sha: SHA1 of the git object
 
381
        """
 
382
        obj = self[sha]
 
383
        return (obj.type, obj.as_raw_string())
 
384
 
 
385
    def __contains__(self, sha):
 
386
        # See if sha is in map
 
387
        try:
 
388
            (type, type_data) = self._lookup_git_sha(sha)
 
389
            if type == "commit":
 
390
                return self.repository.has_revision(type_data[0])
 
391
            elif type == "blob":
 
392
                return self.repository.texts.has_version(type_data)
 
393
            elif type == "tree":
 
394
                return self.repository.has_revision(type_data[1])
 
395
            else:
 
396
                raise AssertionError("Unknown object type '%s'" % type)
 
397
        except KeyError:
 
398
            return False
 
399
 
 
400
    def _lookup_git_sha(self, sha):
 
401
        # See if sha is in map
 
402
        try:
 
403
            return self._idmap.lookup_git_sha(sha)
 
404
        except KeyError:
 
405
            # if not, see if there are any unconverted revisions and add them
94
406
            # to the map, search for sha in map again
95
407
            self._update_sha_map()
96
 
            (type, type_data) = self._idmap.lookup_git_sha(sha)
 
408
            return self._idmap.lookup_git_sha(sha)
 
409
 
 
410
    def __getitem__(self, sha):
 
411
        (type, type_data) = self._lookup_git_sha(sha)
97
412
        # convert object to git object
98
413
        if type == "commit":
99
 
            return self._get_commit(*type_data)
 
414
            (revid, tree_sha) = type_data
 
415
            try:
 
416
                rev = self.repository.get_revision(revid)
 
417
            except errors.NoSuchRevision:
 
418
                trace.mutter('entry for %s %s in shamap: %r, but not found in repository', type, sha, type_data)
 
419
                raise KeyError(sha)
 
420
            commit = self._revision_to_commit(rev, tree_sha)
 
421
            self._check_expected_sha(sha, commit)
 
422
            return commit
100
423
        elif type == "blob":
101
 
            return self._get_blob(*type_data)
 
424
            (fileid, revision) = type_data
 
425
            return self._get_blob(fileid, revision, expected_sha=sha)
102
426
        elif type == "tree":
103
 
            return self._get_tree(*type_data)
 
427
            (fileid, revid) = type_data
 
428
            try:
 
429
                inv = self.parent_invs_cache.get_inventory(revid)
 
430
                rev = self.repository.get_revision(revid)
 
431
            except errors.NoSuchRevision:
 
432
                trace.mutter('entry for %s %s in shamap: %r, but not found in repository', type, sha, type_data)
 
433
                raise KeyError(sha)
 
434
            unusual_modes = extract_unusual_modes(rev)
 
435
            try:
 
436
                return self._get_tree(fileid, revid, inv,
 
437
                    unusual_modes, expected_sha=sha)
 
438
            except errors.NoSuchRevision:
 
439
                raise KeyError(sha)
104
440
        else:
105
441
            raise AssertionError("Unknown object type '%s'" % type)
 
442
 
 
443
    def generate_pack_contents(self, have, want):
 
444
        """Iterate over the contents of a pack file.
 
445
 
 
446
        :param have: List of SHA1s of objects that should not be sent
 
447
        :param want: List of SHA1s of objects that should be sent
 
448
        """
 
449
        processed = set()
 
450
        for commit_sha in have:
 
451
            try:
 
452
                (type, (revid, tree_sha)) = self._lookup_git_sha(commit_sha)
 
453
            except KeyError:
 
454
                pass
 
455
            else:
 
456
                assert type == "commit"
 
457
                processed.add(revid)
 
458
        pending = set()
 
459
        for commit_sha in want:
 
460
            if commit_sha in have:
 
461
                continue
 
462
            (type, (revid, tree_sha)) = self._lookup_git_sha(commit_sha)
 
463
            assert type == "commit"
 
464
            pending.add(revid)
 
465
        todo = set()
 
466
        while pending:
 
467
            processed.update(pending)
 
468
            next_map = self.repository.get_parent_map(pending)
 
469
            next_pending = set()
 
470
            for item in next_map.iteritems():
 
471
                todo.add(item[0])
 
472
                next_pending.update(p for p in item[1] if p not in processed)
 
473
            pending = next_pending
 
474
        if NULL_REVISION in todo:
 
475
            todo.remove(NULL_REVISION)
 
476
        trace.mutter('sending revisions %r', todo)
 
477
        ret = []
 
478
        pb = ui.ui_factory.nested_progress_bar()
 
479
        try:
 
480
            for i, revid in enumerate(todo):
 
481
                pb.update("generating git objects", i, len(todo))
 
482
                rev = self.repository.get_revision(revid)
 
483
                inv = self.parent_invs_cache.get_inventory(revid)
 
484
                for path, obj in self._revision_to_objects(rev, inv):
 
485
                    ret.append((obj, path))
 
486
        finally:
 
487
            pb.finished()
 
488
        return ret