tiny.smg.search

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

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const sql = @import("sql");4const sys = @import("sys");5const graph_mod = @import("graph.zig");6const limits_mod = @import("limits/root.zig");7const model = @import("model.zig");8const storage = @import("storage/root.zig");910const fs_io = std.Options.debug_io;1112pub const Error = error{13    InvalidSearchQuery,14    SearchCacheRepairRequired,15};1617const db_name = "search.sql";18const wal_name = "search.sql.wal";19const temp_db_name = "search.sql.tmp";20const temp_wal_name = "search.sql.tmp.wal";21const cache_schema: u64 = 3;22const search_field_names = [_][]const u8{ "name_tokens", "docstring" };2324pub const SyncKind = enum {25    matched,26    incremental,27    rebuilt,28};2930pub const Hit = struct {31    rank: i64,32    name: []const u8,33    kind: []const u8,34    file: ?[]const u8,35    line_start: ?i64,36    line_end: ?i64,37    docstring: ?[]const u8,38    score: f64,39};4041pub const Result = struct {42    hits: []const Hit,43    total: i64,44};4546pub const DocumentPlan = struct {47    pub const Limits = struct {48        documents: usize,49        text_bytes: usize,50    };5152    pub const Capacity = struct {53        documents: usize,54        text_bytes: usize,55        bytes: usize,5657        pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {58            const document_bytes = try alloc_phase.capacity.mul(59                usize,60                limits.documents,61                @sizeOf(sql.SearchDocument),62            );63            return .{64                .documents = limits.documents,65                .text_bytes = limits.text_bytes,66                .bytes = try alloc_phase.capacity.add(67                    usize,68                    document_bytes,69                    limits.text_bytes,70                ),71            };72        }73    };7475    pub const InitError = std.mem.Allocator.Error || error{CapacityOverflow};7677    pub const claim: alloc_phase.capacity.Declaration = .{78        .source = .{79            .id = "smg.search_document_plan",80            .kind = .phase_static,81            .limit_source = .caller,82            .storage = .{83                .covered = &.{84                    .{85                        .id = "one_search_document_record_per_persisted_node_row",86                        .lifetime = .steady,87                        .detail = "one search document record per persisted node row",88                    },89                    .{90                        .id = "one_contiguous_bounded_search_text_region_admitted_bf91a1d01c82",91                        .lifetime = .steady,92                        .detail = "one contiguous bounded search-text region admitted from exact row views",93                    },94                },95                .excluded = &.{96                    "persisted graph relation scans and borrowed row bytes",97                    "graph database pager catalog and operating-system read storage",98                    "SQL search postings keys lengths write staging WAL and cache database",99                },100            },101            .capacity = .{102                .inputs = &.{103                    alloc_phase.capacity.bindInput(Limits, "documents", "documents"),104                    alloc_phase.capacity.bindInput(Limits, "text_bytes", "text_bytes"),105                },106                .type_selectors = &.{107                    alloc_phase.capacity.bindType(sql.SearchDocument, "search_document"),108                },109                .nodes = &.{110                    .{ .input = 0 },111                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },112                    .{ .input = 1 },113                    .{ .add = .{ .left = 1, .right = 2 } },114                },115                .assertions = &.{.{116                    .scope = .closure_total,117                    .measure = .retained,118                    .relation = .upper_bound,119                    .expression = 3,120                }},121            },122            .overload = .{123                .kind = .reject_before_seal,124                .detail = "checked record and rendered-text arithmetic plus exact acquisitions reject overflow or OOM before the second relation pass",125            },126            .risks = .{127                .transitive = .{128                    .status = .open,129                    .detail = "identifier rendering and row views are sealed in the witness but lack a transitive allocation-closure certificate",130                },131                .foreign = .{132                    .status = .excluded,133                    .detail = "graph and search database effects occur outside the plan-owned slices",134                },135            },136            .obligations = &.{137                .{ .key = "smg_search_document_plan_capacity_capacity_model", .role = .capacity_model },138                .{ .key = "smg_search_document_plan_capacity_overload", .role = .overload },139                .{ .key = "smg_search_document_plan_oom", .role = .overload },140                .{ .key = "smg_search_document_plan_sealed", .role = .transitive_risk },141                .{ .key = "smg_search_document_plan_integration", .role = .foreign_risk },142            },143        },144        .bindings = .{145            .owner = @This(),146            .seal = .{147                .family = alloc_phase.capacity.selector(@This().activate),148                .premise = .{149                    .class = .checked_semantic_fact,150                    .authority = .checker,151                },152            },153            .teardown = .{154                .family = alloc_phase.capacity.selector(@This().deinit),155                .premise = .{156                    .class = .checked_semantic_fact,157                    .authority = .checker,158                },159            },160        },161    };162163    phase: alloc_phase.capacity.Phase,164    capacity: Capacity,165    documents: []sql.SearchDocument,166    text: []u8,167    documents_filled: usize,168    text_filled: usize,169170    pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!DocumentPlan {171        const capacity = try Capacity.derive(limits);172        const documents = try documentAllocSlice(sql.SearchDocument, allocator, capacity.documents);173        errdefer documentFreeSlice(sql.SearchDocument, allocator, documents);174        return .{175            .phase = .initialization,176            .capacity = capacity,177            .documents = documents,178            .text = try documentAllocSlice(u8, allocator, capacity.text_bytes),179            .documents_filled = 0,180            .text_filled = 0,181        };182    }183184    pub fn append(self: *DocumentPlan, rowid: i64, name: []const u8, docstring: ?[]const u8) error{CapacityOverflow}!void {185        std.debug.assert(self.phase == .initialization);186        if (self.documents_filled == self.documents.len) return error.CapacityOverflow;187        const text_bytes = try nodeSearchTextBytes(name, docstring);188        const text_end = std.math.add(usize, self.text_filled, text_bytes) catch return error.CapacityOverflow;189        if (text_end > self.text.len) return error.CapacityOverflow;190        const destination = self.text[self.text_filled..text_end];191        fillNodeSearchText(destination, name, docstring);192        self.documents[self.documents_filled] = .{ .rowid = rowid, .text = destination };193        self.documents_filled += 1;194        self.text_filled = text_end;195    }196197    pub fn activate(self: *DocumentPlan) void {198        std.debug.assert(self.phase == .initialization);199        std.debug.assert(self.documents_filled == self.documents.len);200        std.debug.assert(self.text_filled == self.text.len);201        self.phase = .steady;202    }203204    pub fn deinit(self: *DocumentPlan, allocator: std.mem.Allocator) void {205        std.debug.assert(self.phase != .teardown);206        self.phase = .teardown;207        documentFreeSlice(sql.SearchDocument, allocator, self.documents);208        documentFreeSlice(u8, allocator, self.text);209        self.* = undefined;210    }211};212213comptime {214    alloc_phase.capacity.requireAllocatorExactOwnerShape(DocumentPlan);215}216217const StoredDocuments = struct {218    plan: DocumentPlan,219    head: sql.Hash,220};221222const DocumentChanges = struct {223    added: std.ArrayList(sql.SearchDocument) = .empty,224    updated: std.ArrayList(sql.SearchDocument) = .empty,225226    fn deinit(self: *DocumentChanges, allocator: std.mem.Allocator) void {227        self.added.deinit(allocator);228        self.updated.deinit(allocator);229        self.* = undefined;230    }231};232233fn changedDocuments(234    allocator: std.mem.Allocator,235    node_puts: []const storage.rows.NodePut,236) !DocumentPlan {237    var text_bytes: usize = 0;238    for (node_puts) |put| {239        text_bytes = std.math.add(240            usize,241            text_bytes,242            try nodeSearchTextBytes(put.node.name, put.node.docstring),243        ) catch return error.CapacityOverflow;244    }245    var plan = try DocumentPlan.init(allocator, .{246        .documents = node_puts.len,247        .text_bytes = text_bytes,248    });249    errdefer plan.deinit(allocator);250    for (node_puts) |put| {251        try plan.append(put.rowid, put.node.name, put.node.docstring);252    }253    plan.activate();254    return plan;255}256257pub fn rebuildStored(258    allocator: std.mem.Allocator,259    root: []const u8,260    limits: limits_mod.Limits,261) !usize {262    var opened = try storage.store.open(allocator, root, limits.storage);263    defer opened.close();264    const head = (try opened.database.connection.checkout()).head;265    return try rebuildStoredFromDatabase(266        allocator,267        root,268        &opened.database,269        head,270        limits.search,271    );272}273274pub fn syncStoredFromDatabase(275    allocator: std.mem.Allocator,276    root: []const u8,277    database: *storage.database.Database,278    previous_head: sql.Hash,279    head: sql.Hash,280    node_puts: []const storage.rows.NodePut,281    node_deletes: []const i64,282    limits: limits_mod.Search,283) !SyncKind {284    if (node_puts.len == 0 and node_deletes.len == 0 and285        try cacheMatchesSource(allocator, root, sourceForHead(head)))286    {287        if (!(try storage.names.matchesHead(allocator, root, head))) {288            try storage.names.writeForHead(allocator, root, database, head);289        }290        return .matched;291    }292    if (try updateStoredFromChanges(293        allocator,294        root,295        previous_head,296        head,297        node_puts,298        node_deletes,299        limits,300    )) {301        try storage.names.writeForHead(allocator, root, database, head);302        return .incremental;303    }304    _ = try rebuildStoredFromDatabase(allocator, root, database, head, limits);305    return .rebuilt;306}307308fn updateStoredFromChanges(309    allocator: std.mem.Allocator,310    root: []const u8,311    previous_head: sql.Hash,312    head: sql.Hash,313    node_puts: []const storage.rows.NodePut,314    node_deletes: []const i64,315    limits: limits_mod.Search,316) !bool {317    if (node_deletes.len > limits.incremental_delete_count) return false;318    var documents = try changedDocuments(allocator, node_puts);319    defer documents.deinit(allocator);320    if (documents.documents.len > limits.rebuild_batch_documents or321        documents.text.len > limits.rebuild_batch_text_bytes)322    {323        return false;324    }325    var workspace = try cacheWorkspace(326        allocator,327        sql.file.default_max_wal_bytes,328    );329    defer workspace.deallocate(allocator);330    var cache_database = openCache(allocator, &workspace, root) catch |err| {331        if (err == error.FileNotFound) return false;332        if (searchCacheReadFailure(err)) return false;333        return err;334    };335    defer cache_database.deinit();336    var index = sql.Search.open(&cache_database, .{337        .index_prefixes = false,338        .field_names = &search_field_names,339    }) catch |err| {340        if (searchCacheReadFailure(err)) return false;341        return err;342    };343    const source_matches = index.sourceMatches(344        allocator,345        sourceForHead(previous_head),346    ) catch |err| {347        if (incrementalRepairRequired(err)) return false;348        return err;349    };350    if (!source_matches) return false;351    var changes = (try classifyChangedDocuments(352        allocator,353        &index,354        documents.documents,355    )) orelse return false;356    defer changes.deinit(allocator);357    if (!(try applyDocumentChanges(358        allocator,359        &index,360        changes,361        node_deletes,362    ))) return false;363    return try advanceIncrementalCache(364        allocator,365        &cache_database,366        &index,367        previous_head,368        head,369    );370}371372fn classifyChangedDocuments(373    allocator: std.mem.Allocator,374    index: *sql.Search,375    documents: []const sql.SearchDocument,376) !?DocumentChanges {377    var changes: DocumentChanges = .{};378    errdefer changes.deinit(allocator);379    try changes.added.ensureTotalCapacityPrecise(allocator, documents.len);380    try changes.updated.ensureTotalCapacityPrecise(allocator, documents.len);381    for (documents) |document| {382        const previous = index.getText(allocator, document.rowid) catch |err| {383            if (incrementalRepairRequired(err)) {384                changes.deinit(allocator);385                return null;386            }387            return err;388        };389        if (previous) |text| {390            defer allocator.free(text);391            if (!std.mem.eql(u8, text, document.text)) {392                changes.updated.appendAssumeCapacity(document);393            }394        } else {395            changes.added.appendAssumeCapacity(document);396        }397    }398    return changes;399}400401fn applyDocumentChanges(402    allocator: std.mem.Allocator,403    index: *sql.Search,404    changes: DocumentChanges,405    node_deletes: []const i64,406) !bool {407    for (node_deletes) |rowid| {408        _ = index.delete(allocator, rowid, .{ .durability = .buffered }) catch |err| {409            if (incrementalRepairRequired(err)) return false;410            return err;411        };412    }413    if (changes.added.items.len != 0) {414        _ = index.loadAllNew(415            allocator,416            changes.added.items,417            .{ .durability = .buffered },418        ) catch |err| {419            if (incrementalRepairRequired(err)) return false;420            return err;421        };422    }423    if (changes.updated.items.len != 0) {424        _ = index.putAll(425            allocator,426            changes.updated.items,427            .{ .durability = .buffered },428        ) catch |err| {429            if (incrementalRepairRequired(err)) return false;430            return err;431        };432    }433    return true;434}435436fn advanceIncrementalCache(437    allocator: std.mem.Allocator,438    cache_database: *sql.FileDatabase,439    index: *sql.Search,440    previous_head: sql.Hash,441    head: sql.Hash,442) !bool {443    const advanced = index.advanceSource(444        allocator,445        sourceForHead(previous_head),446        sourceForHead(head),447        .{ .durability = .buffered },448    ) catch |err| {449        if (incrementalRepairRequired(err)) return false;450        return err;451    };452    if (advanced == null) return false;453    try cache_database.syncWal();454    _ = try cache_database.checkpoint(.{ .restart_header = cacheHeader(2) });455    return true;456}457458fn incrementalRepairRequired(err: anyerror) bool {459    if (searchCacheReadFailure(err)) return true;460    return switch (err) {461        error.KeyNotFound,462        error.SearchIndexRebuildRequired,463        error.TransactionTooLarge,464        => true,465        else => false,466    };467}468469fn rebuildStoredFromDatabase(470    allocator: std.mem.Allocator,471    root: []const u8,472    database: *storage.database.Database,473    head: sql.Hash,474    limits: limits_mod.Search,475) !usize {476    var stored = try storedDocuments(allocator, database, head);477    defer stored.plan.deinit(allocator);478    try rebuildDocuments(479        allocator,480        root,481        stored.plan.documents,482        sourceForHead(stored.head),483        limits,484    );485    try storage.names.writeForHead(allocator, root, database, stored.head);486    return stored.plan.documents.len;487}488489fn storedDocuments(allocator: std.mem.Allocator, database: *storage.database.Database, head: sql.Hash) !StoredDocuments {490    const limits = try storedDocumentLimits(allocator, database);491    var plan = try DocumentPlan.init(allocator, limits);492    errdefer plan.deinit(allocator);493    try fillStoredDocuments(allocator, database, &plan);494    plan.activate();495    return .{496        .plan = plan,497        .head = head,498    };499}500501fn storedDocumentLimits(allocator: std.mem.Allocator, database: *storage.database.Database) !DocumentPlan.Limits {502    var handle = database.connection.catalog.openRelation(allocator, storage.rows.nodes_relation) catch |err| switch (err) {503        error.RelationNotFound => return .{ .documents = 0, .text_bytes = 0 },504        else => return err,505    };506    defer handle.deinit();507    var scan: sql.TableScan = undefined;508    try handle.relation.scan(&scan, allocator, null, null);509    defer scan.deinit();510    var documents: usize = 0;511    var text_bytes: usize = 0;512    while (try scan.next()) |entry| {513        const name = try storage.rows.nodeNameView(entry.bytes);514        const docstring = try storage.rows.nodeDocstringView(entry.bytes);515        text_bytes = std.math.add(usize, text_bytes, try nodeSearchTextBytes(name, docstring)) catch return error.CapacityOverflow;516        documents = std.math.add(usize, documents, 1) catch return error.CapacityOverflow;517    }518    const limits = DocumentPlan.Limits{519        .documents = documents,520        .text_bytes = text_bytes,521    };522    _ = try DocumentPlan.Capacity.derive(limits);523    return limits;524}525526fn fillStoredDocuments(allocator: std.mem.Allocator, database: *storage.database.Database, plan: *DocumentPlan) !void {527    var handle = database.connection.catalog.openRelation(allocator, storage.rows.nodes_relation) catch |err| switch (err) {528        error.RelationNotFound => if (plan.documents.len == 0) return else return error.MalformedRow,529        else => return err,530    };531    defer handle.deinit();532    var scan: sql.TableScan = undefined;533    try handle.relation.scan(&scan, allocator, null, null);534    defer scan.deinit();535    while (try scan.next()) |entry| {536        const name = try storage.rows.nodeNameView(entry.bytes);537        const docstring = try storage.rows.nodeDocstringView(entry.bytes);538        try plan.append(entry.rowid, name, docstring);539    }540    if (plan.documents_filled != plan.documents.len or plan.text_filled != plan.text.len) return error.MalformedRow;541}542543fn rebuildDocuments(544    allocator: std.mem.Allocator,545    root: []const u8,546    documents: []const sql.SearchDocument,547    source: sql.SearchSource,548    limits: limits_mod.Search,549) !void {550    const dir_path = try cacheDir(allocator, root);551    defer allocator.free(dir_path);552    try sys.fs.createDirPath(dir_path);553    try deleteTempCacheFiles(allocator, root);554    errdefer deleteTempCacheFiles(allocator, root) catch {};555    var dir = try std.Io.Dir.openDirAbsolute(fs_io, dir_path, .{});556    defer dir.close(fs_io);557    var workspace = try cacheWorkspace(allocator, limits.rebuild_wal_bytes);558    defer workspace.deallocate(allocator);559    {560        var cache_database = try sql.FileDatabase.open(allocator, &workspace, dir, .{561            .paths = .{ .database = temp_db_name, .wal = temp_wal_name },562            .header = cacheHeader(1),563            .max_wal_bytes = limits.rebuild_wal_bytes,564        });565        defer cache_database.deinit();566        var cache = try sql.Search.open(&cache_database, .{ .index_prefixes = false, .field_names = &search_field_names });567        try loadDocumentBatches(&cache_database, &cache, allocator, documents, source, .{568            .documents = limits.rebuild_batch_documents,569            .text_bytes = limits.rebuild_batch_text_bytes,570        });571    }572    try replaceCacheFiles(allocator, root);573}574575const DocumentBatchLimits = struct {576    documents: usize,577    text_bytes: usize,578};579580fn loadDocumentBatches(581    database: *sql.FileDatabase,582    cache: *sql.Search,583    allocator: std.mem.Allocator,584    documents: []const sql.SearchDocument,585    source: sql.SearchSource,586    limits: DocumentBatchLimits,587) !void {588    if (documents.len == 0) {589        _ = try cache.loadAllForSource(allocator, documents, source, .{ .durability = .buffered });590        try database.syncWal();591        _ = try database.checkpoint(.{ .restart_header = cacheHeader(2) });592        return;593    }594595    var start: usize = 0;596    var first = true;597    while (start < documents.len) {598        var end = documentBatchEnd(documents, start, limits);599        while (true) {600            loadDocumentBatch(cache, allocator, documents[start..end], source, first) catch |err| switch (err) {601                error.TransactionTooLarge => {602                    if (end - start == 1) return err;603                    end = start + (end - start) / 2;604                    continue;605                },606                else => return err,607            };608            break;609        }610        const final = end == documents.len;611        if (final) try database.syncWal();612        _ = try database.checkpoint(.{ .restart_header = cacheHeader(if (final) 2 else 1) });613        start = end;614        first = false;615    }616}617618fn loadDocumentBatch(619    cache: *sql.Search,620    allocator: std.mem.Allocator,621    documents: []const sql.SearchDocument,622    source: sql.SearchSource,623    first: bool,624) !void {625    if (first) {626        _ = try cache.loadAllForSource(allocator, documents, source, .{ .durability = .buffered });627    } else {628        _ = try cache.loadAllNew(allocator, documents, .{ .durability = .buffered });629    }630}631632fn documentBatchEnd(documents: []const sql.SearchDocument, start: usize, limits: DocumentBatchLimits) usize {633    std.debug.assert(limits.documents > 0);634    std.debug.assert(limits.text_bytes >= sql.SearchMaxDocumentBytes);635    std.debug.assert(start < documents.len);636    var end = start;637    var text_bytes: usize = 0;638    while (end < documents.len and end - start < limits.documents) : (end += 1) {639        const document_bytes = @min(documents[end].text.len, sql.SearchMaxDocumentBytes);640        if (document_bytes > limits.text_bytes - text_bytes) break;641        text_bytes += document_bytes;642    }643    std.debug.assert(end > start);644    return end;645}646647fn sourceForHead(head: sql.Hash) sql.SearchSource {648    return .{ .schema = cache_schema, .head = head };649}650651pub fn searchStored(652    allocator: std.mem.Allocator,653    root: []const u8,654    raw_query: []const u8,655    kind: ?[]const u8,656    limit: i64,657    limits: limits_mod.Storage,658) !Result {659    const normalized = try normalizeQuery(allocator, raw_query);660    defer allocator.free(normalized);661    if (invalidQuery(normalized)) return Error.InvalidSearchQuery;662    var opened = try storage.store.openRead(allocator, root, limits);663    defer opened.close();664    var workspace = try cacheWorkspace(665        allocator,666        sql.file.default_max_wal_bytes,667    );668    defer workspace.deallocate(allocator);669    var database = try openCacheReadOnly(allocator, &workspace, root);670    defer database.deinit();671    const index = sql.search.Reader.open(database.snapshot(), .{672        .index_prefixes = false,673        .field_names = &search_field_names,674    }) catch |err| {675        if (searchCacheReadFailure(err)) return Error.SearchCacheRepairRequired;676        return err;677    };678    const source_matches = index.sourceMatches(allocator, sourceForHead(opened.reader.head)) catch |err| {679        if (searchCacheReadFailure(err)) return Error.SearchCacheRepairRequired;680        return err;681    };682    if (!source_matches) return Error.SearchCacheRepairRequired;683    const index_limit = searchIndexLimit(kind, limit);684    var matched = querySearchIndex(&index, allocator, normalized, index_limit) catch |err| {685        if (searchCacheReadFailure(err)) return Error.SearchCacheRepairRequired;686        return err;687    };688    defer matched.deinit();689    return try selectStoredMatches(allocator, &opened.reader, matched.hits, matched.total, kind, limit);690}691692fn searchCacheReadFailure(err: anyerror) bool {693    return switch (err) {694        error.ColumnOutOfBounds,695        error.InvalidChecksum,696        error.InvalidDatabaseFile,697        error.InvalidKey,698        error.InvalidPage,699        error.InvalidPageId,700        error.InvalidRange,701        error.InvalidRecord,702        error.InvalidRow,703        error.InvalidSearchIndex,704        error.InvalidWal,705        error.OutputTooSmall,706        error.SecondaryIndexCorrupt,707        error.TreeIdentityMissing,708        error.TreeSpaceMismatch,709        error.TreeTooDeep,710        error.UnsupportedPageSize,711        => true,712        else => false,713    };714}715716fn searchIndexLimit(kind: ?[]const u8, limit: i64) usize {717    if (kind != null or limit <= 0) return 0;718    return @intCast(limit);719}720721fn querySearchIndex(index: anytype, allocator: std.mem.Allocator, query: []const u8, limit: usize) !sql.SearchResults {722    if (limit == 0) return index.query(allocator, query, 0) catch |err| switch (err) {723        error.InvalidQuery => Error.InvalidSearchQuery,724        else => return err,725    };726    return index.queryScoreBand(allocator, query, limit) catch |err| switch (err) {727        error.InvalidQuery => Error.InvalidSearchQuery,728        else => return err,729    };730}731732pub fn dbPath(allocator: std.mem.Allocator, root: []const u8) ![]const u8 {733    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name, db_name });734}735736pub fn splitIdentifier(allocator: std.mem.Allocator, name: []const u8) ![]const u8 {737    const empty = @constCast((&[_]u8{})[0..]);738    const bytes = try identifierTokensInto(empty, name);739    const out = try allocator.alloc(u8, bytes);740    errdefer allocator.free(out);741    const filled = try identifierTokensInto(out, name);742    std.debug.assert(filled == out.len);743    return out;744}745746const IdentifierSink = struct {747    out: []u8,748    produced: usize = 0,749    last_space: bool = false,750751    fn append(self: *IdentifierSink, byte: u8) error{CapacityOverflow}!void {752        if (self.produced == std.math.maxInt(usize)) return error.CapacityOverflow;753        if (self.produced < self.out.len) self.out[self.produced] = byte;754        self.produced += 1;755        self.last_space = byte == ' ';756    }757758    fn appendSpace(self: *IdentifierSink) error{CapacityOverflow}!void {759        if (self.produced == 0 or self.last_space) return;760        try self.append(' ');761    }762763    fn finish(self: *IdentifierSink) usize {764        if (self.produced != 0 and self.last_space) self.produced -= 1;765        return self.produced;766    }767};768769fn identifierTokensInto(out: []u8, name: []const u8) error{CapacityOverflow}!usize {770    var sink = IdentifierSink{ .out = out };771    var previous: ?u8 = null;772    for (name, 0..) |byte, index| {773        if (byte == '.' or byte == '_') {774            try sink.appendSpace();775            previous = ' ';776            continue;777        }778        const next = if (index + 1 < name.len) name[index + 1] else 0;779        if (previous) |prev| {780            if (needsCamelSpace(prev, byte, next)) try sink.appendSpace();781        }782        try sink.append(std.ascii.toLower(byte));783        previous = byte;784    }785    return sink.finish();786}787788pub fn normalizeQuery(allocator: std.mem.Allocator, raw: []const u8) ![]const u8 {789    const trimmed = std.mem.trim(u8, raw, " \t\r\n");790    if (trimmed.len == 0) return try allocator.dupe(u8, trimmed);791    if (!identifierShaped(trimmed)) return try allocator.dupe(u8, trimmed);792    var words = std.mem.splitAny(u8, trimmed, " \t\r\n");793    while (words.next()) |word| {794        if (word.len == 0) continue;795        if (std.mem.eql(u8, word, "AND") or std.mem.eql(u8, word, "OR") or std.mem.eql(u8, word, "NOT") or std.mem.eql(u8, word, "NEAR")) return try allocator.dupe(u8, trimmed);796    }797    const split = try splitIdentifier(allocator, trimmed);798    defer allocator.free(split);799    if (split.len == 0) return try allocator.dupe(u8, trimmed);800    var out: std.Io.Writer.Allocating = .init(allocator);801    errdefer out.deinit();802    var parts = std.mem.splitScalar(u8, split, ' ');803    var first = true;804    while (parts.next()) |part| {805        if (part.len == 0) continue;806        if (!first) try out.writer.writeAll(" AND ");807        first = false;808        try out.writer.writeAll(part);809    }810    if (first) return try allocator.dupe(u8, trimmed);811    return try out.toOwnedSlice();812}813814pub fn location(allocator: std.mem.Allocator, hit: Hit) ![]const u8 {815    if (hit.file) |file| {816        if (hit.line_start) |line| return try std.fmt.allocPrint(allocator, "{s}:{d}", .{ file, line });817        return file;818    }819    return "-";820}821822pub fn snippet(hit: Hit) []const u8 {823    const doc = hit.docstring orelse return "-";824    if (doc.len == 0) return "-";825    const first_line = if (std.mem.indexOfScalar(u8, doc, '\n')) |index| doc[0..index] else doc;826    const trimmed = std.mem.trim(u8, first_line, " \t\r\n");827    return trimmed[0..@min(trimmed.len, 80)];828}829830fn cacheDir(allocator: std.mem.Allocator, root: []const u8) ![]const u8 {831    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name });832}833834fn walPath(allocator: std.mem.Allocator, root: []const u8) ![]const u8 {835    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name, wal_name });836}837838fn tempDbPath(allocator: std.mem.Allocator, root: []const u8) ![]const u8 {839    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name, temp_db_name });840}841842fn tempWalPath(allocator: std.mem.Allocator, root: []const u8) ![]const u8 {843    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name, temp_wal_name });844}845846fn cacheMatchesSource(allocator: std.mem.Allocator, root: []const u8, source: sql.SearchSource) !bool {847    const path = try dbPath(allocator, root);848    defer allocator.free(path);849    if (!sys.fs.exists(path)) return false;850    var workspace = try cacheWorkspace(851        allocator,852        sql.file.default_max_wal_bytes,853    );854    defer workspace.deallocate(allocator);855    var database = openCache(allocator, &workspace, root) catch |err| {856        if (searchCacheReadFailure(err)) return false;857        return err;858    };859    defer database.deinit();860    const index = sql.Search.open(&database, .{ .index_prefixes = false, .field_names = &search_field_names }) catch |err| {861        if (searchCacheReadFailure(err)) return false;862        return err;863    };864    return index.sourceMatches(allocator, source) catch |err| {865        if (searchCacheReadFailure(err)) return false;866        return err;867    };868}869870fn deleteTempCacheFiles(allocator: std.mem.Allocator, root: []const u8) !void {871    const database_path = try tempDbPath(allocator, root);872    defer allocator.free(database_path);873    const wal_path = try tempWalPath(allocator, root);874    defer allocator.free(wal_path);875    try deleteOptionalFile(database_path);876    try deleteOptionalFile(wal_path);877}878879fn deleteOptionalFile(path: []const u8) !void {880    sys.fs.deleteFile(path) catch |err| switch (err) {881        error.FileNotFound => {},882        else => return err,883    };884}885886fn replaceCacheFiles(allocator: std.mem.Allocator, root: []const u8) !void {887    const wal_path = try walPath(allocator, root);888    defer allocator.free(wal_path);889    const temporary_database_path = try tempDbPath(allocator, root);890    defer allocator.free(temporary_database_path);891    const database_path = try dbPath(allocator, root);892    defer allocator.free(database_path);893    const temporary_wal_path = try tempWalPath(allocator, root);894    defer allocator.free(temporary_wal_path);895    try deleteOptionalFile(wal_path);896    try sys.fs.rename(temporary_database_path, database_path);897    try deleteOptionalFile(wal_path);898    try sys.fs.rename(temporary_wal_path, wal_path);899}900901fn cacheWorkspace(902    allocator: std.mem.Allocator,903    max_wal_bytes: usize,904) !sql.FileDatabase.Workspace {905    return try sql.FileDatabase.Workspace.allocate(906        allocator,907        cacheWorkspaceLimits(max_wal_bytes),908    );909}910911fn cacheWorkspaceLimits(max_wal_bytes: usize) sql.FileDatabase.Workspace.Limits {912    return .{913        .header = cacheHeader(1),914        .max_wal_bytes = max_wal_bytes,915        .path_storage = .{916            .database_bytes = @max(db_name.len, temp_db_name.len),917            .wal_bytes = @max(wal_name.len, temp_wal_name.len),918        },919    };920}921922test "search cache workspace path capacity spans current and rebuild names" {923    const limits = cacheWorkspaceLimits(sql.file.default_max_wal_bytes).path_storage;924    try std.testing.expectEqual(925        @max(db_name.len, temp_db_name.len),926        limits.database_bytes,927    );928    try std.testing.expectEqual(929        @max(wal_name.len, temp_wal_name.len),930        limits.wal_bytes,931    );932}933934fn openCache(935    allocator: std.mem.Allocator,936    workspace: *sql.FileDatabase.Workspace,937    root: []const u8,938) !sql.FileDatabase {939    const dir_path = try cacheDir(allocator, root);940    defer allocator.free(dir_path);941    var dir = try std.Io.Dir.openDirAbsolute(fs_io, dir_path, .{});942    defer dir.close(fs_io);943    return try sql.FileDatabase.open(allocator, workspace, dir, .{944        .paths = .{ .database = db_name, .wal = wal_name },945        .header = cacheHeader(3),946        .read_cache_capacity = 16,947    });948}949950fn openCacheForTesting(951    allocator: std.mem.Allocator,952    root: []const u8,953) !sql.FileDatabase {954    const dir_path = try cacheDir(allocator, root);955    defer allocator.free(dir_path);956    var dir = try std.Io.Dir.openDirAbsolute(fs_io, dir_path, .{});957    defer dir.close(fs_io);958    return try sql.FileDatabase.openForTesting(allocator, dir, .{959        .paths = .{ .database = db_name, .wal = wal_name },960        .header = cacheHeader(3),961        .read_cache_capacity = 16,962    });963}964965fn openCacheReadOnly(966    allocator: std.mem.Allocator,967    workspace: *sql.FileDatabase.Workspace,968    root: []const u8,969) !sql.FileReadOnlyDatabase {970    const dir_path = try cacheDir(allocator, root);971    defer allocator.free(dir_path);972    var dir = try std.Io.Dir.openDirAbsolute(fs_io, dir_path, .{});973    defer dir.close(fs_io);974    const opened = try sql.FileReadOnlyDatabase.openExisting(allocator, workspace, dir, .{975        .paths = .{ .database = db_name, .wal = wal_name },976        .header = cacheHeader(3),977        .read_cache_capacity = 16,978    });979    return switch (opened) {980        .ready => |ready| ready,981        .repair_required => Error.SearchCacheRepairRequired,982    };983}984985fn cacheHeader(sequence: u32) sql.wal.Header {986    return .{987        .sequence = sequence,988        .salt = .{ .first = 0x534d_4702 + sequence, .second = 0x5155_4553 + sequence },989    };990}991992fn nodeSearchTextBytes(name: []const u8, docstring: ?[]const u8) error{CapacityOverflow}!usize {993    const token_bytes = try identifierTokensInto(@constCast((&[_]u8{})[0..]), name);994    const doc = docstring orelse return @min(token_bytes, sql.SearchMaxDocumentBytes);995    if (doc.len == 0) return @min(token_bytes, sql.SearchMaxDocumentBytes);996    const separator_end = std.math.add(usize, token_bytes, 1) catch return error.CapacityOverflow;997    const full_bytes = std.math.add(usize, separator_end, doc.len) catch return error.CapacityOverflow;998    return @min(full_bytes, sql.SearchMaxDocumentBytes);999}10001001fn fillNodeSearchText(out: []u8, name: []const u8, docstring: ?[]const u8) void {1002    const token_bytes = identifierTokensInto(@constCast((&[_]u8{})[0..]), name) catch unreachable;1003    const rendered_bytes = identifierTokensInto(out[0..@min(out.len, token_bytes)], name) catch unreachable;1004    std.debug.assert(rendered_bytes == token_bytes);1005    const doc = docstring orelse {1006        std.debug.assert(out.len == @min(token_bytes, sql.SearchMaxDocumentBytes));1007        return;1008    };1009    if (doc.len == 0) {1010        std.debug.assert(out.len == @min(token_bytes, sql.SearchMaxDocumentBytes));1011        return;1012    }1013    if (token_bytes >= out.len) return;1014    out[token_bytes] = sql.SearchFieldSeparator;1015    const doc_start = token_bytes + 1;1016    @memcpy(out[doc_start..], doc[0 .. out.len - doc_start]);1017}10181019const SelectedHit = struct {1020    node: *const model.Node,1021    score: usize,1022};10231024fn selectStoredMatches(allocator: std.mem.Allocator, reader: *storage.database.Reader, hits: []const sql.SearchHit, matched_total: usize, kind: ?[]const u8, limit: i64) !Result {1025    const candidate_hits = storedCandidateHits(hits, kind, limit);1026    if (candidate_hits.len == 0) return .{ .hits = &.{}, .total = if (kind == null) @intCast(matched_total) else 0 };1027    const rowids = try hitRowids(allocator, candidate_hits);1028    defer if (rowids.len != 0) allocator.free(rowids);1029    const rows = try storage.nodes.rowsByIdFromReader(allocator, reader, rowids);1030    defer storage.nodes.freeRows(allocator, rows);1031    var selected: std.ArrayList(SelectedHit) = .empty;1032    defer selected.deinit(allocator);1033    const max_hits: usize = if (limit > 0) @intCast(limit) else 0;1034    const capped = max_hits != 0;1035    var total: i64 = if (kind == null) @intCast(matched_total) else 0;1036    for (candidate_hits) |hit| {1037        const node = nodePointerForStoredRow(rows, hit.rowid) orelse continue;1038        if (kind != null and !std.mem.eql(u8, node.type, kind.?)) continue;1039        if (kind != null) total += 1;1040        const selected_hit: SelectedHit = .{ .node = node, .score = hit.score };1041        if (!capped or selected.items.len < max_hits) {1042            try selected.append(allocator, selected_hit);1043            if (capped and selected.items.len == max_hits) std.mem.sort(SelectedHit, selected.items, {}, selectedHitLess);1044            continue;1045        }1046        if (!selectedHitLess({}, selected_hit, selected.items[selected.items.len - 1])) continue;1047        selected.items[selected.items.len - 1] = selected_hit;1048        restoreSelectedOrder(selected.items);1049    }1050    std.mem.sort(SelectedHit, selected.items, {}, selectedHitLess);1051    const out = try allocator.alloc(Hit, selected.items.len);1052    var filled: usize = 0;1053    errdefer {1054        freeHits(allocator, out[0..filled]);1055        allocator.free(out);1056    }1057    for (selected.items, 0..) |selected_hit, index| {1058        out[index] = try hitFromNode(allocator, selected_hit.node.*, selected_hit.score);1059        out[index].rank = @intCast(index + 1);1060        filled += 1;1061    }1062    return .{ .hits = out, .total = total };1063}10641065fn storedCandidateHits(hits: []const sql.SearchHit, kind: ?[]const u8, limit: i64) []const sql.SearchHit {1066    if (kind != null or limit <= 0) return hits;1067    const max_hits: usize = @intCast(limit);1068    if (hits.len <= max_hits) return hits;1069    const cutoff = hits[max_hits - 1].score;1070    var count = max_hits;1071    while (count < hits.len and hits[count].score >= cutoff) count += 1;1072    return hits[0..count];1073}10741075fn hitRowids(allocator: std.mem.Allocator, hits: []const sql.SearchHit) ![]i64 {1076    if (hits.len == 0) return &.{};1077    const rowids = try allocator.alloc(i64, hits.len);1078    for (hits, 0..) |hit, index| rowids[index] = hit.rowid;1079    return rowids;1080}10811082fn nodePointerForStoredRow(rows: []const storage.nodes.NodeRow, rowid: i64) ?*const model.Node {1083    var low: usize = 0;1084    var high = rows.len;1085    while (low < high) {1086        const mid = low + (high - low) / 2;1087        if (rows[mid].rowid == rowid) return &rows[mid].node;1088        if (rows[mid].rowid < rowid) {1089            low = mid + 1;1090        } else {1091            high = mid;1092        }1093    }1094    return null;1095}10961097fn restoreSelectedOrder(hits: []SelectedHit) void {1098    var index = hits.len - 1;1099    while (index > 0 and selectedHitLess({}, hits[index], hits[index - 1])) : (index -= 1) {1100        std.mem.swap(SelectedHit, &hits[index], &hits[index - 1]);1101    }1102}11031104fn selectedHitLess(_: void, left: SelectedHit, right: SelectedHit) bool {1105    if (left.score != right.score) return left.score > right.score;1106    return std.mem.lessThan(u8, left.node.name, right.node.name);1107}11081109fn hitFromNode(allocator: std.mem.Allocator, node: model.Node, score: usize) !Hit {1110    const name = try allocator.dupe(u8, node.name);1111    errdefer allocator.free(name);1112    const kind = try allocator.dupe(u8, node.type);1113    errdefer allocator.free(kind);1114    const file = try dupOptional(allocator, node.file);1115    errdefer if (file) |value| allocator.free(value);1116    const docstring = try dupOptional(allocator, node.docstring);1117    errdefer if (docstring) |value| allocator.free(value);1118    return .{1119        .rank = 0,1120        .name = name,1121        .kind = kind,1122        .file = file,1123        .line_start = node.line,1124        .line_end = node.end_line,1125        .docstring = docstring,1126        .score = @floatFromInt(score),1127    };1128}11291130fn freeHits(allocator: std.mem.Allocator, hits: []const Hit) void {1131    for (hits) |hit| {1132        allocator.free(hit.name);1133        allocator.free(hit.kind);1134        if (hit.file) |file| allocator.free(file);1135        if (hit.docstring) |docstring| allocator.free(docstring);1136    }1137}11381139fn dupOptional(allocator: std.mem.Allocator, value: ?[]const u8) !?[]const u8 {1140    return if (value) |text| try allocator.dupe(u8, text) else null;1141}11421143fn invalidQuery(query: []const u8) bool {1144    const trimmed = std.mem.trim(u8, query, " \t\r\n");1145    if (trimmed.len == 0) return true;1146    var offset: usize = 0;1147    var saw_operand = false;1148    var expects_operand = true;1149    while (nextQueryPart(trimmed, &offset)) |part| {1150        if (!part.quoted and booleanOperator(part.text)) {1151            if (expects_operand or !saw_operand) return true;1152            expects_operand = true;1153            continue;1154        }1155        saw_operand = true;1156        expects_operand = false;1157    }1158    return !saw_operand or expects_operand;1159}11601161const QueryPart = struct {1162    text: []const u8,1163    quoted: bool,1164};11651166fn nextQueryPart(source: []const u8, offset: *usize) ?QueryPart {1167    while (offset.* < source.len and std.ascii.isWhitespace(source[offset.*])) offset.* += 1;1168    if (offset.* >= source.len) return null;1169    if (source[offset.*] == '"') {1170        const start = offset.* + 1;1171        var end = start;1172        while (end < source.len and source[end] != '"') end += 1;1173        offset.* = if (end < source.len) end + 1 else end;1174        return .{ .text = source[start..end], .quoted = true };1175    }1176    const start = offset.*;1177    while (offset.* < source.len and !std.ascii.isWhitespace(source[offset.*])) offset.* += 1;1178    return .{ .text = source[start..offset.*], .quoted = false };1179}11801181fn booleanOperator(text_value: []const u8) bool {1182    return std.mem.eql(u8, text_value, "AND") or std.mem.eql(u8, text_value, "OR") or std.mem.eql(u8, text_value, "NOT");1183}11841185fn identifierShaped(value: []const u8) bool {1186    for (value) |byte| {1187        if (std.ascii.isAlphanumeric(byte) or byte == '.' or byte == '_' or byte == ' ' or byte == '\t' or byte == '\r' or byte == '\n') continue;1188        return false;1189    }1190    return true;1191}11921193fn needsCamelSpace(previous: u8, current: u8, next: u8) bool {1194    if ((std.ascii.isLower(previous) or std.ascii.isDigit(previous)) and std.ascii.isUpper(current)) return true;1195    if (std.ascii.isUpper(previous) and std.ascii.isUpper(current) and next != 0 and std.ascii.isLower(next)) return true;1196    return false;1197}11981199fn documentAllocSlice(comptime T: type, allocator: std.mem.Allocator, count: usize) std.mem.Allocator.Error![]T {1200    if (count == 0) return @constCast((&[_]T{})[0..]);1201    return try allocator.alloc(T, count);1202}12031204fn documentFreeSlice(comptime T: type, allocator: std.mem.Allocator, values: []T) void {1205    if (values.len != 0) allocator.free(values);1206}12071208fn modelDocumentPlanBytes(limits: DocumentPlan.Limits) ?usize {1209    if (limits.documents > std.math.maxInt(usize) / @sizeOf(sql.SearchDocument)) return null;1210    const document_bytes = limits.documents * @sizeOf(sql.SearchDocument);1211    if (document_bytes > std.math.maxInt(usize) - limits.text_bytes) return null;1212    return document_bytes + limits.text_bytes;1213}12141215test "search document plan capacity matches an independent bounded text model" {1216    comptime {1217        @stardustClaim(1218            @import("alloc_phase").capacity.witness(DocumentPlan, "smg_search_document_plan_capacity_capacity_model"),1219            null,1220            null,1221            null,1222            null,1223            null,1224            null,1225        );1226    }1227    comptime {1228        @stardustClaim(1229            @import("alloc_phase").capacity.witness(DocumentPlan, "smg_search_document_plan_capacity_overload"),1230            null,1231            null,1232            null,1233            null,1234            null,1235            null,1236        );1237    }12381239    for (0..64) |documents| {1240        const limits = DocumentPlan.Limits{1241            .documents = documents,1242            .text_bytes = documents * 19,1243        };1244        const capacity = try DocumentPlan.Capacity.derive(limits);1245        try std.testing.expectEqual(modelDocumentPlanBytes(limits).?, capacity.bytes);1246    }1247    const overflow = DocumentPlan.Limits{1248        .documents = std.math.maxInt(usize),1249        .text_bytes = 1,1250    };1251    try std.testing.expect(modelDocumentPlanBytes(overflow) == null);1252    try std.testing.expectError(error.CapacityOverflow, DocumentPlan.Capacity.derive(overflow));12531254    var long_doc: [sql.SearchMaxDocumentBytes + 64]u8 = undefined;1255    @memset(&long_doc, 'x');1256    try std.testing.expectEqual(1257        @as(usize, sql.SearchMaxDocumentBytes),1258        try nodeSearchTextBytes("app.main", &long_doc),1259    );1260}12611262fn checkDocumentPlanInitAllocationFailures(allocator: std.mem.Allocator) !void {1263    var plan = try DocumentPlan.init(allocator, .{ .documents = 3, .text_bytes = 64 });1264    plan.deinit(allocator);1265}12661267test "search document plan initialization cleans allocation failure and retries" {1268    comptime {1269        @stardustClaim(1270            @import("alloc_phase").capacity.witness(DocumentPlan, "smg_search_document_plan_oom"),1271            null,1272            null,1273            null,1274            null,1275            null,1276            null,1277        );1278    }12791280    try std.testing.checkAllAllocationFailures(1281        std.testing.allocator,1282        checkDocumentPlanInitAllocationFailures,1283        .{},1284    );1285    const expected = "app main" ++ [_]u8{sql.SearchFieldSeparator} ++ "entry";1286    var plan = try DocumentPlan.init(std.testing.allocator, .{ .documents = 1, .text_bytes = expected.len });1287    defer plan.deinit(std.testing.allocator);1288    try plan.append(7, "app.main", "entry");1289    plan.activate();1290    try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, plan.phase);1291}12921293test "search document plan fills exact records and bounded text while sealed" {1294    comptime {1295        @stardustClaim(1296            @import("alloc_phase").capacity.witness(DocumentPlan, "smg_search_document_plan_sealed"),1297            null,1298            null,1299            null,1300            null,1301            null,1302            null,1303        );1304    }13051306    const expected = [_][]const u8{1307        "",1308        "app main",1309        "parse html document" ++ [_]u8{sql.SearchFieldSeparator} ++ "Read markup",1310    };1311    const limits = DocumentPlan.Limits{1312        .documents = expected.len,1313        .text_bytes = expected[0].len + expected[1].len + expected[2].len,1314    };1315    var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator);1316    var plan = try DocumentPlan.init(phase_allocator.initializationAllocator(), limits);1317    defer {1318        if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization();1319        if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();1320        plan.deinit(phase_allocator.teardownAllocator());1321        phase_allocator.deinit();1322    }1323    const documents_pointer = plan.documents.ptr;1324    const text_pointer = plan.text.ptr;1325    phase_allocator.seal();1326    try plan.append(3, "", null);1327    try plan.append(5, "app.main", null);1328    try plan.append(9, "parseHTMLDocument", "Read markup");1329    plan.activate();13301331    for (expected, plan.documents) |text_value, document| {1332        try std.testing.expectEqualStrings(text_value, document.text);1333    }1334    try std.testing.expectEqual(@as(i64, 3), plan.documents[0].rowid);1335    try std.testing.expectEqual(@as(i64, 5), plan.documents[1].rowid);1336    try std.testing.expectEqual(@as(i64, 9), plan.documents[2].rowid);1337    try std.testing.expect(plan.documents[1].text.ptr == plan.text[expected[0].len..].ptr);1338    try std.testing.expectEqual(documents_pointer, plan.documents.ptr);1339    try std.testing.expectEqual(text_pointer, plan.text.ptr);1340    try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());1341}13421343test "stored search document plan preserves rowids and rendered fields without node snapshots" {1344    comptime {1345        @stardustClaim(1346            @import("alloc_phase").capacity.witness(DocumentPlan, "smg_search_document_plan_integration"),1347            null,1348            null,1349            null,1350            null,1351            null,1352            null,1353        );1354    }13551356    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1357    defer arena.deinit();1358    const allocator = arena.allocator();1359    const root = try std.fmt.allocPrint(allocator, "/tmp/smg-search-document-plan-{x}", .{@as(u64, @intCast(@max(0, sys.time.realMilliTimestamp())))});1360    defer sys.fs.deleteTree(root) catch {};1361    try sys.fs.createDirPath(root);1362    _ = try storage.initProject(allocator, root, testingLimits().storage);1363    var graph = graph_mod.init(allocator);1364    try graph_mod.addNode(&graph, .{1365        .name = "z.item",1366        .type = model.NodeType.function,1367        .docstring = "Last entry",1368        .metadata = try model.sourcePair(allocator, "scan"),1369    });1370    try graph_mod.addNode(&graph, .{1371        .name = "a.HTTPServer",1372        .type = model.NodeType.class,1373        .docstring = "Serve requests",1374        .metadata = try model.sourcePair(allocator, "manual"),1375    });1376    var opened = try storage.store.open(allocator, root, testingLimits().storage);1377    defer opened.close();1378    const saved = try storage.graph.replace(allocator, &opened.database, graph);1379    var stored = try storedDocuments(std.testing.allocator, &opened.database, saved);1380    defer stored.plan.deinit(std.testing.allocator);1381    try std.testing.expect(std.mem.eql(u8, &saved, &stored.head));1382    try std.testing.expectEqual(@as(usize, 2), stored.plan.documents.len);1383    try std.testing.expectEqual(@as(i64, 1), stored.plan.documents[0].rowid);1384    try std.testing.expectEqualStrings(1385        "a http server" ++ [_]u8{sql.SearchFieldSeparator} ++ "Serve requests",1386        stored.plan.documents[0].text,1387    );1388    try std.testing.expectEqual(@as(i64, 2), stored.plan.documents[1].rowid);1389    try std.testing.expectEqualStrings(1390        "z item" ++ [_]u8{sql.SearchFieldSeparator} ++ "Last entry",1391        stored.plan.documents[1].text,1392    );1393}13941395test "search document batches cap records and indexed text" {1396    const large_text = @as([(sql.SearchMaxDocumentBytes / 2 + 1)]u8, @splat('x'));1397    const documents = [_]sql.SearchDocument{1398        .{ .rowid = 1, .text = &large_text },1399        .{ .rowid = 2, .text = &large_text },1400        .{ .rowid = 3, .text = "tail" },1401        .{ .rowid = 4, .text = "last" },1402    };1403    const text_limited = DocumentBatchLimits{1404        .documents = documents.len,1405        .text_bytes = sql.SearchMaxDocumentBytes,1406    };1407    try std.testing.expectEqual(@as(usize, 1), documentBatchEnd(&documents, 0, text_limited));1408    try std.testing.expectEqual(@as(usize, 4), documentBatchEnd(&documents, 1, text_limited));14091410    const record_limited = DocumentBatchLimits{1411        .documents = 2,1412        .text_bytes = testingLimits().search.rebuild_batch_text_bytes,1413    };1414    try std.testing.expectEqual(@as(usize, 2), documentBatchEnd(&documents, 0, record_limited));1415    try std.testing.expectEqual(@as(usize, 4), documentBatchEnd(&documents, 2, record_limited));1416}14171418test "search document batches preserve source and postings across reopen" {1419    var tmp = std.testing.tmpDir(.{});1420    defer tmp.cleanup();1421    const source = sql.SearchSource{1422        .schema = cache_schema,1423        .head = @as([32]u8, @splat(7)),1424    };1425    const documents = [_]sql.SearchDocument{1426        .{ .rowid = 1, .text = "shared alpha" },1427        .{ .rowid = 2, .text = "shared beta" },1428        .{ .rowid = 3, .text = "shared gamma" },1429        .{ .rowid = 4, .text = "shared delta" },1430        .{ .rowid = 5, .text = "shared epsilon" },1431    };1432    {1433        var database = try sql.FileDatabase.openForTesting(std.testing.allocator, tmp.dir, .{1434            .paths = .{ .database = temp_db_name, .wal = temp_wal_name },1435            .header = cacheHeader(1),1436            .max_wal_bytes = testingLimits().search.rebuild_wal_bytes,1437        });1438        defer database.deinit();1439        var cache = try sql.Search.open(&database, .{ .index_prefixes = false, .field_names = &search_field_names });1440        try loadDocumentBatches(&database, &cache, std.testing.allocator, &.{}, source, .{1441            .documents = 2,1442            .text_bytes = sql.SearchMaxDocumentBytes,1443        });1444        try std.testing.expect(try cache.sourceMatches(std.testing.allocator, source));1445        try loadDocumentBatches(&database, &cache, std.testing.allocator, &documents, source, .{1446            .documents = 2,1447            .text_bytes = sql.SearchMaxDocumentBytes,1448        });1449        try std.testing.expect(try cache.sourceMatches(std.testing.allocator, source));1450    }1451    var reopened = try sql.FileDatabase.openForTesting(std.testing.allocator, tmp.dir, .{1452        .paths = .{ .database = temp_db_name, .wal = temp_wal_name },1453        .header = cacheHeader(3),1454        .max_wal_bytes = testingLimits().search.rebuild_wal_bytes,1455    });1456    defer reopened.deinit();1457    const cache = try sql.Search.open(&reopened, .{ .index_prefixes = false, .field_names = &search_field_names });1458    try std.testing.expect(try cache.sourceMatches(std.testing.allocator, source));1459    var shared = try cache.query(std.testing.allocator, "shared", 0);1460    defer shared.deinit();1461    try std.testing.expectEqual(documents.len, shared.total);1462    for (shared.hits, 0..) |hit, index| try std.testing.expectEqual(documents[index].rowid, hit.rowid);1463    var epsilon = try cache.query(std.testing.allocator, "epsilon", 0);1464    defer epsilon.deinit();1465    try std.testing.expectEqual(@as(usize, 1), epsilon.total);1466    try std.testing.expectEqual(@as(i64, 5), epsilon.hits[0].rowid);1467}14681469test "search document batches retry within the WAL capacity" {1470    var tmp = std.testing.tmpDir(.{});1471    defer tmp.cleanup();1472    var text: [sql.SearchMaxDocumentBytes]u8 = undefined;1473    for (&text, 0..) |*byte, index| byte.* = "alpha "[index % "alpha ".len];1474    var documents: [8]sql.SearchDocument = undefined;1475    for (&documents, 0..) |*document, index| document.* = .{1476        .rowid = @intCast(index + 1),1477        .text = &text,1478    };1479    const source = sql.SearchSource{1480        .schema = cache_schema,1481        .head = @as([32]u8, @splat(9)),1482    };1483    var database = try sql.FileDatabase.openForTesting(std.testing.allocator, tmp.dir, .{1484        .paths = .{ .database = temp_db_name, .wal = temp_wal_name },1485        .header = cacheHeader(1),1486        .max_wal_bytes = 256 * 1024,1487    });1488    defer database.deinit();1489    var cache = try sql.Search.open(&database, .{ .index_prefixes = false, .field_names = &search_field_names });1490    try std.testing.expectError(1491        error.TransactionTooLarge,1492        cache.loadAllForSource(std.testing.allocator, &documents, source, .{ .durability = .buffered }),1493    );1494    try loadDocumentBatches(&database, &cache, std.testing.allocator, &documents, source, .{1495        .documents = documents.len,1496        .text_bytes = documents.len * sql.SearchMaxDocumentBytes,1497    });1498    try std.testing.expect(try cache.sourceMatches(std.testing.allocator, source));1499    var alpha = try cache.query(std.testing.allocator, "alpha", 0);1500    defer alpha.deinit();1501    try std.testing.expectEqual(documents.len, alpha.total);1502}15031504test "split identifiers like python search schema" {1505    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1506    defer arena.deinit();1507    const allocator = arena.allocator();1508    try std.testing.expectEqualStrings("smg cli helpers truncate", try splitIdentifier(allocator, "smg.cli.helpers._truncate"));1509    try std.testing.expectEqualStrings("parse html document", try splitIdentifier(allocator, "parseHTMLDocument"));1510    try std.testing.expectEqualStrings("smg graph sem graph analyze hot", try splitIdentifier(allocator, "smg.graph.SemGraph.analyze_hot"));1511}15121513test "normalize identifier queries for fts" {1514    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1515    defer arena.deinit();1516    const allocator = arena.allocator();1517    try std.testing.expectEqualStrings("smg AND cli AND helpers AND truncate", try normalizeQuery(allocator, "smg.cli.helpers._truncate"));1518    try std.testing.expectEqualStrings("foo OR", try normalizeQuery(allocator, "foo OR"));1519    try std.testing.expectEqualStrings("foo AND or AND bar", try normalizeQuery(allocator, "foo or bar"));1520}15211522test "reject malformed search queries like python sqlite fts" {1523    try std.testing.expect(invalidQuery(""));1524    try std.testing.expect(invalidQuery("foo OR"));1525    try std.testing.expect(invalidQuery("foo AND"));1526    try std.testing.expect(invalidQuery("foo NOT"));1527    try std.testing.expect(invalidQuery("OR foo"));1528    try std.testing.expect(invalidQuery("NOT foo"));1529    try std.testing.expect(invalidQuery("foo AND NOT bar"));1530    try std.testing.expect(!invalidQuery("foo OR bar"));1531    try std.testing.expect(!invalidQuery("foo AND bar"));1532    try std.testing.expect(!invalidQuery("foo NOT bar"));1533    try std.testing.expect(!invalidQuery("NEAR"));1534    try std.testing.expect(!invalidQuery("foo AND or AND bar"));1535}15361537test "sync incrementally applies graph changes and advances the source head" {1538    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1539    defer arena.deinit();1540    const allocator = arena.allocator();1541    const root = try std.fmt.allocPrint(allocator, "/tmp/smg-search-sync-test-{x}", .{@as(u64, @intCast(@max(0, sys.time.realMilliTimestamp())))});1542    defer sys.fs.deleteTree(root) catch {};1543    try sys.fs.createDirPath(try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name }));1544    var graph = graph_mod.init(allocator);1545    try graph_mod.addNode(&graph, .{1546        .name = "sync.target",1547        .type = model.NodeType.function,1548        .file = "src/sync.py",1549        .line = 3,1550        .docstring = "sync probe",1551    });1552    const saved = try replaceAndSyncForTest(allocator, graph, root);1553    try std.testing.expectEqual(SyncKind.rebuilt, saved.kind);1554    {1555        var database = try openCacheForTesting(allocator, root);1556        defer database.deinit();1557        const index = try sql.Search.open(&database, .{ .index_prefixes = false, .field_names = &search_field_names });1558        try std.testing.expect(try index.sourceMatches(allocator, sourceForHead(saved.head)));1559    }1560    try std.testing.expectEqual(1561        SyncKind.matched,1562        try syncStoredForTest(allocator, root, saved.head),1563    );15641565    try graph_mod.addNode(&graph, .{1566        .name = "sync.other",1567        .type = model.NodeType.function,1568        .file = "src/sync.py",1569        .line = 9,1570        .docstring = "second probe",1571    });1572    const changed = try replaceAndSyncForTest(allocator, graph, root);1573    try std.testing.expectEqual(SyncKind.incremental, changed.kind);1574    try std.testing.expect(!std.mem.eql(u8, &saved.head, &changed.head));1575    {1576        var database = try openCacheForTesting(allocator, root);1577        defer database.deinit();1578        const index = try sql.Search.open(&database, .{ .index_prefixes = false, .field_names = &search_field_names });1579        try std.testing.expect(try index.sourceMatches(allocator, sourceForHead(changed.head)));1580    }15811582    const result = try searchStored(1583        allocator,1584        root,1585        "sync.other",1586        null,1587        10,1588        testingLimits().storage,1589    );1590    try std.testing.expectEqual(@as(i64, 1), result.total);15911592    const other_index = graph.node_index.get("sync.other").?;1593    graph.nodes.items[other_index].line = 10;1594    const metadata = try replaceAndSyncForTest(allocator, graph, root);1595    try std.testing.expectEqual(SyncKind.incremental, metadata.kind);1596    const retained = try searchStored(1597        allocator,1598        root,1599        "second probe",1600        null,1601        10,1602        testingLimits().storage,1603    );1604    try std.testing.expectEqual(@as(i64, 1), retained.total);16051606    graph.nodes.items[other_index].docstring = "replacement marker";1607    const updated = try replaceAndSyncForTest(allocator, graph, root);1608    try std.testing.expectEqual(SyncKind.incremental, updated.kind);1609    const replacement = try searchStored(1610        allocator,1611        root,1612        "replacement marker",1613        null,1614        10,1615        testingLimits().storage,1616    );1617    try std.testing.expectEqual(@as(i64, 1), replacement.total);1618    const retired = try searchStored(1619        allocator,1620        root,1621        "second probe",1622        null,1623        10,1624        testingLimits().storage,1625    );1626    try std.testing.expectEqual(@as(i64, 0), retired.total);16271628    try graph_mod.removeNodes(&graph, &.{"sync.other"});1629    const removed = try replaceAndSyncForTest(allocator, graph, root);1630    try std.testing.expectEqual(SyncKind.incremental, removed.kind);1631    const absent = try searchStored(1632        allocator,1633        root,1634        "replacement marker",1635        null,1636        10,1637        testingLimits().storage,1638    );1639    try std.testing.expectEqual(@as(i64, 0), absent.total);1640}16411642test "stored search rejects a mismatched cache source without rebuilding" {1643    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1644    defer arena.deinit();1645    const allocator = arena.allocator();1646    const root = try std.fmt.allocPrint(allocator, "/tmp/smg-search-source-test-{x}", .{@as(u64, @intCast(@max(0, sys.time.realMilliTimestamp())))});1647    defer sys.fs.deleteTree(root) catch {};1648    try sys.fs.createDirPath(try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name }));1649    var graph = graph_mod.init(allocator);1650    try graph_mod.addNode(&graph, .{1651        .name = "source.target",1652        .type = model.NodeType.function,1653        .docstring = "source probe",1654    });1655    const head = try replaceGraphForTest(allocator, graph, root);1656    _ = try syncStoredForTest(allocator, root, head);1657    const expected = sourceForHead(head);1658    const mismatched = sql.SearchSource{ .schema = cache_schema + 1, .head = head };1659    {1660        var database = try openCacheForTesting(allocator, root);1661        defer database.deinit();1662        var index = try sql.Search.open(&database, .{1663            .index_prefixes = false,1664            .field_names = &search_field_names,1665        });1666        try std.testing.expect((try index.advanceSource(1667            allocator,1668            expected,1669            mismatched,1670            .{ .durability = .synced },1671        )) != null);1672    }16731674    try std.testing.expectError(1675        Error.SearchCacheRepairRequired,1676        searchStored(1677            allocator,1678            root,1679            "source",1680            null,1681            10,1682            testingLimits().storage,1683        ),1684    );1685    var database = try openCacheForTesting(allocator, root);1686    defer database.deinit();1687    const index = try sql.Search.open(&database, .{1688        .index_prefixes = false,1689        .field_names = &search_field_names,1690    });1691    try std.testing.expect(try index.sourceMatches(allocator, mismatched));1692}16931694test "matched graph publication rebuilds a malformed search cache" {1695    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1696    defer arena.deinit();1697    const allocator = arena.allocator();1698    const root = try std.fmt.allocPrint(allocator, "/tmp/smg-search-matched-repair-{x}", .{1699        @as(u64, @intCast(@max(0, sys.time.realMilliTimestamp()))),1700    });1701    defer sys.fs.deleteTree(root) catch {};1702    try sys.fs.createDirPath(root);1703    _ = try storage.initProject(allocator, root, testingLimits().storage);1704    const source = try storage.graph.loadSnapshot(1705        allocator,1706        allocator,1707        root,1708        testingLimits().storage,1709    );1710    var graph = graph_mod.init(allocator);1711    try graph_mod.addNode(&graph, .{1712        .name = "repair.target",1713        .type = model.NodeType.function,1714        .docstring = "matched search repair",1715    });1716    const published = try storage.graph.publishTimed(1717        allocator,1718        root,1719        graph,1720        source.head,1721        testingLimits(),1722    );17231724    try sys.fs.writeFile(try dbPath(allocator, root), "invalid search cache");1725    sys.fs.deleteFile(try walPath(allocator, root)) catch |err| switch (err) {1726        error.FileNotFound => {},1727        else => return err,1728    };1729    const repaired = try storage.graph.publishMatchedTimed(1730        allocator,1731        root,1732        graph,1733        published.head,1734        testingLimits(),1735    );1736    try std.testing.expect(sql.version.same(published.head, repaired.head));1737    try std.testing.expectEqual(@as(u64, 0), repaired.graph_ns);1738    try std.testing.expectEqual(SyncKind.rebuilt, repaired.index_kind);1739    try std.testing.expectEqual(@as(usize, 0), repaired.node_puts);1740    try std.testing.expectEqual(@as(usize, 0), repaired.node_deletes);1741    const result = try searchStored(1742        allocator,1743        root,1744        "matched search repair",1745        null,1746        10,1747        testingLimits().storage,1748    );1749    try std.testing.expectEqual(@as(i64, 1), result.total);1750    try std.testing.expect(try storage.names.matchesHead(allocator, root, published.head));1751}17521753test "rebuild and query native search index" {1754    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);1755    defer arena.deinit();1756    const allocator = arena.allocator();1757    const root = try std.fmt.allocPrint(allocator, "/tmp/smg-search-test-{x}", .{@as(u64, @intCast(@max(0, sys.time.realMilliTimestamp())))});1758    defer sys.fs.deleteTree(root) catch {};1759    try sys.fs.createDirPath(try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name }));1760    var graph = graph_mod.init(allocator);1761    try graph_mod.addNode(&graph, .{1762        .name = "smg.cli.helpers._truncate",1763        .type = model.NodeType.function,1764        .file = "src/smg/cli/_helpers.py",1765        .line = 42,1766        .docstring = "Trim a string to width",1767    });1768    try graph_mod.addNode(&graph, .{1769        .name = "smg.graph.SemGraph",1770        .type = model.NodeType.class,1771        .file = "src/smg/graph.py",1772        .line = 10,1773        .docstring = "Core graph structure",1774    });1775    try graph_mod.addNode(&graph, .{1776        .name = "aaa.truncate",1777        .type = model.NodeType.function,1778        .file = "src/smg/aaa.py",1779        .line = 7,1780        .docstring = "Truncate helper",1781    });1782    try graph_mod.addNode(&graph, .{1783        .name = "zzz.truncate",1784        .type = model.NodeType.class,1785        .file = "src/smg/zzz.py",1786        .line = 8,1787        .docstring = "Truncate class",1788    });1789    const saved = try replaceGraphForTest(allocator, graph, root);1790    try std.testing.expectEqual(1791        @as(usize, 4),1792        try rebuildStored(allocator, root, testingLimits()),1793    );1794    try std.testing.expect(sys.fs.exists(try dbPath(allocator, root)));1795    {1796        var database = try openCacheForTesting(allocator, root);1797        defer database.deinit();1798        const index = try sql.Search.open(&database, .{ .index_prefixes = false, .field_names = &search_field_names });1799        try std.testing.expect(try index.sourceMatches(allocator, sourceForHead(saved)));1800    }1801    const result = try searchStored(1802        allocator,1803        root,1804        "smg.cli.helpers._truncate",1805        model.NodeType.function,1806        10,1807        testingLimits().storage,1808    );1809    try std.testing.expectEqual(@as(i64, 1), result.total);1810    try std.testing.expectEqualStrings("smg.cli.helpers._truncate", result.hits[0].name);1811    try std.testing.expectEqualStrings("src/smg/cli/_helpers.py:42", try location(allocator, result.hits[0]));1812    try std.testing.expectEqualStrings("Trim a string to width", snippet(result.hits[0]));18131814    const ranked = try searchStored(1815        allocator,1816        root,1817        "truncate",1818        null,1819        2,1820        testingLimits().storage,1821    );1822    try std.testing.expectEqual(@as(i64, 3), ranked.total);1823    try std.testing.expectEqual(@as(usize, 2), ranked.hits.len);1824    try std.testing.expectEqualStrings("aaa.truncate", ranked.hits[0].name);1825    try std.testing.expectEqual(@as(i64, 1), ranked.hits[0].rank);1826    try std.testing.expectEqualStrings("zzz.truncate", ranked.hits[1].name);1827    try std.testing.expectEqual(@as(i64, 2), ranked.hits[1].rank);18281829    const filtered = try searchStored(1830        allocator,1831        root,1832        "truncate",1833        model.NodeType.class,1834        10,1835        testingLimits().storage,1836    );1837    try std.testing.expectEqual(@as(i64, 1), filtered.total);1838    try std.testing.expectEqualStrings("zzz.truncate", filtered.hits[0].name);1839}18401841fn syncStoredForTest(1842    allocator: std.mem.Allocator,1843    root: []const u8,1844    head: sql.Hash,1845) !SyncKind {1846    var opened = try storage.store.open(allocator, root, testingLimits().storage);1847    defer opened.close();1848    return try syncStoredFromDatabase(1849        allocator,1850        root,1851        &opened.database,1852        head,1853        head,1854        &.{},1855        &.{},1856        testingLimits().search,1857    );1858}18591860const TestSync = struct {1861    head: sql.Hash,1862    kind: SyncKind,1863};18641865fn replaceAndSyncForTest(1866    allocator: std.mem.Allocator,1867    graph: graph_mod.Graph,1868    root: []const u8,1869) !TestSync {1870    var opened = try storage.store.open(allocator, root, testingLimits().storage);1871    defer opened.close();1872    const previous_head = (try opened.database.connection.checkout()).head;1873    var replaced = try storage.graph.replaceObserved(1874        allocator,1875        &opened.database,1876        graph,1877    );1878    defer replaced.deinit(allocator);1879    return .{1880        .head = replaced.head,1881        .kind = try syncStoredFromDatabase(1882            allocator,1883            root,1884            &opened.database,1885            previous_head,1886            replaced.head,1887            replaced.changes.node_puts,1888            replaced.changes.node_deletes,1889            testingLimits().search,1890        ),1891    };1892}18931894fn replaceGraphForTest(allocator: std.mem.Allocator, graph: graph_mod.Graph, root: []const u8) !sql.Hash {1895    var opened = try storage.store.open(allocator, root, testingLimits().storage);1896    defer opened.close();1897    return try storage.graph.replace(allocator, &opened.database, graph);1898}18991900fn testingLimits() limits_mod.Limits {1901    return @import("root.zig").default_limits;1902}