to-regex-range 0.1.0

//! # to-regex-range — a regex that matches an integer range
//!
//! Generate a compact regular-expression source string matching every integer in a
//! range: `(1, 99)` becomes `[1-9]|[1-9][0-9]`. A faithful Rust port of the
//! [`to-regex-range`](https://www.npmjs.com/package/to-regex-range) npm package (a
//! micromatch building block). Zero dependencies and `#![no_std]`.
//!
//! ```
//! use to_regex_range::{to_regex_range, to_regex_range_with_options, Options};
//!
//! assert_eq!(to_regex_range(1, 5), "[1-5]");
//! assert_eq!(to_regex_range(1, 99), "(?:[1-9]|[1-9][0-9])");
//! assert_eq!(to_regex_range(-10, -1), "(?:-[1-9]|-10)");
//!
//! let opts = Options::default().shorthand(true);
//! assert_eq!(to_regex_range_with_options(1, 99, &opts), "(?:[1-9]|[1-9]\\d)");
//! ```
//!
//! The result is a regex *source* (no delimiters); wrap it in your regex engine of
//! choice. Operates on integer ranges; zero-padded ranges (`001..100`) are out of
//! scope.

#![no_std]
#![doc(html_root_url = "https://docs.rs/to-regex-range/0.1.0")]

extern crate alloc;

use alloc::collections::BTreeSet;
use alloc::format;
use alloc::string::{String, ToString};
use alloc::vec;
use alloc::vec::Vec;

// Compile-test the README's examples as part of `cargo test`.
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct ReadmeDoctests;

/// Options controlling the generated regex. Construct with [`Options::default`] and
/// the builder methods.
///
/// ```
/// use to_regex_range::Options;
/// let opts = Options::default().capture(true).shorthand(true);
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Options {
    /// Wrap the result in a capture group `( … )` instead of `(?: … )`.
    pub capture: bool,
    /// Use `\d` instead of `[0-9]`.
    pub shorthand: bool,
    /// Wrap a multi-alternative result in `(?: … )` (the default).
    pub wrap: bool,
}

impl Default for Options {
    fn default() -> Self {
        Self {
            capture: false,
            shorthand: false,
            wrap: true,
        }
    }
}

impl Options {
    /// See [`Options::capture`].
    #[must_use]
    pub fn capture(mut self, value: bool) -> Self {
        self.capture = value;
        self
    }
    /// See [`Options::shorthand`].
    #[must_use]
    pub fn shorthand(mut self, value: bool) -> Self {
        self.shorthand = value;
        self
    }
    /// See [`Options::wrap`].
    #[must_use]
    pub fn wrap(mut self, value: bool) -> Self {
        self.wrap = value;
        self
    }
}

/// Generate a regex source matching every integer from `min` to `max` (inclusive),
/// using the default [`Options`].
///
/// ```
/// assert_eq!(to_regex_range::to_regex_range(1, 10), "(?:[1-9]|10)");
/// ```
#[must_use]
pub fn to_regex_range(min: i64, max: i64) -> String {
    to_regex_range_with_options(min, max, &Options::default())
}

/// Generate a regex source matching every integer from `min` to `max` (inclusive).
#[must_use]
pub fn to_regex_range_with_options(min: i64, max: i64, options: &Options) -> String {
    if min == max {
        return min.to_string();
    }

    let a = min.min(max);
    let b = min.max(max);

    if a.abs_diff(b) == 1 {
        let result = format!("{min}|{max}");
        if options.capture {
            return format!("({result})");
        }
        if !options.wrap {
            return result;
        }
        return format!("(?:{result})");
    }

    let mut a = a;
    let mut negatives: Vec<Token> = Vec::new();
    let mut positives: Vec<Token> = Vec::new();

    if a < 0 {
        // `saturating_abs` keeps `i64::MIN` from overflowing; ranges that extreme are
        // pathological for a regex and may lose the single most-negative integer.
        let new_min = if b < 0 { b.saturating_abs() } else { 1 };
        negatives = split_to_patterns(new_min, a.saturating_abs(), *options);
        a = 0;
    }

    if b >= 0 {
        positives = split_to_patterns(a, b, *options);
    }

    let mut result = collate_patterns(&negatives, &positives);

    if options.capture {
        result = format!("({result})");
    } else if options.wrap && (positives.len() + negatives.len()) > 1 {
        result = format!("(?:{result})");
    }

    result
}

struct Token {
    pattern: String,
    count: Vec<i64>,
    string: String,
}

fn collate_patterns(neg: &[Token], pos: &[Token]) -> String {
    let mut subpatterns = filter_patterns(neg, pos, "-", false);
    subpatterns.extend(filter_patterns(neg, pos, "-?", true));
    subpatterns.extend(filter_patterns(pos, neg, "", false));
    subpatterns.join("|")
}

fn filter_patterns(
    arr: &[Token],
    comparison: &[Token],
    prefix: &str,
    intersection: bool,
) -> Vec<String> {
    let mut result = Vec::new();
    for ele in arr {
        let present = comparison.iter().any(|e| e.string == ele.string);
        if intersection == present {
            result.push(format!("{prefix}{}", ele.string));
        }
    }
    result
}

#[allow(clippy::cast_possible_truncation)] // each inserted stop is bounded by `max`
fn split_to_ranges(min: i64, max: i64) -> Vec<i64> {
    let (min128, max128) = (i128::from(min), i128::from(max));
    let mut stops: BTreeSet<i64> = BTreeSet::new();
    stops.insert(max);

    // Compute the nine-boundary stops in i128 so an all-nines value can exceed `max`
    // (and stop the loop) even when `max == i64::MAX`.
    let mut nines = 1;
    let mut stop = count_nines(min, nines);
    while min128 <= stop && stop <= max128 {
        stops.insert(stop as i64);
        nines += 1;
        stop = count_nines(min, nines);
    }

    let mut zeros = 1;
    let mut stop = count_zeros(max.saturating_add(1), zeros) - 1;
    while min < stop && stop <= max {
        stops.insert(stop);
        zeros += 1;
        stop = count_zeros(max.saturating_add(1), zeros) - 1;
    }

    stops.into_iter().collect()
}

fn split_to_patterns(min: i64, max: i64, options: Options) -> Vec<Token> {
    let ranges = split_to_ranges(min, max);
    let mut tokens: Vec<Token> = Vec::new();
    let mut start = min;
    let mut prev: Option<usize> = None;

    for &stop in &ranges {
        let obj = range_to_pattern(start, stop, options);

        if let Some(pi) = prev {
            if tokens[pi].pattern == obj.pattern {
                if tokens[pi].count.len() > 1 {
                    tokens[pi].count.pop();
                }
                tokens[pi].count.push(obj.count[0]);
                let quant = to_quantifier(&tokens[pi].count);
                tokens[pi].string = format!("{}{quant}", tokens[pi].pattern);
                start = stop.saturating_add(1);
                continue;
            }
        }

        let quant = to_quantifier(&obj.count);
        let string = format!("{}{quant}", obj.pattern);
        tokens.push(Token {
            pattern: obj.pattern,
            count: obj.count,
            string,
        });
        start = stop.saturating_add(1);
        prev = Some(tokens.len() - 1);
    }

    tokens
}

struct RangePattern {
    pattern: String,
    count: Vec<i64>,
}

fn range_to_pattern(start: i64, stop: i64, options: Options) -> RangePattern {
    if start == stop {
        return RangePattern {
            pattern: start.to_string(),
            count: vec![0],
        };
    }

    let s = start.to_string();
    let t = stop.to_string();
    let mut pattern = String::new();
    let mut count = 0;

    for (sd, td) in s.chars().zip(t.chars()) {
        if sd == td {
            pattern.push(sd);
        } else if sd != '0' || td != '9' {
            pattern.push_str(&to_character_class(sd, td));
        } else {
            count += 1;
        }
    }

    if count > 0 {
        pattern.push_str(if options.shorthand { "\\d" } else { "[0-9]" });
    }

    RangePattern {
        pattern,
        count: vec![count],
    }
}

fn to_quantifier(digits: &[i64]) -> String {
    let start = digits.first().copied().unwrap_or(0);
    let stop = digits.get(1).copied();
    let stop_truthy = stop.is_some_and(|s| s != 0);
    if stop_truthy {
        format!("{{{start},{}}}", stop.unwrap())
    } else if start > 1 {
        format!("{{{start}}}")
    } else {
        String::new()
    }
}

fn to_character_class(a: char, b: char) -> String {
    let dash = if (b as i64 - a as i64) == 1 { "" } else { "-" };
    format!("[{a}{dash}{b}]")
}

/// `Number(String(min).slice(0, -len) + '9'.repeat(len))`, in `i128` so all-nines
/// values that exceed `i64::MAX` can still terminate the loop in `split_to_ranges`.
fn count_nines(min: i64, len: usize) -> i128 {
    let s = min.to_string();
    let keep = s.len().saturating_sub(len);
    let mut out = String::from(&s[..keep]);
    for _ in 0..len {
        out.push('9');
    }
    out.parse::<i128>().unwrap_or(i128::MAX)
}

/// `integer - (integer % 10^zeros)`.
#[allow(clippy::cast_possible_truncation)] // result is bounded by `integer` (an i64)
fn count_zeros(integer: i64, zeros: u32) -> i64 {
    let pow = 10i128.pow(zeros);
    let i = i128::from(integer);
    (i - (i % pow)) as i64
}