use std::collections::{BTreeMap, BTreeSet};
use sha2::{Digest, Sha256};
use wit_parser::decoding::{DecodedWasm, decode};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PackageIdent {
key: String,
}
impl PackageIdent {
pub fn new(
namespace: impl AsRef<str>,
name: impl AsRef<str>,
version: impl AsRef<str>,
) -> Result<Self, WitClosureError> {
let (namespace, name, version) = (namespace.as_ref(), name.as_ref(), version.as_ref());
let bad = |part: &str, chars: fn(char) -> bool| {
part.is_empty() || part == "." || part == ".." || !part.chars().all(chars)
};
let id_char = |c: char| c.is_ascii_alphanumeric() || c == '-';
let ver_char = |c: char| c.is_ascii_alphanumeric() || matches!(c, '.' | '-' | '+');
if bad(namespace, id_char) || bad(name, id_char) || bad(version, ver_char) {
return Err(WitClosureError::MalformedRef {
text: format!("{namespace}:{name}@{version}"),
});
}
Ok(Self {
key: format!("{namespace}:{name}@{version}"),
})
}
fn split(&self) -> (usize, usize) {
let colon = self.key.find(':').unwrap_or(0);
let at = self.key.find('@').unwrap_or(self.key.len());
(colon, at)
}
pub fn namespace(&self) -> &str {
&self.key[..self.split().0]
}
pub fn name(&self) -> &str {
let (colon, at) = self.split();
&self.key[colon + 1..at]
}
pub fn version(&self) -> &str {
&self.key[self.split().1 + 1..]
}
pub fn as_str(&self) -> &str {
&self.key
}
pub fn binary_path(&self) -> String {
format!(
"{}/{}/{}.wasm",
self.namespace(),
self.name(),
self.version()
)
}
}
impl std::fmt::Display for PackageIdent {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.key)
}
}
impl std::str::FromStr for PackageIdent {
type Err = WitClosureError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let malformed = || WitClosureError::MalformedRef {
text: s.to_string(),
};
let (namespace, rest) = s.split_once(':').ok_or_else(malformed)?;
let (name, version) = rest.split_once('@').ok_or_else(malformed)?;
Self::new(namespace, name, version).map_err(|_| malformed())
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WitPackage {
ident: PackageIdent,
imports: BTreeSet<PackageIdent>,
digest: String,
}
impl WitPackage {
pub fn from_binary(bytes: &[u8]) -> Result<Self, WitClosureError> {
let decoded = decode(bytes).map_err(|e| WitClosureError::Undecodable {
detail: format!("{e:#}"),
})?;
let (resolve, package_id) = match decoded {
DecodedWasm::WitPackage(resolve, id) => (resolve, id),
DecodedWasm::Component(..) => return Err(WitClosureError::NotAWitPackage),
};
let ident = ident_of(&resolve, package_id)?;
let mut imports = BTreeSet::new();
for dep in resolve.package_direct_deps(package_id) {
let dep_ident = ident_of(&resolve, dep)?;
if dep_ident != ident {
imports.insert(dep_ident);
}
}
Ok(Self {
ident,
imports,
digest: hex::encode(Sha256::digest(bytes)),
})
}
pub fn ident(&self) -> &PackageIdent {
&self.ident
}
pub fn imports(&self) -> &BTreeSet<PackageIdent> {
&self.imports
}
pub fn digest(&self) -> &str {
&self.digest
}
}
fn ident_of(
resolve: &wit_parser::Resolve,
id: wit_parser::PackageId,
) -> Result<PackageIdent, WitClosureError> {
let name = &resolve.packages[id].name;
let version = name
.version
.as_ref()
.ok_or_else(|| WitClosureError::Unversioned {
ident: format!("{}:{}", name.namespace, name.name),
})?;
PackageIdent::new(&name.namespace, &name.name, version.to_string())
}
#[derive(Debug, Clone, Default)]
pub struct PackageIndex {
by_ident: BTreeMap<PackageIdent, WitPackage>,
}
impl PackageIndex {
pub fn new() -> Self {
Self::default()
}
pub fn insert(&mut self, package: WitPackage) -> Result<(), WitClosureError> {
if let Some(existing) = self.by_ident.get(package.ident())
&& existing.digest() != package.digest()
{
return Err(WitClosureError::ConflictingIdentity {
ident: package.ident().clone(),
first: existing.digest().to_string(),
second: package.digest().to_string(),
});
}
self.by_ident.insert(package.ident().clone(), package);
Ok(())
}
pub fn insert_binary(&mut self, bytes: &[u8]) -> Result<PackageIdent, WitClosureError> {
let package = WitPackage::from_binary(bytes)?;
let ident = package.ident().clone();
self.insert(package)?;
Ok(ident)
}
pub fn get(&self, ident: &PackageIdent) -> Option<&WitPackage> {
self.by_ident.get(ident)
}
pub fn len(&self) -> usize {
self.by_ident.len()
}
pub fn is_empty(&self) -> bool {
self.by_ident.is_empty()
}
pub fn idents(&self) -> impl Iterator<Item = &PackageIdent> {
self.by_ident.keys()
}
}
pub fn closure(
index: &PackageIndex,
root: &PackageIdent,
) -> Result<Vec<PackageIdent>, WitClosureError> {
if index.get(root).is_none() {
return Err(WitClosureError::RootMissing { root: root.clone() });
}
enum Step {
Enter {
ident: PackageIdent,
required_by: Option<PackageIdent>,
},
Leave(PackageIdent),
}
let mut stack = vec![Step::Enter {
ident: root.clone(),
required_by: None,
}];
let mut finished: BTreeSet<PackageIdent> = BTreeSet::new();
let mut path: Vec<PackageIdent> = Vec::new();
let mut order: Vec<PackageIdent> = Vec::new();
while let Some(step) = stack.pop() {
match step {
Step::Enter { ident, required_by } => {
if finished.contains(&ident) {
continue; }
if let Some(at) = path.iter().position(|p| *p == ident) {
let mut cycle: Vec<PackageIdent> = path[at..].to_vec();
cycle.push(ident);
return Err(WitClosureError::Cycle { path: cycle });
}
let package = index
.get(&ident)
.ok_or_else(|| WitClosureError::MissingPackage {
root: root.clone(),
missing: ident.clone(),
required_by: required_by.clone().unwrap_or_else(|| root.clone()),
})?;
path.push(ident.clone());
stack.push(Step::Leave(ident.clone()));
for dep in package.imports().iter().rev() {
stack.push(Step::Enter {
ident: dep.clone(),
required_by: Some(ident.clone()),
});
}
}
Step::Leave(ident) => {
path.pop();
finished.insert(ident.clone());
order.push(ident);
}
}
}
Ok(order)
}
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum WitClosureError {
#[error(
"these bytes are not a binary WIT package: they decode as a WebAssembly \
component. A `wit` payload is one encoded WIT package (DD-036)"
)]
NotAWitPackage,
#[error("these bytes are not a readable WebAssembly artifact: {detail}")]
Undecodable { detail: String },
#[error(
"the WIT package '{ident}' declares no version: a layer keys packages by \
`namespace:name@version`, so an unversioned package has no slot to \
occupy and no way to be pinned"
)]
Unversioned { ident: String },
#[error("'{text}' is not a WIT package reference; expected `namespace:name@version`")]
MalformedRef { text: String },
#[error("the layer does not carry the WIT package {root}")]
RootMissing { root: PackageIdent },
#[error(
"the dependency closure of {root} cannot be completed: the layer does not \
carry {missing}, which {required_by} imports. No tree is produced — a \
partial one would fail later inside another tool (REQ-WIT-001 clause 4)"
)]
MissingPackage {
root: PackageIdent,
missing: PackageIdent,
required_by: PackageIdent,
},
#[error(
"these WIT packages depend on each other in a cycle, which has no \
dependency order: {}",
.path.iter().map(|p| p.to_string()).collect::<Vec<_>>().join(" -> ")
)]
Cycle { path: Vec<PackageIdent> },
#[error(
"two different payloads both claim to be {ident}: sha256:{first} and \
sha256:{second}. One name must mean one set of bytes (REQ-STORE-002)"
)]
ConflictingIdentity {
ident: PackageIdent,
first: String,
second: String,
},
}
#[cfg(test)]
mod tests {
use super::*;
use std::str::FromStr;
fn encode(files: &[(&str, &str)], top: &str) -> Vec<u8> {
let mut resolve = wit_parser::Resolve::new();
let mut top_id = None;
for (name, source) in files {
let id = resolve.push_str(name, source).expect("fixture must parse");
if resolve.packages[id].name.to_string() == top {
top_id = Some(id);
}
}
wit_component::encode(
&resolve,
top_id.expect("fixture must define the top package"),
false,
)
.expect("fixture must encode")
}
const BASE: &str = "package acme:base@2.0.0;\ninterface b { type t = u32; }\n";
const LEFT: &str =
"package acme:left@1.0.0;\ninterface i { use acme:base/b@2.0.0.{t}; type l = t; }\n";
const RIGHT: &str =
"package acme:right@1.0.0;\ninterface i { use acme:base/b@2.0.0.{t}; type r = t; }\n";
const TOP: &str = "package acme:top@0.1.0;\ninterface i { use acme:left/i@1.0.0.{l}; \
use acme:right/i@1.0.0.{r}; type a = l; type c = r; }\n\
world w { import i; }\n";
fn ident(s: &str) -> PackageIdent {
PackageIdent::from_str(s).expect("test reference must parse")
}
fn diamond_index() -> PackageIndex {
let mut index = PackageIndex::new();
for bytes in [
encode(&[("base.wit", BASE)], "acme:base@2.0.0"),
encode(&[("base.wit", BASE), ("l.wit", LEFT)], "acme:left@1.0.0"),
encode(&[("base.wit", BASE), ("r.wit", RIGHT)], "acme:right@1.0.0"),
encode(
&[
("base.wit", BASE),
("l.wit", LEFT),
("r.wit", RIGHT),
("top.wit", TOP),
],
"acme:top@0.1.0",
),
] {
index.insert_binary(&bytes).expect("fixture must index");
}
index
}
#[test]
fn identity_and_imports_come_from_the_packages_own_bytes() {
let bytes = encode(&[("base.wit", BASE), ("l.wit", LEFT)], "acme:left@1.0.0");
let package = WitPackage::from_binary(&bytes).unwrap();
assert_eq!(package.ident(), &ident("acme:left@1.0.0"));
assert_eq!(package.ident().namespace(), "acme");
assert_eq!(package.ident().name(), "left");
assert_eq!(package.ident().version(), "1.0.0");
assert_eq!(
package.imports().iter().collect::<Vec<_>>(),
vec![&ident("acme:base@2.0.0")]
);
let dep = "package otherns:thing@3.1.4;\ninterface i { type t = u32; }\n";
let user = "package acme:user@0.0.1;\n\
interface i { use otherns:thing/i@3.1.4.{t}; type u = t; }\n";
let package =
WitPackage::from_binary(&encode(&[("d.wit", dep)], "otherns:thing@3.1.4")).unwrap();
assert_eq!(package.ident().namespace(), "otherns");
assert_eq!(package.ident().name(), "thing");
assert_eq!(package.ident().version(), "3.1.4");
let package = WitPackage::from_binary(&encode(
&[("d.wit", dep), ("u.wit", user)],
"acme:user@0.0.1",
))
.unwrap();
assert_eq!(
package.imports().iter().collect::<Vec<_>>(),
vec![&ident("otherns:thing@3.1.4")]
);
}
#[test]
fn a_diamond_visits_the_shared_base_exactly_once() {
let index = diamond_index();
let order = closure(&index, &ident("acme:top@0.1.0")).unwrap();
assert_eq!(
order
.iter()
.filter(|p| **p == ident("acme:base@2.0.0"))
.count(),
1,
"a diamond is a DAG, not a repetition: {order:?}"
);
assert_eq!(order.len(), 4, "{order:?}");
let at = |s: &str| order.iter().position(|p| *p == ident(s)).unwrap();
assert!(at("acme:base@2.0.0") < at("acme:left@1.0.0"));
assert!(at("acme:base@2.0.0") < at("acme:right@1.0.0"));
assert!(at("acme:left@1.0.0") < at("acme:top@0.1.0"));
assert!(at("acme:right@1.0.0") < at("acme:top@0.1.0"));
assert_eq!(order.last().unwrap(), &ident("acme:top@0.1.0"));
}
#[test]
fn a_cycle_is_refused_and_the_cycle_is_named() {
let a_stub = "package acme:a@1.0.0;\ninterface x { type ta = u32; }\n";
let b_stub = "package acme:b@1.0.0;\ninterface y { type tb = u64; }\n";
let a = "package acme:a@1.0.0;\ninterface x { use acme:b/y@1.0.0.{tb}; type ta = tb; }\n\
world w { import x; }\n";
let b = "package acme:b@1.0.0;\ninterface y { use acme:a/x@1.0.0.{ta}; type tb = ta; }\n\
world w { import y; }\n";
let mut index = PackageIndex::new();
index
.insert_binary(&encode(&[("b.wit", b_stub), ("a.wit", a)], "acme:a@1.0.0"))
.unwrap();
index
.insert_binary(&encode(&[("a.wit", a_stub), ("b.wit", b)], "acme:b@1.0.0"))
.unwrap();
let err = closure(&index, &ident("acme:a@1.0.0")).unwrap_err();
match &err {
WitClosureError::Cycle { path } => {
assert_eq!(path.first(), path.last(), "{path:?}");
assert_eq!(path.len(), 3, "{path:?}");
assert!(path.contains(&ident("acme:b@1.0.0")), "{path:?}");
}
other => panic!("expected a cycle, got {other:?}"),
}
assert!(
err.to_string().contains("acme:a@1.0.0 -> acme:b@1.0.0"),
"the message must show the cycle: {err}"
);
}
#[test]
fn a_missing_dependency_is_a_refusal_naming_it_not_a_partial_tree() {
let mut index = PackageIndex::new();
index
.insert_binary(&encode(
&[("base.wit", BASE), ("l.wit", LEFT)],
"acme:left@1.0.0",
))
.unwrap();
let err = closure(&index, &ident("acme:left@1.0.0")).unwrap_err();
assert_eq!(
err,
WitClosureError::MissingPackage {
root: ident("acme:left@1.0.0"),
missing: ident("acme:base@2.0.0"),
required_by: ident("acme:left@1.0.0"),
}
);
let text = err.to_string();
assert!(text.contains("acme:base@2.0.0"), "{text}");
assert!(text.contains("acme:left@1.0.0"), "{text}");
}
#[test]
fn a_root_the_layer_does_not_carry_is_its_own_refusal() {
let index = diamond_index();
let err = closure(&index, &ident("acme:absent@9.9.9")).unwrap_err();
assert_eq!(
err,
WitClosureError::RootMissing {
root: ident("acme:absent@9.9.9")
}
);
}
#[test]
fn the_order_depends_only_on_the_keys() {
let forwards = diamond_index();
let mut backwards = PackageIndex::new();
let mut payloads = vec![
encode(&[("base.wit", BASE)], "acme:base@2.0.0"),
encode(&[("base.wit", BASE), ("l.wit", LEFT)], "acme:left@1.0.0"),
encode(&[("base.wit", BASE), ("r.wit", RIGHT)], "acme:right@1.0.0"),
encode(
&[
("base.wit", BASE),
("l.wit", LEFT),
("r.wit", RIGHT),
("top.wit", TOP),
],
"acme:top@0.1.0",
),
];
payloads.reverse();
for bytes in &payloads {
backwards.insert_binary(bytes).unwrap();
}
let root = ident("acme:top@0.1.0");
let a = closure(&forwards, &root).unwrap();
let b = closure(&backwards, &root).unwrap();
assert_eq!(a, b, "insertion order must not reach the result");
assert_eq!(a, closure(&forwards, &root).unwrap());
assert_eq!(
a.iter().map(|p| p.to_string()).collect::<Vec<_>>(),
vec![
"acme:base@2.0.0",
"acme:left@1.0.0",
"acme:right@1.0.0",
"acme:top@0.1.0",
]
);
}
#[test]
fn one_name_may_not_mean_two_sets_of_bytes() {
let base = encode(&[("base.wit", BASE)], "acme:base@2.0.0");
let impostor = encode(
&[(
"base.wit",
"package acme:base@2.0.0;\ninterface b { type t = u64; }\n",
)],
"acme:base@2.0.0",
);
assert_ne!(base, impostor, "the fixture must actually differ");
let mut index = PackageIndex::new();
index.insert_binary(&base).unwrap();
index.insert_binary(&base).unwrap();
assert_eq!(index.len(), 1);
let err = index.insert_binary(&impostor).unwrap_err();
match err {
WitClosureError::ConflictingIdentity {
ident: id,
first,
second,
} => {
assert_eq!(id, ident("acme:base@2.0.0"));
assert_ne!(first, second);
}
other => panic!("expected a conflict, got {other:?}"),
}
assert_eq!(
index.get(&ident("acme:base@2.0.0")).unwrap().digest(),
&hex::encode(Sha256::digest(&base))
);
}
#[test]
fn build_metadata_is_part_of_the_identity() {
let one = encode(
&[(
"m.wit",
"package acme:m@1.0.0+build.one;\ninterface i { type t = u32; }\n",
)],
"acme:m@1.0.0+build.one",
);
let two = encode(
&[(
"m.wit",
"package acme:m@1.0.0+build.two;\ninterface i { type t = u64; }\n",
)],
"acme:m@1.0.0+build.two",
);
let mut index = PackageIndex::new();
index.insert_binary(&one).unwrap();
index.insert_binary(&two).unwrap();
assert_eq!(
index.len(),
2,
"two payloads, two slots: {:?}",
index.idents().collect::<Vec<_>>()
);
assert_ne!(
ident("acme:m@1.0.0+build.one"),
ident("acme:m@1.0.0+build.two")
);
assert_ne!(
ident("acme:m@1.0.0+build.one").binary_path(),
ident("acme:m@1.0.0+build.two").binary_path()
);
}
#[test]
fn only_a_wit_package_is_a_wit_payload() {
let core = [0x00, 0x61, 0x73, 0x6d, 0x01, 0x00, 0x00, 0x00];
assert_eq!(
WitPackage::from_binary(&core).unwrap_err(),
WitClosureError::NotAWitPackage
);
let err = WitPackage::from_binary(b"this is not wasm").unwrap_err();
assert!(
matches!(err, WitClosureError::Undecodable { .. }),
"{err:?}"
);
assert!(err.to_string().contains("magic"), "{err}");
}
#[test]
fn an_unversioned_package_has_no_slot_and_is_refused() {
let bytes = encode(
&[(
"u.wit",
"package acme:unversioned;\ninterface i { type t = u32; }\n",
)],
"acme:unversioned",
);
let err = WitPackage::from_binary(&bytes).unwrap_err();
assert_eq!(
err,
WitClosureError::Unversioned {
ident: "acme:unversioned".to_string()
}
);
}
#[test]
fn a_reference_round_trips_and_cannot_smuggle_a_path() {
let id = ident("wasi:io@0.2.0");
assert_eq!(id.to_string(), "wasi:io@0.2.0");
assert_eq!(id.binary_path(), "wasi/io/0.2.0.wasm");
assert_eq!(
ident("wasi:io@0.2.0-rc.1").binary_path(),
"wasi/io/0.2.0-rc.1.wasm"
);
for bad in [
"wasi:io", "wasi/io@0.2.0", ":io@0.2.0", "wasi:@0.2.0", "wasi:io@", "..:io@0.2.0", "wasi:..@0.2.0", "wasi:io@..", "wasi:io@../../etc", "wasi:i/o@0.2.0", "wasi:io@0.2.0:extra", ] {
let err = PackageIdent::from_str(bad).unwrap_err();
assert!(
matches!(err, WitClosureError::MalformedRef { .. }),
"{bad} should be refused, got {err:?}"
);
}
}
#[test]
fn the_index_reports_what_it_actually_holds() {
let empty = PackageIndex::new();
assert!(empty.is_empty(), "a fresh index is empty");
assert_eq!(empty.len(), 0);
assert_eq!(empty.idents().count(), 0);
let idx = diamond_index();
assert!(!idx.is_empty(), "an index holding packages is not empty");
assert_eq!(idx.len(), 4);
let got: Vec<String> = idx.idents().map(|i| i.as_str().to_string()).collect();
assert_eq!(got.len(), 4, "got {got:?}");
assert!(got.contains(&"acme:base@2.0.0".to_string()), "{got:?}");
let mut sorted = got.clone();
sorted.sort();
assert_eq!(got, sorted, "idents must yield key order: {got:?}");
let ident: PackageIdent = "acme:base@2.0.0".parse().unwrap();
assert_eq!(ident.as_str(), "acme:base@2.0.0");
}
#[test]
fn a_package_with_no_dependencies_closes_over_itself() {
let mut index = PackageIndex::new();
index
.insert_binary(&encode(&[("base.wit", BASE)], "acme:base@2.0.0"))
.unwrap();
assert_eq!(
closure(&index, &ident("acme:base@2.0.0")).unwrap(),
vec![ident("acme:base@2.0.0")]
);
}
}