Readers and writers for Git's objects — blob, tree, commit, tag — as typed values over bytes, built on the EBNF front end over the byte alphabet (fjs/ebnf/byte). The two DISOT issues under todo/ build on Git and neither can start without reading Git objects as typed values: git-name-resolution resolves a name by reading the root entries of a commit's tree and one blob under it, and git-trusted-timestamp-signatures reconstructs a commit's signed payload from its headers and writes a commit back. This directory is the decoder, and this file is the record of what a grammar can and cannot do for the formats.

• object/ — the loose object envelope, <type> SP <size> NUL: a grammar up to the NUL, a reader that slices the payload and holds it to the size, and a writer.

• header/ — the header block a commit and a tag share, and the message after it: a generic grammar over key SP value LF lines with continuation, a reader to a header list, the lookups by position and by key, and a writer that returns the block byte for byte.

• ident/ — an author, committer or tagger value, name SP <email> SP time SP tz, read as a second pass over the bytes a header holds: a try* reader that refuses what git fsck refuses, and a writer.

• tree/ — a tree's entries, mode SP name NUL id, for a repository's id width: a reader that reads what git fsck would flag, a validate that refuses it the way fsck does, mode as the number an entry's digits spell, and a writer.

• refname/ — what names a ref takes, by the rules git check-ref-format applies: the byte rules over the whole name, and the rule each component between slashes must pass. A tag's tag header is a ref name, which is why the tag module asks, and HEAD, a loose ref and a packed-refs line carry one too.

• ref/ — the three files a repository keeps its refs in, each as the grammar it is: a loose ref, a symbolic ref such as HEAD, and packed-refs. The three do not agree with each other — a loose ref need not end in LF and ignores anything after its first line, where packed-refs requires LF on every line and refuses a second comment — so each rule here was measured against Git rather than assumed.

• pack/ — a packfile's framing and the delta instructions inside one, with no effects: an entry's payload is a zlib stream, so nothing can say where one entry ends without inflating it, and walking the file belongs to the reader that inflates. Three different varints appear in a pack and two of them look alike — the odd one is an ofsDelta's distance back, most significant group first with a + 1 per continuation byte, which is what makes its spelling unique and what decides whether a base lands in the right place.

• packidx/ — a pack index, .idx, from an object id to where its entry begins in the .pack beside it. Length-framed and so a decoder rather than a grammar. Both live versions are read into one shape — version 2 with its magic and separate tables, version 1 with its ids and offsets interleaved — because the version says how the bytes were laid out and nothing about what they mean. The ids' order is checked and not trusted, since the lookup is a search and a search over ids that do not ascend answers wrongly instead of failing.

• bytes/ — what the binary formats above are read with: u32be and u64be, the unsigned big-endian words, multiplied rather than shifted because << signs the top bit, and startsWith for a magic number or a name's prefix. Each takes the indexed array a reader already made with byteArray, not the lazy Bytes.

• refstore/ — the refs a repository holds, over the effects: tryRoots for every one of them, tryResolve for a name in hand; and refstore/write/, the writers over the same name rules: tryWrite to put one at an id — the loose file, through the .lock name Git takes, created and filled in one exclusive open so no second writer and no symlink can reach the pathname in between, and reading packed-refs and statting the ref's own path first for the collision no other answer catches: Git lets no ref name be a directory prefix of another, and neither a packed name nor a symlink to a directory gives a mkdir or a rename anything to trip over. tryDelete takes a name out: its packed-refs line, then its loose file, then its reflog, under Git's own two locks, in the order that never lets a stale packed id become the ref again, and the name itself rather than what a symbolic ref there points to. Two rules live here because no reader of one file can decide them: a loose ref shadows the packed line of the same name by existing rather than by being good, so a loose file that is no ref leaves the name with no value instead of the packed one; and a symbolic ref is followed five lookups and no further, which is Git's bound and what catches a ref pointing at itself. A file under refs/ whose name is no ref name gets one of the two answers Git gives: the two file-name conventions its own walk skips — a component beginning with ., one ending in .lock — are skipped in silence, and every other broken name refuses the whole listing, which is Git's bad ref, measured.

• tag/ — a tag as a second pass over the header block: object, type, tag and tagger as functions over the header list, read by position as Git reads them, and a validate.

• commit/ — a commit the same way: tree, parent, author and committer by position, encoding, gpgsig and mergetag by key, the last read as a tag by the tag module, and a validate.

• oid/ — an object id between its two spellings, the raw bytes a tree entry holds and the hex text a header holds, and of, the id an object has at the repository's width: SHA-1 at 20 bytes, SHA-256 at 32.

• inflater/ — fjs/zlib/inflate, the pure inflater, fed the chunks a read gives, and what comes of it as the refusals the host's inflate effect used to give, so a caller that tells them apart by code is told nothing new.

• loose/ — a loose object file read whole, inflated by that and past its envelope. One of the two places a real repository meets the decoder; packstore/ below is the other, and is the one a clone actually takes.

• packstore/ — the same for the other place an object lives: from an id to the object a pack below objects/pack/ holds, through the .idx beside it. Two rules here are the effects' and not the format's. An entry carries no length — its header says what the object inflates to and nothing about how many bytes of the file its zlib stream takes — so the entry is read up to where the next one begins, which is the index's question and packidx's after, and the inflater finds the end of the stream inside it; and a delta chain is walked rather than recursed, for the reason walk/ walks. A refDelta names its base by id and may name one stored after it, which is where index-pack --fix-thin appends the base a fetched pack arrived without, so nothing here assumes a base precedes the delta and a chain is bounded by the pack's object count instead.

• config/ — Git's config grammar: the file as (section, key, value) entries, read a character at a time as Git's own parser reads it — quoted values and their escapes, a header that ends mid-line, a key without a value — and the readers of one key over them, which read it as Git does: every assignment in order, the last one winning, and as Git's int or bool each assignment judged as the reader reaches it. What a key means is its reader's, not the grammar's.

• alternates/ — an objects/info/alternates file as the object directories it names, decoded line shape by line shape as Git reads it: comments and blank lines skipped, a C-quoted line unquoted, a path ended at its first NUL, and a relative entry joined below the objects/ directory holding the file.

• format/ — the repository format a config declares and the id width that follows, read through config/'s readers: extensions.objectFormat absent is SHA-1, sha256 under repositoryformatversion = 1 is SHA-256, and a repository format Git refuses is refused.

• store/ — from an id to the object it names, checked: the loose file at the id's path or the packs through packstore/, whichever answers, hashed with oid's of and refused where the hash is not the id. The loose file is read first and anything but a good object there — no file, no stream, no object, another object — asks the packs, since Git answers a packed copy over a loose one that cannot be read and the hash check stands behind either, and the same two questions are put to each directory objects/info/alternates names, and to the directories those borrow from, six deep — where Git stops, measured. A borrowing already reached is skipped and one that cannot be read is passed over, as Git passes over it. Two line shapes name a directory this cannot reach — a path spelled in bytes, and the mangled second entry Git makes of text after a closing quote — and each is read as an ordinary path that is not found rather than refused, since a miss loses one borrowing where a refusal loses the whole store (alternates/todo/alternates-line-quirks.md). objectsDirs answers that list and readIn reads over it, so a caller reading many objects resolves the borrowings once instead of per object.

• walk/ — the three steps from a name to bytes, over whatever reads objects: peel, a tag to what it names; tryEntries, a commit or a tree to the entries of its tree; and tryEntry, the entry a path names. It reads no object it need not, so a path naming a submodule answers that entry, and it refuses what a corrupt repository makes ambiguous: a tag or a commit Git's own parse refuses, a tag whose target is not the type it declared, a tree naming one name twice, and a path descending through an entry whose mode is no directory — the mode's S_IFMT bits, which is the question Git's own S_ISDIR puts, so 40755 descends as 40000 does and 140000 does not.

  Both of its loops are walks over the effects rather than recursions, and the chain of ids peel has already read is a map rather than a list. Neither is a matter of taste. A Read that answers values — an in-memory store, a proof's — makes step call its own continuation, so a recursion costs a frame or two per link and a deep chain or a long path exhausts the stack; and a list of ids is scanned and copied whole at every link, which is quadratic in a chain Git puts no bound on. A walk's loop is flat in the item count whatever the Read answers, and the map answers and grows in the logarithm.

  Both readers refuse a payload under the length Git's own parse requires before it reads a header — the id's hexadecimal digits plus 24 for a tag, plus 6 for a commit — since that is what the headers each needs cost at their shortest, and nothing shorter could have held them.

• repo/ — from a worktree to the repository directory that holds its objects: .git is the repository, or a file whose gitdir: line names one, and that directory is the repository unless its commondir names another. One rule for a git init worktree, a --separate-git-dir one and a linked one.

• types.ts — Bytes, the type of a field the format leaves unbounded, Oid and OidBytes, the one fixed-width field and its width, and ObjectType.

• testlib.f.mjs — objects Git wrote, checked in as bytes and each carrying the id Git gave it: a signed merge commit of this repository and its root tree, and from a scratch repository a signed tag, a merge of one with the tag whole in mergetag, a tree with every mode, that tag's loose file, and a commit and a tree under SHA-256. Nothing in code calls git.

A loose object is one zlib stream. Inflated, it is an ASCII header and the payload, and the object id is the hash of the inflated whole:

<type> SP <size> NUL <payload>

type is one of blob, tree, commit, tag; size is the payload length in decimal ASCII. The hash is SHA-1 in today's repositories and SHA-256 after the hash-function transition, so an object id is 20 or 32 raw bytes, and every hex spelling of one is 40 or 64 characters. Which of the two a repository uses is a property of the repository, not of any object — every reader that meets an id is parameterized by it, OidBytes, a number since times takes its bound as one.

The four payloads:

• blob — the file content, arbitrary bytes. Nothing to parse, and no module: a blob's payload is what the envelope reader hands back.

• commit — a header block, an empty line, and the message:

  tree <hex>
  parent <hex>              zero or more
  author <ident>
  committer <ident>
  encoding <name>           optional
  gpgsig <first line>       optional; continued on lines that begin with SP
   <continuation line>
  <other headers>           mergetag, and any header a tool adds
  
  <message>                 to the end of the object, arbitrary bytes
  

  The empty line and the message are optional together: an object whose bytes end at its last header's LF is one Git accepts and none of its own tools write, and Payload's message is null for it. That keeps it apart from an object with an empty line and an empty message, which are two byte strings and so two ids, and the writer puts back whichever it was given.

  Every header is key SP value LF, and a line beginning with SP continues the value of the header before it, LF included. That is how a multi-line signature is one header, and how mergetag carries a whole tag object as its value. Git reads tree, parent, author and committer by position and ignores a header it does not know; the ones it knows are checked after, not by the line reader.

• tag — the same shape: object <hex>, type <type>, tag <name>, tagger <ident> (absent in very old tags), other headers, an empty line, the message. A signature is part of the message, from the line that begins its armor to the end.

• tree — a sequence of entries, no separators, no terminator:

  <mode> SP <name> NUL <id>
  

  mode is octal ASCII without padding — 100644, 100755, 120000, 160000, and 40000 for a subtree, five digits, not six. Those are the modes Git writes and the ones validate accepts; a walk asks less of a mode it did not write, since Git does. name is any bytes but NUL; a slash is forbidden by git fsck, not by the reader. id is the raw object id, 20 or 32 bytes, every byte value allowed, and it is what delimits the entry: nothing follows it but the next entry or the end.

An ident is name SP < email > SP time SP tz: the name any bytes but the brackets and LF, spaces included; the email the same; time a decimal Unix timestamp Git can hold; tz a sign and four digits.

The object formats are specified across gitformat-pack, gitformat-signature and the Git Internals chapter; the loose object envelope has no document of its own beyond object-file.c.

The repository has two ways to read a binary format, and the choice between them follows the framing:

• Delimiter-framed structure — a field ends at a byte the grammar can name, or after a fixed count — is what a grammar is for, and fjs/ebnf/ plus its LL(1) backend is the tool. Commit and tag payloads are lines, headers, and one empty line; a tree entry is two delimiters and a fixed-width id. All of it is LL(1).
• Length-framed structure — a field's extent is a number read from an earlier field — is not context-free, and fjs/asn.1/ is the precedent: a hand-written decoder over a Vec, popFront by popFront. A zlib stream and a packfile are this kind, and they get a decoder, not a grammar.

The loose envelope is both: the NUL is a delimiter, so a grammar reads the header and stops there, leaving the rest as the payload, and the size is a claim about that rest, which the reader verifies and refuses when it does not match (DESIGN.md §10). That is what Git does too: the size is a check, not what delimits the payload.

The alphabet is bytes, not Unicode. A Git object is not text: the id in a tree entry is 20 raw bytes and may spell anything, a file name is whatever bytes the file system gave, a message is in the charset the encoding header names or in none, and an old commit's ident may not be valid UTF-8 at all. Decoding the object to code points first would either fail on a valid object or substitute U+FFFD into it — the plausible wrong value DESIGN.md §10 forbids — and it would lose the bytes the trusted-timestamp work hashes. So the parser's symbols are bytes, 0..255, and every value it extracts that is not a number is bytes — a Vec where the format fixes the width, a byte list where it does not. A text view of a message or a name is a layer above, through fjs/text/utf8, when a consumer wants one and only for the encoding the object declares. That alphabet is fjs/ebnf/byte, landed for this consumer; its symbols are non-negative safe integers with EOF at -1, so a byte is an ordinary symbol and no byte has to stand in for the end of input.

Where LL(1) is not enough, the answer is another pass, not a stronger parser. One lookahead byte cannot tell tree from tag, a known header from an unknown one, or a name from the space before its <; it does not have to. The first pass reads the shape every object shares and understands none of it — a word, a header line, a value up to its delimiter — and a later pass reads what the first one cut out: the header list is interpreted after the parse, an ident is a grammar over one header's value, and a mergetag value is a tag object read by the tag grammar. Each pass is a grammar over the previous pass's output, which is the layering layered-parser describes, so the machinery is one LL(1) backend applied more than once rather than a backend that backtracks. It is also how Git reads its own objects. Three places show the principle at its sharpest:

• The envelope's type is one word up to the space, with the mapping accepting the four types and refusing any other word: a variant of the four keywords is not LL(1), since tree and tag share their first byte.
• The header block is generic, the way Git's own reader is. A variant over the known keys would conflict with the unknown-header branch on every first byte, and would refuse a commit the moment a tool adds a header.
• An ident's name is read up to <, and the reader requires its last byte to be SP and drops it: the name's repetition may end in SP, so ' <' after it is a first/follow conflict the backend refuses.

The mergetag pass has one loss, and it is the fold's. Git folds a tag into the header by putting SP before each of the tag's lines and completing the last, so the LF that ends the tag ends the header too and the header's framing takes it; the commit module gives it back, and every tag a tool of Git's writes comes back byte for byte, its id recomputable. A tag whose own bytes never ended in LF — one git hash-object -t tag writes and git tag and git mktag never do — folds to the same header as the same tag with one, so nothing in the commit can tell them apart: no representation is possible, and refusing would refuse a commit git fsck accepts. Giving the LF back is the choice because it is Git's own: show_one_mergetag, behind git verify-commit and git log --show-signature, hashes the value with the LF its reader keeps on every line, and so loses the same tag the same way. The bytes here are the bytes Git reads back.

An id, a name, an email, a header and a message are bytes, and which byte type a field has follows from whether the format bounds it:

type Bytes = List<number>                         // unbounded, one byte per item
type Oid = Vec                                    // 20 or 32 bytes, raw
type OidBytes = 20 | 32                           // the repository's width
type ObjectType = 'blob' | 'tree' | 'commit' | 'tag'
type Ident = { name: Bytes, email: Bytes, time: bigint, tz: string }
type Header = readonly [key: Bytes, value: Bytes]
type Commit = { headers: readonly Header[], message: Bytes }
type Tag = { headers: readonly Header[], message: Bytes }
type TreeEntry = { mode: Bytes, name: Bytes, oid: Oid }

A Vec holds at most 128 KiB, so it is the type of a field the format bounds — an id — and a byte list is the type of one it does not: a message runs to the end of the object, a header value may hold a whole tag, and a name is whatever the file system gave. Where a Vec is built, it is built with tryU8ListToVec and a null is refused, never truncated (DESIGN.md §6). A header's key is bytes too, not a string: the grammar reads any byte but SP and LF, Git accepts what it reads, and a reader that promises the block byte for byte cannot then refuse a key for its spelling. The well-known keys are compared as bytes.

A commit and a tag are their header list and their message, and nothing else: one representation, so there is no second one for a writer to choose over or a caller to leave stale. headers keeps every header as read, the well-known ones included, in order and byte for byte, because the signature work needs the block verbatim to reconstruct a payload, and a header the reader does not know must survive a read and a write unchanged. The well-known fields — tree, parents, author, committer, object, type, name, tagger — are functions over the headers, total once validate has accepted the object and a panic on one it has not; a change to a commit is a change to its headers, and the writer serializes what it is given.

A tree entry's mode is kept as the digits it was spelled with, since 0100644 and 100644 are one number and two spellings — Git writes the unpadded one and git fsck only warns about the other, so both exist — and a writer owes the spelling it read. mode reads the number off it as Git keeps it, the low 32 bits, and validate refuses the padded spelling as fsck's zeroPaddedFilemode flags it: the reader reads such an entry and the writer returns it byte for byte, and only the check that vouches for an object says no to it.

Every reader is a try* returning null for what its grammar does not cover, and reads everything its grammar does, an object git fsck would flag included; the writer returns it byte for byte. validate, one per object type, is where an object is refused, naming why, by the rules fsck applies: required headers and their order, a hex id of the repository's width, an ident where one is required, a NUL in a header, the mode set, the entry order. Those are what fsck reports as an error. Three things it only warns of are refused as well, as this module's own choice, each said where it is made: a tag name no ref takes, which git mktag refuses to write; a NUL in a commit's message, which no tool of Git's writes; and a zero-padded tree mode, zeroPaddedFilemode, which the paragraph above this one explains. What fsck only notes and Git writes passes. The one check fsck does not make: a mergetag must be a tag the tag module vouches for, so that mergetags is total. The ident reader is the exception that refuses at the grammar: Git's own reader is lenient and old history holds idents without an email or with a malformed zone, and this reader reads what fsck vouches for, a time Git can hold included, and refuses the rest, not repairing it; the raw header stays in the list either way, and which of those forms are worth accepting is decided when one is met, as an issue naming the object.

Each is a limit stated, refused where it is crossed, and none approximated:

• The common directory. repo finds the repository a worktree belongs to, and store and walk read at the directory they are given, so a caller puts the two together. What the id check means in a SHA-1 repository, and what a trust layer does about a hash that can collide, is todo/git-sha1-collisions.md.

• A refDelta whose base is not in the pack that names it is refused, and that is the answer rather than a gap. Packs are read — packstore/ answers from the .idx and the pack beside it, and store reads them beside the loose path — and such a pack is one index-pack --fix-thin did not complete. Git refuses it too, with the base in reach: measured on 2.43.0 over two hand-built packs alike but for where the base sits, the one holding its own base read the object at exit 0 and the one whose base was loose and in a second pack beside it exited 128. Resolving it through the whole store would read a pack every Git calls broken, so whether to be deliberately more capable is a decision rather than work: packstore/todo/thin-pack-base.md. Multi-pack indexes, bitmaps and the reverse index are not needed to read an object and are not here either.

• Appending to the reflog: refstore/todo/ref-writing.md. Reading the refs is done, and so are writing and deleting one — ref/ for the file grammars, refstore/'s tryRoots and tryResolve, and refstore/write/'s tryWrite and tryDelete over the effects. Every way the two writers are narrower than git update-ref — no check that the object is there or, under refs/heads/, that it is a commit, no core.sharedRepository mode, no reflog line, no dereference of a symbolic ref at the name, a name outside refs/ refused, and an empty directory at the name's path refused where Git removes it — is measured and listed in that issue. Reading the reflog is not done either, which is why tryRoots answers the refs and not everything the repository is keeping: a reflog entry keeps an object alive until it expires, and so does the index — a staged blob survives gc --prune=now though no ref names it and rev-list --all never lists it, both measured — so a caller must not prune by that list (refstore/todo/reflog-roots.md). The one repository that list cannot describe at all is refused: a packed-refs line naming HEAD is a root Git keeps beside the HEAD file's, and one entry per name holds neither answer (refstore/todo/packed-head.md).

• The Vec ceiling. maxLength in fjs/types/bit_vec is 2^20 bits, 128 KiB, and nothing the format leaves unbounded is safe from it, which is why every unbounded field is a byte list. It used to bind at the host's inflate, which took a Vec and gave one, so an object was refused on either side of its stream; the inflater here (fjs/zlib/inflate) is fed chunks and answers chunks, so an object read whole — loose, or stored whole in a pack — is refused for no length: a blob of 300 000 bytes is read through three windows and answered as a list over the chunks it inflated to. One bound of the same family remains, on a delta chain: a delta, the base it is applied to and the object it builds are dense arrays, a number a byte, and pack/ holds them to maxDeltaBytes, 8 MiB, by the size their entries declare, before anything is inflated. A representation of those that is not a number a byte lifts it (pack/todo/dense-delta.md).

  A whole file is not bound by it any more, which is the half that used to fail on ordinary repositories rather than extreme ones. fjs/effects/node's readWhole is one operation: the host opens the path once, reads it to the end under that descriptor, and answers the chunks it took — each a Vec and so within the cap, the file however many it takes — which readWholeBytes joins into a byte list, which has no cap. packed-refs is read that way: a record is 70 bytes at refs/heads/topic/feature-<n>, measured, so readFile was spent at about 1,870 refs and a repository of 4,000 branches writes a 282,939-byte file that Git reads without comment.

  One operation and not a fold over readBytes, because that one resolves the path per call. git pack-refs replaces packed-refs by rename on every run, so a windowed read could join an old prefix to a new suffix — and where the replacement is the same length, every window is exactly as long as it should be and nothing downstream can tell. The result parses and names refs no version of the file held. A caller cannot close that: stat carries no identity to compare and re-reading races the same way, so the snapshot is the host's to give.

  A ref file still goes through readFile, because it is one line and the extra operation per lookup would be paid on every name a walk reads.

• One Meta per byte. The LL(1) backend takes an array of symbols, each an object, and streams nothing. For commits, tags and trees that is fine; it is the reason a blob is never handed to a parser.

• git-name-resolution — the first consumer: the root entries of a commit's tree, and one blob under it.
• git-trusted-timestamp-signatures — every header verbatim, and the writer.
• doc/DESIGN.md — the ebnf migration, which reserved fjs/ebnf/byte/ for the first consumer that wanted it, this one, and is recorded there now that its plan is done.
• unicode-rules — the byte adapter's first design, as the half of that issue the text half left behind.
• layered-parser — bytes as the bottom alphabet of the pipeline; ident and mergetag are layers over it.
• fjs/ebnf/ll1/README.md — the backend, its conflicts, and the rewrite set the mappings are written against.
• fjs/asn.1 — the length-framed precedent, the shape a packfile decoder takes.