Artifact cef84f327c066b31d869f9da16ffcba97d0013c3267533f66a85d47aa267614e:
- File
src/artifact.zig
— part of check-in
[9897845809]
at
2026-07-28 01:49:53
on branch sub-manifest
— Sub-manifest: record why the final-group merge cap is unpinned
The merge fires when the two groups together hold at most MAX, and no test separates that from a strict comparison. Reaching the distinguishing case needs a natural boundary at exactly MAX minus the tail, which hash-driven boundaries do not produce in generated name sets; a search over two parameter values and nine hundred starts found no instance. Pinning it would mean choosing filenames by their leading zero bits rather than generating them. The note records the reasoning at the site so the gap is visible to the next reader. (user: dmestas, size: 226862) [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"); /// 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; } /// §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(); const comment_tok = it.next() orelse return null; // r1: no token if (comment_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 >= 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. fn fileMode(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 = fileMode(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 var value: []const u8 = ""; // m3: absent value is "", never null if (value_tok) |raw| { if (raw.len == 0) return null; // token = 1*tchar: no production 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 `cli.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, }; /// `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. 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 { 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 { 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 { std.debug.assert(subs.len != 0); // §5: only a tree manifest is looked up this way 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 std.debug.assert((view.subs.len == 0) != (view.files.len == 0)); // §4.4 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}; /// 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); } /// §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, }; /// 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 { std.debug.assert(keys.len != 0); // N = 0 exits before any scan (step 2) std.debug.assert(max >= 1); var bounds: std.ArrayList(usize) = .empty; try bounds.append(arena, 0); // "e1 starts the first group" var i: usize = 1; while (i < keys.len) : (i += 1) { // bound: keys.len - 1 iterations const open = i - bounds.items[bounds.items.len - 1]; // members so far std.debug.assert(open >= 1 and open <= max); // "each subsequent ei starts a new group if and only if the open group // holds MAX members, or zbits(name(ei)) >= k and the open group holds // at least MIN members." if (open == max or (zbits(keys[i]) >= threshold and open >= min)) { try bounds.append(arena, i); } } // KNOWN UNPINNED EDGE: the `<= max` below is the spec's "the two together // hold AT MOST MAX members" (§6.2 step 1), and no test discriminates it // from `< max`. Doing so needs a scan whose final group is under MIN and // whose predecessor holds exactly MAX-minus-that -- at k = 3, a natural // boundary at member 31 followed by exactly one trailing name. Boundaries // are hash-driven, so that alignment does not occur in generated name sets // (searched k = 3 and k = 4 over 900 starts, no instance). Pinning it // requires hand-selecting filenames by their zbits rather than generating // them. The neighbouring "capped by MAX" test covers the other side of the // bound, where the sum exceeds MAX and the merge is suppressed. // // "When the scan completes, if the final group holds fewer than MIN // members, a preceding group exists, and the two together hold at most MAX // members, the final group is merged into the group preceding it." if (bounds.items.len >= 2) { const last = bounds.items[bounds.items.len - 1]; const prev = bounds.items[bounds.items.len - 2]; if (keys.len - last < min and keys.len - prev <= max) { bounds.items.len -= 1; // merged: the boundary simply disappears } } try bounds.append(arena, keys.len); // closing sentinel: group i is [i, i+1) std.debug.assert(bounds.items.len >= 2); std.debug.assert(bounds.items[0] == 0); std.debug.assert(bounds.items[bounds.items.len - 1] == keys.len); return bounds.toOwnedSlice(arena); } /// The number of groups a `scanGroups` result describes (its sentinel is not a /// group). fn groupCount(bounds: []const usize) usize { std.debug.assert(bounds.len >= 2); return bounds.len - 1; } /// §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. fn serializeLeaf(arena: std.mem.Allocator, group: []const FCard) WriteError![]const u8 { std.debug.assert(group.len >= 1); var buf: std.ArrayList(u8) = .empty; for (group) |f| { // §4.4: "a sub-manifest F card without a hash" is a rejection vector -- // `buildTree` asserts this over its whole input before we get here. std.debug.assert(f.hash != null); try appendFCardTokens(appendCanonical, &buf, arena, f); } try appendZCard(&buf, arena); return buf.toOwnedSlice(arena); } /// §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 { std.debug.assert(members.len >= 1); 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); } /// 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); } /// submanifests §6.2 canonical tree construction over a check-in's file /// entries. /// /// `entries` is "the check-in's file entries e1 < ... < eN in canonical /// filename order -- the entries, identical tokens included, that a flat /// baseline manifest would emit as F cards after the reserved-name exclusions /// of [FossilArtifact], Section 4.6.3": exactly what `cli.composeFCards` /// already produces, which is why this takes F cards rather than a shape of /// its own. Strict ascending order and a hash on every card are preconditions, /// asserted here rather than repaired -- ordering belongs to manifest assembly, /// and a hashless entry is a delta's delete marker, which never partitions. /// /// `k` is the repository's PINNED partition parameter (§6.3). It is a /// parameter, never a choice: "A writer MUST take k from the pinned setting, /// MUST NOT derive a value per commit". The out-of-range fallback of §6.3 ("it /// MUST fall back to emitting flat manifests rather than substitute a parameter /// of its own") belongs to the caller holding the setting, so an out-of-range /// value is a programmer error here, not a silent flat result. /// /// Returns a `TreeBuild` the caller must `deinit`. `isFlat()` is §6.2 step 2's /// "fewer than two groups" exit; otherwise the caller MUST store `subs` in list /// order and emit `s` as the manifest's S run -- "an enabled writer that emits /// a flat manifest where the 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 { std.debug.assert(k >= min_k and k <= max_k); // §6.3 supported range std.debug.assert(cap >= 1 and cap <= max_construct_height); if (std.debug.runtime_safety) { for (entries, 0..) |e, i| { std.debug.assert(e.hash != null); // §4.4 leaf F cards carry hashes if (i != 0) std.debug.assert(compareBytes(entries[i - 1].filename, e.filename) == .lt); } } var arena_state = std.heap.ArenaAllocator.init(allocator); errdefer arena_state.deinit(); const arena = arena_state.allocator(); // §6.2: "The group limits MIN = 2^k / 4 (rounded down) and MAX = 4 * 2^k // count members ... never bytes: the same name set MUST partition // identically under either hash policy". k <= 12 keeps both inside usize. const span: usize = @as(usize, 1) << k; const min: usize = span / 4; const max: usize = 4 * span; // §6.2 step 2: "the case N = 0 (an empty check-in, which Fossil permits) // yields zero groups and a flat manifest carrying no F cards and no S // cards." N = 1 yields one group and takes the same exit below. if (entries.len == 0) return .{ .arena_state = arena_state, .subs = &.{}, .s = &.{} }; const leaf_keys = try arena.alloc([]const u8, entries.len); for (entries, leaf_keys) |e, *key| key.* = e.filename; // Step 1 at height 0: the boundary test is zbits(name) >= k (§6.1). const leaf_groups = try scanGroups(arena, leaf_keys, k, min, max); // Step 2: "If the scan yields fewer than two groups, the writer MUST emit a // flat manifest and no sub-manifests." if (groupCount(leaf_groups) < 2) return .{ .arena_state = arena_state, .subs = &.{}, .s = &.{} }; var subs: std.ArrayList(SubArtifact) = .empty; // The level under construction, in key order. var level: std.ArrayList(Node) = .empty; var gi: usize = 0; while (gi < groupCount(leaf_groups)) : (gi += 1) { const group = entries[leaf_groups[gi]..leaf_groups[gi + 1]]; const bytes = try serializeLeaf(arena, group); const name = try nameArtifact(arena, algo, bytes); try subs.append(arena, .{ .name = name, .bytes = bytes }); try level.append(arena, .{ .key = group[0].filename, .name = name }); } // Step 3: "For h = 1, 2, ...: let n1..nm be the height-(h-1) nodes in key // order." `h` is the height of the level being FORMED, which is the same // coordinate §6.1 uses ("a boundary between height-h nodes requires // zbits(key) >= (h+1)*k" -- k for leaves at h = 0, 2k at h = 1, which §A.1 // and §A.4 both confirm). var h: usize = 1; while (h < cap) : (h += 1) { std.debug.assert(level.items.len >= 2); const keys = try arena.alloc([]const u8, level.items.len); for (level.items, keys) |n, *key| key.* = n.key; // (h+1)*k with h <= 15 and k <= 12 is at most 192, inside a u16 and // well inside zbits' 0..256 range. const threshold: u16 = @intCast((h + 1) * @as(usize, k)); const groups = try scanGroups(arena, keys, threshold, min, max); // "If the scan, after the merge, yields a single group, or yields as // many groups as it was given nodes -- a non-reducing scan, which would // make every node a one-child parent -- the writer MUST disregard that // scan and emit one S card per height-(h-1) node, in key order, in the // manifest itself, and construction terminates." if (groupCount(groups) == 1 or groupCount(groups) == level.items.len) break; var next: std.ArrayList(Node) = .empty; var i: usize = 0; while (i < groupCount(groups)) : (i += 1) { const members = level.items[groups[i]..groups[i + 1]]; const bytes = try serializeInterior(arena, members); const name = try nameArtifact(arena, algo, bytes); try subs.append(arena, .{ .name = name, .bytes = bytes }); try next.append(arena, .{ .key = members[0].key, .name = name }); } level = next; } // Loop exit at h == cap is step 3's height cap, which `buildTree` fixes at // 16: "if the scan at h = 16 yields, after the merge, more than one group, // the writer MUST disregard that scan and emit one S card per height-15 // node in the manifest". The other two outcomes of that scan (a single // group, a non-reducing scan) already terminate with the same S run, so // running it at h = 16 could not change a byte -- the loop bound is the // whole rule. std.debug.assert(level.items.len >= 2); const s = try arena.alloc(SCard, level.items.len); for (level.items, s) |n, *card| card.* = .{ .filename = n.key, .hash = n.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 }; } // --------------------------------------------------------------------------- // 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 = @embedFile("rfc_vectors/artifact_a1_1_sha1_manifest.txt"); 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, fileMode(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()); }