[clang-format] Partially revert r322749, replacing array with DenseSet

[krasimir]

Summary

The array + binary_search requires the initializer list of identifiers to be
sorted. I can imagine how this list might change frequently while the support
for ObjectiveC improves (D44632). The array approach might have been a premature
optimization too, since in any case computing a hash for every token is trivial
compared to what we do for formatting it.

[bkramer]

I wouldn't say that this is more maintainable, but I'm not the maintainer of clang-format.

[benhamilton]

I'm fine with whichever approach we use, but I'll defer to @djasper here.

(I'm not fully sure why llvm::DenseSet is better than std::unsorted_set, but I'm sure @djasper and @krasimir understand the subtleties better than I do.)

[krasimir]

One way in which DenseSet is better is that it supports StringRefs - we don't have to define hash. Seems like the lack of this override in core LLVM suggests that unordered_set is not commonly used with StringRefs.

[benhamilton]

One way in which DenseSet is better is that it supports StringRefs - we don't have to define hash. Seems like the lack of this override in core LLVM suggests that unordered_set is not commonly used with StringRefs.

Makes sense, thanks.

lib/Format/Format.cpp

 #include "UnwrappedLineParser.h"
 #include "UsingDeclarationsSorter.h"
 #include "WhitespaceManager.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/VirtualFileSystem.h"
 #include "clang/Lex/Lexer.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #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>
analyze(TokenAnnotator &Annotator,
     return {Result, 0};
   }
 
   bool isObjC() { return IsObjC; }
 
 private:
   static bool guessIsObjC(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
                           const AdditionalKeywords &Keywords) {
-    // Keep this array sorted, since we are binary searching over it.
-    static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
+    static const auto *FoundationIdentifiers = new llvm::DenseSet<StringRef>{
         "CGFloat",
         "NSAffineTransform",
         "NSArray",
         "NSAttributedString",
         "NSBundle",
         "NSCache",
         "NSCalendar",
         "NSCharacterSet",
for (auto &Line : AnnotatedLines) {
         if ((FormatTok->Previous && 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() &&
-             std::binary_search(std::begin(FoundationIdentifiers),
-                                std::end(FoundationIdentifiers),
-                                FormatTok->TokenText)) ||
+             FoundationIdentifiers->find(FormatTok->TokenText) !=
+                 FoundationIdentifiers->end()) ||
             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;
         }
       }