declarative_dataflow/binding/
mod.rs

1//! Binding language, mainly for use in Hector-powered plans.
2
3use std::fmt;
4
5use crate::{Aid, Value, Var};
6
7/// A thing that can act as a binding of values to variables.
8pub trait AsBinding {
9    /// All variables bound by this binding.
10    fn variables(&self) -> Vec<Var>;
11
12    /// Iff the binding has opinions about the given variable, this will
13    /// return the offset, otherwise None.
14    fn binds(&self, variable: Var) -> Option<usize>;
15
16    /// Returns an optional variable which must be bound by the prefix
17    /// in order for this binding to extend the prefix. If None, then
18    /// this binding can never be used to extend the prefix to the
19    /// specified variable (e.g. because it doesn't even bind it).
20    fn required_to_extend(&self, prefix: &AsBinding, target: Var) -> Option<Option<Var>>;
21
22    /// Returns an optional variable by which this binding could
23    /// extend the given prefix.
24    fn ready_to_extend(&self, prefix: &AsBinding) -> Option<Var>;
25
26    /// Returns true iff the binding is ready to participate in the
27    /// extension of a set of prefix variables to a new variable.
28    fn can_extend(&self, prefix: &AsBinding, target: Var) -> bool {
29        self.ready_to_extend(prefix) == Some(target)
30    }
31}
32
33impl AsBinding for Vec<Var> {
34    fn variables(&self) -> Vec<Var> {
35        Vec::new()
36    }
37
38    fn binds(&self, variable: Var) -> Option<usize> {
39        self.iter().position(|&x| variable == x)
40    }
41
42    fn ready_to_extend(&self, _prefix: &AsBinding) -> Option<Var> {
43        None
44    }
45
46    fn required_to_extend(&self, _prefix: &AsBinding, _target: Var) -> Option<Option<Var>> {
47        Some(None)
48    }
49}
50
51/// Binding types supported by Hector.
52#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Debug, Serialize, Deserialize)]
53pub enum Binding {
54    /// Two variables bound by (e,v) pairs from an attribute.
55    Attribute(AttributeBinding),
56    /// Variables that must not be bound by the wrapped binding.
57    Not(AntijoinBinding),
58    /// A variable bound by a constant value.
59    Constant(ConstantBinding),
60    /// Two variables bound by a binary predicate.
61    BinaryPredicate(BinaryPredicateBinding),
62}
63
64impl Binding {
65    /// Creates an AttributeBinding.
66    pub fn attribute(e: Var, name: &str, v: Var) -> Binding {
67        Binding::Attribute(AttributeBinding {
68            variables: (e, v),
69            source_attribute: name.to_string(),
70        })
71    }
72
73    /// Creates a ConstantBinding.
74    pub fn constant(variable: Var, value: Value) -> Binding {
75        Binding::Constant(ConstantBinding { variable, value })
76    }
77
78    /// Creates a BinaryPredicateBinding.
79    pub fn binary_predicate(predicate: BinaryPredicate, x: Var, y: Var) -> Binding {
80        Binding::BinaryPredicate(BinaryPredicateBinding {
81            variables: (x, y),
82            predicate,
83        })
84    }
85
86    /// Creates an AntijoinBinding.
87    pub fn not(binding: Binding) -> Binding {
88        Binding::Not(AntijoinBinding {
89            binding: Box::new(binding),
90        })
91    }
92}
93
94impl AsBinding for Binding {
95    fn variables(&self) -> Vec<Var> {
96        match *self {
97            Binding::Attribute(ref binding) => binding.variables(),
98            Binding::Not(ref binding) => binding.variables(),
99            Binding::Constant(ref binding) => binding.variables(),
100            Binding::BinaryPredicate(ref binding) => binding.variables(),
101        }
102    }
103
104    fn binds(&self, variable: Var) -> Option<usize> {
105        match *self {
106            Binding::Attribute(ref binding) => binding.binds(variable),
107            Binding::Not(ref binding) => binding.binds(variable),
108            Binding::Constant(ref binding) => binding.binds(variable),
109            Binding::BinaryPredicate(ref binding) => binding.binds(variable),
110        }
111    }
112
113    fn ready_to_extend(&self, prefix: &AsBinding) -> Option<Var> {
114        match *self {
115            Binding::Attribute(ref binding) => binding.ready_to_extend(prefix),
116            Binding::Not(ref binding) => binding.ready_to_extend(prefix),
117            Binding::Constant(ref binding) => binding.ready_to_extend(prefix),
118            Binding::BinaryPredicate(ref binding) => binding.ready_to_extend(prefix),
119        }
120    }
121
122    fn required_to_extend(&self, prefix: &AsBinding, target: Var) -> Option<Option<Var>> {
123        match *self {
124            Binding::Attribute(ref binding) => binding.required_to_extend(prefix, target),
125            Binding::Not(ref binding) => binding.required_to_extend(prefix, target),
126            Binding::Constant(ref binding) => binding.required_to_extend(prefix, target),
127            Binding::BinaryPredicate(ref binding) => binding.required_to_extend(prefix, target),
128        }
129    }
130}
131
132/// Describes variables whose possible values are given by an attribute.
133#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Serialize, Deserialize)]
134pub struct AttributeBinding {
135    /// The variables this binding talks about.
136    pub variables: (Var, Var),
137    /// The name of a globally known attribute backing this binding.
138    pub source_attribute: Aid,
139}
140
141impl AsBinding for AttributeBinding {
142    fn variables(&self) -> Vec<Var> {
143        vec![self.variables.0, self.variables.1]
144    }
145
146    fn binds(&self, variable: Var) -> Option<usize> {
147        if self.variables.0 == variable {
148            Some(0)
149        } else if self.variables.1 == variable {
150            Some(1)
151        } else {
152            None
153        }
154    }
155
156    fn ready_to_extend(&self, prefix: &AsBinding) -> Option<Var> {
157        if prefix.binds(self.variables.0).is_some() && prefix.binds(self.variables.1).is_none() {
158            Some(self.variables.1)
159        } else if prefix.binds(self.variables.1).is_some()
160            && prefix.binds(self.variables.0).is_none()
161        {
162            Some(self.variables.0)
163        } else {
164            None
165        }
166    }
167
168    fn required_to_extend(&self, prefix: &AsBinding, target: Var) -> Option<Option<Var>> {
169        match self.binds(target) {
170            None => None,
171            Some(offset) => {
172                // Self binds target at offset.
173                if offset == 0 {
174                    // Ensure that the prefix doesn't in fact bind _both_ variables already.
175                    assert!(prefix.binds(self.variables.0).is_none());
176                    match prefix.binds(self.variables.1) {
177                        None => Some(Some(self.variables.1)),
178                        Some(_) => Some(None),
179                    }
180                } else {
181                    // Analogously for the reverse case.
182                    assert!(prefix.binds(self.variables.1).is_none());
183                    match prefix.binds(self.variables.0) {
184                        None => Some(Some(self.variables.0)),
185                        Some(_) => Some(None),
186                    }
187                }
188            }
189        }
190    }
191}
192
193impl fmt::Debug for AttributeBinding {
194    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
195        write!(
196            f,
197            "[{} {} {}]",
198            self.variables.0, self.source_attribute, self.variables.1
199        )
200    }
201}
202
203/// Describes variables whose possible values must not be contained in
204/// the specified attribute.
205#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Serialize, Deserialize)]
206pub struct AntijoinBinding {
207    /// The wrapped binding.
208    pub binding: Box<Binding>,
209}
210
211impl AsBinding for AntijoinBinding {
212    fn variables(&self) -> Vec<Var> {
213        self.binding.variables()
214    }
215
216    fn binds(&self, variable: Var) -> Option<usize> {
217        self.binding.binds(variable)
218    }
219
220    fn ready_to_extend(&self, prefix: &AsBinding) -> Option<Var> {
221        self.binding.ready_to_extend(prefix)
222    }
223
224    fn required_to_extend(&self, prefix: &AsBinding, target: Var) -> Option<Option<Var>> {
225        self.binding.required_to_extend(prefix, target)
226    }
227}
228
229impl fmt::Debug for AntijoinBinding {
230    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
231        write!(f, "Not({:?})", self.binding)
232    }
233}
234
235/// Describes variables whose possible values are given by an attribute.
236#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Serialize, Deserialize)]
237pub struct ConstantBinding {
238    /// The variable this binding talks about.
239    pub variable: Var,
240    /// The value backing this binding.
241    pub value: Value,
242}
243
244impl AsBinding for ConstantBinding {
245    fn variables(&self) -> Vec<Var> {
246        vec![self.variable]
247    }
248
249    fn binds(&self, variable: Var) -> Option<usize> {
250        if self.variable == variable {
251            Some(0)
252        } else {
253            None
254        }
255    }
256
257    fn ready_to_extend(&self, prefix: &AsBinding) -> Option<Var> {
258        if prefix.binds(self.variable).is_none() {
259            Some(self.variable)
260        } else {
261            None
262        }
263    }
264
265    fn required_to_extend(&self, prefix: &AsBinding, target: Var) -> Option<Option<Var>> {
266        match self.binds(target) {
267            None => None,
268            Some(_) => match prefix.binds(target) {
269                None => Some(Some(self.variable)),
270                Some(_) => Some(None),
271            },
272        }
273    }
274}
275
276impl fmt::Debug for ConstantBinding {
277    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
278        write!(f, "Constant({}, {:?})", self.variable, self.value)
279    }
280}
281
282/// Built-in binary predicates.
283#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Debug, Serialize, Deserialize)]
284pub enum BinaryPredicate {
285    /// Less than
286    LT,
287    /// Greater than
288    GT,
289    /// Less than or equal to
290    LTE,
291    /// Greater than or equal to
292    GTE,
293    /// Equal
294    EQ,
295    /// Not equal
296    NEQ,
297}
298
299/// Describe a binary predicate constraint.
300#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Serialize, Deserialize)]
301pub struct BinaryPredicateBinding {
302    /// The variables this binding talks about.
303    pub variables: (Var, Var),
304    /// Logical predicate to apply.
305    pub predicate: BinaryPredicate,
306}
307
308impl AsBinding for BinaryPredicateBinding {
309    fn variables(&self) -> Vec<Var> {
310        vec![self.variables.0, self.variables.1]
311    }
312
313    fn binds(&self, variable: Var) -> Option<usize> {
314        if self.variables.0 == variable {
315            Some(0)
316        } else if self.variables.1 == variable {
317            Some(1)
318        } else {
319            None
320        }
321    }
322
323    fn ready_to_extend(&self, prefix: &AsBinding) -> Option<Var> {
324        if prefix.binds(self.variables.0).is_some() && prefix.binds(self.variables.1).is_none() {
325            Some(self.variables.1)
326        } else if prefix.binds(self.variables.1).is_some()
327            && prefix.binds(self.variables.0).is_none()
328        {
329            Some(self.variables.0)
330        } else {
331            None
332        }
333    }
334
335    fn required_to_extend(&self, prefix: &AsBinding, target: Var) -> Option<Option<Var>> {
336        match self.binds(target) {
337            None => None,
338            Some(offset) => {
339                // Self binds target at offset.
340                if offset == 0 {
341                    // Ensure that the prefix doesn't in fact bind _both_ variables already.
342                    assert!(prefix.binds(self.variables.0).is_none());
343                    match prefix.binds(self.variables.1) {
344                        None => Some(Some(self.variables.1)),
345                        Some(_) => Some(None),
346                    }
347                } else {
348                    // Analogously for the reverse case.
349                    assert!(prefix.binds(self.variables.1).is_none());
350                    match prefix.binds(self.variables.0) {
351                        None => Some(Some(self.variables.0)),
352                        Some(_) => Some(None),
353                    }
354                }
355            }
356        }
357    }
358}
359
360impl fmt::Debug for BinaryPredicateBinding {
361    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
362        write!(
363            f,
364            "({:?} {} {})",
365            self.predicate, self.variables.0, self.variables.1
366        )
367    }
368}
declarative_dataflow/binding/mod.rs

declarative_dataflow/binding/
mod.rs
