src/packed/tests.rs

use std::collections::HashMap;
use std::usize;

use packed::{Config, MatchKind};
use Match;

/// A description of a single test against a multi-pattern searcher.
///
/// A single test may not necessarily pass on every configuration of a
/// searcher. The tests are categorized and grouped appropriately below.
#[derive(Clone, Debug, Eq, PartialEq)]
struct SearchTest {
    /// The name of this test, for debugging.
    name: &'static str,
    /// The patterns to search for.
    patterns: &'static [&'static str],
    /// The text to search.
    haystack: &'static str,
    /// Each match is a triple of (pattern_index, start, end), where
    /// pattern_index is an index into `patterns` and `start`/`end` are indices
    /// into `haystack`.
    matches: &'static [(usize, usize, usize)],
}

struct SearchTestOwned {
    offset: usize,
    name: String,
    patterns: Vec<String>,
    haystack: String,
    matches: Vec<(usize, usize, usize)>,
}

impl SearchTest {
    fn variations(&self) -> Vec<SearchTestOwned> {
        let mut tests = vec![];
        for i in 0..=260 {
            tests.push(self.offset_prefix(i));
            tests.push(self.offset_suffix(i));
            tests.push(self.offset_both(i));
        }
        tests
    }

    fn offset_both(&self, off: usize) -> SearchTestOwned {
        SearchTestOwned {
            offset: off,
            name: self.name.to_string(),
            patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
            haystack: format!(
                "{}{}{}",
                "Z".repeat(off),
                self.haystack,
                "Z".repeat(off)
            ),
            matches: self
                .matches
                .iter()
                .map(|&(id, s, e)| (id, s + off, e + off))
                .collect(),
        }
    }

    fn offset_prefix(&self, off: usize) -> SearchTestOwned {
        SearchTestOwned {
            offset: off,
            name: self.name.to_string(),
            patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
            haystack: format!("{}{}", "Z".repeat(off), self.haystack),
            matches: self
                .matches
                .iter()
                .map(|&(id, s, e)| (id, s + off, e + off))
                .collect(),
        }
    }

    fn offset_suffix(&self, off: usize) -> SearchTestOwned {
        SearchTestOwned {
            offset: off,
            name: self.name.to_string(),
            patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
            haystack: format!("{}{}", self.haystack, "Z".repeat(off)),
            matches: self.matches.to_vec(),
        }
    }

    // fn to_owned(&self) -> SearchTestOwned {
    // SearchTestOwned {
    // name: self.name.to_string(),
    // patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
    // haystack: self.haystack.to_string(),
    // matches: self.matches.iter().cloned().collect(),
    // }
    // }
}

/// Short-hand constructor for SearchTest. We use it a lot below.
macro_rules! t {
    ($name:ident, $patterns:expr, $haystack:expr, $matches:expr) => {
        SearchTest {
            name: stringify!($name),
            patterns: $patterns,
            haystack: $haystack,
            matches: $matches,
        }
    };
}

/// A collection of test groups.
type TestCollection = &'static [&'static [SearchTest]];

// Define several collections corresponding to the different type of match
// semantics supported. These collections have some overlap, but each
// collection should have some tests that no other collection has.

/// Tests for leftmost-first match semantics.
const PACKED_LEFTMOST_FIRST: TestCollection =
    &[BASICS, LEFTMOST, LEFTMOST_FIRST, REGRESSION, TEDDY];

/// Tests for leftmost-longest match semantics.
const PACKED_LEFTMOST_LONGEST: TestCollection =
    &[BASICS, LEFTMOST, LEFTMOST_LONGEST, REGRESSION, TEDDY];

// Now define the individual tests that make up the collections above.

/// A collection of tests for the that should always be true regardless of
/// match semantics. That is, all combinations of leftmost-{first, longest}
/// should produce the same answer.
const BASICS: &'static [SearchTest] = &[
    t!(basic001, &["a"], "", &[]),
    t!(basic010, &["a"], "a", &[(0, 0, 1)]),
    t!(basic020, &["a"], "aa", &[(0, 0, 1), (0, 1, 2)]),
    t!(basic030, &["a"], "aaa", &[(0, 0, 1), (0, 1, 2), (0, 2, 3)]),
    t!(basic040, &["a"], "aba", &[(0, 0, 1), (0, 2, 3)]),
    t!(basic050, &["a"], "bba", &[(0, 2, 3)]),
    t!(basic060, &["a"], "bbb", &[]),
    t!(basic070, &["a"], "bababbbba", &[(0, 1, 2), (0, 3, 4), (0, 8, 9)]),
    t!(basic100, &["aa"], "", &[]),
    t!(basic110, &["aa"], "aa", &[(0, 0, 2)]),
    t!(basic120, &["aa"], "aabbaa", &[(0, 0, 2), (0, 4, 6)]),
    t!(basic130, &["aa"], "abbab", &[]),
    t!(basic140, &["aa"], "abbabaa", &[(0, 5, 7)]),
    t!(basic150, &["aaa"], "aaa", &[(0, 0, 3)]),
    t!(basic200, &["abc"], "abc", &[(0, 0, 3)]),
    t!(basic210, &["abc"], "zazabzabcz", &[(0, 6, 9)]),
    t!(basic220, &["abc"], "zazabczabcz", &[(0, 3, 6), (0, 7, 10)]),
    t!(basic300, &["a", "b"], "", &[]),
    t!(basic310, &["a", "b"], "z", &[]),
    t!(basic320, &["a", "b"], "b", &[(1, 0, 1)]),
    t!(basic330, &["a", "b"], "a", &[(0, 0, 1)]),
    t!(
        basic340,
        &["a", "b"],
        "abba",
        &[(0, 0, 1), (1, 1, 2), (1, 2, 3), (0, 3, 4),]
    ),
    t!(
        basic350,
        &["b", "a"],
        "abba",
        &[(1, 0, 1), (0, 1, 2), (0, 2, 3), (1, 3, 4),]
    ),
    t!(basic360, &["abc", "bc"], "xbc", &[(1, 1, 3),]),
    t!(basic400, &["foo", "bar"], "", &[]),
    t!(basic410, &["foo", "bar"], "foobar", &[(0, 0, 3), (1, 3, 6),]),
    t!(basic420, &["foo", "bar"], "barfoo", &[(1, 0, 3), (0, 3, 6),]),
    t!(basic430, &["foo", "bar"], "foofoo", &[(0, 0, 3), (0, 3, 6),]),
    t!(basic440, &["foo", "bar"], "barbar", &[(1, 0, 3), (1, 3, 6),]),
    t!(basic450, &["foo", "bar"], "bafofoo", &[(0, 4, 7),]),
    t!(basic460, &["bar", "foo"], "bafofoo", &[(1, 4, 7),]),
    t!(basic470, &["foo", "bar"], "fobabar", &[(1, 4, 7),]),
    t!(basic480, &["bar", "foo"], "fobabar", &[(0, 4, 7),]),
    t!(basic700, &["yabcdef", "abcdezghi"], "yabcdefghi", &[(0, 0, 7),]),
    t!(basic710, &["yabcdef", "abcdezghi"], "yabcdezghi", &[(1, 1, 10),]),
    t!(
        basic720,
        &["yabcdef", "bcdeyabc", "abcdezghi"],
        "yabcdezghi",
        &[(2, 1, 10),]
    ),
    t!(basic810, &["abcd", "bcd", "cd"], "abcd", &[(0, 0, 4),]),
    t!(basic820, &["bcd", "cd", "abcd"], "abcd", &[(2, 0, 4),]),
    t!(basic830, &["abc", "bc"], "zazabcz", &[(0, 3, 6),]),
    t!(
        basic840,
        &["ab", "ba"],
        "abababa",
        &[(0, 0, 2), (0, 2, 4), (0, 4, 6),]
    ),
    t!(basic850, &["foo", "foo"], "foobarfoo", &[(0, 0, 3), (0, 6, 9),]),
];

/// Tests for leftmost match semantics. These should pass for both
/// leftmost-first and leftmost-longest match kinds. Stated differently, among
/// ambiguous matches, the longest match and the match that appeared first when
/// constructing the automaton should always be the same.
const LEFTMOST: &'static [SearchTest] = &[
    t!(leftmost000, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
    t!(leftmost030, &["a", "ab"], "aa", &[(0, 0, 1), (0, 1, 2)]),
    t!(leftmost031, &["ab", "a"], "aa", &[(1, 0, 1), (1, 1, 2)]),
    t!(leftmost032, &["ab", "a"], "xayabbbz", &[(1, 1, 2), (0, 3, 5)]),
    t!(leftmost300, &["abcd", "bce", "b"], "abce", &[(1, 1, 4)]),
    t!(leftmost310, &["abcd", "ce", "bc"], "abce", &[(2, 1, 3)]),
    t!(leftmost320, &["abcd", "bce", "ce", "b"], "abce", &[(1, 1, 4)]),
    t!(leftmost330, &["abcd", "bce", "cz", "bc"], "abcz", &[(3, 1, 3)]),
    t!(leftmost340, &["bce", "cz", "bc"], "bcz", &[(2, 0, 2)]),
    t!(leftmost350, &["abc", "bd", "ab"], "abd", &[(2, 0, 2)]),
    t!(
        leftmost360,
        &["abcdefghi", "hz", "abcdefgh"],
        "abcdefghz",
        &[(2, 0, 8),]
    ),
    t!(
        leftmost370,
        &["abcdefghi", "cde", "hz", "abcdefgh"],
        "abcdefghz",
        &[(3, 0, 8),]
    ),
    t!(
        leftmost380,
        &["abcdefghi", "hz", "abcdefgh", "a"],
        "abcdefghz",
        &[(2, 0, 8),]
    ),
    t!(
        leftmost390,
        &["b", "abcdefghi", "hz", "abcdefgh"],
        "abcdefghz",
        &[(3, 0, 8),]
    ),
    t!(
        leftmost400,
        &["h", "abcdefghi", "hz", "abcdefgh"],
        "abcdefghz",
        &[(3, 0, 8),]
    ),
    t!(
        leftmost410,
        &["z", "abcdefghi", "hz", "abcdefgh"],
        "abcdefghz",
        &[(3, 0, 8), (0, 8, 9),]
    ),
];

/// Tests for non-overlapping leftmost-first match semantics. These tests
/// should generally be specific to leftmost-first, which means they should
/// generally fail under leftmost-longest semantics.
const LEFTMOST_FIRST: &'static [SearchTest] = &[
    t!(leftfirst000, &["ab", "abcd"], "abcd", &[(0, 0, 2)]),
    t!(leftfirst020, &["abcd", "ab"], "abcd", &[(0, 0, 4)]),
    t!(leftfirst030, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
    t!(leftfirst040, &["a", "ab"], "xayabbbz", &[(0, 1, 2), (0, 3, 4)]),
    t!(leftfirst100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[(1, 1, 5)]),
    t!(leftfirst110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[(1, 1, 6)]),
    t!(leftfirst300, &["abcd", "b", "bce"], "abce", &[(1, 1, 2)]),
    t!(
        leftfirst310,
        &["abcd", "b", "bce", "ce"],
        "abce",
        &[(1, 1, 2), (3, 2, 4),]
    ),
    t!(
        leftfirst320,
        &["a", "abcdefghi", "hz", "abcdefgh"],
        "abcdefghz",
        &[(0, 0, 1), (2, 7, 9),]
    ),
    t!(leftfirst330, &["a", "abab"], "abab", &[(0, 0, 1), (0, 2, 3)]),
    t!(
        leftfirst340,
        &["abcdef", "x", "x", "x", "x", "x", "x", "abcde"],
        "abcdef",
        &[(0, 0, 6)]
    ),
];

/// Tests for non-overlapping leftmost-longest match semantics. These tests
/// should generally be specific to leftmost-longest, which means they should
/// generally fail under leftmost-first semantics.
const LEFTMOST_LONGEST: &'static [SearchTest] = &[
    t!(leftlong000, &["ab", "abcd"], "abcd", &[(1, 0, 4)]),
    t!(leftlong010, &["abcd", "bcd", "cd", "b"], "abcd", &[(0, 0, 4),]),
    t!(leftlong040, &["a", "ab"], "a", &[(0, 0, 1)]),
    t!(leftlong050, &["a", "ab"], "ab", &[(1, 0, 2)]),
    t!(leftlong060, &["ab", "a"], "a", &[(1, 0, 1)]),
    t!(leftlong070, &["ab", "a"], "ab", &[(0, 0, 2)]),
    t!(leftlong100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[(2, 1, 6)]),
    t!(leftlong110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[(1, 1, 6)]),
    t!(leftlong300, &["abcd", "b", "bce"], "abce", &[(2, 1, 4)]),
    t!(
        leftlong310,
        &["a", "abcdefghi", "hz", "abcdefgh"],
        "abcdefghz",
        &[(3, 0, 8),]
    ),
    t!(leftlong320, &["a", "abab"], "abab", &[(1, 0, 4)]),
    t!(leftlong330, &["abcd", "b", "ce"], "abce", &[(1, 1, 2), (2, 2, 4),]),
    t!(leftlong340, &["a", "ab"], "xayabbbz", &[(0, 1, 2), (1, 3, 5)]),
];

/// Regression tests that are applied to all combinations.
///
/// If regression tests are needed for specific match semantics, then add them
/// to the appropriate group above.
const REGRESSION: &'static [SearchTest] = &[
    t!(regression010, &["inf", "ind"], "infind", &[(0, 0, 3), (1, 3, 6),]),
    t!(regression020, &["ind", "inf"], "infind", &[(1, 0, 3), (0, 3, 6),]),
    t!(
        regression030,
        &["libcore/", "libstd/"],
        "libcore/char/methods.rs",
        &[(0, 0, 8),]
    ),
    t!(
        regression040,
        &["libstd/", "libcore/"],
        "libcore/char/methods.rs",
        &[(1, 0, 8),]
    ),
    t!(
        regression050,
        &["\x00\x00\x01", "\x00\x00\x00"],
        "\x00\x00\x00",
        &[(1, 0, 3),]
    ),
    t!(
        regression060,
        &["\x00\x00\x00", "\x00\x00\x01"],
        "\x00\x00\x00",
        &[(0, 0, 3),]
    ),
];

const TEDDY: &'static [SearchTest] = &[
    t!(
        teddy010,
        &["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"],
        "abcdefghijk",
        &[
            (0, 0, 1),
            (1, 1, 2),
            (2, 2, 3),
            (3, 3, 4),
            (4, 4, 5),
            (5, 5, 6),
            (6, 6, 7),
            (7, 7, 8),
            (8, 8, 9),
            (9, 9, 10),
            (10, 10, 11)
        ]
    ),
    t!(
        teddy020,
        &["ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl"],
        "abcdefghijk",
        &[(0, 0, 2), (2, 2, 4), (4, 4, 6), (6, 6, 8), (8, 8, 10),]
    ),
    t!(
        teddy030,
        &["abc"],
        "abcdefghijklmnopqrstuvwxyzabcdefghijk",
        &[(0, 0, 3), (0, 26, 29)]
    ),
];

// Now define a test for each combination of things above that we want to run.
// Since there are a few different combinations for each collection of tests,
// we define a couple of macros to avoid repetition drudgery. The testconfig
// macro constructs the automaton from a given match kind, and runs the search
// tests one-by-one over the given collection. The `with` parameter allows one
// to configure the config with additional parameters. The testcombo macro
// invokes testconfig in precisely this way: it sets up several tests where
// each one turns a different knob on Config.

macro_rules! testconfig {
    ($name:ident, $collection:expr, $with:expr) => {
        #[test]
        fn $name() {
            run_search_tests($collection, |test| {
                let mut config = Config::new();
                $with(&mut config);
                config
                    .builder()
                    .extend(test.patterns.iter().map(|p| p.as_bytes()))
                    .build()
                    .unwrap()
                    .find_iter(&test.haystack)
                    .collect()
            });
        }
    };
}

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_default_leftmost_first,
    PACKED_LEFTMOST_FIRST,
    |_: &mut Config| {}
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_default_leftmost_longest,
    PACKED_LEFTMOST_LONGEST,
    |c: &mut Config| {
        c.match_kind(MatchKind::LeftmostLongest);
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_leftmost_first,
    PACKED_LEFTMOST_FIRST,
    |c: &mut Config| {
        c.force_teddy(true);
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_leftmost_longest,
    PACKED_LEFTMOST_LONGEST,
    |c: &mut Config| {
        c.force_teddy(true).match_kind(MatchKind::LeftmostLongest);
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_ssse3_leftmost_first,
    PACKED_LEFTMOST_FIRST,
    |c: &mut Config| {
        c.force_teddy(true);
        if is_x86_feature_detected!("ssse3") {
            c.force_avx(Some(false));
        }
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_ssse3_leftmost_longest,
    PACKED_LEFTMOST_LONGEST,
    |c: &mut Config| {
        c.force_teddy(true).match_kind(MatchKind::LeftmostLongest);
        if is_x86_feature_detected!("ssse3") {
            c.force_avx(Some(false));
        }
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_avx2_leftmost_first,
    PACKED_LEFTMOST_FIRST,
    |c: &mut Config| {
        c.force_teddy(true);
        if is_x86_feature_detected!("avx2") {
            c.force_avx(Some(true));
        }
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_avx2_leftmost_longest,
    PACKED_LEFTMOST_LONGEST,
    |c: &mut Config| {
        c.force_teddy(true).match_kind(MatchKind::LeftmostLongest);
        if is_x86_feature_detected!("avx2") {
            c.force_avx(Some(true));
        }
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_fat_leftmost_first,
    PACKED_LEFTMOST_FIRST,
    |c: &mut Config| {
        c.force_teddy(true);
        if is_x86_feature_detected!("avx2") {
            c.force_teddy_fat(Some(true));
        }
    }
);

#[cfg(target_arch = "x86_64")]
testconfig!(
    search_teddy_fat_leftmost_longest,
    PACKED_LEFTMOST_LONGEST,
    |c: &mut Config| {
        c.force_teddy(true).match_kind(MatchKind::LeftmostLongest);
        if is_x86_feature_detected!("avx2") {
            c.force_teddy_fat(Some(true));
        }
    }
);

testconfig!(
    search_rabinkarp_leftmost_first,
    PACKED_LEFTMOST_FIRST,
    |c: &mut Config| {
        c.force_rabin_karp(true);
    }
);

testconfig!(
    search_rabinkarp_leftmost_longest,
    PACKED_LEFTMOST_LONGEST,
    |c: &mut Config| {
        c.force_rabin_karp(true).match_kind(MatchKind::LeftmostLongest);
    }
);

#[test]
fn search_tests_have_unique_names() {
    let assert = |constname, tests: &[SearchTest]| {
        let mut seen = HashMap::new(); // map from test name to position
        for (i, test) in tests.iter().enumerate() {
            if !seen.contains_key(test.name) {
                seen.insert(test.name, i);
            } else {
                let last = seen[test.name];
                panic!(
                    "{} tests have duplicate names at positions {} and {}",
                    constname, last, i
                );
            }
        }
    };
    assert("BASICS", BASICS);
    assert("LEFTMOST", LEFTMOST);
    assert("LEFTMOST_FIRST", LEFTMOST_FIRST);
    assert("LEFTMOST_LONGEST", LEFTMOST_LONGEST);
    assert("REGRESSION", REGRESSION);
    assert("TEDDY", TEDDY);
}

fn run_search_tests<F: FnMut(&SearchTestOwned) -> Vec<Match>>(
    which: TestCollection,
    mut f: F,
) {
    let get_match_triples =
        |matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
            matches
                .into_iter()
                .map(|m| (m.pattern(), m.start(), m.end()))
                .collect()
        };
    for &tests in which {
        for spec in tests {
            for test in spec.variations() {
                assert_eq!(
                    test.matches,
                    get_match_triples(f(&test)).as_slice(),
                    "test: {}, patterns: {:?}, haystack: {:?}, offset: {:?}",
                    test.name,
                    test.patterns,
                    test.haystack,
                    test.offset,
                );
            }
        }
    }
}