1
use std::borrow::Cow;
2
use std::collections::{HashSet, VecDeque};
3
use std::fmt::{Display, Formatter};
4
use std::hash::{DefaultHasher, Hash, Hasher};
5
use std::sync::atomic::{AtomicU64, Ordering};
6

            
7
static HASH_HITS: AtomicU64 = AtomicU64::new(0);
8
static HASH_MISSES: AtomicU64 = AtomicU64::new(0);
9

            
10
pub fn print_hash_stats() {
11
    println!(
12
        "Expression content hash stats: hits={}, misses={}",
13
        HASH_HITS.load(Ordering::Relaxed),
14
        HASH_MISSES.load(Ordering::Relaxed)
15
    );
16
}
17
use tracing::trace;
18

            
19
use conjure_cp_enum_compatibility_macro::{document_compatibility, generate_discriminants};
20
use itertools::Itertools;
21
use serde::{Deserialize, Serialize};
22
use ustr::Ustr;
23

            
24
use polyquine::Quine;
25
use uniplate::{Biplate, Uniplate};
26

            
27
use crate::ast::metadata::NO_HASH;
28
use crate::bug;
29

            
30
use super::ac_operators::ACOperatorKind;
31
use super::categories::{Category, CategoryOf};
32
use super::collection_domains::{
33
    SetOperation, SizeBounds, bounded_set, collection_size, distinct_size, mset_size,
34
    set_operation_domain,
35
};
36
use super::comprehension::Comprehension;
37
use super::declaration::DeclarationKind;
38
use super::domains::HasDomain as _;
39
use super::eval::eval_constant;
40
use super::expression_domains::{
41
    absolute_integer_domain, binary_integer_domain,
42
    bounded_i32_domain_for_matrix_literal_monotonic, division_domain,
43
    empty_matrix_integer_element_domain, factorial_domain, get_function_codomain,
44
    matrix_element_domain, modulo_domain, mset_union_result_domain, power_integer_domain,
45
    sum_domain_of_child,
46
};
47
use super::function_domains::{
48
    defined_domain, function_size, image_set_domain, pre_image_domain, range_domain,
49
    restricted_domain,
50
};
51
use super::pretty::{pretty_expression_domain_annotation, pretty_expression_type_annotation};
52
use super::pretty::{pretty_expressions_as_top_level, pretty_vec};
53
use super::records::Field;
54
use super::sat_encoding::SATIntEncoding;
55
use super::{
56
    AbstractLiteral, Atom, DeclarationPtr, Domain, DomainPtr, GroundDomain, IntVal, Literal,
57
    MSetAttr, Metadata, Model, Moo, Name, PartialityAttr, Range, Reference, RelAttr, ReturnType,
58
    SetAttr, SymbolTable, SymbolTablePtr, Typeable, matrix,
59
};
60

            
61
// Ensure that this type doesn't get too big
62
//
63
// If you triggered this assertion, you either made a variant of this enum that is too big, or you
64
// made Name,Literal,AbstractLiteral,Atom bigger, which made this bigger! To fix this, put some
65
// stuff in boxes.
66
//
67
// Enums take the size of their largest variant, so an enum with mostly small variants and a few
68
// large ones wastes memory... A larger Expression type also slows down Oxide.
69
//
70
// For more information, and more details on type sizes and how to measure them, see the commit
71
// message for 6012de809 (perf: reduce size of AST types, 2025-06-18).
72
//
73
// You can also see type sizes in the rustdoc documentation, generated by ./tools/gen_docs.sh
74
//
75
// https://github.com/conjure-cp/conjure-oxide/commit/6012de8096ca491ded91ecec61352fdf4e994f2e
76

            
77
// TODO: box all usages of Metadata to bring this down a bit more - I have added variants to
78
// ReturnType, and Metadata contains ReturnType, so Metadata has got bigger. Metadata will get a
79
// lot bigger still when we start using it for memoisation, so it should really be
80
// boxed ~niklasdewally
81

            
82
// Metadata's mutex makes the exact layout platform-dependent, so enforce only the intended
83
// upper bound. The largest known layout is 152 bytes.
84
static_assertions::const_assert!(std::mem::size_of::<Expression>() <= 152);
85

            
86
/// Represents different types of expressions used to define rules and constraints in the model.
87
///
88
/// The `Expression` enum includes operations, constants, and variable references
89
/// used to build rules and conditions for the model.
90
#[generate_discriminants]
91
#[document_compatibility]
92
#[derive(Clone, Debug, Hash, PartialEq, Eq, Serialize, Deserialize, Uniplate, Quine)]
93
#[biplate(to=AbstractLiteral<Expression>)]
94
#[biplate(to=AbstractLiteral<Literal>)]
95
#[biplate(to=Atom)]
96
#[biplate(to=Comprehension)]
97
#[biplate(to=DeclarationPtr)]
98
#[biplate(to=DomainPtr)]
99
#[biplate(to=Literal)]
100
#[biplate(to=Metadata)]
101
#[biplate(to=Name)]
102
#[biplate(to=Option<Expression>)]
103
#[biplate(to=Field<Expression>)]
104
#[biplate(to=Field<Literal>)]
105
#[biplate(to=Reference)]
106
#[biplate(to=Model)]
107
#[biplate(to=SymbolTable)]
108
#[biplate(to=SymbolTablePtr)]
109
#[biplate(to=Vec<Expression>)]
110
#[path_prefix(conjure_cp::ast)]
111
pub enum Expression {
112
    AbstractLiteral(Metadata, AbstractLiteral<Expression>),
113
    /// The top of the model
114
    Root(Metadata, Vec<Expression>),
115

            
116
    /// An expression representing "A is valid as long as B is true"
117
    /// Turns into a conjunction when it reaches a boolean context
118
    Bubble(Metadata, Moo<Expression>, Moo<Expression>),
119

            
120
    /// A comprehension.
121
    ///
122
    /// The inside of the comprehension opens a new scope.
123
    // todo (gskorokhod): Comprehension contains a symbol table which contains a bunch of pointers.
124
    // This makes implementing Quine tricky (it doesnt support Rc, by design). Skip it for now.
125
    #[polyquine_skip]
126
    Comprehension(Metadata, Moo<Comprehension>),
127

            
128
    /// Defines dominance ("Solution A is preferred over Solution B")
129
    DominanceRelation(Metadata, Moo<Expression>),
130
    /// `fromSolution(name)` - Used in dominance relation definitions
131
    FromSolution(Metadata, Moo<Atom>),
132

            
133
    #[polyquine_with(arm = (_, name) => {
134
        let ident = proc_macro2::Ident::new(name.as_str(), proc_macro2::Span::call_site());
135
        quote::quote! { #ident.clone().into() }
136
    })]
137
    Metavar(Metadata, Ustr),
138

            
139
    Atomic(Metadata, Atom),
140

            
141
    /// Type annotation expression: `expr :: type`.
142
    TypeAnnotation(Metadata, Moo<Expression>, DomainPtr),
143

            
144
    /// Domain annotation expression: `expr : domain`.
145
    DomainAnnotation(Metadata, Moo<Expression>, DomainPtr),
146

            
147
    /// Asserts that the given variant of a variant expression is in use.
148
    /// See also: [GroundDomain::Variant]
149
    #[compatible(JsonInput)]
150
    Active(Metadata, Moo<Expression>, Name),
151

            
152
    /// Indexing into a record expression, e.g `{foo = 1, bar = true}[foo]`
153
    /// See also: [GroundDomain::Record]
154
    #[compatible(JsonInput)]
155
    RecordField(Metadata, Moo<Expression>, Name),
156

            
157
    /// A matrix index.
158
    ///
159
    /// Defined iff the indices are within their respective index domains.
160
    #[compatible(JsonInput)]
161
    UnsafeIndex(Metadata, Moo<Expression>, Vec<Expression>),
162

            
163
    /// A safe matrix index.
164
    ///
165
    /// See [`Expression::UnsafeIndex`]
166
    #[compatible(SMT)]
167
    SafeIndex(Metadata, Moo<Expression>, Vec<Expression>),
168

            
169
    /// Internal total element definition. Outside the index domain, the value is unconstrained.
170
    /// Safe indexing introduces this before representation-specific comparisons finish lowering.
171
    #[polyquine_skip]
172
    SatElement(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),
173

            
174
    /// Whole-value distinctness after constructing representation-independent comparisons.
175
    SatAllDifferentComparisons(Metadata, Moo<Expression>),
176

            
177
    /// A matrix slice: `a[indices]`.
178
    ///
179
    /// One of the indicies may be `None`, representing the dimension of the matrix we want to take
180
    /// a slice of. For example, for some 3d matrix a, `a[1,..,2]` has the indices
181
    /// `Some(1),None,Some(2)`.
182
    ///
183
    /// It is assumed that the slice only has one "wild-card" dimension and thus is 1 dimensional.
184
    ///
185
    /// Defined iff the defined indices are within their respective index domains.
186
    #[compatible(JsonInput)]
187
    UnsafeSlice(Metadata, Moo<Expression>, Vec<Option<Expression>>),
188

            
189
    /// A safe matrix slice: `a[indices]`.
190
    ///
191
    /// See [`Expression::UnsafeSlice`].
192
    SafeSlice(Metadata, Moo<Expression>, Vec<Option<Expression>>),
193

            
194
    /// `inDomain(x,domain)` iff `x` is in the domain `domain`.
195
    ///
196
    /// This cannot be constructed from Essence input, nor passed to a solver: this expression is
197
    /// mainly used during the conversion of `UnsafeIndex` and `UnsafeSlice` to `SafeIndex` and
198
    /// `SafeSlice` respectively.
199
    InDomain(Metadata, Moo<Expression>, DomainPtr),
200

            
201
    /// `toInt(b)` casts boolean expression b to an integer.
202
    ///
203
    /// - If b is false, then `toInt(b) == 0`
204
    ///
205
    /// - If b is true, then `toInt(b) == 1`
206
    #[compatible(SMT)]
207
    ToInt(Metadata, Moo<Expression>),
208

            
209
    /// `|x|` - absolute value of `x`
210
    #[compatible(JsonInput, SMT)]
211
    Abs(Metadata, Moo<Expression>),
212

            
213
    /// `sum(<vec_expr>)`
214
    #[compatible(JsonInput, SMT)]
215
    Sum(Metadata, Moo<Expression>),
216

            
217
    /// `a * b * c * ...`
218
    #[compatible(JsonInput, SMT)]
219
    Product(Metadata, Moo<Expression>),
220

            
221
    /// `min(<vec_expr>)`
222
    #[compatible(JsonInput, SMT)]
223
    Min(Metadata, Moo<Expression>),
224

            
225
    /// `max(<vec_expr>)`
226
    #[compatible(JsonInput, SMT)]
227
    Max(Metadata, Moo<Expression>),
228

            
229
    /// `not(a)`
230
    #[compatible(JsonInput, SAT, SMT)]
231
    Not(Metadata, Moo<Expression>),
232

            
233
    /// `or(<vec_expr>)`
234
    #[compatible(JsonInput, SAT, SMT)]
235
    Or(Metadata, Moo<Expression>),
236

            
237
    /// `and(<vec_expr>)`
238
    #[compatible(JsonInput, SAT, SMT)]
239
    And(Metadata, Moo<Expression>),
240

            
241
    /// Ensures that `a->b` (material implication).
242
    #[compatible(JsonInput, SMT)]
243
    Imply(Metadata, Moo<Expression>, Moo<Expression>),
244

            
245
    /// `iff(a, b)` a <-> b
246
    #[compatible(JsonInput, SMT)]
247
    Iff(Metadata, Moo<Expression>, Moo<Expression>),
248

            
249
    #[compatible(JsonInput)]
250
    Union(Metadata, Moo<Expression>, Moo<Expression>),
251

            
252
    #[compatible(JsonInput)]
253
    In(Metadata, Moo<Expression>, Moo<Expression>),
254

            
255
    #[compatible(JsonInput)]
256
    Intersect(Metadata, Moo<Expression>, Moo<Expression>),
257

            
258
    /// Set difference, `a - b`.
259
    ///
260
    /// Spelled with minus in Essence, but kept apart from [`Expression::Minus`]: the two share a
261
    /// symbol and nothing else, and overloading one node for both made every arithmetic rule have
262
    /// to ask whether its operands were really sets.
263
    #[compatible(JsonInput)]
264
    Difference(Metadata, Moo<Expression>, Moo<Expression>),
265

            
266
    #[compatible(JsonInput)]
267
    Supset(Metadata, Moo<Expression>, Moo<Expression>),
268

            
269
    #[compatible(JsonInput)]
270
    SupsetEq(Metadata, Moo<Expression>, Moo<Expression>),
271

            
272
    #[compatible(JsonInput)]
273
    Subset(Metadata, Moo<Expression>, Moo<Expression>),
274

            
275
    #[compatible(JsonInput)]
276
    SubsetEq(Metadata, Moo<Expression>, Moo<Expression>),
277

            
278
    #[compatible(JsonInput, SMT)]
279
    Eq(Metadata, Moo<Expression>, Moo<Expression>),
280

            
281
    #[compatible(JsonInput, SMT)]
282
    Neq(Metadata, Moo<Expression>, Moo<Expression>),
283

            
284
    #[compatible(JsonInput, SMT)]
285
    Geq(Metadata, Moo<Expression>, Moo<Expression>),
286

            
287
    #[compatible(JsonInput, SMT)]
288
    Leq(Metadata, Moo<Expression>, Moo<Expression>),
289

            
290
    #[compatible(JsonInput, SMT)]
291
    Gt(Metadata, Moo<Expression>, Moo<Expression>),
292

            
293
    #[compatible(JsonInput, SMT)]
294
    Lt(Metadata, Moo<Expression>, Moo<Expression>),
295

            
296
    #[compatible(JsonInput)]
297
    Pred(Metadata, Moo<Expression>),
298

            
299
    #[compatible(JsonInput)]
300
    Succ(Metadata, Moo<Expression>),
301

            
302
    /// `s subsequence t` tests whether the list of values taken by s occurs in the same order
303
    /// in the list of values taken by t
304
    #[compatible(JsonInput)]
305
    Subsequence(Metadata, Moo<Expression>, Moo<Expression>),
306

            
307
    /// `s substring t` tests whether the list of values taken by s occurs in the same order
308
    /// and contiguously in the list of values taken by t
309
    #[compatible(JsonInput)]
310
    Substring(Metadata, Moo<Expression>, Moo<Expression>),
311

            
312
    /// `catchUndef(e, d)`: `e` where `e` is defined, `d` where it is not.
313
    ///
314
    /// Definedness is only known once the bubble rules have run, so this survives until then and
315
    /// is lowered against the bubble condition the inner expression produces.
316
    #[compatible(JsonInput)]
317
    CatchUndef(Metadata, Moo<Expression>, Moo<Expression>),
318

            
319
    /// Division after preventing division by zero, usually with a bubble
320
    #[compatible(SMT)]
321
    SafeDiv(Metadata, Moo<Expression>, Moo<Expression>),
322

            
323
    /// Division with a possibly undefined value (division by 0)
324
    #[compatible(JsonInput)]
325
    UnsafeDiv(Metadata, Moo<Expression>, Moo<Expression>),
326

            
327
    /// Modulo after preventing mod 0, usually with a bubble
328
    #[compatible(SMT)]
329
    SafeMod(Metadata, Moo<Expression>, Moo<Expression>),
330

            
331
    /// Modulo with a possibly undefined value (mod 0)
332
    #[compatible(JsonInput)]
333
    UnsafeMod(Metadata, Moo<Expression>, Moo<Expression>),
334

            
335
    /// Negation: `-x`
336
    #[compatible(JsonInput, SMT)]
337
    Neg(Metadata, Moo<Expression>),
338

            
339
    /// Factorial: `x!` or 'factorial(x)`
340
    #[compatible(JsonInput)]
341
    Factorial(Metadata, Moo<Expression>),
342

            
343
    /// Set of domain values function is defined for
344
    #[compatible(JsonInput)]
345
    Defined(Metadata, Moo<Expression>),
346

            
347
    /// Set of codomain values function is defined for
348
    #[compatible(JsonInput)]
349
    Range(Metadata, Moo<Expression>),
350

            
351
    #[compatible(JsonInput)]
352
    ToSet(Metadata, Moo<Expression>),
353

            
354
    #[compatible(JsonInput)]
355
    ToMSet(Metadata, Moo<Expression>),
356

            
357
    #[compatible(JsonInput)]
358
    ToRelation(Metadata, Moo<Expression>),
359

            
360
    /// Unsafe power`x**y` (possibly undefined)
361
    ///
362
    /// Defined when (X!=0 \\/ Y!=0) /\ Y>=0
363
    #[compatible(JsonInput)]
364
    UnsafePow(Metadata, Moo<Expression>, Moo<Expression>),
365

            
366
    /// `UnsafePow` after preventing undefinedness
367
    SafePow(Metadata, Moo<Expression>, Moo<Expression>),
368

            
369
    /// Flatten matrix operator
370
    /// `flatten(M)` or `flatten(n, M)`
371
    /// where M is a matrix and n is an optional integer argument indicating depth of flattening
372
    Flatten(Metadata, Option<Moo<Expression>>, Moo<Expression>),
373

            
374
    /// An attribute predicate used as a constraint, e.g. `reflexive(r)` or `size(s, 3)`.
375
    /// Lifted into the target's declaration domain attributes when possible (see
376
    /// `passes::attribute_as_constraint`); expanded in place to the equivalent formula otherwise.
377
    AttributeAsConstraint(Metadata, Moo<Expression>, Ustr, Option<Moo<Expression>>),
378

            
379
    /// `allDifferent(<vec_expr>)`
380
    #[compatible(JsonInput)]
381
    AllDiff(Metadata, Moo<Expression>),
382

            
383
    /// Z3's native `distinct` over the elements of `<vec_expr>`.
384
    ///
385
    /// This is emitted for the SMT backend only, and never appears in a model bound for any other
386
    /// solver. It exists so that "hand `allDifferent` to Z3 as `distinct`" and "encode
387
    /// `allDifferent` explicitly" are two rules competing at the same choice site, which is what
388
    /// lets the heuristics pick between them -- and what records the choice in the model, so it is
389
    /// not asked again every time the expression is visited.
390
    #[compatible(SMT)]
391
    SmtDistinct(Metadata, Moo<Expression>),
392

            
393
    /// `allDifferentExcept(<matrix>, <except>)`
394
    #[compatible(JsonInput)]
395
    AllDifferentExcept(Metadata, Moo<Expression>, Moo<Expression>),
396

            
397
    /// Select a scalar matrix entry, returning the index itself outside the index domain.
398
    ElementId(Metadata, Moo<Expression>, Moo<Expression>),
399

            
400
    /// Internal inverse lookup used to locate a function argument among its domain values.
401
    #[polyquine_skip]
402
    IndexOf(Metadata, Moo<Expression>, Moo<Expression>),
403

            
404
    /// `table(sequence(x1, x2, ...), {sequence(r11, r12, ...), sequence(r21, r22, ...), ...})`
405
    ///
406
    /// Represents a positive table constraint: the input sequence must match one of the
407
    /// allowed rows.
408
    #[compatible(JsonInput)]
409
    Table(Metadata, Moo<Expression>, Moo<Expression>),
410

            
411
    /// `negativeTable(sequence(x1, x2, ...), rows)` forbids the set of sequence rows.
412
    ///
413
    /// Represents a negative table constraint: the input sequence must NOT match any of the
414
    /// forbidden rows.
415
    #[compatible(JsonInput)]
416
    NegativeTable(Metadata, Moo<Expression>, Moo<Expression>),
417

            
418
    /// `shortTable(sequence(x1, x2, ...), {{(position, value), ...}, ...})` uses one-based positions.
419
    /// Omitted positions are wildcards; each sparse row and the relation itself are sets.
420
    ShortTable(Metadata, Moo<Expression>, Moo<Expression>),
421

            
422
    /// Minion table relation with scalar inputs and numeric rows; the flag forbids matching rows.
423
    #[polyquine_skip]
424
    FlatTable(Metadata, Vec<Atom>, Vec<Vec<i32>>, bool),
425

            
426
    /// Minion sparse table with zero-based positions and numeric values; omitted inputs are wildcards.
427
    #[polyquine_skip]
428
    FlatShortTable(Metadata, Vec<Atom>, Vec<Vec<(usize, i32)>>),
429

            
430
    /// `atleast(vars, counts, values)`
431
    ///
432
    /// For each `values[i]`, requires at least `counts[i]` occurrences in `vars`.
433
    #[compatible(JsonInput)]
434
    AtLeast(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),
435

            
436
    /// `atmost(vars, counts, values)`
437
    ///
438
    /// For each `values[i]`, requires at most `counts[i]` occurrences in `vars`.
439
    #[compatible(JsonInput)]
440
    AtMost(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),
441

            
442
    /// `gcc(vars, values, counts)`
443
    ///
444
    /// Global cardinality constraint. For each `values[i]`, requires exactly `counts[i]`
445
    /// occurrences in `vars`.
446
    #[compatible(JsonInput)]
447
    Gcc(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),
448

            
449
    /// Minion `gccweak(vars, values, counts)` — weaker propagation variant of `gcc`.
450
    #[compatible(Minion)]
451
    GccWeak(Metadata, Moo<Expression>, Moo<Expression>, Moo<Expression>),
452

            
453
    /// Binary subtraction operator
454
    ///
455
    /// This is a parser-level construct, and is immediately normalised to `Sum([a,-b])`.
456
    /// TODO: make this compatible with Set Difference calculations - need to change return type and domain for this expression and write a set comprehension rule.
457
    /// have already edited minus_to_sum to prevent this from applying to sets
458
    #[compatible(JsonInput)]
459
    Minus(Metadata, Moo<Expression>, Moo<Expression>),
460

            
461
    /// Partition Operator: test if a list of elements are not all contained in one part of the partition
462
    /// First Expr Arg is a list of elements
463
    /// Second Expr Arg is the partition
464
    #[compatible(JsonInput)]
465
    Apart(Metadata, Moo<Expression>, Moo<Expression>),
466

            
467
    /// Partition Operator: union of all parts of a partition
468
    /// Expr Arg is a partition
469
    #[compatible(JsonInput)]
470
    Participants(Metadata, Moo<Expression>),
471

            
472
    /// Partition Operator: part of partition that contains specified element
473
    /// First Expr Arg is an element that should be contained
474
    /// Second Expr Arg is the partition that should contain that element
475
    #[compatible(JsonInput)]
476
    Party(Metadata, Moo<Expression>, Moo<Expression>),
477

            
478
    /// Partition Operator: partition to its set of parts
479
    /// Expr Arg is the partition from which the parts come from
480
    #[compatible(JsonInput)]
481
    Parts(Metadata, Moo<Expression>),
482

            
483
    /// Partition Operator: test if a list of elements are all in the same part of the partition
484
    /// First Expr Arg is the list of elements to test with
485
    /// Second Expr Arg is the partition to test on
486
    #[compatible(JsonInput)]
487
    Together(Metadata, Moo<Expression>, Moo<Expression>),
488

            
489
    /// Ensures that x=|y| i.e. x is the absolute value of y.
490
    ///
491
    /// Low-level Minion constraint.
492
    ///
493
    /// # See also
494
    ///
495
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#abs)
496
    #[compatible(Minion)]
497
    FlatAbsEq(Metadata, Moo<Atom>, Moo<Atom>),
498

            
499
    /// Ensures that `alldiff([a,b,...])`.
500
    ///
501
    /// Low-level Minion constraint.
502
    ///
503
    /// # See also
504
    ///
505
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#alldiff)
506
    #[compatible(Minion)]
507
    FlatAllDiff(Metadata, Vec<Atom>),
508

            
509
    /// Ensures that `result = min(vars)`.
510
    ///
511
    /// Low-level Minion constraint. Prefer this over expanding [`Expression::Min`] into
512
    /// leq/or/eq constraints when targeting Minion.
513
    ///
514
    /// # See also
515
    ///
516
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#min)
517
    #[compatible(Minion)]
518
    FlatMinEq(Metadata, Vec<Atom>, Atom),
519

            
520
    /// Ensures that sum(vec) >= x.
521
    ///
522
    /// Low-level Minion constraint.
523
    ///
524
    /// # See also
525
    ///
526
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#sumgeq)
527
    #[compatible(Minion)]
528
    FlatSumGeq(Metadata, Vec<Atom>, Atom),
529

            
530
    /// Ensures that sum(vec) <= x.
531
    ///
532
    /// Low-level Minion constraint.
533
    ///
534
    /// # See also
535
    ///
536
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#sumleq)
537
    #[compatible(Minion)]
538
    FlatSumLeq(Metadata, Vec<Atom>, Atom),
539

            
540
    /// `ineq(x,y,k)` ensures that x <= y + k.
541
    ///
542
    /// Low-level Minion constraint.
543
    ///
544
    /// # See also
545
    ///
546
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#ineq)
547
    #[compatible(Minion)]
548
    FlatIneq(Metadata, Moo<Atom>, Moo<Atom>, Box<Literal>),
549

            
550
    /// `w-literal(x,k)` ensures that x == k, where x is a variable and k a constant.
551
    ///
552
    /// Low-level Minion constraint.
553
    ///
554
    /// This is a low-level Minion constraint and you should probably use Eq instead. The main use
555
    /// of w-literal is to convert boolean variables to constraints so that they can be used inside
556
    /// watched-and and watched-or.
557
    ///
558
    /// # See also
559
    ///
560
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#minuseq)
561
    /// + `rules::minion::boolean_literal_to_wliteral`.
562
    #[compatible(Minion)]
563
    #[polyquine_skip]
564
    FlatWatchedLiteral(Metadata, Reference, Literal),
565

            
566
    /// `weightedsumleq(cs,xs,total)` ensures that cs.xs <= total, where cs.xs is the scalar dot
567
    /// product of cs and xs.
568
    ///
569
    /// Low-level Minion constraint.
570
    ///
571
    /// Represents a weighted sum of the form `ax + by + cz + ...`
572
    ///
573
    /// # See also
574
    ///
575
    /// + [Minion
576
    /// documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#weightedsumleq)
577
    FlatWeightedSumLeq(Metadata, Vec<Literal>, Vec<Atom>, Moo<Atom>),
578

            
579
    /// `weightedsumgeq(cs,xs,total)` ensures that cs.xs >= total, where cs.xs is the scalar dot
580
    /// product of cs and xs.
581
    ///
582
    /// Low-level Minion constraint.
583
    ///
584
    /// Represents a weighted sum of the form `ax + by + cz + ...`
585
    ///
586
    /// # See also
587
    ///
588
    /// + [Minion
589
    /// documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#weightedsumleq)
590
    FlatWeightedSumGeq(Metadata, Vec<Literal>, Vec<Atom>, Moo<Atom>),
591

            
592
    /// Ensures that x =-y, where x and y are atoms.
593
    ///
594
    /// Low-level Minion constraint.
595
    ///
596
    /// # See also
597
    ///
598
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#minuseq)
599
    #[compatible(Minion)]
600
    FlatMinusEq(Metadata, Moo<Atom>, Moo<Atom>),
601

            
602
    /// Ensures that x*y=z.
603
    ///
604
    /// Low-level Minion constraint.
605
    ///
606
    /// # See also
607
    ///
608
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#product)
609
    #[compatible(Minion)]
610
    FlatProductEq(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),
611

            
612
    /// Ensures that floor(x/y)=z. Always true when y=0.
613
    ///
614
    /// Low-level Minion constraint.
615
    ///
616
    /// # See also
617
    ///
618
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#div_undefzero)
619
    #[compatible(Minion)]
620
    MinionDivEqUndefZero(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),
621

            
622
    /// Ensures that x%y=z. Always true when y=0.
623
    ///
624
    /// Low-level Minion constraint.
625
    ///
626
    /// # See also
627
    ///
628
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#mod_undefzero)
629
    #[compatible(Minion)]
630
    MinionModuloEqUndefZero(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),
631

            
632
    /// Ensures that `x**y = z`.
633
    ///
634
    /// Low-level Minion constraint.
635
    ///
636
    /// This constraint is false when `y<0` except for `1**y=1` and `(-1)**y=z` (where z is 1 if y
637
    /// is odd and z is -1 if y is even).
638
    ///
639
    /// # See also
640
    ///
641
    /// + [Github comment about `pow` semantics](https://github.com/minion/minion/issues/40#issuecomment-2595914891)
642
    /// + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#pow)
643
    MinionPow(Metadata, Moo<Atom>, Moo<Atom>, Moo<Atom>),
644

            
645
    /// `reify(constraint,r)` ensures that r=1 iff `constraint` is satisfied, where r is a 0/1
646
    /// variable.
647
    ///
648
    /// Low-level Minion constraint.
649
    ///
650
    /// # See also
651
    ///
652
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#reify)
653
    #[compatible(Minion)]
654
    MinionReify(Metadata, Moo<Expression>, Atom),
655

            
656
    /// `reifyimply(constraint,r)` ensures that `r->constraint`, where r is a 0/1 variable.
657
    /// variable.
658
    ///
659
    /// Low-level Minion constraint.
660
    ///
661
    /// # See also
662
    ///
663
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#reifyimply)
664
    #[compatible(Minion)]
665
    MinionReifyImply(Metadata, Moo<Expression>, Atom),
666

            
667
    /// `w-inintervalset(x, [a1,a2, b1,b2, … ])` ensures that the value of x belongs to one of the
668
    /// intervals {a1,…,a2}, {b1,…,b2} etc.
669
    ///
670
    /// The list of intervals must be given in numerical order.
671
    ///
672
    /// Low-level Minion constraint.
673
    ///
674
    /// # See also
675
    ///>
676
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#w-inintervalset)
677
    #[compatible(Minion)]
678
    MinionWInIntervalSet(Metadata, Atom, Vec<i32>),
679

            
680
    /// `w-inset(x, [v1, v2, … ])` ensures that the value of `x` is one of the explicitly given values `v1`, `v2`, etc.
681
    ///
682
    /// This constraint enforces membership in a specific set of discrete values rather than intervals.
683
    ///
684
    /// The list of values must be given in numerical order.
685
    ///
686
    /// Low-level Minion constraint.
687
    ///
688
    /// # See also
689
    ///
690
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#w-inset)
691
    #[compatible(Minion)]
692
    MinionWInSet(Metadata, Atom, Vec<i32>),
693

            
694
    /// `element_one(vec, i, e)` specifies that `vec[i] = e`. This implies that i is
695
    /// in the range `[1..len(vec)]`.
696
    ///
697
    /// Low-level Minion constraint.
698
    ///
699
    /// # See also
700
    ///
701
    ///  + [Minion documentation](https://minion-solver.readthedocs.io/en/stable/usage/constraints.html#element_one)
702
    #[compatible(Minion)]
703
    MinionElementOne(Metadata, Vec<Atom>, Moo<Atom>, Moo<Atom>),
704

            
705
    /// Declaration of an auxiliary variable.
706
    ///
707
    /// As with Savile Row, we semantically distinguish this from `Eq`.
708
    #[compatible(Minion)]
709
    #[polyquine_skip]
710
    AuxDeclaration(Metadata, Reference, Moo<Expression>),
711

            
712
    /// This expression is for encoding ints for the SAT solver, it stores the encoding type, the vector of booleans and the min/max for the int.
713
    #[compatible(SAT)]
714
    SATInt(Metadata, SATIntEncoding, Moo<Expression>, (i32, i32)),
715
    /// Retain an optimisation objective until its actual-value SAT view is ready.
716
    #[compatible(SAT)]
717
    SatObjective(Metadata, bool, Moo<Expression>),
718

            
719
    /// Addition over a pair of expressions (i.e. a + b) rather than a vec-expr like Expression::Sum.
720
    /// This is for compatibility with backends that do not support addition over vectors.
721
    #[compatible(SMT)]
722
    PairwiseSum(Metadata, Moo<Expression>, Moo<Expression>),
723

            
724
    /// Multiplication over a pair of expressions (i.e. a * b) rather than a vec-expr like Expression::Product.
725
    /// This is for compatibility with backends that do not support multiplication over vectors.
726
    #[compatible(SMT)]
727
    PairwiseProduct(Metadata, Moo<Expression>, Moo<Expression>),
728

            
729
    #[compatible(JsonInput)]
730
    Image(Metadata, Moo<Expression>, Moo<Expression>),
731

            
732
    #[compatible(JsonInput)]
733
    ImageSet(Metadata, Moo<Expression>, Moo<Expression>),
734

            
735
    #[compatible(JsonInput)]
736
    PreImage(Metadata, Moo<Expression>, Moo<Expression>),
737

            
738
    #[compatible(JsonInput)]
739
    Inverse(Metadata, Moo<Expression>, Moo<Expression>),
740

            
741
    /// `permInverse(p)`: the inverse of permutation `p`, as a new permutation value. Not to be
742
    /// confused with [`Expression::Inverse`], which is a boolean predicate over a pair of
743
    /// permutations, not a value-returning operator.
744
    #[compatible(JsonInput)]
745
    PermInverse(Metadata, Moo<Expression>),
746

            
747
    /// `compose(g, h)`: the permutation obtained by applying `h` then `g`, as a new permutation
748
    /// value (`image(compose(g, h), i) = image(g, image(h, i))`).
749
    #[compatible(JsonInput)]
750
    Compose(Metadata, Moo<Expression>, Moo<Expression>),
751

            
752
    #[compatible(JsonInput)]
753
    Restrict(Metadata, Moo<Expression>, Moo<Expression>),
754

            
755
    /// Lexicographical < between two matrices.
756
    ///
757
    /// A <lex B iff: A[i] < B[i] for some i /\ (A[j] > B[j] for some j -> i < j)
758
    /// I.e. A must be less than B at some index i, and if it is greater than B at another index j,
759
    /// then j comes after i.
760
    /// I.e. A must be greater than B at the first index where they differ.
761
    ///
762
    /// E.g. [1, 1] <lex [2, 1] and [1, 1] <lex [1, 2]
763
    LexLt(Metadata, Moo<Expression>, Moo<Expression>),
764

            
765
    /// Lexicographical <= between two matrices
766
    LexLeq(Metadata, Moo<Expression>, Moo<Expression>),
767

            
768
    /// Lexicographical > between two matrices
769
    /// This is a parser-level construct, and is immediately normalised to LexLt(b, a)
770
    LexGt(Metadata, Moo<Expression>, Moo<Expression>),
771

            
772
    /// Lexicographical >= between two matrices
773
    /// This is a parser-level construct, and is immediately normalised to LexLeq(b, a)
774
    LexGeq(Metadata, Moo<Expression>, Moo<Expression>),
775

            
776
    /// Low-level minion constraint. See Expression::LexLt
777
    FlatLexLt(Metadata, Vec<Atom>, Vec<Atom>),
778

            
779
    /// Low-level minion constraint. See Expression::LexLeq
780
    FlatLexLeq(Metadata, Vec<Atom>, Vec<Atom>),
781

            
782
    /// Alters the shape of relations by projection
783
    #[compatible(JsonInput)]
784
    RelationProj(Metadata, Moo<Expression>, Vec<Option<Expression>>),
785

            
786
    /// Cardinality of a collection type
787
    #[compatible(JsonInput)]
788
    Card(Metadata, Moo<Expression>),
789
}
790

            
791
impl Expression {
792
    /// Returns the possible values of the expression, recursing to leaf expressions.
793
    ///
794
    /// Cached in this node's own `Metadata`: `domain_of_uncached` recomputes recursively from
795
    /// scratch with no memoisation of its own, so repeatedly calling `domain_of` on the same
796
    /// subtree (as rules that check "is this operand scalar/abstract" tend to, once per rule
797
    /// attempt) is quadratic in the worst case without a cache. The cache is invalidated when
798
    /// this expression or a descendant changes.
799
487436465
    pub fn domain_of(&self) -> Option<DomainPtr> {
800
487436465
        self.meta_ref().domain_or_init(|| self.domain_of_uncached())
801
487436465
    }
802

            
803
    /// Bypasses the cache in `domain_of`. Needed by callers that read an expression stored
804
    /// *inside a declaration* (e.g. `Declaration::domain`, for `ValueLetting`/`QuantifiedExpr`):
805
    /// such expressions live outside the tree the rewrite engine walks to invalidate
806
    /// `Metadata::domain`, the same "reference embedded outside the standard rewrite tree" gap
807
    /// documented for `Reference::get_repr_as` and comprehension `ExpressionGenerator` sources.
808
319861016
    pub(crate) fn domain_of_uncached(&self) -> Option<DomainPtr> {
809
319861016
        match self {
810
            Expression::Union(_, a, b) => {
811
4961
                let lhs = a.domain_of()?;
812
4961
                let rhs = b.domain_of()?;
813
4961
                set_operation_domain(a, b, SetOperation::Union)
814
70
                    .or_else(|| mset_union_result_domain(a, b))
815
                    .or_else(|| lhs.union(&rhs).ok())
816
            }
817
5942
            Expression::Intersect(_, a, b) => set_operation_domain(a, b, SetOperation::Intersect)
818
                .or_else(|| a.domain_of()?.intersect(&b.domain_of()?).ok()),
819
4300
            Expression::Difference(_, a, b) => set_operation_domain(a, b, SetOperation::Difference),
820
8836
            Expression::In(_, _, _) => Some(Domain::bool()),
821
            Expression::Supset(_, _, _) => Some(Domain::bool()),
822
            Expression::SupsetEq(_, _, _) => Some(Domain::bool()),
823
            Expression::Subset(_, _, _) => Some(Domain::bool()),
824
12
            Expression::SubsetEq(_, _, _) => Some(Domain::bool()),
825
1360269
            Expression::AbstractLiteral(_, abslit) => abslit.domain_of(),
826
            Expression::DominanceRelation(_, _) => Some(Domain::bool()),
827
            Expression::FromSolution(_, expr) => Some(expr.domain_of()),
828
904
            Expression::Metavar(_, _) => None,
829
4942
            Expression::Comprehension(_, comprehension) => comprehension.domain_of(),
830
            Expression::RecordField(_, rec, field_name) => {
831
289333
                let rec_ents = rec.domain_of()?.as_record()?;
832
                for ent in rec_ents {
833
                    if ent.name.eq(field_name) {
834
                        return Some(ent.value);
835
                    }
836
                }
837
                None
838
            }
839
            Expression::UnsafeIndex(_, matrix, index) | Expression::SafeIndex(_, matrix, index) => {
840
34323780
                let dom = matrix.domain_of()?;
841
34323780
                let resolved_dom = dom.resolve().ok().map(Domain::Ground);
842
34323780
                if dom.as_matrix().is_some()
843
263320
                    || resolved_dom
844
263320
                        .as_ref()
845
263320
                        .is_some_and(|dom| dom.as_matrix().is_some())
846
                {
847
                    // A matrix domain may be written flat -- `Matrix(int, [d1, d2])` -- or nested
848
                    // -- `Matrix(Matrix(int, [d2]), [d1])` -- and both mean the same thing. Each
849
                    // level consumes as many indices as it declares, so peel a level at a time
850
                    // until the indices run out rather than assuming one level covers them all.
851
34061359
                    let mut current = dom;
852
34061359
                    let mut remaining = index.len();
853
68122718
                    while remaining > 0 {
854
34061359
                        let resolved = current.resolve().ok().map(Domain::Ground);
855
34061359
                        let Some((elem_domain, idx_domains)) = current
856
34061359
                            .as_matrix()
857
899
                            .or_else(|| resolved.as_ref()?.as_matrix())
858
                        else {
859
                            break;
860
                        };
861
                        // Fewer indices than this level declares is a partial index: what is left
862
                        // is a matrix over the dimensions that were not given.
863
34061359
                        if idx_domains.len() > remaining {
864
                            return Some(Domain::matrix(
865
                                elem_domain,
866
                                idx_domains[remaining..].to_vec(),
867
                            ));
868
34061359
                        }
869
34061359
                        remaining -= idx_domains.len();
870
34061359
                        current = elem_domain;
871
                    }
872
34061359
                    return Some(current);
873
262421
                }
874

            
875
                // Indexing a tuple picks one component, so the domain is that component's --
876
                // known only when the position is a literal, as tuple components need not share
877
                // a domain.
878
                if let Some(components) =
879
262421
                    dom.as_tuple().or_else(|| resolved_dom.as_ref()?.as_tuple())
880
                {
881
                    let Expression::Atomic(_, Atom::Literal(Literal::Int(index))) =
882
262421
                        index.first()?
883
                    else {
884
                        return None;
885
                    };
886
262421
                    let index: usize = (*index - 1).try_into().ok()?;
887
262421
                    return components.get(index).cloned();
888
                }
889

            
890
                if let Some(doms) = dom.as_variant().or(dom.as_record()).or_else(|| {
891
                    let resolved_dom = resolved_dom.as_ref()?;
892
                    resolved_dom.as_variant().or(resolved_dom.as_record())
893
                }) {
894
                    let index_expr = index.first()?;
895
                    return match index_expr {
896
                        Expression::Atomic(_, Atom::Reference(reference)) => {
897
                            for inner_dom in doms {
898
                                if *reference.name() == inner_dom.name {
899
                                    return Some(inner_dom.value);
900
                                }
901
                            }
902
                            None
903
                        }
904
                        Expression::Atomic(_, Atom::Literal(Literal::Int(index))) => {
905
                            let index: usize = (*index - 1).try_into().ok()?;
906
                            doms.get(index).map(|inner_dom| inner_dom.value.clone())
907
                        }
908
                        _ => None,
909
                    };
910
                }
911

            
912
                bug!(
913
                    "subject of an index operation should support indexing, but got {matrix}: {dom}"
914
                )
915
            }
916
            Expression::UnsafeSlice(_, matrix, indices)
917
            | Expression::SafeSlice(_, matrix, indices) => {
918
694579
                let sliced_dimension = indices.iter().position(Option::is_none);
919

            
920
694579
                let dom = matrix.domain_of()?;
921
694579
                let Some((elem_domain, index_domains)) = dom.as_matrix() else {
922
                    bug!("subject of an index operation should be a matrix");
923
                };
924

            
925
694579
                match sliced_dimension {
926
694579
                    Some(dimension) => Some(Domain::matrix(
927
694579
                        elem_domain,
928
694579
                        vec![index_domains[dimension].clone()],
929
694579
                    )),
930

            
931
                    // same as index
932
                    None => Some(elem_domain),
933
                }
934
            }
935
            Expression::InDomain(_, _, _) => Some(Domain::bool()),
936
188403807
            Expression::Atomic(_, atom) => Some(atom.domain_of()),
937
            Expression::TypeAnnotation(_, expr, _) => expr.domain_of(),
938
2
            Expression::DomainAnnotation(_, _, domain) => Some(domain.clone()),
939
15111542
            Expression::Sum(_, e) => sum_domain_of_child(e).or_else(|| {
940
                // Fall back when corner products of bounds overflow i32.
941
14868857
                bounded_i32_domain_for_matrix_literal_monotonic(e, i32::checked_add)
942
14868857
            }),
943
            Expression::Product(_, e) => {
944
                // Grocery-style products (e.g. four int(0..711) factors) overflow i32;
945
                // return None so callers can omit a precise product domain rather than panic.
946
4325588
                bounded_i32_domain_for_matrix_literal_monotonic(e, i32::checked_mul)
947
            }
948
            Expression::Min(_, e) => {
949
279067
                if empty_matrix_integer_element_domain(e).is_some() {
950
13920
                    return Some(Domain::empty(ReturnType::Int));
951
265147
                }
952
1152228
                bounded_i32_domain_for_matrix_literal_monotonic(e, |x, y| {
953
1152228
                    Some(if x < y { x } else { y })
954
1152228
                })
955
3190
                .or_else(|| matrix_element_domain(e))
956
            }
957
            Expression::Max(_, e) => {
958
176083
                if empty_matrix_integer_element_domain(e).is_some() {
959
7395
                    return Some(Domain::empty(ReturnType::Int));
960
168688
                }
961
788360
                bounded_i32_domain_for_matrix_literal_monotonic(e, |x, y| {
962
788336
                    Some(if x > y { x } else { y })
963
788336
                })
964
1039
                .or_else(|| matrix_element_domain(e))
965
            }
966
            Expression::Pred(_, operand) | Expression::Succ(_, operand) => {
967
8
                let domain = operand.domain_of()?.resolve().ok()?;
968
8
                if !matches!(domain.as_ref(), GroundDomain::EnumeratedType(_, _)) {
969
                    return None;
970
8
                }
971
8
                let values = domain
972
8
                    .values()
973
8
                    .ok()?
974
8
                    .filter_map(|value| {
975
8
                        let Literal::EnumVariant(value) = value else {
976
                            return None;
977
                        };
978
8
                        let neighbour = if matches!(self, Expression::Pred(_, _)) {
979
                            value.pred()
980
                        } else {
981
8
                            value.succ()
982
                        };
983
8
                        neighbour.map(Literal::EnumVariant)
984
8
                    })
985
                    .collect::<Vec<_>>();
986
8
                if values.is_empty() {
987
8
                    Some(Domain::empty(operand.return_type()))
988
                } else {
989
                    GroundDomain::from_literal_vec(&values)
990
                        .ok()
991
                        .map(DomainPtr::from)
992
                }
993
            }
994
3849933
            Expression::UnsafeDiv(_, a, b) => division_domain(a, b, false),
995
            // Either operand's value can survive, so the domain must cover both.
996
            Expression::CatchUndef(_, a, b) => {
997
411394
                let inner = a.domain_of()?;
998
411394
                let default = b.domain_of()?;
999
411394
                inner.union(&default).ok()
            }
1647585
            Expression::SafeDiv(_, a, b) => division_domain(a, b, true),
5481456
            Expression::UnsafeMod(_, a, b) => modulo_domain(a, b, false),
4411546
            Expression::SafeMod(_, a, b) => modulo_domain(a, b, true),
            Expression::SafePow(_, a, b) | Expression::UnsafePow(_, a, b) => {
424733
                power_integer_domain(a, b)
            }
            Expression::Root(_, _) => None,
434681
            Expression::Bubble(_, inner, _) => inner.domain_of(),
            Expression::AuxDeclaration(_, _, _) => Some(Domain::bool()),
32025
            Expression::And(_, _) => Some(Domain::bool()),
21312
            Expression::Not(_, _) => Some(Domain::bool()),
22424
            Expression::Or(_, _) => Some(Domain::bool()),
69066
            Expression::Imply(_, _, _) => Some(Domain::bool()),
174
            Expression::Iff(_, _, _) => Some(Domain::bool()),
91658
            Expression::Eq(_, _, _) => Some(Domain::bool()),
1962
            Expression::Neq(_, _, _) => Some(Domain::bool()),
598
            Expression::Geq(_, _, _) => Some(Domain::bool()),
167831
            Expression::Leq(_, _, _) => Some(Domain::bool()),
2150
            Expression::Gt(_, _, _) => Some(Domain::bool()),
265
            Expression::Lt(_, _, _) => Some(Domain::bool()),
94
            Expression::Factorial(_, a) => factorial_domain(a),
            Expression::FlatAbsEq(_, _, _) => Some(Domain::bool()),
            Expression::FlatMinEq(_, _, _) => Some(Domain::bool()),
203
            Expression::FlatSumGeq(_, _, _) => Some(Domain::bool()),
29
            Expression::FlatSumLeq(_, _, _) => Some(Domain::bool()),
            Expression::MinionDivEqUndefZero(_, _, _, _) => Some(Domain::bool()),
            Expression::MinionModuloEqUndefZero(_, _, _, _) => Some(Domain::bool()),
82
            Expression::FlatIneq(_, _, _, _) => Some(Domain::bool()),
            Expression::Flatten(_, n, m) => {
9831
                if let Some(expr) = n {
                    if expr.return_type() == ReturnType::Int {
                        // TODO: handle flatten with depth argument
                        return None;
                    }
                } else {
                    // TODO: currently only works for matrices
9831
                    let dom = m.domain_of()?.resolve().ok()?;
9831
                    let (val_dom, idx_doms) = match dom.as_ref() {
9831
                        GroundDomain::Matrix(val, idx, _) => (val, idx),
                        _ => return None,
                    };
9831
                    let num_elems = matrix::num_elements(idx_doms).ok()? as i32;
9831
                    let new_index_domain = Domain::int(vec![Range::Bounded(1, num_elems)]);
9831
                    return Some(Domain::matrix(
9831
                        val_dom.clone().into(),
9831
                        vec![new_index_domain],
9831
                    ));
                }
                None
            }
1508
            Expression::AllDiff(_, _) => Some(Domain::bool()),
            Expression::SmtDistinct(_, _) => Some(Domain::bool()),
29
            Expression::AllDifferentExcept(_, _, _) => Some(Domain::bool()),
            Expression::ElementId(_, matrix, index) => {
435
                let lookup = Expression::UnsafeIndex(
435
                    Metadata::new(),
435
                    matrix.clone(),
435
                    vec![(**index).clone()],
435
                );
870
                let numeric = |domain: DomainPtr| {
870
                    if domain.is_bool() {
                        Some(Domain::int(vec![Range::Bounded(0, 1)]))
870
                    } else if domain.is_int() {
870
                        Some(domain)
                    } else {
                        None
                    }
870
                };
435
                if matches!(matrix.as_ref(), Expression::Atomic(_, Atom::Literal(Literal::AbstractLiteral(AbstractLiteral::Matrix(entries, _)))) if entries.is_empty())
435
                    || matrix
435
                        .unwrap_matrix_unchecked_ref()
435
                        .is_some_and(|(entries, _)| entries.is_empty())
                {
                    return numeric(index.domain_of()?);
435
                }
435
                numeric(lookup.domain_of()?)?
435
                    .union(&numeric(index.domain_of()?)?)
                    .ok()
            }
            Expression::IndexOf(_, matrix, value) => {
48256
                let dom = matrix.domain_of()?.resolve().ok()?;
48256
                let idx_doms = match dom.as_ref() {
48256
                    GroundDomain::Matrix(_, idx, _) => idx,
                    _ => return None,
                };
48256
                if let [idx_dom] = idx_doms.as_slice() {
48256
                    let index_domain = Domain::Ground(idx_dom.clone());
48256
                    if let Some(n) = matrix.list_len() {
                        if n > 0 {
                            return Some(Domain::int(vec![Range::Bounded(1, n as i32)]));
                        }
                        Some(Moo::new(index_domain))
                    } else {
48256
                        let matrix_is_literal = matches!(
48256
                            matrix.as_ref(),
                            Expression::Atomic(_, Atom::Literal(_))
                                | Expression::AbstractLiteral(_, _)
                        );
48256
                        if !matrix_is_literal || eval_constant(value.as_ref()).is_none() {
21344
                            value
21344
                                .domain_of()
21344
                                .and_then(|value_domain| index_domain.union(&value_domain).ok())
21344
                                .map(Moo::new)
                                .or_else(|| Some(Moo::new(index_domain)))
                        } else {
26912
                            Some(Moo::new(index_domain))
                        }
                    }
                } else {
                    let num_elems = matrix::num_elements(idx_doms).ok()? as i32;
                    Some(Domain::int(vec![Range::Bounded(1, num_elems)]))
                }
            }
            Expression::SatElement(_, _, _, _) | Expression::SatAllDifferentComparisons(_, _) => {
                Some(Domain::bool())
            }
            Expression::Table(_, _, _)
            | Expression::FlatTable(..)
            | Expression::FlatShortTable(..)
            | Expression::NegativeTable(_, _, _)
348
            | Expression::ShortTable(_, _, _) => Some(Domain::bool()),
            Expression::AtLeast(_, _, _, _) => Some(Domain::bool()),
174
            Expression::AtMost(_, _, _, _) => Some(Domain::bool()),
            Expression::Gcc(_, _, _, _) | Expression::GccWeak(_, _, _, _) => Some(Domain::bool()),
17018
            Expression::FlatWatchedLiteral(_, _, _) => Some(Domain::bool()),
            Expression::MinionReify(_, _, _) => Some(Domain::bool()),
            Expression::MinionReifyImply(_, _, _) => Some(Domain::bool()),
58
            Expression::MinionWInIntervalSet(_, _, _) => Some(Domain::bool()),
            Expression::MinionWInSet(_, _, _) => Some(Domain::bool()),
290
            Expression::MinionElementOne(_, _, _, _) => Some(Domain::bool()),
            Expression::Neg(_, x) => {
269169
                let dom = x.domain_of()?;
269169
                let mut ranges = dom.as_int()?;
269169
                ranges = ranges
269169
                    .into_iter()
269256
                    .map(|r| match r {
159993
                        Range::Single(x) => Range::Single(-x),
109263
                        Range::Bounded(x, y) => Range::Bounded(-y, -x),
                        Range::UnboundedR(i) => Range::UnboundedL(-i),
                        Range::UnboundedL(i) => Range::UnboundedR(-i),
                        Range::Unbounded => Range::Unbounded,
269256
                    })
                    .collect();
269169
                Some(Domain::int(ranges))
            }
            Expression::Minus(_, a, b) => {
1103988
                let a_resolved = a.domain_of()?.resolve().ok()?;
1099763
                let b_resolved = b.domain_of()?.resolve().ok()?;
1099763
                if matches!(
1099763
                    a_resolved.as_ref(),
                    GroundDomain::Int(_, _) | GroundDomain::Empty(ReturnType::Int)
1099763
                ) && matches!(
1099763
                    b_resolved.as_ref(),
                    GroundDomain::Int(_, _) | GroundDomain::Empty(ReturnType::Int)
                ) {
1099763
                    binary_integer_domain(a, b, i32::checked_sub)
                } else if matches!(a_resolved.as_ref(), GroundDomain::Set(_, _))
                    && matches!(b_resolved.as_ref(), GroundDomain::Set(_, _))
                {
                    set_operation_domain(a, b, SetOperation::Difference)
                } else {
                    None
                }
            }
            Expression::FlatAllDiff(_, _) => Some(Domain::bool()),
            Expression::FlatMinusEq(_, _, _) => Some(Domain::bool()),
            Expression::FlatProductEq(_, _, _, _) => Some(Domain::bool()),
            Expression::FlatWeightedSumLeq(_, _, _, _) => Some(Domain::bool()),
            Expression::FlatWeightedSumGeq(_, _, _, _) => Some(Domain::bool()),
304590
            Expression::Abs(_, a) => absolute_integer_domain(a),
            Expression::MinionPow(_, _, _, _) => Some(Domain::bool()),
35847883
            Expression::ToInt(_, _) => Some(Domain::int(vec![Range::Bounded(0, 1)])),
            Expression::SatObjective(..) => Some(Domain::bool()),
            Expression::SATInt(_, _, _, (low, high)) => {
19643407
                Some(Domain::int_ground(vec![Range::Bounded(*low, *high)]))
            }
788
            Expression::PairwiseSum(_, a, b) => binary_integer_domain(a, b, i32::checked_add),
788
            Expression::PairwiseProduct(_, a, b) => binary_integer_domain(a, b, i32::checked_mul),
2331
            Expression::Defined(_, function) => defined_domain(function),
3047
            Expression::Range(_, function) => range_domain(function),
507852
            Expression::Image(_, function, _) => get_function_codomain(function),
            Expression::PermInverse(_, perm) => perm.domain_of(),
            Expression::Compose(_, g, _h) => g.domain_of(),
87
            Expression::ImageSet(_, function, argument) => image_set_domain(function, argument)
                .or_else(|| {
                    get_function_codomain(function)
                        .map(|inner| Domain::set(SetAttr::new(Range::Bounded(0, 1)), inner))
                }),
89
            Expression::PreImage(_, function, image) => pre_image_domain(function, image),
            Expression::Restrict(_, function, new_domain) => {
32
                restricted_domain(function, new_domain)
            }
            Expression::Subsequence(_, _, _) => Some(Domain::bool()),
            Expression::Substring(_, _, _) => Some(Domain::bool()),
            Expression::AttributeAsConstraint(_, _, _, _) => Some(Domain::bool()),
            Expression::Inverse(..) => Some(Domain::bool()),
120
            Expression::LexLt(..) => Some(Domain::bool()),
7627
            Expression::LexLeq(..) => Some(Domain::bool()),
58
            Expression::LexGt(..) => Some(Domain::bool()),
174
            Expression::LexGeq(..) => Some(Domain::bool()),
            Expression::FlatLexLt(..) => Some(Domain::bool()),
            Expression::FlatLexLeq(..) => Some(Domain::bool()),
            Expression::Active(..) => Some(Domain::bool()),
            Expression::ToSet(_, other) => {
187
                if let Some((attrs, dom, codom)) = other.domain_of()?.as_function() {
8
                    Some(bounded_set(
8
                        function_size(&attrs, &dom, &codom),
8
                        Domain::tuple(vec![dom, codom]),
8
                    ))
179
                } else if let Some((_, doms)) = other.domain_of()?.as_relation() {
                    let size = collection_size(&other.domain_of()?)?;
                    Some(bounded_set(size, Domain::tuple(doms)))
179
                } else if let Some((attrs, dom)) = other.domain_of()?.as_mset() {
170
                    let size = mset_size(&attrs, &dom);
170
                    let occurrence = SizeBounds::from_size(&attrs.occurrence);
170
                    if size.range().is_none() || occurrence.range().is_none() {
5
                        return Some(Domain::empty(ReturnType::Set(Box::new(dom.return_type()))));
165
                    }
165
                    Some(bounded_set(distinct_size(size, occurrence), dom))
9
                } else if let Some((dom, dimensions)) = other.domain_of()?.as_matrix() {
                    // toSet consumes a list; higher-rank matrices need explicit flattening.
9
                    if dimensions.len() != 1 {
                        return None;
9
                    }
9
                    let size = collection_size(&other.domain_of()?)?;
9
                    Some(bounded_set(
9
                        distinct_size(size, SizeBounds::new(1, None)),
9
                        dom,
9
                    ))
                } else {
                    bug!(
                        "Domain of {self} needed to be a function, relation, mset, or matrix for ToSet"
                    )
                }
            }
            Expression::ToMSet(_, other) => {
                if let Some((attrs, dom, codom)) = other.domain_of()?.as_function() {
                    let set_attrs = MSetAttr {
                        size: function_size(&attrs, &dom, &codom).range()?.into(),
                        occurrence: Range::Single(IntVal::Const(1)),
                        representation: None,
                    };
                    Some(Domain::mset(set_attrs, Domain::tuple(vec![dom, codom])))
                } else if let Some((attrs, doms)) = other.domain_of()?.as_relation() {
                    let set_attrs = MSetAttr {
                        size: attrs.size,
                        occurrence: Range::Single(IntVal::Const(1)),
                        representation: None,
                    };
                    Some(Domain::mset(set_attrs, Domain::tuple(doms)))
                } else if let Some((attrs, dom)) = other.domain_of()?.as_set() {
                    let set_attrs = MSetAttr {
                        size: attrs.size,
                        occurrence: Range::Single(IntVal::Const(1)),
                        representation: None,
                    };
                    Some(Domain::mset(set_attrs, dom))
                } else {
                    bug!("Domain of {self} needed to be a function, relation, or set for ToMSet")
                }
            }
            Expression::ToRelation(_, function) => {
29
                let (attrs, domain, codomain) = function.domain_of()?.as_function()?;
                // Function attributes apply to the relation
                let rel_attrs = RelAttr {
29
                    size: function_size(&attrs, &domain, &codomain).range()?,
29
                    binary: vec![],
                    // The function's layout does not say how its relation view is laid out.
29
                    representation: None,
                };
29
                Some(Domain::relation(rel_attrs, vec![domain, codomain]))
            }
            Expression::RelationProj(_, relation, projections) => {
4
                let (_, domains) = relation.domain_of()?.as_relation()?;
4
                let new_doms = domains
4
                    .iter()
4
                    .zip(projections.iter())
12
                    .filter_map(|(domain, included)| {
12
                        if included.is_none() {
                            // The domains corresponding to projections which are None remain in the relation
8
                            Some(domain.clone())
                        } else {
4
                            None
                        }
12
                    })
                    .collect();
4
                Some(Domain::relation(RelAttr::<IntVal>::default(), new_doms))
            }
            Expression::Apart(_, _, _) => Some(Domain::bool()),
            Expression::Together(_, _, _) => Some(Domain::bool()),
            Expression::Participants(_, p) => {
                // Every single element of the domain _must_ be in the set, so fixed size on that.
66
                let (attr, inner) = p.domain_of()?.as_partition()?;
66
                let len = inner.length_signed().ok()?;
66
                let p_parts = attr.resolve().ok()?.num_parts;
66
                let p_card = attr.resolve().ok()?.part_len;
                // if
66
                match (p_parts.low(), p_parts.high(), p_card.low(), p_card.high()) {
                    (Some(p), Some(q), Some(r), Some(s)) => {
4
                        let lo = p * r;
4
                        let hi = q * s;
4
                        if len < lo || len > hi {
4
                            return Some(Domain::empty(ReturnType::Set(Box::new(
4
                                inner.return_type(),
4
                            ))));
                        }
                    }
                    (None, Some(q), None, Some(s)) => {
                        let hi = q * s;
                        if len > hi {
                            return Some(Domain::empty(ReturnType::Set(Box::new(
                                inner.return_type(),
                            ))));
                        }
                    }
                    (Some(p), None, Some(r), None) => {
                        let lo = p * r;
                        if len < lo {
                            return Some(Domain::empty(ReturnType::Set(Box::new(
                                inner.return_type(),
                            ))));
                        }
                    }
62
                    _ => {}
                }
62
                Some(Domain::set(
62
                    SetAttr::new_size(len),
62
                    Domain::int(inner.as_int()?),
                ))
            }
            Expression::Party(_, _, p) => {
                // Will pick a part, so set will share same attrs
62
                let (attr, inner) = p.domain_of()?.as_partition()?;
62
                Some(Domain::set(SetAttr::new(attr.part_len), inner))
            }
            Expression::Parts(_, p) => {
66
                let (attr, inner) = p.domain_of()?.as_partition()?;
66
                Some(Domain::set(
66
                    SetAttr::new(attr.num_parts.clone()),
66
                    Domain::set(SetAttr::new(attr.part_len), inner),
66
                ))
            }
            Expression::Card(_, collection) => {
25469
                let domain = collection.domain_of()?;
25469
                if matches!(domain.as_ground(), Some(GroundDomain::Empty(_))) {
                    Some(Domain::empty(ReturnType::Int))
25469
                } else if let Some(bounds) = collection_size(&domain) {
24693
                    Some(match bounds.range() {
24688
                        Some(size) => Domain::int(vec![size]),
5
                        None => Domain::empty(ReturnType::Int),
                    })
776
                } else if let Some((attrs, dom, codom)) = domain.as_function() {
776
                    Some(match function_size(&attrs, &dom, &codom).range() {
330
                        Some(size) => Domain::int(vec![size]),
446
                        None => Domain::empty(ReturnType::Int),
                    })
                } else if let Some((_attrs, inner)) = domain.as_partition() {
                    // A partition always covers its whole "from" domain exactly (parts are
                    // disjoint and total), so |p| (== |participants(p)|, per the `partition-card`
                    // horizontal rule) is always exactly the inner domain's size, regardless of
                    // numParts/partSize attributes.
                    match inner.length_signed() {
                        Ok(length) => Some(Domain::int(vec![Range::Single(length)])),
                        Err(_) => None,
                    }
                } else {
                    bug!(
                        "Domain of {self} needed to be a matrix, set, mset, sequence, relation, function, or partition for cardinality"
                    )
                }
            }
        }
319861016
    }
    /// Returns a reference to this expression's metadata without cloning.
6927169463
    pub fn meta_ref(&self) -> &Metadata {
        macro_rules! match_meta_ref {
            ($($variant:ident),* $(,)?) => {
                match self {
                    $(Expression::$variant(meta, ..) => meta,)*
                }
            };
        }
6927169463
        match_meta_ref!(
            AbstractLiteral,
            Root,
            Bubble,
            Comprehension,
            DominanceRelation,
            TypeAnnotation,
            DomainAnnotation,
            FromSolution,
            Metavar,
            Atomic,
            RecordField,
            UnsafeIndex,
            SafeIndex,
            SatElement,
            SatAllDifferentComparisons,
            UnsafeSlice,
            SafeSlice,
            InDomain,
            ToInt,
            Abs,
            Sum,
            Product,
            Min,
            Max,
            Not,
            Or,
            And,
            Imply,
            Iff,
            Union,
            Difference,
            In,
            Intersect,
            Supset,
            SupsetEq,
            Subset,
            SubsetEq,
            Eq,
            Neq,
            Geq,
            Leq,
            Gt,
            Lt,
            CatchUndef,
            SafeDiv,
            UnsafeDiv,
            SafeMod,
            UnsafeMod,
            Apart,
            Together,
            Participants,
            Party,
            Parts,
            Neg,
            Defined,
            Range,
            UnsafePow,
            SafePow,
            Flatten,
            AttributeAsConstraint,
            AllDiff,
            SmtDistinct,
            AllDifferentExcept,
            ElementId,
            IndexOf,
            Minus,
            Factorial,
            FlatAbsEq,
            FlatAllDiff,
            FlatTable,
            FlatShortTable,
            FlatMinEq,
            FlatSumGeq,
            FlatSumLeq,
            FlatIneq,
            FlatWatchedLiteral,
            FlatWeightedSumLeq,
            FlatWeightedSumGeq,
            FlatMinusEq,
            FlatProductEq,
            MinionDivEqUndefZero,
            MinionModuloEqUndefZero,
            MinionPow,
            MinionReify,
            MinionReifyImply,
            MinionWInIntervalSet,
            MinionWInSet,
            MinionElementOne,
            AuxDeclaration,
            SATInt,
            SatObjective,
            PairwiseSum,
            PairwiseProduct,
            Image,
            ImageSet,
            PreImage,
            Inverse,
            PermInverse,
            Compose,
            Restrict,
            LexLt,
            LexLeq,
            LexGt,
            LexGeq,
            FlatLexLt,
            FlatLexLeq,
            NegativeTable,
            ShortTable,
            Table,
            AtLeast,
            AtMost,
            Gcc,
            GccWeak,
            Active,
            ToSet,
            ToMSet,
            ToRelation,
            RelationProj,
            Pred,
            Succ,
            Card,
            Subsequence,
            Substring,
        )
6927169463
    }
    pub fn get_meta(&self) -> Metadata {
        let metas: VecDeque<Metadata> = self.children_bi();
        metas[0].clone()
    }
    pub fn set_meta(&self, meta: Metadata) {
        self.transform_bi(&|_| meta.clone());
    }
    /// Checks whether this expression is safe.
    ///
    /// An expression is unsafe if can be undefined, or if any of its children can be undefined.
    ///
    /// Unsafe expressions are (typically) prefixed with Unsafe in our AST, and can be made
    /// safe through the use of bubble rules.
4896141
    pub fn is_safe(&self) -> bool {
        // TODO: memoise in Metadata
17957990
        !self.any_expression(|expr| {
17957990
            matches!(
17957990
                expr,
                Expression::UnsafeDiv(_, _, _)
                    | Expression::UnsafeMod(_, _, _)
                    | Expression::UnsafePow(_, _, _)
                    | Expression::UnsafeIndex(_, _, _)
                    | Expression::Bubble(_, _, _)
                    | Expression::UnsafeSlice(_, _, _)
                    | Expression::Pred(_, _)
                    | Expression::Succ(_, _)
16951850
            ) || matches!(expr, Expression::Image(_, subject, argument)
                if image_can_be_undefined(subject, argument))
17957990
        })
4896141
    }
    /// True if the expression is an associative and commutative operator
30192216
    pub fn is_associative_commutative_operator(&self) -> bool {
30192216
        TryInto::<ACOperatorKind>::try_into(self).is_ok()
30192216
    }
    /// True if the expression is a matrix literal.
    ///
    /// This is true for both forms of matrix literals: those with elements of type [`Literal`] and
    /// [`Expression`].
19260
    pub fn is_matrix_literal(&self) -> bool {
19260
        matches!(
19260
            self,
            Expression::AbstractLiteral(_, AbstractLiteral::Matrix(_, _))
                | Expression::Atomic(
                    _,
                    Atom::Literal(Literal::AbstractLiteral(AbstractLiteral::Matrix(_, _))),
                )
        )
19260
    }
    /// True iff self and other are both atomic and identical.
    ///
    /// This method is useful to cheaply check equivalence. Assuming CSE is enabled, any unifiable
    /// expressions will be rewritten to a common variable. This is much cheaper than checking the
    /// entire subtrees of `self` and `other`.
117530262
    pub fn identical_atom_to(&self, other: &Expression) -> bool {
117530262
        let atom1: Result<&Atom, _> = self.try_into();
117530262
        let atom2: Result<&Atom, _> = other.try_into();
117530262
        if let (Ok(atom1), Ok(atom2)) = (atom1, atom2) {
34466297
            atom2 == atom1
        } else {
83063965
            false
        }
117530262
    }
    /// If the expression is a list, borrows the inner expressions.
    ///
    /// Prefer this over [`Expression::unwrap_list`] when the elements are only inspected: copying
    /// them costs the whole list, which matters on wide matrices that rules test on every visit.
    ///
    /// Unlike [`Expression::unwrap_list`], a matrix held as an [`Atom::Literal`] is not unwrapped,
    /// since its elements are literals with no `Expression` to borrow.
71292321
    pub fn unwrap_list_ref(&self) -> Option<&[Expression]> {
71292321
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.unwrap_list_ref()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
8051163
                matrix.unwrap_list().map(Vec::as_slice)
            }
63241158
            _ => None,
        }
71292321
    }
    /// If the expression is a list, borrows the inner expressions where it can.
    ///
    /// This accepts exactly the same expressions as [`Expression::unwrap_list`], but avoids the
    /// copy in the common case. Only a matrix held as an [`Atom::Literal`] allocates, because its
    /// elements are literals that have to be materialised as `Expression`s; every other list
    /// borrows.
    ///
    /// Prefer this over [`Expression::unwrap_list`] when the elements are usually only inspected,
    /// and over [`Expression::unwrap_list_ref`] when the narrower set of accepted expressions
    /// would change behaviour.
512933228
    pub fn unwrap_list_cow(&self) -> Option<Cow<'_, [Expression]>> {
512933228
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
12761
                expr.unwrap_list_cow()
            }
502581118
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => matrix
502581118
                .unwrap_list()
497897541
                .map(|elems| Cow::Borrowed(elems.as_slice())),
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
674706
            ) => matrix.unwrap_list().map(|elems| {
                Cow::Owned(
655993
                    elems
655993
                        .iter()
655993
                        .cloned()
753340
                        .map(|literal| Expression::Atomic(Metadata::new(), Atom::Literal(literal)))
                        .collect(),
                )
655993
            }),
9664643
            _ => None,
        }
512933228
    }
    /// Returns the number of elements when this expression is a list, without cloning them.
    ///
    /// Unlike [`Expression::unwrap_list`], this never converts literal elements into expressions.
    /// Use it for length, emptiness, and list-shape checks.
36442032
    pub fn list_len(&self) -> Option<usize> {
36442032
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
1
                expr.list_len()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
29673209
                matrix.unwrap_list().map(Vec::len)
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
782857
            ) => matrix.unwrap_list().map(Vec::len),
5985965
            _ => None,
        }
36442032
    }
    /// Whether this expression is a list, without cloning or materialising its elements.
8107861
    pub fn is_list(&self) -> bool {
8107861
        self.list_len().is_some()
8107861
    }
    /// If the expression is a list, returns a *copied* vector of the inner expressions.
    ///
    /// A list is any a matrix with the domain `int(1..)`. This includes matrix literals without
    /// any explicitly specified domain.
    ///
    /// The vector is owned: a matrix stored inside [`Atom::Literal`] holds [`Literal`]s that have
    /// to be materialised as [`Expression`]s, and callers that rewrite the elements need them by
    /// value. For inspection use [`Expression::unwrap_list_cow`]; for shape checks use
    /// [`Expression::list_len`] or [`Expression::is_list`].
1660374
    pub fn unwrap_list(&self) -> Option<Vec<Expression>> {
1660374
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                expr.unwrap_list()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
1381799
                matrix.unwrap_list().cloned()
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
1
            ) => matrix.unwrap_list().map(|elems| {
1
                elems
1
                    .clone()
1
                    .into_iter()
2
                    .map(|x: Literal| Expression::Atomic(Metadata::new(), Atom::Literal(x)))
                    .collect_vec()
1
            }),
278574
            _ => None,
        }
1660374
    }
    /// If the expression is a list, consumes it and returns its elements.
    ///
    /// Prefer this over [`Expression::unwrap_list`] when the expression is already owned: it moves
    /// expression elements out of the matrix rather than cloning the complete list.
8471055
    pub fn into_list(self) -> Option<Vec<Expression>> {
8471055
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                Moo::unwrap_or_clone(expr).into_list()
            }
            Expression::AbstractLiteral(_, matrix @ AbstractLiteral::Matrix(_, _)) => {
6749199
                matrix.into_list()
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(matrix @ AbstractLiteral::Matrix(_, _))),
1715996
            ) => matrix.into_list().map(|elems| {
1715039
                elems
1715039
                    .into_iter()
3233827
                    .map(|literal| Expression::Atomic(Metadata::new(), Atom::Literal(literal)))
                    .collect()
1715039
            }),
5860
            _ => None,
        }
8471055
    }
    /// If the expression is an expression-valued matrix, borrows its elements and index domain.
    ///
    /// As with [`Expression::unwrap_matrix_unchecked`], callers must preserve the relationship
    /// between the domain and element count. Literal-valued matrices are excluded because their
    /// elements cannot be borrowed as [`Expression`]s.
213904169
    pub fn unwrap_matrix_unchecked_ref(&self) -> Option<(&[Expression], &DomainPtr)> {
213904169
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
14823
                expr.unwrap_matrix_unchecked_ref()
            }
            Expression::AbstractLiteral(_, AbstractLiteral::Matrix(elems, domain)) => {
203176420
                Some((elems, domain))
            }
10712926
            _ => None,
        }
213904169
    }
    /// If the expression is a matrix, gets it elements and index domain.
    ///
    /// **Consider using the safer [`Expression::unwrap_list`] instead.**
    ///
    /// It is generally undefined to edit the length of a matrix unless it is a list (as defined by
    /// [`Expression::unwrap_list`]). Users of this function should ensure that, if the matrix is
    /// reconstructed, the index domain and the number of elements in the matrix remain the same.
57977265
    pub fn unwrap_matrix_unchecked(self) -> Option<(Vec<Expression>, DomainPtr)> {
57977265
        match self {
            Expression::TypeAnnotation(_, expr, _) | Expression::DomainAnnotation(_, expr, _) => {
                Moo::unwrap_or_clone(expr).unwrap_matrix_unchecked()
            }
            Expression::AbstractLiteral(_, AbstractLiteral::Matrix(elems, domain)) => {
45049521
                Some((elems, domain))
            }
            Expression::Atomic(
                _,
                Atom::Literal(Literal::AbstractLiteral(AbstractLiteral::Matrix(elems, domain))),
            ) => Some((
1230528
                elems
1230528
                    .into_iter()
4962480
                    .map(|x: Literal| Expression::Atomic(Metadata::new(), Atom::Literal(x)))
                    .collect_vec(),
1230528
                domain.into(),
            )),
11697216
            _ => None,
        }
57977265
    }
    /// For a Root expression, extends the inner vec with the given vec.
    ///
    /// # Panics
    /// Panics if the expression is not Root.
    pub fn extend_root(self, exprs: Vec<Expression>) -> Expression {
        match self {
            Expression::Root(meta, mut children) => {
                children.extend(exprs);
                Expression::Root(meta, children)
            }
            _ => panic!("extend_root called on a non-Root expression"),
        }
    }
    /// Converts the expression to a literal, if possible.
22250
    pub fn into_literal(self) -> Option<Literal> {
22250
        match self {
21193
            Expression::Atomic(_, Atom::Literal(lit)) => Some(lit),
            Expression::AbstractLiteral(_, abslit) => {
                Some(Literal::AbstractLiteral(abslit.into_literals()?))
            }
            Expression::Neg(_, e) => {
91
                let Literal::Int(i) = Moo::unwrap_or_clone(e).into_literal()? else {
                    bug!("negated literal should be an int");
                };
87
                Some(Literal::Int(-i))
            }
966
            _ => None,
        }
22250
    }
    /// If this expression is an associative-commutative operator, return its [ACOperatorKind].
3067196
    pub fn to_ac_operator_kind(&self) -> Option<ACOperatorKind> {
3067196
        TryFrom::try_from(self).ok()
3067196
    }
    /// [`Typeable::return_type`], where the type can be worked out.
    ///
    /// `return_type` panics for a reference whose declaration has no domain yet -- a value letting
    /// whose body is not yet a constant, say. Parsers cannot rule those out while building the
    /// model, so they ask this instead and read `None` as "unknown".
4391766
    pub fn try_return_type(&self) -> Option<ReturnType> {
11784829
        let has_untyped_reference = self.any_expression(|expr| {
11784829
            matches!(expr, Expression::Atomic(_, Atom::Reference(reference))
4388186
                if reference.domain().is_none())
11784829
        });
4391766
        (!has_untyped_reference).then(|| self.return_type())
4391766
    }
    /// Returns the categories of all sub-expressions of self.
3132
    pub fn universe_categories(&self) -> HashSet<Category> {
3132
        let mut categories = HashSet::new();
3132
        self.for_each_expression(&mut |expr| {
3132
            categories.insert(expr.category_of());
3132
        });
3132
        categories
3132
    }
}
/// True when `image(subject, argument)` can be undefined.
///
/// A function is defined only on its own domain -- `total` means defined for every value *in* that
/// domain, not defined everywhere -- so an argument that can fall outside it has no image there. A
/// partial function may also be undefined inside its domain, and a sequence is defined only on
/// `1..|s|`. When the length varies, every member of the domain still has the prefix `1..minSize`;
/// positions past that prefix are not known until solving.
///
/// Anything this cannot work out counts as undefinable. Safety has to be conservative: treating a
/// partial application as total lets its definedness be reasoned away, and the constraint it sits
/// in then silently holds where it should not.
660214
pub fn image_can_be_undefined(subject: &Expression, argument: &Expression) -> bool {
660214
    let Some(domain) = subject.domain_of().and_then(|domain| domain.resolve().ok()) else {
        return true;
    };
660214
    match domain.as_ref() {
        GroundDomain::Function(attr, from, _) => {
514924
            !matches!(attr.partiality, PartialityAttr::Total) || !argument_always_in(argument, from)
        }
        // A permutation is total on its own domain, which is also where its image lands.
2784
        GroundDomain::Permutation(_, inner) => !argument_always_in(argument, inner),
        GroundDomain::Sequence(attr, _) => {
            // Positions `1..=min_length` exist in every member of the domain. Anything past that
            // may sit in the allocated matrix and still be undefined if `|s|` is shorter.
142506
            let min_length = attr.size.low().copied().unwrap_or(0);
142506
            min_length <= 0
142506
                || !argument_always_in(
142506
                    argument,
142506
                    &GroundDomain::Int(vec![Range::Bounded(1, min_length)], None),
142506
                )
        }
        _ => true,
    }
660214
}
/// Whether every value `argument` can take lies in `domain`.
///
/// Answers false whenever that cannot be established, including for domains that are equivalent
/// but not written the same way -- callers use this to decide whether they may reason about
/// definedness, where saying "no" only costs them the chance to simplify.
650934
fn argument_always_in(argument: &Expression, domain: &GroundDomain) -> bool {
650934
    let Some(argument_domain) = argument.domain_of().and_then(|d| d.resolve().ok()) else {
        return false;
    };
650934
    argument_domain
650934
        .intersect(domain)
650934
        .is_ok_and(|intersection| intersection == *argument_domain.as_ref())
650934
}
impl TryFrom<&Expression> for i32 {
    type Error = ();
44897570
    fn try_from(value: &Expression) -> Result<Self, Self::Error> {
44897570
        let Expression::Atomic(_, atom) = value else {
3175313
            return Err(());
        };
41722257
        let Atom::Literal(lit) = atom else {
72040
            return Err(());
        };
41650217
        let Literal::Int(i) = lit else {
63278
            return Err(());
        };
41586939
        Ok(*i)
44897570
    }
}
impl TryFrom<Expression> for i32 {
    type Error = ();
    fn try_from(value: Expression) -> Result<Self, Self::Error> {
        TryFrom::<&Expression>::try_from(&value)
    }
}
impl From<i32> for Expression {
32952485
    fn from(i: i32) -> Self {
32952485
        Expression::Atomic(Metadata::new(), Atom::Literal(Literal::Int(i)))
32952485
    }
}
impl From<bool> for Expression {
229773399
    fn from(b: bool) -> Self {
229773399
        Expression::Atomic(Metadata::new(), Atom::Literal(Literal::Bool(b)))
229773399
    }
}
impl From<Atom> for Expression {
131014
    fn from(value: Atom) -> Self {
131014
        Expression::Atomic(Metadata::new(), value)
131014
    }
}
impl From<Literal> for Expression {
10428884
    fn from(value: Literal) -> Self {
10428884
        Expression::Atomic(Metadata::new(), value.into())
10428884
    }
}
impl From<AbstractLiteral<Expression>> for Expression {
49776
    fn from(value: AbstractLiteral<Expression>) -> Self {
49776
        Expression::AbstractLiteral(Metadata::new(), value)
49776
    }
}
impl From<Moo<Expression>> for Expression {
11851521
    fn from(val: Moo<Expression>) -> Self {
11851521
        val.as_ref().clone()
11851521
    }
}
impl CategoryOf for Expression {
6824081
    fn category_of(&self) -> Category {
        // take highest category of all the expressions children
21808928
        let category = self.cata(&move |x,children| {
21808928
            if let Some(max_category) = children.iter().max() {
                // if this expression contains subexpressions, return the maximum category of the
                // subexpressions
6714928
                *max_category
            } else {
                // this expression has no children
15094000
                let mut max_category = Category::Bottom;
                // calculate the category by looking at all atoms, submodels, comprehensions, and
                // declarationptrs inside this expression
                // this should generically cover all leaf types we currently have in oxide.
                // if x contains submodels (including comprehensions)
15094000
                if !Biplate::<Model>::universe_bi(&x).is_empty() {
                    // assume that the category is decision
                    return Category::Decision;
15094000
                }
                // if x contains atoms
15094000
                if let Some(max_atom_category) = Biplate::<Atom>::universe_bi(&x).iter().map(|x| x.category_of()).max()
                // and those atoms have a higher category than we already know about
13763942
                && max_atom_category > max_category{
                    // update category
13763942
                    max_category = max_atom_category;
1330058
                }
                // if x contains declarationPtrs
15094000
                if let Some(max_declaration_category) = Biplate::<DeclarationPtr>::universe_bi(&x).iter().map(|x| x.category_of()).max()
                // and those pointers have a higher category than we already know about
11404997
                && max_declaration_category > max_category{
                    // update category
1330638
                    max_category = max_declaration_category;
13763362
                }
15094000
                max_category
            }
21808928
        });
6824081
        if cfg!(debug_assertions) {
6824081
            trace!(
7428
                category= %category,
7428
                expression= %self,
7428
                "Called Expression::category_of()"
            );
        };
6824081
        category
6824081
    }
}
impl Display for Expression {
51228271
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
51228271
        match &self {
            Expression::Union(_, box1, box2) => {
4090
                write!(f, "({} union {})", box1.clone(), box2.clone())
            }
            Expression::Difference(_, box1, box2) => {
659
                write!(f, "({} - {})", box1.clone(), box2.clone())
            }
            Expression::In(_, e1, e2) => {
22629
                write!(f, "{e1} in {e2}")
            }
            Expression::Intersect(_, box1, box2) => {
6792
                write!(f, "({} intersect {})", box1.clone(), box2.clone())
            }
            Expression::Supset(_, box1, box2) => {
348
                write!(f, "({} supset {})", box1.clone(), box2.clone())
            }
            Expression::SupsetEq(_, box1, box2) => {
348
                write!(f, "({} supsetEq {})", box1.clone(), box2.clone())
            }
            Expression::Subset(_, box1, box2) => {
609
                write!(f, "({} subset {})", box1.clone(), box2.clone())
            }
            Expression::SubsetEq(_, box1, box2) => {
2090
                write!(f, "({} subsetEq {})", box1.clone(), box2.clone())
            }
6235850
            Expression::AbstractLiteral(_, l) => l.fmt(f),
75625
            Expression::Comprehension(_, c) => c.fmt(f),
244879
            Expression::UnsafeIndex(_, e1, e2) => write!(f, "{e1}{}", pretty_vec(e2)),
            Expression::RecordField(_, r, fld) => {
4495
                write!(f, "{r}[{fld}]")
            }
434969
            Expression::SafeIndex(_, e1, e2) => write!(f, "SafeIndex({e1},{})", pretty_vec(e2)),
            Expression::UnsafeSlice(_, e1, es) => {
31871
                let args = es
31871
                    .iter()
61538
                    .map(|x| match x {
29667
                        Some(x) => format!("{x}"),
31871
                        None => "..".into(),
61538
                    })
31871
                    .join(",");
31871
                write!(f, "{e1}[{args}]")
            }
            Expression::SafeSlice(_, e1, es) => {
15660
                let args = es
15660
                    .iter()
29348
                    .map(|x| match x {
13688
                        Some(x) => format!("{x}"),
15660
                        None => "..".into(),
29348
                    })
15660
                    .join(",");
15660
                write!(f, "SafeSlice({e1},[{args}])")
            }
            Expression::InDomain(_, e, domain) => {
9280
                write!(f, "__inDomain({e},{domain})")
            }
            Expression::Root(_, exprs) => {
135374
                write!(f, "{}", pretty_expressions_as_top_level(exprs))
            }
            Expression::DominanceRelation(_, expr) => write!(f, "DominanceRelation({expr})"),
            Expression::FromSolution(_, expr) => write!(f, "FromSolution({expr})"),
            Expression::Metavar(_, name) => write!(f, "&{name}"),
32681155
            Expression::Atomic(_, atom) => atom.fmt(f),
            Expression::TypeAnnotation(_, expr, domain) => {
870
                write!(
870
                    f,
                    "{}",
870
                    pretty_expression_type_annotation(expr, domain.as_type_string())
                )
            }
            Expression::DomainAnnotation(_, expr, domain) => {
58
                write!(f, "{}", pretty_expression_domain_annotation(expr, domain))
            }
11488
            Expression::Abs(_, a) | Expression::Card(_, a) => write!(f, "|{a}|"),
            Expression::Sum(_, e) => {
392847
                write!(f, "sum({e})")
            }
            Expression::Product(_, e) => {
171209
                write!(f, "product({e})")
            }
            Expression::Min(_, e) => {
20561
                write!(f, "min({e})")
            }
            Expression::Max(_, e) => {
20366
                write!(f, "max({e})")
            }
            Expression::Not(_, expr_box) => {
220412
                write!(f, "!({})", expr_box.clone())
            }
            Expression::Or(_, e) => {
1655621
                write!(f, "or({e})")
            }
            Expression::And(_, e) => {
2699480
                write!(f, "and({e})")
            }
            Expression::Imply(_, box1, box2) => {
160514
                write!(f, "({box1}) -> ({box2})")
            }
            Expression::Iff(_, box1, box2) => {
197462
                write!(f, "({box1}) <-> ({box2})")
            }
            Expression::Eq(_, box1, box2) => {
1373598
                write!(f, "{box1} = {box2}")
            }
            Expression::Neq(_, box1, box2) => {
572200
                write!(f, "{box1} != {box2}")
            }
            Expression::Geq(_, box1, box2) => {
129836
                write!(f, "{box1} >= {box2}")
            }
            Expression::Leq(_, box1, box2) => {
558287
                write!(f, "{box1} <= {box2}")
            }
            Expression::Gt(_, box1, box2) => {
62137
                write!(f, "{box1} > {box2}")
            }
            Expression::Lt(_, box1, box2) => {
78279
                write!(f, "{box1} < {box2}")
            }
            Expression::Apart(_, list, partition) => {
116
                write!(f, "apart({list}, {partition})")
            }
            Expression::Together(_, list, partition) => {
116
                write!(f, "together({list}, {partition})")
            }
            Expression::Participants(_, partition) => {
132
                write!(f, "participants({partition})")
            }
            Expression::Party(_, element, partition) => {
124
                write!(f, "party({element}, {partition})")
            }
            Expression::Parts(_, partition) => {
132
                write!(f, "parts({partition})")
            }
            Expression::FlatMinEq(_, vars, result) => {
638
                write!(f, "FlatMinEq({}, {})", pretty_vec(vars), result.clone())
            }
            Expression::FlatSumGeq(_, box1, box2) => {
131388
                write!(f, "SumGeq({}, {})", pretty_vec(box1), box2.clone())
            }
            Expression::FlatSumLeq(_, box1, box2) => {
127908
                write!(f, "SumLeq({}, {})", pretty_vec(box1), box2.clone())
            }
158634
            Expression::FlatIneq(_, box1, box2, box3) => write!(
158634
                f,
                "Ineq({}, {}, {})",
158634
                box1.clone(),
158634
                box2.clone(),
158634
                box3.clone()
            ),
            Expression::Flatten(_, n, m) => {
7772
                if let Some(n) = n {
                    write!(f, "flatten({n}, {m})")
                } else {
7772
                    write!(f, "flatten({m})")
                }
            }
            Expression::AttributeAsConstraint(_, target, attr, val) => {
                if let Some(val) = val {
                    write!(f, "{attr}({target}, {val})")
                } else {
                    write!(f, "{attr}({target})")
                }
            }
            Expression::AllDiff(_, e) => {
37951
                write!(f, "allDifferent({e})")
            }
            Expression::SmtDistinct(_, e) => {
6032
                write!(f, "smtDistinct({e})")
            }
            Expression::AllDifferentExcept(_, matrix, except) => {
1334
                write!(f, "allDifferentExcept({matrix}, {except})")
            }
            Expression::ElementId(_, matrix, value) => {
348
                write!(f, "elementId({matrix}, {value})")
            }
232
            Expression::IndexOf(_, matrix, value) => write!(f, "indexOf({matrix}, {value})"),
            Expression::SatAllDifferentComparisons(_, conditions) => {
                write!(f, "sat-allDifferent-comparisons({conditions})")
            }
            Expression::SatElement(_, matrix, index, value) => {
261
                write!(f, "satElement({matrix}, {index}, {value})")
            }
            Expression::FlatShortTable(_, inputs, rows) => {
638
                write!(f, "FlatShortTable({}, {rows:?})", pretty_vec(inputs))
            }
            Expression::FlatTable(_, inputs, rows, negative) => {
1160
                write!(f, "FlatTable({}, {rows:?}, {negative})", pretty_vec(inputs))
            }
            Expression::Table(_, tuple_expr, rows_expr) => {
2436
                write!(f, "table({tuple_expr}, {rows_expr})")
            }
            Expression::ShortTable(_, tuple_expr, rows_expr) => {
1102
                write!(f, "shortTable({tuple_expr}, {rows_expr})")
            }
            Expression::NegativeTable(_, tuple_expr, rows_expr) => {
464
                write!(f, "negativeTable({tuple_expr}, {rows_expr})")
            }
            Expression::AtLeast(_, vars, counts, values) => {
696
                write!(f, "atLeast({vars}, {counts}, {values})")
            }
            Expression::AtMost(_, vars, counts, values) => {
348
                write!(f, "atMost({vars}, {counts}, {values})")
            }
            Expression::Gcc(_, vars, values, counts) => {
                write!(f, "globalCardinality({vars}, {values}, {counts})")
            }
            Expression::GccWeak(_, vars, values, counts) => {
464
                write!(f, "gccweak({vars}, {values}, {counts})")
            }
            Expression::Bubble(_, box1, box2) => {
125743
                write!(f, "{{{} @ {}}}", box1.clone(), box2.clone())
            }
            Expression::CatchUndef(_, box1, box2) => {
957
                write!(f, "catchUndef({box1}, {box2})")
            }
            Expression::SafeDiv(_, box1, box2) => {
113273
                write!(f, "SafeDiv({}, {})", box1.clone(), box2.clone())
            }
            Expression::UnsafeDiv(_, box1, box2) => {
60690
                write!(f, "({} / {})", box1.clone(), box2.clone())
            }
            Expression::UnsafePow(_, box1, box2) => {
232011
                write!(f, "({} ** {})", box1.clone(), box2.clone())
            }
            Expression::SafePow(_, box1, box2) => {
296800
                write!(f, "SafePow({}, {})", box1.clone(), box2.clone())
            }
            Expression::Subsequence(_, s, t) => {
1769
                write!(f, "{} subsequence {}", s.clone(), t.clone())
            }
            Expression::Substring(_, s, t) => {
5423
                write!(f, "{} substring {}", s.clone(), t.clone())
            }
            Expression::MinionDivEqUndefZero(_, box1, box2, box3) => {
21938
                write!(
21938
                    f,
                    "DivEq({}, {}, {})",
21938
                    box1.clone(),
21938
                    box2.clone(),
21938
                    box3.clone()
                )
            }
            Expression::MinionModuloEqUndefZero(_, box1, box2, box3) => {
21184
                write!(
21184
                    f,
                    "ModEq({}, {}, {})",
21184
                    box1.clone(),
21184
                    box2.clone(),
21184
                    box3.clone()
                )
            }
            Expression::FlatWatchedLiteral(_, x, l) => {
460318
                write!(f, "WatchedLiteral({x},{l})")
            }
            Expression::MinionReify(_, box1, box2) => {
82476
                write!(f, "Reify({}, {})", box1.clone(), box2.clone())
            }
            Expression::MinionReifyImply(_, box1, box2) => {
49012
                write!(f, "ReifyImply({}, {})", box1.clone(), box2.clone())
            }
            Expression::MinionWInIntervalSet(_, atom, intervals) => {
986
                let intervals = intervals.iter().join(",");
986
                write!(f, "__minion_w_inintervalset({atom},[{intervals}])")
            }
            Expression::MinionWInSet(_, atom, values) => {
522
                let values = values.iter().join(",");
522
                write!(f, "__minion_w_inset({atom},[{values}])")
            }
            Expression::AuxDeclaration(_, reference, e) => {
143100
                write!(f, "{} =aux {}", reference, e.clone())
            }
            Expression::UnsafeMod(_, a, b) => {
47218
                write!(f, "{} % {}", a.clone(), b.clone())
            }
            Expression::SafeMod(_, a, b) => {
79321
                write!(f, "SafeMod({},{})", a.clone(), b.clone())
            }
            Expression::Neg(_, a) => {
23882
                write!(f, "-({})", a.clone())
            }
            Expression::Factorial(_, a) => {
290
                write!(f, "({})!", a.clone())
            }
            Expression::Minus(_, a, b) => {
81626
                write!(f, "({} - {})", a.clone(), b.clone())
            }
            Expression::FlatAllDiff(_, es) => {
2402
                write!(f, "__flat_alldiff({})", pretty_vec(es))
            }
            Expression::FlatAbsEq(_, a, b) => {
812
                write!(f, "AbsEq({},{})", a.clone(), b.clone())
            }
            Expression::FlatMinusEq(_, a, b) => {
2552
                write!(f, "MinusEq({},{})", a.clone(), b.clone())
            }
            Expression::FlatProductEq(_, a, b, c) => {
3558
                write!(
3558
                    f,
                    "FlatProductEq({},{},{})",
3558
                    a.clone(),
3558
                    b.clone(),
3558
                    c.clone()
                )
            }
            Expression::FlatWeightedSumLeq(_, cs, vs, total) => {
2242
                write!(
2242
                    f,
                    "FlatWeightedSumLeq({},{},{})",
2242
                    pretty_vec(cs),
2242
                    pretty_vec(vs),
2242
                    total.clone()
                )
            }
            Expression::FlatWeightedSumGeq(_, cs, vs, total) => {
2010
                write!(
2010
                    f,
                    "FlatWeightedSumGeq({},{},{})",
2010
                    pretty_vec(cs),
2010
                    pretty_vec(vs),
2010
                    total.clone()
                )
            }
            Expression::MinionPow(_, atom, atom1, atom2) => {
109588
                write!(f, "MinionPow({atom},{atom1},{atom2})")
            }
            Expression::MinionElementOne(_, atoms, atom, atom1) => {
3770
                let atoms = atoms.iter().join(",");
3770
                write!(f, "__minion_element_one([{atoms}],{atom},{atom1})")
            }
            Expression::ToInt(_, expr) => {
477256
                write!(f, "toInt({expr})")
            }
            Expression::SatObjective(_, minimise, value) => {
                write!(f, "optimise(minimise={minimise}, value={value})")
            }
            Expression::SATInt(_, encoding, bits, (min, max)) => {
13601
                write!(f, "SATInt({encoding:?}, {bits} [{min}, {max}])")
            }
            Expression::PairwiseSum(_, a, b) => write!(f, "PairwiseSum({a}, {b})"),
            Expression::PairwiseProduct(_, a, b) => write!(f, "PairwiseProduct({a}, {b})"),
1352
            Expression::Defined(_, function) => write!(f, "defined({function})"),
1997
            Expression::Range(_, function) => write!(f, "range({function})"),
1893
            Expression::Image(_, function, elems) => write!(f, "image({function},{elems})"),
145
            Expression::ImageSet(_, function, elems) => write!(f, "imageSet({function},{elems})"),
257
            Expression::PreImage(_, function, elems) => write!(f, "preImage({function},{elems})"),
145
            Expression::Inverse(_, a, b) => write!(f, "inverse({a},{b})"),
            Expression::PermInverse(_, p) => write!(f, "permInverse({p})"),
            Expression::Compose(_, g, h) => write!(f, "compose({g},{h})"),
205
            Expression::Restrict(_, function, domain) => write!(f, "restrict({function},{domain})"),
18415
            Expression::LexLt(_, a, b) => write!(f, "({a} <lex {b})"),
11513
            Expression::LexLeq(_, a, b) => write!(f, "({a} <=lex {b})"),
1247
            Expression::LexGt(_, a, b) => write!(f, "({a} >lex {b})"),
2001
            Expression::LexGeq(_, a, b) => write!(f, "({a} >=lex {b})"),
            Expression::FlatLexLt(_, a, b) => {
5742
                write!(f, "FlatLexLt({}, {})", pretty_vec(a), pretty_vec(b))
            }
            Expression::FlatLexLeq(_, a, b) => {
2320
                write!(f, "FlatLexLeq({}, {})", pretty_vec(a), pretty_vec(b))
            }
            Expression::Active(_, variant, field_name) => {
1711
                write!(f, "active({variant}, {field_name})")
            }
297
            Expression::ToSet(_, other) => write!(f, "toSet({other})"),
145
            Expression::ToMSet(_, other) => write!(f, "toMSet({other})"),
116
            Expression::ToRelation(_, function) => write!(f, "toRelation({function})"),
            Expression::RelationProj(_, relation, projections) => {
66
                let projections_str = projections
66
                    .iter()
198
                    .map(|x| {
198
                        if let Some(x) = x {
66
                            x.to_string()
                        } else {
132
                            String::from("_")
                        }
198
                    })
66
                    .join(", ");
66
                write!(f, "{relation}({projections_str})")
            }
            Expression::Pred(_, ev) => write!(f, "Pred({})", ev),
            Expression::Succ(_, ev) => write!(f, "Succ({})", ev),
        }
51228271
    }
}
188658
fn minus_operand_return_type(expr: &Expression) -> ReturnType {
188658
    match expr {
        Expression::Atomic(_, Atom::Reference(reference)) => {
73604
            let decl_kind = reference.ptr.kind().clone();
73604
            match decl_kind {
                DeclarationKind::Find(var) | DeclarationKind::FindAuxiliary(var) => {
35760
                    var.return_type()
                }
                DeclarationKind::EnumeratedType(ty) => ReturnType::EnumeratedType(ty),
                DeclarationKind::UnnamedType(_) => reference.ptr.return_type(),
                DeclarationKind::Given(domain)
2900
                | DeclarationKind::DomainLetting(domain) => domain.return_type(),
21344
                DeclarationKind::Quantified(inner) => inner.domain().return_type(),
                DeclarationKind::QuantifiedExpr(inner)
                | DeclarationKind::TemporaryValueLetting(inner)
                // not sure if i should ever be looking at the domain ptr but seems to work
13600
                | DeclarationKind::ValueLetting(inner, _) => inner.return_type(),
            }
        }
115054
        _ => expr.return_type(),
    }
188658
}
impl Typeable for Expression {
179431911
    fn return_type(&self) -> ReturnType {
179431911
        match self {
            Expression::Union(_, subject, _)
            | Expression::Intersect(_, subject, _)
12586
            | Expression::Difference(_, subject, _) => subject.return_type(),
211472
            Expression::In(_, _, _) => ReturnType::Bool,
261
            Expression::Supset(_, _, _) => ReturnType::Bool,
261
            Expression::SupsetEq(_, _, _) => ReturnType::Bool,
261
            Expression::Subset(_, _, _) => ReturnType::Bool,
261
            Expression::SubsetEq(_, _, _) => ReturnType::Bool,
2218063
            Expression::AbstractLiteral(_, lit) => lit.return_type(),
            Expression::RecordField(_, rec, field_name) => {
72210
                if let ReturnType::Record(ents) = rec.return_type() {
21344
                    for Field { name, value } in ents {
31987
                        if name.eq(field_name) {
21344
                            return value;
10643
                        }
                    }
50866
                }
50866
                ReturnType::Unknown
            }
            Expression::UnsafeIndex(_, subject, idx) | Expression::SafeIndex(_, subject, idx) => {
33023258
                let mut indexed_ty = subject.return_type();
33023258
                for index in idx {
33121684
                    indexed_ty = match indexed_ty {
                        ReturnType::Tuple(field_types) => {
671060
                            let Expression::Atomic(_, Atom::Literal(Literal::Int(index))) = index
                            else {
                                return ReturnType::Unknown;
                            };
671060
                            let Some(zero_based_index) = index
671060
                                .checked_sub(1)
671060
                                .and_then(|index| usize::try_from(index).ok())
                            else {
                                return ReturnType::Unknown;
                            };
671060
                            field_types
671060
                                .get(zero_based_index)
671060
                                .cloned()
671060
                                .unwrap_or(ReturnType::Unknown)
                        }
                        // Declared matrix types are flat, whereas matrix literals can have one
                        // nested Matrix return type per dimension. Continue through nested
                        // matrices, but stop once the declared element type is reached.
                        ReturnType::Matrix(element_type) => {
32450624
                            let element_type = *element_type;
32450624
                            if !matches!(element_type, ReturnType::Matrix(_)) {
32102218
                                return element_type;
348406
                            }
348406
                            element_type
                        }
                        // Record and variant indices need their field-name context to determine a
                        // result type. Unknown can likewise be resolved by later typechecking.
                        ReturnType::Record(_) | ReturnType::Variant(_) | ReturnType::Unknown => {
                            return ReturnType::Unknown;
                        }
                        subject_ty => bug!(
                            "Invalid indexing operation: expected the operand to be a collection, got {self}: {subject_ty}"
                        ),
                    };
                }
921040
                indexed_ty
            }
            Expression::UnsafeSlice(_, subject, _) | Expression::SafeSlice(_, subject, _) => {
636179
                let mut element_type = subject.return_type();
1272358
                while let ReturnType::Matrix(inner) = element_type {
636179
                    element_type = *inner;
                }
636179
                ReturnType::Matrix(Box::new(element_type))
            }
            Expression::InDomain(_, _, _) => ReturnType::Bool,
174
            Expression::Comprehension(_, comp) => comp.return_type(),
            Expression::Root(_, _) => ReturnType::Bool,
            Expression::DominanceRelation(_, _) => ReturnType::Bool,
26680
            Expression::FromSolution(_, expr) => expr.return_type(),
1719
            Expression::Metavar(_, _) => ReturnType::Unknown,
113696561
            Expression::Atomic(_, atom) => atom.return_type(),
29
            Expression::TypeAnnotation(_, _, domain) => domain.return_type(),
            Expression::DomainAnnotation(_, _, domain) => domain.return_type(),
16733
            Expression::Abs(_, _) => ReturnType::Int,
5056047
            Expression::Sum(_, _) => ReturnType::Int,
583785
            Expression::Product(_, _) => ReturnType::Int,
65656
            Expression::Min(_, _) => ReturnType::Int,
54050
            Expression::Max(_, _) => ReturnType::Int,
224093
            Expression::Not(_, _) => ReturnType::Bool,
1118265
            Expression::Or(_, _) => ReturnType::Bool,
334635
            Expression::Imply(_, _, _) => ReturnType::Bool,
5249
            Expression::Iff(_, _, _) => ReturnType::Bool,
8393385
            Expression::And(_, _) => ReturnType::Bool,
2279661
            Expression::Eq(_, _, _) => ReturnType::Bool,
597327
            Expression::Neq(_, _, _) => ReturnType::Bool,
44250
            Expression::Geq(_, _, _) => ReturnType::Bool,
446535
            Expression::Leq(_, _, _) => ReturnType::Bool,
97477
            Expression::Gt(_, _, _) => ReturnType::Bool,
26543
            Expression::Lt(_, _, _) => ReturnType::Bool,
            Expression::Apart(_, _, _) => ReturnType::Bool,
            Expression::Together(_, _, _) => ReturnType::Bool,
116
            Expression::Party(_, _, subject) => ReturnType::Set(Box::new(subject.return_type())),
            Expression::Participants(_, subject) => {
116
                ReturnType::Set(Box::new(subject.return_type()))
            }
            Expression::Parts(_, subject) => {
116
                ReturnType::Set(Box::new(ReturnType::Set(Box::new(subject.return_type()))))
            }
37149
            Expression::CatchUndef(_, value, _) => value.return_type(),
385722
            Expression::SafeDiv(_, _, _) => ReturnType::Int,
301492
            Expression::UnsafeDiv(_, _, _) => ReturnType::Int,
            Expression::FlatAllDiff(_, _) => ReturnType::Bool,
            Expression::FlatMinEq(_, _, _) => ReturnType::Bool,
232
            Expression::FlatSumGeq(_, _, _) => ReturnType::Bool,
            Expression::FlatSumLeq(_, _, _) => ReturnType::Bool,
            Expression::MinionDivEqUndefZero(_, _, _, _) => ReturnType::Bool,
265
            Expression::FlatIneq(_, _, _, _) => ReturnType::Bool,
            Expression::Flatten(_, _, matrix) => {
280053
                let matrix_type = matrix.return_type();
280053
                match matrix_type {
                    ReturnType::Matrix(_) => {
                        // unwrap until we get to innermost element
280053
                        let mut elem_type = matrix_type;
560106
                        while let ReturnType::Matrix(new_elem_type) = &elem_type {
280053
                            elem_type = *new_elem_type.clone();
                        }
280053
                        ReturnType::Matrix(Box::new(elem_type))
                    }
                    _ => bug!(
                        "Invalid indexing operation: expected the operand to be a collection, got {self}: {matrix_type}"
                    ),
                }
            }
13195
            Expression::AllDiff(_, _) => ReturnType::Bool,
            Expression::SmtDistinct(_, _) => ReturnType::Bool,
87
            Expression::AllDifferentExcept(_, _, _) => ReturnType::Bool,
7453
            Expression::ElementId(_, _, _) | Expression::IndexOf(_, _, _) => ReturnType::Int,
            Expression::SatElement(_, _, _, _) | Expression::SatAllDifferentComparisons(_, _) => {
29
                ReturnType::Bool
            }
            Expression::Table(_, _, _)
            | Expression::FlatTable(..)
5249
            | Expression::FlatShortTable(..) => ReturnType::Bool,
            Expression::NegativeTable(_, _, _) | Expression::ShortTable(_, _, _) => {
145
                ReturnType::Bool
            }
            Expression::AtLeast(_, _, _, _) => ReturnType::Bool,
899
            Expression::AtMost(_, _, _, _) => ReturnType::Bool,
            Expression::Gcc(_, _, _, _) | Expression::GccWeak(_, _, _, _) => ReturnType::Bool,
254899
            Expression::Bubble(_, inner, _) => inner.return_type(),
30013
            Expression::FlatWatchedLiteral(_, _, _) => ReturnType::Bool,
            Expression::MinionReify(_, _, _) => ReturnType::Bool,
            Expression::MinionReifyImply(_, _, _) => ReturnType::Bool,
58
            Expression::MinionWInIntervalSet(_, _, _) => ReturnType::Bool,
            Expression::MinionWInSet(_, _, _) => ReturnType::Bool,
580
            Expression::MinionElementOne(_, _, _, _) => ReturnType::Bool,
            Expression::AuxDeclaration(_, _, _) => ReturnType::Bool,
1626890
            Expression::UnsafeMod(_, _, _) => ReturnType::Int,
2674717
            Expression::SafeMod(_, _, _) => ReturnType::Int,
            Expression::MinionModuloEqUndefZero(_, _, _, _) => ReturnType::Bool,
175512
            Expression::Neg(_, _) => ReturnType::Int,
2088
            Expression::Factorial(_, _) => ReturnType::Int,
82686
            Expression::UnsafePow(_, _, _) => ReturnType::Int,
171050
            Expression::SafePow(_, _, _) => ReturnType::Int,
            Expression::Minus(_, a, b) => {
                // rather than calling .return_type on a and b which sometimes errors on references that don't have domains
                // use custom function that extracts return type from atomic references based on each declaration variant
94329
                let a_type = minus_operand_return_type(a);
94329
                let b_type = minus_operand_return_type(b);
94329
                if a_type == ReturnType::Int && b_type == ReturnType::Int {
94329
                    ReturnType::Int
                } else if let ReturnType::Set(a_inner) = a_type
                    && let ReturnType::Set(b_inner) = b_type
                    && a_inner == b_inner
                {
                    ReturnType::Set(a_inner)
                } else {
                    bug!(
                        "Invalid minus operation: operands are of different or invalid types for this operation"
                    )
                }
            }
            Expression::FlatAbsEq(_, _, _) => ReturnType::Bool,
            Expression::FlatMinusEq(_, _, _) => ReturnType::Bool,
            Expression::FlatProductEq(_, _, _, _) => ReturnType::Bool,
29
            Expression::FlatWeightedSumLeq(_, _, _, _) => ReturnType::Bool,
            Expression::FlatWeightedSumGeq(_, _, _, _) => ReturnType::Bool,
            Expression::MinionPow(_, _, _, _) => ReturnType::Bool,
661341
            Expression::ToInt(_, _) => ReturnType::Int,
3169703
            Expression::SATInt(..) => ReturnType::Int,
            Expression::SatObjective(..) => ReturnType::Bool,
            Expression::PairwiseSum(_, _, _) => ReturnType::Int,
            Expression::PairwiseProduct(_, _, _) => ReturnType::Int,
            Expression::Defined(_, function) => {
2295
                let subject = function.return_type();
2295
                match subject {
2295
                    ReturnType::Function(domain, _) => ReturnType::Set(Box::new(*domain)),
                    _ => bug!(
                        "Invalid defined operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Range(_, function) => {
4735
                let subject = function.return_type();
4735
                match subject {
4735
                    ReturnType::Function(_, codomain) => ReturnType::Set(Box::new(*codomain)),
                    _ => bug!(
                        "Invalid range operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Image(_, function, _) => {
154309
                let subject = function.return_type();
154309
                match subject {
132269
                    ReturnType::Function(_, codomain) => *codomain,
12064
                    ReturnType::Permutation(inner) => *inner,
                    // A sequence is a function from int, so applying it is an image too.
9976
                    ReturnType::Sequence(inner) => *inner,
                    _ => bug!(
                        "Invalid image operation: expected the operand to be a function or permutation, got {self}: {subject}"
                    ),
                }
            }
            Expression::ImageSet(_, function, _) => {
87
                let subject = function.return_type();
87
                match subject {
87
                    ReturnType::Function(_, codomain) => ReturnType::Set(Box::new(*codomain)),
                    ReturnType::Permutation(inner) => ReturnType::Set(inner),
                    _ => bug!(
                        "Invalid imageSet operation: expected the operand to be a function or permutation, got {self}: {subject}"
                    ),
                }
            }
            Expression::PreImage(_, function, _) => {
95
                let subject = function.return_type();
95
                match subject {
95
                    ReturnType::Function(domain, _) => ReturnType::Set(Box::new(*domain)),
                    _ => bug!(
                        "Invalid preImage operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Restrict(_, function, new_domain) => {
37
                let subject = function.return_type();
37
                match subject {
                    ReturnType::Function(_, codomain) => {
37
                        ReturnType::Function(Box::new(new_domain.return_type()), codomain)
                    }
                    _ => bug!(
                        "Invalid preImage operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::Inverse(..) => ReturnType::Bool,
29
            Expression::PermInverse(_, p) => p.return_type(),
29
            Expression::Compose(_, g, _h) => g.return_type(),
464
            Expression::LexLt(..) => ReturnType::Bool,
406
            Expression::LexGt(..) => ReturnType::Bool,
24070
            Expression::LexLeq(..) => ReturnType::Bool,
870
            Expression::LexGeq(..) => ReturnType::Bool,
            Expression::FlatLexLt(..) => ReturnType::Bool,
            Expression::FlatLexLeq(..) => ReturnType::Bool,
            Expression::Active(..) => ReturnType::Bool,
            Expression::ToSet(_, other) => {
99
                let subject = other.return_type();
99
                match subject {
4
                    ReturnType::Matrix(domain) => ReturnType::Set(Box::new(*domain)),
4
                    ReturnType::MSet(domain) => ReturnType::Set(Box::new(*domain)),
                    ReturnType::Function(domain, codomain) => {
91
                        ReturnType::Set(Box::new(ReturnType::Tuple(vec![*domain, *codomain])))
                    }
                    ReturnType::Relation(domains) => {
                        ReturnType::Set(Box::new(ReturnType::Tuple(domains)))
                    }
                    _ => bug!(
                        "Invalid toSet operation: expected the operand to be a mset, matrix, relation, or function, got {self}: {subject}"
                    ),
                }
            }
            Expression::ToMSet(_, other) => {
29
                let subject = other.return_type();
29
                match subject {
                    ReturnType::Set(domain) => ReturnType::MSet(Box::new(*domain)),
                    ReturnType::Function(domain, codomain) => {
29
                        ReturnType::MSet(Box::new(ReturnType::Tuple(vec![*domain, *codomain])))
                    }
                    ReturnType::Relation(domains) => {
                        ReturnType::MSet(Box::new(ReturnType::Tuple(domains)))
                    }
                    _ => bug!(
                        "Invalid toMSet operation: expected the operand to be a set, relation, or function, got {self}: {subject}"
                    ),
                }
            }
            Expression::ToRelation(_, function) => {
58
                let subject = function.return_type();
58
                match subject {
                    ReturnType::Function(domain, codomain) => {
58
                        ReturnType::Relation(vec![*domain, *codomain])
                    }
                    _ => bug!(
                        "Invalid toRelation operation: expected the operand to be a function, got {self}: {subject}"
                    ),
                }
            }
            Expression::RelationProj(_, relation, projections) => {
                let subject = relation.return_type();
                match subject {
                    ReturnType::Relation(domains) => {
                        let new_doms = domains
                            .iter()
                            .zip(projections.iter())
                            .filter_map(|(domain, included)| {
                                if included.is_none() {
                                    // The domains corresponding to projections which are None remain in the relation
                                    Some(domain.clone())
                                } else {
                                    None
                                }
                            })
                            .collect();
                        ReturnType::Relation(new_doms)
                    }
                    _ => bug!(
                        "Invalid RelationProj operation: expected the operand to be a relation, got {self}: {subject}"
                    ),
                }
            }
            Expression::Pred(_, ev) => ev.return_type(),
32
            Expression::Succ(_, ev) => ev.return_type(),
24388
            Expression::Card(..) => ReturnType::Int,
            Expression::Subsequence(_, _, _) => ReturnType::Bool,
            Expression::Substring(_, _, _) => ReturnType::Bool,
            Expression::AttributeAsConstraint(_, _, _, _) => ReturnType::Bool,
        }
179431911
    }
}
impl Expression {
    /// Visit each direct `Expression` child by reference, without cloning.
1274769474
    pub fn for_each_expr_child<'a>(&'a self, f: &mut impl FnMut(&'a Expression)) {
1274769474
        match self {
            // Special Case
139958562
            Expression::AbstractLiteral(_, alit) => match alit {
                AbstractLiteral::Set(v) | AbstractLiteral::MSet(v) | AbstractLiteral::Tuple(v) => {
1062008
                    for expr in v {
2471177
                        f(expr);
                    }
                }
                AbstractLiteral::Partition(two_d_v) => {
1421
                    for part in two_d_v {
1653
                        for expr in part {
1769
                            f(expr);
                        }
                    }
                }
                AbstractLiteral::Matrix(v, _domain) => {
137100591
                    for expr in v {
1174155429
                        f(expr);
                    }
                }
                AbstractLiteral::Record(rs) => {
10643
                    for r in rs {
21286
                        f(&r.value);
                    }
                }
                AbstractLiteral::Sequence(v) => {
1452284
                    for expr in v {
4224368
                        f(expr);
                    }
                }
                AbstractLiteral::Function(vs) => {
348
                    for (a, b) in vs {
638
                        f(a);
638
                        f(b);
                    }
                }
                AbstractLiteral::Variant(v) => {
312678
                    f(&v.value);
                }
                AbstractLiteral::Relation(vs) => {
2233
                    for exprs in vs {
6641
                        for expr in exprs {
13398
                            f(expr);
                        }
                    }
                }
                AbstractLiteral::Permutation(cycles) => {
16356
                    for cycle in cycles {
16791
                        for expr in cycle {
49300
                            f(expr);
                        }
                    }
                }
            },
            Expression::Root(_, vs) => {
13813939
                for expr in vs {
236195086
                    f(expr);
                }
            }
            // Moo<Expression>
            Expression::DominanceRelation(_, m1)
            | Expression::TypeAnnotation(_, m1, _)
            | Expression::DomainAnnotation(_, m1, _)
            | Expression::ToInt(_, m1)
            | Expression::Abs(_, m1)
            | Expression::Sum(_, m1)
            | Expression::Product(_, m1)
            | Expression::Min(_, m1)
            | Expression::Max(_, m1)
            | Expression::Not(_, m1)
            | Expression::Or(_, m1)
            | Expression::And(_, m1)
            | Expression::Neg(_, m1)
            | Expression::PermInverse(_, m1)
            | Expression::Defined(_, m1)
            | Expression::AllDiff(_, m1)
            | Expression::SatAllDifferentComparisons(_, m1)
            | Expression::SmtDistinct(_, m1)
            | Expression::Factorial(_, m1)
            | Expression::Range(_, m1)
            | Expression::Participants(_, m1)
            | Expression::Parts(_, m1)
            | Expression::ToSet(_, m1)
            | Expression::ToMSet(_, m1)
            | Expression::ToRelation(_, m1)
            | Expression::Pred(_, m1)
            | Expression::Succ(_, m1)
            | Expression::Card(_, m1)
            | Expression::RecordField(_, m1, _)
            | Expression::Active(_, m1, _) => {
481050957
                f(m1);
            }
            // Moo<Expression> + Moo<Expression>
            Expression::Table(_, m1, m2)
            | Expression::NegativeTable(_, m1, m2)
            | Expression::ShortTable(_, m1, m2)
            | Expression::Bubble(_, m1, m2)
            | Expression::Imply(_, m1, m2)
            | Expression::Iff(_, m1, m2)
            | Expression::Difference(_, m1, m2)
            | Expression::Union(_, m1, m2)
            | Expression::In(_, m1, m2)
            | Expression::Intersect(_, m1, m2)
            | Expression::Supset(_, m1, m2)
            | Expression::SupsetEq(_, m1, m2)
            | Expression::Subset(_, m1, m2)
            | Expression::SubsetEq(_, m1, m2)
            | Expression::Eq(_, m1, m2)
            | Expression::Neq(_, m1, m2)
            | Expression::Geq(_, m1, m2)
            | Expression::Leq(_, m1, m2)
            | Expression::Gt(_, m1, m2)
            | Expression::Lt(_, m1, m2)
            | Expression::CatchUndef(_, m1, m2)
            | Expression::SafeDiv(_, m1, m2)
            | Expression::UnsafeDiv(_, m1, m2)
            | Expression::SafeMod(_, m1, m2)
            | Expression::UnsafeMod(_, m1, m2)
            | Expression::UnsafePow(_, m1, m2)
            | Expression::SafePow(_, m1, m2)
            | Expression::Minus(_, m1, m2)
            | Expression::PairwiseSum(_, m1, m2)
            | Expression::PairwiseProduct(_, m1, m2)
            | Expression::Image(_, m1, m2)
            | Expression::ImageSet(_, m1, m2)
            | Expression::PreImage(_, m1, m2)
            | Expression::Inverse(_, m1, m2)
            | Expression::Compose(_, m1, m2)
            | Expression::Restrict(_, m1, m2)
            | Expression::Apart(_, m1, m2)
            | Expression::Together(_, m1, m2)
            | Expression::Party(_, m1, m2)
            | Expression::LexLt(_, m1, m2)
            | Expression::LexLeq(_, m1, m2)
            | Expression::LexGt(_, m1, m2)
            | Expression::LexGeq(_, m1, m2)
            | Expression::Subsequence(_, m1, m2)
            | Expression::Substring(_, m1, m2) => {
243973917
                f(m1);
243973917
                f(m2);
            }
            // Moo<Expression> + Vec<Expression>
            Expression::UnsafeIndex(_, m, vs) | Expression::SafeIndex(_, m, vs) => {
107827336
                f(m);
107827336
                for v in vs {
120112605
                    f(v);
                }
            }
            // Moo<Expression> + Vec<Option<Expression>>
            Expression::UnsafeSlice(_, m, vs)
            | Expression::SafeSlice(_, m, vs)
            | Expression::RelationProj(_, m, vs) => {
4414428
                f(m);
4414428
                for e in vs.iter().flatten() {
4237093
                    f(e);
                }
            }
            // Moo<Expression> + Moo<Expression> + Moo<Expression>
            Expression::SatElement(_, m1, m2, m3)
            | Expression::AtLeast(_, m1, m2, m3)
            | Expression::AtMost(_, m1, m2, m3)
            | Expression::Gcc(_, m1, m2, m3)
            | Expression::GccWeak(_, m1, m2, m3) => {
3749961
                f(m1);
3749961
                f(m2);
3749961
                f(m3);
            }
            // Moo<Expression> + Moo<Expression> (two-arg globals)
            Expression::AllDifferentExcept(_, m1, m2)
            | Expression::ElementId(_, m1, m2)
            | Expression::IndexOf(_, m1, m2) => {
997243
                f(m1);
997243
                f(m2);
            }
            // Moo<Expression> + DomainPtr
            Expression::InDomain(_, m, _) => {
109155
                f(m);
            }
            // Option<Moo<Expression>> + Moo<Expression>
            Expression::Flatten(_, opt, m) => {
2779395
                if let Some(e) = opt {
                    f(e);
2779395
                }
2779395
                f(m);
            }
            // Moo<Expression> + AttrName + Option<Moo<Expression>>
            Expression::AttributeAsConstraint(_, target, _, val) => {
                f(target);
                if let Some(v) = val {
                    f(v);
                }
            }
            // Moo<Expression> + Atom
            Expression::MinionReify(_, m, _) | Expression::MinionReifyImply(_, m, _) => {
1725602
                f(m);
            }
            // Reference + Moo<Expression>
            Expression::AuxDeclaration(_, _, m) => {
13571224
                f(m);
            }
            // SATIntEncoding + Moo<Expression> + (i32, i32)
            Expression::SatObjective(_, _, m) | Expression::SATInt(_, _, m, _) => {
61896343
                f(m);
            }
            // No Expression children
            Expression::Comprehension(_, _)
            | Expression::Atomic(_, _)
            | Expression::FromSolution(_, _)
            | Expression::Metavar(_, _)
            | Expression::FlatAbsEq(_, _, _)
            | Expression::FlatMinusEq(_, _, _)
            | Expression::FlatProductEq(_, _, _, _)
            | Expression::MinionDivEqUndefZero(_, _, _, _)
            | Expression::MinionModuloEqUndefZero(_, _, _, _)
            | Expression::MinionPow(_, _, _, _)
            | Expression::FlatAllDiff(_, _)
            | Expression::FlatTable(..)
            | Expression::FlatShortTable(..)
            | Expression::FlatMinEq(_, _, _)
            | Expression::FlatSumGeq(_, _, _)
            | Expression::FlatSumLeq(_, _, _)
            | Expression::FlatIneq(_, _, _, _)
            | Expression::FlatWatchedLiteral(_, _, _)
            | Expression::FlatWeightedSumLeq(_, _, _, _)
            | Expression::FlatWeightedSumGeq(_, _, _, _)
            | Expression::MinionWInIntervalSet(_, _, _)
            | Expression::MinionWInSet(_, _, _)
            | Expression::MinionElementOne(_, _, _, _)
            | Expression::FlatLexLt(_, _, _)
198901412
            | Expression::FlatLexLeq(_, _, _) => {}
        }
1274769474
    }
    /// Visits this expression and all of its expression descendants by reference.
1315176
    pub fn for_each_expression<'a>(&'a self, f: &mut impl FnMut(&'a Expression)) {
1315176
        f(self);
1315176
        self.for_each_expr_child(&mut |child| child.for_each_expression(f));
1315176
    }
    /// Returns whether this expression or any expression below it satisfies `predicate`.
    ///
    /// Unlike [`Uniplate::universe`], this does not construct an owned copy of the traversed tree.
14494134
    pub fn any_expression(&self, mut predicate: impl FnMut(&Expression) -> bool) -> bool {
42914077
        fn visit(expr: &Expression, predicate: &mut impl FnMut(&Expression) -> bool) -> bool {
42914077
            if predicate(expr) {
1075764
                return true;
41838313
            }
41838313
            let mut found = false;
41838313
            expr.for_each_expr_child(&mut |child| {
28455353
                if !found {
28419943
                    found = visit(child, predicate);
35410
                }
28455353
            });
41838313
            found
42914077
        }
14494134
        visit(self, &mut predicate)
14494134
    }
    /// Returns whether any expression strictly below this one satisfies `predicate`.
1996781
    pub fn any_expression_descendant(
1996781
        &self,
1996781
        mut predicate: impl FnMut(&Expression) -> bool,
1996781
    ) -> bool {
1996781
        let mut found = false;
4847496
        self.for_each_expr_child(&mut |child| {
4847496
            if !found {
4823194
                found = child.any_expression(&mut predicate);
24302
            }
4847496
        });
1996781
        found
1996781
    }
}
impl Expression {
    /// Invalidates the cached content hash on this expression only.
3209989721
    pub(crate) fn invalidate_cached_content_hash(&self) {
3209989721
        let metadata = self.meta_ref();
3209989721
        metadata
3209989721
            .cached_content_hash
3209989721
            .store(NO_HASH, Ordering::Relaxed);
3209989721
    }
    /// Returns the cached expression content hash, computing and storing it when absent.
18575912
    pub(crate) fn cached_content_hash(&self) -> u64 {
18575912
        let stored = self.meta_ref().cached_content_hash.load(Ordering::Relaxed);
18575912
        if stored != NO_HASH {
13463508
            HASH_HITS.fetch_add(1, Ordering::Relaxed);
13463508
            return stored;
5112404
        }
5112404
        HASH_MISSES.fetch_add(1, Ordering::Relaxed);
5112404
        self.calculate_content_hash()
18575912
    }
    /// Computes an expression content hash from precomputed child node hashes.
    ///
    /// Child hashes must be supplied in the same order as [`Uniplate::children`] for this
    /// expression.
    #[allow(unused_variables)]
5112404
    pub(crate) fn content_hash_from_child_hashes(
5112404
        &self,
5112404
        child_hashes: &mut impl Iterator<Item = u64>,
5112404
    ) -> u64 {
1740240
        fn child_hash(child_hashes: &mut impl Iterator<Item = u64>) -> u64 {
1740240
            child_hashes
1740240
                .next()
1740240
                .expect("expression content hash missing child hash")
1740240
        }
5112404
        let mut hasher = DefaultHasher::new();
5112404
        std::mem::discriminant(self).hash(&mut hasher);
5112404
        match self {
            // Special Case
636668
            Expression::AbstractLiteral(_, alit) => match alit {
                AbstractLiteral::Set(v)
                | AbstractLiteral::MSet(v)
                | AbstractLiteral::Tuple(v)
                | AbstractLiteral::Sequence(v) => {
348816
                    for expr in v {
785303
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Matrix(v, domain) => {
262390
                    domain.hash(&mut hasher);
262390
                    for expr in v {
772429
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Record(rs) => {
6409
                    for r in rs {
12818
                        r.name.hash(&mut hasher);
12818
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Function(vs) => {
290
                    for (a, b) in vs {
522
                        child_hash(child_hashes).hash(&mut hasher);
522
                        child_hash(child_hashes).hash(&mut hasher);
                    }
                }
                AbstractLiteral::Variant(v) => {
58
                    v.name.hash(&mut hasher);
58
                    child_hash(child_hashes).hash(&mut hasher);
                }
                AbstractLiteral::Relation(v) => {
2233
                    for exprs in v {
6641
                        for expr in exprs {
13398
                            child_hash(child_hashes).hash(&mut hasher);
                        }
                    }
                }
                AbstractLiteral::Partition(v) => {
116
                    for exprs in v {
348
                        for expr in exprs {
464
                            child_hash(child_hashes).hash(&mut hasher);
                        }
                    }
                }
                AbstractLiteral::Permutation(v) => {
16356
                    for exprs in v {
16791
                        for expr in exprs {
49300
                            child_hash(child_hashes).hash(&mut hasher);
                        }
                    }
                }
            },
            Expression::Root(_, vs) => {
2
                for expr in vs {
2
                    child_hash(child_hashes).hash(&mut hasher);
                }
            }
            // Moo<Expression>
            Expression::DominanceRelation(_, m1)
            | Expression::ToInt(_, m1)
            | Expression::Abs(_, m1)
            | Expression::Sum(_, m1)
            | Expression::Product(_, m1)
            | Expression::Min(_, m1)
            | Expression::Max(_, m1)
            | Expression::Not(_, m1)
            | Expression::Or(_, m1)
            | Expression::And(_, m1)
            | Expression::Neg(_, m1)
            | Expression::PermInverse(_, m1)
            | Expression::Defined(_, m1)
            | Expression::AllDiff(_, m1)
            | Expression::SatAllDifferentComparisons(_, m1)
            | Expression::SmtDistinct(_, m1)
            | Expression::Factorial(_, m1)
            | Expression::Participants(_, m1)
            | Expression::Parts(_, m1)
            | Expression::Range(_, m1)
            | Expression::ToSet(_, m1)
            | Expression::ToMSet(_, m1)
            | Expression::ToRelation(_, m1)
            | Expression::Pred(_, m1)
            | Expression::Succ(_, m1)
            | Expression::Card(_, m1) => {
43075
                child_hash(child_hashes).hash(&mut hasher);
            }
            Expression::TypeAnnotation(_, m1, domain) => {
                child_hash(child_hashes).hash(&mut hasher);
                domain.hash(&mut hasher);
            }
            Expression::DomainAnnotation(_, m1, domain) => {
                child_hash(child_hashes).hash(&mut hasher);
                domain.hash(&mut hasher);
            }
            // Moo<Expression> + Moo<Expression>
            Expression::Table(_, m1, m2)
            | Expression::NegativeTable(_, m1, m2)
            | Expression::ShortTable(_, m1, m2)
            | Expression::Bubble(_, m1, m2)
            | Expression::Imply(_, m1, m2)
            | Expression::Iff(_, m1, m2)
            | Expression::Difference(_, m1, m2)
            | Expression::Union(_, m1, m2)
            | Expression::In(_, m1, m2)
            | Expression::Intersect(_, m1, m2)
            | Expression::Supset(_, m1, m2)
            | Expression::SupsetEq(_, m1, m2)
            | Expression::Subset(_, m1, m2)
            | Expression::SubsetEq(_, m1, m2)
            | Expression::Eq(_, m1, m2)
            | Expression::Neq(_, m1, m2)
            | Expression::Geq(_, m1, m2)
            | Expression::Leq(_, m1, m2)
            | Expression::Gt(_, m1, m2)
            | Expression::Lt(_, m1, m2)
            | Expression::Apart(_, m1, m2)
            | Expression::Together(_, m1, m2)
            | Expression::Party(_, m1, m2)
            | Expression::CatchUndef(_, m1, m2)
            | Expression::SafeDiv(_, m1, m2)
            | Expression::UnsafeDiv(_, m1, m2)
            | Expression::SafeMod(_, m1, m2)
            | Expression::UnsafeMod(_, m1, m2)
            | Expression::UnsafePow(_, m1, m2)
            | Expression::SafePow(_, m1, m2)
            | Expression::Minus(_, m1, m2)
            | Expression::PairwiseSum(_, m1, m2)
            | Expression::PairwiseProduct(_, m1, m2)
            | Expression::Image(_, m1, m2)
            | Expression::ImageSet(_, m1, m2)
            | Expression::PreImage(_, m1, m2)
            | Expression::Inverse(_, m1, m2)
            | Expression::Compose(_, m1, m2)
            | Expression::Restrict(_, m1, m2)
            | Expression::LexLt(_, m1, m2)
            | Expression::LexLeq(_, m1, m2)
            | Expression::LexGt(_, m1, m2)
            | Expression::LexGeq(_, m1, m2)
            | Expression::Subsequence(_, m1, m2)
            | Expression::Substring(_, m1, m2) => {
28954
                child_hash(child_hashes).hash(&mut hasher);
28954
                child_hash(child_hashes).hash(&mut hasher);
            }
            // Moo<Expression> + Vec<Expression>
            Expression::UnsafeIndex(_, m, vs) | Expression::SafeIndex(_, m, vs) => {
2146
                child_hash(child_hashes).hash(&mut hasher);
2146
                for v in vs {
2146
                    child_hash(child_hashes).hash(&mut hasher);
                }
            }
            // Moo<Expression> + Vec<Option<Expression>>
            Expression::UnsafeSlice(_, m, vs)
            | Expression::SafeSlice(_, m, vs)
            | Expression::RelationProj(_, m, vs) => {
                child_hash(child_hashes).hash(&mut hasher);
                for v in vs {
                    match v {
                        Some(e) => child_hash(child_hashes).hash(&mut hasher),
                        None => 0u64.hash(&mut hasher),
                    }
                }
            }
            // Moo<Expression> + Moo<Expression> + Moo<Expression>
            Expression::SatElement(_, m1, m2, m3)
            | Expression::AtLeast(_, m1, m2, m3)
            | Expression::AtMost(_, m1, m2, m3)
            | Expression::Gcc(_, m1, m2, m3)
            | Expression::GccWeak(_, m1, m2, m3) => {
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }
            // Moo<Expression> + Moo<Expression> (two-arg globals)
            Expression::AllDifferentExcept(_, m1, m2)
            | Expression::ElementId(_, m1, m2)
            | Expression::IndexOf(_, m1, m2) => {
                child_hash(child_hashes).hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }
            // Moo<Expression> + Name
            Expression::RecordField(_, m, n) | Expression::Active(_, m, n) => {
                child_hash(child_hashes).hash(&mut hasher);
                n.hash(&mut hasher);
            }
            // Moo<Expression> + DomainPtr
            Expression::InDomain(_, m, d) => {
                child_hash(child_hashes).hash(&mut hasher);
                d.hash(&mut hasher);
            }
            // Option<Moo<Expression>> + Moo<Expression>
            Expression::Flatten(_, opt, m) => {
                if let Some(e) = opt {
                    child_hash(child_hashes).hash(&mut hasher);
                }
                child_hash(child_hashes).hash(&mut hasher);
            }
            // Moo<Expression> + AttrName + Option<Moo<Expression>>
            Expression::AttributeAsConstraint(_, target, attr, val) => {
                child_hash(child_hashes).hash(&mut hasher);
                attr.hash(&mut hasher);
                if let Some(v) = val {
                    child_hash(child_hashes).hash(&mut hasher);
                }
            }
            // Moo<Expression> + Atom
            Expression::MinionReify(_, m, a) | Expression::MinionReifyImply(_, m, a) => {
120
                child_hash(child_hashes).hash(&mut hasher);
120
                a.hash(&mut hasher);
            }
            // Reference + Moo<Expression>
            Expression::AuxDeclaration(_, r, m) => {
                r.hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }
            // SATIntEncoding + Moo<Expression> + (i32, i32)
            Expression::SatObjective(_, minimise, _) => {
                minimise.hash(&mut hasher);
                child_hash(child_hashes).hash(&mut hasher);
            }
            Expression::SATInt(_, enc, m, bounds) => {
29
                enc.hash(&mut hasher);
29
                child_hash(child_hashes).hash(&mut hasher);
29
                bounds.hash(&mut hasher);
            }
            // Non-Expression Moo types - hash normally
40
            Expression::Comprehension(_, c) => c.hash(&mut hasher),
            // Leaf types - no Expression children
4399386
            Expression::Atomic(_, a) => a.hash(&mut hasher),
            Expression::FromSolution(_, a) => a.hash(&mut hasher),
            Expression::Metavar(_, u) => u.hash(&mut hasher),
            // Two Moo<Atom>
            Expression::FlatAbsEq(_, a1, a2) | Expression::FlatMinusEq(_, a1, a2) => {
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
            }
            // Three Moo<Atom>
            Expression::FlatProductEq(_, a1, a2, a3)
            | Expression::MinionDivEqUndefZero(_, a1, a2, a3)
            | Expression::MinionModuloEqUndefZero(_, a1, a2, a3)
            | Expression::MinionPow(_, a1, a2, a3) => {
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
                a3.hash(&mut hasher);
            }
            Expression::FlatShortTable(_, inputs, rows) => {
                inputs.hash(&mut hasher);
                rows.hash(&mut hasher);
            }
            Expression::FlatTable(_, inputs, rows, negative) => {
                inputs.hash(&mut hasher);
                rows.hash(&mut hasher);
                negative.hash(&mut hasher);
            }
            // Vec<Atom>
            Expression::FlatAllDiff(_, vs) => {
                for v in vs {
                    v.hash(&mut hasher);
                }
            }
            // Vec<Atom> + Atom
            Expression::FlatMinEq(_, vs, a)
            | Expression::FlatSumGeq(_, vs, a)
            | Expression::FlatSumLeq(_, vs, a) => {
                for v in vs {
                    v.hash(&mut hasher);
                }
                a.hash(&mut hasher);
            }
            // Moo<Atom> + Moo<Atom> + Box<Literal>
            Expression::FlatIneq(_, a1, a2, lit) => {
268
                a1.hash(&mut hasher);
268
                a2.hash(&mut hasher);
268
                lit.hash(&mut hasher);
            }
            // Reference + Literal
            Expression::FlatWatchedLiteral(_, r, l) => {
1716
                r.hash(&mut hasher);
1716
                l.hash(&mut hasher);
            }
            // Vec<Literal> + Vec<Atom> + Moo<Atom>
            Expression::FlatWeightedSumLeq(_, lits, atoms, a)
            | Expression::FlatWeightedSumGeq(_, lits, atoms, a) => {
                for l in lits {
                    l.hash(&mut hasher);
                }
                for at in atoms {
                    at.hash(&mut hasher);
                }
                a.hash(&mut hasher);
            }
            // Atom + Vec<i32>
            Expression::MinionWInIntervalSet(_, a, vs) | Expression::MinionWInSet(_, a, vs) => {
                a.hash(&mut hasher);
                for v in vs {
                    v.hash(&mut hasher);
                }
            }
            // Vec<Atom> + Moo<Atom> + Moo<Atom>
            Expression::MinionElementOne(_, vs, a1, a2) => {
                for v in vs {
                    v.hash(&mut hasher);
                }
                a1.hash(&mut hasher);
                a2.hash(&mut hasher);
            }
            // Vec<Atom> + Vec<Atom>
            Expression::FlatLexLt(_, v1, v2) | Expression::FlatLexLeq(_, v1, v2) => {
                for v in v1 {
                    v.hash(&mut hasher);
                }
                for v in v2 {
                    v.hash(&mut hasher);
                }
            }
        };
5112404
        hasher.finish()
5112404
    }
    /// Computes an expression content hash that ignores metadata except for child content hashes.
5112404
    pub(crate) fn calculate_content_hash(&self) -> u64 {
5112404
        let mut hashes = Vec::new();
5112404
        self.for_each_expr_child(&mut |child| hashes.push(child.cached_content_hash()));
5112404
        let mut child_hashes = hashes.into_iter();
5112404
        let result = self.content_hash_from_child_hashes(&mut child_hashes);
5112404
        self.meta_ref()
5112404
            .cached_content_hash
5112404
            .store(result, Ordering::Relaxed);
5112404
        result
5112404
    }
}
#[cfg(test)]
mod tests {
    use crate::matrix_expr;
    use super::*;
    #[test]
1
    fn list_inspection_borrows_expression_elements_without_cloning_the_list() {
1
        let list = matrix_expr![
1
            Expression::from(Literal::Int(1)),
1
            Expression::from(Literal::Int(2))
        ];
1
        assert_eq!(list.list_len(), Some(2));
1
        assert!(list.is_list());
1
        assert!(matches!(list.unwrap_list_cow(), Some(Cow::Borrowed(_))));
1
    }
    #[test]
1
    fn list_inspection_materialises_literal_elements_only_when_they_are_requested() {
1
        let list = Expression::Atomic(
1
            Metadata::new(),
1
            Atom::Literal(Literal::AbstractLiteral(
1
                AbstractLiteral::matrix_implied_indices(vec![Literal::Int(1), Literal::Int(2)]),
1
            )),
1
        );
1
        assert_eq!(list.list_len(), Some(2));
1
        assert!(list.is_list());
1
        assert!(matches!(list.unwrap_list_cow(), Some(Cow::Owned(_))));
1
        assert_eq!(
1
            list.unwrap_list_cow().map(Cow::into_owned),
1
            list.unwrap_list()
        );
1
    }
    #[test]
1
    fn list_length_looks_through_annotations() {
1
        let list = Expression::DomainAnnotation(
1
            Metadata::new(),
1
            Moo::new(matrix_expr![Expression::from(Literal::Int(1))]),
1
            Domain::int(vec![Range::Bounded(0, 1)]),
1
        );
1
        assert_eq!(list.list_len(), Some(1));
1
        assert!(matches!(list.unwrap_list_cow(), Some(Cow::Borrowed(_))));
1
    }
}