conjure_cp_core/ast/domains/
ground.rs

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

conjure_cp_core/ast/domains/
ground.rs
