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::parser::common::transform_span;
25use crate::parser::input::Input;
26use crate::parser::token::*;
27use crate::span::pretty_print_error;
28use crate::Range;
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
186pub fn display_parser_error(error: Error, source: &str) -> String {
187    let inner = &*error.backtrace.inner.borrow();
188    let inner = match inner {
189        Some(inner) => inner,
190        None => return String::new(),
191    };
192    let span_text = &source[std::ops::Range::from(inner.span)];
193
194    let mut labels = vec![];
195
196    // Plain text error has the highest priority. Only display it if exists.
197    for (span, kind) in error
198        .errors
199        .iter()
200        .map(|err| (error.span, err))
201        .chain(inner.errors.iter().map(|err| (inner.span, err)))
202    {
203        if let ErrorKind::Other(msg) = kind {
204            labels = vec![(span, msg.to_string())];
205            break;
206        }
207    }
208
209    // List all expected tokens in alternative branches.
210    if labels.is_empty() {
211        let mut expected_tokens = error
212            .errors
213            .iter()
214            .chain(&inner.errors)
215            .filter_map(|kind| match kind {
216                ErrorKind::ExpectToken(EOI) => None,
217                ErrorKind::ExpectToken(token) if token.is_keyword() => {
218                    Some(format!("`{:?}`", token))
219                }
220                ErrorKind::ExpectToken(token) => Some(format!("<{:?}>", token)),
221                ErrorKind::ExpectText(text) => Some(format!("`{}`", text)),
222                _ => None,
223            })
224            .unique()
225            .collect::<Vec<_>>();
226        expected_tokens.sort_by_cached_key(|token| {
227            OrderedFloat::from(-strsim::jaro_winkler(
228                &token.to_lowercase(),
229                &span_text.to_lowercase(),
230            ))
231        });
232
233        let mut msg = if span_text.is_empty() {
234            "unexpected end of input".to_string()
235        } else {
236            format!("unexpected `{span_text}`")
237        };
238        let mut iter = expected_tokens.iter().enumerate().peekable();
239        while let Some((i, error)) = iter.next() {
240            if i == MAX_DISPLAY_ERROR_COUNT {
241                let more = expected_tokens
242                    .len()
243                    .saturating_sub(MAX_DISPLAY_ERROR_COUNT);
244                write!(msg, ", or {} more ...", more).unwrap();
245                break;
246            } else if i == 0 {
247                msg += ", expecting ";
248            } else if iter.peek().is_none() && i == 1 {
249                msg += " or ";
250            } else if iter.peek().is_none() {
251                msg += ", or ";
252            } else {
253                msg += ", ";
254            }
255            msg += error;
256        }
257
258        labels = vec![(inner.span, msg)];
259    }
260
261    // Append contexts as secondary labels.
262    labels.extend(
263        error
264            .contexts
265            .iter()
266            .map(|(span, msg)| (*span, format!("while parsing {}", msg))),
267    );
268
269    pretty_print_error(source, labels)
270}
databend_common_ast/parser/error.rs

databend_common_ast/parser/
error.rs
