« back to all changes in this revision
Viewing changes to bzrlib/inventory.py
- browse files at revision 146
- compare with another revision
- download diff
- download tarball
- view history from revision 146
- 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
- files added:
- bzrlib/tests.py
- files removed:
- .rsyncexclude
- bzrlib/selftest
- contrib
- contrib/bash
- contrib/emacs
- contrib/zsh
- effbot
- effbot/org
- patches
- plugins
- plugins/changeset
- tools
- urlgrabber
- files modified:
- .bzrignore
added
removed
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
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
24
34
25
35
import bzrlib
26
from bzrlib.errors import BzrError, BzrCheckError
27
28
36
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
29
37
from bzrlib.trace import mutter
30
from bzrlib.branch import gen_file_id
31
from bzrlib.errors import NotVersionedError
32
33
38
34
class InventoryEntry(object):
39
class InventoryEntry(XMLMixin):
35
40
"""Description of a versioned file.
36
41
37
42
An InventoryEntry has the following fields, which are also
54
59
55
60
>>> i = Inventory()
56
61
>>> i.path2id('')
57
'TREE_ROOT'
58
>>> i.add(InventoryEntry('123', 'src', 'directory', ROOT_ID))
59
>>> 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'))
60
64
>>> for j in i.iter_entries():
61
65
... print j
62
66
...
63
('src', InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT'))
67
('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
64
68
('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
65
>>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))
69
>>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
66
70
Traceback (most recent call last):
67
71
...
68
BzrError: inventory already contains entry with id {2323}
69
>>> i.add(InventoryEntry('2324', 'bye.c', 'file', '123'))
70
>>> i.add(InventoryEntry('2325', 'wibble', 'directory', '123'))
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'))
71
75
>>> i.path2id('src/wibble')
72
76
'2325'
73
77
>>> '2325' in i
74
78
True
75
>>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))
79
>>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
76
80
>>> i['2326']
77
81
InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
78
82
>>> for j in i.iter_entries():
87
91
>>> i.id2path('2326')
88
92
'src/wibble/wibble.c'
89
93
90
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?
91
95
But those depend on its position within a particular inventory, and
92
96
it would be nice not to need to hold the backpointer here.
93
97
"""
94
95
# TODO: split InventoryEntry into subclasses for files,
96
# directories, etc etc.
97
98
__slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
99
'text_id', 'parent_id', 'children', ]
100
101
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):
102
100
"""Create an InventoryEntry
103
101
104
102
The filename must be a single component, relative to the
105
103
parent directory; it cannot be a whole path or relative name.
106
104
107
>>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)
105
>>> e = InventoryEntry('123', 'hello.c')
108
106
>>> e.name
109
107
'hello.c'
110
108
>>> e.file_id
111
109
'123'
112
>>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)
110
>>> e = InventoryEntry('123', 'src/hello.c')
113
111
Traceback (most recent call last):
114
BzrCheckError: InventoryEntry name 'src/hello.c' is invalid
112
BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
115
113
"""
116
if '/' in name or '\\' in name:
117
raise BzrCheckError('InventoryEntry name %r is invalid' % name)
118
119
self.text_sha1 = None
120
self.text_size = None
121
114
115
if len(splitpath(name)) != 1:
116
bailout('InventoryEntry name is not a simple filename: %r'
117
% name)
118
122
119
self.file_id = file_id
123
120
self.name = name
121
assert kind in ['file', 'directory']
124
122
self.kind = kind
125
123
self.text_id = text_id
126
124
self.parent_id = parent_id
125
self.text_sha1 = None
126
self.text_size = None
127
127
if kind == 'directory':
128
128
self.children = {}
129
elif kind == 'file':
130
pass
131
else:
132
raise BzrError("unhandled entry kind %r" % kind)
133
134
135
136
def sorted_children(self):
137
l = self.children.items()
138
l.sort()
139
return l
140
129
141
130
142
131
def copy(self):
143
132
other = InventoryEntry(self.file_id, self.name, self.kind,
144
self.parent_id, text_id=self.text_id)
133
self.text_id, self.parent_id)
145
134
other.text_sha1 = self.text_sha1
146
135
other.text_size = self.text_size
147
# note that children are *not* copied; they're pulled across when
148
# others are added
149
136
return other
150
137
151
138
160
147
161
148
def to_element(self):
162
149
"""Convert to XML element"""
163
from bzrlib.xml import Element
164
165
150
e = Element('entry')
166
151
167
152
e.set('name', self.name)
168
153
e.set('file_id', self.file_id)
169
154
e.set('kind', self.kind)
170
155
171
if self.text_size != None:
156
if self.text_size is not None:
172
157
e.set('text_size', '%d' % self.text_size)
173
158
174
for f in ['text_id', 'text_sha1']:
159
for f in ['text_id', 'text_sha1', 'parent_id']:
175
160
v = getattr(self, f)
176
if v != None:
161
if v is not None:
177
162
e.set(f, v)
178
163
179
# to be conservative, we don't externalize the root pointers
180
# for now, leaving them as null in the xml form. in a future
181
# version it will be implied by nested elements.
182
if self.parent_id != ROOT_ID:
183
assert isinstance(self.parent_id, basestring)
184
e.set('parent_id', self.parent_id)
185
186
164
e.tail = '\n'
187
165
188
166
return e
190
168
191
169
def from_element(cls, elt):
192
170
assert elt.tag == 'entry'
193
194
## original format inventories don't have a parent_id for
195
## nodes in the root directory, but it's cleaner to use one
196
## internally.
197
parent_id = elt.get('parent_id')
198
if parent_id == None:
199
parent_id = ROOT_ID
200
201
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'))
202
172
self.text_id = elt.get('text_id')
203
173
self.text_sha1 = elt.get('text_sha1')
174
self.parent_id = elt.get('parent_id')
204
175
205
176
## mutter("read inventoryentry: %r" % (elt.attrib))
206
177
212
183
213
184
from_element = classmethod(from_element)
214
185
215
def __eq__(self, other):
186
def __cmp__(self, other):
187
if self is other:
188
return 0
216
189
if not isinstance(other, InventoryEntry):
217
190
return NotImplemented
218
191
219
return (self.file_id == other.file_id) \
220
and (self.name == other.name) \
221
and (self.text_sha1 == other.text_sha1) \
222
and (self.text_size == other.text_size) \
223
and (self.text_id == other.text_id) \
224
and (self.parent_id == other.parent_id) \
225
and (self.kind == other.kind)
226
227
228
def __ne__(self, other):
229
return not (self == other)
230
231
def __hash__(self):
232
raise ValueError('not hashable')
233
234
235
236
class RootEntry(InventoryEntry):
237
def __init__(self, file_id):
238
self.file_id = file_id
239
self.children = {}
240
self.kind = 'root_directory'
241
self.parent_id = None
242
self.name = ''
243
244
def __eq__(self, other):
245
if not isinstance(other, RootEntry):
246
return NotImplemented
247
248
return (self.file_id == other.file_id) \
249
and (self.children == other.children)
250
251
252
253
class Inventory(object):
192
return cmp(self.file_id, other.file_id) \
193
or cmp(self.name, other.name) \
194
or cmp(self.text_sha1, other.text_sha1) \
195
or cmp(self.text_size, other.text_size) \
196
or cmp(self.text_id, other.text_id) \
197
or cmp(self.parent_id, other.parent_id) \
198
or cmp(self.kind, other.kind)
199
200
201
202
class Inventory(XMLMixin):
254
203
"""Inventory of versioned files in a tree.
255
204
256
This describes which file_id is present at each point in the tree,
257
and possibly the SHA-1 or other information about the file.
258
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.
259
211
260
212
The inventory represents a typical unix file tree, with
261
213
directories containing files and subdirectories. We never store
265
217
returned quickly.
266
218
267
219
InventoryEntry objects must not be modified after they are
268
inserted, other than through the Inventory API.
220
inserted.
269
221
270
222
>>> inv = Inventory()
271
>>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
223
>>> inv.write_xml(sys.stdout)
224
<inventory>
225
</inventory>
226
>>> inv.add(InventoryEntry('123-123', 'hello.c'))
272
227
>>> inv['123-123'].name
273
228
'hello.c'
274
229
283
238
284
239
>>> [x[0] for x in inv.iter_entries()]
285
240
['hello.c']
286
>>> inv = Inventory('TREE_ROOT-12345678-12345678')
287
>>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))
241
242
>>> inv.write_xml(sys.stdout)
243
<inventory>
244
<entry file_id="123-123" kind="file" name="hello.c" />
245
</inventory>
246
288
247
"""
289
def __init__(self, root_id=ROOT_ID):
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
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
# We are letting Branch(init=True) create a unique inventory
300
# root id. Rather than generating a random one here.
301
#if root_id is None:
302
# root_id = bzrlib.branch.gen_file_id('TREE_ROOT')
303
self.root = RootEntry(root_id)
304
self._byid = {self.root.file_id: self.root}
267
self._root = InventoryEntry(None, '', kind='directory')
268
self._byid = {None: self._root}
305
269
306
270
307
271
def __iter__(self):
313
277
return len(self._byid)
314
278
315
279
316
def iter_entries(self, from_dir=None):
280
def iter_entries(self, parent_id=None):
317
281
"""Return (path, entry) pairs, in order by name."""
318
if from_dir == None:
319
assert self.root
320
from_dir = self.root
321
elif isinstance(from_dir, basestring):
322
from_dir = self._byid[from_dir]
323
324
kids = from_dir.children.items()
282
kids = self[parent_id].children.items()
325
283
kids.sort()
326
284
for name, ie in kids:
327
285
yield name, ie
328
286
if ie.kind == 'directory':
329
for cn, cie in self.iter_entries(from_dir=ie.file_id):
330
yield os.path.join(name, cn), cie
331
332
333
def entries(self):
334
"""Return list of (path, ie) for all entries except the root.
335
336
This may be faster than iter_entries.
337
"""
338
accum = []
339
def descend(dir_ie, dir_path):
340
kids = dir_ie.children.items()
341
kids.sort()
342
for name, ie in kids:
343
child_path = os.path.join(dir_path, name)
344
accum.append((child_path, ie))
345
if ie.kind == 'directory':
346
descend(ie, child_path)
347
348
descend(self.root, '')
349
return accum
287
for cn, cie in self.iter_entries(parent_id=ie.file_id):
288
yield joinpath([name, cn]), cie
350
289
351
290
352
291
def directories(self):
353
"""Return (path, entry) pairs for all directories, including the root.
292
"""Return (path, entry) pairs for all directories.
354
293
"""
355
accum = []
356
def descend(parent_ie, parent_path):
357
accum.append((parent_path, parent_ie))
358
359
kids = [(ie.name, ie) for ie in parent_ie.children.itervalues() if ie.kind == 'directory']
360
kids.sort()
361
362
for name, child_ie in kids:
363
child_path = os.path.join(parent_path, name)
364
descend(child_ie, child_path)
365
descend(self.root, '')
366
return accum
294
yield '', self._root
295
for path, entry in self.iter_entries():
296
if entry.kind == 'directory':
297
yield path, entry
367
298
368
299
369
300
371
302
"""True if this entry contains a file with given id.
372
303
373
304
>>> inv = Inventory()
374
>>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
305
>>> inv.add(InventoryEntry('123', 'foo.c'))
375
306
>>> '123' in inv
376
307
True
377
308
>>> '456' in inv
384
315
"""Return the entry for given file_id.
385
316
386
317
>>> inv = Inventory()
387
>>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))
318
>>> inv.add(InventoryEntry('123123', 'hello.c'))
388
319
>>> inv['123123'].name
389
320
'hello.c'
390
321
"""
391
try:
392
return self._byid[file_id]
393
except KeyError:
394
if file_id == None:
395
raise BzrError("can't look up file_id None")
396
else:
397
raise BzrError("file_id {%s} not in inventory" % file_id)
398
399
400
def get_file_kind(self, file_id):
401
return self._byid[file_id].kind
322
return self._byid[file_id]
323
402
324
403
325
def get_child(self, parent_id, filename):
404
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)
405
330
406
331
407
332
def add(self, entry):
410
335
To add a file to a branch ready to be committed, use Branch.add,
411
336
which calls this."""
412
337
if entry.file_id in self._byid:
413
raise BzrError("inventory already contains entry with id {%s}" % entry.file_id)
414
415
if entry.parent_id == ROOT_ID or entry.parent_id is None:
416
entry.parent_id = self.root.file_id
417
418
try:
419
parent = self._byid[entry.parent_id]
420
except KeyError:
421
raise BzrError("parent_id {%s} not in inventory" % entry.parent_id)
338
bailout("inventory already contains entry with id {%s}" % entry.file_id)
339
340
parent = self._byid[entry.parent_id]
341
if parent.kind != 'directory':
342
bailout("attempt to add under non-directory {%s}" % parent.file_id)
422
343
423
344
if parent.children.has_key(entry.name):
424
raise BzrError("%s is already versioned" %
345
bailout("%s is already versioned" %
425
346
appendpath(self.id2path(parent.file_id), entry.name))
426
347
427
348
self._byid[entry.file_id] = entry
434
355
The immediate parent must already be versioned"""
435
356
parts = bzrlib.osutils.splitpath(relpath)
436
357
if len(parts) == 0:
437
raise BzrError("cannot re-add root of inventory")
438
439
if file_id == None:
440
file_id = gen_file_id(relpath)
441
442
parent_path = parts[:-1]
443
parent_id = self.path2id(parent_path)
444
if parent_id == None:
445
raise NotVersionedError(parent_path)
446
358
bailout("cannot re-add root of inventory")
359
360
if file_id is None:
361
file_id = bzrlib.branch.gen_file_id(relpath)
362
363
parent_id = self.path2id(parts[:-1])
447
364
ie = InventoryEntry(file_id, parts[-1],
448
365
kind=kind, parent_id=parent_id)
449
366
return self.add(ie)
453
370
"""Remove entry by id.
454
371
455
372
>>> inv = Inventory()
456
>>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))
373
>>> inv.add(InventoryEntry('123', 'foo.c'))
457
374
>>> '123' in inv
458
375
True
459
376
>>> del inv['123']
475
392
del self[ie.parent_id].children[ie.name]
476
393
477
394
395
def id_set(self):
396
return Set(self._byid)
397
398
478
399
def to_element(self):
479
400
"""Convert to XML Element"""
480
from bzrlib.xml import Element
481
482
401
e = Element('inventory')
483
402
e.text = '\n'
484
if self.root.file_id not in (None, ROOT_ID):
485
e.set('file_id', self.root.file_id)
486
403
for path, ie in self.iter_entries():
487
404
e.append(ie.to_element())
488
405
return e
490
407
491
408
def from_element(cls, elt):
492
409
"""Construct from XML Element
493
410
494
411
>>> inv = Inventory()
495
>>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))
412
>>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
496
413
>>> elt = inv.to_element()
497
414
>>> inv2 = Inventory.from_element(elt)
498
415
>>> inv2 == inv
499
416
True
500
417
"""
501
# XXXX: doctest doesn't run this properly under python2.3
502
418
assert elt.tag == 'inventory'
503
root_id = elt.get('file_id') or ROOT_ID
504
o = cls(root_id)
419
o = cls()
505
420
for e in elt:
506
ie = InventoryEntry.from_element(e)
507
if ie.parent_id == ROOT_ID:
508
ie.parent_id = root_id
509
o.add(ie)
421
o.add(InventoryEntry.from_element(e))
510
422
return o
511
423
512
424
from_element = classmethod(from_element)
513
425
514
426
515
def __eq__(self, other):
427
def __cmp__(self, other):
516
428
"""Compare two sets by comparing their contents.
517
429
518
430
>>> i1 = Inventory()
519
431
>>> i2 = Inventory()
520
432
>>> i1 == i2
521
433
True
522
>>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
434
>>> i1.add(InventoryEntry('123', 'foo'))
523
435
>>> i1 == i2
524
436
False
525
>>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))
437
>>> i2.add(InventoryEntry('123', 'foo'))
526
438
>>> i1 == i2
527
439
True
528
440
"""
441
if self is other:
442
return 0
443
529
444
if not isinstance(other, Inventory):
530
445
return NotImplemented
531
446
532
if len(self._byid) != len(other._byid):
533
# shortcut: obviously not the same
534
return False
535
536
return self._byid == other._byid
537
538
539
def __ne__(self, other):
540
return not (self == other)
541
542
543
def __hash__(self):
544
raise ValueError('not hashable')
545
546
547
548
def get_idpath(self, file_id):
549
"""Return a list of file_ids for the path to an entry.
550
551
The list contains one element for each directory followed by
552
the id of the file itself. So the length of the returned list
553
is equal to the depth of the file in the tree, counting the
554
root directory as depth 1.
555
"""
447
if self.id_set() ^ other.id_set():
448
return 1
449
450
for file_id in self._byid:
451
c = cmp(self[file_id], other[file_id])
452
if c: return c
453
454
return 0
455
456
457
def id2path(self, file_id):
458
"""Return as a list the path to file_id."""
556
459
p = []
557
460
while file_id != None:
558
try:
559
ie = self._byid[file_id]
560
except KeyError:
561
raise BzrError("file_id {%s} not found in inventory" % file_id)
562
p.insert(0, ie.file_id)
461
ie = self[file_id]
462
p = [ie.name] + p
563
463
file_id = ie.parent_id
564
return p
565
566
567
def id2path(self, file_id):
568
"""Return as a list the path to file_id."""
569
570
# get all names, skipping root
571
p = [self._byid[fid].name for fid in self.get_idpath(file_id)[1:]]
572
return os.sep.join(p)
464
return joinpath(p)
573
465
574
466
575
467
581
473
582
474
This returns the entry of the last component in the path,
583
475
which may be either a file or a directory.
584
585
Returns None iff the path is not found.
586
476
"""
587
477
if isinstance(name, types.StringTypes):
588
478
name = splitpath(name)
589
479
590
mutter("lookup path %r" % name)
591
592
parent = self.root
480
parent = self[None]
593
481
for f in name:
594
482
try:
595
483
cie = parent.children[f]
596
484
assert cie.name == f
597
assert cie.parent_id == parent.file_id
598
485
parent = cie
599
486
except KeyError:
600
487
# or raise an error?
608
495
609
496
610
497
def has_id(self, file_id):
498
assert isinstance(file_id, str)
611
499
return self._byid.has_key(file_id)
612
500
613
501
614
def rename(self, file_id, new_parent_id, new_name):
615
"""Move a file within the inventory.
616
617
This can change either the name, or the parent, or both.
618
619
This does not move the working file."""
620
if not is_valid_name(new_name):
621
raise BzrError("not an acceptable filename: %r" % new_name)
622
623
new_parent = self._byid[new_parent_id]
624
if new_name in new_parent.children:
625
raise BzrError("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))
626
627
new_parent_idpath = self.get_idpath(new_parent_id)
628
if file_id in new_parent_idpath:
629
raise BzrError("cannot move directory %r into a subdirectory of itself, %r"
630
% (self.id2path(file_id), self.id2path(new_parent_id)))
631
632
file_ie = self._byid[file_id]
633
old_parent = self._byid[file_ie.parent_id]
634
635
# TODO: Don't leave things messed up if this fails
636
637
del old_parent.children[file_ie.name]
638
new_parent.children[new_name] = file_ie
639
640
file_ie.name = new_name
641
file_ie.parent_id = new_parent_id
642
643
644
645
646
_NAME_RE = re.compile(r'^[^/\\]+$')
647
648
def is_valid_name(name):
649
return bool(_NAME_RE.match(name))
502
503
504
505
if __name__ == '__main__':
506
import doctest, inventory
507
doctest.testmod(inventory)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1