Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Woody Woodman]

Sent from my iPhone

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Johannes Schindelin]

Hi Woody,

On Mon, 4 Mar 2019, Woody Woodman wrote:

> 
> 

Details, please.

> Sent from my iPhone

Not sent from my iPhone, as it would really be cumbersome to type an
informative, useful bug report on a phone, even the best of them.

Ciao,
Johannes

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Elijah Newren]

On Mon, Nov 27, 2017 at 3:39 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Elijah Newren <newren@gmail.com> writes:
>
>>> As a fix, this sorely wants something new in t/ directory.
>>
>> Well, then perhaps I was wrong to submit it independent of my
>> directory rename series.  As noted in the (very lengthy) extended
>> commit message explanation, the assumption the previous code made just
>> happened to work ...
>
> Here is what I wrote in What's cooking draft (which automatically
> gets copied to the merge log message and becomes part of release
> notes when a topic graduates) for this thing.  Am I on the right
> track?
>
>     The code internal to the recursive merge strategy was not fully
>     prepared to see a path that is renamed to try overwriting another
>     path that is only different in case on case insensitive systems.
>     This does not matter in the current code, but will start to matter
>     once the rename detection logic starts taking hints from nearby
>     paths moving to some directory and moves a path that is otherwise
>     not changed along with them.

Yes, though I have one minor nit: I'd prefer "a new path" to "a path
that is otherwise not changed".

(Reason for the nit: "Not changed" to me implies the file existed in
the merge base and didn't change name on either side of the merge,
which in turn implies the directory remains on both sides, which means
there was no directory rename.  Since directory rename detection is
mostly about moving file adds into the right directory, this seemed
like the simplest correction.  There are also transitive renames, but
they're much less common and trying to cover them too might make it
even harder to parse.)

As a side note, the two sentences are a little bit unwieldy to try to
parse.  I couldn't come up with any concrete suggestions to improve
it, so it's probably fine, but thought I'd mention in case others spot
an easy way to simplify it.

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

>> As a fix, this sorely wants something new in t/ directory.
>
> Well, then perhaps I was wrong to submit it independent of my
> directory rename series.  As noted in the (very lengthy) extended
> commit message explanation, the assumption the previous code made just
> happened to work ...

Here is what I wrote in What's cooking draft (which automatically
gets copied to the merge log message and becomes part of release
notes when a topic graduates) for this thing.  Am I on the right
track?

    The code internal to the recursive merge strategy was not fully
    prepared to see a path that is renamed to try overwriting another
    path that is only different in case on case insensitive systems.
    This does not matter in the current code, but will start to matter
    once the rename detection logic starts taking hints from nearby
    paths moving to some directory and moves a path that is otherwise
    not changed along with them.

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Elijah Newren]

[Removed cc's that just bounce]

On Sun, Nov 26, 2017 at 7:40 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Elijah Newren <newren@gmail.com> writes:
>
>> In commit ae352c7f3 (merge-recursive.c: fix case-changing merge bug,
>> 2014-05-01), it was observed that removing files could be problematic on
<snip>
>>
>> If that description leaves more questions than answers, we may need to
>> augment the above commit message with the following explanation...
>> ...
>>  merge-recursive.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> As a fix, this sorely wants something new in t/ directory.

Well, then perhaps I was wrong to submit it independent of my
directory rename series.  As noted in the (very lengthy) extended
commit message explanation, the assumption the previous code made just
happened to work until a few extra tweaks (from directory renames)
caused us to want to remove a file from the working copy that was
found at stage 0 in the index.  Thus, the only testcase we can really
use for this commit, is testcase 7b of the new t6043 added by that
other patch series, and it's only valid with the code from that other
series.

When I submitted this patch, I was thinking about just including this
fix with the next reroll of my rename-directory-detection series but
it partially felt like an independent fix...but maybe I chose wrong.

Would you prefer I include it in my next en/rename-directory-detection reroll?

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> In commit ae352c7f3 (merge-recursive.c: fix case-changing merge bug,
> 2014-05-01), it was observed that removing files could be problematic on
> case insensitive file systems, because we could end up removing files
> that differed in case only rather than deleting the intended file --
> something that happened when files were renamed on one branch in a way
> that differed only in case.  To avoid that problem, that commit added
> logic to avoid removing files other than the one intended, rejecting the
> removal if the files differed only in case.
>
> Unfortunately, the logic it used didn't fully implement that condition as
> stated above...
>
> If that description leaves more questions than answers, we may need to
> augment the above commit message with the following explanation...
> ...
>  merge-recursive.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)

As a fix, this sorely wants something new in t/ directory.

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> I had another email I had been composing to try to argue for changing
> merge-recursive.c's design to the above, assuming I could get the time
> to work on it.  Nice to see that I'm not crazy, and that I apparently
> don't need to do much convincing.  :-)

You might even be better off coming up with a *new* merge strategy
backend if you want to do this, without using much from the existing
code in merge-recursive.c at all (I've written off that code as
mostly unsalvageable long time ago, and thanked for whoever had a
clever idea to allow different strategy backend to be made without
disrupting the rest of the system).

After we gain more confidence with the rewrite, we can switch the
internally built-in backend used by different codepaths from
merge-recursive.c::merge_recursive() to the new thing.

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Elijah Newren]

On Fri, Nov 24, 2017 at 7:29 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Elijah Newren <newren@gmail.com> writes:
>
>>     But what it really is forced to do is more of a 4-way merge; a good
>>     chunk of its annoying complexity is based around this (undocumented
>>     and unfortunate) reality.  It derives from what I consider a simple
>>     design flaw.
>
> Yes, and it does not help that it wants to write into the filesystem
> while it performs the outermost merges.
>
> In the ideal world, we should
>
>  - ask unpack_trees() to do "read-tree -m" without "-u";
>
>  - do all the merge-recursive computations in-core and prepare the
>    resulting index, while keeping the current index intact;
>
>  - compare the current in-core index and the resulting in-core
>    index, and notice the paths that need to be added, updated or
>    removed in the working tree, and ensure that there is no loss of
>    information when the change is reflected to the working tree,
>    e.g. the result wants to create a file where the working tree
>    currently has a directory with non-expendable contents in it, the
>    result wants to remove a file where the working tree file has
>    local modification, etc.; and then finally
>
>  - carry out the working tree update to make it match what the
>    resulting in-core index says it should look like.

I had another email I had been composing to try to argue for changing
merge-recursive.c's design to the above, assuming I could get the time
to work on it.  Nice to see that I'm not crazy, and that I apparently
don't need to do much convincing.  :-)

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

>     But what it really is forced to do is more of a 4-way merge; a good
>     chunk of its annoying complexity is based around this (undocumented
>     and unfortunate) reality.  It derives from what I consider a simple
>     design flaw.

Yes, and it does not help that it wants to write into the filesystem
while it performs the outermost merges.

In the ideal world, we should

 - ask unpack_trees() to do "read-tree -m" without "-u";

 - do all the merge-recursive computations in-core and prepare the
   resulting index, while keeping the current index intact;

 - compare the current in-core index and the resulting in-core
   index, and notice the paths that need to be added, updated or
   removed in the working tree, and ensure that there is no loss of
   information when the change is reflected to the working tree,
   e.g. the result wants to create a file where the working tree
   currently has a directory with non-expendable contents in it, the
   result wants to remove a file where the working tree file has
   local modification, etc.; and then finally

 - carry out the working tree update to make it match what the
   resulting in-core index says it should look like.



   

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Elijah Newren]

On Fri, Nov 24, 2017 at 12:04 PM, Eric Sunshine <sunshine@sunshineco.com> wrote:
> On Fri, Nov 24, 2017 at 2:59 PM, Elijah Newren <newren@gmail.com> wrote:
>> In commit ae352c7f3 (merge-recursive.c: fix case-changing merge bug,
>> 2014-05-01), it was observed that removing files could be problematic on
>> case insensitive file systems, because we could end up removing files
>> that differed in case only rather than deleting the intended file --
>> something that happened when files were renamed on one branch in a way
>> that differed only in case.  To avoid that problem, that commit added
>> logic to avoid removing files other than the one intended, rejecting the
>> removal if the files differed only in case.
>>
>> Unfortunately, the logic it used didn't fully implement that condition as
>> stated above; instead it merely checked that a case-insensitive lookup of
>> the file that was requested resulted in finding a file in the index at
>> stage 0, not that the file found in the index actually differed in case.
>> Alternatively, one could view the implementation as making an implicit
>> assumption that the file we actually wanted to remove would never appear
>> in the index with a stage of 0, and thus that if we found a file with our
>> lookup, that it had to be a different file (but different in case only).
>>
>> The net result of this implementation is that it can ignore more requests
>> than it should, leaving a file around in the working copy that should
>> have been removed.  Make sure that the file found in the index actually
>> differs in case before silently ignoring the request to remove the file.
>>
>> ---
>
> Missing sign-off.

Whoops!

Signed-off-by: Elijah Newren <newren@gmail.com>

Re: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Eric Sunshine]

On Fri, Nov 24, 2017 at 2:59 PM, Elijah Newren <newren@gmail.com> wrote:
> In commit ae352c7f3 (merge-recursive.c: fix case-changing merge bug,
> 2014-05-01), it was observed that removing files could be problematic on
> case insensitive file systems, because we could end up removing files
> that differed in case only rather than deleting the intended file --
> something that happened when files were renamed on one branch in a way
> that differed only in case.  To avoid that problem, that commit added
> logic to avoid removing files other than the one intended, rejecting the
> removal if the files differed only in case.
>
> Unfortunately, the logic it used didn't fully implement that condition as
> stated above; instead it merely checked that a case-insensitive lookup of
> the file that was requested resulted in finding a file in the index at
> stage 0, not that the file found in the index actually differed in case.
> Alternatively, one could view the implementation as making an implicit
> assumption that the file we actually wanted to remove would never appear
> in the index with a stage of 0, and thus that if we found a file with our
> lookup, that it had to be a different file (but different in case only).
>
> The net result of this implementation is that it can ignore more requests
> than it should, leaving a file around in the working copy that should
> have been removed.  Make sure that the file found in the index actually
> differs in case before silently ignoring the request to remove the file.
>
> ---

Missing sign-off.

> diff --git a/merge-recursive.c b/merge-recursive.c
> index b48b15a6f..100fb913f 100644
> --- a/merge-recursive.c
> +++ b/merge-recursive.c
> @@ -646,7 +646,7 @@ static int remove_file(struct merge_options *o, int clean,
>                 if (ignore_case) {
>                         struct cache_entry *ce;
>                         ce = cache_file_exists(path, strlen(path), ignore_case);
> -                       if (ce && ce_stage(ce) == 0)
> +                       if (ce && ce_stage(ce) == 0 && strcmp(path, ce->name))
>                                 return 0;
>                 }
>                 if (remove_path(path))
> --
> 2.11.0

[PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

[Elijah Newren]

In commit ae352c7f3 (merge-recursive.c: fix case-changing merge bug,
2014-05-01), it was observed that removing files could be problematic on
case insensitive file systems, because we could end up removing files
that differed in case only rather than deleting the intended file --
something that happened when files were renamed on one branch in a way
that differed only in case.  To avoid that problem, that commit added
logic to avoid removing files other than the one intended, rejecting the
removal if the files differed only in case.

Unfortunately, the logic it used didn't fully implement that condition as
stated above; instead it merely checked that a case-insensitive lookup of
the file that was requested resulted in finding a file in the index at
stage 0, not that the file found in the index actually differed in case.
Alternatively, one could view the implementation as making an implicit
assumption that the file we actually wanted to remove would never appear
in the index with a stage of 0, and thus that if we found a file with our
lookup, that it had to be a different file (but different in case only).

The net result of this implementation is that it can ignore more requests
than it should, leaving a file around in the working copy that should
have been removed.  Make sure that the file found in the index actually
differs in case before silently ignoring the request to remove the file.

---

If that description leaves more questions than answers, we may need to
augment the above commit message with the following explanation...

But, you may ask, why didn't we ever discover this problem before?  And
why would we have a file at stage 0 in the index that we wanted to remove
from the working copy?  Great questions, both, but the answer is fairly
lengthy.  The short answer to the first question is that due to a myriad
of details, this bug is only currently triggerable:

    * on case insensitive filesystems
    * with rename/rename(2to1) conflicts
    * once one has taken care to avoid allowing renames to overwrite
      untracked or dirty files (see commit 30fd3a5 (merge overwrites
      unstaged changes in renamed file, 2012-04-15), which was fixed in
      my in-flight en/rename-directory-detection series currently sitting
      in pu)
    * AND where one of the renames is implicitly done (e.g. via
      directory rename detection).

Thus, this bug remained hidden/latent until those other conditions are
all triggered.  Luckily, testcase 7b of t6043 added in
en/rename-directory-detection was written to carefully check all details
of the index and working copy to ensure they had the right content,
giving us an early notification of this bug.  (I was worried when I wrote
those tests that I was being too laborious in checking all details, but I
apparently got lucky and the extra checks in one of them paid off.)

To explain why we would have a file at stage 0 in the index that we
wanted to remove from the working copy can be explained by four points
(most of which bring up further questions, but be patient and I'll try to
wrap up all the loose ends):

  * If we have two conflicting files at PATH, we will want the index to
    have two higher stage entries for PATH.  There are a few choices for
    the working copy, but one prominent choice is to remove PATH from the
    working copy, then create PATH~HEAD and PATH~$MERGE files.  This
    strategy for the working copy is currently used for
    rename/rename(2to1) conflicts, though it has also been proposed (in
    my pending rename-perf series I submitted this month) for some
    add/add and rename/add conflicts.

  * When unpack_trees() (called by merge-recursive) notices two paths at
    the same location (which could mean an add/add conflict, or after
    rename detection it might more precisely turn out to be a rename/add
    or rename/rename(2to1) conflict), unpack_trees() removes the stage 0
    index entry for the path and just creates higher stage entries.

    HOWEVER, if files can be implicitly renamed to a path that didn't
    exist on either side of the merge (such as from directory rename
    detection), then merge-recursive can see two conflicting files at the
    same location, despite unpack_trees() having left the path at stage
    0.

  * merge-recursive is traditionally thought of as doing a 3-way merge.
    But what it really is forced to do is more of a 4-way merge; a good
    chunk of its annoying complexity is based around this (undocumented
    and unfortunate) reality.  It derives from what I consider a simple
    design flaw.

  * In order to get the 4-way merge right (i.e. avoiding spurious error
    messages and taking care to not overwrite important dirty or
    untracked files), we MUST handle the working copy BEFORE updating the
    index.

The combination of these four items in aggregate answers how we get a
stage 0 file that we want to remove from the working copy, but leaves two
questions -- what do I mean by 4-way merge, and why does the working copy
have to be updated before the index to get that merge right?  Since those
are crucial to understanding this bug, let me begin by explaining the
4-way merge:

The recursive merge strategy is built on first running unpack_trees() and
then "fixing up" the parts it can't resolve.  unpack_trees() does three
things

  * Check whether any untracked or dirty (not-uptodate) files would be
    overwritten by the merge.
  * Update the index AND working tree for trivial cases
  * Store conflicts as higher order stages in the index for later steps
    (e.g. merge-recursive.c) to resolve.

Note that unpack_trees() doesn't understand renames, thus its checks for
whether a dirty or untracked file would be overwritten by the merge is
going to have both false positives and false negatives.  For false
positives, see testcase 10e of the new t6043 introduced in the in-flight
en/rename-directory-detection series.  For false negatives, see commit
30fd3a5 (merge overwrites unstaged changes in renamed file, 2012-04-15),
and most testcases in sections 10 and 11 of the new t6043 introduced in the
en/rename-directory-detection series.

The false positive cannot be fixed with the current design; unpack_trees()
simply aborts early in some highly uncommon cases.

The false negatives cannot be fixed either, but they can be worked around;
fundamentally, it is too late to "abort the merge early" with an error
message, because unpack_trees() already wrote lots of changes to the
working copy for all the trivial merge cases and thus aborting would mean
being left with a dirty working copy.  Since it can't abort early, the code
instead needs to consider what untracked or dirty files might exist in the
working copy and take care to not overwrite them, essentially forcing us to
not only consider HEAD, the merge branch, and the merge base, but also the
working copy as a fourth set of content we need to interact with.  (It
could be worse, though.  If not for merge's check that the index matches
HEAD and aborting early if they don't, we could have been forced to deal
with a 5-way merge.)  The workarounds for false negatives take the form of
calling the would_lose_untracked() and was_dirty() functions (the latter of
which was added in the en/rename-directory-detection series to fix
overwriting dirty files involved in both normal and directory renames).

That brings us to our final loose end -- why does the working copy have to
be updated before the index?  The short answer is that
would_lose_untracked() and was_dirty() both rely on information in the
index in order to do their work.  The current index has information copied
from the original index by unpack_trees() that we need in these functions.
Since unpack_trees() discards the original index before returning, the
current index is our one source for this information, so we need to be
careful not to discard it until after we have handled the working copy.

And it may be important to point out that discarding the information in the
index before updating the working copy is an easy mistake to make that is
painful to debug.  This is evidenced by the existence of commit f53d39778
(merge-recursive: Fix spurious 'refusing to lose untracked file...'
messages, 2011-08-11), which added a big comment at the beginning of
update_stages() pointing out the perils of trying to update the stages in
the index before updating the working copy.  In fact, despite adding that
big comment, I hit the same kind of problem again later and added two more
very similar large warnings to the top of the conflict_rename_rename_2to1()
and apply_directory_rename_modifications() functions in the
en/rename-directory-detection series.

To try to recap, 4-way merge is a pain.  It has always been a pain as
evidenced by commits like
  * f53d39778 (merge-recursive: Fix spurious 'refusing to lose untracked
    file...' messages, 2011)
  * 30fd3a5 (merge overwrites unstaged changes in renamed file, 2012)
but it becomes even more so with additional features and requirements like
case-insensitive filesystems and directory rename detection.  4-way merges
simply cause the complexity to increase with every new capability.

The cleanest fix would be to switch to a 3-way index-only merge (making
unpack_trees() completely ignore the working copy, and making most of
merge-recursive do the same), then checking for untracked or dirty
working tree files in the way of the merge, then adding code that allows
us to update the working copy from one index to a new index.  That new
update code would be very similar to checkout, except that the new index
might have conflicts, and the new update may need to be supplemented with
additional info in order to correctly report various special conflict
cases such as rename/rename(2to1) or rename/add).

But such a large rewrite is a big task.  In the mean time, fix the
ignore_case code.  Allow it to continue rejecting the removal of files
that differ in case only, but only allow it to reject such removals.


 merge-recursive.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Sidenote: I built this commit on master, but it cleanly cherry-picks to
maint, to next, and to pu.

diff --git a/merge-recursive.c b/merge-recursive.c
index b48b15a6f..100fb913f 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -646,7 +646,7 @@ static int remove_file(struct merge_options *o, int clean,
 		if (ignore_case) {
 			struct cache_entry *ce;
 			ce = cache_file_exists(path, strlen(path), ignore_case);
-			if (ce && ce_stage(ce) == 0)
+			if (ce && ce_stage(ce) == 0 && strcmp(path, ce->name))
 				return 0;
 		}
 		if (remove_path(path))
-- 
2.11.0