pub mod bm25;
pub mod exec;
pub mod parser;
pub use bm25::Bm25;
pub use parser::Node;
use crate::error::QueryError;
use crate::index::{DocId, IndexReader};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Query {
root: Node,
}
impl Query {
pub fn parse(input: &str) -> Result<Query, QueryError> {
parser::parse(input).map(|root| Query { root })
}
pub fn root(&self) -> &Node {
&self.root
}
pub fn highlight_terms(&self) -> Vec<&str> {
fn walk<'a>(n: &'a Node, out: &mut Vec<&'a str>) {
let mut add = |t: &'a str| {
if !out.contains(&t) {
out.push(t);
}
};
match n {
Node::Term(t) => add(t),
Node::Phrase(ts) => ts.iter().for_each(|t| add(t)),
Node::And { must, .. } => must.iter().for_each(|c| walk(c, out)),
Node::Or(cs) => cs.iter().for_each(|c| walk(c, out)),
}
}
let mut out = Vec::new();
walk(&self.root, &mut out);
out
}
}
#[derive(Debug, Clone)]
pub struct SearchOptions {
pub limit: usize,
pub bm25: Bm25,
}
impl Default for SearchOptions {
fn default() -> Self {
Self { limit: 20, bm25: Bm25::default() }
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Hit {
pub doc: DocId,
pub score: f32,
}
#[derive(Debug, Clone, PartialEq)]
pub struct SearchResult {
pub hits: Vec<Hit>,
pub total_matches: usize,
}
pub fn search<R: IndexReader>(index: &R, query: &Query, opts: &SearchOptions) -> SearchResult {
let mut hits = exec::evaluate(index, &query.root, &opts.bm25);
let total_matches = hits.len();
let by_rank = |a: &Hit, b: &Hit| b.score.total_cmp(&a.score).then(a.doc.cmp(&b.doc));
if hits.len() > opts.limit {
if opts.limit > 0 {
hits.select_nth_unstable_by(opts.limit - 1, by_rank);
}
hits.truncate(opts.limit);
}
hits.sort_unstable_by(by_rank);
SearchResult { hits, total_matches }
}
#[cfg(test)]
mod tests {
use super::*;
use crate::store::writer::test_support::index_from_texts;
#[test]
fn highlight_terms_skips_negations_and_dedups() {
let q = Query::parse("foo \"bar baz\" -nope (foo OR qux) -\"no way\"").unwrap();
assert_eq!(q.highlight_terms(), vec!["foo", "bar", "baz", "qux"]);
}
#[test]
fn search_ranks_and_limits() {
let idx = index_from_texts(&["a", "a a", "a a a", "a a a a", "b"]);
let q = Query::parse("a").unwrap();
let all = search(&idx, &q, &SearchOptions { limit: 100, ..Default::default() });
assert_eq!(all.total_matches, 4);
assert_eq!(all.hits.iter().map(|h| h.doc).collect::<Vec<_>>(), vec![3, 2, 1, 0]);
assert!(all.hits.windows(2).all(|w| w[0].score >= w[1].score));
let top2 = search(&idx, &q, &SearchOptions { limit: 2, ..Default::default() });
assert_eq!(top2.total_matches, 4);
assert_eq!(top2.hits, all.hits[..2].to_vec());
let none = search(&idx, &q, &SearchOptions { limit: 0, ..Default::default() });
assert_eq!(none.total_matches, 4);
assert!(none.hits.is_empty());
}
#[test]
fn ties_break_by_doc_id() {
let idx = index_from_texts(&["x y", "x z", "x w"]);
let r = search(&idx, &Query::parse("x").unwrap(), &SearchOptions::default());
assert_eq!(r.hits.iter().map(|h| h.doc).collect::<Vec<_>>(), vec![0, 1, 2]);
}
}