1use 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
15pub const RANDOM_ELEMENT_METHOD: &str =
17 "public static tlc2.value.impl.Value tlc2.module.TLC.RandomElement(tlc2.value.impl.Value)";
18pub const RANDOM_SUBSET_METHOD: &str = "public static tlc2.value.impl.Value \
20 tlc2.module.Randomization.RandomSubset(tlc2.value.impl.Value,tlc2.value.impl.Value)";
21pub 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#[derive(Clone, Debug, PartialEq, Eq)]
28pub enum RandomError {
29 Argument {
32 position: &'static str,
34 op: &'static str,
36 expected: String,
38 value: String,
40 },
41 WrongValue {
44 op: &'static str,
46 expected: &'static str,
48 value: String,
50 },
51 JavaOverride {
55 method: &'static str,
57 message: String,
59 },
60 Value(ValueError),
62}
63
64impl RandomError {
65 #[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 #[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
114fn ppr(v: &Value, ctx: Ctx) -> String {
116 print_value(v, ctx).unwrap_or_else(|_| to_tlc_string_lenient(v, ctx))
117}
118
119fn 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
135fn 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
151pub 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 message: format!("Index {idx} out of bounds for length {len}"),
238 })
239}
240
241pub 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 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
335enum 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 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 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
439pub 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 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 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}