Repository: pyfisch/cbor
Pull request #35 (2017-06-09 13:31:57)

Change Value::Object to BTreeMap
Rust's `HashMap`'s iteration order is non-deterministic, meaning deserializing into `Value` and then serializing has a non-deterministic output. This PR changes that by storing a `Value::Object` as a `BTreeMap`, the same way `serde_json` does it. This is a [breaking-change].

Note that this PR does not preserve the order of incoming CBOR, it merely makes sure that the output order is always the same. `serde_json` has an optional `preserve_order` feature using [linked-hash-map](https://crates.io/crates/linked-hash-map) which would need to be implemented to reach parity with `serde_json`.

jethrogb: Possible step towards #17

Patch:
diff --git a/src/lib.rs b/src/lib.rs
index 3a4c249..8976852 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -94,11 +94,11 @@
 //! Read a CBOR value that is known to be a map of string keys to string values and print it.
 //!
 //! ```rust
-//! use std::collections::HashMap;
+//! use std::collections::BTreeMap;
 //! use serde_cbor::from_slice;
 //!
 //! let slice = b"\xa5aaaAabaBacaCadaDaeaE";
-//! let value: HashMap<String, String> = from_slice(slice).unwrap();
+//! let value: BTreeMap<String, String> = from_slice(slice).unwrap();
 //! println!("{:?}", value); // {"e": "E", "d": "D", "a": "A", "c": "C", "b": "B"}
 //! ```
 //!
@@ -115,10 +115,10 @@
 //! Serialize an object.
 //!
 //! ```rust
-//! use std::collections::HashMap;
+//! use std::collections::BTreeMap;
 //! use serde_cbor::to_vec;
 //!
-//! let mut programming_languages = HashMap::new();
+//! let mut programming_languages = BTreeMap::new();
 //! programming_languages.insert("rust", vec!["safe", "concurrent", "fast"]);
 //! programming_languages.insert("python", vec!["powerful", "friendly", "open"]);
 //! programming_languages.insert("js", vec!["lightweight", "interpreted", "object-oriented"]);
diff --git a/src/value.rs b/src/value.rs
index bcb21a1..beff393 100644
--- a/src/value.rs
+++ b/src/value.rs
@@ -1,6 +1,6 @@
 //! CBOR values and keys.
 
-use std::collections::HashMap;
+use std::collections::BTreeMap;
 use std::fmt;
 
 use serde::de;
@@ -20,7 +20,7 @@ pub enum Value {
     /// Represents a list.
     Array(Vec<Value>),
     /// Represents a map.
-    Object(HashMap<ObjectKey, Value>),
+    Object(BTreeMap<ObjectKey, Value>),
     /// Represents a floating point value.
     F64(f64),
     /// Represents a boolean value.
@@ -36,7 +36,7 @@ impl Value {
     }
 
     /// If the value is an object, returns the associated BTreeMap. Returns None otherwise.
-    pub fn as_object(&self) -> Option<&HashMap<ObjectKey, Value>> {
+    pub fn as_object(&self) -> Option<&BTreeMap<ObjectKey, Value>> {
         if let Value::Object(ref v) = *self {
             Some(v)
         } else {
@@ -46,7 +46,7 @@ impl Value {
 
 
     /// If the value is an object, returns the associated mutable BTreeMap. Returns None otherwise.
-    pub fn as_object_mut(&mut self) -> Option<&mut HashMap<ObjectKey, Value>> {
+    pub fn as_object_mut(&mut self) -> Option<&mut BTreeMap<ObjectKey, Value>> {
         if let Value::Object(ref mut v) = *self {
             Some(v)
         } else {
@@ -305,7 +305,7 @@ impl<'de> de::Deserialize<'de> for Value {
             fn visit_map<V>(self, mut visitor: V) -> Result<Value, V::Error>
                 where V: de::MapAccess<'de>
             {
-                let mut values = HashMap::new();
+                let mut values = BTreeMap::new();
 
                 while let Some((key, value)) = visitor.next_entry()? {
                     values.insert(key, value);


Test patch:
diff --git a/tests/de.rs b/tests/de.rs
index 3056cda..9a4c9b8 100644
--- a/tests/de.rs
+++ b/tests/de.rs
@@ -1,6 +1,6 @@
 extern crate serde_cbor;
 
-use std::collections::HashMap;
+use std::collections::BTreeMap;
 
 use serde_cbor::{to_vec, Value, ObjectKey, error, de};
 
@@ -75,7 +75,7 @@ fn test_list2() {
 #[test]
 fn test_object() {
     let value: error::Result<Value> = de::from_slice(b"\xa5aaaAabaBacaCadaDaeaE");
-    let mut object = HashMap::new();
+    let mut object = BTreeMap::new();
     object.insert(ObjectKey::String("a".to_owned()), Value::String("A".to_owned()));
     object.insert(ObjectKey::String("b".to_owned()), Value::String("B".to_owned()));
     object.insert(ObjectKey::String("c".to_owned()), Value::String("C".to_owned()));
@@ -87,7 +87,7 @@ fn test_object() {
 #[test]
 fn test_indefinite_object() {
     let value: error::Result<Value> = de::from_slice(b"\xbfaa\x01ab\x9f\x02\x03\xff\xff");
-    let mut object = HashMap::new();
+    let mut object = BTreeMap::new();
     object.insert(ObjectKey::String("a".to_owned()), Value::U64(1));
     object.insert(ObjectKey::String("b".to_owned()), Value::Array(vec![Value::U64(2), Value::U64(3)]));
     assert_eq!(value.unwrap(), Value::Object(object));
@@ -170,7 +170,7 @@ fn test_32f16() {
 fn test_kietaub_file() {
     let file = include_bytes!("kietaub.cbor");
     let value_result: error::Result<Value> = de::from_slice(file);
-    assert!(value_result.is_ok());
+    value_result.unwrap();
 }
 
 #[test]
@@ -199,7 +199,17 @@ fn test_option_none_roundtrip() {
 fn test_variable_length_map() {
     let slice = b"\xbf\x67\x6d\x65\x73\x73\x61\x67\x65\x64\x70\x6f\x6e\x67\xff";
     let value: Value = de::from_slice(slice).unwrap();
-    let mut map = HashMap::new();
+    let mut map = BTreeMap::new();
     map.insert(ObjectKey::String("message".to_string()), Value::String("pong".to_string()));
     assert_eq!(value, Value::Object(map))
 }
+
+#[test]
+fn test_object_determinism_roundtrip() {
+    let expected = b"\xa2aa\x01ab\x82\x02\x03";
+
+    // 0.1% chance of not catching failure
+    for _ in 0..10 {
+        assert_eq!(&to_vec(&de::from_slice::<Value>(expected).unwrap()).unwrap(), expected);
+    }
+}
diff --git a/tests/ser.rs b/tests/ser.rs
index 7adeef1..85daf16 100644
--- a/tests/ser.rs
+++ b/tests/ser.rs
@@ -1,7 +1,7 @@
 extern crate serde;
 extern crate serde_cbor;
 
-use std::collections::HashMap;
+use std::collections::BTreeMap;
 
 use serde::Serializer;
 use serde_cbor::{to_vec, from_slice};
@@ -21,7 +21,7 @@ fn test_list() {
 
 #[test]
 fn test_object() {
-    let mut object = HashMap::new();
+    let mut object = BTreeMap::new();
     object.insert("a".to_owned(), "A".to_owned());
     object.insert("b".to_owned(), "B".to_owned());
     object.insert("c".to_owned(), "C".to_owned());