Grcov report - ground.rs

1

use crate::ast::domains::attrs::{PartitionAttr, PermutationAttr};

2

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

3

use crate::ast::enumerated::EnumeratedType;

4

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

5

use crate::ast::unnamed::UnnamedType;

6

use crate::ast::{

7

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

8

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

9

    matrix,

10

    records::Field,

11

};

12

use crate::bug_assert;

13

use crate::range;

14

use crate::utils::{

15

    count_combinations, count_permutations, derangements, restricted_partition_count,

16

    stirling_second_kind,

17

};

18

use conjure_cp_core::ast::ReturnType;

19

use funcmap::FuncMap;

20

use itertools::{Itertools, izip};

21

use num_traits::ToPrimitive;

22

use polyquine::Quine;

23

use serde::{Deserialize, Serialize};

24

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

25

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

26

use std::iter::zip;

27

use uniplate::Uniplate;

28

29

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

30

31

/// Writes an integer domain, e.g. `int(1..4)`, `int(representation order, 1..4)`, or just `int`

32

/// when it has unbounded ranges and no representation preference.

33

31671793

pub(super) fn write_int_domain<A>(

34

31671793

    f: &mut Formatter<'_>,

35

31671793

    ranges: &[Range<A>],

36

31671793

    representation: Option<&str>,

37

31671793

) -> std::fmt::Result

38

31671793

where

39

31671793

    Range<A>: Display,

40

41

31671793

    let mut args = Vec::new();

42

31671793

    if let Some(representation) = representation {

43

3462

        args.push(format!("representation {representation}"));

44

31668331

45

31671793

    let bounded = ranges.iter().all(Range::is_lower_or_upper_bounded);

46

31671793

    if bounded {

47

35489596

        args.extend(ranges.iter().map(|r| r.to_string()));

48

240634

49

    // An int with unbounded ranges and nothing to say is just `int`; an empty one is `int()`.

50

31671793

    if !bounded && args.is_empty() {

51

240510

        write!(f, "int")

52

    } else {

53

31431283

        write!(f, "int({})", args.join(", "))

54

55

31671793

56

57

/// ` (representation X)`, for domains whose attribute list holds nothing else; empty without a

58

/// preference.

59

1565089

pub(super) fn representation_attribute(representation: &Option<String>) -> String {

60

1565089

    match representation {

61

696

        Some(representation) => format!(" (representation {representation})"),

62

1564393

        None => String::new(),

63

64

1565089

65

66

/// The Essence type-style spelling of an integer domain: `int` or `int(representation order)`.

67

1598

pub(super) fn int_type_string(representation: Option<&str>) -> String {

68

1598

    match representation {

69

        Some(representation) => format!("int(representation {representation})"),

70

1598

        None => "int".to_string(),

71

72

1598

73

74

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

75

#[path_prefix(conjure_cp::ast)]

76

/// Variants use the project-wide type/domain ordering; keep broad matches in the same order.

77

pub enum GroundDomain {

78

    /// An empty domain of a given type

79

    Empty(ReturnType),

80

    /// A boolean value (true / false)

81

    Bool,

82

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

83

    /// preference (e.g. `int(representation order, 1..5)`)

84

    Int(Vec<Range<Int>>, Option<String>),

85

    /// A tuple of N elements, each with its own domain, and an optional representation preference

86

    Tuple(Vec<Moo<GroundDomain>>, Option<String>),

87

    /// A record, with an optional representation preference

88

    Record(Vec<FieldGround>, Option<String>),

89

    /// A variant domain with its domain options (reusing field entries), and an optional

90

    /// representation preference

91

    Variant(Vec<FieldGround>, Option<String>),

92

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

93

    /// and indices from the n index domains, with an optional representation preference

94

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

95

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

96

    Sequence(SequenceAttr, Moo<GroundDomain>),

97

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

98

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

99

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

100

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

101

    /// A function with a domain and codomain

102

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

103

    /// A relation as a set of tuples

104

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

105

    /// An enumerated type

106

    EnumeratedType(Moo<EnumeratedType>, Vec<Range<u32>>),

107

    /// An unnamed type

108

    UnnamedType(Moo<UnnamedType>),

109

    /// A partition

110

    Partition(PartitionAttr, Moo<GroundDomain>),

111

    /// A permutation

112

    Permutation(PermutationAttr, Moo<GroundDomain>),

113

114

115

/// Counts partitions of `n` labelled elements into unlabelled blocks that are *all* exactly

116

/// `block_size` (a `regular` partition), i.e. `n / (block_size! ^ k) / k!` for `k = n /

117

/// block_size` -- computed by choosing the `k` same-size groups one at a time (dividing out the

118

/// groups' own arbitrary ordering with one final `/ k!`) rather than via raw factorials, so

119

/// intermediate values stay as small as the final answer allows.

120

1

fn regular_partition_count(n: u64, block_size: u64) -> Result<u64, DomainOpError> {

121

1

    if n == 0 {

122

        return Ok(1);

123

1

124

1

    if block_size == 0 || !n.is_multiple_of(block_size) {

125

        return Ok(0);

126

1

127

1

    let num_parts = n / block_size;

128

1

    let mut numerator = 1u64;

129

1

    let mut remaining = n;

130

1

    for _ in 0..num_parts {

131

2

        let choose = count_combinations(remaining, block_size)?;

132

2

        numerator = numerator

133

2

            .checked_mul(choose)

134

2

            .ok_or(DomainOpError::TooLarge)?;

135

2

        remaining -= block_size;

136

137

1

    let num_parts_factorial = (1..=num_parts)

138

2

        .try_fold(1u64, |acc, x| acc.checked_mul(x))

139

1

        .ok_or(DomainOpError::TooLarge)?;

140

1

    numerator

141

1

        .checked_div(num_parts_factorial)

142

1

        .ok_or(DomainOpError::TooLarge)

143

1

144

145

/// Every unordered partition of `elements` into blocks whose size falls in `[block_min,

146

/// block_max]` (both inclusive; `block_min` is floored to `1`, since a block can't be empty).

147

///

148

/// Built by always rooting the block containing the *first* remaining element (`elements` is

149

/// consumed in its given order), then recursing on whatever's left -- the same canonical

150

/// construction [`restricted_partition_count`] counts without generating, so the two stay

151

/// consistent by construction. Each returned partition is a `Vec` of blocks in the order they

152

/// were rooted; each block is a `Vec` of elements in `[root, ..combination order]`.

153

30

fn restricted_partitions(

154

30

    elements: &[Literal],

155

30

    block_min: usize,

156

30

    block_max: usize,

157

30

) -> Vec<Vec<Vec<Literal>>> {

158

30

    let block_min = block_min.max(1);

159

30

    if elements.is_empty() {

160

15

        return vec![vec![]];

161

15

162

15

    let (first, rest) = elements.split_first().expect("checked non-empty above");

163

164

15

    let max_extra = block_max.saturating_sub(1).min(rest.len());

165

15

    if block_min.saturating_sub(1) > max_extra {

166

        return vec![];

167

15

168

169

15

    let mut results = vec![];

170

15

    for extra in block_min.saturating_sub(1)..=max_extra {

171

24

        for combo in rest.iter().cloned().combinations(extra) {

172

29

            let mut block = vec![first.clone()];

173

29

            block.extend(combo.iter().cloned());

174

175

29

            let remaining: Vec<Literal> = rest

176

29

                .iter()

177

40

                .filter(|elem| !combo.contains(elem))

178

                .cloned()

179

                .collect();

180

181

29

            for sub_partition in restricted_partitions(&remaining, block_min, block_max) {

182

37

                let mut whole = vec![block.clone()];

183

37

                whole.extend(sub_partition);

184

37

                results.push(whole);

185

186

187

188

15

    results

189

30

190

191

/// Every permutation of `n` in `0..len` (representing positions in `elements`) whose number of

192

/// non-fixed positions falls in `[moved_min, moved_max]`, returned as the concrete value each

193

/// position maps to (i.e. `result[i]` is what `elements[i]` is sent to).

194

1

fn restricted_permutations(

195

1

    elements: &[Literal],

196

1

    moved_min: usize,

197

1

    moved_max: usize,

198

1

) -> impl Iterator<Item = Vec<Literal>> + '_ {

199

1

    let n = elements.len();

200

1

    (0..n)

201

1

        .permutations(n)

202

6

        .filter(move |perm| {

203

18

            let moved = perm.iter().enumerate().filter(|&(i, p)| i != *p).count();

204

6

            moved >= moved_min && moved <= moved_max

205

6

})

206

9

        .map(move |perm| perm.into_iter().map(|i| elements[i].clone()).collect())

207

1

208

209

/// Converts a full position-to-position permutation mapping (`elements[i]` maps to `mapped[i]`)

210

/// into cycle notation, omitting fixed points -- mirrors

211

/// `PermutationAsFunction`'s own `up()` (`crates/conjure-cp-rules/src/types/permutation/

212

/// as_function/representation.rs`), duplicated here since domain-level enumeration lives in a

213

/// lower crate that representation can't depend on.

214

3

fn permutation_mapping_to_cycles(elements: &[Literal], mapped: &[Literal]) -> Vec<Vec<Literal>> {

215

    let forward: std::collections::HashMap<&Literal, &Literal> =

216

3

        elements.iter().zip(mapped.iter()).collect();

217

3

    let mut visited: std::collections::HashSet<&Literal> = std::collections::HashSet::new();

218

3

    let mut cycles = vec![];

219

3

    for start in elements {

220

9

        if visited.contains(start) {

221

3

            continue;

222

6

223

6

        let image = forward[start];

224

6

        if image == start {

225

3

            visited.insert(start);

226

3

            continue;

227

3

228

3

        let mut cycle = vec![start.clone()];

229

3

        visited.insert(start);

230

3

        let mut current = image;

231

6

        while current != start {

232

3

            visited.insert(current);

233

3

            cycle.push(current.clone());

234

3

            current = forward[current];

235

236

3

        cycles.push(cycle);

237

238

3

    cycles

239

3

240

241

/// The size attribute covering both sizes, for a union of two sequence domains.

242

///

243

/// Sizes have to survive the union: without a maximum, nothing downstream can tell how many

244

/// positions a sequence has -- iterating one, for instance, needs to know the range of positions.

245

12702

fn union_sequence_sizes(left: &Range<i32>, right: &Range<i32>) -> Range<i32> {

246

25404

    let bounds = |range: &Range<i32>| match range {

247

25056

        Range::Single(size) => (*size, Some(*size)),

248

348

        Range::Bounded(min, max) => (*min, Some(*max)),

249

        Range::UnboundedL(max) => (0, Some(*max)),

250

        Range::UnboundedR(min) => (*min, None),

251

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

252

25404

};

253

254

12702

    let (left_min, left_max) = bounds(left);

255

12702

    let (right_min, right_max) = bounds(right);

256

12702

    let min = left_min.min(right_min);

257

258

12702

    match (left_max, right_max) {

259

        (Some(left_max), Some(right_max)) => {

260

12702

            let max = left_max.max(right_max);

261

12702

            if min == max {

262

12238

                Range::Single(min)

263

            } else {

264

464

                Range::Bounded(min, max)

265

266

267

        _ => Range::UnboundedR(min),

268

269

12702

270

271

impl GroundDomain {

272

3734339

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

273

        // Keep implemented variants before `todo!` variants so mixed-domain unions report a type

274

        // error instead of entering an unsupported implementation. Each group uses declaration

275

        // order.

276

3734339

        match (self, other) {

277

            (GroundDomain::UnnamedType(lhs), GroundDomain::UnnamedType(rhs)) if lhs == rhs => {

278

                Ok(self.clone())

279

280

            (GroundDomain::EnumeratedType(_, _) | GroundDomain::UnnamedType(_), _)

281

            | (_, GroundDomain::EnumeratedType(_, _) | GroundDomain::UnnamedType(_)) => {

282

                Err(DomainOpError::WrongType)

283

284

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

285

                if *ty == dom.return_type() {

286

                    Ok(dom.clone())

287

                } else {

288

                    Err(DomainOpError::WrongType)

289

290

291

177248

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

292

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

293

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

294

2994232

                let mut rngs = r1.clone();

295

2994232

                rngs.extend(r2.clone());

296

2994232

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

297

298

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

299

                Err(DomainOpError::WrongType)

300

301

            (GroundDomain::Tuple(in1s, _), GroundDomain::Tuple(in2s, _))

302

182033

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

303

304

182033

                let mut inners = Vec::new();

305

182033

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

306

364066

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

307

308

182033

                Ok(GroundDomain::Tuple(inners, None))

309

310

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

311

                Err(DomainOpError::WrongType)

312

313

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

314

2117

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

315

316

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

317

4234

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

318

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

319

4234

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

320

2117

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

321

2117

                for (n, d) in lhs_fields {

322

4234

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

323

4234

                    let dom = d.union(d2)?;

324

4234

                    new_fields.push(Field {

325

4234

                        name: n.clone(),

326

4234

                        value: dom.into(),

327

4234

});

328

329

2117

                Ok(GroundDomain::Record(new_fields, None))

330

331

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

332

                Err(DomainOpError::WrongType)

333

334

            (GroundDomain::Matrix(in1, idx1, _), GroundDomain::Matrix(in2, idx2, _))

335

291651

                if idx1 == idx2 =>

336

337

                Ok(GroundDomain::Matrix(

338

291651

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

339

291651

                    idx1.clone(),

340

291651

                    None,

341

))

342

343

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

344

                Err(DomainOpError::WrongType)

345

346

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

347

74356

                SetAttr::default(),

348

74356

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

349

)),

350

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

351

                Err(DomainOpError::WrongType)

352

353

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

354

                MSetAttr::default(),

355

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

356

)),

357

            (GroundDomain::Sequence(attr1, in1), GroundDomain::Sequence(attr2, in2)) => {

358

                Ok(GroundDomain::Sequence(

359

12702

                    SequenceAttr {

360

12702

                        size: union_sequence_sizes(&attr1.size, &attr2.size),

361

12702

                        ..SequenceAttr::default()

362

12702

},

363

12702

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

364

))

365

366

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

367

                Err(DomainOpError::WrongType)

368

369

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

370

                let mut inners = Vec::new();

371

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

372

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

373

374

                Ok(GroundDomain::Relation(RelAttr::default(), inners))

375

376

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

377

                Err(DomainOpError::WrongType)

378

379

            #[allow(unreachable_patterns)]

380

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

381

                todo!("union variant domains")

382

383

            #[allow(unreachable_patterns)]

384

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

385

                todo!("union function domains")

386

387

            #[allow(unreachable_patterns)]

388

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

389

                todo!("union partition domains")

390

391

            #[allow(unreachable_patterns)]

392

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

393

                todo!("union permutation domains")

394

395

396

3734339

397

398

    /// Calculates the intersection of two domains.

399

///

400

    /// # Errors

401

///

402

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

403

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

404

968256

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

405

        // TODO: does not consider unbounded domains yet

406

        // needs to be tested once comprehension rules are written

407

408

968256

        match (self, other) {

409

            (GroundDomain::UnnamedType(lhs), GroundDomain::UnnamedType(rhs)) if lhs == rhs => {

410

                Ok(self.clone())

411

412

            // one or more arguments is an empty int domain

413

87

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

414

1

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

415

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

416

                Ok(d.clone())

417

418

419

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

420

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

421

                if matches!(

422

                    **inner1,

423

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

424

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

425

426

                Ok(d.clone())

427

428

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

429

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

430

                    && matches!(

431

                        **inner2,

432

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

433

                    ) =>

434

435

                Ok(d.clone())

436

437

438

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

439

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

440

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

441

                Ok(d.clone())

442

443

444

            // both arguments are non-empy

445

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

446

                SetAttr::default(),

447

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

448

)),

449

450

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

451

                // Intersect intervals, not their expanded values. In particular,

452

                // full machine-sized domains must not allocate billions of ints.

453

2086090

                if a.iter().chain(b).any(|range| !range.is_finite()) {

454

2

                    return Err(DomainOpError::Unbounded);

455

968166

456

968166

                let mut intersections = Vec::new();

457

968166

                for left in a {

458

1009824

                    for right in b {

459

1221021

                        let lo = *left

460

1221021

                            .low()

461

1221021

                            .ok_or(DomainOpError::Unbounded)?

462

1221021

                            .max(right.low().ok_or(DomainOpError::Unbounded)?);

463

1221021

                        let hi = *left

464

1221021

                            .high()

465

1221021

                            .ok_or(DomainOpError::Unbounded)?

466

1221021

                            .min(right.high().ok_or(DomainOpError::Unbounded)?);

467

1221021

                        if lo <= hi {

468

1028972

                            intersections.push((lo, hi));

469

192049

470

471

472

968166

                intersections.sort_unstable();

473

968166

                let mut merged: Vec<(i32, i32)> = Vec::new();

474

968166

                for (lo, hi) in intersections {

475

1028972

                    if let Some(last) = merged.last_mut()

476

65026

                        && i64::from(lo) <= i64::from(last.1) + 1

477

478

6147

                        last.1 = last.1.max(hi);

479

                    } else {

480

1022825

                        merged.push((lo, hi));

481

482

483

968166

                if merged.is_empty() {

484

4220

                    Ok(GroundDomain::Empty(ReturnType::Int))

485

                } else {

486

                    Ok(GroundDomain::Int(

487

963946

                        merged

488

963946

                            .into_iter()

489

1022825

                            .map(|(lo, hi)| Range::new(Some(lo), Some(hi)))

490

                            .collect(),

491

963946

                        None,

492

))

493

494

495

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

496

                todo!("Relation union not yet supported")

497

498

            _ => Err(DomainOpError::WrongType),

499

500

968256

501

502

24350727

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

503

24350727

        match self {

504

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

505

            GroundDomain::EnumeratedType(ty, ranges) => {

506

8

                let values = enum_indices(ty, ranges)

507

8

                    .map(|index| {

508

8

                        Literal::EnumVariant(crate::ast::enumerated::EnumVariant::new(

509

8

                            ty.clone(),

510

8

                            index,

511

8

))

512

8

})

513

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

514

8

                Ok(Box::new(values.into_iter()))

515

516

            GroundDomain::UnnamedType(ty) => {

517

40

                let ty = ty.clone();

518

80

                Ok(Box::new((1..=ty.size).map(move |value| {

519

80

                    Literal::Unnamed(crate::ast::unnamed::UnnamedValue {

520

80

                        ty: ty.clone(),

521

80

                        value,

522

80

})

523

80

                })))

524

525

61547

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

526

61547

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

527

61547

)),

528

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

529

23901439

                let rng_iters = rngs

530

23901439

                    .iter()

531

23901439

                    .map(Range::iter)

532

23901439

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

533

23901439

                    .ok_or(DomainOpError::Unbounded)?;

534

23850250

                Ok(Box::new(

535

24035792

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

536

))

537

538

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

539

                // Collect the possible values for each element

540

308244

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

541

308244

                    .iter()

542

616779

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

543

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

544

545

                // Generate all combinations in lexicographic order

546

308244

                let iter = elem_value_pools

547

308244

                    .into_iter()

548

308244

                    .multi_cartesian_product()

549

1249458

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

550

551

308244

                Ok(Box::new(iter))

552

553

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

554

                // Sort entries by name

555

6092

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

556

6092

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

557

558

12184

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

559

6092

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

560

6092

                    .iter()

561

12184

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

562

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

563

564

                // Generate all combinations in lexicographic order

565

6092

                let iter = value_pools

566

6092

                    .into_iter()

567

6092

                    .multi_cartesian_product()

568

24370

                    .map(move |vals| {

569

24370

                        let record_entries = names

570

24370

                            .iter()

571

24370

                            .cloned()

572

24370

                            .zip(vals)

573

48740

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

574

                            .collect();

575

24370

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

576

24370

});

577

578

6092

                Ok(Box::new(iter))

579

580

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

581

88

                let values = entries

582

88

                    .iter()

583

176

                    .map(|entry| {

584

176

                        let name = entry.name.clone();

585

176

                        entry.value.values().map(|values| {

586

265

                            values.map(move |value| {

587

265

                                Literal::AbstractLiteral(AbstractLiteral::Variant(Moo::new(

588

265

                                    Field {

589

265

                                        name: name.clone(),

590

265

                                        value,

591

265

},

592

265

)))

593

265

})

594

176

})

595

176

})

596

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

597

88

                Ok(Box::new(values.into_iter().flatten()))

598

599

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

600

62714

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

601

62714

                let idx_doms = idx_doms.clone();

602

603

                // Collect all possible element values

604

62714

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

605

606

                // Generate all possible cell assignments in lexicographic order

607

62714

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

608

62714

                    .multi_cartesian_product()

609

4513504

                    .map(move |flat_elems| {

610

4513504

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

611

4513504

});

612

613

62714

                Ok(Box::new(iter))

614

615

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

616

                if attrs.jectivity != JectivityAttr::None {

617

                    // Injective/surjective/bijective sequence enumeration is not yet needed by any

618

                    // in-scope case (the two exhaustive tests using it are deferred pending enum

619

                    // support), so it is left unimplemented rather than guessed at untested.

620

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

621

622

623

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

624

                let max_sz = attrs.size.high().copied().ok_or(DomainOpError::Unbounded)?;

625

626

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

627

628

                let iter = (min_sz..=max_sz)

629

                    .flat_map(move |sz| {

630

                        std::iter::repeat_n(pool.clone(), sz.max(0) as usize)

631

                            .multi_cartesian_product()

632

})

633

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

634

635

                Ok(Box::new(iter))

636

637

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

638

10553

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

639

10553

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

640

10553

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

641

642

10553

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

643

644

10553

                Ok(Box::new(

645

10553

                    (min_sz..=max_sz)

646

15455

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

647

31555

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

648

))

649

650

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

651

            GroundDomain::Function(..) => {

652

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

653

654

            GroundDomain::Relation(..) => {

655

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

656

657

            GroundDomain::Partition(attr, inner_dom) => {

658

1

                let elements: Vec<Literal> = inner_dom.values()?.collect();

659

1

                let n = elements.len();

660

661

1

                let block_lo = attr.part_len.low().copied().unwrap_or(1).max(1) as usize;

662

1

                let block_hi = attr

663

1

                    .part_len

664

1

                    .high()

665

1

                    .copied()

666

                    .map(|h| (h.max(0) as usize).min(n))

667

1

                    .unwrap_or(n);

668

1

                let parts_lo = attr.num_parts.low().copied().unwrap_or(0).max(0) as usize;

669

1

                let parts_hi = attr

670

1

                    .num_parts

671

1

                    .high()

672

1

                    .copied()

673

1

                    .map(|h| (h.max(0) as usize).min(n))

674

1

                    .unwrap_or(n);

675

1

                let is_regular = attr.is_regular;

676

677

1

                let partitions = if block_lo > block_hi {

678

                    vec![]

679

                } else {

680

1

                    restricted_partitions(&elements, block_lo, block_hi)

681

};

682

15

                let iter = partitions.into_iter().filter(move |parts| {

683

15

                    let k = parts.len();

684

15

                    if k < parts_lo || k > parts_hi {

685

2

                        return false;

686

13

687

13

                    !is_regular

688

                        || parts

689

                            .first()

690

                            .is_none_or(|first| parts.iter().all(|p| p.len() == first.len()))

691

15

});

692

13

                Ok(Box::new(iter.map(|parts| {

693

13

                    Literal::AbstractLiteral(AbstractLiteral::Partition(parts))

694

13

                })))

695

696

            GroundDomain::Permutation(attr, inner_dom) => {

697

1

                let elements: Vec<Literal> = inner_dom.values()?.collect();

698

1

                let n = elements.len();

699

700

1

                let moved_lo = attr.num_moved.low().copied().unwrap_or(0).max(0) as usize;

701

1

                let moved_hi = attr

702

1

                    .num_moved

703

1

                    .high()

704

1

                    .copied()

705

1

                    .map(|h| (h.max(0) as usize).min(n))

706

1

                    .unwrap_or(n);

707

708

1

                if moved_lo > moved_hi {

709

                    return Ok(Box::new(std::iter::empty()));

710

1

711

                let mappings: Vec<Vec<Literal>> =

712

1

                    restricted_permutations(&elements, moved_lo, moved_hi).collect();

713

3

                let values = mappings.into_iter().map(move |mapped| {

714

3

                    let cycles = permutation_mapping_to_cycles(&elements, &mapped);

715

3

                    Literal::AbstractLiteral(AbstractLiteral::Permutation(cycles))

716

3

});

717

1

                Ok(Box::new(values.collect_vec().into_iter()))

718

719

720

24350727

721

722

    /// Gets the length of this domain.

723

///

724

    /// # Errors

725

///

726

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

727

13905463

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

728

13905463

        match self {

729

48

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

730

5090535

            GroundDomain::Bool => Ok(2),

731

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

732

7456893

                if ranges.is_empty() {

733

271

                    return Ok(0);

734

7456622

735

736

7456622

                let mut length = 0u64;

737

7456622

                for range in ranges {

738

7648325

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

739

7648315

                        length += range_length as u64;

740

                    } else {

741

10

                        return Err(DomainOpError::Unbounded);

742

743

744

7456612

                Ok(length)

745

746

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

747

394402

                let mut ans = 1u64;

748

394402

                for domain in domains {

749

792024

                    ans = ans

750

792024

                        .checked_mul(domain.length()?)

751

792024

                        .ok_or(DomainOpError::TooLarge)?;

752

753

394402

                Ok(ans)

754

755

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

756

                // A record is just a named tuple

757

5802

                let mut ans = 1u64;

758

5802

                for entry in entries {

759

11604

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

760

11604

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

761

762

5802

                Ok(ans)

763

764

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

765

22824

                let mut ans = 0u64;

766

22824

                for entry in entries {

767

45648

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

768

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

769

45648

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

770

771

22824

                Ok(ans)

772

773

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

774

780960

                let inner_sz = inner_domain.length()?;

775

882859

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

776

882859

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

777

882859

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

778

882859

                })?;

779

780960

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

780

781

            GroundDomain::Sequence(seq_attr, inner_domain) => {

782

145

                if seq_attr.jectivity != JectivityAttr::None {

783

                    // See the matching note on `values()` above: not yet needed by any in-scope case.

784

                    todo!("Length bound of jective sequences is not yet supported");

785

145

786

787

145

                let inner_len = inner_domain.length()?;

788

145

                let min_sz = seq_attr.size.low().copied().unwrap_or(0).max(0) as u64;

789

145

                let max_sz = seq_attr

790

145

                    .size

791

145

                    .high()

792

145

                    .copied()

793

145

                    .ok_or(DomainOpError::Unbounded)? as u64;

794

795

145

                if min_sz > max_sz {

796

                    return Ok(0);

797

145

798

799

145

                let mut ans = 0u64;

800

145

                for sz in min_sz..=max_sz {

801

725

                    let sz: u32 = sz.try_into().map_err(|_| DomainOpError::TooLarge)?;

802

725

                    let c = inner_len.checked_pow(sz).ok_or(DomainOpError::TooLarge)?;

803

725

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

804

805

145

                Ok(ans)

806

807

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

808

106067

                let inner_len = inner_domain.length()?;

809

106065

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

810

13897

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

811

78417

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

812

1

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

813

9138

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

814

4612

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

815

};

816

                // Attributes may overshoot the inner domain (e.g. maxSize 3 of int(1..2));

817

                // only cardinalities that fit can contribute members.

818

106065

                let max_sz = max_sz.min(inner_len);

819

106065

                if min_sz > max_sz {

820

                    return Ok(0);

821

106065

822

106065

                let mut ans = 0u64;

823

106065

                for sz in min_sz..=max_sz {

824

167759

                    let c = count_combinations(inner_len, sz)?;

825

167758

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

826

827

106064

                Ok(ans)

828

829

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

830

                let inner_len = inner_domain.length()?;

831

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

832

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

833

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

834

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

835

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

836

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

837

};

838

                let mut ans = 0u64;

839

                for sz in min_sz..=max_sz {

840

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

841

                    // Where n=inner_len and k=sz

842

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

843

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

844

845

                Ok(ans)

846

847

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

848

817

                let domain_len = domain.length()?;

849

817

                let codomain_len = codomain.length()?;

850

851

817

                match (attr.partiality.clone(), attr.jectivity.clone()) {

852

                    (PartialityAttr::Total, JectivityAttr::None) => {

853

                        let exp: u32 = domain_len.try_into()?;

854

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

855

856

                    (PartialityAttr::Total, JectivityAttr::Injective) => {

857

1

                        if domain_len > codomain_len {

858

                            return Ok(0);

859

1

860

1

                        Ok(count_permutations(codomain_len, domain_len)?)

861

862

                    (PartialityAttr::Total, JectivityAttr::Bijective) => {

863

814

                        if domain_len != codomain_len {

864

1

                            return Ok(0);

865

813

866

813

                        Ok(count_permutations(domain_len, domain_len)?)

867

868

                    (PartialityAttr::Total, JectivityAttr::Surjective) => {

869

1

                        let partitions = stirling_second_kind(domain_len, codomain_len)?;

870

1

                        let arrangements = count_permutations(codomain_len, codomain_len)?;

871

1

                        partitions

872

1

                            .checked_mul(arrangements)

873

1

                            .ok_or(DomainOpError::TooLarge)

874

875

                    (PartialityAttr::Partial, jectivity) => {

876

1

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

877

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

878

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

879

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

880

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

881

1

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

882

};

883

1

                        let max_sz = max_sz.min(domain_len);

884

1

                        if min_sz > max_sz {

885

                            return Ok(0);

886

1

887

888

1

                        let mut ans = 0u64;

889

1

                        for sz in min_sz..=max_sz {

890

                            // Choose which `sz` domain elements are defined, then count the ways

891

                            // to map exactly those `sz` elements per the jectivity requirement.

892

3

                            let choose = count_combinations(domain_len, sz)?;

893

3

                            let assign = match jectivity {

894

                                JectivityAttr::None => codomain_len

895

                                    .checked_pow(sz.try_into()?)

896

                                    .ok_or(DomainOpError::TooLarge)?,

897

                                JectivityAttr::Injective => {

898

3

                                    if sz > codomain_len {

899

900

                                    } else {

901

3

                                        count_permutations(codomain_len, sz)?

902

903

904

                                JectivityAttr::Bijective => {

905

                                    if sz != codomain_len {

906

907

                                    } else {

908

                                        count_permutations(codomain_len, codomain_len)?

909

910

911

                                JectivityAttr::Surjective => {

912

                                    let partitions = stirling_second_kind(sz, codomain_len)?;

913

                                    let arrangements =

914

                                        count_permutations(codomain_len, codomain_len)?;

915

                                    partitions

916

                                        .checked_mul(arrangements)

917

                                        .ok_or(DomainOpError::TooLarge)?

918

919

};

920

3

                            let term = choose.checked_mul(assign).ok_or(DomainOpError::TooLarge)?;

921

3

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

922

923

1

                        Ok(ans)

924

925

926

927

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

928

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

929

93844

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

930

46922

                let dom_sizes = dom_sizes_result?;

931

46922

                let inner_len: u64 = dom_sizes.iter().product();

932

933

46922

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

934

580

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

935

45559

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

936

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

937

464

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

938

319

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

939

};

940

46922

                let max_sz = max_sz.min(inner_len);

941

46922

                if min_sz > max_sz {

942

                    return Ok(0);

943

46922

944

945

46922

                let mut ans = 0u64;

946

46922

                for sz in min_sz..=max_sz {

947

50518

                    let c = count_combinations(inner_len, sz)?;

948

50518

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

949

950

46922

                Ok(ans)

951

952

            GroundDomain::Partition(attr, inner_domain) => {

953

5

                let n = inner_domain.length()?;

954

5

                let block_lo = attr.part_len.low().copied().unwrap_or(1).max(1) as u64;

955

5

                let block_hi = attr

956

5

                    .part_len

957

5

                    .high()

958

5

                    .copied()

959

1

                    .map(|h| (h.max(0) as u64).min(n))

960

5

                    .unwrap_or(n);

961

5

                let parts_lo = attr.num_parts.low().copied().unwrap_or(0).max(0) as u64;

962

5

                let parts_hi = attr

963

5

                    .num_parts

964

5

                    .high()

965

5

                    .copied()

966

3

                    .map(|h| (h.max(0) as u64).min(n))

967

5

                    .unwrap_or(n);

968

5

                if block_lo > block_hi || parts_lo > parts_hi {

969

                    return Ok(0);

970

5

971

972

5

                if attr.is_regular {

973

1

                    let mut ans = 0u64;

974

1

                    for block_size in block_lo..=block_hi {

975

1

                        if n % block_size != 0 {

976

                            continue;

977

1

978

1

                        let num_parts = n / block_size;

979

1

                        if num_parts < parts_lo || num_parts > parts_hi {

980

                            continue;

981

1

982

1

                        let c = regular_partition_count(n, block_size)?;

983

1

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

984

985

1

                    Ok(ans)

986

                } else {

987

4

                    let mut ans = 0u64;

988

4

                    for num_parts in parts_lo..=parts_hi {

989

9

                        let c = restricted_partition_count(n, num_parts, block_lo, block_hi)?;

990

9

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

991

992

4

                    Ok(ans)

993

994

995

            GroundDomain::Permutation(attr, inner_domain) => {

996

3

                let n = inner_domain.length()?;

997

3

                let moved_lo = attr.num_moved.low().copied().unwrap_or(0).max(0) as u64;

998

3

                let moved_hi = attr

999

3

                    .num_moved

1000

3

                    .high()

1001

3

                    .copied()

1002

2

                    .map(|h| (h.max(0) as u64).min(n))

1003

3

                    .unwrap_or(n);

1004

3

                if moved_lo > moved_hi {

1005

                    return Ok(0);

1006

3

1007

1008

3

                let mut ans = 0u64;

1009

3

                for moved in moved_lo..=moved_hi {

1010

8

                    let choose = count_combinations(n, moved)?;

1011

8

                    let derange = derangements(moved)?;

1012

8

                    let term = choose.checked_mul(derange).ok_or(DomainOpError::TooLarge)?;

1013

8

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

1014

1015

3

                Ok(ans)

1016

1017

8

            GroundDomain::EnumeratedType(et, ranges) => Ok(enum_indices(et, ranges).count() as u64),

1018

32

            GroundDomain::UnnamedType(ty) => Ok(ty.size as u64),

1019

1020

13905463

1021

1022

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

1023

89104

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

1024

89104

        self.length()?

1025

            .try_into()

1026

            .map_err(|_| DomainOpError::TooLarge)

1027

89104

1028

1029

64533569

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

1030

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

1031

        // error when a domain is added.

1032

64533569

        match self {

1033

            // empty domain can't contain anything

1034

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

1035

1655374

            GroundDomain::Bool => match lit {

1036

1655366

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

1037

8

                _ => Ok(false),

1038

},

1039

47321064

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

1040

                Literal::Int(x) => {

1041

47321064

                    if ranges.is_empty() {

1042

                        return Ok(false);

1043

47321064

};

1044

1045

47967499

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

1046

1047

                _ => Ok(false),

1048

},

1049

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

1050

7878343

                match lit {

1051

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

1052

7878343

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

1053

                            return Ok(false);

1054

7878343

1055

1056

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

1057

7878343

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

1058

15851690

                            if !elem_domain.contains(elem)? {

1059

                                return Ok(false);

1060

15851690

1061

1062

1063

7878343

                        Ok(true)

1064

1065

                    _ => Ok(false),

1066

1067

1068

362766

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

1069

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

1070

362766

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

1071

                        return Ok(false);

1072

362766

1073

1074

362766

                    let fields = lit_entries

1075

362766

                        .iter()

1076

725532

                        .map(|field| (&field.name, &field.value))

1077

                        .collect::<BTreeMap<_, _>>();

1078

362766

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

1079

                        return Ok(false);

1080

362766

1081

362766

                    for entry in entries {

1082

725532

                        let Some(value) = fields.get(&entry.name) else {

1083

                            return Ok(false);

1084

};

1085

725532

                        if !entry.value.contains(value)? {

1086

1

                            return Ok(false);

1087

725531

1088

1089

362765

                    Ok(true)

1090

1091

                _ => Ok(false),

1092

},

1093

567705

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

1094

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

1095

845265

                    let Some(entry) = entries.iter().find(|entry| entry.name == lit_entry.name)

1096

                    else {

1097

                        return Ok(false);

1098

};

1099

567705

                    entry.value.contains(&lit_entry.value)

1100

1101

                _ => Ok(false),

1102

},

1103

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

1104

5195757

                match lit {

1105

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

1106

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

1107

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

1108

1109

5195757

                        if elems.is_empty()

1110

87

                            && index_domains

1111

87

                                .iter()

1112

87

                                .any(|index_domain| index_domain.length() == Ok(0))

1113

1114

87

                            return Ok(true);

1115

5195670

1116

1117

                        let Some((current_index_domain, remaining_index_domains)) =

1118

5195670

                            index_domains.split_first()

1119

                        else {

1120

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

1121

};

1122

1123

5195670

                        if *current_index_domain != *idx_domain {

1124

                            return Ok(false);

1125

5195670

};

1126

1127

5195670

                        let next_elem_domain = if remaining_index_domains.is_empty() {

1128

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

1129

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

1130

3389771

                            elem_domain.as_ref().clone()

1131

                        } else {

1132

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

1133

1805899

                            GroundDomain::Matrix(

1134

1805899

                                elem_domain.clone(),

1135

1805899

                                remaining_index_domains.to_vec(),

1136

1805899

                                None,

1137

1805899

1138

};

1139

1140

5195670

                        for elem in elems {

1141

10871118

                            if !next_elem_domain.contains(elem)? {

1142

                                return Ok(false);

1143

10871118

1144

1145

1146

5195670

                        Ok(true)

1147

1148

                    _ => Ok(false),

1149

1150

1151

336313

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

1152

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

1153

336313

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

1154

336313

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

1155

                        return Ok(false);

1156

336313

1157

1158

336313

                    for elem in elems {

1159

37584

                        if !inner_dom.contains(elem)? {

1160

                            return Ok(false);

1161

37584

1162

1163

336313

                    Ok(true)

1164

1165

                _ => Ok(false),

1166

},

1167

507974

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

1168

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

1169

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

1170

507974

                    let sz = crate::ast::literals::distinct_literal_count(lit_elems)

1171

507974

                        .to_i32()

1172

507974

                        .ok_or(DomainOpError::TooLarge)?;

1173

507974

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

1174

                        return Ok(false);

1175

507974

1176

1177

507974

                    for elem in lit_elems {

1178

991495

                        if !inner_domain.contains(elem)? {

1179

87

                            return Ok(false);

1180

991408

1181

1182

507887

                    Ok(true)

1183

1184

                _ => Ok(false),

1185

},

1186

686778

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

1187

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

1188

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

1189

686778

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

1190

686778

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

1191

                        return Ok(false);

1192

686778

1193

1194

686778

                    for elem in lit_elems {

1195

915704

                        if !inner_domain.contains(elem)? {

1196

                            return Ok(false);

1197

915704

1198

1199

686778

                    Ok(true)

1200

1201

                _ => Ok(false),

1202

},

1203

7904

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

1204

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

1205

7904

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

1206

7904

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

1207

                        return Ok(false);

1208

7904

1209

7904

                    for lit in lit_elems {

1210

7392

                        let domain_element = &lit.0;

1211

7392

                        let codomain_element = &lit.1;

1212

7392

                        if !domain.contains(domain_element)? {

1213

                            return Ok(false);

1214

7392

1215

7392

                        if !codomain.contains(codomain_element)? {

1216

                            return Ok(false);

1217

7392

1218

1219

7904

                    Ok(true)

1220

1221

                _ => Ok(false),

1222

},

1223

2117

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

1224

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

1225

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

1226

2117

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

1227

2117

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

1228

                        return Ok(false);

1229

2117

1230

1231

2117

                    for elem_tuple in lit_elems {

1232

6351

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

1233

6351

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

1234

12702

                                if !inner_dom.contains(elem)? {

1235

                                    return Ok(false);

1236

12702

1237

1238

                        } else {

1239

                            return Ok(false);

1240

1241

1242

2117

                    Ok(true)

1243

1244

                _ => Ok(false),

1245

},

1246

16

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

1247

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

1248

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

1249

16

                    let sz: i32 = lit_elems

1250

16

                        .iter()

1251

16

                        .flatten()

1252

16

                        .count()

1253

16

                        .to_i32()

1254

16

                        .ok_or(DomainOpError::TooLarge)?;

1255

1256

16

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

1257

2

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

1258

14

                        _ => None,

1259

};

1260

1261

16

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

1262

2

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

1263

14

                        _ => None,

1264

};

1265

1266

16

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

1267

16

                    if !rng.contains(&sz) {

1268

1

                        return Ok(false);

1269

15

1270

1271

15

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

1272

62

                        if !dom.contains(elem)? {

1273

                            return Ok(false);

1274

62

1275

1276

15

                    Ok(true)

1277

1278

                _ => Ok(false),

1279

},

1280

            GroundDomain::EnumeratedType(ty, ranges) => Ok(matches!(lit,

1281

                Literal::EnumVariant(value) if value.ty == *ty && (value.variant as usize) < ty.len()

1282

                && (ranges.is_empty() || ranges.iter().any(|range| range.contains(&value.variant)))

1283

)),

1284

            GroundDomain::UnnamedType(ty) => Ok(

1285

                matches!(lit, Literal::Unnamed(value) if value.ty == *ty && (1..=ty.size).contains(&value.value)),

1286

),

1287

11458

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

1288

                Literal::AbstractLiteral(AbstractLiteral::Permutation(cycles)) => {

1289

                    // numMoved is the count of moved points (elements mentioned in some cycle),

1290

                    // matching cycle notation's "unmentioned = fixed point" semantics -- not the

1291

                    // inner domain's own size.

1292

11458

                    let sz: i32 = cycles

1293

11458

                        .iter()

1294

11458

                        .flatten()

1295

11458

                        .count()

1296

11458

                        .to_i32()

1297

11458

                        .ok_or(DomainOpError::TooLarge)?;

1298

11458

                    if !attr.num_moved.contains(&sz) {

1299

                        return Ok(false);

1300

11458

1301

1302

11458

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

1303

34545

                        if !dom.contains(elem)? {

1304

                            return Ok(false);

1305

34545

1306

1307

11458

                    Ok(true)

1308

1309

                _ => Ok(false),

1310

},

1311

1312

64533569

1313

1314

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

1315

///

1316

    /// # Errors

1317

///

1318

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

1319

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

1320

827480

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

1321

827480

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

1322

4453

            return Ok(vec![]);

1323

823027

1324

823027

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

1325

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

1326

};

1327

1328

823027

        if ranges.is_empty() {

1329

            return Ok(vec![]);

1330

823027

1331

1332

823027

        let mut values = vec![];

1333

823027

        for range in ranges {

1334

862088

            match range {

1335

                Range::Single(i) => {

1336

81627

                    values.push(*i);

1337

1338

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

1339

780461

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

1340

1341

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

1342

                    return Err(DomainOpError::Unbounded);

1343

1344

1345

1346

1347

823027

        Ok(values)

1348

827480

1349

1350

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

1351

///

1352

    /// # Examples

1353

///

1354

    /// ```

1355

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

1356

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

1357

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

1358

///

1359

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

1360

///

1361

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

1362

///

1363

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

1364

    /// ```

1365

///

1366

    /// ```

1367

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

1368

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

1369

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

1370

///

1371

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

1372

///

1373

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

1374

///

1375

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

1376

    /// ```

1377

///

1378

    /// ```

1379

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

1380

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

1381

///

1382

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

1383

///

1384

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

1385

///

1386

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

1387

    /// ```

1388

1444461

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

1389

1444461

        if elements.is_empty() {

1390

29

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

1391

1444432

1392

1444432

        if elements.len() == 1 {

1393

698990

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

1394

745442

1395

1396

745442

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

1397

1398

745442

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

1399

1400

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

1401

        // numbers into ranges.

1402

1403

        // the bounds of the current run of numbers.

1404

745442

        let mut lower = elems_iter

1405

745442

            .next()

1406

745442

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

1407

745442

        let mut upper = lower;

1408

1409

745442

        for current in elems_iter {

1410

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

1411

1412

1911098

            if current == upper + 1 {

1413

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

1414

//

1415

1821618

                upper = current;

1416

            } else {

1417

                // the run lower..upper has ended.

1418

//

1419

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

1420

1421

89480

                if lower == upper {

1422

89053

                    ranges.push(range!(lower));

1423

                } else {

1424

427

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

1425

1426

1427

89480

                lower = current;

1428

89480

                upper = current;

1429

1430

1431

1432

        // add the final run to the domain

1433

745442

        if lower == upper {

1434

79654

            ranges.push(range!(lower));

1435

        } else {

1436

665788

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

1437

1438

1439

745442

        ranges = Range::squeeze(&ranges);

1440

745442

        GroundDomain::Int(ranges, None)

1441

1444461

1442

1443

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

1444

///

1445

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

1446

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

1447

///

1448

    /// # Errors

1449

///

1450

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

1451

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

1452

2

    pub fn apply_i32(

1453

2

        &self,

1454

2

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

1455

2

        other: &GroundDomain,

1456

2

    ) -> Result<GroundDomain, DomainOpError> {

1457

2

        let vs1 = self.values_i32()?;

1458

2

        let vs2 = other.values_i32()?;

1459

1460

2

        let mut set = BTreeSet::new();

1461

2

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

1462

32

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

1463

28

                set.insert(v);

1464

4

1465

1466

1467

2

        Ok(GroundDomain::from_set_i32(&set))

1468

2

1469

1470

    /// Returns true if the domain is finite.

1471

    pub fn is_finite(&self) -> bool {

1472

        for domain in self.universe() {

1473

            if let GroundDomain::Int(ranges, _) = domain

1474

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

1475

                    matches!(

1476

                        range,

1477

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

1478

1479

})

1480

1481

                return false;

1482

1483

1484

        true

1485

1486

1487

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

1488

///

1489

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

1490

///

1491

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

1492

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

1493

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

1494

///

1495

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

1496

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

1497

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

1498

///

1499

    /// # Errors

1500

///

1501

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

1502

    ///   each-other, as described above.

1503

///

1504

    /// # Examples

1505

///

1506

    /// ```

1507

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

1508

///

1509

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

1510

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

1511

    /// ```

1512

///

1513

    /// ```

1514

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

1515

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

1516

///

1517

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

1518

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

1519

///

1520

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

1521

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

1522

///

1523

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

1524

///

1525

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

1526

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

1527

///

1528

    /// assert_eq!(domain,expected_domain);

1529

    /// ```

1530

///

1531

    /// ```

1532

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

1533

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

1534

///

1535

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

1536

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

1537

///

1538

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

1539

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

1540

///

1541

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

1542

///

1543

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

1544

    /// ```

1545

///

1546

    /// ```

1547

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

1548

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

1549

///

1550

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

1551

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

1552

///

1553

///

1554

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

1555

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

1556

///

1557

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

1558

///

1559

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

1560

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

1561

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

1562

    ///     None));

1563

///

1564

    /// assert_eq!(domain,expected_domain);

1565

    /// ```

1566

///

1567

///

1568

3706649

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

1569

        // TODO: use proptest to test this better?

1570

1571

3706649

        if literals.is_empty() {

1572

179568

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

1573

3527081

1574

1575

3527081

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

1576

1577

3527081

        match first_literal {

1578

            Literal::Int(_) => {

1579

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

1580

1444280

                let mut ints = BTreeSet::new();

1581

1444280

                for lit in literals {

1582

3508890

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

1583

                        return Err(DomainOpError::WrongType);

1584

};

1585

1586

3508890

                    ints.insert(*i);

1587

1588

1589

1444280

                Ok(GroundDomain::from_set_i32(&ints))

1590

1591

            Literal::Bool(_) => {

1592

                // check all literals are bools

1593

807389

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

1594

                    Err(DomainOpError::WrongType)

1595

                } else {

1596

392921

                    Ok(GroundDomain::Bool)

1597

1598

1599

            Literal::Unnamed(first) => {

1600

                if literals

1601

                    .iter()

1602

                    .all(|value| matches!(value, Literal::Unnamed(value) if value.ty == first.ty))

1603

1604

                    Ok(GroundDomain::UnnamedType(first.ty.clone()))

1605

                } else {

1606

                    Err(DomainOpError::WrongType)

1607

1608

1609

            Literal::EnumVariant(first_ev) => {

1610

                let mut variants = BTreeSet::new();

1611

1612

                for lit in literals {

1613

                    let Literal::EnumVariant(current_ev) = lit else {

1614

                        return Err(DomainOpError::WrongType);

1615

};

1616

1617

                    if current_ev.ty != first_ev.ty {

1618

                        return Err(DomainOpError::WrongType);

1619

1620

1621

                    variants.insert(current_ev.variant);

1622

1623

1624

                Ok(GroundDomain::EnumeratedType(

1625

                    first_ev.ty.clone(),

1626

                    variants.into_iter().map(Range::Single).collect(),

1627

))

1628

1629

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

1630

138029

                let mut all_elems = vec![];

1631

1632

138029

                for lit in literals {

1633

138551

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

1634

                        return Err(DomainOpError::WrongType);

1635

};

1636

1637

138551

                    all_elems.extend(elems.clone());

1638

1639

138029

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

1640

1641

138029

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

1642

1643

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

1644

242295

                let mut all_elems = vec![];

1645

1646

242295

                for lit in literals {

1647

242295

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

1648

                        return Err(DomainOpError::WrongType);

1649

};

1650

1651

242295

                    all_elems.extend(elems.clone());

1652

1653

242295

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

1654

1655

242295

                Ok(GroundDomain::MSet(

1656

242295

                    MSetAttr::default(),

1657

242295

                    Moo::new(elem_domain),

1658

242295

))

1659

1660

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

1661

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

1662

1663

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

1664

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

1665

1666

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

1667

932236

                let mut first_index_domain = vec![];

1668

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

1669

932236

                let mut l = l.clone();

1670

1864618

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

1671

                    bug_assert!(

1672

932382

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

1673

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

1674

);

1675

932382

                    first_index_domain.push(idx);

1676

932382

                    let Some(first_elem) = elems.first() else {

1677

                        break;

1678

};

1679

932382

                    l = first_elem.clone();

1680

1681

1682

932236

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

1683

1684

                // check types and index domains

1685

932236

                for lit in literals {

1686

932323

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

1687

                        return Err(DomainOpError::NotGround);

1688

};

1689

1690

932323

                    all_elems.extend(elems.clone());

1691

1692

932323

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

1693

932323

                    let Some(first_elem) = elems.first() else {

1694

                        if index_domain != first_index_domain {

1695

                            return Err(DomainOpError::WrongType);

1696

1697

                        continue;

1698

};

1699

932323

                    let mut l = first_elem.clone();

1700

932498

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

1701

                        bug_assert!(

1702

175

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

1703

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

1704

);

1705

175

                        index_domain.push(idx);

1706

175

                        let Some(first_elem) = elems.first() else {

1707

                            break;

1708

};

1709

175

                        l = first_elem.clone();

1710

1711

1712

932323

                    if index_domain != first_index_domain {

1713

29

                        return Err(DomainOpError::WrongType);

1714

932294

1715

1716

1717

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

1718

932207

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

1719

3992301

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

1720

3060094

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

1721

669

                        all_elems.extend(elems);

1722

                    } else {

1723

3059425

                        terminal_elements.push(elem);

1724

1725

1726

1727

932207

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

1728

1729

932207

                Ok(GroundDomain::Matrix(

1730

932207

                    Moo::new(element_domain),

1731

932207

                    first_index_domain,

1732

932207

                    None,

1733

932207

))

1734

1735

1736

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

1737

267902

                let n_fields = first_elems.len();

1738

1739

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

1740

267902

                let mut elem_domains = vec![];

1741

1742

267902

                for i in 0..n_fields {

1743

628372

                    let mut all_elems = vec![];

1744

628372

                    for lit in literals {

1745

636724

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

1746

                            return Err(DomainOpError::NotGround);

1747

};

1748

1749

636724

                        if elems.len() != n_fields {

1750

                            return Err(DomainOpError::NotGround);

1751

636724

1752

1753

636724

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

1754

1755

1756

628372

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

1757

1758

1759

267902

                Ok(GroundDomain::Tuple(elem_domains, None))

1760

1761

1762

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

1763

70441

                let mut all_elems = vec![];

1764

70441

                let mut lengths = Vec::new();

1765

1766

70441

                for lit in literals {

1767

70441

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

1768

                        return Err(DomainOpError::WrongType);

1769

};

1770

1771

70441

                    lengths.push(i32::try_from(elems.len()).map_err(|_| DomainOpError::TooLarge)?);

1772

70441

                    all_elems.extend(elems.clone());

1773

1774

70441

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

1775

1776

                // These literals are known values, so their lengths bound the size attribute --

1777

                // without which nothing downstream can tell how many positions to iterate over.

1778

70441

                let min = lengths.iter().copied().min().unwrap_or(0);

1779

70441

                let max = lengths.iter().copied().max().unwrap_or(0);

1780

70441

                let size = if min == max {

1781

70441

                    Range::Single(min)

1782

                } else {

1783

                    Range::Bounded(min, max)

1784

};

1785

1786

70441

                Ok(GroundDomain::Sequence(

1787

70441

                    SequenceAttr {

1788

70441

                        size,

1789

70441

                        ..SequenceAttr::default()

1790

70441

},

1791

70441

                    Moo::new(elem_domain),

1792

70441

))

1793

1794

1795

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

1796

22040

                let n_fields = first_elems.len();

1797

44080

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

1798

1799

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

1800

22040

                let mut elem_domains = vec![];

1801

1802

22040

                for i in 0..n_fields {

1803

44080

                    let mut all_elems = vec![];

1804

44080

                    for lit in literals {

1805

44080

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

1806

                            return Err(DomainOpError::NotGround);

1807

};

1808

1809

44080

                        if elems.len() != n_fields {

1810

                            return Err(DomainOpError::NotGround);

1811

44080

1812

1813

44080

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

1814

44080

                        if elem.name != field_names[i] {

1815

                            return Err(DomainOpError::NotGround);

1816

44080

1817

1818

44080

                        all_elems.push(elem.value);

1819

1820

1821

44080

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

1822

1823

1824

                Ok(GroundDomain::Record(

1825

22040

                    izip!(field_names, elem_domains)

1826

44080

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

1827

                        .collect(),

1828

22040

                    None,

1829

))

1830

1831

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

1832

                let mut all_keys = vec![];

1833

                let mut all_values = vec![];

1834

1835

                for lit in literals {

1836

                    let Literal::AbstractLiteral(AbstractLiteral::Function(pairs)) = lit else {

1837

                        return Err(DomainOpError::WrongType);

1838

};

1839

1840

                    for (key, value) in pairs {

1841

                        all_keys.push(key.clone());

1842

                        all_values.push(value.clone());

1843

1844

1845

1846

                let domain = GroundDomain::from_literal_vec(&all_keys)?;

1847

                let codomain = GroundDomain::from_literal_vec(&all_values)?;

1848

1849

                Ok(GroundDomain::Function(

1850

                    FuncAttr::default(),

1851

                    Moo::new(domain),

1852

                    Moo::new(codomain),

1853

))

1854

1855

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

1856

16937

                let mut alternatives: Vec<(Name, Vec<Literal>)> = Vec::new();

1857

16937

                for literal in literals {

1858

42343

                    let Literal::AbstractLiteral(AbstractLiteral::Variant(field)) = literal else {

1859

                        return Err(DomainOpError::WrongType);

1860

};

1861

42343

                    if let Some((_, values)) = alternatives

1862

42343

                        .iter_mut()

1863

33874

                        .find(|(name, _)| name == &field.name)

1864

1865

16937

                        values.push(field.value.clone());

1866

                    } else {

1867

25406

                        alternatives.push((field.name.clone(), vec![field.value.clone()]));

1868

1869

1870

1871

                Ok(GroundDomain::Variant(

1872

16937

                    alternatives

1873

16937

                        .into_iter()

1874

25406

                        .map(|(name, values)| {

1875

                            Ok(FieldGround {

1876

25406

                                name,

1877

25406

                                value: Moo::new(GroundDomain::from_literal_vec(&values)?),

1878

})

1879

25406

})

1880

                        .collect::<Result<Vec<_>, DomainOpError>>()?,

1881

16937

                    None,

1882

))

1883

1884

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

1885

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

1886

                for lit in literals {

1887

                    let Literal::AbstractLiteral(AbstractLiteral::Relation(tuples)) = lit else {

1888

                        return Err(DomainOpError::WrongType);

1889

};

1890

                    for tuple in tuples {

1891

                        if columns.is_empty() {

1892

                            columns = vec![Vec::new(); tuple.len()];

1893

1894

                        if tuple.len() != columns.len() {

1895

                            return Err(DomainOpError::NotGround);

1896

1897

                        for (column, field) in columns.iter_mut().zip(tuple) {

1898

                            column.push(field.clone());

1899

1900

1901

1902

1903

                let inner_domains = columns

1904

                    .iter()

1905

                    .map(|column| GroundDomain::from_literal_vec(column).map(Moo::new))

1906

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

1907

1908

                Ok(GroundDomain::Relation(RelAttr::default(), inner_domains))

1909

1910

1911

3706649

1912

1913

176871

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

1914

176871

        match self {

1915

7656

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

1916

166315

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

1917

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

1918

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

1919

2900

                Some(Moo::new(GroundDomain::Tuple(inner_doms.clone(), None)))

1920

1921

            // A sequence is a function from int(1..|s|), and iterating a function yields its

1922

            // pairs, so iterating a sequence yields (position, value).

1923

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

1924

                let max = match attr.size {

1925

                    Range::Single(max) | Range::UnboundedL(max) | Range::Bounded(_, max) => max,

1926

                    Range::UnboundedR(_) | Range::Unbounded => return None,

1927

};

1928

                Some(Moo::new(GroundDomain::Tuple(

1929

                    vec![

1930

                        Moo::new(GroundDomain::Int(vec![Range::Bounded(1, max)], None)),

1931

                        inner.clone(),

1932

],

1933

                    None,

1934

)))

1935

1936

            _ => None,

1937

1938

176871

1939

1940

    /// True if any domain in this tree has a representation preference.

1941

90

    pub fn has_representation_preference(&self) -> bool {

1942

90

        match self {

1943

            GroundDomain::Empty(_)

1944

            | GroundDomain::EnumeratedType(_, _)

1945

            | GroundDomain::UnnamedType(_) => false,

1946

            GroundDomain::Bool => false,

1947

            GroundDomain::Int(_, representation) => representation.is_some(),

1948

            GroundDomain::Tuple(inners, representation) => {

1949

                representation.is_some() || inners.iter().any(|d| d.has_representation_preference())

1950

1951

            GroundDomain::Record(entries, representation) => {

1952

30

                representation.is_some()

1953

30

                    || entries

1954

30

                        .iter()

1955

30

                        .any(|f| f.value.has_representation_preference())

1956

1957

            GroundDomain::Variant(entries, representation) => {

1958

                representation.is_some()

1959

                    || entries

1960

                        .iter()

1961

                        .any(|f| f.value.has_representation_preference())

1962

1963

            GroundDomain::Matrix(inner, idxs, representation) => {

1964

30

                representation.is_some()

1965

30

                    || inner.has_representation_preference()

1966

                    || idxs.iter().any(|d| d.has_representation_preference())

1967

1968

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

1969

                attr.representation.is_some() || inner.has_representation_preference()

1970

1971

            GroundDomain::Set(attr, inner) => {

1972

                attr.representation.is_some() || inner.has_representation_preference()

1973

1974

            GroundDomain::MSet(attr, inner) => {

1975

30

                attr.representation.is_some() || inner.has_representation_preference()

1976

1977

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

1978

                attr.representation.is_some()

1979

                    || dom.has_representation_preference()

1980

                    || cdom.has_representation_preference()

1981

1982

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

1983

                attr.representation.is_some()

1984

                    || inners.iter().any(|d| d.has_representation_preference())

1985

1986

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

1987

                attr.representation.is_some() || inner.has_representation_preference()

1988

1989

            GroundDomain::Permutation(attr, inner) => {

1990

                attr.representation.is_some() || inner.has_representation_preference()

1991

1992

1993

90

1994

1995

    /// Format this domain in Essence type style, omitting size attributes and integer ranges.

1996

2443

    pub fn as_type_string(&self) -> String {

1997

2443

        match self {

1998

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

1999

            GroundDomain::EnumeratedType(ty, _) => ty.to_string(),

2000

            GroundDomain::UnnamedType(_) => "unnamed type".to_string(),

2001

            GroundDomain::Bool => "bool".to_string(),

2002

1598

            GroundDomain::Int(_, representation) => int_type_string(representation.as_deref()),

2003

            GroundDomain::Tuple(inners, representation) => {

2004

                let args = representation

2005

                    .iter()

2006

                    .map(|r| format!("representation {r}"))

2007

                    .chain(inners.iter().map(|d| d.as_type_string()))

2008

                    .join(", ");

2009

                format!("tuple ({args})")

2010

2011

            GroundDomain::Record(entries, representation) => {

2012

                let inners = entries

2013

                    .iter()

2014

                    .map(|f| format!("{}: {}", f.name, f.value.as_type_string()))

2015

                    .join(", ");

2016

                format!(

2017

                    "record{} {{{inners}}}",

2018

                    representation_attribute(representation)

2019

2020

2021

            GroundDomain::Variant(entries, representation) => {

2022

                let inners = entries

2023

                    .iter()

2024

                    .map(|f| format!("{}: {}", f.name, f.value.as_type_string()))

2025

                    .join(", ");

2026

                format!(

2027

                    "variant{} {{{inners}}}",

2028

                    representation_attribute(representation)

2029

2030

2031

            GroundDomain::Matrix(inner, idxs, representation) => {

2032

725

                let idxs = idxs.iter().map(|d| d.as_type_string()).join(", ");

2033

725

                format!(

2034

725

                    "matrix{} indexed by [{idxs}] of {}",

2035

725

                    representation_attribute(representation),

2036

725

                    inner.as_type_string()

2037

2038

2039

            GroundDomain::Sequence(attrs, inner) => format!(

2040

                "sequence{} of {}",

2041

                representation_attribute(&attrs.representation),

2042

                inner.as_type_string()

2043

),

2044

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

2045

119

                let mut out = String::from("set");

2046

119

                if let Some(repr) = &attrs.representation {

2047

119

                    out.push_str(" (representation ");

2048

119

                    out.push_str(repr);

2049

119

                    out.push(')');

2050

2051

119

                out.push_str(" of ");

2052

119

                out.push_str(&inner.as_type_string());

2053

119

out

2054

2055

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

2056

1

                let mut out = String::from("mset");

2057

1

                if let Some(repr) = &attrs.representation {

2058

1

                    out.push_str(" (representation ");

2059

1

                    out.push_str(repr);

2060

1

                    out.push(')');

2061

2062

1

                out.push_str(" of ");

2063

1

                out.push_str(&inner.as_type_string());

2064

1

out

2065

2066

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

2067

                format!(

2068

                    "function{} {} --> {}",

2069

                    representation_attribute(&attr.representation),

2070

                    dom.as_type_string(),

2071

                    cdom.as_type_string()

2072

2073

2074

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

2075

                format!(

2076

                    "relation{} of ({})",

2077

                    representation_attribute(&attr.representation),

2078

                    inners.iter().map(|d| d.as_type_string()).join(" * ")

2079

2080

2081

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

2082

                format!(

2083

                    "partition{} from {}",

2084

                    representation_attribute(&attr.representation),

2085

                    inner.as_type_string()

2086

2087

2088

            GroundDomain::Permutation(attr, inner) => {

2089

                format!(

2090

                    "permutation{} of {}",

2091

                    representation_attribute(&attr.representation),

2092

                    inner.as_type_string()

2093

2094

2095

2096

2443

2097

2098

2099

impl Typeable for GroundDomain {

2100

3339136639

    fn return_type(&self) -> ReturnType {

2101

3339136639

        match self {

2102

238179

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

2103

2829636869

            GroundDomain::Bool => ReturnType::Bool,

2104

384734967

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

2105

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

2106

20650009

                let mut inner_types = Vec::new();

2107

20650009

                for inner in inners {

2108

42746633

                    inner_types.push(inner.return_type());

2109

2110

20650009

                ReturnType::Tuple(inner_types)

2111

2112

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

2113

3117588

                let mut entry_types = Vec::new();

2114

3117588

                for entry in entries {

2115

6235175

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

2116

2117

3117588

                entry_types.sort();

2118

3117588

                ReturnType::Record(entry_types)

2119

2120

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

2121

5710100

                let mut entry_types = Vec::new();

2122

5710100

                for entry in entries {

2123

11420316

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

2124

2125

5710100

                ReturnType::Variant(entry_types)

2126

2127

            GroundDomain::Matrix(inner, _idx, _) => {

2128

62301127

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

2129

2130

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

2131

2952722

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

2132

2133

18719445

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

2134

6238956

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

2135

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

2136

2736472

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

2137

2138

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

2139

2072025

                let mut inner_types = Vec::new();

2140

2072025

                for inner in inners {

2141

4145765

                    inner_types.push(inner.return_type());

2142

2143

2072025

                ReturnType::Relation(inner_types)

2144

2145

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

2146

493

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

2147

2148

            GroundDomain::Permutation(_, inner) => {

2149

27579

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

2150

2151

100

            GroundDomain::EnumeratedType(et, _) => ReturnType::EnumeratedType(et.clone()),

2152

            // TODO: Ensure bounded range on type level

2153

8

            GroundDomain::UnnamedType(ty) => ReturnType::UnnamedType(ty.clone()),

2154

2155

3339136639

2156

2157

2158

impl Display for FieldGround {

2159

217182

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

2160

217182

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

2161

217182

2162

2163

2164

impl Display for GroundDomain {

2165

37301349

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

2166

37301349

        match &self {

2167

8

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

2168

3671727

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

2169

            GroundDomain::Int(ranges, representation) => {

2170

31023107

                write_int_domain(f, ranges, representation.as_deref())

2171

2172

            GroundDomain::Tuple(domains, representation) => {

2173

268548

                let args = representation

2174

268548

                    .iter()

2175

348

                    .map(|r| format!("representation {r}"))

2176

537593

                    .chain(domains.iter().map(|d| d.to_string()))

2177

268548

                    .join(", ");

2178

268548

                write!(f, "tuple ({args})")

2179

2180

            GroundDomain::Record(entries, representation) => {

2181

197288

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

2182

98659

                let attrs = representation_attribute(representation);

2183

98659

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

2184

2185

            GroundDomain::Variant(entries, representation) => {

2186

19894

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

2187

9889

                let attrs = representation_attribute(representation);

2188

9889

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

2189

2190

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

2191

1143483

                write!(

2192

1143483

f,

2193

1143483

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

2194

1143483

                    representation_attribute(representation),

2195

1143483

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

2196

2197

2198

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

2199

118175

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

2200

2201

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

2202

657356

                write!(f, "set")?;

2203

657356

                let attrs = attrs.to_string();

2204

657356

                if attrs.is_empty() {

2205

222656

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

2206

                } else {

2207

434700

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

2208

2209

2210

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

2211

178633

                write!(f, "mset")?;

2212

178633

                let attrs = attrs.to_string();

2213

178633

                if attrs.is_empty() {

2214

58

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

2215

                } else {

2216

178575

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

2217

2218

2219

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

2220

98692

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

2221

2222

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

2223

8310

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

2224

2225

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

2226

1992

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

2227

2228

            GroundDomain::EnumeratedType(et, ranges) => {

2229

48

                if !ranges.is_empty() && ranges.iter().all(Range::is_lower_or_upper_bounded) {

2230

40

                    let ranges = ranges

2231

40

                        .iter()

2232

40

                        .cloned()

2233

40

                        .map(|range| {

2234

40

                            range.func_map(|index| {

2235

40

                                et.variants

2236

40

                                    .get(index as usize)

2237

40

                                    .map(ToString::to_string)

2238

                                    .unwrap_or_else(|| index.to_string())

2239

40

})

2240

40

})

2241

40

                        .join(", ");

2242

40

                    write!(f, "{}({ranges})", et.name)

2243

                } else {

2244

8

                    write!(f, "{}", et.name)

2245

2246

2247

            GroundDomain::UnnamedType(ty) => {

2248

44

                write!(f, "{}", ty.name)

2249

2250

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

2251

22678

                write!(f, "permutation {attrs} of {inner}")

2252

2253

2254

37301349

2255

2256

2257

#[cfg(test)]

2258

mod tests {

2259

    use super::*;

2260

    use crate::ast::Name;

2261

    use crate::{domain_int_ground, matrix_lit};

2262

2263

    #[test]

2264

1

    fn integer_intersection_matches_all_small_sparse_sets() {

2265

1

        for a_mask in 0..128 {

2266

            let a = GroundDomain::Int(

2267

128

                (-3..=3)

2268

896

                    .filter(|i| a_mask & (1 << (i + 3)) != 0)

2269

128

                    .map(Range::Single)

2270

                    .collect(),

2271

128

                None,

2272

);

2273

128

            for b_mask in 0..128 {

2274

                let b = GroundDomain::Int(

2275

16384

                    (-3..=3)

2276

114688

                        .filter(|i| b_mask & (1 << (i + 3)) != 0)

2277

16384

                        .map(Range::Single)

2278

                        .collect(),

2279

16384

                    None,

2280

);

2281

16384

                let expected: BTreeSet<_> = (-3..=3)

2282

114688

                    .filter(|i| (a_mask & b_mask) & (1 << (i + 3)) != 0)

2283

                    .collect();

2284

16384

                let actual = a

2285

16384

                    .intersect(&b)

2286

16384

                    .unwrap()

2287

16384

                    .values_i32()

2288

16384

                    .unwrap()

2289

16384

                    .into_iter()

2290

16384

                    .collect::<BTreeSet<_>>();

2291

16384

                assert_eq!(actual, expected);

2292

2293

2294

1

2295

2296

    #[test]

2297

1

    fn integer_intersection_handles_large_overlapping_and_empty_ranges() {

2298

1

        let full = GroundDomain::Int(vec![Range::Bounded(i32::MIN, i32::MAX)], None);

2299

1

        let positive = GroundDomain::Int(vec![Range::Bounded(0, i32::MAX)], None);

2300

1

        assert_eq!(full.intersect(&positive).unwrap(), positive);

2301

1

        assert_eq!(full.intersect(&full).unwrap(), full);

2302

1

        let empty = GroundDomain::Empty(ReturnType::Int);

2303

1

        assert_eq!(full.intersect(&empty).unwrap(), empty);

2304

1

        let unsorted = GroundDomain::Int(

2305

1

            vec![

2306

1

                Range::Bounded(5, 10),

2307

1

                Range::Bounded(-8, 6),

2308

1

                Range::Single(i32::MAX),

2309

1

],

2310

1

            None,

2311

1

);

2312

1

        let overlap = GroundDomain::Int(

2313

1

            vec![

2314

1

                Range::Bounded(0, 12),

2315

1

                Range::Bounded(3, 8),

2316

1

                Range::Single(i32::MAX),

2317

1

],

2318

1

            None,

2319

1

);

2320

1

        assert_eq!(

2321

1

            unsorted.intersect(&overlap).unwrap(),

2322

1

            GroundDomain::Int(vec![Range::Bounded(0, 10), Range::Single(i32::MAX)], None)

2323

);

2324

1

        let negative = GroundDomain::Int(vec![Range::Bounded(i32::MIN, -1)], None);

2325

1

        assert_eq!(negative.intersect(&positive).unwrap(), empty);

2326

1

        let unbounded = GroundDomain::Int(vec![Range::Unbounded], None);

2327

1

        assert!(matches!(

2328

1

            full.intersect(&unbounded),

2329

            Err(DomainOpError::Unbounded)

2330

));

2331

1

        let no_ranges = GroundDomain::Int(Vec::new(), None);

2332

1

        assert!(matches!(

2333

1

            no_ranges.intersect(&unbounded),

2334

            Err(DomainOpError::Unbounded)

2335

));

2336

1

2337

2338

    #[test]

2339

1

    fn matrix_values_1d_bool_of_bool() {

2340

        // matrix indexed by [bool] of bool

2341

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

2342

1

        let dom = GroundDomain::Matrix(

2343

1

            Moo::new(GroundDomain::Bool),

2344

1

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

2345

1

            None,

2346

1

);

2347

2348

1

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

2349

2350

1

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

2351

1

        assert_eq!(

2352

1

            values[0],

2353

1

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

2354

);

2355

1

        assert_eq!(

2356

1

            values[1],

2357

1

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

2358

);

2359

1

        assert_eq!(

2360

1

            values[2],

2361

1

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

2362

);

2363

1

        assert_eq!(

2364

1

            values[3],

2365

1

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

2366

);

2367

1

2368

2369

    #[test]

2370

1

    fn matrix_values_1d_int() {

2371

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

2372

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

2373

1

        let dom = GroundDomain::Matrix(

2374

1

            domain_int_ground!(0..1),

2375

1

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

2376

1

            None,

2377

1

);

2378

2379

1

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

2380

2381

1

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

2382

1

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

2383

1

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

2384

1

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

2385

1

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

2386

1

2387

2388

    #[test]

2389

1

    fn matrix_values_2d_lexicographic() {

2390

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

2391

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

2392

1

        let dom = GroundDomain::Matrix(

2393

1

            domain_int_ground!(0..1),

2394

1

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

2395

1

            None,

2396

1

);

2397

2398

1

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

2399

2400

1

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

2401

2402

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

2403

1

        assert_eq!(

2404

1

            values[0],

2405

1

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

2406

);

2407

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

2408

1

        assert_eq!(

2409

1

            values[1],

2410

1

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

2411

);

2412

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

2413

1

        assert_eq!(

2414

1

            values[2],

2415

1

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

2416

);

2417

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

2418

1

        assert_eq!(

2419

1

            values[3],

2420

1

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

2421

);

2422

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

2423

1

        assert_eq!(

2424

1

            values[15],

2425

1

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

2426

);

2427

1

2428

2429

    #[test]

2430

1

    fn matrix_values_count_matches_length() {

2431

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

2432

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

2433

1

        let dom = GroundDomain::Matrix(

2434

1

            domain_int_ground!(0..1),

2435

1

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

2436

1

            None,

2437

1

);

2438

2439

1

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

2440

1

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

2441

2442

1

        assert_eq!(count as u64, length);

2443

1

2444

2445

    #[test]

2446

1

    fn tuple_values_two_bools() {

2447

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

2448

1

        let dom = GroundDomain::Tuple(

2449

1

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

2450

1

            None,

2451

1

);

2452

2453

1

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

2454

2455

1

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

2456

4

        let t = |a, b| {

2457

4

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

2458

4

                Literal::Bool(a),

2459

4

                Literal::Bool(b),

2460

4

]))

2461

4

};

2462

1

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

2463

1

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

2464

1

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

2465

1

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

2466

1

2467

2468

    #[test]

2469

1

    fn tuple_values_mixed_domains() {

2470

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

2471

1

        let dom = GroundDomain::Tuple(

2472

1

            vec![Moo::new(GroundDomain::Bool), domain_int_ground!(0..2)],

2473

1

            None,

2474

1

);

2475

2476

1

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

2477

2478

1

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

2479

6

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

2480

6

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

2481

6

                Literal::Bool(b),

2482

6

                Literal::Int(i),

2483

6

]))

2484

6

};

2485

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

2486

1

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

2487

1

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

2488

1

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

2489

        // then bool true

2490

1

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

2491

1

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

2492

1

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

2493

1

2494

2495

    #[test]

2496

1

    fn tuple_values_count_matches_length() {

2497

1

        let dom = GroundDomain::Tuple(

2498

1

            vec![

2499

1

                domain_int_ground!(1..3),

2500

1

                Moo::new(GroundDomain::Bool),

2501

1

                domain_int_ground!(0..1),

2502

1

],

2503

1

            None,

2504

1

);

2505

1

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

2506

1

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

2507

1

        assert_eq!(count as u64, length);

2508

1

2509

2510

    #[test]

2511

1

    fn record_values_lexicographic_by_name() {

2512

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

2513

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

2514

1

        let dom = GroundDomain::Record(

2515

1

            vec![

2516

1

                Field {

2517

1

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

2518

1

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

2519

1

},

2520

1

                Field {

2521

1

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

2522

1

                    value: domain_int_ground!(0..1),

2523

1

},

2524

1

],

2525

1

            None,

2526

1

);

2527

2528

1

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

2529

2530

        // 2 * 2 = 4 values

2531

1

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

2532

2533

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

2534

5

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

2535

5

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

2536

5

                Field {

2537

5

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

2538

5

                    value: Literal::Int(a_val),

2539

5

},

2540

5

                Field {

2541

5

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

2542

5

                    value: Literal::Bool(b_val),

2543

5

},

2544

5

]))

2545

5

};

2546

2547

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

2548

1

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

2549

1

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

2550

1

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

2551

1

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

2552

1

        for value in &values {

2553

4

            assert!(dom.contains(value).unwrap(), "{value}");

2554

2555

1

        assert!(!dom.contains(&r(2, false)).unwrap());

2556

1

2557

2558

    #[test]

2559

1

    fn record_values_count_matches_length() {

2560

1

        let dom = GroundDomain::Record(

2561

1

            vec![

2562

1

                Field {

2563

1

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

2564

1

                    value: domain_int_ground!(1..3),

2565

1

},

2566

1

                Field {

2567

1

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

2568

1

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

2569

1

},

2570

1

],

2571

1

            None,

2572

1

);

2573

1

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

2574

1

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

2575

1

        assert_eq!(count as u64, length);

2576

1

2577

2578

    #[test]

2579

1

    fn variant_values_follow_alternative_order_and_match_length() {

2580

1

        let dom = GroundDomain::Variant(

2581

1

            vec![

2582

1

                Field {

2583

1

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

2584

1

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

2585

1

},

2586

1

                Field {

2587

1

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

2588

1

                    value: domain_int_ground!(2..3),

2589

1

},

2590

1

],

2591

1

            None,

2592

1

);

2593

1

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

2594

1

        assert_eq!(values.len() as u64, dom.length().unwrap());

2595

1

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

2596

1

        assert!(matches!(

2597

1

            &values[0],

2598

            Literal::AbstractLiteral(AbstractLiteral::Variant(field))

2599

1

                if field.name == Name::user("flag") && field.value == Literal::Bool(false)

2600

));

2601

1

        assert!(matches!(

2602

1

            &values[3],

2603

            Literal::AbstractLiteral(AbstractLiteral::Variant(field))

2604

1

                if field.name == Name::user("value") && field.value == Literal::Int(3)

2605

));

2606

1

        assert!(dom.contains(&values[2]).unwrap());

2607

1

2608

2609

    #[test]

2610

1

    fn infers_variant_domain_from_all_observed_alternatives() {

2611

3

        let variant = |name: &str, value: i32| {

2612

3

            Literal::AbstractLiteral(AbstractLiteral::Variant(Moo::new(Field {

2613

3

                name: Name::user(name),

2614

3

                value: Literal::Int(value),

2615

3

            })))

2616

3

};

2617

        let domain =

2618

1

            GroundDomain::from_literal_vec(&[variant("a", 10), variant("a", 13), variant("b", 7)])

2619

1

                .unwrap();

2620

1

        let GroundDomain::Variant(fields, _) = domain else {

2621

            panic!("expected variant domain");

2622

};

2623

2624

1

        assert_eq!(fields.len(), 2);

2625

1

        assert_eq!(fields[0].name, Name::user("a"));

2626

1

        assert!(fields[0].value.contains(&Literal::Int(10)).unwrap());

2627

1

        assert!(fields[0].value.contains(&Literal::Int(13)).unwrap());

2628

1

        assert_eq!(fields[1].name, Name::user("b"));

2629

1

        assert!(fields[1].value.contains(&Literal::Int(7)).unwrap());

2630

1

2631

2632

17

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

2633

17

        Literal::AbstractLiteral(AbstractLiteral::Set(

2634

17

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

2635

17

))

2636

17

2637

2638

    #[test]

2639

1

    fn set_values_unbounded() {

2640

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

2641

1

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

2642

2643

1

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

2644

2645

1

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

2646

1

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

2647

1

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

2648

1

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

2649

1

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

2650

1

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

2651

1

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

2652

1

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

2653

1

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

2654

1

2655

2656

    #[test]

2657

1

    fn set_values_fixed_size() {

2658

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

2659

1

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

2660

2661

1

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

2662

2663

1

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

2664

1

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

2665

1

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

2666

1

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

2667

1

2668

2669

    #[test]

2670

1

    fn set_values_bounded_size() {

2671

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

2672

1

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

2673

2674

1

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

2675

2676

1

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

2677

1

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

2678

1

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

2679

1

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

2680

1

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

2681

1

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

2682

1

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

2683

1

2684

2685

    #[test]

2686

1

    fn set_length_clamps_max_size_to_inner_domain() {

2687

        // maxSize 3 of int(1..2) is effectively maxSize 2: 2^2 = 4 subsets.

2688

1

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

2689

1

        assert_eq!(dom.length().unwrap(), 4);

2690

1

2691

2692

    #[test]

2693

1

    fn set_values_count_matches_length() {

2694

1

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

2695

1

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

2696

1

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

2697

1

        assert_eq!(count as u64, length);

2698

1

2699

2700

5

    fn func_attr(partiality: PartialityAttr, jectivity: JectivityAttr) -> FuncAttr {

2701

5

        FuncAttr {

2702

5

            representation: None,

2703

5

            size: Range::Unbounded,

2704

5

            partiality,

2705

5

            jectivity,

2706

5

2707

5

2708

2709

    #[test]

2710

1

    fn total_bijective_function_length_is_factorial_of_the_shared_size() {

2711

1

        let dom = GroundDomain::Function(

2712

1

            func_attr(PartialityAttr::Total, JectivityAttr::Bijective),

2713

1

            domain_int_ground!(1..3),

2714

1

            domain_int_ground!(1..3),

2715

1

);

2716

1

        assert_eq!(dom.length().unwrap(), 6); // 3!

2717

1

2718

2719

    #[test]

2720

1

    fn total_bijective_function_length_is_zero_for_mismatched_sizes() {

2721

1

        let dom = GroundDomain::Function(

2722

1

            func_attr(PartialityAttr::Total, JectivityAttr::Bijective),

2723

1

            domain_int_ground!(1..3),

2724

1

            domain_int_ground!(1..2),

2725

1

);

2726

1

        assert_eq!(dom.length().unwrap(), 0);

2727

1

2728

2729

    #[test]

2730

1

    fn total_injective_function_length_is_a_falling_factorial() {

2731

        // 2 domain elements injectively into 4 codomain elements: 4*3 = 12.

2732

1

        let dom = GroundDomain::Function(

2733

1

            func_attr(PartialityAttr::Total, JectivityAttr::Injective),

2734

1

            domain_int_ground!(1..2),

2735

1

            domain_int_ground!(1..4),

2736

1

);

2737

1

        assert_eq!(dom.length().unwrap(), 12);

2738

1

2739

2740

    #[test]

2741

1

    fn total_surjective_function_length_uses_stirling_numbers() {

2742

        // 3 domain elements onto 2 codomain elements: S(3,2)=3 partitions, * 2! = 6.

2743

1

        let dom = GroundDomain::Function(

2744

1

            func_attr(PartialityAttr::Total, JectivityAttr::Surjective),

2745

1

            domain_int_ground!(1..3),

2746

1

            domain_int_ground!(1..2),

2747

1

);

2748

1

        assert_eq!(dom.length().unwrap(), 6);

2749

1

2750

2751

    #[test]

2752

1

    fn partial_injective_function_length_sums_over_defined_sizes() {

2753

        // 3 domain elements, 2 codomain elements, up to 2 defined: sum over sz=0..=2 of

2754

        // C(3,sz) * P(2,sz) = 1*1 + 3*2 + 3*2 = 13.

2755

1

        let mut attr = func_attr(PartialityAttr::Partial, JectivityAttr::Injective);

2756

1

        attr.size = Range::Bounded(0, 2);

2757

1

        let dom = GroundDomain::Function(attr, domain_int_ground!(1..3), domain_int_ground!(1..2));

2758

1

        assert_eq!(dom.length().unwrap(), 13);

2759

1

2760

2761

7

    fn partition_attr(num_parts: Range<i32>, part_len: Range<i32>) -> PartitionAttr {

2762

7

        PartitionAttr {

2763

7

            representation: None,

2764

7

            num_parts,

2765

7

            part_len,

2766

7

            is_regular: false,

2767

7

2768

7

2769

2770

3

    fn partition_lit(parts: Vec<Vec<i32>>) -> Literal {

2771

        Literal::AbstractLiteral(AbstractLiteral::Partition(

2772

3

            parts

2773

3

                .into_iter()

2774

5

                .map(|part| part.into_iter().map(Literal::Int).collect())

2775

                .collect(),

2776

))

2777

3

2778

2779

    #[test]

2780

1

    fn partition_contains_accepts_a_literal_whose_size_exactly_matches_num_parts_times_part_len() {

2781

        // num_parts=2, part_len=2 => exactly 4 covered elements is valid.

2782

1

        let dom = GroundDomain::Partition(

2783

1

            partition_attr(Range::Single(2), Range::Single(2)),

2784

1

            domain_int_ground!(1..6),

2785

1

);

2786

1

        let lit = partition_lit(vec![vec![1, 2], vec![3, 4]]);

2787

1

        assert!(

2788

1

            dom.contains(&lit).unwrap(),

2789

            "a 4-element partition literal should be a valid member of a \

2790

             (numParts 2, partSize 2) domain"

2791

);

2792

1

2793

2794

    #[test]

2795

    fn partition_contains_rejects_a_literal_with_the_wrong_covered_size() {

2796

        // num_parts=2, part_len=2 requires exactly 4 covered elements; 3 should be rejected.

2797

1

        let dom = GroundDomain::Partition(

2798

1

            partition_attr(Range::Single(2), Range::Single(2)),

2799

1

            domain_int_ground!(1..6),

2800

1

);

2801

1

        let lit = partition_lit(vec![vec![1, 2, 3]]);

2802

1

        assert!(

2803

1

            !dom.contains(&lit).unwrap(),

2804

            "a 3-element partition literal should not be a valid member of a \

2805

             (numParts 2, partSize 2) domain, which requires exactly 4 covered elements"

2806

);

2807

1

2808

2809

    #[test]

2810

1

    fn partition_contains_accepts_any_size_when_attributes_are_unbounded() {

2811

        // Regression: an unattributed partition domain (Range::Unbounded for both num_parts and

2812

        // part_len) must not reject every literal outright -- Range::Unbounded.contains() is

2813

        // always true, which an inverted condition would misread as "always out of range".

2814

1

        let dom = GroundDomain::Partition(

2815

1

            partition_attr(Range::Unbounded, Range::Unbounded),

2816

1

            domain_int_ground!(1..6),

2817

1

);

2818

1

        let lit = partition_lit(vec![vec![1, 2], vec![3, 4, 5, 6]]);

2819

1

        assert!(

2820

1

            dom.contains(&lit).unwrap(),

2821

            "an unattributed partition domain should accept a literal covering its whole inner \

2822

             domain"

2823

);

2824

1

2825

2826

    #[test]

2827

1

    fn partition_length_unattributed_matches_the_bell_number() {

2828

        // Bell(4) = 15: every way to partition a 4-element set, no size/count restriction.

2829

1

        let dom = GroundDomain::Partition(

2830

1

            partition_attr(Range::Unbounded, Range::Unbounded),

2831

1

            domain_int_ground!(1..4),

2832

1

);

2833

1

        assert_eq!(dom.length().unwrap(), 15);

2834

1

2835

2836

    #[test]

2837

1

    fn partition_length_fixed_num_parts_matches_stirling_second_kind() {

2838

        // S(4, 2) = 7: partitioning 4 elements into exactly 2 unlabelled non-empty blocks, no

2839

        // block-size restriction -- this is restricted_partition_count's block_min=1 case, which

2840

        // should agree with stirling_second_kind exactly.

2841

1

        let dom = GroundDomain::Partition(

2842

1

            partition_attr(Range::Single(2), Range::Unbounded),

2843

1

            domain_int_ground!(1..4),

2844

1

);

2845

1

        assert_eq!(dom.length().unwrap(), stirling_second_kind(4, 2).unwrap());

2846

1

        assert_eq!(dom.length().unwrap(), 7);

2847

1

2848

2849

    #[test]

2850

1

    fn partition_length_regular_fixed_block_size_matches_a_hand_computed_multinomial() {

2851

        // 6 elements into regular blocks of size 3: 6! / (3!^2 * 2!) = 720 / 72 = 10.

2852

1

        let mut attr = partition_attr(Range::Unbounded, Range::Single(3));

2853

1

        attr.is_regular = true;

2854

1

        let dom = GroundDomain::Partition(attr, domain_int_ground!(1..6));

2855

1

        assert_eq!(dom.length().unwrap(), 10);

2856

1

2857

2858

    #[test]

2859

1

    fn partition_values_count_matches_length_and_every_value_is_a_valid_member() {

2860

1

        let dom = GroundDomain::Partition(

2861

1

            partition_attr(Range::Bounded(2, 3), Range::Unbounded),

2862

1

            domain_int_ground!(1..4),

2863

1

);

2864

1

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

2865

1

        assert_eq!(values.len() as u64, dom.length().unwrap());

2866

1

        for value in &values {

2867

13

            assert!(dom.contains(value).unwrap());

2868

2869

1

2870

2871

3

    fn permutation_attr(num_moved: Range<i32>) -> PermutationAttr {

2872

3

        PermutationAttr {

2873

3

            representation: None,

2874

3

            num_moved,

2875

3

2876

3

2877

2878

    #[test]

2879

1

    fn permutation_length_unattributed_matches_factorial() {

2880

        // 4! = 24: every bijection of a 4-element set onto itself, no numMoved restriction.

2881

        let dom =

2882

1

            GroundDomain::Permutation(permutation_attr(Range::Unbounded), domain_int_ground!(1..4));

2883

1

        assert_eq!(dom.length().unwrap(), 24);

2884

1

2885

2886

    #[test]

2887

1

    fn permutation_length_fully_moved_matches_the_derangement_number() {

2888

        // D(4) = 9: permutations of 4 elements with no fixed points at all.

2889

        let dom =

2890

1

            GroundDomain::Permutation(permutation_attr(Range::Single(4)), domain_int_ground!(1..4));

2891

1

        assert_eq!(dom.length().unwrap(), 9);

2892

1

2893

2894

    #[test]

2895

1

    fn permutation_values_count_matches_length_and_every_value_is_a_valid_member() {

2896

1

        let dom = GroundDomain::Permutation(

2897

1

            permutation_attr(Range::Bounded(1, 2)),

2898

1

            domain_int_ground!(1..3),

2899

1

);

2900

1

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

2901

1

        assert_eq!(values.len() as u64, dom.length().unwrap());

2902

1

        for value in &values {

2903

3

            assert!(dom.contains(value).unwrap());

2904

2905

1

2906

2907

2908

16

fn enum_indices<'a>(

2909

16

    ty: &'a Moo<EnumeratedType>,

2910

16

    ranges: &'a [Range<u32>],

2911

16

) -> impl Iterator<Item = u32> + 'a {

2912

16

    (0..ty.len() as u32)

2913

32

        .filter(move |index| ranges.is_empty() || ranges.iter().any(|range| range.contains(index)))

2914

16