triblespace_paths/
constraint.rs1use 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#[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 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 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 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 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}