helm_schema_core/
predicate.rs

1use std::collections::BTreeSet;
2
3use crate::{Guard, GuardValue};
4
5/// How an inexact predicate participates in later semantic projection.
6#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
7pub enum ApproximationRole {
8    /// Ordinary control flow whose exact relation is unavailable.
9    #[default]
10    Control,
11    /// A sound subset identifies when one candidate supplies an expression's
12    /// returned value.
13    OutputSelection,
14}
15
16/// Typed Boolean formula recovered from template control flow.
17#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
18pub enum Predicate {
19    /// Formula that holds for every input.
20    True,
21    /// Formula that holds for no input.
22    False,
23    /// A control condition whose exact relation could not be lowered.
24    ///
25    /// The paths remain available for diagnostics and conservative attribution, but consumers
26    /// must not turn this marker into a narrowing schema condition.
27    Approximate {
28        /// Stable description of the expression shape that could not be lowered.
29        marker: String,
30        /// Values paths mentioned by the unlowerable expression.
31        paths: BTreeSet<String>,
32        /// Whether the subset describes ordinary execution or returned-value
33        /// selection.
34        role: ApproximationRole,
35        /// A predicate that IMPLIES the real condition (a sound subset).
36        /// Usable only in POSITIVE polarity where firing less often is safe
37        /// — a fail-arm's outer condition — never through a negation, which
38        /// would invert the containment.
39        sound_subset: Option<Box<Predicate>>,
40    },
41    /// Exactly lowerable atomic guard.
42    Guard(Guard),
43    /// Logical negation of a predicate.
44    Not(Box<Predicate>),
45    /// Conjunction of every enclosed predicate.
46    And(Vec<Predicate>),
47    /// Disjunction of the enclosed predicates.
48    Or(Vec<Predicate>),
49}
50
51impl From<Guard> for Predicate {
52    fn from(guard: Guard) -> Self {
53        match guard {
54            Guard::Not { path } => Self::Not(Box::new(Self::truthy_path(path))),
55            Guard::Or { paths } => Self::Or(paths.into_iter().map(Self::truthy_path).collect()),
56            Guard::AnyOf { alternatives } => Self::Or(
57                alternatives
58                    .into_iter()
59                    .map(|alternative| Self::all(alternative.into_iter().map(Self::from).collect()))
60                    .collect(),
61            ),
62            Guard::NotTypeIs { path, schema_type } => {
63                Self::Not(Box::new(Self::Guard(Guard::TypeIs { path, schema_type })))
64            }
65            guard => Self::Guard(guard),
66        }
67    }
68}
69
70impl Predicate {
71    /// Creates an atomic truthiness predicate for a values path.
72    pub fn truthy_path(path: impl Into<String>) -> Self {
73        Self::Guard(Guard::Truthy { path: path.into() })
74    }
75
76    /// Creates the exact predicate for Sprig's `kindIs "invalid"` over a values path.
77    pub fn invalid_kind_path(path: impl Into<String>) -> Self {
78        let path = path.into();
79        Self::Or(vec![
80            Self::from(Guard::Absent { path: path.clone() }),
81            Self::from(Guard::Eq {
82                path,
83                value: GuardValue::Null,
84            }),
85        ])
86    }
87
88    /// Marks an unlowerable condition without inventing a relation between its paths.
89    pub fn approximate(marker: impl Into<String>, paths: BTreeSet<String>) -> Self {
90        Self::Approximate {
91            marker: marker.into(),
92            paths,
93            role: ApproximationRole::Control,
94            sound_subset: None,
95        }
96    }
97
98    /// Marks an unlowerable condition that still admits a bounded sound
99    /// strengthening: `guards` hold only in states where the real condition
100    /// holds too.
101    pub fn approximate_with_sound_subset(
102        marker: impl Into<String>,
103        paths: BTreeSet<String>,
104        sound_subset: Vec<Guard>,
105    ) -> Self {
106        let sound_subset = match sound_subset.as_slice() {
107            [] => None,
108            _ => Some(Box::new(Self::all(
109                sound_subset.into_iter().map(Self::from).collect(),
110            ))),
111        };
112        Self::Approximate {
113            marker: marker.into(),
114            paths,
115            role: ApproximationRole::Control,
116            sound_subset,
117        }
118    }
119
120    /// Marks an unlowerable condition with a typed predicate that implies it.
121    #[must_use]
122    pub fn approximate_with_sound_predicate(
123        marker: impl Into<String>,
124        paths: BTreeSet<String>,
125        sound_subset: Self,
126    ) -> Self {
127        let sound_subset = (!matches!(sound_subset, Self::False)
128            && !sound_subset.contains_approximation())
129        .then(|| Box::new(sound_subset.normalize_boolean()));
130        Self::Approximate {
131            marker: marker.into(),
132            paths,
133            role: ApproximationRole::Control,
134            sound_subset,
135        }
136    }
137
138    /// Marks an inexact returned-value selection with a typed predicate that
139    /// proves when the candidate supplies the result.
140    #[must_use]
141    pub fn approximate_output_selection(
142        marker: impl Into<String>,
143        paths: BTreeSet<String>,
144        sound_subset: Self,
145    ) -> Self {
146        let sound_subset = (!matches!(sound_subset, Self::False)
147            && !sound_subset.contains_approximation())
148        .then(|| Box::new(sound_subset.normalize_boolean()));
149        Self::Approximate {
150            marker: marker.into(),
151            paths,
152            role: ApproximationRole::OutputSelection,
153            sound_subset,
154        }
155    }
156
157    /// Normalizes a conjunction, collapsing empty and singleton formulas.
158    #[must_use]
159    pub fn all(predicates: Vec<Self>) -> Self {
160        match predicates.as_slice() {
161            [] => Self::True,
162            [predicate] => predicate.clone(),
163            _ => Self::And(predicates),
164        }
165    }
166
167    /// Returns the logical complement without retaining redundant double negation.
168    #[must_use]
169    pub fn negated(&self) -> Self {
170        match self {
171            Self::True => Self::False,
172            Self::False => Self::True,
173            Self::Not(inner) => inner.as_ref().clone(),
174            other => Self::Not(Box::new(other.clone())),
175        }
176    }
177
178    /// Canonicalizes an exact Boolean formula without distributive expansion.
179    ///
180    /// Opaque approximate predicates are returned unchanged. Exact formulas
181    /// use a bounded decision diagram internally and fall back to the input
182    /// formula if neither normal form stays bounded.
183    #[must_use]
184    pub fn normalize_boolean(self) -> Self {
185        crate::predicate_bdd::normalize(self)
186    }
187
188    /// Reports whether this exact Boolean formula entails `consequent`.
189    ///
190    /// Opaque approximations never prove entailment. The bounded decision
191    /// diagram may also abstain when either formula exceeds its limits.
192    #[must_use]
193    pub fn exactly_implies(&self, consequent: &Self) -> bool {
194        crate::predicate_bdd::exact_implies(self, consequent)
195    }
196
197    /// Reports whether the predicate is the constant `true` or `false` formula.
198    #[must_use]
199    pub fn is_trivial(&self) -> bool {
200        matches!(self, Self::True | Self::False)
201    }
202
203    /// Whether this predicate contains a condition that could not be lowered exactly.
204    #[must_use]
205    pub fn contains_approximation(&self) -> bool {
206        match self {
207            Self::Approximate { .. } => true,
208            Self::Not(inner) => inner.contains_approximation(),
209            Self::And(predicates) | Self::Or(predicates) => {
210                predicates.iter().any(Self::contains_approximation)
211            }
212            Self::True | Self::False | Self::Guard(_) => false,
213        }
214    }
215
216    /// Returns every values path referenced by the formula.
217    #[must_use]
218    pub fn value_paths(&self) -> BTreeSet<String> {
219        let mut paths = BTreeSet::new();
220        self.collect_value_paths(&mut paths);
221        paths
222    }
223
224    /// Expands header predicates into the context-selection facts active in their bodies.
225    pub fn with_context_predicates(self) -> Vec<Self> {
226        match self {
227            Self::True => Vec::new(),
228            Self::False => vec![Self::False],
229            Self::Approximate { .. }
230            | Self::Guard(
231                Guard::Range { .. }
232                | Guard::RangeKeyPrefix { .. }
233                | Guard::RangeKeyEquals { .. }
234                | Guard::RangeKeyMatches { .. }
235                | Guard::Absent { .. }
236                | Guard::With { .. }
237                | Guard::Default { .. }
238                | Guard::TypeIs { .. }
239                | Guard::NotTypeIs { .. }
240                | Guard::Not { .. }
241                | Guard::Or { .. }
242                | Guard::AnyOf { .. }
243                | Guard::IntGt { .. }
244                | Guard::IntLt { .. }
245                | Guard::AtMostOneMember { .. }
246                | Guard::MinMembers { .. }
247                | Guard::HasKey { .. }
248                | Guard::NotHasKey { .. }
249                | Guard::ContainsEquals { .. }
250                | Guard::ContainsMemberEquals { .. }
251                | Guard::ContainsTruthyMember { .. },
252            ) => vec![self],
253            Self::And(predicates) => predicates
254                .into_iter()
255                .flat_map(Self::with_context_predicates)
256                .collect(),
257            Self::Guard(Guard::Truthy { path }) => vec![Self::from(Guard::With { path })],
258            Self::Or(predicates) => {
259                let paths: Option<Vec<String>> = predicates
260                    .iter()
261                    .map(|predicate| match predicate {
262                        Self::Guard(Guard::Truthy { path }) => Some(path.clone()),
263                        _ => None,
264                    })
265                    .collect();
266                let Some(paths) = paths else {
267                    return vec![Self::Or(predicates)];
268                };
269                let mut out: Vec<Self> = paths
270                    .iter()
271                    .map(|path| Self::from(Guard::With { path: path.clone() }))
272                    .collect();
273                out.push(Self::Or(paths.into_iter().map(Self::truthy_path).collect()));
274                out
275            }
276            Self::Not(inner) => match inner.as_ref() {
277                Self::Guard(Guard::Truthy { path }) => vec![
278                    Self::from(Guard::With { path: path.clone() }),
279                    Self::Not(inner),
280                ],
281                _ => vec![Self::Not(inner)],
282            },
283            Self::Guard(Guard::Eq { path, value }) => vec![
284                Self::from(Guard::With { path: path.clone() }),
285                Self::from(Guard::Eq { path, value }),
286            ],
287            Self::Guard(Guard::MatchesPattern {
288                path,
289                pattern,
290                templated,
291            }) => vec![
292                Self::from(Guard::With { path: path.clone() }),
293                Self::from(Guard::MatchesPattern {
294                    path,
295                    pattern,
296                    templated,
297                }),
298            ],
299            Self::Guard(Guard::NotMatchesPattern { path, pattern }) => vec![
300                Self::from(Guard::With { path: path.clone() }),
301                Self::from(Guard::NotMatchesPattern { path, pattern }),
302            ],
303            Self::Guard(Guard::NotEq { path, value }) => vec![
304                Self::from(Guard::With { path: path.clone() }),
305                Self::from(Guard::NotEq { path, value }),
306            ],
307        }
308    }
309
310    /// Returns values paths whose branch structure permits them to be absent.
311    #[must_use]
312    pub fn conditionally_optional_paths(&self) -> BTreeSet<String> {
313        let mut paths = BTreeSet::new();
314        self.collect_conditionally_optional_paths(&mut paths);
315        paths
316    }
317
318    /// Projects this formula into the contract guard vocabulary.
319    pub fn contract_guards(&self) -> Vec<Guard> {
320        match self {
321            Self::True | Self::False | Self::Approximate { .. } => Vec::new(),
322            Self::Guard(guard) => vec![guard.clone()],
323            Self::Not(inner) => negated_contract_guards(inner),
324            Self::And(predicates) => predicates.iter().flat_map(Self::contract_guards).collect(),
325            Self::Or(predicates) => or_contract_guards(predicates),
326        }
327    }
328
329    /// Whether [`Self::contract_guards`] represents this predicate
330    /// EXACTLY: the flattened guard conjunction selects the same states.
331    /// Negations distribute by De Morgan down to negatable guard leaves;
332    /// a negation reaching a leaf the vocabulary cannot flip flattens to
333    /// NOTHING, which an `And` flatten would silently drop — a fail
334    /// conjunction missing such a conjunct negates into states the
335    /// validator never rejects, so callers keep those conjuncts as raw
336    /// predicates instead.
337    #[must_use]
338    pub fn contract_guards_are_exact(&self) -> bool {
339        match self {
340            Self::True | Self::Guard(_) => true,
341            Self::False | Self::Approximate { .. } => false,
342            Self::Not(inner) => negation_flattens_exactly(inner),
343            Self::And(predicates) | Self::Or(predicates) => {
344                predicates.iter().all(Self::contract_guards_are_exact)
345            }
346        }
347    }
348
349    fn collect_value_paths(&self, out: &mut BTreeSet<String>) {
350        match self {
351            Self::True | Self::False => {}
352            Self::Approximate { paths, .. } => out.extend(paths.iter().cloned()),
353            Self::Guard(guard) => {
354                for path in guard.value_paths() {
355                    out.insert(path.to_string());
356                }
357            }
358            Self::Not(inner) => inner.collect_value_paths(out),
359            Self::And(predicates) | Self::Or(predicates) => {
360                for predicate in predicates {
361                    predicate.collect_value_paths(out);
362                }
363            }
364        }
365    }
366
367    fn collect_conditionally_optional_paths(&self, out: &mut BTreeSet<String>) {
368        match self {
369            Self::Guard(Guard::NotEq { path, .. } | Guard::Absent { path }) => {
370                out.insert(path.clone());
371            }
372            Self::Not(inner) => match inner.as_ref() {
373                Self::Guard(Guard::Truthy { path }) => {
374                    out.insert(path.clone());
375                }
376                _ => inner.collect_conditionally_optional_paths(out),
377            },
378            Self::Or(predicates) => {
379                for predicate in predicates {
380                    out.extend(predicate.value_paths());
381                }
382            }
383            Self::And(predicates) => {
384                for predicate in predicates {
385                    predicate.collect_conditionally_optional_paths(out);
386                }
387            }
388            Self::True
389            | Self::False
390            | Self::Approximate { .. }
391            | Self::Guard(
392                Guard::Truthy { .. }
393                | Guard::Eq { .. }
394                | Guard::MatchesPattern { .. }
395                | Guard::NotMatchesPattern { .. }
396                | Guard::RangeKeyPrefix { .. }
397                | Guard::RangeKeyEquals { .. }
398                | Guard::RangeKeyMatches { .. }
399                | Guard::Range { .. }
400                | Guard::With { .. }
401                | Guard::Default { .. }
402                | Guard::TypeIs { .. }
403                | Guard::NotTypeIs { .. }
404                | Guard::Not { .. }
405                | Guard::Or { .. }
406                | Guard::AnyOf { .. }
407                | Guard::IntGt { .. }
408                | Guard::IntLt { .. }
409                | Guard::AtMostOneMember { .. }
410                | Guard::MinMembers { .. }
411                | Guard::HasKey { .. }
412                | Guard::NotHasKey { .. }
413                | Guard::ContainsEquals { .. }
414                | Guard::ContainsMemberEquals { .. }
415                | Guard::ContainsTruthyMember { .. },
416            ) => {}
417        }
418    }
419
420    /// Projects a predicate stack into a deduplicated guard conjunction.
421    #[must_use]
422    pub fn contract_guard_stack(predicates: &[Self]) -> Vec<Guard> {
423        let mut guards = Vec::new();
424        for predicate in predicates {
425            for guard in predicate.contract_guards() {
426                if !guards.contains(&guard) {
427                    guards.push(guard);
428                }
429            }
430        }
431        guards
432    }
433
434    /// Rewrites every values path carried by this formula.
435    #[must_use]
436    pub fn map_value_paths<F>(self, map: &mut F) -> Self
437    where
438        F: FnMut(&str) -> String,
439    {
440        match self {
441            Self::True => Self::True,
442            Self::False => Self::False,
443            Self::Approximate {
444                marker,
445                paths,
446                role,
447                sound_subset,
448            } => Self::Approximate {
449                marker,
450                paths: paths.into_iter().map(|path| map(&path)).collect(),
451                role,
452                sound_subset: sound_subset
453                    .map(|predicate| Box::new(predicate.map_value_paths(map))),
454            },
455            Self::Guard(guard) => Self::Guard(guard.map_value_paths(map)),
456            Self::Not(inner) => Self::Not(Box::new(inner.map_value_paths(map))),
457            Self::And(predicates) => Self::And(
458                predicates
459                    .into_iter()
460                    .map(|predicate| predicate.map_value_paths(map))
461                    .collect(),
462            ),
463            Self::Or(predicates) => Self::Or(
464                predicates
465                    .into_iter()
466                    .map(|predicate| predicate.map_value_paths(map))
467                    .collect(),
468            ),
469        }
470    }
471}
472
473/// Whether [`negated_contract_guards`] flattens `¬inner` exactly: every
474/// De Morgan leaf must be a negatable guard (`True`/`False` leaves are
475/// excluded — the guard vocabulary cannot spell a constant).
476fn negation_flattens_exactly(inner: &Predicate) -> bool {
477    match inner {
478        Predicate::Guard(
479            Guard::Truthy { .. }
480            | Guard::With { .. }
481            | Guard::Not { .. }
482            | Guard::Or { .. }
483            | Guard::Eq { .. }
484            | Guard::NotEq { .. }
485            | Guard::TypeIs { .. }
486            | Guard::NotTypeIs { .. }
487            | Guard::HasKey { .. }
488            | Guard::NotHasKey { .. },
489        ) => true,
490        Predicate::Not(inner) => inner.contract_guards_are_exact(),
491        Predicate::And(predicates) | Predicate::Or(predicates) => {
492            predicates.iter().all(negation_flattens_exactly)
493        }
494        _ => false,
495    }
496}
497
498fn negated_contract_guards(inner: &Predicate) -> Vec<Guard> {
499    match inner {
500        Predicate::Guard(Guard::Truthy { path } | Guard::With { path }) => {
501            vec![Guard::Not { path: path.clone() }]
502        }
503        Predicate::Guard(Guard::Not { path }) => vec![Guard::Truthy { path: path.clone() }],
504        Predicate::Guard(Guard::Or { paths }) => paths
505            .iter()
506            .map(|path| Guard::Not { path: path.clone() })
507            .collect(),
508        Predicate::Guard(Guard::Eq { path, value }) => vec![Guard::NotEq {
509            path: path.clone(),
510            value: value.clone(),
511        }],
512        Predicate::Guard(Guard::NotEq { path, value }) => vec![Guard::Eq {
513            path: path.clone(),
514            value: value.clone(),
515        }],
516        Predicate::Guard(Guard::TypeIs { path, schema_type }) => vec![Guard::NotTypeIs {
517            path: path.clone(),
518            schema_type: schema_type.clone(),
519        }],
520        Predicate::Guard(Guard::NotTypeIs { path, schema_type }) => vec![Guard::TypeIs {
521            path: path.clone(),
522            schema_type: schema_type.clone(),
523        }],
524        Predicate::Guard(Guard::HasKey { path, key }) => vec![Guard::NotHasKey {
525            path: path.clone(),
526            key: key.clone(),
527        }],
528        Predicate::Guard(Guard::NotHasKey { path, key }) => vec![Guard::HasKey {
529            path: path.clone(),
530            key: key.clone(),
531        }],
532        Predicate::Not(inner) => inner.contract_guards(),
533        // ¬(p₁ ∨ … ∨ pₙ) = ¬p₁ ∧ … ∧ ¬pₙ: a plain conjunction, exact only
534        // when every disjunct negates exactly (an empty flatten anywhere
535        // abstains the whole negation instead of silently dropping it).
536        Predicate::Or(predicates) => {
537            let mut guards = Vec::new();
538            for predicate in predicates {
539                let negated = negated_contract_guards(predicate);
540                if negated.is_empty() {
541                    return Vec::new();
542                }
543                guards.extend(negated);
544            }
545            guards
546        }
547        // ¬(p₁ ∧ … ∧ pₙ) = ¬p₁ ∨ … ∨ ¬pₙ: one alternative per conjunct,
548        // sharing the disjunction normalization of the positive `Or` lane.
549        Predicate::And(predicates) => {
550            let mut alternatives = Vec::new();
551            for predicate in predicates {
552                let negated = negated_contract_guards(predicate);
553                if negated.is_empty() {
554                    return Vec::new();
555                }
556                alternatives.push(negated);
557            }
558            alternatives_to_guards(alternatives)
559        }
560        _ => Vec::new(),
561    }
562}
563
564fn or_contract_guards(predicates: &[Predicate]) -> Vec<Guard> {
565    let alternatives = predicates
566        .iter()
567        .map(Predicate::contract_guards)
568        .collect::<Vec<_>>();
569
570    if alternatives.iter().any(Vec::is_empty) {
571        return Vec::new();
572    }
573    alternatives_to_guards(alternatives)
574}
575
576/// Normalize a disjunction of guard conjunctions into guard form: a single
577/// alternative collapses to its conjunction, all-truthy alternatives become
578/// the flat [`Guard::Or`], anything else the general [`Guard::AnyOf`].
579fn alternatives_to_guards(mut alternatives: Vec<Vec<Guard>>) -> Vec<Guard> {
580    for alternative in &mut alternatives {
581        alternative.sort();
582        alternative.dedup();
583    }
584    alternatives.sort();
585    alternatives.dedup();
586
587    if alternatives.len() == 1 {
588        return alternatives.pop().unwrap_or_default();
589    }
590
591    if let Some(paths) = truthy_or_paths(&alternatives) {
592        return vec![Guard::Or { paths }];
593    }
594
595    vec![Guard::AnyOf { alternatives }]
596}
597
598fn truthy_or_paths(alternatives: &[Vec<Guard>]) -> Option<Vec<String>> {
599    alternatives
600        .iter()
601        .map(|alternative| match alternative.as_slice() {
602            [Guard::Truthy { path }] => Some(path.clone()),
603            _ => None,
604        })
605        .collect()
606}
607
608#[cfg(test)]
609#[path = "tests/predicate.rs"]
610mod tests;
helm_schema_core/predicate.rs

helm_schema_core/
predicate.rs
