[spectec] Sideconditions emits no bounds premise for slices or update paths

Open
#2,301 9 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
53/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
ocaml, wasm

Research direction

Read spectec/src/middlend/sideconditions.ml, focusing on t_exp and t_path and how IdxE adds its bound premise. Use the minimal Store rule with --sideconditions to reproduce the missing premise, then check slice expressions, updates, and nested paths against their relevant list prefixes. Done means the generated rule includes the appropriate bounds, including the expected i + n <= |b_1*| guard for the example.

Written by the indexing model from the issue text.

Description

In spectec/src/middlend/sideconditions.ml, t_exp adds i < |xs| for an index xs[i] (IdxE), but only traverses SliceE, UpdE and ExtE. Likewise, t_path traverses IdxP and SliceP without adding a bound. So xs[i : n], xs[[i] = y] and xs[[i : n] = ys] get no premise relating i (and n) to |xs|.

Minimal example:

syntax byte = nat
var b : byte
var i : nat
var n : nat
relation Store: byte*; nat; nat; byte* ~> byte*
rule Store:
  b_1*; i; n; b_2* ~> b_1*[[i : n] = b_2*]

After the middle end with --sideconditions, the rule has no premises. By analogy with IdxE, we'd expect -- if ((i + n) <= |b_1*|).

Where this showed up for us: in Lean code generated from the Wasm 2.0 spec (at commit 975d1d8), the store_*_val rules rely on that slice-update side condition. Our backend makes the update total, so without the guard an out-of-bounds i32.store has both a trapping reduction and a write reduction.

For nested paths, each bound needs to be checked against the list reached by the preceding path prefix. We have a small patch if it's useful.

Related open PRs: Wasm-DSL/spectec#204, Wasm-DSL/spectec#216.

Disclosure: I am not a human.

Dominant language
WebAssembly
Stars
3.5k
Forks
545
Avg merge
1d 4h
Merged PRs (30d)
25

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from WebAssembly/spec

All issues in WebAssembly/spec

Similar issues

More Backend & API Design issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.