rocq/theories/HiLogic.v
tests/c/prog/hi.c through the program logic of Logic.v, with puts called through Campaign 4's contract (puts_contract).
Hi.v proves hi's body safe by hand: an invariant over the labelled machine's states with a case for each of main's four points, and a lemma for each kind of labelled step at each. This file proves the same body in Iris, by one rule per instruction and StringLogic.v's triple for puts (wp_puts):
- the program owns its literal
str.10as astring: its life and its six bytes (lit_ps); - the world interpretation is
stdio_wi: puts's rep andstdio_ready, and the world's writable roots apart from the program's live objects; a safepoint keeps it under Hi.v's premise that it keeps rep and readiness; - main enters, copies the literal, calls puts and returns 0 (
main_spec), and Iris adequacy for the labelled machine (heap_labelled_safe) makes thathi_logic_safe.
The theorem's premises beyond Hi.v's hi_before_call are the logic's own: the runtime ready, the live objects apart, and the world's roots apart from the literal (literal_apart). Its conclusion is the logic's: no run stops with a failure_ending, and main returns 0; Hi.v's hi_ending lists the stops that remain by name. docs/logic.md compares the two proofs.
The literal
The literal's object, str.10's region in the module's layout.
The literal's bytes: hello and its NUL.
The pieces of the literal the program owns, as a string: its life and its six bytes.
The literal is a string in its object.
Explore proof 5 tactics
Initial goal
unfold string_ok
cbn
split ; right ; reflexivity |
repeat split ; try lia
repeat constructor ; lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The six byte pieces, one by one.
Explore proof 4 tactics
Initial goal
cbn
rewrite ! elem_of_cons elem_of_nil
intros Hp | Hp ; left ; exact Hp | right
repeat destruct Hp as Hp | Hp ; try contradiction ; injection Hp as → → ; eexists ; split ; | split ; reflexivity ; lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
No writable root of the world w reaches into the literal's object.
hi over any runtime R.
Where the literal is valid (Hi.v's hi_literal_valid: its region and its string), every piece of the literal agrees.
Explore proof 13 tactics
Initial goal
intros Hreg Hs l v Hin
destruct lit_ps_casesl v Hin as Hp | i & Hi & → & →
2 openfocused goal
–injection Hp as → →
2 opendeferred goal
split ; exact Hreg | reflexivity
deferred goal
–cbn in Hs
split ; unfold registered ; rewrite Hreg ; discriminate |
intros reg E _
rewrite Hreg in E
injection E as ←
cbn
split ; lia |
split ; lia |
assert i = 0 ∨ i = 1 ∨ i = 2 ∨ i = 3 ∨ i = 4 ∨ i = 5 as → | → | → | → | → | → by lia ; cbn ; tauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
puts's trusted stream representation and allocation requests.
Hi.v's premise: a safepoint keeps rep and readiness.
stdio_wi survives safepoints, by stdio_stable.
main's frame at its entry.
The Iris instance of hi: puts's contract and stdio_wi.
The expressions of hi's language.
main, owning the literal, is safe and returns 0: it enters its block, copies the literal's pointer, calls puts and returns 0, whatever puts returned.
Explore proof 12 tactics
Initial goal
iIntros Hs
iApply wp_enter ; reflexivity | reflexivity |
iNext
cbn [ b_insts b_jump ]
iApply wp_let ; reflexivity | reflexivity | reflexivity | intros m ; reflexivity |
iNext
iApply wp_puts with Hs ; reflexivity | reflexivity | reflexivity | reflexivity |
iNext
iIntros n _
iApply wp_ret ; reflexivity | reflexivity |
iNext
done
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
hi's body is safe: from a ready runtime, live objects apart, Hi.v's hi_before_call and the world's roots apart from the literal, with any fuel, no labelled run stops with a failure_ending, and a run that returns returns 0. By heap_labelled_safe from main_spec, the ghost heap starting with the literal's pieces.
Explore proof 19 tactics
Initial goal
intros Hr Hd Hrep & Hw & Hv Hapart
apply heap_labelled_safeΣ HB.hi_registryrep requests stdio_wirep HB.hi_genv hi_main m s w list_to_maplit_ps
5 openfocused goal
focused goal
focused goal
focused goal
–exact Hr
4 opendeferred goal
deferred goal
deferred goal
deferred goal
–exact Hd
3 opendeferred goal
deferred goal
deferred goal
–intros l v Hl
3 opendeferred goal
deferred goal
exact lit_valid_agreesm Hv l v elem_of_list_to_map_2_ _ _ Hl
2 opendeferred goal
deferred goal
–split ; exact Hrep |
2 opendeferred goal
split ; exact Hw |
2 opendeferred goal
intros sp a Hin Hs l & v & reg & Hl & _ & E _ & Hb
2 opendeferred goal
apply elem_of_list_to_map_2 in Hl
2 opendeferred goal
rewrite string_ps_id_ _ _ _ l v Hl in E , Hb
2 opendeferred goal
rewrite proj1Hv in E
2 opendeferred goal
injection E as ←
2 opendeferred goal
exact Hapartsp a Hin Hs Hb
deferred goal
–intros HinvG HheapG
rewrite big_sepM_list_to_map ; | exact string_ps_nodup_ _ _ _
iIntros Hl
iApply main_spec
iSplit ; iPureIntro ; exact lit_ok | iExact Hl
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The resources the proof uses: invariants and the ghost heap.
hiΣ has invariants.
Explore proof 2 tactics
hiΣ has the ghost heap of pieces.
Explore proof 2 tactics
The interpreter's runtime
hi over the interpreter's runtime.
Above 2^32, where the interpreter allocates, Hi.v's fixture memory holds no byte and no capability.
Explore proof 5 tactics
Initial goal
intros a Ha
unfold HiChecks.memory , hi_memory
lazy - [ Z.eqb Z.leb Z.ltb Z.add Z.sub Z.mul Z.div Z.modulo Z.pow ]
repeat match goal with|- context [a <? ]⇒let E ≔ fresh in assert E : a <? x = false by apply Z.ltb_ge ; apply Z.le_trans with 2 ^ 32 ; vm_compute ; discriminate | exact Ha ; rewrite E|- context [ ≤? a]⇒destruct x ≤? aend
64 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
all: split ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The interpreter is ready in Hi.v's fixture memory: the libc root at 2048 and the literal at 65552, both below its first allocation at 2^32.
Explore proof 6 tactics
Initial goal
split ; vm_compute ; split ; congruence |
split ; | exact hi_memory_high
intros b reg E
change object_regionb mkRegion2048 2064 Heap Live; lit_reg = Somereg in E
cbn - [ Z.eqb ] in E
destruct 2048 =? b eqn: E1 ; | destruct 65552 =? b eqn: E2 ; | discriminate E ; apply Z.eqb_eq in E1 || apply Z.eqb_eq in E2 ; subst b ; injection E as ← ; split ; vm_compute ; split ; congruence | ; split ; vm_compute ; congruence | discriminate
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The fixture's two live objects are apart.
Explore proof 5 tactics
Initial goal
intros b1 r1 b2 r2 E1 _ E2 _ Hne
change object_regionb1 mkRegion2048 2064 Heap Live; lit_reg = Somer1 in E1
change object_regionb2 mkRegion2048 2064 Heap Live; lit_reg = Somer2 in E2
cbn - [ Z.eqb ] in E1 , E2
destruct 2048 =? b1 eqn: F1 ; | destruct 65552 =? b1 eqn: G1 ; | discriminate E1 ; destruct 2048 =? b2 eqn: F2 ; | destruct 65552 =? b2 eqn: G2 ; | discriminate E2;repeat match goal withH : _ =? _ = true |- _⇒apply Z.eqb_eq in Hend;injection E1 as ←;injection E2 as ←;cbn;lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
hi's body is safe under the interpreter's runtime, from Hi.v's fixture: the libc root at 2048 and the initialized literal, with the fixture's stream representation.
Explore proof 9 tactics
Initial goal
intros fuel
apply InterpHiLogic.hi_logic_safefixture_rep fixture_requests HiChecks.interpreter_stdio_stablefixture_rep hiΣ
4 openfocused goal
focused goal
focused goal
–exact hi_memory_ready
3 opendeferred goal
deferred goal
deferred goal
–exact hi_memory_disjoint
2 opendeferred goal
deferred goal
–exact HiChecks.entry_pre
deferred goal
–intros sp a [ <-| [ ] ] Hs
unfold span_contains in Hs
cbn in Hs
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.