Rev 4419: Clean out some asserts, get rid of the 'dominator_distance' field which isn't used anyway. in http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads
John Arbash Meinel
john at arbash-meinel.com
Tue Jun 16 16:35:18 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads
------------------------------------------------------------
revno: 4419
revision-id: john at arbash-meinel.com-20090616153514-2croj2d8ych1sk71
parent: john at arbash-meinel.com-20090616142731-a385wy2gmp1i0oih
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Tue 2009-06-16 10:35:14 -0500
message:
Clean out some asserts, get rid of the 'dominator_distance' field which isn't used anyway.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py 2009-06-15 17:00:30 +0000
+++ b/bzrlib/_known_graph_py.py 2009-06-16 15:35:14 +0000
@@ -28,7 +28,7 @@
"""Represents a single object in the known graph."""
__slots__ = ('key', 'parent_keys', 'child_keys', 'linear_dominator',
- 'dominator_distance', 'gdfo', 'ancestor_of')
+ 'gdfo', 'ancestor_of')
def __init__(self, key, parent_keys):
self.key = key
@@ -37,7 +37,6 @@
# oldest ancestor, such that no parents between here and there have >1
# child or >1 parent.
self.linear_dominator = None
- self.dominator_distance = 0
# Greatest distance from origin
self.gdfo = None
# This will become a tuple of known heads that have this node as an
@@ -45,10 +44,10 @@
self.ancestor_of = None
def __repr__(self):
- return '%s(%s gdfo:%s par:%s child:%s dom:%s %s)' % (
+ return '%s(%s gdfo:%s par:%s child:%s %s)' % (
self.__class__.__name__, self.key, self.gdfo,
self.parent_keys, self.child_keys,
- self.linear_dominator, self.dominator_distance)
+ self.linear_dominator)
class KnownGraph(object):
@@ -78,7 +77,6 @@
for key, parent_keys in parent_map.iteritems():
if key in nodes:
node = nodes[key]
- assert node.parent_keys is None
node.parent_keys = parent_keys
else:
node = _KnownGraphNode(key, parent_keys)
@@ -112,19 +110,16 @@
# This node is either a ghost, a tail, or has multiple parents
# It its own dominator
node.linear_dominator = node.key
- node.dominator_distance = 0
return None
parent_node = self._nodes[node.parent_keys[0]]
if len(parent_node.child_keys) > 1:
# The parent has multiple children, so *this* node is the
# dominator
node.linear_dominator = node.key
- node.dominator_distance = 0
return None
# The parent is already filled in, so add and continue
if parent_node.linear_dominator is not None:
node.linear_dominator = parent_node.linear_dominator
- node.dominator_distance = parent_node.dominator_distance + 1
return None
# We don't know this node, or its parent node, so start walking to
# next
@@ -145,12 +140,10 @@
next_node = check_node(node)
# The stack now contains the linear chain, and 'node' should have
# been labeled
- assert node.linear_dominator is not None
dominator = node.linear_dominator
while stack:
next_node = stack.pop()
next_node.linear_dominator = dominator
- next_node.dominator_distance = node.dominator_distance + 1
node = next_node
def _find_gdfo(self):
@@ -166,7 +159,6 @@
node.gdfo = 1
heappush(todo, (1, node))
processed = 0
- max_gdfo = len(self._nodes) + 1
while todo:
gdfo, next = heappop(todo)
processed += 1
@@ -174,10 +166,8 @@
# This node was reached from a longer path, we assume it was
# enqued correctly with the longer gdfo, so don't continue
# processing now
- assert gdfo < next.gdfo
continue
next_gdfo = gdfo + 1
- assert next_gdfo <= max_gdfo
for child_key in next.child_keys:
child_node = nodes[child_key]
if child_node.gdfo is None or child_node.gdfo < next_gdfo:
@@ -208,7 +198,6 @@
other_node = dom_to_node[node.linear_dominator]
# There should be no way that nodes sharing a dominator could
# 'tie' for gdfo
- assert other_node.gdfo != node.gdfo
if other_node.gdfo > node.gdfo:
# The other node has this node as an ancestor
keys_to_remove.append(node.key)
@@ -282,7 +271,6 @@
to_cleanup = []
to_cleanup_append = to_cleanup.append
for node in candidate_nodes.itervalues():
- assert node.ancestor_of is None
node.ancestor_of = (node.key,)
queue.append((-node.gdfo, node))
to_cleanup_append(node)
@@ -296,7 +284,6 @@
heappush = heapq.heappush
while queue and len(candidate_nodes) > 1:
_, node = heappop(queue)
- # assert node.ancestor_of is not None
next_ancestor_of = node.ancestor_of
if len(next_ancestor_of) == num_candidates:
# This node is now considered 'common'
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx 2009-06-16 14:27:31 +0000
+++ b/bzrlib/_known_graph_pyx.pyx 2009-06-16 15:35:14 +0000
@@ -61,7 +61,6 @@
cdef object parents
cdef object children
cdef _KnownGraphNode linear_dominator_node
- cdef public long dominator_distance
cdef public object gdfo # Int
# This could also be simplified
cdef object ancestor_of
@@ -76,7 +75,6 @@
# oldest ancestor, such that no parents between here and there have >1
# child or >1 parent.
self.linear_dominator_node = None
- self.dominator_distance = 0
# Greatest distance from origin
self.gdfo = -1
# This will become a tuple of known heads that have this node as an
@@ -115,10 +113,10 @@
if self.children is not None:
for node in self.children:
child_keys.append(node.key)
- return '%s(%s gdfo:%s par:%s child:%s dom:%s %s)' % (
+ return '%s(%s gdfo:%s par:%s child:%s %s)' % (
self.__class__.__name__, self.key, self.gdfo,
parent_keys, child_keys,
- self.linear_dominator, self.dominator_distance)
+ self.linear_dominator)
cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
@@ -215,7 +213,6 @@
key = <object>temp_key
parent_keys = <object>temp_parent_keys
node = self._get_or_create_node(key)
- assert node.parents is None
# We know how many parents, so we could pre allocate an exact sized
# tuple here
num_parent_keys = len(parent_keys)
@@ -237,19 +234,16 @@
# This node is either a ghost, a tail, or has multiple parents
# It its own dominator
node.linear_dominator_node = node
- node.dominator_distance = 0
return None
parent_node = _get_parent(node.parents, 0)
if PyList_GET_SIZE(parent_node.children) > 1:
# The parent has multiple children, so *this* node is the
# dominator
node.linear_dominator_node = node
- node.dominator_distance = 0
return None
# The parent is already filled in, so add and continue
if parent_node.linear_dominator_node is not None:
node.linear_dominator_node = parent_node.linear_dominator_node
- node.dominator_distance = parent_node.dominator_distance + 1
return None
# We don't know this node, or its parent node, so start walking to
# next
@@ -294,13 +288,11 @@
next_node = self._check_is_linear(node)
# The stack now contains the linear chain, and 'node' should have
# been labeled
- assert node.linear_dominator_node is not None
dominator = node.linear_dominator_node
num_elements = len(stack)
for i from num_elements > i >= 0:
next_node = _get_list_node(stack, i)
next_node.linear_dominator_node = dominator
- next_node.dominator_distance = node.dominator_distance + 1
node = next_node
cdef object _find_tails(self):
@@ -331,18 +323,15 @@
node.gdfo = 1
PyList_Append(todo, (1, node))
# No need to heapify, because all tails have priority=1
- max_gdfo = len(self._nodes) + 1
while PyList_GET_SIZE(todo) > 0:
node = _peek_node(todo)
next_gdfo = node.gdfo + 1
- assert next_gdfo <= max_gdfo
replace_node = 1
for pos from 0 <= pos < PyList_GET_SIZE(node.children):
child_node = _get_list_node(node.children, pos)
# We should never have numbered children before we numbered
# a parent
if child_node.gdfo != -1:
- assert child_node.gdfo >= next_gdfo
continue
# Only enque children when all of their parents have been
# resolved. With a single parent, we can just take 'this' value
@@ -561,7 +550,6 @@
pos = 0
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
node = <_KnownGraphNode>temp_node
- assert node.ancestor_of is None
node.ancestor_of = (node.key,)
PyList_Append(queue, (-node.gdfo, node))
PyList_Append(self._to_cleanup, node)
=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py 2009-06-12 19:37:30 +0000
+++ b/bzrlib/tests/test__known_graph.py 2009-06-16 15:35:14 +0000
@@ -71,10 +71,9 @@
def make_known_graph(self, ancestry):
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
- def assertDominator(self, graph, rev, dominator, distance):
+ def assertDominator(self, graph, rev, dominator):
node = graph._nodes[rev]
self.assertEqual(dominator, node.linear_dominator)
- self.assertEqual(distance, node.dominator_distance)
def assertGDFO(self, graph, rev, gdfo):
node = graph._nodes[rev]
@@ -91,26 +90,26 @@
def test_dominators_ancestry_1(self):
graph = self.make_known_graph(test_graph.ancestry_1)
- self.assertDominator(graph, 'rev1', NULL_REVISION, 1)
- self.assertDominator(graph, 'rev2b', 'rev2b', 0)
- self.assertDominator(graph, 'rev2a', 'rev2a', 0)
- self.assertDominator(graph, 'rev3', 'rev2a', 1)
- self.assertDominator(graph, 'rev4', 'rev4', 0)
+ self.assertDominator(graph, 'rev1', NULL_REVISION)
+ self.assertDominator(graph, 'rev2b', 'rev2b')
+ self.assertDominator(graph, 'rev2a', 'rev2a')
+ self.assertDominator(graph, 'rev3', 'rev2a')
+ self.assertDominator(graph, 'rev4', 'rev4')
def test_dominators_feature_branch(self):
graph = self.make_known_graph(test_graph.feature_branch)
- self.assertDominator(graph, 'rev1', NULL_REVISION, 1)
- self.assertDominator(graph, 'rev2b', NULL_REVISION, 2)
- self.assertDominator(graph, 'rev3b', NULL_REVISION, 3)
+ self.assertDominator(graph, 'rev1', NULL_REVISION)
+ self.assertDominator(graph, 'rev2b', NULL_REVISION)
+ self.assertDominator(graph, 'rev3b', NULL_REVISION)
def test_dominators_extended_history_shortcut(self):
graph = self.make_known_graph(test_graph.extended_history_shortcut)
- self.assertDominator(graph, 'a', NULL_REVISION, 1)
- self.assertDominator(graph, 'b', 'b', 0)
- self.assertDominator(graph, 'c', 'b', 1)
- self.assertDominator(graph, 'd', 'b', 2)
- self.assertDominator(graph, 'e', 'e', 0)
- self.assertDominator(graph, 'f', 'f', 0)
+ self.assertDominator(graph, 'a', NULL_REVISION)
+ self.assertDominator(graph, 'b', 'b')
+ self.assertDominator(graph, 'c', 'b')
+ self.assertDominator(graph, 'd', 'b')
+ self.assertDominator(graph, 'e', 'e')
+ self.assertDominator(graph, 'f', 'f')
def test_gdfo_ancestry_1(self):
graph = self.make_known_graph(test_graph.ancestry_1)
More information about the bazaar-commits
mailing list