1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
//! `--comparisons=tla` (the default): `=` and `\in` answered as TLA+ defines them for functions
//! (including tuples and records) and sets, symmetrically and independently of
//! element order.
//!
//! The rules:
//! - Two scalars of the same kind (booleans, integers, strings, model values)
//! compare by value.
//! - Where TLA+ leaves the answer unspecified, TLC's error is kept: a direct
//! comparison of scalars of different kinds (`1 = "a"`), or of a set, a
//! function or a scalar with a value of another of those three kinds
//! (`{1} = 1`). TLC's own answer is used when TLC gives one (an untyped model
//! value is unequal to everything else).
//! - Inside sets and functions, values of different kinds are unequal, so
//! `[a |-> 1, b |-> 1] = <<1>>` and `<<1>> \in [a : {1}]` are `FALSE`.
//! - Canonical identity demands a materialized value tree. Symbolic operator
//! membership stays lazy; unproved symbolic equality refuses explicitly.
use dive_value::{ErrorKind, SetKind, Value, tlc};
use crate::core::Core;
use crate::error::Result;
#[derive(Clone, Copy, PartialEq, Eq)]
enum Class {
Scalar(u8),
Set,
Fcn,
}
fn class(v: &Value) -> Class {
match v {
Value::Bool(_) => Class::Scalar(0),
Value::Int(_) | Value::BigInt(_) => Class::Scalar(1),
Value::Str(_) => Class::Scalar(2),
Value::Model(_) => Class::Scalar(3),
Value::Set(_) => Class::Set,
Value::Fcn(_) => Class::Fcn,
}
}
fn equality_operand(core: &Core, value: &Value) -> Result<Value> {
// Intervals have exact scalar bounds. Equality compares their bounds or
// streams one against an already materialized set, without structural
// fallback for symbolic children.
if matches!(value, Value::Set(set) if set.as_interval().is_some()) {
return Ok(value.clone());
}
Ok(value.materialized_for_equality(core.ctx)?)
}
/// `a = b`.
pub(crate) fn equals(core: &Core, a: &Value, b: &Value) -> Result<bool> {
let (ca, cb) = (class(a), class(b));
if ca == cb && ca != Class::Scalar(3) {
let a = equality_operand(core, a)?;
let b = equality_operand(core, b)?;
// Same kind: TLA+'s extensional equality, which `Value`'s total
// equality implements (values of different kinds inside are unequal).
return Ok(a == b);
}
// Unspecified in TLA+, or model values: TLC's answer or TLC's error.
Ok(tlc::equals(a, b, core.ctx)?)
}
/// `elem \in set`.
pub(crate) fn member(core: &Core, elem: &Value, set: &Value) -> Result<bool> {
let Value::Set(s) = set else {
return Ok(tlc::member(elem, set, core.ctx)?);
};
match s.kind() {
SetKind::FcnSet | SetKind::RcdSet | SetKind::Product | SetKind::Seq => {
if class(elem) != Class::Fcn {
return Ok(tlc::member(elem, set, core.ctx)?);
}
Ok(structural_member(core, elem, set)?)
}
SetKind::Subset => {
if class(elem) != Class::Set {
return Ok(tlc::member(elem, set, core.ctx)?);
}
let comps = s.components();
let Some((_, base)) = comps.first() else {
return Ok(false);
};
let Value::Set(es) = elem else {
return Ok(false);
};
for x in es.elements(core.ctx)?.iter() {
if !member(core, x, base)? {
return Ok(false);
}
}
Ok(true)
}
SetKind::Enum | SetKind::Raw => {
let elem = equality_operand(core, elem)?;
set.require_materialized(core.ctx)?;
// Inspection admits explicit raw children, but those children still
// need canonical identity before Value equality can compare them.
// Providers were rejected by the read-only inspection above.
let materialized = set.materialized_for_equality(core.ctx)?;
let Value::Set(materialized_set) = &materialized else {
return Err(crate::EvalError::bug("materialized set changed value kind"));
};
let elems = materialized_set.elements(core.ctx)?;
let ce = class(&elem);
let mut unspecified = false;
for x in elems.iter() {
let cx = class(x);
if ce == cx && ce != Class::Scalar(3) {
if &elem == x {
return Ok(true);
}
} else if matches!(ce, Class::Scalar(_))
|| matches!(cx, Class::Scalar(_))
|| ce == Class::Scalar(3)
|| cx == Class::Scalar(3)
{
// A comparison TLA+ leaves unspecified (or a model value):
// TLC's answer decides it, or the membership is unspecified.
match tlc::equals(&elem, x, core.ctx) {
Ok(true) => return Ok(true),
Ok(false) => {}
Err(error) if matches!(error.kind(), ErrorKind::Interrupted { .. }) => {
return Err(error.into());
}
Err(_) => unspecified = true,
}
}
}
if unspecified {
return Ok(tlc::member(&elem, &materialized, core.ctx)?);
}
Ok(false)
}
_ => Ok(tlc::member(elem, set, core.ctx)?),
}
}
/// Membership of a function in `[S -> T]`, `[a : S, ...]`, `S1 \X ... \X Sn`
/// or `Seq(S)`: the domain must be the set's, and each value a member.
fn structural_member(core: &Core, elem: &Value, set: &Value) -> Result<bool> {
let (Value::Fcn(f), Value::Set(s)) = (elem, set) else {
return Ok(false);
};
match s.kind() {
SetKind::RcdSet => {
let (Some(fields), Some(comps)) = (f.as_record(), s.as_rcd_set()) else {
return Ok(false);
};
if fields.len() != comps.len() {
return Ok(false);
}
for (name, sub) in comps {
let Some((_, v)) = fields.iter().find(|(a, _)| a == name) else {
return Ok(false);
};
if !member(core, v, sub)? {
return Ok(false);
}
}
Ok(true)
}
SetKind::Product => {
let (Some(t), Some(comps)) = (f.as_tuple(), s.as_product()) else {
return Ok(false);
};
if t.len() != comps.len() {
return Ok(false);
}
for (x, sub) in t.iter().zip(comps) {
if !member(core, x, sub)? {
return Ok(false);
}
}
Ok(true)
}
SetKind::Seq => {
let Some(t) = f.as_tuple() else {
return Ok(false);
};
let comps = s.components();
let Some((_, range)) = comps.first() else {
return Ok(false);
};
for x in t {
if !member(core, x, range)? {
return Ok(false);
}
}
Ok(true)
}
SetKind::FcnSet => {
let Some((dom, range)) = s.as_fcn_set() else {
return Ok(false);
};
// `DOMAIN f = dom` without building the domain set where the
// answer is certain; otherwise as TLA+ defines it, through the set.
let same = if let Some(same) = dom.as_set().and_then(|d| f.domain_equals(d)) {
same
} else {
let fdom = Value::set(f.iter().map(|(d, _)| d).collect(), core.ctx)?;
equals(core, &fdom, dom)?
};
if !same {
return Ok(false);
}
for v in f.values() {
if !member(core, v, range)? {
return Ok(false);
}
}
Ok(true)
}
_ => Ok(false),
}
}