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

miden_assembly_syntax/library/
path.rs
