RFC: Merge-related plans

RFC: Merge-related plans

[Elijah Newren]

Hi everyone,

I have some merge-related plans (and work in progress) that I'd like
to get some feedback on in order to find what order would be best to
address things in, if there are special steps I should take while
approaching some of the bigger items, and even if folks disagree with
any of the plans.


Currently, I would like to:

A) Fix cases where directory rename detection does not work with
   rebase/am due to how they call merge-recursive.

   Notes: Could just wait for D & E to land before fixing.
   Alternatively, email RFC to list now explaining issues and how the
   fix has performance implications; poll for opinions on whether to
   fix before or after D.

B) Implement a remerge-diff ability (compare a merge commit to what an
   "automatic merge" would look like)[1].

   Notes: Possibly for cherry-picks and reverts too.  Depends on C &
   E.

C) Modify/extend how path-based and mode-based conflicts are
   communicated to the user.

   Notes: Particularly important as a mechanism for handling
   challenges[2] with implementing the remerge-diff ability.  Need to
   send RFC to list with ideas to get feedback.

D) Improve merge performance.

   Notes: Includes 4-5 specific optimizations[5], some of which I
   expect to be somewhat invasive and thus may make more sense to just
   make part of the new merge strategy implemented in E.  Biggest
   optimization depends on F.

E) Write a new merge strategy meant to replace merge-recursive.

   Notes: Suggested by Junio[3][4].  Depends on F & G.

F) Make file collision conflict types more consistent.

   Notes: Specifically, make rename/rename(2to1) & rename/add
   conflicts behave more like add/add[6][7].  Depends on part of G.
   Would prefer H to be accepted first.

G) Improve merge-related portion of testsuite.

   Notes: Intended to help test new merge strategy with more
   confidence.  Will include approximately a dozen edge and corner
   cases where merge-recursive currently falls short.  Started at [8];
   see also [9].

H) Miscellaneous code cleanups irritating me while working on other
   changes[10].


My current plan was to work roughly in reverse, from H to A.  Some questions:

  * Does any of this look objectionable?
  * Should I post RFC questions on A and C earlier?
  * Should I split D and G?  (Current plan was to keep D together, but
    split G into five short slightly inter-dependent topics)
  * E is kind of big.  Are there any specific things folks would like to see
    with how that is handled?


Thanks,
Elijah


[1] https://bugs.chromium.org/p/git/issues/detail?id=12 [remerge-diff]
[2] https://public-inbox.org/git/CABPp-BEsTOZ-tCvG1y5a0qPB8xJLLa0obyTU===mBgXC1jXgFA@mail.gmail.com/
    [remerge-diff challenges]
[3] https://public-inbox.org/git/xmqqd147kpdm.fsf@gitster.mtv.corp.google.com/
    [Ideal world merge strategy]
[4] https://public-inbox.org/git/xmqqk1ydkbx0.fsf@gitster.mtv.corp.google.com/
    [New strategy]
[5] Some of which are included in
    https://public-inbox.org/git/20171120221944.15431-1-newren@gmail.com/
    [perf improvements]
[6] https://public-inbox.org/git/CAPc5daVu8vv9RdGON8JiXEO3ycDVqQ38ySzZc-cpo+AQcAKXjA@mail.gmail.com/
    [discussion of add/add conflict resolution]
[7] https://public-inbox.org/git/20180305171125.22331-1-newren@gmail.com/
    [file collision consistency RFC series]
[8] https://public-inbox.org/git/20180524070439.6367-1-newren@gmail.com/
    [testcase cleanup]
[9] https://public-inbox.org/git/CABPp-BFc1OLYKzS5rauOehvEugPc0oGMJp-NMEAmVMW7QR=4Eg@mail.gmail.com/
    [weird corner cases]
[10] https://public-inbox.org/git/20180522004327.13085-1-newren@gmail.com/
     [code cleanups]

Re: RFC: Merge-related plans

[Stefan Beller]

On Mon, May 28, 2018 at 1:48 PM, Elijah Newren <newren@gmail.com> wrote:
> Hi everyone,
>
> I have some merge-related plans (and work in progress) that I'd like
> to get some feedback on in order to find what order would be best to
> address things in, if there are special steps I should take while
> approaching some of the bigger items, and even if folks disagree with
> any of the plans.
>
>
> Currently, I would like to:
>
> A) Fix cases where directory rename detection does not work with
>    rebase/am due to how they call merge-recursive.
>
>    Notes: Could just wait for D & E to land before fixing.
>    Alternatively, email RFC to list now explaining issues and how the
>    fix has performance implications; poll for opinions on whether to
>    fix before or after D.
>
> B) Implement a remerge-diff ability (compare a merge commit to what an
>    "automatic merge" would look like)[1].
>
>    Notes: Possibly for cherry-picks and reverts too.  Depends on C &
>    E.
>
> C) Modify/extend how path-based and mode-based conflicts are
>    communicated to the user.
>
>    Notes: Particularly important as a mechanism for handling
>    challenges[2] with implementing the remerge-diff ability.  Need to
>    send RFC to list with ideas to get feedback.
>
> D) Improve merge performance.
>
>    Notes: Includes 4-5 specific optimizations[5], some of which I
>    expect to be somewhat invasive and thus may make more sense to just
>    make part of the new merge strategy implemented in E.  Biggest
>    optimization depends on F.
>
> E) Write a new merge strategy meant to replace merge-recursive.
>
>    Notes: Suggested by Junio[3][4].  Depends on F & G.
>
> F) Make file collision conflict types more consistent.
>
>    Notes: Specifically, make rename/rename(2to1) & rename/add
>    conflicts behave more like add/add[6][7].  Depends on part of G.
>    Would prefer H to be accepted first.
>
> G) Improve merge-related portion of testsuite.
>
>    Notes: Intended to help test new merge strategy with more
>    confidence.  Will include approximately a dozen edge and corner
>    cases where merge-recursive currently falls short.  Started at [8];
>    see also [9].

Most items forward-reference "Depends on (<later letter>) up to here;
(H) seems independent, but might be a good first start.
(G) [8] is queued as origin/en/merge-recursive-tests, or do you mean
to expand (G) into a mini-framework of merge-testing? i.e. run the
mini test framework multiple times, each using a different
merge strategy, similar to submodule tests, e.g. see
t/lib-submodule-update.sh and one of its users, t1013.


> H) Miscellaneous code cleanups irritating me while working on other
>    changes[10].
>
>
> My current plan was to work roughly in reverse, from H to A.  Some questions:
>
>   * Does any of this look objectionable?

Going in order A-H seems slightly out-of-order to me, I'd think (H) and (G)
would go first;

(B) sounds like an independent feature, which could go in parallel?

>   * Should I post RFC questions on A and C earlier?

I would think so, it is easier to give feedback on code, I would think.

>   * Should I split D and G?  (Current plan was to keep D together, but
>     split G into five short slightly inter-dependent topics)

I would have expected to have tests (G) as a companion of (A) or (C)
rather than (D), as performance improvements would keep the test suite
unchanged?

>   * E is kind of big.  Are there any specific things folks would like to see
>     with how that is handled?

How much abstraction can be done ahead of time such that there is an
interface/API where you just plug in a new merge strategy and do not
need to duplicate a lot of code/tests?

Stefan

Re: RFC: Merge-related plans

[Elijah Newren]

Hi Stefan,

On Tue, May 29, 2018 at 11:19 AM, Stefan Beller <sbeller@google.com> wrote:
> On Mon, May 28, 2018 at 1:48 PM, Elijah Newren <newren@gmail.com> wrote:
>> Currently, I would like to:
>>
>> A) Fix cases where directory rename detection does not work with
>>    rebase/am due to how they call merge-recursive.
>>
>>    Notes: Could just wait for D & E to land before fixing.
>>    Alternatively, email RFC to list now explaining issues and how the
>>    fix has performance implications; poll for opinions on whether to
>>    fix before or after D.
>>
>> B) Implement a remerge-diff ability (compare a merge commit to what an
>>    "automatic merge" would look like)[1].
>>
>>    Notes: Possibly for cherry-picks and reverts too.  Depends on C &
>>    E.
>>
>> C) Modify/extend how path-based and mode-based conflicts are
>>    communicated to the user.
>>
>>    Notes: Particularly important as a mechanism for handling
>>    challenges[2] with implementing the remerge-diff ability.  Need to
>>    send RFC to list with ideas to get feedback.
>>
>> D) Improve merge performance.
>>
>>    Notes: Includes 4-5 specific optimizations[5], some of which I
>>    expect to be somewhat invasive and thus may make more sense to just
>>    make part of the new merge strategy implemented in E.  Biggest
>>    optimization depends on F.
>>
>> E) Write a new merge strategy meant to replace merge-recursive.
>>
>>    Notes: Suggested by Junio[3][4].  Depends on F & G.
>>
>> F) Make file collision conflict types more consistent.
>>
>>    Notes: Specifically, make rename/rename(2to1) & rename/add
>>    conflicts behave more like add/add[6][7].  Depends on part of G.
>>    Would prefer H to be accepted first.
>>
>> G) Improve merge-related portion of testsuite.
>>
>>    Notes: Intended to help test new merge strategy with more
>>    confidence.  Will include approximately a dozen edge and corner
>>    cases where merge-recursive currently falls short.  Started at [8];
>>    see also [9].
>
> Most items forward-reference "Depends on (<later letter>) up to here;
> (H) seems independent, but might be a good first start.
> (G) [8] is queued as origin/en/merge-recursive-tests, or do you mean
> to expand (G) into a mini-framework of merge-testing? i.e. run the
> mini test framework multiple times, each using a different
> merge strategy, similar to submodule tests, e.g. see
> t/lib-submodule-update.sh and one of its users, t1013.

Sorry, I should have been more clear about G.
en/merge-recursive-tests is not G, it's just a preparation topic for
it (or, alternatively, the first of a few topics for G).  In short,
the idea for G was missing coverage of existing functionality for
merge-recursive.

In more detail...

The idea for G was that, if possible, I wanted to avoid a repeat of
the problems directory rename detection caused Junio where he had to
revert it from master and worried about mis-merges.  That could have
been avoided if we had additional tests in the testsuite covering the
already-up-to-date check, making me wonder if there were other
important cases where merge-recursive lacked coverage.  Rather than
finding untested cases which merge-recursive handles correctly, my
investigation mostly yielded additional testcases where
merge-recursive falls down, including:
  * about 3 different rename cases (non-recursive), one of which was
reported previously but isn't in the testsuite
  * about 4 different issues with submodules (non-recursive) that I
don't think are represented in the testsuite (a couple of which I
mentioned in an email to you on the list last year but never created
testcases for)
  * about 6 different issues with special types and/or mode conflicts
(recursive only)
  * a few additional tests, commentary, and an alternate idea for
improving directory/file conflict handling

>> H) Miscellaneous code cleanups irritating me while working on other
>>    changes[10].
>>
>>
>> My current plan was to work roughly in reverse, from H to A.  Some questions:
>>
>>   * Does any of this look objectionable?
>
> Going in order A-H seems slightly out-of-order to me, I'd think (H) and (G)
> would go first;
>
> (B) sounds like an independent feature, which could go in parallel?

B may sound like an independent feature, but it needs a merge
algorithm that doesn't mess with the working tree so it depends pretty
strongly on E.

>>   * Should I post RFC questions on A and C earlier?
>
> I would think so, it is easier to give feedback on code, I would think.

If the idea is to give feedback on *code* rather than just
ideas/tradeoffs/pinpointing-buggy-lines, then it sounds like you're
actually suggesting posting the RFC later rather than earlier?

Also, the bigger question for me wasn't so much "should I ask the list
about these changes?" before making them, but rather: Do folks want me
to bring these things up before I work on D & E -- even if I end up
not getting back to incorporating their answers for months until D & E
are completed and merged?

>>   * Should I split D and G?  (Current plan was to keep D together, but
>>     split G into five short slightly inter-dependent topics)
>
> I would have expected to have tests (G) as a companion of (A) or (C)
> rather than (D), as performance improvements would keep the test suite
> unchanged?

Let me re-phrase: D and G are completely independent series, both of
which happen to be divisible.  Should either of them be split?

More background: D is only a handful of commits, so far; the main
reason to split it is to allow some of it to go first (maybe even
before G or H).  The downside is introducing extra churn and risk in
merge-recursive, when I'm planning to rewrite it soon anyway.  I was
trying to minimize merge-recursive changes, other than trying to make
sure that the new merge strategy and merge-recursive will give
identical results (modulo maybe fixing a few extra corner cases and
running faster).  Basically, I wanted it to be really easy to compare
old and new strategies, but otherwise wanted to leave merge-recursive
mostly alone.  It's not entirely clear how quickly I'll find time to
work on all of this, though, so maybe just-wait-for-the-rewrite is not
the right prioritization.

(And yes, A & C deserve tests, but they're not of the
missing-coverage-for-merge-recursive variety that I was thinking of
for G.)

>>   * E is kind of big.  Are there any specific things folks would like to see
>>     with how that is handled?
>
> How much abstraction can be done ahead of time such that there is an
> interface/API where you just plug in a new merge strategy and do not
> need to duplicate a lot of code/tests?

For avoiding duplicate tests, my plan was to use a variable (like
GIT_TEST_SPLIT_INDEX or GIT_FSMONITOR_TEST), which, when set, would
change the default merge strategy from "recursive" to the new one, and
also replace explicit requests for the "recursive" merge strategy with
the new one.

For avoiding duplicate code...well, Junio's suggestion was "[to
rewrite] without using much from the existing code in
merge-recursive.c at all" because he has "written off that code as
mostly unsalvageable"[4].

There are some functions that I think are worth leaving intact (e.g.
helpers like output(), the directory rename detection stuff, or the
merge_submodule code that you recently moved).  That stuff I was
planning to put in a "/* COPIED FROM merge-recursive.c VERBATIM */"
section.  And eventually, the idea would be to delete the old
merge-recursive and just use the replacement, making the duplication
concerns eventually go away.

...or is your question more about how to abstract things so that
others can also write new merge strategies in the future and allow as
much code and test re-use as possible?


>> [4] https://public-inbox.org/git/xmqqk1ydkbx0.fsf@gitster.mtv.corp.google.com/
>>    [New strategy]


Thanks for taking a look!

Elijah

Re: RFC: Merge-related plans

[Stefan Beller]

context: https://public-inbox.org/git/CABPp-BFQJZHfCJZ1qvhvVcMd-_sOfi0Fkm5PexEwzzN+Zw2akw@mail.gmail.com/

Hi Elijah,

>> Most items forward-reference "Depends on (<later letter>) up to here;
>> (H) seems independent, but might be a good first start.
>> (G) [8] is queued as origin/en/merge-recursive-tests, or do you mean
>> to expand (G) into a mini-framework of merge-testing? i.e. run the
>> mini test framework multiple times, each using a different
>> merge strategy, similar to submodule tests, e.g. see
>> t/lib-submodule-update.sh and one of its users, t1013.
>
> Sorry, I should have been more clear about G.
>
> In more detail...
>
> [...]

Yeah that is what I had in mind when talking about a mini test frame work
above, such that you can run the same test on any merge strategy easily.
Sorry for being confusing there.

>> (B) sounds like an independent feature, which could go in parallel?
>
> B may sound like an independent feature, but it needs a merge
> algorithm that doesn't mess with the working tree

I agree on that,

> so it depends pretty strongly on E.

.. but not quite on the conclusion:
You could also make the current merge algorithm working
tree independent. Thomas Rast (cc'd) did so IIUC in
https://public-inbox.org/git/cover.1409860234.git.tr@thomasrast.ch/
(search the archive for "--remerge" if interested in this prior work)
which did not land upstream.

>>>   * Should I post RFC questions on A and C earlier?
>>
>> I would think so, it is easier to give feedback on code, I would think.
>
> If the idea is to give feedback on *code* rather than just
> ideas/tradeoffs/pinpointing-buggy-lines, then it sounds like you're
> actually suggesting posting the RFC later rather than earlier?

Some people have complained that they don't get feedback on
ideas/tradeoffs/pinpointing-buggy-lines, but did so after sending
RFC code. So I'd think a sure way to get feedback is to send actual
code as an RFC even if it misses some parts.

> Also, the bigger question for me wasn't so much "should I ask the list
> about these changes?" before making them, but rather: Do folks want me
> to bring these things up before I work on D & E -- even if I end up
> not getting back to incorporating their answers for months until D & E
> are completed and merged?

I'd think A + C are worth asking early nevertheless, even if D & E are
away for some month; having these niche cases covered (in code and
tests) as well as a new UI/UX for user communication sound exciting
(The latter could result in some bike shedding, and then having enough
time before you spend time to do it one way or another in D&E sounds
favorable)

>>>   * Should I split D and G?  (Current plan was to keep D together, but
>>>     split G into five short slightly inter-dependent topics)
>>
>> I would have expected to have tests (G) as a companion of (A) or (C)
>> rather than (D), as performance improvements would keep the test suite
>> unchanged?
>
> Let me re-phrase: D and G are completely independent series, both of
> which happen to be divisible.  Should either of them be split?

Sorry for my confusion. This clears it up

>
> More background: D is only a handful of commits, so far; the main
> reason to split it is to allow some of it to go first (maybe even
> before G or H).  The downside is introducing extra churn and risk in
> merge-recursive, when I'm planning to rewrite it soon anyway.  I was
> trying to minimize merge-recursive changes, other than trying to make
> sure that the new merge strategy and merge-recursive will give
> identical results (modulo maybe fixing a few extra corner cases and
> running faster).  Basically, I wanted it to be really easy to compare
> old and new strategies, but otherwise wanted to leave merge-recursive
> mostly alone.  It's not entirely clear how quickly I'll find time to
> work on all of this, though, so maybe just-wait-for-the-rewrite is not
> the right prioritization.

My experience is that smaller patch series are reviewed faster,
so if the cost of splitting them up is not prohibitive, I'd strongly
consider doing that.

>>>   * E is kind of big.  Are there any specific things folks would like to see
>>>     with how that is handled?
>>
>> How much abstraction can be done ahead of time such that there is an
>> interface/API where you just plug in a new merge strategy and do not
>> need to duplicate a lot of code/tests?
>
> For avoiding duplicate tests, my plan was to use a variable (like
> GIT_TEST_SPLIT_INDEX or GIT_FSMONITOR_TEST), which, when set, would
> change the default merge strategy from "recursive" to the new one, and
> also replace explicit requests for the "recursive" merge strategy with
> the new one.

So your long term plan is to *replace* the whole merge recursive strategy
giving the same results [analogous to implementing refstable as a new refs
back end, that behaves the same except faster and easier code for corner
cases] and not offer a *new* strategy [analog here: different (merge/)diff
strategies, such as Myers vs minimal vs patience] that yields user visible
difference and it is unclear whether the user prefers one or the other?
That wasn't clear to me, thanks for clarifying.

My original reply was assuming a new "mode" of merge strategy which
would be a user visible knob to turn. The environment variable you mentioned
sounds like that is an implementation detail, that is just for a
smooth transition
period, but the current code would be deprecated and deleted eventually.

> For avoiding duplicate code...well, Junio's suggestion was "[to
> rewrite] without using much from the existing code in
> merge-recursive.c at all" because he has "written off that code as
> mostly unsalvageable"[4].
>
> There are some functions that I think are worth leaving intact (e.g.
> helpers like output(), the directory rename detection stuff, or the
> merge_submodule code that you recently moved).  That stuff I was
> planning to put in a "/* COPIED FROM merge-recursive.c VERBATIM */"
> section.  And eventually, the idea would be to delete the old
> merge-recursive and just use the replacement, making the duplication
> concerns eventually go away.

This clears up even more, thanks for clarifying!

> ...or is your question more about how to abstract things so that
> others can also write new merge strategies in the future and allow as
> much code and test re-use as possible?

That was my original question as I thought an API would help with
doing that as it would help to not fiddle around with the rest of the
code base.

>>> [4] https://public-inbox.org/git/xmqqk1ydkbx0.fsf@gitster.mtv.corp.google.com/

Did you mean:
https://public-inbox.org/git/xmqqd147kpdm.fsf@gitster.mtv.corp.google.com/

So in that case my reply above ("..so it depends pretty strongly on E.."
I have a different conclusion) is void, as that *is* the new strategy?

Thanks,
Stefan

Re: RFC: Merge-related plans

[Elijah Newren]

Hi Stefan,

On Tue, May 29, 2018 at 3:12 PM, Stefan Beller <sbeller@google.com> wrote:
>>> (B) sounds like an independent feature, which could go in parallel?
>>
>> B may sound like an independent feature, but it needs a merge
>> algorithm that doesn't mess with the working tree
>
> I agree on that,
>
>> so it depends pretty strongly on E.
>
> .. but not quite on the conclusion:
> You could also make the current merge algorithm working
> tree independent. Thomas Rast (cc'd) did so IIUC in
> https://public-inbox.org/git/cover.1409860234.git.tr@thomasrast.ch/
> (search the archive for "--remerge" if interested in this prior work)
> which did not land upstream.

I'm aware of Thomas' remerge-diff series (it's where I got the name
from, and I linked to it in
https://bugs.chromium.org/p/git/issues/detail?id=12).  It's some
pretty cool work.  I also submitted a previous series to make
merge-recursive not touch the working tree (for different reasons),
and then when folks pointed out the similarity between my series and
Thomas' in this area, I compared our approaches:

https://public-inbox.org/git/CABPp-BG49Gr3Kf8Q3E6Vc=GF9MG+m10HkhkwbaOBfzs1cFcgVw@mail.gmail.com/

I still think my approach to the do-not-touch-worktree aspect was
cleaner, but both complicate the already excessively complex
merge-recursive codebase, and just dance around the fundamental design
flaw in merge-recursive (discussed more at the end of the email via
links to Junio's thoughts on the topic).  At this point, I'd rather
just fix the design flaw rather than complicate the code further.

>> If the idea is to give feedback on *code* rather than just
>> ideas/tradeoffs/pinpointing-buggy-lines, then it sounds like you're
>> actually suggesting posting the RFC later rather than earlier?
>
> Some people have complained that they don't get feedback on
> ideas/tradeoffs/pinpointing-buggy-lines, but did so after sending
> RFC code. So I'd think a sure way to get feedback is to send actual
> code as an RFC even if it misses some parts.

Makes sense.

>> Also, the bigger question for me wasn't so much "should I ask the list
>> about these changes?" before making them, but rather: Do folks want me
>> to bring these things up before I work on D & E -- even if I end up
>> not getting back to incorporating their answers for months until D & E
>> are completed and merged?
>
> I'd think A + C are worth asking early nevertheless, even if D & E are
> away for some month; having these niche cases covered (in code and
> tests) as well as a new UI/UX for user communication sound exciting
> (The latter could result in some bike shedding, and then having enough
> time before you spend time to do it one way or another in D&E sounds
> favorable)

Okay, sounds like I need to put a little code behind my ideas, at
least enough for some RFCs.

> My experience is that smaller patch series are reviewed faster,
> so if the cost of splitting them up is not prohibitive, I'd strongly
> consider doing that.

Will do.

> So your long term plan is to *replace* the whole merge recursive strategy
> giving the same results.

Yes, precisely.  :-)

>> For avoiding duplicate code...well, Junio's suggestion was "[to
>> rewrite] without using much from the existing code in
>> merge-recursive.c at all" because he has "written off that code as
>> mostly unsalvageable"[4].
>
>>>> [4] https://public-inbox.org/git/xmqqk1ydkbx0.fsf@gitster.mtv.corp.google.com/
>
> Did you mean:
> https://public-inbox.org/git/xmqqd147kpdm.fsf@gitster.mtv.corp.google.com/

The email you link describes the new algorithm behind the replacement
strategy.  That's a useful email, but I was specifically trying to
reference where I was quoting Junio from, which was the email where
Junio suggested implementing the new algorithm as a replacement
strategy rather than re-factoring merge-recursive.c; those quotes came
from the email link I gave.

> So in that case my reply above ("..so it depends pretty strongly on E.."
> I have a different conclusion) is void, as that *is* the new strategy?

Yes, I think Junio's suggestion is a _much_ cleaner way of getting a
do-not-touch-the-working-tree merge than either Thomas' or my previous
submissions. It's a much, much bigger chunk of work to do it that way,
but will fix multiple other problems that the current design make hard
or impossible to fix.


Thanks for the feedback!
Elijah