Grcov report - ground.rs

1

use crate::ast::domains::MSetAttr;

2

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

3

use crate::ast::{

4

    AbstractLiteral, Domain, DomainOpError, FuncAttr, HasDomain, Literal, Moo, RecordEntry,

5

    SetAttr, Typeable,

6

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

7

};

8

use crate::range;

9

use crate::utils::count_combinations;

10

use conjure_cp_core::ast::{Name, ReturnType};

11

use itertools::{Itertools, izip};

12

use num_traits::ToPrimitive;

13

use polyquine::Quine;

14

use serde::{Deserialize, Serialize};

15

use std::collections::BTreeSet;

16

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

17

use std::iter::zip;

18

use uniplate::Uniplate;

19

20

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

21

#[path_prefix(conjure_cp::ast)]

22

pub struct RecordEntryGround {

23

    pub name: Name,

24

    pub domain: Moo<GroundDomain>,

25

26

27

impl From<RecordEntryGround> for RecordEntry {

28

80

    fn from(value: RecordEntryGround) -> Self {

29

80

        RecordEntry {

30

80

            name: value.name,

31

80

            domain: value.domain.into(),

32

80

33

80

34

35

36

impl TryFrom<RecordEntry> for RecordEntryGround {

37

    type Error = DomainOpError;

38

39

162

    fn try_from(value: RecordEntry) -> Result<Self, Self::Error> {

40

162

        match value.domain.as_ref() {

41

162

            Domain::Ground(gd) => Ok(RecordEntryGround {

42

162

                name: value.name,

43

162

                domain: gd.clone(),

44

162

}),

45

            Domain::Unresolved(_) => Err(DomainOpError::NotGround),

46

47

162

48

49

50

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

51

#[path_prefix(conjure_cp::ast)]

52

pub enum GroundDomain {

53

    /// An empty domain of a given type

54

    Empty(ReturnType),

55

    /// A boolean value (true / false)

56

    Bool,

57

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

58

    Int(Vec<Range<Int>>),

59

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

60

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

61

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

62

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

63

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

64

    /// and indices from the n index domains

65

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

66

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

67

    Tuple(Vec<Moo<GroundDomain>>),

68

    /// A record

69

    Record(Vec<RecordEntryGround>),

70

    /// A function with a domain and range

71

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

72

73

74

impl GroundDomain {

75

1359994

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

76

1359994

        match (self, other) {

77

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

78

                if *ty == dom.return_type() {

79

                    Ok(dom.clone())

80

                } else {

81

                    Err(DomainOpError::WrongType)

82

83

84

800

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

85

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

86

1317342

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

87

1317342

                let mut rngs = r1.clone();

88

1317342

                rngs.extend(r2.clone());

89

1317342

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

90

91

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

92

96

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

93

96

                SetAttr::default(),

94

96

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

95

)),

96

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

97

                Err(DomainOpError::WrongType)

98

99

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

100

                MSetAttr::default(),

101

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

102

)),

103

41756

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

104

                Ok(GroundDomain::Matrix(

105

41756

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

106

41756

                    idx1.clone(),

107

))

108

109

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

110

                Err(DomainOpError::WrongType)

111

112

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

113

                let mut inners = Vec::new();

114

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

115

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

116

117

                Ok(GroundDomain::Tuple(inners))

118

119

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

120

                Err(DomainOpError::WrongType)

121

122

            // TODO: Eventually we may define semantics for joining record domains. This day is not today.

123

            #[allow(unreachable_patterns)]

124

            // Technically redundant but logically clearer to have both

125

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

126

                Err(DomainOpError::WrongType)

127

128

            #[allow(unreachable_patterns)]

129

            // Technically redundant but logically clearer to have both

130

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

131

                Err(DomainOpError::WrongType)

132

133

134

1359994

135

136

    /// Calculates the intersection of two domains.

137

///

138

    /// # Errors

139

///

140

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

141

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

142

36936

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

143

        // TODO: does not consider unbounded domains yet

144

        // needs to be tested once comprehension rules are written

145

146

36936

        match (self, other) {

147

            // one or more arguments is an empty int domain

148

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

149

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

150

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

151

                Ok(d.clone())

152

153

154

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

155

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

156

                if matches!(

157

                    **inner1,

158

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

159

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

160

161

                Ok(d.clone())

162

163

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

164

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

165

                    && matches!(

166

                        **inner2,

167

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

168

                    ) =>

169

170

                Ok(d.clone())

171

172

173

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

174

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

175

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

176

                Ok(d.clone())

177

178

179

            // both arguments are non-empy

180

90

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

181

90

                SetAttr::default(),

182

90

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

183

)),

184

185

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

186

35474

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

187

188

35474

                let v1 = self.values_i32()?;

189

35474

                let v2 = other.values_i32()?;

190

166092

                for value1 in v1.iter() {

191

166092

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

192

100520

                        v.insert(*value1);

193

100520

194

195

35474

                Ok(GroundDomain::from_set_i32(&v))

196

197

1372

            _ => Err(DomainOpError::WrongType),

198

199

36936

200

201

891646

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

202

891646

        match self {

203

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

204

2660

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

205

2660

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

206

2660

)),

207

887376

            GroundDomain::Int(rngs) => {

208

887376

                let rng_iters = rngs

209

887376

                    .iter()

210

887376

                    .map(Range::iter)

211

887376

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

212

887376

                    .ok_or(DomainOpError::Unbounded)?;

213

887376

                Ok(Box::new(

214

888336

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

215

))

216

217

1610

            GroundDomain::Matrix(elem_domain, index_domains) => Ok(Box::new(

218

1610

                enumerate_matrix_values(elem_domain.as_ref(), index_domains)?.into_iter(),

219

)),

220

            _ => todo!("Enumerating nested domains is not yet supported"),

221

222

891646

223

224

    /// Gets the length of this domain.

225

///

226

    /// # Errors

227

///

228

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

229

5174

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

230

5174

        match self {

231

1

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

232

5

            GroundDomain::Bool => Ok(2),

233

5150

            GroundDomain::Int(ranges) => {

234

5150

                if ranges.is_empty() {

235

                    return Err(DomainOpError::Unbounded);

236

5150

237

238

5150

                let mut length = 0u64;

239

5153

                for range in ranges {

240

5153

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

241

5151

                        length += range_length as u64;

242

5151

                    } else {

243

2

                        return Err(DomainOpError::Unbounded);

244

245

246

5148

                Ok(length)

247

248

12

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

249

12

                let inner_len = inner_domain.length()?;

250

10

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

251

5

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

252

1

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

253

1

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

254

2

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

255

1

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

256

};

257

10

                let mut ans = 0u64;

258

73

                for sz in min_sz..=max_sz {

259

73

                    let c = count_combinations(inner_len, sz)?;

260

72

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

261

262

9

                Ok(ans)

263

264

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

265

                let inner_len = inner_domain.length()?;

266

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

267

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

268

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

269

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

270

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

271

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

272

};

273

                let mut ans = 0u64;

274

                for sz in min_sz..=max_sz {

275

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

276

                    // Where n=inner_len and k=sz

277

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

278

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

279

280

                Ok(ans)

281

282

1

            GroundDomain::Tuple(domains) => {

283

1

                let mut ans = 1u64;

284

2

                for domain in domains {

285

2

                    ans = ans

286

2

                        .checked_mul(domain.length()?)

287

2

                        .ok_or(DomainOpError::TooLarge)?;

288

289

1

                Ok(ans)

290

291

1

            GroundDomain::Record(entries) => {

292

                // A record is just a named tuple

293

1

                let mut ans = 1u64;

294

2

                for entry in entries {

295

2

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

296

2

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

297

298

1

                Ok(ans)

299

300

4

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

301

4

                let inner_sz = inner_domain.length()?;

302

5

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

303

5

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

304

5

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

305

5

                })?;

306

4

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

307

308

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

309

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

310

311

312

5174

313

314

787358

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

315

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

316

        // error when a domain is added.

317

787358

        match self {

318

            // empty domain can't contain anything

319

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

320

176968

            GroundDomain::Bool => match lit {

321

176964

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

322

4

                _ => Ok(false),

323

},

324

605666

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

325

605666

                Literal::Int(x) => {

326

                    // unconstrained int domain - contains all integers

327

605666

                    if ranges.is_empty() {

328

88

                        return Ok(true);

329

605578

};

330

331

606714

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

332

333

                _ => Ok(false),

334

},

335

480

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

336

320

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

337

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

338

320

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

339

320

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

340

                        return Ok(false);

341

320

342

343

640

                    for elem in lit_elems {

344

640

                        if !inner_domain.contains(elem)? {

345

160

                            return Ok(false);

346

480

347

348

160

                    Ok(true)

349

350

160

                _ => Ok(false),

351

},

352

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

353

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

354

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

355

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

356

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

357

                        return Ok(false);

358

359

360

                    for elem in lit_elems {

361

                        if !inner_domain.contains(elem)? {

362

                            return Ok(false);

363

364

365

                    Ok(true)

366

367

                _ => Ok(false),

368

},

369

244

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

370

218

                match lit {

371

218

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

372

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

373

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

374

375

218

                        let Some((current_index_domain, remaining_index_domains)) =

376

218

                            index_domains.split_first()

377

                        else {

378

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

379

};

380

381

218

                        if *current_index_domain != *idx_domain {

382

                            return Ok(false);

383

218

};

384

385

218

                        let next_elem_domain = if remaining_index_domains.is_empty() {

386

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

387

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

388

198

                            elem_domain.as_ref().clone()

389

                        } else {

390

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

391

20

                            GroundDomain::Matrix(

392

20

                                elem_domain.clone(),

393

20

                                remaining_index_domains.to_vec(),

394

20

395

};

396

397

1046

                        for elem in elems {

398

1046

                            if !next_elem_domain.contains(elem)? {

399

                                return Ok(false);

400

1046

401

402

403

218

                        Ok(true)

404

405

26

                    _ => Ok(false),

406

407

408

1120

            GroundDomain::Tuple(elem_domains) => {

409

1120

                match lit {

410

1120

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

411

1120

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

412

                            return Ok(false);

413

1120

414

415

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

416

2240

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

417

2240

                            if !elem_domain.contains(elem)? {

418

                                return Ok(false);

419

2240

420

421

422

1120

                        Ok(true)

423

424

                    _ => Ok(false),

425

426

427

2880

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

428

2880

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

429

2880

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

430

                        return Ok(false);

431

2880

432

433

5760

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

434

5760

                        if entry.name != lit_entry.name

435

5760

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

436

437

                            return Ok(false);

438

5760

439

440

2880

                    Ok(true)

441

442

                _ => Ok(false),

443

},

444

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

445

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

446

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

447

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

448

                        return Ok(false);

449

450

                    for lit in lit_elems {

451

                        let domain_element = &lit.0;

452

                        let codomain_element = &lit.1;

453

                        if !domain.contains(domain_element)? {

454

                            return Ok(false);

455

456

                        if !codomain.contains(codomain_element)? {

457

                            return Ok(false);

458

459

460

                    Ok(true)

461

462

                _ => Ok(false),

463

},

464

465

787358

466

467

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

468

///

469

    /// # Errors

470

///

471

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

472

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

473

925000

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

474

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

475

            return Ok(vec![]);

476

925000

477

925000

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

478

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

479

};

480

481

925000

        if ranges.is_empty() {

482

            return Err(DomainOpError::Unbounded);

483

925000

484

485

925000

        let mut values = vec![];

486

935920

        for range in ranges {

487

935920

            match range {

488

395602

                Range::Single(i) => {

489

395602

                    values.push(*i);

490

395602

491

540318

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

492

540318

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

493

540318

494

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

495

                    return Err(DomainOpError::Unbounded);

496

497

498

499

500

925000

        Ok(values)

501

925000

502

503

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

504

///

505

    /// # Examples

506

///

507

    /// ```

508

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

509

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

510

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

511

///

512

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

513

///

514

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

515

///

516

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

517

    /// ```

518

///

519

    /// ```

520

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

521

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

522

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

523

///

524

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

525

///

526

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

527

///

528

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

529

    /// ```

530

///

531

    /// ```

532

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

533

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

534

///

535

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

536

///

537

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

538

///

539

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

540

    /// ```

541

467738

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

542

467738

        if elements.is_empty() {

543

20

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

544

467718

545

467718

        if elements.len() == 1 {

546

1726

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

547

465992

548

549

465992

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

550

551

465992

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

552

553

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

554

        // numbers into ranges.

555

556

        // the bounds of the current run of numbers.

557

465992

        let mut lower = elems_iter

558

465992

            .next()

559

465992

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

560

465992

        let mut upper = lower;

561

562

1055999

        for current in elems_iter {

563

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

564

565

1055999

            if current == upper + 1 {

566

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

567

//

568

962696

                upper = current;

569

962696

            } else {

570

                // the run lower..upper has ended.

571

//

572

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

573

574

93303

                if lower == upper {

575

82738

                    ranges.push(range!(lower));

576

82739

                } else {

577

10565

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

578

10565

579

580

93303

                lower = current;

581

93303

                upper = current;

582

583

584

585

        // add the final run to the domain

586

465992

        if lower == upper {

587

12687

            ranges.push(range!(lower));

588

453305

        } else {

589

453305

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

590

453305

591

592

465992

        ranges = Range::squeeze(&ranges);

593

465992

        GroundDomain::Int(ranges)

594

467738

595

596

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

597

///

598

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

599

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

600

///

601

    /// # Errors

602

///

603

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

604

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

605

414444

    pub fn apply_i32(

606

414444

        &self,

607

414444

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

608

414444

        other: &GroundDomain,

609

414444

    ) -> Result<GroundDomain, DomainOpError> {

610

414444

        let vs1 = self.values_i32()?;

611

414444

        let vs2 = other.values_i32()?;

612

613

414444

        let mut set = BTreeSet::new();

614

3378862

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

615

3378862

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

616

3206498

                set.insert(v);

617

3206498

618

619

620

414444

        Ok(GroundDomain::from_set_i32(&set))

621

414444

622

623

    /// Returns true if the domain is finite.

624

31562

    pub fn is_finite(&self) -> bool {

625

52826

        for domain in self.universe() {

626

52826

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

627

43402

                if ranges.is_empty() {

628

                    return false;

629

43402

630

631

45202

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

632

45202

                    matches!(

633

45202

                        range,

634

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

635

636

45202

                }) {

637

                    return false;

638

43402

639

9424

640

641

31562

        true

642

31562

643

644

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

645

///

646

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

647

///

648

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

649

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

650

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

651

///

652

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

653

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

654

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

655

///

656

    /// # Errors

657

///

658

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

659

    ///   each-other, as described above.

660

///

661

    /// # Examples

662

///

663

    /// ```

664

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

665

///

666

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

667

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

668

    /// ```

669

///

670

    /// ```

671

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

672

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

673

///

674

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

675

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

676

///

677

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

678

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

679

///

680

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

681

///

682

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

683

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

684

///

685

    /// assert_eq!(domain,expected_domain);

686

    /// ```

687

///

688

    /// ```

689

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

690

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

691

///

692

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

693

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

694

///

695

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

696

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

697

///

698

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

699

///

700

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

701

    /// ```

702

///

703

    /// ```

704

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

705

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

706

///

707

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

708

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

709

///

710

///

711

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

712

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

713

///

714

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

715

///

716

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

717

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

718

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

719

///

720

    /// assert_eq!(domain,expected_domain);

721

    /// ```

722

///

723

///

724

35640

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

725

        // TODO: use proptest to test this better?

726

727

35640

        if literals.is_empty() {

728

20

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

729

35620

730

731

35620

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

732

733

17620

        match first_literal {

734

            Literal::Int(_) => {

735

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

736

17760

                let mut ints = BTreeSet::new();

737

63624

                for lit in literals {

738

63624

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

739

                        return Err(DomainOpError::WrongType);

740

};

741

742

63624

                    ints.insert(*i);

743

744

745

17760

                Ok(GroundDomain::from_set_i32(&ints))

746

747

            Literal::Bool(_) => {

748

                // check all literals are bools

749

240

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

750

                    Err(DomainOpError::WrongType)

751

                } else {

752

240

                    Ok(GroundDomain::Bool)

753

754

755

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

756

6

                let mut all_elems = vec![];

757

758

6

                for lit in literals {

759

6

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

760

                        return Err(DomainOpError::WrongType);

761

};

762

763

6

                    all_elems.extend(elems.clone());

764

765

6

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

766

767

6

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

768

769

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

770

                let mut all_elems = vec![];

771

772

                for lit in literals {

773

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

774

                        return Err(DomainOpError::WrongType);

775

};

776

777

                    all_elems.extend(elems.clone());

778

779

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

780

781

                Ok(GroundDomain::MSet(

782

                    MSetAttr::default(),

783

                    Moo::new(elem_domain),

784

))

785

786

17214

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

787

17214

                let mut first_index_domain = vec![];

788

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

789

17214

                let mut l = l.clone();

790

17234

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

791

17234

                    assert!(

792

17234

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

793

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

794

);

795

17234

                    first_index_domain.push(idx);

796

17234

                    l = elems[0].clone();

797

798

799

17214

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

800

801

                // check types and index domains

802

17274

                for lit in literals {

803

17274

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

804

                        return Err(DomainOpError::NotGround);

805

};

806

807

17274

                    all_elems.extend(elems.clone());

808

809

17274

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

810

17274

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

811

40

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

812

40

                        assert!(

813

40

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

814

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

815

);

816

40

                        index_domain.push(idx);

817

40

                        l = elems[0].clone();

818

819

820

17274

                    if index_domain != first_index_domain {

821

20

                        return Err(DomainOpError::WrongType);

822

17254

823

824

825

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

826

17194

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

827

80290

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

828

40

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

829

40

                        all_elems.extend(elems);

830

63056

                    } else {

831

63056

                        terminal_elements.push(elem);

832

63056

833

834

835

17194

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

836

837

17194

                Ok(GroundDomain::Matrix(

838

17194

                    Moo::new(element_domain),

839

17194

                    first_index_domain,

840

17194

))

841

842

843

160

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

844

160

                let n_fields = first_elems.len();

845

846

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

847

160

                let mut elem_domains = vec![];

848

849

320

                for i in 0..n_fields {

850

320

                    let mut all_elems = vec![];

851

320

                    for lit in literals {

852

320

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

853

                            return Err(DomainOpError::NotGround);

854

};

855

856

320

                        if elems.len() != n_fields {

857

                            return Err(DomainOpError::NotGround);

858

320

859

860

320

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

861

862

863

320

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

864

865

866

160

                Ok(GroundDomain::Tuple(elem_domains))

867

868

869

240

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

870

240

                let n_fields = first_elems.len();

871

480

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

872

873

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

874

240

                let mut elem_domains = vec![];

875

876

480

                for i in 0..n_fields {

877

480

                    let mut all_elems = vec![];

878

480

                    for lit in literals {

879

480

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

880

                            return Err(DomainOpError::NotGround);

881

};

882

883

480

                        if elems.len() != n_fields {

884

                            return Err(DomainOpError::NotGround);

885

480

886

887

480

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

888

480

                        if elem.name != field_names[i] {

889

                            return Err(DomainOpError::NotGround);

890

480

891

892

480

                        all_elems.push(elem.value);

893

894

895

480

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

896

897

898

                Ok(GroundDomain::Record(

899

240

                    izip!(field_names, elem_domains)

900

480

                        .map(|(name, domain)| RecordEntryGround { name, domain })

901

240

                        .collect(),

902

))

903

904

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

905

                if items.is_empty() {

906

                    return Err(DomainOpError::NotGround);

907

908

909

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

910

                let d1 = x1.domain_of();

911

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

912

                let d2 = y1.domain_of();

913

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

914

915

                // Check that all items have the same domains

916

                for (x, y) in items {

917

                    let dx = x.domain_of();

918

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

919

920

                    let dy = y.domain_of();

921

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

922

923

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

924

                        return Err(DomainOpError::WrongType);

925

926

927

928

                todo!();

929

930

931

35640

932

933

40

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

934

40

        match self {

935

40

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

936

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

937

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

938

            _ => None,

939

940

40

941

942

943

impl Typeable for GroundDomain {

944

1773736

    fn return_type(&self) -> ReturnType {

945

1773736

        match self {

946

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

947

160058

            GroundDomain::Bool => ReturnType::Bool,

948

1498534

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

949

16

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

950

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

951

101448

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

952

6800

            GroundDomain::Tuple(inners) => {

953

6800

                let mut inner_types = Vec::new();

954

13600

                for inner in inners {

955

13600

                    inner_types.push(inner.return_type());

956

13600

957

6800

                ReturnType::Tuple(inner_types)

958

959

6880

            GroundDomain::Record(entries) => {

960

6880

                let mut entry_types = Vec::new();

961

13760

                for entry in entries {

962

13760

                    entry_types.push(entry.domain.return_type());

963

13760

964

6880

                ReturnType::Record(entry_types)

965

966

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

967

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

968

969

970

1773736

971

972

973

impl Display for GroundDomain {

974

1141856844

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

975

1141856844

        match &self {

976

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

977

1014575346

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

978

121276944

            GroundDomain::Int(ranges) => {

979

121276944

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

980

125002788

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

981

121276944

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

982

                } else {

983

                    write!(f, "int")

984

985

986

23746

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

987

360

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

988

5822808

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

989

5822808

                write!(

990

5822808

f,

991

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

992

5822808

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

993

994

995

156960

            GroundDomain::Tuple(domains) => {

996

156960

                write!(

997

156960

f,

998

                    "tuple of ({})",

999

156960

                    pretty_vec(&domains.iter().collect_vec())

1000

1001

1002

160

            GroundDomain::Record(entries) => {

1003

160

                write!(

1004

160

f,

1005

                    "record of ({})",

1006

160

                    pretty_vec(

1007

160

                        &entries

1008

160

                            .iter()

1009

320

                            .map(|entry| format!("{}: {}", entry.name, entry.domain))

1010

160

                            .collect_vec()

1011

1012

1013

1014

520

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

1015

520

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

1016

1017

1018

1141856844

1019

1020

1021

1610

fn enumerate_matrix_values(

1022

1610

    elem_domain: &GroundDomain,

1023

1610

    index_domains: &[Moo<GroundDomain>],

1024

1610

) -> Result<Vec<Literal>, DomainOpError> {

1025

1610

    let Some((current_index_domain, remaining_index_domains)) = index_domains.split_first() else {

1026

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

1027

};

1028

1029

1610

    let current_dimension_len =

1030

1610

        usize::try_from(current_index_domain.length()?).map_err(|_| DomainOpError::TooLarge)?;

1031

1032

1610

    let entry_values = if remaining_index_domains.is_empty() {

1033

1610

        elem_domain.values()?.collect_vec()

1034

    } else {

1035

        enumerate_matrix_values(elem_domain, remaining_index_domains)?

1036

};

1037

1038

1610

    Ok((0..current_dimension_len)

1039

1610

        .map(|_| entry_values.iter().cloned())

1040

1610

        .multi_cartesian_product()

1041

3220

        .map(|elems| {

1042

3220

            Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, current_index_domain.clone()))

1043

3220

})

1044

1610

        .collect())

1045

1610