开发工具测试【免费下载链接】fast-checkProperty based testing framework for JavaScript (like QuickCheck) written in TypeScript项目地址https://gitcode.com/gh_mirrors/fa/fast-check点击查看免费下载本文以 fast-check 官方博客 Advent of PBT 2024 · Day 8Uncompress old text messages为蓝本完整复现圣诞老人恢复无空格短信这道挑战题先分析精灵们实现的隐藏缺陷再构造最小反例最后用 fast-check 的差分属性测试自动发现并定位 bug。读完本文你将掌握黑盒算法 参考实现差分对比这一在 fast-check 中极为实用的排障套路并理解fc.property、fc.assert、fc.array、fc.string等核心构件的组合用法。挑战背景为压缩短信重新加回空格在短信按字符数计费的年代为了节省存储与传输空间圣诞老人与精灵们约定所有消息一律省略空格发送单词直接首尾相连。如今存储与通信技术早已不是瓶颈圣诞老人希望把这些压缩消息还原成可读的原始文本——也就是把空格重新插回去。由于消息量巨大精灵们开发了一个自动化算法。算法的输入输出约定如下输入一压缩消息单个字符串由若干单词无空格拼接而成输入二有效单词数组字典中所有合法单词均为a到z的小写字母且每个单词至少包含一个字母输出若存在某种基于字典的合法重建方式返回带空格还原后的消息例如helloworld→hello world若字典不完整、不存在任何合法重建则原样返回压缩消息。挑战任务明确而直接找出一组输入——一个单词列表加一条压缩消息——能让精灵的实现产生错误结果证明其中藏着 bug。圣诞老人的圣诞节能否如期进行就看这一步了。精灵的实现藏在源码里的过早短路挑战的在线 Playground 通过 AdventPlayground.tsx 内嵌 StackBlitz 环境呈现预装fast-check、vitest、typescript启动命令为npx vitest --watch --reporterverbose被测试的可疑实现保存在 buggy.mjs 中// ts-check export default function respace(spacelessMessage, words) { const match respaceInternal(spacelessMessage, words, 0); if (match undefined) { return spacelessMessage; // 无法重建时原样返回压缩消息 } return match.join( ); } function respaceInternal(spacelessMessage, words, startIndex) { if (startIndex spacelessMessage.length) { return []; // 已处理完整个消息 } for (const word of words) { if (spacelessMessage.startsWith(word, startIndex)) { const subMatch respaceInternal(spacelessMessage, words, startIndex word.length); if (subMatch ! undefined) { return [word, ...subMatch]; } else { return undefined; // ← 问题所在 } } } return undefined; }这是一个经典的递归回溯分词word break实现从当前位置起依次尝试用字典中的每个单词匹配前缀匹配成功就递归处理剩余部分。表面看逻辑自洽但把respaceInternal与 AdventOfTheDay.tsx 中内嵌的**参考实现reference implementation**逐行对比缺陷立刻显现function respaceInternal(spacelessMessage: string, words: string[], startIndex: number): string[] | undefined { if (startIndex spacelessMessage.length) { return []; } for (const word of words) { if (spacelessMessage.startsWith(word, startIndex)) { const subMatch respaceInternal(spacelessMessage, words, startIndex word.length); if (subMatch ! undefined) { return [word, ...subMatch]; } // 注意参考实现中没有 else 分支继续尝试下一个单词 } } return undefined; }从源码结构可以清晰推断出 bug 的性质精灵版在当前单词匹配前缀、但后续无法完整重建时直接return undefined放弃了继续尝试字典中剩余单词的机会。这是一次过早的失败短路——算法永远只尝试字典中第一个能匹配前缀的单词一旦这条路走不通就整体宣告失败而不是回溯换一个候选词。参考实现则没有这个else分支会遍历完所有匹配前缀的单词后才放弃。两者行为的分歧点正是我们要找的 bug 触发条件。最小反例追踪一次错误的放弃如何构造一个让精灵版出错、参考实现却成功的输入关键思路让字典中排在前面的单词恰好匹配消息前缀但用它会走进死胡同同时排在后面的另一个单词同样匹配前缀且能走通全路。以消息aab、字典[aa, a, ab]为例逐步追踪精灵版respaceInternal(aab, words, 0)startIndex 0遍历字典先检查aaaab.startsWith(aa, 0)为true于是递归respaceInternal(aab, words, 2)在剩余部分b上aab从索引 2 开始依次尝试aa、a、ab全部false返回undefined回到第 1 步subMatch undefined精灵版直接返回undefined外层respace于是原样输出aab。但字典里明明存在合法分词先取a索引 0 匹配再取ab索引 1 起匹配可还原为a ab。参考实现会继续遍历到a从而得出正确结果。于是这一组输入就是有效的反例压缩消息aab单词列表aa、a、ab精灵版输出aab错误地认为无法重建正确输出a ab类似的失败模式还有很多比如消息ababa配字典[ab, aba, ba]等本质都是贪心锁定第一个前缀匹配导致错过更优/可行的分词。用 fast-check 差分测试自动捕获 bug手动构造反例只是热身真正的力量在于把精灵版 vs 参考实现的对比写成一条差分属性differential property让 fast-check 自动生成大量输入去找茬。核心代码import { test, expect } from vitest; import * as fc from fast-check; import respace from ./advent.js; // 参考实现完整的回溯分词可从 AdventOfTheDay.tsx 提取 function referenceRespace(spacelessMessage, words) { const match referenceInternal(spacelessMessage, words, 0); return match undefined ? spacelessMessage : match.join( ); } function referenceInternal(spacelessMessage, words, startIndex) { if (startIndex spacelessMessage.length) return []; for (const word of words) { if (spacelessMessage.startsWith(word, startIndex)) { const subMatch referenceInternal(spacelessMessage, words, startIndex word.length); if (subMatch ! undefined) return [word, ...subMatch]; } } return undefined; } test(精灵版与参考实现行为一致, () { fc.assert( fc.property( fc.array(fc.string({ minLength: 1, maxLength: 5 }), { minLength: 1, maxLength: 8 }), fc.string({ minLength: 1, maxLength: 20 }), (words, spacelessMessage) { expect(respace(spacelessMessage, words)).toBe(referenceRespace(spacelessMessage, words)); }, ), ); });这个属性里用到的每个构件都能在仓库文档中找到出处fc.string({ minLength, maxLength })生成单词与消息参数含义见 string.mdminLength默认0、maxLength默认0x7fffffff受 larger-entries-by-default.md 中 size 机制约束。这里用minLength: 1保证单词非空与题目每个单词至少一个字母一致fc.array(arb, { minLength, maxLength })生成单词列表参数说明见 array.mdminLength默认0maxLength默认0x7fffffff可通过size调整数组期望长度默认small时数组元素通常落在 010 之间fc.property(...arbitraries, predicate)把生成器与断言组合成属性fc.assert负责执行并失败时抛错两者签名见 properties.md 与 runners.mdfc.assert失败时抛出的错误会自动格式化包含最小化后的反例与复现种子。若想严格贴近题目的a-z约束可改用fc.stringMatching(/^[a-z]$/)用法见 string.md 组合器或用.filter((s) /^[a-z]$/.test(s))想要字典单词互不重复可用fc.uniqueArray(arb)同见 array.md。运行这条属性后fast-check 会迅速命中类似aab/[aa,a,ab]的反例并在断言失败后自动**收缩shrink**到最小化输入把 bug 复现路径压缩到最易读的形态——这正是属性测试相对手工枚举的核心价值。补充一条自洽性属性除了差分对比还可以为算法单独验证一条结构性不变量只要输出不是原始压缩消息那么去掉输出中的所有空格后必须恰好还原回输入消息分词不能丢字也不能多字fc.assert( fc.property( fc.array(fc.string({ minLength: 1, maxLength: 5 }), { minLength: 1, maxLength: 8 }), fc.string({ minLength: 1, maxLength: 20 }), (words, spacelessMessage) { const out respace(spacelessMessage, words); if (out ! spacelessMessage) { expect(out.replace(/ /g, )).toBe(spacelessMessage); } }, ), );这类输出重构后等于输入的性质即使在没有参考实现时也能独立守住算法的基本正确性。挑战背后的判定机制从源码看在线验证逻辑在线表单是如何判定你的答案是否真的戳中 bug 的答案在 AdventOfTheDayBuilder.tsx 的onSubmit中const inputs parser(answer); if (isEqual(postAdvent(buggyFn(...inputs)), postAdvent(referenceAdvent(...inputs)))) { lastError The input you provided seems to be working well: Santa is looking for a bug!; return; } lastError null; localStorage.setItem(storageKey, answer);即把你的输入分别喂给buggyAdvent精灵版与referenceAdvent参考实现用 lodash 的isEqual比较两者输出只有输出不一致答案才被接受并通过localStoragekey 为aopbt24-day8记住你的成果。第 8 天的输入解析器见 AdventOfTheDay.tsx 的parser约定第一行是压缩消息其余每行是一个单词所有内容只能由a-z组成例如占位示例messagewithoutanyspace message space nothing empty without any同时 Playground 页面AdventPlayground.tsx会自动生成一个以vitestfast-check搭建的advent.test.ts骨架含函数签名respace(spacelessMessage: string, words: string[]): string;方便你在浏览器里直接开写差分属性并观察失败反例它同样提供下载入口可以把buggy.mjs拉到本地用 vitest 复现。总结第 8 天挑战浓缩了属性测试中最实用的一招当你面对一个黑盒实现、又恰好能写出或从题目说明中推导出一个参考实现时差分属性测试会自动把两者的行为分歧暴露出来。本例中精灵版的 bug 是递归回溯里的一次过早短路——respaceInternal在子匹配失败时直接放弃整条路径没有尝试字典中其余同样匹配前缀的单词反例aab[aa,a,ab]以最少的字符完整呈现了这一缺陷。这套方法完全可迁移到真实工程为重构后的函数、第三方依赖的算法、竞品实现的接口编写差分属性用fc.property组合fc.array、fc.string、fc.stringMatching、fc.uniqueArray等任意生成器完整清单见 arbitraries 文档再用fc.assert执行并自动收缩反例runner 与参数细节见 runners.md——让随机生成、最小化复现这些原本枯燥的工作全部交给 fast-check 完成。赞分享开发工具测试【免费下载链接】fast-checkProperty based testing framework for JavaScript (like QuickCheck) written in TypeScript项目地址https://gitcode.com/gh_mirrors/fa/fast-check点击查看免费下载相关推荐用 fast-check 破解“去重黑盒”Advent of PBT 2024 Day 2 实战解析用 fast check 破解“去重黑盒”Advent of PBT 2024 Day 2 实战解析 导读 本篇技术指南以 fast check 官方“Adv开发工具测试fast-check 实战用「Advent of PBT Day 1」破解黑盒排序算法 Bugfast check 实战用「Advent of PBT Day 1」破解黑盒排序算法 Bug 本文以 fast check 官方博客系列 Advent of开发工具测试用 fast-check 定位条形码递增算法中的数值精度陷阱Advent of PBT 2024 第 6 天实战解析用 fast check 定位条形码递增算法中的数值精度陷阱Advent of PBT 2024 第 6 天实战解析 导读 本文围绕 fast check开发工具测试上一篇3种突破性策略彻底掌控你的Steam成就数据下一篇oh-my-openagent 跨平台 CI 超时问题实录从 Windows 上 5000ms 预算越界的 RED 证据到平台感知超时修复创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考