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

1 files changed, 64 insertions, 0 deletions

diff --git a/include/clang/Basic/OnDiskHashTable.h b/include/clang/Basic/OnDiskHashTable.h
index 8909e47146..30bf39ef43 100644
--- a/include/clang/Basic/OnDiskHashTable.h
+++ b/include/clang/Basic/OnDiskHashTable.h
@@ -334,6 +334,70 @@ public:
 
   iterator end() const { return iterator(); }
 
+  /// \brief Iterates over all of the keys in the table.
+  class key_iterator {
+    const unsigned char* Ptr;
+    unsigned NumItemsInBucketLeft;
+    unsigned NumEntriesLeft;
+    Info *InfoObj;
+  public:
+    typedef external_key_type value_type;
+
+    key_iterator(const unsigned char* const Ptr, unsigned NumEntries,
+                  Info *InfoObj)
+      : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
+        InfoObj(InfoObj) { }
+    key_iterator()
+      : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) { }
+
+    friend bool operator==(const key_iterator &X, const key_iterator &Y) {
+      return X.NumEntriesLeft == Y.NumEntriesLeft;
+    }
+    friend bool operator!=(const key_iterator& X, const key_iterator &Y) {
+      return X.NumEntriesLeft != Y.NumEntriesLeft;
+    }
+    
+    key_iterator& operator++() {  // Preincrement
+      if (!NumItemsInBucketLeft) {
+        // 'Items' starts with a 16-bit unsigned integer representing the
+        // number of items in this bucket.
+        NumItemsInBucketLeft = io::ReadUnalignedLE16(Ptr);
+      }
+      Ptr += 4; // Skip the hash.
+      // Determine the length of the key and the data.
+      const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Ptr);
+      Ptr += L.first + L.second;
+      assert(NumItemsInBucketLeft);
+      --NumItemsInBucketLeft;
+      assert(NumEntriesLeft);
+      --NumEntriesLeft;
+      return *this;
+    }
+    key_iterator operator++(int) {  // Postincrement
+      key_iterator tmp = *this; ++*this; return tmp;
+    }
+
+    value_type operator*() const {
+      const unsigned char* LocalPtr = Ptr;
+      if (!NumItemsInBucketLeft)
+        LocalPtr += 2; // number of items in bucket
+      LocalPtr += 4; // Skip the hash.
+
+      // Determine the length of the key and the data.
+      const std::pair<unsigned, unsigned>& L
+        = Info::ReadKeyDataLength(LocalPtr);
+
+      // Read the key.
+      const internal_key_type& Key = InfoObj->ReadKey(LocalPtr, L.first);
+      return InfoObj->GetExternalKey(Key);
+    }
+  };
+
+  key_iterator key_begin() {
+    return key_iterator(Base + 4, getNumEntries(), &InfoObj);
+  }
+  key_iterator key_end() { return key_iterator(); }
+
   /// \brief Iterates over all the entries in the table, returning
   /// a key/data pair.
   class item_iterator {