Make Ord TH.Name deterministic
Needs RevisionPublic

Authored by niteria on Jun 1 2016, 8:50 AM.

Details

Summary

Currently the Uniques leak into the TH.NameU making Ord TH.Name
nondeterministic. This makes the microlens library generate
nondeterministic lenses because they keep TH.Names in a set
and then turn it into a list.

To fix it I've added an additional ordering key to NameU as
described in Note [Template Haskell name translation].

This change:

  • refactors the reify step to make reifyName monadic giving access to the env
  • extends NameU to hold an ordering key
  • remembers the Unique -> ordering key mapping in TcGblEnv
  • hooks a translation step in qNewName and reifyName
  • adds a testcase that demonstrates the problem

This is a breaking change that will break at least:

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

There are some things I'm not sure about:

  • is TcGblEnv really the best place to keep the state?
  • do we need the same thing for NameL? I think we don't because these names are already stable
  • this changes the TH library, do I need to document it somewhere?
Test Plan

./validate + new test

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 9871
Build 11916: arc lint + arc unit
niteria updated this revision to Diff 7802.Jun 1 2016, 8:50 AM
niteria retitled this revision from to Make Ord TH.Name deterministic.
niteria updated this object.
niteria edited the test plan for this revision. (Show Details)
niteria added reviewers: simonpj, goldfire, simonmar, bgamari.
niteria updated the Trac tickets for this revision.
goldfire accepted this revision.Jun 1 2016, 10:03 AM
goldfire edited edge metadata.

LGTM. :)

This revision is now accepted and ready to land.Jun 1 2016, 10:03 AM
  • this changes the TH library, do I need to document it somewhere?

I think it deserves a mention in the template-haskell changelog, at the very least.

simonpj edited edge metadata.Jun 2 2016, 6:06 AM

Is the new unique supply required to survive between splices, or could you re-start it for each splice? (In which case we could consider layering a monad on top of TcM to contain the counter.) If it is required to persist, can you give an example? Plainly it can't persist across modules so I'd be surprised if it mattered.

compiler/typecheck/TcRnMonad.hs
1382

See TcSplice.reifyName

1391

Point to the regression-suite test case that is a small example.

compiler/typecheck/TcRnTypes.hs
470

Is the Int the first free one or the last used one? Comment should say.

simonmar edited edge metadata.Jun 10 2016, 7:15 AM

Since you already need a mapping from Unique->ordKey in the TcGblEnv, why not use the ordKey as the Unique in NameU? I'm not getting why you need to have two fields here.

The idea is to keep GHC's Uniques hidden, and give the TH code deterministic uniques instead.

Since you already need a mapping from Unique->ordKey in the TcGblEnv, why not use the ordKey as the Unique in NameU? I'm not getting why you need to have two fields here.

The idea is to keep GHC's Uniques hidden, and give the TH code deterministic uniques instead.

That's a great question, I too thought I can hide the Uniques. If you take a look at thRdrName [1] we need the Unique to create a RdrName. Since we have the mapping in the some global env in theory we should be able to do it. The problem is that thRdrName has no access to that env, so don't its callers and even the CvtM doesn't have access. I don't know how much I would need to change to make this possible.

[1] https://phabricator.haskell.org/diffusion/GHC/browse/master/compiler/hsSyn/Convert.hs;47d81732022e0327f7a5798898b40d1f1bdbb157$1432

Fair enough. I think it would be worth mentioning that design constraint next to`NameU`, for curious people like me: something like "the Unique lets GHC convert a NameU directly back to a RdrName, but it is not deterministic, so the ordKey provides a deterministic ordering. ordKey determines Unique, but caching the Unique here makes it easier to convert back without having to plumb a Unique to ordKey mapping around."

Otherwise I'm fine with this if other people are too. But this API change might make it difficult to backport to 8.0.2, no?

bgamari requested changes to this revision.Jun 18 2016, 5:20 AM
bgamari edited edge metadata.

@niteria, I think @simonpj brought up a few good points in his comments. Would you mind addressing these?

This revision now requires changes to proceed.Jun 18 2016, 5:20 AM
austin resigned from this revision.Nov 9 2017, 9:43 AM