#!/usr/bin/env python3
"""
uuid256.py — reference implementation of README.md (UUID256, random layout).

    import uuid256
    b   = uuid256.generate()          # 32 bytes, ver=4 / var=10 applied
    txt = uuid256.to_canonical(b)     # '0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f'
    b2  = uuid256.parse(txt)          # bytes; strict by default (ver/var checked)

CLI:
    python3 uuid256.py                # self-tests + exact duplicate check over 10,000,000 ids
    python3 uuid256.py -n 5000000 -i 3   # 5e6 ids with 3 planted duplicates (proves detection)
    python3 uuid256.py -g [count]        # just print one (or count) new ids, nothing else
    python3 uuid256.py -p|-P <text>      # parse (strict|lenient): "ok <hex64>" or "error <kind>"

Pure Python, standard library only. generate() serves ids from a 64 KB pool of OS-CSPRNG
bytes (one os.urandom call per 2048 ids; the pool is advanced under a lock so no two threads can
ever receive the same bytes — also on free-threaded builds — and it is dropped after fork(), per
§5.2), which is ~4x faster than one os.urandom call per id. The bulk duplicate check draws all
randomness from os.urandom in one call, applies §4 with slice assignment, then hashes every
32-byte id into a dict keyed by value (first index wins): exact, O(n), ~150 bytes of RAM per id.
"""
import os, re, struct, sys, threading, time

BYTES = 32
TEXT_LEN = 68                          # 64 hex + 4 hyphens
VERSION = 0x4
_HYPHENS = (16, 25, 34, 43)            # 0-based offsets in canonical text
_GROUP_ENDS = (16, 24, 32, 40)         # hex-digit offsets where a hyphen follows
STRICT_RE = re.compile(r'^[0-9a-f]{16}-[0-9a-f]{8}-4[0-9a-f]{7}-[89ab][0-9a-f]{7}-[0-9a-f]{24}\Z')   # \Z, not $: $ also matches before a final newline
_HEX64 = re.compile(r'^[0-9a-f]{64}\Z')


class ParseError(ValueError):
    pass


def set_ver_var(b: bytearray) -> bytearray:
    """§4 — force version nibble (byte 12) and variant bits (byte 16). Mutates and returns b."""
    b[12] = (b[12] & 0x0F) | (VERSION << 4)   # hex digit 24 = '4'
    b[16] = (b[16] & 0x3F) | 0x80             # hex digit 32 in [89ab]
    return b


_POOL_IDS = 2048                       # 64 KB of CSPRNG output per refill
_pool = iter(())                       # iterator over finished ids; only ever advanced while holding _pool_lock
_pool_lock = threading.Lock()


def _refill_pool():
    global _pool
    buf = bytearray(os.urandom(_POOL_IDS * BYTES))                       # §5.2 — OS CSPRNG, nothing seeded
    buf[12::BYTES] = bytes((x & 0x0F) | (VERSION << 4) for x in buf[12::BYTES])   # §4 on every id at once
    buf[16::BYTES] = bytes((x & 0x3F) | 0x80 for x in buf[16::BYTES])
    _pool = struct.iter_unpack(f'{BYTES}s', buf)                         # yields (bytes,) copies, each exactly once


def _drop_pool():                      # a forked child must not replay the parent's pool (§5.2)
    global _pool, _pool_lock
    _pool, _pool_lock = iter(()), threading.Lock()


if hasattr(os, 'register_at_fork'):
    os.register_at_fork(after_in_child=_drop_pool)


def generate() -> bytes:
    """§5.1 — one id (32 bytes, ver/var applied) from the OS-CSPRNG pool. Thread- and fork-safe."""
    # The lock is taken on every call, not only on refill: next() on a shared iterator is only atomic
    # under the GIL, and on a free-threaded interpreter two unlocked callers could be handed the same
    # 32 bytes — a duplicate id, which §5.2 forbids.
    with _pool_lock:
        try:
            return next(_pool)[0]
        except StopIteration:
            _refill_pool()
            return next(_pool)[0]


def is_strict(b) -> bool:
    """§6 — ver == 4 and var == 10 (False for anything that is not exactly 32 bytes)."""
    return len(b) == BYTES and (b[12] >> 4) == VERSION and (b[16] >> 6) == 0b10


def to_canonical(b) -> str:
    """§3.1 — 16-8-8-8-24 lowercase hex, 68 chars."""
    if len(b) != BYTES:
        raise ValueError("UUID256 is exactly 32 bytes")
    h = bytes(b).hex()
    return f"{h[0:16]}-{h[16:24]}-{h[24:32]}-{h[32:40]}-{h[40:64]}"


def parse(s: str, strict: bool = True) -> bytes:
    """§6 — canonical (68) or compact (64) form, any case. Raises ParseError."""
    s = s.lower()
    if len(s) == TEXT_LEN:
        if any(s[i] != '-' for i in _HYPHENS):
            raise ParseError("hyphen at wrong position")
        s = s.replace('-', '')
    elif len(s) != 64:
        raise ParseError("wrong length")
    if not _HEX64.fullmatch(s):            # fullmatch: '$' alone would also accept a trailing newline
        raise ParseError("invalid character")
    b = bytes.fromhex(s)
    if strict and not is_strict(b):
        raise ParseError("unsupported version/variant")
    return b


NIL = bytes(32)
MAX = b'\xff' * 32


# ---------------------------------------------------------------------------
# Self-tests (spec §11 vectors, §3.2/§6 parser rules, live generation)
# ---------------------------------------------------------------------------

def self_test() -> int:
    fails = 0
    vectors = [
        ("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f",
         "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f"),
        ("fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0",
         "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0"),
    ]
    for i, (raw, expected) in enumerate(vectors, 1):
        b = bytes(set_ver_var(bytearray.fromhex(raw)))
        txt = to_canonical(b)
        ok = (txt == expected and parse(txt) == b and parse(txt.upper()) == b and parse(raw, strict=False) is not None
              and STRICT_RE.fullmatch(txt) is not None)
        try:
            parse(raw)               # compact form of the *raw* input has ver != 4 → strict must reject
            ok = False
        except ParseError:
            pass
        print(f"  spec §11 vector {i}: {'PASS' if ok else 'FAIL'}  {txt}")
        fails += not ok

    def rejects(s, strict=True):
        try:
            parse(s, strict); return False
        except ParseError:
            return True
    nil = to_canonical(NIL)
    ok = (rejects("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f")     # bad hyphen
          and rejects("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1")  # length
          and rejects("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g") # char
          and rejects(nil) and not rejects(nil, strict=False)                                  # nil: strict no, lenient yes
          and parse(nil, strict=False) == NIL and to_canonical(MAX) == 'f' * 16 + '-' + 'f' * 8 + '-' + 'f' * 8 + '-' + 'f' * 8 + '-' + 'f' * 24)
    print(f"  parser rules (§3.2/§6):  {'PASS' if ok else 'FAIL'}")
    fails += not ok

    for _ in range(3):
        b = generate(); txt = to_canonical(b)
        ok = is_strict(b) and STRICT_RE.fullmatch(txt) is not None and parse(txt) == b
        print(f"  generate(): {txt}  {'ok' if ok else 'BAD'}")
        fails += not ok
    return fails


# ---------------------------------------------------------------------------
# Bulk exact duplicate check
# ---------------------------------------------------------------------------

def bulk_generate(n: int) -> bytearray:
    """n ids as one contiguous bytearray (n*32 bytes), §4 applied to every id."""
    buf = bytearray(os.urandom(n * BYTES))
    # extended-slice assignment: byte 12 and byte 16 of every id, without a Python-level loop per id
    buf[12::BYTES] = bytes((x & 0x0F) | (VERSION << 4) for x in buf[12::BYTES])
    buf[16::BYTES] = bytes((x & 0x3F) | 0x80 for x in buf[16::BYTES])
    return buf


def find_duplicates(buf: bytearray, n: int):
    """Exact: hash every 32-byte id into a dict keyed by value, remembering the first index seen.
    Returns list of (first_index, later_index, id_bytes) — one entry per repeated id."""
    mv = memoryview(buf)
    first = {}
    dups = []
    for i in range(n):
        b = bytes(mv[i * BYTES:(i + 1) * BYTES])
        j = first.setdefault(b, i)
        if j != i:
            dups.append((j, i, b))
    return dups


def main(argv):
    n, planted = 10_000_000, 0
    args = argv[1:]
    if args and args[0] == '-g':                                            # just print ids: -g [count]
        count = int(args[1]) if len(args) > 1 and args[1].isdigit() else 1        # -g N: exactly N (0 allowed); junk → 1
        for _ in range(count): print(to_canonical(generate()))
        return 0
    if len(args) >= 2 and args[0] in ('-p', '-P'):                          # parse mode: -p strict, -P lenient
        try:
            print('ok', parse(args[1], strict=(args[0] == '-p')).hex()); return 0
        except ParseError as e:
            print('error', {'wrong length': 'length', 'hyphen at wrong position': 'hyphen', 'invalid character': 'char', 'unsupported version/variant': 'version'}[str(e)]); return 1
    try:
        while args:
            a = args.pop(0)
            if a == '-n': n = int(args.pop(0))
            elif a == '-i': planted = int(args.pop(0))
            else: print("usage: python3 uuid256.py [-g [count]] [-n count] [-i planted_dups] | -p|-P <text>"); return 2
    except (IndexError, ValueError):
        print("usage: python3 uuid256.py [-n count] [-i planted_dups]"); return 2
    if n < 2 or planted < 0 or planted > n // 2:
        print(f"-n must be >= 2 and -i at most n/2 (got n={n:,}, planted={planted})"); return 2
    print("UUID256 reference implementation (Python) — README.md (256-bit random, 16-8-8-8-24 text)\n")
    print("Self-tests:")
    if self_test():
        print("  self-test FAILED — aborting"); return 1

    # per-call API throughput (what an application would see)
    t0 = time.perf_counter(); k = 200_000
    for _ in range(k): generate()
    per_call = (time.perf_counter() - t0) / k
    print(f"\ngenerate() per-call cost: {per_call * 1e6:.2f} µs  → {1 / per_call / 1e6:.2f} M ids/s single-threaded "
          f"(1e9 ids would take ~{1e9 * per_call / 60:.0f} min just to generate)")

    print(f"\nBulk exact duplicate check: n={n:,} ids, planted duplicates={planted}")
    t0 = time.perf_counter()
    buf = bulk_generate(n)
    t1 = time.perf_counter()
    step = (n // 2) // planted if planted else 0    # sources evenly spaced over the lower half, each mirrored
    for kk in range(planted):                       # into the upper half → all 2K positions distinct (K <= n/2)
        src = step * kk; dst = n - 1 - src          # id[dst] := id[src]
        buf[dst * BYTES:(dst + 1) * BYTES] = buf[src * BYTES:(src + 1) * BYTES]
        print(f"  planted: id[{dst:,}] := id[{src:,}]")
    bad = sum(1 for i in range(n) if not is_strict(memoryview(buf)[i * BYTES:(i + 1) * BYTES])) if n <= 2_000_000 else \
          sum(1 for x in buf[12::BYTES] if x >> 4 != VERSION) + sum(1 for x in buf[16::BYTES] if x >> 6 != 0b10)
    dups = find_duplicates(buf, n)
    t2 = time.perf_counter()
    for i, j, b in dups:
        print(f"  DUPLICATE  id[{i:,}] == id[{j:,}]  {to_canonical(b)}")
    # sampled text round-trip
    rt_ok = sum(1 for i in range(0, n, max(1, n // 1000)) if parse(to_canonical(buf[i * BYTES:(i + 1) * BYTES])) == bytes(buf[i * BYTES:(i + 1) * BYTES]))
    print("\n==== RESULT ====")
    print(f"ids generated:                   {n:,}   (bulk os.urandom + §4 in {t1 - t0:.1f}s; hash+compare in {t2 - t1:.1f}s)")
    print(f"version/variant violations:      {bad:,}")
    print(f"text round-trips (sampled):      {rt_ok:,} ok")
    print(f"FULL 256-bit DUPLICATES:         {len(dups):,}" + (f"   (planted: {planted} — {'all detected' if len(dups) == planted else 'COUNT MISMATCH'})" if planted else ""))
    if not dups: print(f"  → no duplicates among {n:,} ids")
    import math
    log2p = 2 * math.log2(n) - 251
    print(f"expected P(any collision) §5.3:  n²/2²⁵¹ ≈ 2^{log2p:.1f} ≈ {2 ** log2p:.1e}")
    return 0 if len(dups) == planted else 1


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