This report is spun out from issue1453.

See also the discussion in <20090513024353.GB46881@dewdrop.local>
or http://lists.osuosl.org/pipermail/darcs-users/2009-May/019695.html

The corruption in question is that patches to two different files (foo
vs Foo) can be applied to the same working directory file.  I've
attached a script that demonstrates this.  I believe Trent has a nicer
version and would like him to submit it.

With old fashioned repositories, the problem is more severe (pristine
can get corrupted).  Hashed repositories are affected "only" on the
level of the working directory.

This is a long-term bug with a very invasive fix.  This means that it is
likely to be resolved in darcs 3.  It's not specifically dependent on
patch theory 3 (aka the one used in camp), so the only reason to
postpone releasing a fix is strategic.

Trent's test works for me on HFS+ (case insensitive) on Mac OS X: it creates a 
backup file for one of the working copy files, and doesn't "merge" them.

Here's my version of the test which demonstrates the problem on my Mac

Attachments

• case-sensitivity.sh

On Fri, May 15, 2009 at 09:55:51PM +0000, Salvatore Insalaco wrote:
> Trent's test works for me on HFS+ (case insensitive) on Mac OS X: it
> creates a backup file for one of the working copy files, and doesn't
> "merge" them.

I can confirm this.  If I change the fgrep lines in my test, I can
produce this output:

  [...]

  # The push succeeds on hashed (and darcs-2) repos!  I think this is
  # actually worse, because AFAICT it has silently discarded one branch.
  # Confirm this by grepping for the original strings.
  ls -l S/[fF]*
  -rw-r--r-- 1 twb cyber 17 2009-05-17 12:44 S/f
  -rw-r--r-- 1 twb cyber 19 2009-05-17 12:44 S/f-darcs-backup0
  fgrep 'Example content.' S/[fF]*
  S/f:Example content.
  fgrep 'Different content.' S/[fF]*
  S/f-darcs-backup0:Different content.

  [...]

On this basis, I think that this is "not a bug".

On Sun, May 17, 2009 at 02:48:33 -0000, Trent Buck wrote:
> On this basis, I think that this is "not a bug".

Try my test case, the case-sensitivity.sh one attached to this tracker.
Here the corruption consists of both patches being applied into one
file, a falsely clean merge.

On Sat, May 16, 2009 at 11:03:12PM +0000, Eric Kow wrote:
> On Sun, May 17, 2009 at 02:48:33 -0000, Trent Buck wrote:
>> On this basis, I think that this is "not a bug".
>
> Try my test case, the case-sensitivity.sh one attached to this
> tracker.  Here the corruption consists of both patches being applied
> into one file, a falsely clean merge.

OK, you're right, I can reproduce it with your test script.
Can you send it as a formal patch to the list, please? :-)
Be sure to cite EXAMPLE.sh, particularly, load lib and use its not()
instead of || exit 1, and to name it issue1461_something.sh.

On Sun, May 17, 2009 at 10:01:45 -0000, Trent Buck wrote:
> OK, you're right, I can reproduce it with your test script.
> Can you send it as a formal patch to the list, please? :-)

Done.

While I'm at it, here is the solution proposed for this bug, pasted from
the second darcs hacking sprint report.  Note the last sentence in
particular.

Roughly speaking, darcs could associate each filename with some sort of unique
ID. If we then try to merge two unrelated repositories that (for instance),
have the same filename, darcs need not treat them as an actual conflict. These
files would have a semi-conflicted state, where darcs does not really think of
them as being conflicting, but warns the user about the clashing filenames.
This mechanism could also be easily extended to deal with issues such as
case-insensitive filesystems, or specific unsupported filenames (e.g. COM1 on
Windows).

Just bumping this bug (routine maintenance) and linking Ganesh's add-add
conflicts page while I'm at it.

http://wiki.darcs.net/Ideas/AddAddConflicts

The test succeeds for me (on Linux). Judging from the mailing list
discussion linked in the comments, I guess it was fixed by moving to the
hashed repo format, which is the only one we care about nowadays. Will
send a patch that drops the "failing-" prefix.

Ahem, of course it doesn't show on Linux, sorry. Ganesh, does this still
fail on Windows?

It passes on Windows (it actually shows up as "Skipped" on Linux rather 
than passing, btw)

(I removed the commands that cause it to be skipped on Linux before
testing.)

Before I close this ticket

* Are you sure the Windows machine on which you tested identifies files
with names that differ only in case? (I am not up to date on Windows
development, perhaps they changed that)
* Can you test it with --case-ok, too? The error might not show up if it
is not. Again I am not sure what the test tests, exactly, and how the
error, if there is one, manifests.

> Are you sure the Windows machine on which you tested identifies
> files with names that differ only in case? (I am not up to date on
> Windows development, perhaps they changed that)

Yes (otherwise the test would have been skipped - I just double-
checked and it is reporting "Success").

> Can you test it with --case-ok, too? The error might not show up 
> if it is not. Again I am not sure what the test tests, exactly,
> and how the error, if there is one, manifests.

Where should I put that?

Sorry, forget the --case-ok switch. It is there to override the default
behavior for the add command. The test script works by merging two
separate repos, one with a file named 'a' and one with a file name 'A',
so the switch is irrelevant here.

The test for this bug started failing again after patch1716, not sure
why I missed that when accepting that patch.

I've now looked at it more closely and the test should never have worked
on Windows.

The core and final check of the test is this:

> grep one a && not grep three a
> grep three A && not grep one A

It should never be possible for that to pass on Windows!

However, it seems that && in our tests is not safe on Windows,
which I hadn't known before. The script below *doesn't*
exit early when 'grep one a' fails, at least in my environment
(mingw64).

> #!/usr/bin/env bash
> set -e
> grep one a && not grep three a
> echo done

On the other hand this does exit early:

> #!/usr/bin/env bash
> set -e
> grep one a
> not grep three a
> echo done

The test actually started breaking after patch1716 for unrelated
reasons - the pull from lower with --ignore-times starts prompting
for conflicts when it didn't before.

Overall I am inclined to re-mark this test as failing, and edit it
not to use && so it doesn't pass incorrectly in future.

The behaviour of && also calls into question is use in the rest of
our tests, but I don't feel like doing anything about that right now.

Just for the record:

The interaction of && and -e is actually documented and happens
on Linux too. If you want a failure in foo to cause an early exit of
the script where foo && bar is run, you have to
put the whole thing in a subshell with (foo && bar).

Ganesh, can you give an update on this issue? Has the test script been 
fixed and does it still fail on Windows? I cannot see how patch1716 
could have caused a regression here but I am willing to investigate if 
you can confirm this is the case.

My last comment was confused, sorry for that. The connection to 
patch1716 was superficial as you explained well enough, no need to 
pursue that. The bug is still present on file systems with case-
insensitive path names.

I can think of a possible solution, now that we use AnchoredPath to 
represent patches internally: we change the Eq and Ord instances for 
AnchoredPath (at compile time, depending on the target OS) so that 
on Windows AnchoredPaths that differ only in case compare equal. The 
obvious problem with that is that upper/lower case depends on the 
encoding, so patch semantics (how patches commute and merge) now may 
depend on the encoding that is being used by the file system.

> change the Eq and Ord instances for 
> AnchoredPath (at compile time, depending on the target OS) so that 
> on Windows AnchoredPaths that differ only in case compare equal. The 
> obvious problem with that is that upper/lower case depends on the 
> encoding, so patch semantics (how patches commute and merge) now may 
> depend on the encoding that is being used by the file system.

Okay, I was thinking out loud. So this is not a solution. Whether two
patches conflict (or commute or merge cleanly) should not depend on
which OS we do the merge on. I think we can take this as an axiom.

It follows that, on Windows, Darcs must refuse to apply any patch
containing a path that differs only in case from any existing path in
pristine or working in order to prevent the working tree to become
corrupt. In general this invariant must also be checked when we clone a
repo, otherwise we will get this sort of failure later when we operate
on the history (obliterate, amend, test, etc). On non-Windows OSes doing
these checks is optional, useful in case the user wants full
interoperability with Windows.

The check during clone could be done when we build a patch index. If
that is disabled, we must resort to a built-in 'darcs check' as part of
the clone command. I guess the actual 'darcs check/repair' should also
check the invariant (again on Windows this would be mandatory, otherwise
optional).

I could imagine a configuration option (or an interactive yes/no prompt)
that allows the user to override the decision (after doing the check and
displaying its result, and with appropriate warnings attached). This
would mainly be for cases where collisions happened only in the distant
past so that it is unlikely they will be encountered in practice when
working with the repo.

BTW, I am not convinced adopting FileUUID would solve the problem, at
least not fully. We do have to mention file names, if not full paths, in
patches: on Windows two Manifest patches should conflict when they place
two objects as "foo" and "FOO" in the same directory object (otherwise
the result could not be converted to a valid working tree), whereas on
Linux this would not be a conflict. Again we cannot allow that, so on
Windows we must refuse to apply two such prims.

The very least we must do to resolve the issue at hand is to detect when
we are about to apply such an 'invalid' (relative to the current repo
state) patch and fail with an appropriate error message.

I think warning if you are creating a repository state that wouldn't
work on Windows makes sense. I agree that FileUUIDs don't help.

A couple of notes:

- A patch that both removes A and creates a (or renames A to a) 
should be considered valid, though it may require careful 
implementation in apply.

 - We probably can't protect against all possible failures. 
Reordering patches could lead to invalid states being created even 
when a particular linearisation of the repository looked fine.

>  - We probably can't protect against all possible failures. 
> Reordering patches could lead to invalid states being created even 
> when a particular linearisation of the repository looked fine.

I don't believe this is so. We know that all re-orderings result in the
same state. The commute cases for the 'move' prim ensure that we locally
maintain file identity and the cases for 'addfile' and 'rmfile' (and
removal, too) ensure that file paths are unique in every state. By
induction this generalizes to sequences (assuming permutivity etc) and
thus to complete repositories. So if we make sure that we never add a
patch to the repo that has an 'addfile x' or 'adddir x' or 'move _ x'
where x collides with an existing (tracked) file (using case-insensitive
comparison on Windows), then the repo should be safe regardless of any
reordering.

(Note to self: state and test a property that expresses invariance and
local uniqueness of file identities.)

> - A patch that both removes A and creates a (or renames A to a) 
> should be considered valid, though it may require careful 
> implementation in apply.

I believe we get that behavior by default if we make the check at the
level of prim patches and percolate upwards. We have to be careful with
Conflictors and Mergers, though: we must check /all/ contained prims,
not only the effect. This is why it is not enough to throw an error
inside 'apply', since apply is normally defined by calling the prim
patch level 'apply' on the 'effect'(*). So this requires a new method.

(*) The fact that patch application goes via 'effect' is, I think, what
makes it impossible to build reliable methods to track file identity
based on it. Thus 'applyToPaths', and the functions in
Darcs.Patch.TouchesFiles that build on it, are doomed to fail in the
presence of conflicts and re-orderings. The fix is the same as for the
proposed filename collision check: don't go via effect, instead
implement the method directly for each RepoPatch type.

On 12/07/2019 17:56, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:
> 
>>  - We probably can't protect against all possible failures. 
>> Reordering patches could lead to invalid states being created even 
>> when a particular linearisation of the repository looked fine.
> 
> I don't believe this is so. We know that all re-orderings result in the
> same state. The commute cases for the 'move' prim ensure that we locally
> maintain file identity and the cases for 'addfile' and 'rmfile' (and
> removal, too) ensure that file paths are unique in every state. By
> induction this generalizes to sequences (assuming permutivity etc) and
> thus to complete repositories. So if we make sure that we never add a
> patch to the repo that has an 'addfile x' or 'adddir x' or 'move _ x'
> where x collides with an existing (tracked) file (using case-insensitive
> comparison on Windows), then the repo should be safe regardless of any
> reordering.
> 
> (Note to self: state and test a property that expresses invariance and
> local uniqueness of file identities.)

The kind of example I had in mind was this:

patch 1: add a
patch 2: rm a
patch 3: add A

now unpull 2.


>> - A patch that both removes A and creates a (or renames A to a) 
>> should be considered valid, though it may require careful 
>> implementation in apply.
> 
> I believe we get that behavior by default if we make the check at the
> level of prim patches and percolate upwards.

I'd be surprised if both of the following worked without special care:

atomic patch containing rm A ; add a
atomic patch containing add a ; rm A

I'm sure there are more complicated examples that include moves that
might even need temporary files to handle safely.

>>>  - We probably can't protect against all possible failures. 
>>> Reordering patches could lead to invalid states being created even 
>>> when a particular linearisation of the repository looked fine.
>>
>> I don't believe this is so. [...]
> 
> The kind of example I had in mind was this:
> 
> patch 1: add a
> patch 2: rm a
> patch 3: add A
> 
> now unpull 2.

OMG I feel so stupid. Yes, this could only be avoided if we make it a
global property i.e. you cannot 'add A' if there is an 'add a'
/anywhere/ in the repo (and likewise with move).

>>> - A patch that both removes A and creates a (or renames A to a) 
>>> should be considered valid, though it may require careful 
>>> implementation in apply.
>>
>> I believe we get that behavior by default if we make the check at the
>> level of prim patches and percolate upwards.
> 
> I'd be surprised if both of the following worked without special care:
> 
> atomic patch containing rm A ; add a
> atomic patch containing add a ; rm A

Given your refutation, rather than adding this kind of complexity and
not even gaining full safety, I think the better solution is the global
property. That would mean we forbid a "patch that both removes A and
creates a (or renames A to a)". This is straight forward to implement
and fully safe, unless the user expressly overrides it with a command
line option as I proposed before.

On 13/07/2019 12:49, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:
> 
>>>>  - We probably can't protect against all possible failures. 
>>>> Reordering patches could lead to invalid states being created even 
>>>> when a particular linearisation of the repository looked fine.
>>>
>>> I don't believe this is so. [...]
>>
>> The kind of example I had in mind was this:
>>
>> patch 1: add a
>> patch 2: rm a
>> patch 3: add A
>>
>> now unpull 2.
> 
> OMG I feel so stupid. Yes, this could only be avoided if we make it a
> global property i.e. you cannot 'add A' if there is an 'add a'
> /anywhere/ in the repo (and likewise with move).

And you also can never merge a repo that ever created 'a' with a repo
that ever created 'A'.

>> I'd be surprised if both of the following worked without special care:
>>
>> atomic patch containing rm A ; add a
>> atomic patch containing add a ; rm A
> 
> Given your refutation, rather than adding this kind of complexity and
> not even gaining full safety, I think the better solution is the global
> property. That would mean we forbid a "patch that both removes A and
> creates a (or renames A to a)". This is straight forward to implement
> and fully safe, unless the user expressly overrides it with a command
> line option as I proposed before.

I think that as it happens all these specific cases (atomic patches that
add a and remove A, or one that moves A to a) are perfectly safe. The
atomicity of the patches guarantees they are never both present no
matter what the patch ordering.

I've run into situations in practice where fixing the case of files on
Windows was important, e.g. because a project name is determined by the
exact name of the project file (including its case).

Of course this would only ever be an optional warning so we don't have
to get it perfect. But my preference would be to err on the side of
making case changes in a repo pleasant, compared to guarding against the
much less likely case of commuting generating a dangerous repo.

TBH I'm probably one of the very few darcs users on Windows and I am not
desperate for this feature, so it's unlikely to be much of a development
priority in any case.

Ganesh

> And you also can never merge a repo that ever created 'a' with a repo
> that ever created 'A'.

Yes, that's the price. Perhaps it is too high.

>>> I'd be surprised if both of the following worked without special care:
>>>
>>> atomic patch containing rm A ; add a
>>> atomic patch containing add a ; rm A
>>
>> Given your refutation, rather than adding this kind of complexity and
>> not even gaining full safety, I think the better solution is the global
>> property. That would mean we forbid a "patch that both removes A and
>> creates a (or renames A to a)". This is straight forward to implement
>> and fully safe, unless the user expressly overrides it with a command
>> line option as I proposed before.
> 
> I think that as it happens all these specific cases (atomic patches that
> add a and remove A, or one that moves A to a) are perfectly safe. The
> atomicity of the patches guarantees they are never both present no
> matter what the patch ordering.

Any patch that conflicts with, say, the 'rm A' will have the effect of
'add A' and will thus be treated... how?

> I've run into situations in practice where fixing the case of files on
> Windows was important, e.g. because a project name is determined by the
> exact name of the project file (including its case).

Okay, you mean you want to be able to record 'move A a'. Yes, that would
be forbidden under the strict regime. I guess it really is a bit too
strict...

> Of course this would only ever be an optional warning so we don't have
> to get it perfect. But my preference would be to err on the side of
> making case changes in a repo pleasant, compared to guarding against the
> much less likely case of commuting generating a dangerous repo.
> 
> TBH I'm probably one of the very few darcs users on Windows and I am not
> desperate for this feature, so it's unlikely to be much of a development
> priority in any case.

As it's "only" the working tree that breaks, perhaps it suffices to
reliably detect the situation and instruct the user that they should
rename or remove one of the files to make the problem go away; and also
warn them that this "fix" may not be permanent i.e. the problem may
re-appear if they re-order patches. That shouldn't be too hard to do.

On 13/07/2019 17:52, Ben Franksen wrote:

>> I think that as it happens all these specific cases (atomic patches that
>> add a and remove A, or one that moves A to a) are perfectly safe. The
>> atomicity of the patches guarantees they are never both present no
>> matter what the patch ordering.
> 
> Any patch that conflicts with, say, the 'rm A' will have the effect of
> 'add A' and will thus be treated... how?

You're right. Only 'move A a' is safe.

> As it's "only" the working tree that breaks, perhaps it suffices to
> reliably detect the situation and instruct the user that they should
> rename or remove one of the files to make the problem go away; and also
> warn them that this "fix" may not be permanent i.e. the problem may
> re-appear if they re-order patches. That shouldn't be too hard to do.

That's probably ok, though I'm not entirely sure how they'd actually
record the patch to do that if they don't have access to a non-Windows
machine. But there are various options available to a user familiar
enough with darcs so I'm still not that bothered about the situation.

Ganesh

>> As it's "only" the working tree that breaks, perhaps it suffices to
>> reliably detect the situation and instruct the user that they should
>> rename or remove one of the files to make the problem go away; and also
>> warn them that this "fix" may not be permanent i.e. the problem may
>> re-appear if they re-order patches. That shouldn't be too hard to do.
> 
> That's probably ok, though I'm not entirely sure how they'd actually
> record the patch to do that if they don't have access to a non-Windows
> machine.

I thought they just do 'darcs move A a' followed by a record, possibly
using --case-ok or something... I don't know for sure how this would go
down with apply, but I suppose we can figure that out.