miden_assembly_syntax/ast/path/
components.rs

1use alloc::{string::ToString, sync::Arc};
2use core::{fmt, iter::FusedIterator};
3
4#[cfg(feature = "serde")]
5use serde::{Deserialize, Serialize};
6
7use super::{Path, PathError};
8use crate::{ast::Ident, debuginfo::Span};
9
10// PATH COMPONENT
11// ================================================================================================
12
13/// Represents a single component of a [Path]
14#[derive(Debug, Clone, Eq, PartialEq, PartialOrd, Ord, Hash)]
15#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
16pub enum PathComponent<'a> {
17    /// The root anchor, indicating that the path is absolute/fully qualified
18    Root,
19    /// A normal component of the path, i.e. an identifier
20    Normal(&'a str),
21}
22
23impl<'a> PathComponent<'a> {
24    /// Get this component as a [prim@str]
25    #[inline(always)]
26    pub fn as_str(&self) -> &'a str {
27        match self {
28            Self::Root => "::",
29            Self::Normal(id) => id,
30        }
31    }
32
33    /// Get this component as an [Ident], if it represents an identifier
34    #[inline]
35    pub fn to_ident(&self) -> Option<Ident> {
36        match self {
37            Self::Root => None,
38            Self::Normal(id) => Some(Ident::from_raw_parts(Span::unknown(Arc::from(
39                id.to_string().into_boxed_str(),
40            )))),
41        }
42    }
43
44    /// Get the size in [prim@char]s of this component when printed
45    pub fn char_len(&self) -> usize {
46        match self {
47            Self::Root => 2,
48            Self::Normal(id) => id.chars().count(),
49        }
50    }
51
52    /// Returns true if this path component is a quoted string
53    pub fn is_quoted(&self) -> bool {
54        matches!(self, Self::Normal(component) if component.starts_with('"') && component.ends_with('"'))
55    }
56
57    /// Returns true if this path component requires quoting when displayed/stored as a string
58    pub fn requires_quoting(&self) -> bool {
59        matches!(self, Self::Normal(component) if component.contains("::"))
60    }
61}
62
63impl PartialEq<str> for PathComponent<'_> {
64    fn eq(&self, other: &str) -> bool {
65        self.as_str().eq(other)
66    }
67}
68
69impl AsRef<str> for PathComponent<'_> {
70    #[inline(always)]
71    fn as_ref(&self) -> &str {
72        self.as_str()
73    }
74}
75
76impl fmt::Display for PathComponent<'_> {
77    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
78        f.write_str(self.as_str())
79    }
80}
81
82/// Returns an iterator over the path components represented in the provided source.
83///
84/// A path consists of at list of components separated by `::` delimiter. A path must contain
85/// at least one component. Path components may be quoted, in which `::` delimiters are ignored.
86/// Quoted path components may also contain characters that are not otherwise valid identifiers in
87/// Miden Assembly.
88///
89/// Note that quoted components may not contain nested quotes - the appearance of a nested quote in
90/// a quoted component will be treated as a closing quote resulting in unexpected behavior or
91/// validation errors as a result.
92///
93/// # Errors
94///
95/// Returns an error if:
96///
97/// * The path is empty.
98/// * Any component of the path is empty.
99/// * Any quoted component is missing a closing/opening quote (depending on order of iteration)
100/// * Any unquoted component is not a valid identifier (quoted or unquoted) in Miden Assembly
101///   syntax, i.e. starts with an ASCII alphabetic character, contains only printable ASCII
102///   characters, except for `::`, which must only be used as a path separator.
103#[derive(Debug)]
104pub struct Iter<'a> {
105    components: Components<'a>,
106}
107
108impl<'a> Iter<'a> {
109    pub fn new(path: &'a str) -> Self {
110        Self {
111            components: Components {
112                path,
113                original: path,
114                front_pos: 0,
115                front: State::Start,
116                back_pos: path.len(),
117                back: State::Body,
118            },
119        }
120    }
121
122    #[inline]
123    pub fn as_path(&self) -> &'a Path {
124        Path::new(self.components.path)
125    }
126}
127
128impl FusedIterator for Iter<'_> {}
129
130impl<'a> Iterator for Iter<'a> {
131    type Item = Result<PathComponent<'a>, PathError>;
132
133    fn next(&mut self) -> Option<Self::Item> {
134        match self.components.next() {
135            Some(Ok(PathComponent::Normal(component)))
136                if component.len() > Path::MAX_COMPONENT_LENGTH =>
137            {
138                Some(Err(PathError::InvalidComponent(crate::ast::IdentError::InvalidLength {
139                    max: Path::MAX_COMPONENT_LENGTH,
140                })))
141            },
142            next => next,
143        }
144    }
145}
146
147impl<'a> DoubleEndedIterator for Iter<'a> {
148    fn next_back(&mut self) -> Option<Self::Item> {
149        match self.components.next_back() {
150            Some(Ok(PathComponent::Normal(component)))
151                if component.len() > Path::MAX_COMPONENT_LENGTH =>
152            {
153                Some(Err(PathError::InvalidComponent(crate::ast::IdentError::InvalidLength {
154                    max: Path::MAX_COMPONENT_LENGTH,
155                })))
156            },
157            next => next,
158        }
159    }
160}
161
162/// The underlying path component iterator used by [Iter]
163#[derive(Debug)]
164struct Components<'a> {
165    original: &'a str,
166    /// The path left to parse components from
167    path: &'a str,
168    // To support double-ended iteration, these states keep tack of what has been produced from
169    // each end
170    front_pos: usize,
171    front: State,
172    back_pos: usize,
173    back: State,
174}
175
176#[derive(Debug, Copy, Clone, PartialEq)]
177enum State {
178    // We're at the start of the path
179    Start,
180    // We're parsing components of the path
181    Body,
182    // We've started parsing a quoted component
183    QuoteOpened(usize),
184    // We've parsed a quoted component
185    QuoteClosed(usize),
186    // We're at the end of the path
187    Done,
188}
189
190impl<'a> Components<'a> {
191    fn finished(&self) -> bool {
192        match (self.front, self.back) {
193            (State::Done, _) => true,
194            (_, State::Done) => true,
195            (State::Body | State::QuoteOpened(_) | State::QuoteClosed(_), State::Start) => true,
196            (..) => false,
197        }
198    }
199}
200
201impl<'a> Iterator for Components<'a> {
202    type Item = Result<PathComponent<'a>, PathError>;
203
204    fn next(&mut self) -> Option<Self::Item> {
205        // This is used when consuming a quoted item, to hold the result of the QuoteOpened state
206        // until we've finished transitioning through the QuoteClosed state. It is never used
207        // otherwise.
208        let mut quote_opened = None;
209        while !self.finished() || quote_opened.is_some() {
210            match self.front {
211                State::Start => match self.path.strip_prefix("::") {
212                    Some(rest) => {
213                        self.path = rest;
214                        self.front = State::Body;
215                        self.front_pos += 2;
216                        return Some(Ok(PathComponent::Root));
217                    },
218                    None if self.path.starts_with(Path::KERNEL_PATH)
219                        || self.path.starts_with(Path::EXEC_PATH) =>
220                    {
221                        self.front = State::Body;
222                        return Some(Ok(PathComponent::Root));
223                    },
224                    None => {
225                        self.front = State::Body;
226                    },
227                },
228                State::Body => {
229                    if let Some(rest) = self.path.strip_prefix('"') {
230                        self.front = State::QuoteOpened(self.front_pos);
231                        self.front_pos += 1;
232                        self.path = rest;
233                        continue;
234                    }
235                    match self.path.split_once("::") {
236                        Some(("", rest)) => {
237                            self.path = rest;
238                            self.front_pos += 2;
239                            return Some(Err(PathError::InvalidComponent(
240                                crate::ast::IdentError::Empty,
241                            )));
242                        },
243                        Some((component, rest)) => {
244                            self.front_pos += component.len() + 2;
245                            if rest.is_empty() {
246                                self.path = "::";
247                            } else {
248                                self.path = rest;
249                            }
250                            if let Err(err) =
251                                Ident::validate(component).map_err(PathError::InvalidComponent)
252                            {
253                                return Some(Err(err));
254                            }
255                            return Some(Ok(PathComponent::Normal(component)));
256                        },
257                        None if self.path.is_empty() => {
258                            self.front = State::Done;
259                        },
260                        None => {
261                            self.front = State::Done;
262                            let component = self.path;
263                            self.path = "";
264                            if let Err(err) =
265                                Ident::validate(component).map_err(PathError::InvalidComponent)
266                            {
267                                return Some(Err(err));
268                            }
269                            self.front_pos += component.len();
270                            return Some(Ok(PathComponent::Normal(component)));
271                        },
272                    }
273                },
274                State::QuoteOpened(opened_at) => match self.path.split_once('"') {
275                    Some(("", rest)) => {
276                        self.path = rest;
277                        self.front = State::QuoteClosed(self.front_pos);
278                        self.front_pos += 1;
279                        quote_opened = Some(Err(PathError::EmptyComponent));
280                    },
281                    Some((quoted, rest)) => {
282                        self.path = rest;
283                        self.front_pos += quoted.len();
284                        self.front = State::QuoteClosed(self.front_pos);
285                        self.front_pos += 1;
286                        let quoted = &self.original[opened_at..self.front_pos];
287                        quote_opened = Some(Ok(PathComponent::Normal(quoted)));
288                    },
289                    None => {
290                        self.front = State::Done;
291                        self.front_pos += self.path.len();
292                        return Some(Err(PathError::UnclosedQuotedComponent));
293                    },
294                },
295                State::QuoteClosed(_) => {
296                    if self.path.is_empty() {
297                        self.front = State::Done;
298                    } else {
299                        match self.path.strip_prefix("::") {
300                            Some(rest) => {
301                                self.path = rest;
302                                self.front = State::Body;
303                                self.front_pos += 2;
304                            },
305                            // If we would raise an error, but we have a quoted component to return
306                            // first, leave the state untouched, return the quoted component, and we
307                            // will return here on the next call to `next_back`
308                            None if quote_opened.is_some() => (),
309                            None => {
310                                self.front = State::Done;
311                                return Some(Err(PathError::MissingPathSeparator));
312                            },
313                        }
314                    }
315
316                    if quote_opened.is_some() {
317                        return quote_opened;
318                    }
319                },
320                State::Done => break,
321            }
322        }
323
324        None
325    }
326}
327
328impl<'a> DoubleEndedIterator for Components<'a> {
329    fn next_back(&mut self) -> Option<Self::Item> {
330        // This is used when consuming a quoted item, to hold the result of the QuoteClosed state
331        // until we've finished transitioning through the QuoteOpened state. It is never used
332        // otherwise.
333        let mut quote_closed = None;
334        while !self.finished() || quote_closed.is_some() {
335            match self.back {
336                State::Start => {
337                    self.back = State::Done;
338                    match self.path {
339                        "" => break,
340                        "::" => {
341                            self.back_pos = 0;
342                            return Some(Ok(PathComponent::Root));
343                        },
344                        other => {
345                            assert!(
346                                other.starts_with(Path::KERNEL_PATH)
347                                    || other.starts_with(Path::EXEC_PATH),
348                                "expected path in start state to be a valid path prefix, got '{other}'"
349                            );
350                            return Some(Ok(PathComponent::Root));
351                        },
352                    }
353                },
354                State::Body => {
355                    if let Some(rest) = self.path.strip_suffix('"') {
356                        self.back = State::QuoteClosed(self.back_pos);
357                        self.back_pos -= 1;
358                        self.path = rest;
359                        continue;
360                    }
361                    match self.path.rsplit_once("::") {
362                        Some(("", "")) => {
363                            self.back = State::Start;
364                            self.back_pos -= 2;
365                            continue;
366                        },
367                        Some((prefix, component)) => {
368                            self.back_pos -= component.len() + 2;
369                            if prefix.is_empty() {
370                                self.path = "::";
371                                self.back = State::Start;
372                            } else {
373                                self.path = prefix;
374                            }
375                            if let Err(err) =
376                                Ident::validate(component).map_err(PathError::InvalidComponent)
377                            {
378                                return Some(Err(err));
379                            }
380                            return Some(Ok(PathComponent::Normal(component)));
381                        },
382                        None if self.path.is_empty() => {
383                            self.back = State::Start;
384                        },
385                        None => {
386                            self.back = State::Start;
387                            let component = self.path;
388                            if component.starts_with(Path::KERNEL_PATH)
389                                || component.starts_with(Path::EXEC_PATH)
390                            {
391                                self.path = "::";
392                            } else {
393                                self.path = "";
394                            }
395                            self.back_pos = 0;
396                            if let Err(err) =
397                                Ident::validate(component).map_err(PathError::InvalidComponent)
398                            {
399                                return Some(Err(err));
400                            }
401                            return Some(Ok(PathComponent::Normal(component)));
402                        },
403                    }
404                },
405                State::QuoteOpened(_) => {
406                    if self.path.is_empty() {
407                        self.back = State::Start;
408                    } else {
409                        match self.path.strip_suffix("::") {
410                            Some("") => {
411                                self.back = State::Start;
412                                self.back_pos -= 2;
413                            },
414                            Some(rest) => {
415                                self.back_pos -= 2;
416                                self.path = rest;
417                                self.back = State::Body;
418                            },
419                            // If we would raise an error, but we have a quoted component to return
420                            // first, leave the state untouched, return the quoted component, and we
421                            // will return here on the next call to `next_back`
422                            None if quote_closed.is_some() => (),
423                            None => {
424                                self.back = State::Done;
425                                return Some(Err(PathError::MissingPathSeparator));
426                            },
427                        }
428                    }
429
430                    if quote_closed.is_some() {
431                        return quote_closed;
432                    }
433                },
434                State::QuoteClosed(closed_at) => match self.path.rsplit_once('"') {
435                    Some((rest, "")) => {
436                        self.back_pos -= 1;
437                        self.path = rest;
438                        self.back = State::QuoteOpened(self.back_pos);
439                        quote_closed = Some(Err(PathError::EmptyComponent));
440                    },
441                    Some((rest, quoted)) => {
442                        self.back_pos -= quoted.len() + 1;
443                        let quoted = &self.original[self.back_pos..closed_at];
444                        self.path = rest;
445                        self.back = State::QuoteOpened(self.back_pos);
446                        quote_closed = Some(Ok(PathComponent::Normal(quoted)));
447                    },
448                    None => {
449                        self.back = State::Done;
450                        self.back_pos = 0;
451                        return Some(Err(PathError::UnclosedQuotedComponent));
452                    },
453                },
454                State::Done => break,
455            }
456        }
457        None
458    }
459}
460
461#[cfg(test)]
462mod tests {
463    use miden_core::assert_matches;
464
465    use super::*;
466
467    #[test]
468    fn empty_path() {
469        let mut components = Iter::new("");
470        assert_matches!(components.next(), None);
471    }
472
473    #[test]
474    fn empty_path_back() {
475        let mut components = Iter::new("");
476        assert_matches!(components.next_back(), None);
477    }
478
479    #[test]
480    fn root_prefix_path() {
481        let mut components = Iter::new("::");
482        assert_matches!(components.next(), Some(Ok(PathComponent::Root)));
483        assert_matches!(components.next(), None);
484    }
485
486    #[test]
487    fn root_prefix_path_back() {
488        let mut components = Iter::new("::");
489        assert_matches!(components.next_back(), Some(Ok(PathComponent::Root)));
490        assert_matches!(components.next_back(), None);
491    }
492
493    #[test]
494    fn absolute_path() {
495        let mut components = Iter::new("::foo");
496        assert_matches!(components.next(), Some(Ok(PathComponent::Root)));
497        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("foo"))));
498        assert_matches!(components.next(), None);
499    }
500
501    #[test]
502    fn absolute_path_back() {
503        let mut components = Iter::new("::foo");
504        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("foo"))));
505        assert_matches!(components.next_back(), Some(Ok(PathComponent::Root)));
506        assert_matches!(components.next_back(), None);
507    }
508
509    #[test]
510    fn absolute_nested_path() {
511        let mut components = Iter::new("::foo::bar");
512        assert_matches!(components.next(), Some(Ok(PathComponent::Root)));
513        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("foo"))));
514        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("bar"))));
515        assert_matches!(components.next(), None);
516    }
517
518    #[test]
519    fn absolute_nested_path_back() {
520        let mut components = Iter::new("::foo::bar");
521        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("bar"))));
522        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("foo"))));
523        assert_matches!(components.next_back(), Some(Ok(PathComponent::Root)));
524        assert_matches!(components.next_back(), None);
525    }
526
527    #[test]
528    fn relative_path() {
529        let mut components = Iter::new("foo");
530        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("foo"))));
531        assert_matches!(components.next(), None);
532    }
533
534    #[test]
535    fn relative_path_back() {
536        let mut components = Iter::new("foo");
537        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("foo"))));
538        assert_matches!(components.next_back(), None);
539    }
540
541    #[test]
542    fn relative_nested_path() {
543        let mut components = Iter::new("foo::bar");
544        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("foo"))));
545        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("bar"))));
546        assert_matches!(components.next(), None);
547    }
548
549    #[test]
550    fn relative_nested_path_back() {
551        let mut components = Iter::new("foo::bar");
552        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("bar"))));
553        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("foo"))));
554        assert_matches!(components.next_back(), None);
555    }
556
557    #[test]
558    fn special_path() {
559        let mut components = Iter::new("$kernel");
560        assert_matches!(components.next(), Some(Ok(PathComponent::Root)));
561        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("$kernel"))));
562        assert_matches!(components.next(), None);
563    }
564
565    #[test]
566    fn special_path_back() {
567        let mut components = Iter::new("$kernel");
568        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("$kernel"))));
569        assert_matches!(components.next_back(), Some(Ok(PathComponent::Root)));
570        assert_matches!(components.next_back(), None);
571    }
572
573    #[test]
574    fn special_nested_path() {
575        let mut components = Iter::new("$kernel::bar");
576        assert_matches!(components.next(), Some(Ok(PathComponent::Root)));
577        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("$kernel"))));
578        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("bar"))));
579        assert_matches!(components.next(), None);
580    }
581
582    #[test]
583    fn special_nested_path_back() {
584        let mut components = Iter::new("$kernel::bar");
585        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("bar"))));
586        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("$kernel"))));
587        assert_matches!(components.next_back(), Some(Ok(PathComponent::Root)));
588        assert_matches!(components.next_back(), None);
589    }
590
591    #[test]
592    fn path_with_quoted_component() {
593        let mut components = Iter::new("\"foo\"");
594        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("\"foo\""))));
595        assert_matches!(components.next(), None);
596    }
597
598    #[test]
599    fn path_with_quoted_component_back() {
600        let mut components = Iter::new("\"foo\"");
601        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("\"foo\""))));
602        assert_matches!(components.next_back(), None);
603    }
604
605    #[test]
606    fn nested_path_with_quoted_component() {
607        let mut components = Iter::new("foo::\"bar\"");
608        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("foo"))));
609        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("\"bar\""))));
610        assert_matches!(components.next(), None);
611    }
612
613    #[test]
614    fn nested_path_with_quoted_component_back() {
615        let mut components = Iter::new("foo::\"bar\"");
616        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("\"bar\""))));
617        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("foo"))));
618        assert_matches!(components.next_back(), None);
619    }
620
621    #[test]
622    fn nested_path_with_interspersed_quoted_component() {
623        let mut components = Iter::new("foo::\"bar\"::baz");
624        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("foo"))));
625        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("\"bar\""))));
626        assert_matches!(components.next(), Some(Ok(PathComponent::Normal("baz"))));
627        assert_matches!(components.next(), None);
628    }
629
630    #[test]
631    fn nested_path_with_interspersed_quoted_component_back() {
632        let mut components = Iter::new("foo::\"bar\"::baz");
633        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("baz"))));
634        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("\"bar\""))));
635        assert_matches!(components.next_back(), Some(Ok(PathComponent::Normal("foo"))));
636        assert_matches!(components.next_back(), None);
637    }
638}
miden_assembly_syntax/ast/path/components.rs

miden_assembly_syntax/ast/path/
components.rs
