Re: [RFC/PATCH 0/2] merge-base: add --merge-child option

[John Keeping <john@keeping.me.uk>]

On Sun, May 12, 2013 at 06:44:30PM +0300, Kevin Bracey wrote:
> On 11/05/2013 15:23, John Keeping wrote:
> > This is helpful when examining branches with disjoint roots, for example
> > because one is periodically merged into a subtree of the other.
> >
> >
> >
> >          $ git log --left-right F...E --not $(git merge-base --merge-child F E)
> >          < F
> >          > E
> >
> 
> Wouldn't "--left-right --ancestry-path F...E" do the job? I can't 
> immediately see how that differs.
> 
> Unfortunately, that syntax doesn't currently work - I just stumbled 
> across this problem, and my "history traversal refinements" series in pu 
> fixes it, somewhat incidentally to the main subject in there.

You're right (and I was wrong in my reply to Junio's parallel message)
ancestry path does seem to be what I want:

    $ git rev-list --left-right --count master...git-gui/master
    31959   5

    $ git rev-list --ancestry-path --left-right --count \
            master...git-gui/master
    2056    5

    $ git rev-list --ancestry-path --left-right --count \
            master...git-gui/master \
            --not $(git merge-base --all master git-gui/master)
    2056    5

However, this doesn't seem to make a difference to the time taken when I
add in --cherry-mark (which is why I was partially correct in the
parallel thread - it doesn't have the effect on cherry-mark that I want
it to):

    $ time git rev-list --ancestry-path --left-right --count --cherry-mark \
            origin/master...git-gui/master 
    2056    5       0

    real    0m32.266s
    user    0m31.522s
    sys     0m0.749s

    $ time git rev-list  --left-right --count --cherry-mark \
            origin/master...git-gui/master
    31959   5       0

    real    0m32.140s
    user    0m31.337s
    sys     0m0.807s

This seems to be caused by the code in revision.c::limit_list() which
does the cherry detection then limits to left/right and only then
applies the ancestry path.  I haven't looked further than that, but is
there any reason not to apply the ancestry path restriction before
looking for patch-identical commits?

> However, without that patch, the alternative way of expressing it:
> 
> "--left-right --ancestry path F E --not $(git merge-base --all F E)"
> 
> should still work. Unless --left-right is magic for "..."? If it is, 
> then my patch is more significant than I thought.

Yes, --left-right only applies to symmetric differences ("...").  But I
get the results above both on master and on pu.

> My series will also be better at optimising away D too, through a 
> combination of my and Junio's efforts. Try it out.
> 
> On this subject, is there any way to exclude a path from a log query? Is 
> there a "not" operator for paths? Might be another way of doing this - 
> disjoint histories probably have disjoint paths...

That relates to another idea I had about optimizing the detection of
patch-identical commits.  If the smaller side of a symmetric difference
is quite small (as it is likely to be if it's a topic branch), would it
be a good idea to calculate the set of paths touched by commits on that
side and then skip calculating the patch ID for any commits that touch
paths outside that set.  The tree comparison is a lot cheaper than doing
a diff on all of the files.