wasmtime_environ/component/
names.rs

1use crate::collections::TryCow;
2use crate::error::{Result, bail};
3use crate::{Atom, StringPool, prelude::*};
4use alloc::sync::Arc;
5use core::borrow::Borrow;
6use core::hash::Hash;
7use semver::Version;
8use serde_derive::{Deserialize, Serialize};
9
10/// A semver-aware map for imports/exports of a component.
11///
12/// This data structure is used when looking up the names of imports/exports of
13/// a component to enable semver-compatible matching of lookups. This will
14/// enable lookups of `a:b/c@0.2.0` to match entries defined as `a:b/c@0.2.1`
15/// which is currently considered a key feature of WASI's compatibility story.
16///
17/// On the outside this looks like a map of `K` to `V`.
18#[derive(Serialize, Deserialize, Debug)]
19pub struct NameMap<K, V>
20where
21    K: TryClone + Hash + Eq + Ord,
22{
23    /// A map of keys to the value that they define.
24    ///
25    /// Note that this map is "exact" where the name here is the exact name that
26    /// was specified when the `insert` was called. This doesn't have any
27    /// semver-mangling or anything like that.
28    ///
29    /// This map is always consulted first during lookups.
30    definitions: TryIndexMap<K, V>,
31
32    /// An auxiliary map tracking semver-compatible names. This is a map from
33    /// "semver compatible alternate name" to a name present in `definitions`
34    /// and the semver version it was registered at.
35    ///
36    /// An example map would be:
37    ///
38    /// ```text
39    /// {
40    ///     "a:b/c@0.2": ("a:b/c@0.2.1", 0.2.1),
41    ///     "a:b/c@2": ("a:b/c@2.0.0+abc", 2.0.0+abc),
42    /// }
43    /// ```
44    ///
45    /// As names are inserted into `definitions` each name may have up to one
46    /// semver-compatible name with extra numbers/info chopped off which is
47    /// inserted into this map. This map is the lookup table from `@0.2` to
48    /// `@0.2.x` where `x` is what was inserted manually.
49    ///
50    /// The `Version` here is tracked to ensure that when multiple versions on
51    /// one track are defined that only the maximal version here is retained.
52    alternate_lookups: TryIndexMap<K, (K, TryVersion)>,
53}
54
55/// A wrapper around `Version` that implements `TryClone`.
56#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
57struct TryVersion(Arc<Version>);
58
59impl TryFrom<Version> for TryVersion {
60    type Error = OutOfMemory;
61
62    fn try_from(value: Version) -> Result<Self, Self::Error> {
63        Ok(Self(try_new::<Arc<_>>(value)?))
64    }
65}
66
67impl TryClone for TryVersion {
68    #[inline]
69    fn try_clone(&self) -> Result<Self, OutOfMemory> {
70        Ok(Self(self.0.clone()))
71    }
72}
73
74impl core::ops::Deref for TryVersion {
75    type Target = Version;
76
77    #[inline]
78    fn deref(&self) -> &Self::Target {
79        &self.0
80    }
81}
82
83impl Borrow<Version> for TryVersion {
84    #[inline]
85    fn borrow(&self) -> &Version {
86        &self.0
87    }
88}
89
90impl serde::Serialize for TryVersion {
91    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
92    where
93        S: serde::Serializer,
94    {
95        self.0.serialize(serializer)
96    }
97}
98
99impl<'de> serde::Deserialize<'de> for TryVersion {
100    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
101    where
102        D: serde::Deserializer<'de>,
103    {
104        use serde::de::Error;
105        let v = Version::deserialize(deserializer)?;
106        let v = try_new::<Arc<_>>(v).map_err(|oom| D::Error::custom(oom))?;
107        Ok(Self(v))
108    }
109}
110
111impl<K, V> TryClone for NameMap<K, V>
112where
113    K: TryClone + Hash + Eq + Ord,
114    V: TryClone,
115{
116    fn try_clone(&self) -> Result<Self, OutOfMemory> {
117        Ok(Self {
118            definitions: self.definitions.try_clone()?,
119            alternate_lookups: self.alternate_lookups.try_clone()?,
120        })
121    }
122}
123
124impl<K, V> NameMap<K, V>
125where
126    K: TryClone + Hash + Eq + Ord,
127{
128    /// Inserts the `name` specified into this map.
129    ///
130    /// The name is intern'd through the `cx` argument and shadowing is
131    /// controlled by the `allow_shadowing` variable.
132    ///
133    /// This function will automatically insert an entry in
134    /// `self.alternate_lookups` if `name` is a semver-looking name.
135    ///
136    /// Returns an error if `allow_shadowing` is `false` and the `name` is
137    /// already present in this map (by exact match). Otherwise returns the
138    /// intern'd version of `name`.
139    pub fn insert<I>(&mut self, name: &str, cx: &mut I, allow_shadowing: bool, item: V) -> Result<K>
140    where
141        I: NameMapIntern<Key = K>,
142        I::BorrowedKey: Hash + Eq,
143    {
144        // Always insert `name` and `item` as an exact definition.
145        let key = cx.intern(name)?;
146        if !allow_shadowing && self.definitions.contains_key(&key) {
147            bail!("map entry `{name}` defined twice")
148        }
149        self.definitions.insert(key.try_to_owned()?, item)?;
150
151        // If `name` is a semver-looking thing, like `a:b/c@1.0.0`, then also
152        // insert an entry in the semver-compatible map under a key such as
153        // `a:b/c@1`.
154        //
155        // This key is used during `get` later on.
156        if let Some((alternate_key, version)) = alternate_lookup_key(name) {
157            let alternate_key = cx.intern(alternate_key)?;
158            let version = TryVersion::try_from(version)?;
159            if let Some((prev_key, prev_version)) = self.alternate_lookups.insert(
160                alternate_key.try_clone()?,
161                (key.try_clone()?, version.clone()),
162            )? {
163                // Prefer the latest version, so only do this if we're
164                // greater than the prior version.
165                if version < prev_version {
166                    self.alternate_lookups
167                        .insert(alternate_key, (prev_key, prev_version))?;
168                }
169            }
170        }
171        Ok(key)
172    }
173
174    /// Looks up `name` within this map, using the interning specified by
175    /// `cx`.
176    ///
177    /// This may return a definition even if `name` wasn't exactly defined in
178    /// this map, such as looking up `a:b/c@0.2.0` when the map only has
179    /// `a:b/c@0.2.1` defined.
180    pub fn get<I>(&self, name: &str, cx: &I) -> Option<&V>
181    where
182        I: NameMapIntern<Key = K>,
183        I::Key: Borrow<I::BorrowedKey>,
184        I::BorrowedKey: Hash + Eq,
185    {
186        // First look up an exact match and if that's found return that. This
187        // enables defining multiple versions in the map and the requested
188        // version is returned if it matches exactly.
189        let candidate = cx.lookup(name).and_then(|k| self.definitions.get(&*k));
190        if let Some(def) = candidate {
191            return Some(def);
192        }
193
194        // Failing that, then try to look for a semver-compatible alternative.
195        // This looks up the key based on `name`, if any, and then looks to see
196        // if that was intern'd in `strings`. Given all that look to see if it
197        // was defined in `alternate_lookups` and finally at the end that exact
198        // key is then used to look up again in `self.definitions`.
199        let (alternate_name, _version) = alternate_lookup_key(name)?;
200        let alternate_key = cx.lookup(alternate_name)?;
201        let (exact_key, _version) = self.alternate_lookups.get(&alternate_key)?;
202        self.definitions.get(exact_key.borrow())
203    }
204
205    /// Returns an iterator over inserted values in this map.
206    ///
207    /// Note that the iterator return yields intern'd keys and additionally does
208    /// not do anything special with semver names and such, it only literally
209    /// yields what's been inserted with [`NameMap::insert`].
210    pub fn raw_iter(&self) -> impl Iterator<Item = (&K, &V)> {
211        self.definitions.iter()
212    }
213
214    /// TODO
215    pub fn raw_get_mut(&mut self, key: &K) -> Option<&mut V> {
216        self.definitions.get_mut(key)
217    }
218}
219
220impl<K, V> Default for NameMap<K, V>
221where
222    K: TryClone + Hash + Eq + Ord,
223{
224    fn default() -> NameMap<K, V> {
225        NameMap {
226            definitions: Default::default(),
227            alternate_lookups: Default::default(),
228        }
229    }
230}
231
232/// A helper trait used in conjunction with [`NameMap`] to optionally intern
233/// keys to non-strings.
234pub trait NameMapIntern {
235    /// The key that this interning context generates.
236    type Key: Borrow<Self::BorrowedKey>;
237
238    /// The borrowed version of the key type.
239    type BorrowedKey: ?Sized + TryToOwned<Owned = Self::Key>;
240
241    /// Inserts `s` into `self` and returns the intern'd key `Self::Key`.
242    fn intern(&mut self, s: &str) -> Result<Self::Key, OutOfMemory>;
243
244    /// Looks up `s` in `self` returning `Some` if it was found or `None` if
245    /// it's not present.
246    fn lookup<'a>(&'a self, s: &'a str) -> Option<TryCow<'a, Self::BorrowedKey>>;
247}
248
249/// For use with [`NameMap`] when no interning should happen and instead string
250/// keys are copied as-is.
251pub struct NameMapNoIntern;
252
253impl NameMapIntern for NameMapNoIntern {
254    type Key = TryString;
255    type BorrowedKey = str;
256
257    fn intern(&mut self, s: &str) -> Result<Self::Key, OutOfMemory> {
258        TryString::try_from(s)
259    }
260
261    fn lookup<'a>(&'a self, s: &'a str) -> Option<TryCow<'a, Self::BorrowedKey>> {
262        Some(TryCow::Borrowed(s))
263    }
264}
265
266impl NameMapIntern for StringPool {
267    type Key = Atom;
268    type BorrowedKey = Atom;
269
270    fn intern(&mut self, string: &str) -> Result<Atom, OutOfMemory> {
271        self.insert(string)
272    }
273
274    fn lookup(&self, string: &str) -> Option<TryCow<'_, Atom>> {
275        self.get_atom(string).map(TryCow::Owned)
276    }
277}
278
279/// Determines a version-based "alternate lookup key" for the `name` specified.
280///
281/// Some examples are:
282///
283/// * `foo` => `None`
284/// * `foo:bar/baz` => `None`
285/// * `foo:bar/baz@1.1.2` => `Some(foo:bar/baz@1)`
286/// * `foo:bar/baz@0.1.0` => `Some(foo:bar/baz@0.1)`
287/// * `foo:bar/baz@0.0.1` => `None`
288/// * `foo:bar/baz@0.1.0-rc.2` => `None`
289///
290/// This alternate lookup key is intended to serve the purpose where a
291/// semver-compatible definition can be located, if one is defined, at perhaps
292/// either a newer or an older version.
293fn alternate_lookup_key(name: &str) -> Option<(&str, Version)> {
294    let at = name.find('@')?;
295    let version_string = &name[at + 1..];
296    let version = Version::parse(version_string).ok()?;
297    if !version.pre.is_empty() {
298        // If there's a prerelease then don't consider that compatible with any
299        // other version number.
300        None
301    } else if version.major != 0 {
302        // If the major number is nonzero then compatibility is up to the major
303        // version number, so return up to the first decimal.
304        let first_dot = version_string.find('.')? + at + 1;
305        Some((&name[..first_dot], version))
306    } else if version.minor != 0 {
307        // Like the major version if the minor is nonzero then patch releases
308        // are all considered to be on a "compatible track".
309        let first_dot = version_string.find('.')? + at + 1;
310        let second_dot = name[first_dot + 1..].find('.')? + first_dot + 1;
311        Some((&name[..second_dot], version))
312    } else {
313        // If the patch number is the first nonzero entry then nothing can be
314        // compatible with this patch, e.g. 0.0.1 isn't' compatible with
315        // any other version inherently.
316        None
317    }
318}
319
320#[cfg(test)]
321mod tests {
322    use super::{NameMap, NameMapNoIntern};
323
324    #[test]
325    fn alternate_lookup_key() {
326        fn alt(s: &str) -> Option<&str> {
327            super::alternate_lookup_key(s).map(|(s, _)| s)
328        }
329
330        assert_eq!(alt("x"), None);
331        assert_eq!(alt("x:y/z"), None);
332        assert_eq!(alt("x:y/z@1.0.0"), Some("x:y/z@1"));
333        assert_eq!(alt("x:y/z@1.1.0"), Some("x:y/z@1"));
334        assert_eq!(alt("x:y/z@1.1.2"), Some("x:y/z@1"));
335        assert_eq!(alt("x:y/z@2.1.2"), Some("x:y/z@2"));
336        assert_eq!(alt("x:y/z@2.1.2+abc"), Some("x:y/z@2"));
337        assert_eq!(alt("x:y/z@0.1.2"), Some("x:y/z@0.1"));
338        assert_eq!(alt("x:y/z@0.1.3"), Some("x:y/z@0.1"));
339        assert_eq!(alt("x:y/z@0.2.3"), Some("x:y/z@0.2"));
340        assert_eq!(alt("x:y/z@0.2.3+abc"), Some("x:y/z@0.2"));
341        assert_eq!(alt("x:y/z@0.0.1"), None);
342        assert_eq!(alt("x:y/z@0.0.1-pre"), None);
343        assert_eq!(alt("x:y/z@0.1.0-pre"), None);
344        assert_eq!(alt("x:y/z@1.0.0-pre"), None);
345    }
346
347    #[test]
348    fn name_map_smoke() {
349        let mut map = NameMap::default();
350        let mut intern = NameMapNoIntern;
351
352        map.insert("a", &mut intern, false, 0).unwrap();
353        map.insert("b", &mut intern, false, 1).unwrap();
354
355        assert!(map.insert("a", &mut intern, false, 0).is_err());
356        assert!(map.insert("a", &mut intern, true, 0).is_ok());
357
358        assert_eq!(map.get("a", &intern), Some(&0));
359        assert_eq!(map.get("b", &intern), Some(&1));
360        assert_eq!(map.get("c", &intern), None);
361
362        map.insert("a:b/c@1.0.0", &mut intern, false, 2).unwrap();
363        map.insert("a:b/c@1.0.1", &mut intern, false, 3).unwrap();
364        assert_eq!(map.get("a:b/c@1.0.0", &intern), Some(&2));
365        assert_eq!(map.get("a:b/c@1.0.1", &intern), Some(&3));
366        assert_eq!(map.get("a:b/c@1.0.2", &intern), Some(&3));
367        assert_eq!(map.get("a:b/c@1.1.0", &intern), Some(&3));
368    }
369}
wasmtime_environ/component/names.rs

wasmtime_environ/component/
names.rs
