{"thread":{"id":"21888","subject":"[RFC/PATCHv10 00/11] git notes","startedAt":"2009-12-07T11:27:23Z","lastAt":"2009-12-11T03:00:17Z","messageCount":28,"participants":["Johan Herland","Shawn O. Pearce","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"129404","messageId":"1260185254-1523-1-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":null,"subject":"[RFC/PATCHv10 00/11] git notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:23Z","receivedAt":"2009-12-07T11:27:23Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Hi,\n\nHere is the 10th iteration of the git-notes series. Changes in this\niteration are as follows:\n\nChanges to existing patches:\n\n- Rebased onto 488bdf2... (Fix crasher on encountering SHA1-like non-note\n in notes tree) (There are no conflicts resolved by this, but a test in\n this series crashes without the crash fix in 488bdf2...).\n\n- Yet another rewrite of the fast-import patch. After trying to implement\n Shawn's suggestions, I found that hacking the mode bits of note entries\n could not work, since they are stripped by a mktree()/load_tree()\n round-trip. The new versions treats _all_ entries with note-compatible\n paths (40 hex chars, not including directory separators) as note entries\n (to be subjected to fanout adjustments) in branches where there are note\n activity (one or more 'N' commands).\n Branches without note activity are not touched, of course.\n\n- Otherwise, Shawn's suggestions to the previous iteration have been\n incorporated.\n\n- Extended t9301 tests to verify that non-notes residing in a notes tree\n are not clobbered by the fast-import patch.\n\n- Fix t9301 test #12 to not \"cheat\" (by 'deleteall' followed by a few\n additions). Instead, remove notes one-by-one to verify correct\n fanout consolidation.\n\n- Minor cleanups here and there\n\n\nIf Shawn is OK with the fast-import patch, I believe that at least\npatches #1 - #3 (and possibly #4 - #5) are ready for 'next'.\n\nPatches #6 - #11 drastically extend the notes API. Since there are\ncurrently no users of that API, and it has not been discussed much\non the list (although these patches have already been present in a\nfew iterations), I would still consider them RFC quality.\n\n\nTODO:\n- Builtin-ify git-notes shell script to take advantage of notes API\n- Garbage collect notes whose referenced object is unreachable (gc_notes())\n- Handle note objects that are not blobs, but trees\n\n\nHave fun! :)\n\n...Johan\n\n\nJohan Herland (11):\n fast-import: Proper notes tree manipulation\n Rename t9301 to t9350, to make room for more fast-import tests\n Add more testcases to test fast-import of notes\n Minor style fixes to notes.c\n Notes API: get_commit_notes() -> format_note() + remove the commit restriction\n Notes API: init_notes(): Initialize the notes tree from the given notes ref\n Notes API: add_note(): Add note objects to the internal notes tree structure\n Notes API: get_note(): Return the note annotating the given object\n Notes API: for_each_note(): Traverse the entire notes tree with a callback\n Notes API: Allow multiple concurrent notes trees with new struct notes_tree\n Refactor notes concatenation into a flexible interface for combining notes\n\n fast-import.c | 134 +++++-\n notes.c | 345 +++++++++----\n notes.h | 114 ++++-\n pretty.c | 9 +-\n t/t9300-fast-import.sh | 156 +++++-\n t/t9301-fast-import-notes.sh | 623 ++++++++++++++++++++++\n t/{t9301-fast-export.sh => t9350-fast-export.sh} | 0\n 7 files changed, 1259 insertions(+), 122 deletions(-)\n create mode 100755 t/t9301-fast-import-notes.sh\n rename t/{t9301-fast-export.sh => t9350-fast-export.sh} (100%)\n"},{"id":"129405","messageId":"1260185254-1523-2-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:24Z","receivedAt":"2009-12-07T11:27:24Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This patch teaches 'git fast-import' to automatically organize note objects\nin a fast-import stream into an appropriate fanout structure. The notes API\nin notes.h is NOT used to accomplish this, because trying to keep the\nfast-import and notes data structures in sync would yield a significantly\nlarger patch with higher complexity.\n\nNote objects are added with the 'N' command, and accounted for with a\nper-branch counter, which is used to trigger fanout restructuring when\nneeded. Note that when restructuring the branch tree, _any_ entry whose\npath consists of 40 hex chars (not including directory separators) will\nbe recognized as a note object. It is therefore not advisable to\nmanipulate note entries with M/D/R/C commands.\n\nSince note objects are stored in the same tree structure as other objects,\nthe unloading and reloading of a fast-import branches handle note objects\ntransparently.\n\nThis patch has been improved by the following contributions:\n- Shawn O. Pearce: Several style- and logic-related improvements\n\nCc: Shawn O. Pearce \nSigned-off-by: Johan Herland \n---\n\nAs stated in the cover letter, I simply cannot store note information in\nthe tree_entry mode bits. So, I chose this somewhat more simple and crude\napproach, which I still think solves the problems quite nicely.\n\n\nHave fun! :)\n\n...Johan\n\n\n fast-import.c | 134 +++++++++++++++++++++++++++++++++++++++--\n t/t9300-fast-import.sh | 156 ++++++++++++++++++++++++++++++++++++++++++++----\n 2 files changed, 272 insertions(+), 18 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex dd3c99d..f04cd17 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -245,6 +245,7 @@ struct branch\n \tconst char *name;\n \tstruct tree_entry branch_tree;\n \tuintmax_t last_commit;\n+\tuintmax_t num_notes;\n \tunsigned active : 1;\n \tunsigned pack_id : PACK_ID_BITS;\n \tunsigned char sha1[20];\n@@ -693,6 +694,7 @@ static struct branch *new_branch(const char *name)\n \tb->table_next_branch = branch_table[hc];\n \tb->branch_tree.versions[0].mode = S_IFDIR;\n \tb->branch_tree.versions[1].mode = S_IFDIR;\n+\tb->num_notes = 0;\n \tb->active = 0;\n \tb->pack_id = MAX_PACK_ID;\n \tbranch_table[hc] = b;\n@@ -1860,6 +1862,109 @@ static void load_branch(struct branch *b)\n \t}\n }\n\n+static unsigned char convert_num_notes_to_fanout(uintmax_t num_notes)\n+{\n+\tunsigned char fanout = 0;\n+\twhile ((num_notes >>= 8))\n+\t\tfanout++;\n+\treturn fanout;\n+}\n+\n+static void construct_path_with_fanout(const char *hex_sha1,\n+\t\tunsigned char fanout, char *path)\n+{\n+\tunsigned int i = 0, j = 0;\n+\tif (fanout >= 20)\n+\t\tdie(\"Too large fanout (%u)\", fanout);\n+\twhile (fanout) {\n+\t\tpath[i++] = hex_sha1[j++];\n+\t\tpath[i++] = hex_sha1[j++];\n+\t\tpath[i++] = '/';\n+\t\tfanout--;\n+\t}\n+\tmemcpy(path + i, hex_sha1 + j, 40 - j);\n+\tpath[i + 40 - j] = '\\0';\n+}\n+\n+static uintmax_t do_change_note_fanout(\n+\t\tstruct tree_entry *orig_root, struct tree_entry *root,\n+\t\tchar *hex_sha1, unsigned int hex_sha1_len,\n+\t\tchar *fullpath, unsigned int fullpath_len,\n+\t\tunsigned char fanout)\n+{\n+\tstruct tree_content *t = root->tree;\n+\tstruct tree_entry *e, leaf;\n+\tunsigned int i, tmp_hex_sha1_len, tmp_fullpath_len;\n+\tuintmax_t num_notes = 0;\n+\tunsigned char sha1[20];\n+\tchar realpath[60];\n+\n+\tfor (i = 0; t && i < t->entry_count; i++) {\n+\t\te = t->entries[i];\n+\t\ttmp_hex_sha1_len = hex_sha1_len + e->name->str_len;\n+\t\ttmp_fullpath_len = fullpath_len;\n+\n+\t\t/*\n+\t\t * We're interested in EITHER existing note entries (entries\n+\t\t * with exactly 40 hex chars in path, not including directory\n+\t\t * separators), OR directory entries that may contain note\n+\t\t * entries (with < 40 hex chars in path).\n+\t\t * Also, each path component in a note entry must be a multiple\n+\t\t * of 2 chars.\n+\t\t */\n+\t\tif (!e->versions[1].mode ||\n+\t\t tmp_hex_sha1_len > 40 ||\n+\t\t e->name->str_len % 2)\n+\t\t\tcontinue;\n+\n+\t\t/* This _may_ be a note entry, or a subdir containing notes */\n+\t\tmemcpy(hex_sha1 + hex_sha1_len, e->name->str_dat,\n+\t\t e->name->str_len);\n+\t\tif (tmp_fullpath_len)\n+\t\t\tfullpath[tmp_fullpath_len++] = '/';\n+\t\tmemcpy(fullpath + tmp_fullpath_len, e->name->str_dat,\n+\t\t e->name->str_len);\n+\t\ttmp_fullpath_len += e->name->str_len;\n+\t\tfullpath[tmp_fullpath_len] = '\\0';\n+\n+\t\tif (tmp_hex_sha1_len == 40 && !get_sha1_hex(hex_sha1, sha1)) {\n+\t\t\t/* This is a note entry */\n+\t\t\tconstruct_path_with_fanout(hex_sha1, fanout, realpath);\n+\t\t\tif (!strcmp(fullpath, realpath)) {\n+\t\t\t\t/* Note entry is in correct location */\n+\t\t\t\tnum_notes++;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\t/* Rename fullpath to realpath */\n+\t\t\tif (!tree_content_remove(orig_root, fullpath, &leaf))\n+\t\t\t\tdie(\"Failed to remove path %s\", fullpath);\n+\t\t\ttree_content_set(orig_root, realpath,\n+\t\t\t\tleaf.versions[1].sha1,\n+\t\t\t\tleaf.versions[1].mode,\n+\t\t\t\tleaf.tree);\n+\t\t} else if (S_ISDIR(e->versions[1].mode)) {\n+\t\t\t/* This is a subdir that may contain note entries */\n+\t\t\tif (!e->tree)\n+\t\t\t\tload_tree(e);\n+\t\t\tnum_notes += do_change_note_fanout(orig_root, e,\n+\t\t\t\thex_sha1, tmp_hex_sha1_len,\n+\t\t\t\tfullpath, tmp_fullpath_len, fanout);\n+\t\t}\n+\n+\t\t/* The above may have reallocated the current tree_content */\n+\t\tt = root->tree;\n+\t}\n+\treturn num_notes;\n+}\n+\n+static uintmax_t change_note_fanout(struct tree_entry *root,\n+\t\tunsigned char fanout)\n+{\n+\tchar hex_sha1[40], path[60];\n+\treturn do_change_note_fanout(root, root, hex_sha1, 0, path, 0, fanout);\n+}\n+\n static void file_change_m(struct branch *b)\n {\n \tconst char *p = command_buf.buf + 2;\n@@ -2010,14 +2115,16 @@ static void file_change_cr(struct branch *b, int rename)\n \t\tleaf.tree);\n }\n\n-static void note_change_n(struct branch *b)\n+static void note_change_n(struct branch *b, unsigned char old_fanout)\n {\n \tconst char *p = command_buf.buf + 2;\n \tstatic struct strbuf uq = STRBUF_INIT;\n \tstruct object_entry *oe = oe;\n \tstruct branch *s;\n \tunsigned char sha1[20], commit_sha1[20];\n+\tchar path[60];\n \tuint16_t inline_data = 0;\n+\tunsigned char new_fanout;\n\n \t/* or 'inline' */\n \tif (*p == ':') {\n@@ -2071,7 +2178,7 @@ static void note_change_n(struct branch *b)\n \t\tif (oe->type != OBJ_BLOB)\n \t\t\tdie(\"Not a blob (actually a %s): %s\",\n \t\t\t\ttypename(oe->type), command_buf.buf);\n-\t} else {\n+\t} else if (!is_null_sha1(sha1)) {\n \t\tenum object_type type = sha1_object_info(sha1, NULL);\n \t\tif (type < 0)\n \t\t\tdie(\"Blob not found: %s\", command_buf.buf);\n@@ -2080,8 +2187,17 @@ static void note_change_n(struct branch *b)\n \t\t\t typename(type), command_buf.buf);\n \t}\n\n-\ttree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,\n-\t\tS_IFREG | 0644, NULL);\n+\tconstruct_path_with_fanout(sha1_to_hex(commit_sha1), old_fanout, path);\n+\tif (tree_content_remove(&b->branch_tree, path, NULL))\n+\t\tb->num_notes--;\n+\n+\tif (is_null_sha1(sha1))\n+\t\treturn; /* nothing to insert */\n+\n+\tb->num_notes++;\n+\tnew_fanout = convert_num_notes_to_fanout(b->num_notes);\n+\tconstruct_path_with_fanout(sha1_to_hex(commit_sha1), new_fanout, path);\n+\ttree_content_set(&b->branch_tree, path, sha1, S_IFREG | 0644, NULL);\n }\n\n static void file_change_deleteall(struct branch *b)\n@@ -2090,6 +2206,7 @@ static void file_change_deleteall(struct branch *b)\n \thashclr(b->branch_tree.versions[0].sha1);\n \thashclr(b->branch_tree.versions[1].sha1);\n \tload_tree(&b->branch_tree);\n+\tb->num_notes = 0;\n }\n\n static void parse_from_commit(struct branch *b, char *buf, unsigned long size)\n@@ -2213,6 +2330,7 @@ static void parse_new_commit(void)\n \tchar *committer = NULL;\n \tstruct hash_list *merge_list = NULL;\n \tunsigned int merge_count;\n+\tunsigned char prev_fanout, new_fanout;\n\n \t/* Obtain the branch name from the rest of our command */\n \tsp = strchr(command_buf.buf, ' ') + 1;\n@@ -2243,6 +2361,8 @@ static void parse_new_commit(void)\n \t\tload_branch(b);\n \t}\n\n+\tprev_fanout = convert_num_notes_to_fanout(b->num_notes);\n+\n \t/* file_change* */\n \twhile (command_buf.len > 0) {\n \t\tif (!prefixcmp(command_buf.buf, \"M \"))\n@@ -2254,7 +2374,7 @@ static void parse_new_commit(void)\n \t\telse if (!prefixcmp(command_buf.buf, \"C \"))\n \t\t\tfile_change_cr(b, 0);\n \t\telse if (!prefixcmp(command_buf.buf, \"N \"))\n-\t\t\tnote_change_n(b);\n+\t\t\tnote_change_n(b, prev_fanout);\n \t\telse if (!strcmp(\"deleteall\", command_buf.buf))\n \t\t\tfile_change_deleteall(b);\n \t\telse {\n@@ -2265,6 +2385,10 @@ static void parse_new_commit(void)\n \t\t\tbreak;\n \t}\n\n+\tnew_fanout = convert_num_notes_to_fanout(b->num_notes);\n+\tif (new_fanout != prev_fanout)\n+\t\tb->num_notes = change_note_fanout(&b->branch_tree, new_fanout);\n+\n \t/* build the tree and the commit */\n \tstore_tree(&b->branch_tree);\n \thashcpy(b->branch_tree.versions[0].sha1,\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex b49815d..bf8c509 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -1092,9 +1092,12 @@ test_expect_success 'P: fail on blob mark in gitlink' '\n ### series Q (notes)\n ###\n\n-note1_data=\"Note for the first commit\"\n-note2_data=\"Note for the second commit\"\n-note3_data=\"Note for the third commit\"\n+note1_data=\"The first note for the first commit\"\n+note2_data=\"The first note for the second commit\"\n+note3_data=\"The first note for the third commit\"\n+note1b_data=\"The second note for the first commit\"\n+note1c_data=\"The third note for the first commit\"\n+note2b_data=\"The second note for the second commit\"\n\n test_tick\n cat >input < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n notes (:9)\n EOF\n test_expect_success \\\n-\t'Q: verify notes commit' \\\n-\t'git cat-file commit refs/notes/foobar | sed 1d >actual &&\n+\t'Q: verify first notes commit' \\\n+\t'git cat-file commit refs/notes/foobar~2 | sed 1d >actual &&\n \ttest_cmp expect actual'\n\n cat >expect.unsorted <expect.unsorted <expect\n test_expect_success \\\n-\t'Q: verify notes tree' \\\n-\t'git cat-file -p refs/notes/foobar^{tree} | sed \"s/ [0-9a-f]*\t/ /\" >actual &&\n+\t'Q: verify first notes tree' \\\n+\t'git cat-file -p refs/notes/foobar~2^{tree} | sed \"s/ [0-9a-f]*\t/ /\" >actual &&\n \t test_cmp expect actual'\n\n echo \"$note1_data\" >expect\n test_expect_success \\\n-\t'Q: verify note for first commit' \\\n-\t'git cat-file blob refs/notes/foobar:$commit1 >actual && test_cmp expect actual'\n+\t'Q: verify first note for first commit' \\\n+\t'git cat-file blob refs/notes/foobar~2:$commit1 >actual && test_cmp expect actual'\n\n echo \"$note2_data\" >expect\n test_expect_success \\\n-\t'Q: verify note for second commit' \\\n-\t'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'\n+\t'Q: verify first note for second commit' \\\n+\t'git cat-file blob refs/notes/foobar~2:$commit2 >actual && test_cmp expect actual'\n+\n+echo \"$note3_data\" >expect\n+test_expect_success \\\n+\t'Q: verify first note for third commit' \\\n+\t'git cat-file blob refs/notes/foobar~2:$commit3 >actual && test_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+notes (:10)\n+EOF\n+test_expect_success \\\n+\t'Q: verify second notes commit' \\\n+\t'git cat-file commit refs/notes/foobar^ | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect.unsorted <expect\n+test_expect_success \\\n+\t'Q: verify second notes tree' \\\n+\t'git cat-file -p refs/notes/foobar^^{tree} | sed \"s/ [0-9a-f]*\t/ /\" >actual &&\n+\t test_cmp expect actual'\n+\n+echo \"$note1b_data\" >expect\n+test_expect_success \\\n+\t'Q: verify second note for first commit' \\\n+\t'git cat-file blob refs/notes/foobar^:$commit1 >actual && test_cmp expect actual'\n+\n+echo \"$note2_data\" >expect\n+test_expect_success \\\n+\t'Q: verify first note for second commit' \\\n+\t'git cat-file blob refs/notes/foobar^:$commit2 >actual && test_cmp expect actual'\n\n echo \"$note3_data\" >expect\n test_expect_success \\\n-\t'Q: verify note for third commit' \\\n-\t'git cat-file blob refs/notes/foobar:$commit3 >actual && test_cmp expect actual'\n+\t'Q: verify first note for third commit' \\\n+\t'git cat-file blob refs/notes/foobar^:$commit3 >actual && test_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+notes (:11)\n+EOF\n+test_expect_success \\\n+\t'Q: verify third notes commit' \\\n+\t'git cat-file commit refs/notes/foobar2 | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect.unsorted <expect\n+test_expect_success \\\n+\t'Q: verify third notes tree' \\\n+\t'git cat-file -p refs/notes/foobar2^{tree} | sed \"s/ [0-9a-f]*\t/ /\" >actual &&\n+\t test_cmp expect actual'\n+\n+echo \"$note1c_data\" >expect\n+test_expect_success \\\n+\t'Q: verify third note for first commit' \\\n+\t'git cat-file blob refs/notes/foobar2:$commit1 >actual && test_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+notes (:12)\n+EOF\n+test_expect_success \\\n+\t'Q: verify fourth notes commit' \\\n+\t'git cat-file commit refs/notes/foobar | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect.unsorted <expect\n+test_expect_success \\\n+\t'Q: verify fourth notes tree' \\\n+\t'git cat-file -p refs/notes/foobar^{tree} | sed \"s/ [0-9a-f]*\t/ /\" >actual &&\n+\t test_cmp expect actual'\n+\n+echo \"$note2b_data\" >expect\n+test_expect_success \\\n+\t'Q: verify second note for second commit' \\\n+\t'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'\n\n test_done\n--\n1.6.5.3.433.g11067\n"},{"id":"129407","messageId":"1260185254-1523-3-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 02/11] Rename t9301 to t9350, to make room for more fast-import tests","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:25Z","receivedAt":"2009-12-07T11:27:25Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Signed-off-by: Johan Herland \n---\n t/{t9301-fast-export.sh => t9350-fast-export.sh} | 0\n 1 files changed, 0 insertions(+), 0 deletions(-)\n rename t/{t9301-fast-export.sh => t9350-fast-export.sh} (100%)\n\ndiff --git a/t/t9301-fast-export.sh b/t/t9350-fast-export.sh\nsimilarity index 100%\nrename from t/t9301-fast-export.sh\nrename to t/t9350-fast-export.sh\n-- \n1.6.5.3.433.g11067\n"},{"id":"129406","messageId":"1260185254-1523-4-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 03/11] Add more testcases to test fast-import of notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:26Z","receivedAt":"2009-12-07T11:27:26Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This patch adds testcases verifying correct behaviour in several scenarios\nregarding fast-import of notes:\n- using a mixture of 'N' and 'M' commands\n- updating existing notes\n- concatenation of notes\n- 'deleteall' also removes notes\n- fanout schemes is added/removed when needed\n- git-fast-import's branch unload/reload preserves notes\n- non-notes are not clobbered in the presence of notes\n\nSigned-off-by: Johan Herland \n---\n t/t9301-fast-import-notes.sh | 623 ++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 623 insertions(+), 0 deletions(-)\n create mode 100755 t/t9301-fast-import-notes.sh\n\ndiff --git a/t/t9301-fast-import-notes.sh b/t/t9301-fast-import-notes.sh\nnew file mode 100755\nindex 0000000..a5c99d8\n--- /dev/null\n+++ b/t/t9301-fast-import-notes.sh\n@@ -0,0 +1,623 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2009 Johan Herland\n+#\n+\n+test_description='test git fast-import of notes objects'\n+. ./test-lib.sh\n+\n+\n+test_tick\n+cat >input < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data <input < $GIT_COMMITTER_DATE\n+data <expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_tick\n+cat >input < $GIT_COMMITTER_DATE\n+data <expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_tick\n+cat >input < $GIT_COMMITTER_DATE\n+data <expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_tick\n+cat >input < $GIT_COMMITTER_DATE\n+data <expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_tick\n+cat >input < $GIT_COMMITTER_DATE\n+data <expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_tick\n+cat >input < $GIT_COMMITTER_DATE\n+data <expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+# Write fast-import commands to create the given number of commits\n+fast_import_commits () {\n+\tmy_ref=$1\n+\tmy_num_commits=$2\n+\tmy_append_to_file=$3\n+\tmy_i=0\n+\twhile test $my_i -lt $my_num_commits\n+\tdo\n+\t\tmy_i=$(($my_i + 1))\n+\t\ttest_tick\n+\t\tcat >>\"$my_append_to_file\" < $GIT_COMMITTER_DATE\n+data <>\"$my_append_to_file\" < $GIT_COMMITTER_DATE\n+data <>\"$my_append_to_file\" <>input < $GIT_COMMITTER_DATE\n+data <>expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_expect_success 'verify that lots of notes trigger a fanout scheme' '\n+\n+\t# None of the entries in the top-level notes tree should be a full SHA1\n+\tgit ls-tree --name-only refs/notes/many_notes |\n+\twhile read path\n+\tdo\n+\t\tif test $(expr length \"$path\") -ge 40\n+\t\tthen\n+\t\t\treturn 1\n+\t\tfi\n+\tdone\n+\n+'\n+\n+cat >>expect_non-note1 << EOF\n+This is not a note, but rather a regular file residing in a notes tree\n+EOF\n+\n+cat >>expect_non-note2 << EOF\n+Non-note file\n+EOF\n+\n+cat >>expect_non-note3 << EOF\n+Another non-note file\n+EOF\n+\n+test_expect_success 'verify that non-notes are untouched by a fanout change' '\n+\n+\tgit cat-file -p refs/notes/many_notes:foobar/non-note.txt > actual &&\n+\ttest_cmp expect_non-note1 actual &&\n+\tgit cat-file -p refs/notes/many_notes:deadbeef > actual &&\n+\ttest_cmp expect_non-note2 actual &&\n+\tgit cat-file -p refs/notes/many_notes:de/adbeef > actual &&\n+\ttest_cmp expect_non-note3 actual\n+\n+'\n+remaining_notes=10\n+test_tick\n+cat >>input < $GIT_COMMITTER_DATE\n+data <>input <>expect <>expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_expect_success 'verify that removing notes trigger fanout consolidation' '\n+\n+\t# All entries in the top-level notes tree should be a full SHA1\n+\tgit ls-tree --name-only -r refs/notes/many_notes |\n+\twhile read path\n+\tdo\n+\t\t# Explicitly ignore the non-note paths\n+\t\ttest \"$path\" = \"foobar/non-note.txt\" && continue\n+\t\ttest \"$path\" = \"deadbeef\" && continue\n+\t\ttest \"$path\" = \"de/adbeef\" && continue\n+\n+\t\tif test $(expr length \"$path\") -ne 40\n+\t\tthen\n+\t\t\treturn 1\n+\t\tfi\n+\tdone\n+\n+'\n+\n+test_expect_success 'verify that non-notes are untouched by a fanout change' '\n+\n+\tgit cat-file -p refs/notes/many_notes:foobar/non-note.txt > actual &&\n+\ttest_cmp expect_non-note1 actual &&\n+\tgit cat-file -p refs/notes/many_notes:deadbeef > actual &&\n+\ttest_cmp expect_non-note2 actual &&\n+\tgit cat-file -p refs/notes/many_notes:de/adbeef > actual &&\n+\ttest_cmp expect_non-note3 actual\n+\n+'\n+\n+\n+rm input expect\n+num_notes_refs=10\n+num_commits=16\n+some_commits=8\n+# Create commits\n+fast_import_commits \"refs/heads/more_commits\" $num_commits input\n+# Create one note per above commit per notes ref\n+i=0\n+while test $i -lt $num_notes_refs\n+do\n+\ti=$(($i + 1))\n+\tfast_import_notes \"refs/notes/more_notes_$i\" $num_commits input\n+done\n+# Trigger branch reloading in git-fast-import by repeating the note creation\n+i=0\n+while test $i -lt $num_notes_refs\n+do\n+\ti=$(($i + 1))\n+\tfast_import_notes \"refs/notes/more_notes_$i\" $some_commits input \" (2)\"\n+done\n+# Finally create the expected output from the notes in refs/notes/more_notes_1\n+i=$num_commits\n+while test $i -gt 0\n+do\n+\tnote_data=\"note for commit #$i\"\n+\tif test $i -le $some_commits\n+\tthen\n+\t\tnote_data=\"$note_data (2)\"\n+\tfi\n+\tcat >>expect < actual &&\n+\ttest_cmp expect actual\n+\n+'\n+\n+test_done\n-- \n1.6.5.3.433.g11067\n"},{"id":"129408","messageId":"1260185254-1523-5-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 04/11] Minor style fixes to notes.c","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:27Z","receivedAt":"2009-12-07T11:27:27Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Signed-off-by: Johan Herland \n---\n notes.c | 6 +++---\n 1 files changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 023adce..57d5cdc 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -93,7 +93,7 @@ static void **note_tree_search(struct int_node **tree,\n \n \ti = GET_NIBBLE(*n, key_sha1);\n \tp = (*tree)->a[i];\n-\tswitch(GET_PTR_TYPE(p)) {\n+\tswitch (GET_PTR_TYPE(p)) {\n \tcase PTR_TYPE_INTERNAL:\n \t\t*tree = CLR_PTR_TYPE(p);\n \t\t(*n)++;\n@@ -195,7 +195,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,\n \n \tassert(GET_PTR_TYPE(entry) == 0); /* no type bits set */\n \tl = (struct leaf_node *) CLR_PTR_TYPE(*p);\n-\tswitch(GET_PTR_TYPE(*p)) {\n+\tswitch (GET_PTR_TYPE(*p)) {\n \tcase PTR_TYPE_NULL:\n \t\tassert(!*p);\n \t\t*p = SET_PTR_TYPE(entry, type);\n@@ -257,7 +257,7 @@ static void note_tree_free(struct int_node *tree)\n \tunsigned int i;\n \tfor (i = 0; i < 16; i++) {\n \t\tvoid *p = tree->a[i];\n-\t\tswitch(GET_PTR_TYPE(p)) {\n+\t\tswitch (GET_PTR_TYPE(p)) {\n \t\tcase PTR_TYPE_INTERNAL:\n \t\t\tnote_tree_free(CLR_PTR_TYPE(p));\n \t\t\t/* fall through */\n-- \n1.6.5.3.433.g11067\n"},{"id":"129410","messageId":"1260185254-1523-6-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 05/11] Notes API: get_commit_notes() -> format_note() + remove the commit restriction","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:28Z","receivedAt":"2009-12-07T11:27:28Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"There is really no reason why only commit objects can be annotated. By\nchanging the struct commit parameter to get_commit_notes() into a sha1 we\ngain the ability to annotate any object type. To reflect this in the function\nnaming as well, we rename get_commit_notes() to format_note().\n\nThis patch also fixes comments and variable names throughout notes.c as a\nconsequence of the removal of the unnecessary 'commit' restriction.\n\nSigned-off-by: Johan Herland \n---\n notes.c | 33 ++++++++++++++++-----------------\n notes.h | 11 ++++++++++-\n pretty.c | 8 ++++----\n 3 files changed, 30 insertions(+), 22 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 57d5cdc..5590414 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -1,5 +1,4 @@\n #include \"cache.h\"\n-#include \"commit.h\"\n #include \"notes.h\"\n #include \"refs.h\"\n #include \"utf8.h\"\n@@ -25,10 +24,10 @@ struct int_node {\n /*\n * Leaf nodes come in two variants, note entries and subtree entries,\n * distinguished by the LSb of the leaf node pointer (see above).\n- * As a note entry, the key is the SHA1 of the referenced commit, and the\n+ * As a note entry, the key is the SHA1 of the referenced object, and the\n * value is the SHA1 of the note object.\n * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the\n- * referenced commit, using the last byte of the key to store the length of\n+ * referenced object, using the last byte of the key to store the length of\n * the prefix. The value is the SHA1 of the tree object containing the notes\n * subtree.\n */\n@@ -211,7 +210,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,\n \t\t\t\tif (concatenate_notes(l->val_sha1,\n \t\t\t\t\t\tentry->val_sha1))\n \t\t\t\t\tdie(\"failed to concatenate note %s \"\n-\t\t\t\t\t \"into note %s for commit %s\",\n+\t\t\t\t\t \"into note %s for object %s\",\n \t\t\t\t\t sha1_to_hex(entry->val_sha1),\n \t\t\t\t\t sha1_to_hex(l->val_sha1),\n \t\t\t\t\t sha1_to_hex(l->key_sha1));\n@@ -299,7 +298,7 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,\n static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \t\tunsigned int n)\n {\n-\tunsigned char commit_sha1[20];\n+\tunsigned char object_sha1[20];\n \tunsigned int prefix_len;\n \tvoid *buf;\n \tstruct tree_desc desc;\n@@ -312,23 +311,23 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \n \tprefix_len = subtree->key_sha1[19];\n \tassert(prefix_len * 2 >= n);\n-\tmemcpy(commit_sha1, subtree->key_sha1, prefix_len);\n+\tmemcpy(object_sha1, subtree->key_sha1, prefix_len);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tint len = get_sha1_hex_segment(entry.path, strlen(entry.path),\n-\t\t\t\tcommit_sha1 + prefix_len, 20 - prefix_len);\n+\t\t\t\tobject_sha1 + prefix_len, 20 - prefix_len);\n \t\tif (len < 0)\n \t\t\tcontinue; /* entry.path is not a SHA1 sum. Skip */\n \t\tlen += prefix_len;\n \n \t\t/*\n-\t\t * If commit SHA1 is complete (len == 20), assume note object\n-\t\t * If commit SHA1 is incomplete (len < 20), assume note subtree\n+\t\t * If object SHA1 is complete (len == 20), assume note object\n+\t\t * If object SHA1 is incomplete (len < 20), assume note subtree\n \t\t */\n \t\tif (len <= 20) {\n \t\t\tunsigned char type = PTR_TYPE_NOTE;\n \t\t\tstruct leaf_node *l = (struct leaf_node *)\n \t\t\t\txcalloc(sizeof(struct leaf_node), 1);\n-\t\t\thashcpy(l->key_sha1, commit_sha1);\n+\t\t\thashcpy(l->key_sha1, object_sha1);\n \t\t\thashcpy(l->val_sha1, entry.sha1);\n \t\t\tif (len < 20) {\n \t\t\t\tif (!S_ISDIR(entry.mode))\n@@ -344,12 +343,12 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \n static void initialize_notes(const char *notes_ref_name)\n {\n-\tunsigned char sha1[20], commit_sha1[20];\n+\tunsigned char sha1[20], object_sha1[20];\n \tunsigned mode;\n \tstruct leaf_node root_tree;\n \n-\tif (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||\n-\t get_tree_entry(commit_sha1, \"\", sha1, &mode))\n+\tif (!notes_ref_name || read_ref(notes_ref_name, object_sha1) ||\n+\t get_tree_entry(object_sha1, \"\", sha1, &mode))\n \t\treturn;\n \n \thashclr(root_tree.key_sha1);\n@@ -357,9 +356,9 @@ static void initialize_notes(const char *notes_ref_name)\n \tload_subtree(&root_tree, &root_node, 0);\n }\n \n-static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n+static unsigned char *lookup_notes(const unsigned char *object_sha1)\n {\n-\tstruct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);\n+\tstruct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);\n \tif (found)\n \t\treturn found->val_sha1;\n \treturn NULL;\n@@ -372,7 +371,7 @@ void free_notes(void)\n \tinitialized = 0;\n }\n \n-void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n+void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n \t\tconst char *output_encoding, int flags)\n {\n \tstatic const char utf8[] = \"utf-8\";\n@@ -391,7 +390,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n \t\tinitialized = 1;\n \t}\n \n-\tsha1 = lookup_notes(commit->object.sha1);\n+\tsha1 = lookup_notes(object_sha1);\n \tif (!sha1)\n \t\treturn;\n \ndiff --git a/notes.h b/notes.h\nindex a1421e3..d745ed1 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -4,10 +4,19 @@\n /* Free (and de-initialize) the internal notes tree structure */\n void free_notes(void);\n \n+/* Flags controlling how notes are formatted */\n #define NOTES_SHOW_HEADER 1\n #define NOTES_INDENT 2\n \n-void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n+/*\n+ * Fill the given strbuf with the notes associated with the given object.\n+ *\n+ * If the internal notes structure is not initialized, it will be auto-\n+ * initialized to the default value (see documentation for init_notes() above).\n+ *\n+ * 'flags' is a bitwise combination of the above formatting flags.\n+ */\n+void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n \t\tconst char *output_encoding, int flags);\n \n #endif\ndiff --git a/pretty.c b/pretty.c\nindex 8f5bd1a..fe77090 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -775,8 +775,8 @@ static size_t format_commit_one(struct strbuf *sb, const char *placeholder,\n \t\t}\n \t\treturn 0;\t/* unknown %g placeholder */\n \tcase 'N':\n-\t\tget_commit_notes(commit, sb, git_log_output_encoding ?\n-\t\t\t git_log_output_encoding : git_commit_encoding, 0);\n+\t\tformat_note(commit->object.sha1, sb, git_log_output_encoding ?\n+\t\t\t git_log_output_encoding : git_commit_encoding, 0);\n \t\treturn 1;\n \t}\n \n@@ -1095,8 +1095,8 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,\n \t\tstrbuf_addch(sb, '\\n');\n \n \tif (fmt != CMIT_FMT_ONELINE)\n-\t\tget_commit_notes(commit, sb, encoding,\n-\t\t\t\t NOTES_SHOW_HEADER | NOTES_INDENT);\n+\t\tformat_note(commit->object.sha1, sb, encoding,\n+\t\t\t NOTES_SHOW_HEADER | NOTES_INDENT);\n \n \tfree(reencoded);\n }\n-- \n1.6.5.3.433.g11067\n"},{"id":"129412","messageId":"1260185254-1523-7-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 06/11] Notes API: init_notes(): Initialize the notes tree from the given notes ref","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:29Z","receivedAt":"2009-12-07T11:27:29Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Created by a simple refactoring of initialize_notes().\n\nAlso add a new 'flags' parameter, which is a bitwise combination of notes\ninitialization flags. For now, there is only one flag - NOTES_INIT_EMPTY -\nwhich indicates that the notes tree should not auto-load the contents of\nthe given (or default) notes ref, but rather should leave the notes tree\ninitialized to an empty state. This will become useful in the future when\nmanipulating the notes tree through the notes API.\n\nSigned-off-by: Johan Herland \n---\n notes.c | 27 ++++++++++++++++-----------\n notes.h | 20 ++++++++++++++++++++\n 2 files changed, 36 insertions(+), 11 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 5590414..e0dfa24 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -341,13 +341,25 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \tfree(buf);\n }\n \n-static void initialize_notes(const char *notes_ref_name)\n+void init_notes(const char *notes_ref, int flags)\n {\n \tunsigned char sha1[20], object_sha1[20];\n \tunsigned mode;\n \tstruct leaf_node root_tree;\n \n-\tif (!notes_ref_name || read_ref(notes_ref_name, object_sha1) ||\n+\tassert(!initialized);\n+\tinitialized = 1;\n+\n+\tif (!notes_ref) {\n+\t\tconst char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);\n+\t\tif (env)\n+\t\t\tnotes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);\n+\t\telse\n+\t\t\tnotes_ref = GIT_NOTES_DEFAULT_REF;\n+\t}\n+\n+\tif (flags & NOTES_INIT_EMPTY || !notes_ref ||\n+\t read_ref(notes_ref, object_sha1) ||\n \t get_tree_entry(object_sha1, \"\", sha1, &mode))\n \t\treturn;\n \n@@ -380,15 +392,8 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n \tunsigned long linelen, msglen;\n \tenum object_type type;\n \n-\tif (!initialized) {\n-\t\tconst char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);\n-\t\tif (env)\n-\t\t\tnotes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);\n-\t\telse if (!notes_ref_name)\n-\t\t\tnotes_ref_name = GIT_NOTES_DEFAULT_REF;\n-\t\tinitialize_notes(notes_ref_name);\n-\t\tinitialized = 1;\n-\t}\n+\tif (!initialized)\n+\t\tinit_notes(NULL, 0);\n \n \tsha1 = lookup_notes(object_sha1);\n \tif (!sha1)\ndiff --git a/notes.h b/notes.h\nindex d745ed1..6b52799 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -1,6 +1,26 @@\n #ifndef NOTES_H\n #define NOTES_H\n \n+/*\n+ * Flags controlling behaviour of notes tree initialization\n+ *\n+ * Default behaviour is to initialize the notes tree from the tree object\n+ * specified by the given (or default) notes ref.\n+ */\n+#define NOTES_INIT_EMPTY 1\n+\n+/*\n+ * Initialize internal notes tree structure with the notes tree at the given\n+ * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment\n+ * variable is used, and if that is missing, the default notes ref is used\n+ * (\"refs/notes/commits\").\n+ *\n+ * If you need to re-intialize the internal notes tree structure (e.g. loading\n+ * from a different notes ref), please first de-initialize the current notes\n+ * tree by calling free_notes().\n+ */\n+void init_notes(const char *notes_ref, int flags);\n+\n /* Free (and de-initialize) the internal notes tree structure */\n void free_notes(void);\n \n-- \n1.6.5.3.433.g11067\n"},{"id":"129414","messageId":"1260185254-1523-8-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 07/11] Notes API: add_note(): Add note objects to the internal notes tree structure","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:30Z","receivedAt":"2009-12-07T11:27:30Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Signed-off-by: Johan Herland \n---\n notes.c | 11 +++++++++++\n notes.h | 4 ++++\n 2 files changed, 15 insertions(+), 0 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex e0dfa24..79bfa24 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -368,6 +368,17 @@ void init_notes(const char *notes_ref, int flags)\n \tload_subtree(&root_tree, &root_node, 0);\n }\n \n+void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)\n+{\n+\tstruct leaf_node *l;\n+\n+\tassert(initialized);\n+\tl = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));\n+\thashcpy(l->key_sha1, object_sha1);\n+\thashcpy(l->val_sha1, note_sha1);\n+\tnote_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);\n+}\n+\n static unsigned char *lookup_notes(const unsigned char *object_sha1)\n {\n \tstruct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);\ndiff --git a/notes.h b/notes.h\nindex 6b52799..5f22852 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -21,6 +21,10 @@\n */\n void init_notes(const char *notes_ref, int flags);\n \n+/* Add the given note object to the internal notes tree structure */\n+void add_note(const unsigned char *object_sha1,\n+\t\tconst unsigned char *note_sha1);\n+\n /* Free (and de-initialize) the internal notes tree structure */\n void free_notes(void);\n \n-- \n1.6.5.3.433.g11067\n"},{"id":"129411","messageId":"1260185254-1523-9-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 08/11] Notes API: get_note(): Return the note annotating the given object","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:31Z","receivedAt":"2009-12-07T11:27:31Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Created by a simple cleanup and rename of lookup_notes().\n\nSigned-off-by: Johan Herland \n---\n notes.c | 15 ++++++++-------\n notes.h | 3 +++\n 2 files changed, 11 insertions(+), 7 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 79bfa24..110404a 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -379,12 +379,13 @@ void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)\n \tnote_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);\n }\n \n-static unsigned char *lookup_notes(const unsigned char *object_sha1)\n+const unsigned char *get_note(const unsigned char *object_sha1)\n {\n-\tstruct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);\n-\tif (found)\n-\t\treturn found->val_sha1;\n-\treturn NULL;\n+\tstruct leaf_node *found;\n+\n+\tassert(initialized);\n+\tfound = note_tree_find(&root_node, 0, object_sha1);\n+\treturn found ? found->val_sha1 : NULL;\n }\n \n void free_notes(void)\n@@ -398,7 +399,7 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n \t\tconst char *output_encoding, int flags)\n {\n \tstatic const char utf8[] = \"utf-8\";\n-\tunsigned char *sha1;\n+\tconst unsigned char *sha1;\n \tchar *msg, *msg_p;\n \tunsigned long linelen, msglen;\n \tenum object_type type;\n@@ -406,7 +407,7 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n \tif (!initialized)\n \t\tinit_notes(NULL, 0);\n \n-\tsha1 = lookup_notes(object_sha1);\n+\tsha1 = get_note(object_sha1);\n \tif (!sha1)\n \t\treturn;\n \ndiff --git a/notes.h b/notes.h\nindex 5f22852..21a8930 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -25,6 +25,9 @@ void init_notes(const char *notes_ref, int flags);\n void add_note(const unsigned char *object_sha1,\n \t\tconst unsigned char *note_sha1);\n \n+/* Get the note object SHA1 containing the note data for the given object */\n+const unsigned char *get_note(const unsigned char *object_sha1);\n+\n /* Free (and de-initialize) the internal notes tree structure */\n void free_notes(void);\n \n-- \n1.6.5.3.433.g11067\n"},{"id":"129409","messageId":"1260185254-1523-10-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 09/11] Notes API: for_each_note(): Traverse the entire notes tree with a callback","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:32Z","receivedAt":"2009-12-07T11:27:32Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This includes a first attempt at creating an optimal fanout scheme (which\nis calculated on-the-fly, while traversing).\n\nSigned-off-by: Johan Herland \n---\n notes.c | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n notes.h | 17 ++++++++++\n 2 files changed, 118 insertions(+), 0 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 110404a..de5a847 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -341,6 +341,101 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \tfree(buf);\n }\n \n+/*\n+ * Determine optimal on-disk fanout for this part of the notes tree\n+ *\n+ * Given a (sub)tree and the level in the internal tree structure, determine\n+ * whether or not the given existing fanout should be expanded for this\n+ * (sub)tree.\n+ *\n+ * Values of the 'fanout' variable:\n+ * - 0: No fanout (all notes are stored directly in the root notes tree)\n+ * - 1: 2/38 fanout\n+ * - 2: 2/2/36 fanout\n+ * - 3: 2/2/2/34 fanout\n+ * etc.\n+ */\n+static unsigned char determine_fanout(struct int_node *tree, unsigned char n,\n+\t\tunsigned char fanout)\n+{\n+\t/*\n+\t * The following is a simple heuristic that works well in practice:\n+\t * For each even-numbered 16-tree level (remember that each on-disk\n+\t * fanout level corresponds to two 16-tree levels), peek at all 16\n+\t * entries at that tree level. If any of them are subtree entries, then\n+\t * there are likely plenty of notes below this level, so we return an\n+\t * incremented fanout immediately. Otherwise, we return an incremented\n+\t * fanout only if all of the entries at this level are int_nodes.\n+\t */\n+\tunsigned int i;\n+\tif ((n % 2) || (n > 2 * fanout))\n+\t\treturn fanout;\n+\tfor (i = 0; i < 16; i++) {\n+\t\tswitch (GET_PTR_TYPE(tree->a[i])) {\n+\t\tcase PTR_TYPE_SUBTREE:\n+\t\t\treturn fanout + 1;\n+\t\tcase PTR_TYPE_INTERNAL:\n+\t\t\tcontinue;\n+\t\tdefault:\n+\t\t\treturn fanout;\n+\t\t}\n+\t}\n+\treturn fanout + 1;\n+}\n+\n+static void construct_path_with_fanout(const unsigned char *sha1,\n+\t\tunsigned char fanout, char *path)\n+{\n+\tunsigned int i = 0, j = 0;\n+\tconst char *hex_sha1 = sha1_to_hex(sha1);\n+\tassert(fanout < 20);\n+\twhile (fanout) {\n+\t\tpath[i++] = hex_sha1[j++];\n+\t\tpath[i++] = hex_sha1[j++];\n+\t\tpath[i++] = '/';\n+\t\tfanout--;\n+\t}\n+\tstrcpy(path + i, hex_sha1 + j);\n+}\n+\n+static int for_each_note_helper(struct int_node *tree, unsigned char n,\n+\t\tunsigned char fanout, each_note_fn fn, void *cb_data)\n+{\n+\tunsigned int i;\n+\tvoid *p;\n+\tint ret = 0;\n+\tstruct leaf_node *l;\n+\tstatic char path[40 + 19 + 1]; /* hex SHA1 + 19 * '/' + NUL */\n+\n+\tfanout = determine_fanout(tree, n, fanout);\n+\tfor (i = 0; i < 16; i++) {\n+redo:\n+\t\tp = tree->a[i];\n+\t\tswitch (GET_PTR_TYPE(p)) {\n+\t\tcase PTR_TYPE_INTERNAL:\n+\t\t\t/* recurse into int_node */\n+\t\t\tret = for_each_note_helper(\n+\t\t\t\tCLR_PTR_TYPE(p), n + 1, fanout, fn, cb_data);\n+\t\t\tbreak;\n+\t\tcase PTR_TYPE_SUBTREE:\n+\t\t\t/* unpack subtree and resume traversal */\n+\t\t\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\t\ttree->a[i] = NULL;\n+\t\t\tload_subtree(l, tree, n);\n+\t\t\tfree(l);\n+\t\t\tgoto redo;\n+\t\tcase PTR_TYPE_NOTE:\n+\t\t\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\t\tconstruct_path_with_fanout(l->key_sha1, fanout, path);\n+\t\t\tret = fn(l->key_sha1, l->val_sha1, path, cb_data);\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (ret)\n+\t\t\treturn ret;\n+\t}\n+\treturn 0;\n+}\n+\n void init_notes(const char *notes_ref, int flags)\n {\n \tunsigned char sha1[20], object_sha1[20];\n@@ -388,6 +483,12 @@ const unsigned char *get_note(const unsigned char *object_sha1)\n \treturn found ? found->val_sha1 : NULL;\n }\n \n+int for_each_note(each_note_fn fn, void *cb_data)\n+{\n+\tassert(initialized);\n+\treturn for_each_note_helper(&root_node, 0, 0, fn, cb_data);\n+}\n+\n void free_notes(void)\n {\n \tnote_tree_free(&root_node);\ndiff --git a/notes.h b/notes.h\nindex 21a8930..f67bae8 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -28,6 +28,23 @@ void add_note(const unsigned char *object_sha1,\n /* Get the note object SHA1 containing the note data for the given object */\n const unsigned char *get_note(const unsigned char *object_sha1);\n \n+/*\n+ * Invoke the specified callback function for each note\n+ *\n+ * If the callback returns nonzero, the note walk is aborted, and the return\n+ * value from the callback is returned from for_each_note().\n+ *\n+ * IMPORTANT: The callback function is NOT allowed to change the notes tree.\n+ * In other words, the following functions can NOT be invoked (on the current\n+ * notes tree) from within the callback:\n+ * - add_note()\n+ * - free_notes()\n+ */\n+typedef int each_note_fn(const unsigned char *object_sha1,\n+\t\tconst unsigned char *note_sha1, const char *note_tree_path,\n+\t\tvoid *cb_data);\n+int for_each_note(each_note_fn fn, void *cb_data);\n+\n /* Free (and de-initialize) the internal notes tree structure */\n void free_notes(void);\n \n-- \n1.6.5.3.433.g11067\n"},{"id":"129413","messageId":"1260185254-1523-11-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 10/11] Notes API: Allow multiple concurrent notes trees with new struct notes_tree","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:33Z","receivedAt":"2009-12-07T11:27:33Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"The new struct notes_tree encapsulates access to a specific notes tree.\nIt is provided to allow callers to interface with several different notes\ntrees simultaneously.\n\nA struct notes_tree * parameter is added to every function in the notes API.\nIn all cases, NULL can be passed, in which case, a fallback \"default\" notes\ntree (declared in notes.c) is used.\n\nSigned-off-by: Johan Herland \n---\n notes.c | 67 ++++++++++++++++++++++++++++++++++++++-----------------------\n notes.h | 53 +++++++++++++++++++++++++++++++++++-------------\n pretty.c | 7 +++--\n 3 files changed, 84 insertions(+), 43 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex de5a847..efd0007 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -50,9 +50,7 @@ struct leaf_node {\n #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \\\n \t(memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))\n \n-static struct int_node root_node;\n-\n-static int initialized;\n+static struct notes_tree default_tree;\n \n static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \t\tunsigned int n);\n@@ -436,14 +434,15 @@ redo:\n \treturn 0;\n }\n \n-void init_notes(const char *notes_ref, int flags)\n+void init_notes(struct notes_tree *t, const char *notes_ref, int flags)\n {\n \tunsigned char sha1[20], object_sha1[20];\n \tunsigned mode;\n \tstruct leaf_node root_tree;\n \n-\tassert(!initialized);\n-\tinitialized = 1;\n+\tif (!t)\n+\t\tt = &default_tree;\n+\tassert(!t->initialized);\n \n \tif (!notes_ref) {\n \t\tconst char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);\n@@ -453,6 +452,10 @@ void init_notes(const char *notes_ref, int flags)\n \t\t\tnotes_ref = GIT_NOTES_DEFAULT_REF;\n \t}\n \n+\tt->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);\n+\tt->ref = notes_ref ? xstrdup(notes_ref) : NULL;\n+\tt->initialized = 1;\n+\n \tif (flags & NOTES_INIT_EMPTY || !notes_ref ||\n \t read_ref(notes_ref, object_sha1) ||\n \t get_tree_entry(object_sha1, \"\", sha1, &mode))\n@@ -460,44 +463,56 @@ void init_notes(const char *notes_ref, int flags)\n \n \thashclr(root_tree.key_sha1);\n \thashcpy(root_tree.val_sha1, sha1);\n-\tload_subtree(&root_tree, &root_node, 0);\n+\tload_subtree(&root_tree, t->root, 0);\n }\n \n-void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)\n+void add_note(struct notes_tree *t, const unsigned char *object_sha1,\n+\t\tconst unsigned char *note_sha1)\n {\n \tstruct leaf_node *l;\n \n-\tassert(initialized);\n+\tif (!t)\n+\t\tt = &default_tree;\n+\tassert(t->initialized);\n \tl = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));\n \thashcpy(l->key_sha1, object_sha1);\n \thashcpy(l->val_sha1, note_sha1);\n-\tnote_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);\n+\tnote_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);\n }\n \n-const unsigned char *get_note(const unsigned char *object_sha1)\n+const unsigned char *get_note(struct notes_tree *t,\n+\t\tconst unsigned char *object_sha1)\n {\n \tstruct leaf_node *found;\n \n-\tassert(initialized);\n-\tfound = note_tree_find(&root_node, 0, object_sha1);\n+\tif (!t)\n+\t\tt = &default_tree;\n+\tassert(t->initialized);\n+\tfound = note_tree_find(t->root, 0, object_sha1);\n \treturn found ? found->val_sha1 : NULL;\n }\n \n-int for_each_note(each_note_fn fn, void *cb_data)\n+int for_each_note(struct notes_tree *t, each_note_fn fn, void *cb_data)\n {\n-\tassert(initialized);\n-\treturn for_each_note_helper(&root_node, 0, 0, fn, cb_data);\n+\tif (!t)\n+\t\tt = &default_tree;\n+\tassert(t->initialized);\n+\treturn for_each_note_helper(t->root, 0, 0, fn, cb_data);\n }\n \n-void free_notes(void)\n+void free_notes(struct notes_tree *t)\n {\n-\tnote_tree_free(&root_node);\n-\tmemset(&root_node, 0, sizeof(struct int_node));\n-\tinitialized = 0;\n+\tif (!t)\n+\t\tt = &default_tree;\n+\tif (t->root)\n+\t\tnote_tree_free(t->root);\n+\tfree(t->root);\n+\tfree(t->ref);\n+\tmemset(t, 0, sizeof(struct notes_tree));\n }\n \n-void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n-\t\tconst char *output_encoding, int flags)\n+void format_note(struct notes_tree *t, const unsigned char *object_sha1,\n+\t\tstruct strbuf *sb, const char *output_encoding, int flags)\n {\n \tstatic const char utf8[] = \"utf-8\";\n \tconst unsigned char *sha1;\n@@ -505,10 +520,12 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n \tunsigned long linelen, msglen;\n \tenum object_type type;\n \n-\tif (!initialized)\n-\t\tinit_notes(NULL, 0);\n+\tif (!t)\n+\t\tt = &default_tree;\n+\tif (!t->initialized)\n+\t\tinit_notes(t, NULL, 0);\n \n-\tsha1 = get_note(object_sha1);\n+\tsha1 = get_note(t, object_sha1);\n \tif (!sha1)\n \t\treturn;\n \ndiff --git a/notes.h b/notes.h\nindex f67bae8..ea1235f 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -2,6 +2,21 @@\n #define NOTES_H\n \n /*\n+ * Notes tree object\n+ *\n+ * Encapsulates the internal notes tree structure associated with a notes ref.\n+ * Whenever a struct notes_tree pointer is required below, you may pass NULL in\n+ * order to use the default/internal notes tree. E.g. you only need to pass a\n+ * non-NULL value if you need to refer to several different notes trees\n+ * simultaneously.\n+ */\n+struct notes_tree {\n+\tstruct int_node *root;\n+\tchar *ref;\n+\tint initialized;\n+};\n+\n+/*\n * Flags controlling behaviour of notes tree initialization\n *\n * Default behaviour is to initialize the notes tree from the tree object\n@@ -10,26 +25,32 @@\n #define NOTES_INIT_EMPTY 1\n \n /*\n- * Initialize internal notes tree structure with the notes tree at the given\n+ * Initialize the given notes_tree with the notes tree structure at the given\n * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment\n * variable is used, and if that is missing, the default notes ref is used\n * (\"refs/notes/commits\").\n *\n- * If you need to re-intialize the internal notes tree structure (e.g. loading\n- * from a different notes ref), please first de-initialize the current notes\n- * tree by calling free_notes().\n+ * If you need to re-intialize a notes_tree structure (e.g. when switching from\n+ * one notes ref to another), you must first de-initialize the notes_tree\n+ * structure by calling free_notes(struct notes_tree *).\n+ *\n+ * If you pass t == NULL, the default internal notes_tree will be initialized.\n+ *\n+ * Precondition: The notes_tree structure is zeroed (this can be achieved with\n+ * memset(t, 0, sizeof(struct notes_tree)))\n */\n-void init_notes(const char *notes_ref, int flags);\n+void init_notes(struct notes_tree *t, const char *notes_ref, int flags);\n \n-/* Add the given note object to the internal notes tree structure */\n-void add_note(const unsigned char *object_sha1,\n+/* Add the given note object to the given notes_tree structure */\n+void add_note(struct notes_tree *t, const unsigned char *object_sha1,\n \t\tconst unsigned char *note_sha1);\n \n /* Get the note object SHA1 containing the note data for the given object */\n-const unsigned char *get_note(const unsigned char *object_sha1);\n+const unsigned char *get_note(struct notes_tree *t,\n+\t\tconst unsigned char *object_sha1);\n \n /*\n- * Invoke the specified callback function for each note\n+ * Invoke the specified callback function for each note in the given notes_tree\n *\n * If the callback returns nonzero, the note walk is aborted, and the return\n * value from the callback is returned from for_each_note().\n@@ -43,10 +64,10 @@ const unsigned char *get_note(const unsigned char *object_sha1);\n typedef int each_note_fn(const unsigned char *object_sha1,\n \t\tconst unsigned char *note_sha1, const char *note_tree_path,\n \t\tvoid *cb_data);\n-int for_each_note(each_note_fn fn, void *cb_data);\n+int for_each_note(struct notes_tree *t, each_note_fn fn, void *cb_data);\n \n-/* Free (and de-initialize) the internal notes tree structure */\n-void free_notes(void);\n+/* Free (and de-initialize) the give notes_tree structure */\n+void free_notes(struct notes_tree *t);\n \n /* Flags controlling how notes are formatted */\n #define NOTES_SHOW_HEADER 1\n@@ -55,12 +76,14 @@ void free_notes(void);\n /*\n * Fill the given strbuf with the notes associated with the given object.\n *\n- * If the internal notes structure is not initialized, it will be auto-\n+ * If the given notes_tree structure is not initialized, it will be auto-\n * initialized to the default value (see documentation for init_notes() above).\n+ * If the given notes_tree is NULL, the internal/default notes_tree will be\n+ * used instead.\n *\n * 'flags' is a bitwise combination of the above formatting flags.\n */\n-void format_note(const unsigned char *object_sha1, struct strbuf *sb,\n-\t\tconst char *output_encoding, int flags);\n+void format_note(struct notes_tree *t, const unsigned char *object_sha1,\n+\t\tstruct strbuf *sb, const char *output_encoding, int flags);\n \n #endif\ndiff --git a/pretty.c b/pretty.c\nindex fe77090..b4882cc 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -775,8 +775,9 @@ static size_t format_commit_one(struct strbuf *sb, const char *placeholder,\n \t\t}\n \t\treturn 0;\t/* unknown %g placeholder */\n \tcase 'N':\n-\t\tformat_note(commit->object.sha1, sb, git_log_output_encoding ?\n-\t\t\t git_log_output_encoding : git_commit_encoding, 0);\n+\t\tformat_note(NULL, commit->object.sha1, sb,\n+\t\t\t git_log_output_encoding ? git_log_output_encoding\n+\t\t\t\t\t\t : git_commit_encoding, 0);\n \t\treturn 1;\n \t}\n \n@@ -1095,7 +1096,7 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,\n \t\tstrbuf_addch(sb, '\\n');\n \n \tif (fmt != CMIT_FMT_ONELINE)\n-\t\tformat_note(commit->object.sha1, sb, encoding,\n+\t\tformat_note(NULL, commit->object.sha1, sb, encoding,\n \t\t\t NOTES_SHOW_HEADER | NOTES_INDENT);\n \n \tfree(reencoded);\n-- \n1.6.5.3.433.g11067\n"},{"id":"129415","messageId":"1260185254-1523-12-git-send-email-johan@herland.net","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"[RFC/PATCHv10 11/11] Refactor notes concatenation into a flexible interface for combining notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-07T11:27:34Z","receivedAt":"2009-12-07T11:27:34Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"When adding a note to an object that already has an existing note, the\ncurrent solution is to concatenate the contents of the two notes. However,\nthe caller may instead wish to _overwrite_ the existing note with the new\nnote, or maybe even _ignore_ the new note, and keep the existing one. There\nmight also be other ways of combining notes that are only known to the\ncaller.\n\nTherefore, instead of unconditionally concatenating notes, we let the caller\nspecify how to combine notes, by passing in a pointer to a function for\ncombining notes. The caller may choose to implement its own function for\nnotes combining, but normally one of the following three conveniently\nsupplied notes combination functions will be sufficient:\n\n- combine_notes_concatenate() combines the two notes by appending the\n contents of the new note to the contents of the existing note.\n\n- combine_notes_overwrite() replaces the existing note with the new note.\n\n- combine_notes_ignore() keeps the existing note, and ignores the new note.\n\nA combine_notes function can be passed to init_notes() to choose a default\ncombine_notes function for that notes tree. If NULL is given, the notes tree\nfalls back to combine_notes_concatenate() as the ultimate default.\n\nA combine_notes function can also be passed directly to add_note(), to\ncontrol the notes combining behaviour for a note addition in particular.\nIf NULL is passed, the combine_notes function registered for the given\nnotes tree is used.\n\nSigned-off-by: Johan Herland \n---\n notes.c | 135 ++++++++++++++++++++++++++++++++++++---------------------------\n notes.h | 34 +++++++++++++++-\n 2 files changed, 109 insertions(+), 60 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex efd0007..04f0dae 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -127,55 +127,12 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n \treturn NULL;\n }\n \n-/* Create a new blob object by concatenating the two given blob objects */\n-static int concatenate_notes(unsigned char *cur_sha1,\n-\t\tconst unsigned char *new_sha1)\n-{\n-\tchar *cur_msg, *new_msg, *buf;\n-\tunsigned long cur_len, new_len, buf_len;\n-\tenum object_type cur_type, new_type;\n-\tint ret;\n-\n-\t/* read in both note blob objects */\n-\tnew_msg = read_sha1_file(new_sha1, &new_type, &new_len);\n-\tif (!new_msg || !new_len || new_type != OBJ_BLOB) {\n-\t\tfree(new_msg);\n-\t\treturn 0;\n-\t}\n-\tcur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);\n-\tif (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {\n-\t\tfree(cur_msg);\n-\t\tfree(new_msg);\n-\t\thashcpy(cur_sha1, new_sha1);\n-\t\treturn 0;\n-\t}\n-\n-\t/* we will separate the notes by a newline anyway */\n-\tif (cur_msg[cur_len - 1] == '\\n')\n-\t\tcur_len--;\n-\n-\t/* concatenate cur_msg and new_msg into buf */\n-\tbuf_len = cur_len + 1 + new_len;\n-\tbuf = (char *) xmalloc(buf_len);\n-\tmemcpy(buf, cur_msg, cur_len);\n-\tbuf[cur_len] = '\\n';\n-\tmemcpy(buf + cur_len + 1, new_msg, new_len);\n-\n-\tfree(cur_msg);\n-\tfree(new_msg);\n-\n-\t/* create a new blob object from buf */\n-\tret = write_sha1_file(buf, buf_len, \"blob\", cur_sha1);\n-\tfree(buf);\n-\treturn ret;\n-}\n-\n /*\n * To insert a leaf_node:\n * Search to the tree location appropriate for the given leaf_node's key:\n * - If location is unused (NULL), store the tweaked pointer directly there\n * - If location holds a note entry that matches the note-to-be-inserted, then\n- * concatenate the two notes.\n+ * combine the two notes (by calling the given combine_notes function).\n * - If location holds a note entry that matches the subtree-to-be-inserted,\n * then unpack the subtree-to-be-inserted into the location.\n * - If location holds a matching subtree entry, unpack the subtree at that\n@@ -184,7 +141,8 @@ static int concatenate_notes(unsigned char *cur_sha1,\n * node-to-be-inserted, and store the new int_node into the location.\n */\n static void note_tree_insert(struct int_node *tree, unsigned char n,\n-\t\tstruct leaf_node *entry, unsigned char type)\n+\t\tstruct leaf_node *entry, unsigned char type,\n+\t\tcombine_notes_fn combine_notes)\n {\n \tstruct int_node *new_node;\n \tstruct leaf_node *l;\n@@ -205,12 +163,11 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,\n \t\t\t\tif (!hashcmp(l->val_sha1, entry->val_sha1))\n \t\t\t\t\treturn;\n \n-\t\t\t\tif (concatenate_notes(l->val_sha1,\n-\t\t\t\t\t\tentry->val_sha1))\n-\t\t\t\t\tdie(\"failed to concatenate note %s \"\n-\t\t\t\t\t \"into note %s for object %s\",\n-\t\t\t\t\t sha1_to_hex(entry->val_sha1),\n+\t\t\t\tif (combine_notes(l->val_sha1, entry->val_sha1))\n+\t\t\t\t\tdie(\"failed to combine notes %s and %s\"\n+\t\t\t\t\t \" for object %s\",\n \t\t\t\t\t sha1_to_hex(l->val_sha1),\n+\t\t\t\t\t sha1_to_hex(entry->val_sha1),\n \t\t\t\t\t sha1_to_hex(l->key_sha1));\n \t\t\t\tfree(entry);\n \t\t\t\treturn;\n@@ -233,7 +190,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,\n \t\t\t*p = NULL;\n \t\t\tload_subtree(l, tree, n);\n \t\t\tfree(l);\n-\t\t\tnote_tree_insert(tree, n, entry, type);\n+\t\t\tnote_tree_insert(tree, n, entry, type, combine_notes);\n \t\t\treturn;\n \t\t}\n \t\tbreak;\n@@ -243,9 +200,9 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,\n \tassert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||\n \t GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);\n \tnew_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);\n-\tnote_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p));\n+\tnote_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p), combine_notes);\n \t*p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);\n-\tnote_tree_insert(new_node, n + 1, entry, type);\n+\tnote_tree_insert(new_node, n + 1, entry, type, combine_notes);\n }\n \n /* Free the entire notes data contained in the given tree */\n@@ -333,7 +290,8 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \t\t\t\tl->key_sha1[19] = (unsigned char) len;\n \t\t\t\ttype = PTR_TYPE_SUBTREE;\n \t\t\t}\n-\t\t\tnote_tree_insert(node, n, l, type);\n+\t\t\tnote_tree_insert(node, n, l, type,\n+\t\t\t\t\tcombine_notes_concatenate);\n \t\t}\n \t}\n \tfree(buf);\n@@ -434,7 +392,62 @@ redo:\n \treturn 0;\n }\n \n-void init_notes(struct notes_tree *t, const char *notes_ref, int flags)\n+int combine_notes_concatenate(unsigned char *cur_sha1,\n+\t\tconst unsigned char *new_sha1)\n+{\n+\tchar *cur_msg, *new_msg, *buf;\n+\tunsigned long cur_len, new_len, buf_len;\n+\tenum object_type cur_type, new_type;\n+\tint ret;\n+\n+\t/* read in both note blob objects */\n+\tnew_msg = read_sha1_file(new_sha1, &new_type, &new_len);\n+\tif (!new_msg || !new_len || new_type != OBJ_BLOB) {\n+\t\tfree(new_msg);\n+\t\treturn 0;\n+\t}\n+\tcur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);\n+\tif (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {\n+\t\tfree(cur_msg);\n+\t\tfree(new_msg);\n+\t\thashcpy(cur_sha1, new_sha1);\n+\t\treturn 0;\n+\t}\n+\n+\t/* we will separate the notes by a newline anyway */\n+\tif (cur_msg[cur_len - 1] == '\\n')\n+\t\tcur_len--;\n+\n+\t/* concatenate cur_msg and new_msg into buf */\n+\tbuf_len = cur_len + 1 + new_len;\n+\tbuf = (char *) xmalloc(buf_len);\n+\tmemcpy(buf, cur_msg, cur_len);\n+\tbuf[cur_len] = '\\n';\n+\tmemcpy(buf + cur_len + 1, new_msg, new_len);\n+\tfree(cur_msg);\n+\tfree(new_msg);\n+\n+\t/* create a new blob object from buf */\n+\tret = write_sha1_file(buf, buf_len, \"blob\", cur_sha1);\n+\tfree(buf);\n+\treturn ret;\n+}\n+\n+int combine_notes_overwrite(unsigned char *cur_sha1,\n+\t\tconst unsigned char *new_sha1)\n+{\n+\thashcpy(cur_sha1, new_sha1);\n+\treturn 0;\n+}\n+\n+int combine_notes_ignore(unsigned char *cur_sha1,\n+\t\tconst unsigned char *new_sha1)\n+{\n+\treturn 0;\n+}\n+\n+void init_notes(struct notes_tree *t, const char *notes_ref,\n+\t\tcombine_notes_fn combine_notes, int flags)\n {\n \tunsigned char sha1[20], object_sha1[20];\n \tunsigned mode;\n@@ -452,8 +465,12 @@ void init_notes(struct notes_tree *t, const char *notes_ref, int flags)\n \t\t\tnotes_ref = GIT_NOTES_DEFAULT_REF;\n \t}\n \n+\tif (!combine_notes)\n+\t\tcombine_notes = combine_notes_concatenate;\n+\n \tt->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);\n \tt->ref = notes_ref ? xstrdup(notes_ref) : NULL;\n+\tt->combine_notes = combine_notes;\n \tt->initialized = 1;\n \n \tif (flags & NOTES_INIT_EMPTY || !notes_ref ||\n@@ -467,17 +484,19 @@ void init_notes(struct notes_tree *t, const char *notes_ref, int flags)\n }\n \n void add_note(struct notes_tree *t, const unsigned char *object_sha1,\n-\t\tconst unsigned char *note_sha1)\n+\t\tconst unsigned char *note_sha1, combine_notes_fn combine_notes)\n {\n \tstruct leaf_node *l;\n \n \tif (!t)\n \t\tt = &default_tree;\n \tassert(t->initialized);\n+\tif (!combine_notes)\n+\t\tcombine_notes = t->combine_notes;\n \tl = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));\n \thashcpy(l->key_sha1, object_sha1);\n \thashcpy(l->val_sha1, note_sha1);\n-\tnote_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);\n+\tnote_tree_insert(t->root, 0, l, PTR_TYPE_NOTE, combine_notes);\n }\n \n const unsigned char *get_note(struct notes_tree *t,\n@@ -523,7 +542,7 @@ void format_note(struct notes_tree *t, const unsigned char *object_sha1,\n \tif (!t)\n \t\tt = &default_tree;\n \tif (!t->initialized)\n-\t\tinit_notes(t, NULL, 0);\n+\t\tinit_notes(t, NULL, NULL, 0);\n \n \tsha1 = get_note(t, object_sha1);\n \tif (!sha1)\ndiff --git a/notes.h b/notes.h\nindex ea1235f..047a282 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -2,6 +2,30 @@\n #define NOTES_H\n \n /*\n+ * Function type for combining two notes annotating the same object.\n+ *\n+ * When adding a new note annotating the same object as an existing note, it is\n+ * up to the caller to decide how to combine the two notes. The decision is\n+ * made by passing in a function of the following form. The function accepts\n+ * two SHA1s -- of the existing note and the new note, respectively. The\n+ * function then combines the notes in whatever way it sees fit, and writes the\n+ * resulting SHA1 into the first SHA1 argument (cur_sha1). A non-zero return\n+ * value indicates failure.\n+ *\n+ * The two given SHA1s are guaranteed to be non-NULL and different.\n+ *\n+ * The default combine_notes function (you get this when passing NULL) is\n+ * combine_notes_concatenate(), which appends the contents of the new note to\n+ * the contents of the existing note.\n+ */\n+typedef int combine_notes_fn(unsigned char *cur_sha1, const unsigned char *new_sha1);\n+\n+/* Common notes combinators */\n+int combine_notes_concatenate(unsigned char *cur_sha1, const unsigned char *new_sha1);\n+int combine_notes_overwrite(unsigned char *cur_sha1, const unsigned char *new_sha1);\n+int combine_notes_ignore(unsigned char *cur_sha1, const unsigned char *new_sha1);\n+\n+/*\n * Notes tree object\n *\n * Encapsulates the internal notes tree structure associated with a notes ref.\n@@ -13,6 +37,7 @@\n struct notes_tree {\n \tstruct int_node *root;\n \tchar *ref;\n+\tcombine_notes_fn *combine_notes;\n \tint initialized;\n };\n \n@@ -36,14 +61,19 @@ struct notes_tree {\n *\n * If you pass t == NULL, the default internal notes_tree will be initialized.\n *\n+ * The combine_notes function that is passed becomes the default combine_notes\n+ * function for the given notes_tree. If NULL is passed, the default\n+ * combine_notes function is combine_notes_concatenate().\n+ *\n * Precondition: The notes_tree structure is zeroed (this can be achieved with\n * memset(t, 0, sizeof(struct notes_tree)))\n */\n-void init_notes(struct notes_tree *t, const char *notes_ref, int flags);\n+void init_notes(struct notes_tree *t, const char *notes_ref,\n+\t\tcombine_notes_fn combine_notes, int flags);\n \n /* Add the given note object to the given notes_tree structure */\n void add_note(struct notes_tree *t, const unsigned char *object_sha1,\n-\t\tconst unsigned char *note_sha1);\n+\t\tconst unsigned char *note_sha1, combine_notes_fn combine_notes);\n \n /* Get the note object SHA1 containing the note data for the given object */\n const unsigned char *get_note(struct notes_tree *t,\n-- \n1.6.5.3.433.g11067\n"},{"id":"129431","messageId":"20091207164130.GD17173@spearce.org","threadId":"21888","inReplyTo":"1260185254-1523-2-git-send-email-johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-12-07T16:41:30Z","receivedAt":"2009-12-07T16:41:30Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johan Herland wrote:\n> As stated in the cover letter, I simply cannot store note information in\n> the tree_entry mode bits. So, I chose this somewhat more simple and crude\n> approach, which I still think solves the problems quite nicely.\n\nOh, duh. Of course you can't. You lose the note mode when the\ntree is flushed to disk, purged from memory, and reloaded later.\nWhoops, sorry I missed that during the last round of review.\n \n> +static uintmax_t do_change_note_fanout(\n> +\t\tstruct tree_entry *orig_root, struct tree_entry *root,\n> +\t\tchar *hex_sha1, unsigned int hex_sha1_len,\n> +\t\tchar *fullpath, unsigned int fullpath_len,\n> +\t\tunsigned char fanout)\n\nI think this function winds up processing all notes twice. Yuck.\n\ntree_content_set() adds a new tree entry to the end of the current\ntree. So when converting \"1a9029b006484e8b9aca06ff261beb2324bb9916\"\ninto \"1a\" (to go from fanout 0 to fanout 1) we'll place 1a at the\nend of orig_root, and this function will walk 1a/ recursively,\nexamining 1a9029b006484e8b9aca06ff261beb2324bb9916 all over again.\n\nIf we're here, isn't it likely that *all* notes are in the wrong\npath in the tree, and we need to move them all to a new location?\nIf that's true then should we instead just build an entirely new\ntree and swap the root when we are done?\n\nAs we empty out a tree the object will be recycled into a pool of\ntrees which can be reused at a later point. It might actually make\nsense to build the new tree under a different root. We won't scan\nentries we've moved, and the memory difference should be fairly\nsmall as tree_content_remove() will make a subtree available for\nreuse as soon as its empty. So we're only dealing with a handful\nof additional tree objects as we do the conversion.\n\n-- \nShawn.\n"},{"id":"129432","messageId":"20091207164311.GE17173@spearce.org","threadId":"21888","inReplyTo":"1260185254-1523-2-git-send-email-johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-12-07T16:43:11Z","receivedAt":"2009-12-07T16:43:11Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johan Herland wrote:\n> +static unsigned char convert_num_notes_to_fanout(uintmax_t num_notes)\n> +{\n> +\tunsigned char fanout = 0;\n> +\twhile ((num_notes >>= 8))\n> +\t\tfanout++;\n> +\treturn fanout;\n> +}\n> +\n> +static void construct_path_with_fanout(const char *hex_sha1,\n> +\t\tunsigned char fanout, char *path)\n> +{\n> +\tunsigned int i = 0, j = 0;\n> +\tif (fanout >= 20)\n> +\t\tdie(\"Too large fanout (%u)\", fanout);\n\nShouldn't convert_num_notes_to_fanout have a guard to prevent this\ncase from happening?\n\n-- \nShawn.\n"},{"id":"129448","messageId":"7vocma1ppc.fsf@alter.siamese.dyndns.org","threadId":"21888","inReplyTo":"1260185254-1523-2-git-send-email-johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-07T20:42:07Z","receivedAt":"2009-12-07T20:42:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n> This patch teaches 'git fast-import' to automatically organize note objects\n> in a fast-import stream into an appropriate fanout structure.\n\nI really hate to sound like a clueless newbie, but that is what I am in\nthe area of 'notes', so I have two questions.\n\n - What is the semantics of having more than one note to the same commit\n in the input stream? Does the 'notes' part also have history and the\n latest one overwrite the earlier one by creating a new commit that\n points at the new 'notes' tree? I've always thought of 'notes' as an\n unversioned metainfo, but I realize that versioning them would make\n sense (you can and obviously would want to inspect the story behind the\n current note attached to one particular commit).\n\n - If however 'notes' want to have a history, how would it interact with\n this rebalancing of the tree? Rebalancing makes a lot of sense if the\n 'notes' mechanism deals with the only one latest version because it can\n keep the optimal look-up performance. There were some talks about\n specialized merge strategies that can be made aware of rebalancing, but\n is there a plan to deal with \"git log -p notes\" side, and how?\n"},{"id":"129449","messageId":"7vk4wy1p8d.fsf@alter.siamese.dyndns.org","threadId":"21888","inReplyTo":"1260185254-1523-9-git-send-email-johan@herland.net","subject":"Re: [RFC/PATCHv10 08/11] Notes API: get_note(): Return the note annotating the given object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-07T20:52:18Z","receivedAt":"2009-12-07T20:52:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n> Created by a simple cleanup and rename of lookup_notes().\n>\n> Signed-off-by: Johan Herland \n> ---\n> notes.c | 15 ++++++++-------\n> notes.h | 3 +++\n> 2 files changed, 11 insertions(+), 7 deletions(-)\n>\n> diff --git a/notes.c b/notes.c\n> index 79bfa24..110404a 100644\n> --- a/notes.c\n> +++ b/notes.c\n> @@ -379,12 +379,13 @@ void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)\n> \tnote_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);\n> }\n> \n> -static unsigned char *lookup_notes(const unsigned char *object_sha1)\n> +const unsigned char *get_note(const unsigned char *object_sha1)\n\nIs there a need to find \"note for this commit in the set of notes 3 days\nago\"? IOW, reading note for the given commit not from the tip of the\nhistory of the refs/notes/commits but from say refs/notes/commits~4?\nSimilarly, is there a need to ask for a history of notes for a given\ncommit, something like \"git log refs/notes/commit/$this_commit\" in a world\nwithout any fanout?\n\nObviously, \"there is no need because...\" is the best answer I'd be happy\nwith. \"There may be in the future but we haven't identified a good use\ncase and we don't implement what we do not need now.\" is also perfectly\nacceptable.\n\nIOW, I am not suggesting to change it---I just want to know how much\nthought went in before deciding to implement the interface this way.\n"},{"id":"129464","messageId":"200912080244.30390.johan@herland.net","threadId":"21888","inReplyTo":"20091207164130.GD17173@spearce.org","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-08T01:44:30Z","receivedAt":"2009-12-08T01:44:30Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Monday 07 December 2009, Shawn O. Pearce wrote:\n> Johan Herland wrote:\n> > +static uintmax_t do_change_note_fanout(\n> > +\t\tstruct tree_entry *orig_root, struct tree_entry *root,\n> > +\t\tchar *hex_sha1, unsigned int hex_sha1_len,\n> > +\t\tchar *fullpath, unsigned int fullpath_len,\n> > +\t\tunsigned char fanout)\n> \n> I think this function winds up processing all notes twice. Yuck.\n> \n> tree_content_set() adds a new tree entry to the end of the current\n> tree. So when converting \"1a9029b006484e8b9aca06ff261beb2324bb9916\"\n> into \"1a\" (to go from fanout 0 to fanout 1) we'll place 1a at the\n> end of orig_root, and this function will walk 1a/ recursively,\n> examining 1a9029b006484e8b9aca06ff261beb2324bb9916 all over again.\n\nYep, you're right. Still, we only do the tree_content_remove()/set() once \nper note, so although performance is probably not abysmal, we are still \nclearly suboptimal.\n\nAlso, keep in mind that change_note_fanout() is only called when the number \nof notes crosses a power of 256. Thus for typical notes trees (which are \nassumed to mostly accumulate notes over their lifetime), \nchange_note_fanout() will be called zero, one or two times (depending on the \nfinal number of notes).\n\n> If we're here, isn't it likely that *all* notes are in the wrong\n> path in the tree, and we need to move them all to a new location?\n> If that's true then should we instead just build an entirely new\n> tree and swap the root when we are done?\n\nHmm. Not always. In your earlier scenario where we add 2,000,000 notes in a \nsingle commit, the current code would need to rewrite 255 of them from \nfanout 0 to fanout 2, and 65,535 of them from fanout 1 to fanout 2. But the \nvast majority (1,934,465) would not require rewriting (having been added at \nthe correct fanout initially). However, if we build a new tree (by which I \nassume you mean tree_content_remove() from the old tree and \ntree_content_set() to the new tree for every single note (and non-note)), we \nend up processing all 2,000,000 entries.\n\n> As we empty out a tree the object will be recycled into a pool of\n> trees which can be reused at a later point. It might actually make\n> sense to build the new tree under a different root. We won't scan\n> entries we've moved, and the memory difference should be fairly\n> small as tree_content_remove() will make a subtree available for\n> reuse as soon as its empty. So we're only dealing with a handful\n> of additional tree objects as we do the conversion.\n\nI'm not sure I get the details here. How can we avoid doing the \n_remove()/_set() from/to the old/new tree for every tree_entry? In other \nwords, how do we avoid removing and re-setting the 2,000,000 notes in the \nabove example?\n\n\nThanks for the review!\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129465","messageId":"200912080255.17568.johan@herland.net","threadId":"21888","inReplyTo":"20091207164311.GE17173@spearce.org","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-08T01:55:17Z","receivedAt":"2009-12-08T01:55:17Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Monday 07 December 2009, Shawn O. Pearce wrote:\n> Johan Herland wrote:\n> > +static unsigned char convert_num_notes_to_fanout(uintmax_t num_notes)\n> > +{\n> > +\tunsigned char fanout = 0;\n> > +\twhile ((num_notes >>= 8))\n> > +\t\tfanout++;\n> > +\treturn fanout;\n> > +}\n> > +\n> > +static void construct_path_with_fanout(const char *hex_sha1,\n> > +\t\tunsigned char fanout, char *path)\n> > +{\n> > +\tunsigned int i = 0, j = 0;\n> > +\tif (fanout >= 20)\n> > +\t\tdie(\"Too large fanout (%u)\", fanout);\n> \n> Shouldn't convert_num_notes_to_fanout have a guard to prevent this\n> case from happening?\n\nWell, it sort of already does (unless uintmax_t is more than 19 * 8 = 152 \nbits wide... ;)\n\nNot sure what you're getting at:\n\n- Should I add a \"&& fanout < 19\" condition to the while loop in \nconvert_num_notes_to_fanout()? \n\n- Should I remove the \"if (fanout >= 20) die(...)\"? Of course, \nconstruct_path_with_fanout() is only supposed to be called with values \nreturned from convert_num_notes_to_fanout(), so the condition only tests a \nprecondition that we believe to be true (FTR, it was converted from an \nequivalent assert() in an earlier iteration), but I normally test for these \nthings anyway (when they are not blindingly obvious), just to make sure... \n(and I believe a die(...) is kinder to the user than a segfault...)\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129467","messageId":"20091208015908.GB17588@spearce.org","threadId":"21888","inReplyTo":"200912080255.17568.johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-12-08T01:59:08Z","receivedAt":"2009-12-08T01:59:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johan Herland wrote:\n> On Monday 07 December 2009, Shawn O. Pearce wrote:\n> > > +\tif (fanout >= 20)\n> > > +\t\tdie(\"Too large fanout (%u)\", fanout);\n> > \n> > Shouldn't convert_num_notes_to_fanout have a guard to prevent this\n> > case from happening?\n> \n> Well, it sort of already does (unless uintmax_t is more than 19 * 8 = 152 \n> bits wide... ;)\n\nOh, good point. :-)\n \n> Not sure what you're getting at:\n> \n> - Should I add a \"&& fanout < 19\" condition to the while loop in \n> convert_num_notes_to_fanout()? \n\nThat's what I was thinking. But given the 19 * 8 = 152 case above,\nthis is pointless.\n\n-- \nShawn.\n"},{"id":"129469","messageId":"20091208020134.GC17588@spearce.org","threadId":"21888","inReplyTo":"200912080244.30390.johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-12-08T02:01:34Z","receivedAt":"2009-12-08T02:01:34Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johan Herland wrote:\n> > If we're here, isn't it likely that *all* notes are in the wrong\n> > path in the tree, and we need to move them all to a new location?\n> > If that's true then should we instead just build an entirely new\n> > tree and swap the root when we are done?\n> \n> Hmm. Not always. In your earlier scenario where we add 2,000,000 notes in a \n> single commit, the current code would need to rewrite 255 of them from \n> fanout 0 to fanout 2, and 65,535 of them from fanout 1 to fanout 2. But the \n> vast majority (1,934,465) would not require rewriting (having been added at \n> the correct fanout initially). However, if we build a new tree (by which I \n> assume you mean tree_content_remove() from the old tree and \n> tree_content_set() to the new tree for every single note (and non-note)), we \n> end up processing all 2,000,000 entries.\n\nWell, by processing here you mean we wind up looking at them, only\nto determine they are in the correct place already and skipping past.\n\nI guess I see your point though. We're fairly bounded on how many\nwe might need to move, probably only 65,535, and the rest will be\nat the right position so we're mostly just iterating through to\nconfirm they don't have to be moved.\n \n> I'm not sure I get the details here. How can we avoid doing the \n> _remove()/_set() from/to the old/new tree for every tree_entry? In other \n> words, how do we avoid removing and re-setting the 2,000,000 notes in the \n> above example?\n\nYou can't. But I realize now what you are saying... for the vast\nmajority of the notes we only need to validate they are in the\ncorrect path.\n\n-- \nShawn.\n"},{"id":"129470","messageId":"200912080334.39337.johan@herland.net","threadId":"21888","inReplyTo":"7vocma1ppc.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-08T02:34:39Z","receivedAt":"2009-12-08T02:34:39Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Monday 07 December 2009, Junio C Hamano wrote:\n> Johan Herland writes:\n> > This patch teaches 'git fast-import' to automatically organize note\n> > objects in a fast-import stream into an appropriate fanout structure.\n> \n> I really hate to sound like a clueless newbie, but that is what I am in\n> the area of 'notes', so I have two questions.\n> \n> - What is the semantics of having more than one note to the same commit\n> in the input stream? Does the 'notes' part also have history and the\n> latest one overwrite the earlier one by creating a new commit that\n> points at the new 'notes' tree?\n\nYes.\n\n> I've always thought of 'notes' as an\n> unversioned metainfo, but I realize that versioning them would make\n> sense (you can and obviously would want to inspect the story behind\n> the current note attached to one particular commit).\n\nCorrect. Since the notes themselves are organized in a regular ref pointing \nto a series of commits, the notes for a particular object are indeed \nversioned. Thus, the first annotation of a commit will happen as part of a \ncommit to the notes ref at some point in time, and a change to that \nannotation will happen as part of a subsequent commit to the same notes ref \nat some later point in time. The latter annotation naturally replaces the \nformer, in the same way as a regular file change causes a new blob to \nreplace any blob representing the previous version of the same file.\n\nHowever, if some object is annotated _twice_ in the _same_ notes commit, \nthen only the last annotation will be reachable. (again, this is the same \nbehaviour as if a regular file is changed twice in the same commit).\n\n> - If however 'notes' want to have a history, how would it interact with\n> this rebalancing of the tree? Rebalancing makes a lot of sense if the\n> 'notes' mechanism deals with the only one latest version because it\n> can keep the optimal look-up performance. There were some talks about\n> specialized merge strategies that can be made aware of rebalancing, but\n> is there a plan to deal with \"git log -p notes\" side, and how?\n\nFor now (at least), most use cases concern themselves only with the last \nversion of the notes tree, hence no work has been put into prettifying the \nhistory of the notes tree.\n\nThe notes rebalancing will become part of the same notes commit as the note \naddition/removal that triggers the rebalancing. This does indeed make the \nnotes commits themselves somewhat uglier, but since the rebalancing only \nmoves notes verbatim from one location to another, it's still fairly simple \n(with judicious use of e.g. \"-M\") to find the \"actual\" changes in a notes \ncommit.\n\nFor now, there is no plan to prettify the log of a notes ref, in order to \nmask away the fanout restructuring. For that matter, there is also no plan \nto hide the fanout structure itself of the notes tree. It is assumed that if \nyou need to look at a notes tree directly, you can either deal with the \nimplementation details yourself, (or by using future extensions to the notes \nAPI; see later patches for the beginnings of those...).\n\nWith regards to specialized merge strategies: When merging two notes trees \nwith no specialized strategy, you might end up with two (or more) notes \nobjects annotating the _same_ commit (located at different fanout levels). \nHowever, this has already been taken care of by the concatenation code at \nthe tail of the already-merged early part of jh/notes, which automatically \nconcatenates (non-identical) note objects annotating the same commit. Thus, \nno special merge strategy is needed in order to administer notes trees.\n\n\nHope this helps,\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129471","messageId":"200912080345.37429.johan@herland.net","threadId":"21888","inReplyTo":"20091208020134.GC17588@spearce.org","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-08T02:45:37Z","receivedAt":"2009-12-08T02:45:37Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Tuesday 08 December 2009, Shawn O. Pearce wrote:\n> Johan Herland wrote:\n> > > If we're here, isn't it likely that *all* notes are in the wrong\n> > > path in the tree, and we need to move them all to a new location?\n> > > If that's true then should we instead just build an entirely new\n> > > tree and swap the root when we are done?\n> >\n> > Hmm. Not always. In your earlier scenario where we add 2,000,000 notes\n> > in a single commit, the current code would need to rewrite 255 of them\n> > from fanout 0 to fanout 2, and 65,535 of them from fanout 1 to fanout\n> > 2. But the vast majority (1,934,465) would not require rewriting\n> > (having been added at the correct fanout initially). However, if we\n> > build a new tree (by which I assume you mean tree_content_remove() from\n> > the old tree and\n> > tree_content_set() to the new tree for every single note (and\n> > non-note)), we end up processing all 2,000,000 entries.\n> \n> Well, by processing here you mean we wind up looking at them, only\n> to determine they are in the correct place already and skipping past.\n\nNo, (as far as I (mis?)understood your idea) by processing here I'm talking \nabout moving all 2,000,000 entries from the old tree to the new tree.\n\nHere's my understanding of your idea:\n- Create a new, empty tree\n- For each entry in the old/existing tree:\n - If not a note, move[*] verbatim to new tree\n - If a correctly placed note, move[*] verbatim to new tree\n - Else, move[*] note to the _correct_ place in the new tree\n\n[*]: By \"move\" I assume you mean tree_content_remove() from the old tree, \nfollowed by tree_content_set() into the new tree.\n\n>From this understanding, I cannot see how your idea improves on the \nadding-2M-notes scenario.\n\n> I guess I see your point though. We're fairly bounded on how many\n> we might need to move, probably only 65,535, and the rest will be\n> at the right position so we're mostly just iterating through to\n> confirm they don't have to be moved.\n\nYep.\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129474","messageId":"200912080418.06233.johan@herland.net","threadId":"21888","inReplyTo":"7vk4wy1p8d.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCHv10 08/11] Notes API: get_note(): Return the note annotating the given object","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-08T03:18:06Z","receivedAt":"2009-12-08T03:18:06Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Monday 07 December 2009, Junio C Hamano wrote:\n> Johan Herland writes:\n> > Created by a simple cleanup and rename of lookup_notes().\n> >\n> > Signed-off-by: Johan Herland \n> > ---\n> > notes.c | 15 ++++++++-------\n> > notes.h | 3 +++\n> > 2 files changed, 11 insertions(+), 7 deletions(-)\n> >\n> > diff --git a/notes.c b/notes.c\n> > index 79bfa24..110404a 100644\n> > --- a/notes.c\n> > +++ b/notes.c\n> > @@ -379,12 +379,13 @@ void add_note(const unsigned char *object_sha1,\n> > const unsigned char *note_sha1) note_tree_insert(&root_node, 0, l,\n> > PTR_TYPE_NOTE);\n> > }\n> >\n> > -static unsigned char *lookup_notes(const unsigned char *object_sha1)\n> > +const unsigned char *get_note(const unsigned char *object_sha1)\n> \n> Is there a need to find \"note for this commit in the set of notes 3 days\n> ago\"? IOW, reading note for the given commit not from the tip of the\n> history of the refs/notes/commits but from say refs/notes/commits~4?\n> Similarly, is there a need to ask for a history of notes for a given\n> commit, something like \"git log refs/notes/commit/$this_commit\" in a\n> world without any fanout?\n>\n> Obviously, \"there is no need because...\" is the best answer I'd be happy\n> with. \"There may be in the future but we haven't identified a good use\n> case and we don't implement what we do not need now.\" is also perfectly\n> acceptable.\n\nThere may be in the future but we haven't identified a good use case and we \ndon't implement what we do not need now.\n\n;)\n\n> IOW, I am not suggesting to change it---I just want to know how much\n> thought went in before deciding to implement the interface this way.\n\nWell, this later part of the series (from patch #6) was built mainly to \nsupport the fast-import patch (which is no longer based on this API), but \nalso with an eye towards keeping things fairly flexible and generic. \nFurthermore I expect to use most of these patches when I get around to \nbuiltin-ifying the git-notes shell script (which currently is oblivious the \nnotes API and things like fanout and rebalancing).\n\nIn any case, if you look at patch #10/11, you'll see I introduce the concept \nof multiple notes trees. This was originally done to allow fast-import to \nedit notes in several branches simultaneously, but it now occurs to me that \nthis is exactly what we need to answer your questions above: If you want to \nlook at an older version of your notes tree, you simply instantiate another \nnotes tree with:\n\n\tstruct notes_tree my_notes;\n\tinit_notes(my_notes, \"refs/notes/commits~4\", ...);\n\nand you can now compare notes between my_notes and the current (or any \nother) notes tree.\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129513","messageId":"7vskblg6lr.fsf@alter.siamese.dyndns.org","threadId":"21888","inReplyTo":"1260185254-1523-1-git-send-email-johan@herland.net","subject":"Re: [RFC/PATCHv10 00/11] git notes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-08T09:25:36Z","receivedAt":"2009-12-08T09:25:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thanks; will re-queue.\n"},{"id":"129678","messageId":"200912101039.44526.johan@herland.net","threadId":"21888","inReplyTo":"200912080345.37429.johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-10T09:39:44Z","receivedAt":"2009-12-10T09:39:44Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Tuesday 08 December 2009, Johan Herland wrote:\n> On Tuesday 08 December 2009, Shawn O. Pearce wrote:\n> > Johan Herland wrote:\n> > > > If we're here, isn't it likely that *all* notes are in the wrong\n> > > > path in the tree, and we need to move them all to a new location?\n> > > > If that's true then should we instead just build an entirely new\n> > > > tree and swap the root when we are done?\n> > >\n> > > Hmm. Not always. In your earlier scenario where we add 2,000,000\n> > > notes in a single commit, the current code would need to rewrite 255\n> > > of them from fanout 0 to fanout 2, and 65,535 of them from fanout 1\n> > > to fanout 2. But the vast majority (1,934,465) would not require\n> > > rewriting (having been added at the correct fanout initially).\n> > > However, if we build a new tree (by which I assume you mean\n> > > tree_content_remove() from the old tree and\n> > > tree_content_set() to the new tree for every single note (and\n> > > non-note)), we end up processing all 2,000,000 entries.\n> >\n> > Well, by processing here you mean we wind up looking at them, only\n> > to determine they are in the correct place already and skipping past.\n> \n> No, (as far as I (mis?)understood your idea) by processing here I'm\n> talking about moving all 2,000,000 entries from the old tree to the new\n> tree.\n> \n> Here's my understanding of your idea:\n> - Create a new, empty tree\n> - For each entry in the old/existing tree:\n> - If not a note, move[*] verbatim to new tree\n> - If a correctly placed note, move[*] verbatim to new tree\n> - Else, move[*] note to the _correct_ place in the new tree\n> \n> [*]: By \"move\" I assume you mean tree_content_remove() from the old tree,\n> followed by tree_content_set() into the new tree.\n> \n> From this understanding, I cannot see how your idea improves on the\n> adding-2M-notes scenario.\n> \n> > I guess I see your point though. We're fairly bounded on how many\n> > we might need to move, probably only 65,535, and the rest will be\n> > at the right position so we're mostly just iterating through to\n> > confirm they don't have to be moved.\n> \n> Yep.\n\nDo you have more comments/suggestions on this patch? Or is it ok to include \nin fast-import as-is?\n\n\nHave fun! :)\n\n...Johan\n\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129693","messageId":"20091210140317.GA30665@spearce.org","threadId":"21888","inReplyTo":"200912101039.44526.johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-12-10T14:03:17Z","receivedAt":"2009-12-10T14:03:17Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johan Herland wrote:\n> Do you have more comments/suggestions on this patch? Or is it ok to include \n> in fast-import as-is?\n\nOops, sorry.\n\nNo, no additional comments. I am happy with this patch.\n\nAcked-by: Shawn O. Pearce \n\n-- \nShawn.\n"},{"id":"129697","messageId":"200912101540.43521.johan@herland.net","threadId":"21888","inReplyTo":"20091210140317.GA30665@spearce.org","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-12-10T14:40:43Z","receivedAt":"2009-12-10T14:40:43Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 10 December 2009, Shawn O. Pearce wrote:\n> Johan Herland wrote:\n> > Do you have more comments/suggestions on this patch? Or is it ok to\n> > include in fast-import as-is?\n>\n> Oops, sorry.\n>\n> No, no additional comments. I am happy with this patch.\n>\n> Acked-by: Shawn O. Pearce \n\nThanks.\n\nJunio: With the above Ack, I believe patches #1 - #4 (and possibly #5) \nfrom this series are ready for 'next'.\n\nYou may want to hold off on the remainder of the series until I get \naround to writing some functionality that actually _uses_ the new API.\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"129732","messageId":"7vfx7i6wqm.fsf@alter.siamese.dyndns.org","threadId":"21888","inReplyTo":"200912101540.43521.johan@herland.net","subject":"Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-12-11T03:00:17Z","receivedAt":"2009-12-11T03:00:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n> On Thursday 10 December 2009, Shawn O. Pearce wrote:\n>> Johan Herland wrote:\n>> > Do you have more comments/suggestions on this patch? Or is it ok to\n>> > include in fast-import as-is?\n>>\n>> Oops, sorry.\n>>\n>> No, no additional comments. I am happy with this patch.\n>>\n>> Acked-by: Shawn O. Pearce \n>\n> Thanks.\n>\n> Junio: With the above Ack, I believe patches #1 - #4 (and possibly #5) \n> from this series are ready for 'next'.\n>\n> You may want to hold off on the remainder of the series until I get \n> around to writing some functionality that actually _uses_ the new API.\n\nThanks for a notice, but we are already deep in pre-release freeze. I'll\nhold onto the message I am replying to, but I won't be adding anything to\n'next' until 1.6.6 final, unless it is somehow really urgent and deserves\nto be in 'maint' and/or 'master'.\n"}]}