Avoid including FileManager.h from SourceManager.h
[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/None.h"
21 #include "llvm/ADT/Optional.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/ADT/StringSwitch.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 /// Create a new FileID that represents the specified file
564 /// being \#included from the specified IncludePosition.
565 ///
566 /// This translates NULL into standard input.
567 FileID SourceManager::createFileID(const FileEntry *SourceFile,
568                                    SourceLocation IncludePos,
569                                    SrcMgr::CharacteristicKind FileCharacter,
570                                    int LoadedID, unsigned LoadedOffset) {
571   assert(SourceFile && "Null source file!");
572   const SrcMgr::ContentCache *IR =
573       getOrCreateContentCache(SourceFile, isSystem(FileCharacter));
574   assert(IR && "getOrCreateContentCache() cannot return NULL");
575   return createFileID(IR, SourceFile->getName(), IncludePos, FileCharacter,
576                       LoadedID, LoadedOffset);
577 }
578
579 FileID SourceManager::createFileID(FileEntryRef SourceFile,
580                                    SourceLocation IncludePos,
581                                    SrcMgr::CharacteristicKind FileCharacter,
582                                    int LoadedID, unsigned LoadedOffset) {
583   const SrcMgr::ContentCache *IR = getOrCreateContentCache(
584       &SourceFile.getFileEntry(), isSystem(FileCharacter));
585   assert(IR && "getOrCreateContentCache() cannot return NULL");
586   return createFileID(IR, SourceFile.getName(), IncludePos, FileCharacter,
587                       LoadedID, LoadedOffset);
588 }
589
590 /// Create a new FileID that represents the specified memory buffer.
591 ///
592 /// This does no caching of the buffer and takes ownership of the
593 /// MemoryBuffer, so only pass a MemoryBuffer to this once.
594 FileID SourceManager::createFileID(std::unique_ptr<llvm::MemoryBuffer> Buffer,
595                                    SrcMgr::CharacteristicKind FileCharacter,
596                                    int LoadedID, unsigned LoadedOffset,
597                                    SourceLocation IncludeLoc) {
598   StringRef Name = Buffer->getBufferIdentifier();
599   return createFileID(
600       createMemBufferContentCache(Buffer.release(), /*DoNotFree*/ false),
601       Name, IncludeLoc, FileCharacter, LoadedID, LoadedOffset);
602 }
603
604 /// Create a new FileID that represents the specified memory buffer.
605 ///
606 /// This does not take ownership of the MemoryBuffer. The memory buffer must
607 /// outlive the SourceManager.
608 FileID SourceManager::createFileID(UnownedTag, const llvm::MemoryBuffer *Buffer,
609                                    SrcMgr::CharacteristicKind FileCharacter,
610                                    int LoadedID, unsigned LoadedOffset,
611                                    SourceLocation IncludeLoc) {
612   return createFileID(createMemBufferContentCache(Buffer, /*DoNotFree*/ true),
613                       Buffer->getBufferIdentifier(), IncludeLoc,
614                       FileCharacter, LoadedID, LoadedOffset);
615 }
616
617 /// Get the FileID for \p SourceFile if it exists. Otherwise, create a
618 /// new FileID for the \p SourceFile.
619 FileID
620 SourceManager::getOrCreateFileID(const FileEntry *SourceFile,
621                                  SrcMgr::CharacteristicKind FileCharacter) {
622   FileID ID = translateFile(SourceFile);
623   return ID.isValid() ? ID : createFileID(SourceFile, SourceLocation(),
624                                           FileCharacter);
625 }
626
627 /// createFileID - Create a new FileID for the specified ContentCache and
628 /// include position.  This works regardless of whether the ContentCache
629 /// corresponds to a file or some other input source.
630 FileID SourceManager::createFileID(const ContentCache *File, StringRef Filename,
631                                    SourceLocation IncludePos,
632                                    SrcMgr::CharacteristicKind FileCharacter,
633                                    int LoadedID, unsigned LoadedOffset) {
634   if (LoadedID < 0) {
635     assert(LoadedID != -1 && "Loading sentinel FileID");
636     unsigned Index = unsigned(-LoadedID) - 2;
637     assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
638     assert(!SLocEntryLoaded[Index] && "FileID already loaded");
639     LoadedSLocEntryTable[Index] = SLocEntry::get(
640         LoadedOffset, FileInfo::get(IncludePos, File, FileCharacter, Filename));
641     SLocEntryLoaded[Index] = true;
642     return FileID::get(LoadedID);
643   }
644   unsigned FileSize = File->getSize();
645   if (!(NextLocalOffset + FileSize + 1 > NextLocalOffset &&
646         NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset)) {
647     Diag.Report(IncludePos, diag::err_include_too_large);
648     return FileID();
649   }
650   LocalSLocEntryTable.push_back(
651       SLocEntry::get(NextLocalOffset,
652                      FileInfo::get(IncludePos, File, FileCharacter, Filename)));
653   // We do a +1 here because we want a SourceLocation that means "the end of the
654   // file", e.g. for the "no newline at the end of the file" diagnostic.
655   NextLocalOffset += FileSize + 1;
656
657   // Set LastFileIDLookup to the newly created file.  The next getFileID call is
658   // almost guaranteed to be from that file.
659   FileID FID = FileID::get(LocalSLocEntryTable.size()-1);
660   return LastFileIDLookup = FID;
661 }
662
663 SourceLocation
664 SourceManager::createMacroArgExpansionLoc(SourceLocation SpellingLoc,
665                                           SourceLocation ExpansionLoc,
666                                           unsigned TokLength) {
667   ExpansionInfo Info = ExpansionInfo::createForMacroArg(SpellingLoc,
668                                                         ExpansionLoc);
669   return createExpansionLocImpl(Info, TokLength);
670 }
671
672 SourceLocation
673 SourceManager::createExpansionLoc(SourceLocation SpellingLoc,
674                                   SourceLocation ExpansionLocStart,
675                                   SourceLocation ExpansionLocEnd,
676                                   unsigned TokLength,
677                                   bool ExpansionIsTokenRange,
678                                   int LoadedID,
679                                   unsigned LoadedOffset) {
680   ExpansionInfo Info = ExpansionInfo::create(
681       SpellingLoc, ExpansionLocStart, ExpansionLocEnd, ExpansionIsTokenRange);
682   return createExpansionLocImpl(Info, TokLength, LoadedID, LoadedOffset);
683 }
684
685 SourceLocation SourceManager::createTokenSplitLoc(SourceLocation Spelling,
686                                                   SourceLocation TokenStart,
687                                                   SourceLocation TokenEnd) {
688   assert(getFileID(TokenStart) == getFileID(TokenEnd) &&
689          "token spans multiple files");
690   return createExpansionLocImpl(
691       ExpansionInfo::createForTokenSplit(Spelling, TokenStart, TokenEnd),
692       TokenEnd.getOffset() - TokenStart.getOffset());
693 }
694
695 SourceLocation
696 SourceManager::createExpansionLocImpl(const ExpansionInfo &Info,
697                                       unsigned TokLength,
698                                       int LoadedID,
699                                       unsigned LoadedOffset) {
700   if (LoadedID < 0) {
701     assert(LoadedID != -1 && "Loading sentinel FileID");
702     unsigned Index = unsigned(-LoadedID) - 2;
703     assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
704     assert(!SLocEntryLoaded[Index] && "FileID already loaded");
705     LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, Info);
706     SLocEntryLoaded[Index] = true;
707     return SourceLocation::getMacroLoc(LoadedOffset);
708   }
709   LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info));
710   assert(NextLocalOffset + TokLength + 1 > NextLocalOffset &&
711          NextLocalOffset + TokLength + 1 <= CurrentLoadedOffset &&
712          "Ran out of source locations!");
713   // See createFileID for that +1.
714   NextLocalOffset += TokLength + 1;
715   return SourceLocation::getMacroLoc(NextLocalOffset - (TokLength + 1));
716 }
717
718 const llvm::MemoryBuffer *
719 SourceManager::getMemoryBufferForFile(const FileEntry *File, bool *Invalid) {
720   const SrcMgr::ContentCache *IR = getOrCreateContentCache(File);
721   assert(IR && "getOrCreateContentCache() cannot return NULL");
722   return IR->getBuffer(Diag, getFileManager(), SourceLocation(), Invalid);
723 }
724
725 void SourceManager::overrideFileContents(const FileEntry *SourceFile,
726                                          llvm::MemoryBuffer *Buffer,
727                                          bool DoNotFree) {
728   const SrcMgr::ContentCache *IR = getOrCreateContentCache(SourceFile);
729   assert(IR && "getOrCreateContentCache() cannot return NULL");
730
731   const_cast<SrcMgr::ContentCache *>(IR)->replaceBuffer(Buffer, DoNotFree);
732   const_cast<SrcMgr::ContentCache *>(IR)->BufferOverridden = true;
733
734   getOverriddenFilesInfo().OverriddenFilesWithBuffer.insert(SourceFile);
735 }
736
737 void SourceManager::overrideFileContents(const FileEntry *SourceFile,
738                                          const FileEntry *NewFile) {
739   assert(SourceFile->getSize() == NewFile->getSize() &&
740          "Different sizes, use the FileManager to create a virtual file with "
741          "the correct size");
742   assert(FileInfos.count(SourceFile) == 0 &&
743          "This function should be called at the initialization stage, before "
744          "any parsing occurs.");
745   getOverriddenFilesInfo().OverriddenFiles[SourceFile] = NewFile;
746 }
747
748 const FileEntry *
749 SourceManager::bypassFileContentsOverride(const FileEntry &File) {
750   assert(isFileOverridden(&File));
751   llvm::Optional<FileEntryRef> BypassFile =
752       FileMgr.getBypassFile(FileEntryRef(File.getName(), File));
753
754   // If the file can't be found in the FS, give up.
755   if (!BypassFile)
756     return nullptr;
757
758   const FileEntry *FE = &BypassFile->getFileEntry();
759   (void)getOrCreateContentCache(FE);
760   return FE;
761 }
762
763 void SourceManager::setFileIsTransient(const FileEntry *File) {
764   const SrcMgr::ContentCache *CC = getOrCreateContentCache(File);
765   const_cast<SrcMgr::ContentCache *>(CC)->IsTransient = true;
766 }
767
768 Optional<FileEntryRef> SourceManager::getFileEntryRefForID(FileID FID) const {
769   bool Invalid = false;
770   const SrcMgr::SLocEntry &Entry = getSLocEntry(FID, &Invalid);
771   if (Invalid || !Entry.isFile())
772     return None;
773
774   const SrcMgr::ContentCache *Content = Entry.getFile().getContentCache();
775   if (!Content || !Content->OrigEntry)
776     return None;
777   return FileEntryRef(Entry.getFile().getName(), *Content->OrigEntry);
778 }
779
780 StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const {
781   bool MyInvalid = false;
782   const SLocEntry &SLoc = getSLocEntry(FID, &MyInvalid);
783   if (!SLoc.isFile() || MyInvalid) {
784     if (Invalid)
785       *Invalid = true;
786     return "<<<<<INVALID SOURCE LOCATION>>>>>";
787   }
788
789   const llvm::MemoryBuffer *Buf = SLoc.getFile().getContentCache()->getBuffer(
790       Diag, getFileManager(), SourceLocation(), &MyInvalid);
791   if (Invalid)
792     *Invalid = MyInvalid;
793
794   if (MyInvalid)
795     return "<<<<<INVALID SOURCE LOCATION>>>>>";
796
797   return Buf->getBuffer();
798 }
799
800 //===----------------------------------------------------------------------===//
801 // SourceLocation manipulation methods.
802 //===----------------------------------------------------------------------===//
803
804 /// Return the FileID for a SourceLocation.
805 ///
806 /// This is the cache-miss path of getFileID. Not as hot as that function, but
807 /// still very important. It is responsible for finding the entry in the
808 /// SLocEntry tables that contains the specified location.
809 FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
810   if (!SLocOffset)
811     return FileID::get(0);
812
813   // Now it is time to search for the correct file. See where the SLocOffset
814   // sits in the global view and consult local or loaded buffers for it.
815   if (SLocOffset < NextLocalOffset)
816     return getFileIDLocal(SLocOffset);
817   return getFileIDLoaded(SLocOffset);
818 }
819
820 /// Return the FileID for a SourceLocation with a low offset.
821 ///
822 /// This function knows that the SourceLocation is in a local buffer, not a
823 /// loaded one.
824 FileID SourceManager::getFileIDLocal(unsigned SLocOffset) const {
825   assert(SLocOffset < NextLocalOffset && "Bad function choice");
826
827   // After the first and second level caches, I see two common sorts of
828   // behavior: 1) a lot of searched FileID's are "near" the cached file
829   // location or are "near" the cached expansion location. 2) others are just
830   // completely random and may be a very long way away.
831   //
832   // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
833   // then we fall back to a less cache efficient, but more scalable, binary
834   // search to find the location.
835
836   // See if this is near the file point - worst case we start scanning from the
837   // most newly created FileID.
838   const SrcMgr::SLocEntry *I;
839
840   if (LastFileIDLookup.ID < 0 ||
841       LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
842     // Neither loc prunes our search.
843     I = LocalSLocEntryTable.end();
844   } else {
845     // Perhaps it is near the file point.
846     I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID;
847   }
848
849   // Find the FileID that contains this.  "I" is an iterator that points to a
850   // FileID whose offset is known to be larger than SLocOffset.
851   unsigned NumProbes = 0;
852   while (true) {
853     --I;
854     if (I->getOffset() <= SLocOffset) {
855       FileID Res = FileID::get(int(I - LocalSLocEntryTable.begin()));
856
857       // If this isn't an expansion, remember it.  We have good locality across
858       // FileID lookups.
859       if (!I->isExpansion())
860         LastFileIDLookup = Res;
861       NumLinearScans += NumProbes+1;
862       return Res;
863     }
864     if (++NumProbes == 8)
865       break;
866   }
867
868   // Convert "I" back into an index.  We know that it is an entry whose index is
869   // larger than the offset we are looking for.
870   unsigned GreaterIndex = I - LocalSLocEntryTable.begin();
871   // LessIndex - This is the lower bound of the range that we're searching.
872   // We know that the offset corresponding to the FileID is is less than
873   // SLocOffset.
874   unsigned LessIndex = 0;
875   NumProbes = 0;
876   while (true) {
877     bool Invalid = false;
878     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
879     unsigned MidOffset = getLocalSLocEntry(MiddleIndex, &Invalid).getOffset();
880     if (Invalid)
881       return FileID::get(0);
882
883     ++NumProbes;
884
885     // If the offset of the midpoint is too large, chop the high side of the
886     // range to the midpoint.
887     if (MidOffset > SLocOffset) {
888       GreaterIndex = MiddleIndex;
889       continue;
890     }
891
892     // If the middle index contains the value, succeed and return.
893     // FIXME: This could be made faster by using a function that's aware of
894     // being in the local area.
895     if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) {
896       FileID Res = FileID::get(MiddleIndex);
897
898       // If this isn't a macro expansion, remember it.  We have good locality
899       // across FileID lookups.
900       if (!LocalSLocEntryTable[MiddleIndex].isExpansion())
901         LastFileIDLookup = Res;
902       NumBinaryProbes += NumProbes;
903       return Res;
904     }
905
906     // Otherwise, move the low-side up to the middle index.
907     LessIndex = MiddleIndex;
908   }
909 }
910
911 /// Return the FileID for a SourceLocation with a high offset.
912 ///
913 /// This function knows that the SourceLocation is in a loaded buffer, not a
914 /// local one.
915 FileID SourceManager::getFileIDLoaded(unsigned SLocOffset) const {
916   // Sanity checking, otherwise a bug may lead to hanging in release build.
917   if (SLocOffset < CurrentLoadedOffset) {
918     assert(0 && "Invalid SLocOffset or bad function choice");
919     return FileID();
920   }
921
922   // Essentially the same as the local case, but the loaded array is sorted
923   // in the other direction.
924
925   // First do a linear scan from the last lookup position, if possible.
926   unsigned I;
927   int LastID = LastFileIDLookup.ID;
928   if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset)
929     I = 0;
930   else
931     I = (-LastID - 2) + 1;
932
933   unsigned NumProbes;
934   for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) {
935     // Make sure the entry is loaded!
936     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I);
937     if (E.getOffset() <= SLocOffset) {
938       FileID Res = FileID::get(-int(I) - 2);
939
940       if (!E.isExpansion())
941         LastFileIDLookup = Res;
942       NumLinearScans += NumProbes + 1;
943       return Res;
944     }
945   }
946
947   // Linear scan failed. Do the binary search. Note the reverse sorting of the
948   // table: GreaterIndex is the one where the offset is greater, which is
949   // actually a lower index!
950   unsigned GreaterIndex = I;
951   unsigned LessIndex = LoadedSLocEntryTable.size();
952   NumProbes = 0;
953   while (true) {
954     ++NumProbes;
955     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
956     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex);
957     if (E.getOffset() == 0)
958       return FileID(); // invalid entry.
959
960     ++NumProbes;
961
962     if (E.getOffset() > SLocOffset) {
963       // Sanity checking, otherwise a bug may lead to hanging in release build.
964       if (GreaterIndex == MiddleIndex) {
965         assert(0 && "binary search missed the entry");
966         return FileID();
967       }
968       GreaterIndex = MiddleIndex;
969       continue;
970     }
971
972     if (isOffsetInFileID(FileID::get(-int(MiddleIndex) - 2), SLocOffset)) {
973       FileID Res = FileID::get(-int(MiddleIndex) - 2);
974       if (!E.isExpansion())
975         LastFileIDLookup = Res;
976       NumBinaryProbes += NumProbes;
977       return Res;
978     }
979
980     // Sanity checking, otherwise a bug may lead to hanging in release build.
981     if (LessIndex == MiddleIndex) {
982       assert(0 && "binary search missed the entry");
983       return FileID();
984     }
985     LessIndex = MiddleIndex;
986   }
987 }
988
989 SourceLocation SourceManager::
990 getExpansionLocSlowCase(SourceLocation Loc) const {
991   do {
992     // Note: If Loc indicates an offset into a token that came from a macro
993     // expansion (e.g. the 5th character of the token) we do not want to add
994     // this offset when going to the expansion location.  The expansion
995     // location is the macro invocation, which the offset has nothing to do
996     // with.  This is unlike when we get the spelling loc, because the offset
997     // directly correspond to the token whose spelling we're inspecting.
998     Loc = getSLocEntry(getFileID(Loc)).getExpansion().getExpansionLocStart();
999   } while (!Loc.isFileID());
1000
1001   return Loc;
1002 }
1003
1004 SourceLocation SourceManager::getSpellingLocSlowCase(SourceLocation Loc) const {
1005   do {
1006     std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
1007     Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc();
1008     Loc = Loc.getLocWithOffset(LocInfo.second);
1009   } while (!Loc.isFileID());
1010   return Loc;
1011 }
1012
1013 SourceLocation SourceManager::getFileLocSlowCase(SourceLocation Loc) const {
1014   do {
1015     if (isMacroArgExpansion(Loc))
1016       Loc = getImmediateSpellingLoc(Loc);
1017     else
1018       Loc = getImmediateExpansionRange(Loc).getBegin();
1019   } while (!Loc.isFileID());
1020   return Loc;
1021 }
1022
1023
1024 std::pair<FileID, unsigned>
1025 SourceManager::getDecomposedExpansionLocSlowCase(
1026                                              const SrcMgr::SLocEntry *E) const {
1027   // If this is an expansion record, walk through all the expansion points.
1028   FileID FID;
1029   SourceLocation Loc;
1030   unsigned Offset;
1031   do {
1032     Loc = E->getExpansion().getExpansionLocStart();
1033
1034     FID = getFileID(Loc);
1035     E = &getSLocEntry(FID);
1036     Offset = Loc.getOffset()-E->getOffset();
1037   } while (!Loc.isFileID());
1038
1039   return std::make_pair(FID, Offset);
1040 }
1041
1042 std::pair<FileID, unsigned>
1043 SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E,
1044                                                 unsigned Offset) const {
1045   // If this is an expansion record, walk through all the expansion points.
1046   FileID FID;
1047   SourceLocation Loc;
1048   do {
1049     Loc = E->getExpansion().getSpellingLoc();
1050     Loc = Loc.getLocWithOffset(Offset);
1051
1052     FID = getFileID(Loc);
1053     E = &getSLocEntry(FID);
1054     Offset = Loc.getOffset()-E->getOffset();
1055   } while (!Loc.isFileID());
1056
1057   return std::make_pair(FID, Offset);
1058 }
1059
1060 /// getImmediateSpellingLoc - Given a SourceLocation object, return the
1061 /// spelling location referenced by the ID.  This is the first level down
1062 /// towards the place where the characters that make up the lexed token can be
1063 /// found.  This should not generally be used by clients.
1064 SourceLocation SourceManager::getImmediateSpellingLoc(SourceLocation Loc) const{
1065   if (Loc.isFileID()) return Loc;
1066   std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
1067   Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc();
1068   return Loc.getLocWithOffset(LocInfo.second);
1069 }
1070
1071 /// Return the filename of the file containing a SourceLocation.
1072 StringRef SourceManager::getFilename(SourceLocation SpellingLoc) const {
1073   if (const FileEntry *F = getFileEntryForID(getFileID(SpellingLoc)))
1074     return F->getName();
1075   return StringRef();
1076 }
1077
1078 /// getImmediateExpansionRange - Loc is required to be an expansion location.
1079 /// Return the start/end of the expansion information.
1080 CharSourceRange
1081 SourceManager::getImmediateExpansionRange(SourceLocation Loc) const {
1082   assert(Loc.isMacroID() && "Not a macro expansion loc!");
1083   const ExpansionInfo &Expansion = getSLocEntry(getFileID(Loc)).getExpansion();
1084   return Expansion.getExpansionLocRange();
1085 }
1086
1087 SourceLocation SourceManager::getTopMacroCallerLoc(SourceLocation Loc) const {
1088   while (isMacroArgExpansion(Loc))
1089     Loc = getImmediateSpellingLoc(Loc);
1090   return Loc;
1091 }
1092
1093 /// getExpansionRange - Given a SourceLocation object, return the range of
1094 /// tokens covered by the expansion in the ultimate file.
1095 CharSourceRange SourceManager::getExpansionRange(SourceLocation Loc) const {
1096   if (Loc.isFileID())
1097     return CharSourceRange(SourceRange(Loc, Loc), true);
1098
1099   CharSourceRange Res = getImmediateExpansionRange(Loc);
1100
1101   // Fully resolve the start and end locations to their ultimate expansion
1102   // points.
1103   while (!Res.getBegin().isFileID())
1104     Res.setBegin(getImmediateExpansionRange(Res.getBegin()).getBegin());
1105   while (!Res.getEnd().isFileID()) {
1106     CharSourceRange EndRange = getImmediateExpansionRange(Res.getEnd());
1107     Res.setEnd(EndRange.getEnd());
1108     Res.setTokenRange(EndRange.isTokenRange());
1109   }
1110   return Res;
1111 }
1112
1113 bool SourceManager::isMacroArgExpansion(SourceLocation Loc,
1114                                         SourceLocation *StartLoc) const {
1115   if (!Loc.isMacroID()) return false;
1116
1117   FileID FID = getFileID(Loc);
1118   const SrcMgr::ExpansionInfo &Expansion = getSLocEntry(FID).getExpansion();
1119   if (!Expansion.isMacroArgExpansion()) return false;
1120
1121   if (StartLoc)
1122     *StartLoc = Expansion.getExpansionLocStart();
1123   return true;
1124 }
1125
1126 bool SourceManager::isMacroBodyExpansion(SourceLocation Loc) const {
1127   if (!Loc.isMacroID()) return false;
1128
1129   FileID FID = getFileID(Loc);
1130   const SrcMgr::ExpansionInfo &Expansion = getSLocEntry(FID).getExpansion();
1131   return Expansion.isMacroBodyExpansion();
1132 }
1133
1134 bool SourceManager::isAtStartOfImmediateMacroExpansion(SourceLocation Loc,
1135                                              SourceLocation *MacroBegin) const {
1136   assert(Loc.isValid() && Loc.isMacroID() && "Expected a valid macro loc");
1137
1138   std::pair<FileID, unsigned> DecompLoc = getDecomposedLoc(Loc);
1139   if (DecompLoc.second > 0)
1140     return false; // Does not point at the start of expansion range.
1141
1142   bool Invalid = false;
1143   const SrcMgr::ExpansionInfo &ExpInfo =
1144       getSLocEntry(DecompLoc.first, &Invalid).getExpansion();
1145   if (Invalid)
1146     return false;
1147   SourceLocation ExpLoc = ExpInfo.getExpansionLocStart();
1148
1149   if (ExpInfo.isMacroArgExpansion()) {
1150     // For macro argument expansions, check if the previous FileID is part of
1151     // the same argument expansion, in which case this Loc is not at the
1152     // beginning of the expansion.
1153     FileID PrevFID = getPreviousFileID(DecompLoc.first);
1154     if (!PrevFID.isInvalid()) {
1155       const SrcMgr::SLocEntry &PrevEntry = getSLocEntry(PrevFID, &Invalid);
1156       if (Invalid)
1157         return false;
1158       if (PrevEntry.isExpansion() &&
1159           PrevEntry.getExpansion().getExpansionLocStart() == ExpLoc)
1160         return false;
1161     }
1162   }
1163
1164   if (MacroBegin)
1165     *MacroBegin = ExpLoc;
1166   return true;
1167 }
1168
1169 bool SourceManager::isAtEndOfImmediateMacroExpansion(SourceLocation Loc,
1170                                                SourceLocation *MacroEnd) const {
1171   assert(Loc.isValid() && Loc.isMacroID() && "Expected a valid macro loc");
1172
1173   FileID FID = getFileID(Loc);
1174   SourceLocation NextLoc = Loc.getLocWithOffset(1);
1175   if (isInFileID(NextLoc, FID))
1176     return false; // Does not point at the end of expansion range.
1177
1178   bool Invalid = false;
1179   const SrcMgr::ExpansionInfo &ExpInfo =
1180       getSLocEntry(FID, &Invalid).getExpansion();
1181   if (Invalid)
1182     return false;
1183
1184   if (ExpInfo.isMacroArgExpansion()) {
1185     // For macro argument expansions, check if the next FileID is part of the
1186     // same argument expansion, in which case this Loc is not at the end of the
1187     // expansion.
1188     FileID NextFID = getNextFileID(FID);
1189     if (!NextFID.isInvalid()) {
1190       const SrcMgr::SLocEntry &NextEntry = getSLocEntry(NextFID, &Invalid);
1191       if (Invalid)
1192         return false;
1193       if (NextEntry.isExpansion() &&
1194           NextEntry.getExpansion().getExpansionLocStart() ==
1195               ExpInfo.getExpansionLocStart())
1196         return false;
1197     }
1198   }
1199
1200   if (MacroEnd)
1201     *MacroEnd = ExpInfo.getExpansionLocEnd();
1202   return true;
1203 }
1204
1205 //===----------------------------------------------------------------------===//
1206 // Queries about the code at a SourceLocation.
1207 //===----------------------------------------------------------------------===//
1208
1209 /// getCharacterData - Return a pointer to the start of the specified location
1210 /// in the appropriate MemoryBuffer.
1211 const char *SourceManager::getCharacterData(SourceLocation SL,
1212                                             bool *Invalid) const {
1213   // Note that this is a hot function in the getSpelling() path, which is
1214   // heavily used by -E mode.
1215   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(SL);
1216
1217   // Note that calling 'getBuffer()' may lazily page in a source file.
1218   bool CharDataInvalid = false;
1219   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &CharDataInvalid);
1220   if (CharDataInvalid || !Entry.isFile()) {
1221     if (Invalid)
1222       *Invalid = true;
1223
1224     return "<<<<INVALID BUFFER>>>>";
1225   }
1226   const llvm::MemoryBuffer *Buffer =
1227       Entry.getFile().getContentCache()->getBuffer(
1228           Diag, getFileManager(), SourceLocation(), &CharDataInvalid);
1229   if (Invalid)
1230     *Invalid = CharDataInvalid;
1231   return Buffer->getBufferStart() + (CharDataInvalid? 0 : LocInfo.second);
1232 }
1233
1234 /// getColumnNumber - Return the column # for the specified file position.
1235 /// this is significantly cheaper to compute than the line number.
1236 unsigned SourceManager::getColumnNumber(FileID FID, unsigned FilePos,
1237                                         bool *Invalid) const {
1238   bool MyInvalid = false;
1239   const llvm::MemoryBuffer *MemBuf = getBuffer(FID, &MyInvalid);
1240   if (Invalid)
1241     *Invalid = MyInvalid;
1242
1243   if (MyInvalid)
1244     return 1;
1245
1246   // It is okay to request a position just past the end of the buffer.
1247   if (FilePos > MemBuf->getBufferSize()) {
1248     if (Invalid)
1249       *Invalid = true;
1250     return 1;
1251   }
1252
1253   const char *Buf = MemBuf->getBufferStart();
1254   // See if we just calculated the line number for this FilePos and can use
1255   // that to lookup the start of the line instead of searching for it.
1256   if (LastLineNoFileIDQuery == FID &&
1257       LastLineNoContentCache->SourceLineCache != nullptr &&
1258       LastLineNoResult < LastLineNoContentCache->NumLines) {
1259     unsigned *SourceLineCache = LastLineNoContentCache->SourceLineCache;
1260     unsigned LineStart = SourceLineCache[LastLineNoResult - 1];
1261     unsigned LineEnd = SourceLineCache[LastLineNoResult];
1262     if (FilePos >= LineStart && FilePos < LineEnd) {
1263       // LineEnd is the LineStart of the next line.
1264       // A line ends with separator LF or CR+LF on Windows.
1265       // FilePos might point to the last separator,
1266       // but we need a column number at most 1 + the last column.
1267       if (FilePos + 1 == LineEnd && FilePos > LineStart) {
1268         if (Buf[FilePos - 1] == '\r' || Buf[FilePos - 1] == '\n')
1269           --FilePos;
1270       }
1271       return FilePos - LineStart + 1;
1272     }
1273   }
1274
1275   unsigned LineStart = FilePos;
1276   while (LineStart && Buf[LineStart-1] != '\n' && Buf[LineStart-1] != '\r')
1277     --LineStart;
1278   return FilePos-LineStart+1;
1279 }
1280
1281 // isInvalid - Return the result of calling loc.isInvalid(), and
1282 // if Invalid is not null, set its value to same.
1283 template<typename LocType>
1284 static bool isInvalid(LocType Loc, bool *Invalid) {
1285   bool MyInvalid = Loc.isInvalid();
1286   if (Invalid)
1287     *Invalid = MyInvalid;
1288   return MyInvalid;
1289 }
1290
1291 unsigned SourceManager::getSpellingColumnNumber(SourceLocation Loc,
1292                                                 bool *Invalid) const {
1293   if (isInvalid(Loc, Invalid)) return 0;
1294   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc);
1295   return getColumnNumber(LocInfo.first, LocInfo.second, Invalid);
1296 }
1297
1298 unsigned SourceManager::getExpansionColumnNumber(SourceLocation Loc,
1299                                                  bool *Invalid) const {
1300   if (isInvalid(Loc, Invalid)) return 0;
1301   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1302   return getColumnNumber(LocInfo.first, LocInfo.second, Invalid);
1303 }
1304
1305 unsigned SourceManager::getPresumedColumnNumber(SourceLocation Loc,
1306                                                 bool *Invalid) const {
1307   PresumedLoc PLoc = getPresumedLoc(Loc);
1308   if (isInvalid(PLoc, Invalid)) return 0;
1309   return PLoc.getColumn();
1310 }
1311
1312 #ifdef __SSE2__
1313 #include <emmintrin.h>
1314 #endif
1315
1316 static LLVM_ATTRIBUTE_NOINLINE void
1317 ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
1318                    llvm::BumpPtrAllocator &Alloc,
1319                    const SourceManager &SM, bool &Invalid);
1320 static void ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
1321                                llvm::BumpPtrAllocator &Alloc,
1322                                const SourceManager &SM, bool &Invalid) {
1323   // Note that calling 'getBuffer()' may lazily page in the file.
1324   const MemoryBuffer *Buffer =
1325       FI->getBuffer(Diag, SM.getFileManager(), SourceLocation(), &Invalid);
1326   if (Invalid)
1327     return;
1328
1329   // Find the file offsets of all of the *physical* source lines.  This does
1330   // not look at trigraphs, escaped newlines, or anything else tricky.
1331   SmallVector<unsigned, 256> LineOffsets;
1332
1333   // Line #1 starts at char 0.
1334   LineOffsets.push_back(0);
1335
1336   const unsigned char *Buf = (const unsigned char *)Buffer->getBufferStart();
1337   const unsigned char *End = (const unsigned char *)Buffer->getBufferEnd();
1338   const std::size_t BufLen = End - Buf;
1339   unsigned I = 0;
1340   while (I < BufLen) {
1341     if (Buf[I] == '\n') {
1342       LineOffsets.push_back(I + 1);
1343     } else if (Buf[I] == '\r') {
1344       // If this is \r\n, skip both characters.
1345       if (I + 1 < BufLen && Buf[I + 1] == '\n')
1346         ++I;
1347       LineOffsets.push_back(I + 1);
1348     }
1349     ++I;
1350   }
1351
1352   // Copy the offsets into the FileInfo structure.
1353   FI->NumLines = LineOffsets.size();
1354   FI->SourceLineCache = Alloc.Allocate<unsigned>(LineOffsets.size());
1355   std::copy(LineOffsets.begin(), LineOffsets.end(), FI->SourceLineCache);
1356 }
1357
1358 /// getLineNumber - Given a SourceLocation, return the spelling line number
1359 /// for the position indicated.  This requires building and caching a table of
1360 /// line offsets for the MemoryBuffer, so this is not cheap: use only when
1361 /// about to emit a diagnostic.
1362 unsigned SourceManager::getLineNumber(FileID FID, unsigned FilePos,
1363                                       bool *Invalid) const {
1364   if (FID.isInvalid()) {
1365     if (Invalid)
1366       *Invalid = true;
1367     return 1;
1368   }
1369
1370   ContentCache *Content;
1371   if (LastLineNoFileIDQuery == FID)
1372     Content = LastLineNoContentCache;
1373   else {
1374     bool MyInvalid = false;
1375     const SLocEntry &Entry = getSLocEntry(FID, &MyInvalid);
1376     if (MyInvalid || !Entry.isFile()) {
1377       if (Invalid)
1378         *Invalid = true;
1379       return 1;
1380     }
1381
1382     Content = const_cast<ContentCache*>(Entry.getFile().getContentCache());
1383   }
1384
1385   // If this is the first use of line information for this buffer, compute the
1386   /// SourceLineCache for it on demand.
1387   if (!Content->SourceLineCache) {
1388     bool MyInvalid = false;
1389     ComputeLineNumbers(Diag, Content, ContentCacheAlloc, *this, MyInvalid);
1390     if (Invalid)
1391       *Invalid = MyInvalid;
1392     if (MyInvalid)
1393       return 1;
1394   } else if (Invalid)
1395     *Invalid = false;
1396
1397   // Okay, we know we have a line number table.  Do a binary search to find the
1398   // line number that this character position lands on.
1399   unsigned *SourceLineCache = Content->SourceLineCache;
1400   unsigned *SourceLineCacheStart = SourceLineCache;
1401   unsigned *SourceLineCacheEnd = SourceLineCache + Content->NumLines;
1402
1403   unsigned QueriedFilePos = FilePos+1;
1404
1405   // FIXME: I would like to be convinced that this code is worth being as
1406   // complicated as it is, binary search isn't that slow.
1407   //
1408   // If it is worth being optimized, then in my opinion it could be more
1409   // performant, simpler, and more obviously correct by just "galloping" outward
1410   // from the queried file position. In fact, this could be incorporated into a
1411   // generic algorithm such as lower_bound_with_hint.
1412   //
1413   // If someone gives me a test case where this matters, and I will do it! - DWD
1414
1415   // If the previous query was to the same file, we know both the file pos from
1416   // that query and the line number returned.  This allows us to narrow the
1417   // search space from the entire file to something near the match.
1418   if (LastLineNoFileIDQuery == FID) {
1419     if (QueriedFilePos >= LastLineNoFilePos) {
1420       // FIXME: Potential overflow?
1421       SourceLineCache = SourceLineCache+LastLineNoResult-1;
1422
1423       // The query is likely to be nearby the previous one.  Here we check to
1424       // see if it is within 5, 10 or 20 lines.  It can be far away in cases
1425       // where big comment blocks and vertical whitespace eat up lines but
1426       // contribute no tokens.
1427       if (SourceLineCache+5 < SourceLineCacheEnd) {
1428         if (SourceLineCache[5] > QueriedFilePos)
1429           SourceLineCacheEnd = SourceLineCache+5;
1430         else if (SourceLineCache+10 < SourceLineCacheEnd) {
1431           if (SourceLineCache[10] > QueriedFilePos)
1432             SourceLineCacheEnd = SourceLineCache+10;
1433           else if (SourceLineCache+20 < SourceLineCacheEnd) {
1434             if (SourceLineCache[20] > QueriedFilePos)
1435               SourceLineCacheEnd = SourceLineCache+20;
1436           }
1437         }
1438       }
1439     } else {
1440       if (LastLineNoResult < Content->NumLines)
1441         SourceLineCacheEnd = SourceLineCache+LastLineNoResult+1;
1442     }
1443   }
1444
1445   unsigned *Pos
1446     = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
1447   unsigned LineNo = Pos-SourceLineCacheStart;
1448
1449   LastLineNoFileIDQuery = FID;
1450   LastLineNoContentCache = Content;
1451   LastLineNoFilePos = QueriedFilePos;
1452   LastLineNoResult = LineNo;
1453   return LineNo;
1454 }
1455
1456 unsigned SourceManager::getSpellingLineNumber(SourceLocation Loc,
1457                                               bool *Invalid) const {
1458   if (isInvalid(Loc, Invalid)) return 0;
1459   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc);
1460   return getLineNumber(LocInfo.first, LocInfo.second);
1461 }
1462 unsigned SourceManager::getExpansionLineNumber(SourceLocation Loc,
1463                                                bool *Invalid) const {
1464   if (isInvalid(Loc, Invalid)) return 0;
1465   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1466   return getLineNumber(LocInfo.first, LocInfo.second);
1467 }
1468 unsigned SourceManager::getPresumedLineNumber(SourceLocation Loc,
1469                                               bool *Invalid) const {
1470   PresumedLoc PLoc = getPresumedLoc(Loc);
1471   if (isInvalid(PLoc, Invalid)) return 0;
1472   return PLoc.getLine();
1473 }
1474
1475 /// getFileCharacteristic - return the file characteristic of the specified
1476 /// source location, indicating whether this is a normal file, a system
1477 /// header, or an "implicit extern C" system header.
1478 ///
1479 /// This state can be modified with flags on GNU linemarker directives like:
1480 ///   # 4 "foo.h" 3
1481 /// which changes all source locations in the current file after that to be
1482 /// considered to be from a system header.
1483 SrcMgr::CharacteristicKind
1484 SourceManager::getFileCharacteristic(SourceLocation Loc) const {
1485   assert(Loc.isValid() && "Can't get file characteristic of invalid loc!");
1486   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1487   bool Invalid = false;
1488   const SLocEntry &SEntry = getSLocEntry(LocInfo.first, &Invalid);
1489   if (Invalid || !SEntry.isFile())
1490     return C_User;
1491
1492   const SrcMgr::FileInfo &FI = SEntry.getFile();
1493
1494   // If there are no #line directives in this file, just return the whole-file
1495   // state.
1496   if (!FI.hasLineDirectives())
1497     return FI.getFileCharacteristic();
1498
1499   assert(LineTable && "Can't have linetable entries without a LineTable!");
1500   // See if there is a #line directive before the location.
1501   const LineEntry *Entry =
1502     LineTable->FindNearestLineEntry(LocInfo.first, LocInfo.second);
1503
1504   // If this is before the first line marker, use the file characteristic.
1505   if (!Entry)
1506     return FI.getFileCharacteristic();
1507
1508   return Entry->FileKind;
1509 }
1510
1511 /// Return the filename or buffer identifier of the buffer the location is in.
1512 /// Note that this name does not respect \#line directives.  Use getPresumedLoc
1513 /// for normal clients.
1514 StringRef SourceManager::getBufferName(SourceLocation Loc,
1515                                        bool *Invalid) const {
1516   if (isInvalid(Loc, Invalid)) return "<invalid loc>";
1517
1518   return getBuffer(getFileID(Loc), Invalid)->getBufferIdentifier();
1519 }
1520
1521 /// getPresumedLoc - This method returns the "presumed" location of a
1522 /// SourceLocation specifies.  A "presumed location" can be modified by \#line
1523 /// or GNU line marker directives.  This provides a view on the data that a
1524 /// user should see in diagnostics, for example.
1525 ///
1526 /// Note that a presumed location is always given as the expansion point of an
1527 /// expansion location, not at the spelling location.
1528 PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc,
1529                                           bool UseLineDirectives) const {
1530   if (Loc.isInvalid()) return PresumedLoc();
1531
1532   // Presumed locations are always for expansion points.
1533   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1534
1535   bool Invalid = false;
1536   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
1537   if (Invalid || !Entry.isFile())
1538     return PresumedLoc();
1539
1540   const SrcMgr::FileInfo &FI = Entry.getFile();
1541   const SrcMgr::ContentCache *C = FI.getContentCache();
1542
1543   // To get the source name, first consult the FileEntry (if one exists)
1544   // before the MemBuffer as this will avoid unnecessarily paging in the
1545   // MemBuffer.
1546   FileID FID = LocInfo.first;
1547   StringRef Filename;
1548   if (C->OrigEntry)
1549     Filename = C->OrigEntry->getName();
1550   else
1551     Filename = C->getBuffer(Diag, getFileManager())->getBufferIdentifier();
1552
1553   unsigned LineNo = getLineNumber(LocInfo.first, LocInfo.second, &Invalid);
1554   if (Invalid)
1555     return PresumedLoc();
1556   unsigned ColNo  = getColumnNumber(LocInfo.first, LocInfo.second, &Invalid);
1557   if (Invalid)
1558     return PresumedLoc();
1559
1560   SourceLocation IncludeLoc = FI.getIncludeLoc();
1561
1562   // If we have #line directives in this file, update and overwrite the physical
1563   // location info if appropriate.
1564   if (UseLineDirectives && FI.hasLineDirectives()) {
1565     assert(LineTable && "Can't have linetable entries without a LineTable!");
1566     // See if there is a #line directive before this.  If so, get it.
1567     if (const LineEntry *Entry =
1568           LineTable->FindNearestLineEntry(LocInfo.first, LocInfo.second)) {
1569       // If the LineEntry indicates a filename, use it.
1570       if (Entry->FilenameID != -1) {
1571         Filename = LineTable->getFilename(Entry->FilenameID);
1572         // The contents of files referenced by #line are not in the
1573         // SourceManager
1574         FID = FileID::get(0);
1575       }
1576
1577       // Use the line number specified by the LineEntry.  This line number may
1578       // be multiple lines down from the line entry.  Add the difference in
1579       // physical line numbers from the query point and the line marker to the
1580       // total.
1581       unsigned MarkerLineNo = getLineNumber(LocInfo.first, Entry->FileOffset);
1582       LineNo = Entry->LineNo + (LineNo-MarkerLineNo-1);
1583
1584       // Note that column numbers are not molested by line markers.
1585
1586       // Handle virtual #include manipulation.
1587       if (Entry->IncludeOffset) {
1588         IncludeLoc = getLocForStartOfFile(LocInfo.first);
1589         IncludeLoc = IncludeLoc.getLocWithOffset(Entry->IncludeOffset);
1590       }
1591     }
1592   }
1593
1594   return PresumedLoc(Filename.data(), FID, LineNo, ColNo, IncludeLoc);
1595 }
1596
1597 /// Returns whether the PresumedLoc for a given SourceLocation is
1598 /// in the main file.
1599 ///
1600 /// This computes the "presumed" location for a SourceLocation, then checks
1601 /// whether it came from a file other than the main file. This is different
1602 /// from isWrittenInMainFile() because it takes line marker directives into
1603 /// account.
1604 bool SourceManager::isInMainFile(SourceLocation Loc) const {
1605   if (Loc.isInvalid()) return false;
1606
1607   // Presumed locations are always for expansion points.
1608   std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc);
1609
1610   bool Invalid = false;
1611   const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid);
1612   if (Invalid || !Entry.isFile())
1613     return false;
1614
1615   const SrcMgr::FileInfo &FI = Entry.getFile();
1616
1617   // Check if there is a line directive for this location.
1618   if (FI.hasLineDirectives())
1619     if (const LineEntry *Entry =
1620             LineTable->FindNearestLineEntry(LocInfo.first, LocInfo.second))
1621       if (Entry->IncludeOffset)
1622         return false;
1623
1624   return FI.getIncludeLoc().isInvalid();
1625 }
1626
1627 /// The size of the SLocEntry that \p FID represents.
1628 unsigned SourceManager::getFileIDSize(FileID FID) const {
1629   bool Invalid = false;
1630   const SrcMgr::SLocEntry &Entry = getSLocEntry(FID, &Invalid);
1631   if (Invalid)
1632     return 0;
1633
1634   int ID = FID.ID;
1635   unsigned NextOffset;
1636   if ((ID > 0 && unsigned(ID+1) == local_sloc_entry_size()))
1637     NextOffset = getNextLocalOffset();
1638   else if (ID+1 == -1)
1639     NextOffset = MaxLoadedOffset;
1640   else
1641     NextOffset = getSLocEntry(FileID::get(ID+1)).getOffset();
1642
1643   return NextOffset - Entry.getOffset() - 1;
1644 }
1645
1646 //===----------------------------------------------------------------------===//
1647 // Other miscellaneous methods.
1648 //===----------------------------------------------------------------------===//
1649
1650 /// Get the source location for the given file:line:col triplet.
1651 ///
1652 /// If the source file is included multiple times, the source location will
1653 /// be based upon an arbitrary inclusion.
1654 SourceLocation SourceManager::translateFileLineCol(const FileEntry *SourceFile,
1655                                                   unsigned Line,
1656                                                   unsigned Col) const {
1657   assert(SourceFile && "Null source file!");
1658   assert(Line && Col && "Line and column should start from 1!");
1659
1660   FileID FirstFID = translateFile(SourceFile);
1661   return translateLineCol(FirstFID, Line, Col);
1662 }
1663
1664 /// Get the FileID for the given file.
1665 ///
1666 /// If the source file is included multiple times, the FileID will be the
1667 /// first inclusion.
1668 FileID SourceManager::translateFile(const FileEntry *SourceFile) const {
1669   assert(SourceFile && "Null source file!");
1670
1671   // First, check the main file ID, since it is common to look for a
1672   // location in the main file.
1673   if (MainFileID.isValid()) {
1674     bool Invalid = false;
1675     const SLocEntry &MainSLoc = getSLocEntry(MainFileID, &Invalid);
1676     if (Invalid)
1677       return FileID();
1678
1679     if (MainSLoc.isFile()) {
1680       const ContentCache *MainContentCache =
1681           MainSLoc.getFile().getContentCache();
1682       if (MainContentCache && MainContentCache->OrigEntry == SourceFile)
1683         return MainFileID;
1684     }
1685   }
1686
1687   // The location we're looking for isn't in the main file; look
1688   // through all of the local source locations.
1689   for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) {
1690     bool Invalid = false;
1691     const SLocEntry &SLoc = getLocalSLocEntry(I, &Invalid);
1692     if (Invalid)
1693       return FileID();
1694
1695     if (SLoc.isFile() && SLoc.getFile().getContentCache() &&
1696         SLoc.getFile().getContentCache()->OrigEntry == SourceFile)
1697       return FileID::get(I);
1698   }
1699
1700   // If that still didn't help, try the modules.
1701   for (unsigned I = 0, N = loaded_sloc_entry_size(); I != N; ++I) {
1702     const SLocEntry &SLoc = getLoadedSLocEntry(I);
1703     if (SLoc.isFile() && SLoc.getFile().getContentCache() &&
1704         SLoc.getFile().getContentCache()->OrigEntry == SourceFile)
1705       return FileID::get(-int(I) - 2);
1706   }
1707
1708   return FileID();
1709 }
1710
1711 /// Get the source location in \arg FID for the given line:col.
1712 /// Returns null location if \arg FID is not a file SLocEntry.
1713 SourceLocation SourceManager::translateLineCol(FileID FID,
1714                                                unsigned Line,
1715                                                unsigned Col) const {
1716   // Lines are used as a one-based index into a zero-based array. This assert
1717   // checks for possible buffer underruns.
1718   assert(Line && Col && "Line and column should start from 1!");
1719
1720   if (FID.isInvalid())
1721     return SourceLocation();
1722
1723   bool Invalid = false;
1724   const SLocEntry &Entry = getSLocEntry(FID, &Invalid);
1725   if (Invalid)
1726     return SourceLocation();
1727
1728   if (!Entry.isFile())
1729     return SourceLocation();
1730
1731   SourceLocation FileLoc = SourceLocation::getFileLoc(Entry.getOffset());
1732
1733   if (Line == 1 && Col == 1)
1734     return FileLoc;
1735
1736   ContentCache *Content
1737     = const_cast<ContentCache *>(Entry.getFile().getContentCache());
1738   if (!Content)
1739     return SourceLocation();
1740
1741   // If this is the first use of line information for this buffer, compute the
1742   // SourceLineCache for it on demand.
1743   if (!Content->SourceLineCache) {
1744     bool MyInvalid = false;
1745     ComputeLineNumbers(Diag, Content, ContentCacheAlloc, *this, MyInvalid);
1746     if (MyInvalid)
1747       return SourceLocation();
1748   }
1749
1750   if (Line > Content->NumLines) {
1751     unsigned Size = Content->getBuffer(Diag, getFileManager())->getBufferSize();
1752     if (Size > 0)
1753       --Size;
1754     return FileLoc.getLocWithOffset(Size);
1755   }
1756
1757   const llvm::MemoryBuffer *Buffer = Content->getBuffer(Diag, getFileManager());
1758   unsigned FilePos = Content->SourceLineCache[Line - 1];
1759   const char *Buf = Buffer->getBufferStart() + FilePos;
1760   unsigned BufLength = Buffer->getBufferSize() - FilePos;
1761   if (BufLength == 0)
1762     return FileLoc.getLocWithOffset(FilePos);
1763
1764   unsigned i = 0;
1765
1766   // Check that the given column is valid.
1767   while (i < BufLength-1 && i < Col-1 && Buf[i] != '\n' && Buf[i] != '\r')
1768     ++i;
1769   return FileLoc.getLocWithOffset(FilePos + i);
1770 }
1771
1772 /// Compute a map of macro argument chunks to their expanded source
1773 /// location. Chunks that are not part of a macro argument will map to an
1774 /// invalid source location. e.g. if a file contains one macro argument at
1775 /// offset 100 with length 10, this is how the map will be formed:
1776 ///     0   -> SourceLocation()
1777 ///     100 -> Expanded macro arg location
1778 ///     110 -> SourceLocation()
1779 void SourceManager::computeMacroArgsCache(MacroArgsMap &MacroArgsCache,
1780                                           FileID FID) const {
1781   assert(FID.isValid());
1782
1783   // Initially no macro argument chunk is present.
1784   MacroArgsCache.insert(std::make_pair(0, SourceLocation()));
1785
1786   int ID = FID.ID;
1787   while (true) {
1788     ++ID;
1789     // Stop if there are no more FileIDs to check.
1790     if (ID > 0) {
1791       if (unsigned(ID) >= local_sloc_entry_size())
1792         return;
1793     } else if (ID == -1) {
1794       return;
1795     }
1796
1797     bool Invalid = false;
1798     const SrcMgr::SLocEntry &Entry = getSLocEntryByID(ID, &Invalid);
1799     if (Invalid)
1800       return;
1801     if (Entry.isFile()) {
1802       SourceLocation IncludeLoc = Entry.getFile().getIncludeLoc();
1803       if (IncludeLoc.isInvalid())
1804         continue;
1805       if (!isInFileID(IncludeLoc, FID))
1806         return; // No more files/macros that may be "contained" in this file.
1807
1808       // Skip the files/macros of the #include'd file, we only care about macros
1809       // that lexed macro arguments from our file.
1810       if (Entry.getFile().NumCreatedFIDs)
1811         ID += Entry.getFile().NumCreatedFIDs - 1/*because of next ++ID*/;
1812       continue;
1813     }
1814
1815     const ExpansionInfo &ExpInfo = Entry.getExpansion();
1816
1817     if (ExpInfo.getExpansionLocStart().isFileID()) {
1818       if (!isInFileID(ExpInfo.getExpansionLocStart(), FID))
1819         return; // No more files/macros that may be "contained" in this file.
1820     }
1821
1822     if (!ExpInfo.isMacroArgExpansion())
1823       continue;
1824
1825     associateFileChunkWithMacroArgExp(MacroArgsCache, FID,
1826                                  ExpInfo.getSpellingLoc(),
1827                                  SourceLocation::getMacroLoc(Entry.getOffset()),
1828                                  getFileIDSize(FileID::get(ID)));
1829   }
1830 }
1831
1832 void SourceManager::associateFileChunkWithMacroArgExp(
1833                                          MacroArgsMap &MacroArgsCache,
1834                                          FileID FID,
1835                                          SourceLocation SpellLoc,
1836                                          SourceLocation ExpansionLoc,
1837                                          unsigned ExpansionLength) const {
1838   if (!SpellLoc.isFileID()) {
1839     unsigned SpellBeginOffs = SpellLoc.getOffset();
1840     unsigned SpellEndOffs = SpellBeginOffs + ExpansionLength;
1841
1842     // The spelling range for this macro argument expansion can span multiple
1843     // consecutive FileID entries. Go through each entry contained in the
1844     // spelling range and if one is itself a macro argument expansion, recurse
1845     // and associate the file chunk that it represents.
1846
1847     FileID SpellFID; // Current FileID in the spelling range.
1848     unsigned SpellRelativeOffs;
1849     std::tie(SpellFID, SpellRelativeOffs) = getDecomposedLoc(SpellLoc);
1850     while (true) {
1851       const SLocEntry &Entry = getSLocEntry(SpellFID);
1852       unsigned SpellFIDBeginOffs = Entry.getOffset();
1853       unsigned SpellFIDSize = getFileIDSize(SpellFID);
1854       unsigned SpellFIDEndOffs = SpellFIDBeginOffs + SpellFIDSize;
1855       const ExpansionInfo &Info = Entry.getExpansion();
1856       if (Info.isMacroArgExpansion()) {
1857         unsigned CurrSpellLength;
1858         if (SpellFIDEndOffs < SpellEndOffs)
1859           CurrSpellLength = SpellFIDSize - SpellRelativeOffs;
1860         else
1861           CurrSpellLength = ExpansionLength;
1862         associateFileChunkWithMacroArgExp(MacroArgsCache, FID,
1863                       Info.getSpellingLoc().getLocWithOffset(SpellRelativeOffs),
1864                       ExpansionLoc, CurrSpellLength);
1865       }
1866
1867       if (SpellFIDEndOffs >= SpellEndOffs)
1868         return; // we covered all FileID entries in the spelling range.
1869
1870       // Move to the next FileID entry in the spelling range.
1871       unsigned advance = SpellFIDSize - SpellRelativeOffs + 1;
1872       ExpansionLoc = ExpansionLoc.getLocWithOffset(advance);
1873       ExpansionLength -= advance;
1874       ++SpellFID.ID;
1875       SpellRelativeOffs = 0;
1876     }
1877   }
1878
1879   assert(SpellLoc.isFileID());
1880
1881   unsigned BeginOffs;
1882   if (!isInFileID(SpellLoc, FID, &BeginOffs))
1883     return;
1884
1885   unsigned EndOffs = BeginOffs + ExpansionLength;
1886
1887   // Add a new chunk for this macro argument. A previous macro argument chunk
1888   // may have been lexed again, so e.g. if the map is
1889   //     0   -> SourceLocation()
1890   //     100 -> Expanded loc #1
1891   //     110 -> SourceLocation()
1892   // and we found a new macro FileID that lexed from offset 105 with length 3,
1893   // the new map will be:
1894   //     0   -> SourceLocation()
1895   //     100 -> Expanded loc #1
1896   //     105 -> Expanded loc #2
1897   //     108 -> Expanded loc #1
1898   //     110 -> SourceLocation()
1899   //
1900   // Since re-lexed macro chunks will always be the same size or less of
1901   // previous chunks, we only need to find where the ending of the new macro
1902   // chunk is mapped to and update the map with new begin/end mappings.
1903
1904   MacroArgsMap::iterator I = MacroArgsCache.upper_bound(EndOffs);
1905   --I;
1906   SourceLocation EndOffsMappedLoc = I->second;
1907   MacroArgsCache[BeginOffs] = ExpansionLoc;
1908   MacroArgsCache[EndOffs] = EndOffsMappedLoc;
1909 }
1910
1911 /// If \arg Loc points inside a function macro argument, the returned
1912 /// location will be the macro location in which the argument was expanded.
1913 /// If a macro argument is used multiple times, the expanded location will
1914 /// be at the first expansion of the argument.
1915 /// e.g.
1916 ///   MY_MACRO(foo);
1917 ///             ^
1918 /// Passing a file location pointing at 'foo', will yield a macro location
1919 /// where 'foo' was expanded into.
1920 SourceLocation
1921 SourceManager::getMacroArgExpandedLocation(SourceLocation Loc) const {
1922   if (Loc.isInvalid() || !Loc.isFileID())
1923     return Loc;
1924
1925   FileID FID;
1926   unsigned Offset;
1927   std::tie(FID, Offset) = getDecomposedLoc(Loc);
1928   if (FID.isInvalid())
1929     return Loc;
1930
1931   std::unique_ptr<MacroArgsMap> &MacroArgsCache = MacroArgsCacheMap[FID];
1932   if (!MacroArgsCache) {
1933     MacroArgsCache = std::make_unique<MacroArgsMap>();
1934     computeMacroArgsCache(*MacroArgsCache, FID);
1935   }
1936
1937   assert(!MacroArgsCache->empty());
1938   MacroArgsMap::iterator I = MacroArgsCache->upper_bound(Offset);
1939   --I;
1940
1941   unsigned MacroArgBeginOffs = I->first;
1942   SourceLocation MacroArgExpandedLoc = I->second;
1943   if (MacroArgExpandedLoc.isValid())
1944     return MacroArgExpandedLoc.getLocWithOffset(Offset - MacroArgBeginOffs);
1945
1946   return Loc;
1947 }
1948
1949 std::pair<FileID, unsigned>
1950 SourceManager::getDecomposedIncludedLoc(FileID FID) const {
1951   if (FID.isInvalid())
1952     return std::make_pair(FileID(), 0);
1953
1954   // Uses IncludedLocMap to retrieve/cache the decomposed loc.
1955
1956   using DecompTy = std::pair<FileID, unsigned>;
1957   auto InsertOp = IncludedLocMap.try_emplace(FID);
1958   DecompTy &DecompLoc = InsertOp.first->second;
1959   if (!InsertOp.second)
1960     return DecompLoc; // already in map.
1961
1962   SourceLocation UpperLoc;
1963   bool Invalid = false;
1964   const SrcMgr::SLocEntry &Entry = getSLocEntry(FID, &Invalid);
1965   if (!Invalid) {
1966     if (Entry.isExpansion())
1967       UpperLoc = Entry.getExpansion().getExpansionLocStart();
1968     else
1969       UpperLoc = Entry.getFile().getIncludeLoc();
1970   }
1971
1972   if (UpperLoc.isValid())
1973     DecompLoc = getDecomposedLoc(UpperLoc);
1974
1975   return DecompLoc;
1976 }
1977
1978 /// Given a decomposed source location, move it up the include/expansion stack
1979 /// to the parent source location.  If this is possible, return the decomposed
1980 /// version of the parent in Loc and return false.  If Loc is the top-level
1981 /// entry, return true and don't modify it.
1982 static bool MoveUpIncludeHierarchy(std::pair<FileID, unsigned> &Loc,
1983                                    const SourceManager &SM) {
1984   std::pair<FileID, unsigned> UpperLoc = SM.getDecomposedIncludedLoc(Loc.first);
1985   if (UpperLoc.first.isInvalid())
1986     return true; // We reached the top.
1987
1988   Loc = UpperLoc;
1989   return false;
1990 }
1991
1992 /// Return the cache entry for comparing the given file IDs
1993 /// for isBeforeInTranslationUnit.
1994 InBeforeInTUCacheEntry &SourceManager::getInBeforeInTUCache(FileID LFID,
1995                                                             FileID RFID) const {
1996   // This is a magic number for limiting the cache size.  It was experimentally
1997   // derived from a small Objective-C project (where the cache filled
1998   // out to ~250 items).  We can make it larger if necessary.
1999   enum { MagicCacheSize = 300 };
2000   IsBeforeInTUCacheKey Key(LFID, RFID);
2001
2002   // If the cache size isn't too large, do a lookup and if necessary default
2003   // construct an entry.  We can then return it to the caller for direct
2004   // use.  When they update the value, the cache will get automatically
2005   // updated as well.
2006   if (IBTUCache.size() < MagicCacheSize)
2007     return IBTUCache[Key];
2008
2009   // Otherwise, do a lookup that will not construct a new value.
2010   InBeforeInTUCache::iterator I = IBTUCache.find(Key);
2011   if (I != IBTUCache.end())
2012     return I->second;
2013
2014   // Fall back to the overflow value.
2015   return IBTUCacheOverflow;
2016 }
2017
2018 /// Determines the order of 2 source locations in the translation unit.
2019 ///
2020 /// \returns true if LHS source location comes before RHS, false otherwise.
2021 bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
2022                                               SourceLocation RHS) const {
2023   assert(LHS.isValid() && RHS.isValid() && "Passed invalid source location!");
2024   if (LHS == RHS)
2025     return false;
2026
2027   std::pair<FileID, unsigned> LOffs = getDecomposedLoc(LHS);
2028   std::pair<FileID, unsigned> ROffs = getDecomposedLoc(RHS);
2029
2030   // getDecomposedLoc may have failed to return a valid FileID because, e.g. it
2031   // is a serialized one referring to a file that was removed after we loaded
2032   // the PCH.
2033   if (LOffs.first.isInvalid() || ROffs.first.isInvalid())
2034     return LOffs.first.isInvalid() && !ROffs.first.isInvalid();
2035
2036   std::pair<bool, bool> InSameTU = isInTheSameTranslationUnit(LOffs, ROffs);
2037   if (InSameTU.first)
2038     return InSameTU.second;
2039
2040   // If we arrived here, the location is either in a built-ins buffer or
2041   // associated with global inline asm. PR5662 and PR22576 are examples.
2042
2043   StringRef LB = getBuffer(LOffs.first)->getBufferIdentifier();
2044   StringRef RB = getBuffer(ROffs.first)->getBufferIdentifier();
2045   bool LIsBuiltins = LB == "<built-in>";
2046   bool RIsBuiltins = RB == "<built-in>";
2047   // Sort built-in before non-built-in.
2048   if (LIsBuiltins || RIsBuiltins) {
2049     if (LIsBuiltins != RIsBuiltins)
2050       return LIsBuiltins;
2051     // Both are in built-in buffers, but from different files. We just claim that
2052     // lower IDs come first.
2053     return LOffs.first < ROffs.first;
2054   }
2055   bool LIsAsm = LB == "<inline asm>";
2056   bool RIsAsm = RB == "<inline asm>";
2057   // Sort assembler after built-ins, but before the rest.
2058   if (LIsAsm || RIsAsm) {
2059     if (LIsAsm != RIsAsm)
2060       return RIsAsm;
2061     assert(LOffs.first == ROffs.first);
2062     return false;
2063   }
2064   bool LIsScratch = LB == "<scratch space>";
2065   bool RIsScratch = RB == "<scratch space>";
2066   // Sort scratch after inline asm, but before the rest.
2067   if (LIsScratch || RIsScratch) {
2068     if (LIsScratch != RIsScratch)
2069       return LIsScratch;
2070     return LOffs.second < ROffs.second;
2071   }
2072   llvm_unreachable("Unsortable locations found");
2073 }
2074
2075 std::pair<bool, bool> SourceManager::isInTheSameTranslationUnit(
2076     std::pair<FileID, unsigned> &LOffs,
2077     std::pair<FileID, unsigned> &ROffs) const {
2078   // If the source locations are in the same file, just compare offsets.
2079   if (LOffs.first == ROffs.first)
2080     return std::make_pair(true, LOffs.second < ROffs.second);
2081
2082   // If we are comparing a source location with multiple locations in the same
2083   // file, we get a big win by caching the result.
2084   InBeforeInTUCacheEntry &IsBeforeInTUCache =
2085     getInBeforeInTUCache(LOffs.first, ROffs.first);
2086
2087   // If we are comparing a source location with multiple locations in the same
2088   // file, we get a big win by caching the result.
2089   if (IsBeforeInTUCache.isCacheValid(LOffs.first, ROffs.first))
2090     return std::make_pair(
2091         true, IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second));
2092
2093   // Okay, we missed in the cache, start updating the cache for this query.
2094   IsBeforeInTUCache.setQueryFIDs(LOffs.first, ROffs.first,
2095                           /*isLFIDBeforeRFID=*/LOffs.first.ID < ROffs.first.ID);
2096
2097   // We need to find the common ancestor. The only way of doing this is to
2098   // build the complete include chain for one and then walking up the chain
2099   // of the other looking for a match.
2100   // We use a map from FileID to Offset to store the chain. Easier than writing
2101   // a custom set hash info that only depends on the first part of a pair.
2102   using LocSet = llvm::SmallDenseMap<FileID, unsigned, 16>;
2103   LocSet LChain;
2104   do {
2105     LChain.insert(LOffs);
2106     // We catch the case where LOffs is in a file included by ROffs and
2107     // quit early. The other way round unfortunately remains suboptimal.
2108   } while (LOffs.first != ROffs.first && !MoveUpIncludeHierarchy(LOffs, *this));
2109   LocSet::iterator I;
2110   while((I = LChain.find(ROffs.first)) == LChain.end()) {
2111     if (MoveUpIncludeHierarchy(ROffs, *this))
2112       break; // Met at topmost file.
2113   }
2114   if (I != LChain.end())
2115     LOffs = *I;
2116
2117   // If we exited because we found a nearest common ancestor, compare the
2118   // locations within the common file and cache them.
2119   if (LOffs.first == ROffs.first) {
2120     IsBeforeInTUCache.setCommonLoc(LOffs.first, LOffs.second, ROffs.second);
2121     return std::make_pair(
2122         true, IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second));
2123   }
2124   // Clear the lookup cache, it depends on a common location.
2125   IsBeforeInTUCache.clear();
2126   return std::make_pair(false, false);
2127 }
2128
2129 void SourceManager::PrintStats() const {
2130   llvm::errs() << "\n*** Source Manager Stats:\n";
2131   llvm::errs() << FileInfos.size() << " files mapped, " << MemBufferInfos.size()
2132                << " mem buffers mapped.\n";
2133   llvm::errs() << LocalSLocEntryTable.size() << " local SLocEntry's allocated ("
2134                << llvm::capacity_in_bytes(LocalSLocEntryTable)
2135                << " bytes of capacity), "
2136                << NextLocalOffset << "B of Sloc address space used.\n";
2137   llvm::errs() << LoadedSLocEntryTable.size()
2138                << " loaded SLocEntries allocated, "
2139                << MaxLoadedOffset - CurrentLoadedOffset
2140                << "B of Sloc address space used.\n";
2141
2142   unsigned NumLineNumsComputed = 0;
2143   unsigned NumFileBytesMapped = 0;
2144   for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
2145     NumLineNumsComputed += I->second->SourceLineCache != nullptr;
2146     NumFileBytesMapped  += I->second->getSizeBytesMapped();
2147   }
2148   unsigned NumMacroArgsComputed = MacroArgsCacheMap.size();
2149
2150   llvm::errs() << NumFileBytesMapped << " bytes of files mapped, "
2151                << NumLineNumsComputed << " files with line #'s computed, "
2152                << NumMacroArgsComputed << " files with macro args computed.\n";
2153   llvm::errs() << "FileID scans: " << NumLinearScans << " linear, "
2154                << NumBinaryProbes << " binary.\n";
2155 }
2156
2157 LLVM_DUMP_METHOD void SourceManager::dump() const {
2158   llvm::raw_ostream &out = llvm::errs();
2159
2160   auto DumpSLocEntry = [&](int ID, const SrcMgr::SLocEntry &Entry,
2161                            llvm::Optional<unsigned> NextStart) {
2162     out << "SLocEntry <FileID " << ID << "> " << (Entry.isFile() ? "file" : "expansion")
2163         << " <SourceLocation " << Entry.getOffset() << ":";
2164     if (NextStart)
2165       out << *NextStart << ">\n";
2166     else
2167       out << "???\?>\n";
2168     if (Entry.isFile()) {
2169       auto &FI = Entry.getFile();
2170       if (FI.NumCreatedFIDs)
2171         out << "  covers <FileID " << ID << ":" << int(ID + FI.NumCreatedFIDs)
2172             << ">\n";
2173       if (FI.getIncludeLoc().isValid())
2174         out << "  included from " << FI.getIncludeLoc().getOffset() << "\n";
2175       if (auto *CC = FI.getContentCache()) {
2176         out << "  for " << (CC->OrigEntry ? CC->OrigEntry->getName() : "<none>")
2177             << "\n";
2178         if (CC->BufferOverridden)
2179           out << "  contents overridden\n";
2180         if (CC->ContentsEntry != CC->OrigEntry) {
2181           out << "  contents from "
2182               << (CC->ContentsEntry ? CC->ContentsEntry->getName() : "<none>")
2183               << "\n";
2184         }
2185       }
2186     } else {
2187       auto &EI = Entry.getExpansion();
2188       out << "  spelling from " << EI.getSpellingLoc().getOffset() << "\n";
2189       out << "  macro " << (EI.isMacroArgExpansion() ? "arg" : "body")
2190           << " range <" << EI.getExpansionLocStart().getOffset() << ":"
2191           << EI.getExpansionLocEnd().getOffset() << ">\n";
2192     }
2193   };
2194
2195   // Dump local SLocEntries.
2196   for (unsigned ID = 0, NumIDs = LocalSLocEntryTable.size(); ID != NumIDs; ++ID) {
2197     DumpSLocEntry(ID, LocalSLocEntryTable[ID],
2198                   ID == NumIDs - 1 ? NextLocalOffset
2199                                    : LocalSLocEntryTable[ID + 1].getOffset());
2200   }
2201   // Dump loaded SLocEntries.
2202   llvm::Optional<unsigned> NextStart;
2203   for (unsigned Index = 0; Index != LoadedSLocEntryTable.size(); ++Index) {
2204     int ID = -(int)Index - 2;
2205     if (SLocEntryLoaded[Index]) {
2206       DumpSLocEntry(ID, LoadedSLocEntryTable[Index], NextStart);
2207       NextStart = LoadedSLocEntryTable[Index].getOffset();
2208     } else {
2209       NextStart = None;
2210     }
2211   }
2212 }
2213
2214 ExternalSLocEntrySource::~ExternalSLocEntrySource() = default;
2215
2216 /// Return the amount of memory used by memory buffers, breaking down
2217 /// by heap-backed versus mmap'ed memory.
2218 SourceManager::MemoryBufferSizes SourceManager::getMemoryBufferSizes() const {
2219   size_t malloc_bytes = 0;
2220   size_t mmap_bytes = 0;
2221
2222   for (unsigned i = 0, e = MemBufferInfos.size(); i != e; ++i)
2223     if (size_t sized_mapped = MemBufferInfos[i]->getSizeBytesMapped())
2224       switch (MemBufferInfos[i]->getMemoryBufferKind()) {
2225         case llvm::MemoryBuffer::MemoryBuffer_MMap:
2226           mmap_bytes += sized_mapped;
2227           break;
2228         case llvm::MemoryBuffer::MemoryBuffer_Malloc:
2229           malloc_bytes += sized_mapped;
2230           break;
2231       }
2232
2233   return MemoryBufferSizes(malloc_bytes, mmap_bytes);
2234 }
2235
2236 size_t SourceManager::getDataStructureSizes() const {
2237   size_t size = llvm::capacity_in_bytes(MemBufferInfos)
2238     + llvm::capacity_in_bytes(LocalSLocEntryTable)
2239     + llvm::capacity_in_bytes(LoadedSLocEntryTable)
2240     + llvm::capacity_in_bytes(SLocEntryLoaded)
2241     + llvm::capacity_in_bytes(FileInfos);
2242
2243   if (OverriddenFilesInfo)
2244     size += llvm::capacity_in_bytes(OverriddenFilesInfo->OverriddenFiles);
2245
2246   return size;
2247 }
2248
2249 SourceManagerForFile::SourceManagerForFile(StringRef FileName,
2250                                            StringRef Content) {
2251   // This is referenced by `FileMgr` and will be released by `FileMgr` when it
2252   // is deleted.
2253   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem(
2254       new llvm::vfs::InMemoryFileSystem);
2255   InMemoryFileSystem->addFile(
2256       FileName, 0,
2257       llvm::MemoryBuffer::getMemBuffer(Content, FileName,
2258                                        /*RequiresNullTerminator=*/false));
2259   // This is passed to `SM` as reference, so the pointer has to be referenced
2260   // in `Environment` so that `FileMgr` can out-live this function scope.
2261   FileMgr =
2262       std::make_unique<FileManager>(FileSystemOptions(), InMemoryFileSystem);
2263   // This is passed to `SM` as reference, so the pointer has to be referenced
2264   // by `Environment` due to the same reason above.
2265   Diagnostics = std::make_unique<DiagnosticsEngine>(
2266       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
2267       new DiagnosticOptions);
2268   SourceMgr = std::make_unique<SourceManager>(*Diagnostics, *FileMgr);
2269   FileID ID = SourceMgr->createFileID(*FileMgr->getFile(FileName),
2270                                       SourceLocation(), clang::SrcMgr::C_User);
2271   assert(ID.isValid());
2272   SourceMgr->setMainFileID(ID);
2273 }