tiny.smg.context.query

1const std = @import("std");2const sql = @import("sql");3const repo = @import("repo");4const smg = @import("../root.zig");5const context = @import("root.zig");6const model = context.model;7const rows = smg.storage.rows;89const Visit = struct { name: []const u8, depth: u8 };1011pub fn run(builder: *model.Builder, reader: *smg.storage.database.Reader) !void {12    std.debug.assert(builder.target_count != 0);13    std.debug.assert(builder.target_count <= model.targets_max);14    var nodes = try reader.catalog.openRelation(reader.allocator, rows.nodes_relation);15    defer nodes.deinit();16    var edges = try reader.catalog.openRelation(reader.allocator, rows.edges_relation);17    defer edges.deinit();18    for (builder.targets[0..builder.target_count]) |*target| {19        if (!builder.active()) break;20        if (unsupported(target.input)) {21            target.state = .unsupported;22            builder.report.coverage.unsupported += 1;23            continue;24        }25        const node = try resolve(builder, &nodes, target) orelse continue;26        target.state = .resolved;27        target.name = node.name;28        builder.report.coverage.resolved += 1;29        _ = try append(builder, node, target.input, .target, "target");30        try neighborhood(builder, &nodes, &edges, target.input, node.name);31    }32    std.mem.sort(33        model.Entry,34        builder.entries[0..builder.entry_count],35        builder.targets[0..builder.target_count],36        entryLess,37    );38}3940fn resolve(builder: *model.Builder, nodes: anytype, target: *model.Target) !?smg.Node {41    std.debug.assert(target.state == .unqueried);42    std.debug.assert(target.input.len != 0);43    if (try exact(builder, nodes, target.input)) |node| return node;44    const translated = try translatedPath(builder, target.input);45    if (translated) |name| if (try exact(builder, nodes, name)) |node| return node;46    const query = translated orelse target.input;47    const slot = indexSlot(nodes, rows.node_name_index) orelse return error.StorageIndexMissing;48    var scan: sql.IndexScan = undefined;49    try nodes.relation.indexScan(&scan, builder.allocator, slot, null, null);50    defer scan.deinit();51    var matches: [model.targets_max][]const u8 = undefined;52    var count: usize = 0;53    var complete = false;54    while (builder.row()) {55        const row = (try scan.next()) orelse {56            complete = true;57            break;58        };59        builder.report.work.visited_index_rows += 1;60        var values: [1]sql.row.Value = undefined;61        var key_buffer: [sql.page.size]u8 = undefined;62        const name = try smg.storage.names.indexedName(&values, &key_buffer, row.key);63        if (!smg.name.matchesSuffix(name, query)) continue;64        if (contains(matches[0..count], name)) continue;65        if (count == matches.len) {66            builder.exhausted();67            break;68        }69        matches[count] = try builder.allocator.dupe(u8, name);70        count += 1;71    }72    target.candidates = try builder.allocator.dupe([]const u8, matches[0..count]);73    if (count > 1) {74        target.state = .ambiguous;75        builder.report.coverage.ambiguous += 1;76    } else if (complete and count == 1) {77        return exact(builder, nodes, matches[0]);78    } else if (complete) {79        target.state = .missing;80        builder.report.coverage.missing += 1;81    }82    return null;83}8485fn exact(builder: *model.Builder, nodes: anytype, name: []const u8) !?smg.Node {86    std.debug.assert(name.len != 0);87    std.debug.assert(builder.report.work.index_steps <= builder.options.limits.rows);88    if (!builder.row()) return null;89    const slot = indexSlot(nodes, rows.node_name_index) orelse return error.StorageIndexMissing;90    var lookup: sql.IndexScan = undefined;91    try nodes.relation.lookup(&lookup, builder.allocator, slot, &.{.{ .text = name }});92    defer lookup.deinit();93    const found = (try lookup.next()) orelse return null;94    builder.report.work.visited_index_rows += 1;95    var buffer: [model.row_bytes_max]u8 = undefined;96    const bytes = (try nodes.relation.getInto(found.rowid, &buffer)) orelse97        return error.StorageIndexCorrupt;98    const node = (try rows.decodeNodeRow(builder.allocator, found.rowid, bytes)).node;99    builder.report.work.loaded_nodes += 1;100    try validNode(node);101    return node;102}103104fn neighborhood(105    builder: *model.Builder,106    nodes: anytype,107    edges: anytype,108    target: []const u8,109    name: []const u8,110) !void {111    std.debug.assert(name.len != 0);112    std.debug.assert(builder.options.limits.depth <= 2);113    var queue: [model.entries_max]Visit = undefined;114    queue[0] = .{ .name = name, .depth = 0 };115    var count: usize = 1;116    var cursor: usize = 0;117    while (cursor < count and builder.active()) : (cursor += 1) {118        const visit = queue[cursor];119        builder.report.work.depth_reached = @max(builder.report.work.depth_reached, visit.depth);120        if (visit.depth == builder.options.limits.depth) {121            builder.report.omissions.depth = true;122            builder.exhausted();123            continue;124        }125        try adjacency(builder, nodes, edges, target, visit, true, &queue, &count);126        try adjacency(builder, nodes, edges, target, visit, false, &queue, &count);127    }128}129130fn adjacency(131    builder: *model.Builder,132    nodes: anytype,133    edges: anytype,134    target: []const u8,135    visit: Visit,136    incoming: bool,137    queue: []Visit,138    count: *usize,139) !void {140    std.debug.assert(visit.depth < builder.options.limits.depth);141    std.debug.assert(count.* != 0);142    std.debug.assert(count.* <= queue.len);143    const index = if (incoming) rows.edge_target_index else rows.edge_source_index;144    const slot = indexSlot(edges, index) orelse return error.StorageIndexMissing;145    var lookup: sql.IndexScan = undefined;146    try edges.relation.lookup(&lookup, builder.allocator, slot, &.{.{ .text = visit.name }});147    defer lookup.deinit();148    while (builder.row()) {149        const found = (try lookup.next()) orelse break;150        builder.report.work.visited_index_rows += 1;151        builder.report.work.visited_edges += 1;152        var buffer: [model.row_bytes_max]u8 = undefined;153        const bytes = (try edges.relation.getInto(found.rowid, &buffer)) orelse154            return error.StorageIndexCorrupt;155        const edge = (try rows.decodeEdgeRow(builder.allocator, found.rowid, bytes)).edge;156        try validEdge(edge);157        const name = if (incoming) edge.source else edge.target;158        if (std.mem.eql(u8, name, queue[0].name)) continue;159        const node = try exact(builder, nodes, name) orelse continue;160        const section = classify(node, edge, incoming, visit.depth);161        if (!try append(builder, node, target, section, edge.rel)) continue;162        enqueue(builder, queue, count, .{ .name = node.name, .depth = visit.depth + 1 });163    }164}165166fn classify(node: smg.Node, edge: smg.Edge, incoming: bool, depth: u8) model.Section {167    std.debug.assert(node.name.len != 0);168    std.debug.assert(depth < 2);169    if (smg.api.isTestDeclaration(node)) return .tests;170    if (incoming and std.mem.eql(u8, edge.rel, smg.model.RelType.contains)) return .owner;171    if (incoming) return if (depth == 0) .usages else .impact;172    return .dependencies;173}174175fn append(176    builder: *model.Builder,177    node: smg.Node,178    target: []const u8,179    section: model.Section,180    relation: []const u8,181) !bool {182    std.debug.assert(node.name.len != 0);183    std.debug.assert(target.len != 0);184    var entry = model.Entry{185        .target = target,186        .section = section,187        .relation = relation,188        .name = node.name,189        .path = node.file,190        .line = node.line,191    };192    if (!builder.add(entry)) return false;193    try context.source.inspect(builder, &entry, node);194    builder.entries[builder.entry_count - 1] = entry;195    return true;196}197198fn enqueue(builder: *model.Builder, queue: []Visit, count: *usize, visit: Visit) void {199    std.debug.assert(count.* <= queue.len);200    std.debug.assert(visit.depth <= builder.options.limits.depth);201    for (queue[0..count.*]) |existing| if (std.mem.eql(u8, existing.name, visit.name)) return;202    if (count.* == queue.len) {203        builder.exhausted();204        return;205    }206    queue[count.*] = visit;207    count.* += 1;208}209210fn indexSlot(handle: anytype, name: []const u8) ?usize {211    for (handle.index_definitions, 0..) |definition, slot| {212        if (std.mem.eql(u8, definition.name, name)) return slot;213    }214    return null;215}216217fn contains(names: []const []const u8, name: []const u8) bool {218    std.debug.assert(names.len <= model.targets_max);219    for (names) |entry| if (std.mem.eql(u8, entry, name)) return true;220    return false;221}222223fn translatedPath(builder: *model.Builder, input: []const u8) !?[]const u8 {224    const path = std.mem.indexOfScalar(u8, input, '/') != null or225        smg.scan.scan_files.supported(input);226    if (!path) return null;227    const relative = try repo.work.resolvedPathAlloc(builder.allocator, builder.root, input);228    const prefixed = try std.fmt.allocPrint(builder.allocator, "./{s}", .{relative});229    return smg.name.dottedFromPath(builder.allocator, prefixed);230}231232fn unsupported(input: []const u8) bool {233    if (std.mem.indexOfScalar(u8, input, '/') == null) return false;234    if (std.fs.path.extension(input).len == 0) return false;235    return !smg.scan.scan_files.supported(input);236}237238fn validEdge(edge: smg.Edge) !void {239    for ([_][]const u8{ edge.source, edge.rel, edge.target }) |value| {240        if (value.len > 4096 or !std.unicode.utf8ValidateSlice(value)) {241            return error.InvalidInspectionEdge;242        }243    }244}245246fn validNode(node: smg.Node) !void {247    if (node.name.len > 4096 or !std.unicode.utf8ValidateSlice(node.name)) {248        return error.InvalidInspectionNode;249    }250    if (node.file) |path| if (path.len > 4096 or !std.unicode.utf8ValidateSlice(path)) {251        return error.InvalidInspectionNode;252    };253}254255fn entryLess(targets: []model.Target, left: model.Entry, right: model.Entry) bool {256    std.debug.assert(targets.len != 0);257    std.debug.assert(targets.len <= model.targets_max);258    if (!std.mem.eql(u8, left.target, right.target)) {259        for (targets) |target| {260            if (std.mem.eql(u8, target.input, left.target)) return true;261            if (std.mem.eql(u8, target.input, right.target)) return false;262        }263        unreachable;264    }265    if (left.section != right.section) {266        return @backingInt(left.section) < @backingInt(right.section);267    }268    const name = std.mem.order(u8, left.name, right.name);269    if (name != .eq) return name == .lt;270    return std.mem.lessThan(u8, left.relation, right.relation);271}

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