← 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-25 03:24:47 UTC
  • Revision ID: mbp@sourcefrog.net-20050325032447-aef4d334620f490a
- don't flush the debug log file so often

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, 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
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
 
125
        self.text_sha1 = None
 
126
        self.text_size = None
141
127
 
142
128
 
143
129
    def copy(self):
144
130
        other = InventoryEntry(self.file_id, self.name, self.kind,
145
 
                               self.parent_id, text_id=self.text_id)
 
131
                               self.text_id, self.parent_id)
146
132
        other.text_sha1 = self.text_sha1
147
133
        other.text_size = self.text_size
148
134
        return other
165
151
        e.set('file_id', self.file_id)
166
152
        e.set('kind', self.kind)
167
153
 
168
 
        if self.text_size != None:
 
154
        if self.text_size is not None:
169
155
            e.set('text_size', '%d' % self.text_size)
170
156
            
171
 
        for f in ['text_id', 'text_sha1']:
 
157
        for f in ['text_id', 'text_sha1', 'parent_id']:
172
158
            v = getattr(self, f)
173
 
            if v != None:
 
159
            if v is not None:
174
160
                e.set(f, v)
175
161
 
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
162
        e.tail = '\n'
184
163
            
185
164
        return e
187
166
 
188
167
    def from_element(cls, elt):
189
168
        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)
 
169
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
199
170
        self.text_id = elt.get('text_id')
200
171
        self.text_sha1 = elt.get('text_sha1')
 
172
        self.parent_id = elt.get('parent_id')
201
173
        
202
174
        ## mutter("read inventoryentry: %r" % (elt.attrib))
203
175
 
225
197
 
226
198
 
227
199
 
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
200
class Inventory(XMLMixin):
247
201
    """Inventory of versioned files in a tree.
248
202
 
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.
 
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.
252
209
 
253
210
    The inventory represents a typical unix file tree, with
254
211
    directories containing files and subdirectories.  We never store
258
215
    returned quickly.
259
216
 
260
217
    InventoryEntry objects must not be modified after they are
261
 
    inserted, other than through the Inventory API.
 
218
    inserted.
262
219
 
263
220
    >>> inv = Inventory()
264
221
    >>> inv.write_xml(sys.stdout)
265
222
    <inventory>
266
223
    </inventory>
267
 
    >>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
 
224
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
268
225
    >>> inv['123-123'].name
269
226
    'hello.c'
 
227
    >>> for file_id in inv: print file_id
 
228
    ...
 
229
    123-123
270
230
 
271
231
    May be treated as an iterator or set to look up file ids:
272
232
    
286
246
    </inventory>
287
247
 
288
248
    """
 
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
 
289
263
    def __init__(self):
290
264
        """Create or read an inventory.
291
265
 
292
266
        If a working directory is specified, the inventory is read
293
267
        from there.  If the file is specified, read from that. If not,
294
268
        the inventory is created empty.
295
 
 
296
 
        The inventory is created with a default root directory, with
297
 
        an id of None.
298
269
        """
299
 
        self.root = RootEntry(ROOT_ID)
300
 
        self._byid = {self.root.file_id: self.root}
 
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: {}}
301
275
 
302
276
 
303
277
    def __iter__(self):
309
283
        return len(self._byid)
310
284
 
311
285
 
312
 
    def iter_entries(self, from_dir=None):
 
286
    def iter_entries(self, parent_id=None):
313
287
        """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()
 
288
        kids = self._tree[parent_id].items()
321
289
        kids.sort()
322
290
        for name, ie in kids:
323
291
            yield name, ie
324
292
            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
 
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):
 
298
        """Return (path, entry) pairs for all directories.
 
299
        """
 
300
        if include_root:
 
301
            yield '', None
 
302
        for path, entry in self.iter_entries():
 
303
            if entry.kind == 'directory':
 
304
                yield path, entry
 
305
        
 
306
 
 
307
 
 
308
    def children(self, parent_id):
 
309
        """Return entries that are direct children of parent_id."""
 
310
        return self._tree[parent_id]
327
311
                    
328
312
 
329
313
 
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
 
        
 
314
    # TODO: return all paths and entries
351
315
 
352
316
 
353
317
    def __contains__(self, file_id):
354
318
        """True if this entry contains a file with given id.
355
319
 
356
320
        >>> inv = Inventory()
357
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
321
        >>> inv.add(InventoryEntry('123', 'foo.c'))
358
322
        >>> '123' in inv
359
323
        True
360
324
        >>> '456' in inv
367
331
        """Return the entry for given file_id.
368
332
 
369
333
        >>> inv = Inventory()
370
 
        >>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
 
334
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
371
335
        >>> inv['123123'].name
372
336
        'hello.c'
373
337
        """
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
385
 
 
386
 
    def get_child(self, parent_id, filename):
387
 
        return self[parent_id].children.get(filename)
 
338
        return self._byid[file_id]
388
339
 
389
340
 
390
341
    def add(self, entry):
392
343
 
393
344
        To add  a file to a branch ready to be committed, use Branch.add,
394
345
        which calls this."""
395
 
        if entry.file_id in self._byid:
 
346
        if entry.file_id in self:
396
347
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
397
348
 
398
 
        try:
399
 
            parent = self._byid[entry.parent_id]
400
 
        except KeyError:
401
 
            bailout("parent_id {%s} not in inventory" % entry.parent_id)
402
 
 
403
 
        if parent.children.has_key(entry.name):
404
 
            bailout("%s is already versioned" %
405
 
                    appendpath(self.id2path(parent.file_id), entry.name))
 
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))
406
357
 
407
358
        self._byid[entry.file_id] = entry
408
 
        parent.children[entry.name] = entry
 
359
        self._tree[entry.parent_id][entry.name] = entry
 
360
 
 
361
        if entry.kind == 'directory':
 
362
            self._tree[entry.file_id] = {}
409
363
 
410
364
 
411
365
    def add_path(self, relpath, kind, file_id=None):
416
370
        if len(parts) == 0:
417
371
            bailout("cannot re-add root of inventory")
418
372
 
419
 
        if file_id == None:
 
373
        if file_id is None:
420
374
            file_id = bzrlib.branch.gen_file_id(relpath)
421
375
 
422
376
        parent_id = self.path2id(parts[:-1])
423
 
        assert parent_id != None
424
377
        ie = InventoryEntry(file_id, parts[-1],
425
378
                            kind=kind, parent_id=parent_id)
426
379
        return self.add(ie)
430
383
        """Remove entry by id.
431
384
 
432
385
        >>> inv = Inventory()
433
 
        >>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
 
386
        >>> inv.add(InventoryEntry('123', 'foo.c'))
434
387
        >>> '123' in inv
435
388
        True
436
389
        >>> del inv['123']
439
392
        """
440
393
        ie = self[file_id]
441
394
 
442
 
        assert self[ie.parent_id].children[ie.name] == ie
 
395
        assert self._tree[ie.parent_id][ie.name] == ie
443
396
        
444
397
        # TODO: Test deleting all children; maybe hoist to a separate
445
398
        # deltree method?
446
399
        if ie.kind == 'directory':
447
 
            for cie in ie.children.values():
 
400
            for cie in self._tree[file_id].values():
448
401
                del self[cie.file_id]
449
 
            del ie.children
 
402
            del self._tree[file_id]
450
403
 
451
404
        del self._byid[file_id]
452
 
        del self[ie.parent_id].children[ie.name]
 
405
        del self._tree[ie.parent_id][ie.name]
453
406
 
454
407
 
455
408
    def id_set(self):
469
422
        """Construct from XML Element
470
423
 
471
424
        >>> inv = Inventory()
472
 
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
 
425
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
473
426
        >>> elt = inv.to_element()
474
427
        >>> inv2 = Inventory.from_element(elt)
475
428
        >>> inv2 == inv
491
444
        >>> i2 = Inventory()
492
445
        >>> i1 == i2
493
446
        True
494
 
        >>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
447
        >>> i1.add(InventoryEntry('123', 'foo'))
495
448
        >>> i1 == i2
496
449
        False
497
 
        >>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
 
450
        >>> i2.add(InventoryEntry('123', 'foo'))
498
451
        >>> i1 == i2
499
452
        True
500
453
        """
514
467
        return 0
515
468
 
516
469
 
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
 
        """
 
470
    def id2path(self, file_id):
 
471
        """Return as a list the path to file_id."""
525
472
        p = []
526
473
        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)
 
474
            ie = self[file_id]
 
475
            p = [ie.name] + p
532
476
            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)
 
477
        return joinpath(p)
542
478
            
543
479
 
544
480
 
550
486
 
551
487
        This returns the entry of the last component in the path,
552
488
        which may be either a file or a directory.
553
 
 
554
 
        Returns None iff the path is not found.
555
489
        """
556
490
        if isinstance(name, types.StringTypes):
557
491
            name = splitpath(name)
558
492
 
559
 
        mutter("lookup path %r" % name)
560
 
 
561
 
        parent = self.root
 
493
        parent_id = None
562
494
        for f in name:
563
495
            try:
564
 
                cie = parent.children[f]
 
496
                cie = self._tree[parent_id][f]
565
497
                assert cie.name == f
566
 
                assert cie.parent_id == parent.file_id
567
 
                parent = cie
 
498
                parent_id = cie.file_id
568
499
            except KeyError:
569
500
                # or raise an error?
570
501
                return None
571
502
 
572
 
        return parent.file_id
 
503
        return parent_id
 
504
 
 
505
 
 
506
    def get_child(self, parent_id, child_name):
 
507
        return self._tree[parent_id].get(child_name)
573
508
 
574
509
 
575
510
    def has_filename(self, names):
577
512
 
578
513
 
579
514
    def has_id(self, file_id):
 
515
        assert isinstance(file_id, str)
580
516
        return self._byid.has_key(file_id)
581
517
 
582
518
 
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))
 
519
 
 
520
 
 
521
 
 
522
if __name__ == '__main__':
 
523
    import doctest, inventory
 
524
    doctest.testmod(inventory)