Resolving transitive dependencies of WIT exports

[alexcrichton]

One of the subtelties of imports and exports in WIT is that they both need to somehow resolve their transitive dependencies. For example this world:

package foo:bar

interface foo {
  type t = u32
}

interface bar {
  use foo.{t}
}

world w {
    import bar
}

the bar import transitively depends on foo for type information (trivially in this case but it could be more complicated too, or "significant" with resources). For the import case this is resolved by injecting more dependencies, as is evidence by running wasm-tools component wit over the above, printing:

// ....
world w {
  import foo
  import bar
}

Despite not being written explicitly the import foo statement was injected automatically. More broadly all transitive dependencies of imports are injected as further imports. This works well for now and probably is the right thing to do, but the tricky part is with exports. Instead if the above world is:

world w {
    export bar
}

(note the change of import to export then what to do here is less clear. For now what happens is that the transitive dependencies are sometimes still injected as imports:

// printed by `wasm-tools component wit`
world w {
  import foo
  export bar
}

If, however, the world were subtly different a different resolution is applied. If the world explicitly lists both interfaces as export-ed

world w {
  export foo
  export bar

then no imports are injected. Instead it's assumed that bar's dependency on foo is satisfied by the exported interface foo. More generally the algorithm here is roughly that dependencies of exports are walked and if they don't exist as an export then all futher transitive dependencies are added as imports. If the export already exists then it's assumed that's already taken care of its dependencies, so it's skipped.

This strategy was intended to be a reasonable default for the time being where in the future "power user" syntax (or something like that) could be added to configure more advanced scenarios (e.g. changing these heuristics). In fuzzing resources, however, I've found that this doesn't actually work. Consider for example this world:

package foo:bar

interface a {
  resource name
}

interface b {
  use a.{name}
}

world w {
  export a
  export name: interface {
    use a.{name}
    use b.{name as name2}
  }
}

here the name kebab import depends on both a and b. It's also the case that b depends on a. Given the above heuristics though what's happening is:

• name's dependency on a is satisfied by export a
• name's dependency on b is satisfied by an injected import b, which in turn injects an import a

This means that name actually can access two different copies of resource name, one from the import and one from the export. This not only causes problems (hence the fuzz bug) but additionally I think isn't the desired semantics/behavior in WIT. For example if b defined some aggregate type that contained a's resource then the name export should be able to use the aggregate and the resource from a and have them work together. Given the current lowering, though, that's not possible since they're actually different copies.

---

Ok that's the problem statement (roughly at least). The question for me now is how to fix it? Some hard requirements that must be satisfied are, in my opinion:

• Exports must be able to have transitive dependencies. Most use cases hit this nearly immediately.
• Transitive dependencies of exports, by default, shouldn't have to be worried about. Whatever the solution ends up being it shouldn't involve manually writing down all the transitive dependencies or things like that. Similar to imports this is so unergonomic almost no use case wants this.
• Most worlds for the MVP are expected to have a small set of exports (aka 1? 2?) which are unlikely to run into this sort of use case, so starting conservatively is probably fine.

One alternative I can think of is that all transitive dependencies of exports are forced to be imports. This means that it will change the meaning of a few examples I listed above. Additionally the world w in question here would rightfully have two copies of a's resource, one imported and used by export name and one defined locally and exported (used by export a). The downside of this though is that there's no means by which a resource can be defined locally and used by another export.

Another alternative is to make the above world w simply invalid. There are two "paths" to the a interface where one is imported and one is exported, so it's an invalid world as a result. The fix would be to add export b to the list of exports which means that export name would use both exports.

I'm curious though if others have thoughts on this? I realize I could be missing something obvious by accident or something like that! As I type this all out though I'm realizing the "simply say world w is invalid" is probably the way to go since it doesn't close off some more interesting use cases while still making this reasonable to work with today.

[lukewagner]

Nice writeup and analysis! I think you're right that we should reject that world. What took me a sec was how to precisely state the criteria/rationale for rejection. I think it might be this: if we say that the semantics of a Wit interface is a component type that represents uses as imports, then the component type derived from the final anonymous inline interface in your example would have to be:

(type $anonymous_interface (component
  (import (interface "foo:bar/a") (instance $a (export "name" (type (sub resource)))))
  (alias export $a "name" (type $name))
  (import (interface "foo:bar/b") (instance $b (export "name" (type (eq $name)))))
  (alias export $b "name" (type $name2))
  (export "name" (instance
    (export "name" (type (eq $name)))
    (export "name2" (type (eq $name2)))
  ))
))

(Attempting to import foo:bar/a twice would violate unique naming.) Thus, it is the eq constraint inside foo:bar/b that requires clients of this anonymous interface (viz. world w) to supply a single type for foo:bar/a.name. There is, technically, a valid way to satisfy this constraint--to have both the use a.{name} and use b.{name as name2} satisfied by a single injected import of foo:bar/a--but that seems very surprising and probably not what anyone wants, so that's why we reject and require you to use the (future TBD) power syntax to resolve.

[alexcrichton]

Yeah that sounds right to me, and it's actually what the fuzzer ended up catching. Part of the creation of a component using resources implicitly assumed that two imports of a resource were the same (they had an eq bound) but then two resources were passed in because the two resources came from two different instances which then caused issues along the lines of "expected this to validate but it didn't".

In any case bytecodealliance/wasm-tools#1081 implements the idea here to reject more worlds.