databend_common_ast/parser/
error.rs

1// Copyright 2021 Datafuse Labs
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::cell::RefCell;
16use std::cmp::Ordering;
17use std::fmt::Write;
18use std::num::IntErrorKind;
19use std::num::ParseIntError;
20
21use itertools::Itertools;
22use ordered_float::OrderedFloat;
23
24use crate::Range;
25use crate::parser::common::transform_span;
26use crate::parser::input::Input;
27use crate::parser::token::*;
28use crate::span::pretty_print_error;
29
30const MAX_DISPLAY_ERROR_COUNT: usize = 60;
31
32/// This error type accumulates errors and their position when backtracking
33/// through a parse tree. This take a deepest error at `alt` combinator.
34#[derive(Clone, Debug)]
35pub struct Error<'a> {
36    /// The span of the next token of the last valid one when encountering an error.
37    pub span: Range,
38    /// List of errors tried in various branches that consumed
39    /// the same (farthest) length of input.
40    pub errors: Vec<ErrorKind>,
41    /// The backtrace stack of the error.
42    pub contexts: Vec<(Range, &'static str)>,
43    /// The extra backtrace of error in optional branches.
44    pub backtrace: &'a Backtrace,
45}
46
47/// ErrorKind is the error type returned from parser.
48#[derive(Clone, Copy, Debug, PartialEq, Eq)]
49pub enum ErrorKind {
50    /// Error generated by `match_token` function
51    ExpectToken(TokenKind),
52    /// Error generated by `match_text` function
53    ExpectText(&'static str),
54    /// Plain text description of an error
55    Other(&'static str),
56}
57
58/// Record the farthest position in the input before encountering an error.
59///
60/// This is similar to the `Error`, but the information will not get lost
61/// even the error is from a optional branch.
62#[derive(Debug, Clone, Default)]
63pub struct Backtrace {
64    inner: RefCell<Option<BacktraceInner>>,
65}
66
67impl Backtrace {
68    pub fn new() -> Self {
69        Self::default()
70    }
71
72    pub fn clear(&self) {
73        self.inner.replace(None);
74    }
75
76    /// Restore the backtrace to a previous state.
77    ///
78    /// This is useful when the furthest-reached error reporting strategy is undesirable,
79    /// particularly when the furthest path is reached but considered invalid.
80    pub fn restore(&self, other: Backtrace) {
81        *self.inner.borrow_mut() = other.inner.into_inner();
82    }
83}
84
85#[derive(Clone, Debug, PartialEq, Eq)]
86pub struct BacktraceInner {
87    /// The span of the next token of the last valid one when encountering an error.
88    span: Range,
89    /// List of errors tried in various branches that consumed
90    /// the same (farthest) length of input.
91    errors: Vec<ErrorKind>,
92}
93
94impl<'a> nom::error::ParseError<Input<'a>> for Error<'a> {
95    fn from_error_kind(i: Input<'a>, _: nom::error::ErrorKind) -> Self {
96        Error {
97            span: transform_span(&i[..1]).unwrap(),
98            errors: vec![],
99            contexts: vec![],
100            backtrace: i.backtrace,
101        }
102    }
103
104    fn append(_: Input<'a>, _: nom::error::ErrorKind, other: Self) -> Self {
105        other
106    }
107
108    fn from_char(_: Input<'a>, _: char) -> Self {
109        unreachable!()
110    }
111
112    fn or(mut self, mut other: Self) -> Self {
113        match self.span.start.cmp(&other.span.start) {
114            Ordering::Equal => {
115                self.errors.append(&mut other.errors);
116                self.contexts.clear();
117                self
118            }
119            Ordering::Less => other,
120            Ordering::Greater => self,
121        }
122    }
123}
124
125impl<'a> nom::error::ContextError<Input<'a>> for Error<'a> {
126    fn add_context(input: Input<'a>, ctx: &'static str, mut other: Self) -> Self {
127        other
128            .contexts
129            .push((transform_span(&input.tokens[..1]).unwrap(), ctx));
130        other
131    }
132}
133
134impl<'a> Error<'a> {
135    pub fn from_error_kind(input: Input<'a>, kind: ErrorKind) -> Self {
136        let mut inner = input.backtrace.inner.borrow_mut();
137        if let Some(ref mut inner) = *inner {
138            match input.tokens[0].span.start.cmp(&inner.span.start) {
139                Ordering::Equal => {
140                    inner.errors.push(kind);
141                }
142                Ordering::Less => (),
143                Ordering::Greater => {
144                    *inner = BacktraceInner {
145                        span: transform_span(&input.tokens[..1]).unwrap(),
146                        errors: vec![kind],
147                    };
148                }
149            }
150        } else {
151            *inner = Some(BacktraceInner {
152                span: transform_span(&input.tokens[..1]).unwrap(),
153                errors: vec![kind],
154            })
155        }
156
157        Error {
158            span: transform_span(&input.tokens[..1]).unwrap(),
159            errors: vec![kind],
160            contexts: vec![],
161            backtrace: input.backtrace,
162        }
163    }
164}
165
166impl From<fast_float2::Error> for ErrorKind {
167    fn from(_: fast_float2::Error) -> Self {
168        ErrorKind::Other("unable to parse float number")
169    }
170}
171
172impl From<ParseIntError> for ErrorKind {
173    fn from(err: ParseIntError) -> Self {
174        let msg = match err.kind() {
175            IntErrorKind::InvalidDigit => {
176                "unable to parse number because it contains invalid characters"
177            }
178            IntErrorKind::PosOverflow => "unable to parse number because it positively overflowed",
179            IntErrorKind::NegOverflow => "unable to parse number because it negatively overflowed",
180            _ => "unable to parse number",
181        };
182        ErrorKind::Other(msg)
183    }
184}
185
186/// Suggests corrections using intelligent syntax pattern matching
187fn suggest_keyword_correction(
188    _span_text: &str,
189    source: &str,
190    _expected_tokens: &[String],
191) -> Option<String> {
192    use crate::parser::error_suggestion::suggest_correction;
193
194    suggest_correction(source)
195}
196
197pub fn display_parser_error(error: Error, source: &str) -> String {
198    let inner = &*error.backtrace.inner.borrow();
199    let inner = match inner {
200        Some(inner) => inner,
201        None => return String::new(),
202    };
203    let span_text = &source[std::ops::Range::from(inner.span)];
204
205    let mut labels = vec![];
206
207    // Plain text error has the highest priority. Only display it if exists.
208    for (span, kind) in error
209        .errors
210        .iter()
211        .map(|err| (error.span, err))
212        .chain(inner.errors.iter().map(|err| (inner.span, err)))
213    {
214        if let ErrorKind::Other(msg) = kind {
215            labels = vec![(span, msg.to_string())];
216            break;
217        }
218    }
219
220    // List all expected tokens in alternative branches.
221    if labels.is_empty() {
222        let mut expected_tokens = error
223            .errors
224            .iter()
225            .chain(&inner.errors)
226            .filter_map(|kind| match kind {
227                ErrorKind::ExpectToken(EOI) => None,
228                ErrorKind::ExpectToken(token) if token.is_keyword() => {
229                    Some(format!("`{:?}`", token))
230                }
231                ErrorKind::ExpectToken(token) => Some(format!("<{:?}>", token)),
232                ErrorKind::ExpectText(text) => Some(format!("`{}`", text)),
233                _ => None,
234            })
235            .unique()
236            .collect::<Vec<_>>();
237        expected_tokens.sort_by_cached_key(|token| {
238            OrderedFloat::from(-strsim::jaro_winkler(
239                &token.to_lowercase(),
240                &span_text.to_lowercase(),
241            ))
242        });
243
244        // Check for intelligent keyword suggestions first
245        let has_suggestion = suggest_keyword_correction(span_text, source, &expected_tokens);
246        let mut msg = if span_text.is_empty() {
247            "unexpected end of input".to_string()
248        } else if all_reserved_keywords()
249            .iter()
250            .any(|keyword| keyword.to_lowercase() == span_text.to_lowercase())
251            && has_suggestion.is_none()
252        {
253            format!("unexpected `{span_text}`. it's reserved keyword, you may avoid using it")
254        } else {
255            format!("unexpected `{span_text}`")
256        };
257        if let Some(suggestion) = has_suggestion {
258            write!(msg, ". {}", suggestion).unwrap();
259            labels = vec![(inner.span, msg)];
260
261            // Return early to skip context labels when we have intelligent suggestions
262            return pretty_print_error(source, labels);
263        } else {
264            let mut iter = expected_tokens.iter().enumerate().peekable();
265            while let Some((i, error)) = iter.next() {
266                if i == MAX_DISPLAY_ERROR_COUNT {
267                    let more = expected_tokens
268                        .len()
269                        .saturating_sub(MAX_DISPLAY_ERROR_COUNT);
270                    write!(msg, ", or {} more ...", more).unwrap();
271                    break;
272                } else if i == 0 {
273                    msg += ", expecting ";
274                } else if iter.peek().is_none() && i == 1 {
275                    msg += " or ";
276                } else if iter.peek().is_none() {
277                    msg += ", or ";
278                } else {
279                    msg += ", ";
280                }
281                msg += error;
282            }
283
284            labels = vec![(inner.span, msg)];
285        }
286    }
287
288    // Append contexts as secondary labels.
289    labels.extend(
290        error
291            .contexts
292            .iter()
293            .map(|(span, msg)| (*span, format!("while parsing {}", msg))),
294    );
295
296    pretty_print_error(source, labels)
297}
databend_common_ast/parser/error.rs

databend_common_ast/parser/
error.rs
