618
819
return compatible
621
class CommonInventory(object):
622
"""Basic inventory logic, defined in terms of primitives like has_id.
624
An inventory is the metadata about the contents of a tree.
626
This is broadly a map from file_id to entries such as directories, files,
627
symlinks and tree references. Each entry maintains its own metadata like
628
SHA1 and length for files, or children for a directory.
822
class Inventory(object):
823
"""Inventory of versioned files in a tree.
825
This describes which file_id is present at each point in the tree,
826
and possibly the SHA-1 or other information about the file.
630
827
Entries can be looked up either by path or by file_id.
829
The inventory represents a typical unix file tree, with
830
directories containing files and subdirectories. We never store
831
the full path to a file, because renaming a directory implicitly
832
moves all of its contents. This class internally maintains a
833
lookup tree that allows the children under a directory to be
632
836
InventoryEntry objects must not be modified after they are
633
837
inserted, other than through the Inventory API.
839
>>> inv = Inventory()
840
>>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
841
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
842
>>> inv['123-123'].name
845
May be treated as an iterator or set to look up file ids:
847
>>> bool(inv.path2id('hello.c'))
852
May also look up by name:
854
>>> [x[0] for x in inv.iter_entries()]
856
>>> inv = Inventory('TREE_ROOT-12345678-12345678')
857
>>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
858
Traceback (most recent call last):
859
BzrError: parent_id {TREE_ROOT} not in inventory
860
>>> inv.add(InventoryFile('123-123', 'hello.c', 'TREE_ROOT-12345678-12345678'))
861
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT-12345678-12345678', sha1=None, len=None)
636
def has_filename(self, filename):
637
return bool(self.path2id(filename))
639
def id2path(self, file_id):
640
"""Return as a string the path to file_id.
643
>>> e = i.add(InventoryDirectory('src-id', 'src', ROOT_ID))
644
>>> e = i.add(InventoryFile('foo-id', 'foo.c', parent_id='src-id'))
645
>>> print i.id2path('foo-id')
648
:raises NoSuchId: If file_id is not present in the inventory.
650
# get all names, skipping root
651
return '/'.join(reversed(
652
[parent.name for parent in
653
self._iter_file_id_parents(file_id)][:-1]))
655
def iter_entries(self, from_dir=None, recursive=True):
656
"""Return (path, entry) pairs, in order by name.
658
:param from_dir: if None, start from the root,
659
otherwise start from this directory (either file-id or entry)
660
:param recursive: recurse into directories or not
863
def __init__(self, root_id=ROOT_ID, revision_id=None):
864
"""Create or read an inventory.
866
If a working directory is specified, the inventory is read
867
from there. If the file is specified, read from that. If not,
868
the inventory is created empty.
870
The inventory is created with a default root directory, with
873
if root_id is not None:
874
assert root_id.__class__ == str
875
self._set_root(InventoryDirectory(root_id, u'', None))
879
self.revision_id = revision_id
882
return "<Inventory object at %x, contents=%r>" % (id(self), self._byid)
884
def apply_delta(self, delta):
885
"""Apply a delta to this inventory.
887
:param delta: A list of changes to apply. After all the changes are
888
applied the final inventory must be internally consistent, but it
889
is ok to supply changes which, if only half-applied would have an
890
invalid result - such as supplying two changes which rename two
891
files, 'A' and 'B' with each other : [('A', 'B', 'A-id', a_entry),
892
('B', 'A', 'B-id', b_entry)].
894
Each change is a tuple, of the form (old_path, new_path, file_id,
897
When new_path is None, the change indicates the removal of an entry
898
from the inventory and new_entry will be ignored (using None is
899
appropriate). If new_path is not None, then new_entry must be an
900
InventoryEntry instance, which will be incorporated into the
901
inventory (and replace any existing entry with the same file id).
903
When old_path is None, the change indicates the addition of
904
a new entry to the inventory.
906
When neither new_path nor old_path are None, the change is a
907
modification to an entry, such as a rename, reparent, kind change
910
The children attribute of new_entry is ignored. This is because
911
this method preserves children automatically across alterations to
912
the parent of the children, and cases where the parent id of a
913
child is changing require the child to be passed in as a separate
914
change regardless. E.g. in the recursive deletion of a directory -
915
the directory's children must be included in the delta, or the
916
final inventory will be invalid.
919
# Remove all affected items which were in the original inventory,
920
# starting with the longest paths, thus ensuring parents are examined
921
# after their children, which means that everything we examine has no
922
# modified children remaining by the time we examine it.
923
for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
924
if op is not None), reverse=True):
925
if file_id not in self:
928
# Preserve unaltered children of file_id for later reinsertion.
929
children[file_id] = getattr(self[file_id], 'children', {})
930
# Remove file_id and the unaltered children. If file_id is not
931
# being deleted it will be reinserted back later.
932
self.remove_recursive_id(file_id)
933
# Insert all affected which should be in the new inventory, reattaching
934
# their children if they had any. This is done from shortest path to
935
# longest, ensuring that items which were modified and whose parents in
936
# the resulting inventory were also modified, are inserted after their
938
for new_path, new_entry in sorted((np, e) for op, np, f, e in
939
delta if np is not None):
940
if new_entry.kind == 'directory':
941
new_entry.children = children.get(new_entry.file_id, {})
944
def _set_root(self, ie):
946
self._byid = {self.root.file_id: self.root}
949
# TODO: jam 20051218 Should copy also copy the revision_id?
950
entries = self.iter_entries()
951
if self.root is None:
952
return Inventory(root_id=None)
953
other = Inventory(entries.next()[1].file_id)
954
# copy recursively so we know directories will be added before
955
# their children. There are more efficient ways than this...
956
for path, entry in entries:
957
other.add(entry.copy())
961
return iter(self._byid)
964
"""Returns number of entries."""
965
return len(self._byid)
967
def iter_entries(self, from_dir=None):
968
"""Return (path, entry) pairs, in order by name."""
662
969
if from_dir is None:
663
970
if self.root is None:
665
972
from_dir = self.root
666
973
yield '', self.root
667
974
elif isinstance(from_dir, basestring):
668
from_dir = self[from_dir]
975
from_dir = self._byid[from_dir]
670
977
# unrolling the recursive called changed the time from
671
978
# 440ms/663ms (inline/total) to 116ms/116ms
672
979
children = from_dir.children.items()
675
for name, ie in children:
678
981
children = collections.deque(children)
679
982
stack = [(u'', children)]
828
1100
if ie.kind == 'directory':
829
1101
descend(ie, child_path)
831
if self.root is not None:
832
descend(self.root, u'')
835
def path2id(self, relpath):
836
"""Walk down through directories to return entry of last component.
838
:param relpath: may be either a list of path components, or a single
839
string, in which case it is automatically split.
841
This returns the entry of the last component in the path,
842
which may be either a file or a directory.
844
Returns None IFF the path is not found.
846
if isinstance(relpath, basestring):
847
names = osutils.splitpath(relpath)
853
except errors.NoSuchId:
854
# root doesn't exist yet so nothing else can
860
children = getattr(parent, 'children', None)
869
return parent.file_id
871
def filter(self, specific_fileids):
872
"""Get an inventory view filtered against a set of file-ids.
874
Children of directories and parents are included.
876
The result may or may not reference the underlying inventory
877
so it should be treated as immutable.
879
interesting_parents = set()
880
for fileid in specific_fileids:
882
interesting_parents.update(self.get_idpath(fileid))
883
except errors.NoSuchId:
884
# This fileid is not in the inventory - that's ok
886
entries = self.iter_entries()
887
if self.root is None:
888
return Inventory(root_id=None)
889
other = Inventory(entries.next()[1].file_id)
890
other.root.revision = self.root.revision
891
other.revision_id = self.revision_id
892
directories_to_expand = set()
893
for path, entry in entries:
894
file_id = entry.file_id
895
if (file_id in specific_fileids
896
or entry.parent_id in directories_to_expand):
897
if entry.kind == 'directory':
898
directories_to_expand.add(file_id)
899
elif file_id not in interesting_parents:
901
other.add(entry.copy())
904
def get_idpath(self, file_id):
905
"""Return a list of file_ids for the path to an entry.
907
The list contains one element for each directory followed by
908
the id of the file itself. So the length of the returned list
909
is equal to the depth of the file in the tree, counting the
910
root directory as depth 1.
913
for parent in self._iter_file_id_parents(file_id):
914
p.insert(0, parent.file_id)
918
class Inventory(CommonInventory):
919
"""Mutable dict based in-memory inventory.
921
We never store the full path to a file, because renaming a directory
922
implicitly moves all of its contents. This class internally maintains a
923
lookup tree that allows the children under a directory to be
926
>>> inv = Inventory()
927
>>> inv.add(InventoryFile('123-123', 'hello.c', ROOT_ID))
928
InventoryFile('123-123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
929
>>> inv['123-123'].name
932
Id's may be looked up from paths:
934
>>> inv.path2id('hello.c')
936
>>> inv.has_id('123-123')
939
There are iterators over the contents:
941
>>> [entry[0] for entry in inv.iter_entries()]
945
def __init__(self, root_id=ROOT_ID, revision_id=None):
946
"""Create or read an inventory.
948
If a working directory is specified, the inventory is read
949
from there. If the file is specified, read from that. If not,
950
the inventory is created empty.
952
The inventory is created with a default root directory, with
955
if root_id is not None:
956
self._set_root(InventoryDirectory(root_id, u'', None))
960
self.revision_id = revision_id
963
# More than one page of ouput is not useful anymore to debug
966
contents = repr(self._byid)
967
if len(contents) > max_len:
968
contents = contents[:(max_len-len(closing))] + closing
969
return "<Inventory object at %x, contents=%r>" % (id(self), contents)
971
def apply_delta(self, delta):
972
"""Apply a delta to this inventory.
974
See the inventory developers documentation for the theory behind
977
If delta application fails the inventory is left in an indeterminate
978
state and must not be used.
980
:param delta: A list of changes to apply. After all the changes are
981
applied the final inventory must be internally consistent, but it
982
is ok to supply changes which, if only half-applied would have an
983
invalid result - such as supplying two changes which rename two
984
files, 'A' and 'B' with each other : [('A', 'B', 'A-id', a_entry),
985
('B', 'A', 'B-id', b_entry)].
987
Each change is a tuple, of the form (old_path, new_path, file_id,
990
When new_path is None, the change indicates the removal of an entry
991
from the inventory and new_entry will be ignored (using None is
992
appropriate). If new_path is not None, then new_entry must be an
993
InventoryEntry instance, which will be incorporated into the
994
inventory (and replace any existing entry with the same file id).
996
When old_path is None, the change indicates the addition of
997
a new entry to the inventory.
999
When neither new_path nor old_path are None, the change is a
1000
modification to an entry, such as a rename, reparent, kind change
1003
The children attribute of new_entry is ignored. This is because
1004
this method preserves children automatically across alterations to
1005
the parent of the children, and cases where the parent id of a
1006
child is changing require the child to be passed in as a separate
1007
change regardless. E.g. in the recursive deletion of a directory -
1008
the directory's children must be included in the delta, or the
1009
final inventory will be invalid.
1011
Note that a file_id must only appear once within a given delta.
1012
An AssertionError is raised otherwise.
1014
# Check that the delta is legal. It would be nice if this could be
1015
# done within the loops below but it's safer to validate the delta
1016
# before starting to mutate the inventory, as there isn't a rollback
1018
list(_check_delta_unique_ids(_check_delta_unique_new_paths(
1019
_check_delta_unique_old_paths(_check_delta_ids_match_entry(
1020
_check_delta_ids_are_valid(
1021
_check_delta_new_path_entry_both_or_None(
1025
# Remove all affected items which were in the original inventory,
1026
# starting with the longest paths, thus ensuring parents are examined
1027
# after their children, which means that everything we examine has no
1028
# modified children remaining by the time we examine it.
1029
for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
1030
if op is not None), reverse=True):
1031
# Preserve unaltered children of file_id for later reinsertion.
1032
file_id_children = getattr(self[file_id], 'children', {})
1033
if len(file_id_children):
1034
children[file_id] = file_id_children
1035
if self.id2path(file_id) != old_path:
1036
raise errors.InconsistentDelta(old_path, file_id,
1037
"Entry was at wrong other path %r." % self.id2path(file_id))
1038
# Remove file_id and the unaltered children. If file_id is not
1039
# being deleted it will be reinserted back later.
1040
self.remove_recursive_id(file_id)
1041
# Insert all affected which should be in the new inventory, reattaching
1042
# their children if they had any. This is done from shortest path to
1043
# longest, ensuring that items which were modified and whose parents in
1044
# the resulting inventory were also modified, are inserted after their
1046
for new_path, f, new_entry in sorted((np, f, e) for op, np, f, e in
1047
delta if np is not None):
1048
if new_entry.kind == 'directory':
1049
# Pop the child which to allow detection of children whose
1050
# parents were deleted and which were not reattached to a new
1052
replacement = InventoryDirectory(new_entry.file_id,
1053
new_entry.name, new_entry.parent_id)
1054
replacement.revision = new_entry.revision
1055
replacement.children = children.pop(replacement.file_id, {})
1056
new_entry = replacement
1059
except errors.DuplicateFileId:
1060
raise errors.InconsistentDelta(new_path, new_entry.file_id,
1061
"New id is already present in target.")
1062
except AttributeError:
1063
raise errors.InconsistentDelta(new_path, new_entry.file_id,
1064
"Parent is not a directory.")
1065
if self.id2path(new_entry.file_id) != new_path:
1066
raise errors.InconsistentDelta(new_path, new_entry.file_id,
1067
"New path is not consistent with parent path.")
1069
# Get the parent id that was deleted
1070
parent_id, children = children.popitem()
1071
raise errors.InconsistentDelta("<deleted>", parent_id,
1072
"The file id was deleted but its children were not deleted.")
1074
def create_by_apply_delta(self, inventory_delta, new_revision_id,
1075
propagate_caches=False):
1076
"""See CHKInventory.create_by_apply_delta()"""
1077
new_inv = self.copy()
1078
new_inv.apply_delta(inventory_delta)
1079
new_inv.revision_id = new_revision_id
1082
def _set_root(self, ie):
1084
self._byid = {self.root.file_id: self.root}
1087
# TODO: jam 20051218 Should copy also copy the revision_id?
1088
entries = self.iter_entries()
1089
if self.root is None:
1090
return Inventory(root_id=None)
1091
other = Inventory(entries.next()[1].file_id)
1092
other.root.revision = self.root.revision
1093
# copy recursively so we know directories will be added before
1094
# their children. There are more efficient ways than this...
1095
for path, entry in entries:
1096
other.add(entry.copy())
1100
"""Iterate over all file-ids."""
1101
return iter(self._byid)
1103
def iter_just_entries(self):
1104
"""Iterate over all entries.
1103
descend(self.root, u'')
1106
def directories(self):
1107
"""Return (path, entry) pairs for all directories, including the root.
1110
def descend(parent_ie, parent_path):
1111
accum.append((parent_path, parent_ie))
1113
kids = [(ie.name, ie) for ie in parent_ie.children.itervalues() if ie.kind == 'directory']
1116
for name, child_ie in kids:
1117
child_path = osutils.pathjoin(parent_path, name)
1118
descend(child_ie, child_path)
1119
descend(self.root, u'')
1106
Unlike iter_entries(), just the entries are returned (not (path, ie))
1107
and the order of entries is undefined.
1122
def __contains__(self, file_id):
1123
"""True if this entry contains a file with given id.
1109
XXX: We may not want to merge this into bzr.dev.
1125
>>> inv = Inventory()
1126
>>> inv.add(InventoryFile('123', 'foo.c', ROOT_ID))
1127
InventoryFile('123', 'foo.c', parent_id='TREE_ROOT', sha1=None, len=None)
1111
if self.root is None:
1113
for _, ie in self._byid.iteritems():
1117
"""Returns number of entries."""
1118
return len(self._byid)
1133
return (file_id in self._byid)
1120
1135
def __getitem__(self, file_id):
1121
1136
"""Return the entry for given file_id.
1123
1138
>>> inv = Inventory()
1124
1139
>>> inv.add(InventoryFile('123123', 'hello.c', ROOT_ID))
1125
InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None, revision=None)
1140
InventoryFile('123123', 'hello.c', parent_id='TREE_ROOT', sha1=None, len=None)
1126
1141
>>> inv['123123'].name
1341
1395
return self.root is not None and file_id == self.root.file_id
1344
class CHKInventory(CommonInventory):
1345
"""An inventory persisted in a CHK store.
1347
By design, a CHKInventory is immutable so many of the methods
1348
supported by Inventory - add, rename, apply_delta, etc - are *not*
1349
supported. To create a new CHKInventory, use create_by_apply_delta()
1350
or from_inventory(), say.
1352
Internally, a CHKInventory has one or two CHKMaps:
1354
* id_to_entry - a map from (file_id,) => InventoryEntry as bytes
1355
* parent_id_basename_to_file_id - a map from (parent_id, basename_utf8)
1358
The second map is optional and not present in early CHkRepository's.
1360
No caching is performed: every method call or item access will perform
1361
requests to the storage layer. As such, keep references to objects you
1365
def __init__(self, search_key_name):
1366
CommonInventory.__init__(self)
1367
self._fileid_to_entry_cache = {}
1368
self._fully_cached = False
1369
self._path_to_fileid_cache = {}
1370
self._search_key_name = search_key_name
1373
def __eq__(self, other):
1374
"""Compare two sets by comparing their contents."""
1375
if not isinstance(other, CHKInventory):
1376
return NotImplemented
1378
this_key = self.id_to_entry.key()
1379
other_key = other.id_to_entry.key()
1380
this_pid_key = self.parent_id_basename_to_file_id.key()
1381
other_pid_key = other.parent_id_basename_to_file_id.key()
1382
if None in (this_key, this_pid_key, other_key, other_pid_key):
1384
return this_key == other_key and this_pid_key == other_pid_key
1386
def _entry_to_bytes(self, entry):
1387
"""Serialise entry as a single bytestring.
1389
:param Entry: An inventory entry.
1390
:return: A bytestring for the entry.
1393
ENTRY ::= FILE | DIR | SYMLINK | TREE
1394
FILE ::= "file: " COMMON SEP SHA SEP SIZE SEP EXECUTABLE
1395
DIR ::= "dir: " COMMON
1396
SYMLINK ::= "symlink: " COMMON SEP TARGET_UTF8
1397
TREE ::= "tree: " COMMON REFERENCE_REVISION
1398
COMMON ::= FILE_ID SEP PARENT_ID SEP NAME_UTF8 SEP REVISION
1401
if entry.parent_id is not None:
1402
parent_str = entry.parent_id
1405
name_str = entry.name.encode("utf8")
1406
if entry.kind == 'file':
1407
if entry.executable:
1411
return "file: %s\n%s\n%s\n%s\n%s\n%d\n%s" % (
1412
entry.file_id, parent_str, name_str, entry.revision,
1413
entry.text_sha1, entry.text_size, exec_str)
1414
elif entry.kind == 'directory':
1415
return "dir: %s\n%s\n%s\n%s" % (
1416
entry.file_id, parent_str, name_str, entry.revision)
1417
elif entry.kind == 'symlink':
1418
return "symlink: %s\n%s\n%s\n%s\n%s" % (
1419
entry.file_id, parent_str, name_str, entry.revision,
1420
entry.symlink_target.encode("utf8"))
1421
elif entry.kind == 'tree-reference':
1422
return "tree: %s\n%s\n%s\n%s\n%s" % (
1423
entry.file_id, parent_str, name_str, entry.revision,
1424
entry.reference_revision)
1426
raise ValueError("unknown kind %r" % entry.kind)
1428
def _expand_fileids_to_parents_and_children(self, file_ids):
1429
"""Give a more wholistic view starting with the given file_ids.
1431
For any file_id which maps to a directory, we will include all children
1432
of that directory. We will also include all directories which are
1433
parents of the given file_ids, but we will not include their children.
1440
fringle # fringle-id
1444
if given [foo-id] we will include
1445
TREE_ROOT as interesting parents
1447
foo-id, baz-id, frob-id, fringle-id
1451
# TODO: Pre-pass over the list of fileids to see if anything is already
1452
# deserialized in self._fileid_to_entry_cache
1454
directories_to_expand = set()
1455
children_of_parent_id = {}
1456
# It is okay if some of the fileids are missing
1457
for entry in self._getitems(file_ids):
1458
if entry.kind == 'directory':
1459
directories_to_expand.add(entry.file_id)
1460
interesting.add(entry.parent_id)
1461
children_of_parent_id.setdefault(entry.parent_id, set()
1462
).add(entry.file_id)
1464
# Now, interesting has all of the direct parents, but not the
1465
# parents of those parents. It also may have some duplicates with
1467
remaining_parents = interesting.difference(file_ids)
1468
# When we hit the TREE_ROOT, we'll get an interesting parent of None,
1469
# but we don't actually want to recurse into that
1470
interesting.add(None) # this will auto-filter it in the loop
1471
remaining_parents.discard(None)
1472
while remaining_parents:
1473
next_parents = set()
1474
for entry in self._getitems(remaining_parents):
1475
next_parents.add(entry.parent_id)
1476
children_of_parent_id.setdefault(entry.parent_id, set()
1477
).add(entry.file_id)
1478
# Remove any search tips we've already processed
1479
remaining_parents = next_parents.difference(interesting)
1480
interesting.update(remaining_parents)
1481
# We should probably also .difference(directories_to_expand)
1482
interesting.update(file_ids)
1483
interesting.discard(None)
1484
while directories_to_expand:
1485
# Expand directories by looking in the
1486
# parent_id_basename_to_file_id map
1487
keys = [StaticTuple(f,).intern() for f in directories_to_expand]
1488
directories_to_expand = set()
1489
items = self.parent_id_basename_to_file_id.iteritems(keys)
1490
next_file_ids = set([item[1] for item in items])
1491
next_file_ids = next_file_ids.difference(interesting)
1492
interesting.update(next_file_ids)
1493
for entry in self._getitems(next_file_ids):
1494
if entry.kind == 'directory':
1495
directories_to_expand.add(entry.file_id)
1496
children_of_parent_id.setdefault(entry.parent_id, set()
1497
).add(entry.file_id)
1498
return interesting, children_of_parent_id
1500
def filter(self, specific_fileids):
1501
"""Get an inventory view filtered against a set of file-ids.
1503
Children of directories and parents are included.
1505
The result may or may not reference the underlying inventory
1506
so it should be treated as immutable.
1509
parent_to_children) = self._expand_fileids_to_parents_and_children(
1511
# There is some overlap here, but we assume that all interesting items
1512
# are in the _fileid_to_entry_cache because we had to read them to
1513
# determine if they were a dir we wanted to recurse, or just a file
1514
# This should give us all the entries we'll want to add, so start
1516
other = Inventory(self.root_id)
1517
other.root.revision = self.root.revision
1518
other.revision_id = self.revision_id
1519
if not interesting or not parent_to_children:
1520
# empty filter, or filtering entrys that don't exist
1521
# (if even 1 existed, then we would have populated
1522
# parent_to_children with at least the tree root.)
1524
cache = self._fileid_to_entry_cache
1525
remaining_children = collections.deque(parent_to_children[self.root_id])
1526
while remaining_children:
1527
file_id = remaining_children.popleft()
1529
if ie.kind == 'directory':
1530
ie = ie.copy() # We create a copy to depopulate the .children attribute
1531
# TODO: depending on the uses of 'other' we should probably alwyas
1532
# '.copy()' to prevent someone from mutating other and
1533
# invaliding our internal cache
1535
if file_id in parent_to_children:
1536
remaining_children.extend(parent_to_children[file_id])
1540
def _bytes_to_utf8name_key(bytes):
1541
"""Get the file_id, revision_id key out of bytes."""
1542
# We don't normally care about name, except for times when we want
1543
# to filter out empty names because of non rich-root...
1544
sections = bytes.split('\n')
1545
kind, file_id = sections[0].split(': ')
1546
return (sections[2], intern(file_id), intern(sections[3]))
1548
def _bytes_to_entry(self, bytes):
1549
"""Deserialise a serialised entry."""
1550
sections = bytes.split('\n')
1551
if sections[0].startswith("file: "):
1552
result = InventoryFile(sections[0][6:],
1553
sections[2].decode('utf8'),
1555
result.text_sha1 = sections[4]
1556
result.text_size = int(sections[5])
1557
result.executable = sections[6] == "Y"
1558
elif sections[0].startswith("dir: "):
1559
result = CHKInventoryDirectory(sections[0][5:],
1560
sections[2].decode('utf8'),
1562
elif sections[0].startswith("symlink: "):
1563
result = InventoryLink(sections[0][9:],
1564
sections[2].decode('utf8'),
1566
result.symlink_target = sections[4].decode('utf8')
1567
elif sections[0].startswith("tree: "):
1568
result = TreeReference(sections[0][6:],
1569
sections[2].decode('utf8'),
1571
result.reference_revision = sections[4]
1573
raise ValueError("Not a serialised entry %r" % bytes)
1574
result.file_id = intern(result.file_id)
1575
result.revision = intern(sections[3])
1576
if result.parent_id == '':
1577
result.parent_id = None
1578
self._fileid_to_entry_cache[result.file_id] = result
1581
def create_by_apply_delta(self, inventory_delta, new_revision_id,
1582
propagate_caches=False):
1583
"""Create a new CHKInventory by applying inventory_delta to this one.
1585
See the inventory developers documentation for the theory behind
1588
:param inventory_delta: The inventory delta to apply. See
1589
Inventory.apply_delta for details.
1590
:param new_revision_id: The revision id of the resulting CHKInventory.
1591
:param propagate_caches: If True, the caches for this inventory are
1592
copied to and updated for the result.
1593
:return: The new CHKInventory.
1595
split = osutils.split
1596
result = CHKInventory(self._search_key_name)
1597
if propagate_caches:
1598
# Just propagate the path-to-fileid cache for now
1599
result._path_to_fileid_cache = dict(self._path_to_fileid_cache.iteritems())
1600
search_key_func = chk_map.search_key_registry.get(self._search_key_name)
1601
self.id_to_entry._ensure_root()
1602
maximum_size = self.id_to_entry._root_node.maximum_size
1603
result.revision_id = new_revision_id
1604
result.id_to_entry = chk_map.CHKMap(
1605
self.id_to_entry._store,
1606
self.id_to_entry.key(),
1607
search_key_func=search_key_func)
1608
result.id_to_entry._ensure_root()
1609
result.id_to_entry._root_node.set_maximum_size(maximum_size)
1610
# Change to apply to the parent_id_basename delta. The dict maps
1611
# (parent_id, basename) -> (old_key, new_value). We use a dict because
1612
# when a path has its id replaced (e.g. the root is changed, or someone
1613
# does bzr mv a b, bzr mv c a, we should output a single change to this
1614
# map rather than two.
1615
parent_id_basename_delta = {}
1616
if self.parent_id_basename_to_file_id is not None:
1617
result.parent_id_basename_to_file_id = chk_map.CHKMap(
1618
self.parent_id_basename_to_file_id._store,
1619
self.parent_id_basename_to_file_id.key(),
1620
search_key_func=search_key_func)
1621
result.parent_id_basename_to_file_id._ensure_root()
1622
self.parent_id_basename_to_file_id._ensure_root()
1623
result_p_id_root = result.parent_id_basename_to_file_id._root_node
1624
p_id_root = self.parent_id_basename_to_file_id._root_node
1625
result_p_id_root.set_maximum_size(p_id_root.maximum_size)
1626
result_p_id_root._key_width = p_id_root._key_width
1628
result.parent_id_basename_to_file_id = None
1629
result.root_id = self.root_id
1630
id_to_entry_delta = []
1631
# inventory_delta is only traversed once, so we just update the
1633
# Check for repeated file ids
1634
inventory_delta = _check_delta_unique_ids(inventory_delta)
1635
# Repeated old paths
1636
inventory_delta = _check_delta_unique_old_paths(inventory_delta)
1637
# Check for repeated new paths
1638
inventory_delta = _check_delta_unique_new_paths(inventory_delta)
1639
# Check for entries that don't match the fileid
1640
inventory_delta = _check_delta_ids_match_entry(inventory_delta)
1641
# Check for nonsense fileids
1642
inventory_delta = _check_delta_ids_are_valid(inventory_delta)
1643
# Check for new_path <-> entry consistency
1644
inventory_delta = _check_delta_new_path_entry_both_or_None(
1646
# All changed entries need to have their parents be directories and be
1647
# at the right path. This set contains (path, id) tuples.
1649
# When we delete an item, all the children of it must be either deleted
1650
# or altered in their own right. As we batch process the change via
1651
# CHKMap.apply_delta, we build a set of things to use to validate the
1655
for old_path, new_path, file_id, entry in inventory_delta:
1658
result.root_id = file_id
1659
if new_path is None:
1664
if propagate_caches:
1666
del result._path_to_fileid_cache[old_path]
1669
deletes.add(file_id)
1671
new_key = StaticTuple(file_id,)
1672
new_value = result._entry_to_bytes(entry)
1673
# Update caches. It's worth doing this whether
1674
# we're propagating the old caches or not.
1675
result._path_to_fileid_cache[new_path] = file_id
1676
parents.add((split(new_path)[0], entry.parent_id))
1677
if old_path is None:
1680
old_key = StaticTuple(file_id,)
1681
if self.id2path(file_id) != old_path:
1682
raise errors.InconsistentDelta(old_path, file_id,
1683
"Entry was at wrong other path %r." %
1684
self.id2path(file_id))
1685
altered.add(file_id)
1686
id_to_entry_delta.append(StaticTuple(old_key, new_key, new_value))
1687
if result.parent_id_basename_to_file_id is not None:
1688
# parent_id, basename changes
1689
if old_path is None:
1692
old_entry = self[file_id]
1693
old_key = self._parent_id_basename_key(old_entry)
1694
if new_path is None:
1698
new_key = self._parent_id_basename_key(entry)
1700
# If the two keys are the same, the value will be unchanged
1701
# as its always the file id for this entry.
1702
if old_key != new_key:
1703
# Transform a change into explicit delete/add preserving
1704
# a possible match on the key from a different file id.
1705
if old_key is not None:
1706
parent_id_basename_delta.setdefault(
1707
old_key, [None, None])[0] = old_key
1708
if new_key is not None:
1709
parent_id_basename_delta.setdefault(
1710
new_key, [None, None])[1] = new_value
1711
# validate that deletes are complete.
1712
for file_id in deletes:
1713
entry = self[file_id]
1714
if entry.kind != 'directory':
1716
# This loop could potentially be better by using the id_basename
1717
# map to just get the child file ids.
1718
for child in entry.children.values():
1719
if child.file_id not in altered:
1720
raise errors.InconsistentDelta(self.id2path(child.file_id),
1721
child.file_id, "Child not deleted or reparented when "
1723
result.id_to_entry.apply_delta(id_to_entry_delta)
1724
if parent_id_basename_delta:
1725
# Transform the parent_id_basename delta data into a linear delta
1726
# with only one record for a given key. Optimally this would allow
1727
# re-keying, but its simpler to just output that as a delete+add
1728
# to spend less time calculating the delta.
1730
for key, (old_key, value) in parent_id_basename_delta.iteritems():
1731
if value is not None:
1732
delta_list.append((old_key, key, value))
1734
delta_list.append((old_key, None, None))
1735
result.parent_id_basename_to_file_id.apply_delta(delta_list)
1736
parents.discard(('', None))
1737
for parent_path, parent in parents:
1739
if result[parent].kind != 'directory':
1740
raise errors.InconsistentDelta(result.id2path(parent), parent,
1741
'Not a directory, but given children')
1742
except errors.NoSuchId:
1743
raise errors.InconsistentDelta("<unknown>", parent,
1744
"Parent is not present in resulting inventory.")
1745
if result.path2id(parent_path) != parent:
1746
raise errors.InconsistentDelta(parent_path, parent,
1747
"Parent has wrong path %r." % result.path2id(parent_path))
1751
def deserialise(klass, chk_store, bytes, expected_revision_id):
1752
"""Deserialise a CHKInventory.
1754
:param chk_store: A CHK capable VersionedFiles instance.
1755
:param bytes: The serialised bytes.
1756
:param expected_revision_id: The revision ID we think this inventory is
1758
:return: A CHKInventory
1760
lines = bytes.split('\n')
1762
raise AssertionError('bytes to deserialize must end with an eol')
1764
if lines[0] != 'chkinventory:':
1765
raise ValueError("not a serialised CHKInventory: %r" % bytes)
1767
allowed_keys = frozenset(['root_id', 'revision_id', 'search_key_name',
1768
'parent_id_basename_to_file_id',
1770
for line in lines[1:]:
1771
key, value = line.split(': ', 1)
1772
if key not in allowed_keys:
1773
raise errors.BzrError('Unknown key in inventory: %r\n%r'
1776
raise errors.BzrError('Duplicate key in inventory: %r\n%r'
1779
revision_id = intern(info['revision_id'])
1780
root_id = intern(info['root_id'])
1781
search_key_name = intern(info.get('search_key_name', 'plain'))
1782
parent_id_basename_to_file_id = intern(info.get(
1783
'parent_id_basename_to_file_id', None))
1784
if not parent_id_basename_to_file_id.startswith('sha1:'):
1785
raise ValueError('parent_id_basename_to_file_id should be a sha1'
1786
' key not %r' % (parent_id_basename_to_file_id,))
1787
id_to_entry = info['id_to_entry']
1788
if not id_to_entry.startswith('sha1:'):
1789
raise ValueError('id_to_entry should be a sha1'
1790
' key not %r' % (id_to_entry,))
1792
result = CHKInventory(search_key_name)
1793
result.revision_id = revision_id
1794
result.root_id = root_id
1795
search_key_func = chk_map.search_key_registry.get(
1796
result._search_key_name)
1797
if parent_id_basename_to_file_id is not None:
1798
result.parent_id_basename_to_file_id = chk_map.CHKMap(
1799
chk_store, StaticTuple(parent_id_basename_to_file_id,),
1800
search_key_func=search_key_func)
1802
result.parent_id_basename_to_file_id = None
1804
result.id_to_entry = chk_map.CHKMap(chk_store,
1805
StaticTuple(id_to_entry,),
1806
search_key_func=search_key_func)
1807
if (result.revision_id,) != expected_revision_id:
1808
raise ValueError("Mismatched revision id and expected: %r, %r" %
1809
(result.revision_id, expected_revision_id))
1813
def from_inventory(klass, chk_store, inventory, maximum_size=0, search_key_name='plain'):
1814
"""Create a CHKInventory from an existing inventory.
1816
The content of inventory is copied into the chk_store, and a
1817
CHKInventory referencing that is returned.
1819
:param chk_store: A CHK capable VersionedFiles instance.
1820
:param inventory: The inventory to copy.
1821
:param maximum_size: The CHKMap node size limit.
1822
:param search_key_name: The identifier for the search key function
1824
result = klass(search_key_name)
1825
result.revision_id = inventory.revision_id
1826
result.root_id = inventory.root.file_id
1828
entry_to_bytes = result._entry_to_bytes
1829
parent_id_basename_key = result._parent_id_basename_key
1830
id_to_entry_dict = {}
1831
parent_id_basename_dict = {}
1832
for path, entry in inventory.iter_entries():
1833
key = StaticTuple(entry.file_id,).intern()
1834
id_to_entry_dict[key] = entry_to_bytes(entry)
1835
p_id_key = parent_id_basename_key(entry)
1836
parent_id_basename_dict[p_id_key] = entry.file_id
1838
result._populate_from_dicts(chk_store, id_to_entry_dict,
1839
parent_id_basename_dict, maximum_size=maximum_size)
1842
def _populate_from_dicts(self, chk_store, id_to_entry_dict,
1843
parent_id_basename_dict, maximum_size):
1844
search_key_func = chk_map.search_key_registry.get(self._search_key_name)
1845
root_key = chk_map.CHKMap.from_dict(chk_store, id_to_entry_dict,
1846
maximum_size=maximum_size, key_width=1,
1847
search_key_func=search_key_func)
1848
self.id_to_entry = chk_map.CHKMap(chk_store, root_key,
1850
root_key = chk_map.CHKMap.from_dict(chk_store,
1851
parent_id_basename_dict,
1852
maximum_size=maximum_size, key_width=2,
1853
search_key_func=search_key_func)
1854
self.parent_id_basename_to_file_id = chk_map.CHKMap(chk_store,
1855
root_key, search_key_func)
1857
def _parent_id_basename_key(self, entry):
1858
"""Create a key for a entry in a parent_id_basename_to_file_id index."""
1859
if entry.parent_id is not None:
1860
parent_id = entry.parent_id
1863
return StaticTuple(parent_id, entry.name.encode('utf8')).intern()
1865
def __getitem__(self, file_id):
1866
"""map a single file_id -> InventoryEntry."""
1868
raise errors.NoSuchId(self, file_id)
1869
result = self._fileid_to_entry_cache.get(file_id, None)
1870
if result is not None:
1873
return self._bytes_to_entry(
1874
self.id_to_entry.iteritems([StaticTuple(file_id,)]).next()[1])
1875
except StopIteration:
1876
# really we're passing an inventory, not a tree...
1877
raise errors.NoSuchId(self, file_id)
1879
def _getitems(self, file_ids):
1880
"""Similar to __getitem__, but lets you query for multiple.
1882
The returned order is undefined. And currently if an item doesn't
1883
exist, it isn't included in the output.
1887
for file_id in file_ids:
1888
entry = self._fileid_to_entry_cache.get(file_id, None)
1890
remaining.append(file_id)
1892
result.append(entry)
1893
file_keys = [StaticTuple(f,).intern() for f in remaining]
1894
for file_key, value in self.id_to_entry.iteritems(file_keys):
1895
entry = self._bytes_to_entry(value)
1896
result.append(entry)
1897
self._fileid_to_entry_cache[entry.file_id] = entry
1900
def has_id(self, file_id):
1901
# Perhaps have an explicit 'contains' method on CHKMap ?
1902
if self._fileid_to_entry_cache.get(file_id, None) is not None:
1905
self.id_to_entry.iteritems([StaticTuple(file_id,)]))) == 1
1907
def is_root(self, file_id):
1908
return file_id == self.root_id
1910
def _iter_file_id_parents(self, file_id):
1911
"""Yield the parents of file_id up to the root."""
1912
while file_id is not None:
1916
raise errors.NoSuchId(tree=self, file_id=file_id)
1918
file_id = ie.parent_id
1921
"""Iterate over all file-ids."""
1922
for key, _ in self.id_to_entry.iteritems():
1925
def iter_just_entries(self):
1926
"""Iterate over all entries.
1928
Unlike iter_entries(), just the entries are returned (not (path, ie))
1929
and the order of entries is undefined.
1931
XXX: We may not want to merge this into bzr.dev.
1933
for key, entry in self.id_to_entry.iteritems():
1935
ie = self._fileid_to_entry_cache.get(file_id, None)
1937
ie = self._bytes_to_entry(entry)
1938
self._fileid_to_entry_cache[file_id] = ie
1941
def _preload_cache(self):
1942
"""Make sure all file-ids are in _fileid_to_entry_cache"""
1943
if self._fully_cached:
1944
return # No need to do it again
1945
# The optimal sort order is to use iteritems() directly
1946
cache = self._fileid_to_entry_cache
1947
for key, entry in self.id_to_entry.iteritems():
1949
if file_id not in cache:
1950
ie = self._bytes_to_entry(entry)
1954
last_parent_id = last_parent_ie = None
1955
pid_items = self.parent_id_basename_to_file_id.iteritems()
1956
for key, child_file_id in pid_items:
1957
if key == ('', ''): # This is the root
1958
if child_file_id != self.root_id:
1959
raise ValueError('Data inconsistency detected.'
1960
' We expected data with key ("","") to match'
1961
' the root id, but %s != %s'
1962
% (child_file_id, self.root_id))
1964
parent_id, basename = key
1965
ie = cache[child_file_id]
1966
if parent_id == last_parent_id:
1967
parent_ie = last_parent_ie
1969
parent_ie = cache[parent_id]
1970
if parent_ie.kind != 'directory':
1971
raise ValueError('Data inconsistency detected.'
1972
' An entry in the parent_id_basename_to_file_id map'
1973
' has parent_id {%s} but the kind of that object'
1974
' is %r not "directory"' % (parent_id, parent_ie.kind))
1975
if parent_ie._children is None:
1976
parent_ie._children = {}
1977
basename = basename.decode('utf-8')
1978
if basename in parent_ie._children:
1979
existing_ie = parent_ie._children[basename]
1980
if existing_ie != ie:
1981
raise ValueError('Data inconsistency detected.'
1982
' Two entries with basename %r were found'
1983
' in the parent entry {%s}'
1984
% (basename, parent_id))
1985
if basename != ie.name:
1986
raise ValueError('Data inconsistency detected.'
1987
' In the parent_id_basename_to_file_id map, file_id'
1988
' {%s} is listed as having basename %r, but in the'
1989
' id_to_entry map it is %r'
1990
% (child_file_id, basename, ie.name))
1991
parent_ie._children[basename] = ie
1992
self._fully_cached = True
1994
def iter_changes(self, basis):
1995
"""Generate a Tree.iter_changes change list between this and basis.
1997
:param basis: Another CHKInventory.
1998
:return: An iterator over the changes between self and basis, as per
1999
tree.iter_changes().
2001
# We want: (file_id, (path_in_source, path_in_target),
2002
# changed_content, versioned, parent, name, kind,
2004
for key, basis_value, self_value in \
2005
self.id_to_entry.iter_changes(basis.id_to_entry):
2007
if basis_value is not None:
2008
basis_entry = basis._bytes_to_entry(basis_value)
2009
path_in_source = basis.id2path(file_id)
2010
basis_parent = basis_entry.parent_id
2011
basis_name = basis_entry.name
2012
basis_executable = basis_entry.executable
2014
path_in_source = None
2017
basis_executable = None
2018
if self_value is not None:
2019
self_entry = self._bytes_to_entry(self_value)
2020
path_in_target = self.id2path(file_id)
2021
self_parent = self_entry.parent_id
2022
self_name = self_entry.name
2023
self_executable = self_entry.executable
2025
path_in_target = None
2028
self_executable = None
2029
if basis_value is None:
2031
kind = (None, self_entry.kind)
2032
versioned = (False, True)
2033
elif self_value is None:
2035
kind = (basis_entry.kind, None)
2036
versioned = (True, False)
2038
kind = (basis_entry.kind, self_entry.kind)
2039
versioned = (True, True)
2040
changed_content = False
2041
if kind[0] != kind[1]:
2042
changed_content = True
2043
elif kind[0] == 'file':
2044
if (self_entry.text_size != basis_entry.text_size or
2045
self_entry.text_sha1 != basis_entry.text_sha1):
2046
changed_content = True
2047
elif kind[0] == 'symlink':
2048
if self_entry.symlink_target != basis_entry.symlink_target:
2049
changed_content = True
2050
elif kind[0] == 'tree-reference':
2051
if (self_entry.reference_revision !=
2052
basis_entry.reference_revision):
2053
changed_content = True
2054
parent = (basis_parent, self_parent)
2055
name = (basis_name, self_name)
2056
executable = (basis_executable, self_executable)
2057
if (not changed_content
2058
and parent[0] == parent[1]
2059
and name[0] == name[1]
2060
and executable[0] == executable[1]):
2061
# Could happen when only the revision changed for a directory
2064
yield (file_id, (path_in_source, path_in_target), changed_content,
2065
versioned, parent, name, kind, executable)
2068
"""Return the number of entries in the inventory."""
2069
return len(self.id_to_entry)
2071
def _make_delta(self, old):
2072
"""Make an inventory delta from two inventories."""
2073
if type(old) != CHKInventory:
2074
return CommonInventory._make_delta(self, old)
2076
for key, old_value, self_value in \
2077
self.id_to_entry.iter_changes(old.id_to_entry):
2079
if old_value is not None:
2080
old_path = old.id2path(file_id)
2083
if self_value is not None:
2084
entry = self._bytes_to_entry(self_value)
2085
self._fileid_to_entry_cache[file_id] = entry
2086
new_path = self.id2path(file_id)
2090
delta.append((old_path, new_path, file_id, entry))
2093
def path2id(self, relpath):
2094
"""See CommonInventory.path2id()."""
2095
# TODO: perhaps support negative hits?
2096
if isinstance(relpath, basestring):
2097
names = osutils.splitpath(relpath)
2102
relpath = osutils.pathjoin(*relpath)
2103
result = self._path_to_fileid_cache.get(relpath, None)
2104
if result is not None:
2106
current_id = self.root_id
2107
if current_id is None:
2109
parent_id_index = self.parent_id_basename_to_file_id
2111
for basename in names:
2112
if cur_path is None:
2115
cur_path = cur_path + '/' + basename
2116
basename_utf8 = basename.encode('utf8')
2117
file_id = self._path_to_fileid_cache.get(cur_path, None)
2119
key_filter = [StaticTuple(current_id, basename_utf8)]
2120
items = parent_id_index.iteritems(key_filter)
2121
for (parent_id, name_utf8), file_id in items:
2122
if parent_id != current_id or name_utf8 != basename_utf8:
2123
raise errors.BzrError("corrupt inventory lookup! "
2124
"%r %r %r %r" % (parent_id, current_id, name_utf8,
2129
self._path_to_fileid_cache[cur_path] = file_id
2130
current_id = file_id
2134
"""Serialise the inventory to lines."""
2135
lines = ["chkinventory:\n"]
2136
if self._search_key_name != 'plain':
2137
# custom ordering grouping things that don't change together
2138
lines.append('search_key_name: %s\n' % (self._search_key_name,))
2139
lines.append("root_id: %s\n" % self.root_id)
2140
lines.append('parent_id_basename_to_file_id: %s\n' %
2141
(self.parent_id_basename_to_file_id.key()[0],))
2142
lines.append("revision_id: %s\n" % self.revision_id)
2143
lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
2145
lines.append("revision_id: %s\n" % self.revision_id)
2146
lines.append("root_id: %s\n" % self.root_id)
2147
if self.parent_id_basename_to_file_id is not None:
2148
lines.append('parent_id_basename_to_file_id: %s\n' %
2149
(self.parent_id_basename_to_file_id.key()[0],))
2150
lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
2155
"""Get the root entry."""
2156
return self[self.root_id]
2159
class CHKInventoryDirectory(InventoryDirectory):
2160
"""A directory in an inventory."""
2162
__slots__ = ['_children', '_chk_inventory']
2164
def __init__(self, file_id, name, parent_id, chk_inventory):
2165
# Don't call InventoryDirectory.__init__ - it isn't right for this
2167
InventoryEntry.__init__(self, file_id, name, parent_id)
2168
self._children = None
2169
self._chk_inventory = chk_inventory
2173
"""Access the list of children of this directory.
2175
With a parent_id_basename_to_file_id index, loads all the children,
2176
without loads the entire index. Without is bad. A more sophisticated
2177
proxy object might be nice, to allow partial loading of children as
2178
well when specific names are accessed. (So path traversal can be
2179
written in the obvious way but not examine siblings.).
2181
if self._children is not None:
2182
return self._children
2183
# No longer supported
2184
if self._chk_inventory.parent_id_basename_to_file_id is None:
2185
raise AssertionError("Inventories without"
2186
" parent_id_basename_to_file_id are no longer supported")
2188
# XXX: Todo - use proxy objects for the children rather than loading
2189
# all when the attribute is referenced.
2190
parent_id_index = self._chk_inventory.parent_id_basename_to_file_id
2192
for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
2193
key_filter=[StaticTuple(self.file_id,)]):
2194
child_keys.add(StaticTuple(file_id,))
2196
for file_id_key in child_keys:
2197
entry = self._chk_inventory._fileid_to_entry_cache.get(
2198
file_id_key[0], None)
2199
if entry is not None:
2200
result[entry.name] = entry
2201
cached.add(file_id_key)
2202
child_keys.difference_update(cached)
2203
# populate; todo: do by name
2204
id_to_entry = self._chk_inventory.id_to_entry
2205
for file_id_key, bytes in id_to_entry.iteritems(child_keys):
2206
entry = self._chk_inventory._bytes_to_entry(bytes)
2207
result[entry.name] = entry
2208
self._chk_inventory._fileid_to_entry_cache[file_id_key[0]] = entry
2209
self._children = result
2212
1398
entry_factory = {
2213
1399
'directory': InventoryDirectory,
2214
1400
'file': InventoryFile,
added
removed
bzrlib/inventory.py
