#!/usr/bin/env python3
"""recompute.py -- independent ("blind") recomputation of the Aries Orbitals
leaderboard at the Snapshot, from the published counting rule only.

Rule sources (the only sources): Terms Section 6 (6.1, 6.2) and Aries Honorary
Rules A3, A4, A5. "Receiving Address" = history file's `treasury`.
"The time standings are computed" = the Snapshot block N (A4).

INTERPRETATION DECISIONS (each rests on the quoted sentence; also listed in
RECOMPUTE-DECISIONS.md, same numbering):

D1  Snapshot cut-off is by block height: every transaction with height <= N
    counts, including transactions in block N positioned after the piece-#3000
    transaction; every transaction with height > N is ignored even if present
    in the input.  Rests on A4: "Standings at that block are final for track
    (a). Transactions in later blocks do not count."

D2  Only confirmed transactions count (unconfirmed have no block/position and
    cannot be "at" the Snapshot block).  Rests on A4 (as D1) and A5: "Ranking
    is deterministic from public chain data."

D3  "Paying the Receiving Address": a transaction pays the Receiving Address
    when the sats it sends to the Receiving Address from other addresses are
    positive, i.e. net = (sum of values of outputs whose address is the
    Receiving Address) - (sum of values of inputs whose address is the
    Receiving Address) > 0.  That net is the amount counted for the
    transaction.  Consequently the treasury's own spends and its change outputs
    are not donations.  Rests on 6.2: "cumulative sats sent to the Receiving
    Address from any address" and 6.1: "Each transaction paying the Receiving
    Address".

D4  Multiple outputs to the Receiving Address in one transaction are summed
    (within the D3 net).  Rests on 6.2: "cumulative sats sent to the Receiving
    Address".

D5  "First non-Receiving-Address output" = the output with the lowest index n
    whose `address` is non-null and is not the Receiving Address.  Outputs with
    no address (OP_RETURN, bare/non-standard scripts) are skipped, because
    attribution is to an address and an address-less output cannot be one.
    Rests on 6.1: "attributed to the first non-Receiving-Address output" read
    together with 6.2: "from any address that holds ..." and "Ranks and
    addresses are shown".

D6  A paying transaction with no qualifying output under D5 (every addressed
    output is the Receiving Address, or the only other outputs have no
    address) is attributed to nobody and counts for no one.  It is still
    included in counts.transactions_considered.  Rests on 6.1 (attribution
    target is an output that is not the Receiving Address; none exists).

D7  Inputs play no part in attribution (only in the D3 net).  The donor is the
    attributed output's address even if it differs from the funding inputs.
    Rests on 6.1: "attributed to the first non-Receiving-Address output of
    that transaction."

D8  Refused/failed mints and any other paying transaction count identically;
    no protocol-level outcome is consulted.  Rests on 6.2: "Refused mints
    still count as donations" and 6.1: "public transaction history alone".

D9  Eligibility: an attributed address is eligible iff it is `holder_at_N` of
    at least one piece in the holdings file.  `holdings` in each row = number
    of pieces with holder_at_N equal to the address.  Pieces with
    holder_at_N = null (destroyed / held by no address) count for nobody.
    Rests on 6.2: "from any address that holds at least one Aries Orbitals
    piece at the time standings are computed" and the brief's definition of
    that time as block N.

D10 Only addresses with a positive cumulative total appear on the
    leaderboard; a piece holder that sent nothing is not ranked.  Rests on
    6.2: "Ranking is by cumulative sats sent to the Receiving Address".

D11 All eligible donors are output and ranked 1..n (not truncated to 300);
    the top 300 of this list are A3(a).  The Receiving Address itself can
    never be a donor (D5).  Rests on A3: "The 300 addresses ranked highest on
    the Aries Orbitals leaderboard".

D12 Ordering: cumulative total descending; ties broken by the (height, pos)
    at which the address first reached its final cumulative total, earlier
    wins.  Because every counted amount is > 0 (D3), the final total is first
    reached at the address's last attributed transaction at height <= N; a
    later donation therefore moves its tie point later.  Rests on A5: "Ties
    are broken by the block, then the transaction position, at which the tied
    address first reached its final cumulative total -- earlier wins."
    (One transaction is attributed to exactly one address, so two addresses
    can never share a (height, pos); txid and address are appended as
    sort keys only as an inert safety net.)

D13 Ranks are 1..n consecutive with no shared ranks.  Rests on A5: "No
    element of the award is random" plus the full tie-break of D12.

D14 Address comparison: bech32/bech32m addresses (bc1/tb1/bcrt1 prefixes,
    any case) are compared and reported in lowercase; base58 addresses are
    compared byte-exact.  Rests on 6.1: "anyone with a public block explorer
    can recompute them" (explorers emit lowercase bech32; bech32 is
    case-insensitive by its specification).

D15 Duplicate txids in the input are collapsed; if two copies disagree the
    run aborts.  A transaction at height N whose block_hash differs from the
    snapshot block_hash aborts the run (the history is not of the Snapshot
    chain).  Rests on A5: "Ranking is deterministic from public chain data."

D16 Counts: transactions_considered = number of distinct confirmed
    transactions at height <= N that pay the Receiving Address (D3),
    attributed or not; attributed_donors = distinct addresses receiving at
    least one attribution; eligible = attributed donors that pass D9 (= number
    of rows); ineligible_donors = attributed_donors - eligible.
"""

import argparse
import json
import sys
import time
import urllib.error
import urllib.request


# ---------------------------------------------------------------- utilities

def norm_addr(a):
    """D14."""
    if a is None:
        return None
    low = a.lower()
    if low.startswith(("bc1", "tb1", "bcrt1")):
        return low
    return a


class RuleError(Exception):
    pass


def dump_json(obj):
    return json.dumps(obj, sort_keys=True, indent=1) + "\n"


# ---------------------------------------------------------------- core rule

def compute(history, holdings):
    treasury = norm_addr(history["treasury"])
    snap = history.get("snapshot") or {}
    N = snap.get("height")
    if N is None:
        raise RuleError("history.snapshot.height missing")
    N = int(N)
    hN = holdings.get("snapshot_height")
    if hN is not None and int(hN) != N:
        raise RuleError("holdings snapshot_height %r != history snapshot height %r" % (hN, N))
    snap_hash = snap.get("block_hash")

    # --- holdings (D9)
    held = {}
    seen_numbers = {}
    for p in holdings.get("pieces", []):
        num = p.get("number")
        h = norm_addr(p.get("holder_at_N"))
        if num is not None:
            if num in seen_numbers and seen_numbers[num] != h:
                raise RuleError("piece #%s listed twice with different holders" % num)
            if num in seen_numbers:
                continue
            seen_numbers[num] = h
        if h is None:
            continue  # destroyed / no holder: counts for nobody
        held[h] = held.get(h, 0) + 1

    # --- dedupe and filter transactions (D1, D2, D15)
    txs = {}
    for t in history.get("transactions", []):
        txid = t["txid"]
        if txid in txs:
            if json.dumps(txs[txid], sort_keys=True) != json.dumps(t, sort_keys=True):
                raise RuleError("duplicate txid %s with conflicting content" % txid)
            continue
        txs[txid] = t

    considered = []
    for txid, t in txs.items():
        h = t.get("height")
        if h is None:
            continue  # D2: unconfirmed
        h = int(h)
        if h > N:
            continue  # D1
        if h == N and snap_hash and t.get("block_hash") and t["block_hash"] != snap_hash:
            raise RuleError("tx %s at height N has block_hash %s != snapshot %s"
                            % (txid, t["block_hash"], snap_hash))
        if t.get("pos") is None:
            raise RuleError("tx %s has no pos" % txid)
        considered.append(t)

    # Chain order.
    considered.sort(key=lambda t: (int(t["height"]), int(t["pos"]), t["txid"]))

    totals = {}
    first_reached = {}
    paying = 0
    for t in considered:
        out_to_t = sum(int(o.get("value") or 0) for o in t.get("vout", [])
                       if norm_addr(o.get("address")) == treasury)
        in_from_t = sum(int(i.get("value") or 0) for i in t.get("vin", [])
                        if norm_addr(i.get("address")) == treasury)
        net = out_to_t - in_from_t  # D3, D4
        if net <= 0:
            continue
        paying += 1
        # D5: first addressed, non-treasury output in output order.
        donor = None
        for o in sorted(t.get("vout", []), key=lambda o: int(o["n"])):
            a = norm_addr(o.get("address"))
            if a is None or a == treasury:
                continue
            donor = a
            break
        if donor is None:
            continue  # D6
        totals[donor] = totals.get(donor, 0) + net
        # D12: amounts are strictly positive, so the final total is first
        # reached at the last attributed transaction (chain order).
        first_reached[donor] = {"height": int(t["height"]), "pos": int(t["pos"]),
                                "txid": t["txid"]}

    eligible = [a for a in totals if held.get(a, 0) >= 1]  # D9, D10
    eligible.sort(key=lambda a: (-totals[a], first_reached[a]["height"],
                                 first_reached[a]["pos"], first_reached[a]["txid"], a))
    rows = []
    for i, a in enumerate(eligible, 1):
        rows.append({"rank": i, "address": a, "total_sats": totals[a],
                     "holdings": held[a], "first_reached": first_reached[a]})
    return {
        "snapshot_height": N,
        "treasury": treasury,
        "rows": rows,
        "counts": {
            "transactions_considered": paying,
            "attributed_donors": len(totals),
            "eligible": len(eligible),
            "ineligible_donors": len(totals) - len(eligible),
        },
    }


# ---------------------------------------------------------------- fetch mode
# Written per brief; NOT executed during authoring.

class Fetcher:
    MIN_INTERVAL = 1.5

    def __init__(self, host):
        self.host = host.rstrip("/")
        self.last = 0.0

    def get(self, path, as_json=True):
        url = self.host + path
        while True:
            wait = self.MIN_INTERVAL - (time.monotonic() - self.last)
            if wait > 0:
                time.sleep(wait)
            self.last = time.monotonic()
            req = urllib.request.Request(url, headers={"User-Agent": "recompute.py"})
            try:
                with urllib.request.urlopen(req, timeout=60) as r:
                    body = r.read().decode("utf-8")
            except urllib.error.HTTPError as e:
                if e.code == 429:
                    sys.stderr.write("429 on %s; sleeping 60 s\n" % url)
                    time.sleep(60)
                    self.last = time.monotonic()
                    continue
                raise
            return json.loads(body) if as_json else body.strip()


def fetch_history(host, treasury, N):
    f = Fetcher(host)
    seen = {}
    order = []
    last = None
    while True:
        path = "/address/%s/txs/chain" % treasury + ("/%s" % last if last else "")
        page = f.get(path)
        for tx in page:
            if tx["txid"] not in seen:
                seen[tx["txid"]] = tx
                order.append(tx["txid"])
        if len(page) < 25:
            break
        last = page[-1]["txid"]

    snap_hash = f.get("/block-height/%d" % N, as_json=False)

    kept = []
    later = []
    for txid in order:
        tx = seen[txid]
        st = tx.get("status") or {}
        if not st.get("confirmed"):
            continue
        h = int(st["block_height"])
        if h > N:
            later.append({"txid": txid, "height": h})
            continue
        kept.append(tx)

    positions = {}
    for bh in sorted({tx["status"]["block_hash"] for tx in kept}):
        ids = f.get("/block/%s/txids" % bh)
        positions[bh] = {t: i for i, t in enumerate(ids)}

    out = []
    for tx in kept:
        st = tx["status"]
        vin = []
        for i in tx.get("vin", []):
            pv = i.get("prevout") or {}
            vin.append({"prev": "%s:%s" % (i.get("txid"), i.get("vout")),
                        "address": pv.get("scriptpubkey_address"),
                        "value": pv.get("value", 0)})
        vout = []
        for n, o in enumerate(tx.get("vout", [])):
            typ = o.get("scriptpubkey_type")
            vout.append({"n": n, "address": o.get("scriptpubkey_address"), "type": typ,
                         "value": o.get("value", 0),
                         "script": o.get("scriptpubkey") if typ == "op_return" else None})
        out.append({"txid": tx["txid"], "height": int(st["block_height"]),
                    "block_hash": st["block_hash"],
                    "pos": positions[st["block_hash"]][tx["txid"]],
                    "vin": vin, "vout": vout})
    out.sort(key=lambda t: (t["height"], t["pos"]))
    later.sort(key=lambda t: (t["height"], t["txid"]))
    return {"treasury": treasury,
            "snapshot": {"height": N, "block_hash": snap_hash, "txid": None, "position": None},
            "transactions": out, "later": later}


# ---------------------------------------------------------------- self-test

T = "bc1ptreasury"


def _tx(txid, h, pos, outs, ins=None, bh=None):
    return {"txid": txid, "height": h, "block_hash": bh or ("blk%d" % h), "pos": pos,
            "vin": ins or [{"prev": "00:0", "address": "bc1pfunder", "value": 10**8}],
            "vout": [{"n": n, "address": a, "type": "op_return" if a is None else "v1_p0tr",
                      "value": v, "script": "6a" if a is None else None}
                     for n, (a, v) in enumerate(outs)]}


def _hold(N, holders):
    return {"snapshot_height": N,
            "pieces": [{"number": i + 1, "holder_at_N": h} for i, h in enumerate(holders)]}


def self_test():
    N = 100
    failures = []

    def check(name, cond):
        print(("PASS  " if cond else "FAIL  ") + name)
        if not cond:
            failures.append(name)

    def run(txs, holders):
        hist = {"treasury": T, "snapshot": {"height": N, "block_hash": "blk%d" % N,
                                            "txid": "x", "position": 0},
                "transactions": txs, "later": []}
        return compute(hist, _hold(N, holders))

    # 1. ties broken by block, then position
    r = run([_tx("a1", 50, 3, [("bc1pa", 1), (T, 1000)]),
             _tx("b1", 40, 9, [("bc1pb", 1), (T, 1000)]),
             _tx("c1", 50, 1, [("bc1pc", 1), (T, 1000)])],
            ["bc1pa", "bc1pb", "bc1pc"])
    check("tie: earlier block wins, then earlier position",
          [x["address"] for x in r["rows"]] == ["bc1pb", "bc1pc", "bc1pa"]
          and [x["rank"] for x in r["rows"]] == [1, 2, 3])

    # 2. donating after the tie point moves the tie point later
    r = run([_tx("a1", 10, 0, [("bc1pa", 1), (T, 500)]),
             _tx("b1", 15, 0, [("bc1pb", 1), (T, 1000)]),
             _tx("a2", 20, 0, [("bc1pa", 1), (T, 500)])],
            ["bc1pa", "bc1pb"])
    check("late donation: tie point is when the final total was first reached",
          [x["address"] for x in r["rows"]] == ["bc1pb", "bc1pa"]
          and r["rows"][1]["first_reached"] == {"height": 20, "pos": 0, "txid": "a2"}
          and r["rows"][1]["total_sats"] == 1000)

    # 3. transactions above N ignored (and block N fully included)
    r = run([_tx("a1", 100, 7, [("bc1pa", 1), (T, 100)]),
             _tx("b1", 100, 2, [("bc1pb", 1), (T, 200)]),
             _tx("a2", 101, 0, [("bc1pa", 1), (T, 10**6)])],
            ["bc1pa", "bc1pb"])
    check("above N ignored; whole block N counted",
          [(x["address"], x["total_sats"]) for x in r["rows"]] == [("bc1pb", 200), ("bc1pa", 100)]
          and r["counts"]["transactions_considered"] == 2)

    # 4. donors without pieces excluded
    r = run([_tx("a1", 10, 0, [("bc1pa", 1), (T, 100)]),
             _tx("z1", 11, 0, [("bc1pz", 1), (T, 999999)])],
            ["bc1pa"])
    check("donor without pieces excluded",
          [x["address"] for x in r["rows"]] == ["bc1pa"]
          and r["counts"] == {"transactions_considered": 2, "attributed_donors": 2,
                              "eligible": 1, "ineligible_donors": 1})

    # 5. destroyed pieces count for nobody
    r = run([_tx("a1", 10, 0, [("bc1pa", 1), (T, 100)]),
             _tx("b1", 11, 0, [("bc1pb", 1), (T, 100)])],
            ["bc1pa", None, None, "bc1pa"])
    check("destroyed pieces count for nobody",
          [(x["address"], x["holdings"]) for x in r["rows"]] == [("bc1pa", 2)])

    # 6. attribution: skip treasury and address-less outputs; first wins
    r = run([_tx("a1", 10, 0, [(T, 300), (None, 0), ("bc1pa", 1), ("bc1pz", 5)]),
             _tx("n1", 11, 0, [(T, 300), (None, 0)])],
            ["bc1pa", "bc1pz"])
    check("first addressed non-treasury output; unattributable tx counts for nobody",
          [(x["address"], x["total_sats"]) for x in r["rows"]] == [("bc1pa", 300)]
          and r["counts"]["transactions_considered"] == 2
          and r["counts"]["attributed_donors"] == 1)

    # 7. treasury self-spend with change is not a donation
    r = run([_tx("s1", 10, 0, [("bc1pa", 5000), (T, 4000)],
                 ins=[{"prev": "aa:0", "address": T, "value": 10000}]),
             _tx("a1", 11, 0, [("bc1pa", 1), (T, 100), (T, 50)])],
            ["bc1pa"])
    check("treasury self-spend excluded; multiple treasury outputs summed",
          [(x["address"], x["total_sats"]) for x in r["rows"]] == [("bc1pa", 150)]
          and r["counts"]["transactions_considered"] == 1)

    # 8. determinism and duplicate txids
    txs = [_tx("a1", 10, 0, [("bc1pa", 1), (T, 100)])]
    r1 = dump_json(run(txs + txs, ["bc1pa"]))
    r2 = dump_json(run(list(reversed(txs + txs)), ["bc1pa"]))
    check("byte-identical output; duplicates collapsed",
          r1 == r2 and json.loads(r1)["rows"][0]["total_sats"] == 100)

    # 9. holders with no donation are not ranked
    r = run([_tx("a1", 10, 0, [("bc1pa", 1), (T, 100)])], ["bc1pa", "bc1pq"])
    check("holder with zero donations not ranked", len(r["rows"]) == 1)

    print("self-test: %s (%d failure%s)" % ("OK" if not failures else "FAILED",
                                              len(failures), "" if len(failures) == 1 else "s"))
    return 0 if not failures else 1


# ---------------------------------------------------------------- CLI

def main(argv=None):
    ap = argparse.ArgumentParser(description=__doc__.split("\n")[0])
    ap.add_argument("--history")
    ap.add_argument("--holdings")
    ap.add_argument("--out")
    ap.add_argument("--fetch", action="store_true")
    ap.add_argument("--host", default="https://mempool.space/api")
    ap.add_argument("--treasury")
    ap.add_argument("--snapshot-height", type=int)
    ap.add_argument("--save-history", help="with --fetch: also write the normalised history here")
    ap.add_argument("--self-test", action="store_true")
    a = ap.parse_args(argv)

    if a.self_test:
        return self_test()
    if not a.holdings or not a.out:
        ap.error("--holdings and --out are required")
    with open(a.holdings) as fh:
        holdings = json.load(fh)
    if a.fetch:
        if not a.treasury or a.snapshot_height is None:
            ap.error("--fetch needs --treasury and --snapshot-height")
        history = fetch_history(a.host, a.treasury, a.snapshot_height)
        if a.save_history:
            with open(a.save_history, "w") as fh:
                fh.write(dump_json(history))
    else:
        if not a.history:
            ap.error("--history is required (or use --fetch)")
        with open(a.history) as fh:
            history = json.load(fh)
    result = compute(history, holdings)
    with open(a.out, "w") as fh:
        fh.write(dump_json(result))
    return 0


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