Re: [PATCH v4 01/13] commit-graph: add format document

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 20, 2018, 20:49 UTC
Message-ID: <xmqqa7w32xq7.fsf@gitster-ct.c.googlers.com>
In-Reply-To: <1519066406-81663-2-git-send-email-dstolee@microsoft.com>

Derrick Stolee <stolee@gmail.com> writes:

>  Documentation/technical/commit-graph-format.txt | 90 +++++++++++++++++++++++++
>  1 file changed, 90 insertions(+)
>  create mode 100644 Documentation/technical/commit-graph-format.txt

Hopefully just a few remaining nits. Overall I find this written really clearly.

Show 6 quoted lines

> +== graph-*.graph files have the following format:
> +
> +In order to allow extensions that add extra data to the graph, we organize
> +the body into "chunks" and provide a binary lookup table at the beginning
> +of the body. The header includes certain values, such as number of chunks,
> +hash lengths and types.

We no longer have lengths stored.

> + ...
> +  The remaining data in the body is described one chunk at a time, and
> +  these chunks may be given in any order. Chunks are required unless
> +  otherwise specified.

It is good that this explicitly says chunks can come in any order, and which ones are required. It should also say which chunk can appear multiple times. I think all four chunk types we currently define can have at most one instance in a file.

Show 9 quoted lines

> +CHUNK DATA:
> +
> +  OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)
> +      The ith entry, F[i], stores the number of OIDs with first
> +      byte at most i. Thus F[255] stores the total
> +      number of commits (N).
> +
> +  OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)
> +      The OIDs for all commits in the graph, sorted in ascending order.

Somewhere in this document, we probably would want to say that this format allows at most (1<<31)-1 commits recorded in the file (as CGET and EDGE uses 31-bit uint to index into this table, using MSB for other purposes, and the all-1-bit pattern is also special), and when we refer to "int-ids" of a commit, it is this 31-bit number that is an index into this table.

Show 26 quoted lines

> +  Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)
> +    * The first H bytes are for the OID of the root tree.
> +    * The next 8 bytes are for the int-ids of the first two parents
> +      of the ith commit. Stores value 0xffffffff if no parent in that
> +      position. If there are more than two parents, the second value
> +      has its most-significant bit on and the other bits store an array
> +      position into the Large Edge List chunk.
> +    * The next 8 bytes store the generation number of the commit and
> +      the commit time in seconds since EPOCH. The generation number
> +      uses the higher 30 bits of the first 4 bytes, while the commit
> +      time uses the 32 bits of the second 4 bytes, along with the lowest
> +      2 bits of the lowest byte, storing the 33rd and 34th bit of the
> +      commit time.
> +
> +  Large Edge List (ID: {'E', 'D', 'G', 'E'}) [Optional]
> +      This list of 4-byte values store the second through nth parents for
> +      all octopus merges. The second parent value in the commit data stores
> +      an array position within this list along with the most-significant bit
> +      on. Starting at that array position, iterate through this list of int-ids
> +      for the parents until reaching a value with the most-significant bit on.
> +      The other bits correspond to the int-id of the last parent.
> +
> +TRAILER:
> +
> +	H-byte HASH-checksum of all of the above.
> +