import re

import pytest

from regexploit.ast.sequence import Sequence
from regexploit.ast.sre import SreOpParser
from regexploit.redos import find


def from_regex(pattern: str, flags: int = 0) -> Sequence:
    return SreOpParser().parse_sre(pattern, flags)


def find_redos(pattern: str, flags: int = 0):
    return find(from_regex(pattern, flags))


def test_no_repeats():
    assert len(find_redos(r"aaaaa[abc](\w[\wz]){1,7}X[^x]")) == 0


def test_simple_repeat1():
    (r,) = find_redos(r"abd\w*[def]+\w+[de]!")
    assert r.starriness == 3
    assert r.repeated_character == from_regex("[de]")
    assert r.example_prefix == "abd"
    assert r.killer is None


def test_simple_repeat2():
    rs = find_redos(r"\w*x0*\d*\.?\d\.?\d+4")
    assert len(rs)
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex("0")
    assert r.example_prefix == "x"
    assert r.killer is None


def test_simple_best_repeat():
    rs = find_redos(r"\d*0*\d*x?\dx?\d+4")
    assert len(rs) > 1
    a = rs[0]
    assert a.starriness == 4
    assert a.repeated_character == from_regex("0")
    assert a.example_prefix == ""
    assert a.killer is None
    assert rs[1].starriness == 3


def test_backtrack():
    rs = find_redos(r"[abc]+\w+[ab]+a")
    r = rs[0]
    assert r.starriness == 3
    assert len(r.redos_sequence) == 4
    assert r.killer == from_regex("[^a]")
    assert r.example() == "'b' * 3456"


def test_real_hbbtv():
    rs = find_redos(
        r"(HbbTV)/[0-9]+\.[0-9]+\.[0-9]+ \([^;]*; *(LG)E *; *([^;]*) *;[^;]*;[^;]*;\)"
    )
    r = rs[0]
    assert r.starriness == 3
    assert len(r.redos_sequence) == 4
    assert r.repeated_character == from_regex(" ")
    assert r.example_prefix.startswith("HbbTV/")
    assert r.example_prefix.endswith("(;LGE;")


def test_real_branching():
    rs = [
        redos
        for redos in find_redos(
            r"(HbbTV)/[0-9]+\.[0-9]+\.[0-9]+ \([^;]*; *(?:CUS:([^;]*)|([^;]+)) *; *([^;]*) *;.*;"
        )
        if redos.starriness >= 3
    ]
    assert all(r.starriness == 3 for r in rs)
    assert all(r.killer is None for r in rs)
    assert all(r.repeated_character == from_regex(" ") for r in rs)
    assert {r.example_prefix for r in rs} == {
        "HbbTV/0.0.0 (;CUS:;",
        "HbbTV/0.0.0 (;",
        "HbbTV/0.0.0 (;0;",
    }


def test_dollar():
    rs = find_redos(r"^a+(b*b*b*)$")
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"b")
    assert r.killer == from_regex(r"[^b]")


def test_real_cpython_cookielib():
    # We don't support the (?!) assertions, but can still find ReDoS
    LOOSE_HTTP_DATE_RE = r"""^
        (\d\d?)            # day
           (?:\s+|[-\/])
        (\w+)              # month
            (?:\s+|[-\/])
        (\d+)              # year
        (?:
              (?:\s+|:)    # separator before clock
           (\d\d?):(\d\d)  # hour:min
           (?::(\d\d))?    # optional seconds
        )?                 # optional clock
           \s*
        ([-+]?\d{2,4}|(?![APap][Mm]\b)[A-Za-z]+)? # timezone
           \s*
        (?:\(\w+\))?       # ASCII representation of timezone in parens.
           \s*$"""
    rs = find_redos(LOOSE_HTTP_DATE_RE, re.X)
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"\s")
    assert r.killer == from_regex(r"[^\s]")


def test_real_cpython_cve():
    rs = find_redos(r"(,*,)*(,+)[ \t]")
    r = rs[0]
    assert r.starriness == 12  # exponential


def test_real_ssri():
    rs = find_redos(r"^([A-Za-z0-9+/=]{4})(\?[\x21-\x7E]*)*$")
    r = rs[0]
    assert r.starriness > 10
    assert r.repeated_character == from_regex(r"\?")
    assert r.example_prefix == "0000"


def test_real_pdf():
    # \012 == \n == \x0a
    rs = find_redos(
        r"t[\011\012\015\040]*\<\<(.*?\>\>)[\011\012\015\040]*[\r\n]+[\011\012\015\040]*s"
    )
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"[\n\r]")
    assert r.example_prefix == "t<<>>"
    assert not r.killer


def test_real_markdown():
    # \s\S == .
    rs = find_redos(r"\(\s*(<)?([\s\S]*?)(?(2)>)(?:\s+'([\s\S]*?)')?\s*\)")
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"\s")
    assert r.example_prefix == "("
    assert not r.killer


def test_backtrack_repeated_char():
    # (' ' * 3456 + '\t') won't backtrack because of the .* after
    rs = find_redos(r"#\s*\s*\s*([^ \t]+)(.*)$")
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"\s")
    assert r.example_prefix == "#"
    assert r.killer == from_regex(r"[ \t]")
    assert (
        r.example() == "'#' + ' ' * 3456"
    ), "Merge repeated character and killer in example if possible"


@pytest.mark.parametrize(
    "r",
    [
        r"a+",
        r"a(aa)+a",
        r"a*",
        r"\w*b?c*(def|gh+i|$|\b||)+",
    ],
)
def test_groupref(r):
    rs = find_redos(fr"({r})(a+)\1(a+)b")
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"a")


def test_groupref_not_starry_itself():
    rs = find_redos(r"(a+)(a+)\1b")
    assert not rs


def test_groupref_false_positive():
    # from codemirror
    rs = find_redos(r"^([*\-_])(?:\s*\1){2,}\s*$")
    assert not rs


def test_optional_starry():
    # ua-parser CFNetwork
    rs = find_redos(r"(\d+).?(\d+)?.?(\d+)?.?(\d+)?C")
    r = rs[0]
    assert r.starriness == 4
    assert r.repeated_character == from_regex(r"\d")


def test_negative_lookahead():
    # The final (?!c) isn't actually doing anything yet
    rs = find_redos(r"[abc]+(?!c)[abc]+(?!b)([abc]+[abc])(?!c)[abc]*x")
    r = rs[0]
    assert r.starriness == 4
    assert r.repeated_character == from_regex(r"a")


@pytest.mark.parametrize(
    "r",
    [
        r"(a?b+)+c",
        r"(x*[ab]*x?[bc]*x?)*c",
        r"(x?[ab]+x?[bc]+\w*x?)*c",
    ],
)
def test_regexlib_sequence_exponential(r):
    rs = find_redos(r)
    r = rs[0]
    assert r.starriness > 10
    assert r.repeated_character == from_regex(r"b")
    assert r.killer is None


def test_dt_branch_exponential():
    rs = find_redos(r"a(z|\w*b)*d")
    r = rs[0]
    assert r.starriness == 11
    assert r.repeated_character == from_regex(r"b")
    assert r.killer is None


def test_node_forge_false_positive():
    rs = find_redos(r"\s*([^=]*)=?([^;]*)(;|$)")
    assert not rs


def test_ruby_maruku_false_positive():
    rs = find_redos(r"(\S.*\S)*\s*")
    assert not rs


def test_real_httplib2():
    rs = find_redos(
        r"^(?:\s*(?:,\s*)?([^ \t\r\n=]+)\s*=\s*\"?((?<=\")(?:[^\\\"]|\\.)*?(?=\")|(?<!\")[^ \t\r\n,]+(?!\"))\"?)(.*)$"
    )
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"[\f\v\xa0]")
    assert r.killer is None


def test_real_markdown2():
    rs = find_redos(r"\s*?([\w+-]+)?\s*?\n(.*?)^```")
    r = rs[0]
    assert r.starriness == 3
    assert r.repeated_character == from_regex(r"\n")
    assert r.killer is None


def test_editorconfig_false_positive():
    rs = find_redos(r"\s*(.*?)\s*([#;].*)?$")
    assert not rs
