如何阅读契约
每个函数在手册中有一个条目。条目有两层。契约(前置条件、后置条件、效果)用文字描述函数,
读自 C 和 zlib.h。证明目标段落说明证明了什么:安全目标及其确切条件。
本页解释条目的各个部分,并把每个证明目标段落都会用到的短语统一定义一次。
条目结构
| 部分 | 含义 |
|---|---|
| C 签名 | 函数的 C 名称和参数类型,保留声明宏。 |
| 用途 | 调用者想执行的操作。 |
| 定义域 | 本契约覆盖哪些值、对象和调用历史。 |
| 前置条件 | 调用前要求的条件,包括经过检查的拒绝情况。 |
| 后置条件 | 各条所述返回路径上的结果和保证。 |
| 效果 | 读取、写入、分配、释放、文件操作和借用的存储。 |
| 边界情况或错误 | 空输入、部分输出和拒绝等会改变结果用法的情况。 |
| 证明目标 | 必需的安全目标及其 Lean 命题的条件,以及功能目标;功能目标不在计划内。 |
这些契约是聚焦的:聚焦契约描述通常的正确用法,所以它的前置条件有意比函数实际接受的窄。 前置条件之外、而 C 仍然处理的情况,写在“错误”“边界情况”或“聚焦范围之外”之下。 在前置条件之外,并不表示在 C 中是未定义行为。安全目标通常也覆盖这些情况; 它确切覆盖什么,由证明目标说明。
错误返回通常不会撤销已经完成的工作。输出、指针的推进、长度单元或文件位置可能已经改变。 应当按所述的返回路径和效果来使用结果。特别是,解码时的分配失败可能发生在部分输出之后。
阅读证明目标段落
在手册的每一页上,证明目标段落都由同样的五项组成,顺序如下。 函数没有必需目标的条目,则用一句话说明这一点,不列这五项。
| 项 | 内容 |
|---|---|
| 目标 | Lean 目标的名称,以及它是否必需;然后是类型恰好是该目标的定理。每个名称都链接到它的 Lean 源文件。 |
| 适用条件 | 目标的条件,用 C 的话写出并编号。每条后面的括号里是它的 Lean 名称。违反其中一条的调用不在覆盖范围内:既没有证明它安全,也没有说它不安全。 |
| 无条件覆盖 | 目标不加限制地全称量化的东西,例如标量参数的每个取值、每个输入字节序列和每一种分配结果。 |
| 保证 | 目标的结论,总是按这个顺序:调用返回;调用后的状态;写了什么;分配情况。 |
| 不在本目标内 | 目标的任何子句都不覆盖的情况:由另一个目标陈述的情况、没有任何目标覆盖的情况,以及该函数的功能目标陈述的内容。功能目标标为“不在计划内”,随后注明“已有定理证明它”或“未完成”。 |
一个目标可以有不止一个子句。初始化之外的流函数的目标、接受句柄的 gzip 文件函数的目标,以及 inflateBack 和 inflateBackEnd 的目标,
除了“对可达流的调用”“对句柄的调用”或“历史上的调用”这个子句之外,还有拒绝子句。这时“适用条件”说明每个条件属于哪个子句,
“保证”保持原来的顺序,并在每一项里点明是哪种情形。
这些段落里说的被拒绝的流,是指 C 的流检查不必通过坏指针去读就会拒绝的流:strm 是 NULL;或者它指向一个可读的流记录,
其 zalloc、zfree 或 state 是 NULL;或者其 state 指向一个类型相符的存活状态,而检查拒绝这个状态
(它的回指指针不指向这个记录;对 inflate,它的模式在 HEAD .. SYNC 之外;对 deflate,它的状态值不是检查接受的值)。
Lean 中的名字是 RefusedInflate 和 RefusedDeflate。zalloc 和 zfree 已设置、而 state 是垃圾指针、
指向已释放的状态或指向另一种流的状态的记录,既不是被拒绝的流,也不是可达流:
没有目标覆盖把它当作流、或当作复制的 source 的调用(见偏离记录)。
初始化函数以及复制的 dest 则接受这样的记录。
这些段落使用下列短语,含义固定。
| 短语 | 含义 | Lean |
|---|---|---|
| 返回 | 调用结束时没有未定义行为,没有内存错误,并且终止。C 的错误码(例如 Z_DATA_ERROR 或 Z_MEM_ERROR)也是返回。gzip 文件接口的六个读调用在读取预算下返回;没有这个预算时,它们的目标只陈述前两部分(见 Gzip 文件)。 |
执行是 .ok:既不是 Fault.ub,也不是 Fault.outOfFuel |
| 可达流 | 由一次返回 Z_OK 的初始化调用产生的流(当时堆是库堆,zalloc 和 zfree 各自是 NULL 或默认函数),或者一次返回 Z_OK 的复制的目的流;此后可以接任意多步,每步是下面两种之一:一次带着合法参数、已经返回(返回码任意)的允许的调用;调用者对 next_in、avail_in、next_out、avail_out 或对流不拥有的内存的一次修改。可达流使用默认分配器。 |
StreamReachable |
| 流自己的块 | 状态记录,以及库为这个流分配的缓冲区:对 inflate 是窗口;对 deflate 是窗口、两个哈希数组和待输出缓冲区。z_stream 记录本身属于调用者,另行点名。 |
StreamOwned |
| 句柄自己的块 | 对 gzip 文件句柄:句柄记录、它的路径、它的错误消息、它的缓冲区和它的编解码状态。 | GzOwned |
| 平台大小上界 | 每个字节对象少于 2^63 字节。这是平台的事实,不是调用者的责任(见平台)。 |
ByteObjectsFit |
| 精确的分配账本 | 调用后已分配的块,等于调用前已分配的块,加上流新拥有的块,减去流原先拥有而不再拥有的块。此外没有任何分配或释放。这就是无泄漏子句。对 gzip 文件句柄,把“流”读作“句柄”。 | LiveChange |
| 库堆 | 对模型内存的条件,不是对调用者的条件:块编号是一致的(下一个未用编号及其之后没有存活的对象,每个编号只有一个对象),并且库的常量表都在。 | Fresh、Uniq、LibraryGlobals |
| 每一种分配结果 | 不论哪些 malloc 调用失败,目标都成立。 |
目标对堆全称量化,而分配预言是堆的一部分 |
| 世界 | gzip 文件函数在进程之外看到的东西:文件、打开的描述符、errno,以及每次系统调用的结果。“在每个世界里”包括每次 open、read、write、lseek 和 close 的每一种允许的结果。 |
Fs,其良构性由 FileSystem 给出 |
“保证”背后的四个子句,见安全性中的说明和例子。 目标、历史和拒绝的定义见术语表。 按函数查覆盖情况用一张表给出每个函数的定理。
定义域与效果彼此独立
受限定义域要求的不只是参数类型中的值。指针通常必须指向存活的存储;句柄需要合法的调用历史; 校验和组合可能要求一个为正确长度生成的算子。
完整类型定义域覆盖所选构建中参数类型的每个值,包括规定的拒绝。 即使函数覆盖每个标量值,它的整体定义域仍可能受限,因为它的指针必须指向有效的存储。 这里区分的不是有限与无限,也不是有界与无界。
| 效果 | 含义 |
|---|---|
| 纯计算 | 计算出结果,不读调用者内存,也不改变状态。它可以使用固定的库常量或表。 |
| 只读 | 读调用者内存或流状态,并保持它们不变。借出的结果仍归库所有。 |
| 有状态 | 可能写调用者的目的位置或库的状态,分配或释放存储,调用回调,或执行文件 I/O。 |
这些标签描述的是不同的性质。纯计算可以有受限定义域。 一个往可选的标量结果里写值的查询具有写效果,即使它的流没有改变。
示例:组合两个 CRC
crc32_combine_op 不必再读一遍原来的字节串:
定义域:受限定义域。
前置条件:crc1 是 A 的 CRC;crc2 是 B 的 CRC;
op 是根据 B 的可表示非负长度生成的算子。
后置条件:结果是 A 后接 B 的 CRC。
效果:纯计算。
A 的 CRC 指从零开始对 A 调用 crc32。A 和 B 是普通的字节序列,不需要特殊的 CRC 类型。
即使调用不读调用者内存,生成的算子和正确的长度仍然重要。
零长度和负长度的情况见校验和条目,与标准的一致性见格式关系。
共同的阅读规则
除非条目另有说明:
- 构建是默认 LP64 Linux 静态构建,使用默认分配器。
- 可读或可写的范围在整个调用期间都包含所述数量的字节。
- 长度放得进它的参数类型。
- 存活的句柄已经初始化、尚未关闭,并且被顺序地使用;调用者不修改库拥有的状态。
契约说什么。 在前置条件下,调用终止且没有未定义行为,满足后置条件, 并且只改变效果之下点名的内存。分配失败、部分结果和清理都在其中。 共同的所有权规则见共享流规则。
证明了什么。 只有安全性:证明目标下写出的目标,在那里列出的条件下成立。 契约与目标可以不同:
- 目标的条件比
zlib.h窄时,偏离记录中有一行。 - 后置条件描述功能行为:返回值、输出字节、状态变化。它读自 C。 没有定理陈述的部分尚未由证明确认,它也不是安全结论所必需的。
哪些目标已完成,见进度。