本页内容

Guidedog / 文档 0.2.0

先有不变式，再谈算法

有用的不变量说明算法运行时什么始终成立，也说明算法结束后调用方可以依赖什么。先写不变量，再写循环。

前序遍历中的子树区间

假设树按前序输出：节点先于子节点输出，每个子树占连续区间。设 \(e_i\) 为节点 \(i\) 及其全部后代之后的第一个索引。

(3)\[\operatorname{subtree}(i) = [i,e_i), \qquad i < e_i \le N.\]

命题。 将索引推进到 \(e_i\)，即可跳过整个子树。

证明。 连续性保证所有后代位于 \(e_i\) 之前。右端不包含的定义保证所有后续节点位于 \(e_i\) 或之后。因此推进到该索引，恰好跳过子树。渲染器使用这些假设前，验证器会先检查。

图 5 父节点的区间包含各子节点的区间。

完整扫描只访问每个节点一次，遍历成本为 \(O(N)\)。跳过子树只需更新一次索引，但载荷处理仍有自身成本。常数时间跳过，不等于常数时间渲染。

先测量，后输出

渲染器先测量字节数 \(m\)。设调用方的输出容量为 \(c\)。

\[m \le c \quad \Longrightarrow \quad \text{可以开始输出}.\]

测量与输出遍历采用相同规则。成功输出必须恰好写入 \(m\) 字节。失败时不返回有效的部分产物。发布由宿主负责，因此未完成的字节不能替换先前输出。

缓存有效性

缓存键必须覆盖所有能改变结果的数据。只有源文件还不够：包含文件、模板、配置、引用查找、资源和适配器版本都会影响输出。记录的依赖仍一致时才允许复用。即使键匹配，输出缺失也会使复用失效。

测试在核心边界安装会失败的分配器，并比较输出内容，也审查导入。只统计分配而不检查结果，可能漏掉因拒绝申请而静默丢失文档内容的问题。