From 8ac6db5662dd2db0f082e1651835f1db36e235f8 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Sat, 24 Oct 2026 11:57:35 -0300 Subject: Search converge 4/6: the disk engine, Grep and Find's listing on a worker (rg when there, else a sorted walk), generation-numbered batches, a debounce, a 2000-line cap and More, and the declarations parse off the loop --- src/Stream.zig | 1177 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1177 insertions(+) create mode 100644 src/Stream.zig (limited to 'src/Stream.zig') diff --git a/src/Stream.zig b/src/Stream.zig new file mode 100644 index 00000000..eb420b42 --- /dev/null +++ b/src/Stream.zig @@ -0,0 +1,1177 @@ +//! The disk engine: a query pane's Grep, and the file listing its Find +//! scores, run on a worker thread away from the loop (lifted from the +//! stream prototype). ripgrep when `rg` is on PATH (`rg --json --sort path +//! --fixed-strings --smart-case`, `rg --files --sort path`: it knows +//! .gitignore and is 5-15x faster on a real tree), else pardes's own sorted +//! walk with fs.zig's skips. Rows come back in batches, each stamped with +//! the generation it was started for; a new query bumps the generation and +//! cancels the worker, and the loop drops any batch that is not the live +//! generation's (the race test proves it). A typed Grep starts once the +//! typing pauses (`debounce_ns`); a worker stops at `soft_cap` hits and +//! waits there for `More`. Embedded in Pardes as `stream`: one search on +//! disk at a time, the query pane `target` names. +//! +//! Hosts with workers perform the `search` effect (host_io.Host.search): +//! `start` runs `work` on io.concurrent, posting through the shell's +//! inbox. A host without (a test, a board) runs it on the loop (`runHere`), +//! its cap a hard stop. +const Stream = @This(); + +const std = @import("std"); +const pardes = @import("pardes.zig"); +const config = @import("config.zig"); +const filesystem = @import("fs.zig"); +const look = @import("look.zig"); +const panes = @import("panes.zig"); +const syntax = @import("syntax.zig"); +const Pardes = pardes.Pardes; + +pub const Kind = enum { grep, files }; +pub const Engine = enum { rg, walk }; +pub const State = enum { idle, waiting, searching, capped, done, stopped, failed }; + +/// A keystroke's Grep starts when no other has come for this long. +pub const debounce_ns = 80 * std.time.ns_per_ms; +/// Hits (a Grep's lines, a listing's files) a worker sends before it waits +/// for More. +pub const soft_cap = 2000; +/// A listing of files keeps going this far before it waits: the names are +/// scored on the loop, the cap is for a runaway tree. +pub const files_cap = 200_000; +/// A worker's batch goes once its first row is this old, or it is this big; +/// the first batch goes at its first file with a hit. +const batch_ns = 16 * std.time.ns_per_ms; +const batch_bytes = 256 * 1024; +/// A bigger file is not searched. +const max_file_bytes = 16 << 20; + +/// What a worker sends: rows as fs.zig wrote them (`path:line:col-end +/// text`, a listing's `path`), relative to the search's directory. Owned by +/// the message until taken; the core copies what it keeps. +pub const Batch = struct { + gen: u32, + rows: []u8 = &.{}, + hits: u32 = 0, + /// Files with a hit in this batch's rows. + files: u32 = 0, + /// Files read since the last batch (rg: all of them, at its end). + scanned: u32 = 0, + /// Directories it might not open. + skipped: u32 = 0, + engine: Engine = .walk, + /// The worker waits at its soft cap until More. + capped: bool = false, + end: ?End = null, + /// The worker's own time, start to end (in the last batch). + took_ns: u64 = 0, + /// A parse's answer (`parseFor`): the declarations of pane `serial`'s + /// text at `revision`. + parsed: ?struct { serial: u32, revision: u32 } = null, + decls: []syntax.ContextDeclaration = &.{}, + + pub const End = enum { done, failed }; + + pub fn deinit(b: *const Batch, gpa: std.mem.Allocator) void { + gpa.free(b.rows); + gpa.free(b.decls); + } +}; + +/// A parse of a pane's text for its declarations, on a worker: the rows of +/// a `/` group under them, and Symbols lists them, once it is done. The +/// loop never parses a big text (a 1.2 MB file is seconds in Debug). +pub const ParseJob = struct { + gpa: std.mem.Allocator, + /// What its answer is made with: the shell's, which frees a batch. + out: std.mem.Allocator, + gen: u32, + serial: u32, + revision: u32, + path: []u8, + content: []u8, + /// Set when it is no longer wanted: the parse ends early. + stop: std.atomic.Value(bool) = .init(false), + + pub fn deinit(job: *ParseJob) void { + job.gpa.free(job.path); + job.gpa.free(job.content); + job.gpa.destroy(job); + } +}; + +const ParseTask = struct { job: *ParseJob, future: ?std.Io.Future(void) = null, io: ?std.Io = null }; + +/// Where a worker hands a batch: false when it was turned away (the inbox +/// closed, the wait for room canceled), and the worker stops. +pub const Sink = *const fn (ctx: ?*anyopaque, batch: Batch) bool; + +/// One search, the worker's: copied from the core when it starts. +pub const Job = struct { + gpa: std.mem.Allocator, + gen: u32, + kind: Kind, + pattern: []u8, + /// Rows name files relative to this, the query pane's directory, which + /// is also the one root searched. + base: []u8, + /// Forced (tests, PARDES_STREAM_ENGINE); else rg when there is one. + engine: ?Engine, + /// Hits it may send before it waits; More raises it and wakes it. Run + /// on the loop (no worker) it is a hard stop. + cap: std.atomic.Value(u32) = .init(soft_cap), + waits: bool = true, + + pub fn deinit(job: *Job) void { + const gpa = job.gpa; + gpa.free(job.pattern); + gpa.free(job.base); + gpa.destroy(job); + } +}; + +const Task = struct { job: *Job, future: std.Io.Future(void), io: std.Io }; + +gen: u32 = 0, +state: State = .idle, +kind: Kind = .grep, +/// The query pane the rows are for, by serial. +target: u32 = 0, +pattern: std.ArrayList(u8) = .empty, +dir: std.ArrayList(u8) = .empty, +/// A typed query's start, once the pause runs out (step). +due_ns: ?u64 = null, +task: ?Task = null, +/// Forced engine (tests); null, rg when it runs. +engine: ?Engine = null, +used: Engine = .walk, +hits: u32 = 0, +files: u32 = 0, +scanned: u32 = 0, +skipped: u32 = 0, +/// Stale batches dropped (the race test counts them). +dropped: usize = 0, +started_ns: u64 = 0, +first_ns: ?u64 = null, +finished_ns: u64 = 0, +worker_ns: u64 = 0, +/// The parse running or about to (one at a time), its generation, and the +/// one asked for while it ran (pane serial and revision), started after it. +parse: ?ParseTask = null, +parse_gen: u32 = 0, +parse_next: ?struct { serial: u32, revision: u32 } = null, +/// What the last parse cost the worker. +parse_ns: u64 = 0, + +pub fn deinit(s: *Stream, gpa: std.mem.Allocator) void { + s.cancelTask(); + s.cancelParse(); + s.pattern.deinit(gpa); + s.dir.deinit(gpa); +} + +/// The parse's worker told to stop and joined: short, its progress +/// callback hears the flag. +pub fn cancelParse(s: *Stream) void { + const t = s.parse orelse return; + s.parse = null; + t.job.stop.store(true, .release); + if (t.future) |f| { + pardes.turn.yield(); + var future = f; + future.cancel(t.io.?); + pardes.turn.back(); + } + t.job.deinit(); +} + +/// Pane `id`'s declarations asked for, as its text is now, unless a parse of +/// that text is already on its way. With workers, on one; without (a test), +/// here only for a small text, else not at all (the rows stay ungrouped). +pub fn parseFor(p: *Pardes, id: usize) void { + const s = &p.stream; + const pane = p.panes[id] orelse return; + const f = pane.file orelse return; + if (!syntax.supportsPath(f.path) or f.content.len == 0) return; + if (s.parse) |t| { + if (t.job.serial == pane.serial and t.job.revision == f.revision) return; + // A parse of a text that has changed since: told to stop; this one + // after it. + t.job.stop.store(true, .release); + s.parse_next = .{ .serial = pane.serial, .revision = f.revision }; + return; + } + const workers = p.host.vtable.search != null and !p.fs.serving; + if (!workers and f.content.len > 64 << 10) return; + const job = p.gpa.create(ParseJob) catch return; + const path = p.gpa.dupe(u8, f.path) catch { + p.gpa.destroy(job); + return; + }; + const content = p.gpa.dupe(u8, f.content) catch { + p.gpa.free(path); + p.gpa.destroy(job); + return; + }; + s.gen +%= 1; + s.parse_gen = s.gen; + job.* = .{ .gpa = p.gpa, .out = p.gpa, .gen = s.parse_gen, .serial = pane.serial, .revision = f.revision, .path = path, .content = content }; + s.parse = .{ .job = job }; + if (workers) return p.emit(.{ .search = .{ .gen = s.parse_gen } }); + // Here and now: a small text, a host with no workers. + var got: Collect = .{ .gpa = p.gpa }; + defer got.batches.deinit(p.gpa); + parseWork(std.Io.Threaded.global_single_threaded.io(), job, &got, Collect.take); + for (got.batches.items) |*b| { + receive(p, b); + b.deinit(p.gpa); + } +} + +fn parseWork(io: std.Io, job: *ParseJob, ctx: ?*anyopaque, sink: Sink) void { + const began = std.Io.Clock.awake.now(io); + const decls: []syntax.ContextDeclaration = syntax.declarationsApart(job.out, job.path, job.content, &job.stop) catch @constCast(&[_]syntax.ContextDeclaration{}); + const took: u64 = @intCast(@max(0, began.durationTo(std.Io.Clock.awake.now(io)).nanoseconds)); + _ = sink(ctx, .{ .gen = job.gen, .decls = decls, .parsed = .{ .serial = job.serial, .revision = job.revision }, .end = .done, .took_ns = took }); +} + +fn now() u64 { + if (comptime !filesystem.platform_has_fs) return 0; + const t = std.Io.Clock.awake.now(std.Io.Threaded.global_single_threaded.io()); + return @intCast(@max(0, t.nanoseconds)); +} + +/// Joins the worker, if one runs: a cancel interrupts its waits and reads, +/// so this is short. The turn goes out for it, as for any blocking call: +/// the worker may be reading through a mount of this very session. +pub fn cancelTask(s: *Stream) void { + const t = s.task orelse return; + s.task = null; + pardes.turn.yield(); + var future = t.future; + future.cancel(t.io); + pardes.turn.back(); + t.job.deinit(); +} + +/// A new question for query pane `target`: a Grep of `pattern`, or the +/// listing of the files (`.files`), under `dir`. The generation before it +/// is over (its worker canceled, its batches dropped when they come); +/// `typed`, it starts once the typing pauses, else at the next step. +pub fn query(p: *Pardes, target: u32, kind: Kind, pattern: []const u8, dir: []const u8, how: enum { typed, now }) void { + const s = &p.stream; + s.cancelTask(); + s.gen +%= 1; + s.kind = kind; + s.target = target; + s.pattern.clearRetainingCapacity(); + s.pattern.appendSlice(p.gpa, pattern) catch return; + s.dir.clearRetainingCapacity(); + s.dir.appendSlice(p.gpa, dir) catch return; + s.hits = 0; + s.files = 0; + s.scanned = 0; + s.skipped = 0; + s.first_ns = null; + s.state = .waiting; + s.due_ns = if (how == .typed) p.now_ns + debounce_ns else p.now_ns; +} + +/// Over: the worker canceled, nothing more of it lands. +pub fn stop(s: *Stream) bool { + if (s.state != .waiting and s.state != .searching and s.state != .capped) return false; + s.cancelTask(); + s.due_ns = null; + s.gen +%= 1; + s.state = .stopped; + s.finished_ns = now(); + return true; +} + +/// More: a worker waiting at its cap goes on for another `soft_cap` hits. +pub fn more(s: *Stream) bool { + if (s.state != .capped) return false; + const t = s.task orelse return false; + _ = t.job.cap.fetchAdd(soft_cap, .release); + t.io.futexWake(u32, &t.job.cap.raw, 1); + s.state = .searching; + return true; +} + +/// The `More` word: the query pane's disk search past its cap. +pub fn moreFor(p: *Pardes, id: usize) bool { + if (!p.stream.more()) return false; + if (p.panes[id]) |pane| if (pane.query) |q| { + q.capped = false; + }; + if (p.paneBySerial(p.stream.target)) |tid| if (p.panes[tid].?.query) |q| { + q.capped = false; + }; + return true; +} + +/// Whether query pane `serial`'s rows are still coming. +pub fn busyFor(s: *const Stream, serial: u32) bool { + return s.target == serial and (s.state == .waiting or s.state == .searching); +} + +/// On each tick: a query whose pause ran out starts, on a worker where the +/// host has one, else here and now. +pub fn step(p: *Pardes) void { + const s = &p.stream; + const due = s.due_ns orelse return; + if (p.now_ns < due) return; + s.due_ns = null; + s.state = .searching; + s.started_ns = now(); + // A script's write (whose answer says whether it found anything) and a + // host with no workers: done before this returns. + if (p.host.vtable.search != null and !p.fs.serving) p.emit(.{ .search = .{ .gen = s.gen } }) else runHere(p, s.gen); +} + +/// When the core next needs a tick for the stream: the end of the pause. +pub fn wake(s: *const Stream, next_frame: u64) ?u64 { + const due = s.due_ns orelse return null; + return @max(due, next_frame); +} + +/// Start generation `gen` on a worker that sends to `sink` (a shell's +/// inbox). Called by the shell for the `search` effect, on the loop. +pub fn start(io: std.Io, gpa: std.mem.Allocator, p: *Pardes, gen: u32, ctx: ?*anyopaque, sink: Sink) void { + const s = &p.stream; + // A parse's generation: its own task. + if (s.parse) |*t| if (gen == s.parse_gen and t.job.gen == gen and t.future == null) { + t.job.out = gpa; + t.future = io.concurrent(parseWork, .{ io, t.job, ctx, sink }) catch { + const job = t.job; + s.parse = null; + job.deinit(); + return; + }; + t.io = io; + return; + }; + if (gen != s.gen or s.state != .searching) return; + s.cancelTask(); + const job = makeJob(gpa, s) catch |err| { + s.state = .failed; + return p.reportError(p.active, "search", err); + }; + const future = io.concurrent(work, .{ io, job, ctx, sink }) catch { + // No worker to be had: it runs here, on the loop. + job.deinit(); + return runHere(p, gen); + }; + s.task = .{ .job = job, .future = future, .io = io }; +} + +fn makeJob(gpa: std.mem.Allocator, s: *const Stream) !*Job { + const job = try gpa.create(Job); + errdefer gpa.destroy(job); + const pattern = try gpa.dupe(u8, s.pattern.items); + errdefer gpa.free(pattern); + const base = try gpa.dupe(u8, s.dir.items); + job.* = .{ .gpa = gpa, .gen = s.gen, .kind = s.kind, .pattern = pattern, .base = base, .engine = s.engine }; + if (s.kind == .files) job.cap = .init(files_cap); + return job; +} + +/// A host with no workers (a test's, the fallback when none can be had): +/// the whole search on the loop, the turn out for it, its batches taken in +/// as a worker's would be. Its cap is a hard stop. +pub fn runHere(p: *Pardes, gen: u32) void { + if (comptime !filesystem.platform_has_fs) { + p.stream.state = .failed; + return; + } + const s = &p.stream; + if (gen != s.gen or s.state != .searching) return; + const job = makeJob(p.gpa, s) catch |err| { + s.state = .failed; + return p.reportError(p.active, "search", err); + }; + defer job.deinit(); + job.waits = false; + var got: Collect = .{ .gpa = p.gpa }; + defer got.batches.deinit(p.gpa); + { + pardes.turn.yield(); + defer pardes.turn.back(); + work(std.Io.Threaded.global_single_threaded.io(), job, &got, Collect.take); + } + for (got.batches.items) |*b| { + receive(p, b); + b.deinit(p.gpa); + } +} + +const Collect = struct { + gpa: std.mem.Allocator, + batches: std.ArrayList(Batch) = .empty, + + fn take(ctx: ?*anyopaque, batch: Batch) bool { + const c: *Collect = @ptrCast(@alignCast(ctx.?)); + c.batches.append(c.gpa, batch) catch { + batch.deinit(c.gpa); + return false; + }; + return true; + } +}; + +/// A batch from a worker (`Event.search`), borrowed: the live generation's +/// rows go to its query pane (a Grep's lines, a listing's names); any other +/// generation's are dropped whole. +pub fn receive(p: *Pardes, b: *const Batch) void { + const s = &p.stream; + if (b.parsed) |parsed| return receiveParse(p, b, parsed.serial, parsed.revision); + if (b.gen != s.gen or (s.state != .searching and s.state != .capped)) { + s.dropped += 1; + return; + } + s.used = b.engine; + s.hits += b.hits; + s.files += b.files; + s.scanned += b.scanned; + s.skipped += b.skipped; + if (s.first_ns == null and b.rows.len > 0) s.first_ns = now(); + if (b.capped) s.state = .capped; + if (b.end) |end| { + s.worker_ns = b.took_ns; + s.state = if (end == .failed) .failed else .done; + s.finished_ns = now(); + // It sent its last: its join is a return away. + if (s.task) |t| { + s.task = null; + pardes.turn.yield(); + var future = t.future; + future.await(t.io); + pardes.turn.back(); + t.job.deinit(); + } + } + p.needs_frame = true; + const id = p.paneBySerial(s.target) orelse return; + const q = p.panes[id].?.query orelse return; + q.capped = s.state == .capped; + panes.Query.take(p, q, s.kind, b.rows); +} + +/// A parse's answer: its task joined; the declarations kept as the pane's +/// (File.State.context_declarations, for its revision) when its text is +/// still what was parsed; the query panes of that text told; and a parse +/// asked for while it ran started. +fn receiveParse(p: *Pardes, b: *const Batch, serial: u32, revision: u32) void { + const s = &p.stream; + if (s.parse) |t| if (t.job.gen == b.gen) { + s.parse = null; + if (t.future) |f| { + pardes.turn.yield(); + var future = f; + future.await(t.io.?); + pardes.turn.back(); + } + t.job.deinit(); + }; + s.parse_ns = b.took_ns; + if (p.paneBySerial(serial)) |id| if (p.panes[id].?.file) |*f| if (f.revision == revision and b.decls.len > 0) { + if (p.tree_sitter_gpa.dupe(syntax.ContextDeclaration, b.decls)) |copy| { + if (f.context_declarations.len > 0) p.tree_sitter_gpa.free(f.context_declarations); + f.context_declarations = copy; + f.context_revision = revision; + panes.Query.declsArrived(p, serial); + } else |_| {} + }; + p.needs_frame = true; + if (s.parse_next) |next| { + s.parse_next = null; + if (p.paneBySerial(next.serial)) |id| parseFor(p, id); + } +} + +// ---- the worker ---- + +const Worker = struct { + io: std.Io, + gpa: std.mem.Allocator, + job: *Job, + ctx: ?*anyopaque, + sink: Sink, + engine: Engine = .walk, + exact: bool, + rows: std.ArrayList(u8) = .empty, + hits: u32 = 0, + files: u32 = 0, + scanned: u32 = 0, + skipped: u32 = 0, + total: u32 = 0, + sent: bool = false, + batch_began: ?std.Io.Timestamp = null, + began: std.Io.Timestamp, + /// One read buffer for every file: grown to the biggest, never 0xAA'd per file. + buf: std.ArrayList(u8) = .empty, + + fn deinit(w: *Worker) void { + w.rows.deinit(w.gpa); + w.buf.deinit(w.gpa); + } + + fn send(w: *Worker, end: ?Batch.End, capped: bool) error{ Refused, OutOfMemory }!void { + const rows = try w.rows.toOwnedSlice(w.gpa); + const batch: Batch = .{ + .gen = w.job.gen, + .rows = rows, + .hits = w.hits, + .files = w.files, + .scanned = w.scanned, + .skipped = w.skipped, + .engine = w.engine, + .capped = capped, + .end = end, + .took_ns = if (end != null) @intCast(@max(0, w.began.durationTo(std.Io.Clock.awake.now(w.io)).nanoseconds)) else 0, + }; + w.hits = 0; + w.files = 0; + w.scanned = 0; + w.skipped = 0; + w.sent = true; + w.batch_began = null; + if (!w.sink(w.ctx, batch)) return error.Refused; + } + + /// After a file with hits: the first batch goes at once (what the user + /// sees first), the others once old or big enough. + fn maybeSend(w: *Worker) !void { + if (w.rows.items.len == 0) return; + const began = w.batch_began orelse { + w.batch_began = std.Io.Clock.awake.now(w.io); + if (!w.sent) try w.send(null, false); + return; + }; + const age = began.durationTo(std.Io.Clock.awake.now(w.io)).nanoseconds; + if (age >= batch_ns or w.rows.items.len >= batch_bytes) try w.send(null, false); + } + + /// At the cap, what is gathered goes, and the worker waits for More (a + /// cancel ends the wait); on the loop it is the end. + fn checkCap(w: *Worker) !bool { + var cap = w.job.cap.load(.acquire); + if (w.total < cap) return false; + if (!w.job.waits) return true; + try w.send(null, true); + while (w.total >= cap) { + try w.io.futexWait(u32, &w.job.cap.raw, cap); + cap = w.job.cap.load(.acquire); + } + return false; + } + + /// Smart case: a pattern with a capital matches exactly, else in any case. + fn find(w: *const Worker, hay: []const u8) ?usize { + return if (w.exact) std.mem.indexOf(u8, hay, w.job.pattern) else std.ascii.findIgnoreCase(hay, w.job.pattern); + } + + fn grepText(w: *Worker, path: []const u8, text: []const u8) !u32 { + var found: u32 = 0; + var line: usize = 0; + var it = std.mem.splitScalar(u8, text, '\n'); + while (it.next()) |raw| { + line += 1; + if (w.total >= w.job.cap.load(.acquire)) break; + const at = w.find(raw) orelse continue; + try w.row(path, line, at, at + w.job.pattern.len, raw); + found += 1; + } + return found; + } + + fn row(w: *Worker, path: []const u8, line: usize, from: usize, end: usize, raw: []const u8) !void { + const ln = std.mem.trimEnd(u8, raw, " \t\r\n"); + var cut = @min(ln.len, 400); + while (cut > 0 and cut < ln.len and ln[cut] & 0xc0 == 0x80) cut -= 1; + try w.rows.print(w.gpa, "{s}:{d}:{d}{c}{d} {s}\n", .{ path, line, from + 1, config.range_sep, end, ln[0..cut] }); + w.hits += 1; + w.total += 1; + } + + /// A listing's file: its name, relative to the base. + fn file(w: *Worker, path: []const u8) !bool { + try w.rows.print(w.gpa, "{s}\n", .{path}); + w.hits += 1; + w.total += 1; + w.files += 1; + try w.maybeSend(); + return w.checkCap(); + } + + /// The name a row gives `abs`: under the base, relative to it. + fn shown(w: *const Worker, abs: []const u8) []const u8 { + const base = std.mem.trimEnd(u8, w.job.base, "/"); + if (abs.len > base.len + 1 and std.mem.startsWith(u8, abs, base) and abs[base.len] == '/') return abs[base.len + 1 ..]; + if (std.mem.startsWith(u8, abs, "./")) return abs[2..]; + return abs; + } + + // ---- our own walk: sorted, depth first, fs.zig's skips ---- + + fn walk(w: *Worker) !void { + var dir = std.Io.Dir.cwd().openDir(w.io, w.job.base, .{ .iterate = true }) catch |err| switch (err) { + error.Canceled => return error.Canceled, + else => return, + }; + defer dir.close(w.io); + _ = try w.walkDir(dir, "", 0); + } + + /// Whether the cap ended it (on the loop). + fn walkDir(w: *Worker, dir: std.Io.Dir, prefix: []const u8, depth: usize) anyerror!bool { + try w.io.checkCancel(); + var arena: std.heap.ArenaAllocator = .init(w.gpa); + defer arena.deinit(); + const a = arena.allocator(); + const Entry = struct { name: []const u8, kind: std.Io.File.Kind }; + var entries: std.ArrayList(Entry) = .empty; + var it = dir.iterate(); + while (true) { + const e = it.next(w.io) catch |err| switch (err) { + error.Canceled => return error.Canceled, + else => { + w.skipped += 1; + break; + }, + } orelse break; + try entries.append(a, .{ .name = try a.dupe(u8, e.name), .kind = e.kind }); + } + std.mem.sort(Entry, entries.items, {}, struct { + fn lt(_: void, x: Entry, y: Entry) bool { + return std.mem.lessThan(u8, x.name, y.name); + } + }.lt); + for (entries.items) |e| { + const path = if (prefix.len == 0) e.name else try std.fmt.allocPrint(a, "{s}/{s}", .{ prefix, e.name }); + switch (e.kind) { + .directory => { + if (depth + 1 >= filesystem.WalkNotes.max_depth or e.name[0] == '.') continue; + if (for (filesystem.find_skip) |skip| { + if (std.mem.eql(u8, e.name, skip)) break true; + } else false) continue; + var sub = dir.openDir(w.io, e.name, .{ .iterate = true }) catch |err| switch (err) { + error.Canceled => return error.Canceled, + else => { + w.skipped += 1; + continue; + }, + }; + defer sub.close(w.io); + if (try w.walkDir(sub, path, depth + 1)) return true; + }, + .file => switch (w.job.kind) { + .grep => if (try w.grepFile(dir, e.name, path)) return true, + .files => if (try w.file(path)) return true, + }, + else => {}, + } + } + return false; + } + + fn grepFile(w: *Worker, dir: std.Io.Dir, name: []const u8, path: []const u8) !bool { + const f = dir.openFile(w.io, name, .{}) catch |err| switch (err) { + error.Canceled => return error.Canceled, + else => return false, + }; + defer f.close(w.io); + const len = f.length(w.io) catch |err| switch (err) { + error.Canceled => return error.Canceled, + else => return false, + }; + // ponytail: a file past 16 MiB is passed over unsaid; a chunked + // read, as fs.grep's, would search it. + if (len > max_file_bytes) return false; + try w.buf.resize(w.gpa, @intCast(len)); + const n = f.readPositionalAll(w.io, w.buf.items, 0) catch |err| switch (err) { + error.Canceled => return error.Canceled, + else => return false, + }; + const text = w.buf.items[0..n]; + w.scanned += 1; + if (std.mem.indexOfScalar(u8, text[0..@min(text.len, 1024)], 0) != null) return false; + const found = try w.grepText(path, text); + if (found == 0) return false; + w.files += 1; + try w.maybeSend(); + return w.checkCap(); + } + + // ---- ripgrep: a child on the worker, parsed, never shown ---- + + /// error.NoRipgrep when there is none to run: the walk does it. + fn ripgrep(w: *Worker) !void { + var argv: std.ArrayList([]const u8) = .empty; + defer argv.deinit(w.gpa); + switch (w.job.kind) { + .grep => { + try argv.appendSlice(w.gpa, &.{ "rg", "--json", "--sort", "path", "--fixed-strings", "--smart-case", "--no-messages", "--" }); + try argv.append(w.gpa, w.job.pattern); + }, + .files => try argv.appendSlice(w.gpa, &.{ "rg", "--files", "--sort", "path", "--no-messages" }), + } + // As selection_pipe's children: this thread's mask is the child's. + const none = std.posix.sigemptyset(); + var kept: std.posix.sigset_t = undefined; + std.posix.sigprocmask(std.posix.SIG.SETMASK, &none, &kept); + var child = std.process.spawn(w.io, .{ + .argv = argv.items, + .cwd = if (w.job.base.len == 0) .inherit else .{ .path = w.job.base }, + .stdin = .ignore, + .stdout = .pipe, + .stderr = .ignore, + }) catch |err| { + std.posix.sigprocmask(std.posix.SIG.SETMASK, &kept, null); + return if (err == error.Canceled) error.Canceled else error.NoRipgrep; + }; + std.posix.sigprocmask(std.posix.SIG.SETMASK, &kept, null); + w.engine = .rg; + // Canceled, capped on the loop, failed: it is killed and reaped. + defer if (child.id != null) child.kill(w.io); + var line: std.ArrayList(u8) = .empty; + defer line.deinit(w.gpa); + var json_arena: std.heap.ArenaAllocator = .init(w.gpa); + defer json_arena.deinit(); + var file_hits: u32 = 0; + var file_path: std.ArrayList(u8) = .empty; + defer file_path.deinit(w.gpa); + // Cut at the cap (on the loop), rg is left to the kill. + var cut = false; + var chunk: [64 * 1024]u8 = undefined; + read: while (true) { + const n = child.stdout.?.readStreaming(w.io, &.{&chunk}) catch |err| switch (err) { + error.EndOfStream => break, + error.Canceled => return error.Canceled, + else => return error.ReadFailed, + }; + if (n == 0) break; + var at: usize = 0; + while (std.mem.indexOfScalarPos(u8, chunk[0..n], at, '\n')) |nl| { + try line.appendSlice(w.gpa, chunk[at..nl]); + at = nl + 1; + defer line.clearRetainingCapacity(); + if (w.job.kind == .files) { + // a dot-file is passed over, as the walk passes over + // dot-directories + if (std.mem.startsWith(u8, std.fs.path.basename(line.items), ".")) continue; + w.scanned += 1; + if (try w.file(w.shown(line.items))) { + cut = true; + break :read; + } + continue; + } + _ = json_arena.reset(.retain_capacity); + const value = std.json.parseFromSliceLeaky(std.json.Value, json_arena.allocator(), line.items, .{}) catch continue; + const obj = if (value == .object) value.object else continue; + const kind = (obj.get("type") orelse continue); + if (kind != .string) continue; + const data = if (obj.get("data")) |d| (if (d == .object) d.object else continue) else continue; + if (std.mem.eql(u8, kind.string, "begin")) { + file_hits = 0; + file_path.clearRetainingCapacity(); + const text = jsonText(data.get("path")) orelse continue; + try file_path.appendSlice(w.gpa, w.shown(text)); + } else if (std.mem.eql(u8, kind.string, "match")) { + if (file_path.items.len == 0 or w.total >= w.job.cap.load(.acquire)) continue; + const text = jsonText(data.get("lines")) orelse continue; + const number = data.get("line_number") orelse continue; + if (number != .integer) continue; + var from: usize = 0; + var end: usize = w.job.pattern.len; + if (data.get("submatches")) |subs| if (subs == .array and subs.array.items.len > 0 and subs.array.items[0] == .object) { + const first = subs.array.items[0].object; + if (first.get("start")) |v| if (v == .integer) { + from = @intCast(v.integer); + }; + if (first.get("end")) |v| if (v == .integer) { + end = @intCast(v.integer); + }; + }; + try w.row(file_path.items, @intCast(number.integer), from, end, text); + file_hits += 1; + } else if (std.mem.eql(u8, kind.string, "end")) { + if (file_hits == 0) continue; + w.files += 1; + file_hits = 0; + try w.maybeSend(); + // At the cap rg is left blocked on its full pipe: its + // own backpressure, until More or a cancel. + if (try w.checkCap()) { + cut = true; + break :read; + } + } else if (std.mem.eql(u8, kind.string, "summary")) { + if (data.get("stats")) |stats| if (stats == .object) if (stats.object.get("searches")) |v| if (v == .integer) { + w.scanned = @intCast(v.integer); + }; + } + } + try line.appendSlice(w.gpa, chunk[at..n]); + } + if (!cut and child.id != null) { + _ = child.wait(w.io) catch |err| if (err == error.Canceled) return error.Canceled; + child.id = null; + } + } +}; + +/// rg's `{"text": …}` (a name or line that is not UTF-8 comes as bytes, +/// and is passed over). +fn jsonText(v: ?std.json.Value) ?[]const u8 { + const o = v orelse return null; + if (o != .object) return null; + const t = o.object.get("text") orelse return null; + return if (t == .string) t.string else null; +} + +fn work(io: std.Io, job: *Job, ctx: ?*anyopaque, sink: Sink) void { + var exact = false; + for (job.pattern) |c| exact = exact or std.ascii.isUpper(c); + var w: Worker = .{ .io = io, .gpa = job.gpa, .job = job, .ctx = ctx, .sink = sink, .exact = exact, .began = std.Io.Clock.awake.now(io) }; + defer w.deinit(); + const forced: ?Engine = job.engine orelse if (std.c.getenv("PARDES_STREAM_ENGINE")) |v| + std.meta.stringToEnum(Engine, std.mem.span(v)) + else + null; + const ran = if ((forced orelse .rg) == .rg) w.ripgrep() else error.NoRipgrep; + ran catch |err| switch (err) { + error.Canceled, error.Refused => return, + error.NoRipgrep => { + w.engine = .walk; + w.walk() catch |walk_err| switch (walk_err) { + error.Canceled, error.Refused => return, + else => { + w.send(.failed, false) catch {}; + return; + }, + }; + }, + else => { + w.send(.failed, false) catch {}; + return; + }, + }; + w.send(.done, false) catch {}; +} + +// ---- tests ---- + +const host_io = @import("host_io.zig"); +const testing = std.testing; + +/// The shell's half, in a test: perform the `search` effect on a real +/// worker, hand what it posts to the core. +const TestShell = struct { + q: host_io.Inbox, + + fn init() TestShell { + return .{ .q = .{ .gpa = testing.allocator, .lsp_allocator = testing.allocator, .io = testing.io } }; + } + + const vtable: pardes.Host.VTable = .{ .search = struct { + fn f(_: ?*anyopaque, _: u32) void {} + }.f }; + + fn attach(p: *Pardes) void { + p.host = .{ .vtable = &vtable }; + } + + fn pump(t: *TestShell, p: *Pardes) void { + while (p.nextEffect()) |e| switch (e) { + .search => |s| start(testing.io, testing.allocator, p, s.gen, &t.q, host_io.Inbox.pushSearch), + else => {}, + }; + var batch: host_io.Inbox.Batch = .{}; + t.q.takeInto(&batch); + for (batch.slice()) |m| switch (m) { + .search => |b| { + p.update(.{ .search = b }); + b.deinit(testing.allocator); + }, + else => m.deinit(testing.allocator, testing.allocator), + }; + } + + /// Pump until the search is over (or `limit_ms` passes: a failure). + fn finish(t: *TestShell, p: *Pardes, limit_ms: i64) !void { + const until = std.Io.Clock.awake.now(testing.io).toMilliseconds() + limit_ms; + while (p.stream.state == .searching or p.stream.state == .waiting) { + if (std.Io.Clock.awake.now(testing.io).toMilliseconds() > until) return error.Timeout; + if (p.stream.state == .waiting) p.update(.tick); + t.pump(p); + testing.io.sleep(.fromMicroseconds(200), .awake) catch {}; + } + } +}; + +/// A worker that never heard of the cancel: it pushes rows of a stale +/// generation for as long as the live one streams. +const Rogue = struct { + q: *host_io.Inbox, + gen: u32, + stop: std.atomic.Value(bool) = .init(false), + done: std.atomic.Value(bool) = .init(false), + pushed: usize = 0, + + fn run(r: *Rogue) void { + defer r.done.store(true, .release); + while (!r.stop.load(.acquire) and r.pushed < 200) { + const rows = testing.allocator.dupe(u8, "d00/f000.txt:1:3-8 stale stale\n") catch return; + if (!host_io.Inbox.pushSearch(r.q, .{ .gen = r.gen, .rows = rows, .hits = 1, .files = 1 })) return; + r.pushed += 1; + std.Thread.yield() catch {}; + } + } +}; + +test "Stream: a stale generation's rows never land in the query pane, however two generations race (walk and rg)" { + if (comptime !filesystem.platform_has_fs) return; + var tmp = testing.tmpDir(.{}); + defer tmp.cleanup(); + var root_buf: [4096]u8 = undefined; + const files = 120; + var name_buf: [64]u8 = undefined; + for (0..files) |i| { + const name = try std.fmt.bufPrint(&name_buf, "d{d:0>2}/f{d:0>3}.txt", .{ i / 10, i }); + try tmp.dir.createDirPath(testing.io, std.fs.path.dirname(name).?); + try tmp.dir.writeFile(testing.io, .{ .sub_path = name, .data = "a needle line\nsome hay here\nneedle again\nhay hay\nmore hay\n" }); + } + const root = root_buf[0..try tmp.dir.realPath(testing.io, &root_buf)]; + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 120, .rows = 40 }); + defer p.deinit(); + const pane = try p.setTestFile("x\n"); + p.gpa.free(pane.file.?.path); + pane.file.?.path = try std.fs.path.join(p.gpa, &.{ root, "main.txt" }); + p.advance(1); + var shell: TestShell = .init(); + TestShell.attach(p); + defer { + p.stream.cancelTask(); + shell.q.deinit(); + } + // The query pane the rows are for: a Grep's. + panes.Query.open(p, 0, .grep, "", false); + const qid = for (p.panes, 0..) |slot, i| { + if (slot) |qp| if (qp.query != null) break i; + } else return error.NoQueryPane; + const qp = p.panes[qid].?; + const q = qp.query.?; + var dropped_total: usize = 0; + for ([_]Engine{ .walk, .rg }) |engine| { + p.stream.engine = engine; + for (0..12) |round| { + // A starts and runs a little (0, 1 or 2 pumps: its batches in + // flight, queued, or taken in), then B replaces it, typed (its + // pause run out on the clock) or at once. + const a = if (round % 2 == 0) "needle" else "hay"; + const b = if (round % 2 == 0) "hay" else "needle"; + q.found.clearRetainingCapacity(); + q.found_bytes.clearRetainingCapacity(); + query(p, qp.serial, .grep, a, root, .now); + p.update(.tick); + for (0..round % 3) |_| shell.pump(p); + var rogue: Rogue = .{ .q = &shell.q, .gen = p.stream.gen }; + q.found.clearRetainingCapacity(); + q.found_bytes.clearRetainingCapacity(); + if (round % 4 == 3) { + query(p, qp.serial, .grep, b, root, .typed); + try testing.expectEqual(State.waiting, p.stream.state); + p.advance(p.now_ns + debounce_ns + std.time.ns_per_ms); + } else query(p, qp.serial, .grep, b, root, .now); + try testing.expect(p.stream.gen != rogue.gen); + const thread = try std.Thread.spawn(.{}, Rogue.run, .{&rogue}); + const finished = shell.finish(p, 20_000); + // It may be waiting for room: the queue is taken until it ends. + rogue.stop.store(true, .release); + while (!rogue.done.load(.acquire)) shell.pump(p); + thread.join(); + shell.pump(p); // whatever it pushed last + try finished; + try testing.expectEqual(State.done, p.stream.state); + // b's lines, every one, and not one of a's nor the rogue's. + const per_file: usize = if (std.mem.eql(u8, b, "hay")) 3 else 2; + try testing.expectEqual(files * per_file, q.found.items.len); + try testing.expect(std.mem.indexOf(u8, q.found_bytes.items, "stale") == null); + for (q.found.items) |fd| { + const code = q.found_bytes.items[fd.code..][0..fd.code_len]; + try testing.expect(std.ascii.findIgnoreCase(code, b) != null); + } + if (engine == .rg and p.stream.used != .rg) return; // no rg here: the walk was the test + dropped_total += p.stream.dropped; + p.stream.dropped = 0; + } + } + try testing.expect(dropped_total > 0); +} + +test "Stream: the listing of files for Find on a worker, a cap of hits stops the walk on the loop" { + if (comptime !filesystem.platform_has_fs) return; + var tmp = testing.tmpDir(.{}); + defer tmp.cleanup(); + var root_buf: [4096]u8 = undefined; + try tmp.dir.createDirPath(testing.io, "src"); + try tmp.dir.createDirPath(testing.io, ".git"); + for ([_][]const u8{ "src/a.zig", "src/b.zig", "notes.md", ".git/config" }) |name| + try tmp.dir.writeFile(testing.io, .{ .sub_path = name, .data = "needle\n" }); + const root = root_buf[0..try tmp.dir.realPath(testing.io, &root_buf)]; + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 120, .rows = 40 }); + defer p.deinit(); + const pane = try p.setTestFile("x\n"); + p.gpa.free(pane.file.?.path); + pane.file.?.path = try std.fs.path.join(p.gpa, &.{ root, "main.txt" }); + p.advance(1); + p.stream.engine = .walk; + // No host workers: the listing runs on the loop at the next tick. + panes.Query.open(p, 0, .find, "", false); + p.update(.tick); + p.update(.tick); + const qid = for (p.panes, 0..) |slot, i| { + if (slot) |qp| if (qp.query != null) break i; + } else return error.NoQueryPane; + const q = p.panes[qid].?.query.?; + // the three files, not the dot-directory's + try testing.expectEqual(@as(usize, 3), q.names.cands.items.len); + try testing.expectEqual(State.done, p.stream.state); +} + +test "Stream: a big text's declarations are parsed on a worker, never the loop, and the rows of its / regroup under them" { + if (comptime !filesystem.platform_has_fs) return; + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 120, .rows = 40 }); + defer p.deinit(); + var text: std.ArrayList(u8) = .empty; + defer text.deinit(testing.allocator); + for (0..4000) |i| try text.print(testing.allocator, "fn f{d}() void {{\n _ = needle;\n}}\n", .{i}); + const pane = try p.setTestFile(text.items); + p.gpa.free(pane.file.?.path); + pane.file.?.path = try p.gpa.dupe(u8, "/tmp/big.zig"); + p.advance(1); + var shell: TestShell = .init(); + TestShell.attach(p); + defer { + p.stream.cancelTask(); + p.stream.cancelParse(); + shell.q.deinit(); + } + for ("/needle") |c| p.update(.{ .key = .{ .cp = c, .text = &[_]u8{c} } }); + const qid = for (p.panes, 0..) |slot, i| { + if (slot) |qp| if (qp.query != null) break i; + } else return error.NoQueryPane; + const qp = p.panes[qid].?; + // Not grouped yet: no parse on the loop; one asked of the worker. + try testing.expect(p.stream.parse != null); + try testing.expect(std.mem.indexOf(u8, qp.file.?.content, "fn f") == null); + const until = std.Io.Clock.awake.now(testing.io).toMilliseconds() + 60_000; + while (pane.file.?.context_revision == null or pane.file.?.context_revision.? != pane.file.?.revision) { + if (std.Io.Clock.awake.now(testing.io).toMilliseconds() > until) return error.Timeout; + shell.pump(p); + p.update(.tick); + testing.io.sleep(.fromMilliseconds(2), .awake) catch {}; + } + p.update(.tick); + // Now under their declarations: `fn fN() void {` headers. + try testing.expect(std.mem.indexOf(u8, qp.file.?.content, "fn f") != null); + try testing.expect(p.stream.parse == null); +} + +test "zz stream timings on the stress file with a worker (QUERY_TIMES=)" { + const path_z = std.c.getenv("QUERY_TIMES") orelse return error.SkipZigTest; + const path = std.mem.span(path_z); + const bytes = try std.Io.Dir.cwd().readFileAlloc(testing.io, path, testing.allocator, .limited(8 << 20)); + defer testing.allocator.free(bytes); + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 160, .rows = 50 }); + defer p.deinit(); + const pane = try p.setTestFile(bytes); + p.gpa.free(pane.file.?.path); + pane.file.?.path = try p.gpa.dupe(u8, path); + p.advance(1); + var shell: TestShell = .init(); + TestShell.attach(p); + defer { + p.stream.cancelTask(); + p.stream.cancelParse(); + shell.q.deinit(); + } + var frame = std.heap.ArenaAllocator.init(testing.allocator); + defer frame.deinit(); + pane.body.cur_row = 15000; + pane.ensureCursorVisible(); + _ = try p.render(frame.allocator()); + const t0 = now(); + for ("/pane") |c| p.update(.{ .key = .{ .cp = c, .text = &[_]u8{c} } }); + const typed = now() - t0; + var worst_wait: u64 = 0; + while (pane.file.?.context_revision == null or pane.file.?.context_revision.? != pane.file.?.revision) { + const t1 = now(); + shell.pump(p); + p.update(.tick); + _ = frame.reset(.retain_capacity); + _ = try p.render(frame.allocator()); + worst_wait = @max(worst_wait, now() - t1); + testing.io.sleep(.fromMilliseconds(2), .awake) catch {}; + } + var worst_key: u64 = 0; + for (".v") |c| { + const t2 = now(); + p.update(.{ .key = .{ .cp = c, .text = &[_]u8{c} } }); + _ = frame.reset(.retain_capacity); + _ = try p.render(frame.allocator()); + worst_key = @max(worst_key, now() - t2); + for (0..12) |_| p.update(.tick); + } + std.debug.print("stream: '/pane' typed in {d} us; the worker's parse {d} ms; worst frame while it parsed {d} us; a keystroke with grouped rows {d} us\n", .{ typed / 1000, p.stream.parse_ns / std.time.ns_per_ms, worst_wait / 1000, worst_key / 1000 }); +} + +test "Stream: a Grep stops at its 2000 lines and waits; More in the query pane's tag goes on" { + if (comptime !filesystem.platform_has_fs) return; + var tmp = testing.tmpDir(.{}); + defer tmp.cleanup(); + var root_buf: [4096]u8 = undefined; + var name_buf: [64]u8 = undefined; + var text: std.ArrayList(u8) = .empty; + defer text.deinit(testing.allocator); + for (0..20) |_| try text.appendSlice(testing.allocator, "a needle here\n"); + for (0..150) |i| try tmp.dir.writeFile(testing.io, .{ .sub_path = try std.fmt.bufPrint(&name_buf, "f{d:0>3}.txt", .{i}), .data = text.items }); + const root = root_buf[0..try tmp.dir.realPath(testing.io, &root_buf)]; + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 120, .rows = 40 }); + defer p.deinit(); + const pane = try p.setTestFile("x\n"); + p.gpa.free(pane.file.?.path); + pane.file.?.path = try std.fs.path.join(p.gpa, &.{ root, "main.txt" }); + p.advance(1); + var shell: TestShell = .init(); + TestShell.attach(p); + defer { + p.stream.cancelTask(); + shell.q.deinit(); + } + p.stream.engine = .walk; + panes.Query.open(p, 0, .grep, "needle", false); + const qid = for (p.panes, 0..) |slot, i| { + if (slot) |qp| if (qp.query != null) break i; + } else return error.NoQueryPane; + const qp = p.panes[qid].?; + p.advance(p.now_ns + debounce_ns + std.time.ns_per_ms); + const until = std.Io.Clock.awake.now(testing.io).toMilliseconds() + 20_000; + while (p.stream.state != .capped) { + if (std.Io.Clock.awake.now(testing.io).toMilliseconds() > until) return error.Timeout; + p.update(.tick); + shell.pump(p); + testing.io.sleep(.fromMicroseconds(200), .awake) catch {}; + } + p.update(.tick); + try testing.expectEqual(@as(usize, soft_cap), qp.query.?.found.items.len); + try testing.expect(qp.query.?.capped); + try testing.expectEqualStrings(" More Del", @import("tagline.zig").curTail(qp)); + pardes.exec.runBuiltin(p, .More, qid, "", null); + try shell.finish(p, 20_000); + p.update(.tick); + try testing.expectEqual(State.done, p.stream.state); + try testing.expectEqual(@as(usize, 3000), qp.query.?.found.items.len); + try testing.expect(!qp.query.?.capped); +} -- cgit v1.3