triblespace_core/query/
intersectionconstraint.rs

1use super::*;
2use smallvec::SmallVec;
3
4/// Logical conjunction of constraints (AND).
5///
6/// All children must agree on every variable binding. Built by the
7/// [`and!`](crate::and) macro or directly via [`new`](Self::new).
8///
9/// The intersection delegates to its children using cardinality-aware
10/// ordering: the child with the lowest [`estimate`](Constraint::estimate)
11/// proposes candidates, and the remaining children
12/// [`confirm`](Constraint::confirm) them in order of increasing estimate.
13/// This strategy keeps the candidate set small from the start and avoids
14/// materialising cross products.
15///
16/// Variables from all children are exposed as a single union, so the
17/// engine sees one flat set of variables regardless of how many
18/// sub-constraints contribute.
19pub struct IntersectionConstraint<C> {
20    constraints: Vec<C>,
21}
22
23impl<'a, C> IntersectionConstraint<C>
24where
25    C: Constraint<'a> + 'a,
26{
27    /// Creates an intersection over the given constraints.
28    pub fn new(constraints: Vec<C>) -> Self {
29        IntersectionConstraint { constraints }
30    }
31}
32
33impl<'a, C> Constraint<'a> for IntersectionConstraint<C>
34where
35    C: Constraint<'a> + 'a,
36{
37    /// Returns the union of all children's variable sets.
38    fn variables(&self) -> VariableSet {
39        self.constraints
40            .iter()
41            .fold(VariableSet::new_empty(), |vs, c| vs.union(c.variables()))
42    }
43
44    /// Returns the **minimum** estimate across children that constrain
45    /// `variable`. The tightest child bounds the search, reflecting the
46    /// intersection semantics: every child must agree, so the smallest
47    /// candidate set dominates.
48    fn estimate(&self, variable: VariableId, binding: &Binding) -> Option<usize> {
49        self.constraints
50            .iter()
51            .filter_map(|c| c.estimate(variable, binding))
52            .min()
53    }
54
55    /// Sorts children by estimate, lets the tightest one propose, then
56    /// confirms through the rest in ascending estimate order. Children
57    /// that return `None` for this variable are skipped entirely.
58    fn propose(&self, variable: VariableId, binding: &Binding, proposals: &mut Vec<RawInline>) {
59        let mut relevant_constraints: SmallVec<[(usize, &C); 8]> = self
60            .constraints
61            .iter()
62            .filter_map(|c| Some((c.estimate(variable, binding)?, c)))
63            .collect();
64        if relevant_constraints.is_empty() {
65            return;
66        }
67        relevant_constraints.sort_unstable_by_key(|(estimate, _)| *estimate);
68
69        relevant_constraints[0]
70            .1
71            .propose(variable, binding, proposals);
72
73        relevant_constraints[1..]
74            .iter()
75            .for_each(|(_, c)| c.confirm(variable, binding, proposals));
76    }
77
78    /// Confirms proposals through all children that constrain `variable`,
79    /// in order of increasing estimate.
80    fn confirm(&self, variable: VariableId, binding: &Binding, proposals: &mut Vec<RawInline>) {
81        let mut relevant_constraints: SmallVec<[(usize, &C); 8]> = self
82            .constraints
83            .iter()
84            .filter_map(|c| Some((c.estimate(variable, binding)?, c)))
85            .collect();
86        relevant_constraints.sort_unstable_by_key(|(estimate, _)| *estimate);
87
88        relevant_constraints
89            .iter()
90            .for_each(|(_, c)| c.confirm(variable, binding, proposals));
91    }
92
93    /// Returns `true` only when **every** child is satisfied.
94    fn satisfied(&self, binding: &Binding) -> bool {
95        self.constraints.iter().all(|c| c.satisfied(binding))
96    }
97
98    /// Returns the union of all children's influence sets for `variable`.
99    fn influence(&self, variable: VariableId) -> VariableSet {
100        self.constraints
101            .iter()
102            .fold(VariableSet::new_empty(), |acc, c| {
103                acc.union(c.influence(variable))
104            })
105    }
106}
107
108/// Combines constraints into an [`IntersectionConstraint`] (logical AND).
109///
110/// All constraints must agree on every variable binding for a result to
111/// be produced. Accepts one or more constraint expressions.
112///
113/// ```rust,ignore
114/// and!(set.pattern(e, a, v), allowed.has(v))
115/// ```
116#[macro_export]
117macro_rules! and {
118    // Emits `Arc<IntersectionConstraint<Box<dyn Constraint + Send + Sync>>>`.
119    // The outer `Arc` makes the whole tree cheap to `Clone` (single
120    // refcount bump) — required by the `parallel` feature's `Query::clone`
121    // during rayon split. `Send + Sync` on the trait object lets the tree
122    // cross rayon thread boundaries. Every in-tree constraint built via
123    // this macro already satisfies Send + Sync; non-thread-safe constraint
124    // types (e.g. `Rc`-backed ContainsConstraint variants) can still be
125    // used via direct `IntersectionConstraint::new` construction.
126    ($($c:expr),+ $(,)?) => (
127        ::std::sync::Arc::new(
128            $crate::query::intersectionconstraint::IntersectionConstraint::new(vec![
129                $(Box::new($c)
130                    as Box<dyn $crate::query::Constraint + Send + Sync>),+
131            ])
132        )
133    )
134}
135
136/// Re-export of the [`and!`] macro.
137pub use and;
triblespace_core/query/intersectionconstraint.rs

triblespace_core/query/
intersectionconstraint.rs
