"""Convergence is free. Correctness is not.

Two replicated sets side by side under identical operations: an OR-Set that
decides conflicts with a vector clock, and a last-write-wins store that
decides them with a timestamp. Both converge in every run below. Only one of
them gets better when the replicas talk more.

Everything here is seeded and every timestamp is caller-supplied, so the
output is byte-identical on every run.
"""

import random

from crdt import POLICIES, fmt, gen_trace, run, run_gossip, sequential

SEED, N_REP, N_ELEM, N_OPS, SKEW = 0, 3, 5, 16, 9
SCHEDULES = ((1, "after every op"), (4, "every 4 ops"), (16, "once, at the end"))

SEEDS = 200
GOSSIP_RATES = (0.0, 0.05, 0.2, 0.5, 1.0, 3.0)
SKEW_CHOICES = [0, 3, 7, 25, 100]

SW_REP, SW_ELEM, SW_OPS = 3, 6, 120
SW_SCHEDULES = (1, 2, 3, 4, 8, 16, 32, 64, 120)
P_ADD = 0.55


def banner(text):
    print()
    print("=== %s ===" % text)
    print()


# --- 1. one trace, three sync schedules -----------------------------------
banner("1. one trace: %d ops, %d replicas, %d elements, replica 0's clock +%d ticks"
       % (N_OPS, N_REP, N_ELEM, SKEW))
trace = gen_trace(SEED, N_OPS, N_REP, N_ELEM, 1)
tick = 0
for event in trace:
    if event[0] == "op":
        print("  t=%-3d r%d %-6s %s" % (tick, event[1], event[3], event[2]))
        tick += 1
truth = sequential(trace)
print()
print("  what one machine applying these ops in this order would hold: %s" % fmt(truth))
print()
print("  sync schedule        OR-Set (vector clock)       LWW store (timestamp)")
converged = True
for every, label in SCHEDULES:
    tr = gen_trace(SEED, N_OPS, N_REP, N_ELEM, every)
    orset, c1, _ = run(tr, "add-wins", N_REP, skew={0: SKEW})
    lww, c2, _ = run(tr, "pure-lww", N_REP, skew={0: SKEW})
    converged = converged and c1 and c2
    print("  %-20s %-16s wrong=%d    %-14s wrong=%d"
          % (label, fmt(orset), len(orset ^ truth), fmt(lww), len(lww ^ truth)))
print()
print("  every replica agreed with every other in all 6 runs: %s" % converged)

# --- 2. where those wrong answers came from -------------------------------
banner("2. the two flips, derived")
print("  e4:")
tick = 0
for event in trace:
    if event[0] == "op":
        if event[2] == "e4":
            print("    t=%-3d r%d %-4s e4   stamped %d"
                  % (tick, event[1], event[3],
                     tick + (SKEW if event[1] == 0 else 0)))
        tick += 1
print("    12 > 5, so the delete loses -- even syncing after every single op.")
print()
print("    skew  %-25s %s" % ("LWW value, sync every op", "e4 present?"))
for skew in range(6):
    tr = gen_trace(SEED, N_OPS, N_REP, N_ELEM, 1)
    value, conv, _ = run(tr, "pure-lww", N_REP, skew={0: skew})
    assert conv
    print("    %-5d %-25s %s" % (skew, fmt(value), "e4" in value))
print()
print("  e0:")
tick = 0
for event in trace:
    if event[0] == "op":
        if event[2] == "e0":
            print("    t=%-3d r%d %-4s e0" % (tick, event[1], event[3]))
        tick += 1
print("    the last two ops are 1 tick apart on different replicas; whether")
print("    they are concurrent is decided by the sync schedule, not the clock.")
print()
print("    %-14s %-22s %s" % ("sync schedule", "OR-Set value", "e0 present?"))
for every in (1, 2, 4, 8, 16):
    tr = gen_trace(SEED, N_OPS, N_REP, N_ELEM, every)
    value, conv, _ = run(tr, "add-wins", N_REP, skew={0: SKEW})
    assert conv
    print("    sync_every=%-3d %-22s %s" % (every, fmt(value), "e0" in value))

# --- 3. the headline: gossip harder, measure the error --------------------
banner("3. %d seeds, %d replicas, random pairwise gossip, random per-replica skew"
       % (SEEDS, SW_REP))
print("  gossip  OR-Set wrong   LWW wrong   LWW exact   OR-Set false-absent   converged")
for rate in GOSSIP_RATES:
    wrong = {"add-wins": 0, "pure-lww": 0}
    absent = 0
    exact = 0
    allconv = True
    for seed in range(SEEDS):
        rng = random.Random(10000 + seed)
        skews = {r: rng.choice(SKEW_CHOICES) for r in range(SW_REP)}
        for policy in ("add-wins", "pure-lww"):
            value, conv, ground = run_gossip(seed, SW_REP, policy, rate, skews,
                                             n_ops=SW_OPS, n_elems=SW_ELEM)
            allconv = allconv and conv
            wrong[policy] += len(value ^ ground)
            if policy == "add-wins":
                absent += len(ground - value)
            elif value == ground:
                exact += 1
    print("  %-7.2f %-14.3f %-11.3f %-11s %-21.3f %s"
          % (rate, wrong["add-wins"] / SEEDS, wrong["pure-lww"] / SEEDS,
             "%d/%d" % (exact, SEEDS), absent / SEEDS, allconv))
print()
print("  60x the gossip moves one column and not the other.")

# --- 4. flat on average, or flat per trace? -------------------------------
banner("4. %d seeds, %d elements, %d ops, replica 0's clock +1000 ticks"
       % (SEEDS, SW_ELEM, SW_OPS))
mismatch = {"add-wins": 0, "pure-lww": 0}
totals = {p: {k: 0 for k in SW_SCHEDULES} for p in ("add-wins", "pure-lww")}
for seed in range(SEEDS):
    for policy in ("add-wins", "pure-lww"):
        values = {}
        for every in SW_SCHEDULES:
            tr = gen_trace(seed, SW_OPS, SW_REP, SW_ELEM, every)
            value, conv, _ = run(tr, policy, SW_REP, skew={0: 1000})
            assert conv
            values[every] = value
            totals[policy][every] += len(value ^ sequential(tr))
        mismatch[policy] += len(set(values.values())) != 1
print("  sync_every    OR-Set wrong   LWW wrong")
for every in SW_SCHEDULES:
    print("  %-13d %-14.3f %.3f"
          % (every, totals["add-wins"][every] / SEEDS,
             totals["pure-lww"][every] / SEEDS))
print()
for policy in ("add-wins", "pure-lww"):
    print("  traces whose final %-8s value changed across those 9 schedules: %d/%d"
          % (policy, mismatch[policy], SEEDS))
print()
print("  closed form for the LWW column, from the ops and the clocks alone:")
print("    %d elements x P(last op isn't r0's) x P(labels differ)" % SW_ELEM)
print("      = %d x 2/3 x (2 x %.2f x %.2f) = %.4f"
      % (SW_ELEM, P_ADD, 1 - P_ADD, SW_ELEM * (2 / 3) * 2 * P_ADD * (1 - P_ADD)))
print("    measured, at every one of the 9 schedules: %.4f"
      % (totals["pure-lww"][8] / SEEDS))

# --- 5. the policy is invisible until there is concurrency ----------------
banner("5. when is the conflict policy observable at all?")
print("  sync_every   add-wins != rm-wins   all three policies differ")
for every in (1, 2, 4, 8, 12, 40, 120):
    differ, three = 0, 0
    for seed in range(SEEDS):
        values = {}
        for policy in POLICIES:
            value, conv, _ = run(gen_trace(seed, SW_OPS, SW_REP, SW_ELEM, every),
                                 policy, SW_REP, skew={0: 7})
            assert conv
            values[policy] = value
        differ += values["add-wins"] != values["rm-wins"]
        three += len(set(values.values())) == 3
    print("  %-12d %-21s %d/%d"
          % (every, "%d/%d" % (differ, SEEDS), three, SEEDS))
print()
print("  three policies, three different converged sets, no coordinator, no")
print("  disagreement between replicas in any of them.")
print()