在递归生成器上启用收缩

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报告）