A lightweight WebAssembly runtime that is fast, secure, and standards-compliant
use crate::collections::TryCow;
use crate::error::{Result, bail};
use crate::{Atom, StringPool, prelude::*};
use alloc::sync::Arc;
use core::borrow::Borrow;
use core::hash::Hash;
use semver::Version;
use serde_derive::{Deserialize, Serialize};
/// A semver-aware map for imports/exports of a component.
///
/// This data structure is used when looking up the names of imports/exports of
/// a component to enable semver-compatible matching of lookups. This will
/// enable lookups of `a:b/[email protected]` to match entries defined as `a:b/[email protected]`
/// which is currently considered a key feature of WASI's compatibility story.
///
/// On the outside this looks like a map of `K` to `V`.
#[derive(Serialize, Deserialize, Debug)]
pub struct NameMap<K, V>
where
K: TryClone + Hash + Eq + Ord,
{
/// A map of keys to the value that they define.
///
/// Note that this map is "exact" where the name here is the exact name that
/// was specified when the `insert` was called. This doesn't have any
/// semver-mangling or anything like that.
///
/// This map is always consulted first during lookups.
definitions: TryIndexMap<K, V>,
/// An auxiliary map tracking semver-compatible names. This is a map from
/// "semver compatible alternate name" to a name present in `definitions`
/// and the semver version it was registered at.
///
/// An example map would be:
///
/// ```text
/// {
/// "a:b/[email protected]": ("a:b/[email protected]", 0.2.1),
/// "a:b/c@2": ("a:b/[email protected]+abc", 2.0.0+abc),
/// }
/// ```
///
/// As names are inserted into `definitions` each name may have up to one
/// semver-compatible name with extra numbers/info chopped off which is
/// inserted into this map. This map is the lookup table from `@0.2` to
/// `@0.2.x` where `x` is what was inserted manually.
///
/// The `Version` here is tracked to ensure that when multiple versions on
/// one track are defined that only the maximal version here is retained.
alternate_lookups: TryIndexMap<K, (K, TryVersion)>,
}
/// A wrapper around `Version` that implements `TryClone`.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct TryVersion(Arc<Version>);
impl TryFrom<Version> for TryVersion {
type Error = OutOfMemory;
fn try_from(value: Version) -> Result<Self, Self::Error> {
Ok(Self(try_new::<Arc<_>>(value)?))
}
}
impl TryClone for TryVersion {
#[inline]
fn try_clone(&self) -> Result<Self, OutOfMemory> {
Ok(Self(self.0.clone()))
}
}
impl core::ops::Deref for TryVersion {
type Target = Version;
#[inline]
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl Borrow<Version> for TryVersion {
#[inline]
fn borrow(&self) -> &Version {
&self.0
}
}
impl serde::Serialize for TryVersion {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
self.0.serialize(serializer)
}
}
impl<'de> serde::Deserialize<'de> for TryVersion {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::Deserializer<'de>,
{
use serde::de::Error;
let v = Version::deserialize(deserializer)?;
let v = try_new::<Arc<_>>(v).map_err(|oom| D::Error::custom(oom))?;
Ok(Self(v))
}
}
impl<K, V> TryClone for NameMap<K, V>
where
K: TryClone + Hash + Eq + Ord,
V: TryClone,
{
fn try_clone(&self) -> Result<Self, OutOfMemory> {
Ok(Self {
definitions: self.definitions.try_clone()?,
alternate_lookups: self.alternate_lookups.try_clone()?,
})
}
}
impl<K, V> NameMap<K, V>
where
K: TryClone + Hash + Eq + Ord,
{
/// Inserts the `name` specified into this map.
///
/// The name is intern'd through the `cx` argument and shadowing is
/// controlled by the `allow_shadowing` variable.
///
/// This function will automatically insert an entry in
/// `self.alternate_lookups` if `name` is a semver-looking name.
///
/// Returns an error if `allow_shadowing` is `false` and the `name` is
/// already present in this map (by exact match). Otherwise returns the
/// intern'd version of `name`.
pub fn insert<I>(&mut self, name: &str, cx: &mut I, allow_shadowing: bool, item: V) -> Result<K>
where
I: NameMapIntern<Key = K>,
I::BorrowedKey: Hash + Eq,
{
// Always insert `name` and `item` as an exact definition.
let key = cx.intern(name)?;
if !allow_shadowing && self.definitions.contains_key(&key) {
bail!("map entry `{name}` defined twice")
}
self.definitions.insert(key.try_to_owned()?, item)?;
// If `name` is a semver-looking thing, like `a:b/[email protected]`, then also
// insert an entry in the semver-compatible map under a key such as
// `a:b/c@1`.
//
// This key is used during `get` later on.
if let Some((alternate_key, version)) = alternate_lookup_key(name) {
let alternate_key = cx.intern(alternate_key)?;
let version = TryVersion::try_from(version)?;
if let Some((prev_key, prev_version)) = self.alternate_lookups.insert(
alternate_key.try_clone()?,
(key.try_clone()?, version.clone()),
)? {
// Prefer the latest version, so only do this if we're
// greater than the prior version.
if version < prev_version {
self.alternate_lookups
.insert(alternate_key, (prev_key, prev_version))?;
}
}
}
Ok(key)
}
/// Looks up `name` within this map, using the interning specified by
/// `cx`.
///
/// This may return a definition even if `name` wasn't exactly defined in
/// this map, such as looking up `a:b/[email protected]` when the map only has
/// `a:b/[email protected]` defined.
pub fn get<I>(&self, name: &str, cx: &I) -> Option<&V>
where
I: NameMapIntern<Key = K>,
I::Key: Borrow<I::BorrowedKey>,
I::BorrowedKey: Hash + Eq,
{
// First look up an exact match and if that's found return that. This
// enables defining multiple versions in the map and the requested
// version is returned if it matches exactly.
let candidate = cx.lookup(name).and_then(|k| self.definitions.get(&*k));
if let Some(def) = candidate {
return Some(def);
}
// Failing that, then try to look for a semver-compatible alternative.
// This looks up the key based on `name`, if any, and then looks to see
// if that was intern'd in `strings`. Given all that look to see if it
// was defined in `alternate_lookups` and finally at the end that exact
// key is then used to look up again in `self.definitions`.
let (alternate_name, _version) = alternate_lookup_key(name)?;
let alternate_key = cx.lookup(alternate_name)?;
let (exact_key, _version) = self.alternate_lookups.get(&alternate_key)?;
self.definitions.get(exact_key.borrow())
}
/// Returns an iterator over inserted values in this map.
///
/// Note that the iterator return yields intern'd keys and additionally does
/// not do anything special with semver names and such, it only literally
/// yields what's been inserted with [`NameMap::insert`].
pub fn raw_iter(&self) -> impl Iterator<Item = (&K, &V)> {
self.definitions.iter()
}
/// TODO
pub fn raw_get_mut(&mut self, key: &K) -> Option<&mut V> {
self.definitions.get_mut(key)
}
}
impl<K, V> Default for NameMap<K, V>
where
K: TryClone + Hash + Eq + Ord,
{
fn default() -> NameMap<K, V> {
NameMap {
definitions: Default::default(),
alternate_lookups: Default::default(),
}
}
}
/// A helper trait used in conjunction with [`NameMap`] to optionally intern
/// keys to non-strings.
pub trait NameMapIntern {
/// The key that this interning context generates.
type Key: Borrow<Self::BorrowedKey>;
/// The borrowed version of the key type.
type BorrowedKey: ?Sized + TryToOwned<Owned = Self::Key>;
/// Inserts `s` into `self` and returns the intern'd key `Self::Key`.
fn intern(&mut self, s: &str) -> Result<Self::Key, OutOfMemory>;
/// Looks up `s` in `self` returning `Some` if it was found or `None` if
/// it's not present.
fn lookup<'a>(&'a self, s: &'a str) -> Option<TryCow<'a, Self::BorrowedKey>>;
}
/// For use with [`NameMap`] when no interning should happen and instead string
/// keys are copied as-is.
pub struct NameMapNoIntern;
impl NameMapIntern for NameMapNoIntern {
type Key = TryString;
type BorrowedKey = str;
fn intern(&mut self, s: &str) -> Result<Self::Key, OutOfMemory> {
TryString::try_from(s)
}
fn lookup<'a>(&'a self, s: &'a str) -> Option<TryCow<'a, Self::BorrowedKey>> {
Some(TryCow::Borrowed(s))
}
}
impl NameMapIntern for StringPool {
type Key = Atom;
type BorrowedKey = Atom;
fn intern(&mut self, string: &str) -> Result<Atom, OutOfMemory> {
self.insert(string)
}
fn lookup(&self, string: &str) -> Option<TryCow<'_, Atom>> {
self.get_atom(string).map(TryCow::Owned)
}
}
/// Determines a version-based "alternate lookup key" for the `name` specified.
///
/// Some examples are:
///
/// * `foo` => `None`
/// * `foo:bar/baz` => `None`
/// * `foo:bar/[email protected]` => `Some(foo:bar/baz@1)`
/// * `foo:bar/[email protected]` => `Some(foo:bar/[email protected])`
/// * `foo:bar/[email protected]` => `None`
/// * `foo:bar/[email protected]` => `None`
///
/// This alternate lookup key is intended to serve the purpose where a
/// semver-compatible definition can be located, if one is defined, at perhaps
/// either a newer or an older version.
pub fn alternate_lookup_key(name: &str) -> Option<(&str, Version)> {
let at = name.find('@')?;
let version_string = &name[at + 1..];
let version = Version::parse(version_string).ok()?;
if !version.pre.is_empty() {
// If there's a prerelease then don't consider that compatible with any
// other version number.
None
} else if version.major != 0 {
// If the major number is nonzero then compatibility is up to the major
// version number, so return up to the first decimal.
let first_dot = version_string.find('.')? + at + 1;
Some((&name[..first_dot], version))
} else if version.minor != 0 {
// Like the major version if the minor is nonzero then patch releases
// are all considered to be on a "compatible track".
let first_dot = version_string.find('.')? + at + 1;
let second_dot = name[first_dot + 1..].find('.')? + first_dot + 1;
Some((&name[..second_dot], version))
} else {
// If the patch number is the first nonzero entry then nothing can be
// compatible with this patch, e.g. 0.0.1 isn't' compatible with
// any other version inherently.
None
}
}
#[cfg(test)]
mod tests {
use super::{NameMap, NameMapNoIntern};
#[test]
fn alternate_lookup_key() {
fn alt(s: &str) -> Option<&str> {
super::alternate_lookup_key(s).map(|(s, _)| s)
}
assert_eq!(alt("x"), None);
assert_eq!(alt("x:y/z"), None);
assert_eq!(alt("x:y/[email protected]"), Some("x:y/z@1"));
assert_eq!(alt("x:y/[email protected]"), Some("x:y/z@1"));
assert_eq!(alt("x:y/[email protected]"), Some("x:y/z@1"));
assert_eq!(alt("x:y/[email protected]"), Some("x:y/z@2"));
assert_eq!(alt("x:y/[email protected]+abc"), Some("x:y/z@2"));
assert_eq!(alt("x:y/[email protected]"), Some("x:y/[email protected]"));
assert_eq!(alt("x:y/[email protected]"), Some("x:y/[email protected]"));
assert_eq!(alt("x:y/[email protected]"), Some("x:y/[email protected]"));
assert_eq!(alt("x:y/[email protected]+abc"), Some("x:y/[email protected]"));
assert_eq!(alt("x:y/[email protected]"), None);
assert_eq!(alt("x:y/[email protected]"), None);
assert_eq!(alt("x:y/[email protected]"), None);
assert_eq!(alt("x:y/[email protected]"), None);
}
#[test]
fn name_map_smoke() {
let mut map = NameMap::default();
let mut intern = NameMapNoIntern;
map.insert("a", &mut intern, false, 0).unwrap();
map.insert("b", &mut intern, false, 1).unwrap();
assert!(map.insert("a", &mut intern, false, 0).is_err());
assert!(map.insert("a", &mut intern, true, 0).is_ok());
assert_eq!(map.get("a", &intern), Some(&0));
assert_eq!(map.get("b", &intern), Some(&1));
assert_eq!(map.get("c", &intern), None);
map.insert("a:b/[email protected]", &mut intern, false, 2).unwrap();
map.insert("a:b/[email protected]", &mut intern, false, 3).unwrap();
assert_eq!(map.get("a:b/[email protected]", &intern), Some(&2));
assert_eq!(map.get("a:b/[email protected]", &intern), Some(&3));
assert_eq!(map.get("a:b/[email protected]", &intern), Some(&3));
assert_eq!(map.get("a:b/[email protected]", &intern), Some(&3));
}
}