/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

[merge] robertc's integration, updated tests to check for retcode=3

Show diffs side-by-side

added added

removed removed

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