contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp

   1 //===--- SourceManager.cpp - Track and cache source files -----------------===//
   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 SourceManager interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Basic/SourceManager.h"
  15 #include "clang/Basic/SourceManagerInternals.h"
  16 #include "clang/Basic/Diagnostic.h"
  17 #include "clang/Basic/FileManager.h"
  18 #include "llvm/ADT/StringSwitch.h"
  19 #include "llvm/ADT/Optional.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/Support/Compiler.h"
  22 #include "llvm/Support/MemoryBuffer.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 #include "llvm/Support/Path.h"
  25 #include "llvm/Support/Capacity.h"
  26 #include <algorithm>
  27 #include <string>
  28 #include <cstring>
  29 #include <sys/stat.h>
  30
  31 using namespace clang;
  32 using namespace SrcMgr;
  33 using llvm::MemoryBuffer;
  34
  35 //===----------------------------------------------------------------------===//
  36 // SourceManager Helper Classes
  37 //===----------------------------------------------------------------------===//
  38
  39 ContentCache::~ContentCache() {
  40   if (shouldFreeBuffer())
  41     delete Buffer.getPointer();
  42 }
  43
  44 /// getSizeBytesMapped - Returns the number of bytes actually mapped for this
  45 /// ContentCache. This can be 0 if the MemBuffer was not actually expanded.
  46 unsigned ContentCache::getSizeBytesMapped() const {
  47   return Buffer.getPointer() ? Buffer.getPointer()->getBufferSize() : 0;
  48 }
  49
  50 /// Returns the kind of memory used to back the memory buffer for
  51 /// this content cache.  This is used for performance analysis.
  52 llvm::MemoryBuffer::BufferKind ContentCache::getMemoryBufferKind() const {
  53   assert(Buffer.getPointer());
  54
  55   // Should be unreachable, but keep for sanity.
  56   if (!Buffer.getPointer())
  57     return llvm::MemoryBuffer::MemoryBuffer_Malloc;
  58
  59   const llvm::MemoryBuffer *buf = Buffer.getPointer();
  60   return buf->getBufferKind();
  61 }
  62
  63 /// getSize - Returns the size of the content encapsulated by this ContentCache.
  64 ///  This can be the size of the source file or the size of an arbitrary
  65 ///  scratch buffer.  If the ContentCache encapsulates a source file, that
  66 ///  file is not lazily brought in from disk to satisfy this query.
  67 unsigned ContentCache::getSize() const {
  68   return Buffer.getPointer() ? (unsigned) Buffer.getPointer()->getBufferSize()
  69                              : (unsigned) ContentsEntry->getSize();
  70 }
  71
  72 void ContentCache::replaceBuffer(const llvm::MemoryBuffer *B,
  73                                  bool DoNotFree) {
  74   if (B == Buffer.getPointer()) {
  75     assert(0 && "Replacing with the same buffer");
  76     Buffer.setInt(DoNotFree? DoNotFreeFlag : 0);
  77     return;
  78   }
  79
  80   if (shouldFreeBuffer())
  81     delete Buffer.getPointer();
  82   Buffer.setPointer(B);
  83   Buffer.setInt(DoNotFree? DoNotFreeFlag : 0);
  84 }
  85
  86 const llvm::MemoryBuffer *ContentCache::getBuffer(DiagnosticsEngine &Diag,
  87                                                   const SourceManager &SM,
  88                                                   SourceLocation Loc,
  89                                                   bool *Invalid) const {
  90   // Lazily create the Buffer for ContentCaches that wrap files.  If we already
  91   // computed it, just return what we have.
  92   if (Buffer.getPointer() || ContentsEntry == 0) {
  93     if (Invalid)
  94       *Invalid = isBufferInvalid();
  95
  96     return Buffer.getPointer();
  97   }
  98
  99   std::string ErrorStr;
 100   Buffer.setPointer(SM.getFileManager().getBufferForFile(ContentsEntry, &ErrorStr));
 101
 102   // If we were unable to open the file, then we are in an inconsistent
 103   // situation where the content cache referenced a file which no longer
 104   // exists. Most likely, we were using a stat cache with an invalid entry but
 105   // the file could also have been removed during processing. Since we can't
 106   // really deal with this situation, just create an empty buffer.
 107   //
 108   // FIXME: This is definitely not ideal, but our immediate clients can't
 109   // currently handle returning a null entry here. Ideally we should detect
 110   // that we are in an inconsistent situation and error out as quickly as
 111   // possible.
 112   if (!Buffer.getPointer()) {
 113     const StringRef FillStr("<<<MISSING SOURCE FILE>>>\n");
 114     Buffer.setPointer(MemoryBuffer::getNewMemBuffer(ContentsEntry->getSize(),
 115                                                     "<invalid>"));
 116     char *Ptr = const_cast<char*>(Buffer.getPointer()->getBufferStart());
 117     for (unsigned i = 0, e = ContentsEntry->getSize(); i != e; ++i)
 118       Ptr[i] = FillStr[i % FillStr.size()];
 119
 120     if (Diag.isDiagnosticInFlight())
 121       Diag.SetDelayedDiagnostic(diag::err_cannot_open_file,
 122                                 ContentsEntry->getName(), ErrorStr);
 123     else
 124       Diag.Report(Loc, diag::err_cannot_open_file)
 125         << ContentsEntry->getName() << ErrorStr;
 126
 127     Buffer.setInt(Buffer.getInt() | InvalidFlag);
 128
 129     if (Invalid) *Invalid = true;
 130     return Buffer.getPointer();
 131   }
 132
 133   // Check that the file's size is the same as in the file entry (which may
 134   // have come from a stat cache).
 135   if (getRawBuffer()->getBufferSize() != (size_t)ContentsEntry->getSize()) {
 136     if (Diag.isDiagnosticInFlight())
 137       Diag.SetDelayedDiagnostic(diag::err_file_modified,
 138                                 ContentsEntry->getName());
 139     else
 140       Diag.Report(Loc, diag::err_file_modified)
 141         << ContentsEntry->getName();
 142
 143     Buffer.setInt(Buffer.getInt() | InvalidFlag);
 144     if (Invalid) *Invalid = true;
 145     return Buffer.getPointer();
 146   }
 147
 148   // If the buffer is valid, check to see if it has a UTF Byte Order Mark
 149   // (BOM).  We only support UTF-8 with and without a BOM right now.  See
 150   // http://en.wikipedia.org/wiki/Byte_order_mark for more information.
 151   StringRef BufStr = Buffer.getPointer()->getBuffer();
 152   const char *InvalidBOM = llvm::StringSwitch<const char *>(BufStr)
 153     .StartsWith("\xFE\xFF", "UTF-16 (BE)")
 154     .StartsWith("\xFF\xFE", "UTF-16 (LE)")
 155     .StartsWith("\x00\x00\xFE\xFF", "UTF-32 (BE)")
 156     .StartsWith("\xFF\xFE\x00\x00", "UTF-32 (LE)")
 157     .StartsWith("\x2B\x2F\x76", "UTF-7")
 158     .StartsWith("\xF7\x64\x4C", "UTF-1")
 159     .StartsWith("\xDD\x73\x66\x73", "UTF-EBCDIC")
 160     .StartsWith("\x0E\xFE\xFF", "SDSU")
 161     .StartsWith("\xFB\xEE\x28", "BOCU-1")
 162     .StartsWith("\x84\x31\x95\x33", "GB-18030")
 163     .Default(0);
 164
 165   if (InvalidBOM) {
 166     Diag.Report(Loc, diag::err_unsupported_bom)
 167       << InvalidBOM << ContentsEntry->getName();
 168     Buffer.setInt(Buffer.getInt() | InvalidFlag);
 169   }
 170
 171   if (Invalid)
 172     *Invalid = isBufferInvalid();
 173
 174   return Buffer.getPointer();
 175 }
 176
 177 unsigned LineTableInfo::getLineTableFilenameID(StringRef Name) {
 178   // Look up the filename in the string table, returning the pre-existing value
 179   // if it exists.
 180   llvm::StringMapEntry<unsigned> &Entry =
 181     FilenameIDs.GetOrCreateValue(Name, ~0U);
 182   if (Entry.getValue() != ~0U)
 183     return Entry.getValue();
 184
 185   // Otherwise, assign this the next available ID.
 186   Entry.setValue(FilenamesByID.size());
 187   FilenamesByID.push_back(&Entry);
 188   return FilenamesByID.size()-1;
 189 }
 190
 191 /// AddLineNote - Add a line note to the line table that indicates that there
 192 /// is a #line at the specified FID/Offset location which changes the presumed
 193 /// location to LineNo/FilenameID.
 194 void LineTableInfo::AddLineNote(int FID, unsigned Offset,
 195                                 unsigned LineNo, int FilenameID) {
 196   std::vector<LineEntry> &Entries = LineEntries[FID];
 197
 198   assert((Entries.empty() || Entries.back().FileOffset < Offset) &&
 199          "Adding line entries out of order!");
 200
 201   SrcMgr::CharacteristicKind Kind = SrcMgr::C_User;
 202   unsigned IncludeOffset = 0;
 203
 204   if (!Entries.empty()) {
 205     // If this is a '#line 4' after '#line 42 "foo.h"', make sure to remember
 206     // that we are still in "foo.h".
 207     if (FilenameID == -1)
 208       FilenameID = Entries.back().FilenameID;
 209
 210     // If we are after a line marker that switched us to system header mode, or
 211     // that set #include information, preserve it.
 212     Kind = Entries.back().FileKind;
 213     IncludeOffset = Entries.back().IncludeOffset;
 214   }
 215
 216   Entries.push_back(LineEntry::get(Offset, LineNo, FilenameID, Kind,
 217                                    IncludeOffset));
 218 }
 219
 220 /// AddLineNote This is the same as the previous version of AddLineNote, but is
 221 /// used for GNU line markers.  If EntryExit is 0, then this doesn't change the
 222 /// presumed #include stack.  If it is 1, this is a file entry, if it is 2 then
 223 /// this is a file exit.  FileKind specifies whether this is a system header or
 224 /// extern C system header.
 225 void LineTableInfo::AddLineNote(int FID, unsigned Offset,
 226                                 unsigned LineNo, int FilenameID,
 227                                 unsigned EntryExit,
 228                                 SrcMgr::CharacteristicKind FileKind) {
 229   assert(FilenameID != -1 && "Unspecified filename should use other accessor");
 230
 231   std::vector<LineEntry> &Entries = LineEntries[FID];
 232
 233   assert((Entries.empty() || Entries.back().FileOffset < Offset) &&
 234          "Adding line entries out of order!");
 235
 236   unsigned IncludeOffset = 0;
 237   if (EntryExit == 0) {  // No #include stack change.
 238     IncludeOffset = Entries.empty() ? 0 : Entries.back().IncludeOffset;
 239   } else if (EntryExit == 1) {
 240     IncludeOffset = Offset-1;
 241   } else if (EntryExit == 2) {
 242     assert(!Entries.empty() && Entries.back().IncludeOffset &&
 243        "PPDirectives should have caught case when popping empty include stack");
 244
 245     // Get the include loc of the last entries' include loc as our include loc.
 246     IncludeOffset = 0;
 247     if (const LineEntry *PrevEntry =
 248           FindNearestLineEntry(FID, Entries.back().IncludeOffset))
 249       IncludeOffset = PrevEntry->IncludeOffset;
 250   }
 251
 252   Entries.push_back(LineEntry::get(Offset, LineNo, FilenameID, FileKind,
 253                                    IncludeOffset));
 254 }
 255
 256
 257 /// FindNearestLineEntry - Find the line entry nearest to FID that is before
 258 /// it.  If there is no line entry before Offset in FID, return null.
 259 const LineEntry *LineTableInfo::FindNearestLineEntry(int FID,
 260                                                      unsigned Offset) {
 261   const std::vector<LineEntry> &Entries = LineEntries[FID];
 262   assert(!Entries.empty() && "No #line entries for this FID after all!");
 263
 264   // It is very common for the query to be after the last #line, check this
 265   // first.
 266   if (Entries.back().FileOffset <= Offset)
 267     return &Entries.back();
 268
 269   // Do a binary search to find the maximal element that is still before Offset.
 270   std::vector<LineEntry>::const_iterator I =
 271     std::upper_bound(Entries.begin(), Entries.end(), Offset);
 272   if (I == Entries.begin()) return 0;
 273   return &*--I;
 274 }
 275
 276 /// \brief Add a new line entry that has already been encoded into
 277 /// the internal representation of the line table.
 278 void LineTableInfo::AddEntry(int FID,
 279                              const std::vector<LineEntry> &Entries) {
 280   LineEntries[FID] = Entries;
 281 }
 282
 283 /// getLineTableFilenameID - Return the uniqued ID for the specified filename.
 284 ///
 285 unsigned SourceManager::getLineTableFilenameID(StringRef Name) {
 286   if (LineTable == 0)
 287     LineTable = new LineTableInfo();
 288   return LineTable->getLineTableFilenameID(Name);
 289 }
 290
 291
 292 /// AddLineNote - Add a line note to the line table for the FileID and offset
 293 /// specified by Loc.  If FilenameID is -1, it is considered to be
 294 /// unspecified.
 295 void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo,
 296                                 int FilenameID) {
 297   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
 298
 299   bool Invalid = false;
 300   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
 301   if (!Entry.isFile() || Invalid)
 302     return;
 303
 304   const SrcMgr::FileInfo &FileInfo = Entry.getFile();
 305
 306   // Remember that this file has #line directives now if it doesn't already.
 307   const_cast<SrcMgr::FileInfo&>(FileInfo).setHasLineDirectives();
 308
 309   if (LineTable == 0)
 310     LineTable = new LineTableInfo();
 311   LineTable->AddLineNote(LocInfo.first.ID, LocInfo.second, LineNo, FilenameID);
 312 }
 313
 314 /// AddLineNote - Add a GNU line marker to the line table.
 315 void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo,
 316                                 int FilenameID, bool IsFileEntry,
 317                                 bool IsFileExit, bool IsSystemHeader,
 318                                 bool IsExternCHeader) {
 319   // If there is no filename and no flags, this is treated just like a #line,
 320   // which does not change the flags of the previous line marker.
 321   if (FilenameID == -1) {
 322     assert(!IsFileEntry && !IsFileExit && !IsSystemHeader && !IsExternCHeader &&
 323            "Can't set flags without setting the filename!");
 324     return AddLineNote(Loc, LineNo, FilenameID);
 325   }
 326
 327   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
 328
 329   bool Invalid = false;
 330   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
 331   if (!Entry.isFile() || Invalid)
 332     return;
 333
 334   const SrcMgr::FileInfo &FileInfo = Entry.getFile();
 335
 336   // Remember that this file has #line directives now if it doesn't already.
 337   const_cast<SrcMgr::FileInfo&>(FileInfo).setHasLineDirectives();
 338
 339   if (LineTable == 0)
 340     LineTable = new LineTableInfo();
 341
 342   SrcMgr::CharacteristicKind FileKind;
 343   if (IsExternCHeader)
 344     FileKind = SrcMgr::C_ExternCSystem;
 345   else if (IsSystemHeader)
 346     FileKind = SrcMgr::C_System;
 347   else
 348     FileKind = SrcMgr::C_User;
 349
 350   unsigned EntryExit = 0;
 351   if (IsFileEntry)
 352     EntryExit = 1;
 353   else if (IsFileExit)
 354     EntryExit = 2;
 355
 356   LineTable->AddLineNote(LocInfo.first.ID, LocInfo.second, LineNo, FilenameID,
 357                          EntryExit, FileKind);
 358 }
 359
 360 LineTableInfo &SourceManager::getLineTable() {
 361   if (LineTable == 0)
 362     LineTable = new LineTableInfo();
 363   return *LineTable;
 364 }
 365
 366 //===----------------------------------------------------------------------===//
 367 // Private 'Create' methods.
 368 //===----------------------------------------------------------------------===//
 369
 370 SourceManager::SourceManager(DiagnosticsEngine &Diag, FileManager &FileMgr)
 371   : Diag(Diag), FileMgr(FileMgr), OverridenFilesKeepOriginalName(true),
 372     ExternalSLocEntries(0), LineTable(0), NumLinearScans(0),
 373     NumBinaryProbes(0), FakeBufferForRecovery(0),
 374     FakeContentCacheForRecovery(0) {
 375   clearIDTables();
 376   Diag.setSourceManager(this);
 377 }
 378
 379 SourceManager::~SourceManager() {
 380   delete LineTable;
 381
 382   // Delete FileEntry objects corresponding to content caches.  Since the actual
 383   // content cache objects are bump pointer allocated, we just have to run the
 384   // dtors, but we call the deallocate method for completeness.
 385   for (unsigned i = 0, e = MemBufferInfos.size(); i != e; ++i) {
 386     if (MemBufferInfos[i]) {
 387       MemBufferInfos[i]->~ContentCache();
 388       ContentCacheAlloc.Deallocate(MemBufferInfos[i]);
 389     }
 390   }
 391   for (llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>::iterator
 392        I = FileInfos.begin(), E = FileInfos.end(); I != E; ++I) {
 393     if (I->second) {
 394       I->second->~ContentCache();
 395       ContentCacheAlloc.Deallocate(I->second);
 396     }
 397   }
 398
 399   delete FakeBufferForRecovery;
 400   delete FakeContentCacheForRecovery;
 401
 402   for (llvm::DenseMap<FileID, MacroArgsMap *>::iterator
 403          I = MacroArgsCacheMap.begin(),E = MacroArgsCacheMap.end(); I!=E; ++I) {
 404     delete I->second;
 405   }
 406 }
 407
 408 void SourceManager::clearIDTables() {
 409   MainFileID = FileID();
 410   LocalSLocEntryTable.clear();
 411   LoadedSLocEntryTable.clear();
 412   SLocEntryLoaded.clear();
 413   LastLineNoFileIDQuery = FileID();
 414   LastLineNoContentCache = 0;
 415   LastFileIDLookup = FileID();
 416
 417   if (LineTable)
 418     LineTable->clear();
 419
 420   // Use up FileID #0 as an invalid expansion.
 421   NextLocalOffset = 0;
 422   CurrentLoadedOffset = MaxLoadedOffset;
 423   createExpansionLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1);
 424 }
 425
 426 /// getOrCreateContentCache - Create or return a cached ContentCache for the
 427 /// specified file.
 428 const ContentCache *
 429 SourceManager::getOrCreateContentCache(const FileEntry *FileEnt) {
 430   assert(FileEnt && "Didn't specify a file entry to use?");
 431
 432   // Do we already have information about this file?
 433   ContentCache *&Entry = FileInfos[FileEnt];
 434   if (Entry) return Entry;
 435
 436   // Nope, create a new Cache entry.  Make sure it is at least 8-byte aligned
 437   // so that FileInfo can use the low 3 bits of the pointer for its own
 438   // nefarious purposes.
 439   unsigned EntryAlign = llvm::AlignOf<ContentCache>::Alignment;
 440   EntryAlign = std::max(8U, EntryAlign);
 441   Entry = ContentCacheAlloc.Allocate<ContentCache>(1, EntryAlign);
 442
 443   // If the file contents are overridden with contents from another file,
 444   // pass that file to ContentCache.
 445   llvm::DenseMap<const FileEntry *, const FileEntry *>::iterator
 446       overI = OverriddenFiles.find(FileEnt);
 447   if (overI == OverriddenFiles.end())
 448     new (Entry) ContentCache(FileEnt);
 449   else
 450     new (Entry) ContentCache(OverridenFilesKeepOriginalName ? FileEnt
 451                                                             : overI->second,
 452                              overI->second);
 453
 454   return Entry;
 455 }
 456
 457
 458 /// createMemBufferContentCache - Create a new ContentCache for the specified
 459 ///  memory buffer.  This does no caching.
 460 const ContentCache*
 461 SourceManager::createMemBufferContentCache(const MemoryBuffer *Buffer) {
 462   // Add a new ContentCache to the MemBufferInfos list and return it.  Make sure
 463   // it is at least 8-byte aligned so that FileInfo can use the low 3 bits of
 464   // the pointer for its own nefarious purposes.
 465   unsigned EntryAlign = llvm::AlignOf<ContentCache>::Alignment;
 466   EntryAlign = std::max(8U, EntryAlign);
 467   ContentCache *Entry = ContentCacheAlloc.Allocate<ContentCache>(1, EntryAlign);
 468   new (Entry) ContentCache();
 469   MemBufferInfos.push_back(Entry);
 470   Entry->setBuffer(Buffer);
 471   return Entry;
 472 }
 473
 474 const SrcMgr::SLocEntry &SourceManager::loadSLocEntry(unsigned Index,
 475                                                       bool *Invalid) const {
 476   assert(!SLocEntryLoaded[Index]);
 477   if (ExternalSLocEntries->ReadSLocEntry(-(static_cast<int>(Index) + 2))) {
 478     if (Invalid)
 479       *Invalid = true;
 480     // If the file of the SLocEntry changed we could still have loaded it.
 481     if (!SLocEntryLoaded[Index]) {
 482       // Try to recover; create a SLocEntry so the rest of clang can handle it.
 483       LoadedSLocEntryTable[Index] = SLocEntry::get(0,
 484                                  FileInfo::get(SourceLocation(),
 485                                                getFakeContentCacheForRecovery(),
 486                                                SrcMgr::C_User));
 487     }
 488   }
 489
 490   return LoadedSLocEntryTable[Index];
 491 }
 492
 493 std::pair<int, unsigned>
 494 SourceManager::AllocateLoadedSLocEntries(unsigned NumSLocEntries,
 495                                          unsigned TotalSize) {
 496   assert(ExternalSLocEntries && "Don't have an external sloc source");
 497   LoadedSLocEntryTable.resize(LoadedSLocEntryTable.size() + NumSLocEntries);
 498   SLocEntryLoaded.resize(LoadedSLocEntryTable.size());
 499   CurrentLoadedOffset -= TotalSize;
 500   assert(CurrentLoadedOffset >= NextLocalOffset && "Out of source locations");
 501   int ID = LoadedSLocEntryTable.size();
 502   return std::make_pair(-ID - 1, CurrentLoadedOffset);
 503 }
 504
 505 /// \brief As part of recovering from missing or changed content, produce a
 506 /// fake, non-empty buffer.
 507 const llvm::MemoryBuffer *SourceManager::getFakeBufferForRecovery() const {
 508   if (!FakeBufferForRecovery)
 509     FakeBufferForRecovery
 510       = llvm::MemoryBuffer::getMemBuffer("<<<INVALID BUFFER>>");
 511
 512   return FakeBufferForRecovery;
 513 }
 514
 515 /// \brief As part of recovering from missing or changed content, produce a
 516 /// fake content cache.
 517 const SrcMgr::ContentCache *
 518 SourceManager::getFakeContentCacheForRecovery() const {
 519   if (!FakeContentCacheForRecovery) {
 520     FakeContentCacheForRecovery = new ContentCache();
 521     FakeContentCacheForRecovery->replaceBuffer(getFakeBufferForRecovery(),
 522                                                /*DoNotFree=*/true);
 523   }
 524   return FakeContentCacheForRecovery;
 525 }
 526
 527 //===----------------------------------------------------------------------===//
 528 // Methods to create new FileID's and macro expansions.
 529 //===----------------------------------------------------------------------===//
 530
 531 /// createFileID - Create a new FileID for the specified ContentCache and
 532 /// include position.  This works regardless of whether the ContentCache
 533 /// corresponds to a file or some other input source.
 534 FileID SourceManager::createFileID(const ContentCache *File,
 535                                    SourceLocation IncludePos,
 536                                    SrcMgr::CharacteristicKind FileCharacter,
 537                                    int LoadedID, unsigned LoadedOffset) {
 538   if (LoadedID < 0) {
 539     assert(LoadedID != -1 && "Loading sentinel FileID");
 540     unsigned Index = unsigned(-LoadedID) - 2;
 541     assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
 542     assert(!SLocEntryLoaded[Index] && "FileID already loaded");
 543     LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset,
 544         FileInfo::get(IncludePos, File, FileCharacter));
 545     SLocEntryLoaded[Index] = true;
 546     return FileID::get(LoadedID);
 547   }
 548   LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset,
 549                                                FileInfo::get(IncludePos, File,
 550                                                              FileCharacter)));
 551   unsigned FileSize = File->getSize();
 552   assert(NextLocalOffset + FileSize + 1 > NextLocalOffset &&
 553          NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset &&
 554          "Ran out of source locations!");
 555   // We do a +1 here because we want a SourceLocation that means "the end of the
 556   // file", e.g. for the "no newline at the end of the file" diagnostic.
 557   NextLocalOffset += FileSize + 1;
 558
 559   // Set LastFileIDLookup to the newly created file.  The next getFileID call is
 560   // almost guaranteed to be from that file.
 561   FileID FID = FileID::get(LocalSLocEntryTable.size()-1);
 562   return LastFileIDLookup = FID;
 563 }
 564
 565 SourceLocation
 566 SourceManager::createMacroArgExpansionLoc(SourceLocation SpellingLoc,
 567                                           SourceLocation ExpansionLoc,
 568                                           unsigned TokLength) {
 569   ExpansionInfo Info = ExpansionInfo::createForMacroArg(SpellingLoc,
 570                                                         ExpansionLoc);
 571   return createExpansionLocImpl(Info, TokLength);
 572 }
 573
 574 SourceLocation
 575 SourceManager::createExpansionLoc(SourceLocation SpellingLoc,
 576                                   SourceLocation ExpansionLocStart,
 577                                   SourceLocation ExpansionLocEnd,
 578                                   unsigned TokLength,
 579                                   int LoadedID,
 580                                   unsigned LoadedOffset) {
 581   ExpansionInfo Info = ExpansionInfo::create(SpellingLoc, ExpansionLocStart,
 582                                              ExpansionLocEnd);
 583   return createExpansionLocImpl(Info, TokLength, LoadedID, LoadedOffset);
 584 }
 585
 586 SourceLocation
 587 SourceManager::createExpansionLocImpl(const ExpansionInfo &Info,
 588                                       unsigned TokLength,
 589                                       int LoadedID,
 590                                       unsigned LoadedOffset) {
 591   if (LoadedID < 0) {
 592     assert(LoadedID != -1 && "Loading sentinel FileID");
 593     unsigned Index = unsigned(-LoadedID) - 2;
 594     assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
 595     assert(!SLocEntryLoaded[Index] && "FileID already loaded");
 596     LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, Info);
 597     SLocEntryLoaded[Index] = true;
 598     return SourceLocation::getMacroLoc(LoadedOffset);
 599   }
 600   LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info));
 601   assert(NextLocalOffset + TokLength + 1 > NextLocalOffset &&
 602          NextLocalOffset + TokLength + 1 <= CurrentLoadedOffset &&
 603          "Ran out of source locations!");
 604   // See createFileID for that +1.
 605   NextLocalOffset += TokLength + 1;
 606   return SourceLocation::getMacroLoc(NextLocalOffset - (TokLength + 1));
 607 }
 608
 609 const llvm::MemoryBuffer *
 610 SourceManager::getMemoryBufferForFile(const FileEntry *File,
 611                                       bool *Invalid) {
 612   const SrcMgr::ContentCache *IR = getOrCreateContentCache(File);
 613   assert(IR && "getOrCreateContentCache() cannot return NULL");
 614   return IR->getBuffer(Diag, *this, SourceLocation(), Invalid);
 615 }
 616
 617 void SourceManager::overrideFileContents(const FileEntry *SourceFile,
 618                                          const llvm::MemoryBuffer *Buffer,
 619                                          bool DoNotFree) {
 620   const SrcMgr::ContentCache *IR = getOrCreateContentCache(SourceFile);
 621   assert(IR && "getOrCreateContentCache() cannot return NULL");
 622
 623   const_cast<SrcMgr::ContentCache *>(IR)->replaceBuffer(Buffer, DoNotFree);
 624   const_cast<SrcMgr::ContentCache *>(IR)->BufferOverridden = true;
 625 }
 626
 627 void SourceManager::overrideFileContents(const FileEntry *SourceFile,
 628                                          const FileEntry *NewFile) {
 629   assert(SourceFile->getSize() == NewFile->getSize() &&
 630          "Different sizes, use the FileManager to create a virtual file with "
 631          "the correct size");
 632   assert(FileInfos.count(SourceFile) == 0 &&
 633          "This function should be called at the initialization stage, before "
 634          "any parsing occurs.");
 635   OverriddenFiles[SourceFile] = NewFile;
 636 }
 637
 638 StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const {
 639   bool MyInvalid = false;
 640   const SLocEntry &SLoc = getSLocEntry(FID, &MyInvalid);
 641   if (!SLoc.isFile() || MyInvalid) {
 642     if (Invalid)
 643       *Invalid = true;
 644     return "<<<<<INVALID SOURCE LOCATION>>>>>";
 645   }
 646
 647   const llvm::MemoryBuffer *Buf
 648     = SLoc.getFile().getContentCache()->getBuffer(Diag, *this, SourceLocation(),
 649                                                   &MyInvalid);
 650   if (Invalid)
 651     *Invalid = MyInvalid;
 652
 653   if (MyInvalid)
 654     return "<<<<<INVALID SOURCE LOCATION>>>>>";
 655
 656   return Buf->getBuffer();
 657 }
 658
 659 //===----------------------------------------------------------------------===//
 660 // SourceLocation manipulation methods.
 661 //===----------------------------------------------------------------------===//
 662
 663 /// \brief Return the FileID for a SourceLocation.
 664 ///
 665 /// This is the cache-miss path of getFileID. Not as hot as that function, but
 666 /// still very important. It is responsible for finding the entry in the
 667 /// SLocEntry tables that contains the specified location.
 668 FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
 669   if (!SLocOffset)
 670     return FileID::get(0);
 671
 672   // Now it is time to search for the correct file. See where the SLocOffset
 673   // sits in the global view and consult local or loaded buffers for it.
 674   if (SLocOffset < NextLocalOffset)
 675     return getFileIDLocal(SLocOffset);
 676   return getFileIDLoaded(SLocOffset);
 677 }
 678
 679 /// \brief Return the FileID for a SourceLocation with a low offset.
 680 ///
 681 /// This function knows that the SourceLocation is in a local buffer, not a
 682 /// loaded one.
 683 FileID SourceManager::getFileIDLocal(unsigned SLocOffset) const {
 684   assert(SLocOffset < NextLocalOffset && "Bad function choice");
 685
 686   // After the first and second level caches, I see two common sorts of
 687   // behavior: 1) a lot of searched FileID's are "near" the cached file
 688   // location or are "near" the cached expansion location. 2) others are just
 689   // completely random and may be a very long way away.
 690   //
 691   // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
 692   // then we fall back to a less cache efficient, but more scalable, binary
 693   // search to find the location.
 694
 695   // See if this is near the file point - worst case we start scanning from the
 696   // most newly created FileID.
 697   std::vector<SrcMgr::SLocEntry>::const_iterator I;
 698
 699   if (LastFileIDLookup.ID < 0 ||
 700       LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
 701     // Neither loc prunes our search.
 702     I = LocalSLocEntryTable.end();
 703   } else {
 704     // Perhaps it is near the file point.
 705     I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID;
 706   }
 707
 708   // Find the FileID that contains this.  "I" is an iterator that points to a
 709   // FileID whose offset is known to be larger than SLocOffset.
 710   unsigned NumProbes = 0;
 711   while (1) {
 712     --I;
 713     if (I->getOffset() <= SLocOffset) {
 714       FileID Res = FileID::get(int(I - LocalSLocEntryTable.begin()));
 715
 716       // If this isn't an expansion, remember it.  We have good locality across
 717       // FileID lookups.
 718       if (!I->isExpansion())
 719         LastFileIDLookup = Res;
 720       NumLinearScans += NumProbes+1;
 721       return Res;
 722     }
 723     if (++NumProbes == 8)
 724       break;
 725   }
 726
 727   // Convert "I" back into an index.  We know that it is an entry whose index is
 728   // larger than the offset we are looking for.
 729   unsigned GreaterIndex = I - LocalSLocEntryTable.begin();
 730   // LessIndex - This is the lower bound of the range that we're searching.
 731   // We know that the offset corresponding to the FileID is is less than
 732   // SLocOffset.
 733   unsigned LessIndex = 0;
 734   NumProbes = 0;
 735   while (1) {
 736     bool Invalid = false;
 737     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
 738     unsigned MidOffset = getLocalSLocEntry(MiddleIndex, &Invalid).getOffset();
 739     if (Invalid)
 740       return FileID::get(0);
 741
 742     ++NumProbes;
 743
 744     // If the offset of the midpoint is too large, chop the high side of the
 745     // range to the midpoint.
 746     if (MidOffset > SLocOffset) {
 747       GreaterIndex = MiddleIndex;
 748       continue;
 749     }
 750
 751     // If the middle index contains the value, succeed and return.
 752     // FIXME: This could be made faster by using a function that's aware of
 753     // being in the local area.
 754     if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) {
 755       FileID Res = FileID::get(MiddleIndex);
 756
 757       // If this isn't a macro expansion, remember it.  We have good locality
 758       // across FileID lookups.
 759       if (!LocalSLocEntryTable[MiddleIndex].isExpansion())
 760         LastFileIDLookup = Res;
 761       NumBinaryProbes += NumProbes;
 762       return Res;
 763     }
 764
 765     // Otherwise, move the low-side up to the middle index.
 766     LessIndex = MiddleIndex;
 767   }
 768 }
 769
 770 /// \brief Return the FileID for a SourceLocation with a high offset.
 771 ///
 772 /// This function knows that the SourceLocation is in a loaded buffer, not a
 773 /// local one.
 774 FileID SourceManager::getFileIDLoaded(unsigned SLocOffset) const {
 775   // Sanity checking, otherwise a bug may lead to hanging in release build.
 776   if (SLocOffset < CurrentLoadedOffset) {
 777     assert(0 && "Invalid SLocOffset or bad function choice");
 778     return FileID();
 779   }
 780
 781   // Essentially the same as the local case, but the loaded array is sorted
 782   // in the other direction.
 783
 784   // First do a linear scan from the last lookup position, if possible.
 785   unsigned I;
 786   int LastID = LastFileIDLookup.ID;
 787   if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
 788     I = 0;
 789   else
 790     I = (-LastID - 2) + 1;
 791
 792   unsigned NumProbes;
 793   for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
 794     // Make sure the entry is loaded!
 795     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I);
 796     if (E.getOffset() <= SLocOffset) {
 797       FileID Res = FileID::get(-int(I) - 2);
 798
 799       if (!E.isExpansion())
 800         LastFileIDLookup = Res;
 801       NumLinearScans += NumProbes + 1;
 802       return Res;
 803     }
 804   }
 805
 806   // Linear scan failed. Do the binary search. Note the reverse sorting of the
 807   // table: GreaterIndex is the one where the offset is greater, which is
 808   // actually a lower index!
 809   unsigned GreaterIndex = I;
 810   unsigned LessIndex = LoadedSLocEntryTable.size();
 811   NumProbes = 0;
 812   while (1) {
 813     ++NumProbes;
 814     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
 815     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex);
 816
 817     ++NumProbes;
 818
 819     if (E.getOffset() > SLocOffset) {
 820       GreaterIndex = MiddleIndex;
 821       continue;
 822     }
 823
 824     if (isOffsetInFileID(FileID::get(-int(MiddleIndex) - 2), SLocOffset)) {
 825       FileID Res = FileID::get(-int(MiddleIndex) - 2);
 826       if (!E.isExpansion())
 827         LastFileIDLookup = Res;
 828       NumBinaryProbes += NumProbes;
 829       return Res;
 830     }
 831
 832     LessIndex = MiddleIndex;
 833   }
 834 }
 835
 836 SourceLocation SourceManager::
 837 getExpansionLocSlowCase(SourceLocation Loc) const {
 838   do {
 839     // Note: If Loc indicates an offset into a token that came from a macro
 840     // expansion (e.g. the 5th character of the token) we do not want to add
 841     // this offset when going to the expansion location.  The expansion
 842     // location is the macro invocation, which the offset has nothing to do
 843     // with.  This is unlike when we get the spelling loc, because the offset
 844     // directly correspond to the token whose spelling we're inspecting.
 845     Loc = getSLocEntry(getFileID(Loc)).getExpansion().getExpansionLocStart();
 846   } while (!Loc.isFileID());
 847
 848   return Loc;
 849 }
 850
 851 SourceLocation SourceManager::getSpellingLocSlowCase(SourceLocation Loc) const {
 852   do {
 853     std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
 854     Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc();
 855     Loc = Loc.getLocWithOffset(LocInfo.second);
 856   } while (!Loc.isFileID());
 857   return Loc;
 858 }
 859
 860 SourceLocation SourceManager::getFileLocSlowCase(SourceLocation Loc) const {
 861   do {
 862     if (isMacroArgExpansion(Loc))
 863       Loc = getImmediateSpellingLoc(Loc);
 864     else
 865       Loc = getImmediateExpansionRange(Loc).first;
 866   } while (!Loc.isFileID());
 867   return Loc;
 868 }
 869
 870
 871 std::pair<FileID, unsigned>
 872 SourceManager::getDecomposedExpansionLocSlowCase(
 873                                              const SrcMgr::SLocEntry *E) const {
 874   // If this is an expansion record, walk through all the expansion points.
 875   FileID FID;
 876   SourceLocation Loc;
 877   unsigned Offset;
 878   do {
 879     Loc = E->getExpansion().getExpansionLocStart();
 880
 881     FID = getFileID(Loc);
 882     E = &getSLocEntry(FID);
 883     Offset = Loc.getOffset()-E->getOffset();
 884   } while (!Loc.isFileID());
 885
 886   return std::make_pair(FID, Offset);
 887 }
 888
 889 std::pair<FileID, unsigned>
 890 SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E,
 891                                                 unsigned Offset) const {
 892   // If this is an expansion record, walk through all the expansion points.
 893   FileID FID;
 894   SourceLocation Loc;
 895   do {
 896     Loc = E->getExpansion().getSpellingLoc();
 897     Loc = Loc.getLocWithOffset(Offset);
 898
 899     FID = getFileID(Loc);
 900     E = &getSLocEntry(FID);
 901     Offset = Loc.getOffset()-E->getOffset();
 902   } while (!Loc.isFileID());
 903
 904   return std::make_pair(FID, Offset);
 905 }
 906
 907 /// getImmediateSpellingLoc - Given a SourceLocation object, return the
 908 /// spelling location referenced by the ID.  This is the first level down
 909 /// towards the place where the characters that make up the lexed token can be
 910 /// found.  This should not generally be used by clients.
 911 SourceLocation SourceManager::getImmediateSpellingLoc(SourceLocation Loc) const{
 912   if (Loc.isFileID()) return Loc;
 913   std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
 914   Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc();
 915   return Loc.getLocWithOffset(LocInfo.second);
 916 }
 917
 918
 919 /// getImmediateExpansionRange - Loc is required to be an expansion location.
 920 /// Return the start/end of the expansion information.
 921 std::pair<SourceLocation,SourceLocation>
 922 SourceManager::getImmediateExpansionRange(SourceLocation Loc) const {
 923   assert(Loc.isMacroID() && "Not a macro expansion loc!");
 924   const ExpansionInfo &Expansion = getSLocEntry(getFileID(Loc)).getExpansion();
 925   return Expansion.getExpansionLocRange();
 926 }
 927
 928 /// getExpansionRange - Given a SourceLocation object, return the range of
 929 /// tokens covered by the expansion in the ultimate file.
 930 std::pair<SourceLocation,SourceLocation>
 931 SourceManager::getExpansionRange(SourceLocation Loc) const {
 932   if (Loc.isFileID()) return std::make_pair(Loc, Loc);
 933
 934   std::pair<SourceLocation,SourceLocation> Res =
 935     getImmediateExpansionRange(Loc);
 936
 937   // Fully resolve the start and end locations to their ultimate expansion
 938   // points.
 939   while (!Res.first.isFileID())
 940     Res.first = getImmediateExpansionRange(Res.first).first;
 941   while (!Res.second.isFileID())
 942     Res.second = getImmediateExpansionRange(Res.second).second;
 943   return Res;
 944 }
 945
 946 bool SourceManager::isMacroArgExpansion(SourceLocation Loc) const {
 947   if (!Loc.isMacroID()) return false;
 948
 949   FileID FID = getFileID(Loc);
 950   const SrcMgr::SLocEntry *E = &getSLocEntry(FID);
 951   const SrcMgr::ExpansionInfo &Expansion = E->getExpansion();
 952   return Expansion.isMacroArgExpansion();
 953 }
 954
 955
 956 //===----------------------------------------------------------------------===//
 957 // Queries about the code at a SourceLocation.
 958 //===----------------------------------------------------------------------===//
 959
 960 /// getCharacterData - Return a pointer to the start of the specified location
 961 /// in the appropriate MemoryBuffer.
 962 const char *SourceManager::getCharacterData(SourceLocation SL,
 963                                             bool *Invalid) const {
 964   // Note that this is a hot function in the getSpelling() path, which is
 965   // heavily used by -E mode.
 966   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(SL);
 967
 968   // Note that calling 'getBuffer()' may lazily page in a source file.
 969   bool CharDataInvalid = false;
 970   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &CharDataInvalid);
 971   if (CharDataInvalid || !Entry.isFile()) {
 972     if (Invalid)
 973       *Invalid = true;
 974
 975     return "<<<<INVALID BUFFER>>>>";
 976   }
 977   const llvm::MemoryBuffer *Buffer
 978     = Entry.getFile().getContentCache()
 979                   ->getBuffer(Diag, *this, SourceLocation(), &CharDataInvalid);
 980   if (Invalid)
 981     *Invalid = CharDataInvalid;
 982   return Buffer->getBufferStart() + (CharDataInvalid? 0 : LocInfo.second);
 983 }
 984
 985
 986 /// getColumnNumber - Return the column # for the specified file position.
 987 /// this is significantly cheaper to compute than the line number.
 988 unsigned SourceManager::getColumnNumber(FileID FID, unsigned FilePos,
 989                                         bool *Invalid) const {
 990   bool MyInvalid = false;
 991   const llvm::MemoryBuffer *MemBuf = getBuffer(FID, &MyInvalid);
 992   if (Invalid)
 993     *Invalid = MyInvalid;
 994
 995   if (MyInvalid)
 996     return 1;
 997
 998   if (FilePos >= MemBuf->getBufferSize()) {
 999     if (Invalid)
1000       *Invalid = MyInvalid;
1001     return 1;
1002   }
1003
1004   const char *Buf = MemBuf->getBufferStart();
1005   unsigned LineStart = FilePos;
1006   while (LineStart && Buf[LineStart-1] != '\n' && Buf[LineStart-1] != '\r')
1007     --LineStart;
1008   return FilePos-LineStart+1;
1009 }
1010
1011 // isInvalid - Return the result of calling loc.isInvalid(), and
1012 // if Invalid is not null, set its value to same.
1013 static bool isInvalid(SourceLocation Loc, bool *Invalid) {
1014   bool MyInvalid = Loc.isInvalid();
1015   if (Invalid)
1016     *Invalid = MyInvalid;
1017   return MyInvalid;
1018 }
1019
1020 unsigned SourceManager::getSpellingColumnNumber(SourceLocation Loc,
1021                                                 bool *Invalid) const {
1022   if (isInvalid(Loc, Invalid)) return 0;
1023   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc);
1024   return getColumnNumber(LocInfo.first, LocInfo.second, Invalid);
1025 }
1026
1027 unsigned SourceManager::getExpansionColumnNumber(SourceLocation Loc,
1028                                                  bool *Invalid) const {
1029   if (isInvalid(Loc, Invalid)) return 0;
1030   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1031   return getColumnNumber(LocInfo.first, LocInfo.second, Invalid);
1032 }
1033
1034 unsigned SourceManager::getPresumedColumnNumber(SourceLocation Loc,
1035                                                 bool *Invalid) const {
1036   if (isInvalid(Loc, Invalid)) return 0;
1037   return getPresumedLoc(Loc).getColumn();
1038 }
1039
1040 #ifdef __SSE2__
1041 #include <emmintrin.h>
1042 #endif
1043
1044 static LLVM_ATTRIBUTE_NOINLINE void
1045 ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
1046                    llvm::BumpPtrAllocator &Alloc,
1047                    const SourceManager &SM, bool &Invalid);
1048 static void ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
1049                                llvm::BumpPtrAllocator &Alloc,
1050                                const SourceManager &SM, bool &Invalid) {
1051   // Note that calling 'getBuffer()' may lazily page in the file.
1052   const MemoryBuffer *Buffer = FI->getBuffer(Diag, SM, SourceLocation(),
1053                                              &Invalid);
1054   if (Invalid)
1055     return;
1056
1057   // Find the file offsets of all of the *physical* source lines.  This does
1058   // not look at trigraphs, escaped newlines, or anything else tricky.
1059   SmallVector<unsigned, 256> LineOffsets;
1060
1061   // Line #1 starts at char 0.
1062   LineOffsets.push_back(0);
1063
1064   const unsigned char *Buf = (const unsigned char *)Buffer->getBufferStart();
1065   const unsigned char *End = (const unsigned char *)Buffer->getBufferEnd();
1066   unsigned Offs = 0;
1067   while (1) {
1068     // Skip over the contents of the line.
1069     const unsigned char *NextBuf = (const unsigned char *)Buf;
1070
1071 #ifdef __SSE2__
1072     // Try to skip to the next newline using SSE instructions. This is very
1073     // performance sensitive for programs with lots of diagnostics and in -E
1074     // mode.
1075     __m128i CRs = _mm_set1_epi8('\r');
1076     __m128i LFs = _mm_set1_epi8('\n');
1077
1078     // First fix up the alignment to 16 bytes.
1079     while (((uintptr_t)NextBuf & 0xF) != 0) {
1080       if (*NextBuf == '\n' || *NextBuf == '\r' || *NextBuf == '\0')
1081         goto FoundSpecialChar;
1082       ++NextBuf;
1083     }
1084
1085     // Scan 16 byte chunks for '\r' and '\n'. Ignore '\0'.
1086     while (NextBuf+16 <= End) {
1087       __m128i Chunk = *(__m128i*)NextBuf;
1088       __m128i Cmp = _mm_or_si128(_mm_cmpeq_epi8(Chunk, CRs),
1089                                  _mm_cmpeq_epi8(Chunk, LFs));
1090       unsigned Mask = _mm_movemask_epi8(Cmp);
1091
1092       // If we found a newline, adjust the pointer and jump to the handling code.
1093       if (Mask != 0) {
1094         NextBuf += llvm::CountTrailingZeros_32(Mask);
1095         goto FoundSpecialChar;
1096       }
1097       NextBuf += 16;
1098     }
1099 #endif
1100
1101     while (*NextBuf != '\n' && *NextBuf != '\r' && *NextBuf != '\0')
1102       ++NextBuf;
1103
1104 #ifdef __SSE2__
1105 FoundSpecialChar:
1106 #endif
1107     Offs += NextBuf-Buf;
1108     Buf = NextBuf;
1109
1110     if (Buf[0] == '\n' || Buf[0] == '\r') {
1111       // If this is \n\r or \r\n, skip both characters.
1112       if ((Buf[1] == '\n' || Buf[1] == '\r') && Buf[0] != Buf[1])
1113         ++Offs, ++Buf;
1114       ++Offs, ++Buf;
1115       LineOffsets.push_back(Offs);
1116     } else {
1117       // Otherwise, this is a null.  If end of file, exit.
1118       if (Buf == End) break;
1119       // Otherwise, skip the null.
1120       ++Offs, ++Buf;
1121     }
1122   }
1123
1124   // Copy the offsets into the FileInfo structure.
1125   FI->NumLines = LineOffsets.size();
1126   FI->SourceLineCache = Alloc.Allocate<unsigned>(LineOffsets.size());
1127   std::copy(LineOffsets.begin(), LineOffsets.end(), FI->SourceLineCache);
1128 }
1129
1130 /// getLineNumber - Given a SourceLocation, return the spelling line number
1131 /// for the position indicated.  This requires building and caching a table of
1132 /// line offsets for the MemoryBuffer, so this is not cheap: use only when
1133 /// about to emit a diagnostic.
1134 unsigned SourceManager::getLineNumber(FileID FID, unsigned FilePos,
1135                                       bool *Invalid) const {
1136   if (FID.isInvalid()) {
1137     if (Invalid)
1138       *Invalid = true;
1139     return 1;
1140   }
1141
1142   ContentCache *Content;
1143   if (LastLineNoFileIDQuery == FID)
1144     Content = LastLineNoContentCache;
1145   else {
1146     bool MyInvalid = false;
1147     const SLocEntry &Entry = getSLocEntry(FID, &MyInvalid);
1148     if (MyInvalid || !Entry.isFile()) {
1149       if (Invalid)
1150         *Invalid = true;
1151       return 1;
1152     }
1153
1154     Content = const_cast<ContentCache*>(Entry.getFile().getContentCache());
1155   }
1156
1157   // If this is the first use of line information for this buffer, compute the
1158   /// SourceLineCache for it on demand.
1159   if (Content->SourceLineCache == 0) {
1160     bool MyInvalid = false;
1161     ComputeLineNumbers(Diag, Content, ContentCacheAlloc, *this, MyInvalid);
1162     if (Invalid)
1163       *Invalid = MyInvalid;
1164     if (MyInvalid)
1165       return 1;
1166   } else if (Invalid)
1167     *Invalid = false;
1168
1169   // Okay, we know we have a line number table.  Do a binary search to find the
1170   // line number that this character position lands on.
1171   unsigned *SourceLineCache = Content->SourceLineCache;
1172   unsigned *SourceLineCacheStart = SourceLineCache;
1173   unsigned *SourceLineCacheEnd = SourceLineCache + Content->NumLines;
1174
1175   unsigned QueriedFilePos = FilePos+1;
1176
1177   // FIXME: I would like to be convinced that this code is worth being as
1178   // complicated as it is, binary search isn't that slow.
1179   //
1180   // If it is worth being optimized, then in my opinion it could be more
1181   // performant, simpler, and more obviously correct by just "galloping" outward
1182   // from the queried file position. In fact, this could be incorporated into a
1183   // generic algorithm such as lower_bound_with_hint.
1184   //
1185   // If someone gives me a test case where this matters, and I will do it! - DWD
1186
1187   // If the previous query was to the same file, we know both the file pos from
1188   // that query and the line number returned.  This allows us to narrow the
1189   // search space from the entire file to something near the match.
1190   if (LastLineNoFileIDQuery == FID) {
1191     if (QueriedFilePos >= LastLineNoFilePos) {
1192       // FIXME: Potential overflow?
1193       SourceLineCache = SourceLineCache+LastLineNoResult-1;
1194
1195       // The query is likely to be nearby the previous one.  Here we check to
1196       // see if it is within 5, 10 or 20 lines.  It can be far away in cases
1197       // where big comment blocks and vertical whitespace eat up lines but
1198       // contribute no tokens.
1199       if (SourceLineCache+5 < SourceLineCacheEnd) {
1200         if (SourceLineCache[5] > QueriedFilePos)
1201           SourceLineCacheEnd = SourceLineCache+5;
1202         else if (SourceLineCache+10 < SourceLineCacheEnd) {
1203           if (SourceLineCache[10] > QueriedFilePos)
1204             SourceLineCacheEnd = SourceLineCache+10;
1205           else if (SourceLineCache+20 < SourceLineCacheEnd) {
1206             if (SourceLineCache[20] > QueriedFilePos)
1207               SourceLineCacheEnd = SourceLineCache+20;
1208           }
1209         }
1210       }
1211     } else {
1212       if (LastLineNoResult < Content->NumLines)
1213         SourceLineCacheEnd = SourceLineCache+LastLineNoResult+1;
1214     }
1215   }
1216
1217   // If the spread is large, do a "radix" test as our initial guess, based on
1218   // the assumption that lines average to approximately the same length.
1219   // NOTE: This is currently disabled, as it does not appear to be profitable in
1220   // initial measurements.
1221   if (0 && SourceLineCacheEnd-SourceLineCache > 20) {
1222     unsigned FileLen = Content->SourceLineCache[Content->NumLines-1];
1223
1224     // Take a stab at guessing where it is.
1225     unsigned ApproxPos = Content->NumLines*QueriedFilePos / FileLen;
1226
1227     // Check for -10 and +10 lines.
1228     unsigned LowerBound = std::max(int(ApproxPos-10), 0);
1229     unsigned UpperBound = std::min(ApproxPos+10, FileLen);
1230
1231     // If the computed lower bound is less than the query location, move it in.
1232     if (SourceLineCache < SourceLineCacheStart+LowerBound &&
1233         SourceLineCacheStart[LowerBound] < QueriedFilePos)
1234       SourceLineCache = SourceLineCacheStart+LowerBound;
1235
1236     // If the computed upper bound is greater than the query location, move it.
1237     if (SourceLineCacheEnd > SourceLineCacheStart+UpperBound &&
1238         SourceLineCacheStart[UpperBound] >= QueriedFilePos)
1239       SourceLineCacheEnd = SourceLineCacheStart+UpperBound;
1240   }
1241
1242   unsigned *Pos
1243     = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
1244   unsigned LineNo = Pos-SourceLineCacheStart;
1245
1246   LastLineNoFileIDQuery = FID;
1247   LastLineNoContentCache = Content;
1248   LastLineNoFilePos = QueriedFilePos;
1249   LastLineNoResult = LineNo;
1250   return LineNo;
1251 }
1252
1253 unsigned SourceManager::getSpellingLineNumber(SourceLocation Loc,
1254                                               bool *Invalid) const {
1255   if (isInvalid(Loc, Invalid)) return 0;
1256   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc);
1257   return getLineNumber(LocInfo.first, LocInfo.second);
1258 }
1259 unsigned SourceManager::getExpansionLineNumber(SourceLocation Loc,
1260                                                bool *Invalid) const {
1261   if (isInvalid(Loc, Invalid)) return 0;
1262   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1263   return getLineNumber(LocInfo.first, LocInfo.second);
1264 }
1265 unsigned SourceManager::getPresumedLineNumber(SourceLocation Loc,
1266                                               bool *Invalid) const {
1267   if (isInvalid(Loc, Invalid)) return 0;
1268   return getPresumedLoc(Loc).getLine();
1269 }
1270
1271 /// getFileCharacteristic - return the file characteristic of the specified
1272 /// source location, indicating whether this is a normal file, a system
1273 /// header, or an "implicit extern C" system header.
1274 ///
1275 /// This state can be modified with flags on GNU linemarker directives like:
1276 ///   # 4 "foo.h" 3
1277 /// which changes all source locations in the current file after that to be
1278 /// considered to be from a system header.
1279 SrcMgr::CharacteristicKind
1280 SourceManager::getFileCharacteristic(SourceLocation Loc) const {
1281   assert(!Loc.isInvalid() && "Can't get file characteristic of invalid loc!");
1282   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1283   bool Invalid = false;
1284   const SLocEntry &SEntry = getSLocEntry(LocInfo.first, &Invalid);
1285   if (Invalid || !SEntry.isFile())
1286     return C_User;
1287
1288   const SrcMgr::FileInfo &FI = SEntry.getFile();
1289
1290   // If there are no #line directives in this file, just return the whole-file
1291   // state.
1292   if (!FI.hasLineDirectives())
1293     return FI.getFileCharacteristic();
1294
1295   assert(LineTable && "Can't have linetable entries without a LineTable!");
1296   // See if there is a #line directive before the location.
1297   const LineEntry *Entry =
1298     LineTable->FindNearestLineEntry(LocInfo.first.ID, LocInfo.second);
1299
1300   // If this is before the first line marker, use the file characteristic.
1301   if (!Entry)
1302     return FI.getFileCharacteristic();
1303
1304   return Entry->FileKind;
1305 }
1306
1307 /// Return the filename or buffer identifier of the buffer the location is in.
1308 /// Note that this name does not respect #line directives.  Use getPresumedLoc
1309 /// for normal clients.
1310 const char *SourceManager::getBufferName(SourceLocation Loc,
1311                                          bool *Invalid) const {
1312   if (isInvalid(Loc, Invalid)) return "<invalid loc>";
1313
1314   return getBuffer(getFileID(Loc), Invalid)->getBufferIdentifier();
1315 }
1316
1317
1318 /// getPresumedLoc - This method returns the "presumed" location of a
1319 /// SourceLocation specifies.  A "presumed location" can be modified by #line
1320 /// or GNU line marker directives.  This provides a view on the data that a
1321 /// user should see in diagnostics, for example.
1322 ///
1323 /// Note that a presumed location is always given as the expansion point of an
1324 /// expansion location, not at the spelling location.
1325 PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const {
1326   if (Loc.isInvalid()) return PresumedLoc();
1327
1328   // Presumed locations are always for expansion points.
1329   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1330
1331   bool Invalid = false;
1332   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
1333   if (Invalid || !Entry.isFile())
1334     return PresumedLoc();
1335
1336   const SrcMgr::FileInfo &FI = Entry.getFile();
1337   const SrcMgr::ContentCache *C = FI.getContentCache();
1338
1339   // To get the source name, first consult the FileEntry (if one exists)
1340   // before the MemBuffer as this will avoid unnecessarily paging in the
1341   // MemBuffer.
1342   const char *Filename;
1343   if (C->OrigEntry)
1344     Filename = C->OrigEntry->getName();
1345   else
1346     Filename = C->getBuffer(Diag, *this)->getBufferIdentifier();
1347
1348   unsigned LineNo = getLineNumber(LocInfo.first, LocInfo.second, &Invalid);
1349   if (Invalid)
1350     return PresumedLoc();
1351   unsigned ColNo  = getColumnNumber(LocInfo.first, LocInfo.second, &Invalid);
1352   if (Invalid)
1353     return PresumedLoc();
1354
1355   SourceLocation IncludeLoc = FI.getIncludeLoc();
1356
1357   // If we have #line directives in this file, update and overwrite the physical
1358   // location info if appropriate.
1359   if (FI.hasLineDirectives()) {
1360     assert(LineTable && "Can't have linetable entries without a LineTable!");
1361     // See if there is a #line directive before this.  If so, get it.
1362     if (const LineEntry *Entry =
1363           LineTable->FindNearestLineEntry(LocInfo.first.ID, LocInfo.second)) {
1364       // If the LineEntry indicates a filename, use it.
1365       if (Entry->FilenameID != -1)
1366         Filename = LineTable->getFilename(Entry->FilenameID);
1367
1368       // Use the line number specified by the LineEntry.  This line number may
1369       // be multiple lines down from the line entry.  Add the difference in
1370       // physical line numbers from the query point and the line marker to the
1371       // total.
1372       unsigned MarkerLineNo = getLineNumber(LocInfo.first, Entry->FileOffset);
1373       LineNo = Entry->LineNo + (LineNo-MarkerLineNo-1);
1374
1375       // Note that column numbers are not molested by line markers.
1376
1377       // Handle virtual #include manipulation.
1378       if (Entry->IncludeOffset) {
1379         IncludeLoc = getLocForStartOfFile(LocInfo.first);
1380         IncludeLoc = IncludeLoc.getLocWithOffset(Entry->IncludeOffset);
1381       }
1382     }
1383   }
1384
1385   return PresumedLoc(Filename, LineNo, ColNo, IncludeLoc);
1386 }
1387
1388 /// \brief The size of the SLocEnty that \arg FID represents.
1389 unsigned SourceManager::getFileIDSize(FileID FID) const {
1390   bool Invalid = false;
1391   const SrcMgr::SLocEntry &Entry = getSLocEntry(FID, &Invalid);
1392   if (Invalid)
1393     return 0;
1394
1395   int ID = FID.ID;
1396   unsigned NextOffset;
1397   if ((ID > 0 && unsigned(ID+1) == local_sloc_entry_size()))
1398     NextOffset = getNextLocalOffset();
1399   else if (ID+1 == -1)
1400     NextOffset = MaxLoadedOffset;
1401   else
1402     NextOffset = getSLocEntry(FileID::get(ID+1)).getOffset();
1403
1404   return NextOffset - Entry.getOffset() - 1;
1405 }
1406
1407 //===----------------------------------------------------------------------===//
1408 // Other miscellaneous methods.
1409 //===----------------------------------------------------------------------===//
1410
1411 /// \brief Retrieve the inode for the given file entry, if possible.
1412 ///
1413 /// This routine involves a system call, and therefore should only be used
1414 /// in non-performance-critical code.
1415 static llvm::Optional<ino_t> getActualFileInode(const FileEntry *File) {
1416   if (!File)
1417     return llvm::Optional<ino_t>();
1418
1419   struct stat StatBuf;
1420   if (::stat(File->getName(), &StatBuf))
1421     return llvm::Optional<ino_t>();
1422
1423   return StatBuf.st_ino;
1424 }
1425
1426 /// \brief Get the source location for the given file:line:col triplet.
1427 ///
1428 /// If the source file is included multiple times, the source location will
1429 /// be based upon an arbitrary inclusion.
1430 SourceLocation SourceManager::translateFileLineCol(const FileEntry *SourceFile,
1431                                                   unsigned Line,
1432                                                   unsigned Col) const {
1433   assert(SourceFile && "Null source file!");
1434   assert(Line && Col && "Line and column should start from 1!");
1435
1436   FileID FirstFID = translateFile(SourceFile);
1437   return translateLineCol(FirstFID, Line, Col);
1438 }
1439
1440 /// \brief Get the FileID for the given file.
1441 ///
1442 /// If the source file is included multiple times, the FileID will be the
1443 /// first inclusion.
1444 FileID SourceManager::translateFile(const FileEntry *SourceFile) const {
1445   assert(SourceFile && "Null source file!");
1446
1447   // Find the first file ID that corresponds to the given file.
1448   FileID FirstFID;
1449
1450   // First, check the main file ID, since it is common to look for a
1451   // location in the main file.
1452   llvm::Optional<ino_t> SourceFileInode;
1453   llvm::Optional<StringRef> SourceFileName;
1454   if (!MainFileID.isInvalid()) {
1455     bool Invalid = false;
1456     const SLocEntry &MainSLoc = getSLocEntry(MainFileID, &Invalid);
1457     if (Invalid)
1458       return FileID();
1459
1460     if (MainSLoc.isFile()) {
1461       const ContentCache *MainContentCache
1462         = MainSLoc.getFile().getContentCache();
1463       if (!MainContentCache) {
1464         // Can't do anything
1465       } else if (MainContentCache->OrigEntry == SourceFile) {
1466         FirstFID = MainFileID;
1467       } else {
1468         // Fall back: check whether we have the same base name and inode
1469         // as the main file.
1470         const FileEntry *MainFile = MainContentCache->OrigEntry;
1471         SourceFileName = llvm::sys::path::filename(SourceFile->getName());
1472         if (*SourceFileName == llvm::sys::path::filename(MainFile->getName())) {
1473           SourceFileInode = getActualFileInode(SourceFile);
1474           if (SourceFileInode) {
1475             if (llvm::Optional<ino_t> MainFileInode
1476                                                = getActualFileInode(MainFile)) {
1477               if (*SourceFileInode == *MainFileInode) {
1478                 FirstFID = MainFileID;
1479                 SourceFile = MainFile;
1480               }
1481             }
1482           }
1483         }
1484       }
1485     }
1486   }
1487
1488   if (FirstFID.isInvalid()) {
1489     // The location we're looking for isn't in the main file; look
1490     // through all of the local source locations.
1491     for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) {
1492       bool Invalid = false;
1493       const SLocEntry &SLoc = getLocalSLocEntry(I, &Invalid);
1494       if (Invalid)
1495         return FileID();
1496
1497       if (SLoc.isFile() &&
1498           SLoc.getFile().getContentCache() &&
1499           SLoc.getFile().getContentCache()->OrigEntry == SourceFile) {
1500         FirstFID = FileID::get(I);
1501         break;
1502       }
1503     }
1504     // If that still didn't help, try the modules.
1505     if (FirstFID.isInvalid()) {
1506       for (unsigned I = 0, N = loaded_sloc_entry_size(); I != N; ++I) {
1507         const SLocEntry &SLoc = getLoadedSLocEntry(I);
1508         if (SLoc.isFile() &&
1509             SLoc.getFile().getContentCache() &&
1510             SLoc.getFile().getContentCache()->OrigEntry == SourceFile) {
1511           FirstFID = FileID::get(-int(I) - 2);
1512           break;
1513         }
1514       }
1515     }
1516   }
1517
1518   // If we haven't found what we want yet, try again, but this time stat()
1519   // each of the files in case the files have changed since we originally
1520   // parsed the file.
1521   if (FirstFID.isInvalid() &&
1522       (SourceFileName ||
1523        (SourceFileName = llvm::sys::path::filename(SourceFile->getName()))) &&
1524       (SourceFileInode ||
1525        (SourceFileInode = getActualFileInode(SourceFile)))) {
1526     bool Invalid = false;
1527     for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) {
1528       FileID IFileID;
1529       IFileID.ID = I;
1530       const SLocEntry &SLoc = getSLocEntry(IFileID, &Invalid);
1531       if (Invalid)
1532         return FileID();
1533
1534       if (SLoc.isFile()) {
1535         const ContentCache *FileContentCache
1536           = SLoc.getFile().getContentCache();
1537       const FileEntry *Entry =FileContentCache? FileContentCache->OrigEntry : 0;
1538         if (Entry &&
1539             *SourceFileName == llvm::sys::path::filename(Entry->getName())) {
1540           if (llvm::Optional<ino_t> EntryInode = getActualFileInode(Entry)) {
1541             if (*SourceFileInode == *EntryInode) {
1542               FirstFID = FileID::get(I);
1543               SourceFile = Entry;
1544               break;
1545             }
1546           }
1547         }
1548       }
1549     }
1550   }
1551
1552   return FirstFID;
1553 }
1554
1555 /// \brief Get the source location in \arg FID for the given line:col.
1556 /// Returns null location if \arg FID is not a file SLocEntry.
1557 SourceLocation SourceManager::translateLineCol(FileID FID,
1558                                                unsigned Line,
1559                                                unsigned Col) const {
1560   if (FID.isInvalid())
1561     return SourceLocation();
1562
1563   bool Invalid = false;
1564   const SLocEntry &Entry = getSLocEntry(FID, &Invalid);
1565   if (Invalid)
1566     return SourceLocation();
1567
1568   if (!Entry.isFile())
1569     return SourceLocation();
1570
1571   SourceLocation FileLoc = SourceLocation::getFileLoc(Entry.getOffset());
1572
1573   if (Line == 1 && Col == 1)
1574     return FileLoc;
1575
1576   ContentCache *Content
1577     = const_cast<ContentCache *>(Entry.getFile().getContentCache());
1578   if (!Content)
1579     return SourceLocation();
1580
1581   // If this is the first use of line information for this buffer, compute the
1582   // SourceLineCache for it on demand.
1583   if (Content->SourceLineCache == 0) {
1584     bool MyInvalid = false;
1585     ComputeLineNumbers(Diag, Content, ContentCacheAlloc, *this, MyInvalid);
1586     if (MyInvalid)
1587       return SourceLocation();
1588   }
1589
1590   if (Line > Content->NumLines) {
1591     unsigned Size = Content->getBuffer(Diag, *this)->getBufferSize();
1592     if (Size > 0)
1593       --Size;
1594     return FileLoc.getLocWithOffset(Size);
1595   }
1596
1597   const llvm::MemoryBuffer *Buffer = Content->getBuffer(Diag, *this);
1598   unsigned FilePos = Content->SourceLineCache[Line - 1];
1599   const char *Buf = Buffer->getBufferStart() + FilePos;
1600   unsigned BufLength = Buffer->getBufferSize() - FilePos;
1601   if (BufLength == 0)
1602     return FileLoc.getLocWithOffset(FilePos);
1603
1604   unsigned i = 0;
1605
1606   // Check that the given column is valid.
1607   while (i < BufLength-1 && i < Col-1 && Buf[i] != '\n' && Buf[i] != '\r')
1608     ++i;
1609   if (i < Col-1)
1610     return FileLoc.getLocWithOffset(FilePos + i);
1611
1612   return FileLoc.getLocWithOffset(FilePos + Col - 1);
1613 }
1614
1615 /// \brief Compute a map of macro argument chunks to their expanded source
1616 /// location. Chunks that are not part of a macro argument will map to an
1617 /// invalid source location. e.g. if a file contains one macro argument at
1618 /// offset 100 with length 10, this is how the map will be formed:
1619 ///     0   -> SourceLocation()
1620 ///     100 -> Expanded macro arg location
1621 ///     110 -> SourceLocation()
1622 void SourceManager::computeMacroArgsCache(MacroArgsMap *&CachePtr,
1623                                           FileID FID) const {
1624   assert(!FID.isInvalid());
1625   assert(!CachePtr);
1626
1627   CachePtr = new MacroArgsMap();
1628   MacroArgsMap &MacroArgsCache = *CachePtr;
1629   // Initially no macro argument chunk is present.
1630   MacroArgsCache.insert(std::make_pair(0, SourceLocation()));
1631
1632   int ID = FID.ID;
1633   while (1) {
1634     ++ID;
1635     // Stop if there are no more FileIDs to check.
1636     if (ID > 0) {
1637       if (unsigned(ID) >= local_sloc_entry_size())
1638         return;
1639     } else if (ID == -1) {
1640       return;
1641     }
1642
1643     const SrcMgr::SLocEntry &Entry = getSLocEntryByID(ID);
1644     if (Entry.isFile()) {
1645       SourceLocation IncludeLoc = Entry.getFile().getIncludeLoc();
1646       if (IncludeLoc.isInvalid())
1647         continue;
1648       if (!isInFileID(IncludeLoc, FID))
1649         return; // No more files/macros that may be "contained" in this file.
1650
1651       // Skip the files/macros of the #include'd file, we only care about macros
1652       // that lexed macro arguments from our file.
1653       if (Entry.getFile().NumCreatedFIDs)
1654         ID += Entry.getFile().NumCreatedFIDs - 1/*because of next ++ID*/;
1655       continue;
1656     }
1657
1658     const ExpansionInfo &ExpInfo = Entry.getExpansion();
1659
1660     if (ExpInfo.getExpansionLocStart().isFileID()) {
1661       if (!isInFileID(ExpInfo.getExpansionLocStart(), FID))
1662         return; // No more files/macros that may be "contained" in this file.
1663     }
1664
1665     if (!ExpInfo.isMacroArgExpansion())
1666       continue;
1667
1668     SourceLocation SpellLoc = ExpInfo.getSpellingLoc();
1669     while (!SpellLoc.isFileID()) {
1670       std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(SpellLoc);
1671       const ExpansionInfo &Info = getSLocEntry(LocInfo.first).getExpansion();
1672       if (!Info.isMacroArgExpansion())
1673         break;
1674       SpellLoc = Info.getSpellingLoc().getLocWithOffset(LocInfo.second);
1675     }
1676     if (!SpellLoc.isFileID())
1677       continue;
1678
1679     unsigned BeginOffs;
1680     if (!isInFileID(SpellLoc, FID, &BeginOffs))
1681       continue;
1682
1683     unsigned EndOffs = BeginOffs + getFileIDSize(FileID::get(ID));
1684
1685     // Add a new chunk for this macro argument. A previous macro argument chunk
1686     // may have been lexed again, so e.g. if the map is
1687     //     0   -> SourceLocation()
1688     //     100 -> Expanded loc #1
1689     //     110 -> SourceLocation()
1690     // and we found a new macro FileID that lexed from offet 105 with length 3,
1691     // the new map will be:
1692     //     0   -> SourceLocation()
1693     //     100 -> Expanded loc #1
1694     //     105 -> Expanded loc #2
1695     //     108 -> Expanded loc #1
1696     //     110 -> SourceLocation()
1697     //
1698     // Since re-lexed macro chunks will always be the same size or less of
1699     // previous chunks, we only need to find where the ending of the new macro
1700     // chunk is mapped to and update the map with new begin/end mappings.
1701
1702     MacroArgsMap::iterator I = MacroArgsCache.upper_bound(EndOffs);
1703     --I;
1704     SourceLocation EndOffsMappedLoc = I->second;
1705     MacroArgsCache[BeginOffs] = SourceLocation::getMacroLoc(Entry.getOffset());
1706     MacroArgsCache[EndOffs] = EndOffsMappedLoc;
1707   }
1708 }
1709
1710 /// \brief If \arg Loc points inside a function macro argument, the returned
1711 /// location will be the macro location in which the argument was expanded.
1712 /// If a macro argument is used multiple times, the expanded location will
1713 /// be at the first expansion of the argument.
1714 /// e.g.
1715 ///   MY_MACRO(foo);
1716 ///             ^
1717 /// Passing a file location pointing at 'foo', will yield a macro location
1718 /// where 'foo' was expanded into.
1719 SourceLocation
1720 SourceManager::getMacroArgExpandedLocation(SourceLocation Loc) const {
1721   if (Loc.isInvalid() || !Loc.isFileID())
1722     return Loc;
1723
1724   FileID FID;
1725   unsigned Offset;
1726   llvm::tie(FID, Offset) = getDecomposedLoc(Loc);
1727   if (FID.isInvalid())
1728     return Loc;
1729
1730   MacroArgsMap *&MacroArgsCache = MacroArgsCacheMap[FID];
1731   if (!MacroArgsCache)
1732     computeMacroArgsCache(MacroArgsCache, FID);
1733
1734   assert(!MacroArgsCache->empty());
1735   MacroArgsMap::iterator I = MacroArgsCache->upper_bound(Offset);
1736   --I;
1737
1738   unsigned MacroArgBeginOffs = I->first;
1739   SourceLocation MacroArgExpandedLoc = I->second;
1740   if (MacroArgExpandedLoc.isValid())
1741     return MacroArgExpandedLoc.getLocWithOffset(Offset - MacroArgBeginOffs);
1742
1743   return Loc;
1744 }
1745
1746 /// Given a decomposed source location, move it up the include/expansion stack
1747 /// to the parent source location.  If this is possible, return the decomposed
1748 /// version of the parent in Loc and return false.  If Loc is the top-level
1749 /// entry, return true and don't modify it.
1750 static bool MoveUpIncludeHierarchy(std::pair<FileID, unsigned> &Loc,
1751                                    const SourceManager &SM) {
1752   SourceLocation UpperLoc;
1753   const SrcMgr::SLocEntry &Entry = SM.getSLocEntry(Loc.first);
1754   if (Entry.isExpansion())
1755     UpperLoc = Entry.getExpansion().getExpansionLocStart();
1756   else
1757     UpperLoc = Entry.getFile().getIncludeLoc();
1758
1759   if (UpperLoc.isInvalid())
1760     return true; // We reached the top.
1761
1762   Loc = SM.getDecomposedLoc(UpperLoc);
1763   return false;
1764 }
1765
1766
1767 /// \brief Determines the order of 2 source locations in the translation unit.
1768 ///
1769 /// \returns true if LHS source location comes before RHS, false otherwise.
1770 bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
1771                                               SourceLocation RHS) const {
1772   assert(LHS.isValid() && RHS.isValid() && "Passed invalid source location!");
1773   if (LHS == RHS)
1774     return false;
1775
1776   std::pair<FileID, unsigned> LOffs = getDecomposedLoc(LHS);
1777   std::pair<FileID, unsigned> ROffs = getDecomposedLoc(RHS);
1778
1779   // If the source locations are in the same file, just compare offsets.
1780   if (LOffs.first == ROffs.first)
1781     return LOffs.second < ROffs.second;
1782
1783   // If we are comparing a source location with multiple locations in the same
1784   // file, we get a big win by caching the result.
1785   if (IsBeforeInTUCache.isCacheValid(LOffs.first, ROffs.first))
1786     return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second);
1787
1788   // Okay, we missed in the cache, start updating the cache for this query.
1789   IsBeforeInTUCache.setQueryFIDs(LOffs.first, ROffs.first,
1790                           /*isLFIDBeforeRFID=*/LOffs.first.ID < ROffs.first.ID);
1791
1792   // We need to find the common ancestor. The only way of doing this is to
1793   // build the complete include chain for one and then walking up the chain
1794   // of the other looking for a match.
1795   // We use a map from FileID to Offset to store the chain. Easier than writing
1796   // a custom set hash info that only depends on the first part of a pair.
1797   typedef llvm::DenseMap<FileID, unsigned> LocSet;
1798   LocSet LChain;
1799   do {
1800     LChain.insert(LOffs);
1801     // We catch the case where LOffs is in a file included by ROffs and
1802     // quit early. The other way round unfortunately remains suboptimal.
1803   } while (LOffs.first != ROffs.first && !MoveUpIncludeHierarchy(LOffs, *this));
1804   LocSet::iterator I;
1805   while((I = LChain.find(ROffs.first)) == LChain.end()) {
1806     if (MoveUpIncludeHierarchy(ROffs, *this))
1807       break; // Met at topmost file.
1808   }
1809   if (I != LChain.end())
1810     LOffs = *I;
1811
1812   // If we exited because we found a nearest common ancestor, compare the
1813   // locations within the common file and cache them.
1814   if (LOffs.first == ROffs.first) {
1815     IsBeforeInTUCache.setCommonLoc(LOffs.first, LOffs.second, ROffs.second);
1816     return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second);
1817   }
1818
1819   // This can happen if a location is in a built-ins buffer.
1820   // But see PR5662.
1821   // Clear the lookup cache, it depends on a common location.
1822   IsBeforeInTUCache.clear();
1823   bool LIsBuiltins = strcmp("<built-in>",
1824                             getBuffer(LOffs.first)->getBufferIdentifier()) == 0;
1825   bool RIsBuiltins = strcmp("<built-in>",
1826                             getBuffer(ROffs.first)->getBufferIdentifier()) == 0;
1827   // built-in is before non-built-in
1828   if (LIsBuiltins != RIsBuiltins)
1829     return LIsBuiltins;
1830   assert(LIsBuiltins && RIsBuiltins &&
1831          "Non-built-in locations must be rooted in the main file");
1832   // Both are in built-in buffers, but from different files. We just claim that
1833   // lower IDs come first.
1834   return LOffs.first < ROffs.first;
1835 }
1836
1837 /// PrintStats - Print statistics to stderr.
1838 ///
1839 void SourceManager::PrintStats() const {
1840   llvm::errs() << "\n*** Source Manager Stats:\n";
1841   llvm::errs() << FileInfos.size() << " files mapped, " << MemBufferInfos.size()
1842                << " mem buffers mapped.\n";
1843   llvm::errs() << LocalSLocEntryTable.size() << " local SLocEntry's allocated ("
1844                << llvm::capacity_in_bytes(LocalSLocEntryTable)
1845                << " bytes of capacity), "
1846                << NextLocalOffset << "B of Sloc address space used.\n";
1847   llvm::errs() << LoadedSLocEntryTable.size()
1848                << " loaded SLocEntries allocated, "
1849                << MaxLoadedOffset - CurrentLoadedOffset
1850                << "B of Sloc address space used.\n";
1851
1852   unsigned NumLineNumsComputed = 0;
1853   unsigned NumFileBytesMapped = 0;
1854   for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
1855     NumLineNumsComputed += I->second->SourceLineCache != 0;
1856     NumFileBytesMapped  += I->second->getSizeBytesMapped();
1857   }
1858   unsigned NumMacroArgsComputed = MacroArgsCacheMap.size();
1859
1860   llvm::errs() << NumFileBytesMapped << " bytes of files mapped, "
1861                << NumLineNumsComputed << " files with line #'s computed, "
1862                << NumMacroArgsComputed << " files with macro args computed.\n";
1863   llvm::errs() << "FileID scans: " << NumLinearScans << " linear, "
1864                << NumBinaryProbes << " binary.\n";
1865 }
1866
1867 ExternalSLocEntrySource::~ExternalSLocEntrySource() { }
1868
1869 /// Return the amount of memory used by memory buffers, breaking down
1870 /// by heap-backed versus mmap'ed memory.
1871 SourceManager::MemoryBufferSizes SourceManager::getMemoryBufferSizes() const {
1872   size_t malloc_bytes = 0;
1873   size_t mmap_bytes = 0;
1874
1875   for (unsigned i = 0, e = MemBufferInfos.size(); i != e; ++i)
1876     if (size_t sized_mapped = MemBufferInfos[i]->getSizeBytesMapped())
1877       switch (MemBufferInfos[i]->getMemoryBufferKind()) {
1878         case llvm::MemoryBuffer::MemoryBuffer_MMap:
1879           mmap_bytes += sized_mapped;
1880           break;
1881         case llvm::MemoryBuffer::MemoryBuffer_Malloc:
1882           malloc_bytes += sized_mapped;
1883           break;
1884       }
1885
1886   return MemoryBufferSizes(malloc_bytes, mmap_bytes);
1887 }
1888
1889 size_t SourceManager::getDataStructureSizes() const {
1890   return llvm::capacity_in_bytes(MemBufferInfos)
1891     + llvm::capacity_in_bytes(LocalSLocEntryTable)
1892     + llvm::capacity_in_bytes(LoadedSLocEntryTable)
1893     + llvm::capacity_in_bytes(SLocEntryLoaded)
1894     + llvm::capacity_in_bytes(FileInfos)
1895     + llvm::capacity_in_bytes(OverriddenFiles);
1896 }