migrating the WIP on identical comutes from patch1880

2 patches for repository darcs-unstable@darcs.net:screened:

patch cf337f231cff6f3f0b194643becdf6a6086a8131
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Aug 27 17:33:49 BST 2019
  * WIP: identical commutes are an internal error

patch 41106e6f1995a8ffa7475f701faa78fb746aeca0
Author: Ben Franksen <ben.franksen@online.de>
Date:   Tue Aug 27 20:45:45 BST 2019
  * harness: don't generate arbitrary PrimPatchIds, instead use anonymousNamedPrim
  
  This ensures (or rather: increases the probability to near certainty) that we
  never generate arbitrary prim patches with colliding PrimPatchIds.

Attachments

• patch-preview.txt
• unnamed
• wip_-identical-commutes-are-an-internal-error.dpatch

encouraged by Ben's demonstration that it's possible, I
read the unsafePerformIO docs properly and managed to fix the
hacks, so now the tests do pass.

It feels rather wrong to be using unsafePerformIO to generate
random numbers in Gen, given random generation is precisely
what Gen is for! However, QuickCheck isn't built around the
assumption that randomness should be used to (almost-)guarantee
uniqueness, so perhaps it is appropriate here.

I'll have a play next and see if something that seems robust
can be written directly with Gen.

1 patch for repository darcs-unstable@darcs.net:screened:

patch 7084b0aa342d676c46ef7a2a1a90f78646c319e9
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Aug 28 11:54:46 BST 2019
  * WIP: identical commutes are an internal error

Attachments

• patch-preview.txt
• unnamed
• wip_-identical-commutes-are-an-internal-error.dpatch

> encouraged by Ben's demonstration that it's possible, I
> read the unsafePerformIO docs properly and managed to fix the
> hacks, so now the tests do pass.

I meant to say the hacks in my code - Ben's approach already had the tests
passing. But it seems more modular to generate the patch id independently
so I'd prefer to use that approach.

>> encouraged by Ben's demonstration that it's possible, I
>> read the unsafePerformIO docs properly and managed to fix the
>> hacks, so now the tests do pass.
> 
> I meant to say the hacks in my code - Ben's approach already had the tests
> passing. But it seems more modular to generate the patch id independently
> so I'd prefer to use that approach.

I was just starting to review the first patch of patch1880

patch 403b46b4a02845a8cd2d3b63eef285d734195245
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Aug 27 13:44:48 CEST 2019
  * introduce PrimWithName and make NamedPrim a type synonym

and noticed the TODO item about not being able to call error because of
the problem solved by patch1898 (this bundle).

Can you please rebase this bundle so it applies cleanly to screened (if
necessary) and with the first patch no longer having "WIP" in the
description, and then screen it for review?

> Can you please rebase this bundle so it applies cleanly to screened (if
> necessary) and with the first patch no longer having "WIP" in the
> description, and then screen it for review?

My latest version of this bundle is this single patch:

patch 7084b0aa342d676c46ef7a2a1a90f78646c319e9
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Aug 28 11:54:46 BST 2019
  * WIP: identical commutes are an internal error

I still viewed this as WIP as I wanted to find a better solution than
unsafePerformIO. But I haven't done any more about it yet and I'm not
sure I will soon, so I could just clean this up for now instead. I think
it just needs some comments on the unsafePerformIO and to remove the
-fno-cse in D.P.Prim.Named which looks like a relic of when I had the
unsafePerformIO in there.

> I still viewed this as WIP as I wanted to find a better solution than
> unsafePerformIO. But I haven't done any more about it yet and I'm not
> sure I will soon, so I could just clean this up for now instead. I think
> it just needs some comments on the unsafePerformIO and to remove the
> -fno-cse in D.P.Prim.Named which looks like a relic of when I had the
> unsafePerformIO in there.

The -fno-cse option alone would be a reason to move this code back to
the test suite.... except that we now use it to implement
fromAnonymousPrim, too, which is a good thing, as long as we need that.
And we need it (in lib:darcs) only for rebase:

> grep -rl fromAnonymousPrim src
# calls:
src/Darcs/UI/Commands/Rebase.hs
src/Darcs/Patch/Rebase/Viewing.hs
src/Darcs/Patch/Rebase/Item.hs
src/Darcs/Patch/Rebase/Fixup.hs
# definitions:
src/Darcs/Patch/V3.hs
src/Darcs/Patch/FromPrim.hs
src/Darcs/Patch/V1/Core.hs
src/Darcs/Patch/V2/Non.hs
src/Darcs/Patch/V2/RepoPatch.hs

To get rid of this particular bit of ugliness requires us to /either/
finish what you started with "[patch1911] WIP: use Prim patches in
rebase toedit", /or/ find a way to make the rebase fixups contain
/named/ prims when it works with V3 patches.

This would mean we can no longer use canonizeFL in simplifyPush, but
perhaps this is just as well: we could define a new type class for prims:

  class PrimNormalize prim where
    normalizeFL :: FL prim wX wY -> FL prim wX wY

which for named prims only uses re-ordering and elimination of inverse
pairs.

> The -fno-cse option alone would be a reason to move this code back to
> the test suite.... except that we now use it to implement
> fromAnonymousPrim, too, which is a good thing, as long as we need that.
> And we need it (in lib:darcs) only for rebase:

Oh, I see. I probably left it there because it is needed by existing
code and I realised that when reading the unsafePerformIO docs. That
should probably be a separate patch though.

> To get rid of this particular bit of ugliness requires us to /either/
> finish what you started with "[patch1911] WIP: use Prim patches in
> rebase toedit", /or/ find a way to make the rebase fixups contain
> /named/ prims when it works with V3 patches.

Finishing patch1911 is next on my todo list, now that Invertible is done
and I think you have showed the right way ahead for RebaseName.

> This would mean we can no longer use canonizeFL in simplifyPush, but
> perhaps this is just as well: we could define a new type class for prims:
> 
>   class PrimNormalize prim where
>     normalizeFL :: FL prim wX wY -> FL prim wX wY
> 
> which for named prims only uses re-ordering and elimination of inverse
> pairs.

My gut feeling is that canonizing is important for a good user
experience with rebase. Otherwise the fixups can end up unnecessarily
complicated leading to excessive conflicts. Also, using named prims
inside rebase actually seems wrong to me: they implicitly refer to a
PatchInfo that may no longer exist.

Anyway, I think using Prim patches right through rebase should be our
plan A. But it does mean getting as far as making it work with suspended
conflicts, so there's a reasonable amount to do.

>> [...about the idea to use named prims in rebase...]
>> This would mean we can no longer use canonizeFL in simplifyPush, but
>> perhaps this is just as well: we could define a new type class for prims:
>>
>>   class PrimNormalize prim where
>>     normalizeFL :: FL prim wX wY -> FL prim wX wY
>>
>> which for named prims only uses re-ordering and elimination of inverse
>> pairs.
> 
> My gut feeling is that canonizing is important for a good user
> experience with rebase. Otherwise the fixups can end up unnecessarily
> complicated leading to excessive conflicts.

It is possible but not certain that this would happen in practice.
Perhaps I will try and replace the canonizeFL with some normalizeFL (not
yet written) and invent a few tests or play with it in practice.

The reason I brought up the idea of using name prims is that /my/ gut
feeling tells me to mistrust unnamed prims to behave as we expect in all
cases. Perhaps this is unfounded for something like rebase.

> Also, using named prims
> inside rebase actually seems wrong to me: they implicitly refer to a
> PatchInfo that may no longer exist.

I don't see this as a problem. The patches are re-written on unsuspend
anyway, none of the references remain. This is just about internal
consistency as long as a patch is suspended, and in particular during
the forceCommute.

> Anyway, I think using Prim patches right through rebase should be our
> plan A. But it does mean getting as far as making it work with suspended
> conflicts, so there's a reasonable amount to do.

I just realized that my plan B doesn't help at all with the misbehavior
we observe with rebasing conflicted V1 and V2 patches. Whereas your plan
A should, in principle, be able to fix that. And if there is one thing I
don't trust at all it is that mergers/conflictors for V1 and V2 behave
correctly under all circumstances... which is not a gut feeling but
supported by hard evidence in the form of failing QC tests. So getting
rid of them inside rebase and implementing the forceCommute at the
RebasePatch/prim level directly will avoid running into these problems,
particularly if we rebase conflicted patches.

So yes, in the end it looks as if plan A is the more promising road...

I looked at QuickCheck's random number generation a bit more
and it actually looks like this should work fine (chooseAny
just ends up calling random).

1 patch for repository darcs-unstable@darcs.net:screened:

patch c598974fbaa6965d369e0df73e972fb67e403760
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Sep 22 23:27:44 BST 2019
  * identical commutes are an internal error

Attachments

• identical-commutes-are-an-internal-error.dpatch
• patch-preview.txt
• unnamed

I'm pushing this to screened now. Even if this approach doesn't work after all,
we can fall back to the unsafePerformIO.

> I looked at QuickCheck's random number generation a bit more
> and it actually looks like this should work fine (chooseAny
> just ends up calling random).

I hope you are aware that the standard random uses a time stamp as its
only source of entropy. This is decidedly not cryptographically secure.
(Disclaimer: I haven't yet looked at your patch).

> I hope you are aware that the standard random uses a time stamp as its
> only source of entropy. This is decidedly not cryptographically secure.
> (Disclaimer: I haven't yet looked at your patch).

We don't need cryptographic security for our tests, just a
(probabilistic) guarantee of collision-freedom. As long as the RNG is
only initialised once for a given test then even a deterministic
sequence of pseudo-random numbers ought to be fine, unless I'm
misunderstanding something about their behaviour.

>> I hope you are aware that the standard random uses a time stamp as its
>> only source of entropy. This is decidedly not cryptographically secure.
>> (Disclaimer: I haven't yet looked at your patch).
> 
> We don't need cryptographic security for our tests, just a
> (probabilistic) guarantee of collision-freedom. As long as the RNG is
> only initialised once for a given test then even a deterministic
> sequence of pseudo-random numbers ought to be fine, unless I'm
> misunderstanding something about their behaviour.

No this is correct. Sorry for the noise, I should have looked at your
patch before commenting.

> I'm pushing this to screened now. Even if this approach doesn't work after all,
> we can fall back to the unsafePerformIO.

It works perfectly for me. A very elegant solution. Consider as reviewed.

Thanks - btw I didn't state it explicitly in my previous comments,
but I have also run the tests and they were fine.

I included a few runs with a count of 10000 on the tests that fail
when 'aHash' uses 'arbitrary'.