resolve.rs source code [crates/wit_parser/src/resolve.rs]

1	use std::cmp::Ordering;
2	use std::collections::hash_map;
3	use std::collections::{BTreeMap, HashMap, HashSet};
4	use std::fmt;
5	use std::mem;
6	use std::path::{Path, PathBuf};
7
8	use anyhow::{anyhow, bail, ensure, Context, Result};
9	use id_arena::{Arena, Id};
10	use indexmap::{IndexMap, IndexSet};
11	use semver::Version;
12	#[cfg(feature = "serde")]
13	use serde_derive::Serialize;
14
15	use crate::ast::lex::Span;
16	use crate::ast::{parse_use_path, ParsedUsePath};
17	#[cfg(feature = "serde")]
18	use crate::serde_::{serialize_arena, serialize_id_map};
19	use crate::{
20	AstItem, Docs, Error, Function, FunctionKind, Handle, IncludeName, Interface, InterfaceId,
21	InterfaceSpan, LiftLowerAbi, ManglingAndAbi, PackageName, PackageNotFoundError, Results,
22	SourceMap, Stability, Type, TypeDef, TypeDefKind, TypeId, TypeIdVisitor, TypeOwner,
23	UnresolvedPackage, UnresolvedPackageGroup, World, WorldId, WorldItem, WorldKey, WorldSpan,
24	};
25
26	mod clone;
27
28	/// Representation of a fully resolved set of WIT packages.
29	///
30	/// This structure contains a graph of WIT packages and all of their contents
31	/// merged together into the contained arenas. All items are sorted
32	/// topologically and everything here is fully resolved, so with a `Resolve` no
33	/// name lookups are necessary and instead everything is index-based.
34	///
35	/// Working with a WIT package requires inserting it into a `Resolve` to ensure
36	/// that all of its dependencies are satisfied. This will give the full picture
37	/// of that package's types and such.
38	///
39	/// Each item in a `Resolve` has a parent link to trace it back to the original
40	/// package as necessary.
41	#[derive(Default, Clone, Debug)]
42	#[cfg_attr(feature = "serde", derive(Serialize))]
43	pub struct Resolve {
44	/// All known worlds within this `Resolve`.
45	///
46	/// Each world points at a `PackageId` which is stored below. No ordering is
47	/// guaranteed between this list of worlds.
48	#[cfg_attr(feature = "serde", serde(serialize_with = "serialize_arena"))]
49	pub worlds: Arena<World>,
50
51	/// All known interfaces within this `Resolve`.
52	///
53	/// Each interface points at a `PackageId` which is stored below. No
54	/// ordering is guaranteed between this list of interfaces.
55	#[cfg_attr(feature = "serde", serde(serialize_with = "serialize_arena"))]
56	pub interfaces: Arena<Interface>,
57
58	/// All known types within this `Resolve`.
59	///
60	/// Types are topologically sorted such that any type referenced from one
61	/// type is guaranteed to be defined previously. Otherwise though these are
62	/// not sorted by interface for example.
63	#[cfg_attr(feature = "serde", serde(serialize_with = "serialize_arena"))]
64	pub types: Arena<TypeDef>,
65
66	/// All known packages within this `Resolve`.
67	///
68	/// This list of packages is not sorted. Sorted packages can be queried
69	/// through [`Resolve::topological_packages`].
70	#[cfg_attr(feature = "serde", serde(serialize_with = "serialize_arena"))]
71	pub packages: Arena<Package>,
72
73	/// A map of package names to the ID of the package with that name.
74	#[cfg_attr(feature = "serde", serde(skip))]
75	pub package_names: IndexMap<PackageName, PackageId>,
76
77	/// Activated features for this [`Resolve`].
78	///
79	/// This set of features is empty by default. This is consulted for
80	/// `@unstable` annotations in loaded WIT documents. Any items with
81	/// `@unstable` are filtered out unless their feature is present within this
82	/// set.
83	#[cfg_attr(feature = "serde", serde(skip))]
84	pub features: IndexSet<String>,
85
86	/// Activate all features for this [`Resolve`].
87	#[cfg_attr(feature = "serde", serde(skip))]
88	pub all_features: bool,
89	}
90
91	/// A WIT package within a `Resolve`.
92	///
93	/// A package is a collection of interfaces and worlds. Packages additionally
94	/// have a unique identifier that affects generated components and uniquely
95	/// identifiers this particular package.
96	#[derive(Clone, Debug)]
97	#[cfg_attr(feature = "serde", derive(Serialize))]
98	pub struct Package {
99	/// A unique name corresponding to this package.
100	pub name: PackageName,
101
102	/// Documentation associated with this package.
103	#[cfg_attr(feature = "serde", serde(skip_serializing_if = "Docs::is_empty"))]
104	pub docs: Docs,
105
106	/// All interfaces contained in this packaged, keyed by the interface's
107	/// name.
108	#[cfg_attr(feature = "serde", serde(serialize_with = "serialize_id_map"))]
109	pub interfaces: IndexMap<String, InterfaceId>,
110
111	/// All worlds contained in this package, keyed by the world's name.
112	#[cfg_attr(feature = "serde", serde(serialize_with = "serialize_id_map"))]
113	pub worlds: IndexMap<String, WorldId>,
114	}
115
116	pub type PackageId = Id<Package>;
117
118	/// All the sources used during resolving a directory or path.
119	#[derive(Clone, Debug)]
120	pub struct PackageSourceMap {
121	sources: Vec<Vec<PathBuf>>,
122	package_id_to_source_map_idx: BTreeMap<PackageId, usize>,
123	}
124
125	impl PackageSourceMap {
126	fn from_single_source(package_id: PackageId, source: &Path) -> Self {
127	Self {
128	sources: vec![vec![source.to_path_buf()]],
129	package_id_to_source_map_idx: BTreeMap::from([(package_id, `0`)]),
130	}
131	}
132
133	fn from_source_maps(
134	source_maps: Vec<SourceMap>,
135	package_id_to_source_map_idx: BTreeMap<PackageId, usize>,
136	) -> PackageSourceMap {
137	for (package_id, idx) in &package_id_to_source_map_idx {
138	if *idx >= source_maps.len() {
139	panic!(
140	"Invalid source map index: {}, package id: {:?}, source maps size: {}",
141	idx,
142	package_id,
143	source_maps.len()
144	)
145	}
146	}
147
148	Self {
149	sources: source_maps
150	.into_iter()
151	.map(\|source_map\| {
152	source_map
153	.source_files()
154	.map(\|path\| path.to_path_buf())
155	.collect()
156	})
157	.collect(),
158	package_id_to_source_map_idx,
159	}
160	}
161
162	/// All unique source paths.
163	pub fn paths(&self) -> impl Iterator<Item = &Path> {
164	// Usually any two source map should not have duplicated source paths,
165	// but it can happen, e.g. with using [`Resolve::push_str`] directly.
166	// To be sure we use a set for deduplication here.
167	self.sources
168	.iter()
169	.flatten()
170	.map(\|path_buf\| path_buf.as_ref())
171	.collect::<HashSet<&Path>>()
172	.into_iter()
173	}
174
175	/// Source paths for package
176	pub fn package_paths(&self, id: PackageId) -> Option<impl Iterator<Item = &Path>> {
177	self.package_id_to_source_map_idx
178	.get(&id)
179	.map(\|&idx\| self.sources[idx].iter().map(\|path_buf\| path_buf.as_ref()))
180	}
181	}
182
183	enum ParsedFile {
184	#[cfg(feature = "decoding")]
185	Package(PackageId),
186	Unresolved(UnresolvedPackageGroup),
187	}
188
189	/// Visitor helper for performing topological sort on a group of packages.
190	fn visit<'a>(
191	pkg: &'a UnresolvedPackage,
192	pkg_details_map: &'a BTreeMap<PackageName, (UnresolvedPackage, usize)>,
193	order: &mut IndexSet<PackageName>,
194	visiting: &mut HashSet<&'a PackageName>,
195	source_maps: &[SourceMap],
196	) -> Result<()> {
197	if order.contains(&pkg.name) {
198	return Ok(());
199	}
200
201	match pkg_details_map.get(&pkg.name) {
202	Some(pkg_details) => {
203	let (_, source_maps_index) = pkg_details;
204	source_maps[*source_maps_index].rewrite_error(\|\| {
205	for (i, (dep, _)) in pkg.foreign_deps.iter().enumerate() {
206	let span = pkg.foreign_dep_spans[i];
207	if !visiting.insert(dep) {
208	bail!(Error::new(span, "package depends on itself"));
209	}
210	if let Some(dep) = pkg_details_map.get(dep) {
211	let (dep_pkg, _) = dep;
212	visit(dep_pkg, pkg_details_map, order, visiting, source_maps)?;
213	}
214	assert!(visiting.remove(dep));
215	}
216	assert!(order.insert(pkg.name.clone()));
217	Ok(())
218	})
219	}
220	None => panic!("No pkg_details found for package when doing topological sort"),
221	}
222	}
223
224	impl Resolve {
225	/// Creates a new [`Resolve`] with no packages/items inside of it.
226	pub fn new() -> Resolve {
227	Resolve::default()
228	}
229
230	/// Parse WIT packages from the input `path`.
231	///
232	/// The input `path` can be one of:
233	///
234	/// A directory containing a WIT package with an optional `deps` directory*
235	/// for any dependent WIT packages it references.
236	/// A single standalone WIT file.*
237	/// A wasm-encoded WIT package as a single file in the wasm binary format.*
238	/// A wasm-encoded WIT package as a single file in the wasm text format.*
239	///
240	/// In all of these cases packages are allowed to depend on previously
241	/// inserted packages into this `Resolve`. Resolution for packages is based
242	/// on the name of each package and reference.
243	///
244	/// This method returns a `PackageId` and additionally a `PackageSourceMap`.
245	/// The `PackageId` represent the main package that was parsed. For example if a single WIT
246	/// file was specified this will be the main package found in the file. For a directory this
247	/// will be all the main package in the directory itself. The `PackageId` value is useful
248	/// to pass to [`Resolve::select_world`] to take a user-specified world in a
249	/// conventional fashion and select which to use for bindings generation.
250	///
251	/// The returned [`PackageSourceMap`] contains all the sources used during this operation.
252	/// This can be useful for systems that want to rebuild or regenerate bindings based on files modified,
253	/// or for ones which like to identify the used files for a package.
254	///
255	/// More information can also be found at [`Resolve::push_dir`] and
256	/// [`Resolve::push_file`].
257	pub fn push_path(&mut self, path: impl AsRef<Path>) -> Result<(PackageId, PackageSourceMap)> {
258	self._push_path(path.as_ref())
259	}
260
261	fn _push_path(&mut self, path: &Path) -> Result<(PackageId, PackageSourceMap)> {
262	if path.is_dir() {
263	self.push_dir(path).with_context(\|\| {
264	format!(
265	"failed to resolve directory while parsing WIT for path [{}]",
266	path.display()
267	)
268	})
269	} else {
270	let id = self.push_file(path)?;
271	Ok((id, PackageSourceMap::from_single_source(id, path)))
272	}
273	}
274
275	fn sort_unresolved_packages(
276	&mut self,
277	main: UnresolvedPackageGroup,
278	deps: Vec<UnresolvedPackageGroup>,
279	) -> Result<(PackageId, PackageSourceMap)> {
280	let mut pkg_details_map = BTreeMap::new();
281	let mut source_maps = Vec::new();
282
283	let mut insert = \|group: UnresolvedPackageGroup\| {
284	let UnresolvedPackageGroup {
285	main,
286	nested,
287	source_map,
288	} = group;
289	let i = source_maps.len();
290	source_maps.push(source_map);
291
292	for pkg in nested.into_iter().chain([main]) {
293	let name = pkg.name.clone();
294	let my_span = pkg.package_name_span;
295	let (prev_pkg, prev_i) = match pkg_details_map.insert(name.clone(), (pkg, i)) {
296	Some(pair) => pair,
297	None => continue,
298	};
299	let loc1 = source_maps[i].render_location(my_span);
300	let loc2 = source_maps[prev_i].render_location(prev_pkg.package_name_span);
301	bail!(
302	"\
303	package {name} is defined in two different locations:`\n`\
304	* {loc1}`\n`\
305	* {loc2}`\n`\
306	"
307	)
308	}
309	Ok(())
310	};
311
312	let main_name = main.main.name.clone();
313	insert(main)?;
314	for dep in deps {
315	insert(dep)?;
316	}
317
318	// Perform a simple topological sort which will bail out on cycles
319	// and otherwise determine the order that packages must be added to
320	// this `Resolve`.
321	let mut order = IndexSet::new();
322	let mut visiting = HashSet::new();
323	for pkg_details in pkg_details_map.values() {
324	let (pkg, _) = pkg_details;
325	visit(
326	pkg,
327	&pkg_details_map,
328	&mut order,
329	&mut visiting,
330	&source_maps,
331	)?;
332	}
333
334	// Ensure that the final output is topologically sorted. Use a set to ensure that we render
335	// the buffers for each `SourceMap` only once, even though multiple packages may reference
336	// the same `SourceMap`.
337	let mut package_id_to_source_map_idx = BTreeMap::new();
338	let mut main_pkg_id = None;
339	for name in order {
340	let (pkg, source_map_index) = pkg_details_map.remove(&name).unwrap();
341	let source_map = &source_maps[source_map_index];
342	let is_main = pkg.name == main_name;
343	let id = self.push(pkg, source_map)?;
344	if is_main {
345	assert!(main_pkg_id.is_none());
346	main_pkg_id = Some(id);
347	}
348	package_id_to_source_map_idx.insert(id, source_map_index);
349	}
350
351	Ok((
352	main_pkg_id.unwrap(),
353	PackageSourceMap::from_source_maps(source_maps, package_id_to_source_map_idx),
354	))
355	}
356
357	/// Parses the filesystem directory at `path` as a WIT package and returns
358	/// a fully resolved [`PackageId`] list as a result.
359	///
360	/// The directory itself is parsed with [`UnresolvedPackageGroup::parse_dir`]
361	/// and then all packages found are inserted into this `Resolve`. The `path`
362	/// specified may have a `deps` subdirectory which is probed automatically
363	/// for any other WIT dependencies.
364	///
365	/// The `deps` folder may contain:
366	///
367	/// `$path/deps/my-package/.wit` - a directory that may contain multiple
368	/// WIT files. This is parsed with [`UnresolvedPackageGroup::parse_dir`]
369	/// and then inserted into this [`Resolve`]. Note that cannot recursively
370	/// contain a `deps` directory.
371	/// `$path/deps/my-package.wit` - a single-file WIT package. This is*
372	/// parsed with [`Resolve::push_file`] and then added to `self` for
373	/// name reoslution.
374	/// `$path/deps/my-package.{wasm,wat}` - a wasm-encoded WIT package either*
375	/// in the text for binary format.
376	///
377	/// In all cases entries in the `deps` folder are added to `self` first
378	/// before adding files found in `path` itself. All WIT packages found are
379	/// candidates for name-based resolution that other packages may use.
380	///
381	/// This function returns a tuple of two values. The first value is a
382	/// [`PackageId`], which represents the main WIT package found within
383	/// `path`. This argument is useful for passing to [`Resolve::select_world`]
384	/// for choosing something to bindgen with.
385	///
386	/// The second value returned is a [`PackageSourceMap`], which contains all the sources
387	/// that were parsed during resolving. This can be useful for:
388	/// build systems that want to rebuild bindings whenever one of the files changed*
389	/// or other tools, which want to identify the sources for the resolved packages*
390	pub fn push_dir(&mut self, path: impl AsRef<Path>) -> Result<(PackageId, PackageSourceMap)> {
391	self._push_dir(path.as_ref())
392	}
393
394	fn _push_dir(&mut self, path: &Path) -> Result<(PackageId, PackageSourceMap)> {
395	let top_pkg = UnresolvedPackageGroup::parse_dir(path)
396	.with_context(\|\| format!("failed to parse package: {}", path.display()))?;
397	let deps = path.join("deps");
398	let deps = self
399	.parse_deps_dir(&deps)
400	.with_context(\|\| format!("failed to parse dependency directory: {}", deps.display()))?;
401
402	self.sort_unresolved_packages(top_pkg, deps)
403	}
404
405	fn parse_deps_dir(&mut self, path: &Path) -> Result<Vec<UnresolvedPackageGroup>> {
406	let mut ret = Vec::new();
407	if !path.exists() {
408	return Ok(ret);
409	}
410	let mut entries = path
411	.read_dir()
412	.and_then(\|i\| i.collect::<std::io::Result<Vec<_>>>())
413	.context("failed to read directory")?;
414	entries.sort_by_key(\|e\| e.file_name());
415	for dep in entries {
416	let path = dep.path();
417	let pkg = if dep.file_type()?.is_dir() \|\| path.metadata()?.is_dir() {
418	// If this entry is a directory or a symlink point to a
419	// directory then always parse it as an `UnresolvedPackage`
420	// since it's intentional to not support recursive `deps`
421	// directories.
422	UnresolvedPackageGroup::parse_dir(&path)
423	.with_context(\|\| format!("failed to parse package: {}", path.display()))?
424	} else {
425	// If this entry is a file then we may want to ignore it but
426	// this may also be a standalone WIT file or a `.wasm` or*
427	// `.wat` encoded package.*
428	let filename = dep.file_name();
429	match Path::new(&filename).extension().and_then(\|s\| s.to_str()) {
430	Some("wit") \| Some("wat") \| Some("wasm") => match self._push_file(&path)? {
431	#[cfg(feature = "decoding")]
432	ParsedFile::Package(_) => continue,
433	ParsedFile::Unresolved(pkg) => pkg,
434	},
435
436	// Other files in deps dir are ignored for now to avoid
437	// accidentally including things like `.DS_Store` files in
438	// the call below to `parse_dir`.
439	_ => continue,
440	}
441	};
442	ret.push(pkg);
443	}
444	Ok(ret)
445	}
446
447	/// Parses the contents of `path` from the filesystem and pushes the result
448	/// into this `Resolve`.
449	///
450	/// The `path` referenced here can be one of:
451	///
452	/// A WIT file. Note that in this case this single WIT file will be the*
453	/// entire package and any dependencies it has must already be in `self`.
454	/// A WIT package encoded as WebAssembly, either in text or binary form.*
455	/// In this the package and all of its dependencies are automatically
456	/// inserted into `self`.
457	///
458	/// In both situations the `PackageId`s of the resulting resolved packages
459	/// are returned from this method. The return value is mostly useful in
460	/// conjunction with [`Resolve::select_world`].
461	pub fn push_file(&mut self, path: impl AsRef<Path>) -> Result<PackageId> {
462	match self._push_file(path.as_ref())? {
463	#[cfg(feature = "decoding")]
464	ParsedFile::Package(id) => Ok(id),
465	ParsedFile::Unresolved(pkg) => self.push_group(pkg),
466	}
467	}
468
469	fn _push_file(&mut self, path: &Path) -> Result<ParsedFile> {
470	let contents = std::fs::read(path)
471	.with_context(\|\| format!("failed to read path for WIT [{}]", path.display()))?;
472
473	// If decoding is enabled at compile time then try to see if this is a
474	// wasm file.
475	#[cfg(feature = "decoding")]
476	{
477	use crate::decoding::{decode, DecodedWasm};
478
479	#[cfg(feature = "wat")]
480	let is_wasm = wat::Detect::from_bytes(&contents).is_wasm();
481	#[cfg(not(feature = "wat"))]
482	let is_wasm = wasmparser::Parser::is_component(&contents);
483
484	if is_wasm {
485	#[cfg(feature = "wat")]
486	let contents = wat::parse_bytes(&contents).map_err(\|mut e\| {
487	e.set_path(path);
488	e
489	})?;
490
491	match decode(&contents)? {
492	DecodedWasm::Component(..) => {
493	bail!("found an actual component instead of an encoded WIT package in wasm")
494	}
495	DecodedWasm::WitPackage(resolve, pkg) => {
496	let remap = self.merge(resolve)?;
497	return Ok(ParsedFile::Package(remap.packages[pkg.index()]));
498	}
499	}
500	}
501	}
502
503	// If this wasn't a wasm file then assume it's a WIT file.
504	let text = match std::str::from_utf8(&contents) {
505	Ok(s) => s,
506	Err(_) => bail!("input file is not valid utf-8 [{}]", path.display()),
507	};
508	let pkgs = UnresolvedPackageGroup::parse(path, text)?;
509	Ok(ParsedFile::Unresolved(pkgs))
510	}
511
512	/// Appends a new [`UnresolvedPackage`] to this [`Resolve`], creating a
513	/// fully resolved package with no dangling references.
514	///
515	/// All the dependencies of `unresolved` must already have been loaded
516	/// within this `Resolve` via previous calls to `push` or other methods such
517	/// as [`Resolve::push_path`].
518	///
519	/// Any dependency resolution error or otherwise world-elaboration error
520	/// will be returned here, if successful a package identifier is returned
521	/// which corresponds to the package that was just inserted.
522	pub fn push(
523	&mut self,
524	unresolved: UnresolvedPackage,
525	source_map: &SourceMap,
526	) -> Result<PackageId> {
527	source_map.rewrite_error(\|\| Remap::default().append(self, unresolved))
528	}
529
530	/// Appends new [`UnresolvedPackageGroup`] to this [`Resolve`], creating a
531	/// fully resolved package with no dangling references.
532	///
533	/// Any dependency resolution error or otherwise world-elaboration error
534	/// will be returned here, if successful a package identifier is returned
535	/// which corresponds to the package that was just inserted.
536	///
537	/// The returned [`PackageId`]s are listed in topologically sorted order.
538	pub fn push_group(&mut self, unresolved_group: UnresolvedPackageGroup) -> Result<PackageId> {
539	let (pkg_id, _) = self.sort_unresolved_packages(unresolved_group, Vec::new())?;
540	Ok(pkg_id)
541	}
542
543	/// Convenience method for combining [`UnresolvedPackageGroup::parse`] and
544	/// [`Resolve::push_group`].
545	///
546	/// The `path` provided is used for error messages but otherwise is not
547	/// read. This method does not touch the filesystem. The `contents` provided
548	/// are the contents of a WIT package.
549	pub fn push_str(&mut self, path: impl AsRef<Path>, contents: &str) -> Result<PackageId> {
550	self.push_group(UnresolvedPackageGroup::parse(path.as_ref(), contents)?)
551	}
552
553	pub fn all_bits_valid(&self, ty: &Type) -> bool {
554	match ty {
555	Type::U8
556	\| Type::S8
557	\| Type::U16
558	\| Type::S16
559	\| Type::U32
560	\| Type::S32
561	\| Type::U64
562	\| Type::S64
563	\| Type::F32
564	\| Type::F64 => `true`,
565
566	Type::Bool \| Type::Char \| Type::String => `false`,
567
568	Type::Id(id) => match &self.types[*id].kind {
569	TypeDefKind::List(_)
570	\| TypeDefKind::Variant(_)
571	\| TypeDefKind::Enum(_)
572	\| TypeDefKind::Option(_)
573	\| TypeDefKind::Result(_)
574	\| TypeDefKind::Future(_)
575	\| TypeDefKind::Stream(_)
576	\| TypeDefKind::ErrorContext => `false`,
577	TypeDefKind::Type(t) => self.all_bits_valid(t),
578
579	TypeDefKind::Handle(h) => match h {
580	crate::Handle::Own(_) => `true`,
581	crate::Handle::Borrow(_) => `true`,
582	},
583
584	TypeDefKind::Resource => `false`,
585	TypeDefKind::Record(r) => r.fields.iter().all(\|f\| self.all_bits_valid(&f.ty)),
586	TypeDefKind::Tuple(t) => t.types.iter().all(\|t\| self.all_bits_valid(t)),
587
588	// FIXME: this could perhaps be `true` for multiples-of-32 but
589	// seems better to probably leave this as unconditionally
590	// `false` for now, may want to reconsider later?
591	TypeDefKind::Flags(_) => `false`,
592
593	TypeDefKind::Unknown => unreachable!(),
594	},
595	}
596	}
597
598	/// Merges all the contents of a different `Resolve` into this one. The
599	/// `Remap` structure returned provides a mapping from all old indices to
600	/// new indices
601	///
602	/// This operation can fail if `resolve` disagrees with `self` about the
603	/// packages being inserted. Otherwise though this will additionally attempt
604	/// to "union" packages found in `resolve` with those found in `self`.
605	/// Unioning packages is keyed on the name/url of packages for those with
606	/// URLs present. If found then it's assumed that both `Resolve` instances
607	/// were originally created from the same contents and are two views
608	/// of the same package.
609	pub fn merge(&mut self, resolve: Resolve) -> Result<Remap> {
610	log::trace!(
611	"merging {} packages into {} packages",
612	resolve.packages.len(),
613	self.packages.len()
614	);
615
616	let mut map = MergeMap::new(&resolve, &self);
617	map.build()?;
618	let MergeMap {
619	package_map,
620	interface_map,
621	type_map,
622	world_map,
623	interfaces_to_add,
624	worlds_to_add,
625	..
626	} = map;
627
628	// With a set of maps from ids in `resolve` to ids in `self` the next
629	// operation is to start moving over items and building a `Remap` to
630	// update ids.
631	//
632	// Each component field of `resolve` is moved into `self` so long as
633	// its ID is not within one of the maps above. If it's present in a map
634	// above then that means the item is already present in `self` so a new
635	// one need not be added. If it's not present in a map that means it's
636	// not present in `self` so it must be added to an arena.
637	//
638	// When adding an item to an arena one of the `remap.update_` methods*
639	// is additionally called to update all identifiers from pointers within
640	// `resolve` to becoming pointers within `self`.
641	//
642	// Altogether this should weave all the missing items in `self` from
643	// `resolve` into one structure while updating all identifiers to
644	// be local within `self`.
645
646	let mut remap = Remap::default();
647	let Resolve {
648	types,
649	worlds,
650	interfaces,
651	packages,
652	package_names,
653	features: _,
654	..
655	} = resolve;
656
657	let mut moved_types = Vec::new();
658	for (id, mut ty) in types {
659	let new_id = match type_map.get(&id).copied() {
660	Some(id) => {
661	update_stability(&ty.stability, &mut self.types[id].stability)?;
662	id
663	}
664	None => {
665	log::debug!("moving type {:?}", ty.name);
666	moved_types.push(id);
667	remap.update_typedef(self, &mut ty, None)?;
668	self.types.alloc(ty)
669	}
670	};
671	assert_eq!(remap.types.len(), id.index());
672	remap.types.push(Some(new_id));
673	}
674
675	let mut moved_interfaces = Vec::new();
676	for (id, mut iface) in interfaces {
677	let new_id = match interface_map.get(&id).copied() {
678	Some(id) => {
679	update_stability(&iface.stability, &mut self.interfaces[id].stability)?;
680	id
681	}
682	None => {
683	log::debug!("moving interface {:?}", iface.name);
684	moved_interfaces.push(id);
685	remap.update_interface(self, &mut iface, None)?;
686	self.interfaces.alloc(iface)
687	}
688	};
689	assert_eq!(remap.interfaces.len(), id.index());
690	remap.interfaces.push(Some(new_id));
691	}
692
693	let mut moved_worlds = Vec::new();
694	for (id, mut world) in worlds {
695	let new_id = match world_map.get(&id).copied() {
696	Some(id) => {
697	update_stability(&world.stability, &mut self.worlds[id].stability)?;
698	id
699	}
700	None => {
701	log::debug!("moving world {}", world.name);
702	moved_worlds.push(id);
703	let mut update = \|map: &mut IndexMap<WorldKey, WorldItem>\| -> Result<_> {
704	for (mut name, mut item) in mem::take(map) {
705	remap.update_world_key(&mut name, None)?;
706	match &mut item {
707	WorldItem::Function(f) => remap.update_function(self, f, None)?,
708	WorldItem::Interface { id, .. } => {
709	id = remap.map_interface(id, None)?
710	}
711	WorldItem::Type(i) => i = remap.map_type(i, None)?,
712	}
713	map.insert(name, item);
714	}
715	Ok(())
716	};
717	update(&mut world.imports)?;
718	update(&mut world.exports)?;
719	self.worlds.alloc(world)
720	}
721	};
722	assert_eq!(remap.worlds.len(), id.index());
723	remap.worlds.push(Some(new_id));
724	}
725
726	for (id, mut pkg) in packages {
727	let new_id = match package_map.get(&id).copied() {
728	Some(id) => id,
729	None => {
730	for (_, id) in pkg.interfaces.iter_mut() {
731	id = remap.map_interface(id, None)?;
732	}
733	for (_, id) in pkg.worlds.iter_mut() {
734	id = remap.map_world(id, None)?;
735	}
736	self.packages.alloc(pkg)
737	}
738	};
739	assert_eq!(remap.packages.len(), id.index());
740	remap.packages.push(new_id);
741	}
742
743	for (name, id) in package_names {
744	let id = remap.packages[id.index()];
745	if let Some(prev) = self.package_names.insert(name, id) {
746	assert_eq!(prev, id);
747	}
748	}
749
750	// Fixup all "parent" links now.
751	//
752	// Note that this is only done for items that are actually moved from
753	// `resolve` into `self`, which is tracked by the various `moved_`*
754	// lists built incrementally above. The ids in the `moved_` lists*
755	// are ids within `resolve`, so they're translated through `remap` to
756	// ids within `self`.
757	for id in moved_worlds {
758	let id = remap.map_world(id, None)?;
759	if let Some(pkg) = self.worlds[id].package.as_mut() {
760	*pkg = remap.packages[pkg.index()];
761	}
762	}
763	for id in moved_interfaces {
764	let id = remap.map_interface(id, None)?;
765	if let Some(pkg) = self.interfaces[id].package.as_mut() {
766	*pkg = remap.packages[pkg.index()];
767	}
768	}
769	for id in moved_types {
770	let id = remap.map_type(id, None)?;
771	match &mut self.types[id].owner {
772	TypeOwner::Interface(id) => id = remap.map_interface(id, None)?,
773	TypeOwner::World(id) => id = remap.map_world(id, None)?,
774	TypeOwner::None => {}
775	}
776	}
777
778	// And finally process items that were present in `resolve` but were
779	// not present in `self`. This is only done for merged packages as
780	// documents may be added to `self.documents` but wouldn't otherwise be
781	// present in the `documents` field of the corresponding package.
782	for (name, pkg, iface) in interfaces_to_add {
783	let prev = self.packages[pkg]
784	.interfaces
785	.insert(name, remap.map_interface(iface, None)?);
786	assert!(prev.is_none());
787	}
788	for (name, pkg, world) in worlds_to_add {
789	let prev = self.packages[pkg]
790	.worlds
791	.insert(name, remap.map_world(world, None)?);
792	assert!(prev.is_none());
793	}
794
795	log::trace!("now have {} packages", self.packages.len());
796
797	#[cfg(debug_assertions)]
798	self.assert_valid();
799	Ok(remap)
800	}
801
802	/// Merges the world `from` into the world `into`.
803	///
804	/// This will attempt to merge one world into another, unioning all of its
805	/// imports and exports together. This is an operation performed by
806	/// `wit-component`, for example where two different worlds from two
807	/// different libraries were linked into the same core wasm file and are
808	/// producing a singular world that will be the final component's
809	/// interface.
810	///
811	/// This operation can fail if the imports/exports overlap.
812	pub fn merge_worlds(&mut self, from: WorldId, into: WorldId) -> Result<()> {
813	let mut new_imports = Vec::new();
814	let mut new_exports = Vec::new();
815
816	let from_world = &self.worlds[from];
817	let into_world = &self.worlds[into];
818
819	log::trace!("merging {} into {}", from_world.name, into_world.name);
820
821	// First walk over all the imports of `from` world and figure out what
822	// to do with them.
823	//
824	// If the same item exists in `from` and `into` then merge it together
825	// below with `merge_world_item` which basically asserts they're the
826	// same. Otherwise queue up a new import since if `from` has more
827	// imports than `into` then it's fine to add new imports.
828	for (name, from_import) in from_world.imports.iter() {
829	let name_str = self.name_world_key(name);
830	match into_world.imports.get(name) {
831	Some(into_import) => {
832	log::trace!("info/from shared import on `{name_str}`");
833	self.merge_world_item(from_import, into_import)
834	.with_context(\|\| format!("failed to merge world import {name_str}"))?;
835	}
836	None => {
837	log::trace!("new import: `{name_str}`");
838	new_imports.push((name.clone(), from_import.clone()));
839	}
840	}
841	}
842
843	// Build a set of interfaces which are required to be imported because
844	// of `into`'s exports. This set is then used below during
845	// `ensure_can_add_world_export`.
846	//
847	// This is the set of interfaces which exports depend on that are
848	// themselves not exports.
849	let mut must_be_imported = HashMap::new();
850	for (key, export) in into_world.exports.iter() {
851	for dep in self.world_item_direct_deps(export) {
852	if into_world.exports.contains_key(&WorldKey::Interface(dep)) {
853	continue;
854	}
855	self.foreach_interface_dep(dep, &mut \|id\| {
856	must_be_imported.insert(id, key.clone());
857	});
858	}
859	}
860
861	// Next walk over exports of `from` and process these similarly to
862	// imports.
863	for (name, from_export) in from_world.exports.iter() {
864	let name_str = self.name_world_key(name);
865	match into_world.exports.get(name) {
866	Some(into_export) => {
867	log::trace!("info/from shared export on `{name_str}`");
868	self.merge_world_item(from_export, into_export)
869	.with_context(\|\| format!("failed to merge world export {name_str}"))?;
870	}
871	None => {
872	log::trace!("new export `{name_str}`");
873	// See comments in `ensure_can_add_world_export` for why
874	// this is slightly different than imports.
875	self.ensure_can_add_world_export(
876	into_world,
877	name,
878	from_export,
879	&must_be_imported,
880	)
881	.with_context(\|\| {
882	format!("failed to add export `{}`", self.name_world_key(name))
883	})?;
884	new_exports.push((name.clone(), from_export.clone()));
885	}
886	}
887	}
888
889	// For all the new imports and exports they may need to be "cloned" to
890	// be able to belong to the new world. For example:
891	//
892	// Anonymous interfaces have a `package` field which points to the*
893	// package of the containing world, but `from` and `into` may not be
894	// in the same package.
895	//
896	// Type imports have an `owner` field that point to `from`, but they*
897	// now need to point to `into` instead.
898	//
899	// Cloning is no trivial task, however, so cloning is delegated to a
900	// submodule to perform a "deep" clone and copy items into new arena
901	// entries as necessary.
902	let mut cloner = clone::Cloner::new(self, TypeOwner::World(from), TypeOwner::World(into));
903	cloner.register_world_type_overlap(from, into);
904	for (name, item) in new_imports.iter_mut().chain(&mut new_exports) {
905	cloner.world_item(name, item);
906	}
907
908	// Insert any new imports and new exports found first.
909	let into_world = &mut self.worlds[into];
910	for (name, import) in new_imports {
911	let prev = into_world.imports.insert(name, import);
912	assert!(prev.is_none());
913	}
914	for (name, export) in new_exports {
915	let prev = into_world.exports.insert(name, export);
916	assert!(prev.is_none());
917	}
918
919	#[cfg(debug_assertions)]
920	self.assert_valid();
921	Ok(())
922	}
923
924	fn merge_world_item(&self, from: &WorldItem, into: &WorldItem) -> Result<()> {
925	let mut map = MergeMap::new(self, self);
926	match (from, into) {
927	(WorldItem::Interface { id: from, .. }, WorldItem::Interface { id: into, .. }) => {
928	// If these imports are the same that can happen, for
929	// example, when both worlds to `import foo:bar/baz;`. That
930	// foreign interface will point to the same interface within
931	// `Resolve`.
932	if from == into {
933	return Ok(());
934	}
935
936	// .. otherwise this MUST be a case of
937	// `import foo: interface { ... }`. If `from != into` but
938	// both `from` and `into` have the same name then the
939	// `WorldKey::Interface` case is ruled out as otherwise
940	// they'd have different names.
941	//
942	// In the case of an anonymous interface all we can do is
943	// ensure that the interfaces both match, so use `MergeMap`
944	// for that.
945	map.build_interface(from, into)
946	.context("failed to merge interfaces")?;
947	}
948
949	// Like `WorldKey::Name` interfaces for functions and types the
950	// structure is asserted to be the same.
951	(WorldItem::Function(from), WorldItem::Function(into)) => {
952	map.build_function(from, into)
953	.context("failed to merge functions")?;
954	}
955	(WorldItem::Type(from), WorldItem::Type(into)) => {
956	map.build_type_id(from, into)
957	.context("failed to merge types")?;
958	}
959
960	// Kind-level mismatches are caught here.
961	(WorldItem::Interface { .. }, _)
962	\| (WorldItem::Function { .. }, _)
963	\| (WorldItem::Type { .. }, _) => {
964	bail!("different kinds of items");
965	}
966	}
967	assert!(map.interfaces_to_add.is_empty());
968	assert!(map.worlds_to_add.is_empty());
969	Ok(())
970	}
971
972	/// This method ensures that the world export of `name` and `item` can be
973	/// added to the world `into` without changing the meaning of `into`.
974	///
975	/// All dependencies of world exports must either be:
976	///
977	/// An export themselves*
978	/// An import with all transitive dependencies of the import also imported*
979	///
980	/// It's not possible to depend on an import which then also depends on an
981	/// export at some point, for example. This method ensures that if `name`
982	/// and `item` are added that this property is upheld.
983	fn ensure_can_add_world_export(
984	&self,
985	into: &World,
986	name: &WorldKey,
987	item: &WorldItem,
988	must_be_imported: &HashMap<InterfaceId, WorldKey>,
989	) -> Result<()> {
990	assert!(!into.exports.contains_key(name));
991	let name = self.name_world_key(name);
992
993	// First make sure that all of this item's dependencies are either
994	// exported or the entire chain of imports rooted at that dependency are
995	// all imported.
996	for dep in self.world_item_direct_deps(item) {
997	if into.exports.contains_key(&WorldKey::Interface(dep)) {
998	continue;
999	}
1000	self.ensure_not_exported(into, dep)
1001	.with_context(\|\| format!("failed validating export of `{name}`"))?;
1002	}
1003
1004	// Second make sure that this item, if it's an interface, will not alter
1005	// the meaning of the preexisting world by ensuring that it's not in the
1006	// set of "must be imported" items.
1007	if let WorldItem::Interface { id, .. } = item {
1008	if let Some(export) = must_be_imported.get(&id) {
1009	let export_name = self.name_world_key(export);
1010	bail!(
1011	"export `{export_name}` depends on `{name}` \
1012	previously as an import which will change meaning \
1013	if `{name}` is added as an export"
1014	);
1015	}
1016	}
1017
1018	Ok(())
1019	}
1020
1021	fn ensure_not_exported(&self, world: &World, id: InterfaceId) -> Result<()> {
1022	let key = WorldKey::Interface(id);
1023	let name = self.name_world_key(&key);
1024	if world.exports.contains_key(&key) {
1025	bail!(
1026	"world exports `{name}` but it's also transitively used by an \
1027	import \
1028	which means that this is not valid"
1029	)
1030	}
1031	for dep in self.interface_direct_deps(id) {
1032	self.ensure_not_exported(world, dep)
1033	.with_context(\|\| format!("failed validating transitive import dep `{name}`"))?;
1034	}
1035	Ok(())
1036	}
1037
1038	/// Returns an iterator of all the direct interface dependencies of this
1039	/// `item`.
1040	///
1041	/// Note that this doesn't include transitive dependencies, that must be
1042	/// followed manually.
1043	fn world_item_direct_deps(&self, item: &WorldItem) -> impl Iterator<Item = InterfaceId> + '_ {
1044	let mut interface = None;
1045	let mut ty = None;
1046	match item {
1047	WorldItem::Function(_) => {}
1048	WorldItem::Type(id) => ty = Some(*id),
1049	WorldItem::Interface { id, .. } => interface = Some(*id),
1050	}
1051
1052	interface
1053	.into_iter()
1054	.flat_map(move \|id\| self.interface_direct_deps(id))
1055	.chain(ty.and_then(\|t\| self.type_interface_dep(t)))
1056	}
1057
1058	/// Invokes `f` with `id` and all transitive interface dependencies of `id`.
1059	///
1060	/// Note that `f` may be called with the same id multiple times.
1061	fn foreach_interface_dep(&self, id: InterfaceId, f: &mut dyn FnMut(InterfaceId)) {
1062	f(id);
1063	for dep in self.interface_direct_deps(id) {
1064	self.foreach_interface_dep(dep, f);
1065	}
1066	}
1067
1068	/// Returns the ID of the specified `interface`.
1069	///
1070	/// Returns `None` for unnamed interfaces.
1071	pub fn id_of(&self, interface: InterfaceId) -> Option<String> {
1072	let interface = &self.interfaces[interface];
1073	Some(self.id_of_name(interface.package.unwrap(), interface.name.as_ref()?))
1074	}
1075
1076	/// Returns the "canonicalized interface name" of `interface`.
1077	///
1078	/// Returns `None` for unnamed interfaces. See `BuildTargets.md` in the
1079	/// upstream component model repository for more information about this.
1080	pub fn canonicalized_id_of(&self, interface: InterfaceId) -> Option<String> {
1081	let interface = &self.interfaces[interface];
1082	Some(self.canonicalized_id_of_name(interface.package.unwrap(), interface.name.as_ref()?))
1083	}
1084
1085	/// Convert a world to an "importized" version where the world is updated
1086	/// in-place to reflect what it would look like to be imported.
1087	///
1088	/// This is a transformation which is used as part of the process of
1089	/// importing a component today. For example when a component depends on
1090	/// another component this is useful for generating WIT which can be use to
1091	/// represent the component being imported. The general idea is that this
1092	/// function will update the `world_id` specified such it imports the
1093	/// functionality that it previously exported. The world will be left with
1094	/// no exports.
1095	///
1096	/// This world is then suitable for merging into other worlds or generating
1097	/// bindings in a context that is importing the original world. This
1098	/// is intended to be used as part of language tooling when depending on
1099	/// other components.
1100	pub fn importize(&mut self, world_id: WorldId, out_world_name: Option<String>) -> Result<()> {
1101	// Rename the world to avoid having it get confused with the original
1102	// name of the world. Add `-importized` to it for now. Precisely how
1103	// this new world is created may want to be updated over time if this
1104	// becomes problematic.
1105	let world = &mut self.worlds[world_id];
1106	let pkg = &mut self.packages[world.package.unwrap()];
1107	pkg.worlds.shift_remove(&world.name);
1108	if let Some(name) = out_world_name {
1109	world.name = name.clone();
1110	pkg.worlds.insert(name, world_id);
1111	} else {
1112	world.name.push_str("-importized");
1113	pkg.worlds.insert(world.name.clone(), world_id);
1114	}
1115
1116	// Trim all non-type definitions from imports. Types can be used by
1117	// exported functions, for example, so they're preserved.
1118	world.imports.retain(\|_, item\| match item {
1119	WorldItem::Type(_) => `true`,
1120	_ => `false`,
1121	});
1122
1123	for (name, export) in mem::take(&mut world.exports) {
1124	match (name.clone(), world.imports.insert(name, export)) {
1125	// no previous item? this insertion was ok
1126	(_, None) => {}
1127
1128	// cannot overwrite an import with an export
1129	(WorldKey::Name(name), Some(_)) => {
1130	bail!("world export `{name}` conflicts with import of same name");
1131	}
1132
1133	// Exports already don't overlap each other and the only imports
1134	// preserved above were types so this shouldn't be reachable.
1135	(WorldKey::Interface(_), _) => unreachable!(),
1136	}
1137	}
1138
1139	// Fill out any missing transitive interface imports by elaborating this
1140	// world which does that for us.
1141	self.elaborate_world(world_id)?;
1142
1143	#[cfg(debug_assertions)]
1144	self.assert_valid();
1145	Ok(())
1146	}
1147
1148	/// Returns the ID of the specified `name` within the `pkg`.
1149	pub fn id_of_name(&self, pkg: PackageId, name: &str) -> String {
1150	let package = &self.packages[pkg];
1151	let mut base = String::new();
1152	base.push_str(&package.name.namespace);
1153	base.push_str(":");
1154	base.push_str(&package.name.name);
1155	base.push_str("/");
1156	base.push_str(name);
1157	if let Some(version) = &package.name.version {
1158	base.push_str(&format!("@{version}"));
1159	}
1160	base
1161	}
1162
1163	/// Returns the "canonicalized interface name" of the specified `name`
1164	/// within the `pkg`.
1165	///
1166	/// See `BuildTargets.md` in the upstream component model repository for
1167	/// more information about this.
1168	pub fn canonicalized_id_of_name(&self, pkg: PackageId, name: &str) -> String {
1169	let package = &self.packages[pkg];
1170	let mut base = String::new();
1171	base.push_str(&package.name.namespace);
1172	base.push_str(":");
1173	base.push_str(&package.name.name);
1174	base.push_str("/");
1175	base.push_str(name);
1176	if let Some(version) = &package.name.version {
1177	base.push_str("@");
1178	let string = PackageName::version_compat_track_string(version);
1179	base.push_str(&string);
1180	}
1181	base
1182	}
1183
1184	/// Attempts to locate a world given the "default" set of `packages` and the
1185	/// optional string specifier `world`.
1186	///
1187	/// This method is intended to be used by bindings generation tools to
1188	/// select a world from either `packages` or a package in this `Resolve`.
1189	/// The `packages` list is a return value from methods such as
1190	/// [`push_path`](Resolve::push_path), [`push_dir`](Resolve::push_dir),
1191	/// [`push_file`](Resolve::push_file), [`push_group`](Resolve::push_group),
1192	/// or [`push_str`](Resolve::push_str). The return values of those methods
1193	/// are the "main package list" which is specified by the user and is used
1194	/// as a heuristic for world selection.
1195	///
1196	/// If `world` is `None` then `packages` must have one entry and that
1197	/// package must have exactly one world. If this is the case then that world
1198	/// will be returned, otherwise an error will be returned.
1199	///
1200	/// If `world` is `Some` then it can either be:
1201	///
1202	/// A kebab-name of a world such as `"the-world"`. In this situation*
1203	/// the `packages` list must have only a single entry. If `packages` has
1204	/// no entries or more than one, or if the kebab-name does not exist in
1205	/// the one package specified, then an error will be returned.
1206	///
1207	/// An ID-based form of a world which is selected within this `Resolve`,*
1208	/// for example `"wasi:http/proxy"`. In this situation the `packages`
1209	/// array is ignored and the ID specified is use to lookup a package. Note
1210	/// that a version does not need to be specified in this string if there's
1211	/// only one package of the same name and it has a version. In this
1212	/// situation the version can be omitted.
1213	///
1214	/// If successful the corresponding `WorldId` is returned, otherwise an
1215	/// error is returned.
1216	///
1217	/// # Examples
1218	///
1219	/// ```
1220	/// use anyhow::Result;
1221	/// use wit_parser::Resolve;
1222	///
1223	/// fn main() -> Result<()> {
1224	/// let mut resolve = Resolve::default();
1225	///
1226	/// // For inputs which have a single package and only one world `None`
1227	/// // can be specified.
1228	/// let id = resolve.push_str(
1229	/// "./my-test.wit",
1230	/// r#"
1231	/// package example:wit1;
1232	///
1233	/// world foo {
1234	/// // ...
1235	/// }
1236	/// "#,
1237	/// )?;
1238	/// assert!(resolve.select_world(id, None).is_ok());
1239	///
1240	/// // For inputs which have a single package and multiple worlds then
1241	/// // a world must be specified.
1242	/// let id = resolve.push_str(
1243	/// "./my-test.wit",
1244	/// r#"
1245	/// package example:wit2;
1246	///
1247	/// world foo { /* ... */ }
1248	///
1249	/// world bar { /* ... */ }
1250	/// "#,
1251	/// )?;
1252	/// assert!(resolve.select_world(id, None).is_err());
1253	/// assert!(resolve.select_world(id, Some("foo")).is_ok());
1254	/// assert!(resolve.select_world(id, Some("bar")).is_ok());
1255	///
1256	/// // For inputs which have more than one package then a fully
1257	/// // qualified name must be specified.
1258	///
1259	/// // Note that the `ids` or `packages` argument is ignored if a fully
1260	/// // qualified world specified is provided meaning previous worlds
1261	/// // can be selected.
1262	/// assert!(resolve.select_world(id, Some("example:wit1/foo")).is_ok());
1263	/// assert!(resolve.select_world(id, Some("example:wit2/foo")).is_ok());
1264	///
1265	/// // When selecting with a version it's ok to drop the version when
1266	/// // there's only a single copy of that package in `Resolve`.
1267	/// resolve.push_str(
1268	/// "./my-test.wit",
1269	/// r#"
1270	/// package example:wit5@1.0.0;
1271	///
1272	/// world foo { /* ... */ }
1273	/// "#,
1274	/// )?;
1275	/// assert!(resolve.select_world(id, Some("example:wit5/foo")).is_ok());
1276	///
1277	/// // However when a single package has multiple versions in a resolve
1278	/// // it's required to specify the version to select which one.
1279	/// resolve.push_str(
1280	/// "./my-test.wit",
1281	/// r#"
1282	/// package example:wit5@2.0.0;
1283	///
1284	/// world foo { /* ... */ }
1285	/// "#,
1286	/// )?;
1287	/// assert!(resolve.select_world(id, Some("example:wit5/foo")).is_err());
1288	/// assert!(resolve.select_world(id, Some("example:wit5/foo@1.0.0")).is_ok());
1289	/// assert!(resolve.select_world(id, Some("example:wit5/foo@2.0.0")).is_ok());
1290	///
1291	/// Ok(())
1292	/// }
1293	/// ```
1294	pub fn select_world(&self, package: PackageId, world: Option<&str>) -> Result<WorldId> {
1295	let world_path = match world {
1296	Some(world) => Some(
1297	parse_use_path(world)
1298	.with_context(\|\| format!("failed to parse world specifier `{world}`"))?,
1299	),
1300	None => None,
1301	};
1302
1303	let (pkg, world_name) = match world_path {
1304	Some(ParsedUsePath::Name(name)) => (package, name),
1305	Some(ParsedUsePath::Package(pkg, interface)) => {
1306	let pkg = match self.package_names.get(&pkg) {
1307	Some(pkg) => *pkg,
1308	None => {
1309	let mut candidates = self.package_names.iter().filter(\|(name, _)\| {
1310	pkg.version.is_none()
1311	&& pkg.name == name.name
1312	&& pkg.namespace == name.namespace
1313	&& name.version.is_some()
1314	});
1315	let candidate = candidates.next();
1316	if let Some((c2, _)) = candidates.next() {
1317	let (c1, _) = candidate.unwrap();
1318	bail!(
1319	"package name `{pkg}` is available at both \
1320	versions {} and {} but which is not specified",
1321	c1.version.as_ref().unwrap(),
1322	c2.version.as_ref().unwrap(),
1323	);
1324	}
1325	match candidate {
1326	Some((_, id)) => *id,
1327	None => bail!("unknown package `{pkg}`"),
1328	}
1329	}
1330	};
1331	(pkg, interface.to_string())
1332	}
1333	None => {
1334	let pkg = &self.packages[package];
1335	let worlds = pkg
1336	.worlds
1337	.values()
1338	.map(\|world\| (package, *world))
1339	.collect::<Vec<_>>();
1340
1341	match &worlds[..] {
1342	[] => bail!("The main package `{}` contains no worlds", pkg.name),
1343	[(_, world)] => return Ok(*world),
1344	_ => bail!(
1345	"multiple worlds found; one must be explicitly chosen:{}",
1346	worlds
1347	.iter()
1348	.map(\|(pkg, world)\| format!(
1349	"`\n` {}/{}",
1350	self.packages[pkg].name, self.worlds[world].name
1351	))
1352	.collect::<String>()
1353	),
1354	}
1355	}
1356	};
1357	let pkg = &self.packages[pkg];
1358	pkg.worlds
1359	.get(&world_name)
1360	.copied()
1361	.ok_or_else(\|\| anyhow!("no world named `{world_name}` in package"))
1362	}
1363
1364	/// Assigns a human readable name to the `WorldKey` specified.
1365	pub fn name_world_key(&self, key: &WorldKey) -> String {
1366	match key {
1367	WorldKey::Name(s) => s.to_string(),
1368	WorldKey::Interface(i) => self.id_of(*i).expect("unexpected anonymous interface"),
1369	}
1370	}
1371
1372	/// Same as [`Resolve::name_world_key`] except that `WorldKey::Interfaces`
1373	/// uses [`Resolve::canonicalized_id_of`].
1374	pub fn name_canonicalized_world_key(&self, key: &WorldKey) -> String {
1375	match key {
1376	WorldKey::Name(s) => s.to_string(),
1377	WorldKey::Interface(i) => self
1378	.canonicalized_id_of(*i)
1379	.expect("unexpected anonymous interface"),
1380	}
1381	}
1382
1383	/// Returns the interface that `id` uses a type from, if it uses a type from
1384	/// a different interface than `id` is defined within.
1385	///
1386	/// If `id` is not a use-of-a-type or it's using a type in the same
1387	/// interface then `None` is returned.
1388	pub fn type_interface_dep(&self, id: TypeId) -> Option<InterfaceId> {
1389	let ty = &self.types[id];
1390	let dep = match ty.kind {
1391	TypeDefKind::Type(Type::Id(id)) => id,
1392	_ => return None,
1393	};
1394	let other = &self.types[dep];
1395	if ty.owner == other.owner {
1396	None
1397	} else {
1398	match other.owner {
1399	TypeOwner::Interface(id) => Some(id),
1400	_ => unreachable!(),
1401	}
1402	}
1403	}
1404
1405	/// Returns an iterator of all interfaces that the interface `id` depends
1406	/// on.
1407	///
1408	/// Interfaces may depend on others for type information to resolve type
1409	/// imports.
1410	///
1411	/// Note that the returned iterator may yield the same interface as a
1412	/// dependency multiple times. Additionally only direct dependencies of `id`
1413	/// are yielded, not transitive dependencies.
1414	pub fn interface_direct_deps(&self, id: InterfaceId) -> impl Iterator<Item = InterfaceId> + '_ {
1415	self.interfaces[id]
1416	.types
1417	.iter()
1418	.filter_map(move \|(_name, ty)\| self.type_interface_dep(*ty))
1419	}
1420
1421	/// Returns an iterator of all packages that the package `id` depends
1422	/// on.
1423	///
1424	/// Packages may depend on others for type information to resolve type
1425	/// imports or interfaces to resolve worlds.
1426	///
1427	/// Note that the returned iterator may yield the same package as a
1428	/// dependency multiple times. Additionally only direct dependencies of `id`
1429	/// are yielded, not transitive dependencies.
1430	pub fn package_direct_deps(&self, id: PackageId) -> impl Iterator<Item = PackageId> + '_ {
1431	let pkg = &self.packages[id];
1432
1433	pkg.interfaces
1434	.iter()
1435	.flat_map(move \|(_name, id)\| self.interface_direct_deps(*id))
1436	.chain(pkg.worlds.iter().flat_map(move \|(_name, id)\| {
1437	let world = &self.worlds[*id];
1438	world
1439	.imports
1440	.iter()
1441	.chain(world.exports.iter())
1442	.filter_map(move \|(_name, item)\| match item {
1443	WorldItem::Interface { id, .. } => Some(*id),
1444	WorldItem::Function(_) => None,
1445	WorldItem::Type(t) => self.type_interface_dep(*t),
1446	})
1447	}))
1448	.filter_map(move \|iface_id\| {
1449	let pkg = self.interfaces[iface_id].package?;
1450	if pkg == id {
1451	None
1452	} else {
1453	Some(pkg)
1454	}
1455	})
1456	}
1457
1458	/// Returns a topological ordering of packages contained in this `Resolve`.
1459	///
1460	/// This returns a list of `PackageId` such that when visited in order it's
1461	/// guaranteed that all dependencies will have been defined by prior items
1462	/// in the list.
1463	pub fn topological_packages(&self) -> Vec<PackageId> {
1464	let mut pushed = vec![`false`; self.packages.len()];
1465	let mut order = Vec::new();
1466	for (id, _) in self.packages.iter() {
1467	self.build_topological_package_ordering(id, &mut pushed, &mut order);
1468	}
1469	order
1470	}
1471
1472	fn build_topological_package_ordering(
1473	&self,
1474	id: PackageId,
1475	pushed: &mut Vec<bool>,
1476	order: &mut Vec<PackageId>,
1477	) {
1478	if pushed[id.index()] {
1479	return;
1480	}
1481	for dep in self.package_direct_deps(id) {
1482	self.build_topological_package_ordering(dep, pushed, order);
1483	}
1484	order.push(id);
1485	pushed[id.index()] = `true`;
1486	}
1487
1488	#[doc(hidden)]
1489	pub fn assert_valid(&self) {
1490	let mut package_interfaces = Vec::new();
1491	let mut package_worlds = Vec::new();
1492	for (id, pkg) in self.packages.iter() {
1493	let mut interfaces = HashSet::new();
1494	for (name, iface) in pkg.interfaces.iter() {
1495	assert!(interfaces.insert(*iface));
1496	let iface = &self.interfaces[*iface];
1497	assert_eq!(name, iface.name.as_ref().unwrap());
1498	assert_eq!(iface.package.unwrap(), id);
1499	}
1500	package_interfaces.push(pkg.interfaces.values().copied().collect::<HashSet<_>>());
1501	let mut worlds = HashSet::new();
1502	for (name, world) in pkg.worlds.iter() {
1503	assert!(worlds.insert(*world));
1504	assert_eq!(
1505	pkg.worlds.get_key_value(name),
1506	Some((name, world)),
1507	"`MutableKeys` impl may have been used to change a key's hash or equality"
1508	);
1509	let world = &self.worlds[*world];
1510	assert_eq!(*name, world.name);
1511	assert_eq!(world.package.unwrap(), id);
1512	}
1513	package_worlds.push(pkg.worlds.values().copied().collect::<HashSet<_>>());
1514	}
1515
1516	let mut interface_types = Vec::new();
1517	for (id, iface) in self.interfaces.iter() {
1518	assert!(self.packages.get(iface.package.unwrap()).is_some());
1519	if iface.name.is_some() {
1520	assert!(package_interfaces[iface.package.unwrap().index()].contains(&id));
1521	}
1522
1523	for (name, ty) in iface.types.iter() {
1524	let ty = &self.types[*ty];
1525	assert_eq!(ty.name.as_ref(), Some(name));
1526	assert_eq!(ty.owner, TypeOwner::Interface(id));
1527	}
1528	interface_types.push(iface.types.values().copied().collect::<HashSet<_>>());
1529	for (name, f) in iface.functions.iter() {
1530	assert_eq!(*name, f.name);
1531	}
1532	}
1533
1534	let mut world_types = Vec::new();
1535	for (id, world) in self.worlds.iter() {
1536	log::debug!("validating world {}", &world.name);
1537	if let Some(package) = world.package {
1538	assert!(self.packages.get(package).is_some());
1539	assert!(package_worlds[package.index()].contains(&id));
1540	}
1541	assert!(world.includes.is_empty());
1542
1543	let mut types = HashSet::new();
1544	for (name, item) in world.imports.iter().chain(world.exports.iter()) {
1545	log::debug!("validating world item: {}", self.name_world_key(name));
1546	match item {
1547	WorldItem::Interface { id, .. } => {
1548	// anonymous interfaces must belong to the same package
1549	// as the world's package.
1550	if matches!(name, WorldKey::Name(_)) {
1551	assert_eq!(self.interfaces[*id].package, world.package);
1552	}
1553	}
1554	WorldItem::Function(f) => {
1555	assert!(!matches!(name, WorldKey::Interface(_)));
1556	assert_eq!(f.name, name.clone().unwrap_name());
1557	}
1558	WorldItem::Type(ty) => {
1559	assert!(!matches!(name, WorldKey::Interface(_)));
1560	assert!(types.insert(*ty));
1561	let ty = &self.types[*ty];
1562	assert_eq!(ty.name, Some(name.clone().unwrap_name()));
1563	assert_eq!(ty.owner, TypeOwner::World(id));
1564	}
1565	}
1566	}
1567	self.assert_world_elaborated(world);
1568	world_types.push(types);
1569	}
1570
1571	for (ty_id, ty) in self.types.iter() {
1572	match ty.owner {
1573	TypeOwner::Interface(id) => {
1574	assert!(self.interfaces.get(id).is_some());
1575	assert!(interface_types[id.index()].contains(&ty_id));
1576	}
1577	TypeOwner::World(id) => {
1578	assert!(self.worlds.get(id).is_some());
1579	assert!(world_types[id.index()].contains(&ty_id));
1580	}
1581	TypeOwner::None => {}
1582	}
1583	}
1584
1585	self.assert_topologically_sorted();
1586	}
1587
1588	fn assert_topologically_sorted(&self) {
1589	let mut positions = IndexMap::new();
1590	for id in self.topological_packages() {
1591	let pkg = &self.packages[id];
1592	log::debug!("pkg {}", pkg.name);
1593	let prev = positions.insert(Some(id), IndexSet::new());
1594	assert!(prev.is_none());
1595	}
1596	positions.insert(None, IndexSet::new());
1597
1598	for (id, iface) in self.interfaces.iter() {
1599	log::debug!("iface {:?}", iface.name);
1600	let ok = positions.get_mut(&iface.package).unwrap().insert(id);
1601	assert!(ok);
1602	}
1603
1604	for (_, world) in self.worlds.iter() {
1605	log::debug!("world {:?}", world.name);
1606
1607	let my_package = world.package;
1608	let my_package_pos = positions.get_index_of(&my_package).unwrap();
1609
1610	for (_, item) in world.imports.iter().chain(&world.exports) {
1611	let id = match item {
1612	WorldItem::Interface { id, .. } => *id,
1613	_ => continue,
1614	};
1615	let other_package = self.interfaces[id].package;
1616	let other_package_pos = positions.get_index_of(&other_package).unwrap();
1617
1618	assert!(other_package_pos <= my_package_pos);
1619	}
1620	}
1621
1622	for (_id, ty) in self.types.iter() {
1623	log::debug!("type {:?} {:?}", ty.name, ty.owner);
1624	let other_id = match ty.kind {
1625	TypeDefKind::Type(Type::Id(ty)) => ty,
1626	_ => continue,
1627	};
1628	let other = &self.types[other_id];
1629	if ty.kind == other.kind {
1630	continue;
1631	}
1632	let my_interface = match ty.owner {
1633	TypeOwner::Interface(id) => id,
1634	_ => continue,
1635	};
1636	let other_interface = match other.owner {
1637	TypeOwner::Interface(id) => id,
1638	_ => continue,
1639	};
1640
1641	let my_package = self.interfaces[my_interface].package;
1642	let other_package = self.interfaces[other_interface].package;
1643	let my_package_pos = positions.get_index_of(&my_package).unwrap();
1644	let other_package_pos = positions.get_index_of(&other_package).unwrap();
1645
1646	if my_package_pos == other_package_pos {
1647	let interfaces = &positions[&my_package];
1648	let my_interface_pos = interfaces.get_index_of(&my_interface).unwrap();
1649	let other_interface_pos = interfaces.get_index_of(&other_interface).unwrap();
1650	assert!(other_interface_pos <= my_interface_pos);
1651	} else {
1652	assert!(other_package_pos < my_package_pos);
1653	}
1654	}
1655	}
1656
1657	fn assert_world_elaborated(&self, world: &World) {
1658	for (key, item) in world.imports.iter() {
1659	log::debug!(
1660	"asserting elaborated world import {}",
1661	self.name_world_key(key)
1662	);
1663	match item {
1664	WorldItem::Type(t) => self.assert_world_imports_type_deps(world, key, *t),
1665
1666	// All types referred to must be imported.
1667	WorldItem::Function(f) => self.assert_world_function_imports_types(world, key, f),
1668
1669	// All direct dependencies of this interface must be imported.
1670	WorldItem::Interface { id, .. } => {
1671	for dep in self.interface_direct_deps(*id) {
1672	assert!(
1673	world.imports.contains_key(&WorldKey::Interface(dep)),
1674	"world import of {} is missing transitive dep of {}",
1675	self.name_world_key(key),
1676	self.id_of(dep).unwrap(),
1677	);
1678	}
1679	}
1680	}
1681	}
1682	for (key, item) in world.exports.iter() {
1683	log::debug!(
1684	"asserting elaborated world export {}",
1685	self.name_world_key(key)
1686	);
1687	match item {
1688	// Types referred to by this function must be imported.
1689	WorldItem::Function(f) => self.assert_world_function_imports_types(world, key, f),
1690
1691	// Dependencies of exported interfaces must also be exported, or
1692	// if imported then that entire chain of imports must be
1693	// imported and not exported.
1694	WorldItem::Interface { id, .. } => {
1695	for dep in self.interface_direct_deps(*id) {
1696	let dep_key = WorldKey::Interface(dep);
1697	if world.exports.contains_key(&dep_key) {
1698	continue;
1699	}
1700	self.foreach_interface_dep(dep, &mut \|dep\| {
1701	let dep_key = WorldKey::Interface(dep);
1702	assert!(
1703	world.imports.contains_key(&dep_key),
1704	"world should import {} (required by {})",
1705	self.name_world_key(&dep_key),
1706	self.name_world_key(key),
1707	);
1708	assert!(
1709	!world.exports.contains_key(&dep_key),
1710	"world should not export {} (required by {})",
1711	self.name_world_key(&dep_key),
1712	self.name_world_key(key),
1713	);
1714	});
1715	}
1716	}
1717
1718	// exported types not allowed at this time
1719	WorldItem::Type(_) => unreachable!(),
1720	}
1721	}
1722	}
1723
1724	fn assert_world_imports_type_deps(&self, world: &World, key: &WorldKey, ty: TypeId) {
1725	// If this is a `use` statement then the referred-to interface must be
1726	// imported into this world.
1727	let ty = &self.types[ty];
1728	if let TypeDefKind::Type(Type::Id(other)) = ty.kind {
1729	if let TypeOwner::Interface(id) = self.types[other].owner {
1730	let key = WorldKey::Interface(id);
1731	assert!(world.imports.contains_key(&key));
1732	return;
1733	}
1734	}
1735
1736	// ... otherwise any named type that this type refers to, one level
1737	// deep, must be imported into this world under that name.
1738
1739	let mut visitor = MyVisit(self, Vec::new());
1740	visitor.visit_type_def(self, ty);
1741	for ty in visitor.1 {
1742	let ty = &self.types[ty];
1743	let Some(name) = ty.name.clone() else {
1744	continue;
1745	};
1746	let dep_key = WorldKey::Name(name);
1747	assert!(
1748	world.imports.contains_key(&dep_key),
1749	"world import `{}` should also force an import of `{}`",
1750	self.name_world_key(key),
1751	self.name_world_key(&dep_key),
1752	);
1753	}
1754
1755	struct MyVisit<'a>(&'a Resolve, Vec<TypeId>);
1756
1757	impl TypeIdVisitor for MyVisit<'_> {
1758	fn before_visit_type_id(&mut self, id: TypeId) -> bool {
1759	self.1.push(id);
1760	// recurse into unnamed types to look at all named types
1761	self.0.types[id].name.is_none()
1762	}
1763	}
1764	}
1765
1766	/// This asserts that all types referred to by `func` are imported into
1767	/// `world` under `WorldKey::Name`. Note that this is only applicable to
1768	/// named type
1769	fn assert_world_function_imports_types(&self, world: &World, key: &WorldKey, func: &Function) {
1770	for ty in func
1771	.parameter_and_result_types()
1772	.chain(func.kind.resource().map(Type::Id))
1773	{
1774	let Type::Id(id) = ty else {
1775	continue;
1776	};
1777	self.assert_world_imports_type_deps(world, key, id);
1778	}
1779	}
1780
1781	fn include_stability(&self, stability: &Stability, pkg_id: &PackageId) -> Result<bool> {
1782	Ok(match stability {
1783	Stability::Unknown => `true`,
1784	// NOTE: deprecations are intentionally omitted -- an existing `@since` takes precedence over `@deprecated`
1785	Stability::Stable { since, .. } => {
1786	let Some(p) = self.packages.get(pkg_id) else* {
1787	// We can't check much without a package (possibly dealing with an item in an `UnresolvedPackage`),
1788	// @since version & deprecations can't be checked because there's no package version to compare to.
1789	//
1790	// Feature requirements on stabilized features are ignored in resolved packages, so we do the same here.
1791	return Ok(`true`);
1792	};
1793
1794	// Use of feature gating with version specifiers inside a package that is not versioned is not allowed
1795	let package_version = p.name.version.as_ref().with_context(\|\| format!("package [{}] contains a feature gate with a version specifier, so it must have a version", p.name))?;
1796
1797	// If the version on the feature gate is:
1798	// - released, then we can include it
1799	// - unreleased, then we must check the feature (if present)
1800	ensure!(
1801	since <= package_version,
1802	"feature gate cannot reference unreleased version {since} of package [{}] (current version {package_version})",
1803	p.name
1804	);
1805
1806	`true`
1807	}
1808	Stability::Unstable { feature, .. } => {
1809	self.features.contains(feature) \|\| self.all_features
1810	}
1811	})
1812	}
1813
1814	/// Performs the "elaboration process" necessary for the `world_id`
1815	/// specified to ensure that all of its transitive imports are listed.
1816	///
1817	/// This function will take the unordered lists of the specified world's
1818	/// imports and exports and "elaborate" them to ensure that they're
1819	/// topographically sorted where all transitively required interfaces by
1820	/// imports, or exports, are listed. This will additionally validate that
1821	/// the exports are all valid and present, specifically with the restriction
1822	/// noted on `elaborate_world_exports`.
1823	///
1824	/// The world is mutated in-place in this `Resolve`.
1825	fn elaborate_world(&mut self, world_id: WorldId) -> Result<()> {
1826	// First process all imports. This is easier than exports since the only
1827	// requirement here is that all interfaces need to be added with a
1828	// topological order between them.
1829	let mut new_imports = IndexMap::new();
1830	let world = &self.worlds[world_id];
1831	for (name, item) in world.imports.iter() {
1832	match item {
1833	// Interfaces get their dependencies added first followed by the
1834	// interface itself.
1835	WorldItem::Interface { id, stability } => {
1836	self.elaborate_world_import(&mut new_imports, name.clone(), *id, &stability);
1837	}
1838
1839	// Functions are added as-is since their dependence on types in
1840	// the world should already be satisfied.
1841	WorldItem::Function(_) => {
1842	let prev = new_imports.insert(name.clone(), item.clone());
1843	assert!(prev.is_none());
1844	}
1845
1846	// Types may depend on an interface, in which case a (possibly)
1847	// recursive addition of that interface happens here. Afterwards
1848	// the type itself can be added safely.
1849	WorldItem::Type(id) => {
1850	if let Some(dep) = self.type_interface_dep(*id) {
1851	self.elaborate_world_import(
1852	&mut new_imports,
1853	WorldKey::Interface(dep),
1854	dep,
1855	&self.types[*id].stability,
1856	);
1857	}
1858	let prev = new_imports.insert(name.clone(), item.clone());
1859	assert!(prev.is_none());
1860	}
1861	}
1862	}
1863
1864	// Exports are trickier than imports, notably to uphold the invariant
1865	// required by `elaborate_world_exports`. To do this the exports are
1866	// partitioned into interfaces/functions. All functions are added to
1867	// the new exports list during this loop but interfaces are all deferred
1868	// to be handled in the `elaborate_world_exports` function.
1869	let mut new_exports = IndexMap::new();
1870	let mut export_interfaces = IndexMap::new();
1871	for (name, item) in world.exports.iter() {
1872	match item {
1873	WorldItem::Interface { id, stability } => {
1874	let prev = export_interfaces.insert(*id, (name.clone(), stability));
1875	assert!(prev.is_none());
1876	}
1877	WorldItem::Function(_) => {
1878	let prev = new_exports.insert(name.clone(), item.clone());
1879	assert!(prev.is_none());
1880	}
1881	WorldItem::Type(_) => unreachable!(),
1882	}
1883	}
1884
1885	self.elaborate_world_exports(&export_interfaces, &mut new_imports, &mut new_exports)?;
1886
1887	// And with all that done the world is updated in-place with
1888	// imports/exports.
1889	log::trace!("imports = {:?}", new_imports);
1890	log::trace!("exports = {:?}", new_exports);
1891	let world = &mut self.worlds[world_id];
1892	world.imports = new_imports;
1893	world.exports = new_exports;
1894
1895	Ok(())
1896	}
1897
1898	fn elaborate_world_import(
1899	&self,
1900	imports: &mut IndexMap<WorldKey, WorldItem>,
1901	key: WorldKey,
1902	id: InterfaceId,
1903	stability: &Stability,
1904	) {
1905	if imports.contains_key(&key) {
1906	return;
1907	}
1908	for dep in self.interface_direct_deps(id) {
1909	self.elaborate_world_import(imports, WorldKey::Interface(dep), dep, stability);
1910	}
1911	let prev = imports.insert(
1912	key,
1913	WorldItem::Interface {
1914	id,
1915	stability: stability.clone(),
1916	},
1917	);
1918	assert!(prev.is_none());
1919	}
1920
1921	/// This function adds all of the interfaces in `export_interfaces` to the
1922	/// list of exports of the `world` specified.
1923	///
1924	/// This method is more involved than adding imports because it is fallible.
1925	/// Chiefly what can happen is that the dependencies of all exports must be
1926	/// satisfied by other exports or imports, but not both. For example given a
1927	/// situation such as:
1928	///
1929	/// ```wit
1930	/// interface a {
1931	/// type t = u32
1932	/// }
1933	/// interface b {
1934	/// use a.{t}
1935	/// }
1936	/// interface c {
1937	/// use a.{t}
1938	/// use b.{t as t2}
1939	/// }
1940	/// ```
1941	///
1942	/// where `c` depends on `b` and `a` where `b` depends on `a`, then the
1943	/// purpose of this method is to reject this world:
1944	///
1945	/// ```wit
1946	/// world foo {
1947	/// export a
1948	/// export c
1949	/// }
1950	/// ```
1951	///
1952	/// The reasoning here is unfortunately subtle and is additionally the
1953	/// subject of WebAssembly/component-model#208. Effectively the `c`
1954	/// interface depends on `b`, but it's not listed explicitly as an import,
1955	/// so it's then implicitly added as an import. This then transitively
1956	/// depends on `a` so it's also added as an import. At this point though `c`
1957	/// also depends on `a`, and it's also exported, so naively it should depend
1958	/// on the export and not implicitly add an import. This means though that
1959	/// `c` has access to two copies of `a`, one imported and one exported. This
1960	/// is not valid, especially in the face of resource types.
1961	///
1962	/// Overall this method is tasked with rejecting the above world by walking
1963	/// over all the exports and adding their dependencies. Each dependency is
1964	/// recorded with whether it's required to be imported, and then if an
1965	/// export is added for something that's required to be an error then the
1966	/// operation fails.
1967	fn elaborate_world_exports(
1968	&self,
1969	export_interfaces: &IndexMap<InterfaceId, (WorldKey, &Stability)>,
1970	imports: &mut IndexMap<WorldKey, WorldItem>,
1971	exports: &mut IndexMap<WorldKey, WorldItem>,
1972	) -> Result<()> {
1973	let mut required_imports = HashSet::new();
1974	for (id, (key, stability)) in export_interfaces.iter() {
1975	let name = self.name_world_key(&key);
1976	let ok = add_world_export(
1977	self,
1978	imports,
1979	exports,
1980	export_interfaces,
1981	&mut required_imports,
1982	*id,
1983	key,
1984	`true`,
1985	stability,
1986	);
1987	if !ok {
1988	bail!(
1989	// FIXME: this is not a great error message and basically no
1990	// one will know what to do when it gets printed. Improving
1991	// this error message, however, is a chunk of work that may
1992	// not be best spent doing this at this time, so I'm writing
1993	// this comment instead.
1994	//
1995	// More-or-less what should happen here is that a "path"
1996	// from this interface to the conflicting interface should
1997	// be printed. It should be explained why an import is being
1998	// injected, why that's conflicting with an export, and
1999	// ideally with a suggestion of "add this interface to the
2000	// export list to fix this error".
2001	//
2002	// That's a lot of info that's not easy to get at without
2003	// more refactoring, so it's left to a future date in the
2004	// hopes that most folks won't actually run into this for
2005	// the time being.
2006	InvalidTransitiveDependency(name),
2007	);
2008	}
2009	}
2010	return Ok(());
2011
2012	fn add_world_export(
2013	resolve: &Resolve,
2014	imports: &mut IndexMap<WorldKey, WorldItem>,
2015	exports: &mut IndexMap<WorldKey, WorldItem>,
2016	export_interfaces: &IndexMap<InterfaceId, (WorldKey, &Stability)>,
2017	required_imports: &mut HashSet<InterfaceId>,
2018	id: InterfaceId,
2019	key: &WorldKey,
2020	add_export: bool,
2021	stability: &Stability,
2022	) -> bool {
2023	if exports.contains_key(key) {
2024	if add_export {
2025	return `true`;
2026	} else {
2027	return `false`;
2028	}
2029	}
2030	// If this is an import and it's already in the `required_imports`
2031	// set then we can skip it as we've already visited this interface.
2032	if !add_export && required_imports.contains(&id) {
2033	return `true`;
2034	}
2035	let ok = resolve.interface_direct_deps(id).all(\|dep\| {
2036	let key = WorldKey::Interface(dep);
2037	let add_export = add_export && export_interfaces.contains_key(&dep);
2038	add_world_export(
2039	resolve,
2040	imports,
2041	exports,
2042	export_interfaces,
2043	required_imports,
2044	dep,
2045	&key,
2046	add_export,
2047	stability,
2048	)
2049	});
2050	if !ok {
2051	return `false`;
2052	}
2053	let item = WorldItem::Interface {
2054	id,
2055	stability: stability.clone(),
2056	};
2057	if add_export {
2058	if required_imports.contains(&id) {
2059	return `false`;
2060	}
2061	exports.insert(key.clone(), item);
2062	} else {
2063	required_imports.insert(id);
2064	imports.insert(key.clone(), item);
2065	}
2066	`true`
2067	}
2068	}
2069
2070	/// Remove duplicate imports from a world if they import from the same
2071	/// interface with semver-compatible versions.
2072	///
2073	/// This will merge duplicate interfaces present at multiple versions in
2074	/// both a world by selecting the larger version of the two interfaces. This
2075	/// requires that the interfaces are indeed semver-compatible and it means
2076	/// that some imports might be removed and replaced. Note that this is only
2077	/// done within a single semver track, for example the world imports 0.2.0
2078	/// and 0.2.1 then the result afterwards will be that it imports
2079	/// 0.2.1. If, however, 0.3.0 where imported then the final result would
2080	/// import both 0.2.0 and 0.3.0.
2081	pub fn merge_world_imports_based_on_semver(&mut self, world_id: WorldId) -> Result<()> {
2082	let world = &self.worlds[world_id];
2083
2084	// The first pass here is to build a map of "semver tracks" where they
2085	// key is per-interface and the value is the maximal version found in
2086	// that semver-compatible-track plus the interface which is the maximal
2087	// version.
2088	//
2089	// At the same time a `to_remove` set is maintained to remember what
2090	// interfaces are being removed from `from` and `into`. All of
2091	// `to_remove` are placed with a known other version.
2092	let mut semver_tracks = HashMap::new();
2093	let mut to_remove = HashSet::new();
2094	for (key, _) in world.imports.iter() {
2095	let iface_id = match key {
2096	WorldKey::Interface(id) => *id,
2097	WorldKey::Name(_) => continue,
2098	};
2099	let (track, version) = match self.semver_track(iface_id) {
2100	Some(track) => track,
2101	None => continue,
2102	};
2103	log::debug!(
2104	"{} is on track {}/{}",
2105	self.id_of(iface_id).unwrap(),
2106	track.0,
2107	track.1,
2108	);
2109	match semver_tracks.entry(track.clone()) {
2110	hash_map::Entry::Vacant(e) => {
2111	e.insert((version, iface_id));
2112	}
2113	hash_map::Entry::Occupied(mut e) => match version.cmp(&e.get().0) {
2114	Ordering::Greater => {
2115	to_remove.insert(e.get().1);
2116	e.insert((version, iface_id));
2117	}
2118	Ordering::Equal => {}
2119	Ordering::Less => {
2120	to_remove.insert(iface_id);
2121	}
2122	},
2123	}
2124	}
2125
2126	// Build a map of "this interface is replaced with this interface" using
2127	// the results of the loop above.
2128	let mut replacements = HashMap::new();
2129	for id in to_remove {
2130	let (track, _) = self.semver_track(id).unwrap();
2131	let (_, latest) = semver_tracks[&track];
2132	let prev = replacements.insert(id, latest);
2133	assert!(prev.is_none());
2134	}
2135
2136	// Validate that `merge_world_item` succeeds for merging all removed
2137	// interfaces with their replacement. This is a double-check that the
2138	// semver version is actually correct and all items present in the old
2139	// interface are in the new.
2140	for (to_replace, replace_with) in replacements.iter() {
2141	self.merge_world_item(
2142	&WorldItem::Interface {
2143	id: *to_replace,
2144	stability: Default::default(),
2145	},
2146	&WorldItem::Interface {
2147	id: *replace_with,
2148	stability: Default::default(),
2149	},
2150	)
2151	.with_context(\|\| {
2152	let old_name = self.id_of(*to_replace).unwrap();
2153	let new_name = self.id_of(*replace_with).unwrap();
2154	format!(
2155	"failed to upgrade `{old_name}` to `{new_name}`, was \
2156	this semver-compatible update not semver compatible?"
2157	)
2158	})?;
2159	}
2160
2161	for (to_replace, replace_with) in replacements.iter() {
2162	log::debug!(
2163	"REPLACE {} => {}",
2164	self.id_of(*to_replace).unwrap(),
2165	self.id_of(*replace_with).unwrap(),
2166	);
2167	}
2168
2169	// Finally perform the actual transformation of the imports/exports.
2170	// Here all imports are removed if they're replaced and otherwise all
2171	// imports have their dependencies updated, possibly transitively, to
2172	// point to the new interfaces in `replacements`.
2173	//
2174	// Afterwards exports are additionally updated, but only their
2175	// dependencies on imports which were remapped. Exports themselves are
2176	// not deduplicated and/or removed.
2177	for (key, item) in mem::take(&mut self.worlds[world_id].imports) {
2178	if let WorldItem::Interface { id, .. } = item {
2179	if replacements.contains_key(&id) {
2180	continue;
2181	}
2182	}
2183
2184	self.update_interface_deps_of_world_item(&item, &replacements);
2185
2186	let prev = self.worlds[world_id].imports.insert(key, item);
2187	assert!(prev.is_none());
2188	}
2189	for (key, item) in mem::take(&mut self.worlds[world_id].exports) {
2190	self.update_interface_deps_of_world_item(&item, &replacements);
2191	let prev = self.worlds[world_id].exports.insert(key, item);
2192	assert!(prev.is_none());
2193	}
2194
2195	// Run through `elaborate_world` to reorder imports as appropriate and
2196	// fill anything back in if it's actually required by exports. For now
2197	// this doesn't tamper with exports at all. Also note that this is
2198	// applied to all worlds in this `Resolve` because interfaces were
2199	// modified directly.
2200	let ids = self.worlds.iter().map(\|(id, _)\| id).collect::<Vec<_>>();
2201	for world_id in ids {
2202	self.elaborate_world(world_id).with_context(\|\| {
2203	let name = &self.worlds[world_id].name;
2204	format!(
2205	"failed to elaborate world `{name}` after deduplicating imports \
2206	based on semver"
2207	)
2208	})?;
2209	}
2210
2211	#[cfg(debug_assertions)]
2212	self.assert_valid();
2213
2214	Ok(())
2215	}
2216
2217	fn update_interface_deps_of_world_item(
2218	&mut self,
2219	item: &WorldItem,
2220	replacements: &HashMap<InterfaceId, InterfaceId>,
2221	) {
2222	match *item {
2223	WorldItem::Type(t) => self.update_interface_dep_of_type(t, &replacements),
2224	WorldItem::Interface { id, .. } => {
2225	let types = self.interfaces[id]
2226	.types
2227	.values()
2228	.copied()
2229	.collect::<Vec<_>>();
2230	for ty in types {
2231	self.update_interface_dep_of_type(ty, &replacements);
2232	}
2233	}
2234	WorldItem::Function(_) => {}
2235	}
2236	}
2237
2238	/// Returns the "semver track" of an interface plus the interface's version.
2239	///
2240	/// This function returns `None` if the interface `id` has a package without
2241	/// a version. If the version is present, however, the first element of the
2242	/// tuple returned is a "semver track" for the specific interface. The
2243	/// version listed in `PackageName` will be modified so all
2244	/// semver-compatible versions are listed the same way.
2245	///
2246	/// The second element in the returned tuple is this interface's package's
2247	/// version.
2248	fn semver_track(&self, id: InterfaceId) -> Option<((PackageName, String), &Version)> {
2249	let iface = &self.interfaces[id];
2250	let pkg = &self.packages[iface.package?];
2251	let version = pkg.name.version.as_ref()?;
2252	let mut name = pkg.name.clone();
2253	name.version = Some(PackageName::version_compat_track(version));
2254	Some(((name, iface.name.clone()?), version))
2255	}
2256
2257	/// If `ty` is a definition where it's a `use` from another interface, then
2258	/// change what interface it's using from according to the pairs in the
2259	/// `replacements` map.
2260	fn update_interface_dep_of_type(
2261	&mut self,
2262	ty: TypeId,
2263	replacements: &HashMap<InterfaceId, InterfaceId>,
2264	) {
2265	let to_replace = match self.type_interface_dep(ty) {
2266	Some(id) => id,
2267	None => return,
2268	};
2269	let replace_with = match replacements.get(&to_replace) {
2270	Some(id) => id,
2271	None => return,
2272	};
2273	let dep = match self.types[ty].kind {
2274	TypeDefKind::Type(Type::Id(id)) => id,
2275	_ => return,
2276	};
2277	let name = self.types[dep].name.as_ref().unwrap();
2278	// Note the infallible name indexing happening here. This should be
2279	// previously validated with `merge_world_item` to succeed.
2280	let replacement_id = self.interfaces[*replace_with].types[name];
2281	self.types[ty].kind = TypeDefKind::Type(Type::Id(replacement_id));
2282	}
2283
2284	/// Returns the core wasm module/field names for the specified `import`.
2285	///
2286	/// This function will return the core wasm module/field that can be used to
2287	/// use `import` with the name `mangling` scheme specified as well. This can
2288	/// be useful for bindings generators, for example, and these names are
2289	/// recognized by `wit-component` and `wasm-tools component new`.
2290	pub fn wasm_import_name(
2291	&self,
2292	mangling: ManglingAndAbi,
2293	import: WasmImport<'_>,
2294	) -> (String, String) {
2295	match mangling {
2296	ManglingAndAbi::Standard32 => match import {
2297	WasmImport::Func { interface, func } => {
2298	let module = match interface {
2299	Some(key) => format!("cm32p2\|{}", self.name_canonicalized_world_key(key)),
2300	None => format!("cm32p2"),
2301	};
2302	(module, func.name.clone())
2303	}
2304	WasmImport::ResourceIntrinsic {
2305	interface,
2306	resource,
2307	intrinsic,
2308	} => {
2309	let name = self.types[resource].name.as_ref().unwrap();
2310	let (prefix, name) = match intrinsic {
2311	ResourceIntrinsic::ImportedDrop => ("", format!("{name}_drop")),
2312	ResourceIntrinsic::ExportedDrop => ("_ex_", format!("{name}_drop")),
2313	ResourceIntrinsic::ExportedNew => ("_ex_", format!("{name}_new")),
2314	ResourceIntrinsic::ExportedRep => ("_ex_", format!("{name}_rep")),
2315	};
2316	let module = match interface {
2317	Some(key) => {
2318	format!("cm32p2\|{prefix}{}", self.name_canonicalized_world_key(key))
2319	}
2320	None => {
2321	assert_eq!(prefix, "");
2322	format!("cm32p2")
2323	}
2324	};
2325	(module, name)
2326	}
2327	},
2328	ManglingAndAbi::Legacy(abi) => match import {
2329	WasmImport::Func { interface, func } => {
2330	let module = match interface {
2331	Some(key) => self.name_world_key(key),
2332	None => format!("$root"),
2333	};
2334	(module, format!("{}{}", abi.import_prefix(), func.name))
2335	}
2336	WasmImport::ResourceIntrinsic {
2337	interface,
2338	resource,
2339	intrinsic,
2340	} => {
2341	let name = self.types[resource].name.as_ref().unwrap();
2342	let (prefix, name) = match intrinsic {
2343	ResourceIntrinsic::ImportedDrop => ("", format!("[resource-drop]{name}")),
2344	ResourceIntrinsic::ExportedDrop => {
2345	("[export]", format!("[resource-drop]{name}"))
2346	}
2347	ResourceIntrinsic::ExportedNew => {
2348	("[export]", format!("[resource-new]{name}"))
2349	}
2350	ResourceIntrinsic::ExportedRep => {
2351	("[export]", format!("[resource-rep]{name}"))
2352	}
2353	};
2354	let module = match interface {
2355	Some(key) => format!("{prefix}{}", self.name_world_key(key)),
2356	None => {
2357	assert_eq!(prefix, "");
2358	format!("$root")
2359	}
2360	};
2361	(module, format!("{}{name}", abi.import_prefix()))
2362	}
2363	},
2364	}
2365	}
2366
2367	/// Returns the core wasm export name for the specified `export`.
2368	///
2369	/// This is the same as [`Resolve::wasm_import_name`], except for exports.
2370	pub fn wasm_export_name(&self, mangling: ManglingAndAbi, export: WasmExport<'_>) -> String {
2371	match mangling {
2372	ManglingAndAbi::Standard32 => match export {
2373	WasmExport::Func {
2374	interface,
2375	func,
2376	kind,
2377	} => {
2378	let mut name = String::from("cm32p2\|");
2379	if let Some(interface) = interface {
2380	let s = self.name_canonicalized_world_key(interface);
2381	name.push_str(&s);
2382	}
2383	name.push_str("\|");
2384	name.push_str(&func.name);
2385	match kind {
2386	WasmExportKind::Normal => {}
2387	WasmExportKind::PostReturn => name.push_str("_post"),
2388	WasmExportKind::Callback => todo!(
2389	"not yet supported: \
2390	async callback functions using standard name mangling"
2391	),
2392	}
2393	name
2394	}
2395	WasmExport::ResourceDtor {
2396	interface,
2397	resource,
2398	} => {
2399	let name = self.types[resource].name.as_ref().unwrap();
2400	let interface = self.name_canonicalized_world_key(interface);
2401	format!("cm32p2\|{interface}\|{name}_dtor")
2402	}
2403	WasmExport::Memory => "cm32p2_memory".to_string(),
2404	WasmExport::Initialize => "cm32p2_initialize".to_string(),
2405	WasmExport::Realloc => "cm32p2_realloc".to_string(),
2406	},
2407	ManglingAndAbi::Legacy(abi) => match export {
2408	WasmExport::Func {
2409	interface,
2410	func,
2411	kind,
2412	} => {
2413	let mut name = abi.export_prefix().to_string();
2414	match kind {
2415	WasmExportKind::Normal => {}
2416	WasmExportKind::PostReturn => name.push_str("cabi_post_"),
2417	WasmExportKind::Callback => {
2418	assert!(matches!(abi, LiftLowerAbi::AsyncCallback));
2419	name = format!("[callback]{name}")
2420	}
2421	}
2422	if let Some(interface) = interface {
2423	let s = self.name_world_key(interface);
2424	name.push_str(&s);
2425	name.push_str("#");
2426	}
2427	name.push_str(&func.name);
2428	name
2429	}
2430	WasmExport::ResourceDtor {
2431	interface,
2432	resource,
2433	} => {
2434	let name = self.types[resource].name.as_ref().unwrap();
2435	let interface = self.name_world_key(interface);
2436	format!("{}{interface}#[dtor]{name}", abi.export_prefix())
2437	}
2438	WasmExport::Memory => "memory".to_string(),
2439	WasmExport::Initialize => "_initialize".to_string(),
2440	WasmExport::Realloc => "cabi_realloc".to_string(),
2441	},
2442	}
2443	}
2444	}
2445
2446	/// Possible imports that can be passed to [`Resolve::wasm_import_name`].
2447	#[derive(Debug)]
2448	pub enum WasmImport<'a> {
2449	/// A WIT function is being imported. Optionally from an interface.
2450	Func {
2451	/// The name of the interface that the function is being imported from.
2452	///
2453	/// If the function is imported directly from the world then this is
2454	/// `Noen`.
2455	interface: Option<&'a WorldKey>,
2456
2457	/// The function being imported.
2458	func: &'a Function,
2459	},
2460
2461	/// A resource-related intrinsic is being imported.
2462	ResourceIntrinsic {
2463	/// The optional interface to import from, same as `WasmImport::Func`.
2464	interface: Option<&'a WorldKey>,
2465
2466	/// The resource that's being operated on.
2467	resource: TypeId,
2468
2469	/// The intrinsic that's being imported.
2470	intrinsic: ResourceIntrinsic,
2471	},
2472	}
2473
2474	/// Intrinsic definitions to go with [`WasmImport::ResourceIntrinsic`] which
2475	/// also goes with [`Resolve::wasm_import_name`].
2476	#[derive(Debug)]
2477	pub enum ResourceIntrinsic {
2478	ImportedDrop,
2479	ExportedDrop,
2480	ExportedNew,
2481	ExportedRep,
2482	}
2483
2484	/// Indicates whether a function export is a normal export, a post-return
2485	/// function, or a callback function.
2486	#[derive(Debug)]
2487	pub enum WasmExportKind {
2488	/// Normal function export.
2489	Normal,
2490
2491	/// Post-return function.
2492	PostReturn,
2493
2494	/// Async callback function.
2495	Callback,
2496	}
2497
2498	/// Different kinds of exports that can be passed to
2499	/// [`Resolve::wasm_export_name`] to export from core wasm modules.
2500	#[derive(Debug)]
2501	pub enum WasmExport<'a> {
2502	/// A WIT function is being exported, optionally from an interface.
2503	Func {
2504	/// An optional interface which owns `func`. Use `None` for top-level
2505	/// world function.
2506	interface: Option<&'a WorldKey>,
2507
2508	/// The function being exported.
2509	func: &'a Function,
2510
2511	/// Kind of function (normal, post-return, or callback) being exported.
2512	kind: WasmExportKind,
2513	},
2514
2515	/// A destructor for a resource exported from this module.
2516	ResourceDtor {
2517	/// The interface that owns the resource.
2518	interface: &'a WorldKey,
2519	/// The resource itself that the destructor is for.
2520	resource: TypeId,
2521	},
2522
2523	/// Linear memory, the one that the canonical ABI uses.
2524	Memory,
2525
2526	/// An initialization function (not the core wasm `start`).
2527	Initialize,
2528
2529	/// The general-purpose realloc hook.
2530	Realloc,
2531	}
2532
2533	/// Structure returned by [`Resolve::merge`] which contains mappings from
2534	/// old-ids to new-ids after the merge.
2535	#[derive(Default)]
2536	pub struct Remap {
2537	pub types: Vec<Option<TypeId>>,
2538	pub interfaces: Vec<Option<InterfaceId>>,
2539	pub worlds: Vec<Option<WorldId>>,
2540	pub packages: Vec<PackageId>,
2541
2542	/// A cache of anonymous `own<T>` handles for resource types.
2543	///
2544	/// The appending operation of `Remap` is the one responsible for
2545	/// translating references to `T` where `T` is a resource into `own<T>`
2546	/// instead. This map is used to deduplicate the `own<T>` types generated
2547	/// to generate as few as possible.
2548	///
2549	/// The key of this map is the resource id `T` in the new resolve, and
2550	/// the value is the `own<T>` type pointing to `T`.
2551	own_handles: HashMap<TypeId, TypeId>,
2552
2553	type_has_borrow: Vec<Option<bool>>,
2554	}
2555
2556	fn apply_map<T>(map: &[Option<Id<T>>], id: Id<T>, desc: &str, span: Option<Span>) -> Result<Id<T>> {
2557	match map.get(id.index()) {
2558	Some(Some(id: &Id)) => Ok(*id),
2559	Some(None) => {
2560	let msg: String = format!(
2561	"found a reference to a {desc} which is excluded \
2562	due to its feature not being activated"
2563	);
2564	match span {
2565	Some(span: Span) => Err(Error::new(span, msg).into()),
2566	None => bail!("{msg}"),
2567	}
2568	}
2569	None => panic!("request to remap a {desc} that has not yet been registered"),
2570	}
2571	}
2572
2573	impl Remap {
2574	pub fn map_type(&self, id: TypeId, span: Option<Span>) -> Result<TypeId> {
2575	apply_map(&self.types, id, "type", span)
2576	}
2577
2578	pub fn map_interface(&self, id: InterfaceId, span: Option<Span>) -> Result<InterfaceId> {
2579	apply_map(&self.interfaces, id, "interface", span)
2580	}
2581
2582	pub fn map_world(&self, id: WorldId, span: Option<Span>) -> Result<WorldId> {
2583	apply_map(&self.worlds, id, "world", span)
2584	}
2585
2586	fn append(
2587	&mut self,
2588	resolve: &mut Resolve,
2589	unresolved: UnresolvedPackage,
2590	) -> Result<PackageId> {
2591	self.process_foreign_deps(resolve, &unresolved)?;
2592
2593	let foreign_types = self.types.len();
2594	let foreign_interfaces = self.interfaces.len();
2595	let foreign_worlds = self.worlds.len();
2596
2597	let pkgid = resolve.packages.alloc(Package {
2598	name: unresolved.name.clone(),
2599	docs: unresolved.docs.clone(),
2600	interfaces: Default::default(),
2601	worlds: Default::default(),
2602	});
2603	let prev = resolve.package_names.insert(unresolved.name.clone(), pkgid);
2604	assert!(prev.is_none());
2605
2606	// Copy over all types first, updating any intra-type references. Note
2607	// that types are sorted topologically which means this iteration
2608	// order should be sufficient. Also note though that the interface
2609	// owner of a type isn't updated here due to interfaces not being known
2610	// yet.
2611	assert_eq!(unresolved.types.len(), unresolved.type_spans.len());
2612	for ((id, mut ty), span) in unresolved
2613	.types
2614	.into_iter()
2615	.zip(&unresolved.type_spans)
2616	.skip(foreign_types)
2617	{
2618	if !resolve
2619	.include_stability(&ty.stability, &pkgid)
2620	.with_context(\|\| {
2621	format!(
2622	"failed to process feature gate for type [{}] in package [{}]",
2623	ty.name.as_ref().map(String::as_str).unwrap_or("<unknown>"),
2624	resolve.packages[pkgid].name,
2625	)
2626	})?
2627	{
2628	self.types.push(None);
2629	continue;
2630	}
2631
2632	self.update_typedef(resolve, &mut ty, Some(*span))?;
2633	let new_id = resolve.types.alloc(ty);
2634	assert_eq!(self.types.len(), id.index());
2635
2636	let new_id = match resolve.types[new_id] {
2637	// If this is an `own<T>` handle then either replace it with a
2638	// preexisting `own<T>` handle which may have been generated in
2639	// `update_ty`. If that doesn't exist though then insert it into
2640	// the `own_handles` cache.
2641	TypeDef {
2642	name: None,
2643	owner: TypeOwner::None,
2644	kind: TypeDefKind::Handle(Handle::Own(id)),
2645	docs: _,
2646	stability: _,
2647	} => *self.own_handles.entry(id).or_insert(new_id),
2648
2649	// Everything not-related to `own<T>` doesn't get its ID
2650	// modified.
2651	_ => new_id,
2652	};
2653	self.types.push(Some(new_id));
2654	}
2655
2656	// Next transfer all interfaces into `Resolve`, updating type ids
2657	// referenced along the way.
2658	assert_eq!(
2659	unresolved.interfaces.len(),
2660	unresolved.interface_spans.len()
2661	);
2662	for ((id, mut iface), span) in unresolved
2663	.interfaces
2664	.into_iter()
2665	.zip(&unresolved.interface_spans)
2666	.skip(foreign_interfaces)
2667	{
2668	if !resolve
2669	.include_stability(&iface.stability, &pkgid)
2670	.with_context(\|\| {
2671	format!(
2672	"failed to process feature gate for interface [{}] in package [{}]",
2673	iface
2674	.name
2675	.as_ref()
2676	.map(String::as_str)
2677	.unwrap_or("<unknown>"),
2678	resolve.packages[pkgid].name,
2679	)
2680	})?
2681	{
2682	self.interfaces.push(None);
2683	continue;
2684	}
2685	assert!(iface.package.is_none());
2686	iface.package = Some(pkgid);
2687	self.update_interface(resolve, &mut iface, Some(span))?;
2688	let new_id = resolve.interfaces.alloc(iface);
2689	assert_eq!(self.interfaces.len(), id.index());
2690	self.interfaces.push(Some(new_id));
2691	}
2692
2693	// Now that interfaces are identified go back through the types and
2694	// update their interface owners.
2695	for (i, id) in self.types.iter().enumerate().skip(foreign_types) {
2696	let id = match id {
2697	Some(id) => *id,
2698	None => continue,
2699	};
2700	match &mut resolve.types[id].owner {
2701	TypeOwner::Interface(id) => {
2702	let span = unresolved.type_spans[i];
2703	id = self.map_interface(id, Some(span))
2704	.with_context(\|\| {
2705	"this type is not gated by a feature but its interface is gated by a feature"
2706	})?;
2707	}
2708	TypeOwner::World(_) \| TypeOwner::None => {}
2709	}
2710	}
2711
2712	// Perform a weighty step of full resolution of worlds. This will fully
2713	// expand imports/exports for a world and create the topological
2714	// ordering necessary for this.
2715	//
2716	// This is done after types/interfaces are fully settled so the
2717	// transitive relation between interfaces, through types, is understood
2718	// here.
2719	assert_eq!(unresolved.worlds.len(), unresolved.world_spans.len());
2720	for ((id, mut world), span) in unresolved
2721	.worlds
2722	.into_iter()
2723	.zip(&unresolved.world_spans)
2724	.skip(foreign_worlds)
2725	{
2726	if !resolve
2727	.include_stability(&world.stability, &pkgid)
2728	.with_context(\|\| {
2729	format!(
2730	"failed to process feature gate for world [{}] in package [{}]",
2731	world.name, resolve.packages[pkgid].name,
2732	)
2733	})?
2734	{
2735	self.worlds.push(None);
2736	continue;
2737	}
2738	self.update_world(&mut world, resolve, &pkgid, &span)?;
2739
2740	let new_id = resolve.worlds.alloc(world);
2741	assert_eq!(self.worlds.len(), id.index());
2742	self.worlds.push(Some(new_id));
2743
2744	resolve.elaborate_world(new_id).with_context(\|\| {
2745	Error::new(
2746	span.span,
2747	format!(
2748	"failed to elaborate world imports/exports of `{}`",
2749	resolve.worlds[new_id].name
2750	),
2751	)
2752	})?;
2753	}
2754
2755	// As with interfaces, now update the ids of world-owned types.
2756	for (i, id) in self.types.iter().enumerate().skip(foreign_types) {
2757	let id = match id {
2758	Some(id) => *id,
2759	None => continue,
2760	};
2761	match &mut resolve.types[id].owner {
2762	TypeOwner::World(id) => {
2763	let span = unresolved.type_spans[i];
2764	id = self.map_world(id, Some(span))
2765	.with_context(\|\| {
2766	"this type is not gated by a feature but its interface is gated by a feature"
2767	})?;
2768	}
2769	TypeOwner::Interface(_) \| TypeOwner::None => {}
2770	}
2771	}
2772
2773	// Fixup "parent" ids now that everything has been identified
2774	for id in self.interfaces.iter().skip(foreign_interfaces) {
2775	let id = match id {
2776	Some(id) => *id,
2777	None => continue,
2778	};
2779	let iface = &mut resolve.interfaces[id];
2780	iface.package = Some(pkgid);
2781	if let Some(name) = &iface.name {
2782	let prev = resolve.packages[pkgid].interfaces.insert(name.clone(), id);
2783	assert!(prev.is_none());
2784	}
2785	}
2786	for id in self.worlds.iter().skip(foreign_worlds) {
2787	let id = match id {
2788	Some(id) => *id,
2789	None => continue,
2790	};
2791	let world = &mut resolve.worlds[id];
2792	world.package = Some(pkgid);
2793	let prev = resolve.packages[pkgid]
2794	.worlds
2795	.insert(world.name.clone(), id);
2796	assert!(prev.is_none());
2797	}
2798	Ok(pkgid)
2799	}
2800
2801	fn process_foreign_deps(
2802	&mut self,
2803	resolve: &mut Resolve,
2804	unresolved: &UnresolvedPackage,
2805	) -> Result<()> {
2806	// Invert the `foreign_deps` map to be keyed by world id to get
2807	// used in the loops below.
2808	let mut world_to_package = HashMap::new();
2809	let mut interface_to_package = HashMap::new();
2810	for (i, (pkg_name, worlds_or_ifaces)) in unresolved.foreign_deps.iter().enumerate() {
2811	for (name, item) in worlds_or_ifaces {
2812	match item {
2813	AstItem::Interface(unresolved_interface_id) => {
2814	let prev = interface_to_package.insert(
2815	*unresolved_interface_id,
2816	(pkg_name, name, unresolved.foreign_dep_spans[i]),
2817	);
2818	assert!(prev.is_none());
2819	}
2820	AstItem::World(unresolved_world_id) => {
2821	let prev = world_to_package.insert(
2822	*unresolved_world_id,
2823	(pkg_name, name, unresolved.foreign_dep_spans[i]),
2824	);
2825	assert!(prev.is_none());
2826	}
2827	}
2828	}
2829	}
2830
2831	// Connect all interfaces referred to in `interface_to_package`, which
2832	// are at the front of `unresolved.interfaces`, to interfaces already
2833	// contained within `resolve`.
2834	self.process_foreign_interfaces(unresolved, &interface_to_package, resolve)?;
2835
2836	// Connect all worlds referred to in `world_to_package`, which
2837	// are at the front of `unresolved.worlds`, to worlds already
2838	// contained within `resolve`.
2839	self.process_foreign_worlds(unresolved, &world_to_package, resolve)?;
2840
2841	// Finally, iterate over all foreign-defined types and determine
2842	// what they map to.
2843	self.process_foreign_types(unresolved, resolve)?;
2844
2845	for (id, span) in unresolved.required_resource_types.iter() {
2846	let mut id = self.map_type(id, Some(span))?;
2847	loop {
2848	match resolve.types[id].kind {
2849	TypeDefKind::Type(Type::Id(i)) => id = i,
2850	TypeDefKind::Resource => break,
2851	_ => bail!(Error::new(
2852	*span,
2853	format!("type used in a handle must be a resource"),
2854	)),
2855	}
2856	}
2857	}
2858
2859	#[cfg(debug_assertions)]
2860	resolve.assert_valid();
2861
2862	Ok(())
2863	}
2864
2865	fn process_foreign_interfaces(
2866	&mut self,
2867	unresolved: &UnresolvedPackage,
2868	interface_to_package: &HashMap<InterfaceId, (&PackageName, &String, Span)>,
2869	resolve: &mut Resolve,
2870	) -> Result<(), anyhow::Error> {
2871	for (unresolved_iface_id, unresolved_iface) in unresolved.interfaces.iter() {
2872	let (pkg_name, interface, span) = match interface_to_package.get(&unresolved_iface_id) {
2873	Some(items) => *items,
2874	// All foreign interfaces are defined first, so the first one
2875	// which is defined in a non-foreign document means that all
2876	// further interfaces will be non-foreign as well.
2877	None => break,
2878	};
2879	let pkgid = resolve
2880	.package_names
2881	.get(pkg_name)
2882	.copied()
2883	.ok_or_else(\|\| {
2884	PackageNotFoundError::new(
2885	span,
2886	pkg_name.clone(),
2887	resolve.package_names.keys().cloned().collect(),
2888	)
2889	})?;
2890
2891	// Functions can't be imported so this should be empty.
2892	assert!(unresolved_iface.functions.is_empty());
2893
2894	let pkg = &resolve.packages[pkgid];
2895	let span = &unresolved.interface_spans[unresolved_iface_id.index()];
2896	let iface_id = pkg
2897	.interfaces
2898	.get(interface)
2899	.copied()
2900	.ok_or_else(\|\| Error::new(span.span, "interface not found in package"))?;
2901	assert_eq!(self.interfaces.len(), unresolved_iface_id.index());
2902	self.interfaces.push(Some(iface_id));
2903	}
2904	for (id, _) in unresolved.interfaces.iter().skip(self.interfaces.len()) {
2905	assert!(
2906	interface_to_package.get(&id).is_none(),
2907	"found foreign interface after local interface"
2908	);
2909	}
2910	Ok(())
2911	}
2912
2913	fn process_foreign_worlds(
2914	&mut self,
2915	unresolved: &UnresolvedPackage,
2916	world_to_package: &HashMap<WorldId, (&PackageName, &String, Span)>,
2917	resolve: &mut Resolve,
2918	) -> Result<(), anyhow::Error> {
2919	for (unresolved_world_id, _) in unresolved.worlds.iter() {
2920	let (pkg_name, world, span) = match world_to_package.get(&unresolved_world_id) {
2921	Some(items) => *items,
2922	// Same as above, all worlds are foreign until we find a
2923	// non-foreign one.
2924	None => break,
2925	};
2926
2927	let pkgid = resolve
2928	.package_names
2929	.get(pkg_name)
2930	.copied()
2931	.ok_or_else(\|\| Error::new(span, "package not found"))?;
2932	let pkg = &resolve.packages[pkgid];
2933	let span = &unresolved.world_spans[unresolved_world_id.index()];
2934	let world_id = pkg
2935	.worlds
2936	.get(world)
2937	.copied()
2938	.ok_or_else(\|\| Error::new(span.span, "world not found in package"))?;
2939	assert_eq!(self.worlds.len(), unresolved_world_id.index());
2940	self.worlds.push(Some(world_id));
2941	}
2942	for (id, _) in unresolved.worlds.iter().skip(self.worlds.len()) {
2943	assert!(
2944	world_to_package.get(&id).is_none(),
2945	"found foreign world after local world"
2946	);
2947	}
2948	Ok(())
2949	}
2950
2951	fn process_foreign_types(
2952	&mut self,
2953	unresolved: &UnresolvedPackage,
2954	resolve: &mut Resolve,
2955	) -> Result<(), anyhow::Error> {
2956	for (unresolved_type_id, unresolved_ty) in unresolved.types.iter() {
2957	// All "Unknown" types should appear first so once we're no longer
2958	// in unknown territory it's package-defined types so break out of
2959	// this loop.
2960	match unresolved_ty.kind {
2961	TypeDefKind::Unknown => {}
2962	_ => break,
2963	}
2964	let unresolved_iface_id = match unresolved_ty.owner {
2965	TypeOwner::Interface(id) => id,
2966	_ => unreachable!(),
2967	};
2968	let iface_id = self.map_interface(unresolved_iface_id, None)?;
2969	let name = unresolved_ty.name.as_ref().unwrap();
2970	let span = unresolved.unknown_type_spans[unresolved_type_id.index()];
2971	let type_id = *resolve.interfaces[iface_id]
2972	.types
2973	.get(name)
2974	.ok_or_else(\|\| {
2975	Error::new(span, format!("type `{name}` not defined in interface"))
2976	})?;
2977	assert_eq!(self.types.len(), unresolved_type_id.index());
2978	self.types.push(Some(type_id));
2979	}
2980	for (_, ty) in unresolved.types.iter().skip(self.types.len()) {
2981	if let TypeDefKind::Unknown = ty.kind {
2982	panic!("unknown type after defined type");
2983	}
2984	}
2985	Ok(())
2986	}
2987
2988	fn update_typedef(
2989	&mut self,
2990	resolve: &mut Resolve,
2991	ty: &mut TypeDef,
2992	span: Option<Span>,
2993	) -> Result<()> {
2994	// NB: note that `ty.owner` is not updated here since interfaces
2995	// haven't been mapped yet and that's done in a separate step.
2996	use crate::TypeDefKind::*;
2997	match &mut ty.kind {
2998	Handle(handle) => match handle {
2999	crate::Handle::Own(ty) \| crate::Handle::Borrow(ty) => {
3000	self.update_type_id(ty, span)?
3001	}
3002	},
3003	Resource => {}
3004	Record(r) => {
3005	for field in r.fields.iter_mut() {
3006	self.update_ty(resolve, &mut field.ty, span)
3007	.with_context(\|\| format!("failed to update field `{}`", field.name))?;
3008	}
3009	}
3010	Tuple(t) => {
3011	for ty in t.types.iter_mut() {
3012	self.update_ty(resolve, ty, span)?;
3013	}
3014	}
3015	Variant(v) => {
3016	for case in v.cases.iter_mut() {
3017	if let Some(t) = &mut case.ty {
3018	self.update_ty(resolve, t, span)?;
3019	}
3020	}
3021	}
3022	Option(t) \| List(t) \| Stream(t) => self.update_ty(resolve, t, span)?,
3023	Result(r) => {
3024	if let Some(ty) = &mut r.ok {
3025	self.update_ty(resolve, ty, span)?;
3026	}
3027	if let Some(ty) = &mut r.err {
3028	self.update_ty(resolve, ty, span)?;
3029	}
3030	}
3031	Future(Some(t)) => self.update_ty(resolve, t, span)?,
3032	ErrorContext => {}
3033
3034	// Note that `update_ty` is specifically not used here as typedefs
3035	// because for the `type a = b` form that doesn't force `a` to be a
3036	// handle type if `b` is a resource type, instead `a` is
3037	// simultaneously usable as a resource and a handle type
3038	Type(crate::Type::Id(id)) => self.update_type_id(id, span)?,
3039	Type(_) => {}
3040
3041	// nothing to do for these as they're just names or empty
3042	Flags(_) \| Enum(_) \| Future(None) => {}
3043
3044	Unknown => unreachable!(),
3045	}
3046
3047	Ok(())
3048	}
3049
3050	fn update_ty(
3051	&mut self,
3052	resolve: &mut Resolve,
3053	ty: &mut Type,
3054	span: Option<Span>,
3055	) -> Result<()> {
3056	let id = match ty {
3057	Type::Id(id) => id,
3058	_ => return Ok(()),
3059	};
3060	self.update_type_id(id, span)?;
3061
3062	// If `id` points to a `Resource` type then this means that what was
3063	// just discovered was a reference to what will implicitly become an
3064	// `own<T>` handle. This `own` handle is implicitly allocated here
3065	// and handled during the merging process.
3066	let mut cur = *id;
3067	let points_to_resource = loop {
3068	match resolve.types[cur].kind {
3069	TypeDefKind::Type(Type::Id(id)) => cur = id,
3070	TypeDefKind::Resource => break `true`,
3071	_ => break `false`,
3072	}
3073	};
3074
3075	if points_to_resource {
3076	id = self.own_handles.entry(*id).or_insert_with(\|\| {
3077	resolve.types.alloc(TypeDef {
3078	name: None,
3079	owner: TypeOwner::None,
3080	kind: TypeDefKind::Handle(Handle::Own(*id)),
3081	docs: Default::default(),
3082	stability: Default::default(),
3083	})
3084	});
3085	}
3086	Ok(())
3087	}
3088
3089	fn update_type_id(&self, id: &mut TypeId, span: Option<Span>) -> Result<()> {
3090	id = self.map_type(id, span)?;
3091	Ok(())
3092	}
3093
3094	fn update_interface(
3095	&mut self,
3096	resolve: &mut Resolve,
3097	iface: &mut Interface,
3098	spans: Option<&InterfaceSpan>,
3099	) -> Result<()> {
3100	iface.types.retain(\|_, ty\| self.types[ty.index()].is_some());
3101	let iface_pkg_id = iface.package.as_ref().unwrap_or_else(\|\| {
3102	panic!(
3103	"unexpectedly missing package on interface [{}]",
3104	iface
3105	.name
3106	.as_ref()
3107	.map(String::as_str)
3108	.unwrap_or("<unknown>"),
3109	)
3110	});
3111
3112	// NB: note that `iface.doc` is not updated here since interfaces
3113	// haven't been mapped yet and that's done in a separate step.
3114	for (_name, ty) in iface.types.iter_mut() {
3115	self.update_type_id(ty, spans.map(\|s\| s.span))?;
3116	}
3117	if let Some(spans) = spans {
3118	assert_eq!(iface.functions.len(), spans.funcs.len());
3119	}
3120	for (i, (func_name, func)) in iface.functions.iter_mut().enumerate() {
3121	if !resolve
3122	.include_stability(&func.stability, iface_pkg_id)
3123	.with_context(\|\| {
3124	format!(
3125	"failed to process feature gate for function [{func_name}] in package [{}]",
3126	resolve.packages[*iface_pkg_id].name,
3127	)
3128	})?
3129	{
3130	continue;
3131	}
3132	let span = spans.map(\|s\| s.funcs[i]);
3133	self.update_function(resolve, func, span)
3134	.with_context(\|\| format!("failed to update function `{}`", func.name))?;
3135	}
3136
3137	// Filter out all of the existing functions in interface which fail the
3138	// `include_stability()` check, as they shouldn't be available.
3139	for (name, func) in mem::take(&mut iface.functions) {
3140	if resolve.include_stability(&func.stability, iface_pkg_id)? {
3141	iface.functions.insert(name, func);
3142	}
3143	}
3144
3145	Ok(())
3146	}
3147
3148	fn update_function(
3149	&mut self,
3150	resolve: &mut Resolve,
3151	func: &mut Function,
3152	span: Option<Span>,
3153	) -> Result<()> {
3154	match &mut func.kind {
3155	FunctionKind::Freestanding => {}
3156	FunctionKind::Method(id) \| FunctionKind::Constructor(id) \| FunctionKind::Static(id) => {
3157	self.update_type_id(id, span)?;
3158	}
3159	}
3160	for (_, ty) in func.params.iter_mut() {
3161	self.update_ty(resolve, ty, span)?;
3162	}
3163	match &mut func.results {
3164	Results::Named(named) => {
3165	for (_, ty) in named.iter_mut() {
3166	self.update_ty(resolve, ty, span)?;
3167	}
3168	}
3169	Results::Anon(ty) => self.update_ty(resolve, ty, span)?,
3170	}
3171
3172	for ty in func.results.iter_types() {
3173	if !self.type_has_borrow(resolve, ty) {
3174	continue;
3175	}
3176	match span {
3177	Some(span) => {
3178	bail!(Error::new(
3179	span,
3180	format!(
3181	"function returns a type which contains \
3182	a `borrow<T>` which is not supported"
3183	)
3184	))
3185	}
3186	None => unreachable!(),
3187	}
3188	}
3189
3190	Ok(())
3191	}
3192
3193	fn update_world(
3194	&mut self,
3195	world: &mut World,
3196	resolve: &mut Resolve,
3197	pkg_id: &PackageId,
3198	spans: &WorldSpan,
3199	) -> Result<()> {
3200	assert_eq!(world.imports.len(), spans.imports.len());
3201	assert_eq!(world.exports.len(), spans.exports.len());
3202
3203	// Rewrite imports/exports with their updated versions. Note that this
3204	// may involve updating the key of the imports/exports maps so this
3205	// starts by emptying them out and then everything is re-inserted.
3206	let imports = mem::take(&mut world.imports).into_iter();
3207	let imports = imports.zip(&spans.imports).map(\|p\| (p, `true`));
3208	let exports = mem::take(&mut world.exports).into_iter();
3209	let exports = exports.zip(&spans.exports).map(\|p\| (p, `false`));
3210	for (((mut name, mut item), span), import) in imports.chain(exports) {
3211	// Update the `id` eagerly here so `item.stability(..)` below
3212	// works.
3213	if let WorldItem::Type(id) = &mut item {
3214	id = self.map_type(id, Some(*span))?;
3215	}
3216	let stability = item.stability(resolve);
3217	if !resolve
3218	.include_stability(stability, pkg_id)
3219	.with_context(\|\| {
3220	format!(
3221	"failed to process imported world item type [{}] in package [{}]",
3222	resolve.name_world_key(&name),
3223	resolve.packages[*pkg_id].name,
3224	)
3225	})?
3226	{
3227	continue;
3228	}
3229	self.update_world_key(&mut name, Some(*span))?;
3230	match &mut item {
3231	WorldItem::Interface { id, .. } => {
3232	id = self.map_interface(id, Some(*span))?;
3233	}
3234	WorldItem::Function(f) => {
3235	self.update_function(resolve, f, Some(*span))?;
3236	}
3237	WorldItem::Type(_) => {
3238	// already mapped above
3239	}
3240	}
3241
3242	let dst = if import {
3243	&mut world.imports
3244	} else {
3245	&mut world.exports
3246	};
3247	let prev = dst.insert(name, item);
3248	assert!(prev.is_none());
3249	}
3250
3251	// Resolve all `include` statements of the world which will add more
3252	// entries to the imports/exports list for this world.
3253	assert_eq!(world.includes.len(), spans.includes.len());
3254	let includes = mem::take(&mut world.includes);
3255	let include_names = mem::take(&mut world.include_names);
3256	for (((stability, include_world), span), names) in includes
3257	.into_iter()
3258	.zip(&spans.includes)
3259	.zip(&include_names)
3260	{
3261	if !resolve
3262	.include_stability(&stability, pkg_id)
3263	.with_context(\|\| {
3264	format!(
3265	"failed to process feature gate for included world [{}] in package [{}]",
3266	resolve.worlds[include_world].name.as_str(),
3267	resolve.packages[*pkg_id].name
3268	)
3269	})?
3270	{
3271	continue;
3272	}
3273	self.resolve_include(world, include_world, names, *span, resolve)?;
3274	}
3275
3276	Ok(())
3277	}
3278
3279	fn update_world_key(&self, key: &mut WorldKey, span: Option<Span>) -> Result<()> {
3280	match key {
3281	WorldKey::Name(_) => {}
3282	WorldKey::Interface(id) => {
3283	id = self.map_interface(id, span)?;
3284	}
3285	}
3286	Ok(())
3287	}
3288
3289	fn resolve_include(
3290	&self,
3291	world: &mut World,
3292	include_world: WorldId,
3293	names: &[IncludeName],
3294	span: Span,
3295	resolve: &Resolve,
3296	) -> Result<()> {
3297	let include_world_id = self.map_world(include_world, Some(span))?;
3298	let include_world = &resolve.worlds[include_world_id];
3299	let mut names_ = names.to_owned();
3300
3301	// remove all imports and exports that match the names we're including
3302	for import in include_world.imports.iter() {
3303	self.remove_matching_name(import, &mut names_);
3304	}
3305	for export in include_world.exports.iter() {
3306	self.remove_matching_name(export, &mut names_);
3307	}
3308	if !names_.is_empty() {
3309	bail!(Error::new(
3310	span,
3311	format!("no import or export kebab-name `{}`. Note that an ID does not support renaming", names_[`0`].name),
3312	));
3313	}
3314
3315	// copy the imports and exports from the included world into the current world
3316	for import in include_world.imports.iter() {
3317	self.resolve_include_item(names, &mut world.imports, import, span, "import")?;
3318	}
3319
3320	for export in include_world.exports.iter() {
3321	self.resolve_include_item(names, &mut world.exports, export, span, "export")?;
3322	}
3323	Ok(())
3324	}
3325
3326	fn resolve_include_item(
3327	&self,
3328	names: &[IncludeName],
3329	items: &mut IndexMap<WorldKey, WorldItem>,
3330	item: (&WorldKey, &WorldItem),
3331	span: Span,
3332	item_type: &str,
3333	) -> Result<()> {
3334	match item.0 {
3335	WorldKey::Name(n) => {
3336	let n = if let Some(found) = names
3337	.into_iter()
3338	.find(\|include_name\| include_name.name == n.clone())
3339	{
3340	found.as_.clone()
3341	} else {
3342	n.clone()
3343	};
3344
3345	let prev = items.insert(WorldKey::Name(n.clone()), item.1.clone());
3346	if prev.is_some() {
3347	bail!(Error::new(
3348	span,
3349	format!("{item_type} of `{n}` shadows previously {item_type}ed items"),
3350	))
3351	}
3352	}
3353	key @ WorldKey::Interface(_) => {
3354	let prev = items.entry(key.clone()).or_insert(item.1.clone());
3355	match (&item.1, prev) {
3356	(
3357	WorldItem::Interface {
3358	id: aid,
3359	stability: astability,
3360	},
3361	WorldItem::Interface {
3362	id: bid,
3363	stability: bstability,
3364	},
3365	) => {
3366	assert_eq!(aid, bid);
3367	update_stability(astability, bstability)?;
3368	}
3369	(WorldItem::Interface { .. }, _) => unreachable!(),
3370	(WorldItem::Function(_), _) => unreachable!(),
3371	(WorldItem::Type(_), _) => unreachable!(),
3372	}
3373	}
3374	};
3375	Ok(())
3376	}
3377
3378	fn remove_matching_name(&self, item: (&WorldKey, &WorldItem), names: &mut Vec<IncludeName>) {
3379	match item.0 {
3380	WorldKey::Name(n) => {
3381	names.retain(\|name\| name.name != n.clone());
3382	}
3383	_ => {}
3384	}
3385	}
3386
3387	fn type_has_borrow(&mut self, resolve: &Resolve, ty: &Type) -> bool {
3388	let id = match ty {
3389	Type::Id(id) => *id,
3390	_ => return `false`,
3391	};
3392
3393	if let Some(Some(has_borrow)) = self.type_has_borrow.get(id.index()) {
3394	return *has_borrow;
3395	}
3396
3397	let result = self.typedef_has_borrow(resolve, &resolve.types[id]);
3398	if self.type_has_borrow.len() <= id.index() {
3399	self.type_has_borrow.resize(id.index() + `1`, None);
3400	}
3401	self.type_has_borrow[id.index()] = Some(result);
3402	result
3403	}
3404
3405	fn typedef_has_borrow(&mut self, resolve: &Resolve, ty: &TypeDef) -> bool {
3406	match &ty.kind {
3407	TypeDefKind::Type(t) => self.type_has_borrow(resolve, t),
3408	TypeDefKind::Variant(v) => v
3409	.cases
3410	.iter()
3411	.filter_map(\|case\| case.ty.as_ref())
3412	.any(\|ty\| self.type_has_borrow(resolve, ty)),
3413	TypeDefKind::Handle(Handle::Borrow(_)) => `true`,
3414	TypeDefKind::Handle(Handle::Own(_)) => `false`,
3415	TypeDefKind::Resource => `false`,
3416	TypeDefKind::Record(r) => r
3417	.fields
3418	.iter()
3419	.any(\|case\| self.type_has_borrow(resolve, &case.ty)),
3420	TypeDefKind::Flags(_) => `false`,
3421	TypeDefKind::Tuple(t) => t.types.iter().any(\|t\| self.type_has_borrow(resolve, t)),
3422	TypeDefKind::Enum(_) => `false`,
3423	TypeDefKind::List(ty)
3424	\| TypeDefKind::Future(Some(ty))
3425	\| TypeDefKind::Stream(ty)
3426	\| TypeDefKind::Option(ty) => self.type_has_borrow(resolve, ty),
3427	TypeDefKind::Result(r) => [&r.ok, &r.err]
3428	.iter()
3429	.filter_map(\|t\| t.as_ref())
3430	.any(\|t\| self.type_has_borrow(resolve, t)),
3431	TypeDefKind::Future(None) \| TypeDefKind::ErrorContext => `false`,
3432	TypeDefKind::Unknown => unreachable!(),
3433	}
3434	}
3435	}
3436
3437	struct MergeMap<'a> {
3438	/// A map of package ids in `from` to those in `into` for those that are
3439	/// found to be equivalent.
3440	package_map: HashMap<PackageId, PackageId>,
3441
3442	/// A map of interface ids in `from` to those in `into` for those that are
3443	/// found to be equivalent.
3444	interface_map: HashMap<InterfaceId, InterfaceId>,
3445
3446	/// A map of type ids in `from` to those in `into` for those that are
3447	/// found to be equivalent.
3448	type_map: HashMap<TypeId, TypeId>,
3449
3450	/// A map of world ids in `from` to those in `into` for those that are
3451	/// found to be equivalent.
3452	world_map: HashMap<WorldId, WorldId>,
3453
3454	/// A list of documents that need to be added to packages in `into`.
3455	///
3456	/// The elements here are:
3457	///
3458	/// The name of the interface/world*
3459	/// The ID within `into` of the package being added to*
3460	/// The ID within `from` of the item being added.*
3461	interfaces_to_add: Vec<(String, PackageId, InterfaceId)>,
3462	worlds_to_add: Vec<(String, PackageId, WorldId)>,
3463
3464	/// Which `Resolve` is being merged from.
3465	from: &'a Resolve,
3466
3467	/// Which `Resolve` is being merged into.
3468	into: &'a Resolve,
3469	}
3470
3471	impl<'a> MergeMap<'a> {
3472	fn new(from: &'a Resolve, into: &'a Resolve) -> MergeMap<'a> {
3473	MergeMap {
3474	package_map: Default::default(),
3475	interface_map: Default::default(),
3476	type_map: Default::default(),
3477	world_map: Default::default(),
3478	interfaces_to_add: Default::default(),
3479	worlds_to_add: Default::default(),
3480	from,
3481	into,
3482	}
3483	}
3484
3485	fn build(&mut self) -> Result<()> {
3486	for from_id in self.from.topological_packages() {
3487	let from = &self.from.packages[from_id];
3488	let into_id = match self.into.package_names.get(&from.name) {
3489	Some(id) => *id,
3490
3491	// This package, according to its name and url, is not present
3492	// in `self` so it needs to get added below.
3493	None => {
3494	log::trace!("adding unique package {}", from.name);
3495	continue;
3496	}
3497	};
3498	log::trace!("merging duplicate package {}", from.name);
3499
3500	self.build_package(from_id, into_id).with_context(\|\| {
3501	format!("failed to merge package `{}` into existing copy", from.name)
3502	})?;
3503	}
3504
3505	Ok(())
3506	}
3507
3508	fn build_package(&mut self, from_id: PackageId, into_id: PackageId) -> Result<()> {
3509	let prev = self.package_map.insert(from_id, into_id);
3510	assert!(prev.is_none());
3511
3512	let from = &self.from.packages[from_id];
3513	let into = &self.into.packages[into_id];
3514
3515	// If an interface is present in `from_id` but not present in `into_id`
3516	// then it can be copied over wholesale. That copy is scheduled to
3517	// happen within the `self.interfaces_to_add` list.
3518	for (name, from_interface_id) in from.interfaces.iter() {
3519	let into_interface_id = match into.interfaces.get(name) {
3520	Some(id) => *id,
3521	None => {
3522	log::trace!("adding unique interface {}", name);
3523	self.interfaces_to_add
3524	.push((name.clone(), into_id, *from_interface_id));
3525	continue;
3526	}
3527	};
3528
3529	log::trace!("merging duplicate interfaces {}", name);
3530	self.build_interface(*from_interface_id, into_interface_id)
3531	.with_context(\|\| format!("failed to merge interface `{name}`"))?;
3532	}
3533
3534	for (name, from_world_id) in from.worlds.iter() {
3535	let into_world_id = match into.worlds.get(name) {
3536	Some(id) => *id,
3537	None => {
3538	log::trace!("adding unique world {}", name);
3539	self.worlds_to_add
3540	.push((name.clone(), into_id, *from_world_id));
3541	continue;
3542	}
3543	};
3544
3545	log::trace!("merging duplicate worlds {}", name);
3546	self.build_world(*from_world_id, into_world_id)
3547	.with_context(\|\| format!("failed to merge world `{name}`"))?;
3548	}
3549
3550	Ok(())
3551	}
3552
3553	fn build_interface(&mut self, from_id: InterfaceId, into_id: InterfaceId) -> Result<()> {
3554	let prev = self.interface_map.insert(from_id, into_id);
3555	assert!(prev.is_none());
3556
3557	let from_interface = &self.from.interfaces[from_id];
3558	let into_interface = &self.into.interfaces[into_id];
3559
3560	// Unlike documents/interfaces above if an interface in `from`
3561	// differs from the interface in `into` then that's considered an
3562	// error. Changing interfaces can reflect changes in imports/exports
3563	// which may not be expected so it's currently required that all
3564	// interfaces, when merged, exactly match.
3565	//
3566	// One case to consider here, for example, is that if a world in
3567	// `into` exports the interface `into_id` then if `from_id` were to
3568	// add more items into `into` then it would unexpectedly require more
3569	// items to be exported which may not work. In an import context this
3570	// might work since it's "just more items available for import", but
3571	// for now a conservative route of "interfaces must match" is taken.
3572
3573	for (name, from_type_id) in from_interface.types.iter() {
3574	let into_type_id = *into_interface
3575	.types
3576	.get(name)
3577	.ok_or_else(\|\| anyhow!("expected type `{name}` to be present"))?;
3578	let prev = self.type_map.insert(*from_type_id, into_type_id);
3579	assert!(prev.is_none());
3580
3581	self.build_type_id(*from_type_id, into_type_id)
3582	.with_context(\|\| format!("mismatch in type `{name}`"))?;
3583	}
3584
3585	for (name, from_func) in from_interface.functions.iter() {
3586	let into_func = match into_interface.functions.get(name) {
3587	Some(func) => func,
3588	None => bail!("expected function `{name}` to be present"),
3589	};
3590	self.build_function(from_func, into_func)
3591	.with_context(\|\| format!("mismatch in function `{name}`"))?;
3592	}
3593
3594	Ok(())
3595	}
3596
3597	fn build_type_id(&mut self, from_id: TypeId, into_id: TypeId) -> Result<()> {
3598	// FIXME: ideally the types should be "structurally
3599	// equal" but that's not trivial to do in the face of
3600	// resources.
3601	let _ = from_id;
3602	let _ = into_id;
3603	Ok(())
3604	}
3605
3606	fn build_type(&mut self, from_ty: &Type, into_ty: &Type) -> Result<()> {
3607	match (from_ty, into_ty) {
3608	(Type::Id(from), Type::Id(into)) => {
3609	self.build_type_id(from, into)?;
3610	}
3611	(from, into) if from != into => bail!("different kinds of types"),
3612	_ => {}
3613	}
3614	Ok(())
3615	}
3616
3617	fn build_function(&mut self, from_func: &Function, into_func: &Function) -> Result<()> {
3618	if from_func.name != into_func.name {
3619	bail!(
3620	"different function names `{}` and `{}`",
3621	from_func.name,
3622	into_func.name
3623	);
3624	}
3625	match (&from_func.kind, &into_func.kind) {
3626	(FunctionKind::Freestanding, FunctionKind::Freestanding) => {}
3627
3628	(FunctionKind::Method(from), FunctionKind::Method(into))
3629	\| (FunctionKind::Constructor(from), FunctionKind::Constructor(into))
3630	\| (FunctionKind::Static(from), FunctionKind::Static(into)) => self
3631	.build_type_id(from, into)
3632	.context("different function kind types")?,
3633
3634	(FunctionKind::Method(_), _)
3635	\| (FunctionKind::Constructor(_), _)
3636	\| (FunctionKind::Static(_), _)
3637	\| (FunctionKind::Freestanding, _) => {
3638	bail!("different function kind types")
3639	}
3640	}
3641
3642	if from_func.params.len() != into_func.params.len() {
3643	bail!("different number of function parameters");
3644	}
3645	for ((from_name, from_ty), (into_name, into_ty)) in
3646	from_func.params.iter().zip(&into_func.params)
3647	{
3648	if from_name != into_name {
3649	bail!("different function parameter names: {from_name} != {into_name}");
3650	}
3651	self.build_type(from_ty, into_ty)
3652	.with_context(\|\| format!("different function parameter types for `{from_name}`"))?;
3653	}
3654	if from_func.results.len() != into_func.results.len() {
3655	bail!("different number of function results");
3656	}
3657	for (from_ty, into_ty) in from_func
3658	.results
3659	.iter_types()
3660	.zip(into_func.results.iter_types())
3661	{
3662	self.build_type(from_ty, into_ty)
3663	.context("different function result types")?;
3664	}
3665	Ok(())
3666	}
3667
3668	fn build_world(&mut self, from_id: WorldId, into_id: WorldId) -> Result<()> {
3669	let prev = self.world_map.insert(from_id, into_id);
3670	assert!(prev.is_none());
3671
3672	let from_world = &self.from.worlds[from_id];
3673	let into_world = &self.into.worlds[into_id];
3674
3675	// Same as interfaces worlds are expected to exactly match to avoid
3676	// unexpectedly changing a particular component's view of imports and
3677	// exports.
3678	//
3679	// FIXME: this should probably share functionality with
3680	// `Resolve::merge_worlds` to support adding imports but not changing
3681	// exports.
3682
3683	if from_world.imports.len() != into_world.imports.len() {
3684	bail!("world contains different number of imports than expected");
3685	}
3686	if from_world.exports.len() != into_world.exports.len() {
3687	bail!("world contains different number of exports than expected");
3688	}
3689
3690	for (from_name, from) in from_world.imports.iter() {
3691	let into_name = self.map_name(from_name);
3692	let name_str = self.from.name_world_key(from_name);
3693	let into = into_world
3694	.imports
3695	.get(&into_name)
3696	.ok_or_else(\|\| anyhow!("import `{name_str}` not found in target world"))?;
3697	self.match_world_item(from, into)
3698	.with_context(\|\| format!("import `{name_str}` didn't match target world"))?;
3699	}
3700
3701	for (from_name, from) in from_world.exports.iter() {
3702	let into_name = self.map_name(from_name);
3703	let name_str = self.from.name_world_key(from_name);
3704	let into = into_world
3705	.exports
3706	.get(&into_name)
3707	.ok_or_else(\|\| anyhow!("export `{name_str}` not found in target world"))?;
3708	self.match_world_item(from, into)
3709	.with_context(\|\| format!("export `{name_str}` didn't match target world"))?;
3710	}
3711
3712	Ok(())
3713	}
3714
3715	fn map_name(&self, from_name: &WorldKey) -> WorldKey {
3716	match from_name {
3717	WorldKey::Name(s) => WorldKey::Name(s.clone()),
3718	WorldKey::Interface(id) => {
3719	WorldKey::Interface(self.interface_map.get(id).copied().unwrap_or(*id))
3720	}
3721	}
3722	}
3723
3724	fn match_world_item(&mut self, from: &WorldItem, into: &WorldItem) -> Result<()> {
3725	match (from, into) {
3726	(WorldItem::Interface { id: from, .. }, WorldItem::Interface { id: into, .. }) => {
3727	match (
3728	&self.from.interfaces[*from].name,
3729	&self.into.interfaces[*into].name,
3730	) {
3731	// If one interface is unnamed then they must both be
3732	// unnamed and they must both have the same structure for
3733	// now.
3734	(None, None) => self.build_interface(from, into)?,
3735
3736	// Otherwise both interfaces must be named and they must
3737	// have been previously found to be equivalent. Note that
3738	// if either is unnamed it won't be present in
3739	// `interface_map` so this'll return an error.
3740	_ => {
3741	if self.interface_map.get(&from) != Some(&into) {
3742	bail!("interfaces are not the same");
3743	}
3744	}
3745	}
3746	}
3747	(WorldItem::Function(from), WorldItem::Function(into)) => {
3748	let _ = (from, into);
3749	// FIXME: should assert an check that `from` structurally
3750	// matches `into`
3751	}
3752	(WorldItem::Type(from), WorldItem::Type(into)) => {
3753	// FIXME: should assert an check that `from` structurally
3754	// matches `into`
3755	let prev = self.type_map.insert(from, into);
3756	assert!(prev.is_none());
3757	}
3758
3759	(WorldItem::Interface { .. }, _)
3760	\| (WorldItem::Function(_), _)
3761	\| (WorldItem::Type(_), _) => {
3762	bail!("world items do not have the same type")
3763	}
3764	}
3765	Ok(())
3766	}
3767	}
3768
3769	/// Updates stability annotations when merging `from` into `into`.
3770	///
3771	/// This is done to keep up-to-date stability information if possible.
3772	/// Components for example don't carry stability information but WIT does so
3773	/// this tries to move from "unknown" to stable/unstable if possible.
3774	fn update_stability(from: &Stability, into: &mut Stability) -> Result<()> {
3775	// If `from` is unknown or the two stability annotations are equal then
3776	// there's nothing to do here.
3777	if from == into \|\| from.is_unknown() {
3778	return Ok(());
3779	}
3780	// Otherwise if `into` is unknown then inherit the stability listed in
3781	// `from`.
3782	if into.is_unknown() {
3783	*into = from.clone();
3784	return Ok(());
3785	}
3786
3787	// Failing all that this means that the two attributes are different so
3788	// generate an error.
3789	bail!("mismatch in stability attributes")
3790	}
3791
3792	/// An error that can be returned during "world elaboration" during various
3793	/// [`Resolve`] operations.
3794	///
3795	/// Methods on [`Resolve`] which mutate its internals, such as
3796	/// [`Resolve::push_dir`] or [`Resolve::importize`] can fail if `world` imports
3797	/// in WIT packages are invalid. This error indicates one of these situations
3798	/// where an invalid dependency graph between imports and exports are detected.
3799	///
3800	/// Note that at this time this error is subtle and not easy to understand, and
3801	/// work needs to be done to explain this better and additionally provide a
3802	/// better error message. For now though this type enables callers to test for
3803	/// the exact kind of error emitted.
3804	#[derive(Debug, Clone)]
3805	pub struct InvalidTransitiveDependency(String);
3806
3807	impl fmt::Display for InvalidTransitiveDependency {
3808	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3809	write!(
3810	f,
3811	"interface `{}` transitively depends on an interface in \
3812	incompatible ways",
3813	self.0
3814	)
3815	}
3816	}
3817
3818	impl std::error::Error for InvalidTransitiveDependency {}
3819
3820	#[cfg(test)]
3821	mod tests {
3822	use crate::Resolve;
3823	use anyhow::Result;
3824
3825	#[test]
3826	fn select_world() -> Result<()> {
3827	let mut resolve = Resolve::default();
3828	resolve.push_str(
3829	"test.wit",
3830	r#"
3831	package foo:bar@0.1.0;
3832
3833	world foo {}
3834	"#,
3835	)?;
3836	resolve.push_str(
3837	"test.wit",
3838	r#"
3839	package foo:baz@0.1.0;
3840
3841	world foo {}
3842	"#,
3843	)?;
3844	resolve.push_str(
3845	"test.wit",
3846	r#"
3847	package foo:baz@0.2.0;
3848
3849	world foo {}
3850	"#,
3851	)?;
3852
3853	let dummy = resolve.push_str(
3854	"test.wit",
3855	r#"
3856	package foo:dummy;
3857
3858	world foo {}
3859	"#,
3860	)?;
3861
3862	assert!(resolve.select_world(dummy, None).is_ok());
3863	assert!(resolve.select_world(dummy, Some("xx")).is_err());
3864	assert!(resolve.select_world(dummy, Some("")).is_err());
3865	assert!(resolve.select_world(dummy, Some("foo:bar/foo")).is_ok());
3866	assert!(resolve
3867	.select_world(dummy, Some("foo:bar/foo@0.1.0"))
3868	.is_ok());
3869	assert!(resolve.select_world(dummy, Some("foo:baz/foo")).is_err());
3870	assert!(resolve
3871	.select_world(dummy, Some("foo:baz/foo@0.1.0"))
3872	.is_ok());
3873	assert!(resolve
3874	.select_world(dummy, Some("foo:baz/foo@0.2.0"))
3875	.is_ok());
3876	Ok(())
3877	}
3878	}
3879