[rustc.git] / vendor / rustc-rayon-core / src / scope / test.rs

use crate::unwind;
use crate::ThreadPoolBuilder;
use crate::{scope, scope_fifo, Scope};
use rand::{Rng, SeedableRng};
use rand_xorshift::XorShiftRng;
use std::cmp;
use std::iter::once;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Mutex;
use std::vec;

#[test]
fn scope_empty() {
    scope(|_| {});
}

#[test]
fn scope_result() {
    let x = scope(|_| 22);
    assert_eq!(x, 22);
}

#[test]
fn scope_two() {
    let counter = &AtomicUsize::new(0);
    scope(|s| {
        s.spawn(move |_| {
            counter.fetch_add(1, Ordering::SeqCst);
        });
        s.spawn(move |_| {
            counter.fetch_add(10, Ordering::SeqCst);
        });
    });

    let v = counter.load(Ordering::SeqCst);
    assert_eq!(v, 11);
}

#[test]
fn scope_divide_and_conquer() {
    let counter_p = &AtomicUsize::new(0);
    scope(|s| s.spawn(move |s| divide_and_conquer(s, counter_p, 1024)));

    let counter_s = &AtomicUsize::new(0);
    divide_and_conquer_seq(&counter_s, 1024);

    let p = counter_p.load(Ordering::SeqCst);
    let s = counter_s.load(Ordering::SeqCst);
    assert_eq!(p, s);
}

fn divide_and_conquer<'scope>(scope: &Scope<'scope>, counter: &'scope AtomicUsize, size: usize) {
    if size > 1 {
        scope.spawn(move |scope| divide_and_conquer(scope, counter, size / 2));
        scope.spawn(move |scope| divide_and_conquer(scope, counter, size / 2));
    } else {
        // count the leaves
        counter.fetch_add(1, Ordering::SeqCst);
    }
}

fn divide_and_conquer_seq(counter: &AtomicUsize, size: usize) {
    if size > 1 {
        divide_and_conquer_seq(counter, size / 2);
        divide_and_conquer_seq(counter, size / 2);
    } else {
        // count the leaves
        counter.fetch_add(1, Ordering::SeqCst);
    }
}

struct Tree<T: Send> {
    value: T,
    children: Vec<Tree<T>>,
}

impl<T: Send> Tree<T> {
    fn iter<'s>(&'s self) -> vec::IntoIter<&'s T> {
        once(&self.value)
            .chain(self.children.iter().flat_map(Tree::iter))
            .collect::<Vec<_>>() // seems like it shouldn't be needed... but prevents overflow
            .into_iter()
    }

    fn update<OP>(&mut self, op: OP)
    where
        OP: Fn(&mut T) + Sync,
        T: Send,
    {
        scope(|s| self.update_in_scope(&op, s));
    }

    fn update_in_scope<'scope, OP>(&'scope mut self, op: &'scope OP, scope: &Scope<'scope>)
    where
        OP: Fn(&mut T) + Sync,
    {
        let Tree {
            ref mut value,
            ref mut children,
        } = *self;
        scope.spawn(move |scope| {
            for child in children {
                scope.spawn(move |scope| child.update_in_scope(op, scope));
            }
        });

        op(value);
    }
}

fn random_tree(depth: usize) -> Tree<u32> {
    assert!(depth > 0);
    let mut seed = <XorShiftRng as SeedableRng>::Seed::default();
    (0..).zip(seed.as_mut()).for_each(|(i, x)| *x = i);
    let mut rng = XorShiftRng::from_seed(seed);
    random_tree1(depth, &mut rng)
}

fn random_tree1(depth: usize, rng: &mut XorShiftRng) -> Tree<u32> {
    let children = if depth == 0 {
        vec![]
    } else {
        (0..rng.gen_range(0, 4)) // somewhere between 0 and 3 children at each level
            .map(|_| random_tree1(depth - 1, rng))
            .collect()
    };

    Tree {
        value: rng.gen_range(0, 1_000_000),
        children,
    }
}

#[test]
fn update_tree() {
    let mut tree: Tree<u32> = random_tree(10);
    let values: Vec<u32> = tree.iter().cloned().collect();
    tree.update(|v| *v += 1);
    let new_values: Vec<u32> = tree.iter().cloned().collect();
    assert_eq!(values.len(), new_values.len());
    for (&i, &j) in values.iter().zip(&new_values) {
        assert_eq!(i + 1, j);
    }
}

/// Check that if you have a chain of scoped tasks where T0 spawns T1
/// spawns T2 and so forth down to Tn, the stack space should not grow
/// linearly with N. We test this by some unsafe hackery and
/// permitting an approx 10% change with a 10x input change.
#[test]
fn linear_stack_growth() {
    let builder = ThreadPoolBuilder::new().num_threads(1);
    let pool = builder.build().unwrap();
    pool.install(|| {
        let mut max_diff = Mutex::new(0);
        let bottom_of_stack = 0;
        scope(|s| the_final_countdown(s, &bottom_of_stack, &max_diff, 5));
        let diff_when_5 = *max_diff.get_mut().unwrap() as f64;

        scope(|s| the_final_countdown(s, &bottom_of_stack, &max_diff, 500));
        let diff_when_500 = *max_diff.get_mut().unwrap() as f64;

        let ratio = diff_when_5 / diff_when_500;
        assert!(
            ratio > 0.9 && ratio < 1.1,
            "stack usage ratio out of bounds: {}",
            ratio
        );
    });
}

fn the_final_countdown<'scope>(
    s: &Scope<'scope>,
    bottom_of_stack: &'scope i32,
    max: &'scope Mutex<usize>,
    n: usize,
) {
    let top_of_stack = 0;
    let p = bottom_of_stack as *const i32 as usize;
    let q = &top_of_stack as *const i32 as usize;
    let diff = if p > q { p - q } else { q - p };

    let mut data = max.lock().unwrap();
    *data = cmp::max(diff, *data);

    if n > 0 {
        s.spawn(move |s| the_final_countdown(s, bottom_of_stack, max, n - 1));
    }
}

#[test]
#[should_panic(expected = "Hello, world!")]
fn panic_propagate_scope() {
    scope(|_| panic!("Hello, world!"));
}

#[test]
#[should_panic(expected = "Hello, world!")]
fn panic_propagate_spawn() {
    scope(|s| s.spawn(|_| panic!("Hello, world!")));
}

#[test]
#[should_panic(expected = "Hello, world!")]
fn panic_propagate_nested_spawn() {
    scope(|s| s.spawn(|s| s.spawn(|s| s.spawn(|_| panic!("Hello, world!")))));
}

#[test]
#[should_panic(expected = "Hello, world!")]
fn panic_propagate_nested_scope_spawn() {
    scope(|s| s.spawn(|_| scope(|s| s.spawn(|_| panic!("Hello, world!")))));
}

#[test]
fn panic_propagate_still_execute_1() {
    let mut x = false;
    match unwind::halt_unwinding(|| {
        scope(|s| {
            s.spawn(|_| panic!("Hello, world!")); // job A
            s.spawn(|_| x = true); // job B, should still execute even though A panics
        });
    }) {
        Ok(_) => panic!("failed to propagate panic"),
        Err(_) => assert!(x, "job b failed to execute"),
    }
}

#[test]
fn panic_propagate_still_execute_2() {
    let mut x = false;
    match unwind::halt_unwinding(|| {
        scope(|s| {
            s.spawn(|_| x = true); // job B, should still execute even though A panics
            s.spawn(|_| panic!("Hello, world!")); // job A
        });
    }) {
        Ok(_) => panic!("failed to propagate panic"),
        Err(_) => assert!(x, "job b failed to execute"),
    }
}

#[test]
fn panic_propagate_still_execute_3() {
    let mut x = false;
    match unwind::halt_unwinding(|| {
        scope(|s| {
            s.spawn(|_| x = true); // spanwed job should still execute despite later panic
            panic!("Hello, world!");
        });
    }) {
        Ok(_) => panic!("failed to propagate panic"),
        Err(_) => assert!(x, "panic after spawn, spawn failed to execute"),
    }
}

#[test]
fn panic_propagate_still_execute_4() {
    let mut x = false;
    match unwind::halt_unwinding(|| {
        scope(|s| {
            s.spawn(|_| panic!("Hello, world!"));
            x = true;
        });
    }) {
        Ok(_) => panic!("failed to propagate panic"),
        Err(_) => assert!(x, "panic in spawn tainted scope"),
    }
}

macro_rules! test_order {
    ($scope:ident => $spawn:ident) => {{
        let builder = ThreadPoolBuilder::new().num_threads(1);
        let pool = builder.build().unwrap();
        pool.install(|| {
            let vec = Mutex::new(vec![]);
            $scope(|scope| {
                let vec = &vec;
                for i in 0..10 {
                    scope.$spawn(move |scope| {
                        for j in 0..10 {
                            scope.$spawn(move |_| {
                                vec.lock().unwrap().push(i * 10 + j);
                            });
                        }
                    });
                }
            });
            vec.into_inner().unwrap()
        })
    }};
}

#[test]
fn lifo_order() {
    // In the absense of stealing, `scope()` runs its `spawn()` jobs in LIFO order.
    let vec = test_order!(scope => spawn);
    let expected: Vec<i32> = (0..100).rev().collect(); // LIFO -> reversed
    assert_eq!(vec, expected);
}

#[test]
fn fifo_order() {
    // In the absense of stealing, `scope_fifo()` runs its `spawn_fifo()` jobs in FIFO order.
    let vec = test_order!(scope_fifo => spawn_fifo);
    let expected: Vec<i32> = (0..100).collect(); // FIFO -> natural order
    assert_eq!(vec, expected);
}

macro_rules! test_nested_order {
    ($outer_scope:ident => $outer_spawn:ident,
     $inner_scope:ident => $inner_spawn:ident) => {{
        let builder = ThreadPoolBuilder::new().num_threads(1);
        let pool = builder.build().unwrap();
        pool.install(|| {
            let vec = Mutex::new(vec![]);
            $outer_scope(|scope| {
                let vec = &vec;
                for i in 0..10 {
                    scope.$outer_spawn(move |_| {
                        $inner_scope(|scope| {
                            for j in 0..10 {
                                scope.$inner_spawn(move |_| {
                                    vec.lock().unwrap().push(i * 10 + j);
                                });
                            }
                        });
                    });
                }
            });
            vec.into_inner().unwrap()
        })
    }};
}

#[test]
fn nested_lifo_order() {
    // In the absense of stealing, `scope()` runs its `spawn()` jobs in LIFO order.
    let vec = test_nested_order!(scope => spawn, scope => spawn);
    let expected: Vec<i32> = (0..100).rev().collect(); // LIFO -> reversed
    assert_eq!(vec, expected);
}

#[test]
fn nested_fifo_order() {
    // In the absense of stealing, `scope_fifo()` runs its `spawn_fifo()` jobs in FIFO order.
    let vec = test_nested_order!(scope_fifo => spawn_fifo, scope_fifo => spawn_fifo);
    let expected: Vec<i32> = (0..100).collect(); // FIFO -> natural order
    assert_eq!(vec, expected);
}

#[test]
fn nested_lifo_fifo_order() {
    // LIFO on the outside, FIFO on the inside
    let vec = test_nested_order!(scope => spawn, scope_fifo => spawn_fifo);
    let expected: Vec<i32> = (0..10)
        .rev()
        .flat_map(|i| (0..10).map(move |j| i * 10 + j))
        .collect();
    assert_eq!(vec, expected);
}

#[test]
fn nested_fifo_lifo_order() {
    // FIFO on the outside, LIFO on the inside
    let vec = test_nested_order!(scope_fifo => spawn_fifo, scope => spawn);
    let expected: Vec<i32> = (0..10)
        .flat_map(|i| (0..10).rev().map(move |j| i * 10 + j))
        .collect();
    assert_eq!(vec, expected);
}

macro_rules! spawn_push {
    ($scope:ident . $spawn:ident, $vec:ident, $i:expr) => {{
        $scope.$spawn(move |_| $vec.lock().unwrap().push($i));
    }};
}

/// Test spawns pushing a series of numbers, interleaved
/// such that negative values are using an inner scope.
macro_rules! test_mixed_order {
    ($outer_scope:ident => $outer_spawn:ident,
     $inner_scope:ident => $inner_spawn:ident) => {{
        let builder = ThreadPoolBuilder::new().num_threads(1);
        let pool = builder.build().unwrap();
        pool.install(|| {
            let vec = Mutex::new(vec![]);
            $outer_scope(|outer_scope| {
                let vec = &vec;
                spawn_push!(outer_scope.$outer_spawn, vec, 0);
                $inner_scope(|inner_scope| {
                    spawn_push!(inner_scope.$inner_spawn, vec, -1);
                    spawn_push!(outer_scope.$outer_spawn, vec, 1);
                    spawn_push!(inner_scope.$inner_spawn, vec, -2);
                    spawn_push!(outer_scope.$outer_spawn, vec, 2);
                    spawn_push!(inner_scope.$inner_spawn, vec, -3);
                });
                spawn_push!(outer_scope.$outer_spawn, vec, 3);
            });
            vec.into_inner().unwrap()
        })
    }};
}

#[test]
fn mixed_lifo_order() {
    // NB: the end of the inner scope makes us execute some of the outer scope
    // before they've all been spawned, so they're not perfectly LIFO.
    let vec = test_mixed_order!(scope => spawn, scope => spawn);
    let expected = vec![-3, 2, -2, 1, -1, 3, 0];
    assert_eq!(vec, expected);
}

#[test]
fn mixed_fifo_order() {
    let vec = test_mixed_order!(scope_fifo => spawn_fifo, scope_fifo => spawn_fifo);
    let expected = vec![-1, 0, -2, 1, -3, 2, 3];
    assert_eq!(vec, expected);
}

#[test]
fn mixed_lifo_fifo_order() {
    // NB: the end of the inner scope makes us execute some of the outer scope
    // before they've all been spawned, so they're not perfectly LIFO.
    let vec = test_mixed_order!(scope => spawn, scope_fifo => spawn_fifo);
    let expected = vec![-1, 2, -2, 1, -3, 3, 0];
    assert_eq!(vec, expected);
}

#[test]
fn mixed_fifo_lifo_order() {
    let vec = test_mixed_order!(scope_fifo => spawn_fifo, scope => spawn);
    let expected = vec![-3, 0, -2, 1, -1, 2, 3];
    assert_eq!(vec, expected);
}
Commit	Line	Data
6a06907d XL	1	use crate::unwind;
	2	use crate::ThreadPoolBuilder;
	3	use crate::{scope, scope_fifo, Scope};
e74abb32 XL	4	use rand::{Rng, SeedableRng};
e74abb32 XL	5	use rand_xorshift::XorShiftRng;
2c00a5a8 XL	6	use std::cmp;
	7	use std::iter::once;
	8	use std::sync::atomic::{AtomicUsize, Ordering};
	9	use std::sync::Mutex;
532ac7d7	10	use std::vec;
2c00a5a8 XL	11
	12	#[test]
	13	fn scope_empty() {
532ac7d7	14	scope(\|_\| {});
2c00a5a8 XL	15	}
	16
	17	#[test]
	18	fn scope_result() {
	19	let x = scope(\|_\| 22);
	20	assert_eq!(x, 22);
	21	}
	22
	23	#[test]
	24	fn scope_two() {
	25	let counter = &AtomicUsize::new(0);
	26	scope(\|s\| {
	27	s.spawn(move \|_\| {
	28	counter.fetch_add(1, Ordering::SeqCst);
	29	});
	30	s.spawn(move \|_\| {
	31	counter.fetch_add(10, Ordering::SeqCst);
	32	});
	33	});
	34
	35	let v = counter.load(Ordering::SeqCst);
	36	assert_eq!(v, 11);
	37	}
	38
	39	#[test]
	40	fn scope_divide_and_conquer() {
	41	let counter_p = &AtomicUsize::new(0);
	42	scope(\|s\| s.spawn(move \|s\| divide_and_conquer(s, counter_p, 1024)));
	43
	44	let counter_s = &AtomicUsize::new(0);
	45	divide_and_conquer_seq(&counter_s, 1024);
	46
	47	let p = counter_p.load(Ordering::SeqCst);
	48	let s = counter_s.load(Ordering::SeqCst);
	49	assert_eq!(p, s);
	50	}
	51
	52	fn divide_and_conquer<'scope>(scope: &Scope<'scope>, counter: &'scope AtomicUsize, size: usize) {
	53	if size > 1 {
	54	scope.spawn(move \|scope\| divide_and_conquer(scope, counter, size / 2));
	55	scope.spawn(move \|scope\| divide_and_conquer(scope, counter, size / 2));
	56	} else {
	57	// count the leaves
	58	counter.fetch_add(1, Ordering::SeqCst);
	59	}
	60	}
	61
	62	fn divide_and_conquer_seq(counter: &AtomicUsize, size: usize) {
	63	if size > 1 {
	64	divide_and_conquer_seq(counter, size / 2);
	65	divide_and_conquer_seq(counter, size / 2);
	66	} else {
	67	// count the leaves
	68	counter.fetch_add(1, Ordering::SeqCst);
	69	}
	70	}
	71
	72	struct Tree<T: Send> {
	73	value: T,
	74	children: Vec<Tree<T>>,
	75	}
	76
	77	impl<T: Send> Tree<T> {
e74abb32	78	fn iter<'s>(&'s self) -> vec::IntoIter<&'s T> {
2c00a5a8	79	once(&self.value)
e74abb32	80	.chain(self.children.iter().flat_map(Tree::iter))
2c00a5a8 XL	81	.collect::<Vec<_>>() // seems like it shouldn't be needed... but prevents overflow
	82	.into_iter()
	83	}
	84
e74abb32	85	fn update<OP>(&mut self, op: OP)
532ac7d7 XL	86	where
	87	OP: Fn(&mut T) + Sync,
	88	T: Send,
2c00a5a8 XL	89	{
	90	scope(\|s\| self.update_in_scope(&op, s));
	91	}
	92
	93	fn update_in_scope<'scope, OP>(&'scope mut self, op: &'scope OP, scope: &Scope<'scope>)
532ac7d7 XL	94	where
532ac7d7 XL	95	OP: Fn(&mut T) + Sync,
2c00a5a8	96	{
532ac7d7 XL	97	let Tree {
	98	ref mut value,
	99	ref mut children,
	100	} = *self;
2c00a5a8 XL	101	scope.spawn(move \|scope\| {
	102	for child in children {
	103	scope.spawn(move \|scope\| child.update_in_scope(op, scope));
	104	}
	105	});
	106
	107	op(value);
	108	}
	109	}
	110
	111	fn random_tree(depth: usize) -> Tree<u32> {
	112	assert!(depth > 0);
532ac7d7 XL	113	let mut seed = <XorShiftRng as SeedableRng>::Seed::default();
	114	(0..).zip(seed.as_mut()).for_each(\|(i, x)\| *x = i);
	115	let mut rng = XorShiftRng::from_seed(seed);
2c00a5a8 XL	116	random_tree1(depth, &mut rng)
	117	}
	118
	119	fn random_tree1(depth: usize, rng: &mut XorShiftRng) -> Tree<u32> {
	120	let children = if depth == 0 {
	121	vec![]
	122	} else {
532ac7d7	123	(0..rng.gen_range(0, 4)) // somewhere between 0 and 3 children at each level
2c00a5a8 XL	124	.map(\|_\| random_tree1(depth - 1, rng))
	125	.collect()
	126	};
	127
	128	Tree {
532ac7d7	129	value: rng.gen_range(0, 1_000_000),
e74abb32	130	children,
2c00a5a8 XL	131	}
	132	}
	133
	134	#[test]
	135	fn update_tree() {
	136	let mut tree: Tree<u32> = random_tree(10);
	137	let values: Vec<u32> = tree.iter().cloned().collect();
	138	tree.update(\|v\| *v += 1);
	139	let new_values: Vec<u32> = tree.iter().cloned().collect();
	140	assert_eq!(values.len(), new_values.len());
	141	for (&i, &j) in values.iter().zip(&new_values) {
	142	assert_eq!(i + 1, j);
	143	}
	144	}
	145
	146	/// Check that if you have a chain of scoped tasks where T0 spawns T1
	147	/// spawns T2 and so forth down to Tn, the stack space should not grow
	148	/// linearly with N. We test this by some unsafe hackery and
	149	/// permitting an approx 10% change with a 10x input change.
	150	#[test]
	151	fn linear_stack_growth() {
	152	let builder = ThreadPoolBuilder::new().num_threads(1);
	153	let pool = builder.build().unwrap();
	154	pool.install(\|\| {
	155	let mut max_diff = Mutex::new(0);
	156	let bottom_of_stack = 0;
	157	scope(\|s\| the_final_countdown(s, &bottom_of_stack, &max_diff, 5));
	158	let diff_when_5 = *max_diff.get_mut().unwrap() as f64;
	159
	160	scope(\|s\| the_final_countdown(s, &bottom_of_stack, &max_diff, 500));
	161	let diff_when_500 = *max_diff.get_mut().unwrap() as f64;
	162
	163	let ratio = diff_when_5 / diff_when_500;
532ac7d7 XL	164	assert!(
	165	ratio > 0.9 && ratio < 1.1,
	166	"stack usage ratio out of bounds: {}",
	167	ratio
	168	);
2c00a5a8 XL	169	});
	170	}
	171
532ac7d7 XL	172	fn the_final_countdown<'scope>(
	173	s: &Scope<'scope>,
	174	bottom_of_stack: &'scope i32,
	175	max: &'scope Mutex<usize>,
	176	n: usize,
	177	) {
2c00a5a8 XL	178	let top_of_stack = 0;
	179	let p = bottom_of_stack as *const i32 as usize;
	180	let q = &top_of_stack as *const i32 as usize;
	181	let diff = if p > q { p - q } else { q - p };
	182
	183	let mut data = max.lock().unwrap();
	184	data = cmp::max(diff, data);
	185
	186	if n > 0 {
	187	s.spawn(move \|s\| the_final_countdown(s, bottom_of_stack, max, n - 1));
	188	}
	189	}
	190
	191	#[test]
	192	#[should_panic(expected = "Hello, world!")]
	193	fn panic_propagate_scope() {
	194	scope(\|_\| panic!("Hello, world!"));
	195	}
	196
	197	#[test]
	198	#[should_panic(expected = "Hello, world!")]
	199	fn panic_propagate_spawn() {
	200	scope(\|s\| s.spawn(\|_\| panic!("Hello, world!")));
	201	}
	202
	203	#[test]
	204	#[should_panic(expected = "Hello, world!")]
	205	fn panic_propagate_nested_spawn() {
	206	scope(\|s\| s.spawn(\|s\| s.spawn(\|s\| s.spawn(\|_\| panic!("Hello, world!")))));
	207	}
	208
	209	#[test]
	210	#[should_panic(expected = "Hello, world!")]
	211	fn panic_propagate_nested_scope_spawn() {
	212	scope(\|s\| s.spawn(\|_\| scope(\|s\| s.spawn(\|_\| panic!("Hello, world!")))));
	213	}
	214
	215	#[test]
	216	fn panic_propagate_still_execute_1() {
	217	let mut x = false;
	218	match unwind::halt_unwinding(\|\| {
	219	scope(\|s\| {
	220	s.spawn(\|_\| panic!("Hello, world!")); // job A
	221	s.spawn(\|_\| x = true); // job B, should still execute even though A panics
	222	});
	223	}) {
	224	Ok(_) => panic!("failed to propagate panic"),
	225	Err(_) => assert!(x, "job b failed to execute"),
	226	}
	227	}
	228
	229	#[test]
	230	fn panic_propagate_still_execute_2() {
	231	let mut x = false;
	232	match unwind::halt_unwinding(\|\| {
	233	scope(\|s\| {
	234	s.spawn(\|_\| x = true); // job B, should still execute even though A panics
	235	s.spawn(\|_\| panic!("Hello, world!")); // job A
	236	});
	237	}) {
	238	Ok(_) => panic!("failed to propagate panic"),
	239	Err(_) => assert!(x, "job b failed to execute"),
	240	}
	241	}
242
243	#[test]
244	fn panic_propagate_still_execute_3() {
245	let mut x = false;
246	match unwind::halt_unwinding(\|\| {
247	scope(\|s\| {
248	s.spawn(\|_\| x = true); // spanwed job should still execute despite later panic
249	panic!("Hello, world!");
250	});
251	}) {
252	Ok(_) => panic!("failed to propagate panic"),
253	Err(_) => assert!(x, "panic after spawn, spawn failed to execute"),
254	}
255	}
256
257	#[test]
258	fn panic_propagate_still_execute_4() {
259	let mut x = false;
260	match unwind::halt_unwinding(\|\| {
261	scope(\|s\| {
262	s.spawn(\|_\| panic!("Hello, world!"));
263	x = true;
264	});
265	}) {
266	Ok(_) => panic!("failed to propagate panic"),
267	Err(_) => assert!(x, "panic in spawn tainted scope"),
268	}
269	}
e74abb32 XL	270
	271	macro_rules! test_order {
	272	($scope:ident => $spawn:ident) => {{
	273	let builder = ThreadPoolBuilder::new().num_threads(1);
	274	let pool = builder.build().unwrap();
	275	pool.install(\|\| {
	276	let vec = Mutex::new(vec![]);
	277	$scope(\|scope\| {
	278	let vec = &vec;
	279	for i in 0..10 {
	280	scope.$spawn(move \|scope\| {
	281	for j in 0..10 {
	282	scope.$spawn(move \|_\| {
	283	vec.lock().unwrap().push(i * 10 + j);
	284	});
	285	}
	286	});
	287	}
	288	});
	289	vec.into_inner().unwrap()
	290	})
	291	}};
	292	}
	293
	294	#[test]
	295	fn lifo_order() {
	296	// In the absense of stealing, `scope()` runs its `spawn()` jobs in LIFO order.
	297	let vec = test_order!(scope => spawn);
	298	let expected: Vec<i32> = (0..100).rev().collect(); // LIFO -> reversed
	299	assert_eq!(vec, expected);
	300	}
	301
	302	#[test]
	303	fn fifo_order() {
	304	// In the absense of stealing, `scope_fifo()` runs its `spawn_fifo()` jobs in FIFO order.
	305	let vec = test_order!(scope_fifo => spawn_fifo);
	306	let expected: Vec<i32> = (0..100).collect(); // FIFO -> natural order
	307	assert_eq!(vec, expected);
	308	}
	309
	310	macro_rules! test_nested_order {
	311	($outer_scope:ident => $outer_spawn:ident,
	312	$inner_scope:ident => $inner_spawn:ident) => {{
	313	let builder = ThreadPoolBuilder::new().num_threads(1);
	314	let pool = builder.build().unwrap();
	315	pool.install(\|\| {
	316	let vec = Mutex::new(vec![]);
	317	$outer_scope(\|scope\| {
	318	let vec = &vec;
	319	for i in 0..10 {
	320	scope.$outer_spawn(move \|_\| {
	321	$inner_scope(\|scope\| {
	322	for j in 0..10 {
	323	scope.$inner_spawn(move \|_\| {
	324	vec.lock().unwrap().push(i * 10 + j);
	325	});
	326	}
	327	});
	328	});
	329	}
	330	});
	331	vec.into_inner().unwrap()
	332	})
	333	}};
334	}
335
336	#[test]
337	fn nested_lifo_order() {
338	// In the absense of stealing, `scope()` runs its `spawn()` jobs in LIFO order.
339	let vec = test_nested_order!(scope => spawn, scope => spawn);
340	let expected: Vec<i32> = (0..100).rev().collect(); // LIFO -> reversed
341	assert_eq!(vec, expected);
342	}
343
344	#[test]
345	fn nested_fifo_order() {
346	// In the absense of stealing, `scope_fifo()` runs its `spawn_fifo()` jobs in FIFO order.
347	let vec = test_nested_order!(scope_fifo => spawn_fifo, scope_fifo => spawn_fifo);
348	let expected: Vec<i32> = (0..100).collect(); // FIFO -> natural order
349	assert_eq!(vec, expected);
350	}
351
352	#[test]
353	fn nested_lifo_fifo_order() {
354	// LIFO on the outside, FIFO on the inside
355	let vec = test_nested_order!(scope => spawn, scope_fifo => spawn_fifo);
356	let expected: Vec<i32> = (0..10)
357	.rev()
358	.flat_map(\|i\| (0..10).map(move \|j\| i * 10 + j))
359	.collect();
360	assert_eq!(vec, expected);
361	}
362
363	#[test]
364	fn nested_fifo_lifo_order() {
365	// FIFO on the outside, LIFO on the inside
366	let vec = test_nested_order!(scope_fifo => spawn_fifo, scope => spawn);
367	let expected: Vec<i32> = (0..10)
368	.flat_map(\|i\| (0..10).rev().map(move \|j\| i * 10 + j))
369	.collect();
370	assert_eq!(vec, expected);
371	}
372
373	macro_rules! spawn_push {
374	($scope:ident . $spawn:ident, $vec:ident, $i:expr) => {{
375	$scope.$spawn(move \|_\| $vec.lock().unwrap().push($i));
376	}};
377	}
378
379	/// Test spawns pushing a series of numbers, interleaved
380	/// such that negative values are using an inner scope.
381	macro_rules! test_mixed_order {
382	($outer_scope:ident => $outer_spawn:ident,
383	$inner_scope:ident => $inner_spawn:ident) => {{
384	let builder = ThreadPoolBuilder::new().num_threads(1);
385	let pool = builder.build().unwrap();
386	pool.install(\|\| {
387	let vec = Mutex::new(vec![]);
388	$outer_scope(\|outer_scope\| {
389	let vec = &vec;
390	spawn_push!(outer_scope.$outer_spawn, vec, 0);
391	$inner_scope(\|inner_scope\| {
392	spawn_push!(inner_scope.$inner_spawn, vec, -1);
393	spawn_push!(outer_scope.$outer_spawn, vec, 1);
394	spawn_push!(inner_scope.$inner_spawn, vec, -2);
395	spawn_push!(outer_scope.$outer_spawn, vec, 2);
396	spawn_push!(inner_scope.$inner_spawn, vec, -3);
397	});
398	spawn_push!(outer_scope.$outer_spawn, vec, 3);
399	});
400	vec.into_inner().unwrap()
401	})
402	}};
403	}
404
405	#[test]
406	fn mixed_lifo_order() {
407	// NB: the end of the inner scope makes us execute some of the outer scope
408	// before they've all been spawned, so they're not perfectly LIFO.
409	let vec = test_mixed_order!(scope => spawn, scope => spawn);
410	let expected = vec![-3, 2, -2, 1, -1, 3, 0];
411	assert_eq!(vec, expected);
412	}
413
414	#[test]
415	fn mixed_fifo_order() {
416	let vec = test_mixed_order!(scope_fifo => spawn_fifo, scope_fifo => spawn_fifo);
417	let expected = vec![-1, 0, -2, 1, -3, 2, 3];
418	assert_eq!(vec, expected);
419	}
420
421	#[test]
422	fn mixed_lifo_fifo_order() {
423	// NB: the end of the inner scope makes us execute some of the outer scope
424	// before they've all been spawned, so they're not perfectly LIFO.
425	let vec = test_mixed_order!(scope => spawn, scope_fifo => spawn_fifo);
426	let expected = vec![-1, 2, -2, 1, -3, 3, 0];
427	assert_eq!(vec, expected);
428	}
429
430	#[test]
431	fn mixed_fifo_lifo_order() {
432	let vec = test_mixed_order!(scope_fifo => spawn_fifo, scope => spawn);
433	let expected = vec![-3, 0, -2, 1, -1, 2, 3];
434	assert_eq!(vec, expected);
435	}