~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

Merge up bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005-2011 Canonical Ltd
 
1
# Copyright (C) 2005, 2006, 2007 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
 
# FIXME: This refactoring of the workingtree code doesn't seem to keep
 
17
# FIXME: This refactoring of the workingtree code doesn't seem to keep 
18
18
# the WorkingTree's copy of the inventory in sync with the branch.  The
19
19
# branch modifies its working inventory when it does a commit to make
20
20
# missing files permanently removed.
23
23
# But those depend on its position within a particular inventory, and
24
24
# it would be nice not to need to hold the backpointer here.
25
25
 
26
 
from __future__ import absolute_import
27
 
 
28
26
# This should really be an id randomly assigned when the tree is
29
27
# created, but it's not for now.
30
28
ROOT_ID = "TREE_ROOT"
31
29
 
 
30
import os
 
31
import re
 
32
import sys
 
33
 
32
34
from bzrlib.lazy_import import lazy_import
33
35
lazy_import(globals(), """
34
36
import collections
35
 
import copy
36
 
import re
37
37
import tarfile
38
38
 
 
39
import bzrlib
39
40
from bzrlib import (
40
 
    chk_map,
41
41
    errors,
42
42
    generate_ids,
43
43
    osutils,
 
44
    symbol_versioning,
 
45
    workingtree,
44
46
    )
45
47
""")
46
48
 
47
 
from bzrlib import (
48
 
    lazy_regex,
49
 
    trace,
50
 
    )
51
 
 
52
 
from bzrlib.static_tuple import StaticTuple
53
 
from bzrlib.symbol_versioning import (
54
 
    deprecated_in,
55
 
    deprecated_method,
56
 
    )
 
49
from bzrlib.errors import (
 
50
    BzrCheckError,
 
51
    BzrError,
 
52
    )
 
53
from bzrlib.symbol_versioning import deprecated_method
 
54
from bzrlib.trace import mutter
57
55
 
58
56
 
59
57
class InventoryEntry(object):
71
69
        file_id of the parent directory, or ROOT_ID
72
70
 
73
71
    revision
74
 
        the revision_id in which this variation of this file was
 
72
        the revision_id in which this variation of this file was 
75
73
        introduced.
76
74
 
77
75
    executable
80
78
 
81
79
    text_sha1
82
80
        sha-1 of the text of the file
83
 
 
 
81
        
84
82
    text_size
85
83
        size in bytes of the text of the file
86
 
 
 
84
        
87
85
    (reading a version 4 tree created a text_id field.)
88
86
 
89
87
    >>> i = Inventory()
92
90
    >>> i.add(InventoryDirectory('123', 'src', ROOT_ID))
93
91
    InventoryDirectory('123', 'src', parent_id='TREE_ROOT', revision=None)
94
92
    >>> i.add(InventoryFile('2323', 'hello.c', parent_id='123'))
95
 
    InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None, revision=None)
 
93
    InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None)
96
94
    >>> shouldbe = {0: '', 1: 'src', 2: 'src/hello.c'}
97
95
    >>> for ix, j in enumerate(i.iter_entries()):
98
96
    ...   print (j[0] == shouldbe[ix], j[1])
99
 
    ...
 
97
    ... 
100
98
    (True, InventoryDirectory('TREE_ROOT', u'', parent_id=None, revision=None))
101
99
    (True, InventoryDirectory('123', 'src', parent_id='TREE_ROOT', revision=None))
102
 
    (True, InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None, revision=None))
 
100
    (True, InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None))
103
101
    >>> i.add(InventoryFile('2324', 'bye.c', '123'))
104
 
    InventoryFile('2324', 'bye.c', parent_id='123', sha1=None, len=None, revision=None)
 
102
    InventoryFile('2324', 'bye.c', parent_id='123', sha1=None, len=None)
105
103
    >>> i.add(InventoryDirectory('2325', 'wibble', '123'))
106
104
    InventoryDirectory('2325', 'wibble', parent_id='123', revision=None)
107
105
    >>> i.path2id('src/wibble')
108
106
    '2325'
 
107
    >>> '2325' in i
 
108
    True
109
109
    >>> i.add(InventoryFile('2326', 'wibble.c', '2325'))
110
 
    InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None, revision=None)
 
110
    InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None)
111
111
    >>> i['2326']
112
 
    InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None, revision=None)
 
112
    InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None)
113
113
    >>> for path, entry in i.iter_entries():
114
114
    ...     print path
115
 
    ...
 
115
    ... 
116
116
    <BLANKLINE>
117
117
    src
118
118
    src/bye.c
125
125
 
126
126
    # Constants returned by describe_change()
127
127
    #
128
 
    # TODO: These should probably move to some kind of FileChangeDescription
129
 
    # class; that's like what's inside a TreeDelta but we want to be able to
 
128
    # TODO: These should probably move to some kind of FileChangeDescription 
 
129
    # class; that's like what's inside a TreeDelta but we want to be able to 
130
130
    # generate them just for one file at a time.
131
131
    RENAMED = 'renamed'
132
132
    MODIFIED_AND_RENAMED = 'modified and renamed'
133
 
 
134
 
    __slots__ = ['file_id', 'revision', 'parent_id', 'name']
135
 
 
136
 
    # Attributes that all InventoryEntry instances are expected to have, but
137
 
    # that don't vary for all kinds of entry.  (e.g. symlink_target is only
138
 
    # relevant to InventoryLink, so there's no reason to make every
139
 
    # InventoryFile instance allocate space to hold a value for it.)
140
 
    # Attributes that only vary for files: executable, text_sha1, text_size,
141
 
    # text_id
142
 
    executable = False
143
 
    text_sha1 = None
144
 
    text_size = None
145
 
    text_id = None
146
 
    # Attributes that only vary for symlinks: symlink_target
147
 
    symlink_target = None
148
 
    # Attributes that only vary for tree-references: reference_revision
149
 
    reference_revision = None
150
 
 
 
133
    
 
134
    __slots__ = []
151
135
 
152
136
    def detect_changes(self, old_entry):
153
137
        """Return a (text_modified, meta_modified) from this to old_entry.
154
 
 
155
 
        _read_tree_state must have been called on self and old_entry prior to
 
138
        
 
139
        _read_tree_state must have been called on self and old_entry prior to 
156
140
        calling detect_changes.
157
141
        """
158
142
        return False, False
160
144
    def _diff(self, text_diff, from_label, tree, to_label, to_entry, to_tree,
161
145
             output_to, reverse=False):
162
146
        """Perform a diff between two entries of the same kind."""
163
 
 
 
147
    
164
148
    def parent_candidates(self, previous_inventories):
165
149
        """Find possible per-file graph parents.
166
150
 
174
158
        candidates = {}
175
159
        # identify candidate head revision ids.
176
160
        for inv in previous_inventories:
177
 
            if inv.has_id(self.file_id):
 
161
            if self.file_id in inv:
178
162
                ie = inv[self.file_id]
179
163
                if ie.revision in candidates:
180
164
                    # same revision value in two different inventories:
181
165
                    # correct possible inconsistencies:
182
 
                    #     * there was a bug in revision updates with 'x' bit
 
166
                    #     * there was a bug in revision updates with 'x' bit 
183
167
                    #       support.
184
168
                    try:
185
169
                        if candidates[ie.revision].executable != ie.executable:
192
176
                    candidates[ie.revision] = ie
193
177
        return candidates
194
178
 
 
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
 
195
188
    def has_text(self):
196
189
        """Return true if the object this entry represents has textual data.
197
190
 
203
196
        """
204
197
        return False
205
198
 
206
 
    def __init__(self, file_id, name, parent_id):
 
199
    def __init__(self, file_id, name, parent_id, text_id=None):
207
200
        """Create an InventoryEntry
208
 
 
 
201
        
209
202
        The filename must be a single component, relative to the
210
203
        parent directory; it cannot be a whole path or relative name.
211
204
 
220
213
        """
221
214
        if '/' in name or '\\' in name:
222
215
            raise errors.InvalidEntryName(name=name)
 
216
        self.executable = False
 
217
        self.revision = None
 
218
        self.text_sha1 = None
 
219
        self.text_size = None
223
220
        self.file_id = file_id
224
 
        self.revision = None
225
221
        self.name = name
 
222
        self.text_id = text_id
226
223
        self.parent_id = parent_id
 
224
        self.symlink_target = None
 
225
        self.reference_revision = None
227
226
 
228
227
    def kind_character(self):
229
228
        """Return a short kind indicator useful for appending to names."""
230
 
        raise errors.BzrError('unknown kind %r' % self.kind)
 
229
        raise BzrError('unknown kind %r' % self.kind)
231
230
 
232
231
    known_kinds = ('file', 'directory', 'symlink')
233
232
 
 
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
    def put_on_disk(self, dest, dp, tree):
 
242
        """Create a representation of self on disk in the prefix dest.
 
243
        
 
244
        This is a template method - implement _put_on_disk in subclasses.
 
245
        """
 
246
        fullpath = osutils.pathjoin(dest, dp)
 
247
        self._put_on_disk(fullpath, tree)
 
248
        # mutter("  export {%s} kind %s to %s", self.file_id,
 
249
        #         self.kind, fullpath)
 
250
 
 
251
    def _put_on_disk(self, fullpath, tree):
 
252
        """Put this entry onto disk at fullpath, from tree tree."""
 
253
        raise BzrError("don't know how to export {%s} of kind %r" % (self.file_id, self.kind))
 
254
 
234
255
    def sorted_children(self):
235
256
        return sorted(self.children.items())
236
257
 
238
259
    def versionable_kind(kind):
239
260
        return (kind in ('file', 'directory', 'symlink', 'tree-reference'))
240
261
 
241
 
    def check(self, checker, rev_id, inv):
 
262
    def check(self, checker, rev_id, inv, tree):
242
263
        """Check this inventory entry is intact.
243
264
 
244
265
        This is a template method, override _check for kind specific
245
266
        tests.
246
267
 
247
 
        :param checker: Check object providing context for the checks;
 
268
        :param checker: Check object providing context for the checks; 
248
269
             can be used to find out what parts of the repository have already
249
270
             been checked.
250
271
        :param rev_id: Revision id from which this InventoryEntry was loaded.
251
272
             Not necessarily the last-changed revision for this file.
252
273
        :param inv: Inventory from which the entry was loaded.
 
274
        :param tree: RevisionTree for this entry.
253
275
        """
254
276
        if self.parent_id is not None:
255
277
            if not inv.has_id(self.parent_id):
256
 
                raise errors.BzrCheckError(
257
 
                    'missing parent {%s} in inventory for revision {%s}' % (
258
 
                        self.parent_id, rev_id))
259
 
        checker._add_entry_to_text_key_references(inv, self)
260
 
        self._check(checker, rev_id)
 
278
                raise BzrCheckError('missing parent {%s} in inventory for revision {%s}'
 
279
                        % (self.parent_id, rev_id))
 
280
        self._check(checker, rev_id, tree)
261
281
 
262
 
    def _check(self, checker, rev_id):
 
282
    def _check(self, checker, rev_id, tree):
263
283
        """Check this inventory entry for kind specific errors."""
264
 
        checker._report_items.append(
265
 
            'unknown entry kind %r in revision {%s}' % (self.kind, rev_id))
 
284
        raise BzrCheckError('unknown entry kind %r in revision {%s}' % 
 
285
                            (self.kind, rev_id))
266
286
 
267
287
    def copy(self):
268
288
        """Clone this inventory entry."""
271
291
    @staticmethod
272
292
    def describe_change(old_entry, new_entry):
273
293
        """Describe the change between old_entry and this.
274
 
 
 
294
        
275
295
        This smells of being an InterInventoryEntry situation, but as its
276
296
        the first one, we're making it a static method for now.
277
297
 
278
 
        An entry with a different parent, or different name is considered
 
298
        An entry with a different parent, or different name is considered 
279
299
        to be renamed. Reparenting is an internal detail.
280
300
        Note that renaming the parent does not trigger a rename for the
281
301
        child entry itself.
319
339
                   self.revision))
320
340
 
321
341
    def __eq__(self, other):
322
 
        if other is self:
323
 
            # For the case when objects are cached
324
 
            return True
325
342
        if not isinstance(other, InventoryEntry):
326
343
            return NotImplemented
327
344
 
362
379
 
363
380
    def _read_tree_state(self, path, work_tree):
364
381
        """Populate fields in the inventory entry from the given tree.
365
 
 
 
382
        
366
383
        Note that this should be modified to be a noop on virtual trees
367
384
        as all entries created there are prepopulated.
368
385
        """
369
 
        # TODO: Rather than running this manually, we should check the
 
386
        # TODO: Rather than running this manually, we should check the 
370
387
        # working sha1 and other expensive properties when they're
371
388
        # first requested, or preload them if they're already known
372
389
        pass            # nothing to do by default
375
392
        pass
376
393
 
377
394
 
 
395
class RootEntry(InventoryEntry):
 
396
 
 
397
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
 
398
                 'text_id', 'parent_id', 'children', 'executable',
 
399
                 'revision', 'symlink_target', 'reference_revision']
 
400
 
 
401
    def _check(self, checker, rev_id, tree):
 
402
        """See InventoryEntry._check"""
 
403
 
 
404
    def __init__(self, file_id):
 
405
        self.file_id = file_id
 
406
        self.children = {}
 
407
        self.kind = 'directory'
 
408
        self.parent_id = None
 
409
        self.name = u''
 
410
        self.revision = None
 
411
        symbol_versioning.warn('RootEntry is deprecated as of bzr 0.10.'
 
412
                               '  Please use InventoryDirectory instead.',
 
413
                               DeprecationWarning, stacklevel=2)
 
414
 
 
415
    def __eq__(self, other):
 
416
        if not isinstance(other, RootEntry):
 
417
            return NotImplemented
 
418
        
 
419
        return (self.file_id == other.file_id) \
 
420
               and (self.children == other.children)
 
421
 
 
422
 
378
423
class InventoryDirectory(InventoryEntry):
379
424
    """A directory in an inventory."""
380
425
 
381
 
    __slots__ = ['children']
382
 
 
383
 
    kind = 'directory'
384
 
 
385
 
    def _check(self, checker, rev_id):
 
426
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
 
427
                 'text_id', 'parent_id', 'children', 'executable',
 
428
                 'revision', 'symlink_target', 'reference_revision']
 
429
 
 
430
    def _check(self, checker, rev_id, tree):
386
431
        """See InventoryEntry._check"""
387
 
        # In non rich root repositories we do not expect a file graph for the
388
 
        # root.
389
 
        if self.name == '' and not checker.rich_roots:
390
 
            return
391
 
        # Directories are stored as an empty file, but the file should exist
392
 
        # to provide a per-fileid log. The hash of every directory content is
393
 
        # "da..." below (the sha1sum of '').
394
 
        checker.add_pending_item(rev_id,
395
 
            ('texts', self.file_id, self.revision), 'text',
396
 
             'da39a3ee5e6b4b0d3255bfef95601890afd80709')
 
432
        if self.text_sha1 is not None or self.text_size is not None or self.text_id is not None:
 
433
            raise BzrCheckError('directory {%s} has text in revision {%s}'
 
434
                                % (self.file_id, rev_id))
397
435
 
398
436
    def copy(self):
399
437
        other = InventoryDirectory(self.file_id, self.name, self.parent_id)
405
443
    def __init__(self, file_id, name, parent_id):
406
444
        super(InventoryDirectory, self).__init__(file_id, name, parent_id)
407
445
        self.children = {}
 
446
        self.kind = 'directory'
408
447
 
409
448
    def kind_character(self):
410
449
        """See InventoryEntry.kind_character."""
411
450
        return '/'
412
451
 
 
452
    def _put_in_tar(self, item, tree):
 
453
        """See InventoryEntry._put_in_tar."""
 
454
        item.type = tarfile.DIRTYPE
 
455
        fileobj = None
 
456
        item.name += '/'
 
457
        item.size = 0
 
458
        item.mode = 0755
 
459
        return fileobj
 
460
 
 
461
    def _put_on_disk(self, fullpath, tree):
 
462
        """See InventoryEntry._put_on_disk."""
 
463
        os.mkdir(fullpath)
 
464
 
413
465
 
414
466
class InventoryFile(InventoryEntry):
415
467
    """A file in an inventory."""
416
468
 
417
 
    __slots__ = ['text_sha1', 'text_size', 'text_id', 'executable']
418
 
 
419
 
    kind = 'file'
420
 
 
421
 
    def __init__(self, file_id, name, parent_id):
422
 
        super(InventoryFile, self).__init__(file_id, name, parent_id)
423
 
        self.text_sha1 = None
424
 
        self.text_size = None
425
 
        self.text_id = None
426
 
        self.executable = False
427
 
 
428
 
    def _check(self, checker, tree_revision_id):
 
469
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
 
470
                 'text_id', 'parent_id', 'children', 'executable',
 
471
                 'revision', 'symlink_target', 'reference_revision']
 
472
 
 
473
    def _check(self, checker, tree_revision_id, tree):
429
474
        """See InventoryEntry._check"""
430
 
        # TODO: check size too.
431
 
        checker.add_pending_item(tree_revision_id,
432
 
            ('texts', self.file_id, self.revision), 'text',
433
 
             self.text_sha1)
434
 
        if self.text_size is None:
435
 
            checker._report_items.append(
436
 
                'fileid {%s} in {%s} has None for text_size' % (self.file_id,
437
 
                tree_revision_id))
 
475
        t = (self.file_id, self.revision)
 
476
        if t in checker.checked_texts:
 
477
            prev_sha = checker.checked_texts[t]
 
478
            if prev_sha != self.text_sha1:
 
479
                raise BzrCheckError(
 
480
                    'mismatched sha1 on {%s} in {%s} (%s != %s) %r' %
 
481
                    (self.file_id, tree_revision_id, prev_sha, self.text_sha1,
 
482
                     t))
 
483
            else:
 
484
                checker.repeated_text_cnt += 1
 
485
                return
 
486
 
 
487
        if self.file_id not in checker.checked_weaves:
 
488
            mutter('check weave {%s}', self.file_id)
 
489
            w = tree._get_weave(self.file_id)
 
490
            # Not passing a progress bar, because it creates a new
 
491
            # progress, which overwrites the current progress,
 
492
            # and doesn't look nice
 
493
            w.check()
 
494
            checker.checked_weaves[self.file_id] = True
 
495
        else:
 
496
            w = tree._get_weave(self.file_id)
 
497
 
 
498
        mutter('check version {%s} of {%s}', tree_revision_id, self.file_id)
 
499
        checker.checked_text_cnt += 1
 
500
        # We can't check the length, because Weave doesn't store that
 
501
        # information, and the whole point of looking at the weave's
 
502
        # sha1sum is that we don't have to extract the text.
 
503
        if self.text_sha1 != w.get_sha1s([self.revision])[0]:
 
504
            raise BzrCheckError('text {%s} version {%s} wrong sha1' 
 
505
                                % (self.file_id, self.revision))
 
506
        checker.checked_texts[t] = self.text_sha1
438
507
 
439
508
    def copy(self):
440
509
        other = InventoryFile(self.file_id, self.name, self.parent_id)
472
541
        """See InventoryEntry.has_text."""
473
542
        return True
474
543
 
 
544
    def __init__(self, file_id, name, parent_id):
 
545
        super(InventoryFile, self).__init__(file_id, name, parent_id)
 
546
        self.kind = 'file'
 
547
 
475
548
    def kind_character(self):
476
549
        """See InventoryEntry.kind_character."""
477
550
        return ''
478
551
 
 
552
    def _put_in_tar(self, item, tree):
 
553
        """See InventoryEntry._put_in_tar."""
 
554
        item.type = tarfile.REGTYPE
 
555
        fileobj = tree.get_file(self.file_id)
 
556
        item.size = self.text_size
 
557
        if tree.is_executable(self.file_id):
 
558
            item.mode = 0755
 
559
        else:
 
560
            item.mode = 0644
 
561
        return fileobj
 
562
 
 
563
    def _put_on_disk(self, fullpath, tree):
 
564
        """See InventoryEntry._put_on_disk."""
 
565
        osutils.pumpfile(tree.get_file(self.file_id), file(fullpath, 'wb'))
 
566
        if tree.is_executable(self.file_id):
 
567
            os.chmod(fullpath, 0755)
 
568
 
479
569
    def _read_tree_state(self, path, work_tree):
480
570
        """See InventoryEntry._read_tree_state."""
481
571
        self.text_sha1 = work_tree.get_file_sha1(self.file_id, path=path)
484
574
        self.executable = work_tree.is_executable(self.file_id, path=path)
485
575
 
486
576
    def __repr__(self):
487
 
        return ("%s(%r, %r, parent_id=%r, sha1=%r, len=%s, revision=%s)"
 
577
        return ("%s(%r, %r, parent_id=%r, sha1=%r, len=%s)"
488
578
                % (self.__class__.__name__,
489
579
                   self.file_id,
490
580
                   self.name,
491
581
                   self.parent_id,
492
582
                   self.text_sha1,
493
 
                   self.text_size,
494
 
                   self.revision))
 
583
                   self.text_size))
495
584
 
496
585
    def _forget_tree_state(self):
497
586
        self.text_sha1 = None
513
602
class InventoryLink(InventoryEntry):
514
603
    """A file in an inventory."""
515
604
 
516
 
    __slots__ = ['symlink_target']
517
 
 
518
 
    kind = 'symlink'
519
 
 
520
 
    def __init__(self, file_id, name, parent_id):
521
 
        super(InventoryLink, self).__init__(file_id, name, parent_id)
522
 
        self.symlink_target = None
523
 
 
524
 
    def _check(self, checker, tree_revision_id):
 
605
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
 
606
                 'text_id', 'parent_id', 'children', 'executable',
 
607
                 'revision', 'symlink_target', 'reference_revision']
 
608
 
 
609
    def _check(self, checker, rev_id, tree):
525
610
        """See InventoryEntry._check"""
 
611
        if self.text_sha1 is not None or self.text_size is not None or self.text_id is not None:
 
612
            raise BzrCheckError('symlink {%s} has text in revision {%s}'
 
613
                    % (self.file_id, rev_id))
526
614
        if self.symlink_target is None:
527
 
            checker._report_items.append(
528
 
                'symlink {%s} has no target in revision {%s}'
529
 
                    % (self.file_id, tree_revision_id))
530
 
        # Symlinks are stored as ''
531
 
        checker.add_pending_item(tree_revision_id,
532
 
            ('texts', self.file_id, self.revision), 'text',
533
 
             'da39a3ee5e6b4b0d3255bfef95601890afd80709')
 
615
            raise BzrCheckError('symlink {%s} has no target in revision {%s}'
 
616
                    % (self.file_id, rev_id))
534
617
 
535
618
    def copy(self):
536
619
        other = InventoryLink(self.file_id, self.name, self.parent_id)
543
626
        # FIXME: which _modified field should we use ? RBC 20051003
544
627
        text_modified = (self.symlink_target != old_entry.symlink_target)
545
628
        if text_modified:
546
 
            trace.mutter("    symlink target changed")
 
629
            mutter("    symlink target changed")
547
630
        meta_modified = False
548
631
        return text_modified, meta_modified
549
632
 
566
649
        differ = DiffSymlink(old_tree, new_tree, output_to)
567
650
        return differ.diff_symlink(old_target, new_target)
568
651
 
 
652
    def __init__(self, file_id, name, parent_id):
 
653
        super(InventoryLink, self).__init__(file_id, name, parent_id)
 
654
        self.kind = 'symlink'
 
655
 
569
656
    def kind_character(self):
570
657
        """See InventoryEntry.kind_character."""
571
658
        return ''
572
659
 
 
660
    def _put_in_tar(self, item, tree):
 
661
        """See InventoryEntry._put_in_tar."""
 
662
        item.type = tarfile.SYMTYPE
 
663
        fileobj = None
 
664
        item.size = 0
 
665
        item.mode = 0755
 
666
        item.linkname = self.symlink_target
 
667
        return fileobj
 
668
 
 
669
    def _put_on_disk(self, fullpath, tree):
 
670
        """See InventoryEntry._put_on_disk."""
 
671
        try:
 
672
            os.symlink(self.symlink_target, fullpath)
 
673
        except OSError,e:
 
674
            raise BzrError("Failed to create symlink %r -> %r, error: %s" % (fullpath, self.symlink_target, e))
 
675
 
573
676
    def _read_tree_state(self, path, work_tree):
574
677
        """See InventoryEntry._read_tree_state."""
575
678
        self.symlink_target = work_tree.get_symlink_target(self.file_id)
586
689
 
587
690
 
588
691
class TreeReference(InventoryEntry):
589
 
 
590
 
    __slots__ = ['reference_revision']
591
 
 
 
692
    
592
693
    kind = 'tree-reference'
593
 
 
 
694
    
594
695
    def __init__(self, file_id, name, parent_id, revision=None,
595
696
                 reference_revision=None):
596
697
        InventoryEntry.__init__(self, file_id, name, parent_id)
608
709
            self.file_id, path)
609
710
 
610
711
    def _forget_tree_state(self):
611
 
        self.reference_revision = None
 
712
        self.reference_revision = None 
612
713
 
613
714
    def _unchanged(self, previous_ie):
614
715
        """See InventoryEntry._unchanged."""
618
719
        return compatible
619
720
 
620
721
 
621
 
class CommonInventory(object):
622
 
    """Basic inventory logic, defined in terms of primitives like has_id.
623
 
 
624
 
    An inventory is the metadata about the contents of a tree.
625
 
 
626
 
    This is broadly a map from file_id to entries such as directories, files,
627
 
    symlinks and tree references. Each entry maintains its own metadata like
628
 
    SHA1 and length for files, or children for a directory.
629
 
 
 
722
class Inventory(object):
 
723
    """Inventory of versioned files in a tree.
 
724
 
 
725
    This describes which file_id is present at each point in the tree,
 
726
    and possibly the SHA-1 or other information about the file.
630
727
    Entries can be looked up either by path or by file_id.
631
728
 
 
729
    The inventory represents a typical unix file tree, with
 
730
    directories containing files and subdirectories.  We never store
 
731
    the full path to a file, because renaming a directory implicitly
 
732
    moves all of its contents.  This class internally maintains a
 
733
    lookup tree that allows the children under a directory to be
 
734
    returned quickly.
 
735
 
632
736
    InventoryEntry objects must not be modified after they are
633
737
    inserted, other than through the Inventory API.
 
738
 
 
739
    >>> inv = Inventory()
 
740
    >>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
 
741
    InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
742
    >>> inv['123-123'].name
 
743
    'hello.c'
 
744
 
 
745
    May be treated as an iterator or set to look up file ids:
 
746
    
 
747
    >>> bool(inv.path2id('hello.c'))
 
748
    True
 
749
    >>> '123-123' in inv
 
750
    True
 
751
 
 
752
    May also look up by name:
 
753
 
 
754
    >>> [x[0] for x in inv.iter_entries()]
 
755
    ['', u'hello.c']
 
756
    >>> inv = Inventory('TREE_ROOT-12345678-12345678')
 
757
    >>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
 
758
    Traceback (most recent call last):
 
759
    BzrError: parent_id {TREE_ROOT} not in inventory
 
760
    >>> inv.add(InventoryFile('123-123', 'hello.c', 'TREE_ROOT-12345678-12345678'))
 
761
    InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT-12345678-12345678', sha1=None, len=None)
634
762
    """
635
 
 
636
 
    def has_filename(self, filename):
637
 
        return bool(self.path2id(filename))
638
 
 
639
 
    def id2path(self, file_id):
640
 
        """Return as a string the path to file_id.
641
 
 
642
 
        >>> i = Inventory()
643
 
        >>> e = i.add(InventoryDirectory('src-id', 'src', ROOT_ID))
644
 
        >>> e = i.add(InventoryFile('foo-id', 'foo.c', parent_id='src-id'))
645
 
        >>> print i.id2path('foo-id')
646
 
        src/foo.c
647
 
 
648
 
        :raises NoSuchId: If file_id is not present in the inventory.
649
 
        """
650
 
        # get all names, skipping root
651
 
        return '/'.join(reversed(
652
 
            [parent.name for parent in
653
 
             self._iter_file_id_parents(file_id)][:-1]))
654
 
 
655
 
    def iter_entries(self, from_dir=None, recursive=True):
656
 
        """Return (path, entry) pairs, in order by name.
657
 
        
658
 
        :param from_dir: if None, start from the root,
659
 
          otherwise start from this directory (either file-id or entry)
660
 
        :param recursive: recurse into directories or not
661
 
        """
 
763
    def __init__(self, root_id=ROOT_ID, revision_id=None):
 
764
        """Create or read an inventory.
 
765
 
 
766
        If a working directory is specified, the inventory is read
 
767
        from there.  If the file is specified, read from that. If not,
 
768
        the inventory is created empty.
 
769
 
 
770
        The inventory is created with a default root directory, with
 
771
        an id of None.
 
772
        """
 
773
        if root_id is not None:
 
774
            self._set_root(InventoryDirectory(root_id, u'', None))
 
775
        else:
 
776
            self.root = None
 
777
            self._byid = {}
 
778
        self.revision_id = revision_id
 
779
 
 
780
    def __repr__(self):
 
781
        return "<Inventory object at %x, contents=%r>" % (id(self), self._byid)
 
782
 
 
783
    def apply_delta(self, delta):
 
784
        """Apply a delta to this inventory.
 
785
 
 
786
        :param delta: A list of changes to apply. After all the changes are
 
787
            applied the final inventory must be internally consistent, but it
 
788
            is ok to supply changes which, if only half-applied would have an
 
789
            invalid result - such as supplying two changes which rename two
 
790
            files, 'A' and 'B' with each other : [('A', 'B', 'A-id', a_entry),
 
791
            ('B', 'A', 'B-id', b_entry)].
 
792
 
 
793
            Each change is a tuple, of the form (old_path, new_path, file_id,
 
794
            new_entry).
 
795
            
 
796
            When new_path is None, the change indicates the removal of an entry
 
797
            from the inventory and new_entry will be ignored (using None is
 
798
            appropriate). If new_path is not None, then new_entry must be an
 
799
            InventoryEntry instance, which will be incorporated into the
 
800
            inventory (and replace any existing entry with the same file id).
 
801
            
 
802
            When old_path is None, the change indicates the addition of
 
803
            a new entry to the inventory.
 
804
            
 
805
            When neither new_path nor old_path are None, the change is a
 
806
            modification to an entry, such as a rename, reparent, kind change
 
807
            etc. 
 
808
 
 
809
            The children attribute of new_entry is ignored. This is because
 
810
            this method preserves children automatically across alterations to
 
811
            the parent of the children, and cases where the parent id of a
 
812
            child is changing require the child to be passed in as a separate
 
813
            change regardless. E.g. in the recursive deletion of a directory -
 
814
            the directory's children must be included in the delta, or the
 
815
            final inventory will be invalid.
 
816
        """
 
817
        children = {}
 
818
        # Remove all affected items which were in the original inventory,
 
819
        # starting with the longest paths, thus ensuring parents are examined
 
820
        # after their children, which means that everything we examine has no
 
821
        # modified children remaining by the time we examine it.
 
822
        for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
 
823
                                        if op is not None), reverse=True):
 
824
            if file_id not in self:
 
825
                # adds come later
 
826
                continue
 
827
            # Preserve unaltered children of file_id for later reinsertion.
 
828
            children[file_id] = getattr(self[file_id], 'children', {})
 
829
            # Remove file_id and the unaltered children. If file_id is not
 
830
            # being deleted it will be reinserted back later.
 
831
            self.remove_recursive_id(file_id)
 
832
        # Insert all affected which should be in the new inventory, reattaching
 
833
        # their children if they had any. This is done from shortest path to
 
834
        # longest, ensuring that items which were modified and whose parents in
 
835
        # the resulting inventory were also modified, are inserted after their
 
836
        # parents.
 
837
        for new_path, new_entry in sorted((np, e) for op, np, f, e in
 
838
                                          delta if np is not None):
 
839
            if new_entry.kind == 'directory':
 
840
                new_entry.children = children.get(new_entry.file_id, {})
 
841
            self.add(new_entry)
 
842
 
 
843
    def _set_root(self, ie):
 
844
        self.root = ie
 
845
        self._byid = {self.root.file_id: self.root}
 
846
 
 
847
    def copy(self):
 
848
        # TODO: jam 20051218 Should copy also copy the revision_id?
 
849
        entries = self.iter_entries()
 
850
        if self.root is None:
 
851
            return Inventory(root_id=None)
 
852
        other = Inventory(entries.next()[1].file_id)
 
853
        # copy recursively so we know directories will be added before
 
854
        # their children.  There are more efficient ways than this...
 
855
        for path, entry in entries:
 
856
            other.add(entry.copy())
 
857
        return other
 
858
 
 
859
    def __iter__(self):
 
860
        return iter(self._byid)
 
861
 
 
862
    def __len__(self):
 
863
        """Returns number of entries."""
 
864
        return len(self._byid)
 
865
 
 
866
    def iter_entries(self, from_dir=None):
 
867
        """Return (path, entry) pairs, in order by name."""
662
868
        if from_dir is None:
663
869
            if self.root is None:
664
870
                return
665
871
            from_dir = self.root
666
872
            yield '', self.root
667
873
        elif isinstance(from_dir, basestring):
668
 
            from_dir = self[from_dir]
669
 
 
 
874
            from_dir = self._byid[from_dir]
 
875
            
670
876
        # unrolling the recursive called changed the time from
671
877
        # 440ms/663ms (inline/total) to 116ms/116ms
672
878
        children = from_dir.children.items()
673
879
        children.sort()
674
 
        if not recursive:
675
 
            for name, ie in children:
676
 
                yield name, ie
677
 
            return
678
880
        children = collections.deque(children)
679
881
        stack = [(u'', children)]
680
882
        while stack:
705
907
                # if we finished all children, pop it off the stack
706
908
                stack.pop()
707
909
 
708
 
    def _preload_cache(self):
709
 
        """Populate any caches, we are about to access all items.
710
 
        
711
 
        The default implementation does nothing, because CommonInventory doesn't
712
 
        have a cache.
713
 
        """
714
 
        pass
715
 
    
716
910
    def iter_entries_by_dir(self, from_dir=None, specific_file_ids=None,
717
911
        yield_parents=False):
718
912
        """Iterate over the entries in a directory first order.
731
925
            specific_file_ids = set(specific_file_ids)
732
926
        # TODO? Perhaps this should return the from_dir so that the root is
733
927
        # yielded? or maybe an option?
734
 
        if from_dir is None and specific_file_ids is None:
735
 
            # They are iterating from the root, and have not specified any
736
 
            # specific entries to look at. All current callers fully consume the
737
 
            # iterator, so we can safely assume we are accessing all entries
738
 
            self._preload_cache()
739
928
        if from_dir is None:
740
929
            if self.root is None:
741
930
                return
743
932
            if (not yield_parents and specific_file_ids is not None and
744
933
                len(specific_file_ids) == 1):
745
934
                file_id = list(specific_file_ids)[0]
746
 
                if self.has_id(file_id):
 
935
                if file_id in self:
747
936
                    yield self.id2path(file_id), self[file_id]
748
 
                return
 
937
                return 
749
938
            from_dir = self.root
750
939
            if (specific_file_ids is None or yield_parents or
751
940
                self.root.file_id in specific_file_ids):
752
941
                yield u'', self.root
753
942
        elif isinstance(from_dir, basestring):
754
 
            from_dir = self[from_dir]
 
943
            from_dir = self._byid[from_dir]
755
944
 
756
945
        if specific_file_ids is not None:
757
946
            # TODO: jam 20070302 This could really be done as a loop rather
758
947
            #       than a bunch of recursive calls.
759
948
            parents = set()
760
 
            byid = self
 
949
            byid = self._byid
761
950
            def add_ancestors(file_id):
762
 
                if not byid.has_id(file_id):
 
951
                if file_id not in byid:
763
952
                    return
764
953
                parent_id = byid[file_id].parent_id
765
954
                if parent_id is None:
771
960
                add_ancestors(file_id)
772
961
        else:
773
962
            parents = None
774
 
 
 
963
            
775
964
        stack = [(u'', from_dir)]
776
965
        while stack:
777
966
            cur_relpath, cur_dir = stack.pop()
781
970
 
782
971
                child_relpath = cur_relpath + child_name
783
972
 
784
 
                if (specific_file_ids is None or
 
973
                if (specific_file_ids is None or 
785
974
                    child_ie.file_id in specific_file_ids or
786
975
                    (yield_parents and child_ie.file_id in parents)):
787
976
                    yield child_relpath, child_ie
791
980
                        child_dirs.append((child_relpath+'/', child_ie))
792
981
            stack.extend(reversed(child_dirs))
793
982
 
794
 
    def _make_delta(self, old):
795
 
        """Make an inventory delta from two inventories."""
796
 
        old_ids = set(old)
797
 
        new_ids = set(self)
798
 
        adds = new_ids - old_ids
799
 
        deletes = old_ids - new_ids
800
 
        common = old_ids.intersection(new_ids)
801
 
        delta = []
802
 
        for file_id in deletes:
803
 
            delta.append((old.id2path(file_id), None, file_id, None))
804
 
        for file_id in adds:
805
 
            delta.append((None, self.id2path(file_id), file_id, self[file_id]))
806
 
        for file_id in common:
807
 
            if old[file_id] != self[file_id]:
808
 
                delta.append((old.id2path(file_id), self.id2path(file_id),
809
 
                    file_id, self[file_id]))
810
 
        return delta
811
 
 
812
983
    def make_entry(self, kind, name, parent_id, file_id=None):
813
984
        """Simple thunk to bzrlib.inventory.make_entry."""
814
985
        return make_entry(kind, name, parent_id, file_id)
828
999
                if ie.kind == 'directory':
829
1000
                    descend(ie, child_path)
830
1001
 
831
 
        if self.root is not None:
832
 
            descend(self.root, u'')
833
 
        return accum
834
 
 
835
 
    def path2id(self, relpath):
836
 
        """Walk down through directories to return entry of last component.
837
 
 
838
 
        :param relpath: may be either a list of path components, or a single
839
 
            string, in which case it is automatically split.
840
 
 
841
 
        This returns the entry of the last component in the path,
842
 
        which may be either a file or a directory.
843
 
 
844
 
        Returns None IFF the path is not found.
845
 
        """
846
 
        if isinstance(relpath, basestring):
847
 
            names = osutils.splitpath(relpath)
848
 
        else:
849
 
            names = relpath
850
 
 
851
 
        try:
852
 
            parent = self.root
853
 
        except errors.NoSuchId:
854
 
            # root doesn't exist yet so nothing else can
855
 
            return None
856
 
        if parent is None:
857
 
            return None
858
 
        for f in names:
859
 
            try:
860
 
                children = getattr(parent, 'children', None)
861
 
                if children is None:
862
 
                    return None
863
 
                cie = children[f]
864
 
                parent = cie
865
 
            except KeyError:
866
 
                # or raise an error?
867
 
                return None
868
 
 
869
 
        return parent.file_id
870
 
 
871
 
    def filter(self, specific_fileids):
872
 
        """Get an inventory view filtered against a set of file-ids.
873
 
 
874
 
        Children of directories and parents are included.
875
 
 
876
 
        The result may or may not reference the underlying inventory
877
 
        so it should be treated as immutable.
878
 
        """
879
 
        interesting_parents = set()
880
 
        for fileid in specific_fileids:
881
 
            try:
882
 
                interesting_parents.update(self.get_idpath(fileid))
883
 
            except errors.NoSuchId:
884
 
                # This fileid is not in the inventory - that's ok
885
 
                pass
886
 
        entries = self.iter_entries()
887
 
        if self.root is None:
888
 
            return Inventory(root_id=None)
889
 
        other = Inventory(entries.next()[1].file_id)
890
 
        other.root.revision = self.root.revision
891
 
        other.revision_id = self.revision_id
892
 
        directories_to_expand = set()
893
 
        for path, entry in entries:
894
 
            file_id = entry.file_id
895
 
            if (file_id in specific_fileids
896
 
                or entry.parent_id in directories_to_expand):
897
 
                if entry.kind == 'directory':
898
 
                    directories_to_expand.add(file_id)
899
 
            elif file_id not in interesting_parents:
900
 
                continue
901
 
            other.add(entry.copy())
902
 
        return other
903
 
 
904
 
    def get_idpath(self, file_id):
905
 
        """Return a list of file_ids for the path to an entry.
906
 
 
907
 
        The list contains one element for each directory followed by
908
 
        the id of the file itself.  So the length of the returned list
909
 
        is equal to the depth of the file in the tree, counting the
910
 
        root directory as depth 1.
911
 
        """
912
 
        p = []
913
 
        for parent in self._iter_file_id_parents(file_id):
914
 
            p.insert(0, parent.file_id)
915
 
        return p
916
 
 
917
 
 
918
 
class Inventory(CommonInventory):
919
 
    """Mutable dict based in-memory inventory.
920
 
 
921
 
    We never store the full path to a file, because renaming a directory
922
 
    implicitly moves all of its contents.  This class internally maintains a
923
 
    lookup tree that allows the children under a directory to be
924
 
    returned quickly.
925
 
 
926
 
    >>> inv = Inventory()
927
 
    >>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
928
 
    InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
929
 
    >>> inv['123-123'].name
930
 
    'hello.c'
931
 
 
932
 
    Id's may be looked up from paths:
933
 
 
934
 
    >>> inv.path2id('hello.c')
935
 
    '123-123'
936
 
    >>> inv.has_id('123-123')
937
 
    True
938
 
 
939
 
    There are iterators over the contents:
940
 
 
941
 
    >>> [entry[0] for entry in inv.iter_entries()]
942
 
    ['', u'hello.c']
943
 
    """
944
 
 
945
 
    def __init__(self, root_id=ROOT_ID, revision_id=None):
946
 
        """Create or read an inventory.
947
 
 
948
 
        If a working directory is specified, the inventory is read
949
 
        from there.  If the file is specified, read from that. If not,
950
 
        the inventory is created empty.
951
 
 
952
 
        The inventory is created with a default root directory, with
953
 
        an id of None.
954
 
        """
955
 
        if root_id is not None:
956
 
            self._set_root(InventoryDirectory(root_id, u'', None))
957
 
        else:
958
 
            self.root = None
959
 
            self._byid = {}
960
 
        self.revision_id = revision_id
961
 
 
962
 
    def __repr__(self):
963
 
        # More than one page of ouput is not useful anymore to debug
964
 
        max_len = 2048
965
 
        closing = '...}'
966
 
        contents = repr(self._byid)
967
 
        if len(contents) > max_len:
968
 
            contents = contents[:(max_len-len(closing))] + closing
969
 
        return "<Inventory object at %x, contents=%r>" % (id(self), contents)
970
 
 
971
 
    def apply_delta(self, delta):
972
 
        """Apply a delta to this inventory.
973
 
 
974
 
        See the inventory developers documentation for the theory behind
975
 
        inventory deltas.
976
 
 
977
 
        If delta application fails the inventory is left in an indeterminate
978
 
        state and must not be used.
979
 
 
980
 
        :param delta: A list of changes to apply. After all the changes are
981
 
            applied the final inventory must be internally consistent, but it
982
 
            is ok to supply changes which, if only half-applied would have an
983
 
            invalid result - such as supplying two changes which rename two
984
 
            files, 'A' and 'B' with each other : [('A', 'B', 'A-id', a_entry),
985
 
            ('B', 'A', 'B-id', b_entry)].
986
 
 
987
 
            Each change is a tuple, of the form (old_path, new_path, file_id,
988
 
            new_entry).
989
 
 
990
 
            When new_path is None, the change indicates the removal of an entry
991
 
            from the inventory and new_entry will be ignored (using None is
992
 
            appropriate). If new_path is not None, then new_entry must be an
993
 
            InventoryEntry instance, which will be incorporated into the
994
 
            inventory (and replace any existing entry with the same file id).
995
 
 
996
 
            When old_path is None, the change indicates the addition of
997
 
            a new entry to the inventory.
998
 
 
999
 
            When neither new_path nor old_path are None, the change is a
1000
 
            modification to an entry, such as a rename, reparent, kind change
1001
 
            etc.
1002
 
 
1003
 
            The children attribute of new_entry is ignored. This is because
1004
 
            this method preserves children automatically across alterations to
1005
 
            the parent of the children, and cases where the parent id of a
1006
 
            child is changing require the child to be passed in as a separate
1007
 
            change regardless. E.g. in the recursive deletion of a directory -
1008
 
            the directory's children must be included in the delta, or the
1009
 
            final inventory will be invalid.
1010
 
 
1011
 
            Note that a file_id must only appear once within a given delta.
1012
 
            An AssertionError is raised otherwise.
1013
 
        """
1014
 
        # Check that the delta is legal. It would be nice if this could be
1015
 
        # done within the loops below but it's safer to validate the delta
1016
 
        # before starting to mutate the inventory, as there isn't a rollback
1017
 
        # facility.
1018
 
        list(_check_delta_unique_ids(_check_delta_unique_new_paths(
1019
 
            _check_delta_unique_old_paths(_check_delta_ids_match_entry(
1020
 
            _check_delta_ids_are_valid(
1021
 
            _check_delta_new_path_entry_both_or_None(
1022
 
            delta)))))))
1023
 
 
1024
 
        children = {}
1025
 
        # Remove all affected items which were in the original inventory,
1026
 
        # starting with the longest paths, thus ensuring parents are examined
1027
 
        # after their children, which means that everything we examine has no
1028
 
        # modified children remaining by the time we examine it.
1029
 
        for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
1030
 
                                        if op is not None), reverse=True):
1031
 
            # Preserve unaltered children of file_id for later reinsertion.
1032
 
            file_id_children = getattr(self[file_id], 'children', {})
1033
 
            if len(file_id_children):
1034
 
                children[file_id] = file_id_children
1035
 
            if self.id2path(file_id) != old_path:
1036
 
                raise errors.InconsistentDelta(old_path, file_id,
1037
 
                    "Entry was at wrong other path %r." % self.id2path(file_id))
1038
 
            # Remove file_id and the unaltered children. If file_id is not
1039
 
            # being deleted it will be reinserted back later.
1040
 
            self.remove_recursive_id(file_id)
1041
 
        # Insert all affected which should be in the new inventory, reattaching
1042
 
        # their children if they had any. This is done from shortest path to
1043
 
        # longest, ensuring that items which were modified and whose parents in
1044
 
        # the resulting inventory were also modified, are inserted after their
1045
 
        # parents.
1046
 
        for new_path, f, new_entry in sorted((np, f, e) for op, np, f, e in
1047
 
                                          delta if np is not None):
1048
 
            if new_entry.kind == 'directory':
1049
 
                # Pop the child which to allow detection of children whose
1050
 
                # parents were deleted and which were not reattached to a new
1051
 
                # parent.
1052
 
                replacement = InventoryDirectory(new_entry.file_id,
1053
 
                    new_entry.name, new_entry.parent_id)
1054
 
                replacement.revision = new_entry.revision
1055
 
                replacement.children = children.pop(replacement.file_id, {})
1056
 
                new_entry = replacement
1057
 
            try:
1058
 
                self.add(new_entry)
1059
 
            except errors.DuplicateFileId:
1060
 
                raise errors.InconsistentDelta(new_path, new_entry.file_id,
1061
 
                    "New id is already present in target.")
1062
 
            except AttributeError:
1063
 
                raise errors.InconsistentDelta(new_path, new_entry.file_id,
1064
 
                    "Parent is not a directory.")
1065
 
            if self.id2path(new_entry.file_id) != new_path:
1066
 
                raise errors.InconsistentDelta(new_path, new_entry.file_id,
1067
 
                    "New path is not consistent with parent path.")
1068
 
        if len(children):
1069
 
            # Get the parent id that was deleted
1070
 
            parent_id, children = children.popitem()
1071
 
            raise errors.InconsistentDelta("<deleted>", parent_id,
1072
 
                "The file id was deleted but its children were not deleted.")
1073
 
 
1074
 
    def create_by_apply_delta(self, inventory_delta, new_revision_id,
1075
 
                              propagate_caches=False):
1076
 
        """See CHKInventory.create_by_apply_delta()"""
1077
 
        new_inv = self.copy()
1078
 
        new_inv.apply_delta(inventory_delta)
1079
 
        new_inv.revision_id = new_revision_id
1080
 
        return new_inv
1081
 
 
1082
 
    def _set_root(self, ie):
1083
 
        self.root = ie
1084
 
        self._byid = {self.root.file_id: self.root}
1085
 
 
1086
 
    def copy(self):
1087
 
        # TODO: jam 20051218 Should copy also copy the revision_id?
1088
 
        entries = self.iter_entries()
1089
 
        if self.root is None:
1090
 
            return Inventory(root_id=None)
1091
 
        other = Inventory(entries.next()[1].file_id)
1092
 
        other.root.revision = self.root.revision
1093
 
        # copy recursively so we know directories will be added before
1094
 
        # their children.  There are more efficient ways than this...
1095
 
        for path, entry in entries:
1096
 
            other.add(entry.copy())
1097
 
        return other
1098
 
 
1099
 
    def __iter__(self):
1100
 
        """Iterate over all file-ids."""
1101
 
        return iter(self._byid)
1102
 
 
1103
 
    def iter_just_entries(self):
1104
 
        """Iterate over all entries.
 
1002
        descend(self.root, u'')
 
1003
        return accum
 
1004
 
 
1005
    def directories(self):
 
1006
        """Return (path, entry) pairs for all directories, including the root.
 
1007
        """
 
1008
        accum = []
 
1009
        def descend(parent_ie, parent_path):
 
1010
            accum.append((parent_path, parent_ie))
 
1011
            
 
1012
            kids = [(ie.name, ie) for ie in parent_ie.children.itervalues() if ie.kind == 'directory']
 
1013
            kids.sort()
 
1014
 
 
1015
            for name, child_ie in kids:
 
1016
                child_path = osutils.pathjoin(parent_path, name)
 
1017
                descend(child_ie, child_path)
 
1018
        descend(self.root, u'')
 
1019
        return accum
1105
1020
        
1106
 
        Unlike iter_entries(), just the entries are returned (not (path, ie))
1107
 
        and the order of entries is undefined.
 
1021
    def __contains__(self, file_id):
 
1022
        """True if this entry contains a file with given id.
1108
1023
 
1109
 
        XXX: We may not want to merge this into bzr.dev.
 
1024
        >>> inv = Inventory()
 
1025
        >>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
 
1026
        InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
1027
        >>> '123' in inv
 
1028
        True
 
1029
        >>> '456' in inv
 
1030
        False
1110
1031
        """
1111
 
        if self.root is None:
1112
 
            return
1113
 
        for _, ie in self._byid.iteritems():
1114
 
            yield ie
1115
 
 
1116
 
    def __len__(self):
1117
 
        """Returns number of entries."""
1118
 
        return len(self._byid)
 
1032
        return (file_id in self._byid)
1119
1033
 
1120
1034
    def __getitem__(self, file_id):
1121
1035
        """Return the entry for given file_id.
1122
1036
 
1123
1037
        >>> inv = Inventory()
1124
1038
        >>> inv.add(InventoryFile('123123', 'hello.c', ROOT_ID))
1125
 
        InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
 
1039
        InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
1126
1040
        >>> inv['123123'].name
1127
1041
        'hello.c'
1128
1042
        """
1141
1055
    def _add_child(self, entry):
1142
1056
        """Add an entry to the inventory, without adding it to its parent"""
1143
1057
        if entry.file_id in self._byid:
1144
 
            raise errors.BzrError(
1145
 
                "inventory already contains entry with id {%s}" %
1146
 
                entry.file_id)
 
1058
            raise BzrError("inventory already contains entry with id {%s}" %
 
1059
                           entry.file_id)
1147
1060
        self._byid[entry.file_id] = entry
1148
1061
        for child in getattr(entry, 'children', {}).itervalues():
1149
1062
            self._add_child(child)
1152
1065
    def add(self, entry):
1153
1066
        """Add entry to inventory.
1154
1067
 
1155
 
        :return: entry
 
1068
        To add  a file to a branch ready to be committed, use Branch.add,
 
1069
        which calls this.
 
1070
 
 
1071
        Returns the new entry object.
1156
1072
        """
1157
1073
        if entry.file_id in self._byid:
1158
1074
            raise errors.DuplicateFileId(entry.file_id,
1159
1075
                                         self._byid[entry.file_id])
 
1076
 
1160
1077
        if entry.parent_id is None:
1161
1078
            self.root = entry
1162
1079
        else:
1163
1080
            try:
1164
1081
                parent = self._byid[entry.parent_id]
1165
1082
            except KeyError:
1166
 
                raise errors.InconsistentDelta("<unknown>", entry.parent_id,
1167
 
                    "Parent not in inventory.")
 
1083
                raise BzrError("parent_id {%s} not in inventory" %
 
1084
                               entry.parent_id)
 
1085
 
1168
1086
            if entry.name in parent.children:
1169
 
                raise errors.InconsistentDelta(
1170
 
                    self.id2path(parent.children[entry.name].file_id),
1171
 
                    entry.file_id,
1172
 
                    "Path already versioned")
 
1087
                raise BzrError("%s is already versioned" %
 
1088
                        osutils.pathjoin(self.id2path(parent.file_id),
 
1089
                        entry.name).encode('utf-8'))
1173
1090
            parent.children[entry.name] = entry
1174
1091
        return self._add_child(entry)
1175
1092
 
1179
1096
        The immediate parent must already be versioned.
1180
1097
 
1181
1098
        Returns the new entry object."""
1182
 
 
 
1099
        
1183
1100
        parts = osutils.splitpath(relpath)
1184
1101
 
1185
1102
        if len(parts) == 0:
1201
1118
 
1202
1119
        >>> inv = Inventory()
1203
1120
        >>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
1204
 
        InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1205
 
        >>> inv.has_id('123')
 
1121
        InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
1122
        >>> '123' in inv
1206
1123
        True
1207
1124
        >>> del inv['123']
1208
 
        >>> inv.has_id('123')
 
1125
        >>> '123' in inv
1209
1126
        False
1210
1127
        """
1211
1128
        ie = self[file_id]
1221
1138
        >>> i1 == i2
1222
1139
        True
1223
1140
        >>> i1.add(InventoryFile('123', 'foo', ROOT_ID))
1224
 
        InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
 
1141
        InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None)
1225
1142
        >>> i1 == i2
1226
1143
        False
1227
1144
        >>> i2.add(InventoryFile('123', 'foo', ROOT_ID))
1228
 
        InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
 
1145
        InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None)
1229
1146
        >>> i1 == i2
1230
1147
        True
1231
1148
        """
1250
1167
            yield ie
1251
1168
            file_id = ie.parent_id
1252
1169
 
 
1170
    def get_idpath(self, file_id):
 
1171
        """Return a list of file_ids for the path to an entry.
 
1172
 
 
1173
        The list contains one element for each directory followed by
 
1174
        the id of the file itself.  So the length of the returned list
 
1175
        is equal to the depth of the file in the tree, counting the
 
1176
        root directory as depth 1.
 
1177
        """
 
1178
        p = []
 
1179
        for parent in self._iter_file_id_parents(file_id):
 
1180
            p.insert(0, parent.file_id)
 
1181
        return p
 
1182
 
 
1183
    def id2path(self, file_id):
 
1184
        """Return as a string the path to file_id.
 
1185
        
 
1186
        >>> i = Inventory()
 
1187
        >>> e = i.add(InventoryDirectory('src-id', 'src', ROOT_ID))
 
1188
        >>> e = i.add(InventoryFile('foo-id', 'foo.c', parent_id='src-id'))
 
1189
        >>> print i.id2path('foo-id')
 
1190
        src/foo.c
 
1191
        """
 
1192
        # get all names, skipping root
 
1193
        return '/'.join(reversed(
 
1194
            [parent.name for parent in 
 
1195
             self._iter_file_id_parents(file_id)][:-1]))
 
1196
            
 
1197
    def path2id(self, name):
 
1198
        """Walk down through directories to return entry of last component.
 
1199
 
 
1200
        names may be either a list of path components, or a single
 
1201
        string, in which case it is automatically split.
 
1202
 
 
1203
        This returns the entry of the last component in the path,
 
1204
        which may be either a file or a directory.
 
1205
 
 
1206
        Returns None IFF the path is not found.
 
1207
        """
 
1208
        if isinstance(name, basestring):
 
1209
            name = osutils.splitpath(name)
 
1210
 
 
1211
        # mutter("lookup path %r" % name)
 
1212
 
 
1213
        parent = self.root
 
1214
        if parent is None:
 
1215
            return None
 
1216
        for f in name:
 
1217
            try:
 
1218
                children = getattr(parent, 'children', None)
 
1219
                if children is None:
 
1220
                    return None
 
1221
                cie = children[f]
 
1222
                parent = cie
 
1223
            except KeyError:
 
1224
                # or raise an error?
 
1225
                return None
 
1226
 
 
1227
        return parent.file_id
 
1228
 
 
1229
    def has_filename(self, names):
 
1230
        return bool(self.path2id(names))
 
1231
 
1253
1232
    def has_id(self, file_id):
1254
1233
        return (file_id in self._byid)
1255
1234
 
1256
 
    def _make_delta(self, old):
1257
 
        """Make an inventory delta from two inventories."""
1258
 
        old_getter = getattr(old, '_byid', old)
1259
 
        new_getter = self._byid
1260
 
        old_ids = set(old_getter)
1261
 
        new_ids = set(new_getter)
1262
 
        adds = new_ids - old_ids
1263
 
        deletes = old_ids - new_ids
1264
 
        if not adds and not deletes:
1265
 
            common = new_ids
1266
 
        else:
1267
 
            common = old_ids.intersection(new_ids)
1268
 
        delta = []
1269
 
        for file_id in deletes:
1270
 
            delta.append((old.id2path(file_id), None, file_id, None))
1271
 
        for file_id in adds:
1272
 
            delta.append((None, self.id2path(file_id), file_id, self[file_id]))
1273
 
        for file_id in common:
1274
 
            new_ie = new_getter[file_id]
1275
 
            old_ie = old_getter[file_id]
1276
 
            # If xml_serializer returns the cached InventoryEntries (rather
1277
 
            # than always doing .copy()), inlining the 'is' check saves 2.7M
1278
 
            # calls to __eq__.  Under lsprof this saves 20s => 6s.
1279
 
            # It is a minor improvement without lsprof.
1280
 
            if old_ie is new_ie or old_ie == new_ie:
1281
 
                continue
1282
 
            else:
1283
 
                delta.append((old.id2path(file_id), self.id2path(file_id),
1284
 
                              file_id, new_ie))
1285
 
        return delta
1286
 
 
1287
1235
    def remove_recursive_id(self, file_id):
1288
1236
        """Remove file_id, and children, from the inventory.
1289
 
 
 
1237
        
1290
1238
        :param file_id: A file_id to remove.
1291
1239
        """
1292
1240
        to_find_delete = [self._byid[file_id]]
1313
1261
        """
1314
1262
        new_name = ensure_normalized_name(new_name)
1315
1263
        if not is_valid_name(new_name):
1316
 
            raise errors.BzrError("not an acceptable filename: %r" % new_name)
 
1264
            raise BzrError("not an acceptable filename: %r" % new_name)
1317
1265
 
1318
1266
        new_parent = self._byid[new_parent_id]
1319
1267
        if new_name in new_parent.children:
1320
 
            raise errors.BzrError("%r already exists in %r" %
1321
 
                (new_name, self.id2path(new_parent_id)))
 
1268
            raise BzrError("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
1322
1269
 
1323
1270
        new_parent_idpath = self.get_idpath(new_parent_id)
1324
1271
        if file_id in new_parent_idpath:
1325
 
            raise errors.BzrError(
1326
 
                "cannot move directory %r into a subdirectory of itself, %r"
 
1272
            raise BzrError("cannot move directory %r into a subdirectory of itself, %r"
1327
1273
                    % (self.id2path(file_id), self.id2path(new_parent_id)))
1328
1274
 
1329
1275
        file_ie = self._byid[file_id]
1333
1279
 
1334
1280
        del old_parent.children[file_ie.name]
1335
1281
        new_parent.children[new_name] = file_ie
1336
 
 
 
1282
        
1337
1283
        file_ie.name = new_name
1338
1284
        file_ie.parent_id = new_parent_id
1339
1285
 
1341
1287
        return self.root is not None and file_id == self.root.file_id
1342
1288
 
1343
1289
 
1344
 
class CHKInventory(CommonInventory):
1345
 
    """An inventory persisted in a CHK store.
1346
 
 
1347
 
    By design, a CHKInventory is immutable so many of the methods
1348
 
    supported by Inventory - add, rename, apply_delta, etc - are *not*
1349
 
    supported. To create a new CHKInventory, use create_by_apply_delta()
1350
 
    or from_inventory(), say.
1351
 
 
1352
 
    Internally, a CHKInventory has one or two CHKMaps:
1353
 
 
1354
 
    * id_to_entry - a map from (file_id,) => InventoryEntry as bytes
1355
 
    * parent_id_basename_to_file_id - a map from (parent_id, basename_utf8)
1356
 
        => file_id as bytes
1357
 
 
1358
 
    The second map is optional and not present in early CHkRepository's.
1359
 
 
1360
 
    No caching is performed: every method call or item access will perform
1361
 
    requests to the storage layer. As such, keep references to objects you
1362
 
    want to reuse.
1363
 
    """
1364
 
 
1365
 
    def __init__(self, search_key_name):
1366
 
        CommonInventory.__init__(self)
1367
 
        self._fileid_to_entry_cache = {}
1368
 
        self._fully_cached = False
1369
 
        self._path_to_fileid_cache = {}
1370
 
        self._search_key_name = search_key_name
1371
 
        self.root_id = None
1372
 
 
1373
 
    def __eq__(self, other):
1374
 
        """Compare two sets by comparing their contents."""
1375
 
        if not isinstance(other, CHKInventory):
1376
 
            return NotImplemented
1377
 
 
1378
 
        this_key = self.id_to_entry.key()
1379
 
        other_key = other.id_to_entry.key()
1380
 
        this_pid_key = self.parent_id_basename_to_file_id.key()
1381
 
        other_pid_key = other.parent_id_basename_to_file_id.key()
1382
 
        if None in (this_key, this_pid_key, other_key, other_pid_key):
1383
 
            return False
1384
 
        return this_key == other_key and this_pid_key == other_pid_key
1385
 
 
1386
 
    def _entry_to_bytes(self, entry):
1387
 
        """Serialise entry as a single bytestring.
1388
 
 
1389
 
        :param Entry: An inventory entry.
1390
 
        :return: A bytestring for the entry.
1391
 
 
1392
 
        The BNF:
1393
 
        ENTRY ::= FILE | DIR | SYMLINK | TREE
1394
 
        FILE ::= "file: " COMMON SEP SHA SEP SIZE SEP EXECUTABLE
1395
 
        DIR ::= "dir: " COMMON
1396
 
        SYMLINK ::= "symlink: " COMMON SEP TARGET_UTF8
1397
 
        TREE ::= "tree: " COMMON REFERENCE_REVISION
1398
 
        COMMON ::= FILE_ID SEP PARENT_ID SEP NAME_UTF8 SEP REVISION
1399
 
        SEP ::= "\n"
1400
 
        """
1401
 
        if entry.parent_id is not None:
1402
 
            parent_str = entry.parent_id
1403
 
        else:
1404
 
            parent_str = ''
1405
 
        name_str = entry.name.encode("utf8")
1406
 
        if entry.kind == 'file':
1407
 
            if entry.executable:
1408
 
                exec_str = "Y"
1409
 
            else:
1410
 
                exec_str = "N"
1411
 
            return "file: %s\n%s\n%s\n%s\n%s\n%d\n%s" % (
1412
 
                entry.file_id, parent_str, name_str, entry.revision,
1413
 
                entry.text_sha1, entry.text_size, exec_str)
1414
 
        elif entry.kind == 'directory':
1415
 
            return "dir: %s\n%s\n%s\n%s" % (
1416
 
                entry.file_id, parent_str, name_str, entry.revision)
1417
 
        elif entry.kind == 'symlink':
1418
 
            return "symlink: %s\n%s\n%s\n%s\n%s" % (
1419
 
                entry.file_id, parent_str, name_str, entry.revision,
1420
 
                entry.symlink_target.encode("utf8"))
1421
 
        elif entry.kind == 'tree-reference':
1422
 
            return "tree: %s\n%s\n%s\n%s\n%s" % (
1423
 
                entry.file_id, parent_str, name_str, entry.revision,
1424
 
                entry.reference_revision)
1425
 
        else:
1426
 
            raise ValueError("unknown kind %r" % entry.kind)
1427
 
 
1428
 
    def _expand_fileids_to_parents_and_children(self, file_ids):
1429
 
        """Give a more wholistic view starting with the given file_ids.
1430
 
 
1431
 
        For any file_id which maps to a directory, we will include all children
1432
 
        of that directory. We will also include all directories which are
1433
 
        parents of the given file_ids, but we will not include their children.
1434
 
 
1435
 
        eg:
1436
 
          /     # TREE_ROOT
1437
 
          foo/  # foo-id
1438
 
            baz # baz-id
1439
 
            frob/ # frob-id
1440
 
              fringle # fringle-id
1441
 
          bar/  # bar-id
1442
 
            bing # bing-id
1443
 
 
1444
 
        if given [foo-id] we will include
1445
 
            TREE_ROOT as interesting parents
1446
 
        and 
1447
 
            foo-id, baz-id, frob-id, fringle-id
1448
 
        As interesting ids.
1449
 
        """
1450
 
        interesting = set()
1451
 
        # TODO: Pre-pass over the list of fileids to see if anything is already
1452
 
        #       deserialized in self._fileid_to_entry_cache
1453
 
 
1454
 
        directories_to_expand = set()
1455
 
        children_of_parent_id = {}
1456
 
        # It is okay if some of the fileids are missing
1457
 
        for entry in self._getitems(file_ids):
1458
 
            if entry.kind == 'directory':
1459
 
                directories_to_expand.add(entry.file_id)
1460
 
            interesting.add(entry.parent_id)
1461
 
            children_of_parent_id.setdefault(entry.parent_id, set()
1462
 
                                             ).add(entry.file_id)
1463
 
 
1464
 
        # Now, interesting has all of the direct parents, but not the
1465
 
        # parents of those parents. It also may have some duplicates with
1466
 
        # specific_fileids
1467
 
        remaining_parents = interesting.difference(file_ids)
1468
 
        # When we hit the TREE_ROOT, we'll get an interesting parent of None,
1469
 
        # but we don't actually want to recurse into that
1470
 
        interesting.add(None) # this will auto-filter it in the loop
1471
 
        remaining_parents.discard(None) 
1472
 
        while remaining_parents:
1473
 
            next_parents = set()
1474
 
            for entry in self._getitems(remaining_parents):
1475
 
                next_parents.add(entry.parent_id)
1476
 
                children_of_parent_id.setdefault(entry.parent_id, set()
1477
 
                                                 ).add(entry.file_id)
1478
 
            # Remove any search tips we've already processed
1479
 
            remaining_parents = next_parents.difference(interesting)
1480
 
            interesting.update(remaining_parents)
1481
 
            # We should probably also .difference(directories_to_expand)
1482
 
        interesting.update(file_ids)
1483
 
        interesting.discard(None)
1484
 
        while directories_to_expand:
1485
 
            # Expand directories by looking in the
1486
 
            # parent_id_basename_to_file_id map
1487
 
            keys = [StaticTuple(f,).intern() for f in directories_to_expand]
1488
 
            directories_to_expand = set()
1489
 
            items = self.parent_id_basename_to_file_id.iteritems(keys)
1490
 
            next_file_ids = set([item[1] for item in items])
1491
 
            next_file_ids = next_file_ids.difference(interesting)
1492
 
            interesting.update(next_file_ids)
1493
 
            for entry in self._getitems(next_file_ids):
1494
 
                if entry.kind == 'directory':
1495
 
                    directories_to_expand.add(entry.file_id)
1496
 
                children_of_parent_id.setdefault(entry.parent_id, set()
1497
 
                                                 ).add(entry.file_id)
1498
 
        return interesting, children_of_parent_id
1499
 
 
1500
 
    def filter(self, specific_fileids):
1501
 
        """Get an inventory view filtered against a set of file-ids.
1502
 
 
1503
 
        Children of directories and parents are included.
1504
 
 
1505
 
        The result may or may not reference the underlying inventory
1506
 
        so it should be treated as immutable.
1507
 
        """
1508
 
        (interesting,
1509
 
         parent_to_children) = self._expand_fileids_to_parents_and_children(
1510
 
                                specific_fileids)
1511
 
        # There is some overlap here, but we assume that all interesting items
1512
 
        # are in the _fileid_to_entry_cache because we had to read them to
1513
 
        # determine if they were a dir we wanted to recurse, or just a file
1514
 
        # This should give us all the entries we'll want to add, so start
1515
 
        # adding
1516
 
        other = Inventory(self.root_id)
1517
 
        other.root.revision = self.root.revision
1518
 
        other.revision_id = self.revision_id
1519
 
        if not interesting or not parent_to_children:
1520
 
            # empty filter, or filtering entrys that don't exist
1521
 
            # (if even 1 existed, then we would have populated
1522
 
            # parent_to_children with at least the tree root.)
1523
 
            return other
1524
 
        cache = self._fileid_to_entry_cache
1525
 
        remaining_children = collections.deque(parent_to_children[self.root_id])
1526
 
        while remaining_children:
1527
 
            file_id = remaining_children.popleft()
1528
 
            ie = cache[file_id]
1529
 
            if ie.kind == 'directory':
1530
 
                ie = ie.copy() # We create a copy to depopulate the .children attribute
1531
 
            # TODO: depending on the uses of 'other' we should probably alwyas
1532
 
            #       '.copy()' to prevent someone from mutating other and
1533
 
            #       invaliding our internal cache
1534
 
            other.add(ie)
1535
 
            if file_id in parent_to_children:
1536
 
                remaining_children.extend(parent_to_children[file_id])
1537
 
        return other
1538
 
 
1539
 
    @staticmethod
1540
 
    def _bytes_to_utf8name_key(bytes):
1541
 
        """Get the file_id, revision_id key out of bytes."""
1542
 
        # We don't normally care about name, except for times when we want
1543
 
        # to filter out empty names because of non rich-root...
1544
 
        sections = bytes.split('\n')
1545
 
        kind, file_id = sections[0].split(': ')
1546
 
        return (sections[2], intern(file_id), intern(sections[3]))
1547
 
 
1548
 
    def _bytes_to_entry(self, bytes):
1549
 
        """Deserialise a serialised entry."""
1550
 
        sections = bytes.split('\n')
1551
 
        if sections[0].startswith("file: "):
1552
 
            result = InventoryFile(sections[0][6:],
1553
 
                sections[2].decode('utf8'),
1554
 
                sections[1])
1555
 
            result.text_sha1 = sections[4]
1556
 
            result.text_size = int(sections[5])
1557
 
            result.executable = sections[6] == "Y"
1558
 
        elif sections[0].startswith("dir: "):
1559
 
            result = CHKInventoryDirectory(sections[0][5:],
1560
 
                sections[2].decode('utf8'),
1561
 
                sections[1], self)
1562
 
        elif sections[0].startswith("symlink: "):
1563
 
            result = InventoryLink(sections[0][9:],
1564
 
                sections[2].decode('utf8'),
1565
 
                sections[1])
1566
 
            result.symlink_target = sections[4].decode('utf8')
1567
 
        elif sections[0].startswith("tree: "):
1568
 
            result = TreeReference(sections[0][6:],
1569
 
                sections[2].decode('utf8'),
1570
 
                sections[1])
1571
 
            result.reference_revision = sections[4]
1572
 
        else:
1573
 
            raise ValueError("Not a serialised entry %r" % bytes)
1574
 
        result.file_id = intern(result.file_id)
1575
 
        result.revision = intern(sections[3])
1576
 
        if result.parent_id == '':
1577
 
            result.parent_id = None
1578
 
        self._fileid_to_entry_cache[result.file_id] = result
1579
 
        return result
1580
 
 
1581
 
    def create_by_apply_delta(self, inventory_delta, new_revision_id,
1582
 
        propagate_caches=False):
1583
 
        """Create a new CHKInventory by applying inventory_delta to this one.
1584
 
 
1585
 
        See the inventory developers documentation for the theory behind
1586
 
        inventory deltas.
1587
 
 
1588
 
        :param inventory_delta: The inventory delta to apply. See
1589
 
            Inventory.apply_delta for details.
1590
 
        :param new_revision_id: The revision id of the resulting CHKInventory.
1591
 
        :param propagate_caches: If True, the caches for this inventory are
1592
 
          copied to and updated for the result.
1593
 
        :return: The new CHKInventory.
1594
 
        """
1595
 
        split = osutils.split
1596
 
        result = CHKInventory(self._search_key_name)
1597
 
        if propagate_caches:
1598
 
            # Just propagate the path-to-fileid cache for now
1599
 
            result._path_to_fileid_cache = dict(self._path_to_fileid_cache.iteritems())
1600
 
        search_key_func = chk_map.search_key_registry.get(self._search_key_name)
1601
 
        self.id_to_entry._ensure_root()
1602
 
        maximum_size = self.id_to_entry._root_node.maximum_size
1603
 
        result.revision_id = new_revision_id
1604
 
        result.id_to_entry = chk_map.CHKMap(
1605
 
            self.id_to_entry._store,
1606
 
            self.id_to_entry.key(),
1607
 
            search_key_func=search_key_func)
1608
 
        result.id_to_entry._ensure_root()
1609
 
        result.id_to_entry._root_node.set_maximum_size(maximum_size)
1610
 
        # Change to apply to the parent_id_basename delta. The dict maps
1611
 
        # (parent_id, basename) -> (old_key, new_value). We use a dict because
1612
 
        # when a path has its id replaced (e.g. the root is changed, or someone
1613
 
        # does bzr mv a b, bzr mv c a, we should output a single change to this
1614
 
        # map rather than two.
1615
 
        parent_id_basename_delta = {}
1616
 
        if self.parent_id_basename_to_file_id is not None:
1617
 
            result.parent_id_basename_to_file_id = chk_map.CHKMap(
1618
 
                self.parent_id_basename_to_file_id._store,
1619
 
                self.parent_id_basename_to_file_id.key(),
1620
 
                search_key_func=search_key_func)
1621
 
            result.parent_id_basename_to_file_id._ensure_root()
1622
 
            self.parent_id_basename_to_file_id._ensure_root()
1623
 
            result_p_id_root = result.parent_id_basename_to_file_id._root_node
1624
 
            p_id_root = self.parent_id_basename_to_file_id._root_node
1625
 
            result_p_id_root.set_maximum_size(p_id_root.maximum_size)
1626
 
            result_p_id_root._key_width = p_id_root._key_width
1627
 
        else:
1628
 
            result.parent_id_basename_to_file_id = None
1629
 
        result.root_id = self.root_id
1630
 
        id_to_entry_delta = []
1631
 
        # inventory_delta is only traversed once, so we just update the
1632
 
        # variable.
1633
 
        # Check for repeated file ids
1634
 
        inventory_delta = _check_delta_unique_ids(inventory_delta)
1635
 
        # Repeated old paths
1636
 
        inventory_delta = _check_delta_unique_old_paths(inventory_delta)
1637
 
        # Check for repeated new paths
1638
 
        inventory_delta = _check_delta_unique_new_paths(inventory_delta)
1639
 
        # Check for entries that don't match the fileid
1640
 
        inventory_delta = _check_delta_ids_match_entry(inventory_delta)
1641
 
        # Check for nonsense fileids
1642
 
        inventory_delta = _check_delta_ids_are_valid(inventory_delta)
1643
 
        # Check for new_path <-> entry consistency
1644
 
        inventory_delta = _check_delta_new_path_entry_both_or_None(
1645
 
            inventory_delta)
1646
 
        # All changed entries need to have their parents be directories and be
1647
 
        # at the right path. This set contains (path, id) tuples.
1648
 
        parents = set()
1649
 
        # When we delete an item, all the children of it must be either deleted
1650
 
        # or altered in their own right. As we batch process the change via
1651
 
        # CHKMap.apply_delta, we build a set of things to use to validate the
1652
 
        # delta.
1653
 
        deletes = set()
1654
 
        altered = set()
1655
 
        for old_path, new_path, file_id, entry in inventory_delta:
1656
 
            # file id changes
1657
 
            if new_path == '':
1658
 
                result.root_id = file_id
1659
 
            if new_path is None:
1660
 
                # Make a delete:
1661
 
                new_key = None
1662
 
                new_value = None
1663
 
                # Update caches
1664
 
                if propagate_caches:
1665
 
                    try:
1666
 
                        del result._path_to_fileid_cache[old_path]
1667
 
                    except KeyError:
1668
 
                        pass
1669
 
                deletes.add(file_id)
1670
 
            else:
1671
 
                new_key = StaticTuple(file_id,)
1672
 
                new_value = result._entry_to_bytes(entry)
1673
 
                # Update caches. It's worth doing this whether
1674
 
                # we're propagating the old caches or not.
1675
 
                result._path_to_fileid_cache[new_path] = file_id
1676
 
                parents.add((split(new_path)[0], entry.parent_id))
1677
 
            if old_path is None:
1678
 
                old_key = None
1679
 
            else:
1680
 
                old_key = StaticTuple(file_id,)
1681
 
                if self.id2path(file_id) != old_path:
1682
 
                    raise errors.InconsistentDelta(old_path, file_id,
1683
 
                        "Entry was at wrong other path %r." %
1684
 
                        self.id2path(file_id))
1685
 
                altered.add(file_id)
1686
 
            id_to_entry_delta.append(StaticTuple(old_key, new_key, new_value))
1687
 
            if result.parent_id_basename_to_file_id is not None:
1688
 
                # parent_id, basename changes
1689
 
                if old_path is None:
1690
 
                    old_key = None
1691
 
                else:
1692
 
                    old_entry = self[file_id]
1693
 
                    old_key = self._parent_id_basename_key(old_entry)
1694
 
                if new_path is None:
1695
 
                    new_key = None
1696
 
                    new_value = None
1697
 
                else:
1698
 
                    new_key = self._parent_id_basename_key(entry)
1699
 
                    new_value = file_id
1700
 
                # If the two keys are the same, the value will be unchanged
1701
 
                # as its always the file id for this entry.
1702
 
                if old_key != new_key:
1703
 
                    # Transform a change into explicit delete/add preserving
1704
 
                    # a possible match on the key from a different file id.
1705
 
                    if old_key is not None:
1706
 
                        parent_id_basename_delta.setdefault(
1707
 
                            old_key, [None, None])[0] = old_key
1708
 
                    if new_key is not None:
1709
 
                        parent_id_basename_delta.setdefault(
1710
 
                            new_key, [None, None])[1] = new_value
1711
 
        # validate that deletes are complete.
1712
 
        for file_id in deletes:
1713
 
            entry = self[file_id]
1714
 
            if entry.kind != 'directory':
1715
 
                continue
1716
 
            # This loop could potentially be better by using the id_basename
1717
 
            # map to just get the child file ids.
1718
 
            for child in entry.children.values():
1719
 
                if child.file_id not in altered:
1720
 
                    raise errors.InconsistentDelta(self.id2path(child.file_id),
1721
 
                        child.file_id, "Child not deleted or reparented when "
1722
 
                        "parent deleted.")
1723
 
        result.id_to_entry.apply_delta(id_to_entry_delta)
1724
 
        if parent_id_basename_delta:
1725
 
            # Transform the parent_id_basename delta data into a linear delta
1726
 
            # with only one record for a given key. Optimally this would allow
1727
 
            # re-keying, but its simpler to just output that as a delete+add
1728
 
            # to spend less time calculating the delta.
1729
 
            delta_list = []
1730
 
            for key, (old_key, value) in parent_id_basename_delta.iteritems():
1731
 
                if value is not None:
1732
 
                    delta_list.append((old_key, key, value))
1733
 
                else:
1734
 
                    delta_list.append((old_key, None, None))
1735
 
            result.parent_id_basename_to_file_id.apply_delta(delta_list)
1736
 
        parents.discard(('', None))
1737
 
        for parent_path, parent in parents:
1738
 
            try:
1739
 
                if result[parent].kind != 'directory':
1740
 
                    raise errors.InconsistentDelta(result.id2path(parent), parent,
1741
 
                        'Not a directory, but given children')
1742
 
            except errors.NoSuchId:
1743
 
                raise errors.InconsistentDelta("<unknown>", parent,
1744
 
                    "Parent is not present in resulting inventory.")
1745
 
            if result.path2id(parent_path) != parent:
1746
 
                raise errors.InconsistentDelta(parent_path, parent,
1747
 
                    "Parent has wrong path %r." % result.path2id(parent_path))
1748
 
        return result
1749
 
 
1750
 
    @classmethod
1751
 
    def deserialise(klass, chk_store, bytes, expected_revision_id):
1752
 
        """Deserialise a CHKInventory.
1753
 
 
1754
 
        :param chk_store: A CHK capable VersionedFiles instance.
1755
 
        :param bytes: The serialised bytes.
1756
 
        :param expected_revision_id: The revision ID we think this inventory is
1757
 
            for.
1758
 
        :return: A CHKInventory
1759
 
        """
1760
 
        lines = bytes.split('\n')
1761
 
        if lines[-1] != '':
1762
 
            raise AssertionError('bytes to deserialize must end with an eol')
1763
 
        lines.pop()
1764
 
        if lines[0] != 'chkinventory:':
1765
 
            raise ValueError("not a serialised CHKInventory: %r" % bytes)
1766
 
        info = {}
1767
 
        allowed_keys = frozenset(['root_id', 'revision_id', 'search_key_name',
1768
 
                                  'parent_id_basename_to_file_id',
1769
 
                                  'id_to_entry'])
1770
 
        for line in lines[1:]:
1771
 
            key, value = line.split(': ', 1)
1772
 
            if key not in allowed_keys:
1773
 
                raise errors.BzrError('Unknown key in inventory: %r\n%r'
1774
 
                                      % (key, bytes))
1775
 
            if key in info:
1776
 
                raise errors.BzrError('Duplicate key in inventory: %r\n%r'
1777
 
                                      % (key, bytes))
1778
 
            info[key] = value
1779
 
        revision_id = intern(info['revision_id'])
1780
 
        root_id = intern(info['root_id'])
1781
 
        search_key_name = intern(info.get('search_key_name', 'plain'))
1782
 
        parent_id_basename_to_file_id = intern(info.get(
1783
 
            'parent_id_basename_to_file_id', None))
1784
 
        if not parent_id_basename_to_file_id.startswith('sha1:'):
1785
 
            raise ValueError('parent_id_basename_to_file_id should be a sha1'
1786
 
                             ' key not %r' % (parent_id_basename_to_file_id,))
1787
 
        id_to_entry = info['id_to_entry']
1788
 
        if not id_to_entry.startswith('sha1:'):
1789
 
            raise ValueError('id_to_entry should be a sha1'
1790
 
                             ' key not %r' % (id_to_entry,))
1791
 
 
1792
 
        result = CHKInventory(search_key_name)
1793
 
        result.revision_id = revision_id
1794
 
        result.root_id = root_id
1795
 
        search_key_func = chk_map.search_key_registry.get(
1796
 
                            result._search_key_name)
1797
 
        if parent_id_basename_to_file_id is not None:
1798
 
            result.parent_id_basename_to_file_id = chk_map.CHKMap(
1799
 
                chk_store, StaticTuple(parent_id_basename_to_file_id,),
1800
 
                search_key_func=search_key_func)
1801
 
        else:
1802
 
            result.parent_id_basename_to_file_id = None
1803
 
 
1804
 
        result.id_to_entry = chk_map.CHKMap(chk_store,
1805
 
                                            StaticTuple(id_to_entry,),
1806
 
                                            search_key_func=search_key_func)
1807
 
        if (result.revision_id,) != expected_revision_id:
1808
 
            raise ValueError("Mismatched revision id and expected: %r, %r" %
1809
 
                (result.revision_id, expected_revision_id))
1810
 
        return result
1811
 
 
1812
 
    @classmethod
1813
 
    def from_inventory(klass, chk_store, inventory, maximum_size=0, search_key_name='plain'):
1814
 
        """Create a CHKInventory from an existing inventory.
1815
 
 
1816
 
        The content of inventory is copied into the chk_store, and a
1817
 
        CHKInventory referencing that is returned.
1818
 
 
1819
 
        :param chk_store: A CHK capable VersionedFiles instance.
1820
 
        :param inventory: The inventory to copy.
1821
 
        :param maximum_size: The CHKMap node size limit.
1822
 
        :param search_key_name: The identifier for the search key function
1823
 
        """
1824
 
        result = klass(search_key_name)
1825
 
        result.revision_id = inventory.revision_id
1826
 
        result.root_id = inventory.root.file_id
1827
 
 
1828
 
        entry_to_bytes = result._entry_to_bytes
1829
 
        parent_id_basename_key = result._parent_id_basename_key
1830
 
        id_to_entry_dict = {}
1831
 
        parent_id_basename_dict = {}
1832
 
        for path, entry in inventory.iter_entries():
1833
 
            key = StaticTuple(entry.file_id,).intern()
1834
 
            id_to_entry_dict[key] = entry_to_bytes(entry)
1835
 
            p_id_key = parent_id_basename_key(entry)
1836
 
            parent_id_basename_dict[p_id_key] = entry.file_id
1837
 
 
1838
 
        result._populate_from_dicts(chk_store, id_to_entry_dict,
1839
 
            parent_id_basename_dict, maximum_size=maximum_size)
1840
 
        return result
1841
 
 
1842
 
    def _populate_from_dicts(self, chk_store, id_to_entry_dict,
1843
 
                             parent_id_basename_dict, maximum_size):
1844
 
        search_key_func = chk_map.search_key_registry.get(self._search_key_name)
1845
 
        root_key = chk_map.CHKMap.from_dict(chk_store, id_to_entry_dict,
1846
 
                   maximum_size=maximum_size, key_width=1,
1847
 
                   search_key_func=search_key_func)
1848
 
        self.id_to_entry = chk_map.CHKMap(chk_store, root_key,
1849
 
                                          search_key_func)
1850
 
        root_key = chk_map.CHKMap.from_dict(chk_store,
1851
 
                   parent_id_basename_dict,
1852
 
                   maximum_size=maximum_size, key_width=2,
1853
 
                   search_key_func=search_key_func)
1854
 
        self.parent_id_basename_to_file_id = chk_map.CHKMap(chk_store,
1855
 
                                                    root_key, search_key_func)
1856
 
 
1857
 
    def _parent_id_basename_key(self, entry):
1858
 
        """Create a key for a entry in a parent_id_basename_to_file_id index."""
1859
 
        if entry.parent_id is not None:
1860
 
            parent_id = entry.parent_id
1861
 
        else:
1862
 
            parent_id = ''
1863
 
        return StaticTuple(parent_id, entry.name.encode('utf8')).intern()
1864
 
 
1865
 
    def __getitem__(self, file_id):
1866
 
        """map a single file_id -> InventoryEntry."""
1867
 
        if file_id is None:
1868
 
            raise errors.NoSuchId(self, file_id)
1869
 
        result = self._fileid_to_entry_cache.get(file_id, None)
1870
 
        if result is not None:
1871
 
            return result
1872
 
        try:
1873
 
            return self._bytes_to_entry(
1874
 
                self.id_to_entry.iteritems([StaticTuple(file_id,)]).next()[1])
1875
 
        except StopIteration:
1876
 
            # really we're passing an inventory, not a tree...
1877
 
            raise errors.NoSuchId(self, file_id)
1878
 
 
1879
 
    def _getitems(self, file_ids):
1880
 
        """Similar to __getitem__, but lets you query for multiple.
1881
 
        
1882
 
        The returned order is undefined. And currently if an item doesn't
1883
 
        exist, it isn't included in the output.
1884
 
        """
1885
 
        result = []
1886
 
        remaining = []
1887
 
        for file_id in file_ids:
1888
 
            entry = self._fileid_to_entry_cache.get(file_id, None)
1889
 
            if entry is None:
1890
 
                remaining.append(file_id)
1891
 
            else:
1892
 
                result.append(entry)
1893
 
        file_keys = [StaticTuple(f,).intern() for f in remaining]
1894
 
        for file_key, value in self.id_to_entry.iteritems(file_keys):
1895
 
            entry = self._bytes_to_entry(value)
1896
 
            result.append(entry)
1897
 
            self._fileid_to_entry_cache[entry.file_id] = entry
1898
 
        return result
1899
 
 
1900
 
    def has_id(self, file_id):
1901
 
        # Perhaps have an explicit 'contains' method on CHKMap ?
1902
 
        if self._fileid_to_entry_cache.get(file_id, None) is not None:
1903
 
            return True
1904
 
        return len(list(
1905
 
            self.id_to_entry.iteritems([StaticTuple(file_id,)]))) == 1
1906
 
 
1907
 
    def is_root(self, file_id):
1908
 
        return file_id == self.root_id
1909
 
 
1910
 
    def _iter_file_id_parents(self, file_id):
1911
 
        """Yield the parents of file_id up to the root."""
1912
 
        while file_id is not None:
1913
 
            try:
1914
 
                ie = self[file_id]
1915
 
            except KeyError:
1916
 
                raise errors.NoSuchId(tree=self, file_id=file_id)
1917
 
            yield ie
1918
 
            file_id = ie.parent_id
1919
 
 
1920
 
    def __iter__(self):
1921
 
        """Iterate over all file-ids."""
1922
 
        for key, _ in self.id_to_entry.iteritems():
1923
 
            yield key[-1]
1924
 
 
1925
 
    def iter_just_entries(self):
1926
 
        """Iterate over all entries.
1927
 
 
1928
 
        Unlike iter_entries(), just the entries are returned (not (path, ie))
1929
 
        and the order of entries is undefined.
1930
 
 
1931
 
        XXX: We may not want to merge this into bzr.dev.
1932
 
        """
1933
 
        for key, entry in self.id_to_entry.iteritems():
1934
 
            file_id = key[0]
1935
 
            ie = self._fileid_to_entry_cache.get(file_id, None)
1936
 
            if ie is None:
1937
 
                ie = self._bytes_to_entry(entry)
1938
 
                self._fileid_to_entry_cache[file_id] = ie
1939
 
            yield ie
1940
 
 
1941
 
    def _preload_cache(self):
1942
 
        """Make sure all file-ids are in _fileid_to_entry_cache"""
1943
 
        if self._fully_cached:
1944
 
            return # No need to do it again
1945
 
        # The optimal sort order is to use iteritems() directly
1946
 
        cache = self._fileid_to_entry_cache
1947
 
        for key, entry in self.id_to_entry.iteritems():
1948
 
            file_id = key[0]
1949
 
            if file_id not in cache:
1950
 
                ie = self._bytes_to_entry(entry)
1951
 
                cache[file_id] = ie
1952
 
            else:
1953
 
                ie = cache[file_id]
1954
 
        last_parent_id = last_parent_ie = None
1955
 
        pid_items = self.parent_id_basename_to_file_id.iteritems()
1956
 
        for key, child_file_id in pid_items:
1957
 
            if key == ('', ''): # This is the root
1958
 
                if child_file_id != self.root_id:
1959
 
                    raise ValueError('Data inconsistency detected.'
1960
 
                        ' We expected data with key ("","") to match'
1961
 
                        ' the root id, but %s != %s'
1962
 
                        % (child_file_id, self.root_id))
1963
 
                continue
1964
 
            parent_id, basename = key
1965
 
            ie = cache[child_file_id]
1966
 
            if parent_id == last_parent_id:
1967
 
                parent_ie = last_parent_ie
1968
 
            else:
1969
 
                parent_ie = cache[parent_id]
1970
 
            if parent_ie.kind != 'directory':
1971
 
                raise ValueError('Data inconsistency detected.'
1972
 
                    ' An entry in the parent_id_basename_to_file_id map'
1973
 
                    ' has parent_id {%s} but the kind of that object'
1974
 
                    ' is %r not "directory"' % (parent_id, parent_ie.kind))
1975
 
            if parent_ie._children is None:
1976
 
                parent_ie._children = {}
1977
 
            basename = basename.decode('utf-8')
1978
 
            if basename in parent_ie._children:
1979
 
                existing_ie = parent_ie._children[basename]
1980
 
                if existing_ie != ie:
1981
 
                    raise ValueError('Data inconsistency detected.'
1982
 
                        ' Two entries with basename %r were found'
1983
 
                        ' in the parent entry {%s}'
1984
 
                        % (basename, parent_id))
1985
 
            if basename != ie.name:
1986
 
                raise ValueError('Data inconsistency detected.'
1987
 
                    ' In the parent_id_basename_to_file_id map, file_id'
1988
 
                    ' {%s} is listed as having basename %r, but in the'
1989
 
                    ' id_to_entry map it is %r'
1990
 
                    % (child_file_id, basename, ie.name))
1991
 
            parent_ie._children[basename] = ie
1992
 
        self._fully_cached = True
1993
 
 
1994
 
    def iter_changes(self, basis):
1995
 
        """Generate a Tree.iter_changes change list between this and basis.
1996
 
 
1997
 
        :param basis: Another CHKInventory.
1998
 
        :return: An iterator over the changes between self and basis, as per
1999
 
            tree.iter_changes().
2000
 
        """
2001
 
        # We want: (file_id, (path_in_source, path_in_target),
2002
 
        # changed_content, versioned, parent, name, kind,
2003
 
        # executable)
2004
 
        for key, basis_value, self_value in \
2005
 
            self.id_to_entry.iter_changes(basis.id_to_entry):
2006
 
            file_id = key[0]
2007
 
            if basis_value is not None:
2008
 
                basis_entry = basis._bytes_to_entry(basis_value)
2009
 
                path_in_source = basis.id2path(file_id)
2010
 
                basis_parent = basis_entry.parent_id
2011
 
                basis_name = basis_entry.name
2012
 
                basis_executable = basis_entry.executable
2013
 
            else:
2014
 
                path_in_source = None
2015
 
                basis_parent = None
2016
 
                basis_name = None
2017
 
                basis_executable = None
2018
 
            if self_value is not None:
2019
 
                self_entry = self._bytes_to_entry(self_value)
2020
 
                path_in_target = self.id2path(file_id)
2021
 
                self_parent = self_entry.parent_id
2022
 
                self_name = self_entry.name
2023
 
                self_executable = self_entry.executable
2024
 
            else:
2025
 
                path_in_target = None
2026
 
                self_parent = None
2027
 
                self_name = None
2028
 
                self_executable = None
2029
 
            if basis_value is None:
2030
 
                # add
2031
 
                kind = (None, self_entry.kind)
2032
 
                versioned = (False, True)
2033
 
            elif self_value is None:
2034
 
                # delete
2035
 
                kind = (basis_entry.kind, None)
2036
 
                versioned = (True, False)
2037
 
            else:
2038
 
                kind = (basis_entry.kind, self_entry.kind)
2039
 
                versioned = (True, True)
2040
 
            changed_content = False
2041
 
            if kind[0] != kind[1]:
2042
 
                changed_content = True
2043
 
            elif kind[0] == 'file':
2044
 
                if (self_entry.text_size != basis_entry.text_size or
2045
 
                    self_entry.text_sha1 != basis_entry.text_sha1):
2046
 
                    changed_content = True
2047
 
            elif kind[0] == 'symlink':
2048
 
                if self_entry.symlink_target != basis_entry.symlink_target:
2049
 
                    changed_content = True
2050
 
            elif kind[0] == 'tree-reference':
2051
 
                if (self_entry.reference_revision !=
2052
 
                    basis_entry.reference_revision):
2053
 
                    changed_content = True
2054
 
            parent = (basis_parent, self_parent)
2055
 
            name = (basis_name, self_name)
2056
 
            executable = (basis_executable, self_executable)
2057
 
            if (not changed_content
2058
 
                and parent[0] == parent[1]
2059
 
                and name[0] == name[1]
2060
 
                and executable[0] == executable[1]):
2061
 
                # Could happen when only the revision changed for a directory
2062
 
                # for instance.
2063
 
                continue
2064
 
            yield (file_id, (path_in_source, path_in_target), changed_content,
2065
 
                versioned, parent, name, kind, executable)
2066
 
 
2067
 
    def __len__(self):
2068
 
        """Return the number of entries in the inventory."""
2069
 
        return len(self.id_to_entry)
2070
 
 
2071
 
    def _make_delta(self, old):
2072
 
        """Make an inventory delta from two inventories."""
2073
 
        if type(old) != CHKInventory:
2074
 
            return CommonInventory._make_delta(self, old)
2075
 
        delta = []
2076
 
        for key, old_value, self_value in \
2077
 
            self.id_to_entry.iter_changes(old.id_to_entry):
2078
 
            file_id = key[0]
2079
 
            if old_value is not None:
2080
 
                old_path = old.id2path(file_id)
2081
 
            else:
2082
 
                old_path = None
2083
 
            if self_value is not None:
2084
 
                entry = self._bytes_to_entry(self_value)
2085
 
                self._fileid_to_entry_cache[file_id] = entry
2086
 
                new_path = self.id2path(file_id)
2087
 
            else:
2088
 
                entry = None
2089
 
                new_path = None
2090
 
            delta.append((old_path, new_path, file_id, entry))
2091
 
        return delta
2092
 
 
2093
 
    def path2id(self, relpath):
2094
 
        """See CommonInventory.path2id()."""
2095
 
        # TODO: perhaps support negative hits?
2096
 
        if isinstance(relpath, basestring):
2097
 
            names = osutils.splitpath(relpath)
2098
 
        else:
2099
 
            names = relpath
2100
 
            if relpath == []:
2101
 
                relpath = [""]
2102
 
            relpath = osutils.pathjoin(*relpath)
2103
 
        result = self._path_to_fileid_cache.get(relpath, None)
2104
 
        if result is not None:
2105
 
            return result
2106
 
        current_id = self.root_id
2107
 
        if current_id is None:
2108
 
            return None
2109
 
        parent_id_index = self.parent_id_basename_to_file_id
2110
 
        cur_path = None
2111
 
        for basename in names:
2112
 
            if cur_path is None:
2113
 
                cur_path = basename
2114
 
            else:
2115
 
                cur_path = cur_path + '/' + basename
2116
 
            basename_utf8 = basename.encode('utf8')
2117
 
            file_id = self._path_to_fileid_cache.get(cur_path, None)
2118
 
            if file_id is None:
2119
 
                key_filter = [StaticTuple(current_id, basename_utf8)]
2120
 
                items = parent_id_index.iteritems(key_filter)
2121
 
                for (parent_id, name_utf8), file_id in items:
2122
 
                    if parent_id != current_id or name_utf8 != basename_utf8:
2123
 
                        raise errors.BzrError("corrupt inventory lookup! "
2124
 
                            "%r %r %r %r" % (parent_id, current_id, name_utf8,
2125
 
                            basename_utf8))
2126
 
                if file_id is None:
2127
 
                    return None
2128
 
                else:
2129
 
                    self._path_to_fileid_cache[cur_path] = file_id
2130
 
            current_id = file_id
2131
 
        return current_id
2132
 
 
2133
 
    def to_lines(self):
2134
 
        """Serialise the inventory to lines."""
2135
 
        lines = ["chkinventory:\n"]
2136
 
        if self._search_key_name != 'plain':
2137
 
            # custom ordering grouping things that don't change together
2138
 
            lines.append('search_key_name: %s\n' % (self._search_key_name,))
2139
 
            lines.append("root_id: %s\n" % self.root_id)
2140
 
            lines.append('parent_id_basename_to_file_id: %s\n' %
2141
 
                (self.parent_id_basename_to_file_id.key()[0],))
2142
 
            lines.append("revision_id: %s\n" % self.revision_id)
2143
 
            lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
2144
 
        else:
2145
 
            lines.append("revision_id: %s\n" % self.revision_id)
2146
 
            lines.append("root_id: %s\n" % self.root_id)
2147
 
            if self.parent_id_basename_to_file_id is not None:
2148
 
                lines.append('parent_id_basename_to_file_id: %s\n' %
2149
 
                    (self.parent_id_basename_to_file_id.key()[0],))
2150
 
            lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
2151
 
        return lines
2152
 
 
2153
 
    @property
2154
 
    def root(self):
2155
 
        """Get the root entry."""
2156
 
        return self[self.root_id]
2157
 
 
2158
 
 
2159
 
class CHKInventoryDirectory(InventoryDirectory):
2160
 
    """A directory in an inventory."""
2161
 
 
2162
 
    __slots__ = ['_children', '_chk_inventory']
2163
 
 
2164
 
    def __init__(self, file_id, name, parent_id, chk_inventory):
2165
 
        # Don't call InventoryDirectory.__init__ - it isn't right for this
2166
 
        # class.
2167
 
        InventoryEntry.__init__(self, file_id, name, parent_id)
2168
 
        self._children = None
2169
 
        self._chk_inventory = chk_inventory
2170
 
 
2171
 
    @property
2172
 
    def children(self):
2173
 
        """Access the list of children of this directory.
2174
 
 
2175
 
        With a parent_id_basename_to_file_id index, loads all the children,
2176
 
        without loads the entire index. Without is bad. A more sophisticated
2177
 
        proxy object might be nice, to allow partial loading of children as
2178
 
        well when specific names are accessed. (So path traversal can be
2179
 
        written in the obvious way but not examine siblings.).
2180
 
        """
2181
 
        if self._children is not None:
2182
 
            return self._children
2183
 
        # No longer supported
2184
 
        if self._chk_inventory.parent_id_basename_to_file_id is None:
2185
 
            raise AssertionError("Inventories without"
2186
 
                " parent_id_basename_to_file_id are no longer supported")
2187
 
        result = {}
2188
 
        # XXX: Todo - use proxy objects for the children rather than loading
2189
 
        # all when the attribute is referenced.
2190
 
        parent_id_index = self._chk_inventory.parent_id_basename_to_file_id
2191
 
        child_keys = set()
2192
 
        for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
2193
 
            key_filter=[StaticTuple(self.file_id,)]):
2194
 
            child_keys.add(StaticTuple(file_id,))
2195
 
        cached = set()
2196
 
        for file_id_key in child_keys:
2197
 
            entry = self._chk_inventory._fileid_to_entry_cache.get(
2198
 
                file_id_key[0], None)
2199
 
            if entry is not None:
2200
 
                result[entry.name] = entry
2201
 
                cached.add(file_id_key)
2202
 
        child_keys.difference_update(cached)
2203
 
        # populate; todo: do by name
2204
 
        id_to_entry = self._chk_inventory.id_to_entry
2205
 
        for file_id_key, bytes in id_to_entry.iteritems(child_keys):
2206
 
            entry = self._chk_inventory._bytes_to_entry(bytes)
2207
 
            result[entry.name] = entry
2208
 
            self._chk_inventory._fileid_to_entry_cache[file_id_key[0]] = entry
2209
 
        self._children = result
2210
 
        return result
2211
 
 
2212
1290
entry_factory = {
2213
1291
    'directory': InventoryDirectory,
2214
1292
    'file': InventoryFile,
2230
1308
    try:
2231
1309
        factory = entry_factory[kind]
2232
1310
    except KeyError:
2233
 
        raise errors.BadFileKindError(name, kind)
 
1311
        raise BzrError("unknown kind %r" % kind)
2234
1312
    return factory(file_id, name, parent_id)
2235
1313
 
2236
1314
 
2256
1334
    return name
2257
1335
 
2258
1336
 
2259
 
_NAME_RE = lazy_regex.lazy_compile(r'^[^/\\]+$')
 
1337
_NAME_RE = None
2260
1338
 
2261
1339
def is_valid_name(name):
 
1340
    global _NAME_RE
 
1341
    if _NAME_RE is None:
 
1342
        _NAME_RE = re.compile(r'^[^/\\]+$')
 
1343
        
2262
1344
    return bool(_NAME_RE.match(name))
2263
 
 
2264
 
 
2265
 
def _check_delta_unique_ids(delta):
2266
 
    """Decorate a delta and check that the file ids in it are unique.
2267
 
 
2268
 
    :return: A generator over delta.
2269
 
    """
2270
 
    ids = set()
2271
 
    for item in delta:
2272
 
        length = len(ids) + 1
2273
 
        ids.add(item[2])
2274
 
        if len(ids) != length:
2275
 
            raise errors.InconsistentDelta(item[0] or item[1], item[2],
2276
 
                "repeated file_id")
2277
 
        yield item
2278
 
 
2279
 
 
2280
 
def _check_delta_unique_new_paths(delta):
2281
 
    """Decorate a delta and check that the new paths in it are unique.
2282
 
 
2283
 
    :return: A generator over delta.
2284
 
    """
2285
 
    paths = set()
2286
 
    for item in delta:
2287
 
        length = len(paths) + 1
2288
 
        path = item[1]
2289
 
        if path is not None:
2290
 
            paths.add(path)
2291
 
            if len(paths) != length:
2292
 
                raise errors.InconsistentDelta(path, item[2], "repeated path")
2293
 
        yield item
2294
 
 
2295
 
 
2296
 
def _check_delta_unique_old_paths(delta):
2297
 
    """Decorate a delta and check that the old paths in it are unique.
2298
 
 
2299
 
    :return: A generator over delta.
2300
 
    """
2301
 
    paths = set()
2302
 
    for item in delta:
2303
 
        length = len(paths) + 1
2304
 
        path = item[0]
2305
 
        if path is not None:
2306
 
            paths.add(path)
2307
 
            if len(paths) != length:
2308
 
                raise errors.InconsistentDelta(path, item[2], "repeated path")
2309
 
        yield item
2310
 
 
2311
 
 
2312
 
def _check_delta_ids_are_valid(delta):
2313
 
    """Decorate a delta and check that the ids in it are valid.
2314
 
 
2315
 
    :return: A generator over delta.
2316
 
    """
2317
 
    for item in delta:
2318
 
        entry = item[3]
2319
 
        if item[2] is None:
2320
 
            raise errors.InconsistentDelta(item[0] or item[1], item[2],
2321
 
                "entry with file_id None %r" % entry)
2322
 
        if type(item[2]) != str:
2323
 
            raise errors.InconsistentDelta(item[0] or item[1], item[2],
2324
 
                "entry with non bytes file_id %r" % entry)
2325
 
        yield item
2326
 
 
2327
 
 
2328
 
def _check_delta_ids_match_entry(delta):
2329
 
    """Decorate a delta and check that the ids in it match the entry.file_id.
2330
 
 
2331
 
    :return: A generator over delta.
2332
 
    """
2333
 
    for item in delta:
2334
 
        entry = item[3]
2335
 
        if entry is not None:
2336
 
            if entry.file_id != item[2]:
2337
 
                raise errors.InconsistentDelta(item[0] or item[1], item[2],
2338
 
                    "mismatched id with %r" % entry)
2339
 
        yield item
2340
 
 
2341
 
 
2342
 
def _check_delta_new_path_entry_both_or_None(delta):
2343
 
    """Decorate a delta and check that the new_path and entry are paired.
2344
 
 
2345
 
    :return: A generator over delta.
2346
 
    """
2347
 
    for item in delta:
2348
 
        new_path = item[1]
2349
 
        entry = item[3]
2350
 
        if new_path is None and entry is not None:
2351
 
            raise errors.InconsistentDelta(item[0], item[1],
2352
 
                "Entry with no new_path")
2353
 
        if new_path is not None and entry is None:
2354
 
            raise errors.InconsistentDelta(new_path, item[1],
2355
 
                "new_path with no entry")
2356
 
        yield item
2357
 
 
2358
 
 
2359
 
def mutable_inventory_from_tree(tree):
2360
 
    """Create a new inventory that has the same contents as a specified tree.
2361
 
 
2362
 
    :param tree: Revision tree to create inventory from
2363
 
    """
2364
 
    entries = tree.iter_entries_by_dir()
2365
 
    inv = Inventory(None, tree.get_revision_id())
2366
 
    for path, inv_entry in entries:
2367
 
        inv.add(inv_entry.copy())
2368
 
    return inv