~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

silly commit

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
 
 
18
 
# TODO: Maybe also keep the full path of the entry, and the children?
19
 
# But those depend on its position within a particular inventory, and
20
 
# it would be nice not to need to hold the backpointer here.
21
 
 
22
 
# TODO: Perhaps split InventoryEntry into subclasses for files,
23
 
# directories, etc etc.
24
 
 
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 sys, os.path, types, re
32
 
 
33
 
import bzrlib
34
 
from bzrlib.errors import BzrError, BzrCheckError
35
 
 
36
 
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
37
 
from bzrlib.trace import mutter
38
 
from bzrlib.errors import NotVersionedError
39
 
        
40
 
 
41
 
class InventoryEntry(object):
42
 
    """Description of a versioned file.
43
 
 
44
 
    An InventoryEntry has the following fields, which are also
45
 
    present in the XML inventory-entry element:
46
 
 
47
 
    file_id
48
 
 
49
 
    name
50
 
        (within the parent directory)
51
 
 
52
 
    kind
53
 
        'directory' or 'file'
54
 
 
55
 
    parent_id
56
 
        file_id of the parent directory, or ROOT_ID
57
 
 
58
 
    entry_version
59
 
        the revision_id in which the name or parent of this file was
60
 
        last changed
61
 
 
62
 
    text_sha1
63
 
        sha-1 of the text of the file
64
 
        
65
 
    text_size
66
 
        size in bytes of the text of the file
67
 
        
68
 
    text_version
69
 
        the revision_id in which the text of this file was introduced
70
 
 
71
 
    (reading a version 4 tree created a text_id field.)
72
 
 
73
 
    >>> i = Inventory()
74
 
    >>> i.path2id('')
75
 
    'TREE_ROOT'
76
 
    >>> i.add(InventoryEntry('123', 'src', 'directory', ROOT_ID))
77
 
    InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT')
78
 
    >>> i.add(InventoryEntry('2323', 'hello.c', 'file', parent_id='123'))
79
 
    InventoryEntry('2323', 'hello.c', kind='file', parent_id='123')
80
 
    >>> for j in i.iter_entries():
81
 
    ...   print j
82
 
    ... 
83
 
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT'))
84
 
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
85
 
    >>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))
86
 
    Traceback (most recent call last):
87
 
    ...
88
 
    BzrError: inventory already contains entry with id {2323}
89
 
    >>> i.add(InventoryEntry('2324', 'bye.c', 'file', '123'))
90
 
    InventoryEntry('2324', 'bye.c', kind='file', parent_id='123')
91
 
    >>> i.add(InventoryEntry('2325', 'wibble', 'directory', '123'))
92
 
    InventoryEntry('2325', 'wibble', kind='directory', parent_id='123')
93
 
    >>> i.path2id('src/wibble')
94
 
    '2325'
95
 
    >>> '2325' in i
96
 
    True
97
 
    >>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))
98
 
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
99
 
    >>> i['2326']
100
 
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
101
 
    >>> for j in i.iter_entries():
102
 
    ...     print j[0]
103
 
    ...     assert i.path2id(j[0])
104
 
    ... 
105
 
    src
106
 
    src/bye.c
107
 
    src/hello.c
108
 
    src/wibble
109
 
    src/wibble/wibble.c
110
 
    >>> i.id2path('2326')
111
 
    'src/wibble/wibble.c'
112
 
    """
113
 
    
114
 
    __slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
115
 
                 'text_id', 'parent_id', 'children',
116
 
                 'text_version', 'entry_version', ]
117
 
 
118
 
 
119
 
    def __init__(self, file_id, name, kind, parent_id, text_id=None):
120
 
        """Create an InventoryEntry
121
 
        
122
 
        The filename must be a single component, relative to the
123
 
        parent directory; it cannot be a whole path or relative name.
124
 
 
125
 
        >>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)
126
 
        >>> e.name
127
 
        'hello.c'
128
 
        >>> e.file_id
129
 
        '123'
130
 
        >>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)
131
 
        Traceback (most recent call last):
132
 
        BzrCheckError: InventoryEntry name 'src/hello.c' is invalid
133
 
        """
134
 
        assert isinstance(name, basestring), name
135
 
        if '/' in name or '\\' in name:
136
 
            raise BzrCheckError('InventoryEntry name %r is invalid' % name)
137
 
        
138
 
        self.text_version = None
139
 
        self.entry_version = None
140
 
        self.text_sha1 = None
141
 
        self.text_size = None
142
 
        self.file_id = file_id
143
 
        self.name = name
144
 
        self.kind = kind
145
 
        self.text_id = text_id
146
 
        self.parent_id = parent_id
147
 
        if kind == 'directory':
148
 
            self.children = {}
149
 
        elif kind == 'file':
150
 
            pass
151
 
        else:
152
 
            raise BzrError("unhandled entry kind %r" % kind)
153
 
 
154
 
 
155
 
 
156
 
    def sorted_children(self):
157
 
        l = self.children.items()
158
 
        l.sort()
159
 
        return l
160
 
 
161
 
 
162
 
    def copy(self):
163
 
        other = InventoryEntry(self.file_id, self.name, self.kind,
164
 
                               self.parent_id)
165
 
        other.text_id = self.text_id
166
 
        other.text_sha1 = self.text_sha1
167
 
        other.text_size = self.text_size
168
 
        other.text_version = self.text_version
169
 
        # note that children are *not* copied; they're pulled across when
170
 
        # others are added
171
 
        return other
172
 
 
173
 
 
174
 
    def __repr__(self):
175
 
        return ("%s(%r, %r, kind=%r, parent_id=%r)"
176
 
                % (self.__class__.__name__,
177
 
                   self.file_id,
178
 
                   self.name,
179
 
                   self.kind,
180
 
                   self.parent_id))
181
 
 
182
 
    
183
 
    def __eq__(self, other):
184
 
        if not isinstance(other, InventoryEntry):
185
 
            return NotImplemented
186
 
 
187
 
        return (self.file_id == other.file_id) \
188
 
               and (self.name == other.name) \
189
 
               and (self.text_sha1 == other.text_sha1) \
190
 
               and (self.text_size == other.text_size) \
191
 
               and (self.text_id == other.text_id) \
192
 
               and (self.parent_id == other.parent_id) \
193
 
               and (self.kind == other.kind) \
194
 
               and (self.text_version == other.text_version) \
195
 
               and (self.entry_version == other.entry_version)
196
 
 
197
 
 
198
 
    def __ne__(self, other):
199
 
        return not (self == other)
200
 
 
201
 
    def __hash__(self):
202
 
        raise ValueError('not hashable')
203
 
 
204
 
 
205
 
 
206
 
class RootEntry(InventoryEntry):
207
 
    def __init__(self, file_id):
208
 
        self.file_id = file_id
209
 
        self.children = {}
210
 
        self.kind = 'root_directory'
211
 
        self.parent_id = None
212
 
        self.name = ''
213
 
 
214
 
    def __eq__(self, other):
215
 
        if not isinstance(other, RootEntry):
216
 
            return NotImplemented
217
 
        
218
 
        return (self.file_id == other.file_id) \
219
 
               and (self.children == other.children)
220
 
 
221
 
 
222
 
 
223
 
class Inventory(object):
224
 
    """Inventory of versioned files in a tree.
225
 
 
226
 
    This describes which file_id is present at each point in the tree,
227
 
    and possibly the SHA-1 or other information about the file.
228
 
    Entries can be looked up either by path or by file_id.
229
 
 
230
 
    The inventory represents a typical unix file tree, with
231
 
    directories containing files and subdirectories.  We never store
232
 
    the full path to a file, because renaming a directory implicitly
233
 
    moves all of its contents.  This class internally maintains a
234
 
    lookup tree that allows the children under a directory to be
235
 
    returned quickly.
236
 
 
237
 
    InventoryEntry objects must not be modified after they are
238
 
    inserted, other than through the Inventory API.
239
 
 
240
 
    >>> inv = Inventory()
241
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
242
 
    InventoryEntry('123-123', 'hello.c', kind='file', parent_id='TREE_ROOT')
243
 
    >>> inv['123-123'].name
244
 
    'hello.c'
245
 
 
246
 
    May be treated as an iterator or set to look up file ids:
247
 
    
248
 
    >>> bool(inv.path2id('hello.c'))
249
 
    True
250
 
    >>> '123-123' in inv
251
 
    True
252
 
 
253
 
    May also look up by name:
254
 
 
255
 
    >>> [x[0] for x in inv.iter_entries()]
256
 
    ['hello.c']
257
 
    >>> inv = Inventory('TREE_ROOT-12345678-12345678')
258
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
259
 
    InventoryEntry('123-123', 'hello.c', kind='file', parent_id='TREE_ROOT-12345678-12345678')
260
 
    """
261
 
    def __init__(self, root_id=ROOT_ID):
262
 
        """Create or read an inventory.
263
 
 
264
 
        If a working directory is specified, the inventory is read
265
 
        from there.  If the file is specified, read from that. If not,
266
 
        the inventory is created empty.
267
 
 
268
 
        The inventory is created with a default root directory, with
269
 
        an id of None.
270
 
        """
271
 
        # We are letting Branch(init=True) create a unique inventory
272
 
        # root id. Rather than generating a random one here.
273
 
        #if root_id is None:
274
 
        #    root_id = bzrlib.branch.gen_file_id('TREE_ROOT')
275
 
        self.root = RootEntry(root_id)
276
 
        self._byid = {self.root.file_id: self.root}
277
 
 
278
 
 
279
 
    def copy(self):
280
 
        other = Inventory(self.root.file_id)
281
 
        # copy recursively so we know directories will be added before
282
 
        # their children.  There are more efficient ways than this...
283
 
        for path, entry in self.iter_entries():
284
 
            if entry == self.root:
285
 
                continue
286
 
            other.add(entry.copy())
287
 
        return other
288
 
 
289
 
 
290
 
    def __iter__(self):
291
 
        return iter(self._byid)
292
 
 
293
 
 
294
 
    def __len__(self):
295
 
        """Returns number of entries."""
296
 
        return len(self._byid)
297
 
 
298
 
 
299
 
    def iter_entries(self, from_dir=None):
300
 
        """Return (path, entry) pairs, in order by name."""
301
 
        if from_dir == None:
302
 
            assert self.root
303
 
            from_dir = self.root
304
 
        elif isinstance(from_dir, basestring):
305
 
            from_dir = self._byid[from_dir]
306
 
            
307
 
        kids = from_dir.children.items()
308
 
        kids.sort()
309
 
        for name, ie in kids:
310
 
            yield name, ie
311
 
            if ie.kind == 'directory':
312
 
                for cn, cie in self.iter_entries(from_dir=ie.file_id):
313
 
                    yield os.path.join(name, cn), cie
314
 
 
315
 
 
316
 
    def entries(self):
317
 
        """Return list of (path, ie) for all entries except the root.
318
 
 
319
 
        This may be faster than iter_entries.
320
 
        """
321
 
        accum = []
322
 
        def descend(dir_ie, dir_path):
323
 
            kids = dir_ie.children.items()
324
 
            kids.sort()
325
 
            for name, ie in kids:
326
 
                child_path = os.path.join(dir_path, name)
327
 
                accum.append((child_path, ie))
328
 
                if ie.kind == 'directory':
329
 
                    descend(ie, child_path)
330
 
 
331
 
        descend(self.root, '')
332
 
        return accum
333
 
 
334
 
 
335
 
    def directories(self):
336
 
        """Return (path, entry) pairs for all directories, including the root.
337
 
        """
338
 
        accum = []
339
 
        def descend(parent_ie, parent_path):
340
 
            accum.append((parent_path, parent_ie))
341
 
            
342
 
            kids = [(ie.name, ie) for ie in parent_ie.children.itervalues() if ie.kind == 'directory']
343
 
            kids.sort()
344
 
 
345
 
            for name, child_ie in kids:
346
 
                child_path = os.path.join(parent_path, name)
347
 
                descend(child_ie, child_path)
348
 
        descend(self.root, '')
349
 
        return accum
350
 
        
351
 
 
352
 
 
353
 
    def __contains__(self, file_id):
354
 
        """True if this entry contains a file with given id.
355
 
 
356
 
        >>> inv = Inventory()
357
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
358
 
        InventoryEntry('123', 'foo.c', kind='file', parent_id='TREE_ROOT')
359
 
        >>> '123' in inv
360
 
        True
361
 
        >>> '456' in inv
362
 
        False
363
 
        """
364
 
        return file_id in self._byid
365
 
 
366
 
 
367
 
    def __getitem__(self, file_id):
368
 
        """Return the entry for given file_id.
369
 
 
370
 
        >>> inv = Inventory()
371
 
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
372
 
        InventoryEntry('123123', 'hello.c', kind='file', parent_id='TREE_ROOT')
373
 
        >>> inv['123123'].name
374
 
        'hello.c'
375
 
        """
376
 
        try:
377
 
            return self._byid[file_id]
378
 
        except KeyError:
379
 
            if file_id == None:
380
 
                raise BzrError("can't look up file_id None")
381
 
            else:
382
 
                raise BzrError("file_id {%s} not in inventory" % file_id)
383
 
 
384
 
 
385
 
    def get_file_kind(self, file_id):
386
 
        return self._byid[file_id].kind
387
 
 
388
 
    def get_child(self, parent_id, filename):
389
 
        return self[parent_id].children.get(filename)
390
 
 
391
 
 
392
 
    def add(self, entry):
393
 
        """Add entry to inventory.
394
 
 
395
 
        To add  a file to a branch ready to be committed, use Branch.add,
396
 
        which calls this.
397
 
 
398
 
        Returns the new entry object.
399
 
        """
400
 
        if entry.file_id in self._byid:
401
 
            raise BzrError("inventory already contains entry with id {%s}" % entry.file_id)
402
 
 
403
 
        if entry.parent_id == ROOT_ID or entry.parent_id is None:
404
 
            entry.parent_id = self.root.file_id
405
 
 
406
 
        try:
407
 
            parent = self._byid[entry.parent_id]
408
 
        except KeyError:
409
 
            raise BzrError("parent_id {%s} not in inventory" % entry.parent_id)
410
 
 
411
 
        if parent.children.has_key(entry.name):
412
 
            raise BzrError("%s is already versioned" %
413
 
                    appendpath(self.id2path(parent.file_id), entry.name))
414
 
 
415
 
        self._byid[entry.file_id] = entry
416
 
        parent.children[entry.name] = entry
417
 
        return entry
418
 
 
419
 
 
420
 
    def add_path(self, relpath, kind, file_id=None):
421
 
        """Add entry from a path.
422
 
 
423
 
        The immediate parent must already be versioned.
424
 
 
425
 
        Returns the new entry object."""
426
 
        from bzrlib.branch import gen_file_id
427
 
        
428
 
        parts = bzrlib.osutils.splitpath(relpath)
429
 
        if len(parts) == 0:
430
 
            raise BzrError("cannot re-add root of inventory")
431
 
 
432
 
        if file_id == None:
433
 
            file_id = gen_file_id(relpath)
434
 
 
435
 
        parent_path = parts[:-1]
436
 
        parent_id = self.path2id(parent_path)
437
 
        if parent_id == None:
438
 
            raise NotVersionedError(parent_path)
439
 
 
440
 
        ie = InventoryEntry(file_id, parts[-1],
441
 
                            kind=kind, parent_id=parent_id)
442
 
        return self.add(ie)
443
 
 
444
 
 
445
 
    def __delitem__(self, file_id):
446
 
        """Remove entry by id.
447
 
 
448
 
        >>> inv = Inventory()
449
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
450
 
        InventoryEntry('123', 'foo.c', kind='file', parent_id='TREE_ROOT')
451
 
        >>> '123' in inv
452
 
        True
453
 
        >>> del inv['123']
454
 
        >>> '123' in inv
455
 
        False
456
 
        """
457
 
        ie = self[file_id]
458
 
 
459
 
        assert self[ie.parent_id].children[ie.name] == ie
460
 
        
461
 
        # TODO: Test deleting all children; maybe hoist to a separate
462
 
        # deltree method?
463
 
        if ie.kind == 'directory':
464
 
            for cie in ie.children.values():
465
 
                del self[cie.file_id]
466
 
            del ie.children
467
 
 
468
 
        del self._byid[file_id]
469
 
        del self[ie.parent_id].children[ie.name]
470
 
 
471
 
 
472
 
    def __eq__(self, other):
473
 
        """Compare two sets by comparing their contents.
474
 
 
475
 
        >>> i1 = Inventory()
476
 
        >>> i2 = Inventory()
477
 
        >>> i1 == i2
478
 
        True
479
 
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
480
 
        InventoryEntry('123', 'foo', kind='file', parent_id='TREE_ROOT')
481
 
        >>> i1 == i2
482
 
        False
483
 
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
484
 
        InventoryEntry('123', 'foo', kind='file', parent_id='TREE_ROOT')
485
 
        >>> i1 == i2
486
 
        True
487
 
        """
488
 
        if not isinstance(other, Inventory):
489
 
            return NotImplemented
490
 
 
491
 
        if len(self._byid) != len(other._byid):
492
 
            # shortcut: obviously not the same
493
 
            return False
494
 
 
495
 
        return self._byid == other._byid
496
 
 
497
 
 
498
 
    def __ne__(self, other):
499
 
        return not (self == other)
500
 
 
501
 
 
502
 
    def __hash__(self):
503
 
        raise ValueError('not hashable')
504
 
 
505
 
 
506
 
    def get_idpath(self, file_id):
507
 
        """Return a list of file_ids for the path to an entry.
508
 
 
509
 
        The list contains one element for each directory followed by
510
 
        the id of the file itself.  So the length of the returned list
511
 
        is equal to the depth of the file in the tree, counting the
512
 
        root directory as depth 1.
513
 
        """
514
 
        p = []
515
 
        while file_id != None:
516
 
            try:
517
 
                ie = self._byid[file_id]
518
 
            except KeyError:
519
 
                raise BzrError("file_id {%s} not found in inventory" % file_id)
520
 
            p.insert(0, ie.file_id)
521
 
            file_id = ie.parent_id
522
 
        return p
523
 
 
524
 
 
525
 
    def id2path(self, file_id):
526
 
        """Return as a list the path to file_id."""
527
 
 
528
 
        # get all names, skipping root
529
 
        p = [self._byid[fid].name for fid in self.get_idpath(file_id)[1:]]
530
 
        return os.sep.join(p)
531
 
            
532
 
 
533
 
 
534
 
    def path2id(self, name):
535
 
        """Walk down through directories to return entry of last component.
536
 
 
537
 
        names may be either a list of path components, or a single
538
 
        string, in which case it is automatically split.
539
 
 
540
 
        This returns the entry of the last component in the path,
541
 
        which may be either a file or a directory.
542
 
 
543
 
        Returns None iff the path is not found.
544
 
        """
545
 
        if isinstance(name, types.StringTypes):
546
 
            name = splitpath(name)
547
 
 
548
 
        mutter("lookup path %r" % name)
549
 
 
550
 
        parent = self.root
551
 
        for f in name:
552
 
            try:
553
 
                cie = parent.children[f]
554
 
                assert cie.name == f
555
 
                assert cie.parent_id == parent.file_id
556
 
                parent = cie
557
 
            except KeyError:
558
 
                # or raise an error?
559
 
                return None
560
 
 
561
 
        return parent.file_id
562
 
 
563
 
 
564
 
    def has_filename(self, names):
565
 
        return bool(self.path2id(names))
566
 
 
567
 
 
568
 
    def has_id(self, file_id):
569
 
        return self._byid.has_key(file_id)
570
 
 
571
 
 
572
 
    def rename(self, file_id, new_parent_id, new_name):
573
 
        """Move a file within the inventory.
574
 
 
575
 
        This can change either the name, or the parent, or both.
576
 
 
577
 
        This does not move the working file."""
578
 
        if not is_valid_name(new_name):
579
 
            raise BzrError("not an acceptable filename: %r" % new_name)
580
 
 
581
 
        new_parent = self._byid[new_parent_id]
582
 
        if new_name in new_parent.children:
583
 
            raise BzrError("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
584
 
 
585
 
        new_parent_idpath = self.get_idpath(new_parent_id)
586
 
        if file_id in new_parent_idpath:
587
 
            raise BzrError("cannot move directory %r into a subdirectory of itself, %r"
588
 
                    % (self.id2path(file_id), self.id2path(new_parent_id)))
589
 
 
590
 
        file_ie = self._byid[file_id]
591
 
        old_parent = self._byid[file_ie.parent_id]
592
 
 
593
 
        # TODO: Don't leave things messed up if this fails
594
 
 
595
 
        del old_parent.children[file_ie.name]
596
 
        new_parent.children[new_name] = file_ie
597
 
        
598
 
        file_ie.name = new_name
599
 
        file_ie.parent_id = new_parent_id
600
 
 
601
 
 
602
 
 
603
 
 
604
 
_NAME_RE = None
605
 
 
606
 
def is_valid_name(name):
607
 
    global _NAME_RE
608
 
    if _NAME_RE == None:
609
 
        _NAME_RE = re.compile(r'^[^/\\]+$')
610
 
        
611
 
    return bool(_NAME_RE.match(name))