reddb_server/storage/query/engine/
binding.rs

1//! Variable Bindings
2//!
3//! Maps variables to values during query execution.
4//!
5//! # Design
6//!
7//! - Immutable bindings for thread safety
8//! - Parent binding support for scoped lookups
9//! - Size-optimized implementations for common cases
10//! - Builder pattern for construction
11
12use std::collections::HashMap;
13use std::fmt;
14use std::hash::{Hash, Hasher};
15use std::sync::Arc;
16
17use crate::json;
18use crate::serde_json::{Map as JsonMap, Value as JsonValue};
19
20/// A variable in a query
21///
22/// The name is interned behind an `Arc<str>` so that cloning a `Var` — which
23/// happens once per joined row in `Binding::merge`/`extend`/`project` and per
24/// hash-join key extraction — is a refcount bump rather than a fresh string
25/// allocation. Equality and hashing still compare the underlying `str`, so the
26/// observable semantics are identical to an owned `String`.
27#[derive(Debug, Clone, PartialEq, Eq, Hash)]
28pub struct Var {
29    name: Arc<str>,
30}
31
32impl Var {
33    /// Create a new variable
34    pub fn new(name: &str) -> Self {
35        Self {
36            name: Arc::from(name),
37        }
38    }
39
40    /// Get variable name
41    pub fn name(&self) -> &str {
42        &self.name
43    }
44
45    /// Check if this is an anonymous variable
46    pub fn is_anonymous(&self) -> bool {
47        self.name.starts_with('_')
48    }
49}
50
51impl fmt::Display for Var {
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        write!(f, "?{}", self.name)
54    }
55}
56
57impl From<&str> for Var {
58    fn from(s: &str) -> Self {
59        // Strip leading ? if present
60        let name = s.strip_prefix('?').unwrap_or(s);
61        Self::new(name)
62    }
63}
64
65/// A value that can be bound to a variable
66#[derive(Debug, Clone)]
67pub enum Value {
68    /// Node/vertex ID
69    Node(String),
70    /// Edge ID
71    Edge(String),
72    /// Literal string
73    String(String),
74    /// Integer
75    Integer(i64),
76    /// Float
77    Float(f64),
78    /// Boolean
79    Boolean(bool),
80    /// URI/IRI
81    Uri(String),
82    /// Null/unbound
83    Null,
84}
85
86impl Value {
87    /// Get as string
88    pub fn as_string(&self) -> Option<&str> {
89        match self {
90            Value::String(s) | Value::Node(s) | Value::Edge(s) | Value::Uri(s) => Some(s),
91            _ => None,
92        }
93    }
94
95    /// Get as i64
96    pub fn as_integer(&self) -> Option<i64> {
97        match self {
98            Value::Integer(i) => Some(*i),
99            _ => None,
100        }
101    }
102
103    /// Get as f64
104    pub fn as_float(&self) -> Option<f64> {
105        match self {
106            Value::Float(f) => Some(*f),
107            Value::Integer(i) => Some(*i as f64),
108            _ => None,
109        }
110    }
111
112    /// Check if null
113    pub fn is_null(&self) -> bool {
114        matches!(self, Value::Null)
115    }
116
117    /// Convert to JSON
118    pub fn to_json(&self) -> JsonValue {
119        match self {
120            Value::Node(id) => json!({ "type": "node", "id": id }),
121            Value::Edge(id) => json!({ "type": "edge", "id": id }),
122            Value::String(s) => JsonValue::String(s.clone()),
123            Value::Integer(i) => json!(i),
124            Value::Float(f) => json!(f),
125            Value::Boolean(b) => JsonValue::Bool(*b),
126            Value::Uri(uri) => json!({ "type": "uri", "value": uri }),
127            Value::Null => JsonValue::Null,
128        }
129    }
130}
131
132impl PartialEq for Value {
133    fn eq(&self, other: &Self) -> bool {
134        match (self, other) {
135            (Value::Node(a), Value::Node(b)) => a == b,
136            (Value::Edge(a), Value::Edge(b)) => a == b,
137            (Value::String(a), Value::String(b)) => a == b,
138            (Value::Integer(a), Value::Integer(b)) => a == b,
139            (Value::Float(a), Value::Float(b)) => {
140                (a - b).abs() < f64::EPSILON || (a.is_nan() && b.is_nan())
141            }
142            (Value::Boolean(a), Value::Boolean(b)) => a == b,
143            (Value::Uri(a), Value::Uri(b)) => a == b,
144            (Value::Null, Value::Null) => true,
145            _ => false,
146        }
147    }
148}
149
150impl Eq for Value {}
151
152impl Hash for Value {
153    fn hash<H: Hasher>(&self, state: &mut H) {
154        match self {
155            Value::Node(s) => {
156                0u8.hash(state);
157                s.hash(state);
158            }
159            Value::Edge(s) => {
160                1u8.hash(state);
161                s.hash(state);
162            }
163            Value::String(s) => {
164                2u8.hash(state);
165                s.hash(state);
166            }
167            Value::Integer(i) => {
168                3u8.hash(state);
169                i.hash(state);
170            }
171            Value::Boolean(b) => {
172                4u8.hash(state);
173                b.hash(state);
174            }
175            Value::Uri(s) => {
176                5u8.hash(state);
177                s.hash(state);
178            }
179            Value::Float(f) => {
180                6u8.hash(state);
181                f.to_bits().hash(state);
182            }
183            Value::Null => {
184                7u8.hash(state);
185            }
186        }
187    }
188}
189
190impl fmt::Display for Value {
191    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
192        match self {
193            Value::Node(id) => write!(f, "<node:{}>", id),
194            Value::Edge(id) => write!(f, "<edge:{}>", id),
195            Value::String(s) => write!(f, "\"{}\"", s),
196            Value::Integer(i) => write!(f, "{}", i),
197            Value::Float(fl) => write!(f, "{}", fl),
198            Value::Boolean(b) => write!(f, "{}", b),
199            Value::Uri(uri) => write!(f, "<{}>", uri),
200            Value::Null => write!(f, "NULL"),
201        }
202    }
203}
204
205/// Immutable binding from variables to values
206#[derive(Debug, Clone)]
207pub struct Binding {
208    /// Variable mappings
209    bindings: HashMap<Var, Value>,
210    /// Parent binding for scoped lookups
211    parent: Option<Arc<Binding>>,
212}
213
214impl Binding {
215    /// Create an empty binding
216    pub fn empty() -> Self {
217        Self {
218            bindings: HashMap::new(),
219            parent: None,
220        }
221    }
222
223    /// Create binding with single variable
224    pub fn one(var: Var, value: Value) -> Self {
225        let mut bindings = HashMap::new();
226        bindings.insert(var, value);
227        Self {
228            bindings,
229            parent: None,
230        }
231    }
232
233    /// Create binding with two variables
234    pub fn two(var1: Var, val1: Value, var2: Var, val2: Value) -> Self {
235        let mut bindings = HashMap::new();
236        bindings.insert(var1, val1);
237        bindings.insert(var2, val2);
238        Self {
239            bindings,
240            parent: None,
241        }
242    }
243
244    /// Create binding with parent scope
245    pub fn with_parent(self, parent: Arc<Binding>) -> Self {
246        Self {
247            bindings: self.bindings,
248            parent: Some(parent),
249        }
250    }
251
252    /// Get value for variable
253    pub fn get(&self, var: &Var) -> Option<&Value> {
254        self.bindings
255            .get(var)
256            .or_else(|| self.parent.as_ref().and_then(|p| p.get(var)))
257    }
258
259    /// Check if variable is bound
260    pub fn contains(&self, var: &Var) -> bool {
261        self.bindings.contains_key(var)
262            || self
263                .parent
264                .as_ref()
265                .map(|p| p.contains(var))
266                .unwrap_or(false)
267    }
268
269    /// Get all variables in this binding (not parent)
270    pub fn vars(&self) -> impl Iterator<Item = &Var> {
271        self.bindings.keys()
272    }
273
274    /// Get all variables including parent
275    pub fn all_vars(&self) -> Vec<&Var> {
276        let mut vars: Vec<&Var> = self.bindings.keys().collect();
277        if let Some(ref parent) = self.parent {
278            for v in parent.all_vars() {
279                if !vars.contains(&v) {
280                    vars.push(v);
281                }
282            }
283        }
284        vars
285    }
286
287    /// Number of bindings (not including parent)
288    pub fn size(&self) -> usize {
289        self.bindings.len()
290    }
291
292    /// Check if empty
293    pub fn is_empty(&self) -> bool {
294        self.bindings.is_empty() && self.parent.as_ref().map(|p| p.is_empty()).unwrap_or(true)
295    }
296
297    /// Merge two bindings (returns None if conflict)
298    pub fn merge(&self, other: &Binding) -> Option<Binding> {
299        let mut merged = self.bindings.clone();
300
301        for (var, value) in &other.bindings {
302            if let Some(existing) = self.get(var) {
303                if existing != value {
304                    return None; // Conflict
305                }
306            } else {
307                merged.insert(var.clone(), value.clone());
308            }
309        }
310
311        Some(Binding {
312            bindings: merged,
313            parent: self.parent.clone(),
314        })
315    }
316
317    /// Project to subset of variables
318    pub fn project(&self, vars: &[Var]) -> Binding {
319        let mut projected = HashMap::new();
320        for var in vars {
321            if let Some(value) = self.get(var) {
322                projected.insert(var.clone(), value.clone());
323            }
324        }
325        Binding {
326            bindings: projected,
327            parent: None,
328        }
329    }
330
331    /// Extend with additional binding
332    pub fn extend(&self, var: Var, value: Value) -> Binding {
333        let mut bindings = self.bindings.clone();
334        bindings.insert(var, value);
335        Binding {
336            bindings,
337            parent: self.parent.clone(),
338        }
339    }
340
341    /// Convert to map
342    pub fn to_map(&self) -> HashMap<String, Value> {
343        let mut map = HashMap::new();
344        if let Some(ref parent) = self.parent {
345            for (k, v) in parent.to_map() {
346                map.insert(k, v);
347            }
348        }
349        for (var, value) in &self.bindings {
350            map.insert(var.name().to_string(), value.clone());
351        }
352        map
353    }
354
355    /// Convert to JSON
356    pub fn to_json(&self) -> JsonValue {
357        let map: JsonMap<String, JsonValue> = self
358            .to_map()
359            .into_iter()
360            .map(|(k, v)| (k, v.to_json()))
361            .collect();
362        JsonValue::Object(map)
363    }
364}
365
366impl Default for Binding {
367    fn default() -> Self {
368        Self::empty()
369    }
370}
371
372impl PartialEq for Binding {
373    fn eq(&self, other: &Self) -> bool {
374        // Compare flattened bindings
375        let self_map = self.to_map();
376        let other_map = other.to_map();
377        self_map == other_map
378    }
379}
380
381impl Eq for Binding {}
382
383impl Hash for Binding {
384    fn hash<H: Hasher>(&self, state: &mut H) {
385        // Hash sorted entries for consistency
386        let mut entries: Vec<_> = self.to_map().into_iter().collect();
387        entries.sort_by(|a, b| a.0.cmp(&b.0));
388        for (k, v) in entries {
389            k.hash(state);
390            v.hash(state);
391        }
392    }
393}
394
395/// Builder for creating bindings
396pub struct BindingBuilder {
397    bindings: HashMap<Var, Value>,
398    parent: Option<Arc<Binding>>,
399}
400
401impl BindingBuilder {
402    /// Create new builder
403    pub fn new() -> Self {
404        Self {
405            bindings: HashMap::new(),
406            parent: None,
407        }
408    }
409
410    /// Create builder from existing binding
411    pub fn from(binding: &Binding) -> Self {
412        Self {
413            bindings: binding.bindings.clone(),
414            parent: binding.parent.clone(),
415        }
416    }
417
418    /// Set parent binding
419    pub fn parent(mut self, parent: Arc<Binding>) -> Self {
420        self.parent = Some(parent);
421        self
422    }
423
424    /// Add variable binding
425    pub fn add(mut self, var: Var, value: Value) -> Self {
426        self.bindings.insert(var, value);
427        self
428    }
429
430    /// Add variable binding from string name
431    pub fn add_named(self, name: &str, value: Value) -> Self {
432        self.add(Var::from(name), value)
433    }
434
435    /// Remove variable
436    pub fn remove(mut self, var: &Var) -> Self {
437        self.bindings.remove(var);
438        self
439    }
440
441    /// Build the binding
442    pub fn build(self) -> Binding {
443        Binding {
444            bindings: self.bindings,
445            parent: self.parent,
446        }
447    }
448}
449
450impl Default for BindingBuilder {
451    fn default() -> Self {
452        Self::new()
453    }
454}
455
456#[cfg(test)]
457mod tests {
458    use super::*;
459
460    #[test]
461    fn test_var() {
462        let v = Var::new("x");
463        assert_eq!(v.name(), "x");
464        assert!(!v.is_anonymous());
465
466        let anon = Var::new("_g1");
467        assert!(anon.is_anonymous());
468    }
469
470    #[test]
471    fn test_var_from_string() {
472        let v1 = Var::from("x");
473        let v2 = Var::from("?x");
474        assert_eq!(v1, v2);
475    }
476
477    #[test]
478    fn test_binding_empty() {
479        let b = Binding::empty();
480        assert!(b.is_empty());
481        assert_eq!(b.size(), 0);
482    }
483
484    #[test]
485    fn test_binding_one() {
486        let b = Binding::one(Var::new("x"), Value::Integer(42));
487        assert!(!b.is_empty());
488        assert_eq!(b.size(), 1);
489        assert!(b.contains(&Var::new("x")));
490        assert_eq!(b.get(&Var::new("x")), Some(&Value::Integer(42)));
491    }
492
493    #[test]
494    fn test_binding_parent() {
495        let parent = Arc::new(Binding::one(Var::new("x"), Value::Integer(1)));
496        let child = Binding::one(Var::new("y"), Value::Integer(2)).with_parent(parent);
497
498        // Child can see parent's bindings
499        assert!(child.contains(&Var::new("x")));
500        assert!(child.contains(&Var::new("y")));
501
502        // Direct size doesn't include parent
503        assert_eq!(child.size(), 1);
504    }
505
506    #[test]
507    fn test_binding_merge() {
508        let b1 = Binding::one(Var::new("x"), Value::Integer(1));
509        let b2 = Binding::one(Var::new("y"), Value::Integer(2));
510
511        let merged = b1.merge(&b2).unwrap();
512        assert!(merged.contains(&Var::new("x")));
513        assert!(merged.contains(&Var::new("y")));
514    }
515
516    #[test]
517    fn test_binding_merge_conflict() {
518        let b1 = Binding::one(Var::new("x"), Value::Integer(1));
519        let b2 = Binding::one(Var::new("x"), Value::Integer(2));
520
521        let merged = b1.merge(&b2);
522        assert!(merged.is_none()); // Conflict
523    }
524
525    #[test]
526    fn test_binding_merge_same_value() {
527        let b1 = Binding::one(Var::new("x"), Value::Integer(1));
528        let b2 = Binding::one(Var::new("x"), Value::Integer(1));
529
530        let merged = b1.merge(&b2).unwrap();
531        assert_eq!(merged.get(&Var::new("x")), Some(&Value::Integer(1)));
532    }
533
534    #[test]
535    fn test_binding_project() {
536        let b = Binding::two(
537            Var::new("x"),
538            Value::Integer(1),
539            Var::new("y"),
540            Value::Integer(2),
541        );
542
543        let projected = b.project(&[Var::new("x")]);
544        assert!(projected.contains(&Var::new("x")));
545        assert!(!projected.contains(&Var::new("y")));
546    }
547
548    #[test]
549    fn test_binding_extend() {
550        let b = Binding::one(Var::new("x"), Value::Integer(1));
551        let extended = b.extend(Var::new("y"), Value::Integer(2));
552
553        assert!(extended.contains(&Var::new("x")));
554        assert!(extended.contains(&Var::new("y")));
555    }
556
557    #[test]
558    fn test_binding_builder() {
559        let b = BindingBuilder::new()
560            .add_named("x", Value::Integer(1))
561            .add_named("y", Value::String("hello".to_string()))
562            .build();
563
564        assert_eq!(b.size(), 2);
565        assert_eq!(b.get(&Var::new("x")), Some(&Value::Integer(1)));
566    }
567
568    #[test]
569    fn test_value_display() {
570        assert_eq!(format!("{}", Value::Integer(42)), "42");
571        assert_eq!(
572            format!("{}", Value::String("hello".to_string())),
573            "\"hello\""
574        );
575        assert_eq!(format!("{}", Value::Null), "NULL");
576    }
577}
reddb_server/storage/query/engine/binding.rs

reddb_server/storage/query/engine/
binding.rs
