~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-04 09:50:24 UTC
  • Revision ID: mbp@sourcefrog.net-20050404095024-4646dbcc42eada9e
workaround for python2.3 difflib bug

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
# (C) 2005 Canonical Ltd
 
2
 
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
 
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
 
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
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, re
 
25
from sets import Set
 
26
 
 
27
try:
 
28
    from cElementTree import Element, ElementTree, SubElement
 
29
except ImportError:
 
30
    from elementtree.ElementTree import Element, ElementTree, SubElement
 
31
 
 
32
from xml import XMLMixin
 
33
from errors import bailout
 
34
 
 
35
import bzrlib
 
36
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
 
37
from bzrlib.trace import mutter
 
38
 
 
39
class InventoryEntry(XMLMixin):
 
40
    """Description of a versioned file.
 
41
 
 
42
    An InventoryEntry has the following fields, which are also
 
43
    present in the XML inventory-entry element:
 
44
 
 
45
    * *file_id*
 
46
    * *name*: (only the basename within the directory, must not
 
47
      contain slashes)
 
48
    * *kind*: "directory" or "file"
 
49
    * *directory_id*: (if absent/null means the branch root directory)
 
50
    * *text_sha1*: only for files
 
51
    * *text_size*: in bytes, only for files 
 
52
    * *text_id*: identifier for the text version, only for files
 
53
 
 
54
    InventoryEntries can also exist inside a WorkingTree
 
55
    inventory, in which case they are not yet bound to a
 
56
    particular revision of the file.  In that case the text_sha1,
 
57
    text_size and text_id are absent.
 
58
 
 
59
 
 
60
    >>> i = Inventory()
 
61
    >>> i.path2id('')
 
62
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
 
63
    >>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))
 
64
    >>> for j in i.iter_entries():
 
65
    ...   print j
 
66
    ... 
 
67
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
 
68
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
 
69
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
 
70
    Traceback (most recent call last):
 
71
    ...
 
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'))
 
75
    >>> i.path2id('src/wibble')
 
76
    '2325'
 
77
    >>> '2325' in i
 
78
    True
 
79
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
 
80
    >>> i['2326']
 
81
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
 
82
    >>> for j in i.iter_entries():
 
83
    ...     print j[0]
 
84
    ...     assert i.path2id(j[0])
 
85
    ... 
 
86
    src
 
87
    src/bye.c
 
88
    src/hello.c
 
89
    src/wibble
 
90
    src/wibble/wibble.c
 
91
    >>> i.id2path('2326')
 
92
    'src/wibble/wibble.c'
 
93
 
 
94
    :todo: Maybe also keep the full path of the entry, and the children?
 
95
           But those depend on its position within a particular inventory, and
 
96
           it would be nice not to need to hold the backpointer here.
 
97
    """
 
98
    def __init__(self, file_id, name, kind='file', text_id=None,
 
99
                 parent_id=None):
 
100
        """Create an InventoryEntry
 
101
        
 
102
        The filename must be a single component, relative to the
 
103
        parent directory; it cannot be a whole path or relative name.
 
104
 
 
105
        >>> e = InventoryEntry('123', 'hello.c')
 
106
        >>> e.name
 
107
        'hello.c'
 
108
        >>> e.file_id
 
109
        '123'
 
110
        >>> e = InventoryEntry('123', 'src/hello.c')
 
111
        Traceback (most recent call last):
 
112
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
 
113
        """
 
114
        
 
115
        if len(splitpath(name)) != 1:
 
116
            bailout('InventoryEntry name is not a simple filename: %r'
 
117
                    % name)
 
118
        
 
119
        self.file_id = file_id
 
120
        self.name = name
 
121
        assert kind in ['file', 'directory']
 
122
        self.kind = kind
 
123
        self.text_id = text_id
 
124
        self.parent_id = parent_id
 
125
        self.text_sha1 = None
 
126
        self.text_size = None
 
127
        if kind == 'directory':
 
128
            self.children = {}
 
129
 
 
130
 
 
131
    def sorted_children(self):
 
132
        l = self.children.items()
 
133
        l.sort()
 
134
        return l
 
135
 
 
136
 
 
137
    def copy(self):
 
138
        other = InventoryEntry(self.file_id, self.name, self.kind,
 
139
                               self.text_id, self.parent_id)
 
140
        other.text_sha1 = self.text_sha1
 
141
        other.text_size = self.text_size
 
142
        return other
 
143
 
 
144
 
 
145
    def __repr__(self):
 
146
        return ("%s(%r, %r, kind=%r, parent_id=%r)"
 
147
                % (self.__class__.__name__,
 
148
                   self.file_id,
 
149
                   self.name,
 
150
                   self.kind,
 
151
                   self.parent_id))
 
152
 
 
153
    
 
154
    def to_element(self):
 
155
        """Convert to XML element"""
 
156
        e = Element('entry')
 
157
 
 
158
        e.set('name', self.name)
 
159
        e.set('file_id', self.file_id)
 
160
        e.set('kind', self.kind)
 
161
 
 
162
        if self.text_size is not None:
 
163
            e.set('text_size', '%d' % self.text_size)
 
164
            
 
165
        for f in ['text_id', 'text_sha1', 'parent_id']:
 
166
            v = getattr(self, f)
 
167
            if v is not None:
 
168
                e.set(f, v)
 
169
 
 
170
        e.tail = '\n'
 
171
            
 
172
        return e
 
173
 
 
174
 
 
175
    def from_element(cls, elt):
 
176
        assert elt.tag == 'entry'
 
177
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
 
178
        self.text_id = elt.get('text_id')
 
179
        self.text_sha1 = elt.get('text_sha1')
 
180
        self.parent_id = elt.get('parent_id')
 
181
        
 
182
        ## mutter("read inventoryentry: %r" % (elt.attrib))
 
183
 
 
184
        v = elt.get('text_size')
 
185
        self.text_size = v and int(v)
 
186
 
 
187
        return self
 
188
            
 
189
 
 
190
    from_element = classmethod(from_element)
 
191
 
 
192
    def __cmp__(self, other):
 
193
        if self is other:
 
194
            return 0
 
195
        if not isinstance(other, InventoryEntry):
 
196
            return NotImplemented
 
197
 
 
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)
 
205
 
 
206
 
 
207
 
 
208
class RootEntry(InventoryEntry):
 
209
    def __init__(self, file_id):
 
210
        self.file_id = file_id
 
211
        self.children = {}
 
212
        self.kind = 'root_directory'
 
213
        self.parent_id = None
 
214
        self.name = ''
 
215
 
 
216
    def __cmp__(self, other):
 
217
        if self is other:
 
218
            return 0
 
219
        if not isinstance(other, RootEntry):
 
220
            return NotImplemented
 
221
        return cmp(self.file_id, other.file_id) \
 
222
               or cmp(self.children, other.children)
 
223
 
 
224
 
 
225
 
 
226
class Inventory(XMLMixin):
 
227
    """Inventory of versioned files in a tree.
 
228
 
 
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.
 
235
 
 
236
    The inventory represents a typical unix file tree, with
 
237
    directories containing files and subdirectories.  We never store
 
238
    the full path to a file, because renaming a directory implicitly
 
239
    moves all of its contents.  This class internally maintains a
 
240
    lookup tree that allows the children under a directory to be
 
241
    returned quickly.
 
242
 
 
243
    InventoryEntry objects must not be modified after they are
 
244
    inserted, other than through the Inventory API.
 
245
 
 
246
    >>> inv = Inventory()
 
247
    >>> inv.write_xml(sys.stdout)
 
248
    <inventory>
 
249
    </inventory>
 
250
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
 
251
    >>> inv['123-123'].name
 
252
    'hello.c'
 
253
 
 
254
    May be treated as an iterator or set to look up file ids:
 
255
    
 
256
    >>> bool(inv.path2id('hello.c'))
 
257
    True
 
258
    >>> '123-123' in inv
 
259
    True
 
260
 
 
261
    May also look up by name:
 
262
 
 
263
    >>> [x[0] for x in inv.iter_entries()]
 
264
    ['hello.c']
 
265
    
 
266
    >>> inv.write_xml(sys.stdout)
 
267
    <inventory>
 
268
    <entry file_id="123-123" kind="file" name="hello.c" />
 
269
    </inventory>
 
270
 
 
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
 
 
284
    def __init__(self):
 
285
        """Create or read an inventory.
 
286
 
 
287
        If a working directory is specified, the inventory is read
 
288
        from there.  If the file is specified, read from that. If not,
 
289
        the inventory is created empty.
 
290
 
 
291
        The inventory is created with a default root directory, with
 
292
        an id of None.
 
293
        """
 
294
        self.root = RootEntry(None)
 
295
        self._byid = {None: self.root}
 
296
 
 
297
 
 
298
    def __iter__(self):
 
299
        return iter(self._byid)
 
300
 
 
301
 
 
302
    def __len__(self):
 
303
        """Returns number of entries."""
 
304
        return len(self._byid)
 
305
 
 
306
 
 
307
    def iter_entries(self, from_dir=None):
 
308
        """Return (path, entry) pairs, in order by name."""
 
309
        if from_dir == None:
 
310
            assert self.root
 
311
            from_dir = self.root
 
312
        elif isinstance(from_dir, basestring):
 
313
            from_dir = self._byid[from_dir]
 
314
            
 
315
        kids = from_dir.children.items()
 
316
        kids.sort()
 
317
        for name, ie in kids:
 
318
            yield name, ie
 
319
            if ie.kind == 'directory':
 
320
                for cn, cie in self.iter_entries(from_dir=ie.file_id):
 
321
                    yield '/'.join((name, cn)), cie
 
322
                    
 
323
 
 
324
 
 
325
    def directories(self, from_dir=None):
 
326
        """Return (path, entry) pairs for all directories.
 
327
        """
 
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():
 
335
                if ie.kind == 'directory':
 
336
                    dn.append((ie.name, ie))
 
337
            dn.sort()
 
338
            
 
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
 
342
 
 
343
        for name, ie in descend(self.root):
 
344
            yield name, ie
 
345
        
 
346
 
 
347
 
 
348
    def __contains__(self, file_id):
 
349
        """True if this entry contains a file with given id.
 
350
 
 
351
        >>> inv = Inventory()
 
352
        >>> inv.add(InventoryEntry('123', 'foo.c'))
 
353
        >>> '123' in inv
 
354
        True
 
355
        >>> '456' in inv
 
356
        False
 
357
        """
 
358
        return file_id in self._byid
 
359
 
 
360
 
 
361
    def __getitem__(self, file_id):
 
362
        """Return the entry for given file_id.
 
363
 
 
364
        >>> inv = Inventory()
 
365
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
 
366
        >>> inv['123123'].name
 
367
        'hello.c'
 
368
        """
 
369
        return self._byid[file_id]
 
370
 
 
371
 
 
372
    def get_child(self, parent_id, filename):
 
373
        return self[parent_id].children.get(filename)
 
374
 
 
375
 
 
376
    def add(self, entry):
 
377
        """Add entry to inventory.
 
378
 
 
379
        To add  a file to a branch ready to be committed, use Branch.add,
 
380
        which calls this."""
 
381
        if entry.file_id in self._byid:
 
382
            bailout("inventory already contains entry with id {%s}" % entry.file_id)
 
383
 
 
384
        try:
 
385
            parent = self._byid[entry.parent_id]
 
386
        except KeyError:
 
387
            bailout("parent_id %r not in inventory" % entry.parent_id)
 
388
 
 
389
        if parent.children.has_key(entry.name):
 
390
            bailout("%s is already versioned" %
 
391
                    appendpath(self.id2path(parent.file_id), entry.name))
 
392
 
 
393
        self._byid[entry.file_id] = entry
 
394
        parent.children[entry.name] = entry
 
395
 
 
396
 
 
397
    def add_path(self, relpath, kind, file_id=None):
 
398
        """Add entry from a path.
 
399
 
 
400
        The immediate parent must already be versioned"""
 
401
        parts = bzrlib.osutils.splitpath(relpath)
 
402
        if len(parts) == 0:
 
403
            bailout("cannot re-add root of inventory")
 
404
 
 
405
        if file_id is None:
 
406
            file_id = bzrlib.branch.gen_file_id(relpath)
 
407
 
 
408
        parent_id = self.path2id(parts[:-1])
 
409
        ie = InventoryEntry(file_id, parts[-1],
 
410
                            kind=kind, parent_id=parent_id)
 
411
        return self.add(ie)
 
412
 
 
413
 
 
414
    def __delitem__(self, file_id):
 
415
        """Remove entry by id.
 
416
 
 
417
        >>> inv = Inventory()
 
418
        >>> inv.add(InventoryEntry('123', 'foo.c'))
 
419
        >>> '123' in inv
 
420
        True
 
421
        >>> del inv['123']
 
422
        >>> '123' in inv
 
423
        False
 
424
        """
 
425
        ie = self[file_id]
 
426
 
 
427
        assert self[ie.parent_id].children[ie.name] == ie
 
428
        
 
429
        # TODO: Test deleting all children; maybe hoist to a separate
 
430
        # deltree method?
 
431
        if ie.kind == 'directory':
 
432
            for cie in ie.children.values():
 
433
                del self[cie.file_id]
 
434
            del ie.children
 
435
 
 
436
        del self._byid[file_id]
 
437
        del self[ie.parent_id].children[ie.name]
 
438
 
 
439
 
 
440
    def id_set(self):
 
441
        return Set(self._byid)
 
442
 
 
443
 
 
444
    def to_element(self):
 
445
        """Convert to XML Element"""
 
446
        e = Element('inventory')
 
447
        e.text = '\n'
 
448
        for path, ie in self.iter_entries():
 
449
            e.append(ie.to_element())
 
450
        return e
 
451
    
 
452
 
 
453
    def from_element(cls, elt):
 
454
        """Construct from XML Element
 
455
 
 
456
        >>> inv = Inventory()
 
457
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
 
458
        >>> elt = inv.to_element()
 
459
        >>> inv2 = Inventory.from_element(elt)
 
460
        >>> inv2 == inv
 
461
        True
 
462
        """
 
463
        assert elt.tag == 'inventory'
 
464
        o = cls()
 
465
        for e in elt:
 
466
            o.add(InventoryEntry.from_element(e))
 
467
        return o
 
468
        
 
469
    from_element = classmethod(from_element)
 
470
 
 
471
 
 
472
    def __cmp__(self, other):
 
473
        """Compare two sets by comparing their contents.
 
474
 
 
475
        >>> i1 = Inventory()
 
476
        >>> i2 = Inventory()
 
477
        >>> i1 == i2
 
478
        True
 
479
        >>> i1.add(InventoryEntry('123', 'foo'))
 
480
        >>> i1 == i2
 
481
        False
 
482
        >>> i2.add(InventoryEntry('123', 'foo'))
 
483
        >>> i1 == i2
 
484
        True
 
485
        """
 
486
        if self is other:
 
487
            return 0
 
488
        
 
489
        if not isinstance(other, Inventory):
 
490
            return NotImplemented
 
491
 
 
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."""
 
504
        p = []
 
505
        while file_id != None:
 
506
            ie = self._byid[file_id]
 
507
            p.insert(0, ie.name)
 
508
            file_id = ie.parent_id
 
509
        return '/'.join(p)
 
510
            
 
511
 
 
512
 
 
513
    def path2id(self, name):
 
514
        """Walk down through directories to return entry of last component.
 
515
 
 
516
        names may be either a list of path components, or a single
 
517
        string, in which case it is automatically split.
 
518
 
 
519
        This returns the entry of the last component in the path,
 
520
        which may be either a file or a directory.
 
521
        """
 
522
        if isinstance(name, types.StringTypes):
 
523
            name = splitpath(name)
 
524
 
 
525
        parent = self[None]
 
526
        for f in name:
 
527
            try:
 
528
                cie = parent.children[f]
 
529
                assert cie.name == f
 
530
                parent = cie
 
531
            except KeyError:
 
532
                # or raise an error?
 
533
                return None
 
534
 
 
535
        return parent.file_id
 
536
 
 
537
 
 
538
    def has_filename(self, names):
 
539
        return bool(self.path2id(names))
 
540
 
 
541
 
 
542
    def has_id(self, file_id):
 
543
        return self._byid.has_key(file_id)
 
544
 
 
545
 
 
546
    def rename(self, file_id, new_parent_id, new_name):
 
547
        """Move a file within the inventory.
 
548
 
 
549
        This can change either the name, or the parent, or both.
 
550
 
 
551
        This does not move the working file."""
 
552
        if not is_valid_name(new_name):
 
553
            bailout("not an acceptable filename: %r" % new_name)
 
554
 
 
555
        new_parent = self._byid[new_parent_id]
 
556
        if new_name in new_parent.children:
 
557
            bailout("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
 
558
 
 
559
        file_ie = self._byid[file_id]
 
560
        old_parent = self._byid[file_ie.parent_id]
 
561
 
 
562
        # TODO: Don't leave things messed up if this fails
 
563
 
 
564
        del old_parent.children[file_ie.name]
 
565
        new_parent.children[new_name] = file_ie
 
566
        
 
567
        file_ie.name = new_name
 
568
        file_ie.parent_id = new_parent_id
 
569
 
 
570
 
 
571
 
 
572
 
 
573
_NAME_RE = re.compile(r'^[^/\\]+$')
 
574
 
 
575
def is_valid_name(name):
 
576
    return bool(_NAME_RE.match(name))
 
577
 
 
578
 
 
579
 
 
580
if __name__ == '__main__':
 
581
    import doctest, inventory
 
582
    doctest.testmod(inventory)