#!/usr/bin/env python3
"""redos_prescan.py — deterministic regex-denial-of-service pre-scan.

ARION service artifact. Scans source files for the signatures of
catastrophic-backtracking regular expressions — nested quantifiers
((x+)+ / (x*)*), quantified groups whose alternation branches can
match the same string ((\\w|\\d)+ / (foo|f)+), adjacent unbounded
repeats whose character classes overlap (\\w+\\w+ / .*.*), regexes
built from request or other non-literal input (new RegExp(req…),
re.compile(var), preg_match($pat)), and files where a flagged
pattern is applied to request-derived data — line-wise, fully
offline, no inference.

Findings (base severity):
  REDOS-NESTED-QUANT       HIGH    a quantified group whose body
                                   already contains a quantified
                                   atom — (a+)+, (x*)*, (\\d+){2,} —
                                   the textbook exponential-blowup
                                   shape
  REDOS-OVERLAP-ALT        HIGH    a repeating group whose top-level
                                   alternation branches can match
                                   the same text — identical or
                                   superset first-atoms (\\w|\\d),
                                   literal prefix (foo|foobar|f),
                                   empty-nullable branch (a|) —
                                   exponential ambiguity; MEDIUM
                                   when the overlap only holds
                                   through a negated class
  REDOS-ADJACENT-REPEAT    MEDIUM  two consecutive atoms that are
                                   both unbounded-repeating (*, +,
                                   {n,}, {n,m} m>=4) whose character
                                   classes intersect — \\w+\\w+,
                                   .*.*, a*a* — quadratic
                                   backtracking
  REDOS-USER-PATTERN       MEDIUM  a regex constructed from a
                                   non-literal — new RegExp(x) /
                                   RegExp(`…${x}…`) / re.compile(x) /
                                   preg_match($p…) / Pattern.compile
                                   (x) / regexp.Compile(x) /
                                   Regex::new(x) — pattern injection
                                   plus unknown complexity; HIGH
                                   when the source expression is
                                   request-derived (req./request./
                                   $_GET/$_POST/argv/getParameter…);
                                   LOW when an escape call
                                   (escapeRegExp/re.escape/
                                   preg_quote/Regex.Escape/
                                   QuoteMeta/Pattern.quote) guards
                                   the interpolation
  REDOS-INPUT-APPLIED      MEDIUM  file-level advisory: the file
                                   contains a flagged dangerous
                                   pattern AND a regex application
                                   (test/match/search/replace/
                                   fullmatch/preg_match/matches)
                                   against request-derived input —
                                   the blowup is reachable

Context rules:
  * comment lines and block-comment bodies are stripped first
  * import/require lines never flag
  * test/spec/fixture paths downgrade one tier
  * JS regex literals are only read in regex position — a `/` must
    follow ([{=,:;!&|?^~ return => case or start-of-line, and the
    body must close with /flags; division stays silent
  * 'dangerous' quantifier = * + {n,} or {n,m} with m>=4 — bounded
    {2}/{2,3} repeats and '?' optionals do not count
  * char-class overlap is decided by real set algebra — literal
    chars, \\w \\d \\s . and bracket classes with ranges/negation;
    \d+\s+\w+ and .*literal are safe shapes and stay silent
  * lookaround groups (?= ?! ?<= ?<!) are analyzed for dangerous
    internals but do not take part in adjacency (zero-width)

Scope: deterministic pre-scan for human review — flags regex
constructions that can be driven into exponential/quadratic
backtracking or that are built from input; no proof a given input
is reachable or that the runtime lacks a match timeout — clean
output != ReDoS-safe.

  redos_prescan.py <file-or-dir> [--json]
  redos_prescan.py --selftest
Stdlib only. Exit 0 = no HIGH/MEDIUM findings, 1 = findings, 2 = usage.
"""
import json
import os
import re
import sys

SEV_ORDER = {"HIGH": 0, "MEDIUM": 1, "LOW": 2, "INFO": 3}

TARGET_EXT = (
    ".py", ".js", ".jsx", ".ts", ".tsx", ".mjs", ".cjs",
    ".php", ".rb", ".go", ".java", ".kt", ".cs", ".groovy",
    ".rs", ".scala", ".pl", ".pm",
)

SKIP_DIRS = {
    "node_modules", ".git", "vendor", "dist", "build", "target",
    "__pycache__", ".venv", "venv", "coverage", ".next", "out",
}

IMPORT_LINE = re.compile(
    r"^\s*(?:from\s+[\w.]+\s+import\b|import\s+[\w.{*]|"
    r"(?:const|let|var)\s+[\w${},\s]*=\s*require\s*\(|"
    r"\buse\s+[\w:]+|require\s*\(['\"][\w./-]+['\"]\s*\)?\s*;?\s*$|"
    r"#include|package\s+[\w.]+;?\s*$|using\s+[\w.]+;)")

TEST_PATH = re.compile(
    r"(^|/)(test|tests|spec|specs|fixtures?|mocks?|__tests__|__mocks__|"
    r"e2e|cypress|playwright)(/|$)|(_test|_spec|\.test|\.spec)\.",
    re.I)

# --- regex extraction ----------------------------------------------------
# call sites whose first argument is a pattern
PATTERN_CALL = re.compile(
    r"(?:re|regex)\s*\.\s*(?:compile|search|match|fullmatch|split|"
    r"sub|subn|findall|finditer)|"
    r"Pattern\s*\.\s*compile|"
    r"new\s+RegExp|(?<![\w.])RegExp\s*\(|"
    r"preg_(?:match|match_all|replace|split|grep)|"
    r"regexp\s*\.\s*(?:MustCompile|Compile)|"
    r"Regex\s*::\s*new|new\s+Regex\s*\(|"
    r"(?<![\w.])(?:match|matches|matchAll|search|replace|replaceAll|"
    r"split|test)\s*\(|"
    r"\.matches\s*\(|"
    r"Regexp\s*\.\s*(?:new|compile)|"
    r"=~")

QUOTED = re.compile(
    r"(?P<prefix>[rRuUbBfF]{0,3})"
    r"(?P<q>['\"`])(?P<body>(?:\\.|(?!\2).)*?)(?P=q)")

# JS regex literal in regex position — '/' after an opener/operator
JS_LIT_CTX = re.compile(
    r"(?:^|[({[=,:;!&|?^~*%<>]|\breturn\b|\bcase\b|\btypeof\b|"
    r"\bdelete\b|\bvoid\b|\bin\b|\bof\b|=>|\.\.\.)\s*")
JS_LIT = re.compile(r"/((?:\\.|\[(?:\\.|[^\]])*\]|[^/\\[\]])+)"
                    r"/([a-z]*)")

# variables whose literal we should still analyze (pattern-ish names)
PAT_VAR = re.compile(
    r"(?:^|\b)(?:[\w$]*(?:regex|regexp|pattern|_re\b|re_|_rx\b|rx_|"
    r"matcher|validator)\w*|[A-Z_]*RE\b|[A-Z_]*_RE\b|RX\b)\s*"
    r"(?:=|:=)\s*(?P<lit>[rRuUbBfF]{0,3}['\"`])", re.I)

# a bare quoted literal that is itself regex-shaped — no spaces and
# at least one meta char; 'result: (a+)+ of them' stays silent
REGEX_SHAPED = re.compile(r"^[^^\s]*[()\[\]{}|^$*+?\\][^\s]*$")

# RE2-class engines (Go regexp, Rust regex) run in linear time —
# nested-quant/overlap/adjacent shapes are not exploitable there
BACKTRACK_SAFE_EXT = {".go", ".rs"}

REQ_ISH = re.compile(
    r"\breq(?:uest)?\s*(?:\.|\[)|\brequest\b|params\.|query\.|"
    r"body\.|\$_GET|\$_POST|\$_REQUEST|\$_COOKIE|"
    r"argv|\bargs\.|stdin|getParameter|getQueryString|URLSearchParams|"
    r"location\.|window\.|process\.env|os\.environ|"
    r"getenv|input\s*\(|readline|fmt\.Scan|os\.Args|"
    r"Request\.|HttpRequest|r\.URL|r\.Form|ctx\.|c\.Query|"
    r"\buserInput\b|\binput_\b", re.I)

ESCAPE_MARK = re.compile(
    r"escapeRegExp|escape_?regex|re\.escape|preg_quote|"
    r"Regex\.Escape|regexp\.QuoteMeta|QuoteMeta|Pattern\.quote|"
    r"quotemeta|quoteMeta|escapeStringRegexp|mkregex_safe", re.I)

APPLY_CALL = re.compile(
    r"\.test\s*\(|\.match(?:es|All)?\s*\(|\.search\s*\(|"
    r"\.replace(?:All)?\s*\(|\.split\s*\(|"
    r"re\s*\.\s*(?:search|match|fullmatch|split|sub|subn|findall|"
    r"finditer)\s*\(|regex\s*\.\s*(?:search|match|sub)\s*\(|"
    r"preg_(?:match|match_all|replace|split|grep)\s*\(|"
    r"\.matches\s*\(|Regexp\s*\.\s*match|"
    r"\.is_match\s*\(|\.find\s*\(|\.captures\s*\(|=~")


def _quant(q):
    """-> 'unbounded' | 'bounded' | 'exact' | 'optional' | None"""
    if not q:
        return None
    q = q.strip().rstrip("?")
    if q in ("*", "+"):
        return "unbounded"
    if q == "?":
        return "optional"
    m = re.fullmatch(r"\{(\d+)(?:,(\d*))?\}", q)
    if not m:
        return None
    lo, hi = int(m.group(1)), m.group(2)
    if "," not in q:
        return "exact"              # {n} fixed count
    if hi == "":
        return "unbounded"          # {n,}
    return "bounded" if int(hi) > lo else "exact"


def _dangerous_quant(q):
    """Unbounded repeat — the exponential driver."""
    return _quant(q) == "unbounded"


def _repeat_quant(q):
    """Unbounded OR bounded-range (m > n) — enables ambiguity."""
    return _quant(q) in ("unbounded", "bounded")


def _bounded_quant(q):
    return _quant(q) == "bounded"


# --- mini pattern parser ---------------------------------------------------
_ATOMS = {
    "w": set("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
             "0123456789_"),
    "d": set("0123456789"),
    "s": set(" \t\n\r\f\v"),
}
_FULL = _ATOMS["w"] | set("!\"#$%&'()*+,-./:;<=>?@[\\]^`{|}~ \t\n\r")
_ESC_LIT = {"n": "\n", "r": "\r", "t": "\t", "f": "\f", "v": "\v"}


def _class_set(text):
    """Approximate the symbol set of one char-class body 'a-z0-9'."""
    out = set()
    i = 0
    while i < len(text):
        c = text[i]
        if c == "\\" and i + 1 < len(text):
            nxt = text[i + 1]
            if nxt in _ATOMS:
                out |= _ATOMS[nxt]
            elif nxt in "dws":
                out |= _ATOMS[nxt]
            else:
                out.add(nxt)
            i += 2
            continue
        if i + 2 < len(text) and text[i + 1] == "-" and \
                text[i + 2] != "]":
            a, b = ord(c), ord(text[i + 2])
            if a <= b and b - a < 200:
                out |= {chr(x) for x in range(a, b + 1)}
            i += 3
            continue
        out.add(c)
        i += 1
    return out


def _atom_set(tok):
    """(negated?, set|None-for-all) for a parsed atom token."""
    kind, body = tok[0], tok[1]
    if kind == "dot":
        return (False, _FULL | {"\n"})      # JS '.' ~ all (close enough)
    if kind == "lit":
        return (False, {body})
    if kind == "esc":
        if body in _ATOMS:
            return (False, set(_ATOMS[body]))
        if body in ("W", "D", "S"):
            return (True, set(_ATOMS[body.lower()]))
        if body in _ESC_LIT:
            return (False, {_ESC_LIT[body]})
        return (False, {body})
    if kind == "class":
        neg = body.startswith("^")
        s = _class_set(body[1:] if neg else body)
        return (neg, s)
    return (False, set())                   # group/anchor: unknown


def _overlap(a, b):
    na, sa = _atom_set(a)
    nb, sb = _atom_set(b)
    if sa is None or sb is None:
        return True
    if not sa or not sb:
        return False
    if not na and not nb:
        return bool(sa & sb)
    if na and nb:
        return True                         # two negated classes overlap
    neg, pos = (sa, sb) if na else (sb, sa)
    return not pos <= neg                   # U-neg vs pos


def _is_prefix_branch(a, b):
    """atoms a is a literal prefix of atoms b (a shorter)."""
    if len(a) >= len(b):
        return False
    for ta, tb in zip(a, b):
        if ta != tb:
            return False
    return True


def _parse(pattern):
    """Yield (depth, groupnode) friendly token stream.

    Returns list of groups; each group = {'quant': q|None,
    'branches': [[atoms...]], 'inner_repeat': bool,
    'overlap': None|'definite'|'possible', 'start': int} where each
    atom = (kind, body, quant).
    """
    groups = []
    stack = []
    top = {"quant": None, "branches": [[]], "look": False}
    stack.append(top)
    i = 0
    n = len(pattern)
    while i < n:
        c = pattern[i]
        if c == "\\" and i + 1 < n:
            stack[-1]["branches"][-1].append(("esc", pattern[i + 1],
                                              None))
            i += 2
            continue
        if c == "[":
            j = i + 1
            if j < n and pattern[j] == "^":
                j += 1
            if j < n and pattern[j] == "]":
                j += 1
            while j < n and pattern[j] != "]":
                j += 2 if pattern[j] == "\\" else 1
            stack[-1]["branches"][-1].append(
                ("class", pattern[i + 1:j], None))
            i = j + 1
            continue
        if c == "(":
            look = pattern.startswith(("(?=", "(?!", "(?<=", "(?<!"),
                                      i)
            g = {"quant": None, "branches": [[]], "look": look,
                 "pos": i}
            stack[-1]["branches"][-1].append(("group", g, None))
            stack.append(g)
            i += 4 if pattern.startswith(("(?<=", "(?<!"), i) \
                else 3 if pattern.startswith("(?:", i) or look \
                else 2 if pattern.startswith("(?", i) else 1
            continue
        if c == ")":
            g = stack.pop()
            if not stack:
                stack.append({"quant": None, "branches": [[]],
                              "look": False})
            i += 1
            m = re.match(r"[*+?]|\{\d+(?:,\d*)?\}\??", pattern[i:])
            if m:
                g["quant"] = m.group(0)
                i += len(m.group(0))
            groups.append(g)
            continue
        if c == "|":
            stack[-1]["branches"].append([])
            i += 1
            continue
        if c in "*+?":
            br = stack[-1]["branches"][-1]
            if br:
                a = br[-1]
                br[-1] = (a[0], a[1], c)
            i += 1
            if i < n and pattern[i] == "?":     # lazy suffix *? +?
                i += 1
            continue
        if c == "{":
            m = re.match(r"\{\d+(?:,\d*)?\}\??", pattern[i:])
            if m:
                br = stack[-1]["branches"][-1]
                if br:
                    a = br[-1]
                    br[-1] = (a[0], a[1], m.group(0))
                i += len(m.group(0))
            else:
                i += 1
            continue
        if c == ".":
            stack[-1]["branches"][-1].append(("dot", ".", None))
            i += 1
            continue
        if c in "^$":
            stack[-1]["branches"][-1].append(("anchor", c, None))
            i += 1
            continue
        stack[-1]["branches"][-1].append(("lit", c, None))
        i += 1
    groups.append(stack[0] if stack else top)
    return groups


def _optional_or_zero(a):
    if a[0] == "anchor":
        return True
    if a[0] == "group" and a[1].get("look"):
        return True
    q = (a[2] or "").strip()
    return q in ("?", "*") or q.startswith("{0") or \
        re.fullmatch(r"\{0,\d+\}\??", q) is not None


def _atoms(branch):
    return [a for a in branch if a[0] != "anchor"]


def _branch_overlap_first(a, firsts):
    return a[0] in ("lit", "esc", "class", "dot") and any(
        f is not None and _overlap(a, f) for f in firsts)


def analyze_pattern(pattern):
    """Return list of (code, severity, detail) for one regex body."""
    out = []
    try:
        groups = _parse(pattern)
    except Exception:
        return out
    for g in groups:
        outer_danger = _dangerous_quant(g.get("quant"))
        outer_bounded = _bounded_quant(g.get("quant"))
        branches = g["branches"]
        # nested quantifier: a repeating group is only catastrophic
        # when the iteration boundary is ambiguous — a repeating
        # atom whose class overlaps the next consumable atom, or a
        # branch that can end on a repeat whose chars could also
        # start the next iteration. (a+)+ and ([a-z]+\s*)+ flag;
        # (?:-[a-z0-9]+)* and (?:\n[ \t]*)+ are forced-boundary and
        # stay silent.
        if (outer_danger or outer_bounded) and not g.get("look"):
            firsts = []
            for br in branches:
                aa = _atoms(br)
                firsts.append(aa[0] if aa else None)
            hit = False
            for br in branches:
                atoms = _atoms(br)
                for idx, a in enumerate(atoms):
                    if a[0] == "group" and \
                            _repeat_quant(a[1].get("quant")):
                        hit = True          # nested repeating group
                        break
                    if not _repeat_quant(a[2]):
                        continue
                    nxt = idx + 1
                    if nxt < len(atoms) and \
                            atoms[nxt][0] in ("lit", "esc", "class",
                                              "dot", "group") and \
                            _overlap(a, atoms[nxt]):
                        hit = True          # intra-branch split
                        break
                    if all(_optional_or_zero(x)
                           for x in atoms[idx + 1:]) and \
                            _branch_overlap_first(a, firsts):
                        hit = True          # ambiguous iteration end
                        break
                if hit:
                    break
            if hit:
                sev = "MEDIUM" if (outer_bounded and
                                   not outer_danger) else "HIGH"
                out.append(("REDOS-NESTED-QUANT", sev,
                            "quantified group wraps a quantified atom "
                            "with an ambiguous iteration boundary — "
                            "exponential backtracking"))
        # overlapping alternation inside a repeating group
        if (outer_danger or outer_bounded) and \
                len(branches) > 1 and not g.get("look"):
            sev = None
            firsts = []
            for br in branches:
                atoms = [a for a in br if a[0] != "anchor"]
                firsts.append(atoms)
            for x in range(len(firsts)):
                for y in range(x + 1, len(firsts)):
                    ba, bb = firsts[x], firsts[y]
                    if not ba or not bb:
                        sev = sev or "MEDIUM"     # empty-nullable branch
                        continue
                    # literal-prefix branch: only ambiguous when the
                    # leftover can itself start a new iteration —
                    # (a|aa)+ yes, (foo|foobar)+ no
                    pref = None
                    if _is_prefix_branch(ba, bb):
                        pref = bb[len(ba):]
                    elif _is_prefix_branch(bb, ba):
                        pref = ba[len(bb):]
                    if pref is not None:
                        if pref and any(
                                _overlap(pref[0], f[0])
                                for f in firsts if f):
                            sev = "HIGH"
                        break
                    fa, fb = ba[0], bb[0]
                    if fa[0] in ("lit", "esc", "class", "dot") and \
                            fb[0] in ("lit", "esc", "class", "dot"):
                        if _overlap(fa, fb):
                            na = _atom_set(fa)[0]
                            nb = _atom_set(fb)[0]
                            sev = "MEDIUM" if (na or nb) else "HIGH"
                            if sev == "HIGH":
                                break
                if sev == "HIGH":
                    break
            if sev:
                if outer_bounded and not outer_danger:
                    sev = "MEDIUM"
                out.append(("REDOS-OVERLAP-ALT", sev,
                            "alternation branches in a repeating "
                            "group can match the same text — "
                            "exponential ambiguity"))
    # adjacent unbounded repeats with overlapping classes — a lone
    # pair only enumerates O(n) split points (linear); the blowup is
    # real when the pair sits inside a repeating group or chains 3+
    pair_count = 0
    pair_in_group = False
    for g in groups:
        for br in g["branches"]:
            prev = None
            for a in br:
                if a[0] == "anchor":
                    continue
                cur = a
                if prev is not None and \
                        _repeat_quant(prev[2]) and \
                        _repeat_quant(cur[2]) and \
                        prev[0] in ("lit", "esc", "class", "dot") and \
                        cur[0] in ("lit", "esc", "class", "dot") and \
                        _overlap(prev, cur):
                    pair_count += 1
                    if g is not groups[-1] and \
                            _repeat_quant(g.get("quant")):
                        pair_in_group = True
                prev = cur
    if pair_count:
        if pair_in_group or pair_count >= 2:
            out.append(("REDOS-ADJACENT-REPEAT", "MEDIUM",
                        "chained/in-group unbounded repeats with "
                        "overlapping character classes — polynomial "
                        "backtracking"))
        else:
            out.append(("REDOS-ADJACENT-REPEAT", "LOW",
                        "adjacent unbounded repeats with overlapping "
                        "character classes — review; dangerous when "
                        "chained or nested"))
    return out


# --- regex literal / call-site extraction -----------------------------------
def _extract_regexes(code, i, codes):
    """Yield pattern-body strings found on a code line."""
    # 1) JS/Ruby literal  /.../flags
    for m in JS_LIT.finditer(code):
        ctx = code[:m.start()].rstrip()
        if ctx and JS_LIT_CTX.search(ctx[-12:] + " "):
            yield m.group(1)
        elif not ctx:
            yield m.group(1)
    # 2) pattern-call with quoted first arg — look through a short
    # window so `re.compile(\n    r'...'` still yields its literal
    win = "\n".join(codes[i:i + 5]) if codes else code
    for m in PATTERN_CALL.finditer(win):
        if m.start() > len(code):
            break                       # only calls starting this line
        tail = win[m.end():m.end() + 400]
        qm = QUOTED.match(tail.lstrip(" \t\n("))
        if qm:
            yield qm.group("body")
    # 3) pattern-ish variable assigned a literal
    vm = PAT_VAR.search(code)
    if vm:
        qm = QUOTED.match(code[vm.end("lit") - 1:])
        if qm:
            yield qm.group("body")
    # 4) any quoted literal that is itself regex-shaped
    for qm in QUOTED.finditer(code):
        body = qm.group("body")
        if "${" in body:
            continue
        if len(body) >= 4 and REGEX_SHAPED.match(body):
            yield body


CONST_ASSIGN = re.compile(
    r"(?:^|\b(?:self|cls)\.|(?:const|let|var)\s+|static\s+|readonly\s+)"
    r"\s*([A-Za-z_]\w*)\s*=\s*[rRuUbBfF]{0,3}['\"`]")


def _user_pattern(code, win, consts):
    """Does the line build a regex from a non-literal? -> (reqish, esc)

    `code` is the current line; `win` is code + next few lines so a
    literal/template arg on the following line is still seen. Only
    calls that START on this line are reported (dedup by line)."""
    hits = []
    for m in re.finditer(
            r"new\s+RegExp\s*\(|(?<![\w.])RegExp\s*\(|"
            r"re\s*\.\s*compile\s*\(|regex\s*\.\s*compile\s*\(|"
            r"Pattern\s*\.\s*compile\s*\(|new\s+Regex\s*\(|"
            r"regexp\s*\.\s*(?:MustCompile|Compile)\s*\(|"
            r"Regex\s*::\s*new\s*\(|Regexp\s*\.\s*(?:new|compile)\s*\(|"
            r"preg_(?:match|match_all|replace|split|grep)\s*\(",
            QUOTED.sub(
                lambda m: m.group("q") + "x" * len(m.group("body"))
                + m.group("q"), win)):
        if m.start() > len(code):
            break
        arg = win[m.end():m.end() + 200]
        # X.source re-wraps a literal regex — constant-derived, safe
        if re.match(r"\s*\(*\s*[\w.$]+\.source\b", arg):
            continue
        lit = QUOTED.match(arg.lstrip(" \t\n("))
        if lit:
            body = lit.group("body")
            interp = ("${" in body) or \
                     ("f" in lit.group("prefix").lower()
                      and "{" in body)
            tail = arg[arg.find(lit.group(0)) + len(lit.group(0)):]
            if not interp and not re.search(
                    r"^\s*(\+|%|\.concat|\.format\s*\()", tail):
                continue        # pure literal — analyzed as a pattern
        else:
            # constant-folded: NAME assigned a quoted literal in this
            # file; NAME.format(...) with only literal args is also
            # constant — the literal is analyzed at its own site
            na = arg.lstrip(" \t\n")
            nm = re.match(r"\s*\(*\s*(?:self\.|cls\.)?([A-Za-z_]\w*)\b"
                          r"(\.format\s*\(|\.encode\s*\()?", na)
            if nm and nm.group(1) in consts:
                if not nm.group(2):
                    continue            # bare constant name — silent
                # inside the .format(/.encode( parens: a bare
                # identifier that is not a kwarg name = dynamic arg
                inside = na[nm.end():]
                depth, cut = 1, len(inside)
                for k, ch in enumerate(inside):
                    depth += ch == "("
                    depth -= ch == ")"
                    if depth == 0:
                        cut = k
                        break
                inside = QUOTED.sub(" ", inside[:cut])
                if not re.search(r"[A-Za-z_$][\w.]*(?![\w=])",
                                 inside):
                    continue            # all args literal — silent
        hits.append((bool(REQ_ISH.search(arg)),
                     bool(ESCAPE_MARK.search(code))))
    return hits


def _strip_line_comment(line, ext):
    s = line.strip()
    if not s:
        return ""
    if s.startswith("//") or s.startswith("<!--") or s.startswith("*"):
        return None
    if s.startswith("#") and ext in (".py", ".rb", ".sh", ".pl", ".pm"):
        return None
    for marker in ("//", "<!--"):
        i = s.find(marker)
        if i > 0 and s[i - 1] in " \t)]":
            s = s[:i]
            break
    return s


def _is_test_path(rel):
    return bool(TEST_PATH.search(rel.replace(os.sep, "/")))


def _ext_of(path):
    return os.path.splitext(path)[1].lower()


def scan_file(path, rel):
    ext = _ext_of(path)
    try:
        with open(path, "r", encoding="utf-8", errors="replace") as f:
            lines = f.readlines()
    except OSError:
        return []
    findings = []
    seen = set()
    in_block = False
    codes = []
    for raw in lines:
        line = raw.rstrip("\n")
        j = 0
        out = []
        while j < len(line):
            if in_block:
                k = line.find("*/", j)
                if k < 0:
                    j = len(line)
                    continue
                j = k + 2
                in_block = False
                continue
            ko = line.find("/*", j)
            if ko < 0:
                out.append(line[j:])
                break
            out.append(line[j:ko])
            j = ko
            kc = line.find("*/", j + 2)
            if kc >= 0:
                out.append(" ")
                j = kc + 2
            else:
                in_block = True
                j = len(line)
        code = "".join(out)
        code = _strip_line_comment(code, ext)
        codes.append(code or "")

    def add(cls, sev, i, note):
        if (cls, i + 1) in seen:
            return
        seen.add((cls, i + 1))
        if _is_test_path(rel):
            sev = "LOW"
        findings.append(Finding(cls, sev, rel, i + 1, lines[i], note))

    # names assigned a quoted literal anywhere in the file — constant
    # regex templates folded by name
    consts = set()
    for code in codes:
        cm = CONST_ASSIGN.search(code)
        if cm:
            consts.add(cm.group(1))

    file_dangerous = False
    for i, code in enumerate(codes):
        if not code.strip() or IMPORT_LINE.search(code):
            continue

        # --- regex construction from non-literals ---
        for reqish, escaped in _user_pattern(
                code, "\n".join(codes[i:i + 5]), consts):
            if escaped:
                sev = "LOW"
                note = "regex built from a non-literal — escape " \
                       "call present; verify it covers the whole " \
                       "interpolated piece"
            elif reqish:
                sev = "HIGH"
                note = "regex built from request-derived input — " \
                       "pattern injection plus unknown complexity"
            else:
                sev = "MEDIUM"
                note = "regex built from a non-literal — pattern " \
                       "injection plus unknown complexity"
            add("REDOS-USER-PATTERN", sev, i, note)

        # --- dangerous literal patterns (RE2 engines are immune) ---
        if ext not in BACKTRACK_SAFE_EXT:
            for pat in _extract_regexes(code, i, codes):
                if len(pat) < 4:
                    continue
                for cls, sev, note in analyze_pattern(pat):
                    file_dangerous = file_dangerous or sev in (
                        "HIGH", "MEDIUM")
                    add(cls, sev, i, note + " in /%s/"
                        % (pat[:60] + ("…" if len(pat) > 60 else "")))

    # --- file-level: dangerous pattern + apply on request input ---
    if file_dangerous:
        for i, code in enumerate(codes):
            if APPLY_CALL.search(code) and REQ_ISH.search(code):
                add("REDOS-INPUT-APPLIED", "MEDIUM", i,
                    "a flagged-dangerous pattern in this file is "
                    "applied to request-derived input — the blowup "
                    "is reachable")
                break
    return findings


class Finding:
    def __init__(self, code, sev, path, line_no, line, note):
        self.code = code
        self.sev = sev
        self.path = path
        self.line_no = line_no
        self.line = line.strip()[:200]
        self.note = note

    def as_dict(self):
        return {"code": self.code, "severity": self.sev,
                "file": self.path, "line": self.line_no,
                "text": self.line, "note": self.note}


def find_targets(root):
    if os.path.isfile(root):
        return [root]
    out = []
    for dirpath, dirs, files in os.walk(root):
        dirs[:] = [d for d in dirs if d not in SKIP_DIRS]
        for fn in files:
            if _ext_of(fn) in TARGET_EXT:
                out.append(os.path.join(dirpath, fn))
    return sorted(out)


def render(findings, targets):
    findings.sort(key=lambda f: (SEV_ORDER[f.sev], f.path, f.line_no))
    lines = ["redos_prescan report — %d file(s), %d finding(s)"
             % (len(targets), len(findings)), ""]
    for f in findings:
        lines.append("%-6s %-26s %s:%d  %s"
                     % (f.sev, f.code, f.path, f.line_no, f.note))
        lines.append("       | %s" % f.line)
    if not findings:
        lines.append("no HIGH/MEDIUM/LOW findings")
    lines.append("")
    lines.append("scope: deterministic pre-scan — flags regex shapes "
                 "that can be driven into catastrophic backtracking; "
                 "not an audit, clean != ReDoS-safe")
    return "\n".join(lines)


SELFTEST = [
    # --- REDOS-NESTED-QUANT (HIGH) ---
    ("a.js", "const re = /^(a+)+$/;\n", {"REDOS-NESTED-QUANT"}),
    ("a.js", "const re = /^(a*)*$/;\n", {"REDOS-NESTED-QUANT"}),
    ("a.py", "re.compile(r'^(\\w+)+$')\n", {"REDOS-NESTED-QUANT"}),
    ("a.py", "BAD = r'([a-z]+)*$'\n", {"REDOS-NESTED-QUANT"}),
    ("a.js", "const re = /^(x+)*(y)?$/;\n", {"REDOS-NESTED-QUANT"}),
    ("a.js", "const re = /^((a|b)+)+$/;\n", {"REDOS-NESTED-QUANT"}),
    ("a.js", "const re = /^([a-z]+\\s?)+$/;\n",
     {"REDOS-NESTED-QUANT"}),   # '?' inner is optional not repeat… no
    ("a.js", "const re = /^([a-z]+\\s*)+$/;\n", {"REDOS-NESTED-QUANT"}),
    ("a.php", "preg_match('/^(\\d+)+$/', $s);\n",
     {"REDOS-NESTED-QUANT"}),
    ("a.java", "Pattern.compile(\"^(a+)+$\");\n",
     {"REDOS-NESTED-QUANT"}),
    ("a.go", "regexp.MustCompile(`^(a+)+$`)\n", set()),  # RE2 is immune
    ("a.js", "const re = /^(ab|cd)+$/;\n", set()),
    ("a.js", "const re = /^(a|b)*$/;\n", set()),
    ("a.js", "const re = /^a{2} b{2}$/;\n", set()),
    ("a.js", "// const re = /^(a+)+$/;\n", set()),
    ("a.js", "/* const re = /^(a+)+$/; */\n", set()),
    # forced-boundary shapes are deterministic — not ReDoS
    ("a.js", "const re = /^[a-z0-9]+(?:-[a-z0-9]+)*$/;\n", set()),
    ("a.js", "const re = /(?:\\d+,)+/;\n", set()),
    ("a.js", "const re = /(?:\\n[ \\t]*)+$/;\n", set()),
    ("a.js", "const re = /^[A-Z][a-z]+(\\s+[A-Za-z&/]+){0,4}$/;\n",
     set()),   # iterations forced at \s boundaries — deterministic
    ("a.js", "const re = /^(\\w+){0,4}$/;\n",
     {"REDOS-NESTED-QUANT"}),   # bounded outer → MEDIUM
    ("a.js", "const re = /^a{3}b{3}$/;\n", set()),
    # --- REDOS-OVERLAP-ALT (HIGH) ---
    ("a.js", "const re = /^(\\w|\\d)+$/;\n", {"REDOS-OVERLAP-ALT"}),
    ("a.js", "const re = /^(foo|foobar|f)+$/;\n", set()),
    ("a.js", "const re = /^(a|a)+$/;\n", {"REDOS-OVERLAP-ALT"}),
    ("a.py", "re.compile(r'^(aa?|a)+$')\n", {"REDOS-OVERLAP-ALT"}),
    ("a.js", "const re = /^(.|x)*$/;\n", {"REDOS-OVERLAP-ALT"}),
    ("a.js", "const re = /^(jpg|png|gif)+$/;\n", set()),
    ("a.js", "const re = /^(cat|dog|bird)+$/;\n", set()),
    ("a.js", "const re = /^(ab|ba)+$/;\n", set()),
    ("a.js", "const re = /^([a-f]|x)+$/;\n", set()),
    ("a.js", "const re = /^(foo|foobar)+$/;\n", set()),
    ("a.js", "const re = /^(a|aa)+$/;\n", {"REDOS-OVERLAP-ALT"}),
    # --- REDOS-ADJACENT-REPEAT (MEDIUM) ---
    ("a.js", "const re = /^\\w+\\w+$/;\n", {"REDOS-ADJACENT-REPEAT"}),
    ("a.js", "const re = /.*.*id=./;\n", {"REDOS-ADJACENT-REPEAT"}),
    ("a.py", "re.compile(r'a*a*')\n", {"REDOS-ADJACENT-REPEAT"}),
    ("a.js", "const re = /^[a-z]+[0-9a-z]*$/;\n",
     {"REDOS-ADJACENT-REPEAT"}),
    ("a.js", "const re = /^\\d+\\s+\\w+$/;\n", set()),
    ("a.js", "const re = /^.*error.*$/;\n", set()),
    ("a.js", "const re = /^.*error$/;\n", set()),
    ("a.js", "const re = /^.*\\w+$/;\n", {"REDOS-ADJACENT-REPEAT"}),
    ("a.js", "const re = /\\w+\\d*/;\n", {"REDOS-ADJACENT-REPEAT"}),
    # --- REDOS-USER-PATTERN ---
    ("a.js", "const re = new RegExp(req.query.q);\n",
     {"REDOS-USER-PATTERN"}),
    ("a.js", "const re = new RegExp(name);\n",
     {"REDOS-USER-PATTERN"}),
    ("a.py", "pat = re.compile(pattern)\n", {"REDOS-USER-PATTERN"}),
    ("a.py", "pat = re.compile(request.args['q'])\n",
     {"REDOS-USER-PATTERN"}),
    ("a.php", "preg_match($pat, $s);\n", {"REDOS-USER-PATTERN"}),
    ("a.js", "const re = new RegExp(`^${escapeRegExp(q)}$`);\n",
     {"REDOS-USER-PATTERN"}),
    ("a.js", "const re = new RegExp('^a+$');\n", set()),
    ("a.py", "pat = re.compile(r'^a+$')\n", set()),
    ("a.py", "pat = re.compile(re.escape(user))\n",
     {"REDOS-USER-PATTERN"}),
    ("a.java", "Pattern.compile(cfg.get(\"rx\"));\n",
     {"REDOS-USER-PATTERN"}),
    ("a.go", "regexp.Compile(os.Args[1])\n", {"REDOS-USER-PATTERN"}),
    # --- REDOS-INPUT-APPLIED (file-level) ---
    ("a.js", "const re = /^(a+)+$/;\n"
             "app.get('/s', (req,res)=>{ ok = re.test(req.query.s) });\n",
     {"REDOS-NESTED-QUANT", "REDOS-INPUT-APPLIED"}),
    ("a.js", "const re = /^(a+)+$/;\nok = re.test(saved);\n",
     {"REDOS-NESTED-QUANT"}),
    # --- interplay ---
    ("test/a.js", "const re = /^(a+)+$/;\n", {"REDOS-NESTED-QUANT"}),
    ("a.js", "import re from 're';\n", set()),
    ("a.js", "const t = a / b / c;\n", set()),
    ("a.js", "x = y / 2; z = w / 3;\n", set()),
    ("a.js", "path.split('/').map(f)\n", set()),
    ("a.py", "s = 'result: (a+)+ of them'\n", set()),
    ("a.js", "const re = /^(a+)+$/; // documented evil\n",
     {"REDOS-NESTED-QUANT"}),
    ("a.rb", "EMAIL = /^(\\w+)+$/\n", {"REDOS-NESTED-QUANT"}),
    ("a.rs", "let r = Regex::new(r\"^(a+)+$\").unwrap();\n",
     set()),   # Rust regex crate is linear-time — immune
    ("a.rs", "let r = Regex::new(&pat).unwrap();\n",
     {"REDOS-USER-PATTERN"}),
]


def run_selftest():
    import tempfile
    fails = []
    for i, (name, src, expect) in enumerate(SELFTEST):
        with tempfile.TemporaryDirectory() as td:
            p = os.path.join(td, name)
            os.makedirs(os.path.dirname(p), exist_ok=True)
            open(p, "w").write(src)
            got = {f.code for f in scan_file(p, name)}
            missing = expect - got
            extra = got - expect
            if missing or extra:
                fails.append(("v%d %s" % (i, name),
                              "missing=%s extra=%s" % (missing, extra)))
    if fails:
        for f_ in fails:
            print("SELFTEST FAIL", f_)
        return 1
    print("SELFTEST PASS (%d vectors)" % len(SELFTEST))
    return 0


def main():
    args = [a for a in sys.argv[1:] if a != "--json"]
    want_json = "--json" in sys.argv
    if "--selftest" in sys.argv:
        return run_selftest()
    if not args:
        print(__doc__)
        return 2
    root = args[0]
    targets = find_targets(root)
    findings = []
    for p in targets:
        rel = os.path.relpath(p, root) if os.path.isdir(root) \
            else os.path.basename(p)
        findings += scan_file(p, rel)
    if want_json:
        print(json.dumps([f.as_dict() for f in findings], indent=1))
    else:
        print(render(findings, targets))
    return 1 if any(f.sev in ("HIGH", "MEDIUM") for f in findings) else 0


if __name__ == "__main__":
    sys.exit(main())