组合式收缩（Compositional Shrinking）：Hypothesis 如何通过“收缩输入而非输出“让策略组合保留收缩能力

测试开发工具【免费下载链接】hypothesisThe property-based testing library for Python项目地址https://gitcode.com/gh_mirrors/hy/hypothesis点击查看免费下载导读本文是 Hypothesis 官方博客收缩shrinking系列的第二篇深入剖析属性测试中收缩shrinking机制的两种经典实现路径以 theft、QuickTheories 为代表的值驱动收缩value-based shrinking以及以 clojure.test.check 的玫瑰树rose tree和 Hypothesis 的统一中间表示为代表的输入驱动收缩input-based shrinking。读完本文你将理解为什么integers().map(lambda x: x * 2)这种最简单的策略组合在值驱动收缩下无法保留收缩能力而 Hypothesis 通过收缩输入等价于收缩输出的核心思想让任意策略组合都能自动获得正确、保不变的收缩结果——这正是现代属性测试库永远不需要用户手写 shrinker的根本原因。背景从类型驱动收缩到值驱动收缩在上一篇《集成式收缩Integrated shrinking》中原文档见 website/content/2016-12-05-integrated-shrinking.md我们讨论了以 Haskell QuickCheck 为代表的**类型驱动收缩type based shrinking**的根本缺陷收缩行为由值的类型决定与生成过程无关。这会导致生成器和收缩器各说各话——例如integers().map(lambda x: x * 2)生成的全是偶数但基于类型的收缩器会认为1 也是合法的整数而把失败的测试用例缩到 1从而把n 4的失败缩成n % 2 0的失败得到完全误导性的最小反例。当时文章忽略了一个折中方案halfway house值驱动收缩value-based shrinking。它虽然不如类型驱动那么糟但依然存在显著问题。这种方案在若干实现中可见——其代表性库包括 theft 和 QuickTheories。值驱动收缩不再依据类型而是采用经典的收缩 API接收一个值返回该值所有可能收缩结果的惰性列表lazy list。用户或库作者为每个可收缩的东西定义一个函数value - [smaller values]。这种方案解决了类型驱动收缩的主要问题收缩不再与生成过程脱节但仍然比较脆弱并且——关键的一点——它的组合性远不如 Hypothesis 或 test.check 所采用的方法。核心论点收缩不应基于任何具体值作者在文中明确提出理想形态除了不基于被生成值的类型之外收缩也不应该基于实际生成出来的值。乍看反直觉不基于值还能基于什么但这在实践中效果很好。要理解这一点需要先看值驱动方案在组合上的致命伤。经典反例map 组合下无法定义收缩考虑上一篇中的例子from hypothesis import given from hypothesis.strategies import integers even_numbers integers().map(lambda x: x * 2) given(even_numbers) def test_even_numbers_are_even(n): assert n % 2 0这里我们拿到一个策略用map函数把它组合成一个新策略。假设 Hypothesis 的策略实现早期确实如此长这样class SearchStrategy: def generate(self, random): raise NotImplementedError() def shrink(self, value): return ()也就是说我们能生成一个值也能收缩一个已经生成的值。默认情况下子类不知道如何生成必须实现generate也收缩不了任何东西除非子类自己提供shrink。这正是 theft 或 QuickTheories 采取的路线。问题在于在这个模型下上面用到的map不可能在保留收缩的前提下实现。要收缩map生成的值你必须能求逆你正在组合的那个函数——把生成值映射回产生它的原始值收缩原始值再经过映射函数得到收缩后的输出。而在一般情况下函数的求逆是不可能的即使你的语言真的提供了某种求逆工具绝大多数语言也没有。Hypothesis 和 test.check 都支持远比map复杂的策略组合两者的操作集合相同但 Hypothesis 的底层实现在更复杂的组合上表现更好例如 Hypothesis 支持flatmap、composite装饰器、deferred递归策略等。但即使是最简单的map组合只要需要收缩任意值就会失败。关键洞见收缩输出几乎总是等价于收缩输入为了收缩输出几乎总是只要收缩输入就够了。理论上确实存在更简单的输入导致更复杂的输出的函数但在实践中这种情形足够罕见以至于完全可以接受在这些情况下测试输出稍复杂一点。于是收缩map策略输出值的方法变得极其简单直接收缩第一个策略生成的原始值然后把结果喂给映射函数即可。这要求底层 API 必须支持这种作用于生成过程而非最终值的收缩方式。两条实现路径路径一test.check 的玫瑰树Rose Treetest.check 的做法是不再生成单个值而是生成一整棵**惰性的值树**树中包含每个值的收缩候选。这就是所谓的玫瑰树rose tree其每个节点既是值又是其收缩子树。Reid Draper 在Writing a simple property-based library一文中有更详细的论述。这种结构让map变得非常容易只需把映射函数应用到整棵玫瑰树上——既作用于初始生成的值也作用于所有收缩后的子值。换言之map从值→值的变换升级为树→树的变换收缩关系被结构性保留。路径二Hypothesis 的统一中间表示Unified IRHypothesis 的实现更复杂原文表示将留待后续文章详述但核心思想是把收缩输出等价于收缩输入推演到逻辑终点Hypothesis 拥有一个统一的中间表示IR所有生成都基于它。现代 Hypothesis 源码正是这样组织的整个hypothesis/internal/conjecture/目录就是围绕这份 IR 构建的。关键在于策略只是一个函数它接收一个 IR 对象并返回一个值。MappedStrategy天然免费获得收缩它做同样的事情——内部先从mapped_strategy画出一个值再应用pack映射函数见 strategies.py 中MappedStrategy.do_draw的实现def do_draw(self, data: ConjectureData) - MappedTo: ... for _ in range(3): try: data.start_span(MAPPED_SEARCH_STRATEGY_DO_DRAW_LABEL) x data.draw(self.mapped_strategy) result self.pack(x) data.stop_span() ... return result except UnsatisfiedAssumption as err: ...可以看到map的底层实现就是从底层策略画一个值调用pack(x)——没有定义任何针对映射后值的手写收缩逻辑。收缩发生在 IRchoice 序列层面与具体值无关。策略可以提供可能有用的收缩提示但对收缩过程本身几乎没有控制权。也就是说收缩器shrinker工作在选择序列choice sequence之上而不是在用户可见的值之上。这可以从 shrinking 子模块的目录结构 看出integer.py、floats.py、collection.py、ordering.py、string.py、bytes.py等全部是针对中间表示片段整数选择、浮点选择、集合选择、顺序选择……的局部收缩器而非针对值类型的收缩器。这一设计带来最直接的好处map之后连_invert都不需要。当前仓库中的 MappedStrategy._invert 只有在 pack 是 dict 类构造器这类极少数可逆情形下才尝试求逆否则直接抛CannotInvert——因为收缩根本不需要求逆shrink 阶段是拿更小的选择序列去重放replay生成过程而不是拿更小的值去逆推。从源码看 IR 收缩的实际调用链当前实现中一次完整的生成 收缩的简化调用链是生成ConjectureData通过data.draw(strategy)驱动策略的do_draw(data)策略内部通过data.draw_integer(...)、data.draw_boolean(...)等原语调用把每一次选择追加到data.nodeschoice 序列中。draw的完整逻辑见 data.py 中的ConjectureData.draw。收缩shrinker 在choice 序列上进行。Chooser与ChoiceTreechoicetree.py记录收缩过程中做出的选择Chooser.choose(...)返回一个不会导致分支耗尽exhausted的元素ChoiceTree的每个TreeNode记录哪些子选择已经死亡DeadNode从而确保每次收缩尝试都探索新的可能性。验证每次新的 choice 序列都会被重放——用更小的选择重新执行一次完整的生成与测试看是否仍然触发失败。Shrinkercommon.py维护当前值、谓词与已访问集合__seen目标是更小更简单。因为收缩作用于选择序列而非最终值所以生成与收缩天然不可能脱节任何能通过该策略生成的值其收缩结果也必然来自同一策略所有生成时成立的约束例如x * 2必为偶数在收缩后依然成立。测试佐证收缩后的值仍满足策略约束仓库中的测试直接印证了这一点。以 test_slices.py 中的test_slices_will_shrink为例def test_slices_will_shrink(size): sliced minimal(st.slices(size)) assert sliced.start 0 or sliced.start is None assert sliced.stop 0 or sliced.stop is None assert sliced.step is None它使用测试工具minimaltests/common/debug.py内部通过givenPhases.generate/Phase.shrink找到满足条件的最小值验证st.slices(size)收缩到最小之后所有切片字段都落在策略允许的范围内——start/stop收缩为 0 或Nonestep收缩为None。收缩结果仍然遵守生成器的约束这正是收缩输入设计正确性的直接体现。另外test_map.py 中的test_identity_map_is_noop验证了恒等映射被优化为原策略s.map(lambda x: x) is s说明map被设计为纯粹的、不引入任何额外收缩行为的组合子。两种路径的比较从零实现属性测试库时选哪条作者明确给出结论Hypothesis 的实现更优。基于统一 IR策略组合map/filter/flatmap/one_of/composite……都自动保留收缩组合自由度最高。test.check 的实现也完全体面并且对从零实现一个属性测试系统的人而言更容易照搬玫瑰树的概念简单直观map就是树的函子映射fmap。无论从哪条路径起步都要带走同一个关键思想可以用收缩输入来实现收缩输出策略的组合方式必须保留收缩能力。组合性对照表方案收缩对象map 组合是否保留收缩实现复杂度类型驱动收缩Haskell QuickCheck 早期思路值 类型否缩到类型合法但不属于策略约束的值低但正确性差值驱动收缩theft、QuickTheories值返回惰性收缩列表否需要对映射函数求逆一般不可能中玫瑰树收缩clojure.test.check整棵惰性值树是对树整体施加映射中高统一 IR 收缩Hypothesis选择序列与具体值无关是映射只是函数套函数高但组合性最好用户体验层面的收益这套设计的实际价值在于用户几乎或完全不需要自己编写收缩函数。在类型驱动或值驱动的世界里复杂数据往往需要用户配套提供 shrinker否则收缩质量很差而在 Hypothesis 中只要能生成就能收缩。收缩与生成出错的潜在位置大幅减少。生成器与收缩器不再需要同步维护——因为它们是同一份代码收缩只是用更小的选择序列重新执行生成。这从根源上消灭了一整类生成器改了、收缩器忘了改的 bug。总结从 website/content/2016-12-08-compositional-shrinking.md 的论述出发结合当前仓库源码可以确认收缩不应基于值的类型也不应基于值本身而应基于产生这些值的生成过程Hypothesis 即选择序列 IR收缩输出 ≈ 收缩输入是让map、flatmap、filter、one_of等一切策略组合自动保留收缩能力的钥匙从源码看Hypothesis 的 SearchStrategy.map 只是包了一层 MappedStrategy后者在do_draw中画底层值 应用 pack收缩器则在 choice 序列层面 工作——两者解耦又天然一致。如果你正在实现一个属性测试库请从玫瑰树或统一 IR 起步如果你正在使用属性测试库请确认它属于策略组合保留收缩阵营——这决定了失败用例的缩减结果是否真的有意义。赞分享测试开发工具【免费下载链接】hypothesisThe property-based testing library for Python项目地址https://gitcode.com/gh_mirrors/hy/hypothesis点击查看免费下载相关推荐Hypothesis项目中的策略收缩设计指南Hypothesis项目中的策略收缩设计指南 引言为什么策略收缩如此重要 在基于属性的测试Property Based Testing中Hypothe测试开发工具如何利用Hypothesis进行高效属性测试从策略到收缩器的完整指南如何利用Hypothesis进行高效属性测试从策略到收缩器的完整指南 Hypothesis是一个功能强大、灵活且易于使用的属性测试库它通过自动生成测试用例来测试开发工具PySCF中使用非收缩基组进行CCSD/CCSD(T)密度拟合计算PySCF中使用非收缩基组进行CCSD/CCSD T 密度拟合计算 在量子化学计算中耦合簇 CCSD/CCSD T 方法是获得高精度电子相关能的重要工具。Py科学计算科研高性能计算上一篇【亲测免费】 数据连接器SDK及示例Power Query与Power BI的完美伴侣下一篇如何安全移除npm全局sudo权限npm-g_nosudo工具10分钟快速上手教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考