Need to note unordering-ge for Map/Hash/QuantHash/Bag/Set/Mix/BagHah/SetHash/MixHash

[zoffixznet]

<Altreus> Hmm, the docs for Hash don't say whether order is preserved.

I don't know if the spec guarantees that the hashy types are unordered, but that info should probably mentioned (if it's not part of spec, then maybe say that some implementation keep it unordered?)

Also, it should be noted somewhere that some methods like .Str, .gist, and .perl do sort the hashy type (this is only partially implemented by Rakudo; filed as R#131244).

[labster]

Given that Rakudo used to randomize Hash keys on purpose back when we used an ordered implementation, I think we can assume that the intent is for Hash types not to preserve order.

[jnthn]

Given it's security that is driving the randomization, it might be reasonable for the spec to guarantee it.

[samcv]

From my perspective:

Hashes are not guaranteed to retain order, in fact the user should not expect it to. But I also don't think that we should have the spec guarentee that it is randomized.

I see it as an implementation detail.

Essentially the issue that randomization solves for us is revealing information about how the hash is laid out in memory and which hashes end up in which buckets. If an attacker can know insertion order (which we assume they know since they are inserting keys) plus the order of iteration, they can figure out which items are in the same buckets.

Whereas if an implementation retained insertion order then iteration order would only reveal insertion order which an attacker would already know (they are the one inserting the keys).

So things must either be ordered by either insertion order, or sufficiently randomized. In between reveals information we don't want to provide.

Both ruby and python in their latest versions have an implementation that retains insertion order. Although it is not quite as fast as an implementation that does not worry about insertion order, we should keep in mind that there may be VM's/runtimes Perl 6 may run on and they may have insertion order retention.

[cfa]

The title of this issue is confusing (what does "unordering-ge" mean?).

Anyway, here's what I found after a quick skim of the docs:

• Map: "Note that the order in which keys, values and pairs are retrieved is generally arbitrary, but the keys, values and pairs methods return them always in the same order when called on the same object."
• Hash: "Although the order of the hashes is guaranteed to be random in every single call, still successive calls to .keys and .values are guaranteed to return them in the same order…"
  • Question: is "guaranteed to be random" definitely the case? CC @lizmat
• QuantHash seems to be lacking mention of ordering.
  • I'm not sure how relevant it is here? CC @lizmat
• Bag: "A Bag is an immutable bag/multiset implementing Associative, meaning a collection of distinct elements in no particular order…"
• BagHash: "A BagHash is a mutable bag/multiset, meaning a collection of distinct items in no particular order…"
• Mix: "A Mix is an immutable collection of distinct elements in no particular order"
• Set: "A Set is an immutable set, meaning a collection of distinct elements in no particular order"
• SetHash: "A SetHash is a mutable set, meaning a collection of distinct elements in no particular order."
• MixHash: "A MixHash is a mutable mix, meaning a collection of distinct elements in no particular order"

[coke]

The title of this issue is confusing (what does "unordering-ge" mean?).

Turning it into a noun, just "the fact that it is not ordered." (I would have used -age, like package)