Make source location lightweight

Fixes #24

So far the code has used a representation for source locations that is heavy-weight, but typical of research or hobby compilers: a `struct` type containing a line number and a (heap-allocated) string.
This is actually very convenient for debugging, but it means that any data structure that might contain a source location needs careful memory management (because of those strings) and has a tendency to bloat.

The new represnetation is that a source location is just a pointer-sized integer.
In the simplest mental model, you can think of this as just counting every byte of source text that is passed in, and using those to name locations.

Finding the path and line number that corresponds to a location involves a lookup step, but we can arrange to store all the files in an array sorted by their start locations, and do a binary search.
Finding line numbers inside a file is similarly fast (one you pay a one-time cost to build an array of starting offsets for lines).

More advanced compilers like clang actually go further and create a unique range of source locations to represent a file each time it gets included, so that they can track the include stack and reproduce it in diagnostic messages.
I'm not doing anything that clever here.

1 files changed, 173 insertions, 28 deletions

diff --git a/source/slang/source-loc.h b/source/slang/source-loc.h
index 59f2f10ea..8bb89c645 100644
--- a/source/slang/source-loc.h
+++ b/source/slang/source-loc.h
@@ -6,36 +6,181 @@
 
 namespace Slang {
 
-class CodePosition
+class SourceLoc
 {
 public:
-	int Line = -1, Col = -1, Pos = -1;
-	String FileName;
-	String ToString()
-	{
-		StringBuilder sb(100);
-		sb << FileName;
-		if (Line != -1)
-			sb << "(" << Line << ")";
-		return sb.ProduceString();
-	}
-	CodePosition() = default;
-	CodePosition(int line, int col, int pos, String fileName)
-	{
-		Line = line;
-		Col = col;
-		Pos = pos;
-		this->FileName = fileName;
-	}
-	bool operator < (const CodePosition & pos) const
-	{
-		return FileName < pos.FileName || (FileName == pos.FileName && Line < pos.Line) ||
-			(FileName == pos.FileName && Line == pos.Line && Col < pos.Col);
-	}
-	bool operator == (const CodePosition & pos) const
-	{
-		return FileName == pos.FileName && Line == pos.Line && Col == pos.Col;
-	}
+    typedef UInt RawValue;
+
+private:
+    RawValue raw;
+
+public:
+    SourceLoc()
+        : raw(0)
+    {}
+
+    SourceLoc(
+        SourceLoc const& loc)
+        : raw(loc.raw)
+    {}
+
+    RawValue getRaw() const { return raw; }
+    void setRaw(RawValue value) { raw = value; }
+
+    static SourceLoc fromRaw(RawValue value)
+    {
+        SourceLoc result;
+        result.setRaw(value);
+        return result;
+    }
+
+    bool isValid() const
+    {
+        return raw != 0;
+    }
+};
+
+inline SourceLoc operator+(SourceLoc loc, Int offset)
+{
+    return SourceLoc::fromRaw(loc.getRaw() + UInt(offset));
+}
+
+// A range of locations in the input source
+struct SourceRange
+{
+    SourceRange()
+    {}
+
+    SourceRange(SourceLoc loc)
+        : begin(loc)
+        , end(loc)
+    {}
+
+    SourceRange(SourceLoc begin, SourceLoc end)
+        : begin(begin)
+        , end(end)
+    {}
+
+    SourceLoc begin;
+    SourceLoc end;
+};
+
+// A logical or phyiscal storage object for a range of input code
+// that has logically contiguous source locations.
+class SourceFile : public RefObject
+{
+public:
+    // The logical file path to report for locations inside this span.
+    String path;
+
+    // The actual contents of the file.
+    String content;
+
+    // The range of source locations that the span covers
+    SourceRange sourceRange;
+
+    // In order to speed up lookup of line number information,
+    // we will cache the starting offset of each line break in
+    // the input file:
+    List<UInt> lineBreakOffsets;
+};
+
+struct SourceManager;
+
+// A source location in a format a human might like to see
+struct HumaneSourceLoc
+{
+    String  path;
+    Int     line = 0;
+    Int     column = 0;
+
+    String const& getPath() const { return path; }
+    Int getLine() const { return line; }
+    Int getColumn() const { return column; }
+};
+
+// A source location that has been expanded with the info
+// needed to reconstruct a "humane" location if needed.
+struct ExpandedSourceLoc : public SourceLoc
+{
+    // The source manager that owns this location
+    SourceManager*  sourceManager = nullptr;
+
+    // The entry index that is used to understand the location
+    UInt            entryIndex = 0;
+
+    // Get the nominal path for this location
+    String getPath() const;
+
+    // Get the actual file path where this location appears
+    String getSpellingPath() const;
+
+    // Get the original source file that holds this location
+    SourceFile* getSourceFile() const;
+};
+
+
+
+struct SourceManager
+{
+    // Initialize a source manager, with an optional parent
+    void initialize(
+        SourceManager*  parent);
+
+    SourceRange allocateSourceRange(UInt size);
+
+    SourceFile* allocateSourceFile(
+        String const&   path,
+        String const&   content);
+
+    SourceLoc allocateSourceFileForLineDirective(
+        SourceLoc const&    directiveLoc,
+        String const&       path,
+        UInt                line);
+
+    // Expand a source location to include more explicit info
+    ExpandedSourceLoc expandSourceLoc(SourceLoc const& loc);
+
+    // Get a "humane" version of a source location
+    HumaneSourceLoc getHumaneLoc(ExpandedSourceLoc const& loc);
+    HumaneSourceLoc getHumaneLoc(SourceLoc const& loc);
+
+
+    // Get the source location that represents the spelling location corresponding to a location.
+    SourceLoc getSpellingLoc(ExpandedSourceLoc const& loc);
+    SourceLoc getSpellingLoc(SourceLoc const& loc);
+
+    // The first location available to this source manager
+    // (may not be the first location of all, because we might
+    // have a parent source manager)
+    SourceLoc startLoc;
+
+    // The "parent" source manager that owns locations ahead of `startLoc`
+    SourceManager* parent = nullptr;
+
+    // The location to be used by the next source file to be loaded
+    SourceLoc nextLoc;
+
+    // Each entry represents some contiguous span of locations that
+    // all map to the same logical file.
+    struct Entry
+    {
+        // Where does this entry begin?
+        SourceLoc        startLoc;
+
+        // The soure file that represents the actual data
+        RefPtr<SourceFile>  sourceFile;
+
+        // What is the presumed path for this entry
+        String path;
+
+        // Adjustment to apply to source line numbers when printing presumed locations
+        Int lineAdjust = 0;
+    };
+
+    // An array of soure files we have loaded, ordered by
+    // increasing starting location
+    List<Entry> sourceFiles;
 };