╭─────────────╮ │scroll to top│ ╰─────────────╯ ╭───────────────────────────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯
🬐 🬠 🬞🬂🬏 🬟 🬑 🬟 🬑 ╭master╮ master haxy: 🬋🬋🬋 🬋🬋🬋 🬋 🬋 │files │ commits refs discuss issues patches new login 🬐 🬠 🬐 🬠 🬑 🬟 🬰 ╰──────╯ (712) user
╭ find file ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ ╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ │ │ │http│ ssh │ │ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯
.. embed/ event/ test/ ui/ command.zig diff3.zig event.zig find.zig fork.zig lib.zig main.zig main_wasm.zig markdown.zig notify.zig patch.zig progress.zig push.zig ╭─────────────────────────────────╮ │search.zig │ ╰─────────────────────────────────╯ search_commit.zig search_thread.zig serve.zig serve_common.zig serve_http.zig serve_ssh.zig serve_ssh_protocol.zig test.zig testnet.zig try.zig ui.zig web.zig
9 const min_word_len = 2; 10 // a longer word is truncated to this rather than skipped, so a prefix query 11 // still reaches it. 12 const max_word_len = 32; 13 // how many distinct words one document contributes. 14 const max_words_per_doc = 256; 15 // how much of a document is tokenized. 16 pub const max_indexed_bytes = 16 * 1024; 17 // how many indexed words one typed word expands to. 18 const max_expansions = 200; 19 // the largest doc key, so results are read into a buffer rather than allocated. 20 pub const max_doc_key_len = 64; 21 22 // move `doc_key` from `old_text`'s words to `new_text`'s. the words they share 23 // are left alone, so editing a long description costs what the edit changed 24 // rather than the whole text. an empty side adds or drops the document. 25 pub fn replace( 26 comptime DB: type, 27 index: DB.SortedMap(.read_write), 28 allocator: std.mem.Allocator, 29 doc_key: []const u8, 30 old_text: []const u8, 31 new_text: []const u8, 32 ) !void { 33 var arena = std.heap.ArenaAllocator.init(allocator); 34 defer arena.deinit(); 35 const aa = arena.allocator(); 36 const old_words = try tokenize(aa, old_text); 37 const new_words = try tokenize(aa, new_text); 38 39 for (old_words) |word| { 40 if (!contains(new_words, word)) try removeWord(DB, index, doc_key, word); 41 } 42 for (new_words) |word| { 43 if (!contains(old_words, word)) try addWord(DB, index, doc_key, word); 44 } 45 } 46 47 // a document contributes at most max_words_per_doc words, so a scan costs less 48 // than building a second map 49 fn contains(words: []const []const u8, word: []const u8) bool { 50 for (words) |candidate| { 51 if (std.mem.eql(u8, candidate, word)) return true; 52 } 53 return false; 54 } 55 56 fn addWord(comptime DB: type, index: DB.SortedMap(.read_write), doc_key: []const u8, word: []const u8) !void { 57 const set = try DB.SortedSet(.read_write).init(try index.putCursor(word)); 58 try set.put(doc_key); 59 } 60 61 fn removeWord(comptime DB: type, index: DB.SortedMap(.read_write), doc_key: []const u8, word: []const u8) !void { 62 if (null == try index.getCursor(word)) return; 63 const set = try DB.SortedSet(.read_write).init(try index.putCursor(word)); 64 _ = try set.remove(doc_key); 65 if (0 == try set.count()) _ = try index.remove(word); 66 } 67 68 // the doc keys holding every typed word, in key order. a stream, so callers 69 // stop at their page size. 70 pub fn Query(comptime DB: type) type { 71 return struct { 72 // one per typed word, then one per required set. a term with no 73 // postings matches nothing, so neither does the query. 74 terms: std.ArrayList(Term), 75 // the key the next result starts from, plus room for the one byte that 76 // steps past a returned key 77 pos: [max_doc_key_len + 1]u8 = undefined, 78 pos_len: usize = 0, 79 // whether `pos` holds a key that was already returned 80 returned: bool = false, 81 82 const Self = @This(); 83 84 // one typed word: the doc keys of every indexed word it expands to, 85 // merged into one ascending stream. 86 const Term = struct { 87 postings: []Posting, 88 89 // the smallest doc key at or after `key`, or null when the term is 90 // exhausted. 91 fn seek(self: *Term, key: []const u8) !?[]const u8 { 92 var best: ?[]const u8 = null; 93 for (self.postings) |*posting| { 94 try posting.advance(key); 95 if (posting.done) continue; 96 const current = posting.key[0..posting.key_len]; 97 if (best) |found| { 98 if (std.mem.order(u8, current, found) == .lt) best = current; 99 } else best = current; 100 } 101 return best; 102 } 103 }; 104 105 // one indexed word's doc keys, positioned at the current one. 106 const Posting = struct { 107 set: DB.SortedSet(.read_only), 108 iter: DB.Cursor(.read_only).Iter = undefined, 109 key: [max_doc_key_len]u8 = undefined, 110 key_len: usize = 0, 111 done: bool = false, 112 started: bool = false, 113 114 // move to the first key at or after `key`. one step reaches it in 115 // a dense posting, and a seek skips the rest of a sparse one. 116 fn advance(self: *Posting, key: []const u8) !void { 117 if (self.done) return; 118 if (self.started) { 119 if (std.mem.order(u8, self.key[0..self.key_len], key) != .lt) return; 120 try self.step(); 121 if (self.done or std.mem.order(u8, self.key[0..self.key_len], key) != .lt) return; 122 } 123 self.iter = try self.set.iteratorFrom(key); 124 self.started = true; 125 try self.step(); 126 } 127 128 fn step(self: *Posting) !void { 129 const cursor = (try self.iter.next()) orelse { 130 self.done = true; 131 return; 132 }; 133 const pair = try cursor.readKeyValuePair(); 134 self.key_len = (try pair.key_cursor.readBytes(&self.key)).len; 135 } 136 }; 137 138 pub fn init(index: DB.SortedMap(.read_only), aa: std.mem.Allocator, text: []const u8) !Self { 139 var terms: std.ArrayList(Term) = .empty; 140 for (try tokenize(aa, text)) |word| { 141 var postings: std.ArrayList(Posting) = .empty; 142 var iter = try index.iteratorFrom(word); 143 while (try iter.next()) |cursor| { 144 if (postings.items.len == max_expansions) break; 145 const pair = try cursor.readKeyValuePair(); 146 var buffer: [max_word_len]u8 = undefined; 147 const indexed = try pair.key_cursor.readBytes(&buffer); 148 if (!std.mem.startsWith(u8, indexed, word)) break; 149 try postings.append(aa, .{ .set = try DB.SortedSet(.read_only).init(pair.value_cursor) }); 150 } 151 // a word nothing starts with leaves an empty term, which rules 152 // out every document 153 try terms.append(aa, .{ .postings = postings.items }); 154 } 155 return .{ .terms = terms }; 156 } 157 158 // narrow the results to the doc keys in `set`. it is one more term, 159 // with that set as its only posting. 160 pub fn require(self: *Self, aa: std.mem.Allocator, set: DB.SortedSet(.read_only)) !void { 161 const postings = try aa.alloc(Posting, 1); 162 postings[0] = .{ .set = set }; 163 try self.terms.append(aa, .{ .postings = postings }); 164 } 165 166 // start the next result at `key` rather than the first one. 167 pub fn seek(self: *Self, key: []const u8) void { 168 @memcpy(self.pos[0..key.len], key); 169 self.pos_len = key.len; 170 self.returned = false; 171 } 172 173 pub fn next(self: *Self) !?[]const u8 { 174 // with no terms at all nothing narrows the results, so none are listed 175 if (self.terms.items.len == 0) return null; 176 if (self.returned) { 177 // doc keys are at most max_doc_key_len, so appending a byte 178 // lands strictly after the one just returned 179 self.pos[self.pos_len] = 0; 180 self.pos_len += 1; 181 self.returned = false; 182 } 183 // intersect by seeking: a term that lands past the candidate makes 184 // its key the new candidate and the others seek up to it. 185 var i: usize = 0; 186 while (i < self.terms.items.len) { 187 const key = (try self.terms.items[i].seek(self.pos[0..self.pos_len])) orelse return null; 188 if (std.mem.order(u8, key, self.pos[0..self.pos_len]) == .gt) { 189 @memcpy(self.pos[0..key.len], key); 190 self.pos_len = key.len; 191 i = 0; 192 continue; 193 } 194 i += 1; 195 } 196 self.returned = true; 197 return self.pos[0..self.pos_len]; 198 } 199 }; 200 } 201 202 // the unique lowercased words of `text`, in the order they first appear. 203 fn tokenize(aa: std.mem.Allocator, text: []const u8) ![]const []const u8 { 204 var words: std.StringArrayHashMapUnmanaged(void) = .empty; 205 const limit = @min(text.len, max_indexed_bytes); 206 var i: usize = 0; 207 while (i < limit) { 208 if (!isWordByte(text[i])) { 209 i += 1; 210 continue; 211 } 212 const start = i; 213 while (i < limit and isWordByte(text[i])) i += 1; 214 const word = text[start..@min(i, start + max_word_len)]; 215 if (word.len < min_word_len) continue; 216 const lowered = try aa.alloc(u8, word.len); 217 _ = std.ascii.lowerString(lowered, word); 218 try words.put(aa, lowered, {}); 219 if (words.count() == max_words_per_doc) break; 220 } 221 return words.keys(); 222 } 223 224 // a word is a run of ascii alphanumerics and non-ascii bytes. 225 fn isWordByte(byte: u8) bool { 226 return std.ascii.isAlphanumeric(byte) or byte >= 0x80; 227 } 228