instance selection too eager

changed weight to 5

added Tbug Trac import typechecker labels

Attached file too_eager.hs ($1268).

minimal test case coming from Data.HList.Dredge

No error in 8.0.1, though.

I tried to figure out where in the 8.0.2 branch this regression was introduced. Unfortunately, I wasn't able to isolate an exact commit, because the range of commits in which it was introduced doesn't build. However, I know for sure it was introduced between:

cc02156b (where the bug is not present):

From cc02156b859159eff7d86043f67826c17f2bd170 Mon Sep 17 00:00:00 2001
From: Bartosz Nitka <niteria@gmail.com>
Date: Mon, 18 Apr 2016 07:32:03 -0700
Subject: [PATCH] Make benign non-determinism in pretty-printing more obvious

This change takes us one step closer to being able to remove
`varSetElemsWellScoped`. The end goal is to make every source
of non-determinism obvious at the source level, so that when
we achieve determinism it doesn't get broken accidentally.

Test Plan: compile GHC

Reviewers: simonmar, goldfire, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2123

GHC Trac Issues: #4012

(cherry picked from commit 0f96686b10fd36d479a54c71a6e1753193e85347)

ae94a31e (where the bug is present):

From ae94a31e7f162b4a3ef6b6f837bd6006a98f639a Mon Sep 17 00:00:00 2001
From: Simon Peyton Jones <simonpj@microsoft.com>
Date: Fri, 22 Apr 2016 10:47:14 +0100
Subject: [PATCH] Refactor free tyvars on LHS of rules

A RULE can have unbound meta-tyvars on the LHS.  Consider
  data T a = C

  foo :: T a -> Int
  foo C = 1

  {-# RULES "myrule"  foo C = 1 #-}

After type checking the LHS becomes (foo alpha (C alpah)) and we do
not want to zap the unbound meta-tyvar 'alpha' to Any, because that
limits the applicability of the rule.  Instead, we want to quantify
over it!

Previously there was a rather clunky implementation of this
quantification, buried in the zonker in TcHsSyn (zonkTvCollecting).

This patch refactors it so that the zonker just turns the meta-tyvar
into a skolem, and the desugarer adds the quantification.  See DsBinds
Note [Free tyvars on rule LHS]. As it happened, the desugarer was
already doing something similar for dictionaries. See DsBinds
Note [Free dictionaries on rule LHS]

No change in functionality, but less cruft.

(cherry picked from commit 6ad2b42f866fa718855cc5c850e3549bc1428b3c)

I doubt that ae94a31e was responsible, since it seems to only touch rewrite RULES. Furthermore, niteria authored all commits between cc02156b and that point. Do you have a hunch what might be happening here, niteria?

Actually, compiling these commits from the HEAD branch (instead of the 8.0.2 branch) turned out to be more fruitful. I discovered that the commit which introduced this regression is c9bcaf31:

From c9bcaf3165586ac214fa694e61c55eb45eb131ab Mon Sep 17 00:00:00 2001
From: Bartosz Nitka <niteria@gmail.com>
Date: Tue, 26 Apr 2016 05:58:24 -0700
Subject: [PATCH] Kill varSetElemsWellScoped in quantifyTyVars

varSetElemsWellScoped introduces unnecessary non-determinism in
inferred type signatures.
Removing this instance required changing the representation of
TcDepVars to use deterministic sets.
This is the last occurence of varSetElemsWellScoped, allowing me to
finally remove it.

Test Plan:
./validate
I will update the expected outputs when commiting, some reordering
of type variables in types is expected.

This reproduces on recent HEAD.

This appears to be another case of unspoken assumptions about the order.

On top of c9bcaf31 it suffices to make this change:

--- a/compiler/typecheck/TcMType.hs
+++ b/compiler/typecheck/TcMType.hs
@@ -874,7 +874,7 @@ quantifyZonkedTyVars gbl_tvs (DV{ dv_kvs = dep_tkvs, dv_tvs = nondep_tkvs })
                  -- closeOverKinds all_cvs: do not quantify over coercion
                  --    variables, or any any tvs that a covar depends on

-             nondep_tvs = dVarSetElems $
+             nondep_tvs = varSetElems . dVarSetToVarSet $
                           nondep_tkvs `dVarSetMinusVarSet` gbl_tvs
                  -- No worry about dependent covars here; they are
                  --    all in dep_tkvs

to make the problem go away. It also fixes the problem on HEAD, except you have to use nonDetEltsUFM instead of varSetElems.

Broken GHC infers:

g_f :: forall (b :: k0) k c a. F a (Proxy b) => a -> c

, while the working one infers

g_f :: forall k (b :: k) c a. F a (Proxy b) => a -> c

I think this has been broken since 67465497. Running before c9bcaf31 with -dunique-increment=-1 reproduces the problem.

It appears that when we growThetaTyVarsDSet we add some kind variables to the nondependent type var set, but the vars inside depend on the newly added kind var. We then linearize without any regard for dependencies, because there shouldn't be any.

changed milestone to %8.2.1

changed weight to 7

Trac metadata

Trac field	Value
Priority	normal → high

mentioned in issue #13393 (closed)

mentioned in commit 7e96526a

closed

This is a bit of a big commit, but I think it'd be worth doing for 8.2

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed
Test case	- → polykinds/T13371

Trac field	Value
Version	8.0.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler (Type checker)
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

instance selection too eager

Child items 0

Activity