itertools/tests/specializations.rs

//! Test specializations of methods with default impls match the behavior of the
//! default impls.
//!
//! **NOTE:** Due to performance limitations, these tests are not run with miri!
//! They cannot be relied upon to discover soundness issues.

#![cfg(not(miri))]
#![allow(unstable_name_collisions)]

use itertools::Itertools;
use quickcheck::Arbitrary;
use quickcheck::{quickcheck, TestResult};
use rand::Rng;
use std::fmt::Debug;

struct Unspecialized<I>(I);

impl<I> Iterator for Unspecialized<I>
where
    I: Iterator,
{
    type Item = I::Item;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

impl<I> DoubleEndedIterator for Unspecialized<I>
where
    I: DoubleEndedIterator,
{
    #[inline(always)]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back()
    }
}

fn test_specializations<I>(it: &I)
where
    I::Item: Eq + Debug + Clone,
    I: Iterator + Clone,
{
    macro_rules! check_specialized {
        ($src:expr, |$it:pat| $closure:expr) => {
            // Many iterators special-case the first elements, so we test specializations for iterators that have already been advanced.
            let mut src = $src.clone();
            for _ in 0..5 {
                let $it = src.clone();
                let v1 = $closure;
                let $it = Unspecialized(src.clone());
                let v2 = $closure;
                assert_eq!(v1, v2);
                src.next();
            }
        }
    }
    check_specialized!(it, |i| i.count());
    check_specialized!(it, |i| i.last());
    check_specialized!(it, |i| i.collect::<Vec<_>>());
    check_specialized!(it, |i| {
        let mut parameters_from_fold = vec![];
        let fold_result = i.fold(vec![], |mut acc, v: I::Item| {
            parameters_from_fold.push((acc.clone(), v.clone()));
            acc.push(v);
            acc
        });
        (parameters_from_fold, fold_result)
    });
    check_specialized!(it, |mut i| {
        let mut parameters_from_all = vec![];
        let first = i.next();
        let all_result = i.all(|x| {
            parameters_from_all.push(x.clone());
            Some(x) == first
        });
        (parameters_from_all, all_result)
    });
    let size = it.clone().count();
    for n in 0..size + 2 {
        check_specialized!(it, |mut i| i.nth(n));
    }
    // size_hint is a bit harder to check
    let mut it_sh = it.clone();
    for n in 0..size + 2 {
        let len = it_sh.clone().count();
        let (min, max) = it_sh.size_hint();
        assert_eq!(size - n.min(size), len);
        assert!(min <= len);
        if let Some(max) = max {
            assert!(len <= max);
        }
        it_sh.next();
    }
}

fn test_double_ended_specializations<I>(it: &I)
where
    I::Item: Eq + Debug + Clone,
    I: DoubleEndedIterator + Clone,
{
    macro_rules! check_specialized {
        ($src:expr, |$it:pat| $closure:expr) => {
            // Many iterators special-case the first elements, so we test specializations for iterators that have already been advanced.
            let mut src = $src.clone();
            for step in 0..8 {
                let $it = src.clone();
                let v1 = $closure;
                let $it = Unspecialized(src.clone());
                let v2 = $closure;
                assert_eq!(v1, v2);
                if step % 2 == 0 {
                    src.next();
                } else {
                    src.next_back();
                }
            }
        }
    }
    check_specialized!(it, |i| {
        let mut parameters_from_rfold = vec![];
        let rfold_result = i.rfold(vec![], |mut acc, v: I::Item| {
            parameters_from_rfold.push((acc.clone(), v.clone()));
            acc.push(v);
            acc
        });
        (parameters_from_rfold, rfold_result)
    });
    let size = it.clone().count();
    for n in 0..size + 2 {
        check_specialized!(it, |mut i| i.nth_back(n));
    }
}

quickcheck! {
    fn interleave(v: Vec<u8>, w: Vec<u8>) -> () {
        test_specializations(&v.iter().interleave(w.iter()));
    }

    fn interleave_shortest(v: Vec<u8>, w: Vec<u8>) -> () {
        test_specializations(&v.iter().interleave_shortest(w.iter()));
    }

    fn batching(v: Vec<u8>) -> () {
        test_specializations(&v.iter().batching(Iterator::next));
    }

    fn tuple_windows(v: Vec<u8>) -> () {
        test_specializations(&v.iter().tuple_windows::<(_,)>());
        test_specializations(&v.iter().tuple_windows::<(_, _)>());
        test_specializations(&v.iter().tuple_windows::<(_, _, _)>());
    }

    fn circular_tuple_windows(v: Vec<u8>) -> () {
        test_specializations(&v.iter().circular_tuple_windows::<(_,)>());
        test_specializations(&v.iter().circular_tuple_windows::<(_, _)>());
        test_specializations(&v.iter().circular_tuple_windows::<(_, _, _)>());
    }

    fn tuples(v: Vec<u8>) -> () {
        test_specializations(&v.iter().tuples::<(_,)>());
        test_specializations(&v.iter().tuples::<(_, _)>());
        test_specializations(&v.iter().tuples::<(_, _, _)>());
    }

    fn cartesian_product(a: Vec<u8>, b: Vec<u8>) -> TestResult {
        if a.len() * b.len() > 100 {
            return TestResult::discard();
        }
        test_specializations(&a.iter().cartesian_product(&b));
        TestResult::passed()
    }

    fn multi_cartesian_product(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
        if a.len() * b.len() * c.len() > 100 {
            return TestResult::discard();
        }
        test_specializations(&vec![a, b, c].into_iter().multi_cartesian_product());
        TestResult::passed()
    }

    fn coalesce(v: Vec<u8>) -> () {
        test_specializations(&v.iter().coalesce(|x, y| if x == y { Ok(x) } else { Err((x, y)) }))
    }

    fn dedup(v: Vec<u8>) -> () {
        test_specializations(&v.iter().dedup())
    }

    fn dedup_by(v: Vec<u8>) -> () {
        test_specializations(&v.iter().dedup_by(PartialOrd::ge))
    }

    fn dedup_with_count(v: Vec<u8>) -> () {
        test_specializations(&v.iter().dedup_with_count())
    }

    fn dedup_by_with_count(v: Vec<u8>) -> () {
        test_specializations(&v.iter().dedup_by_with_count(PartialOrd::ge))
    }

    fn duplicates(v: Vec<u8>) -> () {
        let it = v.iter().duplicates();
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn duplicates_by(v: Vec<u8>) -> () {
        let it = v.iter().duplicates_by(|x| *x % 10);
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn unique(v: Vec<u8>) -> () {
        let it = v.iter().unique();
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn unique_by(v: Vec<u8>) -> () {
        let it = v.iter().unique_by(|x| *x % 50);
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn take_while_inclusive(v: Vec<u8>) -> () {
        test_specializations(&v.iter().copied().take_while_inclusive(|&x| x < 100));
    }

    fn while_some(v: Vec<u8>) -> () {
        test_specializations(&v.iter().map(|&x| if x < 100 { Some(2 * x) } else { None }).while_some());
    }

    fn pad_using(v: Vec<u8>) -> () {
        use std::convert::TryFrom;
        let it = v.iter().copied().pad_using(10, |i| u8::try_from(5 * i).unwrap_or(u8::MAX));
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn with_position(v: Vec<u8>) -> () {
        test_specializations(&v.iter().with_position());
    }

    fn positions(v: Vec<u8>) -> () {
        let it = v.iter().positions(|x| x % 5 == 0);
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn update(v: Vec<u8>) -> () {
        let it = v.iter().copied().update(|x| *x = x.wrapping_mul(7));
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn tuple_combinations(v: Vec<u8>) -> TestResult {
        if v.len() > 10 {
            return TestResult::discard();
        }
        test_specializations(&v.iter().tuple_combinations::<(_,)>());
        test_specializations(&v.iter().tuple_combinations::<(_, _)>());
        test_specializations(&v.iter().tuple_combinations::<(_, _, _)>());
        TestResult::passed()
    }

    fn intersperse(v: Vec<u8>) -> () {
        test_specializations(&v.into_iter().intersperse(0));
    }

    fn intersperse_with(v: Vec<u8>) -> () {
        test_specializations(&v.into_iter().intersperse_with(|| 0));
    }

    fn array_combinations(v: Vec<u8>) -> TestResult {
        if v.len() > 10 {
            return TestResult::discard();
        }
        test_specializations(&v.iter().array_combinations::<1>());
        test_specializations(&v.iter().array_combinations::<2>());
        test_specializations(&v.iter().array_combinations::<3>());
        TestResult::passed()
    }

    fn combinations(a: Vec<u8>, n: u8) -> TestResult {
        if n > 3 || a.len() > 8 {
            return TestResult::discard();
        }
        test_specializations(&a.iter().combinations(n as usize));
        TestResult::passed()
    }

    fn combinations_with_replacement(a: Vec<u8>, n: u8) -> TestResult {
        if n > 3 || a.len() > 7 {
            return TestResult::discard();
        }
        test_specializations(&a.iter().combinations_with_replacement(n as usize));
        TestResult::passed()
    }

    fn permutations(a: Vec<u8>, n: u8) -> TestResult {
        if n > 3 || a.len() > 8 {
            return TestResult::discard();
        }
        test_specializations(&a.iter().permutations(n as usize));
        TestResult::passed()
    }

    fn powerset(a: Vec<u8>) -> TestResult {
        if a.len() > 6 {
            return TestResult::discard();
        }
        test_specializations(&a.iter().powerset());
        TestResult::passed()
    }

    fn zip_longest(a: Vec<u8>, b: Vec<u8>) -> () {
        let it = a.into_iter().zip_longest(b);
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn zip_eq(a: Vec<u8>) -> () {
        test_specializations(&a.iter().zip_eq(a.iter().rev()))
    }

    fn multizip(a: Vec<u8>) -> () {
        let it = itertools::multizip((a.iter(), a.iter().rev(), a.iter().take(50)));
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn izip(a: Vec<u8>, b: Vec<u8>) -> () {
        test_specializations(&itertools::izip!(b.iter(), a, b.iter().rev()));
    }

    fn iproduct(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
        if a.len() * b.len() * c.len() > 200 {
            return TestResult::discard();
        }
        test_specializations(&itertools::iproduct!(a, b.iter(), c));
        TestResult::passed()
    }

    fn repeat_n(element: i8, n: u8) -> () {
        let it = itertools::repeat_n(element, n as usize);
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn exactly_one_error(v: Vec<u8>) -> TestResult {
        // Use `at_most_one` would be similar.
        match v.iter().exactly_one() {
            Ok(_) => TestResult::discard(),
            Err(it) => {
                test_specializations(&it);
                TestResult::passed()
            }
        }
    }
}

quickcheck! {
    fn put_back_qc(test_vec: Vec<i32>) -> () {
        test_specializations(&itertools::put_back(test_vec.iter()));
        let mut pb = itertools::put_back(test_vec.into_iter());
        pb.put_back(1);
        test_specializations(&pb);
    }

    fn put_back_n(v: Vec<u8>, n: u8) -> () {
        let mut it = itertools::put_back_n(v);
        for k in 0..n {
            it.put_back(k);
        }
        test_specializations(&it);
    }

    fn multipeek(v: Vec<u8>, n: u8) -> () {
        let mut it = v.into_iter().multipeek();
        for _ in 0..n {
            it.peek();
        }
        test_specializations(&it);
    }

    fn peek_nth_with_peek(v: Vec<u8>, n: u8) -> () {
        let mut it = itertools::peek_nth(v);
        for _ in 0..n {
            it.peek();
        }
        test_specializations(&it);
    }

    fn peek_nth_with_peek_nth(v: Vec<u8>, n: u8) -> () {
        let mut it = itertools::peek_nth(v);
        it.peek_nth(n as usize);
        test_specializations(&it);
    }

    fn peek_nth_with_peek_mut(v: Vec<u8>, n: u8) -> () {
        let mut it = itertools::peek_nth(v);
        for _ in 0..n {
            if let Some(x) = it.peek_mut() {
                *x = x.wrapping_add(50);
            }
        }
        test_specializations(&it);
    }

    fn peek_nth_with_peek_nth_mut(v: Vec<u8>, n: u8) -> () {
        let mut it = itertools::peek_nth(v);
        if let Some(x) = it.peek_nth_mut(n as usize) {
            *x = x.wrapping_add(50);
        }
        test_specializations(&it);
    }
}

quickcheck! {
    fn merge(a: Vec<u8>, b: Vec<u8>) -> () {
        test_specializations(&a.into_iter().merge(b))
    }

    fn merge_by(a: Vec<u8>, b: Vec<u8>) -> () {
        test_specializations(&a.into_iter().merge_by(b, PartialOrd::ge))
    }

    fn merge_join_by_ordering(i1: Vec<u8>, i2: Vec<u8>) -> () {
        test_specializations(&i1.into_iter().merge_join_by(i2, Ord::cmp));
    }

    fn merge_join_by_bool(i1: Vec<u8>, i2: Vec<u8>) -> () {
        test_specializations(&i1.into_iter().merge_join_by(i2, PartialOrd::ge));
    }

    fn kmerge(a: Vec<i8>, b: Vec<i8>, c: Vec<i8>) -> () {
        test_specializations(&vec![a, b, c]
            .into_iter()
            .map(|v| v.into_iter().sorted())
            .kmerge());
    }

    fn kmerge_by(a: Vec<i8>, b: Vec<i8>, c: Vec<i8>) -> () {
        test_specializations(&vec![a, b, c]
            .into_iter()
            .map(|v| v.into_iter().sorted_by_key(|a| a.abs()))
            .kmerge_by(|a, b| a.abs() < b.abs()));
    }
}

quickcheck! {
    fn map_into(v: Vec<u8>) -> () {
        let it = v.into_iter().map_into::<u32>();
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn map_ok(v: Vec<Result<u8, char>>) -> () {
        let it = v.into_iter().map_ok(|u| u.checked_add(1));
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn filter_ok(v: Vec<Result<u8, char>>) -> () {
        let it = v.into_iter().filter_ok(|&i| i < 20);
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    fn filter_map_ok(v: Vec<Result<u8, char>>) -> () {
        let it = v.into_iter().filter_map_ok(|i| if i < 20 { Some(i * 2) } else { None });
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }

    // `SmallIter2<u8>` because `Vec<u8>` is too slow and we get bad coverage from a singleton like Option<u8>
    fn flatten_ok(v: Vec<Result<SmallIter2<u8>, char>>) -> () {
        let it = v.into_iter().flatten_ok();
        test_specializations(&it);
        test_double_ended_specializations(&it);
    }
}

quickcheck! {
    // TODO Replace this function by a normal call to test_specializations
    fn process_results(v: Vec<Result<u8, u8>>) -> () {
        helper(v.iter().copied());
        helper(v.iter().copied().filter(Result::is_ok));

        fn helper(it: impl DoubleEndedIterator<Item = Result<u8, u8>> + Clone) {
            macro_rules! check_results_specialized {
                ($src:expr, |$it:pat| $closure:expr) => {
                    assert_eq!(
                        itertools::process_results($src.clone(), |$it| $closure),
                        itertools::process_results($src.clone(), |i| {
                            let $it = Unspecialized(i);
                            $closure
                        }),
                    )
                }
            }

            check_results_specialized!(it, |i| i.count());
            check_results_specialized!(it, |i| i.last());
            check_results_specialized!(it, |i| i.collect::<Vec<_>>());
            check_results_specialized!(it, |i| i.rev().collect::<Vec<_>>());
            check_results_specialized!(it, |i| {
                let mut parameters_from_fold = vec![];
                let fold_result = i.fold(vec![], |mut acc, v| {
                    parameters_from_fold.push((acc.clone(), v));
                    acc.push(v);
                    acc
                });
                (parameters_from_fold, fold_result)
            });
            check_results_specialized!(it, |i| {
                let mut parameters_from_rfold = vec![];
                let rfold_result = i.rfold(vec![], |mut acc, v| {
                    parameters_from_rfold.push((acc.clone(), v));
                    acc.push(v);
                    acc
                });
                (parameters_from_rfold, rfold_result)
            });
            check_results_specialized!(it, |mut i| {
                let mut parameters_from_all = vec![];
                let first = i.next();
                let all_result = i.all(|x| {
                    parameters_from_all.push(x);
                    Some(x)==first
                });
                (parameters_from_all, all_result)
            });
            let size = it.clone().count();
            for n in 0..size + 2 {
                check_results_specialized!(it, |mut i| i.nth(n));
            }
            for n in 0..size + 2 {
                check_results_specialized!(it, |mut i| i.nth_back(n));
            }
        }
    }
}

/// Like `VecIntoIter<T>` with maximum 2 elements.
#[derive(Debug, Clone, Default)]
enum SmallIter2<T> {
    #[default]
    Zero,
    One(T),
    Two(T, T),
}

impl<T: Arbitrary> Arbitrary for SmallIter2<T> {
    fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
        match g.gen_range(0u8, 3) {
            0 => Self::Zero,
            1 => Self::One(T::arbitrary(g)),
            2 => Self::Two(T::arbitrary(g), T::arbitrary(g)),
            _ => unreachable!(),
        }
    }
    // maybe implement shrink too, maybe not
}

impl<T> Iterator for SmallIter2<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        match std::mem::take(self) {
            Self::Zero => None,
            Self::One(val) => Some(val),
            Self::Two(val, second) => {
                *self = Self::One(second);
                Some(val)
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = match self {
            Self::Zero => 0,
            Self::One(_) => 1,
            Self::Two(_, _) => 2,
        };
        (len, Some(len))
    }
}

impl<T> DoubleEndedIterator for SmallIter2<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        match std::mem::take(self) {
            Self::Zero => None,
            Self::One(val) => Some(val),
            Self::Two(first, val) => {
                *self = Self::One(first);
                Some(val)
            }
        }
    }
}