rbe/
rbe.rs

1use crate::{deriv_error::DerivError, deriv_n, Bag, Cardinality, Max, Min};
2use core::hash::Hash;
3use serde::{Deserialize, Serialize};
4use std::collections::HashSet;
5use std::fmt;
6use std::fmt::{Debug, Display};
7//use log::debug;
8use itertools::cloned;
9
10#[derive(Clone, PartialEq, Eq, Serialize, Deserialize)]
11struct Pending<A> {
12    pending: A,
13}
14
15/// Implementation of Regular Bag Expressions
16#[derive(Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
17pub enum Rbe<A>
18where
19    A: Hash + Eq + Display,
20{
21    Fail {
22        error: DerivError<A>,
23    },
24    #[default]
25    Empty,
26    Symbol {
27        value: A,
28        card: Cardinality,
29    },
30    And {
31        values: Vec<Rbe<A>>,
32    },
33    Or {
34        values: Vec<Rbe<A>>,
35    },
36    Star {
37        value: Box<Rbe<A>>,
38    },
39    Plus {
40        value: Box<Rbe<A>>,
41    },
42    Repeat {
43        value: Box<Rbe<A>>,
44        card: Cardinality,
45    },
46}
47
48type NullableResult = bool;
49
50impl<A> Rbe<A>
51where
52    A: PartialEq + Eq + Hash + Clone + fmt::Debug + fmt::Display,
53{
54    pub fn match_bag(&self, bag: &Bag<A>, open: bool) -> Result<(), DerivError<A>> {
55        match &self.deriv_bag(bag, open, &self.symbols()) {
56            Rbe::Fail { error } => Err(error.clone()),
57            d => {
58                if d.nullable() {
59                    Ok(())
60                } else {
61                    Err(DerivError::NonNullable {
62                        non_nullable_rbe: Box::new(d.clone()),
63                        bag: (*bag).clone(),
64                        expr: Box::new((*self).clone()),
65                    })
66                }
67            }
68        }
69    }
70
71    pub fn empty() -> Rbe<A> {
72        Rbe::Empty
73    }
74
75    pub fn symbol(x: A, min: usize, max: Max) -> Rbe<A> {
76        Rbe::Symbol {
77            value: x,
78            card: Cardinality {
79                min: Min::from(min),
80                max,
81            },
82        }
83    }
84
85    pub fn or<I>(values: I) -> Rbe<A>
86    where
87        I: IntoIterator<Item = Rbe<A>>,
88    {
89        let rs: Vec<Rbe<A>> = values.into_iter().collect();
90        Rbe::Or { values: rs }
91    }
92
93    pub fn and<I>(values: I) -> Rbe<A>
94    where
95        I: IntoIterator<Item = Rbe<A>>,
96    {
97        let rs: Vec<Rbe<A>> = values.into_iter().collect();
98        Rbe::And { values: rs }
99    }
100
101    pub fn opt(v: Rbe<A>) -> Rbe<A> {
102        Rbe::Or {
103            values: vec![v, Rbe::Empty],
104        }
105    }
106
107    pub fn plus(v: Rbe<A>) -> Rbe<A> {
108        Rbe::Plus { value: Box::new(v) }
109    }
110
111    pub fn star(v: Rbe<A>) -> Rbe<A> {
112        Rbe::Star { value: Box::new(v) }
113    }
114
115    pub fn repeat(v: Rbe<A>, min: usize, max: Max) -> Rbe<A> {
116        Rbe::Repeat {
117            value: Box::new(v),
118            card: Cardinality::from(Min::from(min), max),
119        }
120    }
121
122    pub fn is_fail(&self) -> bool {
123        matches!(self, Rbe::Fail { .. })
124    }
125
126    pub fn symbols(&self) -> HashSet<A> {
127        let mut set = HashSet::new();
128        self.symbols_aux(&mut set);
129        set
130    }
131
132    fn symbols_aux(&self, set: &mut HashSet<A>) {
133        match &self {
134            Rbe::Fail { .. } => (),
135            Rbe::Empty => (),
136            Rbe::Symbol { value, card: _ } => {
137                set.insert(value.clone());
138            }
139            Rbe::And { values } => {
140                values.iter().for_each(|v| v.symbols_aux(set));
141            }
142            Rbe::Or { values } => {
143                values.iter().for_each(|v| v.symbols_aux(set));
144            }
145            Rbe::Plus { value } => {
146                value.symbols_aux(set);
147            }
148            Rbe::Star { value } => {
149                value.symbols_aux(set);
150            }
151            Rbe::Repeat { value, card: _ } => {
152                value.symbols_aux(set);
153            }
154        }
155    }
156
157    pub fn deriv_bag(&self, bag: &Bag<A>, open: bool, controlled: &HashSet<A>) -> Rbe<A> {
158        let mut current = (*self).clone();
159        let mut processed = Bag::new();
160        for (x, card) in bag.iter() {
161            let deriv = current.deriv(x, card, open, controlled);
162            match deriv {
163                Rbe::Fail { error } => {
164                    current = Rbe::Fail {
165                        error: DerivError::DerivBagError {
166                            error_msg: format!("{error}"),
167                            processed: Box::new(processed),
168                            bag: Box::new((*bag).clone()),
169                            expr: Box::new((*self).clone()),
170                            current: Box::new(current.clone()),
171                            value: (*x).clone(),
172                            open,
173                        },
174                    };
175                    break;
176                }
177                _ => {
178                    processed.insert((*x).clone());
179                    current = deriv;
180                }
181            }
182        }
183        current
184    }
185
186    fn nullable(&self) -> NullableResult {
187        match &self {
188            Rbe::Fail { .. } => false,
189            Rbe::Empty => true,
190            Rbe::Symbol { card, .. } if card.nullable() => true,
191            Rbe::Symbol { .. } => false,
192            Rbe::And { values } => values.iter().all(|v| v.nullable()),
193            Rbe::Or { values } => values.iter().any(|v| v.nullable()),
194            Rbe::Star { .. } => true,
195            Rbe::Plus { value } => value.nullable(),
196            Rbe::Repeat { value: _, card } if card.min.is_0() => true,
197            Rbe::Repeat { value, card: _ } => value.nullable(),
198        }
199    }
200
201    pub fn deriv(&self, x: &A, n: usize, open: bool, controlled: &HashSet<A>) -> Rbe<A>
202    where
203        A: Eq + Hash + Clone,
204    {
205        match *self {
206            ref fail @ Rbe::Fail { .. } => fail.clone(),
207            Rbe::Empty => {
208                if open && !(controlled.contains(x)) {
209                    Rbe::Empty
210                } else {
211                    Rbe::Fail {
212                        error: DerivError::UnexpectedEmpty {
213                            x: (*x).clone(),
214                            open,
215                        },
216                    }
217                }
218            }
219            Rbe::Symbol {
220                ref value,
221                ref card,
222            } => {
223                if *x == *value {
224                    if card.max == Max::IntMax(0) {
225                        Rbe::Fail {
226                            error: DerivError::MaxCardinalityZeroFoundValue { x: (*x).clone() },
227                        }
228                    } else if card.contains(n) {
229                        let card = card.minus(n);
230                        Self::mk_range_symbol(x, &card)
231                    } else {
232                        Rbe::Fail {
233                            error: DerivError::CardinalityFail {
234                                symbol: value.clone(),
235                                expected_cardinality: card.clone(),
236                                current_number: n,
237                            },
238                        }
239                    }
240                } else if open && !controlled.contains(x) {
241                    // Symbol is different from symbols defined in rbe if the rbe is open, we allow extra symbols
242                    self.clone()
243                } else {
244                    Rbe::Fail {
245                        error: DerivError::UnexpectedSymbol {
246                            x: (*x).clone(),
247                            expected: value.clone(),
248                            open,
249                        },
250                    }
251                }
252            }
253            Rbe::And { ref values } => Self::deriv_and(values, x, n, open, controlled),
254            Rbe::Or { ref values } => {
255                Self::mk_or_values(values.iter().map(|rbe| rbe.deriv(x, n, open, controlled)))
256            }
257            Rbe::Plus { ref value } => {
258                let d = value.deriv(x, n, open, controlled);
259                Self::mk_and(
260                    &d,
261                    &Rbe::Star {
262                        value: value.clone(),
263                    },
264                )
265            }
266            Rbe::Repeat {
267                ref value,
268                ref card,
269            } if card.is_0_0() => {
270                let d = value.deriv(x, n, open, controlled);
271                if d.nullable() {
272                    Rbe::Fail {
273                        error: DerivError::CardinalityZeroZeroDeriv { symbol: x.clone() },
274                    }
275                } else {
276                    Rbe::Empty
277                }
278            }
279            Rbe::Repeat {
280                ref value,
281                ref card,
282            } => {
283                let d = value.deriv(x, n, open, controlled);
284                let card = card.minus(n);
285                let rest = Self::mk_range(value, &card);
286                Self::mk_and(&d, &rest)
287            }
288            Rbe::Star { ref value } => {
289                let d = value.deriv(x, n, open, controlled);
290                Self::mk_and(&d, value)
291            }
292        }
293    }
294
295    fn deriv_and(
296        values: &Vec<Rbe<A>>,
297        x: &A,
298        n: usize,
299        open: bool,
300        controlled: &HashSet<A>,
301    ) -> Rbe<A> {
302        let mut or_values: Vec<Rbe<A>> = Vec::new();
303        let mut failures = crate::deriv_error::Failures::new();
304
305        for vs in deriv_n(cloned((*values).iter()).collect(), |value: &Rbe<A>| {
306            let d = value.deriv(x, n, open, controlled);
307            match d {
308                Rbe::Fail { error } => {
309                    failures.push(value.clone(), error);
310                    None
311                }
312                _ => Some(d),
313            }
314        }) {
315            or_values.push(Rbe::And { values: vs });
316        }
317        match or_values.len() {
318            0 => Rbe::Fail {
319                error: DerivError::OrValuesFail {
320                    e: Box::new(Rbe::And {
321                        values: cloned(values.iter()).collect(),
322                    }),
323                    failures,
324                },
325            },
326            1 => or_values[0].clone(),
327            _ => Rbe::Or { values: or_values },
328        }
329    }
330
331    fn mk_range(e: &Rbe<A>, card: &Cardinality) -> Rbe<A>
332    where
333        A: Clone,
334    {
335        if Self::bigger(card.min, &card.max) {
336            Rbe::Fail {
337                error: DerivError::RangeLowerBoundBiggerMaxExpr {
338                    expr: Box::new((*e).clone()),
339                    card: card.clone(),
340                },
341            }
342        } else {
343            match (e, card) {
344                (_, c) if c.is_0_0() => Rbe::Empty,
345                (e, c) if c.is_1_1() => e.clone(),
346                (fail @ Rbe::Fail { .. }, _) => fail.clone(),
347                (Rbe::Empty, _) => Rbe::Empty,
348                (e, c) => Rbe::Repeat {
349                    value: Box::new(e.clone()),
350                    card: c.clone(),
351                },
352            }
353        }
354    }
355
356    fn mk_range_symbol(x: &A, card: &Cardinality) -> Rbe<A>
357    where
358        A: Clone,
359    {
360        if Self::bigger(card.min, &card.max) {
361            Rbe::Fail {
362                error: DerivError::RangeLowerBoundBiggerMax {
363                    symbol: (*x).clone(),
364                    card: card.clone(),
365                },
366            }
367        } else {
368            Rbe::Symbol {
369                value: (*x).clone(),
370                card: card.clone(),
371            }
372        }
373    }
374
375    fn mk_and(v1: &Rbe<A>, v2: &Rbe<A>) -> Rbe<A>
376    where
377        A: Clone,
378    {
379        match (v1, v2) {
380            (Rbe::Empty, _) => (*v2).clone(),
381            (_, Rbe::Empty) => (*v1).clone(),
382            (f @ Rbe::Fail { .. }, _) => f.clone(),
383            (_, f @ Rbe::Fail { .. }) => f.clone(),
384            (_, _) => Rbe::And {
385                values: vec![(*v1).clone(), (*v2).clone()],
386            },
387        }
388    }
389
390    fn mk_or_values<I>(values: I) -> Rbe<A>
391    where
392        I: IntoIterator<Item = Rbe<A>>,
393    {
394        let init = Rbe::Fail {
395            error: DerivError::MkOrValuesFail,
396        };
397
398        values
399            .into_iter()
400            .fold(init, |result, value| Self::mk_or(&result, &value))
401    }
402
403    fn mk_or(v1: &Rbe<A>, v2: &Rbe<A>) -> Rbe<A> {
404        match (v1, v2) {
405            (Rbe::Fail { .. }, _) => (*v2).clone(),
406            (_, Rbe::Fail { .. }) => (*v1).clone(),
407            (e1, e2) => {
408                if e1 == e2 {
409                    (*v1).clone()
410                } else {
411                    Rbe::Or {
412                        values: vec![(*v1).clone(), (*v2).clone()],
413                    }
414                }
415            }
416        }
417    }
418
419    fn bigger(min: Min, max: &Max) -> bool {
420        match max {
421            Max::Unbounded => false,
422            Max::IntMax(max) => min.value > *max,
423        }
424    }
425}
426
427impl<A> Debug for Rbe<A>
428where
429    A: Debug + Hash + Eq + fmt::Display,
430{
431    fn fmt(&self, dest: &mut fmt::Formatter) -> fmt::Result {
432        match &self {
433            Rbe::Fail { error } => write!(dest, "Fail {{{error:?}}}"),
434            Rbe::Empty => write!(dest, "Empty"),
435            Rbe::Symbol { value, card } => write!(dest, "{value:?}{card:?}"),
436            Rbe::And { values } => values
437                .iter()
438                .try_for_each(|value| write!(dest, "{value:?};")),
439            Rbe::Or { values } => values
440                .iter()
441                .try_for_each(|value| write!(dest, "{value:?}|")),
442            Rbe::Star { value } => write!(dest, "{value:?}*"),
443            Rbe::Plus { value } => write!(dest, "{value:?}+"),
444            Rbe::Repeat { value, card } => write!(dest, "({value:?}){card:?}"),
445        }
446    }
447}
448
449impl<A> Display for Rbe<A>
450where
451    A: Display + Hash + Eq,
452{
453    fn fmt(&self, dest: &mut fmt::Formatter) -> fmt::Result {
454        match &self {
455            Rbe::Fail { error } => write!(dest, "Fail {{{error}}}"),
456            Rbe::Empty => write!(dest, "Empty"),
457            Rbe::Symbol { value, card } => write!(dest, "{value}{card}"),
458            Rbe::And { values } => values.iter().try_for_each(|value| write!(dest, "{value};")),
459            Rbe::Or { values } => values.iter().try_for_each(|value| write!(dest, "{value}|")),
460            Rbe::Star { value } => write!(dest, "{value}*"),
461            Rbe::Plus { value } => write!(dest, "{value}+"),
462            Rbe::Repeat { value, card } => write!(dest, "({value}){card}"),
463        }
464    }
465}
466
467#[cfg(test)]
468mod tests {
469    use super::*;
470    // use indoc::indoc;
471    // use test_log::test;
472
473    #[test]
474    fn deriv_a_1_1_and_b_opt_with_a() {
475        // a?|b? #= b/2
476        let rbe = Rbe::and(vec![
477            Rbe::symbol('a', 1, Max::IntMax(1)),
478            Rbe::symbol('b', 0, Max::IntMax(1)),
479        ]);
480        let expected = Rbe::and(vec![
481            Rbe::symbol('a', 0, Max::IntMax(0)),
482            Rbe::symbol('b', 0, Max::IntMax(1)),
483        ]);
484        assert_eq!(
485            rbe.deriv(&'a', 1, false, &HashSet::from(['a', 'b'])),
486            expected
487        );
488    }
489
490    #[test]
491    fn deriv_symbol() {
492        let rbe = Rbe::symbol('x', 1, Max::IntMax(1));
493        let d = rbe.deriv(&'x', 1, true, &HashSet::new());
494        assert_eq!(d, Rbe::symbol('x', 0, Max::IntMax(0)));
495    }
496
497    #[test]
498    fn symbols() {
499        let rbe = Rbe::and(vec![
500            Rbe::symbol('x', 1, Max::IntMax(1)),
501            Rbe::symbol('y', 1, Max::IntMax(1)),
502        ]);
503        let expected = HashSet::from(['x', 'y']);
504        assert_eq!(rbe.symbols(), expected);
505    }
506
507    #[test]
508    fn symbols2() {
509        let rbe = Rbe::and(vec![
510            Rbe::or(vec![
511                Rbe::symbol('x', 1, Max::IntMax(1)),
512                Rbe::symbol('y', 2, Max::Unbounded),
513            ]),
514            Rbe::symbol('y', 1, Max::IntMax(1)),
515        ]);
516        let expected = HashSet::from(['x', 'y']);
517        assert_eq!(rbe.symbols(), expected);
518    }
519
520    #[test]
521    fn match_bag_y1_4_y_2() {
522        // y{1,4} #= y/2
523        let rbe = Rbe::symbol('y', 1, Max::IntMax(4));
524        assert_eq!(rbe.match_bag(&Bag::from(['y', 'y']), false), Ok(()));
525    }
526
527    #[test]
528    fn match_bag_a_opt_or_b_opt_with_a() {
529        // a?|b? #= a
530        let rbe = Rbe::or(vec![
531            Rbe::symbol('a', 0, Max::IntMax(1)),
532            Rbe::symbol('b', 0, Max::IntMax(1)),
533        ]);
534        assert_eq!(rbe.match_bag(&Bag::from(['a']), false), Ok(()));
535    }
536
537    #[test]
538    fn match_bag_a_opt_or_b_opt_with_b() {
539        // a?|b? #= a
540        let rbe = Rbe::or(vec![
541            Rbe::symbol('a', 0, Max::IntMax(1)),
542            Rbe::symbol('b', 0, Max::IntMax(1)),
543        ]);
544        assert_eq!(rbe.match_bag(&Bag::from(['b']), false), Ok(()));
545    }
546
547    #[test]
548    fn match_bag_a_opt_and_b_opt_with_ba() {
549        // a?|b? #= a
550        let rbe = Rbe::and(vec![
551            Rbe::symbol('a', 0, Max::IntMax(1)),
552            Rbe::symbol('b', 0, Max::IntMax(1)),
553        ]);
554        assert_eq!(rbe.match_bag(&Bag::from(['b', 'a']), false), Ok(()));
555    }
556
557    #[test]
558    fn match_bag_a_and_b_opt_with_ab() {
559        // a?|b? #= b/2
560        let rbe = Rbe::and(vec![
561            Rbe::symbol('a', 1, Max::IntMax(1)),
562            Rbe::symbol('b', 0, Max::IntMax(1)),
563        ]);
564        assert_eq!(rbe.match_bag(&Bag::from(['a', 'b']), false), Ok(()));
565    }
566
567    #[test]
568    fn no_match_bag_a_and_b_opt_with_b_2() {
569        // a?|b? #= b/2
570        let rbe = Rbe::and(vec![
571            Rbe::symbol('a', 1, Max::IntMax(1)),
572            Rbe::symbol('b', 0, Max::IntMax(1)),
573        ]);
574        assert!(rbe.match_bag(&Bag::from(['b', 'b']), false).is_err());
575    }
576
577    #[test]
578    fn no_match_bag_a_and_b_opt_with_c() {
579        // a?|b? #= a
580        let rbe = Rbe::and(vec![
581            Rbe::symbol('a', 1, Max::IntMax(1)),
582            Rbe::symbol('b', 1, Max::IntMax(1)),
583        ]);
584        assert!(rbe.match_bag(&Bag::from(['c']), false).is_err());
585    }
586
587    /* I comment this test because it fails with
588       Result::unwrap()` on an `Err` value: Error { inner: UnsupportedType(Some("Rbe")) }
589    #[test]
590    fn test_serialize_rbe() {
591        let rbe = Rbe::symbol("foo".to_string(), 1, Max::IntMax(2));
592        let expected = indoc! {
593        r#"!Symbol
594                 value: foo
595                 card:
596                   min: 1
597                   max: 2
598              "# };
599        let rbe: String = toml::to_string(&rbe).unwrap();
600        assert_eq!(rbe, expected);
601    }*/
602
603    #[test]
604    fn test_deserialize_rbe() {
605        let str = r#"{
606            "Symbol": {
607                "value": "foo",
608                "card": {"min": 1, "max": 2 }
609            }
610        }"#;
611        let expected = Rbe::symbol("foo".to_string(), 1, Max::IntMax(2));
612        let rbe: Rbe<String> = serde_json::from_str(str).unwrap();
613        assert_eq!(rbe, expected);
614    }
615}
rbe/rbe.rs

rbe/
rbe.rs
