conjure_cp_core/ast/domains/
ground.rs

1use crate::ast::domains::MSetAttr;
2use crate::ast::pretty::pretty_vec;
3use crate::ast::{
4    AbstractLiteral, Domain, DomainOpError, FuncAttr, HasDomain, Literal, Moo, RecordEntry,
5    SetAttr, Typeable,
6    domains::{domain::Int, range::Range},
7};
8use crate::range;
9use crate::utils::count_combinations;
10use conjure_cp_core::ast::{Name, ReturnType};
11use itertools::{Itertools, izip};
12use num_traits::ToPrimitive;
13use polyquine::Quine;
14use serde::{Deserialize, Serialize};
15use std::collections::BTreeSet;
16use std::fmt::{Display, Formatter};
17use std::iter::zip;
18use uniplate::Uniplate;
19
20#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Uniplate, Quine)]
21#[path_prefix(conjure_cp::ast)]
22pub struct RecordEntryGround {
23    pub name: Name,
24    pub domain: Moo<GroundDomain>,
25}
26
27impl From<RecordEntryGround> for RecordEntry {
28    fn from(value: RecordEntryGround) -> Self {
29        RecordEntry {
30            name: value.name,
31            domain: value.domain.into(),
32        }
33    }
34}
35
36impl TryFrom<RecordEntry> for RecordEntryGround {
37    type Error = DomainOpError;
38
39    fn try_from(value: RecordEntry) -> Result<Self, Self::Error> {
40        match value.domain.as_ref() {
41            Domain::Ground(gd) => Ok(RecordEntryGround {
42                name: value.name,
43                domain: gd.clone(),
44            }),
45            Domain::Unresolved(_) => Err(DomainOpError::NotGround),
46        }
47    }
48}
49
50#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Quine, Uniplate)]
51#[path_prefix(conjure_cp::ast)]
52pub enum GroundDomain {
53    /// An empty domain of a given type
54    Empty(ReturnType),
55    /// A boolean value (true / false)
56    Bool,
57    /// An integer value in the given ranges (e.g. int(1, 3..5))
58    Int(Vec<Range<Int>>),
59    /// A set of elements drawn from the inner domain
60    Set(SetAttr<Int>, Moo<GroundDomain>),
61    /// A multiset of elements drawn from the inner domain
62    MSet(MSetAttr<Int>, Moo<GroundDomain>),
63    /// An N-dimensional matrix of elements drawn from the inner domain,
64    /// and indices from the n index domains
65    Matrix(Moo<GroundDomain>, Vec<Moo<GroundDomain>>),
66    /// A tuple of N elements, each with its own domain
67    Tuple(Vec<Moo<GroundDomain>>),
68    /// A record
69    Record(Vec<RecordEntryGround>),
70    /// A function with a domain and range
71    Function(FuncAttr, Moo<GroundDomain>, Moo<GroundDomain>),
72}
73
74impl GroundDomain {
75    pub fn union(&self, other: &GroundDomain) -> Result<GroundDomain, DomainOpError> {
76        match (self, other) {
77            (GroundDomain::Empty(ty), dom) | (dom, GroundDomain::Empty(ty)) => {
78                if *ty == dom.return_type() {
79                    Ok(dom.clone())
80                } else {
81                    Err(DomainOpError::WrongType)
82                }
83            }
84            (GroundDomain::Bool, GroundDomain::Bool) => Ok(GroundDomain::Bool),
85            (GroundDomain::Bool, _) | (_, GroundDomain::Bool) => Err(DomainOpError::WrongType),
86            (GroundDomain::Int(r1), GroundDomain::Int(r2)) => {
87                let mut rngs = r1.clone();
88                rngs.extend(r2.clone());
89                Ok(GroundDomain::Int(Range::squeeze(&rngs)))
90            }
91            (GroundDomain::Int(_), _) | (_, GroundDomain::Int(_)) => Err(DomainOpError::WrongType),
92            (GroundDomain::Set(_, in1), GroundDomain::Set(_, in2)) => Ok(GroundDomain::Set(
93                SetAttr::default(),
94                Moo::new(in1.union(in2)?),
95            )),
96            (GroundDomain::Set(_, _), _) | (_, GroundDomain::Set(_, _)) => {
97                Err(DomainOpError::WrongType)
98            }
99            (GroundDomain::MSet(_, in1), GroundDomain::MSet(_, in2)) => Ok(GroundDomain::MSet(
100                MSetAttr::default(),
101                Moo::new(in1.union(in2)?),
102            )),
103            (GroundDomain::Matrix(in1, idx1), GroundDomain::Matrix(in2, idx2)) if idx1 == idx2 => {
104                Ok(GroundDomain::Matrix(
105                    Moo::new(in1.union(in2)?),
106                    idx1.clone(),
107                ))
108            }
109            (GroundDomain::Matrix(_, _), _) | (_, GroundDomain::Matrix(_, _)) => {
110                Err(DomainOpError::WrongType)
111            }
112            (GroundDomain::Tuple(in1s), GroundDomain::Tuple(in2s)) if in1s.len() == in2s.len() => {
113                let mut inners = Vec::new();
114                for (in1, in2) in zip(in1s, in2s) {
115                    inners.push(Moo::new(in1.union(in2)?));
116                }
117                Ok(GroundDomain::Tuple(inners))
118            }
119            (GroundDomain::Tuple(_), _) | (_, GroundDomain::Tuple(_)) => {
120                Err(DomainOpError::WrongType)
121            }
122            // TODO: Eventually we may define semantics for joining record domains. This day is not today.
123            #[allow(unreachable_patterns)]
124            // Technically redundant but logically clearer to have both
125            (GroundDomain::Record(_), _) | (_, GroundDomain::Record(_)) => {
126                Err(DomainOpError::WrongType)
127            }
128            #[allow(unreachable_patterns)]
129            // Technically redundant but logically clearer to have both
130            (GroundDomain::Function(_, _, _), _) | (_, GroundDomain::Function(_, _, _)) => {
131                Err(DomainOpError::WrongType)
132            }
133        }
134    }
135
136    /// Calculates the intersection of two domains.
137    ///
138    /// # Errors
139    ///
140    ///  - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.
141    ///  - [`DomainOpError::WrongType`] if the input domains are different types, or are not integer or set domains.
142    pub fn intersect(&self, other: &GroundDomain) -> Result<GroundDomain, DomainOpError> {
143        // TODO: does not consider unbounded domains yet
144        // needs to be tested once comprehension rules are written
145
146        match (self, other) {
147            // one or more arguments is an empty int domain
148            (d @ GroundDomain::Empty(ReturnType::Int), GroundDomain::Int(_)) => Ok(d.clone()),
149            (GroundDomain::Int(_), d @ GroundDomain::Empty(ReturnType::Int)) => Ok(d.clone()),
150            (GroundDomain::Empty(ReturnType::Int), d @ GroundDomain::Empty(ReturnType::Int)) => {
151                Ok(d.clone())
152            }
153
154            // one or more arguments is an empty set(int) domain
155            (GroundDomain::Set(_, inner1), d @ GroundDomain::Empty(ReturnType::Set(inner2)))
156                if matches!(
157                    **inner1,
158                    GroundDomain::Int(_) | GroundDomain::Empty(ReturnType::Int)
159                ) && matches!(**inner2, ReturnType::Int) =>
160            {
161                Ok(d.clone())
162            }
163            (d @ GroundDomain::Empty(ReturnType::Set(inner1)), GroundDomain::Set(_, inner2))
164                if matches!(**inner1, ReturnType::Int)
165                    && matches!(
166                        **inner2,
167                        GroundDomain::Int(_) | GroundDomain::Empty(ReturnType::Int)
168                    ) =>
169            {
170                Ok(d.clone())
171            }
172            (
173                d @ GroundDomain::Empty(ReturnType::Set(inner1)),
174                GroundDomain::Empty(ReturnType::Set(inner2)),
175            ) if matches!(**inner1, ReturnType::Int) && matches!(**inner2, ReturnType::Int) => {
176                Ok(d.clone())
177            }
178
179            // both arguments are non-empy
180            (GroundDomain::Set(_, x), GroundDomain::Set(_, y)) => Ok(GroundDomain::Set(
181                SetAttr::default(),
182                Moo::new((*x).intersect(y)?),
183            )),
184
185            (GroundDomain::Int(_), GroundDomain::Int(_)) => {
186                let mut v: BTreeSet<i32> = BTreeSet::new();
187
188                let v1 = self.values_i32()?;
189                let v2 = other.values_i32()?;
190                for value1 in v1.iter() {
191                    if v2.contains(value1) && !v.contains(value1) {
192                        v.insert(*value1);
193                    }
194                }
195                Ok(GroundDomain::from_set_i32(&v))
196            }
197            _ => Err(DomainOpError::WrongType),
198        }
199    }
200
201    pub fn values(&self) -> Result<Box<dyn Iterator<Item = Literal>>, DomainOpError> {
202        match self {
203            GroundDomain::Empty(_) => Ok(Box::new(vec![].into_iter())),
204            GroundDomain::Bool => Ok(Box::new(
205                vec![Literal::from(true), Literal::from(false)].into_iter(),
206            )),
207            GroundDomain::Int(rngs) => {
208                let rng_iters = rngs
209                    .iter()
210                    .map(Range::iter)
211                    .collect::<Option<Vec<_>>>()
212                    .ok_or(DomainOpError::Unbounded)?;
213                Ok(Box::new(
214                    rng_iters.into_iter().flat_map(|ri| ri.map(Literal::from)),
215                ))
216            }
217            _ => todo!("Enumerating nested domains is not yet supported"),
218        }
219    }
220
221    /// Gets the length of this domain.
222    ///
223    /// # Errors
224    ///
225    /// - [`DomainOpError::Unbounded`] if the input domain is of infinite size.
226    pub fn length(&self) -> Result<u64, DomainOpError> {
227        match self {
228            GroundDomain::Empty(_) => Ok(0),
229            GroundDomain::Bool => Ok(2),
230            GroundDomain::Int(ranges) => {
231                if ranges.is_empty() {
232                    return Err(DomainOpError::Unbounded);
233                }
234
235                let mut length = 0u64;
236                for range in ranges {
237                    if let Some(range_length) = range.length() {
238                        length += range_length as u64;
239                    } else {
240                        return Err(DomainOpError::Unbounded);
241                    }
242                }
243                Ok(length)
244            }
245            GroundDomain::Set(set_attr, inner_domain) => {
246                let inner_len = inner_domain.length()?;
247                let (min_sz, max_sz) = match set_attr.size {
248                    Range::Unbounded => (0, inner_len),
249                    Range::Single(n) => (n as u64, n as u64),
250                    Range::UnboundedR(n) => (n as u64, inner_len),
251                    Range::UnboundedL(n) => (0, n as u64),
252                    Range::Bounded(min, max) => (min as u64, max as u64),
253                };
254                let mut ans = 0u64;
255                for sz in min_sz..=max_sz {
256                    let c = count_combinations(inner_len, sz)?;
257                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;
258                }
259                Ok(ans)
260            }
261            GroundDomain::MSet(mset_attr, inner_domain) => {
262                let inner_len = inner_domain.length()?;
263                let (min_sz, max_sz) = match mset_attr.size {
264                    Range::Unbounded => (0, inner_len),
265                    Range::Single(n) => (n as u64, n as u64),
266                    Range::UnboundedR(n) => (n as u64, inner_len),
267                    Range::UnboundedL(n) => (0, n as u64),
268                    Range::Bounded(min, max) => (min as u64, max as u64),
269                };
270                let mut ans = 0u64;
271                for sz in min_sz..=max_sz {
272                    // need  "multichoose", ((n  k)) == (n+k-1  k)
273                    // Where n=inner_len and k=sz
274                    let c = count_combinations(inner_len + sz - 1, sz)?;
275                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;
276                }
277                Ok(ans)
278            }
279            GroundDomain::Tuple(domains) => {
280                let mut ans = 1u64;
281                for domain in domains {
282                    ans = ans
283                        .checked_mul(domain.length()?)
284                        .ok_or(DomainOpError::TooLarge)?;
285                }
286                Ok(ans)
287            }
288            GroundDomain::Record(entries) => {
289                // A record is just a named tuple
290                let mut ans = 1u64;
291                for entry in entries {
292                    let sz = entry.domain.length()?;
293                    ans = ans.checked_mul(sz).ok_or(DomainOpError::TooLarge)?;
294                }
295                Ok(ans)
296            }
297            GroundDomain::Matrix(inner_domain, idx_domains) => {
298                let inner_sz = inner_domain.length()?;
299                let exp = idx_domains.iter().try_fold(1u32, |acc, val| {
300                    let len = val.length()? as u32;
301                    acc.checked_mul(len).ok_or(DomainOpError::TooLarge)
302                })?;
303                inner_sz.checked_pow(exp).ok_or(DomainOpError::TooLarge)
304            }
305            GroundDomain::Function(_, _, _) => {
306                todo!("Length bound of functions is not yet supported")
307            }
308        }
309    }
310
311    pub fn contains(&self, lit: &Literal) -> Result<bool, DomainOpError> {
312        // not adding a generic wildcard condition for all domains, so that this gives a compile
313        // error when a domain is added.
314        match self {
315            // empty domain can't contain anything
316            GroundDomain::Empty(_) => Ok(false),
317            GroundDomain::Bool => match lit {
318                Literal::Bool(_) => Ok(true),
319                _ => Ok(false),
320            },
321            GroundDomain::Int(ranges) => match lit {
322                Literal::Int(x) => {
323                    // unconstrained int domain - contains all integers
324                    if ranges.is_empty() {
325                        return Ok(true);
326                    };
327
328                    Ok(ranges.iter().any(|range| range.contains(x)))
329                }
330                _ => Ok(false),
331            },
332            GroundDomain::Set(set_attr, inner_domain) => match lit {
333                Literal::AbstractLiteral(AbstractLiteral::Set(lit_elems)) => {
334                    // check if the literal's size is allowed by the set attribute
335                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
336                    if !set_attr.size.contains(&sz) {
337                        return Ok(false);
338                    }
339
340                    for elem in lit_elems {
341                        if !inner_domain.contains(elem)? {
342                            return Ok(false);
343                        }
344                    }
345                    Ok(true)
346                }
347                _ => Ok(false),
348            },
349            GroundDomain::MSet(mset_attr, inner_domain) => match lit {
350                Literal::AbstractLiteral(AbstractLiteral::MSet(lit_elems)) => {
351                    // check if the literal's size is allowed by the mset attribute
352                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
353                    if !mset_attr.size.contains(&sz) {
354                        return Ok(false);
355                    }
356
357                    for elem in lit_elems {
358                        if !inner_domain.contains(elem)? {
359                            return Ok(false);
360                        }
361                    }
362                    Ok(true)
363                }
364                _ => Ok(false),
365            },
366            GroundDomain::Matrix(elem_domain, index_domains) => {
367                match lit {
368                    Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx_domain)) => {
369                        // Matrix literals are represented as nested 1d matrices, so the elements of
370                        // the matrix literal will be the inner dimensions of the matrix.
371
372                        let mut index_domains = index_domains.clone();
373                        if index_domains
374                            .pop()
375                            .expect("a matrix should have at least one index domain")
376                            != *idx_domain
377                        {
378                            return Ok(false);
379                        };
380
381                        let next_elem_domain = if index_domains.is_empty() {
382                            // Base case - we have a 1D row. Now check if all elements in the
383                            // literal are in this row's element domain.
384                            elem_domain.as_ref().clone()
385                        } else {
386                            // Otherwise, go down a dimension (e.g. 2D matrix inside a 3D tensor)
387                            GroundDomain::Matrix(elem_domain.clone(), index_domains)
388                        };
389
390                        for elem in elems {
391                            if !next_elem_domain.contains(elem)? {
392                                return Ok(false);
393                            }
394                        }
395
396                        Ok(true)
397                    }
398                    _ => Ok(false),
399                }
400            }
401            GroundDomain::Tuple(elem_domains) => {
402                match lit {
403                    Literal::AbstractLiteral(AbstractLiteral::Tuple(literal_elems)) => {
404                        if elem_domains.len() != literal_elems.len() {
405                            return Ok(false);
406                        }
407
408                        // for every element in the tuple literal, check if it is in the corresponding domain
409                        for (elem_domain, elem) in itertools::izip!(elem_domains, literal_elems) {
410                            if !elem_domain.contains(elem)? {
411                                return Ok(false);
412                            }
413                        }
414
415                        Ok(true)
416                    }
417                    _ => Ok(false),
418                }
419            }
420            GroundDomain::Record(entries) => match lit {
421                Literal::AbstractLiteral(AbstractLiteral::Record(lit_entries)) => {
422                    if entries.len() != lit_entries.len() {
423                        return Ok(false);
424                    }
425
426                    for (entry, lit_entry) in itertools::izip!(entries, lit_entries) {
427                        if entry.name != lit_entry.name
428                            || !(entry.domain.contains(&lit_entry.value)?)
429                        {
430                            return Ok(false);
431                        }
432                    }
433                    Ok(true)
434                }
435                _ => Ok(false),
436            },
437            GroundDomain::Function(func_attr, domain, codomain) => match lit {
438                Literal::AbstractLiteral(AbstractLiteral::Function(lit_elems)) => {
439                    let sz = Int::try_from(lit_elems.len()).expect("Should convert");
440                    if !func_attr.size.contains(&sz) {
441                        return Ok(false);
442                    }
443                    for lit in lit_elems {
444                        let domain_element = &lit.0;
445                        let codomain_element = &lit.1;
446                        if !domain.contains(domain_element)? {
447                            return Ok(false);
448                        }
449                        if !codomain.contains(codomain_element)? {
450                            return Ok(false);
451                        }
452                    }
453                    Ok(true)
454                }
455                _ => Ok(false),
456            },
457        }
458    }
459
460    /// Returns a list of all possible values in an integer domain.
461    ///
462    /// # Errors
463    ///
464    /// - [`DomainOpError::NotInteger`] if the domain is not an integer domain.
465    /// - [`DomainOpError::Unbounded`] if the domain is unbounded.
466    pub fn values_i32(&self) -> Result<Vec<i32>, DomainOpError> {
467        if let GroundDomain::Empty(ReturnType::Int) = self {
468            return Ok(vec![]);
469        }
470        let GroundDomain::Int(ranges) = self else {
471            return Err(DomainOpError::NotInteger(self.return_type()));
472        };
473
474        if ranges.is_empty() {
475            return Err(DomainOpError::Unbounded);
476        }
477
478        let mut values = vec![];
479        for range in ranges {
480            match range {
481                Range::Single(i) => {
482                    values.push(*i);
483                }
484                Range::Bounded(i, j) => {
485                    values.extend(*i..=*j);
486                }
487                Range::UnboundedR(_) | Range::UnboundedL(_) | Range::Unbounded => {
488                    return Err(DomainOpError::Unbounded);
489                }
490            }
491        }
492
493        Ok(values)
494    }
495
496    /// Creates an [`Domain::Int`] containing the given integers.
497    ///
498    /// # Examples
499    ///
500    /// ```
501    /// use conjure_cp_core::ast::{GroundDomain, Range};
502    /// use conjure_cp_core::{domain_int_ground,range};
503    /// use std::collections::BTreeSet;
504    ///
505    /// let elements = BTreeSet::from([1,2,3,4,5]);
506    ///
507    /// let domain = GroundDomain::from_set_i32(&elements);
508    ///
509    /// assert_eq!(domain,domain_int_ground!(1..5));
510    /// ```
511    ///
512    /// ```
513    /// use conjure_cp_core::ast::{GroundDomain,Range};
514    /// use conjure_cp_core::{domain_int_ground,range};
515    /// use std::collections::BTreeSet;
516    ///
517    /// let elements = BTreeSet::from([1,2,4,5,7,8,9,10]);
518    ///
519    /// let domain = GroundDomain::from_set_i32(&elements);
520    ///
521    /// assert_eq!(domain,domain_int_ground!(1..2,4..5,7..10));
522    /// ```
523    ///
524    /// ```
525    /// use conjure_cp_core::ast::{GroundDomain,Range,ReturnType};
526    /// use std::collections::BTreeSet;
527    ///
528    /// let elements = BTreeSet::from([]);
529    ///
530    /// let domain = GroundDomain::from_set_i32(&elements);
531    ///
532    /// assert!(matches!(domain,GroundDomain::Empty(ReturnType::Int)))
533    /// ```
534    pub fn from_set_i32(elements: &BTreeSet<i32>) -> GroundDomain {
535        if elements.is_empty() {
536            return GroundDomain::Empty(ReturnType::Int);
537        }
538        if elements.len() == 1 {
539            return GroundDomain::Int(vec![Range::Single(*elements.first().unwrap())]);
540        }
541
542        let mut elems_iter = elements.iter().copied();
543
544        let mut ranges: Vec<Range<i32>> = vec![];
545
546        // Loop over the elements in ascending order, turning all sequential runs of
547        // numbers into ranges.
548
549        // the bounds of the current run of numbers.
550        let mut lower = elems_iter
551            .next()
552            .expect("if we get here, elements should have => 2 elements");
553        let mut upper = lower;
554
555        for current in elems_iter {
556            // As elements is a BTreeSet, current is always strictly larger than lower.
557
558            if current == upper + 1 {
559                // current is part of the current run - we now have the run lower..current
560                //
561                upper = current;
562            } else {
563                // the run lower..upper has ended.
564                //
565                // Add the run lower..upper to the domain, and start a new run.
566
567                if lower == upper {
568                    ranges.push(range!(lower));
569                } else {
570                    ranges.push(range!(lower..upper));
571                }
572
573                lower = current;
574                upper = current;
575            }
576        }
577
578        // add the final run to the domain
579        if lower == upper {
580            ranges.push(range!(lower));
581        } else {
582            ranges.push(range!(lower..upper));
583        }
584
585        ranges = Range::squeeze(&ranges);
586        GroundDomain::Int(ranges)
587    }
588
589    /// Returns the domain that is the result of applying a binary operation to two integer domains.
590    ///
591    /// The given operator may return `None` if the operation is not defined for its arguments.
592    /// Undefined values will not be included in the resulting domain.
593    ///
594    /// # Errors
595    ///
596    /// - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.
597    /// - [`DomainOpError::NotInteger`] if either of the input domains are not integers.
598    pub fn apply_i32(
599        &self,
600        op: fn(i32, i32) -> Option<i32>,
601        other: &GroundDomain,
602    ) -> Result<GroundDomain, DomainOpError> {
603        let vs1 = self.values_i32()?;
604        let vs2 = other.values_i32()?;
605
606        let mut set = BTreeSet::new();
607        for (v1, v2) in itertools::iproduct!(vs1, vs2) {
608            if let Some(v) = op(v1, v2) {
609                set.insert(v);
610            }
611        }
612
613        Ok(GroundDomain::from_set_i32(&set))
614    }
615
616    /// Returns true if the domain is finite.
617    pub fn is_finite(&self) -> bool {
618        for domain in self.universe() {
619            if let GroundDomain::Int(ranges) = domain {
620                if ranges.is_empty() {
621                    return false;
622                }
623
624                if ranges.iter().any(|range| {
625                    matches!(
626                        range,
627                        Range::UnboundedL(_) | Range::UnboundedR(_) | Range::Unbounded
628                    )
629                }) {
630                    return false;
631                }
632            }
633        }
634        true
635    }
636
637    /// For a vector of literals, creates a domain that contains all the elements.
638    ///
639    /// The literals must all be of the same type.
640    ///
641    /// For abstract literals, this method merges the element domains of the literals, but not the
642    /// index domains. Thus, for fixed-sized abstract literals (matrices, tuples, records, etc.),
643    /// all literals in the vector must also have the same size / index domain:
644    ///
645    /// + Matrices: all literals must have the same index domain.
646    /// + Tuples: all literals must have the same number of elements.
647    /// + Records: all literals must have the same fields.
648    ///
649    /// # Errors
650    ///
651    /// - [DomainOpError::WrongType] if the input literals are of a different type to
652    ///   each-other, as described above.
653    ///
654    /// # Examples
655    ///
656    /// ```
657    /// use conjure_cp_core::ast::{Range, Literal, ReturnType, GroundDomain};
658    ///
659    /// let domain = GroundDomain::from_literal_vec(&vec![]);
660    /// assert_eq!(domain,Ok(GroundDomain::Empty(ReturnType::Unknown)));
661    /// ```
662    ///
663    /// ```
664    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};
665    /// use conjure_cp_core::{domain_int_ground, range, matrix};
666    ///
667    /// // `[1,2;int(2..3)], [4,5; int(2..3)]` has domain
668    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`
669    ///
670    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);
671    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(2..3)]);
672    ///
673    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
674    ///
675    /// let expected_domain = Ok(GroundDomain::Matrix(
676    ///     domain_int_ground!(1..2,4..5),vec![domain_int_ground!(2..3)]));
677    ///
678    /// assert_eq!(domain,expected_domain);
679    /// ```
680    ///
681    /// ```
682    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral,DomainOpError};
683    /// use conjure_cp_core::{domain_int_ground, range, matrix};
684    ///
685    /// // `[1,2;int(2..3)], [4,5; int(1..2)]` cannot be combined
686    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`
687    ///
688    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);
689    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]);
690    ///
691    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
692    ///
693    /// assert_eq!(domain,Err(DomainOpError::WrongType));
694    /// ```
695    ///
696    /// ```
697    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};
698    /// use conjure_cp_core::{domain_int_ground,range, matrix};
699    ///
700    /// // `[[1,2; int(1..2)];int(2)], [[4,5; int(1..2)]; int(2)]` has domain
701    /// // `matrix indexed by [int(2),int(1..2)] of int(1..2,4..5)`
702    ///
703    ///
704    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(1..2)]); domain_int_ground!(2)]);
705    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]); domain_int_ground!(2)]);
706    ///
707    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
708    ///
709    /// let expected_domain = Ok(GroundDomain::Matrix(
710    ///     domain_int_ground!(1..2,4..5),
711    ///     vec![domain_int_ground!(2),domain_int_ground!(1..2)]));
712    ///
713    /// assert_eq!(domain,expected_domain);
714    /// ```
715    ///
716    ///
717    pub fn from_literal_vec(literals: &[Literal]) -> Result<GroundDomain, DomainOpError> {
718        // TODO: use proptest to test this better?
719
720        if literals.is_empty() {
721            return Ok(GroundDomain::Empty(ReturnType::Unknown));
722        }
723
724        let first_literal = literals.first().unwrap();
725
726        match first_literal {
727            Literal::Int(_) => {
728                // check all literals are ints, then pass this to Domain::from_set_i32.
729                let mut ints = BTreeSet::new();
730                for lit in literals {
731                    let Literal::Int(i) = lit else {
732                        return Err(DomainOpError::WrongType);
733                    };
734
735                    ints.insert(*i);
736                }
737
738                Ok(GroundDomain::from_set_i32(&ints))
739            }
740            Literal::Bool(_) => {
741                // check all literals are bools
742                if literals.iter().any(|x| !matches!(x, Literal::Bool(_))) {
743                    Err(DomainOpError::WrongType)
744                } else {
745                    Ok(GroundDomain::Bool)
746                }
747            }
748            Literal::AbstractLiteral(AbstractLiteral::Set(_)) => {
749                let mut all_elems = vec![];
750
751                for lit in literals {
752                    let Literal::AbstractLiteral(AbstractLiteral::Set(elems)) = lit else {
753                        return Err(DomainOpError::WrongType);
754                    };
755
756                    all_elems.extend(elems.clone());
757                }
758                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
759
760                Ok(GroundDomain::Set(SetAttr::default(), Moo::new(elem_domain)))
761            }
762            Literal::AbstractLiteral(AbstractLiteral::MSet(_)) => {
763                let mut all_elems = vec![];
764
765                for lit in literals {
766                    let Literal::AbstractLiteral(AbstractLiteral::MSet(elems)) = lit else {
767                        return Err(DomainOpError::WrongType);
768                    };
769
770                    all_elems.extend(elems.clone());
771                }
772                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
773
774                Ok(GroundDomain::MSet(
775                    MSetAttr::default(),
776                    Moo::new(elem_domain),
777                ))
778            }
779            l @ Literal::AbstractLiteral(AbstractLiteral::Matrix(_, _)) => {
780                let mut first_index_domain = vec![];
781                // flatten index domains of n-d matrix into list
782                let mut l = l.clone();
783                while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {
784                    assert!(
785                        !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),
786                        "n-dimensional matrix literals should be represented as a matrix inside a matrix"
787                    );
788                    first_index_domain.push(idx);
789                    l = elems[0].clone();
790                }
791
792                let mut all_elems: Vec<Literal> = vec![];
793
794                // check types and index domains
795                for lit in literals {
796                    let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = lit else {
797                        return Err(DomainOpError::NotGround);
798                    };
799
800                    all_elems.extend(elems.clone());
801
802                    let mut index_domain = vec![idx.clone()];
803                    let mut l = elems[0].clone();
804                    while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {
805                        assert!(
806                            !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),
807                            "n-dimensional matrix literals should be represented as a matrix inside a matrix"
808                        );
809                        index_domain.push(idx);
810                        l = elems[0].clone();
811                    }
812
813                    if index_domain != first_index_domain {
814                        return Err(DomainOpError::WrongType);
815                    }
816                }
817
818                // extract all the terminal elements (those that are not nested matrix literals) from the matrix literal.
819                let mut terminal_elements: Vec<Literal> = vec![];
820                while let Some(elem) = all_elems.pop() {
821                    if let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, _)) = elem {
822                        all_elems.extend(elems);
823                    } else {
824                        terminal_elements.push(elem);
825                    }
826                }
827
828                let element_domain = GroundDomain::from_literal_vec(&terminal_elements)?;
829
830                Ok(GroundDomain::Matrix(
831                    Moo::new(element_domain),
832                    first_index_domain,
833                ))
834            }
835
836            Literal::AbstractLiteral(AbstractLiteral::Tuple(first_elems)) => {
837                let n_fields = first_elems.len();
838
839                // for each field, calculate the element domain and add it to this list
840                let mut elem_domains = vec![];
841
842                for i in 0..n_fields {
843                    let mut all_elems = vec![];
844                    for lit in literals {
845                        let Literal::AbstractLiteral(AbstractLiteral::Tuple(elems)) = lit else {
846                            return Err(DomainOpError::NotGround);
847                        };
848
849                        if elems.len() != n_fields {
850                            return Err(DomainOpError::NotGround);
851                        }
852
853                        all_elems.push(elems[i].clone());
854                    }
855
856                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));
857                }
858
859                Ok(GroundDomain::Tuple(elem_domains))
860            }
861
862            Literal::AbstractLiteral(AbstractLiteral::Record(first_elems)) => {
863                let n_fields = first_elems.len();
864                let field_names = first_elems.iter().map(|x| x.name.clone()).collect_vec();
865
866                // for each field, calculate the element domain and add it to this list
867                let mut elem_domains = vec![];
868
869                for i in 0..n_fields {
870                    let mut all_elems = vec![];
871                    for lit in literals {
872                        let Literal::AbstractLiteral(AbstractLiteral::Record(elems)) = lit else {
873                            return Err(DomainOpError::NotGround);
874                        };
875
876                        if elems.len() != n_fields {
877                            return Err(DomainOpError::NotGround);
878                        }
879
880                        let elem = elems[i].clone();
881                        if elem.name != field_names[i] {
882                            return Err(DomainOpError::NotGround);
883                        }
884
885                        all_elems.push(elem.value);
886                    }
887
888                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));
889                }
890
891                Ok(GroundDomain::Record(
892                    izip!(field_names, elem_domains)
893                        .map(|(name, domain)| RecordEntryGround { name, domain })
894                        .collect(),
895                ))
896            }
897            Literal::AbstractLiteral(AbstractLiteral::Function(items)) => {
898                if items.is_empty() {
899                    return Err(DomainOpError::NotGround);
900                }
901
902                let (x1, y1) = &items[0];
903                let d1 = x1.domain_of();
904                let d1 = d1.as_ground().ok_or(DomainOpError::NotGround)?;
905                let d2 = y1.domain_of();
906                let d2 = d2.as_ground().ok_or(DomainOpError::NotGround)?;
907
908                // Check that all items have the same domains
909                for (x, y) in items {
910                    let dx = x.domain_of();
911                    let dx = dx.as_ground().ok_or(DomainOpError::NotGround)?;
912
913                    let dy = y.domain_of();
914                    let dy = dy.as_ground().ok_or(DomainOpError::NotGround)?;
915
916                    if (dx != d1) || (dy != d2) {
917                        return Err(DomainOpError::WrongType);
918                    }
919                }
920
921                todo!();
922            }
923        }
924    }
925
926    pub fn element_domain(&self) -> Option<Moo<GroundDomain>> {
927        match self {
928            GroundDomain::Set(_, inner) => Some(inner.clone()),
929            GroundDomain::MSet(_, inner) => Some(inner.clone()),
930            GroundDomain::Matrix(_, _) => todo!("Unwrap one dimension of the domain"),
931            _ => None,
932        }
933    }
934}
935
936impl Typeable for GroundDomain {
937    fn return_type(&self) -> ReturnType {
938        match self {
939            GroundDomain::Empty(ty) => ty.clone(),
940            GroundDomain::Bool => ReturnType::Bool,
941            GroundDomain::Int(_) => ReturnType::Int,
942            GroundDomain::Set(_attr, inner) => ReturnType::Set(Box::new(inner.return_type())),
943            GroundDomain::MSet(_attr, inner) => ReturnType::MSet(Box::new(inner.return_type())),
944            GroundDomain::Matrix(inner, _idx) => ReturnType::Matrix(Box::new(inner.return_type())),
945            GroundDomain::Tuple(inners) => {
946                let mut inner_types = Vec::new();
947                for inner in inners {
948                    inner_types.push(inner.return_type());
949                }
950                ReturnType::Tuple(inner_types)
951            }
952            GroundDomain::Record(entries) => {
953                let mut entry_types = Vec::new();
954                for entry in entries {
955                    entry_types.push(entry.domain.return_type());
956                }
957                ReturnType::Record(entry_types)
958            }
959            GroundDomain::Function(_, dom, cdom) => {
960                ReturnType::Function(Box::new(dom.return_type()), Box::new(cdom.return_type()))
961            }
962        }
963    }
964}
965
966impl Display for GroundDomain {
967    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
968        match &self {
969            GroundDomain::Empty(ty) => write!(f, "empty({ty:?})"),
970            GroundDomain::Bool => write!(f, "bool"),
971            GroundDomain::Int(ranges) => {
972                if ranges.iter().all(Range::is_lower_or_upper_bounded) {
973                    let rngs: String = ranges.iter().map(|r| format!("{r}")).join(", ");
974                    write!(f, "int({})", rngs)
975                } else {
976                    write!(f, "int")
977                }
978            }
979            GroundDomain::Set(attrs, inner_dom) => write!(f, "set {attrs} of {inner_dom}"),
980            GroundDomain::MSet(attrs, inner_dom) => write!(f, "mset {attrs} of {inner_dom}"),
981            GroundDomain::Matrix(value_domain, index_domains) => {
982                write!(
983                    f,
984                    "matrix indexed by [{}] of {value_domain}",
985                    pretty_vec(&index_domains.iter().collect_vec())
986                )
987            }
988            GroundDomain::Tuple(domains) => {
989                write!(
990                    f,
991                    "tuple of ({})",
992                    pretty_vec(&domains.iter().collect_vec())
993                )
994            }
995            GroundDomain::Record(entries) => {
996                write!(
997                    f,
998                    "record of ({})",
999                    pretty_vec(
1000                        &entries
1001                            .iter()
1002                            .map(|entry| format!("{}: {}", entry.name, entry.domain))
1003                            .collect_vec()
1004                    )
1005                )
1006            }
1007            GroundDomain::Function(attribute, domain, codomain) => {
1008                write!(f, "function {} {} --> {} ", attribute, domain, codomain)
1009            }
1010        }
1011    }
1012}
conjure_cp_core/ast/domains/ground.rs

conjure_cp_core/ast/domains/
ground.rs
