Rev 4477: Documented version of John's first proposal, with test showing that it is incomplete. in http://people.ubuntu.com/~robertc/baz2.0/pending/bug-390563
Robert Collins
robertc at robertcollins.net
Thu Jun 25 10:35:00 BST 2009
At http://people.ubuntu.com/~robertc/baz2.0/pending/bug-390563
------------------------------------------------------------
revno: 4477
revision-id: robertc at robertcollins.net-20090625093429-llak4vj4q5nlqt2e
parent: pqm at pqm.ubuntu.com-20090624225712-x20543g8bpv6e9ny
committer: Robert Collins <robertc at robertcollins.net>
branch nick: bug-390563
timestamp: Thu 2009-06-25 19:34:29 +1000
message:
Documented version of John's first proposal, with test showing that it is incomplete.
=== modified file 'bzrlib/chk_map.py'
--- a/bzrlib/chk_map.py 2009-06-17 19:10:35 +0000
+++ b/bzrlib/chk_map.py 2009-06-25 09:34:29 +0000
@@ -1404,6 +1404,7 @@
chks_to_read = uninteresting_keys.union(interesting_keys)
next_uninteresting = set()
next_interesting = set()
+ next_interesting_intersection = None
uninteresting_items = set()
interesting_items = set()
interesting_to_yield = []
@@ -1425,11 +1426,17 @@
else:
interesting_to_yield.append(record.key)
if type(node) is InternalNode:
+ if next_interesting_intersection is None:
+ next_interesting_intersection = set(node.refs())
+ else:
+ next_interesting_intersection = \
+ next_interesting_intersection.intersection(node.refs())
next_interesting.update(node.refs())
else:
interesting_items.update(node.iteritems(None))
return (next_uninteresting, uninteresting_items,
- next_interesting, interesting_to_yield, interesting_items)
+ next_interesting, interesting_to_yield, interesting_items,
+ next_interesting_intersection)
def _find_all_uninteresting(store, interesting_root_keys,
@@ -1450,16 +1457,21 @@
# uninteresting set
(uninteresting_keys, uninteresting_items,
interesting_keys, interesting_to_yield,
- interesting_items) = _find_children_info(store, interesting_root_keys,
+ interesting_items, interesting_intersection,
+ ) = _find_children_info(store, interesting_root_keys,
uninteresting_root_keys,
pb=pb)
all_uninteresting_chks.update(uninteresting_keys)
all_uninteresting_items.update(uninteresting_items)
del uninteresting_items
- # Note: Exact matches between interesting and uninteresting do not need
- # to be search further. Non-exact matches need to be searched in case
- # there is a future exact-match
- uninteresting_keys.difference_update(interesting_keys)
+ # Do not examine in detail pages common to all interesting trees.
+ # Pages that are common to all interesting trees will have their
+ # older versions found via the uninteresting tree traversal. Some pages
+ # found via the interesting trees traversal will be uninteresting for
+ # other of the interesting trees, which is why we require the pages to be
+ # common for us to trim them.
+ if interesting_intersection is not None:
+ uninteresting_keys.difference_update(interesting_intersection)
# Second, find the full set of uninteresting bits reachable by the
# uninteresting roots
=== modified file 'bzrlib/tests/test_chk_map.py'
--- a/bzrlib/tests/test_chk_map.py 2009-06-17 18:23:59 +0000
+++ b/bzrlib/tests/test_chk_map.py 2009-06-25 09:34:29 +0000
@@ -2118,3 +2118,69 @@
(aac_key, [(('aac',), 'target1')]),
(bba_key, [(('bba',), 'target2')]),
], [target1, target2], [basis1, basis2])
+
+ def test_multiple_maps_overlapping_common_new(self):
+ # Test that when a node found through the interesting_keys iteration
+ # for *some roots* and also via the uninteresting keys iteration, that
+ # it is still scanned for uninteresting refs and items, because its
+ # not truely new. This requires 2 levels of InternalNodes to expose,
+ # because of the way the bootstrap in _find_children_info works.
+ # This suggests that the code is probably amenable to/benefit from
+ # consolidation.
+ # How does this test work?
+ # 1) We need a second level InternalNode present in a basis tree.
+ # 2) We need a left side new tree that uses that InternalNode
+ # 3) We need a right side new tree that does not use that InternalNode
+ # at all but that has an unchanged *value* that was reachable inside
+ # that InternalNode
+ basis = self.get_map_key({
+ # InternalNode, unchanged in left:
+ ('aaa',): 'left',
+ ('abb',): 'right',
+ # Forces an internalNode at 'a'
+ ('ccc',): 'common',
+ })
+ left = self.get_map_key({
+ # All of basis unchanged
+ ('aaa',): 'left',
+ ('abb',): 'right',
+ ('ccc',): 'common',
+ # And a new top level node so the root key is different
+ ('ddd',): 'change',
+ })
+ right = self.get_map_key({
+ # A value that is unchanged from basis and thus should be filtered
+ # out.
+ ('abb',): 'right'
+ })
+ basis_map = CHKMap(self.get_chk_bytes(), basis)
+ basis_map._dump_tree()
+ # Get left expected data
+ left_map = CHKMap(self.get_chk_bytes(), left)
+ self.assertEqualDiff(
+ "'' InternalNode\n"
+ " 'a' InternalNode\n"
+ " 'aa' LeafNode\n"
+ " ('aaa',) 'left'\n"
+ " 'ab' LeafNode\n"
+ " ('abb',) 'right'\n"
+ " 'c' LeafNode\n"
+ " ('ccc',) 'common'\n"
+ " 'd' LeafNode\n"
+ " ('ddd',) 'change'\n",
+ left_map._dump_tree())
+ # Keys from left side target
+ l_d_key = left_map._root_node._items['d'].key()
+ # Get right expected data
+ right_map = CHKMap(self.get_chk_bytes(), right)
+ self.assertEqualDiff(
+ "'' LeafNode\n"
+ " ('abb',) 'right'\n",
+ right_map._dump_tree())
+ # Keys from the right side target - none, the root is enough.
+ # Test behaviour
+ self.assertIterInteresting(
+ [(left, []),
+ (right, []),
+ (l_d_key, [(('ddd',), 'change')]),
+ ], [left, right], [basis])
More information about the bazaar-commits
mailing list