prism_parser/core/
adaptive.rs

1use crate::core::cache::Allocs;
2use crate::core::pos::Pos;
3use crate::grammar::{AnnotatedRuleExpr, Block, GrammarFile, Rule};
4use crate::parser::var_map::{VarMap, VarMapValue};
5use serde::{Deserialize, Serialize};
6use std::fmt::{Display, Formatter};
7use std::iter;
8
9#[derive(Copy, Clone)]
10pub struct GrammarState<'arn, 'grm> {
11    rules: &'arn [&'arn RuleState<'arn, 'grm>],
12    last_mut_pos: Option<Pos>,
13}
14
15#[derive(Copy, Clone, Debug, Serialize, Deserialize, Eq, PartialEq, Hash)]
16pub struct RuleId(usize);
17
18impl Display for RuleId {
19    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
20        write!(f, "{}", self.0)
21    }
22}
23
24impl<'arn, 'grm> Default for GrammarState<'arn, 'grm> {
25    fn default() -> Self {
26        Self::new()
27    }
28}
29
30#[derive(Debug)]
31pub enum AdaptError<'grm> {
32    InvalidRuleMutation(&'grm str),
33    SamePos(Pos),
34}
35
36impl<'arn, 'grm: 'arn> GrammarState<'arn, 'grm> {
37    pub fn new() -> Self {
38        Self {
39            rules: &[],
40            last_mut_pos: None,
41        }
42    }
43
44    /// Adapt this grammar state with `grammar`.
45    /// To unify rules, use the names of the rules in `ctx`
46    pub fn adapt_with(
47        &self,
48        grammar: &'arn GrammarFile<'arn, 'grm>,
49        ctx: VarMap<'arn, 'grm>,
50        pos: Option<Pos>,
51        alloc: Allocs<'arn>,
52    ) -> Result<(Self, VarMap<'arn, 'grm>), AdaptError<'grm>> {
53        // If we already tried to adapt at this position before, crash to prevent infinite loop
54        if let Some(pos) = pos {
55            if let Some(last_mut_pos) = self.last_mut_pos {
56                if pos == last_mut_pos {
57                    return Err(AdaptError::SamePos(pos));
58                }
59            }
60        }
61
62        // Create a new ruleid or find an existing rule id for each rule that is adopted
63        let mut new_rules = self.rules.to_vec();
64        let mut new_ctx = ctx;
65        let tmp: Vec<_> = grammar
66            .rules
67            .iter()
68            .map(|new_rule| {
69                let rule = if new_rule.adapt {
70                    ctx.get(new_rule.name)
71                        .and_then(VarMapValue::as_rule_id)
72                        .expect("Name refers to a rule id")
73                } else {
74                    new_rules.push(alloc.alloc(RuleState::new_empty(new_rule.name, new_rule.args)));
75                    RuleId(new_rules.len() - 1)
76                };
77                new_ctx = new_ctx.extend(
78                    iter::once((new_rule.name, VarMapValue::new_rule(rule, alloc))),
79                    alloc,
80                );
81                (new_rule.name, rule)
82            })
83            .collect();
84
85        // Update each rule that is to be adopted, stored in `result`
86        for (&(_, id), rule) in tmp.iter().zip(grammar.rules.iter()) {
87            new_rules[id.0] = alloc.alloc(
88                new_rules[id.0]
89                    .update(rule, new_ctx, alloc)
90                    .map_err(|_| AdaptError::InvalidRuleMutation(rule.name))?,
91            );
92        }
93
94        Ok((
95            Self {
96                last_mut_pos: pos,
97                rules: alloc.alloc_extend(new_rules),
98            },
99            new_ctx,
100        ))
101    }
102
103    pub fn new_with(
104        grammar: &'arn GrammarFile<'arn, 'grm>,
105        alloc: Allocs<'arn>,
106    ) -> (Self, VarMap<'arn, 'grm>) {
107        // We create a new grammar by adapting an empty one
108        GrammarState::new()
109            .adapt_with(grammar, VarMap::default(), None, alloc)
110            .unwrap()
111    }
112
113    pub fn get(&self, rule: RuleId) -> Option<&RuleState<'arn, 'grm>> {
114        self.rules.get(rule.0).map(|v| &**v)
115    }
116
117    pub fn unique_id(&self) -> GrammarStateId {
118        GrammarStateId(self.rules.as_ptr() as usize)
119    }
120}
121
122// TODO instead of one global GrammarStateId, we can track this per rule. Create a graph of rule ids and update the id when one of its components changes
123#[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
124pub struct GrammarStateId(usize);
125
126#[derive(Copy, Clone)]
127pub struct RuleState<'arn, 'grm> {
128    pub name: &'grm str,
129    pub args: &'arn [&'grm str],
130    pub blocks: &'arn [BlockState<'arn, 'grm>],
131}
132
133pub enum UpdateError {
134    ToposortCycle,
135}
136
137impl<'arn, 'grm> RuleState<'arn, 'grm> {
138    pub fn new_empty(name: &'grm str, args: &'arn [&'grm str]) -> Self {
139        Self {
140            name,
141            blocks: &[],
142            args,
143        }
144    }
145
146    pub fn update(
147        &self,
148        r: &'arn Rule<'arn, 'grm>,
149        ctx: VarMap<'arn, 'grm>,
150        allocs: Allocs<'arn>,
151    ) -> Result<Self, UpdateError> {
152        assert_eq!(self.name, r.name);
153        assert_eq!(self.args, r.args);
154
155        //TODO remove this allocation?
156        let mut result = Vec::with_capacity(self.blocks.len() + r.blocks.len());
157        let mut old_iter = self.blocks.iter();
158
159        for new_block in r.blocks {
160            // If this new block should not match an old block, add it as a new block state
161            if !new_block.adapt {
162                result.push(BlockState::new(new_block, ctx, allocs));
163                continue;
164            }
165            // Find matching old block
166            loop {
167                // If the matching block can't be found, it must've already occurred, and therefore we have a cycle
168                let Some(old_block) = old_iter.next() else {
169                    return Err(UpdateError::ToposortCycle);
170                };
171                // If this is not the matching block, add it and continue searching
172                if old_block.name != new_block.name {
173                    result.push(*old_block);
174                    continue;
175                }
176                result.push(old_block.update(new_block, ctx, allocs));
177                break;
178            }
179        }
180        for old_block in old_iter {
181            result.push(*old_block);
182        }
183
184        Ok(Self {
185            name: self.name,
186            args: self.args,
187            blocks: allocs.alloc_extend(result),
188        })
189    }
190}
191
192#[derive(Copy, Clone)]
193pub struct BlockState<'arn, 'grm> {
194    pub name: &'grm str,
195    pub constructors: &'arn [Constructor<'arn, 'grm>],
196}
197
198pub type Constructor<'arn, 'grm> = (&'arn AnnotatedRuleExpr<'arn, 'grm>, VarMap<'arn, 'grm>);
199
200impl<'arn, 'grm> BlockState<'arn, 'grm> {
201    pub fn new(
202        block: &'arn Block<'arn, 'grm>,
203        ctx: VarMap<'arn, 'grm>,
204        allocs: Allocs<'arn>,
205    ) -> Self {
206        Self {
207            name: block.name,
208            constructors: allocs.alloc_extend(block.constructors.iter().map(|r| (r, ctx))),
209        }
210    }
211
212    #[must_use]
213    pub fn update(
214        &self,
215        b: &'arn Block<'arn, 'grm>,
216        ctx: VarMap<'arn, 'grm>,
217        allocs: Allocs<'arn>,
218    ) -> Self {
219        assert_eq!(self.name, b.name);
220        Self {
221            name: self.name,
222            constructors: allocs.alloc_extend_len(
223                self.constructors.len() + b.constructors.len(),
224                self.constructors
225                    .iter()
226                    .cloned()
227                    .chain(b.constructors.iter().map(|r| (r, ctx))),
228            ),
229        }
230    }
231}
prism_parser/core/adaptive.rs

prism_parser/core/
adaptive.rs
