proptest/

string.rs

//-
// Copyright 2017 Jason Lingle
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Strategies for generating strings and byte strings from regular
//! expressions.

use crate::std_facade::{Box, Cow, String, ToOwned, Vec};
use core::fmt;
use core::mem;
use core::ops::RangeInclusive;
use core::u32;

use regex_syntax::hir::{self, Hir, HirKind::*, Repetition};
use regex_syntax::{Error as ParseError, ParserBuilder};

use crate::bool;
use crate::char;
use crate::collection::{size_range, vec, SizeRange};
use crate::strategy::*;
use crate::test_runner::*;

/// Wraps the regex that forms the `Strategy` for `String` so that a sensible
/// `Default` can be given. The default is a string of non-control characters.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct StringParam(&'static str);

impl From<StringParam> for &'static str {
    fn from(x: StringParam) -> Self {
        x.0
    }
}

impl From<&'static str> for StringParam {
    fn from(x: &'static str) -> Self {
        StringParam(x)
    }
}

impl Default for StringParam {
    fn default() -> Self {
        StringParam("\\PC*")
    }
}

/// Errors which may occur when preparing a regular expression for use with
/// string generation.
#[derive(Debug)]
pub enum Error {
    /// The string passed as the regex was not syntactically valid.
    RegexSyntax(ParseError),
    /// The regex was syntactically valid, but contains elements not
    /// supported by proptest.
    UnsupportedRegex(&'static str),
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Error::RegexSyntax(err) => write!(f, "{}", err),
            Error::UnsupportedRegex(message) => write!(f, "{}", message),
        }
    }
}

impl std::error::Error for Error {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            Error::RegexSyntax(err) => Some(err),
            Error::UnsupportedRegex(_) => None,
        }
    }
}

impl From<ParseError> for Error {
    fn from(err: ParseError) -> Error {
        Error::RegexSyntax(err)
    }
}

opaque_strategy_wrapper! {
    /// Strategy which generates values (i.e., `String` or `Vec<u8>`) matching
    /// a regular expression.
    ///
    /// Created by various functions in this module.
    #[derive(Debug)]
    pub struct RegexGeneratorStrategy[<T>][where T : fmt::Debug]
        (SBoxedStrategy<T>) -> RegexGeneratorValueTree<T>;
    /// `ValueTree` corresponding to `RegexGeneratorStrategy`.
    pub struct RegexGeneratorValueTree[<T>][where T : fmt::Debug]
        (Box<dyn ValueTree<Value = T>>) -> T;
}

impl Strategy for str {
    type Tree = RegexGeneratorValueTree<String>;
    type Value = String;

    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
        string_regex(self).unwrap().new_tree(runner)
    }
}

type ParseResult<T> = Result<RegexGeneratorStrategy<T>, Error>;

#[doc(hidden)]
/// A type which knows how to produce a `Strategy` from a regular expression
/// generating the type.
///
/// This trait exists for the benefit of `#[proptest(regex = "...")]`.
/// It is semver exempt, so use at your own risk.
/// If you found a use for the trait beyond `Vec<u8>` and `String`,
/// please file an issue at https://github.com/proptest-rs/proptest.
pub trait StrategyFromRegex: Sized + fmt::Debug {
    type Strategy: Strategy<Value = Self>;

    /// Produce a strategy for `Self` from the `regex`.
    fn from_regex(regex: &str) -> Self::Strategy;
}

impl StrategyFromRegex for String {
    type Strategy = RegexGeneratorStrategy<Self>;

    fn from_regex(regex: &str) -> Self::Strategy {
        string_regex(regex).unwrap()
    }
}

impl StrategyFromRegex for Vec<u8> {
    type Strategy = RegexGeneratorStrategy<Self>;

    fn from_regex(regex: &str) -> Self::Strategy {
        bytes_regex(regex).unwrap()
    }
}

/// Creates a strategy which generates strings matching the given regular
/// expression.
///
/// If you don't need error handling and aren't limited by setup time, it is
/// also possible to directly use a `&str` as a strategy with the same effect.
pub fn string_regex(regex: &str) -> ParseResult<String> {
    let hir = ParserBuilder::new().build().parse(regex)?;
    string_regex_parsed(&hir)
}

/// Like `string_regex()`, but allows providing a pre-parsed expression.
pub fn string_regex_parsed(expr: &Hir) -> ParseResult<String> {
    bytes_regex_parsed(expr)
        .map(|v| {
            v.prop_map(|bytes| {
                String::from_utf8(bytes).expect("non-utf8 string")
            })
            .sboxed()
        })
        .map(RegexGeneratorStrategy)
}

/// Creates a strategy which generates byte strings matching the given regular
/// expression.
///
/// By default, the byte strings generated by this strategy _will_ be valid
/// UTF-8.  If you wish to generate byte strings that aren't (necessarily)
/// valid UTF-8, wrap your regex (or some subsection of it) in `(?-u: ... )`.
/// You may want to turn on the `s` flag as well (`(?s-u: ... )`) so that `.`
/// will generate newline characters (byte value `0x0A`).  See the
/// [`regex` crate's documentation](https://docs.rs/regex/*/regex/#opt-out-of-unicode-support)
/// for more information.
pub fn bytes_regex(regex: &str) -> ParseResult<Vec<u8>> {
    let hir = ParserBuilder::new()
        .utf8(false)
        .build()
        .parse(regex)?;
    bytes_regex_parsed(&hir)
}

/// Like `bytes_regex()`, but allows providing a pre-parsed expression.
pub fn bytes_regex_parsed(expr: &Hir) -> ParseResult<Vec<u8>> {
    match expr.kind() {
        Empty => Ok(Just(vec![]).sboxed()),

        Literal(lit) => Ok(Just(lit.0.to_vec()).sboxed()),

        Class(class) => Ok(match class {
            hir::Class::Unicode(class) => {
                unicode_class_strategy(class).prop_map(to_bytes).sboxed()
            }
            hir::Class::Bytes(class) => {
                let subs = class.iter().map(|r| r.start()..=r.end());
                Union::new(subs).prop_map(|b| vec![b]).sboxed()
            }
        }),

        Repetition(rep) => {
            Ok(vec(bytes_regex_parsed(&rep.sub)?, to_range(rep)?)
                .prop_map(|parts| parts.concat())
                .sboxed())
        }

        Capture(capture) => bytes_regex_parsed(&capture.sub).map(|v| v.0),

        Concat(subs) => {
            let subs = ConcatIter {
                iter: subs.iter(),
                buf: vec![],
                next: None,
            };
            let ext = |(mut lhs, rhs): (Vec<_>, _)| {
                lhs.extend(rhs);
                lhs
            };
            Ok(subs
                .fold(Ok(None), |accum: Result<_, Error>, rhs| {
                    Ok(match accum? {
                        None => Some(rhs?.sboxed()),
                        Some(accum) => {
                            Some((accum, rhs?).prop_map(ext).sboxed())
                        }
                    })
                })?
                .unwrap_or_else(|| Just(vec![]).sboxed()))
        }

        Alternation(subs) => {
            Ok(Union::try_new(subs.iter().map(bytes_regex_parsed))?.sboxed())
        }

        Look(_) => unsupported(
            "anchors/boundaries not supported for string generation",
        ),
    }
    .map(RegexGeneratorStrategy)
}

fn unicode_class_strategy(
    class: &hir::ClassUnicode,
) -> char::CharStrategy<'static> {
    static NONL_RANGES: &[RangeInclusive<char>] = &[
        '\x00'..='\x09',
        // Multiple instances of the latter range to partially make up
        // for the bias of having such a tiny range in the control
        // characters.
        '\x0B'..=::core::char::MAX,
        '\x0B'..=::core::char::MAX,
        '\x0B'..=::core::char::MAX,
        '\x0B'..=::core::char::MAX,
        '\x0B'..=::core::char::MAX,
    ];

    let dotnnl = |x: &hir::ClassUnicodeRange, y: &hir::ClassUnicodeRange| {
        x.start() == '\0'
            && x.end() == '\x09'
            && y.start() == '\x0B'
            && y.end() == '\u{10FFFF}'
    };

    char::ranges(match class.ranges() {
        [x, y] if dotnnl(x, y) || dotnnl(y, x) => Cow::Borrowed(NONL_RANGES),
        _ => Cow::Owned(class.iter().map(|r| r.start()..=r.end()).collect()),
    })
}

struct ConcatIter<'a, I> {
    buf: Vec<u8>,
    iter: I,
    next: Option<&'a Hir>,
}

fn flush_lit_buf<I>(
    it: &mut ConcatIter<'_, I>,
) -> Option<ParseResult<Vec<u8>>> {
    Some(Ok(RegexGeneratorStrategy(
        Just(mem::replace(&mut it.buf, vec![])).sboxed(),
    )))
}

impl<'a, I: Iterator<Item = &'a Hir>> Iterator for ConcatIter<'a, I> {
    type Item = ParseResult<Vec<u8>>;

    fn next(&mut self) -> Option<Self::Item> {
        // A left-over node, process it first:
        if let Some(next) = self.next.take() {
            return Some(bytes_regex_parsed(next));
        }

        // Accumulate a literal sequence as long as we can:
        while let Some(next) = self.iter.next() {
            match next.kind() {
                // A literal. Accumulate:
                Literal(literal) => self.buf.extend_from_slice(&literal.0),
                // Encountered a non-literal.
                _ => {
                    return if !self.buf.is_empty() {
                        // We've accumulated a literal from before, flush it out.
                        // Store this node so we deal with it the next call.
                        self.next = Some(next);
                        flush_lit_buf(self)
                    } else {
                        // We didn't; just yield this node.
                        Some(bytes_regex_parsed(next))
                    };
                }
            }
        }

        // Flush out any accumulated literal from before.
        if !self.buf.is_empty() {
            flush_lit_buf(self)
        } else {
            self.next.take().map(bytes_regex_parsed)
        }
    }
}

fn to_range(rep: &Repetition) -> Result<SizeRange, Error> {
    Ok(match (rep.min, rep.max) {
        // Zero or one
        (0, Some(1)) => size_range(0..=1),
        // Zero or more
        (0, None) => size_range(0..=32),
        // One or more
        (1, None) => size_range(1..=32),
        // Exact count of u32::MAX
        (u32::MAX, Some(u32::MAX)) => {
            return unsupported("Cannot have repetition of exactly u32::MAX");
        }
        // Exact count
        (min, Some(max)) if min == max => size_range(min as usize),
        // At least min
        (min, None) => {
            let max = if min < u32::MAX as u32 / 2 {
                min as usize * 2
            } else {
                u32::MAX as usize
            };
            size_range((min as usize)..max)
        }
        // Bounded range with max of u32::MAX
        (_, Some(u32::MAX)) => {
            return unsupported("Cannot have repetition max of u32::MAX")
        }
        // Bounded range
        (min, Some(max)) => size_range((min as usize)..(max as usize + 1)),
    })
}

fn to_bytes(khar: char) -> Vec<u8> {
    let mut buf = [0u8; 4];
    khar.encode_utf8(&mut buf).as_bytes().to_owned()
}

fn unsupported<T>(error: &'static str) -> Result<T, Error> {
    Err(Error::UnsupportedRegex(error))
}

#[cfg(test)]
mod test {
    use std::collections::HashSet;

    use regex::Regex;
    use regex::bytes::Regex as BytesRegex;

    use super::*;

    fn printable_ascii(v: &[u8]) -> String {
        v.iter()
            .flat_map(|c| std::ascii::escape_default(*c))
            .map(|c| char::from_u32(c.into()).unwrap())
            .collect()
    }

    fn do_test(
        pattern: &str,
        min_distinct: usize,
        max_distinct: usize,
        iterations: usize,
    ) {
        let generated = generate_values_matching_regex(pattern, iterations);
        assert!(
            generated.len() >= min_distinct,
            "Expected to generate at least {} strings, but only \
             generated {}",
            min_distinct,
            generated.len()
        );
        assert!(
            generated.len() <= max_distinct,
            "Expected to generate at most {} strings, but \
             generated {}",
            max_distinct,
            generated.len()
        );
    }

    fn do_test_bytes(
        pattern: &str,
        min_distinct: usize,
        max_distinct: usize,
        iterations: usize,
    ) {
        let generated = generate_byte_values_matching_regex(pattern, iterations);
        assert!(
            generated.len() >= min_distinct,
            "Expected to generate at least {} strings, but only \
             generated {}",
            min_distinct,
            generated.len()
        );
        assert!(
            generated.len() <= max_distinct,
            "Expected to generate at most {} strings, but \
             generated {}",
            max_distinct,
            generated.len()
        );
    }

    fn generate_values_matching_regex(
        pattern: &str,
        iterations: usize,
    ) -> HashSet<String> {
        let rx = Regex::new(pattern).unwrap();
        let mut generated = HashSet::new();

        let strategy = string_regex(pattern).unwrap();
        let mut runner = TestRunner::deterministic();
        for _ in 0..iterations {
            let mut value = strategy.new_tree(&mut runner).unwrap();

            loop {
                let s = value.current();
                let ok = if let Some(matsch) = rx.find(&s) {
                    0 == matsch.start() && s.len() == matsch.end()
                } else {
                    false
                };
                if !ok {
                    panic!(
                        "Generated string {:?} which does not match {:?}",
                        s, pattern
                    );
                }

                generated.insert(s);

                if !value.simplify() {
                    break;
                }
            }
        }
        generated
    }

    fn generate_byte_values_matching_regex(
        pattern: &str,
        iterations: usize,
    ) -> HashSet<Vec<u8>> {
        let rx = BytesRegex::new(pattern).unwrap();
        let mut generated = HashSet::new();

        let strategy = bytes_regex(pattern).unwrap();
        let mut runner = TestRunner::deterministic();
        for _ in 0..iterations {
            let mut value = strategy.new_tree(&mut runner).unwrap();

            loop {
                let s = value.current();
                let ok = if let Some(matsch) = rx.find(&s) {
                    0 == matsch.start() && s.len() == matsch.end()
                } else {
                    false
                };
                if !ok {
                    panic!(
                        "Generated string {:?} which does not match {:?}",
                        printable_ascii(&s), pattern
                    );
                }

                generated.insert(s);

                if !value.simplify() {
                    break;
                }
            }
        }
        generated
    }

    #[test]
    fn test_case_insensitive_produces_all_available_values() {
        let mut expected: HashSet<String> = HashSet::new();
        expected.insert("a".into());
        expected.insert("b".into());
        expected.insert("A".into());
        expected.insert("B".into());
        assert_eq!(generate_values_matching_regex("(?i:a|B)", 64), expected);
    }

    #[test]
    fn test_literal() {
        do_test("foo", 1, 1, 8);
        do_test_bytes("foo", 1, 1, 8);
    }

    #[test]
    fn test_casei_literal() {
        do_test("(?i:fOo)", 8, 8, 64);
    }

    #[test]
    fn test_alternation() {
        do_test("foo|bar|baz", 3, 3, 16);
        do_test_bytes("foo|bar|baz", 3, 3, 16);
    }

    #[test]
    fn test_repetition() {
        do_test("a{0,8}", 9, 9, 64);
        do_test_bytes("a{0,8}", 9, 9, 64);
    }

    #[test]
    fn test_question() {
        do_test("a?", 2, 2, 16);
        do_test_bytes("a?", 2, 2, 16);
    }

    #[test]
    fn test_star() {
        do_test("a*", 33, 33, 256);
        do_test_bytes("a*", 33, 33, 256);
    }

    #[test]
    fn test_plus() {
        do_test("a+", 32, 32, 256);
        do_test_bytes("a+", 32, 32, 256);
    }

    #[test]
    fn test_n_to_range() {
        do_test("a{4,}", 4, 4, 64);
        do_test_bytes("a{4,}", 4, 4, 64);
    }

    #[test]
    fn test_concatenation() {
        do_test("(foo|bar)(xyzzy|plugh)", 4, 4, 32);
        do_test_bytes("(foo|bar)(xyzzy|plugh)", 4, 4, 32);
    }

    #[test]
    fn test_ascii_class() {
        do_test("[[:digit:]]", 10, 10, 256);
    }

    #[test]
    fn test_unicode_class() {
        do_test("\\p{Greek}", 24, 512, 256);
    }

    #[test]
    fn test_dot() {
        do_test(".", 200, 65536, 256);
    }

    #[test]
    fn test_dot_s() {
        do_test("(?s).", 200, 65536, 256);
        do_test_bytes("(?s-u).", 256, 256, 2048);
    }

    #[test]
    fn test_backslash_d_plus() {
        do_test("\\d+", 1, 65536, 256);
    }

    #[test]
    fn test_non_utf8_byte_strings() {
        do_test_bytes(r"(?-u)[\xC0-\xFF]\x20", 64, 64, 512);
        do_test_bytes(r"(?-u)\x20[\x80-\xBF]", 64, 64, 512);
        do_test_bytes(r#"(?x-u)
  \xed (( ( \xa0\x80 | \xad\xbf | \xae\x80 | \xaf\xbf )
          ( \xed ( \xb0\x80 | \xbf\xbf ) )? )
        | \xb0\x80 | \xbe\x80 | \xbf\xbf )"#, 15, 15, 120);
    }

    fn assert_send_and_sync<T: Send + Sync>(_: T) {}

    #[test]
    fn regex_strategy_is_send_and_sync() {
        assert_send_and_sync(string_regex(".").unwrap());
    }

    macro_rules! consistent {
        ($name:ident, $value:expr) => {
            #[test]
            fn $name() {
                test_generates_matching_strings($value);
            }
        };
    }

    fn test_generates_matching_strings(pattern: &str) {
        use std::time;

        let mut runner = TestRunner::default();
        let start = time::Instant::now();

        // If we don't support this regex, just move on quietly
        if let Ok(strategy) = string_regex(pattern) {
            let rx = Regex::new(pattern).unwrap();

            for _ in 0..1000 {
                let mut val = strategy.new_tree(&mut runner).unwrap();
                // No more than 1000 simplify steps to keep test time down
                for _ in 0..1000 {
                    let s = val.current();
                    assert!(
                        rx.is_match(&s),
                        "Produced string {:?}, which does not match {:?}",
                        s,
                        pattern
                    );

                    if !val.simplify() {
                        break;
                    }
                }

                // Quietly stop testing if we've run for >10 s
                if start.elapsed().as_secs() > 10 {
                    break;
                }
            }
        }
    }

    include!("regex-contrib/crates_regex.rs");
}