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    ast::{Ident, IdentError},
16    ByteReader, ByteWriter, Deserializable, DeserializationError, LibraryNamespace, Serializable,
17    Span,
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 bare identifier in Miden Assembly syntax, i.e. lowercase
144    ///   alphanumeric with underscores allowed, starts with alphabetic character.
145    pub fn new(source: impl AsRef<str>) -> Result<Self, PathError> {
146        let source = source.as_ref();
147        if source.is_empty() {
148            return Err(PathError::Empty);
149        }
150
151        // Parse namespace
152        let mut parts = source.split("::");
153        let ns = parts
154            .next()
155            .ok_or(PathError::Empty)
156            .and_then(|part| LibraryNamespace::new(part).map_err(PathError::InvalidNamespace))?;
157
158        // Parse components
159        let mut components = Components::default();
160        parts.map(Ident::new).try_for_each(|part| {
161            part.map_err(PathError::InvalidComponent).map(|c| components.push(c))
162        })?;
163
164        Ok(Self::make(ns, components))
165    }
166
167    /// Create a [LibraryPath] from pre-validated components
168    pub fn new_from_components<I>(ns: LibraryNamespace, components: I) -> Self
169    where
170        I: IntoIterator<Item = Ident>,
171    {
172        Self::make(ns, components.into_iter().collect())
173    }
174
175    #[inline]
176    fn make(ns: LibraryNamespace, components: Components) -> Self {
177        Self {
178            inner: Arc::new(LibraryPathInner { ns, components }),
179        }
180    }
181}
182
183/// Path metadata
184impl LibraryPath {
185    /// Return the size of this path in [char]s when displayed as a string
186    #[allow(clippy::len_without_is_empty)]
187    pub fn len(&self) -> usize {
188        self.inner.components.iter().map(|c| c.len()).sum::<usize>()
189            + self.inner.ns.as_str().len()
190            + (self.inner.components.len() * 2)
191    }
192
193    /// Return the size in bytes of this path when displayed as a string
194    pub fn byte_len(&self) -> usize {
195        self.inner.components.iter().map(|c| c.len()).sum::<usize>()
196            + self.inner.ns.as_str().len()
197            + (self.inner.components.len() * 2)
198    }
199
200    /// Returns the full path of the Library as a string
201    pub fn path(&self) -> Cow<'_, str> {
202        if self.inner.components.is_empty() {
203            Cow::Borrowed(self.inner.ns.as_str())
204        } else {
205            Cow::Owned(self.to_string())
206        }
207    }
208
209    /// Return the namespace component of this path
210    pub fn namespace(&self) -> &LibraryNamespace {
211        &self.inner.ns
212    }
213
214    /// Returns the last component of the path as a `str`
215    pub fn last(&self) -> &str {
216        self.last_component().as_str()
217    }
218
219    /// Returns the last component of the path.
220    pub fn last_component(&self) -> LibraryPathComponent<'_> {
221        self.inner
222            .components
223            .last()
224            .map(LibraryPathComponent::Normal)
225            .unwrap_or_else(|| LibraryPathComponent::Namespace(&self.inner.ns))
226    }
227
228    /// Returns the number of components in the path.
229    ///
230    /// This is guaranteed to return at least 1.
231    pub fn num_components(&self) -> usize {
232        self.inner.components.len() + 1
233    }
234
235    /// Returns an iterator over all components of the path.
236    pub fn components(&self) -> impl Iterator<Item = LibraryPathComponent> + '_ {
237        core::iter::once(LibraryPathComponent::Namespace(&self.inner.ns))
238            .chain(self.inner.components.iter().map(LibraryPathComponent::Normal))
239    }
240
241    /// Returns true if this path is for a kernel module.
242    pub fn is_kernel_path(&self) -> bool {
243        matches!(self.inner.ns, LibraryNamespace::Kernel)
244    }
245
246    /// Returns true if this path is for an executable module.
247    pub fn is_exec_path(&self) -> bool {
248        matches!(self.inner.ns, LibraryNamespace::Exec)
249    }
250
251    /// Returns true if this path is for an anonymous module.
252    pub fn is_anon_path(&self) -> bool {
253        matches!(self.inner.ns, LibraryNamespace::Anon)
254    }
255
256    /// Returns true if `self` starts with `other`
257    pub fn starts_with(&self, other: &LibraryPath) -> bool {
258        let mut a = self.components();
259        let mut b = other.components();
260        loop {
261            match (a.next(), b.next()) {
262                // If we reach the end of `other`, it's a match
263                (_, None) => break true,
264                // If we reach the end of `self` first, it can't start with `other`
265                (None, _) => break false,
266                (Some(a), Some(b)) => {
267                    // If the two components do not match, we have our answer
268                    if a != b {
269                        break false;
270                    }
271                },
272            }
273        }
274    }
275}
276
277/// Mutation
278impl LibraryPath {
279    /// Override the current [LibraryNamespace] for this path.
280    pub fn set_namespace(&mut self, ns: LibraryNamespace) {
281        let inner = Arc::make_mut(&mut self.inner);
282        inner.ns = ns;
283    }
284
285    /// Appends the provided path to this path and returns the result.
286    ///
287    /// # Errors
288    ///
289    /// Returns an error if the join would produce an invalid path. For example, paths with
290    /// reserved namespaces may not be joined to other paths.
291    pub fn join(&self, other: &Self) -> Result<Self, PathError> {
292        if other.inner.ns.is_reserved() {
293            return Err(PathError::UnsupportedJoin);
294        }
295
296        let mut path = self.clone();
297        {
298            let inner = Arc::make_mut(&mut path.inner);
299            inner.components.push(other.inner.ns.to_ident());
300            inner.components.extend(other.inner.components.iter().cloned());
301        }
302
303        Ok(path)
304    }
305
306    /// Append the given component to this path.
307    ///
308    /// Returns an error if the component is not valid.
309    pub fn push(&mut self, component: impl AsRef<str>) -> Result<(), PathError> {
310        let component = component.as_ref().parse::<Ident>().map_err(PathError::InvalidComponent)?;
311        self.push_ident(component);
312        Ok(())
313    }
314
315    /// Append an [Ident] as a component to this path
316    pub fn push_ident(&mut self, component: Ident) {
317        let inner = Arc::make_mut(&mut self.inner);
318        inner.components.push(component);
319    }
320
321    /// Appends the provided component to the end of this path and returns the result.
322    ///
323    /// Returns an error if the input string is not a valid component.
324    pub fn append<S>(&self, component: S) -> Result<Self, PathError>
325    where
326        S: AsRef<str>,
327    {
328        let mut path = self.clone();
329        path.push(component)?;
330        Ok(path)
331    }
332
333    /// Appends the provided component to the end of this path and returns the result.
334    ///
335    /// Returns an error if the input string is not a valid component.
336    pub fn append_ident(&self, component: Ident) -> Result<Self, PathError> {
337        let mut path = self.clone();
338        path.push_ident(component);
339        Ok(path)
340    }
341
342    /// Adds the provided component to the front of this path and returns the result.
343    ///
344    /// # Errors
345    ///
346    /// Returns an error if:
347    ///
348    /// * The input string is not a valid [LibraryNamespace]
349    /// * The current namespace is a reserved identifier and therefore not a valid path component
350    pub fn prepend<S>(&self, component: S) -> Result<Self, PathError>
351    where
352        S: AsRef<str>,
353    {
354        let ns = component
355            .as_ref()
356            .parse::<LibraryNamespace>()
357            .map_err(PathError::InvalidNamespace)?;
358        let component = self.inner.ns.to_ident();
359        let mut components = smallvec![component];
360        components.extend(self.inner.components.iter().cloned());
361        Ok(Self::make(ns, components))
362    }
363
364    /// Pops the last non-namespace component in this path
365    pub fn pop(&mut self) -> Option<Ident> {
366        let inner = Arc::make_mut(&mut self.inner);
367        inner.components.pop()
368    }
369
370    /// Returns a new path, representing the current one with the last non-namespace component
371    /// removed.
372    pub fn strip_last(&self) -> Option<Self> {
373        match self.inner.components.len() {
374            0 => None,
375            1 => Some(Self::make(self.inner.ns.clone(), smallvec![])),
376            _ => {
377                let ns = self.inner.ns.clone();
378                let mut components = self.inner.components.clone();
379                components.pop();
380                Some(Self::make(ns, components))
381            },
382        }
383    }
384
385    /// Checks if the given input string is a valid [LibraryPath], returning the number of
386    /// components in the path.
387    ///
388    /// See the documentation of [LibraryPath::new] for details on what constitutes a valid path.
389    pub fn validate<S>(source: S) -> Result<usize, PathError>
390    where
391        S: AsRef<str>,
392    {
393        let source = source.as_ref();
394
395        let mut count = 0;
396        let mut components = source.split("::");
397
398        let ns = components.next().ok_or(PathError::Empty)?;
399        LibraryNamespace::validate(ns).map_err(PathError::InvalidNamespace)?;
400        count += 1;
401
402        for component in components {
403            validate_component(component)?;
404            count += 1;
405        }
406
407        Ok(count)
408    }
409
410    /// Returns a new [LibraryPath] with the given component appended without any validation.
411    ///
412    /// The caller is expected to uphold the validity invariants of [LibraryPath].
413    pub fn append_unchecked<S>(&self, component: S) -> Self
414    where
415        S: AsRef<str>,
416    {
417        let component = component.as_ref().to_string().into_boxed_str();
418        let component = Ident::new_unchecked(Span::unknown(Arc::from(component)));
419        let mut path = self.clone();
420        path.push_ident(component);
421        path
422    }
423}
424
425impl<'a> TryFrom<Vec<LibraryPathComponent<'a>>> for LibraryPath {
426    type Error = PathError;
427    fn try_from(iter: Vec<LibraryPathComponent<'a>>) -> Result<Self, Self::Error> {
428        let mut iter = iter.into_iter();
429        let ns = match iter.next() {
430            None => return Err(PathError::Empty),
431            Some(LibraryPathComponent::Namespace(ns)) => ns.clone(),
432            Some(LibraryPathComponent::Normal(ident)) => {
433                LibraryNamespace::try_from(ident.clone()).map_err(PathError::InvalidNamespace)?
434            },
435        };
436        let mut components = Components::default();
437        for component in iter {
438            match component {
439                LibraryPathComponent::Normal(ident) => components.push(ident.clone()),
440                LibraryPathComponent::Namespace(LibraryNamespace::User(name)) => {
441                    components.push(Ident::new_unchecked(Span::unknown(name.clone())));
442                },
443                LibraryPathComponent::Namespace(_) => return Err(PathError::UnsupportedJoin),
444            }
445        }
446        Ok(Self::make(ns, components))
447    }
448}
449
450impl From<LibraryNamespace> for LibraryPath {
451    fn from(ns: LibraryNamespace) -> Self {
452        Self::make(ns, smallvec![])
453    }
454}
455
456impl From<LibraryPath> for String {
457    fn from(path: LibraryPath) -> Self {
458        path.to_string()
459    }
460}
461
462impl TryFrom<String> for LibraryPath {
463    type Error = PathError;
464
465    #[inline]
466    fn try_from(value: String) -> Result<Self, Self::Error> {
467        Self::new(value)
468    }
469}
470
471impl<'a> TryFrom<&'a str> for LibraryPath {
472    type Error = PathError;
473
474    #[inline]
475    fn try_from(value: &'a str) -> Result<Self, Self::Error> {
476        Self::new(value)
477    }
478}
479
480impl FromStr for LibraryPath {
481    type Err = PathError;
482
483    #[inline]
484    fn from_str(value: &str) -> Result<Self, Self::Err> {
485        Self::new(value)
486    }
487}
488
489impl Serializable for LibraryPath {
490    fn write_into<W: ByteWriter>(&self, target: &mut W) {
491        let len = self.byte_len();
492
493        target.write_u16(len as u16);
494        target.write_bytes(self.inner.ns.as_str().as_bytes());
495        for component in self.inner.components.iter() {
496            target.write_bytes(b"::");
497            target.write_bytes(component.as_str().as_bytes());
498        }
499    }
500}
501
502impl Deserializable for LibraryPath {
503    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
504        let len = source.read_u16()? as usize;
505        let path = source.read_slice(len)?;
506        let path =
507            str::from_utf8(path).map_err(|e| DeserializationError::InvalidValue(e.to_string()))?;
508        Self::new(path).map_err(|e| DeserializationError::InvalidValue(e.to_string()))
509    }
510}
511
512impl fmt::Display for LibraryPath {
513    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
514        write!(f, "{}", self.inner.ns)?;
515        for component in self.inner.components.iter() {
516            write!(f, "::{component}")?;
517        }
518        Ok(())
519    }
520}
521
522fn validate_component(component: &str) -> Result<(), PathError> {
523    if component.is_empty() {
524        Err(PathError::EmptyComponent)
525    } else if component.len() > LibraryNamespace::MAX_LENGTH {
526        Err(PathError::InvalidComponent(IdentError::InvalidLength {
527            max: LibraryNamespace::MAX_LENGTH,
528        }))
529    } else {
530        Ident::validate(component).map_err(PathError::InvalidComponent)
531    }
532}
533
534// TESTS
535// ================================================================================================
536
537/// Tests
538#[cfg(test)]
539mod tests {
540    use vm_core::assert_matches;
541
542    use super::{super::LibraryNamespaceError, IdentError, LibraryPath, PathError};
543
544    #[test]
545    fn new_path() {
546        let path = LibraryPath::new("foo").unwrap();
547        assert_eq!(path.num_components(), 1);
548
549        let path = LibraryPath::new("foo::bar").unwrap();
550        assert_eq!(path.num_components(), 2);
551
552        let path = LibraryPath::new("foo::bar::baz").unwrap();
553        assert_eq!(path.num_components(), 3);
554
555        let path = LibraryPath::new("#exec::bar::baz").unwrap();
556        assert_eq!(path.num_components(), 3);
557
558        let path = LibraryPath::new("#sys::bar::baz").unwrap();
559        assert_eq!(path.num_components(), 3);
560    }
561
562    #[test]
563    fn new_path_fail() {
564        let path = LibraryPath::new("");
565        assert_matches!(path, Err(PathError::Empty));
566
567        let path = LibraryPath::new("::");
568        assert_matches!(path, Err(PathError::InvalidNamespace(LibraryNamespaceError::Empty)));
569
570        let path = LibraryPath::new("foo::");
571        assert_matches!(path, Err(PathError::InvalidComponent(IdentError::Empty)));
572
573        let path = LibraryPath::new("::foo");
574        assert_matches!(path, Err(PathError::InvalidNamespace(LibraryNamespaceError::Empty)));
575
576        let path = LibraryPath::new("foo::1bar");
577        assert_matches!(path, Err(PathError::InvalidComponent(IdentError::InvalidStart)));
578
579        let path = LibraryPath::new("foo::b@r");
580        assert_matches!(
581            path,
582            Err(PathError::InvalidComponent(IdentError::InvalidChars { ident: _ }))
583        );
584
585        let path = LibraryPath::new("#foo::bar");
586        assert_matches!(
587            path,
588            Err(PathError::InvalidNamespace(LibraryNamespaceError::InvalidStart))
589        );
590    }
591}
miden_assembly/library/path.rs

miden_assembly/library/
path.rs
