Repository: near/borsh-rs (rust)

Issue:
BTreeMap serialization missing in 0.8.0 update
The ability to serialize BTreeMaps is suddenly missing in the new update, is this intentional?

https://docs.rs/borsh/0.7.1/src/borsh/ser/mod.rs.html#235-251 <- present
https://docs.rs/borsh/0.8.0/src/borsh/ser/mod.rs.html#235-251 <- missing

```
#[derive(BorshSerialize, BorshDeserialize)]
    |          ^^^^^^^^^^^^^^ the trait `BorshSerialize` is not implemented for `BTreeMap<std::string::String, Vec<Vec<u8>>>`
    |
    = help: see issue #48214
    = help: add `#![feature(trivial_bounds)]` to the crate attributes to enable
    = note: this error originates in a derive macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.
error: could not compile `test-program`
```

Pull request description:
feat: Added support for BTreeMap, BTreeSet, BinaryHeap, LinkedList types
*Resolves #5*

Patch:
diff --git a/borsh/src/de/mod.rs b/borsh/src/de/mod.rs
index 10243738..0116383e 100644
--- a/borsh/src/de/mod.rs
+++ b/borsh/src/de/mod.rs
@@ -7,7 +7,7 @@ use core::{
 use crate::maybestd::{
     borrow::{Borrow, Cow, ToOwned},
     boxed::Box,
-    collections::{BTreeMap, HashMap, HashSet},
+    collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque},
     format,
     io::{Error, ErrorKind, Result},
     string::{String, ToString},
@@ -290,6 +290,39 @@ where
     }
 }
 
+impl<T> BorshDeserialize for VecDeque<T>
+where
+    T: BorshDeserialize,
+{
+    #[inline]
+    fn deserialize(buf: &mut &[u8]) -> Result<Self> {
+        let vec = <Vec<T>>::deserialize(buf)?;
+        Ok(vec.into())
+    }
+}
+
+impl<T> BorshDeserialize for LinkedList<T>
+where
+    T: BorshDeserialize,
+{
+    #[inline]
+    fn deserialize(buf: &mut &[u8]) -> Result<Self> {
+        let vec = <Vec<T>>::deserialize(buf)?;
+        Ok(vec.into_iter().collect::<LinkedList<T>>())
+    }
+}
+
+impl<T> BorshDeserialize for BinaryHeap<T>
+where
+    T: BorshDeserialize + Ord,
+{
+    #[inline]
+    fn deserialize(buf: &mut &[u8]) -> Result<Self> {
+        let vec = <Vec<T>>::deserialize(buf)?;
+        Ok(vec.into_iter().collect::<BinaryHeap<T>>())
+    }
+}
+
 impl<T> BorshDeserialize for HashSet<T>
 where
     T: BorshDeserialize + Eq + Hash,
@@ -320,6 +353,17 @@ where
     }
 }
 
+impl<T> BorshDeserialize for BTreeSet<T>
+where
+    T: BorshDeserialize + Ord,
+{
+    #[inline]
+    fn deserialize(buf: &mut &[u8]) -> Result<Self> {
+        let vec = <Vec<T>>::deserialize(buf)?;
+        Ok(vec.into_iter().collect::<BTreeSet<T>>())
+    }
+}
+
 impl<K, V> BorshDeserialize for BTreeMap<K, V>
 where
     K: BorshDeserialize + Ord + core::hash::Hash,
diff --git a/borsh/src/ser/mod.rs b/borsh/src/ser/mod.rs
index 50627b92..35e65796 100644
--- a/borsh/src/ser/mod.rs
+++ b/borsh/src/ser/mod.rs
@@ -4,7 +4,7 @@ use core::mem::size_of;
 use crate::maybestd::{
     borrow::{Cow, ToOwned},
     boxed::Box,
-    collections::{HashMap, HashSet},
+    collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque},
     io::{ErrorKind, Result, Write},
     string::String,
     vec::Vec,
@@ -145,6 +145,24 @@ impl BorshSerialize for String {
     }
 }
 
+/// Helper method that is used to serialize a slice of data (without the length marker).
+#[inline]
+fn serialize_slice<T: BorshSerialize, W: Write>(data: &[T], writer: &mut W) -> Result<()> {
+    if T::is_u8() && size_of::<T>() == size_of::<u8>() {
+        // The code below uses unsafe memory representation from `&[T]` to `&[u8]`.
+        // The size of the memory should match because `size_of::<T>() == size_of::<u8>()`.
+        //
+        // `T::is_u8()` is a workaround for not being able to implement `Vec<u8>` separately.
+        let buf = unsafe { core::slice::from_raw_parts(data.as_ptr() as *const u8, data.len()) };
+        writer.write_all(buf)?;
+    } else {
+        for item in data {
+            item.serialize(writer)?;
+        }
+    }
+    Ok(())
+}
+
 impl<T> BorshSerialize for [T]
 where
     T: BorshSerialize,
@@ -154,20 +172,7 @@ where
         writer.write_all(
             &(u32::try_from(self.len()).map_err(|_| ErrorKind::InvalidInput)?).to_le_bytes(),
         )?;
-        if T::is_u8() && size_of::<T>() == size_of::<u8>() {
-            // The code below uses unsafe memory representation from `&[T]` to `&[u8]`.
-            // The size of the memory should match because `size_of::<T>() == size_of::<u8>()`.
-            //
-            // `T::is_u8()` is a workaround for not being able to implement `Vec<u8>` separately.
-            let buf =
-                unsafe { core::slice::from_raw_parts(self.as_ptr() as *const u8, self.len()) };
-            writer.write_all(buf)?;
-        } else {
-            for item in self {
-                item.serialize(writer)?;
-            }
-        }
-        Ok(())
+        serialize_slice(self, writer)
     }
 }
 
@@ -198,6 +203,56 @@ where
     }
 }
 
+impl<T> BorshSerialize for VecDeque<T>
+where
+    T: BorshSerialize,
+{
+    #[inline]
+    fn serialize<W: Write>(&self, writer: &mut W) -> Result<()> {
+        writer.write_all(
+            &(u32::try_from(self.len()).map_err(|_| ErrorKind::InvalidInput)?).to_le_bytes(),
+        )?;
+        let slices = self.as_slices();
+        serialize_slice(slices.0, writer)?;
+        serialize_slice(slices.1, writer)
+    }
+}
+
+impl<T> BorshSerialize for LinkedList<T>
+where
+    T: BorshSerialize,
+{
+    #[inline]
+    fn serialize<W: Write>(&self, writer: &mut W) -> Result<()> {
+        writer.write_all(
+            &(u32::try_from(self.len()).map_err(|_| ErrorKind::InvalidInput)?).to_le_bytes(),
+        )?;
+        for item in self {
+            item.serialize(writer)?;
+        }
+        Ok(())
+    }
+}
+
+impl<T> BorshSerialize for BinaryHeap<T>
+where
+    T: BorshSerialize,
+{
+    #[inline]
+    fn serialize<W: Write>(&self, writer: &mut W) -> Result<()> {
+        // It could have been just `self.as_slice().serialize(writer)`, but there is no
+        // `as_slice()` method:
+        // https://internals.rust-lang.org/t/should-i-add-as-slice-method-to-binaryheap/13816
+        writer.write_all(
+            &(u32::try_from(self.len()).map_err(|_| ErrorKind::InvalidInput)?).to_le_bytes(),
+        )?;
+        for item in self {
+            item.serialize(writer)?;
+        }
+        Ok(())
+    }
+}
+
 impl<K, V> BorshSerialize for HashMap<K, V>
 where
     K: BorshSerialize + PartialOrd,
@@ -236,6 +291,45 @@ where
     }
 }
 
+impl<K, V> BorshSerialize for BTreeMap<K, V>
+where
+    K: BorshSerialize,
+    V: BorshSerialize,
+{
+    #[inline]
+    fn serialize<W: Write>(&self, writer: &mut W) -> Result<()> {
+        // NOTE: BTreeMap iterates over the entries that are sorted by key, so the serialization
+        // result will be consistent without a need to sort the entries as we do for HashMap
+        // serialization.
+        u32::try_from(self.len())
+            .map_err(|_| ErrorKind::InvalidInput)?
+            .serialize(writer)?;
+        for (key, value) in self {
+            key.serialize(writer)?;
+            value.serialize(writer)?;
+        }
+        Ok(())
+    }
+}
+
+impl<T> BorshSerialize for BTreeSet<T>
+where
+    T: BorshSerialize,
+{
+    #[inline]
+    fn serialize<W: Write>(&self, writer: &mut W) -> Result<()> {
+        // NOTE: BTreeSet iterates over the items that are sorted, so the serialization result will
+        // be consistent without a need to sort the entries as we do for HashSet serialization.
+        u32::try_from(self.len())
+            .map_err(|_| ErrorKind::InvalidInput)?
+            .serialize(writer)?;
+        for item in self {
+            item.serialize(writer)?;
+        }
+        Ok(())
+    }
+}
+
 #[cfg(feature = "std")]
 impl BorshSerialize for std::net::SocketAddr {
     #[inline]


Test patch:
diff --git a/borsh/tests/test_binary_heaps.rs b/borsh/tests/test_binary_heaps.rs
new file mode 100644
index 00000000..5ec6cd41
--- /dev/null
+++ b/borsh/tests/test_binary_heaps.rs
@@ -0,0 +1,30 @@
+use borsh::maybestd::collections::BinaryHeap;
+use borsh::{BorshDeserialize, BorshSerialize};
+
+macro_rules! test_binary_heap {
+    ($v: expr, $t: ty) => {
+        let buf = $v.try_to_vec().unwrap();
+        let actual_v: BinaryHeap<$t> =
+            BorshDeserialize::try_from_slice(&buf).expect("failed to deserialize");
+        assert_eq!(actual_v.into_vec(), $v.into_vec());
+    };
+}
+
+macro_rules! test_binary_heaps {
+    ($test_name: ident, $el: expr, $t: ty) => {
+        #[test]
+        fn $test_name() {
+            test_binary_heap!(BinaryHeap::<$t>::new(), $t);
+            test_binary_heap!(vec![$el].into_iter().collect::<BinaryHeap<_>>(), $t);
+            test_binary_heap!(vec![$el; 10].into_iter().collect::<BinaryHeap<_>>(), $t);
+            test_binary_heap!(vec![$el; 100].into_iter().collect::<BinaryHeap<_>>(), $t);
+            test_binary_heap!(vec![$el; 1000].into_iter().collect::<BinaryHeap<_>>(), $t);
+            test_binary_heap!(vec![$el; 10000].into_iter().collect::<BinaryHeap<_>>(), $t);
+        }
+    };
+}
+
+test_binary_heaps!(test_binary_heap_u8, 100u8, u8);
+test_binary_heaps!(test_binary_heap_i8, 100i8, i8);
+test_binary_heaps!(test_binary_heap_u32, 1000000000u32, u32);
+test_binary_heaps!(test_binary_heap_string, "a".to_string(), String);
diff --git a/borsh/tests/test_simple_structs.rs b/borsh/tests/test_simple_structs.rs
index 9b0826ef..deb74985 100644
--- a/borsh/tests/test_simple_structs.rs
+++ b/borsh/tests/test_simple_structs.rs
@@ -1,4 +1,4 @@
-use borsh::maybestd::collections::{HashMap, HashSet};
+use borsh::maybestd::collections::{BTreeMap, BTreeSet, HashMap, HashSet, LinkedList, VecDeque};
 use borsh::{BorshDeserialize, BorshSerialize};
 
 #[derive(BorshSerialize, BorshDeserialize, PartialEq, Debug)]
@@ -11,6 +11,10 @@ struct A<'a> {
     t: (String, u64),
     m: HashMap<String, String>,
     s: HashSet<u64>,
+    btree_map_string: BTreeMap<String, String>,
+    btree_set_u64: BTreeSet<u64>,
+    linked_list_string: LinkedList<String>,
+    vec_deque_u64: VecDeque<u64>,
     v: Vec<String>,
     w: Box<[u8]>,
     box_str: Box<str>,
@@ -89,6 +93,10 @@ fn test_simple_struct() {
         t: ("Hello".to_string(), 10),
         m: map.clone(),
         s: set.clone(),
+        btree_map_string: map.clone().into_iter().collect(),
+        btree_set_u64: set.clone().into_iter().collect(),
+        linked_list_string: vec!["a".to_string(), "b".to_string()].into_iter().collect(),
+        vec_deque_u64: vec![1, 2, 3].into_iter().collect(),
         v: vec!["qwe".to_string(), "zxc".to_string()],
         w: vec![0].into_boxed_slice(),
         box_str: Box::from("asd"),
@@ -117,6 +125,10 @@ fn test_simple_struct() {
         t: ("Hello".to_string(), 10),
         m: map.clone(),
         s: set.clone(),
+        btree_map_string: map.clone().into_iter().collect(),
+        btree_set_u64: set.clone().into_iter().collect(),
+        linked_list_string: vec!["a".to_string(), "b".to_string()].into_iter().collect(),
+        vec_deque_u64: vec![1, 2, 3].into_iter().collect(),
         v: a.v.clone(),
         w: a.w.clone(),
         box_str: Box::from("asd"),