Skip to main content

kernel/graph/
filter.rs

1// Copyright 2026 Mark AB (markik)
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Faceted filter expression engine.
5//!
6//! Implements the canonical filter query model from:
7//! `repos/graphshell/design_docs/graphshell_docs/implementation_strategy/graph/faceted_filter_surface_spec.md §4`
8//!
9//! ## Authority contract (spec §2)
10//!
11//! - Filter truth is derived from graph-owned node/edge metadata.
12//! - Evaluation runs through reducer-owned intent paths.
13//! - Filter output is a **projection** over graph truth — it never mutates node/edge identity.
14//!
15//! ## Namespaced extension keys (spec §3)
16//!
17//! Canonical PMEST facet keys (see `FacetKey` constants) are non-namespaced.
18//! Extension facets **must** use `"namespace:name"` format. Non-namespaced
19//! extension keys are invalid and must emit a `Warn` diagnostic at evaluation
20//! time.
21
22use std::collections::HashMap;
23
24use super::Graph;
25use super::facet_projection::facet_projection_for_node;
26
27// ---------------------------------------------------------------------------
28// Facet value — the runtime type that a facet key resolves to
29// ---------------------------------------------------------------------------
30
31/// Runtime value carried by a facet key.
32///
33/// Used both as the output of [`FacetProjection`] and as the operand type
34/// matched by [`FacetOperator`].
35#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
36pub enum FacetValue {
37    /// Single scalar (string, number, or boolean encoded as string/f64/bool).
38    Scalar(FacetScalar),
39    /// Multi-valued collection (tags, edge kinds, frame memberships, …).
40    Collection(Vec<FacetScalar>),
41}
42
43#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
44pub enum FacetScalar {
45    Text(String),
46    Number(f64),
47    Bool(bool),
48}
49
50// ---------------------------------------------------------------------------
51// Canonical PMEST facet key constants (spec §3)
52// ---------------------------------------------------------------------------
53
54pub mod facet_keys {
55    // Personality
56    pub const ADDRESS_KIND: &str = "address_kind";
57    pub const DOMAIN: &str = "domain";
58    pub const TITLE: &str = "title";
59    pub const ADDRESS: &str = "address";
60
61    // Matter
62    pub const MIME_HINT: &str = "mime_hint";
63    pub const VIEWER_BINDING: &str = "viewer_binding";
64    pub const CONTENT_LENGTH: &str = "content_length";
65
66    // Energy
67    pub const EDGE_KINDS: &str = "edge_kinds";
68    pub const TRAVERSAL_COUNT: &str = "traversal_count";
69    pub const IN_DEGREE: &str = "in_degree";
70    pub const OUT_DEGREE: &str = "out_degree";
71
72    // Space
73    pub const FRAME_MEMBERSHIPS: &str = "frame_memberships";
74    pub const FRAME_AFFINITY_REGION: &str = "frame_affinity_region";
75    pub const UDC_CLASSES: &str = "udc_classes";
76    pub const SPATIAL_CLUSTER: &str = "spatial_cluster";
77
78    // Time
79    pub const CREATED_AT: &str = "created_at";
80    pub const LAST_TRAVERSAL: &str = "last_traversal";
81    pub const LIFECYCLE: &str = "lifecycle";
82
83    /// Returns true for canonical (non-namespaced) PMEST keys.
84    pub fn is_canonical(key: &str) -> bool {
85        matches!(
86            key,
87            ADDRESS_KIND
88                | DOMAIN
89                | TITLE
90                | ADDRESS
91                | MIME_HINT
92                | VIEWER_BINDING
93                | CONTENT_LENGTH
94                | EDGE_KINDS
95                | TRAVERSAL_COUNT
96                | IN_DEGREE
97                | OUT_DEGREE
98                | FRAME_MEMBERSHIPS
99                | FRAME_AFFINITY_REGION
100                | UDC_CLASSES
101                | SPATIAL_CLUSTER
102                | CREATED_AT
103                | LAST_TRAVERSAL
104                | LIFECYCLE
105        )
106    }
107
108    /// Returns true when `key` is a valid namespaced extension key (`"ns:name"`).
109    pub fn is_valid_extension(key: &str) -> bool {
110        let parts: Vec<&str> = key.splitn(2, ':').collect();
111        parts.len() == 2 && !parts[0].is_empty() && !parts[1].is_empty()
112    }
113
114    /// Returns true when a facet key is valid (canonical or correctly namespaced).
115    pub fn is_valid(key: &str) -> bool {
116        is_canonical(key) || is_valid_extension(key)
117    }
118}
119
120// ---------------------------------------------------------------------------
121// Filter query model (spec §4)
122// ---------------------------------------------------------------------------
123
124/// Composable predicate expression over node facets (spec §4.1).
125#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
126pub enum FacetExpr {
127    Predicate(FacetPredicate),
128    And(Vec<FacetExpr>),
129    Or(Vec<FacetExpr>),
130    Not(Box<FacetExpr>),
131}
132
133/// Single predicate over one facet key (spec §4.2).
134#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
135pub struct FacetPredicate {
136    /// PMEST facet key or `"namespace:name"` extension key.
137    pub facet_key: String,
138    pub operator: FacetOperator,
139    pub operand: FacetOperand,
140}
141
142/// Filter operators (spec §4.2).
143#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
144pub enum FacetOperator {
145    Eq,
146    NotEq,
147    In,
148    ContainsAny,
149    ContainsAll,
150    Range,
151    Exists,
152    NotExists,
153}
154
155/// Operand carried by a predicate.
156#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
157pub enum FacetOperand {
158    Scalar(FacetScalar),
159    Set(Vec<FacetScalar>),
160    Range { lo: FacetScalar, hi: FacetScalar },
161    None,
162}
163
164// ---------------------------------------------------------------------------
165// Filter result model (spec §6)
166// ---------------------------------------------------------------------------
167
168pub type FacetProjection = HashMap<String, FacetValue>;
169
170/// Output of filter evaluation against a graph scope.
171#[derive(Debug, Clone)]
172pub struct FilterResult {
173    /// Node keys satisfying the `FacetExpr`.
174    pub matched_nodes: Vec<super::NodeKey>,
175    /// Node keys excluded by current filters.
176    pub filtered_out_nodes: Vec<super::NodeKey>,
177    /// Per-facet bucket counts for visible scope.
178    pub facet_counts: HashMap<String, usize>,
179}
180
181// ---------------------------------------------------------------------------
182// Evaluation (spec §5.1 — runs through reducer-owned intent paths)
183// ---------------------------------------------------------------------------
184
185/// Error produced when a predicate cannot be evaluated.
186#[derive(Debug, Clone, PartialEq, Eq)]
187pub enum FilterEvalError {
188    /// Operator applied to an incompatible facet value type.
189    TypeMismatch {
190        facet_key: String,
191        operator: FacetOperator,
192        actual_value_type: &'static str,
193    },
194    /// Extension key used without the `"namespace:name"` format.
195    InvalidExtensionKey { key: String },
196    /// Facet key not found in projection (used with `Exists`/`NotExists`).
197    KeyAbsent { key: String },
198}
199
200/// Aggregated filter evaluation result plus non-fatal warnings encountered
201/// while evaluating individual node projections.
202#[derive(Debug, Clone)]
203pub struct FilterEvaluationSummary {
204    pub result: FilterResult,
205    pub warnings: Vec<FilterEvalError>,
206}
207
208impl FacetExpr {
209    /// Evaluate this expression against a node's facet projection.
210    ///
211    /// Per spec §4.2 operator invariants:
212    /// - Operator/type mismatch resolves to **no match** (returns `false`) and
213    ///   the caller should emit a `Warn` diagnostic via the diagnostics channel
214    ///   `ux:facet_filter_type_mismatch`.
215    /// - `Range` on non-ordered types is invalid (resolves to no match).
216    /// - `ContainsAny`/`ContainsAll` require collection-valued facets.
217    ///
218    /// Returns `Ok(true/false)` for normal match/no-match, or
219    /// `Err(FilterEvalError)` for structural problems (invalid key, type mismatch)
220    /// that the caller must log as a diagnostic.
221    pub fn evaluate(&self, projection: &FacetProjection) -> Result<bool, FilterEvalError> {
222        match self {
223            FacetExpr::Predicate(pred) => pred.evaluate(projection),
224            FacetExpr::And(exprs) => {
225                for e in exprs {
226                    if !e.evaluate(projection)? {
227                        return Ok(false);
228                    }
229                }
230                Ok(true)
231            }
232            FacetExpr::Or(exprs) => {
233                for e in exprs {
234                    if e.evaluate(projection)? {
235                        return Ok(true);
236                    }
237                }
238                Ok(false)
239            }
240            FacetExpr::Not(inner) => Ok(!inner.evaluate(projection)?),
241        }
242    }
243}
244
245impl FacetPredicate {
246    pub fn evaluate(&self, projection: &FacetProjection) -> Result<bool, FilterEvalError> {
247        // Validate key before evaluation
248        if !facet_keys::is_valid(&self.facet_key) {
249            return Err(FilterEvalError::InvalidExtensionKey {
250                key: self.facet_key.clone(),
251            });
252        }
253
254        match self.operator {
255            FacetOperator::Exists => return Ok(projection.contains_key(&self.facet_key)),
256            FacetOperator::NotExists => return Ok(!projection.contains_key(&self.facet_key)),
257            _ => {}
258        }
259
260        let Some(value) = projection.get(&self.facet_key) else {
261            // Key absent = no match for all other operators
262            return Ok(false);
263        };
264
265        match (&self.operator, value, &self.operand) {
266            (FacetOperator::Eq, FacetValue::Scalar(scalar), FacetOperand::Scalar(operand)) => {
267                Ok(scalar == operand)
268            }
269            (FacetOperator::NotEq, FacetValue::Scalar(scalar), FacetOperand::Scalar(operand)) => {
270                Ok(scalar != operand)
271            }
272            (FacetOperator::In, FacetValue::Scalar(scalar), FacetOperand::Set(set)) => {
273                Ok(set.contains(scalar))
274            }
275            (FacetOperator::ContainsAny, FacetValue::Collection(coll), FacetOperand::Set(set)) => {
276                Ok(set.iter().any(|operand| {
277                    coll.iter()
278                        .any(|value| collection_value_matches(&self.facet_key, value, operand))
279                }))
280            }
281            (FacetOperator::ContainsAll, FacetValue::Collection(coll), FacetOperand::Set(set)) => {
282                Ok(set.iter().all(|operand| {
283                    coll.iter()
284                        .any(|value| collection_value_matches(&self.facet_key, value, operand))
285                }))
286            }
287            (
288                FacetOperator::Range,
289                FacetValue::Scalar(FacetScalar::Number(n)),
290                FacetOperand::Range {
291                    lo: FacetScalar::Number(lo),
292                    hi: FacetScalar::Number(hi),
293                },
294            ) => Ok(n >= lo && n <= hi),
295            // Type mismatches: return Err so caller can emit Warn diagnostic
296            (op, _, _) => Err(FilterEvalError::TypeMismatch {
297                facet_key: self.facet_key.clone(),
298                operator: op.clone(),
299                actual_value_type: value_type_name(value),
300            }),
301        }
302    }
303}
304
305impl FacetExpr {
306    pub fn display_label(&self) -> String {
307        match self {
308            FacetExpr::Predicate(predicate) => predicate.display_label(),
309            FacetExpr::And(exprs) => exprs
310                .iter()
311                .map(FacetExpr::display_label)
312                .collect::<Vec<_>>()
313                .join(" AND "),
314            FacetExpr::Or(exprs) => exprs
315                .iter()
316                .map(FacetExpr::display_label)
317                .collect::<Vec<_>>()
318                .join(" OR "),
319            FacetExpr::Not(inner) => format!("NOT ({})", inner.display_label()),
320        }
321    }
322}
323
324impl FacetPredicate {
325    pub fn display_label(&self) -> String {
326        match (&self.operator, &self.operand) {
327            (FacetOperator::Exists, _) => self.facet_key.clone(),
328            (FacetOperator::NotExists, _) => format!("!{}", self.facet_key),
329            (FacetOperator::Eq, FacetOperand::Scalar(value)) => {
330                format!("{}={}", self.facet_key, facet_scalar_label(value))
331            }
332            (FacetOperator::NotEq, FacetOperand::Scalar(value)) => {
333                format!("{}!={}", self.facet_key, facet_scalar_label(value))
334            }
335            (FacetOperator::In, FacetOperand::Set(values)) => {
336                format!("{} in {}", self.facet_key, facet_set_label(values))
337            }
338            (FacetOperator::ContainsAny, FacetOperand::Set(values)) => {
339                format!("{} has any {}", self.facet_key, facet_set_label(values))
340            }
341            (FacetOperator::ContainsAll, FacetOperand::Set(values)) => {
342                format!("{} has all {}", self.facet_key, facet_set_label(values))
343            }
344            (FacetOperator::Range, FacetOperand::Range { lo, hi }) => format!(
345                "{} in [{}..{}]",
346                self.facet_key,
347                facet_scalar_label(lo),
348                facet_scalar_label(hi)
349            ),
350            _ => self.facet_key.clone(),
351        }
352    }
353}
354
355fn value_type_name(value: &FacetValue) -> &'static str {
356    match value {
357        FacetValue::Scalar(FacetScalar::Text(_)) => "text",
358        FacetValue::Scalar(FacetScalar::Number(_)) => "number",
359        FacetValue::Scalar(FacetScalar::Bool(_)) => "bool",
360        FacetValue::Collection(_) => "collection",
361    }
362}
363
364fn facet_scalar_label(value: &FacetScalar) -> String {
365    match value {
366        FacetScalar::Text(text) => text.clone(),
367        FacetScalar::Number(number) => number.to_string(),
368        FacetScalar::Bool(flag) => flag.to_string(),
369    }
370}
371
372fn facet_set_label(values: &[FacetScalar]) -> String {
373    values
374        .iter()
375        .map(facet_scalar_label)
376        .collect::<Vec<_>>()
377        .join("|")
378}
379
380fn is_collection_facet_key(key: &str) -> bool {
381    matches!(
382        key,
383        facet_keys::EDGE_KINDS | facet_keys::FRAME_MEMBERSHIPS | facet_keys::UDC_CLASSES
384    )
385}
386
387fn collection_value_matches(facet_key: &str, value: &FacetScalar, operand: &FacetScalar) -> bool {
388    match (facet_key, value, operand) {
389        (facet_keys::UDC_CLASSES, FacetScalar::Text(actual), FacetScalar::Text(expected)) => {
390            udc_operand_matches(actual, expected)
391        }
392        _ => value == operand,
393    }
394}
395
396fn udc_operand_matches(actual: &str, expected: &str) -> bool {
397    let actual = actual.trim().to_ascii_lowercase();
398    let expected = expected.trim().to_ascii_lowercase();
399    actual == expected || actual.starts_with(&expected)
400}
401
402pub fn evaluate_filter_result(graph: &Graph, expr: &FacetExpr) -> FilterEvaluationSummary {
403    let mut matched_nodes = Vec::new();
404    let mut filtered_out_nodes = Vec::new();
405    let mut facet_counts = HashMap::new();
406    let mut warnings = Vec::new();
407
408    for (key, _) in graph.nodes() {
409        let Some(projection) = facet_projection_for_node(graph, key) else {
410            filtered_out_nodes.push(key);
411            continue;
412        };
413
414        match expr.evaluate(&projection) {
415            Ok(true) => {
416                matched_nodes.push(key);
417                for facet_key in projection.keys() {
418                    *facet_counts.entry(facet_key.clone()).or_insert(0) += 1;
419                }
420            }
421            Ok(false) => filtered_out_nodes.push(key),
422            Err(error) => {
423                warnings.push(error);
424                filtered_out_nodes.push(key);
425            }
426        }
427    }
428
429    FilterEvaluationSummary {
430        result: FilterResult {
431            matched_nodes,
432            filtered_out_nodes,
433            facet_counts,
434        },
435        warnings,
436    }
437}
438
439// ---------------------------------------------------------------------------
440// Omnibar `facet:` token parser (spec §7.1)
441// ---------------------------------------------------------------------------
442
443/// Parse a minimal `facet:key=value` or `facet:key` (Exists check) token
444/// entered via the omnibar.
445///
446/// Returns `None` with no side effects on invalid input — the caller is
447/// responsible for emitting `ux:facet_filter_invalid_query` (Warn).
448///
449/// Supported syntax:
450/// - `facet:key=value`  → `Eq` or `ContainsAny` depending on facet kind
451/// - `facet:!key=value` → `NotEq` or negated `ContainsAny` depending on facet kind
452/// - `facet:key`        → `Exists` predicate
453pub fn parse_omnibar_facet_token(token: &str) -> Option<FacetExpr> {
454    let body = token.strip_prefix("facet:")?;
455    if body.is_empty() {
456        return None;
457    }
458
459    // `facet:!key=value` → NotEq / Not(ContainsAny)
460    if let Some(rest) = body.strip_prefix('!') {
461        if let Some((key, value)) = rest.split_once('=') {
462            let key = key.trim().to_string();
463            let value = value.trim().to_string();
464            if !facet_keys::is_valid(&key) || key.is_empty() || value.is_empty() {
465                return None;
466            }
467            let collection_facet = is_collection_facet_key(&key);
468            let predicate = FacetPredicate {
469                facet_key: key,
470                operator: if collection_facet {
471                    FacetOperator::ContainsAny
472                } else {
473                    FacetOperator::NotEq
474                },
475                operand: if collection_facet {
476                    FacetOperand::Set(vec![FacetScalar::Text(value)])
477                } else {
478                    FacetOperand::Scalar(FacetScalar::Text(value))
479                },
480            };
481            return if collection_facet {
482                Some(FacetExpr::Not(Box::new(FacetExpr::Predicate(predicate))))
483            } else {
484                Some(FacetExpr::Predicate(predicate))
485            };
486        }
487        return None;
488    }
489
490    // `facet:key=value` → Eq / ContainsAny
491    if let Some((key, value)) = body.split_once('=') {
492        let key = key.trim().to_string();
493        let value = value.trim().to_string();
494        if !facet_keys::is_valid(&key) || key.is_empty() || value.is_empty() {
495            return None;
496        }
497        let collection_facet = is_collection_facet_key(&key);
498        return Some(FacetExpr::Predicate(FacetPredicate {
499            facet_key: key,
500            operator: if collection_facet {
501                FacetOperator::ContainsAny
502            } else {
503                FacetOperator::Eq
504            },
505            operand: if collection_facet {
506                FacetOperand::Set(vec![FacetScalar::Text(value)])
507            } else {
508                FacetOperand::Scalar(FacetScalar::Text(value))
509            },
510        }));
511    }
512
513    // `facet:key` → Exists
514    let key = body.trim().to_string();
515    if !facet_keys::is_valid(&key) || key.is_empty() {
516        return None;
517    }
518    Some(FacetExpr::Predicate(FacetPredicate {
519        facet_key: key,
520        operator: FacetOperator::Exists,
521        operand: FacetOperand::None,
522    }))
523}