From fe30995024c050c6c28ebfc13dae6ed4297e8158 Mon Sep 17 00:00:00 2001 From: Derek Schuff Date: Thu, 19 May 2016 11:25:22 +0200 Subject: Fix BinaryEncoding.md to say that the AST encoding is post-order. (#692) --- BinaryEncoding.md | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'BinaryEncoding.md') diff --git a/BinaryEncoding.md b/BinaryEncoding.md index 3e20f5f..c0eacf0 100644 --- a/BinaryEncoding.md +++ b/BinaryEncoding.md @@ -8,7 +8,7 @@ See the [rationale document](Rationale.md#why-a-binary-encoding) for more detail The encoding is split into three layers: -* **Layer 0** is a simple pre-order encoding of the AST and related data structures. +* **Layer 0** is a simple post-order encoding of the AST and related data structures. The encoding is dense and trivial to interact with, making it suitable for scenarios like JIT, instrumentation tools, and debugging. * **Layer 1** provides structural compression on top of layer 0, exploiting @@ -57,19 +57,19 @@ A single-byte unsigned integer indicating a [value type](AstSemantics.md#types). # Definitions -### Pre-order encoding +### Post-order encoding Refers to an approach for encoding syntax trees, where each node begins with an identifying binary sequence, then followed recursively by any child nodes. * Examples - * Given a simple AST node: `I32Add(left: AstNode, right: AstNode)` - * First write the opcode for `I32Add` (uint8) - * Then recursively write the left and right nodes. + * Given a simple AST node: `i32.add(left: AstNode, right: AstNode)` + * First recursively write the left and right child nodes. + * Then write the opcode for `i32.add` (uint8) - * Given a call AST node: `Call(callee_index: uint32_t, args: AstNode[])` - * First write the opcode of `Call` (uint8) + * Given a call AST node: `call(args: AstNode[], callee_index: varuint32)` + * First recursively write each argument node. * Then write the (variable-length) integer `callee_index` (varuint32) - * Then recursively write each argument node, where arity is determined by looking up `callee_index` in a table of signatures + * Finally write the opcode of `Call` (uint8) # Module structure @@ -299,7 +299,7 @@ count may be greater or less than the actual number of locals. # Function Bodies Function bodies consist of a sequence of local variable declarations followed by a -dense pre-order encoding of an [Abstract Syntax Tree](AstSemantics.md). +dense post-order encoding of an [Abstract Syntax Tree](AstSemantics.md). Each node in the abstract syntax tree corresponds to an operator, such as `i32.add` or `if` or `block`. Operators are encoding by an opcode byte followed by immediate bytes (if any), followed by children nodes (if any). @@ -309,7 +309,7 @@ nodes (if any). | body_size | `varuint32` | size of function body to follow, in bytes | | local_count | `varuint32` | number of local entries | | locals | `local_entry*` | local variables | -| ast | `byte*` | pre-order encoded AST | +| ast | `byte*` | post-order encoded AST | #### Local Entry -- cgit v1.2.3