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

miden_assembly_syntax/library/
path.rs
