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. |

9 | 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. |

34 | 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 { |

70 | 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 { |

78 | fn from(v: Value) -> Self { |

79 | Self(v) |

80 | } |

81 | } |

82 | |

83 | impl From<CanonicalValue> for Value { |

84 | fn from(v: CanonicalValue) -> Self { |

85 | v.0 |

86 | } |

87 | } |

88 | |

89 | impl ser::Serialize for CanonicalValue { |

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 { |

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 | |

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 { |

115 | fn cmp(&self, other: &Self) -> Ordering { |

116 | cmp_value(&self.0, &other.0) |

117 | } |

118 | } |

119 | |

120 | impl PartialOrd for CanonicalValue { |

121 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |

122 | Some(cmp_value(&self.0, &other.0)) |

123 | } |

124 | } |

125 |