← 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-06 03:20:15 UTC
  • Revision ID: mbp@sourcefrog.net-20050506032014-decf4918803147d2
- split out notes on storing annotations in revfiles

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/inventory.py
1
 
#! /usr/bin/env python
2
 
# -*- coding: UTF-8 -*-
 
1
# (C) 2005 Canonical Ltd
3
2
 
4
3
# This program is free software; you can redistribute it and/or modify
5
4
# it under the terms of the GNU General Public License as published by
15
14
# along with this program; if not, write to the Free Software
16
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
16
 
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
 
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
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
118
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
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
 
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
127
141
 
128
142
 
129
143
    def copy(self):
130
144
        other = InventoryEntry(self.file_id, self.name, self.kind,
131
 
                               self.text_id, self.parent_id)
 
145
                               self.parent_id, text_id=self.text_id)
132
146
        other.text_sha1 = self.text_sha1
133
147
        other.text_size = self.text_size
134
148
        return other
151
165
        e.set('file_id', self.file_id)
152
166
        e.set('kind', self.kind)
153
167
 
154
 
        if self.text_size is not None:
 
168
        if self.text_size != None:
155
169
            e.set('text_size', '%d' % self.text_size)
156
170
            
157
 
        for f in ['text_id', 'text_sha1', 'parent_id']:
 
171
        for f in ['text_id', 'text_sha1']:
158
172
            v = getattr(self, f)
159
 
            if v is not None:
 
173
            if v != None:
160
174
                e.set(f, v)
161
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
 
162
183
        e.tail = '\n'
163
184
            
164
185
        return e
166
187
 
167
188
    def from_element(cls, elt):
168
189
        assert elt.tag == 'entry'
169
 
        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)
170
199
        self.text_id = elt.get('text_id')
171
200
        self.text_sha1 = elt.get('text_sha1')
172
 
        self.parent_id = elt.get('parent_id')
173
201
        
174
202
        ## mutter("read inventoryentry: %r" % (elt.attrib))
175
203
 
197
225
 
198
226
 
199
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
 
200
246
class Inventory(XMLMixin):
201
247
    """Inventory of versioned files in a tree.
202
248
 
203
 
    An Inventory acts like a set of InventoryEntry items.  You can
204
 
    also look files up by their file_id or name.
205
 
    
206
 
    May be read from and written to a metadata file in a tree.  To
207
 
    manipulate the inventory (for example to add a file), it is read
208
 
    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.
209
252
 
210
253
    The inventory represents a typical unix file tree, with
211
254
    directories containing files and subdirectories.  We never store
215
258
    returned quickly.
216
259
 
217
260
    InventoryEntry objects must not be modified after they are
218
 
    inserted.
 
261
    inserted, other than through the Inventory API.
219
262
 
220
263
    >>> inv = Inventory()
221
264
    >>> inv.write_xml(sys.stdout)
222
265
    <inventory>
223
266
    </inventory>
224
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
 
267
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
225
268
    >>> inv['123-123'].name
226
269
    'hello.c'
227
 
    >>> for file_id in inv: print file_id
228
 
    ...
229
 
    123-123
230
270
 
231
271
    May be treated as an iterator or set to look up file ids:
232
272
    
246
286
    </inventory>
247
287
 
248
288
    """
249
 
 
250
 
    ## TODO: Clear up handling of files in subdirectories; we probably
251
 
    ## do want to be able to just look them up by name but this
252
 
    ## probably means gradually walking down the path, looking up as we go.
253
 
 
254
 
    ## TODO: Make sure only canonical filenames are stored.
255
 
 
256
 
    ## TODO: Do something sensible about the possible collisions on
257
 
    ## case-losing filesystems.  Perhaps we should just always forbid
258
 
    ## such collisions.
259
 
 
260
 
    ## _tree should probably just be stored as
261
 
    ## InventoryEntry._children on each directory.
262
 
 
263
289
    def __init__(self):
264
290
        """Create or read an inventory.
265
291
 
266
292
        If a working directory is specified, the inventory is read
267
293
        from there.  If the file is specified, read from that. If not,
268
294
        the inventory is created empty.
 
295
 
 
296
        The inventory is created with a default root directory, with
 
297
        an id of None.
269
298
        """
270
 
        self._byid = dict()
271
 
 
272
 
        # _tree is indexed by parent_id; at each level a map from name
273
 
        # to ie.  The None entry is the root.
274
 
        self._tree = {None: {}}
 
299
        self.root = RootEntry(ROOT_ID)
 
300
        self._byid = {self.root.file_id: self.root}
275
301
 
276
302
 
277
303
    def __iter__(self):
283
309
        return len(self._byid)
284
310
 
285
311
 
286
 
    def iter_entries(self, parent_id=None):
 
312
    def iter_entries(self, from_dir=None):
287
313
        """Return (path, entry) pairs, in order by name."""
288
 
        kids = self._tree[parent_id].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()
289
321
        kids.sort()
290
322
        for name, ie in kids:
291
323
            yield name, ie
292
324
            if ie.kind == 'directory':
293
 
                for cn, cie in self.iter_entries(parent_id=ie.file_id):
294
 
                    yield joinpath([name, cn]), cie
295
 
 
296
 
 
297
 
    def directories(self, include_root=True):
 
325
                for cn, cie in self.iter_entries(from_dir=ie.file_id):
 
326
                    yield os.path.join(name, cn), cie
 
327
                    
 
328
 
 
329
 
 
330
    def directories(self):
298
331
        """Return (path, entry) pairs for all directories.
299
332
        """
300
 
        if include_root:
301
 
            yield '', None
302
 
        for path, entry in self.iter_entries():
303
 
            if entry.kind == 'directory':
304
 
                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
305
350
        
306
351
 
307
352
 
308
 
    def children(self, parent_id):
309
 
        """Return entries that are direct children of parent_id."""
310
 
        return self._tree[parent_id]
311
 
                    
312
 
 
313
 
 
314
 
    # TODO: return all paths and entries
315
 
 
316
 
 
317
353
    def __contains__(self, file_id):
318
354
        """True if this entry contains a file with given id.
319
355
 
320
356
        >>> inv = Inventory()
321
 
        >>> inv.add(InventoryEntry('123', 'foo.c'))
 
357
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
322
358
        >>> '123' in inv
323
359
        True
324
360
        >>> '456' in inv
331
367
        """Return the entry for given file_id.
332
368
 
333
369
        >>> inv = Inventory()
334
 
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
 
370
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
335
371
        >>> inv['123123'].name
336
372
        'hello.c'
337
373
        """
338
 
        return self._byid[file_id]
 
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)
339
385
 
340
386
 
341
387
    def add(self, entry):
343
389
 
344
390
        To add  a file to a branch ready to be committed, use Branch.add,
345
391
        which calls this."""
346
 
        if entry.file_id in self:
 
392
        if entry.file_id in self._byid:
347
393
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
348
394
 
349
 
        if entry.parent_id != None:
350
 
            if entry.parent_id not in self:
351
 
                bailout("parent_id %s of new entry not found in inventory"
352
 
                        % entry.parent_id)
353
 
            
354
 
        if self._tree[entry.parent_id].has_key(entry.name):
355
 
            bailout("%s is already versioned"
356
 
                    % appendpath(self.id2path(entry.parent_id), entry.name))
 
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))
357
403
 
358
404
        self._byid[entry.file_id] = entry
359
 
        self._tree[entry.parent_id][entry.name] = entry
360
 
 
361
 
        if entry.kind == 'directory':
362
 
            self._tree[entry.file_id] = {}
 
405
        parent.children[entry.name] = entry
363
406
 
364
407
 
365
408
    def add_path(self, relpath, kind, file_id=None):
370
413
        if len(parts) == 0:
371
414
            bailout("cannot re-add root of inventory")
372
415
 
373
 
        if file_id is None:
 
416
        if file_id == None:
374
417
            file_id = bzrlib.branch.gen_file_id(relpath)
375
418
 
376
419
        parent_id = self.path2id(parts[:-1])
 
420
        assert parent_id != None
377
421
        ie = InventoryEntry(file_id, parts[-1],
378
422
                            kind=kind, parent_id=parent_id)
379
423
        return self.add(ie)
383
427
        """Remove entry by id.
384
428
 
385
429
        >>> inv = Inventory()
386
 
        >>> inv.add(InventoryEntry('123', 'foo.c'))
 
430
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
387
431
        >>> '123' in inv
388
432
        True
389
433
        >>> del inv['123']
392
436
        """
393
437
        ie = self[file_id]
394
438
 
395
 
        assert self._tree[ie.parent_id][ie.name] == ie
 
439
        assert self[ie.parent_id].children[ie.name] == ie
396
440
        
397
441
        # TODO: Test deleting all children; maybe hoist to a separate
398
442
        # deltree method?
399
443
        if ie.kind == 'directory':
400
 
            for cie in self._tree[file_id].values():
 
444
            for cie in ie.children.values():
401
445
                del self[cie.file_id]
402
 
            del self._tree[file_id]
 
446
            del ie.children
403
447
 
404
448
        del self._byid[file_id]
405
 
        del self._tree[ie.parent_id][ie.name]
 
449
        del self[ie.parent_id].children[ie.name]
406
450
 
407
451
 
408
452
    def id_set(self):
422
466
        """Construct from XML Element
423
467
 
424
468
        >>> inv = Inventory()
425
 
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
 
469
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
426
470
        >>> elt = inv.to_element()
427
471
        >>> inv2 = Inventory.from_element(elt)
428
472
        >>> inv2 == inv
444
488
        >>> i2 = Inventory()
445
489
        >>> i1 == i2
446
490
        True
447
 
        >>> i1.add(InventoryEntry('123', 'foo'))
 
491
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
448
492
        >>> i1 == i2
449
493
        False
450
 
        >>> i2.add(InventoryEntry('123', 'foo'))
 
494
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
451
495
        >>> i1 == i2
452
496
        True
453
497
        """
467
511
        return 0
468
512
 
469
513
 
470
 
    def id2path(self, file_id):
471
 
        """Return as a list the path to file_id."""
 
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
        """
472
522
        p = []
473
523
        while file_id != None:
474
 
            ie = self[file_id]
475
 
            p = [ie.name] + p
 
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)
476
529
            file_id = ie.parent_id
477
 
        return joinpath(p)
 
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)
478
539
            
479
540
 
480
541
 
486
547
 
487
548
        This returns the entry of the last component in the path,
488
549
        which may be either a file or a directory.
 
550
 
 
551
        Returns None iff the path is not found.
489
552
        """
490
553
        if isinstance(name, types.StringTypes):
491
554
            name = splitpath(name)
492
555
 
493
 
        parent_id = None
 
556
        mutter("lookup path %r" % name)
 
557
 
 
558
        parent = self.root
494
559
        for f in name:
495
560
            try:
496
 
                cie = self._tree[parent_id][f]
 
561
                cie = parent.children[f]
497
562
                assert cie.name == f
498
 
                parent_id = cie.file_id
 
563
                assert cie.parent_id == parent.file_id
 
564
                parent = cie
499
565
            except KeyError:
500
566
                # or raise an error?
501
567
                return None
502
568
 
503
 
        return parent_id
504
 
 
505
 
 
506
 
    def get_child(self, parent_id, child_name):
507
 
        return self._tree[parent_id].get(child_name)
 
569
        return parent.file_id
508
570
 
509
571
 
510
572
    def has_filename(self, names):
512
574
 
513
575
 
514
576
    def has_id(self, file_id):
515
 
        assert isinstance(file_id, str)
516
577
        return self._byid.has_key(file_id)
517
578
 
518
579
 
519
 
 
520
 
 
521
 
 
522
 
if __name__ == '__main__':
523
 
    import doctest, inventory
524
 
    doctest.testmod(inventory)
 
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))