Template Haskell determinism

[Bartosz Nitka]

Template Haskell with its ability to do arbitrary IO is non-deterministic by
design. You could for example embed the current date in a file. There is
however one kind of non-deterministic behavior that you can trigger
accidentally. It has to do with how Names are reified. If you take a look
at
the definition of reifyName you can see that it puts the assigned Unique in
a
NameU:

  reifyName :: NamedThing n => n -> TH.Name
  reifyName thing
    | isExternalName name = mk_varg pkg_str mod_str occ_str
    | otherwise           = TH.mkNameU occ_str (getKey (getUnique name))
    ...
NameFlavour which NameU is a constructor of has a default Ord instance,
meaning
that it ends up comparing the Uniques. The relative ordering of Uniques is
not
guaranteed to be stable across recompilations [1], so this can lead to
ABI-incompatible binaries.

This isn't an abstract problem and it actually happens in practice. The
microlens package keeps Names in a Set and later turns that set into a list.
The results have different orders of TyVars resulting in different ABI
hashes
and can potentially be optimized differently.

I believe it's worth to handle this case in a deterministic way and I have a
solution in mind. The idea is to extend NameU (and potentially NameL) with
an
ordering key. To be more concrete:

-   | NameU !Int
+   | NameU !Int !Int

This way the Ord instance can use a stable key and the problem reduces to
ensuring the keys are stable. To generate stable keys we can use the fact
that
reify traverses the expressions in the same order every time and
sequentially
allocate new keys based on traversal order. The way I have it implemented
now
is to add a new field in TcGblEnv which maps Uniques to allocated keys:

+        tcg_th_names :: TcRef (UniqFM Int, Int),

Then the reifyName and qNewName do the necessary bookkeeping and translate
the
Uniques on the fly.

This is a breaking change and it doesn't fix the problem that NameFlavour is
not abstract and leaks the Uniques. It would break at least:

- singletons
- th-lift
- haskell-src-meta
- shakespeare
- distributed-closure

I'd like to get feedback if this is an acceptable solution and if the
problem
is worth solving.

Cheers,
Bartosz

[1]
https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20160531/a88bb92d/attachment.html>