#14969 closed bug (fixed)

Underconstrained typed holes are non-performant

Reported by: johnleo Owned by:
Priority: normal Milestone: 8.6.1
Component: Compiler Version: 8.5
Keywords: TypedHoles Cc: pallm@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case: ghci/scripts/T14969
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D4444
Wiki Page:

Description

With a fresh build of 8.5:

GHCi, version 8.5.20180323: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/leo/.ghci
Prelude> 3 _ 4
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 8.5.20180323 for x86_64-apple-darwin):
	ASSERT failed!
  2
  1
  t_a4j6[tau:1]
  Maybe a_a4j7[tau:2]
  Call stack:
      CallStack (from HasCallStack):
        callStackDoc, called at compiler/utils/Outputable.hs:1157:37 in ghc:Outputable
        pprPanic, called at compiler/utils/Outputable.hs:1213:5 in ghc:Outputable
        assertPprPanic, called at compiler/typecheck/TcMType.hs:720:54 in ghc:TcMType

I believe this fails in earlier versions as well, but I haven't tested it.

Change History (18)

comment:1 Changed 18 months ago by sighingnow

This panic is caused by the bad TcLevel when checking the TcLevel invariants, maybe related to ticket:14884.

comment:2 Changed 18 months ago by goldfire

Does not happen on 8.4.1.

comment:3 Changed 18 months ago by RyanGlScott

To be clear, in comment:2, do you mean that it doesn't build with a standard 8.4.1 bindist, or with 8.4.1 built from source with ASSERTions enabled?

comment:4 Changed 18 months ago by simonpj

Cc: pallm@… added

I think this is a variant of #14884.

The machinery that Mathias Gissurarson (cc'd) has implemented for reporting typed holes, does not set type-variable level numbers properly. In that context it doesn't matter much; but it's very unsatisfactory.

I recently had a long conversation with Mathias about various improvements to the type-hole-reporting mechanism. So we can expect improvements here.

Here is the main wiki page about typed holes which summarises the state of play

comment:5 Changed 18 months ago by Richard Eisenberg <rae@…>

In 07abff71/ghc:

Test #14884, #14969

These were fixed by faec8d358985e5d0bf363bd96f23fe76c9e281f7

test cases: typecheck/should_fail/T14884
            ghci/scripts/T14969

comment:6 Changed 18 months ago by goldfire

Resolution: fixed
Status: newclosed
Test Case: ghci/scripts/T14969

I nabbed this one by accident. :)

comment:7 Changed 18 months ago by Tritlo

Yes, I've hit this recently during my work on improving the implementation of the suggestions, and now I've become more familiar with how to properly set the tcLevel. I'll submit the patch soon (hopefully), after I manage to iron out a few more kinks. Thanks for the nab goldfire, hopefully there won't be any more to nab :)

comment:8 Changed 18 months ago by simonpj

Keywords: TypedHoles added

comment:9 Changed 17 months ago by johnleo

The latest behavior using 8.5.20180413 on my Mac is that if I type 3 _ 4 or 3 _ GHCI now hangs, which I do not consider an improvement over the panic. I have to type ^C to break. If I type something like _ or _ 3 I get a Found hole message as expected.

Reopening, but if it makes more sense to file a new bug instead I can do that.

comment:10 Changed 17 months ago by johnleo

Resolution: fixed
Status: closednew

comment:11 Changed 17 months ago by RyanGlScott

Summary: panic on incorrect syntaxUnderconstrained typed holes are non-performant
Type of failure: None/UnknownCompile-time performance bug

Note that it doesn't loop infinitely, but rather takes a very long time to compute:

$ time ghc/inplace/bin/ghc-stage2 -XFlexibleContexts -e "3 _ 4"

<interactive>:0:1: error:
    • Could not deduce (Num t1)
      from the context: (Num t, Num (t2 -> t -> t3))
        bound by the inferred type for ‘it’:
                   forall t t2 t3. (Num t, Num (t2 -> t -> t3)) => t3
        at <interactive>:0:1-5
      The type variable ‘t1’ is ambiguous
    • In the ambiguity check for the inferred type for ‘it’
      To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
      When checking the inferred type
        it :: forall t1 t2 t3. (Num t1, Num (t2 -> t1 -> t3)) => t3

real    0m32.219s
user    0m32.176s
sys     0m0.084s

In other words, this is the same problem observed in https://ghc.haskell.org/trac/ghc/ticket/10946#comment:9. This is good home for this particular bug.

comment:12 Changed 17 months ago by Tritlo

I've reworked the substitution suggestions a lot over the past few weeks, and I've updated the sorting to be based on sizes of matches rather than by subsumption (though sorting by subsumption is still available via a flag). I hope to submit the patch this weekend, after I've updated the documentation.

comment:13 Changed 17 months ago by Tritlo

Status: newpatch

A fix for this is included in https://phabricator.haskell.org/D4444, where we change the default sorting algorithm to one based on comparing sizes of types rather than subsumption, which is much faster and gives comparable results.

comment:14 Changed 17 months ago by RyanGlScott

Differential Rev(s): Phab:D4444

comment:15 Changed 17 months ago by simonpj

It would be good to get this done. e.g #13499 is another example of the typed-hole perf problem.

comment:16 Changed 17 months ago by Tritlo

Yes! I'll try to get the patch ready for inclusion this weekend.

comment:17 Changed 16 months ago by Ben Gamari <ben@…>

In e0b44e2/ghc:

Improved Valid Hole Fits

I've changed the name from `Valid substitutions` to `Valid hole fits`,
since "substitution" already has a well defined meaning within the
theory. As part of this change, the flags and output is reanamed, with
substitution turning into hole-fit in most cases. "hole fit" was already
used internally in the code, it's clear and shouldn't cause any
confusion.

In this update, I've also reworked how we manage side-effects in the
hole we are considering.

This allows us to consider local bindings such as where clauses and
arguments to functions, suggesting e.g. `a` for `head (x:xs) where head
:: [a] -> a`.

It also allows us to find suggestions such as `maximum` for holes of
type `Ord a => a -> [a]`, and `max` when looking for a match for the
hole in `g = foldl1 _`, where `g :: Ord a => [a] -> a`.

We also show much improved output for refinement hole fits, and
fixes #14990. We now show the correct type of the function, but we also
now show what the arguments to the function should be e.g. `foldl1 (_ ::
Integer -> Integer -> Integer)` when looking for `[Integer] -> Integer`.

I've moved the bulk of the code from `TcErrors.hs` to a new file,
`TcHoleErrors.hs`, since it was getting too big to not live on it's own.

This addresses the considerations raised in #14969, and takes proper
care to set the `tcLevel` of the variables to the right level before
passing it to the simplifier.

We now also zonk the suggestions properly, which improves the output of
the refinement hole fits considerably.

This also filters out suggestions from the `GHC.Err` module, since even
though `error` and `undefined` are indeed valid hole fits, they are
"trivial", and almost never useful to the user.

We now find the hole fits using the proper manner, namely by solving
nested implications. This entails that the givens are passed along using
the implications the hole was nested in, which in turn should mean that
there will be fewer weird bugs in the typed holes.

I've also added a new sorting method (as suggested by SPJ) and sort by
the size of the types needed to turn the hole fits into the type of the
hole. This gives a reasonable approximation to relevance, and is much
faster than the subsumption check. I've also added a flag to toggle
whether to use this new sorting algorithm (as is done by default) or the
subsumption algorithm. This fixes #14969

I've also added documentation for these new flags and update the
documentation according to the new output.

Reviewers: bgamari, goldfire

Reviewed By: bgamari

Subscribers: simonpj, rwbarton, thomie, carter

GHC Trac Issues: #14969, #14990, #10946

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

comment:18 Changed 16 months ago by bgamari

Milestone: 8.6.1
Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.