hugr_passes/dataflow/
partial_value.rs

1use ascent::Lattice;
2use ascent::lattice::BoundedLattice;
3use hugr_core::Node;
4use hugr_core::types::{SumType, Type, TypeArg, TypeEnum, TypeRow};
5use itertools::{Itertools, zip_eq};
6use std::cmp::Ordering;
7use std::collections::HashMap;
8use std::hash::{Hash, Hasher};
9use thiserror::Error;
10
11use super::row_contains_bottom;
12
13/// Trait for an underlying domain of abstract values which can form the *elements* of a
14/// [`PartialValue`] and thus be used in dataflow analysis.
15#[deprecated(
16    note = "`hugr-passes` is deprecated. Use tket::passes instead",
17    since = "0.26.2"
18)]
19pub trait AbstractValue: Clone + std::fmt::Debug + PartialEq + Eq + Hash {
20    /// Computes the join of two values (i.e. towards `Top``), if this is representable
21    /// within the underlying domain. Return the new value, and whether this is different from
22    /// the old `self`.
23    ///
24    /// If the join is not representable, return `None` - i.e., we should use [`PartialValue::Top`].
25    ///
26    /// The default checks equality between `self` and `other` and returns `(self,false)` if
27    /// the two are identical, otherwise `None`.
28    fn try_join(self, other: Self) -> Option<(Self, bool)> {
29        (self == other).then_some((self, false))
30    }
31
32    /// Computes the meet of two values (i.e. towards `Bottom`), if this is representable
33    /// within the underlying domain. Return the new value, and whether this is different from
34    /// the old `self`.
35    /// If the meet is not representable, return `None` - i.e., we should use [`PartialValue::Bottom`].
36    ///
37    /// The default checks equality between `self` and `other` and returns `(self, false)` if
38    /// the two are identical, otherwise `None`.
39    fn try_meet(self, other: Self) -> Option<(Self, bool)> {
40        (self == other).then_some((self, false))
41    }
42}
43
44/// Represents a sum with a single/known tag, abstracted over the representation of the elements.
45/// (Identical to [Sum](hugr_core::ops::constant::Sum) except for the type abstraction.)
46#[derive(Clone, Debug, PartialEq, Eq)]
47#[deprecated(
48    note = "`hugr-passes` is deprecated. Use tket::passes instead",
49    since = "0.26.2"
50)]
51pub struct Sum<V> {
52    /// The tag index of the variant.
53    pub tag: usize,
54    /// The value of the variant.
55    ///
56    /// Sum variants are always a row of values, hence the Vec.
57    pub values: Vec<V>,
58    /// The full type of the Sum, including the other variants.
59    pub st: SumType,
60}
61
62/// The output of an [`LoadFunction`](hugr_core::ops::LoadFunction) - a "pointer"
63/// to a function at a specific node, instantiated with the provided type-args.
64#[derive(Clone, Debug, Hash, PartialEq, Eq)]
65#[deprecated(
66    note = "`hugr-passes` is deprecated. Use tket::passes instead",
67    since = "0.26.2"
68)]
69pub struct LoadedFunction<N> {
70    /// The [FuncDefn](hugr_core::ops::FuncDefn) or `FuncDecl`` that was loaded
71    pub func_node: N,
72    /// The type arguments provided when loading
73    pub args: Vec<TypeArg>,
74}
75
76/// A representation of a value of [`SumType`], that may have one or more possible tags,
77/// with a [`PartialValue`] representation of each element-value of each possible tag.
78#[derive(PartialEq, Clone, Eq)]
79#[deprecated(
80    note = "`hugr-passes` is deprecated. Use tket::passes instead",
81    since = "0.26.2"
82)]
83pub struct PartialSum<V, N = Node>(pub HashMap<usize, Vec<PartialValue<V, N>>>);
84
85impl<V, N> PartialSum<V, N> {
86    /// New instance for a single known tag.
87    /// (Multi-tag instances can be created via [`Self::try_join_mut`].)
88    pub fn new_variant(tag: usize, values: impl IntoIterator<Item = PartialValue<V, N>>) -> Self {
89        Self(HashMap::from([(tag, Vec::from_iter(values))]))
90    }
91
92    /// The number of possible variants we know about. (NOT the number
93    /// of tags possible for the value's type, whatever [`SumType`] that might be.)
94    #[must_use]
95    pub fn num_variants(&self) -> usize {
96        self.0.len()
97    }
98
99    fn assert_invariants(&self) {
100        assert_ne!(self.num_variants(), 0);
101        for pv in self.0.values().flat_map(|x| x.iter()) {
102            pv.assert_invariants();
103        }
104    }
105
106    /// Whether this sum might have the specified tag
107    #[must_use]
108    pub fn supports_tag(&self, tag: usize) -> bool {
109        self.0.contains_key(&tag)
110    }
111
112    /// Can this ever occur at runtime? See [`PartialValue::contains_bottom`]
113    #[must_use]
114    pub fn contains_bottom(&self) -> bool {
115        self.0
116            .iter()
117            .all(|(_tag, elements)| row_contains_bottom(elements))
118    }
119}
120
121impl<V: AbstractValue, N: PartialEq + PartialOrd> PartialSum<V, N> {
122    /// Joins (towards `Top`) self with another [`PartialSum`]. If successful, returns
123    /// whether `self` has changed.
124    ///
125    /// Fails (without mutation) with the conflicting tag if any common rows have different lengths.
126    pub fn try_join_mut(&mut self, other: Self) -> Result<bool, usize> {
127        for (k, v) in &other.0 {
128            if self.0.get(k).is_some_and(|row| row.len() != v.len()) {
129                return Err(*k);
130            }
131        }
132        let mut changed = false;
133
134        for (k, v) in other.0 {
135            if let Some(row) = self.0.get_mut(&k) {
136                for (lhs, rhs) in zip_eq(row.iter_mut(), v) {
137                    changed |= lhs.join_mut(rhs);
138                }
139            } else {
140                self.0.insert(k, v);
141                changed = true;
142            }
143        }
144        Ok(changed)
145    }
146
147    /// Mutates self according to lattice meet operation (towards `Bottom`). If successful,
148    /// returns whether `self` has changed.
149    ///
150    /// # Errors
151    /// Fails without mutation, either:
152    /// * `Some(tag)` if the two [`PartialSum`]s both had rows with that `tag` but of different lengths
153    /// * `None` if the two instances had no rows in common (i.e., the result is "Bottom")
154    pub fn try_meet_mut(&mut self, other: Self) -> Result<bool, Option<usize>> {
155        let mut changed = false;
156        let mut keys_to_remove = vec![];
157        for (k, v) in &self.0 {
158            match other.0.get(k) {
159                None => keys_to_remove.push(*k),
160                Some(o_v) => {
161                    if v.len() != o_v.len() {
162                        return Err(Some(*k));
163                    }
164                }
165            }
166        }
167        if keys_to_remove.len() == self.0.len() {
168            return Err(None);
169        }
170        for (k, v) in other.0 {
171            if let Some(row) = self.0.get_mut(&k) {
172                for (lhs, rhs) in zip_eq(row.iter_mut(), v) {
173                    changed |= lhs.meet_mut(rhs);
174                }
175            } else {
176                keys_to_remove.push(k);
177            }
178        }
179        for k in keys_to_remove {
180            self.0.remove(&k);
181            changed = true;
182        }
183        Ok(changed)
184    }
185}
186
187/// Trait implemented by value types into which [`PartialValue`]s can be converted,
188///
189/// so long as the PV has no [Top](PartialValue::Top), [Bottom](PartialValue::Bottom)
190/// or [`PartialSum`]s with more than one possible tag. See [`PartialSum::try_into_sum`]
191/// and [`PartialValue::try_into_concrete`].
192///
193/// `V` is the type of [`AbstractValue`] from which `Self` can (fallibly) be constructed,
194/// `N` is the type of [`HugrNode`](hugr_core::core::HugrNode) for function pointers
195#[deprecated(
196    note = "`hugr-passes` is deprecated. Use tket::passes instead",
197    since = "0.26.2"
198)]
199pub trait AsConcrete<V, N>: Sized {
200    /// Kind of error raised when creating `Self` from a value `V`, see [`Self::from_value`]
201    type ValErr: std::error::Error;
202    /// Kind of error that may be raised when creating `Self` from a [Sum] of `Self`s,
203    /// see [`Self::from_sum`]
204    type SumErr: std::error::Error;
205
206    /// Convert an abstract value into concrete
207    fn from_value(val: V) -> Result<Self, Self::ValErr>;
208
209    /// Convert a sum (of concrete values, already recursively converted) into concrete
210    fn from_sum(sum: Sum<Self>) -> Result<Self, Self::SumErr>;
211
212    /// Convert a function pointer into a concrete value
213    fn from_func(func: LoadedFunction<N>) -> Result<Self, LoadedFunction<N>>;
214}
215
216impl<V: AbstractValue, N: std::fmt::Debug> PartialSum<V, N> {
217    /// Turns this instance into a [Sum] of some "concrete" value type `C`,
218    /// *if* this `PartialSum` has exactly one possible tag.
219    ///
220    /// # Errors
221    ///
222    /// If this `PartialSum` had multiple possible tags; or if `typ` was not a [`TypeEnum::Sum`]
223    /// supporting the single possible tag with the correct number of elements and no row variables;
224    /// or if converting a child element failed via [`PartialValue::try_into_concrete`].
225    #[expect(clippy::type_complexity)] // Since C is a parameter, can't declare type aliases
226    pub fn try_into_sum<C: AsConcrete<V, N>>(
227        self,
228        typ: &Type,
229    ) -> Result<Sum<C>, ExtractValueError<V, N, C::ValErr, C::SumErr>> {
230        if self.0.len() != 1 {
231            return Err(ExtractValueError::MultipleVariants(self));
232        }
233        let (tag, v) = self.0.into_iter().exactly_one().unwrap();
234        if let TypeEnum::Sum(st) = typ.as_type_enum()
235            && let Some(r) = st.get_variant(tag)
236            && let Ok(r) = TypeRow::try_from(r.clone())
237            && v.len() == r.len()
238        {
239            return Ok(Sum {
240                tag,
241                values: zip_eq(v, r.iter())
242                    .map(|(v, t)| v.try_into_concrete(t))
243                    .collect::<Result<Vec<_>, _>>()?,
244                st: st.clone(),
245            });
246        }
247        Err(ExtractValueError::BadSumType {
248            typ: typ.clone(),
249            tag,
250            num_elements: v.len(),
251        })
252    }
253}
254
255/// An error converting a [`PartialValue`] or [`PartialSum`] into a concrete value type
256/// via [`PartialValue::try_into_concrete`] or [`PartialSum::try_into_sum`]
257#[derive(Clone, Debug, PartialEq, Eq, Error)]
258#[deprecated(
259    note = "`hugr-passes` is deprecated. Use tket::passes instead",
260    since = "0.26.2"
261)]
262pub enum ExtractValueError<V, N, VE, SE> {
263    #[error("PartialSum value had multiple possible tags: {0}")]
264    MultipleVariants(PartialSum<V, N>),
265    #[error("Value contained `Bottom`")]
266    ValueIsBottom,
267    #[error("Value contained `Top`")]
268    ValueIsTop,
269    #[error("Could not convert element from abstract value into concrete: {0}")]
270    CouldNotConvert(V, #[source] VE),
271    #[error("Could not build Sum from concrete element values")]
272    CouldNotBuildSum(#[source] SE),
273    #[error("Could not convert into concrete function pointer {0}")]
274    CouldNotLoadFunction(LoadedFunction<N>),
275    #[error("Expected a SumType with tag {tag} having {num_elements} elements, found {typ}")]
276    BadSumType {
277        typ: Type,
278        tag: usize,
279        num_elements: usize,
280    },
281}
282
283impl<V: Clone, N: Clone> PartialSum<V, N> {
284    /// If this Sum might have the specified `tag`, get the elements inside that tag.
285    #[must_use]
286    pub fn variant_values(&self, variant: usize) -> Option<Vec<PartialValue<V, N>>> {
287        self.0.get(&variant).cloned()
288    }
289}
290
291impl<V: PartialEq, N: PartialEq + PartialOrd> PartialOrd for PartialSum<V, N> {
292    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
293        let max_key = self.0.keys().chain(other.0.keys()).copied().max().unwrap();
294        let (mut keys1, mut keys2) = (vec![0; max_key + 1], vec![0; max_key + 1]);
295        for k in self.0.keys() {
296            keys1[*k] = 1;
297        }
298
299        for k in other.0.keys() {
300            keys2[*k] = 1;
301        }
302
303        Some(match keys1.cmp(&keys2) {
304            ord @ (Ordering::Greater | Ordering::Less) => ord,
305            Ordering::Equal => {
306                for (k, lhs) in &self.0 {
307                    let Some(rhs) = other.0.get(k) else {
308                        unreachable!()
309                    };
310                    let key_cmp = lhs.partial_cmp(rhs);
311                    if key_cmp != Some(Ordering::Equal) {
312                        return key_cmp;
313                    }
314                }
315                Ordering::Equal
316            }
317        })
318    }
319}
320
321impl<V: std::fmt::Debug, N: std::fmt::Debug> std::fmt::Debug for PartialSum<V, N> {
322    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
323        self.0.fmt(f)
324    }
325}
326
327impl<V: Hash, N: Hash> Hash for PartialSum<V, N> {
328    fn hash<H: Hasher>(&self, state: &mut H) {
329        for (k, v) in &self.0 {
330            k.hash(state);
331            v.hash(state);
332        }
333    }
334}
335
336/// Wraps some underlying representation (knowledge) of values into a lattice
337/// for use in dataflow analysis, including that an instance may be a [`PartialSum`]
338/// of values of the underlying representation
339#[derive(PartialEq, Clone, Eq, Hash, Debug)]
340#[deprecated(
341    note = "`hugr-passes` is deprecated. Use tket::passes instead",
342    since = "0.26.2"
343)]
344pub enum PartialValue<V, N = Node> {
345    /// No possibilities known (so far)
346    Bottom,
347    /// The output of an [`LoadFunction`](hugr_core::ops::LoadFunction)
348    LoadedFunction(LoadedFunction<N>),
349    /// A single value (of the underlying representation)
350    Value(V),
351    /// Sum (with at least one, perhaps several, possible tags) of underlying values
352    PartialSum(PartialSum<V, N>),
353    /// Might be more than one distinct value of the underlying type `V`
354    Top,
355}
356
357impl<V, N> From<V> for PartialValue<V, N> {
358    fn from(v: V) -> Self {
359        Self::Value(v)
360    }
361}
362
363impl<V, N> From<PartialSum<V, N>> for PartialValue<V, N> {
364    fn from(v: PartialSum<V, N>) -> Self {
365        Self::PartialSum(v)
366    }
367}
368
369impl<V, N> PartialValue<V, N> {
370    fn assert_invariants(&self) {
371        if let Self::PartialSum(ps) = self {
372            ps.assert_invariants();
373        }
374    }
375
376    /// New instance of a sum with a single known tag.
377    pub fn new_variant(tag: usize, values: impl IntoIterator<Item = Self>) -> Self {
378        PartialSum::new_variant(tag, values).into()
379    }
380
381    /// New instance of unit type (i.e. the only possible value, with no contents)
382    #[must_use]
383    pub fn new_unit() -> Self {
384        Self::new_variant(0, [])
385    }
386
387    /// New instance of self for a [`LoadFunction`](hugr_core::ops::LoadFunction)
388    pub fn new_load(func_node: N, args: impl Into<Vec<TypeArg>>) -> Self {
389        Self::LoadedFunction(LoadedFunction {
390            func_node,
391            args: args.into(),
392        })
393    }
394
395    /// Tells us whether this value might be a Sum with the specified `tag`
396    pub fn supports_tag(&self, tag: usize) -> bool {
397        match self {
398            PartialValue::Bottom | PartialValue::Value(_) | PartialValue::LoadedFunction(_) => {
399                false
400            }
401            PartialValue::PartialSum(ps) => ps.supports_tag(tag),
402            PartialValue::Top => true,
403        }
404    }
405
406    /// A value contains bottom means that it cannot occur during execution:
407    /// it may be an artefact during bootstrapping of the analysis, or else
408    /// the value depends upon a `panic` or a loop that
409    /// [never terminates](super::TailLoopTermination::NeverBreaks).
410    pub fn contains_bottom(&self) -> bool {
411        match self {
412            PartialValue::Bottom => true,
413            PartialValue::Top | PartialValue::Value(_) | PartialValue::LoadedFunction(_) => false,
414            PartialValue::PartialSum(ps) => ps.contains_bottom(),
415        }
416    }
417}
418
419impl<V: AbstractValue, N: Clone> PartialValue<V, N> {
420    /// If this value might be a Sum with the specified `tag`, get the elements inside that tag.
421    ///
422    /// # Panics
423    ///
424    /// if the value is believed, for that tag, to have a number of values other than `len`
425    pub fn variant_values(&self, tag: usize, len: usize) -> Option<Vec<PartialValue<V, N>>> {
426        let vals = match self {
427            PartialValue::Bottom | PartialValue::Value(_) | PartialValue::LoadedFunction(_) => {
428                return None;
429            }
430            PartialValue::PartialSum(ps) => ps.variant_values(tag)?,
431            PartialValue::Top => vec![PartialValue::Top; len],
432        };
433        assert_eq!(vals.len(), len);
434        Some(vals)
435    }
436}
437
438impl<V: AbstractValue, N: std::fmt::Debug> PartialValue<V, N> {
439    /// Turns this instance into some "concrete" value type `C`, *if* it is a single value,
440    /// or a [Sum](PartialValue::PartialSum) (of a single tag) convertible by
441    /// [`PartialSum::try_into_sum`].
442    ///
443    /// # Errors
444    ///
445    /// If this `PartialValue` was `Top` or `Bottom`, or was a [`PartialSum`](PartialValue::PartialSum)
446    /// that could not be converted into a [Sum] by [`PartialSum::try_into_sum`] (e.g. if `typ` is
447    /// incorrect), or if that [Sum] could not be converted into a `V2`.
448    pub fn try_into_concrete<C: AsConcrete<V, N>>(
449        self,
450        typ: &Type,
451    ) -> Result<C, ExtractValueError<V, N, C::ValErr, C::SumErr>> {
452        match self {
453            Self::Value(v) => {
454                C::from_value(v.clone()).map_err(|e| ExtractValueError::CouldNotConvert(v, e))
455            }
456            Self::LoadedFunction(lf) => {
457                C::from_func(lf).map_err(ExtractValueError::CouldNotLoadFunction)
458            }
459            Self::PartialSum(ps) => {
460                C::from_sum(ps.try_into_sum(typ)?).map_err(ExtractValueError::CouldNotBuildSum)
461            }
462            Self::Top => Err(ExtractValueError::ValueIsTop),
463            Self::Bottom => Err(ExtractValueError::ValueIsBottom),
464        }
465    }
466}
467
468impl<V: AbstractValue, N: PartialEq + PartialOrd> Lattice for PartialValue<V, N> {
469    fn join_mut(&mut self, other: Self) -> bool {
470        self.assert_invariants();
471        let mut old_self = Self::Top;
472        std::mem::swap(self, &mut old_self);
473        let (res, ch) = match (old_self, other) {
474            (old @ Self::Top, _) | (old, Self::Bottom) => (old, false),
475            (_, other @ Self::Top) | (Self::Bottom, other) => (other, true),
476            (Self::Value(h1), Self::Value(h2)) => match h1.clone().try_join(h2) {
477                Some((h3, b)) => (Self::Value(h3), b),
478                None => (Self::Top, true),
479            },
480            (Self::LoadedFunction(lf1), Self::LoadedFunction(lf2))
481                if lf1.func_node == lf2.func_node =>
482            {
483                // TODO we should also join the TypeArgs but at the moment these are ignored
484                (Self::LoadedFunction(lf1), false)
485            }
486            (Self::PartialSum(mut ps1), Self::PartialSum(ps2)) => match ps1.try_join_mut(ps2) {
487                Ok(ch) => (Self::PartialSum(ps1), ch),
488                Err(_) => (Self::Top, true),
489            },
490            _ => (Self::Top, true),
491        };
492        *self = res;
493        ch
494    }
495
496    fn meet_mut(&mut self, other: Self) -> bool {
497        self.assert_invariants();
498        let mut old_self = Self::Bottom;
499        std::mem::swap(self, &mut old_self);
500        let (res, ch) = match (old_self, other) {
501            (old @ Self::Bottom, _) | (old, Self::Top) => (old, false),
502            (_, other @ Self::Bottom) | (Self::Top, other) => (other, true),
503            (Self::Value(h1), Self::Value(h2)) => match h1.try_meet(h2) {
504                Some((h3, ch)) => (Self::Value(h3), ch),
505                None => (Self::Bottom, true),
506            },
507            (Self::LoadedFunction(lf1), Self::LoadedFunction(lf2))
508                if lf1.func_node == lf2.func_node =>
509            {
510                // TODO we should also meet the TypeArgs but at the moment these are ignored
511                (Self::LoadedFunction(lf1), false)
512            }
513            (Self::PartialSum(mut ps1), Self::PartialSum(ps2)) => match ps1.try_meet_mut(ps2) {
514                Ok(ch) => (Self::PartialSum(ps1), ch),
515                Err(_) => (Self::Bottom, true),
516            },
517            _ => (Self::Bottom, true),
518        };
519        *self = res;
520        ch
521    }
522}
523
524impl<V: AbstractValue, N: PartialEq + PartialOrd> BoundedLattice for PartialValue<V, N> {
525    fn top() -> Self {
526        Self::Top
527    }
528
529    fn bottom() -> Self {
530        Self::Bottom
531    }
532}
533
534impl<V: PartialEq, N: PartialEq + PartialOrd> PartialOrd for PartialValue<V, N> {
535    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
536        use std::cmp::Ordering;
537        match (self, other) {
538            (Self::Bottom, Self::Bottom) => Some(Ordering::Equal),
539            (Self::Top, Self::Top) => Some(Ordering::Equal),
540            (Self::Bottom, _) => Some(Ordering::Less),
541            (_, Self::Bottom) => Some(Ordering::Greater),
542            (Self::Top, _) => Some(Ordering::Greater),
543            (_, Self::Top) => Some(Ordering::Less),
544            (Self::Value(v1), Self::Value(v2)) => (v1 == v2).then_some(Ordering::Equal),
545            (Self::LoadedFunction(lf1), Self::LoadedFunction(lf2)) => {
546                (lf1 == lf2).then_some(Ordering::Equal)
547            }
548            (Self::PartialSum(ps1), Self::PartialSum(ps2)) => ps1.partial_cmp(ps2),
549            _ => None,
550        }
551    }
552}
553
554#[cfg(test)]
555mod test {
556    use std::sync::Arc;
557
558    use ascent::{Lattice, lattice::BoundedLattice};
559    use hugr_core::NodeIndex;
560    use itertools::{Itertools as _, zip_eq};
561    use prop::sample::subsequence;
562    use proptest::prelude::*;
563
564    use proptest_recurse::{StrategyExt, StrategySet};
565
566    use super::{AbstractValue, LoadedFunction, PartialSum, PartialValue};
567
568    #[derive(Debug, PartialEq, Eq, Clone)]
569    enum TestSumType {
570        Branch(Vec<Vec<Arc<TestSumType>>>),
571        LeafVal(usize), // contains a TestValue <= this usize
572        LeafPtr(usize), // contains a LoadedFunction with node <= this *usize*
573    }
574
575    #[derive(Clone, Debug, PartialEq, Eq, Hash)]
576    struct TestValue(usize);
577
578    impl AbstractValue for TestValue {}
579
580    #[derive(Clone)]
581    struct SumTypeParams {
582        depth: usize,
583        desired_size: usize,
584        expected_branch_size: usize,
585    }
586
587    impl Default for SumTypeParams {
588        fn default() -> Self {
589            Self {
590                depth: 5,
591                desired_size: 20,
592                expected_branch_size: 5,
593            }
594        }
595    }
596
597    impl TestSumType {
598        fn check_value(&self, pv: &PartialValue<TestValue>) -> bool {
599            match (self, pv) {
600                (_, PartialValue::Bottom | PartialValue::Top) => true,
601                (Self::LeafVal(max), PartialValue::Value(TestValue(val))) => val <= max,
602                (
603                    Self::LeafPtr(max),
604                    PartialValue::LoadedFunction(LoadedFunction { func_node, args }),
605                ) => args.is_empty() && func_node.index() <= *max,
606                (Self::Branch(sop), PartialValue::PartialSum(ps)) => {
607                    for (k, v) in &ps.0 {
608                        if *k >= sop.len() {
609                            return false;
610                        }
611                        let prod = &sop[*k];
612                        if prod.len() != v.len() {
613                            return false;
614                        }
615                        if !zip_eq(prod, v).all(|(lhs, rhs)| lhs.check_value(rhs)) {
616                            return false;
617                        }
618                    }
619                    true
620                }
621                _ => false,
622            }
623        }
624    }
625
626    impl Arbitrary for TestSumType {
627        type Parameters = SumTypeParams;
628        type Strategy = SBoxedStrategy<Self>;
629        fn arbitrary_with(params: Self::Parameters) -> Self::Strategy {
630            fn arb(params: SumTypeParams, set: &mut StrategySet) -> SBoxedStrategy<TestSumType> {
631                use proptest::collection::vec;
632                let leaf_strat = prop_oneof![
633                    (0..usize::MAX).prop_map(TestSumType::LeafVal),
634                    // This is the maximum value accepted by portgraph::NodeIndex::new
635                    (0..((2usize ^ 31) - 2)).prop_map(TestSumType::LeafPtr)
636                ];
637                leaf_strat.prop_mutually_recursive(
638                    params.depth as u32,
639                    params.desired_size as u32,
640                    params.expected_branch_size as u32,
641                    set,
642                    move |set| {
643                        let params2 = params.clone();
644                        vec(
645                            vec(
646                                set.get::<TestSumType, _>(move |set| arb(params2, set))
647                                    .prop_map(Arc::new),
648                                1..=params.expected_branch_size,
649                            ),
650                            1..=params.expected_branch_size,
651                        )
652                        .prop_map(TestSumType::Branch)
653                        .sboxed()
654                    },
655                )
656            }
657
658            arb(params, &mut StrategySet::default())
659        }
660    }
661
662    fn single_sum_strat(
663        tag: usize,
664        elems: Vec<Arc<TestSumType>>,
665    ) -> impl Strategy<Value = PartialSum<TestValue>> {
666        elems
667            .iter()
668            .map(Arc::as_ref)
669            .map(any_partial_value_of_type)
670            .collect::<Vec<_>>()
671            .prop_map(move |elems| PartialSum::new_variant(tag, elems))
672    }
673
674    fn partial_sum_strat(
675        variants: &[Vec<Arc<TestSumType>>],
676    ) -> impl Strategy<Value = PartialSum<TestValue>> + use<> {
677        // We have to clone the `variants` here but only as far as the Vec<Vec<Arc<_>>>
678        let tagged_variants = variants.iter().cloned().enumerate().collect::<Vec<_>>();
679        // The type annotation here (and the .boxed() enabling it) are just for documentation
680        let sum_variants_strat: BoxedStrategy<Vec<PartialSum<TestValue>>> =
681            subsequence(tagged_variants, 1..=variants.len())
682                .prop_flat_map(|selected_variants| {
683                    selected_variants
684                        .into_iter()
685                        .map(|(tag, elems)| single_sum_strat(tag, elems))
686                        .collect::<Vec<_>>()
687                })
688                .boxed();
689        sum_variants_strat.prop_map(|psums: Vec<PartialSum<TestValue>>| {
690            let mut psums = psums.into_iter();
691            let first = psums.next().unwrap();
692            psums.fold(first, |mut a, b| {
693                a.try_join_mut(b).unwrap();
694                a
695            })
696        })
697    }
698
699    fn any_partial_value_of_type(
700        ust: &TestSumType,
701    ) -> impl Strategy<Value = PartialValue<TestValue>> + use<> {
702        match ust {
703            TestSumType::LeafVal(i) => (0..=*i)
704                .prop_map(TestValue)
705                .prop_map(PartialValue::from)
706                .boxed(),
707            TestSumType::LeafPtr(i) => (0..=*i)
708                .prop_map(|i| {
709                    PartialValue::LoadedFunction(LoadedFunction {
710                        func_node: portgraph::NodeIndex::new(i).into(),
711                        args: vec![],
712                    })
713                })
714                .boxed(),
715            TestSumType::Branch(sop) => partial_sum_strat(sop).prop_map(PartialValue::from).boxed(),
716        }
717    }
718
719    fn any_partial_value_with(
720        params: <TestSumType as Arbitrary>::Parameters,
721    ) -> impl Strategy<Value = PartialValue<TestValue>> {
722        any_with::<TestSumType>(params).prop_flat_map(|t| any_partial_value_of_type(&t))
723    }
724
725    fn any_partial_value() -> impl Strategy<Value = PartialValue<TestValue>> {
726        any_partial_value_with(Default::default())
727    }
728
729    fn any_partial_values<const N: usize>() -> impl Strategy<Value = [PartialValue<TestValue>; N]> {
730        any::<TestSumType>().prop_flat_map(|ust| {
731            TryInto::<[_; N]>::try_into(
732                (0..N)
733                    .map(|_| any_partial_value_of_type(&ust))
734                    .collect_vec(),
735            )
736            .unwrap()
737        })
738    }
739
740    fn any_typed_partial_value() -> impl Strategy<Value = (TestSumType, PartialValue<TestValue>)> {
741        any::<TestSumType>()
742            .prop_flat_map(|t| any_partial_value_of_type(&t).prop_map(move |v| (t.clone(), v)))
743    }
744
745    proptest! {
746        #[test]
747        fn partial_value_type((tst, pv) in any_typed_partial_value()) {
748            prop_assert!(tst.check_value(&pv));
749        }
750
751        // todo: ValidHandle is valid
752        // todo: ValidHandle eq is an equivalence relation
753
754        // todo: PartialValue PartialOrd is transitive
755        // todo: PartialValue eq is an equivalence relation
756        #[test]
757        fn partial_value_valid(pv in any_partial_value()) {
758            pv.assert_invariants();
759        }
760
761        #[test]
762        fn bounded_lattice(v in any_partial_value()) {
763            prop_assert!(v <= PartialValue::top());
764            prop_assert!(v >= PartialValue::bottom());
765        }
766
767        #[test]
768        fn meet_join_self_noop(v1 in any_partial_value()) {
769            let mut subject = v1.clone();
770
771            assert_eq!(v1.clone(), v1.clone().join(v1.clone()));
772            assert!(!subject.join_mut(v1.clone()));
773            assert_eq!(subject, v1);
774
775            assert_eq!(v1.clone(), v1.clone().meet(v1.clone()));
776            assert!(!subject.meet_mut(v1.clone()));
777            assert_eq!(subject, v1);
778        }
779
780        #[test]
781        fn lattice([v1,v2] in any_partial_values()) {
782            let meet = v1.clone().meet(v2.clone());
783            prop_assert!(meet <= v1, "meet not less <=: {:#?}", &meet);
784            prop_assert!(meet <= v2, "meet not less <=: {:#?}", &meet);
785            prop_assert!(meet == v2.clone().meet(v1.clone()), "meet not symmetric");
786            prop_assert!(meet == meet.clone().meet(v1.clone()), "repeated meet should be a no-op");
787            prop_assert!(meet == meet.clone().meet(v2.clone()), "repeated meet should be a no-op");
788
789            let join = v1.clone().join(v2.clone());
790            prop_assert!(join >= v1, "join not >=: {:#?}", &join);
791            prop_assert!(join >= v2, "join not >=: {:#?}", &join);
792            prop_assert!(join == v2.clone().join(v1.clone()), "join not symmetric");
793            prop_assert!(join == join.clone().join(v1.clone()), "repeated join should be a no-op");
794            prop_assert!(join == join.clone().join(v2.clone()), "repeated join should be a no-op");
795        }
796
797        #[test]
798        fn lattice_associative([v1, v2, v3] in any_partial_values()) {
799            let a = v1.clone().meet(v2.clone()).meet(v3.clone());
800            let b = v1.clone().meet(v2.clone().meet(v3.clone()));
801            prop_assert!(a==b, "meet not associative");
802
803            let a = v1.clone().join(v2.clone()).join(v3.clone());
804            let b = v1.clone().join(v2.clone().join(v3.clone()));
805            prop_assert!(a==b, "join not associative");
806        }
807    }
808}
hugr_passes/dataflow/partial_value.rs

hugr_passes/dataflow/
partial_value.rs
