+ find [] ms us = (ms, us)
+ find (item@(tpl_tyvars, tpl, dfun_id) : rest) ms us
+ = case tcMatchTys tpl_tyvars tpl key_tys of
+ Just subst -> find rest ((subst,item):ms) us
+ Nothing
+ -- Does not match, so next check whether the things unify
+ -- [see notes about overlapping instances above]
+ -> ASSERT2( not (tyVarsOfTypes key_tys `intersectsVarSet` tpl_tyvars),
+ (ppr key_cls <+> ppr key_tys <+> ppr key_all_tvs) $$
+ (ppr dfun_id <+> ppr tpl_tyvars <+> ppr tpl)
+ )
+ -- Unification will break badly if the variables overlap
+ -- They shouldn't because we allocate separate uniques for them
+ case tcUnifyTys bind_fn tpl key_tys of
+ Just _ -> find rest ms (dfun_id:us)
+ Nothing -> find rest ms us
+
+ bind_fn tv | isTcTyVar tv && isExistentialTyVar tv = Skolem
+ | otherwise = BindMe
+ -- The key_tys can contain skolem constants, and we can guarantee that those
+ -- are never going to be instantiated to anything, so we should not involve
+ -- them in the unification test. Example:
+ -- class Foo a where { op :: a -> Int }
+ -- instance Foo a => Foo [a] -- NB overlap
+ -- instance Foo [Int] -- NB overlap
+ -- data T = forall a. Foo a => MkT a
+ -- f :: T -> Int
+ -- f (MkT x) = op [x,x]
+ -- The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd
+ -- complain, saying that the choice of instance depended on the instantiation
+ -- of 'a'; but of course it isn't *going* to be instantiated.
+ --
+ -- We do this only for pattern-bound skolems. For example we reject
+ -- g :: forall a => [a] -> Int
+ -- g x = op x
+ -- on the grounds that the correct instance depends on the instantiation of 'a'
+
+insert_overlapping :: (TvSubst, InstEnvElt) -> [(TvSubst, InstEnvElt)]
+ -> [(TvSubst, InstEnvElt)]
+-- Add a new solution, knocking out strictly less specific ones
+insert_overlapping new_item [] = [new_item]
+insert_overlapping new_item (item:items)
+ | new_beats_old && old_beats_new = item : insert_overlapping new_item items
+ -- Duplicate => keep both for error report
+ | new_beats_old = insert_overlapping new_item items
+ -- Keep new one
+ | old_beats_new = item : items
+ -- Keep old one
+ | otherwise = item : insert_overlapping new_item items
+ -- Keep both
+ where
+ new_beats_old = new_item `beats` item
+ old_beats_new = item `beats` new_item
+
+ (_, (tvs1, tys1, _)) `beats` (_, (tvs2, tys2, _))
+ = isJust (tcMatchTys tvs2 tys2 tys1) -- A beats B if A is more specific than B
+ -- I.e. if B can be instantiated to match A