Repository: lalrpop/lalrpop (language: rust)

Issue:
Our CI has a non-deterministic test
              I'm having a little trouble reproducing it. Apparently that test case does some random testing? https://github.com/lalrpop/lalrpop/blob/ab154926da43fbbb9107bd374cef4159aff1fa4c/lalrpop/src/lr1/build/test.rs#L167

I'm interested in random testing in general, but it might not be great to have it in CI.

There might even be a comment about this failure mode? https://github.com/lalrpop/lalrpop/blob/ab154926da43fbbb9107bd374cef4159aff1fa4c/lalrpop/src/generate.rs#L13-L27

Since the call stack was exceeded, we didn't get a printout.

_Originally posted by @Pat-Lafon in https://github.com/lalrpop/lalrpop/issues/993#issuecomment-2484091509_
            


Discussion / hints:
I see in the git blame that there is even a commit lowering this enumeration depth most likely because the previous maintainer hit a similar issue. https://github.com/lalrpop/lalrpop/commit/e932f811a6598a70b93c917fc3ada9e7a5a303c6

My guess is that the limit is still too high for the ci systems that you occasionally get unlucky?
> My guess is that the limit is still too high for the ci systems that you occasionally get unlucky?

Yeah, that makes sense.

I think we should make the test deterministic by seeding the rng, and then add some additional iterations to get broader coverage since it will run the same thing every time.  That way any failures will be deterministic.  It would be nice to do some offline runs with with previously untested seeds for broader coverage like a fuzzer would do, but that requires some way to identify "interesting" seeds so that those can get added to the regression suite, and I'm not sure how far down that road we want to run.  Something like `cargo fuzz` needs to treat your code as more of a black box, and I don't think supports running on unit tests on private functions like this - primarily because of the need to instrument code coverage.

In terms of seeding the rng, the existing rng seems to not support manual seeding (https://rust-random.github.io/rand/rand/rngs/struct.ThreadRng.html), so we'd want to switch out to one of the other rngs supported by `rand` if we want to go the seeding route.

Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index 4abaa6c22..61a134070 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -235,6 +235,7 @@ dependencies = [
  "petgraph",
  "pico-args",
  "rand",
+ "rand_chacha",
  "regex",
  "regex-syntax",
  "sha3",
diff --git a/lalrpop/Cargo.toml b/lalrpop/Cargo.toml
index 38e1c6e3c..b2df349a7 100644
--- a/lalrpop/Cargo.toml
+++ b/lalrpop/Cargo.toml
@@ -23,7 +23,9 @@ doctest = false
 ascii-canvas = { version = "4.0", default-features = false }
 bit-set = { version = "0.8", default-features = false }
 ena = { version = "0.14", default-features = false }
-itertools = { version = "0.13", default-features = false, features = ["use_std"] }
+itertools = { version = "0.13", default-features = false, features = [
+    "use_std",
+] }
 petgraph = { version = "0.6", default-features = false }
 regex = { workspace = true }
 regex-syntax = { workspace = true }
@@ -42,9 +44,10 @@ lalrpop-util = { path = "../lalrpop-util", version = "0.22.0", default-features
 [dev-dependencies]
 diff = { workspace = true }
 rand = "0.8"
+rand_chacha = "0.3.1"
 
 [features]
-default=["lexer", "unicode", "pico-args"]
+default = ["lexer", "unicode", "pico-args"]
 unicode = ["regex/unicode", "regex-syntax/unicode", "lalrpop-util/unicode"]
 lexer = ["lalrpop-util/lexer", "lalrpop-util/std"]
 
diff --git a/lalrpop/src/generate.rs b/lalrpop/src/generate.rs
index e110846de..0be2119ea 100644
--- a/lalrpop/src/generate.rs
+++ b/lalrpop/src/generate.rs
@@ -1,7 +1,7 @@
 //! Generate valid parse trees.
 
 use crate::grammar::repr::*;
-use rand::{self, Rng};
+use rand::prelude::*;
 use std::iter::Iterator;
 
 #[derive(PartialEq, Eq)]
@@ -10,10 +10,14 @@ pub enum ParseTree {
     Terminal(TerminalString),
 }
 
-pub fn random_parse_tree(grammar: &Grammar, symbol: NonterminalString) -> ParseTree {
+pub fn random_parse_tree(
+    grammar: &Grammar,
+    symbol: NonterminalString,
+    rng: &mut rand_chacha::ChaCha8Rng,
+) -> ParseTree {
     let mut gen = Generator {
         grammar,
-        rng: rand::thread_rng(),
+        rng,
         depth: 0,
     };
     loop {
@@ -26,15 +30,15 @@ pub fn random_parse_tree(grammar: &Grammar, symbol: NonterminalString) -> ParseT
     }
 }
 
-struct Generator<'grammar> {
+struct Generator<'grammar, 'rng> {
     grammar: &'grammar Grammar,
-    rng: rand::rngs::ThreadRng,
+    rng: &'rng mut rand_chacha::ChaCha8Rng,
     depth: u32,
 }
 
 const MAX_DEPTH: u32 = 7000;
 
-impl Generator<'_> {
+impl Generator<'_, '_> {
     fn nonterminal(&mut self, nt: NonterminalString) -> Option<ParseTree> {
         if self.depth > MAX_DEPTH {
             return None;


Test patch:
diff --git a/lalrpop/src/lr1/build/test.rs b/lalrpop/src/lr1/build/test.rs
index 31898c1e6..026075007 100644
--- a/lalrpop/src/lr1/build/test.rs
+++ b/lalrpop/src/lr1/build/test.rs
@@ -7,6 +7,7 @@ use crate::lr1::lookahead::TokenSet;
 use crate::lr1::tls::Lr1Tls;
 use crate::test_util::{compare, expect_debug, normalized_grammar};
 use crate::tls::Tls;
+use rand::SeedableRng;
 use string_cache::DefaultAtom as Atom;
 
 use super::{build_lr0_states, build_lr1_states, use_lane_table, Lr};
@@ -15,11 +16,13 @@ fn nt(t: &str) -> NonterminalString {
     NonterminalString(Atom::from(t))
 }
 
-const ITERATIONS: usize = 22;
+const ITERATIONS: usize = 96;
 
 fn random_test<'g>(grammar: &Grammar, states: &'g [Lr1State<'g>], start_symbol: NonterminalString) {
+    let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(0);
+
     for i in 0..ITERATIONS {
-        let input_tree = generate::random_parse_tree(grammar, start_symbol.clone());
+        let input_tree = generate::random_parse_tree(grammar, start_symbol.clone(), &mut rng);
         let output_tree = interpret(states, input_tree.terminals()).unwrap();
 
         println!("test {}", i);