tiny.smg.traversal

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

1const std = @import("std");2const sql = @import("sql");34const smg = @import("root.zig");5const graph_mod = smg.graph;6const model = smg.model;7const storage = smg.storage;8const row_bytes_max = @import("context/model.zig").row_bytes_max;910pub const Direction = enum { incoming, outgoing };1112pub const Edge = struct {13    source: []const u8,14    rel: []const u8,15    target: []const u8,16};1718pub const Source = union(enum) {19    graph: graph_mod.Graph,20    stored: *storage.database.Reader,2122    pub fn node(self: Source, allocator: std.mem.Allocator, name: []const u8) !?model.Node {23        return switch (self) {24            .graph => |graph| if (graph_mod.getNode(&graph, name)) |found|25                found26            else27                null,28            .stored => |reader| blk: {29                const found = storage.context.loadFromReader(30                    allocator,31                    reader,32                    name,33                    false,34                ) catch |err| switch (err) {35                    error.NodeNotFound => break :blk null,36                    else => return err,37                };38                break :blk found.node;39            },40        };41    }4243    pub fn edges(44        self: Source,45        _: std.mem.Allocator,46        name: []const u8,47        direction: Direction,48    ) !EdgeIterator {49        return switch (self) {50            .graph => |graph| .{ .graph = .{51                .graph = graph,52                .indices = if (direction == .incoming)53                    graph_mod.incomingEdges(&graph, name)54                else55                    graph_mod.outgoingEdges(&graph, name),56            } },57            .stored => |reader| blk: {58                var handle = try reader.catalog.openRelation(59                    reader.allocator,60                    storage.rows.edges_relation,61                );62                errdefer handle.deinit();63                const index_name = if (direction == .incoming)64                    storage.rows.edge_target_index65                else66                    storage.rows.edge_source_index;67                const slot = indexSlot(&handle, index_name) orelse68                    return error.StorageIndexMissing;69                var scan: sql.index.Scan = undefined;70                try handle.relation.lookup(71                    &scan,72                    reader.allocator,73                    slot,74                    &.{.{ .text = name }},75                );76                break :blk .{ .stored = .{ .handle = handle, .scan = scan } };77            },78        };79    }8081    pub fn prefix(82        self: Source,83        allocator: std.mem.Allocator,84        namespace: []const u8,85    ) !NodeIterator {86        const prefix_name = try std.fmt.allocPrint(allocator, "{s}.", .{namespace});87        const end_name = try std.fmt.allocPrint(allocator, "{s}/", .{namespace});88        return switch (self) {89            .graph => |graph| .{ .graph = .{90                .graph = graph,91                .prefix_name = prefix_name,92            } },93            .stored => |reader| blk: {94                var handle = try reader.catalog.openRelation(95                    reader.allocator,96                    storage.rows.nodes_relation,97                );98                errdefer handle.deinit();99                const slot = indexSlot(&handle, storage.rows.node_name_index) orelse100                    return error.StorageIndexMissing;101                var scan: sql.index.Scan = undefined;102                try handle.relation.indexScan(103                    &scan,104                    reader.allocator,105                    slot,106                    &.{.{ .text = prefix_name }},107                    &.{.{ .text = end_name }},108                );109                break :blk .{ .stored = .{ .handle = handle, .scan = scan } };110            },111        };112    }113};114115pub const EdgeIterator = union(enum) {116    graph: struct {117        graph: graph_mod.Graph,118        indices: []const usize,119        cursor: usize = 0,120    },121    stored: struct {122        handle: sql.catalog.ReadRelationHandle,123        scan: sql.index.Scan,124        buffer: [row_bytes_max]u8 = undefined,125    },126127    pub fn deinit(self: *EdgeIterator) void {128        switch (self.*) {129            .graph => {},130            .stored => |*stored| {131                stored.scan.deinit();132                stored.handle.deinit();133            },134        }135    }136137    /// The returned strings remain valid until the next call to next.138    pub fn next(self: *EdgeIterator) !?Edge {139        return switch (self.*) {140            .graph => |*graph| blk: {141                if (graph.cursor == graph.indices.len) break :blk null;142                const edge = graph.graph.edges.items[graph.indices[graph.cursor]];143                graph.cursor += 1;144                break :blk .{145                    .source = edge.source,146                    .rel = edge.rel,147                    .target = edge.target,148                };149            },150            .stored => |*stored| blk: {151                const entry = (try stored.scan.next()) orelse break :blk null;152                const bytes = (try stored.handle.relation.getInto(153                    entry.rowid,154                    &stored.buffer,155                )) orelse return error.StorageIndexCorrupt;156                break :blk .{157                    .source = try storage.rows.edgeSourceView(bytes),158                    .rel = try storage.rows.edgeRelView(bytes),159                    .target = try storage.rows.edgeTargetView(bytes),160                };161            },162        };163    }164};165166pub const NodeIterator = union(enum) {167    graph: struct {168        graph: graph_mod.Graph,169        prefix_name: []const u8,170        cursor: usize = 0,171    },172    stored: struct {173        handle: sql.catalog.ReadRelationHandle,174        scan: sql.index.Scan,175        buffer: [row_bytes_max]u8 = undefined,176    },177178    pub fn deinit(self: *NodeIterator) void {179        switch (self.*) {180            .graph => {},181            .stored => |*stored| {182                stored.scan.deinit();183                stored.handle.deinit();184            },185        }186    }187188    pub fn next(self: *NodeIterator, allocator: std.mem.Allocator) !?model.Node {189        return switch (self.*) {190            .graph => |*graph| blk: {191                while (graph.cursor < graph.graph.nodes.items.len) {192                    const node = graph.graph.nodes.items[graph.cursor];193                    graph.cursor += 1;194                    if (std.mem.startsWith(u8, node.name, graph.prefix_name)) break :blk node;195                }196                break :blk null;197            },198            .stored => |*stored| blk: {199                const entry = (try stored.scan.next()) orelse break :blk null;200                const bytes = (try stored.handle.relation.getInto(201                    entry.rowid,202                    &stored.buffer,203                )) orelse return error.StorageIndexCorrupt;204                break :blk (try storage.rows.decodeNodeRow(205                    allocator,206                    entry.rowid,207                    bytes,208                )).node;209            },210        };211    }212};213214fn indexSlot(handle: *const sql.catalog.ReadRelationHandle, name: []const u8) ?usize {215    for (handle.index_definitions, 0..) |definition, slot| {216        if (std.mem.eql(u8, definition.name, name)) return slot;217    }218    return null;219}220221pub fn impact(222    allocator: std.mem.Allocator,223    source: Source,224    name: []const u8,225    max_depth: ?usize,226    coupling_only: bool,227) ![]const []const u8 {228    var seen = std.StringHashMap(usize).init(allocator);229    var queue: std.ArrayList([]const u8) = .empty;230    try seen.put(name, 0);231    try queue.append(allocator, name);232    var cursor: usize = 0;233    while (cursor < queue.items.len) : (cursor += 1) {234        const current = queue.items[cursor];235        const depth = seen.get(current).?;236        if (max_depth != null and depth >= max_depth.?) continue;237        var edges = try source.edges(allocator, current, .incoming);238        defer edges.deinit();239        while (try edges.next()) |edge| {240            if (coupling_only and !smg.exports.isCoupling(edge.rel)) continue;241            if (seen.contains(edge.source)) continue;242            const next = if (source == .stored)243                try allocator.dupe(u8, edge.source)244            else245                edge.source;246            try seen.put(next, depth + 1);247            try queue.append(allocator, next);248        }249    }250    var out: std.ArrayList([]const u8) = .empty;251    var iterator = seen.iterator();252    while (iterator.next()) |entry| {253        if (!std.mem.eql(u8, entry.key_ptr.*, name)) {254            try out.append(allocator, entry.key_ptr.*);255        }256    }257    std.mem.sort([]const u8, out.items, {}, stringLess);258    return try out.toOwnedSlice(allocator);259}260261fn stringLess(_: void, left: []const u8, right: []const u8) bool {262    return std.mem.lessThan(u8, left, right);263}