fasteval2/
parser.rs

1//! This module parses string expressions into an AST which can then be compiled or evaluated.
2//!
3//! # fasteval Algebra Grammar
4//! ```text
5//! Expression: Value (BinaryOp Value)*
6//!
7//! Value: Constant || UnaryOp || PrintFunc || StdFunc
8//!
9//! Constant: [+-]?[0-9]*(\.[0-9]+)?( ([eE][+-]?[0-9]+) || [pnuµmkKMGT] )?  || [+-]?(NaN || inf)
10//!
11//! UnaryOp: +Value || -Value || (Expression) || [Expression] || !Value
12//!
13//! BinaryOp: + || - || * || / || % || ^ || < || <= || == || != || >= || > || (or || '||') || (and || '&&')
14//!
15//! VarName: [a-zA-Z_][a-zA-Z_0-9]*
16//!
17//! StdFunc: VarName((Expression,)*)?  ||  VarName[(Expression,)*]?
18//!
19//! PrintFunc: print(ExpressionOrString,*)
20//!
21//! ExpressionOrString: Expression || String
22//!
23//! String: ".*"
24//! ```
25
26use crate::error::Error;
27use crate::slab::ParseSlab;
28
29use std::ptr;
30use std::str::{from_utf8, from_utf8_unchecked};
31
32/// An `ExpressionI` represents an index into `Slab.ps.exprs`.
33///
34/// It behaves much like a pointer or reference, but it is 'safe' (unlike a raw
35/// pointer) and is not managed by the Rust borrow checker (unlike a reference).
36#[derive(Debug, PartialEq, Copy, Clone)]
37pub struct ExpressionI(pub usize);
38
39/// A `ValueI` represents an index into `Slab.ps.vals`.
40///
41/// It behaves much like a pointer or reference, but it is 'safe' (unlike a raw
42/// pointer) and is not managed by the Rust borrow checker (unlike a reference).
43#[derive(Debug, PartialEq, Copy, Clone)]
44pub struct ValueI(pub usize);
45
46/// An `Expression` is the top node of a parsed AST.
47///
48/// It can be `compile()`d or `eval()`d.
49#[derive(Debug, PartialEq)]
50pub struct Expression {
51    pub(crate) first: Value,
52    pub(crate) pairs: Vec<ExprPair>, // cap=8
53}
54
55#[derive(Debug, PartialEq)]
56pub(crate) struct ExprPair(pub BinaryOp, pub Value);
57
58/// A `Value` can be a Constant, a UnaryOp, a StdFunc, or a PrintFunc.
59#[derive(Debug, PartialEq)]
60pub enum Value {
61    EConstant(f64),
62    EUnaryOp(UnaryOp),
63    EStdFunc(StdFunc),
64    EPrintFunc(PrintFunc),
65}
66use Value::{EConstant, EPrintFunc, EStdFunc, EUnaryOp};
67
68/// Unary Operators
69#[derive(Debug, PartialEq)]
70pub enum UnaryOp {
71    EPos(ValueI),
72    ENeg(ValueI),
73    ENot(ValueI),
74    EParentheses(ExpressionI),
75}
76use UnaryOp::{ENeg, ENot, EParentheses, EPos};
77
78/// Binary Operators
79#[derive(Debug, PartialEq, PartialOrd, Copy, Clone)]
80pub enum BinaryOp {
81    // Sorted in order of precedence (low-priority to high-priority):
82    // Keep this order in-sync with evaler.rs.  (Search for 'rtol' and 'ltor'.)
83    EOR = 1, // Lowest Priority
84    EAND = 2,
85    ENE = 3,
86    EEQ = 4,
87    EGTE = 5,
88    ELTE = 6,
89    EGT = 7,
90    ELT = 8,
91    EAdd = 9,
92    ESub = 10,
93    EMul = 11,
94    EDiv = 12,
95    EMod = 13,
96    EExp = 14, // Highest Priority
97}
98use BinaryOp::{EAdd, EDiv, EExp, EMod, EMul, ESub, EAND, EEQ, EGT, EGTE, ELT, ELTE, ENE, EOR};
99
100/// A Function Call with Standard Syntax.
101#[derive(Debug, PartialEq)]
102pub enum StdFunc {
103    EVar(String),
104    #[cfg(feature = "unsafe-vars")]
105    EUnsafeVar {
106        name: String,
107        ptr: *const f64,
108    },
109    EFunc {
110        name: String,
111        args: Vec<ExpressionI>,
112    }, // cap=4
113
114    EFuncInt(ExpressionI),
115    EFuncCeil(ExpressionI),
116    EFuncFloor(ExpressionI),
117    EFuncAbs(ExpressionI),
118    EFuncSign(ExpressionI),
119    EFuncLog {
120        base: Option<ExpressionI>,
121        expr: ExpressionI,
122    },
123    EFuncRound {
124        modulus: Option<ExpressionI>,
125        expr: ExpressionI,
126    },
127    EFuncMin {
128        first: ExpressionI,
129        rest: Vec<ExpressionI>,
130    }, // cap=4
131    EFuncMax {
132        first: ExpressionI,
133        rest: Vec<ExpressionI>,
134    }, // cap=4
135
136    EFuncE,
137    EFuncPi,
138
139    EFuncSin(ExpressionI),
140    EFuncCos(ExpressionI),
141    EFuncTan(ExpressionI),
142    EFuncASin(ExpressionI),
143    EFuncACos(ExpressionI),
144    EFuncATan(ExpressionI),
145    EFuncSinH(ExpressionI),
146    EFuncCosH(ExpressionI),
147    EFuncTanH(ExpressionI),
148    EFuncASinH(ExpressionI),
149    EFuncACosH(ExpressionI),
150    EFuncATanH(ExpressionI),
151}
152#[cfg(feature = "unsafe-vars")]
153unsafe impl Send for StdFunc {}
154
155#[cfg(feature = "unsafe-vars")]
156use StdFunc::EUnsafeVar;
157use StdFunc::{
158    EFunc, EFuncACos, EFuncACosH, EFuncASin, EFuncASinH, EFuncATan, EFuncATanH, EFuncAbs,
159    EFuncCeil, EFuncCos, EFuncCosH, EFuncE, EFuncFloor, EFuncInt, EFuncLog, EFuncMax, EFuncMin,
160    EFuncPi, EFuncRound, EFuncSign, EFuncSin, EFuncSinH, EFuncTan, EFuncTanH, EVar,
161};
162
163/// Represents a `print()` function call in the `fasteval` expression AST.
164#[derive(Debug, PartialEq)]
165pub struct PrintFunc(pub Vec<ExpressionOrString>); // cap=8
166
167/// Used by the `print()` function.  Can hold an `Expression` or a `String`.
168#[derive(Debug, PartialEq)]
169pub enum ExpressionOrString {
170    EExpr(ExpressionI),
171    EStr(String), // cap=64
172}
173use ExpressionOrString::{EExpr, EStr};
174
175impl Clone for PrintFunc {
176    fn clone(&self) -> Self {
177        let mut vec = Vec::<ExpressionOrString>::with_capacity(self.0.len());
178        for x_or_s in self.0.iter() {
179            vec.push(match x_or_s {
180                EExpr(i) => EExpr(*i),
181                EStr(s) => EStr(s.clone()),
182            });
183        }
184        PrintFunc(vec)
185    }
186}
187
188enum Token<T> {
189    Pass,
190    Bite(T),
191}
192use Token::{Bite, Pass};
193
194macro_rules! peek {
195    ($bs:ident) => {
196        $bs.first().copied()
197    };
198}
199macro_rules! peek_n {
200    ($bs:ident, $skip:literal) => {
201        $bs.get($skip).copied()
202    };
203    ($bs:ident, $skip:ident) => {
204        $bs.get($skip).copied()
205    };
206    ($bs:ident, $skip:expr) => {
207        $bs.get($skip).copied()
208    };
209}
210macro_rules! peek_is {
211    ($bs:ident, $skip:literal, $val:literal) => {
212        peek_n!($bs, $skip) == Some($val)
213    };
214    ($bs:ident, $skip:expr, $val:literal) => {
215        peek_n!($bs, $skip) == Some($val)
216    };
217}
218
219macro_rules! read {
220    ($bs:ident) => {
221        match $bs.first() {
222            Some(b) => {
223                *$bs = &$bs[1..];
224                Ok(*b)
225            }
226            None => Err(Error::EOF),
227        }
228    };
229    ($bs:ident, $parsing:literal) => {
230        match $bs.first() {
231            Some(b) => {
232                *$bs = &$bs[1..];
233                Ok(*b)
234            }
235            None => Err(Error::EofWhileParsing($parsing.to_string())),
236        }
237    };
238}
239
240macro_rules! skip {
241    ($bs:ident) => {
242        *$bs = &$bs[1..];
243    };
244}
245macro_rules! skip_n {
246    ($bs:ident, $n:literal) => {
247        *$bs = &$bs[$n..];
248    };
249    ($bs:ident, $n:ident) => {
250        *$bs = &$bs[$n..];
251    };
252}
253
254macro_rules! is_space {
255    ($b:ident) => {
256        if $b > b' ' {
257            false
258        } else {
259            $b == b' ' || $b == b'\n' || $b == b'\t' || $b == b'\r'
260        }
261    };
262}
263macro_rules! spaces {
264    ($bs:ident) => {
265        while let Some(b) = peek!($bs) {
266            if !is_space!(b) { break }
267            skip!($bs);  // We normally don't have long strings of whitespace, so it is more efficient to put this single-skip inside this loop rather than a skip_n afterwards.
268        }
269    };
270}
271
272pub const DEFAULT_EXPR_LEN_LIMIT: usize = 4096;
273pub const DEFAULT_EXPR_DEPTH_LIMIT: usize = 32;
274
275pub struct Parser {
276    pub expr_len_limit: usize,
277    pub expr_depth_limit: usize,
278}
279
280impl Parser {
281    #[inline]
282    pub const fn new() -> Self {
283        Self {
284            expr_len_limit: DEFAULT_EXPR_LEN_LIMIT,
285            expr_depth_limit: DEFAULT_EXPR_DEPTH_LIMIT,
286        }
287    }
288
289    fn is_varname_byte(b: u8, i: usize) -> bool {
290        (b'A' <= b && b <= b'Z')
291            || (b'a' <= b && b <= b'z')
292            || b == b'_'
293            || (i > 0 && (b'0' <= b && b <= b'9'))
294    }
295    fn is_varname_byte_opt(bo: Option<u8>, i: usize) -> bool {
296        match bo {
297            Some(b) => Self::is_varname_byte(b, i),
298            None => false,
299        }
300    }
301
302    /// Use this function to parse an expression String.  The `Slab` will be cleared first.
303    #[inline]
304    pub fn parse(&self, expr_str: &str, slab: &mut ParseSlab) -> Result<ExpressionI, Error> {
305        slab.clear();
306        self.parse_noclear(expr_str, slab)
307    }
308
309    /// This is exactly the same as `parse()` but the `Slab` will NOT be cleared.
310    /// This is useful in performance-critical sections, when you know that you
311    /// already have an empty `Slab`.
312    ///
313    /// This function cannot return Result<&Expression> because it would
314    /// prolong the mut ref.  / That's why we return an ExpressionI instead.
315    #[inline]
316    pub fn parse_noclear(
317        &self,
318        expr_str: &str,
319        slab: &mut ParseSlab,
320    ) -> Result<ExpressionI, Error> {
321        if expr_str.len() > self.expr_len_limit {
322            return Err(Error::TooLong);
323        } // Restrict length for safety
324        let mut bs = expr_str.as_bytes();
325        self.read_expression(slab, &mut bs, 0, true)
326    }
327
328    fn read_expression(
329        &self,
330        slab: &mut ParseSlab,
331        bs: &mut &[u8],
332        depth: usize,
333        expect_eof: bool,
334    ) -> Result<ExpressionI, Error> {
335        if depth > self.expr_depth_limit {
336            return Err(Error::TooDeep);
337        }
338
339        let first = self.read_value(slab, bs, depth)?;
340        let mut pairs = Vec::<ExprPair>::with_capacity(8);
341        loop {
342            match self.read_binaryop(bs)? {
343                Pass => break,
344                Bite(bop) => {
345                    let val = self.read_value(slab, bs, depth)?;
346                    pairs.push(ExprPair(bop, val));
347                }
348            }
349        }
350        spaces!(bs);
351        if expect_eof && !bs.is_empty() {
352            let bs_str = match from_utf8(bs) {
353                Ok(s) => s,
354                Err(..) => "Utf8Error while handling UnparsedTokensRemaining error",
355            };
356            return Err(Error::UnparsedTokensRemaining(bs_str.to_string()));
357        }
358        Ok(slab.push_expr(Expression { first, pairs })?)
359    }
360
361    fn read_value(
362        &self,
363        slab: &mut ParseSlab,
364        bs: &mut &[u8],
365        depth: usize,
366    ) -> Result<Value, Error> {
367        if depth > self.expr_depth_limit {
368            return Err(Error::TooDeep);
369        }
370
371        match Self::read_const(slab, bs)? {
372            Pass => {}
373            Bite(c) => return Ok(EConstant(c)),
374        }
375        match self.read_unaryop(slab, bs, depth)? {
376            Pass => {}
377            Bite(u) => return Ok(EUnaryOp(u)),
378        }
379        match self.read_callable(slab, bs, depth)? {
380            Pass => {}
381            Bite(c) => return Ok(c),
382        }
383
384        // Improve the precision of this error case:
385        if bs.is_empty() {
386            return Err(Error::EofWhileParsing("value".to_string()));
387        }
388
389        Err(Error::InvalidValue)
390    }
391
392    fn read_const(slab: &mut ParseSlab, bs: &mut &[u8]) -> Result<Token<f64>, Error> {
393        spaces!(bs);
394
395        let mut toklen = 0;
396        let mut sign_ok = true;
397        let mut specials_ok = true;
398        let mut suffix_ok = true;
399        let mut saw_val = false;
400        loop {
401            match peek_n!(bs, toklen) {
402                None => break,
403                Some(b) => {
404                    if b'0' <= b && b <= b'9' || b == b'.' {
405                        saw_val = true;
406                        sign_ok = false;
407                        specials_ok = false;
408                        toklen = toklen + 1;
409                    } else if sign_ok && (b == b'-' || b == b'+') {
410                        sign_ok = false;
411                        toklen = toklen + 1;
412                    } else if saw_val && (b == b'e' || b == b'E') {
413                        suffix_ok = false;
414                        sign_ok = true;
415                        toklen = toklen + 1;
416                    } else if specials_ok
417                        && (b == b'N'
418                            && peek_is!(bs, toklen + 1, b'a')
419                            && peek_is!(bs, toklen + 2, b'N')
420                            || b == b'i'
421                                && peek_is!(bs, toklen + 1, b'n')
422                                && peek_is!(bs, toklen + 2, b'f'))
423                    {
424                        #[cfg(feature = "alpha-keywords")]
425                        {
426                            saw_val = true;
427                            suffix_ok = false;
428                            toklen = toklen + 3;
429                        }
430                        break;
431                    } else {
432                        break;
433                    }
434                }
435            }
436        }
437
438        if !saw_val {
439            return Ok(Pass);
440        }
441
442        let mut tok = unsafe { from_utf8_unchecked(&bs[..toklen]) };
443        if suffix_ok {
444            match peek_n!(bs, toklen) {
445                None => (),
446                Some(b) => {
447                    let (exp, suffixlen) = match b {
448                        b'k' | b'K' => (3, 1),
449                        b'M' => (6, 1),
450                        b'G' => (9, 1),
451                        b'T' => (12, 1),
452                        b'm' => (-3, 1),
453                        b'u' | b'\xb5' => (-6, 1), // ASCII-encoded 'µ'
454                        b'\xc2' if peek_is!(bs, toklen + 1, b'\xb5') => (-6, 2), // UTF8-encoded 'µ'
455                        b'n' => (-9, 1),
456                        b'p' => (-12, 1),
457                        _ => (0, 0),
458                    };
459                    if exp != 0 {
460                        slab.char_buf.clear();
461                        slab.char_buf.push_str(tok);
462                        slab.char_buf.push('e');
463                        slab.char_buf.push_str(&exp.to_string());
464                        tok = &slab.char_buf;
465
466                        toklen = toklen + suffixlen;
467                    }
468                }
469            }
470        }
471
472        let val = tok
473            .parse::<f64>()
474            .map_err(|_| Error::ParseF64(tok.to_string()))?;
475        skip_n!(bs, toklen);
476
477        Ok(Bite(val))
478    }
479
480    // // This implementation is beautiful and correct, but it is slow due to the fact that I am first parsing everything,
481    // // and then I'm calling parse::<f64> which repeats the entire process.
482    // // I wish I could just call dec2flt::convert() ( https://doc.rust-lang.org/src/core/num/dec2flt/mod.rs.html#247 )
483    // // with all the pieces I already parsed, but, alas, that function is private.
484    // //
485    // // Also, I have decided that I really do need to support 'NaN' and 'inf'.  I could add them below, but instead,
486    // // I think I will just switch back to a drastically-simplified parser which isn't as "correct", but re-uses
487    // // more functionality from the stdlib.
488    // //
489    // // As a side-note, It's surprising how similar these algorithms are (which I created from scratch at 3am with no reference),
490    // // compared to the dec2flt::parse module.
491    // fn read_const(&mut self, bs:&mut &[u8]) -> Result<Token<f64>, KErr> {
492    //     spaces!(bs);
493    //
494    //     // Grammar: [+-]?[0-9]*(\.[0-9]+)?( ([eE][+-]?[0-9]+) || [pnuµmkKMGT] )?
495    //     fn peek_digits(bs:&[u8]) -> usize {
496    //         let mut i = 0;
497    //         while i<bs.len() && b'0'<=bs[i] && bs[i]<=b'9' { i+=1; }
498    //         i
499    //     }
500    //     fn peek_exp(bs:&[u8]) -> Result<usize, KErr> {
501    //         if bs.is_empty() { return Err(KErr::new("peek_exp empty")); }
502    //         let mut i = 0;
503    //         if bs[i]==b'-' || bs[i]==b'+' { i+=1; }
504    //         let digits = peek_digits(&bs[i..]);
505    //         if digits==0 { return Err(KErr::new("peek_exp no digits")); }
506    //         Ok(i+digits)
507    //     }
508    //     fn peek_tail(bs:&[u8]) -> Result<(/*read:*/usize, /*skip:*/usize, /*exp:*/i32), KErr> {
509    //         if bs.is_empty() { return Ok((0,0,0)); }
510    //         match bs[0] {
511    //             b'k' | b'K' => Ok((0,1,3)),
512    //             b'M' => Ok((0,1,6)),
513    //             b'G' => Ok((0,1,9)),
514    //             b'T' => Ok((0,1,12)),
515    //             b'm' => Ok((0,1,-3)),
516    //             b'u' | b'\xb5' => Ok((0,1,-6)),  // ASCII-encoded 'µ'
517    //             b'\xc2' if bs.len()>1 && bs[1]==b'\xb5' => Ok((0,2,-6)),  // UTF8-encoded 'µ'
518    //             b'n' => Ok((0,1,-9)),
519    //             b'p' => Ok((0,1,-12)),
520    //             b'e' | b'E' => peek_exp(&bs[1..]).map(|size| (1+size,0,0)),
521    //             _ => Ok((0,0,0)),
522    //         }
523    //     }
524    //
525    //     let mut toread=0;  let mut toskip=0;  let mut exp=0;
526    //
527    //     match peek(bs, 0) {
528    //         None => return Ok(Pass),
529    //         Some(b) => {
530    //             if b==b'-' || b==b'+' { toread+=1; }
531    //         }
532    //
533    //     }
534    //
535    //     let predec = peek_digits(&bs[toread..]);
536    //     toread+=predec;
537    //
538    //     match peek(bs, toread) {
539    //         None => {
540    //             if predec==0 { return Ok(Pass); }
541    //         }
542    //         Some(b) => {
543    //             if b==b'.' {
544    //                 toread+=1;
545    //                 let postdec = peek_digits(&bs[toread..]);
546    //                 if predec==0 && postdec==0 { return Err(KErr::new("decimal without pre- or post-digits")); }
547    //                 toread+=postdec;
548    //             } else {
549    //                 if predec==0 { return Ok(Pass); }
550    //             }
551    //             let (rd,sk,ex) = peek_tail(&bs[toread..])?;
552    //             toread+=rd;  toskip=sk;  exp=ex;
553    //         }
554    //     }
555    //
556    //     self.char_buf.clear();
557    //     for _ in 0..toread { self.char_buf.push(read(bs)? as char); }
558    //     for _ in 0..toskip { read(bs)?; }
559    //     if exp!=0 { self.char_buf.push('e'); self.char_buf.push_str(&exp.to_string()); }
560    //
561    //     let val = self.char_buf.parse::<f64>().map_err(|_| {
562    //         KErr::new("parse<f64> error").pre(&self.char_buf)
563    //     })?;
564    //     Ok(Bite(val))
565    // }
566
567    fn read_unaryop(
568        &self,
569        slab: &mut ParseSlab,
570        bs: &mut &[u8],
571        depth: usize,
572    ) -> Result<Token<UnaryOp>, Error> {
573        spaces!(bs);
574        match peek!(bs) {
575            None => Ok(Pass), // Err(KErr::new("EOF at UnaryOp position")), -- Instead of erroring, let the higher level decide what to do.
576            Some(b) => match b {
577                b'+' => {
578                    skip!(bs);
579                    let v = self.read_value(slab, bs, depth + 1)?;
580                    Ok(Bite(EPos(slab.push_val(v)?)))
581                }
582                b'-' => {
583                    skip!(bs);
584                    let v = self.read_value(slab, bs, depth + 1)?;
585                    Ok(Bite(ENeg(slab.push_val(v)?)))
586                }
587                b'(' => {
588                    skip!(bs);
589                    let xi = self.read_expression(slab, bs, depth + 1, false)?;
590                    spaces!(bs);
591                    if read!(bs, "parentheses")? != b')' {
592                        return Err(Error::Expected(")".to_string()));
593                    }
594                    Ok(Bite(EParentheses(xi)))
595                }
596                b'[' => {
597                    skip!(bs);
598                    let xi = self.read_expression(slab, bs, depth + 1, false)?;
599                    spaces!(bs);
600                    if read!(bs, "square brackets")? != b']' {
601                        return Err(Error::Expected("]".to_string()));
602                    }
603                    Ok(Bite(EParentheses(xi)))
604                }
605                b'!' => {
606                    skip!(bs);
607                    let v = self.read_value(slab, bs, depth + 1)?;
608                    Ok(Bite(ENot(slab.push_val(v)?)))
609                }
610                _ => Ok(Pass),
611            },
612        }
613    }
614
615    fn read_binaryop(&self, bs: &mut &[u8]) -> Result<Token<BinaryOp>, Error> {
616        spaces!(bs);
617        match peek!(bs) {
618            None => Ok(Pass), // Err(KErr::new("EOF")), -- EOF is usually OK in a BinaryOp position.
619            Some(b) => match b {
620                b'+' => {
621                    skip!(bs);
622                    Ok(Bite(EAdd))
623                }
624                b'-' => {
625                    skip!(bs);
626                    Ok(Bite(ESub))
627                }
628                b'*' => {
629                    skip!(bs);
630                    Ok(Bite(EMul))
631                }
632                b'/' => {
633                    skip!(bs);
634                    Ok(Bite(EDiv))
635                }
636                b'%' => {
637                    skip!(bs);
638                    Ok(Bite(EMod))
639                }
640                b'^' => {
641                    skip!(bs);
642                    Ok(Bite(EExp))
643                }
644                b'<' => {
645                    skip!(bs);
646                    if peek_is!(bs, 0, b'=') {
647                        skip!(bs);
648                        Ok(Bite(ELTE))
649                    } else {
650                        Ok(Bite(ELT))
651                    }
652                }
653                b'>' => {
654                    skip!(bs);
655                    if peek_is!(bs, 0, b'=') {
656                        skip!(bs);
657                        Ok(Bite(EGTE))
658                    } else {
659                        Ok(Bite(EGT))
660                    }
661                }
662                b'=' if peek_is!(bs, 1, b'=') => {
663                    skip_n!(bs, 2);
664                    Ok(Bite(EEQ))
665                }
666                b'!' if peek_is!(bs, 1, b'=') => {
667                    skip_n!(bs, 2);
668                    Ok(Bite(ENE))
669                }
670                #[cfg(feature = "alpha-keywords")]
671                b'o' if peek_is!(bs, 1, b'r') => {
672                    skip_n!(bs, 2);
673                    Ok(Bite(EOR))
674                }
675                b'|' if peek_is!(bs, 1, b'|') => {
676                    skip_n!(bs, 2);
677                    Ok(Bite(EOR))
678                }
679                #[cfg(feature = "alpha-keywords")]
680                b'a' if peek_is!(bs, 1, b'n') && peek_is!(bs, 2, b'd') => {
681                    skip_n!(bs, 3);
682                    Ok(Bite(EAND))
683                }
684                b'&' if peek_is!(bs, 1, b'&') => {
685                    skip_n!(bs, 2);
686                    Ok(Bite(EAND))
687                }
688                _ => Ok(Pass),
689            },
690        }
691    }
692
693    fn read_callable(
694        &self,
695        slab: &mut ParseSlab,
696        bs: &mut &[u8],
697        depth: usize,
698    ) -> Result<Token<Value>, Error> {
699        match Self::read_varname(bs)? {
700            Pass => Ok(Pass),
701            Bite(varname) => {
702                match Self::read_open_parenthesis(bs)? {
703                    Pass => {
704                        // VarNames without Parenthesis are always treated as custom 0-arg functions.
705
706                        #[cfg(feature = "unsafe-vars")]
707                        match slab.unsafe_vars.get(&varname) {
708                            None => Ok(Bite(EStdFunc(EVar(varname)))),
709                            Some(&ptr) => Ok(Bite(EStdFunc(EUnsafeVar { name: varname, ptr }))),
710                        }
711
712                        #[cfg(not(feature = "unsafe-vars"))]
713                        Ok(Bite(EStdFunc(EVar(varname))))
714                    }
715                    Bite(open_parenth) => {
716                        // VarNames with Parenthesis are first matched against builtins, then custom.
717                        match varname.as_ref() {
718                            "print" => Ok(Bite(EPrintFunc(self.read_printfunc(
719                                slab,
720                                bs,
721                                depth,
722                                open_parenth,
723                            )?))),
724                            _ => Ok(Bite(EStdFunc(self.read_func(
725                                varname,
726                                slab,
727                                bs,
728                                depth,
729                                open_parenth,
730                            )?))),
731                        }
732                    }
733                }
734            }
735        }
736    }
737
738    fn read_varname(bs: &mut &[u8]) -> Result<Token<String>, Error> {
739        spaces!(bs);
740
741        let mut toklen = 0;
742        while Self::is_varname_byte_opt(peek_n!(bs, toklen), toklen) {
743            toklen = toklen + 1;
744        }
745
746        if toklen == 0 {
747            return Ok(Pass);
748        }
749
750        let out = unsafe { from_utf8_unchecked(&bs[..toklen]) }.to_string();
751        skip_n!(bs, toklen);
752        Ok(Bite(out))
753    }
754
755    fn read_open_parenthesis(bs: &mut &[u8]) -> Result<Token<u8>, Error> {
756        spaces!(bs);
757
758        match peek!(bs) {
759            Some(b'(') | Some(b'[') => Ok(Bite(match read!(bs) {
760                Ok(b) => b,
761                Err(..) => return Err(Error::Unreachable),
762            })),
763            _ => Ok(Pass),
764        }
765    }
766
767    fn read_func(
768        &self,
769        fname: String,
770        slab: &mut ParseSlab,
771        bs: &mut &[u8],
772        depth: usize,
773        open_parenth: u8,
774    ) -> Result<StdFunc, Error> {
775        let close_parenth = match open_parenth {
776            b'(' => b')',
777            b'[' => b']',
778            _ => return Err(Error::Expected("'(' or '['".to_string())),
779        };
780        let mut args = Vec::<ExpressionI>::with_capacity(4);
781        loop {
782            spaces!(bs);
783            match peek!(bs) {
784                Some(b) => {
785                    if b == close_parenth {
786                        skip!(bs);
787                        break;
788                    }
789                }
790                None => return Err(Error::EofWhileParsing(fname)),
791            }
792            if !args.is_empty() {
793                match read!(bs) {
794                    // I accept ',' or ';' because the TV API disallows the ',' char in symbols... so I'm using ';' as a compromise.
795                    Ok(b',') | Ok(b';') => {}
796                    _ => return Err(Error::Expected("',' or ';'".to_string())),
797                }
798            }
799            args.push(self.read_expression(slab, bs, depth + 1, false)?);
800        }
801
802        let fname_str = fname.as_str();
803        match fname_str {
804            "int" => {
805                if args.len() == 1 {
806                    Ok(EFuncInt(match args.pop() {
807                        Some(xi) => xi,
808                        None => return Err(Error::Unreachable),
809                    }))
810                } else {
811                    Err(Error::WrongArgs("int: expected one arg".to_string()))
812                }
813            }
814            "ceil" => {
815                if args.len() == 1 {
816                    Ok(EFuncCeil(match args.pop() {
817                        Some(xi) => xi,
818                        None => return Err(Error::Unreachable),
819                    }))
820                } else {
821                    Err(Error::WrongArgs("ceil: expected one arg".to_string()))
822                }
823            }
824            "floor" => {
825                if args.len() == 1 {
826                    Ok(EFuncFloor(match args.pop() {
827                        Some(xi) => xi,
828                        None => return Err(Error::Unreachable),
829                    }))
830                } else {
831                    Err(Error::WrongArgs("floor: expected one arg".to_string()))
832                }
833            }
834            "abs" => {
835                if args.len() == 1 {
836                    Ok(EFuncAbs(match args.pop() {
837                        Some(xi) => xi,
838                        None => return Err(Error::Unreachable),
839                    }))
840                } else {
841                    Err(Error::WrongArgs("abs: expected one arg".to_string()))
842                }
843            }
844            "sign" => {
845                if args.len() == 1 {
846                    Ok(EFuncSign(match args.pop() {
847                        Some(xi) => xi,
848                        None => return Err(Error::Unreachable),
849                    }))
850                } else {
851                    Err(Error::WrongArgs("sign: expected one arg".to_string()))
852                }
853            }
854            "log" => {
855                if args.len() == 1 {
856                    Ok(EFuncLog {
857                        base: None,
858                        expr: match args.pop() {
859                            Some(xi) => xi,
860                            None => return Err(Error::Unreachable),
861                        },
862                    })
863                } else if args.len() == 2 {
864                    let expr = match args.pop() {
865                        Some(xi) => xi,
866                        None => return Err(Error::Unreachable),
867                    };
868                    Ok(EFuncLog {
869                        base: Some(match args.pop() {
870                            Some(xi) => xi,
871                            None => return Err(Error::Unreachable),
872                        }),
873                        expr,
874                    })
875                } else {
876                    Err(Error::WrongArgs(
877                        "expected log(x) or log(base,x)".to_string(),
878                    ))
879                }
880            }
881            "round" => {
882                if args.len() == 1 {
883                    Ok(EFuncRound {
884                        modulus: None,
885                        expr: match args.pop() {
886                            Some(xi) => xi,
887                            None => return Err(Error::Unreachable),
888                        },
889                    })
890                } else if args.len() == 2 {
891                    let expr = match args.pop() {
892                        Some(xi) => xi,
893                        None => return Err(Error::Unreachable),
894                    };
895                    Ok(EFuncRound {
896                        modulus: Some(match args.pop() {
897                            Some(xi) => xi,
898                            None => return Err(Error::Unreachable),
899                        }),
900                        expr,
901                    })
902                } else {
903                    Err(Error::WrongArgs(
904                        "round: expected round(x) or round(modulus,x)".to_string(),
905                    ))
906                }
907            }
908            "min" => {
909                if !args.is_empty() {
910                    match remove_no_panic(&mut args, 0) {
911                        Some(first) => Ok(EFuncMin { first, rest: args }),
912                        None => Err(Error::Unreachable),
913                    }
914                } else {
915                    Err(Error::WrongArgs(
916                        "min: expected one or more args".to_string(),
917                    ))
918                }
919            }
920            "max" => {
921                if !args.is_empty() {
922                    match remove_no_panic(&mut args, 0) {
923                        Some(first) => Ok(EFuncMax { first, rest: args }),
924                        None => Err(Error::Unreachable),
925                    }
926                } else {
927                    Err(Error::WrongArgs(
928                        "max: expected one or more args".to_string(),
929                    ))
930                }
931            }
932
933            "e" => {
934                if args.is_empty() {
935                    Ok(EFuncE)
936                } else {
937                    Err(Error::WrongArgs("e: expected no args".to_string()))
938                }
939            }
940            "pi" => {
941                if args.is_empty() {
942                    Ok(EFuncPi)
943                } else {
944                    Err(Error::WrongArgs("pi: expected no args".to_string()))
945                }
946            }
947
948            "sin" => {
949                if args.len() == 1 {
950                    Ok(EFuncSin(match args.pop() {
951                        Some(xi) => xi,
952                        None => return Err(Error::Unreachable),
953                    }))
954                } else {
955                    Err(Error::WrongArgs("sin: expected one arg".to_string()))
956                }
957            }
958            "cos" => {
959                if args.len() == 1 {
960                    Ok(EFuncCos(match args.pop() {
961                        Some(xi) => xi,
962                        None => return Err(Error::Unreachable),
963                    }))
964                } else {
965                    Err(Error::WrongArgs("cos: expected one arg".to_string()))
966                }
967            }
968            "tan" => {
969                if args.len() == 1 {
970                    Ok(EFuncTan(match args.pop() {
971                        Some(xi) => xi,
972                        None => return Err(Error::Unreachable),
973                    }))
974                } else {
975                    Err(Error::WrongArgs("tan: expected one arg".to_string()))
976                }
977            }
978            "asin" => {
979                if args.len() == 1 {
980                    Ok(EFuncASin(match args.pop() {
981                        Some(xi) => xi,
982                        None => return Err(Error::Unreachable),
983                    }))
984                } else {
985                    Err(Error::WrongArgs("asin: expected one arg".to_string()))
986                }
987            }
988            "acos" => {
989                if args.len() == 1 {
990                    Ok(EFuncACos(match args.pop() {
991                        Some(xi) => xi,
992                        None => return Err(Error::Unreachable),
993                    }))
994                } else {
995                    Err(Error::WrongArgs("acos: expected one arg".to_string()))
996                }
997            }
998            "atan" => {
999                if args.len() == 1 {
1000                    Ok(EFuncATan(match args.pop() {
1001                        Some(xi) => xi,
1002                        None => return Err(Error::Unreachable),
1003                    }))
1004                } else {
1005                    Err(Error::WrongArgs("atan: expected one arg".to_string()))
1006                }
1007            }
1008            "sinh" => {
1009                if args.len() == 1 {
1010                    Ok(EFuncSinH(match args.pop() {
1011                        Some(xi) => xi,
1012                        None => return Err(Error::Unreachable),
1013                    }))
1014                } else {
1015                    Err(Error::WrongArgs("sinh: expected one arg".to_string()))
1016                }
1017            }
1018            "cosh" => {
1019                if args.len() == 1 {
1020                    Ok(EFuncCosH(match args.pop() {
1021                        Some(xi) => xi,
1022                        None => return Err(Error::Unreachable),
1023                    }))
1024                } else {
1025                    Err(Error::WrongArgs("cosh: expected one arg".to_string()))
1026                }
1027            }
1028            "tanh" => {
1029                if args.len() == 1 {
1030                    Ok(EFuncTanH(match args.pop() {
1031                        Some(xi) => xi,
1032                        None => return Err(Error::Unreachable),
1033                    }))
1034                } else {
1035                    Err(Error::WrongArgs("tanh: expected one arg".to_string()))
1036                }
1037            }
1038            "asinh" => {
1039                if args.len() == 1 {
1040                    Ok(EFuncASinH(match args.pop() {
1041                        Some(xi) => xi,
1042                        None => return Err(Error::Unreachable),
1043                    }))
1044                } else {
1045                    Err(Error::WrongArgs("asinh: expected one arg".to_string()))
1046                }
1047            }
1048            "acosh" => {
1049                if args.len() == 1 {
1050                    Ok(EFuncACosH(match args.pop() {
1051                        Some(xi) => xi,
1052                        None => return Err(Error::Unreachable),
1053                    }))
1054                } else {
1055                    Err(Error::WrongArgs("acosh: expected one arg".to_string()))
1056                }
1057            }
1058            "atanh" => {
1059                if args.len() == 1 {
1060                    Ok(EFuncATanH(match args.pop() {
1061                        Some(xi) => xi,
1062                        None => return Err(Error::Unreachable),
1063                    }))
1064                } else {
1065                    Err(Error::WrongArgs("atanh: expected one arg".to_string()))
1066                }
1067            }
1068
1069            _ => {
1070                #[cfg(feature = "unsafe-vars")]
1071                match slab.unsafe_vars.get(fname_str) {
1072                    None => Ok(EFunc { name: fname, args }),
1073                    Some(&ptr) => Ok(EUnsafeVar { name: fname, ptr }),
1074                }
1075
1076                #[cfg(not(feature = "unsafe-vars"))]
1077                Ok(EFunc { name: fname, args })
1078            }
1079        }
1080    }
1081
1082    fn read_printfunc(
1083        &self,
1084        slab: &mut ParseSlab,
1085        bs: &mut &[u8],
1086        depth: usize,
1087        open_parenth: u8,
1088    ) -> Result<PrintFunc, Error> {
1089        let close_parenth = match open_parenth {
1090            b'(' => b')',
1091            b'[' => b']',
1092            _ => return Err(Error::Expected("'(' or '['".to_string())),
1093        };
1094        let mut args = Vec::<ExpressionOrString>::with_capacity(8);
1095        loop {
1096            spaces!(bs);
1097            match peek!(bs) {
1098                Some(b) => {
1099                    if b == close_parenth {
1100                        skip!(bs);
1101                        break;
1102                    }
1103                }
1104                None => {
1105                    return Err(Error::EofWhileParsing("print".to_string()));
1106                }
1107            }
1108            if !args.is_empty() {
1109                match read!(bs) {
1110                    Ok(b',') | Ok(b';') => {}
1111                    _ => {
1112                        return Err(Error::Expected("',' or ';'".to_string()));
1113                    }
1114                }
1115            }
1116            args.push(self.read_expressionorstring(slab, bs, depth + 1)?);
1117        }
1118
1119        Ok(PrintFunc(args))
1120    }
1121
1122    fn read_expressionorstring(
1123        &self,
1124        slab: &mut ParseSlab,
1125        bs: &mut &[u8],
1126        depth: usize,
1127    ) -> Result<ExpressionOrString, Error> {
1128        match Self::read_string(bs)? {
1129            Pass => {}
1130            Bite(s) => return Ok(EStr(s)),
1131        }
1132        Ok(EExpr(self.read_expression(slab, bs, depth + 1, false)?))
1133    }
1134
1135    // TODO: Improve this logic, especially to handle embedded quotes:
1136    fn read_string(bs: &mut &[u8]) -> Result<Token<String>, Error> {
1137        spaces!(bs);
1138
1139        match peek!(bs) {
1140            None => {
1141                return Err(Error::EofWhileParsing(
1142                    "opening quote of string".to_string(),
1143                ))
1144            }
1145            Some(b'"') => {
1146                skip!(bs);
1147            }
1148            Some(_) => return Ok(Pass),
1149        }
1150
1151        let mut toklen = 0;
1152        while match peek_n!(bs, toklen) {
1153            None => false,
1154            Some(b'"') => false,
1155            Some(_) => true,
1156        } {
1157            toklen = toklen + 1;
1158        }
1159
1160        let out = from_utf8(&bs[..toklen])
1161            .map_err(|_| Error::Utf8ErrorWhileParsing("string".to_string()))?;
1162        skip_n!(bs, toklen);
1163        match read!(bs) {
1164            Err(Error::EOF) => Err(Error::EofWhileParsing("string".to_string())),
1165            Err(_) => Err(Error::Unreachable),
1166            Ok(b'"') => Ok(Bite(out.to_string())),
1167            Ok(_) => Err(Error::Unreachable),
1168        }
1169    }
1170}
1171
1172impl Default for Parser {
1173    fn default() -> Self {
1174        Self::new()
1175    }
1176}
1177impl Default for Expression {
1178    fn default() -> Self {
1179        Expression {
1180            first: Default::default(),
1181            pairs: Vec::new(),
1182        }
1183    }
1184}
1185impl Default for Value {
1186    fn default() -> Self {
1187        EConstant(std::f64::NAN)
1188    }
1189}
1190
1191// A version of Vec::remove that doesn't panic:
1192// (Mostly copy-pasted from https://doc.rust-lang.org/src/alloc/vec.rs.html#991-1010 .)
1193pub(crate) fn remove_no_panic<T>(vself: &mut Vec<T>, index: usize) -> Option<T> {
1194    let len = vself.len();
1195    if index >= len {
1196        return None;
1197    }
1198    unsafe {
1199        // infallible
1200        let ret;
1201        {
1202            // the place we are taking from.
1203            let ptr = vself.as_mut_ptr().add(index);
1204            // copy it out, unsafely having a copy of the value on
1205            // the stack and in the vector at the same time.
1206            ret = ptr::read(ptr);
1207
1208            // Shift everything down to fill in that spot.
1209            ptr::copy(ptr.offset(1), ptr, len - index - 1);
1210        }
1211        vself.set_len(len - 1);
1212        Some(ret)
1213    }
1214}
1215
1216#[cfg(test)]
1217mod internal_tests {
1218    use super::*;
1219    use crate::slab::Slab;
1220
1221    //// Commented so I can compile with stable Rust.
1222    // extern crate test;
1223    // use test::{Bencher, black_box};
1224
1225    #[test]
1226    fn rem_no_panic() {
1227        let mut v = vec![1u8, 2, 3];
1228        assert_eq!(format!("{:?}", v), "[1, 2, 3]");
1229        assert_eq!(remove_no_panic(&mut v, 1), Some(2));
1230        assert_eq!(remove_no_panic(&mut v, 10), None);
1231        assert_eq!(format!("{:?}", v), "[1, 3]");
1232    }
1233
1234    #[test]
1235    fn util() {
1236        match (|| -> Result<(), Error> {
1237            let bsarr = [1, 2, 3];
1238            let bs = &mut &bsarr[..];
1239
1240            assert_eq!(peek!(bs), Some(1));
1241            assert_eq!(peek_n!(bs, 1), Some(2));
1242            assert_eq!(peek_n!(bs, 2), Some(3));
1243            assert_eq!(peek_n!(bs, 3), None);
1244
1245            assert_eq!(read!(bs)?, 1);
1246            skip!(bs);
1247            assert_eq!(read!(bs)?, 3);
1248            match read!(bs).err() {
1249                Some(Error::EOF) => {}
1250                _ => panic!("I expected an EOF"),
1251            }
1252
1253            Ok(())
1254        })() {
1255            Ok(_) => {}
1256            Err(_) => {
1257                unimplemented!();
1258            }
1259        }
1260
1261        assert!((&[0u8; 0]).is_empty());
1262        assert!(!(&[1]).is_empty());
1263        assert!((b"").is_empty());
1264        assert!(!(b"x").is_empty());
1265
1266        let b = b' ';
1267        assert!(is_space!(b));
1268        let b = b'\t';
1269        assert!(is_space!(b));
1270        let b = b'\r';
1271        assert!(is_space!(b));
1272        let b = b'\n';
1273        assert!(is_space!(b));
1274        let b = b'a';
1275        assert!(!is_space!(b));
1276        let b = b'1';
1277        assert!(!is_space!(b));
1278        let b = b'.';
1279        assert!(!is_space!(b));
1280
1281        {
1282            let bsarr = b"  abc 123   ";
1283            let bs = &mut &bsarr[..];
1284            spaces!(bs);
1285            assert_eq!(bs, b"abc 123   ");
1286        }
1287    }
1288
1289    #[test]
1290    fn priv_tests() {
1291        assert!(Parser::is_varname_byte_opt(Some(b'a'), 0));
1292
1293        let mut slab = Slab::new();
1294
1295        {
1296            let bsarr = b"12.34";
1297            let bs = &mut &bsarr[..];
1298            assert_eq!(
1299                Parser::new().read_value(&mut slab.ps, bs, 0),
1300                Ok(EConstant(12.34))
1301            );
1302        }
1303    }
1304
1305    //// Commented so I can compile this library with stable Rust.
1306    // #[bench]
1307    // #[allow(non_snake_case)]
1308    // fn spaces_1M(bencher:&mut Bencher) {
1309    //     let zero = "abc".as_bytes();
1310    //     let one = " abc".as_bytes();
1311    //     let two = "  abc".as_bytes();
1312    //     bencher.iter(|| {
1313    //         let (z1,z2,z3,z4) = (&zero[..], &zero[..], &zero[..], &zero[..]);  // Localize
1314    //         let (o1,o2) = (&one[..], &one[..]);
1315    //         let t1 = &two[..];
1316    //         for _ in 0..1000 {
1317    //             let (z1,z2,z3,z4) = (&mut &z1[..], &mut &z2[..], &mut &z3[..], &mut &z4[..]);
1318    //             let (o1,o2) = (&mut &o1[..], &mut &o2[..]);
1319    //             let t1 = &mut &t1[..];
1320    //             spaces!(z1);
1321    //             spaces!(z2);
1322    //             spaces!(z3);
1323    //             spaces!(z4);
1324    //             spaces!(o1);
1325    //             spaces!(o2);
1326    //             spaces!(t1);
1327    //             black_box(z1);
1328    //             black_box(z2);
1329    //             black_box(z3);
1330    //             black_box(z4);
1331    //             black_box(o1);
1332    //             black_box(o2);
1333    //             black_box(t1);
1334    //         }
1335    //     });
1336    // }
1337}
fasteval2/parser.rs

fasteval2/
parser.rs
