Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/Run.v

Running a function of a module as interp:run/5 does: prepare the module's initial memory, call the function, and take steps until an outcome, choosing each allocation's base as a runtime does.

A run takes its allocations' bases from a Runtime (Runtime.v): DriverR runs with R's choices, and the gates run DriverInterpRuntime (Transport.v), the interpreter's allocator. That is one instance of fresh allocation, not part of the semantics: Semantics.v's step_rel allows any fresh base.

From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Syntax Values Memory Ops Semantics Runtime
Import ListNotations
Open Scope string_scope
Open Scope Z_scope

As data_base/1: the address where the module's items start.

19Definition data_base: Z ≔
65536

As data_cap/3: the capability of data with the linkage lk at base, writable or read-only; a weak declaration or an unknown linkage has none.

24Definition data_caplk : linkage base : Z : optioncap ≔
match lk with
⇒
SomeObjbase
LRo_ | LInit_ _
⇒
SomeRobase

As filc_layout/3: the item it placed after those before it, updating the next address, the globals and the objects. A data object goes at the next address aligned to 16 or its stricter alignment, its size rounded up to 8, with a 16-byte gap after it; a function at the next 16-aligned address, 16 bytes, with the capability fn(Name). A weak declaration (extern(weak)) takes no space and stays undefined; an alias waits for alias_global.

38Definition layoutst : optionZ × listname × ptr × listregion it : item : optionZ × listname × ptr × listregion ≔
let* s ≔ st in
let 'a0, globals, rs ≔ s in
match it with
⇒
Somes
IDatan lk al items
⇒
let align ≔ Z.maxal 16 in
let base ≔ align_upa0 align in
let end_ ≔ base + items_sizeitems + 7 / 8 × 8 in
let* c ≔ data_caplk base in
Someend_ + 16, putn mkPtrbase c globals, mkRegionbase end_ GlobalData Live :: rs
IAlias_ _ _
⇒
Somes
⇒
let base ≔ align_upa0 16 in
Somebase + 16, putfn_namef mkPtrbase Fnfn_namef globals, rs
⇒
let base ≔ align_upa0 16 in
Somebase + 16, putn mkPtrbase Fnn globals, rs

As alias_global/3: an alias's address is its target's, the same pointer.

62Definition alias_globalgs : optionlistname × ptr it : item : optionlistname × ptr ≔
let* globals ≔ gs in
match it with
IAliasn _ t
⇒
let* p ≔ lookupt globals in
Someputn p globals
_
⇒
Someglobals

As filc_item_contents/4: one item of a data object written at the next address, and the address after it. A pointer item writes its symbol's address plus the offset, and the symbol's capability in the aux; a symbol the module does not define is an external one.

75Definition item_contentsglobals : listname × ptr st : optionZ × mem it : data_item : optionZ × mem ≔
let* s ≔ st in
let at_, m ≔ s in
match it with
Symsym off
⇒
negbat_ mod 8 =? 0
→
None
else
let p ≔
match lookupsym globals with
Somep
⇒
p
None
⇒
in
Someat_ + 8, store_auxstore_bytesm at_ 8 ptr_addrp + off mod 2 ^ 64 at_ ptr_capp
Itemw n
⇒
let size ≔ width_bytesw in
Someat_ + size, store_bytesm at_ size n mod 2 ^ 8 × size
Strcs
⇒
Some
at_ + Z.of_natlengthcs
fst
fold_left
λ mi : mem × Z c : Z  ⇒
let m′, i ≔ mi in
store_bytesm′ at_ + i 1 c, i + 1
cs
m, 0
⇒
Someat_ + n, m
⇒
None

As filc_contents/4: a data object's items written in order from its address; other items write nothing.

102Definition contentsglobals : listname × ptr st : optionmem it : item : optionmem ≔
let* m ≔ st in
match it with
⇒
Somem
IDatan _ _ items
⇒
let* p ≔ lookupn globals in
let* r ≔ fold_leftitem_contentsglobals items Someptr_addrp, m in
Somesndr
_
⇒
Somem

The memory with no objects, every byte zero and no stored capability.

116Definition empty_mem: mem ≔
mkMemλ_ ⇒ 0 [ ] λ_ ⇒ CNone

As initial_memory/4 in filc mode: the module md's globals, each name with its pointer, and the memory with every item placed in order from data_base (layout), aliases bound (alias_global), and each data object's contents written (contents).

122Definition initial_memorymd : module : optionlistname × ptr × mem ≔
let* l ≔ fold_leftlayout md Somedata_base, [ ], [ ] in
let '_, globals0, rs ≔ l in
let* globals ≔ fold_leftalias_global md Someglobals0 in
let* m ≔ fold_leftcontentsglobals md SomemkMemm_bytesempty_mem rs m_auxempty_mem in
Someglobals, m

What a run ends with: an outcome, or halted where the interpreter throws or fails, with the step that was stuck.

132Inductive run_result: Type ≔
|Finished
o : outcome
|Halted
why : string

The driver

Running under the runtime R: R's alloc chooses each allocation's base, and R's free is the genv's.

140Module Driver R : Runtime

One step, with the runtime's state beside the configuration. Where R refuses an allocation the run ends with trap(out_of_memory), at whichever allocation it is: a heap object, a named local or a variadic callee's argument snapshot (alloc_res/6, inst_result/5, call_outcome/8).

147Definition run_stepge : genv s : config × R.state : config × R.state + run_result ≔
let c, rt ≔ s in
match stepge c with
Nextc′
⇒
inlc′, rt
⇒
⇒
match R.allocrt q with
Somebase, rt′
⇒
inlkbase, rt′
⇒
inrHaltedwhy

Up to 2^p steps, by halving p, so that the recursion depth is p and the gas a positive. The gas is never the limit in practice: the run's own fuel (blocks entered) ends every run first.

163Fixpoint run_stepsge : genv p : positive s : config × R.state : config × R.state + run_result ≔
match p with
xH
⇒
xOp′
⇒
match run_stepsge p′ s with
inls′
⇒
run_stepsge p′ s′
r
⇒
r
xIp′
⇒
match run_stepge s with
inls1
⇒
match run_stepsge p′ s1 with
inls2
⇒
run_stepsge p′ s2
r
⇒
r
r
⇒
r

As run/5: the run of the function fn of the module md on the words args, entering at most fuel blocks, from the module's initial memory and R's start.

178Definition runmd : module fn : name args : listword fuel : Z : run_result ≔
match initial_memorymd with
None
⇒
Halted"initial memory"
Someglobals, m
⇒
let ge ≔ mkGenvmd globals R.free in
match find_fnge fn with
SomeDefinedf
⇒
match call_framef args with
Somefr
⇒
match run_stepsge 2 ^ 60%positive mkConfigfr [ ] m fuel, R.start with
inrr
⇒
r
inl_
⇒
Halted"driver gas"
None
⇒
Halted"call"
SomeOutsiden
⇒
Halted"outside the core subset"
None
⇒
Halted"no such function"