As discussed in this thread:
https://lists.osuosl.org/pipermail/darcs-devel/2021-April/022073.html

I've fixed the build problems and test failures
(final CI run is in progress), moved out the indexed
monad infrastructure and adopted Ben's changes to
break out the RebindableSyntax-based code from the
rest.

I'll screen this sometime tomorrow if there are no
last-minute objections, and then follow up on the other
review points.

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

patch bb80e5314b59ba45584acac13d9660e4698afa12
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Apr 16 23:23:34 BST 2021
  * substantial rewrite of 'darcs test'
  
  The major user-visible change is that test scripts can
  now return an exit code of 125 to reflect an untestable
  state (in line with git bisect run).
  
  Since untestable states can mean that a group of patches
  is found to trigger a failure rather than a single patch,
  we now also try to minimise such a group by commuting out
  patches from it to try to find a smaller set of patches
  that transition the test script from success to failure.
  
  Internally, an "indexed monad" is introduced to manage
  the state of the testing tree, and a number of new unit
  tests are added.

Attachments

• patch-preview.txt
• substantial-rewrite-of-_darcs-test_.dpatch
• unnamed

These patches are possible followups for a couple of
review comments (in the thread I linked above).

They introduce a bit more machinery that may not
be justified so I'll wait a bit before screening.

The first one introduces asks. As TestingEnv is a
newtype around ReaderT, I introduced a MonadReader
type class like in the mtl so that I could write
a generic asks that would work on TestingEnv:

patch 230c86f199e7b43eab49213ad633885176c72b45
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 17 19:49:01 BST 2021
  * follow the mtl a bit more for ReaderT
  
  - move it to Darcs.Util.IndexedMonad
  - introduce a MonadReader class and 'asks'
  - use a record for TestingEnv so we can use asks

This one gets rid of testableToRL. The only places
it was used were to convert a Testable before calling
applyRL. Now I've made the concept of "indexed" apply
work on several container types (RL, FL, Testable) so
this conversion isn't needed.

It does introduce some extra constraints for reasons
explained in a comment on TestRunnerPatchReqs, and
also in the unit tests I had to introduce an 'IndexedApply'
class because there is no code for the testing patch
types to operate on non-indexed monads.

I think it does make the use of applyPatches look a bit
nicer, and it also demonstrates that the only real
conversion away from Testable is after the strategy
is complete:

patch 8ab043a7ee356caec8701be759cb3d298a77b258
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 17 23:12:23 BST 2021
  * replace applyRL/unapplyRL with applyPatch/unapplyPatch

Attachments

• follow-the-mtl-a-bit-more-for-readert.dpatch
• patch-preview.txt
• unnamed

>   * follow the mtl a bit more for ReaderT
>   
>   - move it to Darcs.Util.IndexedMonad
>   - introduce a MonadReader class and 'asks'
>   - use a record for TestingEnv so we can use asks
> 
> This one gets rid of testableToRL. The only places
> it was used were to convert a Testable before calling
> applyRL. Now I've made the concept of "indexed" apply
> work on several container types (RL, FL, Testable) so
> this conversion isn't needed.

Nice. Indeed it is now clear that conversion from Testable is indeed
only needed directly after running all the tests.

> It does introduce some extra constraints for reasons
> explained in a comment on TestRunnerPatchReqs, and
> also in the unit tests I had to introduce an 'IndexedApply'
> class because there is no code for the testing patch
> types to operate on non-indexed monads.

Not so nice, but for the time being I can live with that ugliness.

I still think that Testable is a poor name. It really is a generic patch
container type that has nothing to do with testing per se. In fact it's
a binary (leaf) tree of patches in application order. I don't mean it
should go into Darcs.Patch.Witnesses yet, but the name should reflect
what it is, not what we happen to use it for.

Regarding QuantifiedConstraints: if you can prove that this really helps
to avoid the boilerplate, I am not averse to raise lower bounds on base
to require ghc-8.6.

On 19/04/2021 13:08, Ben Franksen wrote:

> Regarding QuantifiedConstraints: if you can prove that this really helps
> to avoid the boilerplate, I am not averse to raise lower bounds on base
> to require ghc-8.6.

I've had a play with this now and I can't actually make it work - the
fact that ApplyPatchReqs is a type family complicates resolution and
even if I could solve it it wouldn't be worth it whatever extra
machinery that required.

I'll drop/update the comment about that.

On 19/04/2021 13:01, Ben Franksen wrote:

> I still think that Testable is a poor name. It really is a generic patch
> container type that has nothing to do with testing per se. In fact it's
> a binary (leaf) tree of patches in application order. I don't mean it
> should go into Darcs.Patch.Witnesses yet, but the name should reflect
> what it is, not what we happen to use it for.

I don't mind calling it BinaryTree or NonEmptyBinaryTree or something.

Following up on one comment from Ben in the previous email thread:

> I find it sad that in order to use the indexed monad in practice we have
> to convert large parts of the code to continuation passing style.

Yes, it is a bit unfortunate. I'm not sure if it's fundamental to the
indexed monad or just the situation in 'test' where we end up
manipulating a lot f patches with unknown witnesses.

It's worth mentioning that some form of this is happening pretty much
everywhere in the logic, including in the backoff/bisect
implementations, e.g. moveHalfNewer etc.

I've spent a while experimenting a bit and thinking about ways to
replace or wrap up the continuation passing in a monad or at least
something that would support do-notation, but the witnesses have
defeated me. So I'm just going to document what I have, and of course
make any other cleanups that occur to me on the way.

> I don't mind calling it BinaryTree or NonEmptyBinaryTree or something.

What about PatchTree?

There is a possible collision with the one defined in
harness/Darcs/Test/Patch/Arbitrary/PatchTree.hs but the latter is legacy
stuff only used to test V1 patches. I verified that there is no actual
collision. We could also rename the legacy PatchTree to something else.

>> I find it sad that in order to use the indexed monad in practice we have
>> to convert large parts of the code to continuation passing style.
> 
> Yes, it is a bit unfortunate. I'm not sure if it's fundamental to the
> indexed monad or just the situation in 'test' where we end up
> manipulating a lot f patches with unknown witnesses.

I fear this is a fundamental limitation. We have lots of code handling
patches with (partially) unknown witnesses and in almost all cases this
can be handled simply by wrapping results with some variant of Sealed.
This cannot be done here because we need the hidden result witness to
coincide with one of the monad indices, while still not exposing the
type variable to the outside. I haven't found a way to make this
type-check and neither, it appears, have you.

Perhaps this will improve when the current work on re-adding
impredicativity to ghc
(https://www.microsoft.com/en-us/research/publication/a-quick-look-at-impredicativity/)
becomes available; it may or may not be a coincidence that making it
work with do-notation is one of the remaining stumbling blocks
(https://gitlab.haskell.org/ghc/ghc/-/issues/18126).

> It's worth mentioning that some form of this is happening pretty much
> everywhere in the logic, including in the backoff/bisect
> implementations, e.g. moveHalfNewer etc.

Yes. My concern is that this makes the new code pretty much inscrutable
for the average Haskell programmer, myself included. We'll have to see
how much that affects my ability to make changes to the code e.g. adapt
it to changes I make elsewhere.

> the witnesses have
> defeated me. So I'm just going to document what I have, and of course
> make any other cleanups that occur to me on the way.

Yes, I think ATM this is all we can do.

In the long run I think we may have to re-think the idea of defining
patch application as a monadic action. With a pure apply method that
works over a witness typed ApplyState we wouldn't need an indexed monad
to get the more precise typing we desire. The main question is how to
make this work without keeping too much of the ApplyState in memory.

> In the long run I think we may have to re-think the idea of defining
> patch application as a monadic action. With a pure apply method that
> works over a witness typed ApplyState we wouldn't need an indexed monad
> to get the more precise typing we desire. The main question is how to
> make this work without keeping too much of the ApplyState in memory.

To elaborate this point a bit, the basic problem we are trying to solve
with the indexed monad is that the state we manipulate in the ApplyMonad
is implicit. It is difficult to track something in the type system if
that something is not passed around explicitly.

The underlying implementation is in the TreeMonad which cleverly tracks
not only the tree but also some meta information about the size of the
changes; this is tracked for each tree item and also in their sum. This
allows it to regularly dump (flush) parts of the state to disk when a
certain threshold is reached, which has the effect of limiting memory
consumption to a fixed amount.

Now, suppose we augment the ApplyState with (a) a type witness and (b)
the change size tracking information as in the TreeMonad. We could then
re-type apply from

  type ApplyState p :: (* -> *) -> *
  apply :: ApplyMonad (ApplyState p) m => p wX wY -> m ()

to

class Apply p where
  type ApplyState p :: (* -> *) -> * -> *
  apply :: Monad m => p wX wY -> PureApplyState p m wX -> m
(PureApplyState p m wY)

Thus, apply would still be monadic (so it can perform e.g. the
underlying IO) but would take and return the ApplyState explicitly and
with proper witnesses.

On 21/04/2021 15:57, Ben Franksen wrote:

> class Apply p where
>   type ApplyState p :: (* -> *) -> * -> *
>   apply :: Monad m => p wX wY -> PureApplyState p m wX -> m
> (PureApplyState p m wY)
> 
> Thus, apply would still be monadic (so it can perform e.g. the
> underlying IO) but would take and return the ApplyState explicitly and
> with proper witnesses.

I think this is similar in safety to what we already do with Repository
(which in most cases is a suitable alternative to PureApplyState
anyway). The downside is that without a linearity guarantee the caller
can just reuse an old Repository/PureApplyState. But maybe that's fine
for the 'test' code too. If you feel the indexed monad code is too
complicated I'm happy to give something like that a go. It could
initially be done locally in just that code.

I'd like to play with LinearTypes at some point, which might provide a
nice general solution to the reuse problem. Unfortunately I think the
ecosystem is being a bit slow at supporting GHC 9.

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

patch d8145176d57779cb636ba89e480275071e017684
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Apr 21 22:37:09 BST 2021
  * update comment
  
  I tried using QuantifiedConstraints and couldn't get it
  working.

Attachments

• patch-preview.txt
• unnamed
• update-comment.dpatch

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

patch ecbf1ccaccbd9c47bc2ca932c2059dfd678afe7e
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 24 11:42:34 BST 2021
  * rename Testable to PatchTree

Attachments

• patch-preview.txt
• rename-testable-to-patchtree.dpatch
• unnamed

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

patch 2cce2e64aba3ade2f05a02f4c0245da080d0233e
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 24 12:14:35 BST 2021
  * Clean up code and document backoff/bisect implementations
  
  This patch should only contain:
   - Reformatting/reordering code
   - Doc comments
   - Renaming type variables for clarity

Attachments

• clean-up-code-and-document-backoff_bisect-implementations.dpatch
• patch-preview.txt
• unnamed

These three patches contain some logic cleanups for backoff/bisect.

I'm submitting them separately from the previous documentation/code
cleanup in case any bugs need to be isolated later.

It's probably sensible to just review the new state of the code.

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

patch dc894ce72e2ac487762d4e295137a612505fc33f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 24 12:22:32 BST 2021
  * get rid of special case in trackBisect

patch 9310dfccc50c05059783b2ecfd6472bacf486322
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 24 12:24:09 BST 2021
  * introduce an explicit type to track test failures

patch 0dd99dfc918c9a6928f13a3fdf76083a204fa8c5
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Apr 24 12:29:21 BST 2021
  * explicitly pass evidence of failure through trackNextBackoff

Attachments

• get-rid-of-special-case-in-trackbisect.dpatch
• patch-preview.txt
• unnamed

All the patches in this bundle are now screened and I think are in a
reviewable state. I think the only outstanding question for this set of
changes is whether to make 'minimisation' an option or now or just leave
it on unconditionally.

> All the patches in this bundle are now screened and I think are in a
> reviewable state. I think the only outstanding question for this set of
> changes is whether to make 'minimisation' an option or now or just leave
> it on unconditionally.

Minimization potentially gives better results, so I see no reason to
disable it. Or is there?

On 24/04/2021 19:42, Ben Franksen wrote:
> 
> Ben Franksen <ben.franksen@online.de> added the comment:
> 
>> All the patches in this bundle are now screened and I think are in a
>> reviewable state. I think the only outstanding question for this set of
>> changes is whether to make 'minimisation' an option or now or just leave
>> it on unconditionally.
> 
> Minimization potentially gives better results, so I see no reason to
> disable it. Or is there?

Well, it takes more time. I'm not sure how bad it could get if there are
lots of untestable states.

I think on balance minimisation should be controlled by
an option, so here it is.

I'll wait a bit before screening it.

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

patch d72195b6b878cb3fa6689996bbb84441fe4ecb19
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Apr 28 15:42:22 BST 2021
  * add option to enable failure shrinking in 'darcs test'
  
  Also add some documentation of "untestable" repository
  states.

Attachments

• add-option-to-enable-failure-shrinking-in-_darcs-test_.dpatch
• patch-preview.txt
• unnamed

Everything looks good, new features appreciated.