Merge lp:~vila/bzr/320119-exclude-ancestry into lp:bzr

[Vincent Ladeuil]

Add --exclude-common-ancestry log option

This patch adds an --exclude-common-anccestry to bzr log so that -rX..Y becomes
a real graph difference (killing two birds with one stone, it also fixes bug #320119).

From now on, I consider that the log has reached the point where it's really
hard to add new features. The major culprit is the optimization to avoid
loading the whole graph, so no need to spend much time on the log code
unless this problem is correctly addressed.

The performance impact may be significant but I'd like real-life feedback on its
usage before trying to replace the is_ancestor() call by any caching of the X ancestry
(which may be quite significant anyway).

Again, having a better lazy-loaded graph ancestry is needed there.

[Robert Collins (lifeless)]

This seems like something other commands than log will want; perhaps we
should tackle it using an algreba, like git does?

[Andrew Bennetts (spiv)]

You have a few conflicts because this branch waited so long for a review. Sorry :(

You define a new stop_rule for iter_merge_sorted_revisions, but you haven't added it to the docstring. Please fix that.

It's a shame that make_branch_with_alternate_ancestries is duplicated in test_log and per_branch.test_iter_merge_sorted_revisions. Perhaps make it a function and have the latter import it from the former? Please at least add comments in both places noting the duplication.

(And further, it's a shame that the description of the ancestry is duplicated within that code... if only there were some way to do "make_branch_from_ascii_art_ancestry".)

Other than those, this seems ok to me. Once you fix those issues you can consider my vote upgraded to Approve.

I get the feeling that the next time we are tempted to another parameter to log we should think about refactoring the way we pass log options through the various layers (maybe with a LogOptions object? Or maybe Robert's idea about an algebra...), but this is ok for now.

review: Needs Fixing

[Vincent Ladeuil (vila)]

>>>>> Andrew Bennetts <email address hidden> writes:

    > Review: Needs Fixing

    > You have a few conflicts because this branch waited so long for a review. Sorry :(

    > You define a new stop_rule for iter_merge_sorted_revisions, but
    > you haven't added it to the docstring. Please fix that.

Done.

    > It's a shame that make_branch_with_alternate_ancestries is
    > duplicated in test_log and
    > per_branch.test_iter_merge_sorted_revisions. Perhaps make it a
    > function and have the latter import it from the former? Please at
    > least add comments in both places noting the duplication.

Since there is a valuable slight variation, I went with adding comments.

    > (And further, it's a shame that the description of the ancestry is
    > duplicated within that code... if only there were some way to do
    > "make_branch_from_ascii_art_ancestry".)

Hehe, ideally I'd prefer some GUI to define the graph and get both the
ascii art and the branchbuilder stuff from that. ascii art is *not* fun
to write ;)

    > Other than those, this seems ok to me. Once you fix those issues
    > you can consider my vote upgraded to Approve.

Thanks.

    > I get the feeling that the next time we are tempted to another
    > parameter to log we should think about refactoring the way we pass
    > log options through the various layers (maybe with a LogOptions
    > object?

Definitely, but we also need to wire that up to the command line as many
log formatters will want their own options, I've punted on that one so
far for lack of time to research how to catch the options not recognized
by the parser and allow plugins or any external code to give it a try.

    > Or maybe Robert's idea about an algebra...), but this is ok for
    > now.

[bzr PQM (bzr-pqm)]

Successful steps
Failure output:
All lines of log output:
Executing star-merge lp:~vila/bzr/320119-exclude-ancestry at Wed Apr 28 10:41:57 2010
['Nothing to merge.']

[Vincent Ladeuil (vila)]

Meh, where is that pqm failure coming from ?
I sent a single submission with feed-pqm and it was merged.... (I didn't get a success email for it though).

[Robert Collins (lifeless)]

This is probably due to lp taking too long to mark the branch as
merged: if it takes longer than pqm takes to try again, then pqm will
see it as still pending. Possibly we should:
mark things we succeed at as approved
adding a comment that it landed ok

or mark it as merged.

I'm a little worried about triggering launchpadlib errors though,
because lp is going to be updating the status at the same time - we
can collide.

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert Collins wrote:
> This is probably due to lp taking too long to mark the branch as
> merged: if it takes longer than pqm takes to try again, then pqm will
> see it as still pending. Possibly we should:
> mark things we succeed at as approved
> adding a comment that it landed ok
>
> or mark it as merged.
>
> I'm a little worried about triggering launchpadlib errors though,
> because lp is going to be updating the status at the same time - we
> can collide.

I think it would be reasonable to have your script notice that "Nothing
to be Merged" obviously means that the branch is already merged...

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkvY+TsACgkQJdeBCYSNAAPIMQCgqjpPMmQSCREDGp9/5OdQKQVN
V8YAn34mPZMKIzBYQqYSNCR5lVb6+31+
=hVtp
-----END PGP SIGNATURE-----

=== modified file 'NEWS'
--- NEWS	2010-04-27 18:09:12 +0000
+++ NEWS	2010-04-28 07:18:51 +0000
@@ -34,6 +34,11 @@
   better with sudo.
   (Martin <[e-mail]>, Parth Malwankar, #376388)
 
+* ``bzr log --exclude-common-ancestry -r X..Y`` displays the revisions that
+  are part of Y ancestry but not part of X ancestry (aka the graph
+  difference).
+  (Vincent Ladeuil, #320119)
+
 * ``bzr selftest --parallel=fork`` wait for its children avoiding zombies.
   (Vincent Ladeuil, #566670)
 
@@ -145,7 +150,8 @@
   (Andrew Bennetts)
 
 * When invoked with a range revision, ``bzr log`` doesn't show revisions
-  that are not part of the ancestry anymore.
+  that are not part of the Y revisions ancestry anymore when invoked with
+  -rX..Y.
   (Vincent Ladeuil, #474807)
 
 Improvements
 
=== modified file 'bzrlib/branch.py'
--- bzrlib/branch.py	2010-04-23 07:15:23 +0000
+++ bzrlib/branch.py	2010-04-28 07:18:51 +0000
@@ -420,6 +420,8 @@
             * 'include' - the stop revision is the last item in the result
             * 'with-merges' - include the stop revision and all of its
               merged revisions in the result
+            * 'with-merges-without-common-ancestry' - filter out revisions 
+              that are in both ancestries
         :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
@@ -456,7 +458,7 @@
             stop_revision_id, stop_rule)
         # Make sure we don't return revisions that are not part of the
         # start_revision_id ancestry.
-        filtered = self._filter_non_ancestors(filtered)
+        filtered = self._filter_start_non_ancestors(filtered)
         if direction == 'reverse':
             return filtered
         if direction == 'forward':
@@ -499,6 +501,18 @@
                        node.end_of_merge)
                 if rev_id == stop_revision_id:
                     return
+        elif stop_rule == 'with-merges-without-common-ancestry':
+            # We want to exclude all revisions that are already part of the
+            # stop_revision_id ancestry.
+            graph = self.repository.get_graph()
+            ancestors = graph.find_unique_ancestors(start_revision_id,
+                                                    [stop_revision_id])
+            for node in rev_iter:
+                rev_id = node.key[-1]
+                if rev_id not in ancestors:
+                    continue
+                yield (rev_id, node.merge_depth, node.revno,
+                       node.end_of_merge)
         elif stop_rule == 'with-merges':
             stop_rev = self.repository.get_revision(stop_revision_id)
             if stop_rev.parent_ids:
@@ -527,7 +541,7 @@
         else:
             raise ValueError('invalid stop_rule %r' % stop_rule)
 
-    def _filter_non_ancestors(self, rev_iter):
+    def _filter_start_non_ancestors(self, rev_iter):
         # If we started from a dotted revno, we want to consider it as a tip
         # and don't want to yield revisions that are not part of its
         # ancestry. Given the order guaranteed by the merge sort, we will see
 
=== modified file 'bzrlib/builtins.py'
--- bzrlib/builtins.py	2010-04-23 11:11:22 +0000
+++ bzrlib/builtins.py	2010-04-28 07:18:51 +0000
@@ -2299,6 +2299,10 @@
                    help='Show changes made in each revision as a patch.'),
             Option('include-merges',
                    help='Show merged revisions like --levels 0 does.'),
+            Option('exclude-common-ancestry',
+                   help='Display only the revisions that are not part'
+                   ' of both ancestries (require -rX..Y)'
+                   )
             ]
     encoding_type = 'replace'
 
@@ -2314,13 +2318,19 @@
             message=None,
             limit=None,
             show_diff=False,
-            include_merges=False):
+            include_merges=False,
+            exclude_common_ancestry=False,
+            ):
         from bzrlib.log import (
             Logger,
             make_log_request_dict,
             _get_info_for_log_files,
             )
         direction = (forward and 'forward') or 'reverse'
+        if (exclude_common_ancestry
+            and (revision is None or len(revision) != 2)):
+            raise errors.BzrCommandError(
+                '--exclude-common-ancestry requires -r with two revisions')
         if include_merges:
             if levels is None:
                 levels = 0
@@ -2419,7 +2429,9 @@
             direction=direction, specific_fileids=file_ids,
             start_revision=rev1, end_revision=rev2, limit=limit,
             message_search=message, delta_type=delta_type,
-            diff_type=diff_type, _match_using_deltas=match_using_deltas)
+            diff_type=diff_type, _match_using_deltas=match_using_deltas,
+            exclude_common_ancestry=exclude_common_ancestry,
+            )
         Logger(b, rqst).show(lf)
 
 
 
=== modified file 'bzrlib/log.py'
--- bzrlib/log.py	2010-04-14 10:38:57 +0000
+++ bzrlib/log.py	2010-04-28 07:18:51 +0000
@@ -220,14 +220,18 @@
     'direction': 'reverse',
     'levels': 1,
     'generate_tags': True,
+    'exclude_common_ancestry': False,
     '_match_using_deltas': True,
     }
 
 
 def make_log_request_dict(direction='reverse', specific_fileids=None,
-    start_revision=None, end_revision=None, limit=None,
-    message_search=None, levels=1, generate_tags=True, delta_type=None,
-    diff_type=None, _match_using_deltas=True):
+                          start_revision=None, end_revision=None, limit=None,
+                          message_search=None, levels=1, generate_tags=True,
+                          delta_type=None,
+                          diff_type=None, _match_using_deltas=True,
+                          exclude_common_ancestry=False,
+                          ):
     """Convenience function for making a logging request dictionary.
 
     Using this function may make code slightly safer by ensuring
@@ -271,6 +275,9 @@
       algorithm used for matching specific_fileids. This parameter
       may be removed in the future so bzrlib client code should NOT
       use it.
+
+    :param exclude_common_ancestry: Whether -rX..Y should be interpreted as a
+      range operator or as a graph difference.
     """
     return {
         'direction': direction,
@@ -283,6 +290,7 @@
         'generate_tags': generate_tags,
         'delta_type': delta_type,
         'diff_type': diff_type,
+        'exclude_common_ancestry': exclude_common_ancestry,
         # Add 'private' attributes for features that may be deprecated
         '_match_using_deltas': _match_using_deltas,
     }
@@ -459,7 +467,8 @@
             self.branch, self.start_rev_id, self.end_rev_id,
             rqst.get('direction'),
             generate_merge_revisions=generate_merge_revisions,
-            delayed_graph_generation=delayed_graph_generation)
+            delayed_graph_generation=delayed_graph_generation,
+            exclude_common_ancestry=rqst.get('exclude_common_ancestry'))
 
         # Apply the other filters
         return make_log_rev_iterator(self.branch, view_revisions,
@@ -474,7 +483,8 @@
         rqst = self.rqst
         view_revisions = _calc_view_revisions(
             self.branch, self.start_rev_id, self.end_rev_id,
-            rqst.get('direction'), generate_merge_revisions=True)
+            rqst.get('direction'), generate_merge_revisions=True,
+            exclude_common_ancestry=rqst.get('exclude_common_ancestry'))
         if not isinstance(view_revisions, list):
             view_revisions = list(view_revisions)
         view_revisions = _filter_revisions_touching_file_id(self.branch,
@@ -485,12 +495,18 @@
 
 
 def _calc_view_revisions(branch, start_rev_id, end_rev_id, direction,
-    generate_merge_revisions, delayed_graph_generation=False):
+                         generate_merge_revisions,
+                         delayed_graph_generation=False,
+                         exclude_common_ancestry=False,
+                         ):
     """Calculate the revisions to view.
 
     :return: An iterator of (revision_id, dotted_revno, merge_depth) tuples OR
              a list of the same tuples.
     """
+    if (exclude_common_ancestry and start_rev_id == end_rev_id):
+        raise errors.BzrCommandError(
+            '--exclude-common-ancestry requires two different revisions')
     if direction not in ('reverse', 'forward'):
         raise ValueError('invalid direction %r' % direction)
     br_revno, br_rev_id = branch.last_revision_info()
@@ -511,7 +527,8 @@
             iter_revs = reversed(iter_revs)
     else:
         iter_revs = _generate_all_revisions(branch, start_rev_id, end_rev_id,
-                                            direction, delayed_graph_generation)
+                                            direction, delayed_graph_generation,
+                                            exclude_common_ancestry)
         if direction == 'forward':
             iter_revs = _rebase_merge_depth(reverse_by_depth(list(iter_revs)))
     return iter_revs
@@ -542,7 +559,8 @@
 
 
 def _generate_all_revisions(branch, start_rev_id, end_rev_id, direction,
-                            delayed_graph_generation):
+                            delayed_graph_generation,
+                            exclude_common_ancestry=False):
     # On large trees, generating the merge graph can take 30-60 seconds
     # so we delay doing it until a merge is detected, incrementally
     # returning initial (non-merge) revisions while we can.
@@ -594,7 +612,8 @@
     # indented at the end seems slightly nicer in that case.
     view_revisions = chain(iter(initial_revisions),
         _graph_view_revisions(branch, start_rev_id, end_rev_id,
-                              rebase_initial_depths=(direction == 'reverse')))
+                              rebase_initial_depths=(direction == 'reverse'),
+                              exclude_common_ancestry=exclude_common_ancestry))
     return view_revisions
 
 
@@ -659,7 +678,8 @@
 
 
 def _graph_view_revisions(branch, start_rev_id, end_rev_id,
-                          rebase_initial_depths=True):
+                          rebase_initial_depths=True,
+                          exclude_common_ancestry=False):
     """Calculate revisions to view including merges, newest to oldest.
 
     :param branch: the branch
@@ -669,9 +689,13 @@
       revision is found?
     :return: An iterator of (revision_id, dotted_revno, merge_depth) tuples.
     """
+    if exclude_common_ancestry:
+        stop_rule = 'with-merges-without-common-ancestry'
+    else:
+        stop_rule = 'with-merges'
     view_revisions = branch.iter_merge_sorted_revisions(
         start_revision_id=end_rev_id, stop_revision_id=start_rev_id,
-        stop_rule="with-merges")
+        stop_rule=stop_rule)
     if not rebase_initial_depths:
         for (rev_id, merge_depth, revno, end_of_merge
              ) in view_revisions:
 
=== modified file 'bzrlib/tests/blackbox/test_log.py'
--- bzrlib/tests/blackbox/test_log.py	2010-03-24 14:15:01 +0000
+++ bzrlib/tests/blackbox/test_log.py	2010-04-28 07:18:51 +0000
@@ -365,6 +365,18 @@
                             'options are "utc", "original", "local".'],
                            ['log', '--timezone', 'foo'])
 
+    def test_log_exclude_ancestry_no_range(self):
+        self.make_linear_branch()
+        self.run_bzr_error(['bzr: ERROR: --exclude-common-ancestry'
+                            ' requires -r with two revisions'],
+                           ['log', '--exclude-common-ancestry'])
+
+    def test_log_exclude_ancestry_single_revision(self):
+        self.make_merged_branch()
+        self.run_bzr_error(['bzr: ERROR: --exclude-common-ancestry'
+                            ' requires two different revisions'],
+                           ['log', '--exclude-common-ancestry',
+                            '-r1.1.1..1.1.1'])
 
 class TestLogTags(TestLog):
 
 
=== modified file 'bzrlib/tests/per_branch/test_iter_merge_sorted_revisions.py'
--- bzrlib/tests/per_branch/test_iter_merge_sorted_revisions.py	2010-04-02 15:05:24 +0000
+++ bzrlib/tests/per_branch/test_iter_merge_sorted_revisions.py	2010-04-28 07:18:51 +0000
@@ -229,6 +229,37 @@
         self.addCleanup(br.unlock)
         return br
 
+    def make_branch_with_alternate_ancestries(self, relpath='.'):
+        # See test_merge_sorted_exclude_ancestry below for the difference with
+        # bt.test_log.TestLogExcludeAncestry.
+        # make_branch_with_alternate_ancestries and
+        # test_merge_sorted_exclude_ancestry
+        # See the FIXME in assertLogRevnos there too.
+        builder = self.make_branch_builder(relpath)
+        # 1
+        # |\
+        # | 1.1.1
+        # | /| \
+        # 2  |  |
+        # |  |  1.2.1
+        # |  | /
+        # |  1.1.2
+        # | /
+        # 3
+        builder.start_series()
+        builder.build_snapshot('1', None, [
+            ('add', ('', 'TREE_ROOT', 'directory', '')),])
+        builder.build_snapshot('1.1.1', ['1'], [])
+        builder.build_snapshot('2', ['1', '1.1.1'], [])
+        builder.build_snapshot('1.2.1', ['1.1.1'], [])
+        builder.build_snapshot('1.1.2', ['1.1.1', '1.2.1'], [])
+        builder.build_snapshot('3', ['2', '1.1.2'], [])
+        builder.finish_series()
+        br = builder.get_branch()
+        br.lock_read()
+        self.addCleanup(br.unlock)
+        return br
+
     def assertIterRevids(self, expected, branch, *args, **kwargs):
         # We don't care about depths and revnos here, only about returning the
         # right revids.
@@ -259,3 +290,16 @@
         self.assertIterRevids(['2.2.1', '2.1.1', '2', '1'],
                               branch, start_revision_id='2.2.1',
                               stop_rule='with-merges')
+
+    def test_merge_sorted_exclude_ancestry(self):
+        branch = self.make_branch_with_alternate_ancestries()
+        self.assertIterRevids(['3', '1.1.2', '1.2.1', '2', '1.1.1', '1'],
+                              branch)
+        # '2' is not part of the ancestry even if merge_sort order will make it
+        # appear before 1.1.1
+        self.assertIterRevids(['1.1.2', '1.2.1'],
+                              branch,
+                              stop_rule='with-merges-without-common-ancestry',
+                              start_revision_id='1.1.2',
+                              stop_revision_id='1.1.1')
+
 
=== modified file 'bzrlib/tests/per_repository_reference/__init__.py'
--- bzrlib/tests/per_repository_reference/__init__.py	2010-04-16 06:51:59 +0000
+++ bzrlib/tests/per_repository_reference/__init__.py	2010-04-28 07:18:51 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2008, 2009 Canonical Ltd
+# Copyright (C) 2008, 2009, 2010 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
 
=== modified file 'bzrlib/tests/test_log.py'
--- bzrlib/tests/test_log.py	2010-03-25 08:14:04 +0000
+++ bzrlib/tests/test_log.py	2010-04-28 07:18:51 +0000
@@ -18,6 +18,7 @@
 from cStringIO import StringIO
 
 from bzrlib import (
+    branchbuilder,
     errors,
     log,
     registry,
@@ -1541,3 +1542,62 @@
 
     def test_bugs_handler_present(self):
         self.properties_handler_registry.get('bugs_properties_handler')
+
+class TestLogExcludeAncestry(tests.TestCaseWithTransport):
+
+    def make_branch_with_alternate_ancestries(self, relpath='.'):
+        # See test_merge_sorted_exclude_ancestry below for the difference with
+        # bt.per_branch.test_iter_merge_sorted_revision.
+        # TestIterMergeSortedRevisionsBushyGraph. 
+        # make_branch_with_alternate_ancestries
+        # and test_merge_sorted_exclude_ancestry
+        # See the FIXME in assertLogRevnos too.
+        builder = branchbuilder.BranchBuilder(self.get_transport(relpath))
+        # 1
+        # |\
+        # 2 \
+        # |  |
+        # |  1.1.1
+        # |  | \
+        # |  |  1.2.1
+        # |  | /
+        # |  1.1.2
+        # | /
+        # 3
+        builder.start_series()
+        builder.build_snapshot('1', None, [
+            ('add', ('', 'TREE_ROOT', 'directory', '')),])
+        builder.build_snapshot('1.1.1', ['1'], [])
+        builder.build_snapshot('2', ['1'], [])
+        builder.build_snapshot('1.2.1', ['1.1.1'], [])
+        builder.build_snapshot('1.1.2', ['1.1.1', '1.2.1'], [])
+        builder.build_snapshot('3', ['2', '1.1.2'], [])
+        builder.finish_series()
+        br = builder.get_branch()
+        br.lock_read()
+        self.addCleanup(br.unlock)
+        return br
+
+    def assertLogRevnos(self, expected_revnos, b, start, end,
+                        exclude_common_ancestry):
+        # FIXME: the layering in log makes it hard to test intermediate levels,
+        # I wish adding filters with their parameters were easier...
+        # -- vila 20100413
+        iter_revs = log._calc_view_revisions(
+            b, start, end, direction='reverse',
+            generate_merge_revisions=True,
+            exclude_common_ancestry=exclude_common_ancestry)
+        self.assertEqual(expected_revnos,
+                         [revid for revid, revno, depth in iter_revs])
+
+    def test_merge_sorted_exclude_ancestry(self):
+        b = self.make_branch_with_alternate_ancestries()
+        self.assertLogRevnos(['3', '1.1.2', '1.2.1', '1.1.1', '2', '1'],
+                             b, '1', '3', False)
+        # '2' is part of the '3' ancestry but not part of '1.1.1' ancestry so
+        # it should be mentioned even if merge_sort order will make it appear
+        # after 1.1.1
+        self.assertLogRevnos(['3', '1.1.2', '1.2.1', '2'],
+                             b, '1.1.1', '3', True)
+
+