Shrink with the RoseTree

[bvenners]

Hi Chee Seng,

Please make a branch off of the feature-rose-tree-after-next branch, and change how we do shrinking. We currently use the shrink method on Generator:

https://github.com/scalatest/scalatest/blob/feature-rose-tree-after-next/jvm/core/src/main/scala/org/scalatest/prop/Generator.scala#L446

Prior to us adding RoseTree in there, this used to produce an Iterator that produced shrunken values from small to large. Because we went from small to large, we could stop as soon as we found one that also fails the test. If none of the shrunken values failed the test, we just went with the original failed value of type T. In the first version of this refactoring with RoseTree, I think we just wrap the values we were producing via the iterator in RoseTrees. I am not sure if we go small to large orlarge to small currently. Probably we still go in small to large order.

But to actually use the RoseTree, we need to go in large to small order. This means that if we find a failing case, we need to remember that and keep looking, until we get all the way down to the leaf node. The reason we must go in forward order is that is how the RoseTrees unfold, from larger to smaller.

The shrink algorithm is to traverse depth first while the data at the nodes cause the test to fail, then when a node causes the test to succeed, back up to the previous failure, take the next sibling, and repeat. At some point we will hit the end of the tree, and can search no further. The most recent node that caused the test to fail is the most shrunken value.

Here's an example tree from: https://www.well-typed.com/blog/2019/05/integrated-shrinking/

(True,1,'b')
├─ (False,1,'b')
│  ├─ (False,0,'b')
│  │  └─ (False,0,'a')
│  └─ (False,1,'a')
│     └─ (False,0,'a')
├─ (True,0,'b')
│  ├─ (False,0,'b')
│  │  └─ (False,0,'a')
│  └─ (True,0,'a')
│     └─ (False,0,'a')
└─ (True,1,'a')
   ├─ (False,1,'a')
   │  └─ (False,0,'a')
   └─ (True,0,'a')
      └─ (False,0,'a')

By the way, we repeat exactly the failing case at the top of our tree. I don't recall why I did that. It is OK and maybe better to get rid of that feature, or you can just skip that one because we know it fails the test. Anyway, I'm also not sure yet if we are composing properly, but in the above tree, let's say (True, 1, 'b') failed the test, so now we look for a shrunken variant. We'd look depth first, which would mean (False, 1, 'b'), (False, 0, 'b'), (False, 0, 'a'). Let's say that (False, 1, 'b') also fails the test. That would be our current shrunken winner, but there is more to unfold. We keep going depth first and try (False, 0, 'b'). Let's say that (False, 0, 'b') passes the test. In that case, we abandon this depth first search, back up to the previous failing node (which was (False, 1, 'b')), and move to its next sibling (if it has one, which is does). The next sibling is (True, 0, 'b'), so we try that. If that fails (failure means success in the sense that we got ourselves a new shrunken winner), we continue depth first. Next to try is (False, 0, 'b'). Let's say that fails the test also, so (False, 0, 'b') is now our shrunken winner. Continuing depth first we try (False, 0, 'a'). Let's say that one passes the test, so we back up to our most recent failure, (False, 0, 'b'), and move on to the next sibling. The next sibling is (True, 0, 'a'). Let's say that passes the test. At this point, moving up a notch would put us past our (False, 0, 'b'), so I suspect if there was another sibling to (False, 0, 'b') that we should try it, but in this case there are no more siblings. So we are done. (False, 0, 'b') is our most shrunken node and will end up in the test report.