Note [Casts and coercions in type comparision]
As (EQTYPE) in Note [Non-trivial definitional equality] says, our general plan, implemented by `fullEq`, is: (1) ignore both casts and coercions when comparing types, (2) instead, compare the /kinds/ of the two types, as well as the types themselves If possible we want to avoid step (2), comparing the kinds; doing so involves calling `typeKind` and doing another comparision. When can we avoid doing so? Answer: we can certainly avoid doing so if the types we are comparing have no casts or coercions. But we can do better. Consider eqType (TyConApp T [s1, ..., sn]) (TyConApp T [t1, .., tn]) We are going to call (eqType s1 t1), (eqType s2 t2) etc. The kinds of `s1` and `t1` must be equal, because these TyConApps are well-kinded, and both TyConApps are headed by the same T. So the first recursive call to `eqType` certainly doesn't need to check kinds. If that call returns False, we stop. Otherwise, we know that `s1` and `t1` are themselves equal (not just their kinds). This makes the kinds of `s2` and `t2` to be equal, because those kinds come from the kind of T instantiated with `s1` and `t1` -- which are the same. Thus we do not need to check the kinds of `s2` and `t2`. By induction, we don't need to check the kinds of *any* of the types in a TyConApp, and we also do not need to check the kinds of the TyConApps themselves. Conclusion: * casts and coercions under a TyConApp don't matter -- even including type synonyms * In step (2), use `hasCasts` to tell if there are any casts to worry about. It does not look very deep, because TyConApps and FunTys are so common, and it doesn't allocate. The only recursive cases are AppTy and ForAllTy. Alternative implementation. Instead of `hasCasts`, we could make the generic_eq_type function return data EqResult = NotEq | EqWithNoCasts | EqWithCasts Practically free; but stylistically I prefer useing `hasCasts`: * `generic_eq_type` can just uses familiar booleans * There is a lot more branching with the three-value variant. * It separates concerns. No need to think about cast-tracking when doing the equality comparison. * Indeed sometimes we omit the kind check unconditionally, so tracking it is just wasted work. I did try both; there was no perceptible perf difference so I chose `hasCasts` version.
References 1
- Non-trivial definitional equality GHC.Core.TyCo.Rep
Referenced by 1
- GHC.Core.TyCo.Compare call site