1use super::Expression;
2use crate::{LicenseReq, Licensee};
3use std::fmt;
4
5/// Errors that can occur when trying to minimize the requirements for an [`Expression`]
6#[derive(Debug, PartialEq, Eq)]
7pub enum MinimizeError {
8 /// More than `64` unique licensees satisfied a requirement in the [`Expression`]
9 TooManyRequirements(usize),
10 /// The list of licensees did not fully satisfy the requirements in the [`Expression`]
11 RequirementsUnmet,
12}
13
14impl fmt::Display for MinimizeError {
15 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
16 match self {
17 Self::TooManyRequirements(n: &usize) => write!(
18 f,
19 "the license expression required {} licensees which exceeds the limit of 64",
20 n
21 ),
22 Self::RequirementsUnmet => {
23 f.write_str(data:"the expression was not satisfied by the provided list of licensees")
24 }
25 }
26 }
27}
28
29impl std::error::Error for MinimizeError {
30 fn description(&self) -> &str {
31 match self {
32 Self::TooManyRequirements(_) => "too many requirements in license expression",
33 Self::RequirementsUnmet => {
34 "the expression was not satisfied by the provided list of licensees"
35 }
36 }
37 }
38}
39
40impl Expression {
41 /// Given a set of [`Licensee`]s, attempts to find the minimum number that
42 /// satisfy this [`Expression`].
43 ///
44 /// The list of licensees should be given in priority order, eg, if you wish
45 /// to accept the `Apache-2.0` license if it is available, and the `MIT` if
46 /// not, putting `Apache-2.0` before `MIT` will cause the ubiquitous
47 /// `Apache-2.0 OR MIT` expression to minimize to just `Apache-2.0` as only
48 /// 1 of the licenses is required, and `Apache-2.0` has priority.
49 ///
50 /// # Errors
51 ///
52 /// This method will fail if more than 64 unique licensees are satisfied by
53 /// this expression, but such a case is unlikely in a real world scenario.
54 /// The list of licensees must also actually satisfy this expression,
55 /// otherwise it can't be minimized.
56 ///
57 /// # Example
58 ///
59 /// ```
60 /// let expr = spdx::Expression::parse("Apache-2.0 OR MIT").unwrap();
61 ///
62 /// let apache_licensee = spdx::Licensee::parse("Apache-2.0").unwrap();
63 /// assert_eq!(
64 /// expr.minimized_requirements([&apache_licensee, &spdx::Licensee::parse("MIT").unwrap()]).unwrap(),
65 /// vec![apache_licensee.into_req()],
66 /// );
67 /// ```
68 pub fn minimized_requirements<'lic>(
69 &self,
70 accepted: impl IntoIterator<Item = &'lic Licensee>,
71 ) -> Result<Vec<LicenseReq>, MinimizeError> {
72 let found_set = {
73 let mut found_set = smallvec::SmallVec::<[Licensee; 5]>::new();
74
75 for lic in accepted {
76 if !found_set.contains(lic)
77 && self.requirements().any(|ereq| lic.satisfies(&ereq.req))
78 {
79 found_set.push(lic.clone());
80 }
81 }
82
83 if found_set.len() > 64 {
84 return Err(MinimizeError::TooManyRequirements(found_set.len()));
85 }
86
87 // Ensure that the licensees provided actually _can_ be accepted by
88 // this expression
89 if !self.evaluate(|ereq| found_set.iter().any(|lic| lic.satisfies(ereq))) {
90 return Err(MinimizeError::RequirementsUnmet);
91 }
92
93 found_set
94 };
95
96 let set_size = (1 << found_set.len()) as u64;
97
98 for mask in 1..=set_size {
99 let eval_res = self.evaluate(|req| {
100 for (ind, lic) in found_set.iter().enumerate() {
101 if mask & (1 << ind) != 0 && lic.satisfies(req) {
102 return true;
103 }
104 }
105
106 false
107 });
108
109 if eval_res {
110 return Ok(found_set
111 .into_iter()
112 .enumerate()
113 .filter_map(|(ind, lic)| {
114 if mask & (1 << ind) == 0 {
115 None
116 } else {
117 Some(lic.into_req())
118 }
119 })
120 .collect());
121 }
122 }
123
124 // This should be impossible, but would rather not panic
125 Ok(found_set.into_iter().map(Licensee::into_req).collect())
126 }
127}
128