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