Are the same layout functions defined at any level equivalent?

[oovm]

Motivation

To reduce the size of the final product, I'm trying to merge types.

My operation is as follows

• Promote all types to the top level, keeping only the first type with the same signature.
  • All resource types (sub resource) are treated differently.
• Analyze the set of types imported by all functions in each component
• Use this collection as a dependency for topological sorting.
• Instantiate all types and functions one by one according to topological sorting.
  • The first instantiated component contains definitions of all independent types
  • A dependency-free type means that the recursive dependencies of this type do not contain any resources.
• Declare core functions with (canon lower)

Question

I would like to know if the end product obtained this way is legal?

Can functions and composite types with the same type but different parameter names be merged?

[lukewagner]

That hoisting should work for purely structural types (i.e., anything not transitively referring to a resource type). However, resource types will end up needing to stay where they are defined and thus any structural types referring to those resource types will similarly need to stay in the same scope.

[oovm]

Derived types of specific resource types appear to be promoted to the top level.

This code passes the wasmtime 18 validator.

(component $Root
    (type $array (list u8))

    (import "wasi:io/error@0.2.0" (instance $wasi:io/error@0.2.0
        (export "error" (type (sub resource)))
    ))
    (alias export $wasi:io/error@0.2.0 "error" (type $io-error))

    (type $stream-error (variant
        (case "last-operation-failed" (own $io-error))
        (case "closed")
    ))

    (import "wasi:io/streams@0.2.0" (instance $wasi:io/streams@0.2.0
        (export $output-stream "output-stream" (type (sub resource)))
        (alias outer $Root $array (type $array))
        (alias outer $Root $io-error (type $io-error))
        (alias outer $Root $stream-error (type $stream-error))

        (export $stream-error0 "stream-error" (type (eq $stream-error)))
        (type $stream-result (result (error $stream-error0)))

        (export "[method]output-stream.blocking-write-and-flush"
            (func (param "self" (borrow $output-stream)) (param "contents" $array) (result $stream-result))
        )
    ))
    (alias export $wasi:io/streams@0.2.0 "output-stream" (type $output-stream))
    (alias export $wasi:io/streams@0.2.0 "[method]output-stream.blocking-write-and-flush" (func $output-stream.blocking-write-and-flush))

    (import "wasi:cli/stdout@0.2.0" (instance $wasi:cli/stdout@0.2.0
        (alias outer $Root $output-stream (type $output-stream))
        (export "get-stdout" (func (result (own $output-stream))))
    ))
)

Note that stream-error is actually defined in wasi:io/streams.

---

What I don’t quite understand is why I need to define $stream-error0 = (eq $stream-error).

If I remove this wrap step, the validator will report an error instance not valid to be used as import. I don’t know what this means.

[lukewagner]

Ah, sorry, I thought we were talking about hoisting/deduping types between different (e.g., nested) components. Yes, if we're in a single-component context, what you're talking about makes sense: once you treat each distinct resource type { import, definition, export } as having a distinct identity, then you can aggressively de-duplicate structurally-equal type DAGs.

[oovm]

Your understanding is correct, I did refer to type promotion under components and nested components in the title.

When components are nested, can't they simply be promoted to the top level?

[lukewagner]

Oh right, I forgot an important detail in my last comment (addressing your concurrent edit): in addition to resource types each having their own identity, we also want to treat some otherwise-structural types (viz., records and variants) as-if they were nominal for the benefit of bindings generators in languages that don't have full structural typing and thus need to introduce define and name a type. Thus, validation requires imported/exported functions that use these otherwise-structural types to use the type-index introduced by an import/export eq to the structural type (which now unambiguously pairs that structural type with a name that the bindings generator can use). So yeah, that does rather limit the type hoisting you can do.

[lukewagner]

When components are nested, can't they simply be promoted to the top level?

Yes, you can transform an arbitrary-depth component tree into one root component that nests only leaf components.

[oovm]

Thanks for clearing up my doubts about the eq statement.

---

Can the final product always flatten to the following skeleton form?

(component $Root
    ;; Independent type definition, without any resource dependencies
    (type $name ...)
    ;; import and export the first in topological sort
    (import "world/interface1" (instance $instance-name1
        (alias outer $Root $name (type $name))
        ;; export resource
        (export "resource-name" (type (sub resource)))
        ;; export function
        (export "function-name"
            (func (param $imported-type) (result $imported-type))
        )
    ))
    (alias export $instance-name "resource-name" (type $resource-type))
    (alias export $instance-name "function-name" (type function-type))

    ;; define all type with dependencies $resource-type
    (type $name ...)
    ;; again import and export
    (import "world/interface2" (instance $instance-name2))
    (alias export ...)

    ;; All resources, types, and functions have been defined, and you can start defining core functions
    (core func $core-name (canon lower
        (func $comp-name "core-function-name")
    ))

    ;; Define core modules and instantiate them
    (core module $HelloWorld
        (import "world/interface1" "func1" (func $world/interface1/func1 ...))
        (import "world/interface2" "func1" (func $world/interface2/func1 ...))
        ...
    )
    (core instance $hello-world (instantiate $HelloWorld
        (with "world/interface1" (instance $instance-name1))
        (with "world/interface2" (instance $instance-name2))
    )
    ;; other core modules and instances
    ...
)

[lukewagner]

Yep, that looks right to me!

[oovm]

Excuse me, I still don’t quite understand something about (eq type)

Why this way of writing is wrong:

(component $Root
    (import "wasi:io/error@0.2.0" (instance $wasi:io/error@0.2.0
        (export "error" (type (sub resource)))
    ))
    (alias export $wasi:io/error@0.2.0 "error" (type $io-error))

    (type $stream-error (variant
        (case "last-operation-failed" (own $io-error))
        (case "closed")
    ))
    (type $stream-result (result (error $stream-error)))

    (import "wasi:io/streams@0.2.0" (instance $wasi:io/streams@0.2.0
        (export $output-stream "output-stream" (type (sub resource)))
        (alias outer $Root $io-error (type $io-error))

        ;; right code
;;        (alias outer $Root $stream-error (type $stream-error0))
;;        (export $stream-error "stream-error" (type (eq $stream-error0)))
;;        (type $stream-result (result (error $stream-error)))
        ;; wrong code
        (alias outer $Root $stream-result (type $stream-result0))
        (export $stream-result "stream-result" (type (eq $stream-result0)))

        (export "[method]output-stream.blocking-write-and-flush"
            (func (param "self" (borrow $output-stream)) (param "contents" (list u8)) (result $stream-result))
        )
    ))
    (alias export $wasi:io/streams@0.2.0 "output-stream" (type $output-stream))
    (alias export $wasi:io/streams@0.2.0 "[method]output-stream.blocking-write-and-flush" (func $output-stream.blocking-write-and-flush))
)

Does the type following eq have to be an independent type (enum, variant, flags) rather than a composite type (option, result)?

But according to specialized value types, result is a syntactic sugar for variant?

                    (tuple <valtype>*) ↦ (record (field "𝒊" <valtype>)*) for 𝒊=0,1,...
                    (flags "<label>"*) ↦ (record (field "<label>" bool)*)
                     (enum "<label>"+) ↦ (variant (case "<label>")+)
                    (option <valtype>) ↦ (variant (case "none") (case "some" <valtype>))
(result <valtype>? (error <valtype>)?) ↦ (variant (case "ok" <valtype>?) (case "error" <valtype>?))
                                string ↦ (list char)

[lukewagner]

Great question. I believe (but @alexcrichton check me on this) the reason that the right code works is that:

1. The $stream-error variant needs to be named directly (even when included in a named compound type like a result)
2. Even though result is a specialization of a variant, because a result is something that many languages can express structurally, the "must be named" rule doesn't impact result (and, I expect, option and tuple). In general, specialized types are treated as their own separate types by most of the spec (binary format, validation and Canonical ABI).

Thus, the wrong code is rejected since the transitively-contained variant is not named; the fact that the result is named is neither necessary nor sufficient.

Hope that helps!

[alexcrichton]

Yep that sounds right to me!

The only bit I'd add is that the "specializatoin" nowadays is exclusively about the ABI, so it doesn't apply at the typechecking layer.

[oovm]

This linearization scheme works, but the algorithm I proposed in the original post is wrong.

If direct topological sorting is performed, depending on the node insertion order, sometimes it will cause problems with alternate instantiation of stream and io types.

flowchart LR
    subgraph "group-1"
        std::io::StreamError["stream-error"]:::variant
    end
    subgraph "wasi:io/error@0.2.0"
        std::io::IoError["error"]:::resource
    end
    std::io::IoError -.-> std::io::StreamError
    subgraph "wasi:io/streams@0.2.0"
        std::io::OutputStream["output-stream"]:::resource
        std::io::InputStream["input-stream"]:::resource
        std::io::OutputStream::blocking_write_and_flush["[method]output-stream.blocking-write-and-flush"]:::function
        std::io::OutputStream -.-> std::io::OutputStream::blocking_write_and_flush
        std::io::StreamError -.-> std::io::OutputStream::blocking_write_and_flush
    end
    subgraph "wasi:cli/stderr@0.2.0"
        std::io::standard_error["get-stderr"]:::function
        std::io::OutputStream -.-> std::io::standard_error
    end
    subgraph "wasi:cli/stdin@0.2.0"
        std::io::standard_input["get-stdin"]:::function
        std::io::InputStream -...-> std::io::standard_input
    end
    subgraph "wasi:cli/stdout@0.2.0"
        std::io::standard_output["get-stdout"]:::function
        std::io::OutputStream -.-> std::io::standard_output
    end

In fact, this is a hierarchical topological sorting problem. Each isolated type (top-level type) needs to be assigned a group ID of -1, -2, -3, and each resource type needs to be assigned a group ID of 0, 1, 2, 3 according to the group. group id.

Then first topologically sort the groups, then topologically sort within each group, and finally promote the instantiation order of all independent top-level types, so as to obtain a linear optimal instantiation order.

(component $root
    (import "wasi:io/error@0.2.0" (instance $wasi:io/error@0.2.0
        (export $std::io::IoError "error" (type (sub resource)))
    ))
    (alias export $wasi:io/error@0.2.0 "error" (type $std::io::IoError))
    (type $std::io::StreamError (variant
        (case "last-operation-failed" (own $std::io::IoError))
        (case "closed")
    ))
    (import "wasi:io/streams@0.2.0" (instance $wasi:io/streams@0.2.0
        (export $std::io::InputStream "input-stream" (type (sub resource)))
        (export $std::io::OutputStream "output-stream" (type (sub resource)))
        (alias outer $root $std::io::StreamError (type $std::io::StreamError?))(export $std::io::StreamError "stream-error" (type (eq $std::io::StreamError?)))
        (export "[method]output-stream.blocking-write-and-flush" (func
            (param "self" (borrow $std::io::OutputStream)) 
            (param "contents" (list u8)) 
            (result (result (error $std::io::StreamError)))
        ))
    ))
    (alias export $wasi:io/streams@0.2.0 "input-stream" (type $std::io::InputStream))
    (alias export $wasi:io/streams@0.2.0 "output-stream" (type $std::io::OutputStream))
    (alias export $wasi:io/streams@0.2.0 "[method]output-stream.blocking-write-and-flush" (func $std::io::OutputStream::blocking_write_and_flush))
    (import "wasi:cli/stderr@0.2.0" (instance $wasi:cli/stderr@0.2.0
        (export "get-stderr" (func
            (result (own $std::io::OutputStream))
        ))
    ))
    (alias export $wasi:cli/stderr@0.2.0 "get-stderr" (func $std::io::standard_error))
    (import "wasi:cli/stdin@0.2.0" (instance $wasi:cli/stdin@0.2.0
        (export "get-stdin" (func
            (result (own $std::io::InputStream))
        ))
    ))
    (alias export $wasi:cli/stdin@0.2.0 "get-stdin" (func $std::io::standard_input))
    (import "wasi:cli/stdout@0.2.0" (instance $wasi:cli/stdout@0.2.0
        (export "get-stdout" (func
            (result (own $std::io::OutputStream))
        ))
    ))
    (alias export $wasi:cli/stdout@0.2.0 "get-stdout" (func $std::io::standard_output))
)

[lukewagner]

Thanks for working through that!