1 //- 2 // Copyright 2017 Jason Lingle 3 // 4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 5 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license 6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your 7 // option. This file may not be copied, modified, or distributed 8 // except according to those terms. 9 10 use crate::std_facade::{fmt, Arc}; 11 use core::mem; 12 13 use crate::strategy::fuse::Fuse; 14 use crate::strategy::traits::*; 15 use crate::test_runner::*; 16 17 /// Adaptor that flattens a `Strategy` which produces other `Strategy`s into a 18 /// `Strategy` that picks one of those strategies and then picks values from 19 /// it. 20 #[derive(Debug, Clone, Copy)] 21 #[must_use = "strategies do nothing unless used"] 22 pub struct Flatten<S> { 23 source: S, 24 } 25 26 impl<S: Strategy> Flatten<S> { 27 /// Wrap `source` to flatten it. new(source: S) -> Self28 pub fn new(source: S) -> Self { 29 Flatten { source } 30 } 31 } 32 33 impl<S: Strategy> Strategy for Flatten<S> 34 where 35 S::Value: Strategy, 36 { 37 type Tree = FlattenValueTree<S::Tree>; 38 type Value = <S::Value as Strategy>::Value; 39 new_tree(&self, runner: &mut TestRunner) -> NewTree<Self>40 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { 41 let meta = self.source.new_tree(runner)?; 42 FlattenValueTree::new(runner, meta) 43 } 44 } 45 46 /// The `ValueTree` produced by `Flatten`. 47 pub struct FlattenValueTree<S: ValueTree> 48 where 49 S::Value: Strategy, 50 { 51 meta: Fuse<S>, 52 current: Fuse<<S::Value as Strategy>::Tree>, 53 // The final value to produce after successive calls to complicate() on the 54 // underlying objects return false. 55 final_complication: Option<Fuse<<S::Value as Strategy>::Tree>>, 56 // When `simplify()` or `complicate()` causes a new `Strategy` to be 57 // chosen, we need to find a new failing input for that case. To do this, 58 // we implement `complicate()` by regenerating values up to a number of 59 // times corresponding to the maximum number of test cases. A `simplify()` 60 // which does not cause a new strategy to be chosen always resets 61 // `complicate_regen_remaining` to 0. 62 // 63 // This does unfortunately depart from the direct interpretation of 64 // simplify/complicate as binary search, but is still easier to think about 65 // than other implementations of higher-order strategies. 66 runner: TestRunner, 67 complicate_regen_remaining: u32, 68 } 69 70 impl<S: ValueTree> Clone for FlattenValueTree<S> 71 where 72 S::Value: Strategy + Clone, 73 S: Clone, 74 <S::Value as Strategy>::Tree: Clone, 75 { 76 fn clone(&self) -> Self { 77 FlattenValueTree { 78 meta: self.meta.clone(), 79 current: self.current.clone(), 80 final_complication: self.final_complication.clone(), 81 runner: self.runner.clone(), 82 complicate_regen_remaining: self.complicate_regen_remaining, 83 } 84 } 85 } 86 87 impl<S: ValueTree> fmt::Debug for FlattenValueTree<S> 88 where 89 S::Value: Strategy, 90 S: fmt::Debug, 91 <S::Value as Strategy>::Tree: fmt::Debug, 92 { 93 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 94 f.debug_struct("FlattenValueTree") 95 .field("meta", &self.meta) 96 .field("current", &self.current) 97 .field("final_complication", &self.final_complication) 98 .field( 99 "complicate_regen_remaining", 100 &self.complicate_regen_remaining, 101 ) 102 .finish() 103 } 104 } 105 106 impl<S: ValueTree> FlattenValueTree<S> 107 where 108 S::Value: Strategy, 109 { 110 fn new(runner: &mut TestRunner, meta: S) -> Result<Self, Reason> { 111 let current = meta.current().new_tree(runner)?; 112 Ok(FlattenValueTree { 113 meta: Fuse::new(meta), 114 current: Fuse::new(current), 115 final_complication: None, 116 runner: runner.partial_clone(), 117 complicate_regen_remaining: 0, 118 }) 119 } 120 } 121 122 impl<S: ValueTree> ValueTree for FlattenValueTree<S> 123 where 124 S::Value: Strategy, 125 { 126 type Value = <S::Value as Strategy>::Value; 127 128 fn current(&self) -> Self::Value { 129 self.current.current() 130 } 131 132 fn simplify(&mut self) -> bool { 133 self.complicate_regen_remaining = 0; 134 135 if self.current.simplify() { 136 // Now that we've simplified the derivative value, we can't 137 // re-complicate the meta value unless it gets simplified again. 138 // We also mustn't complicate back to whatever's in 139 // `final_complication` since the new state of `self.current` is 140 // the most complicated state. 141 self.meta.disallow_complicate(); 142 self.final_complication = None; 143 true 144 } else if !self.meta.simplify() { 145 false 146 } else if let Ok(v) = self.meta.current().new_tree(&mut self.runner) { 147 // Shift current into final_complication and `v` into 148 // `current`. We also need to prevent that value from 149 // complicating beyond the current point in the future 150 // since we're going to return `true` from `simplify()` 151 // ourselves. 152 self.current.disallow_complicate(); 153 self.final_complication = Some(Fuse::new(v)); 154 mem::swap( 155 self.final_complication.as_mut().unwrap(), 156 &mut self.current, 157 ); 158 // Initially complicate by regenerating the chosen value. 159 self.complicate_regen_remaining = self.runner.config().cases; 160 true 161 } else { 162 false 163 } 164 } 165 166 fn complicate(&mut self) -> bool { 167 if self.complicate_regen_remaining > 0 { 168 if self.runner.flat_map_regen() { 169 self.complicate_regen_remaining -= 1; 170 171 if let Ok(v) = self.meta.current().new_tree(&mut self.runner) { 172 self.current = Fuse::new(v); 173 return true; 174 } 175 } else { 176 self.complicate_regen_remaining = 0; 177 } 178 } 179 180 if self.current.complicate() { 181 return true; 182 } else if self.meta.complicate() { 183 if let Ok(v) = self.meta.current().new_tree(&mut self.runner) { 184 self.complicate_regen_remaining = self.runner.config().cases; 185 self.current = Fuse::new(v); 186 return true; 187 } 188 } 189 190 if let Some(v) = self.final_complication.take() { 191 self.current = v; 192 true 193 } else { 194 false 195 } 196 } 197 } 198 199 /// Similar to `Flatten`, but does not shrink the input strategy. 200 /// 201 /// See `Strategy::prop_ind_flat_map()` fore more details. 202 #[derive(Clone, Copy, Debug)] 203 pub struct IndFlatten<S>(pub(super) S); 204 205 impl<S: Strategy> Strategy for IndFlatten<S> 206 where 207 S::Value: Strategy, 208 { 209 type Tree = <S::Value as Strategy>::Tree; 210 type Value = <S::Value as Strategy>::Value; 211 212 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { 213 let inner = self.0.new_tree(runner)?; 214 inner.current().new_tree(runner) 215 } 216 } 217 218 /// Similar to `Map` plus `Flatten`, but does not shrink the input strategy and 219 /// passes the original input through. 220 /// 221 /// See `Strategy::prop_ind_flat_map2()` for more details. 222 pub struct IndFlattenMap<S, F> { 223 pub(super) source: S, 224 pub(super) fun: Arc<F>, 225 } 226 227 impl<S: fmt::Debug, F> fmt::Debug for IndFlattenMap<S, F> { 228 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 229 f.debug_struct("IndFlattenMap") 230 .field("source", &self.source) 231 .field("fun", &"<function>") 232 .finish() 233 } 234 } 235 236 impl<S: Clone, F> Clone for IndFlattenMap<S, F> { 237 fn clone(&self) -> Self { 238 IndFlattenMap { 239 source: self.source.clone(), 240 fun: Arc::clone(&self.fun), 241 } 242 } 243 } 244 245 impl<S: Strategy, R: Strategy, F: Fn(S::Value) -> R> Strategy 246 for IndFlattenMap<S, F> 247 { 248 type Tree = crate::tuple::TupleValueTree<(S::Tree, R::Tree)>; 249 type Value = (S::Value, R::Value); 250 251 fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> { 252 let left = self.source.new_tree(runner)?; 253 let right_source = (self.fun)(left.current()); 254 let right = right_source.new_tree(runner)?; 255 256 Ok(crate::tuple::TupleValueTree::new((left, right))) 257 } 258 } 259 260 #[cfg(test)] 261 mod test { 262 use super::*; 263 264 use std::u32; 265 266 use crate::strategy::just::Just; 267 use crate::test_runner::Config; 268 269 #[test] 270 fn test_flat_map() { 271 // Pick random integer A, then random integer B which is ±5 of A and 272 // assert that B <= A if A > 10000. Shrinking should always converge to 273 // A=10001, B=10002. 274 let input = (0..65536).prop_flat_map(|a| (Just(a), (a - 5..a + 5))); 275 276 let mut failures = 0; 277 let mut runner = TestRunner::new_with_rng( 278 Config { 279 max_shrink_iters: u32::MAX - 1, 280 ..Config::default() 281 }, 282 TestRng::deterministic_rng(RngAlgorithm::default()), 283 ); 284 for _ in 0..1000 { 285 let case = input.new_tree(&mut runner).unwrap(); 286 let result = runner.run_one(case, |(a, b)| { 287 if a <= 10000 || b <= a { 288 Ok(()) 289 } else { 290 Err(TestCaseError::fail("fail")) 291 } 292 }); 293 294 match result { 295 Ok(_) => {} 296 Err(TestError::Fail(_, v)) => { 297 failures += 1; 298 assert_eq!((10001, 10002), v); 299 } 300 result => panic!("Unexpected result: {:?}", result), 301 } 302 } 303 304 assert!(failures > 250); 305 } 306 307 #[test] 308 fn test_flat_map_sanity() { 309 check_strategy_sanity( 310 (0..65536).prop_flat_map(|a| (Just(a), (a - 5..a + 5))), 311 None, 312 ); 313 } 314 315 #[test] 316 fn flat_map_respects_regen_limit() { 317 use std::sync::atomic::{AtomicBool, Ordering}; 318 319 let input = (0..65536) 320 .prop_flat_map(|_| 0..65536) 321 .prop_flat_map(|_| 0..65536) 322 .prop_flat_map(|_| 0..65536) 323 .prop_flat_map(|_| 0..65536) 324 .prop_flat_map(|_| 0..65536); 325 326 // Arteficially make the first case fail and all others pass, so that 327 // the regeneration logic futilely searches for another failing 328 // example and eventually gives up. Unfortunately, the test is sort of 329 // semi-decidable; if the limit *doesn't* work, the test just runs 330 // almost forever. 331 let pass = AtomicBool::new(false); 332 let mut runner = TestRunner::new(Config { 333 max_flat_map_regens: 1000, 334 ..Config::default() 335 }); 336 let case = input.new_tree(&mut runner).unwrap(); 337 let _ = runner.run_one(case, |_| { 338 // Only the first run fails, all others succeed 339 prop_assert!(pass.fetch_or(true, Ordering::SeqCst)); 340 Ok(()) 341 }); 342 } 343 344 #[test] 345 fn test_ind_flat_map_sanity() { 346 check_strategy_sanity( 347 (0..65536).prop_ind_flat_map(|a| (Just(a), (a - 5..a + 5))), 348 None, 349 ); 350 } 351 352 #[test] 353 fn test_ind_flat_map2_sanity() { 354 check_strategy_sanity( 355 (0..65536).prop_ind_flat_map2(|a| a - 5..a + 5), 356 None, 357 ); 358 } 359 } 360