← 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-04-05 08:24:51 UTC
  • Revision ID: mbp@sourcefrog.net-20050405082451-408ebb0fd108440f
start adding quotes

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/inventory.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
 
 
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
 
 
 
17
"""Inventories map files to their name in a revision."""
 
18
 
 
19
# TODO: Maybe store inventory_id in the file?  Not really needed.
 
20
 
 
21
__copyright__ = "Copyright (C) 2005 Canonical Ltd."
 
22
__author__ = "Martin Pool <mbp@canonical.com>"
22
23
 
23
24
import sys, os.path, types, re
 
25
from sets import Set
24
26
 
25
27
try:
26
28
    from cElementTree import Element, ElementTree, SubElement
28
30
    from elementtree.ElementTree import Element, ElementTree, SubElement
29
31
 
30
32
from xml import XMLMixin
31
 
from errors import bailout, BzrError, BzrCheckError
 
33
from errors import bailout
32
34
 
33
35
import bzrlib
34
36
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
57
59
 
58
60
    >>> i = Inventory()
59
61
    >>> i.path2id('')
60
 
    'TREE_ROOT'
61
 
    >>> i.add(InventoryEntry('123', 'src', 'directory', ROOT_ID))
62
 
    >>> i.add(InventoryEntry('2323', 'hello.c', 'file', parent_id='123'))
 
62
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
 
63
    >>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))
63
64
    >>> for j in i.iter_entries():
64
65
    ...   print j
65
66
    ... 
66
 
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT'))
 
67
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
67
68
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
68
 
    >>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))
 
69
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
69
70
    Traceback (most recent call last):
70
71
    ...
71
72
    BzrError: ('inventory already contains entry with id {2323}', [])
72
 
    >>> i.add(InventoryEntry('2324', 'bye.c', 'file', '123'))
73
 
    >>> i.add(InventoryEntry('2325', 'wibble', 'directory', '123'))
 
73
    >>> i.add(InventoryEntry('2324', 'bye.c', parent_id='123'))
 
74
    >>> i.add(InventoryEntry('2325', 'wibble', parent_id='123', kind='directory'))
74
75
    >>> i.path2id('src/wibble')
75
76
    '2325'
76
77
    >>> '2325' in i
77
78
    True
78
 
    >>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))
 
79
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
79
80
    >>> i['2326']
80
81
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
81
82
    >>> for j in i.iter_entries():
90
91
    >>> i.id2path('2326')
91
92
    'src/wibble/wibble.c'
92
93
 
93
 
    TODO: Maybe also keep the full path of the entry, and the children?
 
94
    :todo: Maybe also keep the full path of the entry, and the children?
94
95
           But those depend on its position within a particular inventory, and
95
96
           it would be nice not to need to hold the backpointer here.
96
97
    """
97
 
 
98
 
    # TODO: split InventoryEntry into subclasses for files,
99
 
    # directories, etc etc.
100
 
 
101
 
    text_sha1 = None
102
 
    text_size = None
103
 
    
104
 
    def __init__(self, file_id, name, kind, parent_id, text_id=None):
 
98
    def __init__(self, file_id, name, kind='file', text_id=None,
 
99
                 parent_id=None):
105
100
        """Create an InventoryEntry
106
101
        
107
102
        The filename must be a single component, relative to the
108
103
        parent directory; it cannot be a whole path or relative name.
109
104
 
110
 
        >>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)
 
105
        >>> e = InventoryEntry('123', 'hello.c')
111
106
        >>> e.name
112
107
        'hello.c'
113
108
        >>> e.file_id
114
109
        '123'
115
 
        >>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)
 
110
        >>> e = InventoryEntry('123', 'src/hello.c')
116
111
        Traceback (most recent call last):
117
 
        BzrCheckError: InventoryEntry name 'src/hello.c' is invalid
 
112
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
118
113
        """
119
 
        if '/' in name or '\\' in name:
120
 
            raise BzrCheckError('InventoryEntry name %r is invalid' % name)
 
114
        
 
115
        if len(splitpath(name)) != 1:
 
116
            bailout('InventoryEntry name is not a simple filename: %r'
 
117
                    % name)
121
118
        
122
119
        self.file_id = file_id
123
120
        self.name = name
 
121
        assert kind in ['file', 'directory']
124
122
        self.kind = kind
125
123
        self.text_id = text_id
126
124
        self.parent_id = parent_id
 
125
        self.text_sha1 = None
 
126
        self.text_size = None
127
127
        if kind == 'directory':
128
128
            self.children = {}
129
 
        elif kind == 'file':
130
 
            pass
131
 
        else:
132
 
            raise BzrError("unhandled entry kind %r" % kind)
133
 
 
134
129
 
135
130
 
136
131
    def sorted_children(self):
141
136
 
142
137
    def copy(self):
143
138
        other = InventoryEntry(self.file_id, self.name, self.kind,
144
 
                               self.parent_id, text_id=self.text_id)
 
139
                               self.text_id, self.parent_id)
145
140
        other.text_sha1 = self.text_sha1
146
141
        other.text_size = self.text_size
147
 
        # note that children are *not* copied; they're pulled across when
148
 
        # others are added
149
142
        return other
150
143
 
151
144
 
166
159
        e.set('file_id', self.file_id)
167
160
        e.set('kind', self.kind)
168
161
 
169
 
        if self.text_size != None:
 
162
        if self.text_size is not None:
170
163
            e.set('text_size', '%d' % self.text_size)
171
164
            
172
 
        for f in ['text_id', 'text_sha1']:
 
165
        for f in ['text_id', 'text_sha1', 'parent_id']:
173
166
            v = getattr(self, f)
174
 
            if v != None:
 
167
            if v is not None:
175
168
                e.set(f, v)
176
169
 
177
 
        # to be conservative, we don't externalize the root pointers
178
 
        # for now, leaving them as null in the xml form.  in a future
179
 
        # version it will be implied by nested elements.
180
 
        if self.parent_id != ROOT_ID:
181
 
            assert isinstance(self.parent_id, basestring)
182
 
            e.set('parent_id', self.parent_id)
183
 
 
184
170
        e.tail = '\n'
185
171
            
186
172
        return e
188
174
 
189
175
    def from_element(cls, elt):
190
176
        assert elt.tag == 'entry'
191
 
 
192
 
        ## original format inventories don't have a parent_id for
193
 
        ## nodes in the root directory, but it's cleaner to use one
194
 
        ## internally.
195
 
        parent_id = elt.get('parent_id')
196
 
        if parent_id == None:
197
 
            parent_id = ROOT_ID
198
 
 
199
 
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'), parent_id)
 
177
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
200
178
        self.text_id = elt.get('text_id')
201
179
        self.text_sha1 = elt.get('text_sha1')
 
180
        self.parent_id = elt.get('parent_id')
202
181
        
203
182
        ## mutter("read inventoryentry: %r" % (elt.attrib))
204
183
 
210
189
 
211
190
    from_element = classmethod(from_element)
212
191
 
213
 
    def __eq__(self, other):
 
192
    def __cmp__(self, other):
 
193
        if self is other:
 
194
            return 0
214
195
        if not isinstance(other, InventoryEntry):
215
196
            return NotImplemented
216
197
 
217
 
        return (self.file_id == other.file_id) \
218
 
               and (self.name == other.name) \
219
 
               and (self.text_sha1 == other.text_sha1) \
220
 
               and (self.text_size == other.text_size) \
221
 
               and (self.text_id == other.text_id) \
222
 
               and (self.parent_id == other.parent_id) \
223
 
               and (self.kind == other.kind)
224
 
 
225
 
 
226
 
    def __ne__(self, other):
227
 
        return not (self == other)
228
 
 
229
 
    def __hash__(self):
230
 
        raise ValueError('not hashable')
 
198
        return cmp(self.file_id, other.file_id) \
 
199
               or cmp(self.name, other.name) \
 
200
               or cmp(self.text_sha1, other.text_sha1) \
 
201
               or cmp(self.text_size, other.text_size) \
 
202
               or cmp(self.text_id, other.text_id) \
 
203
               or cmp(self.parent_id, other.parent_id) \
 
204
               or cmp(self.kind, other.kind)
231
205
 
232
206
 
233
207
 
239
213
        self.parent_id = None
240
214
        self.name = ''
241
215
 
242
 
    def __eq__(self, other):
 
216
    def __cmp__(self, other):
 
217
        if self is other:
 
218
            return 0
243
219
        if not isinstance(other, RootEntry):
244
220
            return NotImplemented
245
 
        
246
 
        return (self.file_id == other.file_id) \
247
 
               and (self.children == other.children)
 
221
        return cmp(self.file_id, other.file_id) \
 
222
               or cmp(self.children, other.children)
248
223
 
249
224
 
250
225
 
251
226
class Inventory(XMLMixin):
252
227
    """Inventory of versioned files in a tree.
253
228
 
254
 
    This describes which file_id is present at each point in the tree,
255
 
    and possibly the SHA-1 or other information about the file.
256
 
    Entries can be looked up either by path or by file_id.
 
229
    An Inventory acts like a set of InventoryEntry items.  You can
 
230
    also look files up by their file_id or name.
 
231
    
 
232
    May be read from and written to a metadata file in a tree.  To
 
233
    manipulate the inventory (for example to add a file), it is read
 
234
    in, modified, and then written back out.
257
235
 
258
236
    The inventory represents a typical unix file tree, with
259
237
    directories containing files and subdirectories.  We never store
269
247
    >>> inv.write_xml(sys.stdout)
270
248
    <inventory>
271
249
    </inventory>
272
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
 
250
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
273
251
    >>> inv['123-123'].name
274
252
    'hello.c'
275
253
 
291
269
    </inventory>
292
270
 
293
271
    """
 
272
 
 
273
    ## TODO: Make sure only canonical filenames are stored.
 
274
 
 
275
    ## TODO: Do something sensible about the possible collisions on
 
276
    ## case-losing filesystems.  Perhaps we should just always forbid
 
277
    ## such collisions.
 
278
 
 
279
    ## TODO: No special cases for root, rather just give it a file id
 
280
    ## like everything else.
 
281
 
 
282
    ## TODO: Probably change XML serialization to use nesting
 
283
 
294
284
    def __init__(self):
295
285
        """Create or read an inventory.
296
286
 
301
291
        The inventory is created with a default root directory, with
302
292
        an id of None.
303
293
        """
304
 
        self.root = RootEntry(ROOT_ID)
305
 
        self._byid = {self.root.file_id: self.root}
 
294
        self.root = RootEntry(None)
 
295
        self._byid = {None: self.root}
306
296
 
307
297
 
308
298
    def __iter__(self):
328
318
            yield name, ie
329
319
            if ie.kind == 'directory':
330
320
                for cn, cie in self.iter_entries(from_dir=ie.file_id):
331
 
                    yield os.path.join(name, cn), cie
332
 
 
333
 
 
334
 
    def entries(self):
335
 
        """Return list of (path, ie) for all entries except the root.
336
 
 
337
 
        This may be faster than iter_entries.
 
321
                    yield '/'.join((name, cn)), cie
 
322
                    
 
323
 
 
324
 
 
325
    def directories(self, from_dir=None):
 
326
        """Return (path, entry) pairs for all directories.
338
327
        """
339
 
        accum = []
340
 
        def descend(dir_ie, dir_path):
341
 
            kids = dir_ie.children.items()
342
 
            kids.sort()
343
 
            for name, ie in kids:
344
 
                child_path = os.path.join(dir_path, name)
345
 
                accum.append((child_path, ie))
 
328
        def descend(parent_ie):
 
329
            parent_name = parent_ie.name
 
330
            yield parent_name, parent_ie
 
331
 
 
332
            # directory children in sorted order
 
333
            dn = []
 
334
            for ie in parent_ie.children.itervalues():
346
335
                if ie.kind == 'directory':
347
 
                    descend(ie, child_path)
348
 
 
349
 
        descend(self.root, '')
350
 
        return accum
351
 
 
352
 
 
353
 
    def directories(self):
354
 
        """Return (path, entry) pairs for all directories, including the root.
355
 
        """
356
 
        accum = []
357
 
        def descend(parent_ie, parent_path):
358
 
            accum.append((parent_path, parent_ie))
 
336
                    dn.append((ie.name, ie))
 
337
            dn.sort()
359
338
            
360
 
            kids = [(ie.name, ie) for ie in parent_ie.children.itervalues() if ie.kind == 'directory']
361
 
            kids.sort()
 
339
            for name, child_ie in dn:
 
340
                for sub_name, sub_ie in descend(child_ie):
 
341
                    yield appendpath(parent_name, sub_name), sub_ie
362
342
 
363
 
            for name, child_ie in kids:
364
 
                child_path = os.path.join(parent_path, name)
365
 
                descend(child_ie, child_path)
366
 
        descend(self.root, '')
367
 
        return accum
 
343
        for name, ie in descend(self.root):
 
344
            yield name, ie
368
345
        
369
346
 
370
347
 
372
349
        """True if this entry contains a file with given id.
373
350
 
374
351
        >>> inv = Inventory()
375
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
352
        >>> inv.add(InventoryEntry('123', 'foo.c'))
376
353
        >>> '123' in inv
377
354
        True
378
355
        >>> '456' in inv
385
362
        """Return the entry for given file_id.
386
363
 
387
364
        >>> inv = Inventory()
388
 
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
 
365
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
389
366
        >>> inv['123123'].name
390
367
        'hello.c'
391
368
        """
392
 
        try:
393
 
            return self._byid[file_id]
394
 
        except KeyError:
395
 
            if file_id == None:
396
 
                raise BzrError("can't look up file_id None")
397
 
            else:
398
 
                raise BzrError("file_id {%s} not in inventory" % file_id)
399
 
 
400
 
 
401
 
    def get_file_kind(self, file_id):
402
 
        return self._byid[file_id].kind
 
369
        return self._byid[file_id]
 
370
 
403
371
 
404
372
    def get_child(self, parent_id, filename):
405
373
        return self[parent_id].children.get(filename)
416
384
        try:
417
385
            parent = self._byid[entry.parent_id]
418
386
        except KeyError:
419
 
            bailout("parent_id {%s} not in inventory" % entry.parent_id)
 
387
            bailout("parent_id %r not in inventory" % entry.parent_id)
420
388
 
421
389
        if parent.children.has_key(entry.name):
422
390
            bailout("%s is already versioned" %
434
402
        if len(parts) == 0:
435
403
            bailout("cannot re-add root of inventory")
436
404
 
437
 
        if file_id == None:
 
405
        if file_id is None:
438
406
            file_id = bzrlib.branch.gen_file_id(relpath)
439
407
 
440
408
        parent_id = self.path2id(parts[:-1])
441
 
        assert parent_id != None
442
409
        ie = InventoryEntry(file_id, parts[-1],
443
410
                            kind=kind, parent_id=parent_id)
444
411
        return self.add(ie)
448
415
        """Remove entry by id.
449
416
 
450
417
        >>> inv = Inventory()
451
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
418
        >>> inv.add(InventoryEntry('123', 'foo.c'))
452
419
        >>> '123' in inv
453
420
        True
454
421
        >>> del inv['123']
470
437
        del self[ie.parent_id].children[ie.name]
471
438
 
472
439
 
 
440
    def id_set(self):
 
441
        return Set(self._byid)
 
442
 
 
443
 
473
444
    def to_element(self):
474
445
        """Convert to XML Element"""
475
446
        e = Element('inventory')
483
454
        """Construct from XML Element
484
455
 
485
456
        >>> inv = Inventory()
486
 
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
 
457
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
487
458
        >>> elt = inv.to_element()
488
459
        >>> inv2 = Inventory.from_element(elt)
489
460
        >>> inv2 == inv
498
469
    from_element = classmethod(from_element)
499
470
 
500
471
 
501
 
    def __eq__(self, other):
 
472
    def __cmp__(self, other):
502
473
        """Compare two sets by comparing their contents.
503
474
 
504
475
        >>> i1 = Inventory()
505
476
        >>> i2 = Inventory()
506
477
        >>> i1 == i2
507
478
        True
508
 
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
479
        >>> i1.add(InventoryEntry('123', 'foo'))
509
480
        >>> i1 == i2
510
481
        False
511
 
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
482
        >>> i2.add(InventoryEntry('123', 'foo'))
512
483
        >>> i1 == i2
513
484
        True
514
485
        """
 
486
        if self is other:
 
487
            return 0
 
488
        
515
489
        if not isinstance(other, Inventory):
516
490
            return NotImplemented
517
491
 
518
 
        if len(self._byid) != len(other._byid):
519
 
            # shortcut: obviously not the same
520
 
            return False
521
 
 
522
 
        return self._byid == other._byid
523
 
 
524
 
 
525
 
    def __ne__(self, other):
526
 
        return not (self == other)
527
 
 
528
 
 
529
 
    def __hash__(self):
530
 
        raise ValueError('not hashable')
531
 
 
532
 
 
533
 
 
534
 
    def get_idpath(self, file_id):
535
 
        """Return a list of file_ids for the path to an entry.
536
 
 
537
 
        The list contains one element for each directory followed by
538
 
        the id of the file itself.  So the length of the returned list
539
 
        is equal to the depth of the file in the tree, counting the
540
 
        root directory as depth 1.
541
 
        """
 
492
        if self.id_set() ^ other.id_set():
 
493
            return 1
 
494
 
 
495
        for file_id in self._byid:
 
496
            c = cmp(self[file_id], other[file_id])
 
497
            if c: return c
 
498
 
 
499
        return 0
 
500
 
 
501
 
 
502
    def id2path(self, file_id):
 
503
        """Return as a list the path to file_id."""
542
504
        p = []
543
505
        while file_id != None:
544
 
            try:
545
 
                ie = self._byid[file_id]
546
 
            except KeyError:
547
 
                bailout("file_id {%s} not found in inventory" % file_id)
548
 
            p.insert(0, ie.file_id)
 
506
            ie = self._byid[file_id]
 
507
            p.insert(0, ie.name)
549
508
            file_id = ie.parent_id
550
 
        return p
551
 
 
552
 
 
553
 
    def id2path(self, file_id):
554
 
        """Return as a list the path to file_id."""
555
 
 
556
 
        # get all names, skipping root
557
 
        p = [self[fid].name for fid in self.get_idpath(file_id)[1:]]
558
 
        return os.sep.join(p)
 
509
        return '/'.join(p)
559
510
            
560
511
 
561
512
 
567
518
 
568
519
        This returns the entry of the last component in the path,
569
520
        which may be either a file or a directory.
570
 
 
571
 
        Returns None iff the path is not found.
572
521
        """
573
522
        if isinstance(name, types.StringTypes):
574
523
            name = splitpath(name)
575
524
 
576
 
        mutter("lookup path %r" % name)
577
 
 
578
 
        parent = self.root
 
525
        parent = self[None]
579
526
        for f in name:
580
527
            try:
581
528
                cie = parent.children[f]
582
529
                assert cie.name == f
583
 
                assert cie.parent_id == parent.file_id
584
530
                parent = cie
585
531
            except KeyError:
586
532
                # or raise an error?
610
556
        if new_name in new_parent.children:
611
557
            bailout("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
612
558
 
613
 
        new_parent_idpath = self.get_idpath(new_parent_id)
614
 
        if file_id in new_parent_idpath:
615
 
            bailout("cannot move directory %r into a subdirectory of itself, %r"
616
 
                    % (self.id2path(file_id), self.id2path(new_parent_id)))
617
 
 
618
559
        file_ie = self._byid[file_id]
619
560
        old_parent = self._byid[file_ie.parent_id]
620
561
 
633
574
 
634
575
def is_valid_name(name):
635
576
    return bool(_NAME_RE.match(name))
 
577
 
 
578
 
 
579
 
 
580
if __name__ == '__main__':
 
581
    import doctest, inventory
 
582
    doctest.testmod(inventory)