~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Alexander Belchenko
  • Date: 2006-07-31 16:12:57 UTC
  • mto: (1711.2.111 jam-integration)
  • mto: This revision was merged to the branch mainline in revision 1906.
  • Revision ID: bialix@ukr.net-20060731161257-91a231523255332c
new official bzr.ico

Show diffs side-by-side

added added

removed removed

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