fuzzyLookup: More deterministic orderwip/joachim/fuzzyLookup

else the output may depend on the input order, which seems it may depend
on the concrete Uniques, which is causing headaches when including test
cases about that.

10 files changed, 25 insertions, 19 deletions

diff --git a/compiler/GHC/Utils/Misc.hs b/compiler/GHC/Utils/Misc.hs
index 181d6c91e7..05e8365745 100644
--- a/compiler/GHC/Utils/Misc.hs
+++ b/compiler/GHC/Utils/Misc.hs
@@ -950,10 +950,12 @@ fuzzyMatch key vals = fuzzyLookup key [(v,v) | v <- vals]
 fuzzyLookup :: String -> [(String,a)] -> [a]
 fuzzyLookup user_entered possibilites
   = map fst $ take mAX_RESULTS $ List.sortBy (comparing snd)
-    [ (poss_val, distance) | (poss_str, poss_val) <- possibilites
-                       , let distance = restrictedDamerauLevenshteinDistance
-                                            poss_str user_entered
-                       , distance <= fuzzy_threshold ]
+    [ (poss_val, sort_key)
+    | (poss_str, poss_val) <- possibilites
+    , let distance = restrictedDamerauLevenshteinDistance poss_str user_entered
+    , distance <= fuzzy_threshold
+    , let sort_key = (distance, length poss_str, poss_str)
+    ]
   where
     -- Work out an appropriate match threshold:
     -- We report a candidate if its edit distance is <= the threshold,
@@ -966,6 +968,10 @@ fuzzyLookup user_entered possibilites
     --     5         1
     --     6         2
     --
+    -- Candidates with the same distance are sorted by their length. We also
+    -- use the actual string as the third sorting criteria the sort key to get
+    -- deterministic output, even if the input may have depended on the uniques
+    -- in question
     fuzzy_threshold = truncate $ fromIntegral (length user_entered + 2) / (4 :: Rational)
     mAX_RESULTS = 3
 
diff --git a/testsuite/tests/ghci/scripts/T5564.stderr b/testsuite/tests/ghci/scripts/T5564.stderr
index 31ebd14b0e..89de0f18e3 100644
--- a/testsuite/tests/ghci/scripts/T5564.stderr
+++ b/testsuite/tests/ghci/scripts/T5564.stderr
@@ -6,5 +6,5 @@
 <interactive>:4:1: error:
     • Variable not in scope: fit
     • Perhaps you meant one of these:
-        ‘fst’ (imported from Prelude), ‘Ghci1.it’ (imported from Ghci1),
-        ‘it’ (line 3)
+        ‘Ghci1.it’ (imported from Ghci1), ‘it’ (line 3),
+        ‘fst’ (imported from Prelude)
diff --git a/testsuite/tests/ghci/scripts/T5979.stderr b/testsuite/tests/ghci/scripts/T5979.stderr
index ec3c66c8b6..2c23b542d9 100644
--- a/testsuite/tests/ghci/scripts/T5979.stderr
+++ b/testsuite/tests/ghci/scripts/T5979.stderr
@@ -2,6 +2,6 @@
 <no location info>: error:
     Could not find module ‘Control.Monad.Trans.State’
     Perhaps you meant
-      Control.Monad.Trans.State (from transformers-0.5.2.0)
-      Control.Monad.Trans.Class (from transformers-0.5.2.0)
-      Control.Monad.Trans.Cont (from transformers-0.5.2.0)
+      Control.Monad.Trans.State (from transformers-0.5.6.2)
+      Control.Monad.Trans.Cont (from transformers-0.5.6.2)
+      Control.Monad.Trans.List (from transformers-0.5.6.2)
diff --git a/testsuite/tests/module/mod134.stderr b/testsuite/tests/module/mod134.stderr
index 86c2ffb6a5..75c556cd4f 100644
--- a/testsuite/tests/module/mod134.stderr
+++ b/testsuite/tests/module/mod134.stderr
@@ -4,6 +4,6 @@ mod134.hs:6:19: error:
     Perhaps you meant one of these:
       ‘Prelude.read’ (imported from Prelude),
       ‘Prelude.reads’ (imported from Prelude),
-      data constructor ‘Prelude.Left’ (imported from Prelude)
+      ‘Prelude.id’ (imported from Prelude)
     Perhaps you want to remove ‘head’ from the explicit hiding list
     in the import of ‘Prelude’ (mod134.hs:4:1-28).
diff --git a/testsuite/tests/package/package07e.stderr b/testsuite/tests/package/package07e.stderr
index e5efa7e910..7762072014 100644
--- a/testsuite/tests/package/package07e.stderr
+++ b/testsuite/tests/package/package07e.stderr
@@ -3,8 +3,8 @@ package07e.hs:2:1: error:
     Could not find module ‘GHC.Hs.MyTypes’
     Perhaps you meant
       GHC.Hs.Type (needs flag -package-id ghc-9.3)
-      GHC.Hs.Syn.Type (needs flag -package-id ghc-9.3)
       GHC.Tc.Types (needs flag -package-id ghc-9.3)
+      GHC.Hs.Syn.Type (needs flag -package-id ghc-9.3)
     Use -v (or `:set -v` in ghci) to see a list of the files searched for.
 
 package07e.hs:3:1: error:
diff --git a/testsuite/tests/package/package08e.stderr b/testsuite/tests/package/package08e.stderr
index 0f84655e60..5d0867c908 100644
--- a/testsuite/tests/package/package08e.stderr
+++ b/testsuite/tests/package/package08e.stderr
@@ -3,8 +3,8 @@ package08e.hs:2:1: error:
     Could not find module ‘GHC.Hs.MyTypes’
     Perhaps you meant
       GHC.Hs.Type (needs flag -package-id ghc-9.3)
-      GHC.Hs.Syn.Type (needs flag -package-id ghc-9.3)
       GHC.Tc.Types (needs flag -package-id ghc-9.3)
+      GHC.Hs.Syn.Type (needs flag -package-id ghc-9.3)
     Use -v (or `:set -v` in ghci) to see a list of the files searched for.
 
 package08e.hs:3:1: error:
diff --git a/testsuite/tests/rename/should_fail/T10618.stderr b/testsuite/tests/rename/should_fail/T10618.stderr
index 2d478744e1..cba5e47aff 100644
--- a/testsuite/tests/rename/should_fail/T10618.stderr
+++ b/testsuite/tests/rename/should_fail/T10618.stderr
@@ -2,5 +2,5 @@
 T10618.hs:3:22: error:
     • Variable not in scope: (<|>) :: Maybe (Maybe a0) -> Maybe a1 -> t
     • Perhaps you meant one of these:
-        ‘<$>’ (imported from Prelude), ‘<*>’ (imported from Prelude),
-        ‘<>’ (imported from Prelude)
+        ‘<>’ (imported from Prelude), ‘<$>’ (imported from Prelude),
+        ‘<*>’ (imported from Prelude)
diff --git a/testsuite/tests/rename/should_fail/T15539.stderr b/testsuite/tests/rename/should_fail/T15539.stderr
index c3de7780d4..9ac202f420 100644
--- a/testsuite/tests/rename/should_fail/T15539.stderr
+++ b/testsuite/tests/rename/should_fail/T15539.stderr
@@ -1,4 +1,4 @@
 
 T15539.hs:6:13: error:
     • Variable not in scope: baz
-    • Perhaps you meant one of these: ‘bar’ (line 15), ‘bam’ (line 17)
+    • Perhaps you meant one of these: ‘bam’ (line 17), ‘bar’ (line 15)
diff --git a/testsuite/tests/rename/should_fail/rnfail032.stderr b/testsuite/tests/rename/should_fail/rnfail032.stderr
index 70d80a0322..874b1746e6 100644
--- a/testsuite/tests/rename/should_fail/rnfail032.stderr
+++ b/testsuite/tests/rename/should_fail/rnfail032.stderr
@@ -3,7 +3,7 @@ rnfail032.hs:2:21: error:
     Not in scope: ‘Data.List.map’
     Perhaps you meant one of these:
       ‘Data.List.zip’ (imported from Data.List),
-      ‘Data.List.all’ (imported from Data.List),
-      ‘Data.List.and’ (imported from Data.List)
+      ‘Data.List.or’ (imported from Data.List),
+      ‘Data.List.all’ (imported from Data.List)
     Perhaps you want to remove ‘map’ from the explicit hiding list
     in the import of ‘Data.List’ (rnfail032.hs:3:1-41).
diff --git a/testsuite/tests/rename/should_fail/rnfail033.stderr b/testsuite/tests/rename/should_fail/rnfail033.stderr
index 277b42fb16..a445fd7293 100644
--- a/testsuite/tests/rename/should_fail/rnfail033.stderr
+++ b/testsuite/tests/rename/should_fail/rnfail033.stderr
@@ -3,7 +3,7 @@ rnfail033.hs:2:21: error:
     Not in scope: ‘Data.List.map’
     Perhaps you meant one of these:
       ‘Data.List.zip’ (imported from Data.List),
-      ‘Data.List.all’ (imported from Data.List),
-      ‘Data.List.and’ (imported from Data.List)
+      ‘Data.List.or’ (imported from Data.List),
+      ‘Data.List.all’ (imported from Data.List)
     Perhaps you want to remove ‘map’ from the explicit hiding list
     in the import of ‘Data.List’ (rnfail033.hs:3:1-31).