1 //===--- SourceManager.cpp - Track and cache source files -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SourceManager interface.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Basic/SourceManager.h"
15 #include "clang/Basic/SourceManagerInternals.h"
16 #include "clang/Basic/Diagnostic.h"
17 #include "clang/Basic/FileManager.h"
18 #include "llvm/ADT/StringSwitch.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/MemoryBuffer.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/Support/Path.h"
29 using namespace clang
;
30 using namespace SrcMgr
;
31 using llvm::MemoryBuffer
;
33 //===----------------------------------------------------------------------===//
34 // SourceManager Helper Classes
35 //===----------------------------------------------------------------------===//
37 ContentCache::~ContentCache() {
38 if (shouldFreeBuffer())
39 delete Buffer
.getPointer();
42 /// getSizeBytesMapped - Returns the number of bytes actually mapped for
43 /// this ContentCache. This can be 0 if the MemBuffer was not actually
45 unsigned ContentCache::getSizeBytesMapped() const {
46 return Buffer
.getPointer() ? Buffer
.getPointer()->getBufferSize() : 0;
49 /// getSize - Returns the size of the content encapsulated by this ContentCache.
50 /// This can be the size of the source file or the size of an arbitrary
51 /// scratch buffer. If the ContentCache encapsulates a source file, that
52 /// file is not lazily brought in from disk to satisfy this query.
53 unsigned ContentCache::getSize() const {
54 return Buffer
.getPointer() ? (unsigned) Buffer
.getPointer()->getBufferSize()
55 : (unsigned) Entry
->getSize();
58 void ContentCache::replaceBuffer(const llvm::MemoryBuffer
*B
,
60 assert(B
!= Buffer
.getPointer());
62 if (shouldFreeBuffer())
63 delete Buffer
.getPointer();
65 Buffer
.setInt(DoNotFree
? DoNotFreeFlag
: 0);
68 const llvm::MemoryBuffer
*ContentCache::getBuffer(Diagnostic
&Diag
,
69 const SourceManager
&SM
,
71 bool *Invalid
) const {
72 // Lazily create the Buffer for ContentCaches that wrap files. If we already
73 // computed it, jsut return what we have.
74 if (Buffer
.getPointer() || Entry
== 0) {
76 *Invalid
= isBufferInvalid();
78 return Buffer
.getPointer();
82 Buffer
.setPointer(SM
.getFileManager().getBufferForFile(Entry
, &ErrorStr
));
84 // If we were unable to open the file, then we are in an inconsistent
85 // situation where the content cache referenced a file which no longer
86 // exists. Most likely, we were using a stat cache with an invalid entry but
87 // the file could also have been removed during processing. Since we can't
88 // really deal with this situation, just create an empty buffer.
90 // FIXME: This is definitely not ideal, but our immediate clients can't
91 // currently handle returning a null entry here. Ideally we should detect
92 // that we are in an inconsistent situation and error out as quickly as
94 if (!Buffer
.getPointer()) {
95 const llvm::StringRef
FillStr("<<<MISSING SOURCE FILE>>>\n");
96 Buffer
.setPointer(MemoryBuffer::getNewMemBuffer(Entry
->getSize(),
98 char *Ptr
= const_cast<char*>(Buffer
.getPointer()->getBufferStart());
99 for (unsigned i
= 0, e
= Entry
->getSize(); i
!= e
; ++i
)
100 Ptr
[i
] = FillStr
[i
% FillStr
.size()];
102 if (Diag
.isDiagnosticInFlight())
103 Diag
.SetDelayedDiagnostic(diag::err_cannot_open_file
,
104 Entry
->getName(), ErrorStr
);
106 Diag
.Report(Loc
, diag::err_cannot_open_file
)
107 << Entry
->getName() << ErrorStr
;
109 Buffer
.setInt(Buffer
.getInt() | InvalidFlag
);
111 if (Invalid
) *Invalid
= true;
112 return Buffer
.getPointer();
115 // Check that the file's size is the same as in the file entry (which may
116 // have come from a stat cache).
117 if (getRawBuffer()->getBufferSize() != (size_t)Entry
->getSize()) {
118 if (Diag
.isDiagnosticInFlight())
119 Diag
.SetDelayedDiagnostic(diag::err_file_modified
,
122 Diag
.Report(Loc
, diag::err_file_modified
)
125 Buffer
.setInt(Buffer
.getInt() | InvalidFlag
);
126 if (Invalid
) *Invalid
= true;
127 return Buffer
.getPointer();
130 // If the buffer is valid, check to see if it has a UTF Byte Order Mark
131 // (BOM). We only support UTF-8 without a BOM right now. See
132 // http://en.wikipedia.org/wiki/Byte_order_mark for more information.
133 llvm::StringRef BufStr
= Buffer
.getPointer()->getBuffer();
134 const char *BOM
= llvm::StringSwitch
<const char *>(BufStr
)
135 .StartsWith("\xEF\xBB\xBF", "UTF-8")
136 .StartsWith("\xFE\xFF", "UTF-16 (BE)")
137 .StartsWith("\xFF\xFE", "UTF-16 (LE)")
138 .StartsWith("\x00\x00\xFE\xFF", "UTF-32 (BE)")
139 .StartsWith("\xFF\xFE\x00\x00", "UTF-32 (LE)")
140 .StartsWith("\x2B\x2F\x76", "UTF-7")
141 .StartsWith("\xF7\x64\x4C", "UTF-1")
142 .StartsWith("\xDD\x73\x66\x73", "UTF-EBCDIC")
143 .StartsWith("\x0E\xFE\xFF", "SDSU")
144 .StartsWith("\xFB\xEE\x28", "BOCU-1")
145 .StartsWith("\x84\x31\x95\x33", "GB-18030")
149 Diag
.Report(Loc
, diag::err_unsupported_bom
)
150 << BOM
<< Entry
->getName();
151 Buffer
.setInt(Buffer
.getInt() | InvalidFlag
);
155 *Invalid
= isBufferInvalid();
157 return Buffer
.getPointer();
160 unsigned LineTableInfo::getLineTableFilenameID(const char *Ptr
, unsigned Len
) {
161 // Look up the filename in the string table, returning the pre-existing value
163 llvm::StringMapEntry
<unsigned> &Entry
=
164 FilenameIDs
.GetOrCreateValue(Ptr
, Ptr
+Len
, ~0U);
165 if (Entry
.getValue() != ~0U)
166 return Entry
.getValue();
168 // Otherwise, assign this the next available ID.
169 Entry
.setValue(FilenamesByID
.size());
170 FilenamesByID
.push_back(&Entry
);
171 return FilenamesByID
.size()-1;
174 /// AddLineNote - Add a line note to the line table that indicates that there
175 /// is a #line at the specified FID/Offset location which changes the presumed
176 /// location to LineNo/FilenameID.
177 void LineTableInfo::AddLineNote(unsigned FID
, unsigned Offset
,
178 unsigned LineNo
, int FilenameID
) {
179 std::vector
<LineEntry
> &Entries
= LineEntries
[FID
];
181 assert((Entries
.empty() || Entries
.back().FileOffset
< Offset
) &&
182 "Adding line entries out of order!");
184 SrcMgr::CharacteristicKind Kind
= SrcMgr::C_User
;
185 unsigned IncludeOffset
= 0;
187 if (!Entries
.empty()) {
188 // If this is a '#line 4' after '#line 42 "foo.h"', make sure to remember
189 // that we are still in "foo.h".
190 if (FilenameID
== -1)
191 FilenameID
= Entries
.back().FilenameID
;
193 // If we are after a line marker that switched us to system header mode, or
194 // that set #include information, preserve it.
195 Kind
= Entries
.back().FileKind
;
196 IncludeOffset
= Entries
.back().IncludeOffset
;
199 Entries
.push_back(LineEntry::get(Offset
, LineNo
, FilenameID
, Kind
,
203 /// AddLineNote This is the same as the previous version of AddLineNote, but is
204 /// used for GNU line markers. If EntryExit is 0, then this doesn't change the
205 /// presumed #include stack. If it is 1, this is a file entry, if it is 2 then
206 /// this is a file exit. FileKind specifies whether this is a system header or
207 /// extern C system header.
208 void LineTableInfo::AddLineNote(unsigned FID
, unsigned Offset
,
209 unsigned LineNo
, int FilenameID
,
211 SrcMgr::CharacteristicKind FileKind
) {
212 assert(FilenameID
!= -1 && "Unspecified filename should use other accessor");
214 std::vector
<LineEntry
> &Entries
= LineEntries
[FID
];
216 assert((Entries
.empty() || Entries
.back().FileOffset
< Offset
) &&
217 "Adding line entries out of order!");
219 unsigned IncludeOffset
= 0;
220 if (EntryExit
== 0) { // No #include stack change.
221 IncludeOffset
= Entries
.empty() ? 0 : Entries
.back().IncludeOffset
;
222 } else if (EntryExit
== 1) {
223 IncludeOffset
= Offset
-1;
224 } else if (EntryExit
== 2) {
225 assert(!Entries
.empty() && Entries
.back().IncludeOffset
&&
226 "PPDirectives should have caught case when popping empty include stack");
228 // Get the include loc of the last entries' include loc as our include loc.
230 if (const LineEntry
*PrevEntry
=
231 FindNearestLineEntry(FID
, Entries
.back().IncludeOffset
))
232 IncludeOffset
= PrevEntry
->IncludeOffset
;
235 Entries
.push_back(LineEntry::get(Offset
, LineNo
, FilenameID
, FileKind
,
240 /// FindNearestLineEntry - Find the line entry nearest to FID that is before
241 /// it. If there is no line entry before Offset in FID, return null.
242 const LineEntry
*LineTableInfo::FindNearestLineEntry(unsigned FID
,
244 const std::vector
<LineEntry
> &Entries
= LineEntries
[FID
];
245 assert(!Entries
.empty() && "No #line entries for this FID after all!");
247 // It is very common for the query to be after the last #line, check this
249 if (Entries
.back().FileOffset
<= Offset
)
250 return &Entries
.back();
252 // Do a binary search to find the maximal element that is still before Offset.
253 std::vector
<LineEntry
>::const_iterator I
=
254 std::upper_bound(Entries
.begin(), Entries
.end(), Offset
);
255 if (I
== Entries
.begin()) return 0;
259 /// \brief Add a new line entry that has already been encoded into
260 /// the internal representation of the line table.
261 void LineTableInfo::AddEntry(unsigned FID
,
262 const std::vector
<LineEntry
> &Entries
) {
263 LineEntries
[FID
] = Entries
;
266 /// getLineTableFilenameID - Return the uniqued ID for the specified filename.
268 unsigned SourceManager::getLineTableFilenameID(const char *Ptr
, unsigned Len
) {
270 LineTable
= new LineTableInfo();
271 return LineTable
->getLineTableFilenameID(Ptr
, Len
);
275 /// AddLineNote - Add a line note to the line table for the FileID and offset
276 /// specified by Loc. If FilenameID is -1, it is considered to be
278 void SourceManager::AddLineNote(SourceLocation Loc
, unsigned LineNo
,
280 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedInstantiationLoc(Loc
);
282 const SrcMgr::FileInfo
&FileInfo
= getSLocEntry(LocInfo
.first
).getFile();
284 // Remember that this file has #line directives now if it doesn't already.
285 const_cast<SrcMgr::FileInfo
&>(FileInfo
).setHasLineDirectives();
288 LineTable
= new LineTableInfo();
289 LineTable
->AddLineNote(LocInfo
.first
.ID
, LocInfo
.second
, LineNo
, FilenameID
);
292 /// AddLineNote - Add a GNU line marker to the line table.
293 void SourceManager::AddLineNote(SourceLocation Loc
, unsigned LineNo
,
294 int FilenameID
, bool IsFileEntry
,
295 bool IsFileExit
, bool IsSystemHeader
,
296 bool IsExternCHeader
) {
297 // If there is no filename and no flags, this is treated just like a #line,
298 // which does not change the flags of the previous line marker.
299 if (FilenameID
== -1) {
300 assert(!IsFileEntry
&& !IsFileExit
&& !IsSystemHeader
&& !IsExternCHeader
&&
301 "Can't set flags without setting the filename!");
302 return AddLineNote(Loc
, LineNo
, FilenameID
);
305 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedInstantiationLoc(Loc
);
306 const SrcMgr::FileInfo
&FileInfo
= getSLocEntry(LocInfo
.first
).getFile();
308 // Remember that this file has #line directives now if it doesn't already.
309 const_cast<SrcMgr::FileInfo
&>(FileInfo
).setHasLineDirectives();
312 LineTable
= new LineTableInfo();
314 SrcMgr::CharacteristicKind FileKind
;
316 FileKind
= SrcMgr::C_ExternCSystem
;
317 else if (IsSystemHeader
)
318 FileKind
= SrcMgr::C_System
;
320 FileKind
= SrcMgr::C_User
;
322 unsigned EntryExit
= 0;
328 LineTable
->AddLineNote(LocInfo
.first
.ID
, LocInfo
.second
, LineNo
, FilenameID
,
329 EntryExit
, FileKind
);
332 LineTableInfo
&SourceManager::getLineTable() {
334 LineTable
= new LineTableInfo();
338 //===----------------------------------------------------------------------===//
339 // Private 'Create' methods.
340 //===----------------------------------------------------------------------===//
342 SourceManager::SourceManager(Diagnostic
&Diag
, FileManager
&FileMgr
)
343 : Diag(Diag
), FileMgr(FileMgr
),
344 ExternalSLocEntries(0), LineTable(0), NumLinearScans(0),
347 Diag
.setSourceManager(this);
350 SourceManager::~SourceManager() {
353 // Delete FileEntry objects corresponding to content caches. Since the actual
354 // content cache objects are bump pointer allocated, we just have to run the
355 // dtors, but we call the deallocate method for completeness.
356 for (unsigned i
= 0, e
= MemBufferInfos
.size(); i
!= e
; ++i
) {
357 MemBufferInfos
[i
]->~ContentCache();
358 ContentCacheAlloc
.Deallocate(MemBufferInfos
[i
]);
360 for (llvm::DenseMap
<const FileEntry
*, SrcMgr::ContentCache
*>::iterator
361 I
= FileInfos
.begin(), E
= FileInfos
.end(); I
!= E
; ++I
) {
362 I
->second
->~ContentCache();
363 ContentCacheAlloc
.Deallocate(I
->second
);
367 void SourceManager::clearIDTables() {
368 MainFileID
= FileID();
369 SLocEntryTable
.clear();
370 LastLineNoFileIDQuery
= FileID();
371 LastLineNoContentCache
= 0;
372 LastFileIDLookup
= FileID();
377 // Use up FileID #0 as an invalid instantiation.
379 createInstantiationLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1);
382 /// getOrCreateContentCache - Create or return a cached ContentCache for the
385 SourceManager::getOrCreateContentCache(const FileEntry
*FileEnt
) {
386 assert(FileEnt
&& "Didn't specify a file entry to use?");
388 // Do we already have information about this file?
389 ContentCache
*&Entry
= FileInfos
[FileEnt
];
390 if (Entry
) return Entry
;
392 // Nope, create a new Cache entry. Make sure it is at least 8-byte aligned
393 // so that FileInfo can use the low 3 bits of the pointer for its own
394 // nefarious purposes.
395 unsigned EntryAlign
= llvm::AlignOf
<ContentCache
>::Alignment
;
396 EntryAlign
= std::max(8U, EntryAlign
);
397 Entry
= ContentCacheAlloc
.Allocate
<ContentCache
>(1, EntryAlign
);
398 new (Entry
) ContentCache(FileEnt
);
403 /// createMemBufferContentCache - Create a new ContentCache for the specified
404 /// memory buffer. This does no caching.
406 SourceManager::createMemBufferContentCache(const MemoryBuffer
*Buffer
) {
407 // Add a new ContentCache to the MemBufferInfos list and return it. Make sure
408 // it is at least 8-byte aligned so that FileInfo can use the low 3 bits of
409 // the pointer for its own nefarious purposes.
410 unsigned EntryAlign
= llvm::AlignOf
<ContentCache
>::Alignment
;
411 EntryAlign
= std::max(8U, EntryAlign
);
412 ContentCache
*Entry
= ContentCacheAlloc
.Allocate
<ContentCache
>(1, EntryAlign
);
413 new (Entry
) ContentCache();
414 MemBufferInfos
.push_back(Entry
);
415 Entry
->setBuffer(Buffer
);
419 void SourceManager::PreallocateSLocEntries(ExternalSLocEntrySource
*Source
,
420 unsigned NumSLocEntries
,
421 unsigned NextOffset
) {
422 ExternalSLocEntries
= Source
;
423 this->NextOffset
= NextOffset
;
424 unsigned CurPrealloc
= SLocEntryLoaded
.size();
425 // If we've ever preallocated, we must not count the dummy entry.
426 if (CurPrealloc
) --CurPrealloc
;
427 SLocEntryLoaded
.resize(NumSLocEntries
+ 1);
428 SLocEntryLoaded
[0] = true;
429 SLocEntryTable
.resize(SLocEntryTable
.size() + NumSLocEntries
- CurPrealloc
);
432 void SourceManager::ClearPreallocatedSLocEntries() {
434 for (unsigned N
= SLocEntryLoaded
.size(); I
!= N
; ++I
)
435 if (!SLocEntryLoaded
[I
])
438 // We've already loaded all preallocated source location entries.
439 if (I
== SLocEntryLoaded
.size())
442 // Remove everything from location I onward.
443 SLocEntryTable
.resize(I
);
444 SLocEntryLoaded
.clear();
445 ExternalSLocEntries
= 0;
449 //===----------------------------------------------------------------------===//
450 // Methods to create new FileID's and instantiations.
451 //===----------------------------------------------------------------------===//
453 /// createFileID - Create a new FileID for the specified ContentCache and
454 /// include position. This works regardless of whether the ContentCache
455 /// corresponds to a file or some other input source.
456 FileID
SourceManager::createFileID(const ContentCache
*File
,
457 SourceLocation IncludePos
,
458 SrcMgr::CharacteristicKind FileCharacter
,
459 unsigned PreallocatedID
,
461 if (PreallocatedID
) {
462 // If we're filling in a preallocated ID, just load in the file
464 assert(PreallocatedID
< SLocEntryLoaded
.size() &&
465 "Preallocate ID out-of-range");
466 assert(!SLocEntryLoaded
[PreallocatedID
] &&
467 "Source location entry already loaded");
468 assert(Offset
&& "Preallocate source location cannot have zero offset");
469 SLocEntryTable
[PreallocatedID
]
470 = SLocEntry::get(Offset
, FileInfo::get(IncludePos
, File
, FileCharacter
));
471 SLocEntryLoaded
[PreallocatedID
] = true;
472 FileID FID
= FileID::get(PreallocatedID
);
476 SLocEntryTable
.push_back(SLocEntry::get(NextOffset
,
477 FileInfo::get(IncludePos
, File
,
479 unsigned FileSize
= File
->getSize();
480 assert(NextOffset
+FileSize
+1 > NextOffset
&& "Ran out of source locations!");
481 NextOffset
+= FileSize
+1;
483 // Set LastFileIDLookup to the newly created file. The next getFileID call is
484 // almost guaranteed to be from that file.
485 FileID FID
= FileID::get(SLocEntryTable
.size()-1);
486 return LastFileIDLookup
= FID
;
489 /// createInstantiationLoc - Return a new SourceLocation that encodes the fact
490 /// that a token from SpellingLoc should actually be referenced from
491 /// InstantiationLoc.
492 SourceLocation
SourceManager::createInstantiationLoc(SourceLocation SpellingLoc
,
493 SourceLocation ILocStart
,
494 SourceLocation ILocEnd
,
496 unsigned PreallocatedID
,
498 InstantiationInfo II
= InstantiationInfo::get(ILocStart
,ILocEnd
, SpellingLoc
);
499 if (PreallocatedID
) {
500 // If we're filling in a preallocated ID, just load in the
501 // instantiation entry and return.
502 assert(PreallocatedID
< SLocEntryLoaded
.size() &&
503 "Preallocate ID out-of-range");
504 assert(!SLocEntryLoaded
[PreallocatedID
] &&
505 "Source location entry already loaded");
506 assert(Offset
&& "Preallocate source location cannot have zero offset");
507 SLocEntryTable
[PreallocatedID
] = SLocEntry::get(Offset
, II
);
508 SLocEntryLoaded
[PreallocatedID
] = true;
509 return SourceLocation::getMacroLoc(Offset
);
511 SLocEntryTable
.push_back(SLocEntry::get(NextOffset
, II
));
512 assert(NextOffset
+TokLength
+1 > NextOffset
&& "Ran out of source locations!");
513 NextOffset
+= TokLength
+1;
514 return SourceLocation::getMacroLoc(NextOffset
-(TokLength
+1));
517 const llvm::MemoryBuffer
*
518 SourceManager::getMemoryBufferForFile(const FileEntry
*File
,
520 const SrcMgr::ContentCache
*IR
= getOrCreateContentCache(File
);
521 assert(IR
&& "getOrCreateContentCache() cannot return NULL");
522 return IR
->getBuffer(Diag
, *this, SourceLocation(), Invalid
);
525 void SourceManager::overrideFileContents(const FileEntry
*SourceFile
,
526 const llvm::MemoryBuffer
*Buffer
,
528 const SrcMgr::ContentCache
*IR
= getOrCreateContentCache(SourceFile
);
529 assert(IR
&& "getOrCreateContentCache() cannot return NULL");
531 const_cast<SrcMgr::ContentCache
*>(IR
)->replaceBuffer(Buffer
, DoNotFree
);
534 llvm::StringRef
SourceManager::getBufferData(FileID FID
, bool *Invalid
) const {
535 bool MyInvalid
= false;
536 const SLocEntry
&SLoc
= getSLocEntry(FID
.ID
);
537 if (!SLoc
.isFile()) {
540 return "<<<<<INVALID SOURCE LOCATION>>>>>";
543 const llvm::MemoryBuffer
*Buf
544 = SLoc
.getFile().getContentCache()->getBuffer(Diag
, *this, SourceLocation(),
547 *Invalid
= MyInvalid
;
550 return "<<<<<INVALID SOURCE LOCATION>>>>>";
552 return Buf
->getBuffer();
555 //===----------------------------------------------------------------------===//
556 // SourceLocation manipulation methods.
557 //===----------------------------------------------------------------------===//
559 /// getFileIDSlow - Return the FileID for a SourceLocation. This is a very hot
560 /// method that is used for all SourceManager queries that start with a
561 /// SourceLocation object. It is responsible for finding the entry in
562 /// SLocEntryTable which contains the specified location.
564 FileID
SourceManager::getFileIDSlow(unsigned SLocOffset
) const {
565 assert(SLocOffset
&& "Invalid FileID");
567 // After the first and second level caches, I see two common sorts of
568 // behavior: 1) a lot of searched FileID's are "near" the cached file location
569 // or are "near" the cached instantiation location. 2) others are just
570 // completely random and may be a very long way away.
572 // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
573 // then we fall back to a less cache efficient, but more scalable, binary
574 // search to find the location.
576 // See if this is near the file point - worst case we start scanning from the
577 // most newly created FileID.
578 std::vector
<SrcMgr::SLocEntry
>::const_iterator I
;
580 if (SLocEntryTable
[LastFileIDLookup
.ID
].getOffset() < SLocOffset
) {
581 // Neither loc prunes our search.
582 I
= SLocEntryTable
.end();
584 // Perhaps it is near the file point.
585 I
= SLocEntryTable
.begin()+LastFileIDLookup
.ID
;
588 // Find the FileID that contains this. "I" is an iterator that points to a
589 // FileID whose offset is known to be larger than SLocOffset.
590 unsigned NumProbes
= 0;
593 if (ExternalSLocEntries
)
594 getSLocEntry(FileID::get(I
- SLocEntryTable
.begin()));
595 if (I
->getOffset() <= SLocOffset
) {
597 printf("lin %d -> %d [%s] %d %d\n", SLocOffset
,
598 I
-SLocEntryTable
.begin(),
599 I
->isInstantiation() ? "inst" : "file",
600 LastFileIDLookup
.ID
, int(SLocEntryTable
.end()-I
));
602 FileID Res
= FileID::get(I
-SLocEntryTable
.begin());
604 // If this isn't an instantiation, remember it. We have good locality
605 // across FileID lookups.
606 if (!I
->isInstantiation())
607 LastFileIDLookup
= Res
;
608 NumLinearScans
+= NumProbes
+1;
611 if (++NumProbes
== 8)
615 // Convert "I" back into an index. We know that it is an entry whose index is
616 // larger than the offset we are looking for.
617 unsigned GreaterIndex
= I
-SLocEntryTable
.begin();
618 // LessIndex - This is the lower bound of the range that we're searching.
619 // We know that the offset corresponding to the FileID is is less than
621 unsigned LessIndex
= 0;
624 unsigned MiddleIndex
= (GreaterIndex
-LessIndex
)/2+LessIndex
;
625 unsigned MidOffset
= getSLocEntry(FileID::get(MiddleIndex
)).getOffset();
629 // If the offset of the midpoint is too large, chop the high side of the
630 // range to the midpoint.
631 if (MidOffset
> SLocOffset
) {
632 GreaterIndex
= MiddleIndex
;
636 // If the middle index contains the value, succeed and return.
637 if (isOffsetInFileID(FileID::get(MiddleIndex
), SLocOffset
)) {
639 printf("bin %d -> %d [%s] %d %d\n", SLocOffset
,
640 I
-SLocEntryTable
.begin(),
641 I
->isInstantiation() ? "inst" : "file",
642 LastFileIDLookup
.ID
, int(SLocEntryTable
.end()-I
));
644 FileID Res
= FileID::get(MiddleIndex
);
646 // If this isn't an instantiation, remember it. We have good locality
647 // across FileID lookups.
648 if (!I
->isInstantiation())
649 LastFileIDLookup
= Res
;
650 NumBinaryProbes
+= NumProbes
;
654 // Otherwise, move the low-side up to the middle index.
655 LessIndex
= MiddleIndex
;
659 SourceLocation
SourceManager::
660 getInstantiationLocSlowCase(SourceLocation Loc
) const {
662 // Note: If Loc indicates an offset into a token that came from a macro
663 // expansion (e.g. the 5th character of the token) we do not want to add
664 // this offset when going to the instantiation location. The instatiation
665 // location is the macro invocation, which the offset has nothing to do
666 // with. This is unlike when we get the spelling loc, because the offset
667 // directly correspond to the token whose spelling we're inspecting.
668 Loc
= getSLocEntry(getFileID(Loc
)).getInstantiation()
669 .getInstantiationLocStart();
670 } while (!Loc
.isFileID());
675 SourceLocation
SourceManager::getSpellingLocSlowCase(SourceLocation Loc
) const {
677 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedLoc(Loc
);
678 Loc
= getSLocEntry(LocInfo
.first
).getInstantiation().getSpellingLoc();
679 Loc
= Loc
.getFileLocWithOffset(LocInfo
.second
);
680 } while (!Loc
.isFileID());
685 std::pair
<FileID
, unsigned>
686 SourceManager::getDecomposedInstantiationLocSlowCase(const SrcMgr::SLocEntry
*E
,
687 unsigned Offset
) const {
688 // If this is an instantiation record, walk through all the instantiation
693 Loc
= E
->getInstantiation().getInstantiationLocStart();
695 FID
= getFileID(Loc
);
696 E
= &getSLocEntry(FID
);
697 Offset
+= Loc
.getOffset()-E
->getOffset();
698 } while (!Loc
.isFileID());
700 return std::make_pair(FID
, Offset
);
703 std::pair
<FileID
, unsigned>
704 SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry
*E
,
705 unsigned Offset
) const {
706 // If this is an instantiation record, walk through all the instantiation
711 Loc
= E
->getInstantiation().getSpellingLoc();
713 FID
= getFileID(Loc
);
714 E
= &getSLocEntry(FID
);
715 Offset
+= Loc
.getOffset()-E
->getOffset();
716 } while (!Loc
.isFileID());
718 return std::make_pair(FID
, Offset
);
721 /// getImmediateSpellingLoc - Given a SourceLocation object, return the
722 /// spelling location referenced by the ID. This is the first level down
723 /// towards the place where the characters that make up the lexed token can be
724 /// found. This should not generally be used by clients.
725 SourceLocation
SourceManager::getImmediateSpellingLoc(SourceLocation Loc
) const{
726 if (Loc
.isFileID()) return Loc
;
727 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedLoc(Loc
);
728 Loc
= getSLocEntry(LocInfo
.first
).getInstantiation().getSpellingLoc();
729 return Loc
.getFileLocWithOffset(LocInfo
.second
);
733 /// getImmediateInstantiationRange - Loc is required to be an instantiation
734 /// location. Return the start/end of the instantiation information.
735 std::pair
<SourceLocation
,SourceLocation
>
736 SourceManager::getImmediateInstantiationRange(SourceLocation Loc
) const {
737 assert(Loc
.isMacroID() && "Not an instantiation loc!");
738 const InstantiationInfo
&II
= getSLocEntry(getFileID(Loc
)).getInstantiation();
739 return II
.getInstantiationLocRange();
742 /// getInstantiationRange - Given a SourceLocation object, return the
743 /// range of tokens covered by the instantiation in the ultimate file.
744 std::pair
<SourceLocation
,SourceLocation
>
745 SourceManager::getInstantiationRange(SourceLocation Loc
) const {
746 if (Loc
.isFileID()) return std::make_pair(Loc
, Loc
);
748 std::pair
<SourceLocation
,SourceLocation
> Res
=
749 getImmediateInstantiationRange(Loc
);
751 // Fully resolve the start and end locations to their ultimate instantiation
753 while (!Res
.first
.isFileID())
754 Res
.first
= getImmediateInstantiationRange(Res
.first
).first
;
755 while (!Res
.second
.isFileID())
756 Res
.second
= getImmediateInstantiationRange(Res
.second
).second
;
762 //===----------------------------------------------------------------------===//
763 // Queries about the code at a SourceLocation.
764 //===----------------------------------------------------------------------===//
766 /// getCharacterData - Return a pointer to the start of the specified location
767 /// in the appropriate MemoryBuffer.
768 const char *SourceManager::getCharacterData(SourceLocation SL
,
769 bool *Invalid
) const {
770 // Note that this is a hot function in the getSpelling() path, which is
771 // heavily used by -E mode.
772 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedSpellingLoc(SL
);
774 // Note that calling 'getBuffer()' may lazily page in a source file.
775 bool CharDataInvalid
= false;
776 const llvm::MemoryBuffer
*Buffer
777 = getSLocEntry(LocInfo
.first
).getFile().getContentCache()
778 ->getBuffer(Diag
, *this, SourceLocation(), &CharDataInvalid
);
780 *Invalid
= CharDataInvalid
;
781 return Buffer
->getBufferStart() + (CharDataInvalid
? 0 : LocInfo
.second
);
785 /// getColumnNumber - Return the column # for the specified file position.
786 /// this is significantly cheaper to compute than the line number.
787 unsigned SourceManager::getColumnNumber(FileID FID
, unsigned FilePos
,
788 bool *Invalid
) const {
789 bool MyInvalid
= false;
790 const char *Buf
= getBuffer(FID
, &MyInvalid
)->getBufferStart();
792 *Invalid
= MyInvalid
;
797 unsigned LineStart
= FilePos
;
798 while (LineStart
&& Buf
[LineStart
-1] != '\n' && Buf
[LineStart
-1] != '\r')
800 return FilePos
-LineStart
+1;
803 // isInvalid - Return the result of calling loc.isInvalid(), and
804 // if Invalid is not null, set its value to same.
805 static bool isInvalid(SourceLocation Loc
, bool *Invalid
) {
806 bool MyInvalid
= Loc
.isInvalid();
808 *Invalid
= MyInvalid
;
812 unsigned SourceManager::getSpellingColumnNumber(SourceLocation Loc
,
813 bool *Invalid
) const {
814 if (isInvalid(Loc
, Invalid
)) return 0;
815 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedSpellingLoc(Loc
);
816 return getColumnNumber(LocInfo
.first
, LocInfo
.second
, Invalid
);
819 unsigned SourceManager::getInstantiationColumnNumber(SourceLocation Loc
,
820 bool *Invalid
) const {
821 if (isInvalid(Loc
, Invalid
)) return 0;
822 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedInstantiationLoc(Loc
);
823 return getColumnNumber(LocInfo
.first
, LocInfo
.second
, Invalid
);
826 static LLVM_ATTRIBUTE_NOINLINE
void
827 ComputeLineNumbers(Diagnostic
&Diag
, ContentCache
*FI
,
828 llvm::BumpPtrAllocator
&Alloc
,
829 const SourceManager
&SM
, bool &Invalid
);
830 static void ComputeLineNumbers(Diagnostic
&Diag
, ContentCache
*FI
,
831 llvm::BumpPtrAllocator
&Alloc
,
832 const SourceManager
&SM
, bool &Invalid
) {
833 // Note that calling 'getBuffer()' may lazily page in the file.
834 const MemoryBuffer
*Buffer
= FI
->getBuffer(Diag
, SM
, SourceLocation(),
839 // Find the file offsets of all of the *physical* source lines. This does
840 // not look at trigraphs, escaped newlines, or anything else tricky.
841 std::vector
<unsigned> LineOffsets
;
843 // Line #1 starts at char 0.
844 LineOffsets
.push_back(0);
846 const unsigned char *Buf
= (const unsigned char *)Buffer
->getBufferStart();
847 const unsigned char *End
= (const unsigned char *)Buffer
->getBufferEnd();
850 // Skip over the contents of the line.
851 // TODO: Vectorize this? This is very performance sensitive for programs
852 // with lots of diagnostics and in -E mode.
853 const unsigned char *NextBuf
= (const unsigned char *)Buf
;
854 while (*NextBuf
!= '\n' && *NextBuf
!= '\r' && *NextBuf
!= '\0')
859 if (Buf
[0] == '\n' || Buf
[0] == '\r') {
860 // If this is \n\r or \r\n, skip both characters.
861 if ((Buf
[1] == '\n' || Buf
[1] == '\r') && Buf
[0] != Buf
[1])
864 LineOffsets
.push_back(Offs
);
866 // Otherwise, this is a null. If end of file, exit.
867 if (Buf
== End
) break;
868 // Otherwise, skip the null.
873 // Copy the offsets into the FileInfo structure.
874 FI
->NumLines
= LineOffsets
.size();
875 FI
->SourceLineCache
= Alloc
.Allocate
<unsigned>(LineOffsets
.size());
876 std::copy(LineOffsets
.begin(), LineOffsets
.end(), FI
->SourceLineCache
);
879 /// getLineNumber - Given a SourceLocation, return the spelling line number
880 /// for the position indicated. This requires building and caching a table of
881 /// line offsets for the MemoryBuffer, so this is not cheap: use only when
882 /// about to emit a diagnostic.
883 unsigned SourceManager::getLineNumber(FileID FID
, unsigned FilePos
,
884 bool *Invalid
) const {
885 ContentCache
*Content
;
886 if (LastLineNoFileIDQuery
== FID
)
887 Content
= LastLineNoContentCache
;
889 Content
= const_cast<ContentCache
*>(getSLocEntry(FID
)
890 .getFile().getContentCache());
892 // If this is the first use of line information for this buffer, compute the
893 /// SourceLineCache for it on demand.
894 if (Content
->SourceLineCache
== 0) {
895 bool MyInvalid
= false;
896 ComputeLineNumbers(Diag
, Content
, ContentCacheAlloc
, *this, MyInvalid
);
898 *Invalid
= MyInvalid
;
904 // Okay, we know we have a line number table. Do a binary search to find the
905 // line number that this character position lands on.
906 unsigned *SourceLineCache
= Content
->SourceLineCache
;
907 unsigned *SourceLineCacheStart
= SourceLineCache
;
908 unsigned *SourceLineCacheEnd
= SourceLineCache
+ Content
->NumLines
;
910 unsigned QueriedFilePos
= FilePos
+1;
912 // FIXME: I would like to be convinced that this code is worth being as
913 // complicated as it is, binary search isn't that slow.
915 // If it is worth being optimized, then in my opinion it could be more
916 // performant, simpler, and more obviously correct by just "galloping" outward
917 // from the queried file position. In fact, this could be incorporated into a
918 // generic algorithm such as lower_bound_with_hint.
920 // If someone gives me a test case where this matters, and I will do it! - DWD
922 // If the previous query was to the same file, we know both the file pos from
923 // that query and the line number returned. This allows us to narrow the
924 // search space from the entire file to something near the match.
925 if (LastLineNoFileIDQuery
== FID
) {
926 if (QueriedFilePos
>= LastLineNoFilePos
) {
927 // FIXME: Potential overflow?
928 SourceLineCache
= SourceLineCache
+LastLineNoResult
-1;
930 // The query is likely to be nearby the previous one. Here we check to
931 // see if it is within 5, 10 or 20 lines. It can be far away in cases
932 // where big comment blocks and vertical whitespace eat up lines but
933 // contribute no tokens.
934 if (SourceLineCache
+5 < SourceLineCacheEnd
) {
935 if (SourceLineCache
[5] > QueriedFilePos
)
936 SourceLineCacheEnd
= SourceLineCache
+5;
937 else if (SourceLineCache
+10 < SourceLineCacheEnd
) {
938 if (SourceLineCache
[10] > QueriedFilePos
)
939 SourceLineCacheEnd
= SourceLineCache
+10;
940 else if (SourceLineCache
+20 < SourceLineCacheEnd
) {
941 if (SourceLineCache
[20] > QueriedFilePos
)
942 SourceLineCacheEnd
= SourceLineCache
+20;
947 if (LastLineNoResult
< Content
->NumLines
)
948 SourceLineCacheEnd
= SourceLineCache
+LastLineNoResult
+1;
952 // If the spread is large, do a "radix" test as our initial guess, based on
953 // the assumption that lines average to approximately the same length.
954 // NOTE: This is currently disabled, as it does not appear to be profitable in
955 // initial measurements.
956 if (0 && SourceLineCacheEnd
-SourceLineCache
> 20) {
957 unsigned FileLen
= Content
->SourceLineCache
[Content
->NumLines
-1];
959 // Take a stab at guessing where it is.
960 unsigned ApproxPos
= Content
->NumLines
*QueriedFilePos
/ FileLen
;
962 // Check for -10 and +10 lines.
963 unsigned LowerBound
= std::max(int(ApproxPos
-10), 0);
964 unsigned UpperBound
= std::min(ApproxPos
+10, FileLen
);
966 // If the computed lower bound is less than the query location, move it in.
967 if (SourceLineCache
< SourceLineCacheStart
+LowerBound
&&
968 SourceLineCacheStart
[LowerBound
] < QueriedFilePos
)
969 SourceLineCache
= SourceLineCacheStart
+LowerBound
;
971 // If the computed upper bound is greater than the query location, move it.
972 if (SourceLineCacheEnd
> SourceLineCacheStart
+UpperBound
&&
973 SourceLineCacheStart
[UpperBound
] >= QueriedFilePos
)
974 SourceLineCacheEnd
= SourceLineCacheStart
+UpperBound
;
978 = std::lower_bound(SourceLineCache
, SourceLineCacheEnd
, QueriedFilePos
);
979 unsigned LineNo
= Pos
-SourceLineCacheStart
;
981 LastLineNoFileIDQuery
= FID
;
982 LastLineNoContentCache
= Content
;
983 LastLineNoFilePos
= QueriedFilePos
;
984 LastLineNoResult
= LineNo
;
988 unsigned SourceManager::getInstantiationLineNumber(SourceLocation Loc
,
989 bool *Invalid
) const {
990 if (isInvalid(Loc
, Invalid
)) return 0;
991 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedInstantiationLoc(Loc
);
992 return getLineNumber(LocInfo
.first
, LocInfo
.second
);
994 unsigned SourceManager::getSpellingLineNumber(SourceLocation Loc
,
995 bool *Invalid
) const {
996 if (isInvalid(Loc
, Invalid
)) return 0;
997 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedSpellingLoc(Loc
);
998 return getLineNumber(LocInfo
.first
, LocInfo
.second
);
1001 /// getFileCharacteristic - return the file characteristic of the specified
1002 /// source location, indicating whether this is a normal file, a system
1003 /// header, or an "implicit extern C" system header.
1005 /// This state can be modified with flags on GNU linemarker directives like:
1007 /// which changes all source locations in the current file after that to be
1008 /// considered to be from a system header.
1009 SrcMgr::CharacteristicKind
1010 SourceManager::getFileCharacteristic(SourceLocation Loc
) const {
1011 assert(!Loc
.isInvalid() && "Can't get file characteristic of invalid loc!");
1012 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedInstantiationLoc(Loc
);
1013 const SrcMgr::FileInfo
&FI
= getSLocEntry(LocInfo
.first
).getFile();
1015 // If there are no #line directives in this file, just return the whole-file
1017 if (!FI
.hasLineDirectives())
1018 return FI
.getFileCharacteristic();
1020 assert(LineTable
&& "Can't have linetable entries without a LineTable!");
1021 // See if there is a #line directive before the location.
1022 const LineEntry
*Entry
=
1023 LineTable
->FindNearestLineEntry(LocInfo
.first
.ID
, LocInfo
.second
);
1025 // If this is before the first line marker, use the file characteristic.
1027 return FI
.getFileCharacteristic();
1029 return Entry
->FileKind
;
1032 /// Return the filename or buffer identifier of the buffer the location is in.
1033 /// Note that this name does not respect #line directives. Use getPresumedLoc
1034 /// for normal clients.
1035 const char *SourceManager::getBufferName(SourceLocation Loc
,
1036 bool *Invalid
) const {
1037 if (isInvalid(Loc
, Invalid
)) return "<invalid loc>";
1039 return getBuffer(getFileID(Loc
), Invalid
)->getBufferIdentifier();
1043 /// getPresumedLoc - This method returns the "presumed" location of a
1044 /// SourceLocation specifies. A "presumed location" can be modified by #line
1045 /// or GNU line marker directives. This provides a view on the data that a
1046 /// user should see in diagnostics, for example.
1048 /// Note that a presumed location is always given as the instantiation point
1049 /// of an instantiation location, not at the spelling location.
1050 PresumedLoc
SourceManager::getPresumedLoc(SourceLocation Loc
) const {
1051 if (Loc
.isInvalid()) return PresumedLoc();
1053 // Presumed locations are always for instantiation points.
1054 std::pair
<FileID
, unsigned> LocInfo
= getDecomposedInstantiationLoc(Loc
);
1056 const SrcMgr::FileInfo
&FI
= getSLocEntry(LocInfo
.first
).getFile();
1057 const SrcMgr::ContentCache
*C
= FI
.getContentCache();
1059 // To get the source name, first consult the FileEntry (if one exists)
1060 // before the MemBuffer as this will avoid unnecessarily paging in the
1062 const char *Filename
;
1064 Filename
= C
->Entry
->getName();
1066 Filename
= C
->getBuffer(Diag
, *this)->getBufferIdentifier();
1067 bool Invalid
= false;
1068 unsigned LineNo
= getLineNumber(LocInfo
.first
, LocInfo
.second
, &Invalid
);
1070 return PresumedLoc();
1071 unsigned ColNo
= getColumnNumber(LocInfo
.first
, LocInfo
.second
, &Invalid
);
1073 return PresumedLoc();
1075 SourceLocation IncludeLoc
= FI
.getIncludeLoc();
1077 // If we have #line directives in this file, update and overwrite the physical
1078 // location info if appropriate.
1079 if (FI
.hasLineDirectives()) {
1080 assert(LineTable
&& "Can't have linetable entries without a LineTable!");
1081 // See if there is a #line directive before this. If so, get it.
1082 if (const LineEntry
*Entry
=
1083 LineTable
->FindNearestLineEntry(LocInfo
.first
.ID
, LocInfo
.second
)) {
1084 // If the LineEntry indicates a filename, use it.
1085 if (Entry
->FilenameID
!= -1)
1086 Filename
= LineTable
->getFilename(Entry
->FilenameID
);
1088 // Use the line number specified by the LineEntry. This line number may
1089 // be multiple lines down from the line entry. Add the difference in
1090 // physical line numbers from the query point and the line marker to the
1092 unsigned MarkerLineNo
= getLineNumber(LocInfo
.first
, Entry
->FileOffset
);
1093 LineNo
= Entry
->LineNo
+ (LineNo
-MarkerLineNo
-1);
1095 // Note that column numbers are not molested by line markers.
1097 // Handle virtual #include manipulation.
1098 if (Entry
->IncludeOffset
) {
1099 IncludeLoc
= getLocForStartOfFile(LocInfo
.first
);
1100 IncludeLoc
= IncludeLoc
.getFileLocWithOffset(Entry
->IncludeOffset
);
1105 return PresumedLoc(Filename
, LineNo
, ColNo
, IncludeLoc
);
1108 //===----------------------------------------------------------------------===//
1109 // Other miscellaneous methods.
1110 //===----------------------------------------------------------------------===//
1112 /// \brief Retrieve the inode for the given file entry, if possible.
1114 /// This routine involves a system call, and therefore should only be used
1115 /// in non-performance-critical code.
1116 static llvm::Optional
<ino_t
> getActualFileInode(const FileEntry
*File
) {
1118 return llvm::Optional
<ino_t
>();
1120 struct stat StatBuf
;
1121 if (::stat(File
->getName(), &StatBuf
))
1122 return llvm::Optional
<ino_t
>();
1124 return StatBuf
.st_ino
;
1127 /// \brief Get the source location for the given file:line:col triplet.
1129 /// If the source file is included multiple times, the source location will
1130 /// be based upon the first inclusion.
1131 SourceLocation
SourceManager::getLocation(const FileEntry
*SourceFile
,
1132 unsigned Line
, unsigned Col
) {
1133 assert(SourceFile
&& "Null source file!");
1134 assert(Line
&& Col
&& "Line and column should start from 1!");
1136 // Find the first file ID that corresponds to the given file.
1139 // First, check the main file ID, since it is common to look for a
1140 // location in the main file.
1141 llvm::Optional
<ino_t
> SourceFileInode
;
1142 llvm::Optional
<llvm::StringRef
> SourceFileName
;
1143 if (!MainFileID
.isInvalid()) {
1144 const SLocEntry
&MainSLoc
= getSLocEntry(MainFileID
);
1145 if (MainSLoc
.isFile()) {
1146 const ContentCache
*MainContentCache
1147 = MainSLoc
.getFile().getContentCache();
1148 if (!MainContentCache
) {
1149 // Can't do anything
1150 } else if (MainContentCache
->Entry
== SourceFile
) {
1151 FirstFID
= MainFileID
;
1153 // Fall back: check whether we have the same base name and inode
1154 // as the main file.
1155 const FileEntry
*MainFile
= MainContentCache
->Entry
;
1156 SourceFileName
= llvm::sys::path::filename(SourceFile
->getName());
1157 if (*SourceFileName
== llvm::sys::path::filename(MainFile
->getName())) {
1158 SourceFileInode
= getActualFileInode(SourceFile
);
1159 if (SourceFileInode
) {
1160 if (llvm::Optional
<ino_t
> MainFileInode
1161 = getActualFileInode(MainFile
)) {
1162 if (*SourceFileInode
== *MainFileInode
) {
1163 FirstFID
= MainFileID
;
1164 SourceFile
= MainFile
;
1173 if (FirstFID
.isInvalid()) {
1174 // The location we're looking for isn't in the main file; look
1175 // through all of the source locations.
1176 for (unsigned I
= 0, N
= sloc_entry_size(); I
!= N
; ++I
) {
1177 const SLocEntry
&SLoc
= getSLocEntry(I
);
1178 if (SLoc
.isFile() &&
1179 SLoc
.getFile().getContentCache() &&
1180 SLoc
.getFile().getContentCache()->Entry
== SourceFile
) {
1181 FirstFID
= FileID::get(I
);
1187 // If we haven't found what we want yet, try again, but this time stat()
1188 // each of the files in case the files have changed since we originally
1190 if (FirstFID
.isInvalid() &&
1192 (SourceFileName
= llvm::sys::path::filename(SourceFile
->getName()))) &&
1194 (SourceFileInode
= getActualFileInode(SourceFile
)))) {
1195 for (unsigned I
= 0, N
= sloc_entry_size(); I
!= N
; ++I
) {
1196 const SLocEntry
&SLoc
= getSLocEntry(I
);
1197 if (SLoc
.isFile()) {
1198 const ContentCache
*FileContentCache
1199 = SLoc
.getFile().getContentCache();
1200 const FileEntry
*Entry
=FileContentCache
? FileContentCache
->Entry
: 0;
1202 *SourceFileName
== llvm::sys::path::filename(Entry
->getName())) {
1203 if (llvm::Optional
<ino_t
> EntryInode
= getActualFileInode(Entry
)) {
1204 if (*SourceFileInode
== *EntryInode
) {
1205 FirstFID
= FileID::get(I
);
1215 if (FirstFID
.isInvalid())
1216 return SourceLocation();
1218 if (Line
== 1 && Col
== 1)
1219 return getLocForStartOfFile(FirstFID
);
1221 ContentCache
*Content
1222 = const_cast<ContentCache
*>(getOrCreateContentCache(SourceFile
));
1224 return SourceLocation();
1226 // If this is the first use of line information for this buffer, compute the
1227 /// SourceLineCache for it on demand.
1228 if (Content
->SourceLineCache
== 0) {
1229 bool MyInvalid
= false;
1230 ComputeLineNumbers(Diag
, Content
, ContentCacheAlloc
, *this, MyInvalid
);
1232 return SourceLocation();
1235 if (Line
> Content
->NumLines
) {
1236 unsigned Size
= Content
->getBuffer(Diag
, *this)->getBufferSize();
1239 return getLocForStartOfFile(FirstFID
).getFileLocWithOffset(Size
);
1242 unsigned FilePos
= Content
->SourceLineCache
[Line
- 1];
1243 const char *Buf
= Content
->getBuffer(Diag
, *this)->getBufferStart() + FilePos
;
1244 unsigned BufLength
= Content
->getBuffer(Diag
, *this)->getBufferEnd() - Buf
;
1247 // Check that the given column is valid.
1248 while (i
< BufLength
-1 && i
< Col
-1 && Buf
[i
] != '\n' && Buf
[i
] != '\r')
1251 return getLocForStartOfFile(FirstFID
).getFileLocWithOffset(FilePos
+ i
);
1253 return getLocForStartOfFile(FirstFID
).getFileLocWithOffset(FilePos
+ Col
- 1);
1256 /// Given a decomposed source location, move it up the include/instantiation
1257 /// stack to the parent source location. If this is possible, return the
1258 /// decomposed version of the parent in Loc and return false. If Loc is the
1259 /// top-level entry, return true and don't modify it.
1260 static bool MoveUpIncludeHierarchy(std::pair
<FileID
, unsigned> &Loc
,
1261 const SourceManager
&SM
) {
1262 SourceLocation UpperLoc
;
1263 const SrcMgr::SLocEntry
&Entry
= SM
.getSLocEntry(Loc
.first
);
1264 if (Entry
.isInstantiation())
1265 UpperLoc
= Entry
.getInstantiation().getInstantiationLocStart();
1267 UpperLoc
= Entry
.getFile().getIncludeLoc();
1269 if (UpperLoc
.isInvalid())
1270 return true; // We reached the top.
1272 Loc
= SM
.getDecomposedLoc(UpperLoc
);
1277 /// \brief Determines the order of 2 source locations in the translation unit.
1279 /// \returns true if LHS source location comes before RHS, false otherwise.
1280 bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS
,
1281 SourceLocation RHS
) const {
1282 assert(LHS
.isValid() && RHS
.isValid() && "Passed invalid source location!");
1286 // If both locations are macro instantiations, the order of their offsets
1287 // reflect the order that the tokens, pointed to by these locations, were
1288 // instantiated (during parsing each token that is instantiated by a macro,
1289 // expands the SLocEntries).
1290 if (LHS
.isMacroID() && RHS
.isMacroID())
1291 return LHS
.getOffset() < RHS
.getOffset();
1293 std::pair
<FileID
, unsigned> LOffs
= getDecomposedLoc(LHS
);
1294 std::pair
<FileID
, unsigned> ROffs
= getDecomposedLoc(RHS
);
1296 // If the source locations are in the same file, just compare offsets.
1297 if (LOffs
.first
== ROffs
.first
)
1298 return LOffs
.second
< ROffs
.second
;
1300 // If we are comparing a source location with multiple locations in the same
1301 // file, we get a big win by caching the result.
1302 if (IsBeforeInTUCache
.isCacheValid(LOffs
.first
, ROffs
.first
))
1303 return IsBeforeInTUCache
.getCachedResult(LOffs
.second
, ROffs
.second
);
1305 // Okay, we missed in the cache, start updating the cache for this query.
1306 IsBeforeInTUCache
.setQueryFIDs(LOffs
.first
, ROffs
.first
);
1308 // "Traverse" the include/instantiation stacks of both locations and try to
1309 // find a common "ancestor". FileIDs build a tree-like structure that
1310 // reflects the #include hierarchy, and this algorithm needs to find the
1311 // nearest common ancestor between the two locations. For example, if you
1312 // have a.c that includes b.h and c.h, and are comparing a location in b.h to
1313 // a location in c.h, we need to find that their nearest common ancestor is
1314 // a.c, and compare the locations of the two #includes to find their relative
1317 // SourceManager assigns FileIDs in order of parsing. This means that an
1318 // includee always has a larger FileID than an includer. While you might
1319 // think that we could just compare the FileID's here, that doesn't work to
1320 // compare a point at the end of a.c with a point within c.h. Though c.h has
1321 // a larger FileID, we have to compare the include point of c.h to the
1324 // Despite not being able to directly compare FileID's, we can tell that a
1325 // larger FileID is necessarily more deeply nested than a lower one and use
1326 // this information to walk up the tree to the nearest common ancestor.
1328 // If LOffs is larger than ROffs, then LOffs must be more deeply nested than
1329 // ROffs, walk up the #include chain.
1330 if (LOffs
.first
.ID
> ROffs
.first
.ID
) {
1331 if (MoveUpIncludeHierarchy(LOffs
, *this))
1332 break; // We reached the top.
1335 // Otherwise, ROffs is larger than LOffs, so ROffs must be more deeply
1336 // nested than LOffs, walk up the #include chain.
1337 if (MoveUpIncludeHierarchy(ROffs
, *this))
1338 break; // We reached the top.
1340 } while (LOffs
.first
!= ROffs
.first
);
1342 // If we exited because we found a nearest common ancestor, compare the
1343 // locations within the common file and cache them.
1344 if (LOffs
.first
== ROffs
.first
) {
1345 IsBeforeInTUCache
.setCommonLoc(LOffs
.first
, LOffs
.second
, ROffs
.second
);
1346 return IsBeforeInTUCache
.getCachedResult(LOffs
.second
, ROffs
.second
);
1349 // There is no common ancestor, most probably because one location is in the
1350 // predefines buffer or an AST file.
1351 // FIXME: We should rearrange the external interface so this simply never
1352 // happens; it can't conceptually happen. Also see PR5662.
1353 IsBeforeInTUCache
.setQueryFIDs(FileID(), FileID()); // Don't try caching.
1355 // Zip both entries up to the top level record.
1356 while (!MoveUpIncludeHierarchy(LOffs
, *this)) /*empty*/;
1357 while (!MoveUpIncludeHierarchy(ROffs
, *this)) /*empty*/;
1359 // If exactly one location is a memory buffer, assume it preceeds the other.
1361 // Strip off macro instantation locations, going up to the top-level File
1363 bool LIsMB
= getFileEntryForID(LOffs
.first
) == 0;
1364 bool RIsMB
= getFileEntryForID(ROffs
.first
) == 0;
1368 // Otherwise, just assume FileIDs were created in order.
1369 return LOffs
.first
< ROffs
.first
;
1372 /// PrintStats - Print statistics to stderr.
1374 void SourceManager::PrintStats() const {
1375 llvm::errs() << "\n*** Source Manager Stats:\n";
1376 llvm::errs() << FileInfos
.size() << " files mapped, " << MemBufferInfos
.size()
1377 << " mem buffers mapped.\n";
1378 llvm::errs() << SLocEntryTable
.size() << " SLocEntry's allocated, "
1379 << NextOffset
<< "B of Sloc address space used.\n";
1381 unsigned NumLineNumsComputed
= 0;
1382 unsigned NumFileBytesMapped
= 0;
1383 for (fileinfo_iterator I
= fileinfo_begin(), E
= fileinfo_end(); I
!= E
; ++I
){
1384 NumLineNumsComputed
+= I
->second
->SourceLineCache
!= 0;
1385 NumFileBytesMapped
+= I
->second
->getSizeBytesMapped();
1388 llvm::errs() << NumFileBytesMapped
<< " bytes of files mapped, "
1389 << NumLineNumsComputed
<< " files with line #'s computed.\n";
1390 llvm::errs() << "FileID scans: " << NumLinearScans
<< " linear, "
1391 << NumBinaryProbes
<< " binary.\n";
1394 ExternalSLocEntrySource::~ExternalSLocEntrySource() { }