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