Rev 3957: Branch.iter_merge_sorted_revisions API (Ian Clatworthy) in file:///home/pqm/archives/thelove/bzr/%2Btrunk/

Canonical.com Patch Queue Manager pqm at pqm.ubuntu.com
Sat Jan 24 04:49:44 GMT 2009


At file:///home/pqm/archives/thelove/bzr/%2Btrunk/

------------------------------------------------------------
revno: 3957
revision-id: pqm at pqm.ubuntu.com-20090124044940-7j90kl1qq22la0rx
parent: pqm at pqm.ubuntu.com-20090123181416-tku4gdtorboy6d0y
parent: ian.clatworthy at canonical.com-20090124040308-m6u33ditaksvwrrq
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Sat 2009-01-24 04:49:40 +0000
message:
  Branch.iter_merge_sorted_revisions API (Ian Clatworthy)
added:
  bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
modified:
  NEWS                           NEWS-20050323055033-4e00b5db738777ff
  bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
  bzrlib/remote.py               remote.py-20060720103555-yeeg2x51vn0rbtdp-1
  bzrlib/tests/branch_implementations/__init__.py __init__.py-20060123013057-b12a52c3f361daf4
    ------------------------------------------------------------
    revno: 3956.1.1
    revision-id: ian.clatworthy at canonical.com-20090124040308-m6u33ditaksvwrrq
    parent: pqm at pqm.ubuntu.com-20090123181416-tku4gdtorboy6d0y
    parent: ian.clatworthy at canonical.com-20090124035735-r7joe4qxqj0wsp9r
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: ianc-integration
    timestamp: Sat 2009-01-24 14:03:08 +1000
    message:
      Branch.iter_merge_sorted_revisions API (Ian Clatworthy)
    added:
      bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
    modified:
      NEWS                           NEWS-20050323055033-4e00b5db738777ff
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
      bzrlib/remote.py               remote.py-20060720103555-yeeg2x51vn0rbtdp-1
      bzrlib/tests/branch_implementations/__init__.py __init__.py-20060123013057-b12a52c3f361daf4
    ------------------------------------------------------------
    revno: 3949.3.8
    revision-id: ian.clatworthy at canonical.com-20090124035735-r7joe4qxqj0wsp9r
    parent: ian.clatworthy at canonical.com-20090124014858-t8snms0c708b22cj
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Sat 2009-01-24 13:57:35 +1000
    message:
      feedback from poolie
    modified:
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
    ------------------------------------------------------------
    revno: 3949.3.7
    revision-id: ian.clatworthy at canonical.com-20090124014858-t8snms0c708b22cj
    parent: ian.clatworthy at canonical.com-20090124001510-1zy4ycf7et22tq5d
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Sat 2009-01-24 11:48:58 +1000
    message:
      drop seqnum from in-memory cache
    modified:
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
    ------------------------------------------------------------
    revno: 3949.3.6
    revision-id: ian.clatworthy at canonical.com-20090124001510-1zy4ycf7et22tq5d
    parent: ian.clatworthy at canonical.com-20090123212235-e9rkelh590rcdmbb
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Sat 2009-01-24 10:15:10 +1000
    message:
      feedback from beuno
    modified:
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
    ------------------------------------------------------------
    revno: 3949.3.5
    revision-id: ian.clatworthy at canonical.com-20090123212235-e9rkelh590rcdmbb
    parent: ian.clatworthy at canonical.com-20090123211924-am3uaq95d1ebsfcq
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Sat 2009-01-24 07:22:35 +1000
    message:
      NEWS tweak
    modified:
      NEWS                           NEWS-20050323055033-4e00b5db738777ff
    ------------------------------------------------------------
    revno: 3949.3.4
    revision-id: ian.clatworthy at canonical.com-20090123211924-am3uaq95d1ebsfcq
    parent: ian.clatworthy at canonical.com-20090122123241-bv173v5plq0f3s4k
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Sat 2009-01-24 07:19:24 +1000
    message:
      jam feedback: start & stop limits; simple caching
    modified:
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
      bzrlib/remote.py               remote.py-20060720103555-yeeg2x51vn0rbtdp-1
      bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
    ------------------------------------------------------------
    revno: 3949.3.3
    revision-id: ian.clatworthy at canonical.com-20090122123241-bv173v5plq0f3s4k
    parent: ian.clatworthy at canonical.com-20090121030800-q0epxz7r2wq9wklb
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Thu 2009-01-22 22:32:41 +1000
    message:
      simplify the meaning of forward to be appropriate to this layer
    modified:
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
      bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
    ------------------------------------------------------------
    revno: 3949.3.2
    revision-id: ian.clatworthy at canonical.com-20090121030800-q0epxz7r2wq9wklb
    parent: ian.clatworthy at canonical.com-20090121005320-o96d2epcbtd6z331
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Wed 2009-01-21 13:08:00 +1000
    message:
      feedback from jam
    renamed:
      bzrlib/tests/branch_implementations/test_merge_sorted_revisions.py => bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
    modified:
      NEWS                           NEWS-20050323055033-4e00b5db738777ff
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
      bzrlib/tests/branch_implementations/__init__.py __init__.py-20060123013057-b12a52c3f361daf4
      bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
    ------------------------------------------------------------
    revno: 3949.3.1
    revision-id: ian.clatworthy at canonical.com-20090121005320-o96d2epcbtd6z331
    parent: pqm at pqm.ubuntu.com-20090120210300-641tutf1rkdn8a3n
    committer: Ian Clatworthy <ian.clatworthy at canonical.com>
    branch nick: bzr.merge_sorted_revisions
    timestamp: Wed 2009-01-21 10:53:20 +1000
    message:
      introduce Branch.merge_sorted_revisions API
    added:
      bzrlib/tests/branch_implementations/test_merge_sorted_revisions.py test_merge_sorted_re-20090121004847-to3gvjwigstu93eh-1
    modified:
      NEWS                           NEWS-20050323055033-4e00b5db738777ff
      bzrlib/branch.py               branch.py-20050309040759-e4baf4e0d046576e
      bzrlib/tests/branch_implementations/__init__.py __init__.py-20060123013057-b12a52c3f361daf4
=== modified file 'NEWS'
--- a/NEWS	2009-01-23 17:25:52 +0000
+++ b/NEWS	2009-01-24 04:03:08 +0000
@@ -87,6 +87,10 @@
       compile buffers, are such an example).
       (Vincent Ladeuil)
 
+    * New API ``Branch.iter_merge_sorted_revisions()`` that iterates over
+      ``(revision_id, depth, revno, end_of_merge)`` tuples.
+      (Ian Clatworthy)
+
     * New ``Branch.dotted_revno_to_revision_id()`` and
       ``Branch.revision_id_to_dotted_revno()`` APIs that pick the most
       efficient way of doing the mapping.

=== modified file 'bzrlib/branch.py'
--- a/bzrlib/branch.py	2009-01-22 14:24:34 +0000
+++ b/bzrlib/branch.py	2009-01-24 04:03:08 +0000
@@ -91,6 +91,7 @@
         self._revision_id_to_revno_cache = None
         self._partial_revision_id_to_revno_cache = {}
         self._last_revision_info_cache = None
+        self._merge_sorted_revisions_cache = None
         self._open_hook()
         hooks = Branch.hooks['open']
         for hook in hooks:
@@ -283,19 +284,87 @@
 
         :return: A dictionary mapping revision_id => dotted revno.
         """
-        last_revision = self.last_revision()
-        revision_graph = repository._old_get_graph(self.repository,
-            last_revision)
-        merge_sorted_revisions = tsort.merge_sort(
-            revision_graph,
-            last_revision,
-            None,
-            generate_revno=True)
         revision_id_to_revno = dict((rev_id, revno)
-                                    for seq_num, rev_id, depth, revno, end_of_merge
-                                     in merge_sorted_revisions)
+            for rev_id, depth, revno, end_of_merge
+             in self.iter_merge_sorted_revisions())
         return revision_id_to_revno
 
+    @needs_read_lock
+    def iter_merge_sorted_revisions(self, start_revision_id=None,
+            stop_revision_id=None, direction='reverse'):
+        """Walk the revisions for a branch in merge sorted order.
+
+        Merge sorted order is the output from a merge-aware,
+        topological sort, i.e. all parents come before their
+        children going forward; the opposite for reverse.
+
+        :param start_revision_id: the revision_id to begin walking from.
+            If None, the branch tip is used.
+        :param stop_revision_id: the revision_id to terminate the walk
+            after (i.e. the range is inclusive). If None, the rest of
+            history is included.
+        :param direction: either 'reverse' or 'forward':
+            * reverse means return the start_revision_id first, i.e.
+              start at the most recent revision and go backwards in history
+            * forward returns tuples in the opposite order to reverse.
+              Note in particular that forward does *not* do any intelligent
+              ordering w.r.t. depth as some clients of this API may like.
+              (If required, that ought to be done at higher layers.)
+
+        :return: an iterator over (revision_id, depth, revno, end_of_merge)
+            tuples where:
+
+            * revision_id: the unique id of the revision
+            * depth: How many levels of merging deep this node has been
+              found.
+            * revno_sequence: This field provides a sequence of
+              revision numbers for all revisions. The format is:
+              (REVNO, BRANCHNUM, BRANCHREVNO). BRANCHNUM is the number of the
+              branch that the revno is on. From left to right the REVNO numbers
+              are the sequence numbers within that branch of the revision.
+            * end_of_merge: When True the next node (earlier in history) is
+              part of a different merge.
+        """
+        # Note: depth and revno values are in the context of the branch so
+        # we need the full graph to get stable numbers, regardless of the
+        # start_revision_id.
+        if self._merge_sorted_revisions_cache is None:
+            last_revision = self.last_revision()
+            graph = self.repository.get_graph()
+            parent_map = dict(((key, value) for key, value in
+                     graph.iter_ancestry([last_revision]) if value is not None))
+            revision_graph = repository._strip_NULL_ghosts(parent_map)
+            revs = tsort.merge_sort(revision_graph, last_revision, None,
+                generate_revno=True)
+            # Drop the sequence # before caching
+            self._merge_sorted_revisions_cache = [r[1:] for r in revs]
+
+        filtered = self._filter_merge_sorted_revisions(
+            self._merge_sorted_revisions_cache, start_revision_id,
+            stop_revision_id)
+        if direction == 'reverse':
+            return filtered
+        if direction == 'forward':
+            return reversed(list(filtered))
+        else:
+            raise ValueError('invalid direction %r' % direction)
+
+    def _filter_merge_sorted_revisions(self, merge_sorted_revisions,
+        start_revision_id, stop_revision_id):
+        """Iterate over an inclusive range of sorted revisions."""
+        rev_iter = iter(merge_sorted_revisions)
+        if start_revision_id is not None:
+            for rev_id, depth, revno, end_of_merge in rev_iter:
+                if rev_id != start_revision_id:
+                    continue
+                else:
+                    yield rev_id, depth, revno, end_of_merge
+                    break
+        for rev_id, depth, revno, end_of_merge in rev_iter:
+            yield rev_id, depth, revno, end_of_merge
+            if stop_revision_id is not None and rev_id == stop_revision_id:
+                return
+
     def leave_lock_in_place(self):
         """Tell this branch object not to release the physical lock when this
         object is unlocked.
@@ -462,6 +531,7 @@
         self._revision_history_cache = None
         self._revision_id_to_revno_cache = None
         self._last_revision_info_cache = None
+        self._merge_sorted_revisions_cache = None
 
     def _gen_revision_history(self):
         """Return sequence of revision hashes on to this branch.

=== modified file 'bzrlib/remote.py'
--- a/bzrlib/remote.py	2009-01-22 13:58:18 +0000
+++ b/bzrlib/remote.py	2009-01-24 04:03:08 +0000
@@ -1290,6 +1290,7 @@
         self._partial_revision_id_to_revno_cache = {}
         self._revision_history_cache = None
         self._last_revision_info_cache = None
+        self._merge_sorted_revisions_cache = None
         self.bzrdir = remote_bzrdir
         if _client is not None:
             self._client = _client

=== modified file 'bzrlib/tests/branch_implementations/__init__.py'
--- a/bzrlib/tests/branch_implementations/__init__.py	2009-01-22 04:43:30 +0000
+++ b/bzrlib/tests/branch_implementations/__init__.py	2009-01-24 04:03:08 +0000
@@ -161,6 +161,7 @@
         'bzrlib.tests.branch_implementations.test_get_revision_id_to_revno_map',
         'bzrlib.tests.branch_implementations.test_hooks',
         'bzrlib.tests.branch_implementations.test_http',
+        'bzrlib.tests.branch_implementations.test_iter_merge_sorted_revisions',
         'bzrlib.tests.branch_implementations.test_last_revision_info',
         'bzrlib.tests.branch_implementations.test_locking',
         'bzrlib.tests.branch_implementations.test_parent',

=== added file 'bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py'
--- a/bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py	1970-01-01 00:00:00 +0000
+++ b/bzrlib/tests/branch_implementations/test_iter_merge_sorted_revisions.py	2009-01-23 21:19:24 +0000
@@ -0,0 +1,107 @@
+# 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
+
+"""Tests for Branch.iter_merge_sorted_revisions()"""
+
+from bzrlib import (
+    errors,
+    revision,
+    )
+
+from bzrlib.tests.branch_implementations import TestCaseWithBranch
+
+
+class TestIterMergeSortedRevisions(TestCaseWithBranch):
+
+    def test_merge_sorted(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-3', 0, (3,), False),
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ('rev-2', 0, (2,), False),
+            ('rev-1', 0, (1,), True),
+            ], list(the_branch.iter_merge_sorted_revisions()))
+
+    def test_merge_sorted_range(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ('rev-2', 0, (2,), False),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                start_revision_id='rev-1.1.1', stop_revision_id='rev-2')))
+
+    def test_merge_sorted_range_start_only(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ('rev-2', 0, (2,), False),
+            ('rev-1', 0, (1,), True),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                start_revision_id='rev-1.1.1')))
+
+    def test_merge_sorted_range_stop_only(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-3', 0, (3,), False),
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ('rev-2', 0, (2,), False),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                stop_revision_id='rev-2')))
+
+    def test_merge_sorted_forward(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-1', 0, (1,), True),
+            ('rev-2', 0, (2,), False),
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ('rev-3', 0, (3,), False),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                direction='forward')))
+
+    def test_merge_sorted_range_forward(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-2', 0, (2,), False),
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                start_revision_id='rev-1.1.1', stop_revision_id='rev-2',
+                direction='forward')))
+
+    def test_merge_sorted_range_start_only_forward(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-1', 0, (1,), True),
+            ('rev-2', 0, (2,), False),
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                start_revision_id='rev-1.1.1', direction='forward')))
+
+    def test_merge_sorted_range_stop_only_forward(self):
+        tree = self.create_tree_with_merge()
+        the_branch = tree.bzrdir.open_branch()
+        self.assertEqual([
+            ('rev-2', 0, (2,), False),
+            ('rev-1.1.1', 1, (1,1,1), True),
+            ('rev-3', 0, (3,), False),
+            ], list(the_branch.iter_merge_sorted_revisions(
+                stop_revision_id='rev-2', direction='forward')))




More information about the bazaar-commits mailing list