der/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
13use crate::{
14    arrayvec, ord::iter_cmp, ArrayVec, Decode, DecodeValue, DerOrd, Encode, EncodeValue, Error,
15    ErrorKind, FixedTag, Header, Length, Reader, Result, Tag, ValueOrd, Writer,
16};
17use core::cmp::Ordering;
18
19#[cfg(feature = "alloc")]
20use {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)]
29pub struct SetOf<T, const N: usize>
30where
31    T: DerOrd,
32{
33    inner: ArrayVec<T, N>,
34}
35
36impl<T, const N: usize> SetOf<T, N>
37where
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 item to this [`SetOf`].
48    ///
49    /// Items MUST be added in lexicographical order according to the
50    /// [`DerOrd`] impl on `T`.
51    #[deprecated(since = "0.7.6", note = "use `insert` or `insert_ordered` instead")]
52    pub fn add(&mut self, new_elem: T) -> Result<()> {
53        self.insert_ordered(new_elem)
54    }
55
56    /// Insert an item into this [`SetOf`].
57    pub fn insert(&mut self, item: T) -> Result<()> {
58        self.inner.push(item)?;
59        der_sort(self.inner.as_mut())
60    }
61
62    /// Insert an item into this [`SetOf`].
63    ///
64    /// Items MUST be added in lexicographical order according to the
65    /// [`DerOrd`] impl on `T`.
66    pub fn insert_ordered(&mut self, item: T) -> Result<()> {
67        // Ensure set elements are lexicographically ordered
68        if let Some(last) = self.inner.last() {
69            check_der_ordering(last, &item)?;
70        }
71
72        self.inner.push(item)
73    }
74
75    /// Get the nth element from this [`SetOf`].
76    pub fn get(&self, index: usize) -> Option<&T> {
77        self.inner.get(index)
78    }
79
80    /// Iterate over the elements of this [`SetOf`].
81    pub fn iter(&self) -> SetOfIter<'_, T> {
82        SetOfIter {
83            inner: self.inner.iter(),
84        }
85    }
86
87    /// Is this [`SetOf`] empty?
88    pub fn is_empty(&self) -> bool {
89        self.inner.is_empty()
90    }
91
92    /// Number of elements in this [`SetOf`].
93    pub fn len(&self) -> usize {
94        self.inner.len()
95    }
96}
97
98impl<T, const N: usize> Default for SetOf<T, N>
99where
100    T: DerOrd,
101{
102    fn default() -> Self {
103        Self::new()
104    }
105}
106
107impl<'a, T, const N: usize> DecodeValue<'a> for SetOf<T, N>
108where
109    T: Decode<'a> + DerOrd,
110{
111    fn decode_value<R: Reader<'a>>(reader: &mut R, header: Header) -> Result<Self> {
112        reader.read_nested(header.length, |reader| {
113            let mut result = Self::new();
114
115            while !reader.is_finished() {
116                result.inner.push(T::decode(reader)?)?;
117            }
118
119            der_sort(result.inner.as_mut())?;
120            validate(result.inner.as_ref())?;
121            Ok(result)
122        })
123    }
124}
125
126impl<'a, T, const N: usize> EncodeValue for SetOf<T, N>
127where
128    T: 'a + Decode<'a> + Encode + DerOrd,
129{
130    fn value_len(&self) -> Result<Length> {
131        self.iter()
132            .fold(Ok(Length::ZERO), |len, elem| len + elem.encoded_len()?)
133    }
134
135    fn encode_value(&self, writer: &mut impl Writer) -> Result<()> {
136        for elem in self.iter() {
137            elem.encode(writer)?;
138        }
139
140        Ok(())
141    }
142}
143
144impl<'a, T, const N: usize> FixedTag for SetOf<T, N>
145where
146    T: Decode<'a> + DerOrd,
147{
148    const TAG: Tag = Tag::Set;
149}
150
151impl<T, const N: usize> TryFrom<[T; N]> for SetOf<T, N>
152where
153    T: DerOrd,
154{
155    type Error = Error;
156
157    fn try_from(mut arr: [T; N]) -> Result<SetOf<T, N>> {
158        der_sort(&mut arr)?;
159
160        let mut result = SetOf::new();
161
162        for elem in arr {
163            result.insert_ordered(elem)?;
164        }
165
166        Ok(result)
167    }
168}
169
170impl<T, const N: usize> ValueOrd for SetOf<T, N>
171where
172    T: DerOrd,
173{
174    fn value_cmp(&self, other: &Self) -> Result<Ordering> {
175        iter_cmp(self.iter(), other.iter())
176    }
177}
178
179/// Iterator over the elements of an [`SetOf`].
180#[derive(Clone, Debug)]
181pub struct SetOfIter<'a, T> {
182    /// Inner iterator.
183    inner: arrayvec::Iter<'a, T>,
184}
185
186impl<'a, T> Iterator for SetOfIter<'a, T> {
187    type Item = &'a T;
188
189    fn next(&mut self) -> Option<&'a T> {
190        self.inner.next()
191    }
192}
193
194impl<'a, T> ExactSizeIterator for SetOfIter<'a, T> {}
195
196/// ASN.1 `SET OF` backed by a [`Vec`].
197///
198/// This type implements an append-only `SET OF` type which is heap-backed
199/// and depends on `alloc` support.
200#[cfg(feature = "alloc")]
201#[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
202pub struct SetOfVec<T>
203where
204    T: DerOrd,
205{
206    inner: Vec<T>,
207}
208
209#[cfg(feature = "alloc")]
210impl<T: DerOrd> Default for SetOfVec<T> {
211    fn default() -> Self {
212        Self {
213            inner: Default::default(),
214        }
215    }
216}
217
218#[cfg(feature = "alloc")]
219impl<T> SetOfVec<T>
220where
221    T: DerOrd,
222{
223    /// Create a new [`SetOfVec`].
224    pub fn new() -> Self {
225        Self {
226            inner: Vec::default(),
227        }
228    }
229
230    /// Create a new [`SetOfVec`] from the given iterator.
231    ///
232    /// Note: this is an inherent method instead of an impl of the
233    /// [`FromIterator`] trait in order to be fallible.
234    #[allow(clippy::should_implement_trait)]
235    pub fn from_iter<I>(iter: I) -> Result<Self>
236    where
237        I: IntoIterator<Item = T>,
238    {
239        Vec::from_iter(iter).try_into()
240    }
241
242    /// Add an element to this [`SetOfVec`].
243    ///
244    /// Items MUST be added in lexicographical order according to the
245    /// [`DerOrd`] impl on `T`.
246    #[deprecated(since = "0.7.6", note = "use `insert` or `insert_ordered` instead")]
247    pub fn add(&mut self, item: T) -> Result<()> {
248        self.insert_ordered(item)
249    }
250
251    /// Extend a [`SetOfVec`] using an iterator.
252    ///
253    /// Note: this is an inherent method instead of an impl of the
254    /// [`Extend`] trait in order to be fallible.
255    pub fn extend<I>(&mut self, iter: I) -> Result<()>
256    where
257        I: IntoIterator<Item = T>,
258    {
259        self.inner.extend(iter);
260        der_sort(&mut self.inner)
261    }
262
263    /// Insert an item into this [`SetOfVec`]. Must be unique.
264    pub fn insert(&mut self, item: T) -> Result<()> {
265        self.inner.push(item);
266        der_sort(&mut self.inner)
267    }
268
269    /// Insert an item into this [`SetOfVec`]. Must be unique.
270    ///
271    /// Items MUST be added in lexicographical order according to the
272    /// [`DerOrd`] impl on `T`.
273    pub fn insert_ordered(&mut self, item: T) -> Result<()> {
274        // Ensure set elements are lexicographically ordered
275        if let Some(last) = self.inner.last() {
276            check_der_ordering(last, &item)?;
277        }
278
279        self.inner.push(item);
280        Ok(())
281    }
282
283    /// Borrow the elements of this [`SetOfVec`] as a slice.
284    pub fn as_slice(&self) -> &[T] {
285        self.inner.as_slice()
286    }
287
288    /// Get the nth element from this [`SetOfVec`].
289    pub fn get(&self, index: usize) -> Option<&T> {
290        self.inner.get(index)
291    }
292
293    /// Convert this [`SetOfVec`] into the inner [`Vec`].
294    pub fn into_vec(self) -> Vec<T> {
295        self.inner
296    }
297
298    /// Iterate over the elements of this [`SetOfVec`].
299    pub fn iter(&self) -> slice::Iter<'_, T> {
300        self.inner.iter()
301    }
302
303    /// Is this [`SetOfVec`] empty?
304    pub fn is_empty(&self) -> bool {
305        self.inner.is_empty()
306    }
307
308    /// Number of elements in this [`SetOfVec`].
309    pub fn len(&self) -> usize {
310        self.inner.len()
311    }
312}
313
314#[cfg(feature = "alloc")]
315impl<T> AsRef<[T]> for SetOfVec<T>
316where
317    T: DerOrd,
318{
319    fn as_ref(&self) -> &[T] {
320        self.as_slice()
321    }
322}
323
324#[cfg(feature = "alloc")]
325impl<'a, T> DecodeValue<'a> for SetOfVec<T>
326where
327    T: Decode<'a> + DerOrd,
328{
329    fn decode_value<R: Reader<'a>>(reader: &mut R, header: Header) -> Result<Self> {
330        reader.read_nested(header.length, |reader| {
331            let mut inner = Vec::new();
332
333            while !reader.is_finished() {
334                inner.push(T::decode(reader)?);
335            }
336
337            der_sort(inner.as_mut())?;
338            validate(inner.as_ref())?;
339            Ok(Self { inner })
340        })
341    }
342}
343
344#[cfg(feature = "alloc")]
345impl<'a, T> EncodeValue for SetOfVec<T>
346where
347    T: 'a + Decode<'a> + Encode + DerOrd,
348{
349    fn value_len(&self) -> Result<Length> {
350        self.iter()
351            .fold(Ok(Length::ZERO), |len, elem| len + elem.encoded_len()?)
352    }
353
354    fn encode_value(&self, writer: &mut impl Writer) -> Result<()> {
355        for elem in self.iter() {
356            elem.encode(writer)?;
357        }
358
359        Ok(())
360    }
361}
362
363#[cfg(feature = "alloc")]
364impl<T> FixedTag for SetOfVec<T>
365where
366    T: DerOrd,
367{
368    const TAG: Tag = Tag::Set;
369}
370
371#[cfg(feature = "alloc")]
372impl<T> From<SetOfVec<T>> for Vec<T>
373where
374    T: DerOrd,
375{
376    fn from(set: SetOfVec<T>) -> Vec<T> {
377        set.into_vec()
378    }
379}
380
381#[cfg(feature = "alloc")]
382impl<T> TryFrom<Vec<T>> for SetOfVec<T>
383where
384    T: DerOrd,
385{
386    type Error = Error;
387
388    fn try_from(mut vec: Vec<T>) -> Result<SetOfVec<T>> {
389        der_sort(vec.as_mut_slice())?;
390        Ok(SetOfVec { inner: vec })
391    }
392}
393
394#[cfg(feature = "alloc")]
395impl<T, const N: usize> TryFrom<[T; N]> for SetOfVec<T>
396where
397    T: DerOrd,
398{
399    type Error = Error;
400
401    fn try_from(arr: [T; N]) -> Result<SetOfVec<T>> {
402        Vec::from(arr).try_into()
403    }
404}
405
406#[cfg(feature = "alloc")]
407impl<T> ValueOrd for SetOfVec<T>
408where
409    T: DerOrd,
410{
411    fn value_cmp(&self, other: &Self) -> Result<Ordering> {
412        iter_cmp(self.iter(), other.iter())
413    }
414}
415
416// Implement by hand because the derive would create invalid values.
417// Use the conversion from Vec to create a valid value.
418#[cfg(feature = "arbitrary")]
419impl<'a, T> arbitrary::Arbitrary<'a> for SetOfVec<T>
420where
421    T: DerOrd + arbitrary::Arbitrary<'a>,
422{
423    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
424        Self::try_from(
425            u.arbitrary_iter()?
426                .collect::<std::result::Result<Vec<_>, _>>()?,
427        )
428        .map_err(|_| arbitrary::Error::IncorrectFormat)
429    }
430
431    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
432        (0, None)
433    }
434}
435
436/// Ensure set elements are lexicographically ordered using [`DerOrd`].
437fn check_der_ordering<T: DerOrd>(a: &T, b: &T) -> Result<()> {
438    match a.der_cmp(b)? {
439        Ordering::Less => Ok(()),
440        Ordering::Equal => Err(ErrorKind::SetDuplicate.into()),
441        Ordering::Greater => Err(ErrorKind::SetOrdering.into()),
442    }
443}
444
445/// Sort a mut slice according to its [`DerOrd`], returning any errors which
446/// might occur during the comparison.
447///
448/// The algorithm is insertion sort, which should perform well when the input
449/// is mostly sorted to begin with.
450///
451/// This function is used rather than Rust's built-in `[T]::sort_by` in order
452/// to support heapless `no_std` targets as well as to enable bubbling up
453/// sorting errors.
454#[allow(clippy::integer_arithmetic)]
455fn der_sort<T: DerOrd>(slice: &mut [T]) -> Result<()> {
456    for i in 0..slice.len() {
457        let mut j = i;
458
459        while j > 0 {
460            match slice[j - 1].der_cmp(&slice[j])? {
461                Ordering::Less => break,
462                Ordering::Equal => return Err(ErrorKind::SetDuplicate.into()),
463                Ordering::Greater => {
464                    slice.swap(j - 1, j);
465                    j -= 1;
466                }
467            }
468        }
469    }
470
471    Ok(())
472}
473
474/// Validate the elements of a `SET OF`, ensuring that they are all in order
475/// and that there are no duplicates.
476fn validate<T: DerOrd>(slice: &[T]) -> Result<()> {
477    if let Some(len) = slice.len().checked_sub(1) {
478        for i in 0..len {
479            let j = i.checked_add(1).ok_or(ErrorKind::Overflow)?;
480
481            match slice.get(i..=j) {
482                Some([a, b]) => {
483                    if a.der_cmp(b)? != Ordering::Less {
484                        return Err(ErrorKind::SetOrdering.into());
485                    }
486                }
487                _ => return Err(Tag::Set.value_error()),
488            }
489        }
490    }
491
492    Ok(())
493}
494
495#[cfg(test)]
496mod tests {
497    use super::SetOf;
498    #[cfg(feature = "alloc")]
499    use super::SetOfVec;
500    use crate::ErrorKind;
501
502    #[test]
503    fn setof_tryfrom_array() {
504        let arr = [3u16, 2, 1, 65535, 0];
505        let set = SetOf::try_from(arr).unwrap();
506        assert!(set.iter().copied().eq([0, 1, 2, 3, 65535]));
507    }
508
509    #[test]
510    fn setof_tryfrom_array_reject_duplicates() {
511        let arr = [1u16, 1];
512        let err = SetOf::try_from(arr).err().unwrap();
513        assert_eq!(err.kind(), ErrorKind::SetDuplicate);
514    }
515
516    #[cfg(feature = "alloc")]
517    #[test]
518    fn setofvec_tryfrom_array() {
519        let arr = [3u16, 2, 1, 65535, 0];
520        let set = SetOfVec::try_from(arr).unwrap();
521        assert_eq!(set.as_ref(), &[0, 1, 2, 3, 65535]);
522    }
523
524    #[cfg(feature = "alloc")]
525    #[test]
526    fn setofvec_tryfrom_vec() {
527        let vec = vec![3u16, 2, 1, 65535, 0];
528        let set = SetOfVec::try_from(vec).unwrap();
529        assert_eq!(set.as_ref(), &[0, 1, 2, 3, 65535]);
530    }
531
532    #[cfg(feature = "alloc")]
533    #[test]
534    fn setofvec_tryfrom_vec_reject_duplicates() {
535        let vec = vec![1u16, 1];
536        let err = SetOfVec::try_from(vec).err().unwrap();
537        assert_eq!(err.kind(), ErrorKind::SetDuplicate);
538    }
539}
der/asn1/set_of.rs

der/asn1/
set_of.rs
