tiny.smg.query

1const std = @import("std");2const exports = @import("export.zig");3const graph_mod = @import("graph.zig");4const view = @import("view.zig");5const model = @import("model.zig");6const database = @import("storage/database/root.zig");7const traversal = @import("traversal.zig");89pub fn containmentPath(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8) ![]const []const u8 {10    var out: std.ArrayList([]const u8) = .empty;11    var current = name;12    while (true) {13        if (containsName(out.items, current)) break;14        try out.append(allocator, current);15        var parent: ?[]const u8 = null;16        const inc = try view.incoming(graph, allocator, current, model.RelType.contains);17        if (inc.len != 0) parent = inc[0].source;18        if (parent == null) break;19        current = parent.?;20    }21    std.mem.reverse([]const u8, out.items);22    return try out.toOwnedSlice(allocator);23}2425fn containsName(names: []const []const u8, target: []const u8) bool {26    for (names) |name| {27        if (std.mem.eql(u8, name, target)) return true;28    }29    return false;30}3132pub fn transitiveDeps(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, max_depth: ?usize) ![]const []const u8 {33    return try traverse(allocator, graph, name, .out, &.{ model.RelType.imports, model.RelType.depends_on }, max_depth);34}3536pub fn transitiveCallers(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, max_depth: ?usize) ![]const []const u8 {37    return try traverse(allocator, graph, name, .in, &.{model.RelType.calls}, max_depth);38}3940pub fn impact(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, max_depth: ?usize, coupling_only: bool) ![]const []const u8 {41    return try traversal.impact(allocator, .{ .graph = graph }, name, max_depth, coupling_only);42}4344pub fn impactFromReader(45    allocator: std.mem.Allocator,46    reader: *database.Reader,47    name: []const u8,48    max_depth: ?usize,49    coupling_only: bool,50) ![]const []const u8 {51    return try traversal.impact(52        allocator,53        .{ .stored = reader },54        name,55        max_depth,56        coupling_only,57    );58}5960pub fn ancestors(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, rel: []const u8, max_depth: ?usize) ![]const []const u8 {61    return try traverse(allocator, graph, name, .in, &.{rel}, max_depth);62}6364pub fn descendants(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, rel: []const u8, max_depth: ?usize) ![]const []const u8 {65    return try traverse(allocator, graph, name, .out, &.{rel}, max_depth);66}6768pub fn subgraph(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, depth: usize, coupling_only: bool) !graph_mod.Graph {69    var names = std.StringHashMap(usize).init(allocator);70    try names.put(name, 0);71    var frontier: std.ArrayList([]const u8) = .empty;72    try frontier.append(allocator, name);73    var current_depth: usize = 0;74    while (current_depth < depth and frontier.items.len != 0) : (current_depth += 1) {75        var next: std.ArrayList([]const u8) = .empty;76        for (frontier.items) |item| {77            for (graph.edges.items) |edge| {78                if (coupling_only and !exports.isCoupling(edge.rel)) continue;79                if (std.mem.eql(u8, edge.source, item) and !names.contains(edge.target)) {80                    try names.put(edge.target, current_depth + 1);81                    try next.append(allocator, edge.target);82                }83                if (std.mem.eql(u8, edge.target, item) and !names.contains(edge.source)) {84                    try names.put(edge.source, current_depth + 1);85                    try next.append(allocator, edge.source);86                }87            }88        }89        frontier = next;90    }91    var out = graph_mod.init(allocator);92    for (graph.nodes.items) |node| if (names.contains(node.name)) try graph_mod.addNode(&out, node);93    for (graph.edges.items) |edge| {94        if (names.contains(edge.source) and names.contains(edge.target) and (!coupling_only or exports.isCoupling(edge.rel))) try graph_mod.addEdge(&out, edge);95    }96    return out;97}9899pub fn shortestPath(allocator: std.mem.Allocator, graph: graph_mod.Graph, source: []const u8, target: []const u8) !?[]const []const u8 {100    var queue: std.ArrayList([]const u8) = .empty;101    var prev = std.StringHashMap([]const u8).init(allocator);102    try queue.append(allocator, source);103    try prev.put(source, "");104    var head: usize = 0;105    while (head < queue.items.len) : (head += 1) {106        const item = queue.items[head];107        if (std.mem.eql(u8, item, target)) break;108        for (graph.edges.items) |edge| {109            var neighbor: ?[]const u8 = null;110            if (std.mem.eql(u8, edge.source, item)) neighbor = edge.target;111            if (std.mem.eql(u8, edge.target, item)) neighbor = edge.source;112            if (neighbor) |next| {113                if (!prev.contains(next)) {114                    try prev.put(next, item);115                    try queue.append(allocator, next);116                }117            }118        }119    }120    if (!prev.contains(target)) return null;121    var path: std.ArrayList([]const u8) = .empty;122    var current = target;123    while (current.len != 0) {124        try path.append(allocator, current);125        current = prev.get(current) orelse "";126    }127    std.mem.reverse([]const u8, path.items);128    return try path.toOwnedSlice(allocator);129}130131const Direction = enum { in, out };132133fn traverse(allocator: std.mem.Allocator, graph: graph_mod.Graph, name: []const u8, direction: Direction, rels: ?[]const []const u8, max_depth: ?usize) ![]const []const u8 {134    var seen = std.StringHashMap(usize).init(allocator);135    var queue: std.ArrayList([]const u8) = .empty;136    try seen.put(name, 0);137    try queue.append(allocator, name);138    var head: usize = 0;139    while (head < queue.items.len) : (head += 1) {140        const item = queue.items[head];141        const depth = seen.get(item).?;142        if (max_depth != null and depth >= max_depth.?) continue;143        for (graph.edges.items) |edge| {144            if (rels != null and !relIn(edge.rel, rels.?)) continue;145            const next = switch (direction) {146                .out => if (std.mem.eql(u8, edge.source, item)) edge.target else continue,147                .in => if (std.mem.eql(u8, edge.target, item)) edge.source else continue,148            };149            if (!seen.contains(next)) {150                try seen.put(next, depth + 1);151                try queue.append(allocator, next);152            }153        }154    }155    var out: std.ArrayList([]const u8) = .empty;156    var it = seen.iterator();157    while (it.next()) |entry| {158        if (!std.mem.eql(u8, entry.key_ptr.*, name)) try out.append(allocator, entry.key_ptr.*);159    }160    std.mem.sort([]const u8, out.items, {}, cmpString);161    return try out.toOwnedSlice(allocator);162}163164fn relIn(rel: []const u8, rels: []const []const u8) bool {165    for (rels) |item| if (std.mem.eql(u8, rel, item)) return true;166    return false;167}168169fn cmpString(_: void, a: []const u8, b: []const u8) bool {170    return std.mem.lessThan(u8, a, b);171}172173test "query transitive deps callers and paths match python contract" {174    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);175    defer arena.deinit();176    const allocator = arena.allocator();177    var graph = graph_mod.init(allocator);178    for ([_][]const u8{ "app", "lib", "core" }) |name| try graph_mod.addNode(&graph, .{ .name = name, .type = model.NodeType.module });179    try graph_mod.addEdge(&graph, .{ .source = "app", .target = "lib", .rel = model.RelType.depends_on });180    try graph_mod.addEdge(&graph, .{ .source = "lib", .target = "core", .rel = model.RelType.depends_on });181    const deps = try transitiveDeps(allocator, graph, "app", null);182    try std.testing.expectEqualStrings("core", deps[0]);183    try std.testing.expectEqualStrings("lib", deps[1]);184    const depth = try transitiveDeps(allocator, graph, "app", 1);185    try std.testing.expectEqual(@as(usize, 1), depth.len);186    try std.testing.expectEqualStrings("lib", depth[0]);187    const anc = try ancestors(allocator, graph, "core", model.RelType.depends_on, null);188    try std.testing.expectEqualStrings("app", anc[0]);189    try std.testing.expectEqualStrings("lib", anc[1]);190    const desc = try descendants(allocator, graph, "app", model.RelType.depends_on, null);191    try std.testing.expectEqualStrings("core", desc[0]);192    try std.testing.expectEqualStrings("lib", desc[1]);193    const path = (try shortestPath(allocator, graph, "app", "core")).?;194    try std.testing.expectEqualStrings("app", path[0]);195    try std.testing.expectEqualStrings("core", path[2]);196}197198test "containment path terminates at a manual containment cycle" {199    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);200    defer arena.deinit();201    const allocator = arena.allocator();202    var graph = graph_mod.init(allocator);203    try graph_mod.addNode(204        &graph,205        .{ .name = "a", .type = model.NodeType.module },206    );207    try graph_mod.addNode(208        &graph,209        .{ .name = "b", .type = model.NodeType.module },210    );211    try graph_mod.addEdge(212        &graph,213        .{ .source = "a", .target = "b", .rel = model.RelType.contains },214    );215    try graph_mod.addEdge(216        &graph,217        .{ .source = "b", .target = "a", .rel = model.RelType.contains },218    );219    const path = try containmentPath(allocator, graph, "a");220    try std.testing.expectEqual(@as(usize, 2), path.len);221    try std.testing.expectEqualStrings("b", path[0]);222    try std.testing.expectEqualStrings("a", path[1]);223}

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