use core::fmt;
use std::collections::BTreeSet;
use crate::error::Error;
#[path = "spdx_list.rs"]
mod spdx_list;
pub(crate) use spdx_list::{DEPRECATED_LICENSES, KNOWN_EXCEPTIONS, KNOWN_LICENSES};
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expression {
Simple { id: LicenseId },
With {
license: Box<Self>,
exception: LicenseId,
},
And { left: Box<Self>, right: Box<Self> },
Or { left: Box<Self>, right: Box<Self> },
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LicenseId {
pub id: String,
}
impl Expression {
#[must_use]
pub fn identifiers(&self) -> BTreeSet<String> {
let mut out = BTreeSet::new();
self.collect_identifiers(&mut out);
out
}
fn collect_identifiers(&self, out: &mut BTreeSet<String>) {
match self {
Self::Simple { id } => {
out.insert(id.id.clone());
}
Self::With { license, exception } => {
license.collect_identifiers(out);
out.insert(exception.id.clone());
}
Self::And { left, right } | Self::Or { left, right } => {
left.collect_identifiers(out);
right.collect_identifiers(out);
}
}
}
}
impl fmt::Display for Expression {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Simple { id } => write!(f, "{}", id.id),
Self::With { license, exception } => {
write!(f, "{license} WITH {}", exception.id)
}
Self::And { left, right } => write!(f, "{left} AND {right}"),
Self::Or { left, right } => write!(f, "{left} OR {right}"),
}
}
}
const WHITESPACE: &[char] = &[' ', '\t', '\n', '\r'];
const SPECIAL: &[char] = &['(', ')'];
#[allow(clippy::missing_errors_doc)]
pub fn parse(input: &str) -> Result<Expression, Error> {
let tokens = tokenize(input);
let mut pos = 0;
let expr = parse_or(&tokens, &mut pos)?;
if pos < tokens.len() {
return Err(Error::Spdx(format!(
"unexpected token '{}' after expression",
tokens[pos]
)));
}
Ok(expr)
}
#[allow(clippy::missing_errors_doc)]
pub fn validate(input: &str) -> Result<(), Error> {
parse(input)?;
Ok(())
}
#[must_use]
pub fn is_known_license(id: &str) -> bool {
KNOWN_LICENSES.contains(&id)
}
#[must_use]
pub fn is_known_exception(id: &str) -> bool {
KNOWN_EXCEPTIONS.contains(&id)
}
#[must_use]
pub const fn known_licenses() -> &'static [&'static str] {
KNOWN_LICENSES
}
#[must_use]
pub const fn known_exceptions() -> &'static [&'static str] {
KNOWN_EXCEPTIONS
}
#[must_use]
pub const fn deprecated_licenses() -> &'static [&'static str] {
DEPRECATED_LICENSES
}
fn tokenize(input: &str) -> Vec<String> {
let mut tokens = Vec::new();
let mut chars = input.chars().peekable();
while let Some(&ch) = chars.peek() {
if ch == '(' || ch == ')' {
tokens.push(ch.to_string());
chars.next();
} else if WHITESPACE.contains(&ch) {
chars.next();
} else {
let mut token = String::new();
while let Some(&ch) = chars.peek() {
if SPECIAL.contains(&ch) || WHITESPACE.contains(&ch) {
break;
}
token.push(ch);
chars.next();
}
if !token.is_empty() {
tokens.push(token);
}
}
}
tokens
}
fn parse_or(tokens: &[String], pos: &mut usize) -> Result<Expression, Error> {
let mut left = parse_and(tokens, pos)?;
while *pos < tokens.len() && tokens[*pos].eq_ignore_ascii_case("OR") {
*pos += 1;
let right = parse_and(tokens, pos)?;
left = Expression::Or {
left: Box::new(left),
right: Box::new(right),
};
}
Ok(left)
}
fn parse_and(tokens: &[String], pos: &mut usize) -> Result<Expression, Error> {
let mut left = parse_with(tokens, pos)?;
while *pos < tokens.len() && tokens[*pos].eq_ignore_ascii_case("AND") {
*pos += 1;
let right = parse_with(tokens, pos)?;
left = Expression::And {
left: Box::new(left),
right: Box::new(right),
};
}
Ok(left)
}
fn parse_with(tokens: &[String], pos: &mut usize) -> Result<Expression, Error> {
let mut expr = parse_primary(tokens, pos)?;
if *pos < tokens.len() && tokens[*pos].eq_ignore_ascii_case("WITH") {
*pos += 1;
let exception = parse_identifier(tokens, pos)?;
expr = Expression::With {
license: Box::new(expr),
exception: LicenseId { id: exception },
};
}
Ok(expr)
}
fn parse_primary(tokens: &[String], pos: &mut usize) -> Result<Expression, Error> {
if *pos >= tokens.len() {
return Err(Error::Spdx("unexpected end of expression".into()));
}
if tokens[*pos] == "(" {
*pos += 1;
let expr = parse_or(tokens, pos)?;
if *pos >= tokens.len() || tokens[*pos] != ")" {
return Err(Error::Spdx("missing closing parenthesis".into()));
}
*pos += 1;
return Ok(expr);
}
let id = parse_identifier(tokens, pos)?;
Ok(Expression::Simple {
id: LicenseId { id },
})
}
fn parse_identifier(tokens: &[String], pos: &mut usize) -> Result<String, Error> {
if *pos >= tokens.len() {
return Err(Error::Spdx(
"expected identifier, found end of expression".into(),
));
}
let token = &tokens[*pos];
if SPECIAL.contains(&token.chars().next().unwrap_or('\0')) {
return Err(Error::Spdx(format!("expected identifier, found '{token}'")));
}
let upper = token.to_uppercase();
if upper == "AND" || upper == "OR" || upper == "WITH" {
return Err(Error::Spdx(format!("expected identifier, found '{token}'")));
}
*pos += 1;
Ok(token.clone())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_bundled_lists_are_exposed_sorted_and_agree_with_the_predicates() {
let licenses = known_licenses();
let exceptions = known_exceptions();
let deprecated = deprecated_licenses();
assert!(licenses.len() > 700, "got {}", licenses.len());
assert!(exceptions.len() > 30, "got {}", exceptions.len());
assert!(!deprecated.is_empty());
assert!(licenses.windows(2).all(|w| w[0] <= w[1]));
assert!(exceptions.windows(2).all(|w| w[0] <= w[1]));
assert!(is_known_license(licenses[0]));
assert!(is_known_exception(exceptions[0]));
assert!(licenses.contains(&"MIT"));
assert!(deprecated.contains(&"GPL-3.0"));
}
#[test]
fn identifiers_collects_every_licence_an_expression_references() {
let ids = |e: &str| {
parse(e)
.unwrap()
.identifiers()
.into_iter()
.collect::<Vec<_>>()
};
assert_eq!(ids("MIT"), ["MIT"]);
assert_eq!(ids("MIT OR Apache-2.0"), ["Apache-2.0", "MIT"]);
assert_eq!(ids("MIT AND Apache-2.0"), ["Apache-2.0", "MIT"]);
assert_eq!(
ids("(MIT OR Apache-2.0) AND ISC"),
["Apache-2.0", "ISC", "MIT"]
);
assert_eq!(
ids("MIT OR MIT"),
["MIT"],
"a licence named twice is still one licence"
);
}
#[test]
fn identifiers_includes_the_exception_of_a_with_expression() {
let ids = parse("GPL-3.0-only WITH Autoconf-exception-3.0")
.unwrap()
.identifiers()
.into_iter()
.collect::<Vec<_>>();
assert_eq!(ids, ["Autoconf-exception-3.0", "GPL-3.0-only"]);
}
#[test]
fn display_round_trips_every_expression_shape() {
for expr in ["MIT", "MIT OR Apache-2.0", "MIT AND Apache-2.0"] {
assert_eq!(parse(expr).unwrap().to_string(), expr);
}
assert_eq!(
parse("GPL-3.0-only WITH Autoconf-exception-3.0")
.unwrap()
.to_string(),
"GPL-3.0-only WITH Autoconf-exception-3.0"
);
}
#[test]
fn an_expression_ending_in_an_operator_is_rejected() {
let err = parse("MIT AND").unwrap_err().to_string();
assert!(
err.contains("end of expression"),
"a dangling operator should say what was expected, got: {err}"
);
}
#[test]
fn a_trailing_with_has_no_exception_to_attach() {
let err = parse("GPL-3.0-only WITH").unwrap_err().to_string();
assert!(
err.contains("expected identifier, found end of expression"),
"got: {err}"
);
}
#[test]
fn a_parenthesis_where_an_identifier_belongs_is_rejected() {
let err = parse("MIT AND )").unwrap_err().to_string();
assert!(err.contains("expected identifier"), "got: {err}");
}
#[test]
fn parse_simple_mit() {
let expr = parse("MIT").unwrap();
assert_eq!(
expr,
Expression::Simple {
id: LicenseId { id: "MIT".into() }
}
);
}
#[test]
fn parse_simple_apache() {
let expr = parse("Apache-2.0").unwrap();
assert_eq!(
expr,
Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}
);
}
#[test]
fn parse_simple_license_ref() {
let expr = parse("LicenseRef-custom").unwrap();
assert_eq!(
expr,
Expression::Simple {
id: LicenseId {
id: "LicenseRef-custom".into()
}
}
);
}
#[test]
fn parse_or_expression() {
let expr = parse("MIT OR Apache-2.0").unwrap();
assert_eq!(
expr,
Expression::Or {
left: Box::new(Expression::Simple {
id: LicenseId { id: "MIT".into() }
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}),
}
);
}
#[test]
fn parse_and_expression() {
let expr = parse("MIT AND Apache-2.0").unwrap();
assert_eq!(
expr,
Expression::And {
left: Box::new(Expression::Simple {
id: LicenseId { id: "MIT".into() }
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}),
}
);
}
#[test]
fn parse_with_expression() {
let expr = parse("Apache-2.0 WITH LLVM-exception").unwrap();
assert_eq!(
expr,
Expression::With {
license: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}),
exception: LicenseId {
id: "LLVM-exception".into()
},
}
);
}
#[test]
fn parse_parenthesized_expression() {
let expr = parse("(MIT OR Apache-2.0) AND BSD-3-Clause").unwrap();
assert_eq!(
expr,
Expression::And {
left: Box::new(Expression::Or {
left: Box::new(Expression::Simple {
id: LicenseId { id: "MIT".into() }
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}),
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "BSD-3-Clause".into()
}
}),
}
);
}
#[test]
fn parse_chained_or() {
let expr = parse("MIT OR Apache-2.0 OR BSD-3-Clause").unwrap();
assert_eq!(
expr,
Expression::Or {
left: Box::new(Expression::Or {
left: Box::new(Expression::Simple {
id: LicenseId { id: "MIT".into() }
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}),
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "BSD-3-Clause".into()
}
}),
}
);
}
#[test]
fn parse_or_has_lower_precedence_than_and() {
let expr = parse("MIT OR Apache-2.0 AND BSD-3-Clause").unwrap();
assert_eq!(
expr,
Expression::Or {
left: Box::new(Expression::Simple {
id: LicenseId { id: "MIT".into() }
}),
right: Box::new(Expression::And {
left: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into()
}
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "BSD-3-Clause".into()
}
}),
}),
}
);
}
#[test]
fn validate_valid_expression() {
assert!(validate("MIT").is_ok());
assert!(validate("MIT OR Apache-2.0").is_ok());
assert!(validate("(MIT OR Apache-2.0) AND BSD-3-Clause").is_ok());
}
#[test]
fn validate_empty_string_fails() {
assert!(validate("").is_err());
}
#[test]
fn validate_operator_only_fails() {
assert!(validate("OR").is_err());
assert!(validate("AND").is_err());
}
#[test]
fn validate_unclosed_paren_fails() {
assert!(validate("(MIT OR Apache-2.0").is_err());
}
#[test]
fn validate_extra_tokens_fails() {
assert!(validate("MIT OR").is_err());
}
#[test]
fn validate_trailing_paren_fails() {
assert!(validate("MIT)").is_err());
}
#[test]
fn known_license_mit() {
assert!(is_known_license("MIT"));
}
#[test]
fn known_license_apache() {
assert!(is_known_license("Apache-2.0"));
}
#[test]
fn known_license_gpl() {
assert!(is_known_license("GPL-3.0-only"));
}
#[test]
fn known_license_cc0() {
assert!(is_known_license("CC0-1.0"));
}
#[test]
fn unknown_license_is_not_known() {
assert!(!is_known_license("NONEXISTENT-LICENSE"));
}
#[test]
fn license_ref_is_not_in_known_list() {
assert!(!is_known_license("LicenseRef-custom"));
}
#[test]
fn known_exception_llvm() {
assert!(is_known_exception("LLVM-exception"));
}
#[test]
fn known_exception_classpath() {
assert!(is_known_exception("Classpath-exception-2.0"));
}
#[test]
fn unknown_exception_is_not_known() {
assert!(!is_known_exception("MadeUp-exception"));
}
#[test]
fn display_simple() {
let expr = Expression::Simple {
id: LicenseId { id: "MIT".into() },
};
assert_eq!(expr.to_string(), "MIT");
}
#[test]
fn display_or() {
let expr = Expression::Or {
left: Box::new(Expression::Simple {
id: LicenseId { id: "MIT".into() },
}),
right: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into(),
},
}),
};
assert_eq!(expr.to_string(), "MIT OR Apache-2.0");
}
#[test]
fn display_with() {
let expr = Expression::With {
license: Box::new(Expression::Simple {
id: LicenseId {
id: "Apache-2.0".into(),
},
}),
exception: LicenseId {
id: "LLVM-exception".into(),
},
};
assert_eq!(expr.to_string(), "Apache-2.0 WITH LLVM-exception");
}
}