~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Vincent Ladeuil
  • Date: 2011-08-20 09:28:27 UTC
  • mfrom: (5050.78.2 2.2)
  • mto: (5609.48.8 2.3)
  • mto: This revision was merged to the branch mainline in revision 6090.
  • Revision ID: v.ladeuil+lp@free.fr-20110820092827-9dyakfslp0r3hb1k
Merge 2.2 into 2.3 (including fix for #614713, #609187 and #812928)

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2006, 2007 Canonical Ltd
 
1
# Copyright (C) 2005-2011 Canonical Ltd
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
35
35
import re
36
36
import tarfile
37
37
 
38
 
import bzrlib
39
38
from bzrlib import (
40
39
    chk_map,
41
40
    errors,
42
41
    generate_ids,
43
42
    osutils,
44
 
    symbol_versioning,
45
43
    )
46
44
""")
47
45
 
49
47
    BzrCheckError,
50
48
    BzrError,
51
49
    )
52
 
from bzrlib.symbol_versioning import deprecated_in, deprecated_method
53
50
from bzrlib.trace import mutter
 
51
from bzrlib.static_tuple import StaticTuple
54
52
 
55
53
 
56
54
class InventoryEntry(object):
130
128
    RENAMED = 'renamed'
131
129
    MODIFIED_AND_RENAMED = 'modified and renamed'
132
130
 
133
 
    __slots__ = []
 
131
    __slots__ = ['file_id', 'revision', 'parent_id', 'name']
 
132
 
 
133
    # Attributes that all InventoryEntry instances are expected to have, but
 
134
    # that don't vary for all kinds of entry.  (e.g. symlink_target is only
 
135
    # relevant to InventoryLink, so there's no reason to make every
 
136
    # InventoryFile instance allocate space to hold a value for it.)
 
137
    # Attributes that only vary for files: executable, text_sha1, text_size,
 
138
    # text_id
 
139
    executable = False
 
140
    text_sha1 = None
 
141
    text_size = None
 
142
    text_id = None
 
143
    # Attributes that only vary for symlinks: symlink_target
 
144
    symlink_target = None
 
145
    # Attributes that only vary for tree-references: reference_revision
 
146
    reference_revision = None
 
147
 
134
148
 
135
149
    def detect_changes(self, old_entry):
136
150
        """Return a (text_modified, meta_modified) from this to old_entry.
175
189
                    candidates[ie.revision] = ie
176
190
        return candidates
177
191
 
178
 
    @deprecated_method(deprecated_in((1, 6, 0)))
179
 
    def get_tar_item(self, root, dp, now, tree):
180
 
        """Get a tarfile item and a file stream for its content."""
181
 
        item = tarfile.TarInfo(osutils.pathjoin(root, dp).encode('utf8'))
182
 
        # TODO: would be cool to actually set it to the timestamp of the
183
 
        # revision it was last changed
184
 
        item.mtime = now
185
 
        fileobj = self._put_in_tar(item, tree)
186
 
        return item, fileobj
187
 
 
188
192
    def has_text(self):
189
193
        """Return true if the object this entry represents has textual data.
190
194
 
196
200
        """
197
201
        return False
198
202
 
199
 
    def __init__(self, file_id, name, parent_id, text_id=None):
 
203
    def __init__(self, file_id, name, parent_id):
200
204
        """Create an InventoryEntry
201
205
 
202
206
        The filename must be a single component, relative to the
213
217
        """
214
218
        if '/' in name or '\\' in name:
215
219
            raise errors.InvalidEntryName(name=name)
216
 
        self.executable = False
 
220
        self.file_id = file_id
217
221
        self.revision = None
218
 
        self.text_sha1 = None
219
 
        self.text_size = None
220
 
        self.file_id = file_id
221
222
        self.name = name
222
 
        self.text_id = text_id
223
223
        self.parent_id = parent_id
224
 
        self.symlink_target = None
225
 
        self.reference_revision = None
226
224
 
227
225
    def kind_character(self):
228
226
        """Return a short kind indicator useful for appending to names."""
230
228
 
231
229
    known_kinds = ('file', 'directory', 'symlink')
232
230
 
233
 
    def _put_in_tar(self, item, tree):
234
 
        """populate item for stashing in a tar, and return the content stream.
235
 
 
236
 
        If no content is available, return None.
237
 
        """
238
 
        raise BzrError("don't know how to export {%s} of kind %r" %
239
 
                       (self.file_id, self.kind))
240
 
 
241
 
    @deprecated_method(deprecated_in((1, 6, 0)))
242
 
    def put_on_disk(self, dest, dp, tree):
243
 
        """Create a representation of self on disk in the prefix dest.
244
 
 
245
 
        This is a template method - implement _put_on_disk in subclasses.
246
 
        """
247
 
        fullpath = osutils.pathjoin(dest, dp)
248
 
        self._put_on_disk(fullpath, tree)
249
 
        # mutter("  export {%s} kind %s to %s", self.file_id,
250
 
        #         self.kind, fullpath)
251
 
 
252
 
    def _put_on_disk(self, fullpath, tree):
253
 
        """Put this entry onto disk at fullpath, from tree tree."""
254
 
        raise BzrError("don't know how to export {%s} of kind %r" % (self.file_id, self.kind))
255
 
 
256
231
    def sorted_children(self):
257
232
        return sorted(self.children.items())
258
233
 
260
235
    def versionable_kind(kind):
261
236
        return (kind in ('file', 'directory', 'symlink', 'tree-reference'))
262
237
 
263
 
    def check(self, checker, rev_id, inv, tree):
 
238
    def check(self, checker, rev_id, inv):
264
239
        """Check this inventory entry is intact.
265
240
 
266
241
        This is a template method, override _check for kind specific
272
247
        :param rev_id: Revision id from which this InventoryEntry was loaded.
273
248
             Not necessarily the last-changed revision for this file.
274
249
        :param inv: Inventory from which the entry was loaded.
275
 
        :param tree: RevisionTree for this entry.
276
250
        """
277
251
        if self.parent_id is not None:
278
252
            if not inv.has_id(self.parent_id):
279
253
                raise BzrCheckError('missing parent {%s} in inventory for revision {%s}'
280
254
                        % (self.parent_id, rev_id))
281
 
        self._check(checker, rev_id, tree)
 
255
        checker._add_entry_to_text_key_references(inv, self)
 
256
        self._check(checker, rev_id)
282
257
 
283
 
    def _check(self, checker, rev_id, tree):
 
258
    def _check(self, checker, rev_id):
284
259
        """Check this inventory entry for kind specific errors."""
285
 
        raise BzrCheckError('unknown entry kind %r in revision {%s}' %
286
 
                            (self.kind, rev_id))
 
260
        checker._report_items.append(
 
261
            'unknown entry kind %r in revision {%s}' % (self.kind, rev_id))
287
262
 
288
263
    def copy(self):
289
264
        """Clone this inventory entry."""
396
371
        pass
397
372
 
398
373
 
399
 
class RootEntry(InventoryEntry):
400
 
 
401
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
402
 
                 'text_id', 'parent_id', 'children', 'executable',
403
 
                 'revision', 'symlink_target', 'reference_revision']
404
 
 
405
 
    def _check(self, checker, rev_id, tree):
406
 
        """See InventoryEntry._check"""
407
 
 
408
 
    def __init__(self, file_id):
409
 
        self.file_id = file_id
410
 
        self.children = {}
411
 
        self.kind = 'directory'
412
 
        self.parent_id = None
413
 
        self.name = u''
414
 
        self.revision = None
415
 
        symbol_versioning.warn('RootEntry is deprecated as of bzr 0.10.'
416
 
                               '  Please use InventoryDirectory instead.',
417
 
                               DeprecationWarning, stacklevel=2)
418
 
 
419
 
    def __eq__(self, other):
420
 
        if not isinstance(other, RootEntry):
421
 
            return NotImplemented
422
 
 
423
 
        return (self.file_id == other.file_id) \
424
 
               and (self.children == other.children)
425
 
 
426
 
 
427
374
class InventoryDirectory(InventoryEntry):
428
375
    """A directory in an inventory."""
429
376
 
430
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
431
 
                 'text_id', 'parent_id', 'children', 'executable',
432
 
                 'revision', 'symlink_target', 'reference_revision']
433
 
 
434
 
    def _check(self, checker, rev_id, tree):
 
377
    __slots__ = ['children']
 
378
 
 
379
    kind = 'directory'
 
380
 
 
381
    def _check(self, checker, rev_id):
435
382
        """See InventoryEntry._check"""
436
 
        if self.text_sha1 is not None or self.text_size is not None or self.text_id is not None:
437
 
            raise BzrCheckError('directory {%s} has text in revision {%s}'
438
 
                                % (self.file_id, rev_id))
 
383
        # In non rich root repositories we do not expect a file graph for the
 
384
        # root.
 
385
        if self.name == '' and not checker.rich_roots:
 
386
            return
 
387
        # Directories are stored as an empty file, but the file should exist
 
388
        # to provide a per-fileid log. The hash of every directory content is
 
389
        # "da..." below (the sha1sum of '').
 
390
        checker.add_pending_item(rev_id,
 
391
            ('texts', self.file_id, self.revision), 'text',
 
392
             'da39a3ee5e6b4b0d3255bfef95601890afd80709')
439
393
 
440
394
    def copy(self):
441
395
        other = InventoryDirectory(self.file_id, self.name, self.parent_id)
447
401
    def __init__(self, file_id, name, parent_id):
448
402
        super(InventoryDirectory, self).__init__(file_id, name, parent_id)
449
403
        self.children = {}
450
 
        self.kind = 'directory'
451
404
 
452
405
    def kind_character(self):
453
406
        """See InventoryEntry.kind_character."""
454
407
        return '/'
455
408
 
456
 
    def _put_in_tar(self, item, tree):
457
 
        """See InventoryEntry._put_in_tar."""
458
 
        item.type = tarfile.DIRTYPE
459
 
        fileobj = None
460
 
        item.name += '/'
461
 
        item.size = 0
462
 
        item.mode = 0755
463
 
        return fileobj
464
 
 
465
 
    def _put_on_disk(self, fullpath, tree):
466
 
        """See InventoryEntry._put_on_disk."""
467
 
        os.mkdir(fullpath)
468
 
 
469
409
 
470
410
class InventoryFile(InventoryEntry):
471
411
    """A file in an inventory."""
472
412
 
473
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
474
 
                 'text_id', 'parent_id', 'children', 'executable',
475
 
                 'revision', 'symlink_target', 'reference_revision']
476
 
 
477
 
    def _check(self, checker, tree_revision_id, tree):
 
413
    __slots__ = ['text_sha1', 'text_size', 'text_id', 'executable']
 
414
 
 
415
    kind = 'file'
 
416
 
 
417
    def __init__(self, file_id, name, parent_id):
 
418
        super(InventoryFile, self).__init__(file_id, name, parent_id)
 
419
        self.text_sha1 = None
 
420
        self.text_size = None
 
421
        self.text_id = None
 
422
        self.executable = False
 
423
 
 
424
    def _check(self, checker, tree_revision_id):
478
425
        """See InventoryEntry._check"""
479
 
        key = (self.file_id, self.revision)
480
 
        if key in checker.checked_texts:
481
 
            prev_sha = checker.checked_texts[key]
482
 
            if prev_sha != self.text_sha1:
483
 
                raise BzrCheckError(
484
 
                    'mismatched sha1 on {%s} in {%s} (%s != %s) %r' %
485
 
                    (self.file_id, tree_revision_id, prev_sha, self.text_sha1,
486
 
                     t))
487
 
            else:
488
 
                checker.repeated_text_cnt += 1
489
 
                return
490
 
 
491
 
        checker.checked_text_cnt += 1
492
 
        # We can't check the length, because Weave doesn't store that
493
 
        # information, and the whole point of looking at the weave's
494
 
        # sha1sum is that we don't have to extract the text.
495
 
        if (self.text_sha1 != tree._repository.texts.get_sha1s([key])[key]):
496
 
            raise BzrCheckError('text {%s} version {%s} wrong sha1' % key)
497
 
        checker.checked_texts[key] = self.text_sha1
 
426
        # TODO: check size too.
 
427
        checker.add_pending_item(tree_revision_id,
 
428
            ('texts', self.file_id, self.revision), 'text',
 
429
             self.text_sha1)
 
430
        if self.text_size is None:
 
431
            checker._report_items.append(
 
432
                'fileid {%s} in {%s} has None for text_size' % (self.file_id,
 
433
                tree_revision_id))
498
434
 
499
435
    def copy(self):
500
436
        other = InventoryFile(self.file_id, self.name, self.parent_id)
532
468
        """See InventoryEntry.has_text."""
533
469
        return True
534
470
 
535
 
    def __init__(self, file_id, name, parent_id):
536
 
        super(InventoryFile, self).__init__(file_id, name, parent_id)
537
 
        self.kind = 'file'
538
 
 
539
471
    def kind_character(self):
540
472
        """See InventoryEntry.kind_character."""
541
473
        return ''
542
474
 
543
 
    def _put_in_tar(self, item, tree):
544
 
        """See InventoryEntry._put_in_tar."""
545
 
        item.type = tarfile.REGTYPE
546
 
        fileobj = tree.get_file(self.file_id)
547
 
        item.size = self.text_size
548
 
        if tree.is_executable(self.file_id):
549
 
            item.mode = 0755
550
 
        else:
551
 
            item.mode = 0644
552
 
        return fileobj
553
 
 
554
 
    def _put_on_disk(self, fullpath, tree):
555
 
        """See InventoryEntry._put_on_disk."""
556
 
        osutils.pumpfile(tree.get_file(self.file_id), file(fullpath, 'wb'))
557
 
        if tree.is_executable(self.file_id):
558
 
            os.chmod(fullpath, 0755)
559
 
 
560
475
    def _read_tree_state(self, path, work_tree):
561
476
        """See InventoryEntry._read_tree_state."""
562
477
        self.text_sha1 = work_tree.get_file_sha1(self.file_id, path=path)
594
509
class InventoryLink(InventoryEntry):
595
510
    """A file in an inventory."""
596
511
 
597
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
598
 
                 'text_id', 'parent_id', 'children', 'executable',
599
 
                 'revision', 'symlink_target', 'reference_revision']
600
 
 
601
 
    def _check(self, checker, rev_id, tree):
 
512
    __slots__ = ['symlink_target']
 
513
 
 
514
    kind = 'symlink'
 
515
 
 
516
    def __init__(self, file_id, name, parent_id):
 
517
        super(InventoryLink, self).__init__(file_id, name, parent_id)
 
518
        self.symlink_target = None
 
519
 
 
520
    def _check(self, checker, tree_revision_id):
602
521
        """See InventoryEntry._check"""
603
 
        if self.text_sha1 is not None or self.text_size is not None or self.text_id is not None:
604
 
            raise BzrCheckError('symlink {%s} has text in revision {%s}'
605
 
                    % (self.file_id, rev_id))
606
522
        if self.symlink_target is None:
607
 
            raise BzrCheckError('symlink {%s} has no target in revision {%s}'
608
 
                    % (self.file_id, rev_id))
 
523
            checker._report_items.append(
 
524
                'symlink {%s} has no target in revision {%s}'
 
525
                    % (self.file_id, tree_revision_id))
 
526
        # Symlinks are stored as ''
 
527
        checker.add_pending_item(tree_revision_id,
 
528
            ('texts', self.file_id, self.revision), 'text',
 
529
             'da39a3ee5e6b4b0d3255bfef95601890afd80709')
609
530
 
610
531
    def copy(self):
611
532
        other = InventoryLink(self.file_id, self.name, self.parent_id)
641
562
        differ = DiffSymlink(old_tree, new_tree, output_to)
642
563
        return differ.diff_symlink(old_target, new_target)
643
564
 
644
 
    def __init__(self, file_id, name, parent_id):
645
 
        super(InventoryLink, self).__init__(file_id, name, parent_id)
646
 
        self.kind = 'symlink'
647
 
 
648
565
    def kind_character(self):
649
566
        """See InventoryEntry.kind_character."""
650
567
        return ''
651
568
 
652
 
    def _put_in_tar(self, item, tree):
653
 
        """See InventoryEntry._put_in_tar."""
654
 
        item.type = tarfile.SYMTYPE
655
 
        fileobj = None
656
 
        item.size = 0
657
 
        item.mode = 0755
658
 
        item.linkname = self.symlink_target
659
 
        return fileobj
660
 
 
661
 
    def _put_on_disk(self, fullpath, tree):
662
 
        """See InventoryEntry._put_on_disk."""
663
 
        try:
664
 
            os.symlink(self.symlink_target, fullpath)
665
 
        except OSError,e:
666
 
            raise BzrError("Failed to create symlink %r -> %r, error: %s" % (fullpath, self.symlink_target, e))
667
 
 
668
569
    def _read_tree_state(self, path, work_tree):
669
570
        """See InventoryEntry._read_tree_state."""
670
571
        self.symlink_target = work_tree.get_symlink_target(self.file_id)
682
583
 
683
584
class TreeReference(InventoryEntry):
684
585
 
 
586
    __slots__ = ['reference_revision']
 
587
 
685
588
    kind = 'tree-reference'
686
589
 
687
590
    def __init__(self, file_id, name, parent_id, revision=None,
743
646
        """
744
647
        return self.has_id(file_id)
745
648
 
 
649
    def has_filename(self, filename):
 
650
        return bool(self.path2id(filename))
 
651
 
746
652
    def id2path(self, file_id):
747
653
        """Return as a string the path to file_id.
748
654
 
751
657
        >>> e = i.add(InventoryFile('foo-id', 'foo.c', parent_id='src-id'))
752
658
        >>> print i.id2path('foo-id')
753
659
        src/foo.c
 
660
 
 
661
        :raises NoSuchId: If file_id is not present in the inventory.
754
662
        """
755
663
        # get all names, skipping root
756
664
        return '/'.join(reversed(
810
718
                # if we finished all children, pop it off the stack
811
719
                stack.pop()
812
720
 
 
721
    def _preload_cache(self):
 
722
        """Populate any caches, we are about to access all items.
 
723
        
 
724
        The default implementation does nothing, because CommonInventory doesn't
 
725
        have a cache.
 
726
        """
 
727
        pass
 
728
    
813
729
    def iter_entries_by_dir(self, from_dir=None, specific_file_ids=None,
814
730
        yield_parents=False):
815
731
        """Iterate over the entries in a directory first order.
828
744
            specific_file_ids = set(specific_file_ids)
829
745
        # TODO? Perhaps this should return the from_dir so that the root is
830
746
        # yielded? or maybe an option?
 
747
        if from_dir is None and specific_file_ids is None:
 
748
            # They are iterating from the root, and have not specified any
 
749
            # specific entries to look at. All current callers fully consume the
 
750
            # iterator, so we can safely assume we are accessing all entries
 
751
            self._preload_cache()
831
752
        if from_dir is None:
832
753
            if self.root is None:
833
754
                return
928
849
                if ie.kind == 'directory':
929
850
                    descend(ie, child_path)
930
851
 
931
 
        descend(self.root, u'')
 
852
        if self.root is not None:
 
853
            descend(self.root, u'')
932
854
        return accum
933
855
 
934
856
    def directories(self):
947
869
        descend(self.root, u'')
948
870
        return accum
949
871
 
950
 
    def path2id(self, name):
 
872
    def path2id(self, relpath):
951
873
        """Walk down through directories to return entry of last component.
952
874
 
953
 
        names may be either a list of path components, or a single
954
 
        string, in which case it is automatically split.
 
875
        :param relpath: may be either a list of path components, or a single
 
876
            string, in which case it is automatically split.
955
877
 
956
878
        This returns the entry of the last component in the path,
957
879
        which may be either a file or a directory.
958
880
 
959
881
        Returns None IFF the path is not found.
960
882
        """
961
 
        if isinstance(name, basestring):
962
 
            name = osutils.splitpath(name)
963
 
 
964
 
        # mutter("lookup path %r" % name)
 
883
        if isinstance(relpath, basestring):
 
884
            names = osutils.splitpath(relpath)
 
885
        else:
 
886
            names = relpath
965
887
 
966
888
        try:
967
889
            parent = self.root
970
892
            return None
971
893
        if parent is None:
972
894
            return None
973
 
        for f in name:
 
895
        for f in names:
974
896
            try:
975
897
                children = getattr(parent, 'children', None)
976
898
                if children is None:
1186
1108
            raise errors.InconsistentDelta("<deleted>", parent_id,
1187
1109
                "The file id was deleted but its children were not deleted.")
1188
1110
 
 
1111
    def create_by_apply_delta(self, inventory_delta, new_revision_id,
 
1112
                              propagate_caches=False):
 
1113
        """See CHKInventory.create_by_apply_delta()"""
 
1114
        new_inv = self.copy()
 
1115
        new_inv.apply_delta(inventory_delta)
 
1116
        new_inv.revision_id = new_revision_id
 
1117
        return new_inv
 
1118
 
1189
1119
    def _set_root(self, ie):
1190
1120
        self.root = ie
1191
1121
        self._byid = {self.root.file_id: self.root}
1262
1192
    def add(self, entry):
1263
1193
        """Add entry to inventory.
1264
1194
 
1265
 
        To add  a file to a branch ready to be committed, use Branch.add,
1266
 
        which calls this.
1267
 
 
1268
1195
        :return: entry
1269
1196
        """
1270
1197
        if entry.file_id in self._byid:
1363
1290
            yield ie
1364
1291
            file_id = ie.parent_id
1365
1292
 
1366
 
    def has_filename(self, filename):
1367
 
        return bool(self.path2id(filename))
1368
 
 
1369
1293
    def has_id(self, file_id):
1370
1294
        return (file_id in self._byid)
1371
1295
 
1479
1403
    def __init__(self, search_key_name):
1480
1404
        CommonInventory.__init__(self)
1481
1405
        self._fileid_to_entry_cache = {}
 
1406
        self._fully_cached = False
1482
1407
        self._path_to_fileid_cache = {}
1483
1408
        self._search_key_name = search_key_name
1484
1409
        self.root_id = None
1538
1463
        else:
1539
1464
            raise ValueError("unknown kind %r" % entry.kind)
1540
1465
 
 
1466
    def _expand_fileids_to_parents_and_children(self, file_ids):
 
1467
        """Give a more wholistic view starting with the given file_ids.
 
1468
 
 
1469
        For any file_id which maps to a directory, we will include all children
 
1470
        of that directory. We will also include all directories which are
 
1471
        parents of the given file_ids, but we will not include their children.
 
1472
 
 
1473
        eg:
 
1474
          /     # TREE_ROOT
 
1475
          foo/  # foo-id
 
1476
            baz # baz-id
 
1477
            frob/ # frob-id
 
1478
              fringle # fringle-id
 
1479
          bar/  # bar-id
 
1480
            bing # bing-id
 
1481
 
 
1482
        if given [foo-id] we will include
 
1483
            TREE_ROOT as interesting parents
 
1484
        and 
 
1485
            foo-id, baz-id, frob-id, fringle-id
 
1486
        As interesting ids.
 
1487
        """
 
1488
        interesting = set()
 
1489
        # TODO: Pre-pass over the list of fileids to see if anything is already
 
1490
        #       deserialized in self._fileid_to_entry_cache
 
1491
 
 
1492
        directories_to_expand = set()
 
1493
        children_of_parent_id = {}
 
1494
        # It is okay if some of the fileids are missing
 
1495
        for entry in self._getitems(file_ids):
 
1496
            if entry.kind == 'directory':
 
1497
                directories_to_expand.add(entry.file_id)
 
1498
            interesting.add(entry.parent_id)
 
1499
            children_of_parent_id.setdefault(entry.parent_id, []
 
1500
                                             ).append(entry.file_id)
 
1501
 
 
1502
        # Now, interesting has all of the direct parents, but not the
 
1503
        # parents of those parents. It also may have some duplicates with
 
1504
        # specific_fileids
 
1505
        remaining_parents = interesting.difference(file_ids)
 
1506
        # When we hit the TREE_ROOT, we'll get an interesting parent of None,
 
1507
        # but we don't actually want to recurse into that
 
1508
        interesting.add(None) # this will auto-filter it in the loop
 
1509
        remaining_parents.discard(None) 
 
1510
        while remaining_parents:
 
1511
            next_parents = set()
 
1512
            for entry in self._getitems(remaining_parents):
 
1513
                next_parents.add(entry.parent_id)
 
1514
                children_of_parent_id.setdefault(entry.parent_id, []
 
1515
                                                 ).append(entry.file_id)
 
1516
            # Remove any search tips we've already processed
 
1517
            remaining_parents = next_parents.difference(interesting)
 
1518
            interesting.update(remaining_parents)
 
1519
            # We should probably also .difference(directories_to_expand)
 
1520
        interesting.update(file_ids)
 
1521
        interesting.discard(None)
 
1522
        while directories_to_expand:
 
1523
            # Expand directories by looking in the
 
1524
            # parent_id_basename_to_file_id map
 
1525
            keys = [StaticTuple(f,).intern() for f in directories_to_expand]
 
1526
            directories_to_expand = set()
 
1527
            items = self.parent_id_basename_to_file_id.iteritems(keys)
 
1528
            next_file_ids = set([item[1] for item in items])
 
1529
            next_file_ids = next_file_ids.difference(interesting)
 
1530
            interesting.update(next_file_ids)
 
1531
            for entry in self._getitems(next_file_ids):
 
1532
                if entry.kind == 'directory':
 
1533
                    directories_to_expand.add(entry.file_id)
 
1534
                children_of_parent_id.setdefault(entry.parent_id, []
 
1535
                                                 ).append(entry.file_id)
 
1536
        return interesting, children_of_parent_id
 
1537
 
 
1538
    def filter(self, specific_fileids):
 
1539
        """Get an inventory view filtered against a set of file-ids.
 
1540
 
 
1541
        Children of directories and parents are included.
 
1542
 
 
1543
        The result may or may not reference the underlying inventory
 
1544
        so it should be treated as immutable.
 
1545
        """
 
1546
        (interesting,
 
1547
         parent_to_children) = self._expand_fileids_to_parents_and_children(
 
1548
                                specific_fileids)
 
1549
        # There is some overlap here, but we assume that all interesting items
 
1550
        # are in the _fileid_to_entry_cache because we had to read them to
 
1551
        # determine if they were a dir we wanted to recurse, or just a file
 
1552
        # This should give us all the entries we'll want to add, so start
 
1553
        # adding
 
1554
        other = Inventory(self.root_id)
 
1555
        other.root.revision = self.root.revision
 
1556
        other.revision_id = self.revision_id
 
1557
        if not interesting or not parent_to_children:
 
1558
            # empty filter, or filtering entrys that don't exist
 
1559
            # (if even 1 existed, then we would have populated
 
1560
            # parent_to_children with at least the tree root.)
 
1561
            return other
 
1562
        cache = self._fileid_to_entry_cache
 
1563
        remaining_children = collections.deque(parent_to_children[self.root_id])
 
1564
        while remaining_children:
 
1565
            file_id = remaining_children.popleft()
 
1566
            ie = cache[file_id]
 
1567
            if ie.kind == 'directory':
 
1568
                ie = ie.copy() # We create a copy to depopulate the .children attribute
 
1569
            # TODO: depending on the uses of 'other' we should probably alwyas
 
1570
            #       '.copy()' to prevent someone from mutating other and
 
1571
            #       invaliding our internal cache
 
1572
            other.add(ie)
 
1573
            if file_id in parent_to_children:
 
1574
                remaining_children.extend(parent_to_children[file_id])
 
1575
        return other
 
1576
 
1541
1577
    @staticmethod
1542
1578
    def _bytes_to_utf8name_key(bytes):
1543
1579
        """Get the file_id, revision_id key out of bytes."""
1545
1581
        # to filter out empty names because of non rich-root...
1546
1582
        sections = bytes.split('\n')
1547
1583
        kind, file_id = sections[0].split(': ')
1548
 
        return (sections[2], file_id, sections[3])
 
1584
        return (sections[2], intern(file_id), intern(sections[3]))
1549
1585
 
1550
1586
    def _bytes_to_entry(self, bytes):
1551
1587
        """Deserialise a serialised entry."""
1573
1609
            result.reference_revision = sections[4]
1574
1610
        else:
1575
1611
            raise ValueError("Not a serialised entry %r" % bytes)
1576
 
        result.revision = sections[3]
 
1612
        result.file_id = intern(result.file_id)
 
1613
        result.revision = intern(sections[3])
1577
1614
        if result.parent_id == '':
1578
1615
            result.parent_id = None
1579
1616
        self._fileid_to_entry_cache[result.file_id] = result
1677
1714
                        pass
1678
1715
                deletes.add(file_id)
1679
1716
            else:
1680
 
                new_key = (file_id,)
 
1717
                new_key = StaticTuple(file_id,)
1681
1718
                new_value = result._entry_to_bytes(entry)
1682
1719
                # Update caches. It's worth doing this whether
1683
1720
                # we're propagating the old caches or not.
1686
1723
            if old_path is None:
1687
1724
                old_key = None
1688
1725
            else:
1689
 
                old_key = (file_id,)
 
1726
                old_key = StaticTuple(file_id,)
1690
1727
                if self.id2path(file_id) != old_path:
1691
1728
                    raise errors.InconsistentDelta(old_path, file_id,
1692
1729
                        "Entry was at wrong other path %r." %
1693
1730
                        self.id2path(file_id))
1694
1731
                altered.add(file_id)
1695
 
            id_to_entry_delta.append((old_key, new_key, new_value))
 
1732
            id_to_entry_delta.append(StaticTuple(old_key, new_key, new_value))
1696
1733
            if result.parent_id_basename_to_file_id is not None:
1697
1734
                # parent_id, basename changes
1698
1735
                if old_path is None:
1785
1822
                raise errors.BzrError('Duplicate key in inventory: %r\n%r'
1786
1823
                                      % (key, bytes))
1787
1824
            info[key] = value
1788
 
        revision_id = info['revision_id']
1789
 
        root_id = info['root_id']
1790
 
        search_key_name = info.get('search_key_name', 'plain')
1791
 
        parent_id_basename_to_file_id = info.get(
1792
 
            'parent_id_basename_to_file_id', None)
 
1825
        revision_id = intern(info['revision_id'])
 
1826
        root_id = intern(info['root_id'])
 
1827
        search_key_name = intern(info.get('search_key_name', 'plain'))
 
1828
        parent_id_basename_to_file_id = intern(info.get(
 
1829
            'parent_id_basename_to_file_id', None))
 
1830
        if not parent_id_basename_to_file_id.startswith('sha1:'):
 
1831
            raise ValueError('parent_id_basename_to_file_id should be a sha1'
 
1832
                             ' key not %r' % (parent_id_basename_to_file_id,))
1793
1833
        id_to_entry = info['id_to_entry']
 
1834
        if not id_to_entry.startswith('sha1:'):
 
1835
            raise ValueError('id_to_entry should be a sha1'
 
1836
                             ' key not %r' % (id_to_entry,))
1794
1837
 
1795
1838
        result = CHKInventory(search_key_name)
1796
1839
        result.revision_id = revision_id
1799
1842
                            result._search_key_name)
1800
1843
        if parent_id_basename_to_file_id is not None:
1801
1844
            result.parent_id_basename_to_file_id = chk_map.CHKMap(
1802
 
                chk_store, (parent_id_basename_to_file_id,),
 
1845
                chk_store, StaticTuple(parent_id_basename_to_file_id,),
1803
1846
                search_key_func=search_key_func)
1804
1847
        else:
1805
1848
            result.parent_id_basename_to_file_id = None
1806
1849
 
1807
 
        result.id_to_entry = chk_map.CHKMap(chk_store, (id_to_entry,),
 
1850
        result.id_to_entry = chk_map.CHKMap(chk_store,
 
1851
                                            StaticTuple(id_to_entry,),
1808
1852
                                            search_key_func=search_key_func)
1809
1853
        if (result.revision_id,) != expected_revision_id:
1810
1854
            raise ValueError("Mismatched revision id and expected: %r, %r" %
1832
1876
        id_to_entry_dict = {}
1833
1877
        parent_id_basename_dict = {}
1834
1878
        for path, entry in inventory.iter_entries():
1835
 
            id_to_entry_dict[(entry.file_id,)] = entry_to_bytes(entry)
 
1879
            key = StaticTuple(entry.file_id,).intern()
 
1880
            id_to_entry_dict[key] = entry_to_bytes(entry)
1836
1881
            p_id_key = parent_id_basename_key(entry)
1837
1882
            parent_id_basename_dict[p_id_key] = entry.file_id
1838
1883
 
1861
1906
            parent_id = entry.parent_id
1862
1907
        else:
1863
1908
            parent_id = ''
1864
 
        return parent_id, entry.name.encode('utf8')
 
1909
        return StaticTuple(parent_id, entry.name.encode('utf8')).intern()
1865
1910
 
1866
1911
    def __getitem__(self, file_id):
1867
1912
        """map a single file_id -> InventoryEntry."""
1872
1917
            return result
1873
1918
        try:
1874
1919
            return self._bytes_to_entry(
1875
 
                self.id_to_entry.iteritems([(file_id,)]).next()[1])
 
1920
                self.id_to_entry.iteritems([StaticTuple(file_id,)]).next()[1])
1876
1921
        except StopIteration:
1877
1922
            # really we're passing an inventory, not a tree...
1878
1923
            raise errors.NoSuchId(self, file_id)
1879
1924
 
 
1925
    def _getitems(self, file_ids):
 
1926
        """Similar to __getitem__, but lets you query for multiple.
 
1927
        
 
1928
        The returned order is undefined. And currently if an item doesn't
 
1929
        exist, it isn't included in the output.
 
1930
        """
 
1931
        result = []
 
1932
        remaining = []
 
1933
        for file_id in file_ids:
 
1934
            entry = self._fileid_to_entry_cache.get(file_id, None)
 
1935
            if entry is None:
 
1936
                remaining.append(file_id)
 
1937
            else:
 
1938
                result.append(entry)
 
1939
        file_keys = [StaticTuple(f,).intern() for f in remaining]
 
1940
        for file_key, value in self.id_to_entry.iteritems(file_keys):
 
1941
            entry = self._bytes_to_entry(value)
 
1942
            result.append(entry)
 
1943
            self._fileid_to_entry_cache[entry.file_id] = entry
 
1944
        return result
 
1945
 
1880
1946
    def has_id(self, file_id):
1881
1947
        # Perhaps have an explicit 'contains' method on CHKMap ?
1882
1948
        if self._fileid_to_entry_cache.get(file_id, None) is not None:
1883
1949
            return True
1884
 
        return len(list(self.id_to_entry.iteritems([(file_id,)]))) == 1
 
1950
        return len(list(
 
1951
            self.id_to_entry.iteritems([StaticTuple(file_id,)]))) == 1
1885
1952
 
1886
1953
    def is_root(self, file_id):
1887
1954
        return file_id == self.root_id
1903
1970
 
1904
1971
    def iter_just_entries(self):
1905
1972
        """Iterate over all entries.
1906
 
        
 
1973
 
1907
1974
        Unlike iter_entries(), just the entries are returned (not (path, ie))
1908
1975
        and the order of entries is undefined.
1909
1976
 
1917
1984
                self._fileid_to_entry_cache[file_id] = ie
1918
1985
            yield ie
1919
1986
 
 
1987
    def _preload_cache(self):
 
1988
        """Make sure all file-ids are in _fileid_to_entry_cache"""
 
1989
        if self._fully_cached:
 
1990
            return # No need to do it again
 
1991
        # The optimal sort order is to use iteritems() directly
 
1992
        cache = self._fileid_to_entry_cache
 
1993
        for key, entry in self.id_to_entry.iteritems():
 
1994
            file_id = key[0]
 
1995
            if file_id not in cache:
 
1996
                ie = self._bytes_to_entry(entry)
 
1997
                cache[file_id] = ie
 
1998
            else:
 
1999
                ie = cache[file_id]
 
2000
        last_parent_id = last_parent_ie = None
 
2001
        pid_items = self.parent_id_basename_to_file_id.iteritems()
 
2002
        for key, child_file_id in pid_items:
 
2003
            if key == ('', ''): # This is the root
 
2004
                if child_file_id != self.root_id:
 
2005
                    raise ValueError('Data inconsistency detected.'
 
2006
                        ' We expected data with key ("","") to match'
 
2007
                        ' the root id, but %s != %s'
 
2008
                        % (child_file_id, self.root_id))
 
2009
                continue
 
2010
            parent_id, basename = key
 
2011
            ie = cache[child_file_id]
 
2012
            if parent_id == last_parent_id:
 
2013
                parent_ie = last_parent_ie
 
2014
            else:
 
2015
                parent_ie = cache[parent_id]
 
2016
            if parent_ie.kind != 'directory':
 
2017
                raise ValueError('Data inconsistency detected.'
 
2018
                    ' An entry in the parent_id_basename_to_file_id map'
 
2019
                    ' has parent_id {%s} but the kind of that object'
 
2020
                    ' is %r not "directory"' % (parent_id, parent_ie.kind))
 
2021
            if parent_ie._children is None:
 
2022
                parent_ie._children = {}
 
2023
            basename = basename.decode('utf-8')
 
2024
            if basename in parent_ie._children:
 
2025
                existing_ie = parent_ie._children[basename]
 
2026
                if existing_ie != ie:
 
2027
                    raise ValueError('Data inconsistency detected.'
 
2028
                        ' Two entries with basename %r were found'
 
2029
                        ' in the parent entry {%s}'
 
2030
                        % (basename, parent_id))
 
2031
            if basename != ie.name:
 
2032
                raise ValueError('Data inconsistency detected.'
 
2033
                    ' In the parent_id_basename_to_file_id map, file_id'
 
2034
                    ' {%s} is listed as having basename %r, but in the'
 
2035
                    ' id_to_entry map it is %r'
 
2036
                    % (child_file_id, basename, ie.name))
 
2037
            parent_ie._children[basename] = ie
 
2038
        self._fully_cached = True
 
2039
 
1920
2040
    def iter_changes(self, basis):
1921
2041
        """Generate a Tree.iter_changes change list between this and basis.
1922
2042
 
2016
2136
            delta.append((old_path, new_path, file_id, entry))
2017
2137
        return delta
2018
2138
 
2019
 
    def path2id(self, name):
 
2139
    def path2id(self, relpath):
2020
2140
        """See CommonInventory.path2id()."""
2021
2141
        # TODO: perhaps support negative hits?
2022
 
        result = self._path_to_fileid_cache.get(name, None)
 
2142
        result = self._path_to_fileid_cache.get(relpath, None)
2023
2143
        if result is not None:
2024
2144
            return result
2025
 
        if isinstance(name, basestring):
2026
 
            names = osutils.splitpath(name)
 
2145
        if isinstance(relpath, basestring):
 
2146
            names = osutils.splitpath(relpath)
2027
2147
        else:
2028
 
            names = name
 
2148
            names = relpath
2029
2149
        current_id = self.root_id
2030
2150
        if current_id is None:
2031
2151
            return None
2032
2152
        parent_id_index = self.parent_id_basename_to_file_id
 
2153
        cur_path = None
2033
2154
        for basename in names:
2034
 
            # TODO: Cache each path we figure out in this function.
 
2155
            if cur_path is None:
 
2156
                cur_path = basename
 
2157
            else:
 
2158
                cur_path = cur_path + '/' + basename
2035
2159
            basename_utf8 = basename.encode('utf8')
2036
 
            key_filter = [(current_id, basename_utf8)]
2037
 
            file_id = None
2038
 
            for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
2039
 
                key_filter=key_filter):
2040
 
                if parent_id != current_id or name_utf8 != basename_utf8:
2041
 
                    raise errors.BzrError("corrupt inventory lookup! "
2042
 
                        "%r %r %r %r" % (parent_id, current_id, name_utf8,
2043
 
                        basename_utf8))
 
2160
            file_id = self._path_to_fileid_cache.get(cur_path, None)
2044
2161
            if file_id is None:
2045
 
                return None
 
2162
                key_filter = [StaticTuple(current_id, basename_utf8)]
 
2163
                items = parent_id_index.iteritems(key_filter)
 
2164
                for (parent_id, name_utf8), file_id in items:
 
2165
                    if parent_id != current_id or name_utf8 != basename_utf8:
 
2166
                        raise errors.BzrError("corrupt inventory lookup! "
 
2167
                            "%r %r %r %r" % (parent_id, current_id, name_utf8,
 
2168
                            basename_utf8))
 
2169
                if file_id is None:
 
2170
                    return None
 
2171
                else:
 
2172
                    self._path_to_fileid_cache[cur_path] = file_id
2046
2173
            current_id = file_id
2047
 
        self._path_to_fileid_cache[name] = current_id
2048
2174
        return current_id
2049
2175
 
2050
2176
    def to_lines(self):
2055
2181
            lines.append('search_key_name: %s\n' % (self._search_key_name,))
2056
2182
            lines.append("root_id: %s\n" % self.root_id)
2057
2183
            lines.append('parent_id_basename_to_file_id: %s\n' %
2058
 
                self.parent_id_basename_to_file_id.key())
 
2184
                (self.parent_id_basename_to_file_id.key()[0],))
2059
2185
            lines.append("revision_id: %s\n" % self.revision_id)
2060
 
            lines.append("id_to_entry: %s\n" % self.id_to_entry.key())
 
2186
            lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
2061
2187
        else:
2062
2188
            lines.append("revision_id: %s\n" % self.revision_id)
2063
2189
            lines.append("root_id: %s\n" % self.root_id)
2064
2190
            if self.parent_id_basename_to_file_id is not None:
2065
2191
                lines.append('parent_id_basename_to_file_id: %s\n' %
2066
 
                    self.parent_id_basename_to_file_id.key())
2067
 
            lines.append("id_to_entry: %s\n" % self.id_to_entry.key())
 
2192
                    (self.parent_id_basename_to_file_id.key()[0],))
 
2193
            lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
2068
2194
        return lines
2069
2195
 
2070
2196
    @property
2076
2202
class CHKInventoryDirectory(InventoryDirectory):
2077
2203
    """A directory in an inventory."""
2078
2204
 
2079
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
2080
 
                 'text_id', 'parent_id', '_children', 'executable',
2081
 
                 'revision', 'symlink_target', 'reference_revision',
2082
 
                 '_chk_inventory']
 
2205
    __slots__ = ['_children', '_chk_inventory']
2083
2206
 
2084
2207
    def __init__(self, file_id, name, parent_id, chk_inventory):
2085
2208
        # Don't call InventoryDirectory.__init__ - it isn't right for this
2086
2209
        # class.
2087
2210
        InventoryEntry.__init__(self, file_id, name, parent_id)
2088
2211
        self._children = None
2089
 
        self.kind = 'directory'
2090
2212
        self._chk_inventory = chk_inventory
2091
2213
 
2092
2214
    @property
2111
2233
        parent_id_index = self._chk_inventory.parent_id_basename_to_file_id
2112
2234
        child_keys = set()
2113
2235
        for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
2114
 
            key_filter=[(self.file_id,)]):
2115
 
            child_keys.add((file_id,))
 
2236
            key_filter=[StaticTuple(self.file_id,)]):
 
2237
            child_keys.add(StaticTuple(file_id,))
2116
2238
        cached = set()
2117
2239
        for file_id_key in child_keys:
2118
2240
            entry = self._chk_inventory._fileid_to_entry_cache.get(
2151
2273
    try:
2152
2274
        factory = entry_factory[kind]
2153
2275
    except KeyError:
2154
 
        raise BzrError("unknown kind %r" % kind)
 
2276
        raise errors.BadFileKindError(name, kind)
2155
2277
    return factory(file_id, name, parent_id)
2156
2278
 
2157
2279