Skip to content

web search done right

12.8 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/

use ahash::HashSetExt;

use crate::query::parser::{SimpleOrPhrase, Term as ParserTerm};
use crate::schema::text_field::{self, TextField as _};
use crate::{query::parser::SimpleTerm, schema::TextFieldEnum};

type HashSet<T> = std::collections::HashSet<T, ahash::RandomState>;

use super::{Occur, Term};

#[derive(Debug, Clone)]
pub enum Node {
    Term(Term),
    And(Box<Node>, Box<Node>),
    Or(Box<Node>, Box<Node>),
    Not(Box<Node>),
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Node::Term(a), Node::Term(b)) => a == b,
            (Node::And(a, b), Node::And(c, d)) => (a == c && b == d) || (a == d && b == c),
            (Node::Or(a, b), Node::Or(c, d)) => (a == c && b == d) || (a == d && b == c),
            (Node::Not(a), Node::Not(b)) => a == b,
            _ => false,
        }
    }
}

impl Eq for Node {}

impl std::hash::Hash for Node {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        match self {
            Node::Term(term) => term.hash(state),
            Node::And(left, right) => {
                left.hash(state);
                right.hash(state);
            }
            Node::Or(left, right) => {
                left.hash(state);
                right.hash(state);
            }
            Node::Not(inner) => inner.hash(state),
        }
    }
}

impl Node {
    pub fn and<T: Into<Node>>(self, other: T) -> Node {
        Node::And(Box::new(self), Box::new(other.into()))
    }

    pub fn or<T: Into<Node>>(self, other: T) -> Node {
        Node::Or(Box::new(self), Box::new(other.into()))
    }
}

impl Node {
    fn into_non_compacted_query(self) -> super::Query {
        match self {
            Node::Term(term) => super::Query::Term(term),
            Node::And(left, right) => super::Query::Boolean {
                clauses: vec![
                    (Occur::Must, left.into_non_compacted_query()),
                    (Occur::Must, right.into_non_compacted_query()),
                ],
            },
            Node::Or(left, right) => super::Query::Boolean {
                clauses: vec![
                    (Occur::Should, left.into_non_compacted_query()),
                    (Occur::Should, right.into_non_compacted_query()),
                ],
            },
            Node::Not(inner) => super::Query::Boolean {
                clauses: vec![(Occur::MustNot, inner.into_non_compacted_query())],
            },
        }
    }

    pub fn into_query(self) -> super::Query {
        self.optimise()
            .into_non_compacted_query()
            .compact()
            .deduplicate()
    }

    pub fn from_term(term: ParserTerm) -> Self {
        match term {
            ParserTerm::SimpleOrPhrase(s) => match s {
                SimpleOrPhrase::Simple(term) => TextFieldEnum::all()
                    .filter(|f| f.is_searchable())
                    .map(|field| {
                        Node::Term(Term {
                            text: SimpleOrPhrase::Simple(term.clone()),
                            field,
                        })
                    })
                    .reduce(|left, right| left.or(right))
                    .expect("fields should not be empty"),
                SimpleOrPhrase::Phrase(p) => TextFieldEnum::all()
                    .filter(|f| f.is_searchable() && f.is_phrase_searchable())
                    .map(|field| {
                        Node::Term(Term {
                            text: SimpleOrPhrase::Phrase(p.clone()),
                            field,
                        })
                    })
                    .reduce(|left, right| left.or(right))
                    .expect("fields should not be empty"),
            },
            ParserTerm::Site(s) => Node::Term(Term {
                text: SimpleOrPhrase::Simple(SimpleTerm::from(s)),
                field: text_field::UrlForSiteOperator.into(),
            }),
            ParserTerm::LinkTo(s) => Node::Term(Term {
                text: SimpleOrPhrase::Simple(SimpleTerm::from(s)),
                field: text_field::Links.into(),
            }),
            ParserTerm::Title(t) => Node::Term(Term {
                text: t,
                field: text_field::Title.into(),
            }),
            ParserTerm::Body(b) => Node::Term(Term {
                text: b,
                field: text_field::AllBody.into(),
            }),
            ParserTerm::Url(u) => Node::Term(Term {
                text: u,
                field: text_field::Url.into(),
            }),
            ParserTerm::ExactUrl(u) => Node::Term(Term {
                text: SimpleOrPhrase::Simple(SimpleTerm::from(u)),
                field: text_field::UrlNoTokenizer.into(),
            }),
            ParserTerm::PossibleBang { prefix, bang } => {
                let mut s = String::new();
                s.push(prefix);
                s.push_str(bang.as_str());

                let s = SimpleTerm::from(s);

                TextFieldEnum::all()
                    .filter(|f| f.is_searchable())
                    .map(|field| {
                        Node::Term(Term {
                            text: SimpleOrPhrase::Simple(s.clone()),
                            field,
                        })
                    })
                    .reduce(|left, right| left.or(right))
                    .expect("fields should not be empty")
            }
            ParserTerm::Not(n) => Node::Not(Box::new(Node::from_term(*n))),
        }
    }

    fn or_children(self) -> HashSet<Node> {
        match self {
            Node::Or(left, right) => {
                let mut left = left.or_children();
                let right = right.or_children();

                left.extend(right);
                left
            }
            _ => {
                let mut set = HashSet::new();
                set.insert(self);
                set
            }
        }
    }

    fn prune_direct_or_child(self, child: &Self) -> Self {
        match self {
            Node::Or(a, b) if *a == *child => *b,
            Node::Or(a, b) if *b == *child => *a,
            Node::Or(a, b) => Node::Or(
                Box::new(a.prune_direct_or_child(child)),
                Box::new(b.prune_direct_or_child(child)),
            ),
            t => t,
        }
    }

    pub fn optimise(self) -> Self {
        let mut node = self;
        node = Deduplicate.optimise(node);
        DistributiveLaw.optimise(node)
    }
}

trait Optimisation {
    fn optimise(&self, node: Node) -> Node;
}

/// Re-write queries on the form `(A | B) & (A | C)` to `A | (B & C)`.
/// This avoids having to evaluate the same term multiple times.
struct DistributiveLaw;

impl Optimisation for DistributiveLaw {
    fn optimise(&self, node: Node) -> Node {
        match node {
            Node::Term(term) => Node::Term(term),
            Node::Not(inner) => Node::Not(Box::new(self.optimise(*inner))),
            Node::Or(left, right) => Node::Or(
                Box::new(self.optimise(*left)),
                Box::new(self.optimise(*right)),
            ),
            Node::And(left, right) => {
                let left = self.optimise(*left);
                let right = self.optimise(*right);

                match (left, right) {
                    (Node::Or(left_left, left_right), Node::Or(right_left, right_right)) => {
                        let left_children =
                            Node::Or(left_left.clone(), left_right.clone()).or_children();
                        let right_children =
                            Node::Or(right_left.clone(), right_right.clone()).or_children();

                        let common: Vec<_> = left_children
                            .intersection(&right_children)
                            .cloned()
                            .collect();

                        if common.is_empty() {
                            Node::And(
                                Box::new(Node::Or(left_left, left_right)),
                                Box::new(Node::Or(right_left, right_right)),
                            )
                        } else {
                            let mut left = Node::Or(left_left, left_right);
                            let mut right = Node::Or(right_left, right_right);

                            for c in &common {
                                left = left.prune_direct_or_child(c);
                                right = right.prune_direct_or_child(c);
                            }

                            let res = Node::And(Box::new(left), Box::new(right));

                            let common = common
                                .into_iter()
                                .reduce(|left, right| left.or(right))
                                .unwrap();

                            res.or(common)
                        }
                    }

                    (left, right) => Node::And(Box::new(left), Box::new(right)),
                }
            }
        }
    }
}

struct Deduplicate;

impl Optimisation for Deduplicate {
    fn optimise(&self, node: Node) -> Node {
        match node {
            Node::Term(term) => Node::Term(term),
            Node::Not(inner) => Node::Not(Box::new(self.optimise(*inner))),
            Node::Or(left, right) => {
                let left = self.optimise(*left);
                let right = self.optimise(*right);

                if left == right {
                    left
                } else {
                    Node::Or(Box::new(left), Box::new(right))
                }
            }
            Node::And(left, right) => {
                let left = self.optimise(*left);
                let right = self.optimise(*right);

                if left == right {
                    left
                } else {
                    Node::And(Box::new(left), Box::new(right))
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_optimisation() {
        let a = Node::Term(Term {
            text: SimpleOrPhrase::Simple(SimpleTerm::from("a".to_string())),
            field: text_field::Title.into(),
        });

        let b = Node::Term(Term {
            text: SimpleOrPhrase::Simple(SimpleTerm::from("b".to_string())),
            field: text_field::Title.into(),
        });

        let c = Node::Term(Term {
            text: SimpleOrPhrase::Simple(SimpleTerm::from("c".to_string())),
            field: text_field::Title.into(),
        });

        let d = Node::Term(Term {
            text: SimpleOrPhrase::Simple(SimpleTerm::from("d".to_string())),
            field: text_field::Title.into(),
        });

        let e = Node::Term(Term {
            text: SimpleOrPhrase::Simple(SimpleTerm::from("e".to_string())),
            field: text_field::Title.into(),
        });

        let f = Node::Term(Term {
            text: SimpleOrPhrase::Simple(SimpleTerm::from("f".to_string())),
            field: text_field::Title.into(),
        });

        let query = a.clone().or(b.clone()).and(a.clone().or(c.clone()));

        let optimised = query.optimise();

        assert_eq!(optimised, a.clone().or(b.clone().and(c.clone())));

        let query = a.clone().or(b.clone()).and(c.clone().or(d.clone()));

        let optimised = query.optimise();

        assert_eq!(
            optimised,
            a.clone().or(b.clone()).and(c.clone().or(d.clone()))
        );

        let query = (a.clone().or(b.clone()).or(c.clone()).or(d.clone()))
            .and(e.clone().or(f.clone()).or(c.clone()).or(d.clone()));
        let optimised = query.optimise();

        assert_eq!(
            optimised,
            ((a.clone().or(b.clone())).and(e.clone().or(f.clone()))).or(c.clone().or(d.clone()))
        );

        let query = (a.clone().or(a.clone()).or(a.clone()).or(a.clone()))
            .and(a.clone().or(a.clone()).or(a.clone()).or(a.clone()));

        let optimised = query.optimise();

        assert_eq!(optimised, a.clone());

        let query = (a.clone().or(b.clone())).and(a.clone().or(c.clone().and(a.clone())));

        let optimised = query.optimise();

        assert_eq!(
            optimised,
            a.clone().or(b.clone().and(c.clone().and(a.clone())))
        );
    }
}