Rev 2: some typos and other work. in http://bzr.arbash-meinel.com/plugins/test_graph

John Arbash Meinel john at arbash-meinel.com
Mon Dec 10 21:01:10 GMT 2007


At http://bzr.arbash-meinel.com/plugins/test_graph

------------------------------------------------------------
revno: 2
revision-id:john at arbash-meinel.com-20071210210105-afwkl4a38ikmbtzr
parent: john at arbash-meinel.com-20071210194759-ii8q80gow8690x99
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: test_graph
timestamp: Mon 2007-12-10 15:01:05 -0600
message:
  some typos and other work.
modified:
  graph_testing.py               graph_testing.py-20071210194758-1pwa1q7e3wnjf418-2
-------------- next part --------------
=== modified file 'graph_testing.py'
--- a/graph_testing.py	2007-12-10 19:47:59 +0000
+++ b/graph_testing.py	2007-12-10 21:01:05 +0000
@@ -16,6 +16,8 @@
 
 """Basic functions for testing graph operations."""
 
+import time
+
 from bzrlib import (
     branch,
     errors,
@@ -23,16 +25,19 @@
     )
 
 
-
 class GraphTester(object):
 
     def __init__(self, rev_graph):
         self.rev_graph = rev_graph
         self.head_times = {}
+        self.trivial_head_times = {}
         self.find_difference_times = {}
+        self.trivial_diff_times = {}
         self.hold_graph = False
+        self.invalid_heads = set()
+        self.invalid_diffs = set()
 
-    def get_interesting_nodes(self):
+    def get_interesting_nodes(self, last_revision):
         """Go through the revision graph, and look for interesting nodes.
 
         Currently that is just defined as nodes which have more than one parent.
@@ -40,7 +45,8 @@
         comes first.)
         """
         interesting = []
-        for seq_num, revision_id, depth, eom in tsort.merge_sort(self.rev_graph):
+        for seq_num, revision_id, depth, eom in tsort.merge_sort(self.rev_graph,
+                                                                 last_revision):
             parent_ids = self.rev_graph[revision_id]
             if len(parent_ids) > 1:
                 interesting.append(revision_id)
@@ -51,26 +57,28 @@
         ancestries = {}
         # We go in reverse order, so that we will tend to find the ancestries in
         # the map
-        for revision_id in reversed(self.interesting):
-            ancestry = set([revision_id])
-            needed = set([revision_id])
-            while needed:
-                next = needed.pop()
-                parent_ids = self.rev_graph[next]
-                ancestry.update(parent_ids)
-                for parent_id in parent_ids:
-                    if parent_id in ancestries:
-                        ancestry.update(ancestries[parent_id])
-                    else: # We need to probe in this direction
-                        needed.add(parent_id)
-            ancestries[revision_id] = ancestry
+        for interesting_id in reversed(self.interesting):
+            needed_ids = list(self.rev_graph[interesting_id]) + [interesting_id]
+            for revision_id in needed_ids:
+                ancestry = set([revision_id])
+                needed = set([revision_id])
+                while needed:
+                    next = needed.pop()
+                    parent_ids = self.rev_graph[next]
+                    ancestry.update(parent_ids)
+                    for parent_id in parent_ids:
+                        if parent_id in ancestries:
+                            ancestry.update(ancestries[parent_id])
+                        else: # We need to probe in this direction
+                            needed.add(parent_id)
+                ancestries[revision_id] = ancestry
         self.ancestries = ancestries
 
     def time_functions(self, a_branch):
         if self.hold_graph:
             graph = a_branch.repository.get_graph()
 
-        for revision_id in reversed(interesting):
+        for revision_id in reversed(self.interesting):
             parent_ids = self.rev_graph[revision_id]
             a_branch.lock_read()
             try:
@@ -82,17 +90,53 @@
             finally:
                 a_branch.unlock()
             self.head_times[revision_id] = t_heads
-            if heads != set(parent_ids):
-                print 'heads() mismatch for: %s' % (revision_id,)
+            parent_id_set = set(parent_ids)
+            if heads != parent_id_set:
+                if heads.issubset(parent_ids):
+                    print 'heads() is subset for: %s' % (revision_id,)
+                else:
+                    print 'heads() mismatch for: %s' % (revision_id,)
+                self.invalid_heads.add(revision_id)
+
+            a_branch.lock_read()
+            try:
+                if not self.hold_graph:
+                    graph = a_branch.repository.get_graph()
+                t_start = time.clock()
+                for parent_id in parent_ids:
+                    heads = graph.heads((revision_id, parent_id))
+                    assert heads == set([revision_id])
+                t_trivial_heads = time.clock() - t_start
+            finally:
+                a_branch.unlock()
+            self.trivial_head_times[revision_id] = t_heads
+
+            a_branch.lock_read()
+            try:
+                if not self.hold_graph:
+                    graph = a_branch.repository.get_graph()
+                t_start = time.clock()
+                for parent_id in parent_ids:
+                    left, right = graph.find_difference(revision_id, parent_id)
+                    if right != set():
+                        print 'found unmerged nodes for:\n    %s\nand %s' % (
+                            revision_id, parent_id)
+                t_trivial_diff = time.clock() - t_start
+            finally:
+                a_branch.unlock()
+            self.trivial_diff_times[revision_id] = t_trivial_diff
+
             if len(parent_ids) < 2:
                 continue
+
+            a_branch.lock_read()
             try:
                 if not self.hold_graph:
                     graph = a_branch.repository.get_graph()
                 t_start = time.clock()
                 left, right = graph.find_difference(parent_ids[0],
                                                     parent_ids[1])
-                t_diff = t_start - t_start
+                t_diff = time.clock() - t_start
             finally:
                 a_branch.unlock()
             self.find_difference_times[revision_id] = t_diff
@@ -106,6 +150,8 @@
                 print 'left incorrect for: %s' % (revision_id,)
             elif not right_correct:
                 print 'right incorrect for: %s' % (revision_id,)
+            if not left_correct or not right_correct:
+                self.invalid_diffs.add(revision_id)
 
     def get_statistics(self, times):
         min_time = None
@@ -126,6 +172,7 @@
                 'min_time':min_time,
                 'min_rev':min_rev,
                 'max_time':max_time,
+                'max_rev':max_rev,
                 'avg_time':avg_time,
                 'total_time':total_time,
                 }
@@ -134,19 +181,26 @@
 def test_all(location):
     the_branch = branch.Branch.open(location)
     the_branch.lock_read()
+    the_branch.lock_read()
     try:
-        rev_graph = the_branch.repository.get_revision_graph(
-                        the_branch.last_revision())
+        last_revision = the_branch.last_revision()
+        rev_graph = the_branch.repository.get_revision_graph(last_revision)
         rev_id_map = the_branch.get_revision_id_to_revno_map()
     finally:
         the_branch.unlock()
     tester = GraphTester(rev_graph)
-    tester.get_interesting_nodes()
+    tester.hold_graph = True
+    tester.get_interesting_nodes(last_revision)
     tester.get_ancestry_for_interesting()
-    tester.time_functions()
+    tester.time_functions(the_branch)
     import pprint
+    print 'trivial heads:'
+    pprint.pprint(tester.get_statistics(tester.trivial_head_times))
+    print 'trivial diff:'
+    pprint.pprint(tester.get_statistics(tester.trivial_diff_times))
     print 'heads:'
     pprint.pprint(tester.get_statistics(tester.head_times))
     print 'diffs:'
-    pprint.pprint(tester.get_statistics(tester.find_difference_times)
+    pprint.pprint(tester.get_statistics(tester.find_difference_times))
     import pdb; pdb.set_trace()
+    the_branch.unlock()



More information about the bazaar-commits mailing list