Skip to main content

kernel/graph/
filter.rs

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