1#![allow(
30 clippy::many_single_char_names,
31 reason = "ports keep short operand names (a, b, s, t, x, y)"
32)]
33
34use std::cmp::Ordering;
35
36use crate::atom::Atom;
37use crate::ctx::{Ctx, IntMode, ValueOrder};
38use crate::enumerate::{MAX_ENUMERATION, quiet_size};
39use crate::error::{ErrorKind, Result, ValueError};
40use crate::stream::{Elems, slice_stream, stream};
41use crate::value::{Fcn, FcnRepr, HASH_ELEMENT_LIMIT, K_SET, Set, SetRepr, Value, mix2, set_hash};
42
43fn quiet_ctx(order: ValueOrder) -> Ctx {
44 Ctx {
45 int_mode: IntMode::Big,
46 order,
47 }
48}
49
50#[derive(Clone, Copy, PartialEq, Eq)]
55enum Class {
56 Interval,
57 Finite,
58 Structural,
59}
60
61fn class(s: &Set) -> Class {
62 match s.repr() {
63 SetRepr::Interval(..) => Class::Interval,
64 SetRepr::Enum => Class::Finite,
65 SetRepr::Nat | SetRepr::Int | SetRepr::Strings => Class::Structural,
66 _ => match quiet_size(s) {
67 Some(n) if n <= u128::from(MAX_ENUMERATION) => Class::Finite,
68 _ => Class::Structural,
69 },
70 }
71}
72
73fn quiet_stream(s: &Set, order: ValueOrder) -> Option<Elems> {
76 if s.order() == order {
77 return stream(s, quiet_ctx(order), false).ok();
78 }
79 let mut v: Vec<Value> = stream(s, quiet_ctx(s.order()), false).ok()?.collect();
80 v.sort_by(|a, b| total_cmp(a, b, order));
81 Some(slice_stream(v.into()))
82}
83
84fn interval_empty(s: &Set) -> bool {
85 s.as_interval().is_some_and(|(lo, hi)| hi < lo)
86}
87
88pub(crate) fn compute_set_hash(s: &Set) -> u64 {
90 match class(s) {
91 Class::Interval | Class::Finite => match quiet_size(s) {
92 Some(n) if n > HASH_ELEMENT_LIMIT => set_hash(std::iter::empty(), n),
93 Some(n) => match stream(s, quiet_ctx(s.order()), false) {
94 Ok(e) => set_hash(e.map(|v| v.hash64()), n),
95 Err(_) => structural_hash(s),
96 },
97 None => structural_hash(s),
98 },
99 Class::Structural => structural_hash(s),
100 }
101}
102
103fn structural_hash(s: &Set) -> u64 {
104 let seq = |init: u64, vals: &mut dyn Iterator<Item = &Value>| {
105 vals.fold(init, |h, v| mix2(h, v.hash64()))
106 };
107 let h = match s.repr() {
108 SetRepr::Nat => 1,
109 SetRepr::Int => 2,
110 SetRepr::Strings => 3,
111 SetRepr::Seq(r) => mix2(4, r.hash64()),
112 SetRepr::Subset(b) => mix2(5, b.hash64()),
113 SetRepr::FcnSet(d, r) => mix2(mix2(6, d.hash64()), r.hash64()),
114 SetRepr::RcdSet(fs) => fs
115 .iter()
116 .fold(7, |h, (a, v)| mix2(mix2(h, a.text_hash()), v.hash64())),
117 SetRepr::Product(fs) => seq(8, &mut fs.iter()),
118 SetRepr::Raw(e) => seq(9, &mut e.iter()),
119 SetRepr::Deferred(d) => seq(mix2(10, d.kind() as u64), &mut d.key().iter()),
120 SetRepr::Interval(lo, hi) => mix2(
121 mix2(11, Value::int(lo.clone()).hash64()),
122 Value::int(hi.clone()).hash64(),
123 ),
124 SetRepr::Enum => 12,
125 };
126 mix2(K_SET ^ 0xdead_beef, h)
127}
128
129fn structural_eq(a: &Set, b: &Set) -> bool {
131 match (a.repr(), b.repr()) {
132 (SetRepr::Nat, SetRepr::Nat)
133 | (SetRepr::Int, SetRepr::Int)
134 | (SetRepr::Strings, SetRepr::Strings) => true,
135 (SetRepr::Seq(x), SetRepr::Seq(y)) | (SetRepr::Subset(x), SetRepr::Subset(y)) => x == y,
136 (SetRepr::FcnSet(d1, r1), SetRepr::FcnSet(d2, r2)) => d1 == d2 && r1 == r2,
137 (SetRepr::RcdSet(f1), SetRepr::RcdSet(f2)) => {
138 f1.len() == f2.len() && f1.iter().zip(f2.iter()).all(|(p, q)| p == q)
139 }
140 (SetRepr::Product(f1), SetRepr::Product(f2)) | (SetRepr::Raw(f1), SetRepr::Raw(f2)) => {
141 f1 == f2
142 }
143 (SetRepr::Interval(l1, h1), SetRepr::Interval(l2, h2)) => l1 == l2 && h1 == h2,
144 (SetRepr::Deferred(p), SetRepr::Deferred(q)) => p.kind() == q.kind() && p.key() == q.key(),
145 _ => false,
146 }
147}
148
149fn structural_rank(r: &SetRepr) -> u8 {
150 match r {
151 SetRepr::Nat => 0,
152 SetRepr::Int => 1,
153 SetRepr::Strings => 2,
154 SetRepr::Seq(_) => 3,
155 SetRepr::Subset(_) => 4,
156 SetRepr::FcnSet(..) => 5,
157 SetRepr::RcdSet(_) => 6,
158 SetRepr::Product(_) => 7,
159 SetRepr::Interval(..) => 8,
160 SetRepr::Enum => 9,
161 SetRepr::Raw(_) => 10,
162 SetRepr::Deferred(_) => 11,
163 }
164}
165
166fn seq_cmp(a: &[Value], b: &[Value], order: ValueOrder) -> Ordering {
167 a.len().cmp(&b.len()).then_with(|| {
168 for (x, y) in a.iter().zip(b) {
169 let c = total_cmp(x, y, order);
170 if c != Ordering::Equal {
171 return c;
172 }
173 }
174 Ordering::Equal
175 })
176}
177
178fn structural_cmp(a: &Set, b: &Set, order: ValueOrder) -> Ordering {
180 let (ra, rb) = (structural_rank(a.repr()), structural_rank(b.repr()));
181 if ra != rb {
182 return ra.cmp(&rb);
183 }
184 match (a.repr(), b.repr()) {
185 (SetRepr::Seq(x), SetRepr::Seq(y)) | (SetRepr::Subset(x), SetRepr::Subset(y)) => {
186 total_cmp(x, y, order)
187 }
188 (SetRepr::FcnSet(d1, r1), SetRepr::FcnSet(d2, r2)) => {
189 total_cmp(d1, d2, order).then_with(|| total_cmp(r1, r2, order))
190 }
191 (SetRepr::RcdSet(f1), SetRepr::RcdSet(f2)) => f1.len().cmp(&f2.len()).then_with(|| {
192 for ((n1, s1), (n2, s2)) in f1.iter().zip(f2.iter()) {
193 let c = n1
194 .cmp_with(n2, order)
195 .then_with(|| total_cmp(s1, s2, order));
196 if c != Ordering::Equal {
197 return c;
198 }
199 }
200 Ordering::Equal
201 }),
202 (SetRepr::Product(f1), SetRepr::Product(f2)) | (SetRepr::Raw(f1), SetRepr::Raw(f2)) => {
203 seq_cmp(f1, f2, order)
204 }
205 (SetRepr::Interval(l1, h1), SetRepr::Interval(l2, h2)) => {
206 l1.cmp(l2).then_with(|| h1.cmp(h2))
207 }
208 (SetRepr::Deferred(p), SetRepr::Deferred(q)) => (p.kind() as u8)
209 .cmp(&(q.kind() as u8))
210 .then_with(|| seq_cmp(&p.key(), &q.key(), order)),
211 _ => Ordering::Equal,
212 }
213}
214
215fn materialized_ref(s: &Set) -> Option<&[Value]> {
223 match s.repr() {
224 SetRepr::Enum | SetRepr::Raw(_) | SetRepr::Deferred(_) => {
225 s.quiet_elements(quiet_ctx(s.order())).ok()?;
226 s.0.elems.get().map(|e| &**e)
227 }
228 _ => None,
229 }
230}
231
232fn scalar_eq(a: &Value, b: &Value) -> Option<bool> {
234 Some(match (a, b) {
235 (Value::Bool(p), Value::Bool(q)) => p == q,
236 (Value::Int(p), Value::Int(q)) => p == q,
237 (Value::Int(_) | Value::BigInt(_), Value::Int(_) | Value::BigInt(_)) => {
238 a.as_int() == b.as_int()
239 }
240 (Value::Str(p), Value::Str(q)) | (Value::Model(p), Value::Model(q)) => p == q,
241 (Value::Fcn(f), Value::Fcn(g)) => {
242 if f.ptr_eq(g) {
243 return Some(true);
244 }
245 if f.0.hash != g.0.hash {
246 return Some(false);
247 }
248 return None;
249 }
250 (Value::Set(_), Value::Set(_)) => return None,
251 _ => false,
252 })
253}
254
255pub(crate) fn semantic_eq(a: &Value, b: &Value) -> bool {
259 if let Some(r) = scalar_eq(a, b) {
260 return r;
261 }
262 let mut work: Vec<(&Value, &Value)> = vec![(a, b)];
263 while let Some((x, y)) = work.pop() {
264 let equal = match scalar_eq(x, y) {
265 Some(r) => r,
266 None => match (x, y) {
267 (Value::Fcn(f), Value::Fcn(g)) => fcn_eq_step(f, g, &mut work),
268 (Value::Set(s), Value::Set(t)) => set_eq_step(s, t, &mut work),
269 _ => false,
270 },
271 };
272 if !equal {
273 return false;
274 }
275 }
276 true
277}
278
279fn fcn_eq_step<'a>(f: &'a Fcn, g: &'a Fcn, work: &mut Vec<(&'a Value, &'a Value)>) -> bool {
280 if f.len() != g.len() || f.kind() != g.kind() {
281 return false;
282 }
283 match (&f.0.repr, &g.0.repr) {
284 (FcnRepr::Tuple(a), FcnRepr::Tuple(b)) => work.extend(a.iter().zip(b.iter())),
285 (FcnRepr::Record(a), FcnRepr::Record(b)) => {
286 if f.order() == g.order() {
287 for ((n, v), (m, w)) in a.iter().zip(b.iter()) {
288 if n != m {
289 return false;
290 }
291 work.push((v, w));
292 }
293 } else {
294 for (n, v) in a {
295 match b.iter().find(|(m, _)| m == n) {
296 Some((_, w)) => work.push((v, w)),
297 None => return false,
298 }
299 }
300 }
301 }
302 (FcnRepr::General(a), FcnRepr::General(b)) => {
303 if f.order() == g.order() {
304 for ((d1, v1), (d2, v2)) in a.iter().zip(b.iter()) {
305 work.push((d1, d2));
306 work.push((v1, v2));
307 }
308 } else {
309 for (d, v) in a {
310 match b.iter().find(|(e, _)| *e == d) {
311 Some((_, w)) => work.push((v, w)),
312 None => return false,
313 }
314 }
315 }
316 }
317 _ => return false,
318 }
319 true
320}
321
322fn set_eq_step<'a>(s: &'a Set, t: &'a Set, work: &mut Vec<(&'a Value, &'a Value)>) -> bool {
323 if s.ptr_eq(t) {
324 return true;
325 }
326 if let (Some((l1, h1)), Some((l2, h2))) = (s.as_interval(), t.as_interval()) {
327 return (h1 < l1 && h2 < l2) || (l1 == l2 && h1 == h2);
328 }
329 let (cs, ct) = (class(s), class(t));
330 match (cs == Class::Structural, ct == Class::Structural) {
331 (true, true) => return structural_eq(s, t),
332 (true, false) | (false, true) => return false,
333 (false, false) => {}
334 }
335 if quiet_size(s) != quiet_size(t) || s.hash64() != t.hash64() {
336 return false;
337 }
338 if s.order() == t.order()
339 && let (Some(a), Some(b)) = (materialized_ref(s), materialized_ref(t))
340 {
341 work.extend(a.iter().zip(b.iter()));
342 return true;
343 }
344 let order = s.order();
345 match (quiet_stream(s, order), quiet_stream(t, order)) {
346 (Some(a), Some(b)) => a.zip(b).all(|(x, y)| semantic_eq(&x, &y)),
347 _ => false,
348 }
349}
350
351pub(crate) fn rank(v: &Value) -> u8 {
356 match v {
357 Value::Model(_) => 0,
358 Value::Bool(_) => 1,
359 Value::Int(_) | Value::BigInt(_) => 2,
360 Value::Str(_) => 3,
361 Value::Set(s) => {
362 if class(s) == Class::Structural {
363 6
364 } else {
365 4
366 }
367 }
368 Value::Fcn(_) => 5,
369 }
370}
371
372impl Value {
373 #[must_use]
392 pub fn cmp_with(&self, other: &Self, order: ValueOrder) -> Ordering {
393 total_cmp(self, other, order)
394 }
395}
396
397const SELECT_BEFORE_SORT: usize = 4;
399
400pub(crate) fn for_each_sorted<'a, T>(
405 elems: &[&'a Value],
406 order: ValueOrder,
407 mut visit: impl FnMut(&'a Value) -> Result<Option<T>>,
408) -> Result<Option<T>> {
409 let mut rest: Vec<&'a Value> = elems.to_vec();
410 let mut selected = 0usize;
411 while !rest.is_empty() {
412 if selected == SELECT_BEFORE_SORT {
413 rest.sort_unstable_by(|a, b| total_cmp(a, b, order));
414 for x in rest {
415 if let Some(t) = visit(x)? {
416 return Ok(Some(t));
417 }
418 }
419 return Ok(None);
420 }
421 let mut min = 0;
422 for i in 1..rest.len() {
423 if total_cmp(rest[i], rest[min], order) == Ordering::Less {
424 min = i;
425 }
426 }
427 if let Some(t) = visit(rest.swap_remove(min))? {
428 return Ok(Some(t));
429 }
430 selected += 1;
431 }
432 Ok(None)
433}
434
435fn cmp_distinct_set(elems: &[&Value], other: &Value, order: ValueOrder) -> Option<Ordering> {
438 let Value::Set(t) = other else {
439 return None;
440 };
441 if !matches!(t.repr(), SetRepr::Enum | SetRepr::Raw(_)) || class(t) != Class::Finite {
444 return None;
445 }
446 let n = u128::try_from(elems.len()).ok()?;
447 if n > u128::from(MAX_ENUMERATION) {
448 return None;
449 }
450 let c = n.cmp(&quiet_size(t)?);
451 if c != Ordering::Equal {
452 return Some(c);
453 }
454 let mut theirs = quiet_stream(t, order)?;
455 let mut exhausted = false;
456 let decided = for_each_sorted(elems, order, |x| {
457 let Some(y) = theirs.next() else {
458 exhausted = true;
459 return Ok(Some(Ordering::Equal));
460 };
461 let c = total_cmp(x, &y, order);
462 Ok((c != Ordering::Equal).then_some(c))
463 })
464 .ok()?;
465 if exhausted {
466 return None;
467 }
468 Some(decided.unwrap_or(Ordering::Equal))
469}
470
471impl Value {
472 #[must_use]
491 pub fn cmp_distinct_set(
492 elems: &[&Value],
493 other: &Value,
494 order: ValueOrder,
495 ) -> Option<Ordering> {
496 cmp_distinct_set(elems, other, order)
497 }
498
499 #[must_use]
508 pub fn elements_comparable(elems: &[Value]) -> bool {
509 all_comparable(elems)
510 }
511}
512
513fn pairs_in(f: &Fcn, order: ValueOrder) -> crate::function_domain::OrderedFcn<'_> {
515 crate::function_domain::OrderedFcn::new(f, order)
516}
517
518pub(crate) fn scalar_cmp(a: &Value, b: &Value, order: ValueOrder) -> Option<Ordering> {
521 match (a, b) {
522 (Value::Bool(p), Value::Bool(q)) => Some(p.cmp(q)),
523 (Value::Int(p), Value::Int(q)) => Some(p.cmp(q)),
524 (Value::Str(p), Value::Str(q)) | (Value::Model(p), Value::Model(q)) => {
525 Some(p.cmp_with(q, order))
526 }
527 (Value::Set(_) | Value::Fcn(_), _) | (_, Value::Set(_) | Value::Fcn(_)) => None,
528 _ => {
529 let (ra, rb) = (rank(a), rank(b));
530 if ra == rb {
531 Some(a.as_int().cmp(&b.as_int()))
532 } else {
533 Some(ra.cmp(&rb))
534 }
535 }
536 }
537}
538
539pub(crate) fn total_cmp(a: &Value, b: &Value, order: ValueOrder) -> Ordering {
540 if let Some(c) = scalar_cmp(a, b, order) {
541 return c;
542 }
543 if let (Value::Fcn(f), Value::Fcn(g)) = (a, b)
544 && let Some(c) = flat_fcn_cmp(f, g, order)
545 {
546 return c;
547 }
548 let mut work: Vec<(&Value, &Value)> = vec![(a, b)];
549 while let Some((x, y)) = work.pop() {
550 let c = cmp_step(x, y, order, &mut work);
551 if c != Ordering::Equal {
552 return c;
553 }
554 }
555 Ordering::Equal
556}
557
558fn flat_fcn_cmp(f: &Fcn, g: &Fcn, order: ValueOrder) -> Option<Ordering> {
562 if f.ptr_eq(g) {
563 return Some(Ordering::Equal);
564 }
565 let c = f.len().cmp(&g.len());
566 if c != Ordering::Equal {
567 return Some(c);
568 }
569 let values = |pairs: &mut dyn Iterator<Item = (&Value, &Value)>| {
570 for (v, w) in pairs {
571 let c = scalar_cmp(v, w, order)?;
572 if c != Ordering::Equal {
573 return Some(c);
574 }
575 }
576 Some(Ordering::Equal)
577 };
578 match (&f.0.repr, &g.0.repr) {
579 (FcnRepr::Tuple(a), FcnRepr::Tuple(b)) => values(&mut a.iter().zip(b.iter())),
580 (FcnRepr::Record(a), FcnRepr::Record(b)) if f.order() == order && g.order() == order => {
581 for ((n, _), (m, _)) in a.iter().zip(b.iter()) {
582 let c = n.cmp_with(m, order);
583 if c != Ordering::Equal {
584 return Some(c);
585 }
586 }
587 values(&mut a.iter().zip(b.iter()).map(|((_, v), (_, w))| (v, w)))
588 }
589 _ => None,
590 }
591}
592
593fn cmp_step<'a>(
596 x: &'a Value,
597 y: &'a Value,
598 order: ValueOrder,
599 work: &mut Vec<(&'a Value, &'a Value)>,
600) -> Ordering {
601 if let Some(c) = scalar_cmp(x, y, order) {
602 return c;
603 }
604 let (ra, rb) = (rank(x), rank(y));
605 if ra != rb {
606 return ra.cmp(&rb);
607 }
608 match (x, y) {
609 (Value::Fcn(f), Value::Fcn(g)) => fcn_cmp_step(f, g, order, work),
610 (Value::Set(s), Value::Set(t)) => set_cmp_step(s, t, ra, order, work),
611 _ => Ordering::Equal,
612 }
613}
614
615fn fcn_cmp_step<'a>(
616 f: &'a Fcn,
617 g: &'a Fcn,
618 order: ValueOrder,
619 work: &mut Vec<(&'a Value, &'a Value)>,
620) -> Ordering {
621 if f.ptr_eq(g) {
622 return Ordering::Equal;
623 }
624 let c = f.len().cmp(&g.len());
625 if c != Ordering::Equal {
626 return c;
627 }
628 let same_order = f.order() == order && g.order() == order;
629 match (&f.0.repr, &g.0.repr) {
630 (FcnRepr::Tuple(a), FcnRepr::Tuple(b)) => {
632 work.extend(a.iter().zip(b.iter()).rev());
633 Ordering::Equal
634 }
635 (FcnRepr::Record(a), FcnRepr::Record(b)) if same_order => {
636 for ((n, _), (m, _)) in a.iter().zip(b.iter()) {
637 let c = n.cmp_with(m, order);
638 if c != Ordering::Equal {
639 return c;
640 }
641 }
642 work.extend(a.iter().zip(b.iter()).rev().map(|((_, v), (_, w))| (v, w)));
643 Ordering::Equal
644 }
645 (FcnRepr::General(a), FcnRepr::General(b)) if same_order => {
646 work.extend(a.iter().zip(b.iter()).rev().map(|((_, v), (_, w))| (v, w)));
647 work.extend(a.iter().zip(b.iter()).rev().map(|((d, _), (e, _))| (d, e)));
648 Ordering::Equal
649 }
650 _ => {
652 let (p, q) = (pairs_in(f, order), pairs_in(g, order));
653 for ((d1, _), (d2, _)) in p.iter().zip(q.iter()) {
654 let c = total_cmp(&d1, &d2, order);
655 if c != Ordering::Equal {
656 return c;
657 }
658 }
659 for ((_, v1), (_, v2)) in p.iter().zip(q.iter()) {
660 let c = total_cmp(v1, v2, order);
661 if c != Ordering::Equal {
662 return c;
663 }
664 }
665 Ordering::Equal
666 }
667 }
668}
669
670fn set_cmp_step<'a>(
671 s: &'a Set,
672 t: &'a Set,
673 rank: u8,
674 order: ValueOrder,
675 work: &mut Vec<(&'a Value, &'a Value)>,
676) -> Ordering {
677 if s.ptr_eq(t) {
678 return Ordering::Equal;
679 }
680 if rank == 6 {
681 return structural_cmp(s, t, order);
682 }
683 let c = quiet_size(s).cmp(&quiet_size(t));
684 if c != Ordering::Equal {
685 return c;
686 }
687 if let (Some((l1, _)), Some((l2, _))) = (s.as_interval(), t.as_interval()) {
688 if interval_empty(s) {
689 return Ordering::Equal;
690 }
691 return l1.cmp(l2);
692 }
693 if s.order() == order
694 && t.order() == order
695 && let (Some(a), Some(b)) = (materialized_ref(s), materialized_ref(t))
696 {
697 work.extend(a.iter().zip(b.iter()).rev());
698 return Ordering::Equal;
699 }
700 match (quiet_stream(s, order), quiet_stream(t, order)) {
701 (Some(a), Some(b)) => {
702 for (x, y) in a.zip(b) {
703 let c = total_cmp(&x, &y, order);
704 if c != Ordering::Equal {
705 return c;
706 }
707 }
708 Ordering::Equal
709 }
710 _ => structural_cmp(s, t, order),
711 }
712}
713
714#[derive(Clone, PartialEq, Eq, Debug)]
721enum Shape {
722 Bottom,
723 AnyMv,
724 TypedMv(u16),
725 Bool,
726 Int,
727 Str,
728 Set(Box<Shape>),
729 Fcn(Box<Shape>, Box<Shape>),
730 Rcd(Vec<(Vec<Atom>, Vec<Shape>)>),
735 Conflict,
736}
737
738fn join_rcd(mut acc: Vec<(Vec<Atom>, Vec<Shape>)>, other: Vec<(Vec<Atom>, Vec<Shape>)>) -> Shape {
740 for (names, fields) in other {
741 if !join_fields(&mut acc, &names, |n| n, fields.into_iter()) {
742 return Shape::Conflict;
743 }
744 }
745 Shape::Rcd(acc)
746}
747
748fn join_fields<'a, N>(
753 acc: &mut Vec<(Vec<Atom>, Vec<Shape>)>,
754 names: &'a [N],
755 name: impl Fn(&'a N) -> &'a Atom,
756 fields: impl Iterator<Item = Shape>,
757) -> bool {
758 let same =
759 |n: &[Atom]| n.len() == names.len() && n.iter().zip(names).all(|(a, b)| a == name(b));
760 if let Some((_, mine)) = acc.iter_mut().find(|(n, _)| same(n)) {
761 for (field, theirs) in mine.iter_mut().zip(fields) {
762 let joined = join(std::mem::replace(field, Shape::Bottom), theirs);
763 if joined == Shape::Conflict {
764 return false;
765 }
766 *field = joined;
767 }
768 return true;
769 }
770 if acc
771 .iter()
772 .any(|(n, _)| n.len() == names.len() && names.iter().all(|other| n.contains(name(other))))
773 {
774 return false;
775 }
776 let fields: Vec<Shape> = fields.collect();
777 if fields.contains(&Shape::Conflict) {
778 return false;
779 }
780 acc.push((names.iter().map(|n| name(n).clone()).collect(), fields));
781 true
782}
783
784fn join(a: Shape, b: Shape) -> Shape {
785 use Shape::{AnyMv, Bottom, Conflict, Fcn, Set, TypedMv};
786 match (a, b) {
787 (Conflict, _) | (_, Conflict) => Conflict,
788 (Bottom | AnyMv, x) | (x, Bottom | AnyMv) => x,
789 (TypedMv(s), TypedMv(t)) => {
790 if s == t {
791 TypedMv(s)
792 } else {
793 Conflict
794 }
795 }
796 (Set(x), Set(y)) => match join(*x, *y) {
797 Conflict => Conflict,
798 j => Set(Box::new(j)),
799 },
800 (Fcn(d1, v1), Fcn(d2, v2)) => match (join(*d1, *d2), join(*v1, *v2)) {
801 (Conflict, _) | (_, Conflict) => Conflict,
802 (d, v) => Fcn(Box::new(d), Box::new(v)),
803 },
804 (Shape::Rcd(a), Shape::Rcd(b)) => join_rcd(a, b),
805 (Shape::Rcd(r), Fcn(d, v)) | (Fcn(d, v), Shape::Rcd(r)) if *d == Bottom && *v == Bottom => {
809 Shape::Rcd(r)
810 }
811 (x, y) => {
812 if x == y && matches!(x, Shape::Bool | Shape::Int | Shape::Str) {
813 x
814 } else {
815 Conflict
816 }
817 }
818 }
819}
820
821fn join_all<'a>(vals: impl Iterator<Item = &'a Value>) -> Shape {
822 let mut acc = Shape::Bottom;
823 for v in vals {
824 if let (Shape::Rcd(entries), Value::Fcn(f)) = (&mut acc, v)
827 && let FcnRepr::Record(fs) = &f.0.repr
828 {
829 let Ok(_guard) = crate::depth::Guard::enter() else {
830 return Shape::Conflict;
831 };
832 let joined = join_fields(entries, fs, |(n, _)| n, fs.iter().map(|(_, v)| shape(v)));
833 if !joined {
834 return Shape::Conflict;
835 }
836 continue;
837 }
838 acc = join(acc, shape(v));
839 if acc == Shape::Conflict {
840 break;
841 }
842 }
843 acc
844}
845
846fn shape(v: &Value) -> Shape {
847 let Ok(_guard) = crate::depth::Guard::enter() else {
849 return Shape::Conflict;
850 };
851 match v {
852 Value::Bool(_) => Shape::Bool,
853 Value::Int(_) | Value::BigInt(_) => Shape::Int,
854 Value::Str(_) => Shape::Str,
855 Value::Model(a) => a.mv_type().map_or(Shape::AnyMv, Shape::TypedMv),
856 Value::Set(s) => match s.repr() {
857 SetRepr::Enum => match s.0.elems.get() {
858 Some(e) => match join_all(e.iter()) {
859 Shape::Conflict => Shape::Conflict,
860 j => Shape::Set(Box::new(j)),
861 },
862 None => Shape::Conflict,
863 },
864 SetRepr::Interval(..) => Shape::Set(Box::new(Shape::Int)),
865 _ => Shape::Conflict,
866 },
867 Value::Fcn(f) => match &f.0.repr {
868 FcnRepr::Tuple(e) => {
869 let d = if e.is_empty() {
870 Shape::Bottom
871 } else {
872 Shape::Int
873 };
874 match join_all(e.iter()) {
875 Shape::Conflict => Shape::Conflict,
876 j => Shape::Fcn(Box::new(d), Box::new(j)),
877 }
878 }
879 FcnRepr::Record(fs) => {
880 let mut acc = Vec::new();
881 if join_fields(&mut acc, fs, |(n, _)| n, fs.iter().map(|(_, v)| shape(v))) {
882 Shape::Rcd(acc)
883 } else {
884 Shape::Conflict
885 }
886 }
887 FcnRepr::General(ps) if ps.is_empty() => Shape::Conflict,
889 FcnRepr::General(ps) => {
890 match (
891 join_all(ps.iter().map(|(d, _)| d)),
892 join_all(ps.iter().map(|(_, v)| v)),
893 ) {
894 (Shape::Conflict, _) | (_, Shape::Conflict) => Shape::Conflict,
895 (d, v) => Shape::Fcn(Box::new(d), Box::new(v)),
896 }
897 }
898 },
899 }
900}
901
902fn all_comparable(elems: &[Value]) -> bool {
904 let Some(first) = elems.first() else {
906 return true;
907 };
908 let scalar_same = match first {
909 Value::Int(_) => elems
910 .iter()
911 .all(|v| matches!(v, Value::Int(_) | Value::BigInt(_))),
912 Value::Str(_) => elems.iter().all(|v| matches!(v, Value::Str(_))),
913 Value::Bool(_) => elems.iter().all(|v| matches!(v, Value::Bool(_))),
914 _ => false,
915 };
916 scalar_same || join_all(elems.iter()) != Shape::Conflict
917}
918
919fn join_rcd_controlled(
921 mut acc: Vec<(Vec<Atom>, Vec<Shape>)>,
922 other: Vec<(Vec<Atom>, Vec<Shape>)>,
923 poll: &mut dyn FnMut() -> bool,
924) -> std::result::Result<Shape, crate::ConstructionError> {
925 for (names, fields) in other {
926 if !join_fields_controlled(&mut acc, &names, |n| n, fields.into_iter().map(Ok), poll)? {
927 return Ok(Shape::Conflict);
928 }
929 }
930 Ok(Shape::Rcd(acc))
931}
932
933fn join_fields_controlled<'a, N>(
934 acc: &mut Vec<(Vec<Atom>, Vec<Shape>)>,
935 names: &'a [N],
936 name: impl Fn(&'a N) -> &'a Atom,
937 fields: impl Iterator<Item = std::result::Result<Shape, crate::ConstructionError>>,
938 poll: &mut dyn FnMut() -> bool,
939) -> std::result::Result<bool, crate::ConstructionError> {
940 let mut found = None;
941 for (at, (stored, _)) in acc.iter().enumerate() {
942 crate::construction::checkpoint(poll)?;
943 if stored.len() != names.len() {
944 continue;
945 }
946 let mut same = true;
947 for (a, b) in stored.iter().zip(names) {
948 crate::construction::checkpoint(poll)?;
949 same &= a == name(b);
950 }
951 if same {
952 found = Some(at);
953 break;
954 }
955 }
956 if let Some(at) = found {
957 for (field, theirs) in acc[at].1.iter_mut().zip(fields) {
958 let joined = join_controlled(std::mem::replace(field, Shape::Bottom), theirs?, poll)?;
959 if joined == Shape::Conflict {
960 return Ok(false);
961 }
962 *field = joined;
963 }
964 return Ok(true);
965 }
966 for (stored, _) in acc.iter() {
967 if stored.len() == names.len() {
968 let mut same_names = true;
969 for other in names {
970 let mut contains = false;
971 for key in stored {
972 crate::construction::checkpoint(poll)?;
973 contains |= key == name(other);
974 }
975 same_names &= contains;
976 }
977 if same_names {
978 return Ok(false);
979 }
980 }
981 }
982 let mut collected = Vec::new();
983 for field in fields {
984 crate::construction::reserve(&mut collected, 1, poll)?;
985 collected.push(field?);
986 }
987 if collected.contains(&Shape::Conflict) {
988 return Ok(false);
989 }
990 let mut keys = Vec::new();
991 crate::construction::reserve(&mut keys, names.len(), poll)?;
992 for field in names {
993 crate::construction::checkpoint(poll)?;
994 keys.push(name(field).clone());
995 }
996 crate::construction::reserve(acc, 1, poll)?;
997 acc.push((keys, collected));
998 Ok(true)
999}
1000
1001fn join_controlled(
1002 a: Shape,
1003 b: Shape,
1004 poll: &mut dyn FnMut() -> bool,
1005) -> std::result::Result<Shape, crate::ConstructionError> {
1006 use Shape::{AnyMv, Bottom, Conflict, Fcn, Set, TypedMv};
1007 crate::construction::checkpoint(poll)?;
1008 Ok(match (a, b) {
1009 (Conflict, _) | (_, Conflict) => Conflict,
1010 (Bottom | AnyMv, x) | (x, Bottom | AnyMv) => x,
1011 (TypedMv(s), TypedMv(t)) => {
1012 if s == t {
1013 TypedMv(s)
1014 } else {
1015 Conflict
1016 }
1017 }
1018 (Set(x), Set(y)) => match join_controlled(*x, *y, poll)? {
1019 Conflict => Conflict,
1020 j => Set(Box::new(j)),
1021 },
1022 (Fcn(d1, v1), Fcn(d2, v2)) => match (
1023 join_controlled(*d1, *d2, poll)?,
1024 join_controlled(*v1, *v2, poll)?,
1025 ) {
1026 (Conflict, _) | (_, Conflict) => Conflict,
1027 (d, v) => Fcn(Box::new(d), Box::new(v)),
1028 },
1029 (Shape::Rcd(a), Shape::Rcd(b)) => join_rcd_controlled(a, b, poll)?,
1030 (Shape::Rcd(r), Fcn(d, v)) | (Fcn(d, v), Shape::Rcd(r)) if *d == Bottom && *v == Bottom => {
1031 Shape::Rcd(r)
1032 }
1033 (x, y) => {
1034 if x == y && matches!(x, Shape::Bool | Shape::Int | Shape::Str) {
1035 x
1036 } else {
1037 Conflict
1038 }
1039 }
1040 })
1041}
1042
1043fn join_all_controlled<'a>(
1044 vals: impl Iterator<Item = &'a Value>,
1045 poll: &mut dyn FnMut() -> bool,
1046) -> std::result::Result<Shape, crate::ConstructionError> {
1047 let mut acc = Shape::Bottom;
1048 for value in vals {
1049 crate::construction::checkpoint(poll)?;
1050 if let (Shape::Rcd(entries), Value::Fcn(f)) = (&mut acc, value)
1053 && let FcnRepr::Record(fields) = &f.0.repr
1054 {
1055 let Ok(_guard) = crate::depth::Guard::enter() else {
1056 return Ok(Shape::Conflict);
1057 };
1058 let mut shapes = Vec::new();
1059 crate::construction::reserve(&mut shapes, fields.len(), poll)?;
1060 for (_, value) in fields {
1061 shapes.push(shape_controlled(value, poll)?);
1062 }
1063 if !join_fields_controlled(
1064 entries,
1065 fields,
1066 |(name, _)| name,
1067 shapes.into_iter().map(Ok),
1068 poll,
1069 )? {
1070 return Ok(Shape::Conflict);
1071 }
1072 continue;
1073 }
1074 acc = join_controlled(acc, shape_controlled(value, poll)?, poll)?;
1075 if acc == Shape::Conflict {
1076 break;
1077 }
1078 }
1079 Ok(acc)
1080}
1081
1082fn shape_controlled(
1083 value: &Value,
1084 poll: &mut dyn FnMut() -> bool,
1085) -> std::result::Result<Shape, crate::ConstructionError> {
1086 crate::construction::checkpoint(poll)?;
1087 let Ok(_guard) = crate::depth::Guard::enter() else {
1088 return Ok(Shape::Conflict);
1089 };
1090 Ok(match value {
1091 Value::Bool(_) => Shape::Bool,
1092 Value::Int(_) | Value::BigInt(_) => Shape::Int,
1093 Value::Str(_) => Shape::Str,
1094 Value::Model(atom) => atom.mv_type().map_or(Shape::AnyMv, Shape::TypedMv),
1095 Value::Set(set) => match set.repr() {
1096 SetRepr::Enum => match set.0.elems.get() {
1097 Some(elements) => match join_all_controlled(elements.iter(), poll)? {
1098 Shape::Conflict => Shape::Conflict,
1099 joined => Shape::Set(Box::new(joined)),
1100 },
1101 None => Shape::Conflict,
1102 },
1103 SetRepr::Interval(..) => Shape::Set(Box::new(Shape::Int)),
1104 _ => Shape::Conflict,
1105 },
1106 Value::Fcn(f) => match &f.0.repr {
1107 FcnRepr::Tuple(elements) => {
1108 let domain = if elements.is_empty() {
1109 Shape::Bottom
1110 } else {
1111 Shape::Int
1112 };
1113 match join_all_controlled(elements.iter(), poll)? {
1114 Shape::Conflict => Shape::Conflict,
1115 joined => Shape::Fcn(Box::new(domain), Box::new(joined)),
1116 }
1117 }
1118 FcnRepr::Record(fields) => {
1119 let mut shapes = Vec::new();
1120 crate::construction::reserve(&mut shapes, fields.len(), poll)?;
1121 for (_, value) in fields {
1122 shapes.push(shape_controlled(value, poll)?);
1123 }
1124 let mut acc = Vec::new();
1125 if join_fields_controlled(
1126 &mut acc,
1127 fields,
1128 |(name, _)| name,
1129 shapes.into_iter().map(Ok),
1130 poll,
1131 )? {
1132 Shape::Rcd(acc)
1133 } else {
1134 Shape::Conflict
1135 }
1136 }
1137 FcnRepr::General(pairs) if pairs.is_empty() => Shape::Conflict,
1138 FcnRepr::General(pairs) => match (
1139 join_all_controlled(pairs.iter().map(|(key, _)| key), poll)?,
1140 join_all_controlled(pairs.iter().map(|(_, value)| value), poll)?,
1141 ) {
1142 (Shape::Conflict, _) | (_, Shape::Conflict) => Shape::Conflict,
1143 (domain, value) => Shape::Fcn(Box::new(domain), Box::new(value)),
1144 },
1145 },
1146 })
1147}
1148
1149pub(crate) fn all_comparable_controlled(
1151 elems: &[Value],
1152 poll: &mut dyn FnMut() -> bool,
1153) -> std::result::Result<bool, crate::ConstructionError> {
1154 let Some(first) = elems.first() else {
1155 crate::construction::checkpoint(poll)?;
1156 return Ok(true);
1157 };
1158 let mut scalar_same = matches!(first, Value::Int(_) | Value::Str(_) | Value::Bool(_));
1159 for value in elems {
1160 crate::construction::checkpoint(poll)?;
1161 scalar_same &= match first {
1162 Value::Int(_) => matches!(value, Value::Int(_) | Value::BigInt(_)),
1163 Value::Str(_) => matches!(value, Value::Str(_)),
1164 Value::Bool(_) => matches!(value, Value::Bool(_)),
1165 _ => false,
1166 };
1167 }
1168 Ok(scalar_same || join_all_controlled(elems.iter(), poll)? != Shape::Conflict)
1169}
1170pub(crate) fn normalize_set(mut elems: Vec<Value>, ctx: Ctx) -> Result<Vec<Value>> {
1176 if elems.len() <= 1 {
1177 return Ok(elems);
1178 }
1179 if all_comparable(&elems) {
1180 elems.sort_by(|a, b| total_cmp(a, b, ctx.order));
1181 elems.dedup_by(|later, earlier| total_cmp(later, earlier, ctx.order) == Ordering::Equal);
1182 return Ok(elems);
1183 }
1184 let mut out = tlc_insertion_sort(
1186 elems,
1187 Ctx {
1188 order: ValueOrder::Tlc,
1189 ..ctx
1190 },
1191 )?;
1192 if ctx.order != ValueOrder::Tlc {
1193 out.sort_by(|a, b| total_cmp(a, b, ctx.order));
1194 }
1195 Ok(out)
1196}
1197
1198fn tlc_insertion_sort(elems: Vec<Value>, ctx: Ctx) -> Result<Vec<Value>> {
1201 let mut iter = elems.into_iter();
1202 let mut out: Vec<Value> = Vec::new();
1203 if let Some(first) = iter.next() {
1204 out.push(first);
1205 }
1206 for elem in iter {
1207 let (mut low, mut high) = (0usize, out.len());
1208 let mut cmp = Ordering::Equal;
1209 let mut idx = 0usize;
1210 while low < high {
1211 idx = low + ((high - low) >> 1);
1212 cmp = crate::tlc::compare(&elem, &out[idx], ctx)?;
1213 match cmp {
1214 Ordering::Equal => break,
1215 Ordering::Less => high = idx,
1216 Ordering::Greater => low = idx + 1,
1217 }
1218 }
1219 if cmp != Ordering::Equal {
1220 let at = if cmp == Ordering::Less { idx } else { idx + 1 };
1221 out.insert(at, elem);
1222 }
1223 }
1224 Ok(out)
1225}
1226
1227fn dup_domain(v: &Value, ctx: Ctx) -> ValueError {
1228 ValueError::new(
1229 ErrorKind::Duplicate,
1230 format!(
1231 "The value\n{}\noccurs multiple times in the function domain.",
1232 crate::print::to_tlc_string_lenient(v, ctx)
1233 ),
1234 )
1235}
1236
1237pub(crate) fn make_fcn(mut pairs: Vec<(Value, Value)>, ctx: Ctx) -> Result<Value> {
1241 if pairs.is_empty() {
1242 return Ok(Value::tuple_fcn(Vec::new()));
1243 }
1244 if pairs.len() > 1 {
1245 let doms: Vec<Value> = pairs.iter().map(|(d, _)| d.clone()).collect();
1246 if all_comparable(&doms) {
1247 pairs.sort_by(|a, b| total_cmp(&a.0, &b.0, ctx.order));
1248 for w in pairs.windows(2) {
1249 if total_cmp(&w[0].0, &w[1].0, ctx.order) == Ordering::Equal {
1250 return Err(dup_domain(&w[1].0, ctx));
1251 }
1252 }
1253 } else {
1254 tlc_fcn_normalize(
1255 &mut pairs,
1256 Ctx {
1257 order: ValueOrder::Tlc,
1258 ..ctx
1259 },
1260 )?;
1261 if ctx.order != ValueOrder::Tlc {
1262 pairs.sort_by(|a, b| total_cmp(&a.0, &b.0, ctx.order));
1263 }
1264 }
1265 }
1266 let n = pairs.len();
1268 let is_tuple = pairs.iter().enumerate().all(
1269 |(i, (d, _))| matches!(d, Value::Int(k) if i64::try_from(i).is_ok_and(|i| *k == i + 1)),
1270 );
1271 if is_tuple {
1272 return Ok(Value::tuple_fcn(
1273 pairs.into_iter().map(|(_, v)| v).collect(),
1274 ));
1275 }
1276 if pairs.iter().all(|(d, _)| matches!(d, Value::Str(_))) {
1277 let mut fields: Vec<(Atom, Value)> = Vec::with_capacity(n);
1278 for (d, v) in pairs {
1279 if let Value::Str(a) = d {
1280 fields.push((a, v));
1281 }
1282 }
1283 return Ok(Value::Fcn(Fcn::record(fields, ctx.order, false)));
1284 }
1285 Ok(Value::Fcn(Fcn::general(pairs, ctx.order)))
1286}
1287
1288fn tlc_fcn_normalize(pairs: &mut [(Value, Value)], ctx: Ctx) -> Result<()> {
1291 let n = pairs.len();
1292 for i in 1..n {
1293 let c = crate::tlc::compare(&pairs[0].0, &pairs[i].0, ctx)?;
1294 if c == Ordering::Equal {
1295 return Err(dup_domain(&pairs[i].0, ctx));
1296 }
1297 if c == Ordering::Greater {
1298 pairs.swap(0, i);
1299 }
1300 }
1301 for i in 2..n {
1302 let item = pairs[i].clone();
1303 let mut j = i;
1304 let mut c = Ordering::Less;
1305 while j > 0 {
1306 c = crate::tlc::compare(&item.0, &pairs[j - 1].0, ctx)?;
1307 if c != Ordering::Less {
1308 break;
1309 }
1310 pairs[j] = pairs[j - 1].clone();
1311 j -= 1;
1312 }
1313 if c == Ordering::Equal {
1314 return Err(dup_domain(&pairs[i].0, ctx));
1316 }
1317 pairs[j] = item;
1318 }
1319 Ok(())
1320}
1321
1322impl Fcn {
1327 #[must_use]
1346 pub fn domain_equals(&self, dom: &Set) -> Option<bool> {
1347 if let Some(same) = self.exact_domain_equals(dom) {
1348 return Some(same);
1349 }
1350 if !self.domain_comparable() {
1351 return None;
1352 }
1353 let n = self.len() as u128;
1354 match dom.repr() {
1355 SetRepr::Interval(..) | SetRepr::Enum => {
1356 if quiet_size(dom)? != n {
1357 return Some(false);
1358 }
1359 let mut verdict = Some(true);
1360 self.for_each_key(&mut |k| {
1361 if verdict == Some(true) {
1362 verdict = contains_settled(dom, k);
1363 }
1364 });
1365 verdict
1366 }
1367 SetRepr::Product(factors) => {
1368 if class(dom) == Class::Structural {
1370 return None;
1371 }
1372 let mut size: u128 = 1;
1373 for f in factors {
1374 let Value::Set(f) = f else { return None };
1375 if !matches!(f.repr(), SetRepr::Interval(..) | SetRepr::Enum) {
1376 return None;
1377 }
1378 size = size.checked_mul(quiet_size(f)?)?;
1379 }
1380 if size != n {
1381 return Some(false);
1382 }
1383 let mut verdict = Some(true);
1384 self.for_each_key(&mut |k| {
1385 if verdict == Some(true) {
1386 verdict = in_product(factors, k);
1387 }
1388 });
1389 verdict
1390 }
1391 _ => None,
1392 }
1393 }
1394
1395 fn domain_comparable(&self) -> bool {
1398 match &self.0.repr {
1399 FcnRepr::Tuple(_) | FcnRepr::Record(_) => true,
1401 FcnRepr::General(p) => p.domain.comparable(),
1402 }
1403 }
1404
1405 fn for_each_key(&self, visit: &mut dyn FnMut(&Value)) {
1407 match &self.0.repr {
1408 FcnRepr::Tuple(e) => {
1409 for i in 1..=e.len() {
1410 visit(&Value::Int(i64::try_from(i).unwrap_or(i64::MAX)));
1411 }
1412 }
1413 FcnRepr::Record(f) => {
1414 for (a, _) in f {
1415 visit(&Value::Str(a.clone()));
1416 }
1417 }
1418 FcnRepr::General(p) => {
1419 for (d, _) in p {
1420 visit(d);
1421 }
1422 }
1423 }
1424 }
1425}
1426
1427fn in_product(factors: &[Value], k: &Value) -> Option<bool> {
1430 let Some(t) = k.as_fcn().and_then(Fcn::as_tuple) else {
1431 return Some(false);
1432 };
1433 if t.len() != factors.len() {
1434 return Some(false);
1435 }
1436 for (x, f) in t.iter().zip(factors) {
1437 if !contains_settled(f.as_set()?, x)? {
1438 return Some(false);
1439 }
1440 }
1441 Some(true)
1442}
1443
1444fn contains_settled(s: &Set, x: &Value) -> Option<bool> {
1447 match s.repr() {
1448 SetRepr::Interval(lo, hi) => {
1449 let (lo, hi) = (lo.to_i64()?, hi.to_i64()?);
1450 match x {
1451 Value::Int(v) => Some(lo <= *v && *v <= hi),
1452 Value::BigInt(_) => None,
1453 _ => Some(false),
1454 }
1455 }
1456 SetRepr::Enum => {
1457 let elems = s.stored_elements()?;
1458 let order = s.order();
1459 Some(elems.binary_search_by(|e| total_cmp(e, x, order)).is_ok())
1460 }
1461 _ => None,
1462 }
1463}
1464
1465pub(crate) fn stable_key(value: &Value) -> bool {
1467 let Ok(_guard) = crate::depth::Guard::enter() else {
1468 return false;
1469 };
1470 match value {
1471 Value::Bool(_) | Value::Int(_) | Value::BigInt(_) | Value::Str(_) | Value::Model(_) => true,
1472 Value::Set(set) => match set.repr() {
1473 SetRepr::Interval(..) => true,
1474 SetRepr::Enum => set
1475 .stored_elements()
1476 .is_some_and(|e| e.iter().all(stable_key)),
1477 _ => false,
1478 },
1479 Value::Fcn(f) => match &f.0.repr {
1480 FcnRepr::Tuple(values) => values.iter().all(stable_key),
1481 FcnRepr::Record(fields) => fields.iter().all(|(_, v)| stable_key(v)),
1482 FcnRepr::General(pairs) => pairs.iter().all(|(d, v)| stable_key(d) && stable_key(v)),
1483 },
1484 }
1485}