test.check

Rose-filter may assume too much

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

Gary Fredericks commented that the rose-filter will discard a node and all of its children if the node doesn't pass the predicate. On the other hand, some of its children may pass the predicate.

Reid Draper said that he has attempted to solve this previously, but it was not evident how one should exclude a node from the tree. One solution considered was to replace the node with all of its children, then repeat the procedure recursively.

Gary Fredericks came with another solution, where you promote the first child to the root and concatenate the remaining children to the first child's children.

Original issue - GitHub #33

Activity

Hide
Scott Feeney added a comment - - edited

Am I correct in thinking the motivation here is to make such-that applied to generators still find the minimal failing example in all cases?

If so, a complete fix seems impractical. Say we have a tree that lets us shrink from C to B to A, but B fails the predicate while C and A pass. Then it's fairly straightforward to keep A in:

     C
    / \
   B  ...
  / \
 A  ...

becomes

     C
    / \
   A  ...

But what if multiple levels are taken out? Say the shrink is like Y→X1→X2→X3→...→Xn→W where Y and W pass the predicate but all the Xs don't? If we accommodate that, then a single call to (first (children Y)) could, in the worst case, require eager exploration of the entire tree under Y, which could easily be exponential.

Show
Scott Feeney added a comment - - edited Am I correct in thinking the motivation here is to make such-that applied to generators still find the minimal failing example in all cases? If so, a complete fix seems impractical. Say we have a tree that lets us shrink from C to B to A, but B fails the predicate while C and A pass. Then it's fairly straightforward to keep A in:
     C
    / \
   B  ...
  / \
 A  ...
becomes
     C
    / \
   A  ...
But what if multiple levels are taken out? Say the shrink is like Y→X1→X2→X3→...→Xn→W where Y and W pass the predicate but all the Xs don't? If we accommodate that, then a single call to (first (children Y)) could, in the worst case, require eager exploration of the entire tree under Y, which could easily be exponential.
Hide
Reid Draper added a comment -

Indeed. I believe your analysis is correct. And so far, not having this optimization has not resulted in sub-optimal shrinks, as far as I know. Perhaps we should close this issue, and re-open it if we're able to find a specific test whose shrinking is poor because?

Show
Reid Draper added a comment - Indeed. I believe your analysis is correct. And so far, not having this optimization has not resulted in sub-optimal shrinks, as far as I know. Perhaps we should close this issue, and re-open it if we're able to find a specific test whose shrinking is poor because?
Hide
Scott Feeney added a comment - - edited

That seems like a reasonable course of action. But I have a question, and feel free to stop me if this issue isn't the correct place to discuss this, but what do people actually use such-that for? Would it not be preferable to use fmap?

For example: generating even integers. (gen/such-that even? gen/int) has a potential problem finding the optimal shrink, but (gen/fmap #(* 2 %) gen/int) does not. Also, once every thousand runs, the former will error out without finding an appropriate value; the latter is reliable. It does produce larger values, but if it's important, you could cancel that out with:

(defn half-size [f]
  (gen/sized
    (fn [size]
      (gen/resize (/ size 2) f))))

(gen/fmap #(* 2 %) (half-size gen/int))

Isn't it better to find a mapping from all values to the subset of values you want? In what case would that not be possible (yet such-that is sufficiently reliable)?

Show
Scott Feeney added a comment - - edited That seems like a reasonable course of action. But I have a question, and feel free to stop me if this issue isn't the correct place to discuss this, but what do people actually use such-that for? Would it not be preferable to use fmap? For example: generating even integers. (gen/such-that even? gen/int) has a potential problem finding the optimal shrink, but (gen/fmap #(* 2 %) gen/int) does not. Also, once every thousand runs, the former will error out without finding an appropriate value; the latter is reliable. It does produce larger values, but if it's important, you could cancel that out with:
(defn half-size [f]
  (gen/sized
    (fn [size]
      (gen/resize (/ size 2) f))))

(gen/fmap #(* 2 %) (half-size gen/int))
Isn't it better to find a mapping from all values to the subset of values you want? In what case would that not be possible (yet such-that is sufficiently reliable)?

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated: