oni_comb_parser/combinator/
recursive.rs

1use alloc::boxed::Box;
2use alloc::rc::Rc;
3use core::cell::UnsafeCell;
4
5use crate::fail::PResult;
6use crate::parser::Parser;
7use crate::str_input::StrInput;
8
9struct RecursiveInner<'a, O, E> {
10  inner: UnsafeCell<Option<Box<dyn Parser<StrInput<'a>, Output = O, Error = E> + 'a>>>,
11}
12
13/// 再帰パーサー。`recursive()` で構築する。
14///
15/// 再帰の結び目だけ `Box<dyn Parser>` + `Rc` で型消去し、
16/// 非再帰部分は具象型を維持する。
17pub struct Recursive<'a, O, E> {
18  shared: Rc<RecursiveInner<'a, O, E>>,
19}
20
21impl<'a, O, E> Clone for Recursive<'a, O, E> {
22  fn clone(&self) -> Self {
23    Recursive {
24      shared: Rc::clone(&self.shared),
25    }
26  }
27}
28
29impl<'a, O, E> Parser<StrInput<'a>> for Recursive<'a, O, E> {
30  type Error = E;
31  type Output = O;
32
33  #[inline]
34  fn parse_next(&mut self, input: &mut StrInput<'a>) -> PResult<O, E> {
35    // SAFETY: Recursive は Rc を使うため !Send + !Sync（単一スレッド）。
36    // 再帰呼び出しは同一コールスタック上で順次実行され、
37    // 外側の parse_next は内側の完了まで中断しているため、
38    // 内部パーサーの状態に対する並行アクセスは発生しない。
39    unsafe {
40      (*self.shared.inner.get())
41        .as_mut()
42        .expect("recursive parser not initialized")
43        .parse_next(input)
44    }
45  }
46}
47
48/// 再帰パーサーを構築する。
49///
50/// クロージャ `f` は再帰参照（`Recursive`）を受け取り、パーサーを組み立てて返す。
51/// 返されたパーサーは `Box<dyn Parser>` として内部に格納される。
52///
53/// ```ignore
54/// let expr = recursive(|expr| {
55///     let atom = integer().or(between(tag("("), expr, tag(")")));
56///     let term = atom.chainl1(mul_op());
57///     term.chainl1(add_op())
58/// });
59/// ```
60pub fn recursive<'a, O, E, F, P>(f: F) -> Recursive<'a, O, E>
61where
62  F: FnOnce(Recursive<'a, O, E>) -> P,
63  P: Parser<StrInput<'a>, Output = O, Error = E> + 'a, {
64  let rec = Recursive {
65    shared: Rc::new(RecursiveInner {
66      inner: UnsafeCell::new(None),
67    }),
68  };
69  let parser = f(rec.clone());
70  unsafe {
71    *rec.shared.inner.get() = Some(Box::new(parser));
72  }
73  rec
74}
oni_comb_parser/combinator/recursive.rs

oni_comb_parser/combinator/
recursive.rs
