Awkward lack of borrowing on variants that contain resources

[cfallin]

Recently in building up a WIT description for a debugger interface in Wasmtime (current draft, implemented and in use in a WIP branch), I have run into a somewhat awkward interaction between variants, resources, and borrowing.

Consider the problem of modeling a Wasm value in WIT: the standard approach in a language with sum types (variants) to build a reflection-like interface (or interpreter implementation or whatever) is to define the "any type" value like

variant value {
  I32(i32),
  I64(i64),
  // ...
}

This works great for primitive types. But now let's introduce values that can refer to more heavyweight things, such as GC object references; these are likely resources, because we need to represent ownership of the GC root.

variant value {
  I32(i32),
  I64(i64),
  GCRef(gc-ref),
  // ...
}

resource gc-ref {
  get-field: func(index: u32) -> value;
  // ...
  clone: func() -> gc-ref; // build `Clone` on top of the resource's linear type.
}

Now consider an API that takes these values, perhaps to make a function call (in the example WIT above, see inject-call):

resource funcref {
  call: func(args: list<value>);
}

This seems like a reasonable-enough model until one realizes: a variant containing any resources is linear-typed (cannot be cloned). So one is left with a few different options to make a usable API:

• Define a "clone" ad-hoc function for value;
• Define a "clone" helper in userspace, destructure the variant, call the ad-hoc "clone" for each resource-owning arm;
• Avoid use of variants and build ad-hoc resources with kind: func() -> kind and unwrap_i32 / unwrap_i64 / ... methods;
• Somehow "borrow" the values for the duration of the call.

The last option is the natural approach in languages with linear types, like Rust: in Rust, I can define

enum Value {
  I32(i32),
  I64(i64),
  GCRef(Arc<ObjectRoot>), // or whatever
  // ...
}

and pass in &Value to any function.

Unfortunately, in the resource model in the CM, borrowing is intrinsically tied to resources only, and a variant containing a resource cannot be borrowed. Because of this, in the WIT above, the true linear-typed approach ("clone everywhere") became way way too awkward, and because borrowing is not an option, I had to avoid variants entirely. This is awkward from an ergonomics PoV, and is also not great performance-wise: it means that I have a bunch of hostcalls to construct resources that represent (for example) "the constant value I32(42)", and I get to use them exactly once.

Is there a path by which we can consider supporting borrows of variants?

[cfallin]

Additional food for thought: composition of borrowing with lists, options, maps.

Basically the definition of borrowing as a parameter mode ("second-class value") rather than type constructor ("first-class value") is the fundamental PL thing going on here. FWIW, Rust went through a similar evolution where borrowing used to be a parameter mode ("inout"-like thing) and then & was lifted into the type-system proper.

[cfallin]

A little more detail on why cloning with variants is awkward but cloning with resources-as-fake-variants is less so: if I have

variant value {
  // ...
  some-resource(some-resource)
}

then I have to have a function clone-value(v: value) -> tuple<value, value> (take one, return two) because I can't put a method on a variant or borrow it (subject of this issue). On the other hand if I build a "fake variant" with a resource

resource value {
  kind: func() -> value-kind;
  unwrap-some-resource: static func(this: value) -> some-resource;

  clone: func() -> value;
}

the clone method can live on the resource and work exactly like one expects in typical guest-language bindgen'd code.

[lukewagner]

Thanks for filing! I might be misunderstanding your question, but it is legal (and, just testing, implemented) to put borrow<some-resource> handles inside variant cases a la:

interface i {
  resource r;
  variant v {
    one(borrow<r>),
    two(u32)
  }
  foo: func(l: list<v>);
}

Here we're not borrowing (at least at the WIT-level) the variant or list, but we are borrowing all handles contained inside them.

[cfallin]

Yep, that's a good point. The issue is that one also wants the non-borrowing variant for other cases -- for example, to return a Wasm value -- and so one ends up with both variant value and variant borrowed-value, and functions to convert between them.

One also can't actually write a function to return that variant (e.g., a method value.to-borrow) because one cannot return borrows. So one would need to build a helper directly in guest code that destructures, explicitly borrows, puts the variant back together, and then passes that in.

All-in-all it seems it would be worthwhile to think about whether borrows could be hoisted to a first-level concept somehow. One seed of an idea is that lazy value lowering gives value numbers to values in a value table; those look suspiciously like resource handles to resources in a resource table; borrows of any value; discuss?

[cfallin]

One more example that came to mind, in the slightly expanded scope that includes lists too: in a design where I have T and borrowed-T, doing the manual thing to build a list<borrowed-T> from a list<T> is O(n) eager work that creates n new resource handles; it's much more efficient to have a type-system understanding of borrow<list<T>> such that when the underlying list of u32s is copied over, the host directly puts them in the callee's resource table in borrowed mode.

I have only a fairly hazy understanding of the canonical ABI's lowering but (ignoring my further-out lazy lowering handles as borrows thought) I wonder if one could interpret lowering of borrow<T> generically as altering any handle borrowing modes transitively within T but otherwise lowering as before? So then we could have borrows of variants, records, lists, options, ... with the expected semantics. It would not avoid eager copying of the whole list so e.g. borrow<list<u32>> is not a direct analogue to &[u32], but the ownership-passing semantics are right at least...

[lukewagner]

You're right that, at the ABI level, lazy-lowering will have a strong feel of "borrowing" to it b/c we're talking about a (dynamic ref-count-enforced) scope during which you can copy or drop a value you were given. One neat thing about lazy lowering is that, by necessity, it introduces "borrowing" in the return direction: when the callee returns a value, the callee's memory is "lent" to the caller until the caller calls subtask.drop, after which the callee's post-return function will be run at which point the callee knows that it has regained ownership of its memory. But that means we could also relax the rules to allow borrow<R> in result types (trapping if all returned borrowed handles weren't dropped before subtask.drop), addressing the asymmetry you mentioned.

Other than that, though, it seems like owned and borrowed handles are just different types. I suppose we could consider a generic handle<resource-type> type that is "parameterized" by whether its owned or borrowed, so that I could write:

variant v {
  one(handle<r>)
}
foo: func(one: list<v>);
bar: func(two: borrow<list<v>>);

and have this be roughly equivalent to:

variant v {
  one(r)
}
variant borrowed-v {
  one(borrow<r>)
}
foo: func(one: list<v>);
bar: func(two: list<borrowed-v>);

which could be convenient in avoiding duplication. I guess I'd be interested to see if more use cases for this pop up to help prioritize it accordingly since I expect we could always add it later without changing of the meaning of things as they currently stand.

[cfallin]

Sure, "just different types" is a valid outcome of the discussion. But I think there's a little bit of danger in falling back to that too easily: it's true in the same sense that monomorphized template instantiations in C++ are "just different types", or T and &T in Rust, or anything else. Building a little more structure into things helps us avoid repetitive and error-prone boilerplate, which is what makes this worth considering. As-is, the use-case linked above (which is real and will land in Wasmtime!) cannot use WIT variants because of this limitation.

variant v {
  one(handle<r>)
}
foo: func(one: list<v>);
bar: func(two: borrow<list<v>>);

I think this is probably the most promising direction, except (as proposed above) if we have just one(r), we can define the lowering of borrow<list<v>> to lower the inner r as a borrow but the lowering of list<v> to lower the inner r as an owned handle. In other words, lowering of any given type is "in borrowed context" or "in owned context", borrow<T> lowers T "in borrowed context", and primitives are lowered the same in borrowed/owned, records and variants pass through context, and resource handles lower with the given borrowing mode. (In other words, we don't need the handle modifier, I think.) Thoughts?

[lukewagner]

Cool; I think we're agreeing on the abstract shape of this potential solution, and maybe there's just a syntactic difference in how we're thinking about it.

FWIW, I'm imagining that, at the WAT level, there's only one (handle <typeidx> <ownership>) type constructor for all handles where ownership is either owned or borrowed and then (own $R) ≡ (handle $R owned) and (borrow $R) ≡ (handle $R borrowed) as abbreviations. And then in WIT if you say r, that's (own $r), just like it is today, but if you write handle<R>, that's (handle $r $ownership) for some $ownership parameter. And iiuc, you're saying that we could also reconsider r to mean (handle $r $ownership), which is a fair point and worth discussing.

Separately, there's a tricky question of what v looks like as a standalone type definition (that can be used in both owned and borrowed contexts). It seems like we'd somehow need to introduce a way to bind $ownership as a parameter that can be used inside the definition of v and then applied to owned|borrowed by uses of v.

For reference, we do something analogous for interfaces where use is effectively a parameter that can be bound differently in different contexts. E.g., in:

interface i {
  use j.{r};
  foo: func(r: r);
}

we take the instance type that represents i and wrap it with a component type that imports j.{r} so that r becomes a parameter that can be used in the definition of the instance type. (For a worked example, see here.) It seems like we'd need to do likewise for ownership, except that we can't (ab)use component types in the same way b/c ownership isn't really a type.

[cfallin]

Ah, interesting -- I guess I was imagining a more direct syntactic correspondence between WIT and the CM type-system. So r is (own r) (as today?); and borrow<T> is (borrow $lower_type(T)) where $lower_type is a meta-function defining this mapping. Maybe we call (own r) (handle r) for reasons that will become clear below.

That means that borrow<r> is (borrow (handle $R)), borrow<list<r>> is (borrow (list (handle $R))), and borrow<variant> is (borrow $Variant).

Then the canonical ABI defines how we lower with a mapping from type to lowered format that also takes "context" as an argument. So $canonical_abi_lowering(r, mode=owned) lowers r to a u32 pointing to an owned handle in the resource table, but $canonical_abi_lowering(r, mode=borrowed) lowers r to a borrowed handle in the table; and $canonical_abi_lowering(list<T>, mode) lowers elements with $canonical_abi_lowering(T, mode), in other words the "borrowed" context around list<r> passes down to how we lower r.

Does that seem workable? The basic principle I'm going for is to not create bifurcated notions of borrowing at WIT and component level, but have them exactly correspond; and to make this as general and as composable as possible.

[alexcrichton]

I've been trying to follow/skim this, but I haven't ingested it all fully necessarily, so forgive me if this is a repeat of something or already been discussed:

FWIW, Rust went through a similar evolution where borrowing used to be a parameter mode ("inout"-like thing) and then & was lifted into the type-system proper.

This, and other comments here, I'm not sure are quite accurate. The issues you're describing of whether to use a borrow<T> or own<T> within a variant is the exact same problem that Rust has of using a T or &'a T in an enum. Rust is slightly better off with generics where there's just one Option<T> for example, but for a concrete type like wasm-value the design constraints WIT has are, at least in my opinion, the exact same as those in Rust.

Basically I don't think that this is a novel problem or a indicator of something wrong in WIT, I'm under the impression that it's the exact same problem in Rust or at least the exact same problem can arise.

I would personally not be in favor of borrow<list<T>> which would auto-borrow all resources within T. From a bindings generation perspective that would be quite difficult to bind within Rust, C, or any other static language. It would mean, for example, that a record with a resource in it is unknown whether that resource should be an own<T> or a borrow<T>. Generators would have to generate two types for all WIT types that contain resources and then choose the right one.

I don't mean to say that the original problem is solved via some other means of course. WIT today would force some usage of wasm-value and borrow-wasm-value as two different type definitions. In Rust, however, this is also the case. I would imagine that the duplication is undesirable here and the clone-style method would be the bridge to using a variant.

[cfallin]

This, and other comments here, I'm not sure are quite accurate.

I'm referring to this post about early Rust history by Graydon Hoare and others I've read describing "The second-class & types in early Rust" and "I wanted & to be a "second-class" parameter-passing mode" -- that's the analogy to WIT borrow types today. I didn't use the language pre-lifetimes so I don't know for sure but in any case "references as a special mode" is a fairly common PL thing going back to e.g. Pascal's out-parameters, or upvalues in Tcl, etc.

Basically I don't think that this is a novel problem or a indicator of something wrong in WIT, I'm under the impression that it's the exact same problem in Rust or at least the exact same problem can arise.

I don't think WIT has the same expressive power: Rust's Option<T> can take T = &U, or in other words, the universe of types includes & as a type-constructor that can modify any other type (i.e., first-class). That's not the case for WIT types: borrow can modify handles in particular, not any other type.

So concretely, I can have the enum Value in my original comment with an owned value (e.g. an Arc) inside, in Rust, and I can pass a &Value as a parameter with no issues. In WIT, I can have a variant that includes a resource in one arm, but I cannot pass a borrow of that variant (no such concept exists). Instead I have to define a completely new variant, and manually convert, and linear types make that manual conversion extremely tedious (static funcs that take one thing and return two, etc).

I don't mean to say that the original problem is solved via some other means of course. WIT today would force some usage of wasm-value and borrow-wasm-value as two different type definitions. In Rust, however, this is also the case.

I don't think it is! In Rust, I can do the equivalent of passing &wasm-value; I don't have to define the enum twice and convert between them.

I may be missing some way to avoid that, but right now it seems like a clear expressivity hole in the language. It's fine if the resolution is "we don't want to pay the complexity tax", but we should acknowledge that it's a limitation.

[cfallin]

(And to head off confusion: above in your comment and mine we're both switching between containers/variants-of-borrows and borrows-of-containers/variants. The former is supported and fine; it's the latter (&MyEnum) that WIT doesn't have. The "auto-borrowification" of the inner bit is the moral equivalent of matching on a &MyEnum and getting &-borrows of fields that are owned types in the enum's actual definition.)

[fitzgen]

Unless T and &T always have the same representation for all types T, then the "auto-borrowification" is an $O(n)$ operation for e.g. list<T>-to-list<&T>, so I don't think auto-borrowification is reasonable.

[fitzgen]

But being able to pass borrow<list<T>> to functions and not have that drop any resources or deallocate any memory associated with the inner T does seem reasonable to me, and also seems like it would resolve the OP papercut.

[cfallin]

The lowering is already O(n), right?

What this is saying is that (borrow (list (handle $R))) is lowered just like (list (handle $R)), i.e., N pushes into the callee's resource table, except we set the handle-mode to borrowed rather than owned.