Locating merge that dropped a change

Locating merge that dropped a change

[Kevin Bracey]

This morning, I was struggling (not for the first time) to produce a Git 
command that would identify a merge commit that dropped a change. I 
could see where it was added, but couldn't automate finding out why it 
wasn't any longer in HEAD.

All the permutations of "--full-history", "-m", "-S", "-G" on "git log" 
I could think of did not get me anywhere. As long as I had 
"--full-history", they could find the original commit that had added the 
change, but not the merge commit that had dropped it by taking the other 
parent.

So, how to automatically find a merge that ignored a known change?

And then for visualisation purposes, how do you persuade gitk's diff 
display to actually show that that merge commit removed the change from 
one of its parents? Again, "-m" didn't seem to work.

Help appreciated!

Kevin

Re: Locating merge that dropped a change

[Kevin Bracey]

On 09/04/2013 21:00, Kevin Bracey wrote:
>
> So, how to automatically find a merge that ignored a known change?

I think I've found the problem. It only doesn't work _if you specify the 
file_.

Specifically, if I was missing an addition, my first attempt to find it 
would be

   git log -p -m -S<addition> <file>

If the addition was lost in a merge, that doesn't even show the 
addition, which is surprising, but intentional. The addition isn't part 
of the HEAD version of <file>, so no point going down that path of the 
merge. Fine. However, I expected this to work:

   git log --full-history -p -m -S<addition> <file>

But it doesn't. It finds the addition, but _not_ the loss in the merge 
commit.

But this does work:

   git log -p -m -S<addition>

That really feels like a bug to me. By specifying a file, I've made it 
miss the change, and I can see no way to get the change without making 
it a full-tree operation.

Looking at try_to_simplify_commit() it appears the merge that removed 
the addition is excluded because it's TREESAME to its _other_ parent. 
But with --full-history, we should only be eliminating a merge if its 
TREESAME to all parents, surely? Otherwise we have this case that we 
show a commit but not its reversion.

And the code doing this looks broken, or at least illogical - the parent 
loop sets "tree_same" for a same parent in --full-history, rather than 
immediately setting the TREESAME flag, so maybe previous authors were 
thinking about this. But setting tree_same guarantees that TREESAME is 
always set on exit anyway, so it's pointless (unless I'm missing something).

It does appear this is documented behaviour in the manual: "full-history 
without parent rewriting" .. "P and M were excluded because they are 
TREESAME to _a_ parent." I would say that they should have been excluded 
due to being TREESAME to _all_ parents. I really don't want a merge 
where one version of my file was chosen over another excluded from its 
so-called "full history".

Now, obviously in a sane environment, most merges won't be that 
interesting, as they'll just be propagating wanted patches from the real 
commits already in the log. But I'd like some way to find merges that 
drop code in a specified file, and surely "--full-history" is it?

Kevin

Re: Locating merge that dropped a change

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> I think I've found the problem. It only doesn't work _if you specify
> the file_.
>
> Specifically, if I was missing an addition, my first attempt to find
> it would be
>
>   git log -p -m -S<addition> <file>
>
> If the addition was lost in a merge, that doesn't even show the
> addition, which is surprising, but intentional. The addition isn't
> part of the HEAD version of <file>, so no point going down that path
> of the merge. Fine. However, I expected this to work:
>
>   git log --full-history -p -m -S<addition> <file>
>
> But it doesn't. It finds the addition, but _not_ the loss in the merge
> commit.
>
> But this does work:
>
>   git log -p -m -S<addition>
>
> That really feels like a bug to me. By specifying a file, I've made it
> miss the change, and I can see no way to get the change without making
> it a full-tree operation.
> ... But I'd like some way to find merges
> that drop code in a specified file, and surely "--full-history" is it?

Yeah, I think that is a bug.

    $ echo first >file
    $ git add file && git commit -m initial
    $ git checkout -b side
    $ echo second >file && git commit -a -m side
    $ git checkout - && >file && git add file && git commit -m lose
    $ git merge -s ours -m lost side
    $ git log -p -m --full-history -Ssecond -1 file

does not seem to find the commit that lost the line.

[RFC/PATCH] Make --full-history consider more merges

[Kevin Bracey]

History simplification previously always treated merges as TREESAME
if they were TREESAME to any parent.

While the desired default behaviour, this could be extremely unhelpful
when searching detailed history, and could not be overridden. For
example, if a merge had ignored a change, as if by "-s ours", then:

  git log -m -p --full-history -Schange file

would successfully locate "change"'s addition but would not locate the
merge that resolved against it.

This patch changes the simplification so that when --full-history is
specified, a merge is treated as TREESAME only if it is TREESAME to
_all_ parents. This means the command above locates a merge that dropped
"change".

Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
This would address my problem case - it passes existing tests, and covers
my (all-too-common) problem. But it would also need documentation changes and
a new test.

 revision.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/revision.c b/revision.c
index eb98128..96fe3f5 100644
--- a/revision.c
+++ b/revision.c
@@ -516,8 +516,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 		}
 		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 	}
-	if (tree_changed && !tree_same)
-		return;
+
+	if (tree_changed) {
+		if (!tree_same)
+			return;
+
+		if (!revs->simplify_history && !revs->simplify_merges)
+			return;
+	}
 	commit->object.flags |= TREESAME;
 }
 
-- 
1.8.2.255.g39c5835

Re: [RFC/PATCH] Make --full-history consider more merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> diff --git a/revision.c b/revision.c
> index eb98128..96fe3f5 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -516,8 +516,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>  		}
>  		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
>  	}
> -	if (tree_changed && !tree_same)
> -		return;
> +
> +	if (tree_changed) {
> +		if (!tree_same)
> +			return;
> +
> +		if (!revs->simplify_history && !revs->simplify_merges)
> +			return;

So in addition to "have some change and there is no same parent"
case, under _some_ condition we avoid marking a merge not worth
showing (i.e. TREESAME) if there is any change.

And the condition is !simplify_history and !simplify_merges, which
would cover --full-history, but I am not sure if requiring
!simplify_merges is correct.

Do you need it and if so why?  The --simplify-merges option is
defined as a post-processing operation over what full-history
produces in the list limiting code (which involves the logic the
patch is touching).  The --ancestry-path option works the same way
but its post-processing is done inside the limit_list() function.

So it feels more natural if the patch were ignoring simplify_merges
and paid attention only to simplify_history.

> +	}
>  	commit->object.flags |= TREESAME;
>  }

Re: [RFC/PATCH] Make --full-history consider more merges

[Kevin Bracey]

On 22/04/2013 22:49, Junio C Hamano wrote:
>
> So in addition to "have some change and there is no same parent"
> case, under _some_ condition we avoid marking a merge not worth
> showing (i.e. TREESAME) if there is any change.
>
> And the condition is !simplify_history and !simplify_merges, which
> would cover --full-history, but I am not sure if requiring
> !simplify_merges is correct.

You're right, it isn't correct. Logically, the test should be for
simplify_history. The original patch was overly cautious about
limiting it to --full-history. And it avoided breaking a test -
specifically t6016.7. simplify_merges() should just be post-
processing "full history with parents" as you say, not changing its
behaviour.

I've dug into this more, and am now fairly confident about my analysis.
I believe the problem arises because TREESAME's definition was
conflated with the default simplification behaviour, unnecessarily.
Merges were defined as TREESAME if they matched ANY parent.

That's fine if simplify_history is set, but then in that case a merge
which is TREESAME to any parent is turned into a normal commit based
on that parent anyway, and that simplified commit is inherently
TREESAME, regardless of how we define TREESAME for merges.

If simplify_history isn't set, and we don't want ancestry, then that
TREESAME definition is problematic. It avoids showing merges that
don't have anything actually new, but does lead to this issue that
"git log -Sxxx --full-history" can't locate a dropped change.

If simplify_history is set, and we do want ancestry, then it doesn't
matter about the TREESAME definition because it shows all merges,
regardless of the TREESAME flag. Thus adding "--parents" to the above
command means it can find it, but only because it drags _every_ merge
into consideration. Should that be necessary?

Futher, if we add simplify_merges, then TREESAME becomes a problem.
After merge simplification, we can be left with a single-parent
commit that doesn't match its parent but is skipped due to its
TREESAME flag being set: it was TREESAME to a parent that got dropped.

I think the correction is that TREESAME for a commit needs to be
redefined to be "this commit matches all its (remaining) parents",
rather than "this commit matches at least 1 of its (remaining)
parents". And when we eliminate parents, we have to check for the
flag changing, but we should have been doing that anyway.

Now, what effect does post-processing have on TREESAME? Parent
rewriting due to elimination of duplicates, and making dense has no
effect, as there we're always replacing a commit with something it
was TREESAME to, so that doesn't affect TREESAMEness of its children.

But reduce_heads() in simplify_merges() can have an effect. In the
example shown in the comment, X may or may not be TREESAME to its
remaining single parent. And test 6016.7 covers one instance of
that - reduce_heads() eliminates branches B and C, because they
didn't touch bar.txt, and the rewritten parents were then ancestors
of the A path. But that that "drop ancestor paths" logic totally
ignores TREESAMEness, and we don't know whether the merge kept
the bar.txt from A, or eliminated it by an "-s ours" take of B.

In the 6016.7 case, the merge was originally marked TREESAME, as it
matched A. When B and C were eliminated, it remained TREESAME, and
this wasn't recalculated. And that happened to be correct in this
case, because the merge was "normal".

If on the other hand, the merge had taken the "old" version B with
"-s ours", or if there had been some other semantic change arising
in the merge, then simplify_merges would still have eliminated
B and C, and left a normal commit differing from parent A, but still
marked TREESAME from having matched B. So that would have wrongly
hidden the merge. Recalculation is already necessary to spot the
"odd" case.

If we redefine TREESAME, then recalculation becomes necessary to
handle the "normal" case - the merge will not initially be TREESAME,
as it differs from B and C. But once B and C are eliminated, we
should then determine that the commit is TREESAME from matching
its remaining parent A. Simplification should only ever "increase"
the sameness, so we can avoid recalculation if TREESAME is already
set. Without this recalculation, 6016.7 fails.

So I believe that if reduce_heads() does eliminate any parents, and
TREESAME wasn't set, then we have to recalculate TREESAME, by
running over the remaining parents. A call to
try_to_simplify_commit() does the job, but it feels hacky, and
obviously it's slow. It would be nice if we could remember
"per-parent TREESAME" flags, and shuffle them when we change
parents, but that could be fiddly.

Also if limit_to_ancestry() did eliminate parents from outside the
ancestry, as per the NEEDSWORK comment, then that would also want
to do the TREESAME recalculation. (And it could conceivably be very
useful, helping pick up only the merges that went against your base
commit).

So, given all that, revised patch below:

---
 revision.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/revision.c b/revision.c
index eb98128..15d2f3b 100644
--- a/revision.c
+++ b/revision.c
@@ -432,7 +432,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
 static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 {
     struct commit_list **pp, *parent;
-    int tree_changed = 0, tree_same = 0, nth_parent = 0;
+    int tree_changed = 0, nth_parent = 0;

     /*
      * If we don't do pruning, everything is interesting
@@ -474,7 +474,6 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
                 sha1_to_hex(p->object.sha1));
         switch (rev_compare_tree(revs, p, commit)) {
         case REV_TREE_SAME:
-            tree_same = 1;
             if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
                 /* Even if a merge with an uninteresting
                  * side branch brought the entire change
@@ -516,7 +515,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
         }
         die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
     }
-    if (tree_changed && !tree_same)
+    if (tree_changed)
         return;
     commit->object.flags |= TREESAME;
 }
@@ -2042,9 +2041,19 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
      */
     if (1 < cnt) {
         struct commit_list *h = reduce_heads(commit->parents);
+        int orig_cnt = commit_list_count(commit->parents);
         cnt = commit_list_count(h);
         free_commit_list(commit->parents);
         commit->parents = h;
+        if (cnt < orig_cnt && !(commit->object.flags & TREESAME)) {
+            /* Rewrite will likely change the TREESAME state. Eg in
+             * example above, X could be TREESAME or not to its
+             * remaining single parent, depending on how the merge
+             * was resolved - most likely it is now TREESAME, but
+             * it may not be.
+             */
+            try_to_simplify_commit(revs, commit);
+        }
     }

     /*
-- 
1.8.2.255.g39c5835

Re: [RFC/PATCH] Make --full-history consider more merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> If simplify_history is set, and we do want ancestry, then it doesn't
> matter about the TREESAME definition because it shows all merges,
> regardless of the TREESAME flag. Thus adding "--parents" to the above
> command means it can find it, but only because it drags _every_ merge
> into consideration. Should that be necessary?
>
> Futher, if we add simplify_merges, then TREESAME becomes a problem.
> After merge simplification, we can be left with a single-parent
> commit that doesn't match its parent but is skipped due to its
> TREESAME flag being set: it was TREESAME to a parent that got dropped.
>
> I think the correction is that TREESAME for a commit needs to be
> redefined to be "this commit matches all its (remaining) parents",
> rather than "this commit matches at least 1 of its (remaining)
> parents". And when we eliminate parents, we have to check for the
> flag changing, but we should have been doing that anyway.

Thanks, I think this analysis is quite correct.  Marking a commit
with TREESAME means the commit is not worth showing.  If we are
simplifying side branches away, remaining parents may be reduced to
1 and "all its remaining parents" would be the same as "at least 1
of its remaining parents", but if we want to keep side branches that
matter in explaining the history, we do not want to paint the merge
with TREESAME unless it matches with all its remaining parents.

> If we redefine TREESAME, then recalculation becomes necessary to
> handle the "normal" case - the merge will not initially be TREESAME,
> as it differs from B and C. But once B and C are eliminated, we
> should then determine that the commit is TREESAME from matching
> its remaining parent A. Simplification should only ever "increase"
> the sameness, so we can avoid recalculation if TREESAME is already
> set. Without this recalculation, 6016.7 fails.
>
> So I believe that if reduce_heads() does eliminate any parents, and
> TREESAME wasn't set, then we have to recalculate TREESAME, by
> running over the remaining parents. A call to
> try_to_simplify_commit() does the job, but it feels hacky, and
> obviously it's slow. It would be nice if we could remember
> "per-parent TREESAME" flags, and shuffle them when we change
> parents, but that could be fiddly.
>
> Also if limit_to_ancestry() did eliminate parents from outside the
> ancestry, as per the NEEDSWORK comment, then that would also want
> to do the TREESAME recalculation. (And it could conceivably be very
> useful, helping pick up only the merges that went against your base
> commit).

Yeah, I agree to that.

>
> So, given all that, revised patch below:
>
> ---


>  revision.c | 15 ++++++++++++---
>  1 file changed, 12 insertions(+), 3 deletions(-)
>
> diff --git a/revision.c b/revision.c
> index eb98128..15d2f3b 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -432,7 +432,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
>  static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>  {
>      struct commit_list **pp, *parent;
> -    int tree_changed = 0, tree_same = 0, nth_parent = 0;
> +    int tree_changed = 0, nth_parent = 0;
>
>      /*
>       * If we don't do pruning, everything is interesting
> @@ -474,7 +474,6 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>                  sha1_to_hex(p->object.sha1));
>          switch (rev_compare_tree(revs, p, commit)) {
>          case REV_TREE_SAME:
> -            tree_same = 1;
>              if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
>                  /* Even if a merge with an uninteresting
>                   * side branch brought the entire change
> @@ -516,7 +515,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>          }
>          die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
>      }
> -    if (tree_changed && !tree_same)
> +    if (tree_changed)
>          return;
>      commit->object.flags |= TREESAME;
>  }
> @@ -2042,9 +2041,19 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
>       */
>      if (1 < cnt) {
>          struct commit_list *h = reduce_heads(commit->parents);
> +        int orig_cnt = commit_list_count(commit->parents);
>          cnt = commit_list_count(h);
>          free_commit_list(commit->parents);
>          commit->parents = h;
> +        if (cnt < orig_cnt && !(commit->object.flags & TREESAME)) {
> +            /* Rewrite will likely change the TREESAME state. Eg in
> +             * example above, X could be TREESAME or not to its
> +             * remaining single parent, depending on how the merge
> +             * was resolved - most likely it is now TREESAME, but
> +             * it may not be.
> +             */
> +            try_to_simplify_commit(revs, commit);
> +        }
>      }
>
>      /*

Re: [RFC/PATCH] Make --full-history consider more merges

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

>> So, given all that, revised patch below:

I tried to squeeze the minimum test I sent $gmane/220919 to the test
suite.  I think the "do not use --parents option for this test"
switch needs to be cleaned up a bit more, but it fails without your
patch and does pass with your patch.

I somehow was hoping that your fix to TREESAME semantics would also
correct the known breakage documented in that test, but it seems
that I was too greedy ;-)

Thanks.

 t/t6012-rev-list-simplify.sh | 29 +++++++++++++++++++++++------
 1 file changed, 23 insertions(+), 6 deletions(-)

diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh
index dd6dc84..4e55872 100755
--- a/t/t6012-rev-list-simplify.sh
+++ b/t/t6012-rev-list-simplify.sh
@@ -14,21 +14,24 @@ unnote () {
 
 test_expect_success setup '
 	echo "Hi there" >file &&
-	git add file &&
-	test_tick && git commit -m "Initial file" &&
+	echo "initial" >lost &&
+	git add file lost &&
+	test_tick && git commit -m "Initial file and lost" &&
 	note A &&
 
 	git branch other-branch &&
 
 	echo "Hello" >file &&
-	git add file &&
-	test_tick && git commit -m "Modified file" &&
+	echo "second" >lost &&
+	git add file lost &&
+	test_tick && git commit -m "Modified file and lost" &&
 	note B &&
 
 	git checkout other-branch &&
 
 	echo "Hello" >file &&
-	git add file &&
+	>lost &&
+	git add file lost &&
 	test_tick && git commit -m "Modified the file identically" &&
 	note C &&
 
@@ -37,7 +40,9 @@ test_expect_success setup '
 	test_tick && git commit -m "Add another file" &&
 	note D &&
 
-	test_tick && git merge -m "merge" master &&
+	test_tick &&
+	test_must_fail git merge -m "merge" master &&
+	>lost && git commit -a -m "merge" &&
 	note E &&
 
 	echo "Yet another" >elif &&
@@ -110,4 +115,16 @@ check_result 'I B A' -- file
 check_result 'I B A' --topo-order -- file
 check_result 'H' --first-parent -- another-file
 
+check_result 'E C B A' --full-history E -- lost
+test_expect_success 'full history simplification without parent' '
+	printf "%s\n" E C B A >expect &&
+	git log --pretty="$FMT" --full-history E -- lost |
+	unnote >actual &&
+	sed -e "s/^.*	\([^ ]*\) .*/\1/" >check <actual &&
+	test_cmp expect check || {
+		cat actual
+		false
+	}
+'
+
 test_done
-- 
1.8.2.1-730-gf07461b

Re: [RFC/PATCH] Make --full-history consider more merges

[Kevin Bracey]

On 25/04/2013 04:59, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>>> So, given all that, revised patch below:
> I tried to squeeze the minimum test I sent $gmane/220919 to the test
> suite.  I think the "do not use --parents option for this test"
> switch needs to be cleaned up a bit more, but it fails without your
> patch and does pass with your patch.
>
> I somehow was hoping that your fix to TREESAME semantics would also
> correct the known breakage documented in that test, but it seems
> that I was too greedy ;-)
Thanks for the test addition. Maybe we will be able to satisfy your 
greed in this series. There could be more worth doing here, and I think 
getting TREESAME precise is key.

I think I do want to take the step of storing "treesame per parent". And 
once we do that, as well as avoiding the expensive re-diff, we have much 
richer information readily available as a simplification input (and output).

I'm working on a patch that does this - filling in an initial treesame[] 
array as a decoration in try_to_simplify_commit() is easy, and 
maintaining the array through later parent rewrites isn't as onerous as 
I feared - there are only a few places that rewrite parents after the 
initial scan. With a couple of helper functions to do things like 
"delete nth", I think it'll be quite tidy.

I believe that simplify_merges itself needs at least one addition, and 
could use the treesame[] array to do it: if after doing reduce_heads, a 
commit is now different to all remaining parents, but there was a 
TREESAME parent eliminated, that parent should be reinstated. That would 
clearly highlight missed merges, showing both that "older" TREESAME 
parent and the newer !TREESAME parent that would have been taken in a 
normal merge.

And maybe there's more simplify_merges could do, if it had this full 
TREESAME information available.

(But even after you do all this stuff to get the right commits out, we 
then hit a niggle of mine that gitk forces --cc diffs - even if it shows 
shows the offending merge commit, you can't get it to do a diff...)

Kevin

Re: [RFC/PATCH] Make --full-history consider more merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> On 25/04/2013 04:59, Junio C Hamano wrote:
>> Junio C Hamano <gitster@pobox.com> writes:
>>
>>>> So, given all that, revised patch below:
>> I tried to squeeze the minimum test I sent $gmane/220919 to the test
>> suite.  I think the "do not use --parents option for this test"
>> switch needs to be cleaned up a bit more, but it fails without your
>> patch and does pass with your patch.
>>
>> I somehow was hoping that your fix to TREESAME semantics would also
>> correct the known breakage documented in that test, but it seems
>> that I was too greedy ;-)
> Thanks for the test addition. Maybe we will be able to satisfy your
> greed in this series. There could be more worth doing here, and I
> think getting TREESAME precise is key.

It is perfectly fine to do things one step at a time.  Let's get
the --full-history change into a good shape first and worry about
the more complex case after we are done.

Re: [RFC/PATCH] Make --full-history consider more merges

[Kevin Bracey]

On 25/04/2013 19:51, Junio C Hamano wrote:
> Kevin Bracey <kevin@bracey.fi> writes:
>
>> Thanks for the test addition. Maybe we will be able to satisfy your
>> greed in this series. There could be more worth doing here, and I
>> think getting TREESAME precise is key.
> It is perfectly fine to do things one step at a time.  Let's get
> the --full-history change into a good shape first and worry about
> the more complex case after we are done.

So do you see the rerun of try_to_simplify_commit() as acceptable? I'm 
really not happy with it - it was fine for an initial proof-of-concept, 
but it's an obvious waste of CPU cycles to recompute something we 
already figured out, and I'm uncomfortable with the fact that the 
function potentially does more than just compute TREESAME; by inspection 
it seems safe given the known context inside simplify_merges(), but it 
feels like something waiting to trip us up. The latter could be dealt 
with by breaking try_to_simplify_commit() up, but that feels like a 
diversion. I'd rather just get on and make this first patch store and 
use the per-parent-treesame flags if feasible.

Kevin

Re: [RFC/PATCH] Make --full-history consider more merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> On 25/04/2013 19:51, Junio C Hamano wrote:
>> Kevin Bracey <kevin@bracey.fi> writes:
>>
>>> Thanks for the test addition. Maybe we will be able to satisfy your
>>> greed in this series. There could be more worth doing here, and I
>>> think getting TREESAME precise is key.
>> It is perfectly fine to do things one step at a time.  Let's get
>> the --full-history change into a good shape first and worry about
>> the more complex case after we are done.
>
> So do you see the rerun of try_to_simplify_commit() as acceptable? I'm
> really not happy with it - it was fine for an initial
> proof-of-concept, but it's an obvious waste of CPU cycles to recompute
> something we already figured out, and I'm uncomfortable with the fact
> that the function potentially does more than just compute TREESAME; by
> inspection it seems safe given the known context inside
> simplify_merges(), but it feels like something waiting to trip us
> up.

True.

> The latter could be dealt with by breaking
> try_to_simplify_commit() up, but that feels like a diversion. I'd
> rather just get on and make this first patch store and use the
> per-parent-treesame flags if feasible.

OK.  We have survived with this corner case glitch for more than 6
years, so a fix is not ultra-urgent.  Let's try to see if we can get
it right.

How many decorations are we talking about here?  One for each merge
commit in the entire history?  Do we have a cue that can tell us
when we are really done with a commit that lets us discard the
associated data as we go on digging, keeping the size of our working
set somewhat bounded, perhaps proportional to the number of commits
in our rev_info->commits queue?

Re: [RFC/PATCH] Make --full-history consider more merges

[Kevin Bracey]

On 25/04/2013 21:19, Junio C Hamano wrote:
> How many decorations are we talking about here? One for each merge 
> commit in the entire history? Do we have a cue that can tell us when 
> we are really done with a commit that lets us discard the associated 
> data as we go on digging, keeping the size of our working set somewhat 
> bounded, perhaps proportional to the number of commits in our 
> rev_info->commits queue? 

As it stands, it's one decoration per interesting merge commit that's 
processed by try_to_simplify_commit(), if simplify_merges is set. (Only 
simplify_merges needs the information at present - conceivably 
limit_to_ancestry could use it too). I don't know how to go about 
discarding the data, or when it could be done - I'm not clear enough on 
the wider sequencing machinery in revision.c yet.

I have a first draft of a set of patches, which will follow this message.

1/3 addresses the initial "get simplify_merges right", passing your 
test. That patch is written to make it easy to extend with the next two, 
which add a "never eliminate all our TREESAME parents" rule, and 
reinstate your reverted"eliminate irrelevant side branches". The error I 
spotted in that was that you weren't checking that you were eliminating 
root commits - with that fixed it seems sound to me.

I need to create a new test for patch 2, but this version passes the 
full test suite, including fixing the known failure in t6012, and it 
also gets the examples in the manual right. (I've extended the examples 
to include the irrelevant side branch - not sure this is worthwhile, as 
it's such an unusual case, and I think that section is confusing enough 
for newbies...)

Kevin

[RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[Kevin Bracey]

Historically TREESAME was set on a commit if it was TREESAME to _any_ of
its parents. This is not optimal, as such a merge could still be worth
showing, particularly if it is an odd "-s ours" merge that (possibly
accidentally) dropped a change. And the problem is further compounded by
the fact that simplify_merges could drop the actual parent that a commit
was TREESAME to, leaving it as a normal commit marked TREESAME that
isn't actually TREESAME to its remaining parent.

This commit redefines TREESAME to be true only if a commit is TREESAME to
_all_ of its parents. This doesn't affect either the default
simplify_history behaviour (because partially TREESAME merges are turned
into normal commits), or full-history with parent rewriting (because all
merges are output). But it does affect other modes.

It also modifies simplify_merges to recalculate TREESAME after removing
a parent. This is achieved by storing per-parent TREESAME flags on the
initial scan, so the combined flag can be easily recomputed.

Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
 Documentation/rev-list-options.txt |   2 +-
 revision.c                         | 220 ++++++++++++++++++++++++++++++++-----
 revision.h                         |   1 +
 3 files changed, 192 insertions(+), 31 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 3bdbf5e..380db48 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -413,7 +413,7 @@ parent lines.
 	I  A  B  N  D  O
 -----------------------------------------------------------------------
 +
-`P` and `M` were excluded because they are TREESAME to a parent.  `E`,
+`P` and `M` were excluded because they are TREESAME to both parents.  `E`,
 `C` and `B` were all walked, but only `B` was !TREESAME, so the others
 do not appear.
 +
diff --git a/revision.c b/revision.c
index a67b615..176eb7b 100644
--- a/revision.c
+++ b/revision.c
@@ -429,10 +429,85 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
 	return retval >= 0 && (tree_difference == REV_TREE_SAME);
 }
 
+struct treesame_state {
+	unsigned int nparents;
+	unsigned char treesame[FLEX_ARRAY];
+};
+
+static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)
+{
+	unsigned n = commit_list_count(commit->parents);
+	struct treesame_state *st = xcalloc(1, sizeof(*st) + n);
+	st->nparents = n;
+	add_decoration(&revs->treesame, &commit->object, st);
+	return st;
+}
+
+static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned parent)
+{
+	struct treesame_state *st = lookup_decoration(&revs->treesame, &commit->object);
+	int old_same;
+
+	if (!st || parent >= st->nparents)
+		die("compact_treesame %u", parent);
+
+	/* Can be useful to indicate sameness of removed parent */
+	old_same = st->treesame[parent];
+
+	memmove(st->treesame + parent,
+		st->treesame + parent + 1,
+		st->nparents - parent - 1);
+
+	/* If we've just become a non-merge commit, update TREESAME
+	 * immediately, in case we trigger an early-exit optimisation.
+	 * (Note that there may be a mismatch between commit->parents and the
+	 * treesame_state at this stage, as we may be in mid-rewrite).
+	 * If still a merge, defer update until update_treesame().
+	 */
+	switch (--st->nparents) {
+	case 0:
+		if (rev_same_tree_as_empty(revs, commit))
+			commit->object.flags |= TREESAME;
+		else
+			commit->object.flags &= ~TREESAME;
+		break;
+	case 1:
+		if (st->treesame[0] && revs->dense)
+			commit->object.flags |= TREESAME;
+		else
+			commit->object.flags &= ~TREESAME;
+		break;
+	}
+
+	return old_same;
+}
+
+static unsigned update_treesame(struct rev_info *revs, struct commit *commit)
+{
+	/* If 0 or 1 parents, TREESAME should be valid already */
+	if (commit->parents && commit->parents->next) {
+		int n = 0;
+		struct treesame_state *st;
+
+		st = lookup_decoration(&revs->treesame, &commit->object);
+		if (!st) die("update_treesame");
+		commit->object.flags |= TREESAME;
+		for (n = 0; n < st->nparents; n++) {
+			if (!st->treesame[n]) {
+				commit->object.flags &= ~TREESAME;
+				break;
+			}
+		}
+	}
+
+	return commit->object.flags & TREESAME;
+}
+
 static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 {
 	struct commit_list **pp, *parent;
-	int tree_changed = 0, tree_same = 0, nth_parent = 0;
+	struct treesame_state *ts = NULL;
+	int tree_changed = 0, nth_parent = 0;
 
 	/*
 	 * If we don't do pruning, everything is interesting
@@ -456,25 +531,38 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 	if (!revs->dense && !commit->parents->next)
 		return;
 
-	pp = &commit->parents;
-	while ((parent = *pp) != NULL) {
+	for (pp = &commit->parents;
+	     (parent = *pp) != NULL;
+	     pp = &parent->next, nth_parent++) {
 		struct commit *p = parent->item;
 
-		/*
-		 * Do not compare with later parents when we care only about
-		 * the first parent chain, in order to avoid derailing the
-		 * traversal to follow a side branch that brought everything
-		 * in the path we are limited to by the pathspec.
-		 */
-		if (revs->first_parent_only && nth_parent++)
-			break;
+		if (nth_parent == 1) {
+			/*
+			 * Do not compare with later parents when we care only about
+			 * the first parent chain, in order to avoid derailing the
+			 * traversal to follow a side branch that brought everything
+			 * in the path we are limited to by the pathspec.
+			 */
+			if (revs->first_parent_only)
+				break;
+			/*
+			 * If this is going to remain a merge, and it's
+			 * interesting, remember per-parent treesame for
+			 * simplify_merges().
+			 */
+			if (revs->simplify_merges && !(p->object.flags & UNINTERESTING)) {
+				ts = initialise_treesame(revs, commit);
+				if (!tree_changed)
+					ts->treesame[0] = 1;
+
+			}
+		}
 		if (parse_commit(p) < 0)
 			die("cannot simplify commit %s (because of %s)",
 			    sha1_to_hex(commit->object.sha1),
 			    sha1_to_hex(p->object.sha1));
 		switch (rev_compare_tree(revs, p, commit)) {
 		case REV_TREE_SAME:
-			tree_same = 1;
 			if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
 				/* Even if a merge with an uninteresting
 				 * side branch brought the entire change
@@ -482,7 +570,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 				 * to lose the other branches of this
 				 * merge, so we just keep going.
 				 */
-				pp = &parent->next;
+				if (ts)
+					ts->treesame[nth_parent] = 1;
 				continue;
 			}
 			parent->next = NULL;
@@ -511,12 +600,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 		case REV_TREE_OLD:
 		case REV_TREE_DIFFERENT:
 			tree_changed = 1;
-			pp = &parent->next;
 			continue;
 		}
 		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 	}
-	if (tree_changed && !tree_same)
+	if (tree_changed)
 		return;
 	commit->object.flags |= TREESAME;
 }
@@ -773,6 +861,9 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li
 	 * NEEDSWORK: decide if we want to remove parents that are
 	 * not marked with TMP_MARK from commit->parents for commits
 	 * in the resulting list.  We may not want to do that, though.
+	 *
+	 * Maybe it should be considered if we are TREESAME to such
+	 * parents - now possible with stored per-parent flags.
 	 */
 
 	/*
@@ -1930,28 +2021,32 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi
 	l->next = add_decoration(&revs->children, &parent->object, l);
 }
 
-static int remove_duplicate_parents(struct commit *commit)
+static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)
 {
+	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
 	struct commit_list **pp, *p;
 	int surviving_parents;
 
 	/* Examine existing parents while marking ones we have seen... */
 	pp = &commit->parents;
+	surviving_parents = 0;
 	while ((p = *pp) != NULL) {
 		struct commit *parent = p->item;
 		if (parent->object.flags & TMP_MARK) {
 			*pp = p->next;
+			if (ts)
+				compact_treesame(revs, commit, surviving_parents);
 			continue;
 		}
 		parent->object.flags |= TMP_MARK;
+		surviving_parents++;
 		pp = &p->next;
 	}
-	/* count them while clearing the temporary mark */
-	surviving_parents = 0;
+	/* clear the temporary mark */
 	for (p = commit->parents; p; p = p->next) {
 		p->item->object.flags &= ~TMP_MARK;
-		surviving_parents++;
 	}
+	/* no update_treesame() - removing duplicates can't affect TREESAME */
 	return surviving_parents;
 }
 
@@ -1971,6 +2066,70 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,
 	return st;
 }
 
+static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
+{
+	struct commit_list *h = reduce_heads(commit->parents);
+	int i = 0, marked = 0;
+	struct commit_list *po, *pn;
+
+	/* Want these for sanity only */
+	int orig_cnt = commit_list_count(commit->parents);
+	int cnt = commit_list_count(h);
+
+	/* Not ready to remove items yet, just mark them for now, based
+	 * on the output of reduce_heads(). reduce_heads outputs the reduced
+	 * set in its original order, so this isn't too hard.
+	 */
+	po = commit->parents;
+	pn = h;
+	while (po) {
+		if (pn && po->item == pn->item) {
+			pn=pn->next;
+			i++;
+		}
+		else {
+			po->item->object.flags |= TMP_MARK;
+			marked++;
+		}
+		po=po->next;
+	}
+
+	if (i != cnt || cnt+marked != orig_cnt)
+		die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
+
+	free_commit_list(h);
+
+	return marked;
+}
+
+static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
+{
+	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
+	struct commit_list **pp, *p;
+	int n, removed = 0;
+
+	pp = &commit->parents;
+	n = 0;
+	while ((p = *pp) != NULL) {
+		struct commit *parent = p->item;
+		if (parent->object.flags & TMP_MARK) {
+			parent->object.flags &= ~TMP_MARK;
+			compact_treesame(revs, commit, n);
+			*pp = p->next;
+			free(p);
+			removed++;
+			continue;
+		}
+		pp = &p->next;
+		n++;
+	}
+
+	if (removed)
+		update_treesame(revs, commit);
+
+	return removed;
+}
+
 static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
 {
 	struct commit_list *p;
@@ -2015,7 +2174,9 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
 	}
 
 	/*
-	 * Rewrite our list of parents.
+	 * Rewrite our list of parents. Note that this cannot
+	 * affect our TREESAME flags in anyway - a commit is
+	 * always TREESAME to its simplification.
 	 */
 	for (p = commit->parents; p; p = p->next) {
 		pst = locate_simplify_state(revs, p->item);
@@ -2027,31 +2188,30 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
 	if (revs->first_parent_only)
 		cnt = 1;
 	else
-		cnt = remove_duplicate_parents(commit);
+		cnt = remove_duplicate_parents(revs, commit);
 
 	/*
 	 * It is possible that we are a merge and one side branch
 	 * does not have any commit that touches the given paths;
-	 * in such a case, the immediate parents will be rewritten
-	 * to different commits.
+	 * in such a case, the immediate parent from that branch
+	 * will be rewritten to be the merge base.
 	 *
 	 *      o----X		X: the commit we are looking at;
 	 *     /    /		o: a commit that touches the paths;
 	 * ---o----'
 	 *
-	 * Further reduce the parents by removing redundant parents.
+	 * Detect and simplify this case.
 	 */
 	if (1 < cnt) {
-		struct commit_list *h = reduce_heads(commit->parents);
-		cnt = commit_list_count(h);
-		free_commit_list(commit->parents);
-		commit->parents = h;
+		int marked = mark_redundant_parents(revs, commit);
+		if (marked)
+			remove_marked_parents(revs, commit);
 	}
 
 	/*
 	 * A commit simplifies to itself if it is a root, if it is
 	 * UNINTERESTING, if it touches the given paths, or if it is a
-	 * merge and its parents simplifies to more than one commits
+	 * merge and its parents simplify to more than one commit
 	 * (the first two cases are already handled at the beginning of
 	 * this function).
 	 *
@@ -2218,7 +2378,7 @@ static int rewrite_parents(struct rev_info *revs, struct commit *commit)
 		}
 		pp = &parent->next;
 	}
-	remove_duplicate_parents(commit);
+	remove_duplicate_parents(revs, commit);
 	return 0;
 }
 
diff --git a/revision.h b/revision.h
index 01bd2b7..1abe57b 100644
--- a/revision.h
+++ b/revision.h
@@ -167,6 +167,7 @@ struct rev_info {
 	struct reflog_walk_info *reflog_info;
 	struct decoration children;
 	struct decoration merge_simplification;
+	struct decoration treesame;
 
 	/* notes-specific options: which refs to show */
 	struct display_notes_opt notes_opt;
-- 
1.8.2.1.632.gd2b1879

[RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents

[Kevin Bracey]

In the event of an odd merge, we may find ourselves TREESAME to
apparently redundant parents. Prevent simplify_merges() from removing
every TREESAME parent - in the event of such a merge it's useful to see
where we came actually from came.

Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
 Documentation/rev-list-options.txt |  3 ++-
 revision.c                         | 24 ++++++++++++++++++++++++
 2 files changed, 26 insertions(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 380db48..0832004 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -472,7 +472,8 @@ history according to the following rules:
 +
 * Replace each parent `P` of `C'` with its simplification `P'`.  In
   the process, drop parents that are ancestors of other parents, and
-  remove duplicates.
+  remove duplicates, but take care to never drop all parents that
+  we are TREESAME to.
 +
 * If after this parent rewriting, `C'` is a root or merge commit (has
   zero or >1 parents), a boundary commit, or !TREESAME, it remains.
diff --git a/revision.c b/revision.c
index 176eb7b..4e27c9a 100644
--- a/revision.c
+++ b/revision.c
@@ -2106,8 +2106,32 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
 {
 	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
 	struct commit_list **pp, *p;
+	struct commit *su = NULL, *sm = NULL;
 	int n, removed = 0;
 
+	/* Prescan - look for both marked and unmarked TREESAME parents */
+	for (p = commit->parents, n = 0; p; p = p->next, n++) {
+		if (ts->treesame[n]) {
+			if (p->item->object.flags & TMP_MARK) {
+				if (!sm) sm = p->item;
+			}
+			else {
+				if (!su) {
+					su = p->item;
+					break;
+				}
+			}
+		}
+	}
+
+	/* If we are TREESAME to a marked-for-deletion parent, but not to any
+	 * unmarked parents, unmark the first TREESAME parent. We don't want
+	 * to remove our "real" parent in the event of an "-s ours" type
+	 * merge.
+	 */
+	if (!su && sm)
+		sm->object.flags &= ~TMP_MARK;
+
 	pp = &commit->parents;
 	n = 0;
 	while ((p = *pp) != NULL) {
-- 
1.8.2.1.632.gd2b1879

Re: [RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> In the event of an odd merge, we may find ourselves TREESAME to
> apparently redundant parents. Prevent simplify_merges() from removing
> every TREESAME parent - in the event of such a merge it's useful to see
> where we came actually from came.
>
> Signed-off-by: Kevin Bracey <kevin@bracey.fi>
> ---
>  Documentation/rev-list-options.txt |  3 ++-
>  revision.c                         | 24 ++++++++++++++++++++++++
>  2 files changed, 26 insertions(+), 1 deletion(-)
>
> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 380db48..0832004 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -472,7 +472,8 @@ history according to the following rules:
>  +
>  * Replace each parent `P` of `C'` with its simplification `P'`.  In
>    the process, drop parents that are ancestors of other parents, and
> -  remove duplicates.
> +  remove duplicates, but take care to never drop all parents that
> +  we are TREESAME to.
>  +
>  * If after this parent rewriting, `C'` is a root or merge commit (has
>    zero or >1 parents), a boundary commit, or !TREESAME, it remains.
> diff --git a/revision.c b/revision.c
> index 176eb7b..4e27c9a 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -2106,8 +2106,32 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
>  {
>  	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
>  	struct commit_list **pp, *p;
> +	struct commit *su = NULL, *sm = NULL;

What do "su" and "sm" stand for?

>  	int n, removed = 0;
>  
> +	/* Prescan - look for both marked and unmarked TREESAME parents */
> +	for (p = commit->parents, n = 0; p; p = p->next, n++) {
> +		if (ts->treesame[n]) {
> +			if (p->item->object.flags & TMP_MARK) {
> +				if (!sm) sm = p->item;
> +			}
> +			else {
> +				if (!su) {
> +					su = p->item;
> +					break;
> +				}
> +			}
> +		}
> +	}
> +
> +	/* If we are TREESAME to a marked-for-deletion parent, but not to any
> +	 * unmarked parents, unmark the first TREESAME parent. We don't want
> +	 * to remove our "real" parent in the event of an "-s ours" type
> +	 * merge.

Could you explain here a bit more the reason why we do not want to
remove them and why "-s ours" is so significant that it deserves to
be singled out?  And why randomly picking one that is redundant
(because it is an ancestor of some other parent) is an improvement?

The "remove-redundant" logic first marks commits that are ancestors
of other commits in the original set, without taking treesame[] into
account at all.  If the final objective of the code is to keep paths
that consists of non-treesame[] commits, perhaps the logic needs to
be changed to reject non-treesame[] commits that are ancestors of
other non-treesame[] commits, or something?

> +	 */
> +	if (!su && sm)
> +		sm->object.flags &= ~TMP_MARK;
> +
>  	pp = &commit->parents;
>  	n = 0;
>  	while ((p = *pp) != NULL) {

Re: [RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents

[Kevin Bracey]

On 28/04/2013 02:02, Junio C Hamano wrote:
> Kevin Bracey <kevin@bracey.fi> writes:
>
>> In the event of an odd merge, we may find ourselves TREESAME to
>> apparently redundant parents. Prevent simplify_merges() from removing
>> every TREESAME parent - in the event of such a merge it's useful to see
>> where we came actually from came.

"came from" :)

>>
>> @@ -2106,8 +2106,32 @@ static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
>>   {
>>   	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
>>   	struct commit_list **pp, *p;
>> +	struct commit *su = NULL, *sm = NULL;
> What do "su" and "sm" stand for?

"same, unmarked" and "same, marked" were what was in my head.


> Could you explain here a bit more the reason why we do not want to
> remove them and why "-s ours" is so significant that it deserves to
> be singled out?  And why randomly picking one that is redundant
> (because it is an ancestor of some other parent) is an improvement?

I feel it's consistent with the default non-full-history behaviour. The 
parent that we choose not to remove is the  same one that the default 
log with "simplify_history==1" would have followed: the first parent we 
are TREESAME to. Or at least that's the intent. So this parent would 
normally be singled out, and it's not an arbitrary (or "random") choice.

It feels wrong to me that --full-history --simplify-merges could produce 
a disjoint history from the default. I think it should include the 
default simple history. If this code triggered, it should produce 
something quite distinctive in a graphical view, which will help find 
odd/broken merges.


> The "remove-redundant" logic first marks commits that are ancestors
> of other commits in the original set, without taking treesame[] into
> account at all.  If the final objective of the code is to keep paths
> that consists of non-treesame[] commits, perhaps the logic needs to
> be changed to reject non-treesame[] commits that are ancestors of
> other non-treesame[] commits, or something?

Maybe - the main simplify_merges machinery could certainly make use of 
the treesame[] information, and one of the motivations for introducing 
it was to open up the possibility of richer analysis. I'll spend a 
little time to think about whether we want a more fundamental change to 
the original scan.

But this patch as it stands was an "easy" change to make with clearly 
limited scope and relatively little risk - I specifically wanted just to 
include our default "simple" parent.

Kevin

Re: [RFC/PATCH 2/3] simplify-merges: never remove all TREESAME parents

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

>> Could you explain here a bit more the reason why we do not want to
>> remove them and why "-s ours" is so significant that it deserves to
>> be singled out?  And why randomly picking one that is redundant
>> (because it is an ancestor of some other parent) is an improvement?
>
> I feel it's consistent with the default non-full-history
> behaviour. The parent that we choose not to remove is the  same one
> that the default log with "simplify_history==1" would have followed:
> the first parent we are TREESAME to. Or at least that's the intent. So
> this parent would normally be singled out, and it's not an arbitrary
> (or "random") choice.
>
> It feels wrong to me that --full-history --simplify-merges could
> produce a disjoint history from the default.

Finally ;-)  That "avoid creating a disjoint history" is the "why we
do not want to remove them" I wanted to see in the same comment.

> But this patch as it stands was an "easy" change to make with clearly
> limited scope and relatively little risk - I specifically wanted just
> to include our default "simple" parent.

Yeah, I think it all makes sense.

[RFC/PATCH 3/3] simplify-merges: drop merge from irrelevant side branch

[Kevin Bracey]

Reimplement commit 4b7f53da on top of the new simplify-merges
infrastructure, tightening the condition to only consider root parents;
the original version incorrectly dropped parents that were TREESAME to
anything.

Original log message follows.

The merge simplification rule stated in 6546b59 (revision traversal:
show full history with merge simplification, 2008-07-31) still
treated merge commits too specially.  Namely, in a history with this
shape:

	---o---o---M
	          /
         x---x---x

where three 'x' were on a history completely unrelated to the main
history 'o' and do not touch any of the paths we are following, we
still said that after simplifying all of the parents of M, 'x'
(which is the leftmost 'x' that rightmost 'x simplifies down to) and
'o' (which would be the last commit on the main history that touches
the paths we are following) are independent from each other, and
both need to be kept.

That is incorrect; when the side branch 'x' never touches the paths,
it should be removed to allow M to simplify down to the last commit
on the main history that touches the paths.

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
 Documentation/rev-list-options.txt | 35 ++++++++++++++++++++++-------------
 revision.c                         | 26 +++++++++++++++++++++++++-
 t/t6012-rev-list-simplify.sh       |  2 +-
 3 files changed, 48 insertions(+), 15 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 0832004..db45401 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -342,13 +342,13 @@ In the following, we will always refer to the same example history to
 illustrate the differences between simplification settings.  We assume
 that you are filtering for a file `foo` in this commit graph:
 -----------------------------------------------------------------------
-	  .-A---M---N---O---P
-	 /     /   /   /   /
-	I     B   C   D   E
-	 \   /   /   /   /
-	  `-------------'
+	  .-A---M---N---O---P---Q
+	 /     /   /   /   /   /
+	I     B   C   D   E   Y
+	 \   /   /   /   /   /
+	  `-------------'   X
 -----------------------------------------------------------------------
-The horizontal line of history A---P is taken to be the first parent of
+The horizontal line of history A---Q is taken to be the first parent of
 each merge.  The commits are:
 
 * `I` is the initial commit, in which `foo` exists with contents
@@ -370,6 +370,10 @@ each merge.  The commits are:
   strings to "quux xyzzy".  Despite appearing interesting, `P` is
   TREESAME to all parents.
 
+* `X` is an indpendent root commit that added a new file `side`, and `Y`
+  modified it. `Y` is TREESAME to `X`. Its merge `Q` added `side` to `P`, and
+  `Q` is TREESAME to all parents.
+
 'rev-list' walks backwards through history, including or excluding
 commits based on whether '\--full-history' and/or parent rewriting
 (via '\--parents' or '\--children') are used.  The following settings
@@ -413,7 +417,7 @@ parent lines.
 	I  A  B  N  D  O
 -----------------------------------------------------------------------
 +
-`P` and `M` were excluded because they are TREESAME to both parents.  `E`,
+`Q`, `P` and `M` were excluded because they are TREESAME to both parents.  `E`,
 `C` and `B` were all walked, but only `B` was !TREESAME, so the others
 do not appear.
 +
@@ -431,7 +435,7 @@ Along each parent, prune away commits that are not included
 themselves.  This results in
 +
 -----------------------------------------------------------------------
-	  .-A---M---N---O---P
+	  .-A---M---N---O---P---Q
 	 /     /   /   /   /
 	I     B   /   D   /
 	 \   /   /   /   /
@@ -441,7 +445,8 @@ themselves.  This results in
 Compare to '\--full-history' without rewriting above.  Note that `E`
 was pruned away because it is TREESAME, but the parent list of P was
 rewritten to contain `E`'s parent `I`.  The same happened for `C` and
-`N`.  Note also that `P` was included despite being TREESAME.
+`N`, and `X`, `Y` and `Q`.  Note also that `P` and `Q` were included despite
+being TREESAME.
 
 In addition to the above settings, you can change whether TREESAME
 affects inclusion:
@@ -471,9 +476,9 @@ history according to the following rules:
 * Set `C'` to `C`.
 +
 * Replace each parent `P` of `C'` with its simplification `P'`.  In
-  the process, drop parents that are ancestors of other parents, and
-  remove duplicates, but take care to never drop all parents that
-  we are TREESAME to.
+  the process, drop parents that are ancestors of other parents or that are
+  root commits TREESAME to an empty tree, and remove duplicates, but take care
+  to never drop all parents that we are TREESAME to.
 +
 * If after this parent rewriting, `C'` is a root or merge commit (has
   zero or >1 parents), a boundary commit, or !TREESAME, it remains.
@@ -491,7 +496,7 @@ The effect of this is best shown by way of comparing to
 	  `---------'
 -----------------------------------------------------------------------
 +
-Note the major differences in `N` and `P` over '--full-history':
+Note the major differences in `N`, `P` and `Q` over '--full-history':
 +
 --
 * `N`'s parent list had `I` removed, because it is an ancestor of the
@@ -499,6 +504,10 @@ Note the major differences in `N` and `P` over '--full-history':
 +
 * `P`'s parent list similarly had `I` removed.  `P` was then
   removed completely, because it had one parent and is TREESAME.
++
+* `Q`'s parent list had `Y` simplified to `X`. `X` was then removed, because it
+  was a TREESAME root. `Q` was then removed completely, because it had one
+  parent and is TREESAME.
 --
 
 Finally, there is a fifth simplification mode available:
diff --git a/revision.c b/revision.c
index 4e27c9a..67608e0 100644
--- a/revision.c
+++ b/revision.c
@@ -2102,6 +2102,22 @@ static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
 	return marked;
 }
 
+static int mark_treesame_root_parents(struct rev_info *revs, struct commit *commit)
+{
+	struct commit_list *p;
+	int marked = 0;
+
+	for (p = commit->parents; p; p = p->next) {
+		struct commit *parent = p->item;
+		if (!parent->parents && (parent->object.flags & TREESAME)) {
+			parent->object.flags |= TMP_MARK;
+			marked++;
+		}
+	}
+
+	return marked;
+}
+
 static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
 {
 	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
@@ -2224,10 +2240,18 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
 	 *     /    /		o: a commit that touches the paths;
 	 * ---o----'
 	 *
-	 * Detect and simplify this case.
+	 * Further, a merge of an independent branch that doesn't
+	 * touch the path will reduce to a treesame root parent:
+	 *
+	 *  ----o----X		X: the commit we are looking at;
+	 *          /		o: a commit that touches the paths;
+	 *         r		r: a root commit not touching the paths
+	 *
+	 * Detect and simplify both cases.
 	 */
 	if (1 < cnt) {
 		int marked = mark_redundant_parents(revs, commit);
+		marked += mark_treesame_root_parents(revs, commit);
 		if (marked)
 			remove_marked_parents(revs, commit);
 	}
diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh
index 4e55872..57ce239 100755
--- a/t/t6012-rev-list-simplify.sh
+++ b/t/t6012-rev-list-simplify.sh
@@ -110,7 +110,7 @@ check_result 'L K J I H G F E D C B A' --full-history
 check_result 'K I H E C B A' --full-history -- file
 check_result 'K I H E C B A' --full-history --topo-order -- file
 check_result 'K I H E C B A' --full-history --date-order -- file
-check_outcome failure 'I E C B A' --simplify-merges -- file
+check_result 'I E C B A' --simplify-merges -- file
 check_result 'I B A' -- file
 check_result 'I B A' --topo-order -- file
 check_result 'H' --first-parent -- another-file
-- 
1.8.2.1.632.gd2b1879

Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> Historically TREESAME was set on a commit if it was TREESAME to _any_ of
> its parents. This is not optimal, as such a merge could still be worth
> showing, particularly if it is an odd "-s ours" merge that (possibly
> accidentally) dropped a change.

"... and with options like --full-history or --simplify-merges are
used to get more complete history", I think.  "git log path" without
these options is a tool to get one version of simplified history
that explains the end result, and by definition, the side branch
merged by "-s ours" did _not_ contribute anything to the end result.

> And the problem is further compounded by
> the fact that simplify_merges could drop the actual parent that a commit
> was TREESAME to, leaving it as a normal commit marked TREESAME that
> isn't actually TREESAME to its remaining parent.
>
> This commit redefines TREESAME to be true only if a commit is TREESAME to
> _all_ of its parents. This doesn't affect either the default
> simplify_history behaviour (because partially TREESAME merges are turned
> into normal commits), or full-history with parent rewriting (because all
> merges are output). But it does affect other modes.

Yes.

> It also modifies simplify_merges to recalculate TREESAME after removing
> a parent. This is achieved by storing per-parent TREESAME flags on the
> initial scan, so the combined flag can be easily recomputed.

This is a very deep core part of the system, so let me summon/cc
Linus for an extra set of eyes.

> Signed-off-by: Kevin Bracey <kevin@bracey.fi>
> ---
>  Documentation/rev-list-options.txt |   2 +-
>  revision.c                         | 220 ++++++++++++++++++++++++++++++++-----
>  revision.h                         |   1 +
>  3 files changed, 192 insertions(+), 31 deletions(-)
>
> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 3bdbf5e..380db48 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -413,7 +413,7 @@ parent lines.
>  	I  A  B  N  D  O
>  -----------------------------------------------------------------------
>  +
> -`P` and `M` were excluded because they are TREESAME to a parent.  `E`,
> +`P` and `M` were excluded because they are TREESAME to both parents.  `E`,
>  `C` and `B` were all walked, but only `B` was !TREESAME, so the others
>  do not appear.
>  +
> diff --git a/revision.c b/revision.c
> index a67b615..176eb7b 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -429,10 +429,85 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)
>  	return retval >= 0 && (tree_difference == REV_TREE_SAME);
>  }
>  
> +struct treesame_state {
> +	unsigned int nparents;
> +	unsigned char treesame[FLEX_ARRAY];
> +};
> +
> +static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit)
> +{
> +	unsigned n = commit_list_count(commit->parents);
> +	struct treesame_state *st = xcalloc(1, sizeof(*st) + n);
> +	st->nparents = n;
> +	add_decoration(&revs->treesame, &commit->object, st);
> +	return st;
> +}
> +
> +static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned parent)
> +{
> +	struct treesame_state *st = lookup_decoration(&revs->treesame, &commit->object);
> +	int old_same;
> +
> +	if (!st || parent >= st->nparents)
> +		die("compact_treesame %u", parent);
> +
> +	/* Can be useful to indicate sameness of removed parent */
> +	old_same = st->treesame[parent];

(mental note) "Can" may refer to the fact that this value is not yet
used in this series; my gut feeling is that returning old value is a
good API design even if there is no current user.

> +	memmove(st->treesame + parent,
> +		st->treesame + parent + 1,
> +		st->nparents - parent - 1);
> +
> +	/* If we've just become a non-merge commit, update TREESAME

(style) "/*" occupies its own line.

> +	 * immediately, in case we trigger an early-exit optimisation.
> +	 * (Note that there may be a mismatch between commit->parents and the
> +	 * treesame_state at this stage, as we may be in mid-rewrite).
> +	 * If still a merge, defer update until update_treesame().
> +	 */
> +	switch (--st->nparents) {
> +	case 0:
> +		if (rev_same_tree_as_empty(revs, commit))
> +			commit->object.flags |= TREESAME;
> +		else
> +			commit->object.flags &= ~TREESAME;
> +		break;
> +	case 1:
> +		if (st->treesame[0] && revs->dense)
> +			commit->object.flags |= TREESAME;
> +		else
> +			commit->object.flags &= ~TREESAME;
> +		break;
> +	}

Do we want to discard the decoration data when the commit becomes a
non-merge?

> +	return old_same;
> +}

(mental note) compact_treesame() is not to "compact" after
everything is done, but as we remove one parent we call it to remove
the treesame[] record for that parent.  A commit can only lose parents
and never gain a new one, so we will never have to reallocate flex
array part.

> +static unsigned update_treesame(struct rev_info *revs, struct commit *commit)
> +{
> +	/* If 0 or 1 parents, TREESAME should be valid already */
> +	if (commit->parents && commit->parents->next) {
> +		int n = 0;

"compact" counted parents from 0 upwards with "unsigned", here it is
"int". It wouldn't make practical difference (nobody will create a
merge of 2 billion side branches), but we may want to be consistent.

> +		struct treesame_state *st;
> +
> +		st = lookup_decoration(&revs->treesame, &commit->object);
> +		if (!st) die("update_treesame");

(style) put this on two lines.

> +		commit->object.flags |= TREESAME;
> +		for (n = 0; n < st->nparents; n++) {
> +			if (!st->treesame[n]) {
> +				commit->object.flags &= ~TREESAME;
> +				break;
> +			}
> +		}

Can a commit that earlier was marked as TREESAME become not TREESAME?
Wouldn't simplification only increase sameness, never decrease?

> +	}
> +
> +	return commit->object.flags & TREESAME;
> +}
> +
>  static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>  {
>  	struct commit_list **pp, *parent;
> -	int tree_changed = 0, tree_same = 0, nth_parent = 0;
> +	struct treesame_state *ts = NULL;
> +	int tree_changed = 0, nth_parent = 0;
>  
>  	/*
>  	 * If we don't do pruning, everything is interesting
> @@ -456,25 +531,38 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>  	if (!revs->dense && !commit->parents->next)
>  		return;
>  
> -	pp = &commit->parents;
> -	while ((parent = *pp) != NULL) {
> +	for (pp = &commit->parents;
> +	     (parent = *pp) != NULL;
> +	     pp = &parent->next, nth_parent++) {

I see the reason to change from while to for is because you wanted
to count, and I think it makes sense; but it is more readable to
initialise the counter here, too, if that is the case. I.e.

	for (pp = &commit->parents, nth_parent = 0;
	     !(parent = *pp);
	     pp = &parent->next, nth_parent++) {

>  		struct commit *p = parent->item;
>  
> +		if (nth_parent == 1) {
> +			/*
> +			 * Do not compare with later parents when we care only about
> +			 * the first parent chain, in order to avoid derailing the
> +			 * traversal to follow a side branch that brought everything
> +			 * in the path we are limited to by the pathspec.
> +			 */
> +			if (revs->first_parent_only)
> +				break;
> +			/*
> +			 * If this is going to remain a merge, and it's
> +			 * interesting, remember per-parent treesame for
> +			 * simplify_merges().
> +			 */
> +			if (revs->simplify_merges && !(p->object.flags & UNINTERESTING)) {
> +				ts = initialise_treesame(revs, commit);
> +				if (!tree_changed)
> +					ts->treesame[0] = 1;

Have we made any two tree comparison at this point to set this one?
Ahh, this is tricky.  You do this in the _second_ iteration of the
loop, so tree_changed here is from inspecting the first parent, not
the one we are looking at (i.e. *p).

> +

(style) unnecessary new blank line?

> +			}
> +		}
>  		if (parse_commit(p) < 0)
>  			die("cannot simplify commit %s (because of %s)",
>  			    sha1_to_hex(commit->object.sha1),
>  			    sha1_to_hex(p->object.sha1));
>  		switch (rev_compare_tree(revs, p, commit)) {
>  		case REV_TREE_SAME:
> -			tree_same = 1;
>  			if (!revs->simplify_history || (p->object.flags & UNINTERESTING)) {
>  				/* Even if a merge with an uninteresting
>  				 * side branch brought the entire change
> @@ -482,7 +570,8 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>  				 * to lose the other branches of this
>  				 * merge, so we just keep going.
>  				 */
> -				pp = &parent->next;
> +				if (ts)
> +					ts->treesame[nth_parent] = 1;

Again, tricky but correct. ts->treesame[0] is filled during the
second iteration above, and the same iteration fills ts-tree>same[1]
here.

I am starting to like this code ;-).

>  				continue;
>  			}
>  			parent->next = NULL;
> @@ -511,12 +600,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
>  		case REV_TREE_OLD:
>  		case REV_TREE_DIFFERENT:
>  			tree_changed = 1;
> -			pp = &parent->next;
>  			continue;
>  		}
>  		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
>  	}
> -	if (tree_changed && !tree_same)
> +	if (tree_changed)
>  		return;
>  	commit->object.flags |= TREESAME;
>  }
> @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li
>  	 * NEEDSWORK: decide if we want to remove parents that are
>  	 * not marked with TMP_MARK from commit->parents for commits
>  	 * in the resulting list.  We may not want to do that, though.
> +	 *
> +	 * Maybe it should be considered if we are TREESAME to such
> +	 * parents - now possible with stored per-parent flags.
>  	 */

Hmm, that is certainly a thought.

> @@ -1930,28 +2021,32 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi
>  	l->next = add_decoration(&revs->children, &parent->object, l);
>  }
>  
> -static int remove_duplicate_parents(struct commit *commit)
> +static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit)
>  {
> +	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
>  	struct commit_list **pp, *p;
>  	int surviving_parents;
>  
>  	/* Examine existing parents while marking ones we have seen... */
>  	pp = &commit->parents;
> +	surviving_parents = 0;
>  	while ((p = *pp) != NULL) {
>  		struct commit *parent = p->item;
>  		if (parent->object.flags & TMP_MARK) {
>  			*pp = p->next;
> +			if (ts)
> +				compact_treesame(revs, commit, surviving_parents);
>  			continue;
>  		}
>  		parent->object.flags |= TMP_MARK;
> +		surviving_parents++;
>  		pp = &p->next;
>  	}
> -	/* count them while clearing the temporary mark */
> -	surviving_parents = 0;
> +	/* clear the temporary mark */
>  	for (p = commit->parents; p; p = p->next) {
>  		p->item->object.flags &= ~TMP_MARK;
> -		surviving_parents++;
>  	}
> +	/* no update_treesame() - removing duplicates can't affect TREESAME */
>  	return surviving_parents;
>  }

OK.

> @@ -1971,6 +2066,70 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,
>  	return st;
>  }
>  
> +static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
> +{
> +	struct commit_list *h = reduce_heads(commit->parents);
> +	int i = 0, marked = 0;
> +	struct commit_list *po, *pn;
> +
> +	/* Want these for sanity only */
> +	int orig_cnt = commit_list_count(commit->parents);
> +	int cnt = commit_list_count(h);
> +
> +	/* Not ready to remove items yet, just mark them for now, based

(same style on "/*")

> +	 * on the output of reduce_heads(). reduce_heads outputs the reduced
> +	 * set in its original order, so this isn't too hard.
> +	 */
> +	po = commit->parents;
> +	pn = h;
> +	while (po) {
> +		if (pn && po->item == pn->item) {
> +			pn=pn->next;

(style) SPs before and after '='.

> +			i++;
> +		}
> +		else {
> +			po->item->object.flags |= TMP_MARK;
> +			marked++;
> +		}
> +		po=po->next;
> +	}
> +
> +	if (i != cnt || cnt+marked != orig_cnt)
> +		die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked);
> +
> +	free_commit_list(h);
> +
> +	return marked;
> +}
> +
> +static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
> +{
> +	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
> +	struct commit_list **pp, *p;
> +	int n, removed = 0;
> +
> +	pp = &commit->parents;
> +	n = 0;
> +	while ((p = *pp) != NULL) {
> +		struct commit *parent = p->item;
> +		if (parent->object.flags & TMP_MARK) {
> +			parent->object.flags &= ~TMP_MARK;
> +			compact_treesame(revs, commit, n);
> +			*pp = p->next;
> +			free(p);
> +			removed++;
> +			continue;
> +		}
> +		pp = &p->next;
> +		n++;
> +	}
> +
> +	if (removed)
> +		update_treesame(revs, commit);
> +
> +	return removed;
> +}

OK, even though the use of TMP_MARK (meant to be very localized)
across two functions feel somewhat yucky, they are file scope
statics next to each other and hopefully are called back to back.

>  static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail)
>  {
>  	struct commit_list *p;
> @@ -2015,7 +2174,9 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
>  	}
>  
>  	/*
> -	 * Rewrite our list of parents.
> +	 * Rewrite our list of parents. Note that this cannot
> +	 * affect our TREESAME flags in anyway - a commit is
> +	 * always TREESAME to its simplification.
>  	 */
>  	for (p = commit->parents; p; p = p->next) {
>  		pst = locate_simplify_state(revs, p->item);
> @@ -2027,31 +2188,30 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
>  	if (revs->first_parent_only)
>  		cnt = 1;
>  	else
> -		cnt = remove_duplicate_parents(commit);
> +		cnt = remove_duplicate_parents(revs, commit);
>  
>  	/*
>  	 * It is possible that we are a merge and one side branch
>  	 * does not have any commit that touches the given paths;
> -	 * in such a case, the immediate parents will be rewritten
> -	 * to different commits.
> +	 * in such a case, the immediate parent from that branch
> +	 * will be rewritten to be the merge base.
>  	 *
>  	 *      o----X		X: the commit we are looking at;
>  	 *     /    /		o: a commit that touches the paths;
>  	 * ---o----'
>  	 *
> -	 * Further reduce the parents by removing redundant parents.
> +	 * Detect and simplify this case.
>  	 */
>  	if (1 < cnt) {
> -		struct commit_list *h = reduce_heads(commit->parents);
> -		cnt = commit_list_count(h);
> -		free_commit_list(commit->parents);
> -		commit->parents = h;
> +		int marked = mark_redundant_parents(revs, commit);
> +		if (marked)
> +			remove_marked_parents(revs, commit);
>  	}

OK.

>  	/*
>  	 * A commit simplifies to itself if it is a root, if it is
>  	 * UNINTERESTING, if it touches the given paths, or if it is a
> -	 * merge and its parents simplifies to more than one commits
> +	 * merge and its parents simplify to more than one commit
>  	 * (the first two cases are already handled at the beginning of
>  	 * this function).
>  	 *
> @@ -2218,7 +2378,7 @@ static int rewrite_parents(struct rev_info *revs, struct commit *commit)
>  		}
>  		pp = &parent->next;
>  	}
> -	remove_duplicate_parents(commit);
> +	remove_duplicate_parents(revs, commit);
>  	return 0;
>  }
>  
> diff --git a/revision.h b/revision.h
> index 01bd2b7..1abe57b 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -167,6 +167,7 @@ struct rev_info {
>  	struct reflog_walk_info *reflog_info;
>  	struct decoration children;
>  	struct decoration merge_simplification;
> +	struct decoration treesame;
>  
>  	/* notes-specific options: which refs to show */
>  	struct display_notes_opt notes_opt;

Nicely done.

Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[David Aguilar]

On Sat, Apr 27, 2013 at 3:36 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Kevin Bracey <kevin@bracey.fi> writes:
>> diff --git a/revision.c b/revision.c
>> index a67b615..176eb7b 100644
>> --- a/revision.c
>> +++ b/revision.c
>> @@ -1971,6 +2066,70 @@ static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs,
>>       return st;
>>  }
>>
>> +static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
>> +{
>> +     struct commit_list *h = reduce_heads(commit->parents);
>> +     int i = 0, marked = 0;
>> +     struct commit_list *po, *pn;
>> +
>> +     /* Want these for sanity only */
>> +     int orig_cnt = commit_list_count(commit->parents);
>> +     int cnt = commit_list_count(h);
>> +
>> +     /* Not ready to remove items yet, just mark them for now, based
>
> (same style on "/*")
>
>> +      * on the output of reduce_heads(). reduce_heads outputs the reduced
>> +      * set in its original order, so this isn't too hard.
>> +      */
>> +     po = commit->parents;
>> +     pn = h;
>> +     while (po) {
>> +             if (pn && po->item == pn->item) {
>> +                     pn=pn->next;
>
> (style) SPs before and after '='.
>
>> +                     i++;
>> +             }
>> +             else {

(style) cuddle this } else { block.
--
David

Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[Kevin Bracey]

On 28/04/2013 01:36, Junio C Hamano wrote:
> Kevin Bracey <kevin@bracey.fi> writes:
>
>> Historically TREESAME was set on a commit if it was TREESAME to _any_ of
>> its parents. This is not optimal, as such a merge could still be worth
>> showing, particularly if it is an odd "-s ours" merge that (possibly
>> accidentally) dropped a change.
> "... and with options like --full-history or --simplify-merges are
> used to get more complete history", I think.  "git log path" without
> these options is a tool to get one version of simplified history
> that explains the end result, and by definition, the side branch
> merged by "-s ours" did _not_ contribute anything to the end result.

Yeah, I'm not happy with this commit message - I knocked it up 
separately from my first pass, which I didn't have to hand. Next version 
will combine it with the original, which better distinguished the 
default mode, and specifically addressed the "--full-history -S" search 
problem.

That's key - that I really want such searches to be able to track the 
entire life of a change on a side branch, not potentially showing just 
its birth as now, but also always including any ultimate merge death. (I 
think that we may be able to refine --ancestry-path to give an even 
tighter pinpoint, but --full-history should definitely include the 
information, as per its name).

>
> Do we want to discard the decoration data when the commit becomes a
> non-merge?

Would seem reasonable, and would also help make concrete why we update 
TREESAME immediately, and not in update_treesame(), but I didn't spot a 
mechanism to discard decoration. I'll recheck.

>
>> +		commit->object.flags |= TREESAME;
>> +		for (n = 0; n < st->nparents; n++) {
>> +			if (!st->treesame[n]) {
>> +				commit->object.flags &= ~TREESAME;
>> +				break;
>> +			}
>> +		}
> Can a commit that earlier was marked as TREESAME become not TREESAME?
> Wouldn't simplification only increase sameness, never decrease?

That's true - I paid attention to that earlier when it really mattered 
due to the cost of recalculating it with try_to_simplify_commit(). Not 
sure that it matters so much any more, and I don't see how we can use 
that information to change this "scan for !treesame" loop.

I could insert an "if (!commit->object.flags & TREESAME)" test to skip 
the entire update. I'd be inclined to do that as the caller of 
update_treesame(). I think update_treesame() itself should be 
general-purpose without assumptions about what changes have been made, 
so it's a pure treesame[]->TREESAME calculation, without TREESAME as an 
input.

(Aside - just occurred to me we could swap the loop for 
"strlen(st->treesame) == st->nparents", if we kept a zero terminator in 
the array. Maybe a bit too smart-ass?)


>
>> +	for (pp = &commit->parents;
>> +	     (parent = *pp) != NULL;
>> +	     pp = &parent->next, nth_parent++) {
> I see the reason to change from while to for is because you wanted
> to count, and I think it makes sense; but it is more readable to
> initialise the counter here, too, if that is the case. I.e.
>
> 	for (pp = &commit->parents, nth_parent = 0;
> 	     !(parent = *pp);
> 	     pp = &parent->next, nth_parent++) {

Agree on nth_parent, but  "!(parent = *pp)"  isn't "(parent = *pp) != 
NULL", mind. Did you mean "!!"? In which case I still prefer it my way.

>
> +				if (!tree_changed)
> +					ts->treesame[0] = 1;
> Have we made any two tree comparison at this point to set this one?
> Ahh, this is tricky.  You do this in the _second_ iteration of the
> loop, so tree_changed here is from inspecting the first parent, not
> the one we are looking at (i.e. *p).

Yes, this is the "we've reached our second iteration, so from now on 
we're dealing a merge" if {} block. I'll clarify this in the comment at 
the top, and note that we're populating the newly-allocated treesame[] 
from our first iteration.

>
>>   
>> @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *li
>>   	 * NEEDSWORK: decide if we want to remove parents that are
>>   	 * not marked with TMP_MARK from commit->parents for commits
>>   	 * in the resulting list.  We may not want to do that, though.
>> +	 *
>> +	 * Maybe it should be considered if we are TREESAME to such
>> +	 * parents - now possible with stored per-parent flags.
>>   	 */
> Hmm, that is certainly a thought.

My comment's wrong though. Reconsidering, what I think needs removing is 
actually off-ancestry parents that we are !TREESAME to, when we are 
TREESAME on the ancestry path.

I've realised while testing this that there's been one thing that's 
confused me repeatedly, and I think this comment was an example of it. 
The example in the rev-list-options manual is wrong.

           .-A---M---N---O---P
          /     /   /   /   /
         I     B   C   D   E
          \   /   /   /   /
           `-------------'

Contrary to the manual, merge P is !TREESAME to E (or I).  E's base is 
old enough that E isn't up-to-date w.r.t. "foo". Thus merge "P" is no 
longer TREESAME and does become subject to display with the new 
--full-history:

    I  A  B  N  D  O  P

I believe this is correct, because P is a merge that determined the fate 
of "foo", so merits --full-history inspection. (--simplify-merges 
obviously knocks P back out again: --simplify-merges becomes more 
important if --full-history gets fuller).

Given this error, and this change, I think this example may want a 
slight rethink. Do we want a proper "messing with other paths but 
TREESAME merge" example? Say if E's parent was O, P would not be 
TREESAME and not included in --full-history.

>
> OK, even though the use of TMP_MARK (meant to be very localized)
> across two functions feel somewhat yucky, they are file scope
> statics next to each other and hopefully are called back to back.

Well, by the end of the series you've got two functions setting it, in 
preparation for later input to this function. And what's the upper bound 
on complexity of functions that may want to mark removal? They may need 
TMP_MARK to do the job. I'm beginning to think that it should be a 
dedicated REMOVE bit.

Kevin

Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

>> Do we want to discard the decoration data when the commit becomes a
>> non-merge?
>
> Would seem reasonable, and would also help make concrete why we update
> TREESAME immediately, and not in update_treesame(), but I didn't spot
> a mechanism to discard decoration. I'll recheck.

What I meant was a simple "free(it)" and a call to add_decoration()
to register a NULL for the object whose treesame[] we no longer
need.

> I could insert an "if (!commit->object.flags & TREESAME)" test to skip
> the entire update. I'd be inclined to do that as the caller of
> update_treesame(). I think update_treesame() itself should be
> general-purpose without assumptions about what changes have been made,
> so it's a pure treesame[]->TREESAME calculation, without TREESAME as
> an input.

Makes sense.

> (Aside - just occurred to me we could swap the loop for
> "strlen(st->treesame) == st->nparents", if we kept a zero terminator
> in the array. Maybe a bit too smart-ass?)

Probably ;-)

>>> +	for (pp = &commit->parents;
>>> +	     (parent = *pp) != NULL;
>>> +	     pp = &parent->next, nth_parent++) {
>> I see the reason to change from while to for is because you wanted
>> to count, and I think it makes sense; but it is more readable to
>> initialise the counter here, too, if that is the case. I.e.
>>
>> 	for (pp = &commit->parents, nth_parent = 0;
>> 	     !(parent = *pp);
>> 	     pp = &parent->next, nth_parent++) {
>
> Agree on nth_parent, but  "!(parent = *pp)"  isn't "(parent = *pp) !=
> NULL", mind. Did you mean "!!"? In which case I still prefer it my
> way.

Droppage of NULL check was a typo.  I only meant A part of for(A;B;C).

>>>   @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct
>>> commit_list *bottom, struct commit_list *li
>>>   	 * NEEDSWORK: decide if we want to remove parents that are
>>>   	 * not marked with TMP_MARK from commit->parents for commits
>>>   	 * in the resulting list.  We may not want to do that, though.
>>> +	 *
>>> +	 * Maybe it should be considered if we are TREESAME to such
>>> +	 * parents - now possible with stored per-parent flags.
>>>   	 */
>> Hmm, that is certainly a thought.
>
> My comment's wrong though. Reconsidering, what I think needs removing
> is actually off-ancestry parents that we are !TREESAME to, when we are
> TREESAME on the ancestry path.

I thought I read you meant exactly that, i.e. !TREESAME, but now I
re-read what is quoted, you did say "we are TREESAME" ;-).  I think
I agree with you that we do not want any side branch that is not on
the ancestry path we are interested in to affect the sameness
assigned to the merge commit.

> I've realised while testing this that there's been one thing that's
> confused me repeatedly, and I think this comment was an example of
> it. The example in the rev-list-options manual is wrong.
>
>                   *   *
>           .-A---M---N---O---P
>          /*    /   /*  /*  /*
>         I     B   C   D   E
>          \   /*  /   /*  /
>           `-------------'

I've added '*' next to each arc between a commit-pair whose contents
at 'foo' are different to the illustration, following the set-up the
manual describes.  E is the same as I for 'foo' and P would resolve
'foo' to be the same as O.

> Contrary to the manual, merge P is !TREESAME to E (or I).  E's base is
> old enough that E isn't up-to-date w.r.t. "foo". Thus merge "P" is no
> longer TREESAME and does become subject to display with the new
> --full-history:
>
>    I  A  B  N  D  O  P

Assuming N's parents-list is rewritten to be A and B, this sounds
sensible.

> I believe this is correct, because P is a merge that determined the
> fate of "foo", so merits --full-history inspection. (--simplify-merges
> obviously knocks P back out again: --simplify-merges becomes more
> important if --full-history gets fuller).

E simplifies to I which is already an ancestor of O and is redundant
when inspecting P, hence P becomes a single-parent child of O and
further simplifies to O because it has the same 'foo'.  Makes sense.

> Given this error, and this change, I think this example may want a
> slight rethink. Do we want a proper "messing with other paths but
> TREESAME merge" example? Say if E's parent was O, P would not be
> TREESAME and not included in --full-history.

I am not sure if I follow your last sentence.   

Do you mean this topology, where E's sole parent is O, i.e.

              E
             / \
	N---O---P
           /*
          D

and E does not change 'foo' from O?  Then P is TREESAME to all its
parents and would not have to appear in the full history for the
same reason M does not appear in your earlier IABNDOP output, no?

>> OK, even though the use of TMP_MARK (meant to be very localized)
>> across two functions feel somewhat yucky, they are file scope
>> statics next to each other and hopefully are called back to back.
>
> Well, by the end of the series you've got two functions setting it, in
> preparation for later input to this function.

As long as "setting" and "using and then cleaning after done" are
localized enough so that nobody will be tempted to insert another
complex processing in between that might need TMP_MARK we should be
OK.

Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[Kevin Bracey]

On 28/04/2013 21:38, Junio C Hamano wrote:
>
>>>>    @@ -773,6 +861,9 @@ static void limit_to_ancestry(struct
>>>> commit_list *bottom, struct commit_list *li
>>>>    	 * NEEDSWORK: decide if we want to remove parents that are
>>>>    	 * not marked with TMP_MARK from commit->parents for commits
>>>>    	 * in the resulting list.  We may not want to do that, though.
>>>> +	 *
>>>> +	 * Maybe it should be considered if we are TREESAME to such
>>>> +	 * parents - now possible with stored per-parent flags.
>>>>    	 */
>>> Hmm, that is certainly a thought.
>> My comment's wrong though. Reconsidering, what I think needs removing
>> is actually off-ancestry parents that we are !TREESAME to, when we are
>> TREESAME on the ancestry path.
> I thought I read you meant exactly that, i.e. !TREESAME, but now I
> re-read what is quoted, you did say "we are TREESAME" ;-).  I think
> I agree with you that we do not want any side branch that is not on
> the ancestry path we are interested in to affect the sameness
> assigned to the merge commit.

I did a trial implementation of this in limit_to_ancestry(), and the 
result was lovely, but in the end I decided it's not actually the right 
place to do it. The logic is more general than that; this isn't just an 
ancestry-path issue, and I think "hiding" parents isn't the right way to 
go about it anyway.

To slightly generalise your own wording: I think the rule is "we do not 
want any side branch that is UNINTERESTING to affect the sameness 
assigned to the merge commit". I think that rule applies to all dense, 
pruned modes.

Having experimented with some of the annoyingly complex merge paths that 
originally prompted this series, it seems this rule makes a huge 
difference, and it's useful whether asking "--simplify-merges A..B 
<file>" or "--ancestry-path A..B <file>".

At present, either query will show lots of really boring merge commits 
of topic branches at the boundary, with 1 INTERESTING parent that 
they're TREESAME too, and 1 UNINTERESTING parent that they may or may 
not be TREESAME to, depending on how old the base of that topic branch 
was. Most such commits are of no relevance to our history whatsoever. In 
the case of "--simplify-merges", the fact that they're UNINTERESTING 
actually _prevented_ their simplification - if it had been allowed to 
follow the UNINTERESTING path back further, it would have reached an 
ancestor, and been found redundant. So limiting the rev-list actually 
increases the number of merges shown.

We can lose all those boring commits with these two changes:

1) Previously TREESAME was defined as "this commit matches at least 1 
parent". My first patch changes it to "this commit matches all parents". 
It should be refined further to "this commit matches all INTERESTING 
parents, if it has any, else all (UNINTERESTING) parents". (Can we word 
that better?) Note that this fancy rule collapses to the same 
straightforward TREESAME check as ever for 0- or 1-parent commits.

2) simplify_merges currently will not simplify commits unless they have 
exactly 1 parent. That's not what we want. We only need to preserve 
commits that don't have exactly 1 INTERESTING parent.

Those 2 rules produce the desirable result: if we have a merge commit 
with exactly 1 INTERESTING parent it is TREESAME to, it is always 
simplified away - any other UNINTERESTING parents it may have did not 
affect our code, so we don't care about whether we were TREESAME to them 
or not, and as we don't want to see any of the UNINTERESTING parents 
themselves, the merge is not worth showing.

This makes a massive difference on some of my searches, reducing the 
total commits shown by a factor of 5 to 10, greatly improving the 
signal-to-noise ratio.

I'll put together a trial patch at the end of the next iteration of the 
series that implements this logic. I need to think a bit more - I think 
"get_commit_action" needs a similar INTERESTING check for merges too, to 
get the same sort of effect without relying on simplify_merges. Parent 
rewriting shouldn't necessitate keeping all merges - only merges with 2+ 
INTERESTING parents.

>>
>>                    *   *
>>            .-A---M---N---O---P
>>           /*    /   /*  /*  /*
>>          I     B   C   D   E
>>           \   /*  /   /*  /
>>            `-------------'
> I've added '*' next to each arc between a commit-pair whose contents
> at 'foo' are different to the illustration, following the set-up the
> manual describes.  E is the same as I for 'foo' and P would resolve
> 'foo' to be the same as O.

I think that sort of thing could be a useful patch to the docs.
>
>> Given this error, and this change, I think this example may want a
>> slight rethink. Do we want a proper "messing with other paths but
>> TREESAME merge" example? Say if E's parent was O, P would not be
>> TREESAME and not included in --full-history.
> I am not sure if I follow your last sentence.
>
> Do you mean this topology, where E's sole parent is O, i.e.
>
>                E
>               / \
> 	N---O---P
>             /*
>            D
>
> and E does not change 'foo' from O?  Then P is TREESAME to all its
> parents and would not have to appear in the full history for the
> same reason M does not appear in your earlier IABNDOP output, no?

That's the topology I was thinking of.  Yes, P is then "full-TREESAME" 
like M, but it's just a more typical example of a real merge and why 
TREESAMEness arises than M is.  M didn't appear in full-history because 
both parents made the same change to foo - indeed both parents were 
identical. Whereas P wouldn't appear because E is different, but changed 
something other than foo.

Kevin

Re: [RFC/PATCH 1/3] revision.c: tighten up TREESAME handling of merges

[Junio C Hamano]

Kevin Bracey <kevin@bracey.fi> writes:

> At present, either query will show lots of really boring merge commits
> of topic branches at the boundary, with 1 INTERESTING parent that
> they're TREESAME too, and 1 UNINTERESTING parent that they may or may
> not be TREESAME to, depending on how old the base of that topic branch
> was. Most such commits are of no relevance to our history
> whatsoever. In the case of "--simplify-merges", the fact that they're
> UNINTERESTING actually _prevented_ their simplification - if it had
> been allowed to follow the UNINTERESTING path back further, it would
> have reached an ancestor, and been found redundant. So limiting the
> rev-list actually increases the number of merges shown.
>
> We can lose all those boring commits with these two changes:
>
> 1) Previously TREESAME was defined as "this commit matches at least 1
> parent". My first patch changes it to "this commit matches all
> parents". It should be refined further to "this commit matches all
> INTERESTING parents, if it has any, else all (UNINTERESTING)
> parents". (Can we word that better?) Note that this fancy rule
> collapses to the same straightforward TREESAME check as ever for 0- or
> 1-parent commits.
>
> 2) simplify_merges currently will not simplify commits unless they
> have exactly 1 parent. That's not what we want. We only need to
> preserve commits that don't have exactly 1 INTERESTING parent.
>
> Those 2 rules produce the desirable result: if we have a merge commit
> with exactly 1 INTERESTING parent it is TREESAME to, it is always
> simplified away - any other UNINTERESTING parents it may have did not
> affect our code, so we don't care about whether we were TREESAME to
> them or not, and as we don't want to see any of the UNINTERESTING
> parents themselves, the merge is not worth showing.
>
> This makes a massive difference on some of my searches, reducing the
> total commits shown by a factor of 5 to 10, greatly improving the
> signal-to-noise ratio.
>
> I'll put together a trial patch at the end of the next iteration of
> the series that implements this logic. I need to think a bit more - I
> think "get_commit_action" needs a similar INTERESTING check for merges
> too, to get the same sort of effect without relying on
> simplify_merges. Parent rewriting shouldn't necessitate keeping all
> merges - only merges with 2+ INTERESTING parents.

Everything you wrote above makes tons of sense.

One small worry is how this new simplification interacts with the
first parent mode. For the purpose of showing the merge commit
itself, the second and subsequent parents are treated as "not
INTERESTING" in the above discussion, but that should not propagate
back to their parents like the normal UNINTERESTING-ness does.