Rev 1: Writing a simple plugin for finding the mainline which merged a revision. in http://bzr.arbash-meinel.com/plugins/find_mainline_rev

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 1
revision-id:john at arbash-meinel.com-20071101191856-nq75rlbq0nwzm1tr
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: find_mainline_rev
timestamp: Thu 2007-11-01 14:18:56 -0500
message:
  Writing a simple plugin for finding the mainline which merged a revision.
  But it looks to be even simpler than I thought.
added:
  __init__.py                    __init__.py-20071101191826-bpibqad1s9oeqw1d-1
-------------- next part --------------
=== added file '__init__.py'
--- a/__init__.py	1970-01-01 00:00:00 +0000
+++ b/__init__.py	2007-11-01 19:18:56 +0000
@@ -0,0 +1,120 @@
+# Copyright (C) 2007 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+"""Find the mainline revision which merged a given revision."""
+
+from bzrlib import (
+    branch,
+    commands,
+    option,
+    trace,
+    tsort,
+    )
+
+
+def _find_mainline_rev(a_branch, revision_id):
+    """Find the mainline revision which merged this revision_id."""
+    tip_revision_id = a_branch.last_revision()
+    rev_graph = a_branch.repository.get_revision_graph(tip_revision_id)
+    if revision_id not in rev_graph:
+        return None
+    topo_sorted = tsort.merge_sort(
+        [(node, parents) for node, parents in rev_graph.iteritems()],
+        tip_revision_id, generate_revno=True)
+
+    node_offset = {}
+    nodes = []
+    target_node_offset = None
+
+    # We've checked these nodes already
+    # not_in_ancestry_of = set()
+
+    def _check_in_ancestry(mainline_rev_id):
+        found = False
+        nodes_to_check = [mainline_rev_id]
+        checked_nodes = set()
+
+        while nodes_to_check:
+            node = nodes_to_check.pop()
+            checked_nodes.add(node)
+            for parent in rev_graph[node]:
+                # if parent in not_in_ancestry_of:
+                #     # We've checked this one in the past
+                #     continue
+                if (parent not in node_offset
+                    or node_offset[parent] > target_node_offset):
+                    # This parent is too old
+                    continue
+                if parent == revision_id:
+                    # Found it
+                    return True
+                nodes_to_check.append(parent)
+        # if we have gotten this far, then the node is not in the ancestry of
+        # any of the nodes we checked
+        # not_in_ancestry_of.update(checked_nodes)
+        return False
+
+    # topo_sorted starts from the tip and works backwards
+    # this will be the list of all mainline revisions that happen after the
+    # merged revision.
+    mainline_revs = []
+    for num, rev_id, depth, dotted_revno, eo_merge in topo_sorted:
+        node_offset[rev_id] = num
+        if rev_id == revision_id:
+            target_node_offset = num
+            print 'found node at %d' % (num,)
+            if depth == 0:
+                return revision_id
+            break
+        elif depth == 0:
+            mainline_revs.append(rev_id)
+
+    for main_rev_id in reversed(mainline_revs):
+        # We have a mainline node, check if the desired node is in the
+        # ancestry.
+        if _check_in_ancestry(main_rev_id):
+            return main_rev_id
+        assert 'it should have been the last one'
+    trace.warning("somehow we didn't find it in the ancestry,"
+                  " even though get_revision_graph said it was.")
+    import pdb; pdb.set_trace()
+    return None
+
+
+class cmd_find_mainline_rev(commands.Command):
+    """Find the mainline revision which merged a given revision."""
+
+    takes_options = ['revision']
+
+    def run(self, revision=None):
+        if revision is None or len(revision) == 0:
+            raise errors.BzrCommandError('You must supply a --revision.')
+        a_branch, relpath = branch.Branch.open_containing('.')
+        a_branch.lock_read()
+        try:
+            revision_id = revision[0].in_history(a_branch).rev_id
+            mainline_revision_id = _find_mainline_rev(a_branch, revision_id)
+        finally:
+            a_branch.unlock()
+        if mainline_revision_id is None:
+            trace.note('Revision not present in ancestry')
+            return 1
+        else:
+            self.outf.write(mainline_revision_id + '\n')
+
+
+commands.register_command(cmd_find_mainline_rev)
+