contrib/llvm/tools/clang/lib/Lex/PreprocessingRecord.cpp

   1 //===--- PreprocessingRecord.cpp - Record of Preprocessing ------*- 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 //  This file implements the PreprocessingRecord class, which maintains a record
  11 //  of what occurred during preprocessing, and its helpers.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #include "clang/Lex/PreprocessingRecord.h"
  15 #include "clang/Lex/MacroInfo.h"
  16 #include "clang/Lex/Token.h"
  17 #include "llvm/Support/ErrorHandling.h"
  18 #include "llvm/Support/Capacity.h"
  19
  20 using namespace clang;
  21
  22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
  23
  24
  25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
  26                                        InclusionKind Kind,
  27                                        StringRef FileName,
  28                                        bool InQuotes, const FileEntry *File,
  29                                        SourceRange Range)
  30   : PreprocessingDirective(InclusionDirectiveKind, Range),
  31     InQuotes(InQuotes), Kind(Kind), File(File)
  32 {
  33   char *Memory
  34     = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
  35   memcpy(Memory, FileName.data(), FileName.size());
  36   Memory[FileName.size()] = 0;
  37   this->FileName = StringRef(Memory, FileName.size());
  38 }
  39
  40 PreprocessingRecord::PreprocessingRecord(SourceManager &SM,
  41                                          bool IncludeNestedMacroExpansions)
  42   : SourceMgr(SM), IncludeNestedMacroExpansions(IncludeNestedMacroExpansions),
  43     ExternalSource(0)
  44 {
  45 }
  46
  47 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
  48 /// that source range \arg R encompasses.
  49 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
  50 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
  51   if (Range.isInvalid())
  52     return std::make_pair(iterator(this, 0), iterator(this, 0));
  53   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
  54
  55   std::pair<unsigned, unsigned>
  56     Local = findLocalPreprocessedEntitiesInRange(Range);
  57
  58   // Check if range spans local entities.
  59   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
  60     return std::make_pair(iterator(this, Local.first),
  61                           iterator(this, Local.second));
  62
  63   std::pair<unsigned, unsigned>
  64     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
  65
  66   // Check if range spans local entities.
  67   if (Loaded.first == Loaded.second)
  68     return std::make_pair(iterator(this, Local.first),
  69                           iterator(this, Local.second));
  70
  71   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
  72
  73   // Check if range spans loaded entities.
  74   if (Local.first == Local.second)
  75     return std::make_pair(iterator(this, int(Loaded.first)-TotalLoaded),
  76                           iterator(this, int(Loaded.second)-TotalLoaded));
  77
  78   // Range spands loaded and local entities.
  79   return std::make_pair(iterator(this, int(Loaded.first)-TotalLoaded),
  80                         iterator(this, Local.second));
  81 }
  82
  83 std::pair<unsigned, unsigned>
  84 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
  85                                                       SourceRange Range) const {
  86   if (Range.isInvalid())
  87     return std::make_pair(0,0);
  88   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
  89
  90   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
  91   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
  92   return std::make_pair(Begin, End);
  93 }
  94
  95 namespace {
  96
  97 template <SourceLocation (SourceRange::*getRangeLoc)() const>
  98 struct PPEntityComp {
  99   const SourceManager &SM;
 100
 101   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
 102
 103   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
 104     SourceLocation LHS = getLoc(L);
 105     SourceLocation RHS = getLoc(R);
 106     return SM.isBeforeInTranslationUnit(LHS, RHS);
 107   }
 108
 109   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
 110     SourceLocation LHS = getLoc(L);
 111     return SM.isBeforeInTranslationUnit(LHS, RHS);
 112   }
 113
 114   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
 115     SourceLocation RHS = getLoc(R);
 116     return SM.isBeforeInTranslationUnit(LHS, RHS);
 117   }
 118
 119   SourceLocation getLoc(PreprocessedEntity *PPE) const {
 120     SourceRange Range = PPE->getSourceRange();
 121     return (Range.*getRangeLoc)();
 122   }
 123 };
 124
 125 }
 126
 127 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
 128                                                      SourceLocation Loc) const {
 129   if (SourceMgr.isLoadedSourceLocation(Loc))
 130     return 0;
 131
 132   size_t Count = PreprocessedEntities.size();
 133   size_t Half;
 134   std::vector<PreprocessedEntity *>::const_iterator
 135     First = PreprocessedEntities.begin();
 136   std::vector<PreprocessedEntity *>::const_iterator I;
 137
 138   // Do a binary search manually instead of using std::lower_bound because
 139   // The end locations of entities may be unordered (when a macro expansion
 140   // is inside another macro argument), but for this case it is not important
 141   // whether we get the first macro expansion or its containing macro.
 142   while (Count > 0) {
 143     Half = Count/2;
 144     I = First;
 145     std::advance(I, Half);
 146     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
 147                                             Loc)){
 148       First = I;
 149       ++First;
 150       Count = Count - Half - 1;
 151     } else
 152       Count = Half;
 153   }
 154
 155   return First - PreprocessedEntities.begin();
 156 }
 157
 158 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
 159                                                      SourceLocation Loc) const {
 160   if (SourceMgr.isLoadedSourceLocation(Loc))
 161     return 0;
 162
 163   std::vector<PreprocessedEntity *>::const_iterator
 164   I = std::upper_bound(PreprocessedEntities.begin(),
 165                        PreprocessedEntities.end(),
 166                        Loc,
 167                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
 168   return I - PreprocessedEntities.begin();
 169 }
 170
 171 void PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
 172   assert(Entity);
 173   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
 174
 175   // Check normal case, this entity begin location is after the previous one.
 176   if (PreprocessedEntities.empty() ||
 177       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
 178                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
 179     PreprocessedEntities.push_back(Entity);
 180     return;
 181   }
 182
 183   // The entity's location is not after the previous one; this can happen rarely
 184   // e.g. with "#include MACRO".
 185   // Iterate the entities vector in reverse until we find the right place to
 186   // insert the new entity.
 187   for (std::vector<PreprocessedEntity *>::iterator
 188          RI = PreprocessedEntities.end(), Begin = PreprocessedEntities.begin();
 189        RI != Begin; --RI) {
 190     std::vector<PreprocessedEntity *>::iterator I = RI;
 191     --I;
 192     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
 193                                            (*I)->getSourceRange().getBegin())) {
 194       PreprocessedEntities.insert(RI, Entity);
 195       return;
 196     }
 197   }
 198 }
 199
 200 void PreprocessingRecord::SetExternalSource(
 201                                     ExternalPreprocessingRecordSource &Source) {
 202   assert(!ExternalSource &&
 203          "Preprocessing record already has an external source");
 204   ExternalSource = &Source;
 205 }
 206
 207 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
 208   unsigned Result = LoadedPreprocessedEntities.size();
 209   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
 210                                     + NumEntities);
 211   return Result;
 212 }
 213
 214 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
 215                                                   PPEntityID PPID) {
 216   MacroDefinitions[Macro] = PPID;
 217 }
 218
 219 /// \brief Retrieve the preprocessed entity at the given ID.
 220 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
 221   if (PPID < 0) {
 222     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
 223            "Out-of bounds loaded preprocessed entity");
 224     return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
 225   }
 226   assert(unsigned(PPID) < PreprocessedEntities.size() &&
 227          "Out-of bounds local preprocessed entity");
 228   return PreprocessedEntities[PPID];
 229 }
 230
 231 /// \brief Retrieve the loaded preprocessed entity at the given index.
 232 PreprocessedEntity *
 233 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
 234   assert(Index < LoadedPreprocessedEntities.size() &&
 235          "Out-of bounds loaded preprocessed entity");
 236   assert(ExternalSource && "No external source to load from");
 237   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
 238   if (!Entity) {
 239     Entity = ExternalSource->ReadPreprocessedEntity(Index);
 240     if (!Entity) // Failed to load.
 241       Entity = new (*this)
 242          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
 243   }
 244   return Entity;
 245 }
 246
 247 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
 248   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
 249     = MacroDefinitions.find(MI);
 250   if (Pos == MacroDefinitions.end())
 251     return 0;
 252
 253   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
 254   if (Entity->isInvalid())
 255     return 0;
 256   return cast<MacroDefinition>(Entity);
 257 }
 258
 259 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
 260                                        SourceRange Range) {
 261   if (!IncludeNestedMacroExpansions && Id.getLocation().isMacroID())
 262     return;
 263
 264   if (MI->isBuiltinMacro())
 265     addPreprocessedEntity(
 266                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
 267   else if (MacroDefinition *Def = findMacroDefinition(MI))
 268     addPreprocessedEntity(
 269                        new (*this) MacroExpansion(Def, Range));
 270 }
 271
 272 void PreprocessingRecord::MacroDefined(const Token &Id,
 273                                        const MacroInfo *MI) {
 274   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
 275   MacroDefinition *Def
 276       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
 277   addPreprocessedEntity(Def);
 278   MacroDefinitions[MI] = getPPEntityID(PreprocessedEntities.size()-1,
 279                                        /*isLoaded=*/false);
 280 }
 281
 282 void PreprocessingRecord::MacroUndefined(const Token &Id,
 283                                          const MacroInfo *MI) {
 284   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
 285     = MacroDefinitions.find(MI);
 286   if (Pos != MacroDefinitions.end())
 287     MacroDefinitions.erase(Pos);
 288 }
 289
 290 void PreprocessingRecord::InclusionDirective(
 291     SourceLocation HashLoc,
 292     const clang::Token &IncludeTok,
 293     StringRef FileName,
 294     bool IsAngled,
 295     const FileEntry *File,
 296     clang::SourceLocation EndLoc,
 297     StringRef SearchPath,
 298     StringRef RelativePath) {
 299   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
 300
 301   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
 302   case tok::pp_include:
 303     Kind = InclusionDirective::Include;
 304     break;
 305
 306   case tok::pp_import:
 307     Kind = InclusionDirective::Import;
 308     break;
 309
 310   case tok::pp_include_next:
 311     Kind = InclusionDirective::IncludeNext;
 312     break;
 313
 314   case tok::pp___include_macros:
 315     Kind = InclusionDirective::IncludeMacros;
 316     break;
 317
 318   default:
 319     llvm_unreachable("Unknown include directive kind");
 320     return;
 321   }
 322
 323   clang::InclusionDirective *ID
 324     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
 325                                             File, SourceRange(HashLoc, EndLoc));
 326   addPreprocessedEntity(ID);
 327 }
 328
 329 size_t PreprocessingRecord::getTotalMemory() const {
 330   return BumpAlloc.getTotalMemory()
 331     + llvm::capacity_in_bytes(MacroDefinitions)
 332     + llvm::capacity_in_bytes(PreprocessedEntities)
 333     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
 334 }