[rust] flexbuffers doesn't keep the order of IndexMap

[emilk]

indexmap is a crate which provides the type IndexMap, which is an order-preserving map. When encoding it with JSON, the order is restored. However, not with flexbuffers.

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.

I am not familiar with how flexbuffer encodes maps, but could it be made to preserve order somehow?

Related issues

indexmap-rs/indexmap#156

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

[aardappel]

@rw @CasperN

[CasperN]

Unfortunately, I think this is intended behavior.

The keys vector [of a map] is a typed vector of keys. 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.

https://google.github.io/flatbuffers/flatbuffers_internals.html

(unless indexmap could be serialized as something besides a flexbuffers map)

[cuviper]

I think we want the default for IndexMap to be a normal map, despite ordering concerns, but I'm offering an alternative in indexmap-rs/indexmap#158 to write it as a sequence. Do you have any opinion whether it would be better to have a sequence of (key, value) tuples, or a flat heterogeneous sequence of key, value, ...? Or I suppose we could also have separate sequences of keys and values, which looks like how flexbuffers represents its native maps.

[CasperN]

you'd probably have to take a lot of serialization formats into account if you want to change how indexmap interacts with Serde, but for Flexbuffers, I think a flat heterogenous sequence of [k1,v1,k2,v2,...] would be best.

Separate sequences would be more efficient if all the keys or values are the same FlexbufferType (basically int, uint, str, bool), so we won't store type information - but I wouldn't expect that to be generally true.