/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Robert Collins
  • Date: 2006-04-20 04:52:19 UTC
  • mto: (1711.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 1677.
  • Revision ID: robertc@robertcollins.net-20060420045219-440c2336c88c5d0e
Really fix short-read support in tuned_gzip. The python zlib module behaved differently than thought.

Show diffs side-by-side

added added

removed removed

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