//! Experimental permissioned-data primitives for `com.atproto.space.*`.
//!
//! Keep protocol mechanics here so the experimental LtHash, signed-commit,
//! delegation-token, and space-credential code does not sprawl through stable PDS
//! auth, repo, or sync modules.

const std = @import("std");
const clock = @import("../core/clock.zig");
const zat = @import("zat");

const Blake3 = std.crypto.hash.Blake3;
const HkdfSha256 = std.crypto.kdf.hkdf.HkdfSha256;
const HmacSha256 = std.crypto.auth.hmac.sha2.HmacSha256;
const Sha256 = std.crypto.hash.sha2.Sha256;

pub const lthash_lanes = 1024;
pub const lthash_lane_bytes = 2;
pub const lthash_state_bytes = lthash_lanes * lthash_lane_bytes;
pub const commit_hash_bytes = Sha256.digest_length;

pub const LtHash = struct {
    bytes: [lthash_state_bytes]u8 = @splat(0),

    pub fn fromBytes(bytes: []const u8) !LtHash {
        if (bytes.len != lthash_state_bytes) return error.InvalidLtHashState;
        var hash: LtHash = .{};
        @memcpy(&hash.bytes, bytes);
        return hash;
    }

    pub fn add(self: *LtHash, element: []const u8) void {
        var expanded = expandElement(element);
        self.apply(&expanded, .add);
    }

    pub fn remove(self: *LtHash, element: []const u8) void {
        var expanded = expandElement(element);
        self.apply(&expanded, .remove);
    }

    pub fn digest(self: *const LtHash) [commit_hash_bytes]u8 {
        var out: [commit_hash_bytes]u8 = undefined;
        Sha256.hash(&self.bytes, &out, .{});
        return out;
    }

    pub fn equals(self: *const LtHash, other: *const LtHash) bool {
        return std.mem.eql(u8, &self.bytes, &other.bytes);
    }

    fn apply(self: *LtHash, expanded: *const [lthash_state_bytes]u8, op: enum { add, remove }) void {
        var lane: usize = 0;
        while (lane < lthash_lanes) : (lane += 1) {
            const offset = lane * lthash_lane_bytes;
            const current = std.mem.readInt(u16, self.bytes[offset..][0..2], .little);
            const incoming = std.mem.readInt(u16, expanded[offset..][0..2], .little);
            const next = switch (op) {
                .add => current +% incoming,
                .remove => current -% incoming,
            };
            std.mem.writeInt(u16, self.bytes[offset..][0..2], next, .little);
        }
    }
};

pub const SpaceContext = struct {
    space: []const u8,
    author: []const u8,
    rev: []const u8,
};

pub const SignedCommit = struct {
    ver: u8 = 1,
    hash: [32]u8,
    mac: [32]u8,
    ikm: [32]u8,
    sig: [64]u8,
    rev: []const u8,
};

pub const RepoRecordBlock = struct {
    path: []const u8,
    cid: zat.cbor.Cid,
    data: []const u8,
};

pub const VerifiedRepo = struct {
    arena: std.heap.ArenaAllocator,
    commit: SignedCommit,
    records: []const RepoRecordBlock,

    pub fn deinit(self: *VerifiedRepo) void {
        self.arena.deinit();
    }
};

pub const DelegationToken = struct {
    requester_did: []const u8,
    authority_did: []const u8,
    space: []const u8,
    jti: []const u8,
    exp: i64,
};

pub const SpaceCredential = struct {
    authority_did: []const u8,
    space: []const u8,
    holder_key: []const u8,
    jti: []const u8,
    client_id: ?[]const u8,
    exp: f64,
};

pub fn recordElement(allocator: std.mem.Allocator, collection: []const u8, rkey: []const u8, cid: []const u8) ![]const u8 {
    return std.fmt.allocPrint(allocator, "{s}/{s}/{s}", .{ collection, rkey, cid });
}

pub fn createCommit(
    allocator: std.mem.Allocator,
    io: std.Io,
    state: []const u8,
    ctx: SpaceContext,
    keypair: *const zat.Keypair,
) !SignedCommit {
    const lthash = try LtHash.fromBytes(state);
    var ikm: [32]u8 = undefined;
    io.random(&ikm);
    const context = try commitContext(allocator, ctx, &ikm);
    defer allocator.free(context);
    const mac = commitMac(&ikm, context, &lthash.digest());
    const sig = try keypair.sign(context);
    return .{
        .hash = lthash.digest(),
        .mac = mac,
        .ikm = ikm,
        .sig = sig.bytes,
        .rev = ctx.rev,
    };
}

pub fn signedCommitJson(allocator: std.mem.Allocator, commit: SignedCommit) ![]const u8 {
    const hash = try base64Bytes(allocator, &commit.hash);
    defer allocator.free(hash);
    const mac = try base64Bytes(allocator, &commit.mac);
    defer allocator.free(mac);
    const ikm = try base64Bytes(allocator, &commit.ikm);
    defer allocator.free(ikm);
    const sig = try base64Bytes(allocator, &commit.sig);
    defer allocator.free(sig);
    return std.fmt.allocPrint(
        allocator,
        "{{\"ver\":{d},\"hash\":{{\"$bytes\":{f}}},\"mac\":{{\"$bytes\":{f}}},\"ikm\":{{\"$bytes\":{f}}},\"sig\":{{\"$bytes\":{f}}},\"rev\":{f}}}",
        .{ commit.ver, std.json.fmt(hash, .{}), std.json.fmt(mac, .{}), std.json.fmt(ikm, .{}), std.json.fmt(sig, .{}), std.json.fmt(commit.rev, .{}) },
    );
}

pub fn serializeRepoCar(
    allocator: std.mem.Allocator,
    commit: SignedCommit,
    records: []const RepoRecordBlock,
) ![]u8 {
    const commit_value: zat.cbor.Value = .{ .map = &.{
        .{ .key = "ver", .value = .{ .unsigned = commit.ver } },
        .{ .key = "hash", .value = .{ .bytes = &commit.hash } },
        .{ .key = "mac", .value = .{ .bytes = &commit.mac } },
        .{ .key = "ikm", .value = .{ .bytes = &commit.ikm } },
        .{ .key = "sig", .value = .{ .bytes = &commit.sig } },
        .{ .key = "rev", .value = .{ .text = commit.rev } },
    } };
    const commit_bytes = try zat.cbor.encodeAlloc(allocator, commit_value);
    const commit_cid = try zat.cbor.Cid.forDagCbor(allocator, commit_bytes);

    const index_entries = try allocator.alloc(zat.cbor.Value.MapEntry, records.len);
    for (records, 0..) |record, idx| {
        const computed = try zat.cbor.Cid.forDagCbor(allocator, record.data);
        if (!std.mem.eql(u8, computed.raw, record.cid.raw)) return error.RecordCidMismatch;
        index_entries[idx] = .{ .key = record.path, .value = .{ .cid = record.cid } };
    }
    std.mem.sort(zat.cbor.Value.MapEntry, index_entries, {}, canonicalMapKeyLessThan);
    for (index_entries[1..], index_entries[0..index_entries.len -| 1]) |current, previous| {
        if (std.mem.eql(u8, previous.key, current.key)) return error.DuplicateRecordPath;
    }
    const index_bytes = try zat.cbor.encodeAlloc(allocator, .{ .map = index_entries });
    const index_cid = try zat.cbor.Cid.forDagCbor(allocator, index_bytes);

    const blocks = try allocator.alloc(zat.car.Block, records.len + 2);
    blocks[0] = .{ .cid_raw = commit_cid.raw, .data = commit_bytes };
    blocks[1] = .{ .cid_raw = index_cid.raw, .data = index_bytes };
    for (records, 0..) |record, idx| {
        blocks[idx + 2] = .{ .cid_raw = record.cid.raw, .data = record.data };
    }
    return zat.car.writeAlloc(allocator, .{
        .roots = &.{ commit_cid, index_cid },
        .blocks = blocks,
    });
}

/// Check a full-state permissioned repo CAR's consistency and signed context.
/// Deniable commits do not prove record authorship: anyone holding a commit can
/// replace its records and recompute the hash and MAC without the signing key.
/// Content provenance requires a trusted source, such as an authenticated fetch
/// from the author's resolved repo host; this function does not establish it.
/// The returned value owns its data and must be deinitialized by the caller.
pub fn verifyRepoCarFull(
    allocator: std.mem.Allocator,
    car_bytes: []const u8,
    ctx: struct { space: []const u8, author: []const u8 },
    author_did_key: []const u8,
) !VerifiedRepo {
    var arena = std.heap.ArenaAllocator.init(allocator);
    errdefer arena.deinit();
    const a = arena.allocator();
    const owned_car = try a.dupe(u8, car_bytes);
    // Full-state exports routinely exceed the generic commit-CAR block cap.
    // The input is already resident in memory, so derive a structural ceiling
    // from its byte length: every CAR block consumes at least a length byte and
    // a minimally encoded CID.
    const max_blocks = owned_car.len / 5 + 1;
    const car = try zat.car.readWithOptions(a, owned_car, .{
        .max_size = owned_car.len,
        .max_blocks = max_blocks,
    });
    if (car.roots.len != 2 or car.blocks.len < 2) return error.InvalidRepoCar;
    if (!std.mem.eql(u8, car.roots[0].raw, car.blocks[0].cid_raw)) return error.InvalidRepoCar;
    if (!std.mem.eql(u8, car.roots[1].raw, car.blocks[1].cid_raw)) return error.InvalidRepoCar;

    const commit_value = try zat.cbor.decodeAll(a, car.blocks[0].data);
    if (commit_value.getUint("ver") != 1) return error.InvalidRepoCommit;
    const hash = commit_value.getBytes("hash") orelse return error.InvalidRepoCommit;
    const mac = commit_value.getBytes("mac") orelse return error.InvalidRepoCommit;
    const ikm = commit_value.getBytes("ikm") orelse return error.InvalidRepoCommit;
    const sig = commit_value.getBytes("sig") orelse return error.InvalidRepoCommit;
    const rev = commit_value.getString("rev") orelse return error.InvalidRepoCommit;
    if (hash.len != 32 or mac.len != 32 or ikm.len != 32 or sig.len != 64) return error.InvalidRepoCommit;

    var commit: SignedCommit = .{
        .hash = undefined,
        .mac = undefined,
        .ikm = undefined,
        .sig = undefined,
        .rev = try a.dupe(u8, rev),
    };
    @memcpy(&commit.hash, hash);
    @memcpy(&commit.mac, mac);
    @memcpy(&commit.ikm, ikm);
    @memcpy(&commit.sig, sig);

    const context = try commitContext(a, .{
        .space = ctx.space,
        .author = ctx.author,
        .rev = commit.rev,
    }, &commit.ikm);
    try zat.multicodec.verifyDidKeySignature(a, author_did_key, context, &commit.sig);

    const index = try zat.cbor.decodeAll(a, car.blocks[1].data);
    const entries = switch (index) {
        .map => |map| map,
        else => return error.InvalidRepoIndex,
    };
    if (car.blocks.len != entries.len + 2) return error.InvalidRepoCar;

    const records = try a.alloc(RepoRecordBlock, entries.len);
    var set_hash: LtHash = .{};
    for (entries, 0..) |entry, idx| {
        const cid = switch (entry.value) {
            .cid => |value| value,
            else => return error.InvalidRepoIndex,
        };
        const slash = std.mem.indexOfScalar(u8, entry.key, '/') orelse return error.InvalidRepoPath;
        if (std.mem.indexOfScalar(u8, entry.key[slash + 1 ..], '/') != null) return error.InvalidRepoPath;
        const collection = entry.key[0..slash];
        const rkey = entry.key[slash + 1 ..];
        if (zat.Nsid.parse(collection) == null or zat.Rkey.parse(rkey) == null) return error.InvalidRepoPath;

        const block = car.blocks[idx + 2];
        if (!std.mem.eql(u8, cid.raw, block.cid_raw)) return error.InvalidRepoCar;
        const record = try zat.cbor.decodeAll(a, block.data);
        if (record != .map) return error.InvalidRepoRecord;

        const cid_text = try cid.toString(a);
        set_hash.add(try recordElement(a, collection, rkey, cid_text));
        records[idx] = .{ .path = entry.key, .cid = cid, .data = block.data };
    }
    if (!std.mem.eql(u8, &set_hash.digest(), &commit.hash)) return error.InvalidRepoIndex;
    const expected_mac = commitMac(&commit.ikm, context, &commit.hash);
    if (!std.crypto.timing_safe.eql([32]u8, expected_mac, commit.mac)) return error.InvalidRepoCommit;

    return .{ .arena = arena, .commit = commit, .records = records };
}

fn base64Bytes(allocator: std.mem.Allocator, bytes: []const u8) ![]const u8 {
    const encoded = try allocator.alloc(u8, std.base64.standard.Encoder.calcSize(bytes.len));
    _ = std.base64.standard.Encoder.encode(encoded, bytes);
    return encoded;
}

pub fn createDelegationToken(
    allocator: std.mem.Allocator,
    io: std.Io,
    requester_did: []const u8,
    authority_did: []const u8,
    space: []const u8,
    keypair: *const zat.Keypair,
) ![]const u8 {
    const iat = unixNow();
    const exp = iat + 60;
    const jti = try randomTokenId(allocator, io);
    defer allocator.free(jti);
    const header = try std.fmt.allocPrint(allocator, "{{\"typ\":\"atproto-space-delegation+jwt\",\"alg\":\"{s}\",\"kid\":\"#atproto\"}}", .{@tagName(keypair.algorithm())});
    defer allocator.free(header);
    const audience = try std.fmt.allocPrint(allocator, "{s}#atproto_space_host", .{authority_did});
    defer allocator.free(audience);
    const payload = try std.fmt.allocPrint(
        allocator,
        "{{\"iss\":{f},\"aud\":{f},\"sub\":{f},\"iat\":{d},\"exp\":{d},\"jti\":{f}}}",
        .{ std.json.fmt(requester_did, .{}), std.json.fmt(audience, .{}), std.json.fmt(space, .{}), iat, exp, std.json.fmt(jti, .{}) },
    );
    defer allocator.free(payload);
    return zat.oauth.createJwt(allocator, header, payload, keypair);
}

pub fn createSpaceCredential(
    allocator: std.mem.Allocator,
    io: std.Io,
    authority_did: []const u8,
    space: []const u8,
    holder_key: []const u8,
    client_id: ?[]const u8,
    keypair: *const zat.Keypair,
) ![]const u8 {
    const iat = unixNow();
    const exp = iat + 600;
    const jti = try randomTokenId(allocator, io);
    defer allocator.free(jti);
    const header = try std.fmt.allocPrint(allocator, "{{\"typ\":\"atproto-space-credential+jwt\",\"alg\":\"{s}\",\"kid\":\"#atproto\"}}", .{@tagName(keypair.algorithm())});
    defer allocator.free(header);
    const payload = if (client_id) |client|
        try std.fmt.allocPrint(
            allocator,
            "{{\"iss\":{f},\"sub\":{f},\"cnf\":{{\"kid\":{f}}},\"client_id\":{f},\"iat\":{d},\"exp\":{d},\"jti\":{f}}}",
            .{ std.json.fmt(authority_did, .{}), std.json.fmt(space, .{}), std.json.fmt(holder_key, .{}), std.json.fmt(client, .{}), iat, exp, std.json.fmt(jti, .{}) },
        )
    else
        try std.fmt.allocPrint(
            allocator,
            "{{\"iss\":{f},\"sub\":{f},\"cnf\":{{\"kid\":{f}}},\"iat\":{d},\"exp\":{d},\"jti\":{f}}}",
            .{ std.json.fmt(authority_did, .{}), std.json.fmt(space, .{}), std.json.fmt(holder_key, .{}), iat, exp, std.json.fmt(jti, .{}) },
        );
    defer allocator.free(payload);
    return zat.oauth.createJwt(allocator, header, payload, keypair);
}

pub fn verifyDelegationToken(allocator: std.mem.Allocator, token: []const u8, public_key_multibase: []const u8) !DelegationToken {
    const parsed = try parseAndVerifyJwt(allocator, token, public_key_multibase, "atproto-space-delegation+jwt", &.{"#atproto"});
    defer parsed.deinit();
    const exp = zat.json.getInt(parsed.payload.value, "exp") orelse return error.InvalidJwt;
    if (exp < unixNow()) return error.ExpiredJwt;
    const audience = zat.json.getString(parsed.payload.value, "aud") orelse return error.InvalidJwt;
    const authority_did = authorityDidFromAudience(audience) orelse return error.InvalidJwt;
    return .{
        .requester_did = try allocator.dupe(u8, zat.json.getString(parsed.payload.value, "iss") orelse return error.InvalidJwt),
        .authority_did = try allocator.dupe(u8, authority_did),
        .space = try allocator.dupe(u8, zat.json.getString(parsed.payload.value, "sub") orelse return error.InvalidJwt),
        .jti = try allocator.dupe(u8, zat.json.getString(parsed.payload.value, "jti") orelse return error.InvalidJwt),
        .exp = exp,
    };
}

pub fn verifySpaceCredential(allocator: std.mem.Allocator, token: []const u8, public_key_multibase: []const u8) !SpaceCredential {
    const parsed = try parseAndVerifyJwt(allocator, token, public_key_multibase, "atproto-space-credential+jwt", &.{ "#atproto", "#atproto_space" });
    defer parsed.deinit();
    const exp = numericDate(parsed.payload.value, "exp") orelse return error.InvalidJwt;
    const iat = numericDate(parsed.payload.value, "iat") orelse return error.InvalidJwt;
    const jti = zat.json.getString(parsed.payload.value, "jti") orelse return error.InvalidJwt;
    if (jti.len == 0 or exp <= iat or exp - iat > 3600 or iat > @as(f64, @floatFromInt(unixNow() + 5))) return error.InvalidJwt;
    if (exp <= @as(f64, @floatFromInt(unixNow() - 5))) return error.ExpiredJwt;
    const holder_key = zat.json.getString(parsed.payload.value, "cnf.kid") orelse return error.InvalidJwt;
    const key = zat.multicodec.parseDidKey(allocator, holder_key) catch return error.InvalidJwt;
    defer allocator.free(key.raw);
    if (key.key_type != .p256) return error.InvalidJwt;
    return .{
        .jti = try allocator.dupe(u8, jti),
        .authority_did = try allocator.dupe(u8, zat.json.getString(parsed.payload.value, "iss") orelse return error.InvalidJwt),
        .space = try allocator.dupe(u8, zat.json.getString(parsed.payload.value, "sub") orelse return error.InvalidJwt),
        .holder_key = try allocator.dupe(u8, zat.json.getString(parsed.payload.value, "cnf.kid") orelse return error.InvalidJwt),
        .client_id = if (zat.json.getString(parsed.payload.value, "client_id")) |client_id| try allocator.dupe(u8, client_id) else null,
        .exp = exp,
    };
}

fn numericDate(payload: std.json.Value, name: []const u8) ?f64 {
    const value = zat.json.getPath(payload, name) orelse return null;
    const number: f64 = switch (value) {
        .integer => |n| @floatFromInt(n),
        .float => |n| n,
        else => return null,
    };
    return if (std.math.isFinite(number)) number else null;
}

fn authorityDidFromAudience(audience: []const u8) ?[]const u8 {
    const suffix = "#atproto_space_host";
    if (!std.mem.endsWith(u8, audience, suffix)) return null;
    const authority_did = audience[0 .. audience.len - suffix.len];
    if (zat.Did.parse(authority_did) == null) return null;
    return authority_did;
}

pub fn unverifiedStringClaim(allocator: std.mem.Allocator, token: []const u8, claim: []const u8) ![]const u8 {
    return unverifiedStringPart(allocator, token, 1, claim);
}

pub fn unverifiedHeaderString(allocator: std.mem.Allocator, token: []const u8, name: []const u8) ![]const u8 {
    return unverifiedStringPart(allocator, token, 0, name);
}

fn unverifiedStringPart(allocator: std.mem.Allocator, token: []const u8, part_index: usize, name: []const u8) ![]const u8 {
    var parts: [3][]const u8 = undefined;
    var part_count: usize = 0;
    var it = std.mem.splitScalar(u8, token, '.');
    while (it.next()) |part| {
        if (part_count >= 3) return error.InvalidJwt;
        parts[part_count] = part;
        part_count += 1;
    }
    if (part_count != 3) return error.InvalidJwt;
    const json = try zat.jwt.base64UrlDecode(allocator, parts[part_index]);
    defer allocator.free(json);
    const parsed = try std.json.parseFromSlice(std.json.Value, allocator, json, .{});
    defer parsed.deinit();
    return allocator.dupe(u8, zat.json.getString(parsed.value, name) orelse return error.InvalidJwt);
}

fn expandElement(element: []const u8) [lthash_state_bytes]u8 {
    var hasher = Blake3.init(.{});
    hasher.update(element);
    var out: [lthash_state_bytes]u8 = undefined;
    hasher.final(&out);
    return out;
}

const ParsedJwt = struct {
    allocator: std.mem.Allocator,
    header: std.json.Parsed(std.json.Value),
    payload: std.json.Parsed(std.json.Value),
    signature: []u8,
    signed_input: []const u8,

    fn deinit(self: ParsedJwt) void {
        self.header.deinit();
        self.payload.deinit();
        self.allocator.free(self.signature);
    }
};

fn parseAndVerifyJwt(allocator: std.mem.Allocator, token: []const u8, public_key_multibase: []const u8, expected_typ: []const u8, allowed_kids: []const []const u8) !ParsedJwt {
    var parts: [3][]const u8 = undefined;
    var part_count: usize = 0;
    var it = std.mem.splitScalar(u8, token, '.');
    while (it.next()) |part| {
        if (part_count >= 3) return error.InvalidJwt;
        parts[part_count] = part;
        part_count += 1;
    }
    if (part_count != 3) return error.InvalidJwt;
    const signed_input = token[0 .. parts[0].len + 1 + parts[1].len];

    const header_json = try zat.jwt.base64UrlDecode(allocator, parts[0]);
    defer allocator.free(header_json);
    const payload_json = try zat.jwt.base64UrlDecode(allocator, parts[1]);
    defer allocator.free(payload_json);
    const header = try std.json.parseFromSlice(std.json.Value, allocator, header_json, .{});
    errdefer header.deinit();
    const payload = try std.json.parseFromSlice(std.json.Value, allocator, payload_json, .{});
    errdefer payload.deinit();
    const signature = try zat.jwt.base64UrlDecode(allocator, parts[2]);
    errdefer allocator.free(signature);
    if (signature.len != 64) return error.InvalidJwt;

    const typ = zat.json.getString(header.value, "typ") orelse return error.InvalidJwt;
    if (!std.mem.eql(u8, typ, expected_typ)) return error.InvalidJwt;
    const kid = zat.json.getString(header.value, "kid") orelse return error.InvalidJwt;
    var kid_allowed = false;
    for (allowed_kids) |allowed| {
        if (std.mem.eql(u8, kid, allowed)) {
            kid_allowed = true;
            break;
        }
    }
    if (!kid_allowed) return error.InvalidJwt;
    const alg_text = zat.json.getString(header.value, "alg") orelse return error.InvalidJwt;
    const alg = zat.jwt.Algorithm.fromString(alg_text) orelse return error.InvalidJwt;
    const key_bytes = try zat.multibase.decode(allocator, public_key_multibase);
    defer allocator.free(key_bytes);
    const parsed_key = try zat.multicodec.parsePublicKey(key_bytes);
    switch (alg) {
        .ES256K => if (parsed_key.key_type != .secp256k1) return error.InvalidJwt,
        .ES256 => if (parsed_key.key_type != .p256) return error.InvalidJwt,
    }
    try zat.jwt.verifyJose(alg, signed_input, signature, parsed_key.raw);
    return .{ .allocator = allocator, .header = header, .payload = payload, .signature = signature, .signed_input = signed_input };
}

fn randomTokenId(allocator: std.mem.Allocator, io: std.Io) ![]const u8 {
    var bytes: [16]u8 = undefined;
    io.random(&bytes);
    return zat.jwt.base64UrlEncode(allocator, &bytes);
}

fn unixNow() i64 {
    return clock.nowSeconds();
}

fn commitMac(ikm: *const [32]u8, context: []const u8, hash: *const [32]u8) [32]u8 {
    var derived: [32]u8 = undefined;
    HkdfSha256.expand(&derived, context, ikm.*);
    var out: [32]u8 = undefined;
    HmacSha256.create(&out, hash, &derived);
    return out;
}

fn canonicalMapKeyLessThan(_: void, left: zat.cbor.Value.MapEntry, right: zat.cbor.Value.MapEntry) bool {
    if (left.key.len != right.key.len) return left.key.len < right.key.len;
    return std.mem.order(u8, left.key, right.key) == .lt;
}

fn commitContext(allocator: std.mem.Allocator, ctx: SpaceContext, ikm: *const [32]u8) ![]const u8 {
    var out: std.Io.Writer.Allocating = .init(allocator);
    try out.writer.writeAll("atproto-space-v1");
    try writeInfoField(&out.writer, ctx.space);
    try writeInfoField(&out.writer, ctx.author);
    try writeInfoField(&out.writer, ctx.rev);
    try writeInfoField(&out.writer, ikm);
    return out.toOwnedSlice();
}

fn writeInfoField(writer: *std.Io.Writer, value: []const u8) !void {
    if (value.len > std.math.maxInt(u16)) return error.FieldTooLong;
    var len: [2]u8 = undefined;
    std.mem.writeInt(u16, &len, @intCast(value.len), .big);
    try writer.writeAll(&len);
    try writer.writeAll(value);
}

test "LtHash locks empty digest" {
    const hash: LtHash = .{};
    try std.testing.expectEqualStrings(
        "e5a00aa9991ac8a5ee3109844d84a55583bd20572ad3ffcd42792f3c36b183ad",
        &std.fmt.bytesToHex(hash.digest(), .lower),
    );
}

test "LtHash add remove and ordering" {
    var first: LtHash = .{};
    var second: LtHash = .{};
    first.add("alpha");
    first.add("beta");
    second.add("beta");
    second.add("alpha");
    try std.testing.expect(first.equals(&second));
    first.remove("alpha");
    first.remove("beta");
    const empty: LtHash = .{};
    try std.testing.expect(first.equals(&empty));
}

test "permissioned repo CAR has commit and index roots followed by sorted records" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    const first_data = try zat.cbor.encodeAlloc(allocator, .{ .map = &.{
        .{ .key = "$type", .value = .{ .text = "fm.example.note" } },
        .{ .key = "text", .value = .{ .text = "first" } },
    } });
    const second_data = try zat.cbor.encodeAlloc(allocator, .{ .map = &.{
        .{ .key = "$type", .value = .{ .text = "fm.example.note" } },
        .{ .key = "text", .value = .{ .text = "second" } },
    } });
    const first_cid = try zat.cbor.Cid.forDagCbor(allocator, first_data);
    const second_cid = try zat.cbor.Cid.forDagCbor(allocator, second_data);
    const first_cid_text = try zat.multibase.base32lower.encode(allocator, first_cid.raw);
    const second_cid_text = try zat.multibase.base32lower.encode(allocator, second_cid.raw);

    var state: LtHash = .{};
    state.add(try recordElement(allocator, "fm.example.note", "one", first_cid_text));
    state.add(try recordElement(allocator, "fm.example.note", "two", second_cid_text));
    var keypair = try zat.Keypair.fromSecretKey(.p256, @splat(0x21));
    const commit = try createCommit(allocator, std.Options.debug_io, &state.bytes, .{
        .space = "at://did:plc:alice/space/fm.example.private/self",
        .author = "did:plc:alice",
        .rev = "3mrepoexporttest",
    }, &keypair);
    const records = [_]RepoRecordBlock{
        .{ .path = "fm.example.note/one", .cid = first_cid, .data = first_data },
        .{ .path = "fm.example.note/two", .cid = second_cid, .data = second_data },
    };
    const bytes = try serializeRepoCar(allocator, commit, &records);
    const car = try zat.car.read(allocator, bytes);
    try std.testing.expectEqual(@as(usize, 2), car.roots.len);
    try std.testing.expectEqual(@as(usize, 4), car.blocks.len);
    try std.testing.expectEqualSlices(u8, car.roots[0].raw, car.blocks[0].cid_raw);
    try std.testing.expectEqualSlices(u8, car.roots[1].raw, car.blocks[1].cid_raw);
    try std.testing.expectEqualSlices(u8, first_cid.raw, car.blocks[2].cid_raw);
    try std.testing.expectEqualSlices(u8, second_cid.raw, car.blocks[3].cid_raw);

    const decoded_commit = try zat.cbor.decodeAll(allocator, car.blocks[0].data);
    try std.testing.expectEqualSlices(u8, &state.digest(), decoded_commit.getBytes("hash").?);
    try std.testing.expectEqualStrings("3mrepoexporttest", decoded_commit.getString("rev").?);
    const index = try zat.cbor.decodeAll(allocator, car.blocks[1].data);
    try std.testing.expectEqualSlices(u8, first_cid.raw, index.get("fm.example.note/one").?.cid.raw);
    try std.testing.expectEqualSlices(u8, second_cid.raw, index.get("fm.example.note/two").?.cid.raw);
}

test "verifies a permissioned repo CAR produced by the reference implementation" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    // Generated by @atproto/space at bluesky-social/atproto PR 5187 commit
    // 14e3ed0ec5219c58e33eb66a3efe049a3bf2b78f, via pds.js' two-way
    // space-reference harness.
    const encoded = std.mem.trim(u8, @embedFile("testdata/space-reference-repo.car.base64"), "\r\n");
    const car_bytes = try allocator.alloc(u8, try std.base64.standard.Decoder.calcSizeForSlice(encoded));
    try std.base64.standard.Decoder.decode(car_bytes, encoded);

    var verified = try verifyRepoCarFull(
        allocator,
        car_bytes,
        .{
            .space = "at://did:plc:refauthority/space/com.example.forum/general",
            .author = "did:plc:refuser",
        },
        "did:key:zDnaefkZms3Qkc8zrfsujwKN9dBm9gVPJNpm342aJKkZxUbru",
    );
    defer verified.deinit();

    try std.testing.expectEqualStrings("3mrxrefrevaaa", verified.commit.rev);
    try std.testing.expectEqual(@as(usize, 4), verified.records.len);
    try std.testing.expectEqualStrings("com.e.p/x", verified.records[0].path);
    try std.testing.expectEqualStrings("com.example.post/aaa", verified.records[1].path);
    try std.testing.expectEqualStrings("com.example.post/bbb", verified.records[2].path);
    try std.testing.expectEqualStrings("com.example.reply/zz", verified.records[3].path);

    var rejected_wrong_space = false;
    if (verifyRepoCarFull(
        allocator,
        car_bytes,
        .{
            .space = "at://did:plc:refauthority/space/com.example.forum/other",
            .author = "did:plc:refuser",
        },
        "did:key:zDnaefkZms3Qkc8zrfsujwKN9dBm9gVPJNpm342aJKkZxUbru",
    )) |bad| {
        var unexpected = bad;
        unexpected.deinit();
    } else |_| {
        rejected_wrong_space = true;
    }
    try std.testing.expect(rejected_wrong_space);
}

test "permissioned repo CAR permits record substitution without the author's signing key" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    const encoded = std.mem.trim(u8, @embedFile("testdata/space-reference-repo.car.base64"), "\r\n");
    const car_bytes = try allocator.alloc(u8, try std.base64.standard.Decoder.calcSizeForSlice(encoded));
    try std.base64.standard.Decoder.decode(car_bytes, encoded);
    const ctx = .{
        .space = "at://did:plc:refauthority/space/com.example.forum/general",
        .author = "did:plc:refuser",
    };
    const author_key = "did:key:zDnaefkZms3Qkc8zrfsujwKN9dBm9gVPJNpm342aJKkZxUbru";
    var original = try verifyRepoCarFull(allocator, car_bytes, .{ .space = ctx.space, .author = ctx.author }, author_key);
    defer original.deinit();

    const replacement = try zat.cbor.encodeAlloc(allocator, .{ .map = &.{
        .{ .key = "$type", .value = .{ .text = "com.example.post" } },
        .{ .key = "text", .value = .{ .text = "replacement by a reader" } },
    } });
    const cid = try zat.cbor.Cid.forDagCbor(allocator, replacement);
    const records = [_]RepoRecordBlock{
        .{ .path = "com.example.post/aaa", .cid = cid, .data = replacement },
    };
    var state: LtHash = .{};
    state.add(try recordElement(allocator, "com.example.post", "aaa", try cid.toString(allocator)));

    var substituted = original.commit;
    substituted.hash = state.digest();
    try std.testing.expect(!std.mem.eql(u8, &original.commit.hash, &substituted.hash));
    const stale_mac_car = try serializeRepoCar(allocator, substituted, &records);
    try std.testing.expectError(error.InvalidRepoCommit, verifyRepoCarFull(allocator, stale_mac_car, .{ .space = ctx.space, .author = ctx.author }, author_key));

    const context = try commitContext(allocator, .{
        .space = ctx.space,
        .author = ctx.author,
        .rev = substituted.rev,
    }, &substituted.ikm);
    substituted.mac = commitMac(&substituted.ikm, context, &substituted.hash);
    const substituted_car = try serializeRepoCar(allocator, substituted, &records);
    var accepted = try verifyRepoCarFull(allocator, substituted_car, .{ .space = ctx.space, .author = ctx.author }, author_key);
    defer accepted.deinit();

    try std.testing.expectEqualSlices(u8, &original.commit.sig, &accepted.commit.sig);
    try std.testing.expectEqualSlices(u8, &original.commit.ikm, &accepted.commit.ikm);
    try std.testing.expectEqualStrings(original.commit.rev, accepted.commit.rev);
    try std.testing.expectEqual(@as(usize, 1), accepted.records.len);
    try std.testing.expectEqualSlices(u8, replacement, accepted.records[0].data);
}

test "permissioned commit MAC uses HKDF expand without extract" {
    var ikm: [32]u8 = undefined;
    var hash: [32]u8 = undefined;
    for (&ikm, 0..) |*byte, idx| byte.* = @intCast(idx);
    for (&hash, 0..) |*byte, idx| byte.* = @intCast(idx + 32);
    const mac = commitMac(&ikm, "atproto-space-test-context", &hash);
    const expected = "5f162f35ca2a0ad567359c92d907c5c30e15be7db0b8c786fd5bc79074f02369";
    try std.testing.expectEqualStrings(expected, &std.fmt.bytesToHex(mac, .lower));
}

test "permissioned repo CAR canonicalizes index keys by encoded length" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const allocator = arena.allocator();
    const data = try zat.cbor.encodeAlloc(allocator, .{ .map = &.{
        .{ .key = "$type", .value = .{ .text = "fm.example.note" } },
    } });
    const cid = try zat.cbor.Cid.forDagCbor(allocator, data);
    const commit: SignedCommit = .{
        .hash = @splat(0),
        .mac = @splat(0),
        .ikm = @splat(0),
        .sig = @splat(0),
        .rev = "3mcanonicalmap",
    };
    const records = [_]RepoRecordBlock{
        .{ .path = "longer/path", .cid = cid, .data = data },
        .{ .path = "z/x", .cid = cid, .data = data },
    };
    const bytes = try serializeRepoCar(allocator, commit, &records);
    const car = try zat.car.read(allocator, bytes);
    const index = try zat.cbor.decodeAll(allocator, car.blocks[1].data);
    try std.testing.expectEqualStrings("z/x", index.map[0].key);
    try std.testing.expectEqualStrings("longer/path", index.map[1].key);
}

test "LtHash snapshot vector" {
    var hash: LtHash = .{};
    hash.add("atproto");
    hash.add("space");
    const expected =
        "34a3d4a5e9f4ae93fdb1580c14a8e8013342cd303117862c89ec906b462706aaaa26ffa4ae4159c4c6c2b81cc0fa83582d7c05c31ae64e302284dd1bfccad846c94b2e9b4d704b9d21cf8953d28610f5a0af710c99958f107a28a3b1a71017ebd47a14e184d95ca4affc534cba38882b46a6e52350c836ad7b5374246bf354f52dcff8b7dae5255b410b70ed5dfd54ac94ffa083dfb3708c9d923190399a65d108ef05d7ec928e98bbf865f1229a1b497ec09458a9a08d17631a4fa28dc96d384748d544660b116e25066b5b012f7d94fe6e1e8f4b45e9588523a714390e1f61f6a65f21b4e230973b055ae371cd697f4d2733ee0bdf20fde6e934b222cf065ed61a765f09ab8332d36bcaffedaaff483c4f0ba19c2c684e3f1744b073e89ab901d208e0bcf60f9918b820bbb5bb005085d7e2e71df2ad4be0c2d879cce17ea2a46e9d71ef9708715b0a5f34680cb8977f13d9082b141d9638df35eafce0693845a4ab810fd213bbd0dbd12e74d5297e11c9f601df603eb357d80669eacb97051df757a500b16d0edacc8d556e108430e868eae78312985110b20692a3738300221d361d30d02274d662b22808f381564aa966f117383e6b923663dd28c1cca46b8099938fde309ce91a7e99b188f152db7e691752757cf897883be25cf0a9fda51106e6c735f55ff9e77cad2cd8f5041d0c746175eddeb70762efec9604d31254e9ddd9ded2b186e45b40010d595068b94cfb7017553986402646424038fb06cd0d91711caccee3a1e53a1b6849e5b61bb6bc432a1466f3c2bfb9c2503e02e3c8dade31afa7c57b50adb9fbe95706bfec45036a16664184ce3ef4c906b161a640f64708b12c6361f1fab2c14f3fa25281c1cc722b3913a5cdcbfe91690ff98096809271cdf9b9f814d6644227a3d80b4bfd195f352755ae89bc79329d7aa11eed4321b2fffaf7c1a927c394fd59508815ed3881dbf5a17b23e26aa8ea2bb5f0b3c9b207007a96eb1638d499bb211f594cfe0420457b1c0cf827ea14629324c07c087e71509b22dbdcfe2c985e4539c096df8fc02ffe932bf28d68df58abe162eca7683a41f85203d11d9d6decfe157139814b259f2f94fda2fc2f4527e94bd56c0bbfe5344befac7213eaf3acff4cd7148d95ad6babc3381d2abf97b4526787378579519c362e7692817ca885c967f003a65fb76cbcdfe8dd90c48c298c5e2935364957cf3b9a5bfb73a1534341e5fe8c9dc5f9a15afee4fdd2c7d5b6b2cd50112c83bf7901b28575e162fd91565153a2e165f8cc6d0bab13ce0b910eadbc9aff9316531d1fc15bb8aba1f94e0178a43e5935dffaa7d00fa7c57439074f1ae95ef7aa34f76a6d797c722a76ffcf5aeb69bf7490a7237935091e86517201d24d8a68a24bf0c606322a91a34650765151e56bf355f89aeb14bb598d1b1bb19e5508d5d0452117bfec1da43c3533c9cc350ec68f898dc4ff7360a6246f3fd0263fa0aa759699bb29e1f6935b59df39df0f46633b83e3f4cf420a4a9a1ea3331f2b0168007d1f58e40e2b7cb1e5da28477be11f3cdf8798660023bcef29b4c057398a8f7f96c61f2ea983e91a8dc3b4dc9dfba9c50d9060d5618e10cc5bac7bbb6517466c4b112dd9b642a80297f48d2aa3fd231663f508a065bf73e35f7d39c5095330ef8b6b25df0a08e43cfd3d278b5151a845f8e9fd7c1e52a8338716b1f2275a7279a0245e3d5e1de68f0f15d4ac73476a368dc9d8544fc082c11995b80c9ea5812ad2bcc9510d9e1a56d0441fb0cfe0350e5e90dcde9dfb5f174d1639d53c4c42253133fed45e6da16b9da15defe621d27bcfb7a61224474390b5756f1ca7565ae81477793a8c3607aede9ee5805d5b69d67cdb9036f4931f2d4c04df415111dc4f0d143d101fb85a653e940a85a3aee71b8941fe2191dfdbc0a4d4cc7fce6e4ac91aa3f9c679afc0e6314ed492ab1ff9d105f1f0b967a13a45c56b27f66e01376bcdedab1c2ef7e3aa38a37ba7a8fef22682ab8e58e24ae1c6236c365f4198b8de1cf5a052623e6f8c2073b0c3efa464dd435986fd80e0afeea36b0fb1b06c6b1e58b40673563cbe45434defb3b194e3e481896847236cb91154d2badda206655e5be4f36f97ccc38cfca49a66fd1be468ba97dec7ff7f56b37d77d1acd345d2f3e4143643bd4c6f6ac904aa34cc2eb39b16e89d8367a8579821f143804b20f15427224db7618f4bef582c9607a4603022bbfc156f54a85199cc05781c844e517a9074f4037e292ffe74f8c4d923b2a220d6b2da1e91822fd574081a0244e5de9007b358311ffc1f02f7133076302790b71e1f73116ee0dc6fd95290bf1fda2a1c0ebeb669f2d03cda8dc3e817d9e2893f9bd193e4d5908ed4f080452686e8a2a84374a0f678823ead2d8d1f45b245d338955503803471cb732d1f00369e989c016cd718a63a5e3454cf505c69d546ba3da3d8d7fc049d2b7d980a5c7a44bce02d23ad056d9cbe4d61d690c0c7afd3d1d80c3b1a5daf31a2acd4d00de7090b2531c0c9e3a999eca6bd69982328235a65466578469ab96f5aff8d8016d893e92bc3aaf8e603e9910f83b5519953bdbd0c1d94e0cae48889c4d37ac53f47f3d9d340ace07a657b052b800960f79d08e01032759796103e037e1c8af7c1373d953ad50c28cfbbefd0ac3ef1287a7d3efeb3e7416925e21d2122937d39460699945407cb6962f2f31824989510f91c8c558b58b7f09ddccb4c21a3977bb6332a962edbffb86e0a743c217ab39d18125be525cba097ed98895c827246b9e3fa1e965003cf6e919122969b8635051a3ceeeaf9fb45adee52543a2e61c0f75a4ca62c7af10498117fcfb7f296c54176a3b2a1f83c124495afdbcb85dcb0abb2b46c";
    try std.testing.expectEqualStrings(expected, &std.fmt.bytesToHex(hash.bytes, .lower));
}

test "delegation token and space credential round trip" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var keypair = try zat.Keypair.fromSecretKey(.p256, .{
        0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
        0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
        0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38,
        0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40,
    });
    const did_key = try keypair.did(allocator);
    const public_key_multibase = did_key["did:key:".len..];

    const delegation_token = try createDelegationToken(
        allocator,
        std.Options.debug_io,
        "did:plc:requester",
        "did:plc:spaceauthority",
        "at://did:plc:spaceauthority/space/fm.plyr.privateMedia/self",
        &keypair,
    );
    const delegation = try verifyDelegationToken(allocator, delegation_token, public_key_multibase);
    try std.testing.expectEqualStrings("did:plc:requester", delegation.requester_did);
    try std.testing.expectEqualStrings("did:plc:spaceauthority", delegation.authority_did);
    try std.testing.expectEqualStrings("at://did:plc:spaceauthority/space/fm.plyr.privateMedia/self", delegation.space);

    const credential_token = try createSpaceCredential(
        allocator,
        std.Options.debug_io,
        "did:plc:spaceauthority",
        delegation.space,
        try keypair.did(allocator),
        "https://client.example",
        &keypair,
    );
    const credential = try verifySpaceCredential(allocator, credential_token, public_key_multibase);
    try std.testing.expectEqualStrings("did:plc:spaceauthority", credential.authority_did);
    try std.testing.expectEqualStrings(delegation.space, credential.space);
    try std.testing.expectEqualStrings(try keypair.did(allocator), credential.holder_key);
    try std.testing.expectEqualStrings("https://client.example", credential.client_id.?);

    try std.testing.expectError(error.InvalidJwt, verifySpaceCredential(allocator, delegation_token, public_key_multibase));
    try std.testing.expectError(error.InvalidJwt, verifyDelegationToken(allocator, credential_token, public_key_multibase));
}

test "space credential continuity depends on authority identity and key" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var authority_key = try zat.Keypair.fromSecretKey(.p256, @splat(0x31));
    const authority_did_key = try authority_key.did(allocator);
    const credential_token = try createSpaceCredential(
        allocator,
        std.Options.debug_io,
        "did:plc:portableauthority",
        "at://did:plc:portableauthority/space/fm.example.group/main",
        authority_did_key,
        "https://reader.example",
        &authority_key,
    );

    // A credential names the stable authority DID and space coordinate, not
    // the authority's current service endpoint. Moving #atproto_space_host
    // therefore does not invalidate an already-issued credential.
    const verified = try verifySpaceCredential(
        allocator,
        credential_token,
        authority_did_key["did:key:".len..],
    );
    try std.testing.expectEqualStrings("did:plc:portableauthority", verified.authority_did);

    var replacement_key = try zat.Keypair.fromSecretKey(.p256, @splat(0x32));
    const replacement_did_key = try replacement_key.did(allocator);
    try std.testing.expectError(
        error.SignatureVerificationFailed,
        verifySpaceCredential(allocator, credential_token, replacement_did_key["did:key:".len..]),
    );
}

test "space credential lifetime boundaries are enforced" {
    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    var key = try zat.Keypair.fromSecretKey(.p256, @splat(0x42));
    const kid = try key.did(a);
    const header = "{\"typ\":\"atproto-space-credential+jwt\",\"alg\":\"ES256\",\"kid\":\"#atproto\"}";
    const now = unixNow();
    const cases = [_]struct { iat: i64, exp: i64, id: []const u8, valid: bool }{
        .{ .iat = now, .exp = now + 600, .id = "one", .valid = true },
        .{ .iat = now, .exp = now + 3600, .id = "two", .valid = true },
        .{ .iat = now, .exp = now + 3601, .id = "three", .valid = false },
        .{ .iat = now, .exp = now, .id = "four", .valid = false },
        .{ .iat = now + 60, .exp = now + 600, .id = "five", .valid = false },
        .{ .iat = now, .exp = now + 600, .id = "", .valid = false },
    };
    for (cases) |case| {
        const payload = try std.fmt.allocPrint(a, "{{\"iss\":\"did:plc:alice\",\"sub\":\"at://did:plc:alice/space/test.space.type/self\",\"iat\":{d},\"exp\":{d},\"jti\":{f},\"cnf\":{{\"kid\":{f}}}}}", .{ case.iat, case.exp, std.json.fmt(case.id, .{}), std.json.fmt(kid, .{}) });
        const token = try zat.oauth.createJwt(a, header, payload, &key);
        if (case.valid) {
            _ = try verifySpaceCredential(a, token, kid[8..]);
        } else try std.testing.expectError(error.InvalidJwt, verifySpaceCredential(a, token, kid[8..]));
    }
}