Artifact 1e359c5805c0daf124efecae9d1b93533a8a6e05c2b2775a55309195d07578bb:
- File
src/artifact.zig
— part of check-in
[9033c13f21]
at
2026-09-17 17:04:25
on branch trunk
— Remove issue-tracker numbers from source and documents
The tracker is disposable and does not live with the source, so a number is a dangling pointer. Every zit#NN and #NN reference in code comments, test names, help text, smoke labels, identifiers, release notes and errata is replaced by enough context to stand alone, or by a short plain statement of the problem. No behaviour changed. (user: dmestas, size: 239867) [annotate] [blame] [check-ins using]
//! Artifact Format — draft-fossil-artifact-format-00. //! //! An artifact is an immutable byte sequence named by the lowercase-hex hash //! of its content (Section 3). Structural artifacts are line-oriented "cards". //! This module owns the canonical vocabulary for the whole suite: naming, the //! card grammar, the structural types, and the two checksums (Z, R). //! //! Scope note: zit targets the version-control substrate — the check-in //! (manifest), cluster, and tag/control artifact types. The collaboration //! types (wiki, ticket, forum, attachment, technote) are carried opaquely. const std = @import("std"); const rfc_vectors = @import("rfc_vectors.zig"); const cone_mod = @import("cone.zig"); const partition = @import("submanifest_partition.zig"); /// Card-type letters. Only the version-control cards are interpreted; others /// are recognised syntactically and otherwise carried opaquely. pub const CardType = enum(u8) { B = 'B', // baseline (delta manifest) C = 'C', // comment D = 'D', // date (mtime) F = 'F', // file M = 'M', // cluster member N = 'N', // mimetype P = 'P', // parent(s) Q = 'Q', // cherrypick R = 'R', // aggregate content checksum (MD5) T = 'T', // tag U = 'U', // user Z = 'Z', // artifact self-checksum (MD5), always last }; /// Structural artifact types (§5.1 Table 3, extended by /// draft-fossil-submanifests-00 §4.1 with code 9). Every structural artifact /// classifies as exactly one of these nine; the backing integer is the /// stable numeric code from Table 3. Code 0 ("not yet determined") is not /// a variant here -- it is a transient parser state modelled as the /// absence of an `ArtifactType` value (`?ArtifactType`), never as a value /// of this enum (§5.1-m1). pub const ArtifactType = enum(u8) { manifest = 1, // a check-in cluster = 2, // a set of artifact hashes (sync housekeeping) control = 3, // a tag/branch mutation wiki = 4, ticket = 5, attachment = 6, event = 7, // a technote forum = 8, // a forum post submanifest = 9, // a slice of a check-in's file set (submanifests §4.1) /// §5.1 Table 3 external name -- the name emitted on machine-readable /// (JSON/API) surfaces. Distinct from the informative diagnostic /// vocabulary the RFC explicitly declines to normatize (manifest and /// "forum post" with a space); that vocabulary is not implemented. pub fn externalName(self: ArtifactType) []const u8 { return switch (self) { .manifest => "checkin", .cluster => "cluster", .control => "tag", .wiki => "wiki", .ticket => "ticket", .attachment => "attachment", .event => "technote", .forum => "forumpost", .submanifest => "submanifest", }; } /// §5.1 informative diagnostic vocabulary — the human-facing type name a /// plumbing verb SHOWS (contracts/artifact.md B-artifact-1/-2). Distinct /// from `externalName` (the machine/JSON surface): `control` reads /// `control` here (B-artifact-2 pins it, overriding Table 3's `tag`), /// `manifest` keeps its own spelling, and `forum` is the two-word "forum /// post" the §5.1 note calls out. The blob (code-0 "file") label has no /// `ArtifactType` value and is owned by the CLI, not this map. pub fn diagnosticName(self: ArtifactType) []const u8 { return switch (self) { .manifest => "manifest", .cluster => "cluster", .control => "control", .wiki => "wiki", .ticket => "ticket", .attachment => "attachment", .event => "technote", .forum => "forum post", .submanifest => "submanifest", }; } }; /// Hash algorithm that names an artifact (Section 3, Section 7 hash policy). /// The canonical (writer) form is always lowercase hex. pub const HashAlgo = enum { sha1, sha3_256 }; /// Compute the artifact name: the lowercase-hex hash of `content`. /// Writes into `out` and returns the populated slice (40 hex for SHA-1, /// 64 hex for SHA3-256). pub fn artifactName(algo: HashAlgo, content: []const u8, out: *[64]u8) []u8 { switch (algo) { .sha1 => { var digest: [20]u8 = undefined; std.crypto.hash.Sha1.hash(content, &digest, .{}); const hex = std.fmt.bytesToHex(digest, .lower); @memcpy(out[0..hex.len], &hex); return out[0..hex.len]; }, .sha3_256 => { var digest: [32]u8 = undefined; std.crypto.hash.sha3.Sha3_256.hash(content, &digest, .{}); const hex = std.fmt.bytesToHex(digest, .lower); @memcpy(out[0..hex.len], &hex); return out[0..hex.len]; }, } } /// submanifests §6.1 partition predicate: the number of leading zero bits of /// PH(name), "the SHA3-256 digest of a decoded filename -- the byte string /// ordered by the canonical comparator, with no terminator and no /// transformation". /// /// There is deliberately no algorithm, granularity, or salt parameter: /// "The digest algorithm, the bit granularity, and the input bytes are fixed /// and MUST NOT be configurable or negotiable per artifact." The repository /// hash policy (§7) names artifacts; it never reaches this predicate, which is /// why "the same name set MUST partition identically under either hash policy" /// (§6.2) holds by construction rather than by a test. /// /// The result is 0..256 inclusive (an all-zero digest is representable, if /// unreachable), so the return type is wider than the 8 bits a single octet /// contributes. pub fn zbits(name: []const u8) u16 { var digest: [32]u8 = undefined; std.crypto.hash.sha3.Sha3_256.hash(name, &digest, .{}); var n: u16 = 0; for (digest) |b| { // bound: 32 iterations if (b != 0) { std.debug.assert(n + @clz(b) < 256); return n + @clz(b); } n += 8; } std.debug.assert(n == 256); return n; } /// Length-to-algorithm dispatch (§3.2-m1). The two name lengths are disjoint, /// so length alone fully determines the algorithm: 40 hex digits is SHA-1, /// 64 is SHA3-256, any other length names nothing. pub fn nameAlgo(len: usize) ?HashAlgo { return switch (len) { 40 => .sha1, 64 => .sha3_256, else => null, }; } /// ABNF `lhexdig` (§3.5): a lowercase hex digit, 0-9 or a-f. Governs the /// canonical (writer/parse) form only. fn isHexLower(c: u8) bool { return (c >= '0' and c <= '9') or (c >= 'a' and c <= 'f'); } /// ABNF `hexdig-ci` (§3.5): 0-9, A-F, or a-f. Used only on the prefix-lookup /// path (§3.6), which canonicalizes case; the parse path never uses this. fn isHexCi(c: u8) bool { return (c >= '0' and c <= '9') or (c >= 'a' and c <= 'f') or (c >= 'A' and c <= 'F'); } /// Canonical-form validation (§3.2, §3.3, §3.5 `artifact-name`). A token is /// valid iff it is exactly 40 or 64 lowercase hex digits. Length is checked /// before character class (§3.2-r1: length gate precedes char-class check). /// Uppercase digits are rejected outright, never case-normalized (§3.3-m2). pub fn validateName(token: []const u8) bool { if (nameAlgo(token.len) == null) return false; std.debug.assert(token.len == 40 or token.len == 64); var i: usize = 0; while (i < token.len) : (i += 1) { if (!isHexLower(token[i])) return false; } return true; } /// Verify `name` against `content` (§3.4). Dispatch on length picks the /// digest to recompute; the compare is exact byte-for-byte lowercase hex. /// Wrong length, non-hex characters, and a digest mismatch collapse into the /// same `false` (§3.4-m1) — nothing here distinguishes them for the caller. /// An uppercase name never verifies either, since the compare never /// case-folds (§3.4-r1). pub fn verify(name: []const u8, content: []const u8) bool { const algo = nameAlgo(name.len) orelse return false; var buf: [64]u8 = undefined; const computed = artifactName(algo, content, &buf); std.debug.assert(computed.len == name.len); return std.mem.eql(u8, name, computed); } // --------------------------------------------------------------------------- // Section 7 -- Hash Policy // --------------------------------------------------------------------------- // // Pure primitives only. The repository inventory scan (which names exist), // the persisted policy setting, and the store-lookup used for // deduplication are all effectful and belong to the store/repostate layer; // this module models §7's decisions as total functions over injected // booleans and lengths. /// §7.1 Table 7 hash-policy values. The backing integer is the ordinal /// column: "0 through 4, in the order listed" (§7.1-w1). pub const HashPolicy = enum(u3) { sha1 = 0, auto = 1, sha3 = 2, sha3_only = 3, shun_sha1 = 4 }; /// §7.1 Table 7 "Value" column -- the one comptime source of truth for the /// wire strings, shared by `policyName` (encode) and `policyFromString` /// (parse) so the five spellings are never transcribed twice. const policy_value_string = std.EnumArray(HashPolicy, []const u8).init(.{ .sha1 = "sha1", .auto = "auto", .sha3 = "sha3", .sha3_only = "sha3-only", .shun_sha1 = "shun-sha1", }); /// Encode a policy as its Table 7 value string. pub fn policyName(p: HashPolicy) []const u8 { return policy_value_string.get(p); } /// Parse a Table 7 value string. Matching is case-sensitive and exact /// (§7.1-p1); an unrecognized value is `null`, which the caller treats as /// fatal (§7.1-r1). Bounded by the fixed 5-entry policy table. pub fn policyFromString(s: []const u8) ?HashPolicy { for (std.enums.values(HashPolicy)) |tag| { if (std.mem.eql(u8, s, policy_value_string.get(tag))) return tag; } return null; } /// §7.1 Table 7 "Primary hash" column: the algorithm that names newly /// stored content under `p`. pub fn primaryHash(p: HashPolicy) HashAlgo { return switch (p) { .sha1, .auto => .sha1, // §7.1-m1 .sha3, .sha3_only, .shun_sha1 => .sha3_256, // §7.1-m2 }; } /// §7.1 Table 7 "Alternative hash" column. `null` means the policy /// disallows the alternative hash outright: a request for it MUST fail /// with an empty result, never a hash value (§7.1-r2). pub fn alternativeHash(p: HashPolicy) ?HashAlgo { return switch (p) { .sha1, .auto => .sha3_256, // §7.1-m3 .sha3 => .sha1, // §7.1-m3 .sha3_only, .shun_sha1 => null, // §7.1-r2 }; } /// §7.2 default-policy derivation for a repository with no assigned hash- /// policy setting. `has_sha1_named`/`has_sha3_named` are the caller's /// inventory-scan result (a name over 40 hex digits is SHA3-named, exactly /// 40 is SHA1-named -- see `nameAlgo`). pub fn defaultPolicy(has_sha1_named: bool, has_sha3_named: bool) HashPolicy { // §7.2-m1: any SHA3 name, or no SHA-1 name at all (including empty). const r: HashPolicy = if (has_sha3_named or !has_sha1_named) .sha3 else .auto; // §7.2-m2 otherwise std.debug.assert(r == .sha3 or r == .auto); // §7.2-m3: never shun-sha1 return r; } /// §7.3 set-time coercion of an explicit policy assignment. Only `auto` is /// ever rewritten, and only when a SHA3 name already exists (§7.3-m2, /// "set-time coercion"); every other requested value -- including an /// explicit demotion back to `sha1` -- passes through unchanged (§7.3-m1, /// "no demotion guard"). pub fn coerceAssignment(requested: HashPolicy, has_sha3_named: bool) HashPolicy { const r: HashPolicy = if (requested == .auto and has_sha3_named) .sha3 else requested; std.debug.assert(requested == .auto or r == requested); return r; } /// §7.4 ratchet decision for one content-storage write under `effective`. /// `selected_name` is the name already chosen for this write -- computed /// or caller-supplied (§7.4-m2, selection precedes the ratchet check). /// Promotion triggers only out of `auto`, and only once the selected name /// exceeds the 40-character SHA-1 length (§7.4-m1). pub fn ratchet(effective: HashPolicy, selected_name: []const u8) HashPolicy { std.debug.assert(nameAlgo(selected_name.len) != null); // a legal 40/64 name const r: HashPolicy = if (effective == .auto and selected_name.len > 40) .sha3 else effective; std.debug.assert(r == effective or (effective == .auto and r == .sha3)); return r; } /// §7.5 naming algorithm for content stored without an externally supplied /// name. `alternative_present` is the caller's store-lookup result for the /// alternative-algorithm hash. Tries the alternative first where the /// policy permits one, falling back to the primary hash on a miss -- /// which is also where sha3-only/shun-sha1 land, their disallowed /// alternative request absorbed silently as if it had missed (§7.5-p1, /// §7.5-r1). pub fn dedupNameAlgo(p: HashPolicy, alternative_present: bool) HashAlgo { const r: HashAlgo = blk: { if (alternativeHash(p)) |alt| { if (alternative_present) break :blk alt; } break :blk primaryHash(p); }; if (alternativeHash(p)) |alt| { std.debug.assert(r == primaryHash(p) or r == alt); } else { std.debug.assert(r == primaryHash(p)); } return r; } /// §4.7.1 hash-token position kinds. Every artifact-hash-bearing card /// position (A target/source, B, E id, F hash, G, I, M, P, Q, S hash, T /// target) maps to `.artifact_hash`; the two named exceptions get their own /// kind. The S hash joins the enumeration per draft-fossil-submanifests-00 /// §3.5, under the same 40-or-64 case-insensitive-hex rule as the rest. pub const HashTokenKind = enum { artifact_hash, ticket_id, checksum }; /// §4.7.1 Hash-Token Validation Map. Validates a RAW card token against the /// length/char-class policy for `kind`. Never escape-decodes (§4.7.1-m2); /// the sole carve-out is the A card target, which the future A-card parser /// decodes first and then feeds here as `.artifact_hash` (§4.3.1). pub fn validateHashToken(kind: HashTokenKind, token: []const u8) bool { switch (kind) { // 40 or 64 case-insensitive hex (§4.7.1-m1: "MUST be exactly 40 or // 64 case-insensitive hexadecimal characters"). This is a harder // requirement than the bare artifact-name arm (§3.3), where // rejecting uppercase is only a MAY — so this does not delegate to // validateName, which takes that MAY. Length gate precedes // char-class check (§3.2-r1). .artifact_hash => { if (nameAlgo(token.len) == null) return false; std.debug.assert(token.len == 40 or token.len == 64); for (token) |c| { if (!isHexCi(c)) return false; } return true; }, // Pinned to SHA-1 length; 64 is always invalid regardless of hash // policy (§4.7.1-r1). Canonical form is lowercase (§4.7.1: "MUST // emit lowercase"); a parser MAY accept upper- or lowercase, but // acceptance is optional, so this arm takes the stricter, // lowercase-only reading (the same MAY the artifact-name arm takes). .ticket_id => { if (token.len != 40) return false; std.debug.assert(token.len == 40); for (token) |c| { if (!isHexLower(c)) return false; } return true; }, // Exactly 32 hex, parse-accept case-insensitive (§4.7.1-r2, §6.1 // md5-token = 32hexdig-ci). .checksum => { if (token.len != 32) return false; std.debug.assert(token.len == 32); for (token) |c| { if (!isHexCi(c)) return false; } return true; }, } } /// Prefix-resolution outcome (§3.6, informative — not part of the wire /// format). `one` carries the matching index into the caller's `names`. pub const Resolution = union(enum) { none, one: usize, ambiguous }; /// Resolve a hex name or prefix against a candidate universe (§3.6). /// `prefix` must be 4-64 hex characters of any case; it is lowercased before /// matching (the lookup path canonicalizes case, unlike the parse path — /// see `validateName`). One query walk covers both name lengths, so a /// cross-algorithm collision (one 40-char match, one 64-char match) reports /// `.ambiguous` exactly like a same-algorithm collision (§3.6-r1). pub fn resolvePrefix(prefix: []const u8, names: []const []const u8) error{InvalidPrefix}!Resolution { if (prefix.len < 4 or prefix.len > 64) return error.InvalidPrefix; std.debug.assert(prefix.len >= 4 and prefix.len <= 64); var lowered: [64]u8 = undefined; var i: usize = 0; while (i < prefix.len) : (i += 1) { const c = prefix[i]; if (!isHexCi(c)) return error.InvalidPrefix; lowered[i] = if (c >= 'A' and c <= 'F') c + ('a' - 'A') else c; } const query = lowered[0..prefix.len]; var first: ?usize = null; var matches: usize = 0; var n: usize = 0; while (n < names.len) : (n += 1) { std.debug.assert(matches <= names.len); if (std.mem.startsWith(u8, names[n], query)) { matches += 1; if (first == null) first = n; if (matches > 1) return .ambiguous; } } if (first) |idx| { std.debug.assert(idx < names.len); return .{ .one = idx }; } return .none; } /// The Z-card value: lowercase-hex MD5 of all stripped-content bytes that /// precede the `Z ` line (Section 6, Z card). pub fn selfChecksum(stripped_prefix: []const u8, out: *[32]u8) []u8 { var digest: [16]u8 = undefined; std.crypto.hash.Md5.hash(stripped_prefix, &digest, .{}); const hex = std.fmt.bytesToHex(digest, .lower); @memcpy(out, &hex); return out; } // --------------------------------------------------------------------------- // §6.3 R Card: Aggregate Content Checksum // --------------------------------------------------------------------------- /// §6.3.2 one tracked file's contribution to the R aggregate: pathname and /// raw content. The file's size (§6.3.2 step 2) is `content.len`. pub const TrackedFile = struct { name: []const u8, content: []const u8 }; /// Decimal digits needed for the largest representable `usize` size header /// (§6.3.2 step 2 bound): a 64-bit count needs at most 20 digits. const max_size_digits = 20; comptime { std.debug.assert(std.math.maxInt(u64) < std.math.pow(u128, 10, max_size_digits)); } /// Feed one file's §6.3.2 step-2 size header into the running MD5 context: /// a single space, then `size` as minimal decimal ASCII (no leading zeros, /// no sign, no separators -- §6.3.2-m1), then LF. Manual digit extraction /// into a bounded stack buffer avoids `bufPrint`'s `catch unreachable` /// (forbidden outside test code). fn updateSizeHeader(ctx: *std.crypto.hash.Md5, size: usize) void { var digits: [max_size_digits]u8 = undefined; var n_digits: usize = 0; var v = size; while (true) { std.debug.assert(n_digits < digits.len); digits[n_digits] = @as(u8, @intCast(v % 10)) + '0'; n_digits += 1; v /= 10; if (v == 0) break; } std.debug.assert(n_digits >= 1 and n_digits <= digits.len); // "0" for size 0 var header: [1 + max_size_digits + 1]u8 = undefined; var w: usize = 0; header[w] = ' '; w += 1; var i: usize = n_digits; while (i > 0) { i -= 1; std.debug.assert(w < header.len); header[w] = digits[i]; // most-significant digit first w += 1; } std.debug.assert(w < header.len); header[w] = '\n'; w += 1; std.debug.assert(w <= header.len); ctx.update(header[0..w]); } /// §6.3.2 aggregate in streaming form: one file's contribution at a time, so /// a verifier holding the file set but not the file *contents* (a checkout /// walk, or submanifests §5.6's whole-tree verification, which fetches each /// blob in turn) never has to materialize every content buffer at once. /// `aggregateChecksum` is this loop over a slice; the two cannot drift, /// because there is only one copy of the §6.3.2 per-file rule. /// /// Precondition: names arrive in §4.5.3 canonical ascending order, and each /// `name` stays valid until the next `update` or `final` (it is retained only /// for that ordering assertion). pub const ChecksumAggregator = struct { ctx: std.crypto.hash.Md5 = std.crypto.hash.Md5.init(.{}), prev: ?[]const u8 = null, /// §6.3.2 steps 1-3 for one tracked file: pathname, size header, content. pub fn update(self: *ChecksumAggregator, name: []const u8, content: []const u8) void { if (self.prev) |p| std.debug.assert(compareBytes(p, name) == .lt); self.ctx.update(name); updateSizeHeader(&self.ctx, content.len); self.ctx.update(content); self.prev = name; } /// Finalize into 32 lowercase hex bytes, returning the written slice. pub fn final(self: *ChecksumAggregator, out: *[32]u8) []u8 { var digest: [16]u8 = undefined; self.ctx.final(&digest); const hex = std.fmt.bytesToHex(digest, .lower); @memcpy(out, &hex); for (out) |c| std.debug.assert(isHexLower(c)); return out; } }; /// §6.3 R-card aggregate content checksum. Lowercase-hex MD5 over, for each /// tracked file in canonical filename order, name || SP || minimal-decimal /// (size) || LF || content (§6.3.2). `files` MUST already be in §4.5.3 /// canonical ascending order (the F-card ordering, §4.5.2) -- asserted, not /// sorted here (ordering is owned by manifest assembly; re-sorting here /// would duplicate that mechanism). Allocation-free; writes 32 lowercase hex /// bytes to `out` and returns the slice. Delta manifests (§6.3.3) resolve /// their merged file set in the caller before calling this, as does a tree /// manifest (submanifests §5.5, whose enumeration is the §5.1 walk). pub fn aggregateChecksum(files: []const TrackedFile, out: *[32]u8) []u8 { var agg: ChecksumAggregator = .{}; for (files) |f| agg.update(f.name, f.content); return agg.final(out); } // --------------------------------------------------------------------------- // §4.1.1 Signature-Wrapper Removal // --------------------------------------------------------------------------- /// PGP/SSH clearsign open-armor literals (§4.1.1-r1): stripping fires only /// when one of these matches the first 34 bytes of the input, at offset 0. const pgp_open_armor = "-----BEGIN PGP SIGNED MESSAGE-----"; const ssh_open_armor = "-----BEGIN SSH SIGNED MESSAGE-----"; comptime { std.debug.assert(pgp_open_armor.len == 34); std.debug.assert(ssh_open_armor.len == 34); } /// Trailing-armor compare literals (§4.1.1-p3). The real armor line is 30 /// bytes (LF + a 29-byte dashed literal), but only 29 are ever compared: /// LF plus the first 28 armor bytes, one dash short of the closing run — /// the 30th byte, whatever it is, is never read. const pgp_close_armor = "\n-----BEGIN PGP SIGNATURE----"; const ssh_close_armor = "\n-----BEGIN SSH SIGNATURE----"; comptime { std.debug.assert(pgp_close_armor.len == 29); std.debug.assert(ssh_close_armor.len == 29); } /// Forward scan for the first blank-line separator (§4.1.1-p2): LF LF or /// LF CR LF — the sole CR tolerance anywhere in the parse pipeline. Returns /// the offset just past the blank line (start of body), or null if none is /// found before end of input. fn firstBlankLineEnd(bytes: []const u8) ?usize { var i: usize = 0; while (i < bytes.len) : (i += 1) { if (bytes[i] != '\n') continue; if (i + 1 < bytes.len and bytes[i + 1] == '\n') return i + 2; if (i + 2 < bytes.len and bytes[i + 1] == '\r' and bytes[i + 2] == '\n') return i + 3; } return null; } /// Backward scan for the trailing signature armor (§4.1.1-p3). "First /// occurrence" read right-to-left makes the rightmost match win. Returns /// the truncation length (keeping the matched LF as the final byte), or /// `body.len` when no armor is found. fn trailingArmorEnd(body: []const u8) usize { if (body.len < pgp_close_armor.len) return body.len; var p: usize = body.len - pgp_close_armor.len; while (true) : (p -= 1) { std.debug.assert(p + pgp_close_armor.len <= body.len); const slice = body[p .. p + pgp_close_armor.len]; if (std.mem.eql(u8, slice, pgp_close_armor) or std.mem.eql(u8, slice, ssh_close_armor)) { return p + 1; // truncate here, keeping the matched LF } if (p == 0) break; } return body.len; } /// Whether `bytes` carries a §4.1.1 clearsign wrapper, i.e. whether /// stripping would remove anything. The stored artifact IS the wrapped text /// (its name hashes the wrapper), so this is a property of the bytes on /// disk, not of the manifest inside them; every reader already strips before /// interpreting, which is why carrying a signature costs the rest of the /// system nothing. pub fn isSignatureWrapped(bytes: []const u8) bool { return stripSignatureWrapper(bytes).len != bytes.len; } /// §4.1.1 signature-wrapper removal. Total: never fails. Returns `bytes` /// unchanged unless the first 34 bytes are a recognized open armor AND a /// blank line follows somewhere in the input — either condition failing /// leaves the input wholly unstripped (§4.1.1-r1, -m1). pub fn stripSignatureWrapper(bytes: []const u8) []const u8 { const is_pgp = bytes.len >= pgp_open_armor.len and std.mem.eql(u8, bytes[0..pgp_open_armor.len], pgp_open_armor); const is_ssh = bytes.len >= ssh_open_armor.len and std.mem.eql(u8, bytes[0..ssh_open_armor.len], ssh_open_armor); if (!is_pgp and !is_ssh) return bytes; const body_start = firstBlankLineEnd(bytes) orelse return bytes; std.debug.assert(body_start <= bytes.len); const body = bytes[body_start..]; const body_end = trailingArmorEnd(body); std.debug.assert(body_end <= body.len); const result = body[0..body_end]; std.debug.assert(result.len <= bytes.len); return result; } // --------------------------------------------------------------------------- // §4.1 Artifact Framing // --------------------------------------------------------------------------- /// §6.2 Z-card verification outcome (Table 6). pub const ZVerdict = enum { absent, match, mismatch }; /// §6.2 Z self-checksum, evaluated positionally on the final 35 bytes of /// `content` (already wrapper-stripped): the marker sits at n-35, the /// digest at n-33..n-1. Never reads `content[n-1]`, the artifact's /// terminating byte — that byte belongs to the §4.1 raw-LF framing rule. pub fn verifyZCard(content: []const u8) ZVerdict { const n = content.len; if (n < 35) return .absent; if (content[n - 35] != 'Z' or content[n - 34] != ' ') return .absent; const stored = content[n - 33 .. n - 1]; std.debug.assert(stored.len == 32); var digest_buf: [32]u8 = undefined; const computed = selfChecksum(content[0 .. n - 35], &digest_buf); std.debug.assert(computed.len == 32); return if (std.mem.eql(u8, stored, computed)) .match else .mismatch; } /// §4.1 framing gates, evaluated in RFC order before any card is /// interpreted. Returns the wrapper-stripped, gate-passed content, or null /// if the input fails any gate — every rejection reason collapses to null, /// as the RFC only ever says "reject" (the §4.1.2 fast well-formedness /// probe reads this way too). /// /// The final §4.1 rule — unconsumed bytes after the card loop MUST cause /// rejection — is not enforced here: it is defined relative to the card /// loop, one layer up. `parse` calls `frame` as its entry seam and enforces /// it structurally: the §4.4 order/§4.5.1 occurrence gates make a Z card /// (order-terminal, single-occurrence) refuse everything that could follow /// it, so trailing bytes past the last legitimate card always reject. pub fn frame(bytes: []const u8) ?[]const u8 { const stripped = frameNoZ(bytes) orelse return null; // Gate 4: Z self-checksum — a mismatch rejects; absent or matching pass. if (verifyZCard(stripped) == .mismatch) return null; return stripped; } /// §4.1 framing gates 1-3 ONLY — the wrapper-strip and line-1 gates, WITHOUT /// the §6.2 Z self-checksum gate (gate 4). The caller decides whether a Z /// mismatch rejects: `frame` re-adds gate 4 for the RFC-exact path; the /// read-window `parseWindow` deliberately omits it, so a Z-mismatched but /// otherwise structural artifact is still assembled and its mismatch REPORTED /// rather than demoted to a blob (contracts/artifact.md B-artifact-5). For /// every Z-absent or Z-matching input `frameNoZ` and `frame` agree exactly. pub fn frameNoZ(bytes: []const u8) ?[]const u8 { // Gate 1: raw bytes, non-empty, final byte LF — checked before strip. if (bytes.len == 0 or bytes[bytes.len - 1] != '\n') return null; // Gate 2: strip signature wrapper, if present. const stripped = stripSignatureWrapper(bytes); if (stripped.len > 0) std.debug.assert(stripped[stripped.len - 1] == '\n'); // Gate 3: strict line-1 (length, byte0 A-Z, byte1 SP). if (stripped.len < 10) return null; if (stripped[0] < 'A' or stripped[0] > 'Z') return null; if (stripped[1] != ' ') return null; return stripped; } // --------------------------------------------------------------------------- // §4.2 Line and Token Grammar / §4.2.2 Closed Card Alphabet // --------------------------------------------------------------------------- /// §4.2.2 closed alphabet, as revised by draft-fossil-submanifests-00 §3.1: /// true for exactly the 22 defined card letters. A-Z minus the four in-range /// gaps (O V X Y) — closed, no forward-compatibility path for an unknown /// letter. S is the 22nd letter (the sub-manifest reference, §3.6). /// /// Matched pair: this switch and `admitTokenized`'s per-letter dispatch must /// flip together. Admitting a letter here without a dispatch arm there is a /// runtime `unreachable` reachable from attacker bytes; no comptime guard /// spans the two, so the Appendix A vectors are the net that catches it. pub fn isCardLetter(b: u8) bool { return switch (b) { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'W', 'Z' => true, else => false, }; } comptime { var count: usize = 0; var b: usize = 0; while (b < 256) : (b += 1) { if (isCardLetter(@intCast(b))) count += 1; } std.debug.assert(count == 22); // submanifests §3.1 std.debug.assert(isCardLetter('S')); // submanifests §3.1: the 22nd letter std.debug.assert(!isCardLetter('O')); std.debug.assert(!isCardLetter('V')); std.debug.assert(!isCardLetter('X')); std.debug.assert(!isCardLetter('Y')); std.debug.assert(!isTokenByte(' ')); std.debug.assert(!isTokenByte('\n')); std.debug.assert(isTokenByte(0x00)); std.debug.assert(isTokenByte(0xFF)); } /// §4.2 tchar: any octet except SP (0x20) and LF (0x0A). pub fn isTokenByte(b: u8) bool { return b != ' ' and b != '\n'; } /// Splits a card's raw argument bytes on SP only (§4.2-m2 — tab is never a /// delimiter). `rest == null` yields zero tokens (argument-less card); /// `rest.?.len == 0` yields exactly one empty token (§4.7.17's "empty /// token" case) before going null. pub const TokenIterator = struct { rest: ?[]const u8, pub fn next(self: *TokenIterator) ?[]const u8 { const s = self.rest orelse return null; var i: usize = 0; while (i < s.len) : (i += 1) { if (s[i] == ' ') { self.rest = s[i + 1 ..]; return s[0..i]; } } self.rest = null; return s; } }; /// One tokenized card (§4.2 `card`). Borrows from the input; no allocation. pub const CardLine = struct { letter: u8, /// null => argument-less card (`X\n`), 0 tokens. /// slice => SP form (`X ...\n`); raw arg bytes with the LF and the one /// leading SP removed. May be "" (one empty token). args: ?[]const u8, pub fn tokens(self: CardLine) TokenIterator { return .{ .rest = self.args }; } }; /// Tokenize one card, given its full byte extent including the terminating /// LF (the card loop supplies the extent; W's byte-counted body is that /// loop's concern, not this function's — §4.7.18). Returns null iff the /// letter is outside the closed 21-letter alphabet (§4.2.2-r1,-r2) or the /// byte after the letter is neither SP nor LF (§4.2-m1). pub fn tokenizeCardLine(line: []const u8) ?CardLine { std.debug.assert(line.len >= 1); std.debug.assert(line[line.len - 1] == '\n'); // Non-W invariant: no embedded LF before the terminator. The W card's // byte-counted body is the sole exception (§4.7.18), realized by the // card loop, not here. var i: usize = 0; while (i < line.len - 1) : (i += 1) { std.debug.assert(line[i] != '\n'); } if (line.len < 2) return null; if (!isCardLetter(line[0])) return null; const result: CardLine = if (line[1] == '\n') .{ .letter = line[0], .args = null } else if (line[1] == ' ') .{ .letter = line[0], .args = line[2 .. line.len - 1] } else return null; std.debug.assert(isCardLetter(result.letter)); return result; } // --------------------------------------------------------------------------- // §4.4 Card Ordering // --------------------------------------------------------------------------- comptime { // Z is the last defined letter (§4.4 "Nothing follows Z", lines 739-741): // every card letter sorts at or below it. var b: usize = 0; while (b < 256) : (b += 1) { if (isCardLetter(@intCast(b))) std.debug.assert(b <= 'Z'); } // Premises the N-after-P exception rests on (lines 714-717, §A.1 2499-2500). std.debug.assert('N' < 'P'); std.debug.assert('E' < 'P'); // submanifests §3.4: "The inter-type ordering rule of [FossilArtifact], // Section 4.4 is unchanged; S falls between R and T, so a manifest's S // run precedes its T cards." Byte order already delivers that -- these // assertions pin the premise rather than adding a branch. std.debug.assert('R' < 'S'); std.debug.assert('S' < 'T'); } /// §4.4 card-type ordering, fed one accepted card letter at a time in /// document order. Holds the previous letter and whether a valid E card has /// been presented (the N-after-P technote exception, lines 714-717). pub const OrderState = struct { prev: ?u8 = null, e_seen: bool = false, /// Admit `letter` as the next card. Returns false iff it is out of /// order and not the N-after-P exception; the caller collapses false /// to reject, matching the module's "every rejection reason collapses /// to null/false" posture (§4.1). Pure predicate: no error set. pub fn admit(self: *OrderState, letter: u8) bool { std.debug.assert(isCardLetter(letter)); if (self.prev) |p| std.debug.assert(isCardLetter(p)); const ok = if (self.prev == null) true else if (letter >= self.prev.?) true else letter == 'N' and self.prev.? == 'P' and self.e_seen; if (!ok) return false; if (letter == 'E') self.e_seen = true; self.prev = letter; std.debug.assert(self.prev.? == letter); std.debug.assert(!(letter == 'E') or self.e_seen); return true; } }; // --------------------------------------------------------------------------- // §4.3 Character-Escape Encoding // --------------------------------------------------------------------------- /// §4.3 Table 1: the decoded octet for a recognized escape successor, or /// null for an unrecognized one. Exactly eight pairs are defined; every /// other successor byte falls through to `else`. fn escapeOctet(c: u8) ?u8 { return switch (c) { 'n' => 0x0A, // LF 's' => 0x20, // SP 't' => 0x09, // TAB 'r' => 0x0D, // CR 'v' => 0x0B, // VT 'f' => 0x0C, // FF '0' => 0x00, // NUL '\\' => 0x5C, // backslash else => null, }; } comptime { var count: usize = 0; var b: usize = 0; while (b < 256) : (b += 1) { if (escapeOctet(@intCast(b)) != null) count += 1; } std.debug.assert(count == 8); std.debug.assert(escapeOctet('n').? == 0x0A); std.debug.assert(escapeOctet('s').? == 0x20); std.debug.assert(escapeOctet('0').? == 0x00); std.debug.assert(escapeOctet('\\').? == 0x5C); } /// §4.3 in-place escape decode of one free-text token. Writes the decoded /// bytes into `out` and returns the used prefix. Never errors (§4.3: "No /// error is raised"). Precondition: `out.len >= token.len` — decoded length /// never exceeds input length (a recognized or unrecognized escape turns 2 /// input bytes into 1; an ordinary byte or a lone trailing backslash is 1:1, /// §4.3-amb1). pub fn decodeEscapes(token: []const u8, out: []u8) []u8 { std.debug.assert(out.len >= token.len); var i: usize = 0; var w: usize = 0; while (i < token.len) { std.debug.assert(w <= i); if (token[i] == '\\' and i + 1 < token.len) { out[w] = escapeOctet(token[i + 1]) orelse token[i + 1]; i += 2; } else { // Ordinary byte, or a backslash with no successor (§4.3-amb1): // pass through literally. out[w] = token[i]; i += 1; } w += 1; } std.debug.assert(w <= token.len); return out[0..w]; } /// §4.3 inverse of `escapeOctet`: the two-char escape successor for a raw /// octet that Table 1 names, or null for any other byte. Same eight pairs /// as `escapeOctet`, reversed. fn escapeSuccessor(c: u8) ?u8 { return switch (c) { 0x0A => 'n', // LF 0x20 => 's', // SP 0x09 => 't', // TAB 0x0D => 'r', // CR 0x0B => 'v', // VT 0x0C => 'f', // FF 0x00 => '0', // NUL 0x5C => '\\', // backslash else => null, }; } comptime { std.debug.assert(escapeSuccessor(0x0A).? == 'n'); std.debug.assert(escapeSuccessor(0x20).? == 's'); std.debug.assert(escapeSuccessor(0x00).? == '0'); std.debug.assert(escapeSuccessor(0x5C).? == '\\'); std.debug.assert(escapeSuccessor('x') == null); } /// §4.3 in-place escape ENCODE of one free-text token -- the writer-side /// inverse of `decodeEscapes`. Writes the encoded bytes into `out` and /// returns the used prefix: each of Table 1's eight named octets becomes /// the two-byte pair `\<succ>`; every other byte passes through verbatim. /// Precondition: `out.len >= 2 * token.len` -- an escaped byte doubles, /// nothing shrinks, so this bound is always sufficient. pub fn encodeEscapes(token: []const u8, out: []u8) []u8 { std.debug.assert(out.len >= 2 * token.len); var w: usize = 0; for (token) |c| { // bound: token.len iterations, each writes <= 2 bytes std.debug.assert(w <= 2 * token.len); if (escapeSuccessor(c)) |succ| { out[w] = '\\'; out[w + 1] = succ; w += 2; } else { out[w] = c; w += 1; } } std.debug.assert(w <= 2 * token.len); std.debug.assert(w >= token.len); return out[0..w]; } /// submanifests §6.2 CANONICAL encoding of one filename token: "exactly SP /// (0x20) as \s, LF (0x0A) as \n, and backslash (0x5C) as \\; every other /// octet, including the decoder's five other escape octets TAB, CR, VT, FF, /// and NUL ([FossilArtifact], Section 4.3), is emitted raw, and escaping it is /// non-canonical." `decodeEscapes` inverts it exactly -- the three pairs are a /// subset of Table 1's eight, and the five octets left raw are not `tchar` /// escape introducers, so nothing here round-trips ambiguously. /// /// Scoped on purpose: §6.2 names the positions this applies to -- "S card /// filenames and the filename and old-name tokens of leaf F cards" -- and /// those are the ONLY call sites. Every other emission position keeps /// `encodeEscapes`; widening this to the whole writer would respell existing /// filenames and so change the name of every artifact already stored. /// /// Precondition: `out.len >= 2 * token.len` -- the same bound `encodeEscapes` /// needs, since an escaped byte doubles and nothing shrinks. pub fn encodeCanonical(token: []const u8, out: []u8) []u8 { std.debug.assert(out.len >= 2 * token.len); var w: usize = 0; for (token) |c| { // bound: token.len iterations, each writes <= 2 bytes std.debug.assert(w <= 2 * token.len); switch (c) { 0x20, 0x0A, 0x5C => { out[w] = '\\'; out[w + 1] = escapeSuccessor(c).?; // 's', 'n', '\\' w += 2; }, else => { out[w] = c; w += 1; }, } } std.debug.assert(w <= 2 * token.len); std.debug.assert(w >= token.len); return out[0..w]; } // --------------------------------------------------------------------------- // §4.5 Occurrence Classes and Intra-Type Ordering // --------------------------------------------------------------------------- /// §4.5.1 occurrence class of a card letter (lines 753-766). `single`: a /// duplicate MUST be rejected. `repeatable`: each occurrence appends to the /// artifact's growing list for that type — a duplicate is never a syntax /// error. `neither`: the Z card only — no duplicate guard, no list. pub const OccurrenceClass = enum { single, repeatable, neither }; /// §4.5.1 classifier (lines 755-764). Precondition: `isCardLetter(letter)`. pub fn occurrenceClass(letter: u8) OccurrenceClass { std.debug.assert(isCardLetter(letter)); return switch (letter) { 'A', 'B', 'C', 'D', 'E', 'G', 'H', 'I', 'K', 'L', 'N', 'R', 'U', 'W' => .single, // submanifests §3.4: "S joins the repeatable occurrence class ... // which becomes: F, J, M, T, P, Q, S." 'F', 'J', 'M', 'T', 'P', 'Q', 'S' => .repeatable, 'Z' => .neither, else => unreachable, // isCardLetter admits only the 22 letters above }; } comptime { var single: usize = 0; var repeatable: usize = 0; var neither: usize = 0; var b: usize = 0; while (b < 256) : (b += 1) { if (!isCardLetter(@intCast(b))) continue; switch (occurrenceClass(@intCast(b))) { .single => single += 1, .repeatable => repeatable += 1, .neither => neither += 1, } } std.debug.assert(single == 14); std.debug.assert(repeatable == 7); // submanifests §3.4 adds S std.debug.assert(neither == 1); std.debug.assert(occurrenceClass('Z') == .neither); } /// §4.5.2 Table 2 intra-run check structure for a repeatable card's list /// (lines 789-809), as extended by draft-fossil-submanifests-00 §3.4. /// `ascending`: strict ascent by a single decoded key (F, J, M, and S — the /// key itself varies by letter, extracted by the caller). /// `tag_two_level`: T's (tag name, then target hash) rule. `unordered`: P /// (semantic order, lines 804-805) and Q (no check at all, lines 807-808). pub const IntraRunRule = enum { ascending, tag_two_level, unordered }; /// §4.5.2 Table 2 dispatch. Non-null iff `letter` is repeatable; null for /// every single-occurrence letter and for Z. Precondition: `isCardLetter`. pub fn intraRunRule(letter: u8) ?IntraRunRule { std.debug.assert(isCardLetter(letter)); return switch (letter) { // submanifests §3.4 Table row: "S | Strictly ascending by decoded // filename (equal or descending rejected)"; "The comparator is the // canonical comparator, as for the F card run." 'F', 'J', 'M', 'S' => .ascending, 'T' => .tag_two_level, 'P', 'Q' => .unordered, else => null, }; } comptime { var b: usize = 0; while (b < 256) : (b += 1) { if (!isCardLetter(@intCast(b))) continue; const letter: u8 = @intCast(b); const has_rule = intraRunRule(letter) != null; const is_repeatable = occurrenceClass(letter) == .repeatable; std.debug.assert(has_rule == is_repeatable); } std.debug.assert(intraRunRule('F').? == .ascending); std.debug.assert(intraRunRule('J').? == .ascending); std.debug.assert(intraRunRule('M').? == .ascending); std.debug.assert(intraRunRule('S').? == .ascending); // submanifests §3.4 std.debug.assert(intraRunRule('T').? == .tag_two_level); std.debug.assert(intraRunRule('P').? == .unordered); std.debug.assert(intraRunRule('Q').? == .unordered); std.debug.assert(intraRunRule('Z') == null); } /// §4.5.1-r1 duplicate guard, fed one accepted card letter at a time. /// Fixed 26-slot membership set indexed by `letter - 'A'` — a card letter is /// always in A..Z (`isCardLetter`), so 26 slots cover every case with no /// dynamic sizing. pub const SingleOccurrenceSet = struct { seen: [26]bool = .{false} ** 26, /// Admit `letter` as an occurrence. Returns false iff `letter` is /// single-occurrence and this is its second-or-later appearance; /// repeatable letters and Z are always admitted (§4.5.1-m1, §4.5.2-m3, /// the Z paragraph at lines 764-766). pub fn admit(self: *SingleOccurrenceSet, letter: u8) bool { std.debug.assert(isCardLetter(letter)); if (occurrenceClass(letter) != .single) return true; const idx = letter - 'A'; std.debug.assert(idx < 26); if (self.seen[idx]) return false; self.seen[idx] = true; std.debug.assert(self.seen[idx]); return true; } }; /// §4.5.3 the canonical comparator (lines 823-836): raw-byte comparison, /// octets as unsigned values (u8 is already unsigned), locale-independent, /// no Unicode normalization, no case folding. On a common-prefix tie the /// shorter string sorts first (§4.5.3-m1). No byte value — including `/` /// 0x2F — gets special treatment (§4.5.3-m2): there is no branch for it. pub fn compareBytes(a: []const u8, b: []const u8) std.math.Order { const n = @min(a.len, b.len); var i: usize = 0; while (i < n) : (i += 1) { // n = min(a.len, b.len), so this is what actually justifies the // unchecked a[i] / b[i] below — not a restatement of `i < n`. std.debug.assert(i < a.len and i < b.len); if (a[i] != b[i]) return std.math.order(a[i], b[i]); } return std.math.order(a.len, b.len); } comptime { std.debug.assert(compareBytes("A", "a") == .lt); // no case folding std.debug.assert(compareBytes("abc", "abcd") == .lt); // shorter-first std.debug.assert(compareBytes("a.b", "a/b") == .lt); // 0x2E < 0x2F, '/' unprivileged } /// §4.5.3-m1 "an absent value sorts before any present value." Both absent /// compares equal; one absent sorts before any present value including "". /// Two present values compare by `compareBytes`. pub fn compareOptional(a: ?[]const u8, b: ?[]const u8) std.math.Order { if (a == null and b == null) return .eq; if (a == null) return .lt; if (b == null) return .gt; return compareBytes(a.?, b.?); } /// §4.5.2-r4 T two-level rule: compare tag name first; on a name tie, /// target hash must strictly increase, so the hash comparison decides. pub fn compareTag(a_name: []const u8, a_hash: []const u8, b_name: []const u8, b_hash: []const u8) std.math.Order { const name_order = compareBytes(a_name, b_name); if (name_order != .eq) return name_order; return compareBytes(a_hash, b_hash); } /// §4.6.1 Simple-Pathname predicate. Operates on the DECODED form of a token /// (§4.6 line 853), as a sequence of unsigned octets. Applies to the A-card /// filename and to the F-card filename and old-name (§4.6.1-p1, line 858). /// Returns true iff the name is ACCEPTED; false iff it must be rejected. /// Rejection is decidable from the '/'-separator structure alone (§4.6.1-m1): /// no byte-content restriction — backslashes, spaces, control bytes, and /// arbitrary/invalid UTF-8 all pass. The stricter writer profile does NOT /// constrain acceptance (§4.6.1-m2, line 888). pub fn isSimplePathname(name: []const u8) bool { if (name.len == 0) return false; // §4.6.1-r1: empty var start: usize = 0; var i: usize = 0; while (i < name.len) : (i += 1) { // bound: i++ each step, ends at name.len std.debug.assert(start <= i); // invariant: start never runs past i if (name[i] != '/') continue; if (!pathElementOk(name[start..i])) return false; start = i + 1; // element after the '/' } std.debug.assert(start <= name.len); return pathElementOk(name[start..name.len]); // final element, no trailing '/' } /// A single '/'-delimited element is bad iff empty (r2/r5/r6) or exactly /// `.`/`..` (r3/r4/r7). See `isSimplePathname` doc comment for the mapping /// from these two checks back to the seven enumerated RFC bullets. fn pathElementOk(elem: []const u8) bool { if (elem.len == 0) return false; if (std.mem.eql(u8, elem, ".") or std.mem.eql(u8, elem, "..")) return false; return true; } comptime { std.debug.assert(isSimplePathname("alpha.txt")); // §A.3 accept std.debug.assert(isSimplePathname("a/b/c")); // nested accept std.debug.assert(isSimplePathname("...")); // r3/r7 are exact: "..." passes std.debug.assert(!isSimplePathname("")); // r1 std.debug.assert(!isSimplePathname("/a")); // r2 std.debug.assert(!isSimplePathname(".")); // r3 std.debug.assert(!isSimplePathname("./a")); // r4 std.debug.assert(!isSimplePathname("a//b")); // r5 std.debug.assert(!isSimplePathname("a/")); // r6 std.debug.assert(!isSimplePathname("a/../b")); // r7 } const WIKI_NAME_MAX: usize = 100; // §4.6.2-r5 upper bound, in bytes /// §4.6.2 Wiki-Name predicate. Operates on the DECODED form of a token as a /// sequence of unsigned octets. Applies to the L-card title and to the A-card /// target in its wiki-name alternative (§4.6.2-p1, line 903). Returns true iff /// ACCEPTED; false iff it must be rejected. Reject iff any of: first byte /// <= 0x20 (r1: empty/leading-space/leading-control); a subsequent byte < 0x20 /// (r2: control incl. tab/LF); consecutive 0x20 0x20 anywhere (r3); final byte /// 0x20 (r4); byte length outside 1..100 (r5). Bytes >= 0x21 are otherwise /// unconstrained: 0x7F and all bytes >= 0x80 accepted, no UTF-8 check, length /// counted in bytes not characters (§4.6.2-m1, lines 919-921). pub fn isWikiName(name: []const u8) bool { if (name.len < 1 or name.len > WIKI_NAME_MAX) return false; // r5 (also empty) if (name[0] <= 0x20) return false; // r1: first byte if (name[name.len - 1] == 0x20) return false; // r4: final byte var i: usize = 1; while (i < name.len) : (i += 1) { // bound: i++ each step, ends at name.len // i starts at 1 and only grows, so this is what actually justifies // the unchecked i - 1 below — not a restatement of i < name.len. std.debug.assert(i >= 1); const b = name[i]; if (b < 0x20) return false; // r2: subsequent control byte if (b == 0x20 and name[i - 1] == 0x20) return false; // r3: consecutive spaces } return true; } comptime { std.debug.assert(isWikiName("A")); // 1-byte accept (r5 lower) std.debug.assert(isWikiName("Wiki Page")); // single interior space ok std.debug.assert(isWikiName("x" ** 100)); // r5 upper accept std.debug.assert(isWikiName("a\x7f")); // 0x7F accepted (m1) std.debug.assert(isWikiName("a\x80")); // >=0x80 accepted (m1) std.debug.assert(!isWikiName("")); // r5/r1: empty std.debug.assert(!isWikiName(" x")); // r1: leading space std.debug.assert(!isWikiName("\x1fx")); // r1: leading control std.debug.assert(!isWikiName("a\tb")); // r2: tab std.debug.assert(!isWikiName("a\nb")); // r2: LF std.debug.assert(!isWikiName("a b")); // r3: double space std.debug.assert(!isWikiName("a ")); // r4: trailing space std.debug.assert(!isWikiName("x" ** 101)); // r5 upper reject } /// Sidecar suffixes stripped in reserved-filename step 1 (§4.6.3-p1, line /// 926-929). Order does not matter for correctness: the three are mutually /// non-suffixing (none is a suffix of another), so at most one can ever /// match a given trailing region; kept as a fixed comptime-unrolled list. const RESERVED_SIDECAR_SUFFIXES = [_][]const u8{ "-journal", "-wal", "-shm" }; /// §4.6.3 Reserved-filename predicate. Operates on the decoded CURRENT /// F-card filename only -- the old-name field is never tested (line 957). /// Returns true iff the three-step procedure (lines 926-937) matches, which /// means the caller MUST silently drop the F card, not reject it (r2, line /// 961): reserved-ness is a bool drop signal, never a ParseError variant. pub fn isReservedFilename(name: []const u8) bool { // Step 1 (p1, lines 926-929): strip exactly one sidecar suffix. The // `!sidecar_stripped` guard is what makes this "exactly one" -- once a // suffix matches we stop, we never re-scan the shortened remainder. var remaining = name; var sidecar_stripped = false; inline for (RESERVED_SIDECAR_SUFFIXES) |suffix| { if (!sidecar_stripped and std.ascii.endsWithIgnoreCase(remaining, suffix)) { remaining = remaining[0 .. remaining.len - suffix.len]; sidecar_stripped = true; } } // Step 2 (p2, lines 933-934): reserved tail, case-insensitive. const tail_fossil = "_FOSSIL_"; const tail_fslckout = ".fslckout"; const tail_len: usize = if (std.ascii.endsWithIgnoreCase(remaining, tail_fossil)) tail_fossil.len else if (std.ascii.endsWithIgnoreCase(remaining, tail_fslckout)) tail_fslckout.len else return false; std.debug.assert(remaining.len >= tail_len); // endsWithIgnoreCase guarantees this // Step 3 (p3, lines 936-937): whole-string, preceding '/', or sidecar. if (remaining.len == tail_len) return true; // 3a: tail is the whole string if (sidecar_stripped) return true; // 3c: a sidecar suffix was stripped std.debug.assert(remaining.len > tail_len); // 3a ruled out above; index is in-bounds return remaining[remaining.len - tail_len - 1] == '/'; // 3b } comptime { std.debug.assert(isReservedFilename("_FOSSIL_")); // 3a whole string std.debug.assert(isReservedFilename(".fslckout")); // 3a whole string std.debug.assert(isReservedFilename("dir/_FOSSIL_")); // 3b preceding '/' std.debug.assert(isReservedFilename("x_FOSSIL_-wal")); // 3c sidecar stripped std.debug.assert(isReservedFilename("_FOSSIL_-WAL")); // p1 case-insensitive strip std.debug.assert(isReservedFilename("_fossil_")); // p2 case-insensitive tail std.debug.assert(!isReservedFilename("x_FOSSIL_")); // r1: no step-3 condition holds std.debug.assert(!isReservedFilename("CON")); // m1: no reserved tail at all std.debug.assert(!isReservedFilename("readme.txt")); // p2 fails: no tail std.debug.assert(!isReservedFilename("")); // underflow guard boundary std.debug.assert(!isReservedFilename("foo-wal")); // strip leaves no tail } /// §4.6.3-m2 sequencing (lines 967-973): "the F card sort check (Section /// 4.5.2) runs before the reserved-name drop, so a reserved-named F card /// must itself be in sort position relative to the previously retained /// entry, and the next F card is compared against that same retained /// entry. The dropped name never becomes the comparison anchor. A /// validator that checks order before dropping reproduces this behavior /// exactly." `OutOfOrder` is the §4.5.2-r1 sort rejection (equal or /// descending); it is distinct from a drop, which is not an error. pub const FCardSortError = error{OutOfOrder}; /// Feeds F cards one at a time, in wire order, and tracks the effective /// file set (§4.6.3-r2): a reserved-named card is silently dropped, not /// admitted, so it never appears in the retained set and never replaces /// `anchor`. `admit` runs the §4.5.2 sort check first and the §4.6.3 /// reserved check second, per the sequencing clause above. pub const FCardAdmission = struct { /// Decoded current filename of the last RETAINED F card, or null /// before the first admitted card. This is the sort-check anchor; a /// dropped card's name is never written here. anchor: ?[]const u8 = null, /// Admit one F card by its decoded CURRENT filename only (§4.6.3 lines /// 957-959: the old-name field is never tested by this rule -- there /// is no old-name parameter for it to reach). Order is checked against /// `anchor` first: equal or descending is `OutOfOrder`, matching /// §4.5.2-r1, and applies even to a reserved name -- reserved-ness /// does not exempt a card from the sort check. Only a card that passes /// the sort check is then tested for reserved-ness. Returns true and /// advances `anchor` to `name` iff retained; returns false (anchor /// unchanged) iff dropped. pub fn admit(self: *FCardAdmission, name: []const u8) FCardSortError!bool { if (self.anchor) |prev| { if (compareBytes(prev, name) != .lt) return FCardSortError.OutOfOrder; } if (isReservedFilename(name)) return false; // dropped: anchor untouched self.anchor = name; std.debug.assert(self.anchor != null and std.mem.eql(u8, self.anchor.?, name)); return true; } }; // --------------------------------------------------------------------------- // §4.6.4 Timestamps // --------------------------------------------------------------------------- /// The five accepted §4.6.4 D/E timestamp token forms (p1: the token is /// classified RAW, never escape-decoded). `date_time` is the broad reader /// form -- leading '-', whitespace/'T' separator, and tz all permitted; a /// writer that must satisfy m8 uses `isWriterTimestamp` for the narrower /// canonical subset. pub const TimestampForm = enum { date_time, date, time, relative, julian }; /// §4.6.4 classify the raw D/E card timestamp token. Returns the matched /// form, or null iff the token is rejected outright. Pure: reads no clock, /// filesystem, or RNG state (m9 -- `now`/`subsec`/`subsecond` are classified /// as `.relative`, never resolved to an instant here; resolution happens at /// [FossilRepoState] ingestion time, outside this module). pub fn classifyTimestamp(token: []const u8) ?TimestampForm { if (token.len == 0) return null; // negative space: nothing to classify if (matchDate(token)) |dm| { if (dm.cur == token.len) { if (!dateGateOk(dm.y_neg, dm.y, dm.m, dm.d)) return null; // r3 return .date; } // Not a bare date: the remainder must be a date-time separator + // time [+ tz], or the whole token is rejected -- a matched date // prefix is never reinterpreted as a bare time (p1/r1 tokens rely // on this: they fail here, not by falling through below). var cur = dm.cur; const sep_start = cur; while (cur < token.len and (token[cur] == 'T' or std.ascii.isWhitespace(token[cur]))) : (cur += 1) {} if (cur == sep_start) return null; // m1 "1 or more"; r1 lowercase t never advances this const tm = matchTime(token, cur) orelse return null; const tz_end = matchTz(token, tm.cur); if (tz_end != token.len) return null; // trailing garbage after tz if (!dateGateOk(dm.y_neg, dm.y, dm.m, dm.d)) return null; // r3 return .date_time; } if (matchTime(token, 0)) |tm| { if (tm.cur == token.len) return .time; // m4: implied 2000-01-01, gate always passes } if (isRelativeLiteral(token)) return .relative; // m5 if (matchBareDecimal(token)) return .julian; // m6/r3 return null; } /// §4.6.4-m8 writer grammar: `date %x54 time [frac]` -- YYYY-MM-DD, exactly /// the byte 'T' (never lowercase, never whitespace, never a bare space), then /// HH:MM:SS with SS mandatory, then an optional `.frac`. No leading sign, no /// timezone. True iff `token` is exactly that canonical interoperable form /// (w1: `2017-12-06T15:36:24.287`). This is the oracle a future D/E emitter /// and any round-trip check call; parallels the hash-token canonical-writer /// split already in this module (see `validateName` vs. its callers). pub fn isWriterTimestamp(token: []const u8) bool { if (token.len == 0) return false; // negative space const dm = matchDate(token) orelse return false; if (dm.y_neg) return false; // writer form: no leading '-' if (dm.cur >= token.len or token[dm.cur] != 'T') return false; // exactly one 'T', no ws const tm = matchTime(token, dm.cur + 1) orelse return false; if (!tm.had_seconds) return false; // writer time = HH:MM:SS, SS mandatory if (tm.cur != token.len) return false; // no tz permitted return dateGateOk(dm.y_neg, dm.y, dm.m, dm.d); // r3 } /// Parse exactly `n` ASCII digit bytes from the front of `s` as an unsigned /// int, or null if fewer than `n` bytes remain or any of the first `n` bytes /// is not '0'-'9' (§4.6.4-m7 "exactly N digits" -- no sign, no short/long /// reads). Wire-derived input: failure is a guard return, never a panic. fn parseFixedDigits(s: []const u8, comptime n: usize) ?u32 { comptime std.debug.assert(n <= 4); // largest field here is the 4-digit year if (s.len < n) return null; var v: u32 = 0; for (s[0..n]) |b| { // bound: fixed at comptime n if (b < '0' or b > '9') return null; v = v * 10 + (b - '0'); } std.debug.assert(v < comptime std.math.pow(u32, 10, n)); // n digits bound the value return v; } const DateMatch = struct { cur: usize, y_neg: bool, y: u32, m: u32, d: u32 }; /// §4.6.4-m3/m7 date: optional leading '-', then YYYY-MM-DD. Month is /// range-checked to 01-12 and day to 01-31 here (m7); there is no /// calendar-aware check, so 2024-02-31 parses fine (that acceptance is /// exercised by the caller, not rejected here). Returns the match plus the /// cursor just past the day field, or null on any mismatch. fn matchDate(token: []const u8) ?DateMatch { var cur: usize = 0; var y_neg = false; if (token.len > 0 and token[0] == '-') { y_neg = true; cur = 1; } const y = parseFixedDigits(token[cur..], 4) orelse return null; cur += 4; if (cur >= token.len or token[cur] != '-') return null; cur += 1; const m = parseFixedDigits(token[cur..], 2) orelse return null; if (m < 1 or m > 12) return null; // m7: month 01-12 std.debug.assert(m >= 1 and m <= 12); cur += 2; if (cur >= token.len or token[cur] != '-') return null; cur += 1; const d = parseFixedDigits(token[cur..], 2) orelse return null; if (d < 1 or d > 31) return null; // m7: day 01-31, no calendar check std.debug.assert(d >= 1 and d <= 31); cur += 2; std.debug.assert(cur <= token.len); return DateMatch{ .cur = cur, .y_neg = y_neg, .y = y, .m = m, .d = d }; } /// §4.6.4-r3 JD>0 gate, date-granularity reading (RESOLVED operator decision, /// 2026-07-09 -- see ambiguities.md): reject a date/date-time token iff its /// signed (year, month, day) is lexicographically <= (-4713, 11, 24), /// independent of time-of-day or tz. `year` is the signed astronomical year /// (y_neg negates `y`); this is what makes -4713-11-24T18:00:00 reject /// despite its positive fractional Julian Date. fn dateGateOk(y_neg: bool, y: u32, m: u32, d: u32) bool { std.debug.assert(m >= 1 and m <= 12); std.debug.assert(d >= 1 and d <= 31); const year: i32 = if (y_neg) -@as(i32, @intCast(y)) else @as(i32, @intCast(y)); if (year < -4713) return false; if (year > -4713) return true; if (m < 11) return false; if (m > 11) return true; return d > 24; } const TimeMatch = struct { cur: usize, had_seconds: bool }; /// §4.6.4-m1/m4/m7 time-of-day: HH:MM, HH:MM:SS, or HH:MM:SS.frac. HH is /// 00-24, MM/SS are 00-59, frac (only legal after ':SS') is 1+ digits. /// Returns the cursor just past the match plus whether ':SS' was present, or /// null on any mismatch. fn matchTime(token: []const u8, i: usize) ?TimeMatch { var cur = i; const hh = parseFixedDigits(token[cur..], 2) orelse return null; if (hh > 24) return null; // m7: hour 00-24 std.debug.assert(hh <= 24); cur += 2; if (cur >= token.len or token[cur] != ':') return null; cur += 1; const mm = parseFixedDigits(token[cur..], 2) orelse return null; if (mm > 59) return null; // m7: minute 00-59 std.debug.assert(mm <= 59); cur += 2; var had_seconds = false; if (cur < token.len and token[cur] == ':') { cur += 1; const ss = parseFixedDigits(token[cur..], 2) orelse return null; if (ss > 59) return null; // m7: second 00-59 std.debug.assert(ss <= 59); cur += 2; had_seconds = true; if (cur < token.len and token[cur] == '.') { cur += 1; const frac_start = cur; while (cur < token.len and std.ascii.isDigit(token[cur])) : (cur += 1) {} // bound: token.len if (cur == frac_start) return null; // m7: frac needs 1+ digits std.debug.assert(cur > frac_start); } } std.debug.assert(cur <= token.len); return TimeMatch{ .cur = cur, .had_seconds = had_seconds }; } /// §4.6.4-m2 optional timezone: optional whitespace, then '+HH:MM', /// '-HH:MM', 'Z', or 'z'. HH/MM are exactly 2 digits each, structural only -- /// the RFC gives no tz range and no conforming writer ever emits one (m8). /// Returns the cursor past a matched tz, or `i` unchanged if none is present: /// that "no advance" is what makes the whole timezone optional -- the /// caller's final `cur == token.len` check does the actual accept/reject. fn matchTz(token: []const u8, i: usize) usize { var cur = i; while (cur < token.len and std.ascii.isWhitespace(token[cur])) : (cur += 1) {} // bound: token.len if (cur >= token.len) return i; // no tz; don't consume trailing ws const c = token[cur]; if (c == 'Z' or c == 'z') return cur + 1; if (c == '+' or c == '-') { var p = cur + 1; _ = parseFixedDigits(token[p..], 2) orelse return i; p += 2; if (p >= token.len or token[p] != ':') return i; p += 1; _ = parseFixedDigits(token[p..], 2) orelse return i; p += 2; std.debug.assert(p <= token.len); return p; } return i; // no tz } /// §4.6.4-m5: `now`, `subsec`, or `subsecond`, case-insensitive, whole-token /// exact match only. fn isRelativeLiteral(token: []const u8) bool { return std.ascii.eqlIgnoreCase(token, "now") or std.ascii.eqlIgnoreCase(token, "subsec") or std.ascii.eqlIgnoreCase(token, "subsecond"); } /// §4.6.4-m6 (L1014) bare decimal: lexically `1*DIGIT ["." 1*DIGIT]` (>=1 /// integer digit; a dot requires >=1 fraction digit, mirroring the time /// frac rule), consuming the whole token, then accepted iff its value r /// satisfies `0 < r < 5373484.5` directly. fn matchBareDecimal(token: []const u8) bool { var i: usize = 0; while (i < token.len and std.ascii.isDigit(token[i])) : (i += 1) {} // bound: token.len if (i == 0) return false; // need >=1 integer digit std.debug.assert(i >= 1); if (i < token.len and token[i] == '.') { var j = i + 1; while (j < token.len and std.ascii.isDigit(token[j])) : (j += 1) {} // bound: token.len if (j == i + 1) return false; // dot requires >=1 fraction digit i = j; } if (i != token.len) return false; // trailing byte the lexical grammar doesn't cover const r = std.fmt.parseFloat(f64, token) catch return false; // unreachable on a validated slice return r > 0 and r < 5373484.5; } comptime { std.debug.assert(classifyTimestamp("2017-12-06T15:36:24.287").? == .date_time); // w1 std.debug.assert(isWriterTimestamp("2017-12-06T15:36:24.287")); // w1 std.debug.assert(classifyTimestamp("2017-12-06").? == .date); // m3 std.debug.assert(classifyTimestamp("15:36:24").? == .time); // m4 std.debug.assert(classifyTimestamp("now").? == .relative); // m5 std.debug.assert(classifyTimestamp("2451545").? == .julian); // m6 std.debug.assert(classifyTimestamp("2017-12-06t15:36:24") == null); // r1 std.debug.assert(classifyTimestamp("-4713-11-24") == null); // r3 boundary std.debug.assert(classifyTimestamp("0") == null); // r3 numeric zero std.debug.assert(!isWriterTimestamp("2017-12-06")); // m8: date alone is not the writer form } // --------------------------------------------------------------------------- // §4.7.2 A Card // --------------------------------------------------------------------------- /// One parsed A card (§4.7.2 attachment card). Grammar: `a-card = "A" SP /// filename SP target [ SP source ] LF` (line 1074). `name` and `target` /// borrow from the caller's `decode_buf`; `source` borrows the card's raw /// args -- no allocation anywhere in this parse. pub const ACard = struct { /// Decoded filename's final path component only; any directory prefix /// is discarded (m1, lines 1084-1086). name: []const u8, /// Decoded target: hash- or wiki-name-shaped (r2, lines 1088-1089). /// Which family it is, and whether it resolves, is crosslink-time work /// (lines 1097-1107) -- out of scope for parse-time acceptance. target: []const u8, /// Raw, never-decoded artifact hash when present; null when absent /// (r3/m2, lines 1093-1095). source: ?[]const u8, }; /// Return the final '/'-delimited element of `name`. `isSimplePathname` /// already rejects an empty element and a trailing '/' (§4.6.1), so the /// element after the last '/' -- or the whole name, if there is none -- is /// always non-empty. fn finalPathComponent(name: []const u8) []const u8 { std.debug.assert(name.len >= 1); var last_slash: ?usize = null; for (name, 0..) |c, i| { // bound: name.len, via the slice iterator if (c == '/') last_slash = i; } const result = if (last_slash) |idx| name[idx + 1 ..] else name; std.debug.assert(result.len >= 1); return result; } comptime { std.debug.assert(std.mem.eql(u8, finalPathComponent("a/b/c"), "c")); std.debug.assert(std.mem.eql(u8, finalPathComponent("x"), "x")); } /// Parse one already-tokenized A card (§4.7.2). Returns null for any /// rejection reason -- bad arity (§4.2.1 line 610: "a fourth on A"), a /// missing filename/target (p1), a bad filename (r1), a bad target (r2), or /// a bad source (r3) -- matching the module's "every rejection collapses to /// null/false" posture. Parse-time acceptance is syntactic only; it does /// not resolve the target to an object (lines 1080-1081). /// /// `decode_buf` is caller-owned and holds both decoded fields. /// Precondition: `decode_buf.len >= filename_token.len + target_token.len` /// (decoded length never exceeds wire length, per `decodeEscapes`). pub fn parseACard(card: CardLine, decode_buf: []u8) ?ACard { std.debug.assert(card.letter == 'A'); var it = card.tokens(); const filename_tok = it.next() orelse return null; // p1: filename required const target_tok = it.next() orelse return null; // p1: target required const source_tok = it.next(); // optional (grammar's "[ SP source ]") if (it.next() != null) return null; // §4.2.1 line 610: "a fourth on A" std.debug.assert(decode_buf.len >= filename_tok.len + target_tok.len); // Filename: decode, then the pathname predicate, then basename (m1). const filename_dec = decodeEscapes(filename_tok, decode_buf[0..filename_tok.len]); if (!isSimplePathname(filename_dec)) return null; // r1 const name = finalPathComponent(filename_dec); // Target: the one hash-bearing position decoded before validation // (§4.3.1 lines 690-692), since it may alternatively hold a wiki name. const target_buf = decode_buf[filename_tok.len..][0..target_tok.len]; const target = decodeEscapes(target_tok, target_buf); const target_ok = validateHashToken(.artifact_hash, target) or isWikiName(target); if (!target_ok) return null; // r2 // Source: raw hash, never decoded (r3; §4.3.1 line 680 names it the // sole exception among hash-bearing positions). Absent -> null (m2). var source: ?[]const u8 = null; if (source_tok) |raw| { if (!validateHashToken(.artifact_hash, raw)) return null; // r3 source = raw; } std.debug.assert(name.len >= 1); std.debug.assert(target.len >= 1); std.debug.assert(source == null or source.?.len == 40 or source.?.len == 64); return .{ .name = name, .target = target, .source = source }; } // --------------------------------------------------------------------------- // §4.7.3 B Card // --------------------------------------------------------------------------- /// One parsed B card (§4.7.3 baseline card). Grammar: `b-card = "B" SP hash /// LF` (line 1127). `hash` is raw -- B is a hash/checksum position and §4.3.1 /// (line 686-688) never decodes it, unlike the A card's target. Presence /// marks the artifact as a delta manifest and the delta-of-delta rejection /// is §8 assembly work, out of scope here (line 1130-1134). pub const BCard = struct { hash: []const u8 }; /// Parse one already-tokenized B card (§4.7.3). Returns null for bad arity /// or a hash failing the hash map (`.artifact_hash`, §4.7.1). pub fn parseBCard(card: CardLine) ?BCard { std.debug.assert(card.letter == 'B'); var it = card.tokens(); const hash_tok = it.next() orelse return null; // p1: hash required if (it.next() != null) return null; // grammar has no second token if (!validateHashToken(.artifact_hash, hash_tok)) return null; // r1 std.debug.assert(hash_tok.len == 40 or hash_tok.len == 64); return .{ .hash = hash_tok }; } // --------------------------------------------------------------------------- // §4.7.4 C Card // --------------------------------------------------------------------------- /// One parsed C card (§4.7.4 comment card). Grammar: `c-card = "C" SP /// comment LF` (line 1140). `comment` borrows the caller's `decode_buf` -- /// the C card is one of the 12 decoded positions (§4.3.1 line 681), and its /// decoded content is otherwise unvalidated (m1). pub const CCard = struct { comment: []const u8 }; /// Parse one already-tokenized C card (§4.7.4). Returns null for a missing /// token, an empty token (`comment = 1*tchar`, Appendix B), or a second /// token -- the grammar has room for exactly one (r1). /// Precondition: `decode_buf.len >= comment token length` (decoded length /// never exceeds wire length, per `decodeEscapes`). pub fn parseCCard(card: CardLine, decode_buf: []u8) ?CCard { std.debug.assert(card.letter == 'C'); var it = card.tokens(); // ERRATUM (docs/rfcs/erratum/artifact-format-00-s4.2-empty-trailing-token.md): // §4.2's `token = 1*tchar` reads as forbidding an empty comment, but the // reference implementation distinguishes ABSENT from EMPTY positionally and // accepts the latter: `next_token` returns NULL only at end-of-line, so // `C` LF is rejected ("missing comment text on C-card") while `C` SP LF // yields a present, empty comment. Real repositories carry both. Rejecting // the empty form drops the whole check-in, which is silent data loss rather // than a parse error the operator ever sees. const comment_tok = it.next() orelse return null; // r1: no token at all if (it.next() != null) return null; // grammar has no second token std.debug.assert(decode_buf.len >= comment_tok.len); const comment = decodeEscapes(comment_tok, decode_buf[0..comment_tok.len]); std.debug.assert(comment.len <= comment_tok.len); return .{ .comment = comment }; } // --------------------------------------------------------------------------- // §4.7.5 D Card and E Card // --------------------------------------------------------------------------- /// One parsed D card (§4.7.5 date card). Grammar: `d-card = "D" SP /// timestamp LF` (line 1150). `timestamp` is raw -- D/E timestamps are /// never decoded (§4.3.1 line 687-688). pub const DCard = struct { timestamp: []const u8 }; /// One parsed E card (§4.7.5 technote card). Grammar: `e-card = "E" SP /// timestamp SP technote-id LF` (line 1151). Both fields raw. EVENT-type /// marking is §5.3 type resolution -- deferred to the manifest-assembly /// batch, exactly as A/B's "marks the artifact as..." effects are deferred. pub const ECard = struct { timestamp: []const u8, technote_id: []const u8 }; /// Parse one already-tokenized D card (§4.7.5). Returns null for bad arity /// or a timestamp failing `classifyTimestamp` (§4.6.4). pub fn parseDCard(card: CardLine) ?DCard { std.debug.assert(card.letter == 'D'); var it = card.tokens(); const ts_tok = it.next() orelse return null; // p1: timestamp required if (it.next() != null) return null; // grammar has no second token if (classifyTimestamp(ts_tok) == null) return null; // r2 return .{ .timestamp = ts_tok }; } /// Parse one already-tokenized E card (§4.7.5). Returns null for bad arity, /// a timestamp failing §4.6.4, or a technote-id failing the hash map /// (`.artifact_hash`, §4.7.1) -- the id is a hash/checksum position and is /// never decoded. pub fn parseECard(card: CardLine) ?ECard { std.debug.assert(card.letter == 'E'); var it = card.tokens(); const ts_tok = it.next() orelse return null; // p2: timestamp required const id_tok = it.next() orelse return null; // p2: technote-id required if (it.next() != null) return null; // grammar has no third token if (classifyTimestamp(ts_tok) == null) return null; // r2 if (!validateHashToken(.artifact_hash, id_tok)) return null; // r3 std.debug.assert(id_tok.len == 40 or id_tok.len == 64); return .{ .timestamp = ts_tok, .technote_id = id_tok }; } // --------------------------------------------------------------------------- // §4.7.6 F Card // --------------------------------------------------------------------------- /// §4.7.6-m4/m5 permission-derived entry kind. `x` in the raw perm token /// wins over `l` (checked first); anything else, including an absent perm /// or a hash-less delete marker, is `.regular` (lines 1196-1199). pub const FileMode = enum { regular, executable, symlink }; /// One parsed F card (§4.7.6 file-list entry). `filename` and `old_name` /// borrow the caller's `decode_buf` (decoded, §4.6.1-checked); `hash` and /// `perm` are raw slices of the wire args -- never decoded (m3). `hash == /// null` is the delta-manifest deletion marker (§8.2); whether that's legal /// here depends on a B card elsewhere in the same artifact, which this /// single-card parser can't see -- deferred to the manifest-assembly batch, /// same as B's delta-of-delta check. Sort/dedup and reserved-name dropping /// are per-artifact machinery that already exists, in `FCardAdmission` and /// `isReservedFilename` -- not this parser either. pub const FCard = struct { filename: []const u8, hash: ?[]const u8, perm: ?[]const u8, old_name: ?[]const u8, mode: FileMode, }; /// §4.7.6-m5 classifier: raw perm token -> `FileMode`. `x` anywhere wins; /// else `l` anywhere is a symlink; a null or perm-less token is regular. pub fn fileModeOf(perm: ?[]const u8) FileMode { const p = perm orelse return .regular; if (std.mem.indexOfScalar(u8, p, 'x') != null) return .executable; if (std.mem.indexOfScalar(u8, p, 'l') != null) return .symlink; return .regular; } /// Parse one already-tokenized F card (§4.7.6). Returns null for a missing /// filename (r1), a filename or old-name failing the pathname predicate /// (§4.6.1, m1/m2), a hash failing the hash map when present (r3), an empty /// perm token when present (`token = 1*tchar`, Appendix B -- perm is /// unvalidated against {w,x,l} but still must be nonempty), or a 5th token /// (the grammar has room for exactly four positions). /// Precondition: `decode_buf.len >= filename_tok.len + old_tok.len`. pub fn parseFCard(card: CardLine, decode_buf: []u8) ?FCard { std.debug.assert(card.letter == 'F'); var it = card.tokens(); const filename_tok = it.next() orelse return null; // r1: filename required const hash_tok = it.next(); // optional const perm_tok = it.next(); // optional, only meaningful with hash present const old_tok = it.next(); // optional, only meaningful with perm present if (it.next() != null) return null; // grammar has no 5th token std.debug.assert(decode_buf.len >= filename_tok.len + (if (old_tok) |t| t.len else 0)); const filename = decodeEscapes(filename_tok, decode_buf[0..filename_tok.len]); if (!isSimplePathname(filename)) return null; // m1/r2 var hash: ?[]const u8 = null; if (hash_tok) |raw| { if (!validateHashToken(.artifact_hash, raw)) return null; // r3 hash = raw; } // perm: raw, unvalidated against {w,x,l} at parse time (m4), but the // grammar still requires `token = 1*tchar` (Appendix B) -- an empty // 3rd token (e.g. a trailing SP after hash) has no production and // MUST reject, not silently parse as perm=="". if (perm_tok) |raw| { if (raw.len == 0) return null; // p1/r1: no production for empty token } const perm = perm_tok; var old_name: ?[]const u8 = null; if (old_tok) |raw| { const old_buf = decode_buf[filename.len..][0..raw.len]; const decoded = decodeEscapes(raw, old_buf); if (!isSimplePathname(decoded)) return null; // m2/r4 old_name = decoded; } std.debug.assert(filename.len >= 1); std.debug.assert(hash == null or hash.?.len == 40 or hash.?.len == 64); std.debug.assert(perm == null or perm.?.len >= 1); std.debug.assert(old_name == null or old_name.?.len >= 1); return .{ .filename = filename, .hash = hash, .perm = perm, .old_name = old_name, .mode = fileModeOf(perm), }; } // --------------------------------------------------------------------------- // §4.7.7 G Card, H Card, and I Card // --------------------------------------------------------------------------- /// One parsed G card (§4.7.7 forum thread-root). Grammar: `g-card = "G" SP /// hash LF` (line 1207). `hash` is raw -- a hash/checksum position, never /// decoded (§4.3.1). Presence marks the artifact as a forum post (§5.3 type /// resolution) -- deferred to the manifest-assembly batch, same posture as /// A/B's "marks the artifact as..." effects. pub const GCard = struct { hash: []const u8 }; /// One parsed I card (§4.7.7 forum reply-to). Grammar: `i-card = "I" SP hash /// LF` (line 1209). Byte-identical wire shape to G, raw hash, but distinct /// meaning -- the post being replied to, not the thread root. An artifact /// MUST NOT carry both an H and an I card (line 1218), but that is a /// whole-artifact check a single-card parser cannot see; deferred to the /// §5.4 assembly batch, same as B's delta-of-delta check. pub const ICard = struct { hash: []const u8 }; /// One parsed H card (§4.7.7 forum thread title). Grammar: `h-card = "H" SP /// threadtitle LF` (line 1208). `title` borrows the caller's `decode_buf` -- /// one of the 12 decoded positions (§4.3.1); no content validation beyond /// arity/nonempty applies (line 1216-1217): "any decoded string is /// accepted", unlike the L card's wiki-name gate below. pub const HCard = struct { title: []const u8 }; /// Shared G/I helper: one required raw hash token, validated per the hash /// map (`.artifact_hash`), never decoded. G and I are byte-identical on the /// wire (line 1207, 1209); this is the only place that shape is checked -- /// the two callers below wrap the result into their distinct struct types. fn hashOnlyForumCard(card: CardLine) ?[]const u8 { std.debug.assert(card.letter == 'G' or card.letter == 'I'); var it = card.tokens(); const hash_tok = it.next() orelse return null; // p1: hash required if (it.next() != null) return null; // grammar has no second token if (!validateHashToken(.artifact_hash, hash_tok)) return null; // r1 std.debug.assert(hash_tok.len == 40 or hash_tok.len == 64); return hash_tok; } /// Parse one already-tokenized G card (§4.7.7). Returns null for bad arity /// or a hash failing the hash map. pub fn parseGCard(card: CardLine) ?GCard { std.debug.assert(card.letter == 'G'); const hash = hashOnlyForumCard(card) orelse return null; return .{ .hash = hash }; } /// Parse one already-tokenized I card (§4.7.7). Returns null for bad arity /// or a hash failing the hash map. pub fn parseICard(card: CardLine) ?ICard { std.debug.assert(card.letter == 'I'); const hash = hashOnlyForumCard(card) orelse return null; return .{ .hash = hash }; } /// Parse one already-tokenized H card (§4.7.7). Returns null for a missing /// token, an empty token (`threadtitle = token = 1*tchar`, Appendix B), or a /// second token -- the grammar has room for exactly one. Any nonempty /// decoded content is accepted (line 1216-1217); contrast `parseLCard`. /// Precondition: `decode_buf.len >= title token length`. pub fn parseHCard(card: CardLine, decode_buf: []u8) ?HCard { std.debug.assert(card.letter == 'H'); var it = card.tokens(); const title_tok = it.next() orelse return null; // p1: title required if (title_tok.len == 0) return null; // token = 1*tchar if (it.next() != null) return null; // grammar has no second token std.debug.assert(decode_buf.len >= title_tok.len); const title = decodeEscapes(title_tok, decode_buf[0..title_tok.len]); std.debug.assert(title.len <= title_tok.len); return .{ .title = title }; } // --------------------------------------------------------------------------- // §4.7.8 J Card // --------------------------------------------------------------------------- /// One parsed J card (§4.7.8 ticket field-change). Grammar: `j-card = "J" SP /// fieldname [ SP value ] LF` (line 1222). `field` is the raw wire token, /// stored verbatim including any leading `+` (m1/m2, line 1225-1226) -- not /// a decoded position. `value` is escape-decoded (m1) and borrows the /// caller's `decode_buf`; an absent value is "" per m3, never null -- the /// type is plain `[]const u8`, not `?[]const u8`, which defines the null /// case out of existence rather than modelling it. Ascending-by-field /// ordering across a run of J cards (§4.5.2) is manifest-assembly work, out /// of scope for this single-card parser. Ticket-processing semantics (the /// +-prefix append rule, unknown-field tolerance) are explicitly out of /// scope for the artifact layer (line 1227-1240). pub const JCard = struct { field: []const u8, value: []const u8 }; /// Parse one already-tokenized J card (§4.7.8). Returns null for a missing /// fieldname, an empty fieldname or value token (`token = 1*tchar`, Appendix /// B -- neither `fieldname` nor `value` has its own production, so an empty /// wire token has no production either way), or a third token -- the /// grammar has room for exactly two. /// Precondition: `decode_buf.len >= value token length`. pub fn parseJCard(card: CardLine, decode_buf: []u8) ?JCard { std.debug.assert(card.letter == 'J'); var it = card.tokens(); const field_tok = it.next() orelse return null; // r1: fieldname required if (field_tok.len == 0) return null; // token = 1*tchar const value_tok = it.next(); // optional if (it.next() != null) return null; // grammar has no third token // m3: absent value is "", never null — and per the §4.2 erratum an // EMPTY trailing token decodes to the same "", which is exactly what the // reference implementation does (`if( zValue==0 ) zValue = ""`). So absent // and empty are indistinguishable for J alone; the T card keeps them apart // because its own §4.7.16 rule says an absent value is null. var value: []const u8 = ""; if (value_tok) |raw| { std.debug.assert(decode_buf.len >= raw.len); value = decodeEscapes(raw, decode_buf[0..raw.len]); } std.debug.assert(field_tok.len >= 1); std.debug.assert(value.len <= if (value_tok) |t| t.len else 0); return .{ .field = field_tok, .value = value }; } // --------------------------------------------------------------------------- // §4.7.9 K Card // --------------------------------------------------------------------------- /// One parsed K card (§4.7.9 ticket card). Grammar: `k-card = "K" SP /// ticket-id LF` (line 1244). `ticket_id` is raw, pinned to the 40-char /// SHA-1 length (r1) -- a 64-char SHA3-length id is always invalid, /// regardless of hash policy. Presence marks the artifact as a ticket /// change (§5.3 type resolution) -- deferred to manifest assembly. pub const KCard = struct { ticket_id: []const u8 }; /// Parse one already-tokenized K card (§4.7.9). Returns null for bad arity /// or an id failing the hash map (`.ticket_id`, §4.7.1) -- pinned to 40 hex, /// lowercase-only (s1: the module takes the parser's MAY as lowercase-only, /// mirroring the §4.7.1 hash-map decision at line 1648). pub fn parseKCard(card: CardLine) ?KCard { std.debug.assert(card.letter == 'K'); var it = card.tokens(); const id_tok = it.next() orelse return null; // p1: ticket-id required if (it.next() != null) return null; // grammar has no second token if (!validateHashToken(.ticket_id, id_tok)) return null; // r1 std.debug.assert(id_tok.len == 40); return .{ .ticket_id = id_tok }; } // --------------------------------------------------------------------------- // §4.7.10 L Card // --------------------------------------------------------------------------- /// One parsed L card (§4.7.10 wiki-title card). Grammar: `l-card = "L" SP /// wikititle LF` (line 1256). `title` is escape-decoded and borrows the /// caller's `decode_buf`; unlike H, it MUST pass the wiki-name predicate /// (§4.6.2) -- this is the H/L contrast the RFC calls out at line 1217. /// Presence marks the artifact as a wiki page (§5.3) -- deferred. pub const LCard = struct { title: []const u8 }; /// Parse one already-tokenized L card (§4.7.10). Returns null for a missing /// token or a decoded title failing `isWikiName` (§4.6.2) -- which subsumes /// the empty-token and length-bound cases (wiki-name rejects length outside /// 1..100), so no separate `token = 1*tchar` check is needed here. A second /// token also rejects -- the grammar has room for exactly one. /// Precondition: `decode_buf.len >= title token length`. pub fn parseLCard(card: CardLine, decode_buf: []u8) ?LCard { std.debug.assert(card.letter == 'L'); var it = card.tokens(); const title_tok = it.next() orelse return null; // p1: title required if (it.next() != null) return null; // grammar has no second token std.debug.assert(decode_buf.len >= title_tok.len); const title = decodeEscapes(title_tok, decode_buf[0..title_tok.len]); if (!isWikiName(title)) return null; // r1 std.debug.assert(isWikiName(title)); return .{ .title = title }; } // --------------------------------------------------------------------------- // §4.7.11 M Card // --------------------------------------------------------------------------- /// One parsed M card (§4.7.11 cluster-member card). Grammar: `m-card = "M" /// SP hash LF` (line 1263). `hash` is raw -- a hash/checksum position, never /// decoded (§4.3.1). Repeatable; the strict-ascending-by-hash run check /// (line 1266) is §4.5.2 manifest-assembly work, already tested there. /// Presence marks the artifact as a cluster (§5.3 type resolution) -- /// deferred, same posture as A/B/G. pub const MCard = struct { hash: []const u8 }; /// Parse one already-tokenized M card (§4.7.11). Returns null for bad arity /// or a hash failing the hash map (`.artifact_hash`, §4.7.1). pub fn parseMCard(card: CardLine) ?MCard { std.debug.assert(card.letter == 'M'); var it = card.tokens(); const hash_tok = it.next() orelse return null; // p1: hash required if (it.next() != null) return null; // grammar has no second token if (!validateHashToken(.artifact_hash, hash_tok)) return null; // r1 std.debug.assert(hash_tok.len == 40 or hash_tok.len == 64); return .{ .hash = hash_tok }; } // --------------------------------------------------------------------------- // §4.7.12 N Card // --------------------------------------------------------------------------- /// One parsed N card (§4.7.12 mimetype card). Grammar: `n-card = "N" SP /// mimetype LF` (line 1270). `mimetype` is escape-decoded and borrows the /// caller's `decode_buf` -- one of the 12 decoded positions (§4.3.1); no /// mime-syntax validation applies (line 1272). Per-type default/target /// (text/x-fossil-wiki on wiki, text/plain on attachment, inert on /// check-in) is crosslink-time semantics -- deferred to manifest assembly. pub const NCard = struct { mimetype: []const u8 }; /// Parse one already-tokenized N card (§4.7.12). Returns null for a missing /// token, an empty token (`mimetype = token = 1*tchar`, Appendix B), or a /// second token -- the grammar has room for exactly one. /// Precondition: `decode_buf.len >= mimetype token length`. pub fn parseNCard(card: CardLine, decode_buf: []u8) ?NCard { std.debug.assert(card.letter == 'N'); var it = card.tokens(); const tok = it.next() orelse return null; // r1: no token if (tok.len == 0) return null; // r1: empty token if (it.next() != null) return null; // grammar has no second token std.debug.assert(decode_buf.len >= tok.len); const mimetype = decodeEscapes(tok, decode_buf[0..tok.len]); std.debug.assert(mimetype.len >= 1 and mimetype.len <= tok.len); return .{ .mimetype = mimetype }; } // --------------------------------------------------------------------------- // §4.7.13 P Card // --------------------------------------------------------------------------- /// One parsed P card (§4.7.13 parent card). Grammar: `p-card = "P" *( SP /// hash ) LF` (line 1290). `parents` borrows the raw wire arg bytes (never /// decoded -- a hash/checksum position); zero tokens (bare `P\n`) MUST be /// accepted (line 1293-1295) and yields `parents == null`, `count == 0`. /// Tokens are neither sorted nor deduplicated -- order is semantic (line /// 1296). Per-type meaning (primary-ancestor + merge-parents on a /// check-in, edit-chain link on a technote, ...) is manifest-assembly work. pub const PCard = struct { parents: ?[]const u8, count: usize, /// Re-tokenize the already-validated raw arg bytes into hashes, in /// wire order. Cheap: no allocation, `TokenIterator` borrows. pub fn hashes(self: PCard) TokenIterator { return .{ .rest = self.parents }; } }; /// Parse one already-tokenized P card (§4.7.13). Returns null iff any token /// fails the hash map (`.artifact_hash`, §4.7.1) -- zero tokens is not a /// failure (m1). pub fn parsePCard(card: CardLine) ?PCard { std.debug.assert(card.letter == 'P'); var count: usize = 0; var it = card.tokens(); // Bounded by card.args.len: each next() call strictly shrinks // it.rest, so this loop terminates within card.args.len iterations. while (it.next()) |tok| { if (!validateHashToken(.artifact_hash, tok)) return null; // r1 count += 1; } std.debug.assert(card.args != null or count == 0); return .{ .parents = card.args, .count = count }; } // --------------------------------------------------------------------------- // §4.7.14 Q Card // --------------------------------------------------------------------------- /// §4.7.14 q-sign: the byte glued onto the first hash token, distinguishing /// a cherry-pick from a backout (`q-sign = "+" / "-"`, line 1327). pub const QSign = enum { cherrypick, backout }; /// One parsed Q card (§4.7.14 cherry-pick card). Grammar: `q-card = "Q" SP /// q-sign hash [ SP hash ] LF` (line 1325-1326). `target` is the sign- /// stripped first-token remainder, raw, validated per the hash map; /// `baseline` is the optional plain unprefixed second token, raw. An /// absent baseline is left `null`, not resolved to the primary parent /// (m3, line 1334-1336) -- that resolution is manifest-assembly work. pub const QCard = struct { sign: QSign, target: []const u8, baseline: ?[]const u8 }; /// Parse one already-tokenized Q card (§4.7.14). Returns null for a /// missing/third token, a first byte other than '+' or '-' (q-sign, line /// 1327), or a remainder/baseline failing the hash map. pub fn parseQCard(card: CardLine) ?QCard { std.debug.assert(card.letter == 'Q'); var it = card.tokens(); const first = it.next() orelse return null; // r2: token required const baseline_tok = it.next(); // optional if (it.next() != null) return null; // r2: grammar has no third token // token = 1*tchar (Appendix B) guarantees first.len >= 1 on the wire, // but an argument-less-looking empty token (`Q \n`) still reaches // here as one empty token -- guard before indexing the sign byte. if (first.len == 0) return null; // r1 const sign: QSign = switch (first[0]) { '+' => .cherrypick, '-' => .backout, else => return null, // r1: q-sign is "+" / "-" only }; const target = first[1..]; if (!validateHashToken(.artifact_hash, target)) return null; // r3 var baseline: ?[]const u8 = null; if (baseline_tok) |raw| { if (!validateHashToken(.artifact_hash, raw)) return null; // r3 baseline = raw; } std.debug.assert(target.len == 40 or target.len == 64); std.debug.assert(baseline == null or baseline.?.len == 40 or baseline.?.len == 64); return .{ .sign = sign, .target = target, .baseline = baseline }; } // --------------------------------------------------------------------------- // §4.7.15 R Card // --------------------------------------------------------------------------- /// One parsed R card (§4.7.15 repository-checksum card). Grammar: `r-card = /// "R" SP md5-token LF`. `checksum` is raw -- a hash/checksum position, /// never decoded (§4.7.1). An R card may appear only in a manifest (§5.2) /// and is never required there -- both deferred to manifest assembly, same /// posture as A/B/G/M. pub const RCard = struct { checksum: []const u8 }; /// Parse one already-tokenized R card (§4.7.15). Returns null for bad arity /// or a checksum failing the hash map (`.checksum`, §4.7.1: exactly 32 /// case-insensitive hex). pub fn parseRCard(card: CardLine) ?RCard { std.debug.assert(card.letter == 'R'); var it = card.tokens(); const tok = it.next() orelse return null; // p1: checksum required if (it.next() != null) return null; // r1: grammar has no second token if (!validateHashToken(.checksum, tok)) return null; std.debug.assert(tok.len == 32); return .{ .checksum = tok }; } // --------------------------------------------------------------------------- // S Card (draft-fossil-submanifests-00 §3.6) // --------------------------------------------------------------------------- /// One parsed S card (submanifests §3.6 sub-manifest reference). Grammar: /// `s-card = %x53 SP filename SP hash LF`. `filename` is escape-decoded (the /// 13th decoded token position, §3.3) and borrows the caller's `decode_buf`; /// `hash` is raw -- "the hash is raw (never decoded), validated per /// Section 3.5". /// /// "Parse-time acceptance validates only token shapes and intra-run ordering; /// the tree walk of Section 5.1 enforces hash resolution and the /// least-filename property." So neither the slice-boundary claim nor the /// referenced artifact's own type is checked here: both need artifacts this /// single-card parser cannot see, exactly as the B card's delta-of-delta /// check is deferred. pub const SCard = struct { filename: []const u8, hash: []const u8, }; /// Parse one already-tokenized S card (submanifests §3.6). Returns null for a /// missing filename or hash (the grammar makes both mandatory), a filename /// failing the pathname predicate of §4.6.1, a hash failing the §3.5 hash map /// (40 or 64 case-insensitive hex), or a third token -- §3.2: "The exact-arity /// enumeration of [FossilArtifact], Section 4.2.1 gains the S card: a third /// token on S is rejected." /// Precondition: `decode_buf.len >= filename token length`. pub fn parseSCard(card: CardLine, decode_buf: []u8) ?SCard { std.debug.assert(card.letter == 'S'); var it = card.tokens(); const filename_tok = it.next() orelse return null; // filename required const hash_tok = it.next() orelse return null; // hash required if (it.next() != null) return null; // §3.2: a third token on S is rejected std.debug.assert(decode_buf.len >= filename_tok.len); const filename = decodeEscapes(filename_tok, decode_buf[0..filename_tok.len]); if (!isSimplePathname(filename)) return null; // §3.6 -> §4.6.1 if (!validateHashToken(.artifact_hash, hash_tok)) return null; // §3.5 std.debug.assert(filename.len >= 1); std.debug.assert(hash_tok.len == 40 or hash_tok.len == 64); return .{ .filename = filename, .hash = hash_tok }; } // --------------------------------------------------------------------------- // §4.7.16 T Card // --------------------------------------------------------------------------- /// §4.7.16 tag-sign: the byte glued onto the tagname, selecting the tag /// operation (`tag-sign = "+" / "-" / "*"`). `+` adds, `-` cancels, `*` /// propagates to descendants -- crosslink semantics deferred (§5.4). pub const TSign = enum { add, cancel, propagate, /// The literal wire sign byte glued onto the tagname (§4.7.16 `tag-sign`). /// The single home for the sign->byte mapping the writer emits, the parser /// orders by, and `composeCommitTags` sorts on -- one table, no copies. /// §4.7.16 orders a T run by the FULL name token including this byte, so the /// byte's own order leads the key: `*`(0x2a) < `+`(0x2b) < `-`(0x2d). pub fn byte(self: TSign) u8 { return switch (self) { .add => '+', .cancel => '-', .propagate => '*', }; } }; /// One parsed T card (§4.7.16 tag card). Grammar: `t-card = "T" SP tag-sign /// tagname SP ( hash / "*" ) [ SP value ] LF` (lines 1360-1362). `name` is /// the escape-decoded, sign-stripped tagname remainder; `target` is the raw, /// never-decoded hash, or null for the literal `*` self-referential tag /// (p2); `value` is escape-decoded and null iff absent -- an absent value is /// null (m1), unlike the J card's empty-string default. Repeatable; the /// two-level-ascending run check (§4.5.2) keys on the FULL name token — /// leading sign byte first, then the stripped name, then target (§4.7.16 /// l.1373-1376) — and is enforced in `admitTCard`. pub const TCard = struct { sign: TSign, name: []const u8, target: ?[]const u8, value: ?[]const u8, }; // --- composeCommitTags (repostate §6.2 + artifact §4.7; pure; no I/O) -------- // // Beside the card it builds rather than in the CLI, because the CLI is not its // only writer: `import-git` reconstructs a source repository's branch roots and // must emit the SAME §6.2 card set a native commit does, and a `zit`-module // file cannot reach `cli.zig` (it belongs to the CLI's module, so importing it // is `error: file exists in modules`). Two composers is the alternative, and // the second one drifting is exactly how the importer came to write a lone // `*branch` card with no sym pair and no cancel. `cli` re-exports // these names, so every CLI call site still reads `cli.composeCommitTags`. /// The reserved `sym-` prefix (repo-state §2): a symbolic tag name is stored /// with it. Every branch/tag control tag a commit emits carries it, and every /// name in `ComposeCommitTagsInput.parent_syms` arrives already wearing it — /// so it is public, rather than each caller spelling the literal again. pub const sym_tag_prefix = "sym-"; /// Value inputs to `composeCommitTags`. `branch` non-null starts (or switches /// to) that branch at this check-in; `parent_syms` are the parent's active /// `sym-*` tag names to cancel so the check-in leaves the parent's branch(es) /// — each already carrying the `sym-` prefix, and EXCLUDING the new branch's /// own `sym-<branch>` (the caller drops it, since this commit re-establishes /// it as a propagating tag). `close` marks the check-in a closed leaf. pub const ComposeCommitTagsInput = struct { branch: ?[]const u8 = null, close: bool = false, parent_syms: []const []const u8 = &.{}, }; /// §4.7.16 full-signed-token order: the sign byte leads (`*` 0x2A < `+` 0x2B < /// `-` 0x2D), then the sign-stripped name (the target never breaks a tie here — /// every card is self-referential `*`). Equivalent to comparing the whole /// `<sign><name>` token with `compareBytes`, the key §4.7.16 mandates. pub fn tagTokenLess(_: void, a: TCard, b: TCard) bool { const sa = a.sign.byte(); const sb = b.sign.byte(); if (sa != sb) return sa < sb; return compareBytes(a.name, b.name) == .lt; } /// The one deep, RFC-normative unit of `commit --branch/--close/--tag` and of /// the importer's branch roots, extracted pure so it is reusable and unit-tested /// without a subprocess: it builds a check-in's control tag run (`[]TCard`) from /// value inputs, then sorts it into the §4.7.16 wire order. No I/O, no clock, no /// env; allocates only the result array (and each `sym-*` name) on `arena` /// (value-in/value-out, so it lifts verbatim into a future deep /// `checkin.compose`). /// /// Cards emitted (repostate §6.2 branch creation + artifact §4.7): /// - `branch` set: `T *branch * NAME` and `T *sym-NAME *` (both propagating, /// §6.2) — the branch property plus its symbolic tag; /// - one `T -sym-X *` (cancel) per parent sym X, so the check-in leaves the /// parent's branch(es) (§6.2 sym-cancellation); /// - `close`: `T +closed *` (a self-referential singleton, §4.7 closed leaf). /// /// The result is sorted by the FULL signed name token (§4.7.16/§4.5.2), because /// `create` emits `Manifest.t` verbatim (no internal sort) and the commit /// self-check re-`parse`s the bytes — a mis-ordered run would trip the §4.5.2 /// intra-run check. A safety build drives that order over the result. pub fn composeCommitTags(arena: std.mem.Allocator, in: ComposeCommitTagsInput) error{OutOfMemory}![]TCard { var list: std.ArrayList(TCard) = .empty; errdefer list.deinit(arena); if (in.branch) |name| { std.debug.assert(name.len != 0); try list.append(arena, .{ .sign = .propagate, .name = "branch", .target = null, .value = name }); const sym = try std.mem.concat(arena, u8, &.{ sym_tag_prefix, name }); try list.append(arena, .{ .sign = .propagate, .name = sym, .target = null, .value = null }); } for (in.parent_syms) |x| { std.debug.assert(std.mem.startsWith(u8, x, sym_tag_prefix)); // Negative space: the caller excludes the new branch's own sym, so a // `*sym-NAME` we just added is never also cancelled here. if (in.branch) |name| std.debug.assert(!std.mem.eql(u8, x[sym_tag_prefix.len..], name)); try list.append(arena, .{ .sign = .cancel, .name = x, .target = null, .value = null }); } if (in.close) { try list.append(arena, .{ .sign = .add, .name = "closed", .target = null, .value = null }); } std.mem.sort(TCard, list.items, {}, tagTokenLess); // Postcondition (§4.7.16/§4.5.2): the run is STRICTLY ascending by the full // signed token, so `create` emits it verbatim and a re-parse's intra-run // check passes. Distinct by construction (distinct parent syms, sym-NAME // excluded from cancels, one closed/one tag), so a non-strict pair is a // compose bug, not a wire condition. Safety-gated — free in ReleaseFast. if (std.debug.runtime_safety and list.items.len >= 2) { for (list.items[0 .. list.items.len - 1], list.items[1..]) |prev, next| { std.debug.assert(tagTokenLess({}, prev, next)); } } return list.toOwnedSlice(arena); } /// Point every T card at `hash` (the resolved check-in), asserting none was /// already targeted. A CONTROL artifact's T cards MUST target the check-in, never /// the literal `*` self-reference (§5.4): a control never tags itself. pub fn retargetTCards(cards: []TCard, hash: []const u8) void { std.debug.assert(hash.len == 40 or hash.len == 64); for (cards) |*c| { std.debug.assert(c.target == null); // composed self-referential; retargeted once c.target = hash; } } /// `s` is the tagname after the sign byte is stripped (`tagname = tag-sign /// token`, App. B) -- non-empty per grammar, and MUST NOT consist entirely /// of hexadecimal digits at any length (§4.7.16-r2), so a tag name stays /// distinguishable from a hash prefix. Case-insensitive per the hexdig-ci /// production a hash prefix itself uses (§3.6). fn isAllHexCi(s: []const u8) bool { std.debug.assert(s.len >= 1); for (s) |c| { if (!isHexCi(c)) return false; } return true; } /// Parse one already-tokenized T card (§4.7.16). Returns null for bad arity /// (r4), a decoded name that is empty or not `+`/`-`/`*`-prefixed (r1), a /// remainder that is entirely hex digits (r2), or a target failing `*` / the /// hash map (r3). /// Precondition: `decode_buf.len >= name_tok.len + (value_tok orelse "").len`. pub fn parseTCard(card: CardLine, decode_buf: []u8) ?TCard { std.debug.assert(card.letter == 'T'); var it = card.tokens(); const name_tok = it.next() orelse return null; // p1: name required const target_tok = it.next() orelse return null; // p1: target required const value_tok = it.next(); // optional if (it.next() != null) return null; // r4: grammar has no fourth token std.debug.assert(decode_buf.len >= name_tok.len); const name_decoded = decodeEscapes(name_tok, decode_buf[0..name_tok.len]); if (name_decoded.len == 0) return null; // r1: needs at least the sign byte const sign: TSign = switch (name_decoded[0]) { '+' => .add, '-' => .cancel, '*' => .propagate, else => return null, // r1: tag-sign is "+" / "-" / "*" only }; const remainder = name_decoded[1..]; if (remainder.len == 0) return null; // tagname = tag-sign token, token = 1*tchar if (isAllHexCi(remainder)) return null; // r2: stays distinguishable from a hash prefix // m3: target is never decoded -- "*" here means the literal wire byte. var target: ?[]const u8 = null; if (!std.mem.eql(u8, target_tok, "*")) { if (!validateHashToken(.artifact_hash, target_tok)) return null; // r3 target = target_tok; } var value: ?[]const u8 = null; // m1: absent value is null, not "" if (value_tok) |raw| { std.debug.assert(decode_buf.len >= name_tok.len + raw.len); value = decodeEscapes(raw, decode_buf[name_tok.len..][0..raw.len]); // m2 } std.debug.assert(remainder.len >= 1); std.debug.assert(target == null or target.?.len == 40 or target.?.len == 64); return .{ .sign = sign, .name = remainder, .target = target, .value = value }; } // --------------------------------------------------------------------------- // §4.7.17 U Card // --------------------------------------------------------------------------- /// Anonymous-login substitute (§4.7.17, lines 1416-1419): a bare `U` line or /// a `U` followed by an empty token both yield this literal, never null or /// "". const ANONYMOUS_LOGIN = "anonymous"; /// One parsed U card (§4.7.17 user card). Grammar: `u-card = "U" [ SP /// [ login ] ] LF`. `login` is the escape-decoded login token, or /// `ANONYMOUS_LOGIN` when the token is absent or empty (m1) -- this card's /// grammar takes precedence over the general non-empty-token rule other /// single-token cards enforce (m2, contrast `parseNCard`). Single-occurrence; /// required on a wiki artifact (§5.2/App. C) -- deferred to manifest /// assembly. pub const UCard = struct { login: []const u8 }; /// Parse one already-tokenized U card (§4.7.17). Returns null only for a /// second token -- the grammar has room for exactly one, possibly-empty, /// possibly-absent login. /// Precondition: `decode_buf.len >= login token length (0 if absent/empty)`. pub fn parseUCard(card: CardLine, decode_buf: []u8) ?UCard { std.debug.assert(card.letter == 'U'); var it = card.tokens(); const login_tok = it.next(); // optional -- bare `U\n` has args == null if (it.next() != null) return null; // r1: grammar has no second token const login: []const u8 = if (login_tok) |tok| blk: { if (tok.len == 0) break :blk ANONYMOUS_LOGIN; // m1: empty token std.debug.assert(decode_buf.len >= tok.len); break :blk decodeEscapes(tok, decode_buf[0..tok.len]); } else ANONYMOUS_LOGIN; // m1: bare U line std.debug.assert(login.len >= 1); return .{ .login = login }; } // --------------------------------------------------------------------------- // §4.7.18 W Card // --------------------------------------------------------------------------- /// One parsed W card (§4.7.18 body card). `body` borrows the raw, opaque /// payload -- located by byte count, MAY contain 0x0A, never line-split /// (lines 1438-1440). `next` is the offset one past the body's /// terminating LF, where the card loop resumes. pub const WCard = struct { body: []const u8, next: usize }; /// Parse one W card starting at `artifact[start]` (the 'W' letter), /// byte-counted rather than tokenized -- the body may embed LF and so /// cannot flow through `tokenizeCardLine` (§4.7.18, l.422-433). Returns /// null on any rejection: bad grammar, digit-accumulator overflow (r1), a /// declared size exceeding the remaining artifact (r2), a non-LF byte /// after the body (r3), or a terminator LF that is the artifact's final /// byte (r4). /// Precondition: `start < artifact.len` and `artifact[start] == 'W'` (the /// card loop dispatches by letter). /// Postcondition on success: `body.len` equals the parsed size and /// `next < artifact.len`. pub fn parseWCard(artifact: []const u8, start: usize) ?WCard { std.debug.assert(start < artifact.len); std.debug.assert(artifact[start] == 'W'); // w-card = %x57 SP size LF body LF (l.1429). if (start + 1 >= artifact.len) return null; if (artifact[start + 1] != ' ') return null; // Locate the size-line terminator. Bounded by artifact.len. var size_lf: usize = start + 2; while (size_lf < artifact.len and artifact[size_lf] != '\n') : (size_lf += 1) {} if (size_lf >= artifact.len) return null; // no LF before end // p2/r1: accumulate leading decimal digits only, stop at the first // non-digit byte, never re-check the remainder (w1: "12x" accepted; // w2: no leading digit parses as zero). Overflow MUST reject (r1). // Loop bounded by the size-line slice, itself bounded by artifact.len. var size: usize = 0; for (artifact[start + 2 .. size_lf]) |c| { if (c < '0' or c > '9') break; const mul = @mulWithOverflow(size, 10); if (mul[1] != 0) return null; const add = @addWithOverflow(mul[0], c - '0'); if (add[1] != 0) return null; size = add[0]; } const body_start = size_lf + 1; std.debug.assert(body_start <= artifact.len); // r2: bound the declared size against what remains before consuming. const remaining = artifact.len - body_start; if (size > remaining) return null; const body_end = body_start + size; std.debug.assert(body_end <= artifact.len); // r4: the position one past the terminator LF must stay addressable. if (body_end + 1 >= artifact.len) return null; // r3: the byte right after the counted body must be LF. m1: the body // itself is never scanned -- it is sliced by offset, not searched. if (artifact[body_end] != '\n') return null; const body = artifact[body_start..body_end]; const next = body_end + 1; std.debug.assert(body.len == size); std.debug.assert(next < artifact.len); return .{ .body = body, .next = next }; } // --------------------------------------------------------------------------- // §4.7.19 Z Card // --------------------------------------------------------------------------- /// One parsed Z card (§4.7.19 self-checksum card). `checksum` is the raw /// md5-token, never decoded (§6.1). The "structurally last, final 35 /// bytes" property (m1) is enforced by the §6.2 positional framing /// (`verifyZCard`), not here -- this validates only token syntax. pub const ZCard = struct { checksum: []const u8 }; /// Parse one already-tokenized Z card (§4.7.19). Returns null for bad /// arity (r2: zero or a second token) or a token failing the 32-hex-ci /// checksum rule (r1, §6.1). pub fn parseZCard(card: CardLine) ?ZCard { std.debug.assert(card.letter == 'Z'); var it = card.tokens(); const tok = it.next() orelse return null; // r2: token required if (it.next() != null) return null; // r2: grammar has no second token if (!validateHashToken(.checksum, tok)) return null; // r1: 32hexdig-ci std.debug.assert(tok.len == 32); return .{ .checksum = tok }; } // --------------------------------------------------------------------------- // §5 Structural Artifact Types // --------------------------------------------------------------------------- /// Card-presence census over one artifact's cards. Built by the (later) /// single-pass parser; classification and validity below consume this /// summary instead of re-scanning raw card bytes. pub const Census = struct { /// Bit (letter - 'A') set iff at least one card of that letter was /// seen in the artifact. letters: u32 = 0, /// Count of hash tokens recorded across all P cards. Only "zero / one /// / more than one" is ever distinguished downstream (§5.4-r5), so a /// future producer may saturate rather than track the exact count. p_parents: u8 = 0, /// At least one T card targets the literal `*` -- self-referential /// (§4.7.16 p2; consumed by §5.4 checks 1 and 2). t_self_ref: bool = false, /// At least one T card targets a hash, not `*` (§5.4 check 2). t_not_self_ref: bool = false, /// At least one T card's sign is not `+` (§4.7.16 tag-sign; §5.4 /// check 2). t_not_plus: bool = false, /// At least one F card carries no hash -- the §4.7.6 delete marker. /// Recorded because submanifests §4.4 forbids it in a SUBMANIFEST /// ("Every F card in a SUBMANIFEST MUST carry a hash"), a per-card fact /// the letter-presence bits alone cannot express. f_hashless: bool = false, /// Whether a card of `letter` was recorded in this census. pub fn has(self: Census, letter: u8) bool { std.debug.assert(letter >= 'A' and letter <= 'Z'); return (self.letters & (@as(u32, 1) << @intCast(letter - 'A'))) != 0; } }; /// The fourteen type-setting letters (§5.3 Table 5, plus S per /// draft-fossil-submanifests-00 §4.3), ascending. Card order on the wire is /// non-decreasing (§4.4), so folding this array in ascending order and /// unconditionally overwriting on each match reproduces "the alphabetically /// latest present type-setting card wins" (r1) without needing the actual /// card sequence. const type_setting_letters = [_]u8{ 'A', 'B', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'Q', 'R', 'S' }; /// §5.3 Table 5: the type one type-setting letter assigns. submanifests §4.3: /// "S joins B, F, Q, and R as a MANIFEST-setting letter" -- no letter assigns /// SUBMANIFEST directly. fn typeSettingType(letter: u8) ArtifactType { return switch (letter) { 'A' => .attachment, 'B', 'F', 'Q', 'R', 'S' => .manifest, 'E' => .event, 'G', 'H', 'I' => .forum, 'J', 'K' => .ticket, 'L' => .wiki, 'M' => .cluster, else => unreachable, // caller only passes type_setting_letters }; } /// §5.3: determine an artifact's type from its card census. The eight /// remaining letters (C, D, N, P, T, U, W, Z) never set the type (m1); if /// no type-setting letter is present, fall back per p2. Total: always /// returns a concrete code-1..9 type, never the code-0 "undetermined" /// sentinel (§5.1-m1) -- that sentinel is modelled only as the absence of /// an input census entry, never as this function's output. /// /// The submanifests §4.3 reassignment is the final step here rather than in /// `classify`, because §4.3 orders it "after the fallback ... finalizes the /// type and before the card-legality checks" -- which is exactly this /// function's exit. Putting it here also keeps the interface deep: every /// caller gets the FINAL type, never a provisional MANIFEST it would have to /// correct for itself. /// /// §9.1 ("MUST NOT commit to a type while cards are still being read") is /// satisfied structurally, not by a flag: the card loop only accumulates /// `Census`, and this function runs strictly after the last card is read. pub fn determineType(c: Census) ArtifactType { var result: ?ArtifactType = null; // Bounded: exactly type_setting_letters.len iterations. for (type_setting_letters) |letter| { if (c.has(letter)) result = typeSettingType(letter); } const finalized = result orelse fallback(c); // submanifests §4.3: "an artifact whose finalized type is MANIFEST and // which contains no D card MUST be reclassified as SUBMANIFEST (code 9). // The reassignment is the sole assignment path for SUBMANIFEST." No // previously-valid artifact changes classification: a D-less MANIFEST was // already rejected under §5.2, D being in MANIFEST's required set. const t: ArtifactType = if (finalized == .manifest and !c.has('D')) .submanifest else finalized; std.debug.assert(@intFromEnum(t) >= 1 and @intFromEnum(t) <= 9); std.debug.assert(t != .submanifest or !c.has('D')); return t; } /// §5.3 p2 fallback, reached only when no type-setting letter was seen: /// MANIFEST if a C card was present or P-card parents were recorded, /// CONTROL otherwise. The RFC's third fallback disjunct ("F card file /// entries recorded") is unreachable through this path -- F is itself /// type-setting, so an artifact carrying F entries already resolved to /// MANIFEST in the loop above and never reaches fallback. fn fallback(c: Census) ArtifactType { // Precondition (negative space): no type-setting letter present. for (type_setting_letters) |letter| std.debug.assert(!c.has(letter)); return if (c.has('C') or c.p_parents >= 1) .manifest else .control; } /// Comptime helper: OR together the per-letter bits of a Table 4 letter /// list into one mask. fn maskOfLetters(comptime letters: []const u8) u32 { var m: u32 = 0; for (letters) |l| m |= @as(u32, 1) << @intCast(l - 'A'); return m; } /// §5.2 Table 4 "Allowed cards" column, one bit per letter per type. const allowed_mask = std.EnumArray(ArtifactType, u32).init(.{ // submanifests §4.2 Table 1 revises the MANIFEST row to add S. .manifest = maskOfLetters("BCDFNPQRSTUZ"), .cluster = maskOfLetters("MZ"), .control = maskOfLetters("DTUZ"), .wiki = maskOfLetters("CDLNPUWZ"), .ticket = maskOfLetters("DJKUZ"), .attachment = maskOfLetters("ACDNUZ"), .event = maskOfLetters("CDENPTUWZ"), .forum = maskOfLetters("DGHINPUWZ"), .submanifest = maskOfLetters("FSZ"), }); /// §5.2 Table 4 "Required cards" column, one bit per letter per type. const required_mask = std.EnumArray(ArtifactType, u32).init(.{ .manifest = maskOfLetters("DZ"), .cluster = maskOfLetters("MZ"), .control = maskOfLetters("DTUZ"), .wiki = maskOfLetters("DLUWZ"), .ticket = maskOfLetters("DJKUZ"), .attachment = maskOfLetters("ADZ"), .event = maskOfLetters("DEWZ"), .forum = maskOfLetters("DUWZ"), .submanifest = maskOfLetters("Z"), }); comptime { // Table 4 invariant: every required card is also allowed, for all // nine types -- a transcription guard against the two columns // silently disagreeing. for (std.enums.values(ArtifactType)) |t| { std.debug.assert(required_mask.get(t) & allowed_mask.get(t) == required_mask.get(t)); } } pub const ClassifyError = error{ /// §5.2-r1: a card letter outside the finalized type's allowed set. DisallowedCard, /// §5.2-r2: a required card letter is absent. MissingRequiredCard, /// §5.4 check 1: CONTROL with a self-referential T card. ControlSelfTag, /// §5.4 check 2: EVENT with a T card that does not target itself. EventTagNotSelfRef, /// §5.4 check 2: EVENT with a T card lacking the `+` prefix. EventTagNotPlus, /// §5.4 check 3: FORUM with both an H and an I card. ForumHeadAndReply, /// §5.4 check 4: FORUM whose P card lists more than one parent. ForumMultiParent, /// submanifests §4.4: a MANIFEST carrying both a B card and an S card. ManifestBaselineAndSCard, /// submanifests §4.4: a MANIFEST carrying both an F card and an S card /// -- the file set is conveyed by one or the other, never a mixture. ManifestFileAndSCard, /// submanifests §4.4: a SUBMANIFEST carrying both F and S cards. SubmanifestFileAndSCard, /// submanifests §4.4: a SUBMANIFEST carrying neither an F nor an S card. SubmanifestEmpty, /// submanifests §4.4: an F card in a SUBMANIFEST with no hash -- the /// §4.7.6 delete marker is permitted only in a delta manifest. SubmanifestFileWithoutHash, }; /// §5.2: reject any card letter outside `t`'s allowed set, or any missing /// required letter. fn checkLegality(t: ArtifactType, c: Census) ClassifyError!void { const allowed = allowed_mask.get(t); const required = required_mask.get(t); if (c.letters & ~allowed != 0) return error.DisallowedCard; // r1 if (c.letters & required != required) return error.MissingRequiredCard; // r2 } /// §5.4: the four per-type semantic checks beyond card legality, plus the /// three submanifests §4.4 adds. fn checkSemantics(t: ArtifactType, c: Census) ClassifyError!void { switch (t) { // submanifests §4.4, first two items. Both letters are allowed in a // MANIFEST by §4.2, so only this check separates a tree manifest from // an artifact mixing conveyance mechanisms. .manifest => { if (c.has('B') and c.has('S')) return error.ManifestBaselineAndSCard; if (c.has('F') and c.has('S')) return error.ManifestFileAndSCard; }, // submanifests §4.4, third item: "A SUBMANIFEST MUST contain at least // one F card or at least one S card, and MUST NOT contain both. Every // F card in a SUBMANIFEST MUST carry a hash." // // The empty case is unreachable from bytes -- reaching SUBMANIFEST at // all needs a finalized MANIFEST, and every D-less route to MANIFEST // that carries neither F nor S (B, Q, R, or the C/P fallback) is // already dead at §4.2 legality. The check is stated over the census // regardless, because §4.4 states it over the artifact. .submanifest => { if (c.has('F') and c.has('S')) return error.SubmanifestFileAndSCard; if (!c.has('F') and !c.has('S')) return error.SubmanifestEmpty; if (c.f_hashless) return error.SubmanifestFileWithoutHash; }, .control => { if (c.t_self_ref) return error.ControlSelfTag; // check 1 }, .event => { if (c.t_not_self_ref) return error.EventTagNotSelfRef; // check 2 if (c.t_not_plus) return error.EventTagNotPlus; // check 2 }, .forum => { if (c.has('H') and c.has('I')) return error.ForumHeadAndReply; // check 3 if (c.p_parents > 1) return error.ForumMultiParent; // check 4 }, else => {}, } } /// §5 deep entry point: finalize the type (§5.3), then card legality /// (§5.2), then per-type semantics (§5.4) -- strictly in that order, per /// §5.2-m1 and §5.3-m2. pub fn classify(c: Census) ClassifyError!ArtifactType { const t = determineType(c); try checkLegality(t, c); try checkSemantics(t, c); std.debug.assert(@intFromEnum(t) >= 1 and @intFromEnum(t) <= 9); return t; } // --------------------------------------------------------------------------- // §4/§5 Manifest Assembly // --------------------------------------------------------------------------- /// A fully-decoded artifact (the Deck shape, per the operator-approved /// fsl_deck/go-libfossil design): one field per card type, holding every /// card's decoded data, not just the type verdict. `arena_state` OWNS every /// slice below except the raw wire-borrows (hashes/timestamps/W body), /// which point into the caller's `bytes` -- the caller must keep `bytes` /// alive for the Manifest's lifetime and must call `deinit` exactly once. pub const Manifest = struct { arena_state: std.heap.ArenaAllocator, // §5.1-m1: a successful parse always finalizes a code-1..8 type -- // "not yet determined" never survives to here, it is modelled as // `parse` returning an error, not as a null field on this struct. kind: ArtifactType, // §4.5.1 single-occurrence cards: null iff the letter was absent. a: ?ACard, b: ?BCard, c: ?CCard, d: ?DCard, e: ?ECard, g: ?GCard, h: ?HCard, i: ?ICard, k: ?KCard, l: ?LCard, n: ?NCard, r: ?RCard, u: ?UCard, z: ?ZCard, /// W's body only -- `WCard.next` is a parse-loop cursor, not artifact /// data, so it never belongs on the retained Manifest. w: ?[]const u8, // §4.5.2 repeatable cards: arena slice in wire order; empty iff absent. f: []const FCard, j: []const JCard, m: []const MCard, p: []const PCard, q: []const QCard, /// The S run (submanifests §3.6), in wire order. Defaulted to empty /// because "empty iff absent" is exactly what every construction site /// predating sub-manifests means; `parse` always sets it explicitly. s: []const SCard = &.{}, t: []const TCard, /// The complete file set of a tree manifest, memoized by `flattenTree` /// (submanifests §5.1). Null on every flat or delta manifest, and null on /// a tree manifest until it is flattened -- `parse` never sets it, because /// the walk needs a resolver and the parser has no store. Owned by /// `arena_state`: the sub-manifests the walk borrowed may be freed the /// moment `flattenTree` returns. flattened: ?[]const FCard = null, /// Frees every decoded slice this Manifest owns. Raw fields borrow the /// caller's input bytes, unaffected -- the caller owns those. pub fn deinit(self: *Manifest) void { self.arena_state.deinit(); } /// submanifests §5.1: derive this tree manifest's complete file set /// through the tree walk and memoize it in `flattened`, so every /// downstream consumer reads it through the ordinary §8 enumeration seam /// and "MUST NOT distinguish a walked enumeration from a flat or delta /// one" (§5.1 closing paragraph). /// /// §5.2 hard failure: on any `TreeError` the memo is left null and no /// partial set is observable -- "An implementation MUST NOT present a /// partially resolved tree as a complete file set." Every emitted card is /// copied into this manifest's own arena, so the resolver's sub-manifest /// buffers need not outlive the call. pub fn flattenTree(self: *Manifest, resolver: SubResolver) FlattenError!void { std.debug.assert(self.s.len != 0); // §5: a tree manifest is exactly an S-bearing one std.debug.assert(self.f.len == 0); // §4.4: never both F and S std.debug.assert(self.b == null); // §4.4: never both B and S std.debug.assert(self.flattened == null); // memoized once const arena = self.arena_state.allocator(); var out: std.ArrayList(FCard) = .empty; var walk = TreeWalk.init(self.s, resolver); while (try walk.next()) |f| { try out.append(arena, .{ .filename = try arena.dupe(u8, f.filename), .hash = if (f.hash) |h| try arena.dupe(u8, h) else null, .perm = if (f.perm) |p| try arena.dupe(u8, p) else null, .old_name = if (f.old_name) |o| try arena.dupe(u8, o) else null, .mode = f.mode, }); } // Assigned last: until this line the walk may still fail, and a // half-filled `out` must never become visible as the file set. self.flattened = try out.toOwnedSlice(arena); } }; /// Growing accumulator threaded alongside `RunState` through the card loop, /// one lane per card type, mirroring `Manifest`'s shape. Kept separate from /// `RunState` -- this refactor adds a retention lane, it does not rewire /// the §4.4/§4.5 gate `RunState` already enforces. All storage lives on the /// caller's arena. const ManifestBuilder = struct { a: ?ACard = null, b: ?BCard = null, c: ?CCard = null, d: ?DCard = null, e: ?ECard = null, g: ?GCard = null, h: ?HCard = null, i: ?ICard = null, k: ?KCard = null, l: ?LCard = null, n: ?NCard = null, r: ?RCard = null, u: ?UCard = null, z: ?ZCard = null, w: ?[]const u8 = null, f: std.ArrayList(FCard) = .empty, j: std.ArrayList(JCard) = .empty, m: std.ArrayList(MCard) = .empty, p: std.ArrayList(PCard) = .empty, q: std.ArrayList(QCard) = .empty, s: std.ArrayList(SCard) = .empty, t: std.ArrayList(TCard) = .empty, /// Finalize the seven repeatable lists into arena slices and hand back a /// Manifest that owns `arena_state` (moved in by value -- safe: every /// decoded slice above points into a heap buffer node the arena holds, /// never into this struct itself). `kind` is `classify`'s output; the /// retention<->validation invariant against `RunState.census` is the /// caller's job (`parse`), since `census` lives there, not here. fn finish(self: *ManifestBuilder, arena_state: *std.heap.ArenaAllocator, kind: ArtifactType) std.mem.Allocator.Error!Manifest { const arena = arena_state.allocator(); // Finalize every owned slice BEFORE copying the arena by value. A // toOwnedSlice can append a node to the arena's used_list, and Zig // evaluates struct-literal fields in source order; copying arena_state // ahead of these would capture a stale node list and leak whatever a // later slice allocates. Locals force all arena growth to happen first. const f = try self.f.toOwnedSlice(arena); const j = try self.j.toOwnedSlice(arena); const m = try self.m.toOwnedSlice(arena); const p = try self.p.toOwnedSlice(arena); const q = try self.q.toOwnedSlice(arena); const s = try self.s.toOwnedSlice(arena); const t = try self.t.toOwnedSlice(arena); return .{ .arena_state = arena_state.*, .kind = kind, .a = self.a, .b = self.b, .c = self.c, .d = self.d, .e = self.e, .g = self.g, .h = self.h, .i = self.i, .k = self.k, .l = self.l, .n = self.n, .r = self.r, .u = self.u, .z = self.z, .w = self.w, .f = f, .j = j, .m = m, .p = p, .q = q, .s = s, .t = t, }; } }; /// §4's per-card/per-run rejections all collapse to `SyntaxError`, matching /// the module's standing "every rejection reason collapses to null/false" /// posture; §5's `classify` rejections keep their distinct variants, giving /// per-clause coverage for §5.2/§5.4 without inventing a parallel taxonomy. /// `OutOfMemory` surfaces the arena's allocation failures (§4.3 decode /// scratch) -- closed set, no `anyerror` across this boundary. pub const ParseError = error{ SyntaxError, OutOfMemory } || ClassifyError; /// Mutable state threaded through one card loop run: the §4.4 order /// tracker, §4.5.1 occurrence guard, §4.5.2/§4.6.3 F-run admission, the /// two remaining §4.5.2 intra-run anchors (J, M single-key; T two-level), /// and the growing §5 census the loop folds every card into. const RunState = struct { order: OrderState = .{}, occ: SingleOccurrenceSet = .{}, fadmit: FCardAdmission = .{}, prev_j: ?[]const u8 = null, prev_m: ?[]const u8 = null, /// submanifests §3.4: the previous S card's DECODED filename, the key /// the S run must strictly ascend by under the canonical comparator. prev_s: ?[]const u8 = null, prev_t: ?struct { sign: TSign, name: []const u8, target: []const u8 } = null, census: Census = .{}, }; /// Mark `letter` present in the running census (§5 card-presence bit). fn censusMark(rs: *RunState, letter: u8) void { std.debug.assert(isCardLetter(letter)); rs.census.letters |= @as(u32, 1) << @intCast(letter - 'A'); } /// §4.5.2 single-key ascending check shared by the J, M, and S runs (F has /// its own admission type, `FCardAdmission`, since it also carries the /// §4.6.3 reserved-name drop). Rejects iff `key` does not strictly exceed /// the previous key in the same run. fn admitAscending(prev: *?[]const u8, key: []const u8) ParseError!void { if (prev.*) |p| { if (compareBytes(p, key) != .lt) return error.SyntaxError; } prev.* = key; } /// True for the ten card letters whose parser decodes at least one field via /// `decodeEscapes` -- these need a scratch buffer; the other twelve tokenized /// letters carry only raw (hash/checksum/timestamp/sign) positions and need /// none. submanifests §3.3: "The decoder ... applies at exactly 13 token /// positions across 10 card letters: the 12 positions enumerated in /// [FossilArtifact], Section 4.3.1, and the S card filename." fn letterNeedsDecodeBuf(letter: u8) bool { return switch (letter) { 'A', 'C', 'F', 'H', 'J', 'L', 'N', 'S', 'T', 'U' => true, else => false, }; } /// §4.5.2 T two-level ascending check plus the §5.4 census flags a T card /// contributes (self-ref vs. targeted, sign != '+'). `target` folds the /// self-ref sentinel to the literal wire byte `*` (ledger §4.5.2 reading /// #1) so the sort key is always a concrete byte string. §4.7.16 (l.1373- /// 1376): the primary ordering key is the FULL name token INCLUDING its /// leading sign character, not the sign-stripped remainder -- the sign byte /// is compared first, so a run may mix signs (`*branch`, `+closed`, /// `-sym-x`) as long as each full token strictly exceeds the previous. /// /// §4.7.16 (lines 1373-1376) refines §4.5.2 Table 2: the primary ordering key /// is the FULL name token including its leading sign byte, not the sign- /// stripped tag name. That full-token order decomposes losslessly into the /// sign byte (`*` < `+` < `-`) followed by the two-level `compareTag` on the /// stripped name then target -- so an interleaved propagate/cancel branch run /// (`T *sym-x *`, `T -sym-a *`) ascends as Fossil emits it. fn admitTCard(arena: std.mem.Allocator, card: CardLine, decode_buf: []u8, rs: *RunState, mb: *ManifestBuilder) ParseError!void { const tc = parseTCard(card, decode_buf) orelse return error.SyntaxError; const target = tc.target orelse "*"; if (rs.prev_t) |prev| { const order = switch (std.math.order(prev.sign.byte(), tc.sign.byte())) { .eq => compareTag(prev.name, prev.target, tc.name, target), else => |sign_order| sign_order, }; if (order != .lt) return error.SyntaxError; } rs.prev_t = .{ .sign = tc.sign, .name = tc.name, .target = target }; if (tc.target == null) rs.census.t_self_ref = true else rs.census.t_not_self_ref = true; if (tc.sign != .add) rs.census.t_not_plus = true; try mb.t.append(arena, tc); } /// Dispatch one already-tokenized non-W card to its §4.7.x parser, run the /// §4.5.2 intra-run check where the letter has one, and mark it present in /// `rs.census`. `decode_buf` is a fresh arena slice sized to the card's raw /// arg bytes -- always sufficient, since no parser's decoded fields exceed /// the raw bytes they are decoded from. fn admitTokenized(arena: std.mem.Allocator, card: CardLine, decode_buf: []u8, rs: *RunState, mb: *ManifestBuilder) ParseError!void { switch (card.letter) { 'A' => mb.a = parseACard(card, decode_buf) orelse return error.SyntaxError, 'B' => mb.b = parseBCard(card) orelse return error.SyntaxError, 'C' => mb.c = parseCCard(card, decode_buf) orelse return error.SyntaxError, 'D' => mb.d = parseDCard(card) orelse return error.SyntaxError, 'E' => mb.e = parseECard(card) orelse return error.SyntaxError, 'F' => { const fc = parseFCard(card, decode_buf) orelse return error.SyntaxError; _ = rs.fadmit.admit(fc.filename) catch return error.SyntaxError; // §4.5.2/§4.6.3 // submanifests §4.4 needs "did any F card omit its hash?" at // classification time, which the letter-presence bits cannot say. if (fc.hash == null) rs.census.f_hashless = true; try mb.f.append(arena, fc); // retained regardless of admit's drop verdict }, 'G' => mb.g = parseGCard(card) orelse return error.SyntaxError, 'H' => mb.h = parseHCard(card, decode_buf) orelse return error.SyntaxError, 'I' => mb.i = parseICard(card) orelse return error.SyntaxError, 'J' => { const jc = parseJCard(card, decode_buf) orelse return error.SyntaxError; try admitAscending(&rs.prev_j, jc.field); try mb.j.append(arena, jc); }, 'K' => mb.k = parseKCard(card) orelse return error.SyntaxError, 'L' => mb.l = parseLCard(card, decode_buf) orelse return error.SyntaxError, 'M' => { const mc = parseMCard(card) orelse return error.SyntaxError; try admitAscending(&rs.prev_m, mc.hash); try mb.m.append(arena, mc); }, 'N' => mb.n = parseNCard(card, decode_buf) orelse return error.SyntaxError, 'P' => { const pc = parsePCard(card) orelse return error.SyntaxError; const sum = @as(usize, rs.census.p_parents) + pc.count; rs.census.p_parents = @intCast(@min(sum, 2)); // §5.4-r5: only 0/1/>1 matter try mb.p.append(arena, pc); }, 'Q' => { const qc = parseQCard(card) orelse return error.SyntaxError; try mb.q.append(arena, qc); }, 'R' => mb.r = parseRCard(card) orelse return error.SyntaxError, 'S' => { const sc = parseSCard(card, decode_buf) orelse return error.SyntaxError; try admitAscending(&rs.prev_s, sc.filename); // submanifests §3.4 try mb.s.append(arena, sc); }, 'T' => try admitTCard(arena, card, decode_buf, rs, mb), 'U' => mb.u = parseUCard(card, decode_buf) orelse return error.SyntaxError, 'Z' => mb.z = parseZCard(card) orelse return error.SyntaxError, else => unreachable, // caller excludes 'W'; tokenizeCardLine admits only the 22 letters } censusMark(rs, card.letter); } /// Parse and admit exactly one card at `content[pos]`: frame the card /// region (byte-count for W, LF-scan + tokenize otherwise), apply the /// §4.4 order gate and §4.5.1 occurrence gate, then (non-W) dispatch to /// the §4.7.x grammar and §4.5.2 intra-run check. Returns the position /// immediately after the card. Bound: the shortest legal card is `X\n` (2 /// bytes), so the return value always exceeds `pos`. fn admitCard(arena: std.mem.Allocator, content: []const u8, pos: usize, rs: *RunState, mb: *ManifestBuilder) ParseError!usize { std.debug.assert(pos < content.len); const letter = content[pos]; if (letter == 'W') { const w = parseWCard(content, pos) orelse return error.SyntaxError; if (!rs.order.admit(letter)) return error.SyntaxError; // §4.4 if (!rs.occ.admit(letter)) return error.SyntaxError; // §4.5.1 censusMark(rs, letter); mb.w = w.body; std.debug.assert(w.next > pos); return w.next; } const lf = std.mem.indexOfScalarPos(u8, content, pos, '\n') orelse return error.SyntaxError; const card = tokenizeCardLine(content[pos .. lf + 1]) orelse return error.SyntaxError; if (!rs.order.admit(letter)) return error.SyntaxError; // §4.4 if (!rs.occ.admit(letter)) return error.SyntaxError; // §4.5.1 var decode_buf: []u8 = &.{}; if (letterNeedsDecodeBuf(letter)) { const arg_len = if (card.args) |a| a.len else 0; decode_buf = try arena.alloc(u8, arg_len); // may propagate OutOfMemory } try admitTokenized(arena, card, decode_buf, rs, mb); std.debug.assert(lf + 1 > pos); return lf + 1; } /// Parse a structural artifact from its bytes: §4 framing and card grammar, /// then §5 classification. `bytes` is the raw (possibly signature-wrapped) /// artifact; the full pipeline is `frame` -> §5.5 pre-filter -> card loop -> /// `classify`. Returns a fully-populated, data-carrying `Manifest` (every /// decoded card retained, not just the type verdict) or a `ParseError` -- /// never a partial result. The returned Manifest owns an arena; the caller /// must call `manifest.deinit()` exactly once and must keep `bytes` alive /// for the Manifest's lifetime (raw fields borrow it, zero-copy). pub fn parse(allocator: std.mem.Allocator, bytes: []const u8) ParseError!Manifest { const content = frame(bytes) orelse return error.SyntaxError; // §4.1/§6.2 return assemble(allocator, content); } /// Z-tolerant read-window parse: identical to `parse` for every Z-absent or /// Z-matching input, but additionally succeeds on a structural artifact whose /// §6.2 Z self-checksum does NOT match (it frames via `frameNoZ`, skipping /// gate 4). The window verb reports the mismatch instead of rejecting /// (contracts/artifact.md B-artifact-5); a genuine framing (gates 1-3), /// grammar, or classification fault still yields a `ParseError`, so a blob is /// still distinguished from a structural artifact. The caller reads /// `verifyZCard(bytes)` itself to render the verdict — `parseWindow` never /// gates on it. Same ownership contract as `parse`. pub fn parseWindow(allocator: std.mem.Allocator, bytes: []const u8) ParseError!Manifest { const content = frameNoZ(bytes) orelse return error.SyntaxError; // §4.1 gates 1-3 return assemble(allocator, content); } /// §5.5 pre-filter + §4 card loop + §5 classification over an already-framed /// artifact (`content` is the wrapper-stripped, gate-passed body from `frame` /// or `frameNoZ`). The one card-assembly pipeline both `parse` and /// `parseWindow` share, so the Z-gate policy is the ONLY difference between /// them and no card grammar is duplicated. Same ownership contract as `parse`. fn assemble(allocator: std.mem.Allocator, content: []const u8) ParseError!Manifest { std.debug.assert(content.len >= 10); // frame's gate-3 postcondition // §5.5 well-formedness pre-filter, as revised by submanifests §4.5: "an // implementation may reject any input whose first card letter falls in N // through Z, excluding S ... The exclusion is required because an // interior sub-manifest's smallest allowed card letter is S." Card order // is non-decreasing, so a first letter above 'M' can only satisfy a type // whose smallest required letter is above 'M' -- SUBMANIFEST, reached // through S, is the only one. Everything else fails the same way the // full parse eventually would (§4.1.2): this only fast-paths. if (content[0] > 'M' and content[0] != 'S') return error.SyntaxError; std.debug.assert((content[0] >= 'A' and content[0] <= 'M') or content[0] == 'S'); // §4.4 ownership flip: the arena is freed on the error path only. On // success it is moved by value into the returned Manifest (via // `mb.finish`) -- the caller owns it from there and calls `deinit`. var arena_state = std.heap.ArenaAllocator.init(allocator); errdefer arena_state.deinit(); const arena = arena_state.allocator(); var rs: RunState = .{}; var mb: ManifestBuilder = .{}; var pos: usize = 0; const LoopState = enum { parse_card, done }; state: switch (LoopState.parse_card) { .parse_card => { if (pos >= content.len) continue :state .done; const next = try admitCard(arena, content, pos, &rs, &mb); std.debug.assert(next > pos); // strict progress bound pos = next; continue :state .parse_card; }, .done => {}, } std.debug.assert(pos == content.len); // §4.1: unconsumed bytes never happen here const kind = try classify(rs.census); // §5.3 -> §5.2 -> §5.4 const manifest = try mb.finish(&arena_state, kind); assertRetentionMatchesCensus(manifest, rs.census, content.len); return manifest; } // --------------------------------------------------------------------------- // Read-path interop shim -- NON-CONFORMING per §4.2, quarantined here // --------------------------------------------------------------------------- /// A manifest produced by `parseForImport`. `manifest` behaves exactly like a /// `parse` result; `normalized` is non-null ONLY when the legacy trailing- /// separator tolerance fired, in which case `manifest` borrows `normalized` and /// `deinit` frees it. The strict `parse` never yields this wrapper -- it stays /// the RFC-exact reference path. pub const ImportedManifest = struct { manifest: Manifest, /// The owned normalized copy the manifest borrows, or null on the strict /// path (where the manifest borrows the caller's original `bytes`). normalized: ?[]u8, pub fn deinit(self: *ImportedManifest, gpa: std.mem.Allocator) void { self.manifest.deinit(); if (self.normalized) |b| gpa.free(b); self.* = undefined; } }; /// Read/import-path parse. NOT RFC-conforming and NOT the reference parser: it /// exists solely so `zit` can READ fossil's own history, which contains a 2008 /// cvs2fossil-era check-in (32b480faa3465591b8549bdfd889d62d7a8d16a8) whose /// 210/211 F cards are written `F <name> <hash><SP>` -- a single dangling /// trailing separator where §4.2 requires a nonempty perm token or nothing /// (`token = 1*tchar`, no production for an empty token). fossil's tokenizer /// discards the trailing separator; a strict §4.2 reader rejects. Tolerated /// pending the operator's erratum decision (draft Option A: a descriptive /// Interoperability-Considerations note; the grammar itself stays unchanged). /// /// Quarantine contract: /// * The strict `parse` is invoked UNCHANGED and remains the sole /// §4.2/§4.7.6 oracle -- this wrapper never relaxes it. /// * The strict path runs first; the tolerance only engages when `parse` /// rejects AND the artifact is otherwise well-framed (its §6.2 Z self- /// checksum matches the ORIGINAL bytes). A genuine framing or Z-corruption /// failure is therefore never masked. /// * Exactly ONE separator is stripped per F-card line, the Z checksum is /// re-sealed over the shortened copy, and the SAME strict `parse` re-runs. /// Anything still malformed (a second trailing SP, an internal empty token, /// any other defect) is rejected by that strict retry. pub fn parseForImport(gpa: std.mem.Allocator, bytes: []const u8) ParseError!ImportedManifest { if (parse(gpa, bytes)) |m| { return .{ .manifest = m, .normalized = null }; } else |strict_err| { if (strict_err == error.OutOfMemory) return strict_err; // Guard: tolerate only a well-framed, Z-valid artifact -- never mask a // framing or Z-corruption reject behind the separator concession. const content = frame(bytes) orelse return strict_err; const normalized = (try stripLegacyFTrailingSep(gpa, content)) orelse return strict_err; const m = parse(gpa, normalized) catch |retry_err| { gpa.free(normalized); return retry_err; }; return .{ .manifest = m, .normalized = normalized }; } } /// Build a copy of `content` (already wrapper-stripped by `frame`) with exactly /// ONE trailing separator removed from each F-card line (`"F "…<SP>` -> `"F "…`) /// and the §6.2 Z self-checksum re-sealed over the shortened bytes -- or null /// when no such line exists (so the caller keeps the strict rejection). /// NON-CONFORMING per §4.2, read-path only. Operates line-wise; the strict /// retry in `parseForImport` is the safety net that rejects any byte the strip /// mis-touched (e.g. inside a W body), so this never yields a false accept. /// Bound: output length <= input length; one pass over the bytes. fn stripLegacyFTrailingSep(gpa: std.mem.Allocator, content: []const u8) std.mem.Allocator.Error!?[]u8 { std.debug.assert(content.len >= 10); // frame gate-3 postcondition std.debug.assert(content[content.len - 1] == '\n'); // frame gate-1 var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); var modified = false; var i: usize = 0; while (i < content.len) { const lf = std.mem.indexOfScalarPos(u8, content, i, '\n') orelse content.len; const line = content[i..lf]; // card bytes without the LF if (line.len >= 2 and line[0] == 'F' and line[1] == ' ' and line[line.len - 1] == ' ') { try out.appendSlice(gpa, line[0 .. line.len - 1]); // drop exactly one SP modified = true; } else { try out.appendSlice(gpa, line); } if (lf < content.len) try out.append(gpa, '\n'); i = lf + 1; } if (!modified) { out.deinit(gpa); return null; } const buf = try out.toOwnedSlice(gpa); resealZCard(buf); return buf; } /// Re-seal the §6.2 Z self-checksum in place after `stripLegacyFTrailingSep` /// shortened the content, so the strict `parse`'s `frame` Z gate accepts the /// normalized copy. A no-op when no Z card is present (§6.2 absent). The /// artifact's IDENTITY hash is taken over the ORIGINAL bytes by the caller's /// `verify`, never over this re-sealed copy, so identity is unaffected. fn resealZCard(buf: []u8) void { const n = buf.len; if (n < 35 or buf[n - 35] != 'Z' or buf[n - 34] != ' ') return; // §6.2 absent var digest_buf: [32]u8 = undefined; const computed = selfChecksum(buf[0 .. n - 35], &digest_buf); std.debug.assert(computed.len == 32); @memcpy(buf[n - 33 .. n - 1], computed); } /// Retention<->validation invariant (positive + negative space): every /// retained field's presence must exactly match the census bit the /// (untouched) validation lane already recorded, and every repeatable /// list's length stays within the card loop's own progress bound (`next > /// pos`, so the card count -- and each list's length -- can never exceed /// `content_len`). Catches any retain/verdict divergence this batch's /// refactor could introduce; never mutates. fn assertRetentionMatchesCensus(m: Manifest, census: Census, content_len: usize) void { std.debug.assert((m.a != null) == census.has('A')); std.debug.assert((m.b != null) == census.has('B')); std.debug.assert((m.c != null) == census.has('C')); std.debug.assert((m.d != null) == census.has('D')); std.debug.assert((m.e != null) == census.has('E')); std.debug.assert((m.g != null) == census.has('G')); std.debug.assert((m.h != null) == census.has('H')); std.debug.assert((m.i != null) == census.has('I')); std.debug.assert((m.k != null) == census.has('K')); std.debug.assert((m.l != null) == census.has('L')); std.debug.assert((m.n != null) == census.has('N')); std.debug.assert((m.r != null) == census.has('R')); std.debug.assert((m.u != null) == census.has('U')); std.debug.assert((m.w != null) == census.has('W')); std.debug.assert((m.z != null) == census.has('Z')); std.debug.assert((m.f.len > 0) == census.has('F')); std.debug.assert((m.j.len > 0) == census.has('J')); std.debug.assert((m.m.len > 0) == census.has('M')); std.debug.assert((m.p.len > 0) == census.has('P')); std.debug.assert((m.q.len > 0) == census.has('Q')); std.debug.assert((m.s.len > 0) == census.has('S')); std.debug.assert((m.t.len > 0) == census.has('T')); std.debug.assert(m.f.len <= content_len); std.debug.assert(m.j.len <= content_len); std.debug.assert(m.m.len <= content_len); std.debug.assert(m.p.len <= content_len); std.debug.assert(m.q.len <= content_len); std.debug.assert(m.s.len <= content_len); std.debug.assert(m.t.len <= content_len); } // --------------------------------------------------------------------------- // §8 Delta Manifest Reconstruction // --------------------------------------------------------------------------- /// The minimal view §8 reconstruction reads from a manifest: its B-card hash /// (null iff baseline manifest, §8-p1) and its own F cards, sorted by /// decoded filename (§8.1 parse-time invariant -- every successfully parsed /// manifest satisfies it). Manifest assembly (a later batch) will produce /// this view; §8 depends on nothing else about the manifest. pub const ManifestFiles = struct { baseline_hash: ?[]const u8, files: []const FCard, }; /// §8-p1: "A manifest is a delta manifest if and only if it contains a B /// card; otherwise it is a baseline manifest." pub fn isDelta(m: ManifestFiles) bool { return m.baseline_hash != null; } /// Injected seam resolving a B-card hash to the baseline artifact, viewed /// as `ManifestFiles` (§8.3). No store or IO exists at this layer -- the /// caller supplies resolution. `null` means the baseline could not be /// located, or the located artifact is not a manifest at all; both collapse /// to `BaselineUnresolvable` (§8.3-m1), the caller cannot tell them apart /// and doesn't need to. A resolved *delta* manifest MUST be returned as-is /// (its `baseline_hash` left non-null, never collapsed to null) so /// `enumerate`/`lookup` can reject the delta-of-delta case at resolution /// time (§4.7.3). The returned slice must outlive the walk -- caller-owned. pub const BaselineResolver = struct { ctx: *anyopaque, resolveFn: *const fn (ctx: *anyopaque, hash: []const u8) ?ManifestFiles, fn resolve(self: BaselineResolver, hash: []const u8) ?ManifestFiles { return self.resolveFn(self.ctx, hash); } }; /// §8.3 hard-failure surface for both enumeration entry points (full walk, /// §8.2/§8.3, and single-name lookup, §8.4). `BaselineUnresolvable` /// collapses "not located" and "not a manifest" into one fatal outcome /// (§8.3-m1). `BaselineIsDelta` stays distinct: it fires only after a /// *successful* resolve, when the resolved baseline itself carries a B /// card -- the delta-of-delta rejection (§4.7.3). pub const BaselineError = error{ BaselineUnresolvable, BaselineIsDelta }; /// §8.1 precondition: `files` strictly ascending by filename under the /// canonical comparator (§4.5.3). A parse-time invariant of every /// successfully parsed manifest -- asserted here, not re-validated. /// §4.5.3: an F-card run is in canonical ascending filename order. Public /// because a caller that merges two runs directly — without `enumerate` — /// depends on exactly this and must be able to say so. pub fn assertSorted(files: []const FCard) void { if (files.len > 1) { for (1..files.len) |i| { std.debug.assert(compareBytes(files[i - 1].filename, files[i].filename) == .lt); } } } /// §8.1-r1 / §4.7.6 negative-space companion: a baseline manifest's F cards /// never carry a delete marker (every hash is present). Sound only where /// `files` is known to come from a genuine baseline -- `enumerate`/`lookup` /// reject a resolved delta baseline before this ever runs on it. fn assertNoDeleteMarkers(files: []const FCard) void { for (files) |f| std.debug.assert(f.hash != null); } /// §8.2 engine: allocation-free filename-ordered merge-walk over a /// baseline's and a delta's F-card lists (both pre-sorted per §8.1-p1). /// `next()` yields each emitted card verbatim, including an unmatched /// delete marker (§8.2-w1) and any tail delete markers (§8.2-m1); it /// suppresses only the matched-delete case (step 2, §8.2-r2). pub const MergeWalk = struct { /// Sparse-cone RFC section 4.1: when set, `next` yields only entries the /// cone covers. Configured once by the enumeration owner (materialization /// and tracking walks), never per call site; null is dense operation and /// is bit-identical to the pre-cone walk. Manifest-synthesis walks /// (commit) and read verbs stay dense BY DESIGN -- filtering there would /// drop out-of-cone files from minted manifests (section 4.2) or hide /// readable history (section 4.4). sparse: ?*const cone_mod.Cone = null, baseline: []const FCard, delta: []const FCard, bi: usize = 0, di: usize = 0, /// §8.2 step-by-step merge. Every pass through the loop either returns /// (an entry was emitted) or advances both cursors (step 2's matched /// delete, which emits nothing), so the loop makes monotonic progress; /// the step counter plus assert catches a broken invariant rather than /// looping past the bound (§8.2-m1: terminates only once both cursors /// are exhausted). pub fn next(self: *MergeWalk) ?FCard { // Bounded: each nextDense call consumes at least one cursor entry, // so this loop runs at most baseline.len + delta.len times. while (self.nextDense()) |f| { const c = self.sparse orelse return f; if (c.covers(f.filename)) return f; } return null; } fn nextDense(self: *MergeWalk) ?FCard { std.debug.assert(self.bi <= self.baseline.len); std.debug.assert(self.di <= self.delta.len); const bound = self.baseline.len + self.delta.len + 1; var steps: usize = 0; while (true) { std.debug.assert(steps <= bound); steps += 1; const baseline_done = self.bi >= self.baseline.len; const delta_done = self.di >= self.delta.len; if (baseline_done and delta_done) return null; // m1: both exhausted if (baseline_done) { // delta tail verbatim, incl. markers (m1) const f = self.delta[self.di]; self.di += 1; return f; } if (delta_done) { // baseline tail verbatim (m1) const f = self.baseline[self.bi]; self.bi += 1; return f; } const order = compareBytes(self.baseline[self.bi].filename, self.delta[self.di].filename); switch (order) { .lt => { // baseline sorts first (step 3) const f = self.baseline[self.bi]; self.bi += 1; return f; }, .gt => { // delta sorts first, incl. unmatched marker (step 3, w1) const f = self.delta[self.di]; self.di += 1; return f; }, .eq => { const d = self.delta[self.di]; self.bi += 1; self.di += 1; if (d.hash != null) return d; // step 1: delta replaces baseline // step 2: matched delete -- no entry emitted, loop again }, } } } }; /// §8.2 + §8.3 hard-failure entry point: resolve the baseline lazily -- only /// for a delta manifest, only here (§8.3-p1) -- before any iteration begins /// (§8.3-m2, no silent delta-only degrade), reject a delta baseline /// (§4.7.3), then hand back the ready walk. pub fn enumerate(m: ManifestFiles, resolver: BaselineResolver) BaselineError!MergeWalk { assertSorted(m.files); if (!isDelta(m)) { assertNoDeleteMarkers(m.files); // §4.7.6: baseline F cards all carry a hash return MergeWalk{ .baseline = m.files, .delta = &.{} }; } const resolved = resolver.resolve(m.baseline_hash.?) orelse return error.BaselineUnresolvable; // §8.3-m1 if (isDelta(resolved)) return error.BaselineIsDelta; // §4.7.3: delta-of-delta, rejected at resolution assertSorted(resolved.files); assertNoDeleteMarkers(resolved.files); return MergeWalk{ .baseline = resolved.files, .delta = m.files }; } pub const LookupResult = union(enum) { found: FCard, not_found, }; /// §8.4 exact-match scan of one already-sorted F-card list. Bounded by /// `files.len`; terminates early once the sorted invariant proves no later /// entry can match (best-match/closest-name lookup is not a zit feature -- /// this is the only search shape, for both delta and baseline, §8.4-m1). fn scanExact(files: []const FCard, name: []const u8) ?FCard { for (files) |f| { const order = compareBytes(name, f.filename); if (order == .eq) return f; if (order == .lt) break; // sorted: nothing further can match } return null; } /// §8.4: resolve one filename against a manifest. The delta's own F cards /// are searched first (m1). A delta delete marker for the name reports /// not-found without consulting the baseline (m2). Only when the name is /// entirely absent from the delta is the baseline resolved and searched /// (p1), rejecting a resolved delta baseline (§4.7.3) the same as /// `enumerate`. pub fn lookup(m: ManifestFiles, name: []const u8, resolver: BaselineResolver) BaselineError!LookupResult { assertSorted(m.files); if (!isDelta(m)) assertNoDeleteMarkers(m.files); // §4.7.6: baseline carries no delete markers if (scanExact(m.files, name)) |f| { if (f.hash != null) return .{ .found = f }; return .not_found; // m2: delete marker, baseline never consulted } if (!isDelta(m)) return .not_found; const resolved = resolver.resolve(m.baseline_hash.?) orelse return error.BaselineUnresolvable; // §8.3-m1 if (isDelta(resolved)) return error.BaselineIsDelta; // §4.7.3 assertSorted(resolved.files); if (scanExact(resolved.files, name)) |f| { std.debug.assert(f.hash != null); // §4.7.6: baseline carries no delete markers return .{ .found = f }; } return .not_found; } // --------------------------------------------------------------------------- // draft-fossil-submanifests-00 §5 Tree Reconstruction // --------------------------------------------------------------------------- /// The minimal view §5 reads from a resolved sub-manifest: its F run (a leaf) /// or its S run (an interior node), never both -- §4.4: "A SUBMANIFEST MUST /// contain at least one F card or at least one S card, and MUST NOT contain /// both." There is deliberately no `baseline_hash` field: a SUBMANIFEST's /// allowed card set is F, S, Z (§4.2), so it can never carry a B card, and /// the type distinction is what keeps a `ManifestFiles` from being passed /// where a sub-manifest is meant (§9.3: "SHOULD enforce the seam with an /// assertion or type distinction"). pub const SubManifestView = struct { files: []const FCard, subs: []const SCard, }; /// Injected seam resolving an S-card hash to the referenced sub-manifest /// (§5.2). Deliberately the same philosophy as `BaselineResolver`, which §5.2 /// names as its model ("like the B card baseline of [FossilArtifact], /// Section 8.3, under the same two disciplines"): no store or IO exists at /// this layer, so the caller supplies resolution, and `null` collapses the /// two hard failures §5.2 lists -- "absent, or present but not of type /// SUBMANIFEST" -- into one fatal outcome the walk cannot tell apart and does /// not need to. The returned slices must outlive the walk (caller-owned); /// `flattenTree` copies out of them before returning, so a caller may free /// each sub-manifest as soon as the walk completes. pub const SubResolver = struct { ctx: *anyopaque, resolveFn: *const fn (ctx: *anyopaque, hash: []const u8) ?SubManifestView, fn resolve(self: SubResolver, hash: []const u8) ?SubManifestView { return self.resolveFn(self.ctx, hash); } }; /// §5.1/§5.3 hard-failure surface. `SubUnresolvable` is the §5.2 collapse. /// The other four are the walk's own structural checks, kept distinct because /// §A.5's rejection vectors name them separately and a reader that cannot /// tell a cycle from a depth overrun cannot be tested against them. pub const TreeError = error{ /// §5.2: the referenced artifact is absent, or is not a SUBMANIFEST. SubUnresolvable, /// §5.1 step 3: the resolved artifact's depth exceeds `max_tree_depth`. DepthExceeded, /// §5.1 step 3: the referenced artifact is already on the frame stack. ReferenceCycle, /// §5.1 steps 4 and 5: a subtree's first filename is not byte-identical /// to the S card's filename. FirstFilenameMismatch, /// §5.1 steps 3 and 4: a filename does not strictly follow LAST. OrderViolation, }; /// `flattenTree`'s surface: the walk's faults plus the memo allocation. pub const FlattenError = TreeError || error{OutOfMemory}; /// §5.1 step 3: "the referenced artifact's depth ... exceeds 16". §2 fixes /// the reader-side coordinate: "Depth counts sub-manifest artifacts from the /// manifest downward, counting the leaf: ... the depth bound of 16 admits at /// most 16 levels and a walk of at most 17 frames." pub const max_tree_depth: usize = 16; /// One frame per artifact being read (§5.1 step 1). `frames[0]` is the /// manifest's own frame; its `hash` is null because the manifest is not a /// sub-manifest and so is never a legitimate S target -- an S card naming it /// resolves to a non-SUBMANIFEST and fails at §5.2 before the cycle check /// could matter. const TreeFrame = struct { subs: []const SCard, cursor: usize, hash: ?[]const u8, }; /// §5.1 depth-first, in-order walk over the S references of a tree manifest. /// A stack, not recursion: the frame array is fixed at `max_tree_depth + 1` /// (§2's "at most 17 frames"), so the walk allocates nothing and the depth /// bound §10 requires is a property of the type rather than of a check that /// could be forgotten. /// /// `next` is fallible on purpose: every consumer is forced to handle a /// mid-walk fault, which is how §5.2's "MUST NOT present a partially resolved /// tree as a complete file set" is enforced structurally rather than by /// convention. /// /// Termination: each pass either emits one card from the open leaf run, pops /// a frame, or consumes exactly one S card from the top frame's cursor. /// Cursors are monotone and never reset, frames are bounded by 17, and every /// violation is fail-fast, so the walk halts on every input. pub const TreeWalk = struct { resolver: SubResolver, frames: [max_tree_depth + 1]TreeFrame = undefined, n_frames: usize, /// §5.1 step 1's LAST: "the decoded filename most recently emitted", /// initialized to "the absent value, which sorts before any present /// value". last: ?[]const u8 = null, /// The leaf F run being emitted (§5.1 step 4), and its key -- the /// filename of the S card that reached it, for the byte-identity check. leaf: []const FCard = &.{}, leaf_i: usize = 0, leaf_key: []const u8 = &.{}, /// §5.1 step 1: "Initialize the stack with one frame over the manifest's /// S run, and LAST as the absent value." pub fn init(subs: []const SCard, resolver: SubResolver) TreeWalk { std.debug.assert(subs.len != 0); // §5: only a tree manifest is walked var self = TreeWalk{ .resolver = resolver, .n_frames = 1 }; self.frames[0] = .{ .subs = subs, .cursor = 0, .hash = null }; return self; } /// The next F card of the enumeration, or null once the manifest's frame /// is popped (§5.1 step 2: "When the popped frame is the manifest's, /// enumeration terminates"). pub fn next(self: *TreeWalk) TreeError!?FCard { while (true) { if (self.leaf_i < self.leaf.len) return try self.emitLeafCard(); // Step 2: pop exhausted frames; the manifest's frame terminates. while (self.n_frames != 0 and self.frames[self.n_frames - 1].cursor >= self.frames[self.n_frames - 1].subs.len) { self.n_frames -= 1; } if (self.n_frames == 0) return null; try self.descend(); } } /// §5.1 step 4 emission: the F cards of the open leaf, in order, with the /// first checked byte-identical to the S card's filename and every one /// checked strictly after LAST. "the tree walk (Section 5.1, step 4) MUST /// deliver each emitted entry's hash, permission, and old-name tokens to /// consumers unaltered" (§4.4), so the card is returned verbatim. fn emitLeafCard(self: *TreeWalk) TreeError!FCard { const f = self.leaf[self.leaf_i]; if (self.leaf_i == 0 and !std.mem.eql(u8, f.filename, self.leaf_key)) { return error.FirstFilenameMismatch; } if (!self.after(f.filename)) return error.OrderViolation; // §4.4: "Every F card in a SUBMANIFEST MUST carry a hash" -- a // per-type semantic check `parse` already enforces, asserted here the // same way §8's `assertNoDeleteMarkers` asserts the baseline case. std.debug.assert(f.hash != null); self.leaf_i += 1; self.last = f.filename; return f; } /// §5.1 step 3 plus the step-4/step-5 dispatch: read one S card, check it, /// resolve it, and either open its leaf run or push its frame. fn descend(self: *TreeWalk) TreeError!void { const top = &self.frames[self.n_frames - 1]; const sc = top.subs[top.cursor]; // The cursor is consumed on read, not on ascent: step 4 advances the // referencing frame's cursor after a leaf, and step 5 does the same // before pushing an interior frame. Consuming on read serves both. // // Step 5's cursor advance arrived by erratum // (submanifests-00-s5.1-step5-cursor-advance). As first published, // step 5 said only "Push a frame over its S run", which left the // parent re-reading the descended S card after the pop; step 3's // "strictly greater than LAST" then necessarily failed, because the // subtree's first emitted name is byte-identical to that S card's // filename, so LAST already equalled it. Every tree with an interior // node was unwalkable under that reading. No published vector // discriminates the two readings -- A.3 and A.4 both reference leaves // directly (A.4: "the merge fires at height 1 ... the manifest carries // three S cards directly") -- which is why §A.5 requires a corpus to // add "a three-level tree (manifest, interior nodes, leaves), // exercising step 5 of the tree walk". top.cursor += 1; // Step 3: "Its decoded filename MUST compare strictly greater than // LAST." Checked before resolution, so an out-of-order tree costs no // artifact read. if (!self.after(sc.filename)) return error.OrderViolation; // Step 3's depth bound. `n_frames` counts the manifest's frame plus // one per sub-manifest already on the path, so it is exactly the // depth the artifact about to be resolved would have. Checked before // the resolve: §10 makes the bound the defence against "a crafted // deep spine turn[ing] an unauthenticated lookup endpoint into // unbounded sequential artifact reads", which only holds if the read // never happens. if (self.n_frames > max_tree_depth) return error.DepthExceeded; // Step 3's repeated-artifact check, likewise before the resolve. for (self.frames[0..self.n_frames]) |fr| { const h = fr.hash orelse continue; if (std.mem.eql(u8, h, sc.hash)) return error.ReferenceCycle; } const view = self.resolver.resolve(sc.hash) orelse return error.SubUnresolvable; // §5.2 // §4.4: a sub-manifest carries F cards or S cards, never both and // never neither, so the S run alone decides leaf versus interior. std.debug.assert((view.subs.len == 0) != (view.files.len == 0)); if (view.subs.len == 0) { self.leaf = view.files; // step 4 self.leaf_i = 0; self.leaf_key = sc.filename; return; } // Step 5: "its first S card's decoded filename MUST be byte-identical // to the referencing S card's decoded filename." if (!std.mem.eql(u8, view.subs[0].filename, sc.filename)) return error.FirstFilenameMismatch; std.debug.assert(self.n_frames < self.frames.len); // §2: at most 17 frames self.frames[self.n_frames] = .{ .subs = view.subs, .cursor = 0, .hash = sc.hash }; self.n_frames += 1; } /// LAST's ordering test: absent sorts before any present value (§5.1 /// step 1), otherwise the §4.5.3 canonical comparator, strictly. fn after(self: *const TreeWalk, name: []const u8) bool { const last = self.last orelse return true; return compareBytes(last, name) == .lt; } }; /// §5.3 binary search: "the last S card whose decoded filename compares less /// than or equal to the target; if no such card exists the name is absent." /// The S run is strictly ascending by §3.4, a parse-time invariant. fn lastAtOrBelow(subs: []const SCard, name: []const u8) ?usize { var lo: usize = 0; var hi: usize = subs.len; var found: ?usize = null; while (lo < hi) { const mid = lo + (hi - lo) / 2; if (compareBytes(subs[mid].filename, name) == .gt) { hi = mid; } else { found = mid; lo = mid + 1; } } return found; } /// §5.3 single-name lookup against a tree manifest's S run: descend one level /// per binary search -- "the S run of an interior node, the F run of a leaf -- /// until a leaf either contains the name or proves it absent." /// /// Reads at most one sub-manifest per level and at most `max_tree_depth` per /// lookup, by construction: the loop resolves exactly once per iteration and /// refuses the iteration that would exceed the bound, which is the form §10 /// requires ("the depth bound MUST be enforced in single-name lookup"). /// No walk-side integrity check is repeated here -- §5.3 specifies the search /// and the bound, and nothing else. pub fn lookupTree(subs: []const SCard, name: []const u8, resolver: SubResolver) TreeError!?FCard { // §5: only a tree manifest is looked up this way. An empty S run carries no // names, so the answer is "absent". This was an assert until trunk's // release-assert guard named it: `subs` is parsed repository or peer data, // and a panic here is reachable from a malformed manifest. if (subs.len == 0) return null; var run = subs; var depth: usize = 0; while (true) { const idx = lastAtOrBelow(run, name) orelse return null; // absent above the run depth += 1; if (depth > max_tree_depth) return error.DepthExceeded; // §5.3 / §10 const view = resolver.resolve(run[idx].hash) orelse return error.SubUnresolvable; // §5.2 // §4.4 — exactly one of the two runs is populated. A resolved artifact // that violates it is not a sub-manifest, which is precisely what §5.2's // `SubUnresolvable` already names. Asserting it panicked a ReleaseSafe // reader on an artifact a peer can push, and compiled to nothing under // `--release=fast`, walking the malformed node either way. if ((view.subs.len == 0) == (view.files.len == 0)) return error.SubUnresolvable; if (view.subs.len == 0) return scanExact(view.files, name); // the leaf decides run = view.subs; } } // --------------------------------------------------------------------------- // §6/§4 Writer: Manifest -> Canonical Bytes // --------------------------------------------------------------------------- /// `create`'s sole failure mode -- a `Manifest` is valid by construction /// (every field was already grammar-checked by `parse`), so the only way /// serialization can fail is the output allocation itself. Closed set, no /// `anyerror` across the boundary. pub const WriteError = error{OutOfMemory}; /// The two `serializeSubmanifest*` writers' surface: the output allocation plus /// the one structural precondition a caller can violate. `WriteError`'s /// closed-set rationale above is about serializing a `Manifest`, which is valid /// by construction; these two serialize a caller-supplied group instead, and /// §4.4 admits no empty sub-manifest. It was an assert until trunk's /// release-assert guard named the shape: under `--release=fast` the assert /// compiles to nothing and the writer emits a Z-card-only artifact that /// `lookupTree` then rejects as not-a-sub-manifest. A refusal fails at the /// producer instead, where the caller can still say which group was empty. pub const SubmanifestWriteError = WriteError || error{EmptySubmanifest}; /// Append escape-encoded `token` (§4.3, the writer-side inverse of /// `decodeEscapes`). Grows `buf` by exactly the encoded length: reserve the /// worst case (`2 * token.len`, §4.3's own bound), encode into that tail, /// then shrink back to what was actually written. fn appendEscaped(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, token: []const u8) WriteError!void { const dst = try buf.addManyAsSlice(allocator, 2 * token.len); const written = encodeEscapes(token, dst); std.debug.assert(written.len <= dst.len); buf.items.len -= (dst.len - written.len); } /// Append the minimal decimal ASCII rendering of `n` -- no leading zeros, /// no sign (§4.7.18 W-card size prefix). Digit extraction mirrors /// `updateSizeHeader`'s (§6.3.2); kept as its own small function rather than /// shared, since that one's job is a fixed `SP digits LF` MD5-context /// header, not a general buffer append. fn appendMinimalDecimal(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, n: usize) WriteError!void { var digits: [max_size_digits]u8 = undefined; var n_digits: usize = 0; var v = n; while (true) { std.debug.assert(n_digits < digits.len); digits[n_digits] = @as(u8, @intCast(v % 10)) + '0'; n_digits += 1; v /= 10; if (v == 0) break; } std.debug.assert(n_digits >= 1 and n_digits <= digits.len); try buf.ensureUnusedCapacity(allocator, n_digits); var i: usize = n_digits; while (i > 0) { i -= 1; buf.appendAssumeCapacity(digits[i]); // most-significant digit first } } /// Append one single-token RAW card: `<letter> <token>\n`. `letter` must be /// one of the twelve hash/checksum/timestamp/sign positions §4.3.1 never /// escape-decodes, so the token is never escape-encoded on the way back out. fn appendRawCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, letter: u8, token: []const u8) WriteError!void { std.debug.assert(isCardLetter(letter)); try buf.append(allocator, letter); try buf.append(allocator, ' '); try buf.appendSlice(allocator, token); try buf.append(allocator, '\n'); } /// Append one single-token FREE-TEXT card: `<letter> <esc(token)>\n` (§4.3 /// writer inverse of `decodeEscapes`). fn appendEscapedCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, letter: u8, token: []const u8) WriteError!void { std.debug.assert(isCardLetter(letter)); try buf.append(allocator, letter); try buf.append(allocator, ' '); try appendEscaped(buf, allocator, token); try buf.append(allocator, '\n'); } /// §4.7.2 A card: `A <esc(name)> <esc(target)> [<source>]\n`. `source` is /// raw (the parser's one exception among hash-bearing positions, §4.3.1 /// line 680); a prefixed filename never round-trips (parse keeps only the /// basename, §4.7.2-m1) -- not reachable from any card this batch's /// fixtures carry. fn appendACard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, a: ACard) WriteError!void { try buf.append(allocator, 'A'); try buf.append(allocator, ' '); try appendEscaped(buf, allocator, a.name); try buf.append(allocator, ' '); try appendEscaped(buf, allocator, a.target); if (a.source) |src| { try buf.append(allocator, ' '); try buf.appendSlice(allocator, src); } try buf.append(allocator, '\n'); } /// §4.7.5 E card: `E <timestamp> <technote-id>\n`, both raw. fn appendECard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, e: ECard) WriteError!void { try buf.append(allocator, 'E'); try buf.append(allocator, ' '); try buf.appendSlice(allocator, e.timestamp); try buf.append(allocator, ' '); try buf.appendSlice(allocator, e.technote_id); try buf.append(allocator, '\n'); } /// The type every filename-token emitter has: `appendEscaped` (§4.3, every /// existing emission position) and `appendCanonical` (submanifests §6.2, the /// construction's own leaf F run) are the only two. const TokenAppender = fn (*std.ArrayList(u8), std.mem.Allocator, []const u8) WriteError!void; /// §4.7.6 F card: `F <enc(filename)> [<hash>] [<perm>] [<enc(old)>]\n`. The /// three trailing positions nest strictly (perm only with hash, old_name /// only with perm) -- a structural invariant of every successfully-parsed /// FCard, since `parseFCard` reads them positionally, not by name. /// /// The F-card GRAMMAR is written once, here, and the two writers that emit one /// differ only in `appendToken`: a check-in's F run escapes under §4.3, a /// submanifests §6.2 leaf under §6.2's canonical encoding. Duplicating the /// layout to vary the encoder would let a later §4.7.6 refinement land on one /// writer and silently move the other's bytes. fn appendFCardTokens( comptime appendToken: TokenAppender, buf: *std.ArrayList(u8), allocator: std.mem.Allocator, f: FCard, ) WriteError!void { try buf.append(allocator, 'F'); try buf.append(allocator, ' '); try appendToken(buf, allocator, f.filename); if (f.hash) |h| { try buf.append(allocator, ' '); try buf.appendSlice(allocator, h); } if (f.perm) |p| { std.debug.assert(f.hash != null); try buf.append(allocator, ' '); try buf.appendSlice(allocator, p); } if (f.old_name) |old| { std.debug.assert(f.perm != null); try buf.append(allocator, ' '); try appendToken(buf, allocator, old); } try buf.append(allocator, '\n'); } /// The check-in F card: §4.7.6's grammar under §4.3 escaping. Every artifact /// this writer emitted before sub-manifests existed came through here, so the /// encoder is fixed and MUST stay fixed -- changing it respells any filename /// containing TAB, CR, VT, FF or NUL and so renames the stored check-in. fn appendFCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, f: FCard) WriteError!void { try appendFCardTokens(appendEscaped, buf, allocator, f); } /// One flat check-in F card, for a writer that assembles its manifest text /// outside this module. submanifests §6.2 step 2 makes this reachable from a /// sub-manifest-mode writer: a name set that partitions into fewer than two /// groups "MUST emit a flat manifest and no sub-manifests", so such a writer /// needs the flat F run as well as the S run. /// /// Routes to `appendFCard` — the fixed §4.7.6/§4.3 encoder — rather than the /// §6.2 canonical one `serializeLeaf` uses: this card lands in a CHECK-IN /// manifest, where the escaping rule has never been §6.2's. Exposed so the /// alternative (hand-formatting the line at the call site) stays unavailable. pub fn appendFlatFCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, f: FCard) WriteError!void { try appendFCard(buf, allocator, f); } /// §4.7.8 J card: `J <field> [<esc(value)>]\n`. `field` is raw (never /// decoded on read, §4.7.8); an empty `value` is the absent-value sentinel /// (m3) and is omitted, never emitted as a trailing bare SP. fn appendJCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, j: JCard) WriteError!void { try buf.append(allocator, 'J'); try buf.append(allocator, ' '); try buf.appendSlice(allocator, j.field); if (j.value.len > 0) { try buf.append(allocator, ' '); try appendEscaped(buf, allocator, j.value); } try buf.append(allocator, '\n'); } /// §4.7.13 P card: `P [<parents>]\n`. `count == 0` (bare `P\n`, m1) is the /// only case with no argument; `parents` otherwise carries the already /// SP-joined raw hash tokens verbatim. fn appendPCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, p: PCard) WriteError!void { try buf.append(allocator, 'P'); if (p.count > 0) { std.debug.assert(p.parents != null); try buf.append(allocator, ' '); try buf.appendSlice(allocator, p.parents.?); } try buf.append(allocator, '\n'); } /// §4.7.14 Q card: `Q <sign><target> [<baseline>]\n`. Sign and target glue /// into one wire token with no SP between them (q-sign is a byte prefix on /// the hash, not a separate token). fn appendQCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, q: QCard) WriteError!void { try buf.append(allocator, 'Q'); try buf.append(allocator, ' '); try buf.append(allocator, if (q.sign == .cherrypick) '+' else '-'); try buf.appendSlice(allocator, q.target); if (q.baseline) |bl| { try buf.append(allocator, ' '); try buf.appendSlice(allocator, bl); } try buf.append(allocator, '\n'); } /// §6.3.4 R card: `R <checksum>\n`, lowered -- the parser accepts either /// case (§6.1), but the producer MUST always render exactly 32 lowercase /// hex digits (§6.3.4). fn appendRCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, r: RCard) WriteError!void { std.debug.assert(r.checksum.len == 32); var lower: [32]u8 = undefined; for (r.checksum, 0..) |c, i| lower[i] = std.ascii.toLower(c); try appendRawCard(buf, allocator, 'R', &lower); } /// §4.7.16 T card: `T <sign><esc(name)> <target|*> [<esc(value)>]\n`. Sign /// and name glue into one token (no SP), matching Q's sign convention; a /// null `target` is the literal self-referential wire byte `*` (m3). fn appendTCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, t: TCard) WriteError!void { try buf.append(allocator, 'T'); try buf.append(allocator, ' '); try buf.append(allocator, t.sign.byte()); try appendEscaped(buf, allocator, t.name); try buf.append(allocator, ' '); if (t.target) |tgt| { try buf.appendSlice(allocator, tgt); } else { try buf.append(allocator, '*'); } if (t.value) |v| { try buf.append(allocator, ' '); try appendEscaped(buf, allocator, v); } try buf.append(allocator, '\n'); } /// Append escape-encoded `token` under the submanifests §6.2 CANONICAL /// encoding (`encodeCanonical`, not `encodeEscapes`). Same shrink-back shape as /// `appendEscaped`; a distinct function rather than a flag on that one so that /// grepping for `appendCanonical` enumerates every position the canonical /// spelling reaches -- the compatibility argument for the scoping is exactly /// that list. It is the ENCODER that stays separate, never the card grammar: /// `appendFCardTokens` is written once and takes the emitter as its parameter. fn appendCanonical(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, token: []const u8) WriteError!void { const dst = try buf.addManyAsSlice(allocator, 2 * token.len); const written = encodeCanonical(token, dst); std.debug.assert(written.len <= dst.len); buf.items.len -= (dst.len - written.len); } /// submanifests §3.6 S card: `S <min(filename)> <hash>\n`. The filename is a /// decoded token emitted under the §6.2 canonical encoding; the hash is raw /// ("never decoded"), so it passes through verbatim. fn appendSCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, s: SCard) WriteError!void { // §3.5 validates the S hash case-insensitively (§4.7.1-m1) and §3.6 keeps // it raw, so the parser hands back whatever spelling it was given. The // writer therefore accepts exactly what `parseSCard` accepts: asserting a // narrower spelling here would make a parsed card un-re-emittable. std.debug.assert(validateHashToken(.artifact_hash, s.hash)); try buf.append(allocator, 'S'); try buf.append(allocator, ' '); try appendCanonical(buf, allocator, s.filename); try buf.append(allocator, ' '); try buf.appendSlice(allocator, s.hash); try buf.append(allocator, '\n'); } /// §6.2 Z card: the MD5 of everything emitted so far, then `Z <sum>\n`. The /// one place the artifact tail is spelled -- `create` and the submanifests §6.2 /// sub-manifest serializers all end here, so no two writers can disagree about /// what the checksum covers. fn appendZCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator) WriteError!void { var digest: [32]u8 = undefined; _ = selfChecksum(buf.items, &digest); // §6.2: over everything emitted so far try buf.append(allocator, 'Z'); try buf.append(allocator, ' '); try buf.appendSlice(allocator, &digest); try buf.append(allocator, '\n'); } /// §4.7.18 W card: `W <size>\n<body>\n`, size-counted rather than tokenized /// (the body may itself embed LF, §4.7.18). fn appendWCard(buf: *std.ArrayList(u8), allocator: std.mem.Allocator, body: []const u8) WriteError!void { try buf.append(allocator, 'W'); try buf.append(allocator, ' '); try appendMinimalDecimal(buf, allocator, body.len); try buf.append(allocator, '\n'); try buf.appendSlice(allocator, body); try buf.append(allocator, '\n'); } /// Serialize `manifest` to canonical artifact bytes (§4/§6). Cards are /// emitted in the fixed §4.7/§4.4 lexical order A,B,C,D,E,F,G,H,I,J,K,L,M, /// N,P,Q,R,S,T,U,W,Z (S is submanifests §3.4's repeatable card, in the same /// lexical position) -- the writer never reasons about the reader's N-after-P /// compat exception (§4.4), since walking the Manifest's own fields in this /// order always produces a strictly non-decreasing sequence. Z is computed /// over the serialized prefix and appended last (§6.2); `manifest.z` (the /// parsed Z, if any) is never read. Caller owns the returned slice and /// frees it with `allocator`. pub fn create(manifest: *const Manifest, allocator: std.mem.Allocator) WriteError![]u8 { // A code-9 SUBMANIFEST never reaches here: submanifests §6.2 sub-manifests // are serialized by `buildTree`'s own leaf/interior writers, whose F run // takes the §6.2 canonical encoding this general writer must NOT apply to // the check-in cards around it. std.debug.assert(@intFromEnum(manifest.kind) >= 1 and @intFromEnum(manifest.kind) <= 8); // submanifests §4.4/§5: an S run belongs to a tree MANIFEST, and the file // set is conveyed by one mechanism or the other, "never a mixture". An // empty S run (every artifact this writer emitted before sub-manifests // existed) adds not one byte, so no stored check-in's hash moves. if (manifest.s.len != 0) { std.debug.assert(manifest.kind == .manifest); std.debug.assert(manifest.f.len == 0); // §4.4: never both F and S std.debug.assert(manifest.b == null); // §4.4: never both B and S } var buf: std.ArrayList(u8) = .empty; errdefer buf.deinit(allocator); if (manifest.a) |a| try appendACard(&buf, allocator, a); if (manifest.b) |b| try appendRawCard(&buf, allocator, 'B', b.hash); if (manifest.c) |c| try appendEscapedCard(&buf, allocator, 'C', c.comment); if (manifest.d) |d| try appendRawCard(&buf, allocator, 'D', d.timestamp); if (manifest.e) |e| try appendECard(&buf, allocator, e); for (manifest.f) |f| try appendFCard(&buf, allocator, f); if (manifest.g) |g| try appendRawCard(&buf, allocator, 'G', g.hash); if (manifest.h) |h| try appendEscapedCard(&buf, allocator, 'H', h.title); if (manifest.i) |i| try appendRawCard(&buf, allocator, 'I', i.hash); for (manifest.j) |j| try appendJCard(&buf, allocator, j); if (manifest.k) |k| try appendRawCard(&buf, allocator, 'K', k.ticket_id); if (manifest.l) |l| try appendEscapedCard(&buf, allocator, 'L', l.title); for (manifest.m) |m| try appendRawCard(&buf, allocator, 'M', m.hash); if (manifest.n) |n| try appendEscapedCard(&buf, allocator, 'N', n.mimetype); for (manifest.p) |p| try appendPCard(&buf, allocator, p); for (manifest.q) |q| try appendQCard(&buf, allocator, q); if (manifest.r) |r| try appendRCard(&buf, allocator, r); // submanifests §3.4 places S in the repeatable class and the letter itself // in lexical position: R < S < T, which §A.3's C,D,R,S,S,U,Z confirms. for (manifest.s) |s| try appendSCard(&buf, allocator, s); for (manifest.t) |t| try appendTCard(&buf, allocator, t); if (manifest.u) |u| try appendEscapedCard(&buf, allocator, 'U', u.login); if (manifest.w) |w| try appendWCard(&buf, allocator, w); try appendZCard(&buf, allocator); const out = try buf.toOwnedSlice(allocator); std.debug.assert(out.len >= 35); // §4.1: minimum framing (the Z card alone) std.debug.assert(out[out.len - 1] == '\n'); std.debug.assert(out[out.len - 35] == 'Z' and out[out.len - 34] == ' '); std.debug.assert(verifyZCard(out) == .match); // the writer's own output MUST self-verify return out; } // --------------------------------------------------------------------------- // draft-fossil-submanifests-00 §6 Canonical Tree Construction // --------------------------------------------------------------------------- // // §6.2 opens with the obligation this section exists to meet: "the // construction in this section fully determines the sub-manifest bytes and the // manifest's S run: two conforming writers MUST produce byte-identical // artifacts for the same check-in." That is why the whole partition lives here, // beside `create`, rather than in the commit verb: the bytes are a pure // function of (sorted file entries, k, hash policy), and the Appendix A vectors // are the proof. // // The construction is deterministic by shape, not by discipline: the input is // a sorted slice, groups are index ranges into it, each level's node array is // built in scan order, and bytes -> name -> S token are pure functions. No // hashmap, set, or unordered container appears anywhere below, so there is no // iteration order for a build to depend on. /// §6.3: "a writer ... MUST support every value from 1 to 12 inclusive (the /// pinned value MUST lie in that range)". Selecting and pinning k is the /// caller's job (§6.3 makes it a project-scope setting); `buildTree` only /// enforces the range, and never derives a value of its own -- "MUST NOT /// derive a value per commit". pub const min_k: u4 = 1; pub const max_k: u4 = 12; /// §6.2 step 3: "construction MUST NOT create a node of height 16". Heights /// 0..15 are constructible, so a canonical tree's longest path is 16 /// sub-manifest artifacts counting the leaf -- exactly `max_tree_depth`, the /// reader-side bound of §5.1. pub const max_construct_height: usize = 16; comptime { std.debug.assert(max_construct_height == max_tree_depth); } /// One sub-manifest the construction produced: its serialized bytes and its /// artifact name under the repository hash policy ([FossilArtifact], §7). pub const SubArtifact = struct { name: []const u8, bytes: []const u8, /// Position identity for cross-commit comparison: the /// node's §6.2 group key — the decoded filename of the first file entry /// in its subtree — and its height. Two commits' nodes with equal /// (height, key) are "the same node, possibly revised": the pair the /// delta encoder is costed against. Purely informational for emission. key: []const u8, height: u16, }; /// The output of `buildTree`, owning every slice it hands back. /// /// §6.2's storage obligation -- "Sub-manifest artifacts are stored before the /// manifest that references them" -- is encoded as LIST ORDER rather than as a /// rule the caller must remember: `subs` runs height 0 first, then height 1, /// and so on, in key order within each height, so a referencer never precedes /// anything it references. A caller storing `subs` front to back satisfies §6.2 /// without knowing that heights, groups, or keys exist. pub const TreeBuild = struct { arena_state: std.heap.ArenaAllocator, /// Every sub-manifest of the tree, in storage order (see above). Empty iff /// the construction yielded a flat manifest. subs: []const SubArtifact, /// The manifest's own S run (§6.2 step 3), in key order. Empty iff `subs` /// is empty; otherwise at least two cards, since a tree the construction /// emits always partitions the name set at least in two. s: []const SCard, /// §6.2 step 2's outcome: "the writer MUST emit a flat manifest and no /// sub-manifests". The caller keeps its existing flat path unchanged -- /// byte-identically so, since nothing here touched it. pub fn isFlat(self: *const TreeBuild) bool { std.debug.assert((self.subs.len == 0) == (self.s.len == 0)); return self.s.len == 0; } pub fn deinit(self: *TreeBuild) void { self.arena_state.deinit(); } }; /// One node of the level under construction: §6.2's "key of a node is the /// decoded filename of the first file entry in its subtree", and the artifact /// name that key's S card points at. Height 0 nodes are leaves; the manifest's /// own S run is the top level rendered card for card. const Node = struct { key: []const u8, name: []const u8, }; /// §6.2 step 1's scan, run at every height. Returns group BOUNDARIES with a /// closing sentinel: there are `bounds.len - 1` groups, and group i covers /// `bounds[i] .. bounds[i+1]` with no end-of-list special case. Keeping the /// scan on an index list -- rather than materializing nodes -- is what lets one /// function serve height 0 and every height above it, and therefore what makes /// the final-group merge apply "at every height, uniformly" without a second /// code path to keep in step. §A.4 is the vector that fails when those paths /// diverge. /// /// `threshold` is §6.1's boundary test for the height being formed: k for /// leaves, (h+1)*k for height-h nodes. `min`/`max` count MEMBERS (file entries /// at height 0, child nodes above), never bytes. fn scanGroups( arena: std.mem.Allocator, keys: []const []const u8, threshold: u16, min: usize, max: usize, ) std.mem.Allocator.Error![]const usize { return partition.groups(arena, keys, threshold, min, max, zbits); } /// The number of groups a canonical partition describes (its sentinel is not a /// group). Grouping itself is exclusively owned by `submanifest_partition`. fn groupCount(bounds: []const usize) usize { return partition.groupCount(bounds); } /// §6.2 step 2: a leaf sub-manifest "carrying exactly that group's F cards, in /// order, and a Z card". Same §4.7.6 grammar as a check-in's F run -- one /// writer, `appendFCardTokens` -- differing only in the filename/old-name /// encoder, which §6.2 fixes to the canonical spelling. The hash and perm /// tokens are raw positions the decoder never touches. /// Serialize a canonical leaf sub-manifest from already admitted F cards. /// Kept beside the batch writer so every producer emits identical card bytes. pub fn serializeSubmanifestLeaf( arena: std.mem.Allocator, group: []const FCard, ) SubmanifestWriteError![]const u8 { // The public boundary is where an untrusted group arrives; §4.4 admits no // empty sub-manifest. `buildTree`'s own path enters through `serializeLeaf` // below, whose groups the partitioner derives from non-empty entry ranges, // so the builder keeps its allocation-only surface instead of propagating a // refusal it cannot provoke. if (group.len == 0) return error.EmptySubmanifest; return serializeLeafCore(arena, group); } fn serializeLeafCore(arena: std.mem.Allocator, group: []const FCard) WriteError![]const u8 { var buf: std.ArrayList(u8) = .empty; for (group) |f| { std.debug.assert(f.hash != null); try appendFCardTokens(appendCanonical, &buf, arena, f); } try appendZCard(&buf, arena); return buf.toOwnedSlice(arena); } fn serializeLeaf(arena: std.mem.Allocator, group: []const FCard) WriteError![]const u8 { return serializeLeafCore(arena, group); } /// SHA3-256 over the canonical F-card byte encoding of `entries` — the exact /// card bytes a canonical leaf sub-manifest would carry for that F run under /// §6.2's minimal-escaping rule (one encoder, `appendFCardTokens`; nothing is /// hand-formatted here). A cheap STRUCTURAL witness for local bookkeeping /// only (the checkpoint sidecar): it reads no file content, is not a /// specified value, appears in no artifact, and never crosses a wire. /// /// Deliberately NOT the R card's MD5 (§6.3.2, `ChecksumAggregator`): that /// digest folds in every file's content, which is O(repository bytes) and /// useless as a cheap witness. The R-card path is untouched. /// /// Asserts §4.5.3 canonical ascending order over the decoded filenames, the /// same precondition `ChecksumAggregator.update` holds. pub fn fileSetFingerprint(gpa: std.mem.Allocator, entries: []const FCard) error{OutOfMemory}![32]u8 { var sha = std.crypto.hash.sha3.Sha3_256.init(.{}); var buf: std.ArrayList(u8) = .empty; defer buf.deinit(gpa); var prev: ?[]const u8 = null; for (entries) |f| { if (prev) |p| std.debug.assert(compareBytes(p, f.filename) == .lt); prev = f.filename; buf.clearRetainingCapacity(); try appendFCardTokens(appendCanonical, &buf, gpa, f); sha.update(buf.items); } var out: [32]u8 = undefined; sha.final(&out); return out; } /// §6.2 step 3: an interior sub-manifest "carrying one S card per member node, /// in key order, and a Z card". fn serializeInterior(arena: std.mem.Allocator, members: []const Node) WriteError![]const u8 { var buf: std.ArrayList(u8) = .empty; for (members) |n| { try appendSCard(&buf, arena, .{ .filename = n.key, .hash = n.name }); } try appendZCard(&buf, arena); return buf.toOwnedSlice(arena); } /// Serialize a canonical interior sub-manifest from its exact child S cards. pub fn serializeSubmanifestInterior( arena: std.mem.Allocator, members: []const SCard, ) SubmanifestWriteError![]const u8 { if (members.len == 0) return error.EmptySubmanifest; var buf: std.ArrayList(u8) = .empty; for (members) |member| try appendSCard(&buf, arena, member); try appendZCard(&buf, arena); return buf.toOwnedSlice(arena); } /// Name `bytes` under `algo` into arena-owned storage (§6.2: an S card's "hash /// token is the child artifact's name under the repository hash policy"). fn nameArtifact(arena: std.mem.Allocator, algo: HashAlgo, bytes: []const u8) std.mem.Allocator.Error![]const u8 { var scratch: [64]u8 = undefined; const hex = artifactName(algo, bytes, &scratch); return arena.dupe(u8, hex); } /// One planned §6.2 node: its inclusive-exclusive file-entry range and, above /// leaves, the inclusive-exclusive range of direct children in the prior level. const TreeShapeNode = struct { first: usize, end: usize, members_start: usize, members_end: usize, }; const TreeShapeLevel = struct { nodes: []const TreeShapeNode, }; /// §6.2's deterministic partition plan: leaf groups use the §6.1 boundary /// test, and each higher level uses the §6.2 step-3 `(h + 1) * k` threshold. const TreeShapePlan = struct { arena_state: std.heap.ArenaAllocator, levels: []const TreeShapeLevel, fn isFlat(self: *const TreeShapePlan) bool { return self.levels.len == 0; } fn deinit(self: *TreeShapePlan) void { self.arena_state.deinit(); } }; fn treeShapeLeafNodes( arena: std.mem.Allocator, entries: []const FCard, k: u4, min: usize, max: usize, ) std.mem.Allocator.Error![]const TreeShapeNode { if (entries.len == 0) return &.{}; const keys = try arena.alloc([]const u8, entries.len); for (entries, keys) |entry, *key| key.* = entry.filename; const bounds = try scanGroups(arena, keys, k, min, max); if (groupCount(bounds) < 2) return &.{}; const nodes = try arena.alloc(TreeShapeNode, groupCount(bounds)); for (nodes, 0..) |*node, index| { node.* = .{ .first = bounds[index], .end = bounds[index + 1], .members_start = 0, .members_end = 0, }; } return nodes; } fn treeShapeInteriorNodes( arena: std.mem.Allocator, entries: []const FCard, current: []const TreeShapeNode, k: u4, height: usize, min: usize, max: usize, ) std.mem.Allocator.Error![]const TreeShapeNode { std.debug.assert(current.len >= 2); std.debug.assert(height >= 1); const keys = try arena.alloc([]const u8, current.len); for (current, keys) |node, *key| key.* = entries[node.first].filename; const threshold: u16 = @intCast((height + 1) * @as(usize, k)); const bounds = try scanGroups(arena, keys, threshold, min, max); const count = groupCount(bounds); if (count == 1 or count == current.len) return &.{}; const nodes = try arena.alloc(TreeShapeNode, count); for (nodes, 0..) |*node, index| { const members_start = bounds[index]; const members_end = bounds[index + 1]; node.* = .{ .first = current[members_start].first, .end = current[members_end - 1].end, .members_start = members_start, .members_end = members_end, }; } return nodes; } fn treeShapePlan( allocator: std.mem.Allocator, entries: []const FCard, k: u4, cap: usize, ) std.mem.Allocator.Error!TreeShapePlan { std.debug.assert(k >= min_k and k <= max_k); std.debug.assert(cap >= 1 and cap <= max_construct_height); if (std.debug.runtime_safety) { for (entries, 0..) |entry, index| { std.debug.assert(entry.hash != null); if (index != 0) { std.debug.assert(compareBytes(entries[index - 1].filename, entry.filename) == .lt); } } } var arena_state = std.heap.ArenaAllocator.init(allocator); errdefer arena_state.deinit(); const arena = arena_state.allocator(); const span: usize = @as(usize, 1) << k; const min = span / 4; const max = 4 * span; const leaves = try treeShapeLeafNodes(arena, entries, k, min, max); if (leaves.len == 0) return .{ .arena_state = arena_state, .levels = &.{} }; var levels: std.ArrayList(TreeShapeLevel) = .empty; try levels.append(arena, .{ .nodes = leaves }); var current = leaves; var height: usize = 1; while (height < cap) : (height += 1) { const next = try treeShapeInteriorNodes( arena, entries, current, k, height, min, max, ); if (next.len == 0) break; try levels.append(arena, .{ .nodes = next }); current = next; } return .{ .arena_state = arena_state, .levels = try levels.toOwnedSlice(arena) }; } fn treeBuildLeafLevel( arena: std.mem.Allocator, entries: []const FCard, nodes: []const TreeShapeNode, algo: HashAlgo, subs: *std.ArrayList(SubArtifact), ) std.mem.Allocator.Error![]const []const u8 { const names = try arena.alloc([]const u8, nodes.len); for (nodes, names) |node, *name| { const bytes = try serializeLeaf(arena, entries[node.first..node.end]); name.* = try nameArtifact(arena, algo, bytes); try subs.append(arena, .{ .name = name.*, .bytes = bytes, .key = entries[node.first].filename, .height = 0 }); } return names; } fn treeBuildInteriorLevel( arena: std.mem.Allocator, entries: []const FCard, nodes: []const TreeShapeNode, children: []const TreeShapeNode, child_names: []const []const u8, algo: HashAlgo, height: u16, subs: *std.ArrayList(SubArtifact), ) std.mem.Allocator.Error![]const []const u8 { std.debug.assert(children.len == child_names.len); const names = try arena.alloc([]const u8, nodes.len); for (nodes, names) |node, *name| { const members = try arena.alloc(Node, node.members_end - node.members_start); const member_children = children[node.members_start..node.members_end]; for (members, member_children, node.members_start..) |*member, child, index| { member.* = .{ .key = entries[child.first].filename, .name = child_names[index] }; } const bytes = try serializeInterior(arena, members); name.* = try nameArtifact(arena, algo, bytes); try subs.append(arena, .{ .name = name.*, .bytes = bytes, .key = entries[node.first].filename, .height = height }); } return names; } fn treeBuildFromPlan( allocator: std.mem.Allocator, entries: []const FCard, algo: HashAlgo, plan: *const TreeShapePlan, ) std.mem.Allocator.Error!TreeBuild { var arena_state = std.heap.ArenaAllocator.init(allocator); errdefer arena_state.deinit(); const arena = arena_state.allocator(); if (plan.isFlat()) { return .{ .arena_state = arena_state, .subs = &.{}, .s = &.{} }; } var subs: std.ArrayList(SubArtifact) = .empty; var names = try treeBuildLeafLevel(arena, entries, plan.levels[0].nodes, algo, &subs); var level_index: usize = 1; while (level_index < plan.levels.len) : (level_index += 1) { names = try treeBuildInteriorLevel( arena, entries, plan.levels[level_index].nodes, plan.levels[level_index - 1].nodes, names, algo, @intCast(level_index), &subs, ); } const root = plan.levels[plan.levels.len - 1].nodes; const s = try arena.alloc(SCard, root.len); for (s, root, names) |*card, node, name| { card.* = .{ .filename = entries[node.first].filename, .hash = name }; } const subs_slice = try subs.toOwnedSlice(arena); std.debug.assert(subs_slice.len >= s.len); return .{ .arena_state = arena_state, .subs = subs_slice, .s = s }; } /// Submanifests §6.2 canonical tree construction over a check-in's file /// entries. /// /// `entries` are the canonical `e1 < ... < eN` file entries that a flat /// baseline emits after [FossilArtifact] §4.6.3 reserved-name exclusions. /// Strict filename order and a hash on every card are preconditions: ordering /// belongs to manifest assembly and a hashless card is a delta delete marker. /// /// `k` is the §6.3 project-pinned parameter. The caller owns the §6.3 /// out-of-range flat fallback; an out-of-range value is a programmer error here. /// /// The returned `TreeBuild` must be deinitialized. Its `subs` are in §6.2 /// storage order; `isFlat()` is the §6.2 step-2 fewer-than-two-groups result. /// An enabled writer that emits a flat manifest where construction yields a /// tree does not conform. pub fn buildTree( allocator: std.mem.Allocator, entries: []const FCard, k: u4, algo: HashAlgo, ) std.mem.Allocator.Error!TreeBuild { return buildTreeCapped(allocator, entries, k, algo, max_construct_height); } /// `buildTree` with §6.2 step 3's height cap as a parameter. The cap is NOT a /// policy knob -- `buildTree` is the only conforming entry point and always /// passes `max_construct_height`. It is a parameter because reaching height 16 /// needs a name set no test can hold (each level divides by ~MAX, and the /// non-reducing stop fires long before), so the bound would otherwise be /// unexercised code: the inline cap-2 test below drives the same `break` the /// height-16 rule drives, which is the only way to hold that loop bound. fn buildTreeCapped( allocator: std.mem.Allocator, entries: []const FCard, k: u4, algo: HashAlgo, cap: usize, ) std.mem.Allocator.Error!TreeBuild { var plan = try treeShapePlan(allocator, entries, k, cap); defer plan.deinit(); return treeBuildFromPlan(allocator, entries, algo, &plan); } // --------------------------------------------------------------------------- // Tests // --------------------------------------------------------------------------- // Residual unit tests that exercise file-private decls (kept inline; // making those decls pub merely to test them would leak the interface). const a1_1_manifest = rfc_vectors.artifact_a1_1_sha1_manifest; const A_CARD_HASH40: []const u8 = "0123456789" ** 4; // 40 hex chars const TEST_TS = "2007-07-21T14:09:59"; // §4.6.4 writer form, reused across bodies const HASH40_HIGH: []const u8 = "f" ** 40; // sorts above A_CARD_HASH40 (§4.5.3) fn buildArtifact(buf: []u8, body: []const u8) []const u8 { std.debug.assert(buf.len >= body.len + 35); @memcpy(buf[0..body.len], body); var digest_buf: [32]u8 = undefined; const digest = selfChecksum(body, &digest_buf); buf[body.len] = 'Z'; buf[body.len + 1] = ' '; @memcpy(buf[body.len + 2 ..][0..32], digest); buf[body.len + 34] = '\n'; const total = body.len + 35; std.debug.assert(buf[total - 1] == '\n'); return buf[0..total]; } test "artifact §5.1: diagnosticName maps the nine structural type codes (control, technote, forum post)" { try std.testing.expectEqualStrings("manifest", ArtifactType.manifest.diagnosticName()); try std.testing.expectEqualStrings("cluster", ArtifactType.cluster.diagnosticName()); try std.testing.expectEqualStrings("control", ArtifactType.control.diagnosticName()); try std.testing.expectEqualStrings("wiki", ArtifactType.wiki.diagnosticName()); try std.testing.expectEqualStrings("ticket", ArtifactType.ticket.diagnosticName()); try std.testing.expectEqualStrings("attachment", ArtifactType.attachment.diagnosticName()); try std.testing.expectEqualStrings("technote", ArtifactType.event.diagnosticName()); try std.testing.expectEqualStrings("forum post", ArtifactType.forum.diagnosticName()); // submanifests §4.1 Table row, column 3. try std.testing.expectEqualStrings("submanifest", ArtifactType.submanifest.diagnosticName()); } test "artifact §4.1: frameNoZ enforces gates 1-3 without the §6.2 Z gate" { try std.testing.expect(frameNoZ("") == null); // gate 1: empty try std.testing.expect(frameNoZ("C hello") == null); // gate 1: no final LF try std.testing.expect(frameNoZ("C\n") == null); // gate 3: len < 10 try std.testing.expect(frameNoZ("c cccccccc\n") == null); // gate 3: byte0 not A-Z try std.testing.expect(frameNoZ("CCcccccccc\n") == null); // gate 3: byte1 not SP try std.testing.expect(frameNoZ("C ccccccc\n") != null); // passes gates 1-3 } test "artifact §4.1/§6.2: parseWindow matches parse on Z-valid input and reports a Z mismatch parse rejects" { const gpa = std.testing.allocator; var buf: [256]u8 = undefined; const body = "C hello\nD " ++ TEST_TS ++ "\n"; const good = buildArtifact(&buf, body); // appends a VALID §6.2 Z card // Z valid: both paths agree — a manifest (C ⇒ §5.3 fallback MANIFEST). { try std.testing.expectEqual(ZVerdict.match, verifyZCard(good)); var m1 = try parse(gpa, good); defer m1.deinit(); var m2 = try parseWindow(gpa, good); defer m2.deinit(); try std.testing.expectEqual(ArtifactType.manifest, m1.kind); try std.testing.expectEqual(ArtifactType.manifest, m2.kind); } // Corrupt one hex digit of the stored Z digest: `parse` (gate 4) rejects, // `parseWindow` still assembles, and the mismatch stays observable — the // window reports rather than gates (B-artifact-5). { var bad_buf: [256]u8 = undefined; @memcpy(bad_buf[0..good.len], good); const bad = bad_buf[0..good.len]; const zpos = bad.len - 3; // inside the 32-hex digest, before the final LF bad[zpos] = if (bad[zpos] == 'a') 'b' else 'a'; try std.testing.expectEqual(ZVerdict.mismatch, verifyZCard(bad)); try std.testing.expectError(error.SyntaxError, parse(gpa, bad)); var mw = try parseWindow(gpa, bad); defer mw.deinit(); try std.testing.expectEqual(ArtifactType.manifest, mw.kind); } } test "artifact §3.3: computed name is lowercase hex" { var out: [64]u8 = undefined; const sha1_name = artifactName(.sha1, a1_1_manifest, &out); for (sha1_name) |c| try std.testing.expect(isHexLower(c)); var out2: [64]u8 = undefined; const sha3_name = artifactName(.sha3_256, "hello world\n", &out2); for (sha3_name) |c| try std.testing.expect(isHexLower(c)); } test "artifact §4.7.6-m5: perm x wins over l; else l is symlink; else regular" { // Lines 1196-1199. const cases = [_]struct { perm: ?[]const u8, want: FileMode }{ .{ .perm = "x", .want = .executable }, .{ .perm = "l", .want = .symlink }, .{ .perm = "w", .want = .regular }, .{ .perm = "xl", .want = .executable }, // x wins .{ .perm = "wl", .want = .symlink }, .{ .perm = "", .want = .regular }, .{ .perm = null, .want = .regular }, .{ .perm = "abc", .want = .regular }, }; for (cases) |c| { try std.testing.expectEqual(c.want, fileModeOf(c.perm)); } } test "artifact §6.3.4-r1: uppercase R fails the byte-exact commit check" { const files = [_]TrackedFile{ .{ .name = "alpha.txt", .content = "hello world\n" }, .{ .name = "beta.txt", .content = "fossil artifact format\n" }, .{ .name = "gamma.txt", .content = "R card test\n" }, }; var out: [32]u8 = undefined; const recomputed = aggregateChecksum(&files, &out); for (recomputed) |c| try std.testing.expect(isHexLower(c)); var uppercased: [32]u8 = undefined; for (recomputed, 0..) |c, i| uppercased[i] = std.ascii.toUpper(c); // Byte-exact compare against an always-lowercase recomputed digest -- // an uppercase R card fails this even though it is numerically correct. try std.testing.expect(!std.mem.eql(u8, &uppercased, recomputed)); } test "artifact §5.1: undetermined type is always resolved (sentinel never final)" { // Code 0 is never implemented as a value (m1); a census with no // type-setting card still resolves to a concrete type via fallback. try std.testing.expectEqual(ArtifactType.control, determineType(.{ .letters = maskOfLetters("DZ") })); try std.testing.expectEqual(ArtifactType.manifest, determineType(.{ .letters = maskOfLetters("CDZ") })); } test "artifact §5.2: allowed and required sets match Table 4" { const Row = struct { t: ArtifactType, allowed: []const u8, required: []const u8 }; const rows = [_]Row{ // submanifests §4.2 Table 1 revises the MANIFEST row (S joins the // allowed set) and adds the SUBMANIFEST row. .{ .t = .manifest, .allowed = "BCDFNPQRSTUZ", .required = "DZ" }, .{ .t = .cluster, .allowed = "MZ", .required = "MZ" }, .{ .t = .control, .allowed = "DTUZ", .required = "DTUZ" }, .{ .t = .wiki, .allowed = "CDLNPUWZ", .required = "DLUWZ" }, .{ .t = .ticket, .allowed = "DJKUZ", .required = "DJKUZ" }, .{ .t = .attachment, .allowed = "ACDNUZ", .required = "ADZ" }, .{ .t = .event, .allowed = "CDENPTUWZ", .required = "DEWZ" }, .{ .t = .forum, .allowed = "DGHINPUWZ", .required = "DUWZ" }, .{ .t = .submanifest, .allowed = "FSZ", .required = "Z" }, }; // inline: maskOfLetters needs its argument comptime-known, and rows is // itself a comptime-known literal array. inline for (rows) |row| { try std.testing.expectEqual(maskOfLetters(row.allowed), allowed_mask.get(row.t)); try std.testing.expectEqual(maskOfLetters(row.required), required_mask.get(row.t)); } } test "artifact §5.2: a card outside the allowed set is rejected" { const Row = struct { c: Census, want_type: ArtifactType }; // Each baseline satisfies its type's required set plus one letter // outside the allowed set; the extra letter is never type-setting, so // the finalized type is unaffected (event's extra, 'A', is // type-setting but alphabetically precedes 'E' and so loses per r1). const rows = [_]Row{ .{ .c = .{ .letters = maskOfLetters("BDWZ") }, .want_type = .manifest }, .{ .c = .{ .letters = maskOfLetters("CMZ") }, .want_type = .cluster }, // Not 'C': control has no type-setting letter, so (unlike every // other row here) it reaches §5.3's fallback, and 'C' present // would flip the fallback result to MANIFEST (p2). .{ .c = .{ .letters = maskOfLetters("DTUWZ") }, .want_type = .control }, .{ .c = .{ .letters = maskOfLetters("DLTUWZ") }, .want_type = .wiki }, .{ .c = .{ .letters = maskOfLetters("CDJKUZ") }, .want_type = .ticket }, .{ .c = .{ .letters = maskOfLetters("ADPZ") }, .want_type = .attachment }, .{ .c = .{ .letters = maskOfLetters("ADEWZ") }, .want_type = .event }, .{ .c = .{ .letters = maskOfLetters("CDGUWZ") }, .want_type = .forum }, }; for (rows) |row| { try std.testing.expectEqual(row.want_type, determineType(row.c)); try std.testing.expectError(error.DisallowedCard, classify(row.c)); } } test "artifact §5.2: a missing required card is rejected" { const rows = [_]Census{ // Manifest, Z missing. Not "D missing": a D-less MANIFEST is // reassigned to SUBMANIFEST (submanifests §4.3) and then rejected by // that type's allowed set instead. .{ .letters = maskOfLetters("BD") }, .{ .letters = maskOfLetters("M") }, // cluster, Z missing .{ .letters = maskOfLetters("DUZ") }, // control, T missing .{ .letters = maskOfLetters("LUWZ") }, // wiki, D missing .{ .letters = maskOfLetters("JKUZ") }, // ticket, D missing .{ .letters = maskOfLetters("AZ") }, // attachment, D missing .{ .letters = maskOfLetters("DEZ") }, // event, W missing .{ .letters = maskOfLetters("GUWZ") }, // forum, D missing .{ .letters = maskOfLetters("F") }, // submanifest, Z missing }; for (rows) |c| { try std.testing.expectError(error.MissingRequiredCard, classify(c)); } } test "submanifests §4.4: checkSemantics rejects a SUBMANIFEST with neither F nor S" { // "A SUBMANIFEST MUST contain at least one F card or at least one S // card." No byte sequence reaches this check -- §4.2 legality rejects // every D-less route to MANIFEST that carries neither letter first (see // the artifact_test.zig companion) -- so the check is exercised where it // lives, on the census. try std.testing.expectError( error.SubmanifestEmpty, checkSemantics(.submanifest, .{ .letters = maskOfLetters("Z") }), ); // With either letter present it passes; with both it does not. try checkSemantics(.submanifest, .{ .letters = maskOfLetters("FZ") }); try checkSemantics(.submanifest, .{ .letters = maskOfLetters("SZ") }); try std.testing.expectError( error.SubmanifestFileAndSCard, checkSemantics(.submanifest, .{ .letters = maskOfLetters("FSZ") }), ); try std.testing.expectError( error.SubmanifestFileWithoutHash, checkSemantics(.submanifest, .{ .letters = maskOfLetters("FZ"), .f_hashless = true }), ); // The delete marker is only forbidden inside a SUBMANIFEST: a MANIFEST // with a hashless F card is the §8.2 delta deletion, and passes here. try checkSemantics(.manifest, .{ .letters = maskOfLetters("BDFZ"), .f_hashless = true }); } test "artifact §5.2: legality is checked against the finalized type" { // M sets the type to CLUSTER; CLUSTER allows only M and Z, so the // extra C card is rejected only if the check ran against CLUSTER, not // some other type (C is legal on several other types). const c = Census{ .letters = maskOfLetters("CM") }; try std.testing.expectEqual(ArtifactType.cluster, determineType(c)); try std.testing.expectError(error.DisallowedCard, classify(c)); } test "artifact §5.2: a manifest with neither C nor U is accepted" { const c = Census{ .letters = maskOfLetters("BDZ") }; try std.testing.expectEqual(ArtifactType.manifest, try classify(c)); } test "artifact §5.2: a wiki without a U card is rejected" { const c = Census{ .letters = maskOfLetters("DLWZ") }; try std.testing.expectError(error.MissingRequiredCard, classify(c)); } test "artifact §5.2: an artifact with no Z card is rejected here" { // Required-complete-minus-Z per type: even though §4.1's checksum // gate tolerates an absent Z card, §5.2 rejects it for every type. const rows = [_]Census{ .{ .letters = maskOfLetters("BD") }, .{ .letters = maskOfLetters("M") }, .{ .letters = maskOfLetters("DTU") }, .{ .letters = maskOfLetters("DLUW") }, .{ .letters = maskOfLetters("DJKU") }, .{ .letters = maskOfLetters("AD") }, .{ .letters = maskOfLetters("DEW") }, .{ .letters = maskOfLetters("DGUW") }, }; for (rows) |c| { try std.testing.expectError(error.MissingRequiredCard, classify(c)); } } test "artifact §5.3: the alphabetically latest type-setting card wins" { try std.testing.expectEqual(ArtifactType.cluster, determineType(.{ .letters = maskOfLetters("AM") })); try std.testing.expectEqual(ArtifactType.wiki, determineType(.{ .letters = maskOfLetters("BL") })); try std.testing.expectEqual(ArtifactType.forum, determineType(.{ .letters = maskOfLetters("EG") })); // D carried so the winning MANIFEST assignment is observed as MANIFEST, // not rewritten by the submanifests §4.3 reassignment. try std.testing.expectEqual(ArtifactType.manifest, determineType(.{ .letters = maskOfLetters("ABD") })); // S is the latest MANIFEST-setting letter and loses to a later one. try std.testing.expectEqual(ArtifactType.manifest, determineType(.{ .letters = maskOfLetters("BDS") })); } test "artifact §5.3: fallback resolves by C/P presence" { // Each MANIFEST probe carries D: without it the fallback result is // reassigned to SUBMANIFEST (submanifests §4.3), which is a separate test. try std.testing.expectEqual(ArtifactType.manifest, determineType(.{ .letters = maskOfLetters("CD") })); try std.testing.expectEqual(ArtifactType.manifest, determineType(.{ .letters = maskOfLetters("DP"), .p_parents = 1 })); try std.testing.expectEqual(ArtifactType.control, determineType(.{ .letters = maskOfLetters("DZ") })); // P card present but bare (zero parent tokens, §4.7.13 p1) does not // count as "P card parents recorded". try std.testing.expectEqual(ArtifactType.control, determineType(.{ .letters = maskOfLetters("P"), .p_parents = 0 })); } test "artifact §5.3: §5.2 legality runs after the fallback finalizes the type" { // No C, no P parents -> fallback to CONTROL; N is not in CONTROL's // allowed set, so this can only fail as DisallowedCard if the check // ran against the fallback-finalized type. const control_case = Census{ .letters = maskOfLetters("DNTUZ") }; try std.testing.expectEqual(ArtifactType.control, determineType(control_case)); try std.testing.expectError(error.DisallowedCard, classify(control_case)); // C present -> fallback to MANIFEST; W is not in MANIFEST's allowed // set. const manifest_case = Census{ .letters = maskOfLetters("CDWZ") }; try std.testing.expectEqual(ArtifactType.manifest, determineType(manifest_case)); try std.testing.expectError(error.DisallowedCard, classify(manifest_case)); } test "artifact §5.4: a CONTROL artifact with a self-referential T card is rejected" { const c = Census{ .letters = maskOfLetters("DTUZ"), .t_self_ref = true }; try std.testing.expectError(error.ControlSelfTag, classify(c)); const ok = Census{ .letters = maskOfLetters("DTUZ"), .t_self_ref = false }; try std.testing.expectEqual(ArtifactType.control, try classify(ok)); } test "artifact §5.4: an EVENT artifact with a non-self-referential T card is rejected" { const c = Census{ .letters = maskOfLetters("DETWZ"), .t_not_self_ref = true }; try std.testing.expectError(error.EventTagNotSelfRef, classify(c)); } test "artifact §5.4: an EVENT artifact with a T card lacking the + prefix is rejected" { const c = Census{ .letters = maskOfLetters("DETWZ"), .t_self_ref = true, .t_not_plus = true, }; try std.testing.expectError(error.EventTagNotPlus, classify(c)); const ok = Census{ .letters = maskOfLetters("DETWZ"), .t_self_ref = true, .t_not_plus = false, }; try std.testing.expectEqual(ArtifactType.event, try classify(ok)); } test "artifact §5.4: a FORUM artifact with both H and I cards is rejected" { const c = Census{ .letters = maskOfLetters("DHIUWZ") }; try std.testing.expectError(error.ForumHeadAndReply, classify(c)); } test "artifact §5.4: a FORUM artifact whose P card lists more than one parent is rejected" { const rejected = Census{ .letters = maskOfLetters("DGPUWZ"), .p_parents = 2 }; try std.testing.expectError(error.ForumMultiParent, classify(rejected)); const ok = Census{ .letters = maskOfLetters("DGPUWZ"), .p_parents = 1 }; try std.testing.expectEqual(ArtifactType.forum, try classify(ok)); } test "artifact §5.2/§5.4: a well-formed artifact of each type is accepted" { const Row = struct { c: Census, t: ArtifactType }; const rows = [_]Row{ .{ .c = .{ .letters = maskOfLetters("BDZ") }, .t = .manifest }, .{ .c = .{ .letters = maskOfLetters("MZ") }, .t = .cluster }, .{ .c = .{ .letters = maskOfLetters("DTUZ") }, .t = .control }, .{ .c = .{ .letters = maskOfLetters("DLUWZ") }, .t = .wiki }, .{ .c = .{ .letters = maskOfLetters("DJKUZ") }, .t = .ticket }, .{ .c = .{ .letters = maskOfLetters("ADZ") }, .t = .attachment }, .{ .c = .{ .letters = maskOfLetters("DEWZ") }, .t = .event }, .{ .c = .{ .letters = maskOfLetters("DGUWZ") }, .t = .forum }, }; for (rows) |row| { try std.testing.expectEqual(row.t, try classify(row.c)); } } test "artifact §4.5.2/§A.1.1: repeatable-card fields expose wire-order runs" { // §4.7.6: a baseline manifest's F cards all carry a hash (deferred // enforcement -- see assertNoDeleteMarkers) -- give both a hash so this // stays a legal artifact under that eventual rule, not just today's parse. var buf: [200]u8 = undefined; const bytes = buildArtifact(buf[0..], "D " ++ TEST_TS ++ "\nF alpha.txt " ++ A_CARD_HASH40 ++ "\nF beta.txt " ++ HASH40_HIGH ++ "\n"); var m = try parse(std.testing.allocator, bytes); defer m.deinit(); try std.testing.expectEqual(ArtifactType.manifest, m.kind); try std.testing.expectEqual(@as(usize, 2), m.f.len); try std.testing.expectEqualStrings("alpha.txt", m.f[0].filename); try std.testing.expectEqualStrings("beta.txt", m.f[1].filename); } test "submanifests §6.2 step 3: the height cap terminates construction at the capped level" { // §6.2 step 3: "construction MUST NOT create a node of height 16", i.e. // the h loop stops after forming height 15. That bound cannot be reached // by a test: each level divides the node count by roughly MAX, and the // non-reducing stop fires long before 16 levels, so a name set that walks // into the cap does not fit in a test (or in a repository). The bound is // still load-bearing -- without it the loop is unbounded -- so it is a // PARAMETER of `buildTreeCapped` and exercised at a small value here. // `buildTree`, the only conforming entry point, always passes 16. // // Sixty names at k = 1 build four levels uncapped (the shape the // artifact_test.zig step-3 threshold test pins). Capping at 2 must stop // after forming height 1, leaving those nodes as the manifest's own S run: // strictly fewer sub-manifests and a strictly wider S run than the // uncapped build. A loop with no bound produces the uncapped numbers. const gpa = std.testing.allocator; var arena_state = std.heap.ArenaAllocator.init(gpa); defer arena_state.deinit(); const a = arena_state.allocator(); const entries = try a.alloc(FCard, 60); for (entries, 0..) |*e, i| { const content = try std.fmt.allocPrint(a, "/* {d:0>4} */\n", .{i}); const hash = try a.alloc(u8, 64); _ = artifactName(.sha3_256, content, hash[0..64]); e.* = .{ // Fixed-width digits, so numeric and §4.5.3 lexical order coincide. .filename = try std.fmt.allocPrint(a, "p{d:0>4}.c", .{i}), .hash = hash, .perm = null, .old_name = null, .mode = .regular, }; } var full = try buildTreeCapped(gpa, entries, 1, .sha3_256, max_construct_height); defer full.deinit(); var capped = try buildTreeCapped(gpa, entries, 1, .sha3_256, 2); defer capped.deinit(); try std.testing.expectEqual(@as(usize, 62), full.subs.len); try std.testing.expectEqual(@as(usize, 2), full.s.len); try std.testing.expectEqual(@as(usize, 51), capped.subs.len); try std.testing.expectEqual(@as(usize, 16), capped.s.len); // The relation, stated independently of the counts: capping strictly // truncates, and the cap only ever moves the top level into the manifest. try std.testing.expect(capped.subs.len < full.subs.len); try std.testing.expect(capped.s.len > full.s.len); // Both are still trees, and both partition the same 60 entries. try std.testing.expect(!capped.isFlat() and !full.isFlat()); }