gramma/string_matcher/
repeat.rs

1use core::{
2    fmt,
3    ops::{Bound, RangeBounds},
4};
5
6use crate::utils::default;
7
8use super::{
9    machine::{RepeatState, RepeatStyle, StackItem},
10    traits::IntoMatchString,
11    DebugPrecedence, Link, MatchString, Matcher, StringMatcherContext, StringPattern,
12};
13
14struct RepeatContinue {}
15
16pub struct Repeat<'m, M> {
17    min: u32,
18    max: u32,
19    style: RepeatStyle,
20    inner: M,
21    links: (Link<'m>, Link<'m>),
22}
23
24impl<'m, M: MatchString<'m>> Repeat<'m, M> {
25    fn get_repeat_parts(
26        &'m self,
27        cx: &mut StringMatcherContext<'m, '_>,
28    ) -> (StackItem<'m>, StackItem<'m>) {
29        let (inner, outer) = if cx.is_reversed() {
30            (self.inner.last(), self.backward_matcher())
31        } else {
32            (self.inner.first(), self.forward_matcher())
33        };
34
35        let outer = if let Some(outer) = outer {
36            StackItem::Matcher { matcher: outer }
37        } else {
38            StackItem::Accept
39        };
40
41        let inner = StackItem::Matcher { matcher: inner };
42
43        (outer, inner)
44    }
45}
46
47impl<M: IntoMatchString> IntoMatchString for Repeat<'_, M> {
48    type Matcher<'m> = Repeat<'m, M::Matcher<'m>>
49    where
50        Self: 'm;
51
52    fn into_match_string<'m>(self) -> Self::Matcher<'m>
53    where
54        Self: 'm,
55    {
56        let Self {
57            min,
58            max,
59            style,
60            inner,
61            ..
62        } = self;
63        Self::Matcher {
64            min,
65            max,
66            style,
67            inner: inner.into_match_string(),
68            links: default(),
69        }
70    }
71}
72
73impl<'m, M: MatchString<'m>> MatchString<'m> for Repeat<'m, M> {
74    fn match_string(&'m self, cx: &mut super::StringMatcherContext<'m, '_>) -> Option<bool> {
75        let (outer, inner) = self.get_repeat_parts(cx);
76        cx.stack.extend([outer, inner]);
77
78        match self.style {
79            RepeatStyle::Greedy | RepeatStyle::Lazy => {
80                let mut state = cx.state();
81                let RepeatState {
82                    repeat_index: last_repeat,
83                    depth: last_depth,
84                    ..
85                } = state.repeat;
86                let greedy = self.style == RepeatStyle::Greedy;
87                let repeat_index: u16 = cx
88                    .stack
89                    .len()
90                    .try_into()
91                    .expect("string matcher stack exceeded maximum size");
92                cx.stack.push(StackItem::Repeat {
93                    min: self.min,
94                    max: self.max,
95                    greedy,
96                    last_repeat,
97                    last_depth,
98                });
99
100                state.repeat = RepeatState {
101                    repeat_index,
102                    depth: 0,
103                    greedy,
104                    min: self.min,
105                    max: self.max,
106                };
107                cx.set_state(state).continue_repeat()
108            }
109            RepeatStyle::Simple => cx.continue_repeat_simple(self.min, self.max, 0),
110        }
111    }
112
113    fn links(&'m self) -> Option<super::Links<'m>> {
114        Some((&self.links).into())
115    }
116
117    fn initialize(&'m self) {
118        if self.style != RepeatStyle::Simple {
119            let next_matcher = Matcher::from(&RepeatContinue {});
120            self.inner.set_backward(Some(next_matcher));
121            self.inner.set_forward(Some(next_matcher));
122        }
123        self.inner.initialize()
124    }
125
126    fn fmt_matcher(&self, f: &mut fmt::Formatter, prec: DebugPrecedence) -> fmt::Result {
127        prec.wrap_below(DebugPrecedence::Mul, f, |f| {
128            self.inner.fmt_matcher(f, DebugPrecedence::Mul)?;
129            f.write_str(" * ")?;
130            match (self.min, self.max) {
131                (min, max) if min == max => write!(f, "{min}")?,
132                (0, u32::MAX) => f.write_str("..")?,
133                (0, max) => write!(f, "..={max}")?,
134                (min, u32::MAX) => write!(f, "{min}..")?,
135                (min, max) => write!(f, "{min}..={max}")?,
136            }
137            Ok(())
138        })
139    }
140
141    fn quick_test(&'m self, cx: &mut super::StringMatcherContext<'m, '_>) -> Option<bool> {
142        let (outer, inner) = self.get_repeat_parts(cx);
143        let &Self { min, max, .. } = self;
144
145        let depth = if cx.is_reversed() { min } else { 0 };
146
147        cx.quick_test_repeat(outer, inner, depth, min, max, 1)
148    }
149}
150
151impl<'m> MatchString<'m> for RepeatContinue {
152    fn match_string(
153        &'m self,
154        cx: &mut super::machine::StringMatcherContext<'m, '_>,
155    ) -> Option<bool> {
156        cx.continue_repeat()
157    }
158
159    fn quick_test(&'m self, cx: &mut super::StringMatcherContext<'m, '_>) -> Option<bool> {
160        let RepeatState {
161            min,
162            max,
163            depth: mut repeat_depth,
164            ..
165        } = cx.state().repeat;
166        let (outer, inner) = cx.get_repeat_parts();
167
168        if cx.is_reversed() {
169            if repeat_depth == 0 {
170                return None;
171            }
172            repeat_depth -= 1;
173        } else {
174            repeat_depth = repeat_depth.saturating_add(1);
175        }
176
177        cx.quick_test_repeat(outer, inner, repeat_depth, min, max, 1)
178    }
179}
180
181pub trait RepeatCount {
182    fn bounds(&self) -> (Bound<&u32>, Bound<&u32>);
183}
184
185macro_rules! repeat_count_ranges {
186    ($($Name:ty),* $(,)?) => {
187        $(
188            impl RepeatCount for $Name {
189                fn bounds(&self) -> (Bound<&u32>, Bound<&u32>) {
190                    (self.start_bound(), self.end_bound())
191                }
192            }
193        )*
194        impl_mul!($($Name,)*);
195    };
196}
197
198macro_rules! impl_mul {
199    ($($Name:ty),* $(,)?) => { $(
200        impl<M> core::ops::Mul<$Name> for StringPattern<M> {
201            type Output = StringPattern<Repeat<'static, M>>;
202
203            fn mul(self, rhs: $Name) -> Self::Output {
204                self.repeat(rhs)
205            }
206        }
207        impl<M> core::ops::Mul<StringPattern<M>> for $Name {
208            type Output = StringPattern<Repeat<'static, M>>;
209
210            fn mul(self, rhs: StringPattern<M>) -> Self::Output {
211                rhs * self
212            }
213        }
214    )* };
215}
216
217repeat_count_ranges!(
218    core::ops::RangeInclusive<u32>,
219    core::ops::RangeToInclusive<u32>,
220    core::ops::RangeFrom<u32>,
221    core::ops::RangeFull,
222);
223
224impl_mul!(u32);
225
226impl RepeatCount for u32 {
227    fn bounds(&self) -> (Bound<&u32>, Bound<&u32>) {
228        (Bound::Included(self), Bound::Included(self))
229    }
230}
231
232/// Equivalent to [`inner.repeat(count)`](StringPattern::repeat).
233pub fn repeat<'m, M>(
234    count: impl RepeatCount,
235    inner: StringPattern<M>,
236) -> StringPattern<Repeat<'m, M>> {
237    inner.repeat(count)
238}
239
240/// Equivalent to [`inner.repeat(..=1)`](StringPattern::repeat).
241pub fn optional<'m, M>(inner: StringPattern<M>) -> StringPattern<Repeat<'m, M>> {
242    inner.optional()
243}
244
245impl<M> StringPattern<M> {
246    pub fn repeat<'m>(self, count: impl RepeatCount) -> StringPattern<Repeat<'m, M>> {
247        let (start, end) = count.bounds();
248        let min = match start {
249            Bound::Included(&x) => x,
250            Bound::Excluded(&x) => x.saturating_add(1),
251            Bound::Unbounded => 0,
252        };
253        let max = match end {
254            Bound::Included(&x) => x,
255            Bound::Excluded(&x) => x.saturating_sub(1),
256            Bound::Unbounded => u32::MAX,
257        };
258        StringPattern::new(Repeat {
259            min,
260            max,
261            style: default(),
262            inner: self.inner,
263            links: default(),
264        })
265    }
266
267    pub fn optional<'m>(self) -> StringPattern<Repeat<'m, M>> {
268        self.repeat(..=1)
269    }
270}
271
272impl<'m, M> StringPattern<Repeat<'m, M>> {
273    /// First attempts to match the most repetitions, then backtracks to fewer
274    /// if the rest of the pattern fails.
275    pub fn greedy(mut self) -> Self {
276        self.inner.style = RepeatStyle::Greedy;
277        self
278    }
279    /// First attempts to match the fewest repetitions, then backtracks to more
280    /// if the rest of the pattern fails.
281    pub fn lazy(mut self) -> Self {
282        self.inner.style = RepeatStyle::Lazy;
283        self
284    }
285    /// Repeats as many times as the repeated pattern matches and does not backtrack.
286    pub fn simple(mut self) -> Self {
287        self.inner.style = RepeatStyle::Simple;
288        self
289    }
290}
gramma/string_matcher/repeat.rs

gramma/string_matcher/
repeat.rs
