Clang Project

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