When performing typo correction, look through the set of known

identifiers to determine good typo-correction candidates. Once we've
identified those candidates, we perform name lookup on each of them
and the consider the results. 

This optimization makes typo correction > 2x faster on a benchmark
example using a single typo (NSstring) in a tiny file that includes
Cocoa.h from a precompiled header, since we are deserializing far less
information now during typo correction.

There is a semantic change here, which is interesting. The presence of
a similarly-named entity that is not visible can now affect typo
correction. This is both good (you won't get weird corrections if the
thing you wanted isn't in scope) and bad (you won't get good
corrections if there is a similarly-named-but-completely-unrelated
thing). Time will tell whether it was a good choice or not.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@116528 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 116 insertions, 10 deletions

diff --git a/lib/Basic/IdentifierTable.cpp b/lib/Basic/IdentifierTable.cpp
index bd30c68da2..4ea6cedeb5 100644
--- a/lib/Basic/IdentifierTable.cpp
+++ b/lib/Basic/IdentifierTable.cpp
@@ -44,8 +44,24 @@ IdentifierInfo::IdentifierInfo() {
 // IdentifierTable Implementation
 //===----------------------------------------------------------------------===//
 
+IdentifierIterator::~IdentifierIterator() { }
+
 IdentifierInfoLookup::~IdentifierInfoLookup() {}
 
+namespace {
+  /// \brief A simple identifier lookup iterator that represents an
+  /// empty sequence of identifiers.
+  class EmptyLookupIterator : public IdentifierIterator
+  {
+  public:
+    virtual llvm::StringRef Next() { return llvm::StringRef(); }
+  };
+}
+
+IdentifierIterator *IdentifierInfoLookup::getIdentifiers() const {
+  return new EmptyLookupIterator();
+}
+
 ExternalIdentifierLookup::~ExternalIdentifierLookup() {}
 
 IdentifierTable::IdentifierTable(const LangOptions &LangOpts,
diff --git a/lib/Sema/SemaExprObjC.cpp b/lib/Sema/SemaExprObjC.cpp
index 055edd9710..1a90a2aaff 100644
--- a/lib/Sema/SemaExprObjC.cpp
+++ b/lib/Sema/SemaExprObjC.cpp
@@ -557,9 +557,10 @@ Sema::ObjCMessageKind Sema::getObjCMessageKind(Scope *S,
   ReceiverType = ParsedType();
 
   // If the identifier is "super" and there is no trailing dot, we're
-  // messaging super.
-  if (IsSuper && !HasTrailingDot && S->isInObjcMethodScope())
-    return ObjCSuperMessage;
+  // messaging super. If the identifier is "super" and there is a
+  // trailing dot, it's an instance message.
+  if (IsSuper && S->isInObjcMethodScope())
+    return HasTrailingDot? ObjCInstanceMessage : ObjCSuperMessage;
   
   LookupResult Result(*this, Name, NameLoc, LookupOrdinaryName);
   LookupName(Result, S);
@@ -568,14 +569,15 @@ Sema::ObjCMessageKind Sema::getObjCMessageKind(Scope *S,
   case LookupResult::NotFound:
     // Normal name lookup didn't find anything. If we're in an
     // Objective-C method, look for ivars. If we find one, we're done!
-    // FIXME: This is a hack. Ivar lookup should be part of normal lookup.
+    // FIXME: This is a hack. Ivar lookup should be part of normal
+    // lookup.
     if (ObjCMethodDecl *Method = getCurMethodDecl()) {
       ObjCInterfaceDecl *ClassDeclared;
       if (Method->getClassInterface()->lookupInstanceVariable(Name, 
                                                               ClassDeclared))
         return ObjCInstanceMessage;
     }
-      
+  
     // Break out; we'll perform typo correction below.
     break;
 
diff --git a/lib/Sema/SemaLookup.cpp b/lib/Sema/SemaLookup.cpp
index b363e57951..f12ac22f3d 100644
--- a/lib/Sema/SemaLookup.cpp
+++ b/lib/Sema/SemaLookup.cpp
@@ -2694,6 +2694,7 @@ public:
       BestEditDistance((std::numeric_limits<unsigned>::max)()) { }
 
   virtual void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, bool InBaseClass);
+  void FoundName(llvm::StringRef Name);
   void addKeywordResult(ASTContext &Context, llvm::StringRef Keyword);
 
   typedef llvm::StringMap<bool, llvm::BumpPtrAllocator>::iterator iterator;
@@ -2721,10 +2722,17 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
   if (!Name)
     return;
 
+  FoundName(Name->getName());
+}
+
+void TypoCorrectionConsumer::FoundName(llvm::StringRef Name) {
   // Compute the edit distance between the typo and the name of this
   // 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());
+  unsigned ED = Typo.edit_distance(Name);
+  if (ED == 0)
+    return;
+  
   if (ED < BestEditDistance) {
     // This result is better than any we've seen before; clear out
     // the previous results.
@@ -2735,12 +2743,12 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
     // ignore it.
     return;
   }
-
+  
   // Add this name to the list of results. By not assigning a value, we
   // keep the current value if we've seen this name before (either as a
   // keyword or as a declaration), or get the default value (not a keyword)
   // if we haven't seen it before.
-  (void)BestResults[Name->getName()];
+  (void)BestResults[Name];  
 }
 
 void TypoCorrectionConsumer::addKeywordResult(ASTContext &Context, 
@@ -2842,7 +2850,25 @@ DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS,
     
     LookupVisibleDecls(DC, Res.getLookupKind(), Consumer);
   } else {
-    LookupVisibleDecls(S, Res.getLookupKind(), Consumer);
+    // For unqualified lookup, look through all of the names that we have
+    // seen in this translation unit.
+    for (IdentifierTable::iterator I = Context.Idents.begin(), 
+                                IEnd = Context.Idents.end();
+         I != IEnd; ++I)
+      Consumer.FoundName(I->getKey());
+    
+    // Walk through identifiers in external identifier sources.
+    if (IdentifierInfoLookup *External
+                              = Context.Idents.getExternalIdentifierLookup()) {
+      IdentifierIterator *Iter = External->getIdentifiers();
+      do {
+        llvm::StringRef Name = Iter->Next();
+        if (Name.empty())
+          break;
+
+        Consumer.FoundName(Name);
+      } while (true);
+    }
   }
 
   // Add context-dependent keywords.
@@ -3017,7 +3043,7 @@ DeclarationName Sema::CorrectTypo(LookupResult &Res, Scope *S, CXXScopeSpec *SS,
   // Make sure that the user typed at least 3 characters for each correction 
   // made. Otherwise, we don't even both looking at the results.
   unsigned ED = Consumer.getBestEditDistance();
-  if (ED == 0 || (Typo->getName().size() / ED) < 3)
+  if (ED > 0 && Typo->getName().size() / ED < 3)
     return DeclarationName();
 
   // Weed out any names that could not be found by name lookup.
diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 2002ccd1c2..0f7486f82a 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -603,6 +603,10 @@ public:
   static const internal_key_type&
   GetInternalKey(const external_key_type& x) { return x; }
 
+  // This hopefully will just get inlined and removed by the optimizer.
+  static const external_key_type&
+  GetExternalKey(const internal_key_type& x) { return x; }
+
   static std::pair<unsigned, unsigned>
   ReadKeyDataLength(const unsigned char*& d) {
     using namespace clang::io;
@@ -3571,6 +3575,64 @@ IdentifierInfo* ASTReader::get(const char *NameStart, const char *NameEnd) {
   return 0;
 }
 
+namespace clang {
+  /// \brief An identifier-lookup iterator that enumerates all of the
+  /// identifiers stored within a set of AST files.
+  class ASTIdentifierIterator : public IdentifierIterator {
+    /// \brief The AST reader whose identifiers are being enumerated.
+    const ASTReader &Reader;
+
+    /// \brief The current index into the chain of AST files stored in
+    /// the AST reader.
+    unsigned Index;
+
+    /// \brief The current position within the identifier lookup table
+    /// of the current AST file.
+    ASTIdentifierLookupTable::key_iterator Current;
+
+    /// \brief The end position within the identifier lookup table of
+    /// the current AST file.
+    ASTIdentifierLookupTable::key_iterator End;
+
+  public:
+    explicit ASTIdentifierIterator(const ASTReader &Reader);
+
+    virtual llvm::StringRef Next();
+  };
+}
+
+ASTIdentifierIterator::ASTIdentifierIterator(const ASTReader &Reader)
+  : Reader(Reader), Index(Reader.Chain.size() - 1) {
+  ASTIdentifierLookupTable *IdTable
+    = (ASTIdentifierLookupTable *)Reader.Chain[Index]->IdentifierLookupTable;
+  Current = IdTable->key_begin();
+  End = IdTable->key_end();
+}
+
+llvm::StringRef ASTIdentifierIterator::Next() {
+  while (Current == End) {
+    // If we have exhausted all of our AST files, we're done.
+    if (Index == 0)
+      return llvm::StringRef();
+
+    --Index;
+    ASTIdentifierLookupTable *IdTable
+      = (ASTIdentifierLookupTable *)Reader.Chain[Index]->IdentifierLookupTable;
+    Current = IdTable->key_begin();
+    End = IdTable->key_end();
+  }
+
+  // We have any identifiers remaining in the current AST file; return
+  // the next one.
+  std::pair<const char*, unsigned> Key = *Current;
+  ++Current;
+  return llvm::StringRef(Key.first, Key.second);
+}
+
+IdentifierIterator *ASTReader::getIdentifiers() const {
+  return new ASTIdentifierIterator(*this);
+}
+
 std::pair<ObjCMethodList, ObjCMethodList>
 ASTReader::ReadMethodPool(Selector Sel) {
   // Find this selector in a hash table. We want to find the most recent entry.