notescraft/crates/index/tests/search.rs

//! Full-text search end to end: ranking, the query language, incremental
//! updates and hostile input, over the public [`SearchIndex`] API.

use notescraft_index::search::{SearchIndex, SearchQuery};
use std::fmt::Write as _;

use notescraft_index::{Error, Hit, Snippet};

fn index(contents: &[(&str, &str)]) -> SearchIndex {
    let mut notes = SearchIndex::new();
    for (path, body) in contents {
        notes.update(path, body).unwrap();
    }
    notes
}

fn paths(hits: &[Hit]) -> Vec<String> {
    hits.iter().map(|hit| hit.path.clone()).collect()
}

#[test]
fn ranking_prefers_title_and_density_and_is_deterministic() {
    // Hand-checked weighted BM25 (title x4, body x1): `b` carries `boat` 1x in
    // the body and 4 weighted times in its title stem, `a` 3x in the body with
    // a title that does not match, `c` 1x in the body — strictly decreasing.
    let notes = index(&[("a/Ship.md", "boat boat boat\n"), ("b/Boat.md", "boat\n"), ("c/Sail.md", "boat\n")]);
    let boat = SearchQuery::parse("boat").unwrap();
    let hits = notes.search(&boat, 10);
    assert_eq!(paths(&hits), vec![String::from("b/Boat.md"), String::from("a/Ship.md"), String::from("c/Sail.md")]);
    assert!((hits[0].score > hits[1].score) && (hits[1].score > hits[2].score));
    assert!(hits[0].title_match);
    assert!(!hits[1].title_match);

    let title = SearchQuery::parse("ship").unwrap();
    let hits = notes.search(&title, 10);
    assert_eq!(paths(&hits), vec![String::from("a/Ship.md")]);
    assert!(hits[0].title_match, "the stem `Ship` is the weight-4 title field");

    assert_eq!(notes.search(&boat, 10), notes.search(&boat, 10), "same query twice returns the identical list");
}

#[test]
fn phrase_matches_in_order_but_terms_match_anywhere() {
    let notes = index(&[("a.md", "alpha beta gamma\n"), ("b.md", "gamma beta alpha\n"), ("c.md", "alpha something beta\n")]);
    let terms = SearchQuery::parse("alpha beta").unwrap();
    assert_eq!(paths(&notes.search(&terms, 10)).len(), 3, "bare terms are AND, order does not matter");
    let phrase = SearchQuery::parse("\"alpha beta\"").unwrap();
    let hits = notes.search(&phrase, 10);
    assert_eq!(paths(&hits), vec![String::from("a.md")]);
    assert_eq!(hits[0].snippets[0].line, 1);
    assert_eq!(hits[0].snippets[0].ranges, vec![0..5, 6..10]);
}

#[test]
fn exclusion_and_or_compose() {
    let notes = index(&[("a.md", "rust code\n"), ("b.md", "rust crab\n"), ("c.md", "rust rust\n")]);
    let minus = SearchQuery::parse("rust -crab").unwrap();
    // `c.md` carries `rust` twice on one line, so its density wins.
    assert_eq!(paths(&notes.search(&minus, 10)), vec![String::from("c.md"), String::from("a.md")]);
    let minus_phrase = SearchQuery::parse("rust -\"rust rust\"").unwrap();
    assert_eq!(paths(&notes.search(&minus_phrase, 10)), vec![String::from("a.md"), String::from("b.md")]);
    let or = SearchQuery::parse("crab OR code").unwrap();
    assert_eq!(paths(&notes.search(&or, 10)), vec![String::from("a.md"), String::from("b.md")]);
    let or_negative = SearchQuery::parse("crab OR code -\"rust code\"").unwrap();
    assert_eq!(paths(&notes.search(&or_negative, 10)), vec![String::from("b.md")]);
    let limit = notes.search(&SearchQuery::parse("rust").unwrap(), 2);
    assert_eq!(limit.len(), 2, "limit truncates after ranking");
}

#[test]
fn path_file_and_tag_operators_and_nested_tags_match_children() {
    let notes = index(&[("work/a/Note.md", "letter A #team/ops\n"), ("work/b/Site.md", "letter B\n"), ("home/Note.md", "letter C #team\n")]);
    let path = SearchQuery::parse("letter path:work/a/").unwrap();
    assert_eq!(paths(&notes.search(&path, 10)), vec![String::from("work/a/Note.md")]);
    let file = SearchQuery::parse("letter file:Site").unwrap();
    assert_eq!(paths(&notes.search(&file, 10)), vec![String::from("work/b/Site.md")]);
    let parent = SearchQuery::parse("letter tag:#team").unwrap();
    assert_eq!(paths(&notes.search(&parent, 10)), vec![String::from("home/Note.md"), String::from("work/a/Note.md")], "nested tags match children");
    let child = SearchQuery::parse("letter tag:#team/ops").unwrap();
    assert_eq!(paths(&notes.search(&child, 10)), vec![String::from("work/a/Note.md")]);
}

#[test]
fn line_operator_needs_all_terms_on_one_line() {
    let notes = index(&[("a.md", "alpha is here\nbeta is there\nalpha and beta share this line\n"), ("b.md", "alpha\nbeta\n")]);
    let line = SearchQuery::parse("line:(alpha beta)").unwrap();
    assert_eq!(paths(&notes.search(&line, 10)), vec![String::from("a.md")]);
    let hits = notes.search(&line, 10);
    assert_eq!(hits[0].snippets[0].line, 3, "the shared line is the snippet");
}

#[test]
fn unicode_searches_accents_and_cjk_tokens() {
    let notes = index(&[("french/Café.md", "héllo wörld straße\n漢字 kana 仮名\n"), ("japan/日本語.md", "漢字のテスト\n")]);
    let accents = SearchQuery::parse("héllo").unwrap();
    assert_eq!(paths(&notes.search(&accents, 10)), vec![String::from("french/Café.md")]);
    let han = SearchQuery::parse("漢字").unwrap();
    let hits = notes.search(&han, 10);
    assert_eq!(hits.len(), 2, "each CJK char is its own token, both notes carry 漢,字");
    let phrase = SearchQuery::parse("\"漢字の\"").unwrap();
    assert_eq!(paths(&notes.search(&phrase, 10)), vec![String::from("japan/日本語.md")]);
}

#[cfg(debug_assertions)] // `postings_len` is a debug-build-only invariant
#[test]
fn update_and_remove_leave_no_stale_postings() {
    let mut notes = SearchIndex::new();
    notes.update("a.md", "alpha beta\n").unwrap();
    notes.update("b.md", "alpha gamma\n").unwrap();
    let baseline = notes.postings_len();
    notes.update("a.md", "alpha\n").unwrap();
    assert_eq!(notes.postings_len(), baseline - 1, "beta is gone after the re-index");
    notes.remove("b.md").unwrap();
    notes.remove("a.md").unwrap();
    assert_eq!(notes.postings_len(), 0, "removal retracts every posting");
    assert_eq!(notes.search(&SearchQuery::parse("alpha").unwrap(), 10), []);
    assert!(matches!(notes.remove("gone.md"), Err(Error::NotIndexed(path)) if path == "gone.md"));
}

#[test]
fn rename_rekeys_without_touching_the_body() {
    let mut notes = SearchIndex::new();
    notes.update("old/Name.md", "keep me\n").unwrap();
    notes.rename("old/Name.md", "new/Renamed.md").unwrap();
    assert_eq!(notes.len(), 1);
    assert!(matches!(notes.rename("old/Name.md", "x.md"), Err(Error::NotIndexed(_))));
    assert!(notes.rename("new/Renamed.md", "bad/../path.md").is_err());
    let hits = notes.search(&SearchQuery::parse("keep").unwrap(), 5);
    assert_eq!(paths(&hits), vec![String::from("new/Renamed.md")]);
    assert!(!hits[0].title_match, "`keep` is in the body, not the new stem");
    let renamed = SearchQuery::parse("renamed").unwrap();
    let hits = notes.search(&renamed, 5);
    assert_eq!(paths(&hits), vec![String::from("new/Renamed.md")]);
    assert!(hits[0].title_match, "the new stem `Renamed` is the title field now");
}

#[test]
fn regex_search_is_rejected_with_an_error() {
    assert!(matches!(SearchQuery::parse("ship /re.*/"), Err(Error::Unsupported(text)) if text == "regex search"));
}

#[test]
fn malformed_queries_are_errors_never_panics() {
    for query in ["", "   ", "\"unterminated", "a OR", "-a", "/only/"] {
        assert!(SearchQuery::parse(query).is_err(), "{query:?} must not parse");
    }
    assert!(matches!(SearchQuery::parse(&"x".repeat(2000)), Err(Error::QueryTooLong { len: 2000, max: 1000 })));
}

#[test]
fn a_hostile_note_of_two_mib_and_100k_distinct_tokens_survives() {
    let mut body = String::with_capacity(2 * 1024 * 1024);
    let mut token = 0_usize;
    while body.len() < 2 * 1024 * 1024 {
        writeln!(&mut body, "t{token:08} f").unwrap_or_else(|error| panic!("in-memory write cannot fail: {error}"));
        token += 1;
    }
    let mut notes = SearchIndex::new();
    notes.update("huge.md", &body).unwrap();
    let hits = notes.search(&SearchQuery::parse("t00000001").unwrap(), 5);
    assert_eq!(paths(&hits), vec![String::from("huge.md")]);
    assert_eq!(notes.len(), 1);
    assert!(token > 100_000, "100 000 distinct tokens indexed: {token}");
    // A second full re-index must not blow up either.
    notes.update("huge.md", &body).unwrap();
    assert_eq!(notes.search(&SearchQuery::parse("t00000002").unwrap(), 5).len(), 1);
}

#[test]
fn snippets_are_capped_and_char_boundary_safe() {
    let mut body = String::from("é\n");
    body.push_str(&"é".repeat(120));
    body.push_str("\ntail é\n");
    let mut notes = SearchIndex::new();
    notes.update("accent.md", &body).unwrap();
    let hits = notes.search(&SearchQuery::parse("é").unwrap(), 5);
    let snippets: &[Snippet] = &hits[0].snippets;
    assert!(snippets.len() <= 3);
    assert!(snippets.iter().all(|snippet| snippet.text.chars().count() <= 200));
    assert!(snippets.iter().all(|snippet| snippet.text.is_char_boundary(snippet.text.len())));
    assert!(
        snippets
            .iter()
            .all(|snippet| snippet.ranges.iter().all(|range| snippet.text.is_char_boundary(range.start) && snippet.text.is_char_boundary(range.end)))
    );
}

#[test]
fn frontmatter_tags_and_titles_are_searchable_without_being_body() {
    let mut notes = SearchIndex::new();
    notes.update("meta/Note.md", "---\ntags: [rust, index]\n---\nplain body\n").unwrap();
    let tagged = notes.search(&SearchQuery::parse("index").unwrap(), 5);
    assert_eq!(paths(&tagged), vec![String::from("meta/Note.md")], "frontmatter tags are the tags field");
    let title = notes.search(&SearchQuery::parse("note").unwrap(), 5);
    assert!(title[0].title_match, "the stem is the title field");
}

#[test]
fn the_crate_root_reexports_the_search_api() {
    // `SearchIndex` is reachable both at the root and in its module.
    let notes: notescraft_index::SearchIndex = notescraft_index::search::SearchIndex::new();
    assert!(notes.is_empty());
    assert_eq!(notes.search(&SearchQuery::parse("anything").unwrap(), 3), Vec::<Hit>::new());
}

// The scale gates of the task, measured in release.
#[test]
#[ignore = "perf: run with --release --ignored -- --nocapture"]
fn ten_thousand_notes_index_and_search_fast() {
    const NOTES: usize = 10_000;

    fn body(i: usize) -> String {
        format!("---\ntags: [topic/{}]\n---\n# Heading {i}\n\nAlpha {i} beta gamma delta {i} epsilon\n\nZeta {i} eta theta iota\n", i % 13)
    }
    fn path(i: usize) -> String {
        format!("folder{}/Note {i}.md", i % 20)
    }

    let start = std::time::Instant::now();
    let mut notes = SearchIndex::new();
    for i in 0..NOTES {
        notes.update(&path(i), &body(i)).unwrap();
    }
    let index_time = start.elapsed();

    let query = SearchQuery::parse("beta gamma").unwrap();
    let start = std::time::Instant::now();
    for _ in 0..100 {
        let hits = notes.search(&query, 10);
        assert_ne!(hits, []);
    }
    let per_search = start.elapsed().as_secs_f64() * 1000.0 / 100.0;

    println!("index {NOTES} notes: {index_time:?}; average search: {per_search:.3} ms");
    assert!(index_time.as_secs_f64() < 2.0, "indexing took {index_time:?}, budget 2 s");
    assert!(per_search < 50.0, "average search took {per_search:.3} ms, budget 50 ms");
}

#[test]
fn filter_only_queries_list_the_matching_notes() {
    let notes = index(&[("work/a/Note.md", "letter A #team/ops\n"), ("work/b/Site.md", "letter B #rust\n"), ("home/Note.md", "letter C #rust\n")]);
    let tag = SearchQuery::parse("tag:#rust").unwrap();
    assert_eq!(paths(&notes.search(&tag, 10)), vec![String::from("home/Note.md"), String::from("work/b/Site.md")]);
    let path = SearchQuery::parse("path:work/").unwrap();
    assert_eq!(paths(&notes.search(&path, 10)), vec![String::from("work/a/Note.md"), String::from("work/b/Site.md")]);
    let both = SearchQuery::parse("path:work/ tag:#rust").unwrap();
    assert_eq!(paths(&notes.search(&both, 10)), vec![String::from("work/b/Site.md")]);
    assert!(SearchQuery::parse("-letter").is_err(), "only negations stay an error");
}