rocq/theories/HelloLeaf.v
GNU Hello's leaf functions through the program logic of Logic.v (docs/logic.md, "GNU Hello through the logic", milestone 2).
Four small gnulib helpers of the linked module (hello_module) each make one libc call and return, and each gets a Hoare triple from that call's triple: mbszero from wp_memset (mbszero_spec), memeq from wp_memcmp (memeq_spec), streq from wp_strcmp (streq_spec) and strnlen1 from wp_memchr_string (strnlen1_spec). Callers in the module use them through wp_call_bind, as count_l uses next_l in CountLogic.v.
The triples hold in any genv that links Hello: one whose module is hello_module, whose symbols include the module's own (hello_globals) and none of the libc functions it calls (hello_linked). The registry and the world interpretation are any that hold the contracts the calls name, so the same triples serve the whole program, whose world is Campaign 4's.
Integer arithmetic on an unknown stays folded when a premise is computed (Symbolic.v).
The module's symbols and functions
The symbols laying out hello_module gives, from 65536 on (initial_memory): 115 of them, functions and data.
A genv links Hello: its module is hello_module, each of the module's symbols is where hello_globals puts it, and no libc function the module calls (hello_externals) is a symbol, so each such call is an external_site. Startup may add libc's data symbols, such as program_invocation_name.
The module md defines no function named s (find_fn).
A function md does not define is no function of a genv with module md: find_fn reads only the module.
Explore proof 5 tactics
Initial goal
unfold outside , find_fn
cbn [ ge_module ]
destruct find_direct_ _ ; discriminate |
destruct find_alias_ _ as t | ; cbn ; | reflexivity
destruct find_directt _ ; discriminate | reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The libc function s, one Hello calls, is no function of a genv with Hello's module.
Explore proof 9 tactics
Initial goal
intros Hm Hs
apply outside_find
rewrite Hm
assert H : forallboutsidehello_module hello_externals = true by vm_compute ; reflexivity
rewrite forallb_forall in H
apply existsb_exists in Hs as s′ & Hin & Hs
apply String.eqb_eq in Hs
rewrite <- Hs in Hin
exact Hs Hin
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The function f called with the words xs, at its entry, as call_frame makes it; a direct call to f binds this frame.
Block l of f, or an empty one.
mbszero(p): memset of 8 zero bytes, gnulib's mbstate_t reset.
memeq(p, q, n): memcmp, compared with 0.
streq(p, q): strcmp, compared with 0.
strnlen1(p, n): memchr for the NUL in n bytes; one past it, or n.
xmalloc(n): malloc, and xalloc_die on null.
mbszero's one block.
memeq's one block.
streq's one block.
strnlen1's entry: memchr, then is its result null?
strnlen1 after a hit: one past it.
strnlen1 after no hit: n.
xmalloc's entry: malloc, then is the result null?
xmalloc's return.
mbszero has its block.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
memeq has its block.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
streq has its block.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
strnlen1 has its entry.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
strnlen1 has its hit block.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
strnlen1 has its miss block.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
xmalloc has its entry.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
xmalloc has its return block.
Explore proof 2 tactics
Initial goal
vm_compute
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
mbszero's entry binds its pointer.
Explore proof 1 tactics
Initial goal
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
memeq's entry binds its pointers and length.
Explore proof 1 tactics
Source script
streq's entry binds its pointers.
Explore proof 1 tactics
strnlen1's entry binds its pointer and bound.
Explore proof 1 tactics
xmalloc's entry binds its size.
Explore proof 1 tactics
Initial goal
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Prove a premise that names words: by computation, with the environment's facts.
Prove an address premise: drop the wraps of raw_address and of a flight's sum where arithmetic shows them the identity, then arithmetic.
Hello's leaf functions over any runtime R.
The genv links Hello (hello_linked).
The Iris instance of the registry and wi.
The expressions of the language.
The libc function s that Hello calls is no function of the genv.
Explore proof 2 tactics
Initial goal
apply hello_outside
exact proj1Hlinked
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The libc function s that Hello calls is no symbol of the genv.
Explore proof 1 tactics
Initial goal
apply proj2proj2Hlinked
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
mbszero's triple, from wp_memset: owning the 8 bytes xs and their aux slots cs at the 8-aligned offset o of the live object b, at a multiple of 8, where the fill keeps the world interpretation, the call zeroes them and clears the slots.
Explore proof 13 tactics
Initial goal
intros Hreg Hx Hc Hb8 Ho8 Ho Hend Hwi
iIntros Hl Hx Hcs HΦ
rewrite mbszero_entry
iApply wp_enter ; exact find_z_start | reflexivity |
iNext
cbn [ b_insts b_jump z_start ]
iApply wp_memset_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 0 with Hl Hx Hcs ; exact Hreg | apply linked_outside ; reflexivity | apply linked_unbound ; reflexivity | word_premise | word_premise | rewrite Hx ; word_premise | lia | exact Hb8 | exact Ho8 | exact Ho | rewrite Hx ; exact Hend | rewrite Hc Hx ; reflexivity | rewrite Hx ; exact Hwi |
iNext
iIntros Hl Hx Hcs
rewrite Hx
iApply wp_ret_void
iNext
iApply HΦ with Hl Hx Hcs
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
memeq's triple, from wp_memcmp: owning as many bytes xs and ys of two live objects, through read-write or read-only capabilities, n their count, it returns an int and hands them back.
Explore proof 14 tactics
Initial goal
intros Hreg → Hc Hc′ Hlen Ho Ho′ Hend Hend′ Hn Hx Hy
iIntros Hl Hx Hl′ Hy HΦ
rewrite memeq_entry
iApply wp_enter ; exact find_e_start | reflexivity |
iNext
cbn [ b_insts b_jump e_start ]
iApply wp_memcmp with Hl Hx Hl′ Hy ; exact Hreg | apply linked_outside ; reflexivity | apply linked_unbound ; reflexivity | reflexivity | exact Hc | reflexivity | exact Hc′ | cbn ; rewrite Z.mod_small ; reflexivity | lia | exact Hlen | exact Ho | exact Ho′ | exact Hend | exact Hend′ | exact Hx | exact Hy |
iNext
iIntros bits Hl Hx Hl′ Hy
iApply wp_let ; reflexivity | reflexivity | word_premise | intros m ; word_premise |
iNext
iApply wp_ret ; reflexivity | word_premise |
iNext
iApply HΦ with Hl Hx Hl′ Hy
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
streq's triple, from wp_strcmp: owning the strings at p and q, it returns an int and hands them back.
Explore proof 14 tactics
Initial goal
intros Hreg
iIntros Hs Ht HΦ
rewrite streq_entry
iApply wp_enter ; exact find_q_start | reflexivity |
iNext
cbn [ b_insts b_jump q_start ]
iApply wp_strcmp with Hs Ht ; exact Hreg | apply linked_outside ; reflexivity | apply linked_unbound ; reflexivity | reflexivity | reflexivity |
iNext
iIntros bits Hs Ht
iApply wp_let ; reflexivity | reflexivity | word_premise | intros m ; word_premise |
iNext
iApply wp_ret ; reflexivity | word_premise |
iNext
iApply HΦ with Hs Ht
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
strnlen1's triple on a string, from wp_memchr_string: owning the string at p with contents bytes, a bound n returns one past its NUL when that lies within n bytes, and n otherwise. The bytes after the NUL need not exist.
Proof 66 steps Qed
xmalloc's triple, from wp_malloc: for a size n, where an allocation keeps the world interpretation, it returns the base pointer of a fresh heap object of n bytes, whose pieces it owns. The selected malloc never returns null, so xalloc_die, and the abort it may reach, are never called.
Explore proof 28 tactics
Initial goal
intros Hreg Hn Hwi
iIntros HΦ
rewrite xmalloc_entry
iApply wp_enter ; exact find_x_start | reflexivity |
iNext
cbn [ b_insts b_jump x_start ]
iApply wp_malloc_ _ _ _ _ _ _ _ _ _ _ n ; exact Hreg | apply linked_outside ; reflexivity | apply linked_unbound ; reflexivity | cbn ; rewrite Z.mod_small ; reflexivity | lia | exact Hn | exact Hwi |
iNext
iIntros base Hb Hobj
destruct Hb as Hb0 & Hb16 & Hbend & Hmax
assert Hext : 0 ≤ req_extentheap_req16 n
2 openfocused goal
{unfold req_extent , heap_req
2 opendeferred goal
cbn
2 opendeferred goal
apply Z.mul_nonneg_nonneg ; apply Z.div_pos | ; lia
deferred goal
iApply wp_let ; reflexivity | reflexivity | word_premise | intros m ; word_premise |
iNext
iApply wp_let ; reflexivity | reflexivity | word_premise | intros m ; word_premise |
iNext
iApply wp_branch_ _ _ _ _ _ _ _ _ _ 0 ; word_premise |
iNext
cbn [ Z.eqb edge_label ]
iApply wp_enter ; exact find_x_join | reflexivity |
iNext
cbn [ b_insts b_jump x_join ]
iApply wp_ret ; reflexivity | reflexivity |
iNext
iApply HΦ with [%] Hobj
auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
HelloLeafOn over a Logic instance of its own.