在递归生成器中启用收缩

Question

我使用 test.check 为搜索引擎编写了一个 AST 生成器。它运行良好，但不知何故，递归生成器不会“垂直”收缩，而是仅按垂直方向收缩。例如，假设这个 AST 失败了



{:op :and
 :args [{:op :and
         :args [{:op :term ...}
                {:op :term ...}
                {:op :term ...}]}]}



收缩后



{:op :and
 :args [{:op :and
         :args [{:op :term ...}]}]}



问题出在 `{:op :term}` 上，但不知何故，test.check 也没有尝试删除递归的 `:and` 节点。不是什么大事，但这是一个很棒的特性。

Answer 1

评论者：gfredericks

这使用的是 {{gen/recursive-gen}} 吗？

Answer 2

评论者：halgari

是的，我在使用 recursive-gen。

Answer 3

_评论者：gfredericks_

这似乎是相同的问题？


(quick-check 10000
             (prop/for-all [tree (gen/recursive-gen gen/vector gen/large-integer)]
               (->> tree
                    (tree-seq coll? seq)
                    (not-any? #{4242}))))
;; =>
{:result false,
 :seed 1466641044276,
 :failing-size 151,
 :num-tests 3152,
 :fail [[[-250312923371676 -2634403398808308]
         [-134580]
         1190117809715
         [1736827773692]
         [91379147228 281572852]
         []
         []
         [264322377680727]
         [-2 -2005122340306]
         []
         []
         [2133414023]
         []
         [-7203148411369 2093087]
         [-1 -1]
         [-350804570003194 -24726]
         [-2145238760990835556]
         [-4410884650149229158 27914810]
         []
         [21126727]
         [816412492 102]
         [1]
         [-119 -2132126120873]
         [50]
         [1590594626470485464 -555554916273244]
         [4242 322325]]],
 :shrunk {:total-nodes-visited 57,
          :depth 11,
          :result false,
          ;应该缩减到`4242`}
          :smallest [[[4242]]]}}

Answer 4

评论者：gfredericks

我并不完全确定是否有干净的解决方案，但提醒自己：首先尝试缩减到子树

Answer 5

评论者：gfredericks

如果TCHECK-112得以解决，也可能适用于此处。

Answer 6

评论者：gfredericks

我认为对此有一个有点乱但还算是可行的解决方案。

要缩减到子节点，你需要知道它们是什么，包括它们的缩减树。

实现这一点的 一种方法是让 {{recursive-gen}} 将传递给用户函数的生成器包装在某种仪表中，该仪表跟踪生成器使用过的参数（或其返回值），然后在最终缩减树前面添加项，尝试直接缩减到这些值。

对此方法的一个小反对意见是，只是因为调用了传入的生成器，并不意味着由这些调用生成的值实际上被使用了（例如，它们可能已被 {{such-that}} 过滤掉）。

然而，我认为这最多只会导致在最坏情况下出现的可能混淆，因为传递给用户函数的生成器生成的任何内容对于整个结构而言都是有效的。所以，即使它没有关联，也不应该是无效的进行缩小。

Answer 7

参考：https://clojure.atlassian.net/browse/TCHECK-110（由halgari报告）