provenant/license_detection/expression/
mod.rs

1// SPDX-FileCopyrightText: Provenant contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! License expression parsing and manipulation.
5//!
6//! This module provides a parser for ScanCode license expressions, supporting:
7//! - ScanCode license keys (e.g., `mit`, `gpl-2.0-plus`, `apache-2.0`)
8//! - SPDX operators: `AND`, `OR`, `WITH` (case-insensitive)
9//! - Parenthetical grouping
10//! - The `LicenseRef-scancode-*` format for non-SPDX licenses
11//!
12//! The parser converts license expression strings into an AST (Abstract Syntax Tree)
13//! and provides functions for validation and simplification.
14
15mod parse;
16mod simplify;
17
18pub use parse::parse_expression;
19pub use simplify::{
20    combine_expressions_and, combine_expressions_and_preserving_structure, combine_expressions_or,
21    combine_expressions_or_preserving_structure, expression_to_string, licensing_contains,
22    simplify_expression, simplify_expression_preserving_structure,
23};
24
25/// Error type for license expression parsing.
26// Variant names share the "Expression"/"Token" domain vocabulary; renaming for the lint would reduce clarity.
27#[derive(Debug, Clone, PartialEq, thiserror::Error)]
28#[allow(clippy::enum_variant_names)]
29pub enum ParseError {
30    /// Empty expression
31    #[error("Empty license expression")]
32    EmptyExpression,
33
34    /// Unexpected token at position
35    #[error("Unexpected token '{token}' at position {position}")]
36    UnexpectedToken { token: String, position: usize },
37
38    /// Mismatched parentheses
39    #[error("Mismatched parentheses")]
40    MismatchedParentheses,
41
42    /// Generic parse error with message
43    #[error("Parse error: {0}")]
44    ParseError(String),
45}
46
47/// A parsed license expression represented as an AST.
48#[derive(Debug, Clone, PartialEq)]
49pub enum LicenseExpression {
50    /// A single license key
51    License(String),
52
53    /// A LicenseRef-scancode-* reference
54    LicenseRef(String),
55
56    /// AND operation: left AND right
57    And {
58        left: Box<LicenseExpression>,
59        right: Box<LicenseExpression>,
60    },
61
62    /// OR operation: left OR right
63    Or {
64        left: Box<LicenseExpression>,
65        right: Box<LicenseExpression>,
66    },
67
68    /// WITH operation: left WITH right (exception)
69    With {
70        left: Box<LicenseExpression>,
71        right: Box<LicenseExpression>,
72    },
73}
74
75impl LicenseExpression {
76    /// Extract all license keys from the expression.
77    pub fn license_keys(&self) -> Vec<String> {
78        let mut keys = Vec::new();
79        self.collect_keys(&mut keys);
80        keys.sort();
81        keys.dedup();
82        keys
83    }
84
85    fn collect_keys(&self, keys: &mut Vec<String>) {
86        match self {
87            Self::License(key) => keys.push(key.clone()),
88            Self::LicenseRef(key) => keys.push(key.clone()),
89            Self::And { left, right } | Self::Or { left, right } | Self::With { left, right } => {
90                left.collect_keys(keys);
91                right.collect_keys(keys);
92            }
93        }
94    }
95
96    /// Create an AND expression combining multiple expressions.
97    pub fn and(expressions: Vec<LicenseExpression>) -> Option<LicenseExpression> {
98        if expressions.is_empty() {
99            None
100        } else {
101            Some(build_balanced_boolean_expression(
102                &expressions,
103                |left, right| LicenseExpression::And { left, right },
104            ))
105        }
106    }
107
108    /// Create an OR expression combining multiple expressions.
109    pub fn or(expressions: Vec<LicenseExpression>) -> Option<LicenseExpression> {
110        if expressions.is_empty() {
111            None
112        } else {
113            Some(build_balanced_boolean_expression(
114                &expressions,
115                |left, right| LicenseExpression::Or { left, right },
116            ))
117        }
118    }
119}
120
121fn build_balanced_boolean_expression(
122    expressions: &[LicenseExpression],
123    combine: fn(Box<LicenseExpression>, Box<LicenseExpression>) -> LicenseExpression,
124) -> LicenseExpression {
125    debug_assert!(
126        !expressions.is_empty(),
127        "build_balanced_boolean_expression called with empty list"
128    );
129    match expressions.len() {
130        1 => expressions[0].clone(),
131        _ => {
132            let midpoint = expressions.len() / 2;
133            let left = build_balanced_boolean_expression(&expressions[..midpoint], combine);
134            let right = build_balanced_boolean_expression(&expressions[midpoint..], combine);
135            combine(Box::new(left), Box::new(right))
136        }
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143    use std::collections::HashSet;
144
145    fn expression_depth(expr: &LicenseExpression) -> usize {
146        match expr {
147            LicenseExpression::License(_) | LicenseExpression::LicenseRef(_) => 1,
148            LicenseExpression::And { left, right }
149            | LicenseExpression::Or { left, right }
150            | LicenseExpression::With { left, right } => {
151                1 + expression_depth(left).max(expression_depth(right))
152            }
153        }
154    }
155
156    #[test]
157    fn test_and_helper_empty() {
158        let result = LicenseExpression::and(vec![]);
159        assert!(result.is_none());
160    }
161
162    #[test]
163    fn test_and_helper_single() {
164        let expr = LicenseExpression::License("mit".to_string());
165        let result = LicenseExpression::and(vec![expr.clone()]).unwrap();
166        assert_eq!(result, expr);
167    }
168
169    #[test]
170    fn test_and_helper_multiple() {
171        let exprs = vec![
172            LicenseExpression::License("mit".to_string()),
173            LicenseExpression::License("apache-2.0".to_string()),
174        ];
175        let result = LicenseExpression::and(exprs).unwrap();
176        assert!(matches!(result, LicenseExpression::And { .. }));
177    }
178
179    #[test]
180    fn test_or_helper_empty() {
181        let result = LicenseExpression::or(vec![]);
182        assert!(result.is_none());
183    }
184
185    #[test]
186    fn test_or_helper_single() {
187        let expr = LicenseExpression::License("mit".to_string());
188        let result = LicenseExpression::or(vec![expr.clone()]).unwrap();
189        assert_eq!(result, expr);
190    }
191
192    #[test]
193    fn test_or_helper_multiple() {
194        let exprs = vec![
195            LicenseExpression::License("mit".to_string()),
196            LicenseExpression::License("apache-2.0".to_string()),
197        ];
198        let result = LicenseExpression::or(exprs).unwrap();
199        assert!(matches!(result, LicenseExpression::Or { .. }));
200    }
201
202    #[test]
203    fn test_and_helper_balances_large_expression_depth() {
204        let exprs: Vec<_> = (0..1024)
205            .map(|idx| LicenseExpression::License(format!("license-{idx}")))
206            .collect();
207
208        let result = LicenseExpression::and(exprs).unwrap();
209
210        assert!(expression_depth(&result) <= 12);
211    }
212
213    #[test]
214    fn test_or_helper_balances_large_expression_depth() {
215        let exprs: Vec<_> = (0..1024)
216            .map(|idx| LicenseExpression::License(format!("license-{idx}")))
217            .collect();
218
219        let result = LicenseExpression::or(exprs).unwrap();
220
221        assert!(expression_depth(&result) <= 12);
222    }
223
224    #[test]
225    fn test_validate_expression_valid() {
226        let expr = parse_expression("MIT AND Apache-2.0").unwrap();
227        let mut known = HashSet::new();
228        known.insert("mit".to_string());
229        known.insert("apache-2.0".to_string());
230
231        let unknown: Vec<_> = expr
232            .license_keys()
233            .into_iter()
234            .filter(|key| !known.contains(key))
235            .collect();
236        assert!(unknown.is_empty());
237    }
238
239    #[test]
240    fn test_validate_expression_unknown_keys() {
241        let expr = parse_expression("MIT AND UnknownKey").unwrap();
242        let mut known = HashSet::new();
243        known.insert("mit".to_string());
244
245        let unknown: Vec<_> = expr
246            .license_keys()
247            .into_iter()
248            .filter(|key| !known.contains(key))
249            .collect();
250        assert_eq!(unknown, vec!["unknownkey".to_string()]);
251    }
252
253    #[test]
254    fn test_validate_expression_empty_known_keys() {
255        let expr = parse_expression("MIT AND Apache-2.0").unwrap();
256        let known: HashSet<String> = HashSet::new();
257
258        let unknown: Vec<_> = expr
259            .license_keys()
260            .into_iter()
261            .filter(|key| !known.contains(key))
262            .collect();
263        assert_eq!(unknown.len(), 2);
264    }
265}
provenant/license_detection/expression/mod.rs

provenant/license_detection/expression/
mod.rs
