Rev 62: Change to using a _MergeSortNode so that it matches KG.merge_sort. in http://bzr.arbash-meinel.com/plugins/history_db
John Arbash Meinel
john at arbash-meinel.com
Wed Apr 7 22:06:51 BST 2010
At http://bzr.arbash-meinel.com/plugins/history_db
------------------------------------------------------------
revno: 62
revision-id: john at arbash-meinel.com-20100407210635-syhdace9q90ib8p4
parent: john at arbash-meinel.com-20100407204932-c16n3focq5d8bpvr
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: history_db
timestamp: Wed 2010-04-07 16:06:35 -0500
message:
Change to using a _MergeSortNode so that it matches KG.merge_sort.
-------------- next part --------------
=== modified file 'history_db.py'
--- a/history_db.py 2010-04-07 20:49:32 +0000
+++ b/history_db.py 2010-04-07 21:06:35 +0000
@@ -423,6 +423,26 @@
self._db_conn.commit()
+class _MergeSortNode(object):
+ """A simple object that represents one entry in the merge sorted graph."""
+
+ __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge',
+ '_left_parent', '_left_pending_parent',
+ '_pending_parents', '_is_first',
+ )
+
+ def __init__(self, key, merge_depth, left_parent, pending_parents,
+ is_first):
+ self.key = key
+ self.merge_depth = merge_depth
+ self.revno = None
+ self.end_of_merge = None
+ self._left_parent = left_parent
+ self._left_pending_parent = left_parent
+ self._pending_parents = pending_parents
+ self._is_first = is_first
+
+
class _IncrementalMergeSort(object):
"""Context for importing partial history."""
# Note: all of the ids in this object are database ids. the revision_ids
@@ -804,20 +824,19 @@
if p not in self._ghosts])
# v- logically probably better as a tuple or object. We currently
# modify it in place, so we use a list
- self._depth_first_stack.append([db_id, merge_depth, left_parent,
- left_parent, pending_parents,
- is_first])
+ self._depth_first_stack.append(
+ _MergeSortNode(db_id, merge_depth, left_parent, pending_parents,
+ is_first))
def _pop_node(self):
"""Move the last node from the _depth_first_stack to _scheduled_stack.
This is the most left-hand node that we are able to find.
"""
- (db_id, merge_depth, left_parent_id, _, _,
- is_first) = self._depth_first_stack.pop()
- if left_parent_id is not None:
- parent_revno = self._imported_dotted_revno[left_parent_id][0]
- if is_first: # We simply number as parent + 1
+ node = self._depth_first_stack.pop()
+ if node._left_parent is not None:
+ parent_revno = self._imported_dotted_revno[node._left_parent][0]
+ if node._is_first: # We simply number as parent + 1
if len(parent_revno) == 1:
mini_revno = parent_revno[0] + 1
revno = (mini_revno,)
@@ -880,20 +899,24 @@
# when we start new numbering, end_of_merge is True. For mainline
# revisions, this is only true when we don't have a parent.
end_of_merge = True
- if left_parent_id is not None and merge_depth == 0:
+ if node._left_parent is not None and node.merge_depth == 0:
end_of_merge = False
else:
- prev_db_id, prev_revno, _, prev_depth = self._scheduled_stack[-1]
- if prev_depth < merge_depth:
+ prev_node = self._scheduled_stack[-1]
+ if prev_node.merge_depth < node.merge_depth:
end_of_merge = True
- elif (prev_depth == merge_depth
- and prev_db_id not in self._parent_map[db_id]):
+ elif (prev_node.merge_depth == node.merge_depth
+ and prev_node.key not in self._parent_map[node.key]):
# Next node is not a direct parent
end_of_merge = True
else:
end_of_merge = False
- self._imported_dotted_revno[db_id] = (revno, end_of_merge, merge_depth)
- self._scheduled_stack.append((db_id, revno, end_of_merge, merge_depth))
+ node.revno = revno
+ node.end_of_merge = end_of_merge
+ self._imported_dotted_revno[node.key] = (revno, end_of_merge,
+ node.merge_depth)
+ node._pending_parents = None
+ self._scheduled_stack.append(node)
def _compute_merge_sort(self):
self._depth_first_stack = []
@@ -903,25 +926,26 @@
while self._depth_first_stack:
last = self._depth_first_stack[-1]
- if last[3] is None and not last[4]:
+ if last._left_pending_parent is None and not last._pending_parents:
# The parents have been processed, pop the node
self._pop_node()
continue
- while last[3] is not None or last[4]:
- if last[3] is not None:
+ while (last._left_pending_parent is not None
+ or last._pending_parents):
+ if last._left_pending_parent is not None:
# Push on the left-hand-parent
- next_db_id = last[3]
- last[3] = None
+ next_db_id = last._left_pending_parent
+ last._left_pending_parent = None
else:
- pending_parents = last[4]
+ pending_parents = last._pending_parents
next_db_id = pending_parents[-1]
- last[4] = pending_parents[:-1]
+ last._pending_parents = pending_parents[:-1]
if next_db_id in self._imported_dotted_revno:
continue
- if next_db_id == last[2]: #Is the left-parent?
- next_merge_depth = last[1]
+ if next_db_id == last._left_parent: #Is the left-parent?
+ next_merge_depth = last.merge_depth
else:
- next_merge_depth = last[1] + 1
+ next_merge_depth = last.merge_depth + 1
self._push_node(next_db_id, next_merge_depth)
# And switch to the outer loop
break
=== modified file 'test_importer.py'
--- a/test_importer.py 2010-04-07 20:49:32 +0000
+++ b/test_importer.py 2010-04-07 21:06:35 +0000
@@ -271,6 +271,12 @@
class Test_IncrementalMergeSort(TestCaseWithGraphs):
+ def assertScheduledStack(self, inc_importer, expected):
+ """Check that the merge_sort result is as expected."""
+ actual = [(node.key, node.revno, node.end_of_merge, node.merge_depth)
+ for node in inc_importer._scheduled_stack]
+ self.assertEqual(expected, actual)
+
def test_step_by_step(self):
b = self.make_interesting_branch()
b._tip_revision = 'G' # Something older
@@ -354,11 +360,12 @@
self.assertEqual({0: 3, (1, 1): 2, (1, 2): 2},
inc_importer._branch_to_child_count)
inc_importer._compute_merge_sort()
- self.assertEqual([(self.H_id, (1, 3, 1), True, 1),
+ self.assertScheduledStack(inc_importer,
+ [(self.H_id, (1, 3, 1), True, 1),
(self.I_id, (4,), False, 0),
(self.J_id, (1, 2, 3), True, 1),
(self.N_id, (5,), False, 0),
- ], inc_importer._scheduled_stack)
+ ])
def test__find_interesting_ancestry(self):
b = self.make_interesting_branch()
@@ -450,11 +457,12 @@
inc_importer = history_db._IncrementalMergeSort(importer, self.O_id)
inc_importer._find_interesting_ancestry()
inc_importer._compute_merge_sort()
- self.assertEqual([(self.K_id, (1, 2, 4), True, 1),
+ self.assertScheduledStack(inc_importer,
+ [(self.K_id, (1, 2, 4), True, 1),
(self.L_id, (1, 4, 1), True, 2),
(self.M_id, (1, 2, 5), False, 1),
(self.O_id, (6,), False, 0),
- ], inc_importer._scheduled_stack)
+ ])
# We have to load G to get E, but we shouldn't have to load D_id, so
# that should be where we stop.
self.assertEqual(self.D_id, inc_importer._imported_mainline_id)
@@ -469,8 +477,7 @@
inc_importer = history_db._IncrementalMergeSort(importer, self.B_id)
inc_importer._find_interesting_ancestry()
inc_importer._compute_merge_sort()
- self.assertEqual([(self.B_id, (2,), False, 0),
- ], inc_importer._scheduled_stack)
+ self.assertScheduledStack(inc_importer, [(self.B_id, (2,), False, 0)])
def test_handles_multi_roots(self):
# Graph:
@@ -497,9 +504,10 @@
self.assertEqual(set([self.E_id, self.F_id]),
inc_importer._interesting_ancestor_ids)
inc_importer._compute_merge_sort()
- self.assertEqual([(self.E_id, (0, 2, 1), True, 1),
+ self.assertScheduledStack(inc_importer,
+ [(self.E_id, (0, 2, 1), True, 1),
(self.F_id, (4,), False, 0),
- ], inc_importer._scheduled_stack)
+ ])
def test_handles_partial_complex_multi_roots(self):
# Graph:
@@ -535,9 +543,10 @@
self.assertEqual(set([self.K_id, self.J_id]),
inc_importer._interesting_ancestor_ids)
inc_importer._compute_merge_sort()
- self.assertEqual([(self.J_id, (0, 3, 1), True, 1),
+ self.assertScheduledStack(inc_importer,
+ [(self.J_id, (0, 3, 1), True, 1),
(self.K_id, (6,), False, 0),
- ], inc_importer._scheduled_stack)
+ ])
# We only have to walk back and stop at D because we have found (0,2,1)
# which must be the latest branch.
self.assertEqual(self.D_id, inc_importer._imported_mainline_id)
@@ -553,8 +562,9 @@
inc_importer = history_db._IncrementalMergeSort(importer, self.A_id)
inc_importer._find_interesting_ancestry()
inc_importer._compute_merge_sort()
- self.assertEqual([(self.A_id, (1,), True, 0),
- ], inc_importer._scheduled_stack)
+ self.assertScheduledStack(inc_importer,
+ [(self.A_id, (1,), True, 0),
+ ])
def test_skips_ghosts(self):
b = self.make_branch_with_ghosts()
@@ -566,9 +576,10 @@
inc_importer._compute_merge_sort()
# G is not mentioned in merge_sorted, neither as a left-hand parent,
# nor as a right-hand parent
- self.assertEqual([(self.A_id, (1,), True, 0),
+ self.assertScheduledStack(inc_importer,
+ [(self.A_id, (1,), True, 0),
(self.B_id, (2,), False, 0),
(self.C_id, (3,), False, 0),
(self.D_id, (0, 1, 1), True, 1),
(self.E_id, (4,), False, 0),
- ], inc_importer._scheduled_stack)
+ ])
More information about the bazaar-commits
mailing list