| // SPDX-FileCopyrightText: 2022 HH Partners |
| // |
| // SPDX-License-Identifier: MIT |
| |
| //! Parsing logic for SPDX Expressions. |
| //! |
| //! The code is heavily inspired by |
| //! <https://github.com/Geal/nom/blob/294ffb3d9e0ade2c3b7ddfff52484b6d643dcce1/tests/arithmetic_ast.rs> |
| //! which is licensed under the MIT License. The source project includes the following copyright |
| //! statement: Copyright (c) 2014-2019 Geoffroy Couprie. |
| |
| use nom::{ |
| branch::alt, |
| bytes::complete::{tag, tag_no_case, take_while1}, |
| character::{ |
| complete::{multispace0, multispace1}, |
| streaming::char, |
| }, |
| combinator::{complete, map, opt, recognize}, |
| multi::many0, |
| sequence::{delimited, pair, preceded, separated_pair}, |
| AsChar, IResult, |
| }; |
| |
| use crate::expression_variant::{ExpressionVariant, SimpleExpression, WithExpression}; |
| |
| #[derive(Debug)] |
| enum Operator { |
| And, |
| Or, |
| } |
| |
| fn parentheses(i: &str) -> IResult<&str, ExpressionVariant> { |
| delimited( |
| multispace0, |
| delimited( |
| tag("("), |
| map(or_expression, |e| ExpressionVariant::Parens(Box::new(e))), |
| tag(")"), |
| ), |
| multispace0, |
| )(i) |
| } |
| |
| fn terminal_expression(i: &str) -> IResult<&str, ExpressionVariant> { |
| alt(( |
| delimited(multispace0, with_expression, multispace0), |
| map( |
| delimited(multispace0, simple_expression, multispace0), |
| ExpressionVariant::Simple, |
| ), |
| parentheses, |
| ))(i) |
| } |
| |
| fn with_expression(i: &str) -> IResult<&str, ExpressionVariant> { |
| map( |
| separated_pair( |
| simple_expression, |
| delimited(multispace1, tag_no_case("WITH"), multispace1), |
| idstring, |
| ), |
| |(lic, exc)| ExpressionVariant::With(WithExpression::new(lic, exc.to_string())), |
| )(i) |
| } |
| |
| fn fold_expressions( |
| initial: ExpressionVariant, |
| remainder: Vec<(Operator, ExpressionVariant)>, |
| ) -> ExpressionVariant { |
| remainder.into_iter().fold(initial, |acc, pair| { |
| let (oper, expr) = pair; |
| match oper { |
| Operator::And => ExpressionVariant::And(Box::new(acc), Box::new(expr)), |
| Operator::Or => ExpressionVariant::Or(Box::new(acc), Box::new(expr)), |
| } |
| }) |
| } |
| |
| fn and_expression(i: &str) -> IResult<&str, ExpressionVariant> { |
| let (i, initial) = terminal_expression(i)?; |
| let (i, remainder) = many0(|i| { |
| let (i, and) = preceded(tag_no_case("AND"), terminal_expression)(i)?; |
| Ok((i, (Operator::And, and))) |
| })(i)?; |
| |
| Ok((i, fold_expressions(initial, remainder))) |
| } |
| |
| fn or_expression(i: &str) -> IResult<&str, ExpressionVariant> { |
| let (i, initial) = and_expression(i)?; |
| let (i, remainder) = many0(|i| { |
| let (i, or) = preceded(tag_no_case("OR"), and_expression)(i)?; |
| Ok((i, (Operator::Or, or))) |
| })(i)?; |
| |
| Ok((i, fold_expressions(initial, remainder))) |
| } |
| |
| pub fn parse_expression(i: &str) -> IResult<&str, ExpressionVariant> { |
| or_expression(i) |
| } |
| |
| fn idstring(i: &str) -> IResult<&str, &str> { |
| take_while1(|c: char| c.is_alphanum() || c == '-' || c == '.')(i) |
| } |
| |
| fn license_idstring(i: &str) -> IResult<&str, &str> { |
| recognize(pair(idstring, opt(complete(char('+')))))(i) |
| } |
| |
| fn document_ref(i: &str) -> IResult<&str, &str> { |
| delimited(tag("DocumentRef-"), idstring, char(':'))(i) |
| } |
| |
| fn license_ref(i: &str) -> IResult<&str, (Option<&str>, &str)> { |
| separated_pair(opt(document_ref), tag("LicenseRef-"), idstring)(i) |
| } |
| |
| pub fn simple_expression(i: &str) -> IResult<&str, SimpleExpression> { |
| alt(( |
| map(license_ref, |(document_ref, id)| { |
| let document_ref = document_ref.map(std::string::ToString::to_string); |
| SimpleExpression::new(id.to_string(), document_ref, true) |
| }), |
| map(license_idstring, |id| { |
| SimpleExpression::new(id.to_string(), None, false) |
| }), |
| ))(i) |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| //! A lot of the test cases for parsing are copied from |
| //! <https://github.com/oss-review-toolkit/ort/blob/6eb18b6d36f59c6d7ec221bad1cf5d4cd6acfc8b/utils/spdx/src/test/kotlin/SpdxExpressionParserTest.kt> |
| //! which is licensed under the Apache License, Version 2.0 and includes the following copyright |
| //! statement: |
| //! Copyright (C) 2017-2019 HERE Europe B.V. |
| |
| use super::*; |
| |
| use pretty_assertions::assert_eq; |
| |
| #[test] |
| fn parse_a_license_id_correctly() { |
| let parsed = ExpressionVariant::parse("spdx.license-id").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Simple(SimpleExpression::new( |
| "spdx.license-id".to_string(), |
| None, |
| false |
| )) |
| ); |
| } |
| |
| #[test] |
| fn parse_a_license_id_starting_with_a_digit_correctly() { |
| let parsed = ExpressionVariant::parse("0license").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Simple(SimpleExpression::new("0license".to_string(), None, false)) |
| ); |
| } |
| |
| #[test] |
| fn parse_a_license_id_with_any_later_version_correctly() { |
| let parsed = ExpressionVariant::parse("license+").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Simple(SimpleExpression::new("license+".to_string(), None, false)) |
| ); |
| } |
| |
| #[test] |
| fn parse_a_document_ref_correctly() { |
| let parsed = ExpressionVariant::parse("DocumentRef-document:LicenseRef-license").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Simple(SimpleExpression::new( |
| "license".to_string(), |
| Some("document".to_string()), |
| true |
| )) |
| ); |
| } |
| |
| #[test] |
| fn parse_a_license_ref_correctly() { |
| let parsed = ExpressionVariant::parse("LicenseRef-license").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Simple(SimpleExpression::new("license".to_string(), None, true)) |
| ); |
| } |
| |
| #[test] |
| fn parse_a_with_expression_correctly() { |
| let parsed = ExpressionVariant::parse("license WITH exception").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::With(WithExpression::new( |
| SimpleExpression::new("license".to_string(), None, false), |
| "exception".to_string() |
| )) |
| ); |
| } |
| |
| #[test] |
| fn parse_a_complex_expression_correctly() { |
| let parsed = ExpressionVariant::parse( |
| "license1+ and ((license2 with exception1) OR license3+ AND license4 WITH exception2)", |
| ) |
| .unwrap(); |
| |
| assert_eq!( |
| parsed, |
| ExpressionVariant::And( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license1+".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::Parens(Box::new(ExpressionVariant::Or( |
| Box::new(ExpressionVariant::Parens(Box::new( |
| ExpressionVariant::With(WithExpression::new( |
| SimpleExpression::new("license2".to_string(), None, false), |
| "exception1".to_string() |
| )) |
| ))), |
| Box::new(ExpressionVariant::And( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license3+".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::With(WithExpression::new( |
| SimpleExpression::new("license4".to_string(), None, false), |
| "exception2".to_string() |
| ))) |
| )), |
| )))) |
| ) |
| ); |
| } |
| |
| #[test] |
| fn bind_plus_stronger_than_with() { |
| let parsed = ExpressionVariant::parse("license+ WITH exception").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::With(WithExpression::new( |
| SimpleExpression::new("license+".to_string(), None, false), |
| "exception".to_string() |
| )) |
| ); |
| } |
| |
| #[test] |
| fn bind_with_stronger_than_and() { |
| let parsed = ExpressionVariant::parse("license1 AND license2 WITH exception").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::And( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license1".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::With(WithExpression::new( |
| SimpleExpression::new("license2".to_string(), None, false), |
| "exception".to_string() |
| ))) |
| ) |
| ); |
| } |
| |
| #[test] |
| fn bind_and_stronger_than_or() { |
| let parsed = ExpressionVariant::parse("license1 OR license2 AND license3").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Or( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license1".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::And( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license2".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license3".to_string(), |
| None, |
| false |
| ))) |
| )) |
| ) |
| ); |
| } |
| |
| #[test] |
| fn bind_the_and_operator_left_associative() { |
| let parsed = ExpressionVariant::parse("license1 AND license2 AND license3").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::And( |
| Box::new(ExpressionVariant::And( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license1".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license2".to_string(), |
| None, |
| false |
| ))) |
| )), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license3".to_string(), |
| None, |
| false |
| ))), |
| ) |
| ); |
| } |
| |
| #[test] |
| fn bind_the_or_operator_left_associative() { |
| let parsed = ExpressionVariant::parse("license1 OR license2 OR license3").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::Or( |
| Box::new(ExpressionVariant::Or( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license1".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license2".to_string(), |
| None, |
| false |
| ))) |
| )), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license3".to_string(), |
| None, |
| false |
| ))), |
| ) |
| ); |
| } |
| |
| #[test] |
| fn respect_parentheses_for_binding_strength_of_operators() { |
| let parsed = ExpressionVariant::parse("(license1 OR license2) AND license3").unwrap(); |
| assert_eq!( |
| parsed, |
| ExpressionVariant::And( |
| Box::new(ExpressionVariant::Parens(Box::new(ExpressionVariant::Or( |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license1".to_string(), |
| None, |
| false |
| ))), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license2".to_string(), |
| None, |
| false |
| ))) |
| )))), |
| Box::new(ExpressionVariant::Simple(SimpleExpression::new( |
| "license3".to_string(), |
| None, |
| false |
| ))), |
| ) |
| ); |
| } |
| |
| #[test] |
| fn fail_if_plus_is_used_in_an_exception_expression() { |
| let parsed = ExpressionVariant::parse("license WITH exception+"); |
| assert!(parsed.is_err()); |
| } |
| |
| #[test] |
| fn fail_if_a_compound_expressions_is_used_before_with() { |
| let parsed = ExpressionVariant::parse("(license1 AND license2) WITH exception"); |
| assert!(parsed.is_err()); |
| } |
| |
| #[test] |
| fn fail_on_an_invalid_symbol() { |
| let parsed = ExpressionVariant::parse("/"); |
| assert!(parsed.is_err()); |
| } |
| |
| #[test] |
| fn fail_on_a_syntax_error() { |
| let parsed = ExpressionVariant::parse("(("); |
| assert!(parsed.is_err()); |
| } |
| } |