fuchsia_triage/metrics/
parse.rs

Help
1// Copyright 2019 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::metrics::context::ParsingContext;
6use crate::metrics::variable::VariableName;
7use crate::metrics::{ExpressionTree, Function, MathFunction, MetricValue};
8use anyhow::{format_err, Error};
9use nom::branch::alt;
10use nom::bytes::complete::{is_not, tag, take_while, take_while_m_n};
11use nom::character::complete::{char, none_of, one_of};
12use nom::combinator::{all_consuming, map, opt, peek, recognize};
13use nom::multi::{fold_many0, many0, separated_list0};
14use nom::sequence::{delimited, pair, preceded, separated_pair, terminated};
15use nom::Err::{self, Incomplete};
16use nom::{AsChar, IResult, Input, Parser};
17use nom_language::error::{convert_error, VerboseError};
18
19pub type ParsingResult<'a, O> = IResult<ParsingContext<'a>, O, VerboseError<ParsingContext<'a>>>;
20
21// The 'nom' crate supports buiding parsers by combining functions into more
22// powerful functions. Combined functions can be applied to a sequence of
23// chars (or bytes) and will parse into the sequence as far as possible (left
24// to right) returning the result of the parse and the remainder of the sequence.
25//
26// This parser parses infix math expressions with operators
27// + - * / > < >= <= == () [] following standard order of operations.
28// It also supports functions like FuncName(expr, expr, expr...)
29// () must contain one expression, except when it's part of a function.
30// [] contains a comma-separated list of expressions.
31//
32// Combinators (parse-function builders) used in this parser:
33// alt: Allows backtracking and trying an alternative parse.
34// tag: Matches and returns a fixed string.
35// take_while: Matches and returns characters as long as they satisfy a condition.
36// take_while_m_n: Take_while constrained to return at least M and at most N chars.
37// char: Matches and returns a single character.
38// all_consuming: The parser must use all characters.
39// map: Applies a transformation function to the return type of a parser.
40// double: Parses an f64 and returns its value.
41// delimited: Applies three parsers and returns the result of the middle one.
42// preceded: Applies two parsers and returns the result of the second one.
43// terminated: Applies two parsers and returns the result of the first one.
44// separated_list: Takes two parsers, a separator and element, and returns a Vec of elements.
45// separated_pair: Applies three parsers and returns a tuple of the first and third results.
46// tuple: Takes a tuple of parsers and returns a tuple of the corresponding results.
47//
48//  In addition, two boolean functions match characters:
49// is_alphabetic: ASCII a..zA..Z
50// is_alphanumeric: ASCII a..zA..Z0..9
51//
52// VerboseError stores human-friendly information about parse errors.
53// convert_error() produces a human-friendly string from a VerboseError.
54//
55// This parser accepts whitespace. For consistency, whitespace is accepted
56//  _before_ the non-whitespace that the parser is trying to match.
57
58// Matches 0 or more whitespace characters: \n, \t, ' '.
59fn whitespace(i: ParsingContext<'_>) -> ParsingResult<'_, ParsingContext<'_>> {
60    take_while(|c| " \n\t".contains(c)).parse(i)
61}
62
63// spewing() is useful for debugging. If you touch this file, you will
64// likely want to uncomment and use it. Wrap any parser in
65// spewing("diagnostic string", parser) to get lots of printouts showing
66// how far the parser has gotten and what strings it's seeing.
67// Remember that every backtrack (alt) will produce lots of output.
68
69/*use std::cmp::min;
70fn spewing<'a, F, O>(
71    note: &'static str,
72    parser: F,
73) -> impl FnMut(&'a str) -> IResult<&'a str, O, VerboseError<&'a str>>
74where
75    F: FnMut(&'a str) -> IResult<&'a str, O, VerboseError<&'a str>>,
76{
77    let dumper = move |i: ParsingContext<'_>| {
78        println!("{}:'{}'", note, &i[..min(20, i.len())]);
79        Ok((i, ()))
80    };
81    preceded(dumper, parser)
82}*/
83
84// A bit of syntactic sugar - just adds optional whitespace in front of any parser.
85fn spaced<'a, F, O>(
86    parser: F,
87) -> impl Parser<ParsingContext<'a>, Output = O, Error = VerboseError<ParsingContext<'a>>>
88where
89    F: Parser<ParsingContext<'a>, Output = O, Error = VerboseError<ParsingContext<'a>>>,
90{
91    preceded(whitespace, parser)
92}
93
94// Parses a name with the first character alphabetic or '_' and 0..n additional
95// characters alphanumeric or '_'.
96fn simple_name(i: ParsingContext<'_>) -> ParsingResult<'_, &str> {
97    map(
98        recognize(pair(
99            take_while_m_n(1, 1, |c: char| c.is_ascii() && (c.is_alpha() || c == '_')),
100            take_while(|c: char| c.is_ascii() && (c.is_alphanum() || c == '_')),
101        )),
102        |name: ParsingContext<'_>| name.into_inner(),
103    )
104    .parse(i)
105}
106
107// Parses two simple names joined by "::" to form a namespaced name. Returns a
108// Metric-type Expression holding the namespaced name.
109fn name_with_namespace(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
110    map(separated_pair(simple_name, tag("::"), simple_name), move |(s1, s2)| {
111        ExpressionTree::Variable(VariableName::new(format!("{}::{}", s1, s2)))
112    })
113    .parse(i)
114}
115
116// Parses a simple name with no namespace and returns a Metric-type Expression
117// holding the simple name.
118fn name_no_namespace(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
119    map(simple_name, move |s: &str| ExpressionTree::Variable(VariableName::new(s.to_string())))
120        .parse(i)
121}
122
123// Parses either a simple or namespaced name and returns a Metric-type Expression
124// holding it.
125fn name(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
126    alt((name_with_namespace, name_no_namespace)).parse(i)
127}
128
129// Parse a decimal literal as specified in https://doc.rust-lang.org/reference/tokens.html#integer-literals
130// DEC_DIGIT (DEC_DIGIT|_)*
131// Parse the first decimal digit
132// Consume all the remaining (DEC_DIGIT|_)
133fn decimal_literal(i: ParsingContext<'_>) -> ParsingResult<'_, &str> {
134    map(recognize((one_of("0123456789"), many0(one_of("0123456789_")))), |d: ParsingContext<'_>| {
135        d.into_inner()
136    })
137    .parse(i)
138}
139
140// Parse float exponent as specified in https://doc.rust-lang.org/reference/tokens.html#floating-point-literals
141// (e|E)(+|-)?(DEC_DIGIT|_)*(DEC_DIGIT)(DEC_DIGIT|_)*
142// This essentially means that there should be atleast one DEC_DIGIT after (e|E)(+|-)?
143// So we consume all the preceding '_'
144// The next digit must be a DEC_DIGIT, if not the float exponent is not valid
145// Consume all the remaining (DEC_DIGIT|_)
146fn float_exponent(i: ParsingContext<'_>) -> ParsingResult<'_, &str> {
147    map(
148        recognize((
149            one_of("eE"),
150            opt(one_of("+-")),
151            many0(char('_')),
152            one_of("0123456789"),
153            many0(one_of("0123456789_")),
154        )),
155        |exponent: ParsingContext<'_>| exponent.into_inner(),
156    )
157    .parse(i)
158}
159
160// Parse a floating point literal
161// This mostly follows from https://doc.rust-lang.org/reference/tokens.html#floating-point-literals
162// with the addition of . DECIMAL_LITERAL
163// Consume the starting optional sign (+|-)
164// We try to parse the remaining string as
165//  1. . DECIMAL_LITERAL (FLOAT_EXPONENT)? Eg. .12_34___ (0.1234) .2e__2_ (20.0)
166//  2. DECIMAL_LITERAL FLOAT_EXPONENT Eg. 1_234_567___8E-__1_0 (0.0012345678)
167//  3. DECIMAL_LITERAL . DECIMAL_LITERAL (FLOAT_EXPONENT)? Eg. 1__234__.12E-3 (1.23412)
168//  4. DECIMAL_LITERAL . (not followed by '.', '_', 'e') Eg. 1.
169//  5. DECIMAL_LITERAL Eg. 1_2__3__4 (1234)
170fn double(i: ParsingContext<'_>) -> ParsingResult<'_, f64> {
171    map(
172        recognize((
173            opt(one_of("+-")),
174            alt((
175                recognize((char('.'), decimal_literal, opt(float_exponent))),
176                recognize((decimal_literal, float_exponent)),
177                recognize((decimal_literal, char('.'), decimal_literal, opt(float_exponent))),
178                recognize((decimal_literal, char('.'), peek(none_of("._")))),
179                recognize((decimal_literal, char('.'))),
180                recognize(decimal_literal),
181            )),
182        )),
183        |d: ParsingContext<'_>| d.into_inner().replace("_", "").parse::<f64>().unwrap(),
184    )
185    .parse(i)
186}
187
188// Returns a Value-type expression holding either an Int or Float number.
189//
190// Every int can be parsed as a float. The float parser is applied first. If
191// it finds a number, number() attempts to parse those same characters as an int.
192// If it succeeds, it treats the number as an Int type.
193// Note that this handles unary + and -.
194fn number(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
195    match double(i) {
196        Ok((remaining, float)) => {
197            let number_len = i.input_len() - remaining.input_len(); // How many characters were accepted
198            match i.take(number_len).into_inner().parse::<i64>() {
199                Ok(int) => Ok((remaining, ExpressionTree::Value(MetricValue::Int(int)))),
200                Err(_) => Ok((remaining, ExpressionTree::Value(MetricValue::Float(float)))),
201            }
202        }
203        Err(error) => Err(error),
204    }
205}
206
207macro_rules! any_string {
208    ($left:expr, $mid:expr, $right:expr, $i:expr) => {{
209        let mid = map(recognize($mid), |s: ParsingContext<'_>| {
210            ExpressionTree::Value(MetricValue::String(s.into_inner().to_string()))
211        });
212        delimited($left, mid, $right).parse($i)
213    }};
214}
215
216fn single_quote_string(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
217    any_string!(char('\''), is_not("'"), char('\''), i)
218}
219
220fn escaped_single_quote_string(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
221    any_string!(tag("\'"), is_not("\'"), tag("\'"), i)
222}
223
224fn double_quote_string(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
225    any_string!(char('\"'), is_not("\""), char('\"'), i)
226}
227
228fn escaped_double_quote_string(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
229    any_string!(tag("\""), is_not("\""), tag("\""), i)
230}
231
232// Returns a Value-type expression holding a String.
233//
234// Will match the following strings
235// - "'hello'"
236// - '"hello"'
237// - "\"hello\""
238// - '\'hello\''
239fn string(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
240    alt((
241        single_quote_string,
242        escaped_single_quote_string,
243        double_quote_string,
244        escaped_double_quote_string,
245    ))
246    .parse(i)
247}
248
249macro_rules! function {
250    ($tag:expr, $function:ident) => {
251        (map(spaced(tag($tag)), move |_| Function::$function))
252    };
253}
254
255macro_rules! math {
256    ($tag:expr, $function:ident) => {
257        (map(spaced(tag($tag)), move |_| Function::Math(MathFunction::$function)))
258    };
259}
260
261fn function_name_parser(i: ParsingContext<'_>) -> ParsingResult<'_, Function> {
262    // alt has a limited number of args, so must be nested.
263    // At some point, worry about efficiency.
264    // Make sure that if one function is a prefix of another, the longer one comes first or the
265    // shorter one will match and short-circuit.
266    alt((
267        alt((
268            function!("And", And),
269            function!("Or", Or),
270            function!("Not", Not),
271            math!("Max", Max),
272            function!("Minutes", Minutes), // Parser must try "Minutes" before "Min"
273            math!("Min", Min),
274            function!("SyslogHas", SyslogHas),
275            function!("KlogHas", KlogHas),
276            function!("BootlogHas", BootlogHas),
277            function!("Missing", Missing),
278            function!("UnhandledType", UnhandledType),
279            function!("Problem", Problem),
280            function!("Annotation", Annotation),
281            math!("Abs", Abs),
282        )),
283        alt((
284            function!("Fn", Lambda),
285            function!("Map", Map),
286            function!("Fold", Fold),
287            function!("All", All),
288            function!("Any", Any),
289            function!("Filter", Filter),
290            function!("Apply", Apply),
291            function!("CountChildren", CountChildren),
292            function!("CountProperties", CountProperties),
293            function!("Count", Count),
294            function!("Nanos", Nanos),
295            function!("Micros", Micros),
296            function!("Millis", Millis),
297            function!("Seconds", Seconds),
298            function!("Hours", Hours),
299            function!("Days", Days),
300            function!("Now", Now),
301            function!("Option", OptionF),
302            function!("StringMatches", StringMatches),
303            function!("True", True),
304            function!("False", False),
305        )),
306    ))
307    .parse(i)
308}
309
310fn function_expression(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
311    let open_paren = spaced(char('('));
312    let expressions = separated_list0(spaced(char(',')), expression_top);
313    let close_paren = spaced(char(')'));
314    let function_sequence = (function_name_parser, open_paren, expressions, close_paren);
315    map(function_sequence, move |(function, _, operands, _)| {
316        ExpressionTree::Function(function, operands)
317    })
318    .parse(i)
319}
320
321fn vector_expression(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
322    let open_bracket = spaced(char('['));
323    let expressions = separated_list0(spaced(char(',')), expression_top);
324    let close_bracket = spaced(char(']'));
325    let vector_sequence = (open_bracket, expressions, close_bracket);
326    map(vector_sequence, move |(_, items, _)| ExpressionTree::Vector(items)).parse(i)
327}
328
329// I use "primitive" to mean an expression that is not an infix operator pair:
330// a primitive value, a metric name, a function (simple name followed by
331// parenthesized expression list), or any expression contained by ( ) or [ ].
332fn expression_primitive(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
333    let paren_expr = delimited(char('('), terminated(expression_top, whitespace), char(')'));
334    let res =
335        spaced(alt((paren_expr, function_expression, vector_expression, number, string, name)))
336            .parse(i);
337    res
338}
339
340// Scans for primitive expressions separated by * and /.
341fn expression_muldiv(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
342    let (i, init) = expression_primitive(i)?;
343    let mut init = Some(init);
344    fold_many0(
345        pair(
346            alt((
347                math!("*", Mul),
348                math!("//?", IntDivChecked),
349                math!("/?", FloatDivChecked),
350                math!("//", IntDiv),
351                math!("/", FloatDiv),
352            )),
353            expression_primitive,
354        ),
355        move || init.take().unwrap(),
356        |acc, (op, expr)| ExpressionTree::Function(op, vec![acc, expr]),
357    )
358    .parse(i)
359}
360
361// Scans for muldiv expressions (which may be a single primitive expression)
362// separated by + and -. Remember unary + and - will be recognized by number().
363fn expression_addsub(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
364    let (i, init) = expression_muldiv(i)?;
365    let mut init = Some(init);
366    fold_many0(
367        pair(alt((math!("+", Add), math!("-", Sub))), expression_muldiv),
368        move || init.take().unwrap(),
369        |acc, (op, expr)| ExpressionTree::Function(op, vec![acc, expr]),
370    )
371    .parse(i)
372}
373
374// Top-level expression. Should match the entire expression string, and also
375// can be used inside parentheses.
376fn expression_top(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
377    // Note: alt() is not BNF - it's sequential. It's important to put the longer strings first.
378    // If a shorter substring succeeds where it shouldn't, the alt() may not get another chance.
379    let comparison = alt((
380        math!(">=", GreaterEq),
381        math!("<=", LessEq),
382        function!("==", Equals),
383        function!("!=", NotEq),
384        math!(">", Greater),
385        math!("<", Less),
386    ));
387    alt((
388        map((expression_addsub, comparison, expression_addsub), move |(left, op, right)| {
389            ExpressionTree::Function(op, vec![left, right])
390        }),
391        expression_addsub,
392    ))
393    .parse(i)
394}
395
396// Parses a given string into either an Error or an Expression ready
397// to be evaluated.
398pub(crate) fn parse_expression(i: &str, namespace: &str) -> Result<ExpressionTree, Error> {
399    let ctx = ParsingContext::new(i, namespace);
400    let mut match_whole = all_consuming(terminated(expression_top, whitespace));
401    match match_whole.parse(ctx) {
402        Err(Err::Error(e)) | Err(Err::Failure(e)) => Err(format_err!(
403            "Expression Error: \n{}",
404            convert_error(
405                ctx.into_inner(),
406                VerboseError {
407                    errors: e.errors.into_iter().map(|e| (e.0.into_inner(), e.1)).collect()
408                }
409            )
410        )),
411        Ok((_, result)) => Ok(result),
412        Err(Incomplete(what)) => Err(format_err!("Why did I get an incomplete? {:?}", what)),
413    }
414}
415
416#[cfg(test)]
417mod test {
418    use super::*;
419    use crate::assert_problem;
420    use crate::metrics::{Fetcher, MetricState, TrialDataFetcher};
421    use std::collections::HashMap;
422
423    // Res, simplify_fn, and get_parse are necessary because IResult can't be compared and can't
424    //   easily be matched/decomposed. Res can be compared and debug-formatted.
425    // Call get_parse(parse_function, string) to get either Ok(remainder_str, result)
426    //   or Err(descriptive_string).
427    #[derive(PartialEq, Debug)]
428    enum Res<'a, T> {
429        Ok(&'a str, T),
430        Err(String),
431    }
432
433    fn simplify_fn<'a, T: std::fmt::Debug>(i: &str, r: ParsingResult<'a, T>) -> Res<'a, T> {
434        match r {
435            Err(Err::Error(e)) => Res::Err(format!(
436                "Error: \n{:?}",
437                convert_error(
438                    i,
439                    VerboseError {
440                        errors: e.errors.into_iter().map(|e| (e.0.into_inner(), e.1)).collect()
441                    }
442                )
443            )),
444            Err(Err::Failure(e)) => Res::Err(format!(
445                "Failure: \n{:?}",
446                convert_error(
447                    i,
448                    VerboseError {
449                        errors: e.errors.into_iter().map(|e| (e.0.into_inner(), e.1)).collect()
450                    }
451                )
452            )),
453            Err(Incomplete(e)) => Res::Err(format!("Incomplete: {:?}", e)),
454            Ok((unused, result)) => Res::Ok(unused.into_inner(), result),
455        }
456    }
457
458    macro_rules! get_parse {
459        ($fn:expr, $string:expr) => {
460            simplify_fn($string, $fn(ParsingContext::new($string, /*namespace= */ "")))
461        };
462    }
463
464    impl<T> Res<'_, T> {
465        fn is_err(&self) -> bool {
466            match self {
467                Res::Err(_) => true,
468                Res::Ok(_, _) => false,
469            }
470        }
471    }
472
473    #[fuchsia::test]
474    fn parse_vectors() {
475        fn v(i: i64) -> ExpressionTree {
476            ExpressionTree::Value(MetricValue::Int(i))
477        }
478
479        assert_eq!(
480            get_parse!(expression_primitive, "[1,2]"),
481            Res::Ok("", ExpressionTree::Vector(vec![v(1), v(2)]))
482        );
483        assert_eq!(
484            get_parse!(expression_primitive, " [ 1 , 2 ] "),
485            Res::Ok(" ", ExpressionTree::Vector(vec![v(1), v(2)]))
486        );
487        assert_eq!(
488            get_parse!(expression_primitive, "[1]"),
489            Res::Ok("", ExpressionTree::Vector(vec![v(1)]))
490        );
491        assert_eq!(
492            get_parse!(expression_primitive, "[]"),
493            Res::Ok("", ExpressionTree::Vector(Vec::new()))
494        );
495        let first = ExpressionTree::Function(Function::Math(MathFunction::Add), vec![v(1), v(2)]);
496        let second = ExpressionTree::Function(Function::Math(MathFunction::Sub), vec![v(2), v(1)]);
497        assert_eq!(
498            get_parse!(expression_primitive, "[1+2, 2-1]"),
499            Res::Ok("", ExpressionTree::Vector(vec![first, second]))
500        );
501        // Verify that we reject un-closed braces.
502        assert!(get_parse!(expression_primitive, "[1+2, 2-1").is_err());
503        // Verify that it's just the unclosed brace that was the problem in the previous line.
504        // (The parser will only look for the first complete primitive expression.)
505        assert_eq!(get_parse!(expression_primitive, "1+2, 2-1"), Res::Ok("+2, 2-1", v(1)));
506        assert!(get_parse!(expression_primitive, "]").is_err());
507        assert!(get_parse!(expression_primitive, "[").is_err());
508    }
509
510    #[fuchsia::test]
511    fn parse_numbers() {
512        // No leading extraneous characters allowed in number, not even whitespace.
513        assert!(get_parse!(number, "f5").is_err());
514        assert!(get_parse!(number, " 1").is_err());
515        // Empty string should fail
516        assert!(get_parse!(number, "").is_err());
517        // Trailing characters will be returned as unused remainder
518        assert_eq!(
519            get_parse!(number, "1 "),
520            Res::Ok(" ", ExpressionTree::Value(MetricValue::Int(1)))
521        );
522        assert_eq!(
523            get_parse!(number, "1a"),
524            Res::Ok("a", ExpressionTree::Value(MetricValue::Int(1)))
525        );
526        // If it parses as int, it's an int.
527        assert_eq!(
528            get_parse!(number, "234"),
529            Res::Ok("", ExpressionTree::Value(MetricValue::Int(234)))
530        );
531        // Otherwise it's a float.
532        assert_eq!(
533            get_parse!(number, "234.0"),
534            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0)))
535        );
536        assert_eq!(
537            get_parse!(number, "234.0e-5"),
538            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0e-5)))
539        );
540        // Leading -, +, 0 are all OK for int
541        assert_eq!(
542            get_parse!(number, "0"),
543            Res::Ok("", ExpressionTree::Value(MetricValue::Int(0)))
544        );
545        assert_eq!(
546            get_parse!(number, "00234"),
547            Res::Ok("", ExpressionTree::Value(MetricValue::Int(234)))
548        );
549        assert_eq!(
550            get_parse!(number, "+234"),
551            Res::Ok("", ExpressionTree::Value(MetricValue::Int(234)))
552        );
553        assert_eq!(
554            get_parse!(number, "-234"),
555            Res::Ok("", ExpressionTree::Value(MetricValue::Int(-234)))
556        );
557        // Leading +, -, 0 are OK for float.
558        assert_eq!(
559            get_parse!(number, "0.0"),
560            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.0)))
561        );
562        assert_eq!(
563            get_parse!(number, "00234.0"),
564            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0)))
565        );
566        assert_eq!(
567            get_parse!(number, "+234.0"),
568            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0)))
569        );
570        assert_eq!(
571            get_parse!(number, "-234.0"),
572            Res::Ok("", ExpressionTree::Value(MetricValue::Float(-234.0)))
573        );
574        // Leading and trailing periods parse as valid float.
575        assert_eq!(
576            get_parse!(number, ".1"),
577            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.1)))
578        );
579        assert_eq!(
580            get_parse!(number, "1."),
581            Res::Ok("", ExpressionTree::Value(MetricValue::Float(1.0)))
582        );
583        assert_eq!(
584            get_parse!(number, "1.a"),
585            Res::Ok("a", ExpressionTree::Value(MetricValue::Float(1.0)))
586        );
587
588        assert_eq!(
589            get_parse!(number, ".12_34___"),
590            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.1234)))
591        );
592        assert_eq!(
593            get_parse!(number, ".2e__2_"),
594            Res::Ok("", ExpressionTree::Value(MetricValue::Float(20.0)))
595        );
596        assert_eq!(
597            get_parse!(number, "1_234_567___8E-__1_0__"),
598            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.0012345678)))
599        );
600        assert_eq!(
601            get_parse!(number, "1__234__.12E-3__"),
602            Res::Ok("", ExpressionTree::Value(MetricValue::Float(1.23412)))
603        );
604        assert_eq!(
605            get_parse!(number, "1_2__3__4__"),
606            Res::Ok("", ExpressionTree::Value(MetricValue::Int(1234)))
607        );
608
609        // number cannot begin with '_'
610        assert!(get_parse!(number, "_100").is_err());
611    }
612
613    #[fuchsia::test]
614    fn parse_string() {
615        // needs to have quotes
616        assert!(get_parse!(string, "OK").is_err());
617
618        // needs to close its quotes
619        assert!(get_parse!(string, "'OK").is_err());
620
621        assert_eq!(
622            get_parse!(string, "'OK'"),
623            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
624        );
625        assert_eq!(
626            get_parse!(string, "'OK'a"),
627            Res::Ok("a", ExpressionTree::Value(MetricValue::String("OK".to_string())))
628        );
629        assert_eq!(
630            get_parse!(string, r#""OK""#),
631            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
632        );
633        assert_eq!(
634            get_parse!(string, "\'OK\'"),
635            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
636        );
637        assert_eq!(
638            get_parse!(string, "\"OK\""),
639            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
640        );
641
642        // can handle nested qoutes
643        assert_eq!(
644            get_parse!(string, r#"'a"b'"#),
645            Res::Ok("", ExpressionTree::Value(MetricValue::String(r#"a"b"#.to_string())))
646        );
647        assert_eq!(
648            get_parse!(string, r#""a'b""#),
649            Res::Ok("", ExpressionTree::Value(MetricValue::String("a'b".to_string())))
650        );
651
652        // can handle whitespace
653        assert_eq!(
654            get_parse!(string, "'OK OK'"),
655            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK OK".to_string())))
656        );
657
658        // can parse strings that are numbers
659        assert_eq!(
660            get_parse!(string, "'123'"),
661            Res::Ok("", ExpressionTree::Value(MetricValue::String("123".to_string())))
662        );
663    }
664
665    macro_rules! variable_expression {
666        ($name:expr) => {
667            ExpressionTree::Variable(VariableName::new($name.to_owned()))
668        };
669    }
670
671    #[fuchsia::test]
672    fn parse_names_no_namespace() {
673        assert_eq!(get_parse!(name_no_namespace, "abc"), Res::Ok("", variable_expression!("abc")));
674        assert_eq!(get_parse!(name_no_namespace, "bc."), Res::Ok(".", variable_expression!("bc")));
675        // Names can contain digits and _ but can't start with digits
676        assert_eq!(
677            get_parse!(name_no_namespace, "bc42."),
678            Res::Ok(".", variable_expression!("bc42"))
679        );
680        assert!(get_parse!(name_no_namespace, "42bc.").is_err());
681        assert_eq!(
682            get_parse!(name_no_namespace, "_bc42_"),
683            Res::Ok("", variable_expression!("_bc42_"))
684        );
685        assert_eq!(
686            get_parse!(name_no_namespace, "_bc42_::abc"),
687            Res::Ok("::abc", variable_expression!("_bc42_"))
688        );
689        assert_eq!(
690            get_parse!(name_no_namespace, "_bc42_:abc"),
691            Res::Ok(":abc", variable_expression!("_bc42_"))
692        );
693    }
694
695    #[fuchsia::test]
696    fn parse_names_with_namespace() {
697        assert_eq!(
698            get_parse!(name_with_namespace, "_bc42_::abc"),
699            Res::Ok("", variable_expression!("_bc42_::abc"))
700        );
701        assert_eq!(
702            get_parse!(name_with_namespace, "_bc42_::abc::def"),
703            Res::Ok("::def", variable_expression!("_bc42_::abc"))
704        );
705        assert!(get_parse!(name_with_namespace, "_bc42_:abc::def").is_err());
706    }
707
708    #[fuchsia::test]
709    fn parse_names() {
710        assert_eq!(
711            get_parse!(name, "_bc42_::abc"),
712            Res::Ok("", variable_expression!("_bc42_::abc"))
713        );
714        assert_eq!(
715            get_parse!(name, "_bc42_:abc::def"),
716            Res::Ok(":abc::def", variable_expression!("_bc42_"))
717        );
718        assert_eq!(
719            get_parse!(name, "_bc42_::abc::def"),
720            Res::Ok("::def", variable_expression!("_bc42_::abc"))
721        );
722    }
723
724    macro_rules! eval {
725        ($e:expr) => {
726            MetricState::evaluate_math($e)
727        };
728    }
729
730    #[fuchsia::test]
731    fn parse_number_types() -> Result<(), Error> {
732        assert_eq!(eval!("2"), MetricValue::Int(2));
733        assert_eq!(eval!("2+3"), MetricValue::Int(5));
734        assert_eq!(eval!("2.0+3"), MetricValue::Float(5.0));
735        assert_eq!(eval!("2+3.0"), MetricValue::Float(5.0));
736        assert_eq!(eval!("2.0+2.0"), MetricValue::Float(4.0));
737
738        Ok(())
739    }
740
741    #[fuchsia::test]
742    fn parse_div_operations() -> Result<(), Error> {
743        assert_eq!(eval!("5.0/2"), MetricValue::Float(2.5));
744        assert_eq!(eval!("-5.0/2"), MetricValue::Float(-2.5));
745        assert_eq!(eval!("5.0/2.0"), MetricValue::Float(2.5));
746        assert_eq!(eval!("-5.0/2.0"), MetricValue::Float(-2.5));
747        assert_eq!(eval!("5/2"), MetricValue::Float(2.5));
748        assert_eq!(eval!("-5/2"), MetricValue::Float(-2.5));
749
750        // int division should truncate towards zero
751        assert_eq!(eval!("5.0//2"), MetricValue::Float(2.0));
752        assert_eq!(eval!("-5.0//2"), MetricValue::Float(-2.0));
753        assert_eq!(eval!("5.0//2.0"), MetricValue::Float(2.0));
754        assert_eq!(eval!("-5.0//2.0"), MetricValue::Float(-2.0));
755        assert_eq!(eval!("5//2"), MetricValue::Int(2));
756        assert_eq!(eval!("-5//2"), MetricValue::Int(-2));
757
758        // test truncation happens after division
759        assert_eq!(eval!("5000//5.1"), MetricValue::Float(980.0));
760        Ok(())
761    }
762
763    #[fuchsia::test]
764    fn parse_operator_precedence() -> Result<(), Error> {
765        assert_eq!(eval!("2+3*4"), MetricValue::Int(14));
766        assert_eq!(eval!("2+3*4>14-1*1"), MetricValue::Bool(true));
767        assert_eq!(eval!("3*4+2"), MetricValue::Int(14));
768        assert_eq!(eval!("2-3-4"), MetricValue::Int(-5));
769        assert_eq!(eval!("6//3*4"), MetricValue::Int(8));
770        assert_eq!(eval!("6//?3*4"), MetricValue::Int(8));
771        assert_eq!(eval!("6/3*4"), MetricValue::Float(8.0));
772        assert_eq!(eval!("6/?3*4"), MetricValue::Float(8.0));
773        assert_eq!(eval!("8/4/2"), MetricValue::Float(1.0));
774        assert_eq!(eval!("8/4*2"), MetricValue::Float(4.0));
775        assert_eq!(eval!("2-3-4"), MetricValue::Int(-5));
776        assert_eq!(eval!("(2+3)*4"), MetricValue::Int(20));
777        assert_eq!(eval!("2++4"), MetricValue::Int(6));
778        assert_eq!(eval!("2+-4"), MetricValue::Int(-2));
779        assert_eq!(eval!("2-+4"), MetricValue::Int(-2));
780        assert_eq!(eval!("2--4"), MetricValue::Int(6));
781        Ok(())
782    }
783
784    #[fuchsia::test]
785    fn division_by_zero() -> Result<(), Error> {
786        assert_problem!(eval!("4/0"), "ValueError: Division by zero");
787        assert_problem!(eval!("4//0"), "ValueError: Division by zero");
788        assert_problem!(eval!("4/?0"), "Ignore: ValueError: Division by zero");
789        assert_problem!(eval!("4//?0"), "Ignore: ValueError: Division by zero");
790        Ok(())
791    }
792
793    #[fuchsia::test]
794    fn parser_accepts_whitespace() -> Result<(), Error> {
795        assert_eq!(eval!(" 2 + +3 * 4 - 5 // ( -2 + Min ( -2 , 3 ) ) "), MetricValue::Int(15));
796        Ok(())
797    }
798
799    #[fuchsia::test]
800    fn parser_comparisons() -> Result<(), Error> {
801        assert_eq!(
802            format!("{:?}", parse_expression("2>1", /*namespace= */ "")),
803            "Ok(Function(Math(Greater), [Value(Int(2)), Value(Int(1))]))"
804        );
805        assert_eq!(eval!("2>2"), MetricValue::Bool(false));
806        assert_eq!(eval!("2>=2"), MetricValue::Bool(true));
807        assert_eq!(eval!("2<2"), MetricValue::Bool(false));
808        assert_eq!(eval!("2<=2"), MetricValue::Bool(true));
809        assert_eq!(eval!("2==2"), MetricValue::Bool(true));
810        assert_eq!(eval!("2==2.0"), MetricValue::Bool(true));
811
812        // can do string comparison
813        assert_eq!(eval!("'a'=='a'"), MetricValue::Bool(true));
814        assert_eq!(eval!("'a'!='a'"), MetricValue::Bool(false));
815        assert_eq!(eval!("'a'!='b'"), MetricValue::Bool(true));
816
817        // check variants of string parsing
818        assert_eq!(eval!(r#""a"=="a""#), MetricValue::Bool(true));
819        assert_eq!(eval!(r#"'a'=="a""#), MetricValue::Bool(true));
820
821        // There can be only one.
822        assert!(parse_expression("2==2==2", /* namespace= */ "").is_err());
823        Ok(())
824    }
825
826    #[fuchsia::test]
827    fn parser_boolean_functions_value() -> Result<(), Error> {
828        assert_eq!(
829            format!("{:?}", parse_expression("Not(2>1)", /* namespace= */ "")),
830            "Ok(Function(Not, [Function(Math(Greater), [Value(Int(2)), Value(Int(1))])]))"
831        );
832        assert_eq!(eval!("And(2>1, 2>2)"), MetricValue::Bool(false));
833        assert_eq!(eval!("And(2>2, 2>1)"), MetricValue::Bool(false));
834        assert_eq!(eval!("And(2>2, 2>2)"), MetricValue::Bool(false));
835        assert_eq!(eval!("And(2>1, 2>1)"), MetricValue::Bool(true));
836        assert_eq!(eval!("Or(2>1, 2>2)"), MetricValue::Bool(true));
837        assert_eq!(eval!("Or(2>2, 2>1)"), MetricValue::Bool(true));
838        assert_eq!(eval!("Or(2>2, 2>2)"), MetricValue::Bool(false));
839        assert_eq!(eval!("Or(2>1, 2>1)"), MetricValue::Bool(true));
840        assert_eq!(eval!("Not(2>1)"), MetricValue::Bool(false));
841        assert_eq!(eval!("Not(2>2)"), MetricValue::Bool(true));
842        Ok(())
843    }
844
845    #[fuchsia::test]
846    fn parser_boolean_functions_args() -> Result<(), Error> {
847        assert_eq!(eval!("And(2>1)"), MetricValue::Bool(true));
848        assert_eq!(eval!("And(2>1, 2>1, 2>1)"), MetricValue::Bool(true));
849        assert_problem!(eval!("And()"), "SyntaxError: No operands in boolean expression");
850        assert_eq!(eval!("Or(2>1)"), MetricValue::Bool(true));
851        assert_eq!(eval!("Or(2>1, 2>1, 2>1)"), MetricValue::Bool(true));
852        assert_problem!(eval!("Or()"), "SyntaxError: No operands in boolean expression");
853        assert_problem!(
854            eval!("Not(2>1, 2>1)"),
855            "SyntaxError: Wrong number of arguments (2) for unary bool operator"
856        );
857        assert_problem!(
858            eval!("Not()"),
859            "SyntaxError: Wrong number of arguments (0) for unary bool operator"
860        );
861        Ok(())
862    }
863
864    #[fuchsia::test]
865    fn parser_maxmin_functions() -> Result<(), Error> {
866        assert_eq!(eval!("Max(2, 5, 3, -1)"), MetricValue::Int(5));
867        assert_eq!(eval!("Min(2, 5, 3, -1)"), MetricValue::Int(-1));
868        assert_eq!(eval!("Min(2)"), MetricValue::Int(2));
869        assert_eq!(eval!("Max(2)"), MetricValue::Int(2));
870        assert_problem!(eval!("Max()"), "SyntaxError: No operands in math expression");
871        assert_problem!(eval!("Min()"), "SyntaxError: No operands in math expression");
872        Ok(())
873    }
874
875    #[fuchsia::test]
876    fn parser_time_functions() -> Result<(), Error> {
877        assert_eq!(eval!("Nanos(5)"), MetricValue::Int(5));
878        assert_eq!(eval!("Micros(4)"), MetricValue::Int(4_000));
879        assert_eq!(eval!("Millis(5)"), MetricValue::Int(5_000_000));
880        assert_eq!(eval!("Seconds(2)"), MetricValue::Int(2_000_000_000));
881        assert_eq!(eval!("Minutes(2)"), MetricValue::Int(2_000_000_000 * 60));
882        assert_eq!(eval!("Hours(2)"), MetricValue::Int(2_000_000_000 * 60 * 60));
883        assert_eq!(eval!("Days(2)"), MetricValue::Int(2_000_000_000 * 60 * 60 * 24));
884        // Floating point values work.
885        assert_eq!(eval!("Seconds(0.5)"), MetricValue::Int(500_000_000));
886        // Negative values are fine.
887        assert_eq!(eval!("Seconds(-0.5)"), MetricValue::Int(-500_000_000));
888        // Non-numeric or bad arg combinations return Problem.
889        assert_problem!(eval!("Hours()"), "SyntaxError: Time conversion needs 1 numeric argument");
890        assert_problem!(
891            eval!("Hours(2, 3)"),
892            "SyntaxError: Time conversion needs 1 numeric argument"
893        );
894        assert_problem!(
895            eval!("Hours('a')"),
896            "ValueError: Time conversion needs 1 numeric argument, not String(a)"
897        );
898        assert_problem!(eval!("1.0/0.0"), "ValueError: Division by zero");
899        assert_problem!(eval!("Hours(1.0/0.0)"), "ValueError: Division by zero");
900        Ok(())
901    }
902
903    #[fuchsia::test]
904    fn parser_nested_function() -> Result<(), Error> {
905        assert_eq!(eval!("Max(2, Min(4-1, 5))"), MetricValue::Int(3));
906        assert_eq!(eval!("And(Max(1, 2+3)>1, Or(1>2, 2>1))"), MetricValue::Bool(true));
907        Ok(())
908    }
909
910    #[fuchsia::test]
911    fn singleton_vecs_promote() -> Result<(), Error> {
912        assert_eq!(eval!("Max([1+1], Min([4]-1, 4+[1]))"), MetricValue::Int(3));
913        assert_eq!(eval!("And(Max(1, 2+[3])>1, Or([1]>2, [1>2], 2>[1]))"), MetricValue::Bool(true));
914        Ok(())
915    }
916
917    fn b(b: bool) -> MetricValue {
918        MetricValue::Bool(b)
919    }
920
921    fn i(i: i64) -> MetricValue {
922        MetricValue::Int(i)
923    }
924
925    fn v(v: &[MetricValue]) -> MetricValue {
926        MetricValue::Vector(v.to_vec())
927    }
928
929    #[fuchsia::test]
930    fn functional_programming() -> Result<(), Error> {
931        assert_eq!(eval!("Apply(Fn([], 5), [])"), i(5));
932        assert_eq!(eval!("Apply(Fn([a], a+5), [2])"), i(7));
933        assert_eq!(eval!("Apply(Fn([a, b], a*b+5), [2, 3])"), i(11));
934        assert_eq!(eval!("Map(Fn([a], a*2), [1,2,3])"), v(&[i(2), i(4), i(6)]));
935        assert_eq!(
936            eval!("Map(Fn([a, b], [a, b]), [1, 2, 3], [4, 5, 6])"),
937            v(&[v(&[i(1), i(4)]), v(&[i(2), i(5)]), v(&[i(3), i(6)])])
938        );
939        assert_eq!(eval!("Map(Fn([a, b], [a, b]), [1, 2, 3], [4])"), v(&[v(&[i(1), i(4)])]));
940        assert_eq!(
941            eval!("Map(Fn([a, b], [a, b]), [1, 2, 3], 4)"),
942            v(&[v(&[i(1), i(4)]), v(&[i(2), i(4)]), v(&[i(3), i(4)])])
943        );
944        assert_eq!(eval!("Fold(Fn([a, b], a + b), [1, 2, 3])"), i(6));
945        assert_eq!(eval!("Fold(Fn([a, b], a + 1), ['a', 'b', 'c', 'd'], 0)"), i(4));
946        assert_eq!(eval!("Filter(Fn([a], a > 5), [2, 4, 6, 8])"), v(&[i(6), i(8)]));
947        assert_eq!(eval!("Count([1, 'a', 3, 2])"), i(4));
948
949        assert_eq!(eval!("All(Fn([a], a > 5), [2, 4, 6, 8])"), b(false));
950        assert_eq!(eval!("All(Fn([a], a > 1), [2, 4, 6, 8])"), b(true));
951        assert_eq!(eval!("Any(Fn([a], a > 5), [2, 4, 6, 8])"), b(true));
952        assert_eq!(eval!("Any(Fn([a], a > 8), [2, 4, 6, 8])"), b(false));
953        assert_eq!(eval!("Any(Fn([a], a > 8), [])"), b(false));
954        assert_eq!(eval!("All(Fn([a], a > 8), [])"), b(true));
955
956        // Wrong arguments order
957        assert_problem!(
958            eval!("All([2, 4, 6, 8], Fn([a], a > 8))"),
959            "SyntaxError: All needs a function in its first argument"
960        );
961        // Wrong number of arguments: 0
962        assert_problem!(eval!("All()"), "SyntaxError: All needs a function in its first argument");
963        // Wrong number of arguments: 1
964        assert_problem!(
965            eval!("All(Fn([a], a > 8))"),
966            "SyntaxError: All needs two arguments (function, vector)"
967        );
968        // Wrong number of arguments: 3
969        assert_problem!(
970            eval!("All(Fn([a], a > 8), [], [])"),
971            "SyntaxError: All needs two arguments (function, vector)"
972        );
973        // Wrong argument type
974        assert_problem!(
975            eval!("All(Fn([a], a > 8), 'b')"),
976            "SyntaxError: The second argument passed to All must be a vector"
977        );
978        // Lambda not returning a boolean
979        assert_problem!(eval!("Any(Fn([a], a), [2, 4])"), "ValueError: Int(2) is not boolean");
980        Ok(())
981    }
982
983    #[fuchsia::test]
984    fn booleans() {
985        assert_eq!(eval!("True()"), MetricValue::Bool(true));
986        assert_eq!(eval!("False()"), MetricValue::Bool(false));
987        assert_problem!(
988            eval!("True(1)"),
989            "SyntaxError: Boolean functions don't take any arguments"
990        );
991    }
992
993    #[fuchsia::test]
994    fn test_now() -> Result<(), Error> {
995        let now_expression = parse_expression("Now()", /* namespace= */ "")?;
996        let values = HashMap::new();
997        let fetcher = Fetcher::TrialData(TrialDataFetcher::new(&values));
998        let files = HashMap::new();
999        let state = MetricState::new(&files, fetcher, Some(2000));
1000
1001        let time = state.evaluate_expression(&now_expression);
1002        let no_time =
1003            state.evaluate_expression(&parse_expression("Now(5)", /* namespace= */ "")?);
1004        assert_eq!(time, i(2000));
1005        assert_problem!(no_time, "SyntaxError: Now() requires no operands.");
1006        Ok(())
1007    }
1008
1009    #[fuchsia::test]
1010    fn test_option() {
1011        // Should "Every value was missing" be a ValueError or a Missing?
1012        assert_problem!(eval!("Option()"), "Missing: Every value was missing");
1013        // Now() will return Problem::Missing.
1014        assert_problem!(
1015            eval!("Option(Now(), Now(), Now(), Now())"),
1016            "Missing: Every value was missing"
1017        );
1018        assert_eq!(eval!("Option(5)"), i(5));
1019        assert_eq!(eval!("Option(5, Now())"), i(5));
1020        assert_eq!(eval!("Option(Now(), 5, Now())"), i(5));
1021        assert_eq!(eval!("Option(Now(), Now(), Now(), Now(), 5)"), i(5));
1022        assert_eq!(eval!("Option(Now(), Now(), [], Now())"), MetricValue::Vector(vec![]));
1023        assert_eq!(eval!("Option(Now(), Now(), [], Now(), [5])"), MetricValue::Vector(vec![i(5)]));
1024        assert_eq!(eval!("Option(Now(), Now(), 5, Now(), [5])"), i(5));
1025        assert_eq!(eval!("Option(Now(), Now(), [5], Now(), 5)"), MetricValue::Vector(vec![i(5)]));
1026    }
1027
1028    #[fuchsia::test]
1029    fn test_abs() {
1030        assert_eq!(eval!("Abs(-10)"), i(10));
1031        assert_eq!(eval!("Abs(10)"), i(10));
1032        assert_eq!(eval!("Abs(-1.23)"), MetricValue::Float(1.23));
1033        assert_eq!(eval!("Abs(1.23)"), MetricValue::Float(1.23));
1034
1035        assert_problem!(eval!("Abs(1,2)"), "SyntaxError: Abs requires exactly one operand.");
1036        assert_problem!(eval!("Abs(1,2,3)"), "SyntaxError: Abs requires exactly one operand.");
1037        assert_problem!(eval!("Abs()"), "SyntaxError: Abs requires exactly one operand.");
1038        assert_problem!(
1039            eval!(r#"Abs("quoted-string")"#),
1040            "Missing: String(quoted-string) not numeric"
1041        );
1042        assert_problem!(eval!("Abs(True())"), "Missing: Bool(true) not numeric");
1043    }
1044}
fuchsia_triage/metrics/parse.rs

fuchsia_triage/metrics/
parse.rs
