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 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
85impl<T, const N: usize> Default for SetOf<T, N>
86where
87    T: DerOrd,
88{
89    fn default() -> Self {
90        Self::new()
91    }
92}
93
94impl<'a, T, const N: usize> DecodeValue<'a> for SetOf<T, N>
95where
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
113impl<'a, T, const N: usize> EncodeValue for SetOf<T, N>
114where
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
131impl<'a, T, const N: usize> FixedTag for SetOf<T, N>
132where
133    T: Decode<'a> + DerOrd,
134{
135    const TAG: Tag = Tag::Set;
136}
137
138impl<T, const N: usize> TryFrom<[T; N]> for SetOf<T, N>
139where
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
157impl<T, const N: usize> ValueOrd for SetOf<T, N>
158where
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)]
168pub struct SetOfIter<'a, T> {
169    /// Inner iterator.
170    inner: arrayvec::Iter<'a, T>,
171}
172
173impl<'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
181impl<'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)]
190pub struct SetOfVec<T>
191where
192    T: DerOrd,
193{
194    inner: Vec<T>,
195}
196
197#[cfg(feature = "alloc")]
198#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
199impl<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")))]
209impl<T> SetOfVec<T>
210where
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")))]
269impl<T> AsRef<[T]> for SetOfVec<T>
270where
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")))]
280impl<'a, T> DecodeValue<'a> for SetOfVec<T>
281where
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")))]
301impl<'a, T> EncodeValue for SetOfVec<T>
302where
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")))]
321impl<T> FixedTag for SetOfVec<T>
322where
323    T: DerOrd,
324{
325    const TAG: Tag = Tag::Set;
326}
327
328#[cfg(feature = "alloc")]
329#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
330impl<T> From<SetOfVec<T>> for Vec<T>
331where
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")))]
341impl<T> TryFrom<Vec<T>> for SetOfVec<T>
342where
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")))]
356impl<T, const N: usize> TryFrom<[T; N]> for SetOfVec<T>
357where
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")))]
369impl<T> ValueOrd for SetOfVec<T>
370where
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)]
388fn 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.
403fn 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"))]
423mod 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}
der/asn1/set_of.rs

der/asn1/
set_of.rs
