No public description PiperOrigin-RevId: 998678837
diff --git a/rust/src/domains/arbitrary.rs b/rust/src/domains/arbitrary.rs index 326e16a..df1023b 100644 --- a/rust/src/domains/arbitrary.rs +++ b/rust/src/domains/arbitrary.rs
@@ -13,10 +13,12 @@ // limitations under the License. use super::utility::choose_value; +use super::utility::map_char_to_int; +use super::utility::map_int_to_char; use super::utility::mutate_integer; use super::utility::shrink_towards; +use super::utility::NUM_VALID_CODEPOINTS; use super::Domain; -use std::char; use std::fmt; use std::marker::PhantomData; @@ -240,43 +242,6 @@ impl_domain_for_float!(f32); impl_domain_for_float!(f64); -const SURROGATE_START: u32 = 0xD800; -const SURROGATE_END: u32 = 0xDFFF; -const MAX_VALID_CODEPOINT: u32 = 0x10FFFF; -const NUM_VALID_CODEPOINTS: u32 = MAX_VALID_CODEPOINT - (SURROGATE_END - SURROGATE_START); - -/// Maps a `char` to a `u32` in a contiguous range. -/// -/// Rust's `char` type represents a Unicode Scalar Value, which means it cannot be a -/// surrogate code point (U+D800 to U+DFFF). This function maps `char` values to a -/// contiguous integer range by shifting down the code points that are above the -/// surrogate range. This is useful for mutation strategies like random walks over -/// a dense integer space. -fn map_char_to_int(c: char) -> u32 { - let val = c as u32; - if val >= SURROGATE_START { - val - (SURROGATE_END - SURROGATE_START + 1) - } else { - val - } -} - -/// Maps a `u32` from the contiguous range back to a `char`. -/// -/// This is the inverse of `map_char_to_int`. It converts an integer from the -/// dense range back to a `char`. Integers that fall within the range previously -/// occupied by surrogates are shifted up to their correct code points. -fn map_int_to_char(u: u32) -> char { - assert!( - u < NUM_VALID_CODEPOINTS, - "input to map_int_to_char out of range: got {}, expected value < {}", - u, - NUM_VALID_CODEPOINTS - ); - let val = if u >= SURROGATE_START { u + (SURROGATE_END - SURROGATE_START + 1) } else { u }; - char::from_u32(val).unwrap() -} - impl Domain for Arbitrary<char> { type UserValue<'user> = char; type CorpusValue = char; @@ -768,25 +733,6 @@ } #[test] - fn test_char_mapping() { - // Test boundary conditions and values around the surrogate range - assert_eq!(map_char_to_int('\u{0000}'), 0); - assert_eq!(map_int_to_char(0), '\u{0000}'); - - let before_surrogate = SURROGATE_START - 1; - assert_eq!(map_char_to_int(char::from_u32(before_surrogate).unwrap()), before_surrogate); - assert_eq!(map_int_to_char(before_surrogate), char::from_u32(before_surrogate).unwrap()); - - let after_surrogate = SURROGATE_END + 1; - let mapped_after_surrogate = map_char_to_int(char::from_u32(after_surrogate).unwrap()); - assert_eq!(mapped_after_surrogate, SURROGATE_START); - assert_eq!(map_int_to_char(SURROGATE_START), char::from_u32(after_surrogate).unwrap()); - - assert_eq!(map_char_to_int('\u{10FFFF}'), NUM_VALID_CODEPOINTS - 1); - assert_eq!(map_int_to_char(NUM_VALID_CODEPOINTS - 1), '\u{10FFFF}'); - } - - #[test] fn test_char_shrink_to_null() { for _ in 0..10 { let mut domain = Arbitrary::<char>::default();
diff --git a/rust/src/domains/range.rs b/rust/src/domains/range.rs index 24208de..0adb0af 100644 --- a/rust/src/domains/range.rs +++ b/rust/src/domains/range.rs
@@ -12,11 +12,17 @@ // See the License for the specific language governing permissions and // limitations under the License. +use super::utility::map_char_to_int; +use super::utility::map_int_to_char; +use super::utility::mutate_float; +use super::utility::mutate_integer; +use super::utility::shrink_towards; +use super::utility::SpecialValues; use super::Domain; +use std::fmt::Display; use anyhow; -use rand::distr::uniform::SampleUniform; -use rand::distr::uniform::UniformSampler; +use rand::RngExt; /// Generates values of type `T` in a given range. /// @@ -37,28 +43,269 @@ /// assert!(sample >= 21); /// assert!(sample <= 73); /// ``` +#[derive(Debug, Clone, Copy)] pub struct InRange<T> { lower: T, upper: T, } -impl InRange<i32> { - pub fn new(lower: i32, upper: i32) -> Self { - Self { lower, upper } - } +pub(crate) trait DomainRangeBounds { + fn validate(lower: &Self, upper: &Self); + fn shrinking_target(lower: &Self, upper: &Self) -> Self + where + Self: Sized; +} - pub fn get_in_range(&self, rng: &mut dyn rand::Rng) -> i32 { - <i32 as SampleUniform>::Sampler::sample_single(self.lower, self.upper, rng) - .expect("Failed to sample from Uniform distribution") +macro_rules! impl_domain_range_bounds_for_integer { + ($($ty:ty),*) => { + $( + impl DomainRangeBounds for $ty { + fn validate(lower: &Self, upper: &Self) { + assert!(lower <= upper, "InRange: lower bound {} must be <= upper bound {}", lower, upper); + } + fn shrinking_target(lower: &Self, upper: &Self) -> Self { + #[allow(unused_comparisons)] + if *lower <= 0 && *upper >= 0 { + 0 + } else if *lower > 0 { + *lower + } else { + *upper + } + } + } + )* + }; +} + +impl_domain_range_bounds_for_integer!( + i8, u8, i16, u16, i32, u32, i64, u64, i128, u128, isize, usize +); + +macro_rules! impl_domain_range_bounds_for_float { + ($($ty:ty),*) => { + $( + impl DomainRangeBounds for $ty { + fn validate(lower: &Self, upper: &Self) { + assert!(lower <= upper, "InRange: lower bound {} must be <= upper bound {}", lower, upper); + // Rejects both overflowing finite ranges and infinite bounds (including + // `lower == upper == ±INFINITY`, where `upper - lower` is `NaN`), matching + // C++ `InRangeImpl` and `rand`'s `UniformFloat` finite-bound requirement. + assert!((*upper - *lower).is_finite(), "Range is too large!"); + } + fn shrinking_target(lower: &Self, upper: &Self) -> Self { + if *lower <= 0.0 && *upper >= 0.0 { + 0.0 + } else if *lower > 0.0 { + *lower + } else { + *upper + } + } + } + )* + }; +} + +impl_domain_range_bounds_for_float!(f32, f64); + +impl DomainRangeBounds for char { + fn validate(lower: &Self, upper: &Self) { + assert!(lower <= upper, "InRange: lower bound {} must be <= upper bound {}", lower, upper); + } + fn shrinking_target(lower: &Self, _upper: &Self) -> Self { + *lower } } -impl Domain for InRange<i32> { - type UserValue<'user> = i32; - type CorpusValue = i32; +#[allow(private_bounds)] +impl<T> InRange<T> +where + T: DomainRangeBounds + PartialOrd + Display, +{ + pub fn new(lower: T, upper: T) -> Self { + T::validate(&lower, &upper); + Self { lower, upper } + } +} + +macro_rules! impl_domain_for_in_range_integer { + // `rand` does not implement `SampleUniform` for `isize` (required by + // `rng.random_range`, `shrink_towards`, and `mutate_integer`), and `usize` is mapped + // through `u64` for symmetry. Casting the result back `as $ty` cannot truncate even on + // 32-bit targets because all outputs are bounded by `[lower, upper]`. + ($ty:ty, $int_ty:ty) => { + impl Domain for InRange<$ty> { + type UserValue<'user> = $ty; + type CorpusValue = $ty; + + fn init(&mut self, rng: &mut dyn rand::Rng) -> anyhow::Result<Self::CorpusValue> { + let lower = self.lower as $int_ty; + let upper = self.upper as $int_ty; + + if rng.random_bool(0.2) { + let mut specials = Vec::new(); + specials.push(self.lower); + specials.push(self.upper); + + let default_specials = <$ty as SpecialValues>::get(); + for &v in default_specials { + if v > self.lower && v < self.upper { + specials.push(v); + } + } + let idx = rng.random_range(0..specials.len()); + return Ok(specials[idx]); + } + + Ok(rng.random_range(lower..=upper) as $ty) + } + + fn mutate( + &mut self, + val: &mut Self::CorpusValue, + rng: &mut dyn rand::Rng, + only_shrink: bool, + ) -> anyhow::Result<()> { + if self.lower == self.upper { + *val = self.lower; + return Ok(()); + } + let lower = self.lower as $int_ty; + let upper = self.upper as $int_ty; + if only_shrink { + let target = <$ty>::shrinking_target(&self.lower, &self.upper) as $int_ty; + *val = shrink_towards(rng, *val as $int_ty, target) as $ty; + } else { + let range = 5; + *val = mutate_integer(rng, *val as $int_ty, range, Some(lower), Some(upper)) + as $ty; + } + Ok(()) + } + + fn corpus_to_user_value<'a>( + &self, + corpus_value: &'a Self::CorpusValue, + ) -> anyhow::Result<Self::UserValue<'a>> { + Ok(*corpus_value) + } + + fn validate_corpus_value( + &self, + corpus_value: &Self::CorpusValue, + ) -> anyhow::Result<()> { + if *corpus_value < self.lower || *corpus_value > self.upper { + anyhow::bail!( + "Value {} is out of range [{}, {}]", + corpus_value, + self.lower, + self.upper + ); + } + Ok(()) + } + } + }; +} + +impl_domain_for_in_range_integer!(i8, i8); +impl_domain_for_in_range_integer!(u8, u8); +impl_domain_for_in_range_integer!(i16, i16); +impl_domain_for_in_range_integer!(u16, u16); +impl_domain_for_in_range_integer!(i32, i32); +impl_domain_for_in_range_integer!(u32, u32); +impl_domain_for_in_range_integer!(i64, i64); +impl_domain_for_in_range_integer!(u64, u64); +impl_domain_for_in_range_integer!(i128, i128); +impl_domain_for_in_range_integer!(u128, u128); +impl_domain_for_in_range_integer!(isize, i64); +impl_domain_for_in_range_integer!(usize, u64); + +macro_rules! impl_domain_for_in_range_float { + ($ty:ty) => { + impl Domain for InRange<$ty> { + type UserValue<'user> = $ty; + type CorpusValue = $ty; + + fn init(&mut self, rng: &mut dyn rand::Rng) -> anyhow::Result<Self::CorpusValue> { + if rng.random_bool(0.2) { + let mut specials = Vec::new(); + specials.push(self.lower); + specials.push(self.upper); + + let default_specials = <$ty as SpecialValues>::get(); + for &v in default_specials { + if v > self.lower && v < self.upper { + specials.push(v); + } + } + let idx = rng.random_range(0..specials.len()); + return Ok(specials[idx]); + } + + Ok(rng.random_range(self.lower..=self.upper)) + } + + fn mutate( + &mut self, + val: &mut Self::CorpusValue, + rng: &mut dyn rand::Rng, + only_shrink: bool, + ) -> anyhow::Result<()> { + mutate_float(rng, val, only_shrink, Some((self.lower, self.upper))) + } + + fn corpus_to_user_value<'a>( + &self, + corpus_value: &'a Self::CorpusValue, + ) -> anyhow::Result<Self::UserValue<'a>> { + Ok(*corpus_value) + } + + fn validate_corpus_value( + &self, + corpus_value: &Self::CorpusValue, + ) -> anyhow::Result<()> { + if corpus_value.is_nan() || *corpus_value < self.lower || *corpus_value > self.upper + { + anyhow::bail!( + "Value {} is out of range [{}, {}]", + corpus_value, + self.lower, + self.upper + ); + } + Ok(()) + } + } + }; +} + +impl_domain_for_in_range_float!(f32); +impl_domain_for_in_range_float!(f64); + +impl Domain for InRange<char> { + type UserValue<'user> = char; + type CorpusValue = char; fn init(&mut self, rng: &mut dyn rand::Rng) -> anyhow::Result<Self::CorpusValue> { - Ok(self.get_in_range(rng)) + if rng.random_bool(0.2) { + let mut specials = Vec::new(); + specials.push(self.lower); + specials.push(self.upper); + + let default_specials = <char as SpecialValues>::get(); + for &v in default_specials { + if v > self.lower && v < self.upper { + specials.push(v); + } + } + let idx = rng.random_range(0..specials.len()); + return Ok(specials[idx]); + } + + Ok(rng.random_range(self.lower..=self.upper)) } fn mutate( @@ -67,10 +314,23 @@ rng: &mut dyn rand::Rng, only_shrink: bool, ) -> anyhow::Result<()> { + if self.lower == self.upper { + *val = self.lower; + return Ok(()); + } if only_shrink { - *val -= 1; + let target = <char>::shrinking_target(&self.lower, &self.upper); + // Pass `char` directly rather than casting to `u32` so `SampleUniform` + // compacts the UTF-16 surrogate gap (0xD800..=0xDFFF) during sampling. + *val = shrink_towards(rng, *val, target); } else { - *val = self.get_in_range(rng); + // Mutate in compacted codepoint space so random walks and bit flips never land + // in the UTF-16 surrogate gap (0xD800..=0xDFFF). + let lower = map_char_to_int(self.lower); + let upper = map_char_to_int(self.upper); + let val_int = map_char_to_int((*val).clamp(self.lower, self.upper)); + let mutated_int = mutate_integer(rng, val_int, 5, Some(lower), Some(upper)); + *val = map_int_to_char(mutated_int); } Ok(()) } @@ -97,15 +357,263 @@ #[cfg(test)] mod tests { + use std::any::type_name; + use std::fmt::Debug; + + use rand::rngs::{SmallRng, SysRng}; use rand::SeedableRng; use super::*; + fn get_rng() -> SmallRng { + SmallRng::try_from_rng(&mut SysRng).unwrap() + } + + fn test_in_range_init_property<T>(lower: T, upper: T) + where + T: DomainRangeBounds + PartialOrd + Debug + Copy + PartialEq + Display + 'static, + InRange<T>: Domain<CorpusValue = T>, + { + let mut range = InRange::new(lower, upper); + let mut rng = get_rng(); + for _ in 0..100 { + let val = range.init(&mut rng).unwrap(); + assert!( + val >= lower && val <= upper, + "Init value {:?} out of range [{:?}, {:?}]", + val, + lower, + upper + ); + } + } + + fn test_in_range_mutate_property<T>(lower: T, upper: T) + where + T: DomainRangeBounds + PartialOrd + Debug + Copy + PartialEq + Display + 'static, + InRange<T>: Domain<CorpusValue = T>, + { + let mut range = InRange::new(lower, upper); + let mut rng = get_rng(); + let val = range.init(&mut rng).unwrap(); + let mut mutated_val = val; + let mut changed = false; + for _ in 0..100 { + let prev = mutated_val; + range.mutate(&mut mutated_val, &mut rng, false).unwrap(); + assert!( + mutated_val >= lower && mutated_val <= upper, + "Mutated value {:?} out of range [{:?}, {:?}]", + mutated_val, + lower, + upper + ); + if mutated_val != prev { + changed = true; + } + } + assert!( + changed, + "Value did not change after 100 mutations for type {:?}", + type_name::<T>() + ); + } + + fn test_in_range_shrink_property<T>(lower: T, upper: T) + where + T: DomainRangeBounds + PartialOrd + Debug + Copy + PartialEq + Display + 'static, + InRange<T>: Domain<CorpusValue = T>, + { + let mut range = InRange::new(lower, upper); + let mut rng = get_rng(); + let target = T::shrinking_target(&lower, &upper); + + // Test shrinking from upper bound + let mut shrunk_val = upper; + for _ in 0..100 { + let prev = shrunk_val; + range.mutate(&mut shrunk_val, &mut rng, true).unwrap(); + assert!( + shrunk_val >= lower && shrunk_val <= upper, + "Shrunk value {:?} out of range [{:?}, {:?}]", + shrunk_val, + lower, + upper + ); + if prev > target { + assert!(shrunk_val <= prev, "Value {:?} should be <= prev {:?}", shrunk_val, prev); + assert!( + shrunk_val >= target, + "Value {:?} should be >= target {:?}", + shrunk_val, + target + ); + } + } + + // Test shrinking from lower bound + let mut shrunk_val = lower; + for _ in 0..100 { + let prev = shrunk_val; + range.mutate(&mut shrunk_val, &mut rng, true).unwrap(); + assert!( + shrunk_val >= lower && shrunk_val <= upper, + "Shrunk value {:?} out of range [{:?}, {:?}]", + shrunk_val, + lower, + upper + ); + if prev < target { + assert!(shrunk_val >= prev, "Value {:?} should be >= prev {:?}", shrunk_val, prev); + assert!( + shrunk_val <= target, + "Value {:?} should be <= target {:?}", + shrunk_val, + target + ); + } + } + } + + fn test_in_range_properties<T>(lower: T, upper: T) + where + T: DomainRangeBounds + PartialOrd + Debug + Copy + PartialEq + Display + 'static, + InRange<T>: Domain<CorpusValue = T>, + { + test_in_range_init_property(lower, upper); + test_in_range_mutate_property(lower, upper); + test_in_range_shrink_property(lower, upper); + } + #[test] - fn test_in_range() { - let in_range = InRange::<i32>::new(0, 100); - let mut rng = rand::rngs::StdRng::from_seed([73; 32]); - let in_range_val = in_range.get_in_range(&mut rng); - assert!(in_range_val >= 0 && in_range_val <= 100); + fn test_in_range_i8() { + test_in_range_properties::<i8>(-10, 10); + test_in_range_properties::<i8>(0, 100); + test_in_range_properties::<i8>(-100, -10); + } + #[test] + fn test_in_range_u8() { + test_in_range_properties::<u8>(10, 50); + } + #[test] + fn test_in_range_i16() { + test_in_range_properties::<i16>(-100, 100); + test_in_range_properties::<i16>(0, 1000); + test_in_range_properties::<i16>(-1000, -100); + } + #[test] + fn test_in_range_u16() { + test_in_range_properties::<u16>(100, 500); + } + #[test] + fn test_in_range_i32() { + test_in_range_properties::<i32>(-1000, 1000); + test_in_range_properties::<i32>(0, 10000); + test_in_range_properties::<i32>(-10000, -1000); + } + #[test] + fn test_in_range_u32() { + test_in_range_properties::<u32>(1000, 5000); + } + #[test] + fn test_in_range_i64() { + test_in_range_properties::<i64>(-10000, 10000); + test_in_range_properties::<i64>(0, 100000); + test_in_range_properties::<i64>(-100000, -10000); + } + #[test] + fn test_in_range_u64() { + test_in_range_properties::<u64>(10000, 50000); + } + #[test] + fn test_in_range_i128() { + test_in_range_properties::<i128>(-100000, 100000); + test_in_range_properties::<i128>(0, 1000000); + test_in_range_properties::<i128>(-1000000, -100000); + } + #[test] + fn test_in_range_u128() { + test_in_range_properties::<u128>(0, 200000); + test_in_range_properties::<u128>(100000, 500000); + test_in_range_properties::<u128>(1000000, 2000000); + } + #[test] + fn test_in_range_isize() { + test_in_range_properties::<isize>(-1000, 1000); + test_in_range_properties::<isize>(0, 10000); + test_in_range_properties::<isize>(-10000, -1000); + } + #[test] + fn test_in_range_usize() { + test_in_range_properties::<usize>(0, 2000); + test_in_range_properties::<usize>(1000, 5000); + test_in_range_properties::<usize>(10000, 20000); + } + #[test] + fn test_in_range_f32() { + test_in_range_properties::<f32>(-1.0, 1.0); + test_in_range_properties::<f32>(0.0, 100.0); + test_in_range_properties::<f32>(-100.0, -10.0); + test_in_range_properties::<f32>(1.0, f32::from_bits(1.0f32.to_bits() + 1)); + } + #[test] + fn test_in_range_f64() { + test_in_range_properties::<f64>(-1.0, 1.0); + test_in_range_properties::<f64>(0.0, 1.0e10); + test_in_range_properties::<f64>(-1.0e10, -1.0); + } + #[test] + fn test_in_range_char() { + test_in_range_properties::<char>('a', 'z'); + test_in_range_properties::<char>('A', 'Z'); + test_in_range_properties::<char>('0', '9'); + test_in_range_properties::<char>('\u{D700}', '\u{E100}'); + } + + #[test] + #[should_panic(expected = "InRange: lower bound")] + fn test_invalid_range_panic_integer() { + InRange::<i32>::new(10, 0); + } + + #[test] + #[should_panic(expected = "InRange: lower bound")] + fn test_invalid_range_panic_float() { + InRange::<f32>::new(1.0, 0.0); + } + + #[test] + #[should_panic(expected = "Range is too large!")] + fn test_invalid_range_panic_float_large() { + InRange::<f32>::new(-3.0e38f32, 3.0e38f32); + } + + #[test] + fn test_in_range_singleton() { + let mut rng = get_rng(); + + let mut int_range = InRange::<i32>::new(5, 5); + let mut int_val = int_range.init(&mut rng).unwrap(); + assert_eq!(int_val, 5); + int_range.mutate(&mut int_val, &mut rng, false).unwrap(); + assert_eq!(int_val, 5); + int_range.mutate(&mut int_val, &mut rng, true).unwrap(); + assert_eq!(int_val, 5); + + let mut float_range = InRange::<f64>::new(2.5, 2.5); + let mut float_val = float_range.init(&mut rng).unwrap(); + assert_eq!(float_val, 2.5); + float_range.mutate(&mut float_val, &mut rng, false).unwrap(); + assert_eq!(float_val, 2.5); + float_range.mutate(&mut float_val, &mut rng, true).unwrap(); + assert_eq!(float_val, 2.5); + + let mut char_range = InRange::<char>::new('a', 'a'); + let mut char_val = char_range.init(&mut rng).unwrap(); + assert_eq!(char_val, 'a'); + char_range.mutate(&mut char_val, &mut rng, false).unwrap(); + assert_eq!(char_val, 'a'); + char_range.mutate(&mut char_val, &mut rng, true).unwrap(); + assert_eq!(char_val, 'a'); } }
diff --git a/rust/src/domains/utility.rs b/rust/src/domains/utility.rs index e14bcef..cf70f56 100644 --- a/rust/src/domains/utility.rs +++ b/rust/src/domains/utility.rs
@@ -60,9 +60,9 @@ /// Mutates an integer value using one of several strategies. /// /// The mutation strategies are: -/// 1. Random Walk: Add/subtract a small value within the given `range`. -/// 2. Bit Flip: Flip a single random bit. -/// 3. Random Choice: Replace with a new completely random value. +/// 1. Random Walk: Add/subtract a small value within the given `range`. +/// 2. Bit Flip: Flip a single random bit. +/// 3. Random Choice: Replace with a new completely random value. /// /// # Arguments /// * `rng`: Random number generator. @@ -89,9 +89,12 @@ let min_val = min_value.unwrap_or(T::min_value()); let max_val = max_value.unwrap_or(T::max_value()); assert!( - min_val < max_val, - "mutate_integer: min_val must be strictly smaller than max_val: min={min_val}, max={max_val}" + min_val <= max_val, + "mutate_integer: min_val must be <= max_val: min={min_val}, max={max_val}" ); + if min_val == max_val { + return min_val; + } match rng.random_range(0..3) { 0 => { @@ -107,15 +110,7 @@ } 1 => { // 1/3 chance: Flip a random bit - let num_bits = size_of::<T>() * 8; - let bit_index = rng.random_range(0..num_bits); - let mask = T::one() << bit_index; - let result = val ^ mask; - if result < min_val || result > max_val { - val - } else { - result - } + bit_flip_integer(rng, val, min_val, max_val) } _ => { // 1/3 chance: Replace with a new random value @@ -124,6 +119,77 @@ } } +fn bit_flip_integer<T, R: rand::Rng + ?Sized>(rng: &mut R, val: T, lower: T, upper: T) -> T +where + T: PrimInt + Display + Copy, +{ + assert!(lower <= upper, "bit_flip_integer: lower bound must be <= upper bound"); + + // For same-sign bounds, `lower ^ upper` zeros shared high-order bits so flips stay + // within the active bit width of the interval. When the range straddles zero + // (`lower < 0 <= upper`), `lower ^ upper` has the sign bit set (`leading_zeros() == 0`), + // so bound the magnitude bit width by the active sign half and include the sign bit + // (`type_bits - 1`) as one additional candidate. This avoids sampling dead + // sign-extension bits for narrow ranges while still allowing sign-bit flips for + // full-range signed types (`Arbitrary<iN>`) and asymmetric ranges straddling zero. + let type_bits = size_of::<T>() * 8; + let bit = if lower < T::zero() && upper >= T::zero() { + let mag_width = if val >= T::zero() { + type_bits - upper.leading_zeros() as usize + } else { + type_bits - (!lower).leading_zeros() as usize + }; + let idx = rng.random_range(0..=mag_width); + if idx == mag_width { + type_bits - 1 + } else { + idx + } + } else { + let width = type_bits - (lower ^ upper).leading_zeros() as usize; + if width == 0 { + return val; + } + rng.random_range(0..width) + }; + + let next = val ^ (T::one() << bit); + if next >= lower && next <= upper { + next + } else { + val + } +} + +const SURROGATE_START: u32 = 0xD800; +const SURROGATE_END: u32 = 0xDFFF; +const MAX_VALID_CODEPOINT: u32 = 0x10FFFF; +pub(crate) const NUM_VALID_CODEPOINTS: u32 = + MAX_VALID_CODEPOINT - (SURROGATE_END - SURROGATE_START); + +/// Maps a `char` to a `u32` in a contiguous range `[0, NUM_VALID_CODEPOINTS)` by +/// shifting down code points above the UTF-16 surrogate range (`0xD800..=0xDFFF`). +pub(crate) fn map_char_to_int(c: char) -> u32 { + let val = c as u32; + if val >= SURROGATE_START { + val - (SURROGATE_END - SURROGATE_START + 1) + } else { + val + } +} + +/// Maps a `u32` from the contiguous range `[0, NUM_VALID_CODEPOINTS)` back to a `char`. +pub(crate) fn map_int_to_char(u: u32) -> char { + assert!( + u < NUM_VALID_CODEPOINTS, + "input to map_int_to_char out of range: got {}, expected value < {}", + u, + NUM_VALID_CODEPOINTS + ); + let val = if u >= SURROGATE_START { u + (SURROGATE_END - SURROGATE_START + 1) } else { u }; + char::from_u32(val).unwrap() +} + pub trait SpecialValues: Sized + Copy { fn get() -> &'static [Self]; } @@ -152,8 +218,8 @@ }; } -impl_special_values_signed!(i8, i16, i32, i64, i128); -impl_special_values_unsigned!(u8, u16, u32, u64, u128); +impl_special_values_signed!(i8, i16, i32, i64, i128, isize); +impl_special_values_unsigned!(u8, u16, u32, u64, u128, usize); macro_rules! impl_special_values_float { ($($ty:ty),*) => { @@ -194,8 +260,8 @@ /// * `rng`: Random number generator. /// /// # Type Parameters -/// * `T`: The type of the value to choose. Must implement `SpecialValues` and -/// `StandardUniform` must be able to generate values of type `T`. +/// * `T`: The type of the value to choose. Must implement `SpecialValues` and `StandardUniform` +/// must be able to generate values of type `T`. pub fn choose_value<T, R: rand::Rng + ?Sized>(rng: &mut R) -> T where T: SpecialValues + 'static, @@ -215,25 +281,83 @@ rng: &mut R, val: &mut T, only_shrink: bool, - _range: Option<(T, T)>, // TODO: Implement range support for floats. + range: Option<(T, T)>, ) -> anyhow::Result<()> where T: num_traits::Float + SampleUniform + Display + Copy + SpecialValues + 'static, StandardUniform: Distribution<T>, { + if let Some((lower, upper)) = range { + assert!(lower <= upper, "mutate_float: lower bound must be <= upper bound"); + assert!(!lower.is_nan() && !upper.is_nan(), "mutate_float: bounds cannot be NaN"); + } + if only_shrink { - // Shrink only finite, non-terminal values. - if val.is_finite() && *val != T::zero() { - *val = shrink_towards(rng, *val, T::zero()); + if val.is_finite() { + let target = if let Some((lower, upper)) = range { + if lower <= T::zero() && upper >= T::zero() { + T::zero() + } else if lower > T::zero() { + lower + } else { + upper + } + } else { + T::zero() + }; + if *val != target { + *val = shrink_towards(rng, *val, target); + } } return Ok(()); } - // Non-shrinking mutation. + + if let Some((lower, upper)) = range { + if lower == upper { + *val = lower; + return Ok(()); + } + + if !val.is_finite() || *val < lower || *val > upper { + *val = rng.random_range(lower..=upper); + return Ok(()); + } + + let original_val = *val; + // Cap retry attempts because for narrow float ranges (e.g. a few ULPs wide), + // `delta = width / 100.0` underflows relative to `*val` (`lo == hi == *val`), + // and uniform float sampling can repeatedly round to the current value. + for _ in 0..10 { + match rng.random_range(0..2) { + 0 => { + // Random Walk + let width = upper - lower; + let delta = if width > T::zero() && width.is_finite() { + width / T::from(100.0).unwrap() + } else { + T::from(1.0).unwrap() + }; + let lo = (*val - delta).max(lower); + let hi = (*val + delta).min(upper); + *val = rng.random_range(lo..=hi); + } + 1 => { + // Uniform Choice + *val = rng.random_range(lower..=upper); + } + _ => unreachable!(), + } + if *val != original_val { + return Ok(()); + } + } + *val = if original_val == lower { upper } else { lower }; + return Ok(()); + } + let original_val = *val; loop { - // Loop to ensure mutation if !val.is_finite() { - // NaN or Infinity *val = choose_value(rng); } else { match rng.random_range(0..4) { @@ -411,4 +535,59 @@ check_mutate_float::<f32>(); check_mutate_float::<f64>(); } + + #[test] + fn test_bit_flip_integer_sign_bit() { + let mut rng = get_rng(); + // Full signed range [i8::MIN, i8::MAX]: flipping the sign bit of 3 yields -125. + let mut flipped_sign_full = false; + for _ in 0..200 { + if bit_flip_integer(&mut rng, 3i8, i8::MIN, i8::MAX) == -125i8 { + flipped_sign_full = true; + break; + } + } + assert!( + flipped_sign_full, + "bit_flip_integer should be able to flip sign bit on full i8 range" + ); + + // Asymmetric range straddling zero [i8::MIN, 5]: flipping the sign bit of 3 yields -125. + let mut flipped_sign_asymmetric = false; + for _ in 0..200 { + if bit_flip_integer(&mut rng, 3i8, i8::MIN, 5i8) == -125i8 { + flipped_sign_asymmetric = true; + break; + } + } + assert!( + flipped_sign_asymmetric, + "bit_flip_integer should be able to flip sign bit on asymmetric range straddling zero" + ); + } + + #[test] + fn test_mutate_integer_singleton() { + let mut rng = get_rng(); + assert_eq!(mutate_integer(&mut rng, 5i32, 5, Some(5), Some(5)), 5); + } + + #[test] + fn test_char_mapping() { + // Test boundary conditions and values around the surrogate range + assert_eq!(map_char_to_int('\u{0000}'), 0); + assert_eq!(map_int_to_char(0), '\u{0000}'); + + let before_surrogate = SURROGATE_START - 1; + assert_eq!(map_char_to_int(char::from_u32(before_surrogate).unwrap()), before_surrogate); + assert_eq!(map_int_to_char(before_surrogate), char::from_u32(before_surrogate).unwrap()); + + let after_surrogate = SURROGATE_END + 1; + let mapped_after_surrogate = map_char_to_int(char::from_u32(after_surrogate).unwrap()); + assert_eq!(mapped_after_surrogate, SURROGATE_START); + assert_eq!(map_int_to_char(SURROGATE_START), char::from_u32(after_surrogate).unwrap()); + + assert_eq!(map_char_to_int('\u{10FFFF}'), NUM_VALID_CODEPOINTS - 1); + assert_eq!(map_int_to_char(NUM_VALID_CODEPOINTS - 1), '\u{10FFFF}'); + } }