Skip to main content

dive_stdlib/random/
ops.rs

1//! `RandomElement` (module `TLC`) and the `Randomization` operators over values.
2
3use std::collections::HashSet;
4use std::fmt;
5
6use num_bigint::BigInt;
7use num_traits::ToPrimitive;
8
9use dive_value::print::{print_value, to_tlc_string_lenient};
10use dive_value::{Atom, Ctx, ErrorKind, Int, Set, SetKind, Value, ValueError, tlc};
11
12use super::lcg::{BigIndices, SubsetIndices, big_digit};
13use super::source::RandomSource;
14
15/// The Java method TLC names when `RandomElement` throws a non-TLC exception.
16pub const RANDOM_ELEMENT_METHOD: &str =
17    "public static tlc2.value.impl.Value tlc2.module.TLC.RandomElement(tlc2.value.impl.Value)";
18/// The Java method TLC names when `RandomSubset` throws a non-TLC exception.
19pub const RANDOM_SUBSET_METHOD: &str = "public static tlc2.value.impl.Value \
20     tlc2.module.Randomization.RandomSubset(tlc2.value.impl.Value,tlc2.value.impl.Value)";
21/// The Java method TLC names when `RandomSetOfSubsets` throws a non-TLC exception.
22pub const RANDOM_SET_OF_SUBSETS_METHOD: &str = "public static tlc2.value.impl.Value \
23     tlc2.module.Randomization.RandomSetOfSubsets(tlc2.value.impl.Value,\
24     tlc2.value.impl.Value,tlc2.value.impl.Value)";
25
26/// An error from a random operator, with TLC's error class and message.
27#[derive(Clone, Debug, PartialEq, Eq)]
28pub enum RandomError {
29    /// `EC.TLC_MODULE_ARGUMENT_ERROR` (2169): `The <position> argument of <op> should
30    /// be a <expected>, but instead it is:\n<value>`.
31    Argument {
32        /// `first`, `second` or `third`.
33        position: &'static str,
34        /// The operator.
35        op: &'static str,
36        /// What TLC expected (TLC's wording, including its `a a finite set`).
37        expected: String,
38        /// The argument as TLC prints it.
39        value: String,
40    },
41    /// `EC.TLC_MODULE_APPLYING_TO_WRONG_VALUE` (2176): `Applying <op> to the following
42    /// value,\nwhich is not <expected>:\n<value>`.
43    WrongValue {
44        /// The operator.
45        op: &'static str,
46        /// What TLC expected.
47        expected: &'static str,
48        /// The value as TLC prints it.
49        value: String,
50    },
51    /// `EC.TLC_MODULE_VALUE_JAVA_METHOD_OVERRIDE` (2154): a Java exception other than
52    /// TLC's own evaluation errors escaped the override (an index out of bounds, a
53    /// negative array size, or a `GENERAL` error such as an unenumerable set).
54    JavaOverride {
55        /// The Java method's signature, as TLC prints it.
56        method: &'static str,
57        /// The exception's message.
58        message: String,
59    },
60    /// A value-layer error that TLC reports with its own class.
61    Value(ValueError),
62}
63
64impl RandomError {
65    /// TLC's `EC` code.
66    #[must_use]
67    pub const fn tlc_code(&self) -> u32 {
68        match self {
69            Self::Argument { .. } => 2169,
70            Self::WrongValue { .. } => 2176,
71            Self::JavaOverride { .. } => 2154,
72            Self::Value(e) => e.kind().tlc_code(),
73        }
74    }
75
76    /// The message TLC prints.
77    #[must_use]
78    pub fn message(&self) -> String {
79        match self {
80            Self::Argument {
81                position,
82                op,
83                expected,
84                value,
85            } => format!(
86                "The {position} argument of {op} should be a {expected}, but instead it is:\n{value}"
87            ),
88            Self::WrongValue {
89                op,
90                expected,
91                value,
92            } => {
93                format!("Applying {op} to the following value,\nwhich is not {expected}:\n{value}")
94            }
95            Self::JavaOverride { method, message } => format!(
96                "Attempted to apply the operator overridden by the Java method\n{method},\n\
97                 but it produced the following error:\n{message}"
98            ),
99            Self::Value(e) => e.message().to_owned(),
100        }
101    }
102}
103
104impl fmt::Display for RandomError {
105    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
106        write!(f, "TLC error {}: {}", self.tlc_code(), self.message())
107    }
108}
109
110impl std::error::Error for RandomError {}
111
112type Result<T> = std::result::Result<T, RandomError>;
113
114/// `Values.ppr(v.toString())`.
115fn ppr(v: &Value, ctx: Ctx) -> String {
116    print_value(v, ctx).unwrap_or_else(|_| to_tlc_string_lenient(v, ctx))
117}
118
119/// A value-layer error raised inside an override. TLC's `GENERAL` errors are
120/// `Assert.fail`s, not `EvalException`s, so the override reports them as
121/// `TLC_MODULE_VALUE_JAVA_METHOD_OVERRIDE`; errors with their own class pass through.
122fn in_override(method: &'static str) -> impl Fn(ValueError) -> RandomError {
123    move |e| match e.kind() {
124        ErrorKind::DiveLimit | ErrorKind::Codec | ErrorKind::Json | ErrorKind::Unsupported => {
125            RandomError::Value(e)
126        }
127        k if k.tlc_code() == 1000 => RandomError::JavaOverride {
128            method,
129            message: e.message().to_owned(),
130        },
131        _ => RandomError::Value(e),
132    }
133}
134
135/// Infinite sets: TLC's `toSetEnum` gives `null` for them, and `isFinite` is false.
136fn is_infinite_set(s: &Set) -> bool {
137    matches!(s.kind(), SetKind::Nat | SetKind::Int | SetKind::Strings) || s.is_infinite()
138}
139
140fn dive_limit(what: &str) -> RandomError {
141    RandomError::Value(ValueError::new(
142        ErrorKind::DiveLimit,
143        format!("{what} is outside the 32-bit range that TLC's random operators support"),
144    ))
145}
146
147fn to_i32_size(n: u64) -> Result<i32> {
148    i32::try_from(n).map_err(|_| dive_limit(&format!("a set of {n} elements")))
149}
150
151// ---------------------------------------------------------------------------------
152// RandomElement
153// ---------------------------------------------------------------------------------
154
155/// `RandomElement(S)`: a pseudo-random element of the finite set `S`
156/// (`tlc2.module.TLC.RandomElement`).
157///
158/// It draws exactly as TLC does, so with a [`JavaRandom`](super::JavaRandom) stream
159/// seeded as TLC seeds it, the result is TLC's:
160/// - `[D -> R]`: one `RandomElement(R)` per element of `D`, in normalized order;
161/// - `[f1 : S1, ...]`: one per field, in TLC's field order;
162/// - `S1 \X ... \X Sn`: one per component;
163/// - `a..b`: `a + floor(nextDouble() * (b - a + 1))`;
164/// - any other finite set: element `floor(nextDouble() * |S|)` of its normalized
165///   enumeration.
166///
167/// # Errors
168/// TLC's: `TLC_MODULE_APPLYING_TO_WRONG_VALUE` for a non-set or an infinite set, and
169/// `TLC_MODULE_VALUE_JAVA_METHOD_OVERRIDE` for an empty set (after a draw, as in
170/// TLC) and for enumeration errors.
171pub fn random_element(set: &Value, ctx: Ctx, src: &mut dyn RandomSource) -> Result<Value> {
172    let wrap = in_override(RANDOM_ELEMENT_METHOD);
173    let wrong = |v: &Value| RandomError::WrongValue {
174        op: "RandomElement",
175        expected: "a finite set",
176        value: ppr(v, ctx),
177    };
178    let Value::Set(s) = set else {
179        return Err(wrong(set));
180    };
181    if let Some((dom, range)) = s.as_fcn_set() {
182        let dom_elems = match dom {
183            Value::Set(d) if !is_infinite_set(d) => d.elements(ctx).map_err(&wrap)?,
184            _ => return Err(wrong(set)),
185        };
186        let mut pairs = Vec::with_capacity(dom_elems.len());
187        for d in dom_elems.iter() {
188            pairs.push((d.clone(), random_element(range, ctx, src)?));
189        }
190        return Value::fcn(pairs, ctx).map_err(&wrap);
191    }
192    if let Some(fields) = s.as_rcd_set() {
193        let mut out: Vec<(Atom, Value)> = Vec::with_capacity(fields.len());
194        for (name, field_set) in fields {
195            out.push((name.clone(), random_element(field_set, ctx, src)?));
196        }
197        return Value::record(out, ctx).map_err(&wrap);
198    }
199    if let Some(factors) = s.as_product() {
200        let mut out = Vec::with_capacity(factors.len());
201        for f in factors {
202            out.push(random_element(f, ctx, src)?);
203        }
204        return Ok(Value::tuple(out));
205    }
206    if is_infinite_set(s) {
207        return Err(wrong(set));
208    }
209    if let Some((lo, _)) = s.as_interval() {
210        let size = s.size(ctx).map_err(&wrap)?;
211        let idx = src.next_index(size);
212        if idx >= size {
213            return Err(RandomError::JavaOverride {
214                method: RANDOM_ELEMENT_METHOD,
215                message: format!(
216                    "Attempted to retrieve out-of-bounds element from the interval value {}.",
217                    ppr(set, ctx)
218                ),
219            });
220        }
221        let v = lo
222            .add(&Int::from(idx.cast_signed()), ctx.int_mode)
223            .map_err(&wrap)?;
224        return Ok(Value::int(v));
225    }
226    let elems = s.elements(ctx).map_err(&wrap)?;
227    let len = elems.len() as u64;
228    let idx = src.next_index(len);
229    usize::try_from(idx)
230        .ok()
231        .and_then(|i| elems.get(i))
232        .cloned()
233        .ok_or_else(|| RandomError::JavaOverride {
234            method: RANDOM_ELEMENT_METHOD,
235            // Java's ArrayIndexOutOfBoundsException text. TLC's length is the
236            // backing array's capacity, 0 for literal and most other empty sets.
237            message: format!("Index {idx} out of bounds for length {len}"),
238        })
239}
240
241// ---------------------------------------------------------------------------------
242// RandomSubset
243// ---------------------------------------------------------------------------------
244
245/// `RandomSubset(k, S)`: `k` pseudo-random elements of the finite set `S`, without
246/// repetition while `k <= |S|` (`tlc2.module.Randomization.RandomSubset`, through
247/// `getRandomSubset` of each set class). For `k > |S|` the indices wrap around and the
248/// result is all of `S`, as in TLC.
249///
250/// The result is unnormalized, as TLC builds it (`new SetEnumValue(vec, false)`).
251///
252/// # Errors
253/// TLC's: `TLC_MODULE_ARGUMENT_ERROR` when `k` is not an integer or `S` not a finite
254/// set; `TLC_MODULE_VALUE_JAVA_METHOD_OVERRIDE` for `k < 0` (Java's
255/// `NegativeArraySizeException`) and enumeration errors.
256pub fn random_subset(
257    k: &Value,
258    set: &Value,
259    ctx: Ctx,
260    src: &mut dyn RandomSource,
261) -> Result<Value> {
262    let wrap = in_override(RANDOM_SUBSET_METHOD);
263    let Some(k_int) = k.as_int() else {
264        return Err(RandomError::Argument {
265            position: "first",
266            op: "RandomSubset",
267            expected: "nonnegative integer".to_owned(),
268            value: ppr(k, ctx),
269        });
270    };
271    let not_finite = || RandomError::Argument {
272        position: "second",
273        op: "RandomSubset",
274        expected: "a finite set".to_owned(),
275        value: ppr(set, ctx),
276    };
277    let Value::Set(s) = set else {
278        return Err(not_finite());
279    };
280    if is_infinite_set(s) {
281        return Err(not_finite());
282    }
283    let k = k_int
284        .to_i32()
285        .ok_or_else(|| dive_limit(&format!("RandomSubset's count {k_int}")))?;
286    let negative = || RandomError::JavaOverride {
287        method: RANDOM_SUBSET_METHOD,
288        message: k.to_string(),
289    };
290
291    if s.as_fcn_set().is_some() || s.as_rcd_set().is_some() || s.as_product().is_some() {
292        if k < 0 {
293            return Err(negative());
294        }
295        return product_subset(k, set, s, ctx, src);
296    }
297    if let Some((lo, _)) = s.as_interval() {
298        if k < 0 {
299            return Err(negative());
300        }
301        let n = to_i32_size(s.size(ctx).map_err(&wrap)?)?;
302        let mut indices = SubsetIndices::new(k, n, src);
303        let mut out = Vec::new();
304        while let Some(i) = indices.next_index() {
305            let v = lo
306                .add(
307                    &Int::from(i64::try_from(i).unwrap_or(i64::MAX)),
308                    ctx.int_mode,
309                )
310                .map_err(&wrap)?;
311            out.push(Value::int(v));
312        }
313        return Ok(Value::set_raw(out, ctx));
314    }
315    // `SetEnumValue.getRandomSubset` fails on a negative count before it normalizes;
316    // every other enumerable set goes through `toSetEnum` first, which enumerates.
317    if k < 0 && matches!(s.kind(), SetKind::Enum | SetKind::Raw) {
318        return Err(negative());
319    }
320    let elems = s.elements(ctx).map_err(&wrap)?;
321    if k < 0 {
322        return Err(negative());
323    }
324    let n = to_i32_size(elems.len() as u64)?;
325    let mut indices = SubsetIndices::new(k, n, src);
326    let mut out = Vec::new();
327    while let Some(i) = indices.next_index() {
328        if let Some(v) = elems.get(i) {
329            out.push(v.clone());
330        }
331    }
332    Ok(Value::set_raw(out, ctx))
333}
334
335/// The constituents of `[D -> R]`, `[f : S, ...]` or `S1 \X ... \X Sn` as TLC's
336/// `SetOfFcnsOrRcdsValue.Product` reports them, most significant first, and how to
337/// build an element from one value per constituent.
338enum Product {
339    Fcn(std::sync::Arc<[Value]>),
340    Rcd(Vec<Atom>),
341    Tuple,
342}
343
344fn product_subset(
345    count: i32,
346    whole: &Value,
347    set: &Set,
348    ctx: Ctx,
349    src: &mut dyn RandomSource,
350) -> Result<Value> {
351    let wrap = in_override(RANDOM_SUBSET_METHOD);
352    if tlc::is_empty(whole, ctx).map_err(&wrap)? {
353        return Ok(Value::set_raw(Vec::new(), ctx));
354    }
355    let elems_of = |v: &Value| -> Result<std::sync::Arc<[Value]>> {
356        match v {
357            Value::Set(c) => c.elements(ctx).map_err(&wrap),
358            _ => Err(RandomError::Argument {
359                position: "second",
360                op: "RandomSubset",
361                expected: "a finite set".to_owned(),
362                value: ppr(whole, ctx),
363            }),
364        }
365    };
366    let (shape, constituents): (Product, Vec<std::sync::Arc<[Value]>>) =
367        if let Some((dom, range)) = set.as_fcn_set() {
368            let domain = elems_of(dom)?;
369            let range = elems_of(range)?;
370            let c = vec![range; domain.len()];
371            (Product::Fcn(domain), c)
372        } else if let Some(fields) = set.as_rcd_set() {
373            let names = fields.iter().map(|(n, _)| n.clone()).collect();
374            let c = fields
375                .iter()
376                .map(|(_, f)| elems_of(f))
377                .collect::<Result<Vec<_>>>()?;
378            (Product::Rcd(names), c)
379        } else {
380            let factors = set.as_product().unwrap_or(&[]);
381            let c = factors.iter().map(elems_of).collect::<Result<Vec<_>>>()?;
382            (Product::Tuple, c)
383        };
384    let build = |values: Vec<Value>| -> Result<Value> {
385        match &shape {
386            Product::Fcn(d) => {
387                Value::fcn(d.iter().cloned().zip(values).collect(), ctx).map_err(&wrap)
388            }
389            Product::Rcd(names) => {
390                Value::record(names.iter().cloned().zip(values).collect(), ctx).map_err(&wrap)
391            }
392            Product::Tuple => Ok(Value::tuple(values)),
393        }
394    };
395    // The size, and TLC's `needBigInteger`: whether it exceeds an int.
396    let mut size = BigInt::from(1);
397    for c in &constituents {
398        size *= BigInt::from(c.len());
399    }
400    let mut out = Vec::new();
401    if let Some(n) = size.to_i32() {
402        // `SubsetEnumerator`: indices in mixed radix, rescaled by the product of the
403        // sizes of the less significant constituents.
404        let mut rescale = vec![1usize; constituents.len()];
405        let mut acc = 1usize;
406        for i in (0..constituents.len()).rev() {
407            rescale[i] = acc;
408            acc = acc.saturating_mul(constituents[i].len());
409        }
410        let mut indices = SubsetIndices::new(count, n, src);
411        while let Some(idx) = indices.next_index() {
412            let values = constituents
413                .iter()
414                .zip(&rescale)
415                .map(|(c, r)| c[(idx / r) % c.len()].clone())
416                .collect();
417            out.push(build(values)?);
418        }
419    } else {
420        let mut rescale = vec![BigInt::from(1); constituents.len()];
421        let mut acc = BigInt::from(1);
422        for i in (0..constituents.len()).rev() {
423            rescale[i].clone_from(&acc);
424            acc *= BigInt::from(constituents[i].len());
425        }
426        let mut indices = BigIndices::new(count, size, src);
427        while let Some(idx) = indices.next_index() {
428            let values = constituents
429                .iter()
430                .zip(&rescale)
431                .map(|(c, r)| c[big_digit(&idx, r, c.len())].clone())
432                .collect();
433            out.push(build(values)?);
434        }
435    }
436    Ok(Value::set_raw(out, ctx))
437}
438
439// ---------------------------------------------------------------------------------
440// RandomSetOfSubsets
441// ---------------------------------------------------------------------------------
442
443/// `RandomSetOfSubsets(k, n, S)`: `k` pseudo-random subsets of `S`, each containing
444/// each element of `S` with probability `n / |S|`, duplicates removed
445/// (`tlc2.module.Randomization.RandomSetOfSubsets`, `SubsetValue.getRandomSetOfSubsets`
446/// with `CoinTossingSubsetEnumerator`). Draws `k * |S|` doubles, in pick order and the
447/// normalized order of `S`.
448///
449/// The result is unnormalized, as in TLC. TLC orders it by a Java `HashSet`; dive keeps
450/// the first occurrence of each subset in pick order. No TLA+ operation observes the
451/// difference: the elements are mutually comparable subsets of `S`, and TLC
452/// normalizes before printing, choosing or comparing elementwise.
453///
454/// # Errors
455/// TLC's `TLC_MODULE_ARGUMENT_ERROR`s, in TLC's order of checks.
456pub fn random_set_of_subsets(
457    k: &Value,
458    n: &Value,
459    set: &Value,
460    ctx: Ctx,
461    src: &mut dyn RandomSource,
462) -> Result<Value> {
463    const OP: &str = "RandomSetOfSubsets";
464    let wrap = in_override(RANDOM_SET_OF_SUBSETS_METHOD);
465    let arg = |position: &'static str, expected: &str, value: String| RandomError::Argument {
466        position,
467        op: OP,
468        expected: expected.to_owned(),
469        value,
470    };
471    let nonneg = |position: &'static str, v: &Value| -> Result<i32> {
472        match v.as_int() {
473            Some(i) if !i.is_negative() => i
474                .to_i32()
475                .ok_or_else(|| dive_limit(&format!("{OP}'s {position} argument {i}"))),
476            _ => Err(arg(position, "nonnegative integer", ppr(v, ctx))),
477        }
478    };
479    let picks = nonneg("first", k)?;
480    let mean = nonneg("second", n)?;
481    let s = match set {
482        Value::Set(s) if !is_infinite_set(s) => s,
483        _ => return Err(arg("third", "finite set", ppr(set, ctx))),
484    };
485    let size = s.size(ctx).map_err(&wrap)?;
486    // `31 - numberOfLeadingZeros(k) + 1 > size && k > (1 << size)`.
487    let bits = u64::from(32 - picks.leading_zeros());
488    if bits > size && i64::from(picks) > (1i64 << size) {
489        return Err(arg(
490            "first",
491            &format!("nonnegative integer that is smaller than the subset's size of 2^{size}"),
492            picks.to_string(),
493        ));
494    }
495    if size < u64::from(mean.unsigned_abs()) {
496        return Err(arg(
497            "second",
498            "nonnegative integer in range 0..Cardinality(S)",
499            ppr(n, ctx),
500        ));
501    }
502    #[allow(
503        clippy::cast_precision_loss,
504        reason = "TLC: (1d * n) / ev.size(), int size"
505    )]
506    let probability = f64::from(mean) / size as f64;
507    let elems = s.elements(ctx).map_err(&wrap)?;
508    let mut subsets: Vec<Value> = Vec::new();
509    #[allow(
510        clippy::mutable_key_type,
511        reason = "Value's interior mutability is caches that never change its Hash or Eq (ADR 0012)"
512    )]
513    let mut seen: HashSet<Value> = HashSet::new();
514    for _ in 0..picks {
515        let mut chosen = Vec::new();
516        for e in elems.iter() {
517            if src.next_double() < probability {
518                chosen.push(e.clone());
519            }
520        }
521        let subset = Value::set_raw(chosen, ctx);
522        if seen.insert(subset.clone()) {
523            subsets.push(subset);
524        }
525    }
526    Ok(Value::set_raw(subsets, ctx))
527}
528
529#[cfg(test)]
530mod tests {
531    use super::*;
532    use crate::random::JavaRandom;
533
534    #[test]
535    fn negative_count_on_an_enumerated_set_fails_before_normalizing() {
536        // `RandomSubset(-1, {1, "a"})`: TLC's `new ValueVec(-1)` throws before
537        // `{1, "a"}` is normalized (which would fail comparing 1 with "a").
538        let ctx = Ctx::tlc();
539        let names = dive_value::Interner::new();
540        let s = Value::set_raw(vec![Value::from(1), Value::string(&names, "a")], ctx);
541        let mut r = JavaRandom::new(0);
542        let before = r;
543        let err = random_subset(&Value::from(-1), &s, ctx, &mut r);
544        let err = err.err().map(|e| (e.tlc_code(), e.message()));
545        assert_eq!(err.as_ref().map(|e| e.0), Some(2154));
546        assert!(err.is_some_and(|e| e.1.ends_with("\n-1")));
547        assert_eq!(r, before, "no draw");
548    }
549}