Repository: bytecodealliance/wasm-tools
Pull request #1323 (2023-12-07 23:11:07)

Fix incorrect errors returned from merging worlds
This commit fixes a bug in `Resolve::merge` which is one of the workhorses of the `wasm-tools component new` subcommand. Previously it was assumed that `Resolve::packages` always listed packages in topological order, but `Resolve::merge` updated the internal state of `Resolve` to violate this invariant. This happened because new packages which might be dependencies of existing packages (through newly discovered interfaces for example) would be appended at the end.

After wrestling with a few options to solve this issue I've settled on relaxing the invariants of `Resolve` such that it does not always contain a topologically sorted list of packages. Instead a new method, `topological_packages`, is explicitly used to order the packages within `Resolve`. This method is then used as part of `Resolve::merge` which relies on visiting in a topological order.

For testing this it wasn't previously found via fuzzing because fuzzing does not execute `Resolve::merge`. Extra validation about topological-sorted-ness caught the problem in the `merge` tests, however. The fuzzer for WIT has been updated to test merging and assert validity now as well too.


Patch:
diff --git a/crates/wit-component/src/decoding.rs b/crates/wit-component/src/decoding.rs
index 03aee249..48964e97 100644
--- a/crates/wit-component/src/decoding.rs
+++ b/crates/wit-component/src/decoding.rs
@@ -1,30 +1,37 @@
 use anyhow::{anyhow, bail, Context, Result};
 use indexmap::{IndexMap, IndexSet};
-use std::collections::HashMap;
 use std::mem;
+use std::{collections::HashMap, io::Read};
+use wasmparser::Chunk;
 use wasmparser::{
     names::{ComponentName, ComponentNameKind},
-    types, ComponentExport, ComponentExternalKind, ComponentImport, Parser, Payload,
-    PrimitiveValType, ValidPayload, Validator, WasmFeatures,
+    types, ComponentExternalKind, Parser, Payload, PrimitiveValType, ValidPayload, Validator,
+    WasmFeatures,
 };
 use wit_parser::*;
 
 use crate::encoding::docs::{PackageDocs, PACKAGE_DOCS_SECTION_NAME};
 
 /// Represents information about a decoded WebAssembly component.
-struct ComponentInfo<'a> {
+struct ComponentInfo {
     /// Wasmparser-defined type information learned after a component is fully
     /// validated.
     types: types::Types,
     /// List of all imports and exports from this component.
-    externs: Vec<(&'a str, Extern<'a>)>,
+    externs: Vec<(String, Extern)>,
     /// Decoded package docs
     package_docs: Option<PackageDocs>,
 }
 
-enum Extern<'a> {
-    Import(ComponentImport<'a>),
-    Export(ComponentExport<'a>),
+struct DecodingExport {
+    name: String,
+    kind: ComponentExternalKind,
+    index: u32,
+}
+
+enum Extern {
+    Import(String),
+    Export(DecodingExport),
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -33,21 +40,41 @@ enum WitEncodingVersion {
     V2,
 }
 
-impl<'a> ComponentInfo<'a> {
+impl ComponentInfo {
     /// Creates a new component info by parsing the given WebAssembly component bytes.
-    fn new(bytes: &'a [u8]) -> Result<Self> {
-        if !Parser::is_component(bytes) {
-            bail!("input is not a component wasm binary");
-        }
+
+    fn from_reader(mut reader: impl Read) -> Result<Self> {
         let mut validator = Validator::new_with_features(WasmFeatures::all());
         let mut externs = Vec::new();
         let mut depth = 1;
         let mut types = None;
         let mut package_docs = None;
+        let mut cur = Parser::new(0);
+        let mut eof = false;
+        let mut stack = Vec::new();
+        let mut buffer = Vec::new();
+
+        loop {
+            let chunk = cur.parse(&buffer, eof)?;
+            let (payload, consumed) = match chunk {
+                Chunk::NeedMoreData(hint) => {
+                    assert!(!eof); // otherwise an error would be returned
+
+                    // Use the hint to preallocate more space, then read
+                    // some more data into our buffer.
+                    //
+                    // Note that the buffer management here is not ideal,
+                    // but it's compact enough to fit in an example!
+                    let len = buffer.len().clone();
+                    buffer.extend((0..hint).map(|_| 0u8));
+                    let n = reader.read(&mut buffer[len..])?;
+                    buffer.truncate(len + n);
+                    eof = n == 0;
+                    continue;
+                }
 
-        for payload in Parser::new(0).parse_all(bytes) {
-            let payload = payload?;
-
+                Chunk::Parsed { consumed, payload } => (payload, consumed),
+            };
             match validator.payload(&payload)? {
                 ValidPayload::Ok => {}
                 ValidPayload::Parser(_) => depth += 1,
@@ -64,13 +91,23 @@ impl<'a> ComponentInfo<'a> {
                 Payload::ComponentImportSection(s) if depth == 1 => {
                     for import in s {
                         let import = import?;
-                        externs.push((import.name.0, Extern::Import(import)));
+                        externs.push((
+                            import.name.0.to_string(),
+                            Extern::Import(import.name.0.to_string()),
+                        ));
                     }
                 }
                 Payload::ComponentExportSection(s) if depth == 1 => {
                     for export in s {
                         let export = export?;
-                        externs.push((export.name.0, Extern::Export(export)));
+                        externs.push((
+                            export.name.0.to_string(),
+                            Extern::Export(DecodingExport {
+                                name: export.name.0.to_string(),
+                                kind: export.kind,
+                                index: export.index,
+                            }),
+                        ));
                     }
                 }
                 Payload::CustomSection(s) if s.name() == PACKAGE_DOCS_SECTION_NAME => {
@@ -79,9 +116,26 @@ impl<'a> ComponentInfo<'a> {
                     }
                     package_docs = Some(PackageDocs::decode(s.data())?);
                 }
+                Payload::ModuleSection { parser, .. }
+                | Payload::ComponentSection { parser, .. } => {
+                    stack.push(cur.clone());
+                    cur = parser.clone();
+                }
+                Payload::End(_) => {
+                    if let Some(parent_parser) = stack.pop() {
+                        cur = parent_parser.clone();
+                    } else {
+                        break;
+                    }
+                }
                 _ => {}
             }
+
+            // once we're done processing the payload we can forget the
+            // original.
+            buffer.drain(..consumed);
         }
+
         Ok(Self {
             types: types.unwrap(),
             externs,
@@ -116,7 +170,7 @@ impl<'a> ComponentInfo<'a> {
         // strings for each component. The v1 format uses "<namespace>:<package>/wit" as the name
         // for the top-level exports, while the v2 format uses the unqualified name of the encoded
         // entity.
-        match ComponentName::new(self.externs[0].0, 0).ok()?.kind() {
+        match ComponentName::new(&self.externs[0].0, 0).ok()?.kind() {
             ComponentNameKind::Interface(name) if name.interface().as_str() == "wit" => {
                 Some(WitEncodingVersion::V1)
             }
@@ -139,7 +193,7 @@ impl<'a> ComponentInfo<'a> {
             if pkg.is_some() {
                 bail!("more than one top-level exported component type found");
             }
-            let name = ComponentName::new(*name, 0).unwrap();
+            let name = ComponentName::new(name, 0).unwrap();
             pkg = Some(
                 decoder
                     .decode_v1_package(&name, ty)
@@ -318,14 +372,9 @@ impl DecodedWasm {
     }
 }
 
-/// Decodes an in-memory WebAssembly binary into a WIT [`Resolve`] and
-/// associated metadata.
-///
-/// The WebAssembly binary provided here can either be a
-/// WIT-package-encoded-as-binary or an actual component itself. A [`Resolve`]
-/// is always created and the return value indicates which was detected.
-pub fn decode(bytes: &[u8]) -> Result<DecodedWasm> {
-    let info = ComponentInfo::new(bytes)?;
+/// Decode for incremental reading
+pub fn decode_reader(reader: impl Read) -> Result<DecodedWasm> {
+    let info = ComponentInfo::from_reader(reader)?;
 
     if let Some(version) = info.is_wit_package() {
         match version {
@@ -346,6 +395,15 @@ pub fn decode(bytes: &[u8]) -> Result<DecodedWasm> {
         Ok(DecodedWasm::Component(resolve, world))
     }
 }
+/// Decodes an in-memory WebAssembly binary into a WIT [`Resolve`] and
+/// associated metadata.
+///
+/// The WebAssembly binary provided here can either be a
+/// WIT-package-encoded-as-binary or an actual component itself. A [`Resolve`]
+/// is always created and the return value indicates which was detected.
+pub fn decode(bytes: &[u8]) -> Result<DecodedWasm> {
+    decode_reader(bytes)
+}
 
 /// Decodes the single component type `world` specified as a WIT world.
 ///
@@ -533,11 +591,10 @@ impl WitPackageDecoder<'_> {
 
     fn decode_component_import<'a>(
         &mut self,
-        import: &ComponentImport<'_>,
+        name: &str,
         world: WorldId,
         package: &mut PackageFields<'a>,
     ) -> Result<()> {
-        let name = import.name.0;
         log::debug!("decoding component import `{name}`");
         let ty = self.types.component_entity_type_of_import(name).unwrap();
         let owner = TypeOwner::World(world);
@@ -578,11 +635,11 @@ impl WitPackageDecoder<'_> {
 
     fn decode_component_export<'a>(
         &mut self,
-        export: &ComponentExport<'_>,
+        export: &DecodingExport,
         world: WorldId,
         package: &mut PackageFields<'a>,
     ) -> Result<()> {
-        let name = export.name.0;
+        let name = &export.name;
         log::debug!("decoding component export `{name}`");
         let types = &self.types;
         let ty = types.component_entity_type_of_export(name).unwrap();
diff --git a/crates/wit-component/src/encoding.rs b/crates/wit-component/src/encoding.rs
index 6a596087..f6de9d2a 100644
--- a/crates/wit-component/src/encoding.rs
+++ b/crates/wit-component/src/encoding.rs
@@ -434,11 +434,13 @@ impl<'a> EncodingState<'a> {
         }
     }
 
-    fn encode_imports(&mut self) -> Result<()> {
+    fn encode_imports(&mut self, name_map: &HashMap<String, String>) -> Result<()> {
         let mut has_funcs = false;
         for (name, info) in self.info.import_map.iter() {
             match name {
-                Some(name) => self.encode_interface_import(name, info)?,
+                Some(name) => {
+                    self.encode_interface_import(name_map.get(name).unwrap_or(name), info)?
+                }
                 None => has_funcs = true,
             }
         }
@@ -1865,7 +1867,7 @@ pub struct LibraryInfo {
     pub arguments: Vec<(String, Instance)>,
 }
 
-/// Represents an adapter or library to be instansiated as part of the component
+/// Represents an adapter or library to be instantiated as part of the component
 struct Adapter {
     /// The wasm of the module itself, with `component-type` sections stripped
     wasm: Vec<u8>,
@@ -1892,7 +1894,7 @@ pub struct ComponentEncoder {
     validate: bool,
     main_module_exports: IndexSet<WorldKey>,
     adapters: IndexMap<String, Adapter>,
-
+    import_name_map: HashMap<String, String>,
     realloc_via_memory_grow: bool,
 }
 
@@ -1907,7 +1909,7 @@ impl ComponentEncoder {
         let world = self
             .metadata
             .merge(metadata)
-            .context("failed merge WIT package sets together")?;
+            .context("failed merge WIT metadata for module with previous metadata")?;
         self.main_module_exports
             .extend(self.metadata.resolve.worlds[world].exports.keys().cloned());
         self.module = if let Some(producers) = &self.metadata.producers {
@@ -2032,15 +2034,30 @@ impl ComponentEncoder {
         Ok(self)
     }
 
-    /// True if the realloc and stack alloction should use ememory.grow
+    /// True if the realloc and stack allocation should use memory.grow
     /// The default is to use the main module realloc
     /// Can be useful if cabi_realloc cannot be called before the host
-    /// runtime is initialised.
+    /// runtime is initialized.
     pub fn realloc_via_memory_grow(mut self, value: bool) -> Self {
         self.realloc_via_memory_grow = value;
         self
     }
 
+    /// The instance import name map to use.
+    ///
+    /// This is used to rename instance imports in the final component.
+    ///
+    /// For example, if there is an instance import `foo:bar/baz` and it is
+    /// desired that the import actually be an `unlocked-dep` name, then
+    /// `foo:bar/baz` can be mapped to `unlocked-dep=<a:b/c@{>=x.y.z}>`.
+    ///
+    /// Note: the replacement names are not validated during encoding unless
+    /// the `validate` option is set to true.
+    pub fn import_name_map(mut self, map: HashMap<String, String>) -> Self {
+        self.import_name_map = map;
+        self
+    }
+
     /// Encode the component and return the bytes.
     pub fn encode(&self) -> Result<Vec<u8>> {
         if self.module.is_empty() {
@@ -2069,7 +2086,7 @@ impl ComponentEncoder {
             exported_instances: Default::default(),
             info: &world,
         };
-        state.encode_imports()?;
+        state.encode_imports(&self.import_name_map)?;
         state.encode_core_modules();
         state.encode_core_instantiation()?;
         state.encode_exports(CustomModule::Main)?;
@@ -2095,3 +2112,66 @@ impl ComponentEncoder {
         Ok(bytes)
     }
 }
+
+#[cfg(test)]
+mod test {
+    use crate::{dummy_module, embed_component_metadata};
+
+    use super::*;
+    use std::path::Path;
+    use wit_parser::UnresolvedPackage;
+
+    #[test]
+    fn it_renames_imports() {
+        let mut resolve = Resolve::new();
+        let pkg = resolve
+            .push(
+                UnresolvedPackage::parse(
+                    Path::new("test.wit"),
+                    r#"
+package test:wit;
+
+interface i {
+    f: func();
+}
+
+world test {
+    import i;
+    import foo: interface {
+        f: func();
+    }
+}
+"#,
+                )
+                .unwrap(),
+            )
+            .unwrap();
+
+        let world = resolve.select_world(pkg, None).unwrap();
+
+        let mut module = dummy_module(&resolve, world);
+
+        embed_component_metadata(&mut module, &resolve, world, StringEncoding::UTF8).unwrap();
+
+        let encoded = ComponentEncoder::default()
+            .import_name_map(HashMap::from([
+                (
+                    "foo".to_string(),
+                    "unlocked-dep=<foo:bar/foo@{>=1.0.0 <1.1.0}>".to_string(),
+                ),
+                (
+                    "test:wit/i".to_string(),
+                    "locked-dep=<foo:bar/i@1.2.3>".to_string(),
+                ),
+            ]))
+            .module(&module)
+            .unwrap()
+            .validate(true)
+            .encode()
+            .unwrap();
+
+        let wat = wasmprinter::print_bytes(encoded).unwrap();
+        assert!(wat.contains("unlocked-dep=<foo:bar/foo@{>=1.0.0 <1.1.0}>"));
+        assert!(wat.contains("locked-dep=<foo:bar/i@1.2.3>"));
+    }
+}
diff --git a/crates/wit-component/src/lib.rs b/crates/wit-component/src/lib.rs
index 57356451..92205a32 100644
--- a/crates/wit-component/src/lib.rs
+++ b/crates/wit-component/src/lib.rs
@@ -17,7 +17,7 @@ mod printing;
 mod targets;
 mod validation;
 
-pub use decoding::{decode, DecodedWasm};
+pub use decoding::{decode, decode_reader, DecodedWasm};
 pub use encoding::{encode, ComponentEncoder};
 pub use linking::Linker;
 pub use printing::*;
diff --git a/crates/wit-parser/src/resolve.rs b/crates/wit-parser/src/resolve.rs
index 50457c3a..c9086698 100644
--- a/crates/wit-parser/src/resolve.rs
+++ b/crates/wit-parser/src/resolve.rs
@@ -29,14 +29,36 @@ use std::path::{Path, PathBuf};
 /// package as necessary.
 #[derive(Default, Clone, Serialize)]
 pub struct Resolve {
+    /// All knowns worlds within this `Resolve`.
+    ///
+    /// Each world points at a `PackageId` which is stored below. No ordering is
+    /// guaranteed between this list of worlds.
     #[serde(serialize_with = "serialize_arena")]
     pub worlds: Arena<World>,
+
+    /// All knowns interfaces within this `Resolve`.
+    ///
+    /// Each interface points at a `PackageId` which is stored below. No
+    /// ordering is guaranteed between this list of interfaces.
     #[serde(serialize_with = "serialize_arena")]
     pub interfaces: Arena<Interface>,
+
+    /// All knowns types within this `Resolve`.
+    ///
+    /// Types are topologically sorted such that any type referenced from one
+    /// type is guaranteed to be defined previously. Otherwise though these are
+    /// not sorted by interface for example.
     #[serde(serialize_with = "serialize_arena")]
     pub types: Arena<TypeDef>,
+
+    /// All knowns packages within this `Resolve`.
+    ///
+    /// This list of packages is not sorted. Sorted packages can be queried
+    /// through [`Resolve::topological_packages`].
     #[serde(serialize_with = "serialize_arena")]
     pub packages: Arena<Package>,
+
+    /// A map of package names to the ID of the package with that name.
     #[serde(skip)]
     pub package_names: IndexMap<PackageName, PackageId>,
 }
@@ -292,6 +314,7 @@ impl Resolve {
         let mut moved_types = Vec::new();
         for (id, mut ty) in types {
             let new_id = type_map.get(&id).copied().unwrap_or_else(|| {
+                log::debug!("moving type {:?}", ty.name);
                 moved_types.push(id);
                 remap.update_typedef(self, &mut ty);
                 self.types.alloc(ty)
@@ -303,6 +326,7 @@ impl Resolve {
         let mut moved_interfaces = Vec::new();
         for (id, mut iface) in interfaces {
             let new_id = interface_map.get(&id).copied().unwrap_or_else(|| {
+                log::debug!("moving interface {:?}", iface.name);
                 moved_interfaces.push(id);
                 remap.update_interface(self, &mut iface);
                 self.interfaces.alloc(iface)
@@ -314,6 +338,7 @@ impl Resolve {
         let mut moved_worlds = Vec::new();
         for (id, mut world) in worlds {
             let new_id = world_map.get(&id).copied().unwrap_or_else(|| {
+                log::debug!("moving world {}", world.name);
                 moved_worlds.push(id);
                 let mut update = |map: &mut IndexMap<WorldKey, WorldItem>| {
                     for (mut name, mut item) in mem::take(map) {
@@ -619,37 +644,267 @@ impl Resolve {
         }
     }
 
+    /// Returns the interface that `id` uses a type from, if it uses a type from
+    /// a different interface than `id` is defined within.
+    ///
+    /// If `id` is not a use-of-a-type or it's using a type in the same
+    /// interface then `None` is returned.
+    pub fn type_interface_dep(&self, id: TypeId) -> Option<InterfaceId> {
+        let ty = &self.types[id];
+        let dep = match ty.kind {
+            TypeDefKind::Type(Type::Id(id)) => id,
+            _ => return None,
+        };
+        let other = &self.types[dep];
+        if ty.owner == other.owner {
+            None
+        } else {
+            match other.owner {
+                TypeOwner::Interface(id) => Some(id),
+                _ => unreachable!(),
+            }
+        }
+    }
+
     /// Returns an iterator of all interfaces that the interface `id` depends
     /// on.
     ///
     /// Interfaces may depend on others for type information to resolve type
     /// imports.
     ///
-    /// Note that the returned iterate may yield the same interface as a
+    /// Note that the returned iterator may yield the same interface as a
     /// dependency multiple times. Additionally only direct dependencies of `id`
     /// are yielded, not transitive dependencies.
     pub fn interface_direct_deps(&self, id: InterfaceId) -> impl Iterator<Item = InterfaceId> + '_ {
         self.interfaces[id]
             .types
             .iter()
-            .filter_map(move |(_name, ty)| {
-                // Find `other` which `ty` is defined within to determine which
-                // interfaces this interface depends on.
-                let dep = match self.types[*ty].kind {
-                    TypeDefKind::Type(Type::Id(id)) => id,
-                    _ => return None,
-                };
-                let other = match self.types[dep].owner {
-                    TypeOwner::Interface(id) => id,
-                    _ => return None,
-                };
-                if other == id {
+            .filter_map(move |(_name, ty)| self.type_interface_dep(*ty))
+    }
+
+    /// Returns an iterator of all packages that the package `id` depends
+    /// on.
+    ///
+    /// Packages may depend on others for type information to resolve type
+    /// imports or interfaces to resolve worlds.
+    ///
+    /// Note that the returned iterator may yield the same package as a
+    /// dependency multiple times. Additionally only direct dependencies of `id`
+    /// are yielded, not transitive dependencies.
+    pub fn package_direct_deps(&self, id: PackageId) -> impl Iterator<Item = PackageId> + '_ {
+        let pkg = &self.packages[id];
+
+        pkg.interfaces
+            .iter()
+            .flat_map(move |(_name, id)| self.interface_direct_deps(*id))
+            .chain(pkg.worlds.iter().flat_map(move |(_name, id)| {
+                let world = &self.worlds[*id];
+                world
+                    .imports
+                    .iter()
+                    .chain(world.exports.iter())
+                    .filter_map(move |(_name, item)| match item {
+                        WorldItem::Interface(id) => Some(*id),
+                        WorldItem::Function(_) => None,
+                        WorldItem::Type(t) => self.type_interface_dep(*t),
+                    })
+            }))
+            .filter_map(move |iface_id| {
+                let pkg = self.interfaces[iface_id].package?;
+                if pkg == id {
                     None
                 } else {
-                    Some(other)
+                    Some(pkg)
                 }
             })
     }
+
+    /// Returns a topological ordering of packages contained in this `Resolve`.
+    ///
+    /// This returns a list of `PackageId` such that when visited in order it's
+    /// guaranteed that all dependencies will have been defined by prior items
+    /// in the list.
+    pub fn topological_packages(&self) -> Vec<PackageId> {
+        let mut pushed = vec![false; self.packages.len()];
+        let mut order = Vec::new();
+        for (id, _) in self.packages.iter() {
+            self.build_topological_package_ordering(id, &mut pushed, &mut order);
+        }
+        order
+    }
+
+    fn build_topological_package_ordering(
+        &self,
+        id: PackageId,
+        pushed: &mut Vec<bool>,
+        order: &mut Vec<PackageId>,
+    ) {
+        if pushed[id.index()] {
+            return;
+        }
+        for dep in self.package_direct_deps(id) {
+            self.build_topological_package_ordering(dep, pushed, order);
+        }
+        order.push(id);
+        pushed[id.index()] = true;
+    }
+
+    #[doc(hidden)]
+    pub fn assert_valid(&self) {
+        let mut package_interfaces = Vec::new();
+        let mut package_worlds = Vec::new();
+        for (id, pkg) in self.packages.iter() {
+            let mut interfaces = HashSet::new();
+            for (name, iface) in pkg.interfaces.iter() {
+                assert!(interfaces.insert(*iface));
+                let iface = &self.interfaces[*iface];
+                assert_eq!(name, iface.name.as_ref().unwrap());
+                assert_eq!(iface.package.unwrap(), id);
+            }
+            package_interfaces.push(pkg.interfaces.values().copied().collect::<HashSet<_>>());
+            let mut worlds = HashSet::new();
+            for (name, world) in pkg.worlds.iter() {
+                assert!(worlds.insert(*world));
+                let world = &self.worlds[*world];
+                assert_eq!(*name, world.name);
+                assert_eq!(world.package.unwrap(), id);
+            }
+            package_worlds.push(pkg.worlds.values().copied().collect::<HashSet<_>>());
+        }
+
+        let mut interface_types = Vec::new();
+        for (id, iface) in self.interfaces.iter() {
+            assert!(self.packages.get(iface.package.unwrap()).is_some());
+            if iface.name.is_some() {
+                assert!(package_interfaces[iface.package.unwrap().index()].contains(&id));
+            }
+
+            for (name, ty) in iface.types.iter() {
+                let ty = &self.types[*ty];
+                assert_eq!(ty.name.as_ref(), Some(name));
+                assert_eq!(ty.owner, TypeOwner::Interface(id));
+            }
+            interface_types.push(iface.types.values().copied().collect::<HashSet<_>>());
+            for (name, f) in iface.functions.iter() {
+                assert_eq!(*name, f.name);
+            }
+        }
+
+        let mut world_types = Vec::new();
+        for (id, world) in self.worlds.iter() {
+            log::debug!("validating world {}", &world.name);
+            assert!(self.packages.get(world.package.unwrap()).is_some());
+            assert!(package_worlds[world.package.unwrap().index()].contains(&id));
+
+            let mut types = HashSet::new();
+            for (name, item) in world.imports.iter().chain(world.exports.iter()) {
+                log::debug!("validating world item: {}", self.name_world_key(name));
+                match item {
+                    WorldItem::Interface(_) => {}
+                    WorldItem::Function(f) => {
+                        assert_eq!(f.name, name.clone().unwrap_name());
+                    }
+                    WorldItem::Type(ty) => {
+                        assert!(types.insert(*ty));
+                        let ty = &self.types[*ty];
+                        assert_eq!(ty.name, Some(name.clone().unwrap_name()));
+
+                        // TODO: `Resolve::merge_worlds` doesn't uphold this
+                        // invariant, and that should be fixed.
+                        if false {
+                            assert_eq!(ty.owner, TypeOwner::World(id));
+                        }
+                    }
+                }
+            }
+            world_types.push(types);
+        }
+
+        for (ty_id, ty) in self.types.iter() {
+            match ty.owner {
+                TypeOwner::Interface(id) => {
+                    assert!(self.interfaces.get(id).is_some());
+                    assert!(interface_types[id.index()].contains(&ty_id));
+                }
+                TypeOwner::World(id) => {
+                    assert!(self.worlds.get(id).is_some());
+                    assert!(world_types[id.index()].contains(&ty_id));
+                }
+                TypeOwner::None => {}
+            }
+        }
+
+        self.assert_topologically_sorted();
+    }
+
+    fn assert_topologically_sorted(&self) {
+        let mut positions = IndexMap::new();
+        for id in self.topological_packages() {
+            let pkg = &self.packages[id];
+            log::debug!("pkg {}", pkg.name);
+            let prev = positions.insert(Some(id), IndexSet::new());
+            assert!(prev.is_none());
+        }
+        positions.insert(None, IndexSet::new());
+
+        for (id, iface) in self.interfaces.iter() {
+            log::debug!("iface {:?}", iface.name);
+            let ok = positions.get_mut(&iface.package).unwrap().insert(id);
+            assert!(ok);
+        }
+
+        for (_, world) in self.worlds.iter() {
+            log::debug!("world {:?}", world.name);
+
+            let my_package = world.package;
+            let my_package_pos = positions.get_index_of(&my_package).unwrap();
+
+            for (_, item) in world.imports.iter().chain(&world.exports) {
+                let id = match item {
+                    WorldItem::Interface(id) => *id,
+                    _ => continue,
+                };
+                let other_package = self.interfaces[id].package;
+                let other_package_pos = positions.get_index_of(&other_package).unwrap();
+
+                assert!(other_package_pos <= my_package_pos);
+            }
+        }
+
+        for (_id, ty) in self.types.iter() {
+            log::debug!("type {:?} {:?}", ty.name, ty.owner);
+            let other_id = match ty.kind {
+                TypeDefKind::Type(Type::Id(ty)) => ty,
+                _ => continue,
+            };
+            let other = &self.types[other_id];
+            if ty.kind == other.kind {
+                continue;
+            }
+            let my_interface = match ty.owner {
+                TypeOwner::Interface(id) => id,
+                _ => continue,
+            };
+            let other_interface = match other.owner {
+                TypeOwner::Interface(id) => id,
+                _ => continue,
+            };
+
+            let my_package = self.interfaces[my_interface].package;
+            let other_package = self.interfaces[other_interface].package;
+            let my_package_pos = positions.get_index_of(&my_package).unwrap();
+            let other_package_pos = positions.get_index_of(&other_package).unwrap();
+
+            if my_package_pos == other_package_pos {
+                let interfaces = &positions[&my_package];
+                let my_interface_pos = interfaces.get_index_of(&my_interface).unwrap();
+                let other_interface_pos = interfaces.get_index_of(&other_interface).unwrap();
+                assert!(other_interface_pos <= my_interface_pos);
+            } else {
+                assert!(other_package_pos < my_package_pos);
+            }
+        }
+    }
 }
 
 /// Structure returned by [`Resolve::merge`] which contains mappings from
@@ -1599,7 +1854,8 @@ impl<'a> MergeMap<'a> {
     }
 
     fn build(&mut self) -> Result<()> {
-        for (from_id, from) in self.from.packages.iter() {
+        for from_id in self.from.topological_packages() {
+            let from = &self.from.packages[from_id];
             let into_id = match self.into.package_names.get(&from.name) {
                 Some(id) => *id,
 
@@ -1634,12 +1890,14 @@ impl<'a> MergeMap<'a> {
             let into_interface_id = match into.interfaces.get(name) {
                 Some(id) => *id,
                 None => {
+                    log::trace!("adding unique interface {}", name);
                     self.interfaces_to_add
                         .push((name.clone(), into_id, *from_interface_id));
                     continue;
                 }
             };
 
+            log::trace!("merging duplicate interfaces {}", name);
             self.build_interface(*from_interface_id, into_interface_id)
                 .with_context(|| format!("failed to merge interface `{name}`"))?;
         }
@@ -1648,12 +1906,14 @@ impl<'a> MergeMap<'a> {
             let into_world_id = match into.worlds.get(name) {
                 Some(id) => *id,
                 None => {
+                    log::trace!("adding unique world {}", name);
                     self.worlds_to_add
                         .push((name.clone(), into_id, *from_world_id));
                     continue;
                 }
             };
 
+            log::trace!("merging duplicate worlds {}", name);
             self.build_world(*from_world_id, into_world_id)
                 .with_context(|| format!("failed to merge world `{name}`"))?;
         }
diff --git a/fuzz/src/roundtrip_wit.rs b/fuzz/src/roundtrip_wit.rs
index 9bd5a5e6..9a4ef1da 100644
--- a/fuzz/src/roundtrip_wit.rs
+++ b/fuzz/src/roundtrip_wit.rs
@@ -1,7 +1,5 @@
 use arbitrary::{Result, Unstructured};
-use std::borrow::Cow;
 use std::path::Path;
-use wasm_encoder::{CustomSection, Encode, Section};
 use wit_component::*;
 use wit_parser::{Resolve, SourceMap};
 
@@ -34,20 +32,17 @@ pub fn run(u: &mut Unstructured<'_>) -> Result<()> {
 
     // If there's hundreds or thousands of worlds only work with the first few
     // to avoid timing out this fuzzer with asan enabled.
-    let use_next = Some(u.arbitrary()?);
-    for (id, _world) in resolve.worlds.iter().take(20) {
+    let mut decoded_worlds = Vec::new();
+    for (id, world) in resolve.worlds.iter().take(20) {
+        log::debug!("testing world {}", world.name);
         let mut dummy = wit_component::dummy_module(&resolve, id);
-        let metadata =
-            wit_component::metadata::encode(&resolve, id, StringEncoding::UTF8, None, use_next)
-                .unwrap();
-        let section = CustomSection {
-            name: "component-type".into(),
-            data: Cow::Borrowed(&metadata),
-        };
-        dummy.push(section.id());
-        section.encode(&mut dummy);
-
+        wit_component::embed_component_metadata(&mut dummy, &resolve, id, StringEncoding::UTF8)
+            .unwrap();
         write_file("dummy.wasm", &dummy);
+
+        let (_, decoded) = wit_component::metadata::decode(&dummy).unwrap();
+        decoded_worlds.push(decoded.resolve);
+
         let wasm = wit_component::ComponentEncoder::default()
             .module(&dummy)
             .unwrap()
@@ -63,6 +58,17 @@ pub fn run(u: &mut Unstructured<'_>) -> Result<()> {
 
         wit_component::decode(&wasm).unwrap();
     }
+
+    if decoded_worlds.len() < 2 {
+        return Ok(());
+    }
+
+    log::debug!("merging worlds");
+    let w1 = u.choose(&decoded_worlds)?;
+    let w2 = u.choose(&decoded_worlds)?;
+    let mut dst = w1.clone();
+    dst.merge(w2.clone()).unwrap();
+    dst.assert_valid();
     Ok(())
 }
 
diff --git a/src/bin/wasm-tools/component.rs b/src/bin/wasm-tools/component.rs
index 7a4a09de..070ae944 100644
--- a/src/bin/wasm-tools/component.rs
+++ b/src/bin/wasm-tools/component.rs
@@ -72,6 +72,12 @@ fn parse_adapter(s: &str) -> Result<(String, Vec<u8>)> {
     Ok((name.to_string(), wasm))
 }
 
+fn parse_import_name(s: &str) -> Result<(String, String)> {
+    s.split_once('=')
+        .map(|(old, new)| (old.to_string(), new.to_string()))
+        .context("expected `--import-name` option to be of the form `OLD=NEW`")
+}
+
 /// WebAssembly component encoder from an input core wasm binary.
 ///
 /// This subcommand will create a new component `*.wasm` file from an input core
@@ -100,6 +106,18 @@ pub struct NewOpts {
     #[clap(long = "adapt", value_name = "[NAME=]MODULE", value_parser = parse_adapter)]
     adapters: Vec<(String, Vec<u8>)>,
 
+    /// Rename an instance import in the output component.
+    ///
+    /// This may be used to rename instance imports in the final component.
+    ///
+    /// For example, `--import-name "a:b/c=unlocked-dep=<d:e/f>"` will
+    /// rename the instance import `a:b/c` such that it becomes an `unlocked-dep`
+    /// name.
+    ///
+    /// If the old import name is not found, it is ignored.
+    #[clap(long = "import-name", value_name = "[OLD]=NEW", value_parser = parse_import_name)]
+    import_names: HashMap<String, String>,
+
     #[clap(flatten)]
     io: wasm_tools::InputOutput,
 
@@ -135,6 +153,7 @@ impl NewOpts {
         encoder = encoder.realloc_via_memory_grow(self.realloc_via_memory_grow);
 
         let bytes = encoder
+            .import_name_map(self.import_names)
             .encode()
             .context("failed to encode a component from module")?;
 


Test patch:
diff --git a/crates/wit-component/tests/merge.rs b/crates/wit-component/tests/merge.rs
index 6176b1c1..264c0c0d 100644
--- a/crates/wit-component/tests/merge.rs
+++ b/crates/wit-component/tests/merge.rs
@@ -1,9 +1,8 @@
 use anyhow::{Context, Result};
 use pretty_assertions::assert_eq;
-use std::collections::HashSet;
 use std::{fs, path::Path};
 use wit_component::WitPrinter;
-use wit_parser::{Resolve, TypeOwner, WorldItem};
+use wit_parser::Resolve;
 
 /// This is a test which iterates over the `tests/merge` directory and treats
 /// each subdirectory as its own test. Each subdirectory has an `into` and a
@@ -32,8 +31,8 @@ fn merging() -> Result<()> {
         let mut into = Resolve::default();
         into.push_dir(&path.join("into"))?;
 
-        assert_valid_resolve(&from);
-        assert_valid_resolve(&into);
+        from.assert_valid();
+        into.assert_valid();
 
         match into.merge(from) {
             Ok(_) => {
@@ -41,7 +40,7 @@ fn merging() -> Result<()> {
                     !test_case.starts_with("bad-"),
                     "should have failed to merge"
                 );
-                assert_valid_resolve(&into);
+                into.assert_valid();
                 for (id, pkg) in into.packages.iter() {
                     let expected = path
                         .join("merge")
@@ -77,81 +76,3 @@ fn assert_output(expected: &Path, actual: &str) -> Result<()> {
     }
     Ok(())
 }
-
-fn assert_valid_resolve(resolve: &Resolve) {
-    let mut package_interfaces = Vec::new();
-    let mut package_worlds = Vec::new();
-    for (id, pkg) in resolve.packages.iter() {
-        let mut interfaces = HashSet::new();
-        for (name, iface) in pkg.interfaces.iter() {
-            assert!(interfaces.insert(*iface));
-            let iface = &resolve.interfaces[*iface];
-            assert_eq!(name, iface.name.as_ref().unwrap());
-            assert_eq!(iface.package.unwrap(), id);
-        }
-        package_interfaces.push(pkg.interfaces.values().copied().collect::<HashSet<_>>());
-        let mut worlds = HashSet::new();
-        for (name, world) in pkg.worlds.iter() {
-            assert!(worlds.insert(*world));
-            let world = &resolve.worlds[*world];
-            assert_eq!(*name, world.name);
-            assert_eq!(world.package.unwrap(), id);
-        }
-        package_worlds.push(pkg.worlds.values().copied().collect::<HashSet<_>>());
-    }
-
-    let mut interface_types = Vec::new();
-    for (id, iface) in resolve.interfaces.iter() {
-        assert!(resolve.packages.get(iface.package.unwrap()).is_some());
-        if iface.name.is_some() {
-            assert!(package_interfaces[iface.package.unwrap().index()].contains(&id));
-        }
-
-        for (name, ty) in iface.types.iter() {
-            let ty = &resolve.types[*ty];
-            assert_eq!(ty.name.as_ref(), Some(name));
-            assert_eq!(ty.owner, TypeOwner::Interface(id));
-        }
-        interface_types.push(iface.types.values().copied().collect::<HashSet<_>>());
-        for (name, f) in iface.functions.iter() {
-            assert_eq!(*name, f.name);
-        }
-    }
-
-    let mut world_types = Vec::new();
-    for (id, world) in resolve.worlds.iter() {
-        assert!(resolve.packages.get(world.package.unwrap()).is_some());
-        assert!(package_worlds[world.package.unwrap().index()].contains(&id));
-
-        let mut types = HashSet::new();
-        for (name, item) in world.imports.iter().chain(world.exports.iter()) {
-            match item {
-                WorldItem::Interface(_) => {}
-                WorldItem::Function(f) => {
-                    assert_eq!(f.name, name.clone().unwrap_name());
-                }
-                WorldItem::Type(ty) => {
-                    assert!(types.insert(*ty));
-                    let ty = &resolve.types[*ty];
-                    assert_eq!(ty.name, Some(name.clone().unwrap_name()));
-                    assert_eq!(ty.owner, TypeOwner::World(id));
-                }
-            }
-        }
-        world_types.push(types);
-    }
-
-    for (ty_id, ty) in resolve.types.iter() {
-        match ty.owner {
-            TypeOwner::Interface(id) => {
-                assert!(resolve.interfaces.get(id).is_some());
-                assert!(interface_types[id.index()].contains(&ty_id));
-            }
-            TypeOwner::World(id) => {
-                assert!(resolve.worlds.get(id).is_some());
-                assert!(world_types[id.index()].contains(&ty_id));
-            }
-            TypeOwner::None => {}
-        }
-    }
-}