Skip to main content

dive_value/
ops.rs

1//! Set algebra on finite sets, as TLC evaluates it.
2//!
3//! These port TLC's eager forms (`SetEnumValue.cup`, `cap`, `diff`; tlaplus
4//! `94d0c50`), including which results stay unnormalized: a union is built
5//! unnormalized, and an intersection or difference keeps its left operand's state. That
6//! matters for TLC's errors, because membership in an unnormalized set is a linear scan
7//! with `equals` (fixture `ErrMemNormalized`). Membership uses the checked
8//! [`crate::tlc::member`]. Lazy unions of infinite sets are `dive-eval`'s concern
9//! ([`DeferredSet`](crate::DeferredSet)).
10
11use crate::ctx::Ctx;
12use crate::error::{ErrorKind, Result, ValueError};
13use crate::tlc::member;
14use crate::value::{Set, SetRepr, Value};
15
16/// The elements of a set in TLC's current order, and whether that order is normalized.
17fn current(v: &Value, ctx: Ctx) -> Result<(Vec<Value>, bool)> {
18    match v {
19        Value::Set(s) => match s.repr() {
20            SetRepr::Raw(raw) => {
21                if s.is_tlc_normalized() {
22                    Ok((crate::stream::elems_in(s, ctx, true)?.to_vec(), true))
23                } else {
24                    Ok((raw.to_vec(), false))
25                }
26            }
27            _ => Ok((crate::stream::elems_in(s, ctx, true)?.to_vec(), true)),
28        },
29        _ => Err(ValueError::new(
30            ErrorKind::Argument,
31            format!(
32                "Attempted to apply a set operator to the non-set value\n{}",
33                crate::print::print_value(v, ctx).unwrap_or_default()
34            ),
35        )),
36    }
37}
38
39fn build(elems: Vec<Value>, normalized: bool, ctx: Ctx) -> Value {
40    if normalized {
41        Value::Set(Set::from_sorted(ctx.order, elems))
42    } else {
43        Value::set_raw(elems, ctx)
44    }
45}
46
47/// `a \cup b` (`SetEnumValue.cup`): `a`'s elements, then `b`'s elements not in `a`,
48/// unnormalized.
49///
50/// # Errors
51/// Enumeration and membership errors.
52pub fn union(a: &Value, b: &Value, ctx: Ctx) -> Result<Value> {
53    let (mut out, _) = current(a, ctx)?;
54    if out.is_empty() {
55        return Ok(b.clone());
56    }
57    // TLC enumerates `b` with `elements()`, which normalizes it.
58    let Value::Set(bs) = b else {
59        return current(b, ctx).map(|(_, _)| b.clone());
60    };
61    for e in crate::stream::elems_in(bs, ctx, true)?.iter() {
62        if !member(e, a, ctx)? {
63            out.push(e.clone());
64        }
65    }
66    Ok(Value::set_raw(out, ctx))
67}
68
69/// `a \cap b` (`SetEnumValue.cap`).
70///
71/// # Errors
72/// Enumeration and membership errors.
73pub fn intersect(a: &Value, b: &Value, ctx: Ctx) -> Result<Value> {
74    let (elems, norm) = current(a, ctx)?;
75    let mut out = Vec::new();
76    for e in elems {
77        if member(&e, b, ctx)? {
78            out.push(e);
79        }
80    }
81    Ok(build(out, norm, ctx))
82}
83
84/// `a \ b` (`SetEnumValue.diff`).
85///
86/// # Errors
87/// Enumeration and membership errors.
88pub fn difference(a: &Value, b: &Value, ctx: Ctx) -> Result<Value> {
89    let (elems, norm) = current(a, ctx)?;
90    let mut out = Vec::new();
91    for e in elems {
92        if !member(&e, b, ctx)? {
93            out.push(e);
94        }
95    }
96    Ok(build(out, norm, ctx))
97}
98
99/// The first element of `s` in normalized order that satisfies `pred`: TLC's
100/// `CHOOSE x \in s : pred(x)` (`Tool`, `OPCODE_bc`, which enumerates with
101/// `Ordering.NORMALIZED`). `None` when no element satisfies it.
102///
103/// # Errors
104/// Enumeration errors and errors from `pred`.
105pub fn choose(
106    s: &Value,
107    ctx: Ctx,
108    mut pred: impl FnMut(&Value) -> Result<bool>,
109) -> Result<Option<Value>> {
110    let Value::Set(set) = s else {
111        return Err(ValueError::new(
112            ErrorKind::NotEnumerable,
113            "Attempted to compute the value of an expression of form CHOOSE x \\in S: P, but S was not enumerable.",
114        ));
115    };
116    for e in crate::stream::elems_in(set, ctx, true)?.iter() {
117        if pred(e)? {
118            return Ok(Some(e.clone()));
119        }
120    }
121    Ok(None)
122}