~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Alexander Belchenko
  • Date: 2006-07-30 06:52:39 UTC
  • mto: (1711.2.111 jam-integration)
  • mto: This revision was merged to the branch mainline in revision 1906.
  • Revision ID: bialix@ukr.net-20060730065239-03b4ac02d9f56202
branding: change Bazaar-NG to Bazaar

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