# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Count the shapes with a tiny dependency-graph checker.

Builds ww, wr and rw edges from a history of (transaction, op, object,
version) and finds the cycles, for the lost-update, write-skew and read-skew
histories, then for write skew with a materialized conflict.
"""
import argparse, json
from itertools import permutations

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()


def edges(h):
    """Edges between transactions. Each read names the version it returned (snapshot isolation):
    wr from that version's writer; rw to whoever installed the next version of the object."""
    writers = {}                                       # (object, version) -> writer
    for t, op, x, v in h:
        if op == "w": writers[(x, v)] = t
    order = {}                                         # object -> versions in install order
    for t, op, x, v in h:
        if op == "w": order.setdefault(x, []).append(v)
    E = set()
    for x, vs in order.items():                        # ww: consecutive versions
        for a, b in zip(vs, vs[1:]):
            if writers[(x, a)] != writers[(x, b)]: E.add((writers[(x, a)], writers[(x, b)], "ww"))
    for t, op, x, v in h:
        if op != "r": continue
        if (x, v) in writers and writers[(x, v)] != t: E.add((writers[(x, v)], t, "wr"))
        vs = [0] + order.get(x, [])                    # version 0 = the initial value
        nxt = vs[vs.index(v) + 1] if v in vs and vs.index(v) + 1 < len(vs) else None
        if nxt is not None and writers[(x, nxt)] != t: E.add((t, writers[(x, nxt)], "rw"))
    return E


def cycles(E):
    """Simple cycles (as edge lists) in a small graph, each reported once."""
    nodes = sorted({a for a, _, _ in E} | {b for _, b, _ in E})
    out, seen = [], set()
    for k in range(2, len(nodes) + 1):
        for perm in permutations(nodes, k):
            if perm[0] != min(perm): continue
            path = []
            for a, b in zip(perm, perm[1:] + perm[:1]):
                es = [e for e in E if e[0] == a and e[1] == b]
                if not es: break
                path.append(es[0])
            else:
                key = frozenset(path)
                if key not in seen: seen.add(key); out.append(path)
    return out


H = {
    # T1 reads x (v0), T2 writes x (v1) and commits, T1 writes x (v2): T2's write is lost
    "lost update": [("T1", "r", "x", 0), ("T2", "r", "x", 0), ("T2", "w", "x", 1), ("T1", "w", "x", 2)],
    # both read x and y at v0, T1 writes x, T2 writes y
    "write skew": [("T1", "r", "x", 0), ("T1", "r", "y", 0), ("T2", "r", "x", 0), ("T2", "r", "y", 0),
                   ("T1", "w", "x", 1), ("T2", "w", "y", 1)],
    # T1 reads x at v0; T2 writes x and y; T1 reads y at T2's version
    "read skew": [("T1", "r", "x", 0), ("T2", "w", "x", 1), ("T2", "w", "y", 1), ("T1", "r", "y", 1)],
    # write skew plus a write by both to a shared row z (the materialized conflict)
    "write skew + shared row": [("T1", "r", "x", 0), ("T1", "r", "y", 0), ("T2", "r", "x", 0), ("T2", "r", "y", 0),
                                ("T1", "w", "z", 1), ("T2", "w", "z", 2), ("T1", "w", "x", 1), ("T2", "w", "y", 1)],
}
rows = []
for name, h in H.items():
    E = edges(h)
    for c in cycles(E):
        kinds = [k for _, _, k in c]
        rows.append({"history": name, "cycle": " → ".join(f"{a}-{k}->{b}" for a, b, k in c),
                     "rw": kinds.count("rw"), "ww": kinds.count("ww"), "wr": kinds.count("wr"),
                     "objects": len({x for t, op, x, v in h})})
        print(f"{name:<24} cycle {rows[-1]['cycle']:<34} rw={rows[-1]['rw']} ww={rows[-1]['ww']} wr={rows[-1]['wr']}")
    if not cycles(E): print(f"{name:<24} no cycle")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"cycles": rows}}, f)