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