Recursive Types

There was some discussion on recursive types in WebAssembly/interface-types#137.

My takeaway was that recursion would be hard to specify with adapter functions.

With adapters punted to a post-MVP phase , would it be sensible to re-consider allowing recursion?

There were arguments for and against in the linked issue, but I'd like to point out again that having to fall back to resources to represent nested data structures is quite a big limitation and would require falling back to other serialization formats like JSON/msgpack/Protobuf/... quite often to get decent performance.

Adapter functions were extra-extra hard, but, even just talking through the implementation of canonical adapters (especially with the coercive subtyping), I believe that recursive types would make the implementation a lot more complicated. I do actually expect that we'll want recursive types before too long for the reasons you're describing; it's just not yet clear that recursive types are necessary for viability in the MVP sense. That being said, I'm happy to keep this issue open and collect feedback over the course of the proposal's standardization; maybe it ends up needing to be a carefully-considered late addition.

I'd like to point out again that having to fall back to resources to represent nested data structures is quite a big limitation and would require falling back to other serialization formats like JSON/msgpack/Protobuf/... quite often to get decent performance.

It's probably worth mentioning that there's no way to represent trees without recursive types, and trees are pretty much ubiquitous in programming. For example, imagine a DOM or AST.

My fear is that if we release the MVP without a solid plan for dealing with recursive types, it'll become much harder to implement them later on.

You're that these datatypes are ubiquitous, but the two examples you gave sound like examples where we wouldn't want to pass the entire tree as an eagerly-copied value in a function parameter or result. For the DOM we'd probably want to use resource types/handles in the roughly same manner that the browser/JS do, and for an AST, it seems like you'd want various iteration/cursor/streaming/etc schemes, that depended on the data structure and intended operations.

Are there any concerns around Denial of Service with passing recursive types across a boundary? It seems like you could spend a lot of time in the adapter (or even infinite if something malicious happens?) that you'd want to bound in some way.

Great question! Because even though the abstract values produced by lifting a recursive type are acyclic (trees), the hazard is if the lifted core memory somehow encodes a cycle/iloop (which should trap of course; but the question is how that trap is specified to happen and implemented). I suppose one option is for the Canonical ABI to say that recursive-type values are laid out contiguously in linear memory (including lists involved in the recursion), but I can imagine several other alternatives, so this is something that would have to be thought about more.

Another hazard is if the implementation used stack-based recursion to implement the fused lift+lower and stack-overflowed; we'd need to either fix a maximum dept (probably bad idea) or mandate that implementations needed to use iteration (which is more complicated, but seems doable).

The flattened representation of a recursive type also doesn't inherently have a fixed type or size unless the recursion is through a list.

e.g. in this simple tree type, which has a flattened size dependent on the depth of the tree (in Rust terms it's !Sized)

variant node {
   branch(branch-node),
   leaf(i32)
}

record branch-node {
   left: node,
   right: node
}

It seems like the Canonical ABI would need to choose where to insert pointer-indirection to make it flattenable. Either at the top making the whole thing flatten into a pointer into memory or at branch-node's left and right fields allowing more to be flattened.

I've run into this issue of not supporting recursive types and reading through the comments above it is not clear to me if there is a way to work around this. If anyone has some links to examples/documentation where this is explained please let me know.

For example, we have the following type:

  variant value-pattern {                                                       
    null,                                                                       
    %string(string),                                                            
    integer(s64),                                                               
    decimal(float64),                                                           
    boolean(bool),                                                              
    %list(list<value-pattern>),                                              
    octets(list<u8>),                                                           
  }

This above is intended to mimic the following Rust enum:

  pub enum ValuePattern {                                                            
      Null,                                                                          
      String(Arc<str>),                                                              
      Integer(i64),                                                                  
      Decimal(f64),                                                                  
      Boolean(bool),                                                                 
      List(Vec<Arc<ValuePattern>>),                                                  
      Octets(Vec<u8>),                                                               
  }

This is just one example of a number of places in our code base where we have similar constructs.

It would be really nice to have support for recursive types for the MVP. I realize that I don't have a complete picture of the difficulties of implementing this but I want to express our wish to have this supported.

You can't represent your ValuePattern directly in WIT because there are no recursive types. There are workarounds using indices into a list as indirection which I've used for trees, and you can also serialize into bytes or strings, but neither solution is very ergonomic.

Here's an example of the index-indirection pattern:

variant value-item {                                                       
   null,
   %string(string),
   integer(s64),
   decimal(float64),
   boolean(bool),
   %list(list<u32>), // list of indices of values
   octets(list<u8>),
}

type value-tree = list<value-item>;

Additionally, while recursive types are useful for some things, in many cases where you could send a JSON-like recursive value across the component boundary the actual data isn't even recursively typed if modeled concretely and it can be represented using records and lists instead (e.g. it represents a list of customers as opposed to a parse tree). On the other hand, if your structure is very large, you may want to represent it as a resource type (which are arriving pre-MVP) anyway so you aren't copying lots of data between components frequently and instead pass a handle to it around.

So while this is something we need eventually, there are workarounds and alternate options available and it's very complicated & time consuming to implement for reasons like those mentioned in this issue, so it won't be available for quite some time.

@Kylebrown9 Thank you for the explanation and the example! I'll take a shot at implementing it this way.

This issue prevents me from making an ergonomic adapter for dynamodb types. I figure it's 2025 and this issue merits a bump?

variant attribute-value {
    s(string),
    l(list<attribute-value>),
    // [...]
}

This will result in boilerplate, unsafe types, and json-as-abi; the burden of which will be thrust onto my users.

Where is this issue at in terms of priority & workaround state of the art?

Note that I'm only interested in indirected "recursion" which isn't really type recursion. I think structural recursion should always be prohibited.

// should never be legal
record a {
  aa: a,
}

// this should be fine
record a {
  aa: list<a>,
}

list's size is not dependent on a - it's structurally separated. This should be permissible without needing to solve record a { aa: a }. This does not necessarily solve tree authors' desires in by-reference languages, but they could at least use list<node>. That would sure beat the separate index list, and it's far simpler than recursive resources for guest implementations...

The current priority is releasing preview 3 which is occupying the time of a lot of the folks who are working on this. Agreed that this feature would be really helpful and significantly improve ergonomics though; the main reason this hasn't been worked on yet is that recursive types are pretty tricky; to see the issues involved, see this recent paper about wasm-gc's recursive types (whose lead we should probably follow).

Can't we manually mark the box to break the recursion like Rust does?

Just like defining an intermediate resource type to break the recursion now.

Both equi-recursive and iso-recursive are too advanced.

@oovm

I agree with @oovm and I think requiring a manual box annotation is 100% the right approach here, and would satisfy most use cases with a minimum of specification effort because the semantics can be expressed straightforwardly in terms of existing concepts. Just specify that any interface which declares any function that mentions a box (whether directly or indirectly through a record or variant) implicitly defines a resource type

resource box<T> {
    constructor(init: T);
    unbox: func() -> T;
}

This approach avoids introducing any new fundamental types and only slightly complicates despecialization logic. There's no need to think deeply about subtyping since it's obviously invariant. It's still necessary to check type equality to determine whether two mentions of a boxed type should produce separate resource types or be merged into one. For example,

variant foo {
    nil,
    cons(tuple<u32, box<bar>>),
}

variant bar {
   empty,
   pair(tuple<u32, box<foo>>),
}

baz: func(arg: foo);
quux: func(arg: bar);

ought to generate just one resource type, not two, because foo and bar are structurally equal.

Navigation Menu

Repository navigation

Recursive Types #56

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Recursive Types #56

Description

Activity

lukewagner commented on Jun 28, 2022

Michael-F-Bryan commented on Oct 26, 2022

lukewagner commented on Oct 28, 2022

esoterra commented on May 9, 2023

lukewagner commented on May 9, 2023

esoterra commented on May 10, 2023

danbev commented on May 22, 2023

esoterra commented on May 22, 2023

danbev commented on May 22, 2023

kvcache commented on Apr 14, 2025

lukewagner commented on Apr 15, 2025

oovm commented on Apr 26, 2025

dfoxfranke commented on Jul 30, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions