1 // SPDX-License-Identifier: Apache-2.0
2
3 use crate::value::Value;
4 use alloc::vec::Vec;
5 use core::cmp::Ordering;
6 use serde::{de, ser};
7
8 /// Manually serialize values to compare them.
serialized_canonical_cmp(v1: &Value, v2: &Value) -> Ordering9 fn serialized_canonical_cmp(v1: &Value, v2: &Value) -> Ordering {
10 // There is an optimization to be done here, but it would take a lot more code
11 // and using mixing keys, Arrays or Maps as CanonicalValue is probably not the
12 // best use of this type as it is meant mainly to be used as keys.
13
14 let mut bytes1 = Vec::new();
15 let _ = crate::ser::into_writer(v1, &mut bytes1);
16 let mut bytes2 = Vec::new();
17 let _ = crate::ser::into_writer(v2, &mut bytes2);
18
19 match bytes1.len().cmp(&bytes2.len()) {
20 Ordering::Equal => bytes1.cmp(&bytes2),
21 x => x,
22 }
23 }
24
25 /// Compares two values uses canonical comparison, as defined in both
26 /// RFC 7049 Section 3.9 (regarding key sorting) and RFC 8949 4.2.3 (as errata).
27 ///
28 /// In short, the comparison follow the following rules:
29 /// - If two keys have different lengths, the shorter one sorts earlier;
30 /// - If two keys have the same length, the one with the lower value in
31 /// (byte-wise) lexical order sorts earlier.
32 ///
33 /// This specific comparison allows Maps and sorting that respect these two rules.
cmp_value(v1: &Value, v2: &Value) -> Ordering34 pub fn cmp_value(v1: &Value, v2: &Value) -> Ordering {
35 use Value::*;
36
37 match (v1, v2) {
38 (Integer(i), Integer(o)) => {
39 // Because of the first rule above, two numbers might be in a different
40 // order than regular i128 comparison. For example, 10 < -1 in
41 // canonical ordering, since 10 serializes to `0x0a` and -1 to `0x20`,
42 // and -1 < -1000 because of their lengths.
43 i.canonical_cmp(o)
44 }
45 (Text(s), Text(o)) => match s.len().cmp(&o.len()) {
46 Ordering::Equal => s.cmp(o),
47 x => x,
48 },
49 (Bool(s), Bool(o)) => s.cmp(o),
50 (Null, Null) => Ordering::Equal,
51 (Tag(t, v), Tag(ot, ov)) => match Value::from(*t).partial_cmp(&Value::from(*ot)) {
52 Some(Ordering::Equal) | None => match v.partial_cmp(ov) {
53 Some(x) => x,
54 None => serialized_canonical_cmp(v1, v2),
55 },
56 Some(x) => x,
57 },
58 (_, _) => serialized_canonical_cmp(v1, v2),
59 }
60 }
61
62 /// A CBOR Value that impl Ord and Eq to allow sorting of values as defined in both
63 /// RFC 7049 Section 3.9 (regarding key sorting) and RFC 8949 4.2.3 (as errata).
64 ///
65 /// Since a regular [Value] can be
66 #[derive(Clone, Debug)]
67 pub struct CanonicalValue(Value);
68
69 impl PartialEq for CanonicalValue {
eq(&self, other: &Self) -> bool70 fn eq(&self, other: &Self) -> bool {
71 self.cmp(other) == Ordering::Equal
72 }
73 }
74
75 impl Eq for CanonicalValue {}
76
77 impl From<Value> for CanonicalValue {
from(v: Value) -> Self78 fn from(v: Value) -> Self {
79 Self(v)
80 }
81 }
82
83 impl From<CanonicalValue> for Value {
from(v: CanonicalValue) -> Self84 fn from(v: CanonicalValue) -> Self {
85 v.0
86 }
87 }
88
89 impl ser::Serialize for CanonicalValue {
serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: ser::Serializer,90 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
91 where
92 S: ser::Serializer,
93 {
94 self.0.serialize(serializer)
95 }
96 }
97
98 impl<'de> de::Deserialize<'de> for CanonicalValue {
deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: de::Deserializer<'de>,99 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
100 where
101 D: de::Deserializer<'de>,
102 {
103 Value::deserialize(deserializer).map(Into::into)
104 }
105
deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error> where D: de::Deserializer<'de>,106 fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error>
107 where
108 D: de::Deserializer<'de>,
109 {
110 Value::deserialize_in_place(deserializer, &mut place.0)
111 }
112 }
113
114 impl Ord for CanonicalValue {
cmp(&self, other: &Self) -> Ordering115 fn cmp(&self, other: &Self) -> Ordering {
116 cmp_value(&self.0, &other.0)
117 }
118 }
119
120 impl PartialOrd for CanonicalValue {
partial_cmp(&self, other: &Self) -> Option<Ordering>121 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
122 Some(cmp_value(&self.0, &other.0))
123 }
124 }
125