fuchsia_triage/metrics/
parse.rs

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::{Error, format_err};
9use nom::Err::{self, Incomplete};
10use nom::branch::alt;
11use nom::bytes::complete::{is_not, tag, take_while, take_while_m_n};
12use nom::character::complete::{char, none_of, one_of};
13use nom::combinator::{all_consuming, map, opt, peek, recognize};
14use nom::multi::{fold_many0, many0, separated_list0};
15use nom::sequence::{delimited, pair, preceded, separated_pair, terminated};
16use nom::{AsChar, IResult, Input, Parser};
17use nom_language::error::{VerboseError, convert_error};
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
335    spaced(alt((paren_expr, function_expression, vector_expression, number, string, name))).parse(i)
336}
337
338// Scans for primitive expressions separated by * and /.
339fn expression_muldiv(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
340    let (i, init) = expression_primitive(i)?;
341    let mut init = Some(init);
342    fold_many0(
343        pair(
344            alt((
345                math!("*", Mul),
346                math!("//?", IntDivChecked),
347                math!("/?", FloatDivChecked),
348                math!("//", IntDiv),
349                math!("/", FloatDiv),
350            )),
351            expression_primitive,
352        ),
353        move || init.take().unwrap(),
354        |acc, (op, expr)| ExpressionTree::Function(op, vec![acc, expr]),
355    )
356    .parse(i)
357}
358
359// Scans for muldiv expressions (which may be a single primitive expression)
360// separated by + and -. Remember unary + and - will be recognized by number().
361fn expression_addsub(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
362    let (i, init) = expression_muldiv(i)?;
363    let mut init = Some(init);
364    fold_many0(
365        pair(alt((math!("+", Add), math!("-", Sub))), expression_muldiv),
366        move || init.take().unwrap(),
367        |acc, (op, expr)| ExpressionTree::Function(op, vec![acc, expr]),
368    )
369    .parse(i)
370}
371
372// Top-level expression. Should match the entire expression string, and also
373// can be used inside parentheses.
374fn expression_top(i: ParsingContext<'_>) -> ParsingResult<'_, ExpressionTree> {
375    // Note: alt() is not BNF - it's sequential. It's important to put the longer strings first.
376    // If a shorter substring succeeds where it shouldn't, the alt() may not get another chance.
377    let comparison = alt((
378        math!(">=", GreaterEq),
379        math!("<=", LessEq),
380        function!("==", Equals),
381        function!("!=", NotEq),
382        math!(">", Greater),
383        math!("<", Less),
384    ));
385    alt((
386        map((expression_addsub, comparison, expression_addsub), move |(left, op, right)| {
387            ExpressionTree::Function(op, vec![left, right])
388        }),
389        expression_addsub,
390    ))
391    .parse(i)
392}
393
394// Parses a given string into either an Error or an Expression ready
395// to be evaluated.
396pub(crate) fn parse_expression(i: &str, namespace: &str) -> Result<ExpressionTree, Error> {
397    let ctx = ParsingContext::new(i, namespace);
398    let mut match_whole = all_consuming(terminated(expression_top, whitespace));
399    match match_whole.parse(ctx) {
400        Err(Err::Error(e)) | Err(Err::Failure(e)) => Err(format_err!(
401            "Expression Error: \n{}",
402            convert_error(
403                ctx.into_inner(),
404                VerboseError {
405                    errors: e.errors.into_iter().map(|e| (e.0.into_inner(), e.1)).collect()
406                }
407            )
408        )),
409        Ok((_, result)) => Ok(result),
410        Err(Incomplete(what)) => Err(format_err!("Why did I get an incomplete? {:?}", what)),
411    }
412}
413
414#[cfg(test)]
415mod test {
416    use super::*;
417    use crate::assert_problem;
418    use crate::metrics::{Fetcher, MetricState, TrialDataFetcher};
419    use std::collections::HashMap;
420
421    // Res, simplify_fn, and get_parse are necessary because IResult can't be compared and can't
422    //   easily be matched/decomposed. Res can be compared and debug-formatted.
423    // Call get_parse(parse_function, string) to get either Ok(remainder_str, result)
424    //   or Err(descriptive_string).
425    #[derive(PartialEq, Debug)]
426    enum Res<'a, T> {
427        Ok(&'a str, T),
428        Err(String),
429    }
430
431    fn simplify_fn<'a, T: std::fmt::Debug>(i: &str, r: ParsingResult<'a, T>) -> Res<'a, T> {
432        match r {
433            Err(Err::Error(e)) => Res::Err(format!(
434                "Error: \n{:?}",
435                convert_error(
436                    i,
437                    VerboseError {
438                        errors: e.errors.into_iter().map(|e| (e.0.into_inner(), e.1)).collect()
439                    }
440                )
441            )),
442            Err(Err::Failure(e)) => Res::Err(format!(
443                "Failure: \n{:?}",
444                convert_error(
445                    i,
446                    VerboseError {
447                        errors: e.errors.into_iter().map(|e| (e.0.into_inner(), e.1)).collect()
448                    }
449                )
450            )),
451            Err(Incomplete(e)) => Res::Err(format!("Incomplete: {e:?}")),
452            Ok((unused, result)) => Res::Ok(unused.into_inner(), result),
453        }
454    }
455
456    macro_rules! get_parse {
457        ($fn:expr, $string:expr) => {
458            simplify_fn($string, $fn(ParsingContext::new($string, /*namespace= */ "")))
459        };
460    }
461
462    impl<T> Res<'_, T> {
463        fn is_err(&self) -> bool {
464            match self {
465                Res::Err(_) => true,
466                Res::Ok(_, _) => false,
467            }
468        }
469    }
470
471    #[fuchsia::test]
472    fn parse_vectors() {
473        fn v(i: i64) -> ExpressionTree {
474            ExpressionTree::Value(MetricValue::Int(i))
475        }
476
477        assert_eq!(
478            get_parse!(expression_primitive, "[1,2]"),
479            Res::Ok("", ExpressionTree::Vector(vec![v(1), v(2)]))
480        );
481        assert_eq!(
482            get_parse!(expression_primitive, " [ 1 , 2 ] "),
483            Res::Ok(" ", ExpressionTree::Vector(vec![v(1), v(2)]))
484        );
485        assert_eq!(
486            get_parse!(expression_primitive, "[1]"),
487            Res::Ok("", ExpressionTree::Vector(vec![v(1)]))
488        );
489        assert_eq!(
490            get_parse!(expression_primitive, "[]"),
491            Res::Ok("", ExpressionTree::Vector(Vec::new()))
492        );
493        let first = ExpressionTree::Function(Function::Math(MathFunction::Add), vec![v(1), v(2)]);
494        let second = ExpressionTree::Function(Function::Math(MathFunction::Sub), vec![v(2), v(1)]);
495        assert_eq!(
496            get_parse!(expression_primitive, "[1+2, 2-1]"),
497            Res::Ok("", ExpressionTree::Vector(vec![first, second]))
498        );
499        // Verify that we reject un-closed braces.
500        assert!(get_parse!(expression_primitive, "[1+2, 2-1").is_err());
501        // Verify that it's just the unclosed brace that was the problem in the previous line.
502        // (The parser will only look for the first complete primitive expression.)
503        assert_eq!(get_parse!(expression_primitive, "1+2, 2-1"), Res::Ok("+2, 2-1", v(1)));
504        assert!(get_parse!(expression_primitive, "]").is_err());
505        assert!(get_parse!(expression_primitive, "[").is_err());
506    }
507
508    #[fuchsia::test]
509    fn parse_numbers() {
510        // No leading extraneous characters allowed in number, not even whitespace.
511        assert!(get_parse!(number, "f5").is_err());
512        assert!(get_parse!(number, " 1").is_err());
513        // Empty string should fail
514        assert!(get_parse!(number, "").is_err());
515        // Trailing characters will be returned as unused remainder
516        assert_eq!(
517            get_parse!(number, "1 "),
518            Res::Ok(" ", ExpressionTree::Value(MetricValue::Int(1)))
519        );
520        assert_eq!(
521            get_parse!(number, "1a"),
522            Res::Ok("a", ExpressionTree::Value(MetricValue::Int(1)))
523        );
524        // If it parses as int, it's an int.
525        assert_eq!(
526            get_parse!(number, "234"),
527            Res::Ok("", ExpressionTree::Value(MetricValue::Int(234)))
528        );
529        // Otherwise it's a float.
530        assert_eq!(
531            get_parse!(number, "234.0"),
532            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0)))
533        );
534        assert_eq!(
535            get_parse!(number, "234.0e-5"),
536            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0e-5)))
537        );
538        // Leading -, +, 0 are all OK for int
539        assert_eq!(
540            get_parse!(number, "0"),
541            Res::Ok("", ExpressionTree::Value(MetricValue::Int(0)))
542        );
543        assert_eq!(
544            get_parse!(number, "00234"),
545            Res::Ok("", ExpressionTree::Value(MetricValue::Int(234)))
546        );
547        assert_eq!(
548            get_parse!(number, "+234"),
549            Res::Ok("", ExpressionTree::Value(MetricValue::Int(234)))
550        );
551        assert_eq!(
552            get_parse!(number, "-234"),
553            Res::Ok("", ExpressionTree::Value(MetricValue::Int(-234)))
554        );
555        // Leading +, -, 0 are OK for float.
556        assert_eq!(
557            get_parse!(number, "0.0"),
558            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.0)))
559        );
560        assert_eq!(
561            get_parse!(number, "00234.0"),
562            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0)))
563        );
564        assert_eq!(
565            get_parse!(number, "+234.0"),
566            Res::Ok("", ExpressionTree::Value(MetricValue::Float(234.0)))
567        );
568        assert_eq!(
569            get_parse!(number, "-234.0"),
570            Res::Ok("", ExpressionTree::Value(MetricValue::Float(-234.0)))
571        );
572        // Leading and trailing periods parse as valid float.
573        assert_eq!(
574            get_parse!(number, ".1"),
575            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.1)))
576        );
577        assert_eq!(
578            get_parse!(number, "1."),
579            Res::Ok("", ExpressionTree::Value(MetricValue::Float(1.0)))
580        );
581        assert_eq!(
582            get_parse!(number, "1.a"),
583            Res::Ok("a", ExpressionTree::Value(MetricValue::Float(1.0)))
584        );
585
586        assert_eq!(
587            get_parse!(number, ".12_34___"),
588            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.1234)))
589        );
590        assert_eq!(
591            get_parse!(number, ".2e__2_"),
592            Res::Ok("", ExpressionTree::Value(MetricValue::Float(20.0)))
593        );
594        assert_eq!(
595            get_parse!(number, "1_234_567___8E-__1_0__"),
596            Res::Ok("", ExpressionTree::Value(MetricValue::Float(0.0012345678)))
597        );
598        assert_eq!(
599            get_parse!(number, "1__234__.12E-3__"),
600            Res::Ok("", ExpressionTree::Value(MetricValue::Float(1.23412)))
601        );
602        assert_eq!(
603            get_parse!(number, "1_2__3__4__"),
604            Res::Ok("", ExpressionTree::Value(MetricValue::Int(1234)))
605        );
606
607        // number cannot begin with '_'
608        assert!(get_parse!(number, "_100").is_err());
609    }
610
611    #[fuchsia::test]
612    fn parse_string() {
613        // needs to have quotes
614        assert!(get_parse!(string, "OK").is_err());
615
616        // needs to close its quotes
617        assert!(get_parse!(string, "'OK").is_err());
618
619        assert_eq!(
620            get_parse!(string, "'OK'"),
621            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
622        );
623        assert_eq!(
624            get_parse!(string, "'OK'a"),
625            Res::Ok("a", ExpressionTree::Value(MetricValue::String("OK".to_string())))
626        );
627        assert_eq!(
628            get_parse!(string, r#""OK""#),
629            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
630        );
631        assert_eq!(
632            get_parse!(string, "\'OK\'"),
633            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
634        );
635        assert_eq!(
636            get_parse!(string, "\"OK\""),
637            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK".to_string())))
638        );
639
640        // can handle nested qoutes
641        assert_eq!(
642            get_parse!(string, r#"'a"b'"#),
643            Res::Ok("", ExpressionTree::Value(MetricValue::String(r#"a"b"#.to_string())))
644        );
645        assert_eq!(
646            get_parse!(string, r#""a'b""#),
647            Res::Ok("", ExpressionTree::Value(MetricValue::String("a'b".to_string())))
648        );
649
650        // can handle whitespace
651        assert_eq!(
652            get_parse!(string, "'OK OK'"),
653            Res::Ok("", ExpressionTree::Value(MetricValue::String("OK OK".to_string())))
654        );
655
656        // can parse strings that are numbers
657        assert_eq!(
658            get_parse!(string, "'123'"),
659            Res::Ok("", ExpressionTree::Value(MetricValue::String("123".to_string())))
660        );
661    }
662
663    macro_rules! variable_expression {
664        ($name:expr) => {
665            ExpressionTree::Variable(VariableName::new($name.to_owned()))
666        };
667    }
668
669    #[fuchsia::test]
670    fn parse_names_no_namespace() {
671        assert_eq!(get_parse!(name_no_namespace, "abc"), Res::Ok("", variable_expression!("abc")));
672        assert_eq!(get_parse!(name_no_namespace, "bc."), Res::Ok(".", variable_expression!("bc")));
673        // Names can contain digits and _ but can't start with digits
674        assert_eq!(
675            get_parse!(name_no_namespace, "bc42."),
676            Res::Ok(".", variable_expression!("bc42"))
677        );
678        assert!(get_parse!(name_no_namespace, "42bc.").is_err());
679        assert_eq!(
680            get_parse!(name_no_namespace, "_bc42_"),
681            Res::Ok("", variable_expression!("_bc42_"))
682        );
683        assert_eq!(
684            get_parse!(name_no_namespace, "_bc42_::abc"),
685            Res::Ok("::abc", variable_expression!("_bc42_"))
686        );
687        assert_eq!(
688            get_parse!(name_no_namespace, "_bc42_:abc"),
689            Res::Ok(":abc", variable_expression!("_bc42_"))
690        );
691    }
692
693    #[fuchsia::test]
694    fn parse_names_with_namespace() {
695        assert_eq!(
696            get_parse!(name_with_namespace, "_bc42_::abc"),
697            Res::Ok("", variable_expression!("_bc42_::abc"))
698        );
699        assert_eq!(
700            get_parse!(name_with_namespace, "_bc42_::abc::def"),
701            Res::Ok("::def", variable_expression!("_bc42_::abc"))
702        );
703        assert!(get_parse!(name_with_namespace, "_bc42_:abc::def").is_err());
704    }
705
706    #[fuchsia::test]
707    fn parse_names() {
708        assert_eq!(
709            get_parse!(name, "_bc42_::abc"),
710            Res::Ok("", variable_expression!("_bc42_::abc"))
711        );
712        assert_eq!(
713            get_parse!(name, "_bc42_:abc::def"),
714            Res::Ok(":abc::def", variable_expression!("_bc42_"))
715        );
716        assert_eq!(
717            get_parse!(name, "_bc42_::abc::def"),
718            Res::Ok("::def", variable_expression!("_bc42_::abc"))
719        );
720    }
721
722    macro_rules! eval {
723        ($e:expr) => {
724            MetricState::evaluate_math($e)
725        };
726    }
727
728    #[fuchsia::test]
729    fn parse_number_types() -> Result<(), Error> {
730        assert_eq!(eval!("2"), MetricValue::Int(2));
731        assert_eq!(eval!("2+3"), MetricValue::Int(5));
732        assert_eq!(eval!("2.0+3"), MetricValue::Float(5.0));
733        assert_eq!(eval!("2+3.0"), MetricValue::Float(5.0));
734        assert_eq!(eval!("2.0+2.0"), MetricValue::Float(4.0));
735
736        Ok(())
737    }
738
739    #[fuchsia::test]
740    fn parse_div_operations() -> Result<(), Error> {
741        assert_eq!(eval!("5.0/2"), MetricValue::Float(2.5));
742        assert_eq!(eval!("-5.0/2"), MetricValue::Float(-2.5));
743        assert_eq!(eval!("5.0/2.0"), MetricValue::Float(2.5));
744        assert_eq!(eval!("-5.0/2.0"), MetricValue::Float(-2.5));
745        assert_eq!(eval!("5/2"), MetricValue::Float(2.5));
746        assert_eq!(eval!("-5/2"), MetricValue::Float(-2.5));
747
748        // int division should truncate towards zero
749        assert_eq!(eval!("5.0//2"), MetricValue::Float(2.0));
750        assert_eq!(eval!("-5.0//2"), MetricValue::Float(-2.0));
751        assert_eq!(eval!("5.0//2.0"), MetricValue::Float(2.0));
752        assert_eq!(eval!("-5.0//2.0"), MetricValue::Float(-2.0));
753        assert_eq!(eval!("5//2"), MetricValue::Int(2));
754        assert_eq!(eval!("-5//2"), MetricValue::Int(-2));
755
756        // test truncation happens after division
757        assert_eq!(eval!("5000//5.1"), MetricValue::Float(980.0));
758        Ok(())
759    }
760
761    #[fuchsia::test]
762    fn parse_operator_precedence() -> Result<(), Error> {
763        assert_eq!(eval!("2+3*4"), MetricValue::Int(14));
764        assert_eq!(eval!("2+3*4>14-1*1"), MetricValue::Bool(true));
765        assert_eq!(eval!("3*4+2"), MetricValue::Int(14));
766        assert_eq!(eval!("2-3-4"), MetricValue::Int(-5));
767        assert_eq!(eval!("6//3*4"), MetricValue::Int(8));
768        assert_eq!(eval!("6//?3*4"), MetricValue::Int(8));
769        assert_eq!(eval!("6/3*4"), MetricValue::Float(8.0));
770        assert_eq!(eval!("6/?3*4"), MetricValue::Float(8.0));
771        assert_eq!(eval!("8/4/2"), MetricValue::Float(1.0));
772        assert_eq!(eval!("8/4*2"), MetricValue::Float(4.0));
773        assert_eq!(eval!("2-3-4"), MetricValue::Int(-5));
774        assert_eq!(eval!("(2+3)*4"), MetricValue::Int(20));
775        assert_eq!(eval!("2++4"), MetricValue::Int(6));
776        assert_eq!(eval!("2+-4"), MetricValue::Int(-2));
777        assert_eq!(eval!("2-+4"), MetricValue::Int(-2));
778        assert_eq!(eval!("2--4"), MetricValue::Int(6));
779        Ok(())
780    }
781
782    #[fuchsia::test]
783    fn division_by_zero() -> Result<(), Error> {
784        assert_problem!(eval!("4/0"), "ValueError: Division by zero");
785        assert_problem!(eval!("4//0"), "ValueError: Division by zero");
786        assert_problem!(eval!("4/?0"), "Ignore: ValueError: Division by zero");
787        assert_problem!(eval!("4//?0"), "Ignore: ValueError: Division by zero");
788        Ok(())
789    }
790
791    #[fuchsia::test]
792    fn parser_accepts_whitespace() -> Result<(), Error> {
793        assert_eq!(eval!(" 2 + +3 * 4 - 5 // ( -2 + Min ( -2 , 3 ) ) "), MetricValue::Int(15));
794        Ok(())
795    }
796
797    #[fuchsia::test]
798    fn parser_comparisons() -> Result<(), Error> {
799        assert_eq!(
800            format!("{:?}", parse_expression("2>1", /*namespace= */ "")),
801            "Ok(Function(Math(Greater), [Value(Int(2)), Value(Int(1))]))"
802        );
803        assert_eq!(eval!("2>2"), MetricValue::Bool(false));
804        assert_eq!(eval!("2>=2"), MetricValue::Bool(true));
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(true));
808        assert_eq!(eval!("2==2.0"), MetricValue::Bool(true));
809
810        // can do string comparison
811        assert_eq!(eval!("'a'=='a'"), MetricValue::Bool(true));
812        assert_eq!(eval!("'a'!='a'"), MetricValue::Bool(false));
813        assert_eq!(eval!("'a'!='b'"), MetricValue::Bool(true));
814
815        // check variants of string parsing
816        assert_eq!(eval!(r#""a"=="a""#), MetricValue::Bool(true));
817        assert_eq!(eval!(r#"'a'=="a""#), MetricValue::Bool(true));
818
819        // There can be only one.
820        assert!(parse_expression("2==2==2", /* namespace= */ "").is_err());
821        Ok(())
822    }
823
824    #[fuchsia::test]
825    fn parser_boolean_functions_value() -> Result<(), Error> {
826        assert_eq!(
827            format!("{:?}", parse_expression("Not(2>1)", /* namespace= */ "")),
828            "Ok(Function(Not, [Function(Math(Greater), [Value(Int(2)), Value(Int(1))])]))"
829        );
830        assert_eq!(eval!("And(2>1, 2>2)"), MetricValue::Bool(false));
831        assert_eq!(eval!("And(2>2, 2>1)"), MetricValue::Bool(false));
832        assert_eq!(eval!("And(2>2, 2>2)"), MetricValue::Bool(false));
833        assert_eq!(eval!("And(2>1, 2>1)"), MetricValue::Bool(true));
834        assert_eq!(eval!("Or(2>1, 2>2)"), MetricValue::Bool(true));
835        assert_eq!(eval!("Or(2>2, 2>1)"), MetricValue::Bool(true));
836        assert_eq!(eval!("Or(2>2, 2>2)"), MetricValue::Bool(false));
837        assert_eq!(eval!("Or(2>1, 2>1)"), MetricValue::Bool(true));
838        assert_eq!(eval!("Not(2>1)"), MetricValue::Bool(false));
839        assert_eq!(eval!("Not(2>2)"), MetricValue::Bool(true));
840        Ok(())
841    }
842
843    #[fuchsia::test]
844    fn parser_boolean_functions_args() -> Result<(), Error> {
845        assert_eq!(eval!("And(2>1)"), MetricValue::Bool(true));
846        assert_eq!(eval!("And(2>1, 2>1, 2>1)"), MetricValue::Bool(true));
847        assert_problem!(eval!("And()"), "SyntaxError: No operands in boolean expression");
848        assert_eq!(eval!("Or(2>1)"), MetricValue::Bool(true));
849        assert_eq!(eval!("Or(2>1, 2>1, 2>1)"), MetricValue::Bool(true));
850        assert_problem!(eval!("Or()"), "SyntaxError: No operands in boolean expression");
851        assert_problem!(
852            eval!("Not(2>1, 2>1)"),
853            "SyntaxError: Wrong number of arguments (2) for unary bool operator"
854        );
855        assert_problem!(
856            eval!("Not()"),
857            "SyntaxError: Wrong number of arguments (0) for unary bool operator"
858        );
859        Ok(())
860    }
861
862    #[fuchsia::test]
863    fn parser_maxmin_functions() -> Result<(), Error> {
864        assert_eq!(eval!("Max(2, 5, 3, -1)"), MetricValue::Int(5));
865        assert_eq!(eval!("Min(2, 5, 3, -1)"), MetricValue::Int(-1));
866        assert_eq!(eval!("Min(2)"), MetricValue::Int(2));
867        assert_eq!(eval!("Max(2)"), MetricValue::Int(2));
868        assert_problem!(eval!("Max()"), "SyntaxError: No operands in math expression");
869        assert_problem!(eval!("Min()"), "SyntaxError: No operands in math expression");
870        Ok(())
871    }
872
873    #[fuchsia::test]
874    fn parser_time_functions() -> Result<(), Error> {
875        assert_eq!(eval!("Nanos(5)"), MetricValue::Int(5));
876        assert_eq!(eval!("Micros(4)"), MetricValue::Int(4_000));
877        assert_eq!(eval!("Millis(5)"), MetricValue::Int(5_000_000));
878        assert_eq!(eval!("Seconds(2)"), MetricValue::Int(2_000_000_000));
879        assert_eq!(eval!("Minutes(2)"), MetricValue::Int(2_000_000_000 * 60));
880        assert_eq!(eval!("Hours(2)"), MetricValue::Int(2_000_000_000 * 60 * 60));
881        assert_eq!(eval!("Days(2)"), MetricValue::Int(2_000_000_000 * 60 * 60 * 24));
882        // Floating point values work.
883        assert_eq!(eval!("Seconds(0.5)"), MetricValue::Int(500_000_000));
884        // Negative values are fine.
885        assert_eq!(eval!("Seconds(-0.5)"), MetricValue::Int(-500_000_000));
886        // Non-numeric or bad arg combinations return Problem.
887        assert_problem!(eval!("Hours()"), "SyntaxError: Time conversion needs 1 numeric argument");
888        assert_problem!(
889            eval!("Hours(2, 3)"),
890            "SyntaxError: Time conversion needs 1 numeric argument"
891        );
892        assert_problem!(
893            eval!("Hours('a')"),
894            "ValueError: Time conversion needs 1 numeric argument, not String(a)"
895        );
896        assert_problem!(eval!("1.0/0.0"), "ValueError: Division by zero");
897        assert_problem!(eval!("Hours(1.0/0.0)"), "ValueError: Division by zero");
898        Ok(())
899    }
900
901    #[fuchsia::test]
902    fn parser_nested_function() -> Result<(), Error> {
903        assert_eq!(eval!("Max(2, Min(4-1, 5))"), MetricValue::Int(3));
904        assert_eq!(eval!("And(Max(1, 2+3)>1, Or(1>2, 2>1))"), MetricValue::Bool(true));
905        Ok(())
906    }
907
908    #[fuchsia::test]
909    fn singleton_vecs_promote() -> Result<(), Error> {
910        assert_eq!(eval!("Max([1+1], Min([4]-1, 4+[1]))"), MetricValue::Int(3));
911        assert_eq!(eval!("And(Max(1, 2+[3])>1, Or([1]>2, [1>2], 2>[1]))"), MetricValue::Bool(true));
912        Ok(())
913    }
914
915    fn b(b: bool) -> MetricValue {
916        MetricValue::Bool(b)
917    }
918
919    fn i(i: i64) -> MetricValue {
920        MetricValue::Int(i)
921    }
922
923    fn v(v: &[MetricValue]) -> MetricValue {
924        MetricValue::Vector(v.to_vec())
925    }
926
927    #[fuchsia::test]
928    fn functional_programming() -> Result<(), Error> {
929        assert_eq!(eval!("Apply(Fn([], 5), [])"), i(5));
930        assert_eq!(eval!("Apply(Fn([a], a+5), [2])"), i(7));
931        assert_eq!(eval!("Apply(Fn([a, b], a*b+5), [2, 3])"), i(11));
932        assert_eq!(eval!("Map(Fn([a], a*2), [1,2,3])"), v(&[i(2), i(4), i(6)]));
933        assert_eq!(
934            eval!("Map(Fn([a, b], [a, b]), [1, 2, 3], [4, 5, 6])"),
935            v(&[v(&[i(1), i(4)]), v(&[i(2), i(5)]), v(&[i(3), i(6)])])
936        );
937        assert_eq!(eval!("Map(Fn([a, b], [a, b]), [1, 2, 3], [4])"), v(&[v(&[i(1), i(4)])]));
938        assert_eq!(
939            eval!("Map(Fn([a, b], [a, b]), [1, 2, 3], 4)"),
940            v(&[v(&[i(1), i(4)]), v(&[i(2), i(4)]), v(&[i(3), i(4)])])
941        );
942        assert_eq!(eval!("Fold(Fn([a, b], a + b), [1, 2, 3])"), i(6));
943        assert_eq!(eval!("Fold(Fn([a, b], a + 1), ['a', 'b', 'c', 'd'], 0)"), i(4));
944        assert_eq!(eval!("Filter(Fn([a], a > 5), [2, 4, 6, 8])"), v(&[i(6), i(8)]));
945        assert_eq!(eval!("Count([1, 'a', 3, 2])"), i(4));
946
947        assert_eq!(eval!("All(Fn([a], a > 5), [2, 4, 6, 8])"), b(false));
948        assert_eq!(eval!("All(Fn([a], a > 1), [2, 4, 6, 8])"), b(true));
949        assert_eq!(eval!("Any(Fn([a], a > 5), [2, 4, 6, 8])"), b(true));
950        assert_eq!(eval!("Any(Fn([a], a > 8), [2, 4, 6, 8])"), b(false));
951        assert_eq!(eval!("Any(Fn([a], a > 8), [])"), b(false));
952        assert_eq!(eval!("All(Fn([a], a > 8), [])"), b(true));
953
954        // Wrong arguments order
955        assert_problem!(
956            eval!("All([2, 4, 6, 8], Fn([a], a > 8))"),
957            "SyntaxError: All needs a function in its first argument"
958        );
959        // Wrong number of arguments: 0
960        assert_problem!(eval!("All()"), "SyntaxError: All needs a function in its first argument");
961        // Wrong number of arguments: 1
962        assert_problem!(
963            eval!("All(Fn([a], a > 8))"),
964            "SyntaxError: All needs two arguments (function, vector)"
965        );
966        // Wrong number of arguments: 3
967        assert_problem!(
968            eval!("All(Fn([a], a > 8), [], [])"),
969            "SyntaxError: All needs two arguments (function, vector)"
970        );
971        // Wrong argument type
972        assert_problem!(
973            eval!("All(Fn([a], a > 8), 'b')"),
974            "SyntaxError: The second argument passed to All must be a vector"
975        );
976        // Lambda not returning a boolean
977        assert_problem!(eval!("Any(Fn([a], a), [2, 4])"), "ValueError: Int(2) is not boolean");
978        Ok(())
979    }
980
981    #[fuchsia::test]
982    fn booleans() {
983        assert_eq!(eval!("True()"), MetricValue::Bool(true));
984        assert_eq!(eval!("False()"), MetricValue::Bool(false));
985        assert_problem!(
986            eval!("True(1)"),
987            "SyntaxError: Boolean functions don't take any arguments"
988        );
989    }
990
991    #[fuchsia::test]
992    fn test_now() -> Result<(), Error> {
993        let now_expression = parse_expression("Now()", /* namespace= */ "")?;
994        let values = HashMap::new();
995        let fetcher = Fetcher::TrialData(TrialDataFetcher::new(&values));
996        let files = HashMap::new();
997        let state = MetricState::new(&files, fetcher, Some(2000));
998
999        let time = state.evaluate_expression(&now_expression);
1000        let no_time =
1001            state.evaluate_expression(&parse_expression("Now(5)", /* namespace= */ "")?);
1002        assert_eq!(time, i(2000));
1003        assert_problem!(no_time, "SyntaxError: Now() requires no operands.");
1004        Ok(())
1005    }
1006
1007    #[fuchsia::test]
1008    fn test_option() {
1009        // Should "Every value was missing" be a ValueError or a Missing?
1010        assert_problem!(eval!("Option()"), "Missing: Every value was missing");
1011        // Now() will return Problem::Missing.
1012        assert_problem!(
1013            eval!("Option(Now(), Now(), Now(), Now())"),
1014            "Missing: Every value was missing"
1015        );
1016        assert_eq!(eval!("Option(5)"), i(5));
1017        assert_eq!(eval!("Option(5, Now())"), i(5));
1018        assert_eq!(eval!("Option(Now(), 5, Now())"), i(5));
1019        assert_eq!(eval!("Option(Now(), Now(), Now(), Now(), 5)"), i(5));
1020        assert_eq!(eval!("Option(Now(), Now(), [], Now())"), MetricValue::Vector(vec![]));
1021        assert_eq!(eval!("Option(Now(), Now(), [], Now(), [5])"), MetricValue::Vector(vec![i(5)]));
1022        assert_eq!(eval!("Option(Now(), Now(), 5, Now(), [5])"), i(5));
1023        assert_eq!(eval!("Option(Now(), Now(), [5], Now(), 5)"), MetricValue::Vector(vec![i(5)]));
1024    }
1025
1026    #[fuchsia::test]
1027    fn test_abs() {
1028        assert_eq!(eval!("Abs(-10)"), i(10));
1029        assert_eq!(eval!("Abs(10)"), i(10));
1030        assert_eq!(eval!("Abs(-1.23)"), MetricValue::Float(1.23));
1031        assert_eq!(eval!("Abs(1.23)"), MetricValue::Float(1.23));
1032
1033        assert_problem!(eval!("Abs(1,2)"), "SyntaxError: Abs requires exactly one operand.");
1034        assert_problem!(eval!("Abs(1,2,3)"), "SyntaxError: Abs requires exactly one operand.");
1035        assert_problem!(eval!("Abs()"), "SyntaxError: Abs requires exactly one operand.");
1036        assert_problem!(
1037            eval!(r#"Abs("quoted-string")"#),
1038            "Missing: String(quoted-string) not numeric"
1039        );
1040        assert_problem!(eval!("Abs(True())"), "Missing: Bool(true) not numeric");
1041    }
1042}
fuchsia_triage/metrics/parse.rs

fuchsia_triage/metrics/
parse.rs
