prism_parser/core/
cache.rs

1use crate::core::adaptive::GrammarStateId;
2use crate::core::context::ParserContext;
3use crate::core::parser::Parser;
4use crate::core::pos::Pos;
5use crate::core::presult::PResult;
6use crate::core::presult::PResult::{PErr, POk};
7use crate::core::state::ParserState;
8use crate::error::error_printer::ErrorLabel;
9use crate::error::error_printer::ErrorLabel::Debug;
10use crate::error::{err_combine_opt, ParseError};
11use crate::grammar::action_result::ActionResult;
12use crate::parser::var_map::BlockCtx;
13use bumpalo::Bump;
14use bumpalo_try::BumpaloExtend;
15
16#[derive(Eq, PartialEq, Hash, Clone)]
17pub struct CacheKey {
18    pos: Pos,
19    block_state: BlockKey,
20    ctx: ParserContext,
21    state: GrammarStateId,
22}
23
24#[derive(Eq, PartialEq, Hash, Clone)]
25pub struct BlockKey(usize, usize);
26
27impl From<BlockCtx<'_, '_>> for BlockKey {
28    fn from(value: BlockCtx) -> Self {
29        BlockKey(value.0.as_ptr() as usize, value.1.as_ptr() as usize)
30    }
31}
32
33pub type CacheVal<'arn, 'grm, E> = PResult<&'arn ActionResult<'arn, 'grm>, E>;
34
35#[derive(Copy, Clone)]
36pub struct Allocs<'arn> {
37    bump: &'arn Bump,
38}
39
40impl<'arn> Allocs<'arn> {
41    pub fn new(bump: &'arn Bump) -> Self {
42        Self { bump }
43    }
44
45    pub fn new_leaking() -> Self {
46        Self {
47            bump: Box::leak(Box::new(Bump::new())),
48        }
49    }
50
51    pub fn alloc<T: Copy>(&self, t: T) -> &'arn mut T {
52        self.bump.alloc(t)
53    }
54
55    pub fn alloc_extend<T: Copy, I: IntoIterator<Item = T, IntoIter: ExactSizeIterator>>(
56        &self,
57        iter: I,
58    ) -> &'arn mut [T] {
59        self.bump.alloc_slice_fill_iter(iter)
60    }
61
62    pub fn alloc_extend_len<T: Copy, I: IntoIterator<Item = T>>(
63        &self,
64        len: usize,
65        iter: I,
66    ) -> &'arn mut [T] {
67        let mut iter = iter.into_iter();
68        let slice = self.bump.alloc_slice_fill_with(len, |_| {
69            iter.next().expect("Iterator supplied too few elements")
70        });
71        assert!(iter.next().is_none());
72        slice
73    }
74
75    pub fn try_alloc_extend<
76        T: Copy,
77        I: IntoIterator<Item = Option<T>, IntoIter: ExactSizeIterator>,
78    >(
79        &self,
80        iter: I,
81    ) -> Option<&'arn mut [T]> {
82        self.bump.alloc_slice_fill_iter_option(iter)
83    }
84}
85
86pub struct ParserCacheEntry<PR> {
87    pub read: bool,
88    pub value: PR,
89}
90
91pub fn parser_cache_recurse<'a, 'arn: 'a, 'grm: 'arn, E: ParseError<L = ErrorLabel<'grm>>>(
92    sub: &'a impl Parser<'arn, 'grm, &'arn ActionResult<'arn, 'grm>, E>,
93    block_state: BlockCtx<'arn, 'grm>,
94    grammar_state: GrammarStateId,
95) -> impl Parser<'arn, 'grm, &'arn ActionResult<'arn, 'grm>, E> + 'a {
96    move |pos_start: Pos, state: &mut ParserState<'arn, 'grm, E>, context: ParserContext| {
97        //Check if this result is cached
98        let key = CacheKey {
99            pos: pos_start,
100            block_state: block_state.into(),
101            ctx: context,
102            state: grammar_state,
103        };
104        if let Some(cached) = state.cache_get(&key) {
105            return cached.clone();
106        }
107
108        //Before executing, put a value for the current position in the cache.
109        //This value is used if the rule is left-recursive
110        let mut res_recursive = PResult::new_err(E::new(pos_start.span_to(pos_start)), pos_start);
111        res_recursive.add_label_explicit(Debug(pos_start.span_to(pos_start), "LEFTREC"));
112
113        let cache_state = state.cache_state_get();
114        state.cache_insert(key.clone(), res_recursive);
115
116        //Now execute the grammar rule, taking into account left recursion
117        //The way this is done is heavily inspired by http://web.cs.ucla.edu/~todd/research/pepm08.pdf
118        //A quick summary
119        //- First put an error value for the current (rule, position) in the cache (already done)
120        //- Try to parse the current (rule, position). If this fails, there is definitely no left recursion. Otherwise, we now have a seed.
121        //- Put the new seed in the cache, and rerun on the current (rule, position). Make sure to revert the cache to the previous state.
122        //- At some point, the above will fail. Either because no new input is parsed, or because the entire parse now failed. At this point, we have reached the maximum size.
123        let res = sub.parse(pos_start, state, context);
124        match res {
125            POk(mut o, mut spos, mut epos, mut be) => {
126                //Did our rule left-recurse? (Safety: We just inserted it)
127                if !state.cache_is_read(key.clone()).unwrap() {
128                    //No leftrec, cache and return
129                    let res = POk(o, spos, epos, be);
130                    state.cache_insert(key, res.clone());
131                    res
132                } else {
133                    //There was leftrec, we need to grow the seed
134                    loop {
135                        //Insert the current seed into the cache
136                        state.cache_state_revert(cache_state);
137                        state.cache_insert(key.clone(), POk(o, spos, epos, be.clone()));
138
139                        //Grow the seed
140                        let new_res = sub.parse(pos_start, state, context);
141                        match new_res {
142                            POk(new_o, new_spos, new_epos, new_be)
143                                if new_epos.cmp(&epos).is_gt() =>
144                            {
145                                o = new_o;
146                                spos = new_spos;
147                                epos = new_epos;
148                                be = new_be;
149                            }
150                            POk(_, _, _, new_be) => {
151                                be = err_combine_opt(be, new_be);
152                                break;
153                            }
154                            PErr(new_e, new_s) => {
155                                be = err_combine_opt(be, Some((new_e, new_s)));
156                                break;
157                            }
158                        }
159                    }
160
161                    //The seed is at its maximum size
162                    //It should still be in the cache,
163                    POk(o, spos, epos, be)
164                }
165            }
166            res @ PErr(_, _) => {
167                state.cache_insert(key, res.clone());
168                res
169            }
170        }
171    }
172}
prism_parser/core/cache.rs

prism_parser/core/
cache.rs
