summaryrefslogtreecommitdiff
path: root/compiler/GHC/Rename/Names.hs
blob: 65bb2c92d2ce8b270424805922a0c941001b3f73 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
{-
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998

Extracting imported and top-level names in scope
-}

{-# LANGUAGE NondecreasingIndentation #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE LambdaCase #-}

module GHC.Rename.Names (
        rnImports, getLocalNonValBinders, newRecordSelector,
        extendGlobalRdrEnvRn,
        gresFromAvails,
        calculateAvails,
        reportUnusedNames,
        checkConName,
        mkChildEnv,
        findChildren,
        findImportUsage,
        getMinimalImports,
        printMinimalImports,
        renamePkgQual, renameRawPkgQual,
        ImportDeclUsage
    ) where

import GHC.Prelude hiding ( head, init, last, tail )

import GHC.Driver.Env
import GHC.Driver.Session
import GHC.Driver.Ppr

import GHC.Rename.Env
import GHC.Rename.Fixity
import GHC.Rename.Utils ( warnUnusedTopBinds, mkFieldEnv )

import GHC.Tc.Errors.Types
import GHC.Tc.Utils.Env
import GHC.Tc.Utils.Monad

import GHC.Hs
import GHC.Iface.Load   ( loadSrcInterface )
import GHC.Builtin.Names
import GHC.Parser.PostProcess ( setRdrNameSpace )
import GHC.Core.Type
import GHC.Core.PatSyn
import GHC.Core.TyCon ( TyCon, tyConName )
import qualified GHC.LanguageExtensions as LangExt

import GHC.Utils.Outputable as Outputable
import GHC.Utils.Misc as Utils
import GHC.Utils.Panic

import GHC.Types.Fixity.Env
import GHC.Types.SafeHaskell
import GHC.Types.Name
import GHC.Types.Name.Env
import GHC.Types.Name.Set
import GHC.Types.Name.Reader
import GHC.Types.Avail
import GHC.Types.FieldLabel
import GHC.Types.SourceFile
import GHC.Types.SrcLoc as SrcLoc
import GHC.Types.Basic  ( Arity, TopLevelFlag(..) )
import GHC.Types.SourceText
import GHC.Types.Id
import GHC.Types.HpcInfo
import GHC.Types.Error
import GHC.Types.PkgQual
import GHC.Types.ConInfo (ConInfo, mkConInfo)

import GHC.Unit
import GHC.Unit.Module.Warnings
import GHC.Unit.Module.ModIface
import GHC.Unit.Module.Imported
import GHC.Unit.Module.Deps
import GHC.Unit.Env

import GHC.Data.Maybe
import GHC.Data.FastString
import GHC.Data.FastString.Env

import Language.Haskell.Syntax.Basic (FieldLabelString(..))

import Control.Monad
import Data.Either      ( partitionEithers )
import Data.Map         ( Map )
import qualified Data.Map as Map
import Data.Ord         ( comparing )
import Data.List        ( partition, (\\), find, sortBy )
import Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as NE
import Data.Function    ( on )
import qualified Data.Set as S
import Data.Foldable    ( toList )
import Data.Void        ( Void )
import System.FilePath  ((</>))

import System.IO
import GHC.Data.Bag

{-
************************************************************************
*                                                                      *
\subsection{rnImports}
*                                                                      *
************************************************************************

Note [Tracking Trust Transitively]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When we import a package as well as checking that the direct imports are safe
according to the rules outlined in the Note [Safe Haskell Trust Check] in GHC.Driver.Main
we must also check that these rules hold transitively for all dependent modules
and packages. Doing this without caching any trust information would be very
slow as we would need to touch all packages and interface files a module depends
on. To avoid this we make use of the property that if a modules Safe Haskell
mode changes, this triggers a recompilation from that module in the dependency
graph. So we can just worry mostly about direct imports.

There is one trust property that can change for a package though without
recompilation being triggered: package trust. So we must check that all
packages a module transitively depends on to be trusted are still trusted when
we are compiling this module (as due to recompilation avoidance some modules
below may not be considered trusted any more without recompilation being
triggered).

We handle this by augmenting the existing transitive list of packages a module M
depends on with a bool for each package that says if it must be trusted when the
module M is being checked for trust. This list of trust required packages for a
single import is gathered in the rnImportDecl function and stored in an
ImportAvails data structure. The union of these trust required packages for all
imports is done by the rnImports function using the combine function which calls
the plusImportAvails function that is a union operation for the ImportAvails
type. This gives us in an ImportAvails structure all packages required to be
trusted for the module we are currently compiling. Checking that these packages
are still trusted (and that direct imports are trusted) is done in
GHC.Driver.Main.checkSafeImports.

See the note below, [Trust Own Package] for a corner case in this method and
how its handled.


Note [Trust Own Package]
~~~~~~~~~~~~~~~~~~~~~~~~
There is a corner case of package trust checking that the usual transitive check
doesn't cover. (For how the usual check operates see the Note [Tracking Trust
Transitively] below). The case is when you import a -XSafe module M and M
imports a -XTrustworthy module N. If N resides in a different package than M,
then the usual check works as M will record a package dependency on N's package
and mark it as required to be trusted. If N resides in the same package as M
though, then importing M should require its own package be trusted due to N
(since M is -XSafe so doesn't create this requirement by itself). The usual
check fails as a module doesn't record a package dependency of its own package.
So instead we now have a bool field in a modules interface file that simply
states if the module requires its own package to be trusted. This field avoids
us having to load all interface files that the module depends on to see if one
is trustworthy.


Note [Trust Transitive Property]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
So there is an interesting design question in regards to transitive trust
checking. Say I have a module B compiled with -XSafe. B is dependent on a bunch
of modules and packages, some packages it requires to be trusted as its using
-XTrustworthy modules from them. Now if I have a module A that doesn't use safe
haskell at all and simply imports B, should A inherit all the trust
requirements from B? Should A now also require that a package p is trusted since
B required it?

We currently say no but saying yes also makes sense. The difference is, if a
module M that doesn't use Safe Haskell imports a module N that does, should all
the trusted package requirements be dropped since M didn't declare that it cares
about Safe Haskell (so -XSafe is more strongly associated with the module doing
the importing) or should it be done still since the author of the module N that
uses Safe Haskell said they cared (so -XSafe is more strongly associated with
the module that was compiled that used it).

Going with yes is a simpler semantics we think and harder for the user to stuff
up but it does mean that Safe Haskell will affect users who don't care about
Safe Haskell as they might grab a package from Cabal which uses safe haskell (say
network) and that packages imports -XTrustworthy modules from another package
(say bytestring), so requires that package is trusted. The user may now get
compilation errors in code that doesn't do anything with Safe Haskell simply
because they are using the network package. They will have to call 'ghc-pkg
trust network' to get everything working. Due to this invasive nature of going
with yes we have gone with no for now.
-}

-- | Process Import Decls.  See 'rnImportDecl' for a description of what
-- the return types represent.
-- Note: Do the non SOURCE ones first, so that we get a helpful warning
-- for SOURCE ones that are unnecessary
rnImports :: [(LImportDecl GhcPs, SDoc)]
          -> RnM ([LImportDecl GhcRn], GlobalRdrEnv, ImportAvails, AnyHpcUsage)
rnImports imports = do
    tcg_env <- getGblEnv
    -- NB: want an identity module here, because it's OK for a signature
    -- module to import from its implementor
    let this_mod = tcg_mod tcg_env
    let (source, ordinary) = partition (is_source_import . fst) imports
        is_source_import d = ideclSource (unLoc d) == IsBoot
    stuff1 <- mapAndReportM (rnImportDecl this_mod) ordinary
    stuff2 <- mapAndReportM (rnImportDecl this_mod) source
    -- Safe Haskell: See Note [Tracking Trust Transitively]
    let (decls, rdr_env, imp_avails, hpc_usage) = combine (stuff1 ++ stuff2)
    -- Update imp_boot_mods if imp_direct_mods mentions any of them
    let merged_import_avail = clobberSourceImports imp_avails
    dflags <- getDynFlags
    let final_import_avail  =
          merged_import_avail { imp_dep_direct_pkgs = S.fromList (implicitPackageDeps dflags)
                                                        `S.union` imp_dep_direct_pkgs merged_import_avail}
    return (decls, rdr_env, final_import_avail, hpc_usage)

  where
    clobberSourceImports imp_avails =
      imp_avails { imp_boot_mods = imp_boot_mods' }
      where
        imp_boot_mods' = mergeInstalledModuleEnv combJ id (const emptyInstalledModuleEnv)
                            (imp_boot_mods imp_avails)
                            (imp_direct_dep_mods imp_avails)

        combJ (GWIB _ IsBoot) x = Just x
        combJ r _               = Just r
    -- See Note [Combining ImportAvails]
    combine :: [(LImportDecl GhcRn,  GlobalRdrEnv, ImportAvails, AnyHpcUsage)]
            -> ([LImportDecl GhcRn], GlobalRdrEnv, ImportAvails, AnyHpcUsage)
    combine ss =
      let (decls, rdr_env, imp_avails, hpc_usage, finsts) = foldr
            plus
            ([], emptyGlobalRdrEnv, emptyImportAvails, False, emptyModuleSet)
            ss
      in (decls, rdr_env, imp_avails { imp_finsts = moduleSetElts finsts },
            hpc_usage)

    plus (decl,  gbl_env1, imp_avails1, hpc_usage1)
         (decls, gbl_env2, imp_avails2, hpc_usage2, finsts_set)
      = ( decl:decls,
          gbl_env1 `plusGlobalRdrEnv` gbl_env2,
          imp_avails1' `plusImportAvails` imp_avails2,
          hpc_usage1 || hpc_usage2,
          extendModuleSetList finsts_set new_finsts )
      where
      imp_avails1' = imp_avails1 { imp_finsts = [] }
      new_finsts = imp_finsts imp_avails1

{-
Note [Combining ImportAvails]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
imp_finsts in ImportAvails is a list of family instance modules
transitively depended on by an import. imp_finsts for a currently
compiled module is a union of all the imp_finsts of imports.
Computing the union of two lists of size N is O(N^2) and if we
do it to M imports we end up with O(M*N^2). That can get very
expensive for bigger module hierarchies.

Union can be optimized to O(N log N) if we use a Set.
imp_finsts is converted back and forth between dep_finsts, so
changing a type of imp_finsts means either paying for the conversions
or changing the type of dep_finsts as well.

I've measured that the conversions would cost 20% of allocations on my
test case, so that can be ruled out.

Changing the type of dep_finsts forces checkFamInsts to
get the module lists in non-deterministic order. If we wanted to restore
the deterministic order, we'd have to sort there, which is an additional
cost. As far as I can tell, using a non-deterministic order is fine there,
but that's a brittle nonlocal property which I'd like to avoid.

Additionally, dep_finsts is read from an interface file, so its "natural"
type is a list. Which makes it a natural type for imp_finsts.

Since rnImports.combine is really the only place that would benefit from
it being a Set, it makes sense to optimize the hot loop in rnImports.combine
without changing the representation.

So here's what we do: instead of naively merging ImportAvails with
plusImportAvails in a loop, we make plusImportAvails merge empty imp_finsts
and compute the union on the side using Sets. When we're done, we can
convert it back to a list. One nice side effect of this approach is that
if there's a lot of overlap in the imp_finsts of imports, the
Set doesn't really need to grow and we don't need to allocate.

Running generateModules from #14693 with DEPTH=16, WIDTH=30 finishes in
23s before, and 11s after.
-}



-- | Given a located import declaration @decl@ from @this_mod@,
-- calculate the following pieces of information:
--
--  1. An updated 'LImportDecl', where all unresolved 'RdrName' in
--     the entity lists have been resolved into 'Name's,
--
--  2. A 'GlobalRdrEnv' representing the new identifiers that were
--     brought into scope (taking into account module qualification
--     and hiding),
--
--  3. 'ImportAvails' summarizing the identifiers that were imported
--     by this declaration, and
--
--  4. A boolean 'AnyHpcUsage' which is true if the imported module
--     used HPC.
rnImportDecl  :: Module -> (LImportDecl GhcPs, SDoc)
             -> RnM (LImportDecl GhcRn, GlobalRdrEnv, ImportAvails, AnyHpcUsage)
rnImportDecl this_mod
             (L loc decl@(ImportDecl { ideclName = loc_imp_mod_name
                                     , ideclPkgQual = raw_pkg_qual
                                     , ideclSource = want_boot, ideclSafe = mod_safe
                                     , ideclQualified = qual_style
                                     , ideclExt = XImportDeclPass { ideclImplicit = implicit }
                                     , ideclAs = as_mod, ideclImportList = imp_details }), import_reason)
  = setSrcSpanA loc $ do

    case raw_pkg_qual of
      NoRawPkgQual -> pure ()
      RawPkgQual _ -> do
        pkg_imports <- xoptM LangExt.PackageImports
        when (not pkg_imports) $ addErr packageImportErr

    let qual_only = isImportDeclQualified qual_style

    -- If there's an error in loadInterface, (e.g. interface
    -- file not found) we get lots of spurious errors from 'filterImports'
    let imp_mod_name = unLoc loc_imp_mod_name
        doc = ppr imp_mod_name <+> import_reason

    hsc_env <- getTopEnv
    unit_env <- hsc_unit_env <$> getTopEnv
    let pkg_qual = renameRawPkgQual unit_env imp_mod_name raw_pkg_qual

    -- Check for self-import, which confuses the typechecker (#9032)
    -- ghc --make rejects self-import cycles already, but batch-mode may not
    -- at least not until GHC.IfaceToCore.tcHiBootIface, which is too late to avoid
    -- typechecker crashes.  (Indirect self imports are not caught until
    -- GHC.IfaceToCore, see #10337 tracking how to make this error better.)
    --
    -- Originally, we also allowed 'import {-# SOURCE #-} M', but this
    -- caused bug #10182: in one-shot mode, we should never load an hs-boot
    -- file for the module we are compiling into the EPS.  In principle,
    -- it should be possible to support this mode of use, but we would have to
    -- extend Provenance to support a local definition in a qualified location.
    -- For now, we don't support it, but see #10336
    when (imp_mod_name == moduleName this_mod &&
          (case pkg_qual of -- If we have import "<pkg>" M, then we should
                            -- check that "<pkg>" is "this" (which is magic)
                            -- or the name of this_mod's package.  Yurgh!
                            -- c.f. GHC.findModule, and #9997
             NoPkgQual         -> True
             ThisPkg uid       -> uid == homeUnitId_ (hsc_dflags hsc_env)
             OtherPkg _        -> False))
         (addErr $ mkTcRnUnknownMessage $ mkPlainError noHints $
           (text "A module cannot import itself:" <+> ppr imp_mod_name))

    -- Check for a missing import list (Opt_WarnMissingImportList also
    -- checks for T(..) items but that is done in checkDodgyImport below)
    case imp_details of
        Just (Exactly, _) -> return () -- Explicit import list
        _  | implicit   -> return () -- Do not bleat for implicit imports
           | qual_only  -> return ()
           | otherwise  -> whenWOptM Opt_WarnMissingImportList $ do
                             let msg = mkTcRnUnknownMessage $
                                   mkPlainDiagnostic (WarningWithFlag Opt_WarnMissingImportList)
                                                     noHints
                                                     (missingImportListWarn imp_mod_name)
                             addDiagnostic msg


    iface <- loadSrcInterface doc imp_mod_name want_boot pkg_qual

    -- Compiler sanity check: if the import didn't say
    -- {-# SOURCE #-} we should not get a hi-boot file
    warnPprTrace ((want_boot == NotBoot) && (mi_boot iface == IsBoot)) "rnImportDecl" (ppr imp_mod_name) $ do

    -- Issue a user warning for a redundant {- SOURCE -} import
    -- NB that we arrange to read all the ordinary imports before
    -- any of the {- SOURCE -} imports.
    --
    -- in --make and GHCi, the compilation manager checks for this,
    -- and indeed we shouldn't do it here because the existence of
    -- the non-boot module depends on the compilation order, which
    -- is not deterministic.  The hs-boot test can show this up.
    dflags <- getDynFlags
    warnIf ((want_boot == IsBoot) && (mi_boot iface == NotBoot) && isOneShot (ghcMode dflags))
           (warnRedundantSourceImport imp_mod_name)
    when (mod_safe && not (safeImportsOn dflags)) $
        addErr $ mkTcRnUnknownMessage $ mkPlainError noHints $
          (text "safe import can't be used as Safe Haskell isn't on!"
                $+$ text ("please enable Safe Haskell through either Safe, Trustworthy or Unsafe"))

    let
        qual_mod_name = fmap unLoc as_mod `orElse` imp_mod_name
        imp_spec  = ImpDeclSpec { is_mod = imp_mod_name, is_qual = qual_only,
                                  is_dloc = locA loc, is_as = qual_mod_name }

    -- filter the imports according to the import declaration
    (new_imp_details, gres) <- filterImports iface imp_spec imp_details

    -- for certain error messages, we’d like to know what could be imported
    -- here, if everything were imported
    potential_gres <- mkGlobalRdrEnv . snd <$> filterImports iface imp_spec Nothing

    let gbl_env = mkGlobalRdrEnv gres

        is_hiding | Just (EverythingBut,_) <- imp_details = True
                  | otherwise                             = False

        -- should the import be safe?
        mod_safe' = mod_safe
                    || (not implicit && safeDirectImpsReq dflags)
                    || (implicit && safeImplicitImpsReq dflags)

    hsc_env <- getTopEnv
    let home_unit = hsc_home_unit hsc_env
        other_home_units = hsc_all_home_unit_ids hsc_env
        imv = ImportedModsVal
            { imv_name        = qual_mod_name
            , imv_span        = locA loc
            , imv_is_safe     = mod_safe'
            , imv_is_hiding   = is_hiding
            , imv_all_exports = potential_gres
            , imv_qualified   = qual_only
            }
        imports = calculateAvails home_unit other_home_units iface mod_safe' want_boot (ImportedByUser imv)

    -- Complain if we import a deprecated module
    case mi_warns iface of
       WarnAll txt -> do
         let msg = mkTcRnUnknownMessage $
               mkPlainDiagnostic (WarningWithFlag Opt_WarnWarningsDeprecations)
                                 noHints
                                 (moduleWarn imp_mod_name txt)
         addDiagnostic msg
       _           -> return ()

    -- Complain about -Wcompat-unqualified-imports violations.
    warnUnqualifiedImport decl iface

    let new_imp_decl = ImportDecl
          { ideclExt       = ideclExt decl
          , ideclName      = ideclName decl
          , ideclPkgQual   = pkg_qual
          , ideclSource    = ideclSource decl
          , ideclSafe      = mod_safe'
          , ideclQualified = ideclQualified decl
          , ideclAs        = ideclAs decl
          , ideclImportList = new_imp_details
          }

    return (L loc new_imp_decl, gbl_env, imports, mi_hpc iface)


-- | Rename raw package imports
renameRawPkgQual :: UnitEnv -> ModuleName -> RawPkgQual -> PkgQual
renameRawPkgQual unit_env mn = \case
  NoRawPkgQual -> NoPkgQual
  RawPkgQual p -> renamePkgQual unit_env mn (Just (sl_fs p))

-- | Rename raw package imports
renamePkgQual :: UnitEnv -> ModuleName -> Maybe FastString -> PkgQual
renamePkgQual unit_env mn mb_pkg = case mb_pkg of
  Nothing -> NoPkgQual
  Just pkg_fs
    | Just uid <- homeUnitId <$> ue_homeUnit unit_env
    , pkg_fs == fsLit "this"
    -> ThisPkg uid

    | Just (uid, _) <- find (fromMaybe False . fmap (== pkg_fs) . snd) home_names
    -> ThisPkg uid

    | Just uid <- resolvePackageImport (ue_units unit_env) mn (PackageName pkg_fs)
    -> OtherPkg uid

    | otherwise
    -> OtherPkg (UnitId pkg_fs)
       -- not really correct as pkg_fs is unlikely to be a valid unit-id but
       -- we will report the failure later...
  where
    home_names  = map (\uid -> (uid, mkFastString <$> thisPackageName (homeUnitEnv_dflags (ue_findHomeUnitEnv uid unit_env)))) hpt_deps

    units = ue_units unit_env

    hpt_deps :: [UnitId]
    hpt_deps  = homeUnitDepends units


-- | Calculate the 'ImportAvails' induced by an import of a particular
-- interface, but without 'imp_mods'.
calculateAvails :: HomeUnit
                -> S.Set UnitId
                -> ModIface
                -> IsSafeImport
                -> IsBootInterface
                -> ImportedBy
                -> ImportAvails
calculateAvails home_unit other_home_units iface mod_safe' want_boot imported_by =
  let imp_mod    = mi_module iface
      imp_sem_mod= mi_semantic_module iface
      orph_iface = mi_orphan (mi_final_exts iface)
      has_finsts = mi_finsts (mi_final_exts iface)
      deps       = mi_deps iface
      trust      = getSafeMode $ mi_trust iface
      trust_pkg  = mi_trust_pkg iface
      is_sig     = mi_hsc_src iface == HsigFile

      -- If the module exports anything defined in this module, just
      -- ignore it.  Reason: otherwise it looks as if there are two
      -- local definition sites for the thing, and an error gets
      -- reported.  Easiest thing is just to filter them out up
      -- front. This situation only arises if a module imports
      -- itself, or another module that imported it.  (Necessarily,
      -- this involves a loop.)
      --
      -- We do this *after* filterImports, so that if you say
      --      module A where
      --         import B( AType )
      --         type AType = ...
      --
      --      module B( AType ) where
      --         import {-# SOURCE #-} A( AType )
      --
      -- then you won't get a 'B does not export AType' message.


      -- Compute new transitive dependencies
      --
      -- 'dep_orphs' and 'dep_finsts' do NOT include the imported module
      -- itself, but we DO need to include this module in 'imp_orphs' and
      -- 'imp_finsts' if it defines an orphan or instance family; thus the
      -- orph_iface/has_iface tests.

      deporphs  = dep_orphs deps
      depfinsts = dep_finsts deps

      orphans | orph_iface = assertPpr (not (imp_sem_mod `elem` deporphs)) (ppr imp_sem_mod <+> ppr deporphs) $
                             imp_sem_mod : deporphs
              | otherwise  = deporphs

      finsts | has_finsts = assertPpr (not (imp_sem_mod `elem` depfinsts)) (ppr imp_sem_mod <+> ppr depfinsts) $
                            imp_sem_mod : depfinsts
             | otherwise  = depfinsts

      -- Trusted packages are a lot like orphans.
      trusted_pkgs | mod_safe' = dep_trusted_pkgs deps
                   | otherwise = S.empty


      pkg = moduleUnit (mi_module iface)
      ipkg = toUnitId pkg

      -- Does this import mean we now require our own pkg
      -- to be trusted? See Note [Trust Own Package]
      ptrust = trust == Sf_Trustworthy || trust_pkg
      pkg_trust_req
        | isHomeUnit home_unit pkg = ptrust
        | otherwise = False

      dependent_pkgs = if toUnitId pkg `S.member` other_home_units
                        then S.empty
                        else S.singleton ipkg

      direct_mods = mkModDeps $ if toUnitId pkg `S.member` other_home_units
                      then S.singleton (moduleUnitId imp_mod, (GWIB (moduleName imp_mod) want_boot))
                      else S.empty

      dep_boot_mods_map = mkModDeps (dep_boot_mods deps)

      boot_mods
        -- If we are looking for a boot module, it must be HPT
        | IsBoot <- want_boot = extendInstalledModuleEnv dep_boot_mods_map (toUnitId <$> imp_mod) (GWIB (moduleName imp_mod) IsBoot)
        -- Now we are importing A properly, so don't go looking for
        -- A.hs-boot
        | isHomeUnit home_unit pkg = dep_boot_mods_map
        -- There's no boot files to find in external imports
        | otherwise = emptyInstalledModuleEnv

      sig_mods =
        if is_sig
          then moduleName imp_mod : dep_sig_mods deps
          else dep_sig_mods deps


  in ImportAvails {
          imp_mods       = unitModuleEnv (mi_module iface) [imported_by],
          imp_orphs      = orphans,
          imp_finsts     = finsts,
          imp_sig_mods   = sig_mods,
          imp_direct_dep_mods = direct_mods,
          imp_dep_direct_pkgs = dependent_pkgs,
          imp_boot_mods = boot_mods,

          -- Add in the imported modules trusted package
          -- requirements. ONLY do this though if we import the
          -- module as a safe import.
          -- See Note [Tracking Trust Transitively]
          -- and Note [Trust Transitive Property]
          imp_trust_pkgs = trusted_pkgs,
          -- Do we require our own pkg to be trusted?
          -- See Note [Trust Own Package]
          imp_trust_own_pkg = pkg_trust_req
     }


-- | Issue a warning if the user imports Data.List without either an import
-- list or `qualified`. This is part of the migration plan for the
-- `Data.List.singleton` proposal. See #17244.
warnUnqualifiedImport :: ImportDecl GhcPs -> ModIface -> RnM ()
warnUnqualifiedImport decl iface =
    when bad_import $ do
      let msg = mkTcRnUnknownMessage $
            mkPlainDiagnostic (WarningWithFlag Opt_WarnCompatUnqualifiedImports)
                              noHints
                              warning
      addDiagnosticAt loc msg
  where
    mod = mi_module iface
    loc = getLocA $ ideclName decl

    is_qual = isImportDeclQualified (ideclQualified decl)
    has_import_list =
      -- We treat a `hiding` clause as not having an import list although
      -- it's not entirely clear this is the right choice.
      case ideclImportList decl of
        Just (Exactly, _) -> True
        _               -> False
    bad_import =
         not is_qual
      && not has_import_list
      && mod `elemModuleSet` qualifiedMods

    warning = vcat
      [ text "To ensure compatibility with future core libraries changes"
      , text "imports to" <+> ppr (ideclName decl) <+> text "should be"
      , text "either qualified or have an explicit import list."
      ]

    -- Modules for which we warn if we see unqualified imports
    qualifiedMods = mkModuleSet [ dATA_LIST ]


warnRedundantSourceImport :: ModuleName -> TcRnMessage
warnRedundantSourceImport mod_name
  = mkTcRnUnknownMessage $ mkPlainDiagnostic WarningWithoutFlag noHints $
      text "Unnecessary {-# SOURCE #-} in the import of module" <+> quotes (ppr mod_name)

{-
************************************************************************
*                                                                      *
\subsection{importsFromLocalDecls}
*                                                                      *
************************************************************************

From the top-level declarations of this module produce
        * the lexical environment
        * the ImportAvails
created by its bindings.

Note [Top-level Names in Template Haskell decl quotes]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
See also: Note [Interactively-bound Ids in GHCi] in GHC.Driver.Env
          Note [Looking up Exact RdrNames] in GHC.Rename.Env

Consider a Template Haskell declaration quotation like this:
      module M where
        f x = h [d| f = 3 |]
When renaming the declarations inside [d| ...|], we treat the
top level binders specially in two ways

1.  We give them an Internal Name, not (as usual) an External one.
    This is done by GHC.Rename.Env.newTopSrcBinder.

2.  We make them *shadow* the outer bindings.
    See Note [GlobalRdrEnv shadowing]

3. We find out whether we are inside a [d| ... |] by testing the TH
   stage. This is a slight hack, because the stage field was really
   meant for the type checker, and here we are not interested in the
   fields of Brack, hence the error thunks in thRnBrack.
-}

extendGlobalRdrEnvRn :: [AvailInfo]
                     -> MiniFixityEnv
                     -> RnM (TcGblEnv, TcLclEnv)
-- Updates both the GlobalRdrEnv and the FixityEnv
-- We return a new TcLclEnv only because we might have to
-- delete some bindings from it;
-- see Note [Top-level Names in Template Haskell decl quotes]

extendGlobalRdrEnvRn avails new_fixities
  = checkNoErrs $  -- See Note [Fail fast on duplicate definitions]
    do  { (gbl_env, lcl_env) <- getEnvs
        ; stage <- getStage
        ; isGHCi <- getIsGHCi
        ; let rdr_env  = tcg_rdr_env gbl_env
              fix_env  = tcg_fix_env gbl_env
              th_bndrs = tcl_th_bndrs lcl_env
              th_lvl   = thLevel stage

              -- Delete new_occs from global and local envs
              -- If we are in a TemplateHaskell decl bracket,
              --    we are going to shadow them
              -- See Note [GlobalRdrEnv shadowing]
              inBracket = isBrackStage stage

              lcl_env_TH = lcl_env { tcl_rdr = minusLocalRdrEnv (tcl_rdr lcl_env) new_occs }
                           -- See Note [GlobalRdrEnv shadowing]

              lcl_env2 | inBracket = lcl_env_TH
                       | otherwise = lcl_env

              -- Deal with shadowing: see Note [GlobalRdrEnv shadowing]
              want_shadowing = isGHCi || inBracket
              rdr_env1 | want_shadowing = shadowNames rdr_env new_occs
                       | otherwise      = rdr_env

              lcl_env3 = lcl_env2 { tcl_th_bndrs = extendNameEnvList th_bndrs
                                                       [ ( greNameMangledName n
                                                         , (TopLevel, th_lvl) )
                                                       | n <- new_names ] }

        ; rdr_env2 <- foldlM add_gre rdr_env1 new_gres

        ; let fix_env' = foldl' extend_fix_env fix_env new_gres
              gbl_env' = gbl_env { tcg_rdr_env = rdr_env2, tcg_fix_env = fix_env' }

        ; traceRn "extendGlobalRdrEnvRn 2" (pprGlobalRdrEnv True rdr_env2)
        ; return (gbl_env', lcl_env3) }
  where
    new_names = concatMap availGreNames avails
    new_occs  = occSetToEnv (mkOccSet (map occName new_names))

    -- If there is a fixity decl for the gre, add it to the fixity env
    extend_fix_env fix_env gre
      | Just (L _ fi) <- lookupFsEnv new_fixities (occNameFS occ)
      = extendNameEnv fix_env name (FixItem occ fi)
      | otherwise
      = fix_env
      where
        name = greMangledName gre
        occ  = greOccName gre

    new_gres :: [GlobalRdrElt]  -- New LocalDef GREs, derived from avails
    new_gres = concatMap localGREsFromAvail avails

    add_gre :: GlobalRdrEnv -> GlobalRdrElt -> RnM GlobalRdrEnv
    -- Extend the GlobalRdrEnv with a LocalDef GRE
    -- If there is already a LocalDef GRE with the same OccName,
    --    report an error and discard the new GRE
    -- This establishes INVARIANT 1 of GlobalRdrEnvs
    add_gre env gre
      | not (null dups)    -- Same OccName defined twice
      = do { addDupDeclErr (gre :| dups); return env }

      | otherwise
      = return (extendGlobalRdrEnv env gre)
      where
        -- See Note [Reporting duplicate local declarations]
        dups = filter isDupGRE (lookupGlobalRdrEnv env (greOccName gre))
        isDupGRE gre' = isLocalGRE gre' && not (isAllowedDup gre')
        isAllowedDup gre' =
            case (isRecFldGRE gre, isRecFldGRE gre') of
              (True,  True)  -> gre_name gre /= gre_name gre'
                                  && isDuplicateRecFldGRE gre'
              (True,  False) -> isNoFieldSelectorGRE gre
              (False, True)  -> isNoFieldSelectorGRE gre'
              (False, False) -> False

{- Note [Fail fast on duplicate definitions]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
If there are duplicate bindings for the same thing, we want to fail
fast. Having two bindings for the same thing can cause follow-on errors.
Example (test T9975a):
   data Test = Test { x :: Int }
   pattern Test wat = Test { x = wat }
This defines 'Test' twice.  The second defn has no field-names; and then
we get an error from Test { x=wat }, saying "Test has no field 'x'".

Easiest thing is to bale out fast on duplicate definitions, which
we do via `checkNoErrs` on `extendGlobalRdrEnvRn`.

Note [Reporting duplicate local declarations]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In general, a single module may not define the same OccName multiple times. This
is checked in extendGlobalRdrEnvRn: when adding a new locally-defined GRE to the
GlobalRdrEnv we report an error if there are already duplicates in the
environment.  This establishes INVARIANT 1 (see comments on GlobalRdrEnv in
GHC.Types.Name.Reader), which says that for a given OccName, all the
GlobalRdrElts to which it maps must have distinct 'gre_name's.

For example, the following will be rejected:

  f x = x
  g x = x
  f x = x  -- Duplicate!

Two GREs with the same OccName are OK iff:
-------------------------------------------------------------------
  Existing GRE     |          Newly-defined GRE
                   |  NormalGre            FieldGre
-------------------------------------------------------------------
  Imported         |  Always               Always
                   |
  Local NormalGre  |  Never                NoFieldSelectors
                   |
  Local FieldGre   |  NoFieldSelectors     DuplicateRecordFields
                   |                       and not in same record
-------------------------------------------------------------------            -
In this table "NoFieldSelectors" means "NoFieldSelectors was enabled at the
definition site of the fields; ditto "DuplicateRecordFields".  These facts are
recorded in the 'FieldLabel' (but where both GREs are local, both will
necessarily have the same extensions enabled).

More precisely:

* The programmer is allowed to make a new local definition that clashes with an
  imported one (although attempting to refer to either may lead to ambiguity
  errors at use sites).  For example, the following definition is allowed:

    import M (f)
    f x = x

  Thus isDupGRE reports errors only if the existing GRE is a LocalDef.

* When DuplicateRecordFields is enabled, the same field label may be defined in
  multiple records. For example, this is allowed:

    {-# LANGUAGE DuplicateRecordFields #-}
    data S1 = MkS1 { f :: Int }
    data S2 = MkS2 { f :: Int }

  Even though both fields have the same OccName, this does not violate INVARIANT
  1 of the GlobalRdrEnv, because the fields have distinct selector names, which
  form part of the gre_name (see Note [GreNames] in GHC.Types.Name.Reader).

* However, we must be careful to reject the following (#9156):

    {-# LANGUAGE DuplicateRecordFields #-}
    data T = MkT { f :: Int, f :: Int }  -- Duplicate!

  In this case, both 'gre_name's are the same (because the fields belong to the
  same type), and adding them both to the environment would be a violation of
  INVARIANT 1. Thus isAllowedDup checks both GREs have distinct 'gre_name's
  if they are both record fields.

* With DuplicateRecordFields, we reject attempts to define a field and a
  non-field with the same OccName (#17965):

    {-# LANGUAGE DuplicateRecordFields #-}
    f x = x
    data T = MkT { f :: Int}

  In principle this could be supported, but the current "specification" of
  DuplicateRecordFields does not allow it. Thus isAllowedDup checks for
  DuplicateRecordFields only if *both* GREs being compared are record fields.

* However, with NoFieldSelectors, it is possible by design to define a field and
  a non-field with the same OccName:

    {-# LANGUAGE NoFieldSelectors #-}
    f x = x
    data T = MkT { f :: Int}

  Thus isAllowedDup checks for NoFieldSelectors if either the existing or the
  new GRE are record fields.  See Note [NoFieldSelectors] in GHC.Rename.Env.

See also Note [Skipping ambiguity errors at use sites of local declarations] in
GHC.Rename.Utils.
-}


{- *********************************************************************
*                                                                      *
    getLocalDeclBindersd@ returns the names for an HsDecl
             It's used for source code.

        *** See Note [The Naming story] in GHC.Hs.Decls ****
*                                                                      *
********************************************************************* -}

getLocalNonValBinders :: MiniFixityEnv -> HsGroup GhcPs
    -> RnM ((TcGblEnv, TcLclEnv), NameSet)
-- Get all the top-level binders bound the group *except*
-- for value bindings, which are treated separately
-- Specifically we return AvailInfo for
--      * type decls (incl constructors and record selectors)
--      * class decls (including class ops)
--      * associated types
--      * foreign imports
--      * value signatures (in hs-boot files only)

getLocalNonValBinders fixity_env
     (HsGroup { hs_valds  = binds,
                hs_tyclds = tycl_decls,
                hs_fords  = foreign_decls })
  = do  { -- Process all type/class decls *except* family instances
        ; let inst_decls = tycl_decls >>= group_instds
        ; dup_fields_ok <- xopt_DuplicateRecordFields <$> getDynFlags
        ; has_sel <- xopt_FieldSelectors <$> getDynFlags
        ; (tc_avails, tc_fldss)
            <- fmap unzip $ mapM (new_tc dup_fields_ok has_sel)
                                 (tyClGroupTyClDecls tycl_decls)
        ; traceRn "getLocalNonValBinders 1" (ppr tc_avails)
        ; envs <- extendGlobalRdrEnvRn tc_avails fixity_env
        ; restoreEnvs envs $ do {
            -- Bring these things into scope first
            -- See Note [Looking up family names in family instances]

          -- Process all family instances
          -- to bring new data constructors into scope
        ; (nti_availss, nti_fldss) <- mapAndUnzipM (new_assoc dup_fields_ok has_sel)
                                                   inst_decls

          -- Finish off with value binders:
          --    foreign decls and pattern synonyms for an ordinary module
          --    type sigs in case of a hs-boot file only
        ; is_boot <- tcIsHsBootOrSig
        ; let val_bndrs
                | is_boot = case binds of
                      ValBinds _ _val_binds val_sigs ->
                          -- In a hs-boot file, the value binders come from the
                          --  *signatures*, and there should be no foreign binders
                          [ L (l2l decl_loc) (unLoc n)
                          | L decl_loc (TypeSig _ ns _) <- val_sigs, n <- ns]
                      _ -> panic "Non-ValBinds in hs-boot group"
                | otherwise = for_hs_bndrs
        ; val_avails <- mapM new_simple val_bndrs

        ; let avails    = concat nti_availss ++ val_avails
              new_bndrs = availsToNameSetWithSelectors avails `unionNameSet`
                          availsToNameSetWithSelectors tc_avails
              flds      = concat nti_fldss ++ concat tc_fldss
        ; traceRn "getLocalNonValBinders 2" (ppr avails)
        ; (tcg_env, tcl_env) <- extendGlobalRdrEnvRn avails fixity_env

        -- Force the field access so that tcg_env is not retained. The
        -- selector thunk optimisation doesn't kick-in, see #20139
        ; let !old_field_env = tcg_con_env tcg_env
        -- Extend tcg_con_env with new fields (this used to be the
        -- work of extendRecordFieldEnv)
              field_env = extendNameEnvList old_field_env flds
              envs      = (tcg_env { tcg_con_env = field_env }, tcl_env)

        ; traceRn "getLocalNonValBinders 3" (vcat [ppr flds, ppr field_env])
        ; return (envs, new_bndrs) } }
  where
    for_hs_bndrs :: [LocatedN RdrName]
    for_hs_bndrs = hsForeignDeclsBinders foreign_decls

      -- the SrcSpan attached to the input should be the span of the
      -- declaration, not just the name
    new_simple :: LocatedN RdrName -> RnM AvailInfo
    new_simple rdr_name = do{ nm <- newTopSrcBinder rdr_name
                            ; return (avail nm) }

    new_tc :: DuplicateRecordFields -> FieldSelectors -> LTyClDecl GhcPs
           -> RnM (AvailInfo, [(Name, ConInfo)])
    new_tc dup_fields_ok has_sel tc_decl -- NOT for type/data instances
        = do { let (bndrs, flds) = hsLTyClDeclBinders tc_decl
             ; names@(main_name : sub_names) <- mapM (newTopSrcBinder . l2n) bndrs
             ; flds' <- mapM (newRecordSelector dup_fields_ok has_sel sub_names) flds
             ; let fld_env = case unLoc tc_decl of
                     DataDecl { tcdDataDefn = d } -> mk_con_env d names flds'
                     _                            -> []
             ; return (availTC main_name names flds', fld_env) }


    -- Calculate the mapping from constructor names to arity and fields, which
    -- will go in tcg_con_env. It's convenient to do this here where
    -- we are working with a single datatype definition.
    -- For more details, see Note [Local constructor info in the renamer]
    mk_con_env :: HsDataDefn GhcPs -> [Name] -> [FieldLabel]
               -> [(Name, ConInfo)]
    mk_con_env d names flds = concatMap find_con_flds (dd_cons d)
      where
        find_con_flds :: GenLocated l (ConDecl GhcPs) -> [(Name, ConInfo)]
        find_con_flds (L _ (ConDeclH98 { con_name = L _ rdr
                                       , con_args = con_det }))
            = [( find_con_name rdr
               , con_det_con_info con_det
               )]
        find_con_flds (L _ (ConDeclGADT { con_names = rdrs
                                        , con_g_args = con_gadt_det }))
            = [ ( find_con_name rdr
                , gadt_det_con_info con_gadt_det
                )
              | L _ rdr <- toList rdrs ]

        find_con_name rdr
          = expectJust "getLocalNonValBinders/find_con_name" $
              find (\ n -> nameOccName n == rdrNameOcc rdr) names

        con_det_con_info
          :: HsConDetails Void (HsScaled GhcPs (GenLocated SrcSpanAnnA (HsType GhcPs))) (GenLocated SrcSpanAnnL [GenLocated SrcSpanAnnA (ConDeclField GhcPs)])
          -> ConInfo
        con_det_con_info con_det =
          let
            (arity, fields) =
              case con_det of
                PrefixCon _ args ->
                  (length args, [])
                RecCon cdflds ->
                  ((find_con_decl_field_arity . unLoc) cdflds, concatMap find_con_decl_flds $ unLoc cdflds)
                InfixCon _ _ ->
                  (2, [])
           in
            mkConInfo
              arity
              fields

        gadt_det_con_info :: HsConDeclGADTDetails GhcPs -> ConInfo
        gadt_det_con_info con_gadt_det =
          let
            (arity, fields) =
              case con_gadt_det of
                PrefixConGADT args ->
                  (length args, [])
                RecConGADT (L _ args) _ ->
                  (find_con_decl_field_arity args, concatMap find_con_decl_flds args)
           in
            mkConInfo
              arity
              fields

        find_con_decl_flds :: GenLocated l (ConDeclField GhcPs) -> [FieldLabel]
        find_con_decl_flds (L _ x)
          = map find_con_decl_fld (cd_fld_names x)

        find_con_decl_fld  (L _ (FieldOcc _ (L _ rdr)))
          = expectJust "getLocalNonValBinders/find_con_decl_fld" $
              find (\ fl -> flLabel fl == lbl) flds
          where lbl = FieldLabelString $ occNameFS (rdrNameOcc rdr)

        find_con_decl_field_arity :: [GenLocated SrcSpanAnnA (ConDeclField GhcPs)] -> Arity
        find_con_decl_field_arity = length . concatMap (cd_fld_names . unLoc)

    new_assoc :: DuplicateRecordFields -> FieldSelectors -> LInstDecl GhcPs
              -> RnM ([AvailInfo], [(Name, ConInfo)])
    new_assoc _ _ (L _ (TyFamInstD {})) = return ([], [])
      -- type instances don't bind new names

    new_assoc dup_fields_ok has_sel (L _ (DataFamInstD _ d))
      = do { (avail, arityAndFlds) <- new_di dup_fields_ok has_sel Nothing d
           ; return ([avail], arityAndFlds) }
    new_assoc dup_fields_ok has_sel (L _ (ClsInstD _ (ClsInstDecl { cid_poly_ty = inst_ty
                                                      , cid_datafam_insts = adts })))
      = do -- First, attempt to grab the name of the class from the instance.
           -- This step could fail if the instance is not headed by a class,
           -- such as in the following examples:
           --
           -- (1) The class is headed by a bang pattern, such as in
           --     `instance !Show Int` (#3811c)
           -- (2) The class is headed by a type variable, such as in
           --     `instance c` (#16385)
           --
           -- If looking up the class name fails, then mb_cls_nm will
           -- be Nothing.
           mb_cls_nm <- runMaybeT $ do
             -- See (1) above
             L loc cls_rdr <- MaybeT $ pure $ getLHsInstDeclClass_maybe inst_ty
             -- See (2) above
             MaybeT $ setSrcSpan (locA loc) $ lookupGlobalOccRn_maybe cls_rdr
           -- Assuming the previous step succeeded, process any associated data
           -- family instances. If the previous step failed, bail out.
           case mb_cls_nm of
             Nothing -> pure ([], [])
             Just cls_nm -> do
               (avails, fldss)
                 <- mapAndUnzipM (new_loc_di dup_fields_ok has_sel (Just cls_nm)) adts
               pure (avails, concat fldss)

    new_di :: DuplicateRecordFields -> FieldSelectors -> Maybe Name -> DataFamInstDecl GhcPs
                   -> RnM (AvailInfo, [(Name, ConInfo)])
    new_di dup_fields_ok has_sel mb_cls dfid@(DataFamInstDecl { dfid_eqn = ti_decl })
        = do { main_name <- lookupFamInstName mb_cls (feqn_tycon ti_decl)
             ; let (bndrs, flds) = hsDataFamInstBinders dfid
             ; sub_names <- mapM (newTopSrcBinder .l2n) bndrs
             ; flds' <- mapM (newRecordSelector dup_fields_ok has_sel sub_names) flds
             ; let avail    = availTC (unLoc main_name) sub_names flds'
                                  -- main_name is not bound here!
                   fld_env  = mk_con_env (feqn_rhs ti_decl) sub_names flds'
             ; return (avail, fld_env) }

    new_loc_di :: DuplicateRecordFields -> FieldSelectors -> Maybe Name -> LDataFamInstDecl GhcPs
                   -> RnM (AvailInfo, [(Name, ConInfo)])
    new_loc_di dup_fields_ok has_sel mb_cls (L _ d) = new_di dup_fields_ok has_sel mb_cls d

newRecordSelector :: DuplicateRecordFields -> FieldSelectors -> [Name] -> LFieldOcc GhcPs -> RnM FieldLabel
newRecordSelector _ _ [] _ = error "newRecordSelector: datatype has no constructors!"
newRecordSelector dup_fields_ok has_sel (dc:_) (L loc (FieldOcc _ (L _ fld)))
  = do { selName <- newTopSrcBinder $ L (l2l loc) $ field
       ; return $ FieldLabel { flLabel = fieldLabelString
                             , flHasDuplicateRecordFields = dup_fields_ok
                             , flHasFieldSelector = has_sel
                             , flSelector = selName } }
  where
    fieldLabelString = FieldLabelString $ occNameFS $ rdrNameOcc fld
    selOccName = fieldSelectorOccName fieldLabelString (nameOccName dc) dup_fields_ok has_sel
    field | isExact fld = fld
              -- use an Exact RdrName as is to preserve the bindings
              -- of an already renamer-resolved field and its use
              -- sites. This is needed to correctly support record
              -- selectors in Template Haskell. See Note [Binders in
              -- Template Haskell] in "GHC.ThToHs" and Note [Looking up
              -- Exact RdrNames] in "GHC.Rename.Env".
          | otherwise   = mkRdrUnqual selOccName

{-
Note [Looking up family names in family instances]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider

  module M where
    type family T a :: *
    type instance M.T Int = Bool

We might think that we can simply use 'lookupOccRn' when processing the type
instance to look up 'M.T'.  Alas, we can't!  The type family declaration is in
the *same* HsGroup as the type instance declaration.  Hence, as we are
currently collecting the binders declared in that HsGroup, these binders will
not have been added to the global environment yet.

Solution is simple: process the type family declarations first, extend
the environment, and then process the type instances.


************************************************************************
*                                                                      *
\subsection{Filtering imports}
*                                                                      *
************************************************************************

@filterImports@ takes the @ExportEnv@ telling what the imported module makes
available, and filters it through the import spec (if any).

Note [Dealing with imports]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
For import M( ies ), we take the mi_exports of M, and make
   imp_occ_env :: OccEnv (NameEnv (GreName, AvailInfo, Maybe Name))
One entry for each OccName that M exports, mapping each corresponding Name to
its GreName, the AvailInfo exported from M that exports that Name, and
optionally a Name for an associated type's parent class. (Typically there will
be a single Name in the NameEnv, but see Note [Importing DuplicateRecordFields]
for why we may need more than one.)

The situation is made more complicated by associated types. E.g.
   module M where
     class    C a    where { data T a }
     instance C Int  where { data T Int = T1 | T2 }
     instance C Bool where { data T Int = T3 }
Then M's export_avails are (recall the AvailTC invariant from Avails.hs)
  C(C,T), T(T,T1,T2,T3)
Notice that T appears *twice*, once as a child and once as a parent. From
this list we construct a raw list including
   T -> (T, T( T1, T2, T3 ), Nothing)
   T -> (T, C( C, T ),       Nothing)
and we combine these (in function 'combine' in 'imp_occ_env' in
'filterImports') to get
   T  -> (T,  T(T,T1,T2,T3), Just C)

So the overall imp_occ_env is
   C  -> (C,  C(C,T),        Nothing)
   T  -> (T,  T(T,T1,T2,T3), Just C)
   T1 -> (T1, T(T,T1,T2,T3), Nothing)   -- similarly T2,T3

If we say
   import M( T(T1,T2) )
then we get *two* Avails:  C(T), T(T1,T2)

Note that the imp_occ_env will have entries for data constructors too,
although we never look up data constructors.

Note [Importing PatternSynonyms]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As described in Note [Dealing with imports], associated types can lead to the
same Name appearing twice, both as a child and once as a parent, when
constructing the imp_occ_env.  The same thing can happen with pattern synonyms
if they are exported bundled with a type.

A simplified example, based on #11959:

  {-# LANGUAGE PatternSynonyms #-}
  module M (T(P), pattern P) where  -- Duplicate export warning, but allowed
    data T = MkT
    pattern P = MkT

Here we have T(P) and P in export_avails, and construct both
  P -> (P, P, Nothing)
  P -> (P, T(P), Nothing)
which are 'combine'd to leave
  P -> (P, T(P), Nothing)
i.e. we simply discard the non-bundled Avail.

Note [Importing DuplicateRecordFields]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In filterImports, another complicating factor is DuplicateRecordFields.
Suppose we have:

  {-# LANGUAGE DuplicateRecordFields #-}
  module M (S(foo), T(foo)) where
    data S = MkS { foo :: Int }
    data T = mkT { foo :: Int }

  module N where
    import M (foo)    -- this is allowed (A)
    import M (S(foo)) -- this is allowed (B)

Here M exports the OccName 'foo' twice, so we get an imp_occ_env where 'foo'
maps to a NameEnv containing an entry for each of the two mangled field selector
names (see Note [FieldLabel] in GHC.Types.FieldLabel).

  foo -> [ $sel:foo:MkS -> (foo, S(foo), Nothing)
         , $sel:foo:MKT -> (foo, T(foo), Nothing)
         ]

Then when we look up 'foo' in lookup_names for case (A) we get both entries and
hence two Avails.  Whereas in case (B) we reach the lookup_ie
case for IEThingWith, which looks up 'S' and then finds the unique 'foo' amongst
its children.

See T16745 for a test of this.

-}

filterImports
    :: ModIface
    -> ImpDeclSpec                     -- The span for the entire import decl
    -> Maybe (ImportListInterpretation, LocatedL [LIE GhcPs])    -- Import spec; True => hiding
    -> RnM (Maybe (ImportListInterpretation, LocatedL [LIE GhcRn]), -- Import spec w/ Names
            [GlobalRdrElt])                   -- Same again, but in GRE form
filterImports iface decl_spec Nothing
  = return (Nothing, gresFromAvails (Just imp_spec) (mi_exports iface))
  where
    imp_spec = ImpSpec { is_decl = decl_spec, is_item = ImpAll }


filterImports iface decl_spec (Just (want_hiding, L l import_items))
  = do  -- check for errors, convert RdrNames to Names
        items1 <- mapM lookup_lie import_items

        let items2 :: [(LIE GhcRn, AvailInfo)]
            items2 = concat items1
                -- NB the AvailInfo may have duplicates, and several items
                --    for the same parent; e.g N(x) and N(y)

            names  = availsToNameSetWithSelectors (map snd items2)
            keep n = not (n `elemNameSet` names)
            pruned_avails = filterAvails keep all_avails
            hiding_spec = ImpSpec { is_decl = decl_spec, is_item = ImpAll }

            gres | want_hiding == EverythingBut = gresFromAvails (Just hiding_spec) pruned_avails
                 | otherwise = concatMap (gresFromIE decl_spec) items2

        return (Just (want_hiding, L l (map fst items2)), gres)
  where
    all_avails = mi_exports iface

        -- See Note [Dealing with imports]
    imp_occ_env :: OccEnv (NameEnv (GreName,    -- the name or field
                           AvailInfo,   -- the export item providing it
                           Maybe Name))   -- the parent of associated types
    imp_occ_env = mkOccEnv_C (plusNameEnv_C combine)
                             [ (occName c, mkNameEnv [(greNameMangledName c, (c, a, Nothing))])
                                     | a <- all_avails
                                     , c <- availGreNames a]
    -- See Note [Dealing with imports]
    -- 'combine' may be called for associated data types which appear
    -- twice in the all_avails. In the example, we combine
    --    T(T,T1,T2,T3) and C(C,T)  to give   (T, T(T,T1,T2,T3), Just C)
    -- NB: the AvailTC can have fields as well as data constructors (#12127)
    combine :: (GreName, AvailInfo, Maybe Name)
            -> (GreName, AvailInfo, Maybe Name)
            -> (GreName, AvailInfo, Maybe Name)
    combine (NormalGreName name1, a1@(AvailTC p1 _), mb1)
            (NormalGreName name2, a2@(AvailTC p2 _), mb2)
      = assertPpr (name1 == name2 && isNothing mb1 && isNothing mb2)
                  (ppr name1 <+> ppr name2 <+> ppr mb1 <+> ppr mb2) $
        if p1 == name1 then (NormalGreName name1, a1, Just p2)
                       else (NormalGreName name1, a2, Just p1)
    -- 'combine' may also be called for pattern synonyms which appear both
    -- unassociated and associated (see Note [Importing PatternSynonyms]).
    combine (c1, a1, mb1) (c2, a2, mb2)
      = assertPpr (c1 == c2 && isNothing mb1 && isNothing mb2
                          && (isAvailTC a1 || isAvailTC a2))
                  (ppr c1 <+> ppr c2 <+> ppr a1 <+> ppr a2 <+> ppr mb1 <+> ppr mb2) $
        if isAvailTC a1 then (c1, a1, Nothing)
                        else (c1, a2, Nothing)

    isAvailTC AvailTC{} = True
    isAvailTC _ = False

    -- Look up a RdrName used in an import, failing if it is ambiguous
    -- (e.g. because it refers to multiple record fields)
    lookup_name :: IE GhcPs -> RdrName -> IELookupM (Name, AvailInfo, Maybe Name)
    lookup_name ie rdr = do
        xs <- lookup_names ie rdr
        case xs of
          [cax] -> return cax
          _     -> failLookupWith (AmbiguousImport rdr (map sndOf3 xs))

    -- Look up a RdrName used in an import, returning multiple values if there
    -- are several fields with the same name exposed by the module
    lookup_names :: IE GhcPs -> RdrName -> IELookupM [(Name, AvailInfo, Maybe Name)]
    lookup_names ie rdr
       | isQual rdr              = failLookupWith (QualImportError rdr)
       | Just succ <- mb_success = return $ map (\ (c,a,x) -> (greNameMangledName c, a, x)) (nonDetNameEnvElts succ)
       | otherwise               = failLookupWith (BadImport ie)
      where
        mb_success = lookupOccEnv imp_occ_env (rdrNameOcc rdr)

    lookup_lie :: LIE GhcPs -> TcRn [(LIE GhcRn, AvailInfo)]
    lookup_lie (L loc ieRdr)
        = do (stuff, warns) <- setSrcSpanA loc $
                               liftM (fromMaybe ([],[])) $
                               run_lookup (lookup_ie ieRdr)
             mapM_ emit_warning warns
             return [ (L loc ie, avail) | (ie,avail) <- stuff ]
        where
            -- Warn when importing T(..) if T was exported abstractly
            emit_warning (DodgyImport n) = whenWOptM Opt_WarnDodgyImports $
              addTcRnDiagnostic (TcRnDodgyImports n)
            emit_warning MissingImportList = whenWOptM Opt_WarnMissingImportList $
              addTcRnDiagnostic (TcRnMissingImportList ieRdr)
            emit_warning (BadImportW ie) = whenWOptM Opt_WarnDodgyImports $ do
              let msg = mkTcRnUnknownMessage $
                    mkPlainDiagnostic (WarningWithFlag Opt_WarnDodgyImports)
                                      noHints
                                      (lookup_err_msg (BadImport ie))
              addDiagnostic msg

            run_lookup :: IELookupM a -> TcRn (Maybe a)
            run_lookup m = case m of
              Failed err -> do
                addErr $ mkTcRnUnknownMessage $ mkPlainError noHints (lookup_err_msg err)
                return Nothing
              Succeeded a -> return (Just a)

            lookup_err_msg err = case err of
              BadImport ie  -> badImportItemErr iface decl_spec ie all_avails
              IllegalImport -> illegalImportItemErr
              QualImportError rdr -> qualImportItemErr rdr
              AmbiguousImport rdr xs -> ambiguousImportItemErr rdr xs

        -- For each import item, we convert its RdrNames to Names,
        -- and at the same time construct an AvailInfo corresponding
        -- to what is actually imported by this item.
        -- Returns Nothing on error.
        -- We return a list here, because in the case of an import
        -- item like C, if we are hiding, then C refers to *both* a
        -- type/class and a data constructor.  Moreover, when we import
        -- data constructors of an associated family, we need separate
        -- AvailInfos for the data constructors and the family (as they have
        -- different parents).  See Note [Dealing with imports]
    lookup_ie :: IE GhcPs
              -> IELookupM ([(IE GhcRn, AvailInfo)], [IELookupWarning])
    lookup_ie ie = handle_bad_import $
      case ie of
        IEVar _ (L l n) -> do
            -- See Note [Importing DuplicateRecordFields]
            xs <- lookup_names ie (ieWrappedName n)
            return ([(IEVar noExtField (L l (replaceWrappedName n name)),
                                                  trimAvail avail name)
                    | (name, avail, _) <- xs ], [])

        IEThingAll _ (L l tc) -> do
            (name, avail, mb_parent) <- lookup_name ie $ ieWrappedName tc
            let warns = case avail of
                          Avail {}                     -- e.g. f(..)
                            -> [DodgyImport $ ieWrappedName tc]

                          AvailTC _ subs
                            | null (drop 1 subs) -- e.g. T(..) where T is a synonym
                            -> [DodgyImport $ ieWrappedName tc]

                            | not (is_qual decl_spec)  -- e.g. import M( T(..) )
                            -> [MissingImportList]

                            | otherwise
                            -> []

                renamed_ie = IEThingAll noAnn (L l (replaceWrappedName tc name))
                sub_avails = case avail of
                               Avail {}           -> []
                               AvailTC name2 subs -> [(renamed_ie, AvailTC name2 (subs \\ [NormalGreName name]))]
            case mb_parent of
              Nothing     -> return ([(renamed_ie, avail)], warns)
                             -- non-associated ty/cls
              Just parent -> return ((renamed_ie, AvailTC parent [NormalGreName name]) : sub_avails, warns)
                             -- associated type

        IEThingAbs _ (L l tc')
            | want_hiding == EverythingBut   -- hiding ( C )
                       -- Here the 'C' can be a data constructor
                       --  *or* a type/class, or even both
            -> let tc = ieWrappedName tc'
                   tc_name = lookup_name ie tc
                   dc_name = lookup_name ie (setRdrNameSpace tc srcDataName)
               in
               case catIELookupM [ tc_name, dc_name ] of
                 []    -> failLookupWith (BadImport ie)
                 names -> return ([mkIEThingAbs tc' l name | name <- names], [])
            | otherwise
            -> do nameAvail <- lookup_name ie (ieWrappedName tc')
                  return ([mkIEThingAbs tc' l nameAvail]
                         , [])

        IEThingWith xt ltc@(L l rdr_tc) wc rdr_ns -> do
           (name, avail, mb_parent)
               <- lookup_name (IEThingAbs noAnn ltc) (ieWrappedName rdr_tc)

           -- Look up the children in the sub-names of the parent
           -- See Note [Importing DuplicateRecordFields]
           let subnames = availSubordinateGreNames avail
           case lookupChildren subnames rdr_ns of

             Failed rdrs -> failLookupWith (BadImport (IEThingWith xt ltc wc rdrs))
                                -- We are trying to import T( a,b,c,d ), and failed
                                -- to find 'b' and 'd'.  So we make up an import item
                                -- to report as failing, namely T( b, d ).
                                -- c.f. #15412

             Succeeded (childnames, childflds) ->
               case mb_parent of
                 -- non-associated ty/cls
                 Nothing
                   -> return ([(IEThingWith childflds (L l name') wc childnames',
                               availTC name (name:map unLoc childnames) (map unLoc childflds))],
                              [])
                   where name' = replaceWrappedName rdr_tc name
                         childnames' = map to_ie_post_rn childnames
                         -- childnames' = postrn_ies childnames
                 -- associated ty
                 Just parent
                   -> return ([(IEThingWith childflds (L l name') wc childnames',
                                availTC name (map unLoc childnames) (map unLoc childflds)),
                               (IEThingWith childflds (L l name') wc childnames',
                                availTC parent [name] [])],
                              [])
                   where name' = replaceWrappedName rdr_tc name
                         childnames' = map to_ie_post_rn childnames

        _other -> failLookupWith IllegalImport
        -- could be IEModuleContents, IEGroup, IEDoc, IEDocNamed
        -- all errors.

      where
        mkIEThingAbs tc l (n, av, Nothing    )
          = (IEThingAbs noAnn (L l (replaceWrappedName tc n)), trimAvail av n)
        mkIEThingAbs tc l (n, _,  Just parent)
          = (IEThingAbs noAnn (L l (replaceWrappedName tc n))
             , availTC parent [n] [])

        handle_bad_import m = catchIELookup m $ \err -> case err of
          BadImport ie | want_hiding == EverythingBut -> return ([], [BadImportW ie])
          _ -> failLookupWith err

type IELookupM = MaybeErr IELookupError

data IELookupWarning
  = BadImportW (IE GhcPs)
  | MissingImportList
  | DodgyImport RdrName
  -- NB. use the RdrName for reporting a "dodgy" import

data IELookupError
  = QualImportError RdrName
  | BadImport (IE GhcPs)
  | IllegalImport
  | AmbiguousImport RdrName [AvailInfo] -- e.g. a duplicated field name as a top-level import

failLookupWith :: IELookupError -> IELookupM a
failLookupWith err = Failed err

catchIELookup :: IELookupM a -> (IELookupError -> IELookupM a) -> IELookupM a
catchIELookup m h = case m of
  Succeeded r -> return r
  Failed err  -> h err

catIELookupM :: [IELookupM a] -> [a]
catIELookupM ms = [ a | Succeeded a <- ms ]

{-
************************************************************************
*                                                                      *
\subsection{Import/Export Utils}
*                                                                      *
************************************************************************
-}

-- | Given an import\/export spec, construct the appropriate 'GlobalRdrElt's.
gresFromIE :: ImpDeclSpec -> (LIE GhcRn, AvailInfo) -> [GlobalRdrElt]
gresFromIE decl_spec (L loc ie, avail)
  = gresFromAvail prov_fn avail
  where
    is_explicit = case ie of
                    IEThingAll _ name -> \n -> n == lieWrappedName name
                    _                 -> \_ -> True
    prov_fn name
      = Just (ImpSpec { is_decl = decl_spec, is_item = item_spec })
      where
        item_spec = ImpSome { is_explicit = is_explicit name
                            , is_iloc = locA loc }


{-
Note [Children for duplicate record fields]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider the module

    {-# LANGUAGE DuplicateRecordFields #-}
    module M (F(foo, MkFInt, MkFBool)) where
      data family F a
      data instance F Int = MkFInt { foo :: Int }
      data instance F Bool = MkFBool { foo :: Bool }

The `foo` in the export list refers to *both* selectors! For this
reason, lookupChildren builds an environment that maps the FastString
to a list of items, rather than a single item.
-}

mkChildEnv :: [GlobalRdrElt] -> NameEnv [GlobalRdrElt]
mkChildEnv gres = foldr add emptyNameEnv gres
  where
    add gre env = case gre_par gre of
        ParentIs  p -> extendNameEnv_Acc (:) Utils.singleton env p gre
        NoParent    -> env

findChildren :: NameEnv [a] -> Name -> [a]
findChildren env n = lookupNameEnv env n `orElse` []

lookupChildren :: [GreName] -> [LIEWrappedName GhcPs]
               -> MaybeErr [LIEWrappedName GhcPs]   -- The ones for which the lookup failed
                           ([LocatedA Name], [Located FieldLabel])
-- (lookupChildren all_kids rdr_items) maps each rdr_item to its
-- corresponding Name all_kids, if the former exists
-- The matching is done by FastString, not OccName, so that
--    Cls( meth, AssocTy )
-- will correctly find AssocTy among the all_kids of Cls, even though
-- the RdrName for AssocTy may have a (bogus) DataName namespace
-- (Really the rdr_items should be FastStrings in the first place.)
lookupChildren all_kids rdr_items
  | null fails
  = Succeeded (fmap concat (partitionEithers oks))
       -- This 'fmap concat' trickily applies concat to the /second/ component
       -- of the pair, whose type is ([LocatedA Name], [[Located FieldLabel]])
  | otherwise
  = Failed fails
  where
    mb_xs = map doOne rdr_items
    fails = [ bad_rdr | Failed bad_rdr <- mb_xs ]
    oks   = [ ok      | Succeeded ok   <- mb_xs ]
    oks :: [Either (LocatedA Name) [Located FieldLabel]]

    doOne item@(L l r)
       = case (lookupFsEnv kid_env . occNameFS . rdrNameOcc . ieWrappedName) r of
           Just [NormalGreName n]                             -> Succeeded (Left (L l n))
           Just rs | Just fs <- traverse greNameFieldLabel rs -> Succeeded (Right (map (L (locA l)) fs))
           _                                                  -> Failed    item

    -- See Note [Children for duplicate record fields]
    kid_env = extendFsEnvList_C (++) emptyFsEnv
              [(occNameFS (occName x), [x]) | x <- all_kids]



-------------------------------

{-
*********************************************************
*                                                       *
\subsection{Unused names}
*                                                       *
*********************************************************
-}

reportUnusedNames :: TcGblEnv -> HscSource -> RnM ()
reportUnusedNames gbl_env hsc_src
  = do  { keep <- readTcRef (tcg_keep gbl_env)
        ; traceRn "RUN" (ppr (tcg_dus gbl_env))
        ; warnUnusedImportDecls gbl_env hsc_src
        ; warnUnusedTopBinds $ unused_locals keep
        ; warnMissingSignatures gbl_env
        ; warnMissingKindSignatures gbl_env }
  where
    used_names :: NameSet -> NameSet
    used_names keep = findUses (tcg_dus gbl_env) emptyNameSet `unionNameSet` keep
    -- NB: currently, if f x = g, we only treat 'g' as used if 'f' is used
    -- Hence findUses

    -- Collect the defined names from the in-scope environment
    defined_names :: [GlobalRdrElt]
    defined_names = globalRdrEnvElts (tcg_rdr_env gbl_env)

    kids_env = mkChildEnv defined_names
    -- This is done in mkExports too; duplicated work

    gre_is_used :: NameSet -> GlobalRdrElt -> Bool
    gre_is_used used_names gre0
        = name `elemNameSet` used_names
          || any (\ gre -> greMangledName gre `elemNameSet` used_names) (findChildren kids_env name)
                -- A use of C implies a use of T,
                -- if C was brought into scope by T(..) or T(C)
      where
        name = greMangledName gre0

    -- Filter out the ones that are
    --  (a) defined in this module, and
    --  (b) not defined by a 'deriving' clause
    -- The latter have an Internal Name, so we can filter them out easily
    unused_locals :: NameSet -> [GlobalRdrElt]
    unused_locals keep =
      let -- Note that defined_and_used, defined_but_not_used
          -- are both [GRE]; that's why we need defined_and_used
          -- rather than just used_names
          _defined_and_used, defined_but_not_used :: [GlobalRdrElt]
          (_defined_and_used, defined_but_not_used)
              = partition (gre_is_used (used_names keep)) defined_names

      in filter is_unused_local defined_but_not_used
    is_unused_local :: GlobalRdrElt -> Bool
    is_unused_local gre = isLocalGRE gre && isExternalName (greMangledName gre)

{- *********************************************************************
*                                                                      *
              Missing signatures
*                                                                      *
********************************************************************* -}

{-
Note [Missing signatures]
~~~~~~~~~~~~~~~~~~~~~~~~~
There are four warning flags in play:

  * -Wmissing-exported-signatures
    Warn about any exported top-level function/value without a type signature.
    Does not include pattern synonyms.

  * -Wmissing-signatures
    Warn about any top-level function/value without a type signature. Does not
    include pattern synonyms. Takes priority over -Wmissing-exported-signatures.

  * -Wmissing-exported-pattern-synonym-signatures
    Warn about any exported pattern synonym without a type signature.

  * -Wmissing-pattern-synonym-signatures
    Warn about any pattern synonym without a type signature. Takes priority over
    -Wmissing-exported-pattern-synonym-signatures.

-}

-- | Warn the user about top level binders that lack type signatures.
-- Called /after/ type inference, so that we can report the
-- inferred type of the function
warnMissingSignatures :: TcGblEnv -> RnM ()
warnMissingSignatures gbl_env
  = do { warn_binds    <- woptM Opt_WarnMissingSignatures
       ; warn_pat_syns <- woptM Opt_WarnMissingPatternSynonymSignatures
       ; let exports = availsToNameSet (tcg_exports gbl_env)
             sig_ns  = tcg_sigs gbl_env
               -- We use sig_ns to exclude top-level bindings that are generated by GHC
             binds    = collectHsBindsBinders CollNoDictBinders $ tcg_binds gbl_env
             pat_syns = tcg_patsyns gbl_env

             not_ghc_generated :: Name -> Bool
             not_ghc_generated name = name `elemNameSet` sig_ns

             add_binding_warn :: Id -> RnM ()
             add_binding_warn id =
               when (not_ghc_generated name) $
               do { env <- tcInitTidyEnv -- Why not use emptyTidyEnv?
                  ; let (_, ty) = tidyOpenType env (idType id)
                        missing = MissingTopLevelBindingSig name ty
                        diag = TcRnMissingSignature missing exported warn_binds
                  ; addDiagnosticAt (getSrcSpan name) diag }
               where
                 name = idName id
                 exported = if name `elemNameSet` exports
                            then IsExported
                            else IsNotExported

             add_patsyn_warn :: PatSyn -> RnM ()
             add_patsyn_warn ps =
               when (not_ghc_generated name) $
                 addDiagnosticAt (getSrcSpan name)
                  (TcRnMissingSignature missing exported warn_pat_syns)
               where
                 name = patSynName ps
                 missing = MissingPatSynSig ps
                 exported = if name `elemNameSet` exports
                            then IsExported
                            else IsNotExported

         -- Warn about missing signatures
         -- Do this only when we have a type to offer
         -- See Note [Missing signatures]
       ; mapM_ add_binding_warn binds
       ; mapM_ add_patsyn_warn  pat_syns
       }

-- | Warn the user about tycons that lack kind signatures.
-- Called /after/ type (and kind) inference, so that we can report the
-- inferred kinds.
warnMissingKindSignatures :: TcGblEnv -> RnM ()
warnMissingKindSignatures gbl_env
  = do { cusks_enabled <- xoptM LangExt.CUSKs
       ; mapM_ (add_ty_warn cusks_enabled) tcs
       }
  where
    tcs = tcg_tcs gbl_env
    ksig_ns = tcg_ksigs gbl_env
    exports = availsToNameSet (tcg_exports gbl_env)
    not_ghc_generated :: Name -> Bool
    not_ghc_generated name = name `elemNameSet` ksig_ns

    add_ty_warn :: Bool -> TyCon -> RnM ()
    add_ty_warn cusks_enabled tyCon =
      when (not_ghc_generated name) $
        addDiagnosticAt (getSrcSpan name) diag
      where
        name = tyConName tyCon
        diag = TcRnMissingSignature missing exported False
        missing = MissingTyConKindSig tyCon cusks_enabled
        exported = if name `elemNameSet` exports
                   then IsExported
                   else IsNotExported

{-
*********************************************************
*                                                       *
\subsection{Unused imports}
*                                                       *
*********************************************************

This code finds which import declarations are unused.  The
specification and implementation notes are here:
  https://gitlab.haskell.org/ghc/ghc/wikis/commentary/compiler/unused-imports

See also Note [Choosing the best import declaration] in GHC.Types.Name.Reader
-}

type ImportDeclUsage
   = ( LImportDecl GhcRn   -- The import declaration
     , [GlobalRdrElt]      -- What *is* used (normalised)
     , [Name] )            -- What is imported but *not* used

warnUnusedImportDecls :: TcGblEnv -> HscSource -> RnM ()
warnUnusedImportDecls gbl_env hsc_src
  = do { uses <- readMutVar (tcg_used_gres gbl_env)
       ; let user_imports = filterOut
                              (ideclImplicit . ideclExt . 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 hsc_src usage }

findImportUsage :: [LImportDecl GhcRn]
                -> [GlobalRdrElt]
                -> [ImportDeclUsage]

findImportUsage imports used_gres
  = map unused_decl imports
  where
    import_usage :: ImportMap
    import_usage = mkImportMap used_gres

    unused_decl :: LImportDecl GhcRn -> (LImportDecl GhcRn, [GlobalRdrElt], [Name])
    unused_decl decl@(L loc (ImportDecl { ideclImportList = imps }))
      = (decl, used_gres, nameSetElemsStable unused_imps)
      where
        used_gres = lookupSrcLoc (srcSpanEnd $ locA loc) import_usage
                               -- srcSpanEnd: see Note [The ImportMap]
                    `orElse` []

        used_names   = mkNameSet (map      greMangledName        used_gres)
        used_parents = mkNameSet (mapMaybe greParent_maybe used_gres)

        unused_imps   -- Not trivial; see eg #7454
          = case imps of
              Just (Exactly, L _ imp_ies) ->
                                 foldr (add_unused . unLoc) emptyNameSet imp_ies
              _other -> emptyNameSet -- No explicit import list => no unused-name list

        add_unused :: IE GhcRn -> NameSet -> NameSet
        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 fs p wc ns) 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 pn
        add_unused _ acc = acc

        add_unused_name n acc
          | n `elemNameSet` used_names = acc
          | otherwise                  = acc `extendNameSet` n
        add_unused_all n acc
          | n `elemNameSet` used_names   = acc
          | n `elemNameSet` used_parents = acc
          | otherwise                    = acc `extendNameSet` n
        add_unused_with p ns acc
          | all (`elemNameSet` acc1) ns = add_unused_name p acc1
          | otherwise = acc1
          where
            acc1 = foldr add_unused_name acc ns
       -- If you use 'signum' from Num, then the user may well have
       -- imported Num(signum).  We don't want to complain that
       -- Num is not itself mentioned.  Hence the two cases in add_unused_with.


{- 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 (#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 RealSrcLoc [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
mkImportMap gres
  = foldr add_one Map.empty gres
  where
    add_one gre@(GRE { gre_imp = imp_specs }) imp_map =
      case srcSpanEnd (is_dloc (is_decl best_imp_spec)) of
                              -- For srcSpanEnd see Note [The ImportMap]
       RealSrcLoc decl_loc _ -> Map.insertWith add decl_loc [gre] imp_map
       UnhelpfulLoc _ -> imp_map
       where
          best_imp_spec = bestImport (bagToList imp_specs)
          add _ gres = gre : gres

warnUnusedImport :: WarningFlag -> NameEnv (FieldLabelString, Parent)
                 -> ImportDeclUsage -> RnM ()
warnUnusedImport flag fld_env (L loc decl, used, unused)

  -- Do not warn for 'import M()'
  | Just (Exactly, L _ []) <- ideclImportList decl
  = return ()

  -- Note [Do not warn about Prelude hiding]
  | Just (EverythingBut, L _ hides) <- ideclImportList decl
  , not (null hides)
  , pRELUDE_NAME == unLoc (ideclName decl)
  = return ()

  -- Nothing used; drop entire declaration
  | null used
  = let dia = mkTcRnUnknownMessage $
          mkPlainDiagnostic (WarningWithFlag flag) noHints msg1
    in addDiagnosticAt (locA loc) dia

  -- Everything imported is used; nop
  | null unused
  = return ()

  -- Only one import is unused, with `SrcSpan` covering only the unused item instead of
  -- the whole import statement
  | Just (_, L _ imports) <- ideclImportList decl
  , length unused == 1
  , Just (L loc _) <- find (\(L _ ie) -> ((ieName ie) :: Name) `elem` unused) imports
  = let dia = mkTcRnUnknownMessage $ mkPlainDiagnostic (WarningWithFlag flag) noHints msg2
    in addDiagnosticAt (locA loc) dia

  -- Some imports are unused
  | otherwise
  = let dia = mkTcRnUnknownMessage $ mkPlainDiagnostic (WarningWithFlag flag) noHints msg2
    in addDiagnosticAt (locA loc) dia

  where
    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 <+> is_redundant]
    pp_herald  = text "The" <+> pp_qual <+> text "import of"
    pp_qual
      | isImportDeclQualified (ideclQualified decl)= text "qualified"
      | otherwise                                  = Outputable.empty
    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.
    -- See trac#14881.
    ppr_possible_field n = case lookupNameEnv fld_env n of
                               Just (fld, ParentIs p) -> pprNameUnqualified p <> parens (ppr fld)
                               Just (fld, NoParent)   -> ppr fld
                               Nothing                -> pprNameUnqualified n

    -- Print unused names in a deterministic (lexicographic) order
    sort_unused :: SDoc
    sort_unused = pprWithCommas ppr_possible_field $
                  sortBy (comparing nameOccName) unused

{-
Note [Do not warn about Prelude hiding]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We do not warn about
   import Prelude hiding( x, y )
because even if nothing else from Prelude is used, it may be essential to hide
x,y to avoid name-shadowing warnings.  Example (#9061)
   import Prelude hiding( log )
   f x = log where log = ()



Note [Printing minimal imports]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
To print the minimal imports we walk over the user-supplied import
decls, and simply trim their import lists.  NB that

  * We do *not* change the 'qualified' or 'as' parts!

  * We do not discard a decl altogether; we might need instances
    from it.  Instead we just trim to an empty import list
-}

getMinimalImports :: [ImportDeclUsage] -> RnM [LImportDecl GhcRn]
getMinimalImports = fmap combine . mapM mk_minimal
  where
    mk_minimal (L l decl, used_gres, unused)
      | null unused
      , Just (Exactly, _) <- ideclImportList decl
      = return (L l decl)
      | otherwise
      = do { let ImportDecl { ideclName    = L _ mod_name
                            , ideclSource  = is_boot
                            , ideclPkgQual = pkg_qual } = decl
           ; iface <- loadSrcInterface doc mod_name is_boot pkg_qual
           ; let used_avails = gresToAvailInfo used_gres
                 lies = map (L l) (concatMap (to_ie iface) used_avails)
           ; return (L l (decl { ideclImportList = Just (Exactly, L (l2l l) lies) })) }
      where
        doc = text "Compute minimal imports for" <+> ppr decl

    to_ie :: ModIface -> AvailInfo -> [IE GhcRn]
    -- The main trick here is that if we're importing all the constructors
    -- we want to say "T(..)", but if we're importing only a subset we want
    -- to say "T(A,B,C)".  So we have to find out what the module exports.
    to_ie _ (Avail c)  -- Note [Overloaded field import]
       = [IEVar noExtField (to_ie_post_rn $ noLocA (greNamePrintableName c))]
    to_ie _ avail@(AvailTC n [_])  -- Exporting the main decl and nothing else
       | availExportsDecl avail = [IEThingAbs noAnn (to_ie_post_rn $ noLocA n)]
    to_ie iface (AvailTC n cs)
      = case [xs | avail@(AvailTC x xs) <- mi_exports iface
                 , x == n
                 , availExportsDecl avail  -- Note [Partial export]
                 ] of
           [xs] | all_used xs ->
                   [IEThingAll noAnn (to_ie_post_rn $ noLocA n)]
                | otherwise   ->
                   [IEThingWith (map noLoc fs) (to_ie_post_rn $ noLocA n) NoIEWildcard
                                (map (to_ie_post_rn . noLocA) (filter (/= n) ns))]
                                          -- Note [Overloaded field import]
           _other | all_non_overloaded fs
                           -> map (IEVar noExtField . to_ie_post_rn_var . noLocA) $ ns
                                 ++ map flSelector fs
                  | otherwise ->
                      [IEThingWith (map noLoc fs) (to_ie_post_rn $ noLocA n) NoIEWildcard
                                (map (to_ie_post_rn . noLocA) (filter (/= n) ns))]
        where
          (ns, fs) = partitionGreNames cs

          all_used avail_cs = all (`elem` cs) avail_cs

          all_non_overloaded = all (not . flIsOverloaded)

    combine :: [LImportDecl GhcRn] -> [LImportDecl GhcRn]
    combine = map merge . NE.groupAllWith getKey

    getKey :: LImportDecl GhcRn -> (Bool, Maybe ModuleName, ModuleName)
    getKey decl =
      ( isImportDeclQualified . ideclQualified $ idecl -- is this qualified? (important that this be first)
      , unLoc <$> ideclAs idecl -- what is the qualifier (inside Maybe monad)
      , unLoc . ideclName $ idecl -- Module Name
      )
      where
        idecl :: ImportDecl GhcRn
        idecl = unLoc decl

    merge :: NonEmpty (LImportDecl GhcRn) -> LImportDecl GhcRn
    merge decls@((L l decl) :| _) = L l (decl { ideclImportList = Just (Exactly, L (noAnnSrcSpan (locA l)) lies) })
      where lies = concatMap (unLoc . snd) $ mapMaybe (ideclImportList . unLoc) $ NE.toList decls


printMinimalImports :: HscSource -> [ImportDeclUsage] -> RnM ()
-- See Note [Printing minimal imports]
printMinimalImports hsc_src imports_w_usage
  = do { imports' <- getMinimalImports imports_w_usage
       ; this_mod <- getModule
       ; dflags   <- getDynFlags
       ; liftIO $ withFile (mkFilename dflags this_mod) WriteMode $ \h ->
          printForUser dflags h neverQualify AllTheWay (vcat (map ppr imports'))
              -- The neverQualify is important.  We are printing Names
              -- but they are in the context of an 'import' decl, and
              -- we never qualify things inside there
              -- E.g.   import Blag( f, b )
              -- not    import Blag( Blag.f, Blag.g )!
       }
  where
    mkFilename dflags this_mod
      | Just d <- dumpDir dflags = d </> basefn
      | otherwise                = basefn
      where
        suffix = case hsc_src of
                     HsBootFile -> ".imports-boot"
                     HsSrcFile  -> ".imports"
                     HsigFile   -> ".imports"
        basefn = moduleNameString (moduleName this_mod) ++ suffix


to_ie_post_rn_var :: LocatedA (IdP GhcRn) -> LIEWrappedName GhcRn
to_ie_post_rn_var (L l n)
  | isDataOcc $ occName n = L l (IEPattern (la2e l)   (L (la2na l) n))
  | otherwise             = L l (IEName    noExtField (L (la2na l) n))


to_ie_post_rn :: LocatedA (IdP GhcRn) -> LIEWrappedName GhcRn
to_ie_post_rn (L l n)
  | isTcOcc occ && isSymOcc occ = L l (IEType (la2e l)   (L (la2na l) n))
  | otherwise                   = L l (IEName noExtField (L (la2na l) n))
  where occ = occName n

{-
Note [Partial export]
~~~~~~~~~~~~~~~~~~~~~
Suppose we have

   module A( op ) where
     class C a where
       op :: a -> a

   module B where
   import A
   f = ..op...

Then the minimal import for module B is
   import A( op )
not
   import A( C( op ) )
which we would usually generate if C was exported from B.  Hence
the availExportsDecl test when deciding what to generate.


Note [Overloaded field import]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
On the other hand, if we have

    {-# LANGUAGE DuplicateRecordFields #-}
    module A where
      data T = MkT { foo :: Int }

    module B where
      import A
      f = ...foo...

then the minimal import for module B must be
    import A ( T(foo) )
because when DuplicateRecordFields is enabled, field selectors are
not in scope without their enclosing datatype.

On the third hand, if we have

    {-# LANGUAGE DuplicateRecordFields #-}
    module A where
      pattern MkT { foo } = Just foo

    module B where
      import A
      f = ...foo...

then the minimal import for module B must be
    import A ( foo )
because foo doesn't have a parent.  This might actually be ambiguous if A
exports another field called foo, but there is no good answer to return and this
is a very obscure corner, so it seems to be the best we can do.  See
DRFPatSynExport for a test of this.


************************************************************************
*                                                                      *
\subsection{Errors}
*                                                                      *
************************************************************************
-}

qualImportItemErr :: RdrName -> SDoc
qualImportItemErr rdr
  = hang (text "Illegal qualified name in import item:")
       2 (ppr rdr)

ambiguousImportItemErr :: RdrName -> [AvailInfo] -> SDoc
ambiguousImportItemErr rdr avails
  = hang (text "Ambiguous name" <+> quotes (ppr rdr) <+> text "in import item. It could refer to:")
       2 (vcat (map ppr_avail avails))
  where
    ppr_avail (AvailTC parent _) = ppr parent <> parens (ppr rdr)
    ppr_avail (Avail name)       = ppr name

pprImpDeclSpec :: ModIface -> ImpDeclSpec -> SDoc
pprImpDeclSpec iface decl_spec =
  quotes (ppr (is_mod decl_spec)) <+> case mi_boot iface of
    IsBoot -> text "(hi-boot interface)"
    NotBoot -> Outputable.empty

badImportItemErrStd :: ModIface -> ImpDeclSpec -> IE GhcPs -> SDoc
badImportItemErrStd iface decl_spec ie
  = sep [text "Module", pprImpDeclSpec iface decl_spec,
         text "does not export", quotes (ppr ie)]

badImportItemErrDataCon :: OccName -> ModIface -> ImpDeclSpec -> IE GhcPs
                        -> SDoc
badImportItemErrDataCon dataType_occ iface decl_spec ie
  = vcat [ text "In module"
             <+> pprImpDeclSpec iface decl_spec
             <> colon
         , nest 2 $ quotes datacon
             <+> text "is a data constructor of"
             <+> quotes dataType
         , text "To import it use"
         , nest 2 $ text "import"
             <+> ppr (is_mod decl_spec)
             <> parens_sp (dataType <> parens_sp datacon)
         , text "or"
         , nest 2 $ text "import"
             <+> ppr (is_mod decl_spec)
             <> parens_sp (dataType <> text "(..)")
         ]
  where
    datacon_occ = rdrNameOcc $ ieName ie
    datacon = parenSymOcc datacon_occ (ppr datacon_occ)
    dataType = parenSymOcc dataType_occ (ppr dataType_occ)
    parens_sp d = parens (space <> d <> space)  -- T( f,g )

badImportItemErr :: ModIface -> ImpDeclSpec -> IE GhcPs -> [AvailInfo] -> SDoc
badImportItemErr iface decl_spec ie avails
  = case find checkIfDataCon avails of
      Just con -> badImportItemErrDataCon (availOccName con) iface decl_spec ie
      Nothing  -> badImportItemErrStd iface decl_spec ie
  where
    checkIfDataCon (AvailTC _ ns) =
      case find (\n -> importedFS == occNameFS (occName n)) ns of
        Just n  -> isDataConName (greNameMangledName n)
        Nothing -> False
    checkIfDataCon _ = False
    availOccName = occName . availGreName
    importedFS = occNameFS . rdrNameOcc $ ieName ie

illegalImportItemErr :: SDoc
illegalImportItemErr = text "Illegal import item"

addDupDeclErr :: NonEmpty GlobalRdrElt -> TcRn ()
addDupDeclErr gres@(gre :| _)
  = addErrAt (getSrcSpan (NE.last sorted_names)) $ mkTcRnUnknownMessage $ mkPlainError noHints $
    -- Report the error at the later location
    vcat [text "Multiple declarations of" <+>
             quotes (ppr (greOccName gre)),
             -- NB. print the OccName, not the Name, because the
             -- latter might not be in scope in the RdrEnv and so will
             -- be printed qualified.
          text "Declared at:" <+>
                   vcat (toList $ ppr . nameSrcLoc <$> sorted_names)]
  where
    sorted_names =
      NE.sortBy (SrcLoc.leftmost_smallest `on` nameSrcSpan)
             (fmap greMangledName gres)



missingImportListWarn :: ModuleName -> SDoc
missingImportListWarn mod
  = text "The module" <+> quotes (ppr mod) <+> text "does not have an explicit import list"

moduleWarn :: ModuleName -> WarningTxt GhcRn -> SDoc
moduleWarn mod (WarningTxt _ txt)
  = sep [ text "Module" <+> quotes (ppr mod) <> colon,
          nest 2 (vcat (map (ppr . hsDocString . unLoc) txt)) ]
moduleWarn mod (DeprecatedTxt _ txt)
  = sep [ text "Module" <+> quotes (ppr mod)
                                <+> text "is deprecated:",
          nest 2 (vcat (map (ppr . hsDocString . unLoc) txt)) ]

packageImportErr :: TcRnMessage
packageImportErr
  = mkTcRnUnknownMessage $ mkPlainError noHints $
  text "Package-qualified imports are not enabled; use PackageImports"

-- This data decl will parse OK
--      data T = a Int
-- treating "a" as the constructor.
-- It is really hard to make the parser spot this malformation.
-- So the renamer has to check that the constructor is legal
--
-- We can get an operator as the constructor, even in the prefix form:
--      data T = :% Int Int
-- from interface files, which always print in prefix form
--
-- We also allow type constructor names, which are defined by "type data"
-- declarations.  See Note [Type data declarations] in GHC.Rename.Module.

checkConName :: RdrName -> TcRn ()
checkConName name
  = checkErr (isRdrDataCon name || isRdrTc name) (badDataCon name)

badDataCon :: RdrName -> TcRnMessage
badDataCon name
   = mkTcRnUnknownMessage $ mkPlainError noHints $
   hsep [text "Illegal data constructor name", quotes (ppr name)]