conjure_cp_core/ast/domains/
ground.rs

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

conjure_cp_core/ast/domains/
ground.rs
