Order of IndexMap is not restored with some serde implementations

[emilk]

When using flexbuffers the order of IndexMap is not restored on deserialize.

I am not sure if this should be considered a bug in flexbuffers, a bug in indexmap or a shortcoming of serde. The implementation of serse::Serialize for IndexMap uses serialize_map which does not specify if the keys should keep the order.

Maybe IndexMap should use serialize_seq instead, i.e. encode a map as an array of key-value pairs?

Related issues

google/flatbuffers#6120

Reproduce

with indexmap = { version = "=1.6.0", features = ["serde-1"] }:

use indexmap::IndexMap;
fn main() {
    let mut map = IndexMap::new();
    map.insert("b".to_owned(), 1_i32);
    map.insert("a".to_owned(), 0_i32);
    let flex = flexbuffers::to_vec(&map).unwrap();
    let back: IndexMap<String, i32> = flexbuffers::from_slice(&flex).unwrap();
    assert_eq!(map.keys().collect::<Vec<_>>(), back.keys().collect::<Vec<_>>());
}

This fails with

  left: `["b", "a"]`,
 right: `["a", "b"]`', src/main.rs:8:5

[cuviper]

It seems the FlexBuffers spec requires this:

Both the keys and corresponding values have to be stored in sorted order (as determined by strcmp), such that lookups can be made using binary search.

However, I don't think we should use serialize_seq instead, at least not by default. For one, that would totally lose the map-like representation in formats like JSON -- instead of an Object we would get an Array. It would also break compatibility to change the serialized format at all, as this is an ABI of sorts -- old clients would lose the ability to read newly serialized maps. (It's possible to make new clients understand it either way.)

Maybe we could offer ordered helper functions instead, the same way we did "untagged" support for Either. So we would add a module like serde_ordered that treats the map like a sequence, and this could be tagged on specific fields like #[serde(with = "indexmap::serde_ordered")].

---

IndexSet is already treated as a sequence, so we should be fine there.