« back to all changes in this revision
Viewing changes to bzrlib/inventory.py
- browse files at revision 3735.2.9
- compare with another revision
- download diff
- download tarball
- view history from revision 3735.2.9
- Committer: Robert Collins
- Date: 2008-10-09 04:50:37 UTC
- mto: (3735.30.1 trivial-fixes) (4194.1.1 bbc) (4216.5.1 bbc) (4265.1.1 bbc-merge)
- mto: This revision was merged to the branch mainline in revision 4280.
- Revision ID: robertc@robertcollins.net-20081009045037-cbgz8f749b93oe87
Get a working chk_map using inventory implementation bootstrapped.
- files added:
- bzrlib/chk_serializer.py
- files modified:
- bzrlib/chk_map.py
added
removed
bzrlib/inventory.py
38
38
39
39
import bzrlib
40
40
from bzrlib import (
41
chk_map,
41
42
errors,
42
43
generate_ids,
43
44
osutils,
90
91
>>> i.add(InventoryDirectory('123', 'src', ROOT_ID))
91
92
InventoryDirectory('123', 'src', parent_id='TREE_ROOT', revision=None)
92
93
>>> i.add(InventoryFile('2323', 'hello.c', parent_id='123'))
93
InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None)
94
InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None, revision=None)
94
95
>>> shouldbe = {0: '', 1: 'src', 2: 'src/hello.c'}
95
96
>>> for ix, j in enumerate(i.iter_entries()):
96
97
... print (j[0] == shouldbe[ix], j[1])
97
98
...
98
99
(True, InventoryDirectory('TREE_ROOT', u'', parent_id=None, revision=None))
99
100
(True, InventoryDirectory('123', 'src', parent_id='TREE_ROOT', revision=None))
100
(True, InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None))
101
(True, InventoryFile('2323', 'hello.c', parent_id='123', sha1=None, len=None, revision=None))
101
102
>>> i.add(InventoryFile('2324', 'bye.c', '123'))
102
InventoryFile('2324', 'bye.c', parent_id='123', sha1=None, len=None)
103
InventoryFile('2324', 'bye.c', parent_id='123', sha1=None, len=None, revision=None)
103
104
>>> i.add(InventoryDirectory('2325', 'wibble', '123'))
104
105
InventoryDirectory('2325', 'wibble', parent_id='123', revision=None)
105
106
>>> i.path2id('src/wibble')
107
108
>>> '2325' in i
108
109
True
109
110
>>> i.add(InventoryFile('2326', 'wibble.c', '2325'))
110
InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None)
111
InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None, revision=None)
111
112
>>> i['2326']
112
InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None)
113
InventoryFile('2326', 'wibble.c', parent_id='2325', sha1=None, len=None, revision=None)
113
114
>>> for path, entry in i.iter_entries():
114
115
... print path
115
116
...
564
565
self.executable = work_tree.is_executable(self.file_id, path=path)
565
566
566
567
def __repr__(self):
567
return ("%s(%r, %r, parent_id=%r, sha1=%r, len=%s)"
568
return ("%s(%r, %r, parent_id=%r, sha1=%r, len=%s, revision=%s)"
568
569
% (self.__class__.__name__,
569
570
self.file_id,
570
571
self.name,
571
572
self.parent_id,
572
573
self.text_sha1,
573
self.text_size))
574
self.text_size,
575
self.revision))
574
576
575
577
def _forget_tree_state(self):
576
578
self.text_sha1 = None
709
711
return compatible
710
712
711
713
712
class Inventory(object):
714
class CommonInventory(object):
715
"""Basic inventory logic, defined in terms of primitives like has_id."""
716
717
def iter_entries(self, from_dir=None):
718
"""Return (path, entry) pairs, in order by name."""
719
if from_dir is None:
720
if self.root is None:
721
return
722
from_dir = self.root
723
yield '', self.root
724
elif isinstance(from_dir, basestring):
725
from_dir = self[from_dir]
726
727
# unrolling the recursive called changed the time from
728
# 440ms/663ms (inline/total) to 116ms/116ms
729
children = from_dir.children.items()
730
children.sort()
731
children = collections.deque(children)
732
stack = [(u'', children)]
733
while stack:
734
from_dir_relpath, children = stack[-1]
735
736
while children:
737
name, ie = children.popleft()
738
739
# we know that from_dir_relpath never ends in a slash
740
# and 'f' doesn't begin with one, we can do a string op, rather
741
# than the checks of pathjoin(), though this means that all paths
742
# start with a slash
743
path = from_dir_relpath + '/' + name
744
745
yield path[1:], ie
746
747
if ie.kind != 'directory':
748
continue
749
750
# But do this child first
751
new_children = ie.children.items()
752
new_children.sort()
753
new_children = collections.deque(new_children)
754
stack.append((path, new_children))
755
# Break out of inner loop, so that we start outer loop with child
756
break
757
else:
758
# if we finished all children, pop it off the stack
759
stack.pop()
760
761
def iter_entries_by_dir(self, from_dir=None, specific_file_ids=None,
762
yield_parents=False):
763
"""Iterate over the entries in a directory first order.
764
765
This returns all entries for a directory before returning
766
the entries for children of a directory. This is not
767
lexicographically sorted order, and is a hybrid between
768
depth-first and breadth-first.
769
770
:param yield_parents: If True, yield the parents from the root leading
771
down to specific_file_ids that have been requested. This has no
772
impact if specific_file_ids is None.
773
:return: This yields (path, entry) pairs
774
"""
775
if specific_file_ids and not isinstance(specific_file_ids, set):
776
specific_file_ids = set(specific_file_ids)
777
# TODO? Perhaps this should return the from_dir so that the root is
778
# yielded? or maybe an option?
779
if from_dir is None:
780
if self.root is None:
781
return
782
# Optimize a common case
783
if (not yield_parents and specific_file_ids is not None and
784
len(specific_file_ids) == 1):
785
file_id = list(specific_file_ids)[0]
786
if file_id in self:
787
yield self.id2path(file_id), self[file_id]
788
return
789
from_dir = self.root
790
if (specific_file_ids is None or yield_parents or
791
self.root.file_id in specific_file_ids):
792
yield u'', self.root
793
elif isinstance(from_dir, basestring):
794
from_dir = self[from_dir]
795
796
if specific_file_ids is not None:
797
# TODO: jam 20070302 This could really be done as a loop rather
798
# than a bunch of recursive calls.
799
parents = set()
800
byid = self
801
def add_ancestors(file_id):
802
if file_id not in byid:
803
return
804
parent_id = byid[file_id].parent_id
805
if parent_id is None:
806
return
807
if parent_id not in parents:
808
parents.add(parent_id)
809
add_ancestors(parent_id)
810
for file_id in specific_file_ids:
811
add_ancestors(file_id)
812
else:
813
parents = None
814
815
stack = [(u'', from_dir)]
816
while stack:
817
cur_relpath, cur_dir = stack.pop()
818
819
child_dirs = []
820
for child_name, child_ie in sorted(cur_dir.children.iteritems()):
821
822
child_relpath = cur_relpath + child_name
823
824
if (specific_file_ids is None or
825
child_ie.file_id in specific_file_ids or
826
(yield_parents and child_ie.file_id in parents)):
827
yield child_relpath, child_ie
828
829
if child_ie.kind == 'directory':
830
if parents is None or child_ie.file_id in parents:
831
child_dirs.append((child_relpath+'/', child_ie))
832
stack.extend(reversed(child_dirs))
833
834
835
class Inventory(CommonInventory):
713
836
"""Inventory of versioned files in a tree.
714
837
715
838
This describes which file_id is present at each point in the tree,
728
851
729
852
>>> inv = Inventory()
730
853
>>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
731
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
854
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
732
855
>>> inv['123-123'].name
733
856
'hello.c'
734
857
748
871
Traceback (most recent call last):
749
872
BzrError: parent_id {TREE_ROOT} not in inventory
750
873
>>> inv.add(InventoryFile('123-123', 'hello.c', 'TREE_ROOT-12345678-12345678'))
751
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT-12345678-12345678', sha1=None, len=None)
874
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT-12345678-12345678', sha1=None, len=None, revision=None)
752
875
"""
753
876
def __init__(self, root_id=ROOT_ID, revision_id=None):
754
877
"""Create or read an inventory.
864
987
"""Returns number of entries."""
865
988
return len(self._byid)
866
989
867
def iter_entries(self, from_dir=None):
868
"""Return (path, entry) pairs, in order by name."""
869
if from_dir is None:
870
if self.root is None:
871
return
872
from_dir = self.root
873
yield '', self.root
874
elif isinstance(from_dir, basestring):
875
from_dir = self._byid[from_dir]
876
877
# unrolling the recursive called changed the time from
878
# 440ms/663ms (inline/total) to 116ms/116ms
879
children = from_dir.children.items()
880
children.sort()
881
children = collections.deque(children)
882
stack = [(u'', children)]
883
while stack:
884
from_dir_relpath, children = stack[-1]
885
886
while children:
887
name, ie = children.popleft()
888
889
# we know that from_dir_relpath never ends in a slash
890
# and 'f' doesn't begin with one, we can do a string op, rather
891
# than the checks of pathjoin(), though this means that all paths
892
# start with a slash
893
path = from_dir_relpath + '/' + name
894
895
yield path[1:], ie
896
897
if ie.kind != 'directory':
898
continue
899
900
# But do this child first
901
new_children = ie.children.items()
902
new_children.sort()
903
new_children = collections.deque(new_children)
904
stack.append((path, new_children))
905
# Break out of inner loop, so that we start outer loop with child
906
break
907
else:
908
# if we finished all children, pop it off the stack
909
stack.pop()
910
911
def iter_entries_by_dir(self, from_dir=None, specific_file_ids=None,
912
yield_parents=False):
913
"""Iterate over the entries in a directory first order.
914
915
This returns all entries for a directory before returning
916
the entries for children of a directory. This is not
917
lexicographically sorted order, and is a hybrid between
918
depth-first and breadth-first.
919
920
:param yield_parents: If True, yield the parents from the root leading
921
down to specific_file_ids that have been requested. This has no
922
impact if specific_file_ids is None.
923
:return: This yields (path, entry) pairs
924
"""
925
if specific_file_ids and not isinstance(specific_file_ids, set):
926
specific_file_ids = set(specific_file_ids)
927
# TODO? Perhaps this should return the from_dir so that the root is
928
# yielded? or maybe an option?
929
if from_dir is None:
930
if self.root is None:
931
return
932
# Optimize a common case
933
if (not yield_parents and specific_file_ids is not None and
934
len(specific_file_ids) == 1):
935
file_id = list(specific_file_ids)[0]
936
if file_id in self:
937
yield self.id2path(file_id), self[file_id]
938
return
939
from_dir = self.root
940
if (specific_file_ids is None or yield_parents or
941
self.root.file_id in specific_file_ids):
942
yield u'', self.root
943
elif isinstance(from_dir, basestring):
944
from_dir = self._byid[from_dir]
945
946
if specific_file_ids is not None:
947
# TODO: jam 20070302 This could really be done as a loop rather
948
# than a bunch of recursive calls.
949
parents = set()
950
byid = self._byid
951
def add_ancestors(file_id):
952
if file_id not in byid:
953
return
954
parent_id = byid[file_id].parent_id
955
if parent_id is None:
956
return
957
if parent_id not in parents:
958
parents.add(parent_id)
959
add_ancestors(parent_id)
960
for file_id in specific_file_ids:
961
add_ancestors(file_id)
962
else:
963
parents = None
964
965
stack = [(u'', from_dir)]
966
while stack:
967
cur_relpath, cur_dir = stack.pop()
968
969
child_dirs = []
970
for child_name, child_ie in sorted(cur_dir.children.iteritems()):
971
972
child_relpath = cur_relpath + child_name
973
974
if (specific_file_ids is None or
975
child_ie.file_id in specific_file_ids or
976
(yield_parents and child_ie.file_id in parents)):
977
yield child_relpath, child_ie
978
979
if child_ie.kind == 'directory':
980
if parents is None or child_ie.file_id in parents:
981
child_dirs.append((child_relpath+'/', child_ie))
982
stack.extend(reversed(child_dirs))
983
984
990
def make_entry(self, kind, name, parent_id, file_id=None):
985
991
"""Simple thunk to bzrlib.inventory.make_entry."""
986
992
return make_entry(kind, name, parent_id, file_id)
1024
1030
1025
1031
>>> inv = Inventory()
1026
1032
>>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
1027
InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
1033
InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1028
1034
>>> '123' in inv
1029
1035
True
1030
1036
>>> '456' in inv
1037
1043
1038
1044
>>> inv = Inventory()
1039
1045
>>> inv.add(InventoryFile('123123', 'hello.c', ROOT_ID))
1040
InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
1046
InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1041
1047
>>> inv['123123'].name
1042
1048
'hello.c'
1043
1049
"""
1119
1125
1120
1126
>>> inv = Inventory()
1121
1127
>>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
1122
InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
1128
InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1123
1129
>>> '123' in inv
1124
1130
True
1125
1131
>>> del inv['123']
1139
1145
>>> i1 == i2
1140
1146
True
1141
1147
>>> i1.add(InventoryFile('123', 'foo', ROOT_ID))
1142
InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None)
1148
InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1143
1149
>>> i1 == i2
1144
1150
False
1145
1151
>>> i2.add(InventoryFile('123', 'foo', ROOT_ID))
1146
InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None)
1152
InventoryFile('123', 'foo', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1147
1153
>>> i1 == i2
1148
1154
True
1149
1155
"""
1288
1294
return self.root is not None and file_id == self.root.file_id
1289
1295
1290
1296
1297
class CHKInventory(CommonInventory):
1298
"""A inventory persisted in a CHK store.
1299
1300
No caching is performed: every method call or item access will perform
1301
requests to the storage layer. As such, keep references to objects you want
1302
to reuse.
1303
"""
1304
1305
def _entry_to_bytes(self, entry):
1306
"""Serialise entry as a single bytestring.
1307
1308
:param Entry: An inventory entry.
1309
:return: A bytestring for the entry.
1310
1311
The BNF:
1312
ENTRY ::= FILE | DIR | SYMLINK | TREE
1313
FILE ::= "file: " COMMON NULL SHA NULL SIZE NULL EXECUTABLE
1314
DIR ::= "dir: " COMMON
1315
SYMLINK ::= "symlink: " COMMON NULL TARGET_UTF8
1316
TREE ::= "tree: " COMMON REFERENCE_REVISION
1317
COMMON ::= FILE_ID NULL PARENT_ID NULL NAME_UTF8 NULL REVISION
1318
"""
1319
if entry.parent_id is not None:
1320
parent_str = entry.parent_id
1321
else:
1322
parent_str = ''
1323
name_str = entry.name.encode("utf8")
1324
if entry.kind == 'file':
1325
if entry.executable:
1326
exec_str = "Y"
1327
else:
1328
exec_str = "N"
1329
return "file: %s\x00%s\x00%s\x00%s\x00%s\x00%d\x00%s" % (
1330
entry.file_id, parent_str, name_str, entry.revision,
1331
entry.text_sha1, entry.text_size, exec_str)
1332
elif entry.kind == 'directory':
1333
return "dir: %s\x00%s\x00%s\x00%s" % (
1334
entry.file_id, parent_str, name_str, entry.revision)
1335
elif entry.kind == 'symlink':
1336
return "symlink: %s\x00%s\x00%s\x00%s\x00%s" % (
1337
entry.file_id, parent_str, name_str, entry.revision,
1338
entry.symlink_target.encode("utf8"))
1339
elif entry.kind == 'tree-reference':
1340
return "tree: %s\x00%s\x00%s\x00%s\x00%s" % (
1341
entry.file_id, parent_str, name_str, entry.revision,
1342
entry.reference_revision)
1343
else:
1344
raise ValueError("unknown kind %r" % entry.kind)
1345
1346
def _bytes_to_entry(self, bytes):
1347
"""Deserialise a serialised entry."""
1348
sections = bytes.split('\x00')
1349
if sections[0].startswith("file: "):
1350
result = InventoryFile(sections[0][6:],
1351
sections[2].decode('utf8'),
1352
sections[1])
1353
result.text_sha1 = sections[4]
1354
result.text_size = int(sections[5])
1355
result.executable = sections[6] == "Y"
1356
elif sections[0].startswith("dir: "):
1357
result = CHKInventoryDirectory(sections[0][5:],
1358
sections[2].decode('utf8'),
1359
sections[1], self)
1360
elif sections[0].startswith("symlink: "):
1361
result = InventoryLink(sections[0][9:],
1362
sections[2].decode('utf8'),
1363
sections[1])
1364
result.symlink_target = sections[4]
1365
elif sections[0].startswith("tree: "):
1366
result = TreeReference(sections[0][6:],
1367
sections[2].decode('utf8'),
1368
sections[1])
1369
result.reference_revision = sections[4]
1370
else:
1371
raise ValueError("Not a serialised entry %r" % bytes)
1372
result.revision = sections[3]
1373
if result.parent_id == '':
1374
result.parent_id = None
1375
return result
1376
1377
@classmethod
1378
def deserialise(klass, chk_store, bytes, expected_revision_id):
1379
"""Deserialise a CHKInventory.
1380
1381
:param chk_store: A CHK capable VersionedFiles instance.
1382
:param bytes: The serialised bytes.
1383
:param expected_revision_id: The revision ID we think this inventory is
1384
for.
1385
:return: A CHKInventory
1386
"""
1387
result = CHKInventory()
1388
lines = bytes.splitlines()
1389
if lines[0] != 'chkinventory:':
1390
raise ValueError("not a serialised CHKInventory: %r" % bytes)
1391
result.revision_id = lines[1][13:]
1392
result.root_id = lines[2][9:]
1393
result.id_to_entry = chk_map.CHKMap(chk_store, (lines[3][13:],))
1394
if (result.revision_id,) != expected_revision_id:
1395
raise ValueError("Mismatched revision id and expected: %r, %r" %
1396
(result.revision_id, expected_revision_id))
1397
return result
1398
1399
@classmethod
1400
def from_inventory(klass, chk_store, inventory):
1401
"""Create a CHKInventory from an existing inventory.
1402
1403
The content of inventory is copied into the chk_store, and a
1404
CHKInventory referencing that is returned.
1405
1406
:param chk_store: A CHK capable VersionedFiles instance.
1407
:param inventory: The inventory to copy.
1408
"""
1409
result = CHKInventory()
1410
result.revision_id = inventory.revision_id
1411
result.root_id = inventory.root.file_id
1412
result.id_to_entry = chk_map.CHKMap(chk_store, None)
1413
for path, entry in inventory.iter_entries():
1414
result.id_to_entry._map(entry.file_id,
1415
result._entry_to_bytes(entry))
1416
result.id_to_entry._save()
1417
return result
1418
1419
def __getitem__(self, file_id):
1420
"""map a single file_id -> InventoryEntry."""
1421
try:
1422
return self._bytes_to_entry(
1423
self.id_to_entry.iteritems([file_id]).next()[1])
1424
except StopIteration:
1425
raise KeyError(file_id)
1426
1427
def has_id(self, file_id):
1428
# Perhaps have an explicit 'contains' method on CHKMap ?
1429
return len(list(self.id_to_entry.iteritems([file_id]))) == 1
1430
1431
def __iter__(self):
1432
"""Iterate over the entire inventory contents; size-of-tree - beware!."""
1433
for file_id, _ in self.id_to_entry.iteritems():
1434
yield file_id
1435
1436
def __len__(self):
1437
"""Return the number of entries in the inventory."""
1438
# Might want to cache the length in the meta node.
1439
return len([item for item in self])
1440
1441
def to_lines(self):
1442
"""Serialise the inventory to lines."""
1443
lines = ["chkinventory:\n"]
1444
lines.append("revision_id: %s\n" % self.revision_id)
1445
lines.append("root_id: %s\n" % self.root_id)
1446
lines.append("id_to_entry: %s\n" % self.id_to_entry._root_node._key)
1447
return lines
1448
1449
@property
1450
def root(self):
1451
"""Get the root entry."""
1452
return self[self.root_id]
1453
1454
1455
class CHKInventoryDirectory(InventoryDirectory):
1456
"""A directory in an inventory."""
1457
1458
__slots__ = ['text_sha1', 'text_size', 'file_id', 'name', 'kind',
1459
'text_id', 'parent_id', '_children', 'executable',
1460
'revision', 'symlink_target', 'reference_revision',
1461
'_chk_inventory']
1462
1463
def __init__(self, file_id, name, parent_id, chk_inventory):
1464
# Don't call InventoryDirectory.__init__ - it isn't right for this
1465
# class.
1466
InventoryEntry.__init__(self, file_id, name, parent_id)
1467
self._children = None
1468
self.kind = 'directory'
1469
self._chk_inventory = chk_inventory
1470
1471
@property
1472
def children(self):
1473
"""Access the list of children of this inventory.
1474
1475
Currently causes a full-load of all the children; a more sophisticated
1476
proxy object is planned.
1477
"""
1478
if self._children is not None:
1479
return self._children
1480
result = {}
1481
# populate; todo: do by name
1482
for file_id, bytes in self._chk_inventory.id_to_entry.iteritems():
1483
entry = self._chk_inventory._bytes_to_entry(bytes)
1484
if entry.parent_id == self.file_id:
1485
result[entry.name] = entry
1486
self._children = result
1487
return result
1488
1489
1291
1490
entry_factory = {
1292
1491
'directory': InventoryDirectory,
1293
1492
'file': InventoryFile,
Loggerhead is a web-based interface for Breezy
Version: 2.0.1