<?php
// National AI Feed verifier (PHP). Verification rules, version 1. Needs PHP 8.1 or newer with the sodium extension.
//
// Usage:
//   php verify-record.php [--keys public-key.json] [--prev-seq N --prev-hash HEX] [--filtered] [--json] page1.json [page2.json ...]
//   php verify-record.php --vectors DIR      run every test vector in DIR and report agreement
//
// A page is a /v1/feed response ({entries, next_after, has_more, feed_head}). A single entry or a list of entries is also accepted
// (then there is no signed head). The older form "php verify-record.php entries.json public-key.json" still works.
// Exit status: 0 nothing wrong found, 1 problems found, 2 input could not be read.

const SPEC = '1.2';
const NEW_FIELDS = [['authority_record_id', 'i'], ['provider_id', 'i'], ['provider_name', 's'], ['government_official_id_type', 's'],
    ['government_official_id', 's'], ['revision', 'i'], ['supersedes_seq', 'i'], ['prev_seq', 'i'], ['prev_hash', 's'],
    ['status_scope', 's'], ['status_event', 's'], ['reason_class', 's'], ['reason_code', 's'],
    ['revoked_from_seq', 'i'], ['revoked_through_seq', 'i'], ['references_seq', 'i']];
const SCOPE_EVENTS = ['provider' => ['suspended', 'reinstated', 'revoked', 'revocation_lifted'],
    'authority_record' => ['suspended', 'reinstated', 'ended', 'revoked', 'revocation_lifted'],
    'publication' => ['revoked', 'revocation_lifted']];
const ADMIN_CODES = ['agreement_lapsed', 'provider_request', 'investigation', 'technical_problem', 'other'];
const COMPROMISE_CODES = ['unauthorized_publishing', 'fraud', 'key_compromise'];

class Unreadable extends Exception {}

function enc_str(string $s): string {
    $out = '"';
    foreach (preg_split('//u', $s, -1, PREG_SPLIT_NO_EMPTY) as $ch) {
        $o = mb_ord($ch, 'UTF-8');
        if ($ch === '"') $out .= '\\"';
        elseif ($ch === '\\') $out .= '\\\\';
        elseif ($o === 8) $out .= '\\b';
        elseif ($o === 12) $out .= '\\f';
        elseif ($o === 10) $out .= '\\n';
        elseif ($o === 13) $out .= '\\r';
        elseif ($o === 9) $out .= '\\t';
        elseif ($o < 0x20) $out .= sprintf('\\u%04x', $o);
        elseif ($o === 0x2028) $out .= '\\u2028';
        elseif ($o === 0x2029) $out .= '\\u2029';
        else $out .= $ch;
    }
    return $out . '"';
}
function enc($v): string {
    if ($v === null) return 'null';
    if (is_bool($v)) return $v ? 'true' : 'false';
    if (is_int($v)) return (string)$v;
    if (is_string($v)) return enc_str($v);
    throw new Unreadable('unsupported value in canonical form');
}
function blank_null($v) { return $v === '' ? null : $v; }
function canonical(array $e): string {
    $a = isset($e['authority']) && is_array($e['authority']) ? $e['authority'] : [];
    $f = [['seq', $e['seq']], ['type', $e['type']], ['external_id', $e['external_id'] ?? null],
        ['authority_name', $a['name'] ?? null], ['authority_type', $a['type'] ?? null], ['state', $a['state'] ?? null],
        ['county', $a['county'] ?? null], ['city', $a['city'] ?? null], ['agency', $e['agency'] ?? null], ['title', $e['title'] ?? null],
        ['body', $e['body'] ?? null], ['source_url', $e['source_url'] ?? null], ['published_at', $e['published_at'] ?? null],
        ['received_at', $e['received_at'] ?? null]];
    $parts = [];
    foreach ($f as [$k, $v]) $parts[] = enc_str($k) . ':' . enc(blank_null($v));
    $att = $e['attachments'] ?? null;
    if (is_array($att) && count($att) > 0) {
        $items = [];
        foreach ($att as $x) {
            $p = [];
            foreach (['id', 'filename', 'content_type', 'size', 'sha256'] as $k) $p[] = enc_str($k) . ':' . enc($x[$k] ?? null);
            $items[] = '{' . implode(',', $p) . '}';
        }
        $parts[] = enc_str('attachments') . ':[' . implode(',', $items) . ']';
    }
    foreach (NEW_FIELDS as [$k, $t]) {
        $v = $e[$k] ?? null;
        if ($v === null || $v === '') continue;
        $parts[] = enc_str($k) . ':' . enc($v);
    }
    return '{' . implode(',', $parts) . '}';
}

const SMALL_ORDER = [
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000080',
    '0100000000000000000000000000000000000000000000000000000000000000',
    '0100000000000000000000000000000000000000000000000000000000000080',
    '26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05',
    '26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85',
    'c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a',
    'c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa',
    'ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f',
    'ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff',
    'edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f',
    'edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff',
    'eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f',
    'eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff',
];   // rules 1.2 section 1.4: points of small order (all 8, both sign bits, and the non-canonical forms).
function load_keys($doc): array {
    // returns [keys, raw]: the usable public keys by key_id, and the key-file entry each came from
    $keys = []; $raw = [];
    $lst = is_array($doc) && is_obj($doc) ? ($doc['keys'] ?? null) : null;
    foreach ((is_array($lst) && is_list($lst) ? $lst : []) as $k) {
        if (!is_array($k) || !is_obj($k) || !isset($k['key_id'], $k['public_key']) || !is_string($k['key_id']) || $k['key_id'] === '' || !is_string($k['public_key'])) continue;
        if (!preg_match('/^[0-9a-fA-F]{64}\z/', $k['public_key']) || in_array(strtolower($k['public_key']), SMALL_ORDER, true)) continue;
        $keys[$k['key_id']] = sodium_hex2bin($k['public_key']);
        $raw[$k['key_id']] = $k;
    }
    return [$keys, $raw];
}
const REVOKE_REASONS = ['key_compromise', 'suspected_compromise'];
const UTC_RE = '/^[0-9]{4}-[0-9]{2}-[0-9]{2}T[0-9]{2}:[0-9]{2}:[0-9]{2}Z\z/';
function notice_text($kid, array $k): string {
    // the exact text a revocation notice signs (VERIFICATION.md 1.3)
    $lth = $k['last_trusted_hash'] ?? null;
    return '{"type":"key_revocation","key_id":' . enc_str((string)$kid) . ',"public_key":' . enc_str($k['public_key']) . ',"revoked_at":' . enc_str($k['revoked_at']) . ',"compromised_since":' . enc_str($k['compromised_since'])
        . ',"last_trusted_seq":' . $k['last_trusted_seq'] . ',"last_trusted_hash":' . ($lth === null ? 'null' : enc_str($lth)) . ',"reason":' . enc_str($k['reason']) . ',"signed_by":' . enc_str($k['notice_signed_by']) . '}';
}
function notice_problem($kid, array $k, array $keys): ?string {
    $ra = $k['revoked_at'] ?? null; $cs = $k['compromised_since'] ?? null; $lts = $k['last_trusted_seq'] ?? null; $lth = $k['last_trusted_hash'] ?? null;
    $why = $k['reason'] ?? null; $by = $k['notice_signed_by'] ?? null; $sig = $k['notice_signature'] ?? null;
    if (!(is_string($ra) && preg_match(UTC_RE, $ra) && is_string($cs) && preg_match(UTC_RE, $cs))) return 'revoked_at or compromised_since is missing or not a UTC time';
    if (strcmp($cs, $ra) > 0) return 'compromised_since is after revoked_at';
    if (!is_int($lts) || $lts < 0) return 'last_trusted_seq is not a whole number of zero or more';
    if ($lts === 0 && $lth !== null) return 'last_trusted_hash must be null when nothing is trusted';
    if ($lts >= 1 && !(is_string($lth) && preg_match('/^[0-9a-f]{64}\z/', $lth))) return 'last_trusted_hash is not a 64-character lower-case hash';
    if (!is_string($why) || !in_array($why, REVOKE_REASONS, true)) return 'reason is not key_compromise or suspected_compromise';
    if (!is_string($by) || $by === $kid || !isset($keys[$by])) return 'notice_signed_by is missing, unknown, or the revoked key itself';
    if (!is_string($sig) || !preg_match('/^[0-9a-fA-F]{128}\z/', $sig)) return 'notice_signature is missing';
    if (!sig_ok($keys[$by], $sig, hash('sha256', notice_text($kid, $k)))) return 'notice_signature does not verify with ' . $by;
    return null;
}
function load_revocations(array $keys, array $raw): array {
    // for every key the file lists as revoked: whether its notice is valid and what it says. An invalid notice makes every entry of that key untrusted.
    $out = [];
    foreach ($raw as $kid => $k) {
        if (($k['status'] ?? null) !== 'revoked') continue;
        $kid = (string)$kid;
        $w = notice_problem($kid, $k, $keys);
        $out[$kid] = $w === null ? ['valid' => true, 'why' => '', 'lts' => $k['last_trusted_seq'], 'lth' => $k['last_trusted_hash'] ?? null, 'since' => $k['compromised_since']]
                                 : ['valid' => false, 'why' => $w, 'lts' => 0, 'lth' => null, 'since' => null];
    }
    return $out;
}
function sig_ok(string $pk, string $sigHex, string $text): bool {
    if (!preg_match('/^[0-9a-fA-F]{128}\z/', $sigHex)) return false;
    return sodium_crypto_sign_verify_detached(sodium_hex2bin($sigHex), $text, $pk);
}

// A JSON object that has no members is read as [EMPTY_OBJECT => true] (see read_json), so it is told apart from an empty list [].
const EMPTY_OBJECT = '~empty-object~';
function is_obj($v): bool { return is_array($v) && !array_is_list($v); }
function is_list($v): bool { return is_array($v) && array_is_list($v); }
function is_pos_int($v): bool { return is_int($v) && $v >= 1; }
function opt_str(array $a, string $k): bool { return !isset($a[$k]) || is_string($a[$k]); }

function entry_shape_problem($e): ?string {
    if (!is_obj($e)) return 'entry is not an object';
    if (!isset($e['seq']) || !is_pos_int($e['seq'])) return 'seq is not a positive integer';
    if (!isset($e['type']) || !in_array($e['type'], ['record', 'removal', 'status'], true)) return 'type is not record, removal or status';
    foreach (['record_hash', 'signature', 'public_key_id', 'received_at'] as $k) if (!isset($e[$k]) || !is_string($e[$k])) return $k . ' is missing';
    if (!opt_str($e, 'external_id')) return 'external_id is not text';
    if (!isset($e['authority']) || !is_obj($e['authority'])) return 'authority is missing';
    foreach (['name', 'type', 'state', 'county', 'city'] as $k) if (!opt_str($e['authority'], $k)) return 'authority.' . $k . ' is not text';
    foreach (['agency', 'title', 'body', 'source_url', 'published_at'] as $k) if (!opt_str($e, $k)) return $k . ' is not text';
    foreach (NEW_FIELDS as [$k, $t]) {
        if (!isset($e[$k])) continue;
        if ($t === 'i' && !is_int($e[$k])) return $k . ' is not an integer';
        if ($t === 's' && !is_string($e[$k])) return $k . ' is not text';
    }
    if (isset($e['attachments'])) {
        if (!is_list($e['attachments'])) return 'attachments is not a list';
        foreach ($e['attachments'] as $x) {
            if (!is_obj($x)) return 'an attachment is not an object';
            foreach (['id', 'filename', 'content_type', 'sha256'] as $k) if (!isset($x[$k]) || !is_string($x[$k])) return 'attachment ' . $k . ' is missing';
            if (!isset($x['size']) || !is_int($x['size'])) return 'attachment size is not an integer';
        }
    }
    return null;
}

function status_problem(array $e): ?string {
    $s = $e['status_scope'] ?? null; $ev = $e['status_event'] ?? null;
    if (!is_string($s) || !isset(SCOPE_EVENTS[$s]) || !in_array($ev, SCOPE_EVENTS[$s], true)) return 'scope and event do not go together';
    if (($e['provider_id'] ?? null) === null || ($e['provider_name'] ?? '') === '') return 'no provider named';
    if (($e['title'] ?? null) !== null || ($e['body'] ?? null) !== null || ($e['revision'] ?? null) !== null || ($e['supersedes_seq'] ?? null) !== null || !empty($e['attachments'])) return 'carries publication fields';
    if ($s === 'provider' && (($e['authority_record_id'] ?? null) !== null || ($e['government_official_id'] ?? '') !== '')) return 'provider-level entry names a record or government';
    if ($s !== 'provider' && (($e['authority_record_id'] ?? null) === null || ($e['government_official_id'] ?? '') === '')) return 'record-level entry names no record or government';
    if ($s === 'publication' && ($e['external_id'] ?? '') === '') return 'publication-level entry has no external_id';
    if ($s !== 'publication' && ($e['external_id'] ?? '') !== '') return 'unexpected external_id';
    $rc = $e['reason_code'] ?? null; $cls = $e['reason_class'] ?? null;
    if ($ev === 'revoked') {
        $f = $e['revoked_from_seq'] ?? null; $t = $e['revoked_through_seq'] ?? null;
        if ($cls !== 'compromise' || !in_array($rc, COMPROMISE_CODES, true)) return 'revocation reason is not a compromise reason';
        if ($f === null || $t === null || !(1 <= $f && $f <= $t && $t < $e['seq'])) return 'revoked range is not valid';
        if (($e['references_seq'] ?? null) !== null) return 'revocation carries references_seq';
    } elseif ($ev === 'revocation_lifted') {
        if ($cls !== 'administrative' || $rc !== 'error_corrected') return 'lift reason is not error_corrected';
        if (($e['revoked_from_seq'] ?? null) !== null || ($e['revoked_through_seq'] ?? null) !== null) return 'lift carries a range';
        $r = $e['references_seq'] ?? null;
        if ($r === null || !(1 <= $r && $r < $e['seq'])) return 'lift does not name an earlier entry';
    } else {
        if ($cls !== 'administrative' || ($e['revoked_from_seq'] ?? null) !== null || ($e['revoked_through_seq'] ?? null) !== null || ($e['references_seq'] ?? null) !== null) return 'administrative event has revocation fields';
        if ($ev === 'suspended' && !in_array($rc, ADMIN_CODES, true)) return 'suspension reason not allowed';
        if ($ev === 'ended' && $rc !== 'provider_request') return 'end reason not allowed';
        if ($ev === 'reinstated' && $rc !== null) return 'reinstatement carries a reason';
    }
    return null;
}

function covers(array $r, array $x): bool {
    if ($x['type'] === 'status') return false;
    if (!($r['revoked_from_seq'] <= $x['seq'] && $x['seq'] <= $r['revoked_through_seq'])) return false;
    $s = $r['status_scope'];
    if ($s === 'provider') return ($x['provider_id'] ?? null) === $r['provider_id'];
    if ($s === 'authority_record') return ($x['authority_record_id'] ?? null) === $r['authority_record_id'];
    return ($x['authority_record_id'] ?? null) === $r['authority_record_id'] && ($x['external_id'] ?? null) === ($r['external_id'] ?? null);
}

function verify_stream(array $pages, $keysDoc, ?array $anchor = null, bool $filtered = false): array {
    // $filtered: the pages came from a filtered read (see VERIFICATION.md, 'Filtered reads')
    if ($filtered && $anchor) throw new Unreadable('an anchor cannot be used with a filtered read (it skips entries, so no entry follows the anchor)');
    [$keys, $rawKeys] = load_keys($keysDoc);
    $revk = load_revocations($keys, $rawKeys);
    $P = []; $N = [];
    $prob = function (string $code, $seq = null, string $detail = '') use (&$P) { $P[] = ['code' => $code, 'seq' => $seq, 'detail' => $detail]; };
    $note = function (string $code, $seq = null) use (&$N) { $N[] = ['code' => $code, 'seq' => $seq]; };
    if ($filtered) $note('filtered_read');
    foreach ($revk as $kid => $r) if (!$r['valid']) $prob('revocation_notice_invalid', null, 'key ' . $kid . ': ' . $r['why']);
    $byRev = [];        // revoked key id => seqs of entries it signed correctly

    $entries = []; $heads = []; $lastPage = null;
    foreach ($pages as $pi => $pg) {
        if (is_obj($pg) && array_key_exists('entries', $pg)) $page = $pg;
        elseif (is_obj($pg) && array_key_exists('seq', $pg)) $page = ['entries' => [$pg]];
        elseif (is_list($pg) && $pg !== []) $page = ['entries' => $pg];
        elseif ($pg === []) $page = ['entries' => []];
        else throw new Unreadable('page ' . ($pi + 1) . ' is not a feed page, an entry or a list of entries');
        if (!is_list($page['entries'])) throw new Unreadable('entries is not a list');
        $good = [];
        foreach ($page['entries'] as $e) {
            $sp = entry_shape_problem($e);
            if ($sp !== null) $prob('entry_malformed', is_array($e) && isset($e['seq']) && is_pos_int($e['seq']) ? $e['seq'] : null, $sp);
            else $good[] = $e;
        }
        $rawLast = $page['entries'] ? $page['entries'][count($page['entries']) - 1] : null;
        if (is_array($rawLast) && isset($rawLast['seq']) && is_int($rawLast['seq']) && array_key_exists('next_after', $page) && $page['next_after'] !== $rawLast['seq']) $prob('page_cursor_mismatch', $rawLast['seq'], 'next_after is not the last entry');
        foreach ($good as $g) $entries[] = $g;
        $lastPage = $page;
        if (isset($page['feed_head'])) $heads[] = [$pi, $page['feed_head'], $good ? $good[count($good) - 1]['seq'] : null];
    }

    $bySeq = []; $firstSeq = $entries ? $entries[0]['seq'] : null; $prev = null;
    $pub = []; $revokes = []; $lifted = [];
    foreach ($entries as $idx => $e) {
        $seq = $e['seq'];
        $text = canonical($e);
        $h = hash('sha256', $text);
        if (isset($e['signature_algorithm']) && $e['signature_algorithm'] !== 'Ed25519') $prob('algorithm_unsupported', $seq);
        elseif ($h !== $e['record_hash'] || !preg_match('/^[0-9a-f]{64}\z/', $e['record_hash'])) $prob('hash_mismatch', $seq);
        else {
            $k = $keys[$e['public_key_id']] ?? null;
            if ($k === null) $prob('key_unknown', $seq);
            elseif (!sig_ok($k, $e['signature'], $h)) $prob('signature_invalid', $seq);
            elseif (isset($revk[(string)$e['public_key_id']])) $byRev[(string)$e['public_key_id']][] = $seq;
        }
        if ($prev !== null && $seq <= $prev['seq']) $prob('seq_not_increasing', $seq);
        $chained = ($e['prev_seq'] ?? null) !== null;
        if ($filtered) {
            // a filtered read skips entries, so links cannot be followed one after another; each link is checked where it can be
            if ($chained) {
                $ps = $e['prev_seq'];
                if (!is_int($ps) || $ps >= $seq) $prob('chain_break', $seq, 'prev_seq is not an earlier entry');
                elseif (isset($bySeq[$ps]) && ($e['prev_hash'] ?? null) !== $bySeq[$ps]['record_hash']) $prob('chain_break', $seq, 'prev_hash differs from the hash of entry ' . $ps . ' in this stream');
            } elseif ($prev !== null && ($prev['prev_seq'] ?? null) !== null) $prob('chain_missing', $seq);
            else $note('unchained_entry', $seq);
        } elseif ($prev === null) {
            if ($anchor && isset($anchor['prev_seq'])) {
                if (($e['prev_seq'] ?? null) !== $anchor['prev_seq'] || ($e['prev_hash'] ?? null) !== ($anchor['prev_hash'] ?? null)) $prob('chain_anchor_mismatch', $seq);
            } elseif ($chained) $note('start_not_anchored', $seq);
            else $note('unchained_entry', $seq);
        } else {
            if ($chained) {
                if ($e['prev_seq'] !== $prev['seq'] || ($e['prev_hash'] ?? null) !== $prev['record_hash']) $prob('chain_break', $seq);
            } elseif (($prev['prev_seq'] ?? null) !== null) $prob('chain_missing', $seq);
            else $note('unchained_entry', $seq);
        }
        if (in_array($e['type'], ['record', 'removal'], true) && ($e['authority_record_id'] ?? null) !== null) {
            $rev = $e['revision'] ?? null; $sup = $e['supersedes_seq'] ?? null;
            if ($rev === null || ($e['provider_id'] ?? null) === null || ($e['government_official_id'] ?? '') === '') $prob('entry_malformed', $seq, 'publication entry lacks revision, provider or government');
            else {
                $key = $e['authority_record_id'] . "\0" . ($e['external_id'] ?? '');
                if (isset($pub[$key])) {
                    [$ls, $lr] = $pub[$key];
                    if ($rev !== $lr + 1) $prob('revision_gap', $seq);
                    if ($sup !== $ls) $prob('supersedes_mismatch', $seq);
                } else {
                    if ($rev === 1) { if ($sup !== null) $prob('supersedes_mismatch', $seq); }
                    else $note('revision_start_not_seen', $seq);
                }
                $pub[$key] = [$seq, $rev];
            }
        }
        if ($e['type'] === 'status') {
            $why = status_problem($e);
            if (!$why && !$filtered && $e['status_event'] === 'revoked' && $firstSeq !== null && $firstSeq <= $e['revoked_from_seq']) {
                $any = false;
                foreach (array_slice($entries, 0, $idx) as $x) if ($e['revoked_from_seq'] <= $x['seq'] && $x['seq'] <= $e['revoked_through_seq'] && covers($e, $x)) { $any = true; break; }
                if (!$any) $why = 'range holds no entry of its scope';
            }
            if (!$why && $e['status_event'] === 'revocation_lifted') {
                $r = $bySeq[$e['references_seq']] ?? null;
                if ($r !== null) {
                    if ($r['type'] !== 'status' || ($r['status_event'] ?? null) !== 'revoked' || ($r['status_scope'] ?? null) !== $e['status_scope'] || ($r['provider_id'] ?? null) !== $e['provider_id']
                        || ($r['authority_record_id'] ?? null) !== ($e['authority_record_id'] ?? null) || ($r['external_id'] ?? null) !== ($e['external_id'] ?? null)) $why = 'does not lift a revocation of the same scope';
                    elseif (isset($lifted[$e['references_seq']])) $prob('lift_duplicate', $seq);
                } elseif (!$filtered && $firstSeq !== null && $e['references_seq'] >= $firstSeq) $why = 'lifts an entry that is not in the feed';
                else $note('lift_target_not_seen', $seq);
            }
            if ($why) $prob('status_malformed', $seq, $why);
            elseif ($e['status_event'] === 'revoked') $revokes[] = $e;
            elseif ($e['status_event'] === 'revocation_lifted' && !isset($lifted[$e['references_seq']])) $lifted[$e['references_seq']] = $seq;
        }
        $bySeq[$seq] = $e;
        $prev = $e;
    }

    $hashAt = [];
    foreach ($entries as $e) $hashAt[$e['seq']] = $e['record_hash'];
    // entries signed by a revoked key: trusted only up to the last trusted entry named in the signed notice, and only if the stream reaches that entry with that hash
    foreach ($byRev as $kid => $seqs) {
        $r = $revk[(string)$kid];
        if (!$r['valid']) { foreach ($seqs as $sq) $prob('key_revoked', $sq, 'key ' . $kid . ' is listed as revoked with a notice that is not valid, so nothing it signed can be trusted'); continue; }
        foreach ($seqs as $sq) if ($sq > $r['lts']) $prob('key_revoked', $sq, 'signed by revoked key ' . $kid . ' after its last trusted entry (seq ' . $r['lts'] . ')');
        $before = array_values(array_filter($seqs, fn($sq) => $sq <= $r['lts']));
        if ($before) {
            if (isset($hashAt[$r['lts']])) {
                if ($hashAt[$r['lts']] === $r['lth']) $note('signed_by_revoked_key_trusted_prefix', min($before));
                else foreach ($before as $sq) $prob('key_revoked', $sq, 'the stream holds entry ' . $r['lts'] . ' with a different hash than the revocation notice of key ' . $kid . ' names');
            } else $note('revoked_key_prefix_unconfirmed', min($before));
        }
    }
    foreach ($heads as [$pi, $hd, $lastSeq]) {
        if (!is_obj($hd) || !isset($hd['seq']) || !is_int($hd['seq']) || !isset($hd['record_hash']) || !is_string($hd['record_hash']) || !isset($hd['signed_at']) || !is_string($hd['signed_at'])
            || !isset($hd['head_hash']) || !is_string($hd['head_hash']) || !isset($hd['signature']) || !is_string($hd['signature']) || !isset($hd['public_key_id']) || !is_string($hd['public_key_id'])) { $prob('head_malformed', null); continue; }
        $text = '{"type":"feed_head","seq":' . $hd['seq'] . ',"record_hash":' . enc_str($hd['record_hash']) . ',"signed_at":' . enc_str($hd['signed_at']) . '}';
        $hh = hash('sha256', $text);
        if ($hh !== $hd['head_hash']) $prob('head_hash_mismatch', $hd['seq']);
        else {
            $k = $keys[$hd['public_key_id']] ?? null;
            if ($k === null) $prob('head_key_unknown', $hd['seq']);
            elseif (!sig_ok($k, $hd['signature'], $hh)) $prob('head_signature_invalid', $hd['seq']);
            elseif (isset($revk[(string)$hd['public_key_id']])) {
                $r = $revk[(string)$hd['public_key_id']];
                if (!$r['valid'] || $hd['seq'] > $r['lts'] || !preg_match(UTC_RE, $hd['signed_at']) || strcmp($hd['signed_at'], $r['since']) >= 0) $prob('head_key_revoked', $hd['seq']);
            }
        }
        if (isset($hashAt[$hd['seq']]) && $hashAt[$hd['seq']] !== $hd['record_hash']) $prob('head_entry_mismatch', $hd['seq']);
        if ($lastSeq !== null && $hd['seq'] < $lastSeq) $prob('head_behind', $hd['seq']);
    }
    if (!$heads) $note('no_head');
    else {
        [$pi, $hd, $lastSeq] = $heads[count($heads) - 1];
        if ($pi === count($pages) - 1 && is_obj($hd) && isset($hd['seq']) && is_int($hd['seq'])) {
            $newest = $entries ? max(array_column($entries, 'seq')) : null;
            if (($lastPage['has_more'] ?? null) === true) $note('stream_incomplete');
            elseif (!$filtered && $newest !== null && $hd['seq'] > $newest) $prob('tail_truncated', $hd['seq']);
        }
    }
    $revoked = [];
    foreach ($entries as $x) {
        if ($x['type'] === 'status') continue;
        foreach ($revokes as $r) {
            if (isset($lifted[$r['seq']])) continue;
            if (covers($r, $x)) { $revoked[$x['seq']] = $r['seq']; break; }
        }
    }
    $cmp = fn($a, $b) => [$a['seq'] ?? -1, $a['code']] <=> [$b['seq'] ?? -1, $b['code']];
    usort($P, $cmp); usort($N, $cmp);
    return ['verifier' => 'php', 'spec' => SPEC, 'entries' => count($entries), 'ok' => !$P, 'problems' => $P, 'notes' => $N, 'derived' => ['revoked' => $revoked]];
}

function pairs(array $l): array { return array_map(fn($x) => [$x['code'], $x['seq']], $l); }

const MAX_DEPTH = 64;
function lex_check(string $raw, string $path): void {
    // rules 1.2 section 1.4: before parsing, refuse nesting deeper than 64 levels and any number that is not a whole number within +-(2^53-1)
    // (no fractions, exponents, NaN or Infinity). The three verifiers apply this identically, so they read the same numbers.
    $n = preg_match_all('/"[^"\\\\]*+(?:\\\\.[^"\\\\]*+)*+"|[\[\]{}]|-?[0-9][0-9.eE+\-]*+|-|NaN|Infinity/s', $raw, $m);
    if ($n === false) throw new Unreadable($path . ': cannot be scanned');
    $depth = 0;
    foreach ($m[0] as $t) {
        $c = $t[0];
        if ($c === '"') continue;
        if ($c === '[' || $c === '{') { if (++$depth > MAX_DEPTH) throw new Unreadable($path . ': nested deeper than ' . MAX_DEPTH . ' levels'); }
        elseif ($c === ']' || $c === '}') $depth--;
        elseif (!preg_match('/^-?(?:0|[1-9][0-9]*)\z/', $t) || strlen(ltrim($t, '-')) > 16 || abs((float)$t) > 9007199254740991.0) throw new Unreadable($path . ': a number is not a whole number within +-(2^53-1)');
    }
}
function to_arrays($v) {
    if (is_object($v)) { $a = []; foreach ($v as $k => $x) $a[$k] = to_arrays($x); return $a ?: [EMPTY_OBJECT => true]; }
    if (is_array($v)) return array_map('to_arrays', $v);
    return $v;
}
function parse_text(string $raw, string $path) {
    lex_check($raw, $path);
    $o = json_decode($raw, false, 512);
    if ($o === null && trim($raw) !== 'null') throw new Unreadable($path . ': ' . json_last_error_msg());
    return to_arrays($o);
}
function read_json(string $path) {
    $raw = @file_get_contents($path);
    if ($raw === false) throw new Unreadable($path . ': cannot be read');
    return parse_text($raw, $path);
}

function run_vector(array $v): array {
    try { $pages = isset($v['raw_pages']) && is_array($v['raw_pages']) ? array_map(fn($t) => parse_text($t, 'vector'), $v['raw_pages']) : $v['pages'];
          $rep = verify_stream($pages, $v['keys'], $v['anchor'] ?? null, !empty($v['filtered'])); }
    catch (Unreadable $ex) { $rep = ['unreadable' => true]; }
    $exp = $v['expect'];
    if (!empty($exp['unreadable'])) return [!empty($rep['unreadable']), $rep];
    if (!empty($rep['unreadable'])) return [false, $rep];
    $er = $exp['derived']['revoked'] ?? []; ksort($er); $gr = $rep['derived']['revoked']; ksort($gr);
    $ok = $rep['ok'] === $exp['ok'] && pairs($rep['problems']) === $exp['problems'] && pairs($rep['notes']) === $exp['notes'] && $gr == $er;
    return [$ok, $rep];
}

function run_vectors(string $dir): int {
    $files = glob(rtrim($dir, '/') . '/*.json'); sort($files); $bad = 0; $n = 0;
    foreach ($files as $f) {
        if (basename($f) === 'manifest.json') continue;
        $n++;
        $raw = file_get_contents($f);
        $v = json_decode($raw, true, 512);
        if ($v === null) {
            // a vector whose pages hold text that is not valid (a lone surrogate) cannot even be decoded here: that is the expected outcome
            $meta = json_decode(preg_replace('/"pages"\s*:.*?"expect"/s', '"pages":[],"expect"', $raw), true);
            $ok = is_array($meta) && !empty($meta['expect']['unreadable']);
            echo ($ok ? 'PASS ' : 'FAIL ') . basename($f) . "\n"; if (!$ok) $bad++;
            continue;
        }
        [$ok, $rep] = run_vector($v);
        echo ($ok ? 'PASS ' : 'FAIL ') . basename($f) . "\n";
        if (!$ok) { $bad++; echo '   got: ' . substr(json_encode($rep), 0, 600) . "\n"; }
    }
    echo "$n vectors, " . ($n - $bad) . " passed, $bad failed\n";
    return $bad ? 1 : 0;
}

function main(array $argv): int {
    array_shift($argv);
    $keysPath = 'public-key.json'; $anchor = []; $asJson = false; $files = []; $vec = null; $filtered = false;
    for ($i = 0; $i < count($argv); ) {
        $a = $argv[$i];
        if ($a === '--keys') { $keysPath = $argv[$i + 1] ?? ''; $i += 2; }
        elseif ($a === '--prev-seq') { $anchor['prev_seq'] = (int)($argv[$i + 1] ?? 0); $i += 2; }
        elseif ($a === '--prev-hash') { $anchor['prev_hash'] = $argv[$i + 1] ?? ''; $i += 2; }
        elseif ($a === '--json') { $asJson = true; $i++; }
        elseif ($a === '--filtered') { $filtered = true; $i++; }
        elseif ($a === '--vectors') { $vec = $argv[$i + 1] ?? ''; $i += 2; }
        else { $files[] = $a; $i++; }
    }
    if ($vec !== null) return run_vectors($vec);
    $ci = array_search('--canon-hashes', $argv, true);
    if ($ci !== false) { foreach (read_json($argv[$ci + 1]) as $e) echo hash('sha256', canonical($e)), "\n"; return 0; }   // test aid
    // older form: entries.json public-key.json
    if (count($files) === 2 && $keysPath === 'public-key.json' && !file_exists('public-key.json') && is_array(@json_decode(@file_get_contents($files[1]), true)) && isset(json_decode(file_get_contents($files[1]), true)['keys'])) { $keysPath = $files[1]; $files = [$files[0]]; }
    if (!$files) { fwrite(STDERR, "Usage: php verify-record.php [--keys public-key.json] [--prev-seq N --prev-hash HEX] [--filtered] [--json] page1.json [page2.json ...]\n"); return 2; }
    try {
        $keysDoc = read_json($keysPath);
        $pages = array_map('read_json', $files);
        $rep = verify_stream($pages, $keysDoc, $anchor ?: null, $filtered);
    } catch (Unreadable $ex) { fwrite(STDERR, 'Could not read input: ' . $ex->getMessage() . "\n"); return 2; }
    if ($asJson) { if (!$rep['derived']['revoked']) $rep['derived']['revoked'] = new stdClass();   // an empty map must print as {} like the other verifiers, not []
        echo json_encode($rep, JSON_PRETTY_PRINT | JSON_UNESCAPED_SLASHES | JSON_UNESCAPED_UNICODE), "\n"; }
    else {
        echo $rep['entries'] . ' entries; ' . ($rep['ok'] ? 'no problems found' : count($rep['problems']) . ' problem(s)') . "\n";
        foreach ($rep['problems'] as $p) printf("  PROBLEM %-24s seq %s  %s\n", $p['code'], $p['seq'] ?? 'null', $p['detail']);
        foreach ($rep['notes'] as $n) if ($n['code'] !== 'unchained_entry') printf("  note    %-24s seq %s\n", $n['code'], $n['seq'] ?? 'null');
        if ($rep['derived']['revoked']) echo '  revoked entries (seq: revoked by status seq): ' . json_encode($rep['derived']['revoked']) . "\n";
    }
    return $rep['ok'] ? 0 : 1;
}

if (PHP_SAPI === 'cli' && realpath($_SERVER['SCRIPT_FILENAME'] ?? '') === realpath(__FILE__)) exit(main($argv));