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

oni_comb_parser/combinator/
recursive.rs
