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 `SET OF`. This is
6//! technically non-canonical, but occurs frequently enough that most DER decoders tolerate it.
7//!
8//! When decoding with `EncodingRules::Der`, this implementation sorts the elements of `SET OF` at
9//! decode-time to ensure reserializations are canonical.
10
11#![cfg(any(feature = "alloc", feature = "heapless"))]
12
13use crate::{
14    Decode, DecodeValue, DerOrd, Encode, EncodeValue, Error, ErrorKind, FixedTag, Header, Length,
15    Reader, Tag, ValueOrd, Writer, ord::iter_cmp,
16};
17use core::cmp::Ordering;
18
19#[cfg(feature = "alloc")]
20use alloc::vec::Vec;
21#[cfg(any(feature = "alloc", feature = "heapless"))]
22use core::slice;
23
24/// ASN.1 `SET OF` backed by an array.
25///
26/// This type implements an append-only `SET OF` type which is stack-based
27/// and does not depend on `alloc` support.
28// TODO(tarcieri): use `ArrayVec` when/if it's merged into `core` (rust-lang/rfcs#3316)
29#[cfg(feature = "heapless")]
30#[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash)]
31pub struct SetOf<T, const N: usize>
32where
33    T: DerOrd,
34{
35    inner: heapless::Vec<T, N>,
36}
37
38#[cfg(feature = "heapless")]
39impl<T, const N: usize> SetOf<T, N>
40where
41    T: DerOrd,
42{
43    /// Create a new [`SetOf`].
44    #[must_use]
45    pub fn new() -> Self {
46        Self {
47            inner: heapless::Vec::default(),
48        }
49    }
50
51    /// Insert an item into this [`SetOf`].
52    ///
53    /// # Errors
54    /// If there's a duplicate or sorting error.
55    pub fn insert(&mut self, item: T) -> Result<(), Error> {
56        check_duplicate(&item, self.iter())?;
57        self.try_push(item)?;
58        der_sort(self.inner.as_mut())
59    }
60
61    /// Insert an item into this [`SetOf`].
62    ///
63    /// Items MUST be added in lexicographical order according to the [`DerOrd`] impl on `T`.
64    ///
65    /// # Errors
66    /// If items are added out-of-order or there isn't sufficient space.
67    pub fn insert_ordered(&mut self, item: T) -> Result<(), Error> {
68        // Ensure set elements are lexicographically ordered
69        if let Some(last) = self.inner.last() {
70            check_der_ordering(last, &item)?;
71        }
72
73        self.try_push(item)
74    }
75
76    /// Borrow the elements of this [`SetOf`] as a slice.
77    pub fn as_slice(&self) -> &[T] {
78        self.inner.as_slice()
79    }
80
81    /// Get the nth element from this [`SetOf`].
82    pub fn get(&self, index: usize) -> Option<&T> {
83        self.inner.get(index)
84    }
85
86    /// Extract the inner `heapless::Vec`.
87    pub fn into_inner(self) -> heapless::Vec<T, N> {
88        self.inner
89    }
90
91    /// Iterate over the elements of this [`SetOf`].
92    pub fn iter(&self) -> SetOfIter<'_, T> {
93        SetOfIter {
94            inner: self.inner.iter(),
95        }
96    }
97
98    /// Is this [`SetOf`] empty?
99    pub fn is_empty(&self) -> bool {
100        self.inner.is_empty()
101    }
102
103    /// Number of elements in this [`SetOf`].
104    pub fn len(&self) -> usize {
105        self.inner.len()
106    }
107
108    /// Attempt to push an element onto the [`SetOf`].
109    ///
110    /// Does not perform ordering or uniqueness checks.
111    fn try_push(&mut self, item: T) -> Result<(), Error> {
112        self.inner
113            .push(item)
114            .map_err(|_| ErrorKind::Overlength.into())
115    }
116}
117
118#[cfg(feature = "heapless")]
119impl<T, const N: usize> AsRef<[T]> for SetOf<T, N>
120where
121    T: DerOrd,
122{
123    fn as_ref(&self) -> &[T] {
124        self.as_slice()
125    }
126}
127
128#[cfg(feature = "heapless")]
129impl<T, const N: usize> Default for SetOf<T, N>
130where
131    T: DerOrd,
132{
133    fn default() -> Self {
134        Self::new()
135    }
136}
137
138#[cfg(feature = "heapless")]
139impl<'a, T, const N: usize> DecodeValue<'a> for SetOf<T, N>
140where
141    T: Decode<'a> + DerOrd,
142{
143    type Error = T::Error;
144
145    fn decode_value<R: Reader<'a>>(reader: &mut R, _header: Header) -> Result<Self, Self::Error> {
146        let mut result = Self::new();
147
148        while !reader.is_finished() {
149            result.try_push(T::decode(reader)?)?;
150        }
151
152        if reader.encoding_rules().is_der() {
153            // Ensure elements of the `SetOf` are sorted and will serialize as valid DER
154            der_sort(result.inner.as_mut())?;
155        }
156
157        Ok(result)
158    }
159}
160
161#[cfg(feature = "heapless")]
162impl<T, const N: usize> EncodeValue for SetOf<T, N>
163where
164    T: Encode + DerOrd,
165{
166    fn value_len(&self) -> Result<Length, Error> {
167        self.iter()
168            .try_fold(Length::ZERO, |len, elem| len + elem.encoded_len()?)
169    }
170
171    fn encode_value(&self, writer: &mut impl Writer) -> Result<(), Error> {
172        for elem in self.iter() {
173            elem.encode(writer)?;
174        }
175
176        Ok(())
177    }
178}
179
180#[cfg(feature = "heapless")]
181impl<T, const N: usize> FixedTag for SetOf<T, N>
182where
183    T: DerOrd,
184{
185    const TAG: Tag = Tag::Set;
186}
187
188#[cfg(feature = "heapless")]
189impl<T, const N: usize> TryFrom<[T; N]> for SetOf<T, N>
190where
191    T: DerOrd,
192{
193    type Error = Error;
194
195    fn try_from(mut arr: [T; N]) -> Result<SetOf<T, N>, Error> {
196        der_sort(&mut arr)?;
197
198        let mut result = SetOf::new();
199
200        for elem in arr {
201            result.insert_ordered(elem)?;
202        }
203
204        Ok(result)
205    }
206}
207
208#[cfg(feature = "heapless")]
209impl<T, const N: usize> ValueOrd for SetOf<T, N>
210where
211    T: DerOrd,
212{
213    fn value_cmp(&self, other: &Self) -> Result<Ordering, Error> {
214        iter_cmp(self.iter(), other.iter())
215    }
216}
217
218/// Iterator over the elements of an [`SetOf`].
219#[derive(Clone, Debug)]
220pub struct SetOfIter<'a, T> {
221    /// Inner iterator.
222    inner: slice::Iter<'a, T>,
223}
224
225impl<'a, T: 'a> Iterator for SetOfIter<'a, T> {
226    type Item = &'a T;
227
228    fn next(&mut self) -> Option<&'a T> {
229        self.inner.next()
230    }
231
232    fn size_hint(&self) -> (usize, Option<usize>) {
233        self.inner.size_hint()
234    }
235}
236
237impl<'a, T: 'a> ExactSizeIterator for SetOfIter<'a, T> {}
238
239/// ASN.1 `SET OF` backed by a [`Vec`].
240///
241/// This type implements an append-only `SET OF` type which is heap-backed
242/// and depends on `alloc` support.
243#[cfg(feature = "alloc")]
244#[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash)]
245pub struct SetOfVec<T>
246where
247    T: DerOrd,
248{
249    inner: Vec<T>,
250}
251
252#[cfg(feature = "alloc")]
253impl<T: DerOrd> Default for SetOfVec<T> {
254    fn default() -> Self {
255        Self {
256            inner: Default::default(),
257        }
258    }
259}
260
261#[cfg(feature = "alloc")]
262impl<T> SetOfVec<T>
263where
264    T: DerOrd,
265{
266    /// Create a new [`SetOfVec`].
267    #[must_use]
268    pub fn new() -> Self {
269        Self {
270            inner: Vec::default(),
271        }
272    }
273
274    /// Create a new [`SetOfVec`] from the given iterator.
275    ///
276    /// Note: this is an inherent method instead of an impl of the [`FromIterator`] trait in order
277    /// to be fallible.
278    ///
279    /// # Errors
280    /// If a sorting error occurred.
281    #[allow(clippy::should_implement_trait)]
282    pub fn from_iter<I>(iter: I) -> Result<Self, Error>
283    where
284        I: IntoIterator<Item = T>,
285    {
286        Vec::from_iter(iter).try_into()
287    }
288
289    /// Extend a [`SetOfVec`] using an iterator.
290    ///
291    /// Note: this is an inherent method instead of an impl of the [`Extend`] trait in order to
292    /// be fallible.
293    ///
294    /// # Errors
295    /// If a sorting error occurred.
296    pub fn extend<I>(&mut self, iter: I) -> Result<(), Error>
297    where
298        I: IntoIterator<Item = T>,
299    {
300        self.inner.extend(iter);
301        der_sort(&mut self.inner)
302    }
303
304    /// Insert an item into this [`SetOfVec`]. Must be unique.
305    ///
306    /// # Errors
307    /// If `item` is a duplicate or a sorting error occurred.
308    pub fn insert(&mut self, item: T) -> Result<(), Error> {
309        check_duplicate(&item, self.iter())?;
310        self.inner.push(item);
311        der_sort(&mut self.inner)
312    }
313
314    /// Insert an item into this [`SetOfVec`]. Must be unique.
315    ///
316    /// Items MUST be added in lexicographical order according to the [`DerOrd`] impl on `T`.
317    ///
318    /// # Errors
319    /// If a sorting error occurred.
320    pub fn insert_ordered(&mut self, item: T) -> Result<(), Error> {
321        // Ensure set elements are lexicographically ordered
322        if let Some(last) = self.inner.last() {
323            check_der_ordering(last, &item)?;
324        }
325
326        self.inner.push(item);
327        Ok(())
328    }
329
330    /// Borrow the elements of this [`SetOfVec`] as a slice.
331    #[must_use]
332    pub fn as_slice(&self) -> &[T] {
333        self.inner.as_slice()
334    }
335
336    /// Get the nth element from this [`SetOfVec`].
337    #[must_use]
338    pub fn get(&self, index: usize) -> Option<&T> {
339        self.inner.get(index)
340    }
341
342    /// Convert this [`SetOfVec`] into the inner [`Vec`].
343    #[must_use]
344    pub fn into_vec(self) -> Vec<T> {
345        self.inner
346    }
347
348    /// Iterate over the elements of this [`SetOfVec`].
349    #[must_use]
350    pub fn iter(&self) -> SetOfIter<'_, T> {
351        SetOfIter {
352            inner: self.inner.iter(),
353        }
354    }
355
356    /// Is this [`SetOfVec`] empty?
357    #[must_use]
358    pub fn is_empty(&self) -> bool {
359        self.inner.is_empty()
360    }
361
362    /// Number of elements in this [`SetOfVec`].
363    #[must_use]
364    pub fn len(&self) -> usize {
365        self.inner.len()
366    }
367}
368
369#[cfg(feature = "alloc")]
370impl<T> AsRef<[T]> for SetOfVec<T>
371where
372    T: DerOrd,
373{
374    fn as_ref(&self) -> &[T] {
375        self.as_slice()
376    }
377}
378
379#[cfg(feature = "alloc")]
380impl<'a, T> DecodeValue<'a> for SetOfVec<T>
381where
382    T: Decode<'a> + DerOrd,
383{
384    type Error = T::Error;
385
386    fn decode_value<R: Reader<'a>>(reader: &mut R, _header: Header) -> Result<Self, Self::Error> {
387        let mut inner = Vec::new();
388
389        while !reader.is_finished() {
390            inner.push(T::decode(reader)?);
391        }
392
393        if reader.encoding_rules().is_der() {
394            der_sort(inner.as_mut())?;
395        }
396
397        Ok(Self { inner })
398    }
399}
400
401#[cfg(feature = "alloc")]
402impl<T> EncodeValue for SetOfVec<T>
403where
404    T: Encode + DerOrd,
405{
406    fn value_len(&self) -> Result<Length, Error> {
407        self.iter()
408            .try_fold(Length::ZERO, |len, elem| len + elem.encoded_len()?)
409    }
410
411    fn encode_value(&self, writer: &mut impl Writer) -> Result<(), Error> {
412        for elem in self.iter() {
413            elem.encode(writer)?;
414        }
415
416        Ok(())
417    }
418}
419
420#[cfg(feature = "alloc")]
421impl<T> FixedTag for SetOfVec<T>
422where
423    T: DerOrd,
424{
425    const TAG: Tag = Tag::Set;
426}
427
428#[cfg(feature = "alloc")]
429impl<T> From<SetOfVec<T>> for Vec<T>
430where
431    T: DerOrd,
432{
433    fn from(set: SetOfVec<T>) -> Vec<T> {
434        set.into_vec()
435    }
436}
437
438#[cfg(feature = "alloc")]
439impl<T> TryFrom<Vec<T>> for SetOfVec<T>
440where
441    T: DerOrd,
442{
443    type Error = Error;
444
445    fn try_from(mut vec: Vec<T>) -> Result<SetOfVec<T>, Error> {
446        // TODO(tarcieri): use `[T]::sort_by` here?
447        der_sort(vec.as_mut_slice())?;
448        Ok(SetOfVec { inner: vec })
449    }
450}
451
452#[cfg(feature = "alloc")]
453impl<T, const N: usize> TryFrom<[T; N]> for SetOfVec<T>
454where
455    T: DerOrd,
456{
457    type Error = Error;
458
459    fn try_from(arr: [T; N]) -> Result<SetOfVec<T>, Error> {
460        Vec::from(arr).try_into()
461    }
462}
463
464#[cfg(feature = "alloc")]
465impl<T> ValueOrd for SetOfVec<T>
466where
467    T: DerOrd,
468{
469    fn value_cmp(&self, other: &Self) -> Result<Ordering, Error> {
470        iter_cmp(self.iter(), other.iter())
471    }
472}
473
474// Implement by hand because custom derive would create invalid values.
475// Use the conversion from Vec to create a valid value.
476#[cfg(feature = "arbitrary")]
477impl<'a, T> arbitrary::Arbitrary<'a> for SetOfVec<T>
478where
479    T: DerOrd + arbitrary::Arbitrary<'a>,
480{
481    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
482        Self::try_from(u.arbitrary_iter()?.collect::<Result<Vec<_>, _>>()?)
483            .map_err(|_| arbitrary::Error::IncorrectFormat)
484    }
485
486    fn size_hint(_depth: usize) -> (usize, Option<usize>) {
487        (0, None)
488    }
489}
490
491/// Check if the given item is a duplicate, given an iterator over sorted items (which we can
492/// short-circuit once we hit `Ordering::Less`.
493fn check_duplicate<'a, T, I>(item: &T, iter: I) -> Result<(), Error>
494where
495    T: DerOrd + 'a,
496    I: Iterator<Item = &'a T>,
497{
498    for item2 in iter {
499        match item.der_cmp(item2)? {
500            Ordering::Less => return Ok(()), // all remaining items are greater
501            Ordering::Equal => return Err(ErrorKind::SetDuplicate.into()),
502            Ordering::Greater => continue,
503        }
504    }
505
506    Ok(())
507}
508
509/// Ensure set elements are lexicographically ordered using [`DerOrd`].
510fn check_der_ordering<T: DerOrd>(a: &T, b: &T) -> Result<(), Error> {
511    match a.der_cmp(b)? {
512        Ordering::Less => Ok(()),
513        Ordering::Equal => Err(ErrorKind::SetDuplicate.into()),
514        Ordering::Greater => Err(ErrorKind::SetOrdering.into()),
515    }
516}
517
518/// Sort a mut slice according to its [`DerOrd`], returning any errors which
519/// might occur during the comparison.
520///
521/// The algorithm is insertion sort, which should perform well when the input
522/// is mostly sorted to begin with.
523///
524/// This function is used rather than Rust's built-in `[T]::sort_by` in order
525/// to support heapless `no_std` targets as well as to enable bubbling up
526/// sorting errors.
527#[allow(clippy::arithmetic_side_effects)]
528fn der_sort<T: DerOrd>(slice: &mut [T]) -> Result<(), Error> {
529    for i in 0..slice.len() {
530        let mut j = i;
531
532        while j > 0 {
533            match slice[j - 1].der_cmp(&slice[j])? {
534                Ordering::Less => break,
535                Ordering::Equal => return Err(ErrorKind::SetDuplicate.into()),
536                Ordering::Greater => {
537                    slice.swap(j - 1, j);
538                    j -= 1;
539                }
540            }
541        }
542    }
543
544    Ok(())
545}
546
547#[cfg(test)]
548#[allow(clippy::unwrap_used)]
549mod tests {
550    #[cfg(feature = "alloc")]
551    use super::SetOfVec;
552    use crate::ErrorKind;
553    #[cfg(feature = "heapless")]
554    use {super::SetOf, crate::DerOrd};
555
556    #[cfg(feature = "heapless")]
557    #[test]
558    fn setof_insert() {
559        let mut setof = SetOf::<u8, 10>::new();
560        setof.insert(42).unwrap();
561        assert_eq!(setof.len(), 1);
562        assert_eq!(*setof.iter().next().unwrap(), 42);
563
564        // Ensure duplicates are disallowed
565        assert_eq!(
566            setof.insert(42).unwrap_err().kind(),
567            ErrorKind::SetDuplicate
568        );
569        assert_eq!(setof.len(), 1);
570    }
571
572    #[cfg(feature = "heapless")]
573    #[test]
574    fn setof_tryfrom_array() {
575        let arr = [3u16, 2, 1, 65535, 0];
576        let set = SetOf::try_from(arr).unwrap();
577        assert!(set.iter().copied().eq([0, 1, 2, 3, 65535]));
578    }
579
580    #[cfg(feature = "heapless")]
581    #[test]
582    fn setof_tryfrom_array_reject_duplicates() {
583        let arr = [1u16, 1];
584        let err = SetOf::try_from(arr).err().unwrap();
585        assert_eq!(err.kind(), ErrorKind::SetDuplicate);
586    }
587
588    #[cfg(feature = "heapless")]
589    #[test]
590    fn setof_valueord_value_cmp() {
591        use core::cmp::Ordering;
592
593        let arr1 = [3u16, 2, 1, 5, 0];
594        let arr2 = [3u16, 2, 1, 4, 0];
595        let set1 = SetOf::try_from(arr1).unwrap();
596        let set2 = SetOf::try_from(arr2).unwrap();
597        assert_eq!(set1.der_cmp(&set2), Ok(Ordering::Greater));
598    }
599
600    #[cfg(feature = "alloc")]
601    #[test]
602    fn setofvec_insert() {
603        let mut setof = SetOfVec::new();
604        setof.insert(42).unwrap();
605        assert_eq!(setof.len(), 1);
606        assert_eq!(*setof.iter().next().unwrap(), 42);
607
608        // Ensure duplicates are disallowed
609        assert_eq!(
610            setof.insert(42).unwrap_err().kind(),
611            ErrorKind::SetDuplicate
612        );
613        assert_eq!(setof.len(), 1);
614    }
615
616    #[cfg(feature = "alloc")]
617    #[test]
618    fn setofvec_tryfrom_array() {
619        let arr = [3u16, 2, 1, 65535, 0];
620        let set = SetOfVec::try_from(arr).unwrap();
621        assert_eq!(set.as_ref(), &[0, 1, 2, 3, 65535]);
622    }
623
624    #[cfg(feature = "alloc")]
625    #[test]
626    fn setofvec_tryfrom_vec() {
627        let vec = vec![3u16, 2, 1, 65535, 0];
628        let set = SetOfVec::try_from(vec).unwrap();
629        assert_eq!(set.as_ref(), &[0, 1, 2, 3, 65535]);
630    }
631
632    #[cfg(feature = "alloc")]
633    #[test]
634    fn setofvec_tryfrom_vec_reject_duplicates() {
635        let vec = vec![1u16, 1];
636        let err = SetOfVec::try_from(vec).err().unwrap();
637        assert_eq!(err.kind(), ErrorKind::SetDuplicate);
638    }
639}
der/asn1/set_of.rs

der/asn1/
set_of.rs
