fexplib/
parser.rs

1use crate::token::{self, *};
2use crate::types::*;
3
4use bumpalo::collections::Vec;
5use bumpalo::Bump;
6use std::cell::Cell;
7use std::collections::HashMap;
8use tattle::{declare_error, Loc, Reporter};
9
10macro_rules! error {
11    ($p:expr, $m:expr, $msg:literal) => {{
12        $p.error($m, None, format!($msg))
13    }};
14    ($p:expr, $m:expr, $msg:literal, $($arg:expr),+) => {{
15        $p.error($m, None, format!($msg, $($arg),+))
16    }};
17}
18
19macro_rules! error_at {
20    ($p:expr, $m:expr, $l:expr, $msg:literal) => {{
21        $p.error($m, Some($l), format!($msg))
22    }};
23    ($p:expr, $m:expr, $l:expr, $msg:literal, $($arg:expr),+) => {{
24        $p.error($m, Some($l), format!($msg, $($arg),+))
25    }};
26}
27
28declare_error!(SYNTAX_ERROR, "syntax", "an error during the parsing phase");
29
30type Marker = usize;
31
32pub struct Parser<'a> {
33    src: &'a str,
34    reporter: Reporter,
35    tokens: &'a [Token],
36    arena: &'a Bump,
37    prectable: &'a HashMap<String, Prec>,
38    pos: Cell<usize>,
39    gas: Cell<usize>,
40}
41
42impl<'a> Parser<'a> {
43    pub fn new(
44        src: &'a str,
45        reporter: Reporter,
46        prectable: &'a HashMap<String, Prec>,
47        tokens: &'a [Token],
48        arena: &'a Bump,
49    ) -> Self {
50        Parser {
51            src,
52            reporter,
53            tokens,
54            arena,
55            prectable,
56            pos: Cell::new(0),
57            gas: Cell::new(256),
58        }
59    }
60
61    pub fn cur(&self) -> Kind {
62        if self.gas.get() == 0 {
63            panic!("probable infinite loop in grammar")
64        }
65
66        self.gas.set(self.gas.get() - 1);
67        if self.pos.get() >= self.tokens.len() {
68            token::EOF
69        } else {
70            self.tokens[self.pos.get()].kind
71        }
72    }
73
74    pub fn no_preceding_whitespace(&self) -> bool {
75        if self.pos.get() >= self.tokens.len() {
76            false
77        } else {
78            !self.tokens[self.pos.get()].preceding_whitespace
79        }
80    }
81
82    pub fn advance(&self) {
83        self.gas.set(256);
84        self.pos.set(self.pos.get() + 1);
85    }
86
87    pub fn open(&self) -> Marker {
88        self.tokens[self.pos.get().min(self.tokens.len() - 1)]
89            .loc
90            .start
91    }
92
93    fn closing_pos(&self) -> Marker {
94        let prev = self.pos.get().min(self.tokens.len()) - 1;
95        self.tokens[prev].loc.end
96    }
97
98    pub fn loc_from(&self, m: Marker) -> Loc {
99        let n = self.closing_pos();
100        Loc::new(n.min(m), n, None)
101    }
102
103    pub fn close(&self, m: Marker, node: FExp0<'a>) -> &'a FExp<'a> {
104        self.arena.alloc(FExp::L(self.loc_from(m), node))
105    }
106
107    pub fn new_vec<T>(&self) -> Vec<'a, T> {
108        Vec::new_in(self.arena)
109    }
110
111    pub fn slice(&self) -> &'a str {
112        if self.pos.get() >= self.tokens.len() {
113            ""
114        } else {
115            self.tokens[self.pos.get()].loc.slice(self.src)
116        }
117    }
118
119    pub fn error(&self, m: Marker, loc: Option<Loc>, message: String) -> &'a FExp<'a> {
120        let loc = loc.unwrap_or_else(|| self.loc_from(m));
121        self.reporter.error(loc, SYNTAX_ERROR, message);
122        self.close(m, Error)
123    }
124
125    pub fn prec(&self, op: &str) -> Option<Prec> {
126        self.prectable.get(op).copied()
127    }
128
129    pub fn at(&self, token: Kind) -> bool {
130        self.cur() == token
131    }
132
133    pub fn at_any(&self, tokens: &[Kind]) -> bool {
134        tokens.contains(&self.cur())
135    }
136
137    pub fn cur_loc(&self) -> Loc {
138        if self.pos.get() >= self.tokens.len() {
139            Loc::new(self.src.len(), self.src.len() + 1, None)
140        } else {
141            self.tokens[self.pos.get()].loc
142        }
143    }
144
145    pub fn eat(&self, m: Marker, kind: Kind) -> Result<(), &'a FExp<'a>> {
146        let cur = self.cur();
147        if cur == kind {
148            self.advance();
149            Ok(())
150        } else {
151            Err(error_at!(
152                self,
153                m,
154                self.cur_loc(),
155                "unexpected token {:?}, expected {:?}",
156                cur,
157                kind
158            ))
159        }
160    }
161
162    pub fn open_with(&self, kind: Kind) -> Marker {
163        assert!(self.at(kind));
164        let m = self.open();
165        self.advance();
166        m
167    }
168
169    pub fn advance_close(&self, m: Marker, node: FExp0<'a>) -> &'a FExp<'a> {
170        self.advance();
171        self.close(m, node)
172    }
173
174    pub fn slice_when(&self, m: Marker, kind: Kind) -> Result<&'a str, &'a FExp<'a>> {
175        let s = self.slice();
176        self.eat(m, kind).map(|_| s)
177    }
178}
179
180pub type PResult<'a> = Result<&'a FExp<'a>, &'a FExp<'a>>;
181
182pub fn get<'a>(r: PResult<'a>) -> &'a FExp<'a> {
183    r.unwrap_or_else(|s| s)
184}
185
186#[derive(Clone, Copy, Debug, PartialEq, Eq)]
187pub enum Assoc {
188    Left,
189    Right,
190    Non,
191}
192
193#[derive(Clone, Copy, Debug, PartialEq, Eq)]
194pub struct Prec {
195    tightness: usize,
196    assoc: Assoc,
197}
198
199impl Prec {
200    pub const fn lassoc(tightness: usize) -> Self {
201        Prec {
202            tightness,
203            assoc: Assoc::Left,
204        }
205    }
206
207    pub const fn rassoc(tightness: usize) -> Self {
208        Prec {
209            tightness,
210            assoc: Assoc::Right,
211        }
212    }
213
214    pub const fn nonassoc(tightness: usize) -> Self {
215        Prec {
216            tightness,
217            assoc: Assoc::Non,
218        }
219    }
220
221    fn loosest() -> Self {
222        Prec {
223            tightness: 0,
224            assoc: Assoc::Non,
225        }
226    }
227}
228
229impl PartialOrd for Prec {
230    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
231        use std::cmp::Ordering::*;
232        use Assoc::*;
233        match self.tightness.cmp(&other.tightness) {
234            Less => Some(Less),
235            Equal => match (self.assoc, other.assoc) {
236                (Left, Left) => Some(Greater),
237                (Right, Right) => Some(Less),
238                _ => None,
239            },
240            Greater => Some(Greater),
241        }
242    }
243}
244
245#[derive(Clone, Copy, PartialEq)]
246pub struct BinOp<'a> {
247    pub expr: &'a FExp<'a>,
248    pub prec: Prec,
249}
250
251impl<'a> BinOp<'a> {
252    fn start(&self) -> usize {
253        self.expr.loc().start
254    }
255
256    fn app(&self, x: &'a FExp<'a>, y: &'a FExp<'a>) -> FExp0<'a> {
257        App2(self.expr, x, y)
258    }
259}
260
261impl<'a> PartialOrd for BinOp<'a> {
262    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
263        self.prec.partial_cmp(&other.prec)
264    }
265}
266
267enum PrecState<'a> {
268    Complete(&'a FExp<'a>),
269    HalfApp(&'a FExp<'a>, BinOp<'a>),
270    Error(usize), // start position of the error
271}
272
273pub struct TermStack<'a> {
274    states: Vec<'a, PrecState<'a>>,
275    start: usize,
276}
277
278impl<'a> TermStack<'a> {
279    pub fn new(start: usize, p: &Parser<'a>) -> Self {
280        TermStack {
281            start,
282            states: p.new_vec(),
283        }
284    }
285
286    pub fn push_term(&mut self, p: &Parser<'a>, i: &'a FExp<'a>) {
287        use PrecState::*;
288        match self.states.pop() {
289            None => self.states.push(Complete(i)),
290            Some(x) => match x {
291                Complete(f) => self
292                    .states
293                    .push(Complete(p.close(f.loc().start, App1(f, i)))),
294                HalfApp(l, op) => {
295                    self.states.push(HalfApp(l, op));
296                    self.states.push(Complete(i));
297                }
298                Error(i) => self.states.push(Error(i)),
299            },
300        }
301    }
302
303    pub fn collect_for(&mut self, p: &Parser<'a>, prec: Prec, mut i: &'a FExp<'a>) -> &'a FExp<'a> {
304        use PrecState::*;
305        while let Some(x) = self.states.pop() {
306            match x {
307                Complete(_j) => {
308                    // this should never happen
309                    panic!()
310                }
311                HalfApp(l, op) => {
312                    if op.prec > prec {
313                        i = p.close(l.loc().start, op.app(l, i))
314                    } else {
315                        self.states.push(HalfApp(l, op));
316                        return i;
317                    }
318                }
319                Error(u) => {
320                    self.states.push(Error(u));
321                    return i;
322                }
323            }
324        }
325        i
326    }
327
328    pub fn push_binop(&mut self, p: &Parser<'a>, op: BinOp<'a>) -> Result<(), &'a FExp<'a>> {
329        use PrecState::*;
330        match self.states.pop() {
331            None => Err(error!(p, op.start(), "expected term before binary op"))?,
332            Some(x) => match x {
333                Complete(i) => {
334                    let i = self.collect_for(p, op.prec, i);
335                    self.states.push(HalfApp(i, op))
336                }
337                HalfApp(i, _prevop) => {
338                    error!(p, i.loc().start, "expected term after binary op");
339                    self.states.push(Error(i.loc().start))
340                }
341                Error(i) => self.states.push(Error(i)),
342            },
343        }
344        Ok(())
345    }
346
347    pub fn finish(mut self, p: &Parser<'a>) -> &'a FExp<'a> {
348        use PrecState::*;
349        if self.states.is_empty() {
350            return error!(p, self.start, "uncompleted term");
351        }
352        let i = match self.states.pop().unwrap() {
353            Complete(i) => self.collect_for(p, Prec::loosest(), i),
354            _ => {
355                return error!(p, self.start, "uncompleted term");
356            }
357        };
358        if !self.states.is_empty() {
359            return error!(p, self.start, "uncompleted term");
360        } else {
361            i
362        }
363    }
364}
fexplib/parser.rs

fexplib/
parser.rs
