Rev 3478: (broken) start working on some ideas for generating dotted revnos without searching the whole graph. in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno

------------------------------------------------------------
revno: 3478
revision-id: john at arbash-meinel.com-20080606131011-xv0frx6tepflevrw
parent: pqm at pqm.ubuntu.com-20080605191237-2306x0goo9pfh9to
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: lazy_revno
timestamp: Fri 2008-06-06 08:10:11 -0500
message:
  (broken) start working on some ideas for generating dotted revnos without searching the whole graph.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2008-05-29 20:17:37 +0000
+++ b/bzrlib/graph.py	2008-06-06 13:10:11 +0000
@@ -1397,3 +1397,90 @@
         """
         return self._keys
 
+
+class LazyRevnoMapper(object):
+    """Compute dotted revnos without walking the whole graph.
+    
+    :ivar _parent_provider: An object that implements .get_parent_map()
+    :ivar _distance_to_null: Map revision_id => known distance to null (aka
+        revno if this is in the mainline.)
+        Currently not used, this could be useful as it would be preserved
+        different tip_revision_ids.
+    :ivar _revno: Map revision_id => known revno, mainline revisions will be
+        a simple integer, others will be a 3-integer tuple
+    :ivar _known_children: revision_id => children we have encountered
+    :ivar _tip_revision_id: Dotted revnos are calculated relative to this
+        revision_id.
+    :ivar _merged_into_at_least: Map revision_id => the first mainline revno we
+        know of that has this revision in its ancestry.
+    :ivar _cur_mainline_tip: (revno, revision_id) tuple which indicates how far
+        we have walked along the mailine.
+    """
+
+    def __init__(self, parent_provider, tip_revision_id, tip_revno):
+        assert isinstance(tip_revno, int)
+        self._parent_provider = parent_provider
+        self.get_parent_map = self._parent_provider.get_parent_map
+        self._tip_revision_id = tip_revision_id
+        # self._distance_to_null = {tip_revision_id:tip_revno}
+        self._revno = {tip_revision_id:tip_revno}
+        self._merged_into_at_least = {tip_revision_id:tip_revno}
+        self._known_children = {}
+
+        self._cur_mainline_revno = tip_revno
+        self._cur_mainline_tip = tip_revision_id
+
+    def get_dotted_revno(self, revision_id):
+        """Compute the dotted revno for revision_id
+
+        :param revision_id: The revision id we are curious about.
+        :return: The revno for the given revision. Either a simple integer, or
+            a 3-integer tuple.
+        """
+        if revision_id in self._revno:
+            return self._revno[revision_id]
+
+    def _update_known_children(self, parent_map):
+        for revision_id, parent_ids in parent_map.iteritems():
+            for p_id in parent_ids:
+                self._known_children.setdefault(p_id, set()).add(revision_id)
+
+    def _find_boundary_revisions(self, revision_id):
+        """Walk backwards until we find the mainline revision we descend from.
+
+        This walks the left-hand parent of both the mainline and the
+        revision_id until we find the point at which they converge, reach
+        NULL_REVISION, or a ghost.
+        """
+        next_parent_request = set()
+        # Have we finished walking the mainline?
+        if self._cur_mainline_tip is not None:
+            next_parent_request.add(self._cur_mainline_tip)
+        next_parent_request.add(revision_id)
+
+        cur_revision_ancestor_id = revision_id
+        while cur_revision_ancestor_id is not None and next_parent_request:
+            if cur_revision_ancestor_id in self._revno:
+                # We know the revno for this revision, is it on the mainline?
+                revno = self._revno[cur_revision_ancestor_id]
+                if isinstance(revno, int): # Mainline, we are done
+                    pass # XXX: ???
+            parent_map = self.get_parent_map(next_parent_request)
+            self._update_known_children(parent_map)
+
+            # Step the mainline searcher
+            if self._cur_mainline_tip is not None:
+                # TODO: handle ghosts here
+                next_mainline_parents = parent_map[self._cur_mainline_tip]
+                next_mainline_tip = next_mainline_parents[0]
+                revno = self._cur_mainline_revno - 1
+                self._cur_mainline_tip = next_mainline_tip
+                self._cur_mainline_revno = revno
+                self._merged_into_at_least[next_mainline_tip] = revno
+                self._revno[next_mainline_tip] = revno
+
+            # XXX: handle ghosts
+            cur_parent_ids = parent_map[cur_revision_ancestor_id]
+            for p_id in cur_parent_ids:
+                self._known_children.setdefault(p_id,
+                    set()).add(cur_revision_ancestor_id)

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2008-05-29 20:17:37 +0000
+++ b/bzrlib/tests/test_graph.py	2008-06-06 13:10:11 +0000
@@ -1354,3 +1354,20 @@
         # Use sorted because we don't care about the order, just that each is
         # only present 1 time.
         self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
+
+
+class TestLazyRevnoMapper(TestGraphBase):
+
+    def make_mapper(self, ancestors, tip):
+        graph = self.make_graph(ancestors)
+        tip_revno = graph.find_distance_to_null(tip, [])
+        return _mod_graph.LazyRevnoMapper(graph, tip, tip_revno)
+
+    def test_init(self):
+        mapper = self.make_mapper(ancestry_1, 'rev4')
+        self.assertEqual(4, mapper._distance_to_null['rev4'])
+        self.assertEqual(4, mapper._dotted_revno['rev4'])
+
+    def test_tip_revision(self):
+        mapper = self.make_mapper(ancestry_1, 'rev4')
+        self.assertEqual(4, mapper.get_dotted_revno('rev4'))