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