lib/Lex/PreprocessingRecord.cpp - platform/external/clang - Git at Google

 //===--- PreprocessingRecord.cpp - Record of Preprocessing ------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file implements the PreprocessingRecord class, which maintains a record
 //  of what occurred during preprocessing, and its helpers.
 //
 //===----------------------------------------------------------------------===//
 #include "clang/Lex/PreprocessingRecord.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/Token.h"
 #include "llvm/Support/Capacity.h"
 #include "llvm/Support/ErrorHandling.h"

 using namespace clang;

 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }


 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
                                        InclusionKind Kind,
                                        StringRef FileName,
                                        bool InQuotes, bool ImportedModule,
                                        const FileEntry *File,
                                        SourceRange Range)
   : PreprocessingDirective(InclusionDirectiveKind, Range),
     InQuotes(InQuotes), Kind(Kind), ImportedModule(ImportedModule), File(File)
 {
   char *Memory
     = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
   memcpy(Memory, FileName.data(), FileName.size());
   Memory[FileName.size()] = 0;
   this->FileName = StringRef(Memory, FileName.size());
 }

 PreprocessingRecord::PreprocessingRecord(SourceManager &SM)
   : SourceMgr(SM),
     ExternalSource(0) {
 }

 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
 /// that source range \p Range encompasses.
 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
   if (Range.isInvalid())
     return std::make_pair(iterator(), iterator());

   if (CachedRangeQuery.Range == Range) {
     return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
                           iterator(this, CachedRangeQuery.Result.second));
   }

   std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);

   CachedRangeQuery.Range = Range;
   CachedRangeQuery.Result = Res;

   return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
 }

 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
                                            SourceManager &SM) {
   assert(!FID.isInvalid());
   if (!PPE)
     return false;

   SourceLocation Loc = PPE->getSourceRange().getBegin();
   if (Loc.isInvalid())
     return false;

   if (SM.isInFileID(SM.getFileLoc(Loc), FID))
     return true;
   else
     return false;
 }

 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
 /// points to is coming from the file \arg FID.
 ///
 /// Can be used to avoid implicit deserializations of preallocated
 /// preprocessed entities if we only care about entities of a specific file
 /// and not from files \#included in the range given at
 /// \see getPreprocessedEntitiesInRange.
 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
   if (FID.isInvalid())
     return false;

   int Pos = PPEI.Position;
   if (Pos < 0) {
     if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
       assert(0 && "Out-of bounds loaded preprocessed entity");
       return false;
     }
     assert(ExternalSource && "No external source to load from");
     unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
     if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
       return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);

     // See if the external source can see if the entity is in the file without
     // deserializing it.
     Optional<bool> IsInFile =
         ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
     if (IsInFile.hasValue())
       return IsInFile.getValue();

     // The external source did not provide a definite answer, go and deserialize
     // the entity to check it.
     return isPreprocessedEntityIfInFileID(
                                        getLoadedPreprocessedEntity(LoadedIndex),
                                           FID, SourceMgr);
   }

   if (unsigned(Pos) >= PreprocessedEntities.size()) {
     assert(0 && "Out-of bounds local preprocessed entity");
     return false;
   }
   return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
                                         FID, SourceMgr);
 }

 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
 /// that source range \arg R encompasses.
 std::pair<int, int>
 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
   assert(Range.isValid());
   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));

   std::pair<unsigned, unsigned>
     Local = findLocalPreprocessedEntitiesInRange(Range);

   // Check if range spans local entities.
   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
     return std::make_pair(Local.first, Local.second);

   std::pair<unsigned, unsigned>
     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);

   // Check if range spans local entities.
   if (Loaded.first == Loaded.second)
     return std::make_pair(Local.first, Local.second);

   unsigned TotalLoaded = LoadedPreprocessedEntities.size();

   // Check if range spans loaded entities.
   if (Local.first == Local.second)
     return std::make_pair(int(Loaded.first)-TotalLoaded,
                           int(Loaded.second)-TotalLoaded);

   // Range spands loaded and local entities.
   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
 }

 std::pair<unsigned, unsigned>
 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
                                                       SourceRange Range) const {
   if (Range.isInvalid())
     return std::make_pair(0,0);
   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));

   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
   return std::make_pair(Begin, End);
 }

 namespace {

 template <SourceLocation (SourceRange::*getRangeLoc)() const>
 struct PPEntityComp {
   const SourceManager &SM;

   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }

   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
     SourceLocation LHS = getLoc(L);
     SourceLocation RHS = getLoc(R);
     return SM.isBeforeInTranslationUnit(LHS, RHS);
   }

   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
     SourceLocation LHS = getLoc(L);
     return SM.isBeforeInTranslationUnit(LHS, RHS);
   }

   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
     SourceLocation RHS = getLoc(R);
     return SM.isBeforeInTranslationUnit(LHS, RHS);
   }

   SourceLocation getLoc(PreprocessedEntity *PPE) const {
     SourceRange Range = PPE->getSourceRange();
     return (Range.*getRangeLoc)();
   }
 };

 }

 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
                                                      SourceLocation Loc) const {
   if (SourceMgr.isLoadedSourceLocation(Loc))
     return 0;

   size_t Count = PreprocessedEntities.size();
   size_t Half;
   std::vector<PreprocessedEntity *>::const_iterator
     First = PreprocessedEntities.begin();
   std::vector<PreprocessedEntity *>::const_iterator I;

   // Do a binary search manually instead of using std::lower_bound because
   // The end locations of entities may be unordered (when a macro expansion
   // is inside another macro argument), but for this case it is not important
   // whether we get the first macro expansion or its containing macro.
   while (Count > 0) {
     Half = Count/2;
     I = First;
     std::advance(I, Half);
     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
                                             Loc)){
       First = I;
       ++First;
       Count = Count - Half - 1;
     } else
       Count = Half;
   }

   return First - PreprocessedEntities.begin();
 }

 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
                                                      SourceLocation Loc) const {
   if (SourceMgr.isLoadedSourceLocation(Loc))
     return 0;

   std::vector<PreprocessedEntity *>::const_iterator
   I = std::upper_bound(PreprocessedEntities.begin(),
                        PreprocessedEntities.end(),
                        Loc,
                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
   return I - PreprocessedEntities.begin();
 }

 PreprocessingRecord::PPEntityID
 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
   assert(Entity);
   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();

   if (isa<MacroDefinition>(Entity)) {
     assert((PreprocessedEntities.empty() ||
             !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
                    PreprocessedEntities.back()->getSourceRange().getBegin())) &&
            "a macro definition was encountered out-of-order");
     PreprocessedEntities.push_back(Entity);
     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
   }

   // Check normal case, this entity begin location is after the previous one.
   if (PreprocessedEntities.empty() ||
       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
     PreprocessedEntities.push_back(Entity);
     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
   }

   // The entity's location is not after the previous one; this can happen with
   // include directives that form the filename using macros, e.g:
   // "#include MACRO(STUFF)"
   // or with macro expansions inside macro arguments where the arguments are
   // not expanded in the same order as listed, e.g:
   // \code
   //  #define M1 1
   //  #define M2 2
   //  #define FM(x,y) y x
   //  FM(M1, M2)
   // \endcode

   typedef std::vector<PreprocessedEntity *>::iterator pp_iter;

   // Usually there are few macro expansions when defining the filename, do a
   // linear search for a few entities.
   unsigned count = 0;
   for (pp_iter RI    = PreprocessedEntities.end(),
                Begin = PreprocessedEntities.begin();
        RI != Begin && count < 4; --RI, ++count) {
     pp_iter I = RI;
     --I;
     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
                                            (*I)->getSourceRange().getBegin())) {
       pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
       return getPPEntityID(insertI - PreprocessedEntities.begin(),
                            /*isLoaded=*/false);
     }
   }

   // Linear search unsuccessful. Do a binary search.
   pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
                                PreprocessedEntities.end(),
                                BeginLoc,
                                PPEntityComp<&SourceRange::getBegin>(SourceMgr));
   pp_iter insertI = PreprocessedEntities.insert(I, Entity);
   return getPPEntityID(insertI - PreprocessedEntities.begin(),
                        /*isLoaded=*/false);
 }

 void PreprocessingRecord::SetExternalSource(
                                     ExternalPreprocessingRecordSource &Source) {
   assert(!ExternalSource &&
          "Preprocessing record already has an external source");
   ExternalSource = &Source;
 }

 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
   unsigned Result = LoadedPreprocessedEntities.size();
   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
                                     + NumEntities);
   return Result;
 }

 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
                                                   MacroDefinition *Def) {
   MacroDefinitions[Macro] = Def;
 }

 /// \brief Retrieve the preprocessed entity at the given ID.
 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
   if (PPID.ID < 0) {
     unsigned Index = -PPID.ID - 1;
     assert(Index < LoadedPreprocessedEntities.size() &&
            "Out-of bounds loaded preprocessed entity");
     return getLoadedPreprocessedEntity(Index);
   }

   if (PPID.ID == 0)
     return 0;
   unsigned Index = PPID.ID - 1;
   assert(Index < PreprocessedEntities.size() &&
          "Out-of bounds local preprocessed entity");
   return PreprocessedEntities[Index];
 }

 /// \brief Retrieve the loaded preprocessed entity at the given index.
 PreprocessedEntity *
 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
   assert(Index < LoadedPreprocessedEntities.size() &&
          "Out-of bounds loaded preprocessed entity");
   assert(ExternalSource && "No external source to load from");
   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
   if (!Entity) {
     Entity = ExternalSource->ReadPreprocessedEntity(Index);
     if (!Entity) // Failed to load.
       Entity = new (*this)
          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
   }
   return Entity;
 }

 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
   llvm::DenseMap<const MacroInfo *, MacroDefinition *>::iterator Pos
     = MacroDefinitions.find(MI);
   if (Pos == MacroDefinitions.end())
     return 0;

   return Pos->second;
 }

 void PreprocessingRecord::addMacroExpansion(const Token &Id,
                                             const MacroInfo *MI,
                                             SourceRange Range) {
   // We don't record nested macro expansions.
   if (Id.getLocation().isMacroID())
     return;

   if (MI->isBuiltinMacro())
     addPreprocessedEntity(
                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
   else if (MacroDefinition *Def = findMacroDefinition(MI))
     addPreprocessedEntity(
                        new (*this) MacroExpansion(Def, Range));
 }

 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
                                 const MacroDirective *MD) {
   // This is not actually a macro expansion but record it as a macro reference.
   if (MD)
     addMacroExpansion(MacroNameTok, MD->getInfo(), MacroNameTok.getLocation());
 }

 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
                                  const MacroDirective *MD) {
   // This is not actually a macro expansion but record it as a macro reference.
   if (MD)
     addMacroExpansion(MacroNameTok, MD->getInfo(), MacroNameTok.getLocation());
 }

 void PreprocessingRecord::Defined(const Token &MacroNameTok,
                                   const MacroDirective *MD) {
   // This is not actually a macro expansion but record it as a macro reference.
   if (MD)
     addMacroExpansion(MacroNameTok, MD->getInfo(), MacroNameTok.getLocation());
 }

 void PreprocessingRecord::MacroExpands(const Token &Id,const MacroDirective *MD,
                                        SourceRange Range) {
   addMacroExpansion(Id, MD->getInfo(), Range);
 }

 void PreprocessingRecord::MacroDefined(const Token &Id,
                                        const MacroDirective *MD) {
   const MacroInfo *MI = MD->getInfo();
   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
   MacroDefinition *Def
       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
   addPreprocessedEntity(Def);
   MacroDefinitions[MI] = Def;
 }

 void PreprocessingRecord::MacroUndefined(const Token &Id,
                                          const MacroDirective *MD) {
   // Note: MI may be null (when #undef'ining an undefined macro).
   if (MD)
     MacroDefinitions.erase(MD->getInfo());
 }

 void PreprocessingRecord::InclusionDirective(
     SourceLocation HashLoc,
     const clang::Token &IncludeTok,
     StringRef FileName,
     bool IsAngled,
     CharSourceRange FilenameRange,
     const FileEntry *File,
     StringRef SearchPath,
     StringRef RelativePath,
     const Module *Imported) {
   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;

   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
   case tok::pp_include:
     Kind = InclusionDirective::Include;
     break;

   case tok::pp_import:
     Kind = InclusionDirective::Import;
     break;

   case tok::pp_include_next:
     Kind = InclusionDirective::IncludeNext;
     break;

   case tok::pp___include_macros:
     Kind = InclusionDirective::IncludeMacros;
     break;

   default:
     llvm_unreachable("Unknown include directive kind");
   }

   SourceLocation EndLoc;
   if (!IsAngled) {
     EndLoc = FilenameRange.getBegin();
   } else {
     EndLoc = FilenameRange.getEnd();
     if (FilenameRange.isCharRange())
       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
                                             // a token range.
   }
   clang::InclusionDirective *ID
     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
                                             (bool)Imported,
                                             File, SourceRange(HashLoc, EndLoc));
   addPreprocessedEntity(ID);
 }

 size_t PreprocessingRecord::getTotalMemory() const {
   return BumpAlloc.getTotalMemory()
     + llvm::capacity_in_bytes(MacroDefinitions)
     + llvm::capacity_in_bytes(PreprocessedEntities)
     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
 }
	//===--- PreprocessingRecord.cpp - Record of Preprocessing ------- C++ --===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This file implements the PreprocessingRecord class, which maintains a record
	// of what occurred during preprocessing, and its helpers.
	//
	//===----------------------------------------------------------------------===//
	#include "clang/Lex/PreprocessingRecord.h"
	#include "clang/Lex/MacroInfo.h"
	#include "clang/Lex/Token.h"
	#include "llvm/Support/Capacity.h"
	#include "llvm/Support/ErrorHandling.h"

	using namespace clang;

	ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }


	InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
	InclusionKind Kind,
	StringRef FileName,
	bool InQuotes, bool ImportedModule,
	const FileEntry *File,
	SourceRange Range)
	: PreprocessingDirective(InclusionDirectiveKind, Range),
	InQuotes(InQuotes), Kind(Kind), ImportedModule(ImportedModule), File(File)
	{
	char *Memory
	= (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
	memcpy(Memory, FileName.data(), FileName.size());
	Memory[FileName.size()] = 0;
	this->FileName = StringRef(Memory, FileName.size());
	}

	PreprocessingRecord::PreprocessingRecord(SourceManager &SM)
	: SourceMgr(SM),
	ExternalSource(0) {
	}

	/// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
	/// that source range \p Range encompasses.
	std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
	PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
	if (Range.isInvalid())
	return std::make_pair(iterator(), iterator());

	if (CachedRangeQuery.Range == Range) {
	return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
	iterator(this, CachedRangeQuery.Result.second));
	}

	std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);

	CachedRangeQuery.Range = Range;
	CachedRangeQuery.Result = Res;

	return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
	}

	static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
	SourceManager &SM) {
	assert(!FID.isInvalid());
	if (!PPE)
	return false;

	SourceLocation Loc = PPE->getSourceRange().getBegin();
	if (Loc.isInvalid())
	return false;

	if (SM.isInFileID(SM.getFileLoc(Loc), FID))
	return true;
	else
	return false;
	}

	/// \brief Returns true if the preprocessed entity that \arg PPEI iterator
	/// points to is coming from the file \arg FID.
	///
	/// Can be used to avoid implicit deserializations of preallocated
	/// preprocessed entities if we only care about entities of a specific file
	/// and not from files \#included in the range given at
	/// \see getPreprocessedEntitiesInRange.
	bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
	if (FID.isInvalid())
	return false;

	int Pos = PPEI.Position;
	if (Pos < 0) {
	if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
	assert(0 && "Out-of bounds loaded preprocessed entity");
	return false;
	}
	assert(ExternalSource && "No external source to load from");
	unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
	if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
	return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);

	// See if the external source can see if the entity is in the file without
	// deserializing it.
	Optional<bool> IsInFile =
	ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
	if (IsInFile.hasValue())
	return IsInFile.getValue();

	// The external source did not provide a definite answer, go and deserialize
	// the entity to check it.
	return isPreprocessedEntityIfInFileID(
	getLoadedPreprocessedEntity(LoadedIndex),
	FID, SourceMgr);
	}

	if (unsigned(Pos) >= PreprocessedEntities.size()) {
	assert(0 && "Out-of bounds local preprocessed entity");
	return false;
	}
	return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
	FID, SourceMgr);
	}

	/// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
	/// that source range \arg R encompasses.
	std::pair<int, int>
	PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
	assert(Range.isValid());
	assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));

	std::pair<unsigned, unsigned>
	Local = findLocalPreprocessedEntitiesInRange(Range);

	// Check if range spans local entities.
	if (!ExternalSource \|\| SourceMgr.isLocalSourceLocation(Range.getBegin()))
	return std::make_pair(Local.first, Local.second);

	std::pair<unsigned, unsigned>
	Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);

	// Check if range spans local entities.
	if (Loaded.first == Loaded.second)
	return std::make_pair(Local.first, Local.second);

	unsigned TotalLoaded = LoadedPreprocessedEntities.size();

	// Check if range spans loaded entities.
	if (Local.first == Local.second)
	return std::make_pair(int(Loaded.first)-TotalLoaded,
	int(Loaded.second)-TotalLoaded);

	// Range spands loaded and local entities.
	return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
	}

	std::pair<unsigned, unsigned>
	PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
	SourceRange Range) const {
	if (Range.isInvalid())
	return std::make_pair(0,0);
	assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));

	unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
	unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
	return std::make_pair(Begin, End);
	}

	namespace {

	template <SourceLocation (SourceRange::*getRangeLoc)() const>
	struct PPEntityComp {
	const SourceManager &SM;

	explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }

	bool operator()(PreprocessedEntity L, PreprocessedEntity R) const {
	SourceLocation LHS = getLoc(L);
	SourceLocation RHS = getLoc(R);
	return SM.isBeforeInTranslationUnit(LHS, RHS);
	}

	bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
	SourceLocation LHS = getLoc(L);
	return SM.isBeforeInTranslationUnit(LHS, RHS);
	}

	bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
	SourceLocation RHS = getLoc(R);
	return SM.isBeforeInTranslationUnit(LHS, RHS);
	}

	SourceLocation getLoc(PreprocessedEntity *PPE) const {
	SourceRange Range = PPE->getSourceRange();
	return (Range.*getRangeLoc)();
	}
	};

	}

	unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
	SourceLocation Loc) const {
	if (SourceMgr.isLoadedSourceLocation(Loc))
	return 0;

	size_t Count = PreprocessedEntities.size();
	size_t Half;
	std::vector<PreprocessedEntity *>::const_iterator
	First = PreprocessedEntities.begin();
	std::vector<PreprocessedEntity *>::const_iterator I;

	// Do a binary search manually instead of using std::lower_bound because
	// The end locations of entities may be unordered (when a macro expansion
	// is inside another macro argument), but for this case it is not important
	// whether we get the first macro expansion or its containing macro.
	while (Count > 0) {
	Half = Count/2;
	I = First;
	std::advance(I, Half);
	if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
	Loc)){
	First = I;
	++First;
	Count = Count - Half - 1;
	} else
	Count = Half;
	}

	return First - PreprocessedEntities.begin();
	}

	unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
	SourceLocation Loc) const {
	if (SourceMgr.isLoadedSourceLocation(Loc))
	return 0;

	std::vector<PreprocessedEntity *>::const_iterator
	I = std::upper_bound(PreprocessedEntities.begin(),
	PreprocessedEntities.end(),
	Loc,
	PPEntityComp<&SourceRange::getBegin>(SourceMgr));
	return I - PreprocessedEntities.begin();
	}

	PreprocessingRecord::PPEntityID
	PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
	assert(Entity);
	SourceLocation BeginLoc = Entity->getSourceRange().getBegin();

	if (isa<MacroDefinition>(Entity)) {
	assert((PreprocessedEntities.empty() \|\|
	!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
	PreprocessedEntities.back()->getSourceRange().getBegin())) &&
	"a macro definition was encountered out-of-order");
	PreprocessedEntities.push_back(Entity);
	return getPPEntityID(PreprocessedEntities.size()-1, /isLoaded=/false);
	}

	// Check normal case, this entity begin location is after the previous one.
	if (PreprocessedEntities.empty() \|\|
	!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
	PreprocessedEntities.back()->getSourceRange().getBegin())) {
	PreprocessedEntities.push_back(Entity);
	return getPPEntityID(PreprocessedEntities.size()-1, /isLoaded=/false);
	}

	// The entity's location is not after the previous one; this can happen with
	// include directives that form the filename using macros, e.g:
	// "#include MACRO(STUFF)"
	// or with macro expansions inside macro arguments where the arguments are
	// not expanded in the same order as listed, e.g:
	// \code
	// #define M1 1
	// #define M2 2
	// #define FM(x,y) y x
	// FM(M1, M2)
	// \endcode

	typedef std::vector<PreprocessedEntity *>::iterator pp_iter;

	// Usually there are few macro expansions when defining the filename, do a
	// linear search for a few entities.
	unsigned count = 0;
	for (pp_iter RI = PreprocessedEntities.end(),
	Begin = PreprocessedEntities.begin();
	RI != Begin && count < 4; --RI, ++count) {
	pp_iter I = RI;
	--I;
	if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
	(*I)->getSourceRange().getBegin())) {
	pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
	return getPPEntityID(insertI - PreprocessedEntities.begin(),
	/isLoaded=/false);
	}
	}

	// Linear search unsuccessful. Do a binary search.
	pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
	PreprocessedEntities.end(),
	BeginLoc,
	PPEntityComp<&SourceRange::getBegin>(SourceMgr));
	pp_iter insertI = PreprocessedEntities.insert(I, Entity);
	return getPPEntityID(insertI - PreprocessedEntities.begin(),
	/isLoaded=/false);
	}

	void PreprocessingRecord::SetExternalSource(
	ExternalPreprocessingRecordSource &Source) {
	assert(!ExternalSource &&
	"Preprocessing record already has an external source");
	ExternalSource = &Source;
	}

	unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
	unsigned Result = LoadedPreprocessedEntities.size();
	LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
	+ NumEntities);
	return Result;
	}

	void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
	MacroDefinition *Def) {
	MacroDefinitions[Macro] = Def;
	}

	/// \brief Retrieve the preprocessed entity at the given ID.
	PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
	if (PPID.ID < 0) {
	unsigned Index = -PPID.ID - 1;
	assert(Index < LoadedPreprocessedEntities.size() &&
	"Out-of bounds loaded preprocessed entity");
	return getLoadedPreprocessedEntity(Index);
	}

	if (PPID.ID == 0)
	return 0;
	unsigned Index = PPID.ID - 1;
	assert(Index < PreprocessedEntities.size() &&
	"Out-of bounds local preprocessed entity");
	return PreprocessedEntities[Index];
	}

	/// \brief Retrieve the loaded preprocessed entity at the given index.
	PreprocessedEntity *
	PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
	assert(Index < LoadedPreprocessedEntities.size() &&
	"Out-of bounds loaded preprocessed entity");
	assert(ExternalSource && "No external source to load from");
	PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
	if (!Entity) {
	Entity = ExternalSource->ReadPreprocessedEntity(Index);
	if (!Entity) // Failed to load.
	Entity = new (*this)
	PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
	}
	return Entity;
	}

	MacroDefinition PreprocessingRecord::findMacroDefinition(const MacroInfo MI) {
	llvm::DenseMap<const MacroInfo , MacroDefinition >::iterator Pos
	= MacroDefinitions.find(MI);
	if (Pos == MacroDefinitions.end())
	return 0;

	return Pos->second;
	}

	void PreprocessingRecord::addMacroExpansion(const Token &Id,
	const MacroInfo *MI,
	SourceRange Range) {
	// We don't record nested macro expansions.
	if (Id.getLocation().isMacroID())
	return;

	if (MI->isBuiltinMacro())
	addPreprocessedEntity(
	new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
	else if (MacroDefinition *Def = findMacroDefinition(MI))
	addPreprocessedEntity(
	new (*this) MacroExpansion(Def, Range));
	}

	void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
	const MacroDirective *MD) {
	// This is not actually a macro expansion but record it as a macro reference.
	if (MD)
	addMacroExpansion(MacroNameTok, MD->getInfo(), MacroNameTok.getLocation());
	}

	void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
	const MacroDirective *MD) {
	// This is not actually a macro expansion but record it as a macro reference.
	if (MD)
	addMacroExpansion(MacroNameTok, MD->getInfo(), MacroNameTok.getLocation());
	}

	void PreprocessingRecord::Defined(const Token &MacroNameTok,
	const MacroDirective *MD) {
	// This is not actually a macro expansion but record it as a macro reference.
	if (MD)
	addMacroExpansion(MacroNameTok, MD->getInfo(), MacroNameTok.getLocation());
	}

	void PreprocessingRecord::MacroExpands(const Token &Id,const MacroDirective *MD,
	SourceRange Range) {
	addMacroExpansion(Id, MD->getInfo(), Range);
	}

	void PreprocessingRecord::MacroDefined(const Token &Id,
	const MacroDirective *MD) {
	const MacroInfo *MI = MD->getInfo();
	SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
	MacroDefinition *Def
	= new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
	addPreprocessedEntity(Def);
	MacroDefinitions[MI] = Def;
	}

	void PreprocessingRecord::MacroUndefined(const Token &Id,
	const MacroDirective *MD) {
	// Note: MI may be null (when #undef'ining an undefined macro).
	if (MD)
	MacroDefinitions.erase(MD->getInfo());
	}

	void PreprocessingRecord::InclusionDirective(
	SourceLocation HashLoc,
	const clang::Token &IncludeTok,
	StringRef FileName,
	bool IsAngled,
	CharSourceRange FilenameRange,
	const FileEntry *File,
	StringRef SearchPath,
	StringRef RelativePath,
	const Module *Imported) {
	InclusionDirective::InclusionKind Kind = InclusionDirective::Include;

	switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
	case tok::pp_include:
	Kind = InclusionDirective::Include;
	break;

	case tok::pp_import:
	Kind = InclusionDirective::Import;
	break;

	case tok::pp_include_next:
	Kind = InclusionDirective::IncludeNext;
	break;

	case tok::pp___include_macros:
	Kind = InclusionDirective::IncludeMacros;
	break;

	default:
	llvm_unreachable("Unknown include directive kind");
	}

	SourceLocation EndLoc;
	if (!IsAngled) {
	EndLoc = FilenameRange.getBegin();
	} else {
	EndLoc = FilenameRange.getEnd();
	if (FilenameRange.isCharRange())
	EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
	// a token range.
	}
	clang::InclusionDirective *ID
	= new (this) clang::InclusionDirective(this, Kind, FileName, !IsAngled,
	(bool)Imported,
	File, SourceRange(HashLoc, EndLoc));
	addPreprocessedEntity(ID);
	}

	size_t PreprocessingRecord::getTotalMemory() const {
	return BumpAlloc.getTotalMemory()
	+ llvm::capacity_in_bytes(MacroDefinitions)
	+ llvm::capacity_in_bytes(PreprocessedEntities)
	+ llvm::capacity_in_bytes(LoadedPreprocessedEntities);
	}