miden_assembly/library/
path.rs

1use alloc::{
2    borrow::Cow,
3    string::{String, ToString},
4    sync::Arc,
5    vec::Vec,
6};
7use core::{
8    fmt,
9    str::{self, FromStr},
10};
11
12use smallvec::smallvec;
13
14use crate::{
15    ByteReader, ByteWriter, Deserializable, DeserializationError, LibraryNamespace, Serializable,
16    Span,
17    ast::{Ident, IdentError},
18};
19
20/// Represents errors that can occur when creating, parsing, or manipulating [LibraryPath]s
21#[derive(Debug, thiserror::Error)]
22pub enum PathError {
23    #[error("invalid library path: cannot be empty")]
24    Empty,
25    #[error("invalid library path component: cannot be empty")]
26    EmptyComponent,
27    #[error("invalid library path component: {0}")]
28    InvalidComponent(crate::ast::IdentError),
29    #[error("invalid library path: contains invalid utf8 byte sequences")]
30    InvalidUtf8,
31    #[error(transparent)]
32    InvalidNamespace(crate::library::LibraryNamespaceError),
33    #[error("cannot join a path with reserved name to other paths")]
34    UnsupportedJoin,
35}
36
37// LIBRARY PATH COMPONENT
38// ================================================================================================
39
40/// Represents a component of a [LibraryPath] in [LibraryPath::components]
41pub enum LibraryPathComponent<'a> {
42    /// The first component of the path, and the namespace of the path
43    Namespace(&'a LibraryNamespace),
44    /// A non-namespace component of the path
45    Normal(&'a Ident),
46}
47
48impl<'a> LibraryPathComponent<'a> {
49    /// Get this component as a [prim@str]
50    #[inline(always)]
51    pub fn as_str(&self) -> &'a str {
52        match self {
53            Self::Namespace(ns) => ns.as_str(),
54            Self::Normal(id) => id.as_str(),
55        }
56    }
57
58    /// Get this component as an [Ident]
59    #[inline]
60    pub fn to_ident(&self) -> Ident {
61        match self {
62            Self::Namespace(ns) => ns.to_ident(),
63            Self::Normal(id) => Ident::clone(id),
64        }
65    }
66}
67
68impl Eq for LibraryPathComponent<'_> {}
69
70impl PartialEq for LibraryPathComponent<'_> {
71    fn eq(&self, other: &Self) -> bool {
72        match (self, other) {
73            (Self::Namespace(a), Self::Namespace(b)) => a == b,
74            (Self::Normal(a), Self::Normal(b)) => a == b,
75            _ => false,
76        }
77    }
78}
79
80impl PartialEq<str> for LibraryPathComponent<'_> {
81    fn eq(&self, other: &str) -> bool {
82        self.as_ref().eq(other)
83    }
84}
85
86impl AsRef<str> for LibraryPathComponent<'_> {
87    fn as_ref(&self) -> &str {
88        match self {
89            Self::Namespace(ns) => ns.as_str(),
90            Self::Normal(ident) => ident.as_str(),
91        }
92    }
93}
94
95impl fmt::Display for LibraryPathComponent<'_> {
96    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
97        f.write_str(self.as_ref())
98    }
99}
100
101impl From<LibraryPathComponent<'_>> for Ident {
102    #[inline]
103    fn from(component: LibraryPathComponent<'_>) -> Self {
104        component.to_ident()
105    }
106}
107
108/// This is a convenience type alias for a smallvec of [Ident]
109type Components = smallvec::SmallVec<[Ident; 1]>;
110
111// LIBRARY PATH
112// ================================================================================================
113
114/// Path to a module or a procedure.
115#[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
116pub struct LibraryPath {
117    inner: Arc<LibraryPathInner>,
118}
119
120/// The data of a [LibraryPath] is allocated on the heap to make a [LibraryPath] the size of a
121/// pointer, rather than the size of 4 pointers. This makes them cheap to clone and move around.
122#[derive(Default, Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
123struct LibraryPathInner {
124    /// The namespace of this library path
125    ns: LibraryNamespace,
126    /// The individual components of the path, i.e. the parts delimited by `::`
127    components: Components,
128}
129
130impl LibraryPath {
131    /// Returns a new path created from the provided source.
132    ///
133    /// A path consists of at list of components separated by `::` delimiter. A path must contain
134    /// at least one component.
135    ///
136    /// # Errors
137    ///
138    /// Returns an error if:
139    ///
140    /// * The path is empty.
141    /// * The path prefix represents an invalid namespace, see [LibraryNamespace] for details.
142    /// * Any component of the path is empty.
143    /// * Any component is not a valid identifier (quoted or unquoted) in Miden Assembly syntax,
144    ///   i.e. starts with an ASCII alphabetic character, contains only printable ASCII characters,
145    ///   except for `::`, which must only be used as a path separator.
146    pub fn new(source: impl AsRef<str>) -> Result<Self, PathError> {
147        let source = source.as_ref();
148        if source.is_empty() {
149            return Err(PathError::Empty);
150        }
151
152        // Parse namespace
153        let mut parts = source.split("::");
154        let ns = parts
155            .next()
156            .ok_or(PathError::Empty)
157            .and_then(|part| LibraryNamespace::new(part).map_err(PathError::InvalidNamespace))?;
158
159        // Parse components
160        let mut components = Components::default();
161        parts.map(Ident::new).try_for_each(|part| {
162            part.map_err(PathError::InvalidComponent).map(|c| components.push(c))
163        })?;
164
165        Ok(Self::make(ns, components))
166    }
167
168    /// Create a [LibraryPath] from pre-validated components
169    pub fn new_from_components<I>(ns: LibraryNamespace, components: I) -> Self
170    where
171        I: IntoIterator<Item = Ident>,
172    {
173        Self::make(ns, components.into_iter().collect())
174    }
175
176    #[inline]
177    fn make(ns: LibraryNamespace, components: Components) -> Self {
178        Self {
179            inner: Arc::new(LibraryPathInner { ns, components }),
180        }
181    }
182}
183
184/// Path metadata
185impl LibraryPath {
186    /// Return the size of this path in [char]s when displayed as a string
187    #[allow(clippy::len_without_is_empty)]
188    pub fn len(&self) -> usize {
189        self.inner.components.iter().map(|c| c.len()).sum::<usize>()
190            + self.inner.ns.as_str().len()
191            + (self.inner.components.len() * 2)
192    }
193
194    /// Return the size in bytes of this path when displayed as a string
195    pub fn byte_len(&self) -> usize {
196        self.inner.components.iter().map(|c| c.len()).sum::<usize>()
197            + self.inner.ns.as_str().len()
198            + (self.inner.components.len() * 2)
199    }
200
201    /// Returns the full path of the Library as a string
202    pub fn path(&self) -> Cow<'_, str> {
203        if self.inner.components.is_empty() {
204            Cow::Borrowed(self.inner.ns.as_str())
205        } else {
206            Cow::Owned(self.to_string())
207        }
208    }
209
210    /// Return the namespace component of this path
211    pub fn namespace(&self) -> &LibraryNamespace {
212        &self.inner.ns
213    }
214
215    /// Returns the last component of the path as a `str`
216    pub fn last(&self) -> &str {
217        self.last_component().as_str()
218    }
219
220    /// Returns the last component of the path.
221    pub fn last_component(&self) -> LibraryPathComponent<'_> {
222        self.inner
223            .components
224            .last()
225            .map(LibraryPathComponent::Normal)
226            .unwrap_or_else(|| LibraryPathComponent::Namespace(&self.inner.ns))
227    }
228
229    /// Returns the number of components in the path.
230    ///
231    /// This is guaranteed to return at least 1.
232    pub fn num_components(&self) -> usize {
233        self.inner.components.len() + 1
234    }
235
236    /// Returns an iterator over all components of the path.
237    pub fn components(&self) -> impl Iterator<Item = LibraryPathComponent> + '_ {
238        core::iter::once(LibraryPathComponent::Namespace(&self.inner.ns))
239            .chain(self.inner.components.iter().map(LibraryPathComponent::Normal))
240    }
241
242    /// Returns true if this path is for a kernel module.
243    pub fn is_kernel_path(&self) -> bool {
244        matches!(self.inner.ns, LibraryNamespace::Kernel)
245    }
246
247    /// Returns true if this path is for an executable module.
248    pub fn is_exec_path(&self) -> bool {
249        matches!(self.inner.ns, LibraryNamespace::Exec)
250    }
251
252    /// Returns true if this path is for an anonymous module.
253    pub fn is_anon_path(&self) -> bool {
254        matches!(self.inner.ns, LibraryNamespace::Anon)
255    }
256
257    /// Returns true if `self` starts with `other`
258    pub fn starts_with(&self, other: &LibraryPath) -> bool {
259        let mut a = self.components();
260        let mut b = other.components();
261        loop {
262            match (a.next(), b.next()) {
263                // If we reach the end of `other`, it's a match
264                (_, None) => break true,
265                // If we reach the end of `self` first, it can't start with `other`
266                (None, _) => break false,
267                (Some(a), Some(b)) => {
268                    // If the two components do not match, we have our answer
269                    if a != b {
270                        break false;
271                    }
272                },
273            }
274        }
275    }
276}
277
278/// Mutation
279impl LibraryPath {
280    /// Override the current [LibraryNamespace] for this path.
281    pub fn set_namespace(&mut self, ns: LibraryNamespace) {
282        let inner = Arc::make_mut(&mut self.inner);
283        inner.ns = ns;
284    }
285
286    /// Appends the provided path to this path and returns the result.
287    ///
288    /// # Errors
289    ///
290    /// Returns an error if the join would produce an invalid path. For example, paths with
291    /// reserved namespaces may not be joined to other paths.
292    pub fn join(&self, other: &Self) -> Result<Self, PathError> {
293        if other.inner.ns.is_reserved() {
294            return Err(PathError::UnsupportedJoin);
295        }
296
297        let mut path = self.clone();
298        {
299            let inner = Arc::make_mut(&mut path.inner);
300            inner.components.push(other.inner.ns.to_ident());
301            inner.components.extend(other.inner.components.iter().cloned());
302        }
303
304        Ok(path)
305    }
306
307    /// Append the given component to this path.
308    ///
309    /// Returns an error if the component is not valid.
310    pub fn push(&mut self, component: impl AsRef<str>) -> Result<(), PathError> {
311        let component = component.as_ref().parse::<Ident>().map_err(PathError::InvalidComponent)?;
312        self.push_ident(component);
313        Ok(())
314    }
315
316    /// Append an [Ident] as a component to this path
317    pub fn push_ident(&mut self, component: Ident) {
318        let inner = Arc::make_mut(&mut self.inner);
319        inner.components.push(component);
320    }
321
322    /// Appends the provided component to the end of this path and returns the result.
323    ///
324    /// Returns an error if the input string is not a valid component.
325    pub fn append<S>(&self, component: S) -> Result<Self, PathError>
326    where
327        S: AsRef<str>,
328    {
329        let mut path = self.clone();
330        path.push(component)?;
331        Ok(path)
332    }
333
334    /// Appends the provided component to the end of this path and returns the result.
335    ///
336    /// Returns an error if the input string is not a valid component.
337    pub fn append_ident(&self, component: Ident) -> Result<Self, PathError> {
338        let mut path = self.clone();
339        path.push_ident(component);
340        Ok(path)
341    }
342
343    /// Adds the provided component to the front of this path and returns the result.
344    ///
345    /// # Errors
346    ///
347    /// Returns an error if:
348    ///
349    /// * The input string is not a valid [LibraryNamespace]
350    /// * The current namespace is a reserved identifier and therefore not a valid path component
351    pub fn prepend<S>(&self, component: S) -> Result<Self, PathError>
352    where
353        S: AsRef<str>,
354    {
355        let ns = component
356            .as_ref()
357            .parse::<LibraryNamespace>()
358            .map_err(PathError::InvalidNamespace)?;
359        let component = self.inner.ns.to_ident();
360        let mut components = smallvec![component];
361        components.extend(self.inner.components.iter().cloned());
362        Ok(Self::make(ns, components))
363    }
364
365    /// Pops the last non-namespace component in this path
366    pub fn pop(&mut self) -> Option<Ident> {
367        let inner = Arc::make_mut(&mut self.inner);
368        inner.components.pop()
369    }
370
371    /// Returns a new path, representing the current one with the last non-namespace component
372    /// removed.
373    pub fn strip_last(&self) -> Option<Self> {
374        match self.inner.components.len() {
375            0 => None,
376            1 => Some(Self::make(self.inner.ns.clone(), smallvec![])),
377            _ => {
378                let ns = self.inner.ns.clone();
379                let mut components = self.inner.components.clone();
380                components.pop();
381                Some(Self::make(ns, components))
382            },
383        }
384    }
385
386    /// Checks if the given input string is a valid [LibraryPath], returning the number of
387    /// components in the path.
388    ///
389    /// See the documentation of [LibraryPath::new] for details on what constitutes a valid path.
390    pub fn validate<S>(source: S) -> Result<usize, PathError>
391    where
392        S: AsRef<str>,
393    {
394        let source = source.as_ref();
395
396        let mut count = 0;
397        let mut components = source.split("::");
398
399        let ns = components.next().ok_or(PathError::Empty)?;
400        LibraryNamespace::validate(ns).map_err(PathError::InvalidNamespace)?;
401        count += 1;
402
403        for component in components {
404            validate_component(component)?;
405            count += 1;
406        }
407
408        Ok(count)
409    }
410
411    /// Returns a new [LibraryPath] with the given component appended without any validation.
412    ///
413    /// The caller is expected to uphold the validity invariants of [LibraryPath].
414    pub fn append_unchecked<S>(&self, component: S) -> Self
415    where
416        S: AsRef<str>,
417    {
418        let component = component.as_ref().to_string().into_boxed_str();
419        let component = Ident::from_raw_parts(Span::unknown(Arc::from(component)));
420        let mut path = self.clone();
421        path.push_ident(component);
422        path
423    }
424}
425
426impl<'a> TryFrom<Vec<LibraryPathComponent<'a>>> for LibraryPath {
427    type Error = PathError;
428    fn try_from(iter: Vec<LibraryPathComponent<'a>>) -> Result<Self, Self::Error> {
429        let mut iter = iter.into_iter();
430        let ns = match iter.next() {
431            None => return Err(PathError::Empty),
432            Some(LibraryPathComponent::Namespace(ns)) => ns.clone(),
433            Some(LibraryPathComponent::Normal(ident)) => {
434                LibraryNamespace::try_from(ident.clone()).map_err(PathError::InvalidNamespace)?
435            },
436        };
437        let mut components = Components::default();
438        for component in iter {
439            match component {
440                LibraryPathComponent::Normal(ident) => components.push(ident.clone()),
441                LibraryPathComponent::Namespace(LibraryNamespace::User(name)) => {
442                    components.push(Ident::from_raw_parts(Span::unknown(name.clone())));
443                },
444                LibraryPathComponent::Namespace(_) => return Err(PathError::UnsupportedJoin),
445            }
446        }
447        Ok(Self::make(ns, components))
448    }
449}
450
451impl From<LibraryNamespace> for LibraryPath {
452    fn from(ns: LibraryNamespace) -> Self {
453        Self::make(ns, smallvec![])
454    }
455}
456
457impl From<LibraryPath> for String {
458    fn from(path: LibraryPath) -> Self {
459        path.to_string()
460    }
461}
462
463impl TryFrom<String> for LibraryPath {
464    type Error = PathError;
465
466    #[inline]
467    fn try_from(value: String) -> Result<Self, Self::Error> {
468        Self::new(value)
469    }
470}
471
472impl<'a> TryFrom<&'a str> for LibraryPath {
473    type Error = PathError;
474
475    #[inline]
476    fn try_from(value: &'a str) -> Result<Self, Self::Error> {
477        Self::new(value)
478    }
479}
480
481impl FromStr for LibraryPath {
482    type Err = PathError;
483
484    #[inline]
485    fn from_str(value: &str) -> Result<Self, Self::Err> {
486        Self::new(value)
487    }
488}
489
490impl Serializable for LibraryPath {
491    fn write_into<W: ByteWriter>(&self, target: &mut W) {
492        let len = self.byte_len();
493
494        target.write_u16(len as u16);
495        target.write_bytes(self.inner.ns.as_str().as_bytes());
496        for component in self.inner.components.iter() {
497            target.write_bytes(b"::");
498            target.write_bytes(component.as_str().as_bytes());
499        }
500    }
501}
502
503impl Deserializable for LibraryPath {
504    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
505        let len = source.read_u16()? as usize;
506        let path = source.read_slice(len)?;
507        let path =
508            str::from_utf8(path).map_err(|e| DeserializationError::InvalidValue(e.to_string()))?;
509        Self::new(path).map_err(|e| DeserializationError::InvalidValue(e.to_string()))
510    }
511}
512
513impl fmt::Display for LibraryPath {
514    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
515        write!(f, "{}", self.inner.ns)?;
516        for component in self.inner.components.iter() {
517            write!(f, "::{component}")?;
518        }
519        Ok(())
520    }
521}
522
523fn validate_component(component: &str) -> Result<(), PathError> {
524    if component.is_empty() {
525        Err(PathError::EmptyComponent)
526    } else if component.len() > LibraryNamespace::MAX_LENGTH {
527        Err(PathError::InvalidComponent(IdentError::InvalidLength {
528            max: LibraryNamespace::MAX_LENGTH,
529        }))
530    } else {
531        Ident::validate(component).map_err(PathError::InvalidComponent)
532    }
533}
534
535// ARBITRARY IMPLEMENTATION
536// ================================================================================================
537
538#[cfg(feature = "testing")]
539impl proptest::prelude::Arbitrary for LibraryPath {
540    type Parameters = ();
541
542    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
543        use proptest::prelude::*;
544
545        let wasm_cm_style = LibraryPath::new_from_components(
546            LibraryNamespace::Anon,
547            [Ident::new("namespace-kebab:package-kebab/interface-kebab@1.0.0").unwrap()],
548        );
549        let path_len_2 = LibraryPath::new_from_components(
550            LibraryNamespace::User("user_ns".into()),
551            [Ident::new("user_module").unwrap()],
552        );
553        let path_len_3 = LibraryPath::new_from_components(
554            LibraryNamespace::User("userns".into()),
555            [Ident::new("user_path1").unwrap(), Ident::new("user_module").unwrap()],
556        );
557        prop_oneof![Just(wasm_cm_style), Just(path_len_2), Just(path_len_3)].boxed()
558    }
559
560    type Strategy = proptest::prelude::BoxedStrategy<Self>;
561}
562
563// TESTS
564// ================================================================================================
565
566/// Tests
567#[cfg(test)]
568mod tests {
569
570    use proptest::prelude::*;
571    use vm_core::{
572        assert_matches,
573        utils::{Deserializable, Serializable},
574    };
575
576    use super::{super::LibraryNamespaceError, IdentError, LibraryPath, PathError};
577
578    #[test]
579    fn new_path() {
580        let path = LibraryPath::new("foo").unwrap();
581        assert_eq!(path.num_components(), 1);
582
583        let path = LibraryPath::new("foo::bar").unwrap();
584        assert_eq!(path.num_components(), 2);
585
586        let path = LibraryPath::new("foo::bar::baz").unwrap();
587        assert_eq!(path.num_components(), 3);
588
589        let path = LibraryPath::new("miden:base/account@0.1.0").unwrap();
590        assert_eq!(path.num_components(), 1);
591
592        let path = LibraryPath::new("#exec::bar::baz").unwrap();
593        assert_eq!(path.num_components(), 3);
594
595        let path = LibraryPath::new("#sys::bar::baz").unwrap();
596        assert_eq!(path.num_components(), 3);
597    }
598
599    #[test]
600    fn new_path_fail() {
601        let path = LibraryPath::new("");
602        assert_matches!(path, Err(PathError::Empty));
603
604        let path = LibraryPath::new("::");
605        assert_matches!(path, Err(PathError::InvalidNamespace(LibraryNamespaceError::Empty)));
606
607        let path = LibraryPath::new("foo::");
608        assert_matches!(path, Err(PathError::InvalidComponent(IdentError::Empty)));
609
610        let path = LibraryPath::new("::foo");
611        assert_matches!(path, Err(PathError::InvalidNamespace(LibraryNamespaceError::Empty)));
612
613        let path = LibraryPath::new("#foo::bar");
614        assert_matches!(
615            path,
616            Err(PathError::InvalidNamespace(LibraryNamespaceError::InvalidStart))
617        );
618    }
619
620    proptest! {
621        #[test]
622        fn path_serialization_roundtrip(path in any::<LibraryPath>()) {
623            let bytes = path.to_bytes();
624            let deserialized = LibraryPath::read_from_bytes(&bytes).unwrap();
625            assert_eq!(path, deserialized);
626        }
627    }
628}
miden_assembly/library/path.rs

miden_assembly/library/
path.rs
