[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

225

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.

234

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)

244

nit: drop unused default param

246

Comment here just echoes the code - remove?

254

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

225

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

234

Forgot about the new default SmallVector storage feature.

254

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

234

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

242

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)

254

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)

287

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)

292

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;
 
+llvm::Optional<llvm::StringRef>
+bestGuess(llvm::StringRef Search,
+          llvm::ArrayRef<llvm::StringRef> AllowedValues) {
+  unsigned MaxEdit = (Search.size() + 1) / 3;
+  if (!MaxEdit)
+    return llvm::None;
+  llvm::Optional<llvm::StringRef> Result;
+  for (const auto &AllowedValue : AllowedValues) {
+    unsigned EditDistance = Search.edit_distance(AllowedValue, true, MaxEdit);
+    // We can't do better than an edit distance of 1, so just return this and
+    // save computing other values.
+    if (EditDistance == 1U)
+      return AllowedValue;
+    if (EditDistance == MaxEdit && !Result) {
+      Result = AllowedValue;
+    } else if (EditDistance < MaxEdit) {
+      Result = AllowedValue;
+      MaxEdit = EditDistance;
+    }
+  }
+  return Result;
+}
+
 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
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, Seen);
+    }
+
+  private:
+    void warnUnknownKeys(llvm::ArrayRef<Located<std::string>> UnknownKeys,
+                         const llvm::SmallSet<std::string, 8> &SeenKeys) const {
+      llvm::SmallVector<llvm::StringRef> UnseenKeys;
+      for (const auto &KeyAndHandler : Keys)
+        if (!SeenKeys.count(KeyAndHandler.first.str()))
+          UnseenKeys.push_back(KeyAndHandler.first);
+
+      for (const Located<std::string> &UnknownKey : UnknownKeys)
+        if (auto BestGuess = bestGuess(*UnknownKey, UnseenKeys))
+          Outer->warning("Unknown " + Description + " key '" + *UnknownKey +
+                             "'; did you mean '" + *BestGuess + "'?",
+                         UnknownKey.Range);
+        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))
       return Located<std::string>(S->getValue(Buf).str(), N.getSourceRange());
     if (auto *BS = llvm::dyn_cast<BlockScalarNode>(&N))
       return Located<std::string>(BS->getValue().str(), N.getSourceRange());
     warning(Desc + " should be scalar", N);
     return llvm::None;
   }
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) {
     HadError = true;
-    SM.PrintMessage(N.getSourceRange().Start, llvm::SourceMgr::DK_Error, Msg,
-                    N.getSourceRange());
+    SM.PrintMessage(Range.Start, llvm::SourceMgr::DK_Error, Msg, Range);
+  }
+  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) {
+    SM.PrintMessage(Range.Start, llvm::SourceMgr::DK_Warning, Msg, Range);
+  }
   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/test/config.test

 {"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
 ---
 {"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///foo.c","languageId":"c","text":"int x = FOO;"}}}
 # First, the errors from the config file.
 #      CHECK:  "method": "textDocument/publishDiagnostics",
 # CHECK-NEXT:  "params": {
 # CHECK-NEXT:    "diagnostics": [
 # CHECK-NEXT:      {
-# CHECK-NEXT:        "message": "Unknown Config key Foo",
+# CHECK-NEXT:        "message": "Unknown Config key 'Foo'",
 # CHECK-NEXT:        "range": {
 # CHECK-NEXT:          "end": {
 # CHECK-NEXT:            "character": 3,
 # CHECK-NEXT:            "line": 0
 # CHECK-NEXT:          },
 # CHECK-NEXT:          "start": {
 # CHECK-NEXT:            "character": 0,
 # CHECK-NEXT:            "line": 0

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))));