1 use super::Expression; 2 use crate::{LicenseReq, Licensee}; 3 use std::fmt; 4 5 /// Errors that can occur when trying to minimize the requirements for an [`Expression`] 6 #[derive(Debug, PartialEq, Eq)] 7 pub 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 14 impl fmt::Display for MinimizeError { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result15 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 16 match self { 17 Self::TooManyRequirements(n) => 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("the expression was not satisfied by the provided list of licensees") 24 } 25 } 26 } 27 } 28 29 impl std::error::Error for MinimizeError { description(&self) -> &str30 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 40 impl 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 /// ``` minimized_requirements<'lic>( &self, accepted: impl IntoIterator<Item = &'lic Licensee>, ) -> Result<Vec<LicenseReq>, MinimizeError>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