← 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-29 08:01:30 UTC
  • Revision ID: mbp@sourcefrog.net-20050329080130-89b78af279b196b3
match ignore patterns like ./config.h

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
 
 
22
 
 
23
 
import sys, os.path, types, re
 
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
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, BzrCheckError
 
33
from errors import bailout
33
34
 
34
35
import bzrlib
35
36
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
58
59
 
59
60
    >>> i = Inventory()
60
61
    >>> 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'))
 
62
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
 
63
    >>> i.add(InventoryEntry('2323', 'hello.c', 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='TREE_ROOT'))
 
67
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
68
68
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
69
 
    >>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))
 
69
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='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', 'file', '123'))
74
 
    >>> 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'))
75
75
    >>> i.path2id('src/wibble')
76
76
    '2325'
77
77
    >>> '2325' in i
78
78
    True
79
 
    >>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))
 
79
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='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
 
 
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):
 
98
    def __init__(self, file_id, name, kind='file', text_id=None,
 
99
                 parent_id=None):
106
100
        """Create an InventoryEntry
107
101
        
108
102
        The filename must be a single component, relative to the
109
103
        parent directory; it cannot be a whole path or relative name.
110
104
 
111
 
        >>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)
 
105
        >>> e = InventoryEntry('123', 'hello.c')
112
106
        >>> e.name
113
107
        'hello.c'
114
108
        >>> e.file_id
115
109
        '123'
116
 
        >>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)
 
110
        >>> e = InventoryEntry('123', 'src/hello.c')
117
111
        Traceback (most recent call last):
118
 
        BzrCheckError: InventoryEntry name 'src/hello.c' is invalid
 
112
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
119
113
        """
120
 
        if '/' in name or '\\' in name:
121
 
            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)
122
118
        
123
119
        self.file_id = file_id
124
120
        self.name = name
 
121
        assert kind in ['file', 'directory']
125
122
        self.kind = kind
126
123
        self.text_id = text_id
127
124
        self.parent_id = parent_id
 
125
        self.text_sha1 = None
 
126
        self.text_size = None
128
127
        if kind == 'directory':
129
128
            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
141
129
 
142
130
 
143
131
    def copy(self):
144
132
        other = InventoryEntry(self.file_id, self.name, self.kind,
145
 
                               self.parent_id, text_id=self.text_id)
 
133
                               self.text_id, self.parent_id)
146
134
        other.text_sha1 = self.text_sha1
147
135
        other.text_size = self.text_size
148
136
        return other
165
153
        e.set('file_id', self.file_id)
166
154
        e.set('kind', self.kind)
167
155
 
168
 
        if self.text_size != None:
 
156
        if self.text_size is not None:
169
157
            e.set('text_size', '%d' % self.text_size)
170
158
            
171
 
        for f in ['text_id', 'text_sha1']:
 
159
        for f in ['text_id', 'text_sha1', 'parent_id']:
172
160
            v = getattr(self, f)
173
 
            if v != None:
 
161
            if v is not None:
174
162
                e.set(f, v)
175
163
 
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
164
        e.tail = '\n'
184
165
            
185
166
        return e
187
168
 
188
169
    def from_element(cls, elt):
189
170
        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)
 
171
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
199
172
        self.text_id = elt.get('text_id')
200
173
        self.text_sha1 = elt.get('text_sha1')
 
174
        self.parent_id = elt.get('parent_id')
201
175
        
202
176
        ## mutter("read inventoryentry: %r" % (elt.attrib))
203
177
 
225
199
 
226
200
 
227
201
 
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
202
class Inventory(XMLMixin):
247
203
    """Inventory of versioned files in a tree.
248
204
 
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.
 
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.
252
211
 
253
212
    The inventory represents a typical unix file tree, with
254
213
    directories containing files and subdirectories.  We never store
258
217
    returned quickly.
259
218
 
260
219
    InventoryEntry objects must not be modified after they are
261
 
    inserted, other than through the Inventory API.
 
220
    inserted.
262
221
 
263
222
    >>> inv = Inventory()
264
223
    >>> inv.write_xml(sys.stdout)
265
224
    <inventory>
266
225
    </inventory>
267
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
 
226
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
268
227
    >>> inv['123-123'].name
269
228
    'hello.c'
270
229
 
286
245
    </inventory>
287
246
 
288
247
    """
 
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
 
289
260
    def __init__(self):
290
261
        """Create or read an inventory.
291
262
 
292
263
        If a working directory is specified, the inventory is read
293
264
        from there.  If the file is specified, read from that. If not,
294
265
        the inventory is created empty.
295
 
 
296
 
        The inventory is created with a default root directory, with
297
 
        an id of None.
298
266
        """
299
 
        self.root = RootEntry(ROOT_ID)
300
 
        self._byid = {self.root.file_id: self.root}
 
267
        self._root = InventoryEntry(None, '', kind='directory')
 
268
        self._byid = {None: self._root}
301
269
 
302
270
 
303
271
    def __iter__(self):
309
277
        return len(self._byid)
310
278
 
311
279
 
312
 
    def iter_entries(self, from_dir=None):
 
280
    def iter_entries(self, parent_id=None):
313
281
        """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()
 
282
        kids = self[parent_id].children.items()
321
283
        kids.sort()
322
284
        for name, ie in kids:
323
285
            yield name, ie
324
286
            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
327
 
                    
 
287
                for cn, cie in self.iter_entries(parent_id=ie.file_id):
 
288
                    yield joinpath([name, cn]), cie
328
289
 
329
290
 
330
291
    def directories(self):
331
292
        """Return (path, entry) pairs for all directories.
332
293
        """
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
 
294
        yield '', self._root
 
295
        for path, entry in self.iter_entries():
 
296
            if entry.kind == 'directory':
 
297
                yield path, entry
350
298
        
351
299
 
352
300
 
354
302
        """True if this entry contains a file with given id.
355
303
 
356
304
        >>> inv = Inventory()
357
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
305
        >>> inv.add(InventoryEntry('123', 'foo.c'))
358
306
        >>> '123' in inv
359
307
        True
360
308
        >>> '456' in inv
367
315
        """Return the entry for given file_id.
368
316
 
369
317
        >>> inv = Inventory()
370
 
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
 
318
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
371
319
        >>> inv['123123'].name
372
320
        'hello.c'
373
321
        """
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
 
322
        return self._byid[file_id]
 
323
 
385
324
 
386
325
    def get_child(self, parent_id, filename):
387
 
        return self[parent_id].children.get(filename)
 
326
        if parent_id == None:
 
327
            return self._root.children.get(filename)
 
328
        else:
 
329
            return self[parent_id].children.get(filename)
388
330
 
389
331
 
390
332
    def add(self, entry):
395
337
        if entry.file_id in self._byid:
396
338
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
397
339
 
398
 
        try:
399
 
            parent = self._byid[entry.parent_id]
400
 
        except KeyError:
401
 
            bailout("parent_id {%s} not in inventory" % entry.parent_id)
 
340
        parent = self._byid[entry.parent_id]
 
341
        if parent.kind != 'directory':
 
342
            bailout("attempt to add under non-directory {%s}" % parent.file_id)
402
343
 
403
344
        if parent.children.has_key(entry.name):
404
345
            bailout("%s is already versioned" %
416
357
        if len(parts) == 0:
417
358
            bailout("cannot re-add root of inventory")
418
359
 
419
 
        if file_id == None:
 
360
        if file_id is None:
420
361
            file_id = bzrlib.branch.gen_file_id(relpath)
421
362
 
422
363
        parent_id = self.path2id(parts[:-1])
423
 
        assert parent_id != None
424
364
        ie = InventoryEntry(file_id, parts[-1],
425
365
                            kind=kind, parent_id=parent_id)
426
366
        return self.add(ie)
430
370
        """Remove entry by id.
431
371
 
432
372
        >>> inv = Inventory()
433
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
373
        >>> inv.add(InventoryEntry('123', 'foo.c'))
434
374
        >>> '123' in inv
435
375
        True
436
376
        >>> del inv['123']
469
409
        """Construct from XML Element
470
410
 
471
411
        >>> inv = Inventory()
472
 
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
 
412
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
473
413
        >>> elt = inv.to_element()
474
414
        >>> inv2 = Inventory.from_element(elt)
475
415
        >>> inv2 == inv
491
431
        >>> i2 = Inventory()
492
432
        >>> i1 == i2
493
433
        True
494
 
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
434
        >>> i1.add(InventoryEntry('123', 'foo'))
495
435
        >>> i1 == i2
496
436
        False
497
 
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
437
        >>> i2.add(InventoryEntry('123', 'foo'))
498
438
        >>> i1 == i2
499
439
        True
500
440
        """
514
454
        return 0
515
455
 
516
456
 
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
 
        """
 
457
    def id2path(self, file_id):
 
458
        """Return as a list the path to file_id."""
525
459
        p = []
526
460
        while file_id != None:
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)
 
461
            ie = self[file_id]
 
462
            p = [ie.name] + p
532
463
            file_id = ie.parent_id
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)
 
464
        return joinpath(p)
542
465
            
543
466
 
544
467
 
550
473
 
551
474
        This returns the entry of the last component in the path,
552
475
        which may be either a file or a directory.
553
 
 
554
 
        Returns None iff the path is not found.
555
476
        """
556
477
        if isinstance(name, types.StringTypes):
557
478
            name = splitpath(name)
558
479
 
559
 
        mutter("lookup path %r" % name)
560
 
 
561
 
        parent = self.root
 
480
        parent = self[None]
562
481
        for f in name:
563
482
            try:
564
483
                cie = parent.children[f]
565
484
                assert cie.name == f
566
 
                assert cie.parent_id == parent.file_id
567
485
                parent = cie
568
486
            except KeyError:
569
487
                # or raise an error?
577
495
 
578
496
 
579
497
    def has_id(self, file_id):
 
498
        assert isinstance(file_id, str)
580
499
        return self._byid.has_key(file_id)
581
500
 
582
501
 
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))
 
502
 
 
503
 
 
504
 
 
505
if __name__ == '__main__':
 
506
    import doctest, inventory
 
507
    doctest.testmod(inventory)