← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/inventory.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-07-20 08:56:45 UTC
  • mfrom: (4526.9.23 apply-inventory-delta)
  • Revision ID: pqm@pqm.ubuntu.com-20090720085645-54mtgybxua0yx6hw
(robertc) Add checks for inventory deltas which try to ensure that
        deltas that are not an exact fit are not applied. (Robert
        Collins, bug 397705, bug 367633)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/inventory.py
1089
1089
        See the inventory developers documentation for the theory behind
1090
1090
        inventory deltas.
1091
1091
 
 
1092
        If delta application fails the inventory is left in an indeterminate
 
1093
        state and must not be used.
 
1094
 
1092
1095
        :param delta: A list of changes to apply. After all the changes are
1093
1096
            applied the final inventory must be internally consistent, but it
1094
1097
            is ok to supply changes which, if only half-applied would have an
1129
1132
        # facility.
1130
1133
        list(_check_delta_unique_ids(_check_delta_unique_new_paths(
1131
1134
            _check_delta_unique_old_paths(_check_delta_ids_match_entry(
1132
 
            delta)))))
 
1135
            _check_delta_ids_are_valid(
 
1136
            _check_delta_new_path_entry_both_or_None(
 
1137
            delta)))))))
1133
1138
 
1134
1139
        children = {}
1135
1140
        # Remove all affected items which were in the original inventory,
1138
1143
        # modified children remaining by the time we examine it.
1139
1144
        for old_path, file_id in sorted(((op, f) for op, np, f, e in delta
1140
1145
                                        if op is not None), reverse=True):
1141
 
            if file_id not in self:
1142
 
                # adds come later
1143
 
                continue
1144
1146
            # Preserve unaltered children of file_id for later reinsertion.
1145
1147
            file_id_children = getattr(self[file_id], 'children', {})
1146
1148
            if len(file_id_children):
1147
1149
                children[file_id] = file_id_children
 
1150
            if self.id2path(file_id) != old_path:
 
1151
                raise errors.InconsistentDelta(old_path, file_id,
 
1152
                    "Entry was at wrong other path %r." % self.id2path(file_id))
1148
1153
            # Remove file_id and the unaltered children. If file_id is not
1149
1154
            # being deleted it will be reinserted back later.
1150
1155
            self.remove_recursive_id(file_id)
1153
1158
        # longest, ensuring that items which were modified and whose parents in
1154
1159
        # the resulting inventory were also modified, are inserted after their
1155
1160
        # parents.
1156
 
        for new_path, new_entry in sorted((np, e) for op, np, f, e in
 
1161
        for new_path, f, new_entry in sorted((np, f, e) for op, np, f, e in
1157
1162
                                          delta if np is not None):
1158
1163
            if new_entry.kind == 'directory':
1159
1164
                # Pop the child which to allow detection of children whose
1166
1171
                new_entry = replacement
1167
1172
            try:
1168
1173
                self.add(new_entry)
 
1174
            except errors.DuplicateFileId:
 
1175
                raise errors.InconsistentDelta(new_path, new_entry.file_id,
 
1176
                    "New id is already present in target.")
1169
1177
            except AttributeError:
1170
1178
                raise errors.InconsistentDelta(new_path, new_entry.file_id,
1171
1179
                    "Parent is not a directory.")
 
1180
            if self.id2path(new_entry.file_id) != new_path:
 
1181
                raise errors.InconsistentDelta(new_path, new_entry.file_id,
 
1182
                    "New path is not consistent with parent path.")
1172
1183
        if len(children):
1173
1184
            # Get the parent id that was deleted
1174
1185
            parent_id, children = children.popitem()
1254
1265
        To add  a file to a branch ready to be committed, use Branch.add,
1255
1266
        which calls this.
1256
1267
 
1257
 
        Returns the new entry object.
 
1268
        :return: entry
1258
1269
        """
1259
1270
        if entry.file_id in self._byid:
1260
1271
            raise errors.DuplicateFileId(entry.file_id,
1261
1272
                                         self._byid[entry.file_id])
1262
 
 
1263
1273
        if entry.parent_id is None:
1264
1274
            self.root = entry
1265
1275
        else:
1471
1481
        self._fileid_to_entry_cache = {}
1472
1482
        self._path_to_fileid_cache = {}
1473
1483
        self._search_key_name = search_key_name
 
1484
        self.root_id = None
1474
1485
 
1475
1486
    def __eq__(self, other):
1476
1487
        """Compare two sets by comparing their contents."""
1590
1601
          copied to and updated for the result.
1591
1602
        :return: The new CHKInventory.
1592
1603
        """
 
1604
        split = osutils.split
1593
1605
        result = CHKInventory(self._search_key_name)
1594
1606
        if propagate_caches:
1595
1607
            # Just propagate the path-to-fileid cache for now
1604
1616
            search_key_func=search_key_func)
1605
1617
        result.id_to_entry._ensure_root()
1606
1618
        result.id_to_entry._root_node.set_maximum_size(maximum_size)
1607
 
        parent_id_basename_delta = []
 
1619
        # Change to apply to the parent_id_basename delta. The dict maps
 
1620
        # (parent_id, basename) -> (old_key, new_value). We use a dict because
 
1621
        # when a path has its id replaced (e.g. the root is changed, or someone
 
1622
        # does bzr mv a b, bzr mv c a, we should output a single change to this
 
1623
        # map rather than two.
 
1624
        parent_id_basename_delta = {}
1608
1625
        if self.parent_id_basename_to_file_id is not None:
1609
1626
            result.parent_id_basename_to_file_id = chk_map.CHKMap(
1610
1627
                self.parent_id_basename_to_file_id._store,
1630
1647
        inventory_delta = _check_delta_unique_new_paths(inventory_delta)
1631
1648
        # Check for entries that don't match the fileid
1632
1649
        inventory_delta = _check_delta_ids_match_entry(inventory_delta)
1633
 
        # All changed entries need to have their parents be directories.
 
1650
        # Check for nonsense fileids
 
1651
        inventory_delta = _check_delta_ids_are_valid(inventory_delta)
 
1652
        # Check for new_path <-> entry consistency
 
1653
        inventory_delta = _check_delta_new_path_entry_both_or_None(
 
1654
            inventory_delta)
 
1655
        # All changed entries need to have their parents be directories and be
 
1656
        # at the right path. This set contains (path, id) tuples.
1634
1657
        parents = set()
 
1658
        # When we delete an item, all the children of it must be either deleted
 
1659
        # or altered in their own right. As we batch process the change via
 
1660
        # CHKMap.apply_delta, we build a set of things to use to validate the
 
1661
        # delta.
 
1662
        deletes = set()
 
1663
        altered = set()
1635
1664
        for old_path, new_path, file_id, entry in inventory_delta:
1636
1665
            # file id changes
1637
1666
            if new_path == '':
1646
1675
                        del result._path_to_fileid_cache[old_path]
1647
1676
                    except KeyError:
1648
1677
                        pass
 
1678
                deletes.add(file_id)
1649
1679
            else:
1650
1680
                new_key = (file_id,)
1651
1681
                new_value = result._entry_to_bytes(entry)
1652
1682
                # Update caches. It's worth doing this whether
1653
1683
                # we're propagating the old caches or not.
1654
1684
                result._path_to_fileid_cache[new_path] = file_id
1655
 
                parents.add(entry.parent_id)
 
1685
                parents.add((split(new_path)[0], entry.parent_id))
1656
1686
            if old_path is None:
1657
1687
                old_key = None
1658
1688
            else:
1659
1689
                old_key = (file_id,)
 
1690
                if self.id2path(file_id) != old_path:
 
1691
                    raise errors.InconsistentDelta(old_path, file_id,
 
1692
                        "Entry was at wrong other path %r." %
 
1693
                        self.id2path(file_id))
 
1694
                altered.add(file_id)
1660
1695
            id_to_entry_delta.append((old_key, new_key, new_value))
1661
1696
            if result.parent_id_basename_to_file_id is not None:
1662
1697
                # parent_id, basename changes
1671
1706
                else:
1672
1707
                    new_key = self._parent_id_basename_key(entry)
1673
1708
                    new_value = file_id
 
1709
                # If the two keys are the same, the value will be unchanged
 
1710
                # as its always the file id for this entry.
1674
1711
                if old_key != new_key:
1675
 
                    # If the two keys are the same, the value will be unchanged
1676
 
                    # as its always the file id.
1677
 
                    parent_id_basename_delta.append((old_key, new_key, new_value))
 
1712
                    # Transform a change into explicit delete/add preserving
 
1713
                    # a possible match on the key from a different file id.
 
1714
                    if old_key is not None:
 
1715
                        parent_id_basename_delta.setdefault(
 
1716
                            old_key, [None, None])[0] = old_key
 
1717
                    if new_key is not None:
 
1718
                        parent_id_basename_delta.setdefault(
 
1719
                            new_key, [None, None])[1] = new_value
 
1720
        # validate that deletes are complete.
 
1721
        for file_id in deletes:
 
1722
            entry = self[file_id]
 
1723
            if entry.kind != 'directory':
 
1724
                continue
 
1725
            # This loop could potentially be better by using the id_basename
 
1726
            # map to just get the child file ids.
 
1727
            for child in entry.children.values():
 
1728
                if child.file_id not in altered:
 
1729
                    raise errors.InconsistentDelta(self.id2path(child.file_id),
 
1730
                        child.file_id, "Child not deleted or reparented when "
 
1731
                        "parent deleted.")
1678
1732
        result.id_to_entry.apply_delta(id_to_entry_delta)
1679
1733
        if parent_id_basename_delta:
1680
 
            result.parent_id_basename_to_file_id.apply_delta(parent_id_basename_delta)
1681
 
        parents.discard(None)
1682
 
        for parent in parents:
 
1734
            # Transform the parent_id_basename delta data into a linear delta
 
1735
            # with only one record for a given key. Optimally this would allow
 
1736
            # re-keying, but its simpler to just output that as a delete+add
 
1737
            # to spend less time calculating the delta.
 
1738
            delta_list = []
 
1739
            for key, (old_key, value) in parent_id_basename_delta.iteritems():
 
1740
                if value is not None:
 
1741
                    delta_list.append((old_key, key, value))
 
1742
                else:
 
1743
                    delta_list.append((old_key, None, None))
 
1744
            result.parent_id_basename_to_file_id.apply_delta(delta_list)
 
1745
        parents.discard(('', None))
 
1746
        for parent_path, parent in parents:
1683
1747
            try:
1684
1748
                if result[parent].kind != 'directory':
1685
1749
                    raise errors.InconsistentDelta(result.id2path(parent), parent,
1687
1751
            except errors.NoSuchId:
1688
1752
                raise errors.InconsistentDelta("<unknown>", parent,
1689
1753
                    "Parent is not present in resulting inventory.")
 
1754
            if result.path2id(parent_path) != parent:
 
1755
                raise errors.InconsistentDelta(parent_path, parent,
 
1756
                    "Parent has wrong path %r." % result.path2id(parent_path))
1690
1757
        return result
1691
1758
 
1692
1759
    @classmethod
1951
2018
 
1952
2019
    def path2id(self, name):
1953
2020
        """See CommonInventory.path2id()."""
 
2021
        # TODO: perhaps support negative hits?
1954
2022
        result = self._path_to_fileid_cache.get(name, None)
1955
 
        if result is None:
1956
 
            result = CommonInventory.path2id(self, name)
1957
 
            self._path_to_fileid_cache[name] = result
1958
 
        return result
 
2023
        if result is not None:
 
2024
            return result
 
2025
        if isinstance(name, basestring):
 
2026
            names = osutils.splitpath(name)
 
2027
        else:
 
2028
            names = name
 
2029
        current_id = self.root_id
 
2030
        if current_id is None:
 
2031
            return None
 
2032
        parent_id_index = self.parent_id_basename_to_file_id
 
2033
        for basename in names:
 
2034
            # TODO: Cache each path we figure out in this function.
 
2035
            basename_utf8 = basename.encode('utf8')
 
2036
            key_filter = [(current_id, basename_utf8)]
 
2037
            file_id = None
 
2038
            for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
 
2039
                key_filter=key_filter):
 
2040
                if parent_id != current_id or name_utf8 != basename_utf8:
 
2041
                    raise errors.BzrError("corrupt inventory lookup! "
 
2042
                        "%r %r %r %r" % (parent_id, current_id, name_utf8,
 
2043
                        basename_utf8))
 
2044
            if file_id is None:
 
2045
                return None
 
2046
            current_id = file_id
 
2047
        self._path_to_fileid_cache[name] = current_id
 
2048
        return current_id
1959
2049
 
1960
2050
    def to_lines(self):
1961
2051
        """Serialise the inventory to lines."""
2144
2234
        yield item
2145
2235
 
2146
2236
 
 
2237
def _check_delta_ids_are_valid(delta):
 
2238
    """Decorate a delta and check that the ids in it are valid.
 
2239
 
 
2240
    :return: A generator over delta.
 
2241
    """
 
2242
    for item in delta:
 
2243
        entry = item[3]
 
2244
        if item[2] is None:
 
2245
            raise errors.InconsistentDelta(item[0] or item[1], item[2],
 
2246
                "entry with file_id None %r" % entry)
 
2247
        if type(item[2]) != str:
 
2248
            raise errors.InconsistentDelta(item[0] or item[1], item[2],
 
2249
                "entry with non bytes file_id %r" % entry)
 
2250
        yield item
 
2251
 
 
2252
 
2147
2253
def _check_delta_ids_match_entry(delta):
2148
2254
    """Decorate a delta and check that the ids in it match the entry.file_id.
2149
2255
 
2156
2262
                raise errors.InconsistentDelta(item[0] or item[1], item[2],
2157
2263
                    "mismatched id with %r" % entry)
2158
2264
        yield item
 
2265
 
 
2266
 
 
2267
def _check_delta_new_path_entry_both_or_None(delta):
 
2268
    """Decorate a delta and check that the new_path and entry are paired.
 
2269
 
 
2270
    :return: A generator over delta.
 
2271
    """
 
2272
    for item in delta:
 
2273
        new_path = item[1]
 
2274
        entry = item[3]
 
2275
        if new_path is None and entry is not None:
 
2276
            raise errors.InconsistentDelta(item[0], item[1],
 
2277
                "Entry with no new_path")
 
2278
        if new_path is not None and entry is None:
 
2279
            raise errors.InconsistentDelta(new_path, item[1],
 
2280
                "new_path with no entry")
 
2281
        yield item