lib/sql/src/search/posting.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sql = @import("../root.zig");
3 const engine_mod = @import("engine.zig");
4 const hit_mod = @import("hit.zig");
5 const text_mod = @import("text.zig");
6 const token_mod = @import("token.zig");
7 const vbyte = @import("vbyte.zig");
8 const row = sql.row;
9
10 const Allocator = std.mem.Allocator;
11
12 pub const posting_payload_size = 4;
13
14 pub const phrase_pair_posting_kind: u8 = '"';
15
16 pub const phrase_pair_posting_key_max_bytes = token_mod.max_token_bytes * 2 + 2;
17
18 pub const segment_payload_tag: u8 = 0x53;
19
20 pub const segment_payload_header_size = 5;
21
22 pub const segment_payload_entry_size = 12;
23
24 pub const compact_segment_payload_tag: u8 = 0x73;
25
26 pub const compact_segment_payload_header_size = 13;
27
28 pub const compact_segment_payload_entry_size = 6;
29
30 pub const stream_segment_payload_tag: u8 = 0x76;
31
32 pub const stream_segment_payload_header_size = 17;
33
34 pub const segment_min_postings = 2;
35
36 pub const length_segment_payload_tag: u8 = 0x4c;
37
38 pub const document_length_payload_size = 4;
39
40 pub const document_length_tombstone = std.math.maxInt(u32);
41
42 pub const corpus_stats_payload_size = 16;
43
44 pub const capabilities_payload_size = 8;
45
46 pub const source_payload_size = 40;
47
48 pub const internal_meta_rowid: i64 = 0;
49
50 pub const corpus_stats_key = "\x01s";
51
52 pub const document_length_key = "\x01l";
53
54 pub const capabilities_key = "\x01c";
55
56 pub const source_key = "\x01r";
57
58 pub const capability_phrase_pair_postings: u64 = 1;
59
60 pub const capability_phrase_pair_singletons_omitted: u64 = 2;
61
62 pub const Capabilities = struct {
63 phrase_pair_postings: bool = false,
64 phrase_pair_singletons_omitted: bool = false,
65 };
66
67 pub const Source = struct {
68 schema: u64,
69 head: [32]u8,
70
71 pub fn same(left: Source, right: Source) bool {
72 return left.schema == right.schema and std.mem.eql(u8, &left.head, &right.head);
73 }
74 };
75
76 pub const PostingStats = struct {
77 term_index_entries: usize = 0,
78 metadata_entries: usize = 0,
79 payload_bytes: usize = 0,
80 posting_payload_bytes: usize = 0,
81 posting_key_text_bytes: usize = 0,
82 posting_entries: usize = 0,
83 posting_term_keys: usize = 0,
84 posting_term_key_text_bytes: usize = 0,
85 exact_term_keys: usize = 0,
86 exact_term_key_text_bytes: usize = 0,
87 prefix_term_keys: usize = 0,
88 prefix_term_key_text_bytes: usize = 0,
89 phrase_pair_term_keys: usize = 0,
90 phrase_pair_term_key_text_bytes: usize = 0,
91 direct_posting_entries: usize = 0,
92 direct_posting_tombstones: usize = 0,
93 segment_entries: usize = 0,
94 segment_postings: usize = 0,
95 exact_posting_key_text_bytes: usize = 0,
96 prefix_posting_key_text_bytes: usize = 0,
97 phrase_pair_posting_key_text_bytes: usize = 0,
98 exact_posting_payload_bytes: usize = 0,
99 prefix_posting_payload_bytes: usize = 0,
100 phrase_pair_posting_payload_bytes: usize = 0,
101 phrase_pair_direct_posting_entries: usize = 0,
102 phrase_pair_direct_posting_tombstones: usize = 0,
103 phrase_pair_segment_entries: usize = 0,
104 phrase_pair_segment_postings: usize = 0,
105 document_length_entries: usize = 0,
106 document_length_direct_entries: usize = 0,
107 document_length_segment_entries: usize = 0,
108 document_length_segment_postings: usize = 0,
109
110 pub fn livePostingEntries(self: PostingStats) usize {
111 return self.direct_posting_entries + self.segment_postings;
112 }
113
114 pub fn phrasePairLivePostingEntries(self: PostingStats) usize {
115 return self.phrase_pair_direct_posting_entries + self.phrase_pair_segment_postings;
116 }
117 };
118
119 pub const SegmentCursor = struct {
120 payload: []u8,
121 count: usize,
122 decoder: SegmentDecoder,
123
124 pub fn init(allocator: Allocator, payload: []const u8, count: usize) engine_mod.Error!SegmentCursor {
125 const owned = try allocator.dupe(u8, payload);
126 errdefer allocator.free(owned);
127 const decoder = try SegmentDecoder.initValidated(owned, count);
128 return .{
129 .payload = owned,
130 .count = decoder.count,
131 .decoder = decoder,
132 };
133 }
134
135 pub fn deinit(self: *SegmentCursor, allocator: Allocator) void {
136 allocator.free(self.payload);
137 self.* = undefined;
138 }
139
140 pub fn current(self: *SegmentCursor) engine_mod.Error!?hit_mod.Hit {
141 return try self.decoder.current();
142 }
143
144 pub fn advance(self: *SegmentCursor) engine_mod.Error!void {
145 try self.decoder.advance();
146 }
147
148 pub fn reset(self: *SegmentCursor) void {
149 self.decoder.reset();
150 }
151 };
152
153 pub const SegmentDecoder = struct {
154 payload: []const u8,
155 count: usize,
156 index: usize = 0,
157 stream: vbyte.Decoder = .{},
158 previous_rowid: i64 = 0,
159 block: [2]hit_mod.Hit = undefined,
160 block_count: usize = 0,
161 block_index: usize = 0,
162 block_loaded: bool = false,
163
164 pub fn init(payload: []const u8) engine_mod.Error!SegmentDecoder {
165 const count = segmentPayloadCount(payload) orelse return error.InvalidSearchIndex;
166 return try initValidated(payload, count);
167 }
168
169 pub fn initValidated(payload: []const u8, count: usize) engine_mod.Error!SegmentDecoder {
170 std.debug.assert(segmentPayloadCount(payload) == count);
171 if (payload.len < segment_payload_header_size) return error.InvalidSearchIndex;
172 var decoder = SegmentDecoder{
173 .payload = payload,
174 .count = count,
175 };
176 decoder.reset();
177 return decoder;
178 }
179
180 pub fn current(self: *SegmentDecoder) engine_mod.Error!?hit_mod.Hit {
181 if (self.index >= self.count) return null;
182 if (!self.block_loaded) try self.loadBlock();
183 return self.block[self.block_index];
184 }
185
186 pub fn advance(self: *SegmentDecoder) engine_mod.Error!void {
187 if (self.index >= self.count) return;
188 if (!self.block_loaded) try self.loadBlock();
189 self.consume();
190 }
191
192 pub fn next(self: *SegmentDecoder) engine_mod.Error!?hit_mod.Hit {
193 const hit = (try self.current()) orelse return null;
194 self.consume();
195 return hit;
196 }
197
198 fn consume(self: *SegmentDecoder) void {
199 self.index += 1;
200 self.block_index += 1;
201 if (self.block_index == self.block_count) {
202 self.block_count = 0;
203 self.block_index = 0;
204 self.block_loaded = false;
205 }
206 }
207
208 pub fn reset(self: *SegmentDecoder) void {
209 self.index = 0;
210 self.block_count = 0;
211 self.block_index = 0;
212 self.block_loaded = false;
213 if (self.payload[0] == stream_segment_payload_tag) {
214 const value_count = std.math.mul(usize, self.count, 2) catch unreachable;
215 self.stream = vbyte.Decoder.initValidated(self.payload[stream_segment_payload_header_size..], value_count);
216 self.previous_rowid = std.mem.readInt(i64, self.payload[5..13], .big);
217 } else {
218 self.stream = .{};
219 self.previous_rowid = 0;
220 }
221 }
222
223 fn loadBlock(self: *SegmentDecoder) engine_mod.Error!void {
224 if (self.payload[0] != stream_segment_payload_tag) {
225 self.block[0] = try fixedSegmentPayloadHit(self.payload, self.count, self.index);
226 self.block_count = 1;
227 self.block_loaded = true;
228 return;
229 }
230 if (self.index % 2 != 0) return error.InvalidSearchIndex;
231 const block_count: usize = @min(self.count - self.index, 2);
232 var values: [4]u32 = undefined;
233 try self.stream.nextBlock(&values, block_count * 2);
234 var previous = self.previous_rowid;
235 for (0..block_count) |block_index| {
236 const posting_index = self.index + block_index;
237 const gap = values[block_index * 2];
238 const score = values[block_index * 2 + 1];
239 if ((posting_index == 0 and gap != 0) or (posting_index != 0 and gap == 0) or score == 0) return error.InvalidSearchIndex;
240 const rowid = std.math.add(i64, previous, gap) catch return error.InvalidSearchIndex;
241 self.block[block_index] = .{ .rowid = rowid, .score = score };
242 previous = rowid;
243 }
244 if (self.index + block_count == self.count) {
245 const first_rowid = std.mem.readInt(i64, self.payload[5..13], .big);
246 const last_delta = std.mem.readInt(u32, self.payload[13..17], .big);
247 const last_rowid = std.math.add(i64, first_rowid, last_delta) catch return error.InvalidSearchIndex;
248 if (previous != last_rowid or self.stream.value_index != self.stream.value_count or self.stream.data_offset != self.stream.input.len) return error.InvalidSearchIndex;
249 }
250 self.previous_rowid = previous;
251 self.block_count = block_count;
252 self.block_loaded = true;
253 }
254 };
255
256 pub const DirectPosting = struct {
257 rowid: i64,
258 score: usize,
259 };
260
261 pub const CorpusStats = struct {
262 documents: usize,
263 total_tokens: usize,
264 };
265
266 pub const DocumentLength = struct {
267 rowid: i64,
268 length: usize,
269 };
270
271 pub const LengthSegmentCursor = struct {
272 payload: []u8,
273 index: usize = 0,
274 count: usize,
275
276 pub fn deinit(self: *LengthSegmentCursor, allocator: Allocator) void {
277 allocator.free(self.payload);
278 self.* = undefined;
279 }
280
281 pub fn current(self: *const LengthSegmentCursor) engine_mod.Error!?DocumentLength {
282 if (self.index >= self.count) return null;
283 return try lengthSegmentPayloadValue(self.payload, self.index);
284 }
285
286 pub fn advance(self: *LengthSegmentCursor) void {
287 self.index += 1;
288 }
289 };
290
291 pub const DirectDocumentLength = struct {
292 rowid: i64,
293 length: ?usize,
294 };
295
296 pub const Posting = struct {
297 rowid: i64,
298 key_index: u32,
299 count: u32,
300 };
301
302 pub const PostingKeyMap = std.StringHashMap(u32);
303
304 pub const PostingSet = struct {
305 items: []Posting,
306 keys: []const []const u8,
307
308 pub fn deinit(self: *PostingSet, allocator: Allocator) void {
309 freeStringSlice(allocator, self.keys);
310 if (self.items.len != 0) allocator.free(self.items);
311 self.* = undefined;
312 }
313 };
314
315 pub const TermCount = struct {
316 key: []const u8,
317 count: usize,
318 };
319
320 pub const PhrasePairAccumulator = struct {
321 first: []const u8,
322 second: []const u8,
323 first_rowid: i64,
324 first_count: u32 = 1,
325 key_index: ?u32 = null,
326 last_rowid: i64 = 0,
327 last_posting_index: usize = 0,
328 next: ?usize = null,
329 };
330
331 pub fn documentTermCounts(allocator: Allocator, text: []const u8, index_prefixes: bool, index_phrase_pairs: bool) engine_mod.Error![]TermCount {
332 var counts: std.ArrayList(TermCount) = .empty;
333 errdefer {
334 for (counts.items) |term_count| allocator.free(term_count.key);
335 counts.deinit(allocator);
336 }
337 if (!index_prefixes) try counts.ensureTotalCapacity(allocator, if (index_phrase_pairs) 32 else 16);
338 var offset: usize = 0;
339 var position: usize = 0;
340 var field: usize = 0;
341 var previous_text: []const u8 = &.{};
342 var previous_position: usize = 0;
343 var previous_field: usize = 0;
344 var have_previous = false;
345 while (text_mod.nextTextToken(text, &offset, &position, &field)) |token| {
346 try incrementTokenTermCount(allocator, &counts, '=', token.text, token.text.len);
347 if (index_phrase_pairs and have_previous and token.field == previous_field and token.position == previous_position + 1) try incrementPhrasePairTermCount(allocator, &counts, previous_text, token.text);
348 previous_text = token.text;
349 previous_position = token.position;
350 previous_field = token.field;
351 have_previous = true;
352 if (!index_prefixes) continue;
353 var len: usize = 1;
354 while (len <= token.text.len) : (len += 1) try incrementTokenTermCount(allocator, &counts, '*', token.text, len);
355 }
356 return try counts.toOwnedSlice(allocator);
357 }
358
359 pub fn documentTermCountCapacity(text: []const u8, index_prefixes: bool, index_phrase_pairs: bool) Allocator.Error!usize {
360 var capacity: usize = 0;
361 var offset: usize = 0;
362 var position: usize = 0;
363 var field: usize = 0;
364 var previous_position: usize = 0;
365 var previous_field: usize = 0;
366 var have_previous = false;
367 while (text_mod.nextTextToken(text, &offset, &position, &field)) |token| {
368 capacity = std.math.add(usize, capacity, 1) catch return error.OutOfMemory;
369 if (index_phrase_pairs and have_previous and token.field == previous_field and token.position == previous_position + 1) {
370 capacity = std.math.add(usize, capacity, 1) catch return error.OutOfMemory;
371 }
372 previous_position = token.position;
373 previous_field = token.field;
374 have_previous = true;
375 if (index_prefixes) capacity = std.math.add(usize, capacity, token.text.len) catch return error.OutOfMemory;
376 }
377 return capacity;
378 }
379
380 pub fn documentInternedTermCounts(
381 allocator: Allocator,
382 text: []const u8,
383 index_prefixes: bool,
384 index_phrase_pairs: bool,
385 key_map: *PostingKeyMap,
386 keys: *std.ArrayList([]const u8),
387 counts_buffer: []TermCount,
388 ) engine_mod.Error![]const TermCount {
389 var count: usize = 0;
390 var offset: usize = 0;
391 var position: usize = 0;
392 var field: usize = 0;
393 var previous_text: []const u8 = &.{};
394 var previous_position: usize = 0;
395 var previous_field: usize = 0;
396 var have_previous = false;
397 while (text_mod.nextTextToken(text, &offset, &position, &field)) |token| {
398 try incrementInternedTokenTermCount(allocator, counts_buffer, &count, key_map, keys, '=', token.text, token.text.len);
399 if (index_phrase_pairs and have_previous and token.field == previous_field and token.position == previous_position + 1) try incrementInternedPhrasePairTermCount(allocator, counts_buffer, &count, key_map, keys, previous_text, token.text);
400 previous_text = token.text;
401 previous_position = token.position;
402 previous_field = token.field;
403 have_previous = true;
404 if (!index_prefixes) continue;
405 var len: usize = 1;
406 while (len <= token.text.len) : (len += 1) try incrementInternedTokenTermCount(allocator, counts_buffer, &count, key_map, keys, '*', token.text, len);
407 }
408 return counts_buffer[0..count];
409 }
410
411 pub fn postingValues(key_text: []const u8) [1]row.Value {
412 return .{.{ .text = key_text }};
413 }
414
415 pub fn postingPayload(target: []u8, count: usize) engine_mod.Error![]const u8 {
416 if (target.len < posting_payload_size) return error.OutputTooSmall;
417 std.mem.writeInt(u32, target[0..posting_payload_size], @intCast(count), .big);
418 return target[0..posting_payload_size];
419 }
420
421 pub fn documentLengthValues() [1]row.Value {
422 return .{.{ .text = document_length_key }};
423 }
424
425 pub fn corpusStatsValues() [1]row.Value {
426 return .{.{ .text = corpus_stats_key }};
427 }
428
429 pub fn capabilitiesValues() [1]row.Value {
430 return .{.{ .text = capabilities_key }};
431 }
432
433 pub fn sourceValues() [1]row.Value {
434 return .{.{ .text = source_key }};
435 }
436
437 pub fn documentLengthPayload(target: []u8, length: usize) engine_mod.Error![]const u8 {
438 if (target.len < document_length_payload_size) return error.OutputTooSmall;
439 const value = std.math.cast(u32, length) orelse return error.InvalidSearchIndex;
440 if (value == document_length_tombstone) return error.InvalidSearchIndex;
441 std.mem.writeInt(u32, target[0..document_length_payload_size], value, .big);
442 return target[0..document_length_payload_size];
443 }
444
445 pub fn documentLengthTombstonePayload(target: []u8) []const u8 {
446 std.debug.assert(target.len >= document_length_payload_size);
447 std.mem.writeInt(u32, target[0..document_length_payload_size], document_length_tombstone, .big);
448 return target[0..document_length_payload_size];
449 }
450
451 pub fn documentLengthPayloadMaybe(payload: []const u8) engine_mod.Error!?usize {
452 if (payload.len != document_length_payload_size) return error.InvalidSearchIndex;
453 const value = std.mem.readInt(u32, payload[0..document_length_payload_size], .big);
454 if (value == document_length_tombstone) return null;
455 return value;
456 }
457
458 pub fn documentLengthPayloadValue(payload: []const u8) engine_mod.Error!usize {
459 return (try documentLengthPayloadMaybe(payload)) orelse error.InvalidSearchIndex;
460 }
461
462 pub fn corpusStatsPayload(target: []u8, stats: CorpusStats) engine_mod.Error![]const u8 {
463 if (target.len < corpus_stats_payload_size) return error.OutputTooSmall;
464 const documents = std.math.cast(u64, stats.documents) orelse return error.InvalidSearchIndex;
465 const total_tokens = std.math.cast(u64, stats.total_tokens) orelse return error.InvalidSearchIndex;
466 std.mem.writeInt(u64, target[0..8], documents, .big);
467 std.mem.writeInt(u64, target[8..16], total_tokens, .big);
468 return target[0..corpus_stats_payload_size];
469 }
470
471 pub fn corpusStatsPayloadValue(payload: []const u8) engine_mod.Error!CorpusStats {
472 if (payload.len != corpus_stats_payload_size) return error.InvalidSearchIndex;
473 const documents = std.mem.readInt(u64, payload[0..8], .big);
474 const total_tokens = std.mem.readInt(u64, payload[8..16], .big);
475 return .{
476 .documents = std.math.cast(usize, documents) orelse return error.InvalidSearchIndex,
477 .total_tokens = std.math.cast(usize, total_tokens) orelse return error.InvalidSearchIndex,
478 };
479 }
480
481 pub fn capabilitiesPayload(target: []u8, capabilities_value: Capabilities) engine_mod.Error![]const u8 {
482 if (target.len < capabilities_payload_size) return error.OutputTooSmall;
483 std.mem.writeInt(u64, target[0..capabilities_payload_size], capabilityFlags(capabilities_value), .big);
484 return target[0..capabilities_payload_size];
485 }
486
487 pub fn capabilitiesPayloadValue(payload: []const u8) engine_mod.Error!Capabilities {
488 if (payload.len != capabilities_payload_size) return error.InvalidSearchIndex;
489 return try capabilitiesFromFlags(std.mem.readInt(u64, payload[0..capabilities_payload_size], .big));
490 }
491
492 pub fn sourcePayload(target: []u8, source: Source) engine_mod.Error![]const u8 {
493 if (target.len < source_payload_size) return error.OutputTooSmall;
494 std.mem.writeInt(u64, target[0..8], source.schema, .big);
495 @memcpy(target[8..source_payload_size], &source.head);
496 return target[0..source_payload_size];
497 }
498
499 pub fn sourcePayloadValue(payload: []const u8) engine_mod.Error!Source {
500 if (payload.len != source_payload_size) return error.InvalidSearchIndex;
501 return .{
502 .schema = std.mem.readInt(u64, payload[0..8], .big),
503 .head = payload[8..source_payload_size].*,
504 };
505 }
506
507 pub fn capabilityFlags(capabilities_value: Capabilities) u64 {
508 var flags: u64 = 0;
509 if (capabilities_value.phrase_pair_postings) flags |= capability_phrase_pair_postings;
510 if (capabilities_value.phrase_pair_singletons_omitted) flags |= capability_phrase_pair_singletons_omitted;
511 return flags;
512 }
513
514 pub fn capabilitiesFromFlags(flags: u64) engine_mod.Error!Capabilities {
515 const known = capability_phrase_pair_postings | capability_phrase_pair_singletons_omitted;
516 if (flags & ~known != 0) return error.InvalidSearchIndex;
517 return .{
518 .phrase_pair_postings = flags & capability_phrase_pair_postings != 0,
519 .phrase_pair_singletons_omitted = flags & capability_phrase_pair_singletons_omitted != 0,
520 };
521 }
522
523 pub fn capabilitiesEmpty(capabilities_value: Capabilities) bool {
524 return capabilityFlags(capabilities_value) == 0;
525 }
526
527 pub fn capabilitiesInclude(current: Capabilities, requested: Capabilities) bool {
528 return capabilityFlags(current) & capabilityFlags(requested) == capabilityFlags(requested);
529 }
530
531 pub fn mergeCapabilities(left: Capabilities, right: Capabilities) Capabilities {
532 return .{
533 .phrase_pair_postings = left.phrase_pair_postings or right.phrase_pair_postings,
534 .phrase_pair_singletons_omitted = left.phrase_pair_singletons_omitted or right.phrase_pair_singletons_omitted,
535 };
536 }
537
538 pub fn addDocumentStats(stats: CorpusStats, length: usize) engine_mod.Error!CorpusStats {
539 return .{
540 .documents = std.math.add(usize, stats.documents, 1) catch return error.InvalidSearchIndex,
541 .total_tokens = std.math.add(usize, stats.total_tokens, length) catch return error.InvalidSearchIndex,
542 };
543 }
544
545 pub fn subtractDocumentStats(stats: CorpusStats, length: usize) engine_mod.Error!CorpusStats {
546 if (stats.documents == 0 or stats.total_tokens < length) return error.InvalidSearchIndex;
547 return .{
548 .documents = stats.documents - 1,
549 .total_tokens = stats.total_tokens - length,
550 };
551 }
552
553 pub fn canSegmentPostings(postings: []const Posting) bool {
554 if (postings.len < segment_min_postings) return false;
555 var previous: ?i64 = null;
556 for (postings) |posting| {
557 if (posting.rowid < 0 or posting.count == 0) return false;
558 if (previous) |rowid| {
559 if (posting.rowid <= rowid) return false;
560 }
561 previous = posting.rowid;
562 }
563 return true;
564 }
565
566 pub fn canSegmentDocumentLengths(lengths: []const DocumentLength) bool {
567 if (lengths.len < segment_min_postings) return false;
568 var previous: ?i64 = null;
569 for (lengths) |document_length| {
570 if (document_length.rowid < 0) return false;
571 if (previous) |rowid| {
572 if (document_length.rowid <= rowid) return false;
573 }
574 previous = document_length.rowid;
575 }
576 return true;
577 }
578
579 pub fn segmentRowid(first_rowid: i64) engine_mod.Error!i64 {
580 if (first_rowid < 0) return error.InvalidSearchIndex;
581 const value = @as(i128, std.math.minInt(i64)) + @as(i128, first_rowid);
582 return @intCast(value);
583 }
584
585 pub fn postingSegmentPayload(allocator: Allocator, postings: []const Posting) engine_mod.Error![]u8 {
586 if (!canSegmentPostings(postings)) return error.InvalidSearchIndex;
587 if (postings.len > std.math.maxInt(u32)) return error.InvalidSearchIndex;
588 const wide_payload_len = segmentPayloadSize(segment_payload_header_size, segment_payload_entry_size, postings.len) orelse return error.InvalidSearchIndex;
589 const compact_payload_len = if (canCompactSegmentPostings(postings))
590 segmentPayloadSize(compact_segment_payload_header_size, compact_segment_payload_entry_size, postings.len) orelse return error.InvalidSearchIndex
591 else
592 null;
593 if (streamPostingSegmentPayloadSize(postings)) |stream_payload_len| {
594 const fixed_payload_len = compact_payload_len orelse wide_payload_len;
595 if (stream_payload_len < fixed_payload_len) return try streamPostingSegmentPayload(allocator, postings, stream_payload_len);
596 }
597 if (canCompactSegmentPostings(postings)) return try compactPostingSegmentPayload(allocator, postings);
598 const payload = try allocator.alloc(u8, wide_payload_len);
599 errdefer allocator.free(payload);
600 payload[0] = segment_payload_tag;
601 std.mem.writeInt(u32, payload[1..5], @intCast(postings.len), .big);
602 var cursor: usize = segment_payload_header_size;
603 for (postings) |posting| {
604 std.mem.writeInt(i64, payload[cursor..][0..8], posting.rowid, .big);
605 cursor += 8;
606 std.mem.writeInt(u32, payload[cursor..][0..4], @intCast(posting.count), .big);
607 cursor += 4;
608 }
609 return payload;
610 }
611
612 pub fn canCompactSegmentPostings(postings: []const Posting) bool {
613 if (postings.len == 0) return false;
614 const first_rowid = postings[0].rowid;
615 if (first_rowid < 0) return false;
616 var previous_rowid: ?i64 = null;
617 for (postings) |posting| {
618 if (posting.rowid < first_rowid) return false;
619 if (previous_rowid) |previous| {
620 if (posting.rowid <= previous) return false;
621 }
622 const delta = @as(u128, @intCast(posting.rowid - first_rowid));
623 if (delta > std.math.maxInt(u32)) return false;
624 if (posting.count == 0 or posting.count > std.math.maxInt(u16)) return false;
625 previous_rowid = posting.rowid;
626 }
627 return true;
628 }
629
630 pub fn compactPostingSegmentPayload(allocator: Allocator, postings: []const Posting) engine_mod.Error![]u8 {
631 if (!canCompactSegmentPostings(postings)) return error.InvalidSearchIndex;
632 const payload_len = segmentPayloadSize(compact_segment_payload_header_size, compact_segment_payload_entry_size, postings.len) orelse return error.InvalidSearchIndex;
633 const payload = try allocator.alloc(u8, payload_len);
634 errdefer allocator.free(payload);
635 const first_rowid = postings[0].rowid;
636 payload[0] = compact_segment_payload_tag;
637 std.mem.writeInt(u32, payload[1..5], @intCast(postings.len), .big);
638 std.mem.writeInt(i64, payload[5..13], first_rowid, .big);
639 var cursor: usize = compact_segment_payload_header_size;
640 for (postings) |posting| {
641 std.mem.writeInt(u32, payload[cursor..][0..4], @intCast(posting.rowid - first_rowid), .big);
642 cursor += 4;
643 std.mem.writeInt(u16, payload[cursor..][0..2], @intCast(posting.count), .big);
644 cursor += 2;
645 }
646 return payload;
647 }
648
649 fn streamPostingSegmentPayloadSize(postings: []const Posting) ?usize {
650 if (postings.len < segment_min_postings or postings.len > std.math.maxInt(u32)) return null;
651 const first_rowid = postings[0].rowid;
652 if (first_rowid < 0) return null;
653 var previous_rowid = first_rowid;
654 var data_count: usize = 0;
655 for (postings, 0..) |posting, index| {
656 if (posting.count == 0 or posting.rowid < first_rowid) return null;
657 if (index != 0 and posting.rowid <= previous_rowid) return null;
658 const span: u64 = @intCast(posting.rowid - first_rowid);
659 if (span > std.math.maxInt(u32)) return null;
660 const gap: u64 = if (index == 0) 0 else @intCast(posting.rowid - previous_rowid);
661 if ((index != 0 and gap == 0) or gap > std.math.maxInt(u32)) return null;
662 data_count = std.math.add(usize, data_count, vbyte.valueByteCount(@intCast(gap))) catch return null;
663 data_count = std.math.add(usize, data_count, vbyte.valueByteCount(posting.count)) catch return null;
664 previous_rowid = posting.rowid;
665 }
666 const value_count = std.math.mul(usize, postings.len, 2) catch return null;
667 const stream_size = std.math.add(usize, vbyte.controlByteCount(value_count), data_count) catch return null;
668 return std.math.add(usize, stream_segment_payload_header_size, stream_size) catch null;
669 }
670
671 fn streamPostingSegmentPayload(allocator: Allocator, postings: []const Posting, payload_len: usize) engine_mod.Error![]u8 {
672 const payload = try allocator.alloc(u8, payload_len);
673 errdefer allocator.free(payload);
674 const first_rowid = postings[0].rowid;
675 const last_delta = std.math.cast(u32, postings[postings.len - 1].rowid - first_rowid) orelse return error.InvalidSearchIndex;
676 payload[0] = stream_segment_payload_tag;
677 std.mem.writeInt(u32, payload[1..5], @intCast(postings.len), .big);
678 std.mem.writeInt(i64, payload[5..13], first_rowid, .big);
679 std.mem.writeInt(u32, payload[13..17], last_delta, .big);
680 const value_count = std.math.mul(usize, postings.len, 2) catch return error.InvalidSearchIndex;
681 var encoder = try vbyte.Encoder.init(payload[stream_segment_payload_header_size..], value_count);
682 var previous_rowid = first_rowid;
683 for (postings, 0..) |posting, index| {
684 const gap: u32 = if (index == 0) 0 else @intCast(posting.rowid - previous_rowid);
685 try encoder.append(gap);
686 try encoder.append(posting.count);
687 previous_rowid = posting.rowid;
688 }
689 try encoder.finish();
690 return payload;
691 }
692
693 fn segmentPayloadSize(header_size: usize, entry_size: usize, count: usize) ?usize {
694 const entries_size = std.math.mul(usize, entry_size, count) catch return null;
695 return std.math.add(usize, header_size, entries_size) catch null;
696 }
697
698 pub fn documentLengthSegmentPayload(allocator: Allocator, lengths: []const DocumentLength) engine_mod.Error![]u8 {
699 if (lengths.len > std.math.maxInt(u32)) return error.InvalidSearchIndex;
700 const payload_len = segmentPayloadSize(segment_payload_header_size, segment_payload_entry_size, lengths.len) orelse return error.InvalidSearchIndex;
701 const payload = try allocator.alloc(u8, payload_len);
702 errdefer allocator.free(payload);
703 payload[0] = length_segment_payload_tag;
704 std.mem.writeInt(u32, payload[1..5], @intCast(lengths.len), .big);
705 var cursor: usize = segment_payload_header_size;
706 for (lengths) |document_length| {
707 std.mem.writeInt(i64, payload[cursor..][0..8], document_length.rowid, .big);
708 cursor += 8;
709 const value = std.math.cast(u32, document_length.length) orelse return error.InvalidSearchIndex;
710 if (value == document_length_tombstone) return error.InvalidSearchIndex;
711 std.mem.writeInt(u32, payload[cursor..][0..4], value, .big);
712 cursor += 4;
713 }
714 return payload;
715 }
716
717 pub fn segmentPayloadCount(payload: []const u8) ?usize {
718 if (payload.len < segment_payload_header_size) return null;
719 switch (payload[0]) {
720 segment_payload_tag => {
721 const count = std.mem.readInt(u32, payload[1..5], .big);
722 const expected_size = segmentPayloadSize(segment_payload_header_size, segment_payload_entry_size, count) orelse return null;
723 if (payload.len != expected_size) return null;
724 return count;
725 },
726 compact_segment_payload_tag => {
727 if (payload.len < compact_segment_payload_header_size) return null;
728 const count = std.mem.readInt(u32, payload[1..5], .big);
729 const expected_size = segmentPayloadSize(compact_segment_payload_header_size, compact_segment_payload_entry_size, count) orelse return null;
730 if (payload.len != expected_size) return null;
731 return count;
732 },
733 stream_segment_payload_tag => {
734 if (payload.len < stream_segment_payload_header_size) return null;
735 const count = std.mem.readInt(u32, payload[1..5], .big);
736 if (count < segment_min_postings) return null;
737 const first_rowid = std.mem.readInt(i64, payload[5..13], .big);
738 if (first_rowid < 0) return null;
739 const last_delta = std.mem.readInt(u32, payload[13..17], .big);
740 _ = std.math.add(i64, first_rowid, last_delta) catch return null;
741 const value_count = std.math.mul(usize, count, 2) catch return null;
742 const control_count = vbyte.controlByteCount(value_count);
743 const minimum_stream_size = std.math.add(usize, control_count, value_count) catch return null;
744 const maximum_data_size = std.math.mul(usize, value_count, 4) catch return null;
745 const maximum_stream_size = std.math.add(usize, control_count, maximum_data_size) catch return null;
746 const stream_size = payload.len - stream_segment_payload_header_size;
747 if (stream_size < minimum_stream_size or stream_size > maximum_stream_size) return null;
748 if (value_count % 4 != 0 and payload[stream_segment_payload_header_size + control_count - 1] >> @intCast((value_count % 4) * 2) != 0) return null;
749 return count;
750 },
751 else => return null,
752 }
753 }
754
755 pub fn lengthSegmentPayloadCount(payload: []const u8) ?usize {
756 if (payload.len < segment_payload_header_size or payload[0] != length_segment_payload_tag) return null;
757 const count = std.mem.readInt(u32, payload[1..5], .big);
758 const expected_size = segmentPayloadSize(segment_payload_header_size, segment_payload_entry_size, count) orelse return null;
759 if (payload.len != expected_size) return null;
760 return count;
761 }
762
763 pub fn segmentPayloadHit(payload: []const u8, index: usize) engine_mod.Error!hit_mod.Hit {
764 const count = segmentPayloadCount(payload) orelse return error.InvalidSearchIndex;
765 if (index >= count) return error.InvalidSearchIndex;
766 if (payload[0] == stream_segment_payload_tag) {
767 var decoder = try SegmentDecoder.initValidated(payload, count);
768 var current_index: usize = 0;
769 while (current_index < index) : (current_index += 1) try decoder.advance();
770 return (try decoder.current()) orelse error.InvalidSearchIndex;
771 }
772 return try fixedSegmentPayloadHit(payload, count, index);
773 }
774
775 fn fixedSegmentPayloadHit(payload: []const u8, count: usize, index: usize) engine_mod.Error!hit_mod.Hit {
776 if (index >= count) return error.InvalidSearchIndex;
777 switch (payload[0]) {
778 segment_payload_tag => {
779 const offset = segment_payload_header_size + index * segment_payload_entry_size;
780 const rowid = std.mem.readInt(i64, payload[offset..][0..8], .big);
781 const score = std.mem.readInt(u32, payload[offset + 8 ..][0..4], .big);
782 if (score == 0) return error.InvalidSearchIndex;
783 return .{ .rowid = rowid, .score = score };
784 },
785 compact_segment_payload_tag => {
786 const first_rowid = std.mem.readInt(i64, payload[5..13], .big);
787 const offset = compact_segment_payload_header_size + index * compact_segment_payload_entry_size;
788 const rowid_delta = std.mem.readInt(u32, payload[offset..][0..4], .big);
789 const score = std.mem.readInt(u16, payload[offset + 4 ..][0..2], .big);
790 if (score == 0) return error.InvalidSearchIndex;
791 const rowid = std.math.add(i64, first_rowid, rowid_delta) catch return error.InvalidSearchIndex;
792 return .{ .rowid = rowid, .score = score };
793 },
794 else => return error.InvalidSearchIndex,
795 }
796 }
797
798 pub const SegmentBounds = struct {
799 first: i64,
800 last: i64,
801 };
802
803 pub fn segmentPayloadBounds(payload: []const u8) engine_mod.Error!SegmentBounds {
804 const count = segmentPayloadCount(payload) orelse return error.InvalidSearchIndex;
805 if (count == 0) return error.InvalidSearchIndex;
806 switch (payload[0]) {
807 segment_payload_tag, compact_segment_payload_tag => {
808 const first = try fixedSegmentPayloadHit(payload, count, 0);
809 const last = try fixedSegmentPayloadHit(payload, count, count - 1);
810 return .{ .first = first.rowid, .last = last.rowid };
811 },
812 stream_segment_payload_tag => {
813 const first = std.mem.readInt(i64, payload[5..13], .big);
814 const last_delta = std.mem.readInt(u32, payload[13..17], .big);
815 const last = std.math.add(i64, first, last_delta) catch return error.InvalidSearchIndex;
816 return .{ .first = first, .last = last };
817 },
818 else => return error.InvalidSearchIndex,
819 }
820 }
821
822 pub fn lengthSegmentPayloadValue(payload: []const u8, index: usize) engine_mod.Error!DocumentLength {
823 const count = lengthSegmentPayloadCount(payload) orelse return error.InvalidSearchIndex;
824 if (index >= count) return error.InvalidSearchIndex;
825 const offset = segment_payload_header_size + index * segment_payload_entry_size;
826 const rowid = std.mem.readInt(i64, payload[offset..][0..8], .big);
827 const value = std.mem.readInt(u32, payload[offset + 8 ..][0..4], .big);
828 if (value == document_length_tombstone) return error.InvalidSearchIndex;
829 return .{ .rowid = rowid, .length = value };
830 }
831
832 pub fn directPostingLess(_: void, left: DirectPosting, right: DirectPosting) bool {
833 if (left.rowid != right.rowid) return left.rowid < right.rowid;
834 return left.score < right.score;
835 }
836
837 pub fn directDocumentLengthLess(_: void, left: DirectDocumentLength, right: DirectDocumentLength) bool {
838 return left.rowid < right.rowid;
839 }
840
841 pub fn documentLengthLess(_: void, left: DocumentLength, right: DocumentLength) bool {
842 return left.rowid < right.rowid;
843 }
844
845 pub fn postingKey(allocator: Allocator, kind: u8, token: []const u8) engine_mod.Error![]u8 {
846 const out = try allocator.alloc(u8, token.len + 1);
847 out[0] = kind;
848 @memcpy(out[1..], token);
849 return out;
850 }
851
852 pub fn phrasePairPostingKeyLower(allocator: Allocator, first: []const u8, second: []const u8) engine_mod.Error![]u8 {
853 const out = try allocator.alloc(u8, first.len + second.len + 2);
854 out[0] = phrase_pair_posting_kind;
855 for (first, 0..) |byte, index| out[index + 1] = std.ascii.toLower(byte);
856 out[first.len + 1] = ' ';
857 for (second, 0..) |byte, index| out[first.len + 2 + index] = std.ascii.toLower(byte);
858 return out;
859 }
860
861 pub fn postingKeyBuffer(buffer: *[token_mod.max_token_bytes + 1]u8, kind: u8, token: []const u8) []const u8 {
862 std.debug.assert(token.len <= token_mod.max_token_bytes);
863 buffer[0] = kind;
864 @memcpy(buffer[1..][0..token.len], token);
865 return buffer[0 .. token.len + 1];
866 }
867
868 pub fn phrasePairPostingKeyBuffer(buffer: *[phrase_pair_posting_key_max_bytes]u8, first: []const u8, second: []const u8) []const u8 {
869 std.debug.assert(first.len <= token_mod.max_token_bytes);
870 std.debug.assert(second.len <= token_mod.max_token_bytes);
871 buffer[0] = phrase_pair_posting_kind;
872 @memcpy(buffer[1..][0..first.len], first);
873 buffer[first.len + 1] = ' ';
874 @memcpy(buffer[first.len + 2 ..][0..second.len], second);
875 return buffer[0 .. first.len + second.len + 2];
876 }
877
878 pub fn postingKeyLowerBuffer(buffer: *[token_mod.max_token_bytes + 1]u8, kind: u8, token: []const u8, len: usize) []const u8 {
879 std.debug.assert(len <= token.len);
880 std.debug.assert(len <= token_mod.max_token_bytes);
881 buffer[0] = kind;
882 for (token[0..len], 0..) |byte, index| buffer[index + 1] = std.ascii.toLower(byte);
883 return buffer[0 .. len + 1];
884 }
885
886 pub fn phrasePairPostingKeyLowerBuffer(buffer: *[phrase_pair_posting_key_max_bytes]u8, first: []const u8, second: []const u8) []const u8 {
887 std.debug.assert(first.len <= token_mod.max_token_bytes);
888 std.debug.assert(second.len <= token_mod.max_token_bytes);
889 buffer[0] = phrase_pair_posting_kind;
890 for (first, 0..) |byte, index| buffer[index + 1] = std.ascii.toLower(byte);
891 buffer[first.len + 1] = ' ';
892 for (second, 0..) |byte, index| buffer[first.len + 2 + index] = std.ascii.toLower(byte);
893 return buffer[0 .. first.len + second.len + 2];
894 }
895
896 pub fn prefixEndBuffer(buffer: *[token_mod.max_token_bytes + 2]u8, prefix: []const u8) []const u8 {
897 std.debug.assert(prefix.len <= token_mod.max_token_bytes + 1);
898 @memcpy(buffer[0..prefix.len], prefix);
899 buffer[prefix.len] = 0xff;
900 return buffer[0 .. prefix.len + 1];
901 }
902
903 pub fn postingScore(payload: []const u8) engine_mod.Error!usize {
904 const count = try postingPayloadCount(payload);
905 if (count == 0) return error.InvalidSearchIndex;
906 return count;
907 }
908
909 pub fn postingPayloadCount(payload: []const u8) engine_mod.Error!usize {
910 if (payload.len != posting_payload_size) return error.InvalidSearchIndex;
911 return std.mem.readInt(u32, payload[0..posting_payload_size], .big);
912 }
913
914 pub fn collectPartialPhrasePairPostings(allocator: Allocator, documents: []const engine_mod.Document, postings: *std.ArrayList(Posting), keys: *std.ArrayList([]const u8)) engine_mod.Error!void {
915 var by_hash = std.AutoHashMap(u64, usize).init(allocator);
916 defer by_hash.deinit();
917 var accumulators: std.ArrayList(PhrasePairAccumulator) = .empty;
918 defer accumulators.deinit(allocator);
919
920 for (documents) |document| {
921 const text = token_mod.documentText(document.text);
922 var offset: usize = 0;
923 var position: usize = 0;
924 var field: usize = 0;
925 var previous_text: []const u8 = &.{};
926 var previous_position: usize = 0;
927 var previous_field: usize = 0;
928 var have_previous = false;
929 while (text_mod.nextTextToken(text, &offset, &position, &field)) |token| {
930 if (have_previous and token.field == previous_field and token.position == previous_position + 1) {
931 try appendPartialPhrasePairOccurrence(allocator, postings, keys, &accumulators, &by_hash, document.rowid, previous_text, token.text);
932 }
933 previous_text = token.text;
934 previous_position = token.position;
935 previous_field = token.field;
936 have_previous = true;
937 }
938 }
939 }
940
941 pub fn appendPartialPhrasePairOccurrence(
942 allocator: Allocator,
943 postings: *std.ArrayList(Posting),
944 keys: *std.ArrayList([]const u8),
945 accumulators: *std.ArrayList(PhrasePairAccumulator),
946 by_hash: *std.AutoHashMap(u64, usize),
947 rowid: i64,
948 first: []const u8,
949 second: []const u8,
950 ) engine_mod.Error!void {
951 const hash = phrasePairSliceHash(first, second);
952 const entry = try by_hash.getOrPut(hash);
953 if (!entry.found_existing) {
954 const index = accumulators.items.len;
955 try accumulators.append(allocator, .{ .first = first, .second = second, .first_rowid = rowid });
956 entry.value_ptr.* = index;
957 return;
958 }
959
960 var index = entry.value_ptr.*;
961 while (true) {
962 if (phrasePairSlicesMatch(accumulators.items[index], first, second)) {
963 return try appendPartialPhrasePairPosting(allocator, postings, keys, &accumulators.items[index], rowid);
964 }
965 if (accumulators.items[index].next) |next| {
966 index = next;
967 continue;
968 }
969 const next = accumulators.items.len;
970 try accumulators.append(allocator, .{ .first = first, .second = second, .first_rowid = rowid });
971 accumulators.items[index].next = next;
972 return;
973 }
974 }
975
976 pub fn appendPartialPhrasePairPosting(allocator: Allocator, postings: *std.ArrayList(Posting), keys: *std.ArrayList([]const u8), accumulator: *PhrasePairAccumulator, rowid: i64) engine_mod.Error!void {
977 if (accumulator.key_index) |key_index| {
978 if (accumulator.last_rowid == rowid) {
979 postings.items[accumulator.last_posting_index].count = std.math.add(u32, postings.items[accumulator.last_posting_index].count, 1) catch return error.InvalidSearchIndex;
980 return;
981 }
982 try postings.append(allocator, .{ .rowid = rowid, .key_index = key_index, .count = 1 });
983 accumulator.last_rowid = rowid;
984 accumulator.last_posting_index = postings.items.len - 1;
985 return;
986 }
987 if (accumulator.first_rowid == rowid) {
988 accumulator.first_count = std.math.add(u32, accumulator.first_count, 1) catch return error.InvalidSearchIndex;
989 return;
990 }
991 const key = try phrasePairPostingKeyLower(allocator, accumulator.first, accumulator.second);
992 errdefer allocator.free(key);
993 try postings.ensureUnusedCapacity(allocator, 2);
994 const key_index = std.math.cast(u32, keys.items.len) orelse return error.InvalidSearchIndex;
995 try keys.append(allocator, key);
996 postings.appendAssumeCapacity(.{ .rowid = accumulator.first_rowid, .key_index = key_index, .count = accumulator.first_count });
997 postings.appendAssumeCapacity(.{ .rowid = rowid, .key_index = key_index, .count = 1 });
998 accumulator.key_index = key_index;
999 accumulator.last_rowid = rowid;
1000 accumulator.last_posting_index = postings.items.len - 1;
1001 }
1002
1003 pub fn phrasePairSlicesMatch(accumulator: PhrasePairAccumulator, first: []const u8, second: []const u8) bool {
1004 return token_mod.asciiEqlIgnoreCase(accumulator.first, first) and token_mod.asciiEqlIgnoreCase(accumulator.second, second);
1005 }
1006
1007 pub fn phrasePairSliceHash(first: []const u8, second: []const u8) u64 {
1008 var hash: u64 = 14695981039346656037;
1009 hash = updatePhrasePairHashByte(hash, phrase_pair_posting_kind);
1010 for (first) |byte| hash = updatePhrasePairHashByte(hash, std.ascii.toLower(byte));
1011 hash = updatePhrasePairHashByte(hash, ' ');
1012 for (second) |byte| hash = updatePhrasePairHashByte(hash, std.ascii.toLower(byte));
1013 return hash;
1014 }
1015
1016 pub fn updatePhrasePairHashByte(hash: u64, byte: u8) u64 {
1017 return (hash ^ byte) *% 1099511628211;
1018 }
1019
1020 pub fn incrementTokenTermCount(allocator: Allocator, counts: *std.ArrayList(TermCount), kind: u8, token: []const u8, len: usize) engine_mod.Error!void {
1021 for (counts.items) |*existing| {
1022 if (postingKeyMatchesToken(existing.key, kind, token, len)) {
1023 existing.count += 1;
1024 return;
1025 }
1026 }
1027 try counts.append(allocator, .{ .key = try postingKeyLower(allocator, kind, token, len), .count = 1 });
1028 }
1029
1030 pub fn incrementPhrasePairTermCount(allocator: Allocator, counts: *std.ArrayList(TermCount), first: []const u8, second: []const u8) engine_mod.Error!void {
1031 for (counts.items) |*existing| {
1032 if (postingKeyMatchesPhrasePair(existing.key, first, second)) {
1033 existing.count += 1;
1034 return;
1035 }
1036 }
1037 try counts.append(allocator, .{ .key = try phrasePairPostingKeyLower(allocator, first, second), .count = 1 });
1038 }
1039
1040 pub fn incrementInternedTokenTermCount(
1041 allocator: Allocator,
1042 counts: []TermCount,
1043 count: *usize,
1044 key_map: *PostingKeyMap,
1045 keys: *std.ArrayList([]const u8),
1046 kind: u8,
1047 token: []const u8,
1048 len: usize,
1049 ) engine_mod.Error!void {
1050 for (counts[0..count.*]) |*existing| {
1051 if (postingKeyMatchesToken(existing.key, kind, token, len)) {
1052 existing.count += 1;
1053 return;
1054 }
1055 }
1056 std.debug.assert(count.* < counts.len);
1057 const key_index = try internTokenPostingKey(allocator, key_map, keys, kind, token, len);
1058 counts[count.*] = .{ .key = keys.items[key_index], .count = 1 };
1059 count.* += 1;
1060 }
1061
1062 pub fn incrementInternedPhrasePairTermCount(
1063 allocator: Allocator,
1064 counts: []TermCount,
1065 count: *usize,
1066 key_map: *PostingKeyMap,
1067 keys: *std.ArrayList([]const u8),
1068 first: []const u8,
1069 second: []const u8,
1070 ) engine_mod.Error!void {
1071 for (counts[0..count.*]) |*existing| {
1072 if (postingKeyMatchesPhrasePair(existing.key, first, second)) {
1073 existing.count += 1;
1074 return;
1075 }
1076 }
1077 std.debug.assert(count.* < counts.len);
1078 const key_index = try internPhrasePairPostingKey(allocator, key_map, keys, first, second);
1079 counts[count.*] = .{ .key = keys.items[key_index], .count = 1 };
1080 count.* += 1;
1081 }
1082
1083 pub fn postingKeyMatchesToken(key_text: []const u8, kind: u8, token: []const u8, len: usize) bool {
1084 if (key_text.len != len + 1 or key_text[0] != kind) return false;
1085 for (key_text[1..], token[0..len]) |left, right| if (left != std.ascii.toLower(right)) return false;
1086 return true;
1087 }
1088
1089 pub fn postingKeyMatchesPhrasePair(key_text: []const u8, first: []const u8, second: []const u8) bool {
1090 if (key_text.len != first.len + second.len + 2 or key_text[0] != phrase_pair_posting_kind or key_text[first.len + 1] != ' ') return false;
1091 for (key_text[1..][0..first.len], first) |left, right| if (left != std.ascii.toLower(right)) return false;
1092 for (key_text[first.len + 2 ..], second) |left, right| if (left != std.ascii.toLower(right)) return false;
1093 return true;
1094 }
1095
1096 pub fn isPhrasePairPostingKey(key_text: []const u8) bool {
1097 return key_text.len != 0 and key_text[0] == phrase_pair_posting_kind;
1098 }
1099
1100 pub fn postingKeyLower(allocator: Allocator, kind: u8, token: []const u8, len: usize) engine_mod.Error![]u8 {
1101 const out = try allocator.alloc(u8, len + 1);
1102 out[0] = kind;
1103 for (token[0..len], 0..) |byte, index| out[index + 1] = std.ascii.toLower(byte);
1104 return out;
1105 }
1106
1107 pub fn internTokenPostingKey(allocator: Allocator, key_map: *PostingKeyMap, keys: *std.ArrayList([]const u8), kind: u8, token: []const u8, len: usize) engine_mod.Error!u32 {
1108 var buffer: [token_mod.max_token_bytes + 1]u8 = undefined;
1109 const key_text = postingKeyLowerBuffer(&buffer, kind, token, len);
1110 return try internPostingKeyText(allocator, key_map, keys, key_text);
1111 }
1112
1113 pub fn internPhrasePairPostingKey(allocator: Allocator, key_map: *PostingKeyMap, keys: *std.ArrayList([]const u8), first: []const u8, second: []const u8) engine_mod.Error!u32 {
1114 var buffer: [phrase_pair_posting_key_max_bytes]u8 = undefined;
1115 const key_text = phrasePairPostingKeyLowerBuffer(&buffer, first, second);
1116 return try internPostingKeyText(allocator, key_map, keys, key_text);
1117 }
1118
1119 pub fn internPostingKeyText(allocator: Allocator, key_map: *PostingKeyMap, keys: *std.ArrayList([]const u8), key_text: []const u8) engine_mod.Error!u32 {
1120 if (key_map.get(key_text)) |key_index| return key_index;
1121 const key_index = std.math.cast(u32, keys.items.len) orelse return error.InvalidSearchIndex;
1122 const owned = try allocator.dupe(u8, key_text);
1123 errdefer allocator.free(owned);
1124 try keys.append(allocator, owned);
1125 errdefer _ = keys.pop();
1126 try key_map.put(owned, key_index);
1127 return key_index;
1128 }
1129
1130 pub fn deinitStringList(allocator: Allocator, strings: *std.ArrayList([]const u8)) void {
1131 for (strings.items) |string| allocator.free(string);
1132 strings.deinit(allocator);
1133 }
1134
1135 pub fn freeStringSlice(allocator: Allocator, strings: []const []const u8) void {
1136 for (strings) |string| allocator.free(string);
1137 if (strings.len != 0) allocator.free(strings);
1138 }
1139
1140 pub fn freeTermCounts(allocator: Allocator, counts: []const TermCount) void {
1141 for (counts) |term_count| allocator.free(term_count.key);
1142 allocator.free(counts);
1143 }
1144
1145 pub fn postingLess(keys: []const []const u8, left: Posting, right: Posting) bool {
1146 std.debug.assert(left.key_index < keys.len);
1147 std.debug.assert(right.key_index < keys.len);
1148 const order = std.mem.order(u8, keys[left.key_index], keys[right.key_index]);
1149 if (order != .eq) return order == .lt;
1150 if (left.rowid != right.rowid) return left.rowid < right.rowid;
1151 if (left.count != right.count) return left.count < right.count;
1152 return false;
1153 }
1154
1155 fn expectInternedTermCounts(text: []const u8, index_prefixes: bool, index_phrase_pairs: bool, expected_capacity: usize) !void {
1156 const allocator = std.testing.allocator;
1157 const expected = try documentTermCounts(allocator, text, index_prefixes, index_phrase_pairs);
1158 defer freeTermCounts(allocator, expected);
1159 const capacity = try documentTermCountCapacity(text, index_prefixes, index_phrase_pairs);
1160 try std.testing.expectEqual(expected_capacity, capacity);
1161 const scratch: []TermCount = if (capacity == 0) &.{} else try allocator.alloc(TermCount, capacity);
1162 defer if (scratch.len != 0) allocator.free(scratch);
1163 var key_map = PostingKeyMap.init(allocator);
1164 defer key_map.deinit();
1165 var keys: std.ArrayList([]const u8) = .empty;
1166 defer deinitStringList(allocator, &keys);
1167 const actual = try documentInternedTermCounts(allocator, text, index_prefixes, index_phrase_pairs, &key_map, &keys, scratch);
1168 try std.testing.expect(actual.len <= capacity);
1169 try std.testing.expectEqual(expected.len, actual.len);
1170 for (expected, actual) |expected_count, actual_count| {
1171 try std.testing.expectEqualStrings(expected_count.key, actual_count.key);
1172 try std.testing.expectEqual(expected_count.count, actual_count.count);
1173 }
1174 }
1175
1176 test "search interned term counts fit actual document capacity" {
1177 const allocator = std.testing.allocator;
1178 try expectInternedTermCounts("", false, false, 0);
1179 try expectInternedTermCounts("alpha alpha beta", false, false, 3);
1180 try expectInternedTermCounts("alpha beta alpha", false, true, 5);
1181 try expectInternedTermCounts("alpha\x1fbeta", false, true, 2);
1182 try expectInternedTermCounts("abc abc", true, false, 8);
1183
1184 var skipped: [token_mod.max_token_bytes + 1]u8 = undefined;
1185 @memset(&skipped, 'x');
1186 const skipped_text = try std.fmt.allocPrint(allocator, "alpha {s} beta", .{skipped[0..]});
1187 defer allocator.free(skipped_text);
1188 try expectInternedTermCounts(skipped_text, false, true, 2);
1189 }
1190
1191 test "search interned term counts reuse caller scratch without allocation" {
1192 const allocator = std.testing.allocator;
1193 const text = "alpha beta alpha";
1194 const capacity = try documentTermCountCapacity(text, false, true);
1195 const scratch = try allocator.alloc(TermCount, capacity);
1196 defer allocator.free(scratch);
1197 var key_map = PostingKeyMap.init(allocator);
1198 defer key_map.deinit();
1199 var keys: std.ArrayList([]const u8) = .empty;
1200 defer deinitStringList(allocator, &keys);
1201 const first = try documentInternedTermCounts(allocator, text, false, true, &key_map, &keys, scratch);
1202 const expected = [_]TermCount{
1203 .{ .key = "=alpha", .count = 2 },
1204 .{ .key = "=beta", .count = 1 },
1205 .{ .key = "\"alpha beta", .count = 1 },
1206 .{ .key = "\"beta alpha", .count = 1 },
1207 };
1208 try std.testing.expectEqual(expected.len, first.len);
1209 for (&expected, first) |expected_count, actual_count| {
1210 try std.testing.expectEqualStrings(expected_count.key, actual_count.key);
1211 try std.testing.expectEqual(expected_count.count, actual_count.count);
1212 }
1213
1214 var failing = std.testing.FailingAllocator.init(allocator, .{ .fail_index = 0 });
1215 const second = try documentInternedTermCounts(failing.allocator(), text, false, true, &key_map, &keys, scratch);
1216 try std.testing.expect(!failing.has_induced_failure);
1217 try std.testing.expectEqual(expected.len, second.len);
1218 for (&expected, second) |expected_count, actual_count| {
1219 try std.testing.expectEqualStrings(expected_count.key, actual_count.key);
1220 try std.testing.expectEqual(expected_count.count, actual_count.count);
1221 }
1222 }
1223
1224 test "search segment payload uses Stream VByte for dense scores" {
1225 const postings = [_]Posting{
1226 .{ .rowid = 10, .key_index = 0, .count = 1 },
1227 .{ .rowid = 12, .key_index = 0, .count = 3 },
1228 .{ .rowid = 15, .key_index = 0, .count = 5 },
1229 };
1230 const payload = try postingSegmentPayload(std.testing.allocator, &postings);
1231 defer std.testing.allocator.free(payload);
1232 try std.testing.expectEqual(stream_segment_payload_tag, payload[0]);
1233 try std.testing.expectEqual(@as(usize, 25), payload.len);
1234 try std.testing.expectEqual(@as(usize, postings.len), segmentPayloadCount(payload).?);
1235 const hit = try segmentPayloadHit(payload, 2);
1236 try std.testing.expectEqual(@as(i64, 15), hit.rowid);
1237 try std.testing.expectEqual(@as(usize, 5), hit.score);
1238
1239 var decoder = try SegmentDecoder.init(payload);
1240 for (postings) |posting| {
1241 const current = (try decoder.current()).?;
1242 try std.testing.expectEqual(posting.rowid, current.rowid);
1243 try std.testing.expectEqual(@as(usize, posting.count), current.score);
1244 try decoder.advance();
1245 }
1246 try std.testing.expectEqual(@as(?hit_mod.Hit, null), try decoder.current());
1247 decoder.reset();
1248 try std.testing.expectEqual(@as(i64, 10), (try decoder.current()).?.rowid);
1249 }
1250
1251 test "search bulk postings keep compact key indexes" {
1252 try std.testing.expectEqual(@as(usize, 16), @sizeOf(Posting));
1253 const keys = [_][]const u8{ "=beta", "=alpha" };
1254 const key_slice: []const []const u8 = &keys;
1255 var postings = [_]Posting{
1256 .{ .rowid = 12, .key_index = 0, .count = 3 },
1257 .{ .rowid = 15, .key_index = 1, .count = 5 },
1258 .{ .rowid = 10, .key_index = 1, .count = 1 },
1259 };
1260 std.mem.sort(Posting, &postings, key_slice, postingLess);
1261 try std.testing.expectEqual(@as(u32, 1), postings[0].key_index);
1262 try std.testing.expectEqual(@as(i64, 10), postings[0].rowid);
1263 try std.testing.expectEqual(@as(u32, 1), postings[1].key_index);
1264 try std.testing.expectEqual(@as(i64, 15), postings[1].rowid);
1265 try std.testing.expectEqual(@as(u32, 0), postings[2].key_index);
1266 }
1267
1268 test "search segment payload uses Stream VByte for wide scores" {
1269 const postings = [_]Posting{
1270 .{ .rowid = 1, .key_index = 0, .count = std.math.maxInt(u16) + 1 },
1271 .{ .rowid = 2, .key_index = 0, .count = std.math.maxInt(u16) + 2 },
1272 };
1273 const payload = try postingSegmentPayload(std.testing.allocator, &postings);
1274 defer std.testing.allocator.free(payload);
1275 try std.testing.expectEqual(stream_segment_payload_tag, payload[0]);
1276 try std.testing.expectEqual(@as(usize, 26), payload.len);
1277 try std.testing.expectEqual(@as(usize, postings.len), segmentPayloadCount(payload).?);
1278 const hit = try segmentPayloadHit(payload, 1);
1279 try std.testing.expectEqual(@as(i64, 2), hit.rowid);
1280 try std.testing.expectEqual(@as(usize, std.math.maxInt(u16) + 2), hit.score);
1281 }
1282
1283 test "search segment payload keeps smaller compact and required wide forms" {
1284 const compact_postings = [_]Posting{
1285 .{ .rowid = 0, .key_index = 0, .count = std.math.maxInt(u16) },
1286 .{ .rowid = std.math.maxInt(u32), .key_index = 0, .count = std.math.maxInt(u16) },
1287 };
1288 const compact = try postingSegmentPayload(std.testing.allocator, &compact_postings);
1289 defer std.testing.allocator.free(compact);
1290 try std.testing.expectEqual(compact_segment_payload_tag, compact[0]);
1291 try std.testing.expectEqual(@as(usize, 25), compact.len);
1292 try std.testing.expectEqual(@as(i64, std.math.maxInt(u32)), (try segmentPayloadHit(compact, 1)).rowid);
1293
1294 const wide_postings = [_]Posting{
1295 .{ .rowid = 0, .key_index = 0, .count = 1 },
1296 .{ .rowid = @as(i64, std.math.maxInt(u32)) + 1, .key_index = 0, .count = 2 },
1297 };
1298 const wide = try postingSegmentPayload(std.testing.allocator, &wide_postings);
1299 defer std.testing.allocator.free(wide);
1300 try std.testing.expectEqual(segment_payload_tag, wide[0]);
1301 try std.testing.expectEqual(@as(usize, 29), wide.len);
1302 try std.testing.expectEqual(@as(i64, std.math.maxInt(u32)) + 1, (try segmentPayloadHit(wide, 1)).rowid);
1303 }
1304
1305 test "search Stream VByte segment rejects invalid gaps scores and bounds" {
1306 const postings = [_]Posting{
1307 .{ .rowid = 10, .key_index = 0, .count = 1 },
1308 .{ .rowid = 12, .key_index = 0, .count = 3 },
1309 .{ .rowid = 15, .key_index = 0, .count = 5 },
1310 };
1311 const payload = try postingSegmentPayload(std.testing.allocator, &postings);
1312 defer std.testing.allocator.free(payload);
1313 const data_offset = stream_segment_payload_header_size + vbyte.controlByteCount(postings.len * 2);
1314
1315 const zero_gap = try std.testing.allocator.dupe(u8, payload);
1316 defer std.testing.allocator.free(zero_gap);
1317 zero_gap[data_offset + 2] = 0;
1318 try std.testing.expectError(error.InvalidSearchIndex, segmentPayloadHit(zero_gap, 0));
1319
1320 const zero_score = try std.testing.allocator.dupe(u8, payload);
1321 defer std.testing.allocator.free(zero_score);
1322 zero_score[data_offset + 1] = 0;
1323 try std.testing.expectError(error.InvalidSearchIndex, segmentPayloadHit(zero_score, 0));
1324
1325 const wrong_last = try std.testing.allocator.dupe(u8, payload);
1326 defer std.testing.allocator.free(wrong_last);
1327 std.mem.writeInt(u32, wrong_last[13..17], 4, .big);
1328 try std.testing.expectError(error.InvalidSearchIndex, segmentPayloadHit(wrong_last, postings.len - 1));
1329 }