ll_sparql_parser/parser/
mod.rs

1mod grammar;
2
3use std::{cell::Cell, ops::Range};
4
5use crate::SyntaxKind;
6use grammar::{parse_QueryUnit, parse_UpdateUnit};
7use logos::Logos;
8use rowan::{GreenNode, GreenNodeBuilder, TextRange, TextSize};
9
10pub struct Parser {
11    tokens: Vec<Token>,
12    pos: usize,
13    fuel: Cell<u32>,
14    events: Vec<Event>,
15}
16
17#[derive(Debug, Clone)]
18pub(super) struct Token {
19    kind: SyntaxKind,
20    text: std::string::String,
21}
22
23impl Token {
24    fn is_trivia(&self) -> bool {
25        matches!(self.kind, SyntaxKind::WHITESPACE | SyntaxKind::Comment)
26    }
27
28    pub(super) fn kind(&self) -> SyntaxKind {
29        self.kind
30    }
31}
32
33#[derive(Debug)]
34pub struct ParseError {
35    pub span: TextRange,
36    pub message: String,
37}
38
39pub fn parse_text(input: &str, entry: TopEntryPoint) -> (GreenNode, Vec<ParseError>) {
40    let tokens = lex(input);
41    let parse_input = tokens
42        .iter()
43        .filter_map(|(token, _span)| (!token.is_trivia()).then_some(token))
44        .cloned()
45        .collect();
46    let output = entry.parse(parse_input);
47    build_tree(tokens, remove_empty_nodes(output))
48}
49
50/// Removes `Open`/`Close` pairs that contain no `Advance` event.
51///
52/// NOTE: The parser opens nodes speculatively during error recovery, which can
53/// produce zero-width nodes. These break tree navigation (e.g. rowan's
54/// `prev_token` gives up when a sibling subtree contains no tokens), so they
55/// are dropped before the tree is built. The root node is always kept.
56fn remove_empty_nodes(events: Vec<Event>) -> Vec<Event> {
57    let mut remove = vec![false; events.len()];
58    // INFO: stack of (index of `Open` event, node contains an `Advance`)
59    let mut stack: Vec<(usize, bool)> = Vec::new();
60    for (index, event) in events.iter().enumerate() {
61        match event {
62            Event::Open { .. } => stack.push((index, false)),
63            Event::Advance => {
64                if let Some(top) = stack.last_mut() {
65                    top.1 = true;
66                }
67            }
68            Event::Close => {
69                let (open_index, has_tokens) = stack
70                    .pop()
71                    .expect("Every \"Close\" event should occur after a open event");
72                if !has_tokens && !stack.is_empty() {
73                    remove[open_index] = true;
74                    remove[index] = true;
75                } else if has_tokens {
76                    if let Some(parent) = stack.last_mut() {
77                        parent.1 = true;
78                    }
79                }
80            }
81            Event::Error { .. } => {}
82        }
83    }
84    events
85        .into_iter()
86        .zip(remove)
87        .filter_map(|(event, remove)| (!remove).then_some(event))
88        .collect()
89}
90
91fn build_tree(
92    tokens: Vec<(Token, Range<usize>)>,
93    events: Vec<Event>,
94) -> (GreenNode, Vec<ParseError>) {
95    let mut cursor = 0;
96    let mut builder = GreenNodeBuilder::new();
97    let mut erros: Vec<ParseError> = Vec::new();
98
99    // Special case: pop the last `Close` event to ensure
100    // that the stack is non-empty inside the loop.
101    // assert!(matches!(events.pop(), Some(Event::Close)));
102    for event in &events[..events.len() - 1] {
103        match event {
104            Event::Open { kind } => {
105                while !matches!(kind, SyntaxKind::QueryUnit | SyntaxKind::UpdateUnit)
106                    && tokens
107                        .get(cursor)
108                        .map_or(false, |(next, _)| next.is_trivia())
109                {
110                    let (token, _) = &tokens[cursor];
111                    builder.token(token.kind.into(), &token.text);
112                    cursor += 1;
113                }
114                builder.start_node((*kind).into());
115            }
116            Event::Error { expected } => {
117                // NOTE: the error is anchored to the next non-trivia token;
118                // if there is none, to the end of the last non-trivia token
119                let span = tokens[cursor..]
120                    .iter()
121                    .find(|(token, _)| !token.is_trivia())
122                    .map(|(_, span)| {
123                        TextRange::new(
124                            TextSize::new(span.start as u32),
125                            TextSize::new(span.end as u32),
126                        )
127                    })
128                    .unwrap_or_else(|| {
129                        let end = tokens[..cursor]
130                            .iter()
131                            .rev()
132                            .find(|(token, _)| !token.is_trivia())
133                            .map_or(0, |(_, span)| span.end as u32);
134                        TextRange::new(TextSize::new(end), TextSize::new(end))
135                    });
136                erros.push(ParseError {
137                    span,
138                    message: if expected.is_empty() {
139                        "Syntax Error: unexpected token".to_string()
140                    } else {
141                        format!(
142                            "Syntax Error: expected {}",
143                            expected
144                                .into_iter()
145                                .map(|kind| format!("{kind:?}"))
146                                .collect::<Vec<_>>()
147                                .join(" or ")
148                        )
149                    },
150                });
151            }
152            Event::Close => {
153                builder.finish_node();
154            }
155
156            Event::Advance => {
157                while tokens
158                    .get(cursor)
159                    .map_or(false, |(next, _)| next.is_trivia())
160                {
161                    let (token, _) = &tokens[cursor];
162                    builder.token(token.kind.into(), &token.text);
163                    cursor += 1;
164                }
165                let (token, _) = &tokens[cursor];
166                builder.token(token.kind.into(), &token.text);
167                cursor += 1;
168            }
169        }
170    }
171    // Eat trailing trivia tokens
172    assert!(matches!(events.last(), Some(Event::Close)));
173    while tokens
174        .get(cursor)
175        .map_or(false, |(next, _)| next.is_trivia())
176    {
177        let (token, _) = &tokens[cursor];
178        builder.token(token.kind.into(), &token.text);
179        cursor += 1;
180    }
181    builder.finish_node();
182    (builder.finish(), erros)
183}
184
185impl Parser {
186    fn new(input: Vec<Token>) -> Self {
187        Self {
188            tokens: input,
189            pos: 0,
190            fuel: 1024.into(),
191            events: Vec::new(),
192        }
193    }
194}
195
196#[derive(Debug)]
197enum Event {
198    Open { kind: SyntaxKind },
199    Error { expected: Vec<SyntaxKind> },
200    Close,
201    Advance,
202}
203
204// NOTE: Tokens that reliably mark the start or end of a major construct.
205// Used by `advance_with_error` to synchronize after a syntax error.
206const RECOVERY_TOKENS: &[SyntaxKind] = &[SyntaxKind::WHERE, SyntaxKind::LCurly, SyntaxKind::RCurly];
207
208struct MarkOpened {
209    index: usize,
210}
211
212impl Parser {
213    fn open(&mut self) -> MarkOpened {
214        let mark = MarkOpened {
215            index: self.events.len(),
216        };
217        self.events.push(Event::Open {
218            kind: SyntaxKind::Error,
219        });
220        mark
221    }
222
223    fn close(&mut self, m: MarkOpened, kind: SyntaxKind) {
224        self.events[m.index] = Event::Open { kind };
225        self.events.push(Event::Close);
226    }
227
228    fn advance(&mut self) {
229        assert!(!self.eof());
230        self.fuel.set(1024);
231        self.events.push(Event::Advance);
232        self.pos += 1;
233    }
234
235    fn eof(&self) -> bool {
236        self.pos == self.tokens.len()
237    }
238
239    fn nth(&self, lookahead: usize) -> SyntaxKind {
240        if self.fuel.get() == 0 {
241            panic!("parser is stuck")
242        }
243        self.fuel.set(self.fuel.get() - 1);
244        self.tokens
245            .get(self.pos + lookahead)
246            .map_or(SyntaxKind::Eof, |it| it.kind)
247    }
248
249    fn at(&self, kind: SyntaxKind) -> bool {
250        self.nth(0) == kind
251    }
252
253    fn at_any(&self, kinds: &[SyntaxKind]) -> bool {
254        let current = self.nth(0);
255        kinds.contains(&current)
256    }
257
258    fn eat(&mut self, kind: SyntaxKind) -> bool {
259        if self.at(kind) {
260            self.advance();
261            true
262        } else {
263            false
264        }
265    }
266
267    fn expect(&mut self, kind: SyntaxKind) {
268        if self.eat(kind) {
269            return;
270        }
271        self.events.push(Event::Error {
272            expected: vec![kind],
273        });
274    }
275
276    fn advance_with_error(&mut self, expected: Vec<SyntaxKind>) {
277        self.events.push(Event::Error { expected });
278        // NOTE: Recovery tokens are strong synchronization points. They are
279        // never consumed as part of an error; instead the error is reported
280        // and the token is left for an ancestor rule to consume.
281        if self.at_any(RECOVERY_TOKENS) {
282            return;
283        }
284        let m = self.open();
285        self.advance();
286        self.close(m, SyntaxKind::Error);
287    }
288
289    fn error_until(&mut self, expected: Vec<SyntaxKind>, recovery: &[SyntaxKind]) {
290        self.events.push(Event::Error { expected }); // ONE diagnostic
291        if self.at_any(recovery) || self.eof() {
292            return; // nothing to skip
293        }
294        let m = self.open();
295        while !self.at_any(recovery) && !self.eof() {
296            self.advance(); // swallow all junk
297        }
298        self.close(m, SyntaxKind::Error); // ONE error node
299    }
300
301    pub(super) fn pos(&self) -> usize {
302        self.pos
303    }
304}
305
306#[derive(Debug)]
307pub enum TopEntryPoint {
308    QueryUnit,
309    UpdateUnit,
310}
311
312impl TopEntryPoint {
313    fn parse(&self, input: Vec<Token>) -> Vec<Event> {
314        let mut parser = Parser::new(input);
315        match self {
316            TopEntryPoint::QueryUnit => parse_QueryUnit(&mut parser),
317            TopEntryPoint::UpdateUnit => parse_UpdateUnit(&mut parser),
318        }
319        parser.events
320    }
321}
322
323pub(super) fn lex(text: &str) -> Vec<(Token, Range<usize>)> {
324    let mut lexer = SyntaxKind::lexer(text);
325    let mut tokens = Vec::new();
326
327    while let Some(result) = lexer.next() {
328        tokens.push((
329            Token {
330                kind: result.unwrap_or(SyntaxKind::Error),
331                text: lexer.slice().to_string(),
332            },
333            lexer.span(),
334        ));
335    }
336    tokens
337}
338
339pub fn guess_operation_type(input: &str) -> Option<TopEntryPoint> {
340    let tokens = lex(input);
341    tokens.iter().find_map(|(token, _)| match token.kind {
342        SyntaxKind::SELECT | SyntaxKind::CONSTRUCT | SyntaxKind::ASK | SyntaxKind::DESCRIBE => {
343            Some(TopEntryPoint::QueryUnit)
344        }
345        SyntaxKind::LOAD
346        | SyntaxKind::CLEAR
347        | SyntaxKind::DROP
348        | SyntaxKind::CREATE
349        | SyntaxKind::ADD
350        | SyntaxKind::MOVE
351        | SyntaxKind::COPY
352        | SyntaxKind::INSERT
353        | SyntaxKind::INSERT_DATA
354        | SyntaxKind::DELETE
355        | SyntaxKind::DELETE_DATA
356        | SyntaxKind::DELETE_WHERE => Some(TopEntryPoint::UpdateUnit),
357        _ => None,
358    })
359}
360
361#[cfg(test)]
362mod tests;
ll_sparql_parser/parser/mod.rs

ll_sparql_parser/parser/
mod.rs
