conjure_cp_core/ast/domains/
ground.rs

1use crate::ast::domains::attrs::PartitionAttr;
2use crate::ast::domains::{MSetAttr, SequenceAttr};
3use crate::ast::pretty::pretty_vec;
4use crate::ast::{
5    AbstractLiteral, DomainOpError, FuncAttr, HasDomain, Literal, Moo, Name, RelAttr, SetAttr,
6    Typeable,
7    domains::{domain::Int, range::Range},
8    matrix,
9    records::Field,
10};
11use crate::range;
12use crate::utils::count_combinations;
13use conjure_cp_core::ast::ReturnType;
14use funcmap::FuncMap;
15use itertools::{Itertools, izip};
16use num_traits::ToPrimitive;
17use polyquine::Quine;
18use serde::{Deserialize, Serialize};
19use std::collections::{BTreeMap, BTreeSet};
20use std::fmt::{Display, Formatter};
21use std::iter::zip;
22use uniplate::Uniplate;
23
24pub(super) type FieldGround = Field<Moo<GroundDomain>>;
25
26#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Quine, Uniplate)]
27#[path_prefix(conjure_cp::ast)]
28pub enum GroundDomain {
29    /// An empty domain of a given type
30    Empty(ReturnType),
31    /// A boolean value (true / false)
32    Bool,
33    /// An integer value in the given ranges (e.g. int(1, 3..5))
34    Int(Vec<Range<Int>>),
35    /// A set of elements drawn from the inner domain
36    Set(SetAttr<Int>, Moo<GroundDomain>),
37    /// A multiset of elements drawn from the inner domain
38    MSet(MSetAttr<Int>, Moo<GroundDomain>),
39    /// An N-dimensional matrix of elements drawn from the inner domain,
40    /// and indices from the n index domains
41    Matrix(Moo<GroundDomain>, Vec<Moo<GroundDomain>>),
42    /// A tuple of N elements, each with its own domain
43    Tuple(Vec<Moo<GroundDomain>>),
44    /// A record
45    Record(Vec<FieldGround>),
46    /// A Partition
47    Partition(PartitionAttr, Moo<GroundDomain>),
48    /// A sequence of elements drawn from the inner domain
49    Sequence(SequenceAttr, Moo<GroundDomain>),
50    /// A function with a domain and codomain
51    Function(FuncAttr, Moo<GroundDomain>, Moo<GroundDomain>),
52    /// A relation as a set of tuples
53    Relation(RelAttr, Vec<Moo<GroundDomain>>),
54    /// A variant domain with its domain options (reusing field entries)
55    Variant(Vec<FieldGround>),
56}
57
58impl GroundDomain {
59    pub fn union(&self, other: &GroundDomain) -> Result<GroundDomain, DomainOpError> {
60        match (self, other) {
61            (GroundDomain::Empty(ty), dom) | (dom, GroundDomain::Empty(ty)) => {
62                if *ty == dom.return_type() {
63                    Ok(dom.clone())
64                } else {
65                    Err(DomainOpError::WrongType)
66                }
67            }
68            (GroundDomain::Bool, GroundDomain::Bool) => Ok(GroundDomain::Bool),
69            (GroundDomain::Bool, _) | (_, GroundDomain::Bool) => Err(DomainOpError::WrongType),
70            (GroundDomain::Int(r1), GroundDomain::Int(r2)) => {
71                let mut rngs = r1.clone();
72                rngs.extend(r2.clone());
73                Ok(GroundDomain::Int(Range::squeeze(&rngs)))
74            }
75            (GroundDomain::Int(_), _) | (_, GroundDomain::Int(_)) => Err(DomainOpError::WrongType),
76            (GroundDomain::Set(_, in1), GroundDomain::Set(_, in2)) => Ok(GroundDomain::Set(
77                SetAttr::default(),
78                Moo::new(in1.union(in2)?),
79            )),
80            (GroundDomain::Set(_, _), _) | (_, GroundDomain::Set(_, _)) => {
81                Err(DomainOpError::WrongType)
82            }
83            (GroundDomain::MSet(_, in1), GroundDomain::MSet(_, in2)) => Ok(GroundDomain::MSet(
84                MSetAttr::default(),
85                Moo::new(in1.union(in2)?),
86            )),
87            (GroundDomain::Matrix(in1, idx1), GroundDomain::Matrix(in2, idx2)) if idx1 == idx2 => {
88                Ok(GroundDomain::Matrix(
89                    Moo::new(in1.union(in2)?),
90                    idx1.clone(),
91                ))
92            }
93            (GroundDomain::Matrix(_, _), _) | (_, GroundDomain::Matrix(_, _)) => {
94                Err(DomainOpError::WrongType)
95            }
96            (GroundDomain::Tuple(in1s), GroundDomain::Tuple(in2s)) if in1s.len() == in2s.len() => {
97                let mut inners = Vec::new();
98                for (in1, in2) in zip(in1s, in2s) {
99                    inners.push(Moo::new(in1.union(in2)?));
100                }
101                Ok(GroundDomain::Tuple(inners))
102            }
103            (GroundDomain::Tuple(_), _) | (_, GroundDomain::Tuple(_)) => {
104                Err(DomainOpError::WrongType)
105            }
106            (GroundDomain::Record(in1s), GroundDomain::Record(in2s))
107                if in1s.len() == in2s.len() =>
108            {
109                let lhs_fields: BTreeMap<&Name, &Moo<GroundDomain>> =
110                    in1s.iter().map(|x| (&x.name, &x.value)).collect();
111                let rhs_fields: BTreeMap<&Name, &Moo<GroundDomain>> =
112                    in2s.iter().map(|x| (&x.name, &x.value)).collect();
113                let mut new_fields = Vec::with_capacity(in1s.len());
114                for (n, d) in lhs_fields {
115                    let d2 = rhs_fields.get(&n).ok_or(DomainOpError::WrongType)?;
116                    let dom = d.union(d2)?;
117                    new_fields.push(Field {
118                        name: n.clone(),
119                        value: dom.into(),
120                    });
121                }
122                Ok(GroundDomain::Record(new_fields))
123            }
124            (GroundDomain::Record(_), _) | (_, GroundDomain::Record(_)) => {
125                Err(DomainOpError::WrongType)
126            }
127            (GroundDomain::Relation(_, in1s), GroundDomain::Relation(_, in2s)) => {
128                let mut inners = Vec::new();
129                for (in1, in2) in zip(in1s, in2s) {
130                    inners.push(Moo::new(in1.union(in2)?));
131                }
132                Ok(GroundDomain::Tuple(inners))
133            }
134            (GroundDomain::Relation(..), _) | (_, GroundDomain::Relation(..)) => {
135                Err(DomainOpError::WrongType)
136            }
137            #[allow(unreachable_patterns)]
138            (GroundDomain::Sequence(_, _), _) | (_, GroundDomain::Sequence(_, _)) => {
139                todo!("union sequence domains")
140            }
141            #[allow(unreachable_patterns)]
142            (GroundDomain::Variant(_), _) | (_, GroundDomain::Variant(_)) => {
143                todo!("union variant domains")
144            }
145            #[allow(unreachable_patterns)]
146            (GroundDomain::Function(..), _) | (_, GroundDomain::Function(..)) => {
147                todo!("union function domains")
148            }
149            #[allow(unreachable_patterns)]
150            (GroundDomain::Partition(..), _) | (_, GroundDomain::Partition(..)) => {
151                todo!("union partition domains")
152            }
153        }
154    }
155
156    /// Calculates the intersection of two domains.
157    ///
158    /// # Errors
159    ///
160    ///  - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.
161    ///  - [`DomainOpError::WrongType`] if the input domains are different types, or are not integer or set domains.
162    pub fn intersect(&self, other: &GroundDomain) -> Result<GroundDomain, DomainOpError> {
163        // TODO: does not consider unbounded domains yet
164        // needs to be tested once comprehension rules are written
165
166        match (self, other) {
167            // one or more arguments is an empty int domain
168            (d @ GroundDomain::Empty(ReturnType::Int), GroundDomain::Int(_)) => Ok(d.clone()),
169            (GroundDomain::Int(_), d @ GroundDomain::Empty(ReturnType::Int)) => Ok(d.clone()),
170            (GroundDomain::Empty(ReturnType::Int), d @ GroundDomain::Empty(ReturnType::Int)) => {
171                Ok(d.clone())
172            }
173
174            // one or more arguments is an empty set(int) domain
175            (GroundDomain::Set(_, inner1), d @ GroundDomain::Empty(ReturnType::Set(inner2)))
176                if matches!(
177                    **inner1,
178                    GroundDomain::Int(_) | GroundDomain::Empty(ReturnType::Int)
179                ) && matches!(**inner2, ReturnType::Int) =>
180            {
181                Ok(d.clone())
182            }
183            (d @ GroundDomain::Empty(ReturnType::Set(inner1)), GroundDomain::Set(_, inner2))
184                if matches!(**inner1, ReturnType::Int)
185                    && matches!(
186                        **inner2,
187                        GroundDomain::Int(_) | GroundDomain::Empty(ReturnType::Int)
188                    ) =>
189            {
190                Ok(d.clone())
191            }
192            (
193                d @ GroundDomain::Empty(ReturnType::Set(inner1)),
194                GroundDomain::Empty(ReturnType::Set(inner2)),
195            ) if matches!(**inner1, ReturnType::Int) && matches!(**inner2, ReturnType::Int) => {
196                Ok(d.clone())
197            }
198
199            // both arguments are non-empy
200            (GroundDomain::Set(_, x), GroundDomain::Set(_, y)) => Ok(GroundDomain::Set(
201                SetAttr::default(),
202                Moo::new((*x).intersect(y)?),
203            )),
204
205            (GroundDomain::Int(_), GroundDomain::Int(_)) => {
206                let mut v: BTreeSet<i32> = BTreeSet::new();
207
208                let v1 = self.values_i32()?;
209                let v2 = other.values_i32()?;
210                for value1 in v1.iter() {
211                    if v2.contains(value1) && !v.contains(value1) {
212                        v.insert(*value1);
213                    }
214                }
215                Ok(GroundDomain::from_set_i32(&v))
216            }
217            (GroundDomain::Relation(_, _), GroundDomain::Relation(_, _)) => {
218                todo!("Relation union not yet supported")
219            }
220            _ => Err(DomainOpError::WrongType),
221        }
222    }
223
224    pub fn values(&self) -> Result<Box<dyn Iterator<Item = Literal>>, DomainOpError> {
225        match self {
226            GroundDomain::Empty(_) => Ok(Box::new(vec![].into_iter())),
227            GroundDomain::Bool => Ok(Box::new(
228                vec![Literal::from(false), Literal::from(true)].into_iter(),
229            )),
230            GroundDomain::Int(rngs) => {
231                let rng_iters = rngs
232                    .iter()
233                    .map(Range::iter)
234                    .collect::<Option<Vec<_>>>()
235                    .ok_or(DomainOpError::Unbounded)?;
236                Ok(Box::new(
237                    rng_iters.into_iter().flat_map(|ri| ri.map(Literal::from)),
238                ))
239            }
240            GroundDomain::Matrix(elem_dom, idx_doms) => {
241                let shape = matrix::shape_of_dom(self)?;
242                let idx_doms = idx_doms.clone();
243
244                // Collect all possible element values
245                let elem_values: Vec<Literal> = elem_dom.values()?.collect();
246
247                // Generate all possible cell assignments in lexicographic order
248                let iter = std::iter::repeat_n(elem_values, shape.size)
249                    .multi_cartesian_product()
250                    .map(move |flat_elems| {
251                        matrix::unflatten_matrix::<Literal>(&flat_elems, &idx_doms, &shape.strides)
252                    });
253
254                Ok(Box::new(iter))
255            }
256            GroundDomain::Tuple(elem_doms) => {
257                // Collect the possible values for each element
258                let elem_value_pools: Vec<Vec<Literal>> = elem_doms
259                    .iter()
260                    .map(|d| d.values().map(|it| it.collect()))
261                    .collect::<Result<_, _>>()?;
262
263                // Generate all combinations in lexicographic order
264                let iter = elem_value_pools
265                    .into_iter()
266                    .multi_cartesian_product()
267                    .map(|elems| Literal::AbstractLiteral(AbstractLiteral::Tuple(elems)));
268
269                Ok(Box::new(iter))
270            }
271            GroundDomain::Record(entries) => {
272                // Sort entries by name
273                let mut sorted: Vec<&_> = entries.iter().collect();
274                sorted.sort_by(|a, b| a.name.cmp(&b.name));
275
276                let names: Vec<_> = sorted.iter().map(|e| e.name.clone()).collect();
277                let value_pools: Vec<Vec<Literal>> = sorted
278                    .iter()
279                    .map(|e| e.value.values().map(|it| it.collect()))
280                    .collect::<Result<_, _>>()?;
281
282                // Generate all combinations in lexicographic order
283                let iter = value_pools
284                    .into_iter()
285                    .multi_cartesian_product()
286                    .map(move |vals| {
287                        let record_entries = names
288                            .iter()
289                            .cloned()
290                            .zip(vals)
291                            .map(|(name, value)| Field { name, value })
292                            .collect();
293                        Literal::AbstractLiteral(AbstractLiteral::Record(record_entries))
294                    });
295
296                Ok(Box::new(iter))
297            }
298            GroundDomain::Set(attrs, inner_dom) => {
299                let n: Int = inner_dom.len_usize()?.try_into()?;
300                let min_sz = attrs.size.low().copied().unwrap_or(0);
301                let max_sz = attrs.size.high().copied().unwrap_or(n);
302
303                let pool = inner_dom.values()?.collect_vec();
304
305                Ok(Box::new(
306                    (min_sz..=max_sz)
307                        .flat_map(move |sz| pool.clone().into_iter().combinations(sz as usize))
308                        .map(|elems| Literal::AbstractLiteral(AbstractLiteral::Set(elems))),
309                ))
310            }
311            GroundDomain::MSet(..) => todo!("Enumerating multi-set domains is not yet supported"),
312            GroundDomain::Function(..) => {
313                todo!("Enumerating function domains is not yet supported")
314            }
315            GroundDomain::Partition(..) => {
316                todo!("Enumerating partition domains is not yet supported")
317            }
318            GroundDomain::Relation(..) => {
319                todo!("Enumerating relation domains is not yet supported")
320            }
321            GroundDomain::Sequence(..) => {
322                todo!("Enumerating sequence domains is not yet supported")
323            }
324            GroundDomain::Variant(..) => {
325                todo!("Enumerating variant domains is not yet supported")
326            }
327        }
328    }
329
330    /// Gets the length of this domain.
331    ///
332    /// # Errors
333    ///
334    /// - [`DomainOpError::Unbounded`] if the input domain is of infinite size.
335    pub fn length(&self) -> Result<u64, DomainOpError> {
336        match self {
337            GroundDomain::Empty(_) => Ok(0),
338            GroundDomain::Bool => Ok(2),
339            GroundDomain::Int(ranges) => {
340                if ranges.is_empty() {
341                    return Err(DomainOpError::Unbounded);
342                }
343
344                let mut length = 0u64;
345                for range in ranges {
346                    if let Some(range_length) = range.length() {
347                        length += range_length as u64;
348                    } else {
349                        return Err(DomainOpError::Unbounded);
350                    }
351                }
352                Ok(length)
353            }
354            GroundDomain::Set(set_attr, inner_domain) => {
355                let inner_len = inner_domain.length()?;
356                let (min_sz, max_sz) = match set_attr.size {
357                    Range::Unbounded => (0, inner_len),
358                    Range::Single(n) => (n as u64, n as u64),
359                    Range::UnboundedR(n) => (n as u64, inner_len),
360                    Range::UnboundedL(n) => (0, n as u64),
361                    Range::Bounded(min, max) => (min as u64, max as u64),
362                };
363                let mut ans = 0u64;
364                for sz in min_sz..=max_sz {
365                    let c = count_combinations(inner_len, sz)?;
366                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;
367                }
368                Ok(ans)
369            }
370            GroundDomain::MSet(mset_attr, inner_domain) => {
371                let inner_len = inner_domain.length()?;
372                let (min_sz, max_sz) = match mset_attr.size {
373                    Range::Unbounded => (0, inner_len),
374                    Range::Single(n) => (n as u64, n as u64),
375                    Range::UnboundedR(n) => (n as u64, inner_len),
376                    Range::UnboundedL(n) => (0, n as u64),
377                    Range::Bounded(min, max) => (min as u64, max as u64),
378                };
379                let mut ans = 0u64;
380                for sz in min_sz..=max_sz {
381                    // need  "multichoose", ((n  k)) == (n+k-1  k)
382                    // Where n=inner_len and k=sz
383                    let c = count_combinations(inner_len + sz - 1, sz)?;
384                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;
385                }
386                Ok(ans)
387            }
388            GroundDomain::Sequence(_, _) => {
389                // If jectivity is not set, the sequence can have any permutation.
390                //
391                todo!("Length bound currently not supported");
392            }
393            GroundDomain::Tuple(domains) => {
394                let mut ans = 1u64;
395                for domain in domains {
396                    ans = ans
397                        .checked_mul(domain.length()?)
398                        .ok_or(DomainOpError::TooLarge)?;
399                }
400                Ok(ans)
401            }
402            GroundDomain::Record(entries) => {
403                // A record is just a named tuple
404                let mut ans = 1u64;
405                for entry in entries {
406                    let sz = entry.value.length()?;
407                    ans = ans.checked_mul(sz).ok_or(DomainOpError::TooLarge)?;
408                }
409                Ok(ans)
410            }
411            GroundDomain::Matrix(inner_domain, idx_domains) => {
412                let inner_sz = inner_domain.length()?;
413                let exp = idx_domains.iter().try_fold(1u32, |acc, val| {
414                    let len = val.length()? as u32;
415                    acc.checked_mul(len).ok_or(DomainOpError::TooLarge)
416                })?;
417                inner_sz.checked_pow(exp).ok_or(DomainOpError::TooLarge)
418            }
419            GroundDomain::Function(_, _, _) => {
420                todo!("Length bound of functions is not yet supported")
421            }
422            GroundDomain::Variant(entries) => {
423                let mut ans = 1u64;
424                for entry in entries {
425                    let sz = entry.value.length()?;
426                    // Only one field can be in the variant at once
427                    ans = ans.checked_add(sz).ok_or(DomainOpError::TooLarge)?;
428                }
429                Ok(ans)
430            }
431            GroundDomain::Relation(_, domains) => {
432                // Cannot currently use attributes to better infer length because of i32 u64 mismatch
433                let dom_sizes_result: Result<Vec<u64>, DomainOpError> =
434                    domains.iter().map(|x| x.length()).collect();
435                let dom_sizes = dom_sizes_result?;
436                Ok(dom_sizes.iter().product())
437            }
438            GroundDomain::Partition(_, _) => {
439                todo!("Length bound of Partitions is not yet supported")
440            }
441        }
442    }
443
444    /// Get size of this domain as a [usize]
445    pub fn len_usize(&self) -> Result<usize, DomainOpError> {
446        self.length()?
447            .try_into()
448            .map_err(|_| DomainOpError::TooLarge)
449    }
450
451    pub fn contains(&self, lit: &Literal) -> Result<bool, DomainOpError> {
452        // not adding a generic wildcard condition for all domains, so that this gives a compile
453        // error when a domain is added.
454        match self {
455            // empty domain can't contain anything
456            GroundDomain::Empty(_) => Ok(false),
457            GroundDomain::Bool => match lit {
458                Literal::Bool(_) => Ok(true),
459                _ => Ok(false),
460            },
461            GroundDomain::Int(ranges) => match lit {
462                Literal::Int(x) => {
463                    // unconstrained int domain - contains all integers
464                    if ranges.is_empty() {
465                        return Ok(true);
466                    };
467
468                    Ok(ranges.iter().any(|range| range.contains(x)))
469                }
470                _ => Ok(false),
471            },
472            GroundDomain::Set(set_attr, inner_domain) => match lit {
473                Literal::AbstractLiteral(AbstractLiteral::Set(lit_elems)) => {
474                    // check if the literal's size is allowed by the set attribute
475                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
476                    if !set_attr.size.contains(&sz) {
477                        return Ok(false);
478                    }
479
480                    for elem in lit_elems {
481                        if !inner_domain.contains(elem)? {
482                            return Ok(false);
483                        }
484                    }
485                    Ok(true)
486                }
487                _ => Ok(false),
488            },
489            GroundDomain::MSet(mset_attr, inner_domain) => match lit {
490                Literal::AbstractLiteral(AbstractLiteral::MSet(lit_elems)) => {
491                    // check if the literal's size is allowed by the mset attribute
492                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
493                    if !mset_attr.size.contains(&sz) {
494                        return Ok(false);
495                    }
496
497                    for elem in lit_elems {
498                        if !inner_domain.contains(elem)? {
499                            return Ok(false);
500                        }
501                    }
502                    Ok(true)
503                }
504                _ => Ok(false),
505            },
506            GroundDomain::Sequence(seq_attr, inner_dom) => match lit {
507                Literal::AbstractLiteral(AbstractLiteral::Sequence(elems)) => {
508                    let sz = elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
509                    if !seq_attr.size.contains(&sz) {
510                        return Ok(false);
511                    }
512
513                    for elem in elems {
514                        if !inner_dom.contains(elem)? {
515                            return Ok(false);
516                        }
517                    }
518                    Ok(true)
519                }
520                _ => Ok(false),
521            },
522            GroundDomain::Matrix(elem_domain, index_domains) => {
523                match lit {
524                    Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx_domain)) => {
525                        // Matrix literals are represented as nested 1d matrices, so the elements of
526                        // the matrix literal will be the inner dimensions of the matrix.
527
528                        let Some((current_index_domain, remaining_index_domains)) =
529                            index_domains.split_first()
530                        else {
531                            panic!("a matrix should have at least one index domain");
532                        };
533
534                        if *current_index_domain != *idx_domain {
535                            return Ok(false);
536                        };
537
538                        let next_elem_domain = if remaining_index_domains.is_empty() {
539                            // Base case - we have a 1D row. Now check if all elements in the
540                            // literal are in this row's element domain.
541                            elem_domain.as_ref().clone()
542                        } else {
543                            // Otherwise, go down a dimension (e.g. 2D matrix inside a 3D tensor)
544                            GroundDomain::Matrix(
545                                elem_domain.clone(),
546                                remaining_index_domains.to_vec(),
547                            )
548                        };
549
550                        for elem in elems {
551                            if !next_elem_domain.contains(elem)? {
552                                return Ok(false);
553                            }
554                        }
555
556                        Ok(true)
557                    }
558                    _ => Ok(false),
559                }
560            }
561            GroundDomain::Tuple(elem_domains) => {
562                match lit {
563                    Literal::AbstractLiteral(AbstractLiteral::Tuple(literal_elems)) => {
564                        if elem_domains.len() != literal_elems.len() {
565                            return Ok(false);
566                        }
567
568                        // for every element in the tuple literal, check if it is in the corresponding domain
569                        for (elem_domain, elem) in itertools::izip!(elem_domains, literal_elems) {
570                            if !elem_domain.contains(elem)? {
571                                return Ok(false);
572                            }
573                        }
574
575                        Ok(true)
576                    }
577                    _ => Ok(false),
578                }
579            }
580            GroundDomain::Record(entries) => match lit {
581                Literal::AbstractLiteral(AbstractLiteral::Record(lit_entries)) => {
582                    if entries.len() != lit_entries.len() {
583                        return Ok(false);
584                    }
585
586                    for (entry, lit_entry) in itertools::izip!(entries, lit_entries) {
587                        if entry.name != lit_entry.name
588                            || !(entry.value.contains(&lit_entry.value)?)
589                        {
590                            return Ok(false);
591                        }
592                    }
593                    Ok(true)
594                }
595                _ => Ok(false),
596            },
597            GroundDomain::Function(func_attr, domain, codomain) => match lit {
598                Literal::AbstractLiteral(AbstractLiteral::Function(lit_elems)) => {
599                    let sz = Int::try_from(lit_elems.len()).expect("Should convert");
600                    if !func_attr.size.contains(&sz) {
601                        return Ok(false);
602                    }
603                    for lit in lit_elems {
604                        let domain_element = &lit.0;
605                        let codomain_element = &lit.1;
606                        if !domain.contains(domain_element)? {
607                            return Ok(false);
608                        }
609                        if !codomain.contains(codomain_element)? {
610                            return Ok(false);
611                        }
612                    }
613                    Ok(true)
614                }
615                _ => Ok(false),
616            },
617            GroundDomain::Variant(entries) => match lit {
618                Literal::AbstractLiteral(AbstractLiteral::Variant(lit_entry)) => {
619                    for entry in entries {
620                        if entry.name == lit_entry.name
621                            && !(entry.value.contains(&lit_entry.value)?)
622                        {
623                            return Ok(true);
624                        }
625                    }
626                    Ok(false)
627                }
628                _ => Ok(false),
629            },
630            GroundDomain::Relation(rel_attr, inner_domains) => match lit {
631                Literal::AbstractLiteral(AbstractLiteral::Relation(lit_elems)) => {
632                    // check if the literal's size is allowed by the attributes
633                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
634                    if !rel_attr.size.contains(&sz) {
635                        return Ok(false);
636                    }
637
638                    for elem_tuple in lit_elems {
639                        if elem_tuple.len() == inner_domains.len() {
640                            for (elem, inner_dom) in elem_tuple.iter().zip(inner_domains.iter()) {
641                                if !inner_dom.contains(elem)? {
642                                    return Ok(false);
643                                }
644                            }
645                        } else {
646                            return Ok(false);
647                        }
648                    }
649                    Ok(true)
650                }
651                _ => Ok(false),
652            },
653            GroundDomain::Partition(attr, dom) => match lit {
654                Literal::AbstractLiteral(AbstractLiteral::Partition(lit_elems)) => {
655                    // let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
656                    let sz: i32 = lit_elems
657                        .iter()
658                        .flatten()
659                        .count()
660                        .to_i32()
661                        .ok_or(DomainOpError::TooLarge)?;
662
663                    let min: Option<i32> = match (attr.num_parts.low(), attr.part_len.low()) {
664                        (Some(x), Some(y)) => Some(x * y),
665                        _ => None,
666                    };
667
668                    let max: Option<i32> = match (attr.num_parts.high(), attr.part_len.high()) {
669                        (Some(x), Some(y)) => Some(x * y),
670                        _ => None,
671                    };
672
673                    let rng = Range::new(min, max);
674                    if rng.contains(&sz) {
675                        return Ok(false);
676                    }
677
678                    for elem in lit_elems.iter().flatten() {
679                        if !dom.contains(elem)? {
680                            return Ok(false);
681                        }
682                    }
683                    Ok(true)
684                }
685                _ => Ok(false),
686            },
687        }
688    }
689
690    /// Returns a list of all possible values in an integer domain.
691    ///
692    /// # Errors
693    ///
694    /// - [`DomainOpError::NotInteger`] if the domain is not an integer domain.
695    /// - [`DomainOpError::Unbounded`] if the domain is unbounded.
696    pub fn values_i32(&self) -> Result<Vec<i32>, DomainOpError> {
697        if let GroundDomain::Empty(ReturnType::Int) = self {
698            return Ok(vec![]);
699        }
700        let GroundDomain::Int(ranges) = self else {
701            return Err(DomainOpError::NotInteger(self.return_type()));
702        };
703
704        if ranges.is_empty() {
705            return Err(DomainOpError::Unbounded);
706        }
707
708        let mut values = vec![];
709        for range in ranges {
710            match range {
711                Range::Single(i) => {
712                    values.push(*i);
713                }
714                Range::Bounded(i, j) => {
715                    values.extend(*i..=*j);
716                }
717                Range::UnboundedR(_) | Range::UnboundedL(_) | Range::Unbounded => {
718                    return Err(DomainOpError::Unbounded);
719                }
720            }
721        }
722
723        Ok(values)
724    }
725
726    /// Creates an [`Domain::Int`] containing the given integers.
727    ///
728    /// # Examples
729    ///
730    /// ```
731    /// use conjure_cp_core::ast::{GroundDomain, Range};
732    /// use conjure_cp_core::{domain_int_ground,range};
733    /// use std::collections::BTreeSet;
734    ///
735    /// let elements = BTreeSet::from([1,2,3,4,5]);
736    ///
737    /// let domain = GroundDomain::from_set_i32(&elements);
738    ///
739    /// assert_eq!(domain,domain_int_ground!(1..5));
740    /// ```
741    ///
742    /// ```
743    /// use conjure_cp_core::ast::{GroundDomain,Range};
744    /// use conjure_cp_core::{domain_int_ground,range};
745    /// use std::collections::BTreeSet;
746    ///
747    /// let elements = BTreeSet::from([1,2,4,5,7,8,9,10]);
748    ///
749    /// let domain = GroundDomain::from_set_i32(&elements);
750    ///
751    /// assert_eq!(domain,domain_int_ground!(1..2,4..5,7..10));
752    /// ```
753    ///
754    /// ```
755    /// use conjure_cp_core::ast::{GroundDomain,Range,ReturnType};
756    /// use std::collections::BTreeSet;
757    ///
758    /// let elements = BTreeSet::from([]);
759    ///
760    /// let domain = GroundDomain::from_set_i32(&elements);
761    ///
762    /// assert!(matches!(domain,GroundDomain::Empty(ReturnType::Int)))
763    /// ```
764    pub fn from_set_i32(elements: &BTreeSet<i32>) -> GroundDomain {
765        if elements.is_empty() {
766            return GroundDomain::Empty(ReturnType::Int);
767        }
768        if elements.len() == 1 {
769            return GroundDomain::Int(vec![Range::Single(*elements.first().unwrap())]);
770        }
771
772        let mut elems_iter = elements.iter().copied();
773
774        let mut ranges: Vec<Range<i32>> = vec![];
775
776        // Loop over the elements in ascending order, turning all sequential runs of
777        // numbers into ranges.
778
779        // the bounds of the current run of numbers.
780        let mut lower = elems_iter
781            .next()
782            .expect("if we get here, elements should have => 2 elements");
783        let mut upper = lower;
784
785        for current in elems_iter {
786            // As elements is a BTreeSet, current is always strictly larger than lower.
787
788            if current == upper + 1 {
789                // current is part of the current run - we now have the run lower..current
790                //
791                upper = current;
792            } else {
793                // the run lower..upper has ended.
794                //
795                // Add the run lower..upper to the domain, and start a new run.
796
797                if lower == upper {
798                    ranges.push(range!(lower));
799                } else {
800                    ranges.push(range!(lower..upper));
801                }
802
803                lower = current;
804                upper = current;
805            }
806        }
807
808        // add the final run to the domain
809        if lower == upper {
810            ranges.push(range!(lower));
811        } else {
812            ranges.push(range!(lower..upper));
813        }
814
815        ranges = Range::squeeze(&ranges);
816        GroundDomain::Int(ranges)
817    }
818
819    /// Returns the domain that is the result of applying a binary operation to two integer domains.
820    ///
821    /// The given operator may return `None` if the operation is not defined for its arguments.
822    /// Undefined values will not be included in the resulting domain.
823    ///
824    /// # Errors
825    ///
826    /// - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.
827    /// - [`DomainOpError::NotInteger`] if either of the input domains are not integers.
828    pub fn apply_i32(
829        &self,
830        op: fn(i32, i32) -> Option<i32>,
831        other: &GroundDomain,
832    ) -> Result<GroundDomain, DomainOpError> {
833        let vs1 = self.values_i32()?;
834        let vs2 = other.values_i32()?;
835
836        let mut set = BTreeSet::new();
837        for (v1, v2) in itertools::iproduct!(vs1, vs2) {
838            if let Some(v) = op(v1, v2) {
839                set.insert(v);
840            }
841        }
842
843        Ok(GroundDomain::from_set_i32(&set))
844    }
845
846    /// Returns true if the domain is finite.
847    pub fn is_finite(&self) -> bool {
848        for domain in self.universe() {
849            if let GroundDomain::Int(ranges) = domain {
850                if ranges.is_empty() {
851                    return false;
852                }
853
854                if ranges.iter().any(|range| {
855                    matches!(
856                        range,
857                        Range::UnboundedL(_) | Range::UnboundedR(_) | Range::Unbounded
858                    )
859                }) {
860                    return false;
861                }
862            }
863        }
864        true
865    }
866
867    /// For a vector of literals, creates a domain that contains all the elements.
868    ///
869    /// The literals must all be of the same type.
870    ///
871    /// For abstract literals, this method merges the element domains of the literals, but not the
872    /// index domains. Thus, for fixed-sized abstract literals (matrices, tuples, records, etc.),
873    /// all literals in the vector must also have the same size / index domain:
874    ///
875    /// + Matrices: all literals must have the same index domain.
876    /// + Tuples: all literals must have the same number of elements.
877    /// + Records: all literals must have the same fields.
878    ///
879    /// # Errors
880    ///
881    /// - [DomainOpError::WrongType] if the input literals are of a different type to
882    ///   each-other, as described above.
883    ///
884    /// # Examples
885    ///
886    /// ```
887    /// use conjure_cp_core::ast::{Range, Literal, ReturnType, GroundDomain};
888    ///
889    /// let domain = GroundDomain::from_literal_vec(&vec![]);
890    /// assert_eq!(domain,Ok(GroundDomain::Empty(ReturnType::Unknown)));
891    /// ```
892    ///
893    /// ```
894    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};
895    /// use conjure_cp_core::{domain_int_ground, range, matrix};
896    ///
897    /// // `[1,2;int(2..3)], [4,5; int(2..3)]` has domain
898    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`
899    ///
900    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);
901    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(2..3)]);
902    ///
903    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
904    ///
905    /// let expected_domain = Ok(GroundDomain::Matrix(
906    ///     domain_int_ground!(1..2,4..5),vec![domain_int_ground!(2..3)]));
907    ///
908    /// assert_eq!(domain,expected_domain);
909    /// ```
910    ///
911    /// ```
912    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral,DomainOpError};
913    /// use conjure_cp_core::{domain_int_ground, range, matrix};
914    ///
915    /// // `[1,2;int(2..3)], [4,5; int(1..2)]` cannot be combined
916    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`
917    ///
918    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);
919    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]);
920    ///
921    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
922    ///
923    /// assert_eq!(domain,Err(DomainOpError::WrongType));
924    /// ```
925    ///
926    /// ```
927    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};
928    /// use conjure_cp_core::{domain_int_ground,range, matrix};
929    ///
930    /// // `[[1,2; int(1..2)];int(2)], [[4,5; int(1..2)]; int(2)]` has domain
931    /// // `matrix indexed by [int(2),int(1..2)] of int(1..2,4..5)`
932    ///
933    ///
934    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(1..2)]); domain_int_ground!(2)]);
935    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]); domain_int_ground!(2)]);
936    ///
937    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
938    ///
939    /// let expected_domain = Ok(GroundDomain::Matrix(
940    ///     domain_int_ground!(1..2,4..5),
941    ///     vec![domain_int_ground!(2),domain_int_ground!(1..2)]));
942    ///
943    /// assert_eq!(domain,expected_domain);
944    /// ```
945    ///
946    ///
947    pub fn from_literal_vec(literals: &[Literal]) -> Result<GroundDomain, DomainOpError> {
948        // TODO: use proptest to test this better?
949
950        if literals.is_empty() {
951            return Ok(GroundDomain::Empty(ReturnType::Unknown));
952        }
953
954        let first_literal = literals.first().unwrap();
955
956        match first_literal {
957            Literal::Int(_) => {
958                // check all literals are ints, then pass this to Domain::from_set_i32.
959                let mut ints = BTreeSet::new();
960                for lit in literals {
961                    let Literal::Int(i) = lit else {
962                        return Err(DomainOpError::WrongType);
963                    };
964
965                    ints.insert(*i);
966                }
967
968                Ok(GroundDomain::from_set_i32(&ints))
969            }
970            Literal::Bool(_) => {
971                // check all literals are bools
972                if literals.iter().any(|x| !matches!(x, Literal::Bool(_))) {
973                    Err(DomainOpError::WrongType)
974                } else {
975                    Ok(GroundDomain::Bool)
976                }
977            }
978            Literal::AbstractLiteral(AbstractLiteral::Set(_)) => {
979                let mut all_elems = vec![];
980
981                for lit in literals {
982                    let Literal::AbstractLiteral(AbstractLiteral::Set(elems)) = lit else {
983                        return Err(DomainOpError::WrongType);
984                    };
985
986                    all_elems.extend(elems.clone());
987                }
988                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
989
990                Ok(GroundDomain::Set(SetAttr::default(), Moo::new(elem_domain)))
991            }
992            Literal::AbstractLiteral(AbstractLiteral::MSet(_)) => {
993                let mut all_elems = vec![];
994
995                for lit in literals {
996                    let Literal::AbstractLiteral(AbstractLiteral::MSet(elems)) = lit else {
997                        return Err(DomainOpError::WrongType);
998                    };
999
1000                    all_elems.extend(elems.clone());
1001                }
1002                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
1003
1004                Ok(GroundDomain::MSet(
1005                    MSetAttr::default(),
1006                    Moo::new(elem_domain),
1007                ))
1008            }
1009            Literal::AbstractLiteral(AbstractLiteral::Partition(_)) => {
1010                todo!("Need to figure out how this is going to work")
1011            }
1012            l @ Literal::AbstractLiteral(AbstractLiteral::Matrix(_, _)) => {
1013                let mut first_index_domain = vec![];
1014                // flatten index domains of n-d matrix into list
1015                let mut l = l.clone();
1016                while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {
1017                    assert!(
1018                        !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),
1019                        "n-dimensional matrix literals should be represented as a matrix inside a matrix"
1020                    );
1021                    first_index_domain.push(idx);
1022                    l = elems[0].clone();
1023                }
1024
1025                let mut all_elems: Vec<Literal> = vec![];
1026
1027                // check types and index domains
1028                for lit in literals {
1029                    let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = lit else {
1030                        return Err(DomainOpError::NotGround);
1031                    };
1032
1033                    all_elems.extend(elems.clone());
1034
1035                    let mut index_domain = vec![idx.clone()];
1036                    let mut l = elems[0].clone();
1037                    while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {
1038                        assert!(
1039                            !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),
1040                            "n-dimensional matrix literals should be represented as a matrix inside a matrix"
1041                        );
1042                        index_domain.push(idx);
1043                        l = elems[0].clone();
1044                    }
1045
1046                    if index_domain != first_index_domain {
1047                        return Err(DomainOpError::WrongType);
1048                    }
1049                }
1050
1051                // extract all the terminal elements (those that are not nested matrix literals) from the matrix literal.
1052                let mut terminal_elements: Vec<Literal> = vec![];
1053                while let Some(elem) = all_elems.pop() {
1054                    if let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, _)) = elem {
1055                        all_elems.extend(elems);
1056                    } else {
1057                        terminal_elements.push(elem);
1058                    }
1059                }
1060
1061                let element_domain = GroundDomain::from_literal_vec(&terminal_elements)?;
1062
1063                Ok(GroundDomain::Matrix(
1064                    Moo::new(element_domain),
1065                    first_index_domain,
1066                ))
1067            }
1068
1069            Literal::AbstractLiteral(AbstractLiteral::Tuple(first_elems)) => {
1070                let n_fields = first_elems.len();
1071
1072                // for each field, calculate the element domain and add it to this list
1073                let mut elem_domains = vec![];
1074
1075                for i in 0..n_fields {
1076                    let mut all_elems = vec![];
1077                    for lit in literals {
1078                        let Literal::AbstractLiteral(AbstractLiteral::Tuple(elems)) = lit else {
1079                            return Err(DomainOpError::NotGround);
1080                        };
1081
1082                        if elems.len() != n_fields {
1083                            return Err(DomainOpError::NotGround);
1084                        }
1085
1086                        all_elems.push(elems[i].clone());
1087                    }
1088
1089                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));
1090                }
1091
1092                Ok(GroundDomain::Tuple(elem_domains))
1093            }
1094
1095            Literal::AbstractLiteral(AbstractLiteral::Sequence(_)) => {
1096                let mut all_elems = vec![];
1097
1098                for lit in literals {
1099                    let Literal::AbstractLiteral(AbstractLiteral::Sequence(elems)) = lit else {
1100                        return Err(DomainOpError::WrongType);
1101                    };
1102
1103                    all_elems.extend(elems.clone());
1104                }
1105                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
1106
1107                Ok(GroundDomain::Sequence(
1108                    SequenceAttr::default(),
1109                    Moo::new(elem_domain),
1110                ))
1111            }
1112
1113            Literal::AbstractLiteral(AbstractLiteral::Record(first_elems)) => {
1114                let n_fields = first_elems.len();
1115                let field_names = first_elems.iter().map(|x| x.name.clone()).collect_vec();
1116
1117                // for each field, calculate the element domain and add it to this list
1118                let mut elem_domains = vec![];
1119
1120                for i in 0..n_fields {
1121                    let mut all_elems = vec![];
1122                    for lit in literals {
1123                        let Literal::AbstractLiteral(AbstractLiteral::Record(elems)) = lit else {
1124                            return Err(DomainOpError::NotGround);
1125                        };
1126
1127                        if elems.len() != n_fields {
1128                            return Err(DomainOpError::NotGround);
1129                        }
1130
1131                        let elem = elems[i].clone();
1132                        if elem.name != field_names[i] {
1133                            return Err(DomainOpError::NotGround);
1134                        }
1135
1136                        all_elems.push(elem.value);
1137                    }
1138
1139                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));
1140                }
1141
1142                Ok(GroundDomain::Record(
1143                    izip!(field_names, elem_domains)
1144                        .map(|(name, value)| FieldGround { name, value })
1145                        .collect(),
1146                ))
1147            }
1148            Literal::AbstractLiteral(AbstractLiteral::Function(items)) => {
1149                if items.is_empty() {
1150                    return Err(DomainOpError::NotGround);
1151                }
1152
1153                let (x1, y1) = &items[0];
1154                let d1 = x1.domain_of();
1155                let d1 = d1.as_ground().ok_or(DomainOpError::NotGround)?;
1156                let d2 = y1.domain_of();
1157                let d2 = d2.as_ground().ok_or(DomainOpError::NotGround)?;
1158
1159                // Check that all items have the same domains
1160                for (x, y) in items {
1161                    let dx = x.domain_of();
1162                    let dx = dx.as_ground().ok_or(DomainOpError::NotGround)?;
1163
1164                    let dy = y.domain_of();
1165                    let dy = dy.as_ground().ok_or(DomainOpError::NotGround)?;
1166
1167                    if (dx != d1) || (dy != d2) {
1168                        return Err(DomainOpError::WrongType);
1169                    }
1170                }
1171
1172                todo!();
1173            }
1174            Literal::AbstractLiteral(AbstractLiteral::Variant(_)) => {
1175                todo!();
1176            }
1177            Literal::AbstractLiteral(AbstractLiteral::Relation(_)) => {
1178                todo!();
1179            }
1180        }
1181    }
1182
1183    pub fn element_domain(&self) -> Option<Moo<GroundDomain>> {
1184        match self {
1185            GroundDomain::Set(_, inner) => Some(inner.clone()),
1186            GroundDomain::MSet(_, inner) => Some(inner.clone()),
1187            GroundDomain::Matrix(_, _) => todo!("Unwrap one dimension of the domain"),
1188            _ => None,
1189        }
1190    }
1191}
1192
1193impl Typeable for GroundDomain {
1194    fn return_type(&self) -> ReturnType {
1195        match self {
1196            GroundDomain::Empty(ty) => ty.clone(),
1197            GroundDomain::Bool => ReturnType::Bool,
1198            GroundDomain::Int(_) => ReturnType::Int,
1199            GroundDomain::Set(_attr, inner) => ReturnType::Set(Box::new(inner.return_type())),
1200            GroundDomain::MSet(_attr, inner) => ReturnType::MSet(Box::new(inner.return_type())),
1201            GroundDomain::Sequence(_attr, inner) => {
1202                ReturnType::Sequence(Box::new(inner.return_type()))
1203            }
1204            GroundDomain::Matrix(inner, _idx) => ReturnType::Matrix(Box::new(inner.return_type())),
1205            GroundDomain::Tuple(inners) => {
1206                let mut inner_types = Vec::new();
1207                for inner in inners {
1208                    inner_types.push(inner.return_type());
1209                }
1210                ReturnType::Tuple(inner_types)
1211            }
1212            GroundDomain::Function(_, dom, cdom) => {
1213                ReturnType::Function(Box::new(dom.return_type()), Box::new(cdom.return_type()))
1214            }
1215            GroundDomain::Record(entries) => {
1216                let mut entry_types = Vec::new();
1217                for entry in entries {
1218                    entry_types.push(entry.clone().func_map(|x| x.return_type()));
1219                }
1220                ReturnType::Record(entry_types)
1221            }
1222            GroundDomain::Variant(entries) => {
1223                let mut entry_types = Vec::new();
1224                for entry in entries {
1225                    entry_types.push(entry.clone().func_map(|x| x.return_type()));
1226                }
1227                ReturnType::Variant(entry_types)
1228            }
1229            GroundDomain::Relation(_, inners) => {
1230                let mut inner_types = Vec::new();
1231                for inner in inners {
1232                    inner_types.push(inner.return_type());
1233                }
1234                ReturnType::Relation(inner_types)
1235            }
1236            GroundDomain::Partition(_, inner) => ReturnType::Set(Box::new(inner.return_type())),
1237        }
1238    }
1239}
1240
1241impl Display for FieldGround {
1242    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
1243        write!(f, "{}: {}", self.name, self.value)
1244    }
1245}
1246
1247impl Display for GroundDomain {
1248    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
1249        match &self {
1250            GroundDomain::Empty(ty) => write!(f, "empty({ty})"),
1251            GroundDomain::Bool => write!(f, "bool"),
1252            GroundDomain::Int(ranges) => {
1253                if ranges.iter().all(Range::is_lower_or_upper_bounded) {
1254                    let rngs: String = ranges.iter().map(|r| format!("{r}")).join(", ");
1255                    write!(f, "int({})", rngs)
1256                } else {
1257                    write!(f, "int")
1258                }
1259            }
1260            GroundDomain::Set(attrs, inner_dom) => write!(f, "set {attrs} of {inner_dom}"),
1261            GroundDomain::MSet(attrs, inner_dom) => write!(f, "mset {attrs} of {inner_dom}"),
1262            GroundDomain::Sequence(attrs, inner_dom) => {
1263                write!(f, "sequence {attrs} of {inner_dom}")
1264            }
1265            GroundDomain::Matrix(value_domain, index_domains) => {
1266                write!(
1267                    f,
1268                    "matrix indexed by {} of {value_domain}",
1269                    pretty_vec(&index_domains.iter().collect_vec())
1270                )
1271            }
1272            GroundDomain::Tuple(domains) => {
1273                write!(f, "tuple ({})", &domains.iter().join(", "))
1274            }
1275            GroundDomain::Record(entries) => {
1276                let inners = entries.iter().map(|t| format!("{}", t)).join(", ");
1277                write!(f, "record {{{inners}}}",)
1278            }
1279            GroundDomain::Variant(entries) => {
1280                let inners = entries.iter().map(|t| format!("{}", t)).join(", ");
1281                write!(f, "variant {{{inners}}}",)
1282            }
1283            GroundDomain::Function(attribute, domain, codomain) => {
1284                write!(f, "function {} {} --> {} ", attribute, domain, codomain)
1285            }
1286            GroundDomain::Relation(attrs, domains) => {
1287                write!(f, "relation {} of ({})", attrs, domains.iter().join(" * "))
1288            }
1289            GroundDomain::Partition(attrs, inner) => {
1290                write!(f, "partition {attrs} from {inner}")
1291            }
1292        }
1293    }
1294}
1295
1296#[cfg(test)]
1297mod tests {
1298    use super::*;
1299    use crate::ast::Name;
1300    use crate::{domain_int_ground, matrix_lit};
1301
1302    #[test]
1303    fn matrix_values_1d_bool_of_bool() {
1304        // matrix indexed by [bool] of bool
1305        // 2 cells, 2 possible values => 2^2 = 4 matrices
1306        let dom = GroundDomain::Matrix(
1307            Moo::new(GroundDomain::Bool),
1308            vec![Moo::new(GroundDomain::Bool)],
1309        );
1310
1311        let values: Vec<Literal> = dom.values().unwrap().collect();
1312
1313        assert_eq!(values.len(), 4);
1314        assert_eq!(
1315            values[0],
1316            matrix_lit![false, false; Moo::new(GroundDomain::Bool)]
1317        );
1318        assert_eq!(
1319            values[1],
1320            matrix_lit![false, true; Moo::new(GroundDomain::Bool)]
1321        );
1322        assert_eq!(
1323            values[2],
1324            matrix_lit![true, false; Moo::new(GroundDomain::Bool)]
1325        );
1326        assert_eq!(
1327            values[3],
1328            matrix_lit![true, true; Moo::new(GroundDomain::Bool)]
1329        );
1330    }
1331
1332    #[test]
1333    fn matrix_values_1d_int() {
1334        // matrix indexed by [int(1..2)] of int(0..1)
1335        // 2 cells, 2 possible values => 4 matrices
1336        let dom = GroundDomain::Matrix(domain_int_ground!(0..1), vec![domain_int_ground!(1..2)]);
1337
1338        let values: Vec<Literal> = dom.values().unwrap().collect();
1339
1340        assert_eq!(values.len(), 4);
1341        assert_eq!(values[0], matrix_lit![0, 0; domain_int_ground!(1..2)]);
1342        assert_eq!(values[1], matrix_lit![0, 1; domain_int_ground!(1..2)]);
1343        assert_eq!(values[2], matrix_lit![1, 0; domain_int_ground!(1..2)]);
1344        assert_eq!(values[3], matrix_lit![1, 1; domain_int_ground!(1..2)]);
1345    }
1346
1347    #[test]
1348    fn matrix_values_2d_lexicographic() {
1349        // matrix indexed by [int(1..2), int(1..2)] of int(0..1)
1350        // 4 cells, 2 possible values => 2^4 = 16 matrices
1351        let dom = GroundDomain::Matrix(
1352            domain_int_ground!(0..1),
1353            vec![domain_int_ground!(1..2), domain_int_ground!(1..2)],
1354        );
1355
1356        let values: Vec<Literal> = dom.values().unwrap().collect();
1357
1358        assert_eq!(values.len(), 16);
1359
1360        // First: [[0,0],[0,0]]
1361        assert_eq!(
1362            values[0],
1363            matrix_lit![[0, 0], [0, 0]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]
1364        );
1365        // Second: [[0,0],[0,1]]
1366        assert_eq!(
1367            values[1],
1368            matrix_lit![[0, 0], [0, 1]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]
1369        );
1370        // Third: [[0,0],[1,0]]
1371        assert_eq!(
1372            values[2],
1373            matrix_lit![[0, 0], [1, 0]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]
1374        );
1375        // Fourth: [[0,0],[1,1]]
1376        assert_eq!(
1377            values[3],
1378            matrix_lit![[0, 0], [1, 1]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]
1379        );
1380        // Last: [[1,1],[1,1]]
1381        assert_eq!(
1382            values[15],
1383            matrix_lit![[1, 1], [1, 1]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]
1384        );
1385    }
1386
1387    #[test]
1388    fn matrix_values_count_matches_length() {
1389        // matrix indexed by [int(1..3)] of int(0..1)
1390        // 3 cells, 2 possible values => 2^3 = 8 matrices
1391        let dom = GroundDomain::Matrix(domain_int_ground!(0..1), vec![domain_int_ground!(1..3)]);
1392
1393        let count = dom.values().unwrap().count();
1394        let length = dom.length().unwrap();
1395
1396        assert_eq!(count as u64, length);
1397    }
1398
1399    #[test]
1400    fn tuple_values_two_bools() {
1401        // tuple of (bool, bool) => 2*2 = 4 values
1402        let dom = GroundDomain::Tuple(vec![
1403            Moo::new(GroundDomain::Bool),
1404            Moo::new(GroundDomain::Bool),
1405        ]);
1406
1407        let values: Vec<Literal> = dom.values().unwrap().collect();
1408
1409        assert_eq!(values.len(), 4);
1410        let t = |a, b| {
1411            Literal::AbstractLiteral(AbstractLiteral::Tuple(vec![
1412                Literal::Bool(a),
1413                Literal::Bool(b),
1414            ]))
1415        };
1416        assert_eq!(values[0], t(false, false));
1417        assert_eq!(values[1], t(false, true));
1418        assert_eq!(values[2], t(true, false));
1419        assert_eq!(values[3], t(true, true));
1420    }
1421
1422    #[test]
1423    fn tuple_values_mixed_domains() {
1424        // tuple of (bool, int(0..2)) => 2*3 = 6 values, lexicographic
1425        let dom = GroundDomain::Tuple(vec![Moo::new(GroundDomain::Bool), domain_int_ground!(0..2)]);
1426
1427        let values: Vec<Literal> = dom.values().unwrap().collect();
1428
1429        assert_eq!(values.len(), 6);
1430        let t = |b: bool, i: i32| {
1431            Literal::AbstractLiteral(AbstractLiteral::Tuple(vec![
1432                Literal::Bool(b),
1433                Literal::Int(i),
1434            ]))
1435        };
1436        // bool false first, then ints 0,1,2
1437        assert_eq!(values[0], t(false, 0));
1438        assert_eq!(values[1], t(false, 1));
1439        assert_eq!(values[2], t(false, 2));
1440        // then bool true
1441        assert_eq!(values[3], t(true, 0));
1442        assert_eq!(values[4], t(true, 1));
1443        assert_eq!(values[5], t(true, 2));
1444    }
1445
1446    #[test]
1447    fn tuple_values_count_matches_length() {
1448        let dom = GroundDomain::Tuple(vec![
1449            domain_int_ground!(1..3),
1450            Moo::new(GroundDomain::Bool),
1451            domain_int_ground!(0..1),
1452        ]);
1453        let count = dom.values().unwrap().count();
1454        let length = dom.length().unwrap();
1455        assert_eq!(count as u64, length);
1456    }
1457
1458    #[test]
1459    fn record_values_lexicographic_by_name() {
1460        // record {b: bool, a: int(0..1)}
1461        // Entries should be ordered by name: a first, then b
1462        let dom = GroundDomain::Record(vec![
1463            Field {
1464                name: Name::user("b"),
1465                value: Moo::new(GroundDomain::Bool),
1466            },
1467            Field {
1468                name: Name::user("a"),
1469                value: domain_int_ground!(0..1),
1470            },
1471        ]);
1472
1473        let values: Vec<Literal> = dom.values().unwrap().collect();
1474
1475        // 2 * 2 = 4 values
1476        assert_eq!(values.len(), 4);
1477
1478        // Entries should be sorted by name: "a" before "b"
1479        let r = |a_val: i32, b_val: bool| {
1480            Literal::AbstractLiteral(AbstractLiteral::Record(vec![
1481                Field {
1482                    name: Name::user("a"),
1483                    value: Literal::Int(a_val),
1484                },
1485                Field {
1486                    name: Name::user("b"),
1487                    value: Literal::Bool(b_val),
1488                },
1489            ]))
1490        };
1491
1492        // "a" (int) varies slowest, "b" (bool) varies fastest
1493        assert_eq!(values[0], r(0, false));
1494        assert_eq!(values[1], r(0, true));
1495        assert_eq!(values[2], r(1, false));
1496        assert_eq!(values[3], r(1, true));
1497    }
1498
1499    #[test]
1500    fn record_values_count_matches_length() {
1501        let dom = GroundDomain::Record(vec![
1502            Field {
1503                name: Name::user("x"),
1504                value: domain_int_ground!(1..3),
1505            },
1506            Field {
1507                name: Name::user("y"),
1508                value: Moo::new(GroundDomain::Bool),
1509            },
1510        ]);
1511        let count = dom.values().unwrap().count();
1512        let length = dom.length().unwrap();
1513        assert_eq!(count as u64, length);
1514    }
1515
1516    fn set_lit(elems: Vec<i32>) -> Literal {
1517        Literal::AbstractLiteral(AbstractLiteral::Set(
1518            elems.into_iter().map(Literal::Int).collect(),
1519        ))
1520    }
1521
1522    #[test]
1523    fn set_values_unbounded() {
1524        // set of int(1..3) => all 2^3 = 8 subsets, in order of ascending size
1525        let dom = GroundDomain::Set(SetAttr::default(), domain_int_ground!(1..3));
1526
1527        let values: Vec<Literal> = dom.values().unwrap().collect();
1528
1529        assert_eq!(values.len(), 8);
1530        assert_eq!(values[0], set_lit(vec![])); // size 0
1531        assert_eq!(values[1], set_lit(vec![1])); // size 1
1532        assert_eq!(values[2], set_lit(vec![2]));
1533        assert_eq!(values[3], set_lit(vec![3]));
1534        assert_eq!(values[4], set_lit(vec![1, 2])); // size 2
1535        assert_eq!(values[5], set_lit(vec![1, 3]));
1536        assert_eq!(values[6], set_lit(vec![2, 3]));
1537        assert_eq!(values[7], set_lit(vec![1, 2, 3])); // size 3
1538    }
1539
1540    #[test]
1541    fn set_values_fixed_size() {
1542        // set (size 2) of int(1..3) => the 3 two-element subsets
1543        let dom = GroundDomain::Set(SetAttr::new_size(2), domain_int_ground!(1..3));
1544
1545        let values: Vec<Literal> = dom.values().unwrap().collect();
1546
1547        assert_eq!(values.len(), 3);
1548        assert_eq!(values[0], set_lit(vec![1, 2]));
1549        assert_eq!(values[1], set_lit(vec![1, 3]));
1550        assert_eq!(values[2], set_lit(vec![2, 3]));
1551    }
1552
1553    #[test]
1554    fn set_values_bounded_size() {
1555        // set (minSize 1, maxSize 2) of int(1..3) => subsets of size 1 and 2
1556        let dom = GroundDomain::Set(SetAttr::new_min_max_size(1, 2), domain_int_ground!(1..3));
1557
1558        let values: Vec<Literal> = dom.values().unwrap().collect();
1559
1560        assert_eq!(values.len(), 6);
1561        assert_eq!(values[0], set_lit(vec![1]));
1562        assert_eq!(values[1], set_lit(vec![2]));
1563        assert_eq!(values[2], set_lit(vec![3]));
1564        assert_eq!(values[3], set_lit(vec![1, 2]));
1565        assert_eq!(values[4], set_lit(vec![1, 3]));
1566        assert_eq!(values[5], set_lit(vec![2, 3]));
1567    }
1568
1569    #[test]
1570    fn set_values_count_matches_length() {
1571        let dom = GroundDomain::Set(SetAttr::default(), domain_int_ground!(1..4));
1572        let count = dom.values().unwrap().count();
1573        let length = dom.length().unwrap();
1574        assert_eq!(count as u64, length);
1575    }
1576}
conjure_cp_core/ast/domains/ground.rs

conjure_cp_core/ast/domains/
ground.rs
