helm_schema_core/
predicate.rs

1use std::collections::BTreeSet;
2
3use crate::{Guard, GuardValue, ValuesPath};
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<ValuesPath>,
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_values_path(path))),
55            Guard::Or { paths } => {
56                Self::Or(paths.into_iter().map(Self::truthy_values_path).collect())
57            }
58            Guard::AnyOf { alternatives } => Self::Or(
59                alternatives
60                    .into_iter()
61                    .map(|alternative| Self::all(alternative.into_iter().map(Self::from).collect()))
62                    .collect(),
63            ),
64            Guard::NotTypeIs { path, schema_type } => {
65                Self::Not(Box::new(Self::Guard(Guard::TypeIs { path, schema_type })))
66            }
67            guard => Self::Guard(guard),
68        }
69    }
70}
71
72impl Predicate {
73    /// Creates an atomic truthiness predicate for a values path.
74    pub fn truthy_path(path: impl Into<String>) -> Self {
75        Self::truthy_values_path(ValuesPath::parse(&path.into()))
76    }
77
78    /// Creates the exact predicate for Sprig's `kindIs "invalid"` over a values path.
79    pub fn invalid_kind_path(path: impl Into<String>) -> Self {
80        let path = ValuesPath::parse(&path.into());
81        Self::Or(vec![
82            Self::from(Guard::Absent { path: path.clone() }),
83            Self::from(Guard::Eq {
84                path,
85                value: GuardValue::Null,
86            }),
87        ])
88    }
89
90    /// Marks an unlowerable condition without inventing a relation between its paths.
91    pub fn approximate(marker: impl Into<String>, paths: BTreeSet<String>) -> Self {
92        Self::Approximate {
93            marker: marker.into(),
94            paths: paths
95                .into_iter()
96                .map(|path| ValuesPath::parse(&path))
97                .collect(),
98            role: ApproximationRole::Control,
99            sound_subset: None,
100        }
101    }
102
103    /// Marks an unlowerable condition that still admits a bounded sound
104    /// strengthening: `guards` hold only in states where the real condition
105    /// holds too.
106    pub fn approximate_with_sound_subset(
107        marker: impl Into<String>,
108        paths: BTreeSet<String>,
109        sound_subset: Vec<Guard>,
110    ) -> Self {
111        let sound_subset = match sound_subset.as_slice() {
112            [] => None,
113            _ => Some(Box::new(Self::all(
114                sound_subset.into_iter().map(Self::from).collect(),
115            ))),
116        };
117        Self::Approximate {
118            marker: marker.into(),
119            paths: paths
120                .into_iter()
121                .map(|path| ValuesPath::parse(&path))
122                .collect(),
123            role: ApproximationRole::Control,
124            sound_subset,
125        }
126    }
127
128    /// Marks an unlowerable condition with a typed predicate that implies it.
129    #[must_use]
130    pub fn approximate_with_sound_predicate(
131        marker: impl Into<String>,
132        paths: BTreeSet<String>,
133        sound_subset: Self,
134    ) -> Self {
135        let sound_subset = (!matches!(sound_subset, Self::False)
136            && !sound_subset.contains_approximation())
137        .then(|| Box::new(sound_subset.normalize_boolean()));
138        Self::Approximate {
139            marker: marker.into(),
140            paths: paths
141                .into_iter()
142                .map(|path| ValuesPath::parse(&path))
143                .collect(),
144            role: ApproximationRole::Control,
145            sound_subset,
146        }
147    }
148
149    /// Marks an inexact returned-value selection with a typed predicate that
150    /// proves when the candidate supplies the result.
151    #[must_use]
152    pub fn approximate_output_selection(
153        marker: impl Into<String>,
154        paths: BTreeSet<String>,
155        sound_subset: Self,
156    ) -> Self {
157        let sound_subset = (!matches!(sound_subset, Self::False)
158            && !sound_subset.contains_approximation())
159        .then(|| Box::new(sound_subset.normalize_boolean()));
160        Self::Approximate {
161            marker: marker.into(),
162            paths: paths
163                .into_iter()
164                .map(|path| ValuesPath::parse(&path))
165                .collect(),
166            role: ApproximationRole::OutputSelection,
167            sound_subset,
168        }
169    }
170
171    /// Normalizes a conjunction, collapsing empty and singleton formulas.
172    #[must_use]
173    pub fn all(predicates: Vec<Self>) -> Self {
174        match predicates.as_slice() {
175            [] => Self::True,
176            [predicate] => predicate.clone(),
177            _ => Self::And(predicates),
178        }
179    }
180
181    /// Returns the logical complement without retaining redundant double negation.
182    #[must_use]
183    pub fn negated(&self) -> Self {
184        match self {
185            Self::True => Self::False,
186            Self::False => Self::True,
187            Self::Not(inner) => inner.as_ref().clone(),
188            other => Self::Not(Box::new(other.clone())),
189        }
190    }
191
192    /// Canonicalizes an exact Boolean formula without distributive expansion.
193    ///
194    /// Opaque approximate predicates are returned unchanged. Exact formulas
195    /// use a bounded decision diagram internally and fall back to the input
196    /// formula if neither normal form stays bounded.
197    #[must_use]
198    pub fn normalize_boolean(self) -> Self {
199        crate::predicate_bdd::normalize(self)
200    }
201
202    /// Reports whether this exact Boolean formula entails `consequent`.
203    ///
204    /// Opaque approximations never prove entailment. The bounded decision
205    /// diagram may also abstain when either formula exceeds its limits.
206    #[must_use]
207    pub fn exactly_implies(&self, consequent: &Self) -> bool {
208        crate::predicate_bdd::exact_implies(self, consequent)
209    }
210
211    /// Reports whether the predicate is the constant `true` or `false` formula.
212    #[must_use]
213    pub fn is_trivial(&self) -> bool {
214        matches!(self, Self::True | Self::False)
215    }
216
217    /// Whether this predicate contains a condition that could not be lowered exactly.
218    #[must_use]
219    pub fn contains_approximation(&self) -> bool {
220        match self {
221            Self::Approximate { .. } => true,
222            Self::Not(inner) => inner.contains_approximation(),
223            Self::And(predicates) | Self::Or(predicates) => {
224                predicates.iter().any(Self::contains_approximation)
225            }
226            Self::True | Self::False | Self::Guard(_) => false,
227        }
228    }
229
230    /// Returns every values path referenced by the formula.
231    #[must_use]
232    pub fn value_paths(&self) -> BTreeSet<ValuesPath> {
233        let mut paths = BTreeSet::new();
234        self.collect_value_paths(&mut paths);
235        paths
236    }
237
238    /// Expands header predicates into the context-selection facts active in their bodies.
239    pub fn with_context_predicates(self) -> Vec<Self> {
240        match self {
241            Self::True => Vec::new(),
242            Self::False => vec![Self::False],
243            Self::Approximate { .. }
244            | Self::Guard(
245                Guard::Range { .. }
246                | Guard::RangeKeyPrefix { .. }
247                | Guard::RangeKeyEquals { .. }
248                | Guard::RangeKeyMatches { .. }
249                | Guard::Absent { .. }
250                | Guard::With { .. }
251                | Guard::Default { .. }
252                | Guard::TypeIs { .. }
253                | Guard::NotTypeIs { .. }
254                | Guard::Not { .. }
255                | Guard::Or { .. }
256                | Guard::AnyOf { .. }
257                | Guard::IntGt { .. }
258                | Guard::IntLt { .. }
259                | Guard::AtMostOneMember { .. }
260                | Guard::MinMembers { .. }
261                | Guard::HasKey { .. }
262                | Guard::NotHasKey { .. }
263                | Guard::ContainsEquals { .. }
264                | Guard::ContainsMemberEquals { .. }
265                | Guard::ContainsTruthyMember { .. },
266            ) => vec![self],
267            Self::And(predicates) => predicates
268                .into_iter()
269                .flat_map(Self::with_context_predicates)
270                .collect(),
271            Self::Guard(Guard::Truthy { path }) => vec![Self::from(Guard::With { path })],
272            Self::Or(predicates) => {
273                let paths: Option<Vec<ValuesPath>> = predicates
274                    .iter()
275                    .map(|predicate| match predicate {
276                        Self::Guard(Guard::Truthy { path }) => Some(path.clone()),
277                        _ => None,
278                    })
279                    .collect();
280                let Some(paths) = paths else {
281                    return vec![Self::Or(predicates)];
282                };
283                let mut out: Vec<Self> = paths
284                    .iter()
285                    .map(|path| Self::from(Guard::With { path: path.clone() }))
286                    .collect();
287                out.push(Self::Or(
288                    paths.into_iter().map(Self::truthy_values_path).collect(),
289                ));
290                out
291            }
292            Self::Not(inner) => match inner.as_ref() {
293                Self::Guard(Guard::Truthy { path }) => vec![
294                    Self::from(Guard::With { path: path.clone() }),
295                    Self::Not(inner),
296                ],
297                _ => vec![Self::Not(inner)],
298            },
299            Self::Guard(Guard::Eq { path, value }) => vec![
300                Self::from(Guard::With { path: path.clone() }),
301                Self::from(Guard::Eq { path, value }),
302            ],
303            Self::Guard(Guard::MatchesPattern {
304                path,
305                pattern,
306                templated,
307            }) => vec![
308                Self::from(Guard::With { path: path.clone() }),
309                Self::from(Guard::MatchesPattern {
310                    path,
311                    pattern,
312                    templated,
313                }),
314            ],
315            Self::Guard(Guard::NotMatchesPattern { path, pattern }) => vec![
316                Self::from(Guard::With { path: path.clone() }),
317                Self::from(Guard::NotMatchesPattern { path, pattern }),
318            ],
319            Self::Guard(Guard::NotEq { path, value }) => vec![
320                Self::from(Guard::With { path: path.clone() }),
321                Self::from(Guard::NotEq { path, value }),
322            ],
323        }
324    }
325
326    /// Returns values paths whose branch structure permits them to be absent.
327    #[must_use]
328    pub fn conditionally_optional_paths(&self) -> BTreeSet<ValuesPath> {
329        let mut paths = BTreeSet::new();
330        self.collect_conditionally_optional_paths(&mut paths);
331        paths
332    }
333
334    /// Projects this formula exactly into the contract guard vocabulary.
335    /// `None` means some predicate node has no exact guard spelling.
336    #[must_use]
337    pub fn contract_guards(&self) -> Option<Vec<Guard>> {
338        flatten_contract_guards(self, false)
339    }
340
341    fn collect_value_paths(&self, out: &mut BTreeSet<ValuesPath>) {
342        match self {
343            Self::True | Self::False => {}
344            Self::Approximate { paths, .. } => out.extend(paths.iter().cloned()),
345            Self::Guard(guard) => {
346                for path in guard.value_paths() {
347                    out.insert(path);
348                }
349            }
350            Self::Not(inner) => inner.collect_value_paths(out),
351            Self::And(predicates) | Self::Or(predicates) => {
352                for predicate in predicates {
353                    predicate.collect_value_paths(out);
354                }
355            }
356        }
357    }
358
359    fn collect_conditionally_optional_paths(&self, out: &mut BTreeSet<ValuesPath>) {
360        match self {
361            Self::Guard(Guard::NotEq { path, .. } | Guard::Absent { path }) => {
362                out.insert(path.clone());
363            }
364            Self::Not(inner) => match inner.as_ref() {
365                Self::Guard(Guard::Truthy { path }) => {
366                    out.insert(path.clone());
367                }
368                _ => inner.collect_conditionally_optional_paths(out),
369            },
370            Self::Or(predicates) => {
371                for predicate in predicates {
372                    out.extend(predicate.value_paths());
373                }
374            }
375            Self::And(predicates) => {
376                for predicate in predicates {
377                    predicate.collect_conditionally_optional_paths(out);
378                }
379            }
380            Self::True
381            | Self::False
382            | Self::Approximate { .. }
383            | Self::Guard(
384                Guard::Truthy { .. }
385                | Guard::Eq { .. }
386                | Guard::MatchesPattern { .. }
387                | Guard::NotMatchesPattern { .. }
388                | Guard::RangeKeyPrefix { .. }
389                | Guard::RangeKeyEquals { .. }
390                | Guard::RangeKeyMatches { .. }
391                | Guard::Range { .. }
392                | Guard::With { .. }
393                | Guard::Default { .. }
394                | Guard::TypeIs { .. }
395                | Guard::NotTypeIs { .. }
396                | Guard::Not { .. }
397                | Guard::Or { .. }
398                | Guard::AnyOf { .. }
399                | Guard::IntGt { .. }
400                | Guard::IntLt { .. }
401                | Guard::AtMostOneMember { .. }
402                | Guard::MinMembers { .. }
403                | Guard::HasKey { .. }
404                | Guard::NotHasKey { .. }
405                | Guard::ContainsEquals { .. }
406                | Guard::ContainsMemberEquals { .. }
407                | Guard::ContainsTruthyMember { .. },
408            ) => {}
409        }
410    }
411
412    /// Projects a predicate stack into a deduplicated guard conjunction.
413    #[must_use]
414    pub fn contract_guard_stack(predicates: &[Self]) -> Vec<Guard> {
415        let mut guards = Vec::new();
416        for predicate in predicates {
417            if let Some(projected) = predicate.contract_guards() {
418                for guard in projected {
419                    if !guards.contains(&guard) {
420                        guards.push(guard);
421                    }
422                }
423            }
424        }
425        guards
426    }
427
428    /// Rewrites every values path carried by this formula.
429    #[must_use]
430    pub fn map_value_paths<F>(self, map: &mut F) -> Self
431    where
432        F: FnMut(ValuesPath) -> ValuesPath,
433    {
434        match self {
435            Self::True => Self::True,
436            Self::False => Self::False,
437            Self::Approximate {
438                marker,
439                paths,
440                role,
441                sound_subset,
442            } => Self::Approximate {
443                marker,
444                paths: paths.into_iter().map(&mut *map).collect(),
445                role,
446                sound_subset: sound_subset
447                    .map(|predicate| Box::new(predicate.map_value_paths(map))),
448            },
449            Self::Guard(guard) => Self::Guard(guard.map_value_paths(map)),
450            Self::Not(inner) => Self::Not(Box::new(inner.map_value_paths(map))),
451            Self::And(predicates) => Self::And(
452                predicates
453                    .into_iter()
454                    .map(|predicate| predicate.map_value_paths(map))
455                    .collect(),
456            ),
457            Self::Or(predicates) => Self::Or(
458                predicates
459                    .into_iter()
460                    .map(|predicate| predicate.map_value_paths(map))
461                    .collect(),
462            ),
463        }
464    }
465
466    fn truthy_values_path(path: ValuesPath) -> Self {
467        Self::Guard(Guard::Truthy { path })
468    }
469}
470
471fn flatten_contract_guards(predicate: &Predicate, negated: bool) -> Option<Vec<Guard>> {
472    match (predicate, negated) {
473        (Predicate::True, false) => Some(Vec::new()),
474        (Predicate::True | Predicate::False | Predicate::Approximate { .. }, true)
475        | (Predicate::False | Predicate::Approximate { .. }, false) => None,
476        (Predicate::Guard(guard), false) => Some(vec![guard.clone()]),
477        (Predicate::Guard(Guard::Or { paths }), true) => Some(
478            paths
479                .iter()
480                .map(|path| Guard::Not { path: path.clone() })
481                .collect(),
482        ),
483        (Predicate::Guard(guard), true) => negated_guard(guard).map(|guard| vec![guard]),
484        (Predicate::Not(inner), polarity) => flatten_contract_guards(inner, !polarity),
485        (Predicate::And(predicates), false) | (Predicate::Or(predicates), true) => predicates
486            .iter()
487            .map(|predicate| flatten_contract_guards(predicate, negated))
488            .collect::<Option<Vec<_>>>()
489            .map(|guards| guards.into_iter().flatten().collect()),
490        (Predicate::Or(predicates), false) | (Predicate::And(predicates), true) => predicates
491            .iter()
492            .map(|predicate| flatten_contract_guards(predicate, negated))
493            .collect::<Option<Vec<_>>>()
494            .map(alternatives_to_guards),
495    }
496}
497
498fn negated_guard(guard: &Guard) -> Option<Guard> {
499    match guard {
500        Guard::Truthy { path } | Guard::With { path } => Some(Guard::Not { path: path.clone() }),
501        Guard::Not { path } => Some(Guard::Truthy { path: path.clone() }),
502        Guard::Eq { path, value } => Some(Guard::NotEq {
503            path: path.clone(),
504            value: value.clone(),
505        }),
506        Guard::NotEq { path, value } => Some(Guard::Eq {
507            path: path.clone(),
508            value: value.clone(),
509        }),
510        Guard::TypeIs { path, schema_type } => Some(Guard::NotTypeIs {
511            path: path.clone(),
512            schema_type: schema_type.clone(),
513        }),
514        Guard::NotTypeIs { path, schema_type } => Some(Guard::TypeIs {
515            path: path.clone(),
516            schema_type: schema_type.clone(),
517        }),
518        Guard::HasKey { path, key } => Some(Guard::NotHasKey {
519            path: path.clone(),
520            key: key.clone(),
521        }),
522        Guard::NotHasKey { path, key } => Some(Guard::HasKey {
523            path: path.clone(),
524            key: key.clone(),
525        }),
526        Guard::Absent { .. }
527        | Guard::MatchesPattern { .. }
528        | Guard::NotMatchesPattern { .. }
529        | Guard::RangeKeyPrefix { .. }
530        | Guard::RangeKeyEquals { .. }
531        | Guard::RangeKeyMatches { .. }
532        | Guard::Or { .. }
533        | Guard::AnyOf { .. }
534        | Guard::Range { .. }
535        | Guard::Default { .. }
536        | Guard::IntGt { .. }
537        | Guard::IntLt { .. }
538        | Guard::AtMostOneMember { .. }
539        | Guard::MinMembers { .. }
540        | Guard::ContainsEquals { .. }
541        | Guard::ContainsMemberEquals { .. }
542        | Guard::ContainsTruthyMember { .. } => None,
543    }
544}
545
546/// Normalize a disjunction of guard conjunctions into guard form: a single
547/// alternative collapses to its conjunction, all-truthy alternatives become
548/// the flat [`Guard::Or`], anything else the general [`Guard::AnyOf`].
549fn alternatives_to_guards(mut alternatives: Vec<Vec<Guard>>) -> Vec<Guard> {
550    for alternative in &mut alternatives {
551        alternative.sort();
552        alternative.dedup();
553    }
554    alternatives.sort();
555    alternatives.dedup();
556
557    if alternatives.len() == 1 {
558        return alternatives.pop().unwrap_or_default();
559    }
560
561    if let Some(paths) = truthy_or_paths(&alternatives) {
562        return vec![Guard::Or { paths }];
563    }
564
565    vec![Guard::AnyOf { alternatives }]
566}
567
568fn truthy_or_paths(alternatives: &[Vec<Guard>]) -> Option<Vec<ValuesPath>> {
569    alternatives
570        .iter()
571        .map(|alternative| match alternative.as_slice() {
572            [Guard::Truthy { path }] => Some(path.clone()),
573            _ => None,
574        })
575        .collect()
576}
577
578#[cfg(test)]
579#[path = "tests/predicate.rs"]
580mod tests;
helm_schema_core/predicate.rs

helm_schema_core/
predicate.rs
