ucglib/parse/
precedence.rs

1// Copyright 2017 Jeremy Wall <jeremy@marzhillstudios.com>
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
15//! Bottom up parser for precedence parsing of expressions separated by binary
16//! operators.
17use abortable_parser::combinators::eoi;
18use abortable_parser::{Error, Peekable, Result, SliceIter};
19
20use super::{non_op_expression, ParseResult};
21use crate::ast::*;
22
23macro_rules! abort_on_end {
24    ($i:expr) => {{
25        if eoi($i.clone()).is_complete() {
26            return Result::Fail(Error::new(
27                format!("Expected Expression found End Of Input"),
28                Box::new($i.clone()),
29            ));
30        }
31    }};
32}
33
34/// Defines the intermediate stages of our bottom up parser for precedence parsing.
35#[derive(Debug, PartialEq, Clone)]
36pub enum Element {
37    Expr(Expression),
38    Op(BinaryExprType),
39}
40
41make_fn!(
42    dot_op_type<SliceIter<Token>, Element>,
43    do_each!(
44        _ => punct!("."),
45        (Element::Op(BinaryExprType::DOT)))
46);
47
48make_fn!(
49    math_op_type<SliceIter<Token>, Element>,
50    either!(
51        do_each!(
52            _ => punct!("+"),
53            (Element::Op(BinaryExprType::Add))),
54        do_each!(
55            _ => punct!("-"),
56            (Element::Op(BinaryExprType::Sub))),
57        do_each!(
58            _ => punct!("*"),
59            (Element::Op(BinaryExprType::Mul))),
60        do_each!(
61            _ => punct!("/"),
62            (Element::Op(BinaryExprType::Div))),
63        do_each!(
64            _ => punct!("%%"),
65            (Element::Op(BinaryExprType::Mod)))
66    )
67);
68
69make_fn!(
70    bool_op_type<SliceIter<Token>, Element>,
71    either!(
72        do_each!(
73            _ => punct!("&&"),
74            (Element::Op(BinaryExprType::AND))),
75        do_each!(
76            _ => punct!("||"),
77            (Element::Op(BinaryExprType::OR)))
78    )
79);
80
81fn parse_expression(i: SliceIter<Element>) -> Result<SliceIter<Element>, Expression> {
82    let mut i_ = i.clone();
83    abort_on_end!(i_);
84    let el = i_.next();
85    if let Some(&Element::Expr(ref expr)) = el {
86        return Result::Complete(i_, expr.clone());
87    }
88    return Result::Fail(Error::new(
89        format!(
90            "Error while parsing Binary Expression Expected Expression got {:?}",
91            el
92        ),
93        Box::new(i_),
94    ));
95}
96
97fn parse_bool_operator(i: SliceIter<Element>) -> Result<SliceIter<Element>, BinaryExprType> {
98    let mut i_ = i.clone();
99    abort_on_end!(i_);
100    let el = i_.next();
101    if let Some(&Element::Op(ref op)) = el {
102        match op {
103            BinaryExprType::AND | BinaryExprType::OR => {
104                return Result::Complete(i_, op.clone());
105            }
106            _other => {
107                // noop
108            }
109        };
110    }
111    return Result::Fail(Error::new(
112        format!(
113            "Error while parsing Binary Expression Unexpected Operator {:?}",
114            el
115        ),
116        Box::new(i_),
117    ));
118}
119
120fn parse_dot_operator(i: SliceIter<Element>) -> Result<SliceIter<Element>, BinaryExprType> {
121    let mut i_ = i.clone();
122    abort_on_end!(i_);
123    let el = i_.next();
124    if let Some(&Element::Op(ref op)) = el {
125        match op {
126            &BinaryExprType::DOT => {
127                return Result::Complete(i_, op.clone());
128            }
129            _other => {
130                // noop
131            }
132        };
133    }
134    return Result::Fail(Error::new(
135        format!(
136            "Error while parsing Binary Expression Unexpected Operator {:?}",
137            el
138        ),
139        Box::new(i_),
140    ));
141}
142
143fn parse_sum_operator(i: SliceIter<Element>) -> Result<SliceIter<Element>, BinaryExprType> {
144    let mut i_ = i.clone();
145    abort_on_end!(i_);
146    let el = i_.next();
147    if let Some(&Element::Op(ref op)) = el {
148        match op {
149            &BinaryExprType::Add => {
150                return Result::Complete(i_, op.clone());
151            }
152            &BinaryExprType::Sub => {
153                return Result::Complete(i_, op.clone());
154            }
155            _other => {
156                // noop
157            }
158        };
159    }
160    return Result::Fail(Error::new(
161        format!(
162            "Error while parsing Binary Expression Unexpected Operator {:?}",
163            el
164        ),
165        Box::new(i_),
166    ));
167}
168
169fn parse_product_operator(i: SliceIter<Element>) -> Result<SliceIter<Element>, BinaryExprType> {
170    let mut i_ = i.clone();
171    abort_on_end!(i_);
172    let el = i_.next();
173    if let Some(&Element::Op(ref op)) = el {
174        match op {
175            &BinaryExprType::Mul => {
176                return Result::Complete(i_, op.clone());
177            }
178            &BinaryExprType::Div => {
179                return Result::Complete(i_, op.clone());
180            }
181            &BinaryExprType::Mod => {
182                return Result::Complete(i_, op.clone());
183            }
184            _other => {
185                // noop
186            }
187        };
188    }
189    return Result::Fail(Error::new(
190        format!(
191            "Error while parsing Binary Expression Unexpected Operator {:?}",
192            el
193        ),
194        Box::new(i_),
195    ));
196}
197
198make_fn!(
199    compare_op_type<SliceIter<Token>, Element>,
200    either!(
201        do_each!(_ => punct!("=="), (Element::Op(BinaryExprType::Equal))),
202        do_each!(_ => punct!("!="), (Element::Op(BinaryExprType::NotEqual))),
203        do_each!(_ => punct!("~"), (Element::Op(BinaryExprType::REMatch))),
204        do_each!(_ => punct!("!~"), (Element::Op(BinaryExprType::NotREMatch))),
205        do_each!(_ => punct!("<="), (Element::Op(BinaryExprType::LTEqual))),
206        do_each!(_ => punct!(">="), (Element::Op(BinaryExprType::GTEqual))),
207        do_each!(_ => punct!("<"),  (Element::Op(BinaryExprType::LT))),
208        do_each!(_ => punct!(">"),  (Element::Op(BinaryExprType::GT))),
209        do_each!(_ => word!("in"),  (Element::Op(BinaryExprType::IN))),
210        do_each!(_ => word!("is"),  (Element::Op(BinaryExprType::IS)))
211    )
212);
213
214fn parse_compare_operator(i: SliceIter<Element>) -> Result<SliceIter<Element>, BinaryExprType> {
215    let mut i_ = i.clone();
216    abort_on_end!(i_);
217    let el = i_.next();
218    if let Some(&Element::Op(ref op)) = el {
219        match op {
220            &BinaryExprType::GT
221            | &BinaryExprType::GTEqual
222            | &BinaryExprType::LT
223            | &BinaryExprType::LTEqual
224            | &BinaryExprType::NotEqual
225            | &BinaryExprType::REMatch
226            | &BinaryExprType::NotREMatch
227            | &BinaryExprType::Equal
228            | &BinaryExprType::IS
229            | &BinaryExprType::IN => {
230                return Result::Complete(i_, op.clone());
231            }
232            _other => {
233                // noop
234            }
235        };
236    }
237    return Result::Fail(Error::new(
238        format!(
239            "Error while parsing Binary Expression Unexpected Operator {:?}",
240            el
241        ),
242        Box::new(i),
243    ));
244}
245
246/// Parse a list of expressions separated by operators into a Vec<Element>.
247fn parse_operand_list<'a>(i: SliceIter<'a, Token>) -> ParseResult<'a, Vec<Element>> {
248    // 1. First try to parse a non_op_expression,
249    let mut _i = i.clone();
250    let mut list = Vec::new();
251    // 1. loop
252    let mut firstrun = true;
253    loop {
254        // 2. Parse a non_op_expression.
255        match non_op_expression(_i.clone()) {
256            Result::Fail(e) => {
257                // A failure to parse an expression
258                // is always an error.
259                if !firstrun {
260                    // if we have successfully parsed an element and an operator then
261                    // failing to parse a second expression is an abort since we know
262                    // for sure now that the next expression is supposed to be there.
263                    let err = Error::new("Missing operand for binary expression", Box::new(_i));
264                    return Result::Abort(err);
265                }
266                return Result::Fail(e);
267            }
268            Result::Abort(e) => {
269                // A failure to parse an expression
270                // is always an error.
271                return Result::Abort(e);
272            }
273            Result::Incomplete(i) => {
274                return Result::Incomplete(i);
275            }
276            Result::Complete(rest, expr) => {
277                list.push(Element::Expr(expr));
278                _i = rest.clone();
279            }
280        }
281        // 3. Parse an operator.
282        match either!(
283            _i.clone(),
284            dot_op_type,
285            math_op_type,
286            compare_op_type,
287            bool_op_type
288        ) {
289            Result::Fail(e) => {
290                if firstrun {
291                    // If we don't find an operator in our first
292                    // run then this is not an operand list.
293                    return Result::Fail(e);
294                }
295                // if we don't find one on subsequent runs then
296                // that's the end of the operand list.
297                break;
298            }
299            Result::Abort(e) => {
300                // A failure to parse an operator
301                // is always an error.
302                return Result::Abort(e);
303            }
304            Result::Incomplete(i) => {
305                return Result::Incomplete(i);
306            }
307            Result::Complete(rest, el) => {
308                list.push(el);
309                _i = rest.clone();
310            }
311        }
312        firstrun = false;
313    }
314    return Result::Complete(_i, list);
315}
316
317make_fn!(
318    parse_operator_element<SliceIter<Element>, BinaryExprType>,
319    either!(
320        parse_dot_operator,
321        parse_sum_operator,
322        parse_product_operator,
323        parse_compare_operator,
324        parse_bool_operator
325    )
326);
327
328macro_rules! try_parse {
329    ($r:expr) => {
330        match $r {
331            Result::Abort(e) => return Result::Abort(e),
332            Result::Fail(e) => return Result::Fail(e),
333            Result::Incomplete(i) => return Result::Incomplete(i),
334            Result::Complete(rest, op_type) => (rest, op_type),
335        }
336    };
337}
338
339fn parse_op(
340    mut lhs: Expression,
341    mut i: SliceIter<Element>,
342    min_precedence: u32,
343) -> Result<SliceIter<Element>, Expression> {
344    // Termination condition
345    if eoi(i.clone()).is_complete() {
346        return Result::Complete(i, lhs);
347    }
348    let (_, mut lookahead_op) = try_parse!(parse_operator_element(i.clone()));
349    while !eoi(i.clone()).is_complete() && (lookahead_op.precedence_level() >= min_precedence) {
350        // Stash a copy of our lookahead operator for future use.
351        let op = lookahead_op.clone();
352        // Advance to next element.
353        i.next();
354        let (rest, mut rhs) = try_parse!(parse_expression(i.clone()));
355        i = rest;
356        if !eoi(i.clone()).is_complete() {
357            let (_, peek_op) = try_parse!(parse_operator_element(i.clone()));
358            lookahead_op = peek_op;
359        }
360        while !eoi(i.clone()).is_complete()
361            && (lookahead_op.precedence_level() > op.precedence_level())
362        {
363            let (rest, inner_rhs) =
364                try_parse!(parse_op(rhs, i.clone(), lookahead_op.precedence_level()));
365            i = rest;
366            rhs = inner_rhs;
367            // Before we check for another operator we should see
368            // if we are at the end of the input.
369            if eoi(i.clone()).is_complete() {
370                break;
371            }
372            let (_, peek_op) = try_parse!(parse_operator_element(i.clone()));
373            lookahead_op = peek_op;
374        }
375        let pos = lhs.pos().clone();
376        lhs = Expression::Binary(BinaryOpDef {
377            kind: op.clone(),
378            left: Box::new(lhs.clone()),
379            right: Box::new(rhs),
380            pos: pos,
381        });
382    }
383    return Result::Complete(i, lhs);
384}
385
386pub fn parse_precedence(i: SliceIter<Element>) -> Result<SliceIter<Element>, Expression> {
387    match parse_expression(i) {
388        Result::Abort(e) => Result::Abort(e),
389        Result::Fail(e) => Result::Fail(e),
390        Result::Incomplete(i) => Result::Incomplete(i),
391        Result::Complete(rest, expr) => parse_op(expr, rest, 0),
392    }
393}
394
395/// Parse a binary operator expression.
396pub fn op_expression<'a>(i: SliceIter<'a, Token>) -> Result<SliceIter<Token>, Expression> {
397    let preparse = parse_operand_list(i.clone());
398    match preparse {
399        Result::Fail(e) => Result::Fail(e),
400        Result::Abort(e) => Result::Abort(e),
401        Result::Incomplete(i) => Result::Incomplete(i),
402        Result::Complete(rest, oplist) => {
403            let i_ = SliceIter::new(&oplist);
404            let parse_result = parse_precedence(i_);
405            match parse_result {
406                Result::Fail(e) => {
407                    let err = Error::new(e.get_msg(), Box::new(rest.clone()));
408                    Result::Fail(err)
409                }
410                Result::Abort(e) => {
411                    let err = Error::new(e.get_msg(), Box::new(rest.clone()));
412                    Result::Abort(err)
413                }
414                Result::Incomplete(_) => Result::Incomplete(i.clone()),
415                Result::Complete(rest_ops, expr) => {
416                    if rest_ops.peek_next().is_some() {
417                        panic!("premature abort parsing Operator expression!");
418                    }
419                    Result::Complete(rest.clone(), expr)
420                }
421            }
422        }
423    }
424}
ucglib/parse/precedence.rs

ucglib/parse/
precedence.rs
