SourceMappings

pub const SourceMappings = struct

File

Code

pub const SourceMappings = struct {
    sources: Sources = .{},
    files: StringTable = .{},
    /// The default assumes that the first filename added is the root file.
    /// The value should be set to the correct offset if that assumption does not hold.
    root_filename_offset: u32 = 0,
    source_node_pool: std.heap.MemoryPool(Sources.Node) = .empty,
    end_line: usize = 0,

    const sourceCompare = struct {
        fn compare(a: Source, b: Source) std.math.Order {
            return std.math.order(a.start_line, b.start_line);
        }
    }.compare;
    const Sources = std.Treap(Source, sourceCompare);

    pub const Source = struct {
        start_line: usize,
        span: usize = 0,
        corresponding_start_line: usize,
        filename_offset: u32,
    };

    pub fn deinit(self: *SourceMappings, allocator: Allocator) void {
        self.files.deinit(allocator);
        self.source_node_pool.deinit(std.heap.page_allocator);
    }

    /// Find the node that 'contains' the `line`, i.e. the node's start_line is
    /// >= `line`
    fn findNode(self: SourceMappings, line: usize) ?*Sources.Node {
        var node = self.sources.root;
        var last_gt: ?*Sources.Node = null;

        var search_key: Source = undefined;
        search_key.start_line = line;
        while (node) |current| {
            const order = sourceCompare(search_key, current.key);
            if (order == .eq) break;
            if (order == .gt) last_gt = current;

            node = current.children[@intFromBool(order == .gt)] orelse {
                // Regardless of the current order, last_gt will contain the
                // the node we want to return.
                //
                // If search key is > current node's key, then last_gt will be
                // current which we now know is the closest node that is <=
                // the search key.
                //
                //
                // If the key is < current node's key, we want to jump back to the
                // node that the search key was most recently greater than.
                // This is necessary for scenarios like (where the search key is 2):
                //
                //   1
                //    \
                //     6
                //    /
                //   3
                //
                // In this example, we'll get down to the '3' node but ultimately want
                // to return the '1' node.
                //
                // Note: If we've never seen a key that the search key is greater than,
                // then we know that there's no valid node, so last_gt will be null.
                return last_gt;
            };
        }

        return node;
    }

    /// Note: `line_num` and `corresponding_line_num` start at 1
    pub fn set(self: *SourceMappings, line_num: usize, corresponding_line_num: usize, filename_offset: u32) !void {
        const maybe_node = self.findNode(line_num);

        const need_new_node = need_new_node: {
            if (maybe_node) |node| {
                if (node.key.filename_offset != filename_offset) {
                    break :need_new_node true;
                }
                // TODO: These use i65 to avoid truncation when any of the line number values
                //       use all 64 bits of the usize. In reality, line numbers can't really
                //       get that large so limiting the line number and using a smaller iX
                //       type here might be a better solution.
                const exist_delta = @as(i65, @intCast(node.key.corresponding_start_line)) - @as(i65, @intCast(node.key.start_line));
                const cur_delta = @as(i65, @intCast(corresponding_line_num)) - @as(i65, @intCast(line_num));
                if (exist_delta != cur_delta) {
                    break :need_new_node true;
                }
                break :need_new_node false;
            }
            break :need_new_node true;
        };
        if (need_new_node) {
            // spans must not overlap
            if (maybe_node) |node| {
                std.debug.assert(node.key.start_line != line_num);
            }

            const key = Source{
                .start_line = line_num,
                .corresponding_start_line = corresponding_line_num,
                .filename_offset = filename_offset,
            };
            var entry = self.sources.getEntryFor(key);
            var new_node = try self.source_node_pool.create(std.heap.page_allocator);
            new_node.key = key;
            entry.set(new_node);
        }
        if (line_num > self.end_line) {
            self.end_line = line_num;
        }
    }

    /// Note: `line_num` starts at 1
    pub fn get(self: SourceMappings, line_num: usize) ?Source {
        const node = self.findNode(line_num) orelse return null;
        return node.key;
    }

    pub const CorrespondingSpan = struct {
        start_line: usize,
        end_line: usize,
        filename_offset: u32,
    };

    pub fn getCorrespondingSpan(self: SourceMappings, line_num: usize) ?CorrespondingSpan {
        const source = self.get(line_num) orelse return null;
        const diff = line_num - source.start_line;
        const start_line = source.corresponding_start_line + (if (line_num == source.start_line) 0 else source.span + diff);
        const end_line = start_line + (if (line_num == source.start_line) source.span else 0);
        return CorrespondingSpan{
            .start_line = start_line,
            .end_line = end_line,
            .filename_offset = source.filename_offset,
        };
    }

    pub fn collapse(self: *SourceMappings, line_num: usize, num_following_lines_to_collapse: usize) !void {
        std.debug.assert(num_following_lines_to_collapse > 0);
        var node = self.findNode(line_num).?;
        const span_diff = num_following_lines_to_collapse;
        if (node.key.start_line != line_num) {
            const offset = line_num - node.key.start_line;
            const key = Source{
                .start_line = line_num,
                .span = num_following_lines_to_collapse,
                .corresponding_start_line = node.key.corresponding_start_line + node.key.span + offset,
                .filename_offset = node.key.filename_offset,
            };
            var entry = self.sources.getEntryFor(key);
            var new_node = try self.source_node_pool.create(std.heap.page_allocator);
            new_node.key = key;
            entry.set(new_node);
            node = new_node;
        } else {
            node.key.span += span_diff;
        }

        // now subtract the span diff from the start line number of all of
        // the following nodes in order
        var it = Sources.InorderIterator{ .current = node };
        // skip past current, but store it
        var prev = it.next().?;
        while (it.next()) |inorder_node| {
            inorder_node.key.start_line -= span_diff;

            // This can only really happen if there are #line commands within
            // a multiline comment, which should be skipped over.
            std.debug.assert(prev.key.start_line <= inorder_node.key.start_line);
            prev = inorder_node;
        }
        self.end_line -= span_diff;
    }

    /// Returns true if the line is from the main/root file (i.e. not a file that has been
    /// `#include`d).
    pub fn isRootFile(self: *const SourceMappings, line_num: usize) bool {
        const source = self.get(line_num) orelse return false;
        return source.filename_offset == self.root_filename_offset;
    }
}