Teach typo correction about various language keywords. We can't

generally recover from typos in keywords (since we would effectively
have to mangle the token stream). However, there are still benefits to
typo-correcting with keywords:
  - We don't make stupid suggestions when the user typed something
  that is similar to a keyword. 
  - We can suggest the keyword in a diagnostic (did you mean
  "static_cast"?), even if we can't recover and therefore don't have
  a fix-it.

llvm-svn: 101274

1 files changed, 267 insertions, 27 deletions

diff --git a/clang/lib/Sema/SemaLookup.cpp b/clang/lib/Sema/SemaLookup.cpp
index 0e2a10aeb0d..18b6e720506 100644
--- a/clang/lib/Sema/SemaLookup.cpp
+++ b/clang/lib/Sema/SemaLookup.cpp
@@ -2421,6 +2421,9 @@ class TypoCorrectionConsumer : public VisibleDeclConsumer {
   /// found (so far) with the typo name.
   llvm::SmallVector<NamedDecl *, 4> BestResults;
 
+  /// \brief The keywords that have the smallest edit distance.
+  llvm::SmallVector<IdentifierInfo *, 4> BestKeywords;
+  
   /// \brief The best edit distance found so far.
   unsigned BestEditDistance;
   
@@ -2429,13 +2432,23 @@ public:
     : Typo(Typo->getName()) { }
 
   virtual void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, bool InBaseClass);
+  void addKeywordResult(ASTContext &Context, llvm::StringRef Keyword);
 
   typedef llvm::SmallVector<NamedDecl *, 4>::const_iterator iterator;
   iterator begin() const { return BestResults.begin(); }
   iterator end() const { return BestResults.end(); }
-  bool empty() const { return BestResults.empty(); }
-
-  unsigned getBestEditDistance() const { return BestEditDistance; }
+  void clear_decls() { BestResults.clear(); }
+  
+  bool empty() const { return BestResults.empty() && BestKeywords.empty(); }
+
+  typedef llvm::SmallVector<IdentifierInfo *, 4>::const_iterator
+    keyword_iterator;
+  keyword_iterator keyword_begin() const { return BestKeywords.begin(); }
+  keyword_iterator keyword_end() const { return BestKeywords.end(); }
+  bool keyword_empty() const { return BestKeywords.empty(); }
+  unsigned keyword_size() const { return BestKeywords.size(); }
+  
+  unsigned getBestEditDistance() const { return BestEditDistance; }  
 };
 
 }
@@ -2457,11 +2470,12 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
   // entity. If this edit distance is not worse than the best edit
   // distance we've seen so far, add it to the list of results.
   unsigned ED = Typo.edit_distance(Name->getName());
-  if (!BestResults.empty()) {
+  if (!BestResults.empty() || !BestKeywords.empty()) {
     if (ED < BestEditDistance) {
       // This result is better than any we've seen before; clear out
       // the previous results.
       BestResults.clear();
+      BestKeywords.clear();
       BestEditDistance = ED;
     } else if (ED > BestEditDistance) {
       // This result is worse than the best results we've seen so far;
@@ -2474,6 +2488,28 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
   BestResults.push_back(ND);
 }
 
+void TypoCorrectionConsumer::addKeywordResult(ASTContext &Context, 
+                                              llvm::StringRef Keyword) {
+  // Compute the edit distance between the typo and this keyword.
+  // If this edit distance is not worse than the best edit
+  // distance we've seen so far, add it to the list of results.
+  unsigned ED = Typo.edit_distance(Keyword);
+  if (!BestResults.empty() || !BestKeywords.empty()) {
+    if (ED < BestEditDistance) {
+      BestResults.clear();
+      BestKeywords.clear();
+      BestEditDistance = ED;
+    } else if (ED > BestEditDistance) {
+      // This result is worse than the best results we've seen so far;
+      // ignore it.
+      return;
+    }
+  } else
+    BestEditDistance = ED;
+  
+  BestKeywords.push_back(&Context.Idents.get(Keyword));
+}
+
 /// \brief Try to "correct" a typo in the source code by finding
 /// visible declarations whose names are similar to the name that was
 /// present in the source code.
@@ -2494,6 +2530,9 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
 /// \param EnteringContext whether we're entering the context described by 
 /// the nested-name-specifier SS.
 ///
+/// \param CTC The context in which typo correction occurs, which impacts the
+/// set of keywords permitted.
+///
 /// \param OPT when non-NULL, the search for visible declarations will
 /// also walk the protocols in the qualified interfaces of \p OPT.
 ///
@@ -2502,8 +2541,10 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
 /// may contain the results of name lookup for the correct name or it may be
 /// empty.
 DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS,
-                       DeclContext *MemberContext, bool EnteringContext,
-                       const ObjCObjectPointerType *OPT) {
+                                  DeclContext *MemberContext, 
+                                  bool EnteringContext,
+                                  CorrectTypoContext CTC,
+                                  const ObjCObjectPointerType *OPT) {
   if (Diags.hasFatalErrorOccurred())
     return DeclarationName();
 
@@ -2529,8 +2570,10 @@ DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS,
   // instantiation.
   if (!ActiveTemplateInstantiations.empty())
     return DeclarationName();
-
+  
   TypoCorrectionConsumer Consumer(Typo);
+  
+  // Perform name lookup to find visible, similarly-named entities.
   if (MemberContext) {
     LookupVisibleDecls(MemberContext, Res.getLookupKind(), Consumer);
 
@@ -2551,37 +2594,231 @@ DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS,
     LookupVisibleDecls(S, Res.getLookupKind(), Consumer);
   }
 
+  // Add context-dependent keywords.
+  bool WantTypeSpecifiers = false;
+  bool WantExpressionKeywords = false;
+  bool WantCXXNamedCasts = false;
+  bool WantRemainingKeywords = false;
+  switch (CTC) {
+    case CTC_Unknown:
+      WantTypeSpecifiers = true;
+      WantExpressionKeywords = true;
+      WantCXXNamedCasts = true;
+      WantRemainingKeywords = true;
+      break;
+  
+    case CTC_NoKeywords:
+      break;
+  
+    case CTC_Type:
+      WantTypeSpecifiers = true;
+      break;
+      
+    case CTC_ObjCMessageReceiver:
+      Consumer.addKeywordResult(Context, "super");
+      // Fall through to handle message receivers like expressions.
+      
+    case CTC_Expression:
+      if (getLangOptions().CPlusPlus)
+        WantTypeSpecifiers = true;
+      WantExpressionKeywords = true;
+      // Fall through to get C++ named casts.
+      
+    case CTC_CXXCasts:
+      WantCXXNamedCasts = true;
+      break;
+      
+    case CTC_MemberLookup:
+      if (getLangOptions().CPlusPlus)
+        Consumer.addKeywordResult(Context, "template");
+      break;
+  }
+
+  if (WantTypeSpecifiers) {
+    // Add type-specifier keywords to the set of results.
+    const char *CTypeSpecs[] = {
+      "char", "const", "double", "enum", "float", "int", "long", "short",
+      "signed", "struct", "union", "unsigned", "void", "volatile", "_Bool",
+      "_Complex", "_Imaginary",
+      // storage-specifiers as well
+      "extern", "inline", "static", "typedef"
+    };
+    
+    const unsigned NumCTypeSpecs = sizeof(CTypeSpecs) / sizeof(CTypeSpecs[0]);
+    for (unsigned I = 0; I != NumCTypeSpecs; ++I)
+      Consumer.addKeywordResult(Context, CTypeSpecs[I]);
+    
+    if (getLangOptions().C99)
+      Consumer.addKeywordResult(Context, "restrict");
+    if (getLangOptions().Bool || getLangOptions().CPlusPlus)
+      Consumer.addKeywordResult(Context, "bool");
+    
+    if (getLangOptions().CPlusPlus) {
+      Consumer.addKeywordResult(Context, "class");
+      Consumer.addKeywordResult(Context, "typename");
+      Consumer.addKeywordResult(Context, "wchar_t");
+      
+      if (getLangOptions().CPlusPlus0x) {
+        Consumer.addKeywordResult(Context, "char16_t");
+        Consumer.addKeywordResult(Context, "char32_t");
+        Consumer.addKeywordResult(Context, "constexpr");
+        Consumer.addKeywordResult(Context, "decltype");
+        Consumer.addKeywordResult(Context, "thread_local");
+      }      
+    }
+        
+    if (getLangOptions().GNUMode)
+      Consumer.addKeywordResult(Context, "typeof");
+  }
+  
+  if (WantCXXNamedCasts) {
+    Consumer.addKeywordResult(Context, "const_cast");
+    Consumer.addKeywordResult(Context, "dynamic_cast");
+    Consumer.addKeywordResult(Context, "reinterpret_cast");
+    Consumer.addKeywordResult(Context, "static_cast");
+  }
+  
+  if (WantExpressionKeywords) {
+    Consumer.addKeywordResult(Context, "sizeof");
+    if (getLangOptions().Bool || getLangOptions().CPlusPlus) {
+      Consumer.addKeywordResult(Context, "false");
+      Consumer.addKeywordResult(Context, "true");
+    }
+    
+    if (getLangOptions().CPlusPlus) {
+      const char *CXXExprs[] = { 
+        "delete", "new", "operator", "throw", "typeid" 
+      };
+      const unsigned NumCXXExprs = sizeof(CXXExprs) / sizeof(CXXExprs[0]);
+      for (unsigned I = 0; I != NumCXXExprs; ++I)
+        Consumer.addKeywordResult(Context, CXXExprs[I]);
+      
+      if (isa<CXXMethodDecl>(CurContext) &&
+          cast<CXXMethodDecl>(CurContext)->isInstance())
+        Consumer.addKeywordResult(Context, "this");
+      
+      if (getLangOptions().CPlusPlus0x) {
+        Consumer.addKeywordResult(Context, "alignof");
+        Consumer.addKeywordResult(Context, "nullptr");
+      }
+    }
+  }
+  
+  if (WantRemainingKeywords) {
+    if (getCurFunctionOrMethodDecl() || getCurBlock()) {
+      // Statements.
+      const char *CStmts[] = {
+        "do", "else", "for", "goto", "if", "return", "switch", "while" };
+      const unsigned NumCStmts = sizeof(CStmts) / sizeof(CStmts[0]);
+      for (unsigned I = 0; I != NumCStmts; ++I)
+        Consumer.addKeywordResult(Context, CStmts[I]);
+      
+      if (getLangOptions().CPlusPlus) {
+        Consumer.addKeywordResult(Context, "catch");
+        Consumer.addKeywordResult(Context, "try");
+      }
+      
+      if (S && S->getBreakParent())
+        Consumer.addKeywordResult(Context, "break");
+      
+      if (S && S->getContinueParent())
+        Consumer.addKeywordResult(Context, "continue");
+      
+      if (!getSwitchStack().empty()) {
+        Consumer.addKeywordResult(Context, "case");
+        Consumer.addKeywordResult(Context, "default");
+      }
+    } else {
+      if (getLangOptions().CPlusPlus) {
+        Consumer.addKeywordResult(Context, "namespace");
+        Consumer.addKeywordResult(Context, "template");
+      }
+
+      if (S && S->isClassScope()) {
+        Consumer.addKeywordResult(Context, "explicit");
+        Consumer.addKeywordResult(Context, "friend");
+        Consumer.addKeywordResult(Context, "mutable");
+        Consumer.addKeywordResult(Context, "private");
+        Consumer.addKeywordResult(Context, "protected");
+        Consumer.addKeywordResult(Context, "public");
+        Consumer.addKeywordResult(Context, "virtual");
+      }
+    }
+        
+    if (getLangOptions().CPlusPlus) {
+      Consumer.addKeywordResult(Context, "using");
+
+      if (getLangOptions().CPlusPlus0x)
+        Consumer.addKeywordResult(Context, "static_assert");
+    }
+  }
+  
+  // If we haven't found anything, we're done.
   if (Consumer.empty())
     return DeclarationName();
 
   // Only allow a single, closest name in the result set (it's okay to
   // have overloads of that name, though).
-  TypoCorrectionConsumer::iterator I = Consumer.begin();
-  DeclarationName BestName = (*I)->getDeclName();
-
-  // If we've found an Objective-C ivar or property, don't perform
-  // name lookup again; we'll just return the result directly.
-  NamedDecl *FoundBest = 0;
-  if (isa<ObjCIvarDecl>(*I) || isa<ObjCPropertyDecl>(*I))
-    FoundBest = *I;
-  ++I;
-  for(TypoCorrectionConsumer::iterator IEnd = Consumer.end(); I != IEnd; ++I) {
-    if (BestName != (*I)->getDeclName())
+  DeclarationName BestName;
+  NamedDecl *BestIvarOrPropertyDecl = 0;
+  bool FoundIvarOrPropertyDecl = false;
+  
+  // Check all of the declaration results to find the best name so far.
+  for (TypoCorrectionConsumer::iterator I = Consumer.begin(), 
+                                     IEnd = Consumer.end();
+       I != IEnd; ++I) {
+    if (!BestName)
+      BestName = (*I)->getDeclName();
+    else if (BestName != (*I)->getDeclName())
       return DeclarationName();
 
-    // FIXME: If there are both ivars and properties of the same name,
-    // don't return both because the callee can't handle two
-    // results. We really need to separate ivar lookup from property
-    // lookup to avoid this problem.
-    FoundBest = 0;
+    // \brief Keep track of either an Objective-C ivar or a property, but not
+    // both.
+    if (isa<ObjCIvarDecl>(*I) || isa<ObjCPropertyDecl>(*I)) {
+      if (FoundIvarOrPropertyDecl)
+        BestIvarOrPropertyDecl = 0;
+      else {
+        BestIvarOrPropertyDecl = *I;
+        FoundIvarOrPropertyDecl = true;
+      }
+    }
   }
 
+  // Now check all of the keyword results to find the best name. 
+  switch (Consumer.keyword_size()) {
+    case 0:
+      // No keywords matched.
+      break;
+      
+    case 1:
+      // If we already have a name
+      if (!BestName) {
+        // We did not have anything previously, 
+        BestName = *Consumer.keyword_begin();
+      } else if (BestName.getAsIdentifierInfo() == *Consumer.keyword_begin()) {
+        // We have a declaration with the same name as a context-sensitive
+        // keyword. The keyword takes precedence.
+        BestIvarOrPropertyDecl = 0;
+        FoundIvarOrPropertyDecl = false;
+        Consumer.clear_decls();
+      } else {
+        // Name collision; we will not correct typos.
+        return DeclarationName();
+      }
+      break;
+      
+    default:
+      // Name collision; we will not correct typos.
+      return DeclarationName();
+  }
+  
   // BestName is the closest viable name to what the user
   // typed. However, to make sure that we don't pick something that's
   // way off, make sure that the user typed at least 3 characters for
   // each correction.
   unsigned ED = Consumer.getBestEditDistance();
-  if (ED == 0 || (BestName.getAsIdentifierInfo()->getName().size() / ED) < 3)
+  if (ED == 0 || !BestName.getAsIdentifierInfo() ||
+      (BestName.getAsIdentifierInfo()->getName().size() / ED) < 3)
     return DeclarationName();
 
   // Perform name lookup again with the name we chose, and declare
@@ -2591,11 +2828,14 @@ DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS,
 
   // If we found an ivar or property, add that result; no further
   // lookup is required.
-  if (FoundBest)
-    Res.addDecl(FoundBest);  
+  if (BestIvarOrPropertyDecl)
+    Res.addDecl(BestIvarOrPropertyDecl);  
   // If we're looking into the context of a member, perform qualified
   // name lookup on the best name.
-  else if (MemberContext)
+  else if (!Consumer.keyword_empty()) {
+    // The best match was a keyword. Return it.
+    return BestName;
+  } else if (MemberContext)
     LookupQualifiedName(Res, MemberContext);
   // Perform lookup as if we had just parsed the best name.
   else