← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Martin Pool
  • Date: 2005-05-12 02:14:35 UTC
  • Revision ID: mbp@sourcefrog.net-20050512021435-87fa19f051842647
- new helper function kind_marker()

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
 
"""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>"
23
 
 
24
 
import sys, os.path, types
 
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
25
24
from sets import Set
26
25
 
27
26
try:
30
29
    from elementtree.ElementTree import Element, ElementTree, SubElement
31
30
 
32
31
from xml import XMLMixin
33
 
from errors import bailout
 
32
from errors import bailout, BzrError, BzrCheckError
34
33
 
35
34
import bzrlib
36
35
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
59
58
 
60
59
    >>> i = Inventory()
61
60
    >>> i.path2id('')
62
 
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
63
 
    >>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))
 
61
    'TREE_ROOT'
 
62
    >>> i.add(InventoryEntry('123', 'src', 'directory', ROOT_ID))
 
63
    >>> i.add(InventoryEntry('2323', 'hello.c', 'file', parent_id='123'))
64
64
    >>> for j in i.iter_entries():
65
65
    ...   print j
66
66
    ... 
67
 
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
 
67
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT'))
68
68
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
69
 
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
 
69
    >>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))
70
70
    Traceback (most recent call last):
71
71
    ...
72
72
    BzrError: ('inventory already contains entry with id {2323}', [])
73
 
    >>> i.add(InventoryEntry('2324', 'bye.c', parent_id='123'))
74
 
    >>> i.add(InventoryEntry('2325', 'wibble', parent_id='123', kind='directory'))
 
73
    >>> i.add(InventoryEntry('2324', 'bye.c', 'file', '123'))
 
74
    >>> i.add(InventoryEntry('2325', 'wibble', 'directory', '123'))
75
75
    >>> i.path2id('src/wibble')
76
76
    '2325'
77
77
    >>> '2325' in i
78
78
    True
79
 
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
 
79
    >>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))
80
80
    >>> i['2326']
81
81
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
82
82
    >>> for j in i.iter_entries():
91
91
    >>> i.id2path('2326')
92
92
    'src/wibble/wibble.c'
93
93
 
94
 
    :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?
95
95
           But those depend on its position within a particular inventory, and
96
96
           it would be nice not to need to hold the backpointer here.
97
97
    """
98
 
    def __init__(self, file_id, name, kind='file', text_id=None,
99
 
                 parent_id=None):
 
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):
100
106
        """Create an InventoryEntry
101
107
        
102
108
        The filename must be a single component, relative to the
103
109
        parent directory; it cannot be a whole path or relative name.
104
110
 
105
 
        >>> e = InventoryEntry('123', 'hello.c')
 
111
        >>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)
106
112
        >>> e.name
107
113
        'hello.c'
108
114
        >>> e.file_id
109
115
        '123'
110
 
        >>> e = InventoryEntry('123', 'src/hello.c')
 
116
        >>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)
111
117
        Traceback (most recent call last):
112
 
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
 
118
        BzrCheckError: InventoryEntry name 'src/hello.c' is invalid
113
119
        """
114
 
        
115
 
        if len(splitpath(name)) != 1:
116
 
            bailout('InventoryEntry name is not a simple filename: %r'
117
 
                    % name)
 
120
        if '/' in name or '\\' in name:
 
121
            raise BzrCheckError('InventoryEntry name %r is invalid' % name)
118
122
        
119
123
        self.file_id = file_id
120
124
        self.name = name
121
 
        assert kind in ['file', 'directory']
122
125
        self.kind = kind
123
126
        self.text_id = text_id
124
127
        self.parent_id = parent_id
125
 
        self.text_sha1 = None
126
 
        self.text_size = None
127
128
        if kind == 'directory':
128
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
129
141
 
130
142
 
131
143
    def copy(self):
132
144
        other = InventoryEntry(self.file_id, self.name, self.kind,
133
 
                               self.text_id, self.parent_id)
 
145
                               self.parent_id, text_id=self.text_id)
134
146
        other.text_sha1 = self.text_sha1
135
147
        other.text_size = self.text_size
136
148
        return other
153
165
        e.set('file_id', self.file_id)
154
166
        e.set('kind', self.kind)
155
167
 
156
 
        if self.text_size is not None:
 
168
        if self.text_size != None:
157
169
            e.set('text_size', '%d' % self.text_size)
158
170
            
159
 
        for f in ['text_id', 'text_sha1', 'parent_id']:
 
171
        for f in ['text_id', 'text_sha1']:
160
172
            v = getattr(self, f)
161
 
            if v is not None:
 
173
            if v != None:
162
174
                e.set(f, v)
163
175
 
 
176
        # to be conservative, we don't externalize the root pointers
 
177
        # for now, leaving them as null in the xml form.  in a future
 
178
        # version it will be implied by nested elements.
 
179
        if self.parent_id != ROOT_ID:
 
180
            assert isinstance(self.parent_id, basestring)
 
181
            e.set('parent_id', self.parent_id)
 
182
 
164
183
        e.tail = '\n'
165
184
            
166
185
        return e
168
187
 
169
188
    def from_element(cls, elt):
170
189
        assert elt.tag == 'entry'
171
 
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
 
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)
172
199
        self.text_id = elt.get('text_id')
173
200
        self.text_sha1 = elt.get('text_sha1')
174
 
        self.parent_id = elt.get('parent_id')
175
201
        
176
202
        ## mutter("read inventoryentry: %r" % (elt.attrib))
177
203
 
199
225
 
200
226
 
201
227
 
 
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
 
202
246
class Inventory(XMLMixin):
203
247
    """Inventory of versioned files in a tree.
204
248
 
205
 
    An Inventory acts like a set of InventoryEntry items.  You can
206
 
    also look files up by their file_id or name.
207
 
    
208
 
    May be read from and written to a metadata file in a tree.  To
209
 
    manipulate the inventory (for example to add a file), it is read
210
 
    in, modified, and then written back out.
 
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.
211
252
 
212
253
    The inventory represents a typical unix file tree, with
213
254
    directories containing files and subdirectories.  We never store
217
258
    returned quickly.
218
259
 
219
260
    InventoryEntry objects must not be modified after they are
220
 
    inserted.
 
261
    inserted, other than through the Inventory API.
221
262
 
222
263
    >>> inv = Inventory()
223
264
    >>> inv.write_xml(sys.stdout)
224
265
    <inventory>
225
266
    </inventory>
226
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
 
267
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
227
268
    >>> inv['123-123'].name
228
269
    'hello.c'
229
270
 
245
286
    </inventory>
246
287
 
247
288
    """
248
 
 
249
 
    ## TODO: Make sure only canonical filenames are stored.
250
 
 
251
 
    ## TODO: Do something sensible about the possible collisions on
252
 
    ## case-losing filesystems.  Perhaps we should just always forbid
253
 
    ## such collisions.
254
 
 
255
 
    ## TODO: No special cases for root, rather just give it a file id
256
 
    ## like everything else.
257
 
 
258
 
    ## TODO: Probably change XML serialization to use nesting
259
 
 
260
289
    def __init__(self):
261
290
        """Create or read an inventory.
262
291
 
263
292
        If a working directory is specified, the inventory is read
264
293
        from there.  If the file is specified, read from that. If not,
265
294
        the inventory is created empty.
 
295
 
 
296
        The inventory is created with a default root directory, with
 
297
        an id of None.
266
298
        """
267
 
        self._root = InventoryEntry(None, '', kind='directory')
268
 
        self._byid = {None: self._root}
 
299
        self.root = RootEntry(ROOT_ID)
 
300
        self._byid = {self.root.file_id: self.root}
269
301
 
270
302
 
271
303
    def __iter__(self):
277
309
        return len(self._byid)
278
310
 
279
311
 
280
 
    def iter_entries(self, parent_id=None):
 
312
    def iter_entries(self, from_dir=None):
281
313
        """Return (path, entry) pairs, in order by name."""
282
 
        kids = self[parent_id].children.items()
 
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()
283
321
        kids.sort()
284
322
        for name, ie in kids:
285
323
            yield name, ie
286
324
            if ie.kind == 'directory':
287
 
                for cn, cie in self.iter_entries(parent_id=ie.file_id):
288
 
                    yield joinpath([name, cn]), cie
 
325
                for cn, cie in self.iter_entries(from_dir=ie.file_id):
 
326
                    yield os.path.join(name, cn), cie
 
327
                    
289
328
 
290
329
 
291
330
    def directories(self):
292
331
        """Return (path, entry) pairs for all directories.
293
332
        """
294
 
        yield '', self._root
295
 
        for path, entry in self.iter_entries():
296
 
            if entry.kind == 'directory':
297
 
                yield path, entry
 
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
298
350
        
299
351
 
300
352
 
302
354
        """True if this entry contains a file with given id.
303
355
 
304
356
        >>> inv = Inventory()
305
 
        >>> inv.add(InventoryEntry('123', 'foo.c'))
 
357
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
306
358
        >>> '123' in inv
307
359
        True
308
360
        >>> '456' in inv
315
367
        """Return the entry for given file_id.
316
368
 
317
369
        >>> inv = Inventory()
318
 
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
 
370
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
319
371
        >>> inv['123123'].name
320
372
        'hello.c'
321
373
        """
322
 
        return self._byid[file_id]
323
 
 
 
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_file_kind(self, file_id):
 
384
        return self._byid[file_id].kind
324
385
 
325
386
    def get_child(self, parent_id, filename):
326
 
        if parent_id == None:
327
 
            return self._root.children.get(filename)
328
 
        else:
329
 
            return self[parent_id].children.get(filename)
 
387
        return self[parent_id].children.get(filename)
330
388
 
331
389
 
332
390
    def add(self, entry):
337
395
        if entry.file_id in self._byid:
338
396
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
339
397
 
340
 
        parent = self._byid[entry.parent_id]
341
 
        if parent.kind != 'directory':
342
 
            bailout("attempt to add under non-directory {%s}" % parent.file_id)
 
398
        try:
 
399
            parent = self._byid[entry.parent_id]
 
400
        except KeyError:
 
401
            bailout("parent_id {%s} not in inventory" % entry.parent_id)
343
402
 
344
403
        if parent.children.has_key(entry.name):
345
404
            bailout("%s is already versioned" %
357
416
        if len(parts) == 0:
358
417
            bailout("cannot re-add root of inventory")
359
418
 
360
 
        if file_id is None:
 
419
        if file_id == None:
361
420
            file_id = bzrlib.branch.gen_file_id(relpath)
362
421
 
363
422
        parent_id = self.path2id(parts[:-1])
 
423
        assert parent_id != None
364
424
        ie = InventoryEntry(file_id, parts[-1],
365
425
                            kind=kind, parent_id=parent_id)
366
426
        return self.add(ie)
370
430
        """Remove entry by id.
371
431
 
372
432
        >>> inv = Inventory()
373
 
        >>> inv.add(InventoryEntry('123', 'foo.c'))
 
433
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
374
434
        >>> '123' in inv
375
435
        True
376
436
        >>> del inv['123']
409
469
        """Construct from XML Element
410
470
 
411
471
        >>> inv = Inventory()
412
 
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
 
472
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
413
473
        >>> elt = inv.to_element()
414
474
        >>> inv2 = Inventory.from_element(elt)
415
475
        >>> inv2 == inv
431
491
        >>> i2 = Inventory()
432
492
        >>> i1 == i2
433
493
        True
434
 
        >>> i1.add(InventoryEntry('123', 'foo'))
 
494
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
435
495
        >>> i1 == i2
436
496
        False
437
 
        >>> i2.add(InventoryEntry('123', 'foo'))
 
497
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
438
498
        >>> i1 == i2
439
499
        True
440
500
        """
454
514
        return 0
455
515
 
456
516
 
457
 
    def id2path(self, file_id):
458
 
        """Return as a list the path to file_id."""
 
517
    def get_idpath(self, file_id):
 
518
        """Return a list of file_ids for the path to an entry.
 
519
 
 
520
        The list contains one element for each directory followed by
 
521
        the id of the file itself.  So the length of the returned list
 
522
        is equal to the depth of the file in the tree, counting the
 
523
        root directory as depth 1.
 
524
        """
459
525
        p = []
460
526
        while file_id != None:
461
 
            ie = self[file_id]
462
 
            p = [ie.name] + p
 
527
            try:
 
528
                ie = self._byid[file_id]
 
529
            except KeyError:
 
530
                bailout("file_id {%s} not found in inventory" % file_id)
 
531
            p.insert(0, ie.file_id)
463
532
            file_id = ie.parent_id
464
 
        return joinpath(p)
 
533
        return p
 
534
 
 
535
 
 
536
    def id2path(self, file_id):
 
537
        """Return as a list the path to file_id."""
 
538
 
 
539
        # get all names, skipping root
 
540
        p = [self[fid].name for fid in self.get_idpath(file_id)[1:]]
 
541
        return os.sep.join(p)
465
542
            
466
543
 
467
544
 
473
550
 
474
551
        This returns the entry of the last component in the path,
475
552
        which may be either a file or a directory.
 
553
 
 
554
        Returns None iff the path is not found.
476
555
        """
477
556
        if isinstance(name, types.StringTypes):
478
557
            name = splitpath(name)
479
558
 
480
 
        parent = self[None]
 
559
        mutter("lookup path %r" % name)
 
560
 
 
561
        parent = self.root
481
562
        for f in name:
482
563
            try:
483
564
                cie = parent.children[f]
484
565
                assert cie.name == f
 
566
                assert cie.parent_id == parent.file_id
485
567
                parent = cie
486
568
            except KeyError:
487
569
                # or raise an error?
495
577
 
496
578
 
497
579
    def has_id(self, file_id):
498
 
        assert isinstance(file_id, str)
499
580
        return self._byid.has_key(file_id)
500
581
 
501
582
 
502
 
 
503
 
 
504
 
 
505
 
if __name__ == '__main__':
506
 
    import doctest, inventory
507
 
    doctest.testmod(inventory)
 
583
    def rename(self, file_id, new_parent_id, new_name):
 
584
        """Move a file within the inventory.
 
585
 
 
586
        This can change either the name, or the parent, or both.
 
587
 
 
588
        This does not move the working file."""
 
589
        if not is_valid_name(new_name):
 
590
            bailout("not an acceptable filename: %r" % new_name)
 
591
 
 
592
        new_parent = self._byid[new_parent_id]
 
593
        if new_name in new_parent.children:
 
594
            bailout("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
 
595
 
 
596
        new_parent_idpath = self.get_idpath(new_parent_id)
 
597
        if file_id in new_parent_idpath:
 
598
            bailout("cannot move directory %r into a subdirectory of itself, %r"
 
599
                    % (self.id2path(file_id), self.id2path(new_parent_id)))
 
600
 
 
601
        file_ie = self._byid[file_id]
 
602
        old_parent = self._byid[file_ie.parent_id]
 
603
 
 
604
        # TODO: Don't leave things messed up if this fails
 
605
 
 
606
        del old_parent.children[file_ie.name]
 
607
        new_parent.children[new_name] = file_ie
 
608
        
 
609
        file_ie.name = new_name
 
610
        file_ie.parent_id = new_parent_id
 
611
 
 
612
 
 
613
 
 
614
 
 
615
_NAME_RE = re.compile(r'^[^/\\]+$')
 
616
 
 
617
def is_valid_name(name):
 
618
    return bool(_NAME_RE.match(name))