{"thread":{"id":"30413","subject":"Index format v5","startedAt":"2012-05-03T17:25:12Z","lastAt":"2012-05-21T20:30:18Z","messageCount":49,"participants":["Thomas Gummerer","Thomas Rast","Ronan Keryell","Junio C Hamano","solo-git@goeswhere.com","Michael Haggerty","Nguyen Thai Ngoc Duy","Philip Oakley","Phil Hord","Robin Rosenberg"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"190658","messageId":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","threadId":"30413","inReplyTo":null,"subject":"Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-03T17:25:12Z","receivedAt":"2012-05-03T17:25:12Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"I have been drafting the Version 5 of the index format over the past\nfew days with the help of Thomas Rast, Michael Haggerty, cmn and\nbarrbrain on IRC. It will save with prefix compression on the path, and\nusing a crc32 over the stat data, instead of the full data, since it is only\nused for checking if the file is changed. (Thanks Michael Haggerty for\nthis hint. Unless we are missing something this will save another\n~4 MB on the Webkit index.\n\n\n\nGIT index format\n================\n\n= The git index file has the following format\n\n All binary numbers are in network byte order. Version 5 is described\n here.\n\n - A 16-byte header consisting of\n\n 4-byte signature:\n The signature is { 'D', 'I', 'R', 'C' } (stands for \"dircache\")\n\n 4-byte version number:\n The current supported versions are 2, 3, 4 and 5.\n\n 32-bit number of directories.\n\n 32-bit number of file entries.\n\n - Offset to the extensions.\n\n 32-bit number of extensions.\n\n 32-bit number offset to the extension. (Possibly none, as many as\n indicated in the 4-byte number of extensions)\n\n - A number of directory offsets (see below). [1]\n\n - A number of sorted directories (see below). [2]\n\n - 32-bit crc32 checksum for the header, extension offsets and directories.\n\n - A number of file offsets (see below). [1]\n\n - A number of file entries (see below).\n\n - A number of entries for conflicted data/resolved conflicts (see below).\n\n - Extensions\n\n Extensions are identified by signature. Optional extensions can\n be ignored if GIT does not understand them.\n\n GIT supports an arbitrary number of extension, but currently none\n is implemented. [3]\n\n 4-byte extension signature. If the first byte is 'A'..'Z' the\n extension is optional and can be ignored.\n\n 32-bit size of the extension\n\n 32-bit crc32 checksum of the extension signature and size\n\n Extension data\n\n\n== Directory entry offsets\n\n 32-bit offset to the directory.\n\n This part is needed for making the directory entries bisectable and\n thus allowing a binary search.\n\n== Directory entry\n\n Directory entries are sorted in lexicographic order by the name\n of their path starting with the root.\n\n Path names (variable length) relative to top level directory (without the\n leading slash). '/' is used as path separator. '.' indicates the root\n directory. The special patch components \"..\" and \".git\" (without quotes)\n are disallowed. Trailing slash is also disallowed.\n\n 1 nul byte to terminate the path.\n\n 32-bit offset to the first file of a directory\n\n 32-bit offset to conflicted/resolved data at the end of the index.\n 0 if there is no such data. [4]\n\n 4-byte number of subtrees this tree has\n\n 4-byte number of entries in the index that is covered by the tree this\n entry represents. (entry_count) (-1 if the entry is invalid)\n\n 160-bit object name for the object that would result from writing\n this span of index as a tree.\n\n The last 24 bytes are for the cache tree. An entry can be in an\n invalidated state which is represented by having -1 in the entry_count\n field. If an entry is in invalidated state, the next entry will begin\n after the number of subtrees, and the 160-bit object name is dropped.\n\n The entries are written out in the top-down, depth-first order. The\n first entry represents the root level of the repository, followed by\n the first subtree - let's call it A - of the root level, followed by\n the first subtree of A, ...\n\n== File entry offsets\n\n 32-bit offset to the directory.\n\n This part is needed for making the directory entries bisectable and\n thus allowing a binary search.\n\n== File entry\n\n File entries are sorted in ascending order on the name field, after the\n respective offset given by the directory entries.\n\n File name (variable length). Nul bytes are not allowed in file names and\n they have no leading slash. They are 7-bit ASCII encoded.\n\n 1 nul byte to terminate the filename.\n\n A 16-bit 'flags' field split into (high to low bits)\n\n 1-bit assume-valid flag\n\n 1-bit conflict flag\n\n 2-bit stage (during merge)\n\n 2-bit mode (0 = 1000644 (regular file without execution\n permission), 1 = 1000755 (regular file with execution\n permission), 2 = 1010000 (symbolic link), 3 = 1110\n (gitlink)) [5]\n\n 1-bit skip-worktree flag (used by sparse checkout)\n\n 1-bit intent-to-add flag (used by \"git add -N\")\n\n 8-bit unused, must be zero [6]\n\n 32-bit mtime seconds, the last time a file's data changed\n this is stat(2) data\n\n 32-bit mtime nanosecond fractions\n this is stat(2) data\n\n 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n\n 160-bit SHA-1 for the represented object\n\n 32-bit crc32 checksum for the file entry\n\n== Conflicted data\n\n A conflict is represented in the index as a set of higher stage entries.\n These entries are stored at the end of the index. When a conflict is\n resolved (e.g. with \"git add path\"). A bit is flipped, to indicate that\n the conflict is resolved, but the entries will be kept, so that\n conflicts can be recreated (e.g. with \"git checkout -m\", in case users\n want to redo a conflict resolution from scratch.\n\n - NUL-terminated filename of the entry\n\n - A 8-bit 'flags' field split into:\n\n - 1-bit conflicted state (conflicted/resolved) (1 if conflicted)\n\n - 7-bit unused\n\n - Three 4-byte octal numbers, entry mode of entries in stage 1 to 3 (a\n missing stage is represented by \"0\" in this field);\n and\n\n - At most three 160-bit object names of the entry in stages from 1 to 3\n (nothing is written for a missing stage).\n\n - 32-bit crc32 checksum over one conflicted entry.\n\n== Design explanations\n\n[1] The directory and file offsets are included in the index format\n to enable bisectability of the index, for binary searches.Updating\n a single entry and partial reading will benefit from this.\n\n[2] The directories are saved in their own block, to be able to\n quickly search for a directory in the index. They include a\n offset to the (lexically) first file in the directory.\n\n[3] The data of the cache-tree extension and the resolve undo\n extension is now part of the index itself, but if other extensions\n come up in the future, there is no need to change the index, they\n can simply be added at the end.\n\n[4] To avoid rewrites of the whole index when there are conflicts or\n conflicts are being resolved, conflicted data will be stored at\n the end of the index. To mark the conflict resolved, just a bit\n has to be flipped. The data will still be there, if a user wants\n to redo the conflict resolution.\n\n[5] Since only 4 modes are effectively allowed in git but 32-bit are\n used to store them, having a two bit flag for the mode is enough\n and saves 4 byte per entry.\n\n[6] The length of the file name was dropped, since each file name is\n nul terminated anyway.\n\n[7] Since all stat data (except mtime and ctime) is just used for\n checking if a file has changed a checksum of the data is enough.\n In addition to that Thomas Rast suggested ctime could be ditched\n completely (core.trustctime=false) and thus included in the\n checksum. This would save 24 bytes per index entry, which would\n be about 4 MB on the Webkit index.\n (Thanks for the suggestion to Michael Haggerty)\n"},{"id":"190661","messageId":"87obq5p1t0.fsf@thomas.inf.ethz.ch","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-03T18:16:59Z","receivedAt":"2012-05-03T18:16:59Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Gummerer writes:\n\n> 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n> ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n[...]\n> [7] Since all stat data (except mtime and ctime) is just used for\n> checking if a file has changed a checksum of the data is enough.\n> In addition to that Thomas Rast suggested ctime could be ditched\n> completely (core.trustctime=false) and thus included in the\n> checksum. This would save 24 bytes per index entry, which would\n> be about 4 MB on the Webkit index.\n> (Thanks for the suggestion to Michael Haggerty)\n\nThis is the part I'm most curious about. Are we missing anything?\nMichael brought it up on IRC: the stat() results are only used to test\nwhether they are still the same, with the exception of the mtime (which\nalso undergoes raciness checks).\n\nAs far as I can see, none of st_{ino,dev,uid,gid} are useful for\nanything. st_size might conceivably be used as a hint for a buffer\nsize, but nobody actually does that. The ctime undergoes stricter\nchecks, but AFAICS it's also all about whether it has changed, and\nbesides that can be turned off. We think all of those fields can be\nreplaced by an arbitrary hash/CRC and only tested for equality. 32 bits\nshould be plenty, probably even if we just xor the values together.\n\nSo what's wrong in this thinking?\n\n[The one flaw I found so far is that this makes it impossible to convert\nback to v2-4 without at the very least refreshing the index. Do we\ncare?]\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"190664","messageId":"87ehr15dnh.fsf@an-dro.info.enstb.org","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Ronan Keryell","fromEmail":"ronan.keryell@hpc-project.com","sentAt":"2012-05-03T18:21:22Z","receivedAt":"2012-05-03T18:21:22Z","isPatch":false,"sender":{"key":"ronan.keryell@hpc-project.com","avatar":null},"body":">>>>> On Thu, 3 May 2012 19:25:12 +0200, Thomas Gummerer said:\n\n Thomas> I have been drafting the Version 5 of the index format over\n Thomas> the past few days with the help of Thomas Rast, Michael\n Thomas> Haggerty, cmn and barrbrain on IRC. It will save with prefix\n Thomas> compression on the path, and using a crc32 over the stat\n Thomas> data, instead of the full data, since it is only used for\n Thomas> checking if the file is changed. (Thanks Michael Haggerty\n Thomas> for this hint. Unless we are missing something this will\n Thomas> save another ~4 MB on the Webkit index.\n\nGreat!\n\nBut I wonder whether it may not worth to investigate a 64-bit version for\nthe offsets and so on, just in case...\n-- \n Ronan KERYELL |\\/ Phone: +1 408 658 9453\n Wild Systems / HPC Project |/)\n 5201 Great America Parkway, Suite 320 K Ronan.Keryell@wild-systems.com\n Santa Clara, CA 95054 |\\ skype:keryell\n USA | \\ http://wild-systems.com\n"},{"id":"190669","messageId":"7vd36lf634.fsf@alter.siamese.dyndns.org","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-03T18:54:39Z","receivedAt":"2012-05-03T18:54:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Gummerer writes:\n\n> I have been drafting the Version 5 of the index format over the past\n> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n> barrbrain on IRC.\n\nHrm, so if there is anything glaringly wrong below, should I reduce the\n\"trustable reviewer karma point\" from these people? Or did you forget to\nsay \"but remaining errors are mine\" ;-)?\n\n> GIT index format\n> ================\n>\n> = The git index file has the following format\n>\n> All binary numbers are in network byte order. Version 5 is described\n> here.\n>\n> - A 16-byte header consisting of\n>\n> 4-byte signature:\n> The signature is { 'D', 'I', 'R', 'C' } (stands for \"dircache\")\n>\n> 4-byte version number:\n> The current supported versions are 2, 3, 4 and 5.\n>\n> 32-bit number of directories.\n\n> 32-bit number of file entries.\n\nI take these two numbers mean \"we have this many directory entries in the\nindex\" and \"we have this many file entries in the index\"; I found it\nunclear during my first scan.\n\nHave you considered expressing these new \"directories\", \"files\" and\nassociated data as a new (mandatory) extension?\n\n> - Offset to the extensions.\n>\n> 32-bit number of extensions.\n\nWhy is this necessary? It means that the writer needs to enumerate how\nmany extensions it is going to write before starting to write, unless it\nis willing to seek back and fill this. And it is not like the reader will\nfirst allocate an array to hold uniformly sized extension and will be\nhelped to have the number of entries upfront in order to do the\nallocation.\n\nWhat purpose does this serve?\n\n> 32-bit number offset to the extension. (Possibly none, as many as\n> indicated in the 4-byte number of extensions)\n\nWhy is this needed? It appears that there is no field that points at the\nbeginning of array that stores \"directory offsets\", nor \"file offsets\", so\nI am assuming that you will be scanning the index file to find them. Why\ncan't the extensions be handled exactly the same way?\n\n> - A number of directory offsets (see below). [1]\n>\n> - A number of sorted directories (see below). [2]\n>\n> - 32-bit crc32 checksum for the header, extension offsets and directories.\n\nWhat does \"32\" in \"crc32\" stand for ? ;-)\n\n> - A number of file offsets (see below). [1]\n>\n> - A number of file entries (see below).\n>\n> - A number of entries for conflicted data/resolved conflicts (see below).\n>\n> - Extensions\n>\n> Extensions are identified by signature. Optional extensions can\n> be ignored if GIT does not understand them.\n>\n> GIT supports an arbitrary number of extension, but currently none\n> is implemented. [3]\n>\n> 4-byte extension signature. If the first byte is 'A'..'Z' the\n> extension is optional and can be ignored.\n>\n> 32-bit size of the extension\n>\n> 32-bit crc32 checksum of the extension signature and size\n>\n> Extension data\n>\n>\n> == Directory entry offsets\n\nThe name \"directory entry offset\" does not seem to appear anywhere before\nthis, so it is unclear what this section of the documentation is trying to\ndescribe. Is this the same as \"directory offsets\" above? In other words,\n\"A number of directory offsets (see below).\" above is an array of something,\nand this section is trying to describe what that something is?\n\n> 32-bit offset to the directory.\n\nI take it is \"offset relative to the beginning of the file in the index\".\n\n> This part is needed for making the directory entries bisectable and\n> thus allowing a binary search.\n>\n> == Directory entry\n>\n> Directory entries are sorted in lexicographic order by the name\n> of their path starting with the root.\n>\n> Path names (variable length) relative to top level directory (without the\n> leading slash). '/' is used as path separator. '.' indicates the root\n> directory. The special patch components \"..\" and \".git\" (without quotes)\n> are disallowed. Trailing slash is also disallowed.\n\nI understood \"the root\" to mean \"the top level of the directory hierarchy\"\n(i.e. the directory that corresponds to the top level of the working\ntree), but it needs to be explained better. Using '.' for root sounds\nsomewhat questionable, though. Why not a string of length 0?\n\nWhen an index represents a D/F conflict, some stages may have a directory\nD while others do not have D (but have a regular file at D). Doesn't\ndirectory entry need to have a stage information?\n\n> 1 nul byte to terminate the path.\n>\n> 32-bit offset to the first file of a directory\n\nWhat does this point at? Does it point into the array of \"file offsets\"\nor the array of \"file entries\"?\n\n> 32-bit offset to conflicted/resolved data at the end of the index.\n> 0 if there is no such data. [4]\n>\n> 4-byte number of subtrees this tree has\n\nWhich is an undefined number unless you specify which stage you are\ntalking about.\n\n> 4-byte number of entries in the index that is covered by the tree this\n> entry represents. (entry_count) (-1 if the entry is invalid)\n>\n> 160-bit object name for the object that would result from writing\n> this span of index as a tree.\n>\n> The last 24 bytes are for the cache tree. An entry can be in an\n> invalidated state which is represented by having -1 in the entry_count\n> field. If an entry is in invalidated state, the next entry will begin\n> after the number of subtrees, and the 160-bit object name is dropped.\n\nBy \"The last 24 bytes\", do you mean the \"4-byte number of entries...\" and\n\"160-bit object name\"?\n\n> The entries are written out in the top-down, depth-first order. The\n> first entry represents the root level of the repository, followed by\n> the first subtree - let's call it A - of the root level, followed by\n> the first subtree of A, ...\n>\n> == File entry offsets\n>\n> 32-bit offset to the directory.\n\nWhat directory? The containing directory? What does this point at? Does\nit point into which array?\n\n> This part is needed for making the directory entries bisectable and\n> thus allowing a binary search.\n>\n> == File entry\n>\n> File entries are sorted in ascending order on the name field, after the\n> respective offset given by the directory entries.\n>\n> File name (variable length). Nul bytes are not allowed in file names and\n> they have no leading slash. They are 7-bit ASCII encoded.\n\nIs this a name relative to its containing directory (i.e. without leading\ncomponents)? Or is it a full path relative to the top level of the\nworking tree?\n\nI have some UTF-8 encoded files in my repository. Are they\nnow disallowed?\n\n> 1 nul byte to terminate the filename.\n>\n> A 16-bit 'flags' field split into (high to low bits)\n>\n> 1-bit assume-valid flag\n\nIs this \"assume unchanged\"?\n\n> 1-bit conflict flag\n>\n> 2-bit stage (during merge)\n\nHuh? When stage #0 entry exists for a given path, no other stages for the\nsame path can exist in the index. By definition, that is how a conflicted\npath is resolved. What is this separate \"conflict flag\" for?\n\n> 2-bit mode (0 = 1000644 (regular file without execution\n> permission), 1 = 1000755 (regular file with execution\n> permission), 2 = 1010000 (symbolic link), 3 = 1110\n> (gitlink)) [5]\n\nDon't penny-pinch bits like this. \n\n> 1-bit skip-worktree flag (used by sparse checkout)\n>\n> 1-bit intent-to-add flag (used by \"git add -N\")\n>\n> 8-bit unused, must be zero [6]\n>\n> 32-bit mtime seconds, the last time a file's data changed\n> this is stat(2) data\n>\n> 32-bit mtime nanosecond fractions\n> this is stat(2) data\n>\n> 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n> ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n\nGiving occassional false positive to \"did this change?\" is acceptable, but\nany false negative is absolutely unacceptable. How does this work with\nsomething like \"racy git\" situation (i.e. coming from \"mtime happens to be\nthe same as before\") but due to crc32 collisions?\n\nIf there is no good answer to the above question, I would have to say that\nanybody who suggested or passed this through review loses all the\naccumulated reviewer karma points (if s/he has accumulated any, that is).\n\n> 160-bit SHA-1 for the represented object\n>\n> 32-bit crc32 checksum for the file entry\n>\n> == Conflicted data\n\nI do not think the data described in this section should be conflicting.\nIt ought to be data that describe conflicted state. Perhaps you meant\n\"Conflict data\"?\n\n> A conflict is represented in the index as a set of higher stage entries.\n> These entries are stored at the end of the index. When a conflict is\n> resolved (e.g. with \"git add path\"). A bit is flipped, to indicate that\n> the conflict is resolved, but the entries will be kept, so that\n> conflicts can be recreated (e.g. with \"git checkout -m\", in case users\n> want to redo a conflict resolution from scratch.\n>\n> - NUL-terminated filename of the entry\n\nIs this a name relative to its containing directory (i.e. without leading\ncomponents)? Or a full path relative to the top-level of the working\ntree?\n\n> - A 8-bit 'flags' field split into:\n>\n> - 1-bit conflicted state (conflicted/resolved) (1 if conflicted)\n>\n> - 7-bit unused\n>\n> - Three 4-byte octal numbers, entry mode of entries in stage 1 to 3 (a\n> missing stage is represented by \"0\" in this field);\n> and\n>\n> - At most three 160-bit object names of the entry in stages from 1 to 3\n> (nothing is written for a missing stage).\n\nIt is allowed to have more than 1 entries in stage #1 to represent\nmultiple merge-base, so this needs to be rethought.\n\n> - 32-bit crc32 checksum over one conflicted entry.\n\nThere is no definition of \"one conflicted entry\"; be consistent and say\n\"Conflicted data\" as what the section header claims to describe.\n\n> == Design explanations\n>\n> [1] The directory and file offsets are included in the index format\n> to enable bisectability of the index, for binary searches.Updating\n> a single entry and partial reading will benefit from this.\n>\n> [2] The directories are saved in their own block, to be able to\n> quickly search for a directory in the index. They include a\n> offset to the (lexically) first file in the directory.\n>\n> [3] The data of the cache-tree extension and the resolve undo\n> extension is now part of the index itself, but if other extensions\n> come up in the future, there is no need to change the index, they\n> can simply be added at the end.\n>\n> [4] To avoid rewrites of the whole index when there are conflicts or\n> conflicts are being resolved, conflicted data will be stored at\n> the end of the index. To mark the conflict resolved, just a bit\n> has to be flipped. The data will still be there, if a user wants\n> to redo the conflict resolution.\n>\n> [5] Since only 4 modes are effectively allowed in git but 32-bit are\n> used to store them, having a two bit flag for the mode is enough\n> and saves 4 byte per entry.\n>\n> [6] The length of the file name was dropped, since each file name is\n> nul terminated anyway.\n\nThis is micronit, but I think we do this to save one strlen() for each\nread of the entry, except for unusually long paths where we fall back to\nstrlen(). A change like this needs to be justified better than simply\nsaying \"because we _could_ compute in a different way by spending extra\ncycles\".\n"},{"id":"190672","messageId":"7v8vh9f5nr.fsf@alter.siamese.dyndns.org","threadId":"30413","inReplyTo":"87obq5p1t0.fsf@thomas.inf.ethz.ch","subject":"Re: Index format v5","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-03T19:03:52Z","receivedAt":"2012-05-03T19:03:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> So what's wrong in this thinking?\n\nWe tolerate giving occasional false positive \"Yes\" to \"Has this changed?\",\nbut do not allow false negative \"No\". So the value st_{ino,dev,uid,gid}\ngives us is strictly \"these are not likely to change, but if even a single\nbit in them change, we need to suspect that it may have changed.\" The\nprimary field that protect us is mtime, and all the rest are more or less\nbelt-and-suspender safety.\n"},{"id":"190674","messageId":"8762cdm651.fsf@thomas.inf.ethz.ch","threadId":"30413","inReplyTo":"7vd36lf634.fsf@alter.siamese.dyndns.org","subject":"Re: Index format v5","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-03T19:11:38Z","receivedAt":"2012-05-03T19:11:38Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n>> [6] The length of the file name was dropped, since each file name is\n>> nul terminated anyway.\n>\n> This is micronit, but I think we do this to save one strlen() for each\n> read of the entry, except for unusually long paths where we fall back to\n> strlen(). A change like this needs to be justified better than simply\n> saying \"because we _could_ compute in a different way by spending extra\n> cycles\".\n\n(Partially also answering the whole \"what are these offsets\" confusion)\n\nThe bisectability has evolved to the point where we envision the\nstructure of a \"flat list\" (the directories, and the files in each\ndirectory) to have the format\n\n offset to entry 1 [1]\n ....\n offset to entry n\n\n entry 1, consisting of:\n name, nul-terminated\n rest of data:\n for dirs: cache-tree sha1, offset to files, etc.\n for files: stat data, content sha1, flags, etc.\n\nThat makes bisection very easy: the offsets point at the start of each\nstring, so you just strcmp() and get on with it.\n\nOn the other hand, by the time you can look at the flags, it's too late\nfor the strlen() optimization anyway, so meh. If you think it's\nimportant, we can perhaps lay it out so the rest of the data goes\nimmediately after the pointer. But so far it wasn't clear whether it's\nfixed-size, or uses some smart compression scheme. Tonight's edition\nhas a fixed length, so perhaps it would be preferable to keep the\nlength.\n\n\nFootnotes: \n[1] It probably doesn't matter whether this is relative to the position\nof the offset, or absolute (in terms of file pointer).\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"190677","messageId":"87pqalgiyv.fsf@thomas.inf.ethz.ch","threadId":"30413","inReplyTo":"7vd36lf634.fsf@alter.siamese.dyndns.org","subject":"Re: Index format v5","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-03T19:31:04Z","receivedAt":"2012-05-03T19:31:04Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Gummerer writes:\n>\n>> I have been drafting the Version 5 of the index format over the past\n>> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n>> barrbrain on IRC.\n>\n> Hrm, so if there is anything glaringly wrong below, should I reduce the\n> \"trustable reviewer karma point\" from these people? Or did you forget to\n> say \"but remaining errors are mine\" ;-)?\n\nHeh.\n\nPartly it's my fault, I told Thomas to get this out tonight for a single\nreason: Michael's CRC-over-stat idea is so radical that I wanted to know\nwhether there's anything wrong with it. So the misunderstanding is\nreally that this is not anywhere near the final result.\n\nBut yeah:\n\n> > 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n> > ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n> \n> Giving occassional false positive to \"did this change?\" is acceptable, but\n> any false negative is absolutely unacceptable. How does this work with\n> something like \"racy git\" situation (i.e. coming from \"mtime happens to be\n> the same as before\") but due to crc32 collisions?\n> \n> If there is no good answer to the above question, I would have to say that\n> anybody who suggested or passed this through review loses all the\n> accumulated reviewer karma points (if s/he has accumulated any, that is).\n\nIf this is a problem, then the fault is with me (and I do hope I have\nsome karma to lose...).\n\nNote that the scenario you outlined is not an issue. The entries other\nthan mtime and ctime are really only compared for equality, see\ne.g. ce_match_stat_basic(). Comparisons for equality never have false\nnegatives with any hash function. Collisions are false positives.\n\nUpon closer reading I noticed that the ie_match_stat and ce_match_stat_*\nfamily actually to distinguish between basically all the fields that can\nchange. But this knowledge is never actually put to use, except that\nthere's an optimized code path where\n\n* mode/type difference implies changed entry\n* size difference implies changed entry\n\nSo that does constitute an argument to not put the size in the\nstat-hash. Mode and type aren't part of it in the proposed format\nanyway.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"190678","messageId":"87k40tgix2.fsf@thomas.inf.ethz.ch","threadId":"30413","inReplyTo":"87pqalgiyv.fsf@thomas.inf.ethz.ch","subject":"Re: Index format v5","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-03T19:32:09Z","receivedAt":"2012-05-03T19:32:09Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast writes:\n\n> Comparisons for equality never have false negatives with any hash\n> function. Collisions are false positives.\n\nBah, shouldn't hit \"send\" so fast. There goes my karma :-D\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"190680","messageId":"20120503193846.GA31233@goeswhere.com","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"","fromEmail":"solo-git@goeswhere.com","sentAt":"2012-05-03T19:38:46Z","receivedAt":"2012-05-03T19:38:46Z","isPatch":false,"sender":{"key":"solo-git@goeswhere.com","avatar":null},"body":"On Thu, May 03, 2012 at 07:25:12PM +0200, Thomas Gummerer wrote:\n\n> 160-bit object name for the object that would result from writing\n> this span of index as a tree.\n\nWould now be a fun time to bring up the idea of eventually migrating\naway from 160-bit hashes? I love to keep reminding people that SHA-1\nis showing its age[1].\n\nEven if we don't add support for variable length hashes at this point,\nit would be nice to at least have the code written in a relatively\nhash-length-independent way, such that someone could come along and\nmake a new, very similar, format without rewriting much of the code.\n\nIf there is going to be support for different hash algorithms, or even\ndifferent length hashes, we need space in the file (before the first\nhash, obviously) to indicate what we're using; currently reserved.\n\nFor this, we need to decide on how we're going to store the algorithm;\nmy guesses would be either:\n\n* a (1-octet) enum, like tls (0: sha1/160, 1: sha2-256/160 [sha2's\n256-bit mode truncated to 160-bits using a recommended truncation mode],\n2: keccak-512, etc.); stopping at 127 (i.e. reserving the high-bit for\nfuture use), or\n\n* a lowascii string, with prefixed 1 (or 2?)-octet length, like ssh,\nusing the above format. If people believe that the chance of this being\nimplemented (within the lifespan of v5) is tiny, this octet can be\nreserved; i.e. a zero-length string means sha1/160.\n\n\ntl;dr: Please reserve one or more octet(s) early on for the details of\nthe hash, and think about people who want more than 20/40 octets\navailable when implementing it.\n\n--\nChris West (FauxFaux).\n\n[1]: http://csrc.nist.gov/groups/ST/hash/policy.html \"...and must use\nthe SHA-2 family of hash functions for these applications after 2010.\"\n"},{"id":"190685","messageId":"7vr4v1dmzc.fsf@alter.siamese.dyndns.org","threadId":"30413","inReplyTo":"87k40tgix2.fsf@thomas.inf.ethz.ch","subject":"Re: Index format v5","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-03T20:32:39Z","receivedAt":"2012-05-03T20:32:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Thomas Rast writes:\n>\n>> Comparisons for equality never have false negatives with any hash\n>> function. Collisions are false positives.\n>\n> Bah, shouldn't hit \"send\" so fast. There goes my karma :-D\n\nHeh, don't take \"karma\" thing too seriously. I was merely trying to be\nfunny and I seem to have failed the attempt.\n\nIt depends on what question you are asking, and against \"Did this change?\"\nquestion, saying \"No, it didn't\" when the right answer is \"Yes, it did\" is\na false negative. You are asking for a false negative if you substitute\nbyte-for-byte comparison with comparison of hashed results of the values\nthat needs to be compared.\n\nBut as I said, mtime is the primary thing that protects us, so it may not\nbe such a big deal.\n"},{"id":"190686","messageId":"CALgYhfOLGFK92833nZp5ny25+uoRnsygkH2M4yYRzU4JBE3Evw@mail.gmail.com","threadId":"30413","inReplyTo":"87ehr15dnh.fsf@an-dro.info.enstb.org","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-03T20:36:07Z","receivedAt":"2012-05-03T20:36:07Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On Thu, May 3, 2012 at 8:21 PM, Ronan Keryell\n wrote:\n>>>>>> On Thu, 3 May 2012 19:25:12 +0200, Thomas Gummerer said:\n>\n>    Thomas> I have been drafting the Version 5 of the index format over\n>    Thomas> the past few days with the help of Thomas Rast, Michael\n>    Thomas> Haggerty, cmn and barrbrain on IRC. It will save with prefix\n>    Thomas> compression on the path, and using a crc32 over the stat\n>    Thomas> data, instead of the full data, since it is only used for\n>    Thomas> checking if the file is changed. (Thanks Michael Haggerty\n>    Thomas> for this hint. Unless we are missing something this will\n>    Thomas> save another ~4 MB on the Webkit index.\n>\n> Great!\n>\n> But I wonder whether it may not worth to investigate a 64-bit version for\n> the offsets and so on, just in case...\n\n64-bit versions of the offsets were taken into consideration, but currently\nthe Webkit index (the largest I know) has a size of 26 Mb, which is\nreduced to about 15 MB or less with the v5 format. With 32-bit we can\naddress 4GB, which is about 266 times the Webkit index. Therefore there\nprobably is no use for 64-bit offsets in the years to come.\n"},{"id":"190694","messageId":"CALgYhfMQMdtcNN2a_BwPMkb_aHGr9ivBpWOSEjkqjGiaVzgS_w@mail.gmail.com","threadId":"30413","inReplyTo":"7vd36lf634.fsf@alter.siamese.dyndns.org","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-03T21:38:43Z","receivedAt":"2012-05-03T21:38:43Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On Thu, May 3, 2012 at 8:54 PM, Junio C Hamano wrote:\n> Thomas Gummerer writes:\n>\n>> I have been drafting the Version 5 of the index format over the past\n>> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n>> barrbrain on IRC.\n>\n> Hrm, so if there is anything glaringly wrong below, should I reduce the\n> \"trustable reviewer karma point\" from these people? Or did you forget to\n> say \"but remaining errors are mine\" ;-)?\n\nHeh yes most of the remaining errors are mine ;-) (And I hope nothing is\n*that* wrong ;-) )\n\n>> GIT index format\n>> ================\n>>\n>> = The git index file has the following format\n>>\n>> All binary numbers are in network byte order. Version 5 is described\n>> here.\n>>\n>> - A 16-byte header consisting of\n>>\n>> 4-byte signature:\n>> The signature is { 'D', 'I', 'R', 'C' } (stands for \"dircache\")\n>>\n>> 4-byte version number:\n>> The current supported versions are 2, 3, 4 and 5.\n>>\n>> 32-bit number of directories.\n>\n>> 32-bit number of file entries.\n>\n> I take these two numbers mean \"we have this many directory entries in the\n> index\" and \"we have this many file entries in the index\"; I found it\n> unclear during my first scan.\n\nYes, that's exactly what they mean. I'll write this down more clearly in the\nnext version.\n\n> Have you considered expressing these new \"directories\", \"files\" and\n> associated data as a new (mandatory) extension?\n\nSince they are the main part of the index, I don't consider them\nextensions, unless we say \"everything in the index is a extension\"\n\n>> - Offset to the extensions.\n>>\n>> 32-bit number of extensions.\n>\n> Why is this necessary? It means that the writer needs to enumerate how\n> many extensions it is going to write before starting to write, unless it\n> is willing to seek back and fill this. And it is not like the reader will\n> first allocate an array to hold uniformly sized extension and will be\n> helped to have the number of entries upfront in order to do the\n> allocation.\n>\n> What purpose does this serve?\n\nIt's to determine how many offsets the reader has to read (or to skip\nto get to the first directory offset).\n\n>> 32-bit number offset to the extension. (Possibly none, as many as\n>> indicated in the 4-byte number of extensions)\n>\n> Why is this needed? It appears that there is no field that points at the\n> beginning of array that stores \"directory offsets\", nor \"file offsets\", so\n> I am assuming that you will be scanning the index file to find them. Why\n> can't the extensions be handled exactly the same way?\n\nThe offsets are necessary to quickly skip to the extension data, in case it\nmakes sense without knowing about the index/without reading the whole\nindex. The directories and files are different in the sense that the reader\nneeds to read to the first \"directory offset\" entry in any case, since it needs\nto read the header in any case, then the number of extensions (and\nif it doesn't know about any extensions skipping them), and then there come\nthe directory offsets. Those then have the pointer to the actual directory\ndata, which itself has the pointer to it's files. And since the files don't make\nsense without knowing about the directory, there is no need for offsets for\nthe files.\n\n>> - A number of directory offsets (see below). [1]\n>>\n>> - A number of sorted directories (see below). [2]\n>>\n>> - 32-bit crc32 checksum for the header, extension offsets and directories.\n>\n> What does \"32\" in \"crc32\" stand for ? ;-)\n\n32 bit I guess ;-) It's just standing there to make it clear on first\nsight that there\nis a 32-bit entry, since every other entry starts with the bit/byte count too.\n\n>> - A number of file offsets (see below). [1]\n>>\n>> - A number of file entries (see below).\n>>\n>> - A number of entries for conflicted data/resolved conflicts (see below).\n>>\n>> - Extensions\n>>\n>> Extensions are identified by signature. Optional extensions can\n>> be ignored if GIT does not understand them.\n>>\n>> GIT supports an arbitrary number of extension, but currently none\n>> is implemented. [3]\n>>\n>> 4-byte extension signature. If the first byte is 'A'..'Z' the\n>> extension is optional and can be ignored.\n>>\n>> 32-bit size of the extension\n>>\n>> 32-bit crc32 checksum of the extension signature and size\n>>\n>> Extension data\n>>\n>>\n>> == Directory entry offsets\n>\n> The name \"directory entry offset\" does not seem to appear anywhere before\n> this, so it is unclear what this section of the documentation is trying to\n> describe. Is this the same as \"directory offsets\" above? In other words,\n> \"A number of directory offsets (see below).\" above is an array of something,\n> and this section is trying to describe what that something is?\n\nYes, exactly, it's the directory offsets above. I'll write this down more\nclearly too.\n\n>> 32-bit offset to the directory.\n>\n> I take it is \"offset relative to the beginning of the file in the index\".\n\nYes, that will be written more clearly too.\n\n>> This part is needed for making the directory entries bisectable and\n>> thus allowing a binary search.\n>>\n>> == Directory entry\n>>\n>> Directory entries are sorted in lexicographic order by the name\n>> of their path starting with the root.\n>>\n>> Path names (variable length) relative to top level directory (without the\n>> leading slash). '/' is used as path separator. '.' indicates the root\n>> directory. The special patch components \"..\" and \".git\" (without quotes)\n>> are disallowed. Trailing slash is also disallowed.\n>\n> I understood \"the root\" to mean \"the top level of the directory hierarchy\"\n> (i.e. the directory that corresponds to the top level of the working\n> tree), but it needs to be explained better. Using '.' for root sounds\n> somewhat questionable, though. Why not a string of length 0?\n\nYes, that's right. I thought about '.' for root since *nix environments do it\nthat way too. But the string of length 0 would also work better with the\nlexicographic sorting.\n\n> When an index represents a D/F conflict, some stages may have a directory\n> D while others do not have D (but have a regular file at D). Doesn't\n> directory entry need to have a stage information?\n\nI didn't think about that, I'll include that in the next version.\n\n>> 1 nul byte to terminate the path.\n>>\n>> 32-bit offset to the first file of a directory\n>\n> What does this point at? Does it point into the array of \"file offsets\"\n> or the array of \"file entries\"?\n\nIt points to the \"file offsets\".\n\n>> 32-bit offset to conflicted/resolved data at the end of the index.\n>> 0 if there is no such data. [4]\n>>\n>> 4-byte number of subtrees this tree has\n>\n> Which is an undefined number unless you specify which stage you are\n> talking about.\n\nI'm talking about the number of subtrees, that are in the index. This\nis used for further compressing the index, and not being redundant\nwith path components. E.g: we have a directory A/A then the index\nsaves it as\n\nA...1Subtree...\nA...0Subtrees...\n\n(... is the rest of the data that's stored)\n\n>> 4-byte number of entries in the index that is covered by the tree this\n>> entry represents. (entry_count) (-1 if the entry is invalid)\n>>\n>> 160-bit object name for the object that would result from writing\n>> this span of index as a tree.\n>>\n>> The last 24 bytes are for the cache tree. An entry can be in an\n>> invalidated state which is represented by having -1 in the entry_count\n>> field. If an entry is in invalidated state, the next entry will begin\n>> after the number of subtrees, and the 160-bit object name is dropped.\n>\n> By \"The last 24 bytes\", do you mean the \"4-byte number of entries...\" and\n> \"160-bit object name\"?\n\nYes, exactly.\n\n>> The entries are written out in the top-down, depth-first order. The\n>> first entry represents the root level of the repository, followed by\n>> the first subtree - let's call it A - of the root level, followed by\n>> the first subtree of A, ...\n>>\n>> == File entry offsets\n>>\n>> 32-bit offset to the directory.\n>\n> What directory? The containing directory? What does this point at? Does\n> it point into which array?\n\nThat's actually wrong it should say file entry, as it should below. That's what\nI get from copy and pasting ;-)\n\n>> This part is needed for making the directory entries bisectable and\n>> thus allowing a binary search.\n>>\n>> == File entry\n>>\n>> File entries are sorted in ascending order on the name field, after the\n>> respective offset given by the directory entries.\n>>\n>> File name (variable length). Nul bytes are not allowed in file names and\n>> they have no leading slash. They are 7-bit ASCII encoded.\n>\n> Is this a name relative to its containing directory (i.e. without leading\n> components)? Or is it a full path relative to the top level of the\n> working tree?\n\nThe path is relative to its containing directory, to save space, as in your\nv4 index format.\n\n> I have some UTF-8 encoded files in my repository. Are they\n> now disallowed?\n\nRight I should have taken the old format there, and leave the\nfiles in undefined encoding?\n\n>> 1 nul byte to terminate the filename.\n>>\n>> A 16-bit 'flags' field split into (high to low bits)\n>>\n>> 1-bit assume-valid flag\n>\n> Is this \"assume unchanged\"?\n\nI have taken this from the old index format documentation, which\ndescribes it as assume-valid flag, but I guess it's assume unchanged then.\n\n>> 1-bit conflict flag\n>>\n>> 2-bit stage (during merge)\n>\n> Huh? When stage #0 entry exists for a given path, no other stages for the\n> same path can exist in the index. By definition, that is how a conflicted\n> path is resolved. What is this separate \"conflict flag\" for?\n\nI probably got this wrong, and the conflict flag isn't needed. So if I have a\nstage #1 entry in the index, I'm sure that it's conflicted?\n\n>> 2-bit mode (0 = 1000644 (regular file without execution\n>> permission), 1 = 1000755 (regular file with execution\n>> permission), 2 = 1010000 (symbolic link), 3 = 1110\n>> (gitlink)) [5]\n>\n> Don't penny-pinch bits like this.\n\nHeh ok, I thought this saves 4-bytes per entry so it would be good,\nbut if it's better the other way we'll invest 16-bits for this.\n\n>> 1-bit skip-worktree flag (used by sparse checkout)\n>>\n>> 1-bit intent-to-add flag (used by \"git add -N\")\n>>\n>> 8-bit unused, must be zero [6]\n>>\n>> 32-bit mtime seconds, the last time a file's data changed\n>> this is stat(2) data\n>>\n>> 32-bit mtime nanosecond fractions\n>> this is stat(2) data\n>>\n>> 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n>> ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n>\n> Giving occassional false positive to \"did this change?\" is acceptable, but\n> any false negative is absolutely unacceptable. How does this work with\n> something like \"racy git\" situation (i.e. coming from \"mtime happens to be\n> the same as before\") but due to crc32 collisions?\n>\n> If there is no good answer to the above question, I would have to say that\n> anybody who suggested or passed this through review loses all the\n> accumulated reviewer karma points (if s/he has accumulated any, that is).\n>\n>> 160-bit SHA-1 for the represented object\n>>\n>> 32-bit crc32 checksum for the file entry\n>>\n>> == Conflicted data\n>\n> I do not think the data described in this section should be conflicting.\n> It ought to be data that describe conflicted state. Perhaps you meant\n> \"Conflict data\"?\n\nYes, it's conflict data. It's the data that used to have more entries in the\nin the index, and it has been moved to the far end to avoid lots of rewrites\nof the index, when a conflict is resolved.\n\n>> A conflict is represented in the index as a set of higher stage entries.\n>> These entries are stored at the end of the index. When a conflict is\n>> resolved (e.g. with \"git add path\"). A bit is flipped, to indicate that\n>> the conflict is resolved, but the entries will be kept, so that\n>> conflicts can be recreated (e.g. with \"git checkout -m\", in case users\n>> want to redo a conflict resolution from scratch.\n>>\n>> - NUL-terminated filename of the entry\n>\n> Is this a name relative to its containing directory (i.e. without leading\n> components)? Or a full path relative to the top-level of the working\n> tree?\n\nThis is again relative to it's containing directory. That's what the second\noffsets in the directory entry part is about. (The offset is pointing to the\nfilename)\n\n>> - A 8-bit 'flags' field split into:\n>>\n>> - 1-bit conflicted state (conflicted/resolved) (1 if conflicted)\n>>\n>> - 7-bit unused\n>>\n>> - Three 4-byte octal numbers, entry mode of entries in stage 1 to 3 (a\n>> missing stage is represented by \"0\" in this field);\n>> and\n>>\n>> - At most three 160-bit object names of the entry in stages from 1 to 3\n>> (nothing is written for a missing stage).\n>\n> It is allowed to have more than 1 entries in stage #1 to represent\n> multiple merge-base, so this needs to be rethought.\n\nOk, I'll rethink this. Thought it's this way, because it currently\nworks this way\nin the resolve undo extension.\n\n>> - 32-bit crc32 checksum over one conflicted entry.\n>\n> There is no definition of \"one conflicted entry\"; be consistent and say\n> \"Conflicted data\" as what the section header claims to describe.\n\nOk, I'll change that.\n\n\n>> == Design explanations\n>>\n>> [1] The directory and file offsets are included in the index format\n>> to enable bisectability of the index, for binary searches.Updating\n>> a single entry and partial reading will benefit from this.\n>>\n>> [2] The directories are saved in their own block, to be able to\n>> quickly search for a directory in the index. They include a\n>> offset to the (lexically) first file in the directory.\n>>\n>> [3] The data of the cache-tree extension and the resolve undo\n>> extension is now part of the index itself, but if other extensions\n>> come up in the future, there is no need to change the index, they\n>> can simply be added at the end.\n>>\n>> [4] To avoid rewrites of the whole index when there are conflicts or\n>> conflicts are being resolved, conflicted data will be stored at\n>> the end of the index. To mark the conflict resolved, just a bit\n>> has to be flipped. The data will still be there, if a user wants\n>> to redo the conflict resolution.\n>>\n>> [5] Since only 4 modes are effectively allowed in git but 32-bit are\n>> used to store them, having a two bit flag for the mode is enough\n>> and saves 4 byte per entry.\n>>\n>> [6] The length of the file name was dropped, since each file name is\n>> nul terminated anyway.\n>\n> This is micronit, but I think we do this to save one strlen() for each\n> read of the entry, except for unusually long paths where we fall back to\n> strlen(). A change like this needs to be justified better than simply\n> saying \"because we _could_ compute in a different way by spending extra\n> cycles\".\n"},{"id":"190728","messageId":"4FA3816E.8090005@alum.mit.edu","threadId":"30413","inReplyTo":"87obq5p1t0.fsf@thomas.inf.ethz.ch","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-04T07:12:46Z","receivedAt":"2012-05-04T07:12:46Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/03/2012 08:16 PM, Thomas Rast wrote:\n> Thomas Gummerer writes:\n>\n>> 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n>> ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n> [...]\n>> [7] Since all stat data (except mtime and ctime) is just used for\n>> checking if a file has changed a checksum of the data is enough.\n>> In addition to that Thomas Rast suggested ctime could be ditched\n>> completely (core.trustctime=false) and thus included in the\n>> checksum. This would save 24 bytes per index entry, which would\n>> be about 4 MB on the Webkit index.\n>> (Thanks for the suggestion to Michael Haggerty)\n>\n> This is the part I'm most curious about. Are we missing anything?\n> Michael brought it up on IRC: the stat() results are only used to test\n> whether they are still the same, with the exception of the mtime (which\n> also undergoes raciness checks).\n>\n> As far as I can see, none of st_{ino,dev,uid,gid} are useful for\n> anything. st_size might conceivably be used as a hint for a buffer\n> size, but nobody actually does that. The ctime undergoes stricter\n> checks, but AFAICS it's also all about whether it has changed, and\n> besides that can be turned off. We think all of those fields can be\n> replaced by an arbitrary hash/CRC and only tested for equality. 32 bits\n> should be plenty, probably even if we just xor the values together.\n\nXOR is definitely *not* adequate; for example, changing uid=gid=\"you\" to \nuid=gid=\"me\" would not affect the XOR of the values (assuming, as is \noften the case, that each user has his own uid/gid with the same \nnumerical values).\n\nWhich hash to use depends on some estimate of the likelihood that the \nhashes collide and simultaneously that the other metadata coincide. It \nseems to me that CRC-32 would be adequate. But if not, a longer hash \ncould be used (albeit with less space savings).\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"190750","messageId":"CACsJy8B9p1Z_eW20mZwBLwRnFWHstEdRxmw7GujECpMKByfBEg@mail.gmail.com","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-04T13:20:38Z","receivedAt":"2012-05-04T13:20:38Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 4, 2012 at 12:25 AM, Thomas Gummerer wrote:\n> GIT index format\n> ================\n>\n> = The git index file has the following format\n>\n>  All binary numbers are in network byte order. Version 5 is described\n>  here.\n> ...\n>   - A number of directory offsets (see below). [1]\n>\n>   - A number of sorted directories (see below). [2]\n>\n>   - 32-bit crc32 checksum for the header, extension offsets and directories.\n\nSo we use one checksum for all dirs? I thought we could do checksum\nper dir, so if I'm interested in path/to/here only, I only need to\nverify data of three directories.\n\n> == Directory entry offsets\n>\n>  32-bit offset to the directory.\n>\n>  This part is needed for making the directory entries bisectable and\n>    thus allowing a binary search.\n\nHow is this (I assume) array ordered? The same top-down depth-first\nwith \"Directory entry\" section below? I can see ordering as\ntop-down/breadth-first help bsearch though.\n\n> == Directory entry\n>\n>  Directory entries are sorted in lexicographic order by the name\n>  of their path starting with the root.\n>\n>  Path names (variable length) relative to top level directory (without the\n>    leading slash). '/' is used as path separator. '.' indicates the root\n>    directory. The special patch components \"..\" and \".git\" (without quotes)\n>    are disallowed. Trailing slash is also disallowed.\n>\n>  1 nul byte to terminate the path.\n\nI don't see it mention prefix compression here, nor in \"file entry\"\nsection. Does it use it here? If so I don't think prefix compression\nplays well with bsearch (on path name). In the worst case you may have\nto process up to the first entry in order to get a path name (e.g. a\ndirectory with entries \"a\", \"aa\", \"aaa\", \"aaaa\"...)\n\n>  The entries are written out in the top-down, depth-first order. The\n>    first entry represents the root level of the repository, followed by\n>    the first subtree - let's call it A - of the root level, followed by\n>    the first subtree of A, ...\n\nSo depth-first traversal becomes natural even without the help of\ndirectory offset table above. Nice.\n\n> == File entry\n>\n>  File entries are sorted in ascending order on the name field, after the\n>  respective offset given by the directory entries.\n\nI wonder if we need to keep file entry table separate from directory\nentry. It feels more natural to put the sequence of file entries of a\ndirectory right after the directory entry, might help read-ahead too\nduring traversal. You save 4 bytes (for file entry offset) in each\ndirectory entry. You still have file offset table for random access.\n\n>  File name (variable length). Nul bytes are not allowed in file names and\n>    they have no leading slash. They are 7-bit ASCII encoded.\n\nWhy can't it be 8-bit? I suppose file name is also prefix compressed?\n-- \nDuy\n"},{"id":"190751","messageId":"2A6D903A618147EEBBFEF99234104EE6@PhilipOakley","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2012-05-04T13:25:05Z","receivedAt":"2012-05-04T13:25:05Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Thomas Gummerer\" Sent: Thursday, May 03, 2012 \n6:25 PM\n>I have been drafting the Version 5 of the index format over the past\n> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n> barrbrain on IRC. It will save with prefix compression on the path, and\n> using a crc32 over the stat data, instead of the full data, since it is \n> only\n> used for checking if the file is changed. (Thanks Michael Haggerty for\n> this hint. Unless we are missing something this will save another\n> ~4 MB on the Webkit index.\n>\n>\n>\n> GIT index format\n> ================\n>\n> = The git index file has the following format\n>\nxxx\n>\n> == Directory entry\n>\n> Directory entries are sorted in lexicographic order by the name\n> of their path starting with the root.\n>\n> Path names (variable length) relative to top level directory (without the\n> leading slash). '/' is used as path separator. '.' indicates the root\n> directory. The special patch components \"..\" and \".git\" (without \n> quotes)\n> are disallowed. Trailing slash is also disallowed.\n>\n\nDoes the prohibition of \".git\" prevent the potential for versioning of the \n.git directory itself (e.g. .gitignore the pack & objects themselves)?\n\nIt should be possible for one's current repo status to be tracked and \nsummarised by a single sha1, say as an indepenedent branch, as you would the \ncode itself.\n\n[my use case is in a managed environment where one has plenty of networked \nproject storage, but no real availability of a network server, so anybody \nand his mate could corrupt ones network repo with badly thought through \ntweaks. The lack of a server is the root cause, but that's not something the \nproject can fix, so thinks ... 'version the meta data...']\n\nI can see that the lack of the leading \"/\", and the \"..\" are a policy \nstatement about paths being relative to top level directory, with direct \npath referencing. The typical avoidance of \".git\" should be a note about how \nregular git works, rather than an absolute prohibition.\n\nPhilip \n"},{"id":"190760","messageId":"20120504154424.GA923@tgummerer.unibz.it","threadId":"30413","inReplyTo":"CACsJy8B9p1Z_eW20mZwBLwRnFWHstEdRxmw7GujECpMKByfBEg@mail.gmail.com","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-04T15:44:24Z","receivedAt":"2012-05-04T15:44:24Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/04, Nguyen Thai Ngoc Duy wrote:\n> On Fri, May 4, 2012 at 12:25 AM, Thomas Gummerer wrote:\n> > GIT index format\n> > ================\n> >\n> > = The git index file has the following format\n> >\n> >  All binary numbers are in network byte order. Version 5 is described\n> >  here.\n> > ...\n> >   - A number of directory offsets (see below). [1]\n> >\n> >   - A number of sorted directories (see below). [2]\n> >\n> >   - 32-bit crc32 checksum for the header, extension offsets and directories.\n> \n> So we use one checksum for all dirs? I thought we could do checksum\n> per dir, so if I'm interested in path/to/here only, I only need to\n> verify data of three directories.\n\nGood point. Not sure how they could exactly be implemented, but probably\none checksum for offset + directory data. I'll definitely think about this.\n\n> > == Directory entry offsets\n> >\n> >  32-bit offset to the directory.\n> >\n> >  This part is needed for making the directory entries bisectable and\n> >    thus allowing a binary search.\n> \n> How is this (I assume) array ordered? The same top-down depth-first\n> with \"Directory entry\" section below? I can see ordering as\n> top-down/breadth-first help bsearch though.\n\nTrue, the breadth-first approach might be better, since we are using\nprefix compression for the pathname. It will need some more offsets\n(or calculation, but should still be faster)\n\n> > == Directory entry\n> >\n> >  Directory entries are sorted in lexicographic order by the name\n> >  of their path starting with the root.\n> >\n> >  Path names (variable length) relative to top level directory (without the\n> >    leading slash). '/' is used as path separator. '.' indicates the root\n> >    directory. The special patch components \"..\" and \".git\" (without quotes)\n> >    are disallowed. Trailing slash is also disallowed.\n> >\n> >  1 nul byte to terminate the path.\n> \n> I don't see it mention prefix compression here, nor in \"file entry\"\n> section. Does it use it here? If so I don't think prefix compression\n> plays well with bsearch (on path name). In the worst case you may have\n> to process up to the first entry in order to get a path name (e.g. a\n> directory with entries \"a\", \"aa\", \"aaa\", \"aaaa\"...)\n\nI planned to use prefix compression here, which would benefit especially\nthe reader (we're reading more often then writing). By designing the\noffsets carefully we should still be able to get log(n) (n = number of\ndirectories in the index) search time for a directory.\n\n> >  The entries are written out in the top-down, depth-first order. The\n> >    first entry represents the root level of the repository, followed by\n> >    the first subtree - let's call it A - of the root level, followed by\n> >    the first subtree of A, ...\n> \n> So depth-first traversal becomes natural even without the help of\n> directory offset table above. Nice.\n> \n> > == File entry\n> >\n> >  File entries are sorted in ascending order on the name field, after the\n> >  respective offset given by the directory entries.\n> \n> I wonder if we need to keep file entry table separate from directory\n> entry. It feels more natural to put the sequence of file entries of a\n> directory right after the directory entry, might help read-ahead too\n> during traversal. You save 4 bytes (for file entry offset) in each\n> directory entry. You still have file offset table for random access.\n\nThe reason for this design choice is the fast searching of a directory, \n(for partial reading or changing a single file in the index). Keeping\nthem separate also simplifies the reading of the cache-tree, which will\nbe included in the directory section. Instead of offsets to the first file\nwe'd need offsets to the next directory to enable fast reading of the\ncache-tree.\n\n> >  File name (variable length). Nul bytes are not allowed in file names and\n> >    they have no leading slash. They are 7-bit ASCII encoded.\n> \n> Why can't it be 8-bit? I suppose file name is also prefix compressed?\n\nI changed that, the file name can have UTF8 or ASCII encoding, as it was\nallowed in the old index.\n\n--\nThomas\n"},{"id":"190761","messageId":"7vzk9oaqzc.fsf@alter.siamese.dyndns.org","threadId":"30413","inReplyTo":"2A6D903A618147EEBBFEF99234104EE6@PhilipOakley","subject":"Re: Index format v5","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-04T15:46:47Z","receivedAt":"2012-05-04T15:46:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Philip Oakley\" writes:\n\n> Does the prohibition of \".git\" prevent the potential for versioning of\n> the .git directory itself (e.g. .gitignore the pack & objects\n> themselves)?\n\nIt is a good thing that you are forbidden from adding .git/anything to the\nindex and the trees. The information inside your .git/ repository does\nhave to change from time to time. For example, you may change your e-mail\naddress and update user.email in your .git/config file.\n\nBut the history of them and the history of the evolution of the project\nitself are distinct [*1*]. When you clone git.git, you have no business\nlearning what is in .git/config in my repository. The project should not\nbe able to overwrite what is in your .git/hooks/. These are only a few\nreasons why an attempt to \"git add .git/something\" is always a mistake.\n\nAnd it is irrelevant to this discussion, as the rest of .git does not\nallow putting .git anyway. In that sense, the index \"format\" does not\nhave to enforce it. For that reason, I would suggest dropping the mention\nof \".git\" (but not \"..\") from the format description.\n\n[Footnote]\n\n*1* You could choose to track the contents of .git/ in another repository\nwith creative uses of GIT_DIR/GIT_WORK_TREE/core.worktree and friends.\n"},{"id":"190889","messageId":"CACsJy8Ba3F45-gx90JVxyOscxX=-JKj5Kbjrd53q_NWXw-nPSg@mail.gmail.com","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-06T10:23:58Z","receivedAt":"2012-05-06T10:23:58Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, May 4, 2012 at 12:25 AM, Thomas Gummerer wrote:\n> == Directory entry\n>\n>  Directory entries are sorted in lexicographic order by the name\n>  of their path starting with the root.\n>\n>  Path names (variable length) relative to top level directory (without the\n>    leading slash). '/' is used as path separator. '.' indicates the root\n>    directory. The special patch components \"..\" and \".git\" (without quotes)\n>    are disallowed. Trailing slash is also disallowed.\n>\n>  1 nul byte to terminate the path.\n>\n>  32-bit offset to the first file of a directory\n>\n>  32-bit offset to conflicted/resolved data at the end of the index.\n>    0 if there is no such data. [4]\n\nIf it's non-zero, how do we know how many conflict entries we have?\n\n>  4-byte number of subtrees this tree has\n\nlet's name this nr_subtrees\n\n>  4-byte number of entries in the index that is covered by the tree this\n>    entry represents. (entry_count) (-1 if the entry is invalid)\n\nand this nr_entries.\n\nSo how do we know how many entries (including all dirs, files, staged\nfiles) this directory has? I assume if enry_count != -1, the number\nwould be nr_subtrees + nr_entries (or just nr_entries, depending on\nyour definition). When entry_count == -1, how do we calculate this\nnumber?\n\n>  160-bit object name for the object that would result from writing\n>    this span of index as a tree.\n>\n>  The last 24 bytes are for the cache tree. An entry can be in an\n>    invalidated state which is represented by having -1 in the entry_count\n>    field. If an entry is in invalidated state, the next entry will begin\n>    after the number of subtrees, and the 160-bit object name is dropped.\n>\n>  The entries are written out in the top-down, depth-first order. The\n>    first entry represents the root level of the repository, followed by\n>    the first subtree - let's call it A - of the root level, followed by\n>    the first subtree of A, ...\n\nAssume the command is \"git diff -- path/to/h*\", we don't need full\nindex, just stuff in \"path/to/h*\" from the index. I'm trying to see\nhow to load just those paths from index, not full index.\n\nI assume again that you won't invent a new function and use\ntree_entry_interesting() to do tree pruning while loading index.\nt_e_i() is designed to read tree objects. But I think we can make it\nread on-disk directory/file entries with a few small changes. t_e_i()\nis recursive and fits quite well with depth-first directory layout in\nthe proposed index format.\n\nI have difficulties figuring out how you skip subtrees though. Assume\nwe are at \"path\" and we are not interested in anything there until we\nmeet \"path/to\", how do you skip subtrees \"path/abc\" and \"path/def\"?\nProcessing directory entries sequentially will eventually get us to\n\"path/to\", but that could be a lot of entries if \"path/abc\" is deep. A\nfile offset pointer to the next sibling directory entry might help.\nDoes such a pointer exist but I did not see it, or you have other\nmeans to do this?\n\nAlso the file/dir separation makes it more difficult to match the last\n\"h*\" part, if there are both \"here\" directory and \"howto\" file.\n-- \nDuy\n"},{"id":"190929","messageId":"CABURp0rAjrhVACQEafrZRxtXBAmajpEqfp+EmB7s595dobqHQQ@mail.gmail.com","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2012-05-06T16:49:27Z","receivedAt":"2012-05-06T16:49:27Z","isPatch":false,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"On Thu, May 3, 2012 at 1:25 PM, Thomas Gummerer wrote:\n> I have been drafting the Version 5 of the index format over the past\n> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n> barrbrain on IRC. It will save with prefix compression on the path, and\n> using a crc32 over the stat data, instead of the full data, since it is only\n> used for checking if the file is changed. (Thanks Michael Haggerty for\n> this hint. Unless we are missing something this will save another\n> ~4 MB on the Webkit index.\n\n...\n\n> == Directory entry\n>\n>  Directory entries are sorted in lexicographic order by the name\n>  of their path starting with the root.\n>\n>  Path names (variable length) relative to top level directory (without the\n>    leading slash). '/' is used as path separator. '.' indicates the root\n>    directory. The special patch components \"..\" and \".git\" (without quotes)\n>    are disallowed. Trailing slash is also disallowed.\n\ntypo: The special _path_ components \"..\" and \".git\" ...\n"},{"id":"190996","messageId":"20120507130803.GA6189@tgummerer","threadId":"30413","inReplyTo":"CABURp0rAjrhVACQEafrZRxtXBAmajpEqfp+EmB7s595dobqHQQ@mail.gmail.com","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-07T13:08:03Z","receivedAt":"2012-05-07T13:08:03Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"> > �Path names (variable length) relative to top level directory (without the\n> > � �leading slash). '/' is used as path separator. '.' indicates the root\n> > � �directory. The special patch components \"..\" and \".git\" (without quotes)\n> > � �are disallowed. Trailing slash is also disallowed.\n> \n> typo: The special _path_ components \"..\" and \".git\" ...\n\nThanks, I changed it.\n"},{"id":"190998","messageId":"20120507134427.GB6189@tgummerer","threadId":"30413","inReplyTo":"CACsJy8Ba3F45-gx90JVxyOscxX=-JKj5Kbjrd53q_NWXw-nPSg@mail.gmail.com","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-07T13:44:27Z","receivedAt":"2012-05-07T13:44:27Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\n\n\nOn 05/06, Nguyen Thai Ngoc Duy wrote:\n> On Fri, May 4, 2012 at 12:25 AM, Thomas Gummerer wrote:\n> > == Directory entry\n> >\n> >  Directory entries are sorted in lexicographic order by the name\n> >  of their path starting with the root.\n> >\n> >  Path names (variable length) relative to top level directory (without the\n> >    leading slash). '/' is used as path separator. '.' indicates the root\n> >    directory. The special patch components \"..\" and \".git\" (without quotes)\n> >    are disallowed. Trailing slash is also disallowed.\n> >\n> >  1 nul byte to terminate the path.\n> >\n> >  32-bit offset to the first file of a directory\n> >\n> >  32-bit offset to conflicted/resolved data at the end of the index.\n> >    0 if there is no such data. [4]\n> \n> If it's non-zero, how do we know how many conflict entries we have?\n\nRight, I'll add this to the next version. \n\n(32-bit number of conflicted/resolved data entries at the end of the\n index if the offset is non 0.)\n\n> >  4-byte number of subtrees this tree has\n> \n> let's name this nr_subtrees\n> \n> >  4-byte number of entries in the index that is covered by the tree this\n> >    entry represents. (entry_count) (-1 if the entry is invalid)\n> \n> and this nr_entries.\n> \n> So how do we know how many entries (including all dirs, files, staged\n> files) this directory has? I assume if enry_count != -1, the number\n> would be nr_subtrees + nr_entries (or just nr_entries, depending on\n> your definition). When entry_count == -1, how do we calculate this\n> number?\n\nYou're right. In order to maintain the bisectability we'll have to\nkeep the entry count up to date.\n\n> >  160-bit object name for the object that would result from writing\n> >    this span of index as a tree.\n> >\n> >  The last 24 bytes are for the cache tree. An entry can be in an\n> >    invalidated state which is represented by having -1 in the entry_count\n> >    field. If an entry is in invalidated state, the next entry will begin\n> >    after the number of subtrees, and the 160-bit object name is dropped.\n> >\n> >  The entries are written out in the top-down, depth-first order. The\n> >    first entry represents the root level of the repository, followed by\n> >    the first subtree - let's call it A - of the root level, followed by\n> >    the first subtree of A, ...\n> \n> Assume the command is \"git diff -- path/to/h*\", we don't need full\n> index, just stuff in \"path/to/h*\" from the index. I'm trying to see\n> how to load just those paths from index, not full index.\n> \n> I assume again that you won't invent a new function and use\n> tree_entry_interesting() to do tree pruning while loading index.\n> t_e_i() is designed to read tree objects. But I think we can make it\n> read on-disk directory/file entries with a few small changes. t_e_i()\n> is recursive and fits quite well with depth-first directory layout in\n> the proposed index format.\n> \n> I have difficulties figuring out how you skip subtrees though. Assume\n> we are at \"path\" and we are not interested in anything there until we\n> meet \"path/to\", how do you skip subtrees \"path/abc\" and \"path/def\"?\n> Processing directory entries sequentially will eventually get us to\n> \"path/to\", but that could be a lot of entries if \"path/abc\" is deep. A\n> file offset pointer to the next sibling directory entry might help.\n> Does such a pointer exist but I did not see it, or you have other\n> means to do this?\n\nI have changed the index format slightly, not to use prefix compression\non the directory entries, so that binary search through the index gets\nsimple. Using the directory offsets, we can binary search to the\npath/to. We always have log(n) (n is the number of directories) search\ntime for each path.\n\n> Also the file/dir separation makes it more difficult to match the last\n> \"h*\" part, if there are both \"here\" directory and \"howto\" file.\n\nIt doesn't make it more difficult to find, since we can first just\ncheck if there exists the directory with a binary search (and\npossibly more directories, around it) and then search for the file\nin the superdirectory (can you say that?) with another binary search.\n\n-- \nThomas\n"},{"id":"191004","messageId":"4FA7E703.7040408@alum.mit.edu","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-07T15:15:15Z","receivedAt":"2012-05-07T15:15:15Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/03/2012 07:25 PM, Thomas Gummerer wrote:\n> I have been drafting the Version 5 of the index format over the past\n> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n> barrbrain on IRC. It will save with prefix compression on the path, and\n> using a crc32 over the stat data, instead of the full data, since it is only\n> used for checking if the file is changed. (Thanks Michael Haggerty for\n> this hint. Unless we are missing something this will save another\n> ~4 MB on the Webkit index.\n>\n>\n>\n> GIT index format\n> ================\n > [...]\n\nHere are some comments about the format document, version 55047b3d. \nThey probably overlap with other feedback that you have gotten, but I \ndon't have time to cross-correlate everything. Hope it helps.\n\nOverall\n=======\n\nI find the format definition pretty difficult to read. The following\nsuggestions might make it easier to follow.\n\n* You might want to give each of the elements C-like names; e.g.,\n \"ndir (32 bits): number of directories in the index\". These names\n could be used as unambiguous references from other parts of the\n documentation. The names could also be used in the implementing\n code, to make the correspondence with the format definition easier\n to follow.\n\n* Name things consistently. For example, \"A number of sorted\n directories (see below)\" should be changed to \"A number of directory\n entries (see below), sorted by path name\".\n\n* Putting the above two things together, the description \"A number of\n sorted directories\" might become \"direntries (ndir * directory\n entries): one directory entry for each of the ndir directories in\n the index, sorted by path name\".\n\n* Are all \"offsets\" relative to the start of the index file? If so,\n it would be good to state this explicitly at the start (and maybe\n rename them \"file positions\"?). If not, please be very explicit\n about where each offset is measured from, and whether it is signed\n or unsigned.\n\n* You seem to switch randomly between counting sizes in bits vs bytes.\n Please try to be more consistent. BTW, I think the size of an SHA1\n object name is more commonly described as \"20 bytes\" rather than\n \"160 bits\".\n\n* The details of the extension data blocks are described in the first\n (overview) section, whereas it seems like they should be described\n in their own section following the \"conflict data\" section. But\n wouldn't the presence of extension data blocks prevent the addition\n of conflict data?\n\n* Are there situations (for example during conflicts?) when it is\n allowed to have directory and file entries with the same name?\n\n* Does the index file include directory entries for empty directories?\n What about directories that contain only other directories?\n\nOverview\n========\n\n* Does \"32-bit size of the extension\" include the whole extension data\n block (including header) or only the \"extension data\"?\n\nDirectory entry\n===============\n\n* \"4-byte number of entries in the index that is covered by the tree\n this entry represents.\" What does this include?\n Files/directories/both? Recursive or non-recursive?\n\n* \"160-bit object name for the object that would result from writing\n this span of index as a tree.\" Is this always valid?\n\n* It might be convenient to store directory names with trailing '/'\n characters (except for the top-level directory, which can be stored\n as \"\"). That way (1) it is trivial to concatenate the directory\n name and the filename to produce the file path; (2) directories and\n files can be distinguished by name and therefore intermingled in\n lists; (3) such lists can be sorted using strcmp() without having to\n simulate an invisible '/' character.\n\nFile entry\n==========\n\n* I believe that only the basename is stored, not the whole path. But\n then why is the encoding for '/' specified (there should be no '/'\n characters)?\n\n* Why is the encoding of '.' specified? Is it somehow significant for\n the index file format?\n\n* Are file entries sorted by entire path or only by the basename?\n\nFlat loading\n============\n\n* I found the explanation pretty incomprehensible. Perhaps some\n pseudo-code would make it clearer?\n\n* Since I can't understand the explanation, I'm not sure if this\n comment makes any sense. But when traversing into a subdirectory,\n don't *all* of the remaining files from the parent directory need to\n be tucked away somewhere?\n\n* At an even higher level of abstraction, your directory entry\n contains a count \"number of entries in the index that is covered by\n the tree this entry represents\". If this count is recursive, then\n it seems like it would be enough to know how many entries will come\n from traversing a whole subdirectory tree. So it should be possible\n to skip that many entries in the in-memory array and continue\n reading the file entries for the parent subdirectory. For example,\n suppose our files are [A, B/1, B/2/a, B/2/b, B/3, C]. If I start by\n reading the files in the root directory, then I can fill the index\n array entries\n\n [A, -, -, -, -, C]\n\n because when I see that \"B\" is a directory containing a total of\n four entries, I just leave fours spaces for them in the array and\n continue with the next file, \"C\". Of course I would have to\n remember (e.g., on a queue) that directory \"B\" still needs to be\n processed, and the starting index in the array where its entries\n have to be filled in. Still, this jumping around would be in the\n RAM holding the index array pointers rather than in the file\n positions.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191023","messageId":"4FA81B04.9060402@dewire.com","threadId":"30413","inReplyTo":"CALgYhfMQMdtcNN2a_BwPMkb_aHGr9ivBpWOSEjkqjGiaVzgS_w@mail.gmail.com","subject":"Re: Index format v5","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg@dewire.com","sentAt":"2012-05-07T18:57:08Z","receivedAt":"2012-05-07T18:57:08Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"Thomas Gummerer skrev 2012-05-03 23.38:\n> On Thu, May 3, 2012 at 8:54 PM, Junio C Hamano wrote:\n>> Thomas Gummerer writes:\n>>> 1 nul byte to terminate the filename.\n>>>\n>>> A 16-bit 'flags' field split into (high to low bits)\n>>>\n>>> 1-bit assume-valid flag\n>>\n>> Is this \"assume unchanged\"?\n>\n\n> I have taken this from the old index format documentation, which\n> describes it as assume-valid flag, but I guess it's assume unchanged then.\n\nThe bit for \"assume unchanged\" is called CE_VALID in the code.\n\n-- robin\n"},{"id":"191049","messageId":"4FA84A32.7070607@dewire.com","threadId":"30413","inReplyTo":"4FA3816E.8090005@alum.mit.edu","subject":"Re: Index format v5","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg@dewire.com","sentAt":"2012-05-07T22:18:26Z","receivedAt":"2012-05-07T22:18:26Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"Michael Haggerty skrev 2012-05-04 09.12:\n> On 05/03/2012 08:16 PM, Thomas Rast wrote:\n>> Thomas Gummerer writes:\n>>\n>>> 32-bit crc32 checksum over ctime seconds, ctime nanoseconds,\n>>> ino, file size, dev, uid, gid (All stat(2) data except mtime) [7]\n>> [...]\n>>> [7] Since all stat data (except mtime and ctime) is just used for\n>>> checking if a file has changed a checksum of the data is enough.\n>>> In addition to that Thomas Rast suggested ctime could be ditched\n>>> completely (core.trustctime=false) and thus included in the\n>>> checksum. This would save 24 bytes per index entry, which would\n>>> be about 4 MB on the Webkit index.\n>>> (Thanks for the suggestion to Michael Haggerty)\n>>\n>> This is the part I'm most curious about. Are we missing anything?\n>> Michael brought it up on IRC: the stat() results are only used to test\n>> whether they are still the same, with the exception of the mtime (which\n>> also undergoes raciness checks).\n>>\n>> As far as I can see, none of st_{ino,dev,uid,gid} are useful for\n>> anything. st_size might conceivably be used as a hint for a buffer\n>> size, but nobody actually does that. The ctime undergoes stricter\n>> checks, but AFAICS it's also all about whether it has changed, and\n>> besides that can be turned off. We think all of those fields can be\n>> replaced by an arbitrary hash/CRC and only tested for equality. 32 bits\n>> should be plenty, probably even if we just xor the values together.\n>\n> XOR is definitely *not* adequate; for example, changing uid=gid=\"you\" to uid=gid=\"me\"\n > would not affect the XOR of the values (assuming, as is often the case, that each user\n> has his own uid/gid with the same numerical values).\n\nIf you change uid/gid, that has no relevance for the content that git tracks. If the CRC\nis equal you have to check the content. Ideally a change that does not change the content\nshould not change the CRC either, so there is really no absolute need to see that change.\n\nI assume the idea is that if you do \"tar xvf\" or something like that, then changes in file,\nmtime etc could be picked up by looking at these attributes, but it seems that those that\nmess with mtime such that it goes back in time are out of luck with git anyway.\n\n> Which hash to use depends on some estimate of the likelihood that the hashes collide and\n > simultaneously that the other metadata coincide. It seems to me that CRC-32 would\n> be adequate. But if not, a longer hash could be used (albeit with less space savings).\n>\n> Michael\n>\n\nJGit simply ignores ctime, ino, dev, uid and gid. The real reason is of course that\nstandard Java does not have an API for these extra attributes. On the the other hand\nnobody is going to fix this bug. The reason is that if you follow the rule that mtime\nmust always change to \"now\" if content change, then all changes will be found simply\nby looking at mtime or performing a content check for the racy case. Those that mess\nwith mtime tend to be unhappy anyway.\n\nThen there is the issue of how often we can detect changes without checking content. Ino\nusually changes, but when it changes mtime usually does too, so how often does it speed\nup.\n\nHas anyone instrumented git to see how much the different attributes actually\ncontribute to performance and accuracy?\n\nI'd like to extend the size field to 64 bits. We rarely need the extra bits, but we\ncannot differ between 3 bytes and 4294967299 bytes so avoiding the very expensive\ncontent check there would be welcome, even it it's a rare event. I haven't thought\ntoo much about this though. I just felt uncomfortable when looking at the code and\nknowing that performing a content check of a 4 GB file could take a minute or two.\n\n-- robin\n"},{"id":"191095","messageId":"20120508141137.GA3937@tgummerer.surfnet.iacbox","threadId":"30413","inReplyTo":"4FA7E703.7040408@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-08T14:11:37Z","receivedAt":"2012-05-08T14:11:37Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/07, Michael Haggerty wrote:\n> Here are some comments about the format document, version 55047b3d.\n> They probably overlap with other feedback that you have gotten, but\n> I don't have time to cross-correlate everything. Hope it helps.\n\nThanks for the feedback!\n\nFor those who may not know yet, I've created a wiki on github, since\nthis file is going through a lot of revisions, it may not be a good\nidea to post every revision on the mailing list.\nhttps://github.com/tgummerer/git/wiki/Index-format-v5\n\n> Overall\n> =======\n> \n> I find the format definition pretty difficult to read. The following\n> suggestions might make it easier to follow.\n\nThanks, I've incorporated your feedback. I hope it's easier readable now.\n\n> [...] \n> * You seem to switch randomly between counting sizes in bits vs bytes.\n> Please try to be more consistent. BTW, I think the size of an SHA1\n> object name is more commonly described as \"20 bytes\" rather than\n> \"160 bits\".\n\nAll sizes are now in bits. I have taken the 160 bits for the SHA1 from\nthe old index documentation in Documentation/technical. I chose to\nleave it as 160bits for now, as all the other sizes were changed to\nbits too.\n\n> * The details of the extension data blocks are described in the first\n> (overview) section, whereas it seems like they should be described\n> in their own section following the \"conflict data\" section. But\n> wouldn't the presence of extension data blocks prevent the addition\n> of conflict data?\n\nOnly the details that should be there for every extension are described\nin the overview (the header of the extension), to make sure every\nextension has the same header format, and thus a reader which doesn't\nunderstand a specific extension still can read its header and know \nwhat's going on.\n\nThey won't prevent the addition of conflicted data, since when a\nconflict is created, other files were probably added and the index has\nto be rewritten anyway. Once the conflict is resolved however only a\nbit has to be flipped, so there is no rewrite necessary.\n\n> * Are there situations (for example during conflicts?) when it is\n> allowed to have directory and file entries with the same name?\n\nYes, that's why I have added the stage data to the directory.\n\n> * Does the index file include directory entries for empty directories?\n> What about directories that contain only other directories?\n\nIn theory the index is able to include empty directories. I'm however\nnot sure if this should be implemented. I'd be happy to get more\nfeedback there.\n\n> Overview\n> ========\n> \n> * Does \"32-bit size of the extension\" include the whole extension data\n> block (including header) or only the \"extension data\"?\n\nIt includes only the extension data. It's clarified in the documentation\nnow.\n\n> Directory entry\n> ===============\n> \n> * \"4-byte number of entries in the index that is covered by the tree\n> this entry represents.\" What does this include?\n> Files/directories/both? Recursive or non-recursive?\n\nThis is from the cache-tree. I'm not sure but I think it includes both\nfiles and directories, recursively.\n\n> * \"160-bit object name for the object that would result from writing\n> this span of index as a tree.\" Is this always valid?\n\nNo, this is only valid if the entry count is not -1. It's clarified\nnow.\n\n> * It might be convenient to store directory names with trailing '/'\n> characters (except for the top-level directory, which can be stored\n> as \"\"). That way (1) it is trivial to concatenate the directory\n> name and the filename to produce the file path; (2) directories and\n> files can be distinguished by name and therefore intermingled in\n> lists; (3) such lists can be sorted using strcmp() without having to\n> simulate an invisible '/' character.\n\nGood point. Changed this in the documentation.\n\n> File entry\n> ==========\n> \n> * I believe that only the basename is stored, not the whole path. But\n> then why is the encoding for '/' specified (there should be no '/'\n> characters)?\n>\n> * Why is the encoding of '.' specified? Is it somehow significant for\n> the index file format?\n\nYes, you are right, only the basename is stored. '.' and '/' don't need\na specific encoding, it's removed from the documentation.\n\n> * Are file entries sorted by entire path or only by the basename?\n\nThey are sorted by the basename, in the respective block of their\ndirectories.\nExample: paths: a/a a/z b/b\nFile entries in the index:\na ...\nz ...\nb ...\n\n> Flat loading\n> ============\n> \n> * I found the explanation pretty incomprehensible. Perhaps some\n> pseudo-code would make it clearer?\n> \n> * Since I can't understand the explanation, I'm not sure if this\n> comment makes any sense. But when traversing into a subdirectory,\n> don't *all* of the remaining files from the parent directory need to\n> be tucked away somewhere?\n> \n> * At an even higher level of abstraction, your directory entry\n> contains a count \"number of entries in the index that is covered by\n> the tree this entry represents\". If this count is recursive, then\n> it seems like it would be enough to know how many entries will come\n> from traversing a whole subdirectory tree. So it should be possible\n> to skip that many entries in the in-memory array and continue\n> reading the file entries for the parent subdirectory. For example,\n> suppose our files are [A, B/1, B/2/a, B/2/b, B/3, C]. If I start by\n> reading the files in the root directory, then I can fill the index\n> array entries\n> \n> [A, -, -, -, -, C]\n> \n> because when I see that \"B\" is a directory containing a total of\n> four entries, I just leave fours spaces for them in the array and\n> continue with the next file, \"C\". Of course I would have to\n> remember (e.g., on a queue) that directory \"B\" still needs to be\n> processed, and the starting index in the array where its entries\n> have to be filled in. Still, this jumping around would be in the\n> RAM holding the index array pointers rather than in the file\n> positions.\n\nThe entry_count in the index is only valid, if the cache-tree is valid,\nwhich is not always the case. Therefore it's impossible to rely on that\nfor the reading. I have changed the flat loading in the documentation,\nhope it's more understandable now.\n\n--\nThomas\n"},{"id":"191096","messageId":"CACsJy8CUC8AXYvDEH75NGC_r3HwLoaiq0qxn2EAC0Aq4VXVMag@mail.gmail.com","threadId":"30413","inReplyTo":"20120508141137.GA3937@tgummerer.surfnet.iacbox","subject":"Re: Index format v5","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-08T14:25:50Z","receivedAt":"2012-05-08T14:25:50Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, May 8, 2012 at 9:11 PM, Thomas Gummerer wrote:\n>> * \"160-bit object name for the object that would result from writing\n>>   this span of index as a tree.\"  Is this always valid?\n>\n> No, this is only valid if the entry count is not -1. It's clarified\n> now.\n\n..and..\n\n> The entry_count in the index is only valid, if the cache-tree is valid,\n> which is not always the case.\n\nI think your trees are the cache-trees already. For invalid\ncache-trees, you can just use all-zero sha-1 as the indicator. Then\nentry_count can go away.\n-- \nDuy\n"},{"id":"191097","messageId":"CACsJy8DmhcFHOOToEWLoHNRJtXHe8EOnKfOn4+kOMBaW=tyWBw@mail.gmail.com","threadId":"30413","inReplyTo":"CACsJy8CUC8AXYvDEH75NGC_r3HwLoaiq0qxn2EAC0Aq4VXVMag@mail.gmail.com","subject":"Re: Index format v5","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-08T14:34:30Z","receivedAt":"2012-05-08T14:34:30Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Sorry I replied too fast.\n\nOn Tue, May 8, 2012 at 9:25 PM, Nguyen Thai Ngoc Duy wrote:\n> On Tue, May 8, 2012 at 9:11 PM, Thomas Gummerer wrote:\n>>> * \"160-bit object name for the object that would result from writing\n>>>   this span of index as a tree.\"  Is this always valid?\n>>\n>> No, this is only valid if the entry count is not -1. It's clarified\n>> now.\n>\n> ..and..\n>\n>> The entry_count in the index is only valid, if the cache-tree is valid,\n>> which is not always the case.\n>\n> I think your trees are the cache-trees already. For invalid\n> cache-trees, you can just use all-zero sha-1 as the indicator. Then\n> entry_count can go away.\n\nFurthermore, in directory entry format:\n\n The last 24 bytes (4-byte number of entries + 160-bit object name) are\n for the cache tree. An entry can be in an invalidated state which is\n represented by having -1 in the entry_count field. If an entry is in\n invalidated state, the next entry will begin after the number of\n subtrees, and the 160-bit object name is dropped.\n\nDropping objname out of invalid (cache-)trees is a bad idea. When you\ngenerate tree objects (aka cache_tree_update), you'll need objname\nfield again, which means structure change and directory entry rewrite.\nIf objname is always there, you can just overwrite objname with new\nvalue. Though this may bring race condition issue back to directory\nentries. The same approach on file entries might be reused.\n-- \nDuy\n"},{"id":"191187","messageId":"4FAA2CAF.3040408@alum.mit.edu","threadId":"30413","inReplyTo":"20120508141137.GA3937@tgummerer.surfnet.iacbox","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-09T08:37:03Z","receivedAt":"2012-05-09T08:37:03Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/08/2012 04:11 PM, Thomas Gummerer wrote:\n>> * The details of the extension data blocks are described in the first\n>> (overview) section, whereas it seems like they should be described\n>> in their own section following the \"conflict data\" section. But\n>> wouldn't the presence of extension data blocks prevent the addition\n>> of conflict data?\n>\n> Only the details that should be there for every extension are described\n> in the overview (the header of the extension), to make sure every\n> extension has the same header format, and thus a reader which doesn't\n> understand a specific extension still can read its header and know\n> what's going on.\n>\n> They won't prevent the addition of conflicted data, since when a\n> conflict is created, other files were probably added and the index has\n> to be rewritten anyway. Once the conflict is resolved however only a\n> bit has to be flipped, so there is no rewrite necessary.\n\nIn other words, the presence of extensions *does indeed* prevent the \naddition of conflict data, but you don't think that it is a problem.\n\nMoving the conflict data to after the extensions, on the other hand, \nwould mean that conflict data can sometimes be added without a rewrite. \n I cannot judge whether this would be useful.\n\nHandling conflict data *as* an extension would allow the conflict data \nto be added at any time without rewriting. I cannot judge whether this \nwould be useful.\n\n>> * Does the index file include directory entries for empty directories?\n>> What about directories that contain only other directories?\n>\n> In theory the index is able to include empty directories. I'm however\n> not sure if this should be implemented. I'd be happy to get more\n> feedback there.\n\nCurrently git does not keep track of empty directories. Even though \nthere have been proposals to fix this, it is far beyond the scope of \nyour project to implement the handling of empty directories. The \nquestion is whether your format definition *forbids* the presence of \nempty directories in the index file (in the interest of definiteness, \nand it might make the reader implementation a little bit simpler, but it \nimposes a constraint on the writer). Obviously empty directories, even \nif present, mustn't have an effect on the SHA1 of the trees containing them.\n\n>> Directory entry\n>> ===============\n>>\n>> * \"4-byte number of entries in the index that is covered by the tree\n>> this entry represents.\" What does this include?\n>> Files/directories/both? Recursive or non-recursive?\n>\n> This is from the cache-tree. I'm not sure but I think it includes both\n> files and directories, recursively.\n\nPlease figure this out for the final spec.\n\n>> File entry\n>> ==========\n>> [...]\n>\n>> * Are file entries sorted by entire path or only by the basename?\n>\n> They are sorted by the basename, in the respective block of their\n> directories.\n> Example: paths: a/a a/z b/b\n> File entries in the index:\n> a ...\n> z ...\n> b ...\n\nOK, so in other words, the file entries of all files in a directory (not \nincluding files in subdirectories) are stored contiguously, sorted by \nbasename. (The thing that wasn't immediately clear is whether files \nfrom subdirectories are intermingled with those of the parent directory.)\n\n>> Flat loading\n>> ============\n>>\n>> * I found the explanation pretty incomprehensible. Perhaps some\n>> pseudo-code would make it clearer?\n>> [...]\n> [...] I have changed the flat loading in the documentation,\n> hope it's more understandable now.\n\nMaybe it's just be, but I still don't think it is very clear. Here is \nversion fbf8add1b026:\n\n> == Flat loading\n>\n> Since internally git expects and works with lexicografic ordering,\n> a simple linear scan throught the subdirectories doesn't give\n> the right internal sorting. To achieve the right internal sorting\n> the loading will be done in the following way:\n>\n> 1. Start with the root directory, and read also the name of the\n> first subdirectory (=next directory in the list).\n>\n> 1a. Use the next directory (the one against which the filenames\n> were checked previously), and read the next directory name,\n> to check the files against.\n>\n> 2. Check the stack if the element at the top is < then the current\n> directoryname.\n>\n> If it's < then current directory name, add files from the stack\n> to the entry list, until the file name is > then the\n> directory name.\n>\n> 2. While filename < directoryname add the filenames to the entry\n> list\n>\n> 3. Add the rest of the files to a stack.\n>\n> 4. Continue with 1a, if there are more directories left.\n>\n> 5. Add the rest of the files from the stack to the end of the\n> entry list.\n\nAside from the fact that there are two number (2)s,\n\n* What does \"Use the next directory (the one against which the filenames \nwere checked previously)\" mean? What does it mean to \"use a directory\"? \n Does it mean to recurse into the directory? Is the stack preserved \npassed down to the recursive function calls, or does each level of the \nrecursion have its own stack? What does \"against which the filenames \nwere checked previously\" mean (there are no filenames mentioned in the \nearlier steps)?\n\n* You talk about a stack, and \"Add the rest of the files to a stack\". \nBut when you retrieve entries from a stack, they come out in reverse \norder. So are you imagining that each element of the stack is an array \nof file entries? Or do you push the files onto the stack in reverse \norder? Or do you really mean a queue rather than a stack?\n\n* Are the file entries read before they are put on the stack, or does \nthe stack just remember where to read them from when their turn comes?\n\n* \"Continue with 1a, if there are more directories left\": I assume you \nmean subdirectories of the current directory, but maybe you are talking \nabout all directories?\n\nThere is a reason that I asked for pseudocode, namely because it forces \nyou to be more precise in your description. I can certainly imagine \nseveral workable algorithms for reading the index file, and the \ndifferent algorithms have different tradeoffs particularly regarding the \namount of temporary space needed and locality of reference in the index \nfile (which, I understand, will be mmapped when practical but it is not \npractical on all platforms). Once you express the algorithm in \npseudocode it is possible to be sure which variant you have chosen and \nconsider whether it is really workable.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191271","messageId":"20120510065303.GA98491@tgummerer","threadId":"30413","inReplyTo":"CACsJy8DmhcFHOOToEWLoHNRJtXHe8EOnKfOn4+kOMBaW=tyWBw@mail.gmail.com","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-10T06:53:03Z","receivedAt":"2012-05-10T06:53:03Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/08, Nguyen Thai Ngoc Duy wrote:\n> Sorry I replied too fast.\n> \n> On Tue, May 8, 2012 at 9:25 PM, Nguyen Thai Ngoc Duy wrote:\n> > On Tue, May 8, 2012 at 9:11 PM, Thomas Gummerer wrote:\n> >>> * \"160-bit object name for the object that would result from writing\n> >>>   this span of index as a tree.\"  Is this always valid?\n> >>\n> >> No, this is only valid if the entry count is not -1. It's clarified\n> >> now.\n> >\n> > ..and..\n> >\n> >> The entry_count in the index is only valid, if the cache-tree is valid,\n> >> which is not always the case.\n> >\n> > I think your trees are the cache-trees already. For invalid\n> > cache-trees, you can just use all-zero sha-1 as the indicator. Then\n> > entry_count can go away.\n\nHow is it a cache-tree already? The subtree is covered, but the \nentry_count is calculated recursively, while nfiles only keeps track of\nthe files directly in the directory, which is used for bisectability.\n\n> Furthermore, in directory entry format:\n> \n> The last 24 bytes (4-byte number of entries + 160-bit object name) are\n> for the cache tree. An entry can be in an invalidated state which is\n> represented by having -1 in the entry_count field. If an entry is in\n> invalidated state, the next entry will begin after the number of\n> subtrees, and the 160-bit object name is dropped.\n> \n> Dropping objname out of invalid (cache-)trees is a bad idea. When you\n> generate tree objects (aka cache_tree_update), you'll need objname\n> field again, which means structure change and directory entry rewrite.\n> If objname is always there, you can just overwrite objname with new\n> value. Though this may bring race condition issue back to directory\n> entries. The same approach on file entries might be reused.\n\nYes you're right, at least the field for the object name (even if 0)\nshould always be there.\n"},{"id":"191277","messageId":"CACsJy8Dx9jrC+8yC6eSsYbg2Yu6Xk+gkc-9Xe-iAy6+Uv_EoyA@mail.gmail.com","threadId":"30413","inReplyTo":"20120510065303.GA98491@tgummerer","subject":"Re: Index format v5","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-10T11:06:13Z","receivedAt":"2012-05-10T11:06:13Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, May 10, 2012 at 1:53 PM, Thomas Gummerer wrote:\n>\n>\n> On 05/08, Nguyen Thai Ngoc Duy wrote:\n>> Sorry I replied too fast.\n>>\n>> On Tue, May 8, 2012 at 9:25 PM, Nguyen Thai Ngoc Duy wrote:\n>> > On Tue, May 8, 2012 at 9:11 PM, Thomas Gummerer wrote:\n>> >>> * \"160-bit object name for the object that would result from writing\n>> >>>   this span of index as a tree.\"  Is this always valid?\n>> >>\n>> >> No, this is only valid if the entry count is not -1. It's clarified\n>> >> now.\n>> >\n>> > ..and..\n>> >\n>> >> The entry_count in the index is only valid, if the cache-tree is valid,\n>> >> which is not always the case.\n>> >\n>> > I think your trees are the cache-trees already. For invalid\n>> > cache-trees, you can just use all-zero sha-1 as the indicator. Then\n>> > entry_count can go away.\n>\n> How is it a cache-tree already? The subtree is covered, but the\n> entry_count is calculated recursively, while nfiles only keeps track of\n> the files directly in the directory, which is used for bisectability.\n\nCache-tree maintains the information that what part of the index\nalready has corresponding tree objects (and what sha-1). If a tree is\nchanged, the tree all the way up must be invalidated (i.e. throw out\nthe old sha-1 of trees). You have trees and objname for each tree.\nInvalidating a tree is simply erasing objname. Before performing a\ncommit, we just need to traverse the trees from leaves up, generate\ntree objects for trees that do not have valid objname yet.\n-- \nDuy\n"},{"id":"191280","messageId":"20120510121911.GB98491@tgummerer","threadId":"30413","inReplyTo":"4FAA2CAF.3040408@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-10T12:19:11Z","receivedAt":"2012-05-10T12:19:11Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 05/09, Michael Haggerty wrote:\n> On 05/08/2012 04:11 PM, Thomas Gummerer wrote:\n> >>* The details of the extension data blocks are described in the first\n> >> (overview) section, whereas it seems like they should be described\n> >> in their own section following the \"conflict data\" section. But\n> >> wouldn't the presence of extension data blocks prevent the addition\n> >> of conflict data?\n> >\n> >Only the details that should be there for every extension are described\n> >in the overview (the header of the extension), to make sure every\n> >extension has the same header format, and thus a reader which doesn't\n> >understand a specific extension still can read its header and know\n> >what's going on.\n> >\n> >They won't prevent the addition of conflicted data, since when a\n> >conflict is created, other files were probably added and the index has\n> >to be rewritten anyway. Once the conflict is resolved however only a\n> >bit has to be flipped, so there is no rewrite necessary.\n> \n> In other words, the presence of extensions *does indeed* prevent the\n> addition of conflict data, but you don't think that it is a problem.\n\nExactly.\n\n> Moving the conflict data to after the extensions, on the other hand,\n> would mean that conflict data can sometimes be added without a\n> rewrite. I cannot judge whether this would be useful.\n>\n> Handling conflict data *as* an extension would allow the conflict\n> data to be added at any time without rewriting. I cannot judge\n> whether this would be useful.\n\nSince there are offsets in the directory data to the conflicted data\nI don't think it's good to call this data extension data. It may\nhowever be beneficial to have the conflict data after the extension.\nI'll investigate this.\n\n> >>* Does the index file include directory entries for empty directories?\n> >> What about directories that contain only other directories?\n> >\n> >In theory the index is able to include empty directories. I'm however\n> >not sure if this should be implemented. I'd be happy to get more\n> >feedback there.\n> \n> Currently git does not keep track of empty directories. Even though\n> there have been proposals to fix this, it is far beyond the scope of\n> your project to implement the handling of empty directories. The\n> question is whether your format definition *forbids* the presence of\n> empty directories in the index file (in the interest of\n> definiteness, and it might make the reader implementation a little\n> bit simpler, but it imposes a constraint on the writer). Obviously\n> empty directories, even if present, mustn't have an effect on the\n> SHA1 of the trees containing them.\n\nNo, the index format doesn't forbid the presence of empty directories.\nEmpty directories will have a fileoffset of 0, and the reader will\njust ignore them as long as there is no empty directory tracking.\n\n> >>Directory entry\n> >>===============\n> >>\n> >>* \"4-byte number of entries in the index that is covered by the tree\n> >> this entry represents.\" What does this include?\n> >> Files/directories/both? Recursive or non-recursive?\n> >\n> >This is from the cache-tree. I'm not sure but I think it includes both\n> >files and directories, recursively.\n> \n> Please figure this out for the final spec.\n\nIt includes only files, in a recursive manner. I've written this down\nin the spec.\n\n> >>File entry\n> >>==========\n> >>[...]\n> >\n> >>* Are file entries sorted by entire path or only by the basename?\n> >\n> >They are sorted by the basename, in the respective block of their\n> >directories.\n> >Example: paths: a/a a/z b/b\n> >File entries in the index:\n> >a ...\n> >z ...\n> >b ...\n> \n> OK, so in other words, the file entries of all files in a directory\n> (not including files in subdirectories) are stored contiguously,\n> sorted by basename. (The thing that wasn't immediately clear is\n> whether files from subdirectories are intermingled with those of the\n> parent directory.)\n\nYes, exactly.\n\n> >>Flat loading\n> >>============\n> >>\n> >>* I found the explanation pretty incomprehensible. Perhaps some\n> >> pseudo-code would make it clearer?\n> >>[...]\n> >[...] I have changed the flat loading in the documentation,\n> >hope it's more understandable now.\n> \n> Maybe it's just be, but I still don't think it is very clear. Here\n> is version fbf8add1b026:\n> \n> >== Flat loading\n> >\n> >Since internally git expects and works with lexicografic ordering,\n> >a simple linear scan throught the subdirectories doesn't give\n> >the right internal sorting. To achieve the right internal sorting\n> >the loading will be done in the following way:\n> >\n> >1. Start with the root directory, and read also the name of the\n> > first subdirectory (=next directory in the list).\n> >\n> >1a. Use the next directory (the one against which the filenames\n> > were checked previously), and read the next directory name,\n> > to check the files against.\n> >\n> >2. Check the stack if the element at the top is < then the current\n> > directoryname.\n> >\n> > If it's < then current directory name, add files from the stack\n> > to the entry list, until the file name is > then the\n> > directory name.\n> >\n> >2. While filename < directoryname add the filenames to the entry\n> > list\n> >\n> >3. Add the rest of the files to a stack.\n> >\n> >4. Continue with 1a, if there are more directories left.\n> >\n> >5. Add the rest of the files from the stack to the end of the\n> > entry list.\n> \n> [..] \n> There is a reason that I asked for pseudocode, namely because it\n> forces you to be more precise in your description. I can certainly\n> imagine several workable algorithms for reading the index file, and\n> the different algorithms have different tradeoffs particularly\n> regarding the amount of temporary space needed and locality of\n> reference in the index file (which, I understand, will be mmapped\n> when practical but it is not practical on all platforms). Once you\n> express the algorithm in pseudocode it is possible to be sure which\n> variant you have chosen and consider whether it is really workable.\n\nOk, here is the variant in pseudo code. I hope it's understandable\nthis way. It needs some temporary space, but never more then the\nactual entries will need in the end anyway.\n\n== Flat loading\n\nSince internally git expects and works with lexicografic ordering,\na simple linear scan throught the subdirectories doesn't give\nthe right internal sorting. To achieve the right internal sorting\nthe loading will be done in the following way:\n\nThe data structure is a stack of queues, to allow continous reading\nof the file.\n\ns -> queue1\nt -> queue2\na -> queue3\nc -> queue4\nk -> queue5\n\ndirs = read_all_directories\n\nforeach dir in dirs do\n file = read_next_file\n\n while element_on_top_of_stack.first_element < nextdir\n indexentries.append(dequeue(element_on_top_of_stack))\n if element_on_top_of_stack == emtpy:\n remove_element_on_top_of_stack\n\n if file[filename] < nextdir\n indexentries.append(file)\n else\n queue.add(file)\n foreach f in rest_of_files_in_directory:\n queue.add(f)\n stack.push(queue)\n\nforeach queue in stack:\n foreach entry in queue:\n indexentry.append(entry)\n"},{"id":"191334","messageId":"4FAC0633.90809@alum.mit.edu","threadId":"30413","inReplyTo":"20120510121911.GB98491@tgummerer","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-10T18:17:23Z","receivedAt":"2012-05-10T18:17:23Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/10/2012 02:19 PM, Thomas Gummerer wrote:\n> == Flat loading\n>\n> Since internally git expects and works with lexicografic ordering,\n> a simple linear scan throught the subdirectories doesn't give\n> the right internal sorting. To achieve the right internal sorting\n> the loading will be done in the following way:\n>\n> The data structure is a stack of queues, to allow continous reading\n> of the file.\n>\n> s -> queue1\n> t -> queue2\n> a -> queue3\n> c -> queue4\n> k -> queue5\n>\n> dirs = read_all_directories\n>\n> foreach dir in dirs do\n> file = read_next_file\n>\n> while element_on_top_of_stack.first_element< nextdir\n> indexentries.append(dequeue(element_on_top_of_stack))\n> if element_on_top_of_stack == emtpy:\n> remove_element_on_top_of_stack\n>\n> if file[filename]< nextdir\n> indexentries.append(file)\n> else\n> queue.add(file)\n> foreach f in rest_of_files_in_directory:\n> queue.add(f)\n> stack.push(queue)\n>\n> foreach queue in stack:\n> foreach entry in queue:\n> indexentry.append(entry)\n\n1. It seems to me that the first time that a file with a filename before \nnextdir is encountered, the reading of the directory containing the file \nwill be terminated. This would, for example, be the case for any \ndirectory that contains multiple files but no subdirectories.\n\n2. There is still a lot that is unnecessarily obscure. For example, I \nsuppose (but you don't say) that \"rest_of_files_in_directory\" means to \nread the files at that moment. It would be more explicit (and no more \nverbose) to write\n\n while (f = read_next_file()) != NULL:\n queue.add(f)\n\n3. You don't cover corner cases, like when read_next_file() is called \nbut there are no files left in the directory, or when there is no \nnextdir (which itself is not defined). OK, this pseudocode is only \nmeant to be illustrative, so I guess we can wait until your real \nimplementation to see such details. On the other hand, you probably \nwant to get all the details straight in pseudocode or Python before you \nstart translating it into C.\n\n4. I think the algorithm would be easier to understand and implement if \nit were written recursively. The call stack would replace your explicit \nstack (but you would still need one queue per directory level). A key \nobservation is that when \"nextdir\" precedes the next file, then all of \nthe files in subdirectories of nextdir do as well. Thus an obvious \nrecursion would be to call a function like \nread_all_files_under_dir(indexentries, dirs, dirindex) at this point, \nwhich would consume all of the directories that are subdirectories of \ndirs[dirindex] (i.e., all directories whose names have the string \ndirs[dirindex] as a prefix). Using this method would mean that there is \nno need to compare each file under dirs[dirindex] against the next file \nin the outer directory.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191401","messageId":"20120511171230.GA2107@tgummerer","threadId":"30413","inReplyTo":"4FAC0633.90809@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-11T17:12:30Z","receivedAt":"2012-05-11T17:12:30Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 05/10, Michael Haggerty wrote:\n> On 05/10/2012 02:19 PM, Thomas Gummerer wrote:\n> >== Flat loading\n> >\n> >Since internally git expects and works with lexicografic ordering,\n> >a simple linear scan throught the subdirectories doesn't give\n> >the right internal sorting. To achieve the right internal sorting\n> >the loading will be done in the following way:\n> >\n> >The data structure is a stack of queues, to allow continous reading\n> >of the file.\n> >\n> >s -> queue1\n> >t -> queue2\n> >a -> queue3\n> >c -> queue4\n> >k -> queue5\n> >\n> >dirs = read_all_directories\n> >\n> >foreach dir in dirs do\n> > file = read_next_file\n> >\n> > while element_on_top_of_stack.first_element< nextdir\n> > indexentries.append(dequeue(element_on_top_of_stack))\n> > if element_on_top_of_stack == emtpy:\n> > remove_element_on_top_of_stack\n> >\n> > if file[filename]< nextdir\n> > indexentries.append(file)\n> > else\n> > queue.add(file)\n> > foreach f in rest_of_files_in_directory:\n> > queue.add(f)\n> > stack.push(queue)\n> >\n> >foreach queue in stack:\n> > foreach entry in queue:\n> > indexentry.append(entry)\n> \n> 1. It seems to me that the first time that a file with a filename\n> before nextdir is encountered, the reading of the directory\n> containing the file will be terminated. This would, for example, be\n> the case for any directory that contains multiple files but no\n> subdirectories.\n> \n> 2. There is still a lot that is unnecessarily obscure. For example,\n> I suppose (but you don't say) that \"rest_of_files_in_directory\"\n> means to read the files at that moment. It would be more explicit\n> (and no more verbose) to write\n> \n> while (f = read_next_file()) != NULL:\n> queue.add(f)\n> \n> 3. You don't cover corner cases, like when read_next_file() is\n> called but there are no files left in the directory, or when there\n> is no nextdir (which itself is not defined). OK, this pseudocode is\n> only meant to be illustrative, so I guess we can wait until your\n> real implementation to see such details. On the other hand, you\n> probably want to get all the details straight in pseudocode or\n> Python before you start translating it into C.\n> \n> 4. I think the algorithm would be easier to understand and implement\n> if it were written recursively. The call stack would replace your\n> explicit stack (but you would still need one queue per directory\n> level). A key observation is that when \"nextdir\" precedes the next\n> file, then all of the files in subdirectories of nextdir do as well.\n> Thus an obvious recursion would be to call a function like\n> read_all_files_under_dir(indexentries, dirs, dirindex) at this\n> point, which would consume all of the directories that are\n> subdirectories of dirs[dirindex] (i.e., all directories whose names\n> have the string dirs[dirindex] as a prefix). Using this method\n> would mean that there is no need to compare each file under\n> dirs[dirindex] against the next file in the outer directory.\n> \n> Michael\n\nThanks for your feedback! To get clearer code I've now written a\nworking reader for the v5 index format in Python. The full reader\nwould probably be to long for the mailing list, but here is the\ninteresting part:\n\n\ndef readfiles(directories, dirnr, entries):\n global filedata\n f.seek(directories[dirnr][\"foffset\"])\n offset = struct.unpack(\"!I\", fread(4))[0]\n f.seek(offset)\n filedata = list()\n queue = list()\n i = 0\n while i < directories[dirnr][\"nfiles\"]:\n filedata.append(struct.pack(\"!I\", f.tell()))\n filename = \"\"\n byte = fread(1)\n while byte != '\\0':\n filename += byte\n byte = fread(1)\n\n data = struct.unpack(\"!HHIII\", fread(16))\n objhash = fread(20)\n readcrc = struct.pack(\"!i\", binascii.crc32(\"\".join(filedata)))\n crc = f.read(4)\n if readcrc != crc:\n print \"Wrong CRC: \" + filename\n filedata = list()\n\n i += 1\n\n queue.append(dict({\"name\": directories[dirnr][\"pathname\"] + filename, \"flags\": data[0], \"mode\": data[1], \"mtimes\": data[2], \"mtimens\": data[3], \"statcrc\": data[4], \"objhash\": binascii.hexlify(objhash)}))\n\n if len(directories) > dirnr:\n i = 0\n while i < len(queue):\n if len(directories) - 1 > dirnr and queue[i][\"name\"] > directories[dirnr + 1][\"pathname\"]:\n entries, dirnr = readfiles(directories, dirnr + 1, entries)\n else:\n entries.append(queue[i])\n i += 1\n return entries, dirnr\n\nThe full reader can be found here:\nhttps://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py\n\n-- \nThomas\n"},{"id":"191472","messageId":"4FB01080.6010605@alum.mit.edu","threadId":"30413","inReplyTo":"20120511171230.GA2107@tgummerer","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-13T19:50:24Z","receivedAt":"2012-05-13T19:50:24Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/11/2012 07:12 PM, Thomas Gummerer wrote:\n> Thanks for your feedback! To get clearer code I've now written a\n> working reader for the v5 index format in Python. The full reader\n> would probably be to long for the mailing list, but here is the\n> interesting part:\n>\n> [...]\n> The full reader can be found here:\n> https://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py\n\nGood.\n\nI tried to review your code 3fe08f9b:git-read-index-v5.py and compare it \nto your file spec f858cf6a9:Index-format-v5.textile. I have the \nfollowing comments (some of them already discussed in IRC):\n\n1. Your script seems to be reading a different version of the file than \ndescribed in the spec. [When I mentioned this on IRC you pushed a new \nversion a4ee558ea of the spec.]\n\n2. Your script seems to assume that the index file has no extensions. \nIt would be better (for documentation purposes and to ensure that there \nare no surprises) to make sure that the code knows how to handle extensions.\n\n3. Please document briefly how the scripts should be used.\n\n4. Please limit line length to 80 columns (like the main git project).\n\n5. Python has a nicer way to initialize dictionaries whose keys are all \nvalid identifiers; for example:\n\n- return dict({\"signature\": signature, \"vnr\": header[0], \"ndir\": \nheader[1], \"nfile\": header[2], \"next\": header[3]})\n+ return dict(signature=signature, vnr=header[0], ndir=header[1],\n+ nfile=header[2], next=header[3])\n\n6. Some of your print statements are just begging to be written using \nstring interpolation; e.g.,\n\n- print d[\"pathname\"] + \" \" + str(d[\"flags\"]) + \" \" + \nstr(d[\"foffset\"]) + \" \" + str(d[\"cr\"]) + \" \" + str(d[\"ncr\"]) + \" \" + \nstr(d[\"nsubtrees\"]) + \" \" + str(d[\"nfiles\"]) + \" \" + str(d[\"nentries\"]) \n+ \" \" + str(binascii.hexlify(d[\"objname\"]))\n+ print (\"%(pathname)s %(flags)s %(foffset)s %(cr)s %(ncr)s \"\n+ \"%(nsubtrees)s %(nfiles)s %(nentries)s \" % d\n+ + str(binascii.hexlify(d[\"objname\"])))\n\nprintheader() can be rewritten similarly.\n\n7. You have a couple of while loops that would be easier to read if \nwritten as for loops.\n\n8. There is no need to use global variables. Global variables have lots \nof disadvantages, one of which is that it is hard to tell what functions \nhave side effects via the global variables. It is better to pass the \nneeded variables explicitly to functions that need them.\n\n9. ...after you eliminate the global variables, you will see that the \nchecksums are mostly needed over limited areas of code then can be \ndiscarded. Rewriting the checksum handling in this way would make it \neasier to see exactly what range of bytes is included in a particular \nchecksum.\n\n10. There is no need to keep track of all of the data that will go into \na checksum. The CRC32 checksum can be computed incrementally via the \nsecond argument of binascii.crc32(data, crc). Therefore, you only need \nto retain a 32-bit running checksum instead of the filedata array of \ndata strings.\n\n11. It is bad style to generate output from within the \nreadindexentries() function. Given that it reads the whole array of \nfile entries anyway, it would be cleaner to return the array to the \ncaller and let the caller print out what it wants.\n\n12. Your handling of checksum errors is inconsistent. In some places \nyou generate exceptions; in another you simply print an error to stdout \n(not stderr!) and proceed to use the corrupt data.\n\n13. It is probably clearer to unpack the tuples returned by \nstruct.unpack() directly into local variables with meaningful names \ninstead of carrying them around as a tuple; e.g.,\n\n- header = struct.unpack('!IIII', checksum.add(f.read(16)))\n+ (vnr, ndir, nfile, next) = struct.unpack('!IIII', fread(16))\n\n14. It is more correct to check the file signature and version \nexplicitly before plowing into the rest of the file (that's what they're \nthere for!)\n\nThat's as far as I've got.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191473","messageId":"D4710CB39C254E8DA3B9778366145718@PhilipOakley","threadId":"30413","inReplyTo":"CALgYhfMKdbv8TiT4ALDSvD3pSXHEPLWHM09DxYnRmRdBWRjh8Q@mail.gmail.com","subject":"Re: Index format v5","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":"2012-05-13T21:01:44Z","receivedAt":"2012-05-13T21:01:44Z","isPatch":false,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Thomas Gummerer\" Sent: Thursday, May 03, 2012 6:25 PM\n> I have been drafting the Version 5 of the index format over the past\n> few days with the help of Thomas Rast, Michael Haggerty, cmn and\n> barrbrain on IRC. \n\n>\n> GIT index format\n> ================\n>\n> = The git index file has the following format\n>\n\nGiven the discussions on the list about the general naming of Staging vs Index [1], \nwould a careful change to the title, and the adding of an introductory line \nhelp in putting the index file format in the appropriate (implementation) context?\n\nI'm thinking that perhaps -\nTitle: \"GIT index file format (V5)\", i.e. add the 'file' qualifier.\n\nIntroduction line:\n\"The git index file (.git/index) documents the status of the files in the git staging area.\"\n i.e. this is an implementation document for this particular file, but using the terms\n suggested in [1]. Followed by\n\"The staging area is used for preparing commits, merging, etc.\".\n i.e. show the purpose of this index relative to the overall 'staging area'. \n IIRC the use of the staging area for merging was one of Linus's key features;-)\n\nBy crafting the title and the introduction line(s) the confusion e.g. [2], between implementation \ndetails (this document) and conceptual operation can be clearly separated.\n\nPhilip\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/197111 \n [1.8.0] use 'stage' term consistently\n\n[2] http://raflabs.com/blogs/silence-is-foo/2011/04/07/staging-area-index-cache-git/\n ... Git it's a little bit confusing to undersand some of its terminology\n"},{"id":"191493","messageId":"20120514145437.GC2107@tgummerer","threadId":"30413","inReplyTo":"D4710CB39C254E8DA3B9778366145718@PhilipOakley","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-14T14:54:37Z","receivedAt":"2012-05-14T14:54:37Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/13, Philip Oakley wrote:\n> From: \"Thomas Gummerer\" Sent: Thursday, May 03, 2012 6:25 PM\n> >I have been drafting the Version 5 of the index format over the past\n> >few days with the help of Thomas Rast, Michael Haggerty, cmn and\n> >barrbrain on IRC.\n> \n> >\n> >GIT index format\n> >================\n> >\n> >= The git index file has the following format\n> >\n> \n> Given the discussions on the list about the general naming of\n> Staging vs Index [1], would a careful change to the title, and the\n> adding of an introductory line help in putting the index file format\n> in the appropriate (implementation) context?\n> \n> I'm thinking that perhaps -\n> Title: \"GIT index file format (V5)\", i.e. add the 'file' qualifier.\n> \n> Introduction line:\n> \"The git index file (.git/index) documents the status of the files in the git staging area.\"\n> i.e. this is an implementation document for this particular file, but using the terms\n> suggested in [1]. Followed by\n> \"The staging area is used for preparing commits, merging, etc.\".\n> i.e. show the purpose of this index relative to the overall\n> 'staging area'. IIRC the use of the staging area for merging was\n> one of Linus's key features;-)\n> \n> By crafting the title and the introduction line(s) the confusion\n> e.g. [2], between implementation details (this document) and\n> conceptual operation can be clearly separated.\n> \n> Philip\n> \n> [1] http://article.gmane.org/gmane.comp.version-control.git/197111\n> [1.8.0] use 'stage' term consistently\n> \n> [2] http://raflabs.com/blogs/silence-is-foo/2011/04/07/staging-area-index-cache-git/\n> ... Git it's a little bit confusing to undersand some of its terminology\n\nThanks for your suggestion. I've changed the documentation to take this\ninto account.\n"},{"id":"191494","messageId":"20120514150113.GD2107@tgummerer","threadId":"30413","inReplyTo":"4FB01080.6010605@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-14T15:01:13Z","receivedAt":"2012-05-14T15:01:13Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/13, Michael Haggerty wrote:\n> On 05/11/2012 07:12 PM, Thomas Gummerer wrote:\n> >Thanks for your feedback! To get clearer code I've now written a\n> >working reader for the v5 index format in Python. The full reader\n> >would probably be to long for the mailing list, but here is the\n> >interesting part:\n> >\n> >[...]\n> >The full reader can be found here:\n> >https://github.com/tgummerer/git/blob/pythonprototype/git-read-index-v5.py\n> \n> Good.\n> \n> I tried to review your code 3fe08f9b:git-read-index-v5.py and\n> compare it to your file spec f858cf6a9:Index-format-v5.textile. I\n> have the following comments (some of them already discussed in IRC):\n> \n> 1. Your script seems to be reading a different version of the file\n> than described in the spec. [When I mentioned this on IRC you\n> pushed a new version a4ee558ea of the spec.]\n> \n> 2. Your script seems to assume that the index file has no\n> extensions. It would be better (for documentation purposes and to\n> ensure that there are no surprises) to make sure that the code knows\n> how to handle extensions.\n> \n> 3. Please document briefly how the scripts should be used.\n> \n> 4. Please limit line length to 80 columns (like the main git project).\n> \n> 5. Python has a nicer way to initialize dictionaries whose keys are\n> all valid identifiers; for example:\n> \n> - return dict({\"signature\": signature, \"vnr\": header[0],\n> \"ndir\": header[1], \"nfile\": header[2], \"next\": header[3]})\n> + return dict(signature=signature, vnr=header[0], ndir=header[1],\n> + nfile=header[2], next=header[3])\n> \n> 6. Some of your print statements are just begging to be written\n> using string interpolation; e.g.,\n> \n> - print d[\"pathname\"] + \" \" + str(d[\"flags\"]) + \" \" +\n> str(d[\"foffset\"]) + \" \" + str(d[\"cr\"]) + \" \" + str(d[\"ncr\"]) + \" \" +\n> str(d[\"nsubtrees\"]) + \" \" + str(d[\"nfiles\"]) + \" \" +\n> str(d[\"nentries\"]) + \" \" + str(binascii.hexlify(d[\"objname\"]))\n> + print (\"%(pathname)s %(flags)s %(foffset)s %(cr)s %(ncr)s \"\n> + \"%(nsubtrees)s %(nfiles)s %(nentries)s \" % d\n> + + str(binascii.hexlify(d[\"objname\"])))\n> \n> printheader() can be rewritten similarly.\n> \n> 7. You have a couple of while loops that would be easier to read if\n> written as for loops.\n> \n> 8. There is no need to use global variables. Global variables have\n> lots of disadvantages, one of which is that it is hard to tell what\n> functions have side effects via the global variables. It is better\n> to pass the needed variables explicitly to functions that need them.\n> \n> 9. ...after you eliminate the global variables, you will see that\n> the checksums are mostly needed over limited areas of code then can\n> be discarded. Rewriting the checksum handling in this way would\n> make it easier to see exactly what range of bytes is included in a\n> particular checksum.\n> \n> 10. There is no need to keep track of all of the data that will go\n> into a checksum. The CRC32 checksum can be computed incrementally\n> via the second argument of binascii.crc32(data, crc). Therefore,\n> you only need to retain a 32-bit running checksum instead of the\n> filedata array of data strings.\n> \n> 11. It is bad style to generate output from within the\n> readindexentries() function. Given that it reads the whole array of\n> file entries anyway, it would be cleaner to return the array to the\n> caller and let the caller print out what it wants.\n> \n> 12. Your handling of checksum errors is inconsistent. In some\n> places you generate exceptions; in another you simply print an error\n> to stdout (not stderr!) and proceed to use the corrupt data.\n> \n> 13. It is probably clearer to unpack the tuples returned by\n> struct.unpack() directly into local variables with meaningful names\n> instead of carrying them around as a tuple; e.g.,\n> \n> - header = struct.unpack('!IIII', checksum.add(f.read(16)))\n> + (vnr, ndir, nfile, next) = struct.unpack('!IIII', fread(16))\n> \n> 14. It is more correct to check the file signature and version\n> explicitly before plowing into the rest of the file (that's what\n> they're there for!)\n> \n> That's as far as I've got.\n> \n> Michael\n\nThanks a lot for your feedback. I've now refactored the code and\nthanks to your suggestions hopefully made it simpler and easier\nto read. The reader should now read exactly the data from the\nspec.\n"},{"id":"191531","messageId":"4FB1746A.6090408@alum.mit.edu","threadId":"30413","inReplyTo":"20120514150113.GD2107@tgummerer","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-14T21:08:58Z","receivedAt":"2012-05-14T21:08:58Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/14/2012 05:01 PM, Thomas Gummerer wrote:\n> Thanks a lot for your feedback. I've now refactored the code and\n> thanks to your suggestions hopefully made it simpler and easier\n> to read. The reader should now read exactly the data from the\n> spec.\n\nYes, the style is much better now. Here is the next round of feedback:\n\n1. f is still a global variable. This is unnecessary.\n\n2. read_name() is indented incorrectly.\n\n3. The signature and version number should be checked within \nread_header() *before* reading anything else. Otherwise, if some random \nfile is given to the script, it will read some random, probably very \nlarge number for \"nextensions\" and then try to read that number of \nextension offsets into RAM. It would be a pretty innocent error to have \nthe wrong version of the index file lying around, and the script should \ndetect such an error quickly and painlessly rather than triggering a lot \nof pointless disk activity (and likely an out-of-memory error) before \nfiguring out that it shouldn't be reading the file in the first place.\n\n4. For readability reasons, it is better to raise an exception \nimmediately in an error situation rather than put the error-handling \ncode in the \"else\" part of an if statement; i.e., instead of\n\n if not error_condition:\n non-error-actions\n else:\n raise exception\n\nuse\n\n if error_condition:\n raise exception\n\n non-error-actions\n\nThe reasons are: (a) the reader can see immediately what will happen in \nthe error case, then forget it and continue on with the \"normal\" flow \ninstead of having to remember the \"if\" condition through the whole long \n\"then\" block before finally seeing the point in the \"else\" block; (b) \nthen the \"normal\" case doesn't have to be within the if statement at \nall, thereby requiring less block nesting and less indentation. For \nexample:\n\n> - if crc == datacrc:\n> - return dict(signature=signature, vnr=vnr, ndir=ndir, nfile=nfile,\n> - nextensions=nextensions, extoffsets=extoffsets)\n> - else:\n> - raise Exception(\"Wrong header crc\")\n> + if crc != datacrc:\n> + raise Exception(\"Wrong header crc\")\n> +\n> + return dict(signature=signature, vnr=vnr, ndir=ndir, nfile=nfile,\n> + nextensions=nextensions, extoffsets=extoffsets)\n\n5. If the first limit of a range() or xrange() is zero, it is usually \nomitted; e.g., \"xrange(0, nextensions)\" -> \"xrange(nextensions)\".\n\n6. It is possible to precompile \"struct\" patterns, which should be \nfaster and also allows you to ask the Struct object its size, reducing \nthe number of magic numbers needed in the code. And fixed-length \nstrings can also be read via struct. For example:\n\n> DIR_DATA_STRUCT = struct.Struct(\"!HIIIIII 20s\")\n>\n>\n> def read_dirs(f, ndir):\n> dirs = list()\n> for i in xrange(0, ndir):\n> (pathname, partialcrc) = read_name(f)\n>\n> (filedata, partialcrc) = read_calc_crc(f, DIR_DATA_STRUCT.size, partialcrc)\n> (flags, foffset, cr, ncr, nsubtrees, nfiles,\n> nentries, objname) = DIR_DATA_STRUCT.unpack(filedata)\n> # ...\n\n7. The \"if dirnr == 0\" stuff in read_files() should probably be done in \nread_index_entries() (the first invocation is the only place dirnr==0, \nright?)\n\n8. read_files() only returns a result \"if len(directories) > dirnr\". \nBut actually I don't see the purpose for the check. Earlier in the \nfunction you dereference directories[dirnr] several times, so it *must* \nbe that dirnr < len(directories). I think you can take out this test \nand unindent its block.\n\n9. read_files() doesn't need to return \"entries\". Since entries is an \narray that is only mutated in place, the return value will always be the \nsame as the \"entries\" argument (albeit fuller).\n\n10. It would make sense to extract a function read_file(), which reads a \nsingle file entry from the current position in the current file (using \ncode from read_files()). Similarly for read_dir()/read_dirs().\n\n11. It is good form to move the file-level code into a main() function, \nthen call that from the bottom of the file, something like this:\n\n > def main(args):\n > ....\n >\n > main(sys.argv[1:])\n\nThis avoids creating global variables that are accidentally used within \nfunctions.\n\n\nWhat is your plan for testing this code, and later the C version? For \nexample, you might want to have a suite of index files with various \ncontents, and compare the \"git ls-files --debug\" output with the output \nthat is expected. How would you create index files like this? Via git \ncommands? Or should one of your Python scripts be taught how to do it?\n\nTo make testing easier, you probably don't want to hard-code the name of \nthe input file in git-read-index-v5.py, so that you can use it to read \narbitrary files. For example, you might want to honor the \nGIT_INDEX_FILES environment variable in some form, or to take the name \nof the index file as a command-line argument.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191532","messageId":"87bolqtnva.fsf@thomas.inf.ethz.ch","threadId":"30413","inReplyTo":"4FB1746A.6090408@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-14T22:10:49Z","receivedAt":"2012-05-14T22:10:49Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Michael Haggerty writes:\n\nFirst of all, many thanks for taking up this time-consuming job while I\nwas away! There's not much I can add at this point, just a few minor\npoints:\n\n> 9. read_files() doesn't need to return \"entries\". Since entries is an\n> array that is only mutated in place, the return value will always be\n> the same as the \"entries\" argument (albeit fuller).\n\n(Ab)using an array in this fashion is somewhat iffy. It seems\nunavoidable in this case (while still retaining the runtime), but try\nnot to do it too often, and perhaps name the parameter something that\nmakes this clear (such as 'out'). Usually changing it to use a\ngenerator function (with 'yield') helps.\n\n> 11. It is good form to move the file-level code into a main()\n> function, then call that from the bottom of the file, something like\n> this:\n>\n>> def main(args):\n>> ....\n>>\n>> main(sys.argv[1:])\n\nIt's customary to wrap it as\n\nif __name__ == '__main__':\n main(sys.argv[1:])\n\nThat way your script becomes 'import'-able, which can be handy (if only\nfor testing).\n\nCheers,\nThomas\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"191539","messageId":"4FB1FB11.70209@alum.mit.edu","threadId":"30413","inReplyTo":"87bolqtnva.fsf@thomas.inf.ethz.ch","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-15T06:43:29Z","receivedAt":"2012-05-15T06:43:29Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/15/2012 12:10 AM, Thomas Rast wrote:\n> Michael Haggerty writes:\n>> 9. read_files() doesn't need to return \"entries\". Since entries is an\n>> array that is only mutated in place, the return value will always be\n>> the same as the \"entries\" argument (albeit fuller).\n>\n> (Ab)using an array in this fashion is somewhat iffy. It seems\n> unavoidable in this case (while still retaining the runtime), but try\n> not to do it too often, and perhaps name the parameter something that\n> makes this clear (such as 'out'). Usually changing it to use a\n> generator function (with 'yield') helps.\n\nIf the goal were an ideal Python program, then by all means generators \nare the way to go. But since the goal is a prototype for a C program, \nthen a change to using generators would just have to be undone when \nconverting to C.\n\n>> 11. It is good form to move the file-level code into a main()\n>> function, then call that from the bottom of the file, something like\n>> this:\n>>\n>>> def main(args):\n>>> ....\n>>>\n>>> main(sys.argv[1:])\n>\n> It's customary to wrap it as\n>\n> if __name__ == '__main__':\n> main(sys.argv[1:])\n>\n> That way your script becomes 'import'-able, which can be handy (if only\n> for testing).\n\n+1\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191548","messageId":"20120515134916.GA2074@tgummerer.unibz.it","threadId":"30413","inReplyTo":"4FB1746A.6090408@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-15T13:49:16Z","receivedAt":"2012-05-15T13:49:16Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/14, Michael Haggerty wrote:\n> On 05/14/2012 05:01 PM, Thomas Gummerer wrote:\n> >Thanks a lot for your feedback. I've now refactored the code and\n> >thanks to your suggestions hopefully made it simpler and easier\n> >to read. The reader should now read exactly the data from the\n> >spec.\n> \n> Yes, the style is much better now. Here is the next round of feedback:\n> [...]\n> \n> >DIR_DATA_STRUCT = struct.Struct(\"!HIIIIII 20s\")\n> >\n> >\n> >def read_dirs(f, ndir):\n> > dirs = list()\n> > for i in xrange(0, ndir):\n> > (pathname, partialcrc) = read_name(f)\n> >\n> > (filedata, partialcrc) = read_calc_crc(f, DIR_DATA_STRUCT.size, partialcrc)\n> > (flags, foffset, cr, ncr, nsubtrees, nfiles,\n> > nentries, objname) = DIR_DATA_STRUCT.unpack(filedata)\n> > # ...\n> \n> [...]\n\nThanks again for your feedback. I've refactored the code again,\nthanks to your suggestions. If I'm correct it's fine to have the\ncompiled structs global?\n\n> What is your plan for testing this code, and later the C version?\n> For example, you might want to have a suite of index files with\n> various contents, and compare the \"git ls-files --debug\" output with\n> the output that is expected. How would you create index files like\n> this? Via git commands? Or should one of your Python scripts be\n> taught how to do it?\n\nI thought of using real world examples for this, for example the\nWebKit index, which is pretty large, and some others, for example the\ngit index and the linux kernel index.\n\nThere would be some changes necessary to the output format of \ngit ls-files --debug, to work with the new index format, but those\nshould be fairly simple.\n\n> To make testing easier, you probably don't want to hard-code the\n> name of the input file in git-read-index-v5.py, so that you can use\n> it to read arbitrary files. For example, you might want to honor\n> the GIT_INDEX_FILES environment variable in some form, or to take\n> the name of the index file as a command-line argument.\n\nI've changed this in the script, which now takes a --file argument\nwith the file name of the index file that should be read.\n(git-read-index-v5.py --file=FILENAME)\n\n-- \nThomas\n"},{"id":"191549","messageId":"4FB2700D.5000900@alum.mit.edu","threadId":"30413","inReplyTo":"20120515134916.GA2074@tgummerer.unibz.it","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-15T15:02:37Z","receivedAt":"2012-05-15T15:02:37Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/15/2012 03:49 PM, Thomas Gummerer wrote:\n> Thanks again for your feedback. I've refactored the code again,\n> thanks to your suggestions.\n\nGood. I'll try to review the new version as soon as possible.\n\nI suggest that you apply the same kinds of cleanups to \ngit-convert-index.py (which I personally haven't looked at yet at all). \n If you want my feedback on that script, please let me know when you \nthink it is ready.\n\n > If I'm correct it's fine to have the\n> compiled structs global?\n\nYes, that's OK because they are constants so there is no risk of them \npropagating side-effects. (Of course, Python doesn't enforce the \nconstness of identifiers, but by convention ALL_CAPS identifiers are \nconstants and it would be an obvious no-no to modify one.)\n\nA real Pythonic solution would probably encapsulate all of your code \n(including the constants) in classes. But since you will eventually \ntranslate the code to C, I don't think that step is crucial. If, on the \nother hand, you propose to include Python scripts in the git \ndistribution, then making them Pythonic would definitely be on the agenda.\n\n>> What is your plan for testing this code, and later the C version?\n>> For example, you might want to have a suite of index files with\n>> various contents, and compare the \"git ls-files --debug\" output with\n>> the output that is expected. How would you create index files like\n>> this? Via git commands? Or should one of your Python scripts be\n>> taught how to do it?\n>\n> I thought of using real world examples for this, for example the\n> WebKit index, which is pretty large, and some others, for example the\n> git index and the linux kernel index.\n\nIt is good to do such manual tests, but you probably also want small, \nhand-constructed, automatable tests to make sure that all of the \ncodepaths are exercised. For example,\n\n* A directory containing only files\n\n* A directory containing only subdirectories\n\n* A mixed directory whose last element is a file / last element is a \nsubdirectory\n\n* Various types of conflicts\n\n...etc.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191574","messageId":"4FB334C7.2070201@alum.mit.edu","threadId":"30413","inReplyTo":"20120515134916.GA2074@tgummerer.unibz.it","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-16T05:01:59Z","receivedAt":"2012-05-16T05:01:59Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/15/2012 03:49 PM, Thomas Gummerer wrote:\n> Thanks again for your feedback. I've refactored the code again,\n> thanks to your suggestions.\n\nI just reviewed version 1369bd855b86 of your script, and it is MUCH \nbetter. It's easy to read and review. The functions that it defines \nare now self-contained and could therefore be reused for other purposes. \n There are fewer magic numbers (though there are still a few; I wonder \nif there is a way to get rid of those?) You've done a nice job \npolishing up the code.\n\nI have only a few remaining niggles::\n\n1. The struct module can handle fixed-length strings, so you could read \nand parse the SHA1s as part of FILE_DATA_STRUCT and DIR_DATA_STRUCT \nrather than handling them separately.\n\n2. At least some of the functions deserve docstrings, especially when \nthey are nontrivial. For example, what arguments read_files() needs and \nhow they are used is far from obvious.\n\n3. It would be easier to read the multiline string formatting templates \nif they are written as multiline strings (even though this kindof \nrequires that they be made file-level constants); e.g.,\n\nFILE_FORMAT = \"\"\"\\\n%(name)s (%(objhash)s)\nmtime: %(mtimes)s:%(mtimens)s\nmode: %(mode)s flags: %(flags)s\nstatcrc: \"\"\"\n\nIn the future, please try to commit one self-contained change at a time \nand make your commit messages really describe what is changed in the \ncommit. For example, commit fb2654c648a does at least three things, \nonly one of which is mentioned in its commit message. It would be \nbetter to break this into three commits with three commit messages. Use \n\"git rebase -i\" and the other commit-rewriting tools liberally to tidy \nup commits before publishing them (but not after publishing them!); for \nexample, commit be8d01c22c should really have been squashed on top of \n\"Changed main to a function\" so that the rest of the world doesn't have \nto see the broken latter commit.\n\nBut I don't want to detract from the fact that altogether you have made \nvery nice improvements to the script, and I hope to see more like this \nfrom you in the future!\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191611","messageId":"20120516215407.GA1738@tgummerer.surfnet.iacbox","threadId":"30413","inReplyTo":"4FB334C7.2070201@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-16T21:54:07Z","receivedAt":"2012-05-16T21:54:07Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/16, Michael Haggerty wrote:\n> I just reviewed version 1369bd855b86 of your script, and it is MUCH\n> better. It's easy to read and review. The functions that it\n> defines are now self-contained and could therefore be reused for\n> other purposes. There are fewer magic numbers (though there are\n> still a few; I wonder if there is a way to get rid of those?)\n> You've done a nice job polishing up the code.\n\nThanks for the feedback! I could get rid of the magic numbers for\nthe crc code, but I'm not sure if it makes sense to replace the\nothers with constants, since they only occur once in the file. I\nadded comments instead explaining where those numbers come from\ninstead.\n\n> I have only a few remaining niggles::\n> \n> 1. The struct module can handle fixed-length strings, so you could\n> read and parse the SHA1s as part of FILE_DATA_STRUCT and\n> DIR_DATA_STRUCT rather than handling them separately.\n> \n> 2. At least some of the functions deserve docstrings, especially\n> when they are nontrivial. For example, what arguments read_files()\n> needs and how they are used is far from obvious.\n> \n> 3. It would be easier to read the multiline string formatting\n> templates if they are written as multiline strings (even though this\n> kindof requires that they be made file-level constants); e.g.,\n> \n> FILE_FORMAT = \"\"\"\\\n> %(name)s (%(objhash)s)\n> mtime: %(mtimes)s:%(mtimens)s\n> mode: %(mode)s flags: %(flags)s\n> statcrc: \"\"\"\n\nThanks, I have changed those. I added the docstrings for all read\nfunctions, they however don't seem to make sense for the print\nfunctions, since you're probably faster just reading the code for\nthem.\n\nOne since I changed in addition is to those changes, is that I\ngave the exceptions names to make them more meaningful.\n\n> In the future, please try to commit one self-contained change at a\n> time and make your commit messages really describe what is changed\n> in the commit. For example, commit fb2654c648a does at least three\n> things, only one of which is mentioned in its commit message. It\n> would be better to break this into three commits with three commit\n> messages. Use \"git rebase -i\" and the other commit-rewriting tools\n> liberally to tidy up commits before publishing them (but not after\n> publishing them!); for example, commit be8d01c22c should really have\n> been squashed on top of \"Changed main to a function\" so that the\n> rest of the world doesn't have to see the broken latter commit.\n\nOk, I'll try my best to do that.\n\n--\nThomas\n"},{"id":"191666","messageId":"20120518153826.GB1738@tgummerer.surfnet.iacbox","threadId":"30413","inReplyTo":"4FB2700D.5000900@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-18T15:38:26Z","receivedAt":"2012-05-18T15:38:26Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n> I suggest that you apply the same kinds of cleanups to\n> git-convert-index.py (which I personally haven't looked at yet at\n> all). If you want my feedback on that script, please let me know\n> when you think it is ready.\n\nThat would be great, if you have the time to do it. I'm not\ncompletely finished with it (docstrings and conflicted data writing\nare still missing).\n\nI'm not sure about the read_tree_extensiondata method, if I should\nextract a method, which only reads one entry, but I'm not sure that\nwould make any sense, since there would be a lot of parameters and\nreturn values to the function.\n\nThe same thing is in the main method, where I'm not sure if it's\nbetter to extract the read_index and write_index functions, or\njust leave the code in the main method. My guess is that it makes\nsense in the main method, since there are less calls, but it\ndoesn't make sense in the read_tree_extensiondata method?\n\nAnother thing I'm unsure about is the write_directory_data method,\nif there is any way to replace the try/except with something\nsimpler?\n\n--\nThomas\n"},{"id":"191722","messageId":"4FB73268.4020204@alum.mit.edu","threadId":"30413","inReplyTo":"20120516215407.GA1738@tgummerer.surfnet.iacbox","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-19T05:40:56Z","receivedAt":"2012-05-19T05:40:56Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/16/2012 11:54 PM, Thomas Gummerer wrote:\n> On 05/16, Michael Haggerty wrote:\n>> I just reviewed version 1369bd855b86 of your script, and it is MUCH\n>> better. It's easy to read and review. The functions that it\n>> defines are now self-contained and could therefore be reused for\n>> other purposes. There are fewer magic numbers (though there are\n>> still a few; I wonder if there is a way to get rid of those?)\n>> You've done a nice job polishing up the code.\n>\n> Thanks for the feedback! I could get rid of the magic numbers for\n> the crc code, but I'm not sure if it makes sense to replace the\n> others with constants, since they only occur once in the file. I\n> added comments instead explaining where those numbers come from\n> instead.\n\nI think it is possible to remove the last magic number and also to make \nthe CRC handling easier. I have pushed some suggested changes to github \n[1]:\n\n1. With the current code, trying to read a file that is less than 24 \nbytes long would result in a struct.error (because it would try to \nunpack a string that is shorter than the struct) whereas the underlying \nerror in this case should almost always be reported as a signature \nerror. So it is correct to read the signature separately from the rest \nof the header, but it is even more correct to check the signature \n(including its length) before reading on.\n\n2. I introduce a class CRC to hold checksums, so that (a) the code for \nhandling checksums can be encapsulated, and (b) an instance of this \nclass can be passed into functions and mutated in-place, which is less \ncumbersome than requiring functions to return (data, crc) tuples. This, \nin turn, makes possible...\n\n3. ...a new function read_struct(f, s, crc), which reads the data for a \nstruct.Struct from f, checksums it, and returns the unpacked data. This \nfunction is more convenient to use than the old read_calc_crc().\n\n4. The checksum instance can also be made responsible for verifying that \nthe next four bytes in the file agree with the expected checksum. This \nremoves some more code duplication. (See CRC.matches().)\n\n5. You read the extension offsets using CRC_STRUCT.size, which is \ntechnically correct but misleading. In fact, the extension offsets \nshould be documented using their own EXTENSION_INDEX_STRUCT. Also, it \nmakes more sense to store the unpacked integer offsets to extoffsets \nrather than the raw 4-byte strings.\n\n6. With a couple of more minor changes it is possible to replace the \nmagic number \"24\" in read_index_entries(). With this change the \ncomputation is documented very explicitly and is also (somewhat) robust \nagainst future changes in the format.\n\nLook over my changes and take whatever you want.\n\n> Thanks, I have changed those. I added the docstrings for all read\n> functions, they however don't seem to make sense for the print\n> functions, since you're probably faster just reading the code for\n> them.\n\nThat's fine. If you document nontrivial functions you are already doing \nmuch better than the git project average.\n\n> One since I changed in addition is to those changes, is that I\n> gave the exceptions names to make them more meaningful.\n\nGood.\n\nMichael\n\n[1] https://github.com/mhagger/git/tree/pythonprototype\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191734","messageId":"4FB7998B.2030305@alum.mit.edu","threadId":"30413","inReplyTo":"20120518153826.GB1738@tgummerer.surfnet.iacbox","subject":"Re: Index format v5","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-05-19T13:00:59Z","receivedAt":"2012-05-19T13:00:59Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/18/2012 05:38 PM, Thomas Gummerer wrote:\n>\n>> I suggest that you apply the same kinds of cleanups to\n>> git-convert-index.py (which I personally haven't looked at yet at\n>> all). If you want my feedback on that script, please let me know\n>> when you think it is ready.\n>\n> That would be great, if you have the time to do it. I'm not\n> completely finished with it (docstrings and conflicted data writing\n> are still missing).\n\nI've looked over the writing side of git-convert-index.py version\n81411fe6c98, and here are my first comments:\n\n* Please remove trailing whitespace from the source code.\n\n* I suggest that you move constants and code shared by\n git-convert-index.py and git-read-index-v5.py into a library. Though\n actually, given that git doesn't seem to have infrastructure for\n dealing with Python libraries, this might take some improvisation.\n\n* Please use constants for all of the struct formats. Constants have\n names, making them mostly self-documenting.\n\n* write_directories() currently writes pathnames and fake data and\n stores file offsets in memory. Later write_directory_data() runs\n through the file again, seek()ing over the filenames and filling in\n real data.\n\n Wouldn't it be easier for the first pass just to *compute* and\n record the offsets of the entries to RAM, without writing anything\n to disk, and leave all of the writing to the second pass?\n\n* Instead of writing blank data, it is possible to seek() past it and\n start writing the next thing. The skipped-over file contents are\n logically initialized to zero.\n\n* When working with iteritems(), it is clearer to unpack the item\n pairs and give them names rather than working with d[0] and d[1];\n for example,\n\n - for d in sorted(dirdata.iteritems()):\n + for (pathname,entry) in sorted(dirdata.iteritems()):\n\n* write_directories() returns a \"dirdata\" that is just an empty\n defaultdict. This seems pointless. Do you have future plans to\n change write_directories() to store something into the dictionary?\n\n* The documentation for binascii.crc32() mentions that it gives\n inconsistent results (signed vs. unsigned) for different versions of\n Python. Please ensure that you are using it in a way that is\n maximally portable. (That seems to imply using (binascii.crc32(...)\n & 0xffffffff) and treating the result as unsigned.)\n\n* At first I thought it was a little bit odd that you pass data\n structures around as dictionaries, but I didn't object. But as I\n look at more and more code it seems more and more cumbersome.\n Therefore, I suggest that you define classes to hold the various\n entities that are manipulated by your programs, because:\n\n * A class definition is a good place to document exactly what fields\n an object is expected to have, and what they mean.\n\n * Access of instance fields (entry.path) is easier to read and type\n than dictionary access (entry[\"path\"]).\n\n * The class definitions will translate pretty directly to C structs.\n\n The fact that class instances use a bit more memory than\n dictionaries is, I think, unimportant. But if that really bothers\n you, you can use __slots__ to save some of the instance memory.\n\nAt a higher level:\n\n* What if the offsets to each section were stored in the header, and\n the offsets recorded for dirs and files were relative to the start\n of the section (rather than relative to the start of the file)? I\n think that this would leave open the possibility of formatting the\n sections in memory in parallel in a single pass, then dumping the\n sections to disk in a few big writes (though I'm not saying that this\n should be the *default* way of writing).\n\n* Do you plan to write prototypes for some of the cool new\n functionality that v5 is intended to make possible? For example,\n\n * reading a few specific entries out of an index file\n\n * updating single entries\n\n * adding/removing conflict data to an existing file\n\n * dealing with all of the issues that will come with supporting the\n mutation of an existing index file (i.e., locking, consistency\n checks, etc)\n\n As you probably know from discussions on IRC, I think that the last\n of these is the biggest risk to the success of the project.\n\n> I'm not sure about the read_tree_extensiondata method, if I should\n> extract a method, which only reads one entry, but I'm not sure that\n> would make any sense, since there would be a lot of parameters and\n> return values to the function.\n\nIf the index were represented by a class instance, then all of the \ninformation would be grouped together as a coherent whole that is easy \nto pass around.\n\n> The same thing is in the main method, where I'm not sure if it's\n> better to extract the read_index and write_index functions, or\n> just leave the code in the main method. My guess is that it makes\n> sense in the main method, since there are less calls, but it\n> doesn't make sense in the read_tree_extensiondata method?\n\nDitto.\n\n> Another thing I'm unsure about is the write_directory_data method,\n> if there is any way to replace the try/except with something\n> simpler?\n\nWith dictionaries, you can do\n\n- try:\n- flags = d[1][\"flags\"]\n- except KeyError:\n- flags = 0\n+ flags = d[1].get(\"flags\", 0)\n\nIf you convert to class instances, then presumably the constructor would \nset valid default values for all of the fields.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"191787","messageId":"20120521074525.GA1054@tgummerer","threadId":"30413","inReplyTo":"4FB7998B.2030305@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-21T07:45:25Z","receivedAt":"2012-05-21T07:45:25Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\nThanks a lot for your feedback.\n\nOn 05/19, Michael Haggerty wrote:\n> I've looked over the writing side of git-convert-index.py version\n> 81411fe6c98, and here are my first comments:\n> \n> * Please remove trailing whitespace from the source code.\n> \n> * I suggest that you move constants and code shared by\n> git-convert-index.py and git-read-index-v5.py into a library. Though\n> actually, given that git doesn't seem to have infrastructure for\n> dealing with Python libraries, this might take some improvisation.\n\nI've created a directory python/lib, where I'll put the python libraries.\nI'm not entirely sure this is the correct way to do it, however since\nthe python code will not be in the main git, but is just a prototype,\nI think it's fine.\n\nFor now I moved the format strings, the structs, the exceptions and\nthe new calculate_crc method to the library. Once I go over\ngit-read-index-v5.py I'll probably move more code there.\n\n> * Please use constants for all of the struct formats. Constants have\n> names, making them mostly self-documenting.\n> \n> * write_directories() currently writes pathnames and fake data and\n> stores file offsets in memory. Later write_directory_data() runs\n> through the file again, seek()ing over the filenames and filling in\n> real data.\n> \n> Wouldn't it be easier for the first pass just to *compute* and\n> record the offsets of the entries to RAM, without writing anything\n> to disk, and leave all of the writing to the second pass?\n\nI don't think that would be easier, since I have to go over all the\ndata when writing anyway. It might however be faster.\n\n> * Instead of writing blank data, it is possible to seek() past it and\n> start writing the next thing. The skipped-over file contents are\n> logically initialized to zero.\n> \n> * When working with iteritems(), it is clearer to unpack the item\n> pairs and give them names rather than working with d[0] and d[1];\n> for example,\n> \n> - for d in sorted(dirdata.iteritems()):\n> + for (pathname,entry) in sorted(dirdata.iteritems()):\n> \n> * write_directories() returns a \"dirdata\" that is just an empty\n> defaultdict. This seems pointless. Do you have future plans to\n> change write_directories() to store something into the dictionary?\n> \n> * The documentation for binascii.crc32() mentions that it gives\n> inconsistent results (signed vs. unsigned) for different versions of\n> Python. Please ensure that you are using it in a way that is\n> maximally portable. (That seems to imply using (binascii.crc32(...)\n> & 0xffffffff) and treating the result as unsigned.)\n> \n> * At first I thought it was a little bit odd that you pass data\n> structures around as dictionaries, but I didn't object. But as I\n> look at more and more code it seems more and more cumbersome.\n> Therefore, I suggest that you define classes to hold the various\n> entities that are manipulated by your programs, because:\n> \n> * A class definition is a good place to document exactly what fields\n> an object is expected to have, and what they mean.\n> \n> * Access of instance fields (entry.path) is easier to read and type\n> than dictionary access (entry[\"path\"]).\n> \n> * The class definitions will translate pretty directly to C structs.\n> \n> The fact that class instances use a bit more memory than\n> dictionaries is, I think, unimportant. But if that really bothers\n> you, you can use __slots__ to save some of the instance memory.\n> \n> At a higher level:\n> \n> * What if the offsets to each section were stored in the header, and\n> the offsets recorded for dirs and files were relative to the start\n> of the section (rather than relative to the start of the file)? I\n> think that this would leave open the possibility of formatting the\n> sections in memory in parallel in a single pass, then dumping the\n> sections to disk in a few big writes (though I'm not saying that this\n> should be the *default* way of writing).\n\nI'm thinking if there are any drawbacks doing it that way, but until\nnow no drawbacks came to my mind. Otherwise this sounds like a good\nidea, and I'll include it in the next version.\n\n> * Do you plan to write prototypes for some of the cool new\n> functionality that v5 is intended to make possible? For example,\n> \n> * reading a few specific entries out of an index file\n> \n> * updating single entries\n> \n> * adding/removing conflict data to an existing file\n> \n> * dealing with all of the issues that will come with supporting the\n> mutation of an existing index file (i.e., locking, consistency\n> checks, etc)\n> \n> As you probably know from discussions on IRC, I think that the last\n> of these is the biggest risk to the success of the project.\n\nI thought of implementing prototypes as the proejct goes on, but not\nall of them now. I'd rather first start implementing the reader,\nbecause otherwise the time could get a problem for the midterm.\n\n--\nThomas\n"},{"id":"191826","messageId":"20120521203018.GA57389@tgummerer.unibz.it","threadId":"30413","inReplyTo":"4FB73268.4020204@alum.mit.edu","subject":"Re: Index format v5","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2012-05-21T20:30:18Z","receivedAt":"2012-05-21T20:30:18Z","isPatch":false,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"\n\nOn 05/19, Michael Haggerty wrote:\n> I think it is possible to remove the last magic number and also to\n> make the CRC handling easier. I have pushed some suggested changes\n> to github [1]:\n> \n> 1. With the current code, trying to read a file that is less than 24\n> bytes long would result in a struct.error (because it would try to\n> unpack a string that is shorter than the struct) whereas the\n> underlying error in this case should almost always be reported as a\n> signature error. So it is correct to read the signature separately\n> from the rest of the header, but it is even more correct to check\n> the signature (including its length) before reading on.\n\nI looked at the current git code, and the filesize is used for\nchecking if the index size is big enough. I'll implement it that way\nin the prototype for now.\n\n> 2. I introduce a class CRC to hold checksums, so that (a) the code\n> for handling checksums can be encapsulated, and (b) an instance of\n> this class can be passed into functions and mutated in-place, which\n> is less cumbersome than requiring functions to return (data, crc)\n> tuples. This, in turn, makes possible...\n> \n> 3. ...a new function read_struct(f, s, crc), which reads the data\n> for a struct.Struct from f, checksums it, and returns the unpacked\n> data. This function is more convenient to use than the old\n> read_calc_crc().\n> \n> 4. The checksum instance can also be made responsible for verifying\n> that the next four bytes in the file agree with the expected\n> checksum. This removes some more code duplication. (See\n> CRC.matches().)\n>\n> 5. You read the extension offsets using CRC_STRUCT.size, which is\n> technically correct but misleading. In fact, the extension offsets\n> should be documented using their own EXTENSION_INDEX_STRUCT. Also,\n> it makes more sense to store the unpacked integer offsets to\n> extoffsets rather than the raw 4-byte strings.\n> \n> 6. With a couple of more minor changes it is possible to replace the\n> magic number \"24\" in read_index_entries(). With this change the\n> computation is documented very explicitly and is also (somewhat)\n> robust against future changes in the format.\n> \n> Look over my changes and take whatever you want.\n\nThanks, I didn't merge them directly, but I took the basics out and\nmerged them with my code.\n\n--\nThomas\n"}]}