Test Fwk: Add function for constructing an ScMap in order

[jonjove]

Semantically, an ScMap is an ordered structure to present efficient look-up. This is not encoded in the XDR of course, so it is possible to construct an ScMap out of order. Having encountered this issue yesterday, I feel confident it is (a) a foot-gun and (b) quite difficult to debug when it occurs.

Let's make it impossible--or at the very least difficult--to construct an ScMap out of order.

[leighmcculloch]

I don't think xdr libs can guarantee this, nor should they. We can add a helper function that maybe helps a user produce an ordered map, maybe, but that also introduces dependencies into the xdr lib that don't seem appropriate to live here.

I think it'll be unwise to also require this of all xdr libs, because what we're saying is that this logic will need replicated in a dozen languages.

We've already made intentional decisions to simplify the xdr representations of types, such as Symbol, so that SDKs do not need to know how to produce the bespoke formats we use within the host and I think map is a similar problem.

This issue really challenges the idea that maps should be lexicographically ordered. If the map was insertion ordered this problem wouldn't exist.

[jonjove]

Insertion ordered doesn't help. We're using maps for serialization, so they have to serialize in a predictable manner.

Without functionality to assist with this, using maps for serialization is very frustrating. I acknowledge it shouldn't necessarily be in this crate, but it should be somewhere.

[leighmcculloch]

We're using maps for serialization, so they have to serialize in a predictable manner.

The intent with insertion order is that the map is represented in the same order everywhere it exists. When it is created B,A,C, when it is serialized B,A,C, when it is deserialized B,A,C.

[jonjove]

But that means I have to know the order in which it was inserted, across different pieces of code. For example, the UDT code ends up "in order" as expected. So to match that anywhere else I would still have to insert it in order.... which is exactly the thing I'm trying to avoid because it requires that external knowledge.

Fundamentally, it's an ordered map. No matter how I insert the items it should have the same structure. If we don't want that, let's just go back to vectors.

[leighmcculloch]

I'm trying to avoid because it requires that external knowledge.

This isn't free and comes at a cost of trying to make a variety of SDKs all produce the same result.

Developers are already accustomed to placing fields in the correct order, because in most programming languages developers have to order arguments on functions in the correct order, so it's not clear to me why this is a unique challenge in this case.

[jonjove]

If we think that developers are accustomed to ordered fields, then let's just use vectors.

For context, here's the specific case that tripped me up: MessageV0 { nonce, domain, parameters }. When I wrote the serialization, I just went down the list of fields because I was writing into a map. So I inserted nonce, then domain, then parameters. But this isn't in alphabetical order, so it didn't match what the UDT code does. I'm aware of this now, and I doubt it will trip me up again. But it's a perfect foot-gun that will definitely not provide a positive experience.

[leighmcculloch]

In your case if maps were serialized in insertion order your intuition would have been correct.

In the XDR maps are just vectors already so I don't think there is anything to change there. In the host we are maybe being too clever by making them lexicographically ordered. For efficient lookup we should still probably load them into a map, but we could be using a map implementation that results in consistent roundtrip serialization of any XDR map.

[leighmcculloch]

Even if we switch UDTs to use the host vec, we run into this issue if anyone stores a map inside a vec, so I think we need to address this issue at the host map level.

[leighmcculloch]

@graydon Can maps in the host be changed to preserve the order of the entries in the original XDR array? By preserve the order, I mean that iterating the map should use the original order, inserting into the map should append to the order unless replacing the key, and serializing should use the iteration order.

[leighmcculloch]

I think this behavior to sort an ScMap belongs here in rs-stellar-xdr. I'll look into ways to present this in the API such that the ScMap type could never be not sorted.

[leighmcculloch]

@graydon did this in #112