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