SourceManager: Encapsulate line number mapping into SrcMgr::LineOffsetMapping

[dexonsmith]

Summary

Put the guts of ComputeLineNumbers into LineOffsetMapping::get and
LineOffsetMapping::LineOffsetMapping. As a drive-by, store the number
of lines directly in the bump-ptr-allocated array.

[dexonsmith]

Renamed getNumLines() to size(), which is more natural given begin() and end().

[dexonsmith]

Fix an off-by-one bug in LineOffsetMapping::LineOffsetMapping, add unit tests, and clang-format.

[dexonsmith]

Add the unittest (constructTwo) that caught the off-by-one bug, somehow missed in the last update.

[JDevlieghere]

clang/include/clang/Basic/SourceManager.h

118

I guess it's implicit in the implementation, but maybe it's worth adding a comment describing the layout (first element is the size, elements at index i are at index i+1.

[dexonsmith]

clang/include/clang/Basic/SourceManager.h

118

Thanks, good idea; I'll have that in the commit.

[v.g.vassilev]

@dexonsmith thanks for doing that cleanup!

I am currently trying to rebase https://reviews.llvm.org/D33275 on top of our internal infrastructure. We (cling) use SourceManager::overrideFileContents to provide virtual file content. It seems that every call to ContentCache::getBufferOrNone should somehow consider if the content was not overridden. Do you see an easy way to get D33275 aligned to LineOffsetMapping? Alternatively, we could require a SourceManager& argument to ContentCache::getBufferOrNone and return the overridden buffer...

clang/include/clang/Basic/SourceManager.h

inline bool isSystem(CharacteristicKind CK) {
     return CK != C_User && CK != C_User_ModuleMap;
   }
 
   /// Determine whether a file characteristic is for a module map.
   inline bool isModuleMap(CharacteristicKind CK) {
     return CK == C_User_ModuleMap || CK == C_System_ModuleMap;
   }
 
+  /// Mapping of line offsets into a source file. This does not own the storage
+  /// for the line numbers.
+  class LineOffsetMapping {
+  public:
+    explicit operator bool() const { return Storage; }
+    unsigned size() const {
+      assert(Storage);
+      return Storage[0];
+    }
+    ArrayRef<unsigned> getLines() const {
+      assert(Storage);
+      return ArrayRef<unsigned>(Storage + 1, Storage + 1 + size());
+    }
+    const unsigned *begin() const { return getLines().begin(); }
+    const unsigned *end() const { return getLines().end(); }
+    const unsigned &operator[](int I) const { return getLines()[I]; }
+
+    static LineOffsetMapping get(llvm::MemoryBufferRef Buffer,
+                                 llvm::BumpPtrAllocator &Alloc);
+
+    LineOffsetMapping() = default;
+    LineOffsetMapping(ArrayRef<unsigned> LineOffsets,
+                      llvm::BumpPtrAllocator &Alloc);
+
+  private:
+    /// First element is the size, followed by elements at off-by-one indexes.
+    unsigned *Storage = nullptr;
+  };
+
   /// One instance of this struct is kept for every file loaded or used.
   ///
   /// This object owns the MemoryBuffer object.
   class alignas(8) ContentCache {
     /// The actual buffer containing the characters from the input
     /// file.
     mutable std::unique_ptr<llvm::MemoryBuffer> Buffer;
 
public:
     /// References the file which the contents were actually loaded from.
     ///
     /// Can be different from 'Entry' if we overridden the contents of one file
     /// with the contents of another file.
     const FileEntry *ContentsEntry;
 
     /// A bump pointer allocated array of offsets for each source line.
     ///
-    /// This is lazily computed.  This is owned by the SourceManager
+    /// This is lazily computed.  The lines are owned by the SourceManager
     /// BumpPointerAllocator object.
-    unsigned *SourceLineCache = nullptr;
-
-    /// The number of lines in this ContentCache.
-    ///
-    /// This is only valid if SourceLineCache is non-null.
-    unsigned NumLines = 0;
+    LineOffsetMapping SourceLineCache;
 
     /// Indicates whether the buffer itself was provided to override
     /// the actual file contents.
     ///
     /// When true, the original entry may be a virtual file that does not
     /// exist.
     unsigned BufferOverridden : 1;
 
public:
     /// a non-NULL Buffer or SourceLineCache.  Ownership of allocated memory
     /// is not transferred, so this is a logical error.
     ContentCache(const ContentCache &RHS)
         : BufferOverridden(false), IsFileVolatile(false), IsTransient(false),
           IsBufferInvalid(false) {
       OrigEntry = RHS.OrigEntry;
       ContentsEntry = RHS.ContentsEntry;
 
-      assert(!RHS.Buffer && RHS.SourceLineCache == nullptr &&
+      assert(!RHS.Buffer && !RHS.SourceLineCache &&
              "Passed ContentCache object cannot own a buffer.");
-
-      NumLines = RHS.NumLines;
     }
 
     ContentCache &operator=(const ContentCache& RHS) = delete;
 
     /// Returns the memory buffer for the associated content.
     ///
     /// \param Diag Object through which diagnostics will be emitted if the
     ///   buffer cannot be retrieved.

clang/lib/Basic/SourceManager.cpp

if (FilePos > MemBuf->getBufferSize()) {
     if (Invalid)
       *Invalid = true;
     return 1;
   }
 
   const char *Buf = MemBuf->getBufferStart();
   // See if we just calculated the line number for this FilePos and can use
   // that to lookup the start of the line instead of searching for it.
-  if (LastLineNoFileIDQuery == FID &&
-      LastLineNoContentCache->SourceLineCache != nullptr &&
-      LastLineNoResult < LastLineNoContentCache->NumLines) {
-    unsigned *SourceLineCache = LastLineNoContentCache->SourceLineCache;
+  if (LastLineNoFileIDQuery == FID && LastLineNoContentCache->SourceLineCache &&
+      LastLineNoResult < LastLineNoContentCache->SourceLineCache.size()) {
+    const unsigned *SourceLineCache =
+        LastLineNoContentCache->SourceLineCache.begin();
     unsigned LineStart = SourceLineCache[LastLineNoResult - 1];
     unsigned LineEnd = SourceLineCache[LastLineNoResult];
     if (FilePos >= LineStart && FilePos < LineEnd) {
       // LineEnd is the LineStart of the next line.
       // A line ends with separator LF or CR+LF on Windows.
       // FilePos might point to the last separator,
       // but we need a column number at most 1 + the last column.
       if (FilePos + 1 == LineEnd && FilePos > LineStart) {
static void ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI,
                                const SourceManager &SM, bool &Invalid) {
   // Note that calling 'getBuffer()' may lazily page in the file.
   llvm::Optional<llvm::MemoryBufferRef> Buffer =
       FI->getBufferOrNone(Diag, SM.getFileManager(), SourceLocation());
   Invalid = !Buffer;
   if (Invalid)
     return;
 
+  FI->SourceLineCache = LineOffsetMapping::get(*Buffer, Alloc);
+}
+
+LineOffsetMapping LineOffsetMapping::get(llvm::MemoryBufferRef Buffer,
+                                         llvm::BumpPtrAllocator &Alloc) {
   // Find the file offsets of all of the *physical* source lines.  This does
   // not look at trigraphs, escaped newlines, or anything else tricky.
   SmallVector<unsigned, 256> LineOffsets;
 
   // Line #1 starts at char 0.
   LineOffsets.push_back(0);
 
-  const unsigned char *Buf = (const unsigned char *)Buffer->getBufferStart();
-  const unsigned char *End = (const unsigned char *)Buffer->getBufferEnd();
+  const unsigned char *Buf = (const unsigned char *)Buffer.getBufferStart();
+  const unsigned char *End = (const unsigned char *)Buffer.getBufferEnd();
   const std::size_t BufLen = End - Buf;
   unsigned I = 0;
   while (I < BufLen) {
     if (Buf[I] == '\n') {
       LineOffsets.push_back(I + 1);
     } else if (Buf[I] == '\r') {
       // If this is \r\n, skip both characters.
       if (I + 1 < BufLen && Buf[I + 1] == '\n')
         ++I;
       LineOffsets.push_back(I + 1);
     }
     ++I;
   }
 
-  // Copy the offsets into the FileInfo structure.
-  FI->NumLines = LineOffsets.size();
-  FI->SourceLineCache = Alloc.Allocate<unsigned>(LineOffsets.size());
-  std::copy(LineOffsets.begin(), LineOffsets.end(), FI->SourceLineCache);
+  return LineOffsetMapping(LineOffsets, Alloc);
+}
+
+LineOffsetMapping::LineOffsetMapping(ArrayRef<unsigned> LineOffsets,
+                                     llvm::BumpPtrAllocator &Alloc)
+    : Storage(Alloc.Allocate<unsigned>(LineOffsets.size() + 1)) {
+  Storage[0] = LineOffsets.size();
+  std::copy(LineOffsets.begin(), LineOffsets.end(), Storage + 1);
 }
 
 /// getLineNumber - Given a SourceLocation, return the spelling line number
 /// for the position indicated.  This requires building and caching a table of
 /// line offsets for the MemoryBuffer, so this is not cheap: use only when
 /// about to emit a diagnostic.
 unsigned SourceManager::getLineNumber(FileID FID, unsigned FilePos,
                                       bool *Invalid) const {
if (Invalid)
       *Invalid = MyInvalid;
     if (MyInvalid)
       return 1;
   } else if (Invalid)
     *Invalid = false;
 
   // Okay, we know we have a line number table.  Do a binary search to find the
   // line number that this character position lands on.
-  unsigned *SourceLineCache = Content->SourceLineCache;
-  unsigned *SourceLineCacheStart = SourceLineCache;
-  unsigned *SourceLineCacheEnd = SourceLineCache + Content->NumLines;
+  const unsigned *SourceLineCache = Content->SourceLineCache.begin();
+  const unsigned *SourceLineCacheStart = SourceLineCache;
+  const unsigned *SourceLineCacheEnd = Content->SourceLineCache.end();
 
   unsigned QueriedFilePos = FilePos+1;
 
   // FIXME: I would like to be convinced that this code is worth being as
   // complicated as it is, binary search isn't that slow.
   //
   // If it is worth being optimized, then in my opinion it could be more
   // performant, simpler, and more obviously correct by just "galloping" outward
if (QueriedFilePos >= LastLineNoFilePos) {
             SourceLineCacheEnd = SourceLineCache+10;
           else if (SourceLineCache+20 < SourceLineCacheEnd) {
             if (SourceLineCache[20] > QueriedFilePos)
               SourceLineCacheEnd = SourceLineCache+20;
           }
         }
       }
     } else {
-      if (LastLineNoResult < Content->NumLines)
+      if (LastLineNoResult < Content->SourceLineCache.size())
         SourceLineCacheEnd = SourceLineCache+LastLineNoResult+1;
     }
   }
 
-  unsigned *Pos
-    = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
+  const unsigned *Pos =
+      std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
   unsigned LineNo = Pos-SourceLineCacheStart;
 
   LastLineNoFileIDQuery = FID;
   LastLineNoContentCache = Content;
   LastLineNoFilePos = QueriedFilePos;
   LastLineNoResult = LineNo;
   return LineNo;
 }
if (MyInvalid)
       return SourceLocation();
   }
 
   llvm::Optional<llvm::MemoryBufferRef> Buffer =
       Content->getBufferOrNone(Diag, getFileManager());
   if (!Buffer)
     return SourceLocation();
 
-  if (Line > Content->NumLines) {
+  if (Line > Content->SourceLineCache.size()) {
     unsigned Size = Buffer->getBufferSize();
     if (Size > 0)
       --Size;
     return FileLoc.getLocWithOffset(Size);
   }
 
   unsigned FilePos = Content->SourceLineCache[Line - 1];
   const char *Buf = Buffer->getBufferStart() + FilePos;
void SourceManager::PrintStats() const {
   llvm::errs() << LoadedSLocEntryTable.size()
                << " loaded SLocEntries allocated, "
                << MaxLoadedOffset - CurrentLoadedOffset
                << "B of Sloc address space used.\n";
 
   unsigned NumLineNumsComputed = 0;
   unsigned NumFileBytesMapped = 0;
   for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){
-    NumLineNumsComputed += I->second->SourceLineCache != nullptr;
+    NumLineNumsComputed += bool(I->second->SourceLineCache);
     NumFileBytesMapped  += I->second->getSizeBytesMapped();
   }
   unsigned NumMacroArgsComputed = MacroArgsCacheMap.size();
 
   llvm::errs() << NumFileBytesMapped << " bytes of files mapped, "
                << NumLineNumsComputed << " files with line #'s computed, "
                << NumMacroArgsComputed << " files with macro args computed.\n";
   llvm::errs() << "FileID scans: " << NumLinearScans << " linear, "

clang/lib/Lex/ScratchBuffer.cpp

if (BytesUsed+Len+2 > ScratchBufSize)
     AllocScratchBuffer(Len+2);
   else {
     // Clear out the source line cache if it's already been computed.
     // FIXME: Allow this to be incrementally extended.
     auto *ContentCache = const_cast<SrcMgr::ContentCache *>(
         &SourceMgr.getSLocEntry(SourceMgr.getFileID(BufferStartLoc))
              .getFile()
              .getContentCache());
-    ContentCache->SourceLineCache = nullptr;
+    ContentCache->SourceLineCache = SrcMgr::LineOffsetMapping();
   }
 
   // Prefix the token with a \n, so that it looks like it is the first thing on
   // its own virtual line in caret diagnostics.
   CurBuffer[BytesUsed++] = '\n';
 
   // Return a pointer to the character data.
   DestPtr = CurBuffer+BytesUsed;

clang/unittests/Basic/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(BasicTests
   CharInfoTest.cpp
   DiagnosticTest.cpp
   FileManagerTest.cpp
+  LineOffsetMappingTest.cpp
   SourceManagerTest.cpp
   )
 
 clang_target_link_libraries(BasicTests
   PRIVATE
   clangAST
   clangBasic
   clangLex
   )

clang/unittests/Basic/LineOffsetMappingTest.cpp

+//===- unittests/Basic/LineOffsetMappingTest.cpp - Test LineOffsetMapping -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Basic/SourceManager.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace clang::SrcMgr;
+using namespace llvm;
+
+namespace {
+
+TEST(LineOffsetMappingTest, empty) {
+  LineOffsetMapping Mapping;
+  EXPECT_FALSE(Mapping);
+
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH((void)Mapping.getLines(), "Assertion");
+#endif
+}
+
+TEST(LineOffsetMappingTest, construct) {
+  BumpPtrAllocator Alloc;
+  unsigned Offsets[] = {0, 10, 20};
+  LineOffsetMapping Mapping(Offsets, Alloc);
+  EXPECT_EQ(3u, Mapping.size());
+  EXPECT_EQ(0u, Mapping[0]);
+  EXPECT_EQ(10u, Mapping[1]);
+  EXPECT_EQ(20u, Mapping[2]);
+
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH((void)Mapping[3], "Assertion");
+#endif
+}
+
+TEST(LineOffsetMappingTest, constructTwo) {
+  // Confirm allocation size is big enough, convering an off-by-one bug.
+  BumpPtrAllocator Alloc;
+  unsigned Offsets1[] = {0, 10};
+  unsigned Offsets2[] = {0, 20};
+  LineOffsetMapping Mapping1(Offsets1, Alloc);
+  LineOffsetMapping Mapping2(Offsets2, Alloc);
+
+  // Need to check Mapping1 *after* building Mapping2.
+  EXPECT_EQ(2u, Mapping1.size());
+  EXPECT_EQ(0u, Mapping1[0]);
+  EXPECT_EQ(10u, Mapping1[1]);
+  EXPECT_EQ(2u, Mapping2.size());
+  EXPECT_EQ(0u, Mapping2[0]);
+  EXPECT_EQ(20u, Mapping2[1]);
+}
+
+TEST(LineOffsetMappingTest, get) {
+  BumpPtrAllocator Alloc;
+  StringRef Source = "first line\n"
+                     "second line\n";
+  auto Mapping = LineOffsetMapping::get(MemoryBufferRef(Source, ""), Alloc);
+  EXPECT_EQ(3u, Mapping.size());
+  EXPECT_EQ(0u, Mapping[0]);
+  EXPECT_EQ(11u, Mapping[1]);
+  EXPECT_EQ(23u, Mapping[2]);
+}
+
+TEST(LineOffsetMappingTest, getMissingFinalNewline) {
+  BumpPtrAllocator Alloc;
+  StringRef Source = "first line\n"
+                     "second line";
+  auto Mapping = LineOffsetMapping::get(MemoryBufferRef(Source, ""), Alloc);
+  EXPECT_EQ(2u, Mapping.size());
+  EXPECT_EQ(0u, Mapping[0]);
+  EXPECT_EQ(11u, Mapping[1]);
+}
+
+} // end namespace