← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: mbp at sourcefrog
  • Date: 2005-03-19 08:19:38 UTC
  • Revision ID: mbp@sourcefrog.net-20050319081938-596d89f99a644569
use "/usr/bin/env python" for shebang"

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/inventory.py
1
 
# (C) 2005 Canonical Ltd
 
1
#! /usr/bin/env python
 
2
# -*- coding: UTF-8 -*-
2
3
 
3
4
# This program is free software; you can redistribute it and/or modify
4
5
# it under the terms of the GNU General Public License as published by
14
15
# along with this program; if not, write to the Free Software
15
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
17
 
17
 
 
18
 
# This should really be an id randomly assigned when the tree is
19
 
# created, but it's not for now.
20
 
ROOT_ID = "TREE_ROOT"
21
 
 
22
 
 
23
 
import sys, os.path, types, re
 
18
"""Inventories map files to their name in a revision."""
 
19
 
 
20
 
 
21
__copyright__ = "Copyright (C) 2005 Canonical Ltd."
 
22
__author__ = "Martin Pool <mbp@canonical.com>"
 
23
 
 
24
import sys, os.path, types
24
25
from sets import Set
25
26
 
26
27
try:
29
30
    from elementtree.ElementTree import Element, ElementTree, SubElement
30
31
 
31
32
from xml import XMLMixin
32
 
from errors import bailout, BzrError
33
 
 
34
 
import bzrlib
35
 
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
36
 
from bzrlib.trace import mutter
 
33
from errors import bailout
 
34
from osutils import uuid, quotefn, splitpath, joinpath, appendpath
 
35
from trace import mutter
37
36
 
38
37
class InventoryEntry(XMLMixin):
39
38
    """Description of a versioned file.
58
57
 
59
58
    >>> i = Inventory()
60
59
    >>> i.path2id('')
61
 
    'TREE_ROOT'
62
 
    >>> i.add(InventoryEntry('123', 'src', 'directory', ROOT_ID))
63
 
    >>> i.add(InventoryEntry('2323', 'hello.c', 'file', parent_id='123'))
 
60
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
 
61
    >>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))
64
62
    >>> for j in i.iter_entries():
65
63
    ...   print j
66
64
    ... 
67
 
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT'))
 
65
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
68
66
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
69
 
    >>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))
 
67
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
70
68
    Traceback (most recent call last):
71
69
    ...
72
70
    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'))
 
71
    >>> i.add(InventoryEntry('2324', 'bye.c', parent_id='123'))
 
72
    >>> i.add(InventoryEntry('2325', 'wibble', parent_id='123', kind='directory'))
75
73
    >>> i.path2id('src/wibble')
76
74
    '2325'
77
75
    >>> '2325' in i
78
76
    True
79
 
    >>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))
 
77
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
80
78
    >>> i['2326']
81
79
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
82
80
    >>> for j in i.iter_entries():
91
89
    >>> i.id2path('2326')
92
90
    'src/wibble/wibble.c'
93
91
 
94
 
    TODO: Maybe also keep the full path of the entry, and the children?
 
92
    :todo: Maybe also keep the full path of the entry, and the children?
95
93
           But those depend on its position within a particular inventory, and
96
94
           it would be nice not to need to hold the backpointer here.
97
95
    """
98
 
 
99
 
    # TODO: split InventoryEntry into subclasses for files,
100
 
    # directories, etc etc.
101
 
 
102
 
    text_sha1 = None
103
 
    text_size = None
104
 
    
105
 
    def __init__(self, file_id, name, kind, parent_id, text_id=None):
 
96
    def __init__(self, file_id, name, kind='file', text_id=None,
 
97
                 parent_id=None):
106
98
        """Create an InventoryEntry
107
99
        
108
100
        The filename must be a single component, relative to the
109
101
        parent directory; it cannot be a whole path or relative name.
110
102
 
111
 
        >>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)
 
103
        >>> e = InventoryEntry('123', 'hello.c')
112
104
        >>> e.name
113
105
        'hello.c'
114
106
        >>> e.file_id
115
107
        '123'
116
 
        >>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)
 
108
        >>> e = InventoryEntry('123', 'src/hello.c')
117
109
        Traceback (most recent call last):
118
110
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
119
111
        """
120
 
        if '/' in name or '\\' in name:
121
 
            raise BzrCheckError('InventoryEntry name %r is invalid' % name)
 
112
        
 
113
        if len(splitpath(name)) != 1:
 
114
            bailout('InventoryEntry name is not a simple filename: %r'
 
115
                    % name)
122
116
        
123
117
        self.file_id = file_id
124
118
        self.name = name
 
119
        assert kind in ['file', 'directory']
125
120
        self.kind = kind
126
121
        self.text_id = text_id
127
122
        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
 
 
136
 
 
137
 
    def sorted_children(self):
138
 
        l = self.children.items()
139
 
        l.sort()
140
 
        return l
 
123
        self.text_sha1 = None
 
124
        self.text_size = None
141
125
 
142
126
 
143
127
    def copy(self):
144
128
        other = InventoryEntry(self.file_id, self.name, self.kind,
145
 
                               self.parent_id, text_id=self.text_id)
 
129
                               self.text_id, self.parent_id)
146
130
        other.text_sha1 = self.text_sha1
147
131
        other.text_size = self.text_size
148
132
        return other
165
149
        e.set('file_id', self.file_id)
166
150
        e.set('kind', self.kind)
167
151
 
168
 
        if self.text_size != None:
 
152
        if self.text_size is not None:
169
153
            e.set('text_size', '%d' % self.text_size)
170
154
            
171
 
        for f in ['text_id', 'text_sha1']:
 
155
        for f in ['text_id', 'text_sha1', 'parent_id']:
172
156
            v = getattr(self, f)
173
 
            if v != None:
 
157
            if v is not None:
174
158
                e.set(f, v)
175
159
 
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
160
        e.tail = '\n'
184
161
            
185
162
        return e
187
164
 
188
165
    def from_element(cls, elt):
189
166
        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)
 
167
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
199
168
        self.text_id = elt.get('text_id')
200
169
        self.text_sha1 = elt.get('text_sha1')
 
170
        self.parent_id = elt.get('parent_id')
201
171
        
202
172
        ## mutter("read inventoryentry: %r" % (elt.attrib))
203
173
 
225
195
 
226
196
 
227
197
 
228
 
class RootEntry(InventoryEntry):
229
 
    def __init__(self, file_id):
230
 
        self.file_id = file_id
231
 
        self.children = {}
232
 
        self.kind = 'root_directory'
233
 
        self.parent_id = None
234
 
        self.name = ''
235
 
 
236
 
    def __cmp__(self, other):
237
 
        if self is other:
238
 
            return 0
239
 
        if not isinstance(other, RootEntry):
240
 
            return NotImplemented
241
 
        return cmp(self.file_id, other.file_id) \
242
 
               or cmp(self.children, other.children)
243
 
 
244
 
 
245
 
 
246
198
class Inventory(XMLMixin):
247
199
    """Inventory of versioned files in a tree.
248
200
 
249
 
    This describes which file_id is present at each point in the tree,
250
 
    and possibly the SHA-1 or other information about the file.
251
 
    Entries can be looked up either by path or by file_id.
 
201
    An Inventory acts like a set of InventoryEntry items.  You can
 
202
    also look files up by their file_id or name.
 
203
    
 
204
    May be read from and written to a metadata file in a tree.  To
 
205
    manipulate the inventory (for example to add a file), it is read
 
206
    in, modified, and then written back out.
252
207
 
253
208
    The inventory represents a typical unix file tree, with
254
209
    directories containing files and subdirectories.  We never store
258
213
    returned quickly.
259
214
 
260
215
    InventoryEntry objects must not be modified after they are
261
 
    inserted, other than through the Inventory API.
 
216
    inserted.
262
217
 
263
218
    >>> inv = Inventory()
264
219
    >>> inv.write_xml(sys.stdout)
265
220
    <inventory>
266
221
    </inventory>
267
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
 
222
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
268
223
    >>> inv['123-123'].name
269
224
    'hello.c'
 
225
    >>> for file_id in inv: print file_id
 
226
    ...
 
227
    123-123
270
228
 
271
229
    May be treated as an iterator or set to look up file ids:
272
230
    
286
244
    </inventory>
287
245
 
288
246
    """
 
247
 
 
248
    ## TODO: Clear up handling of files in subdirectories; we probably
 
249
    ## do want to be able to just look them up by name but this
 
250
    ## probably means gradually walking down the path, looking up as we go.
 
251
 
 
252
    ## TODO: Make sure only canonical filenames are stored.
 
253
 
 
254
    ## TODO: Do something sensible about the possible collisions on
 
255
    ## case-losing filesystems.  Perhaps we should just always forbid
 
256
    ## such collisions.
 
257
 
 
258
    ## _tree should probably just be stored as
 
259
    ## InventoryEntry._children on each directory.
 
260
 
289
261
    def __init__(self):
290
262
        """Create or read an inventory.
291
263
 
292
264
        If a working directory is specified, the inventory is read
293
265
        from there.  If the file is specified, read from that. If not,
294
266
        the inventory is created empty.
295
 
 
296
 
        The inventory is created with a default root directory, with
297
 
        an id of None.
298
267
        """
299
 
        self.root = RootEntry(ROOT_ID)
300
 
        self._byid = {self.root.file_id: self.root}
 
268
        self._byid = dict()
 
269
 
 
270
        # _tree is indexed by parent_id; at each level a map from name
 
271
        # to ie.  The None entry is the root.
 
272
        self._tree = {None: {}}
301
273
 
302
274
 
303
275
    def __iter__(self):
309
281
        return len(self._byid)
310
282
 
311
283
 
312
 
    def iter_entries(self, from_dir=None):
 
284
    def iter_entries(self, parent_id=None):
313
285
        """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()
 
286
        kids = self._tree[parent_id].items()
321
287
        kids.sort()
322
288
        for name, ie in kids:
323
289
            yield name, ie
324
290
            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
 
291
                for cn, cie in self.iter_entries(parent_id=ie.file_id):
 
292
                    yield joinpath([name, cn]), cie
 
293
 
 
294
 
 
295
    def directories(self, include_root=True):
 
296
        """Return (path, entry) pairs for all directories.
 
297
        """
 
298
        if include_root:
 
299
            yield '', None
 
300
        for path, entry in self.iter_entries():
 
301
            if entry.kind == 'directory':
 
302
                yield path, entry
 
303
        
 
304
 
 
305
 
 
306
    def children(self, parent_id):
 
307
        """Return entries that are direct children of parent_id."""
 
308
        return self._tree[parent_id]
327
309
                    
328
310
 
329
311
 
330
 
    def directories(self):
331
 
        """Return (path, entry) pairs for all directories.
332
 
        """
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()
343
 
            
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
347
 
 
348
 
        for name, ie in descend(self.root):
349
 
            yield name, ie
350
 
        
 
312
    # TODO: return all paths and entries
351
313
 
352
314
 
353
315
    def __contains__(self, file_id):
354
316
        """True if this entry contains a file with given id.
355
317
 
356
318
        >>> inv = Inventory()
357
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
319
        >>> inv.add(InventoryEntry('123', 'foo.c'))
358
320
        >>> '123' in inv
359
321
        True
360
322
        >>> '456' in inv
367
329
        """Return the entry for given file_id.
368
330
 
369
331
        >>> inv = Inventory()
370
 
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
 
332
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
371
333
        >>> inv['123123'].name
372
334
        'hello.c'
373
335
        """
374
 
        try:
375
 
            return self._byid[file_id]
376
 
        except KeyError:
377
 
            if file_id == None:
378
 
                raise BzrError("can't look up file_id None")
379
 
            else:
380
 
                raise BzrError("file_id {%s} not in inventory" % file_id)
381
 
 
382
 
 
383
 
    def get_child(self, parent_id, filename):
384
 
        return self[parent_id].children.get(filename)
 
336
        return self._byid[file_id]
385
337
 
386
338
 
387
339
    def add(self, entry):
389
341
 
390
342
        To add  a file to a branch ready to be committed, use Branch.add,
391
343
        which calls this."""
392
 
        if entry.file_id in self._byid:
 
344
        if entry.file_id in self:
393
345
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
394
346
 
395
 
        try:
396
 
            parent = self._byid[entry.parent_id]
397
 
        except KeyError:
398
 
            bailout("parent_id {%s} not in inventory" % entry.parent_id)
399
 
 
400
 
        if parent.children.has_key(entry.name):
401
 
            bailout("%s is already versioned" %
402
 
                    appendpath(self.id2path(parent.file_id), entry.name))
 
347
        if entry.parent_id != None:
 
348
            if entry.parent_id not in self:
 
349
                bailout("parent_id %s of new entry not found in inventory"
 
350
                        % entry.parent_id)
 
351
            
 
352
        if self._tree[entry.parent_id].has_key(entry.name):
 
353
            bailout("%s is already versioned"
 
354
                    % appendpath(self.id2path(entry.parent_id), entry.name))
403
355
 
404
356
        self._byid[entry.file_id] = entry
405
 
        parent.children[entry.name] = entry
406
 
 
407
 
 
408
 
    def add_path(self, relpath, kind, file_id=None):
409
 
        """Add entry from a path.
410
 
 
411
 
        The immediate parent must already be versioned"""
412
 
        parts = bzrlib.osutils.splitpath(relpath)
413
 
        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)
423
 
        return self.add(ie)
 
357
        self._tree[entry.parent_id][entry.name] = entry
 
358
 
 
359
        if entry.kind == 'directory':
 
360
            self._tree[entry.file_id] = {}
424
361
 
425
362
 
426
363
    def __delitem__(self, file_id):
427
364
        """Remove entry by id.
428
365
 
429
366
        >>> inv = Inventory()
430
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
367
        >>> inv.add(InventoryEntry('123', 'foo.c'))
431
368
        >>> '123' in inv
432
369
        True
433
370
        >>> del inv['123']
436
373
        """
437
374
        ie = self[file_id]
438
375
 
439
 
        assert self[ie.parent_id].children[ie.name] == ie
 
376
        assert self._tree[ie.parent_id][ie.name] == ie
440
377
        
441
378
        # TODO: Test deleting all children; maybe hoist to a separate
442
379
        # deltree method?
443
380
        if ie.kind == 'directory':
444
 
            for cie in ie.children.values():
 
381
            for cie in self._tree[file_id].values():
445
382
                del self[cie.file_id]
446
 
            del ie.children
 
383
            del self._tree[file_id]
447
384
 
448
385
        del self._byid[file_id]
449
 
        del self[ie.parent_id].children[ie.name]
 
386
        del self._tree[ie.parent_id][ie.name]
450
387
 
451
388
 
452
389
    def id_set(self):
466
403
        """Construct from XML Element
467
404
 
468
405
        >>> inv = Inventory()
469
 
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
 
406
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
470
407
        >>> elt = inv.to_element()
471
408
        >>> inv2 = Inventory.from_element(elt)
472
409
        >>> inv2 == inv
488
425
        >>> i2 = Inventory()
489
426
        >>> i1 == i2
490
427
        True
491
 
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
428
        >>> i1.add(InventoryEntry('123', 'foo'))
492
429
        >>> i1 == i2
493
430
        False
494
 
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
431
        >>> i2.add(InventoryEntry('123', 'foo'))
495
432
        >>> i1 == i2
496
433
        True
497
434
        """
511
448
        return 0
512
449
 
513
450
 
514
 
    def get_idpath(self, file_id):
515
 
        """Return a list of file_ids for the path to an entry.
516
 
 
517
 
        The list contains one element for each directory followed by
518
 
        the id of the file itself.  So the length of the returned list
519
 
        is equal to the depth of the file in the tree, counting the
520
 
        root directory as depth 1.
521
 
        """
 
451
    def id2path(self, file_id):
 
452
        """Return as a list the path to file_id."""
522
453
        p = []
523
454
        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)
 
455
            ie = self[file_id]
 
456
            p = [ie.name] + p
529
457
            file_id = ie.parent_id
530
 
        return p
531
 
 
532
 
 
533
 
    def id2path(self, file_id):
534
 
        """Return as a list the path to file_id."""
535
 
 
536
 
        # 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)
 
458
        return joinpath(p)
539
459
            
540
460
 
541
461
 
547
467
 
548
468
        This returns the entry of the last component in the path,
549
469
        which may be either a file or a directory.
550
 
 
551
 
        Returns None iff the path is not found.
552
470
        """
553
 
        if isinstance(name, types.StringTypes):
554
 
            name = splitpath(name)
555
 
 
556
 
        mutter("lookup path %r" % name)
557
 
 
558
 
        parent = self.root
559
 
        for f in name:
 
471
        assert isinstance(name, types.StringTypes)
 
472
 
 
473
        parent_id = None
 
474
        for f in splitpath(name):
560
475
            try:
561
 
                cie = parent.children[f]
 
476
                cie = self._tree[parent_id][f]
562
477
                assert cie.name == f
563
 
                assert cie.parent_id == parent.file_id
564
 
                parent = cie
 
478
                parent_id = cie.file_id
565
479
            except KeyError:
566
480
                # or raise an error?
567
481
                return None
568
482
 
569
 
        return parent.file_id
 
483
        return parent_id
 
484
 
 
485
 
 
486
    def get_child(self, parent_id, child_name):
 
487
        return self._tree[parent_id].get(child_name)
570
488
 
571
489
 
572
490
    def has_filename(self, names):
574
492
 
575
493
 
576
494
    def has_id(self, file_id):
 
495
        assert isinstance(file_id, str)
577
496
        return self._byid.has_key(file_id)
578
497
 
579
498
 
580
 
    def rename(self, file_id, new_parent_id, new_name):
581
 
        """Move a file within the inventory.
582
 
 
583
 
        This can change either the name, or the parent, or both.
584
 
 
585
 
        This does not move the working file."""
586
 
        if not is_valid_name(new_name):
587
 
            bailout("not an acceptable filename: %r" % new_name)
588
 
 
589
 
        new_parent = self._byid[new_parent_id]
590
 
        if new_name in new_parent.children:
591
 
            bailout("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
592
 
 
593
 
        new_parent_idpath = self.get_idpath(new_parent_id)
594
 
        if file_id in new_parent_idpath:
595
 
            bailout("cannot move directory %r into a subdirectory of itself, %r"
596
 
                    % (self.id2path(file_id), self.id2path(new_parent_id)))
597
 
 
598
 
        file_ie = self._byid[file_id]
599
 
        old_parent = self._byid[file_ie.parent_id]
600
 
 
601
 
        # TODO: Don't leave things messed up if this fails
602
 
 
603
 
        del old_parent.children[file_ie.name]
604
 
        new_parent.children[new_name] = file_ie
605
 
        
606
 
        file_ie.name = new_name
607
 
        file_ie.parent_id = new_parent_id
608
 
 
609
 
 
610
 
 
611
 
 
612
 
_NAME_RE = re.compile(r'^[^/\\]+$')
613
 
 
614
 
def is_valid_name(name):
615
 
    return bool(_NAME_RE.match(name))
 
499
 
 
500
if __name__ == '__main__':
 
501
    import doctest, inventory
 
502
    doctest.testmod(inventory)