~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: John Arbash Meinel
  • Date: 2006-07-13 00:05:14 UTC
  • mfrom: (1861 +trunk)
  • mto: This revision was merged to the branch mainline in revision 1871.
  • Revision ID: john@arbash-meinel.com-20060713000514-aa62627aa0d4deb6
[merge] bzr.dev 1861

Show diffs side-by-side

added added

removed removed

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