Skip to content

Conversation

@alexcrichton
Copy link
Member

This commit is an initial implementation of resource types for the component model. The support added in this commit encompasses:

  • wasmparser - parsing and validation of resource types
  • wasmprinter - converting binary to text for resource types
  • wast - parsing the text format for resource types
  • wasm-encoder - writing the binary format for resource types

Other crates such as wit-component and wasm-compose saw a few small changes to continue compiling but do not have support added for resource types. WIT, for example, continues to not support resource types. That's planned to be added in a subsequent commit. This support is intended to be everything necessary for Wasmtime to start working on implementing resource types, and once that's ready I'll circle back to implement WIT support with host/guest/etc generators.

This is a substantial commit. The binary format for resources is pretty minor but the major feature it requires support for is the type-checking in validation. Resources effectively add an ML-module-style type system to the component model with abstract types. This required quite a lot of meticulous and careful plumbing throughout the validator along with a rewritten form of checking subtypes.

This commit in theory implements what should be all or at least a large bulk of what's specified for resources at the binary format layer. Without spec tests for formal spec wording it can't really be said how close to the current documentation it follows, but the intention was to follow it closely. Tests have been attempted to be added here in a number of interesting flavors but this implementation is highly likely to still have holes and/or bugs that break the guarantees of resources.

@alexcrichton
Copy link
Member Author

In terms of tests one thing @elliottt and I wanted to add was fuzzing, but I'm not sure that's going to happen in the near future. The current strategy for components with wasm-smith based fuzzing and with core wasm modules I don't think would lend itself all that well to exercising many interesting cases of the resources implementation here. While still useful to stand up and at least fuzz a bit it probably would end up mostly just stressing validation in general as opposed to specifically resources.

@alexcrichton
Copy link
Member Author

alexcrichton commented Mar 28, 2023

And now as I'm rereading the explainer I'm realizing unimplemented portions are:

  • Labels such as [method]foo.bar
  • Restrictions on outer aliases touch resource types or resource-using-types.
  • Restrictions on more-fine-grained use of type indices and whether or not they're exported or imported.

@alexcrichton
Copy link
Member Author

I'll also note that this implementation intentionally diverges from the currently-written explainer as explained here.

I also opened up WebAssembly/component-model#179 for a difference in this implementation with the explainer which is less so intentional and more so "fell out" of the implementation rules.

(instance $i (instantiate $m (with "a" (core module $i))))
)
"type mismatch for component instantiation argument `a`")
"type mismatch in import `::`")
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is this because of (import "" "" (func))?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Indeed yeah, the error message is a bit more descriptive here but this was the substring I figured would be worth matching here. I tried to add some more tests to assert various other parts of the error message too.

@alexcrichton alexcrichton force-pushed the resources branch 2 times, most recently from ed5069f to 206886c Compare April 13, 2023 17:31
@alexcrichton
Copy link
Member Author

As a bit of a status update on this, I've been working recently on this bullet:

Restrictions on more-fine-grained use of type indices and whether or not they're exported or imported.

This motivated by the Explainer.md of the component model explicitly mentioning:

(component
  (import "R1" (type $R1 (sub resource)))
  (type $R2 (resource (rep i32)))
  (export $R2' "R2" (type $R2))
  (func $f1 (result (own $R1)) (canon lift ...))
  (func $f2 (result (own $R2)) (canon lift ...))
  (func $f2' (result (own $R2')) (canon lift ...))
  (export "f1" (func $f1))
  ;; (export "f2" (func $f2)) -- invalid
  (export "f2" (func $f2) (func (result (own $R2'))))
  (export "f2" (func $f2'))
)

Currently as-is with this PR this module is valid (including the "invalid" function) because of the way the "explicit in" checks work. Fixing this has proven to be much more difficult than I previously expected. This sort of logic requires tracking what's exported and what isn't at a per-index level rather than a per-resource-id level. For example in the above "invalid" function it depends on through what path $R2 is referenced rather than simply testing that $R2 was exported somewhere.

I've at this time attempted maybe 3 different methods of implementing this not only for resources but additionally other structural types such as (record) which are intended to be named rather than being allowed to be anonymous. So far all of them have met dead ends and have not produced a final solution. I'm struggling to figure out how best to balance all this and get something implemented to move on.

@alexcrichton
Copy link
Member Author

I should mention another motivation for fixing this is to implement the first bullet:

Labels such as [method]foo.bar

which requires going from (own $foo) to the export/import-name of $foo to validate that the labels are correct. Currently that's not tracked in the validator.

@alexcrichton
Copy link
Member Author

Ok after what feels like it should have been obvious in retrospect I've now pushed up a commit which validates that types are exported (or imported). The implementation is relatively simple at a high level, but I want to doubly-make-aware that the latest commit will invalidate many existing components, namely those created by wit-component which export instances. The old validator accepts them and the new validator will not.

@alexcrichton
Copy link
Member Author

Ok thankfully as I expected implementing [method]foo.bar wasn't so bad. I haven't pushed it up yet though since there are some spec-level clarifications I'd like to sort out first:

@alexcrichton
Copy link
Member Author

I've pushed up a new commit now which is in response to a problem that arose where a WIT-generated component didn't validate. The input WIT was:

interface foo {
  record baz {}

  record bar {
    baz: baz,
  }
}

default world the-world {
  import bar: interface {
    use self.foo.{bar}

    a: func() -> bar
  }
}

which generates a component along the lines of:

(component $C
  (import "foo" (instance $i
    (type $baz' (record))
    (export $baz "baz" (type (eq $baz')))
    (type $bar' (record (field "baz" $baz)))
    (export $bar "bar" (type (eq $bar')))
  ))
  (alias export $i "bar" (type $bar))
  (import "bar" (instance
    (alias outer $C $bar (type $bar'))
    (export $bar "bar" (type (eq $bar')))
    (export $f "a" (func (result $bar)))
  ))
)

the previous version of this PR, however, said the "bar" import was invalid because the type $bar referred to an unexported type, in the context of the instance type defined for "bar". That's true, but its something that should be explicitly allowed since the instance is only ever used in a context where the types are all exported.

To fix this I disabled validation of instance types entirely with respect to whether types are named/exported/etc. This seemed like the easiest way to fix the problem but I'll need to double-check with Luke to make sure that this is ok behavior since it seems like a bit of a big hammer.

@alexcrichton
Copy link
Member Author

More updates! Digging into #986 led me to running the roundtrip-wit fuzzer on this PR, and it uncovered a few more issues. One was that types are now substituted during instantiation in addition to resource ids. This is exhibited by a new test added which previously didn't validate.

Otherwise some various miscellaenous fixes and such were applied to wit-component to ensure that all shapes of WIT documents generate valid components with respect to naming and such.

Copy link
Member

@peterhuene peterhuene left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Really fantastic work here and I'm glad to see the replacement for the original subtype validation implementation, both out of necessity given the complexity of checking resource types and that the original implementation needed some (shall we say...)TLC.

I relied heavily on reading through the various long-form comments (thanks for adding them!), so most of the feedback here is just nits on spotted typos while trying to make sense of the changes.

Copy link

@lukewagner lukewagner left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Just looking at resources.wast and type-export-restrictions.wast: looks great, nice job capturing some interesting cases! I can't spot any tests that look wrong; only a few nits/ideas.

alexcrichton and others added 9 commits April 25, 2023 07:29
This commit is an initial implementation of resource types for the
component model. The support added in this commit encompasses:

* `wasmparser` - parsing and validation of resource types
* `wasmprinter` - converting binary to text for resource types
* `wast` - parsing the text format for resource types
* `wasm-encoder` - writing the binary format for resource types

Other crates such as `wit-component` and `wasm-compose` saw a few small
changes to continue compiling but do not have support added for resource
types. WIT, for example, continues to not support resource types. That's
planned to be added in a subsequent commit. This support is intended to
be everything necessary for Wasmtime to start working on implementing
resource types, and once that's ready I'll circle back to implement WIT
support with host/guest/etc generators.

This is a substantial commit. The binary format for resources is pretty
minor but the major feature it requires support for is the type-checking
in validation. Resources effectively add an ML-module-style type system
to the component model with abstract types. This required quite a lot of
meticulous and careful plumbing throughout the validator along with a
rewritten form of checking subtypes.

This commit in theory implements what should be all or at least a large
bulk of what's specified for resources at the binary format layer.
Without spec tests for formal spec wording it can't really be said how
close to the current documentation it follows, but the intention was to
follow it closely. Tests have been attempted to be added here in a
number of interesting flavors but this implementation is highly likely
to still have holes and/or bugs that break the guarantees of resources.

Co-authored-by: Trevor Elliott <telliott@fastly.com>
Co-authored-by: Trevor Elliott <telliott@fastly.com>
This commit implements a long-desired feature for wasmparser's
implementation of the component model, which is to validate that all
referred-to-types in imports and exports are all themselves named via
imports or exports. This design took a surprising amount of
back-and-forth to settle on something which felt reasonable enough to
land, but the general idea landed on in this commit is relatively
simple:

* The validator's component state now maintains a set of
  exported/imported types.
* When exporting/importing an item, all referred-to types must be
  present in these sets.
* When exporting/importing a type, it's added to these sets.
* When exporting/importing an instance, that recursively is reached into
  to additionally add to these sets.

A minor optimization is that when validating that all names are in the
appropriate set it only has to travel one layer deep in the type
hierarchy since if the one-layer-deep version is "in the set" then it's
already previously validated that everything else is in the set.

The validation predicate here is done with sets and type traversal so
it's probably no the fastest thing in the world, but after all the
back-and-forth about how to implement this I think this is a reasonable
place to start and continue to iterate on the future as necessary.

It's important to note that while this does not alter the binary format
this does change the validation algorithm meaning previously valid
components may no longer be valid. For example the old output of
`wit-component` is no longer considered valid for exported instances.
Instead the output has been updated here to ensure the generated
components conform to the new shape expected by wasmparser.

The other affected crates in this commit are:

* `wit-component` - construction of exported instances is updated so the
  imports in to the shim-component generated are no longer aliased from
  the outer context but redefined in the shim's context. This bloats
  components a bit but the type information additionally shouldn't be
  that intensive.

* `wasm-smith` - the test for generated components has been disabled.
  This would need an update to filter what can be used in exports, but
  for now `wasm-smith` has fallen far enough behind the current state of
  components it seemed more prudent to simply disable it and get back to
  it later.
This commit is an initial pass at implementing methods, constructors,
and static methods on resource types. These introduce names of the
form:

* `[method]foo.bar`
* `[constructor]foo`
* `[static]foo.baz`

which all have their own set of validation rules about when the names
can be mentioned and when they can be applied. The current iteration of
validation and design is working through some upstream questions at this
time but otherwise the implementation here was relatively
straightforward and largely changing some base types and then
propagating the change outwards.
Instead only validate them on components and component types. Helps
handle an extra case that needs to work for WIT.
This commit removes the last remaining usages of the `outer alias`
construct with components generated by `wit-component`. These aliases
ran afoul of the new check about exported type names since they
introduced unnamed types to the current context. Instead necessary types
are imported into the component under various names (the specific names
don't matter) and then the type information is reconstructed in the
component.

This additionally revealed a hole in the implementation of name
validation, as exhibited by the new test, where types provided as
imports needed to be substituted in the final instance type of an
instantiation. Previously only resource types were substituted, but now
type imports are additionally substituted to ensure that the final
output type doesn't refer to internal imported types which won't ever be
exported from any other context.
Give them different prefixes to avoid clashes.
This was improperly generating a topological ordering by adding items to
the order first. Instead the item needs to be added afterwards and
short-circuiting can still happen at the beginning but it's no longer
inserted there.
Copy link
Member

@elliottt elliottt left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks great!

Comment on lines +123 to +124
// TODO: make these `SkolemResourceId` and then go fix all the compile
// errors, don't add skolem things into the type area
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Did you want to make this change before merging this, or should this TODO be turned into an issue?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I fiddled with this for a bit but I wasn't able to get it to work out well in terms of a small handful of casts were ideally all that's necessary, so I'll open an issue for this.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hm on second thought this probably isn't worth an issue, but I think it's fine to revisit at a later date if more issues arise. On another attempt to do this it feels like this adds unnecessary verbosity and more conversions, but I could also be getting the types wrong for sure.

alexcrichton and others added 5 commits April 26, 2023 11:31
Co-authored-by: Trevor Elliott <awesomelyawesome@gmail.com>
Instead refer to them as "imported" and "defined" resources
This logic feels better within `add_entity` to me at least
When an instance type is used to declare an export any resources
mentioned internally must be freshened to become unique to ensure that
other uses of the same instance type don't conflict with the original use.
Insertion into this map should never overlap with previous insertions
and would have uncovered the bug fixed in the prior commit, so add
runtime-level assertions that these maps are only appended to.
@alexcrichton alexcrichton merged commit 11cf92c into bytecodealliance:main Apr 27, 2023
@alexcrichton alexcrichton deleted the resources branch April 27, 2023 03:40
Mossaka pushed a commit to Mossaka/wasm-tools-fork that referenced this pull request May 29, 2023
* Initial implementation of resource types

This commit is an initial implementation of resource types for the
component model. The support added in this commit encompasses:

* `wasmparser` - parsing and validation of resource types
* `wasmprinter` - converting binary to text for resource types
* `wast` - parsing the text format for resource types
* `wasm-encoder` - writing the binary format for resource types

Other crates such as `wit-component` and `wasm-compose` saw a few small
changes to continue compiling but do not have support added for resource
types. WIT, for example, continues to not support resource types. That's
planned to be added in a subsequent commit. This support is intended to
be everything necessary for Wasmtime to start working on implementing
resource types, and once that's ready I'll circle back to implement WIT
support with host/guest/etc generators.

This is a substantial commit. The binary format for resources is pretty
minor but the major feature it requires support for is the type-checking
in validation. Resources effectively add an ML-module-style type system
to the component model with abstract types. This required quite a lot of
meticulous and careful plumbing throughout the validator along with a
rewritten form of checking subtypes.

This commit in theory implements what should be all or at least a large
bulk of what's specified for resources at the binary format layer.
Without spec tests for formal spec wording it can't really be said how
close to the current documentation it follows, but the intention was to
follow it closely. Tests have been attempted to be added here in a
number of interesting flavors but this implementation is highly likely
to still have holes and/or bugs that break the guarantees of resources.

Co-authored-by: Trevor Elliott <telliott@fastly.com>

* Implement validating outer aliases for types

* Add suggested tests

Co-authored-by: Trevor Elliott <telliott@fastly.com>

* Implement validation of imported/exported type names

This commit implements a long-desired feature for wasmparser's
implementation of the component model, which is to validate that all
referred-to-types in imports and exports are all themselves named via
imports or exports. This design took a surprising amount of
back-and-forth to settle on something which felt reasonable enough to
land, but the general idea landed on in this commit is relatively
simple:

* The validator's component state now maintains a set of
  exported/imported types.
* When exporting/importing an item, all referred-to types must be
  present in these sets.
* When exporting/importing a type, it's added to these sets.
* When exporting/importing an instance, that recursively is reached into
  to additionally add to these sets.

A minor optimization is that when validating that all names are in the
appropriate set it only has to travel one layer deep in the type
hierarchy since if the one-layer-deep version is "in the set" then it's
already previously validated that everything else is in the set.

The validation predicate here is done with sets and type traversal so
it's probably no the fastest thing in the world, but after all the
back-and-forth about how to implement this I think this is a reasonable
place to start and continue to iterate on the future as necessary.

It's important to note that while this does not alter the binary format
this does change the validation algorithm meaning previously valid
components may no longer be valid. For example the old output of
`wit-component` is no longer considered valid for exported instances.
Instead the output has been updated here to ensure the generated
components conform to the new shape expected by wasmparser.

The other affected crates in this commit are:

* `wit-component` - construction of exported instances is updated so the
  imports in to the shim-component generated are no longer aliased from
  the outer context but redefined in the shim's context. This bloats
  components a bit but the type information additionally shouldn't be
  that intensive.

* `wasm-smith` - the test for generated components has been disabled.
  This would need an update to filter what can be used in exports, but
  for now `wasm-smith` has fallen far enough behind the current state of
  components it seemed more prudent to simply disable it and get back to
  it later.

* Initial implementation of kebab names for resources

This commit is an initial pass at implementing methods, constructors,
and static methods on resource types. These introduce names of the
form:

* `[method]foo.bar`
* `[constructor]foo`
* `[static]foo.baz`

which all have their own set of validation rules about when the names
can be mentioned and when they can be applied. The current iteration of
validation and design is working through some upstream questions at this
time but otherwise the implementation here was relatively
straightforward and largely changing some base types and then
propagating the change outwards.

* Fix tests

* Test some kebab-case behavior

* Don't validate name export restrictions on instances

Instead only validate them on components and component types. Helps
handle an extra case that needs to work for WIT.

* Remove outer aliases from `wit-component`

This commit removes the last remaining usages of the `outer alias`
construct with components generated by `wit-component`. These aliases
ran afoul of the new check about exported type names since they
introduced unnamed types to the current context. Instead necessary types
are imported into the component under various names (the specific names
don't matter) and then the type information is reconstructed in the
component.

This additionally revealed a hole in the implementation of name
validation, as exhibited by the new test, where types provided as
imports needed to be substituted in the final instance type of an
instantiation. Previously only resource types were substituted, but now
type imports are additionally substituted to ensure that the final
output type doesn't refer to internal imported types which won't ever be
exported from any other context.

* Fix function/type import name conflict

Give them different prefixes to avoid clashes.

* Fix topological order of `LiveTypes`

This was improperly generating a topological ordering by adding items to
the order first. Instead the item needs to be added afterwards and
short-circuiting can still happen at the beginning but it's no longer
inserted there.

* Fix typos

* Update some tests with review comments

* Validate imported/exported entity types as well

* Update crates/wasmparser/src/validator/types.rs

Co-authored-by: Trevor Elliott <awesomelyawesome@gmail.com>

* Rename universals/existentials

Instead refer to them as "imported" and "defined" resources

* Move some resource handling out of `check_type_ref`

This logic feels better within `add_entity` to me at least

* Fix freshening resource types when instances are exported

When an instance type is used to declare an export any resources
mentioned internally must be freshened to become unique to ensure that
other uses of the same instance type don't conflict with the original use.

* Assert defined/imported resources are always unique

Insertion into this map should never overlap with previous insertions
and would have uncovered the bug fixed in the prior commit, so add
runtime-level assertions that these maps are only appended to.

* Add issues for TODOs

---------

Co-authored-by: Trevor Elliott <telliott@fastly.com>
Co-authored-by: Trevor Elliott <awesomelyawesome@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants