Repository: camshaft/bolero (c)

Issue:
Uniform never generates upper value
This also affects `one_of`, which never generates the last variant.

I think the bug is in this line: 

https://github.com/camshaft/bolero/blob/ed2f9f5d49b277e14737aeef6c07af00118c43c3/lib/bolero-generator/src/uniform.rs#L96

```
let value = value % range;
```

should be replaced with
```
let value = value % range.saturating_add(1);
```


Pull request description:
fix: use exclusive modulus for uniform samples
Fixes #199 

Patch:
diff --git a/lib/bolero-generator/Cargo.toml b/lib/bolero-generator/Cargo.toml
index 8c835f1..e4f8da5 100644
--- a/lib/bolero-generator/Cargo.toml
+++ b/lib/bolero-generator/Cargo.toml
@@ -7,7 +7,7 @@ homepage = "https://github.com/camshaft/bolero"
 repository = "https://github.com/camshaft/bolero"
 keywords = ["testing", "quickcheck", "property", "fuzz", "fuzzing"]
 license = "MIT"
-edition = "2018"
+edition = "2021"
 readme = "README.md"
 rust-version = "1.57.0"
 
diff --git a/lib/bolero-generator/src/uniform.rs b/lib/bolero-generator/src/uniform.rs
index f726134..caf97bb 100644
--- a/lib/bolero-generator/src/uniform.rs
+++ b/lib/bolero-generator/src/uniform.rs
@@ -24,6 +24,23 @@ macro_rules! uniform_int {
             #[inline]
             fn sample<F: FillBytes>(fill: &mut F, min: Bound<&$ty>, max: Bound<&$ty>) -> Option<$ty> {
                 match (min, max) {
+                    // filter invalid ranges
+                    (Bound::Unbounded, Bound::Excluded(&$ty::MIN)) | (Bound::Excluded(&$ty::MAX), Bound::Unbounded)  => {
+                        return None;
+                    }
+                    (Bound::Included(&x), Bound::Included(&y)) if x > y  => {
+                        return None;
+                    }
+                    (Bound::Included(&x), Bound::Excluded(&y)) if x >= y  => {
+                        return None;
+                    }
+                    (Bound::Excluded(&x), Bound::Included(&y)) if x >= y  => {
+                        return None;
+                    }
+                    (Bound::Excluded(&x), Bound::Excluded(&y)) if x.saturating_add(1) >= y  => {
+                        return None;
+                    }
+                    // full ranges
                     (Bound::Unbounded, Bound::Unbounded)
                     | (Bound::Unbounded, Bound::Included(&$ty::MAX))
                     | (Bound::Included(&$ty::MIN), Bound::Unbounded)
@@ -32,12 +49,6 @@ macro_rules! uniform_int {
                         fill.fill_bytes(&mut bytes)?;
                         return Some(<$ty>::from_le_bytes(bytes));
                     }
-                    (Bound::Included(&x), Bound::Included(&y)) if x == y => {
-                        return Some(x);
-                    }
-                    (Bound::Included(&x), Bound::Excluded(&y)) if x + 1 == y  => {
-                        return Some(x);
-                    }
                     _ => {}
                 }
 
@@ -59,25 +70,16 @@ macro_rules! uniform_int {
                     Bound::Unbounded => $ty::MAX,
                 };
 
-                // swap the two if reversed
-                let (lower, upper) = if upper > lower {
-                    (lower, upper)
-                } else {
-                    (upper, lower)
-                };
-
-                let range = upper.wrapping_sub(lower) as $unsigned;
+                let range_inclusive = upper.wrapping_sub(lower) as $unsigned;
 
-                if range == 0 {
+                if range_inclusive == 0 {
                     return Some(lower);
                 }
 
                 $({
-                    use core::convert::TryInto;
-
                     // if the range fits in a smaller data type use that instead
-                    if let Ok(range) = range.try_into() {
-                        let value: $smaller = Uniform::sample(fill, Bound::Unbounded, Bound::Included(&range))?;
+                    if let Ok(range_inclusive) = range_inclusive.try_into() {
+                        let value: $smaller = Uniform::sample(fill, Bound::Unbounded, Bound::Included(&range_inclusive))?;
                         let value = value as $ty;
                         let value = lower.wrapping_add(value);
 
@@ -92,8 +94,12 @@ macro_rules! uniform_int {
 
                 let value: $unsigned = Uniform::sample(fill, Bound::Unbounded, Bound::Unbounded)?;
 
+                if cfg!(test) {
+                    assert!(range_inclusive < $unsigned::MAX, "range inclusive should always be less than the max value");
+                }
+                let range_exclusive = range_inclusive.wrapping_add(1);
                 // TODO make this less biased
-                let value = value % range;
+                let value = value % range_exclusive;
                 let value = value as $ty;
                 let value = lower.wrapping_add(value);
 
@@ -132,6 +138,7 @@ impl Uniform for char {
         const START: u32 = 0xD800;
         const LEN: u32 = 0xE000 - START;
 
+        #[inline]
         fn map_to_u32(c: &char) -> u32 {
             match *c as u32 {
                 c if c >= START => c - LEN,
@@ -152,6 +159,228 @@ impl Uniform for char {
             value += LEN;
         }
 
+        if cfg!(test) {
+            assert!(
+                char::from_u32(value).is_some(),
+                "invalid value generated: {}",
+                value
+            );
+        }
+
         char::from_u32(value)
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[derive(Clone, Copy, Debug)]
+    struct Byte {
+        value: Option<u8>,
+        driver_mode: DriverMode,
+    }
+
+    impl FillBytes for Byte {
+        fn mode(&self) -> DriverMode {
+            self.driver_mode
+        }
+
+        fn peek_bytes(&mut self, offset: usize, bytes: &mut [u8]) -> Option<()> {
+            if offset > 0 {
+                return None;
+            }
+
+            match (bytes.len(), self.value) {
+                (0, Some(_)) => Some(()),
+                (1, Some(value)) => {
+                    bytes[0] = value;
+                    Some(())
+                }
+                _ => None,
+            }
+        }
+
+        fn consume_bytes(&mut self, consumed: usize) {
+            match consumed {
+                0 => {}
+                1 => self.value = None,
+                _ => panic!(),
+            }
+        }
+    }
+
+    #[derive(Clone, Copy, Debug, PartialEq)]
+    struct Seen<T: SeenValue>([bool; 256], core::marker::PhantomData<T>);
+
+    impl<T: SeenValue> Default for Seen<T> {
+        fn default() -> Self {
+            Self([false; 256], Default::default())
+        }
+    }
+
+    impl<T: SeenValue> Seen<T> {
+        fn insert(&mut self, v: T) {
+            self.0[v.index()] = true;
+        }
+    }
+
+    trait SeenValue: Copy + Uniform + core::fmt::Debug {
+        fn index(self) -> usize;
+        fn fill_expected(min: Bound<Self>, max: Bound<Self>, seen: &mut Seen<Self>);
+    }
+
+    impl SeenValue for u8 {
+        fn index(self) -> usize {
+            self as _
+        }
+
+        fn fill_expected(min: Bound<Self>, max: Bound<Self>, seen: &mut Seen<Self>) {
+            for value in Self::MIN..=Self::MAX {
+                if (min, max).contains(&value) {
+                    seen.insert(value);
+                }
+            }
+        }
+    }
+
+    impl SeenValue for i8 {
+        fn index(self) -> usize {
+            (self as isize + -(i8::MIN as isize)).try_into().unwrap()
+        }
+
+        fn fill_expected(min: Bound<Self>, max: Bound<Self>, seen: &mut Seen<Self>) {
+            for value in Self::MIN..=Self::MAX {
+                if (min, max).contains(&value) {
+                    seen.insert(value);
+                }
+            }
+        }
+    }
+
+    fn range_test<T: SeenValue>(
+        driver_mode: DriverMode,
+        map: impl Fn(u8, u8) -> (Bound<T>, Bound<T>),
+    ) {
+        for min in 0..=255 {
+            for max in 0..=255 {
+                let (min_b, max_b) = map(min, max);
+                let mut expected = Seen::default();
+                T::fill_expected(min_b, max_b, &mut expected);
+
+                let min_b = BoundExt::as_ref(&min_b);
+                let max_b = BoundExt::as_ref(&max_b);
+
+                let mut actual = Seen::default();
+                for seed in 0..=255 {
+                    let mut driver = Byte {
+                        value: Some(seed),
+                        driver_mode,
+                    };
+                    let result = T::sample(&mut driver, min_b, max_b);
+                    if let Some(value) = result {
+                        assert!(
+                            (min_b, max_b).contains(&value),
+                            "generated value ({:?}) outside of bounds ({:?}, {:?}) in {:?}",
+                            value,
+                            min_b,
+                            max_b,
+                            driver_mode,
+                        );
+                        actual.insert(value);
+                    }
+                }
+
+                assert_eq!(&expected, &actual, "min: {:?}, max: {:?}", min_b, max_b);
+            }
+        }
+    }
+
+    macro_rules! range_tests {
+        ($name:ident, $ty:ident, $map:expr) => {
+            mod $name {
+                use super::*;
+
+                range_tests!(Direct, direct, $ty, $map);
+                range_tests!(Forced, forced, $ty, $map);
+            }
+        };
+        ($mode:ident, $name:ident, $ty:ident, $map:expr) => {
+            mod $name {
+                use super::*;
+
+                // Inclusive
+                #[test]
+                fn inclusive_inclusive() {
+                    range_test(DriverMode::$mode, |min, max| {
+                        (Bound::Included(($map)(min)), Bound::Included(($map)(max)))
+                    });
+                }
+
+                #[test]
+                fn inclusive_exclusive() {
+                    range_test(DriverMode::$mode, |min, max| {
+                        (Bound::Included(($map)(min)), Bound::Excluded(($map)(max)))
+                    });
+                }
+
+                #[test]
+                fn inclusive_unbounded() {
+                    range_test(DriverMode::$mode, |min, _max| {
+                        (Bound::Included(($map)(min)), Bound::Unbounded)
+                    });
+                }
+
+                // Exclusive
+                #[test]
+                fn exclusive_inclusive() {
+                    range_test(DriverMode::$mode, |min, max| {
+                        (Bound::Excluded(($map)(min)), Bound::Included(($map)(max)))
+                    });
+                }
+
+                #[test]
+                fn exclusive_exclusive() {
+                    range_test(DriverMode::$mode, |min, max| {
+                        (Bound::Excluded(($map)(min)), Bound::Excluded(($map)(max)))
+                    });
+                }
+
+                #[test]
+                fn exclusive_unbounded() {
+                    range_test(DriverMode::$mode, |min, _max| {
+                        (Bound::Excluded(($map)(min)), Bound::Unbounded)
+                    });
+                }
+
+                // Unbounded
+                #[test]
+                fn unbounded_inclusive() {
+                    range_test(DriverMode::$mode, |_min, max| {
+                        (Bound::Unbounded, Bound::Included(($map)(max)))
+                    });
+                }
+
+                #[test]
+                fn unbounded_exclusive() {
+                    range_test(DriverMode::$mode, |_min, max| {
+                        (Bound::Unbounded, Bound::Excluded(($map)(max)))
+                    });
+                }
+
+                #[test]
+                fn unbounded_unbounded() {
+                    range_test(DriverMode::$mode, |_min, _max| {
+                        (<Bound<$ty>>::Unbounded, Bound::Unbounded)
+                    });
+                }
+            }
+        };
+    }
+
+    range_tests!(unsigned, u8, |value| value);
+    range_tests!(signed, i8, |value| -> i8 {
+        // shift the u8 into the i8 range
+        (value as i16 - -(i8::MIN as i16)).try_into().unwrap()
+    });
+}
diff --git a/lib/bolero-kani/src/lib.rs b/lib/bolero-kani/src/lib.rs
index 3c3abe1..aa918cf 100644
--- a/lib/bolero-kani/src/lib.rs
+++ b/lib/bolero-kani/src/lib.rs
@@ -58,6 +58,7 @@ pub mod lib {
                         was_valid,
                         "the generator should produce at least one valid value"
                     );
+                    let _ = was_valid;
                 }
                 Err(_) => {
                     panic!("test failed");


Test patch:
diff --git a/examples/basic/tests/fuzz_operations/fuzz_target.rs b/examples/basic/tests/fuzz_operations/fuzz_target.rs
index c27050d..dbe061d 100644
--- a/examples/basic/tests/fuzz_operations/fuzz_target.rs
+++ b/examples/basic/tests/fuzz_operations/fuzz_target.rs
@@ -11,12 +11,12 @@ enum Operation {
 }
 
 fn main() {
-    let len = if should_panic() { 50 } else { 32 };
+    let len = if should_panic() { 16 } else { 4 };
 
     check!()
         .with_generator(gen::<Vec<Operation>>().with().len(0usize..=len))
         .for_each(|operations| {
-            let mut subject: ArrayVec<[_; 32]> = ArrayVec::new();
+            let mut subject: ArrayVec<[_; 4]> = ArrayVec::new();
             let mut oracle = LinkedList::new();
 
             for operation in operations.iter() {