Skip to content
  • Richard Eisenberg's avatar
    Implement overlapping type family instances. · 7a42cf66
    Richard Eisenberg authored
    An ordered, overlapping type family instance is introduced by 'type
    instance
    where', followed by equations. See the new section in the user manual
    (7.7.2.2) for details. The canonical example is Boolean equality at the
    type
    level:
    
    type family Equals (a :: k) (b :: k) :: Bool
    type instance where
      Equals a a = True
      Equals a b = False
    
    A branched family instance, such as this one, checks its equations in
    order
    and applies only the first the matches. As explained in the note
    [Instance
    checking within groups] in FamInstEnv.lhs, we must be careful not to
    simplify,
    say, (Equals Int b) to False, because b might later unify with Int.
    
    This commit includes all of the commits on the overlapping-tyfams
    branch. SPJ
    requested that I combine all my commits over the past several months
    into one
    monolithic commit. The following GHC repos are affected: ghc, testsuite,
    utils/haddock, libraries/template-haskell, and libraries/dph.
    
    Here are some details for the interested:
    
    - The definition of CoAxiom has been moved from TyCon.lhs to a
      new file CoAxiom.lhs. I made this decision because of the
      number of definitions necessary to support BranchList.
    
    - BranchList is a GADT whose type tracks whether it is a
      singleton list or not-necessarily-a-singleton-list. The reason
      I introduced this type is to increase static checking of places
      where GHC code assumes that a FamInst or CoAxiom is indeed a
      singleton. This assumption takes place roughly 10 times
      throughout the code. I was worried that a future change to GHC
      would invalidate the assumption, and GHC might subtly fail to
      do the right thing. By explicitly labeling CoAxioms and
      FamInsts as being Unbranched (singleton) or
      Branched (not-necessarily-singleton), we make this assumption
      explicit and checkable. Furthermore, to enforce the accuracy of
      this label, the list of branches of a CoAxiom or FamInst is
      stored using a BranchList, whose constructors constrain its
      type index appropriately.
    
    I think that the decision to use BranchList is probably the most
    controversial decision I made from a code design point of view.
    Although I provide conversions to/from ordinary lists, it is more
    efficient to use the brList... functions provided in CoAxiom than
    always to convert. The use of these functions does not wander far
    from the core CoAxiom/FamInst logic.
    
    BranchLists are motivated and explained in the note [Branched axioms] in
    CoAxiom.lhs.
    
    - The CoAxiom type has changed significantly. You can see the new
      type in CoAxiom.lhs. It uses a CoAxBranch type to track
      branches of the CoAxiom. Correspondingly various functions
      producing and consuming CoAxioms had to change, including the
      binary layout of interface files.
    
    - To get branched axioms to work correctly, it is important to have a
      notion
      of type "apartness": two types are apart if they cannot unify, and no
      substitution of variables can ever get them to unify, even after type
    family
      simplification. (This is different than the normal failure to unify
    because
      of the type family bit.) This notion in encoded in tcApartTys, in
    Unify.lhs.
      Because apartness is finer-grained than unification, the tcUnifyTys
    now
      calls tcApartTys.
    
    - CoreLinting axioms has been updated, both to reflect the new
      form of CoAxiom and to enforce the apartness rules of branch
      application. The formalization of the new rules is in
      docs/core-spec/core-spec.pdf.
    
    - The FamInst type (in types/FamInstEnv.lhs) has changed
      significantly, paralleling the changes to CoAxiom. Of course,
      this forced minor changes in many files.
    
    - There are several new Notes in FamInstEnv.lhs, including one
      discussing confluent overlap and why we're not doing it.
    
    - lookupFamInstEnv, lookupFamInstEnvConflicts, and
      lookup_fam_inst_env' (the function that actually does the work)
      have all been more-or-less completely rewritten. There is a
      Note [lookup_fam_inst_env' implementation] describing the
      implementation. One of the changes that affects other files is
      to change the type of matches from a pair of (FamInst, [Type])
      to a new datatype (which now includes the index of the matching
      branch). This seemed a better design.
    
    - The TySynInstD constructor in Template Haskell was updated to
      use the new datatype TySynEqn. I also bumped the TH version
      number, requiring changes to DPH cabal files. (That's why the
      DPH repo has an overlapping-tyfams branch.)
    
    - As SPJ requested, I refactored some of the code in HsDecls:
    
     * splitting up TyDecl into SynDecl and DataDecl, correspondingly
       changing HsTyDefn to HsDataDefn (with only one constructor)
    
     * splitting FamInstD into TyFamInstD and DataFamInstD and
       splitting FamInstDecl into DataFamInstDecl and TyFamInstDecl
    
     * making the ClsInstD take a ClsInstDecl, for parallelism with
       InstDecl's other constructors
    
     * changing constructor TyFamily into FamDecl
    
     * creating a FamilyDecl type that stores the details for a family
       declaration; this is useful because FamilyDecls can appear in classes
    but
       other decls cannot
    
     * restricting the associated types and associated type defaults for a
     * class
       to be the new, more restrictive types
    
     * splitting cid_fam_insts into cid_tyfam_insts and cid_datafam_insts,
       according to the new types
    
     * perhaps one or two more that I'm overlooking
    
    None of these changes has far-reaching implications.
    
    - The user manual, section 7.7.2.2, is updated to describe the new type
      family
      instances.
    7a42cf66