Preprocessor.h

//===--- Preprocessor.h - C Language Family Preprocessor --------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief Defines the clang::Preprocessor interface.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_LEX_PREPROCESSOR_H
#define LLVM_CLANG_LEX_PREPROCESSOR_H

#include "clang/Basic/Builtins.h"
#include "clang/Basic/Diagnostic.h"
#include "clang/Basic/IdentifierTable.h"
#include "clang/Basic/SourceLocation.h"
#include "clang/Lex/Lexer.h"
#include "clang/Lex/MacroInfo.h"
#include "clang/Lex/ModuleMap.h"
#include "clang/Lex/PPCallbacks.h"
#include "clang/Lex/PTHLexer.h"
#include "clang/Lex/TokenLexer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IntrusiveRefCntPtr.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Registry.h"
#include <memory>
#include <vector>

namespace llvm {
  template<unsigned InternalLen> class SmallString;
}

namespace clang {

class SourceManager;
class ExternalPreprocessorSource;
class FileManager;
class FileEntry;
class HeaderSearch;
class PragmaNamespace;
class PragmaHandler;
class CommentHandler;
class ScratchBuffer;
class TargetInfo;
class PPCallbacks;
class CodeCompletionHandler;
class DirectoryLookup;
class PreprocessingRecord;
class ModuleLoader;
class PTHManager;
class PreprocessorOptions;

/// \brief Stores token information for comparing actual tokens with
/// predefined values.  Only handles simple tokens and identifiers.
class TokenValue {
  tok::TokenKind Kind;
  IdentifierInfo *II;

public:
  TokenValue(tok::TokenKind Kind) : Kind(Kind), II(nullptr) {
    assert(Kind != tok::raw_identifier && "Raw identifiers are not supported.");
    assert(Kind != tok::identifier &&
           "Identifiers should be created by TokenValue(IdentifierInfo *)");
    assert(!tok::isLiteral(Kind) && "Literals are not supported.");
    assert(!tok::isAnnotation(Kind) && "Annotations are not supported.");
  }
  TokenValue(IdentifierInfo *II) : Kind(tok::identifier), II(II) {}
  bool operator==(const Token &Tok) const {
    return Tok.getKind() == Kind &&
        (!II || II == Tok.getIdentifierInfo());
  }
};

/// \brief Context in which macro name is used.
enum MacroUse {
  MU_Other  = 0,  // other than #define or #undef
  MU_Define = 1,  // macro name specified in #define
  MU_Undef  = 2   // macro name specified in #undef
};

/// \brief Engages in a tight little dance with the lexer to efficiently
/// preprocess tokens.
///
/// Lexers know only about tokens within a single source file, and don't
/// know anything about preprocessor-level issues like the \#include stack,
/// token expansion, etc.
class Preprocessor : public RefCountedBase<Preprocessor> {
  IntrusiveRefCntPtr<PreprocessorOptions> PPOpts;
  DiagnosticsEngine        *Diags;
  LangOptions       &LangOpts;
  const TargetInfo  *Target;
  const TargetInfo  *AuxTarget;
  FileManager       &FileMgr;
  SourceManager     &SourceMgr;
  std::unique_ptr<ScratchBuffer> ScratchBuf;
  HeaderSearch      &HeaderInfo;
  ModuleLoader      &TheModuleLoader;

  /// \brief External source of macros.
  ExternalPreprocessorSource *ExternalSource;


  /// An optional PTHManager object used for getting tokens from
  /// a token cache rather than lexing the original source file.
  std::unique_ptr<PTHManager> PTH;

  /// A BumpPtrAllocator object used to quickly allocate and release
  /// objects internal to the Preprocessor.
  llvm::BumpPtrAllocator BP;

  /// Identifiers for builtin macros and other builtins.
  IdentifierInfo *Ident__LINE__, *Ident__FILE__;   // __LINE__, __FILE__
  IdentifierInfo *Ident__DATE__, *Ident__TIME__;   // __DATE__, __TIME__
  IdentifierInfo *Ident__INCLUDE_LEVEL__;          // __INCLUDE_LEVEL__
  IdentifierInfo *Ident__BASE_FILE__;              // __BASE_FILE__
  IdentifierInfo *Ident__TIMESTAMP__;              // __TIMESTAMP__
  IdentifierInfo *Ident__COUNTER__;                // __COUNTER__
  IdentifierInfo *Ident_Pragma, *Ident__pragma;    // _Pragma, __pragma
  IdentifierInfo *Ident__identifier;               // __identifier
  IdentifierInfo *Ident__VA_ARGS__;                // __VA_ARGS__
  IdentifierInfo *Ident__has_feature;              // __has_feature
  IdentifierInfo *Ident__has_extension;            // __has_extension
  IdentifierInfo *Ident__has_builtin;              // __has_builtin
  IdentifierInfo *Ident__has_attribute;            // __has_attribute
  IdentifierInfo *Ident__has_include;              // __has_include
  IdentifierInfo *Ident__has_include_next;         // __has_include_next
  IdentifierInfo *Ident__has_warning;              // __has_warning
  IdentifierInfo *Ident__is_identifier;            // __is_identifier
  IdentifierInfo *Ident__building_module;          // __building_module
  IdentifierInfo *Ident__MODULE__;                 // __MODULE__
  IdentifierInfo *Ident__has_cpp_attribute;        // __has_cpp_attribute
  IdentifierInfo *Ident__has_declspec;             // __has_declspec_attribute

  SourceLocation DATELoc, TIMELoc;
  unsigned CounterValue;  // Next __COUNTER__ value.

  enum {
    /// \brief Maximum depth of \#includes.
    MaxAllowedIncludeStackDepth = 200
  };

  // State that is set before the preprocessor begins.
  bool KeepComments : 1;
  bool KeepMacroComments : 1;
  bool SuppressIncludeNotFoundError : 1;

  // State that changes while the preprocessor runs:
  bool InMacroArgs : 1;            // True if parsing fn macro invocation args.

  /// Whether the preprocessor owns the header search object.
  bool OwnsHeaderSearch : 1;

  /// True if macro expansion is disabled.
  bool DisableMacroExpansion : 1;

  /// Temporarily disables DisableMacroExpansion (i.e. enables expansion)
  /// when parsing preprocessor directives.
  bool MacroExpansionInDirectivesOverride : 1;

  class ResetMacroExpansionHelper;

  /// \brief Whether we have already loaded macros from the external source.
  mutable bool ReadMacrosFromExternalSource : 1;

  /// \brief True if pragmas are enabled.
  bool PragmasEnabled : 1;

  /// \brief True if the current build action is a preprocessing action.
  bool PreprocessedOutput : 1;

  /// \brief True if we are currently preprocessing a #if or #elif directive
  bool ParsingIfOrElifDirective;

  /// \brief True if we are pre-expanding macro arguments.
  bool InMacroArgPreExpansion;

  /// \brief Mapping/lookup information for all identifiers in
  /// the program, including program keywords.
  mutable IdentifierTable Identifiers;

  /// \brief This table contains all the selectors in the program.
  ///
  /// Unlike IdentifierTable above, this table *isn't* populated by the
  /// preprocessor. It is declared/expanded here because its role/lifetime is
  /// conceptually similar to the IdentifierTable. In addition, the current
  /// control flow (in clang::ParseAST()), make it convenient to put here.
  ///
  /// FIXME: Make sure the lifetime of Identifiers/Selectors *isn't* tied to
  /// the lifetime of the preprocessor.
  SelectorTable Selectors;

  /// \brief Information about builtins.
  Builtin::Context BuiltinInfo;

  /// \brief Tracks all of the pragmas that the client registered
  /// with this preprocessor.
  std::unique_ptr<PragmaNamespace> PragmaHandlers;

  /// \brief Pragma handlers of the original source is stored here during the
  /// parsing of a model file.
  std::unique_ptr<PragmaNamespace> PragmaHandlersBackup;

  /// \brief Tracks all of the comment handlers that the client registered
  /// with this preprocessor.
  std::vector<CommentHandler *> CommentHandlers;

  /// \brief True if we want to ignore EOF token and continue later on (thus 
  /// avoid tearing the Lexer and etc. down).
  bool IncrementalProcessing;

  /// The kind of translation unit we are processing.
  TranslationUnitKind TUKind;

  /// \brief The code-completion handler.
  CodeCompletionHandler *CodeComplete;

  /// \brief The file that we're performing code-completion for, if any.
  const FileEntry *CodeCompletionFile;

  /// \brief The offset in file for the code-completion point.
  unsigned CodeCompletionOffset;

  /// \brief The location for the code-completion point. This gets instantiated
  /// when the CodeCompletionFile gets \#include'ed for preprocessing.
  SourceLocation CodeCompletionLoc;

  /// \brief The start location for the file of the code-completion point.
  ///
  /// This gets instantiated when the CodeCompletionFile gets \#include'ed
  /// for preprocessing.
  SourceLocation CodeCompletionFileLoc;

  /// \brief The source location of the \c import contextual keyword we just 
  /// lexed, if any.
  SourceLocation ModuleImportLoc;

  /// \brief The module import path that we're currently processing.
  SmallVector<std::pair<IdentifierInfo *, SourceLocation>, 2> ModuleImportPath;

  /// \brief Whether the last token we lexed was an '@'.
  bool LastTokenWasAt;

  /// \brief Whether the module import expects an identifier next. Otherwise,
  /// it expects a '.' or ';'.
  bool ModuleImportExpectsIdentifier;
  
  /// \brief The source location of the currently-active
  /// \#pragma clang arc_cf_code_audited begin.
  SourceLocation PragmaARCCFCodeAuditedLoc;

  /// \brief The source location of the currently-active
  /// \#pragma clang assume_nonnull begin.
  SourceLocation PragmaAssumeNonNullLoc;

  /// \brief True if we hit the code-completion point.
  bool CodeCompletionReached;

  /// \brief The directory that the main file should be considered to occupy,
  /// if it does not correspond to a real file (as happens when building a
  /// module).
  const DirectoryEntry *MainFileDir;

  /// \brief The number of bytes that we will initially skip when entering the
  /// main file, along with a flag that indicates whether skipping this number
  /// of bytes will place the lexer at the start of a line.
  ///
  /// This is used when loading a precompiled preamble.
  std::pair<int, bool> SkipMainFilePreamble;

  /// \brief The current top of the stack that we're lexing from if
  /// not expanding a macro and we are lexing directly from source code.
  ///
  /// Only one of CurLexer, CurPTHLexer, or CurTokenLexer will be non-null.
  std::unique_ptr<Lexer> CurLexer;

  /// \brief The current top of stack that we're lexing from if
  /// not expanding from a macro and we are lexing from a PTH cache.
  ///
  /// Only one of CurLexer, CurPTHLexer, or CurTokenLexer will be non-null.
  std::unique_ptr<PTHLexer> CurPTHLexer;

  /// \brief The current top of the stack what we're lexing from
  /// if not expanding a macro.
  ///
  /// This is an alias for either CurLexer or  CurPTHLexer.
  PreprocessorLexer *CurPPLexer;

  /// \brief Used to find the current FileEntry, if CurLexer is non-null
  /// and if applicable.
  ///
  /// This allows us to implement \#include_next and find directory-specific
  /// properties.
  const DirectoryLookup *CurDirLookup;

  /// \brief The current macro we are expanding, if we are expanding a macro.
  ///
  /// One of CurLexer and CurTokenLexer must be null.
  std::unique_ptr<TokenLexer> CurTokenLexer;

  /// \brief The kind of lexer we're currently working with.
  enum CurLexerKind {
    CLK_Lexer,
    CLK_PTHLexer,
    CLK_TokenLexer,
    CLK_CachingLexer,
    CLK_LexAfterModuleImport
  } CurLexerKind;

  /// \brief If the current lexer is for a submodule that is being built, this
  /// is that submodule.
  Module *CurSubmodule;

  /// \brief Keeps track of the stack of files currently
  /// \#included, and macros currently being expanded from, not counting
  /// CurLexer/CurTokenLexer.
  struct IncludeStackInfo {
    enum CurLexerKind           CurLexerKind;
    Module                     *TheSubmodule;
    std::unique_ptr<Lexer>      TheLexer;
    std::unique_ptr<PTHLexer>   ThePTHLexer;
    PreprocessorLexer          *ThePPLexer;
    std::unique_ptr<TokenLexer> TheTokenLexer;
    const DirectoryLookup      *TheDirLookup;

    // The following constructors are completely useless copies of the default
    // versions, only needed to pacify MSVC.
    IncludeStackInfo(enum CurLexerKind CurLexerKind, Module *TheSubmodule,
                     std::unique_ptr<Lexer> &&TheLexer,
                     std::unique_ptr<PTHLexer> &&ThePTHLexer,
                     PreprocessorLexer *ThePPLexer,
                     std::unique_ptr<TokenLexer> &&TheTokenLexer,
                     const DirectoryLookup *TheDirLookup)
        : CurLexerKind(std::move(CurLexerKind)),
          TheSubmodule(std::move(TheSubmodule)), TheLexer(std::move(TheLexer)),
          ThePTHLexer(std::move(ThePTHLexer)),
          ThePPLexer(std::move(ThePPLexer)),
          TheTokenLexer(std::move(TheTokenLexer)),
          TheDirLookup(std::move(TheDirLookup)) {}
    IncludeStackInfo(IncludeStackInfo &&RHS)
        : CurLexerKind(std::move(RHS.CurLexerKind)),
          TheSubmodule(std::move(RHS.TheSubmodule)),
          TheLexer(std::move(RHS.TheLexer)),
          ThePTHLexer(std::move(RHS.ThePTHLexer)),
          ThePPLexer(std::move(RHS.ThePPLexer)),
          TheTokenLexer(std::move(RHS.TheTokenLexer)),
          TheDirLookup(std::move(RHS.TheDirLookup)) {}
  };
  std::vector<IncludeStackInfo> IncludeMacroStack;

  /// \brief Actions invoked when some preprocessor activity is
  /// encountered (e.g. a file is \#included, etc).
  std::unique_ptr<PPCallbacks> Callbacks;

  struct MacroExpandsInfo {
    Token Tok;
    MacroDefinition MD;
    SourceRange Range;
    MacroExpandsInfo(Token Tok, MacroDefinition MD, SourceRange Range)
      : Tok(Tok), MD(MD), Range(Range) { }
  };
  SmallVector<MacroExpandsInfo, 2> DelayedMacroExpandsCallbacks;

  /// Information about a name that has been used to define a module macro.
  struct ModuleMacroInfo {
    ModuleMacroInfo(MacroDirective *MD)
        : MD(MD), ActiveModuleMacrosGeneration(0), IsAmbiguous(false) {}

    /// The most recent macro directive for this identifier.
    MacroDirective *MD;
    /// The active module macros for this identifier.
    llvm::TinyPtrVector<ModuleMacro*> ActiveModuleMacros;
    /// The generation number at which we last updated ActiveModuleMacros.
    /// \see Preprocessor::VisibleModules.
    unsigned ActiveModuleMacrosGeneration;
    /// Whether this macro name is ambiguous.
    bool IsAmbiguous;
    /// The module macros that are overridden by this macro.
    llvm::TinyPtrVector<ModuleMacro*> OverriddenMacros;
  };

  /// The state of a macro for an identifier.
  class MacroState {
    mutable llvm::PointerUnion<MacroDirective *, ModuleMacroInfo *> State;

    ModuleMacroInfo *getModuleInfo(Preprocessor &PP,
                                   const IdentifierInfo *II) const {
      // FIXME: Find a spare bit on IdentifierInfo and store a
      //        HasModuleMacros flag.
      if (!II->hasMacroDefinition() ||
          (!PP.getLangOpts().Modules &&
           !PP.getLangOpts().ModulesLocalVisibility) ||
          !PP.CurSubmoduleState->VisibleModules.getGeneration())
        return nullptr;

      auto *Info = State.dyn_cast<ModuleMacroInfo*>();
      if (!Info) {
        Info = new (PP.getPreprocessorAllocator())
            ModuleMacroInfo(State.get<MacroDirective *>());
        State = Info;
      }

      if (PP.CurSubmoduleState->VisibleModules.getGeneration() !=
          Info->ActiveModuleMacrosGeneration)
        PP.updateModuleMacroInfo(II, *Info);
      return Info;
    }

  public:
    MacroState() : MacroState(nullptr) {}
    MacroState(MacroDirective *MD) : State(MD) {}
    MacroState(MacroState &&O) LLVM_NOEXCEPT : State(O.State) {
      O.State = (MacroDirective *)nullptr;
    }
    MacroState &operator=(MacroState &&O) LLVM_NOEXCEPT {
      auto S = O.State;
      O.State = (MacroDirective *)nullptr;
      State = S;
      return *this;
    }
    ~MacroState() {
      if (auto *Info = State.dyn_cast<ModuleMacroInfo*>())
        Info->~ModuleMacroInfo();
    }

    MacroDirective *getLatest() const {
      if (auto *Info = State.dyn_cast<ModuleMacroInfo*>())
        return Info->MD;
      return State.get<MacroDirective*>();
    }
    void setLatest(MacroDirective *MD) {
      if (auto *Info = State.dyn_cast<ModuleMacroInfo*>())
        Info->MD = MD;
      else
        State = MD;
    }

    bool isAmbiguous(Preprocessor &PP, const IdentifierInfo *II) const {
      auto *Info = getModuleInfo(PP, II);
      return Info ? Info->IsAmbiguous : false;
    }
    ArrayRef<ModuleMacro *>
    getActiveModuleMacros(Preprocessor &PP, const IdentifierInfo *II) const {
      if (auto *Info = getModuleInfo(PP, II))
        return Info->ActiveModuleMacros;
      return None;
    }

    MacroDirective::DefInfo findDirectiveAtLoc(SourceLocation Loc,
                                               SourceManager &SourceMgr) const {
      // FIXME: Incorporate module macros into the result of this.
      if (auto *Latest = getLatest())
        return Latest->findDirectiveAtLoc(Loc, SourceMgr);
      return MacroDirective::DefInfo();
    }

    void overrideActiveModuleMacros(Preprocessor &PP, IdentifierInfo *II) {
      if (auto *Info = getModuleInfo(PP, II)) {
        Info->OverriddenMacros.insert(Info->OverriddenMacros.end(),
                                      Info->ActiveModuleMacros.begin(),
                                      Info->ActiveModuleMacros.end());
        Info->ActiveModuleMacros.clear();
        Info->IsAmbiguous = false;
      }
    }
    ArrayRef<ModuleMacro*> getOverriddenMacros() const {
      if (auto *Info = State.dyn_cast<ModuleMacroInfo*>())
        return Info->OverriddenMacros;
      return None;
    }
    void setOverriddenMacros(Preprocessor &PP,
                             ArrayRef<ModuleMacro *> Overrides) {
      auto *Info = State.dyn_cast<ModuleMacroInfo*>();
      if (!Info) {
        if (Overrides.empty())
          return;
        Info = new (PP.getPreprocessorAllocator())
            ModuleMacroInfo(State.get<MacroDirective *>());
        State = Info;
      }
      Info->OverriddenMacros.clear();
      Info->OverriddenMacros.insert(Info->OverriddenMacros.end(),
                                    Overrides.begin(), Overrides.end());
      Info->ActiveModuleMacrosGeneration = 0;
    }
  };

  /// For each IdentifierInfo that was associated with a macro, we
  /// keep a mapping to the history of all macro definitions and #undefs in
  /// the reverse order (the latest one is in the head of the list).
  ///
  /// This mapping lives within the \p CurSubmoduleState.
  typedef llvm::DenseMap<const IdentifierInfo *, MacroState> MacroMap;

  friend class ASTReader;

  struct SubmoduleState;

  /// \brief Information about a submodule that we're currently building.
  struct BuildingSubmoduleInfo {
    BuildingSubmoduleInfo(Module *M, SourceLocation ImportLoc,
                          SubmoduleState *OuterSubmoduleState,
                          unsigned OuterPendingModuleMacroNames)
        : M(M), ImportLoc(ImportLoc), OuterSubmoduleState(OuterSubmoduleState),
          OuterPendingModuleMacroNames(OuterPendingModuleMacroNames) {}

    /// The module that we are building.
    Module *M;
    /// The location at which the module was included.
    SourceLocation ImportLoc;
    /// The previous SubmoduleState.
    SubmoduleState *OuterSubmoduleState;
    /// The number of pending module macro names when we started building this.
    unsigned OuterPendingModuleMacroNames;
  };
  SmallVector<BuildingSubmoduleInfo, 8> BuildingSubmoduleStack;

  /// \brief Information about a submodule's preprocessor state.
  struct SubmoduleState {
    /// The macros for the submodule.
    MacroMap Macros;
    /// The set of modules that are visible within the submodule.
    VisibleModuleSet VisibleModules;
    // FIXME: CounterValue?
    // FIXME: PragmaPushMacroInfo?
  };
  std::map<Module*, SubmoduleState> Submodules;

  /// The preprocessor state for preprocessing outside of any submodule.
  SubmoduleState NullSubmoduleState;

  /// The current submodule state. Will be \p NullSubmoduleState if we're not
  /// in a submodule.
  SubmoduleState *CurSubmoduleState;

  /// The set of known macros exported from modules.
  llvm::FoldingSet<ModuleMacro> ModuleMacros;

  /// The names of potential module macros that we've not yet processed.
  llvm::SmallVector<const IdentifierInfo*, 32> PendingModuleMacroNames;

  /// The list of module macros, for each identifier, that are not overridden by
  /// any other module macro.
  llvm::DenseMap<const IdentifierInfo *, llvm::TinyPtrVector<ModuleMacro*>>
      LeafModuleMacros;

  /// \brief Macros that we want to warn because they are not used at the end
  /// of the translation unit.
  ///
  /// We store just their SourceLocations instead of
  /// something like MacroInfo*. The benefit of this is that when we are
  /// deserializing from PCH, we don't need to deserialize identifier & macros
  /// just so that we can report that they are unused, we just warn using
  /// the SourceLocations of this set (that will be filled by the ASTReader).
  /// We are using SmallPtrSet instead of a vector for faster removal.
  typedef llvm::SmallPtrSet<SourceLocation, 32> WarnUnusedMacroLocsTy;
  WarnUnusedMacroLocsTy WarnUnusedMacroLocs;

  /// \brief A "freelist" of MacroArg objects that can be
  /// reused for quick allocation.
  MacroArgs *MacroArgCache;
  friend class MacroArgs;

  /// For each IdentifierInfo used in a \#pragma push_macro directive,
  /// we keep a MacroInfo stack used to restore the previous macro value.
  llvm::DenseMap<IdentifierInfo*, std::vector<MacroInfo*> > PragmaPushMacroInfo;

  // Various statistics we track for performance analysis.
  unsigned NumDirectives, NumDefined, NumUndefined, NumPragma;
  unsigned NumIf, NumElse, NumEndif;
  unsigned NumEnteredSourceFiles, MaxIncludeStackDepth;
  unsigned NumMacroExpanded, NumFnMacroExpanded, NumBuiltinMacroExpanded;
  unsigned NumFastMacroExpanded, NumTokenPaste, NumFastTokenPaste;
  unsigned NumSkipped;

  /// \brief The predefined macros that preprocessor should use from the
  /// command line etc.
  std::string Predefines;

  /// \brief The file ID for the preprocessor predefines.
  FileID PredefinesFileID;

  /// \{
  /// \brief Cache of macro expanders to reduce malloc traffic.
  enum { TokenLexerCacheSize = 8 };
  unsigned NumCachedTokenLexers;
  std::unique_ptr<TokenLexer> TokenLexerCache[TokenLexerCacheSize];
  /// \}

  /// \brief Keeps macro expanded tokens for TokenLexers.
  //
  /// Works like a stack; a TokenLexer adds the macro expanded tokens that is
  /// going to lex in the cache and when it finishes the tokens are removed
  /// from the end of the cache.
  SmallVector<Token, 16> MacroExpandedTokens;
  std::vector<std::pair<TokenLexer *, size_t> > MacroExpandingLexersStack;

  /// \brief A record of the macro definitions and expansions that
  /// occurred during preprocessing.
  ///
  /// This is an optional side structure that can be enabled with
  /// \c createPreprocessingRecord() prior to preprocessing.
  PreprocessingRecord *Record;

  /// Cached tokens state.
  typedef SmallVector<Token, 1> CachedTokensTy;

  /// \brief Cached tokens are stored here when we do backtracking or
  /// lookahead. They are "lexed" by the CachingLex() method.
  CachedTokensTy CachedTokens;

  /// \brief The position of the cached token that CachingLex() should
  /// "lex" next.
  ///
  /// If it points beyond the CachedTokens vector, it means that a normal
  /// Lex() should be invoked.
  CachedTokensTy::size_type CachedLexPos;

  /// \brief Stack of backtrack positions, allowing nested backtracks.
  ///
  /// The EnableBacktrackAtThisPos() method pushes a position to
  /// indicate where CachedLexPos should be set when the BackTrack() method is
  /// invoked (at which point the last position is popped).
  std::vector<CachedTokensTy::size_type> BacktrackPositions;

  struct MacroInfoChain {
    MacroInfo MI;
    MacroInfoChain *Next;
  };

  /// MacroInfos are managed as a chain for easy disposal.  This is the head
  /// of that list.
  MacroInfoChain *MIChainHead;

  struct DeserializedMacroInfoChain {
    MacroInfo MI;
    unsigned OwningModuleID; // MUST be immediately after the MacroInfo object
                     // so it can be accessed by MacroInfo::getOwningModuleID().
    DeserializedMacroInfoChain *Next;
  };
  DeserializedMacroInfoChain *DeserialMIChainHead;

public:
  Preprocessor(IntrusiveRefCntPtr<PreprocessorOptions> PPOpts,
               DiagnosticsEngine &diags, LangOptions &opts,
               SourceManager &SM, HeaderSearch &Headers,
               ModuleLoader &TheModuleLoader,
               IdentifierInfoLookup *IILookup = nullptr,
               bool OwnsHeaderSearch = false,
               TranslationUnitKind TUKind = TU_Complete);

  ~Preprocessor();

  /// \brief Initialize the preprocessor using information about the target.
  ///
  /// \param Target is owned by the caller and must remain valid for the
  /// lifetime of the preprocessor.
  /// \param AuxTarget is owned by the caller and must remain valid for
  /// the lifetime of the preprocessor.
  void Initialize(const TargetInfo &Target,
                  const TargetInfo *AuxTarget = nullptr);

  /// \brief Initialize the preprocessor to parse a model file
  ///
  /// To parse model files the preprocessor of the original source is reused to
  /// preserver the identifier table. However to avoid some duplicate
  /// information in the preprocessor some cleanup is needed before it is used
  /// to parse model files. This method does that cleanup.
  void InitializeForModelFile();

  /// \brief Cleanup after model file parsing
  void FinalizeForModelFile();

  /// \brief Retrieve the preprocessor options used to initialize this
  /// preprocessor.
  PreprocessorOptions &getPreprocessorOpts() const { return *PPOpts; }
  
  DiagnosticsEngine &getDiagnostics() const { return *Diags; }
  void setDiagnostics(DiagnosticsEngine &D) { Diags = &D; }

  const LangOptions &getLangOpts() const { return LangOpts; }
  const TargetInfo &getTargetInfo() const { return *Target; }
  const TargetInfo *getAuxTargetInfo() const { return AuxTarget; }
  FileManager &getFileManager() const { return FileMgr; }
  SourceManager &getSourceManager() const { return SourceMgr; }
  HeaderSearch &getHeaderSearchInfo() const { return HeaderInfo; }

  IdentifierTable &getIdentifierTable() { return Identifiers; }
  const IdentifierTable &getIdentifierTable() const { return Identifiers; }
  SelectorTable &getSelectorTable() { return Selectors; }
  Builtin::Context &getBuiltinInfo() { return BuiltinInfo; }
  llvm::BumpPtrAllocator &getPreprocessorAllocator() { return BP; }

  void setPTHManager(PTHManager* pm);

  PTHManager *getPTHManager() { return PTH.get(); }

  void setExternalSource(ExternalPreprocessorSource *Source) {
    ExternalSource = Source;
  }

  ExternalPreprocessorSource *getExternalSource() const {
    return ExternalSource;
  }

  /// \brief Retrieve the module loader associated with this preprocessor.
  ModuleLoader &getModuleLoader() const { return TheModuleLoader; }

  bool hadModuleLoaderFatalFailure() const {
    return TheModuleLoader.HadFatalFailure;
  }

  /// \brief True if we are currently preprocessing a #if or #elif directive
  bool isParsingIfOrElifDirective() const { 
    return ParsingIfOrElifDirective;
  }

  /// \brief Control whether the preprocessor retains comments in output.
  void SetCommentRetentionState(bool KeepComments, bool KeepMacroComments) {
    this->KeepComments = KeepComments | KeepMacroComments;
    this->KeepMacroComments = KeepMacroComments;
  }

  bool getCommentRetentionState() const { return KeepComments; }

  void setPragmasEnabled(bool Enabled) { PragmasEnabled = Enabled; }
  bool getPragmasEnabled() const { return PragmasEnabled; }

  void SetSuppressIncludeNotFoundError(bool Suppress) {
    SuppressIncludeNotFoundError = Suppress;
  }

  bool GetSuppressIncludeNotFoundError() {
    return SuppressIncludeNotFoundError;
  }

  /// Sets whether the preprocessor is responsible for producing output or if
  /// it is producing tokens to be consumed by Parse and Sema.
  void setPreprocessedOutput(bool IsPreprocessedOutput) {
    PreprocessedOutput = IsPreprocessedOutput;
  }

  /// Returns true if the preprocessor is responsible for generating output,
  /// false if it is producing tokens to be consumed by Parse and Sema.
  bool isPreprocessedOutput() const { return PreprocessedOutput; }

  /// \brief Return true if we are lexing directly from the specified lexer.
  bool isCurrentLexer(const PreprocessorLexer *L) const {
    return CurPPLexer == L;
  }

  /// \brief Return the current lexer being lexed from.
  ///
  /// Note that this ignores any potentially active macro expansions and _Pragma
  /// expansions going on at the time.
  PreprocessorLexer *getCurrentLexer() const { return CurPPLexer; }

  /// \brief Return the current file lexer being lexed from.
  ///
  /// Note that this ignores any potentially active macro expansions and _Pragma
  /// expansions going on at the time.
  PreprocessorLexer *getCurrentFileLexer() const;

  /// \brief Return the submodule owning the file being lexed.
  Module *getCurrentSubmodule() const { return CurSubmodule; }

  /// \brief Returns the FileID for the preprocessor predefines.
  FileID getPredefinesFileID() const { return PredefinesFileID; }

  /// \{
  /// \brief Accessors for preprocessor callbacks.
  ///
  /// Note that this class takes ownership of any PPCallbacks object given to
  /// it.
  PPCallbacks *getPPCallbacks() const { return Callbacks.get(); }
  void addPPCallbacks(std::unique_ptr<PPCallbacks> C) {
    if (Callbacks)
      C = llvm::make_unique<PPChainedCallbacks>(std::move(C),
                                                std::move(Callbacks));
    Callbacks = std::move(C);
  }
  /// \}

  bool isMacroDefined(StringRef Id) {
    return isMacroDefined(&Identifiers.get(Id));
  }
  bool isMacroDefined(const IdentifierInfo *II) {
    return II->hasMacroDefinition() &&
           (!getLangOpts().Modules || (bool)getMacroDefinition(II));
  }

  /// \brief Determine whether II is defined as a macro within the module M,
  /// if that is a module that we've already preprocessed. Does not check for
  /// macros imported into M.
  bool isMacroDefinedInLocalModule(const IdentifierInfo *II, Module *M) {
    if (!II->hasMacroDefinition())
      return false;
    auto I = Submodules.find(M);
    if (I == Submodules.end())
      return false;
    auto J = I->second.Macros.find(II);
    if (J == I->second.Macros.end())
      return false;
    auto *MD = J->second.getLatest();
    return MD && MD->isDefined();
  }

  MacroDefinition getMacroDefinition(const IdentifierInfo *II) {
    if (!II->hasMacroDefinition())
      return MacroDefinition();

    MacroState &S = CurSubmoduleState->Macros[II];
    auto *MD = S.getLatest();
    while (MD && isa<VisibilityMacroDirective>(MD))
      MD = MD->getPrevious();
    return MacroDefinition(dyn_cast_or_null<DefMacroDirective>(MD),
                           S.getActiveModuleMacros(*this, II),
                           S.isAmbiguous(*this, II));
  }

  MacroDefinition getMacroDefinitionAtLoc(const IdentifierInfo *II,
                                          SourceLocation Loc) {
    if (!II->hadMacroDefinition())
      return MacroDefinition();

    MacroState &S = CurSubmoduleState->Macros[II];
    MacroDirective::DefInfo DI;
    if (auto *MD = S.getLatest())
      DI = MD->findDirectiveAtLoc(Loc, getSourceManager());
    // FIXME: Compute the set of active module macros at the specified location.
    return MacroDefinition(DI.getDirective(),
                           S.getActiveModuleMacros(*this, II),
                           S.isAmbiguous(*this, II));
  }

  /// \brief Given an identifier, return its latest non-imported MacroDirective
  /// if it is \#define'd and not \#undef'd, or null if it isn't \#define'd.
  MacroDirective *getLocalMacroDirective(const IdentifierInfo *II) const {
    if (!II->hasMacroDefinition())
      return nullptr;

    auto *MD = getLocalMacroDirectiveHistory(II);
    if (!MD || MD->getDefinition().isUndefined())
      return nullptr;

    return MD;
  }

  const MacroInfo *getMacroInfo(const IdentifierInfo *II) const {
    return const_cast<Preprocessor*>(this)->getMacroInfo(II);
  }

  MacroInfo *getMacroInfo(const IdentifierInfo *II) {
    if (!II->hasMacroDefinition())
      return nullptr;
    if (auto MD = getMacroDefinition(II))
      return MD.getMacroInfo();
    return nullptr;
  }

  /// \brief Given an identifier, return the latest non-imported macro
  /// directive for that identifier.
  ///
  /// One can iterate over all previous macro directives from the most recent
  /// one.
  MacroDirective *getLocalMacroDirectiveHistory(const IdentifierInfo *II) const;

  /// \brief Add a directive to the macro directive history for this identifier.
  void appendMacroDirective(IdentifierInfo *II, MacroDirective *MD);
  DefMacroDirective *appendDefMacroDirective(IdentifierInfo *II, MacroInfo *MI,
                                             SourceLocation Loc) {
    DefMacroDirective *MD = AllocateDefMacroDirective(MI, Loc);
    appendMacroDirective(II, MD);
    return MD;
  }
  DefMacroDirective *appendDefMacroDirective(IdentifierInfo *II,
                                             MacroInfo *MI) {
    return appendDefMacroDirective(II, MI, MI->getDefinitionLoc());
  }
  /// \brief Set a MacroDirective that was loaded from a PCH file.
  void setLoadedMacroDirective(IdentifierInfo *II, MacroDirective *MD);

  /// \brief Register an exported macro for a module and identifier.
  ModuleMacro *addModuleMacro(Module *Mod, IdentifierInfo *II, MacroInfo *Macro,
                              ArrayRef<ModuleMacro *> Overrides, bool &IsNew);
  ModuleMacro *getModuleMacro(Module *Mod, IdentifierInfo *II);

  /// \brief Get the list of leaf (non-overridden) module macros for a name.
  ArrayRef<ModuleMacro*> getLeafModuleMacros(const IdentifierInfo *II) const {
    auto I = LeafModuleMacros.find(II);
    if (I != LeafModuleMacros.end())
      return I->second;
    return None;
  }

  /// \{
  /// Iterators for the macro history table. Currently defined macros have
  /// IdentifierInfo::hasMacroDefinition() set and an empty
  /// MacroInfo::getUndefLoc() at the head of the list.
  typedef MacroMap::const_iterator macro_iterator;
  macro_iterator macro_begin(bool IncludeExternalMacros = true) const;
  macro_iterator macro_end(bool IncludeExternalMacros = true) const;
  llvm::iterator_range<macro_iterator>
  macros(bool IncludeExternalMacros = true) const {
    return llvm::make_range(macro_begin(IncludeExternalMacros),
                            macro_end(IncludeExternalMacros));
  }
  /// \}

  /// \brief Return the name of the macro defined before \p Loc that has
  /// spelling \p Tokens.  If there are multiple macros with same spelling,
  /// return the last one defined.
  StringRef getLastMacroWithSpelling(SourceLocation Loc,
                                     ArrayRef<TokenValue> Tokens) const;

  const std::string &getPredefines() const { return Predefines; }
  /// \brief Set the predefines for this Preprocessor.
  ///
  /// These predefines are automatically injected when parsing the main file.
  void setPredefines(const char *P) { Predefines = P; }
  void setPredefines(StringRef P) { Predefines = P; }

  /// Return information about the specified preprocessor
  /// identifier token.
  IdentifierInfo *getIdentifierInfo(StringRef Name) const {
    return &Identifiers.get(Name);
  }

  /// \brief Add the specified pragma handler to this preprocessor.
  ///
  /// If \p Namespace is non-null, then it is a token required to exist on the
  /// pragma line before the pragma string starts, e.g. "STDC" or "GCC".
  void AddPragmaHandler(StringRef Namespace, PragmaHandler *Handler);
  void AddPragmaHandler(PragmaHandler *Handler) {
    AddPragmaHandler(StringRef(), Handler);
  }

  /// \brief Remove the specific pragma handler from this preprocessor.
  ///
  /// If \p Namespace is non-null, then it should be the namespace that
  /// \p Handler was added to. It is an error to remove a handler that
  /// has not been registered.
  void RemovePragmaHandler(StringRef Namespace, PragmaHandler *Handler);
  void RemovePragmaHandler(PragmaHandler *Handler) {
    RemovePragmaHandler(StringRef(), Handler);
  }

  /// Install empty handlers for all pragmas (making them ignored).
  void IgnorePragmas();

  /// \brief Add the specified comment handler to the preprocessor.
  void addCommentHandler(CommentHandler *Handler);

  /// \brief Remove the specified comment handler.
  ///
  /// It is an error to remove a handler that has not been registered.
  void removeCommentHandler(CommentHandler *Handler);

  /// \brief Set the code completion handler to the given object.
  void setCodeCompletionHandler(CodeCompletionHandler &Handler) {
    CodeComplete = &Handler;
  }

  /// \brief Retrieve the current code-completion handler.
  CodeCompletionHandler *getCodeCompletionHandler() const {
    return CodeComplete;
  }

  /// \brief Clear out the code completion handler.
  void clearCodeCompletionHandler() {
    CodeComplete = nullptr;
  }

  /// \brief Hook used by the lexer to invoke the "natural language" code
  /// completion point.
  void CodeCompleteNaturalLanguage();

  /// \brief Retrieve the preprocessing record, or NULL if there is no
  /// preprocessing record.
  PreprocessingRecord *getPreprocessingRecord() const { return Record; }

  /// \brief Create a new preprocessing record, which will keep track of
  /// all macro expansions, macro definitions, etc.
  void createPreprocessingRecord();

  /// \brief Enter the specified FileID as the main source file,
  /// which implicitly adds the builtin defines etc.
  void EnterMainSourceFile();

  /// \brief Inform the preprocessor callbacks that processing is complete.
  void EndSourceFile();