Skip to content

web search done right

18.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 super::query;

use super::*;

impl Webgraph {
    pub fn ingoing_edges(&self, node: Node, limit: EdgeLimit) -> Vec<Edge> {
        self.search(&query::FullBacklinksQuery::new(node).with_limit(limit))
            .unwrap_or_default()
    }

    pub fn raw_ingoing_edges(&self, node: &NodeID, limit: EdgeLimit) -> Vec<SmallEdge> {
        self.search(&query::BacklinksQuery::new(*node).with_limit(limit))
            .unwrap_or_default()
    }

    pub fn raw_ingoing_edges_with_labels(
        &self,
        node: &NodeID,
        limit: EdgeLimit,
    ) -> Vec<SmallEdgeWithLabel> {
        self.search(&query::BacklinksWithLabelsQuery::new(*node).with_limit(limit))
            .unwrap_or_default()
    }

    pub fn outgoing_edges(&self, node: Node, limit: EdgeLimit) -> Vec<Edge> {
        self.search(&query::FullForwardlinksQuery::new(node).with_limit(limit))
            .unwrap_or_default()
    }

    pub fn raw_outgoing_edges(&self, node: &NodeID, limit: EdgeLimit) -> Vec<SmallEdge> {
        self.search(&query::ForwardlinksQuery::new(*node).with_limit(limit))
            .unwrap_or_default()
    }
}

use crate::config::WebgraphGranularity;
use crate::webpage::html::links::RelFlags;

use file_store::temp::TempDir;
use proptest::prelude::*;

pub fn test_edges() -> Vec<(Node, Node)> {
    vec![
        (Node::from("A"), Node::from("B")),
        (Node::from("B"), Node::from("C")),
        (Node::from("A"), Node::from("C")),
        (Node::from("C"), Node::from("A")),
        (Node::from("D"), Node::from("C")),
    ]
}

pub fn test_graph() -> (Webgraph, TempDir) {
    //     ┌-----┐
    //     │     │
    // ┌───A◄─┐  │
    // │      │  │
    // ▼      │  │
    // B─────►C◄-┘
    //        ▲
    //        │
    //        │
    //        D

    let temp_dir = crate::gen_temp_dir().unwrap();
    let mut graph = Webgraph::builder(&temp_dir, 0u64.into()).open().unwrap();

    for (from, to) in test_edges() {
        graph.insert(Edge::new_test(from, to)).unwrap();
    }

    graph.commit().unwrap();

    (graph, temp_dir)
}

#[test]
fn distance_calculation() {
    let (graph, _temp_dir) = test_graph();

    let distances = graph.distances(Node::from("D"), WebgraphGranularity::Page);

    assert_eq!(distances.get(&Node::from("C")), Some(&1));
    assert_eq!(distances.get(&Node::from("A")), Some(&2));
    assert_eq!(distances.get(&Node::from("B")), Some(&3));
}

#[test]
fn nonexisting_node() {
    let (graph, _temp_dir) = test_graph();
    assert_eq!(
        graph
            .distances(Node::from("E"), WebgraphGranularity::Page)
            .len(),
        0
    );
    assert_eq!(
        graph
            .reversed_distances(Node::from("E"), WebgraphGranularity::Page)
            .len(),
        0
    );
}

#[test]
fn reversed_distance_calculation() {
    let (graph, _temp_dir) = test_graph();

    let distances = graph.reversed_distances(Node::from("D"), WebgraphGranularity::Page);

    assert_eq!(distances.get(&Node::from("C")), None);
    assert_eq!(distances.get(&Node::from("A")), None);
    assert_eq!(distances.get(&Node::from("B")), None);

    let distances = graph.reversed_distances(Node::from("A"), WebgraphGranularity::Page);

    assert_eq!(distances.get(&Node::from("C")), Some(&1));
    assert_eq!(distances.get(&Node::from("D")), Some(&2));
    assert_eq!(distances.get(&Node::from("B")), Some(&2));
}

#[test]
fn merge_path() {
    let mut graphs = Vec::new();
    let temp_dir = crate::gen_temp_dir().unwrap();
    for (i, (from, to)) in (0..).zip([
        (Node::from("A"), Node::from("B")),
        (Node::from("B"), Node::from("C")),
        (Node::from("C"), Node::from("D")),
        (Node::from("D"), Node::from("E")),
        (Node::from("E"), Node::from("F")),
        (Node::from("F"), Node::from("G")),
        (Node::from("G"), Node::from("H")),
    ]) {
        let mut graph =
            Webgraph::builder(&temp_dir.as_ref().join(format!("test_{}", i)), 0u64.into())
                .open()
                .unwrap();
        graph.insert(Edge::new_test(from, to)).unwrap();
        graph.commit().unwrap();
        graphs.push(graph);
    }

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    graph.optimize_read().unwrap();

    assert_eq!(
        graph
            .distances(Node::from("A"), WebgraphGranularity::Page)
            .get(&Node::from("H")),
        Some(&7)
    );

    assert_eq!(
        graph
            .reversed_distances(Node::from("H"), WebgraphGranularity::Page)
            .get(&Node::from("A")),
        Some(&7)
    );
}

#[test]
fn merge_simple() {
    let mut graphs = Vec::new();
    let temp_dir = crate::gen_temp_dir().unwrap();
    for (i, (from, to)) in (0..).zip(test_edges()) {
        let mut graph =
            Webgraph::builder(&temp_dir.as_ref().join(format!("test_{}", i)), 0u64.into())
                .open()
                .unwrap();
        graph.insert(Edge::new_test(from, to)).unwrap();
        graph.commit().unwrap();
        graphs.push(graph);
    }

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    graph.optimize_read().unwrap();

    let mut res = graph.outgoing_edges(Node::from("A"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.to.cmp(&b.to));
    assert_eq!(res.len(), 2);

    assert_eq!(res[0].to, Node::from("B"));
    assert_eq!(res[1].to, Node::from("C"));

    let mut res = graph.outgoing_edges(Node::from("B"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.to.cmp(&b.to));

    assert_eq!(res.len(), 1);
    assert_eq!(res[0].to, Node::from("C"));

    let mut res = graph.outgoing_edges(Node::from("C"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.to.cmp(&b.to));

    assert_eq!(res.len(), 1);
    assert_eq!(res[0].to, Node::from("A"));

    let mut res = graph.outgoing_edges(Node::from("D"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.to.cmp(&b.to));

    assert_eq!(res.len(), 1);
    assert_eq!(res[0].to, Node::from("C"));

    let mut res = graph.ingoing_edges(Node::from("A"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.from.cmp(&b.from));

    assert_eq!(res.len(), 1);
    assert_eq!(res[0].from, Node::from("C"));

    let mut res = graph.ingoing_edges(Node::from("B"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.from.cmp(&b.from));

    assert_eq!(res.len(), 1);
    assert_eq!(res[0].from, Node::from("A"));

    let mut res = graph.ingoing_edges(Node::from("C"), EdgeLimit::Unlimited);
    res.sort_by(|a, b| a.from.cmp(&b.from));

    assert_eq!(res.len(), 3);
    assert_eq!(res[0].from, Node::from("A"));
    assert_eq!(res[1].from, Node::from("B"));
    assert_eq!(res[2].from, Node::from("D"));
}

#[test]
fn merge_cycle() {
    let mut graphs = Vec::new();
    let temp_dir = crate::gen_temp_dir().unwrap();
    for (i, (from, to)) in (0..).zip([
        (Node::from("A"), Node::from("B")),
        (Node::from("B"), Node::from("A")),
        (Node::from("B"), Node::from("C")),
        (Node::from("C"), Node::from("A")),
    ]) {
        let mut graph =
            Webgraph::builder(&temp_dir.as_ref().join(format!("test_{}", i)), 0u64.into())
                .open()
                .unwrap();
        graph.insert(Edge::new_test(from, to)).unwrap();
        graph.commit().unwrap();
        graphs.push(graph);
    }

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    assert_eq!(
        graph
            .distances(Node::from("A"), WebgraphGranularity::Page)
            .get(&Node::from("C")),
        Some(&2)
    );

    graph.optimize_read().unwrap();

    assert_eq!(
        graph
            .distances(Node::from("A"), WebgraphGranularity::Page)
            .get(&Node::from("C")),
        Some(&2)
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Unlimited)
            .len(),
        1
    );
    assert_eq!(
        graph
            .outgoing_edges(Node::from("B"), EdgeLimit::Unlimited)
            .len(),
        2
    );
    assert_eq!(
        graph
            .outgoing_edges(Node::from("C"), EdgeLimit::Unlimited)
            .len(),
        1
    );
}

#[test]
fn merge_star() {
    let mut graphs = Vec::new();
    let temp_dir = crate::gen_temp_dir().unwrap();
    for (i, (from, to)) in (0..).zip([
        (Node::from("A"), Node::from("B")),
        (Node::from("A"), Node::from("C")),
        (Node::from("A"), Node::from("D")),
        (Node::from("A"), Node::from("E")),
    ]) {
        let mut graph =
            Webgraph::builder(&temp_dir.as_ref().join(format!("test_{}", i)), 0u64.into())
                .open()
                .unwrap();
        graph.insert(Edge::new_test(from, to)).unwrap();
        graph.commit().unwrap();
        graphs.push(graph);
    }

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    graph.optimize_read().unwrap();

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Unlimited)
            .len(),
        4
    );

    assert_eq!(
        graph
            .ingoing_edges(Node::from("B"), EdgeLimit::Unlimited)
            .len(),
        1
    );

    assert_eq!(
        graph
            .ingoing_edges(Node::from("C"), EdgeLimit::Unlimited)
            .len(),
        1
    );

    assert_eq!(
        graph
            .ingoing_edges(Node::from("D"), EdgeLimit::Unlimited)
            .len(),
        1
    );
}

#[test]
fn merge_reverse_star() {
    let mut graphs = Vec::new();
    let temp_dir = crate::gen_temp_dir().unwrap();
    for (i, (from, to)) in (0..).zip([
        (Node::from("B"), Node::from("A")),
        (Node::from("C"), Node::from("A")),
        (Node::from("D"), Node::from("A")),
        (Node::from("E"), Node::from("A")),
    ]) {
        let mut graph =
            Webgraph::builder(&temp_dir.as_ref().join(format!("test_{}", i)), 0u64.into())
                .open()
                .unwrap();
        graph.insert(Edge::new_test(from, to)).unwrap();
        graph.commit().unwrap();
        graphs.push(graph);
    }

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    graph.optimize_read().unwrap();

    assert_eq!(
        graph
            .ingoing_edges(Node::from("A"), EdgeLimit::Unlimited)
            .len(),
        4
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("B"), EdgeLimit::Unlimited)
            .len(),
        1
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("C"), EdgeLimit::Unlimited)
            .len(),
        1
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("D"), EdgeLimit::Unlimited)
            .len(),
        1
    );
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(8))]

    #[test]
    fn prop_merge(
        nodes in
        proptest::collection::vec(
            ("[a-z]", "[a-z]"), 0..100
        )
    ) {
        let mut graphs = Vec::new();
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(&temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()), 0u64.into())
            .open()
            .unwrap();
        for (from, to) in nodes.clone() {
            graph.insert(Edge::new_test(
                Node::new_for_test(from.as_str()),
                Node::new_for_test(to.as_str()),
            )).unwrap();

            if rand::random::<usize>() % 10 == 0 {
                graph.commit().unwrap();
                graphs.push(graph);
                graph = Webgraph::builder(&temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()), 0u64.into())
                    .open()
                    .unwrap();
            }
        }

        if graphs.is_empty() {
            return Ok(());
        }

        graphs.push(graph);

        let mut graph = graphs.pop().unwrap();


        for other in graphs {
            graph.merge(other).unwrap();
        }


        for (from, to) in nodes {
            if from == to {
                continue;
            }

            let from = Node::new_for_test(from.as_str());
            let to = Node::new_for_test(to.as_str());

            let outgoing = graph.outgoing_edges(from.clone(), EdgeLimit::Unlimited);
            let ingoing = graph.ingoing_edges(to.clone(), EdgeLimit::Unlimited);

            prop_assert!(outgoing.iter().any(|e| e.to == to));
            prop_assert!(ingoing.iter().any(|e| e.from == from));
        }
    }
}

fn proptest_case(nodes: &[(&str, &str)]) {
    let mut graphs = Vec::new();
    let temp_dir = crate::gen_temp_dir().unwrap();
    let mut graph = Webgraph::builder(
        &temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()),
        0u64.into(),
    )
    .open()
    .unwrap();

    for (i, (from, to)) in nodes.iter().enumerate() {
        graph
            .insert(Edge::new_test(
                Node::new_for_test(from),
                Node::new_for_test(to),
            ))
            .unwrap();

        if i % 2 == 0 {
            graph.commit().unwrap();
            graphs.push(graph);
            graph = Webgraph::builder(
                &temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()),
                0u64.into(),
            )
            .open()
            .unwrap();
        }
    }

    graphs.push(graph);

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    for (from, to) in nodes {
        if from == to {
            continue;
        }

        let from = Node::new_for_test(from);
        let to = Node::new_for_test(to);

        let outgoing = graph.outgoing_edges(from.clone(), EdgeLimit::Unlimited);
        let ingoing = graph.ingoing_edges(to.clone(), EdgeLimit::Unlimited);

        assert!(outgoing.iter().any(|e| e.to == to));
        assert!(ingoing.iter().any(|e| e.from == from));
    }
}

#[test]
fn merge_proptest_case1() {
    let nodes = [("k", "d"), ("k", "t"), ("y", "m")];
    proptest_case(&nodes);
}

#[test]
fn merge_proptest_case2() {
    let nodes = [("i", "k"), ("k", "g"), ("y", "m"), ("q", "r"), ("e", "g")];

    proptest_case(&nodes);
}

#[test]
fn merge_proptest_case3() {
    let nodes = [("h", "c"), ("r", "r")];

    proptest_case(&nodes);
}

#[test]
fn node_lowercase_name() {
    let n = Node::from("TEST".to_string());
    assert_eq!(n.as_str(), "test");
}

#[test]
fn host_node_cleanup() {
    let n = Node::from("https://www.example.com?test").into_host();
    assert_eq!(n.as_str(), "example.com");
}

#[test]
fn remove_protocol() {
    let n = Node::from("https://www.example.com/?test");

    assert_eq!(n.as_str(), "example.com/?test=");
}

#[test]
fn cap_label_length() {
    let temp_dir = crate::gen_temp_dir().unwrap();
    let mut graph = Webgraph::builder(
        &temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()),
        0u64.into(),
    )
    .open()
    .unwrap();

    graph
        .insert(Edge {
            from: Node::from("A"),
            to: Node::from("B"),
            label: "a".repeat(MAX_LABEL_LENGTH + 1),
            ..Edge::empty()
        })
        .unwrap();

    graph.commit().unwrap();

    assert_eq!(
        graph.outgoing_edges(Node::from("A"), EdgeLimit::Unlimited)[0].label,
        "a".repeat(MAX_LABEL_LENGTH)
    );
}

#[test]
fn test_edge_limits() {
    let (graph, temp_dir) = test_graph();

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Unlimited)
            .len(),
        2
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Limit(1))
            .len(),
        1
    );

    let mut graphs = Vec::new();
    for (from, to) in &[
        (Node::from("A"), Node::from("B")),
        (Node::from("A"), Node::from("C")),
    ] {
        let mut graph = Webgraph::builder(
            &temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()),
            0u64.into(),
        )
        .open()
        .unwrap();
        graph
            .insert(Edge::new_test(from.clone(), to.clone()))
            .unwrap();
        graph.commit().unwrap();
        graphs.push(graph);
    }

    let mut graph = graphs.pop().unwrap();

    for other in graphs {
        graph.merge(other).unwrap();
    }

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Unlimited)
            .len(),
        2
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Limit(1))
            .len(),
        1
    );

    graph.optimize_read().unwrap();

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Unlimited)
            .len(),
        2
    );

    assert_eq!(
        graph
            .outgoing_edges(Node::from("A"), EdgeLimit::Limit(1))
            .len(),
        1
    );
}

#[test]
fn test_node_normalized() {
    let n = Node::from("http://www.example.com/abc");
    assert_eq!(n.as_str(), "example.com/abc");

    let n = Node::from("http://www.example.com/abc#123");
    assert_eq!(n.as_str(), "example.com/abc");
}

#[test]
fn test_rel_flags() {
    let temp_dir = crate::gen_temp_dir().unwrap();
    let mut graph = Webgraph::builder(
        &temp_dir.as_ref().join(uuid::Uuid::new_v4().to_string()),
        0u64.into(),
    )
    .open()
    .unwrap();

    graph
        .insert(Edge {
            from: Node::from("A"),
            to: Node::from("B"),
            rel_flags: RelFlags::IS_IN_FOOTER | RelFlags::TAG,
            ..Edge::empty()
        })
        .unwrap();

    graph.commit().unwrap();

    assert_eq!(
        graph.raw_outgoing_edges(&Node::from("A").id(), EdgeLimit::Unlimited)[0].rel_flags,
        RelFlags::IS_IN_FOOTER | RelFlags::TAG,
    );
}

#[test]
fn test_limit_and_offset() {
    let (graph, _temp_dir) = test_graph();

    let no_offset = graph.raw_outgoing_edges(
        &Node::from("A").id(),
        EdgeLimit::LimitAndOffset {
            limit: 2,
            offset: 0,
        },
    );
    assert_eq!(no_offset.len(), 2);

    let edges = graph.raw_outgoing_edges(
        &Node::from("A").id(),
        EdgeLimit::LimitAndOffset {
            limit: 2,
            offset: 1,
        },
    );
    assert_eq!(edges.len(), 1);
    assert_eq!(edges[0].to, no_offset[1].to);
}