[clang-format] Replace unordered_set with an array

[krasimir]

Summary

This replaces an unordered_set from r322690 with an array and binary search.

[bkramer]

lib/Format/Format.cpp

1424–1425

The ArrayRef doesn't own its contents, so this is a use-after-scope.

I'd prefer static constexpr llvm::StringLiteral FoundationIdentifiers[] = {

[krasimir]

• Address review comment

[benhamilton]

Thanks, this is smarter.

[benhamilton]

lib/Format/Format.cpp

1424–1425

Should we add a comment that this array must be sorted if someone adds a new entry?

[krasimir]

• Add comment

[bkramer]

lgtm

lib/Format/Format.cpp

 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/YAMLTraits.h"
 #include <algorithm>
 #include <memory>
 #include <string>
-#include <unordered_set>
 
 #define DEBUG_TYPE "format-formatter"
 
 using clang::format::FormatStyle;
 
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::IncludeCategory)
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::RawStringFormat)
 
-namespace std {
-// Allow using StringRef in std::unordered_set.
-template <> struct hash<llvm::StringRef> {
-public:
-  size_t operator()(const llvm::StringRef &s) const {
-    return llvm::hash_value(s);
-  }
-};
-} // namespace std
-
 namespace llvm {
 namespace yaml {
 template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
   static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
     IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
     IO.enumCase(Value, "Java", FormatStyle::LK_Java);
     IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
     IO.enumCase(Value, "ObjC", FormatStyle::LK_ObjC);
analyze(TokenAnnotator &Annotator,
     return {Result, 0};
   }
 
   bool isObjC() { return IsObjC; }
 
 private:
   static bool guessIsObjC(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
                           const AdditionalKeywords &Keywords) {
-    static const std::unordered_set<StringRef> FoundationIdentifiers = {
+    // Keep this array sorted, since we are binary searching over it.
+    static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
         "CGFloat",
         "NSAffineTransform",
         "NSArray",
         "NSAttributedString",
         "NSCache",
         "NSCharacterSet",
         "NSCountedSet",
         "NSData",
for (auto &Line : AnnotatedLines) {
         if ((FormatTok->Previous->is(tok::at) &&
              (FormatTok->isObjCAtKeyword(tok::objc_interface) ||
               FormatTok->isObjCAtKeyword(tok::objc_implementation) ||
               FormatTok->isObjCAtKeyword(tok::objc_protocol) ||
               FormatTok->isObjCAtKeyword(tok::objc_end) ||
               FormatTok->isOneOf(tok::numeric_constant, tok::l_square,
                                  tok::l_brace))) ||
             (FormatTok->Tok.isAnyIdentifier() &&
-             FoundationIdentifiers.find(FormatTok->TokenText) !=
-                 FoundationIdentifiers.end()) ||
+             std::binary_search(std::begin(FoundationIdentifiers),
+                                std::end(FoundationIdentifiers),
+                                FormatTok->TokenText)) ||
             FormatTok->is(TT_ObjCStringLiteral) ||
             FormatTok->isOneOf(Keywords.kw_NS_ENUM, Keywords.kw_NS_OPTIONS,
                                TT_ObjCBlockLBrace, TT_ObjCBlockLParen,
                                TT_ObjCDecl, TT_ObjCForIn, TT_ObjCMethodExpr,
                                TT_ObjCMethodSpecifier, TT_ObjCProperty)) {
           return true;
         }
       }