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            GroundDomain::Matrix(elem_domain, index_domains) => Ok(Box::new(
218                enumerate_matrix_values(elem_domain.as_ref(), index_domains)?.into_iter(),
219            )),
220            _ => todo!("Enumerating nested domains is not yet supported"),
221        }
222    }
223
224    /// Gets the length of this domain.
225    ///
226    /// # Errors
227    ///
228    /// - [`DomainOpError::Unbounded`] if the input domain is of infinite size.
229    pub fn length(&self) -> Result<u64, DomainOpError> {
230        match self {
231            GroundDomain::Empty(_) => Ok(0),
232            GroundDomain::Bool => Ok(2),
233            GroundDomain::Int(ranges) => {
234                if ranges.is_empty() {
235                    return Err(DomainOpError::Unbounded);
236                }
237
238                let mut length = 0u64;
239                for range in ranges {
240                    if let Some(range_length) = range.length() {
241                        length += range_length as u64;
242                    } else {
243                        return Err(DomainOpError::Unbounded);
244                    }
245                }
246                Ok(length)
247            }
248            GroundDomain::Set(set_attr, inner_domain) => {
249                let inner_len = inner_domain.length()?;
250                let (min_sz, max_sz) = match set_attr.size {
251                    Range::Unbounded => (0, inner_len),
252                    Range::Single(n) => (n as u64, n as u64),
253                    Range::UnboundedR(n) => (n as u64, inner_len),
254                    Range::UnboundedL(n) => (0, n as u64),
255                    Range::Bounded(min, max) => (min as u64, max as u64),
256                };
257                let mut ans = 0u64;
258                for sz in min_sz..=max_sz {
259                    let c = count_combinations(inner_len, sz)?;
260                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;
261                }
262                Ok(ans)
263            }
264            GroundDomain::MSet(mset_attr, inner_domain) => {
265                let inner_len = inner_domain.length()?;
266                let (min_sz, max_sz) = match mset_attr.size {
267                    Range::Unbounded => (0, inner_len),
268                    Range::Single(n) => (n as u64, n as u64),
269                    Range::UnboundedR(n) => (n as u64, inner_len),
270                    Range::UnboundedL(n) => (0, n as u64),
271                    Range::Bounded(min, max) => (min as u64, max as u64),
272                };
273                let mut ans = 0u64;
274                for sz in min_sz..=max_sz {
275                    // need  "multichoose", ((n  k)) == (n+k-1  k)
276                    // Where n=inner_len and k=sz
277                    let c = count_combinations(inner_len + sz - 1, sz)?;
278                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;
279                }
280                Ok(ans)
281            }
282            GroundDomain::Tuple(domains) => {
283                let mut ans = 1u64;
284                for domain in domains {
285                    ans = ans
286                        .checked_mul(domain.length()?)
287                        .ok_or(DomainOpError::TooLarge)?;
288                }
289                Ok(ans)
290            }
291            GroundDomain::Record(entries) => {
292                // A record is just a named tuple
293                let mut ans = 1u64;
294                for entry in entries {
295                    let sz = entry.domain.length()?;
296                    ans = ans.checked_mul(sz).ok_or(DomainOpError::TooLarge)?;
297                }
298                Ok(ans)
299            }
300            GroundDomain::Matrix(inner_domain, idx_domains) => {
301                let inner_sz = inner_domain.length()?;
302                let exp = idx_domains.iter().try_fold(1u32, |acc, val| {
303                    let len = val.length()? as u32;
304                    acc.checked_mul(len).ok_or(DomainOpError::TooLarge)
305                })?;
306                inner_sz.checked_pow(exp).ok_or(DomainOpError::TooLarge)
307            }
308            GroundDomain::Function(_, _, _) => {
309                todo!("Length bound of functions is not yet supported")
310            }
311        }
312    }
313
314    pub fn contains(&self, lit: &Literal) -> Result<bool, DomainOpError> {
315        // not adding a generic wildcard condition for all domains, so that this gives a compile
316        // error when a domain is added.
317        match self {
318            // empty domain can't contain anything
319            GroundDomain::Empty(_) => Ok(false),
320            GroundDomain::Bool => match lit {
321                Literal::Bool(_) => Ok(true),
322                _ => Ok(false),
323            },
324            GroundDomain::Int(ranges) => match lit {
325                Literal::Int(x) => {
326                    // unconstrained int domain - contains all integers
327                    if ranges.is_empty() {
328                        return Ok(true);
329                    };
330
331                    Ok(ranges.iter().any(|range| range.contains(x)))
332                }
333                _ => Ok(false),
334            },
335            GroundDomain::Set(set_attr, inner_domain) => match lit {
336                Literal::AbstractLiteral(AbstractLiteral::Set(lit_elems)) => {
337                    // check if the literal's size is allowed by the set attribute
338                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
339                    if !set_attr.size.contains(&sz) {
340                        return Ok(false);
341                    }
342
343                    for elem in lit_elems {
344                        if !inner_domain.contains(elem)? {
345                            return Ok(false);
346                        }
347                    }
348                    Ok(true)
349                }
350                _ => Ok(false),
351            },
352            GroundDomain::MSet(mset_attr, inner_domain) => match lit {
353                Literal::AbstractLiteral(AbstractLiteral::MSet(lit_elems)) => {
354                    // check if the literal's size is allowed by the mset attribute
355                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;
356                    if !mset_attr.size.contains(&sz) {
357                        return Ok(false);
358                    }
359
360                    for elem in lit_elems {
361                        if !inner_domain.contains(elem)? {
362                            return Ok(false);
363                        }
364                    }
365                    Ok(true)
366                }
367                _ => Ok(false),
368            },
369            GroundDomain::Matrix(elem_domain, index_domains) => {
370                match lit {
371                    Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx_domain)) => {
372                        // Matrix literals are represented as nested 1d matrices, so the elements of
373                        // the matrix literal will be the inner dimensions of the matrix.
374
375                        let Some((current_index_domain, remaining_index_domains)) =
376                            index_domains.split_first()
377                        else {
378                            panic!("a matrix should have at least one index domain");
379                        };
380
381                        if *current_index_domain != *idx_domain {
382                            return Ok(false);
383                        };
384
385                        let next_elem_domain = if remaining_index_domains.is_empty() {
386                            // Base case - we have a 1D row. Now check if all elements in the
387                            // literal are in this row's element domain.
388                            elem_domain.as_ref().clone()
389                        } else {
390                            // Otherwise, go down a dimension (e.g. 2D matrix inside a 3D tensor)
391                            GroundDomain::Matrix(
392                                elem_domain.clone(),
393                                remaining_index_domains.to_vec(),
394                            )
395                        };
396
397                        for elem in elems {
398                            if !next_elem_domain.contains(elem)? {
399                                return Ok(false);
400                            }
401                        }
402
403                        Ok(true)
404                    }
405                    _ => Ok(false),
406                }
407            }
408            GroundDomain::Tuple(elem_domains) => {
409                match lit {
410                    Literal::AbstractLiteral(AbstractLiteral::Tuple(literal_elems)) => {
411                        if elem_domains.len() != literal_elems.len() {
412                            return Ok(false);
413                        }
414
415                        // for every element in the tuple literal, check if it is in the corresponding domain
416                        for (elem_domain, elem) in itertools::izip!(elem_domains, literal_elems) {
417                            if !elem_domain.contains(elem)? {
418                                return Ok(false);
419                            }
420                        }
421
422                        Ok(true)
423                    }
424                    _ => Ok(false),
425                }
426            }
427            GroundDomain::Record(entries) => match lit {
428                Literal::AbstractLiteral(AbstractLiteral::Record(lit_entries)) => {
429                    if entries.len() != lit_entries.len() {
430                        return Ok(false);
431                    }
432
433                    for (entry, lit_entry) in itertools::izip!(entries, lit_entries) {
434                        if entry.name != lit_entry.name
435                            || !(entry.domain.contains(&lit_entry.value)?)
436                        {
437                            return Ok(false);
438                        }
439                    }
440                    Ok(true)
441                }
442                _ => Ok(false),
443            },
444            GroundDomain::Function(func_attr, domain, codomain) => match lit {
445                Literal::AbstractLiteral(AbstractLiteral::Function(lit_elems)) => {
446                    let sz = Int::try_from(lit_elems.len()).expect("Should convert");
447                    if !func_attr.size.contains(&sz) {
448                        return Ok(false);
449                    }
450                    for lit in lit_elems {
451                        let domain_element = &lit.0;
452                        let codomain_element = &lit.1;
453                        if !domain.contains(domain_element)? {
454                            return Ok(false);
455                        }
456                        if !codomain.contains(codomain_element)? {
457                            return Ok(false);
458                        }
459                    }
460                    Ok(true)
461                }
462                _ => Ok(false),
463            },
464        }
465    }
466
467    /// Returns a list of all possible values in an integer domain.
468    ///
469    /// # Errors
470    ///
471    /// - [`DomainOpError::NotInteger`] if the domain is not an integer domain.
472    /// - [`DomainOpError::Unbounded`] if the domain is unbounded.
473    pub fn values_i32(&self) -> Result<Vec<i32>, DomainOpError> {
474        if let GroundDomain::Empty(ReturnType::Int) = self {
475            return Ok(vec![]);
476        }
477        let GroundDomain::Int(ranges) = self else {
478            return Err(DomainOpError::NotInteger(self.return_type()));
479        };
480
481        if ranges.is_empty() {
482            return Err(DomainOpError::Unbounded);
483        }
484
485        let mut values = vec![];
486        for range in ranges {
487            match range {
488                Range::Single(i) => {
489                    values.push(*i);
490                }
491                Range::Bounded(i, j) => {
492                    values.extend(*i..=*j);
493                }
494                Range::UnboundedR(_) | Range::UnboundedL(_) | Range::Unbounded => {
495                    return Err(DomainOpError::Unbounded);
496                }
497            }
498        }
499
500        Ok(values)
501    }
502
503    /// Creates an [`Domain::Int`] containing the given integers.
504    ///
505    /// # Examples
506    ///
507    /// ```
508    /// use conjure_cp_core::ast::{GroundDomain, Range};
509    /// use conjure_cp_core::{domain_int_ground,range};
510    /// use std::collections::BTreeSet;
511    ///
512    /// let elements = BTreeSet::from([1,2,3,4,5]);
513    ///
514    /// let domain = GroundDomain::from_set_i32(&elements);
515    ///
516    /// assert_eq!(domain,domain_int_ground!(1..5));
517    /// ```
518    ///
519    /// ```
520    /// use conjure_cp_core::ast::{GroundDomain,Range};
521    /// use conjure_cp_core::{domain_int_ground,range};
522    /// use std::collections::BTreeSet;
523    ///
524    /// let elements = BTreeSet::from([1,2,4,5,7,8,9,10]);
525    ///
526    /// let domain = GroundDomain::from_set_i32(&elements);
527    ///
528    /// assert_eq!(domain,domain_int_ground!(1..2,4..5,7..10));
529    /// ```
530    ///
531    /// ```
532    /// use conjure_cp_core::ast::{GroundDomain,Range,ReturnType};
533    /// use std::collections::BTreeSet;
534    ///
535    /// let elements = BTreeSet::from([]);
536    ///
537    /// let domain = GroundDomain::from_set_i32(&elements);
538    ///
539    /// assert!(matches!(domain,GroundDomain::Empty(ReturnType::Int)))
540    /// ```
541    pub fn from_set_i32(elements: &BTreeSet<i32>) -> GroundDomain {
542        if elements.is_empty() {
543            return GroundDomain::Empty(ReturnType::Int);
544        }
545        if elements.len() == 1 {
546            return GroundDomain::Int(vec![Range::Single(*elements.first().unwrap())]);
547        }
548
549        let mut elems_iter = elements.iter().copied();
550
551        let mut ranges: Vec<Range<i32>> = vec![];
552
553        // Loop over the elements in ascending order, turning all sequential runs of
554        // numbers into ranges.
555
556        // the bounds of the current run of numbers.
557        let mut lower = elems_iter
558            .next()
559            .expect("if we get here, elements should have => 2 elements");
560        let mut upper = lower;
561
562        for current in elems_iter {
563            // As elements is a BTreeSet, current is always strictly larger than lower.
564
565            if current == upper + 1 {
566                // current is part of the current run - we now have the run lower..current
567                //
568                upper = current;
569            } else {
570                // the run lower..upper has ended.
571                //
572                // Add the run lower..upper to the domain, and start a new run.
573
574                if lower == upper {
575                    ranges.push(range!(lower));
576                } else {
577                    ranges.push(range!(lower..upper));
578                }
579
580                lower = current;
581                upper = current;
582            }
583        }
584
585        // add the final run to the domain
586        if lower == upper {
587            ranges.push(range!(lower));
588        } else {
589            ranges.push(range!(lower..upper));
590        }
591
592        ranges = Range::squeeze(&ranges);
593        GroundDomain::Int(ranges)
594    }
595
596    /// Returns the domain that is the result of applying a binary operation to two integer domains.
597    ///
598    /// The given operator may return `None` if the operation is not defined for its arguments.
599    /// Undefined values will not be included in the resulting domain.
600    ///
601    /// # Errors
602    ///
603    /// - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.
604    /// - [`DomainOpError::NotInteger`] if either of the input domains are not integers.
605    pub fn apply_i32(
606        &self,
607        op: fn(i32, i32) -> Option<i32>,
608        other: &GroundDomain,
609    ) -> Result<GroundDomain, DomainOpError> {
610        let vs1 = self.values_i32()?;
611        let vs2 = other.values_i32()?;
612
613        let mut set = BTreeSet::new();
614        for (v1, v2) in itertools::iproduct!(vs1, vs2) {
615            if let Some(v) = op(v1, v2) {
616                set.insert(v);
617            }
618        }
619
620        Ok(GroundDomain::from_set_i32(&set))
621    }
622
623    /// Returns true if the domain is finite.
624    pub fn is_finite(&self) -> bool {
625        for domain in self.universe() {
626            if let GroundDomain::Int(ranges) = domain {
627                if ranges.is_empty() {
628                    return false;
629                }
630
631                if ranges.iter().any(|range| {
632                    matches!(
633                        range,
634                        Range::UnboundedL(_) | Range::UnboundedR(_) | Range::Unbounded
635                    )
636                }) {
637                    return false;
638                }
639            }
640        }
641        true
642    }
643
644    /// For a vector of literals, creates a domain that contains all the elements.
645    ///
646    /// The literals must all be of the same type.
647    ///
648    /// For abstract literals, this method merges the element domains of the literals, but not the
649    /// index domains. Thus, for fixed-sized abstract literals (matrices, tuples, records, etc.),
650    /// all literals in the vector must also have the same size / index domain:
651    ///
652    /// + Matrices: all literals must have the same index domain.
653    /// + Tuples: all literals must have the same number of elements.
654    /// + Records: all literals must have the same fields.
655    ///
656    /// # Errors
657    ///
658    /// - [DomainOpError::WrongType] if the input literals are of a different type to
659    ///   each-other, as described above.
660    ///
661    /// # Examples
662    ///
663    /// ```
664    /// use conjure_cp_core::ast::{Range, Literal, ReturnType, GroundDomain};
665    ///
666    /// let domain = GroundDomain::from_literal_vec(&vec![]);
667    /// assert_eq!(domain,Ok(GroundDomain::Empty(ReturnType::Unknown)));
668    /// ```
669    ///
670    /// ```
671    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};
672    /// use conjure_cp_core::{domain_int_ground, range, matrix};
673    ///
674    /// // `[1,2;int(2..3)], [4,5; int(2..3)]` has domain
675    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`
676    ///
677    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);
678    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(2..3)]);
679    ///
680    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
681    ///
682    /// let expected_domain = Ok(GroundDomain::Matrix(
683    ///     domain_int_ground!(1..2,4..5),vec![domain_int_ground!(2..3)]));
684    ///
685    /// assert_eq!(domain,expected_domain);
686    /// ```
687    ///
688    /// ```
689    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral,DomainOpError};
690    /// use conjure_cp_core::{domain_int_ground, range, matrix};
691    ///
692    /// // `[1,2;int(2..3)], [4,5; int(1..2)]` cannot be combined
693    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`
694    ///
695    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);
696    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]);
697    ///
698    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
699    ///
700    /// assert_eq!(domain,Err(DomainOpError::WrongType));
701    /// ```
702    ///
703    /// ```
704    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};
705    /// use conjure_cp_core::{domain_int_ground,range, matrix};
706    ///
707    /// // `[[1,2; int(1..2)];int(2)], [[4,5; int(1..2)]; int(2)]` has domain
708    /// // `matrix indexed by [int(2),int(1..2)] of int(1..2,4..5)`
709    ///
710    ///
711    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(1..2)]); domain_int_ground!(2)]);
712    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]); domain_int_ground!(2)]);
713    ///
714    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);
715    ///
716    /// let expected_domain = Ok(GroundDomain::Matrix(
717    ///     domain_int_ground!(1..2,4..5),
718    ///     vec![domain_int_ground!(2),domain_int_ground!(1..2)]));
719    ///
720    /// assert_eq!(domain,expected_domain);
721    /// ```
722    ///
723    ///
724    pub fn from_literal_vec(literals: &[Literal]) -> Result<GroundDomain, DomainOpError> {
725        // TODO: use proptest to test this better?
726
727        if literals.is_empty() {
728            return Ok(GroundDomain::Empty(ReturnType::Unknown));
729        }
730
731        let first_literal = literals.first().unwrap();
732
733        match first_literal {
734            Literal::Int(_) => {
735                // check all literals are ints, then pass this to Domain::from_set_i32.
736                let mut ints = BTreeSet::new();
737                for lit in literals {
738                    let Literal::Int(i) = lit else {
739                        return Err(DomainOpError::WrongType);
740                    };
741
742                    ints.insert(*i);
743                }
744
745                Ok(GroundDomain::from_set_i32(&ints))
746            }
747            Literal::Bool(_) => {
748                // check all literals are bools
749                if literals.iter().any(|x| !matches!(x, Literal::Bool(_))) {
750                    Err(DomainOpError::WrongType)
751                } else {
752                    Ok(GroundDomain::Bool)
753                }
754            }
755            Literal::AbstractLiteral(AbstractLiteral::Set(_)) => {
756                let mut all_elems = vec![];
757
758                for lit in literals {
759                    let Literal::AbstractLiteral(AbstractLiteral::Set(elems)) = lit else {
760                        return Err(DomainOpError::WrongType);
761                    };
762
763                    all_elems.extend(elems.clone());
764                }
765                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
766
767                Ok(GroundDomain::Set(SetAttr::default(), Moo::new(elem_domain)))
768            }
769            Literal::AbstractLiteral(AbstractLiteral::MSet(_)) => {
770                let mut all_elems = vec![];
771
772                for lit in literals {
773                    let Literal::AbstractLiteral(AbstractLiteral::MSet(elems)) = lit else {
774                        return Err(DomainOpError::WrongType);
775                    };
776
777                    all_elems.extend(elems.clone());
778                }
779                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;
780
781                Ok(GroundDomain::MSet(
782                    MSetAttr::default(),
783                    Moo::new(elem_domain),
784                ))
785            }
786            l @ Literal::AbstractLiteral(AbstractLiteral::Matrix(_, _)) => {
787                let mut first_index_domain = vec![];
788                // flatten index domains of n-d matrix into list
789                let mut l = l.clone();
790                while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {
791                    assert!(
792                        !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),
793                        "n-dimensional matrix literals should be represented as a matrix inside a matrix"
794                    );
795                    first_index_domain.push(idx);
796                    l = elems[0].clone();
797                }
798
799                let mut all_elems: Vec<Literal> = vec![];
800
801                // check types and index domains
802                for lit in literals {
803                    let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = lit else {
804                        return Err(DomainOpError::NotGround);
805                    };
806
807                    all_elems.extend(elems.clone());
808
809                    let mut index_domain = vec![idx.clone()];
810                    let mut l = elems[0].clone();
811                    while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {
812                        assert!(
813                            !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),
814                            "n-dimensional matrix literals should be represented as a matrix inside a matrix"
815                        );
816                        index_domain.push(idx);
817                        l = elems[0].clone();
818                    }
819
820                    if index_domain != first_index_domain {
821                        return Err(DomainOpError::WrongType);
822                    }
823                }
824
825                // extract all the terminal elements (those that are not nested matrix literals) from the matrix literal.
826                let mut terminal_elements: Vec<Literal> = vec![];
827                while let Some(elem) = all_elems.pop() {
828                    if let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, _)) = elem {
829                        all_elems.extend(elems);
830                    } else {
831                        terminal_elements.push(elem);
832                    }
833                }
834
835                let element_domain = GroundDomain::from_literal_vec(&terminal_elements)?;
836
837                Ok(GroundDomain::Matrix(
838                    Moo::new(element_domain),
839                    first_index_domain,
840                ))
841            }
842
843            Literal::AbstractLiteral(AbstractLiteral::Tuple(first_elems)) => {
844                let n_fields = first_elems.len();
845
846                // for each field, calculate the element domain and add it to this list
847                let mut elem_domains = vec![];
848
849                for i in 0..n_fields {
850                    let mut all_elems = vec![];
851                    for lit in literals {
852                        let Literal::AbstractLiteral(AbstractLiteral::Tuple(elems)) = lit else {
853                            return Err(DomainOpError::NotGround);
854                        };
855
856                        if elems.len() != n_fields {
857                            return Err(DomainOpError::NotGround);
858                        }
859
860                        all_elems.push(elems[i].clone());
861                    }
862
863                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));
864                }
865
866                Ok(GroundDomain::Tuple(elem_domains))
867            }
868
869            Literal::AbstractLiteral(AbstractLiteral::Record(first_elems)) => {
870                let n_fields = first_elems.len();
871                let field_names = first_elems.iter().map(|x| x.name.clone()).collect_vec();
872
873                // for each field, calculate the element domain and add it to this list
874                let mut elem_domains = vec![];
875
876                for i in 0..n_fields {
877                    let mut all_elems = vec![];
878                    for lit in literals {
879                        let Literal::AbstractLiteral(AbstractLiteral::Record(elems)) = lit else {
880                            return Err(DomainOpError::NotGround);
881                        };
882
883                        if elems.len() != n_fields {
884                            return Err(DomainOpError::NotGround);
885                        }
886
887                        let elem = elems[i].clone();
888                        if elem.name != field_names[i] {
889                            return Err(DomainOpError::NotGround);
890                        }
891
892                        all_elems.push(elem.value);
893                    }
894
895                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));
896                }
897
898                Ok(GroundDomain::Record(
899                    izip!(field_names, elem_domains)
900                        .map(|(name, domain)| RecordEntryGround { name, domain })
901                        .collect(),
902                ))
903            }
904            Literal::AbstractLiteral(AbstractLiteral::Function(items)) => {
905                if items.is_empty() {
906                    return Err(DomainOpError::NotGround);
907                }
908
909                let (x1, y1) = &items[0];
910                let d1 = x1.domain_of();
911                let d1 = d1.as_ground().ok_or(DomainOpError::NotGround)?;
912                let d2 = y1.domain_of();
913                let d2 = d2.as_ground().ok_or(DomainOpError::NotGround)?;
914
915                // Check that all items have the same domains
916                for (x, y) in items {
917                    let dx = x.domain_of();
918                    let dx = dx.as_ground().ok_or(DomainOpError::NotGround)?;
919
920                    let dy = y.domain_of();
921                    let dy = dy.as_ground().ok_or(DomainOpError::NotGround)?;
922
923                    if (dx != d1) || (dy != d2) {
924                        return Err(DomainOpError::WrongType);
925                    }
926                }
927
928                todo!();
929            }
930        }
931    }
932
933    pub fn element_domain(&self) -> Option<Moo<GroundDomain>> {
934        match self {
935            GroundDomain::Set(_, inner) => Some(inner.clone()),
936            GroundDomain::MSet(_, inner) => Some(inner.clone()),
937            GroundDomain::Matrix(_, _) => todo!("Unwrap one dimension of the domain"),
938            _ => None,
939        }
940    }
941}
942
943impl Typeable for GroundDomain {
944    fn return_type(&self) -> ReturnType {
945        match self {
946            GroundDomain::Empty(ty) => ty.clone(),
947            GroundDomain::Bool => ReturnType::Bool,
948            GroundDomain::Int(_) => ReturnType::Int,
949            GroundDomain::Set(_attr, inner) => ReturnType::Set(Box::new(inner.return_type())),
950            GroundDomain::MSet(_attr, inner) => ReturnType::MSet(Box::new(inner.return_type())),
951            GroundDomain::Matrix(inner, _idx) => ReturnType::Matrix(Box::new(inner.return_type())),
952            GroundDomain::Tuple(inners) => {
953                let mut inner_types = Vec::new();
954                for inner in inners {
955                    inner_types.push(inner.return_type());
956                }
957                ReturnType::Tuple(inner_types)
958            }
959            GroundDomain::Record(entries) => {
960                let mut entry_types = Vec::new();
961                for entry in entries {
962                    entry_types.push(entry.domain.return_type());
963                }
964                ReturnType::Record(entry_types)
965            }
966            GroundDomain::Function(_, dom, cdom) => {
967                ReturnType::Function(Box::new(dom.return_type()), Box::new(cdom.return_type()))
968            }
969        }
970    }
971}
972
973impl Display for GroundDomain {
974    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
975        match &self {
976            GroundDomain::Empty(ty) => write!(f, "empty({ty:?})"),
977            GroundDomain::Bool => write!(f, "bool"),
978            GroundDomain::Int(ranges) => {
979                if ranges.iter().all(Range::is_lower_or_upper_bounded) {
980                    let rngs: String = ranges.iter().map(|r| format!("{r}")).join(", ");
981                    write!(f, "int({})", rngs)
982                } else {
983                    write!(f, "int")
984                }
985            }
986            GroundDomain::Set(attrs, inner_dom) => write!(f, "set {attrs} of {inner_dom}"),
987            GroundDomain::MSet(attrs, inner_dom) => write!(f, "mset {attrs} of {inner_dom}"),
988            GroundDomain::Matrix(value_domain, index_domains) => {
989                write!(
990                    f,
991                    "matrix indexed by {} of {value_domain}",
992                    pretty_vec(&index_domains.iter().collect_vec())
993                )
994            }
995            GroundDomain::Tuple(domains) => {
996                write!(
997                    f,
998                    "tuple of ({})",
999                    pretty_vec(&domains.iter().collect_vec())
1000                )
1001            }
1002            GroundDomain::Record(entries) => {
1003                write!(
1004                    f,
1005                    "record of ({})",
1006                    pretty_vec(
1007                        &entries
1008                            .iter()
1009                            .map(|entry| format!("{}: {}", entry.name, entry.domain))
1010                            .collect_vec()
1011                    )
1012                )
1013            }
1014            GroundDomain::Function(attribute, domain, codomain) => {
1015                write!(f, "function {} {} --> {} ", attribute, domain, codomain)
1016            }
1017        }
1018    }
1019}
1020
1021fn enumerate_matrix_values(
1022    elem_domain: &GroundDomain,
1023    index_domains: &[Moo<GroundDomain>],
1024) -> Result<Vec<Literal>, DomainOpError> {
1025    let Some((current_index_domain, remaining_index_domains)) = index_domains.split_first() else {
1026        panic!("a matrix should have at least one index domain");
1027    };
1028
1029    let current_dimension_len =
1030        usize::try_from(current_index_domain.length()?).map_err(|_| DomainOpError::TooLarge)?;
1031
1032    let entry_values = if remaining_index_domains.is_empty() {
1033        elem_domain.values()?.collect_vec()
1034    } else {
1035        enumerate_matrix_values(elem_domain, remaining_index_domains)?
1036    };
1037
1038    Ok((0..current_dimension_len)
1039        .map(|_| entry_values.iter().cloned())
1040        .multi_cartesian_product()
1041        .map(|elems| {
1042            Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, current_index_domain.clone()))
1043        })
1044        .collect())
1045}
conjure_cp_core/ast/domains/ground.rs

conjure_cp_core/ast/domains/
ground.rs
