#!/usr/bin/env python3
"""Version numbers detect the conflict last-write-wins hides, DDIA 2e Ch. 6.

In leaderless (and multi-leader) replication two clients can write the same key
concurrently -- each based on the same prior state, neither having seen the
other. Last-Write-Wins resolves this by keeping the greater-timestamp write and
throwing the other away, silently. But the two writes were CONCURRENT: neither
happened-before the other, so neither is safe to discard. LWW loses data.

The book's fix (§"Capturing the happens-before relationship") is a version
number per key. The rules:

  * A client must READ before it writes. A read returns every un-overwritten
    value (the "siblings") plus the current version number.
  * When a client writes, it sends back the version number it last read. The
    server OVERWRITES (removes) every value at or below that version -- those the
    client had already seen and thus subsumes -- but KEEPS every sibling written
    since, because the client had not seen those and cannot claim to supersede
    them. It then stores the new value under a freshly incremented version.

A write "based on v0" that arrives after another "based on v0" write therefore
does NOT overwrite it: both survive as siblings, and the app is handed both to
merge. No coordination, no clocks, no lost data.

We replay the book's shopping-cart example on such a server, printing the
version and sibling set after every step, then replay the SAME two concurrent
writes under naive LWW so the dropped cart is visible side by side. Pure
standard library, fully deterministic.
"""


class VersionedStore:
    """Single-replica store keeping a version number + un-overwritten siblings.

    `siblings` maps the version at which a value was written -> the value. The
    key invariant: a value stored under version v was written by a client that
    had seen everything up to some earlier version, so it may only be overwritten
    by a later write that has seen v itself.
    """

    def __init__(self):
        self.version = 0
        self.siblings = {}  # version_written -> value (a cart, as a tuple)

    def read(self):
        """Return (current version, list of sibling values) -- what a client sees."""
        values = [self.siblings[v] for v in sorted(self.siblings)]
        return self.version, values

    def write(self, based_on_version, value):
        """Apply a write the client made after reading `based_on_version`.

        Overwrite every value at or below the version the client had seen; keep
        every sibling written since (the client never saw those); store the new
        value under a new, incremented version.
        """
        self.siblings = {
            v: val for v, val in self.siblings.items() if v > based_on_version
        }
        self.version += 1
        self.siblings[self.version] = value
        return self.version


def show(store, note):
    version, values = store.read()
    carts = "  ".join(fmt_cart(c) for c in values)
    print(f"    server: version {version}, siblings {{ {carts} }}   {note}")


def fmt_cart(cart):
    return "[" + ", ".join(cart) + "]"


def version_vector_run():
    print("VERSION NUMBERS -- the server keeps a version + the un-overwritten siblings")
    print("-" * 74)
    store = VersionedStore()
    show(store, "(empty cart, nothing written yet)")

    # Client 1 reads the empty cart (v0), adds milk, writes based on v0.
    c1_seen, _ = store.read()
    store.write(c1_seen, ("milk",))
    show(store, "client 1 read v0, added milk, wrote based on v0")

    # Client 2 ALSO read v0 -- BEFORE client 1's write existed -- adds eggs,
    # writes based on v0. Its write does not overwrite [milk] (written at v1 > 0).
    c2_seen = 0  # client 2 had read version 0 earlier, concurrently with client 1
    store.write(c2_seen, ("eggs",))
    show(store, "client 2 also read v0, added eggs, wrote based on v0  <-- CONCURRENT")

    print("    ^ two writes both 'based on v0' -> server recognizes them as concurrent")
    print("      and returns BOTH as siblings. Neither milk nor eggs is lost.\n")

    # A later client reads BOTH siblings (v2), merges them, writes based on v2.
    merge_seen, merge_values = store.read()
    merged = tuple(dict.fromkeys(v for cart in merge_values for v in cart))
    store.write(merge_seen, merged)
    show(store, f"later client read v2, merged siblings -> {fmt_cart(merged)}, wrote based on v2")

    print("    ^ writing based on v2 (having seen both) overwrites both siblings:")
    print("      the conflict is now resolved by the app, with everything preserved.\n")

    _, final = store.read()
    return final[0]  # the single merged cart


def lww_run():
    print("LAST-WRITE-WINS -- same two concurrent writes, keep the greater timestamp")
    print("-" * 74)
    # The identical concurrent writes: client 1 adds milk, client 2 adds eggs.
    # LWW attaches a timestamp and keeps the max. Client 2's write is later on the
    # wall clock, so eggs wins; ties broken by value for a deterministic total order.
    writes = [
        {"client": 1, "value": ("milk",), "ts": 100},
        {"client": 2, "value": ("eggs",), "ts": 101},
    ]
    for w in writes:
        print(f"    client {w['client']} writes {fmt_cart(w['value'])}  (ts={w['ts']})")
    winner = max(writes, key=lambda w: (w["ts"], w["value"]))
    print(f"    => LWW keeps the greater timestamp: {fmt_cart(winner['value'])} "
          f"(client {winner['client']}, ts={winner['ts']})")
    for w in writes:
        if w is not winner:
            print(f"     - {fmt_cart(w['value'])} (client {w['client']}, ts={w['ts']}): "
                  "LOST (silently discarded)")
    print()
    return winner["value"]


def main():
    vv_final = version_vector_run()
    lww_final = lww_run()

    print("bottom line -- what each cart contained after the two concurrent writes:")
    print(f"  version numbers -> {fmt_cart(vv_final)}   "
          "(both writes detected as concurrent, kept as siblings, then merged)")
    print(f"  last-write-wins -> {fmt_cart(lww_final)}          "
          "(one concurrent write silently dropped)")
    lost = [item for item in vv_final if item not in lww_final]
    print(f"  LWW lost: {lost}  -- the customer's cart is missing an item, with no error.")
    print("  Concurrent writes are not ordered by a clock; a version number that")
    print("  captures happens-before is what tells the two apart.")


if __name__ == "__main__":
    main()