lib/modules: Support multiple suggestions, optimize

4 files changed, 108 insertions, 4 deletions

diff --git a/lib/modules.nix b/lib/modules.nix
index fd5cf76eda03..eb4afd03d03b 100644
--- a/lib/modules.nix
+++ b/lib/modules.nix
@@ -12,6 +12,7 @@ let
     concatMap
     concatStringsSep
     elem
+    elemAt
     filter
     foldl'
     functionArgs
@@ -36,13 +37,16 @@ let
     optional
     optionalAttrs
     optionalString
+    pipe
     recursiveUpdate
     remove
     reverseList
     sort
+    sortOn
     seq
     setAttrByPath
     substring
+    take
     throwIfNot
     trace
     typeOf
@@ -64,6 +68,7 @@ let
   inherit (lib.strings)
     isConvertibleWithToString
     levenshtein
+    levenshteinAtMost
     ;
 
   showDeclPrefix =
@@ -311,11 +316,30 @@ let
                 prefix' = init (prefix ++ firstDef.prefix);
                 adj = attrNames (attrByPath prefix' { } options);
                 adj' = if prefix' == [ ] then remove "_module" adj else adj;
-                lev = levenshtein (last firstDef.prefix);
-                closest = if adj' == [ ] then null else head (sort (p: q: lev p < lev q) adj');
+                invalidOptName = last firstDef.prefix;
+                # For small option sets, check all; for large sets, only check distance ≤ 2
+                suggestions =
+                  if length adj' < 100 then
+                    pipe adj' [
+                      (sortOn (levenshtein invalidOptName))
+                      (take 3)
+                    ]
+                  else
+                    pipe adj' [
+                      # levenshteinAtMost is only fast for distance ≤ 2
+                      (filter (levenshteinAtMost 2 invalidOptName))
+                      (sortOn (levenshtein invalidOptName))
+                      (take 3)
+                    ];
                 suggestion =
-                  optionalString (closest != null)
-                    "\n\nDid you mean `${showOption (prefix' ++ [ closest ])}'?";
+                  if suggestions == [ ] then
+                    ""
+                  else if length suggestions == 1 then
+                    "\n\nDid you mean `${showOption (prefix' ++ [ (head suggestions) ])}'?"
+                  else
+                    "\n\nDid you mean ${
+                      concatStringsSep ", " (map (s: "`${showOption (prefix' ++ [ s ])}'") (init suggestions))
+                    } or `${showOption (prefix' ++ [ (last suggestions) ])}'?";
               in
               "The option `${optText}' does not exist. Definition values:${defText}${suggestion}";
           in
diff --git a/lib/tests/modules.sh b/lib/tests/modules.sh
index 69fb2aa9c7ae..af40d521635e 100755
--- a/lib/tests/modules.sh
+++ b/lib/tests/modules.sh
@@ -744,6 +744,8 @@ checkConfigOutput '"foo"' config.sub.conditionalImportAsDarwin.bar ./specialArgs
 # Option name suggestions
 checkConfigError 'Did you mean .set\.enable.\?' config.set ./error-typo-nested.nix
 checkConfigError 'Did you mean .set.\?' config ./error-typo-outside-with-nested.nix
+checkConfigError 'Did you mean .bar., .baz. or .foo.\?' config ./error-typo-multiple-suggestions.nix
+checkConfigError 'Did you mean .enable., .ebe. or .enabled.\?' config ./error-typo-large-attrset.nix
 
 cat <<EOF
 ====== module tests ======
diff --git a/lib/tests/modules/error-typo-large-attrset.nix b/lib/tests/modules/error-typo-large-attrset.nix
new file mode 100644
index 000000000000..0991f9a2c9e2
--- /dev/null
+++ b/lib/tests/modules/error-typo-large-attrset.nix
@@ -0,0 +1,56 @@
+{ lib, ... }:
+
+let
+  inherit (lib) mkOption concatMapAttrs;
+
+  ten = {
+    a = null;
+    b = null;
+    c = null;
+    d = null;
+    e = null;
+    f = null;
+    g = null;
+    h = null;
+    i = null;
+    j = null;
+  };
+
+  # Generate 1000 options (10 * 10 * 10)
+  generatedOptions = concatMapAttrs (
+    k1: _:
+    concatMapAttrs (
+      k2: _:
+      concatMapAttrs (k3: _: {
+        "${k1}${k2}${k3}" = mkOption {
+          type = lib.types.bool;
+          default = false;
+        };
+      }) ten
+    ) ten
+  ) ten;
+
+  # Add some sensible options that are close to our typo
+  sensibleOptions = {
+    enable = mkOption {
+      type = lib.types.bool;
+      default = false;
+    };
+    enabled = mkOption {
+      type = lib.types.bool;
+      default = false;
+    };
+    disable = mkOption {
+      type = lib.types.bool;
+      default = false;
+    };
+  };
+in
+{
+  options = generatedOptions // sensibleOptions;
+
+  config = {
+    # Typo: "enble" is distance 1 from "enable"
+    enble = true;
+  };
+}
diff --git a/lib/tests/modules/error-typo-multiple-suggestions.nix b/lib/tests/modules/error-typo-multiple-suggestions.nix
new file mode 100644
index 000000000000..d01d649c3a05
--- /dev/null
+++ b/lib/tests/modules/error-typo-multiple-suggestions.nix
@@ -0,0 +1,22 @@
+{ lib, ... }:
+
+{
+  options.foo = lib.mkOption {
+    default = false;
+    type = lib.types.bool;
+  };
+
+  options.bar = lib.mkOption {
+    default = false;
+    type = lib.types.bool;
+  };
+
+  options.baz = lib.mkOption {
+    default = false;
+    type = lib.types.bool;
+  };
+
+  config = {
+    far = true;
+  };
+}