Repository: pyfisch/cbor
Pull request #82 (2018-11-28 01:07:05)

sort ObjectKey using canonical ordering
This should check an item off of https://github.com/pyfisch/cbor/issues/17. Let me know if you have any questions or concerns! I took care to implement this without needing to serialize the keys

pyfisch: I see this orders only ObjectKey but also lists and even objects can be used as keys. 

With this change it should be relatively easy to serialize `Value` in canonical order but not arbitrary structures with derive.
kcking: Thanks for taking a look at the changes.

Ah yes this doesn't affect derived struct or map serializations. After looking further, it looks like this might be a limitation of serde and the order of serialization of map keys and struct fields is out of our control.

I suppose my next step would be to look into adding that to serde.
pyfisch: I am not sure that serde would accept this functionality. We should try before to make it work in serde-cbor even if it is more limited and has a worse API. It should be possible to serialize structs and enums to a CBOR-Value and then canonically serialize this value. (De-serialization is in reverse.) This will be slower and require temporary allocations for the whole message but may be doable without help from serde.
kcking: I found a way to achieve map sorting in the serializer impl by overriding `collect_map`. I also modified struct serialization to not write anything until `.end()` is called and do the sorting then.

I haven't given any thought to deserialization -- I suppose a `from_slice_canon` method could re-serialize the value and check that it matches the passed-in bytes. Another method would be to check in real-time that keys are sorted and ints are smallest encoding.

Patch:
diff --git a/src/ser.rs b/src/ser.rs
index 39de663..3329675 100644
--- a/src/ser.rs
+++ b/src/ser.rs
@@ -128,6 +128,16 @@ where
         }
     }
 
+    fn serialize_with_same_settings<V: Serialize>(&self, v: V) -> Result<Vec<u8>> {
+        let buf: Vec<u8> = vec![];
+        let mut s = Serializer {
+            writer: buf,
+            packed: self.packed,
+        };
+        v.serialize(&mut s)?;
+        Ok(s.writer)
+    }
+
     /// Writes a CBOR self-describe tag to the stream.
     ///
     /// Tagging allows a decoder to distinguish different file formats based on their content
@@ -439,10 +449,39 @@ where
         self.serialize_collection(5, len)
     }
 
+    fn collect_map<K, V, I>(self, iter: I) -> Result<Self::Ok>
+        where
+            K: Serialize,
+            V: Serialize,
+            I: IntoIterator<Item = (K, V)>,
+    {
+        use serde::ser::SerializeMap;
+
+        let entry_results = iter.into_iter().map(|(k, v)| {
+            (self.serialize_with_same_settings(k), self.serialize_with_same_settings(v))
+        }).collect::<Vec<_>>();
+
+        let mut entries = vec![];
+        for (k, v) in entry_results {
+            let (k, v) = (k?, v?);
+            entries.push((k, v));
+        }
+
+        entries.sort_by(|a, b| a.0.cmp(&b.0));
+
+        let serializer = self.serialize_map(Some(entries.len()))?;
+
+        for (key, value) in entries {
+            serializer.ser.writer.write_all(&key).map_err(Error::io)?;
+            serializer.ser.writer.write_all(&value).map_err(Error::io)?;
+        }
+        serializer.end()
+    }
+
     #[inline]
     fn serialize_struct(self, _name: &'static str, len: usize) -> Result<StructSerializer<'a, W>> {
         self.write_u64(5, len as u64)?;
-        Ok(StructSerializer { ser: self, idx: 0 })
+        Ok(StructSerializer { ser: self, idx: 0, entries: vec![]})
     }
 
     #[inline]
@@ -531,6 +570,7 @@ where
 pub struct StructSerializer<'a, W: 'a> {
     ser: &'a mut Serializer<W>,
     idx: u32,
+    entries: Vec<(Vec<u8>, Vec<u8>)>,
 }
 
 impl<'a, W> StructSerializer<'a, W>
@@ -542,13 +582,14 @@ where
     where
         T: ?Sized + ser::Serialize,
     {
-        if self.ser.packed {
-            self.idx.serialize(&mut *self.ser)?;
+        let key_bytes = if self.ser.packed {
+            self.ser.serialize_with_same_settings(self.idx)?
         } else {
-            key.serialize(&mut *self.ser)?;
-        }
+            self.ser.serialize_with_same_settings(key)?
+        };
         self.idx += 1;
-        value.serialize(&mut *self.ser)
+        self.entries.push((key_bytes, self.ser.serialize_with_same_settings(value)?));
+        Ok(())
     }
 
     #[inline]
@@ -556,6 +597,16 @@ where
         self.idx += 1;
         Ok(())
     }
+
+    #[inline]
+    fn end_inner(mut self) -> Result<()> {
+        self.entries.sort_by(|a, b| a.0.cmp(&b.0));
+        for (k, v) in self.entries {
+            self.ser.writer.write_all(&k).map_err(Error::io)?;
+            self.ser.writer.write_all(&v).map_err(Error::io)?;
+        }
+        Ok(())
+    }
 }
 
 impl<'a, W> ser::SerializeStruct for StructSerializer<'a, W>
@@ -580,7 +631,7 @@ where
 
     #[inline]
     fn end(self) -> Result<()> {
-        Ok(())
+        self.end_inner()
     }
 }
 
@@ -606,7 +657,7 @@ where
 
     #[inline]
     fn end(self) -> Result<()> {
-        Ok(())
+        self.end_inner()
     }
 }
 
diff --git a/src/value/value.rs b/src/value/value.rs
index a3c1ba1..d0cd483 100644
--- a/src/value/value.rs
+++ b/src/value/value.rs
@@ -1,6 +1,7 @@
 //! CBOR values and keys.
 
 use std::collections::BTreeMap;
+use std::cmp::{PartialOrd, Ord, Ordering};
 use std::fmt;
 
 use serde::de;
@@ -360,7 +361,7 @@ impl ser::Serialize for Value {
 }
 
 /// A simplified CBOR value containing only types useful for keys.
-#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub enum ObjectKey {
     /// An integer.
     Integer(i64),
@@ -374,7 +375,53 @@ pub enum ObjectKey {
     Null,
 }
 
+impl Ord for ObjectKey {
+    fn cmp(&self, other: &ObjectKey) -> Ordering {
+        self.canonical_sort_key().cmp(&other.canonical_sort_key())
+    }
+}
+
+impl PartialOrd for ObjectKey {
+    fn partial_cmp(&self, other: &ObjectKey) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl ObjectKey {
+    // Returns a key to sort `ObjectKey`s by major type, then byte-length, then lexicographically
+    // by content. Equivalent to sorting `ObjectKey`s __lexicographically__ by their CBOR serialization.
+    //
+    // Note: the first guidelines regarding canonicalized CBOR
+    // [located here](https://tools.ietf.org/html/rfc7049#section-3.9) sorted keys by length
+    // before sorting by major type, but a [later draft](https://tools.ietf.org/html/draft-ietf-cbor-7049bis-04#section-4.10)
+    // has moved to a purely lexicographic ordering. This newer ordering is also used by the
+    // [WebAuthn standard](https://fidoalliance.org/specs/fido-v2.0-id-20180227/fido-client-to-authenticator-protocol-v2.0-id-20180227.html#ctap2-canonical-cbor-encoding-form).
+    fn canonical_sort_key(&self) -> (u8, usize, Option<&[u8]>) {
+        use ObjectKey::*;
+        match *self {
+            Integer(i) => {
+                let major_type = if i >= 0 { 0u8 } else { 1u8 };
+                let magnitude = if i >= 0 {
+                    i
+                } else {
+                    -(i + 1)
+                };
+                (major_type, magnitude as usize, None)
+            }
+            Bytes(ref v) => {
+                (2, v.len(), Some(v))
+            }
+            String(ref s) => {
+                (3, s.len(), Some(s.as_bytes()))
+            }
+            Bool(b) => {
+                (7, if b { 21 } else { 20 }, None)
+            }
+            Null => {
+                (7, 22, None)
+            }
+        }
+    }
     /// Returns true if the ObjectKey is a byte string.
     pub fn is_bytes(&self) -> bool {
         self.as_bytes().is_some()


Test patch:
diff --git a/tests/canonical.rs b/tests/canonical.rs
new file mode 100644
index 0000000..383263f
--- /dev/null
+++ b/tests/canonical.rs
@@ -0,0 +1,67 @@
+extern crate serde_cbor;
+use serde_cbor::ObjectKey;
+
+#[test]
+fn integer_canonical_sort_order() {
+    let expected = [
+        0, 23, 24, 255, 256, 65535, 65536, 4294967295,
+        -1, -24, -25, -256, -257, -65536, -65537, -4294967296,
+    ].into_iter().map(|i| ObjectKey::Integer(*i)).collect::<Vec<_>>();
+
+    let mut sorted = expected.clone();
+    sorted.sort();
+
+    assert_eq!(expected, sorted);
+}
+
+#[test]
+fn string_canonical_sort_order() {
+    let expected = [
+        "", "a", "b", "aa",
+    ].into_iter().map(|s| ObjectKey::String(s.to_string())).collect::<Vec<_>>();
+
+    let mut sorted = expected.clone();
+    sorted.sort();
+
+    assert_eq!(expected, sorted);
+}
+
+#[test]
+fn bytes_canonical_sort_order() {
+    let expected = vec![
+        vec![], vec![0u8], vec![1u8], vec![0u8, 0u8],
+    ].into_iter().map(|v| ObjectKey::Bytes(v)).collect::<Vec<_>>();
+
+    let mut sorted = expected.clone();
+    sorted.sort();
+
+    assert_eq!(expected, sorted);
+}
+
+#[test]
+fn simple_data_canonical_sort_order() {
+    let expected = vec![
+        ObjectKey::Bool(false), ObjectKey::Bool(true), ObjectKey::Null
+    ];
+
+    let mut sorted = expected.clone();
+    sorted.sort();
+
+    assert_eq!(expected, sorted);
+}
+
+#[test]
+fn major_type_canonical_sort_order() {
+    let expected = vec![
+        ObjectKey::Integer(0),
+        ObjectKey::Integer(-1),
+        ObjectKey::Bytes(vec![]),
+        ObjectKey::String("".to_string()),
+        ObjectKey::Null,
+    ].into_iter().collect::<Vec<_>>();
+
+    let mut sorted = expected.clone();
+    sorted.sort();
+
+    assert_eq!(expected, sorted);
+}
diff --git a/tests/ser.rs b/tests/ser.rs
index 6806988..aba7cca 100644
--- a/tests/ser.rs
+++ b/tests/ser.rs
@@ -34,6 +34,49 @@ fn test_object() {
     assert_eq!(object, test_object);
 }
 
+#[test]
+fn test_object_list_keys() {
+    let mut object = BTreeMap::new();
+    object.insert(vec![0i64], ());
+    object.insert(vec![100i64], ());
+    object.insert(vec![-1i64], ());
+    object.insert(vec![-2i64], ());
+    object.insert(vec![0i64, 0i64], ());
+    object.insert(vec![0i64, -1i64], ());
+    let vec = to_vec(&object).unwrap();
+    assert_eq!(
+        vec![166, 129, 0, 246, 129, 24, 100, 246, 129, 32, 246, 129, 33, 246, 130, 0, 0, 246, 130, 0, 32, 246],
+        vec);
+    let test_object = from_slice(&vec[..]).unwrap();
+    assert_eq!(object, test_object);
+}
+
+#[test]
+fn test_object_object_keys() {
+    use std::iter::FromIterator;
+    let mut object = BTreeMap::new();
+    let keys = vec![
+        vec!["a"],
+        vec!["b"],
+        vec!["c"],
+        vec!["d"],
+        vec!["aa"],
+        vec!["a", "aa"],
+    ].into_iter().map(|v| {
+        BTreeMap::from_iter(v.into_iter().map(|s| (s.to_owned(), ())))
+    });
+
+    for key in keys {
+        object.insert(key, ());
+    }
+    let vec = to_vec(&object).unwrap();
+    assert_eq!(
+        vec![166, 161, 97, 97, 246, 246, 161, 97, 98, 246, 246, 161, 97, 99, 246, 246, 161, 97, 100, 246, 246, 161, 98, 97, 97, 246, 246, 162, 97, 97, 246, 98, 97, 97, 246, 246],
+        vec);
+    let test_object = from_slice(&vec[..]).unwrap();
+    assert_eq!(object, test_object);
+}
+
 #[test]
 fn test_float() {
     let vec = to_vec(&12.3f64).unwrap();
diff --git a/tests/std_types.rs b/tests/std_types.rs
index ff56d80..fb03e26 100644
--- a/tests/std_types.rs
+++ b/tests/std_types.rs
@@ -113,7 +113,7 @@ testcase!(test_person_struct,
         year_of_birth: 1906,
         profession: Some("computer scientist".to_string()),
     },
-    "a3646e616d656c477261636520486f707065726d796561725f6f665f62697274681907726a70726f66657373696f6e72636f6d707574657220736369656e74697374");
+    "a3646e616d656c477261636520486f707065726a70726f66657373696f6e72636f6d707574657220736369656e746973746d796561725f6f665f6269727468190772");
 
 #[derive(Debug, PartialEq, Deserialize, Serialize)]
 struct OptionalPerson {