Fix unused-import warnings

This patch fixes a fairly long-standing bug (dating back to 2015) in
RdrName.bestImport, namely

   commit 9376249b6b78610db055a10d05f6592d6bbbea2f
   Author: Simon Peyton Jones <simonpj@microsoft.com>
   Date:   Wed Oct 28 17:16:55 2015 +0000

   Fix unused-import stuff in a better way

In that patch got the sense of the comparison back to front, and
thereby failed to implement the unused-import rules described in
  Note [Choosing the best import declaration] in RdrName

This led to Trac #13064 and #15393

Fixing this bug revealed a bunch of unused imports in libraries;
the ones in the GHC repo are part of this commit.

The two important changes are

* Fix the bug in bestImport

* Modified the rules by adding (a) in
     Note [Choosing the best import declaration] in RdrName
  Reason: the previosu rules made Trac #5211 go bad again.  And
  the new rule (a) makes sense to me.

In unravalling this I also ended up doing a few other things

* Refactor RnNames.ImportDeclUsage to use a [GlobalRdrElt] for the
  things that are used, rather than [AvailInfo]. This is simpler
  and more direct.

* Rename greParentName to greParent_maybe, to follow GHC
  naming conventions

* Delete dead code RdrName.greUsedRdrName

Bumps a few submodules.

Reviewers: hvr, goldfire, bgamari, simonmar, jrtc27

Subscribers: rwbarton, carter

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

4 files changed, 138 insertions, 117 deletions

diff --git a/compiler/rename/RnEnv.hs b/compiler/rename/RnEnv.hs
index c28f47e43d..87f8be7d4f 100644
--- a/compiler/rename/RnEnv.hs
+++ b/compiler/rename/RnEnv.hs
@@ -77,7 +77,6 @@ import ListSetOps       ( minusList )
 import qualified GHC.LanguageExtensions as LangExt
 import RnUnbound
 import RnUtils
-import Data.Maybe (isJust)
 import qualified Data.Semigroup as Semi
 import Data.Either      ( partitionEithers )
 import Data.List        (find)
@@ -638,21 +637,21 @@ lookupSubBndrOcc_helper must_have_parent warn_if_deprec parent rdr_name
             NoParent -> Nothing
 
         picked_gres :: [GlobalRdrElt] -> DisambigInfo
+        -- For Unqual, find GREs that are in scope qualified or unqualified
+        -- For Qual,   find GREs that are in scope with that qualification
         picked_gres gres
           | isUnqual rdr_name
-              = mconcat (map right_parent gres)
+          = mconcat (map right_parent gres)
           | otherwise
-              = mconcat (map right_parent (pickGREs rdr_name gres))
-
+          = mconcat (map right_parent (pickGREs rdr_name gres))
 
         right_parent :: GlobalRdrElt -> DisambigInfo
         right_parent p
-          | Just cur_parent <- getParent p
-            = if parent == cur_parent
-                then DisambiguatedOccurrence p
-                else NoOccurrence
-          | otherwise
-            = UniqueOccurrence p
+          = case getParent p of
+               Just cur_parent
+                  | parent == cur_parent -> DisambiguatedOccurrence p
+                  | otherwise            -> NoOccurrence
+               Nothing                   -> UniqueOccurrence p
 
 
 -- This domain specific datatype is used to record why we decided it was
diff --git a/compiler/rename/RnExpr.hs-boot b/compiler/rename/RnExpr.hs-boot
index a944d7124e..b325eeb6f0 100644
--- a/compiler/rename/RnExpr.hs-boot
+++ b/compiler/rename/RnExpr.hs-boot
@@ -5,7 +5,6 @@ import NameSet     ( FreeVars )
 import TcRnTypes
 import SrcLoc      ( Located )
 import Outputable  ( Outputable )
-import HsExtension ( GhcPs, GhcRn )
 
 rnLExpr :: LHsExpr GhcPs
         -> RnM (LHsExpr GhcRn, FreeVars)
diff --git a/compiler/rename/RnNames.hs b/compiler/rename/RnNames.hs
index 8ded9c27db..09fa81576a 100644
--- a/compiler/rename/RnNames.hs
+++ b/compiler/rename/RnNames.hs
@@ -63,13 +63,11 @@ import qualified GHC.LanguageExtensions as LangExt
 
 import Control.Monad
 import Data.Either      ( partitionEithers, isRight, rights )
--- import qualified Data.Foldable as Foldable
 import Data.Map         ( Map )
 import qualified Data.Map as Map
 import Data.Ord         ( comparing )
 import Data.List        ( partition, (\\), find, sortBy )
 import qualified Data.Set as S
--- import qualified Data.Set as Set
 import System.FilePath  ((</>))
 
 import System.IO
@@ -1094,8 +1092,8 @@ gresFromIE decl_spec (L loc ie, avail)
   = gresFromAvail prov_fn avail
   where
     is_explicit = case ie of
-                    IEThingAll _ (L _ name) -> \n -> n == ieWrappedName name
-                    _                       -> \_ -> True
+                    IEThingAll _ name -> \n -> n == lieWrappedName name
+                    _                 -> \_ -> True
     prov_fn name
       = Just (ImpSpec { is_decl = decl_spec, is_item = item_spec })
       where
@@ -1217,44 +1215,11 @@ reportUnusedNames _export_decls gbl_env
     is_unused_local :: GlobalRdrElt -> Bool
     is_unused_local gre = isLocalGRE gre && isExternalName (gre_name gre)
 
-{-
-*********************************************************
-*                                                       *
-\subsection{Unused imports}
-*                                                       *
-*********************************************************
-
-This code finds which import declarations are unused.  The
-specification and implementation notes are here:
-  http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/UnusedImports
--}
-
-type ImportDeclUsage
-   = ( LImportDecl GhcRn   -- The import declaration
-     , [AvailInfo]        -- What *is* used (normalised)
-     , [Name] )       -- What is imported but *not* used
-
-warnUnusedImportDecls :: TcGblEnv -> RnM ()
-warnUnusedImportDecls gbl_env
-  = do { uses <- readMutVar (tcg_used_gres gbl_env)
-       ; let user_imports = filterOut (ideclImplicit . unLoc) (tcg_rn_imports gbl_env)
-                            -- This whole function deals only with *user* imports
-                            -- both for warning about unnecessary ones, and for
-                            -- deciding the minimal ones
-             rdr_env = tcg_rdr_env gbl_env
-             fld_env = mkFieldEnv rdr_env
-
-       ; let usage :: [ImportDeclUsage]
-             usage = findImportUsage user_imports uses
-
-       ; traceRn "warnUnusedImportDecls" $
-                       (vcat [ text "Uses:" <+> ppr uses
-                       , text "Import usage" <+> ppr usage])
-       ; whenWOptM Opt_WarnUnusedImports $
-         mapM_ (warnUnusedImport Opt_WarnUnusedImports fld_env) usage
-
-       ; whenGOptM Opt_D_dump_minimal_imports $
-         printMinimalImports usage }
+{- *********************************************************************
+*                                                                      *
+              Missing signatures
+*                                                                      *
+********************************************************************* -}
 
 -- | Warn the user about top level binders that lack type signatures.
 -- Called /after/ type inference, so that we can report the
@@ -1312,29 +1277,50 @@ warnMissingSignatures gbl_env
 
        ; add_sig_warns }
 
+
 {-
-Note [The ImportMap]
-~~~~~~~~~~~~~~~~~~~~
-The ImportMap is a short-lived intermediate data structure records, for
-each import declaration, what stuff brought into scope by that
-declaration is actually used in the module.
+*********************************************************
+*                                                       *
+\subsection{Unused imports}
+*                                                       *
+*********************************************************
 
-The SrcLoc is the location of the END of a particular 'import'
-declaration.  Why *END*?  Because we don't want to get confused
-by the implicit Prelude import. Consider (Trac #7476) the module
-    import Foo( foo )
-    main = print foo
-There is an implicit 'import Prelude(print)', and it gets a SrcSpan
-of line 1:1 (just the point, not a span). If we use the *START* of
-the SrcSpan to identify the import decl, we'll confuse the implicit
-import Prelude with the explicit 'import Foo'.  So we use the END.
-It's just a cheap hack; we could equally well use the Span too.
+This code finds which import declarations are unused.  The
+specification and implementation notes are here:
+  http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/UnusedImports
 
-The AvailInfos are the things imported from that decl (just a list,
-not normalised).
+See also Note [Choosing the best import declaration] in RdrName
 -}
 
-type ImportMap = Map SrcLoc [AvailInfo]  -- See [The ImportMap]
+type ImportDeclUsage
+   = ( LImportDecl GhcRn   -- The import declaration
+     , [GlobalRdrElt]      -- What *is* used (normalised)
+     , [Name] )            -- What is imported but *not* used
+
+warnUnusedImportDecls :: TcGblEnv -> RnM ()
+warnUnusedImportDecls gbl_env
+  = do { uses <- readMutVar (tcg_used_gres gbl_env)
+       ; let user_imports = filterOut
+                              (ideclImplicit . unLoc)
+                              (tcg_rn_imports gbl_env)
+                -- This whole function deals only with *user* imports
+                -- both for warning about unnecessary ones, and for
+                -- deciding the minimal ones
+             rdr_env = tcg_rdr_env gbl_env
+             fld_env = mkFieldEnv rdr_env
+
+       ; let usage :: [ImportDeclUsage]
+             usage = findImportUsage user_imports uses
+
+       ; traceRn "warnUnusedImportDecls" $
+                       (vcat [ text "Uses:" <+> ppr uses
+                             , text "Import usage" <+> ppr usage])
+
+       ; whenWOptM Opt_WarnUnusedImports $
+         mapM_ (warnUnusedImport Opt_WarnUnusedImports fld_env) usage
+
+       ; whenGOptM Opt_D_dump_minimal_imports $
+         printMinimalImports usage }
 
 findImportUsage :: [LImportDecl GhcRn]
                 -> [GlobalRdrElt]
@@ -1344,16 +1330,17 @@ findImportUsage imports used_gres
   = map unused_decl imports
   where
     import_usage :: ImportMap
-    import_usage
-      = foldr extendImportMap Map.empty used_gres
+    import_usage = mkImportMap used_gres
 
     unused_decl decl@(L loc (ImportDecl { ideclHiding = imps }))
-      = (decl, nubAvails used_avails, nameSetElemsStable unused_imps)
+      = (decl, used_gres, nameSetElemsStable unused_imps)
       where
-        used_avails = Map.lookup (srcSpanEnd loc) import_usage `orElse` []
-                      -- srcSpanEnd: see Note [The ImportMap]
-        used_names   = availsToNameSetWithSelectors used_avails
-        used_parents = mkNameSet [n | AvailTC n _ _ <- used_avails]
+        used_gres = Map.lookup (srcSpanEnd loc) import_usage
+                               -- srcSpanEnd: see Note [The ImportMap]
+                    `orElse` []
+
+        used_names   = mkNameSet (map      gre_name        used_gres)
+        used_parents = mkNameSet (mapMaybe greParent_maybe used_gres)
 
         unused_imps   -- Not trivial; see eg Trac #7454
           = case imps of
@@ -1362,19 +1349,16 @@ findImportUsage imports used_gres
               _other -> emptyNameSet -- No explicit import list => no unused-name list
 
         add_unused :: IE GhcRn -> NameSet -> NameSet
-        add_unused (IEVar _ (L _ n))      acc
-                                       = add_unused_name (ieWrappedName n) acc
-        add_unused (IEThingAbs _ (L _ n)) acc
-                                       = add_unused_name (ieWrappedName n) acc
-        add_unused (IEThingAll _ (L _ n)) acc
-                                       = add_unused_all  (ieWrappedName n) acc
-        add_unused (IEThingWith _ (L _ p) wc ns fs) acc =
-          add_wc_all (add_unused_with (ieWrappedName p) xs acc)
-          where xs = map (ieWrappedName . unLoc) ns
-                          ++ map (flSelector . unLoc) fs
+        add_unused (IEVar _ n)      acc = add_unused_name (lieWrappedName n) acc
+        add_unused (IEThingAbs _ n) acc = add_unused_name (lieWrappedName n) acc
+        add_unused (IEThingAll _ n) acc = add_unused_all  (lieWrappedName n) acc
+        add_unused (IEThingWith _ p wc ns fs) acc =
+          add_wc_all (add_unused_with pn xs acc)
+          where pn = lieWrappedName p
+                xs = map lieWrappedName ns ++ map (flSelector . unLoc) fs
                 add_wc_all = case wc of
                             NoIEWildcard -> id
-                            IEWildcard _ -> add_unused_all (ieWrappedName p)
+                            IEWildcard _ -> add_unused_all pn
         add_unused _ acc = acc
 
         add_unused_name n acc
@@ -1394,49 +1378,86 @@ findImportUsage imports used_gres
        -- Num is not itself mentioned.  Hence the two cases in add_unused_with.
     unused_decl (L _ (XImportDecl _)) = panic "unused_decl"
 
-extendImportMap :: GlobalRdrElt -> ImportMap -> ImportMap
+
+{- Note [The ImportMap]
+~~~~~~~~~~~~~~~~~~~~~~~
+The ImportMap is a short-lived intermediate data structure records, for
+each import declaration, what stuff brought into scope by that
+declaration is actually used in the module.
+
+The SrcLoc is the location of the END of a particular 'import'
+declaration.  Why *END*?  Because we don't want to get confused
+by the implicit Prelude import. Consider (Trac #7476) the module
+    import Foo( foo )
+    main = print foo
+There is an implicit 'import Prelude(print)', and it gets a SrcSpan
+of line 1:1 (just the point, not a span). If we use the *START* of
+the SrcSpan to identify the import decl, we'll confuse the implicit
+import Prelude with the explicit 'import Foo'.  So we use the END.
+It's just a cheap hack; we could equally well use the Span too.
+
+The [GlobalRdrElt] are the things imported from that decl.
+-}
+
+type ImportMap = Map SrcLoc [GlobalRdrElt]  -- See [The ImportMap]
+     -- If loc :-> gres, then
+     --   'loc' = the end loc of the bestImport of each GRE in 'gres'
+
+mkImportMap :: [GlobalRdrElt] -> ImportMap
 -- For each of a list of used GREs, find all the import decls that brought
 -- it into scope; choose one of them (bestImport), and record
 -- the RdrName in that import decl's entry in the ImportMap
-extendImportMap gre imp_map
-   = add_imp gre (bestImport (gre_imp gre)) imp_map
+mkImportMap gres
+  = foldr add_one Map.empty gres
   where
-    add_imp :: GlobalRdrElt -> ImportSpec -> ImportMap -> ImportMap
-    add_imp gre (ImpSpec { is_decl = imp_decl_spec }) imp_map
-      = Map.insertWith add decl_loc [avail] imp_map
-      where
-        add _ avails = avail : avails -- add is really just a specialised (++)
-        decl_loc = srcSpanEnd (is_dloc imp_decl_spec)
-                   -- For srcSpanEnd see Note [The ImportMap]
-        avail    = availFromGRE gre
+    add_one gre@(GRE { gre_imp = imp_specs }) imp_map
+       = Map.insertWith add decl_loc [gre] imp_map
+       where
+          best_imp_spec = bestImport imp_specs
+          decl_loc      = srcSpanEnd (is_dloc (is_decl best_imp_spec))
+                        -- For srcSpanEnd see Note [The ImportMap]
+          add _ gres = gre : gres
 
 warnUnusedImport :: WarningFlag -> NameEnv (FieldLabelString, Name)
                  -> ImportDeclUsage -> RnM ()
 warnUnusedImport flag fld_env (L loc decl, used, unused)
+
+  -- Do not warn for 'import M()'
   | Just (False,L _ []) <- ideclHiding decl
-                = return ()            -- Do not warn for 'import M()'
+  = return ()
 
+  -- Note [Do not warn about Prelude hiding]
   | Just (True, L _ hides) <- ideclHiding decl
   , not (null hides)
   , pRELUDE_NAME == unLoc (ideclName decl)
-                = return ()            -- Note [Do not warn about Prelude hiding]
-  | null used   = addWarnAt (Reason flag) loc msg1 -- Nothing used; drop entire decl
-  | null unused = return ()            -- Everything imported is used; nop
-  | otherwise   = addWarnAt (Reason flag) loc msg2 -- Some imports are unused
+  = return ()
+
+  -- Nothing used; drop entire declaration
+  | null used
+  = addWarnAt (Reason flag) loc msg1
+
+  -- Everything imported is used; nop
+  | null unused
+  = return ()
+
+  -- Some imports are unused
+  | otherwise
+  = addWarnAt (Reason flag) loc  msg2
+
   where
-    msg1 = vcat [pp_herald <+> quotes pp_mod <+> pp_not_used,
-                 nest 2 (text "except perhaps to import instances from"
-                                   <+> quotes pp_mod),
-                 text "To import instances alone, use:"
+    msg1 = vcat [ pp_herald <+> quotes pp_mod <+> is_redundant
+                , nest 2 (text "except perhaps to import instances from"
+                                   <+> quotes pp_mod)
+                , text "To import instances alone, use:"
                                    <+> text "import" <+> pp_mod <> parens Outputable.empty ]
-    msg2 = sep [pp_herald <+> quotes sort_unused,
-                    text "from module" <+> quotes pp_mod <+> pp_not_used]
+    msg2 = sep [ pp_herald <+> quotes sort_unused
+               , text "from module" <+> quotes pp_mod <+> is_redundant]
     pp_herald  = text "The" <+> pp_qual <+> text "import of"
     pp_qual
       | ideclQualified decl = text "qualified"
       | otherwise           = Outputable.empty
-    pp_mod      = ppr (unLoc (ideclName decl))
-    pp_not_used = text "is redundant"
+    pp_mod       = ppr (unLoc (ideclName decl))
+    is_redundant = text "is redundant"
 
     -- In warning message, pretty-print identifiers unqualified unconditionally
     -- to improve the consistent for ambiguous/unambiguous identifiers.
@@ -1446,8 +1467,9 @@ warnUnusedImport flag fld_env (L loc decl, used, unused)
                                Nothing  -> pprNameUnqualified n
 
     -- Print unused names in a deterministic (lexicographic) order
+    sort_unused :: SDoc
     sort_unused = pprWithCommas ppr_possible_field $
-                    sortBy (comparing nameOccName) unused
+                  sortBy (comparing nameOccName) unused
 
 {-
 Note [Do not warn about Prelude hiding]
@@ -1475,7 +1497,7 @@ decls, and simply trim their import lists.  NB that
 getMinimalImports :: [ImportDeclUsage] -> RnM [LImportDecl GhcRn]
 getMinimalImports = mapM mk_minimal
   where
-    mk_minimal (L l decl, used, unused)
+    mk_minimal (L l decl, used_gres, unused)
       | null unused
       , Just (False, _) <- ideclHiding decl
       = return (L l decl)
@@ -1484,7 +1506,8 @@ getMinimalImports = mapM mk_minimal
                             , ideclSource  = is_boot
                             , ideclPkgQual = mb_pkg } = decl
            ; iface <- loadSrcInterface doc mod_name is_boot (fmap sl_fs mb_pkg)
-           ; let lies = map (L l) (concatMap (to_ie iface) used)
+           ; let used_avails = gresToAvailInfo used_gres
+                 lies = map (L l) (concatMap (to_ie iface) used_avails)
            ; return (L l (decl { ideclHiding = Just (False, L l lies) })) }
       where
         doc = text "Compute minimal imports for" <+> ppr decl
diff --git a/compiler/rename/RnSource.hs b/compiler/rename/RnSource.hs
index 48739cdf69..5ecb1a68e7 100644
--- a/compiler/rename/RnSource.hs
+++ b/compiler/rename/RnSource.hs
@@ -67,7 +67,7 @@ import Control.Arrow ( first )
 import Data.List ( mapAccumL )
 import qualified Data.List.NonEmpty as NE
 import Data.List.NonEmpty ( NonEmpty(..) )
-import Data.Maybe ( isNothing, maybe, fromMaybe )
+import Data.Maybe ( isNothing, fromMaybe )
 import qualified Data.Set as Set ( difference, fromList, toList, null )
 
 {- | @rnSourceDecl@ "renames" declarations.