Fil-C on Nix

Filnix wiki

the formal campaign

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.
From iris.proofmode Require Import proofmode
From iris.base_logic.lib Require Import gen_heap
From iris.program_logic Require Import language weakestpre
From Stdlib Require Import ZArith Lia
From Stdlib Require String
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Run Machine Panics StepRules ExternalCalls ExternalMachine Pieces Heap ContractFrame Language Logic StringLogic MemLogic
Open Scope Z_scope
Open Scope list_scope

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.

51Definition lent_atm : mem h : gmappiece pval p : ptr t : listZ : Prop ≔
c_stringm p t ∧ 0 < ptr_addrp ∧ ptr_addrp + Z.of_natlengtht < 2 ^ 64 ∧ ∃b, ptr_capp = Objb ∨ ptr_capp = Rob ∧ b mod 8 = 0 ∧ ∀a, ptr_addrp ≤ a ≤ ptr_addrp + Z.of_natlengtht → ¬owned_liveh m a

The i-th byte of a string in memory.

57Lemma string_at_lookup
∀ m a t i y
t !! i = Somey
m_bytesm a + Z.of_nati = y
Explore proof 9 tactics

Initial goal

m :
a :
Z
t :
listZ
i :
nat
y :
Z
⊢
string_atm a t → t !! i = Somey → m_bytesm a + i = y

revert a i

m :
t :
listZ
y :
Z
⊢
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y

induction t as | x t IH ; intros a i Hs Hy ; discriminate Hy |

m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hs :
string_atm a x :: t
Hy :
x :: t !! i = Somey
⊢
m_bytesm a + i = y

destruct Hs as _ & Hx & Hs

m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
x :: t !! i = Somey
⊢
m_bytesm a + i = y

destruct i as | i ; cbn in Hy

2 open

m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
Somex = Somey
⊢
m_bytesm a + 0%nat = y
focused goal
m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
t !! i = Somey
⊢
m_bytesm a + Si = y

–injection Hy as ←

2 open

m :
x :
Z
t :
listZ
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somex → m_bytesm a + i = x
a :
Z
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
⊢
m_bytesm a + 0%nat = x
deferred goal
m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
t !! i = Somey
⊢
m_bytesm a + Si = y

rewrite Z.add_0_r

2 open

m :
x :
Z
t :
listZ
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somex → m_bytesm a + i = x
a :
Z
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
⊢
m_bytesm a = x
deferred goal
m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
t !! i = Somey
⊢
m_bytesm a + Si = y

exact Hx

deferred goal
m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
t !! i = Somey
⊢
m_bytesm a + Si = y

–replace a + Z.of_natSi with a + 1 + Z.of_nati by lia

m :
x :
Z
t :
listZ
y :
Z
IH :
∀a : Z i : nat, string_atm a t → t !! i = Somey → m_bytesm a + i = y
a :
Z
i :
nat
Hx :
m_bytesm a = x
Hs :
string_atm a + 1 t
Hy :
t !! i = Somey
⊢
m_bytesm a + 1 + i = y

exact IH_ _ Hs Hy

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
–injection Hy as ←
rewrite Z.add_0_r
exact Hx
–replace a + Z.of_natSi with a + 1 + Z.of_nati by lia
exact IH_ _ Hs Hy

Overwriting pieces of memory keeps every name.

66Lemma overwrite_name
∀ ps h k
Forallmem_piece ps.*1
overwriteps h !! PNamek = h !! PNamek
Explore proof 6 tactics

Initial goal

ps :
listpiece × pval
h :
k :
Z
⊢
Forallmem_piece ps.*1 → overwriteps h !! PNamek = h !! PNamek

induction ps as | l v ps IH ; intros Hm ; reflexivity |

v :
ps :
listpiece × pval
h :
k :
Z
IH :
Forallmem_piece ps.*1 → overwriteps h !! PNamek = h !! PNamek
Hm :
Forallmem_piece l, v :: ps.*1
⊢
overwritel, v :: ps h !! PNamek = h !! PNamek

inversion Hm as [ |? ? Hl Hps ] ; subst

v :
ps :
listpiece × pval
h :
k :
Z
IH :
Forallmem_piece ps.*1 → overwriteps h !! PNamek = h !! PNamek
Hm :
Forallmem_piece l, v :: ps.*1
Hps :
Forallmem_piece list_fmappiece × pval%type piece fst ps
⊢
overwritel, v :: ps h !! PNamek = h !! PNamek

cbn [ overwrite fst snd ]

v :
ps :
listpiece × pval
h :
k :
Z
IH :
Forallmem_piece ps.*1 → overwriteps h !! PNamek = h !! PNamek
Hm :
Forallmem_piece l, v :: ps.*1
Hps :
Forallmem_piece list_fmappiece × pval%type piece fst ps
⊢
<[l ≔ v]>overwriteps h !! PNamek = h !! PNamek

rewrite lookup_insert_ne ; exact IHHps |

v :
ps :
listpiece × pval
h :
k :
Z
IH :
Forallmem_piece ps.*1 → overwriteps h !! PNamek = h !! PNamek
Hm :
Forallmem_piece l, v :: ps.*1
Hps :
Forallmem_piece list_fmappiece × pval%type piece fst ps
⊢
l ≠ PNamek

intros →

v :
ps :
listpiece × pval
h :
k :
Z
IH :
Forallmem_piece ps.*1 → overwriteps h !! PNamek = h !! PNamek
Hm :
Forallmem_piece PNamek, v :: ps.*1
Hps :
Forallmem_piece list_fmappiece × pval%type piece fst ps
⊢
False

exact Hl

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

The bytes of a string in memory are not NUL.

75Lemma string_at_nonzero
∀ m a t
Forallλx ⇒ 0 < x < 256 t
Explore proof 4 tactics

Initial goal

m :
a :
Z
t :
listZ
⊢
string_atm a t → Forallλx : Z ⇒ 0 < x < 256 t

revert a

m :
t :
listZ
⊢
∀a : Z, string_atm a t → Forallλx : Z ⇒ 0 < x < 256 t

induction t as | x t IH ; intros a Hs ; constructor |

m :
x :
Z
t :
listZ
IH :
∀a : Z, string_atm a t → Forallλx : Z ⇒ 0 < x < 256 t
a :
Z
Hs :
string_atm a x :: t
⊢
Forallλx0 : Z ⇒ 0 < x0 < 256 x :: t

destruct Hs as Hx & _ & Hs

m :
x :
Z
t :
listZ
IH :
∀a : Z, string_atm a t → Forallλx : Z ⇒ 0 < x < 256 t
a :
Z
Hx :
0 < x < 256
Hs :
string_atm a + 1 t
⊢
Forallλx0 : Z ⇒ 0 < x0 < 256 x :: t

constructor ; exact Hx | exact IH_ Hs

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
revert a
induction t as | x t IH ; intros a Hs ; constructor |
destruct Hs as Hx & _ & Hs
constructor ; exact Hx | exact IH_ Hs

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.

83Fixpoint renameh : gmappiece pval ks : listZ new : Z → ptr × listZ : gmappiece pval ≔
match ks with
[ ]
⇒
h
k :: ks′
⇒
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks′ new

A renamed key has its new name.

90Lemma rename_lookup
∀ h ks new k
Ink ks
renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
Explore proof 6 tactics

Initial goal

h :
ks :
listZ
new :
Z → ptr × listZ
k :
Z
⊢
Ink ks → renameh ks new !! PNamek = SomeVNamenewk.1 newk.2

induction ks as | k′ ks IH ; intros Hk ; destruct Hk |

h :
k′ :
Z
ks :
listZ
new :
Z → ptr × listZ
k :
Z
IH :
Ink ks → renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
Hk :
Ink k′ :: ks
⊢
renameh k′ :: ks new !! PNamek = SomeVNamenewk.1 newk.2

cbn [ rename ]

h :
k′ :
Z
ks :
listZ
new :
Z → ptr × listZ
k :
Z
IH :
Ink ks → renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
Hk :
Ink k′ :: ks
⊢
<[PNamek′ ≔ VNamenewk′.1 newk′.2]>renameh ks new !! PNamek = SomeVNamenewk.1 newk.2

destruct decidek′ = k as [ ->| Hne ] ; apply lookup_insert_eq |

h :
k′ :
Z
ks :
listZ
new :
Z → ptr × listZ
k :
Z
IH :
Ink ks → renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
Hk :
Ink k′ :: ks
Hne :
k′ ≠ k
⊢
<[PNamek′ ≔ VNamenewk′.1 newk′.2]>renameh ks new !! PNamek = SomeVNamenewk.1 newk.2

rewrite lookup_insert_ne ; | congruence

h :
k′ :
Z
ks :
listZ
new :
Z → ptr × listZ
k :
Z
IH :
Ink ks → renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
Hk :
Ink k′ :: ks
Hne :
k′ ≠ k
⊢
renameh ks new !! PNamek = SomeVNamenewk.1 newk.2

apply IH

h :
k′ :
Z
ks :
listZ
new :
Z → ptr × listZ
k :
Z
IH :
Ink ks → renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
Hk :
Ink k′ :: ks
Hne :
k′ ≠ k
⊢
Ink ks

destruct Hk as Hk | Hk ; congruence | exact Hk

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

Renaming changes no piece of memory, so a memory that agrees with h agrees with it renamed.

100Lemma rename_agrees
∀ m h ks new
agreesm renameh ks new
Explore proof 10 tactics

Initial goal

m :
h :
ks :
listZ
new :
Z → ptr × listZ
⊢
agreesm h → agreesm renameh ks new

intros Ha

m :
h :
ks :
listZ
new :
Z → ptr × listZ
Ha :
⊢
agreesm renameh ks new

induction ks as | k ks IH ; exact Ha |

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
⊢
agreesm renameh k :: ks new

cbn [ rename ]

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
⊢
agreesm <[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new

intros l v Hl

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new !! l = Somev
⊢

destruct decidel = PNamek as [ ->| Hne ]

2 open

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new !! PNamek = Somev
focused goal
m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new !! l = Somev
Hne :
l ≠ PNamek
⊢

–rewrite lookup_insert_eq in Hl

2 open

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
SomeVNamenewk.1 newk.2 = Somev
deferred goal
m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new !! l = Somev
Hne :
l ≠ PNamek
⊢

injection Hl as ←

2 open

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
⊢
agree_piecem PNamek VNamenewk.1 newk.2
deferred goal
m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new !! l = Somev
Hne :
l ≠ PNamek
⊢

exact I

deferred goal
m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hl :
<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new !! l = Somev
Hne :
l ≠ PNamek
⊢

–rewrite lookup_insert_ne in Hl ; | congruence

m :
h :
k :
Z
ks :
listZ
new :
Z → ptr × listZ
Ha :
IH :
agreesm renameh ks new
v :
Hne :
l ≠ PNamek
Hl :
renameh ks new !! l = Somev
⊢

exact IHl v Hl

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros Ha
induction ks as | k ks IH ; exact Ha |
cbn [ rename ]
intros l v Hl
destruct decidel = PNamek as [ ->| Hne ]
–rewrite lookup_insert_eq in Hl
injection Hl as ←
exact I
–rewrite lookup_insert_ne in Hl ; | congruence
exact IHl v Hl

Pieces that agree with every memory: ghost names and codecs.

109Definition ghost_psps : listpiece × pval : Prop ≔
Forallλlv ⇒ ∀m, agree_piecem lv.1 lv.2 ps

A key that ps does not write keeps its piece.

113Lemma overwrite_out
∀ ps h l
l ∉ ps.*1
overwriteps h !! l = h !! l
Explore proof 8 tactics

Initial goal

ps :
listpiece × pval
h :
⊢
l ∉ ps.*1 → overwriteps h !! l = h !! l

induction ps as | l′ v′ ps IH ; intros Hl ; reflexivity |

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hl :
l ∉ l′, v′ :: ps.*1
⊢
overwritel′, v′ :: ps h !! l = h !! l

cbn [ overwrite fst snd ]

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hl :
l ∉ l′, v′ :: ps.*1
⊢
<[l′ ≔ v′]>overwriteps h !! l = h !! l

apply not_elem_of_cons in Hl as Hne Hl

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hne :
l ≠ l′, v′.1
Hl :
l
∉
fix go l : listpiece × pval : listpiece ≔
match l with
[ ]
⇒
[ ]
x :: l0
⇒
x.1 :: gol0
ps
⊢
<[l′ ≔ v′]>overwriteps h !! l = h !! l

rewrite lookup_insert_ne ; exact IHHl |

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hne :
l ≠ l′, v′.1
Hl :
l
∉
fix go l : listpiece × pval : listpiece ≔
match l with
[ ]
⇒
[ ]
x :: l0
⇒
x.1 :: gol0
ps
⊢
l′ ≠ l

intros E

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hne :
l ≠ l′, v′.1
Hl :
l
∉
fix go l : listpiece × pval : listpiece ≔
match l with
[ ]
⇒
[ ]
x :: l0
⇒
x.1 :: gol0
ps
E :
l′ = l
⊢
False

apply Hne

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hne :
l ≠ l′, v′.1
Hl :
l
∉
fix go l : listpiece × pval : listpiece ≔
match l with
[ ]
⇒
[ ]
x :: l0
⇒
x.1 :: gol0
ps
E :
l′ = l
⊢
l = l′, v′.1

symmetry

l′ :
v′ :
ps :
listpiece × pval
h :
IH :
l ∉ ps.*1 → overwriteps h !! l = h !! l
Hne :
l ≠ l′, v′.1
Hl :
l
∉
fix go l : listpiece × pval : listpiece ≔
match l with
[ ]
⇒
[ ]
x :: l0
⇒
x.1 :: gol0
ps
E :
l′ = l
⊢
l′, v′.1 = l

exact E

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

Overwriting with ghost pieces keeps a memory agreeing.

121Lemma ghost_agrees
∀ m h ps
Explore proof 5 tactics

Initial goal

m :
h :
ps :
listpiece × pval
⊢
agreesm h → ghost_psps → agreesm overwriteps h

intros Ha Hg l v Hl

m :
h :
ps :
listpiece × pval
Ha :
Hg :
v :
Hl :
overwriteps h !! l = Somev
⊢

destruct lookup_overwrite_ _ _ _ Hl as Hin | _ Hh ; | exact Hal v Hh

m :
h :
ps :
listpiece × pval
Ha :
Hg :
v :
Hl :
overwriteps h !! l = Somev
Hin :
l, v ∈ ps
⊢

unfold ghost_ps in Hg

m :
h :
ps :
listpiece × pval
Ha :
Hg :
Forallλlv : piece × pval ⇒ ∀m : mem, agree_piecem lv.1 lv.2 ps
v :
Hl :
overwriteps h !! l = Somev
Hin :
l, v ∈ ps
⊢

rewrite List.Forall_forall in Hg

m :
h :
ps :
listpiece × pval
Ha :
v :
Hl :
overwriteps h !! l = Somev
Hin :
l, v ∈ ps
Hg :
∀x : piece × pval, Inx ps → ∀m : mem, agree_piecem x.1 x.2
⊢

exact Hgl, v proj1list_elem_of_In_ _ Hin m

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

The aux slots of the n bytes from offset o of the object b in the memory m'.

130Definition slots_afterm′ : mem b o : Z n : nat : listcap ≔
λi ⇒ m_auxm′ b + o + i <$> seqZ0 Z.of_natn

There are n of them.

134Lemma length_slots_after
∀ m′ b o n
lengthslots_afterm′ b o n = n
Explore proof 3 tactics

Initial goal

m′ :
b, o :
Z
n :
nat
⊢
lengthslots_afterm′ b o n = n

unfold slots_after

m′ :
b, o :
Z
n :
nat
⊢
lengthλi : Z ⇒ m_auxm′ b + o + i <$> seqZ0 n = n

rewrite length_fmap length_seqZ

m′ :
b, o :
Z
n :
nat
⊢
Z.to_natn = n

lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
rewrite length_fmap length_seqZ
lia

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.

142Lemma lent_copy_after
∀ m m′ b reg o xs cs s ys
live_atm b reg
b mod 8 = 0
o mod 8 = 0
lengthys = lengthxs
lengthcs = lengthxs
all_agreem byte_psb o xs ++ aux_psb o cs
∀i y, ys !! i = Somey → m_bytesm ptr_addrs + Z.of_nati = y
copy_resultm mkPtrb + o Objb s Z.of_natlengthxs m′
all_agreem′ byte_psb o ys ++ aux_psb o slots_afterm′ b o lengthxs ∧ frame_okbyte_psb o xs ++ aux_psb o cs.*1 m m′
Proof 43 steps Qed
intros Hd Hl Hb8 Ho8 Hly Hlc Hdst Hys Hres
pose proof Hres as Hfr & Hcb & _
pose proof Hfr as Hr & _ & _
split ; | exact block_frame_ _ _ _ _ _ _ Hd Hl Hb8 Ho8 Hlc Hdst Hfr
pose proof Hdst as Hdst′
apply all_agree_app in Hdst' as Hx _
destruct Hl as E0 L0
assert Hreg : registeredm' b by unfold registered ; rewrite Hr E0 ; discriminate
assert Hbyte : ∀i, i < lengthxs%nat → 0 ≤ o + Z.of_nati ∧ b + o + Z.of_nati < r_endreg
{intros i Hi
destruct lookup_lt_is_Some_2xs i Hi as x Hxi
destruct byte_ps_agree_ _ _ _ _ _ _ conjE0 L0 Hx Hxi as _ & H1 & H2
lia
split ; apply all_agree_intro ; intros l v Hin
–apply byte_ps_elem in Hin as i & y & Hyi & → & →
assert Hi : i < lengthxs%nat by rewrite <- Hly ; exact lookup_lt_Some_ _ _ Hyi
destruct Hbytei Hi as H1 H2
cbn [ agree_piece ]
split ; exact Hreg |
intros reg0 E L
rewrite Hr E0 in E
injection E as ←
split ; exact H1 |
split ; exact H2 |
rewrite Hcb ; | unfold span_contains ; cbn ; lia
cbn [ ptr_addr ]
replace ptr_addrs + b + o + Z.of_nati − b + o with ptr_addrs + Z.of_nati by lia
exact Hysi y Hyi
–apply aux_ps_elem in Hin as i & c & Hci & → & →
unfold slots_after in Hci
apply list_lookup_fmap_Some in Hci as z & → & Hz
apply lookup_seqZ in Hz as → Hi
destruct Hbytei ltac:lia as H1 H2
cbn [ agree_piece ]
split ; exact Hreg |
intros reg0 E L
rewrite Hr E0 in E
injection E as ←
split ; exact H1 |
split ; exact H2 |
left
reflexivity

Triples

The triples over any runtime R.

178Module LentLogicOn R : Runtime LG0 : LogicSigR
179Module ML ≔ MemLogicOn R LG0
180Module SL ≔ ML.SL
181Module LG ≔ ML.LG
182Module L ≔ LG.L
183Module SLen ≔ StringLengths R
Import L LG SL ML
186Section lent
187Context `{!invGS_genhlc Σ, !gen_heapGSpiece pval Σ}

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.

192Definition lentk : Z p : ptr t : listZ : iPropΣ ≔
⌜0 < ptr_addrp ∧ ptr_addrp + Z.of_natlengtht < 2 ^ 64 ∧ Forallλx ⇒ 0 < x < 256 t⌝ ∗ pointstoPNamek DfracDiscarded VNamep t

Lending is persistent.

196Instance lent_persistentk p t : Persistentlentk p t
Explore proof 1 tactics

Initial goal

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
k :
Z
p :
t :
listZ
⊢
Persistentlentk p t

apply _

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
apply _

named k p t: the name t at p of the key k, owned whole and not yet lent. A setter that changes k's name takes it (wp_lend).

201Definition namedk : Z p : ptr t : listZ : iPropΣ ≔
pointstoPNamek DfracOwn1 VNamep t

Owning the names of the keys ks, the ghost heap may rename them, to any new names, which it then owns.

206Lemma rename_update
∀ h ks old new
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Explore proof 8 tactics

Initial goal

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
ks :
listZ
old, new :
Z → ptr × listZ
⊢
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2

induction ks as | k ks IH ; iIntros Hh Hks ; iModIntro ; iFrame |

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hh :
gen_heap_interph
Hks :
∗k0∈k :: ksnamedk0 oldk0.1 oldk0.2
∗
|⇛ gen_heap_interprenameh k :: ks new ∗ ∗k0∈k :: ksnamedk0 newk0.1 newk0.2

rewrite ! big_sepL_cons

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hh :
gen_heap_interph
Hks :
namedk oldk.1 oldk.2 ∗ ∗y∈ksnamedy oldy.1 oldy.2
∗
|⇛ gen_heap_interprenameh k :: ks new ∗ namedk newk.1 newk.2 ∗ ∗y∈ksnamedy newy.1 newy.2

iDestruct Hks as [Hk Hks]

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hh :
gen_heap_interph
Hk :
namedk oldk.1 oldk.2
Hks :
∗y∈ksnamedy oldy.1 oldy.2
∗
|⇛ gen_heap_interprenameh k :: ks new ∗ namedk newk.1 newk.2 ∗ ∗y∈ksnamedy newy.1 newy.2

iMod IH with Hh Hks as [Hh Hks]

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hk :
namedk oldk.1 oldk.2
Hh :
gen_heap_interprenameh ks new
Hks :
∗k0∈ksnamedk0 newk0.1 newk0.2
∗
|⇛ gen_heap_interprenameh k :: ks new ∗ namedk newk.1 newk.2 ∗ ∗y∈ksnamedy newy.1 newy.2

iMod gen_heap_update with Hh Hk as [Hh Hk]

2 open

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hks :
∗k0∈ksnamedk0 newk0.1 newk0.2
Hh :
gen_heap_interp<[PNamek ≔ ?Goal]>renameh ks new
Hk :
pointstoPNamek DfracOwn1 ?Goal
∗
|⇛ gen_heap_interprenameh k :: ks new ∗ namedk newk.1 newk.2 ∗ ∗y∈ksnamedy newy.1 newy.2
shelved goal
hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
⊢

iModIntro

2 open

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hks :
∗k0∈ksnamedk0 newk0.1 newk0.2
Hh :
gen_heap_interp<[PNamek ≔ ?Goal]>renameh ks new
Hk :
pointstoPNamek DfracOwn1 ?Goal
∗
gen_heap_interprenameh k :: ks new ∗ namedk newk.1 newk.2 ∗ ∗y∈ksnamedy newy.1 newy.2
shelved goal
hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
⊢

cbn [ rename ]

2 open

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
Hks :
∗k0∈ksnamedk0 newk0.1 newk0.2
Hh :
gen_heap_interp<[PNamek ≔ ?Goal]>renameh ks new
Hk :
pointstoPNamek DfracOwn1 ?Goal
∗
gen_heap_interp<[PNamek ≔ VNamenewk.1 newk.2]>renameh ks new ∗ namedk newk.1 newk.2 ∗ ∗y∈ksnamedy newy.1 newy.2
shelved goal
hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
h :
k :
Z
ks :
listZ
old, new :
Z → ptr × listZ
IH :
gen_heap_interph −∗ ∗k∈ksnamedk oldk.1 oldk.2 ⇛ gen_heap_interprenameh ks new ∗ ∗k∈ksnamedk newk.1 newk.2
⊢

iFrame

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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]
iModIntro
cbn [ rename ]
iFrame
216Section calls
217Context world : Type registry : name → optioncontractworld wi : mem → world → gmappiece pval → Prop `{!SafepointStablewi} ge : genv

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.

224Hypothesis wi_lent
∀ m w h k p t
lent_atm h p t

The Iris instance of the registry and wi.

229Instance lent_irisGS: irisGS_genhlc nanofil_langregistry ge Σ ≔
nanofil_irisGSregistry wi ge

The expressions of the language.

233Notation lexpr ≔ language.exprnanofil_langregistry ge

In an interpreted state, a lent string is where lent_at says, against the state's ghost heap h, which h itself agrees with.

237Lemma lent_facts
∀ σ k p t
heap_interpwi σ −∗ lentk p t −∗ ∃h, ⌜agreesls_memσ h ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h p t⌝
Explore proof 9 tactics

Initial goal

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
⊢
heap_interpwi σ −∗ lentk p t −∗ ∃h : gmappiece pval, ⌜agreesls_memσ h ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h p t⌝

iIntros (%h & Hh & %Hf) [_ Hk]

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Hf :
agreesLentLogicOn.LG.L.ls_memσ h ∧ live_disjointLentLogicOn.LG.L.ls_memσ ∧ R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ ∧ wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hh :
gen_heap_interph
Hk :
pointstoPNamek DfracDiscarded VNamep t
∗
∃h0 : gmappiece pval, ⌜agreesls_memσ h0 ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h0 p t⌝

destruct Hf as Ha & Hd & Hr & Hw

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hh :
gen_heap_interph
Hk :
pointstoPNamek DfracDiscarded VNamep t
∗
∃h0 : gmappiece pval, ⌜agreesls_memσ h0 ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h0 p t⌝

iDestruct gen_heap_valid with Hh Hk as %Hl

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hl :
h !! PNamek = SomeVNamep t
Hh :
gen_heap_interph
Hk :
pointstoPNamek DfracDiscarded VNamep t
∗
∃h0 : gmappiece pval, ⌜agreesls_memσ h0 ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h0 p t⌝

iExists h

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hl :
h !! PNamek = SomeVNamep t
Hh :
gen_heap_interph
Hk :
pointstoPNamek DfracDiscarded VNamep t
∗
⌜agreesls_memσ h ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h p t⌝

iPureIntro

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hl :
h !! PNamek = SomeVNamep t
⊢
agreesls_memσ h ∧ live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h p t

split ; exact Ha |

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hl :
h !! PNamek = SomeVNamep t
⊢
live_disjointls_memσ ∧ R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h p t

split ; exact Hd |

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hl :
h !! PNamek = SomeVNamep t
⊢
R.readyls_rtσ ls_memσ ∧ lent_atls_memσ h p t

split ; exact Hr |

hlc :
has_lc
Σ :
gFunctors
invGS_gen0 :
invGS_genhlc Σ
gen_heapGS0 :
gen_heapGSpiece pval Σ
world :
Type
registry :
name → optioncontractworld
wi :
mem → world → gmappiece pval → Prop
SafepointStable0 :
ge :
wi_lent :
∀m : mem w : world h : gmappiece pval k : Z p : ptr t : listZ, wim w h → live_disjointm → objects_fitm_regionsm → freed_emptym_regionsm → h !! PNamek = SomeVNamep t → lent_atm h p t
k :
Z
p :
t :
listZ
h :
Ha :
agreesLentLogicOn.LG.L.ls_memσ h
Hd :
live_disjointLentLogicOn.LG.L.ls_memσ
Hr :
R.readyLentLogicOn.LG.L.ls_rtσ LentLogicOn.LG.L.ls_memσ
Hw :
wiLentLogicOn.LG.L.ls_memσ LentLogicOn.LG.L.ls_worldσ h
Hl :
h !! PNamek = SomeVNamep t
⊢

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
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

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.

252Lemma wp_lent_query
∀ f e ls lab d g args rest j spec xs k p t Φ
registryg = Somespec
find_fnge g = None
map_optionarg_xge e args = Somexs
∀m w h, wim w h → h !! PNamek = SomeVNamep t → contract_prespec xs m w
∀s m w h trace ending s′ m′ w′, wim w h → h !! PNamek = SomeVNamep t → M.E.invokespec CResultd P args xs s m w trace ending s′ m′ w′ → s′ = s ∧ m′ = m ∧ w′ = w ∧ ending = CallReturnWPtrp
lentk p t −∗ ▷WPERunmkFramef putd WPtrp e ls None Execlab rest j : lexpr {Φ} −∗ WPERunmkFramef e ls None Execlab CallCResultd P Globalg args :: rest j : lexpr {Φ}
Proof 24 steps Qed
intros Hreg Hret Hfn Hdata Hfree Hx Habi Hpre Hinv
iIntros #Hk HK
iApply wp_external_ _ _ _ _ _ _ _ _ _ _ _ spec xs lentk p t with Hk [HK] ; done | done | done | done | done | done | |
–iIntros σ (%h & Hh & %Hf) [_ Hk′]
destruct Hf as _ & _ & _ & Hw
iDestruct gen_heap_valid with Hh Hk′ as %Hl
iPureIntro
exact Hpre_ _ _ Hw Hl
–iNext
iIntros σ trace values s′ m′ w′ Hi (%h & Hh & %Hf) [_ Hk′]
pose proof Hf as _ & _ & _ & Hw
iDestruct gen_heap_valid with Hh Hk′ as %Hl
destruct Hinv_ _ _ _ _ _ _ _ _ Hw Hl Hi as → & → & → & He
injection He as →
iModIntro
iExists _
iSplit
+iPureIntro
rewrite Hret
reflexivity
+destruct σ as m s fuel w
iSplitL Hh ; iExists h ; iFrame Hh ; iPureIntro ; exact Hf |
iExact HK

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.

291Lemma wp_lend
∀ f e ls lab d g args rest j spec xs ks old gs Rq : ptr → Z → ptr × listZ → listpiece × pval → Prop Q : iPropΣ Φ
registryg = Somespec
find_fnge g = None
map_optionarg_xge e args = Somexs
Forallλk ⇒ PNamek ∉ gs.*1 ks
∀σ, heap_interpwi σ −∗ Q −∗ ⌜contract_prespec xs ls_memσ ls_worldσ⌝
∀s m w h trace values s′ m′ w′, wim w h → agreesm h → live_disjointm → R.readys m → M.E.invokespec CResultd P args xs s m w trace CallReturnvalues s′ m′ w′ → ∃q new gs′, values = WPtrq ∧ Rqq new gs′ ∧ gs′.*1 = gs.*1 ∧ ghost_psgs′ ∧ agreesm′ h ∧ live_disjointm′ ∧ R.readys′ m′ ∧ wim′ w′ overwritegs′ renameh ks new
∗k∈ksnamedk oldk.1 oldk.2 −∗ ptsgs −∗ Q −∗ ▷∀q new gs′, ⌜Rqq new gs′⌝ −∗ Q −∗ ptsgs′ −∗ ∗k∈kslentk newk.1 newk.2 −∗ WPERunmkFramef putd WPtrq e ls None Execlab rest j : lexpr {Φ} −∗ WPERunmkFramef e ls None Execlab CallCResultd P Globalg args :: rest j : lexpr {Φ}
Proof 44 steps Qed
intros Hreg Hret Hfn Hdata Hfree Hx Habi Hgs Hpre Hpost
iIntros Hks Hgs HQ HK
iApply wp_external_ _ _ _ _ _ _ _ _ _ _ _ spec xs Q ∗ ∗k∈ksnamedk oldk.1 oldk.2 ∗ ptsgs%I with [$HQ $Hks $Hgs] [HK] ; done | done | done | done | done | done | |
–iIntros σ Hσ [HQ _]
iApply Hpre with Hσ HQ
–iNext
iIntros σ trace values s′ m′ w′ Hi (%h & Hh & %Hf) (HQ & Hks & Hgs)
destruct Hf as Ha & Hd & Hr & Hw
destruct Hpost_ _ _ _ _ _ _ _ _ Hw Ha Hd Hr Hi as q & new & gs′ & → & Hq & Hkeys & Hghost & Ha′ & Hd′ & Hr′ & Hw′
iMod rename_update_ _ _ new with Hh Hks as [Hh Hks]
iMod pts_update_ _ gs' Hkeys with Hh Hgs as [Hh Hgs]
iAssert |⇛ ∗k∈kslentk newk.1 newk.2%I with [Hks] as >Hl
{iApply big_sepL_bupd
iApply big_sepL_impl with Hks
iIntros !> i k Hik Hk
iMod pointsto_persist with Hk as Hk
iModIntro
iFrame Hk
iPureIntro
assert Hin : Ink ks by apply list_elem_of_In ; exact list_elem_of_lookup_2_ _ _ Hik
assert Hk : overwritegs' renameh ks new !! PNamek = SomeVNamenewk.1 newk.2
{rewrite overwrite_out ; exact rename_lookuph ks new k Hin |
rewrite Hkeys
rewrite List.Forall_forall in Hgs
exact Hgsk Hin
destruct wi_lent_ _ _ _ _ _ Hw' Hd' R.address_space_ _ Hr' R.freed_bounds_ _ Hr' Hk as _ Hs & H0 & Hlen & _
split ; exact H0 |
split ; exact Hlen | exact string_at_nonzero_ _ _ Hs
iModIntro
iExists _
iSplit
+iPureIntro
rewrite Hret
reflexivity
+iSplitL Hh
∗iExists _
iFrame Hh
iPureIntro
split ; exact ghost_agrees_ _ _ rename_agrees_ _ _ _ Ha' Hghost |
auto
∗iApply HK with [%] HQ Hgs Hl
exact Hq

strlen's triple, from strlen_contract, for the string t lent at p: d is bound to t's length.

339Lemma wp_strlen_lent
∀ f e ls lab d v rest j k p t Φ
registryTAtom"strlen" = Somestrlen_contractworld
find_fnge TAtom"strlen" = None
lookupTAtom"strlen" ge_globalsge = None
arg_xge e ArgP v = SomeWPtrp
lentk p t −∗ ▷WPERunmkFramef putd WIntZ.of_natlengtht e ls None Execlab rest j : lexpr {Φ} −∗ WPERunmkFramef e ls None Execlab CallCResultd L GlobalTAtom"strlen" ArgP v :: rest j : lexpr {Φ}
Proof 30 steps Qed
intros Hreg Hfn Hdata Hv
iIntros #Hk HK
iApply wp_external_ _ _ _ _ _ _ _ _ _ _ _ strlen_contractworld WPtrp lentk p t with Hk [HK] ; done | done | done | done | cbn [ map_option ] ; rewrite Hv ; done | | |
–split ; right ; eexists ; reflexivity | eexists ; reflexivity
–iIntros σ Hσ Hk′
iDestruct lent_facts with Hσ Hk′ as %h & _ & _ & Hr & Hs & _
iPureIntro
exists p, Z.of_natlengtht
split ; reflexivity |
–iNext
iIntros σ trace values s′ m′ w′ Hinv Hσ Hk′
iDestruct lent_facts with Hσ Hk′ as %h & _ & _ & Hr & Hs & _
pose proof SLen.c_string_length_ _ _ _ Hr Hs as Ht
destruct M.E.strlen_invocation_ _ _ _ _ _ _ _ _ _ _ _ Hinv as _ & → & → & p′ & n & Hx & Hn & He
injection Hx as ←
injection He as →
rewrite terminated_length_unique_ _ _ _ Hn Ht
iDestruct pure_return with Hσ as Hσ ; exact Hinv |
destruct σ as m s fuel w
iModIntro
iExists _
iSplit
+iPureIntro
cbn
rewrite Z.mod_small ; reflexivity |
destruct Ht as _ ?
lia
+iFrame Hσ
iExact HK

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.

376Lemma wp_memcpy_lent
∀ f e ls lab d vd vs vn rest j b reg o xs cs k p t Φ
registryTAtom"memcpy" = Somememcpy_contractworld
find_fnge TAtom"memcpy" = None
lookupTAtom"memcpy" ge_globalsge = None
arg_xge e ArgP vd = SomeWPtrmkPtrb + o Objb
arg_xge e ArgP vs = SomeWPtrp
arg_xge e ArgL vn = SomeWIntZ.of_natlengthxs
lengthxs ≤ Slengtht%nat
lengthcs = lengthxs
b mod 8 = 0
o mod 8 = 0
0 ≤ o
b + o + Z.of_natlengthxs ≤ r_endreg
∀m m′ wd h, copy_resultm mkPtrb + o Objb p Z.of_natlengthxs m′ → ∀l v, l, v ∈ block_psb reg o xs cs → h !! l = Somev → wim wd h → wim′ wd overwriteblock_psb reg o takelengthxs t ++ 0 slots_afterm′ b o lengthxs h
lentk p t −∗ liveb reg −∗ bytesb o xs −∗ auxesb o cs −∗ ▷∀cs′, ⌜lengthcs′ = lengthxs⌝ −∗ liveb reg −∗ bytesb o takelengthxs t ++ 0 −∗ auxesb o cs′ −∗ WPERunmkFramef putd WPtrmkPtrb + o Objb e ls None Execlab rest j : lexpr {Φ} −∗ WPERunmkFramef e ls None Execlab CallCResultd P GlobalTAtom"memcpy" ArgP vd; ArgP vs; ArgL vn :: rest j : lexpr {Φ}
Proof 122 steps Qed
intros Hreg Hfn Hdata Hpd Hps Hn Hlt Hlc Hb8 Ho8 Ho Hend Hwi
iIntros #Hk Hl Hx Hcs HK
set n := lengthxs
set ys := taken t ++ 0
assert Hly : lengthys = n by unfold ys ; rewrite length_take length_app ; cbn ; lia

The prefix ys is in memory wherever t is a C string there.

assert Hys : ∀m, c_stringm p t → ∀i y, ys !! i = Somey → m_bytesm ptr_addrp + Z.of_nati = y
{intros m _ Hs i y Hy
pose proof string_at_length_ _ _ Hs as _ Hnul
unfold ys in Hy
apply lookup_take_Some in Hy as Hy _
destruct decidei < lengtht%nat as Hi | Hi
–rewrite lookup_app_l in Hy ; | exact Hi
exact string_at_lookup_ _ _ _ _ Hs Hy
–rewrite lookup_app_r in Hy ; | lia
apply list_lookup_singleton_Some in Hy as Hi′ ←
replace Z.of_nati with Z.of_natlengtht by lia
exact Hnul
iDestruct block_ptsb reg o xs cs with [$Hl $Hx $Hcs] as Hdst
iApply wp_external_ _ _ _ _ _ _ _ _ _ _ _ memcpy_contractworld WPtrmkPtrb + o Objb; WPtrp; WIntZ.of_natn ptsblock_psb reg o xs cs ∗ lentk p t with [$Hdst $Hk] [HK] ; done | done | done | done | cbn [ map_option ] ; rewrite Hpd Hps Hn ; done | | |
–split ; right ; eexists ; reflexivity | exists vd, vs, vn ; reflexivity
–iIntros σ Hσ [Hdst Hk′]
iDestruct pts_facts with Hσ Hdst as %Ha & Hd & Hfit
iDestruct Hσ as h [Hh %Hf]
iDestruct pts_lookup with Hh Hdst as %Hlk
iDestruct Hk′ as [_ Hk′]
iDestruct gen_heap_valid with Hh Hk′ as %Hlent
iPureIntro
destruct Hf as _ & _ & Hr & Hw
destruct wi_lent_ _ _ _ _ _ Hw Hd R.address_space_ _ Hr R.freed_bounds_ _ Hr Hlent as Hs & _ & _ & Hal & Hapart
destruct Ha as E L _
cbn [ fst snd ] in E , L
destruct Hfitb reg E as Hb0 Hfit′
assert Hown : ∀a, b ≤ a < r_endreg → owned_liveh ls_memσ a
{intros a Ha
exists PLiveb, VLivereg, reg
split ; apply Hlk ; left |
split ; exact I |
split ; split ; exact E | exact L | exact Ha
eexists _, _, _
split ; reflexivity |
split ; | split ; | split
+split ; lia |
split ; lia |
split
∗unfold writable_span
split ; lia |
exists b, reg
split ; reflexivity |
split ; exact E |
split ; exact L |
apply access_obj_ _ reg ; exact E | lia | lia | apply Z.mod_1_r
∗right
exists b
auto
+apply readable_bytes_prefix_ _ Z.of_natlengtht + 1 ; | lia
+destruct Hal as b′ & Hc & Hb′
right
exists b'
auto
+right
right
cbn [ ptr_addr ]
destruct Z.le_gt_casesb + o + Z.of_natn ptr_addrp as H | H ; left ; exact H |
destruct Z.le_gt_casesptr_addrp + Z.of_natn b + o as H′ | H′ ; right ; exact H' |
exfalso
apply HapartZ.maxptr_addrp b + o ; lia |
apply Hown
lia
–iNext
iIntros σ trace values s′ m′ w′ Hinv (%h & Hh & %Hf) [Hdst [_ Hk′]]
destruct Hf as Ha & Hd & Hr & Hw
iDestruct gen_heap_valid with Hh Hk′ as %Hlent
destruct wi_lent_ _ _ _ _ _ Hw Hd R.address_space_ _ Hr R.freed_bounds_ _ Hr Hlent as Hs & _
destruct M.E.copy_invocation_ _ _ _ _ _ _ _ _ _ _ _ _ _ Hinv as _ & → & d′ & s0 & n′ & Hx & _ & Hres & He
injection Hx as ← ← ←
injection He as →
iDestruct pts_lookup with Hh Hdst as %Hlk
assert Hold : all_agreels_memσ block_psb reg o xs cs
intros l v Hin
exact Hal v Hlkl v Hin
destruct Hold as Hlv Hold
cbn [ agree_piece fst snd ] in Hlv
destruct lent_copy_afterls_memσ m' b reg o xs cs p ys Hd Hlv Hb8 Ho8 Hly Hlc Hold Hys_ Hs Hres as Hnew Hfr
destruct M.E.invoke_prefix_ _ _ _ _ _ _ _ _ _ _ _ _ Hinv as born & Hpre
destruct M.E.prefix_preserve_ _ _ _ _ _ _ _ _ _ _ Hpre Hr as Hr′ _
pose proof Hres as Hregs & _ & _
assert Hk : block_psb reg o ys slots_afterm' b o n.*1 = block_psb reg o xs cs.*1
{apply block_ps_keys ; exact Hly | rewrite length_slots_after ; lia
iMod pts_update_ _ block_psb reg o ys slots_afterm' b o n with Hh Hdst as [Hh Hdst] ; exact Hk |
iModIntro
iExists _
iSplit ; iPureIntro ; reflexivity |
iSplitL Hh
+iExists _
iFrame Hh
iPureIntro
split ; | split ; | split
∗intros l v Hl′
destruct lookup_overwrite_ _ _ _ Hl' as Hin | Hnk Hh
--apply elem_of_cons in Hin as Hin | Hin
++injection Hin as → →
cbn [ agree_piece ]
exact live_at_regions_ _ _ _ Hregs Hlv
++exact all_agree_elem_ _ _ _ Hnew Hin
--apply Hfr ; | exact Hal v Hh
intros Hk′
apply Hnk
rewrite Hk
cbn [ fmap list_fmap fst block_ps ]
right
exact Hk'
∗exact live_disjoint_regions_ _ Hregs Hd
∗exact Hr'
∗exact Hwi_ _ _ _ Hres Hlk Hw
+rewrite ! block_pts
iDestruct Hdst as (Hl & Hx & Hcs)
iApply HK $! slots_afterm' b o n with [%] Hl Hx Hcs

LentLogicOn over a Logic instance of its own.

481Module LentLogic R : Runtime
482Module LG0 ≔ Logic R
Include LentLogicOn R LG0