Opened 9 years ago

Closed 7 years ago

Last modified 7 years ago

#2442 closed feature request (fixed)

Heuristics to improve error messages for badly referenced things

Reported by: batterseapower Owned by: simonpj
Priority: high Milestone: 7.0.2
Component: Compiler Version: 6.9
Keywords: Cc: pho@…, merehap@…, mmitar@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I propose the implementation of fuzzy-matching heuristics so we can get errors like this:

Prelude> fsa

<interactive>:1:0:
    Not in scope: `fsa'
    Maybe you meant `fst'
Prelude> import Data.Lits
Could not find module `Data.Lits':
  Use -v to see a list of the files searched for.
  Maybe you meant `Data.Bits' or `Data.List'
Prelude> 

And a heuristic such that when resolution of an unqualified name fails it can suggest a qualified alternative:

module Main where
import qualified Char

main = print (isSpace ' ')
$ stage2/ghc-inplace --make Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )

Test.hs:4:14:
    Not in scope: `isSpace'
    Maybe you meant `Char.isSpace'

I believe both of these represent an improvement to the compiler user experience.

If you wish to implement this feature in GHC, I have implemented, documented and tested it already and the patches are attached. It is under flag control: use -fno-helpful-errors to disable it. This is turned by default for the testsuite.

Attachments (5)

HelpfulErrors-Compiler.patch (75.8 KB) - added by batterseapower 9 years ago.
HelpfulErrors-Testsuite.patch (39.7 KB) - added by batterseapower 9 years ago.
HelpfulErrors-Doc.patch (55.5 KB) - added by batterseapower 9 years ago.
HelpfulErrors-Compiler-v2.patch (91.6 KB) - added by guest 9 years ago.
HelpfulErrors-Testsuite-v2.patch (42.6 KB) - added by guest 9 years ago.
Necessary due to a conflict with another change in the testsuite since v1

Download all attachments as: .zip

Change History (25)

Changed 9 years ago by batterseapower

Changed 9 years ago by batterseapower

Changed 9 years ago by batterseapower

Attachment: HelpfulErrors-Doc.patch added

comment:1 Changed 9 years ago by batterseapower

I've played with this a bit more and there is a small bug in the part of the patch that suggests qualified alternatives. If you are interested in merging the patch, let me know and I will take the time to fix it.

comment:2 Changed 9 years ago by simonpj

difficulty: Unknown

Looks splendid. I'd like to review the patch when I get back from holiday, but in principle thumbs-up from me. Thank you!

Simon

comment:3 Changed 9 years ago by batterseapower

Great!

For posterity, the accompanying thread on Haskell-Cafe is at http://www.haskell.org/pipermail/haskell-cafe/2008-July/045175.html

That thread also discusses what would be a cool improvement: searching all installed packages for the unbound name. However, that would require an actual index and as such is a bit of a heavier-weight solution.

As a practical matter, I've been developing GHC using a stage1 compiler with this patch compiled into it and there is a noticable delay when displaying unbound name error messages if there are many things in scope. This is because I have made no attempt to optimize the code yet, and this needs to be resolved.

Notes for me, when I get time to look at it:

  • Cache global reader environment elements between unbound name error messages (I'm guessing eltsUniqFM is fairly expensive)
  • Possibly adapt the distance metric so it operates in conjunction with a threshold distance it should bail out after

comment:4 Changed 9 years ago by guest

I've solved the performance problem purely by making use of an edit-distance algorithm based on bit-vectors. This is /very fast/. For future reference, I've actually released it's implementation (plus some other edit distances, QuickCheck tests for it all etc) on Hackage (http://hackage.haskell.org/cgi-bin/hackage-scripts/package/edit-distance).

My stress test was compiling GHC.hs with the Module import commented out. This generates a number of unbound name errors, each of which has to do a full scan of the (huge) imported name set. This takes 1 second on my modified GHC compared with 0.3 seconds on an unmodified one. If this is not an acceptable speed I can pursue the other performance-improving possibilities above.

Changed 9 years ago by guest

Changed 9 years ago by guest

Necessary due to a conflict with another change in the testsuite since v1

comment:5 Changed 9 years ago by ross

Type: proposalfeature request

comment:6 Changed 9 years ago by igloo

Milestone: 6.12 branch
Priority: normalhigh

I don't think we'll look at this in time for 6.10, but we should make a decision early in 6.12 to avoid collecting any more conflicts than necessary (although I guess it'll be in the wrong VCS by then; ug).

comment:7 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:8 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:9 Changed 9 years ago by igloo

Milestone: 6.12 branch6.12.1

comment:10 Changed 8 years ago by igloo

See also #3209.

comment:11 Changed 8 years ago by simonmar

Owner: set to simonpj

comment:12 Changed 8 years ago by simonmar

Milestone: 6.12.16.14 branch

Ran out of time; still needs review, and there might be some concerns about performance.

comment:13 Changed 8 years ago by PHO

Cc: pho@… added

comment:14 Changed 7 years ago by igloo

Milestone: 6.14 branch6.14.1
Status: newpatch
Type of failure: None/Unknown

comment:15 Changed 7 years ago by merehap

Cc: merehap@… added

comment:16 Changed 7 years ago by gidyn

Cc: gideon@… added

comment:17 Changed 7 years ago by mitar

Cc: mmitar@… added

comment:18 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:19 Changed 7 years ago by simonpj

Resolution: fixed
Status: patchclosed

Finally done!

Wed Dec 22 17:51:24 GMT 2010  simonpj@microsoft.com
  * Add fuzzyLookup, a variant of fuzzyMatch
  
  Plus, I changed quite a bit of layout to make the lines shorter.

    M ./compiler/utils/Util.lhs -33 +70

Wed Dec 22 17:54:00 GMT 2010  simonpj@microsoft.com
  * Implement fuzzy matching for the Finder
  
  ..so that you get a more helpful message when
  you mis-spell a module name in an 'import'.
  
  Validates, but not fully tested.
  
  Based on Max's patch in Trac #2442, but heavily refactored.

    M ./compiler/main/Finder.lhs -45 +59
    M ./compiler/main/HeaderInfo.hs -1 +2
    M ./compiler/main/HscTypes.lhs -8 +16
    M ./compiler/main/Packages.lhs -5 +27

Wed Dec 22 17:53:06 GMT 2010  simonpj@microsoft.com
  * Implement fuzzy matching for the renamer
  
  ...so that you get helpful suggestions when you mis-spell a name
  Based on Max's patch in Trac #2442, but heavily refactored.

    M ./compiler/main/DynFlags.hs -1 +4
    M ./compiler/rename/RnEnv.lhs -47 +176
    M ./compiler/typecheck/TcRnMonad.lhs +4

Fri Jan  7 10:28:55 GMT 2011  simonpj@microsoft.com
  * Make fuzzy matching a little less eager for short identifiers
  
  For single-character identifiers we now don't make any suggestions
  See comments in Util.fuzzyLookup

    M ./compiler/utils/Util.lhs -3 +12

Thu Jan 13 11:12:33 GMT 2011  simonpj@microsoft.com
  * Improve the finder's error messages
  
  I'd done all the work to add fuzzy-match suggestions, but they
  weren't really being used!  Here's what you get now
  
     module Foo where
      import Data.Lst
  
  Foo.hs:3:1:
      Failed to load interface for `Data.Lst'
      Perhaps you meant
        Data.List (from base)
        Data.List (needs flag -package haskell2010-1.0.0.0)
        Data.Int (needs flag -package haskell2010-1.0.0.0)
      Use -v to see a list of the files searched for.

    M ./compiler/main/Finder.lhs -7 +28

Thanks to Max for doing most of the real work.

Simon

comment:20 Changed 7 years ago by gidyn

Cc: gideon@… removed
Note: See TracTickets for help on using tickets.