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