# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/beyond-what-complexity-and-linear-automaton-bounds-must-an-instance-constrain-regular-expression-matching-to-prevent-catastrophic-backtracking-denial-of-service.md
# Remnant Warrant:    https://corpusfetch.com/c/beyond-what-complexity-and-linear-automaton-bounds-must-an-instance-constrain-regular-expression-matching-to-prevent-catastrophic-backtracking-denial-of-service.warrant.json
# Markdown SHA-256:   f2fddccb0dee4d78dfd300e5ab84e49666d2c8aa3d58a3fb3f0dcff0a0ab6635
# Code AST SHA-256:   b883576578c0a54c49543c9ff86c621649ba3a49c2a0bc976c1a41ad4dae499a
# Verified Classes:   LinearAutomatonRegexGuard
# Defensive Guards:   4 fail-closed invariants (zero external deps)

import re
from typing import Sequence

# Detects classic nested-quantifier ReDoS anti-patterns such as (a+)+, (a*)+, (?:x+)*
_NESTED_QUANTIFIER_HAZARD_RE = re.compile(
    r"\([^)]*[+*][^)]*\)\s*[+*?]|\(\?:[^)]*[+*][^)]*\)\s*[+*?]"
)

# Unambiguous O(N) patterns: mandatory single separator between non-overlapping token classes
_SAFE_SLUG_RE = re.compile(r"^[a-z0-9]+(?:-[a-z0-9]+)*$")
_SAFE_DOTTED_IDENT_RE = re.compile(r"^[A-Za-z_][A-Za-z0-9_]*(?:\.[A-Za-z_][A-Za-z0-9_]*)*$")


def verify_regex_pattern_safety(pattern: str) -> re.Pattern[str]:
    '''
    Audits a regex pattern string for nested-quantifier backtracking hazards
    before compiling it.
    '''
    if _NESTED_QUANTIFIER_HAZARD_RE.search(pattern):
        raise ValueError(
            f"Rejected ReDoS-vulnerable regex containing nested quantifiers: {pattern!r}. "
            "Rewrite as an unambiguous flat separator pattern: ^token(?:sep+token)*$"
        )
    return re.compile(pattern)


def bounded_regex_match(
    compiled_re: re.Pattern[str],
    candidate: str,
    *,
    max_input_len: int = 256,
) -> re.Match[str] | None:
    '''
    Enforces a strict O(1) input length gate BEFORE invoking the regex engine
    so oversized payloads are rejected without entering NFA evaluation.
    '''
    if not isinstance(candidate, str):
        raise TypeError(f"Expected str input, got {type(candidate).__name__}")
    if len(candidate) > max_input_len:
        raise ValueError(
            f"Input length {len(candidate)} exceeds maximum allowed ceiling of {max_input_len} chars"
        )
    return compiled_re.match(candidate)


def validate_safe_slug(value: str, max_len: int = 64) -> str:
    '''
    Validates a hyphen-separated alphanumeric slug in guaranteed O(N) linear time.
    Contrast with vulnerable `^([a-z0-9]+-?)+\\$` which hangs on 'aaaaaaaaaa!'.
    '''
    if bounded_regex_match(_SAFE_SLUG_RE, value, max_input_len=max_len) is None:
        raise ValueError(f"Invalid slug format: {value!r}")
    return value


def safe_literal_or_prefix_filter(
    lines: Sequence[str],
    user_query: str,
    *,
    case_sensitive: bool = False,
) -> list[str]:
    '''
    Safely filters lines by a user-supplied search string in O(N) time without
    compiling untrusted user input as a regular expression.
    '''
    if not user_query:
        return list(lines)

    if case_sensitive:
        return [line for line in lines if user_query in line]

    needle = user_query.casefold()
    return [line for line in lines if needle in line.casefold()]


class LinearAutomatonRegexGuard:
    """Operational boundary reference implementation."""
    verify_regex_pattern_safety = staticmethod(verify_regex_pattern_safety)
    bounded_regex_match = staticmethod(bounded_regex_match)
    validate_safe_slug = staticmethod(validate_safe_slug)
    safe_literal_or_prefix_filter = staticmethod(safe_literal_or_prefix_filter)