Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312//! Search's index as a file, `file_name` in the account's directory,//! mapped into memory rather than read: the operating system keeps in//! memory only the pages searches touch. It is the index of the corpus//! up to `corpus_end`, written whole from an index in memory (`write`)//! and never changed after; what the corpus gains past it is indexed in//! memory as it loads, until there is enough to write the file again.//!//! After a header, each part is an array the file holds as memory does,//! 8-byte aligned: the messages, their threads' ids and their own ids//! (sorted, for finding one), the words (sorted, so the words a prefix//! starts are a range), the postings of each, and the strings these name.
const std = @import("std");const builtin = @import("builtin");const Index = @import("Index.zig");const assert = std.debug.assert;const mem = std.mem;const Allocator = std.mem.Allocator;const Io = std.Io;const testing = std.testing;
const Segment = @This();
io: Io,map: Io.File.MemoryMap,/// How much of the corpus it indexes, in bytes, whether the backfill/// had gone through every message by then, and how far down it had/// kept every one (Corpus.reached).corpus_end: u64,walked: bool,reached: i64,docs: []const Doc,/// Each thread's id, by its place; sorted.threads: []const Str,/// Each message's id and place; sorted by id.messages: []const Message,/// Each word and its postings; sorted by word.words: []const Word,postings: []const Index.Posting,strings: []const u8,
pub const file_name = "index";
// The file holds the postings as memory does, which is little-endian// here.comptime { assert(builtin.cpu.arch.endian() == .little);}
const Header = extern struct { magic: [12]u8, version: u32, corpus_end: u64, docs: u32, threads: u32, messages: u32, words: u32, postings: u64, strings: u64, /// Whether the backfill had gone through every message. walked: u32, /// How far down the backfill had kept every message, in seconds /// since the epoch; 0 before it had kept a page. reached: u32,};
const magic = "parcel index".*;const version = 1;
/// A message: when it came, its thread by place, and whether it went/// from the account before the file was written.pub const Doc = extern struct { date: i64, thread: u32, gone: u32 };
/// Bytes of `strings`.pub const Str = extern struct { at: u32, len: u32,
fn of(s: Str) Str { return s; }};
const Message = extern struct { id: Str, doc: u32,
fn of(m: Message) Str { return m.id; }};
const Word = extern struct { word: Str, first: u32, count: u32,
fn of(w: Word) Str { return w.word; }};
/// Maps the file in `dir`, if it is there, whole, and indexes no more/// of the corpus than its `corpus_size` bytes; null otherwise, and it is/// to be written again.pub fn open(io: Io, dir: Io.Dir, corpus_size: u64) !?Segment { const file = dir.openFile(io, file_name, .{}) catch |err| switch (err) { error.FileNotFound => return null, else => return err, }; errdefer file.close(io); const size = try file.length(io); if (size < @sizeOf(Header) or size > std.math.maxInt(usize)) { file.close(io); return null; } var map = try file.createMemoryMap(io, .{ .len = @intCast(size), .protection = .{ .read = true }, .populate = false, }); errdefer map.destroy(io); const self = parse(io, map, corpus_size) orelse { map.destroy(io); file.close(io); return null; }; return self;}
pub fn close(self: *Segment) void { const file = self.map.file; self.map.destroy(self.io); file.close(self.io); self.* = undefined;}
/// The parts of a mapped file, if its header says it is one of this/// layout, whole, for no more of the corpus than there is.fn parse(io: Io, map: Io.File.MemoryMap, corpus_size: u64) ?Segment { const bytes = map.memory; const h = mem.bytesToValue(Header, bytes[0..@sizeOf(Header)]); if (!mem.eql(u8, &h.magic, &magic) or h.version != version or h.corpus_end > corpus_size) return null; var at: u64 = @sizeOf(Header); const docs = part(Doc, bytes, &at, h.docs) orelse return null; const threads = part(Str, bytes, &at, h.threads) orelse return null; const messages = part(Message, bytes, &at, h.messages) orelse return null; const words = part(Word, bytes, &at, h.words) orelse return null; const postings = part(Index.Posting, bytes, &at, h.postings) orelse return null; const strings = part(u8, bytes, &at, h.strings) orelse return null; return .{ .io = io, .map = map, .corpus_end = h.corpus_end, .walked = h.walked != 0, .reached = if (h.reached == 0) std.math.maxInt(i64) else h.reached, .docs = docs, .threads = threads, .messages = messages, .words = words, .postings = postings, .strings = strings, };}
fn part(comptime T: type, bytes: []align(std.heap.page_size_min) const u8, at: *u64, n: u64) ?[]const T { const start = mem.alignForward(u64, at.*, 8); const end = start + n * @sizeOf(T); if (end > bytes.len) return null; at.* = end; const slice: []align(8) const u8 = @alignCast(bytes[@intCast(start)..@intCast(end)]); return mem.bytesAsSlice(T, slice);}
pub fn str(self: *const Segment, s: Str) []const u8 { return self.strings[s.at..][0..s.len];}
/// The place of thread `id`, if it has one.pub fn findThread(self: *const Segment, id: []const u8) ?u32 { const i = lowerBound(Str, self, self.threads, id, Str.of); return if (i < self.threads.len and mem.eql(u8, self.str(self.threads[i]), id)) i else null;}
/// The place of message `id`, if it has one.pub fn findMessage(self: *const Segment, id: []const u8) ?u32 { const i = lowerBound(Message, self, self.messages, id, Message.of); if (i < self.messages.len and mem.eql(u8, self.str(self.messages[i].id), id)) return self.messages[i].doc; return null;}
/// The words `prefix` starts, by their places: itself first, if it is one.pub fn wordsStarting(self: *const Segment, prefix: []const u8) struct { start: u32, end: u32 } { const start = lowerBound(Word, self, self.words, prefix, Word.of); // The words it starts come together in order, from there. var lo = start; var hi: u32 = @intCast(self.words.len); while (lo < hi) { const mid = lo + (hi - lo) / 2; if (mem.startsWith(u8, self.str(self.words[mid].word), prefix)) lo = mid + 1 else hi = mid; } return .{ .start = start, .end = lo };}
pub fn postingsOf(self: *const Segment, w: u32) []const Index.Posting { const word = self.words[w]; return self.postings[word.first..][0..word.count];}
fn lowerBound( comptime T: type, self: *const Segment, items: []const T, key: []const u8, comptime keyOf: fn (T) Str,) u32 { var lo: u32 = 0; var hi: u32 = @intCast(items.len); while (lo < hi) { const mid = lo + (hi - lo) / 2; if (mem.order(u8, self.str(keyOf(items[mid])), key) == .lt) lo = mid + 1 else hi = mid; } return lo;}
/// What `write` puts in the file, in order: thread ids, messages by id,/// and words, each sorted.pub const Parts = struct { corpus_end: u64, walked: bool, reached: i64, docs: []const Doc, threads: []const []const u8, messages: []const struct { id: []const u8, doc: u32 }, words: []const []const u8, /// Each word's postings, in its order. postings: []const []const Index.Posting,};
/// Writes `parts` as the file in `dir`, which replaces the old one whole/// or not at all, for the user alone.pub fn write(io: Io, dir: Io.Dir, parts: Parts) !void { var postings: u64 = 0; var strings: u64 = 0; for (parts.threads) |t| strings += t.len; for (parts.messages) |m| strings += m.id.len; for (parts.words, parts.postings) |w, p| { strings += w.len; postings += p.len; } if (strings > std.math.maxInt(u32) or postings > std.math.maxInt(u32)) return error.IndexTooBig; var atomic = try dir.createFileAtomic(io, file_name, .{ .replace = true, .permissions = @fromBackingInt(0o600) }); defer atomic.deinit(io); var buf: [64 * 1024]u8 = undefined; var fw = atomic.file.writer(io, &buf); const w = &fw.interface; const header: Header = .{ .magic = magic, .version = version, .corpus_end = parts.corpus_end, .docs = @intCast(parts.docs.len), .threads = @intCast(parts.threads.len), .messages = @intCast(parts.messages.len), .words = @intCast(parts.words.len), .postings = postings, .strings = strings, .walked = @intFromBool(parts.walked), .reached = std.math.cast(u32, parts.reached) orelse 0, }; var at: u64 = 0; try put(w, &at, mem.asBytes(&header)); try put(w, &at, mem.sliceAsBytes(parts.docs)); // Each string's place in `strings`, in the order they are written below. var next: u32 = 0; try pad(w, &at); for (parts.threads) |t| try put(w, &at, mem.asBytes(&strAt(&next, t))); try pad(w, &at); for (parts.messages) |m| try put(w, &at, mem.asBytes(&Message{ .id = strAt(&next, m.id), .doc = m.doc })); try pad(w, &at); var first: u32 = 0; for (parts.words, parts.postings) |word, p| { const entry: Word = .{ .word = strAt(&next, word), .first = first, .count = @intCast(p.len) }; try put(w, &at, mem.asBytes(&entry)); first += @intCast(p.len); } try pad(w, &at); for (parts.postings) |p| try put(w, &at, mem.sliceAsBytes(p)); try pad(w, &at); for (parts.threads) |t| try put(w, &at, t); for (parts.messages) |m| try put(w, &at, m.id); for (parts.words) |word| try put(w, &at, word); try w.flush(); try atomic.replace(io);}
fn strAt(next: *u32, s: []const u8) Str { defer next.* += @intCast(s.len); return .{ .at = next.*, .len = @intCast(s.len) };}
fn put(w: *Io.Writer, at: *u64, bytes: []const u8) !void { try w.writeAll(bytes); at.* += bytes.len;}
/// Pads to the next part's alignment, as `part` reads it.fn pad(w: *Io.Writer, at: *u64) !void { const zeros: [8]u8 = @splat(0); const n = mem.alignForward(u64, at.*, 8) - at.*; try put(w, at, zeros[0..@intCast(n)]);}