path: root/src/locations.zig

const std = @import("std");
const pardes = @import("pardes.zig");
const look = @import("look.zig");
const syntax = @import("syntax.zig");
const filesystem = @import("fs.zig");

const neighbor_context: u8 = 1;
const declaration_context: u8 = 2;
const declaration_start: u8 = 4;
/// Legacy marked rows and hidden locations remain recognizable without metadata.
/// Visible context locations are flush left and use Row.kind instead.
pub fn isContextLine(line: []const u8) bool {
    return std.mem.startsWith(u8, line, "  ") or std.mem.startsWith(u8, line, "| ");
}

pub const Row = struct {
    kind: enum { match, context, preview },
    declaration: bool = false,
    path: []u8,
    at: look.Spot,
    location_end: usize,
    code_start: usize,
    colors: []u8 = &.{},
};

pub fn freeRows(gpa: std.mem.Allocator, rows: []Row) void {
    for (rows) |row| {
        gpa.free(row.path);
        gpa.free(row.colors);
    }
    gpa.free(rows);
}

pub fn equalRows(a: []const Row, b: []const Row) bool {
    if (a.len != b.len) return false;
    for (a, b) |left, right| {
        if (left.kind != right.kind or left.declaration != right.declaration or !std.meta.eql(left.at, right.at) or
            left.location_end != right.location_end or left.code_start != right.code_start or
            !std.mem.eql(u8, left.path, right.path) or !std.mem.eql(u8, left.colors, right.colors)) return false;
    }
    return true;
}

/// Compare native producer rows with an already formatted, context-free view.
/// Identical refreshes retain allocations, syntax and selection state.
pub fn sameInput(input: []const u8, rendered: []const u8, rows: []const Row, layout: Config.Layout) bool {
    if (rows.len == 0) return std.mem.eql(u8, input, rendered);
    var raw_lines = std.mem.splitScalar(u8, input, '\n');
    var shown_lines = std.mem.splitScalar(u8, rendered, '\n');
    var width: usize = 0;
    var index: usize = 0;
    while (index < rows.len) {
        const row = rows[index];
        if (row.kind != .match) return false;
        if (layout == .@"inline" and index % alignment_entries == 0) {
            width = 0;
            var chunk = raw_lines;
            for (0..alignment_entries) |_| {
                const line = chunk.next() orelse break;
                const target = parseRaw(line);
                width = @max(width, pardes.panes.File.displayWidth(line[0..target.end]));
            }
        }
        const raw = raw_lines.next() orelse return false;
        const shown = shown_lines.next() orelse return false;
        const target = parseRaw(raw);
        if (target.end != row.location_end or row.location_end > shown.len or row.code_start > shown.len or
            !std.mem.eql(u8, raw[0..target.end], shown[0..row.location_end])) return false;
        if (layout == .stacked) {
            if (shown.len != row.location_end or row.code_start != shown.len or index + 1 >= rows.len) return false;
            const preview = rows[index + 1];
            if (preview.kind != .preview or preview.location_end != 0 or preview.code_start != 0 or
                !std.meta.eql(row.at, preview.at) or !std.mem.eql(u8, row.path, preview.path)) return false;
            const code = shown_lines.next() orelse return false;
            if (!std.mem.eql(u8, raw[target.code_start..], code)) return false;
            index += 2;
            continue;
        }
        if (!std.mem.eql(u8, raw[target.code_start..], shown[row.code_start..])) return false;
        // A restored result may still have the old pane-wide padding. Do not
        // let the identical-input shortcut retain that layout when rerun.
        if (row.code_start <= row.location_end) return false;
        const padding = shown[row.location_end..row.code_start];
        if (padding.len != width - pardes.panes.File.displayWidth(raw[0..target.end]) + 1 or
            padding[padding.len - 1] != '\t') return false;
        for (padding[0 .. padding.len - 1]) |byte| if (byte != ' ') return false;
        index += 1;
    }
    const raw_tail = raw_lines.next();
    const shown_tail = shown_lines.next();
    if ((raw_tail == null) != (shown_tail == null)) return false;
    if (raw_tail) |tail| if (tail.len != 0) return false;
    if (shown_tail) |tail| if (tail.len != 0) return false;
    return raw_lines.next() == null and shown_lines.next() == null;
}

pub const Parsed = struct {
    path: []const u8,
    at: look.Spot,
    end: usize,
    code_start: usize,
};

/// The tab separates alignment from code; source indentation after it is data.
pub fn parse(line: []const u8) Parsed {
    if (std.mem.indexOfScalar(u8, line, '\t')) |tab| {
        const prefix = std.mem.trimEnd(u8, line[0..tab], " ");
        const target = parseRaw(prefix);
        if (target.at.line > 0) {
            const suffix = std.mem.trim(u8, prefix[target.end..], " ");
            var stars = true;
            for (suffix) |byte| if (byte != '*') {
                stars = false;
                break;
            };
            if (stars) return .{ .path = target.path, .at = target.at, .end = target.end, .code_start = tab + 1 };
        }
    }
    return parseRaw(line);
}

fn parseRaw(line: []const u8) Parsed {
    var at: usize = 1;
    while (at < line.len) : (at += 1) {
        if (line[at] != ':' or at + 1 == line.len or !std.ascii.isDigit(line[at + 1])) continue;
        const start = at;
        at += 1;
        while (at < line.len and (std.ascii.isDigit(line[at]) or line[at] == ':' or line[at] == '-')) at += 1;
        if (at < line.len and line[at] != ' ' and line[at] != '\t') continue;
        const target = look.parsePathLine(line[start..at]);
        if (target.at.line > 0 and target.end == at - start)
            return .{ .path = line[0..start], .at = target.at, .end = at, .code_start = @min(line.len, at + 1) };
    }
    return .{ .path = line, .at = .{}, .end = line.len, .code_start = line.len };
}

pub const Result = struct {
    content: []u8,
    rows: []Row,
    anchor: ?usize,
};

const Pending = struct {
    path: []const u8,
    at: look.Spot,
    label: []const u8,
    code: []const u8,
    original: ?usize,
    hidden: bool = false,
    declaration: bool = false,
    depth: usize = 0,
    colors: []const u8 = &.{},

    fn lessThan(_: void, a: Pending, b: Pending) bool {
        if (a.at.line != b.at.line) return a.at.line < b.at.line;
        return (a.original orelse std.math.maxInt(usize)) < (b.original orelse std.math.maxInt(usize));
    }
};

const Source = struct { path: []const u8, bytes: []const u8 };

fn sourceText(p: *pardes.Pardes, arena: std.mem.Allocator, dir: []const u8, path: []const u8) ?Source {
    if (std.ascii.eqlIgnoreCase(std.fs.path.extension(path), ".pdf")) return null;
    const lexical = std.fs.path.resolvePosix(arena, &.{ dir, path }) catch return null;
    var pathbuf: [4096]u8 = undefined;
    const full = if (filesystem.resolve(p, path, dir, &pathbuf)) |resolved| resolved.path else lexical;
    for (p.panes) |slot| if (slot) |pane| {
        if (pane.file) |file| if (file.output == null and (std.mem.eql(u8, file.path, full) or std.mem.eql(u8, file.path, lexical))) return .{ .path = lexical, .bytes = file.content };
    };
    const bytes = filesystem.read(p, full) catch return null;
    defer p.gpa.free(bytes);
    return .{ .path = lexical, .bytes = arena.dupe(u8, bytes) catch return null };
}

/// Inputs are sorted results. Expand each source group, merge context with
/// matches, then align groups of eight matches. All temporary source data
/// stays in the caller's scratch arena; returned text and rows are owned.
pub fn format(p: *pardes.Pardes, dir: []const u8, input: []const u8, anchor: ?usize, expand: bool) !Result {
    const arena = p.scratch.allocator();
    var matches: std.ArrayList(Pending) = .empty;
    const body = input[0 .. input.len - @intFromBool(std.mem.endsWith(u8, input, "\n"))];
    var lines = std.mem.splitScalar(u8, body, '\n');
    while (lines.next()) |line| {
        const target = parseRaw(line);
        if (target.at.line == 0) return .{ .content = try p.gpa.dupe(u8, input), .rows = &.{}, .anchor = anchor };
        try matches.append(arena, .{ .path = target.path, .at = target.at, .label = line[0..target.end], .code = line[target.code_start..], .original = matches.items.len });
    }
    var pending: std.ArrayList(Pending) = .empty;
    var first: usize = 0;
    while (first < matches.items.len) {
        var end = first + 1;
        while (end < matches.items.len and std.mem.eql(u8, matches.items[first].path, matches.items[end].path)) : (end += 1) {}
        const path = matches.items[first].path;
        const group_start = pending.items.len;
        try pending.appendSlice(arena, matches.items[first..end]);
        if (expand and (p.locations_config.context > 0 or p.locations_config.tscontext)) {
            if (sourceText(p, arena, dir, path)) |text| {
                const source = text.bytes;
                var source_lines: std.ArrayList([]const u8) = .empty;
                var source_split = std.mem.splitScalar(u8, source, '\n');
                while (source_split.next()) |line| try source_lines.append(arena, line);
                const count = source_lines.items.len;
                const wanted = try arena.alloc(u8, count);
                @memset(wanted, 0);
                // Muted declaration headers do not need a source-color pass.
                // Exact bytes include unsaved edits and virtual/remote sources.
                var cached = p.locations_cache.get(p.tree_sitter_gpa, text.path, source, p.locations_config.tscontext, p.locations_config.context > 0) catch
                    Cache.Hit{ .analysis = syntax.analyzeSource(arena, text.path, source, p.locations_config.tscontext, p.locations_config.context > 0) catch .{} };
                defer cached.deinit(p.tree_sitter_gpa);
                const analysis = cached.analysis;
                const source_colors = analysis.colors;
                const declarations = if (p.locations_config.tscontext) analysis.declarations else &.{};
                for (pending.items[group_start..]) |*match| {
                    const row = match.at.line -| 1;
                    if (row >= count) continue;
                    var enclosing_start: ?usize = null;
                    for (declarations) |declaration| {
                        if (declaration.start_line > row) break;
                        if (declaration.end_line < row) continue;
                        enclosing_start = @min(enclosing_start orelse declaration.start_line, declaration.start_line);
                        match.depth += 1;
                        var header = declaration.start_line;
                        while (header <= declaration.header_end_line and header < row) : (header += 1) {
                            wanted[header] |= declaration_context;
                            if (header == declaration.start_line) wanted[header] |= declaration_start;
                        }
                    }
                    const lo = @max(row -| p.locations_config.context, enclosing_start orelse 0);
                    const hi = @min(count -| 1, row +| p.locations_config.context);
                    var context_row = lo;
                    while (context_row <= hi) : (context_row += 1) {
                        if (context_row == row) continue;
                        wanted[context_row] |= neighbor_context;
                    }
                }
                for (wanted, 0..) |kind, row| {
                    if (kind > 0) {
                        const line = source_lines.items[row];
                        const offset = @intFromPtr(line.ptr) - @intFromPtr(source.ptr);
                        const declaration = kind & declaration_context != 0;
                        const colors = if (!declaration and offset + line.len <= source_colors.len) source_colors[offset..][0..line.len] else &.{};
                        const hidden = !declaration or !p.locations_config.tslocations or kind & declaration_start == 0;
                        // Later source groups may evict this analysis from the cache.
                        try appendContext(arena, &pending, path, line, row, declaration, hidden, try arena.dupe(u8, colors));
                    }
                }
            }
        }
        std.mem.sort(Pending, pending.items[group_start..], {}, Pending.lessThan);
        // Keep every original result, but show each extra source row once.
        var write = group_start;
        for (pending.items[group_start..]) |row| {
            if (row.original == null and write > group_start and pending.items[write - 1].at.line == row.at.line) continue;
            pending.items[write] = row;
            write += 1;
        }
        pending.items.len = write;
        first = end;
    }
    var out: std.Io.Writer.Allocating = .init(p.gpa);
    errdefer out.deinit();
    var rows: std.ArrayList(Row) = .empty;
    errdefer {
        for (rows.items) |row| {
            p.gpa.free(row.path);
            p.gpa.free(row.colors);
        }
        rows.deinit(p.gpa);
    }
    var mapped = anchor;
    if (p.locations_config.layout == .stacked) {
        for (pending.items, 0..) |row, index| {
            const context = row.original == null;
            if (anchor != null and row.original == anchor) mapped = rows.items.len;
            if (!row.hidden) {
                const before = out.written().len;
                try out.writer.writeAll(row.label);
                if (row.depth > 0) {
                    try out.writer.writeByte(' ');
                    try out.writer.splatByteAll('*', row.depth);
                }
                try appendMetadata(p.gpa, &rows, row, if (context) .context else .match, row.label.len, out.written().len - before, false);
                try out.writer.writeByte('\n');
            }
            try writeCode(&out.writer, pending.items, index);
            try appendMetadata(p.gpa, &rows, row, if (context) .context else .preview, 0, 0, true);
            if (index + 1 < pending.items.len or std.mem.endsWith(u8, input, "\n")) try out.writer.writeByte('\n');
        }
    } else {
        first = 0;
        while (first < pending.items.len) {
            const end = alignmentEnd(pending.items, first);
            var width: usize = 0;
            for (pending.items[first..end]) |row| width = @max(width, labelWidth(row));
            for (pending.items[first..end], first..) |row, index| {
                const before = out.written().len;
                const context = row.original == null;
                try out.writer.writeAll(row.label);
                const location_end = if (row.hidden) 0 else out.written().len - before;
                if (row.depth > 0) {
                    try out.writer.writeByte(' ');
                    try out.writer.splatByteAll('*', row.depth);
                }
                try out.writer.splatByteAll(' ', width - labelWidth(row));
                try out.writer.writeByte('\t');
                const code_start = out.written().len - before;
                try writeCode(&out.writer, pending.items, index);
                if (index + 1 < pending.items.len or std.mem.endsWith(u8, input, "\n")) try out.writer.writeByte('\n');
                try appendMetadata(p.gpa, &rows, row, if (context) .context else .match, location_end, code_start, true);
                if (anchor != null and row.original == anchor) mapped = index;
            }
            first = end;
        }
    }
    const owned_rows = try rows.toOwnedSlice(p.gpa);
    errdefer freeRows(p.gpa, owned_rows);
    return .{ .content = try out.toOwnedSlice(), .rows = owned_rows, .anchor = mapped };
}

fn writeCode(writer: *std.Io.Writer, rows: []const Pending, index: usize) !void {
    const row = rows[index];
    try writer.writeAll(row.code);
    if (row.declaration and index + 1 < rows.len) {
        const next = rows[index + 1];
        if (std.mem.eql(u8, row.path, next.path) and next.at.line -| row.at.line > 1)
            try writer.writeAll(" ...");
    }
}

fn appendMetadata(gpa: std.mem.Allocator, rows: *std.ArrayList(Row), pending: Pending, kind: @FieldType(Row, "kind"), location_end: usize, code_start: usize, source: bool) !void {
    const path = try gpa.dupe(u8, pending.path);
    errdefer gpa.free(path);
    const colors = try gpa.dupe(u8, if (source) pending.colors else &.{});
    errdefer gpa.free(colors);
    try rows.append(gpa, .{ .kind = kind, .declaration = pending.declaration, .path = path, .at = pending.at, .location_end = location_end, .code_start = code_start, .colors = colors });
}

const alignment_entries = 8;

/// Keep neighboring context with the nearer match at a chunk boundary. Shared
/// context stays deduplicated; ties belong to the preceding chunk.
fn alignmentEnd(rows: []const Pending, first: usize) usize {
    var matches: usize = 0;
    var previous: usize = first;
    for (rows[first..], first..) |row, index| {
        if (row.original == null) continue;
        if (matches == alignment_entries) {
            var end = index;
            while (end > previous + 1) {
                const context = rows[end - 1];
                if (!std.mem.eql(u8, context.path, row.path)) break;
                if (std.mem.eql(u8, rows[previous].path, row.path) and
                    row.at.line -| context.at.line >= context.at.line -| rows[previous].at.line) break;
                end -= 1;
            }
            return end;
        }
        matches += 1;
        previous = index;
    }
    return rows.len;
}

fn labelWidth(row: Pending) usize {
    return pardes.panes.File.displayWidth(row.label) +
        @as(usize, if (row.depth > 0) row.depth + 1 else 0);
}

fn appendContext(arena: std.mem.Allocator, rows: *std.ArrayList(Pending), path: []const u8, source: []const u8, row: usize, declaration: bool, hidden: bool, colors: []const u8) !void {
    try rows.append(arena, .{
        .path = path,
        .at = .{ .line = row + 1 },
        .label = if (hidden) "" else try std.fmt.allocPrint(arena, "{s}:{d}", .{ path, row + 1 }),
        .code = source,
        .original = null,
        .hidden = hidden,
        .declaration = declaration,
        .colors = colors,
    });
}

test "locations tab delimiter preserves source indentation and spaced paths" {
    const row = parse("some directory/界.zig:12:3-5   \t\t  value");
    try std.testing.expectEqualStrings("some directory/界.zig", row.path);
    try std.testing.expectEqual(@as(usize, 12), row.at.line);
    try std.testing.expectEqualStrings("\t  value", "some directory/界.zig:12:3-5   \t\t  value"[row.code_start..]);
}

test "locations native results retain the first source tab" {
    const text = "some directory/a.zig:3:2 \t  value";
    const row = parseRaw(text);
    try std.testing.expectEqualStrings("some directory/a.zig", row.path);
    try std.testing.expectEqualStrings("\t  value", text[row.code_start..]);
}

// ---- the Locations setting ----

pub const Config = struct {
    pub const Layout = enum { @"inline", stacked };
    context: u16 = 0,
    tscontext: bool = false,
    tslocations: bool = true,
    layout: Layout = .stacked,

    /// Apply only supplied fields. A malformed token rejects the whole update.
    /// Repeating a field uses its last supplied value.
    pub fn parse(current: Config, text: []const u8) !Config {
        var result = current;
        var tokens = std.mem.tokenizeAny(u8, text, " \t\r\n");
        while (tokens.next()) |token| {
            const colon = std.mem.indexOfScalar(u8, token, ':') orelse return error.ExpectedKeyValue;
            const key = token[0..colon];
            const value = token[colon + 1 ..];
            var found = false;
            inline for (@typeInfo(Config).@"struct".fields) |field| {
                if (std.mem.eql(u8, key, field.name)) {
                    @field(result, field.name) = switch (@typeInfo(field.type)) {
                        .bool => if (std.mem.eql(u8, value, "on")) true else if (std.mem.eql(u8, value, "off")) false else return error.ExpectedOnOrOff,
                        .int => std.fmt.parseInt(field.type, value, 10) catch return error.InvalidContext,
                        .@"enum" => std.meta.stringToEnum(field.type, value) orelse return error.InvalidLayout,
                        else => @compileError("unsupported location setting type"),
                    };
                    found = true;
                }
            }
            if (!found) return error.UnknownLocationSetting;
        }
        return result;
    }

    pub fn write(config: Config, writer: *std.Io.Writer) !void {
        inline for (@typeInfo(Config).@"struct".fields, 0..) |field, index| {
            if (index > 0) try writer.writeByte(' ');
            try writer.writeAll(field.name ++ ":");
            const value = @field(config, field.name);
            switch (@typeInfo(field.type)) {
                .bool => try writer.writeAll(if (value) "on" else "off"),
                .int => try writer.print("{d}", .{value}),
                .@"enum" => try writer.writeAll(@tagName(value)),
                else => @compileError("unsupported location setting type"),
            }
        }
    }
};

test "LocationsConfig reflection round trip and partial updates" {
    var config: Config = .{};
    config = try config.parse("context:5 tscontext:on");
    config = try config.parse("tslocations:off");
    try std.testing.expectEqual(Config{ .context = 5, .tscontext = true, .tslocations = false }, config);
    var out: std.Io.Writer.Allocating = .init(std.testing.allocator);
    defer out.deinit();
    try config.write(&out.writer);
    try std.testing.expectEqualStrings("context:5 tscontext:on tslocations:off layout:stacked", out.written());
    try std.testing.expectEqual(config, try (Config{}).parse(out.written()));
    try std.testing.expectEqual(config, try config.parse(" \n\t"));
    try std.testing.expectEqual(@as(u16, 2), (try config.parse("context:1 context:2")).context);
    try std.testing.expectEqual(Config.Layout.@"inline", (try config.parse("layout:inline")).layout);
}

test "LocationsConfig rejects invalid updates atomically" {
    const config: Config = .{ .context = 3, .tscontext = true };
    try std.testing.expectError(error.UnknownLocationSetting, config.parse("context:5 unknown:on"));
    try std.testing.expectError(error.ExpectedOnOrOff, config.parse("context:5 tscontext:true"));
    try std.testing.expectError(error.ExpectedKeyValue, config.parse("context"));
    try std.testing.expectError(error.InvalidLayout, config.parse("context:5 layout:sideways"));
    for ([_][]const u8{ "context:", "context:-1", "context:65536", "context:five" }) |input|
        try std.testing.expectError(error.InvalidContext, config.parse(input));
    try std.testing.expectEqual(@as(u16, 3), config.context);
}

// ---- the analysis cache ----

/// Owned source snapshots keep analysis valid across filesystem changes and
/// borrowed editor buffers. Entries are ordered from least to most recent.
pub const Cache = struct {
    /// A cache hit borrows its analysis; an entry too large to retain transfers
    /// ownership instead. Call deinit after consuming either result.
    pub const Hit = struct {
        analysis: syntax.SourceAnalysis,
        owned: bool = false,

        pub fn deinit(result: *Hit, gpa: std.mem.Allocator) void {
            if (result.owned) result.analysis.deinit(gpa);
            result.* = undefined;
        }
    };

    pub const max_bytes = 64 * 1024 * 1024;
    pub const max_entries = 64;

    const Entry = struct {
        path: []u8,
        source: []u8,
        analysis: syntax.SourceAnalysis,
        declarations_ready: bool,
        colors_ready: bool,

        fn size(entry: Entry) usize {
            return entry.path.len + entry.source.len + entry.analysis.colors.len +
                entry.analysis.declarations.len * @sizeOf(syntax.ContextDeclaration);
        }

        fn deinit(entry: *Entry, gpa: std.mem.Allocator) void {
            gpa.free(entry.path);
            gpa.free(entry.source);
            entry.analysis.deinit(gpa);
        }
    };

    entries: [max_entries]Entry = undefined,
    len: usize = 0,
    bytes: usize = 0,
    analyses: usize = 0,
    hits: usize = 0,

    pub fn deinit(cache: *Cache, gpa: std.mem.Allocator) void {
        for (cache.entries[0..cache.len]) |*entry| entry.deinit(gpa);
        cache.* = .{};
    }

    /// Borrowed slices remain valid until the next get or cache deinit; an
    /// owned result remains valid until Hit.deinit. All calls for this
    /// cache must use the same allocator. Unsupported languages
    /// are cached too, including their empty analysis arrays.
    pub fn get(cache: *Cache, gpa: std.mem.Allocator, path: []const u8, source: []const u8, want_declarations: bool, want_colors: bool) !Hit {
        return cache.getBounded(gpa, path, source, want_declarations, want_colors, max_bytes);
    }

    fn getBounded(cache: *Cache, gpa: std.mem.Allocator, path: []const u8, source: []const u8, want_declarations: bool, want_colors: bool, budget: usize) !Hit {
        if (source.len > budget or path.len > budget - source.len) return error.SourceTooLarge;
        var previous: ?usize = null;
        var declarations = want_declarations;
        var colors = want_colors;
        for (cache.entries[0..cache.len], 0..) |entry, index| {
            if (!std.mem.eql(u8, entry.path, path)) continue;
            previous = index;
            if (!std.mem.eql(u8, entry.source, source)) break;
            if ((!want_declarations or entry.declarations_ready) and (!want_colors or entry.colors_ready)) {
                // Moving the small ownership record keeps the underlying
                // allocations intact and avoids timestamp/overflow state.
                std.mem.copyForwards(Entry, cache.entries[index .. cache.len - 1], cache.entries[index + 1 .. cache.len]);
                cache.entries[cache.len - 1] = entry;
                cache.hits +|= 1;
                return .{ .analysis = entry.analysis };
            }
            declarations = declarations or entry.declarations_ready;
            colors = colors or entry.colors_ready;
            break;
        }
        // A supported full-source color map needs one byte per source byte.
        // Reject that known minimum before parsing, so the caller's uncached
        // path does not repeat an expensive analysis for oversized inputs.
        const input_bytes = path.len + source.len;
        if (colors and syntax.supportsPath(path) and source.len > budget - input_bytes) return error.SourceTooLarge;
        var analysis = try syntax.analyzeSource(gpa, path, source, declarations, colors);
        errdefer analysis.deinit(gpa);
        cache.analyses +|= 1;
        const analysis_bytes = analysis.colors.len + analysis.declarations.len * @sizeOf(syntax.ContextDeclaration);
        if (analysis_bytes > budget - input_bytes) return .{ .analysis = analysis, .owned = true };
        const owned_path = try gpa.dupe(u8, path);
        errdefer gpa.free(owned_path);
        const owned_source = try gpa.dupe(u8, source);
        errdefer gpa.free(owned_source);
        const next: Entry = .{
            .path = owned_path,
            .source = owned_source,
            .analysis = analysis,
            .declarations_ready = declarations,
            .colors_ready = colors,
        };
        // Commit only after every allocation succeeds. A failed refresh leaves
        // the previous cached snapshot usable by the next request.
        if (previous) |index| cache.remove(gpa, index);
        while (cache.len == max_entries or cache.bytes > budget - next.size()) cache.remove(gpa, 0);
        cache.entries[cache.len] = next;
        cache.len += 1;
        cache.bytes += next.size();
        return .{ .analysis = next.analysis };
    }

    fn remove(cache: *Cache, gpa: std.mem.Allocator, index: usize) void {
        cache.bytes -= cache.entries[index].size();
        cache.entries[index].deinit(gpa);
        std.mem.copyForwards(Entry, cache.entries[index .. cache.len - 1], cache.entries[index + 1 .. cache.len]);
        cache.len -= 1;
    }
};

test "locations cache validates exact source and path and upgrades analysis" {
    const gpa = std.testing.allocator;
    syntax.start(gpa);
    defer syntax.stop();
    var cache: Cache = .{};
    defer cache.deinit(gpa);
    const source = "const Thing = struct {\n    value: u32,\n};\n";
    _ = try cache.get(gpa, "a.zig", source, true, false);
    try std.testing.expectEqual(@as(usize, 1), cache.analyses);
    _ = try cache.get(gpa, "a.zig", source, true, false);
    try std.testing.expectEqual(@as(usize, 1), cache.analyses);
    try std.testing.expectEqual(@as(usize, 1), cache.hits);
    _ = try cache.get(gpa, "a.zig", source, false, true);
    try std.testing.expectEqual(@as(usize, 2), cache.analyses);
    try std.testing.expect(cache.entries[0].declarations_ready and cache.entries[0].colors_ready);
    _ = try cache.get(gpa, "a.zig", source, true, true);
    try std.testing.expectEqual(@as(usize, 2), cache.analyses);
    _ = try cache.get(gpa, "a.zig", "const Thing = struct {\n    other: u32,\n};\n", true, true);
    try std.testing.expectEqual(@as(usize, 3), cache.analyses);
    try std.testing.expectEqual(@as(usize, 1), cache.len);
    _ = try cache.get(gpa, "a.txt", source, true, true);
    try std.testing.expectEqual(@as(usize, 4), cache.analyses);
    try std.testing.expectEqual(@as(usize, 2), cache.len);
}

test "locations cache bounds memory and entries and evicts least recently used" {
    const gpa = std.testing.allocator;
    var cache: Cache = .{};
    defer cache.deinit(gpa);
    for (0..Cache.max_entries) |index| {
        var path: [32]u8 = undefined;
        _ = try cache.get(gpa, try std.fmt.bufPrint(&path, "{d}.unknown", .{index}), "source", false, false);
    }
    _ = try cache.get(gpa, "0.unknown", "source", false, false);
    _ = try cache.get(gpa, "new.unknown", "source", false, false);
    try std.testing.expectEqual(Cache.max_entries, cache.len);
    try std.testing.expectEqualStrings("2.unknown", cache.entries[0].path);
    const count = cache.analyses;
    _ = try cache.get(gpa, "0.unknown", "source", false, false);
    try std.testing.expectEqual(count, cache.analyses);
    cache.deinit(gpa);
    _ = try cache.getBounded(gpa, "a.unknown", "source", false, false, 40);
    _ = try cache.getBounded(gpa, "b.unknown", "source", false, false, 40);
    _ = try cache.getBounded(gpa, "c.unknown", "source", false, false, 40);
    try std.testing.expectEqual(@as(usize, 2), cache.len);
    try std.testing.expect(cache.bytes <= 40);
    try std.testing.expectEqualStrings("b.unknown", cache.entries[0].path);
    try std.testing.expectError(error.SourceTooLarge, cache.getBounded(gpa, "large.unknown", "x" ** 41, false, false, 40));
    try std.testing.expectEqual(@as(usize, 2), cache.len);
    if (syntax.supportsPath("large.zig")) {
        const before = cache.analyses;
        try std.testing.expectError(error.SourceTooLarge, cache.getBounded(gpa, "large.zig", "x" ** 25, true, true, 40));
        try std.testing.expectEqual(before, cache.analyses);
    }
    cache.deinit(gpa);
    try std.testing.expectEqual(@as(usize, 0), cache.bytes);
    try std.testing.expectEqual(@as(usize, 0), cache.len);
}

test "locations cache keeps its previous snapshot after allocation failure" {
    var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
    const gpa = failing.allocator();
    var cache: Cache = .{};
    defer cache.deinit(gpa);
    _ = try cache.get(gpa, "a.unknown", "old bytes", false, false);
    const retained = cache.bytes;
    failing.fail_index = failing.alloc_index;
    try std.testing.expectError(error.OutOfMemory, cache.get(gpa, "a.unknown", "new bytes", false, false));
    try std.testing.expectEqual(@as(usize, 1), cache.len);
    try std.testing.expectEqual(retained, cache.bytes);
    try std.testing.expectEqualStrings("old bytes", cache.entries[0].source);
    // This succeeds with allocations still disabled because the old entry
    // remains valid and the hit path moves ownership records only.
    _ = try cache.get(gpa, "a.unknown", "old bytes", false, false);
    try std.testing.expectEqual(@as(usize, 1), cache.hits);
}

test "locations cache transfers oversized completed analysis without reparsing" {
    if (!syntax.supportsPath("large.zig")) return error.SkipZigTest;
    const gpa = std.testing.allocator;
    syntax.start(gpa);
    defer syntax.stop();
    var cache: Cache = .{};
    defer cache.deinit(gpa);
    const source = "const Thing = struct {\n    value: u32,\n};\n";
    const budget = "large.zig".len + source.len;
    var result = try cache.getBounded(gpa, "large.zig", source, true, false, budget);
    defer result.deinit(gpa);
    try std.testing.expect(result.owned);
    try std.testing.expect(result.analysis.declarations.len > 0);
    try std.testing.expectEqual(@as(usize, 1), cache.analyses);
    try std.testing.expectEqual(@as(usize, 0), cache.len);
    try std.testing.expectEqual(@as(usize, 0), cache.bytes);
}