Skip to content

`Ord Literal` instance is non-deterministic

The Ord Literal instance is non-deterministic, because it uses uniqCompareFS to compare a FastString in LitLabel in the cmpLit function. That non-determinism propagates into the CoreMap implementation, which I'm pretty certain people expect to behave deterministically.

Given how rare FFI calls are, I suspect that this non-determinism is mostly of theoretical interest. Nevertheless I at least wanted to document it.

Proposal

Change the FastString field of LitLabel to LexicalFastString and use its Ord instance. Alternatively, replace uniqCompareFS with lexicalCompareFS.

Lexical comparison is O(n), but given the rarity of LitLabel it shouldn't matter much. Also we compare the ByteString in LitString lexically already, which I expect to occur much more often.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information