vendor/der/src/asn1/set_of.rs

   1 //! ASN.1 `SET OF` support.
   2 //!
   3 //! # Ordering Notes
   4 //!
   5 //! Some DER serializer implementations fail to properly sort elements of a
   6 //! `SET OF`. This is technically non-canonical, but occurs frequently
   7 //! enough that most DER decoders tolerate it. Unfortunately because
   8 //! of that, we must also follow suit.
   9 //!
  10 //! However, all types in this module sort elements of a set at decode-time,
  11 //! ensuring they'll be in the proper order if reserialized.
  12
  13 use crate::{
  14     arrayvec, ord::iter_cmp, ArrayVec, Decode, DecodeValue, DerOrd, Encode, EncodeValue, Error,
  15     ErrorKind, FixedTag, Header, Length, Reader, Result, Tag, ValueOrd, Writer,
  16 };
  17 use core::cmp::Ordering;
  18
  19 #[cfg(feature = "alloc")]
  20 use {alloc::vec::Vec, core::slice};
  21
  22 /// ASN.1 `SET OF` backed by an array.
  23 ///
  24 /// This type implements an append-only `SET OF` type which is stack-based
  25 /// and does not depend on `alloc` support.
  26 // TODO(tarcieri): use `ArrayVec` when/if it's merged into `core`
  27 // See: https://github.com/rust-lang/rfcs/pull/2990
  28 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
  29 pub struct SetOf<T, const N: usize>
  30 where
  31     T: DerOrd,
  32 {
  33     inner: ArrayVec<T, N>,
  34 }
  35
  36 impl<T, const N: usize> SetOf<T, N>
  37 where
  38     T: DerOrd,
  39 {
  40     /// Create a new [`SetOf`].
  41     pub fn new() -> Self {
  42         Self {
  43             inner: ArrayVec::default(),
  44         }
  45     }
  46
  47     /// Add an element to this [`SetOf`].
  48     ///
  49     /// Items MUST be added in lexicographical order according to the
  50     /// [`DerOrd`] impl on `T`.
  51     pub fn add(&mut self, new_elem: T) -> Result<()> {
  52         // Ensure set elements are lexicographically ordered
  53         if let Some(last_elem) = self.inner.last() {
  54             if new_elem.der_cmp(last_elem)? != Ordering::Greater {
  55                 return Err(ErrorKind::SetOrdering.into());
  56             }
  57         }
  58
  59         self.inner.add(new_elem)
  60     }
  61
  62     /// Get the nth element from this [`SetOf`].
  63     pub fn get(&self, index: usize) -> Option<&T> {
  64         self.inner.get(index)
  65     }
  66
  67     /// Iterate over the elements of this [`SetOf`].
  68     pub fn iter(&self) -> SetOfIter<'_, T> {
  69         SetOfIter {
  70             inner: self.inner.iter(),
  71         }
  72     }
  73
  74     /// Is this [`SetOf`] empty?
  75     pub fn is_empty(&self) -> bool {
  76         self.inner.is_empty()
  77     }
  78
  79     /// Number of elements in this [`SetOf`].
  80     pub fn len(&self) -> usize {
  81         self.inner.len()
  82     }
  83 }
  84
  85 impl<T, const N: usize> Default for SetOf<T, N>
  86 where
  87     T: DerOrd,
  88 {
  89     fn default() -> Self {
  90         Self::new()
  91     }
  92 }
  93
  94 impl<'a, T, const N: usize> DecodeValue<'a> for SetOf<T, N>
  95 where
  96     T: Decode<'a> + DerOrd,
  97 {
  98     fn decode_value<R: Reader<'a>>(reader: &mut R, header: Header) -> Result<Self> {
  99         reader.read_nested(header.length, |reader| {
 100             let mut result = Self::new();
 101
 102             while !reader.is_finished() {
 103                 result.inner.add(T::decode(reader)?)?;
 104             }
 105
 106             der_sort(result.inner.as_mut())?;
 107             validate(result.inner.as_ref())?;
 108             Ok(result)
 109         })
 110     }
 111 }
 112
 113 impl<'a, T, const N: usize> EncodeValue for SetOf<T, N>
 114 where
 115     T: 'a + Decode<'a> + Encode + DerOrd,
 116 {
 117     fn value_len(&self) -> Result<Length> {
 118         self.iter()
 119             .fold(Ok(Length::ZERO), |len, elem| len + elem.encoded_len()?)
 120     }
 121
 122     fn encode_value(&self, writer: &mut dyn Writer) -> Result<()> {
 123         for elem in self.iter() {
 124             elem.encode(writer)?;
 125         }
 126
 127         Ok(())
 128     }
 129 }
 130
 131 impl<'a, T, const N: usize> FixedTag for SetOf<T, N>
 132 where
 133     T: Decode<'a> + DerOrd,
 134 {
 135     const TAG: Tag = Tag::Set;
 136 }
 137
 138 impl<T, const N: usize> TryFrom<[T; N]> for SetOf<T, N>
 139 where
 140     T: DerOrd,
 141 {
 142     type Error = Error;
 143
 144     fn try_from(mut arr: [T; N]) -> Result<SetOf<T, N>> {
 145         der_sort(&mut arr)?;
 146
 147         let mut result = SetOf::new();
 148
 149         for elem in arr {
 150             result.add(elem)?;
 151         }
 152
 153         Ok(result)
 154     }
 155 }
 156
 157 impl<T, const N: usize> ValueOrd for SetOf<T, N>
 158 where
 159     T: DerOrd,
 160 {
 161     fn value_cmp(&self, other: &Self) -> Result<Ordering> {
 162         iter_cmp(self.iter(), other.iter())
 163     }
 164 }
 165
 166 /// Iterator over the elements of an [`SetOf`].
 167 #[derive(Clone, Debug)]
 168 pub struct SetOfIter<'a, T> {
 169     /// Inner iterator.
 170     inner: arrayvec::Iter<'a, T>,
 171 }
 172
 173 impl<'a, T> Iterator for SetOfIter<'a, T> {
 174     type Item = &'a T;
 175
 176     fn next(&mut self) -> Option<&'a T> {
 177         self.inner.next()
 178     }
 179 }
 180
 181 impl<'a, T> ExactSizeIterator for SetOfIter<'a, T> {}
 182
 183 /// ASN.1 `SET OF` backed by a [`Vec`].
 184 ///
 185 /// This type implements an append-only `SET OF` type which is heap-backed
 186 /// and depends on `alloc` support.
 187 #[cfg(feature = "alloc")]
 188 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 189 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
 190 pub struct SetOfVec<T>
 191 where
 192     T: DerOrd,
 193 {
 194     inner: Vec<T>,
 195 }
 196
 197 #[cfg(feature = "alloc")]
 198 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 199 impl<T: DerOrd> Default for SetOfVec<T> {
 200     fn default() -> Self {
 201         Self {
 202             inner: Default::default(),
 203         }
 204     }
 205 }
 206
 207 #[cfg(feature = "alloc")]
 208 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 209 impl<T> SetOfVec<T>
 210 where
 211     T: DerOrd,
 212 {
 213     /// Create a new [`SetOfVec`].
 214     pub fn new() -> Self {
 215         Self {
 216             inner: Vec::default(),
 217         }
 218     }
 219
 220     /// Add an element to this [`SetOfVec`].
 221     ///
 222     /// Items MUST be added in lexicographical order according to the
 223     /// [`DerOrd`] impl on `T`.
 224     pub fn add(&mut self, new_elem: T) -> Result<()> {
 225         // Ensure set elements are lexicographically ordered
 226         if let Some(last_elem) = self.inner.last() {
 227             if new_elem.der_cmp(last_elem)? != Ordering::Greater {
 228                 return Err(ErrorKind::SetOrdering.into());
 229             }
 230         }
 231
 232         self.inner.push(new_elem);
 233         Ok(())
 234     }
 235
 236     /// Borrow the elements of this [`SetOfVec`] as a slice.
 237     pub fn as_slice(&self) -> &[T] {
 238         self.inner.as_slice()
 239     }
 240
 241     /// Get the nth element from this [`SetOfVec`].
 242     pub fn get(&self, index: usize) -> Option<&T> {
 243         self.inner.get(index)
 244     }
 245
 246     /// Convert this [`SetOfVec`] into the inner [`Vec`].
 247     pub fn into_vec(self) -> Vec<T> {
 248         self.inner
 249     }
 250
 251     /// Iterate over the elements of this [`SetOfVec`].
 252     pub fn iter(&self) -> slice::Iter<'_, T> {
 253         self.inner.iter()
 254     }
 255
 256     /// Is this [`SetOfVec`] empty?
 257     pub fn is_empty(&self) -> bool {
 258         self.inner.is_empty()
 259     }
 260
 261     /// Number of elements in this [`SetOfVec`].
 262     pub fn len(&self) -> usize {
 263         self.inner.len()
 264     }
 265 }
 266
 267 #[cfg(feature = "alloc")]
 268 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 269 impl<T> AsRef<[T]> for SetOfVec<T>
 270 where
 271     T: DerOrd,
 272 {
 273     fn as_ref(&self) -> &[T] {
 274         self.as_slice()
 275     }
 276 }
 277
 278 #[cfg(feature = "alloc")]
 279 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 280 impl<'a, T> DecodeValue<'a> for SetOfVec<T>
 281 where
 282     T: Decode<'a> + DerOrd,
 283 {
 284     fn decode_value<R: Reader<'a>>(reader: &mut R, header: Header) -> Result<Self> {
 285         reader.read_nested(header.length, |reader| {
 286             let mut inner = Vec::new();
 287
 288             while !reader.is_finished() {
 289                 inner.push(T::decode(reader)?);
 290             }
 291
 292             der_sort(inner.as_mut())?;
 293             validate(inner.as_ref())?;
 294             Ok(Self { inner })
 295         })
 296     }
 297 }
 298
 299 #[cfg(feature = "alloc")]
 300 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 301 impl<'a, T> EncodeValue for SetOfVec<T>
 302 where
 303     T: 'a + Decode<'a> + Encode + DerOrd,
 304 {
 305     fn value_len(&self) -> Result<Length> {
 306         self.iter()
 307             .fold(Ok(Length::ZERO), |len, elem| len + elem.encoded_len()?)
 308     }
 309
 310     fn encode_value(&self, writer: &mut dyn Writer) -> Result<()> {
 311         for elem in self.iter() {
 312             elem.encode(writer)?;
 313         }
 314
 315         Ok(())
 316     }
 317 }
 318
 319 #[cfg(feature = "alloc")]
 320 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 321 impl<T> FixedTag for SetOfVec<T>
 322 where
 323     T: DerOrd,
 324 {
 325     const TAG: Tag = Tag::Set;
 326 }
 327
 328 #[cfg(feature = "alloc")]
 329 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 330 impl<T> From<SetOfVec<T>> for Vec<T>
 331 where
 332     T: DerOrd,
 333 {
 334     fn from(set: SetOfVec<T>) -> Vec<T> {
 335         set.into_vec()
 336     }
 337 }
 338
 339 #[cfg(feature = "alloc")]
 340 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 341 impl<T> TryFrom<Vec<T>> for SetOfVec<T>
 342 where
 343     T: DerOrd,
 344 {
 345     type Error = Error;
 346
 347     fn try_from(mut vec: Vec<T>) -> Result<SetOfVec<T>> {
 348         // TODO(tarcieri): use `[T]::sort_by` here?
 349         der_sort(vec.as_mut_slice())?;
 350         Ok(SetOfVec { inner: vec })
 351     }
 352 }
 353
 354 #[cfg(feature = "alloc")]
 355 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 356 impl<T, const N: usize> TryFrom<[T; N]> for SetOfVec<T>
 357 where
 358     T: DerOrd,
 359 {
 360     type Error = Error;
 361
 362     fn try_from(arr: [T; N]) -> Result<SetOfVec<T>> {
 363         Vec::from(arr).try_into()
 364     }
 365 }
 366
 367 #[cfg(feature = "alloc")]
 368 #[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
 369 impl<T> ValueOrd for SetOfVec<T>
 370 where
 371     T: DerOrd,
 372 {
 373     fn value_cmp(&self, other: &Self) -> Result<Ordering> {
 374         iter_cmp(self.iter(), other.iter())
 375     }
 376 }
 377
 378 /// Sort a mut slice according to its [`DerOrd`], returning any errors which
 379 /// might occur during the comparison.
 380 ///
 381 /// The algorithm is insertion sort, which should perform well when the input
 382 /// is mostly sorted to begin with.
 383 ///
 384 /// This function is used rather than Rust's built-in `[T]::sort_by` in order
 385 /// to support heapless `no_std` targets as well as to enable bubbling up
 386 /// sorting errors.
 387 #[allow(clippy::integer_arithmetic)]
 388 fn der_sort<T: DerOrd>(slice: &mut [T]) -> Result<()> {
 389     for i in 0..slice.len() {
 390         let mut j = i;
 391
 392         while j > 0 && slice[j - 1].der_cmp(&slice[j])? == Ordering::Greater {
 393             slice.swap(j - 1, j);
 394             j -= 1;
 395         }
 396     }
 397
 398     Ok(())
 399 }
 400
 401 /// Validate the elements of a `SET OF`, ensuring that they are all in order
 402 /// and that there are no duplicates.
 403 fn validate<T: DerOrd>(slice: &[T]) -> Result<()> {
 404     if let Some(len) = slice.len().checked_sub(1) {
 405         for i in 0..len {
 406             let j = i.checked_add(1).ok_or(ErrorKind::Overflow)?;
 407
 408             match slice.get(i..=j) {
 409                 Some([a, b]) => {
 410                     if a.der_cmp(b)? != Ordering::Less {
 411                         return Err(ErrorKind::SetOrdering.into());
 412                     }
 413                 }
 414                 _ => return Err(Tag::Set.value_error()),
 415             }
 416         }
 417     }
 418
 419     Ok(())
 420 }
 421
 422 #[cfg(all(test, feature = "alloc"))]
 423 mod tests {
 424     use super::{SetOf, SetOfVec};
 425     use alloc::vec::Vec;
 426
 427     #[test]
 428     fn setof_tryfrom_array() {
 429         let arr = [3u16, 2, 1, 65535, 0];
 430         let set = SetOf::try_from(arr).unwrap();
 431         assert_eq!(
 432             set.iter().cloned().collect::<Vec<u16>>(),
 433             &[0, 1, 2, 3, 65535]
 434         );
 435     }
 436
 437     #[test]
 438     fn setofvec_tryfrom_array() {
 439         let arr = [3u16, 2, 1, 65535, 0];
 440         let set = SetOfVec::try_from(arr).unwrap();
 441         assert_eq!(set.as_ref(), &[0, 1, 2, 3, 65535]);
 442     }
 443
 444     #[cfg(feature = "alloc")]
 445     #[test]
 446     fn setofvec_tryfrom_vec() {
 447         let vec = vec![3u16, 2, 1, 65535, 0];
 448         let set = SetOfVec::try_from(vec).unwrap();
 449         assert_eq!(set.as_ref(), &[0, 1, 2, 3, 65535]);
 450     }
 451 }