Grcov report - literals.rs

1

use funcmap::FuncMap;

2

use itertools::Itertools;

3

use serde::{Deserialize, Serialize};

4

use std::cmp::Ordering;

5

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

6

use std::hash::Hash;

7

use ustr::Ustr;

8

9

use super::collection_domains::{SizeBounds, bounded_set};

10

use super::eval::eval_constant;

11

12

use super::{

13

    Atom, Domain, DomainPtr, Expression, GroundDomain, Moo, PartitionAttr, PermutationAttr, Range,

14

    ReturnType, SetAttr, Typeable, domains::HasDomain, domains::Int, records::Field,

15

};

16

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

17

use crate::ast::enumerated::EnumVariant;

18

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

19

use crate::bug;

20

use crate::bug_assert;

21

use polyquine::Quine;

22

use uniplate::{Biplate, Tree, Uniplate};

23

24

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

25

#[uniplate(walk_into=[AbstractLiteral<Literal>])]

26

#[biplate(to=Atom)]

27

#[biplate(to=AbstractLiteral<Literal>)]

28

#[biplate(to=AbstractLiteral<Expression>)]

29

#[biplate(to=Field<Literal>)]

30

#[biplate(to=Field<Expression>)]

31

#[biplate(to=Expression)]

32

#[path_prefix(conjure_cp::ast)]

33

/// A literal value, equivalent to constants in Conjure.

34

pub enum Literal {

35

    Int(i32),

36

    Bool(bool),

37

    EnumVariant(EnumVariant),

38

    Unnamed(crate::ast::unnamed::UnnamedValue),

39

    //abstract literal variant ends in Literal, but that's ok

40

    #[allow(clippy::enum_variant_names)]

41

    AbstractLiteral(AbstractLiteral<Literal>),

42

43

44

impl HasDomain for Literal {

45

37024378

    fn domain_of(&self) -> DomainPtr {

46

37024378

        match self {

47

34266344

            Literal::Int(i) => Domain::int(vec![Range::Single(*i)]),

48

1132000

            Literal::Bool(_) => Domain::bool(),

49

            Literal::EnumVariant(ev) => {

50

332

                Domain::enumerated_ground(ev.ty.clone(), vec![Range::Single(ev.variant)])

51

52

            Literal::Unnamed(value) => {

53

                Moo::new(crate::ast::GroundDomain::UnnamedType(value.ty.clone())).into()

54

55

1625702

            Literal::AbstractLiteral(abstract_literal) => abstract_literal.domain_of(),

56

57

37024378

58

59

60

impl Literal {

61

    /// Compare values using Essence-aware value ordering.

62

///

63

    /// Booleans and integers use their natural order, tuple-like values use

64

    /// lexicographic order, and sets use lexicographic occurrence order over

65

    /// ascending element values (`false < true`).

66

721315919

    pub fn essence_cmp(&self, other: &Self) -> Ordering {

67

721315919

        match (self, other) {

68

            (Literal::Unnamed(lhs), Literal::Unnamed(rhs)) => {

69

20

                (&lhs.ty.name, lhs.ty.size, lhs.value).cmp(&(&rhs.ty.name, rhs.ty.size, rhs.value))

70

71

19729856

            (Literal::Bool(lhs), Literal::Bool(rhs)) => lhs.cmp(rhs),

72

554388115

            (Literal::Int(lhs), Literal::Int(rhs)) => lhs.cmp(rhs),

73

4

            (Literal::EnumVariant(lhs), Literal::EnumVariant(rhs)) => (

74

4

                &lhs.ty.name,

75

4

                &lhs.ty.variants,

76

4

                lhs.variant,

77

4

78

4

                .cmp(&(&rhs.ty.name, &rhs.ty.variants, rhs.variant)),

79

            (Literal::AbstractLiteral(lhs), Literal::AbstractLiteral(rhs)) => {

80

147197924

                abstract_literal_essence_cmp(lhs, rhs)

81

82

            _ => literal_kind(self).cmp(&literal_kind(other)),

83

84

721315919

85

86

87

fn literal_kind(literal: &Literal) -> u8 {

88

    match literal {

89

        Literal::Bool(_) => 0,

90

        Literal::Int(_) => 1,

91

        Literal::AbstractLiteral(_) => 2,

92

        Literal::EnumVariant(_) => 3,

93

        Literal::Unnamed(_) => 4,

94

95

96

97

147197924

fn abstract_literal_essence_cmp(

98

147197924

    lhs: &AbstractLiteral<Literal>,

99

147197924

    rhs: &AbstractLiteral<Literal>,

100

147197924

) -> Ordering {

101

147197924

    match (lhs, rhs) {

102

21140167

        (AbstractLiteral::Set(lhs), AbstractLiteral::Set(rhs)) => set_essence_cmp(lhs, rhs),

103

3929674

        (AbstractLiteral::MSet(lhs), AbstractLiteral::MSet(rhs)) => sorted_literals_cmp(lhs, rhs),

104

        (AbstractLiteral::Matrix(lhs, _), AbstractLiteral::Matrix(rhs, _))

105

        | (AbstractLiteral::Tuple(lhs), AbstractLiteral::Tuple(rhs))

106

        | (AbstractLiteral::Sequence(lhs), AbstractLiteral::Sequence(rhs)) => {

107

111565819

            literal_slice_cmp(lhs, rhs)

108

109

3695412

        (AbstractLiteral::Record(lhs), AbstractLiteral::Record(rhs)) => lhs

110

3695412

            .iter()

111

3695412

            .zip(rhs)

112

5974232

            .find_map(|(lhs, rhs)| {

113

5974232

                let ordering = lhs.name.to_string().cmp(&rhs.name.to_string());

114

5974232

                (ordering != Ordering::Equal)

115

5974232

                    .then_some(ordering)

116

5974232

                    .or_else(|| {

117

5974232

                        let ordering = lhs.value.essence_cmp(&rhs.value);

118

5974232

                        (ordering != Ordering::Equal).then_some(ordering)

119

5974232

})

120

5974232

})

121

1463195

            .unwrap_or_else(|| lhs.len().cmp(&rhs.len())),

122

379958

        (AbstractLiteral::Function(lhs), AbstractLiteral::Function(rhs)) => lhs

123

379958

            .iter()

124

379958

            .zip(rhs)

125

637014

            .find_map(|((lhs_from, lhs_to), (rhs_from, rhs_to))| {

126

637014

                let ordering = lhs_from.essence_cmp(rhs_from);

127

637014

                (ordering != Ordering::Equal)

128

637014

                    .then_some(ordering)

129

609754

                    .or_else(|| {

130

609754

                        let ordering = lhs_to.essence_cmp(rhs_to);

131

609754

                        (ordering != Ordering::Equal).then_some(ordering)

132

609754

})

133

637014

})

134

139403

            .unwrap_or_else(|| lhs.len().cmp(&rhs.len())),

135

6112620

        (AbstractLiteral::Variant(lhs), AbstractLiteral::Variant(rhs)) => lhs

136

6112620

            .name

137

6112620

            .to_string()

138

6112620

            .cmp(&rhs.name.to_string())

139

3352139

            .then_with(|| lhs.value.essence_cmp(&rhs.value)),

140

        (AbstractLiteral::Partition(lhs), AbstractLiteral::Partition(rhs))

141

        | (AbstractLiteral::Relation(lhs), AbstractLiteral::Relation(rhs))

142

374274

        | (AbstractLiteral::Permutation(lhs), AbstractLiteral::Permutation(rhs)) => lhs

143

374274

            .iter()

144

374274

            .zip(rhs)

145

522464

            .find_map(|(lhs, rhs)| {

146

522464

                let ordering = literal_slice_cmp(lhs, rhs);

147

522464

                (ordering != Ordering::Equal).then_some(ordering)

148

522464

})

149

12644

            .unwrap_or_else(|| lhs.len().cmp(&rhs.len())),

150

        _ => abstract_literal_kind(lhs).cmp(&abstract_literal_kind(rhs)),

151

152

147197924

153

154

fn abstract_literal_kind(literal: &AbstractLiteral<Literal>) -> u8 {

155

    match literal {

156

        AbstractLiteral::Set(_) => 0,

157

        AbstractLiteral::MSet(_) => 1,

158

        AbstractLiteral::Matrix(..) => 2,

159

        AbstractLiteral::Tuple(_) => 3,

160

        AbstractLiteral::Record(_) => 4,

161

        AbstractLiteral::Sequence(_) => 5,

162

        AbstractLiteral::Function(_) => 6,

163

        AbstractLiteral::Variant(_) => 7,

164

        AbstractLiteral::Partition(_) => 8,

165

        AbstractLiteral::Relation(_) => 9,

166

        AbstractLiteral::Permutation(_) => 10,

167

168

169

170

112088283

fn literal_slice_cmp(lhs: &[Literal], rhs: &[Literal]) -> Ordering {

171

112088283

    lhs.iter()

172

112088283

        .zip(rhs)

173

206114235

        .find_map(|(lhs, rhs)| {

174

206114235

            let ordering = lhs.essence_cmp(rhs);

175

206114235

            (ordering != Ordering::Equal).then_some(ordering)

176

206114235

})

177

25671006

        .unwrap_or_else(|| lhs.len().cmp(&rhs.len()))

178

112088283

179

180

3929674

fn sorted_literals_cmp(lhs: &[Literal], rhs: &[Literal]) -> Ordering {

181

3929674

    let mut lhs = lhs.iter().collect::<Vec<_>>();

182

3929674

    let mut rhs = rhs.iter().collect::<Vec<_>>();

183

6829036

    lhs.sort_by(|lhs, rhs| lhs.essence_cmp(rhs));

184

7328880

    rhs.sort_by(|lhs, rhs| lhs.essence_cmp(rhs));

185

3929674

    lhs.iter()

186

3929674

        .zip(&rhs)

187

6132543

        .find_map(|(lhs, rhs)| {

188

6132543

            let ordering = lhs.essence_cmp(rhs);

189

6132543

            (ordering != Ordering::Equal).then_some(ordering)

190

6132543

})

191

1389796

        .unwrap_or_else(|| lhs.len().cmp(&rhs.len()))

192

3929674

193

194

/// Compare sets as occurrence vectors over the ordered union of their elements.

195

21140167

fn set_essence_cmp(lhs: &[Literal], rhs: &[Literal]) -> Ordering {

196

21140167

    let mut lhs = lhs.iter().collect::<Vec<_>>();

197

21140167

    let mut rhs = rhs.iter().collect::<Vec<_>>();

198

21140167

    lhs.sort_by(|lhs, rhs| lhs.essence_cmp(rhs));

199

21140167

    rhs.sort_by(|lhs, rhs| lhs.essence_cmp(rhs));

200

201

21140167

    let (mut lhs_index, mut rhs_index) = (0, 0);

202

31353249

    while lhs_index < lhs.len() && rhs_index < rhs.len() {

203

23679380

        match lhs[lhs_index].essence_cmp(rhs[rhs_index]) {

204

            Ordering::Equal => {

205

10213082

                lhs_index += 1;

206

10213082

                rhs_index += 1;

207

208

            // `lhs` contains the least differing element and `rhs` does not.

209

7111061

            Ordering::Less => return Ordering::Greater,

210

            // `rhs` contains the least differing element and `lhs` does not.

211

6355237

            Ordering::Greater => return Ordering::Less,

212

213

214

7673869

    match (lhs_index < lhs.len(), rhs_index < rhs.len()) {

215

2709993

        (false, false) => Ordering::Equal,

216

3332042

        (true, false) => Ordering::Greater,

217

1631834

        (false, true) => Ordering::Less,

218

        (true, true) => unreachable!(),

219

220

21140167

221

222

// make possible values of an AbstractLiteral a closed world to make the trait bounds more sane (particularly in Uniplate instances!!)

223

pub trait AbstractLiteralValue:

224

    Clone + Eq + PartialEq + Display + Uniplate + Biplate<Field<Self>> + 'static

225

226

    type Dom: Clone

227

        + Eq

228

        + PartialEq

229

        + Debug

230

        + Display

231

        + Quine

232

        + From<GroundDomain>

233

        + Into<DomainPtr>;

234

235

    /// Returns whether `domain` is the implicit one-based list index domain.

236

    fn has_implied_list_domain(domain: &Self::Dom) -> bool;

237

238

impl AbstractLiteralValue for Expression {

239

    type Dom = DomainPtr;

240

241

548436488

    fn has_implied_list_domain(domain: &Self::Dom) -> bool {

242

548436488

        let Domain::Ground(domain) = domain.as_ref() else {

243

            return false;

244

};

245

548436488

        matches!(domain.as_ref(), GroundDomain::Int(ranges, _) if ranges.as_slice() == [Range::UnboundedR(1)])

246

548436488

247

248

impl AbstractLiteralValue for Literal {

249

    type Dom = Moo<GroundDomain>;

250

251

3173560

    fn has_implied_list_domain(domain: &Self::Dom) -> bool {

252

3173560

        matches!(domain.as_ref(), GroundDomain::Int(ranges, _) if ranges.as_slice() == [Range::UnboundedR(1)])

253

3173560

254

255

256

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

257

#[path_prefix(conjure_cp::ast)]

258

pub enum AbstractLiteral<T: AbstractLiteralValue> {

259

    Set(Vec<T>),

260

261

    MSet(Vec<T>),

262

263

    /// A 1 dimensional matrix slice with an index domain.

264

    Matrix(Vec<T>, T::Dom),

265

266

    // a tuple of literals

267

    Tuple(Vec<T>),

268

269

    Record(Vec<Field<T>>),

270

271

    Sequence(Vec<T>),

272

273

    Function(Vec<(T, T)>),

274

275

    // Variants only contain one of their name-domain pairs

276

    Variant(Moo<Field<T>>),

277

278

    // A list of partitions, each part has a set of values

279

    Partition(Vec<Vec<T>>),

280

    Relation(Vec<Vec<T>>),

281

282

    /// Cycle notation for a permutation: each inner vec is one cycle. Unlike `Partition`, this is

283

    /// *sparse* -- any element of the permutation's domain not mentioned in any cycle is an

284

    /// implicit fixed point (maps to itself), rather than every element needing to be covered.

285

    Permutation(Vec<Vec<T>>),

286

287

288

// TODO: use HasDomain instead once Expression::domain_of returns Domain not Option<Domain>

289

1068407

fn union_item_domains(item_domains: Vec<DomainPtr>, literal_kind: &str) -> Option<DomainPtr> {

290

1068407

    let mut item_domain_iter = item_domains.into_iter();

291

1068407

    let first_item = item_domain_iter.next()?;

292

293

    Some(

294

1002983

        item_domain_iter

295

2538900

            .try_fold(first_item, |x, y| x.union(&y))

296

            .unwrap_or_else(|error| {

297

                bug!(

298

                    "taking the union of all item domains of a {literal_kind} literal should succeed: {error}"

299

300

}),

301

302

1068407

303

304

impl AbstractLiteral<Expression> {

305

1360270

    pub fn domain_of(&self) -> Option<DomainPtr> {

306

1360270

        match self {

307

            AbstractLiteral::Set(items) => {

308

227601

                if items.is_empty() {

309

1

                    return Some(Domain::set(

310

1

                        SetAttr::new_size(0),

311

1

                        Domain::empty(ReturnType::Unknown),

312

1

));

313

227600

314

                // ensure that all items have a domain, or return None

315

227600

                let item_domains: Vec<DomainPtr> = items

316

227600

                    .iter()

317

628620

                    .map(|x| x.domain_of())

318

                    .collect::<Option<Vec<DomainPtr>>>()?;

319

320

                // union all item domains together

321

227600

                let item_domain = union_item_domains(item_domains, "set")?;

322

323

227600

                let values = items.iter().map(eval_constant).collect::<Option<Vec<_>>>();

324

227600

                let high = i64::try_from(items.len()).ok()?;

325

227600

                let bounds = match values {

326

                    Some(values) => {

327

227542

                        let n = i64::try_from(distinct_literal_count(&values)).ok()?;

328

227542

                        SizeBounds::new(n, Some(n))

329

330

58

                    None => SizeBounds::new(1, Some(high)),

331

};

332

227600

                Some(bounded_set(bounds, item_domain))

333

334

335

            AbstractLiteral::MSet(items) => {

336

30918

                if items.is_empty() {

337

10268

                    return Some(Domain::mset(

338

10268

                        MSetAttr::new(Range::Single(0), Range::Single(0)),

339

10268

                        Domain::empty(ReturnType::Unknown),

340

10268

));

341

20650

342

20650

                let cardinality = i32::try_from(items.len()).ok()?;

343

                // ensure that all items have a domain, or return None

344

20650

                let item_domains: Vec<DomainPtr> = items

345

20650

                    .iter()

346

41358

                    .map(|x| x.domain_of())

347

                    .collect::<Option<Vec<DomainPtr>>>()?;

348

349

                // union all item domains together

350

20650

                let item_domain = union_item_domains(item_domains, "mset")?;

351

352

20650

                let occurrence = if cardinality == 0 {

353

                    Range::Single(0)

354

                } else {

355

20650

                    Range::Bounded(1, cardinality)

356

};

357

20650

                Some(Domain::mset(

358

20650

                    MSetAttr::new(Range::Single(cardinality), occurrence),

359

20650

                    item_domain,

360

20650

))

361

362

363

            AbstractLiteral::Sequence(elems) => {

364

84216

                let item_domains: Vec<DomainPtr> = elems

365

84216

                    .iter()

366

39121

                    .map(|x| x.domain_of())

367

                    .collect::<Option<Vec<DomainPtr>>>()?;

368

369

                // Get the union of all domains in the sequence.

370

                // i.e. if <(1..3), (1..3), (5), (8..9)> then seq dom is (1..3, 5, 8..9)

371

84216

                let item_domain = union_item_domains(item_domains, "sequence")?;

372

373

                // The literal's own length is its size: without it nothing downstream can tell

374

                // how many positions the sequence has.

375

19140

                let size = Range::Single(i32::try_from(elems.len()).ok()?);

376

19140

                Some(Domain::sequence(

377

19140

                    SequenceAttr::<Int> {

378

19140

                        size,

379

19140

                        ..SequenceAttr::default()

380

19140

},

381

19140

                    item_domain,

382

19140

))

383

384

385

            AbstractLiteral::Partition(items) => {

386

                // Flatten the Vec<Vec< into a single vec

387

                // ensure that all elemes in each part have a domain, or return None

388

389

406

                let item_domains: Vec<DomainPtr> = items

390

406

                    .iter()

391

406

                    .flatten()

392

725

                    .map(|x| x.domain_of())

393

                    .collect::<Option<Vec<DomainPtr>>>()?;

394

395

                // union all item domains together

396

406

                let item_domain = union_item_domains(item_domains, "partition")?;

397

398

377

                Some(Domain::partition(

399

377

                    PartitionAttr::<Int>::default(),

400

377

                    item_domain,

401

377

))

402

403

404

            AbstractLiteral::Permutation(cycles) => {

405

                // Flatten the Vec<Vec< into a single vec; unlike partition, elements not

406

                // mentioned in any cycle are implicit fixed points, so an empty literal (or one

407

                // with no domain-bearing elements) has no way to infer an inner domain.

408

20793

                let item_domains: Vec<DomainPtr> = cycles

409

20793

                    .iter()

410

20793

                    .flatten()

411

62524

                    .map(|x| x.domain_of())

412

                    .collect::<Option<Vec<DomainPtr>>>()?;

413

414

20793

                let item_domain = union_item_domains(item_domains, "permutation")?;

415

416

20735

                Some(Domain::permutation(

417

20735

                    PermutationAttr::<Int>::default(),

418

20735

                    item_domain,

419

20735

))

420

421

422

            AbstractLiteral::Matrix(items, _) => {

423

714800

                let item_domains = items

424

714800

                    .iter()

425

2769593

                    .map(|x| x.domain_of())

426

58

                    .collect::<Option<Vec<DomainPtr>>>()?;

427

428

                // union all item domains together

429

714742

                let mut item_domain = union_item_domains(item_domains, "matrix")?;

430

431

714481

                let mut new_index_domain = vec![];

432

433

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

434

714481

                let mut matrix = self;

435

785765

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

436

                    bug_assert!(

437

785765

                        idx.as_matrix().is_none(),

438

                        "n-dimensional matrix literals should be represented as a matrix inside a matrix, got {idx}"

439

);

440

785765

                    new_index_domain.push(idx.clone());

441

                    let Some(Expression::AbstractLiteral(_, inner @ AbstractLiteral::Matrix(..))) =

442

785765

                        elems.first()

443

                    else {

444

714481

                        break;

445

};

446

71284

                    matrix = inner;

447

448

                // Each flattened literal dimension has already contributed to the row domain.

449

                // Peel those dimensions so they are not represented twice. Matrix-valued

450

                // expression leaves retain their own domains.

451

714481

                let mut remaining = new_index_domain.len() - 1;

452

785765

                while remaining > 0 {

453

71284

                    let (inner, indices) = item_domain.as_matrix()?;

454

71284

                    if indices.is_empty() {

455

                        return None;

456

71284

457

71284

                    remaining = remaining.checked_sub(indices.len())?;

458

71284

                    item_domain = inner;

459

460

714481

                Some(Domain::matrix(item_domain, new_index_domain))

461

462

267964

            AbstractLiteral::Tuple(items) => Some(Domain::tuple(

463

267964

                items

464

267964

                    .iter()

465

267964

                    .map(Expression::domain_of)

466

267964

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

467

)),

468

8526

            AbstractLiteral::Record(items) => Some(Domain::record(

469

8526

                items

470

8526

                    .iter()

471

17052

                    .map(|field| {

472

                        Some(super::Field {

473

17052

                            name: field.name.clone(),

474

17052

                            value: field.value.domain_of()?,

475

})

476

17052

})

477

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

478

)),

479

638

            AbstractLiteral::Function(_) => None,

480

58

            AbstractLiteral::Variant(_) => None,

481

4350

            AbstractLiteral::Relation(_) => None,

482

483

1360270

484

485

486

4558338

pub(super) fn distinct_literal_count(items: &[Literal]) -> usize {

487

4558338

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

488

10259738

    sorted.sort_by(|a, b| a.essence_cmp(b));

489

9587199

    sorted.dedup_by(|a, b| a.essence_cmp(b).is_eq());

490

4558338

    sorted.len()

491

4558338

492

493

impl HasDomain for AbstractLiteral<Literal> {

494

1625702

    fn domain_of(&self) -> DomainPtr {

495

1625702

        let domain = Domain::from_literal_vec(&[Literal::AbstractLiteral(self.clone())])

496

1625702

            .expect("abstract literals should be correctly typed");

497

1625702

        match self {

498

            AbstractLiteral::Set(items) => {

499

121847

                let (_, inner) = domain.as_set().expect("set literal domain");

500

                let n =

501

121847

                    i64::try_from(distinct_literal_count(items)).expect("literal fits in memory");

502

121847

                bounded_set(SizeBounds::new(n, Some(n)), inner)

503

504

            AbstractLiteral::MSet(items) => {

505

242295

                let (_, inner) = domain.as_mset().expect("multiset literal domain");

506

242295

                let n = i32::try_from(items.len()).expect("literal cardinality fits i32");

507

242295

                let occurrence = if n == 0 {

508

80765

                    Range::Single(0)

509

                } else {

510

161530

                    Range::Bounded(1, n)

511

};

512

242295

                Domain::mset(MSetAttr::new(Range::Single(n), occurrence), inner)

513

514

1261560

            _ => domain,

515

516

1625702

517

518

519

impl Typeable for AbstractLiteral<Expression> {

520

2218063

    fn return_type(&self) -> ReturnType {

521

2218063

        match self {

522

236660

            AbstractLiteral::Set(items) if items.is_empty() => {

523

                ReturnType::Set(Box::new(ReturnType::Unknown))

524

525

            AbstractLiteral::Set(items) => {

526

236660

                let item_type = items[0].return_type();

527

528

                // if any items do not have a type, return none.

529

626519

                let item_types: Vec<ReturnType> = items.iter().map(|x| x.return_type()).collect();

530

531

                bug_assert!(

532

626519

                    item_types.iter().all(|x| x == &item_type),

533

                    "all items in a set should have the same type"

534

);

535

536

236660

                ReturnType::Set(Box::new(item_type))

537

538

30798

            AbstractLiteral::MSet(items) if items.is_empty() => {

539

10266

                ReturnType::MSet(Box::new(ReturnType::Unknown))

540

541

            AbstractLiteral::MSet(items) => {

542

20532

                let item_type = items[0].return_type();

543

544

                // if any items do not have a type, return none.

545

41064

                let item_types: Vec<ReturnType> = items.iter().map(|x| x.return_type()).collect();

546

547

                bug_assert!(

548

41064

                    item_types.iter().all(|x| x == &item_type),

549

                    "all items in a set should have the same type"

550

);

551

552

20532

                ReturnType::MSet(Box::new(item_type))

553

554

42137

            AbstractLiteral::Sequence(items) if items.is_empty() => {

555

17284

                ReturnType::Sequence(Box::new(ReturnType::Unknown))

556

557

            AbstractLiteral::Sequence(items) => {

558

24853

                let item_type = items[0].return_type();

559

560

                // if any items do not have a type, return none.

561

50083

                let item_types: Vec<ReturnType> = items.iter().map(|x| x.return_type()).collect();

562

563

                bug_assert!(

564

50083

                    item_types.iter().all(|x| x == &item_type),

565

                    "all items in a sequence should have the same type"

566

);

567

568

24853

                ReturnType::Sequence(Box::new(item_type))

569

570

841

            AbstractLiteral::Partition(items) if items.is_empty() || items[0].is_empty() => {

571

                ReturnType::Partition(Box::new(ReturnType::Unknown))

572

573

            AbstractLiteral::Partition(items) => {

574

841

                let item_type = items[0][0].return_type();

575

576

                // if any items do not have a type, return none.

577

                let item_types: Vec<ReturnType> =

578

1015

                    items.iter().flatten().map(|x| x.return_type()).collect();

579

580

                bug_assert!(

581

1015

                    item_types.iter().all(|x| x == &item_type),

582

                    "all items in every part of a partition should have the same type"

583

);

584

585

841

                ReturnType::Partition(Box::new(item_type))

586

587

16356

            AbstractLiteral::Permutation(items) if items.is_empty() || items[0].is_empty() => {

588

29

                ReturnType::Permutation(Box::new(ReturnType::Unknown))

589

590

            AbstractLiteral::Permutation(items) => {

591

16327

                let item_type = items[0][0].return_type();

592

593

                let item_types: Vec<ReturnType> =

594

49300

                    items.iter().flatten().map(|x| x.return_type()).collect();

595

596

                bug_assert!(

597

49300

                    item_types.iter().all(|x| x == &item_type),

598

                    "all items in every cycle of a permutation should have the same type"

599

);

600

601

16327

                ReturnType::Permutation(Box::new(item_type))

602

603

1391800

            AbstractLiteral::Matrix(items, _) if items.is_empty() => {

604

37381

                ReturnType::Matrix(Box::new(ReturnType::Unknown))

605

606

            AbstractLiteral::Matrix(items, _) => {

607

1354419

                let item_type = items[0].return_type();

608

609

                // if any items do not have a type, return none.

610

10146349

                let item_types: Vec<ReturnType> = items.iter().map(|x| x.return_type()).collect();

611

612

                bug_assert!(

613

10146349

                    item_types.iter().all(|x| x == &item_type),

614

                    "all items in a matrix should have the same type. items: {items} types: {types:#?}",

615

                    items = pretty_vec(items),

616

                    types = items

617

                        .iter()

618

                        .map(|x| x.return_type())

619

                        .collect::<Vec<ReturnType>>()

620

);

621

622

1354419

                ReturnType::Matrix(Box::new(item_type))

623

624

            AbstractLiteral::Tuple(items) => {

625

467455

                let mut item_types = vec![];

626

467455

                for item in items {

627

935088

                    item_types.push(item.return_type());

628

629

467455

                ReturnType::Tuple(item_types)

630

631

            AbstractLiteral::Record(items) => {

632

12702

                let mut item_types = vec![];

633

12702

                for item in items {

634

25404

                    item_types.push(item.clone().func_map(|x| x.return_type()));

635

636

12702

                item_types.sort();

637

12702

                ReturnType::Record(item_types)

638

639

            AbstractLiteral::Function(items) => {

640

232

                if items.is_empty() {

641

29

                    return ReturnType::Function(

642

29

                        Box::new(ReturnType::Unknown),

643

29

                        Box::new(ReturnType::Unknown),

644

29

);

645

203

646

647

                // Check that all items have the same return type

648

203

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

649

203

                let (t1, t2) = (x1.return_type(), y1.return_type());

650

203

                for (x, y) in items {

651

406

                    let (tx, ty) = (x.return_type(), y.return_type());

652

406

                    if tx != t1 {

653

                        bug!("Expected {t1}, got {x}: {tx}");

654

406

655

406

                    if ty != t2 {

656

                        bug!("Expected {t2}, got {y}: {ty}");

657

406

658

659

660

203

                ReturnType::Function(Box::new(t1), Box::new(t2))

661

662

            AbstractLiteral::Variant(item) => {

663

                // Variants hold multiple possible types. In the case of a literal we know which type it chose

664

16965

                ReturnType::Variant(vec![item.as_ref().clone().func_map(|x| x.return_type())])

665

666

            AbstractLiteral::Relation(items) => {

667

2117

                if items.is_empty() {

668

                    return ReturnType::Relation(vec![ReturnType::Unknown]);

669

2117

670

2117

                let mut item_types = vec![];

671

2117

                let x1 = &items[0];

672

2117

                let size = x1.len();

673

2117

                for item in x1 {

674

4234

                    item_types.push(item.return_type());

675

676

2117

                for x in items {

677

6351

                    if x.len() != size {

678

                        let strs = item_types.iter().map(|x| format!("{}", x)).join(",");

679

                        bug!("Expected ({strs}) with length {size}, got size {}", x.len());

680

6351

681

6351

                    for i in 1..size {

682

6351

                        if let Some(new_type) = x.get(i)

683

6351

                            && let Some(old_type) = item_types.get(i)

684

6351

                            && new_type.return_type() != *old_type

685

686

                            bug!("Expected {old_type}, got {new_type}");

687

6351

688

689

690

2117

                ReturnType::Relation(item_types)

691

692

693

2218063

694

695

696

impl<T> AbstractLiteral<T>

697

where

698

    T: AbstractLiteralValue,

699

700

    /// Creates a matrix with elements `elems`, with domain `int(1..)`.

701

///

702

    /// This acts as a variable sized list.

703

598755494

    pub fn matrix_implied_indices(elems: Vec<T>) -> Self {

704

598755494

        AbstractLiteral::Matrix(

705

598755494

            elems,

706

598755494

            GroundDomain::Int(vec![Range::UnboundedR(1)], None).into(),

707

598755494

708

598755494

709

710

    /// If the AbstractLiteral is a list, returns its elements.

711

///

712

    /// A list is any a matrix with the domain `int(1..)`. This includes matrix literals without

713

    /// any explicitly specified domain.

714

543144853

    pub fn unwrap_list(&self) -> Option<&Vec<T>> {

715

543144853

        let AbstractLiteral::Matrix(elems, domain) = self else {

716

            return None;

717

};

718

719

543144853

        T::has_implied_list_domain(domain).then_some(elems)

720

543144853

721

722

    /// If this abstract literal is a list, consumes it and returns its elements.

723

8465195

    pub fn into_list(self) -> Option<Vec<T>> {

724

8465195

        let AbstractLiteral::Matrix(elems, domain) = self else {

725

            return None;

726

};

727

728

8465195

        T::has_implied_list_domain(&domain).then_some(elems)

729

8465195

730

731

732

impl<T> Display for AbstractLiteral<T>

733

where

734

    T: AbstractLiteralValue,

735

736

36472135

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

737

36472135

        match self {

738

            AbstractLiteral::Set(elems) => {

739

8237828

                let elems_str: String = elems.iter().map(|x| format!("{x}")).join(",");

740

4283796

                write!(f, "{{{elems_str}}}")

741

742

            AbstractLiteral::MSet(elems) => {

743

2622180

                let elems_str: String = elems.iter().map(|x| format!("{x}")).join(",");

744

1153910

                write!(f, "mset({elems_str})")

745

746

            AbstractLiteral::Matrix(elems, index_domain) => {

747

65548083

                let elems_str: String = elems.iter().map(|x| format!("{x}")).join(",");

748

22555225

                write!(f, "[{elems_str};{index_domain}]")

749

750

            AbstractLiteral::Tuple(elems) => {

751

11806156

                let elems_str: String = elems.iter().map(|x| format!("{x}")).join(",");

752

5902552

                write!(f, "({elems_str})")

753

754

            AbstractLiteral::Sequence(elems) => {

755

833816

                let elems_str: String = elems.iter().map(|x| format!("{x}")).join(",");

756

679675

                write!(f, "sequence({elems_str})")

757

758

            AbstractLiteral::Partition(parts) => {

759

812

                let elems_str: String = parts

760

812

                    .iter()

761

1392

                    .map(|inner| {

762

1682

                        let elems_str = inner.iter().map(|x| format!("{x}")).join(",");

763

1392

                        format!("{{{}}}", elems_str)

764

1392

})

765

812

                    .join(", ");

766

767

812

                write!(f, "partition({elems_str})")

768

769

            AbstractLiteral::Permutation(cycles) => {

770

96628

                let cycles_str: String = cycles

771

96628

                    .iter()

772

104632

                    .map(|cycle| {

773

305486

                        let elems_str = cycle.iter().map(|x| format!("{x}")).join(",");

774

104632

                        format!("({elems_str})")

775

104632

})

776

96628

                    .join("");

777

778

96628

                write!(f, "permutation{cycles_str}")

779

780

            AbstractLiteral::Record(entries) => {

781

916110

                let entries_str: String = entries

782

916110

                    .iter()

783

1832220

                    .map(|entry| format!("{} = {}", entry.name, entry.value))

784

916110

                    .join(",");

785

916110

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

786

787

            AbstractLiteral::Function(entries) => {

788

250792

                let entries_str: String = entries

789

250792

                    .iter()

790

545490

                    .map(|entry| format!("{} --> {}", entry.0, entry.1))

791

250792

                    .join(",");

792

250792

                write!(f, "function({entries_str})")

793

794

            AbstractLiteral::Variant(entry) => {

795

602069

                write!(f, "variant{{{} = {}}}", entry.name, entry.value)

796

797

            AbstractLiteral::Relation(elems) => {

798

30566

                let elems_str: String = elems

799

30566

                    .iter()

800

222372

                    .map(|x| format!("({})", x.iter().map(|x| format!("{x}")).join(",")))

801

30566

                    .join(",");

802

30566

                write!(f, "relation({elems_str})")

803

804

805

36472135

806

807

808

impl<T> Uniplate for AbstractLiteral<T>

809

where

810

    T: AbstractLiteralValue + Biplate<AbstractLiteral<T>>,

811

812

3615354

    fn uniplate(&self) -> (Tree<Self>, Box<dyn Fn(Tree<Self>) -> Self>) {

813

        // walking into T

814

3615354

        match self {

815

            AbstractLiteral::Set(vec) => {

816

418340

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(vec);

817

418340

                (f1_tree, Box::new(move |x| AbstractLiteral::Set(f1_ctx(x))))

818

819

            AbstractLiteral::MSet(vec) => {

820

142008

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(vec);

821

142008

                (f1_tree, Box::new(move |x| AbstractLiteral::MSet(f1_ctx(x))))

822

823

            AbstractLiteral::Matrix(elems, index_domain) => {

824

1972806

                let index_domain = index_domain.clone();

825

1972806

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(elems);

826

827

1972806

                    f1_tree,

828

1972806

                    Box::new(move |x| AbstractLiteral::Matrix(f1_ctx(x), index_domain.clone())),

829

830

831

            AbstractLiteral::Sequence(vec) => {

832

100640

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(vec);

833

834

100640

                    f1_tree,

835

100640

                    Box::new(move |x| AbstractLiteral::Sequence(f1_ctx(x))),

836

837

838

            AbstractLiteral::Tuple(elems) => {

839

752208

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(elems);

840

841

752208

                    f1_tree,

842

752208

                    Box::new(move |x| AbstractLiteral::Tuple(f1_ctx(x))),

843

844

845

            AbstractLiteral::Record(entries) => {

846

122688

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(entries);

847

848

122688

                    f1_tree,

849

122688

                    Box::new(move |x| AbstractLiteral::Record(f1_ctx(x))),

850

851

852

            AbstractLiteral::Function(entries) => {

853

34712

                let entry_count = entries.len();

854

34712

                let flattened: Vec<T> = entries

855

34712

                    .iter()

856

75744

                    .flat_map(|(lhs, rhs)| [lhs.clone(), rhs.clone()])

857

                    .collect();

858

859

                let (f1_tree, f1_ctx) =

860

34712

                    <Vec<T> as Biplate<AbstractLiteral<T>>>::biplate(&flattened);

861

862

34712

                    f1_tree,

863

34712

                    Box::new(move |x| {

864

34712

                        let rebuilt = f1_ctx(x);

865

34712

                        assert_eq!(

866

34712

                            rebuilt.len(),

867

34712

                            entry_count * 2,

868

                            "number of function literal children should remain unchanged"

869

);

870

871

34712

                        let mut iter = rebuilt.into_iter();

872

34712

                        let mut pairs = Vec::with_capacity(entry_count);

873

110456

                        while let (Some(lhs), Some(rhs)) = (iter.next(), iter.next()) {

874

75744

                            pairs.push((lhs, rhs));

875

876

877

34712

                        AbstractLiteral::Function(pairs)

878

34712

}),

879

880

881

            AbstractLiteral::Variant(entries) => {

882

64640

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(entries);

883

884

64640

                    f1_tree,

885

64640

                    Box::new(move |x| AbstractLiteral::Variant(f1_ctx(x))),

886

887

888

            AbstractLiteral::Relation(elems) => {

889

2992

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(elems);

890

891

2992

                    f1_tree,

892

2992

                    Box::new(move |x| AbstractLiteral::Relation(f1_ctx(x))),

893

894

895

            AbstractLiteral::Partition(elems) => {

896

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(elems);

897

898

                    f1_tree,

899

                    Box::new(move |x| AbstractLiteral::Partition(f1_ctx(x))),

900

901

902

            AbstractLiteral::Permutation(elems) => {

903

4320

                let (f1_tree, f1_ctx) = <_ as Biplate<AbstractLiteral<T>>>::biplate(elems);

904

905

4320

                    f1_tree,

906

4320

                    Box::new(move |x| AbstractLiteral::Permutation(f1_ctx(x))),

907

908

909

910

3615354

911

912

913

impl<U, To> Biplate<To> for AbstractLiteral<U>

914

where

915

    To: Uniplate,

916

    U: AbstractLiteralValue + Biplate<AbstractLiteral<U>> + Biplate<To>,

917

    Field<U>: Biplate<AbstractLiteral<U>> + Biplate<To>,

918

919

2142982878

    fn biplate(&self) -> (Tree<To>, Box<dyn Fn(Tree<To>) -> Self>) {

920

2142982878

        if std::any::TypeId::of::<To>() == std::any::TypeId::of::<AbstractLiteral<U>>() {

921

            // To ==From => return One(self)

922

923

            unsafe {

924

                // SAFETY: asserted the type equality above

925

9414623

                let self_to = std::mem::transmute::<&AbstractLiteral<U>, &To>(self).clone();

926

9414623

                let tree = Tree::One(self_to);

927

9414623

                let ctx = Box::new(move |x| {

928

9414618

                    let Tree::One(x) = x else {

929

                        panic!();

930

};

931

932

9414618

                    std::mem::transmute::<&To, &AbstractLiteral<U>>(&x).clone()

933

9414618

});

934

935

9414623

                (tree, ctx)

936

937

        } else {

938

            // walking into T

939

2133568255

            match self {

940

                AbstractLiteral::Set(vec) => {

941

9502618

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(vec);

942

9502618

                    (f1_tree, Box::new(move |x| AbstractLiteral::Set(f1_ctx(x))))

943

944

                AbstractLiteral::MSet(vec) => {

945

1980555

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(vec);

946

1980555

                    (f1_tree, Box::new(move |x| AbstractLiteral::MSet(f1_ctx(x))))

947

948

                AbstractLiteral::Matrix(elems, index_domain) => {

949

2082055164

                    let index_domain = index_domain.clone();

950

2082055164

                    let (f1_tree, f1_ctx) = <Vec<U> as Biplate<To>>::biplate(elems);

951

952

2082055164

                        f1_tree,

953

2082055164

                        Box::new(move |x| AbstractLiteral::Matrix(f1_ctx(x), index_domain.clone())),

954

955

956

                AbstractLiteral::Sequence(vec) => {

957

6169402

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(vec);

958

959

6169402

                        f1_tree,

960

6169402

                        Box::new(move |x| AbstractLiteral::Sequence(f1_ctx(x))),

961

962

963

                AbstractLiteral::Tuple(elems) => {

964

29142100

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(elems);

965

966

29142100

                        f1_tree,

967

29142100

                        Box::new(move |x| AbstractLiteral::Tuple(f1_ctx(x))),

968

969

970

                AbstractLiteral::Record(entries) => {

971

2377333

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(entries);

972

973

2377333

                        f1_tree,

974

2377333

                        Box::new(move |x| AbstractLiteral::Record(f1_ctx(x))),

975

976

977

                AbstractLiteral::Function(entries) => {

978

377899

                    let entry_count = entries.len();

979

377899

                    let flattened: Vec<U> = entries

980

377899

                        .iter()

981

822672

                        .flat_map(|(lhs, rhs)| [lhs.clone(), rhs.clone()])

982

                        .collect();

983

984

377899

                    let (f1_tree, f1_ctx) = <Vec<U> as Biplate<To>>::biplate(&flattened);

985

986

377899

                        f1_tree,

987

377899

                        Box::new(move |x| {

988

125831

                            let rebuilt = f1_ctx(x);

989

125831

                            assert_eq!(

990

125831

                                rebuilt.len(),

991

125831

                                entry_count * 2,

992

                                "number of function literal children should remain unchanged"

993

);

994

995

125831

                            let mut iter = rebuilt.into_iter();

996

125831

                            let mut pairs = Vec::with_capacity(entry_count);

997

400403

                            while let (Some(lhs), Some(rhs)) = (iter.next(), iter.next()) {

998

274572

                                pairs.push((lhs, rhs));

999

1000

1001

125831

                            AbstractLiteral::Function(pairs)

1002

125831

}),

1003

1004

1005

                AbstractLiteral::Variant(entries) => {

1006

1764273

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(entries);

1007

1008

1764273

                        f1_tree,

1009

1764273

                        Box::new(move |x| AbstractLiteral::Variant(f1_ctx(x))),

1010

1011

1012

                AbstractLiteral::Relation(elems) => {

1013

45704

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(elems);

1014

1015

45704

                        f1_tree,

1016

45704

                        Box::new(move |x| AbstractLiteral::Relation(f1_ctx(x))),

1017

1018

1019

                AbstractLiteral::Partition(elems) => {

1020

3016

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(elems);

1021

1022

3016

                        f1_tree,

1023

3016

                        Box::new(move |x| AbstractLiteral::Partition(f1_ctx(x))),

1024

1025

1026

                AbstractLiteral::Permutation(elems) => {

1027

150191

                    let (f1_tree, f1_ctx) = <_ as Biplate<To>>::biplate(elems);

1028

1029

150191

                        f1_tree,

1030

150191

                        Box::new(move |x| AbstractLiteral::Permutation(f1_ctx(x))),

1031

1032

1033

1034

1035

2142982878

1036

1037

622360124

    fn children_bi_count(&self) -> usize {

1038

        // Manual `biplate` (not derive): delegate counts to the plated containers so wide

1039

        // matrices/lists stay O(1) instead of materialising `children_bi`.

1040

622360124

        if std::any::TypeId::of::<To>() == std::any::TypeId::of::<AbstractLiteral<U>>() {

1041

            return 1;

1042

622360124

1043

622360124

        match self {

1044

            AbstractLiteral::Set(v)

1045

            | AbstractLiteral::MSet(v)

1046

            | AbstractLiteral::Sequence(v)

1047

            | AbstractLiteral::Tuple(v)

1048

621966710

            | AbstractLiteral::Matrix(v, _) => <Vec<U> as Biplate<To>>::children_bi_count(v),

1049

            AbstractLiteral::Record(entries) => {

1050

37410

                <Vec<Field<U>> as Biplate<To>>::children_bi_count(entries)

1051

1052

            AbstractLiteral::Variant(entry) => {

1053

293625

                <Moo<Field<U>> as Biplate<To>>::children_bi_count(entry)

1054

1055

            AbstractLiteral::Relation(elems)

1056

            | AbstractLiteral::Partition(elems)

1057

            | AbstractLiteral::Permutation(elems) => {

1058

62379

                <Vec<Vec<U>> as Biplate<To>>::children_bi_count(elems)

1059

1060

            AbstractLiteral::Function(_) => <Self as Biplate<To>>::children_bi(self).len(),

1061

1062

622360124

1063

1064

622360124

    fn try_replace_child_at_bi(&mut self, index: usize, child: To) -> bool {

1065

        // Same as `children_bi_count`: keep in-place updates for owned vectors (lee-distance).

1066

622360124

        if std::any::TypeId::of::<To>() == std::any::TypeId::of::<AbstractLiteral<U>>() {

1067

            if index != 0 {

1068

                return false;

1069

1070

            // SAFETY: TypeId equality means To and AbstractLiteral<U> are the same type.

1071

            unsafe {

1072

                let child_as_self = std::mem::transmute_copy::<To, AbstractLiteral<U>>(&child);

1073

                std::mem::forget(child);

1074

                *self = child_as_self;

1075

1076

            return true;

1077

622360124

1078

622360124

        match self {

1079

            AbstractLiteral::Set(v)

1080

            | AbstractLiteral::MSet(v)

1081

            | AbstractLiteral::Sequence(v)

1082

            | AbstractLiteral::Tuple(v)

1083

            | AbstractLiteral::Matrix(v, _) => {

1084

621966710

                <Vec<U> as Biplate<To>>::try_replace_child_at_bi(v, index, child)

1085

1086

            AbstractLiteral::Record(entries) => {

1087

37410

                <Vec<Field<U>> as Biplate<To>>::try_replace_child_at_bi(entries, index, child)

1088

1089

            AbstractLiteral::Variant(entry) => {

1090

293625

                <Moo<Field<U>> as Biplate<To>>::try_replace_child_at_bi(entry, index, child)

1091

1092

            AbstractLiteral::Relation(elems)

1093

            | AbstractLiteral::Partition(elems)

1094

            | AbstractLiteral::Permutation(elems) => {

1095

62379

                <Vec<Vec<U>> as Biplate<To>>::try_replace_child_at_bi(elems, index, child)

1096

1097

            AbstractLiteral::Function(_) => {

1098

                let mut children = <Self as Biplate<To>>::children_bi(self);

1099

                if index >= children.len() {

1100

                    return false;

1101

1102

                children[index] = child;

1103

                *self = self.with_children_bi(children);

1104

                true

1105

1106

1107

622360124

1108

1109

1110

impl TryFrom<Literal> for i32 {

1111

    type Error = &'static str;

1112

1113

121981250

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

1114

121981250

        match value {

1115

121981221

            Literal::Int(i) => Ok(i),

1116

29

            _ => Err("Cannot convert non-i32 literal to i32"),

1117

1118

121981250

1119

1120

1121

impl TryFrom<Box<Literal>> for i32 {

1122

    type Error = &'static str;

1123

1124

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

1125

        (*value).try_into()

1126

1127

1128

1129

impl TryFrom<&Box<Literal>> for i32 {

1130

    type Error = &'static str;

1131

1132

    fn try_from(value: &Box<Literal>) -> Result<Self, Self::Error> {

1133

        TryFrom::<&Literal>::try_from(value.as_ref())

1134

1135

1136

1137

impl TryFrom<&Moo<Literal>> for i32 {

1138

    type Error = &'static str;

1139

1140

    fn try_from(value: &Moo<Literal>) -> Result<Self, Self::Error> {

1141

        TryFrom::<&Literal>::try_from(value.as_ref())

1142

1143

1144

1145

impl TryFrom<&Literal> for i32 {

1146

    type Error = &'static str;

1147

1148

1957004

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

1149

1957004

        match value {

1150

1957004

            Literal::Int(i) => Ok(*i),

1151

            _ => Err("Cannot convert non-i32 literal to i32"),

1152

1153

1957004

1154

1155

1156

impl TryFrom<Literal> for bool {

1157

    type Error = &'static str;

1158

1159

28169954

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

1160

28169954

        match value {

1161

28169074

            Literal::Bool(b) => Ok(b),

1162

880

            _ => Err("Cannot convert non-bool literal to bool"),

1163

1164

28169954

1165

1166

1167

impl TryFrom<&Literal> for bool {

1168

    type Error = &'static str;

1169

1170

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

1171

        match value {

1172

            Literal::Bool(b) => Ok(*b),

1173

            _ => Err("Cannot convert non-bool literal to bool"),

1174

1175

1176

1177

1178

impl TryFrom<Literal> for EnumVariant {

1179

    type Error = &'static str;

1180

1181

16

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

1182

16

        match value {

1183

16

            Literal::EnumVariant(v) => Ok(v),

1184

            _ => Err("Cannot convert non-enum literal to enum variant"),

1185

1186

16

1187

1188

1189

impl TryFrom<&Literal> for EnumVariant {

1190

    type Error = &'static str;

1191

1192

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

1193

        match value {

1194

            Literal::EnumVariant(v) => Ok(v.clone()),

1195

            _ => Err("Cannot convert non-enum literal to enum variant"),

1196

1197

1198

1199

1200

impl From<i32> for Literal {

1201

149050813

    fn from(i: i32) -> Self {

1202

149050813

        Literal::Int(i)

1203

149050813

1204

1205

1206

impl From<bool> for Literal {

1207

2807711

    fn from(b: bool) -> Self {

1208

2807711

        Literal::Bool(b)

1209

2807711

1210

1211

1212

impl From<Literal> for Ustr {

1213

    fn from(value: Literal) -> Self {

1214

        // TODO: avoid the temporary-allocation of a string by format! here?

1215

        Ustr::from(&format!("{value}"))

1216

1217

1218

1219

impl From<AbstractLiteral<Literal>> for Literal {

1220

13023414

    fn from(literal: AbstractLiteral<Literal>) -> Self {

1221

13023414

        Literal::AbstractLiteral(literal)

1222

13023414

1223

1224

1225

impl AbstractLiteral<Expression> {

1226

    /// If all the elements are literals, returns this as an AbstractLiteral<Literal>.

1227

    /// Otherwise, returns `None`.

1228

101943167

    pub fn into_literals(self) -> Option<AbstractLiteral<Literal>> {

1229

101943167

        match self {

1230

            AbstractLiteral::Set(elements) => {

1231

1359179

                let literals = elements

1232

1359179

                    .into_iter()

1233

3108679

                    .map(|expr| match expr {

1234

2112024

                        Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1235

                        Expression::AbstractLiteral(_, abslit) => {

1236

993366

                            Some(Literal::AbstractLiteral(abslit.into_literals()?))

1237

1238

3289

                        _ => None,

1239

3108679

})

1240

303120

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

1241

1056059

                Some(AbstractLiteral::Set(literals))

1242

1243

            AbstractLiteral::MSet(elements) => {

1244

92394

                let literals = elements

1245

92394

                    .into_iter()

1246

123192

                    .map(|expr| match expr {

1247

123192

                        Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1248

                        Expression::AbstractLiteral(_, abslit) => {

1249

                            Some(Literal::AbstractLiteral(abslit.into_literals()?))

1250

1251

                        _ => None,

1252

123192

})

1253

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

1254

92394

                Some(AbstractLiteral::MSet(literals))

1255

1256

            AbstractLiteral::Partition(elems) => {

1257

                // want to ascertain if every elem in Vec<Vec<Expr>> is a literal. If any are not, return none

1258

                // otherwise confirm it is an abslit<lit>

1259

522

                let mut partition: Vec<Vec<_>> = Vec::new();

1260

1261

522

                for part in elems {

1262

522

                    let literals = part

1263

522

                        .into_iter()

1264

522

                        .map(|expr| match expr {

1265

522

                            Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1266

                            Expression::AbstractLiteral(_, abslit) => {

1267

                                Some(Literal::AbstractLiteral(abslit.into_literals()?))

1268

1269

                            _ => None,

1270

522

})

1271

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

1272

1273

522

                    partition.push(literals);

1274

1275

1276

522

                Some(AbstractLiteral::Partition(partition))

1277

1278

            AbstractLiteral::Permutation(elems) => {

1279

43622

                let mut permutation: Vec<Vec<_>> = Vec::new();

1280

1281

43622

                for cycle in elems {

1282

44410

                    let literals = cycle

1283

44410

                        .into_iter()

1284

131310

                        .map(|expr| match expr {

1285

131310

                            Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1286

                            Expression::AbstractLiteral(_, abslit) => {

1287

                                Some(Literal::AbstractLiteral(abslit.into_literals()?))

1288

1289

                            _ => None,

1290

131310

})

1291

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

1292

1293

44410

                    permutation.push(literals);

1294

1295

1296

43622

                Some(AbstractLiteral::Permutation(permutation))

1297

1298

            AbstractLiteral::Matrix(items, domain) => {

1299

96361985

                let mut literals = vec![];

1300

96361985

                for item in items {

1301

114427736

                    let literal = match item {

1302

26466639

                        Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1303

                        Expression::AbstractLiteral(_, abslit) => {

1304

1512436

                            Some(Literal::AbstractLiteral(abslit.into_literals()?))

1305

1306

86448661

                        _ => None,

1307

86448661

}?;

1308

27917827

                    literals.push(literal);

1309

1310

1311

9852076

                Some(AbstractLiteral::Matrix(literals, domain.resolve().ok()?))

1312

1313

            AbstractLiteral::Sequence(elements) => {

1314

1924527

                let literals = elements

1315

1924527

                    .into_iter()

1316

2540545

                    .map(|expr| match expr {

1317

1090487

                        Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1318

                        Expression::AbstractLiteral(_, abslit) => {

1319

                            Some(Literal::AbstractLiteral(abslit.into_literals()?))

1320

1321

1450058

                        _ => None,

1322

2540545

})

1323

1450058

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

1324

474469

                Some(AbstractLiteral::Sequence(literals))

1325

1326

            AbstractLiteral::Tuple(items) => {

1327

1966635

                let mut literals = vec![];

1328

1966635

                for item in items {

1329

3871007

                    let literal = match item {

1330

3724847

                        Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1331

                        Expression::AbstractLiteral(_, abslit) => {

1332

29

                            Some(Literal::AbstractLiteral(abslit.into_literals()?))

1333

1334

146131

                        _ => None,

1335

146131

}?;

1336

3724876

                    literals.push(literal);

1337

1338

1339

1820504

                Some(AbstractLiteral::Tuple(literals))

1340

1341

            AbstractLiteral::Record(entries) => {

1342

39904

                let mut literals = vec![];

1343

39904

                for entry in entries {

1344

79808

                    let literal = match entry.value {

1345

79808

                        Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1346

                        Expression::AbstractLiteral(_, abslit) => {

1347

                            Some(Literal::AbstractLiteral(abslit.into_literals()?))

1348

1349

                        _ => None,

1350

}?;

1351

1352

79808

                    literals.push((entry.name, literal));

1353

1354

                Some(AbstractLiteral::Record(

1355

39904

                    literals

1356

39904

                        .into_iter()

1357

                        .map(|(name, literal)| Field {

1358

79808

                            name,

1359

79808

                            value: literal,

1360

79808

})

1361

                        .collect(),

1362

))

1363

1364

            AbstractLiteral::Function(_) => todo!("Implement into_literals for functions"),

1365

            AbstractLiteral::Variant(entry) => {

1366

148048

                let literal = match entry.value.clone() {

1367

8471

                    Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1368

                    Expression::AbstractLiteral(_, abslit) => {

1369

                        Some(Literal::AbstractLiteral(abslit.into_literals()?))

1370

1371

139577

                    _ => None,

1372

139577

}?;

1373

8471

                Some(AbstractLiteral::Variant(Moo::new(Field {

1374

8471

                    name: entry.name.clone(),

1375

8471

                    value: literal,

1376

8471

                })))

1377

1378

            AbstractLiteral::Relation(tuples) => {

1379

6351

                let mut literal_tuples = Vec::with_capacity(tuples.len());

1380

6351

                for fields in tuples {

1381

19053

                    let literals = fields

1382

19053

                        .into_iter()

1383

38106

                        .map(|expr| match expr {

1384

38106

                            Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),

1385

                            Expression::AbstractLiteral(_, abslit) => {

1386

                                Some(Literal::AbstractLiteral(abslit.into_literals()?))

1387

1388

                            _ => None,

1389

38106

})

1390

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

1391

19053

                    literal_tuples.push(literals);

1392

1393

6351

                Some(AbstractLiteral::Relation(literal_tuples))

1394

1395

1396

101943167

1397

1398

1399

// need display implementations for other types as well

1400

impl Display for Literal {

1401

187079734

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

1402

187079734

        match &self {

1403

147857976

            Literal::Int(i) => write!(f, "{i}"),

1404

8985369

            Literal::Bool(b) => write!(f, "{b}"),

1405

96

            Literal::EnumVariant(ev) => write!(f, "{}", ev.name()),

1406

8

            Literal::Unnamed(value) => write!(f, "{}_{}", value.ty.name, value.value),

1407

30236285

            Literal::AbstractLiteral(l) => write!(f, "{l}"),

1408

1409

187079734

1410

1411

1412

#[cfg(test)]

1413

mod tests {

1414

1415

    use super::*;

1416

    use crate::ast::matrix::{flatten, partial_flatten, shape_of};

1417

    use crate::ast::{DeclarationPtr, Metadata, Name};

1418

    use crate::{domain_int_ground, into_matrix, matrix, matrix_lit, range};

1419

    use uniplate::Uniplate;

1420

1421

    #[test]

1422

1

    fn essence_value_ordering_uses_occurrence_lex_for_sets() {

1423

8

        let set = |values: &[i32]| {

1424

8

            Literal::AbstractLiteral(AbstractLiteral::Set(

1425

8

                values.iter().copied().map(Literal::Int).collect(),

1426

8

))

1427

8

};

1428

1

        let ordered = [

1429

1

            set(&[]),

1430

1

            set(&[3]),

1431

1

            set(&[2]),

1432

1

            set(&[2, 3]),

1433

1

            set(&[1]),

1434

1

            set(&[1, 3]),

1435

1

            set(&[1, 2]),

1436

1

            set(&[1, 2, 3]),

1437

1

];

1438

1439

1

        for pair in ordered.windows(2) {

1440

7

            assert_eq!(pair[0].essence_cmp(&pair[1]), Ordering::Less);

1441

1442

1

1443

1444

    #[test]

1445

1

    fn essence_value_ordering_is_lexicographic_for_tuples_and_matrices() {

1446

4

        let tuple = |values: &[i32]| {

1447

4

            Literal::AbstractLiteral(AbstractLiteral::Tuple(

1448

4

                values.iter().copied().map(Literal::Int).collect(),

1449

4

))

1450

4

};

1451

1

        assert_eq!(tuple(&[1, 2]).essence_cmp(&tuple(&[1, 3])), Ordering::Less);

1452

1

        assert_eq!(

1453

1

            tuple(&[1, 2]).essence_cmp(&tuple(&[1, 2, 0])),

1454

1

            Ordering::Less

1455

);

1456

1457

2

        let matrix = |values: &[i32]| {

1458

2

            Literal::AbstractLiteral(AbstractLiteral::Matrix(

1459

2

                values.iter().copied().map(Literal::Int).collect(),

1460

2

                Moo::new(GroundDomain::Int(

1461

2

                    vec![Range::Bounded(1, values.len() as i32)],

1462

2

                    None,

1463

2

)),

1464

2

))

1465

2

};

1466

1

        assert_eq!(

1467

1

            matrix(&[1, 2]).essence_cmp(&matrix(&[1, 3])),

1468

1

            Ordering::Less

1469

);

1470

1

1471

1472

    #[test]

1473

1

    fn mset_domain_accepts_domain_letting_references() {

1474

1

        let declaration = DeclarationPtr::new_domain_letting(

1475

1

            Name::user("NUM"),

1476

1

            Domain::int(vec![Range::Bounded(1, 999)]),

1477

1

);

1478

1

        let alias = Domain::reference(declaration).unwrap();

1479

1

        let item = Expression::DomainAnnotation(

1480

1

            Metadata::new(),

1481

1

            Moo::new(Expression::Atomic(

1482

1

                Metadata::new(),

1483

1

                Atom::Literal(Literal::Int(1)),

1484

1

)),

1485

1

            alias,

1486

1

);

1487

1488

1

        let domain = AbstractLiteral::MSet(vec![item.clone(), item])

1489

1

            .domain_of()

1490

1

            .unwrap();

1491

1

        let (_, item_domain) = domain.as_mset().unwrap();

1492

1493

1

        assert_eq!(

1494

1

            item_domain.resolve(),

1495

1

            Ok(Moo::new(GroundDomain::Int(

1496

1

                vec![Range::Bounded(1, 999)],

1497

1

                None

1498

1

)))

1499

);

1500

1

1501

1502

    #[test]

1503

1

    fn matrix_uniplate_universe() {

1504

        // Can we traverse through matrices with uniplate?

1505

1

        let my_matrix: AbstractLiteral<Literal> = into_matrix![

1506

1

            vec![Literal::AbstractLiteral(matrix![Literal::Bool(true);Moo::new(GroundDomain::Bool)]); 5];

1507

1

            Moo::new(GroundDomain::Bool)

1508

];

1509

1510

1

        let expected_index_domains = vec![Moo::new(GroundDomain::Bool); 6];

1511

        let actual_index_domains: Vec<Moo<GroundDomain>> =

1512

6

            my_matrix.cata(&move |elem, children| {

1513

6

                let mut res = vec![];

1514

6

                res.extend(children.into_iter().flatten());

1515

6

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

1516

6

                    res.push(index_domain);

1517

1518

1519

6

res

1520

6

});

1521

1522

1

        assert_eq!(actual_index_domains, expected_index_domains);

1523

1

1524

1525

    #[test]

1526

1

    fn matrix_flatten() {

1527

1

        let tensor: AbstractLiteral<Literal> = matrix![

1528

1529

                // batch 1

1530

1

                [1, 2, 3, 4],

1531

1

                [5, 6, 7, 8],

1532

1

                [9, 10, 11, 12]

1533

],

1534

1535

                // batch 2

1536

1

                [13, 14, 15, 16],

1537

1

                [17, 18, 19, 20],

1538

1

                [21, 22, 23, 24]

1539

1540

];

1541

1542

1

        let actual_elems: Vec<Literal> = flatten(&tensor).cloned().collect();

1543

1

        let expected_elems = (1..25).map(Literal::from).collect::<Vec<_>>();

1544

1

        assert_eq!(actual_elems, expected_elems);

1545

1

1546

1547

    #[test]

1548

1

    fn matrix_domain_1d() {

1549

1

        let matrix = matrix_lit![10, 11, 12, 13; domain_int_ground!(1..4)];

1550

1

        let dom = matrix.domain_of();

1551

1552

1

        let (inner_dom, idx_doms) = dom.as_matrix_ground().expect("must be ground matrix");

1553

1

        assert_eq!(inner_dom, &domain_int_ground!(10..13));

1554

1

        assert_eq!(idx_doms.len(), 1);

1555

1

        assert_eq!(&idx_doms[0], &domain_int_ground!(1..4));

1556

1

1557

1558

    #[test]

1559

1

    fn matrix_domain_2d() {

1560

1

        let matrix = matrix_lit![

1561

1

            [1, 2, 3, 4],

1562

1

            [5, 6, 7, 8];

1563

1564

1

                domain_int_ground!(1..2),

1565

1

                domain_int_ground!(1..4)

1566

1567

];

1568

1

        let dom = matrix.domain_of();

1569

1570

1

        let (inner_dom, idx_doms) = dom.as_matrix_ground().expect("must be ground matrix");

1571

1

        assert_eq!(inner_dom, &domain_int_ground!(1..8));

1572

1

        assert_eq!(idx_doms.len(), 2);

1573

1

        assert_eq!(&idx_doms[0], &domain_int_ground!(1..2));

1574

1

        assert_eq!(&idx_doms[1], &domain_int_ground!(1..4));

1575

1

1576

1577

    #[test]

1578

1

    fn matrix_shape_3d() {

1579

1

        let tensor: AbstractLiteral<Literal> = matrix![

1580

1581

1

                [1, 2, 3, 4],

1582

1

                [5, 6, 7, 8],

1583

1

                [9, 10, 11, 12]

1584

],

1585

1586

1

                [13, 14, 15, 16],

1587

1

                [17, 18, 19, 20],

1588

1

                [21, 22, 23, 24]

1589

];

1590

1591

1

                domain_int_ground!(1..2),

1592

1

                domain_int_ground!(1..3),

1593

1

                domain_int_ground!(1..4)

1594

1595

];

1596

1

        let shape = shape_of(&tensor).expect("shape_of to work on a 3D matrix");

1597

1598

1

        assert_eq!(shape.size, 24);

1599

1

        assert_eq!(shape.dims, vec![2, 3, 4]);

1600

1

        assert_eq!(shape.strides, vec![12, 4, 1]);

1601

1

        assert_eq!(

1602

1

            shape.idx_doms,

1603

1

            vec![

1604

1

                domain_int_ground!(1..2),

1605

1

                domain_int_ground!(1..3),

1606

1

                domain_int_ground!(1..4)

1607

1608

);

1609

1

1610

1611

    #[test]

1612

1

    fn matrix_partial_flatten() {

1613

1

        let tensor: AbstractLiteral<Literal> = matrix![

1614

1615

                // batch 1

1616

1

                [1, 2, 3, 4],

1617

1

                [5, 6, 7, 8],

1618

1

                [9, 10, 11, 12]

1619

],

1620

1621

                // batch 2

1622

1

                [13, 14, 15, 16],

1623

1

                [17, 18, 19, 20],

1624

1

                [21, 22, 23, 24]

1625

1626

];

1627

1

        assert_eq!(partial_flatten(0, tensor.clone()), tensor);

1628

1629

1

        let expected_flatten_1: AbstractLiteral<Literal> = matrix![

1630

1

            [1, 2, 3, 4],

1631

1

            [5, 6, 7, 8],

1632

1

            [9, 10, 11, 12],

1633

1

            [13, 14, 15, 16],

1634

1

            [17, 18, 19, 20],

1635

1

            [21, 22, 23, 24]

1636

];

1637

1

        assert_eq!(partial_flatten(1, tensor.clone()), expected_flatten_1);

1638

1639

        let expected_flatten_2 =

1640

1

            AbstractLiteral::matrix_implied_indices((1..25).map(Literal::from).collect());

1641

1

        assert_eq!(partial_flatten(2, tensor), expected_flatten_2);

1642

1

1643