[ASTMatchers][Dynamic] Provide Fallback and suggestions for typos.

[njames93]

Summary

If there is a typo in parsing and we can see a close match, offer a suggestion hint and in the case of matchers carry on parsing to see if more diags are generated.

[njames93]

Tests haven't been added yet, wanted to gauge opinions on this first before fully committing to it.

clang/lib/ASTMatchers/Dynamic/TypoSuggester.cpp

40

Duly noted :)

[njames93]

Address clang-tidy issue.

[njames93]

clang/include/clang/ASTMatchers/Dynamic/Diagnostics.h

62–72

Any reason for these being explicitly initialized?

[steveire]

I like the idea, but I think you're violating the Interface Segregation Principle by putting it in the Registry::lookupMatcherCtor implementation. The interface here is easy to use incorrectly. Consider adding a new method instead. That way, lookupMatcherCtor will continue to do what it's name says it does and it will never return a "wrong" matcher. A new lookupCloseMatch API can be called if the optional returned by lookupMatcherCtor is None. That seems to be a more consistent API.

clang/include/clang/ASTMatchers/Dynamic/Diagnostics.h

enum ContextType {
     CT_MatcherArg = 0,
     CT_MatcherConstruct = 1
   };
 
   /// All errors from the system.
   enum ErrorType {
     ET_None = 0,
 
     ET_RegistryMatcherNotFound = 1,
-    ET_RegistryWrongArgCount = 2,
-    ET_RegistryWrongArgType = 3,
-    ET_RegistryNotBindable = 4,
-    ET_RegistryAmbiguousOverload = 5,
-    ET_RegistryValueNotFound = 6,
-    ET_RegistryUnknownEnumWithReplace = 7,
-    ET_RegistryNonNodeMatcher = 8,
-    ET_RegistryMatcherNoWithSupport = 9,
+    ET_RegistryMatcherNotFoundWithReplace = 2,
+    ET_RegistryWrongArgCount = 3,
+    ET_RegistryWrongArgType = 4,
+    ET_RegistryNotBindable = 5,
+    ET_RegistryAmbiguousOverload = 6,
+    ET_RegistryValueNotFound = 7,
+    ET_RegistryValueNotFoundWithReplace = 8,
+    ET_RegistryUnknownEnumWithReplace = 9,
+    ET_RegistryNonNodeMatcher = 10,
+    ET_RegistryMatcherNoWithSupport = 11,
 
     ET_ParserStringError = 100,
     ET_ParserNoOpenParen = 101,
     ET_ParserNoCloseParen = 102,
     ET_ParserNoComma = 103,
     ET_ParserNoCode = 104,
     ET_ParserNotAMatcher = 105,
     ET_ParserInvalidToken = 106,

clang/include/clang/ASTMatchers/Dynamic/Parser.h

virtual VariantMatcher actOnMatcherExpression(MatcherCtor Ctor,
                                                   StringRef BindID,
                                                   ArrayRef<ParserValue> Args,
                                                   Diagnostics *Error) = 0;
 
     /// Look up a matcher by name.
     ///
     /// \param MatcherName The matcher name found by the parser.
     ///
-    /// \return The matcher constructor, or Optional<MatcherCtor>() if not
-    /// found.
+    /// \param SuggestedTypo If non-null and no matcher constructor was found,
+    /// This will be set to the closest matching name if any exists.
+    ///
+    /// \return The matcher constructor if found. If match not found but \p
+    /// SuggestedTypo was non-null and a close match was found, the
+    /// corresponding match constructor will be returned to let further error
+    /// checking continue.
     virtual llvm::Optional<MatcherCtor>
-    lookupMatcherCtor(StringRef MatcherName) = 0;
+    lookupMatcherCtor(StringRef MatcherName,
+                      StringRef *SuggestedTypo = nullptr) = 0;
 
     virtual bool isBuilderMatcher(MatcherCtor) const = 0;
 
     virtual ASTNodeKind nodeMatcherType(MatcherCtor) const = 0;
 
     virtual internal::MatcherDescriptorPtr
     buildMatcherCtor(MatcherCtor, SourceRange NameRange,
                      ArrayRef<ParserValue> Args, Diagnostics *Error) const = 0;
public:
 
   /// Sema implementation that uses the matcher registry to process the
   ///   tokens.
   class RegistrySema : public Parser::Sema {
   public:
     ~RegistrySema() override;
 
     llvm::Optional<MatcherCtor>
-    lookupMatcherCtor(StringRef MatcherName) override;
+    lookupMatcherCtor(StringRef MatcherName, StringRef *SuggestedTypo) override;
 
     VariantMatcher actOnMatcherExpression(MatcherCtor Ctor,
                                           SourceRange NameRange,
                                           StringRef BindID,
                                           ArrayRef<ParserValue> Args,
                                           Diagnostics *Error) override;
 
     std::vector<ArgKind> getAcceptedCompletionTypes(

clang/include/clang/ASTMatchers/Dynamic/Registry.h

public:
   static internal::MatcherDescriptorPtr
   buildMatcherCtor(MatcherCtor, SourceRange NameRange,
                    ArrayRef<ParserValue> Args, Diagnostics *Error);
 
   /// Look up a matcher in the registry by name,
   ///
   /// \return An opaque value which may be used to refer to the matcher
   /// constructor, or Optional<MatcherCtor>() if not found.
-  static llvm::Optional<MatcherCtor> lookupMatcherCtor(StringRef MatcherName);
+  static llvm::Optional<MatcherCtor> lookupMatcherCtor(StringRef MatcherName,
+                                                       StringRef *SuggestTypo);
 
   /// Compute the list of completion types for \p Context.
   ///
   /// Each element of \p Context represents a matcher invocation, going from
   /// outermost to innermost. Elements are pairs consisting of a reference to
   /// the matcher constructor and the index of the next element in the
   /// argument list of that matcher (or for the last element, the index of
   /// the completion point in the argument list). An empty list requests

clang/lib/ASTMatchers/Dynamic/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
 )
 
 add_clang_library(clangDynamicASTMatchers
   Diagnostics.cpp
   Marshallers.cpp
   Parser.cpp
   Registry.cpp
+  TypoSuggester.cpp
   VariantValue.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
 
   DEPENDS
   omp_gen
   )

clang/lib/ASTMatchers/Dynamic/Diagnostics.cpp

static StringRef contextTypeToFormatString(Diagnostics::ContextType Type) {
   }
   llvm_unreachable("Unknown ContextType value.");
 }
 
 static StringRef errorTypeToFormatString(Diagnostics::ErrorType Type) {
   switch (Type) {
   case Diagnostics::ET_RegistryMatcherNotFound:
     return "Matcher not found: $0";
+  case Diagnostics::ET_RegistryMatcherNotFoundWithReplace:
+    return "Matcher not found: $0; did you mean $1?";
   case Diagnostics::ET_RegistryWrongArgCount:
     return "Incorrect argument count. (Expected = $0) != (Actual = $1)";
   case Diagnostics::ET_RegistryWrongArgType:
     return "Incorrect type for arg $0. (Expected = $1) != (Actual = $2)";
   case Diagnostics::ET_RegistryNotBindable:
     return "Matcher does not support binding.";
   case Diagnostics::ET_RegistryAmbiguousOverload:
     // TODO: Add type info about the overload error.
     return "Ambiguous matcher overload.";
   case Diagnostics::ET_RegistryValueNotFound:
     return "Value not found: $0";
+  case Diagnostics::ET_RegistryValueNotFoundWithReplace:
+    return "Value not found: $0; did you mean $1?";
   case Diagnostics::ET_RegistryUnknownEnumWithReplace:
     return "Unknown value '$1' for arg $0; did you mean '$2'";
   case Diagnostics::ET_RegistryNonNodeMatcher:
     return "Matcher not a node matcher: $0";
   case Diagnostics::ET_RegistryMatcherNoWithSupport:
     return "Matcher does not support with call.";
 
   case Diagnostics::ET_ParserStringError:

clang/lib/ASTMatchers/Dynamic/Parser.cpp

 //===- Parser.cpp - Matcher expression parser -----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// Recursive parser implementation for the matcher expression grammar.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "clang/ASTMatchers/Dynamic/Parser.h"
+#include "TypoSuggester.h"
 #include "clang/ASTMatchers/ASTMatchersInternal.h"
 #include "clang/ASTMatchers/Dynamic/Diagnostics.h"
 #include "clang/ASTMatchers/Dynamic/Registry.h"
 #include "clang/Basic/CharInfo.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"

 };
 
 /// Parse expressions that start with an identifier.
 ///
 /// This function can parse named values and matchers.
 /// In case of failure it will try to determine the user's intent to give
 /// an appropriate error message.
 bool Parser::parseIdentifierPrefixImpl(VariantValue *Value) {
-  const TokenInfo NameToken = Tokenizer->consumeNextToken();
+  TokenInfo NameToken = Tokenizer->consumeNextToken();
 
   if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
     // Parse as a named value.
     if (const VariantValue NamedValue =
             NamedValues ? NamedValues->lookup(NameToken.Text)
                         : VariantValue()) {
 
       if (Tokenizer->nextTokenKind() != TokenInfo::TK_Period) {
if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
 
     // If the syntax is correct and the name is not a matcher either, report
     // unknown named value.
     if ((Tokenizer->nextTokenKind() == TokenInfo::TK_Comma ||
          Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen ||
          Tokenizer->nextTokenKind() == TokenInfo::TK_NewLine ||
          Tokenizer->nextTokenKind() == TokenInfo::TK_Eof) &&
         !S->lookupMatcherCtor(NameToken.Text)) {
+      TypoSuggester T(NameToken.Text, TypoSuggester::AutoMaxEdit);
+      if (NamedValues) {
+        for (const auto &NamedValue : *NamedValues) {
+          if (T.addSuggestion(NamedValue.getKey()))
+            break;
+        }
+      }
+      if (T.foundSuggestion())
+        Error->addError(NameToken.Range,
+                        Error->ET_RegistryValueNotFoundWithReplace)
+            << NameToken.Text << T.getSuggestion();
+      else
         Error->addError(NameToken.Range, Error->ET_RegistryValueNotFound)
             << NameToken.Text;
       return false;
     }
     // Otherwise, fallback to the matcher parser.
   }
 
   Tokenizer->SkipNewlines();
 
   assert(NameToken.Kind == TokenInfo::TK_Ident);
   TokenInfo OpenToken = Tokenizer->consumeNextToken();
   if (OpenToken.Kind != TokenInfo::TK_OpenParen) {
     Error->addError(OpenToken.Range, Error->ET_ParserNoOpenParen)
         << OpenToken.Text;
     return false;
   }
 
-  llvm::Optional<MatcherCtor> Ctor = S->lookupMatcherCtor(NameToken.Text);
+  StringRef Typo;
+  llvm::Optional<MatcherCtor> Ctor =
+      S->lookupMatcherCtor(NameToken.Text, &Typo);
+
+  if (!Typo.empty()) {
+    Error->addError(NameToken.Range,
+                    Error->ET_RegistryMatcherNotFoundWithReplace)
+        << NameToken.Text << Typo;
+    // Update the NameToken so diagnostics are better.
+    NameToken.Text = Typo;
+  }
 
   // Parse as a matcher expression.
-  return parseMatcherExpressionImpl(NameToken, OpenToken, Ctor, Value);
+  return parseMatcherExpressionImpl(NameToken, OpenToken, Ctor, Value) &&
+         Typo.empty();
 }
 
 bool Parser::parseBindID(std::string &BindID) {
   // Parse the parenthesized argument to .bind("foo")
   const TokenInfo OpenToken = Tokenizer->consumeNextToken();
   const TokenInfo IDToken = Tokenizer->consumeNextTokenIgnoreNewlines();
   const TokenInfo CloseToken = Tokenizer->consumeNextTokenIgnoreNewlines();
 

 }
 
 bool Parser::parseMatcherBuilder(MatcherCtor Ctor, const TokenInfo &NameToken,
                                  const TokenInfo &OpenToken,
                                  VariantValue *Value) {
   std::vector<ParserValue> Args;
   TokenInfo EndToken;
 
+  bool HasError = false;
+
   Tokenizer->SkipNewlines();
 
   {
     ScopedContextEntry SCE(this, Ctor);
 
     while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
       if (Tokenizer->nextTokenKind() == TokenInfo::TK_CloseParen) {
         // End of args.
while (Tokenizer->nextTokenKind() != TokenInfo::TK_Eof) {
         Error->addError(NameToken.Range, Error->ET_ParserFailedToBuildMatcher)
             << NameToken.Text;
         return false;
       }
 
       ArgValue.Text = NodeMatcherToken.Text;
       ArgValue.Range = NodeMatcherToken.Range;
 
+      StringRef Typo;
+
       llvm::Optional<MatcherCtor> MappedMatcher =
-          S->lookupMatcherCtor(ArgValue.Text);
+          S->lookupMatcherCtor(ArgValue.Text, &Typo);
 
       if (!MappedMatcher) {
         Error->addError(NodeMatcherToken.Range,
                         Error->ET_RegistryMatcherNotFound)
             << NodeMatcherToken.Text;
         return false;
       }
+      if (!Typo.empty()) {
+        Error->addError(NodeMatcherToken.Range,
+                        Error->ET_RegistryMatcherNotFoundWithReplace)
+            << NodeMatcherToken.Text << Typo;
+        HasError = true;
+      }
 
       ASTNodeKind NK = S->nodeMatcherType(*MappedMatcher);
 
       if (NK.isNone()) {
         Error->addError(NodeMatcherToken.Range,
                         Error->ET_RegistryNonNodeMatcher)
             << NodeMatcherToken.Text;
         return false;
if (ChainCallToken.Text == TokenInfo::ID_Bind) {
       SourceRange MatcherRange = NameToken.Range;
       MatcherRange.End = ChainCallToken.Range.End;
       VariantMatcher Result = S->actOnMatcherExpression(
           BuiltCtor.get(), MatcherRange, BindID, {}, Error);
       if (Result.isNull())
         return false;
 
       *Value = Result;
-      return true;
+      return !HasError;
     } else if (ChainCallToken.Text == TokenInfo::ID_With) {
       Tokenizer->SkipNewlines();
 
       if (Tokenizer->nextTokenKind() != TokenInfo::TK_OpenParen) {
         StringRef ErrTxt = Tokenizer->nextTokenKind() == TokenInfo::TK_Eof
                                ? StringRef("EOF")
                                : Tokenizer->peekNextToken().Text;
         Error->addError(Tokenizer->peekNextToken().Range,
                         Error->ET_ParserNoOpenParen)
             << ErrTxt;
         return false;
       }
 
       TokenInfo WithOpenToken = Tokenizer->consumeNextToken();
 
       return parseMatcherExpressionImpl(NameToken, WithOpenToken,
-                                        BuiltCtor.get(), Value);
+                                        BuiltCtor.get(), Value) &&
+             !HasError;
     }
   }
 
   Diagnostics::Context Ctx(Diagnostics::Context::ConstructMatcher, Error,
                            NameToken.Text, NameToken.Range);
   SourceRange MatcherRange = NameToken.Range;
   MatcherRange.End = EndToken.Range.End;
   VariantMatcher Result = S->actOnMatcherExpression(
       BuiltCtor.get(), MatcherRange, BindID, {}, Error);
   if (Result.isNull())
     return false;
 
   *Value = Result;
-  return true;
+  return !HasError;
 }
 
 /// Parse and validate a matcher expression.
 /// \return \c true on success, in which case \c Value has the matcher parsed.
 ///   If the input is malformed, or some argument has an error, it
 ///   returns \c false.
 bool Parser::parseMatcherExpressionImpl(const TokenInfo &NameToken,
                                         const TokenInfo &OpenToken,

 Parser::Parser(CodeTokenizer *Tokenizer, Sema *S,
                const NamedValueMap *NamedValues, Diagnostics *Error)
     : Tokenizer(Tokenizer), S(S ? S : &*DefaultRegistrySema),
       NamedValues(NamedValues), Error(Error) {}
 
 Parser::RegistrySema::~RegistrySema() = default;
 
 llvm::Optional<MatcherCtor>
-Parser::RegistrySema::lookupMatcherCtor(StringRef MatcherName) {
-  return Registry::lookupMatcherCtor(MatcherName);
+Parser::RegistrySema::lookupMatcherCtor(StringRef MatcherName,
+                                        StringRef *SuggestedTypo) {
+  return Registry::lookupMatcherCtor(MatcherName, SuggestedTypo);
 }
 
 VariantMatcher Parser::RegistrySema::actOnMatcherExpression(
     MatcherCtor Ctor, SourceRange NameRange, StringRef BindID,
     ArrayRef<ParserValue> Args, Diagnostics *Error) {
   if (BindID.empty()) {
     return Registry::constructMatcher(Ctor, NameRange, Args, Error);
   } else {

clang/lib/ASTMatchers/Dynamic/Registry.cpp

 //===- Registry.cpp - Matcher registry ------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// Registry map populated at static initialization time.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/ASTMatchers/Dynamic/Registry.h"
 #include "Marshallers.h"
+#include "TypoSuggester.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/ASTMatchers/Dynamic/Diagnostics.h"
 #include "clang/ASTMatchers/Dynamic/VariantValue.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"

 internal::MatcherDescriptorPtr
 Registry::buildMatcherCtor(MatcherCtor Ctor, SourceRange NameRange,
                            ArrayRef<ParserValue> Args, Diagnostics *Error) {
   return internal::MatcherDescriptorPtr(
       Ctor->buildMatcherCtor(NameRange, Args, Error).release());
 }
 
 // static
-llvm::Optional<MatcherCtor> Registry::lookupMatcherCtor(StringRef MatcherName) {
+llvm::Optional<MatcherCtor>
+Registry::lookupMatcherCtor(StringRef MatcherName, StringRef *SuggestedTypo) {
   auto it = RegistryData->constructors().find(MatcherName);
-  return it == RegistryData->constructors().end()
-             ? llvm::Optional<MatcherCtor>()
-             : it->second.get();
+  if (it != RegistryData->constructors().end())
+    return it->second.get();
+  if (SuggestedTypo) {
+    TypoSuggester T(MatcherName, TypoSuggester::AutoMaxEdit);
+    for (const auto &Ctor : RegistryData->constructors()) {
+      if (T.addSuggestion(Ctor.getKey()))
+        break;
+    }
+    if (T.foundSuggestion()) {
+      *SuggestedTypo = T.getSuggestion();
+      // If we found a good suggestion, return the Ctor so parsing can continue,
+      // The error state is conveyed by SuggestedTypo being written to.
+      return RegistryData->constructors().find(T.getSuggestion())->second.get();
+    }
+  }
+  return llvm::None;
 }
 
 static llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                      const std::set<ASTNodeKind> &KS) {
   unsigned Count = 0;
   for (std::set<ASTNodeKind>::const_iterator I = KS.begin(), E = KS.end();
        I != E; ++I) {
     if (I != KS.begin())

clang/lib/ASTMatchers/Dynamic/TypoSuggester.h

+//===- TypoSuggester.h ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_ASTMATCHERS_DYNAMIC_TYPOSUGGESTER_H
+#define LLVM_CLANG_LIB_ASTMATCHERS_DYNAMIC_TYPOSUGGESTER_H
+
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+// Helper class for getting the closest match for a typo string.
+// If OwnSuggestions is true, temporary strings can be passed to addSuggestion.
+class TypoSuggester {
+  llvm::StringRef Current;
+  const llvm::StringRef Value;
+  unsigned BestDistance;
+  bool HasMatch = false;
+
+public:
+  enum AutoMaxEditT { AutoMaxEdit };
+  TypoSuggester(llvm::StringRef Value, AutoMaxEditT)
+      : Value(Value), BestDistance((Value.size() + 3U) / 5U) {
+    // This BestDistance is rather arbitrary but prevents generating suggestions
+    // for single character values and grows more lenient as the value grows.
+  }
+  TypoSuggester(llvm::StringRef Target,
+                unsigned MaxEdit = std::numeric_limits<unsigned>::max())
+      : Value(Target), BestDistance(MaxEdit) {
+    assert(MaxEdit > 0);
+  }
+
+  // Returns true if we reach a state where we can never find a unique closest
+  // match.
+  bool addSuggestion(llvm::StringRef Suggest);
+  // If true, we are in a state where we can never find a unique closest match.
+  bool hasFailed() const { return BestDistance == 0; }
+  bool foundSuggestion() const { return HasMatch; }
+  llvm::StringRef getSuggestion() const {
+    assert(foundSuggestion());
+    return Current;
+  }
+};
+
+} // namespace dynamic
+} // namespace ast_matchers
+} // namespace clang
+
+#endif // LLVM_CLANG_LIB_ASTMATCHERS_DYNAMIC_TYPOSUGGESTER_H

clang/lib/ASTMatchers/Dynamic/TypoSuggester.cpp

+//===- TypoSuggester.cpp --------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "TypoSuggester.h"
+
+namespace clang {
+namespace ast_matchers {
+namespace dynamic {
+bool TypoSuggester::addSuggestion(llvm::StringRef Suggest) {
+  unsigned Dist = Value.edit_distance(Suggest, true, BestDistance);
+  if (Dist > BestDistance)
+    return false;
+  if (Dist == BestDistance) {
+    if (HasMatch) {
+      // If we already have a completion candidate with the same edit
+      // distance, we can't be sure so disregard both.
+      HasMatch = false;
+      --BestDistance;
+      // As we assume Target will never appear in Suggest, once we reach a
+      // case where we need 0 edits, we can stop work.
+      return BestDistance == 0;
+    }
+    Current = Suggest;
+    HasMatch = true;
+    return false;
+  }
+  Current = Suggest;
+  HasMatch = true;
+  BestDistance = Dist;
+  return false;
+}
+} // namespace dynamic
+} // namespace ast_matchers
+} // namespace clang
 No newline at end of file