rocq/theories/LentLogic.v
Strings the world lends, in the program logic of Logic.v (docs/logic.md). setlocale(k, NULL) returns libc's own name for the locale category k: memory the program does not own and may read only while the world keeps it. A weakest precondition cannot remember across steps which string a query returned, since the memory and the world are the state, not the assertion. A ghost piece does (PName of Pieces.v): lent k p t says the world lends the string t at p under the key k, and the world interpretation wi ties every such piece to the world.
What a proof needs of wi is one fact, lent_at: a lent string is a C string (c_string), in an object at a multiple of 8, and apart from every object owning a piece of memory in the ghost heap. Its triples are generic in wi under that hypothesis:
wp_lent_query: a call that returns the lent pointer and changes nothing, such as setlocale's query;wp_strlen_lent: strlen of a lent string;wp_memcpy_lent: memcpy of a prefix of a lent string, with its NUL, into an owned block, whose aux slots afterwards are what the copy left there (slots_after).
The token is persistent: a lent string is read, never given back, so no triple changes a lent string. Before it is lent, a name is owned whole (named), and a setter that changes it, such as setlocale(LC_ALL, ""), takes it:
wp_lend: a call that renames the keys whose names it is given, and lends the new names. The ghost heap renames them (rename_update); what the call must keep of the state is its premise, for the contract and wi to discharge.
Lent strings in the memory
The string t at p, lent by the world, in the memory m and against the ghost heap h: a C string through its NUL, not at null and ending before 2^64, in an object, or a read-only one, at a multiple of 8, and no byte of it in a live object owning a piece of memory of h.
The i-th byte of a string in memory.
Explore proof 9 tactics
Initial goal
revert a i
induction t as | x t IH ; intros a i Hs Hy ; discriminate Hy |
destruct Hs as _ & Hx & Hs
destruct i as | i ; cbn in Hy
2 open–injection Hy as ←
2 openrewrite Z.add_0_r
2 openexact Hx
–replace a + Z.of_natSi with a + 1 + Z.of_nati by lia
exact IH_ _ Hs Hy
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Overwriting pieces of memory keeps every name.
Explore proof 6 tactics
Initial goal
induction ps as | l v ps IH ; intros Hm ; reflexivity |
inversion Hm as [ |? ? Hl Hps ] ; subst
cbn [ overwrite fst snd ]
rewrite lookup_insert_ne ; exact IHHps |
intros →
exact Hl
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The bytes of a string in memory are not NUL.
Explore proof 4 tactics
Initial goal
revert a
induction t as | x t IH ; intros a Hs ; constructor |
destruct Hs as Hx & _ & Hs
constructor ; exact Hx | exact IH_ Hs
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The ghost heap h with the name of each key in ks renamed to new's: what a setter makes of the names it changes.
A renamed key has its new name.
Explore proof 6 tactics
Initial goal
induction ks as | k′ ks IH ; intros Hk ; destruct Hk |
cbn [ rename ]
destruct decidek′ = k as [ ->| Hne ] ; apply lookup_insert_eq |
rewrite lookup_insert_ne ; | congruence
apply IH
destruct Hk as Hk | Hk ; congruence | exact Hk
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Renaming changes no piece of memory, so a memory that agrees with h agrees with it renamed.
Explore proof 10 tactics
Initial goal
intros Ha
induction ks as | k ks IH ; exact Ha |
cbn [ rename ]
intros l v Hl
destruct decidel = PNamek as [ ->| Hne ]
2 open–rewrite lookup_insert_eq in Hl
2 openinjection Hl as ←
2 openexact I
–rewrite lookup_insert_ne in Hl ; | congruence
exact IHl v Hl
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Pieces that agree with every memory: ghost names and codecs.
A key that ps does not write keeps its piece.
Explore proof 8 tactics
Initial goal
induction ps as | l′ v′ ps IH ; intros Hl ; reflexivity |
cbn [ overwrite fst snd ]
apply not_elem_of_cons in Hl as Hne Hl
rewrite lookup_insert_ne ; exact IHHl |
intros E
apply Hne
symmetry
exact E
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Overwriting with ghost pieces keeps a memory agreeing.
Explore proof 5 tactics
Initial goal
intros Ha Hg l v Hl
destruct lookup_overwrite_ _ _ _ Hl as Hin | _ Hh ; | exact Hal v Hh
unfold ghost_ps in Hg
rewrite List.Forall_forall in Hg
exact Hgl, v proj1list_elem_of_In_ _ Hin m
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The aux slots of the n bytes from offset o of the object b in the memory m'.
There are n of them.
Explore proof 3 tactics
Initial goal
unfold slots_after
rewrite length_fmap length_seqZ
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A copy of the n bytes ys at s, which need not be the program's, into the block of the bytes xs and the slots cs at offset o of the live object b, both at multiples of 8: afterwards the destination's bytes are ys and its slots what the copy left there, and every piece outside it keeps its agreement.
Proof 43 steps Qed
Triples
The triples over any runtime R.
lent k p t: the world lends the string t at p under the key k; p is not null, t ends before 2^64 and its bytes are not NUL, facts of the lent value that hold from when the world lends it.
Lending is persistent.
Explore proof 1 tactics
Owning the names of the keys ks, the ghost heap may rename them, to any new names, which it then owns.
Explore proof 8 tactics
Initial goal
induction ks as | k ks IH ; iIntros Hh Hks ; iModIntro ; iFrame |
rewrite ! big_sepL_cons
iDestruct Hks as [Hk Hks]
iMod IH with Hh Hks as [Hh Hks]
iMod gen_heap_update with Hh Hk as [Hh Hk]
2 openiModIntro
2 opencbn [ rename ]
2 openiFrame
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The world interpretation keeps every lent string where lent_at says, in a memory whose live objects are apart, whose objects fit the address space and whose freed objects are empty, as a ready runtime's are.
The Iris instance of the registry and wi.
The expressions of the language.
In an interpreted state, a lent string is where lent_at says, against the state's ghost heap h, which h itself agrees with.
Explore proof 9 tactics
Initial goal
iIntros (%h & Hh & %Hf) [_ Hk]
destruct Hf as Ha & Hd & Hr & Hw
iDestruct gen_heap_valid with Hh Hk as %Hl
iExists h
iPureIntro
split ; exact Ha |
split ; exact Hd |
split ; exact Hr |
exact wi_lent_ _ _ _ _ _ Hw Hd R.address_space_ _ Hr R.freed_bounds_ _ Hr Hl
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call of the external g, with contract spec, returning a pointer, whose invocation from any state lending t at p under k admits the arguments xs and returns p, changing nothing: setlocale's query of the category k is one. d is bound to p.
Proof 24 steps Qed
A setter's triple: a call of the external g, with contract spec, returning a pointer, that renames the keys ks. Owning their names (named), the ghost pieces gs, whose keys are none of the names, and Q, from which spec admits the arguments xs in any state, the call lends the new names for good and gives the ghost pieces new values gs'. Every invocation that returns, from an interpreted state with the ghost heap h, returns some q with new names and ghost pieces, related by Rq, and keeps h's memory agreeing, the live objects apart and the runtime ready, while wi holds of the renamed h with gs' written over it (rename). d is bound to q. setlocale(LC_ALL, "") is one, renaming every category and giving the codec piece the new codec.
Proof 44 steps Qed
strlen's triple, from strlen_contract, for the string t lent at p: d is bound to t's length.
Proof 30 steps Qed
memcpy's triple, from memcpy_contract, of the first n bytes of the string t lent at p with its NUL, n at most t's length plus one, into the block of the n bytes xs and the slots cs at the 8-aligned offset o of the owned live object b, at a multiple of 8, where the copy keeps the world interpretation: the block's bytes are then that prefix, its slots what the copy left there, and d is bound to the block's pointer.
Proof 122 steps Qed
The prefix ys is in memory wherever t is a C string there.
LentLogicOn over a Logic instance of its own.