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