We often want to make top-level auxiliary bindings in derived instances.
For example, derived Ix instances sometimes generate code like this:
data T = ...
deriving instance Ix T
==>
instance Ix T where
range (a, b) = map tag2con_T [dataToTag# a .. dataToTag# b]
$tag2con_T :: Int -> T
$tag2con_T = ...code....
Note that multiple instances of the same type might need to use the same sort
of auxiliary binding. For example, $tag2con is used not only in derived Ix
instances, but also in derived Enum instances:
deriving instance Enum T
==>
instance Enum T where
toEnum i = tag2con_T i
$tag2con_T :: Int -> T
$tag2con_T = ...code....
How do we ensure that the two usages of $tag2con_T do not conflict with each
other? We do so by generating a separate $tag2con_T definition for each
instance, giving each definition an Exact RdrName with a separate Unique to
avoid name clashes:
instance Ix T where
range (a, b) = map tag2con_T{Uniq2} [dataToTag# a .. dataToTag# b]
instance Enum T where
toEnum a = $tag2con_T{Uniq2} a
$tag2con_T{Uniq1} and $tag2con_T{Uniq2} are Exact RdrNames with
underlying System Names
$tag2con_T{Uniq1} :: Int -> T
$tag2con_T{Uniq1} = ...code....
$tag2con_T{Uniq2} :: Int -> T
$tag2con_T{Uniq2} = ...code....
Note that:
* This is /precisely/ the same mechanism that we use for
Template Haskell–generated code.
See Note [Binders in Template Haskell] in GHC.ThToHs.
There we explain why we use a 'System' flavour of the Name we generate.
* See "Wrinkle: Reducing code duplication" for how we can avoid generating
lots of duplicated code in common situations.
* See "Wrinkle: Why we sometimes do generated duplicate code" for why this
de-duplication mechanism isn't perfect, so we fall back to CSE
(which is very effective within a single module).
* Note that the "_T" part of "$tag2con_T" is just for debug-printing
purposes. We could call them all "$tag2con", or even just "aux".
The Unique is enough to keep them separate.
This is important: we might be generating an Eq instance for two
completely-distinct imported type constructors T.
At first glance, it might appear that this plan is infeasible, as it would
require generating multiple top-level declarations with the same OccName. But
what if auxiliary bindings /weren't/ top-level? Conceptually, we could imagine
that auxiliary bindings are /local/ to the instance declarations in which they
are used. Using some hypothetical Haskell syntax, it might look like this:
let {
$tag2con_T{Uniq1} :: Int -> T
$tag2con_T{Uniq1} = ...code....
$tag2con_T{Uniq2} :: Int -> T
$tag2con_T{Uniq2} = ...code....
} in {
instance Ix T where
range (a, b) = map tag2con_T{Uniq2} [dataToTag# a .. dataToTag# b]
instance Enum T where
toEnum a = $tag2con_T{Uniq2} a
}
Making auxiliary bindings local is key to making this work, since GHC will
not reject local bindings with duplicate names provided that:
* Each binding has a distinct unique, and
* Each binding has an Exact RdrName with a System Name.
Even though the hypothetical Haskell syntax above does not exist, we can
accomplish the same end result through some sleight of hand in renameDeriv:
we rename auxiliary bindings with rnLocalValBindsLHS. (If we had used
rnTopBindsLHS instead, then GHC would spuriously reject auxiliary bindings
with the same OccName as duplicates.) Luckily, no special treatment is needed
to typecheck them; we can typecheck them as normal top-level bindings
(using tcTopBinds) without danger.
Wrinkle: Reducing code duplication
While the approach of generating copies of each sort of auxiliary binder per
derived instance is simpler, it can lead to code bloat if done naïvely.
Consider this example:
data T = ...
deriving instance Eq T
deriving instance Ord T
==>
instance Ix T where
range (a, b) = map tag2con_T{Uniq2} [dataToTag# a .. dataToTag# b]
instance Enum T where
toEnum a = $tag2con_T{Uniq2} a
$tag2con_T{Uniq1} :: Int -> T
$tag2con_T{Uniq1} = ...code....
$tag2con_T{Uniq2} :: Int -> T
$tag2con_T{Uniq2} = ...code....
$tag2con_T{Uniq1} and $tag2con_T{Uniq2} are blatant duplicates of each other,
which is not ideal. Surely GHC can do better than that at the very least! And
indeed it does. Within the genAuxBinds function, GHC performs a small CSE-like
pass to define duplicate auxiliary binders in terms of the original one. On
the example above, that would look like this:
$tag2con_T{Uniq1} :: Int -> T
$tag2con_T{Uniq1} = ...code....
$tag2con_T{Uniq2} :: Int -> T
$tag2con_T{Uniq2} = $tag2con_T{Uniq1}
(Note that this pass does not cover all possible forms of code duplication.
See "Wrinkle: Why we sometimes do generate duplicate code" for situations
where genAuxBinds does not deduplicate code.)
To start, genAuxBinds is given a list of AuxBindSpecs, which describe the sort
of auxiliary bindings that must be generates along with their RdrNames. As
genAuxBinds processes this list, it marks the first occurrence of each sort of
auxiliary binding as the "original". For example, if genAuxBinds sees a
DerivCon2Tag for the first time (with the RdrName $tag2con_T{Uniq1}), then it
will generate the full code for a $tag2con binding:
$tag2con_T{Uniq1} :: Int -> T
$tag2con_T{Uniq1} = ...code....
Later, if genAuxBinds sees any additional DerivCon2Tag values, it will treat
them as duplicates. For example, if genAuxBinds later sees a DerivCon2Tag with
the RdrName $tag2con_T{Uniq2}, it will generate this code, which is much more
compact:
$tag2con_T{Uniq2} :: Int -> T
$tag2con_T{Uniq2} = $tag2con_T{Uniq1}
An alternative approach would be /not/ performing any kind of deduplication in
genAuxBinds at all and simply relying on GHC's simplifier to perform this kind
of CSE. But this is a more expensive analysis in general, while genAuxBinds can
accomplish the same result with a simple check.
Wrinkle: Why we sometimes do generate duplicate code
It is worth noting that deduplicating auxiliary binders is difficult in the
general case. Here are two particular examples where GHC cannot easily remove
duplicate copies of an auxiliary binding:
1. When derived instances are contained in different modules, as in the
following example:
module A where
data T = ...
module B where
import A
deriving instance Ix T
module C where
import B
deriving instance Enum T
The derived Eq and Enum instances for T make use of $tag2con_T, and since
they are defined in separate modules, each module must produce its own copy
of $tag2con_T.
2. When derived instances are separated by TH splices (#18321), as in the
following example:
module M where
data T = ...
deriving instance Ix T
$(pure [])
deriving instance Enum T
Due to the way that GHC typechecks TyClGroups, genAuxBinds will run twice
in this program: once for all the declarations before the TH splice, and
once again for all the declarations after the TH splice. As a result,
$tag2con_T will be generated twice, since genAuxBinds will be unable to
recognize the presence of duplicates.
These situations are much rarer, so we do not spend any effort to deduplicate
auxiliary bindings there. Instead, we focus on the common case of multiple
derived instances within the same module, not separated by any TH splices.
(This is the case described in "Wrinkle: Reducing code duplication".) In
situation (1), we can at least fall back on GHC's simplifier to pick up
genAuxBinds' slack.