[clangd] Provide suggestions with invalid config keys

[njames93]

Summary

Update the config file warning when an unknown key is detected which is likely a typo by suggesting the likely key.
This won't suggest a key that has already been seen in the block.

Appends the fix to the diag, however right now there is no support for presenting that fix to the user.

[njames93]

Fix lit test failure

[njames93]

Adding in support for fix-its(at least in vscode) didn't seem to work. The language server there doesn't seem to send the textDocument/codeAction message to the server for the .clangd file.

[sammccall]

This is cool! Detecting basic typos could save a fair bit of time.
I do want to be a bit wary of spending too much complexity on small enhancements to rarely used code - if it's more than a simple typo we're correcting, then I think it's ok to make the user look it up.

In D92990#2445283, @njames93 wrote:

Adding in support for fix-its(at least in vscode) didn't seem to work. The language server there doesn't seem to send the textDocument/codeAction message to the server for the .clangd file.

Right, we can publish to any file, but we only expect to get requests for files we're active on, and users will expect us to track draft changes etc. I don't think we want to go down the path of being a full language server for config files, so I wouldn't pursue fixit support.

clang-tools-extra/clangd/ConfigYAML.cpp

202

i'm not sure it's actually worth the complexity to delay this, track the seen keys, and exclude them from the analysis.
Offering a suggestion already seems pretty good, but I don't think we should try too hard to make it perfect.

211

nit: drop explicit '4' size here
also drop get prefix here and for best-guess (matching the local style for functions used for value rather than for side-effect)

221

nit: drop unused default param

223

Comment here just echoes the code - remove?

231

This branch is confusing.
It seems to be saying if we have a tie for best, don't return either result. Why is that important/worth any complexity?

[njames93]

Address some comments

[njames93]

In D92990#2446097, @sammccall wrote:

This is cool! Detecting basic typos could save a fair bit of time.
I do want to be a bit wary of spending too much complexity on small enhancements to rarely used code - if it's more than a simple typo we're correcting, then I think it's ok to make the user look it up.

I always like to think users don't spend much time reading the instructions, so little pointers like this do add value and result in a more polished experience.

In D92990#2445283, @njames93 wrote:

Adding in support for fix-its(at least in vscode) didn't seem to work. The language server there doesn't seem to send the textDocument/codeAction message to the server for the .clangd file.

Right, we can publish to any file, but we only expect to get requests for files we're active on, and users will expect us to track draft changes etc. I don't think we want to go down the path of being a full language server for config files, so I wouldn't pursue fixit support.

Ahh I don't know the full ins and outs of LSP. As nice as a fix-it would be, It appears that's a little too much work so should best be avoided.

clang-tools-extra/clangd/ConfigYAML.cpp

202

Perfection isn't needed, but suggesting a fix that will result in another error is arguably counter-productive.

211

Forgot about the new default SmallVector storage feature.

231

If we have 2 (or more) possible solutions, we can't say for certainty what the user wanted, in which case its best to not suggest anything, in case its incorrect and instead force the user to take an informed look. It doesn't really add much complexity to do this check, And most of this code is copied from somewhere else in llvm as its a pretty common routine. Maybe they could be coalesced into 1 class to reduce duplication,

[sammccall]

Sorry about being slow here.
Just a couple of suggestions to avoid cluttering the config parsing bits too much, and IIUC fixits can be removed.

clang-tools-extra/clangd/ConfigYAML.cpp

211

I think inlining unseenKeys into warnUnknownKeys would be more readable by isolating the mechanics of typo correction into fewer places.

219

I think we can pull this function out of this class, since it doesn't have much to do with config parsing. (Probably just anonymous above - it's not so reusable since candidates aren't always just strings)

231

Well, there isn't *any* case where we can say for certain that we know what the user wanted.

If this were a common library then that shifts the complexity/accuracy tradeoff and justifies a bit of extra work. As it is, the fact that it's copy/pasted doesn't help much with maintaining/reading it. We can keep this, though I don't feel great about it.

(FWIW, these same copy/pasted numbers thresholds are used for clang's typo correction, and we're pretty sure they're not very good - @hokein has tuning them on his backlog)

295

please remove the SMFixIt bits, since we don't have any way to use them

[njames93]

Address comments.

[sammccall]

LG, thanks!

clang-tools-extra/clangd/ConfigYAML.cpp

27

(nit: no need for static in anon namespace)

301

optional nit: these node variants are now just convenience wrappers, I'd drop the comment from them and group them accordingly with whitespace, up to you.

[njames93]

Last nits.

clang-tools-extra/clangd/ConfigYAML.cpp

 namespace config {
 namespace {
 using llvm::yaml::BlockScalarNode;
 using llvm::yaml::MappingNode;
 using llvm::yaml::Node;
 using llvm::yaml::ScalarNode;
 using llvm::yaml::SequenceNode;
 
 class Parser {
   llvm::SourceMgr &SM;
   bool HadError = false;
 
 public:
   Parser(llvm::SourceMgr &SM) : SM(SM) {}
 
   // Tries to parse N into F, returning false if it failed and we couldn't
   // meaningfully recover (YAML syntax error, or hard semantic error).
public:
 
     // Process a mapping node and call handlers for each key/value pair.
     void parse(Node &N) const {
       if (N.getType() != Node::NK_Mapping) {
         Outer->error(Description + " should be a dictionary", N);
         return;
       }
       llvm::SmallSet<std::string, 8> Seen;
+      llvm::SmallVector<Located<std::string>, 0> UnknownKeys;
       // We *must* consume all items, even on error, or the parser will assert.
       for (auto &KV : llvm::cast<MappingNode>(N)) {
         auto *K = KV.getKey();
         if (!K) // YAMLParser emitted an error.
           continue;
         auto Key = Outer->scalarValue(*K, "Dictionary key");
         if (!Key)
           continue;
void parse(Node &N) const {
           }
         }
         if (!Matched) {
           bool Warn = !UnknownHandler;
           if (UnknownHandler)
             Warn = UnknownHandler(
                 Located<std::string>(**Key, K->getSourceRange()), *Value);
           if (Warn)
-            Outer->warning("Unknown " + Description + " key " + **Key, *K);
+            UnknownKeys.push_back(std::move(*Key));
         }
       }
+      if (!UnknownKeys.empty())
+        warnUnknownKeys(UnknownKeys, getUnseenKeys(Seen));
+    }
+
+  private:
+    llvm::SmallVector<llvm::StringRef, 4>
+    getUnseenKeys(const llvm::SmallSet<std::string, 8> &SeenKeys) const {
+      llvm::SmallVector<llvm::StringRef, 4> Result;
+      for (const auto &KeyAndHandler : Keys)
+        if (!SeenKeys.count(KeyAndHandler.first.str()))
+          Result.push_back(KeyAndHandler.first);
+      return Result;
+    }
+
+    static llvm::Optional<llvm::StringRef>
+    getBestGuess(llvm::StringRef Search, llvm::ArrayRef<llvm::StringRef> Items,
+                 unsigned MaxEdit = 0) {
+      if (!MaxEdit)
+        MaxEdit = (Search.size() + 1) / 3;
+      // If Search is sufficiently short (size() < 2), just return nothing.
+      if (!MaxEdit)
+        return llvm::None;
+      llvm::Optional<llvm::StringRef> Result;
+      for (const auto &Item : Items) {
+        unsigned EditDistance = Search.edit_distance(Item, true, MaxEdit);
+        if (EditDistance == MaxEdit) {
+          if (!Result)
+            Result = Item;
+          else
+            Result = llvm::StringRef();
+        } else if (EditDistance < MaxEdit) {
+          Result = Item;
+          MaxEdit = EditDistance;
+        }
+      }
+      if (Result && !Result->empty())
+        return Result;
+      return llvm::None;
+    }
+
+    void warnUnknownKeys(llvm::ArrayRef<Located<std::string>> UnknownKeys,
+                         llvm::ArrayRef<llvm::StringRef> UnseenKeys) const {
+      for (const Located<std::string> &UnknownKey : UnknownKeys)
+        if (auto BestGuess = getBestGuess(*UnknownKey, UnseenKeys))
+          Outer->warning("Unknown " + Description + " key '" + *UnknownKey +
+                             "'; did you mean '" + *BestGuess + "'?",
+                         UnknownKey.Range,
+                         llvm::SMFixIt(UnknownKey.Range, *BestGuess));
+        else
+          Outer->warning("Unknown " + Description + " key '" + *UnknownKey +
+                             "'",
+                         UnknownKey.Range);
     }
   };
 
   // Try to parse a single scalar value from the node, warn on failure.
   llvm::Optional<Located<std::string>> scalarValue(Node &N,
                                                    llvm::StringRef Desc) {
     llvm::SmallString<256> Buf;
     if (auto *S = llvm::dyn_cast<ScalarNode>(&N))
llvm::Optional<std::vector<Located<std::string>>> scalarValues(Node &N) {
     } else {
       warning("Expected scalar or list of scalars", N);
       return llvm::None;
     }
     return Result;
   }
 
   // Report a "hard" error, reflecting a config file that can never be valid.
-  void error(const llvm::Twine &Msg, const Node &N) {
+  void error(const llvm::Twine &Msg, llvm::SMRange Range,
+             llvm::ArrayRef<llvm::SMFixIt> Fixes = {}) {
     HadError = true;
-    SM.PrintMessage(N.getSourceRange().Start, llvm::SourceMgr::DK_Error, Msg,
-                    N.getSourceRange());
+    SM.PrintMessage(Range.Start, llvm::SourceMgr::DK_Error, Msg, Range, Fixes);
+  }
+
+  // Report a "hard" error, reflecting a config file that can never be valid.
+  void error(const llvm::Twine &Msg, const Node &N) {
+    return error(Msg, N.getSourceRange());
+  }
+  // Report a "soft" error that could be caused by e.g. version skew.
+  void warning(const llvm::Twine &Msg, llvm::SMRange Range,
+               llvm::ArrayRef<llvm::SMFixIt> Fixes = {}) {
+    SM.PrintMessage(Range.Start, llvm::SourceMgr::DK_Warning, Msg, Range,
+                    Fixes);
   }
 
   // Report a "soft" error that could be caused by e.g. version skew.
   void warning(const llvm::Twine &Msg, const Node &N) {
-    SM.PrintMessage(N.getSourceRange().Start, llvm::SourceMgr::DK_Warning, Msg,
-                    N.getSourceRange());
+    return warning(Msg, N.getSourceRange());
   }
 };
 
 } // namespace
 
 std::vector<Fragment> Fragment::parseYAML(llvm::StringRef YAML,
                                           llvm::StringRef BufferName,
                                           DiagnosticCallback Diags) {

clang-tools-extra/clangd/unittests/ConfigProviderTests.cpp

 }
 
 const char *AddFooWithErr = R"yaml(
 CompileFlags:
   Add: foo
   Unknown: 42
 )yaml";
 
+const char *AddFooWithTypoErr = R"yaml(
+CompileFlags:
+  Add: foo
+  Removr: 42
+)yaml";
+
 const char *AddBarBaz = R"yaml(
 CompileFlags:
   Add: bar
 ---
 CompileFlags:
   Add: baz
 )yaml";
 
 TEST(ProviderTest, FromYAMLFile) {
   MockFS FS;
   FS.Files["foo.yaml"] = AddFooWithErr;
 
   CapturedDiags Diags;
   auto P = Provider::fromYAMLFile(testPath("foo.yaml"), /*Directory=*/"", FS);
   auto Cfg = P->getConfig(Params(), Diags.callback());
   EXPECT_THAT(Diags.Diagnostics,
-              ElementsAre(DiagMessage("Unknown CompileFlags key Unknown")));
+              ElementsAre(DiagMessage("Unknown CompileFlags key 'Unknown'")));
   EXPECT_THAT(Diags.Files, ElementsAre(testPath("foo.yaml")));
   EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("foo"));
   Diags.clear();
 
   Cfg = P->getConfig(Params(), Diags.callback());
   EXPECT_THAT(Diags.Diagnostics, IsEmpty()) << "Cached, not re-parsed";
   EXPECT_THAT(Diags.Files, IsEmpty());
   EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("foo"));
 
+  FS.Files["foo.yaml"] = AddFooWithTypoErr;
+  Cfg = P->getConfig(Params(), Diags.callback());
+  EXPECT_THAT(
+      Diags.Diagnostics,
+      ElementsAre(DiagMessage(
+          "Unknown CompileFlags key 'Removr'; did you mean 'Remove'?")));
+  EXPECT_THAT(Diags.Files, ElementsAre(testPath("foo.yaml")));
+  EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("foo"));
+  Diags.clear();
+
   FS.Files["foo.yaml"] = AddBarBaz;
   Cfg = P->getConfig(Params(), Diags.callback());
   EXPECT_THAT(Diags.Diagnostics, IsEmpty()) << "New config, no errors";
   EXPECT_THAT(Diags.Files, ElementsAre(testPath("foo.yaml")));
   EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("bar", "baz"));
   Diags.clear();
 
   FS.Files.erase("foo.yaml");
TEST(ProviderTest, FromAncestorRelativeYAMLFiles) {
 
   auto Cfg = P->getConfig(Params(), Diags.callback());
   EXPECT_THAT(Diags.Diagnostics, IsEmpty());
   EXPECT_THAT(Diags.Files, IsEmpty());
   EXPECT_THAT(getAddedArgs(Cfg), IsEmpty());
 
   Cfg = P->getConfig(ABCParams, Diags.callback());
   EXPECT_THAT(Diags.Diagnostics,
-              ElementsAre(DiagMessage("Unknown CompileFlags key Unknown")));
+              ElementsAre(DiagMessage("Unknown CompileFlags key 'Unknown'")));
   // FIXME: fails on windows: paths have mixed slashes like C:\a/b\c.yaml
   EXPECT_THAT(Diags.Files,
               ElementsAre(testPath("a/foo.yaml"), testPath("a/b/c/foo.yaml")));
   EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("foo", "bar", "baz"));
   Diags.clear();
 
   Cfg = P->getConfig(AParams, Diags.callback());
   EXPECT_THAT(Diags.Diagnostics, IsEmpty()) << "Cached config";
TEST(ProviderTest, Staleness) {
   MustBeFresh.FreshTime = StartTime + std::chrono::hours(1);
   CapturedDiags Diags;
   auto P = Provider::fromYAMLFile(testPath("foo.yaml"), /*Directory=*/"", FS);
 
   // Initial query always reads, regardless of policy.
   FS.Files["foo.yaml"] = AddFooWithErr;
   auto Cfg = P->getConfig(StaleOK, Diags.callback());
   EXPECT_THAT(Diags.Diagnostics,
-              ElementsAre(DiagMessage("Unknown CompileFlags key Unknown")));
+              ElementsAre(DiagMessage("Unknown CompileFlags key 'Unknown'")));
   EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("foo"));
   Diags.clear();
 
   // Stale value reused by policy.
   FS.Files["foo.yaml"] = AddBarBaz;
   Cfg = P->getConfig(StaleOK, Diags.callback());
   EXPECT_THAT(Diags.Diagnostics, IsEmpty()) << "Cached, not re-parsed";
   EXPECT_THAT(getAddedArgs(Cfg), ElementsAre("foo"));

clang-tools-extra/clangd/unittests/ConfigYAMLTests.cpp

 ---
 CompileFlags: {$unexpected^
 )yaml");
   auto Results =
       Fragment::parseYAML(YAML.code(), "config.yaml", Diags.callback());
 
   ASSERT_THAT(
       Diags.Diagnostics,
-      ElementsAre(AllOf(DiagMessage("Unknown If key UnknownCondition"),
+      ElementsAre(AllOf(DiagMessage("Unknown If key 'UnknownCondition'"),
                         DiagKind(llvm::SourceMgr::DK_Warning),
                         DiagPos(YAML.range("unknown").start),
                         DiagRange(YAML.range("unknown"))),
                   AllOf(DiagMessage("Unexpected token. Expected Key, Flow "
                                     "Entry, or Flow Mapping End."),
                         DiagKind(llvm::SourceMgr::DK_Error),
                         DiagPos(YAML.point("unexpected")),
                         DiagRange(llvm::None))));