contrib/llvm/tools/clang/include/clang/Basic/IdentifierTable.h

   1 //===--- IdentifierTable.h - Hash table for identifier lookup ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// \brief Defines the clang::IdentifierInfo, clang::IdentifierTable, and
  12 /// clang::Selector interfaces.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_BASIC_IDENTIFIERTABLE_H
  17 #define LLVM_CLANG_BASIC_IDENTIFIERTABLE_H
  18
  19 #include "clang/Basic/LLVM.h"
  20 #include "clang/Basic/TokenKinds.h"
  21 #include "llvm/ADT/SmallString.h"
  22 #include "llvm/ADT/StringMap.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/Support/Allocator.h"
  25 #include <cassert>
  26 #include <cstddef>
  27 #include <cstdint>
  28 #include <cstring>
  29 #include <new>
  30 #include <string>
  31 #include <utility>
  32
  33 namespace llvm {
  34
  35   template <typename T> struct DenseMapInfo;
  36
  37 } // end namespace llvm
  38
  39 namespace clang {
  40
  41   class LangOptions;
  42   class IdentifierInfo;
  43   class IdentifierTable;
  44   class SourceLocation;
  45   class MultiKeywordSelector; // private class used by Selector
  46   class DeclarationName;      // AST class that stores declaration names
  47
  48   /// \brief A simple pair of identifier info and location.
  49   typedef std::pair<IdentifierInfo*, SourceLocation> IdentifierLocPair;
  50
  51 /// One of these records is kept for each identifier that
  52 /// is lexed.  This contains information about whether the token was \#define'd,
  53 /// is a language keyword, or if it is a front-end token of some sort (e.g. a
  54 /// variable or function name).  The preprocessor keeps this information in a
  55 /// set, and all tok::identifier tokens have a pointer to one of these.
  56 class IdentifierInfo {
  57   friend class IdentifierTable;
  58
  59   unsigned TokenID            : 9; // Front-end token ID or tok::identifier.
  60   // Objective-C keyword ('protocol' in '@protocol') or builtin (__builtin_inf).
  61   // First NUM_OBJC_KEYWORDS values are for Objective-C, the remaining values
  62   // are for builtins.
  63   unsigned ObjCOrBuiltinID    :13;
  64   bool HasMacro               : 1; // True if there is a #define for this.
  65   bool HadMacro               : 1; // True if there was a #define for this.
  66   bool IsExtension            : 1; // True if identifier is a lang extension.
  67   bool IsFutureCompatKeyword  : 1; // True if identifier is a keyword in a
  68                                    // newer Standard or proposed Standard.
  69   bool IsPoisoned             : 1; // True if identifier is poisoned.
  70   bool IsCPPOperatorKeyword   : 1; // True if ident is a C++ operator keyword.
  71   bool NeedsHandleIdentifier  : 1; // See "RecomputeNeedsHandleIdentifier".
  72   bool IsFromAST              : 1; // True if identifier was loaded (at least
  73                                    // partially) from an AST file.
  74   bool ChangedAfterLoad       : 1; // True if identifier has changed from the
  75                                    // definition loaded from an AST file.
  76   bool FEChangedAfterLoad     : 1; // True if identifier's frontend information
  77                                    // has changed from the definition loaded
  78                                    // from an AST file.
  79   bool RevertedTokenID        : 1; // True if revertTokenIDToIdentifier was
  80                                    // called.
  81   bool OutOfDate              : 1; // True if there may be additional
  82                                    // information about this identifier
  83                                    // stored externally.
  84   bool IsModulesImport        : 1; // True if this is the 'import' contextual
  85                                    // keyword.
  86   // 29 bit left in 64-bit word.
  87
  88   void *FETokenInfo;               // Managed by the language front-end.
  89   llvm::StringMapEntry<IdentifierInfo*> *Entry;
  90
  91 public:
  92   IdentifierInfo();
  93   IdentifierInfo(const IdentifierInfo &) = delete;
  94   IdentifierInfo &operator=(const IdentifierInfo &) = delete;
  95
  96   /// \brief Return true if this is the identifier for the specified string.
  97   ///
  98   /// This is intended to be used for string literals only: II->isStr("foo").
  99   template <std::size_t StrLen>
 100   bool isStr(const char (&Str)[StrLen]) const {
 101     return getLength() == StrLen-1 &&
 102            memcmp(getNameStart(), Str, StrLen-1) == 0;
 103   }
 104
 105   /// \brief Return the beginning of the actual null-terminated string for this
 106   /// identifier.
 107   ///
 108   const char *getNameStart() const {
 109     if (Entry) return Entry->getKeyData();
 110     // FIXME: This is gross. It would be best not to embed specific details
 111     // of the PTH file format here.
 112     // The 'this' pointer really points to a
 113     // std::pair<IdentifierInfo, const char*>, where internal pointer
 114     // points to the external string data.
 115     typedef std::pair<IdentifierInfo, const char*> actualtype;
 116     return ((const actualtype*) this)->second;
 117   }
 118
 119   /// \brief Efficiently return the length of this identifier info.
 120   ///
 121   unsigned getLength() const {
 122     if (Entry) return Entry->getKeyLength();
 123     // FIXME: This is gross. It would be best not to embed specific details
 124     // of the PTH file format here.
 125     // The 'this' pointer really points to a
 126     // std::pair<IdentifierInfo, const char*>, where internal pointer
 127     // points to the external string data.
 128     typedef std::pair<IdentifierInfo, const char*> actualtype;
 129     const char* p = ((const actualtype*) this)->second - 2;
 130     return (((unsigned) p[0]) | (((unsigned) p[1]) << 8)) - 1;
 131   }
 132
 133   /// \brief Return the actual identifier string.
 134   StringRef getName() const {
 135     return StringRef(getNameStart(), getLength());
 136   }
 137
 138   /// \brief Return true if this identifier is \#defined to some other value.
 139   /// \note The current definition may be in a module and not currently visible.
 140   bool hasMacroDefinition() const {
 141     return HasMacro;
 142   }
 143   void setHasMacroDefinition(bool Val) {
 144     if (HasMacro == Val) return;
 145
 146     HasMacro = Val;
 147     if (Val) {
 148       NeedsHandleIdentifier = true;
 149       HadMacro = true;
 150     } else {
 151       RecomputeNeedsHandleIdentifier();
 152     }
 153   }
 154   /// \brief Returns true if this identifier was \#defined to some value at any
 155   /// moment. In this case there should be an entry for the identifier in the
 156   /// macro history table in Preprocessor.
 157   bool hadMacroDefinition() const {
 158     return HadMacro;
 159   }
 160
 161   /// If this is a source-language token (e.g. 'for'), this API
 162   /// can be used to cause the lexer to map identifiers to source-language
 163   /// tokens.
 164   tok::TokenKind getTokenID() const { return (tok::TokenKind)TokenID; }
 165
 166   /// \brief True if revertTokenIDToIdentifier() was called.
 167   bool hasRevertedTokenIDToIdentifier() const { return RevertedTokenID; }
 168
 169   /// \brief Revert TokenID to tok::identifier; used for GNU libstdc++ 4.2
 170   /// compatibility.
 171   ///
 172   /// TokenID is normally read-only but there are 2 instances where we revert it
 173   /// to tok::identifier for libstdc++ 4.2. Keep track of when this happens
 174   /// using this method so we can inform serialization about it.
 175   void revertTokenIDToIdentifier() {
 176     assert(TokenID != tok::identifier && "Already at tok::identifier");
 177     TokenID = tok::identifier;
 178     RevertedTokenID = true;
 179   }
 180   void revertIdentifierToTokenID(tok::TokenKind TK) {
 181     assert(TokenID == tok::identifier && "Should be at tok::identifier");
 182     TokenID = TK;
 183     RevertedTokenID = false;
 184   }
 185
 186   /// \brief Return the preprocessor keyword ID for this identifier.
 187   ///
 188   /// For example, "define" will return tok::pp_define.
 189   tok::PPKeywordKind getPPKeywordID() const;
 190
 191   /// \brief Return the Objective-C keyword ID for the this identifier.
 192   ///
 193   /// For example, 'class' will return tok::objc_class if ObjC is enabled.
 194   tok::ObjCKeywordKind getObjCKeywordID() const {
 195     if (ObjCOrBuiltinID < tok::NUM_OBJC_KEYWORDS)
 196       return tok::ObjCKeywordKind(ObjCOrBuiltinID);
 197     else
 198       return tok::objc_not_keyword;
 199   }
 200   void setObjCKeywordID(tok::ObjCKeywordKind ID) { ObjCOrBuiltinID = ID; }
 201
 202   /// \brief True if setNotBuiltin() was called.
 203   bool hasRevertedBuiltin() const {
 204     return ObjCOrBuiltinID == tok::NUM_OBJC_KEYWORDS;
 205   }
 206
 207   /// \brief Revert the identifier to a non-builtin identifier. We do this if
 208   /// the name of a known builtin library function is used to declare that
 209   /// function, but an unexpected type is specified.
 210   void revertBuiltin() {
 211     setBuiltinID(0);
 212   }
 213
 214   /// \brief Return a value indicating whether this is a builtin function.
 215   ///
 216   /// 0 is not-built-in. 1+ are specific builtin functions.
 217   unsigned getBuiltinID() const {
 218     if (ObjCOrBuiltinID >= tok::NUM_OBJC_KEYWORDS)
 219       return ObjCOrBuiltinID - tok::NUM_OBJC_KEYWORDS;
 220     else
 221       return 0;
 222   }
 223   void setBuiltinID(unsigned ID) {
 224     ObjCOrBuiltinID = ID + tok::NUM_OBJC_KEYWORDS;
 225     assert(ObjCOrBuiltinID - unsigned(tok::NUM_OBJC_KEYWORDS) == ID
 226            && "ID too large for field!");
 227   }
 228
 229   unsigned getObjCOrBuiltinID() const { return ObjCOrBuiltinID; }
 230   void setObjCOrBuiltinID(unsigned ID) { ObjCOrBuiltinID = ID; }
 231
 232   /// get/setExtension - Initialize information about whether or not this
 233   /// language token is an extension.  This controls extension warnings, and is
 234   /// only valid if a custom token ID is set.
 235   bool isExtensionToken() const { return IsExtension; }
 236   void setIsExtensionToken(bool Val) {
 237     IsExtension = Val;
 238     if (Val)
 239       NeedsHandleIdentifier = true;
 240     else
 241       RecomputeNeedsHandleIdentifier();
 242   }
 243
 244   /// is/setIsFutureCompatKeyword - Initialize information about whether or not
 245   /// this language token is a keyword in a newer or proposed Standard. This
 246   /// controls compatibility warnings, and is only true when not parsing the
 247   /// corresponding Standard. Once a compatibility problem has been diagnosed
 248   /// with this keyword, the flag will be cleared.
 249   bool isFutureCompatKeyword() const { return IsFutureCompatKeyword; }
 250   void setIsFutureCompatKeyword(bool Val) {
 251     IsFutureCompatKeyword = Val;
 252     if (Val)
 253       NeedsHandleIdentifier = true;
 254     else
 255       RecomputeNeedsHandleIdentifier();
 256   }
 257
 258   /// setIsPoisoned - Mark this identifier as poisoned.  After poisoning, the
 259   /// Preprocessor will emit an error every time this token is used.
 260   void setIsPoisoned(bool Value = true) {
 261     IsPoisoned = Value;
 262     if (Value)
 263       NeedsHandleIdentifier = true;
 264     else
 265       RecomputeNeedsHandleIdentifier();
 266   }
 267
 268   /// \brief Return true if this token has been poisoned.
 269   bool isPoisoned() const { return IsPoisoned; }
 270
 271   /// isCPlusPlusOperatorKeyword/setIsCPlusPlusOperatorKeyword controls whether
 272   /// this identifier is a C++ alternate representation of an operator.
 273   void setIsCPlusPlusOperatorKeyword(bool Val = true) {
 274     IsCPPOperatorKeyword = Val;
 275     if (Val)
 276       NeedsHandleIdentifier = true;
 277     else
 278       RecomputeNeedsHandleIdentifier();
 279   }
 280   bool isCPlusPlusOperatorKeyword() const { return IsCPPOperatorKeyword; }
 281
 282   /// \brief Return true if this token is a keyword in the specified language.
 283   bool isKeyword(const LangOptions &LangOpts) const;
 284
 285   /// \brief Return true if this token is a C++ keyword in the specified
 286   /// language.
 287   bool isCPlusPlusKeyword(const LangOptions &LangOpts) const;
 288
 289   /// getFETokenInfo/setFETokenInfo - The language front-end is allowed to
 290   /// associate arbitrary metadata with this token.
 291   template<typename T>
 292   T *getFETokenInfo() const { return static_cast<T*>(FETokenInfo); }
 293   void setFETokenInfo(void *T) { FETokenInfo = T; }
 294
 295   /// \brief Return true if the Preprocessor::HandleIdentifier must be called
 296   /// on a token of this identifier.
 297   ///
 298   /// If this returns false, we know that HandleIdentifier will not affect
 299   /// the token.
 300   bool isHandleIdentifierCase() const { return NeedsHandleIdentifier; }
 301
 302   /// \brief Return true if the identifier in its current state was loaded
 303   /// from an AST file.
 304   bool isFromAST() const { return IsFromAST; }
 305
 306   void setIsFromAST() { IsFromAST = true; }
 307
 308   /// \brief Determine whether this identifier has changed since it was loaded
 309   /// from an AST file.
 310   bool hasChangedSinceDeserialization() const {
 311     return ChangedAfterLoad;
 312   }
 313
 314   /// \brief Note that this identifier has changed since it was loaded from
 315   /// an AST file.
 316   void setChangedSinceDeserialization() {
 317     ChangedAfterLoad = true;
 318   }
 319
 320   /// \brief Determine whether the frontend token information for this
 321   /// identifier has changed since it was loaded from an AST file.
 322   bool hasFETokenInfoChangedSinceDeserialization() const {
 323     return FEChangedAfterLoad;
 324   }
 325
 326   /// \brief Note that the frontend token information for this identifier has
 327   /// changed since it was loaded from an AST file.
 328   void setFETokenInfoChangedSinceDeserialization() {
 329     FEChangedAfterLoad = true;
 330   }
 331
 332   /// \brief Determine whether the information for this identifier is out of
 333   /// date with respect to the external source.
 334   bool isOutOfDate() const { return OutOfDate; }
 335
 336   /// \brief Set whether the information for this identifier is out of
 337   /// date with respect to the external source.
 338   void setOutOfDate(bool OOD) {
 339     OutOfDate = OOD;
 340     if (OOD)
 341       NeedsHandleIdentifier = true;
 342     else
 343       RecomputeNeedsHandleIdentifier();
 344   }
 345
 346   /// \brief Determine whether this is the contextual keyword \c import.
 347   bool isModulesImport() const { return IsModulesImport; }
 348
 349   /// \brief Set whether this identifier is the contextual keyword \c import.
 350   void setModulesImport(bool I) {
 351     IsModulesImport = I;
 352     if (I)
 353       NeedsHandleIdentifier = true;
 354     else
 355       RecomputeNeedsHandleIdentifier();
 356   }
 357
 358   /// Return true if this identifier is an editor placeholder.
 359   ///
 360   /// Editor placeholders are produced by the code-completion engine and are
 361   /// represented as characters between '<#' and '#>' in the source code. An
 362   /// example of auto-completed call with a placeholder parameter is shown
 363   /// below:
 364   /// \code
 365   ///   function(<#int x#>);
 366   /// \endcode
 367   bool isEditorPlaceholder() const {
 368     return getName().startswith("<#") && getName().endswith("#>");
 369   }
 370
 371   /// \brief Provide less than operator for lexicographical sorting.
 372   bool operator<(const IdentifierInfo &RHS) const {
 373     return getName() < RHS.getName();
 374   }
 375
 376 private:
 377   /// The Preprocessor::HandleIdentifier does several special (but rare)
 378   /// things to identifiers of various sorts.  For example, it changes the
 379   /// \c for keyword token from tok::identifier to tok::for.
 380   ///
 381   /// This method is very tied to the definition of HandleIdentifier.  Any
 382   /// change to it should be reflected here.
 383   void RecomputeNeedsHandleIdentifier() {
 384     NeedsHandleIdentifier =
 385       (isPoisoned() | hasMacroDefinition() | isCPlusPlusOperatorKeyword() |
 386        isExtensionToken() | isFutureCompatKeyword() || isOutOfDate() ||
 387        isModulesImport());
 388   }
 389 };
 390
 391 /// \brief An RAII object for [un]poisoning an identifier within a scope.
 392 ///
 393 /// \p II is allowed to be null, in which case objects of this type have
 394 /// no effect.
 395 class PoisonIdentifierRAIIObject {
 396   IdentifierInfo *const II;
 397   const bool OldValue;
 398
 399 public:
 400   PoisonIdentifierRAIIObject(IdentifierInfo *II, bool NewValue)
 401     : II(II), OldValue(II ? II->isPoisoned() : false) {
 402     if(II)
 403       II->setIsPoisoned(NewValue);
 404   }
 405
 406   ~PoisonIdentifierRAIIObject() {
 407     if(II)
 408       II->setIsPoisoned(OldValue);
 409   }
 410 };
 411
 412 /// \brief An iterator that walks over all of the known identifiers
 413 /// in the lookup table.
 414 ///
 415 /// Since this iterator uses an abstract interface via virtual
 416 /// functions, it uses an object-oriented interface rather than the
 417 /// more standard C++ STL iterator interface. In this OO-style
 418 /// iteration, the single function \c Next() provides dereference,
 419 /// advance, and end-of-sequence checking in a single
 420 /// operation. Subclasses of this iterator type will provide the
 421 /// actual functionality.
 422 class IdentifierIterator {
 423 protected:
 424   IdentifierIterator() = default;
 425
 426 public:
 427   IdentifierIterator(const IdentifierIterator &) = delete;
 428   IdentifierIterator &operator=(const IdentifierIterator &) = delete;
 429
 430   virtual ~IdentifierIterator();
 431
 432   /// \brief Retrieve the next string in the identifier table and
 433   /// advances the iterator for the following string.
 434   ///
 435   /// \returns The next string in the identifier table. If there is
 436   /// no such string, returns an empty \c StringRef.
 437   virtual StringRef Next() = 0;
 438 };
 439
 440 /// \brief Provides lookups to, and iteration over, IdentiferInfo objects.
 441 class IdentifierInfoLookup {
 442 public:
 443   virtual ~IdentifierInfoLookup();
 444
 445   /// \brief Return the IdentifierInfo for the specified named identifier.
 446   ///
 447   /// Unlike the version in IdentifierTable, this returns a pointer instead
 448   /// of a reference.  If the pointer is null then the IdentifierInfo cannot
 449   /// be found.
 450   virtual IdentifierInfo* get(StringRef Name) = 0;
 451
 452   /// \brief Retrieve an iterator into the set of all identifiers
 453   /// known to this identifier lookup source.
 454   ///
 455   /// This routine provides access to all of the identifiers known to
 456   /// the identifier lookup, allowing access to the contents of the
 457   /// identifiers without introducing the overhead of constructing
 458   /// IdentifierInfo objects for each.
 459   ///
 460   /// \returns A new iterator into the set of known identifiers. The
 461   /// caller is responsible for deleting this iterator.
 462   virtual IdentifierIterator *getIdentifiers();
 463 };
 464
 465 /// \brief Implements an efficient mapping from strings to IdentifierInfo nodes.
 466 ///
 467 /// This has no other purpose, but this is an extremely performance-critical
 468 /// piece of the code, as each occurrence of every identifier goes through
 469 /// here when lexed.
 470 class IdentifierTable {
 471   // Shark shows that using MallocAllocator is *much* slower than using this
 472   // BumpPtrAllocator!
 473   typedef llvm::StringMap<IdentifierInfo*, llvm::BumpPtrAllocator> HashTableTy;
 474   HashTableTy HashTable;
 475
 476   IdentifierInfoLookup* ExternalLookup;
 477
 478 public:
 479   /// \brief Create the identifier table, populating it with info about the
 480   /// language keywords for the language specified by \p LangOpts.
 481   IdentifierTable(const LangOptions &LangOpts,
 482                   IdentifierInfoLookup* externalLookup = nullptr);
 483
 484   /// \brief Set the external identifier lookup mechanism.
 485   void setExternalIdentifierLookup(IdentifierInfoLookup *IILookup) {
 486     ExternalLookup = IILookup;
 487   }
 488
 489   /// \brief Retrieve the external identifier lookup object, if any.
 490   IdentifierInfoLookup *getExternalIdentifierLookup() const {
 491     return ExternalLookup;
 492   }
 493
 494   llvm::BumpPtrAllocator& getAllocator() {
 495     return HashTable.getAllocator();
 496   }
 497
 498   /// \brief Return the identifier token info for the specified named
 499   /// identifier.
 500   IdentifierInfo &get(StringRef Name) {
 501     auto &Entry = *HashTable.insert(std::make_pair(Name, nullptr)).first;
 502
 503     IdentifierInfo *&II = Entry.second;
 504     if (II) return *II;
 505
 506     // No entry; if we have an external lookup, look there first.
 507     if (ExternalLookup) {
 508       II = ExternalLookup->get(Name);
 509       if (II)
 510         return *II;
 511     }
 512
 513     // Lookups failed, make a new IdentifierInfo.
 514     void *Mem = getAllocator().Allocate<IdentifierInfo>();
 515     II = new (Mem) IdentifierInfo();
 516
 517     // Make sure getName() knows how to find the IdentifierInfo
 518     // contents.
 519     II->Entry = &Entry;
 520
 521     return *II;
 522   }
 523
 524   IdentifierInfo &get(StringRef Name, tok::TokenKind TokenCode) {
 525     IdentifierInfo &II = get(Name);
 526     II.TokenID = TokenCode;
 527     assert(II.TokenID == (unsigned) TokenCode && "TokenCode too large");
 528     return II;
 529   }
 530
 531   /// \brief Gets an IdentifierInfo for the given name without consulting
 532   ///        external sources.
 533   ///
 534   /// This is a version of get() meant for external sources that want to
 535   /// introduce or modify an identifier. If they called get(), they would
 536   /// likely end up in a recursion.
 537   IdentifierInfo &getOwn(StringRef Name) {
 538     auto &Entry = *HashTable.insert(std::make_pair(Name, nullptr)).first;
 539
 540     IdentifierInfo *&II = Entry.second;
 541     if (II)
 542       return *II;
 543
 544     // Lookups failed, make a new IdentifierInfo.
 545     void *Mem = getAllocator().Allocate<IdentifierInfo>();
 546     II = new (Mem) IdentifierInfo();
 547
 548     // Make sure getName() knows how to find the IdentifierInfo
 549     // contents.
 550     II->Entry = &Entry;
 551
 552     // If this is the 'import' contextual keyword, mark it as such.
 553     if (Name.equals("import"))
 554       II->setModulesImport(true);
 555
 556     return *II;
 557   }
 558
 559   typedef HashTableTy::const_iterator iterator;
 560   typedef HashTableTy::const_iterator const_iterator;
 561
 562   iterator begin() const { return HashTable.begin(); }
 563   iterator end() const   { return HashTable.end(); }
 564   unsigned size() const  { return HashTable.size(); }
 565
 566   /// \brief Print some statistics to stderr that indicate how well the
 567   /// hashing is doing.
 568   void PrintStats() const;
 569
 570   void AddKeywords(const LangOptions &LangOpts);
 571 };
 572
 573 /// \brief A family of Objective-C methods.
 574 ///
 575 /// These families have no inherent meaning in the language, but are
 576 /// nonetheless central enough in the existing implementations to
 577 /// merit direct AST support.  While, in theory, arbitrary methods can
 578 /// be considered to form families, we focus here on the methods
 579 /// involving allocation and retain-count management, as these are the
 580 /// most "core" and the most likely to be useful to diverse clients
 581 /// without extra information.
 582 ///
 583 /// Both selectors and actual method declarations may be classified
 584 /// into families.  Method families may impose additional restrictions
 585 /// beyond their selector name; for example, a method called '_init'
 586 /// that returns void is not considered to be in the 'init' family
 587 /// (but would be if it returned 'id').  It is also possible to
 588 /// explicitly change or remove a method's family.  Therefore the
 589 /// method's family should be considered the single source of truth.
 590 enum ObjCMethodFamily {
 591   /// \brief No particular method family.
 592   OMF_None,
 593
 594   // Selectors in these families may have arbitrary arity, may be
 595   // written with arbitrary leading underscores, and may have
 596   // additional CamelCase "words" in their first selector chunk
 597   // following the family name.
 598   OMF_alloc,
 599   OMF_copy,
 600   OMF_init,
 601   OMF_mutableCopy,
 602   OMF_new,
 603
 604   // These families are singletons consisting only of the nullary
 605   // selector with the given name.
 606   OMF_autorelease,
 607   OMF_dealloc,
 608   OMF_finalize,
 609   OMF_release,
 610   OMF_retain,
 611   OMF_retainCount,
 612   OMF_self,
 613   OMF_initialize,
 614
 615   // performSelector families
 616   OMF_performSelector
 617 };
 618
 619 /// Enough bits to store any enumerator in ObjCMethodFamily or
 620 /// InvalidObjCMethodFamily.
 621 enum { ObjCMethodFamilyBitWidth = 4 };
 622
 623 /// \brief An invalid value of ObjCMethodFamily.
 624 enum { InvalidObjCMethodFamily = (1 << ObjCMethodFamilyBitWidth) - 1 };
 625
 626 /// \brief A family of Objective-C methods.
 627 ///
 628 /// These are family of methods whose result type is initially 'id', but
 629 /// but are candidate for the result type to be changed to 'instancetype'.
 630 enum ObjCInstanceTypeFamily {
 631   OIT_None,
 632   OIT_Array,
 633   OIT_Dictionary,
 634   OIT_Singleton,
 635   OIT_Init,
 636   OIT_ReturnsSelf
 637 };
 638
 639 enum ObjCStringFormatFamily {
 640   SFF_None,
 641   SFF_NSString,
 642   SFF_CFString
 643 };
 644
 645 /// \brief Smart pointer class that efficiently represents Objective-C method
 646 /// names.
 647 ///
 648 /// This class will either point to an IdentifierInfo or a
 649 /// MultiKeywordSelector (which is private). This enables us to optimize
 650 /// selectors that take no arguments and selectors that take 1 argument, which
 651 /// accounts for 78% of all selectors in Cocoa.h.
 652 class Selector {
 653   friend class Diagnostic;
 654
 655   enum IdentifierInfoFlag {
 656     // Empty selector = 0.
 657     ZeroArg  = 0x1,
 658     OneArg   = 0x2,
 659     MultiArg = 0x3,
 660     ArgFlags = ZeroArg|OneArg
 661   };
 662   uintptr_t InfoPtr; // a pointer to the MultiKeywordSelector or IdentifierInfo.
 663
 664   Selector(IdentifierInfo *II, unsigned nArgs) {
 665     InfoPtr = reinterpret_cast<uintptr_t>(II);
 666     assert((InfoPtr & ArgFlags) == 0 &&"Insufficiently aligned IdentifierInfo");
 667     assert(nArgs < 2 && "nArgs not equal to 0/1");
 668     InfoPtr |= nArgs+1;
 669   }
 670   Selector(MultiKeywordSelector *SI) {
 671     InfoPtr = reinterpret_cast<uintptr_t>(SI);
 672     assert((InfoPtr & ArgFlags) == 0 &&"Insufficiently aligned IdentifierInfo");
 673     InfoPtr |= MultiArg;
 674   }
 675
 676   IdentifierInfo *getAsIdentifierInfo() const {
 677     if (getIdentifierInfoFlag() < MultiArg)
 678       return reinterpret_cast<IdentifierInfo *>(InfoPtr & ~ArgFlags);
 679     return nullptr;
 680   }
 681
 682   MultiKeywordSelector *getMultiKeywordSelector() const {
 683     return reinterpret_cast<MultiKeywordSelector *>(InfoPtr & ~ArgFlags);
 684   }
 685
 686   unsigned getIdentifierInfoFlag() const {
 687     return InfoPtr & ArgFlags;
 688   }
 689
 690   static ObjCMethodFamily getMethodFamilyImpl(Selector sel);
 691
 692   static ObjCStringFormatFamily getStringFormatFamilyImpl(Selector sel);
 693
 694 public:
 695   friend class SelectorTable; // only the SelectorTable can create these
 696   friend class DeclarationName; // and the AST's DeclarationName.
 697
 698   /// The default ctor should only be used when creating data structures that
 699   ///  will contain selectors.
 700   Selector() : InfoPtr(0) {}
 701   Selector(uintptr_t V) : InfoPtr(V) {}
 702
 703   /// operator==/!= - Indicate whether the specified selectors are identical.
 704   bool operator==(Selector RHS) const {
 705     return InfoPtr == RHS.InfoPtr;
 706   }
 707   bool operator!=(Selector RHS) const {
 708     return InfoPtr != RHS.InfoPtr;
 709   }
 710
 711   void *getAsOpaquePtr() const {
 712     return reinterpret_cast<void*>(InfoPtr);
 713   }
 714
 715   /// \brief Determine whether this is the empty selector.
 716   bool isNull() const { return InfoPtr == 0; }
 717
 718   // Predicates to identify the selector type.
 719   bool isKeywordSelector() const {
 720     return getIdentifierInfoFlag() != ZeroArg;
 721   }
 722
 723   bool isUnarySelector() const {
 724     return getIdentifierInfoFlag() == ZeroArg;
 725   }
 726
 727   unsigned getNumArgs() const;
 728
 729   /// \brief Retrieve the identifier at a given position in the selector.
 730   ///
 731   /// Note that the identifier pointer returned may be NULL. Clients that only
 732   /// care about the text of the identifier string, and not the specific,
 733   /// uniqued identifier pointer, should use \c getNameForSlot(), which returns
 734   /// an empty string when the identifier pointer would be NULL.
 735   ///
 736   /// \param argIndex The index for which we want to retrieve the identifier.
 737   /// This index shall be less than \c getNumArgs() unless this is a keyword
 738   /// selector, in which case 0 is the only permissible value.
 739   ///
 740   /// \returns the uniqued identifier for this slot, or NULL if this slot has
 741   /// no corresponding identifier.
 742   IdentifierInfo *getIdentifierInfoForSlot(unsigned argIndex) const;
 743
 744   /// \brief Retrieve the name at a given position in the selector.
 745   ///
 746   /// \param argIndex The index for which we want to retrieve the name.
 747   /// This index shall be less than \c getNumArgs() unless this is a keyword
 748   /// selector, in which case 0 is the only permissible value.
 749   ///
 750   /// \returns the name for this slot, which may be the empty string if no
 751   /// name was supplied.
 752   StringRef getNameForSlot(unsigned argIndex) const;
 753
 754   /// \brief Derive the full selector name (e.g. "foo:bar:") and return
 755   /// it as an std::string.
 756   std::string getAsString() const;
 757
 758   /// \brief Prints the full selector name (e.g. "foo:bar:").
 759   void print(llvm::raw_ostream &OS) const;
 760
 761   /// \brief Derive the conventional family of this method.
 762   ObjCMethodFamily getMethodFamily() const {
 763     return getMethodFamilyImpl(*this);
 764   }
 765
 766   ObjCStringFormatFamily getStringFormatFamily() const {
 767     return getStringFormatFamilyImpl(*this);
 768   }
 769
 770   static Selector getEmptyMarker() {
 771     return Selector(uintptr_t(-1));
 772   }
 773
 774   static Selector getTombstoneMarker() {
 775     return Selector(uintptr_t(-2));
 776   }
 777
 778   static ObjCInstanceTypeFamily getInstTypeMethodFamily(Selector sel);
 779 };
 780
 781 /// \brief This table allows us to fully hide how we implement
 782 /// multi-keyword caching.
 783 class SelectorTable {
 784   void *Impl;  // Actually a SelectorTableImpl
 785
 786 public:
 787   SelectorTable();
 788   SelectorTable(const SelectorTable &) = delete;
 789   SelectorTable &operator=(const SelectorTable &) = delete;
 790   ~SelectorTable();
 791
 792   /// \brief Can create any sort of selector.
 793   ///
 794   /// \p NumArgs indicates whether this is a no argument selector "foo", a
 795   /// single argument selector "foo:" or multi-argument "foo:bar:".
 796   Selector getSelector(unsigned NumArgs, IdentifierInfo **IIV);
 797
 798   Selector getUnarySelector(IdentifierInfo *ID) {
 799     return Selector(ID, 1);
 800   }
 801   Selector getNullarySelector(IdentifierInfo *ID) {
 802     return Selector(ID, 0);
 803   }
 804
 805   /// \brief Return the total amount of memory allocated for managing selectors.
 806   size_t getTotalMemory() const;
 807
 808   /// \brief Return the default setter name for the given identifier.
 809   ///
 810   /// This is "set" + \p Name where the initial character of \p Name
 811   /// has been capitalized.
 812   static SmallString<64> constructSetterName(StringRef Name);
 813
 814   /// \brief Return the default setter selector for the given identifier.
 815   ///
 816   /// This is "set" + \p Name where the initial character of \p Name
 817   /// has been capitalized.
 818   static Selector constructSetterSelector(IdentifierTable &Idents,
 819                                           SelectorTable &SelTable,
 820                                           const IdentifierInfo *Name);
 821 };
 822
 823 /// DeclarationNameExtra - Common base of the MultiKeywordSelector,
 824 /// CXXSpecialName, and CXXOperatorIdName classes, all of which are
 825 /// private classes that describe different kinds of names.
 826 class DeclarationNameExtra {
 827 public:
 828   /// ExtraKind - The kind of "extra" information stored in the
 829   /// DeclarationName. See @c ExtraKindOrNumArgs for an explanation of
 830   /// how these enumerator values are used.
 831   enum ExtraKind {
 832     CXXConstructor = 0,
 833     CXXDestructor,
 834     CXXConversionFunction,
 835 #define OVERLOADED_OPERATOR(Name,Spelling,Token,Unary,Binary,MemberOnly) \
 836     CXXOperator##Name,
 837 #include "clang/Basic/OperatorKinds.def"
 838     CXXDeductionGuide,
 839     CXXLiteralOperator,
 840     CXXUsingDirective,
 841     NUM_EXTRA_KINDS
 842   };
 843
 844   /// ExtraKindOrNumArgs - Either the kind of C++ special name or
 845   /// operator-id (if the value is one of the CXX* enumerators of
 846   /// ExtraKind), in which case the DeclarationNameExtra is also a
 847   /// CXXSpecialName, (for CXXConstructor, CXXDestructor, or
 848   /// CXXConversionFunction) CXXOperatorIdName, or CXXLiteralOperatorName,
 849   /// it may be also name common to C++ using-directives (CXXUsingDirective),
 850   /// otherwise it is NUM_EXTRA_KINDS+NumArgs, where NumArgs is the number of
 851   /// arguments in the Objective-C selector, in which case the
 852   /// DeclarationNameExtra is also a MultiKeywordSelector.
 853   unsigned ExtraKindOrNumArgs;
 854 };
 855
 856 }  // end namespace clang
 857
 858 namespace llvm {
 859
 860 /// Define DenseMapInfo so that Selectors can be used as keys in DenseMap and
 861 /// DenseSets.
 862 template <>
 863 struct DenseMapInfo<clang::Selector> {
 864   static inline clang::Selector getEmptyKey() {
 865     return clang::Selector::getEmptyMarker();
 866   }
 867
 868   static inline clang::Selector getTombstoneKey() {
 869     return clang::Selector::getTombstoneMarker();
 870   }
 871
 872   static unsigned getHashValue(clang::Selector S);
 873
 874   static bool isEqual(clang::Selector LHS, clang::Selector RHS) {
 875     return LHS == RHS;
 876   }
 877 };
 878
 879 template <>
 880 struct isPodLike<clang::Selector> { static const bool value = true; };
 881
 882 template <typename T> class PointerLikeTypeTraits;
 883
 884 template<>
 885 class PointerLikeTypeTraits<clang::Selector> {
 886 public:
 887   static inline const void *getAsVoidPointer(clang::Selector P) {
 888     return P.getAsOpaquePtr();
 889   }
 890
 891   static inline clang::Selector getFromVoidPointer(const void *P) {
 892     return clang::Selector(reinterpret_cast<uintptr_t>(P));
 893   }
 894
 895   enum { NumLowBitsAvailable = 0 };
 896 };
 897
 898 // Provide PointerLikeTypeTraits for IdentifierInfo pointers, which
 899 // are not guaranteed to be 8-byte aligned.
 900 template<>
 901 class PointerLikeTypeTraits<clang::IdentifierInfo*> {
 902 public:
 903   static inline void *getAsVoidPointer(clang::IdentifierInfo* P) {
 904     return P;
 905   }
 906
 907   static inline clang::IdentifierInfo *getFromVoidPointer(void *P) {
 908     return static_cast<clang::IdentifierInfo*>(P);
 909   }
 910
 911   enum { NumLowBitsAvailable = 1 };
 912 };
 913
 914 template<>
 915 class PointerLikeTypeTraits<const clang::IdentifierInfo*> {
 916 public:
 917   static inline const void *getAsVoidPointer(const clang::IdentifierInfo* P) {
 918     return P;
 919   }
 920
 921   static inline const clang::IdentifierInfo *getFromVoidPointer(const void *P) {
 922     return static_cast<const clang::IdentifierInfo*>(P);
 923   }
 924
 925   enum { NumLowBitsAvailable = 1 };
 926 };
 927
 928 } // end namespace llvm
 929
 930 #endif // LLVM_CLANG_BASIC_IDENTIFIERTABLE_H