Length-prefix recursive types in the type section

Open
#732 0 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 4 days

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
35/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Active
Tech stack
wasm
Domain
compilers

Research direction

Start by reviewing the recursive type grammar described in the issue and wasm-tools pull request #2686, which provides context on parser stack-overflow handling. Determine whether a length-prefixed encoding is appropriate for the component and instance type sections, and document the proposed 1.0 binary-format change and its compatibility implications.

Written by the indexing model from the issue text.

Description

pre-1.0

Currently the binary format for component and instance types is self-recursive, for example:

type          ::= dt:<deftype>
deftype       ::= ...
                | ct:<componenttype>
componenttype ::= 0x41 cd*:vec(<componentdecl>)
componentdecl ::= ...
                | id:<instancedecl>
instancedecl  ::= ...
                | 0x01 t:<type>

This recursive nature already needs to be handled by validators but the binary format here means that even just component parsers need to be hardened against this sort of binary format. For example in wasm-tools https://github.com/bytecodealliance/wasm-tools/pull/2686 was a bugfix which adds extra logic to the parser to ensure that stack-overflow doesn't happen on the host where parsers are currently written as recursive-descent parsing.

Elsewhere in wasmparser and wasm's binary format this is often a use case for length-prefixed portions of the binary. For example if a component or instance type were prefixed by not only their numeric item length but also the byte size in the type section it would enable parsers to more efficiently model this as a not-recursive case. Parsing a component type would then yield "here's a chunk of bytes that's supposed to be a component" without actually parsing anything. The caller would then have to parse those bytes itself, but this inverts the control flow a bit where the caller/embedder is now in control of recursion instead of that having to happen internally.

I realize though that this is a breaking change to the binary format so not something we can do in the near-term. Otherwise though I was thinking that this might be a good 1.0-style binary tweak to make it a bit easier on parsers.

Dominant language
WebAssembly
Stars
1.4k
Forks
134
Avg merge
3d 19h
Merged PRs (30d)
8

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

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/component-model

All issues in WebAssembly/component-model

Similar issues

More Compilers issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.