"""
CWE-407 benchmark for SQLite defects sqlite-0001 and sqlite-0003.

UNDF-2026-000000299: sqlite-0001 — checkColumnOverlap() in src/trigger.c
UNDF-2026-000000300: sqlite-0003 — sqlite3CreateForeignKey() in src/build.c

Defect 1 (sqlite-0001): every UPDATE on a triggered table scans the trigger's
  watched-column list (pIdList) for each SET-clause column (pEList). Cost:
  O(nExpr * nId) case-insensitive string comparisons per UPDATE.

Defect 2 (sqlite-0003): every CREATE TABLE ... REFERENCES resolves FK column
  names against parent table columns. Cost: O(nFK * parentCols) string
  comparisons per CREATE TABLE. Runs once per DDL statement.

Fix: replace the inner linear scan with a hash table for O(1) lookup when
  either list exceeds a small threshold.

Complexity gate:
  nCol-scaling 5x: time ratio must be <7x (O(N) not O(N^2))
  At nCol=500: must complete in <10ms after fix
  Functional: before/after identical boolean/index results
"""

import time


def strcmp_icmp(a, b):
    """Simulate sqlite3StrICmp cost — case-insensitive string compare."""
    return a.lower() == b.lower()


# ---------------------------------------------------------------------------
# sqlite-0001: checkColumnOverlap() — BEFORE
# ---------------------------------------------------------------------------

def check_column_overlap_before(id_list, expr_list):
    """Original: linear scan of id_list for each expr."""
    for expr in expr_list:
        for name in id_list:  # sqlite3IdListIndex: O(|id_list|) scan
            if strcmp_icmp(expr, name):
                return True
    return False


def check_column_overlap_after(id_list, expr_list):
    """Fixed: hash set for O(1) lookup (when lists > 4 entries)."""
    if len(id_list) <= 4 or len(expr_list) <= 4:
        # Small lists — keep linear scan (no hash overhead)
        return check_column_overlap_before(id_list, expr_list)
    seen = {name.lower() for name in id_list}
    for expr in expr_list:
        if expr.lower() in seen:
            return True
    return False


# ---------------------------------------------------------------------------
# sqlite-0003: sqlite3CreateForeignKey() — BEFORE
# ---------------------------------------------------------------------------

def resolve_fk_columns_before(fk_cols, parent_cols):
    """Original: O(nFK * parentCols) nested sqlite3StrICmp."""
    resolved = []
    for fk_col in fk_cols:
        found = -1
        for j, p_col in enumerate(parent_cols):  # O(parentCols) per FK
            if strcmp_icmp(p_col, fk_col):
                found = j
                break
        resolved.append(found)
    return resolved


def resolve_fk_columns_after(fk_cols, parent_cols):
    """Fixed: hash map for O(1) column lookup."""
    col_index = {c.lower(): j for j, c in enumerate(parent_cols)}
    return [col_index.get(fk.lower(), -1) for fk in fk_cols]


# ---------------------------------------------------------------------------
# Correctness tests
# ---------------------------------------------------------------------------

def test_sqlite_0001_functional():
    """Both versions produce identical boolean results."""
    watched = ["name", "email", "status", "created_at", "updated_at", "role"]
    set_cols = ["email", "bio"]
    assert check_column_overlap_before(watched, set_cols) == check_column_overlap_after(watched, set_cols) == True

    set_cols_no_overlap = ["bio", "avatar"]
    assert check_column_overlap_before(watched, set_cols_no_overlap) == check_column_overlap_after(watched, set_cols_no_overlap) == False

    # Case insensitivity
    assert check_column_overlap_after(["Email"], ["email", "name", "x", "y", "z"]) == True

    print("PASS sqlite-0001 correctness: overlap detection matches before/after")


def test_sqlite_0003_functional():
    """Both versions produce identical index mappings."""
    parent = [f"col_{i}" for i in range(50)]
    fk = ["col_3", "col_17", "col_42"]
    before = resolve_fk_columns_before(fk, parent)
    after = resolve_fk_columns_after(fk, parent)
    assert before == after == [3, 17, 42]

    # Unknown column -> -1
    fk_bad = ["col_3", "nonexistent"]
    assert resolve_fk_columns_before(fk_bad, parent) == resolve_fk_columns_after(fk_bad, parent) == [3, -1]

    print("PASS sqlite-0003 correctness: FK column resolution matches before/after")


# ---------------------------------------------------------------------------
# Complexity gate: timing at wide-table scale
# ---------------------------------------------------------------------------

def make_columns(n):
    return [f"column_name_{i:06d}" for i in range(n)]


def test_sqlite_0001_wide_trigger():
    """
    Wide table with trigger watching many columns, UPDATE changing many.
    nId=200 watched columns, nExpr=50 SET columns (no overlap — worst case).
    """
    watched = make_columns(200)
    set_cols = [f"other_{i}" for i in range(50)]   # no overlap

    # Before
    t0 = time.perf_counter()
    for _ in range(1000):
        check_column_overlap_before(watched, set_cols)
    t_before = time.perf_counter() - t0

    # After
    t0 = time.perf_counter()
    for _ in range(1000):
        check_column_overlap_after(watched, set_cols)
    t_after = time.perf_counter() - t0

    speedup = t_before / t_after if t_after > 0 else float('inf')
    assert speedup >= 5.0, f"FAIL: speedup {speedup:.1f}x (expected >=5x)"
    print(f"PASS sqlite-0001 wide trigger: nId=200, nExpr=50, "
          f"1000 UPDATEs: before={t_before*1000:.1f}ms after={t_after*1000:.1f}ms "
          f"speedup={speedup:.0f}x")


def test_sqlite_0003_wide_table():
    """
    Wide parent table with composite FK referencing many columns.
    parent=500 columns, FK=50 columns at end (worst case — linear scan traverses full parent).
    Realistic for composite keys on wide ML feature tables.
    """
    parent = make_columns(500)
    # FK columns near the end of parent — maximizes linear-scan cost
    fk = [f"column_name_{450+i:06d}" for i in range(50)]

    # Before
    t0 = time.perf_counter()
    for _ in range(1000):
        resolve_fk_columns_before(fk, parent)
    t_before = time.perf_counter() - t0

    # After
    t0 = time.perf_counter()
    for _ in range(1000):
        resolve_fk_columns_after(fk, parent)
    t_after = time.perf_counter() - t0

    speedup = t_before / t_after if t_after > 0 else float('inf')
    assert speedup >= 5.0, f"FAIL: speedup {speedup:.1f}x"
    print(f"PASS sqlite-0003 wide table: parent=500, FK=50, "
          f"1000 CREATE TABLEs: before={t_before*1000:.1f}ms after={t_after*1000:.1f}ms "
          f"speedup={speedup:.0f}x")


def test_sqlite_scaling_ratio():
    """5x scaling: nCol 100 -> 500 should give <7x time ratio (linear, not quadratic)."""
    for defect_label, fn_after in [("sqlite-0001", check_column_overlap_after),
                                    ("sqlite-0003", resolve_fk_columns_after)]:
        small = make_columns(100)
        large = make_columns(500)

        if defect_label == "sqlite-0001":
            query_small = [f"other_{i}" for i in range(50)]
            query_large = [f"other_{i}" for i in range(50)]
        else:
            query_small = [f"column_name_{i*10:06d}" for i in range(5)]
            query_large = [f"column_name_{i*50:06d}" for i in range(5)]

        t0 = time.perf_counter()
        for _ in range(10_000):
            fn_after(small, query_small) if defect_label == "sqlite-0001" else fn_after(query_small, small)
        t_small = time.perf_counter() - t0

        t0 = time.perf_counter()
        for _ in range(10_000):
            fn_after(large, query_large) if defect_label == "sqlite-0001" else fn_after(query_large, large)
        t_large = time.perf_counter() - t0

        ratio = t_large / t_small if t_small > 0 else float('inf')
        assert ratio < 7.0, f"FAIL {defect_label}: scaling 5x gave {ratio:.1f}x (expected <7x)"
        print(f"PASS {defect_label} scaling: 100->500 cols (5x), time ratio={ratio:.1f}x (limit 7x)")


if __name__ == "__main__":
    test_sqlite_0001_functional()
    test_sqlite_0003_functional()
    test_sqlite_0001_wide_trigger()
    test_sqlite_0003_wide_table()
    test_sqlite_scaling_ratio()
    print("ALL PASS")