~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Martin Pool
  • Date: 2005-03-15 05:19:54 UTC
  • Revision ID: mbp@sourcefrog.net-20050315051954-e4bdd6dfd26f8ecf
witty comment

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005, 2006 Canonical Ltd
2
 
#
 
1
#! /usr/bin/env python
 
2
# -*- coding: UTF-8 -*-
 
3
 
3
4
# This program is free software; you can redistribute it and/or modify
4
5
# it under the terms of the GNU General Public License as published by
5
6
# the Free Software Foundation; either version 2 of the License, or
6
7
# (at your option) any later version.
7
 
#
 
8
 
8
9
# This program is distributed in the hope that it will be useful,
9
10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
12
# GNU General Public License for more details.
12
 
#
 
13
 
13
14
# You should have received a copy of the GNU General Public License
14
15
# along with this program; if not, write to the Free Software
15
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
17
 
17
 
# FIXME: This refactoring of the workingtree code doesn't seem to keep 
18
 
# the WorkingTree's copy of the inventory in sync with the branch.  The
19
 
# branch modifies its working inventory when it does a commit to make
20
 
# missing files permanently removed.
21
 
 
22
 
# TODO: Maybe also keep the full path of the entry, and the children?
23
 
# But those depend on its position within a particular inventory, and
24
 
# it would be nice not to need to hold the backpointer here.
25
 
 
26
 
# This should really be an id randomly assigned when the tree is
27
 
# created, but it's not for now.
28
 
ROOT_ID = "TREE_ROOT"
29
 
 
30
 
 
31
 
import collections
32
 
import os.path
33
 
import re
34
 
import sys
35
 
import tarfile
36
 
import types
37
 
from warnings import warn
38
 
 
39
 
import bzrlib
40
 
from bzrlib import errors, osutils
41
 
from bzrlib.osutils import (pumpfile, quotefn, splitpath, joinpath,
42
 
                            pathjoin, sha_strings)
43
 
from bzrlib.errors import (NotVersionedError, InvalidEntryName,
44
 
                           BzrError, BzrCheckError, BinaryFile)
45
 
from bzrlib.trace import mutter
46
 
 
47
 
 
48
 
class InventoryEntry(object):
 
18
"""Inventories map files to their name in a revision."""
 
19
 
 
20
 
 
21
__copyright__ = "Copyright (C) 2005 Canonical Ltd."
 
22
__author__ = "Martin Pool <mbp@canonical.com>"
 
23
 
 
24
import sys, os.path, types
 
25
from sets import Set
 
26
 
 
27
try:
 
28
    from cElementTree import Element, ElementTree, SubElement
 
29
except ImportError:
 
30
    from elementtree.ElementTree import Element, ElementTree, SubElement
 
31
 
 
32
from xml import XMLMixin
 
33
from errors import bailout
 
34
from osutils import uuid, quotefn, splitpath, joinpath, appendpath
 
35
from trace import mutter
 
36
 
 
37
class InventoryEntry(XMLMixin):
49
38
    """Description of a versioned file.
50
39
 
51
40
    An InventoryEntry has the following fields, which are also
52
41
    present in the XML inventory-entry element:
53
42
 
54
 
    file_id
55
 
 
56
 
    name
57
 
        (within the parent directory)
58
 
 
59
 
    parent_id
60
 
        file_id of the parent directory, or ROOT_ID
61
 
 
62
 
    revision
63
 
        the revision_id in which this variation of this file was 
64
 
        introduced.
65
 
 
66
 
    executable
67
 
        Indicates that this file should be executable on systems
68
 
        that support it.
69
 
 
70
 
    text_sha1
71
 
        sha-1 of the text of the file
72
 
        
73
 
    text_size
74
 
        size in bytes of the text of the file
75
 
        
76
 
    (reading a version 4 tree created a text_id field.)
 
43
    * *file_id*
 
44
    * *name*: (only the basename within the directory, must not
 
45
      contain slashes)
 
46
    * *kind*: "directory" or "file"
 
47
    * *directory_id*: (if absent/null means the branch root directory)
 
48
    * *text_sha1*: only for files
 
49
    * *text_size*: in bytes, only for files 
 
50
    * *text_id*: identifier for the text version, only for files
 
51
 
 
52
    InventoryEntries can also exist inside a WorkingTree
 
53
    inventory, in which case they are not yet bound to a
 
54
    particular revision of the file.  In that case the text_sha1,
 
55
    text_size and text_id are absent.
 
56
 
77
57
 
78
58
    >>> i = Inventory()
79
59
    >>> i.path2id('')
80
 
    'TREE_ROOT'
81
 
    >>> i.add(InventoryDirectory('123', 'src', ROOT_ID))
82
 
    InventoryDirectory('123', 'src', parent_id='TREE_ROOT', revision=None)
83
 
    >>> i.add(InventoryFile('2323', 'hello.c', parent_id='123'))
84
 
    InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None)
85
 
    >>> shouldbe = {0: '', 1: 'src', 2: pathjoin('src','hello.c')}
86
 
    >>> for ix, j in enumerate(i.iter_entries()):
87
 
    ...   print (j[0] == shouldbe[ix], j[1])
 
60
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
 
61
    >>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))
 
62
    >>> for j in i.iter_entries():
 
63
    ...   print j
88
64
    ... 
89
 
    (True, InventoryDirectory('TREE_ROOT', '', parent_id=None, revision=None))
90
 
    (True, InventoryDirectory('123', 'src', parent_id='TREE_ROOT', revision=None))
91
 
    (True, InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None))
92
 
    >>> i.add(InventoryFile('2323', 'bye.c', '123'))
 
65
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
 
66
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
 
67
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
93
68
    Traceback (most recent call last):
94
69
    ...
95
 
    BzrError: inventory already contains entry with id {2323}
96
 
    >>> i.add(InventoryFile('2324', 'bye.c', '123'))
97
 
    InventoryFile('2324', 'bye.c', parent_id='123', sha1=None, len=None)
98
 
    >>> i.add(InventoryDirectory('2325', 'wibble', '123'))
99
 
    InventoryDirectory('2325', 'wibble', parent_id='123', revision=None)
 
70
    BzrError: ('inventory already contains entry with id {2323}', [])
 
71
    >>> i.add(InventoryEntry('2324', 'bye.c', parent_id='123'))
 
72
    >>> i.add(InventoryEntry('2325', 'wibble', parent_id='123', kind='directory'))
100
73
    >>> i.path2id('src/wibble')
101
74
    '2325'
102
75
    >>> '2325' in i
103
76
    True
104
 
    >>> i.add(InventoryFile('2326', 'wibble.c', '2325'))
105
 
    InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None)
 
77
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
106
78
    >>> i['2326']
107
 
    InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None)
108
 
    >>> for path, entry in i.iter_entries():
109
 
    ...     print path
110
 
    ...     assert i.path2id(path)
 
79
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
 
80
    >>> for j in i.iter_entries():
 
81
    ...     print j[0]
 
82
    ...     assert i.path2id(j[0])
111
83
    ... 
112
 
    <BLANKLINE>
113
84
    src
114
85
    src/bye.c
115
86
    src/hello.c
117
88
    src/wibble/wibble.c
118
89
    >>> i.id2path('2326')
119
90
    'src/wibble/wibble.c'
 
91
 
 
92
    :todo: Maybe also keep the full path of the entry, and the children?
 
93
           But those depend on its position within a particular inventory, and
 
94
           it would be nice not to need to hold the backpointer here.
120
95
    """
121
 
 
122
 
    # Constants returned by describe_change()
123
 
    #
124
 
    # TODO: These should probably move to some kind of FileChangeDescription 
125
 
    # class; that's like what's inside a TreeDelta but we want to be able to 
126
 
    # generate them just for one file at a time.
127
 
    RENAMED = 'renamed'
128
 
    MODIFIED_AND_RENAMED = 'modified and renamed'
129
 
    
130
 
    __slots__ = []
131
 
 
132
 
    def detect_changes(self, old_entry):
133
 
        """Return a (text_modified, meta_modified) from this to old_entry.
134
 
        
135
 
        _read_tree_state must have been called on self and old_entry prior to 
136
 
        calling detect_changes.
137
 
        """
138
 
        return False, False
139
 
 
140
 
    def diff(self, text_diff, from_label, tree, to_label, to_entry, to_tree,
141
 
             output_to, reverse=False):
142
 
        """Perform a diff from this to to_entry.
143
 
 
144
 
        text_diff will be used for textual difference calculation.
145
 
        This is a template method, override _diff in child classes.
146
 
        """
147
 
        self._read_tree_state(tree.id2path(self.file_id), tree)
148
 
        if to_entry:
149
 
            # cannot diff from one kind to another - you must do a removal
150
 
            # and an addif they do not match.
151
 
            assert self.kind == to_entry.kind
152
 
            to_entry._read_tree_state(to_tree.id2path(to_entry.file_id),
153
 
                                      to_tree)
154
 
        self._diff(text_diff, from_label, tree, to_label, to_entry, to_tree,
155
 
                   output_to, reverse)
156
 
 
157
 
    def _diff(self, text_diff, from_label, tree, to_label, to_entry, to_tree,
158
 
             output_to, reverse=False):
159
 
        """Perform a diff between two entries of the same kind."""
160
 
 
161
 
    def find_previous_heads(self, previous_inventories,
162
 
                            versioned_file_store,
163
 
                            transaction,
164
 
                            entry_vf=None):
165
 
        """Return the revisions and entries that directly precede this.
166
 
 
167
 
        Returned as a map from revision to inventory entry.
168
 
 
169
 
        This is a map containing the file revisions in all parents
170
 
        for which the file exists, and its revision is not a parent of
171
 
        any other. If the file is new, the set will be empty.
172
 
 
173
 
        :param versioned_file_store: A store where ancestry data on this
174
 
                                     file id can be queried.
175
 
        :param transaction: The transaction that queries to the versioned 
176
 
                            file store should be completed under.
177
 
        :param entry_vf: The entry versioned file, if its already available.
178
 
        """
179
 
        def get_ancestors(weave, entry):
180
 
            return set(weave.get_ancestry(entry.revision))
181
 
        # revision:ie mapping for each ie found in previous_inventories.
182
 
        candidates = {}
183
 
        # revision:ie mapping with one revision for each head.
184
 
        heads = {}
185
 
        # revision: ancestor list for each head
186
 
        head_ancestors = {}
187
 
        # identify candidate head revision ids.
188
 
        for inv in previous_inventories:
189
 
            if self.file_id in inv:
190
 
                ie = inv[self.file_id]
191
 
                assert ie.file_id == self.file_id
192
 
                if ie.revision in candidates:
193
 
                    # same revision value in two different inventories:
194
 
                    # correct possible inconsistencies:
195
 
                    #     * there was a bug in revision updates with 'x' bit 
196
 
                    #       support.
197
 
                    try:
198
 
                        if candidates[ie.revision].executable != ie.executable:
199
 
                            candidates[ie.revision].executable = False
200
 
                            ie.executable = False
201
 
                    except AttributeError:
202
 
                        pass
203
 
                    # must now be the same.
204
 
                    assert candidates[ie.revision] == ie
205
 
                else:
206
 
                    # add this revision as a candidate.
207
 
                    candidates[ie.revision] = ie
208
 
 
209
 
        # common case optimisation
210
 
        if len(candidates) == 1:
211
 
            # if there is only one candidate revision found
212
 
            # then we can opening the versioned file to access ancestry:
213
 
            # there cannot be any ancestors to eliminate when there is 
214
 
            # only one revision available.
215
 
            heads[ie.revision] = ie
216
 
            return heads
217
 
 
218
 
        # eliminate ancestors amongst the available candidates:
219
 
        # heads are those that are not an ancestor of any other candidate
220
 
        # - this provides convergence at a per-file level.
221
 
        for ie in candidates.values():
222
 
            # may be an ancestor of a known head:
223
 
            already_present = 0 != len(
224
 
                [head for head in heads 
225
 
                 if ie.revision in head_ancestors[head]])
226
 
            if already_present:
227
 
                # an ancestor of an analyzed candidate.
228
 
                continue
229
 
            # not an ancestor of a known head:
230
 
            # load the versioned file for this file id if needed
231
 
            if entry_vf is None:
232
 
                entry_vf = versioned_file_store.get_weave_or_empty(
233
 
                    self.file_id, transaction)
234
 
            ancestors = get_ancestors(entry_vf, ie)
235
 
            # may knock something else out:
236
 
            check_heads = list(heads.keys())
237
 
            for head in check_heads:
238
 
                if head in ancestors:
239
 
                    # this previously discovered 'head' is not
240
 
                    # really a head - its an ancestor of the newly 
241
 
                    # found head,
242
 
                    heads.pop(head)
243
 
            head_ancestors[ie.revision] = ancestors
244
 
            heads[ie.revision] = ie
245
 
        return heads
246
 
 
247
 
    def get_tar_item(self, root, dp, now, tree):
248
 
        """Get a tarfile item and a file stream for its content."""
249
 
        item = tarfile.TarInfo(pathjoin(root, dp))
250
 
        # TODO: would be cool to actually set it to the timestamp of the
251
 
        # revision it was last changed
252
 
        item.mtime = now
253
 
        fileobj = self._put_in_tar(item, tree)
254
 
        return item, fileobj
255
 
 
256
 
    def has_text(self):
257
 
        """Return true if the object this entry represents has textual data.
258
 
 
259
 
        Note that textual data includes binary content.
260
 
 
261
 
        Also note that all entries get weave files created for them.
262
 
        This attribute is primarily used when upgrading from old trees that
263
 
        did not have the weave index for all inventory entries.
264
 
        """
265
 
        return False
266
 
 
267
 
    def __init__(self, file_id, name, parent_id, text_id=None):
 
96
    def __init__(self, file_id, name, kind='file', text_id=None,
 
97
                 parent_id=None):
268
98
        """Create an InventoryEntry
269
99
        
270
100
        The filename must be a single component, relative to the
271
101
        parent directory; it cannot be a whole path or relative name.
272
102
 
273
 
        >>> e = InventoryFile('123', 'hello.c', ROOT_ID)
 
103
        >>> e = InventoryEntry('123', 'hello.c')
274
104
        >>> e.name
275
105
        'hello.c'
276
106
        >>> e.file_id
277
107
        '123'
278
 
        >>> e = InventoryFile('123', 'src/hello.c', ROOT_ID)
 
108
        >>> e = InventoryEntry('123', 'src/hello.c')
279
109
        Traceback (most recent call last):
280
 
        InvalidEntryName: Invalid entry name: src/hello.c
 
110
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
281
111
        """
282
 
        assert isinstance(name, basestring), name
283
 
        if '/' in name or '\\' in name:
284
 
            raise InvalidEntryName(name=name)
285
 
        self.executable = False
286
 
        self.revision = None
287
 
        self.text_sha1 = None
288
 
        self.text_size = None
 
112
        
 
113
        if len(splitpath(name)) != 1:
 
114
            bailout('InventoryEntry name is not a simple filename: %r'
 
115
                    % name)
 
116
        
289
117
        self.file_id = file_id
290
118
        self.name = name
 
119
        assert kind in ['file', 'directory']
 
120
        self.kind = kind
291
121
        self.text_id = text_id
292
122
        self.parent_id = parent_id
293
 
        self.symlink_target = None
294
 
 
295
 
    def kind_character(self):
296
 
        """Return a short kind indicator useful for appending to names."""
297
 
        raise BzrError('unknown kind %r' % self.kind)
298
 
 
299
 
    known_kinds = ('file', 'directory', 'symlink')
300
 
 
301
 
    def _put_in_tar(self, item, tree):
302
 
        """populate item for stashing in a tar, and return the content stream.
303
 
 
304
 
        If no content is available, return None.
305
 
        """
306
 
        raise BzrError("don't know how to export {%s} of kind %r" %
307
 
                       (self.file_id, self.kind))
308
 
 
309
 
    def put_on_disk(self, dest, dp, tree):
310
 
        """Create a representation of self on disk in the prefix dest.
311
 
        
312
 
        This is a template method - implement _put_on_disk in subclasses.
313
 
        """
314
 
        fullpath = pathjoin(dest, dp)
315
 
        self._put_on_disk(fullpath, tree)
316
 
        # mutter("  export {%s} kind %s to %s", self.file_id,
317
 
        #         self.kind, fullpath)
318
 
 
319
 
    def _put_on_disk(self, fullpath, tree):
320
 
        """Put this entry onto disk at fullpath, from tree tree."""
321
 
        raise BzrError("don't know how to export {%s} of kind %r" % (self.file_id, self.kind))
322
 
 
323
 
    def sorted_children(self):
324
 
        return sorted(self.children.items())
325
 
 
326
 
    @staticmethod
327
 
    def versionable_kind(kind):
328
 
        return kind in ('file', 'directory', 'symlink')
329
 
 
330
 
    def check(self, checker, rev_id, inv, tree):
331
 
        """Check this inventory entry is intact.
332
 
 
333
 
        This is a template method, override _check for kind specific
334
 
        tests.
335
 
 
336
 
        :param checker: Check object providing context for the checks; 
337
 
             can be used to find out what parts of the repository have already
338
 
             been checked.
339
 
        :param rev_id: Revision id from which this InventoryEntry was loaded.
340
 
             Not necessarily the last-changed revision for this file.
341
 
        :param inv: Inventory from which the entry was loaded.
342
 
        :param tree: RevisionTree for this entry.
343
 
        """
344
 
        if self.parent_id is not None:
345
 
            if not inv.has_id(self.parent_id):
346
 
                raise BzrCheckError('missing parent {%s} in inventory for revision {%s}'
347
 
                        % (self.parent_id, rev_id))
348
 
        self._check(checker, rev_id, tree)
349
 
 
350
 
    def _check(self, checker, rev_id, tree):
351
 
        """Check this inventory entry for kind specific errors."""
352
 
        raise BzrCheckError('unknown entry kind %r in revision {%s}' % 
353
 
                            (self.kind, rev_id))
354
 
 
355
 
    def copy(self):
356
 
        """Clone this inventory entry."""
357
 
        raise NotImplementedError
358
 
 
359
 
    @staticmethod
360
 
    def describe_change(old_entry, new_entry):
361
 
        """Describe the change between old_entry and this.
362
 
        
363
 
        This smells of being an InterInventoryEntry situation, but as its
364
 
        the first one, we're making it a static method for now.
365
 
 
366
 
        An entry with a different parent, or different name is considered 
367
 
        to be renamed. Reparenting is an internal detail.
368
 
        Note that renaming the parent does not trigger a rename for the
369
 
        child entry itself.
370
 
        """
371
 
        # TODO: Perhaps return an object rather than just a string
372
 
        if old_entry is new_entry:
373
 
            # also the case of both being None
374
 
            return 'unchanged'
375
 
        elif old_entry is None:
376
 
            return 'added'
377
 
        elif new_entry is None:
378
 
            return 'removed'
379
 
        text_modified, meta_modified = new_entry.detect_changes(old_entry)
380
 
        if text_modified or meta_modified:
381
 
            modified = True
382
 
        else:
383
 
            modified = False
384
 
        # TODO 20060511 (mbp, rbc) factor out 'detect_rename' here.
385
 
        if old_entry.parent_id != new_entry.parent_id:
386
 
            renamed = True
387
 
        elif old_entry.name != new_entry.name:
388
 
            renamed = True
389
 
        else:
390
 
            renamed = False
391
 
        if renamed and not modified:
392
 
            return InventoryEntry.RENAMED
393
 
        if modified and not renamed:
394
 
            return 'modified'
395
 
        if modified and renamed:
396
 
            return InventoryEntry.MODIFIED_AND_RENAMED
397
 
        return 'unchanged'
398
 
 
399
 
    def __repr__(self):
400
 
        return ("%s(%r, %r, parent_id=%r, revision=%r)"
401
 
                % (self.__class__.__name__,
402
 
                   self.file_id,
403
 
                   self.name,
404
 
                   self.parent_id,
405
 
                   self.revision))
406
 
 
407
 
    def snapshot(self, revision, path, previous_entries,
408
 
                 work_tree, commit_builder):
409
 
        """Make a snapshot of this entry which may or may not have changed.
410
 
        
411
 
        This means that all its fields are populated, that it has its
412
 
        text stored in the text store or weave.
413
 
        """
414
 
        # mutter('new parents of %s are %r', path, previous_entries)
415
 
        self._read_tree_state(path, work_tree)
416
 
        # TODO: Where should we determine whether to reuse a
417
 
        # previous revision id or create a new revision? 20060606
418
 
        if len(previous_entries) == 1:
419
 
            # cannot be unchanged unless there is only one parent file rev.
420
 
            parent_ie = previous_entries.values()[0]
421
 
            if self._unchanged(parent_ie):
422
 
                # mutter("found unchanged entry")
423
 
                self.revision = parent_ie.revision
424
 
                return "unchanged"
425
 
        return self._snapshot_into_revision(revision, previous_entries, 
426
 
                                            work_tree, commit_builder)
427
 
 
428
 
    def _snapshot_into_revision(self, revision, previous_entries, work_tree,
429
 
                                commit_builder):
430
 
        """Record this revision unconditionally into a store.
431
 
 
432
 
        The entry's last-changed revision property (`revision`) is updated to 
433
 
        that of the new revision.
434
 
        
435
 
        :param revision: id of the new revision that is being recorded.
436
 
 
437
 
        :returns: String description of the commit (e.g. "merged", "modified"), etc.
438
 
        """
439
 
        # mutter('new revision {%s} for {%s}', revision, self.file_id)
440
 
        self.revision = revision
441
 
        self._snapshot_text(previous_entries, work_tree, commit_builder)
442
 
 
443
 
    def _snapshot_text(self, file_parents, work_tree, commit_builder): 
444
 
        """Record the 'text' of this entry, whatever form that takes.
445
 
        
446
 
        This default implementation simply adds an empty text.
447
 
        """
448
 
        raise NotImplementedError(self._snapshot_text)
449
 
 
450
 
    def __eq__(self, other):
451
 
        if not isinstance(other, InventoryEntry):
452
 
            return NotImplemented
453
 
 
454
 
        return ((self.file_id == other.file_id)
455
 
                and (self.name == other.name)
456
 
                and (other.symlink_target == self.symlink_target)
457
 
                and (self.text_sha1 == other.text_sha1)
458
 
                and (self.text_size == other.text_size)
459
 
                and (self.text_id == other.text_id)
460
 
                and (self.parent_id == other.parent_id)
461
 
                and (self.kind == other.kind)
462
 
                and (self.revision == other.revision)
463
 
                and (self.executable == other.executable)
464
 
                )
465
 
 
466
 
    def __ne__(self, other):
467
 
        return not (self == other)
468
 
 
469
 
    def __hash__(self):
470
 
        raise ValueError('not hashable')
471
 
 
472
 
    def _unchanged(self, previous_ie):
473
 
        """Has this entry changed relative to previous_ie.
474
 
 
475
 
        This method should be overridden in child classes.
476
 
        """
477
 
        compatible = True
478
 
        # different inv parent
479
 
        if previous_ie.parent_id != self.parent_id:
480
 
            compatible = False
481
 
        # renamed
482
 
        elif previous_ie.name != self.name:
483
 
            compatible = False
484
 
        return compatible
485
 
 
486
 
    def _read_tree_state(self, path, work_tree):
487
 
        """Populate fields in the inventory entry from the given tree.
488
 
        
489
 
        Note that this should be modified to be a noop on virtual trees
490
 
        as all entries created there are prepopulated.
491
 
        """
492
 
        # TODO: Rather than running this manually, we should check the 
493
 
        # working sha1 and other expensive properties when they're
494
 
        # first requested, or preload them if they're already known
495
 
        pass            # nothing to do by default
496
 
 
497
 
    def _forget_tree_state(self):
498
 
        pass
499
 
 
500
 
 
501
 
class RootEntry(InventoryEntry):
502
 
 
503
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
504
 
                 'text_id', 'parent_id', 'children', 'executable', 
505
 
                 'revision', 'symlink_target']
506
 
 
507
 
    def _check(self, checker, rev_id, tree):
508
 
        """See InventoryEntry._check"""
509
 
 
510
 
    def __init__(self, file_id):
511
 
        self.file_id = file_id
512
 
        self.children = {}
513
 
        self.kind = 'directory'
514
 
        self.parent_id = None
515
 
        self.name = u''
516
 
        self.revision = None
517
 
        warn('RootEntry is deprecated as of bzr 0.10.  Please use '
518
 
             'InventoryDirectory instead.',
519
 
            DeprecationWarning, stacklevel=2)
520
 
 
521
 
    def __eq__(self, other):
522
 
        if not isinstance(other, RootEntry):
523
 
            return NotImplemented
524
 
        
525
 
        return (self.file_id == other.file_id) \
526
 
               and (self.children == other.children)
527
 
 
528
 
 
529
 
class InventoryDirectory(InventoryEntry):
530
 
    """A directory in an inventory."""
531
 
 
532
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
533
 
                 'text_id', 'parent_id', 'children', 'executable', 
534
 
                 'revision', 'symlink_target']
535
 
 
536
 
    def _check(self, checker, rev_id, tree):
537
 
        """See InventoryEntry._check"""
538
 
        if self.text_sha1 is not None or self.text_size is not None or self.text_id is not None:
539
 
            raise BzrCheckError('directory {%s} has text in revision {%s}'
540
 
                                % (self.file_id, rev_id))
541
 
 
542
 
    def copy(self):
543
 
        other = InventoryDirectory(self.file_id, self.name, self.parent_id)
544
 
        other.revision = self.revision
545
 
        # note that children are *not* copied; they're pulled across when
546
 
        # others are added
547
 
        return other
548
 
 
549
 
    def __init__(self, file_id, name, parent_id):
550
 
        super(InventoryDirectory, self).__init__(file_id, name, parent_id)
551
 
        self.children = {}
552
 
        self.kind = 'directory'
553
 
 
554
 
    def kind_character(self):
555
 
        """See InventoryEntry.kind_character."""
556
 
        return '/'
557
 
 
558
 
    def _put_in_tar(self, item, tree):
559
 
        """See InventoryEntry._put_in_tar."""
560
 
        item.type = tarfile.DIRTYPE
561
 
        fileobj = None
562
 
        item.name += '/'
563
 
        item.size = 0
564
 
        item.mode = 0755
565
 
        return fileobj
566
 
 
567
 
    def _put_on_disk(self, fullpath, tree):
568
 
        """See InventoryEntry._put_on_disk."""
569
 
        os.mkdir(fullpath)
570
 
 
571
 
    def _snapshot_text(self, file_parents, work_tree, commit_builder):
572
 
        """See InventoryEntry._snapshot_text."""
573
 
        commit_builder.modified_directory(self.file_id, file_parents)
574
 
 
575
 
 
576
 
class InventoryFile(InventoryEntry):
577
 
    """A file in an inventory."""
578
 
 
579
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
580
 
                 'text_id', 'parent_id', 'children', 'executable', 
581
 
                 'revision', 'symlink_target']
582
 
 
583
 
    def _check(self, checker, tree_revision_id, tree):
584
 
        """See InventoryEntry._check"""
585
 
        t = (self.file_id, self.revision)
586
 
        if t in checker.checked_texts:
587
 
            prev_sha = checker.checked_texts[t]
588
 
            if prev_sha != self.text_sha1:
589
 
                raise BzrCheckError('mismatched sha1 on {%s} in {%s}' %
590
 
                                    (self.file_id, tree_revision_id))
591
 
            else:
592
 
                checker.repeated_text_cnt += 1
593
 
                return
594
 
 
595
 
        if self.file_id not in checker.checked_weaves:
596
 
            mutter('check weave {%s}', self.file_id)
597
 
            w = tree.get_weave(self.file_id)
598
 
            # Not passing a progress bar, because it creates a new
599
 
            # progress, which overwrites the current progress,
600
 
            # and doesn't look nice
601
 
            w.check()
602
 
            checker.checked_weaves[self.file_id] = True
603
 
        else:
604
 
            w = tree.get_weave(self.file_id)
605
 
 
606
 
        mutter('check version {%s} of {%s}', tree_revision_id, self.file_id)
607
 
        checker.checked_text_cnt += 1
608
 
        # We can't check the length, because Weave doesn't store that
609
 
        # information, and the whole point of looking at the weave's
610
 
        # sha1sum is that we don't have to extract the text.
611
 
        if self.text_sha1 != w.get_sha1(self.revision):
612
 
            raise BzrCheckError('text {%s} version {%s} wrong sha1' 
613
 
                                % (self.file_id, self.revision))
614
 
        checker.checked_texts[t] = self.text_sha1
615
 
 
616
 
    def copy(self):
617
 
        other = InventoryFile(self.file_id, self.name, self.parent_id)
618
 
        other.executable = self.executable
619
 
        other.text_id = self.text_id
 
123
        self.text_sha1 = None
 
124
        self.text_size = None
 
125
 
 
126
 
 
127
    def copy(self):
 
128
        other = InventoryEntry(self.file_id, self.name, self.kind,
 
129
                               self.text_id, self.parent_id)
620
130
        other.text_sha1 = self.text_sha1
621
131
        other.text_size = self.text_size
622
 
        other.revision = self.revision
623
132
        return other
624
133
 
625
 
    def detect_changes(self, old_entry):
626
 
        """See InventoryEntry.detect_changes."""
627
 
        assert self.text_sha1 is not None
628
 
        assert old_entry.text_sha1 is not None
629
 
        text_modified = (self.text_sha1 != old_entry.text_sha1)
630
 
        meta_modified = (self.executable != old_entry.executable)
631
 
        return text_modified, meta_modified
632
 
 
633
 
    def _diff(self, text_diff, from_label, tree, to_label, to_entry, to_tree,
634
 
             output_to, reverse=False):
635
 
        """See InventoryEntry._diff."""
636
 
        try:
637
 
            from_text = tree.get_file(self.file_id).readlines()
638
 
            if to_entry:
639
 
                to_text = to_tree.get_file(to_entry.file_id).readlines()
640
 
            else:
641
 
                to_text = []
642
 
            if not reverse:
643
 
                text_diff(from_label, from_text,
644
 
                          to_label, to_text, output_to)
645
 
            else:
646
 
                text_diff(to_label, to_text,
647
 
                          from_label, from_text, output_to)
648
 
        except BinaryFile:
649
 
            if reverse:
650
 
                label_pair = (to_label, from_label)
651
 
            else:
652
 
                label_pair = (from_label, to_label)
653
 
            print >> output_to, "Binary files %s and %s differ" % label_pair
654
 
 
655
 
    def has_text(self):
656
 
        """See InventoryEntry.has_text."""
657
 
        return True
658
 
 
659
 
    def __init__(self, file_id, name, parent_id):
660
 
        super(InventoryFile, self).__init__(file_id, name, parent_id)
661
 
        self.kind = 'file'
662
 
 
663
 
    def kind_character(self):
664
 
        """See InventoryEntry.kind_character."""
665
 
        return ''
666
 
 
667
 
    def _put_in_tar(self, item, tree):
668
 
        """See InventoryEntry._put_in_tar."""
669
 
        item.type = tarfile.REGTYPE
670
 
        fileobj = tree.get_file(self.file_id)
671
 
        item.size = self.text_size
672
 
        if tree.is_executable(self.file_id):
673
 
            item.mode = 0755
674
 
        else:
675
 
            item.mode = 0644
676
 
        return fileobj
677
 
 
678
 
    def _put_on_disk(self, fullpath, tree):
679
 
        """See InventoryEntry._put_on_disk."""
680
 
        pumpfile(tree.get_file(self.file_id), file(fullpath, 'wb'))
681
 
        if tree.is_executable(self.file_id):
682
 
            os.chmod(fullpath, 0755)
683
 
 
684
 
    def _read_tree_state(self, path, work_tree):
685
 
        """See InventoryEntry._read_tree_state."""
686
 
        self.text_sha1 = work_tree.get_file_sha1(self.file_id, path=path)
687
 
        # FIXME: 20050930 probe for the text size when getting sha1
688
 
        # in _read_tree_state
689
 
        self.executable = work_tree.is_executable(self.file_id, path=path)
690
134
 
691
135
    def __repr__(self):
692
 
        return ("%s(%r, %r, parent_id=%r, sha1=%r, len=%s)"
 
136
        return ("%s(%r, %r, kind=%r, parent_id=%r)"
693
137
                % (self.__class__.__name__,
694
138
                   self.file_id,
695
139
                   self.name,
696
 
                   self.parent_id,
697
 
                   self.text_sha1,
698
 
                   self.text_size))
699
 
 
700
 
    def _forget_tree_state(self):
701
 
        self.text_sha1 = None
702
 
 
703
 
    def _snapshot_text(self, file_parents, work_tree, commit_builder):
704
 
        """See InventoryEntry._snapshot_text."""
705
 
        def get_content_byte_lines():
706
 
            return work_tree.get_file(self.file_id).readlines()
707
 
        self.text_sha1, self.text_size = commit_builder.modified_file_text(
708
 
            self.file_id, file_parents, get_content_byte_lines, self.text_sha1, self.text_size)
709
 
 
710
 
    def _unchanged(self, previous_ie):
711
 
        """See InventoryEntry._unchanged."""
712
 
        compatible = super(InventoryFile, self)._unchanged(previous_ie)
713
 
        if self.text_sha1 != previous_ie.text_sha1:
714
 
            compatible = False
715
 
        else:
716
 
            # FIXME: 20050930 probe for the text size when getting sha1
717
 
            # in _read_tree_state
718
 
            self.text_size = previous_ie.text_size
719
 
        if self.executable != previous_ie.executable:
720
 
            compatible = False
721
 
        return compatible
722
 
 
723
 
 
724
 
class InventoryLink(InventoryEntry):
725
 
    """A file in an inventory."""
726
 
 
727
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
728
 
                 'text_id', 'parent_id', 'children', 'executable', 
729
 
                 'revision', 'symlink_target']
730
 
 
731
 
    def _check(self, checker, rev_id, tree):
732
 
        """See InventoryEntry._check"""
733
 
        if self.text_sha1 is not None or self.text_size is not None or self.text_id is not None:
734
 
            raise BzrCheckError('symlink {%s} has text in revision {%s}'
735
 
                    % (self.file_id, rev_id))
736
 
        if self.symlink_target is None:
737
 
            raise BzrCheckError('symlink {%s} has no target in revision {%s}'
738
 
                    % (self.file_id, rev_id))
739
 
 
740
 
    def copy(self):
741
 
        other = InventoryLink(self.file_id, self.name, self.parent_id)
742
 
        other.symlink_target = self.symlink_target
743
 
        other.revision = self.revision
744
 
        return other
745
 
 
746
 
    def detect_changes(self, old_entry):
747
 
        """See InventoryEntry.detect_changes."""
748
 
        # FIXME: which _modified field should we use ? RBC 20051003
749
 
        text_modified = (self.symlink_target != old_entry.symlink_target)
750
 
        if text_modified:
751
 
            mutter("    symlink target changed")
752
 
        meta_modified = False
753
 
        return text_modified, meta_modified
754
 
 
755
 
    def _diff(self, text_diff, from_label, tree, to_label, to_entry, to_tree,
756
 
             output_to, reverse=False):
757
 
        """See InventoryEntry._diff."""
758
 
        from_text = self.symlink_target
759
 
        if to_entry is not None:
760
 
            to_text = to_entry.symlink_target
761
 
            if reverse:
762
 
                temp = from_text
763
 
                from_text = to_text
764
 
                to_text = temp
765
 
            print >>output_to, '=== target changed %r => %r' % (from_text, to_text)
766
 
        else:
767
 
            if not reverse:
768
 
                print >>output_to, '=== target was %r' % self.symlink_target
769
 
            else:
770
 
                print >>output_to, '=== target is %r' % self.symlink_target
771
 
 
772
 
    def __init__(self, file_id, name, parent_id):
773
 
        super(InventoryLink, self).__init__(file_id, name, parent_id)
774
 
        self.kind = 'symlink'
775
 
 
776
 
    def kind_character(self):
777
 
        """See InventoryEntry.kind_character."""
778
 
        return ''
779
 
 
780
 
    def _put_in_tar(self, item, tree):
781
 
        """See InventoryEntry._put_in_tar."""
782
 
        item.type = tarfile.SYMTYPE
783
 
        fileobj = None
784
 
        item.size = 0
785
 
        item.mode = 0755
786
 
        item.linkname = self.symlink_target
787
 
        return fileobj
788
 
 
789
 
    def _put_on_disk(self, fullpath, tree):
790
 
        """See InventoryEntry._put_on_disk."""
791
 
        try:
792
 
            os.symlink(self.symlink_target, fullpath)
793
 
        except OSError,e:
794
 
            raise BzrError("Failed to create symlink %r -> %r, error: %s" % (fullpath, self.symlink_target, e))
795
 
 
796
 
    def _read_tree_state(self, path, work_tree):
797
 
        """See InventoryEntry._read_tree_state."""
798
 
        self.symlink_target = work_tree.get_symlink_target(self.file_id)
799
 
 
800
 
    def _forget_tree_state(self):
801
 
        self.symlink_target = None
802
 
 
803
 
    def _unchanged(self, previous_ie):
804
 
        """See InventoryEntry._unchanged."""
805
 
        compatible = super(InventoryLink, self)._unchanged(previous_ie)
806
 
        if self.symlink_target != previous_ie.symlink_target:
807
 
            compatible = False
808
 
        return compatible
809
 
 
810
 
    def _snapshot_text(self, file_parents, work_tree, commit_builder):
811
 
        """See InventoryEntry._snapshot_text."""
812
 
        commit_builder.modified_link(
813
 
            self.file_id, file_parents, self.symlink_target)
814
 
 
815
 
 
816
 
class Inventory(object):
 
140
                   self.kind,
 
141
                   self.parent_id))
 
142
 
 
143
    
 
144
    def to_element(self):
 
145
        """Convert to XML element"""
 
146
        e = Element('entry')
 
147
 
 
148
        e.set('name', self.name)
 
149
        e.set('file_id', self.file_id)
 
150
        e.set('kind', self.kind)
 
151
 
 
152
        if self.text_size is not None:
 
153
            e.set('text_size', '%d' % self.text_size)
 
154
            
 
155
        for f in ['text_id', 'text_sha1', 'parent_id']:
 
156
            v = getattr(self, f)
 
157
            if v is not None:
 
158
                e.set(f, v)
 
159
 
 
160
        e.tail = '\n'
 
161
            
 
162
        return e
 
163
 
 
164
 
 
165
    def from_element(cls, elt):
 
166
        assert elt.tag == 'entry'
 
167
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
 
168
        self.text_id = elt.get('text_id')
 
169
        self.text_sha1 = elt.get('text_sha1')
 
170
        self.parent_id = elt.get('parent_id')
 
171
        
 
172
        ## mutter("read inventoryentry: %r" % (elt.attrib))
 
173
 
 
174
        v = elt.get('text_size')
 
175
        self.text_size = v and int(v)
 
176
 
 
177
        return self
 
178
            
 
179
 
 
180
    from_element = classmethod(from_element)
 
181
 
 
182
    def __cmp__(self, other):
 
183
        if self is other:
 
184
            return 0
 
185
        if not isinstance(other, InventoryEntry):
 
186
            return NotImplemented
 
187
 
 
188
        return cmp(self.file_id, other.file_id) \
 
189
               or cmp(self.name, other.name) \
 
190
               or cmp(self.text_sha1, other.text_sha1) \
 
191
               or cmp(self.text_size, other.text_size) \
 
192
               or cmp(self.text_id, other.text_id) \
 
193
               or cmp(self.parent_id, other.parent_id) \
 
194
               or cmp(self.kind, other.kind)
 
195
 
 
196
 
 
197
 
 
198
class Inventory(XMLMixin):
817
199
    """Inventory of versioned files in a tree.
818
200
 
819
 
    This describes which file_id is present at each point in the tree,
820
 
    and possibly the SHA-1 or other information about the file.
821
 
    Entries can be looked up either by path or by file_id.
 
201
    An Inventory acts like a set of InventoryEntry items.  You can
 
202
    also look files up by their file_id or name.
 
203
    
 
204
    May be read from and written to a metadata file in a tree.  To
 
205
    manipulate the inventory (for example to add a file), it is read
 
206
    in, modified, and then written back out.
822
207
 
823
208
    The inventory represents a typical unix file tree, with
824
209
    directories containing files and subdirectories.  We never store
828
213
    returned quickly.
829
214
 
830
215
    InventoryEntry objects must not be modified after they are
831
 
    inserted, other than through the Inventory API.
 
216
    inserted.
832
217
 
833
218
    >>> inv = Inventory()
834
 
    >>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
835
 
    InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
219
    >>> inv.write_xml(sys.stdout)
 
220
    <inventory>
 
221
    </inventory>
 
222
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
836
223
    >>> inv['123-123'].name
837
224
    'hello.c'
 
225
    >>> for file_id in inv: print file_id
 
226
    ...
 
227
    123-123
838
228
 
839
229
    May be treated as an iterator or set to look up file ids:
840
230
    
846
236
    May also look up by name:
847
237
 
848
238
    >>> [x[0] for x in inv.iter_entries()]
849
 
    ['', u'hello.c']
850
 
    >>> inv = Inventory('TREE_ROOT-12345678-12345678')
851
 
    >>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
852
 
    InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT-12345678-12345678', sha1=None, len=None)
 
239
    ['hello.c']
 
240
    
 
241
    >>> inv.write_xml(sys.stdout)
 
242
    <inventory>
 
243
    <entry file_id="123-123" kind="file" name="hello.c" />
 
244
    </inventory>
 
245
 
853
246
    """
854
 
    def __init__(self, root_id=ROOT_ID, revision_id=None):
 
247
 
 
248
    ## TODO: Clear up handling of files in subdirectories; we probably
 
249
    ## do want to be able to just look them up by name but this
 
250
    ## probably means gradually walking down the path, looking up as we go.
 
251
 
 
252
    ## TODO: Make sure only canonical filenames are stored.
 
253
 
 
254
    ## TODO: Do something sensible about the possible collisions on
 
255
    ## case-losing filesystems.  Perhaps we should just always forbid
 
256
    ## such collisions.
 
257
 
 
258
    ## _tree should probably just be stored as
 
259
    ## InventoryEntry._children on each directory.
 
260
 
 
261
    def __init__(self):
855
262
        """Create or read an inventory.
856
263
 
857
264
        If a working directory is specified, the inventory is read
858
265
        from there.  If the file is specified, read from that. If not,
859
266
        the inventory is created empty.
860
 
 
861
 
        The inventory is created with a default root directory, with
862
 
        an id of None.
863
267
        """
864
 
        # We are letting Branch.create() create a unique inventory
865
 
        # root id. Rather than generating a random one here.
866
 
        #if root_id is None:
867
 
        #    root_id = bzrlib.branch.gen_file_id('TREE_ROOT')
868
 
        self.root = InventoryDirectory(root_id, '', None)
869
 
        # FIXME: this isn't ever used, changing it to self.revision may break
870
 
        # things. TODO make everything use self.revision_id
871
 
        self.revision_id = revision_id
872
 
        self._byid = {self.root.file_id: self.root}
873
 
 
874
 
    def copy(self):
875
 
        # TODO: jam 20051218 Should copy also copy the revision_id?
876
 
        entries = self.iter_entries()
877
 
        other = Inventory(entries.next()[1].file_id)
878
 
        # copy recursively so we know directories will be added before
879
 
        # their children.  There are more efficient ways than this...
880
 
        for path, entry in entries():
881
 
            other.add(entry.copy())
882
 
        return other
 
268
        self._byid = dict()
 
269
 
 
270
        # _tree is indexed by parent_id; at each level a map from name
 
271
        # to ie.  The None entry is the root.
 
272
        self._tree = {None: {}}
 
273
 
883
274
 
884
275
    def __iter__(self):
885
276
        return iter(self._byid)
886
277
 
 
278
 
887
279
    def __len__(self):
888
280
        """Returns number of entries."""
889
281
        return len(self._byid)
890
282
 
891
 
    def iter_entries(self, from_dir=None):
 
283
 
 
284
    def iter_entries(self, parent_id=None):
892
285
        """Return (path, entry) pairs, in order by name."""
893
 
        if from_dir is None:
894
 
            assert self.root
895
 
            from_dir = self.root
896
 
            yield '', self.root
897
 
        elif isinstance(from_dir, basestring):
898
 
            from_dir = self._byid[from_dir]
899
 
            
900
 
        # unrolling the recursive called changed the time from
901
 
        # 440ms/663ms (inline/total) to 116ms/116ms
902
 
        children = from_dir.children.items()
903
 
        children.sort()
904
 
        children = collections.deque(children)
905
 
        stack = [(u'', children)]
906
 
        while stack:
907
 
            from_dir_relpath, children = stack[-1]
908
 
 
909
 
            while children:
910
 
                name, ie = children.popleft()
911
 
 
912
 
                # we know that from_dir_relpath never ends in a slash
913
 
                # and 'f' doesn't begin with one, we can do a string op, rather
914
 
                # than the checks of pathjoin(), though this means that all paths
915
 
                # start with a slash
916
 
                path = from_dir_relpath + '/' + name
917
 
 
918
 
                yield path[1:], ie
919
 
 
920
 
                if ie.kind != 'directory':
921
 
                    continue
922
 
 
923
 
                # But do this child first
924
 
                new_children = ie.children.items()
925
 
                new_children.sort()
926
 
                new_children = collections.deque(new_children)
927
 
                stack.append((path, new_children))
928
 
                # Break out of inner loop, so that we start outer loop with child
929
 
                break
930
 
            else:
931
 
                # if we finished all children, pop it off the stack
932
 
                stack.pop()
933
 
 
934
 
    def iter_entries_by_dir(self, from_dir=None):
935
 
        """Iterate over the entries in a directory first order.
936
 
 
937
 
        This returns all entries for a directory before returning
938
 
        the entries for children of a directory. This is not
939
 
        lexicographically sorted order, and is a hybrid between
940
 
        depth-first and breadth-first.
941
 
 
942
 
        :return: This yields (path, entry) pairs
943
 
        """
944
 
        # TODO? Perhaps this should return the from_dir so that the root is
945
 
        # yielded? or maybe an option?
946
 
        if from_dir is None:
947
 
            assert self.root
948
 
            from_dir = self.root
949
 
            yield '', self.root
950
 
        elif isinstance(from_dir, basestring):
951
 
            from_dir = self._byid[from_dir]
952
 
            
953
 
        stack = [(u'', from_dir)]
954
 
        while stack:
955
 
            cur_relpath, cur_dir = stack.pop()
956
 
 
957
 
            child_dirs = []
958
 
            for child_name, child_ie in sorted(cur_dir.children.iteritems()):
959
 
 
960
 
                child_relpath = cur_relpath + child_name
961
 
 
962
 
                yield child_relpath, child_ie
963
 
 
964
 
                if child_ie.kind == 'directory':
965
 
                    child_dirs.append((child_relpath+'/', child_ie))
966
 
            stack.extend(reversed(child_dirs))
967
 
 
968
 
    def entries(self):
969
 
        """Return list of (path, ie) for all entries except the root.
970
 
 
971
 
        This may be faster than iter_entries.
972
 
        """
973
 
        accum = []
974
 
        def descend(dir_ie, dir_path):
975
 
            kids = dir_ie.children.items()
976
 
            kids.sort()
977
 
            for name, ie in kids:
978
 
                child_path = pathjoin(dir_path, name)
979
 
                accum.append((child_path, ie))
980
 
                if ie.kind == 'directory':
981
 
                    descend(ie, child_path)
982
 
 
983
 
        descend(self.root, u'')
984
 
        return accum
985
 
 
986
 
    def directories(self):
987
 
        """Return (path, entry) pairs for all directories, including the root.
988
 
        """
989
 
        accum = []
990
 
        def descend(parent_ie, parent_path):
991
 
            accum.append((parent_path, parent_ie))
992
 
            
993
 
            kids = [(ie.name, ie) for ie in parent_ie.children.itervalues() if ie.kind == 'directory']
994
 
            kids.sort()
995
 
 
996
 
            for name, child_ie in kids:
997
 
                child_path = pathjoin(parent_path, name)
998
 
                descend(child_ie, child_path)
999
 
        descend(self.root, u'')
1000
 
        return accum
 
286
        kids = self._tree[parent_id].items()
 
287
        kids.sort()
 
288
        for name, ie in kids:
 
289
            yield name, ie
 
290
            if ie.kind == 'directory':
 
291
                for cn, cie in self.iter_entries(parent_id=ie.file_id):
 
292
                    yield joinpath([name, cn]), cie
 
293
 
 
294
 
 
295
    def directories(self, include_root=True):
 
296
        """Return (path, entry) pairs for all directories.
 
297
        """
 
298
        if include_root:
 
299
            yield '', None
 
300
        for path, entry in self.iter_entries():
 
301
            if entry.kind == 'directory':
 
302
                yield path, entry
1001
303
        
 
304
 
 
305
 
 
306
    def children(self, parent_id):
 
307
        """Return entries that are direct children of parent_id."""
 
308
        return self._tree[parent_id]
 
309
                    
 
310
 
 
311
 
 
312
    # TODO: return all paths and entries
 
313
 
 
314
 
1002
315
    def __contains__(self, file_id):
1003
316
        """True if this entry contains a file with given id.
1004
317
 
1005
318
        >>> inv = Inventory()
1006
 
        >>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
1007
 
        InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
319
        >>> inv.add(InventoryEntry('123', 'foo.c'))
1008
320
        >>> '123' in inv
1009
321
        True
1010
322
        >>> '456' in inv
1012
324
        """
1013
325
        return file_id in self._byid
1014
326
 
 
327
 
1015
328
    def __getitem__(self, file_id):
1016
329
        """Return the entry for given file_id.
1017
330
 
1018
331
        >>> inv = Inventory()
1019
 
        >>> inv.add(InventoryFile('123123', 'hello.c', ROOT_ID))
1020
 
        InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
332
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
1021
333
        >>> inv['123123'].name
1022
334
        'hello.c'
1023
335
        """
1024
 
        try:
1025
 
            return self._byid[file_id]
1026
 
        except KeyError:
1027
 
            if file_id is None:
1028
 
                raise BzrError("can't look up file_id None")
1029
 
            else:
1030
 
                raise BzrError("file_id {%s} not in inventory" % file_id)
1031
 
 
1032
 
    def get_file_kind(self, file_id):
1033
 
        return self._byid[file_id].kind
1034
 
 
1035
 
    def get_child(self, parent_id, filename):
1036
 
        return self[parent_id].children.get(filename)
 
336
        return self._byid[file_id]
 
337
 
1037
338
 
1038
339
    def add(self, entry):
1039
340
        """Add entry to inventory.
1040
341
 
1041
342
        To add  a file to a branch ready to be committed, use Branch.add,
1042
 
        which calls this.
1043
 
 
1044
 
        Returns the new entry object.
1045
 
        """
1046
 
        if entry.file_id in self._byid:
1047
 
            raise BzrError("inventory already contains entry with id {%s}" % entry.file_id)
1048
 
 
1049
 
        if entry.parent_id == ROOT_ID or entry.parent_id is None:
1050
 
            entry.parent_id = self.root.file_id
1051
 
 
1052
 
        try:
1053
 
            parent = self._byid[entry.parent_id]
1054
 
        except KeyError:
1055
 
            raise BzrError("parent_id {%s} not in inventory" % entry.parent_id)
1056
 
 
1057
 
        if entry.name in parent.children:
1058
 
            raise BzrError("%s is already versioned" %
1059
 
                    pathjoin(self.id2path(parent.file_id), entry.name))
 
343
        which calls this."""
 
344
        if entry.file_id in self:
 
345
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
 
346
 
 
347
        if entry.parent_id != None:
 
348
            if entry.parent_id not in self:
 
349
                bailout("parent_id %s of new entry not found in inventory"
 
350
                        % entry.parent_id)
 
351
            
 
352
        if self._tree[entry.parent_id].has_key(entry.name):
 
353
            bailout("%s is already versioned"
 
354
                    % appendpath(self.id2path(entry.parent_id), entry.name))
1060
355
 
1061
356
        self._byid[entry.file_id] = entry
1062
 
        parent.children[entry.name] = entry
1063
 
        return entry
1064
 
 
1065
 
    def add_path(self, relpath, kind, file_id=None, parent_id=None):
1066
 
        """Add entry from a path.
1067
 
 
1068
 
        The immediate parent must already be versioned.
1069
 
 
1070
 
        Returns the new entry object."""
1071
 
        
1072
 
        parts = osutils.splitpath(relpath)
1073
 
 
1074
 
        if len(parts) == 0:
1075
 
            if file_id is None:
1076
 
                file_id = bzrlib.workingtree.gen_root_id()
1077
 
            self.root = InventoryDirectory(file_id, '', None)
1078
 
            self._byid = {self.root.file_id: self.root}
1079
 
            return
1080
 
        else:
1081
 
            parent_path = parts[:-1]
1082
 
            parent_id = self.path2id(parent_path)
1083
 
            if parent_id is None:
1084
 
                raise NotVersionedError(path=parent_path)
1085
 
        ie = make_entry(kind, parts[-1], parent_id, file_id)
1086
 
        return self.add(ie)
 
357
        self._tree[entry.parent_id][entry.name] = entry
 
358
 
 
359
        if entry.kind == 'directory':
 
360
            self._tree[entry.file_id] = {}
 
361
 
1087
362
 
1088
363
    def __delitem__(self, file_id):
1089
364
        """Remove entry by id.
1090
365
 
1091
366
        >>> inv = Inventory()
1092
 
        >>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
1093
 
        InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
 
367
        >>> inv.add(InventoryEntry('123', 'foo.c'))
1094
368
        >>> '123' in inv
1095
369
        True
1096
370
        >>> del inv['123']
1099
373
        """
1100
374
        ie = self[file_id]
1101
375
 
1102
 
        assert ie.parent_id is None or \
1103
 
            self[ie.parent_id].children[ie.name] == ie
 
376
        assert self._tree[ie.parent_id][ie.name] == ie
1104
377
        
 
378
        # TODO: Test deleting all children; maybe hoist to a separate
 
379
        # deltree method?
 
380
        if ie.kind == 'directory':
 
381
            for cie in self._tree[file_id].values():
 
382
                del self[cie.file_id]
 
383
            del self._tree[file_id]
 
384
 
1105
385
        del self._byid[file_id]
1106
 
        if ie.parent_id is not None:
1107
 
            del self[ie.parent_id].children[ie.name]
1108
 
 
1109
 
    def __eq__(self, other):
 
386
        del self._tree[ie.parent_id][ie.name]
 
387
 
 
388
 
 
389
    def id_set(self):
 
390
        return Set(self._byid)
 
391
 
 
392
 
 
393
    def to_element(self):
 
394
        """Convert to XML Element"""
 
395
        e = Element('inventory')
 
396
        e.text = '\n'
 
397
        for path, ie in self.iter_entries():
 
398
            e.append(ie.to_element())
 
399
        return e
 
400
    
 
401
 
 
402
    def from_element(cls, elt):
 
403
        """Construct from XML Element
 
404
 
 
405
        >>> inv = Inventory()
 
406
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
 
407
        >>> elt = inv.to_element()
 
408
        >>> inv2 = Inventory.from_element(elt)
 
409
        >>> inv2 == inv
 
410
        True
 
411
        """
 
412
        assert elt.tag == 'inventory'
 
413
        o = cls()
 
414
        for e in elt:
 
415
            o.add(InventoryEntry.from_element(e))
 
416
        return o
 
417
        
 
418
    from_element = classmethod(from_element)
 
419
 
 
420
 
 
421
    def __cmp__(self, other):
1110
422
        """Compare two sets by comparing their contents.
1111
423
 
1112
424
        >>> i1 = Inventory()
1113
425
        >>> i2 = Inventory()
1114
426
        >>> i1 == i2
1115
427
        True
1116
 
        >>> i1.add(InventoryFile('123', 'foo', ROOT_ID))
1117
 
        InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None)
 
428
        >>> i1.add(InventoryEntry('123', 'foo'))
1118
429
        >>> i1 == i2
1119
430
        False
1120
 
        >>> i2.add(InventoryFile('123', 'foo', ROOT_ID))
1121
 
        InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None)
 
431
        >>> i2.add(InventoryEntry('123', 'foo'))
1122
432
        >>> i1 == i2
1123
433
        True
1124
434
        """
 
435
        if self is other:
 
436
            return 0
 
437
        
1125
438
        if not isinstance(other, Inventory):
1126
439
            return NotImplemented
1127
440
 
1128
 
        return self._byid == other._byid
1129
 
 
1130
 
    def __ne__(self, other):
1131
 
        return not self.__eq__(other)
1132
 
 
1133
 
    def __hash__(self):
1134
 
        raise ValueError('not hashable')
1135
 
 
1136
 
    def _iter_file_id_parents(self, file_id):
1137
 
        """Yield the parents of file_id up to the root."""
1138
 
        while file_id is not None:
1139
 
            try:
1140
 
                ie = self._byid[file_id]
1141
 
            except KeyError:
1142
 
                raise BzrError("file_id {%s} not found in inventory" % file_id)
1143
 
            yield ie
 
441
        if self.id_set() ^ other.id_set():
 
442
            return 1
 
443
 
 
444
        for file_id in self._byid:
 
445
            c = cmp(self[file_id], other[file_id])
 
446
            if c: return c
 
447
 
 
448
        return 0
 
449
 
 
450
 
 
451
    def id2path(self, file_id):
 
452
        """Return as a list the path to file_id."""
 
453
        p = []
 
454
        while file_id != None:
 
455
            ie = self[file_id]
 
456
            p = [ie.name] + p
1144
457
            file_id = ie.parent_id
1145
 
 
1146
 
    def get_idpath(self, file_id):
1147
 
        """Return a list of file_ids for the path to an entry.
1148
 
 
1149
 
        The list contains one element for each directory followed by
1150
 
        the id of the file itself.  So the length of the returned list
1151
 
        is equal to the depth of the file in the tree, counting the
1152
 
        root directory as depth 1.
1153
 
        """
1154
 
        p = []
1155
 
        for parent in self._iter_file_id_parents(file_id):
1156
 
            p.insert(0, parent.file_id)
1157
 
        return p
1158
 
 
1159
 
    def id2path(self, file_id):
1160
 
        """Return as a string the path to file_id.
1161
 
        
1162
 
        >>> i = Inventory()
1163
 
        >>> e = i.add(InventoryDirectory('src-id', 'src', ROOT_ID))
1164
 
        >>> e = i.add(InventoryFile('foo-id', 'foo.c', parent_id='src-id'))
1165
 
        >>> print i.id2path('foo-id')
1166
 
        src/foo.c
1167
 
        """
1168
 
        # get all names, skipping root
1169
 
        return '/'.join(reversed(
1170
 
            [parent.name for parent in 
1171
 
             self._iter_file_id_parents(file_id)][:-1]))
 
458
        return joinpath(p)
1172
459
            
 
460
 
 
461
 
1173
462
    def path2id(self, name):
1174
463
        """Walk down through directories to return entry of last component.
1175
464
 
1178
467
 
1179
468
        This returns the entry of the last component in the path,
1180
469
        which may be either a file or a directory.
1181
 
 
1182
 
        Returns None IFF the path is not found.
1183
470
        """
1184
 
        if isinstance(name, types.StringTypes):
1185
 
            name = splitpath(name)
1186
 
 
1187
 
        # mutter("lookup path %r" % name)
1188
 
 
1189
 
        parent = self.root
1190
 
        for f in name:
 
471
        assert isinstance(name, types.StringTypes)
 
472
 
 
473
        parent_id = None
 
474
        for f in splitpath(name):
1191
475
            try:
1192
 
                cie = parent.children[f]
 
476
                cie = self._tree[parent_id][f]
1193
477
                assert cie.name == f
1194
 
                assert cie.parent_id == parent.file_id
1195
 
                parent = cie
 
478
                parent_id = cie.file_id
1196
479
            except KeyError:
1197
480
                # or raise an error?
1198
481
                return None
1199
482
 
1200
 
        return parent.file_id
 
483
        return parent_id
 
484
 
 
485
 
 
486
    def get_child(self, parent_id, child_name):
 
487
        return self._tree[parent_id].get(child_name)
 
488
 
1201
489
 
1202
490
    def has_filename(self, names):
1203
491
        return bool(self.path2id(names))
1204
492
 
 
493
 
1205
494
    def has_id(self, file_id):
 
495
        assert isinstance(file_id, str)
1206
496
        return self._byid.has_key(file_id)
1207
497
 
1208
 
    def rename(self, file_id, new_parent_id, new_name):
1209
 
        """Move a file within the inventory.
1210
 
 
1211
 
        This can change either the name, or the parent, or both.
1212
 
 
1213
 
        This does not move the working file."""
1214
 
        if not is_valid_name(new_name):
1215
 
            raise BzrError("not an acceptable filename: %r" % new_name)
1216
 
 
1217
 
        new_parent = self._byid[new_parent_id]
1218
 
        if new_name in new_parent.children:
1219
 
            raise BzrError("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
1220
 
 
1221
 
        new_parent_idpath = self.get_idpath(new_parent_id)
1222
 
        if file_id in new_parent_idpath:
1223
 
            raise BzrError("cannot move directory %r into a subdirectory of itself, %r"
1224
 
                    % (self.id2path(file_id), self.id2path(new_parent_id)))
1225
 
 
1226
 
        file_ie = self._byid[file_id]
1227
 
        old_parent = self._byid[file_ie.parent_id]
1228
 
 
1229
 
        # TODO: Don't leave things messed up if this fails
1230
 
 
1231
 
        del old_parent.children[file_ie.name]
1232
 
        new_parent.children[new_name] = file_ie
1233
 
        
1234
 
        file_ie.name = new_name
1235
 
        file_ie.parent_id = new_parent_id
1236
 
 
1237
 
 
1238
 
def make_entry(kind, name, parent_id, file_id=None):
1239
 
    """Create an inventory entry.
1240
 
 
1241
 
    :param kind: the type of inventory entry to create.
1242
 
    :param name: the basename of the entry.
1243
 
    :param parent_id: the parent_id of the entry.
1244
 
    :param file_id: the file_id to use. if None, one will be created.
1245
 
    """
1246
 
    if file_id is None:
1247
 
        file_id = bzrlib.workingtree.gen_file_id(name)
1248
 
 
1249
 
    norm_name, can_access = osutils.normalized_filename(name)
1250
 
    if norm_name != name:
1251
 
        if can_access:
1252
 
            name = norm_name
1253
 
        else:
1254
 
            # TODO: jam 20060701 This would probably be more useful
1255
 
            #       if the error was raised with the full path
1256
 
            raise errors.InvalidNormalization(name)
1257
 
 
1258
 
    if kind == 'directory':
1259
 
        return InventoryDirectory(file_id, name, parent_id)
1260
 
    elif kind == 'file':
1261
 
        return InventoryFile(file_id, name, parent_id)
1262
 
    elif kind == 'symlink':
1263
 
        return InventoryLink(file_id, name, parent_id)
1264
 
    else:
1265
 
        raise BzrError("unknown kind %r" % kind)
1266
 
 
1267
 
 
1268
 
_NAME_RE = None
1269
 
 
1270
 
def is_valid_name(name):
1271
 
    global _NAME_RE
1272
 
    if _NAME_RE is None:
1273
 
        _NAME_RE = re.compile(r'^[^/\\]+$')
1274
 
        
1275
 
    return bool(_NAME_RE.match(name))
 
498
 
 
499
 
 
500
if __name__ == '__main__':
 
501
    import doctest, inventory
 
502
    doctest.testmod(inventory)