Rev 4412: Add a bit of discussion about why we would want to use linear dominators. in http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.16-better_heads

------------------------------------------------------------
revno: 4412
revision-id: john at arbash-meinel.com-20090615170030-p3am5qp19pstlu9x
parent: john at arbash-meinel.com-20090612202108-blsyks1kdxod0lsk
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.16-better_heads
timestamp: Mon 2009-06-15 12:00:30 -0500
message:
  Add a bit of discussion about why we would want to use linear dominators.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-06-12 20:21:08 +0000
+++ b/bzrlib/_known_graph_py.py	2009-06-15 17:00:30 +0000
@@ -97,8 +97,15 @@
         For any given node, the 'linear dominator' is an ancestor, such that
         all parents between this node and that one have a single parent, and a
         single child. So if A->B->C->D then B,C,D all have a linear dominator
-        of A. Because there are no interesting siblings, we can quickly skip to
-        the nearest dominator when doing comparisons.
+        of A.
+
+        There are two main benefits:
+        1) When walking the graph, we can jump to the nearest linear dominator,
+           rather than walking all of the nodes inbetween.
+        2) When caching heads() results, dominators give the "same" results as
+           their children. (If the dominator is a head, then the descendant is
+           a head, if the dominator is not a head, then the child isn't
+           either.)
         """
         def check_node(node):
             if node.parent_keys is None or len(node.parent_keys) != 1:

=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-12 20:21:08 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-15 17:00:30 +0000
@@ -257,13 +257,19 @@
         return parent_node
 
     def _find_linear_dominators(self):
-        """For each node in the set, find any linear dominators.
-
+        """
         For any given node, the 'linear dominator' is an ancestor, such that
         all parents between this node and that one have a single parent, and a
         single child. So if A->B->C->D then B,C,D all have a linear dominator
-        of A. Because there are no interesting siblings, we can quickly skip to
-        the nearest dominator when doing comparisons.
+        of A.
+
+        There are two main benefits:
+        1) When walking the graph, we can jump to the nearest linear dominator,
+           rather than walking all of the nodes inbetween.
+        2) When caching heads() results, dominators give the "same" results as
+           their children. (If the dominator is a head, then the descendant is
+           a head, if the dominator is not a head, then the child isn't
+           either.)
         """
         cdef PyObject *temp_node
         cdef Py_ssize_t pos