Consider different stable map representations

There are several good options:

`IntMap`

Stick with an IntMap-backed representation, but use an unpacked non-empty list representation optimized for the no-collision case.

`HashMap`

Switch to a HashMap-backed representation. This should be considerably simpler, and will probably perform well.

Type fingerprints

At present, stable maps are very unsafe when used with GADTs or certain higher-rank types, because there's an assumption that stable name equality implies equality of the types of the stable names' underlying objects. This could be fixed (using either the IntMap or HashMap representation) by keying the map on both the stable name of the key and the fingerprint of its type's TypeRep. That burns a couple words per key, but it really seems like the Right Thing.

A super-legit version

newtype Map f = Map {unMap :: IntMap (NEL f)}
data SNTriple f = forall a. SNTriple !(TypeRep a) !(StableName a) (f a)
data NEL f
  = NELOne {-# UNPACK #-} !(SNTriple f)
  | NELCons {-# UNPACK #-} !(SNTriple f) (NEL f)

A lookup would search the bucket for something matching both the TypeRep and the StableName of the target, and there wouldn't need to be any unsafe coercions anywhere.

A more reasonable version

We really don't want or need to store a TypeRep in the map. We can quite easily write an API for type-indexed fingerprints that offers precisely what we need in the TypeRep interface but more compactly.

newtype Fingerprint a = Fingerprint GHC.Fingerprint.Fingerprint
  deriving (Eq, Ord, Show, Hashable)
type role Fingerprint nominal

fingerprint :: forall a. Typeable a => Fingerprint a
fingerprint = Fingerprint (typeRepFingerprint (typeRep @a))

eqFingerprint :: Fingerprint a -> Fingerprint b -> Maybe (a :~~: b)
eqFingerprint (Fingerprint a) (Fingerprint b)
  | a == b = unsafeCoerce (Just HRefl)
  | otherwise = Nothing

Replacing TypeRep a with Fingerprint a should make the map more compact.

For HashMap, we can't be quite so principled about types unless we want to reimplement HashMap, but that's okay.

data TaggedSN = TaggedSN {-# UNPACK #-} !GHC.Fingerprint.Fingerprint !DynStableName
  deriving (Eq, Ord)
instance Hashable TaggedSN where
  -- This should certainly use the stable name hash; it probably shouldn't use the
  -- type fingerprint hash, but if someone's doing a lot of really crazy stuff with nested
  -- types I guess that's an option.
  hashWithSalt s (TaggedSN fp sn) = ....
newtype Map f = Map {unMap :: HashMap TaggedSN (f Any)}

ekmett / stable-maps