atagen

macltok

public
Star0
Watch0
419c65426a62191a26b47d07a0e0661e047317da
3
ssh://brewery@pls.lobotomise.me:33/atagen/macltok.git
src/search/index.rsRust832 lines27.9 KB
1
use std::{collections::HashMap, path::PathBuf, sync::Arc};
2
3
use sha2::{Digest, Sha256};
4
use tantivy::{
5
    DocAddress, DocId, DocSet, Index, IndexSettings, ReloadPolicy, Score, Searcher, SegmentReader,
6
    TantivyDocument, Term,
7
    collector::{Collector, SegmentCollector},
8
    directory::{Directory, OwnedBytes, RamDirectory},
9
    fastfield::{AliveBitSet, write_alive_bitset},
10
    indexer::{SingleSegmentIndexWriter, merge_filtered_segments},
11
    query::{BooleanQuery, Occur, Query, TermSetQuery},
12
    schema::{
13
        FAST, Field, IndexRecordOption, STORED, STRING, Schema, TextFieldIndexing, TextOptions,
14
        Value,
15
    },
16
};
17
use tantivy_common::BitSet;
18
19
use super::{
20
    MessageIndex,
21
    text::{TOKENIZER, analyzer, build_query},
22
};
23
use crate::{Error, ErrorKind};
24
25
const WRITER_BUDGET: usize = 4_000_000;
26
/// segments of a size class merge once there are this many of them
27
const MERGE_FACTOR: usize = 6;
28
/// decompressed docstore blocks a searcher keeps per segment, tantivy's default is 100
29
const DOCSTORE_BLOCKS: usize = 2;
30
31
#[derive(Clone, Debug, Eq, PartialEq)]
32
pub(crate) struct Doc {
33
    pub(crate) key: String,
34
    pub(crate) room: String,
35
    pub(crate) sender: String,
36
    /// the original's, or the edit's while the original hasn't turned up
37
    pub(crate) ts: u64,
38
    /// the event whose text is indexed, the original or its latest edit
39
    pub(crate) content: String,
40
    pub(crate) content_ts: u64,
41
    /// only kept for provisional docs, read back empty otherwise
42
    pub(crate) text: String,
43
    /// an edit seen before its original, under `provisional_key`. it's kept out of results,
44
    /// since its timestamp moves to the original's once that turns up
45
    pub(crate) provisional: bool,
46
}
47
48
/// one per target and edit sender, so an edit from anyone else can't crowd out the author's
49
pub(crate) fn provisional_key(target: &str, sender: &str) -> String {
50
    format!("{target}\n{sender}")
51
}
52
53
#[derive(Clone, Debug, Eq, PartialEq)]
54
pub(crate) struct Hit {
55
    pub(crate) key: String,
56
    pub(crate) room: String,
57
    pub(crate) sender: String,
58
    pub(crate) content: String,
59
    pub(crate) ts: u64,
60
    pub(crate) tie: u64,
61
}
62
63
struct SegmentRecord {
64
    id: u64,
65
    del_gen: u64,
66
}
67
68
#[derive(Default)]
69
pub(crate) struct Changes {
70
    pub(crate) puts: Vec<(String, Vec<u8>)>,
71
    pub(crate) deletes: Vec<String>,
72
    /// the index as it stands once these land, which is what has to be saved with them
73
    pub(crate) manifest: serde_json::Value,
74
    files: Vec<u64>,
75
    dels: Vec<(u64, u64)>,
76
    removed: Vec<u64>,
77
}
78
79
#[derive(Clone, Copy)]
80
struct Fields {
81
    key: Field,
82
    room: Field,
83
    sender: Field,
84
    content: Field,
85
    text: Field,
86
    ts: Field,
87
    tie: Field,
88
    content_ts: Field,
89
    pending: Field,
90
    target: Field,
91
}
92
93
struct Segment {
94
    id: u64,
95
    raw: RamDirectory,
96
    index: Index,
97
    searcher: Searcher,
98
    alive: Arc<BitSet>,
99
    max_doc: u32,
100
    del_gen: u64,
101
    persisted: bool,
102
    deletes_dirty: bool,
103
}
104
105
impl Segment {
106
    fn live(&self) -> usize {
107
        self.alive.len()
108
    }
109
}
110
111
pub(crate) struct KeywordIndex {
112
    schema: Schema,
113
    fields: Fields,
114
    settings: IndexSettings,
115
    segments: Vec<Segment>,
116
    buffer: HashMap<String, Doc>,
117
    next_id: u64,
118
    persistent: bool,
119
    /// merged away since the last commit, with the delete generation they were persisted at
120
    removed: Vec<(u64, bool, u64)>,
121
}
122
123
fn schema() -> (Schema, Fields) {
124
    let mut builder = Schema::builder();
125
    let text_options = TextOptions::default().set_indexing_options(
126
        TextFieldIndexing::default()
127
            .set_tokenizer(TOKENIZER)
128
            .set_index_option(IndexRecordOption::WithFreqsAndPositions),
129
    );
130
    let fields = Fields {
131
        key: builder.add_text_field("key", STRING | STORED),
132
        room: builder.add_text_field("room", STRING | STORED),
133
        sender: builder.add_text_field("sender", STRING | STORED),
134
        content: builder.add_text_field("content", STRING | STORED),
135
        text: builder.add_text_field("text", text_options),
136
        ts: builder.add_u64_field("ts", FAST | STORED),
137
        tie: builder.add_u64_field("tie", FAST),
138
        content_ts: builder.add_u64_field("content_ts", STORED),
139
        pending: builder.add_text_field("pending", STORED),
140
        target: builder.add_text_field("target", STRING),
141
    };
142
    (builder.build(), fields)
143
}
144
145
fn tie(key: &str) -> u64 {
146
    let digest = Sha256::digest(key.as_bytes());
147
    u64::from_le_bytes(digest[..8].try_into().expect("a sha256 digest is 32 bytes"))
148
}
149
150
fn settings() -> IndexSettings {
151
    // the dedicated compressor is a thread, and wasm32-unknown-unknown has none
152
    IndexSettings {
153
        docstore_compress_dedicated_thread: false,
154
        ..IndexSettings::default()
155
    }
156
}
157
158
fn tantivy_error(
159
    context: &'static str,
160
    error: impl std::error::Error + Send + Sync + 'static,
161
) -> Error {
162
    Error::with_source(ErrorKind::Store, context, error)
163
}
164
165
fn open_segment(id: u64, raw: RamDirectory, max_doc_hint: Option<u32>) -> Result<Segment, Error> {
166
    let index = Index::open(raw.clone())
167
        .map_err(|error| tantivy_error("opening a search segment", error))?;
168
    index.tokenizers().register(TOKENIZER, analyzer());
169
    let reader = index
170
        .reader_builder()
171
        .reload_policy(ReloadPolicy::Manual)
172
        .doc_store_cache_num_blocks(DOCSTORE_BLOCKS)
173
        .try_into()
174
        .map_err(|error| tantivy_error("reading a search segment", error))?;
175
    let searcher = reader.searcher();
176
    let max_doc = searcher
177
        .segment_readers()
178
        .iter()
179
        .map(SegmentReader::max_doc)
180
        .sum();
181
    if searcher.segment_readers().len() > 1 || max_doc_hint.is_some_and(|hint| hint != max_doc) {
182
        return Err(Error::new(
183
            ErrorKind::Store,
184
            "a search segment has an unexpected shape",
185
        ));
186
    }
187
    Ok(Segment {
188
        id,
189
        raw,
190
        index,
191
        searcher,
192
        alive: Arc::new(BitSet::with_max_value_and_full(max_doc)),
193
        max_doc,
194
        del_gen: 0,
195
        persisted: false,
196
        deletes_dirty: false,
197
    })
198
}
199
200
fn pack(files: &[(String, OwnedBytes)]) -> Vec<u8> {
201
    let mut packed = Vec::with_capacity(
202
        files
203
            .iter()
204
            .map(|(name, bytes)| name.len() + bytes.len() + 12)
205
            .sum::<usize>()
206
            + 68,
207
    );
208
    packed.extend_from_slice(&(files.len() as u32).to_le_bytes());
209
    for (name, bytes) in files {
210
        packed.extend_from_slice(&(name.len() as u32).to_le_bytes());
211
        packed.extend_from_slice(name.as_bytes());
212
        packed.extend_from_slice(&(bytes.len() as u64).to_le_bytes());
213
        packed.extend_from_slice(bytes.as_slice());
214
    }
215
    packed
216
}
217
218
fn unpack(mut bytes: &[u8]) -> Option<Vec<(String, &[u8])>> {
219
    fn take<'a>(bytes: &mut &'a [u8], len: usize) -> Option<&'a [u8]> {
220
        if bytes.len() < len {
221
            return None;
222
        }
223
        let (head, tail) = bytes.split_at(len);
224
        *bytes = tail;
225
        Some(head)
226
    }
227
    let count = u32::from_le_bytes(take(&mut bytes, 4)?.try_into().ok()?);
228
    let mut files = Vec::new();
229
    for _ in 0..count {
230
        let name_len = u32::from_le_bytes(take(&mut bytes, 4)?.try_into().ok()?) as usize;
231
        let name = std::str::from_utf8(take(&mut bytes, name_len)?)
232
            .ok()?
233
            .to_owned();
234
        let len =
235
            usize::try_from(u64::from_le_bytes(take(&mut bytes, 8)?.try_into().ok()?)).ok()?;
236
        files.push((name, take(&mut bytes, len)?));
237
    }
238
    bytes.is_empty().then_some(files)
239
}
240
241
pub(crate) fn segment_key(id: u64) -> String {
242
    format!("seg/{id}")
243
}
244
245
pub(crate) fn deletes_key(id: u64, generation: u64) -> String {
246
    format!("del/{id}/{generation}")
247
}
248
249
fn manifest(records: impl Iterator<Item = SegmentRecord>, next_id: u64) -> serde_json::Value {
250
    let segments: Vec<_> = records
251
        .map(|record| serde_json::json!([record.id, record.del_gen]))
252
        .collect();
253
    serde_json::json!({ "segments": segments, "next": next_id })
254
}
255
256
impl KeywordIndex {
257
    pub(crate) fn new(persistent: bool) -> Self {
258
        let (schema, fields) = schema();
259
        Self {
260
            schema,
261
            fields,
262
            settings: settings(),
263
            segments: Vec::new(),
264
            buffer: HashMap::new(),
265
            next_id: 1,
266
            persistent,
267
            removed: Vec::new(),
268
        }
269
    }
270
271
    /// `blob` hands over what an earlier commit put, once each, and any of it missing or
272
    /// unreadable fails the load
273
    pub(crate) fn load(
274
        manifest: &serde_json::Value,
275
        mut blob: impl FnMut(&str) -> Option<Vec<u8>>,
276
    ) -> Result<Self, Error> {
277
        let invalid = || Error::new(ErrorKind::Store, "the search manifest is unreadable");
278
        let records = manifest["segments"]
279
            .as_array()
280
            .ok_or_else(invalid)?
281
            .iter()
282
            .map(|record| {
283
                Some(SegmentRecord {
284
                    id: record.get(0)?.as_u64()?,
285
                    del_gen: record.get(1)?.as_u64()?,
286
                })
287
            })
288
            .collect::<Option<Vec<_>>>()
289
            .ok_or_else(invalid)?;
290
        let next_id = manifest["next"].as_u64().ok_or_else(invalid)?;
291
        let mut index = Self::new(true);
292
        let missing = || {
293
            Error::new(
294
                ErrorKind::Store,
295
                "a search segment is missing or unreadable",
296
            )
297
        };
298
        for record in &records {
299
            let packed = blob(&segment_key(record.id)).ok_or_else(missing)?;
300
            let raw = RamDirectory::create();
301
            for (name, bytes) in unpack(&packed).ok_or_else(missing)? {
302
                raw.atomic_write(&PathBuf::from(name), bytes)
303
                    .map_err(|error| tantivy_error("loading a search segment", error))?;
304
            }
305
            drop(packed);
306
            let mut segment = open_segment(record.id, raw, None)?;
307
            if segment.index.schema() != index.schema {
308
                return Err(Error::new(
309
                    ErrorKind::Store,
310
                    "a search segment has another schema",
311
                ));
312
            }
313
            if record.del_gen > 0 {
314
                let bytes = blob(&deletes_key(record.id, record.del_gen)).ok_or_else(missing)?;
315
                let alive = AliveBitSet::open(OwnedBytes::new(bytes));
316
                let mut bits = BitSet::with_max_value(segment.max_doc);
317
                for doc in alive.iter_alive().filter(|doc| *doc < segment.max_doc) {
318
                    bits.insert(doc);
319
                }
320
                segment.alive = Arc::new(bits);
321
            }
322
            segment.del_gen = record.del_gen;
323
            segment.persisted = true;
324
            index.segments.push(segment);
325
        }
326
        index.next_id = next_id.max(
327
            records
328
                .iter()
329
                .map(|record| record.id + 1)
330
                .max()
331
                .unwrap_or(1),
332
        );
333
        Ok(index)
334
    }
335
336
    /// the blob names what is persisted points at
337
    #[cfg(test)]
338
    pub(crate) fn referenced(&self) -> Vec<String> {
339
        let mut keys = Vec::new();
340
        for segment in self.segments.iter().filter(|segment| segment.persisted) {
341
            keys.push(segment_key(segment.id));
342
            if segment.del_gen > 0 {
343
                keys.push(deletes_key(segment.id, segment.del_gen));
344
            }
345
        }
346
        keys
347
    }
348
349
    fn document(&self, doc: &Doc) -> TantivyDocument {
350
        let fields = self.fields;
351
        let mut document = TantivyDocument::default();
352
        document.add_text(fields.key, &doc.key);
353
        document.add_text(fields.room, &doc.room);
354
        document.add_text(fields.sender, &doc.sender);
355
        document.add_text(fields.content, &doc.content);
356
        document.add_u64(fields.ts, doc.ts);
357
        document.add_u64(fields.tie, tie(&doc.key));
358
        document.add_u64(fields.content_ts, doc.content_ts);
359
        if doc.provisional {
360
            document.add_text(fields.pending, &doc.text);
361
            let target = doc
362
                .key
363
                .split_once('\n')
364
                .map_or(doc.key.as_str(), |(target, _)| target);
365
            document.add_text(fields.target, target);
366
        } else {
367
            document.add_text(fields.text, &doc.text);
368
        }
369
        document
370
    }
371
372
    fn stored(&self, document: &TantivyDocument) -> Option<Doc> {
373
        let fields = self.fields;
374
        let text = |field| {
375
            document
376
                .get_first(field)
377
                .and_then(|value| value.as_str())
378
                .map(str::to_owned)
379
        };
380
        let number = |field| document.get_first(field).and_then(|value| value.as_u64());
381
        let pending = text(fields.pending);
382
        Some(Doc {
383
            key: text(fields.key)?,
384
            room: text(fields.room)?,
385
            sender: text(fields.sender)?,
386
            ts: number(fields.ts)?,
387
            content: text(fields.content)?,
388
            content_ts: number(fields.content_ts)?,
389
            provisional: pending.is_some(),
390
            text: pending.unwrap_or_default(),
391
        })
392
    }
393
394
    /// the live docs in `segment` whose `field` holds `value`
395
    fn find(&self, segment: &Segment, field: Field, value: &str) -> Vec<DocId> {
396
        let term = Term::from_field_text(field, value);
397
        let mut found = Vec::new();
398
        for reader in segment.searcher.segment_readers() {
399
            let Ok(inverted) = reader.inverted_index(field) else {
400
                continue;
401
            };
402
            let Ok(Some(mut postings)) = inverted.read_postings(&term, IndexRecordOption::Basic)
403
            else {
404
                continue;
405
            };
406
            let mut doc = postings.doc();
407
            while doc != tantivy::TERMINATED {
408
                if segment.alive.contains(doc) {
409
                    found.push(doc);
410
                }
411
                doc = postings.advance();
412
            }
413
        }
414
        found
415
    }
416
417
    fn lookup(&self, field: Field, value: &str) -> Option<Doc> {
418
        self.segments.iter().rev().find_map(|segment| {
419
            let doc = *self.find(segment, field, value).first()?;
420
            let document: TantivyDocument = segment.searcher.doc(DocAddress::new(0, doc)).ok()?;
421
            self.stored(&document)
422
        })
423
    }
424
425
    /// tombstones every live doc in a segment whose `field` holds `value`
426
    fn remove_where(&mut self, field: Field, value: &str) -> bool {
427
        let mut removed = false;
428
        for position in 0..self.segments.len() {
429
            let docs = self.find(&self.segments[position], field, value);
430
            if docs.is_empty() {
431
                continue;
432
            }
433
            let segment = &mut self.segments[position];
434
            let alive = Arc::make_mut(&mut segment.alive);
435
            for doc in docs {
436
                alive.remove(doc);
437
            }
438
            segment.deletes_dirty = true;
439
            removed = true;
440
        }
441
        removed
442
    }
443
444
    fn flush_buffer(&mut self) -> Result<(), Error> {
445
        if self.buffer.is_empty() {
446
            return Ok(());
447
        }
448
        let raw = RamDirectory::create();
449
        let index = Index::create(raw.clone(), self.schema.clone(), self.settings.clone())
450
            .map_err(|error| tantivy_error("creating a search segment", error))?;
451
        index.tokenizers().register(TOKENIZER, analyzer());
452
        let mut writer = SingleSegmentIndexWriter::new(index, WRITER_BUDGET)
453
            .map_err(|error| tantivy_error("writing a search segment", error))?;
454
        let mut docs: Vec<_> = self.buffer.values().collect();
455
        docs.sort_by_key(|doc| doc.ts);
456
        for doc in docs {
457
            writer
458
                .add_document(self.document(doc))
459
                .map_err(|error| tantivy_error("writing a search segment", error))?;
460
        }
461
        writer
462
            .finalize()
463
            .map_err(|error| tantivy_error("finishing a search segment", error))?;
464
        let segment = open_segment(self.next_id, raw, Some(self.buffer.len() as u32))?;
465
        self.next_id += 1;
466
        self.segments.push(segment);
467
        self.buffer.clear();
468
        Ok(())
469
    }
470
471
    fn class(live: usize) -> u32 {
472
        live.max(1).ilog(MERGE_FACTOR)
473
    }
474
475
    fn forget(&mut self, segment: &Segment) {
476
        if self.persistent {
477
            self.removed
478
                .push((segment.id, segment.persisted, segment.del_gen));
479
        }
480
    }
481
482
    /// merges a size class once it fills up, and rewrites a segment that's mostly deleted
483
    fn compact(&mut self) -> Result<(), Error> {
484
        let (empty, kept): (Vec<_>, Vec<_>) = std::mem::take(&mut self.segments)
485
            .into_iter()
486
            .partition(|segment| segment.live() == 0);
487
        self.segments = kept;
488
        for segment in &empty {
489
            self.forget(segment);
490
        }
491
        loop {
492
            let mut classes: HashMap<u32, Vec<usize>> = HashMap::new();
493
            for (position, segment) in self.segments.iter().enumerate() {
494
                classes
495
                    .entry(Self::class(segment.live()))
496
                    .or_default()
497
                    .push(position);
498
            }
499
            let full = classes
500
                .into_values()
501
                .find(|positions| positions.len() >= MERGE_FACTOR);
502
            let sparse = self
503
                .segments
504
                .iter()
505
                .position(|segment| {
506
                    segment.max_doc >= 1_000 && segment.live() * 2 < segment.max_doc as usize
507
                })
508
                .map(|position| vec![position]);
509
            let Some(positions) = full.or(sparse) else {
510
                return Ok(());
511
            };
512
            self.merge(&positions)?;
513
        }
514
    }
515
516
    fn merge(&mut self, positions: &[usize]) -> Result<(), Error> {
517
        let mut inputs = Vec::new();
518
        let mut alive = Vec::new();
519
        for position in positions {
520
            let segment = &self.segments[*position];
521
            let searchable = segment
522
                .index
523
                .searchable_segments()
524
                .map_err(|error| tantivy_error("merging search segments", error))?;
525
            let mut bytes = Vec::new();
526
            write_alive_bitset(&segment.alive, &mut bytes)
527
                .map_err(|error| tantivy_error("merging search segments", error))?;
528
            let bytes = OwnedBytes::new(bytes);
529
            for tantivy_segment in searchable {
530
                inputs.push(tantivy_segment);
531
                alive.push(Some(AliveBitSet::open(bytes.clone())));
532
            }
533
        }
534
        let raw = RamDirectory::create();
535
        merge_filtered_segments(&inputs, self.settings.clone(), alive, raw.clone())
536
            .map_err(|error| tantivy_error("merging search segments", error))?;
537
        drop(inputs);
538
        let merged = open_segment(self.next_id, raw, None)?;
539
        self.next_id += 1;
540
        let (merging, kept): (Vec<_>, Vec<_>) = std::mem::take(&mut self.segments)
541
            .into_iter()
542
            .enumerate()
543
            .partition(|(position, _)| positions.contains(position));
544
        self.segments = kept.into_iter().map(|(_, segment)| segment).collect();
545
        for (_, segment) in &merging {
546
            self.forget(segment);
547
        }
548
        self.segments.push(merged);
549
        Ok(())
550
    }
551
552
    fn segment_files(segment: &Segment) -> Result<Vec<u8>, Error> {
553
        let mut names: Vec<PathBuf> = segment
554
            .index
555
            .searchable_segment_metas()
556
            .map_err(|error| tantivy_error("reading a search segment", error))?
557
            .iter()
558
            .flat_map(|meta| meta.list_files())
559
            .collect();
560
        names.push(PathBuf::from("meta.json"));
561
        let mut files = Vec::new();
562
        for name in names {
563
            if !segment.raw.exists(&name).unwrap_or(false) {
564
                continue;
565
            }
566
            let bytes = segment
567
                .raw
568
                .open_read(&name)
569
                .map_err(|error| tantivy_error("reading a search segment", error))?
570
                .read_bytes()
571
                .map_err(|error| tantivy_error("reading a search segment", error))?;
572
            files.push((name.to_string_lossy().into_owned(), bytes));
573
        }
574
        Ok(pack(&files))
575
    }
576
}
577
578
impl MessageIndex for KeywordIndex {
579
    fn get(&self, key: &str) -> Option<Doc> {
580
        if let Some(doc) = self.buffer.get(key) {
581
            return Some(doc.clone());
582
        }
583
        self.lookup(self.fields.key, key)
584
    }
585
586
    fn by_content(&self, content: &str) -> Option<Doc> {
587
        if let Some(doc) = self.buffer.values().find(|doc| doc.content == content) {
588
            return Some(doc.clone());
589
        }
590
        self.lookup(self.fields.content, content)
591
    }
592
593
    fn put(&mut self, doc: Doc) {
594
        self.remove(&doc.key);
595
        self.buffer.insert(doc.key.clone(), doc);
596
    }
597
598
    fn remove(&mut self, key: &str) -> bool {
599
        let buffered = self.buffer.remove(key).is_some();
600
        let key_field = self.fields.key;
601
        self.remove_where(key_field, key) || buffered
602
    }
603
604
    fn remove_provisional(&mut self, target: &str) -> bool {
605
        let prefix = format!("{target}\n");
606
        let before = self.buffer.len();
607
        self.buffer
608
            .retain(|key, doc| !(doc.provisional && key.starts_with(&prefix)));
609
        let buffered = self.buffer.len() != before;
610
        let target_field = self.fields.target;
611
        self.remove_where(target_field, target) || buffered
612
    }
613
614
    fn buffered(&self) -> usize {
615
        self.buffer.len()
616
    }
617
618
    fn search(
619
        &mut self,
620
        query: &str,
621
        rooms: Option<&[String]>,
622
        before: Option<(u64, u64)>,
623
        limit: usize,
624
    ) -> Result<(Vec<Hit>, Vec<String>), Error> {
625
        let (text_query, terms) = build_query(self.fields.text, query)?;
626
        self.flush_buffer()?;
627
        let query: Box<dyn Query> = match rooms {
628
            None => text_query,
629
            Some(rooms) => Box::new(BooleanQuery::new(vec![
630
                (Occur::Must, text_query),
631
                (
632
                    Occur::Must,
633
                    Box::new(TermSetQuery::new(
634
                        rooms
635
                            .iter()
636
                            .map(|room| Term::from_field_text(self.fields.room, room)),
637
                    )),
638
                ),
639
            ])),
640
        };
641
        let mut found = Vec::new();
642
        for segment in &self.segments {
643
            let collector = Newest {
644
                alive: segment.alive.clone(),
645
                before,
646
                limit,
647
            };
648
            let newest = segment
649
                .searcher
650
                .search(&*query, &collector)
651
                .map_err(|error| tantivy_error("searching messages", error))?;
652
            for (ts, tie, doc) in newest {
653
                found.push((ts, tie, segment.id, doc));
654
            }
655
        }
656
        found.sort_by(|a, b| (b.0, b.1).cmp(&(a.0, a.1)));
657
        found.truncate(limit);
658
        let mut hits = Vec::new();
659
        for (ts, tie, id, doc) in found {
660
            let segment = self
661
                .segments
662
                .iter()
663
                .find(|segment| segment.id == id)
664
                .expect("the segment was just searched");
665
            let document: TantivyDocument = segment
666
                .searcher
667
                .doc(doc)
668
                .map_err(|error| tantivy_error("reading a search hit", error))?;
669
            let Some(stored) = self.stored(&document) else {
670
                continue;
671
            };
672
            hits.push(Hit {
673
                key: stored.key,
674
                room: stored.room,
675
                sender: stored.sender,
676
                content: stored.content,
677
                ts,
678
                tie,
679
            });
680
        }
681
        Ok((hits, terms))
682
    }
683
684
    fn maintain(&mut self) -> Result<(), Error> {
685
        self.flush_buffer()?;
686
        self.compact()
687
    }
688
689
    fn changes(&mut self) -> Result<Changes, Error> {
690
        self.maintain()?;
691
        let mut changes = Changes::default();
692
        for (id, persisted, del_gen) in &self.removed {
693
            if *persisted {
694
                changes.deletes.push(segment_key(*id));
695
            }
696
            if *del_gen > 0 {
697
                changes.deletes.push(deletes_key(*id, *del_gen));
698
            }
699
            changes.removed.push(*id);
700
        }
701
        let mut records = Vec::with_capacity(self.segments.len());
702
        for segment in &self.segments {
703
            if !segment.persisted {
704
                changes
705
                    .puts
706
                    .push((segment_key(segment.id), Self::segment_files(segment)?));
707
                changes.files.push(segment.id);
708
            }
709
            let mut del_gen = segment.del_gen;
710
            if segment.deletes_dirty && segment.live() < segment.max_doc as usize {
711
                del_gen = segment.del_gen + 1;
712
                let mut bytes = Vec::new();
713
                write_alive_bitset(&segment.alive, &mut bytes)
714
                    .map_err(|error| tantivy_error("saving search deletes", error))?;
715
                changes.puts.push((deletes_key(segment.id, del_gen), bytes));
716
                if segment.del_gen > 0 {
717
                    changes
718
                        .deletes
719
                        .push(deletes_key(segment.id, segment.del_gen));
720
                }
721
                changes.dels.push((segment.id, del_gen));
722
            }
723
            records.push(SegmentRecord {
724
                id: segment.id,
725
                del_gen,
726
            });
727
        }
728
        changes.manifest = manifest(records.into_iter(), self.next_id);
729
        Ok(changes)
730
    }
731
732
    fn committed(&mut self, changes: &Changes) {
733
        self.removed
734
            .retain(|(id, ..)| !changes.removed.contains(id));
735
        for segment in &mut self.segments {
736
            if changes.files.contains(&segment.id) {
737
                segment.persisted = true;
738
            }
739
            if let Some((_, generation)) = changes.dels.iter().find(|(id, _)| *id == segment.id) {
740
                segment.del_gen = *generation;
741
                segment.deletes_dirty = false;
742
            }
743
        }
744
    }
745
746
    fn detach(&mut self) {
747
        self.persistent = false;
748
        self.removed.clear();
749
    }
750
}
751
752
/// the `limit` newest live docs older than `before`, by timestamp and then key hash
753
struct Newest {
754
    alive: Arc<BitSet>,
755
    before: Option<(u64, u64)>,
756
    limit: usize,
757
}
758
759
struct NewestSegment {
760
    alive: Arc<BitSet>,
761
    before: Option<(u64, u64)>,
762
    limit: usize,
763
    ts: tantivy::columnar::Column<u64>,
764
    tie: tantivy::columnar::Column<u64>,
765
    segment: u32,
766
    top: std::collections::BinaryHeap<std::cmp::Reverse<(u64, u64, DocAddress)>>,
767
}
768
769
impl Collector for Newest {
770
    type Fruit = Vec<(u64, u64, DocAddress)>;
771
    type Child = NewestSegment;
772
773
    fn for_segment(&self, segment: u32, reader: &SegmentReader) -> tantivy::Result<NewestSegment> {
774
        Ok(NewestSegment {
775
            alive: self.alive.clone(),
776
            before: self.before,
777
            limit: self.limit,
778
            ts: reader.fast_fields().u64("ts")?,
779
            tie: reader.fast_fields().u64("tie")?,
780
            segment,
781
            top: std::collections::BinaryHeap::new(),
782
        })
783
    }
784
785
    fn requires_scoring(&self) -> bool {
786
        false
787
    }
788
789
    fn merge_fruits(&self, fruits: Vec<Self::Fruit>) -> tantivy::Result<Self::Fruit> {
790
        let mut all: Vec<_> = fruits.into_iter().flatten().collect();
791
        all.sort_by(|a, b| (b.0, b.1).cmp(&(a.0, a.1)));
792
        all.truncate(self.limit);
793
        Ok(all)
794
    }
795
}
796
797
impl SegmentCollector for NewestSegment {
798
    type Fruit = Vec<(u64, u64, DocAddress)>;
799
800
    fn collect(&mut self, doc: DocId, _: Score) {
801
        if !self.alive.contains(doc) {
802
            return;
803
        }
804
        let (Some(ts), Some(tie)) = (self.ts.first(doc), self.tie.first(doc)) else {
805
            return;
806
        };
807
        if self.before.is_some_and(|before| (ts, tie) >= before) {
808
            return;
809
        }
810
        let entry = std::cmp::Reverse((ts, tie, DocAddress::new(self.segment, doc)));
811
        if self.top.len() < self.limit {
812
            self.top.push(entry);
813
        } else if self.top.peek().is_some_and(|smallest| entry < *smallest) {
814
            self.top.pop();
815
            self.top.push(entry);
816
        }
817
    }
818
819
    fn harvest(self) -> Self::Fruit {
820
        let mut top: Vec<_> = self
821
            .top
822
            .into_iter()
823
            .map(|std::cmp::Reverse(entry)| entry)
824
            .collect();
825
        top.sort_by(|a, b| (b.0, b.1).cmp(&(a.0, a.1)));
826
        top
827
    }
828
}
829
830
#[cfg(test)]
831
#[path = "index_tests.rs"]
832
mod tests;