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

目标的命题

这些目标说的不是单个函数:完整的调用序列、对无效流或句柄的拒绝、各目标的前提可以满足,以及默认 zlib 流的往返。每个函数自己的目标在该函数的页面上。哪些已经完成,见结论的状态;完整的序列契约是功能目标,它们各自的状态写在下面每一条旁边。

调用序列的安全

inflate_sequence_safety

/-- **Safety of every permitted inflate call sequence** (the safety half of
`Goal.inflate_sequence`): every reachable stream satisfies the stream invariant, and one more
permitted call returns without a fault, keeps the invariant, writes only the stream's own blocks,
the stream record, the gzip header record and the declared caller regions, and changes the live
blocks exactly as the allocation ledger says (no leak); `inflateEnd` frees every block the stream
owns. The functional clauses of `Goal.inflate_sequence` are not planned (`docs/en/progress.md`,
"Not planned"). -/
def Goal.inflate_sequence_safety : Prop := StreamSequenceSafety .inflate
完整上下文 ↗

deflate_sequence_safety

/-- **Safety of every permitted deflate call sequence** (the safety half of
`Goal.deflate_sequence`): every reachable stream satisfies the stream invariant, and one more
permitted call returns without a fault, keeps the invariant, writes only the stream's own blocks,
the stream record and the declared caller regions, and changes the live blocks exactly as the
allocation ledger says (no leak). The functional clauses of `Goal.deflate_sequence` are not planned. -/
def Goal.deflate_sequence_safety : Prop := StreamSequenceSafety .deflate
完整上下文 ↗

inflate_back_sequence_safety

/-- **Safety of every permitted callback-decoder sequence** (the safety half of
`Goal.inflate_back_sequence`). A null stream is refused. Every reachable history leaves a valid
state over the caller's window. One more `inflateBack` call, for every caller protocol whose total
input is below `2^48` bytes (the runtime bounds every loop by `2^64` iterations; `docs/en/deviations.md`),
returns without a fault with one of its three results, keeps the state valid over the same window,
changes only the stream record, the state record, the callback's own blocks and the window slice,
and leaves the live blocks outside the callback's own unchanged (no leak). `inflateBackEnd` frees the
state. The histories are those of `BackSafeReachable`: the window is a slice of a heap byte block,
every byte object has fewer than `2^63` bytes on the heap of each call and after each call-back
step (`BackPlatform`), and every input chunk lies in a heap byte block (`BackFirstChunk`,
`BackPlatform`); `docs/en/deviations.md` lists these premises. The decoding clauses of
`Goal.inflateBack` (what reaches `out`, `Decodes`) are not planned (`docs/en/progress.md`, "Not planned"). -/
def Goal.inflate_back_sequence_safety : Prop :=
  (∀ h input inDesc output outDesc,
    C.run (Zlib.Infback.inflateBack none input inDesc output outDesc) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h r i window n, BackSafeReachable h r i window n →
    ∃ z s, BackValid h r i z s ∧ s.window = window ∧ s.wsize.toNat = n) ∧
  (∀ h r i window n z s input inDesc output outDesc
      (protocol : CallbackProtocol r i window n input inDesc output outDesc) first,
    BackSafeReachable h r i window n → BackValid h r i z s →
    (if z.next_in = .null then first = [] else Bytes h z.next_in z.avail_in.toNat first) →
    Separate z.next_in first.length window n →
    protocol.invariant h { supplied := first, chunks := [], active := z.next_in, held := first } →
    protocol.inputBound < 2 ^ 48 →
    ZlibF.PlatformMemory.ByteObjectsFit h → BackPlatform protocol → BackFirstChunk z first →
    ∃ rc after z' s' log,
      C.run (Zlib.Infback.inflateBack (some r) input inDesc output outDesc) h = .ok (rc, after) ∧
      BackValid after r i z' s' ∧ s'.window = window ∧ s'.wsize = s.wsize ∧
      protocol.invariant after log ∧
      (rc = Z_STREAM_END ∨ rc = Z_DATA_ERROR ∨ rc = Z_BUF_ERROR) ∧
      CallbackFrame protocol.own h after r i window n ∧
      (∀ b, ¬ protocol.own b → (after.live b ↔ h.live b))) ∧
  (∀ h r i window n, BackSafeReachable h r i window n →
    ∃ after z, C.run (Zlib.Infback.inflateBackEnd (some r)) h = .ok (Z_OK, after) ∧
      r.get after = some z ∧ z.state = none ∧
      Frame h after (fun b => StreamRoot r b ∨ b = i) ∧
      LiveChange h after (fun _ => False) (fun b => b = i))
完整上下文 ↗

gz_sequence_safety

/-- **Goal: safety of every gz file history.** Every history keeps the world well formed and the
handle in `GzInv`; `GzHistory` has no budget premise. For every next public call and every world (every
oracle): the run's result is not a fault, it is `.ok` or the out-of-fuel outcome, never `Fault.ub` or a memory
error (no premise); with `ReadsFinite` (a read budget below `2^61` bytes, only for the reading calls of `NeedsReadBound`) the result is `.ok`. `NeedsReadBound` goes by call name:
`gzread`, `gzfread`, `gzgetc`, `gzgetc_`, `gzgets` and `gzungetc`. For these the termination claim needs `ReadsFinite`, also
where the C returns at once (a call on a writer, a request of length 0); every other call terminates in every world. The
first half is partial correctness up to `2^64` iterations of each loop, which no real execution reaches. A call
that returns keeps the open descriptors, keeps
`GzInv`, writes only the handle's blocks and the declared caller regions, and changes the live blocks exactly
by the handle's ledger. The `gzgetc()` macro has the post of the function, which writes no caller region, and the
termination split of a reading call: with buffered output (`x.have ≠ 0`, the inline path) it returns with no premise;
with `x.have = 0` it calls the function `gzgetc`, and returns under `ReadsFinite`. The pointer `gzerror` returns is a readable NUL-terminated string in the heap after the
call: a literal or the handle's message. Every close returns and either refuses on the wrong mode or frees every owned block and
releases the descriptor. Every open returns; a failed open leaves no block and no open descriptor behind. -/
def Goal.gz_sequence_safety : Prop :=
  (∀ h fs i, GzHistory h fs i → FileSystem fs ∧ ∃ s, GzInv h i s) ∧
  (∀ h fs i s call, GzHistory h fs i → h.gzstates i = some s → GzOperation i call → GzArguments h i s call →
    (∀ e, call.execute fs h = .error e → e = .outOfFuel) ∧
    ((NeedsReadBound call → ReadsFinite fs s.fd) →
      ∃ value fs' after, call.execute fs h = .ok ((value, fs'), after)) ∧
    (∀ value fs' after, call.execute fs h = .ok ((value, fs'), after) →
      FdsKept fs fs' ∧ GzStepPost h i s call fs' after)) ∧
  (∀ h fs i s, GzHistory h fs i → h.gzstates i = some s →
    (∀ e, Zlib.ZlibH.gzgetc (some (.in_gzstate_x i)) fs h = .error e → e = .outOfFuel) ∧
    ((s.x.have = 0 → NeedsReadBound (.gzgetc (some (.in_gzstate_x i))) → ReadsFinite fs s.fd) →
      ∃ value fs' after, Zlib.ZlibH.gzgetc (some (.in_gzstate_x i)) fs h = .ok ((value, fs'), after)) ∧
    (∀ value fs' after, Zlib.ZlibH.gzgetc (some (.in_gzstate_x i)) fs h = .ok ((value, fs'), after) →
      FdsKept fs fs' ∧ GzStepPost h i s (.gzgetc (some (.in_gzstate_x i))) fs' after)) ∧
  (∀ h fs i s errnum, GzHistory h fs i → h.gzstates i = some s →
    GzArguments h i s (.gzerror (some (.in_gzstate_x i)) errnum) →
    ∀ (value : BPtr) fs' after,
      (Call.gzerror (some (.in_gzstate_x i)) errnum).execute fs h = .ok ((value, fs'), after) →
      ∃ t, CString after value t) ∧
  (∀ h fs i s call, GzHistory h fs i → h.gzstates i = some s → GzCloseCall i call →
    ∃ value fs' after, call.execute fs h = .ok ((value, fs'), after) ∧
      ((CloseRefuses s call ∧ after = h ∧ fs' = fs) ∨ (¬ CloseRefuses s call ∧ GzReleased h after fs fs' i s))) ∧
  GzOpenSafe Zlib.Gzlib.gzopen ∧ GzOpenSafe Zlib.Gzlib.gzopen64 ∧ GzDopenSafe
完整上下文 ↗

拒绝

inflate_refusal

/-- **Inflate stream refusals.** `inflate` makes and frees its local four-byte array, so its
refusal is stated with a frame and an unchanged ledger; the other functions leave the heap
exactly as it was. `inflateCopy` from a refused source clears the destination state. -/
def Goal.inflate_refusal : Prop :=
  (∀ h p flush, Fresh h → RefusedInflate h p →
    ∃ after, C.run (Zlib.Inflate.inflate p flush) h = .ok (Z_STREAM_ERROR, after) ∧
      Frame h after (fun _ => False) ∧ LiveChange h after (fun _ => False) (fun _ => False)) ∧
  (∀ h p, RefusedInflate h p → C.run (Zlib.Inflate.inflateEnd p) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h p, RefusedInflate h p → C.run (Zlib.Inflate.inflateReset p) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h p windowBits, RefusedInflate h p →
    C.run (Zlib.Inflate.inflateReset2 p windowBits) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h p dictionary dictLength, RefusedInflate h p →
    C.run (Zlib.Inflate.inflateGetDictionary p dictionary dictLength) h =
      .ok ((Z_STREAM_ERROR, dictLength), h)) ∧
  (∀ h p dictionary dictLength, RefusedInflate h p →
    C.run (Zlib.Inflate.inflateSetDictionary p dictionary dictLength) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h dest oldDest source, dest.get h = some oldDest → RefusedInflate h source →
    C.run (Zlib.Inflate.inflateCopy (some dest) source) h =
      .ok (Z_STREAM_ERROR, dest.put h { oldDest with state := none }))
完整上下文 ↗

deflate_refusal

/-- **Deflate stream refusals.** Each function refuses a refused stream and leaves the heap
exactly as it was. `deflateCopy` from a refused source clears the destination state; this
includes a source whose live state the check refuses (a wrong back pointer or status). -/
def Goal.deflate_refusal : Prop :=
  (∀ h p flush, RefusedDeflate h p → C.run (Zlib.Deflate.deflate p flush) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h p dictionary dictLength, RefusedDeflate h p →
    C.run (Zlib.Deflate.deflateSetDictionary p dictionary dictLength) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h p level strategy, RefusedDeflate h p →
    C.run (Zlib.Deflate.deflateParams p level strategy) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h p dictionary hasDictLength, RefusedDeflate h p →
    C.run (Zlib.Deflate.deflateGetDictionary p dictionary hasDictLength) h = .ok ((Z_STREAM_ERROR, none), h)) ∧
  (∀ h dest oldDest source, dest.get h = some oldDest → RefusedDeflate h source →
    C.run (Zlib.Deflate.deflateCopy (some dest) source) h =
      .ok (Z_STREAM_ERROR, dest.put h { oldDest with state := none }))
完整上下文 ↗

gz_refusal

/-- **Refusal of a `NULL` handle** by every gz function of the public interface: the documented
value, the heap and the file-system world unchanged, for every heap, world and other argument.
No precondition. `gzprintf` and `gzvprintf` quantify over the argument list.

`gzgetc` is the function `(gzgetc)(file)`. The `gzgetc` macro of `zlib.h` reads `(g)->have` first,
so the macro on `NULL` is undefined behaviour in C; the translation `Zlib.Gzread.gzgetc` is the
function, and that is what is stated here. -/
def Goal.gz_refusal : Prop :=
  (∀ (fs : Fs) (h : Heap) buf len, Zlib.Gzread.gzread none buf len fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) buf size nitems,
    Zlib.Gzread.gzfread buf size nitems none fs h = .ok ((0, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) buf len, Zlib.Gzwrite.gzwrite none buf len fs h = .ok ((0, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) buf size nitems,
    Zlib.Gzwrite.gzfwrite buf size nitems none fs h = .ok ((0, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) c, Zlib.Gzwrite.gzputc none c fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) str, Zlib.Gzwrite.gzputs none str fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) format (va : List VaArg),
    Zlib.Gzwrite.gzprintf none format va fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) format (va : List VaArg),
    Zlib.Gzwrite.gzvprintf none format va fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) flush,
    Zlib.Gzwrite.gzflush none flush fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) level strategy,
    Zlib.Gzwrite.gzsetparams none level strategy fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzgetc none fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzgetc_ none fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) c, Zlib.Gzread.gzungetc c none fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) buf len, Zlib.Gzread.gzgets none buf len fs h = .ok ((.null, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzdirect none fs h = .ok ((0, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) offset whence,
    Zlib.Gzlib.gzseek none offset whence fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap) offset whence,
    Zlib.Gzlib.gzseek64 none offset whence fs h = .ok ((-1, fs), h)) ∧
  (∀ h : Heap, Zlib.Gzlib.gztell none h = .ok (-1, h)) ∧
  (∀ h : Heap, Zlib.Gzlib.gztell64 none h = .ok (-1, h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzlib.gzoffset none fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzlib.gzoffset64 none fs h = .ok ((-1, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzlib.gzrewind none fs h = .ok ((-1, fs), h)) ∧
  (∀ h : Heap, Zlib.Gzlib.gzeof none h = .ok (0, h)) ∧
  (∀ (h : Heap) errnum, Zlib.Gzlib.gzerror none errnum h = .ok (.null, h)) ∧
  (∀ h : Heap, Zlib.Gzlib.gzclearerr none h = .ok ((), h)) ∧
  (∀ (h : Heap) size, Zlib.Gzlib.gzbuffer none size h = .ok (-1, h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzclose.gzclose none fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzclose_r none fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
  (∀ (fs : Fs) (h : Heap), Zlib.Gzwrite.gzclose_w none fs h = .ok ((Z_STREAM_ERROR, fs), h))
完整上下文 ↗

前提可以满足

inflate_initialisation_domain

/-- Every accepted signed window parameter has a non-failing init on every permitted heap.
The fixed witness additionally rules out an empty caller domain. -/
def Goal.inflate_initialisation_domain : Prop :=
  (∀ h r version wb wrap bits,
    InitDomain h r version → Api.inflWbits wb.toInt = some (wrap, bits) →
    h.allocOk h.nalloc = true →
    ∃ after, C.run (Zlib.Inflate.inflateInit2_ (some r) wb version 112) h = .ok (Z_OK, after) ∧
      InflateInitial h after r wrap bits ∧ StreamReachable .inflate after r) ∧
  InitDomain witnessHeap (.tab 0) (.ref (.blk 1) 0) ∧
  (∀ wb wrap bits, Api.inflWbits wb.toInt = some (wrap, bits) →
    ∃ after, C.run (Zlib.Inflate.inflateInit2_ (some (.tab 0)) wb (.ref (.blk 1) 0) 112)
      witnessHeap = .ok (Z_OK, after) ∧ InflateInitial witnessHeap after (.tab 0) wrap bits)
完整上下文 ↗

deflate_initialisation_domain

/-- Full level, method, window, memory-level and strategy coverage, including normalisation.
No assumption that the post-init invariant already holds is permitted. -/
def Goal.deflate_initialisation_domain : Prop :=
  (∀ h r version level method wb mem strategy p,
    InitDomain h r version →
    Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
    (∀ j, j < 5 → h.allocOk (h.nalloc + j) = true) →
    ∃ after, C.run (Zlib.Deflate.deflateInit2_ (some r) level method wb mem strategy version 112) h =
      .ok (Z_OK, after) ∧ DeflateInitial h after r p ∧ StreamReachable .deflate after r) ∧
  InitDomain witnessHeap (.tab 0) (.ref (.blk 1) 0) ∧
  (∀ level method wb mem strategy p,
    Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
    ∃ after, C.run (Zlib.Deflate.deflateInit2_ (some (.tab 0)) level method wb mem strategy
      (.ref (.blk 1) 0) 112) witnessHeap = .ok (Z_OK, after) ∧
      DeflateInitial witnessHeap after (.tab 0) p)
完整上下文 ↗

inflate_back_initialisation_domain

/-- All eight documented callback-window sizes, with an arbitrary valid caller window.
Init establishes the back-decoder invariant and retains ownership of the window. -/
def Goal.inflate_back_initialisation_domain : Prop :=
  (∀ h r version wb window,
    InitDomain h r version → 8 ≤ wb.toInt → wb.toInt ≤ 15 →
    window ≠ .null → Writable h window (2 ^ wb.toInt.toNat) → h.allocOk h.nalloc = true →
    ∃ after z s, C.run (Zlib.Infback.inflateBackInit_ (some r) wb window version 112) h =
      .ok (Z_OK, after) ∧ BackValid after r h.nextBlk z s ∧ s.window = window ∧
      s.wbits = wb.toUInt32 ∧ Frame h after (StreamRoot r) ∧
      LiveChange h after (fun b => b = h.nextBlk) (fun _ => False)) ∧
  InitDomain witnessHeap (.tab 0) (.ref (.blk 1) 0) ∧
  (∀ wb : Int32, 8 ≤ wb.toInt → wb.toInt ≤ 15 →
    ∃ after z s, C.run (Zlib.Infback.inflateBackInit_ (some (.tab 0)) wb (.ref (.blk 2) 0)
      (.ref (.blk 1) 0) 112) witnessHeap = .ok (Z_OK, after) ∧
      BackValid after (.tab 0) witnessHeap.nextBlk z s ∧ s.window = .ref (.blk 2) 0)
完整上下文 ↗

inflateBack_call_domain

/-- The premises of the call clause of `Goal.inflateBack_safety` hold together on a concrete
history, with a concrete pair of callbacks, a concrete `CallbackProtocol` and a non-empty first
chunk of input in a heap byte block. So that clause is not vacuous: its conclusion holds for this
call of `inflateBack`. A protocol is a structure of obligations, and a set of obligations that no
callback meets would make every statement over "every protocol" true. -/
def Goal.inflateBack_call_domain : Prop :=
  ∃ (h : Heap) (r : ZStreamRef) (i : Nat) (window : BPtr) (n : Nat) (z : ZStream) (s : InflateState)
    (input : Zlib.Infback.InCb) (inDesc : BPtr) (output : Zlib.Infback.OutCb) (outDesc : BPtr)
    (protocol : CallbackProtocol r i window n input inDesc output outDesc) (first : List UInt8),
    first ≠ [] ∧ z.next_in ≠ .null ∧
    BackSafeReachable h r i window n ∧ BackValid h r i z s ∧
    Bytes h z.next_in z.avail_in.toNat first ∧
    Separate z.next_in first.length window n ∧
    protocol.invariant h { supplied := first, chunks := [], active := z.next_in, held := first } ∧
    protocol.inputBound < 2 ^ 48 ∧
    ZlibF.PlatformMemory.ByteObjectsFit h ∧ BackPlatform protocol ∧ BackFirstChunk z first
完整上下文 ↗

gz_sequence_nonvacuity

/-- **Goal: the premises of `gz_sequence_safety` are satisfiable** (non-vacuity). Two concrete histories, one per
entry point and mode, each from a caller heap and a world that satisfy every premise of the opening constructor of
`GzHistory`, with no allocation failure:

1. `gzopen` gives a reading handle in `GzInv` whose descriptor has a finite read budget (`ReadsFinite`, the premise
   of the termination half), and a one-byte `gzread` into a caller buffer satisfies `GzArguments`;
2. `gzdopen` on an open descriptor gives a writing handle in `GzInv` that keeps the descriptor, and a one-byte
   `gzwrite` from a caller buffer satisfies `GzArguments`.

So the call clause of `gz_sequence_safety`, and its termination half for a reading call, apply to a real call with a
nonzero length. -/
def Goal.gz_sequence_nonvacuity : Prop :=
  (∃ (h : Heap) (fs : Fs) (path mode : BPtr) (name flags : List UInt8) (after : Heap) (fs' : Fs) (i : Nat)
      (s : GzState) (buf : BPtr),
    Fresh h ∧ Zlib.Gzlib.Spec.Uniq h ∧ LibraryGlobals h ∧ ZlibF.PlatformMemory.ByteObjectsFit h ∧
    NoAllocationFailure h ∧ FileSystem fs ∧ CString h path name ∧ CString h mode flags ∧
    Zlib.Gzlib.gzopen path mode fs h = .ok ((some (.in_gzstate_x i), fs'), after) ∧
    GzHistory after fs' i ∧ after.gzstates i = some s ∧ s.mode = GZ_READ ∧ GzInv after i s ∧
    ReadsFinite fs' s.fd ∧
    GzOperation i (.gzread (some (.in_gzstate_x i)) buf 1) ∧
    NeedsReadBound (.gzread (some (.in_gzstate_x i)) buf 1) ∧
    GzArguments after i s (.gzread (some (.in_gzstate_x i)) buf 1)) ∧
  (∃ (h : Heap) (fs : Fs) (fd : Int32) (mode : BPtr) (flags : List UInt8) (after : Heap) (fs' : Fs) (i : Nat)
      (s : GzState) (buf : BPtr),
    Fresh h ∧ Zlib.Gzlib.Spec.Uniq h ∧ LibraryGlobals h ∧ ZlibF.PlatformMemory.ByteObjectsFit h ∧
    NoAllocationFailure h ∧ FileSystem fs ∧ 0 ≤ fd.toInt ∧ GzOracle.FdOpen fs fd.toInt.toNat ∧
    CString h mode flags ∧
    Zlib.Gzlib.gzdopen fd mode fs h = .ok ((some (.in_gzstate_x i), fs'), after) ∧
    GzHistory after fs' i ∧ after.gzstates i = some s ∧ s.mode = GZ_WRITE ∧ s.fd = fd ∧ GzInv after i s ∧
    GzOperation i (.gzwrite (some (.in_gzstate_x i)) buf 1) ∧
    GzArguments after i s (.gzwrite (some (.in_gzstate_x i)) buf 1))
完整上下文 ↗

默认 zlib 流的往返

compress_uncompress_roundtrip

/-- **`uncompress(compress(x)) = x`.** When every allocation succeeds, `compress` with
`compressBound` room returns `Z_OK` and stores the length `m` it wrote; the `m` bytes it wrote,
given to `uncompress` on any heap where every allocation succeeds, with room for the source, give
back the source and its length, with `Z_OK`. -/
def Goal.compress_uncompress_roundtrip : Prop :=
  ∀ h dest c source n xs,
    Fresh h → Zlib.Deflate.Spec.Uniq h → LibraryGlobals h → ZlibF.PlatformMemory.ByteObjectsFit h →
    NoAllocationFailure h →
    Bytes h source n.toNat xs → Writable h dest c.toNat → Separate source n.toNat dest c.toNat →
    ¬ compressRejected dest (some c) source n →
    Api.compressBound n.toNat ≤ c.toNat →
    ∃ stored after out, C.run (Zlib.Compress.compress dest (some c) source n) h = .ok ((Z_OK, stored), after) ∧
      out.length = stored.toNat ∧ Bytes after dest stored.toNat out ∧
      ∀ h₂ dest₂ destLen₂ source₂ capacity₂,
        Fresh h₂ → Zlib.Inflate.Spec.Uniq h₂ → LibraryGlobals h₂ →
        ZlibF.PlatformMemory.ByteObjectsFit h₂ → NoAllocationFailure h₂ →
        LengthCell h₂ destLen₂ capacity₂ → destLen₂ ≠ .null → source₂ ≠ .null → dest₂ ≠ .null →
        Bytes h₂ source₂ stored.toNat out → Writable h₂ dest₂ capacity₂.toNat →
        Separate source₂ stored.toNat dest₂ capacity₂.toNat →
        Separate destLen₂ 8 dest₂ capacity₂.toNat → Separate destLen₂ 8 source₂ stored.toNat →
        n.toNat ≤ capacity₂.toNat →
        ∃ after₂, C.run (Zlib.Uncompr.uncompress dest₂ destLen₂ source₂ stored) h₂ = .ok (Z_OK, after₂) ∧
          Bytes after₂ dest₂ n.toNat xs ∧ LengthCell after₂ destLen₂ n
完整上下文 ↗

compress_uncompress_roundtrip_witness

/-- **Non-vacuity of `Goal.compress_uncompress_roundtrip`.** There is a heap, a destination and a
non-empty source on which every premise of the `compress` half holds; and for every output `out`
that `compress` can produce there (`stored` bytes, at most `compressBound n`), a second heap,
destination, length cell and source holding `out` on which every premise of the `uncompress` half
holds. -/
def Goal.compress_uncompress_roundtrip_witness : Prop :=
  ∃ h dest c source n xs,
    Fresh h ∧ Zlib.Deflate.Spec.Uniq h ∧ LibraryGlobals h ∧ ZlibF.PlatformMemory.ByteObjectsFit h ∧
    NoAllocationFailure h ∧
    xs ≠ [] ∧
    Bytes h source n.toNat xs ∧ Writable h dest c.toNat ∧ Separate source n.toNat dest c.toNat ∧
    ¬ compressRejected dest (some c) source n ∧ Api.compressBound n.toNat ≤ c.toNat ∧
    ∀ (stored : UInt64) (out : List UInt8), stored.toNat ≤ Api.compressBound n.toNat →
      out.length = stored.toNat →
      ∃ h₂ dest₂ destLen₂ source₂ capacity₂,
        Fresh h₂ ∧ Zlib.Inflate.Spec.Uniq h₂ ∧ LibraryGlobals h₂ ∧
        ZlibF.PlatformMemory.ByteObjectsFit h₂ ∧ NoAllocationFailure h₂ ∧
        LengthCell h₂ destLen₂ capacity₂ ∧ destLen₂ ≠ .null ∧ source₂ ≠ .null ∧ dest₂ ≠ .null ∧
        Bytes h₂ source₂ stored.toNat out ∧ Writable h₂ dest₂ capacity₂.toNat ∧
        Separate source₂ stored.toNat dest₂ capacity₂.toNat ∧
        Separate destLen₂ 8 dest₂ capacity₂.toNat ∧ Separate destLen₂ 8 source₂ stored.toNat ∧
        n.toNat ≤ capacity₂.toNat
完整上下文 ↗

compress_completes

/-- `compress` (the default level) completes with `compressBound` room. -/
def Goal.compress_completes : Prop :=
  CompressCompletes (fun d c s n => do
    let (rc, size) ← Zlib.Compress.compress d c s n
    pure (rc, some size))
完整上下文 ↗

compress_z_completes

/-- `compress_z` (the default level) completes with `compressBound` room. -/
def Goal.compress_z_completes : Prop :=
  CompressCompletes Zlib.Compress.compress_z
完整上下文 ↗

uncompress_completes

/-- **`uncompress` completes on a complete stream.** The `n` source bytes are a zlib stream that
does not ask for a preset dictionary and decodes to `xs`, and the destination holds at least
`xs.length` bytes:
when every allocation succeeds, `uncompress` returns `Z_OK`, writes `xs` and stores its length. -/
def Goal.uncompress_completes : Prop :=
  ∀ h dest destLen source capacity n stream xs,
    Fresh h → Zlib.Inflate.Spec.Uniq h → LibraryGlobals h → ZlibF.PlatformMemory.ByteObjectsFit h →
    NoAllocationFailure h →
    LengthCell h destLen capacity → destLen ≠ .null → source ≠ .null → dest ≠ .null →
    Bytes h source n.toNat stream → Writable h dest capacity.toNat →
    Separate source n.toNat dest capacity.toNat →
    Separate destLen 8 dest capacity.toNat → Separate destLen 8 source n.toNat →
    Zlib.Decodes [] stream xs → ¬ AsksDictionary stream → xs.length ≤ capacity.toNat →
    ∃ after, C.run (Zlib.Uncompr.uncompress dest destLen source n) h = .ok (Z_OK, after) ∧
      Bytes after dest xs.length xs ∧ LengthCell after destLen (UInt64.ofNat xs.length)
完整上下文 ↗

stream_roundtrip_total

/-- **The stream round trip, unconditional form.** The default encoder ends under every finishing
schedule, with an output that decodes to its input (`Goal.deflate_finish_ends`); and the default
decoder, given that output under every chunking, ends with exactly the encoder's input
(`Goal.inflate_chain_ends`). -/
def Goal.stream_roundtrip_total : Prop :=
  Goal.deflate_finish_ends ∧ Goal.inflate_chain_ends
完整上下文 ↗

deflate_finish_ends

/-- **The default encoder ends under every finishing schedule.** After any default history (any
flush values, any chunking) that has not ended, with the remaining input `input` at the input
pointer: there is a number `N` such that every continuation by `Z_FINISH` calls with positive
room that offers the rest of `input` has, while unfinished, made at most `N` calls; and once it
ends it has accepted all of `input` and its whole output decodes to its whole input. No bound on
the room is needed. -/
def Goal.deflate_finish_ends : Prop :=
  ∀ r h log z input,
    DefaultDeflateHistory r h log → log.finished = false →
    r.get h = some z → StreamBuffers h r → Bytes h z.next_in z.avail_in.toNat input →
    (∀ ds d, z.state = some (.deflate ds) → h.dstates ds = some d →
      d.status = FINISH_STATE → input = []) →
    ∃ N, ∀ k after final, DefaultFinishChain r log.input input k h log after final →
      (final.finished = false → k ≤ N) ∧
      (final.finished = true → final.input = log.input ++ input ∧
        Zlib.Decodes [] final.output final.input)
完整上下文 ↗

inflate_chain_ends

/-- **The default decoder ends under every chunking.** `encoded` is a complete default stream. From
a default decoder that has read a prefix of it and has not ended, there is a number `N` such that
every continuation of `inflate` calls on the rest of the stream (`DefaultInflateChain`) has, while
unfinished, made at most `N` calls; and once it ends it has consumed the whole stream and written
exactly the encoder's input. -/
def Goal.inflate_chain_ends : Prop :=
  ∀ rd hd encoded ri hi decoded,
    DefaultDeflateHistory rd hd encoded → encoded.result = Z_STREAM_END →
    DefaultInflateTrace ri hi decoded → decoded.finished = false →
    decoded.input <+: encoded.output →
    ∃ N, ∀ k after final,
      DefaultInflateChain ri encoded.output encoded.input k hi decoded after final →
      (final.finished = false → k ≤ N) ∧
      (final.finished = true → final.input = encoded.output ∧ final.output = encoded.input)
完整上下文 ↗

stream_roundtrip

/-- **The stream round trip, conditional form.** A default zlib stream written by `deflate`
under any flush values and any chunking, and read by `inflate` under any chunking: when both
histories reach `Z_STREAM_END` and the decoder read a prefix of the encoder's output, the
decoder's output is the encoder's input. The two histories run on separate heaps. -/
def Goal.stream_roundtrip : Prop :=
  ∀ (rd ri : ZStreamRef) (hd hi : Heap) (encoded decoded : DataLog),
    DefaultDeflateHistory rd hd encoded → DefaultInflateHistory ri hi decoded →
    encoded.result = Z_STREAM_END → decoded.result = Z_STREAM_END →
    (∃ trailing, encoded.output = decoded.input ++ trailing) →
    decoded.output = encoded.input
完整上下文 ↗

deflate_completes_default

/-- **Completion of the default stream from the bound.** After a clean default history that has
not ended, a `deflate(Z_FINISH)` call offered all the remaining input `input`, with output room
more than what the bound of the whole input leaves after the output so far, returns
`Z_STREAM_END`: it accepts all of `input`, and the whole output decodes to the whole input. The
stream can be exactly as long as the bound, and a call that first delivers pending output and is
left with no room returns `Z_OK` (`deflate.c`), so room equal to the rest is not enough after an
earlier call; one call from a fresh stream needs only the bound (`Goal.deflate_bound_default`). The room is measured against `unsaturatedBound` of the whole input, which is
`compressBound` of the whole input below the saturation point. `zlib.h` promises nothing once
`compressBound` saturates at `2^64 - 1`, and a history may accept more input than that. At these
parameters `deflateBound` is `compressBound` (`Goal.deflate_bound_default`). Before
`Z_STREAM_END`, a `Z_FINISH` already given keeps the caller from offering new input. -/
def Goal.deflate_completes_default : Prop :=
  ∀ r h log z input,
    DefaultCleanHistory r h log → log.finished = false →
    r.get h = some z → StreamBuffers h r → z.next_out ≠ .null →
    Bytes h z.next_in z.avail_in.toNat input →
    (∀ ds d, z.state = some (.deflate ds) → h.dstates ds = some d →
      d.status = FINISH_STATE → input = []) →
    0 < z.avail_out.toNat →
    unsaturatedBound (log.input.length + input.length) < log.output.length + z.avail_out.toNat →
    ∃ after output, DataStep .deflate h after r Z_FINISH Z_STREAM_END input output input.length ∧
      Zlib.Decodes [] (log.output ++ output) (log.input ++ input)
完整上下文 ↗

deflate_bound_default

/-- **The promise of `deflateBound`, default stream** (`zlib.h`): after `deflateInit` and caller
edits only, `deflateBound(strm, n)` returns `b`; then one `deflate(Z_FINISH)` offered all `n`
input bytes with at least `b` bytes of room returns `Z_STREAM_END`, accepts all input, and writes
a stream that decodes to the input. -/
def Goal.deflate_bound_default : Prop :=
  ∀ r h log z input n b,
    DefaultCleanHistory r h log → log.input = [] → log.output = [] → log.finished = false →
    C.run (Zlib.Deflate.deflateBound (some r) n) h = .ok (b, h) →
    r.get h = some z → StreamBuffers h r → z.next_out ≠ .null →
    Bytes h z.next_in z.avail_in.toNat input → input.length = n.toNat →
    b.toNat ≤ z.avail_out.toNat →
    ∃ after output, DataStep .deflate h after r Z_FINISH Z_STREAM_END input output input.length ∧
      Zlib.Decodes [] output input
完整上下文 ↗

inflate_completes_default

/-- **Completion of `inflate` on a default stream.** `encoded` is a complete default stream: the
output of a default deflate history that ended. A default decoder (`DefaultInflateTrace`) that has
read a prefix of it and has not ended, offered exactly the rest of the stream with room for the
rest of the input, on a heap where every allocation succeeds, returns `Z_STREAM_END` and writes
exactly the rest of the input. -/
def Goal.inflate_completes_default : Prop :=
  ∀ rd hd encoded ri hi decoded z flush,
    DefaultDeflateHistory rd hd encoded → encoded.result = Z_STREAM_END →
    DefaultInflateTrace ri hi decoded → decoded.finished = false →
    decoded.input <+: encoded.output →
    ri.get hi = some z → StreamBuffers hi ri → z.next_out ≠ .null →
    ZlibF.PlatformMemory.ByteObjectsFit hi → NoAllocationFailure hi →
    Bytes hi z.next_in z.avail_in.toNat (encoded.output.drop decoded.input.length) →
    encoded.input.length ≤ decoded.output.length + z.avail_out.toNat → OrdinaryFlush flush →
    ∃ after, C.run (Zlib.Inflate.inflate (some ri) flush) hi = .ok (Z_STREAM_END, after) ∧
      Bytes after z.next_out (encoded.input.length - decoded.output.length)
        (encoded.input.drop decoded.output.length)
完整上下文 ↗

default_inflate_progress

/-- Progress of the default decoder on a valid stream, under any chunking. -/
def Goal.default_inflate_progress : Prop :=
  ∀ (r : ZStreamRef) (h : Heap) (log : DataLog) (S D input : List UInt8) (z : ZStream) (flush : Int32),
    DefaultInflateTrace r h log → log.finished = false →
    Zlib.Decodes [] S D → log.input <+: S →
    ZlibF.PlatformMemory.ByteObjectsFit h → NoAllocationFailure h → StreamBuffers h r →
    r.get h = some z → z.next_out ≠ .null → (z.avail_out ≠ 0 ∨ log.output = D) →
    Bytes h z.next_in z.avail_in.toNat input → log.input ++ input <+: S →
    (input ≠ [] ∨ log.input = S) → OrdinaryFlush flush →
    ∃ rc after output used, DataStep .inflate h after r flush rc input output used ∧
      ((rc = Z_STREAM_END ∧ log.input ++ input.take used = S ∧ log.output ++ output = D) ∨
       ((rc = Z_OK ∨ (rc = Z_BUF_ERROR ∧ flush = Z_FINISH)) ∧ (used ≠ 0 ∨ output ≠ []) ∧
         log.input ++ input.take used <+: S ∧ log.output ++ output <+: D) ∨
       (rc = Z_NEED_DICT ∧ AsksDictionary S ∧ log.output ++ output = []))
完整上下文 ↗

default_inflate_completes

/-- Completion of the default decoder in one call: the whole rest of a valid stream and room for
the rest of its decoding. -/
def Goal.default_inflate_completes : Prop :=
  ∀ (r : ZStreamRef) (h : Heap) (log : DataLog) (S D : List UInt8) (z : ZStream) (flush : Int32),
    DefaultInflateTrace r h log → log.finished = false →
    Zlib.Decodes [] S D → log.input <+: S →
    ZlibF.PlatformMemory.ByteObjectsFit h → NoAllocationFailure h → StreamBuffers h r →
    r.get h = some z → z.next_out ≠ .null →
    Bytes h z.next_in z.avail_in.toNat (S.drop log.input.length) →
    D.length ≤ log.output.length + z.avail_out.toNat → OrdinaryFlush flush →
    ∃ rc after output used, DataStep .inflate h after r flush rc (S.drop log.input.length) output used ∧
      ((rc = Z_STREAM_END ∧ used = S.length - log.input.length ∧ log.output ++ output = D) ∨
       (rc = Z_NEED_DICT ∧ AsksDictionary S ∧ log.output ++ output = []))
完整上下文 ↗

完整的序列契约(安全之外)

inflate_sequence

状态:未完成,不在计划内

/-- All legal public histories are safe and retain cleanup. For ordinary data epochs every
input/output split is covered, including allocation failures and dictionary handshakes.
The functional clauses use protocol-admitted histories, with one successful wrapped
dictionary installation per NEED_DICT request. Successful acceptance uses the configured
dictionary window; valid-input prefix and completion use the unchanged RFC byte format. -/
def Goal.inflate_sequence : Prop :=
  StreamSequenceSafety .inflate ∧
  (∀ wb wrap bits r h log, Api.inflWbits wb.toInt = some (wrap, bits) →
    AllowedInflateProtocol wb r h log →
    (log.singleDictionary = true → log.result = Z_STREAM_END →
      Api.Layer.InflateAccepted wrap bits log.dictionary log.input log.output) ∧
    (∀ source decoded, Api.Layer.Decodes wrap bits log.dictionary source decoded →
      log.singleDictionary = true → Api.FullWindow wrap bits source → log.input <+: source →
      log.output <+: decoded ∧ log.result ≠ Z_DATA_ERROR ∧
      (log.result = Z_STREAM_END → log.input = source ∧ log.output = decoded))) ∧
  InflateCompletes
完整上下文 ↗

deflate_sequence

状态:未完成,不在计划内

/-- All legal public histories are safe and retain cleanup. A finished ordinary data epoch
encodes exactly its accepted input, for every accepted parameter set and flush schedule.
A completed `Z_SYNC_FLUSH` or `Z_FULL_FLUSH` (`Z_OK` with output space left, `zlib.h`) has
consumed all offered input, and the output so far ends at a flush point that produces exactly
the input so far. After a completed `Z_FULL_FLUSH`, the rest of a finished stream decodes
without the earlier data. A successful call leaves the Adler-32 (zlib) or CRC-32 (gzip) of
the accepted input in `adler`. Before any output, `deflateBound` returns the bound that
`DeflateCompletes` uses. -/
def Goal.deflate_sequence : Prop :=
  StreamSequenceSafety .deflate ∧
  (∀ level method wb mem strategy p r h log,
    Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
    DeflateDataTrace level method wb mem strategy r h log →
    log.result = Z_STREAM_END → DecodesFor p log.dictionary log.output log.input) ∧
  (∀ level method wb mem strategy p r h log after flush rc input output used z',
    Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
    DeflateDataTrace level method wb mem strategy r h log →
    DataStep .deflate h after r flush rc input output used →
    (flush = Z_SYNC_FLUSH ∨ flush = Z_FULL_FLUSH) → rc = Z_OK →
    r.get after = some z' → z'.avail_out ≠ 0 →
    let log₁ := deflateLogStep log flush rc input output used
    z'.avail_in = 0 ∧ FlushedFor p log₁.dictionary log₁.output log₁.input ∧
    (flush = Z_FULL_FLUSH → ∀ h₂ log₂, DeflateDataRun r after log₁ h₂ log₂ →
      log₂.result = Z_STREAM_END →
      ∃ tail, Deflate.Prefix [] (log₂.output.drop log₁.output.length) tail
        (log₂.input.drop log₁.input.length))) ∧
  (∀ level method wb mem strategy p r h log after flush rc input output used z',
    Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
    DeflateDataTrace level method wb mem strategy r h log →
    DataStep .deflate h after r flush rc input output used →
    (rc = Z_OK ∨ rc = Z_STREAM_END) → r.get after = some z' →
    let accepted := log.input ++ input.take used
    (p.wrap = .zlib → z'.adler.toNat = (ZlibF.Spec.adler32 accepted).toNat) ∧
    (p.wrap = .gzip → z'.adler.toNat = (ZlibF.Spec.crc32 accepted).toNat)) ∧
  (∀ level method wb mem strategy p r h log n,
    Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
    DeflateDataTrace level method wb mem strategy r h log → log.output = [] →
    let bound := UInt64.ofNat (min (({ Api.DeflState.fresh p with dict := some log.dictionary }).bound
      n.toNat) (2 ^ 64 - 1))
    C.run (Zlib.Deflate.deflateBound_z (some r) n) h = .ok (bound, h) ∧
    C.run (Zlib.Deflate.deflateBound (some r) n) h = .ok (bound, h)) ∧
  DeflateCompletes
完整上下文 ↗

inflate_back_sequence

状态:未完成,不在计划内

/-- Includes actual callback execution and raw-format delivery, re-use of the window, and
complete end cleanup. Callback memory and returning/finite-input obligations remain explicit. -/
def Goal.inflate_back_sequence : Prop :=
  Goal.inflateBack ∧
  (∀ h r i window n, BackReachable h r i window n →
    (∃ z s, BackValid h r i z s ∧ s.window = window ∧ s.wsize.toNat = n) ∧
    ∃ after z, C.run (Zlib.Infback.inflateBackEnd (some r)) h = .ok (Z_OK, after) ∧
      r.get after = some z ∧ z.state = none ∧
      Frame h after (fun b => StreamRoot r b ∨ b = i) ∧
      LiveChange h after (fun _ => False) (fun b => b = i))
完整上下文 ↗

gz_sequence

状态:未完成,不在计划内

/-- The gz lifecycle includes every admitted operation, external file growth and final close.
The per-entry read contracts express transparent/concatenated-member decoding and the
per-entry write contracts account for accepted bytes and seek zeros. -/
def Goal.gz_sequence : Prop :=
  (∀ h fs i, GzReachable h fs i → FileSystem fs ∧ ∃ s, GzValid h i s) ∧
  (∀ h fs i s call, GzReachable h fs i → h.gzstates i = some s →
    GzOperation i call → GzArguments h i s call → RegularOs fs →
    ∃ value fs' after s', call.execute fs h = .ok ((value, fs'), after) ∧
      GzValid after i s' ∧ FileSystem fs' ∧
      LiveChange h after
        (fun b => GzOwned after i s' b ∧ ¬ h.live b)
        (fun b => GzOwned h i s b ∧ ¬ GzOwned after i s' b)) ∧
  (∀ h fs i s, GzReachable h fs i → h.gzstates i = some s →
    ∃ rc fs' after, Zlib.Gzclose.gzclose (some (.in_gzstate_x i)) fs h = .ok ((rc, fs'), after) ∧
      CloseEffects h after fs fs' i s) ∧
  Goal.gzread ∧ Goal.gzfread ∧ Goal.gzgetc ∧ Goal.gzgets ∧
  Goal.gzwrite ∧ Goal.gzfwrite ∧ Goal.gzflush ∧ Goal.gzclose ∧ GzWriterFormat
完整上下文 ↗
ZLIB × LEAN

目录

正在阅读目标的命题