Grcov report - ground.rs

1

use crate::ast::domains::attrs::PartitionAttr;

2

use crate::ast::domains::{MSetAttr, SequenceAttr};

3

use crate::ast::pretty::pretty_vec;

4

use crate::ast::{

5

    AbstractLiteral, DomainOpError, FuncAttr, HasDomain, Literal, Moo, Name, RelAttr, SetAttr,

6

    Typeable,

7

    domains::{domain::Int, range::Range},

8

    matrix,

9

    records::Field,

10

};

11

use crate::range;

12

use crate::utils::count_combinations;

13

use conjure_cp_core::ast::ReturnType;

14

use funcmap::FuncMap;

15

use itertools::{Itertools, izip};

16

use num_traits::ToPrimitive;

17

use polyquine::Quine;

18

use serde::{Deserialize, Serialize};

19

use std::collections::{BTreeMap, BTreeSet};

20

use std::fmt::{Display, Formatter};

21

use std::iter::zip;

22

use uniplate::Uniplate;

23

24

pub(super) type FieldGround = Field<Moo<GroundDomain>>;

25

26

#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize, Quine, Uniplate)]

27

#[path_prefix(conjure_cp::ast)]

28

pub enum GroundDomain {

29

    /// An empty domain of a given type

30

    Empty(ReturnType),

31

    /// A boolean value (true / false)

32

    Bool,

33

    /// An integer value in the given ranges (e.g. int(1, 3..5))

34

    Int(Vec<Range<Int>>),

35

    /// A set of elements drawn from the inner domain

36

    Set(SetAttr<Int>, Moo<GroundDomain>),

37

    /// A multiset of elements drawn from the inner domain

38

    MSet(MSetAttr<Int>, Moo<GroundDomain>),

39

    /// An N-dimensional matrix of elements drawn from the inner domain,

40

    /// and indices from the n index domains

41

    Matrix(Moo<GroundDomain>, Vec<Moo<GroundDomain>>),

42

    /// A tuple of N elements, each with its own domain

43

    Tuple(Vec<Moo<GroundDomain>>),

44

    /// A record

45

    Record(Vec<FieldGround>),

46

    /// A Partition

47

    Partition(PartitionAttr, Moo<GroundDomain>),

48

    /// A sequence of elements drawn from the inner domain

49

    Sequence(SequenceAttr, Moo<GroundDomain>),

50

    /// A function with a domain and codomain

51

    Function(FuncAttr, Moo<GroundDomain>, Moo<GroundDomain>),

52

    /// A relation as a set of tuples

53

    Relation(RelAttr, Vec<Moo<GroundDomain>>),

54

    /// A variant domain with its domain options (reusing field entries)

55

    Variant(Vec<FieldGround>),

56

57

58

impl GroundDomain {

59

1583320

    pub fn union(&self, other: &GroundDomain) -> Result<GroundDomain, DomainOpError> {

60

1583320

        match (self, other) {

61

            (GroundDomain::Empty(ty), dom) | (dom, GroundDomain::Empty(ty)) => {

62

                if *ty == dom.return_type() {

63

                    Ok(dom.clone())

64

                } else {

65

                    Err(DomainOpError::WrongType)

66

67

68

800

            (GroundDomain::Bool, GroundDomain::Bool) => Ok(GroundDomain::Bool),

69

            (GroundDomain::Bool, _) | (_, GroundDomain::Bool) => Err(DomainOpError::WrongType),

70

1506200

            (GroundDomain::Int(r1), GroundDomain::Int(r2)) => {

71

1506200

                let mut rngs = r1.clone();

72

1506200

                rngs.extend(r2.clone());

73

1506200

                Ok(GroundDomain::Int(Range::squeeze(&rngs)))

74

75

            (GroundDomain::Int(_), _) | (_, GroundDomain::Int(_)) => Err(DomainOpError::WrongType),

76

112

            (GroundDomain::Set(_, in1), GroundDomain::Set(_, in2)) => Ok(GroundDomain::Set(

77

112

                SetAttr::default(),

78

112

                Moo::new(in1.union(in2)?),

79

)),

80

            (GroundDomain::Set(_, _), _) | (_, GroundDomain::Set(_, _)) => {

81

                Err(DomainOpError::WrongType)

82

83

            (GroundDomain::MSet(_, in1), GroundDomain::MSet(_, in2)) => Ok(GroundDomain::MSet(

84

                MSetAttr::default(),

85

                Moo::new(in1.union(in2)?),

86

)),

87

76208

            (GroundDomain::Matrix(in1, idx1), GroundDomain::Matrix(in2, idx2)) if idx1 == idx2 => {

88

                Ok(GroundDomain::Matrix(

89

76208

                    Moo::new(in1.union(in2)?),

90

76208

                    idx1.clone(),

91

))

92

93

            (GroundDomain::Matrix(_, _), _) | (_, GroundDomain::Matrix(_, _)) => {

94

                Err(DomainOpError::WrongType)

95

96

            (GroundDomain::Tuple(in1s), GroundDomain::Tuple(in2s)) if in1s.len() == in2s.len() => {

97

                let mut inners = Vec::new();

98

                for (in1, in2) in zip(in1s, in2s) {

99

                    inners.push(Moo::new(in1.union(in2)?));

100

101

                Ok(GroundDomain::Tuple(inners))

102

103

            (GroundDomain::Tuple(_), _) | (_, GroundDomain::Tuple(_)) => {

104

                Err(DomainOpError::WrongType)

105

106

            (GroundDomain::Record(in1s), GroundDomain::Record(in2s))

107

                if in1s.len() == in2s.len() =>

108

109

                let lhs_fields: BTreeMap<&Name, &Moo<GroundDomain>> =

110

                    in1s.iter().map(|x| (&x.name, &x.value)).collect();

111

                let rhs_fields: BTreeMap<&Name, &Moo<GroundDomain>> =

112

                    in2s.iter().map(|x| (&x.name, &x.value)).collect();

113

                let mut new_fields = Vec::with_capacity(in1s.len());

114

                for (n, d) in lhs_fields {

115

                    let d2 = rhs_fields.get(&n).ok_or(DomainOpError::WrongType)?;

116

                    let dom = d.union(d2)?;

117

                    new_fields.push(Field {

118

                        name: n.clone(),

119

                        value: dom.into(),

120

});

121

122

                Ok(GroundDomain::Record(new_fields))

123

124

            (GroundDomain::Record(_), _) | (_, GroundDomain::Record(_)) => {

125

                Err(DomainOpError::WrongType)

126

127

            (GroundDomain::Relation(_, in1s), GroundDomain::Relation(_, in2s)) => {

128

                let mut inners = Vec::new();

129

                for (in1, in2) in zip(in1s, in2s) {

130

                    inners.push(Moo::new(in1.union(in2)?));

131

132

                Ok(GroundDomain::Tuple(inners))

133

134

            (GroundDomain::Relation(..), _) | (_, GroundDomain::Relation(..)) => {

135

                Err(DomainOpError::WrongType)

136

137

            #[allow(unreachable_patterns)]

138

            (GroundDomain::Sequence(_, _), _) | (_, GroundDomain::Sequence(_, _)) => {

139

                todo!("union sequence domains")

140

141

            #[allow(unreachable_patterns)]

142

            (GroundDomain::Variant(_), _) | (_, GroundDomain::Variant(_)) => {

143

                todo!("union variant domains")

144

145

            #[allow(unreachable_patterns)]

146

            (GroundDomain::Function(..), _) | (_, GroundDomain::Function(..)) => {

147

                todo!("union function domains")

148

149

            #[allow(unreachable_patterns)]

150

            (GroundDomain::Partition(..), _) | (_, GroundDomain::Partition(..)) => {

151

                todo!("union partition domains")

152

153

154

1583320

155

156

    /// Calculates the intersection of two domains.

157

///

158

    /// # Errors

159

///

160

    ///  - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.

161

    ///  - [`DomainOpError::WrongType`] if the input domains are different types, or are not integer or set domains.

162

46468

    pub fn intersect(&self, other: &GroundDomain) -> Result<GroundDomain, DomainOpError> {

163

        // TODO: does not consider unbounded domains yet

164

        // needs to be tested once comprehension rules are written

165

166

46468

        match (self, other) {

167

            // one or more arguments is an empty int domain

168

            (d @ GroundDomain::Empty(ReturnType::Int), GroundDomain::Int(_)) => Ok(d.clone()),

169

            (GroundDomain::Int(_), d @ GroundDomain::Empty(ReturnType::Int)) => Ok(d.clone()),

170

            (GroundDomain::Empty(ReturnType::Int), d @ GroundDomain::Empty(ReturnType::Int)) => {

171

                Ok(d.clone())

172

173

174

            // one or more arguments is an empty set(int) domain

175

            (GroundDomain::Set(_, inner1), d @ GroundDomain::Empty(ReturnType::Set(inner2)))

176

                if matches!(

177

                    **inner1,

178

                    GroundDomain::Int(_) | GroundDomain::Empty(ReturnType::Int)

179

                ) && matches!(**inner2, ReturnType::Int) =>

180

181

                Ok(d.clone())

182

183

            (d @ GroundDomain::Empty(ReturnType::Set(inner1)), GroundDomain::Set(_, inner2))

184

                if matches!(**inner1, ReturnType::Int)

185

                    && matches!(

186

                        **inner2,

187

                        GroundDomain::Int(_) | GroundDomain::Empty(ReturnType::Int)

188

                    ) =>

189

190

                Ok(d.clone())

191

192

193

                d @ GroundDomain::Empty(ReturnType::Set(inner1)),

194

                GroundDomain::Empty(ReturnType::Set(inner2)),

195

            ) if matches!(**inner1, ReturnType::Int) && matches!(**inner2, ReturnType::Int) => {

196

                Ok(d.clone())

197

198

199

            // both arguments are non-empy

200

100

            (GroundDomain::Set(_, x), GroundDomain::Set(_, y)) => Ok(GroundDomain::Set(

201

100

                SetAttr::default(),

202

100

                Moo::new((*x).intersect(y)?),

203

)),

204

205

            (GroundDomain::Int(_), GroundDomain::Int(_)) => {

206

43624

                let mut v: BTreeSet<i32> = BTreeSet::new();

207

208

43624

                let v1 = self.values_i32()?;

209

43624

                let v2 = other.values_i32()?;

210

198252

                for value1 in v1.iter() {

211

198252

                    if v2.contains(value1) && !v.contains(value1) {

212

125552

                        v.insert(*value1);

213

125552

214

215

43624

                Ok(GroundDomain::from_set_i32(&v))

216

217

            (GroundDomain::Relation(_, _), GroundDomain::Relation(_, _)) => {

218

                todo!("Relation union not yet supported")

219

220

2744

            _ => Err(DomainOpError::WrongType),

221

222

46468

223

224

1096756

    pub fn values(&self) -> Result<Box<dyn Iterator<Item = Literal>>, DomainOpError> {

225

1096756

        match self {

226

            GroundDomain::Empty(_) => Ok(Box::new(vec![].into_iter())),

227

2667

            GroundDomain::Bool => Ok(Box::new(

228

2667

                vec![Literal::from(false), Literal::from(true)].into_iter(),

229

2667

)),

230

1090856

            GroundDomain::Int(rngs) => {

231

1090856

                let rng_iters = rngs

232

1090856

                    .iter()

233

1090856

                    .map(Range::iter)

234

1090856

                    .collect::<Option<Vec<_>>>()

235

1090856

                    .ok_or(DomainOpError::Unbounded)?;

236

1090856

                Ok(Box::new(

237

1091816

                    rng_iters.into_iter().flat_map(|ri| ri.map(Literal::from)),

238

))

239

240

3224

            GroundDomain::Matrix(elem_dom, idx_doms) => {

241

3224

                let shape = matrix::shape_of_dom(self)?;

242

3224

                let idx_doms = idx_doms.clone();

243

244

                // Collect all possible element values

245

3224

                let elem_values: Vec<Literal> = elem_dom.values()?.collect();

246

247

                // Generate all possible cell assignments in lexicographic order

248

3224

                let iter = std::iter::repeat_n(elem_values, shape.size)

249

3224

                    .multi_cartesian_product()

250

6472

                    .map(move |flat_elems| {

251

6472

                        matrix::unflatten_matrix::<Literal>(&flat_elems, &idx_doms, &shape.strides)

252

6472

});

253

254

3224

                Ok(Box::new(iter))

255

256

3

            GroundDomain::Tuple(elem_doms) => {

257

                // Collect the possible values for each element

258

3

                let elem_value_pools: Vec<Vec<Literal>> = elem_doms

259

3

                    .iter()

260

7

                    .map(|d| d.values().map(|it| it.collect()))

261

3

                    .collect::<Result<_, _>>()?;

262

263

                // Generate all combinations in lexicographic order

264

3

                let iter = elem_value_pools

265

3

                    .into_iter()

266

3

                    .multi_cartesian_product()

267

22

                    .map(|elems| Literal::AbstractLiteral(AbstractLiteral::Tuple(elems)));

268

269

3

                Ok(Box::new(iter))

270

271

2

            GroundDomain::Record(entries) => {

272

                // Sort entries by name

273

2

                let mut sorted: Vec<&_> = entries.iter().collect();

274

2

                sorted.sort_by(|a, b| a.name.cmp(&b.name));

275

276

4

                let names: Vec<_> = sorted.iter().map(|e| e.name.clone()).collect();

277

2

                let value_pools: Vec<Vec<Literal>> = sorted

278

2

                    .iter()

279

4

                    .map(|e| e.value.values().map(|it| it.collect()))

280

2

                    .collect::<Result<_, _>>()?;

281

282

                // Generate all combinations in lexicographic order

283

2

                let iter = value_pools

284

2

                    .into_iter()

285

2

                    .multi_cartesian_product()

286

10

                    .map(move |vals| {

287

10

                        let record_entries = names

288

10

                            .iter()

289

10

                            .cloned()

290

10

                            .zip(vals)

291

20

                            .map(|(name, value)| Field { name, value })

292

10

                            .collect();

293

10

                        Literal::AbstractLiteral(AbstractLiteral::Record(record_entries))

294

10

});

295

296

2

                Ok(Box::new(iter))

297

298

4

            GroundDomain::Set(attrs, inner_dom) => {

299

4

                let n: Int = inner_dom.len_usize()?.try_into()?;

300

4

                let min_sz = attrs.size.low().copied().unwrap_or(0);

301

4

                let max_sz = attrs.size.high().copied().unwrap_or(n);

302

303

4

                let pool = inner_dom.values()?.collect_vec();

304

305

4

                Ok(Box::new(

306

4

                    (min_sz..=max_sz)

307

12

                        .flat_map(move |sz| pool.clone().into_iter().combinations(sz as usize))

308

33

                        .map(|elems| Literal::AbstractLiteral(AbstractLiteral::Set(elems))),

309

))

310

311

            GroundDomain::MSet(..) => todo!("Enumerating multi-set domains is not yet supported"),

312

            GroundDomain::Function(..) => {

313

                todo!("Enumerating function domains is not yet supported")

314

315

            GroundDomain::Partition(..) => {

316

                todo!("Enumerating partition domains is not yet supported")

317

318

            GroundDomain::Relation(..) => {

319

                todo!("Enumerating relation domains is not yet supported")

320

321

            GroundDomain::Sequence(..) => {

322

                todo!("Enumerating sequence domains is not yet supported")

323

324

            GroundDomain::Variant(..) => {

325

                todo!("Enumerating variant domains is not yet supported")

326

327

328

1096756

329

330

    /// Gets the length of this domain.

331

///

332

    /// # Errors

333

///

334

    /// - [`DomainOpError::Unbounded`] if the input domain is of infinite size.

335

7061

    pub fn length(&self) -> Result<u64, DomainOpError> {

336

7061

        match self {

337

1

            GroundDomain::Empty(_) => Ok(0),

338

12

            GroundDomain::Bool => Ok(2),

339

7026

            GroundDomain::Int(ranges) => {

340

7026

                if ranges.is_empty() {

341

                    return Err(DomainOpError::Unbounded);

342

7026

343

344

7026

                let mut length = 0u64;

345

7029

                for range in ranges {

346

7029

                    if let Some(range_length) = range.length() {

347

7027

                        length += range_length as u64;

348

7027

                    } else {

349

2

                        return Err(DomainOpError::Unbounded);

350

351

352

7024

                Ok(length)

353

354

13

            GroundDomain::Set(set_attr, inner_domain) => {

355

13

                let inner_len = inner_domain.length()?;

356

11

                let (min_sz, max_sz) = match set_attr.size {

357

6

                    Range::Unbounded => (0, inner_len),

358

1

                    Range::Single(n) => (n as u64, n as u64),

359

1

                    Range::UnboundedR(n) => (n as u64, inner_len),

360

2

                    Range::UnboundedL(n) => (0, n as u64),

361

1

                    Range::Bounded(min, max) => (min as u64, max as u64),

362

};

363

11

                let mut ans = 0u64;

364

78

                for sz in min_sz..=max_sz {

365

78

                    let c = count_combinations(inner_len, sz)?;

366

77

                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;

367

368

10

                Ok(ans)

369

370

            GroundDomain::MSet(mset_attr, inner_domain) => {

371

                let inner_len = inner_domain.length()?;

372

                let (min_sz, max_sz) = match mset_attr.size {

373

                    Range::Unbounded => (0, inner_len),

374

                    Range::Single(n) => (n as u64, n as u64),

375

                    Range::UnboundedR(n) => (n as u64, inner_len),

376

                    Range::UnboundedL(n) => (0, n as u64),

377

                    Range::Bounded(min, max) => (min as u64, max as u64),

378

};

379

                let mut ans = 0u64;

380

                for sz in min_sz..=max_sz {

381

                    // need  "multichoose", ((n  k)) == (n+k-1  k)

382

                    // Where n=inner_len and k=sz

383

                    let c = count_combinations(inner_len + sz - 1, sz)?;

384

                    ans = ans.checked_add(c).ok_or(DomainOpError::TooLarge)?;

385

386

                Ok(ans)

387

388

            GroundDomain::Sequence(_, _) => {

389

                // If jectivity is not set, the sequence can have any permutation.

390

//

391

                todo!("Length bound currently not supported");

392

393

2

            GroundDomain::Tuple(domains) => {

394

2

                let mut ans = 1u64;

395

5

                for domain in domains {

396

5

                    ans = ans

397

5

                        .checked_mul(domain.length()?)

398

5

                        .ok_or(DomainOpError::TooLarge)?;

399

400

2

                Ok(ans)

401

402

2

            GroundDomain::Record(entries) => {

403

                // A record is just a named tuple

404

2

                let mut ans = 1u64;

405

4

                for entry in entries {

406

4

                    let sz = entry.value.length()?;

407

4

                    ans = ans.checked_mul(sz).ok_or(DomainOpError::TooLarge)?;

408

409

2

                Ok(ans)

410

411

5

            GroundDomain::Matrix(inner_domain, idx_domains) => {

412

5

                let inner_sz = inner_domain.length()?;

413

6

                let exp = idx_domains.iter().try_fold(1u32, |acc, val| {

414

6

                    let len = val.length()? as u32;

415

6

                    acc.checked_mul(len).ok_or(DomainOpError::TooLarge)

416

6

                })?;

417

5

                inner_sz.checked_pow(exp).ok_or(DomainOpError::TooLarge)

418

419

            GroundDomain::Function(_, _, _) => {

420

                todo!("Length bound of functions is not yet supported")

421

422

            GroundDomain::Variant(entries) => {

423

                let mut ans = 1u64;

424

                for entry in entries {

425

                    let sz = entry.value.length()?;

426

                    // Only one field can be in the variant at once

427

                    ans = ans.checked_add(sz).ok_or(DomainOpError::TooLarge)?;

428

429

                Ok(ans)

430

431

            GroundDomain::Relation(_, domains) => {

432

                // Cannot currently use attributes to better infer length because of i32 u64 mismatch

433

                let dom_sizes_result: Result<Vec<u64>, DomainOpError> =

434

                    domains.iter().map(|x| x.length()).collect();

435

                let dom_sizes = dom_sizes_result?;

436

                Ok(dom_sizes.iter().product())

437

438

            GroundDomain::Partition(_, _) => {

439

                todo!("Length bound of Partitions is not yet supported")

440

441

442

7061

443

444

    /// Get size of this domain as a [usize]

445

3229

    pub fn len_usize(&self) -> Result<usize, DomainOpError> {

446

3229

        self.length()?

447

3229

            .try_into()

448

3229

            .map_err(|_| DomainOpError::TooLarge)

449

3229

450

451

797996

    pub fn contains(&self, lit: &Literal) -> Result<bool, DomainOpError> {

452

        // not adding a generic wildcard condition for all domains, so that this gives a compile

453

        // error when a domain is added.

454

797996

        match self {

455

            // empty domain can't contain anything

456

            GroundDomain::Empty(_) => Ok(false),

457

176776

            GroundDomain::Bool => match lit {

458

176768

                Literal::Bool(_) => Ok(true),

459

8

                _ => Ok(false),

460

},

461

616892

            GroundDomain::Int(ranges) => match lit {

462

616892

                Literal::Int(x) => {

463

                    // unconstrained int domain - contains all integers

464

616892

                    if ranges.is_empty() {

465

156

                        return Ok(true);

466

616736

};

467

468

617888

                    Ok(ranges.iter().any(|range| range.contains(x)))

469

470

                _ => Ok(false),

471

},

472

480

            GroundDomain::Set(set_attr, inner_domain) => match lit {

473

320

                Literal::AbstractLiteral(AbstractLiteral::Set(lit_elems)) => {

474

                    // check if the literal's size is allowed by the set attribute

475

320

                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;

476

320

                    if !set_attr.size.contains(&sz) {

477

                        return Ok(false);

478

320

479

480

640

                    for elem in lit_elems {

481

640

                        if !inner_domain.contains(elem)? {

482

160

                            return Ok(false);

483

480

484

485

160

                    Ok(true)

486

487

160

                _ => Ok(false),

488

},

489

            GroundDomain::MSet(mset_attr, inner_domain) => match lit {

490

                Literal::AbstractLiteral(AbstractLiteral::MSet(lit_elems)) => {

491

                    // check if the literal's size is allowed by the mset attribute

492

                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;

493

                    if !mset_attr.size.contains(&sz) {

494

                        return Ok(false);

495

496

497

                    for elem in lit_elems {

498

                        if !inner_domain.contains(elem)? {

499

                            return Ok(false);

500

501

502

                    Ok(true)

503

504

                _ => Ok(false),

505

},

506

            GroundDomain::Sequence(seq_attr, inner_dom) => match lit {

507

                Literal::AbstractLiteral(AbstractLiteral::Sequence(elems)) => {

508

                    let sz = elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;

509

                    if !seq_attr.size.contains(&sz) {

510

                        return Ok(false);

511

512

513

                    for elem in elems {

514

                        if !inner_dom.contains(elem)? {

515

                            return Ok(false);

516

517

518

                    Ok(true)

519

520

                _ => Ok(false),

521

},

522

488

            GroundDomain::Matrix(elem_domain, index_domains) => {

523

436

                match lit {

524

436

                    Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx_domain)) => {

525

                        // Matrix literals are represented as nested 1d matrices, so the elements of

526

                        // the matrix literal will be the inner dimensions of the matrix.

527

528

436

                        let Some((current_index_domain, remaining_index_domains)) =

529

436

                            index_domains.split_first()

530

                        else {

531

                            panic!("a matrix should have at least one index domain");

532

};

533

534

436

                        if *current_index_domain != *idx_domain {

535

                            return Ok(false);

536

436

};

537

538

436

                        let next_elem_domain = if remaining_index_domains.is_empty() {

539

                            // Base case - we have a 1D row. Now check if all elements in the

540

                            // literal are in this row's element domain.

541

396

                            elem_domain.as_ref().clone()

542

                        } else {

543

                            // Otherwise, go down a dimension (e.g. 2D matrix inside a 3D tensor)

544

40

                            GroundDomain::Matrix(

545

40

                                elem_domain.clone(),

546

40

                                remaining_index_domains.to_vec(),

547

40

548

};

549

550

2092

                        for elem in elems {

551

2092

                            if !next_elem_domain.contains(elem)? {

552

                                return Ok(false);

553

2092

554

555

556

436

                        Ok(true)

557

558

52

                    _ => Ok(false),

559

560

561

1120

            GroundDomain::Tuple(elem_domains) => {

562

1120

                match lit {

563

1120

                    Literal::AbstractLiteral(AbstractLiteral::Tuple(literal_elems)) => {

564

1120

                        if elem_domains.len() != literal_elems.len() {

565

                            return Ok(false);

566

1120

567

568

                        // for every element in the tuple literal, check if it is in the corresponding domain

569

2240

                        for (elem_domain, elem) in itertools::izip!(elem_domains, literal_elems) {

570

2240

                            if !elem_domain.contains(elem)? {

571

                                return Ok(false);

572

2240

573

574

575

1120

                        Ok(true)

576

577

                    _ => Ok(false),

578

579

580

2240

            GroundDomain::Record(entries) => match lit {

581

2240

                Literal::AbstractLiteral(AbstractLiteral::Record(lit_entries)) => {

582

2240

                    if entries.len() != lit_entries.len() {

583

                        return Ok(false);

584

2240

585

586

4480

                    for (entry, lit_entry) in itertools::izip!(entries, lit_entries) {

587

4480

                        if entry.name != lit_entry.name

588

4480

                            || !(entry.value.contains(&lit_entry.value)?)

589

590

                            return Ok(false);

591

4480

592

593

2240

                    Ok(true)

594

595

                _ => Ok(false),

596

},

597

            GroundDomain::Function(func_attr, domain, codomain) => match lit {

598

                Literal::AbstractLiteral(AbstractLiteral::Function(lit_elems)) => {

599

                    let sz = Int::try_from(lit_elems.len()).expect("Should convert");

600

                    if !func_attr.size.contains(&sz) {

601

                        return Ok(false);

602

603

                    for lit in lit_elems {

604

                        let domain_element = &lit.0;

605

                        let codomain_element = &lit.1;

606

                        if !domain.contains(domain_element)? {

607

                            return Ok(false);

608

609

                        if !codomain.contains(codomain_element)? {

610

                            return Ok(false);

611

612

613

                    Ok(true)

614

615

                _ => Ok(false),

616

},

617

            GroundDomain::Variant(entries) => match lit {

618

                Literal::AbstractLiteral(AbstractLiteral::Variant(lit_entry)) => {

619

                    for entry in entries {

620

                        if entry.name == lit_entry.name

621

                            && !(entry.value.contains(&lit_entry.value)?)

622

623

                            return Ok(true);

624

625

626

                    Ok(false)

627

628

                _ => Ok(false),

629

},

630

            GroundDomain::Relation(rel_attr, inner_domains) => match lit {

631

                Literal::AbstractLiteral(AbstractLiteral::Relation(lit_elems)) => {

632

                    // check if the literal's size is allowed by the attributes

633

                    let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;

634

                    if !rel_attr.size.contains(&sz) {

635

                        return Ok(false);

636

637

638

                    for elem_tuple in lit_elems {

639

                        if elem_tuple.len() == inner_domains.len() {

640

                            for (elem, inner_dom) in elem_tuple.iter().zip(inner_domains.iter()) {

641

                                if !inner_dom.contains(elem)? {

642

                                    return Ok(false);

643

644

645

                        } else {

646

                            return Ok(false);

647

648

649

                    Ok(true)

650

651

                _ => Ok(false),

652

},

653

            GroundDomain::Partition(attr, dom) => match lit {

654

                Literal::AbstractLiteral(AbstractLiteral::Partition(lit_elems)) => {

655

                    // let sz = lit_elems.len().to_i32().ok_or(DomainOpError::TooLarge)?;

656

                    let sz: i32 = lit_elems

657

                        .iter()

658

                        .flatten()

659

                        .count()

660

                        .to_i32()

661

                        .ok_or(DomainOpError::TooLarge)?;

662

663

                    let min: Option<i32> = match (attr.num_parts.low(), attr.part_len.low()) {

664

                        (Some(x), Some(y)) => Some(x * y),

665

                        _ => None,

666

};

667

668

                    let max: Option<i32> = match (attr.num_parts.high(), attr.part_len.high()) {

669

                        (Some(x), Some(y)) => Some(x * y),

670

                        _ => None,

671

};

672

673

                    let rng = Range::new(min, max);

674

                    if rng.contains(&sz) {

675

                        return Ok(false);

676

677

678

                    for elem in lit_elems.iter().flatten() {

679

                        if !dom.contains(elem)? {

680

                            return Ok(false);

681

682

683

                    Ok(true)

684

685

                _ => Ok(false),

686

},

687

688

797996

689

690

    /// Returns a list of all possible values in an integer domain.

691

///

692

    /// # Errors

693

///

694

    /// - [`DomainOpError::NotInteger`] if the domain is not an integer domain.

695

    /// - [`DomainOpError::Unbounded`] if the domain is unbounded.

696

957464

    pub fn values_i32(&self) -> Result<Vec<i32>, DomainOpError> {

697

        if let GroundDomain::Empty(ReturnType::Int) = self {

698

            return Ok(vec![]);

699

957464

700

957464

        let GroundDomain::Int(ranges) = self else {

701

            return Err(DomainOpError::NotInteger(self.return_type()));

702

};

703

704

957464

        if ranges.is_empty() {

705

            return Err(DomainOpError::Unbounded);

706

957464

707

708

957464

        let mut values = vec![];

709

978404

        for range in ranges {

710

978404

            match range {

711

411084

                Range::Single(i) => {

712

411084

                    values.push(*i);

713

411084

714

567320

                Range::Bounded(i, j) => {

715

567320

                    values.extend(*i..=*j);

716

567320

717

                Range::UnboundedR(_) | Range::UnboundedL(_) | Range::Unbounded => {

718

                    return Err(DomainOpError::Unbounded);

719

720

721

722

723

957464

        Ok(values)

724

957464

725

726

    /// Creates an [`Domain::Int`] containing the given integers.

727

///

728

    /// # Examples

729

///

730

    /// ```

731

    /// use conjure_cp_core::ast::{GroundDomain, Range};

732

    /// use conjure_cp_core::{domain_int_ground,range};

733

    /// use std::collections::BTreeSet;

734

///

735

    /// let elements = BTreeSet::from([1,2,3,4,5]);

736

///

737

    /// let domain = GroundDomain::from_set_i32(&elements);

738

///

739

    /// assert_eq!(domain,domain_int_ground!(1..5));

740

    /// ```

741

///

742

    /// ```

743

    /// use conjure_cp_core::ast::{GroundDomain,Range};

744

    /// use conjure_cp_core::{domain_int_ground,range};

745

    /// use std::collections::BTreeSet;

746

///

747

    /// let elements = BTreeSet::from([1,2,4,5,7,8,9,10]);

748

///

749

    /// let domain = GroundDomain::from_set_i32(&elements);

750

///

751

    /// assert_eq!(domain,domain_int_ground!(1..2,4..5,7..10));

752

    /// ```

753

///

754

    /// ```

755

    /// use conjure_cp_core::ast::{GroundDomain,Range,ReturnType};

756

    /// use std::collections::BTreeSet;

757

///

758

    /// let elements = BTreeSet::from([]);

759

///

760

    /// let domain = GroundDomain::from_set_i32(&elements);

761

///

762

    /// assert!(matches!(domain,GroundDomain::Empty(ReturnType::Int)))

763

    /// ```

764

488588

    pub fn from_set_i32(elements: &BTreeSet<i32>) -> GroundDomain {

765

488588

        if elements.is_empty() {

766

20

            return GroundDomain::Empty(ReturnType::Int);

767

488568

768

488568

        if elements.len() == 1 {

769

3052

            return GroundDomain::Int(vec![Range::Single(*elements.first().unwrap())]);

770

485516

771

772

485516

        let mut elems_iter = elements.iter().copied();

773

774

485516

        let mut ranges: Vec<Range<i32>> = vec![];

775

776

        // Loop over the elements in ascending order, turning all sequential runs of

777

        // numbers into ranges.

778

779

        // the bounds of the current run of numbers.

780

485516

        let mut lower = elems_iter

781

485516

            .next()

782

485516

            .expect("if we get here, elements should have => 2 elements");

783

485516

        let mut upper = lower;

784

785

1117947

        for current in elems_iter {

786

            // As elements is a BTreeSet, current is always strictly larger than lower.

787

788

1117947

            if current == upper + 1 {

789

                // current is part of the current run - we now have the run lower..current

790

//

791

1009582

                upper = current;

792

1009582

            } else {

793

                // the run lower..upper has ended.

794

//

795

                // Add the run lower..upper to the domain, and start a new run.

796

797

108365

                if lower == upper {

798

93460

                    ranges.push(range!(lower));

799

93461

                } else {

800

14905

                    ranges.push(range!(lower..upper));

801

14905

802

803

108365

                lower = current;

804

108365

                upper = current;

805

806

807

808

        // add the final run to the domain

809

485516

        if lower == upper {

810

19189

            ranges.push(range!(lower));

811

466327

        } else {

812

466327

            ranges.push(range!(lower..upper));

813

466327

814

815

485516

        ranges = Range::squeeze(&ranges);

816

485516

        GroundDomain::Int(ranges)

817

488588

818

819

    /// Returns the domain that is the result of applying a binary operation to two integer domains.

820

///

821

    /// The given operator may return `None` if the operation is not defined for its arguments.

822

    /// Undefined values will not be included in the resulting domain.

823

///

824

    /// # Errors

825

///

826

    /// - [`DomainOpError::Unbounded`] if either of the input domains are unbounded.

827

    /// - [`DomainOpError::NotInteger`] if either of the input domains are not integers.

828

418966

    pub fn apply_i32(

829

418966

        &self,

830

418966

        op: fn(i32, i32) -> Option<i32>,

831

418966

        other: &GroundDomain,

832

418966

    ) -> Result<GroundDomain, DomainOpError> {

833

418966

        let vs1 = self.values_i32()?;

834

418966

        let vs2 = other.values_i32()?;

835

836

418966

        let mut set = BTreeSet::new();

837

3539372

        for (v1, v2) in itertools::iproduct!(vs1, vs2) {

838

3539372

            if let Some(v) = op(v1, v2) {

839

3357728

                set.insert(v);

840

3357728

841

842

843

418966

        Ok(GroundDomain::from_set_i32(&set))

844

418966

845

846

    /// Returns true if the domain is finite.

847

32164

    pub fn is_finite(&self) -> bool {

848

53532

        for domain in self.universe() {

849

53532

            if let GroundDomain::Int(ranges) = domain {

850

44044

                if ranges.is_empty() {

851

                    return false;

852

44044

853

854

45844

                if ranges.iter().any(|range| {

855

45844

                    matches!(

856

45844

                        range,

857

                        Range::UnboundedL(_) | Range::UnboundedR(_) | Range::Unbounded

858

859

45844

                }) {

860

                    return false;

861

44044

862

9488

863

864

32164

        true

865

32164

866

867

    /// For a vector of literals, creates a domain that contains all the elements.

868

///

869

    /// The literals must all be of the same type.

870

///

871

    /// For abstract literals, this method merges the element domains of the literals, but not the

872

    /// index domains. Thus, for fixed-sized abstract literals (matrices, tuples, records, etc.),

873

    /// all literals in the vector must also have the same size / index domain:

874

///

875

    /// + Matrices: all literals must have the same index domain.

876

    /// + Tuples: all literals must have the same number of elements.

877

    /// + Records: all literals must have the same fields.

878

///

879

    /// # Errors

880

///

881

    /// - [DomainOpError::WrongType] if the input literals are of a different type to

882

    ///   each-other, as described above.

883

///

884

    /// # Examples

885

///

886

    /// ```

887

    /// use conjure_cp_core::ast::{Range, Literal, ReturnType, GroundDomain};

888

///

889

    /// let domain = GroundDomain::from_literal_vec(&vec![]);

890

    /// assert_eq!(domain,Ok(GroundDomain::Empty(ReturnType::Unknown)));

891

    /// ```

892

///

893

    /// ```

894

    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};

895

    /// use conjure_cp_core::{domain_int_ground, range, matrix};

896

///

897

    /// // `[1,2;int(2..3)], [4,5; int(2..3)]` has domain

898

    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`

899

///

900

    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);

901

    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(2..3)]);

902

///

903

    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);

904

///

905

    /// let expected_domain = Ok(GroundDomain::Matrix(

906

    ///     domain_int_ground!(1..2,4..5),vec![domain_int_ground!(2..3)]));

907

///

908

    /// assert_eq!(domain,expected_domain);

909

    /// ```

910

///

911

    /// ```

912

    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral,DomainOpError};

913

    /// use conjure_cp_core::{domain_int_ground, range, matrix};

914

///

915

    /// // `[1,2;int(2..3)], [4,5; int(1..2)]` cannot be combined

916

    /// // `matrix indexed by [int(2..3)] of int(1..2,4..5)`

917

///

918

    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(2..3)]);

919

    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]);

920

///

921

    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);

922

///

923

    /// assert_eq!(domain,Err(DomainOpError::WrongType));

924

    /// ```

925

///

926

    /// ```

927

    /// use conjure_cp_core::ast::{GroundDomain,Range,Literal, AbstractLiteral};

928

    /// use conjure_cp_core::{domain_int_ground,range, matrix};

929

///

930

    /// // `[[1,2; int(1..2)];int(2)], [[4,5; int(1..2)]; int(2)]` has domain

931

    /// // `matrix indexed by [int(2),int(1..2)] of int(1..2,4..5)`

932

///

933

///

934

    /// let matrix_1 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(1),Literal::Int(2);domain_int_ground!(1..2)]); domain_int_ground!(2)]);

935

    /// let matrix_2 = Literal::AbstractLiteral(matrix![Literal::AbstractLiteral(matrix![Literal::Int(4),Literal::Int(5);domain_int_ground!(1..2)]); domain_int_ground!(2)]);

936

///

937

    /// let domain = GroundDomain::from_literal_vec(&vec![matrix_1,matrix_2]);

938

///

939

    /// let expected_domain = Ok(GroundDomain::Matrix(

940

    ///     domain_int_ground!(1..2,4..5),

941

    ///     vec![domain_int_ground!(2),domain_int_ground!(1..2)]));

942

///

943

    /// assert_eq!(domain,expected_domain);

944

    /// ```

945

///

946

///

947

51996

    pub fn from_literal_vec(literals: &[Literal]) -> Result<GroundDomain, DomainOpError> {

948

        // TODO: use proptest to test this better?

949

950

51996

        if literals.is_empty() {

951

20

            return Ok(GroundDomain::Empty(ReturnType::Unknown));

952

51976

953

954

51976

        let first_literal = literals.first().unwrap();

955

956

25798

        match first_literal {

957

            Literal::Int(_) => {

958

                // check all literals are ints, then pass this to Domain::from_set_i32.

959

25938

                let mut ints = BTreeSet::new();

960

96324

                for lit in literals {

961

96324

                    let Literal::Int(i) = lit else {

962

                        return Err(DomainOpError::WrongType);

963

};

964

965

96324

                    ints.insert(*i);

966

967

968

25938

                Ok(GroundDomain::from_set_i32(&ints))

969

970

            Literal::Bool(_) => {

971

                // check all literals are bools

972

240

                if literals.iter().any(|x| !matches!(x, Literal::Bool(_))) {

973

                    Err(DomainOpError::WrongType)

974

                } else {

975

240

                    Ok(GroundDomain::Bool)

976

977

978

            Literal::AbstractLiteral(AbstractLiteral::Set(_)) => {

979

12

                let mut all_elems = vec![];

980

981

12

                for lit in literals {

982

12

                    let Literal::AbstractLiteral(AbstractLiteral::Set(elems)) = lit else {

983

                        return Err(DomainOpError::WrongType);

984

};

985

986

12

                    all_elems.extend(elems.clone());

987

988

12

                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;

989

990

12

                Ok(GroundDomain::Set(SetAttr::default(), Moo::new(elem_domain)))

991

992

            Literal::AbstractLiteral(AbstractLiteral::MSet(_)) => {

993

                let mut all_elems = vec![];

994

995

                for lit in literals {

996

                    let Literal::AbstractLiteral(AbstractLiteral::MSet(elems)) = lit else {

997

                        return Err(DomainOpError::WrongType);

998

};

999

1000

                    all_elems.extend(elems.clone());

1001

1002

                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;

1003

1004

                Ok(GroundDomain::MSet(

1005

                    MSetAttr::default(),

1006

                    Moo::new(elem_domain),

1007

))

1008

1009

            Literal::AbstractLiteral(AbstractLiteral::Partition(_)) => {

1010

                todo!("Need to figure out how this is going to work")

1011

1012

25386

            l @ Literal::AbstractLiteral(AbstractLiteral::Matrix(_, _)) => {

1013

25386

                let mut first_index_domain = vec![];

1014

                // flatten index domains of n-d matrix into list

1015

25386

                let mut l = l.clone();

1016

25407

                while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {

1017

25407

                    assert!(

1018

25407

                        !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),

1019

                        "n-dimensional matrix literals should be represented as a matrix inside a matrix"

1020

);

1021

25407

                    first_index_domain.push(idx);

1022

25407

                    l = elems[0].clone();

1023

1024

1025

25386

                let mut all_elems: Vec<Literal> = vec![];

1026

1027

                // check types and index domains

1028

25446

                for lit in literals {

1029

25446

                    let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = lit else {

1030

                        return Err(DomainOpError::NotGround);

1031

};

1032

1033

25446

                    all_elems.extend(elems.clone());

1034

1035

25446

                    let mut index_domain = vec![idx.clone()];

1036

25446

                    let mut l = elems[0].clone();

1037

41

                    while let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, idx)) = l {

1038

41

                        assert!(

1039

41

                            !matches!(idx.as_ref(), GroundDomain::Matrix(_, _)),

1040

                            "n-dimensional matrix literals should be represented as a matrix inside a matrix"

1041

);

1042

41

                        index_domain.push(idx);

1043

41

                        l = elems[0].clone();

1044

1045

1046

25446

                    if index_domain != first_index_domain {

1047

20

                        return Err(DomainOpError::WrongType);

1048

25426

1049

1050

1051

                // extract all the terminal elements (those that are not nested matrix literals) from the matrix literal.

1052

25366

                let mut terminal_elements: Vec<Literal> = vec![];

1053

121156

                while let Some(elem) = all_elems.pop() {

1054

42

                    if let Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, _)) = elem {

1055

42

                        all_elems.extend(elems);

1056

95748

                    } else {

1057

95748

                        terminal_elements.push(elem);

1058

95748

1059

1060

1061

25366

                let element_domain = GroundDomain::from_literal_vec(&terminal_elements)?;

1062

1063

25366

                Ok(GroundDomain::Matrix(

1064

25366

                    Moo::new(element_domain),

1065

25366

                    first_index_domain,

1066

25366

))

1067

1068

1069

160

            Literal::AbstractLiteral(AbstractLiteral::Tuple(first_elems)) => {

1070

160

                let n_fields = first_elems.len();

1071

1072

                // for each field, calculate the element domain and add it to this list

1073

160

                let mut elem_domains = vec![];

1074

1075

320

                for i in 0..n_fields {

1076

320

                    let mut all_elems = vec![];

1077

320

                    for lit in literals {

1078

320

                        let Literal::AbstractLiteral(AbstractLiteral::Tuple(elems)) = lit else {

1079

                            return Err(DomainOpError::NotGround);

1080

};

1081

1082

320

                        if elems.len() != n_fields {

1083

                            return Err(DomainOpError::NotGround);

1084

320

1085

1086

320

                        all_elems.push(elems[i].clone());

1087

1088

1089

320

                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));

1090

1091

1092

160

                Ok(GroundDomain::Tuple(elem_domains))

1093

1094

1095

            Literal::AbstractLiteral(AbstractLiteral::Sequence(_)) => {

1096

                let mut all_elems = vec![];

1097

1098

                for lit in literals {

1099

                    let Literal::AbstractLiteral(AbstractLiteral::Sequence(elems)) = lit else {

1100

                        return Err(DomainOpError::WrongType);

1101

};

1102

1103

                    all_elems.extend(elems.clone());

1104

1105

                let elem_domain = GroundDomain::from_literal_vec(&all_elems)?;

1106

1107

                Ok(GroundDomain::Sequence(

1108

                    SequenceAttr::default(),

1109

                    Moo::new(elem_domain),

1110

))

1111

1112

1113

240

            Literal::AbstractLiteral(AbstractLiteral::Record(first_elems)) => {

1114

240

                let n_fields = first_elems.len();

1115

480

                let field_names = first_elems.iter().map(|x| x.name.clone()).collect_vec();

1116

1117

                // for each field, calculate the element domain and add it to this list

1118

240

                let mut elem_domains = vec![];

1119

1120

480

                for i in 0..n_fields {

1121

480

                    let mut all_elems = vec![];

1122

480

                    for lit in literals {

1123

480

                        let Literal::AbstractLiteral(AbstractLiteral::Record(elems)) = lit else {

1124

                            return Err(DomainOpError::NotGround);

1125

};

1126

1127

480

                        if elems.len() != n_fields {

1128

                            return Err(DomainOpError::NotGround);

1129

480

1130

1131

480

                        let elem = elems[i].clone();

1132

480

                        if elem.name != field_names[i] {

1133

                            return Err(DomainOpError::NotGround);

1134

480

1135

1136

480

                        all_elems.push(elem.value);

1137

1138

1139

480

                    elem_domains.push(Moo::new(GroundDomain::from_literal_vec(&all_elems)?));

1140

1141

1142

                Ok(GroundDomain::Record(

1143

240

                    izip!(field_names, elem_domains)

1144

480

                        .map(|(name, value)| FieldGround { name, value })

1145

240

                        .collect(),

1146

))

1147

1148

            Literal::AbstractLiteral(AbstractLiteral::Function(items)) => {

1149

                if items.is_empty() {

1150

                    return Err(DomainOpError::NotGround);

1151

1152

1153

                let (x1, y1) = &items[0];

1154

                let d1 = x1.domain_of();

1155

                let d1 = d1.as_ground().ok_or(DomainOpError::NotGround)?;

1156

                let d2 = y1.domain_of();

1157

                let d2 = d2.as_ground().ok_or(DomainOpError::NotGround)?;

1158

1159

                // Check that all items have the same domains

1160

                for (x, y) in items {

1161

                    let dx = x.domain_of();

1162

                    let dx = dx.as_ground().ok_or(DomainOpError::NotGround)?;

1163

1164

                    let dy = y.domain_of();

1165

                    let dy = dy.as_ground().ok_or(DomainOpError::NotGround)?;

1166

1167

                    if (dx != d1) || (dy != d2) {

1168

                        return Err(DomainOpError::WrongType);

1169

1170

1171

1172

                todo!();

1173

1174

            Literal::AbstractLiteral(AbstractLiteral::Variant(_)) => {

1175

                todo!();

1176

1177

            Literal::AbstractLiteral(AbstractLiteral::Relation(_)) => {

1178

                todo!();

1179

1180

1181

51996

1182

1183

40

    pub fn element_domain(&self) -> Option<Moo<GroundDomain>> {

1184

40

        match self {

1185

40

            GroundDomain::Set(_, inner) => Some(inner.clone()),

1186

            GroundDomain::MSet(_, inner) => Some(inner.clone()),

1187

            GroundDomain::Matrix(_, _) => todo!("Unwrap one dimension of the domain"),

1188

            _ => None,

1189

1190

40

1191

1192

1193

impl Typeable for GroundDomain {

1194

1840026

    fn return_type(&self) -> ReturnType {

1195

1840026

        match self {

1196

            GroundDomain::Empty(ty) => ty.clone(),

1197

177969

            GroundDomain::Bool => ReturnType::Bool,

1198

1532972

            GroundDomain::Int(_) => ReturnType::Int,

1199

76

            GroundDomain::Set(_attr, inner) => ReturnType::Set(Box::new(inner.return_type())),

1200

4

            GroundDomain::MSet(_attr, inner) => ReturnType::MSet(Box::new(inner.return_type())),

1201

            GroundDomain::Sequence(_attr, inner) => {

1202

                ReturnType::Sequence(Box::new(inner.return_type()))

1203

1204

116716

            GroundDomain::Matrix(inner, _idx) => ReturnType::Matrix(Box::new(inner.return_type())),

1205

6960

            GroundDomain::Tuple(inners) => {

1206

6960

                let mut inner_types = Vec::new();

1207

13920

                for inner in inners {

1208

13920

                    inner_types.push(inner.return_type());

1209

13920

1210

6960

                ReturnType::Tuple(inner_types)

1211

1212

4

            GroundDomain::Function(_, dom, cdom) => {

1213

4

                ReturnType::Function(Box::new(dom.return_type()), Box::new(cdom.return_type()))

1214

1215

5121

            GroundDomain::Record(entries) => {

1216

5121

                let mut entry_types = Vec::new();

1217

10241

                for entry in entries {

1218

10241

                    entry_types.push(entry.clone().func_map(|x| x.return_type()));

1219

1220

5121

                ReturnType::Record(entry_types)

1221

1222

80

            GroundDomain::Variant(entries) => {

1223

80

                let mut entry_types = Vec::new();

1224

240

                for entry in entries {

1225

240

                    entry_types.push(entry.clone().func_map(|x| x.return_type()));

1226

1227

80

                ReturnType::Variant(entry_types)

1228

1229

4

            GroundDomain::Relation(_, inners) => {

1230

4

                let mut inner_types = Vec::new();

1231

12

                for inner in inners {

1232

12

                    inner_types.push(inner.return_type());

1233

12

1234

4

                ReturnType::Relation(inner_types)

1235

1236

120

            GroundDomain::Partition(_, inner) => ReturnType::Set(Box::new(inner.return_type())),

1237

1238

1840026

1239

1240

1241

impl Display for FieldGround {

1242

880

    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {

1243

880

        write!(f, "{}: {}", self.name, self.value)

1244

880

1245

1246

1247

impl Display for GroundDomain {

1248

1198531752

    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {

1249

1198531752

        match &self {

1250

12

            GroundDomain::Empty(ty) => write!(f, "empty({ty})"),

1251

1068176944

            GroundDomain::Bool => write!(f, "bool"),

1252

124326892

            GroundDomain::Int(ranges) => {

1253

124326892

                if ranges.iter().all(Range::is_lower_or_upper_bounded) {

1254

128108980

                    let rngs: String = ranges.iter().map(|r| format!("{r}")).join(", ");

1255

124326892

                    write!(f, "int({})", rngs)

1256

                } else {

1257

                    write!(f, "int")

1258

1259

1260

29820

            GroundDomain::Set(attrs, inner_dom) => write!(f, "set {attrs} of {inner_dom}"),

1261

484

            GroundDomain::MSet(attrs, inner_dom) => write!(f, "mset {attrs} of {inner_dom}"),

1262

320

            GroundDomain::Sequence(attrs, inner_dom) => {

1263

320

                write!(f, "sequence {attrs} of {inner_dom}")

1264

1265

5837956

            GroundDomain::Matrix(value_domain, index_domains) => {

1266

5837956

                write!(

1267

5837956

f,

1268

                    "matrix indexed by {} of {value_domain}",

1269

5837956

                    pretty_vec(&index_domains.iter().collect_vec())

1270

1271

1272

157280

            GroundDomain::Tuple(domains) => {

1273

157280

                write!(f, "tuple ({})", &domains.iter().join(", "))

1274

1275

240

            GroundDomain::Record(entries) => {

1276

480

                let inners = entries.iter().map(|t| format!("{}", t)).join(", ");

1277

240

                write!(f, "record {{{inners}}}",)

1278

1279

160

            GroundDomain::Variant(entries) => {

1280

400

                let inners = entries.iter().map(|t| format!("{}", t)).join(", ");

1281

160

                write!(f, "variant {{{inners}}}",)

1282

1283

808

            GroundDomain::Function(attribute, domain, codomain) => {

1284

808

                write!(f, "function {} {} --> {} ", attribute, domain, codomain)

1285

1286

456

            GroundDomain::Relation(attrs, domains) => {

1287

456

                write!(f, "relation {} of ({})", attrs, domains.iter().join(" * "))

1288

1289

380

            GroundDomain::Partition(attrs, inner) => {

1290

380

                write!(f, "partition {attrs} from {inner}")

1291

1292

1293

1198531752

1294

1295

1296

#[cfg(test)]

1297

mod tests {

1298

    use super::*;

1299

    use crate::ast::Name;

1300

    use crate::{domain_int_ground, matrix_lit};

1301

1302

    #[test]

1303

1

    fn matrix_values_1d_bool_of_bool() {

1304

        // matrix indexed by [bool] of bool

1305

        // 2 cells, 2 possible values => 2^2 = 4 matrices

1306

1

        let dom = GroundDomain::Matrix(

1307

1

            Moo::new(GroundDomain::Bool),

1308

1

            vec![Moo::new(GroundDomain::Bool)],

1309

1

);

1310

1311

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1312

1313

1

        assert_eq!(values.len(), 4);

1314

1

        assert_eq!(

1315

1

            values[0],

1316

1

            matrix_lit![false, false; Moo::new(GroundDomain::Bool)]

1317

);

1318

1

        assert_eq!(

1319

1

            values[1],

1320

1

            matrix_lit![false, true; Moo::new(GroundDomain::Bool)]

1321

);

1322

1

        assert_eq!(

1323

1

            values[2],

1324

1

            matrix_lit![true, false; Moo::new(GroundDomain::Bool)]

1325

);

1326

1

        assert_eq!(

1327

1

            values[3],

1328

1

            matrix_lit![true, true; Moo::new(GroundDomain::Bool)]

1329

);

1330

1

1331

1332

    #[test]

1333

1

    fn matrix_values_1d_int() {

1334

        // matrix indexed by [int(1..2)] of int(0..1)

1335

        // 2 cells, 2 possible values => 4 matrices

1336

1

        let dom = GroundDomain::Matrix(domain_int_ground!(0..1), vec![domain_int_ground!(1..2)]);

1337

1338

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1339

1340

1

        assert_eq!(values.len(), 4);

1341

1

        assert_eq!(values[0], matrix_lit![0, 0; domain_int_ground!(1..2)]);

1342

1

        assert_eq!(values[1], matrix_lit![0, 1; domain_int_ground!(1..2)]);

1343

1

        assert_eq!(values[2], matrix_lit![1, 0; domain_int_ground!(1..2)]);

1344

1

        assert_eq!(values[3], matrix_lit![1, 1; domain_int_ground!(1..2)]);

1345

1

1346

1347

    #[test]

1348

1

    fn matrix_values_2d_lexicographic() {

1349

        // matrix indexed by [int(1..2), int(1..2)] of int(0..1)

1350

        // 4 cells, 2 possible values => 2^4 = 16 matrices

1351

1

        let dom = GroundDomain::Matrix(

1352

1

            domain_int_ground!(0..1),

1353

1

            vec![domain_int_ground!(1..2), domain_int_ground!(1..2)],

1354

1

);

1355

1356

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1357

1358

1

        assert_eq!(values.len(), 16);

1359

1360

        // First: [[0,0],[0,0]]

1361

1

        assert_eq!(

1362

1

            values[0],

1363

1

            matrix_lit![[0, 0], [0, 0]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]

1364

);

1365

        // Second: [[0,0],[0,1]]

1366

1

        assert_eq!(

1367

1

            values[1],

1368

1

            matrix_lit![[0, 0], [0, 1]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]

1369

);

1370

        // Third: [[0,0],[1,0]]

1371

1

        assert_eq!(

1372

1

            values[2],

1373

1

            matrix_lit![[0, 0], [1, 0]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]

1374

);

1375

        // Fourth: [[0,0],[1,1]]

1376

1

        assert_eq!(

1377

1

            values[3],

1378

1

            matrix_lit![[0, 0], [1, 1]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]

1379

);

1380

        // Last: [[1,1],[1,1]]

1381

1

        assert_eq!(

1382

1

            values[15],

1383

1

            matrix_lit![[1, 1], [1, 1]; [domain_int_ground!(1..2), domain_int_ground!(1..2)]]

1384

);

1385

1

1386

1387

    #[test]

1388

1

    fn matrix_values_count_matches_length() {

1389

        // matrix indexed by [int(1..3)] of int(0..1)

1390

        // 3 cells, 2 possible values => 2^3 = 8 matrices

1391

1

        let dom = GroundDomain::Matrix(domain_int_ground!(0..1), vec![domain_int_ground!(1..3)]);

1392

1393

1

        let count = dom.values().unwrap().count();

1394

1

        let length = dom.length().unwrap();

1395

1396

1

        assert_eq!(count as u64, length);

1397

1

1398

1399

    #[test]

1400

1

    fn tuple_values_two_bools() {

1401

        // tuple of (bool, bool) => 2*2 = 4 values

1402

1

        let dom = GroundDomain::Tuple(vec![

1403

1

            Moo::new(GroundDomain::Bool),

1404

1

            Moo::new(GroundDomain::Bool),

1405

1

]);

1406

1407

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1408

1409

1

        assert_eq!(values.len(), 4);

1410

4

        let t = |a, b| {

1411

4

            Literal::AbstractLiteral(AbstractLiteral::Tuple(vec![

1412

4

                Literal::Bool(a),

1413

4

                Literal::Bool(b),

1414

4

]))

1415

4

};

1416

1

        assert_eq!(values[0], t(false, false));

1417

1

        assert_eq!(values[1], t(false, true));

1418

1

        assert_eq!(values[2], t(true, false));

1419

1

        assert_eq!(values[3], t(true, true));

1420

1

1421

1422

    #[test]

1423

1

    fn tuple_values_mixed_domains() {

1424

        // tuple of (bool, int(0..2)) => 2*3 = 6 values, lexicographic

1425

1

        let dom = GroundDomain::Tuple(vec![Moo::new(GroundDomain::Bool), domain_int_ground!(0..2)]);

1426

1427

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1428

1429

1

        assert_eq!(values.len(), 6);

1430

6

        let t = |b: bool, i: i32| {

1431

6

            Literal::AbstractLiteral(AbstractLiteral::Tuple(vec![

1432

6

                Literal::Bool(b),

1433

6

                Literal::Int(i),

1434

6

]))

1435

6

};

1436

        // bool false first, then ints 0,1,2

1437

1

        assert_eq!(values[0], t(false, 0));

1438

1

        assert_eq!(values[1], t(false, 1));

1439

1

        assert_eq!(values[2], t(false, 2));

1440

        // then bool true

1441

1

        assert_eq!(values[3], t(true, 0));

1442

1

        assert_eq!(values[4], t(true, 1));

1443

1

        assert_eq!(values[5], t(true, 2));

1444

1

1445

1446

    #[test]

1447

1

    fn tuple_values_count_matches_length() {

1448

1

        let dom = GroundDomain::Tuple(vec![

1449

1

            domain_int_ground!(1..3),

1450

1

            Moo::new(GroundDomain::Bool),

1451

1

            domain_int_ground!(0..1),

1452

1

]);

1453

1

        let count = dom.values().unwrap().count();

1454

1

        let length = dom.length().unwrap();

1455

1

        assert_eq!(count as u64, length);

1456

1

1457

1458

    #[test]

1459

1

    fn record_values_lexicographic_by_name() {

1460

        // record {b: bool, a: int(0..1)}

1461

        // Entries should be ordered by name: a first, then b

1462

1

        let dom = GroundDomain::Record(vec![

1463

1

            Field {

1464

1

                name: Name::user("b"),

1465

1

                value: Moo::new(GroundDomain::Bool),

1466

1

},

1467

1

            Field {

1468

1

                name: Name::user("a"),

1469

1

                value: domain_int_ground!(0..1),

1470

1

},

1471

1

]);

1472

1473

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1474

1475

        // 2 * 2 = 4 values

1476

1

        assert_eq!(values.len(), 4);

1477

1478

        // Entries should be sorted by name: "a" before "b"

1479

4

        let r = |a_val: i32, b_val: bool| {

1480

4

            Literal::AbstractLiteral(AbstractLiteral::Record(vec![

1481

4

                Field {

1482

4

                    name: Name::user("a"),

1483

4

                    value: Literal::Int(a_val),

1484

4

},

1485

4

                Field {

1486

4

                    name: Name::user("b"),

1487

4

                    value: Literal::Bool(b_val),

1488

4

},

1489

4

]))

1490

4

};

1491

1492

        // "a" (int) varies slowest, "b" (bool) varies fastest

1493

1

        assert_eq!(values[0], r(0, false));

1494

1

        assert_eq!(values[1], r(0, true));

1495

1

        assert_eq!(values[2], r(1, false));

1496

1

        assert_eq!(values[3], r(1, true));

1497

1

1498

1499

    #[test]

1500

1

    fn record_values_count_matches_length() {

1501

1

        let dom = GroundDomain::Record(vec![

1502

1

            Field {

1503

1

                name: Name::user("x"),

1504

1

                value: domain_int_ground!(1..3),

1505

1

},

1506

1

            Field {

1507

1

                name: Name::user("y"),

1508

1

                value: Moo::new(GroundDomain::Bool),

1509

1

},

1510

1

]);

1511

1

        let count = dom.values().unwrap().count();

1512

1

        let length = dom.length().unwrap();

1513

1

        assert_eq!(count as u64, length);

1514

1

1515

1516

17

    fn set_lit(elems: Vec<i32>) -> Literal {

1517

17

        Literal::AbstractLiteral(AbstractLiteral::Set(

1518

17

            elems.into_iter().map(Literal::Int).collect(),

1519

17

))

1520

17

1521

1522

    #[test]

1523

1

    fn set_values_unbounded() {

1524

        // set of int(1..3) => all 2^3 = 8 subsets, in order of ascending size

1525

1

        let dom = GroundDomain::Set(SetAttr::default(), domain_int_ground!(1..3));

1526

1527

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1528

1529

1

        assert_eq!(values.len(), 8);

1530

1

        assert_eq!(values[0], set_lit(vec![])); // size 0

1531

1

        assert_eq!(values[1], set_lit(vec![1])); // size 1

1532

1

        assert_eq!(values[2], set_lit(vec![2]));

1533

1

        assert_eq!(values[3], set_lit(vec![3]));

1534

1

        assert_eq!(values[4], set_lit(vec![1, 2])); // size 2

1535

1

        assert_eq!(values[5], set_lit(vec![1, 3]));

1536

1

        assert_eq!(values[6], set_lit(vec![2, 3]));

1537

1

        assert_eq!(values[7], set_lit(vec![1, 2, 3])); // size 3

1538

1

1539

1540

    #[test]

1541

1

    fn set_values_fixed_size() {

1542

        // set (size 2) of int(1..3) => the 3 two-element subsets

1543

1

        let dom = GroundDomain::Set(SetAttr::new_size(2), domain_int_ground!(1..3));

1544

1545

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1546

1547

1

        assert_eq!(values.len(), 3);

1548

1

        assert_eq!(values[0], set_lit(vec![1, 2]));

1549

1

        assert_eq!(values[1], set_lit(vec![1, 3]));

1550

1

        assert_eq!(values[2], set_lit(vec![2, 3]));

1551

1

1552

1553

    #[test]

1554

1

    fn set_values_bounded_size() {

1555

        // set (minSize 1, maxSize 2) of int(1..3) => subsets of size 1 and 2

1556

1

        let dom = GroundDomain::Set(SetAttr::new_min_max_size(1, 2), domain_int_ground!(1..3));

1557

1558

1

        let values: Vec<Literal> = dom.values().unwrap().collect();

1559

1560

1

        assert_eq!(values.len(), 6);

1561

1

        assert_eq!(values[0], set_lit(vec![1]));

1562

1

        assert_eq!(values[1], set_lit(vec![2]));

1563

1

        assert_eq!(values[2], set_lit(vec![3]));

1564

1

        assert_eq!(values[3], set_lit(vec![1, 2]));

1565

1

        assert_eq!(values[4], set_lit(vec![1, 3]));

1566

1

        assert_eq!(values[5], set_lit(vec![2, 3]));

1567

1

1568

1569

    #[test]

1570

1

    fn set_values_count_matches_length() {

1571

1

        let dom = GroundDomain::Set(SetAttr::default(), domain_int_ground!(1..4));

1572

1

        let count = dom.values().unwrap().count();

1573

1

        let length = dom.length().unwrap();

1574

1

        assert_eq!(count as u64, length);

1575

1

1576