tiny.smg.storage.summary

1pub const summary = @import("summary.zig");

1const std = @import("std");2const pretty_json = @import("pretty").json;3const sql = @import("sql");4const sys = @import("sys");5const smg = @import("../root.zig");67const storage = smg.storage;8const database = storage.database;9const rows = storage.rows;10const store = storage.store;11const graph_mod = smg.graph;12const model = smg.model;1314const cache_name = "summary.json";15const temp_cache_name = "summary.json.tmp";16const schema = "tiny.smg.storage-summary/v2";1718pub const Count = struct {19    name: []const u8,20    count: usize,21    first: []const u8,22};2324pub const Graph = struct {25    nodes: usize,26    edges: usize,27    node_types: []const Count,28    rel_types: []const Count,29};3031pub fn load(allocator: std.mem.Allocator, root: []const u8, limits: smg.StorageLimits) !Graph {32    var opened = try store.openRead(allocator, root, limits);33    defer opened.close();34    return readCache(allocator, root, opened.reader.head, limits) catch35        try loadStreaming(allocator, &opened.reader);36}3738pub fn writeForHead(39    allocator: std.mem.Allocator,40    root: []const u8,41    opened: *database.Database,42    head: sql.Hash,43) !void {44    const checkout = try opened.connection.checkout();45    std.debug.assert(!checkout.working.dirty());46    std.debug.assert(sql.version.same(checkout.head, head));47    var graph_summary = try summarizeCatalog(48        allocator,49        &opened.connection.catalog,50        opened.allocator,51    );52    defer deinitStreamingGraph(allocator, &graph_summary);53    try writeGraph(allocator, root, head, graph_summary);54}5556pub fn writeGraphForHead(57    allocator: std.mem.Allocator,58    root: []const u8,59    graph: graph_mod.Graph,60    head: sql.Hash,61) !void {62    var graph_summary = try summarizeGraph(allocator, graph);63    defer deinitStreamingGraph(allocator, &graph_summary);64    try writeGraph(allocator, root, head, graph_summary);65}6667fn loadStreaming(allocator: std.mem.Allocator, reader: *database.Reader) !Graph {68    return try summarizeCatalog(allocator, &reader.catalog, reader.allocator);69}7071fn summarizeCatalog(72    allocator: std.mem.Allocator,73    catalog: anytype,74    scratch: std.mem.Allocator,75) !Graph {76    const nodes = try relationEntryCount(catalog, scratch, rows.nodes_relation);77    const edges = try relationEntryCount(catalog, scratch, rows.edges_relation);78    const node_types = try nodeCounts(allocator, catalog, scratch);79    errdefer deinitCountSlice(allocator, node_types);80    const rel_types = try edgeCounts(allocator, catalog, scratch);81    return .{82        .nodes = nodes,83        .edges = edges,84        .node_types = node_types,85        .rel_types = rel_types,86    };87}8889fn summarizeGraph(90    allocator: std.mem.Allocator,91    graph: graph_mod.Graph,92) !Graph {93    var node_types: std.ArrayList(Count) = .empty;94    errdefer deinitCounts(allocator, &node_types);95    for (graph.nodes.items) |node| {96        try record(allocator, &node_types, node.type, node.name);97    }98    std.mem.sort(Count, node_types.items, {}, firstLess);99    var rel_types: std.ArrayList(Count) = .empty;100    errdefer deinitCounts(allocator, &rel_types);101    var key: std.ArrayList(u8) = .empty;102    defer key.deinit(allocator);103    for (graph.edges.items) |edge| {104        key.clearRetainingCapacity();105        try edgeKey(&key, allocator, edge.source, edge.rel, edge.target);106        try record(allocator, &rel_types, edge.rel, key.items);107    }108    std.mem.sort(Count, rel_types.items, {}, firstLess);109    const owned_node_types = try node_types.toOwnedSlice(allocator);110    errdefer deinitCountSlice(allocator, owned_node_types);111    const owned_rel_types = try rel_types.toOwnedSlice(allocator);112    return .{113        .nodes = graph.nodes.items.len,114        .edges = graph.edges.items.len,115        .node_types = owned_node_types,116        .rel_types = owned_rel_types,117    };118}119120fn deinitStreamingGraph(allocator: std.mem.Allocator, graph: *Graph) void {121    deinitCountSlice(allocator, graph.node_types);122    deinitCountSlice(allocator, graph.rel_types);123    graph.* = undefined;124}125126fn deinitCountSlice(allocator: std.mem.Allocator, counts: []const Count) void {127    for (counts) |count| {128        allocator.free(count.name);129        allocator.free(count.first);130    }131    allocator.free(counts);132}133134fn relationEntryCount(catalog: anytype, scratch: std.mem.Allocator, relation: []const u8) !usize {135    var handle = try catalog.openRelation(scratch, relation);136    defer handle.deinit();137    return try handle.relation.table.count();138}139140fn nodeCounts(141    allocator: std.mem.Allocator,142    catalog: anytype,143    scratch: std.mem.Allocator,144) ![]Count {145    var handle = try catalog.openRelation(scratch, rows.nodes_relation);146    defer handle.deinit();147    var scan: sql.TableScan = undefined;148    try handle.relation.scan(&scan, scratch, null, null);149    defer scan.deinit();150    var counts: std.ArrayList(Count) = .empty;151    errdefer deinitCounts(allocator, &counts);152    while (try scan.next()) |entry| {153        try record(154            allocator,155            &counts,156            try rows.nodeTypeView(entry.bytes),157            try rows.nodeNameView(entry.bytes),158        );159    }160    std.mem.sort(Count, counts.items, {}, firstLess);161    return try counts.toOwnedSlice(allocator);162}163164fn edgeCounts(165    allocator: std.mem.Allocator,166    catalog: anytype,167    scratch: std.mem.Allocator,168) ![]Count {169    var handle = try catalog.openRelation(scratch, rows.edges_relation);170    defer handle.deinit();171    var scan: sql.TableScan = undefined;172    try handle.relation.scan(&scan, scratch, null, null);173    defer scan.deinit();174    var counts: std.ArrayList(Count) = .empty;175    errdefer deinitCounts(allocator, &counts);176    var key: std.ArrayList(u8) = .empty;177    defer key.deinit(allocator);178    while (try scan.next()) |entry| {179        const source = try rows.edgeSourceView(entry.bytes);180        const rel = try rows.edgeRelView(entry.bytes);181        const target = try rows.edgeTargetView(entry.bytes);182        key.clearRetainingCapacity();183        try edgeKey(&key, allocator, source, rel, target);184        try record(allocator, &counts, rel, key.items);185    }186    std.mem.sort(Count, counts.items, {}, firstLess);187    return try counts.toOwnedSlice(allocator);188}189190fn edgeKey(191    key: *std.ArrayList(u8),192    allocator: std.mem.Allocator,193    source: []const u8,194    rel: []const u8,195    target: []const u8,196) !void {197    try key.appendSlice(allocator, source);198    try key.append(allocator, 0);199    try key.appendSlice(allocator, rel);200    try key.append(allocator, 0);201    try key.appendSlice(allocator, target);202}203204fn record(205    allocator: std.mem.Allocator,206    counts: *std.ArrayList(Count),207    name: []const u8,208    first: []const u8,209) !void {210    for (counts.items) |*count| {211        if (!std.mem.eql(u8, count.name, name)) continue;212        count.count += 1;213        if (std.mem.lessThan(u8, first, count.first)) {214            const replacement = try allocator.dupe(u8, first);215            allocator.free(count.first);216            count.first = replacement;217        }218        return;219    }220    const owned_name = try allocator.dupe(u8, name);221    errdefer allocator.free(owned_name);222    const owned_first = try allocator.dupe(u8, first);223    errdefer allocator.free(owned_first);224    try counts.append(allocator, .{225        .name = owned_name,226        .count = 1,227        .first = owned_first,228    });229}230231fn deinitCounts(allocator: std.mem.Allocator, counts: *std.ArrayList(Count)) void {232    for (counts.items) |count| {233        allocator.free(count.name);234        allocator.free(count.first);235    }236    counts.deinit(allocator);237}238239fn firstLess(_: void, left: Count, right: Count) bool {240    return std.mem.lessThan(u8, left.first, right.first);241}242243const CachedCount = struct {244    name: []const u8,245    count: usize,246};247248const CachedGraph = struct {249    schema: []const u8,250    head: []const u8,251    nodes: usize,252    edges: usize,253    node_types: []const CachedCount,254    rel_types: []const CachedCount,255};256257fn readCache(258    allocator: std.mem.Allocator,259    root: []const u8,260    head: sql.Hash,261    limits: smg.StorageLimits,262) !Graph {263    const path = try cachePath(allocator, root, cache_name);264    defer allocator.free(path);265    const raw = try sys.fs.readFileAlloc(allocator, path, limits.max_summary_bytes);266    defer allocator.free(raw);267    var parsed = try std.json.parseFromSlice(CachedGraph, allocator, raw, .{});268    defer parsed.deinit();269    const cached = parsed.value;270    if (!std.mem.eql(u8, cached.schema, schema)) return error.InvalidSummarySchema;271    if (!cacheHeadMatches(cached.head, head)) return error.StaleSummary;272    const node_types = try cachedCounts(allocator, cached.node_types);273    errdefer deinitCountSlice(allocator, node_types);274    return .{275        .nodes = cached.nodes,276        .edges = cached.edges,277        .node_types = node_types,278        .rel_types = try cachedCounts(allocator, cached.rel_types),279    };280}281282fn cacheHeadMatches(cached: []const u8, head: sql.Hash) bool {283    const expected = std.fmt.bytesToHex(head, .lower);284    return std.mem.eql(u8, cached, expected[0..]);285}286287fn cachedCounts(allocator: std.mem.Allocator, cached: []const CachedCount) ![]Count {288    const counts = try allocator.alloc(Count, cached.len);289    var initialized: usize = 0;290    errdefer {291        for (counts[0..initialized]) |count| {292            allocator.free(count.name);293            allocator.free(count.first);294        }295        allocator.free(counts);296    }297    for (cached, counts) |source, *target| {298        const name = try allocator.dupe(u8, source.name);299        const first = allocator.dupe(u8, source.name) catch |err| {300            allocator.free(name);301            return err;302        };303        target.* = .{ .name = name, .count = source.count, .first = first };304        initialized += 1;305    }306    return counts;307}308309fn writeGraph(310    allocator: std.mem.Allocator,311    root: []const u8,312    head: sql.Hash,313    graph_summary: Graph,314) !void {315    var out: std.Io.Writer.Allocating = .init(allocator);316    defer out.deinit();317    var writer = pretty_json.Writer.init(&out.writer, .minified);318    try writer.beginObject();319    try writer.objectField("schema");320    try writer.write(schema);321    try writer.objectField("head");322    try writer.hexString(head[0..]);323    try writer.objectField("nodes");324    try writer.write(graph_summary.nodes);325    try writer.objectField("edges");326    try writer.write(graph_summary.edges);327    try writer.objectField("node_types");328    try writeCounts(&writer, graph_summary.node_types);329    try writer.objectField("rel_types");330    try writeCounts(&writer, graph_summary.rel_types);331    try writer.endObject();332    try out.writer.writeByte('\n');333    const temporary = try cachePath(allocator, root, temp_cache_name);334    defer allocator.free(temporary);335    const destination = try cachePath(allocator, root, cache_name);336    defer allocator.free(destination);337    try sys.fs.writeFile(temporary, out.written());338    try sys.fs.rename(temporary, destination);339}340341fn writeCounts(writer: *pretty_json.Writer, counts: []const Count) !void {342    try writer.beginArray();343    for (counts) |count| {344        try writer.beginObject();345        try writer.objectField("name");346        try writer.write(count.name);347        try writer.objectField("count");348        try writer.write(count.count);349        try writer.endObject();350    }351    try writer.endArray();352}353354fn cachePath(allocator: std.mem.Allocator, root: []const u8, name: []const u8) ![]const u8 {355    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name, name });356}357358fn checkRecordAllocationFailures(allocator: std.mem.Allocator) !void {359    var counts: std.ArrayList(Count) = .empty;360    defer deinitCounts(allocator, &counts);361    try record(allocator, &counts, "function", "z.last");362    try record(allocator, &counts, "function", "a.first");363    try record(allocator, &counts, "type", "m.middle");364}365366const TestingSummary = enum {367    write,368    omit,369};370371fn publishTestingGraph(372    allocator: std.mem.Allocator,373    root: []const u8,374    graph: graph_mod.Graph,375    summary: TestingSummary,376) !sql.Hash {377    var publisher = try store.beginRepairPublish(378        allocator,379        root,380        smg.default_limits.storage,381    );382    defer publisher.close();383    try storage.sync.replaceGraph(allocator, &publisher.store.database, graph);384    const head = (try publisher.store.database.connection.checkout()).head;385    if (summary == .write) {386        try writeGraphForHead(387            allocator,388            root,389            graph,390            head,391        );392    }393    try publisher.finish();394    return head;395}396397fn testingRoot(allocator: std.mem.Allocator, offset: i64) ![]const u8 {398    const now = @max(0, sys.time.realMilliTimestamp() + offset);399    return try std.fmt.allocPrint(allocator, "/tmp/smg-storage-summary-test-{x}", .{400        @as(u64, @intCast(now)),401    });402}403404test "summary counts clean allocation failure and replacement" {405    try std.testing.checkAllAllocationFailures(406        std.testing.allocator,407        checkRecordAllocationFailures,408        .{},409    );410    var counts: std.ArrayList(Count) = .empty;411    defer deinitCounts(std.testing.allocator, &counts);412    try record(std.testing.allocator, &counts, "function", "z.last");413    try record(std.testing.allocator, &counts, "function", "a.first");414    try std.testing.expectEqual(@as(usize, 1), counts.items.len);415    try std.testing.expectEqual(@as(usize, 2), counts.items[0].count);416    try std.testing.expectEqualStrings("a.first", counts.items[0].first);417}418419test "in-memory summary matches the stored graph catalog" {420    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);421    defer arena.deinit();422    const allocator = arena.allocator();423    var graph = graph_mod.init(allocator);424    try graph_mod.addNode(&graph, .{ .name = "b", .type = model.NodeType.function });425    try graph_mod.addNode(&graph, .{ .name = "a", .type = model.NodeType.module });426    try graph_mod.addEdge(&graph, .{427        .source = "a",428        .target = "b",429        .rel = model.RelType.contains,430    });431    var temporary = std.testing.tmpDir(.{});432    defer temporary.cleanup();433    var opened = try database.open(allocator, temporary.dir, smg.default_limits.storage);434    defer opened.deinit();435    try storage.sync.replaceGraph(allocator, &opened, graph);436    var direct = try summarizeGraph(allocator, graph);437    defer deinitStreamingGraph(allocator, &direct);438    var stored = try summarizeCatalog(439        allocator,440        &opened.connection.catalog,441        opened.allocator,442    );443    defer deinitStreamingGraph(allocator, &stored);444    try std.testing.expectEqual(direct.nodes, stored.nodes);445    try std.testing.expectEqual(direct.edges, stored.edges);446    try expectCountsEqual(direct.node_types, stored.node_types);447    try expectCountsEqual(direct.rel_types, stored.rel_types);448}449450fn expectCountsEqual(left: []const Count, right: []const Count) !void {451    try std.testing.expectEqual(left.len, right.len);452    for (left, right) |a, b| {453        try std.testing.expectEqualStrings(a.name, b.name);454        try std.testing.expectEqual(a.count, b.count);455        try std.testing.expectEqualStrings(a.first, b.first);456    }457}458459test "summary cache is bound to the reader head and stale reads do not rewrite" {460    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);461    defer arena.deinit();462    const allocator = arena.allocator();463    const root = try testingRoot(allocator, 0);464    defer sys.fs.deleteTree(root) catch {};465    try sys.fs.createDirPath(root);466467    var graph = graph_mod.init(allocator);468    defer graph_mod.deinit(&graph);469    try graph_mod.addNode(&graph, .{ .name = "a", .type = model.NodeType.module });470    const first_head = try publishTestingGraph(allocator, root, graph, .write);471    const path = try cachePath(allocator, root, cache_name);472    const cached = try sys.fs.readFileAlloc(allocator, path, 1024 * 1024);473    const head_text = std.fmt.bytesToHex(first_head, .lower);474    try std.testing.expect(std.mem.indexOf(u8, cached, head_text[0..]) != null);475    try std.testing.expectEqual(476        @as(usize, 1),477        (try load(allocator, root, smg.default_limits.storage)).nodes,478    );479    try writeGraph(allocator, root, first_head, .{480        .nodes = 99,481        .edges = 0,482        .node_types = &.{},483        .rel_types = &.{},484    });485    try std.testing.expectEqual(486        @as(usize, 99),487        (try load(allocator, root, smg.default_limits.storage)).nodes,488    );489    const exact_head_cache = try sys.fs.readFileAlloc(allocator, path, 1024 * 1024);490491    try graph_mod.addNode(&graph, .{ .name = "b", .type = model.NodeType.function });492    const second_head = try publishTestingGraph(allocator, root, graph, .omit);493    try std.testing.expect(!sql.version.same(first_head, second_head));494    try std.testing.expectEqual(495        @as(usize, 2),496        (try load(allocator, root, smg.default_limits.storage)).nodes,497    );498    const unchanged = try sys.fs.readFileAlloc(allocator, path, 1024 * 1024);499    try std.testing.expectEqualSlices(u8, exact_head_cache, unchanged);500}501502test "summary missing and invalid caches stream without publishing" {503    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);504    defer arena.deinit();505    const allocator = arena.allocator();506    const root = try testingRoot(allocator, 1);507    defer sys.fs.deleteTree(root) catch {};508    try sys.fs.createDirPath(root);509510    var graph = graph_mod.init(allocator);511    defer graph_mod.deinit(&graph);512    try graph_mod.addNode(&graph, .{ .name = "only", .type = model.NodeType.module });513    _ = try publishTestingGraph(allocator, root, graph, .omit);514    const path = try cachePath(allocator, root, cache_name);515    try std.testing.expect(!sys.fs.exists(path));516    try std.testing.expectEqual(517        @as(usize, 1),518        (try load(allocator, root, smg.default_limits.storage)).nodes,519    );520    try std.testing.expect(!sys.fs.exists(path));521522    try sys.fs.writeFile(path, "invalid summary");523    try std.testing.expectEqual(524        @as(usize, 1),525        (try load(allocator, root, smg.default_limits.storage)).nodes,526    );527    const unchanged = try sys.fs.readFileAlloc(allocator, path, 1024);528    try std.testing.expectEqualStrings("invalid summary", unchanged);529}