Skip to main content

triblespace_paths/
constraint.rs

1use triblespace_core::inline::InlineEncoding;
2use triblespace_core::query::{
3    Binding, Candidates, Constraint, Frontier, ProposalBuffer, RawTerm, Term, VariableId,
4    VariableSet,
5};
6
7use crate::PathIndex;
8
9/// A two-endpoint view of a [`PathIndex`] for the ordinary query solver.
10#[derive(Clone, Copy, Debug)]
11pub struct PathConstraint<'a> {
12    index: &'a PathIndex,
13    start: RawTerm,
14    end: RawTerm,
15}
16
17impl<'a> PathConstraint<'a> {
18    /// Constrains `start` and `end` to an accepted pair in `index`.
19    pub fn new<S: InlineEncoding, E: InlineEncoding>(
20        index: &'a PathIndex,
21        start: impl Into<Term<S>>,
22        end: impl Into<Term<E>>,
23    ) -> Self {
24        Self {
25            index,
26            start: start.into().erase(),
27            end: end.into().erase(),
28        }
29    }
30
31    fn candidates(&self, variable: VariableId, binding: &Binding) -> Option<&[u32]> {
32        let at_start = self.start.is_var(variable);
33        let at_end = self.end.is_var(variable);
34        match (at_start, at_end) {
35            (false, false) => None,
36            (true, true) => Some(self.index.diagonal_ordinals()),
37            (true, false) => Some(match self.end.position_value(binding) {
38                Some(end) => self.index.reverse_ordinals(end),
39                None => self.index.starts_ordinals(),
40            }),
41            (false, true) => Some(match self.start.position_value(binding) {
42                Some(start) => self.index.forward_ordinals(start),
43                None => self.index.ends_ordinals(),
44            }),
45        }
46    }
47
48    fn is_same_unbound_variable(&self, binding: &Binding) -> bool {
49        matches!(
50            (self.start, self.end),
51            (RawTerm::Var(start), RawTerm::Var(end))
52                if start == end && binding.get(start).is_none()
53        )
54    }
55}
56
57impl<'a> Constraint<'a> for PathConstraint<'a> {
58    fn variables(&self) -> VariableSet {
59        let mut variables = VariableSet::new_empty();
60        self.start.add_to(&mut variables);
61        self.end.add_to(&mut variables);
62        variables
63    }
64
65    fn estimate(&self, variable: VariableId, binding: &Binding) -> Option<usize> {
66        self.candidates(variable, binding).map(<[u32]>::len)
67    }
68
69    /// Proposes each row's own ordinal run. Which endpoint is bound is
70    /// uniform across the batch; the bound *value* is not, so the ordinal
71    /// slice is looked up once per row.
72    fn propose(
73        &self,
74        variable: VariableId,
75        frontier: &Frontier<'_>,
76        proposals: &mut ProposalBuffer,
77    ) {
78        for row in 0..frontier.len() {
79            if let Some(ordinals) = self.candidates(variable, &frontier.row(row)) {
80                proposals.open(row as u32);
81                proposals.extend(self.index.values(ordinals));
82            }
83        }
84    }
85
86    /// Confirms each candidate against its own row's ordinal run — one
87    /// lookup per run of equal parent tags rather than one per candidate.
88    fn confirm(
89        &self,
90        variable: VariableId,
91        frontier: &Frontier<'_>,
92        candidates: &mut Candidates<'_>,
93    ) {
94        candidates.for_each_parent(|row, run| {
95            if let Some(ordinals) = self.candidates(variable, &frontier.row(row as usize)) {
96                run.retain(|candidate| self.index.ordinal_in(ordinals, candidate));
97            }
98        });
99    }
100
101    fn satisfied(&self, binding: &Binding) -> bool {
102        let start = self.start.position_value(binding);
103        let end = self.end.position_value(binding);
104        match (start, end) {
105            (Some(start), Some(end)) => self.index.contains(start, end),
106            (Some(start), None) => !self.index.forward_ordinals(start).is_empty(),
107            (None, Some(end)) => !self.index.reverse_ordinals(end).is_empty(),
108            (None, None) if self.is_same_unbound_variable(binding) => {
109                !self.index.diagonal_ordinals().is_empty()
110            }
111            (None, None) => self.index.accepted_pair_count() != 0,
112        }
113    }
114}
115
116impl PathIndex {
117    /// Creates an ordinary query constraint over this path relation.
118    pub fn constraint<'a, S: InlineEncoding, E: InlineEncoding>(
119        &'a self,
120        start: impl Into<Term<S>>,
121        end: impl Into<Term<E>>,
122    ) -> PathConstraint<'a> {
123        PathConstraint::new(self, start, end)
124    }
125}