{- |
Wasm32: a 32-bit stack machine for teaching, based on the @i32@ subset of
<https://webassembly.github.io/spec/core/ WebAssembly>. There are no
general-purpose registers: instructions pop operands from a stack and push
results. Control flow is structured (@block@, @loop@, @if@, each closed by
@end@), and functions are called by address.

> _start:
>     i32.const 2        ; 2
>     i32.const 3        ; 3:2
>     i32.add            ; 5
>     halt
-}
module Wrench.Isa.Wasm32 (
    -- * Program
    -- $program

    -- * Instructions
    -- $instructions
    Wasm32Isa (..),
    wasm32Mnemonics,

    -- * Architecture
    -- $architecture

    -- ** Memory
    -- $memory

    -- ** Operand stack
    -- $operands

    -- ** Conditions
    -- $conditions

    -- ** Control stack
    -- $control

    -- ** Functions and locals
    -- $functions

    -- * State views
    -- $views

    -- * Differences from WebAssembly
    -- $differences
) where

import Wrench.Isa.Wasm32.Execute ()
import Wrench.Isa.Wasm32.Instruction (Wasm32Isa (..), wasm32Mnemonics)
import Wrench.Isa.Wasm32.Report ()

-- $program
-- Sections, labels and data directives are shared by all ISAs; see the
-- <https://github.com/ryukzak/wrench/blob/master/docs/README.md Wrench documentation>.
-- Specific to wasm32:
--
-- * Mnemonics are WebAssembly text-format names. A line may hold several
--   instructions. Comments start with @;@.
-- * Execution starts at @_start@.
-- * @i32.const@ takes a 32-bit number or a label. Other immediates are
--   unsigned bytes, @0@ to @255@, checked at translation. A load or store
--   offset is optional (default @0@) and must be a number.
-- * An instruction is one byte, plus one per byte immediate, plus four for
--   @i32.const@.
-- * @.frame@ names a function's locals (see Functions and locals).

-- $instructions
-- An immediate is written @\<name: type\>@. A stack effect
-- @( before -- after )@ has the top rightmost:
-- @i32.sub ( a: i32, b: i32 -- difference: i32 )@ pops @b@, then @a@, and
-- pushes @a - b@. An error stops the simulation with a message.
--
-- * Constants and arithmetic: [@i32.const@](#v:I32Const),
--   [@i32.add@](#v:I32Add), [@i32.sub@](#v:I32Sub), [@i32.mul@](#v:I32Mul),
--   [@i32.div_s@](#v:I32DivS), [@i32.rem_s@](#v:I32RemS)
-- * Bitwise and shifts: [@i32.and@](#v:I32And), [@i32.or@](#v:I32Or),
--   [@i32.xor@](#v:I32Xor), [@i32.shl@](#v:I32Shl),
--   [@i32.shr_s@](#v:I32ShrS), [@i32.shr_u@](#v:I32ShrU)
-- * Comparison: [@i32.eqz@](#v:I32Eqz), [@i32.eq@](#v:I32Eq),
--   [@i32.lt_s@](#v:I32LtS), [@i32.le_s@](#v:I32LeS),
--   [@i32.gt_s@](#v:I32GtS), [@i32.ge_s@](#v:I32GeS),
--   [@i32.lt_u@](#v:I32LtU), [@i32.le_u@](#v:I32LeU),
--   [@i32.gt_u@](#v:I32GtU), [@i32.ge_u@](#v:I32GeU)
-- * Memory: [@i32.load@](#v:I32Load), [@i32.load8_u@](#v:I32Load8U),
--   [@i32.load8_s@](#v:I32Load8S), [@i32.store@](#v:I32Store),
--   [@i32.store8@](#v:I32Store8)
-- * Control: [@block@](#v:Block), [@loop@](#v:Loop), [@if@](#v:If),
--   [@else@](#v:Else), [@end@](#v:End), [@br@](#v:Br),
--   [@br_if@](#v:BrIf), [@unreachable@](#v:Unreachable)
-- * Functions: [@call@](#v:Call), [@return@](#v:Return)
-- * Locals and stack: [@local.get@](#v:LocalGet),
--   [@local.set@](#v:LocalSet), [@local.tee@](#v:LocalTee),
--   [@locals.reserve@](#v:LocalsReserve), [@drop@](#v:Drop),
--   [@select@](#v:Select)
-- * Machine: [@sp.init@](#v:SpInit), [@halt@](#v:Halt)

-- $architecture
-- Unlike the other wrench ISAs, wasm32 has no general-purpose registers, no
-- flags and no branches to labels. Values live on stacks in memory, loops
-- are nested scopes, and each call gets its own frame. Each section builds
-- on the previous one.

-- $memory
-- Code, data, I\/O ports and both stacks share one byte-addressed memory.
-- The stacks start at @stackRoot@ (three quarters into memory, unless
-- @sp.init@ moves it) and grow apart: the operand stack down, the control
-- stack up.
--
-- > memory end   +---------------------+
-- >              |         ...         |
-- > ctrlSp    -> +---------------------+
-- >              | control stack       |  grows up
-- > stackRoot -> +=====================+
-- >              | operand stack       |  grows down
-- > sp        -> +---------------------+
-- >              |                     |
-- >              |         ...         |
-- >              |                     |
-- >              | .text, .data        |
-- > 0            +---------------------+
--
-- Besides memory, the machine keeps only @pc@, an instruction register and
-- a few stack pointers, introduced below. The stacks are plain memory: a
-- program can read and overwrite them, and nothing stops them from running
-- into each other or into code and data.
--
-- Memory is read a word (4 bytes) at a time, from any address. The machine
-- keeps the instructions it read in the instruction register. A fetch takes
-- the instruction at @pc@ from there at no cost; otherwise it reads words
-- starting at @pc@, 1 read for an instruction of up to 4 bytes and 2 for
-- @i32.const@, and keeps that instruction and every following one that ends
-- inside the first word read. Here the first @local.get@ reads the word
-- holding both @local.get@s, and @i32.mul@ the word holding @local.set@ too,
-- so the four instructions cost 2 fetch reads:
--
-- > local.get $acc local.get $n i32.mul
-- > local.set $acc
--
-- Data reads never come from the instruction register, and stores don't
-- change it.

-- $operands
-- Every value is a 32-bit word. @i32.const@ pushes a value; an operation
-- pops its operands and pushes its result. @sp@ is the address of the top
-- value; a push moves it four bytes down, a pop four bytes up. Comments
-- show the stack after each line as the @stack@ view prints it: top first,
-- separated by colons.
--
-- > i32.const 7         ; 7
-- > i32.const 2         ; 2:7
-- > i32.sub             ; 5         7 - 2: the deeper value is the left operand
-- > i32.const 3         ; 3:5
-- > i32.mul             ; 15
--
-- Memory is accessed through the stack too: @i32.load@ pops an address and
-- pushes the word there; @i32.store@ pops a value, then an address. I\/O
-- ports (@memory_mapped_io@ in the configuration) are ordinary addresses:
-- a load from an input port reads the next input, a store to an output
-- port writes one. This copies one value from the input at @128@ to the output at @132@:
--
-- > i32.const 132       ; 132
-- > i32.const 128       ; 128:132
-- > i32.load            ; x:132
-- > i32.store           ;
--
-- A push writes its value to memory, and a pop reads it back: one access
-- each. The machine also keeps copies of the last two values pushed in
-- two /top-of-stack registers/, with the address of each one's slot, and
-- popping one of them reads nothing. So most operations pay only for
-- their fetch and their result: @i32.add@ right after two pushes reads
-- nothing but its fetch and writes only the sum. A register lets go of its
-- value when it is popped, when a third push needs the register, or when
-- anything writes to its slot, so memory always holds the whole stack and
-- the registers never disagree with it. A slot at an I\/O port is never
-- held, since reading the port gives the next input instead. The
-- registers start empty and are shown by the @stack:tos-regs@ view.

-- $conditions
-- A comparison pushes @1@ (true) or @0@ (false), and @if@ pops it. If it is
-- non-zero, execution enters the body, and reaching @else@ jumps past the
-- matching @end@. If it is zero, execution jumps past the matching @else@,
-- or past @end@ if there is none.
--
-- This writes @-1@ if @x@ is negative, @1@ otherwise:
--
-- > i32.const 132                 ; 132
-- > i32.const 128 i32.load        ; x:132
-- > i32.const 0 i32.lt_s          ; (x<0):132
-- > if                            ; 132
-- >     i32.const -1              ; -1:132
-- > else
-- >     i32.const 1               ; 1:132
-- > end
-- > i32.store                     ;
--
-- What either part pushes stays on the stack after @end@. Nothing checks
-- that both parts push the same number of values.
--
-- There is no table of @end@ addresses. To skip, @if@ or @else@ reads the
-- following instructions one by one, tracking nested @block@, @loop@ and
-- @if@, until it finds its own @else@ or @end@. Each instruction it reads
-- is fetched like any other, so each path pays for the part it skips. In
-- the example, @if@ comes in the same word as @i32.lt_s@, so its fetch is
-- free, and the flag it pops is still in a top-of-stack register. When @x@
-- is negative @if@ costs nothing and @else@ 4 (fetch, 2 for the five-byte
-- @i32.const 1@, @end@); otherwise @if@ costs 3 (2 for @i32.const -1@,
-- @else@), as the @mem:accesses@ view shows. An @if@'s @end@ does
-- nothing; a missing @end@ is noticed only when a skip looks for it.
--
-- The machine remembers its last four scans in the /scan cache/: where
-- each scan started and where it ended. When the same @if@ or @else@ skips
-- again while its entry is still there, it continues at the remembered
-- address and reads nothing: in the example, a second negative @x@ costs
-- 1 access for the @else@ (its fetch), and a second positive one nothing
-- for the @if@. A hit moves its entry to the front, and a new scan pushes
-- out the entry used longest ago, so a loop whose body skips at more than
-- four places can lose an entry before it comes round again. The cache is
-- part of the machine, not of memory, starts empty, and is shown by the
-- @cache:scan@ view.

-- $control
-- @if@ only skips forward, and a branch cannot name a label. To repeat
-- code, wrap it in a /scope/ and branch to the scope. Scopes nest, each
-- closed by its own @end@:
--
-- * @block ... end@ -- a branch to a block /breaks/ out: execution
--   continues after its @end@.
-- * @loop ... end@ -- a branch to a loop /continues/ it: execution returns
--   to the start of its body. Without a branch the body runs once.
--
-- Open scopes live on the /control stack/. @block@ or @loop@ pushes an
-- eight-byte record with the addresses a branch needs, and its @end@ pops
-- it. @ctrlSp@ points just past the top record. To fill the record,
-- @block@ and @loop@ search for their @end@ the way @if@ skips, through the
-- same scan cache, so entering a scope again soon costs only its fetch and
-- the record.
--
-- @br n@ jumps to the scope @n@ records down (@0@ is the innermost) and
-- pops the records of the scopes it leaves; @br_if n@ does the same if the
-- value it pops is non-zero. @if@ pushes no record, so it is not counted
-- and cannot be a target. Branches leave the operand stack unchanged.
--
-- A taken branch reads its scope's record, 2 accesses, to learn where to
-- go. The machine remembers its last four taken branches in the /branch
-- cache/: where each branch was, which record it read, and where it went.
-- When the same branch is taken again with the same record at the same
-- place on the control stack, it goes to the remembered address without
-- reading the record: in the example below, @br 0@ costs 3 accesses in the
-- first round and only its fetch after that. A write that changes a
-- remembered record makes the machine forget the branches that read it, so
-- a remembered branch always goes where reading the record would. Like the
-- scan cache, the branch cache is part of the machine, starts empty, and
-- is shown by the @cache:branch@ view.
--
-- This writes @n@, @n - 1@, ..., @1@, with @n@ a word in @.data@:
--
-- > block                                 ; control stack: block
-- >     loop                              ; control stack: loop:block
-- >         i32.const n i32.load
-- >         i32.eqz
-- >         br_if 1                       ; n = 0 -> leave the block
-- >         i32.const 132
-- >         i32.const n i32.load
-- >         i32.store                     ; write n
-- >         i32.const n
-- >         i32.const n i32.load
-- >         i32.const 1 i32.sub
-- >         i32.store                     ; n -= 1
-- >         br 0                          ; back to the loop head
-- >     end
-- > end
--
-- Here @block@ costs 21 accesses (19 reads to fetch it and the instructions
-- up to its @end@, two record words), and @loop@ the same. A missing @end@
-- is reported when its scope runs.
--
-- <https://github.com/ryukzak/wrench/blob/master/example/wasm32/factorial.s example/wasm32/factorial.s>
-- is a complete program with a loop.

-- $functions
-- A function is a label; its address is an ordinary value:
--
-- > i32.const 10          ; 10
-- > i32.const fib         ; fib:10
-- > call 1, 1             ; fib(10)     one parameter, one result
--
-- In <https://github.com/ryukzak/wrench/blob/master/docs/f32a.md f32a> a
-- call only saves a return address and the callee shares the caller's data
-- stack. Here @call p, r@ pops the target and gives the callee its own
-- /frame/:
--
-- 1. The top @p@ values stay in place and become the callee's /locals/
--    @0@ to @p-1@ (local 0 was pushed first). These are its parameters;
--    the caller's frame now ends below them.
--
-- 2. A call record on the control stack saves the caller's frame, the
--    return address and @r@.
--
-- 3. The callee starts at the target with an empty operand stack.
--
-- A frame holds its locals, then its operands. While @_start@ runs a
-- function with two parameters and one more local:
--
-- > ctrlSp    -> +---------------------+
-- >              | call record         |  caller's frame, return address, r
-- > stackRoot -> +=====================+
-- >              | local 0, 1, ...     |  _start's frame
-- >              | operands            |
-- > frameBase -> | local 0  (param)    |  callee's frame
-- >              | local 1  (param)    |
-- >              | local 2             |
-- >              | operands            |
-- > sp        -> +---------------------+
--
-- @frameBase@ is the address of local 0, @localCount@ the number of
-- locals. @local.get i@ pushes local @i@, @local.set i@ pops into it, and
-- @local.tee i@ stores the top value without popping it. @locals.reserve n@
-- adds @n@ locals after the existing ones. They are just the next @n@
-- words down the stack, so reserve them before pushing anything; they are
-- not cleared. @_start@ has a frame without parameters and may reserve
-- locals too.
--
-- Local indices are relative to the current @frameBase@, so a function
-- sees only its own locals, and a call, recursive or not, leaves the
-- caller's frame intact. Indices are not checked against @localCount@.
--
-- @.frame@ names locals: parameters in parentheses, then reserved locals.
-- @.frame ($a, $b) $acc@ makes @$a@ and @$b@ locals 0 and 1 (filled by
-- @call 2, r@) and @$acc@ local 2; @.frame () $acc@ has no parameters.
-- Names become indices at translation: @local.get $acc@ is
-- @local.get 2@. @.frame@ emits no code, so the function still needs
-- @locals.reserve@, and nothing checks the names against the counts of
-- @call@ or @locals.reserve@. Names start with @$@, last until the next
-- label or the end of the section, and mix freely with indices. A
-- malformed @.frame@ or a repeated name is a translation error.
--
-- @return@ keeps the top @r@ values and discards the rest of the frame
-- (parameters, locals, leftover operands), the call record and any scope
-- still open. The results replace the parameters on the caller's stack,
-- and the caller continues after @call@. @return@ outside a function is
-- an error, and @br@ cannot leave a function.
--
-- A factorial with @n@ as its parameter and the product in a reserved
-- local:
--
-- > factorial:
-- >     .frame ($n) $acc                  ; locals 0, 1
-- >     locals.reserve 1                  ; $acc
-- >     i32.const 1 local.set $acc
-- >     block
-- >         loop
-- >             local.get $n i32.const 1 i32.le_s
-- >             br_if 1                   ; n <= 1 -> leave the block
-- >             local.get $acc local.get $n i32.mul
-- >             local.set $acc            ; acc *= n
-- >             local.get $n i32.const 1 i32.sub
-- >             local.set $n              ; n -= 1
-- >             br 0                      ; back to the loop head
-- >         end
-- >     end
-- >     local.get $acc
-- >     return
--
-- Since the target is a value, calling a computed address (from a function
-- table, say) uses the same instruction.
--
-- <https://github.com/ryukzak/wrench/blob/master/example/wasm32/factorial-recursive.s example/wasm32/factorial-recursive.s>
-- computes the factorial recursively, with @if@ and @return@.

-- $views
-- Besides the common views (@pc@, @mem:dump@, @io@), wasm32 has these, each
-- with @:dec@ (default) or @:hex@:
--
-- [@stack@] The current frame's operands, top first, e.g. @14:14@.
-- [@locals@] The current frame's locals, local 0 first. There is no
--   @localCount@ view; this shows that many words.
-- [@sp@, @frame-base@, @ctrl-sp@, @stack-root@] The pointers.
-- [@cache:scan@] The scan cache, most recently used first, each entry as
--   @start->end@, e.g. @0x02e->0x044, 0x011->0x070@.
-- [@cache:branch@] The branch cache, most recently used first, each entry
--   as @from->to@, e.g. @0x0e->0x36, 0x32->0x06@.
-- [@stack:layout@] Every frame, oldest first: locals, control records,
--   operands. @stack:layout:hex:2@ shows only the last two frames.
-- [@stack:dump@] Memory from @sp@ to the end, by address. Each word
--   appears once, with every frame it belongs to; a frame's locals are
--   grouped, control records decoded, everything else (such as memory
--   above @ctrl-sp@) raw. @stack:dump:hex:2@ also limits it to two frames.
-- [@stack:tos-regs@] The top-of-stack registers, the last pushed first,
--   each as @slot=value@, e.g. @0xb8=0x00000003, 0xbc=0x00000002@.
--
-- @{stack:layout:hex}@ at the @halt@ of
-- <https://github.com/ryukzak/wrench/blob/master/example/wasm32/frames.s example/wasm32/frames.s>:
-- @_start@ called @foo@ with two arguments, and @foo@, inside a @block@,
-- called @bar@ with one:
--
-- > #0 _start (pc=0x44)
-- >   mem[0x7c..0x7f]: (operands)
-- >     0x7c..0x7f: 0x0000000a (0)
-- > #1 foo (pc=0x15)
-- >   mem[0x70..0x7b]: locals
-- >     0x78..0x7b: 0x0000000b (0)
-- >     0x74..0x77: 0x0000000c (1)
-- >     0x70..0x73: 0x00000001 (2)
-- >   mem[0x80..0x87]: CallScope
-- >     { csCallerFrameBase = 0x7c
-- >     , csCallerLocalCount = 0
-- >     , csReturnPc = 0x44
-- >     , csResultCount = 1 }
-- >   mem[0x88..0x8f]: BlockScope { csEnd = 0x16 }
-- >   (operands): empty, base=0x70
-- > #2 bar (pc=0x25, live)
-- >   mem[0x6c..0x6f]: locals
-- >     0x6c..0x6f: 0x00000001 (0) [frameBase]
-- >   mem[0x90..0x97]: CallScope
-- >     { csCallerFrameBase = 0x78
-- >     , csCallerLocalCount = 3
-- >     , csReturnPc = 0x15
-- >     , csResultCount = 1 }
-- >   mem[0x64..0x6b]: (operands)
-- >     0x68..0x6b: 0x0000000e (0)
-- >     0x64..0x67: 0x0000000e (1) [sp]

-- $differences
-- * Only @i32@. Missing: @i32.ne@, @i32.div_u@, @i32.rem_u@, rotations,
--   @clz@\/@ctz@\/@popcnt@, 16-bit loads and stores, @br_table@, @nop@,
--   globals, @memory.size@\/@memory.grow@.
-- * No modules, function declarations or types: a function is a label, and
--   @call@ takes its target from the stack (like @call_indirect@) and its
--   parameter and result counts from the instruction.
-- * Locals are added at run time by @locals.reserve@ and named by
--   @.frame ($n) $acc@ instead of @(param $n i32)@ and @(local $acc i32)@.
-- * Scopes have no result types, @if@ is not a branch target, and branches
--   neither unwind nor check the operand stack.
-- * The stacks live in ordinary memory, readable and writable by the
--   program; @sp.init@ places them.
-- * A program ends with @halt@.