sift_query_core/query/
predicate.rs

1use crate::{ConfigError, FieldId, ParamError, ScalarValue};
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4pub struct RegisteredOperator {
5    pub operator: CustomOperator,
6    pub field_type: crate::ValueType,
7    pub input_type: crate::ValueType,
8}
9
10/// Trusted server-side SQL template for a custom operator.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
12pub struct CustomOperator {
13    name: &'static str,
14    template: &'static str,
15    arity: u8,
16    types: Option<(crate::ValueType, crate::ValueType)>,
17    exists_kind: Option<ExistsKind>,
18}
19
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
21enum ExistsKind {
22    Exists,
23    NotExists,
24}
25
26impl CustomOperator {
27    pub fn new(name: &'static str, template: &'static str, arity: u8) -> Result<Self, ConfigError> {
28        if name.is_empty()
29            || name.len() > 64
30            || template.len() > 4096
31            || !name
32                .bytes()
33                .all(|byte| byte.is_ascii_alphanumeric() || byte == b'_')
34        {
35            return Err(ConfigError::Invalid(
36                "custom operator name must be ASCII alphanumeric or underscore".to_owned(),
37            ));
38        }
39        if !template.contains("{field}")
40            || template.contains(';')
41            || template.contains("--")
42            || template.contains("/*")
43            || template.contains('$')
44            || template.contains('\0')
45        {
46            return Err(ConfigError::Invalid(
47                "custom operator template contains a forbidden token".to_owned(),
48            ));
49        }
50        validate_template_placeholders(template, arity)?;
51        Ok(Self {
52            name,
53            template,
54            arity,
55            types: None,
56            exists_kind: None,
57        })
58    }
59
60    /// Declares a trusted correlated `EXISTS (SELECT ...)` relation filter.
61    /// The complete SQL fragment is server-owned; all `{0}` values remain
62    /// bound parameters and `{field}` is replaced by the selected outer field.
63    pub fn exists(
64        name: &'static str,
65        template: &'static str,
66        arity: u8,
67    ) -> Result<Self, ConfigError> {
68        Self::exists_kind(name, template, arity, ExistsKind::Exists)
69    }
70
71    /// Declares a trusted correlated `NOT EXISTS (SELECT ...)` relation filter.
72    pub fn not_exists(
73        name: &'static str,
74        template: &'static str,
75        arity: u8,
76    ) -> Result<Self, ConfigError> {
77        Self::exists_kind(name, template, arity, ExistsKind::NotExists)
78    }
79
80    fn exists_kind(
81        name: &'static str,
82        template: &'static str,
83        arity: u8,
84        kind: ExistsKind,
85    ) -> Result<Self, ConfigError> {
86        let upper = template.trim_start().to_ascii_uppercase();
87        let prefix = match kind {
88            ExistsKind::Exists => "EXISTS (SELECT",
89            ExistsKind::NotExists => "NOT EXISTS (SELECT",
90        };
91        if !upper.starts_with(prefix) {
92            return Err(ConfigError::Invalid(
93                "exists template must start with EXISTS (SELECT ...) or NOT EXISTS (SELECT ...)"
94                    .to_owned(),
95            ));
96        }
97        let mut operator = Self::new(name, template, arity)?;
98        operator.exists_kind = Some(kind);
99        Ok(operator)
100    }
101
102    /// A trusted operator with distinct field/result and query input types.
103    pub fn typed(
104        name: &'static str,
105        template: &'static str,
106        arity: u8,
107        field_type: crate::ValueType,
108        input_type: crate::ValueType,
109    ) -> Result<Self, ConfigError> {
110        let mut operator = Self::new(name, template, arity)?;
111        operator.types = Some((field_type, input_type));
112        Ok(operator)
113    }
114
115    pub const fn types(self) -> Option<(crate::ValueType, crate::ValueType)> {
116        self.types
117    }
118
119    #[must_use]
120    pub const fn name(self) -> &'static str {
121        self.name
122    }
123
124    #[must_use]
125    pub const fn template(self) -> &'static str {
126        self.template
127    }
128
129    #[must_use]
130    pub const fn arity(self) -> u8 {
131        self.arity
132    }
133
134    #[must_use]
135    pub const fn is_exists(self) -> bool {
136        matches!(self.exists_kind, Some(ExistsKind::Exists))
137    }
138
139    #[must_use]
140    pub const fn is_not_exists(self) -> bool {
141        matches!(self.exists_kind, Some(ExistsKind::NotExists))
142    }
143}
144
145fn validate_template_placeholders(template: &str, arity: u8) -> Result<(), ConfigError> {
146    let mut referenced = vec![false; usize::from(arity)];
147    let mut remaining = template;
148    while let Some(start) = remaining.find('{') {
149        let after = &remaining[start + 1..];
150        let Some(end) = after.find('}') else {
151            return Err(ConfigError::Invalid(
152                "custom operator template has an unclosed placeholder".to_owned(),
153            ));
154        };
155        let token = &after[..end];
156        if token != "field" {
157            let index = token.parse::<usize>().map_err(|_| {
158                ConfigError::Invalid(format!("unknown custom operator placeholder {{{token}}}"))
159            })?;
160            let Some(slot) = referenced.get_mut(index) else {
161                return Err(ConfigError::Invalid(format!(
162                    "custom operator placeholder {{{index}}} exceeds arity {arity}"
163                )));
164            };
165            *slot = true;
166        }
167        remaining = &after[end + 1..];
168    }
169    if referenced.iter().any(|seen| !seen) {
170        return Err(ConfigError::Invalid(
171            "custom operator template must reference every value".to_owned(),
172        ));
173    }
174    Ok(())
175}
176
177/// M1 field operators.
178#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
179#[non_exhaustive]
180pub enum Operator {
181    Eq,
182    Ne,
183    Gt,
184    Ge,
185    Lt,
186    Le,
187    Between,
188    NotBetween,
189    InList,
190    NotIn,
191    IsNull,
192    NotNull,
193    Empty,
194    NotEmpty,
195    StartWith,
196    EndWith,
197    Contain,
198    OrLike,
199    NotLike,
200    AlwaysTrue,
201    AlwaysFalse,
202    Custom(CustomOperator),
203}
204
205impl Operator {
206    pub fn input_type(self, field_type: crate::ValueType) -> crate::ValueType {
207        match self {
208            Self::Custom(operator) => operator.types.map_or(field_type, |types| types.1),
209            _ => field_type,
210        }
211    }
212
213    pub fn accepts_field_type(self, field_type: crate::ValueType) -> bool {
214        match self {
215            Self::Custom(operator) => operator.types.is_none_or(|types| types.0 == field_type),
216            _ => true,
217        }
218    }
219    #[must_use]
220    pub const fn short_name(self) -> &'static str {
221        match self {
222            Self::Eq => "eq",
223            Self::Ne => "ne",
224            Self::Gt => "gt",
225            Self::Ge => "ge",
226            Self::Lt => "lt",
227            Self::Le => "le",
228            Self::Between => "bt",
229            Self::NotBetween => "nb",
230            Self::InList => "il",
231            Self::NotIn => "ni",
232            Self::IsNull => "nl",
233            Self::NotNull => "nn",
234            Self::Empty => "ey",
235            Self::NotEmpty => "ny",
236            Self::StartWith => "sw",
237            Self::EndWith => "ew",
238            Self::Contain => "ct",
239            Self::OrLike => "ol",
240            Self::NotLike => "nk",
241            Self::AlwaysTrue => "at",
242            Self::AlwaysFalse => "af",
243            Self::Custom(operator) => operator.name(),
244        }
245    }
246
247    pub fn parse(value: &str) -> Option<Self> {
248        match value {
249            "eq" => Some(Self::Eq),
250            "ne" => Some(Self::Ne),
251            "gt" => Some(Self::Gt),
252            "ge" => Some(Self::Ge),
253            "lt" => Some(Self::Lt),
254            "le" => Some(Self::Le),
255            "bt" => Some(Self::Between),
256            "nb" => Some(Self::NotBetween),
257            "il" => Some(Self::InList),
258            "ni" => Some(Self::NotIn),
259            "nl" => Some(Self::IsNull),
260            "nn" => Some(Self::NotNull),
261            "ey" => Some(Self::Empty),
262            "ny" => Some(Self::NotEmpty),
263            "sw" => Some(Self::StartWith),
264            "ew" => Some(Self::EndWith),
265            "ct" => Some(Self::Contain),
266            "ol" => Some(Self::OrLike),
267            "nk" => Some(Self::NotLike),
268            "at" => Some(Self::AlwaysTrue),
269            "af" => Some(Self::AlwaysFalse),
270            _ => None,
271        }
272    }
273
274    #[must_use]
275    pub const fn expected_arity(self) -> &'static str {
276        match self {
277            Self::Between | Self::NotBetween => "2",
278            Self::InList | Self::NotIn | Self::OrLike => "1..N",
279            Self::IsNull
280            | Self::NotNull
281            | Self::Empty
282            | Self::NotEmpty
283            | Self::AlwaysTrue
284            | Self::AlwaysFalse => "0",
285            Self::Custom(_) => "custom",
286            _ => "1",
287        }
288    }
289
290    #[must_use]
291    pub fn accepts_arity(self, actual: usize) -> bool {
292        match self {
293            Self::Between | Self::NotBetween => actual == 2,
294            Self::InList | Self::NotIn | Self::OrLike => actual > 0,
295            Self::IsNull
296            | Self::NotNull
297            | Self::Empty
298            | Self::NotEmpty
299            | Self::AlwaysTrue
300            | Self::AlwaysFalse => actual == 0,
301            Self::Custom(operator) => actual == usize::from(operator.arity()),
302            _ => actual == 1,
303        }
304    }
305
306    #[must_use]
307    pub const fn supports_ignore_case(self) -> bool {
308        matches!(
309            self,
310            Self::Eq
311                | Self::Ne
312                | Self::StartWith
313                | Self::EndWith
314                | Self::Contain
315                | Self::OrLike
316                | Self::NotLike
317        )
318    }
319}
320
321#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
322pub enum PredicatePhase {
323    Row,
324    Group,
325}
326
327#[derive(Debug, Clone, PartialEq)]
328pub struct Condition {
329    pub field: FieldId,
330    pub operator: Operator,
331    pub values: Vec<ScalarValue>,
332    pub ignore_case: bool,
333    pub phase: PredicatePhase,
334}
335
336#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
337#[repr(transparent)]
338pub struct NodeId(pub u16);
339
340#[derive(Debug, Clone, PartialEq)]
341pub enum PredicateNode {
342    Condition(Condition),
343    And(Vec<NodeId>),
344    Or(Vec<NodeId>),
345}
346
347/// Compact predicate storage with index-based edges.
348#[derive(Debug, Clone, Default, PartialEq)]
349pub struct PredicateArena {
350    nodes: Vec<PredicateNode>,
351    root: Option<NodeId>,
352}
353
354#[derive(Debug, Clone, Copy, PartialEq, Eq)]
355enum PhaseClass {
356    None,
357    Row,
358    Group,
359    Mixed,
360}
361
362impl PredicateArena {
363    #[must_use]
364    pub fn empty() -> Self {
365        Self::default()
366    }
367
368    pub fn from_condition(condition: Condition) -> Self {
369        let mut arena = Self::default();
370        let root = arena.push(PredicateNode::Condition(condition));
371        arena.root = Some(root);
372        arena
373    }
374
375    #[must_use]
376    pub fn nodes(&self) -> &[PredicateNode] {
377        &self.nodes
378    }
379
380    #[must_use]
381    pub const fn root(&self) -> Option<NodeId> {
382        self.root
383    }
384
385    #[must_use]
386    pub fn node(&self, id: NodeId) -> Option<&PredicateNode> {
387        self.nodes.get(usize::from(id.0))
388    }
389
390    fn push(&mut self, node: PredicateNode) -> NodeId {
391        let id = u16::try_from(self.nodes.len()).expect("predicate budget exceeds u16");
392        self.nodes.push(node);
393        NodeId(id)
394    }
395
396    pub(crate) fn combine_and(arenas: impl IntoIterator<Item = Self>) -> Self {
397        Self::combine(arenas, true)
398    }
399
400    /// Combines independent predicates with AND.
401    pub fn all(arenas: impl IntoIterator<Item = Self>) -> Self {
402        Self::combine_and(arenas)
403    }
404
405    fn combine(arenas: impl IntoIterator<Item = Self>, and: bool) -> Self {
406        let mut output = Self::default();
407        let mut roots = Vec::new();
408        for arena in arenas {
409            let offset = u16::try_from(output.nodes.len()).expect("predicate budget exceeds u16");
410            for node in arena.nodes {
411                output.nodes.push(remap_node(node, offset));
412            }
413            if let Some(root) = arena.root {
414                roots.push(NodeId(root.0 + offset));
415            }
416        }
417        output.root = match roots.len() {
418            0 => None,
419            1 => roots.first().copied(),
420            _ => Some(output.push(if and {
421                PredicateNode::And(roots)
422            } else {
423                PredicateNode::Or(roots)
424            })),
425        };
426        output
427    }
428
429    pub(crate) fn combine_or(arenas: impl IntoIterator<Item = Self>) -> Self {
430        Self::combine(arenas, false)
431    }
432
433    /// Combines independent predicates with OR.
434    pub fn any(arenas: impl IntoIterator<Item = Self>) -> Self {
435        Self::combine_or(arenas)
436    }
437
438    /// Splits an AND-separable tree into WHERE and HAVING trees.
439    pub fn partition(&self) -> Result<(Self, Self), ParamError> {
440        let Some(root) = self.root else {
441            return Ok((Self::default(), Self::default()));
442        };
443        self.validate_or_phases(root)?;
444        let mut row = Self::default();
445        let mut group = Self::default();
446        row.root = self.copy_phase(root, PredicatePhase::Row, &mut row);
447        group.root = self.copy_phase(root, PredicatePhase::Group, &mut group);
448        Ok((row, group))
449    }
450
451    /// Returns a predicate with conditions on `field` removed.
452    ///
453    /// This is used by facet self-exclusion. The remaining boolean tree keeps
454    /// its original shape; a branch that contains only the excluded field is
455    /// treated as an empty branch so the facet can evaluate the rest of the
456    /// query without accidentally broadening the server-owned predicates.
457    #[must_use]
458    pub fn without_field(&self, field: FieldId) -> Self {
459        let mut output = Self::default();
460        let Some(root) = self.root else {
461            return output;
462        };
463        output.root = self.copy_without_field(root, field, &mut output);
464        output
465    }
466
467    fn copy_without_field(&self, id: NodeId, field: FieldId, output: &mut Self) -> Option<NodeId> {
468        match self.node(id).expect("valid predicate node") {
469            PredicateNode::Condition(condition) => (condition.field != field)
470                .then(|| output.push(PredicateNode::Condition(condition.clone()))),
471            PredicateNode::And(children) => {
472                let copied = children
473                    .iter()
474                    .filter_map(|child| self.copy_without_field(*child, field, output))
475                    .collect::<Vec<_>>();
476                collapse(output, copied, true)
477            }
478            PredicateNode::Or(children) => {
479                let copied = children
480                    .iter()
481                    .filter_map(|child| self.copy_without_field(*child, field, output))
482                    .collect::<Vec<_>>();
483                collapse(output, copied, false)
484            }
485        }
486    }
487
488    fn validate_or_phases(&self, id: NodeId) -> Result<PhaseClass, ParamError> {
489        let node = self.node(id).expect("valid predicate node");
490        match node {
491            PredicateNode::Condition(condition) => Ok(match condition.phase {
492                PredicatePhase::Row => PhaseClass::Row,
493                PredicatePhase::Group => PhaseClass::Group,
494            }),
495            PredicateNode::And(children) => {
496                let mut class = PhaseClass::None;
497                for child in children {
498                    class = merge_phase(class, self.validate_or_phases(*child)?);
499                }
500                Ok(class)
501            }
502            PredicateNode::Or(children) => {
503                let mut class = PhaseClass::None;
504                for child in children {
505                    let child_class = self.validate_or_phases(*child)?;
506                    if child_class == PhaseClass::Mixed {
507                        return Err(ParamError::MixedPredicatePhase);
508                    }
509                    class = merge_phase(class, child_class);
510                    if class == PhaseClass::Mixed {
511                        return Err(ParamError::MixedPredicatePhase);
512                    }
513                }
514                Ok(class)
515            }
516        }
517    }
518
519    fn copy_phase(&self, id: NodeId, phase: PredicatePhase, output: &mut Self) -> Option<NodeId> {
520        match self.node(id).expect("valid predicate node") {
521            PredicateNode::Condition(condition) => (condition.phase == phase)
522                .then(|| output.push(PredicateNode::Condition(condition.clone()))),
523            PredicateNode::And(children) => {
524                let copied = children
525                    .iter()
526                    .filter_map(|child| self.copy_phase(*child, phase, output))
527                    .collect::<Vec<_>>();
528                collapse(output, copied, true)
529            }
530            PredicateNode::Or(children) => {
531                let copied = children
532                    .iter()
533                    .filter_map(|child| self.copy_phase(*child, phase, output))
534                    .collect::<Vec<_>>();
535                collapse(output, copied, false)
536            }
537        }
538    }
539}
540
541fn collapse(arena: &mut PredicateArena, children: Vec<NodeId>, and: bool) -> Option<NodeId> {
542    match children.len() {
543        0 => None,
544        1 => children.first().copied(),
545        _ => Some(arena.push(if and {
546            PredicateNode::And(children)
547        } else {
548            PredicateNode::Or(children)
549        })),
550    }
551}
552
553fn remap_node(node: PredicateNode, offset: u16) -> PredicateNode {
554    match node {
555        PredicateNode::Condition(condition) => PredicateNode::Condition(condition),
556        PredicateNode::And(children) => PredicateNode::And(
557            children
558                .into_iter()
559                .map(|id| NodeId(id.0 + offset))
560                .collect(),
561        ),
562        PredicateNode::Or(children) => PredicateNode::Or(
563            children
564                .into_iter()
565                .map(|id| NodeId(id.0 + offset))
566                .collect(),
567        ),
568    }
569}
570
571const fn merge_phase(left: PhaseClass, right: PhaseClass) -> PhaseClass {
572    match (left, right) {
573        (PhaseClass::None, value) | (value, PhaseClass::None) => value,
574        (PhaseClass::Row, PhaseClass::Row) => PhaseClass::Row,
575        (PhaseClass::Group, PhaseClass::Group) => PhaseClass::Group,
576        _ => PhaseClass::Mixed,
577    }
578}
sift_query_core/query/predicate.rs

sift_query_core/query/
predicate.rs
