<div dir="ltr"><div>+1 to solving this. Not sure about the approach, but assuming the following concerns are addressed, I'm (+1) on it too:</div><div><br></div><div>This solution is clever! However, I think there is some difficulty to determining this ordering key. Namely, what happens when I construct the (Set Name) using results from multiple reifies?</div><div><br></div><div>One solution is to have the ordering key be a consecutive supply that's initialized on a per-module basis. There is still an issue there, though, which is that you might store one of these names in a global IORef that's used by a later TH splice. Or, similarly, serialize the names to a file and later load them. At least in those cases you need to use 'runIO' to break determinism.</div><div><br></div><div>If names get different ordering keys when reified from different modules (seems like they'd have to, particularly given ghc's "-j"), then we end up with an unpleasant circumstance where these do not compare as equal. How about having the Eq instance ignore the ordering key? I think that mostly resolves this concern. This implies that the Ord instance should also yield EQ and ignore the ordering key, when the unique key matches.</div><div><br></div><div>One issue with this is that switching the order of reify could unexpectedly vary the behavior.</div><div><br></div><div>Does the map in TcGblEnv imply that a reify from a later module will get the same ordering key? So does this mean that the keys used in a given reify depend on which things have already been reified? In that case, then this is also an issue with your solution. Now, it's not a big problem at all, just surprising to the user.</div><div><br></div><div><br></div><div>If the internal API for Name does change, may as well address <a href="https://ghc.haskell.org/trac/ghc/ticket/10311">https://ghc.haskell.org/trac/ghc/ticket/10311</a> too. I agree with SPJ's suggested solution of having both the traditional package identifier and package keys in 'Name'. </div><div><br></div><div>-Michael</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 31, 2016 at 6:54 AM, Bartosz Nitka <span dir="ltr"><<a href="mailto:niteria@gmail.com" target="_blank">niteria@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Template Haskell with its ability to do arbitrary IO is non-deterministic by</div><div>design. You could for example embed the current date in a file. There is</div><div>however one kind of non-deterministic behavior that you can trigger </div><div>accidentally. It has to do with how Names are reified. If you take a look at </div><div>the definition of reifyName you can see that it puts the assigned Unique in a</div><div>NameU:</div><div><br></div><div> reifyName :: NamedThing n => n -> TH.Name</div><div> reifyName thing</div><div> | isExternalName name = mk_varg pkg_str mod_str occ_str</div><div> | otherwise = TH.mkNameU occ_str (getKey (getUnique name))</div><div> ...</div><div><span style="white-space:pre-wrap"> </span></div><div>NameFlavour which NameU is a constructor of has a default Ord instance, meaning</div><div>that it ends up comparing the Uniques. The relative ordering of Uniques is not</div><div>guaranteed to be stable across recompilations [1], so this can lead to </div><div>ABI-incompatible binaries.</div><div><br></div><div>This isn't an abstract problem and it actually happens in practice. The </div><div>microlens package keeps Names in a Set and later turns that set into a list.</div><div>The results have different orders of TyVars resulting in different ABI hashes</div><div>and can potentially be optimized differently.</div><div><br></div><div>I believe it's worth to handle this case in a deterministic way and I have a</div><div>solution in mind. The idea is to extend NameU (and potentially NameL) with an</div><div>ordering key. To be more concrete:</div><div><br></div><div>- | NameU !Int</div><div>+ | NameU !Int !Int</div><div><br></div><div>This way the Ord instance can use a stable key and the problem reduces to</div><div>ensuring the keys are stable. To generate stable keys we can use the fact that</div><div>reify traverses the expressions in the same order every time and sequentially</div><div>allocate new keys based on traversal order. The way I have it implemented now </div><div>is to add a new field in TcGblEnv which maps Uniques to allocated keys:</div><div><br></div><div>+ tcg_th_names :: TcRef (UniqFM Int, Int),</div><div><br></div><div>Then the reifyName and qNewName do the necessary bookkeeping and translate the</div><div>Uniques on the fly.</div><div><br></div><div>This is a breaking change and it doesn't fix the problem that NameFlavour is</div><div>not abstract and leaks the Uniques. It would break at least:</div><div><br></div><div>- singletons</div><div>- th-lift</div><div>- haskell-src-meta</div><div>- shakespeare</div><div>- distributed-closure</div><div><br></div><div>I'd like to get feedback if this is an acceptable solution and if the problem</div><div>is worth solving.</div><div><br></div><div>Cheers,</div><div>Bartosz</div><div><br></div><div>[1] <a href="https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques" target="_blank">https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques</a></div></div>
<br>_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
<br></blockquote></div><br></div>