跳到正文
参考文档 / ZLIB × LEAN

如何阅读契约

每个函数在手册中有一个条目。条目有两层。契约(前置条件、后置条件、效果)用文字描述函数, 读自 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。 没有定理陈述的部分尚未由证明确认,它也不是安全结论所必需的。

哪些目标已完成,见进度。

ZLIB × LEAN

目录

正在阅读如何阅读契约