Skip to content

web search done right

9.4 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 tantivy::{columnar::CachedColumn, postings::SegmentPostings, DocSet};

use crate::webgraph::{
    schema::{Field, FieldEnum},
    warmed_column_fields::WarmedColumnFields,
    NodeID,
};

#[derive(Debug, Clone)]
pub struct LinksQuery {
    node: NodeID,
    field: FieldEnum,
    deduplication_field: Option<FieldEnum>,
    warmed_column_fields: WarmedColumnFields,
    skip_self_links: bool,
}

impl LinksQuery {
    pub fn new<F: Field>(
        node: NodeID,
        lookup_field: F,
        warmed_column_fields: WarmedColumnFields,
    ) -> Self {
        Self {
            node,
            field: lookup_field.into(),
            deduplication_field: None,
            warmed_column_fields,
            skip_self_links: true,
        }
    }

    pub fn skip_self_links(mut self, skip_self_links: bool) -> Self {
        self.skip_self_links = skip_self_links;
        self
    }

    pub fn with_deduplication_field<F: Field>(mut self, deduplication_field: F) -> Self {
        self.deduplication_field = Some(deduplication_field.into());
        self
    }
}

impl tantivy::query::Query for LinksQuery {
    fn weight(
        &self,
        _: tantivy::query::EnableScoring<'_>,
    ) -> tantivy::Result<Box<dyn tantivy::query::Weight>> {
        Ok(Box::new(LinksWeight {
            node: self.node,
            field: self.field,
            deduplication_field: self.deduplication_field,
            warmed_column_fields: self.warmed_column_fields.clone(),
            skip_self_links: self.skip_self_links,
        }))
    }
}

struct LinksWeight {
    node: NodeID,
    field: FieldEnum,
    deduplication_field: Option<FieldEnum>,
    warmed_column_fields: WarmedColumnFields,
    skip_self_links: bool,
}

impl tantivy::query::Weight for LinksWeight {
    fn scorer(
        &self,
        reader: &tantivy::SegmentReader,
        _: tantivy::Score,
    ) -> tantivy::Result<Box<dyn tantivy::query::Scorer>> {
        let schema = reader.schema();
        let field = schema.get_field(self.field.name())?;
        let term = tantivy::Term::from_field_u128(field, self.node.as_u128());

        match LinksScorer::new(
            reader,
            term,
            self.deduplication_field,
            &self.warmed_column_fields,
            self.node.as_u128(),
            self.skip_self_links,
        ) {
            Ok(Some(scorer)) => Ok(Box::new(scorer)),
            _ => Ok(Box::new(tantivy::query::EmptyScorer)),
        }
    }

    fn explain(
        &self,
        _: &tantivy::SegmentReader,
        _: tantivy::DocId,
    ) -> tantivy::Result<tantivy::query::Explanation> {
        Ok(tantivy::query::Explanation::new("LinksWeight", 0.0))
    }
}

struct LinksScorer {
    postings: SegmentPostings,
    dedup_column: Option<CachedColumn<u128>>,
    last_dedup_val: Option<u128>,
    self_dedup_val: u128,
    skip_self_links: bool,
}

impl LinksScorer {
    fn new(
        reader: &tantivy::SegmentReader,
        term: tantivy::Term,
        deduplication_field: Option<FieldEnum>,
        warmed_column_fields: &WarmedColumnFields,
        self_dedup_val: u128,
        skip_self_links: bool,
    ) -> tantivy::Result<Option<Self>> {
        let dedup_column = deduplication_field.map(|f| {
            warmed_column_fields
                .segment(&reader.segment_id())
                .u128(f)
                .unwrap()
                .to_cached()
        });

        Ok(reader
            .inverted_index(term.field())?
            .read_postings(&term, tantivy::schema::IndexRecordOption::Basic)?
            .map(|mut postings| {
                let mut last_dedup_val = None;

                if postings.doc() != tantivy::TERMINATED {
                    last_dedup_val = dedup_column
                        .as_ref()
                        .map(|c| c.first(postings.doc()).unwrap());
                }

                while postings.doc() != tantivy::TERMINATED
                    && skip_self_links
                    && last_dedup_val == Some(self_dedup_val)
                {
                    postings.advance();

                    if postings.doc() != tantivy::TERMINATED {
                        last_dedup_val = dedup_column
                            .as_ref()
                            .map(|c| c.first(postings.doc()).unwrap());
                    } else {
                        last_dedup_val = None;
                    }
                }

                Self {
                    last_dedup_val,
                    dedup_column,
                    postings,
                    self_dedup_val,
                    skip_self_links,
                }
            }))
    }
}

impl LinksScorer {
    fn dedup_val(&self, doc: tantivy::DocId) -> Option<u128> {
        if doc == tantivy::TERMINATED {
            return None;
        }

        self.dedup_column.as_ref().map(|c| c.first(doc).unwrap())
    }

    fn has_seen(&self, doc: tantivy::DocId) -> bool {
        self.dedup_val(doc)
            .map(|dedup_val| self.last_dedup_val == Some(dedup_val))
            .unwrap_or(false)
    }

    fn skip_self(&self, doc: tantivy::DocId) -> bool {
        self.skip_self_links && self.dedup_val(doc) == Some(self.self_dedup_val)
    }
}

impl tantivy::query::Scorer for LinksScorer {
    fn score(&mut self) -> tantivy::Score {
        unimplemented!()
    }
}
impl tantivy::DocSet for LinksScorer {
    fn advance(&mut self) -> tantivy::DocId {
        self.postings.advance();

        while self.has_seen(
            self.postings
                .block_cursor()
                .skip_reader()
                .last_doc_in_block(),
        ) && self.doc() != tantivy::TERMINATED
        {
            self.postings.mut_block_cursor().advance();
            self.postings.reset_cursor_start_block();
        }

        while (self.has_seen(self.doc()) || self.skip_self(self.doc()))
            && self.doc() != tantivy::TERMINATED
        {
            self.postings.advance();
        }

        if let Some(dedup_val) = self.dedup_val(self.doc()) {
            self.last_dedup_val = Some(dedup_val);
        }

        self.doc()
    }

    fn doc(&self) -> tantivy::DocId {
        self.postings.doc()
    }

    fn size_hint(&self) -> u32 {
        self.postings.size_hint()
    }
}

#[cfg(test)]
mod tests {
    use crate::webgraph::{query::HostBacklinksQuery, Edge, Node, Webgraph};

    #[test]
    fn test_simple() {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(&temp_dir, 0u64.into()).open().unwrap();

        let node_a = Node::from("A");
        let node_b = Node::from("B");
        let node_c = Node::from("C");

        graph
            .insert(Edge::new_test(node_a.clone(), node_b.clone()))
            .unwrap();

        graph
            .insert(Edge::new_test(node_c.clone(), node_b.clone()))
            .unwrap();

        graph.commit().unwrap();

        let res = graph.search(&HostBacklinksQuery::new(node_b.id())).unwrap();

        assert_eq!(res.len(), 2);
        assert!(res.iter().any(|r| r.from == node_a.id()));
        assert!(res.iter().any(|r| r.from == node_c.id()));
    }

    #[test]
    fn test_self_host_skipped() {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(&temp_dir, 0u64.into()).open().unwrap();

        let node_a = Node::from("A");
        let node_b = Node::from("B");

        graph
            .insert(Edge::new_test(node_a.clone(), node_b.clone()))
            .unwrap();

        graph
            .insert(Edge::new_test(node_b.clone(), node_b.clone()))
            .unwrap();

        graph.commit().unwrap();

        let res = graph.search(&HostBacklinksQuery::new(node_b.id())).unwrap();

        assert_eq!(res.len(), 1);
        assert!(res[0].from == node_a.id());
    }

    #[test]
    fn test_deduplication() {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(&temp_dir, 0u64.into()).open().unwrap();

        graph
            .insert(Edge::new_test(
                Node::from("https://A.com/1"),
                Node::from("https://B.com/1"),
            ))
            .unwrap();

        graph
            .insert(Edge::new_test(
                Node::from("https://A.com/2"),
                Node::from("https://B.com/2"),
            ))
            .unwrap();

        graph
            .insert(Edge::new_test(
                Node::from("https://A.com/3"),
                Node::from("https://B.com/3"),
            ))
            .unwrap();

        graph.commit().unwrap();

        let res = graph
            .search(&HostBacklinksQuery::new(
                Node::from("https://B.com/").into_host().id(),
            ))
            .unwrap();

        assert_eq!(res.len(), 1);
        assert!(res[0].from == Node::from("https://A.com/").into_host().id());
    }
}