Re: Index format v5

[Michael Haggerty <mhagger@alum.mit.edu>]

On 05/03/2012 07:25 PM, Thomas Gummerer wrote:
> I have been drafting the Version 5 of the index format over the past
> few days with the help of Thomas Rast, Michael Haggerty, cmn and
> barrbrain on IRC. It will save with prefix compression on the path, and
> using a crc32 over the stat data, instead of the full data, since it is only
> used for checking if the file is changed. (Thanks Michael Haggerty for
> this hint. Unless we are missing something this will save another
> ~4 MB on the Webkit index.
>
>
>
> GIT index format
> ================
 > [...]

Here are some comments about the format document, version 55047b3d. 
They probably overlap with other feedback that you have gotten, but I 
don't have time to cross-correlate everything.  Hope it helps.

Overall
=======

I find the format definition pretty difficult to read.  The following
suggestions might make it easier to follow.

* You might want to give each of the elements C-like names; e.g.,
   "ndir (32 bits): number of directories in the index".  These names
   could be used as unambiguous references from other parts of the
   documentation.  The names could also be used in the implementing
   code, to make the correspondence with the format definition easier
   to follow.

* Name things consistently.  For example, "A number of sorted
   directories (see below)" should be changed to "A number of directory
   entries (see below), sorted by path name".

* Putting the above two things together, the description "A number of
   sorted directories" might become "direntries (ndir * directory
   entries): one directory entry for each of the ndir directories in
   the index, sorted by path name".

* Are all "offsets" relative to the start of the index file?  If so,
   it would be good to state this explicitly at the start (and maybe
   rename them "file positions"?).  If not, please be very explicit
   about where each offset is measured from, and whether it is signed
   or unsigned.

* You seem to switch randomly between counting sizes in bits vs bytes.
   Please try to be more consistent.  BTW, I think the size of an SHA1
   object name is more commonly described as "20 bytes" rather than
   "160 bits".

* The details of the extension data blocks are described in the first
   (overview) section, whereas it seems like they should be described
   in their own section following the "conflict data" section.  But
   wouldn't the presence of extension data blocks prevent the addition
   of conflict data?

* Are there situations (for example during conflicts?) when it is
   allowed to have directory and file entries with the same name?

* Does the index file include directory entries for empty directories?
   What about directories that contain only other directories?

Overview
========

* Does "32-bit size of the extension" include the whole extension data
   block (including header) or only the "extension data"?

Directory entry
===============

* "4-byte number of entries in the index that is covered by the tree
   this entry represents."  What does this include?
   Files/directories/both?  Recursive or non-recursive?

* "160-bit object name for the object that would result from writing
   this span of index as a tree."  Is this always valid?

* It might be convenient to store directory names with trailing '/'
   characters (except for the top-level directory, which can be stored
   as "").  That way (1) it is trivial to concatenate the directory
   name and the filename to produce the file path; (2) directories and
   files can be distinguished by name and therefore intermingled in
   lists; (3) such lists can be sorted using strcmp() without having to
   simulate an invisible '/' character.

File entry
==========

* I believe that only the basename is stored, not the whole path.  But
   then why is the encoding for '/' specified (there should be no '/'
   characters)?

* Why is the encoding of '.' specified?  Is it somehow significant for
   the index file format?

* Are file entries sorted by entire path or only by the basename?

Flat loading
============

* I found the explanation pretty incomprehensible.  Perhaps some
   pseudo-code would make it clearer?

* Since I can't understand the explanation, I'm not sure if this
   comment makes any sense.  But when traversing into a subdirectory,
   don't *all* of the remaining files from the parent directory need to
   be tucked away somewhere?

* At an even higher level of abstraction, your directory entry
   contains a count "number of entries in the index that is covered by
   the tree this entry represents".  If this count is recursive, then
   it seems like it would be enough to know how many entries will come
   from traversing a whole subdirectory tree.  So it should be possible
   to skip that many entries in the in-memory array and continue
   reading the file entries for the parent subdirectory.  For example,
   suppose our files are [A, B/1, B/2/a, B/2/b, B/3, C].  If I start by
   reading the files in the root directory, then I can fill the index
   array entries

       [A, -, -, -, -, C]

   because when I see that "B" is a directory containing a total of
   four entries, I just leave fours spaces for them in the array and
   continue with the next file, "C".  Of course I would have to
   remember (e.g., on a queue) that directory "B" still needs to be
   processed, and the starting index in the array where its entries
   have to be filled in.  Still, this jumping around would be in the
   RAM holding the index array pointers rather than in the file
   positions.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/