xref: /llvm-project/clang/lib/Basic/SourceManager.cpp (revision 153a0f1f52f803e286b057cd31de49ac940ebe78)
1 //===--- SourceManager.cpp - Track and cache source files -----------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file implements the SourceManager interface.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/Basic/SourceManager.h"
15 #include "clang/Basic/FileManager.h"
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/MemoryBuffer.h"
18 #include "llvm/System/Path.h"
19 #include "llvm/Bitcode/Serialize.h"
20 #include "llvm/Bitcode/Deserialize.h"
21 #include "llvm/Support/Streams.h"
22 #include <algorithm>
23 using namespace clang;
24 using namespace SrcMgr;
25 using llvm::MemoryBuffer;
26 
27 //===----------------------------------------------------------------------===//
28 // SourceManager Helper Classes
29 //===----------------------------------------------------------------------===//
30 
31 ContentCache::~ContentCache() {
32   delete Buffer;
33 }
34 
35 /// getSizeBytesMapped - Returns the number of bytes actually mapped for
36 ///  this ContentCache.  This can be 0 if the MemBuffer was not actually
37 ///  instantiated.
38 unsigned ContentCache::getSizeBytesMapped() const {
39   return Buffer ? Buffer->getBufferSize() : 0;
40 }
41 
42 /// getSize - Returns the size of the content encapsulated by this ContentCache.
43 ///  This can be the size of the source file or the size of an arbitrary
44 ///  scratch buffer.  If the ContentCache encapsulates a source file, that
45 ///  file is not lazily brought in from disk to satisfy this query.
46 unsigned ContentCache::getSize() const {
47   return Entry ? Entry->getSize() : Buffer->getBufferSize();
48 }
49 
50 const llvm::MemoryBuffer *ContentCache::getBuffer() const {
51   // Lazily create the Buffer for ContentCaches that wrap files.
52   if (!Buffer && Entry) {
53     // FIXME: Should we support a way to not have to do this check over
54     //   and over if we cannot open the file?
55     Buffer = MemoryBuffer::getFile(Entry->getName(), 0, Entry->getSize());
56   }
57   return Buffer;
58 }
59 
60 //===----------------------------------------------------------------------===//
61 // Line Table Implementation
62 //===----------------------------------------------------------------------===//
63 
64 namespace clang {
65 struct LineEntry {
66   /// FileOffset - The offset in this file that the line entry occurs at.
67   unsigned FileOffset;
68   /// LineNo - The presumed line number of this line entry: #line 4.
69   unsigned LineNo;
70   /// FilenameID - The ID of the filename identified by this line entry:
71   /// #line 4 "foo.c".  This is -1 if not specified.
72   int FilenameID;
73 
74   static LineEntry get(unsigned Offs, unsigned Line, int Filename) {
75     LineEntry E;
76     E.FileOffset = Offs;
77     E.LineNo = Line;
78     E.FilenameID = Filename;
79     return E;
80   }
81 };
82 
83 
84 /// LineTableInfo - This class is used to hold and unique data used to
85 /// represent #line information.
86 class LineTableInfo {
87   /// FilenameIDs - This map is used to assign unique IDs to filenames in
88   /// #line directives.  This allows us to unique the filenames that
89   /// frequently reoccur and reference them with indices.  FilenameIDs holds
90   /// the mapping from string -> ID, and FilenamesByID holds the mapping of ID
91   /// to string.
92   llvm::StringMap<unsigned, llvm::BumpPtrAllocator> FilenameIDs;
93   std::vector<llvm::StringMapEntry<unsigned>*> FilenamesByID;
94 
95   /// LineEntries - This is a map from FileIDs to a list of line entries (sorted
96   /// by the offset they occur in the file.
97   std::map<unsigned, std::vector<LineEntry> > LineEntries;
98 public:
99   LineTableInfo() {
100   }
101 
102   void clear() {
103     FilenameIDs.clear();
104     FilenamesByID.clear();
105   }
106 
107   ~LineTableInfo() {}
108 
109   unsigned getLineTableFilenameID(const char *Ptr, unsigned Len);
110   void AddLineNote(unsigned FID, unsigned Offset,
111                    unsigned LineNo, int FilenameID);
112 };
113 } // namespace clang
114 
115 
116 
117 
118 unsigned LineTableInfo::getLineTableFilenameID(const char *Ptr, unsigned Len) {
119   // Look up the filename in the string table, returning the pre-existing value
120   // if it exists.
121   llvm::StringMapEntry<unsigned> &Entry =
122     FilenameIDs.GetOrCreateValue(Ptr, Ptr+Len, ~0U);
123   if (Entry.getValue() != ~0U)
124     return Entry.getValue();
125 
126   // Otherwise, assign this the next available ID.
127   Entry.setValue(FilenamesByID.size());
128   FilenamesByID.push_back(&Entry);
129   return FilenamesByID.size()-1;
130 }
131 
132 /// AddLineNote - Add a line note to the line table that indicates that there
133 /// is a #line at the specified FID/Offset location which changes the presumed
134 /// location to LineNo/FilenameID.
135 void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset,
136                                 unsigned LineNo, int FilenameID) {
137   std::vector<LineEntry> &Entries = LineEntries[FID];
138 
139   assert((Entries.empty() || Entries.back().FileOffset < Offset) &&
140          "Adding line entries out of order!");
141   Entries.push_back(LineEntry::get(Offset, LineNo, FilenameID));
142 }
143 
144 
145 
146 /// getLineTableFilenameID - Return the uniqued ID for the specified filename.
147 ///
148 unsigned SourceManager::getLineTableFilenameID(const char *Ptr, unsigned Len) {
149   if (LineTable == 0)
150     LineTable = new LineTableInfo();
151   return LineTable->getLineTableFilenameID(Ptr, Len);
152 }
153 
154 
155 /// AddLineNote - Add a line note to the line table for the FileID and offset
156 /// specified by Loc.  If FilenameID is -1, it is considered to be
157 /// unspecified.
158 void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo,
159                                 int FilenameID) {
160   std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc);
161 
162   const SrcMgr::FileInfo &FileInfo = getSLocEntry(LocInfo.first).getFile();
163 
164   // Remember that this file has #line directives now if it doesn't already.
165   const_cast<SrcMgr::FileInfo&>(FileInfo).setHasLineDirectives();
166 
167   if (LineTable == 0)
168     LineTable = new LineTableInfo();
169   LineTable->AddLineNote(LocInfo.first.ID, LocInfo.second, LineNo, FilenameID);
170 }
171 
172 
173 //===----------------------------------------------------------------------===//
174 // Private 'Create' methods.
175 //===----------------------------------------------------------------------===//
176 
177 SourceManager::~SourceManager() {
178   delete LineTable;
179 
180   // Delete FileEntry objects corresponding to content caches.  Since the actual
181   // content cache objects are bump pointer allocated, we just have to run the
182   // dtors, but we call the deallocate method for completeness.
183   for (unsigned i = 0, e = MemBufferInfos.size(); i != e; ++i) {
184     MemBufferInfos[i]->~ContentCache();
185     ContentCacheAlloc.Deallocate(MemBufferInfos[i]);
186   }
187   for (llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>::iterator
188        I = FileInfos.begin(), E = FileInfos.end(); I != E; ++I) {
189     I->second->~ContentCache();
190     ContentCacheAlloc.Deallocate(I->second);
191   }
192 }
193 
194 void SourceManager::clearIDTables() {
195   MainFileID = FileID();
196   SLocEntryTable.clear();
197   LastLineNoFileIDQuery = FileID();
198   LastLineNoContentCache = 0;
199   LastFileIDLookup = FileID();
200 
201   if (LineTable)
202     LineTable->clear();
203 
204   // Use up FileID #0 as an invalid instantiation.
205   NextOffset = 0;
206   createInstantiationLoc(SourceLocation(), SourceLocation(), 1);
207 }
208 
209 /// getOrCreateContentCache - Create or return a cached ContentCache for the
210 /// specified file.
211 const ContentCache *
212 SourceManager::getOrCreateContentCache(const FileEntry *FileEnt) {
213   assert(FileEnt && "Didn't specify a file entry to use?");
214 
215   // Do we already have information about this file?
216   ContentCache *&Entry = FileInfos[FileEnt];
217   if (Entry) return Entry;
218 
219   // Nope, create a new Cache entry.  Make sure it is at least 8-byte aligned
220   // so that FileInfo can use the low 3 bits of the pointer for its own
221   // nefarious purposes.
222   unsigned EntryAlign = llvm::AlignOf<ContentCache>::Alignment;
223   EntryAlign = std::max(8U, EntryAlign);
224   Entry = ContentCacheAlloc.Allocate<ContentCache>(1, EntryAlign);
225   new (Entry) ContentCache(FileEnt);
226   return Entry;
227 }
228 
229 
230 /// createMemBufferContentCache - Create a new ContentCache for the specified
231 ///  memory buffer.  This does no caching.
232 const ContentCache*
233 SourceManager::createMemBufferContentCache(const MemoryBuffer *Buffer) {
234   // Add a new ContentCache to the MemBufferInfos list and return it.  Make sure
235   // it is at least 8-byte aligned so that FileInfo can use the low 3 bits of
236   // the pointer for its own nefarious purposes.
237   unsigned EntryAlign = llvm::AlignOf<ContentCache>::Alignment;
238   EntryAlign = std::max(8U, EntryAlign);
239   ContentCache *Entry = ContentCacheAlloc.Allocate<ContentCache>(1, EntryAlign);
240   new (Entry) ContentCache();
241   MemBufferInfos.push_back(Entry);
242   Entry->setBuffer(Buffer);
243   return Entry;
244 }
245 
246 //===----------------------------------------------------------------------===//
247 // Methods to create new FileID's and instantiations.
248 //===----------------------------------------------------------------------===//
249 
250 /// createFileID - Create a new fileID for the specified ContentCache and
251 /// include position.  This works regardless of whether the ContentCache
252 /// corresponds to a file or some other input source.
253 FileID SourceManager::createFileID(const ContentCache *File,
254                                    SourceLocation IncludePos,
255                                    SrcMgr::CharacteristicKind FileCharacter) {
256   SLocEntryTable.push_back(SLocEntry::get(NextOffset,
257                                           FileInfo::get(IncludePos, File,
258                                                         FileCharacter)));
259   unsigned FileSize = File->getSize();
260   assert(NextOffset+FileSize+1 > NextOffset && "Ran out of source locations!");
261   NextOffset += FileSize+1;
262 
263   // Set LastFileIDLookup to the newly created file.  The next getFileID call is
264   // almost guaranteed to be from that file.
265   return LastFileIDLookup = FileID::get(SLocEntryTable.size()-1);
266 }
267 
268 /// createInstantiationLoc - Return a new SourceLocation that encodes the fact
269 /// that a token from SpellingLoc should actually be referenced from
270 /// InstantiationLoc.
271 SourceLocation SourceManager::createInstantiationLoc(SourceLocation SpellingLoc,
272                                                      SourceLocation InstantLoc,
273                                                      unsigned TokLength) {
274   SLocEntryTable.push_back(SLocEntry::get(NextOffset,
275                                           InstantiationInfo::get(InstantLoc,
276                                                                  SpellingLoc)));
277   assert(NextOffset+TokLength+1 > NextOffset && "Ran out of source locations!");
278   NextOffset += TokLength+1;
279   return SourceLocation::getMacroLoc(NextOffset-(TokLength+1));
280 }
281 
282 /// getBufferData - Return a pointer to the start and end of the source buffer
283 /// data for the specified FileID.
284 std::pair<const char*, const char*>
285 SourceManager::getBufferData(FileID FID) const {
286   const llvm::MemoryBuffer *Buf = getBuffer(FID);
287   return std::make_pair(Buf->getBufferStart(), Buf->getBufferEnd());
288 }
289 
290 
291 //===----------------------------------------------------------------------===//
292 // SourceLocation manipulation methods.
293 //===----------------------------------------------------------------------===//
294 
295 /// getFileIDSlow - Return the FileID for a SourceLocation.  This is a very hot
296 /// method that is used for all SourceManager queries that start with a
297 /// SourceLocation object.  It is responsible for finding the entry in
298 /// SLocEntryTable which contains the specified location.
299 ///
300 FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const {
301   assert(SLocOffset && "Invalid FileID");
302 
303   // After the first and second level caches, I see two common sorts of
304   // behavior: 1) a lot of searched FileID's are "near" the cached file location
305   // or are "near" the cached instantiation location.  2) others are just
306   // completely random and may be a very long way away.
307   //
308   // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
309   // then we fall back to a less cache efficient, but more scalable, binary
310   // search to find the location.
311 
312   // See if this is near the file point - worst case we start scanning from the
313   // most newly created FileID.
314   std::vector<SrcMgr::SLocEntry>::const_iterator I;
315 
316   if (SLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
317     // Neither loc prunes our search.
318     I = SLocEntryTable.end();
319   } else {
320     // Perhaps it is near the file point.
321     I = SLocEntryTable.begin()+LastFileIDLookup.ID;
322   }
323 
324   // Find the FileID that contains this.  "I" is an iterator that points to a
325   // FileID whose offset is known to be larger than SLocOffset.
326   unsigned NumProbes = 0;
327   while (1) {
328     --I;
329     if (I->getOffset() <= SLocOffset) {
330 #if 0
331       printf("lin %d -> %d [%s] %d %d\n", SLocOffset,
332              I-SLocEntryTable.begin(),
333              I->isInstantiation() ? "inst" : "file",
334              LastFileIDLookup.ID,  int(SLocEntryTable.end()-I));
335 #endif
336       FileID Res = FileID::get(I-SLocEntryTable.begin());
337 
338       // If this isn't an instantiation, remember it.  We have good locality
339       // across FileID lookups.
340       if (!I->isInstantiation())
341         LastFileIDLookup = Res;
342       NumLinearScans += NumProbes+1;
343       return Res;
344     }
345     if (++NumProbes == 8)
346       break;
347   }
348 
349   // Convert "I" back into an index.  We know that it is an entry whose index is
350   // larger than the offset we are looking for.
351   unsigned GreaterIndex = I-SLocEntryTable.begin();
352   // LessIndex - This is the lower bound of the range that we're searching.
353   // We know that the offset corresponding to the FileID is is less than
354   // SLocOffset.
355   unsigned LessIndex = 0;
356   NumProbes = 0;
357   while (1) {
358     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
359     unsigned MidOffset = SLocEntryTable[MiddleIndex].getOffset();
360 
361     ++NumProbes;
362 
363     // If the offset of the midpoint is too large, chop the high side of the
364     // range to the midpoint.
365     if (MidOffset > SLocOffset) {
366       GreaterIndex = MiddleIndex;
367       continue;
368     }
369 
370     // If the middle index contains the value, succeed and return.
371     if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) {
372 #if 0
373       printf("bin %d -> %d [%s] %d %d\n", SLocOffset,
374              I-SLocEntryTable.begin(),
375              I->isInstantiation() ? "inst" : "file",
376              LastFileIDLookup.ID, int(SLocEntryTable.end()-I));
377 #endif
378       FileID Res = FileID::get(MiddleIndex);
379 
380       // If this isn't an instantiation, remember it.  We have good locality
381       // across FileID lookups.
382       if (!I->isInstantiation())
383         LastFileIDLookup = Res;
384       NumBinaryProbes += NumProbes;
385       return Res;
386     }
387 
388     // Otherwise, move the low-side up to the middle index.
389     LessIndex = MiddleIndex;
390   }
391 }
392 
393 SourceLocation SourceManager::
394 getInstantiationLocSlowCase(SourceLocation Loc) const {
395   do {
396     std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
397     Loc =getSLocEntry(LocInfo.first).getInstantiation().getInstantiationLoc();
398     Loc = Loc.getFileLocWithOffset(LocInfo.second);
399   } while (!Loc.isFileID());
400 
401   return Loc;
402 }
403 
404 SourceLocation SourceManager::getSpellingLocSlowCase(SourceLocation Loc) const {
405   do {
406     std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
407     Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc();
408     Loc = Loc.getFileLocWithOffset(LocInfo.second);
409   } while (!Loc.isFileID());
410   return Loc;
411 }
412 
413 
414 std::pair<FileID, unsigned>
415 SourceManager::getDecomposedInstantiationLocSlowCase(const SrcMgr::SLocEntry *E,
416                                                      unsigned Offset) const {
417   // If this is an instantiation record, walk through all the instantiation
418   // points.
419   FileID FID;
420   SourceLocation Loc;
421   do {
422     Loc = E->getInstantiation().getInstantiationLoc();
423 
424     FID = getFileID(Loc);
425     E = &getSLocEntry(FID);
426     Offset += Loc.getOffset()-E->getOffset();
427   } while (!Loc.isFileID());
428 
429   return std::make_pair(FID, Offset);
430 }
431 
432 std::pair<FileID, unsigned>
433 SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E,
434                                                 unsigned Offset) const {
435   // If this is an instantiation record, walk through all the instantiation
436   // points.
437   FileID FID;
438   SourceLocation Loc;
439   do {
440     Loc = E->getInstantiation().getSpellingLoc();
441 
442     FID = getFileID(Loc);
443     E = &getSLocEntry(FID);
444     Offset += Loc.getOffset()-E->getOffset();
445   } while (!Loc.isFileID());
446 
447   return std::make_pair(FID, Offset);
448 }
449 
450 
451 //===----------------------------------------------------------------------===//
452 // Queries about the code at a SourceLocation.
453 //===----------------------------------------------------------------------===//
454 
455 /// getCharacterData - Return a pointer to the start of the specified location
456 /// in the appropriate MemoryBuffer.
457 const char *SourceManager::getCharacterData(SourceLocation SL) const {
458   // Note that this is a hot function in the getSpelling() path, which is
459   // heavily used by -E mode.
460   std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(SL);
461 
462   // Note that calling 'getBuffer()' may lazily page in a source file.
463   return getSLocEntry(LocInfo.first).getFile().getContentCache()
464               ->getBuffer()->getBufferStart() + LocInfo.second;
465 }
466 
467 
468 /// getColumnNumber - Return the column # for the specified file position.
469 /// this is significantly cheaper to compute than the line number.  This returns
470 /// zero if the column number isn't known.
471 unsigned SourceManager::getColumnNumber(SourceLocation Loc) const {
472   if (Loc.isInvalid()) return 0;
473   assert(Loc.isFileID() && "Don't know what part of instantiation loc to get");
474 
475   std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
476   unsigned FilePos = LocInfo.second;
477 
478   const char *Buf = getBuffer(LocInfo.first)->getBufferStart();
479 
480   unsigned LineStart = FilePos;
481   while (LineStart && Buf[LineStart-1] != '\n' && Buf[LineStart-1] != '\r')
482     --LineStart;
483   return FilePos-LineStart+1;
484 }
485 
486 static void ComputeLineNumbers(ContentCache* FI,
487                                llvm::BumpPtrAllocator &Alloc) DISABLE_INLINE;
488 static void ComputeLineNumbers(ContentCache* FI, llvm::BumpPtrAllocator &Alloc){
489   // Note that calling 'getBuffer()' may lazily page in the file.
490   const MemoryBuffer *Buffer = FI->getBuffer();
491 
492   // Find the file offsets of all of the *physical* source lines.  This does
493   // not look at trigraphs, escaped newlines, or anything else tricky.
494   std::vector<unsigned> LineOffsets;
495 
496   // Line #1 starts at char 0.
497   LineOffsets.push_back(0);
498 
499   const unsigned char *Buf = (const unsigned char *)Buffer->getBufferStart();
500   const unsigned char *End = (const unsigned char *)Buffer->getBufferEnd();
501   unsigned Offs = 0;
502   while (1) {
503     // Skip over the contents of the line.
504     // TODO: Vectorize this?  This is very performance sensitive for programs
505     // with lots of diagnostics and in -E mode.
506     const unsigned char *NextBuf = (const unsigned char *)Buf;
507     while (*NextBuf != '\n' && *NextBuf != '\r' && *NextBuf != '\0')
508       ++NextBuf;
509     Offs += NextBuf-Buf;
510     Buf = NextBuf;
511 
512     if (Buf[0] == '\n' || Buf[0] == '\r') {
513       // If this is \n\r or \r\n, skip both characters.
514       if ((Buf[1] == '\n' || Buf[1] == '\r') && Buf[0] != Buf[1])
515         ++Offs, ++Buf;
516       ++Offs, ++Buf;
517       LineOffsets.push_back(Offs);
518     } else {
519       // Otherwise, this is a null.  If end of file, exit.
520       if (Buf == End) break;
521       // Otherwise, skip the null.
522       ++Offs, ++Buf;
523     }
524   }
525 
526   // Copy the offsets into the FileInfo structure.
527   FI->NumLines = LineOffsets.size();
528   FI->SourceLineCache = Alloc.Allocate<unsigned>(LineOffsets.size());
529   std::copy(LineOffsets.begin(), LineOffsets.end(), FI->SourceLineCache);
530 }
531 
532 /// getLineNumber - Given a SourceLocation, return the spelling line number
533 /// for the position indicated.  This requires building and caching a table of
534 /// line offsets for the MemoryBuffer, so this is not cheap: use only when
535 /// about to emit a diagnostic.
536 unsigned SourceManager::getLineNumber(SourceLocation Loc) const {
537   if (Loc.isInvalid()) return 0;
538   assert(Loc.isFileID() && "Don't know what part of instantiation loc to get");
539 
540   std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc);
541 
542   ContentCache *Content;
543   if (LastLineNoFileIDQuery == LocInfo.first)
544     Content = LastLineNoContentCache;
545   else
546     Content = const_cast<ContentCache*>(getSLocEntry(LocInfo.first)
547                                         .getFile().getContentCache());
548 
549   // If this is the first use of line information for this buffer, compute the
550   /// SourceLineCache for it on demand.
551   if (Content->SourceLineCache == 0)
552     ComputeLineNumbers(Content, ContentCacheAlloc);
553 
554   // Okay, we know we have a line number table.  Do a binary search to find the
555   // line number that this character position lands on.
556   unsigned *SourceLineCache = Content->SourceLineCache;
557   unsigned *SourceLineCacheStart = SourceLineCache;
558   unsigned *SourceLineCacheEnd = SourceLineCache + Content->NumLines;
559 
560   unsigned QueriedFilePos = LocInfo.second+1;
561 
562   // If the previous query was to the same file, we know both the file pos from
563   // that query and the line number returned.  This allows us to narrow the
564   // search space from the entire file to something near the match.
565   if (LastLineNoFileIDQuery == LocInfo.first) {
566     if (QueriedFilePos >= LastLineNoFilePos) {
567       SourceLineCache = SourceLineCache+LastLineNoResult-1;
568 
569       // The query is likely to be nearby the previous one.  Here we check to
570       // see if it is within 5, 10 or 20 lines.  It can be far away in cases
571       // where big comment blocks and vertical whitespace eat up lines but
572       // contribute no tokens.
573       if (SourceLineCache+5 < SourceLineCacheEnd) {
574         if (SourceLineCache[5] > QueriedFilePos)
575           SourceLineCacheEnd = SourceLineCache+5;
576         else if (SourceLineCache+10 < SourceLineCacheEnd) {
577           if (SourceLineCache[10] > QueriedFilePos)
578             SourceLineCacheEnd = SourceLineCache+10;
579           else if (SourceLineCache+20 < SourceLineCacheEnd) {
580             if (SourceLineCache[20] > QueriedFilePos)
581               SourceLineCacheEnd = SourceLineCache+20;
582           }
583         }
584       }
585     } else {
586       SourceLineCacheEnd = SourceLineCache+LastLineNoResult+1;
587     }
588   }
589 
590   // If the spread is large, do a "radix" test as our initial guess, based on
591   // the assumption that lines average to approximately the same length.
592   // NOTE: This is currently disabled, as it does not appear to be profitable in
593   // initial measurements.
594   if (0 && SourceLineCacheEnd-SourceLineCache > 20) {
595     unsigned FileLen = Content->SourceLineCache[Content->NumLines-1];
596 
597     // Take a stab at guessing where it is.
598     unsigned ApproxPos = Content->NumLines*QueriedFilePos / FileLen;
599 
600     // Check for -10 and +10 lines.
601     unsigned LowerBound = std::max(int(ApproxPos-10), 0);
602     unsigned UpperBound = std::min(ApproxPos+10, FileLen);
603 
604     // If the computed lower bound is less than the query location, move it in.
605     if (SourceLineCache < SourceLineCacheStart+LowerBound &&
606         SourceLineCacheStart[LowerBound] < QueriedFilePos)
607       SourceLineCache = SourceLineCacheStart+LowerBound;
608 
609     // If the computed upper bound is greater than the query location, move it.
610     if (SourceLineCacheEnd > SourceLineCacheStart+UpperBound &&
611         SourceLineCacheStart[UpperBound] >= QueriedFilePos)
612       SourceLineCacheEnd = SourceLineCacheStart+UpperBound;
613   }
614 
615   unsigned *Pos
616     = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
617   unsigned LineNo = Pos-SourceLineCacheStart;
618 
619   LastLineNoFileIDQuery = LocInfo.first;
620   LastLineNoContentCache = Content;
621   LastLineNoFilePos = QueriedFilePos;
622   LastLineNoResult = LineNo;
623   return LineNo;
624 }
625 
626 /// getPresumedLoc - This method returns the "presumed" location of a
627 /// SourceLocation specifies.  A "presumed location" can be modified by #line
628 /// or GNU line marker directives.  This provides a view on the data that a
629 /// user should see in diagnostics, for example.
630 ///
631 /// Note that a presumed location is always given as the instantiation point
632 /// of an instantiation location, not at the spelling location.
633 PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const {
634   if (Loc.isInvalid()) return PresumedLoc();
635 
636   // Presumed locations are always for instantiation points.
637   Loc = getInstantiationLoc(Loc);
638 
639   // FIXME: Could just decompose Loc once!
640 
641   const SrcMgr::FileInfo &FI = getSLocEntry(getFileID(Loc)).getFile();
642   const SrcMgr::ContentCache *C = FI.getContentCache();
643 
644   // To get the source name, first consult the FileEntry (if one exists) before
645   // the MemBuffer as this will avoid unnecessarily paging in the MemBuffer.
646   const char *Filename =
647     C->Entry ? C->Entry->getName() : C->getBuffer()->getBufferIdentifier();
648 
649   return PresumedLoc(Filename, getLineNumber(Loc), getColumnNumber(Loc),
650                      FI.getIncludeLoc());
651 }
652 
653 //===----------------------------------------------------------------------===//
654 // Other miscellaneous methods.
655 //===----------------------------------------------------------------------===//
656 
657 
658 /// PrintStats - Print statistics to stderr.
659 ///
660 void SourceManager::PrintStats() const {
661   llvm::cerr << "\n*** Source Manager Stats:\n";
662   llvm::cerr << FileInfos.size() << " files mapped, " << MemBufferInfos.size()
663              << " mem buffers mapped.\n";
664   llvm::cerr << SLocEntryTable.size() << " SLocEntry's allocated, "
665              << NextOffset << "B of Sloc address space used.\n";
666 
667   unsigned NumLineNumsComputed = 0;
668   unsigned NumFileBytesMapped = 0;
669   for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
670     NumLineNumsComputed += I->second->SourceLineCache != 0;
671     NumFileBytesMapped  += I->second->getSizeBytesMapped();
672   }
673 
674   llvm::cerr << NumFileBytesMapped << " bytes of files mapped, "
675              << NumLineNumsComputed << " files with line #'s computed.\n";
676   llvm::cerr << "FileID scans: " << NumLinearScans << " linear, "
677              << NumBinaryProbes << " binary.\n";
678 }
679 
680 //===----------------------------------------------------------------------===//
681 // Serialization.
682 //===----------------------------------------------------------------------===//
683 
684 void ContentCache::Emit(llvm::Serializer& S) const {
685   S.FlushRecord();
686   S.EmitPtr(this);
687 
688   if (Entry) {
689     llvm::sys::Path Fname(Buffer->getBufferIdentifier());
690 
691     if (Fname.isAbsolute())
692       S.EmitCStr(Fname.c_str());
693     else {
694       // Create an absolute path.
695       // FIXME: This will potentially contain ".." and "." in the path.
696       llvm::sys::Path path = llvm::sys::Path::GetCurrentDirectory();
697       path.appendComponent(Fname.c_str());
698       S.EmitCStr(path.c_str());
699     }
700   }
701   else {
702     const char* p = Buffer->getBufferStart();
703     const char* e = Buffer->getBufferEnd();
704 
705     S.EmitInt(e-p);
706 
707     for ( ; p != e; ++p)
708       S.EmitInt(*p);
709   }
710 
711   S.FlushRecord();
712 }
713 
714 void ContentCache::ReadToSourceManager(llvm::Deserializer& D,
715                                        SourceManager& SMgr,
716                                        FileManager* FMgr,
717                                        std::vector<char>& Buf) {
718   if (FMgr) {
719     llvm::SerializedPtrID PtrID = D.ReadPtrID();
720     D.ReadCStr(Buf,false);
721 
722     // Create/fetch the FileEntry.
723     const char* start = &Buf[0];
724     const FileEntry* E = FMgr->getFile(start,start+Buf.size());
725 
726     // FIXME: Ideally we want a lazy materialization of the ContentCache
727     //  anyway, because we don't want to read in source files unless this
728     //  is absolutely needed.
729     if (!E)
730       D.RegisterPtr(PtrID,NULL);
731     else
732       // Get the ContextCache object and register it with the deserializer.
733       D.RegisterPtr(PtrID, SMgr.getOrCreateContentCache(E));
734     return;
735   }
736 
737   // Register the ContextCache object with the deserializer.
738   /* FIXME:
739   ContentCache *Entry
740   SMgr.MemBufferInfos.push_back(ContentCache());
741    = const_cast<ContentCache&>(SMgr.MemBufferInfos.back());
742   D.RegisterPtr(&Entry);
743 
744   // Create the buffer.
745   unsigned Size = D.ReadInt();
746   Entry.Buffer = MemoryBuffer::getNewUninitMemBuffer(Size);
747 
748   // Read the contents of the buffer.
749   char* p = const_cast<char*>(Entry.Buffer->getBufferStart());
750   for (unsigned i = 0; i < Size ; ++i)
751     p[i] = D.ReadInt();
752    */
753 }
754 
755 void SourceManager::Emit(llvm::Serializer& S) const {
756   S.EnterBlock();
757   S.EmitPtr(this);
758   S.EmitInt(MainFileID.getOpaqueValue());
759 
760   // Emit: FileInfos.  Just emit the file name.
761   S.EnterBlock();
762 
763   // FIXME: Emit FileInfos.
764   //std::for_each(FileInfos.begin(), FileInfos.end(),
765   //              S.MakeEmitter<ContentCache>());
766 
767   S.ExitBlock();
768 
769   // Emit: MemBufferInfos
770   S.EnterBlock();
771 
772   /* FIXME: EMIT.
773   std::for_each(MemBufferInfos.begin(), MemBufferInfos.end(),
774                 S.MakeEmitter<ContentCache>());
775    */
776 
777   S.ExitBlock();
778 
779   // FIXME: Emit SLocEntryTable.
780 
781   S.ExitBlock();
782 }
783 
784 SourceManager*
785 SourceManager::CreateAndRegister(llvm::Deserializer &D, FileManager &FMgr) {
786   SourceManager *M = new SourceManager();
787   D.RegisterPtr(M);
788 
789   // Read: the FileID of the main source file of the translation unit.
790   M->MainFileID = FileID::get(D.ReadInt());
791 
792   std::vector<char> Buf;
793 
794   /*{ // FIXME Read: FileInfos.
795     llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation();
796     while (!D.FinishedBlock(BLoc))
797     ContentCache::ReadToSourceManager(D,*M,&FMgr,Buf);
798   }*/
799 
800   { // Read: MemBufferInfos.
801     llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation();
802     while (!D.FinishedBlock(BLoc))
803     ContentCache::ReadToSourceManager(D,*M,NULL,Buf);
804   }
805 
806   // FIXME: Read SLocEntryTable.
807 
808   return M;
809 }
810