{"thread":{"id":"20748","subject":"[PATCHv4 00/12] git notes","startedAt":"2009-08-27T01:43:45Z","lastAt":"2009-08-28T14:15:48Z","messageCount":38,"participants":["Johan Herland","Junio C Hamano","Alex Riesen","Johannes Schindelin","Shawn O. Pearce","Jeff King","Sverre Rabbelier"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"121832","messageId":"1251337437-16947-1-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":null,"subject":"[PATCHv4 00/12] git notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:45Z","receivedAt":"2009-08-27T01:43:45Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Another iteration of the 'git notes' feature. Rebased on top of 'next':\n- Patches 1-7 are unchanged from (patches 1-5 + 7-8 of) the last iteration.\n- Patch 8 introduces the new notes lookup code that offers both handling of\n fanout subtrees, and other performance improvements.\n- Patch 9 adds a selftest that verifies correct parsing of notes trees with\n various fanouts.\n- Patch 10 adds simple memory pooling to parts of the data structure from\n patch 8. This improves performance slightly.\n- Patches 11-12 adds the '%N' format specifier for pretty-printing commit\n notes (as suggested by Dscho in the previous notes thread).\n\n\nSome performance numbers from the notes lookup code:\n(these numbers are from my Core 2 Quad, 4 GB RAM)\n\nTest scenario I: Running t3302-notes-index-expensive\nTiming numbers from the 'time_notes 100' following 'create_repo 10000'\n\n no-notes notes\nbefore 16.22s 23.74s\nafter 16.31s 22.16s\nafter+mempool 16.24s 22.03s\n\nComments: This is a worst case scenario for pretty much any notes lookup\nalgorithm: Looking up all 10000 notes with no fanout (fanout level 0).\nThe new implementation does marginally better than the old.\n\n\nTest scenario II: Repo with 100,000 commits, 1 note per commit.\nTiming 100 repetitions of 'git log -n 10 refs/heads/master >/dev/null'\n\n without notes fanout level 0 fanout level 1 fanout level 2\n before 0.20s 32.44s N/A N/A\n after 0.19s 16.66s 0.85s 0.61s\n after+mempool 0.19s 16.20s 0.83s 0.57s\n\nComments: This hopefully gives a better simulation of a common use case\n(displaying only a handful of commits, and their notes). In the (relative)\nworst case (fanout level 0), the new code almost twice as fast as the old one.\nAs we add fanout, the runtime plummets (since we only need to unpack a handful\nof subtrees).\n\nIn practice, this means that with even a modest 2/38 or 2/2/36 fanout in the\nnotes tree (fanout level 1 and 2, respectively), the 'git log' user experience\ngoes from unbearable to barely noticeable in a repo with hundreds of thousands\nof notes.\n\n\nHave fun! :)\n\n...Johan\n\n\nJohan Herland (7):\n Teach \"-m \" and \"-F \" to \"git notes edit\"\n fast-import: Add support for importing commit notes\n t3302-notes-index-expensive: Speed up create_repo()\n Teach the notes lookup code to parse notes trees with various fanout schemes\n Selftests verifying semantics when loading notes trees with various fanouts\n notes.c: Implement simple memory pooling of leaf nodes\n Add flags to get_commit_notes() to control the format of the note string\n\nJohannes Schindelin (5):\n Introduce commit notes\n Add a script to edit/inspect notes\n Speed up git notes lookup\n Add an expensive test for git-notes\n Add '%N'-format for pretty-printing commit notes\n\n .gitignore | 1 +\n Documentation/config.txt | 13 ++\n Documentation/git-fast-import.txt | 45 +++++-\n Documentation/git-notes.txt | 60 +++++++\n Documentation/pretty-formats.txt | 1 +\n Makefile | 3 +\n cache.h | 4 +\n command-list.txt | 1 +\n commit.c | 1 +\n config.c | 5 +\n environment.c | 1 +\n fast-import.c | 88 +++++++++-\n git-notes.sh | 121 +++++++++++++\n notes.c | 338 +++++++++++++++++++++++++++++++++++++\n notes.h | 10 +\n pretty.c | 10 +\n t/t3301-notes.sh | 150 ++++++++++++++++\n t/t3302-notes-index-expensive.sh | 118 +++++++++++++\n t/t3303-notes-subtrees.sh | 206 ++++++++++++++++++++++\n t/t9300-fast-import.sh | 166 ++++++++++++++++++\n 20 files changed, 1332 insertions(+), 10 deletions(-)\n create mode 100644 Documentation/git-notes.txt\n create mode 100755 git-notes.sh\n create mode 100644 notes.c\n create mode 100644 notes.h\n create mode 100755 t/t3301-notes.sh\n create mode 100755 t/t3302-notes-index-expensive.sh\n create mode 100755 t/t3303-notes-subtrees.sh\n"},{"id":"121833","messageId":"1251337437-16947-2-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 01/12] Introduce commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:46Z","receivedAt":"2009-08-27T01:43:46Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nCommit notes are blobs which are shown together with the commit\nmessage. These blobs are taken from the notes ref, which you can\nconfigure by the config variable core.notesRef, which in turn can\nbe overridden by the environment variable GIT_NOTES_REF.\n\nThe notes ref is a branch which contains \"files\" whose names are\nthe names of the corresponding commits (i.e. the SHA-1).\n\nThe rationale for putting this information into a ref is this: we\nwant to be able to fetch and possibly union-merge the notes,\nmaybe even look at the date when a note was introduced, and we\nwant to store them efficiently together with the other objects.\n\nThis patch has been improved by the following contributions:\n- Thomas Rast: fix core.notesRef documentation\n- Tor Arne Vestbø: fix printing of multi-line notes\n- Alex Riesen: Using char array instead of char pointer costs less BSS\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Thomas Rast \nSigned-off-by: Tor Arne Vestbø \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n Documentation/config.txt | 13 +++++++++\n Makefile | 2 +\n cache.h | 4 +++\n commit.c | 1 +\n config.c | 5 +++\n environment.c | 1 +\n notes.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++\n notes.h | 7 +++++\n pretty.c | 5 +++\n 9 files changed, 106 insertions(+), 0 deletions(-)\n create mode 100644 notes.c\n create mode 100644 notes.h\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 5256c7f..645775f 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -439,6 +439,19 @@ On some file system/operating system combinations, this is unreliable.\n Set this config setting to 'rename' there; However, This will remove the\n check that makes sure that existing object files will not get overwritten.\n \n+core.notesRef::\n+\tWhen showing commit messages, also show notes which are stored in\n+\tthe given ref. This ref is expected to contain files named\n+\tafter the full SHA-1 of the commit they annotate.\n++\n+If such a file exists in the given ref, the referenced blob is read, and\n+appended to the commit message, separated by a \"Notes:\" line. If the\n+given ref itself does not exist, it is not an error, but means that no\n+notes should be printed.\n++\n+This setting defaults to \"refs/notes/commits\", and can be overridden by\n+the `GIT_NOTES_REF` environment variable.\n+\n add.ignore-errors::\n \tTells 'git-add' to continue adding files when some files cannot be\n \tadded due to indexing errors. Equivalent to the '--ignore-errors'\ndiff --git a/Makefile b/Makefile\nindex 4190a5d..95571db 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -426,6 +426,7 @@ LIB_H += ll-merge.h\n LIB_H += log-tree.h\n LIB_H += mailmap.h\n LIB_H += merge-recursive.h\n+LIB_H += notes.h\n LIB_H += object.h\n LIB_H += pack.h\n LIB_H += pack-refs.h\n@@ -509,6 +510,7 @@ LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += name-hash.o\n+LIB_OBJS += notes.o\n LIB_OBJS += object.o\n LIB_OBJS += pack-check.o\n LIB_OBJS += pack-refs.o\ndiff --git a/cache.h b/cache.h\nindex 808daba..739b42c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -371,6 +371,8 @@ static inline enum object_type object_type(unsigned int mode)\n #define GITATTRIBUTES_FILE \".gitattributes\"\n #define INFOATTRIBUTES_FILE \"info/attributes\"\n #define ATTRIBUTE_MACRO_PREFIX \"[attr]\"\n+#define GIT_NOTES_REF_ENVIRONMENT \"GIT_NOTES_REF\"\n+#define GIT_NOTES_DEFAULT_REF \"refs/notes/commits\"\n \n extern int is_bare_repository_cfg;\n extern int is_bare_repository(void);\n@@ -565,6 +567,8 @@ enum object_creation_mode {\n \n extern enum object_creation_mode object_creation_mode;\n \n+extern char *notes_ref_name;\n+\n extern int grafts_replace_parents;\n \n #define GIT_REPO_VERSION 0\ndiff --git a/commit.c b/commit.c\nindex e2bcbe8..ae6bff4 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -5,6 +5,7 @@\n #include \"utf8.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n+#include \"notes.h\"\n \n int save_commit_buffer = 1;\n \ndiff --git a/config.c b/config.c\nindex e87edea..70a7d34 100644\n--- a/config.c\n+++ b/config.c\n@@ -467,6 +467,11 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.notesref\")) {\n+\t\tnotes_ref_name = xstrdup(value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.pager\"))\n \t\treturn git_config_string(&pager_program, var, value);\n \ndiff --git a/environment.c b/environment.c\nindex 5de6837..571ab56 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -49,6 +49,7 @@ enum push_default_type push_default = PUSH_DEFAULT_MATCHING;\n #define OBJECT_CREATION_MODE OBJECT_CREATION_USES_HARDLINKS\n #endif\n enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;\n+char *notes_ref_name;\n int grafts_replace_parents = 1;\n \n /* Parallel index stat data preload? */\ndiff --git a/notes.c b/notes.c\nnew file mode 100644\nindex 0000000..401966d\n--- /dev/null\n+++ b/notes.c\n@@ -0,0 +1,68 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"notes.h\"\n+#include \"refs.h\"\n+#include \"utf8.h\"\n+#include \"strbuf.h\"\n+\n+static int initialized;\n+\n+void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n+\t\tconst char *output_encoding)\n+{\n+\tstatic const char utf8[] = \"utf-8\";\n+\tstruct strbuf name = STRBUF_INIT;\n+\tunsigned char sha1[20];\n+\tchar *msg, *msg_p;\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\tif (notes_ref_name && read_ref(notes_ref_name, sha1))\n+\t\t\tnotes_ref_name = NULL;\n+\t\tinitialized = 1;\n+\t}\n+\n+\tif (!notes_ref_name)\n+\t\treturn;\n+\n+\tstrbuf_addf(&name, \"%s:%s\", notes_ref_name,\n+\t\t\tsha1_to_hex(commit->object.sha1));\n+\tif (get_sha1(name.buf, sha1))\n+\t\treturn;\n+\n+\tif (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||\n+\t\t\ttype != OBJ_BLOB)\n+\t\treturn;\n+\n+\tif (output_encoding && *output_encoding &&\n+\t\t\tstrcmp(utf8, output_encoding)) {\n+\t\tchar *reencoded = reencode_string(msg, output_encoding, utf8);\n+\t\tif (reencoded) {\n+\t\t\tfree(msg);\n+\t\t\tmsg = reencoded;\n+\t\t\tmsglen = strlen(msg);\n+\t\t}\n+\t}\n+\n+\t/* we will end the annotation by a newline anyway */\n+\tif (msglen && msg[msglen - 1] == '\\n')\n+\t\tmsglen--;\n+\n+\tstrbuf_addstr(sb, \"\\nNotes:\\n\");\n+\n+\tfor (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {\n+\t\tlinelen = strchrnul(msg_p, '\\n') - msg_p;\n+\n+\t\tstrbuf_addstr(sb, \" \");\n+\t\tstrbuf_add(sb, msg_p, linelen);\n+\t\tstrbuf_addch(sb, '\\n');\n+\t}\n+\n+\tfree(msg);\n+}\ndiff --git a/notes.h b/notes.h\nnew file mode 100644\nindex 0000000..79d21b6\n--- /dev/null\n+++ b/notes.h\n@@ -0,0 +1,7 @@\n+#ifndef NOTES_H\n+#define NOTES_H\n+\n+void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n+\t\tconst char *output_encoding);\n+\n+#endif\ndiff --git a/pretty.c b/pretty.c\nindex f5983f8..e25db81 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -6,6 +6,7 @@\n #include \"string-list.h\"\n #include \"mailmap.h\"\n #include \"log-tree.h\"\n+#include \"notes.h\"\n #include \"color.h\"\n \n static char *user_format;\n@@ -975,5 +976,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,\n \t */\n \tif (fmt == CMIT_FMT_EMAIL && sb->len <= beginning_of_body)\n \t\tstrbuf_addch(sb, '\\n');\n+\n+\tif (fmt != CMIT_FMT_ONELINE)\n+\t\tget_commit_notes(commit, sb, encoding);\n+\n \tfree(reencoded);\n }\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121834","messageId":"1251337437-16947-3-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 02/12] Add a script to edit/inspect notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:47Z","receivedAt":"2009-08-27T01:43:47Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nThe script 'git notes' allows you to edit and show commit notes, by\ncalling either\n\n\tgit notes show \n\nor\n\n\tgit notes edit \n\nThis patch has been improved by the following contributions:\n- Tor Arne Vestbø: fix printing of multi-line notes\n- Michael J Gruber: test and handle empty notes gracefully\n- Thomas Rast:\n - only clean up message file when editing\n - use GIT_EDITOR and core.editor over VISUAL/EDITOR\n - t3301: fix confusing quoting in test for valid notes ref\n - t3301: use test_must_fail instead of !\n - refuse to edit notes outside refs/notes/\n- Junio C Hamano: tests: fix \"export var=val\"\n- Christian Couder: documentation: fix 'linkgit' macro in \"git-notes.txt\"\n- Johan Herland: minor cleanup and bugfixing in git-notes.sh (v2)\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Tor Arne Vestbø \nSigned-off-by: Michael J Gruber \nSigned-off-by: Thomas Rast \nSigned-off-by: Christian Couder \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n .gitignore | 1 +\n Documentation/git-notes.txt | 46 +++++++++++++++++\n Makefile | 1 +\n command-list.txt | 1 +\n git-notes.sh | 73 +++++++++++++++++++++++++++\n t/t3301-notes.sh | 114 +++++++++++++++++++++++++++++++++++++++++++\n 6 files changed, 236 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/git-notes.txt\n create mode 100755 git-notes.sh\n create mode 100755 t/t3301-notes.sh\n\ndiff --git a/.gitignore b/.gitignore\nindex c446290..703241b 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -86,6 +86,7 @@ git-mktag\n git-mktree\n git-name-rev\n git-mv\n+git-notes\n git-pack-redundant\n git-pack-objects\n git-pack-refs\ndiff --git a/Documentation/git-notes.txt b/Documentation/git-notes.txt\nnew file mode 100644\nindex 0000000..7136016\n--- /dev/null\n+++ b/Documentation/git-notes.txt\n@@ -0,0 +1,46 @@\n+git-notes(1)\n+============\n+\n+NAME\n+----\n+git-notes - Add/inspect commit notes\n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git-notes' (edit | show) [commit]\n+\n+DESCRIPTION\n+-----------\n+This command allows you to add notes to commit messages, without\n+changing the commit. To discern these notes from the message stored\n+in the commit object, the notes are indented like the message, after\n+an unindented line saying \"Notes:\".\n+\n+To disable commit notes, you have to set the config variable\n+core.notesRef to the empty string. Alternatively, you can set it\n+to a different ref, something like \"refs/notes/bugzilla\". This setting\n+can be overridden by the environment variable \"GIT_NOTES_REF\".\n+\n+\n+SUBCOMMANDS\n+-----------\n+\n+edit::\n+\tEdit the notes for a given commit (defaults to HEAD).\n+\n+show::\n+\tShow the notes for a given commit (defaults to HEAD).\n+\n+\n+Author\n+------\n+Written by Johannes Schindelin \n+\n+Documentation\n+-------------\n+Documentation by Johannes Schindelin\n+\n+GIT\n+---\n+Part of the linkgit:git[7] suite\ndiff --git a/Makefile b/Makefile\nindex 95571db..a2ec7b0 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -315,6 +315,7 @@ SCRIPT_SH += git-merge-one-file.sh\n SCRIPT_SH += git-merge-resolve.sh\n SCRIPT_SH += git-mergetool.sh\n SCRIPT_SH += git-mergetool--lib.sh\n+SCRIPT_SH += git-notes.sh\n SCRIPT_SH += git-parse-remote.sh\n SCRIPT_SH += git-pull.sh\n SCRIPT_SH += git-quiltimport.sh\ndiff --git a/command-list.txt b/command-list.txt\nindex fb03a2e..4296941 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -74,6 +74,7 @@ git-mktag plumbingmanipulators\n git-mktree plumbingmanipulators\n git-mv mainporcelain common\n git-name-rev plumbinginterrogators\n+git-notes mainporcelain\n git-pack-objects plumbingmanipulators\n git-pack-redundant plumbinginterrogators\n git-pack-refs ancillarymanipulators\ndiff --git a/git-notes.sh b/git-notes.sh\nnew file mode 100755\nindex 0000000..f06c254\n--- /dev/null\n+++ b/git-notes.sh\n@@ -0,0 +1,73 @@\n+#!/bin/sh\n+\n+USAGE=\"(edit | show) [commit]\"\n+. git-sh-setup\n+\n+test -n \"$3\" && usage\n+\n+test -z \"$1\" && usage\n+ACTION=\"$1\"; shift\n+\n+test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"$(git config core.notesref)\"\n+test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"refs/notes/commits\"\n+\n+COMMIT=$(git rev-parse --verify --default HEAD \"$@\") ||\n+die \"Invalid commit: $@\"\n+\n+case \"$ACTION\" in\n+edit)\n+\tif [ \"${GIT_NOTES_REF#refs/notes/}\" = \"$GIT_NOTES_REF\" ]; then\n+\t\tdie \"Refusing to edit notes in $GIT_NOTES_REF (outside of refs/notes/)\"\n+\tfi\n+\n+\tMSG_FILE=\"$GIT_DIR/new-notes-$COMMIT\"\n+\tGIT_INDEX_FILE=\"$MSG_FILE.idx\"\n+\texport GIT_INDEX_FILE\n+\n+\ttrap '\n+\t\ttest -f \"$MSG_FILE\" && rm \"$MSG_FILE\"\n+\t\ttest -f \"$GIT_INDEX_FILE\" && rm \"$GIT_INDEX_FILE\"\n+\t' 0\n+\n+\tGIT_NOTES_REF= git log -1 $COMMIT | sed \"s/^/#/\" > \"$MSG_FILE\"\n+\n+\tCURRENT_HEAD=$(git show-ref \"$GIT_NOTES_REF\" | cut -f 1 -d ' ')\n+\tif [ -z \"$CURRENT_HEAD\" ]; then\n+\t\tPARENT=\n+\telse\n+\t\tPARENT=\"-p $CURRENT_HEAD\"\n+\t\tgit read-tree \"$GIT_NOTES_REF\" || die \"Could not read index\"\n+\t\tgit cat-file blob :$COMMIT >> \"$MSG_FILE\" 2> /dev/null\n+\tfi\n+\n+\tcore_editor=\"$(git config core.editor)\"\n+\t${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} \"$MSG_FILE\"\n+\n+\tgrep -v ^# < \"$MSG_FILE\" | git stripspace > \"$MSG_FILE\".processed\n+\tmv \"$MSG_FILE\".processed \"$MSG_FILE\"\n+\tif [ -s \"$MSG_FILE\" ]; then\n+\t\tBLOB=$(git hash-object -w \"$MSG_FILE\") ||\n+\t\t\tdie \"Could not write into object database\"\n+\t\tgit update-index --add --cacheinfo 0644 $BLOB $COMMIT ||\n+\t\t\tdie \"Could not write index\"\n+\telse\n+\t\ttest -z \"$CURRENT_HEAD\" &&\n+\t\t\tdie \"Will not initialise with empty tree\"\n+\t\tgit update-index --force-remove $COMMIT ||\n+\t\t\tdie \"Could not update index\"\n+\tfi\n+\n+\tTREE=$(git write-tree) || die \"Could not write tree\"\n+\tNEW_HEAD=$(echo Annotate $COMMIT | git commit-tree $TREE $PARENT) ||\n+\t\tdie \"Could not annotate\"\n+\tgit update-ref -m \"Annotate $COMMIT\" \\\n+\t\t\"$GIT_NOTES_REF\" $NEW_HEAD $CURRENT_HEAD\n+;;\n+show)\n+\tgit rev-parse -q --verify \"$GIT_NOTES_REF\":$COMMIT > /dev/null ||\n+\t\tdie \"No note for commit $COMMIT.\"\n+\tgit show \"$GIT_NOTES_REF\":$COMMIT\n+;;\n+*)\n+\tusage\n+esac\ndiff --git a/t/t3301-notes.sh b/t/t3301-notes.sh\nnew file mode 100755\nindex 0000000..73e53be\n--- /dev/null\n+++ b/t/t3301-notes.sh\n@@ -0,0 +1,114 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2007 Johannes E. Schindelin\n+#\n+\n+test_description='Test commit notes'\n+\n+. ./test-lib.sh\n+\n+cat > fake_editor.sh << \\EOF\n+echo \"$MSG\" > \"$1\"\n+echo \"$MSG\" >& 2\n+EOF\n+chmod a+x fake_editor.sh\n+VISUAL=./fake_editor.sh\n+export VISUAL\n+\n+test_expect_success 'cannot annotate non-existing HEAD' '\n+\t(MSG=3 && export MSG && test_must_fail git notes edit)\n+'\n+\n+test_expect_success setup '\n+\t: > a1 &&\n+\tgit add a1 &&\n+\ttest_tick &&\n+\tgit commit -m 1st &&\n+\t: > a2 &&\n+\tgit add a2 &&\n+\ttest_tick &&\n+\tgit commit -m 2nd\n+'\n+\n+test_expect_success 'need valid notes ref' '\n+\t(MSG=1 GIT_NOTES_REF=/ && export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes edit) &&\n+\t(MSG=2 GIT_NOTES_REF=/ && export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes show)\n+'\n+\n+test_expect_success 'refusing to edit in refs/heads/' '\n+\t(MSG=1 GIT_NOTES_REF=refs/heads/bogus &&\n+\t export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes edit)\n+'\n+\n+test_expect_success 'refusing to edit in refs/remotes/' '\n+\t(MSG=1 GIT_NOTES_REF=refs/remotes/bogus &&\n+\t export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes edit)\n+'\n+\n+# 1 indicates caught gracefully by die, 128 means git-show barked\n+test_expect_success 'handle empty notes gracefully' '\n+\tgit notes show ; test 1 = $?\n+'\n+\n+test_expect_success 'create notes' '\n+\tgit config core.notesRef refs/notes/commits &&\n+\tMSG=b1 git notes edit &&\n+\ttest ! -f .git/new-notes &&\n+\ttest 1 = $(git ls-tree refs/notes/commits | wc -l) &&\n+\ttest b1 = $(git notes show) &&\n+\tgit show HEAD^ &&\n+\ttest_must_fail git notes show HEAD^\n+'\n+\n+cat > expect << EOF\n+commit 268048bfb8a1fb38e703baceb8ab235421bf80c5\n+Author: A U Thor \n+Date: Thu Apr 7 15:14:13 2005 -0700\n+\n+ 2nd\n+\n+Notes:\n+ b1\n+EOF\n+\n+test_expect_success 'show notes' '\n+\t! (git cat-file commit HEAD | grep b1) &&\n+\tgit log -1 > output &&\n+\ttest_cmp expect output\n+'\n+test_expect_success 'create multi-line notes (setup)' '\n+\t: > a3 &&\n+\tgit add a3 &&\n+\ttest_tick &&\n+\tgit commit -m 3rd &&\n+\tMSG=\"b3\n+c3c3c3c3\n+d3d3d3\" git notes edit\n+'\n+\n+cat > expect-multiline << EOF\n+commit 1584215f1d29c65e99c6c6848626553fdd07fd75\n+Author: A U Thor \n+Date: Thu Apr 7 15:15:13 2005 -0700\n+\n+ 3rd\n+\n+Notes:\n+ b3\n+ c3c3c3c3\n+ d3d3d3\n+EOF\n+\n+printf \"\\n\" >> expect-multiline\n+cat expect >> expect-multiline\n+\n+test_expect_success 'show multi-line notes' '\n+\tgit log -2 > output &&\n+\ttest_cmp expect-multiline output\n+'\n+\n+test_done\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121835","messageId":"1251337437-16947-4-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 03/12] Speed up git notes lookup","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:48Z","receivedAt":"2009-08-27T01:43:48Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nTo avoid looking up each and every commit in the notes ref's tree\nobject, which is very expensive, speed things up by slurping the tree\nobject's contents into a hash_map.\n\nThe idea for the hashmap singleton is from David Reiss, initial\nbenchmarking by Jeff King.\n\nNote: the implementation allows for arbitrary entries in the notes\ntree object, ignoring those that do not reference a valid object. This\nallows you to annotate arbitrary branches, or objects.\n\nThis patch has been improved by the following contributions:\n- Junio C Hamano: fixed an obvious error in initialize_hash_map()\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n notes.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 files changed, 102 insertions(+), 10 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 401966d..9172154 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -4,15 +4,112 @@\n #include \"refs.h\"\n #include \"utf8.h\"\n #include \"strbuf.h\"\n+#include \"tree-walk.h\"\n+\n+struct entry {\n+\tunsigned char commit_sha1[20];\n+\tunsigned char notes_sha1[20];\n+};\n+\n+struct hash_map {\n+\tstruct entry *entries;\n+\toff_t count, size;\n+};\n \n static int initialized;\n+static struct hash_map hash_map;\n+\n+static int hash_index(struct hash_map *map, const unsigned char *sha1)\n+{\n+\tint i = ((*(unsigned int *)sha1) % map->size);\n+\n+\tfor (;;) {\n+\t\tunsigned char *current = map->entries[i].commit_sha1;\n+\n+\t\tif (!hashcmp(sha1, current))\n+\t\t\treturn i;\n+\n+\t\tif (is_null_sha1(current))\n+\t\t\treturn -1 - i;\n+\n+\t\tif (++i == map->size)\n+\t\t\ti = 0;\n+\t}\n+}\n+\n+static void add_entry(const unsigned char *commit_sha1,\n+\t\tconst unsigned char *notes_sha1)\n+{\n+\tint index;\n+\n+\tif (hash_map.count + 1 > hash_map.size >> 1) {\n+\t\tint i, old_size = hash_map.size;\n+\t\tstruct entry *old = hash_map.entries;\n+\n+\t\thash_map.size = old_size ? old_size << 1 : 64;\n+\t\thash_map.entries = (struct entry *)\n+\t\t\txcalloc(sizeof(struct entry), hash_map.size);\n+\n+\t\tfor (i = 0; i < old_size; i++)\n+\t\t\tif (!is_null_sha1(old[i].commit_sha1)) {\n+\t\t\t\tindex = -1 - hash_index(&hash_map,\n+\t\t\t\t\t\told[i].commit_sha1);\n+\t\t\t\tmemcpy(hash_map.entries + index, old + i,\n+\t\t\t\t\tsizeof(struct entry));\n+\t\t\t}\n+\t\tfree(old);\n+\t}\n+\n+\tindex = hash_index(&hash_map, commit_sha1);\n+\tif (index < 0) {\n+\t\tindex = -1 - index;\n+\t\thash_map.count++;\n+\t}\n+\n+\thashcpy(hash_map.entries[index].commit_sha1, commit_sha1);\n+\thashcpy(hash_map.entries[index].notes_sha1, notes_sha1);\n+}\n+\n+static void initialize_hash_map(const char *notes_ref_name)\n+{\n+\tunsigned char sha1[20], commit_sha1[20];\n+\tunsigned mode;\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tvoid *buf;\n+\n+\tif (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||\n+\t get_tree_entry(commit_sha1, \"\", sha1, &mode))\n+\t\treturn;\n+\n+\tbuf = fill_tree_descriptor(&desc, sha1);\n+\tif (!buf)\n+\t\tdie(\"Could not read %s for notes-index\", sha1_to_hex(sha1));\n+\n+\twhile (tree_entry(&desc, &entry))\n+\t\tif (!get_sha1(entry.path, commit_sha1))\n+\t\t\tadd_entry(commit_sha1, entry.sha1);\n+\tfree(buf);\n+}\n+\n+static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n+{\n+\tint index;\n+\n+\tif (!hash_map.size)\n+\t\treturn NULL;\n+\n+\tindex = hash_index(&hash_map, commit_sha1);\n+\tif (index < 0)\n+\t\treturn NULL;\n+\treturn hash_map.entries[index].notes_sha1;\n+}\n \n void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n \t\tconst char *output_encoding)\n {\n \tstatic const char utf8[] = \"utf-8\";\n-\tstruct strbuf name = STRBUF_INIT;\n-\tunsigned char sha1[20];\n+\tunsigned char *sha1;\n \tchar *msg, *msg_p;\n \tunsigned long linelen, msglen;\n \tenum object_type type;\n@@ -23,17 +120,12 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,\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\tif (notes_ref_name && read_ref(notes_ref_name, sha1))\n-\t\t\tnotes_ref_name = NULL;\n+\t\tinitialize_hash_map(notes_ref_name);\n \t\tinitialized = 1;\n \t}\n \n-\tif (!notes_ref_name)\n-\t\treturn;\n-\n-\tstrbuf_addf(&name, \"%s:%s\", notes_ref_name,\n-\t\t\tsha1_to_hex(commit->object.sha1));\n-\tif (get_sha1(name.buf, sha1))\n+\tsha1 = lookup_notes(commit->object.sha1);\n+\tif (!sha1)\n \t\treturn;\n \n \tif (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121836","messageId":"1251337437-16947-5-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 04/12] Add an expensive test for git-notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:49Z","receivedAt":"2009-08-27T01:43:49Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\ngit-notes have the potential of being pretty expensive, so test with\na lot of commits. A lot. So to make things cheaper, you have to\nopt-in explicitely, by setting the environment variable\nGIT_NOTES_TIMING_TESTS.\n\nThis patch has been improved by the following contributions:\n- Junio C Hamano: tests: fix \"export var=val\"\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n t/t3302-notes-index-expensive.sh | 98 ++++++++++++++++++++++++++++++++++++++\n 1 files changed, 98 insertions(+), 0 deletions(-)\n create mode 100755 t/t3302-notes-index-expensive.sh\n\ndiff --git a/t/t3302-notes-index-expensive.sh b/t/t3302-notes-index-expensive.sh\nnew file mode 100755\nindex 0000000..0ef3e95\n--- /dev/null\n+++ b/t/t3302-notes-index-expensive.sh\n@@ -0,0 +1,98 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2007 Johannes E. Schindelin\n+#\n+\n+test_description='Test commit notes index (expensive!)'\n+\n+. ./test-lib.sh\n+\n+test -z \"$GIT_NOTES_TIMING_TESTS\" && {\n+\tsay Skipping timing tests\n+\ttest_done\n+\texit\n+}\n+\n+create_repo () {\n+\tnumber_of_commits=$1\n+\tnr=0\n+\tparent=\n+\ttest -d .git || {\n+\tgit init &&\n+\ttree=$(git write-tree) &&\n+\twhile [ $nr -lt $number_of_commits ]; do\n+\t\ttest_tick &&\n+\t\tcommit=$(echo $nr | git commit-tree $tree $parent) ||\n+\t\t\treturn\n+\t\tparent=\"-p $commit\"\n+\t\tnr=$(($nr+1))\n+\tdone &&\n+\tgit update-ref refs/heads/master $commit &&\n+\t{\n+\t\tGIT_INDEX_FILE=.git/temp; export GIT_INDEX_FILE;\n+\t\tgit rev-list HEAD | cat -n | sed \"s/^[ \t][ \t]*/ /g\" |\n+\t\twhile read nr sha1; do\n+\t\t\tblob=$(echo note $nr | git hash-object -w --stdin) &&\n+\t\t\techo $sha1 | sed \"s/^/0644 $blob 0\t/\"\n+\t\tdone | git update-index --index-info &&\n+\t\ttree=$(git write-tree) &&\n+\t\ttest_tick &&\n+\t\tcommit=$(echo notes | git commit-tree $tree) &&\n+\t\tgit update-ref refs/notes/commits $commit\n+\t} &&\n+\tgit config core.notesRef refs/notes/commits\n+\t}\n+}\n+\n+test_notes () {\n+\tcount=$1 &&\n+\tgit config core.notesRef refs/notes/commits &&\n+\tgit log | grep \"^ \" > output &&\n+\ti=1 &&\n+\twhile [ $i -le $count ]; do\n+\t\techo \" $(($count-$i))\" &&\n+\t\techo \" note $i\" &&\n+\t\ti=$(($i+1));\n+\tdone > expect &&\n+\tgit diff expect output\n+}\n+\n+cat > time_notes << \\EOF\n+\tmode=$1\n+\ti=1\n+\twhile [ $i -lt $2 ]; do\n+\t\tcase $1 in\n+\t\tno-notes)\n+\t\t\tGIT_NOTES_REF=non-existing; export GIT_NOTES_REF\n+\t\t;;\n+\t\tnotes)\n+\t\t\tunset GIT_NOTES_REF\n+\t\t;;\n+\t\tesac\n+\t\tgit log >/dev/null\n+\t\ti=$(($i+1))\n+\tdone\n+EOF\n+\n+time_notes () {\n+\tfor mode in no-notes notes\n+\tdo\n+\t\techo $mode\n+\t\t/usr/bin/time sh ../time_notes $mode $1\n+\tdone\n+}\n+\n+for count in 10 100 1000 10000; do\n+\n+\tmkdir $count\n+\t(cd $count;\n+\n+\ttest_expect_success \"setup $count\" \"create_repo $count\"\n+\n+\ttest_expect_success 'notes work' \"test_notes $count\"\n+\n+\ttest_expect_success 'notes timing' \"time_notes 100\"\n+\t)\n+done\n+\n+test_done\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121837","messageId":"1251337437-16947-6-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 05/12] Teach \"-m \" and \"-F \" to \"git notes edit\"","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:50Z","receivedAt":"2009-08-27T01:43:50Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"The \"-m\" and \"-F\" options are already the established method\n(in both git-commit and git-tag) to specify a commit/tag message\nwithout invoking the editor. This patch teaches \"git notes edit\"\nto respect the same options for specifying a notes message without\ninvoking the editor.\n\nMultiple \"-m\" and/or \"-F\" options are concatenated as separate\nparagraphs.\n\nThe patch also updates the \"git notes\" documentation and adds\nselftests for the new functionality. Unfortunately, the added\nselftests include a couple of lines with trailing whitespace\n(without these the test will fail). This may cause git to warn\nabout \"whitespace errors\".\n\nThis patch has been improved by the following contributions:\n- Thomas Rast: fix trailing whitespace in t3301\n\nSigned-off-by: Johan Herland \n---\n Documentation/git-notes.txt | 16 ++++++++++-\n git-notes.sh | 64 +++++++++++++++++++++++++++++++++++++-----\n t/t3301-notes.sh | 36 ++++++++++++++++++++++++\n 3 files changed, 107 insertions(+), 9 deletions(-)\n\ndiff --git a/Documentation/git-notes.txt b/Documentation/git-notes.txt\nindex 7136016..94cceb1 100644\n--- a/Documentation/git-notes.txt\n+++ b/Documentation/git-notes.txt\n@@ -8,7 +8,7 @@ git-notes - Add/inspect commit notes\n SYNOPSIS\n --------\n [verse]\n-'git-notes' (edit | show) [commit]\n+'git-notes' (edit [-F | -m ] | show) [commit]\n \n DESCRIPTION\n -----------\n@@ -33,6 +33,20 @@ show::\n \tShow the notes for a given commit (defaults to HEAD).\n \n \n+OPTIONS\n+-------\n+-m ::\n+\tUse the given note message (instead of prompting).\n+\tIf multiple `-m` (or `-F`) options are given, their\n+\tvalues are concatenated as separate paragraphs.\n+\n+-F ::\n+\tTake the note message from the given file. Use '-' to\n+\tread the note message from the standard input.\n+\tIf multiple `-F` (or `-m`) options are given, their\n+\tvalues are concatenated as separate paragraphs.\n+\n+\n Author\n ------\n Written by Johannes Schindelin \ndiff --git a/git-notes.sh b/git-notes.sh\nindex f06c254..e642e47 100755\n--- a/git-notes.sh\n+++ b/git-notes.sh\n@@ -1,16 +1,59 @@\n #!/bin/sh\n \n-USAGE=\"(edit | show) [commit]\"\n+USAGE=\"(edit [-F | -m ] | show) [commit]\"\n . git-sh-setup\n \n-test -n \"$3\" && usage\n-\n test -z \"$1\" && usage\n ACTION=\"$1\"; shift\n \n test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"$(git config core.notesref)\"\n test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"refs/notes/commits\"\n \n+MESSAGE=\n+while test $# != 0\n+do\n+\tcase \"$1\" in\n+\t-m)\n+\t\ttest \"$ACTION\" = \"edit\" || usage\n+\t\tshift\n+\t\tif test \"$#\" = \"0\"; then\n+\t\t\tdie \"error: option -m needs an argument\"\n+\t\telse\n+\t\t\tif [ -z \"$MESSAGE\" ]; then\n+\t\t\t\tMESSAGE=\"$1\"\n+\t\t\telse\n+\t\t\t\tMESSAGE=\"$MESSAGE\n+\n+$1\"\n+\t\t\tfi\n+\t\t\tshift\n+\t\tfi\n+\t\t;;\n+\t-F)\n+\t\ttest \"$ACTION\" = \"edit\" || usage\n+\t\tshift\n+\t\tif test \"$#\" = \"0\"; then\n+\t\t\tdie \"error: option -F needs an argument\"\n+\t\telse\n+\t\t\tif [ -z \"$MESSAGE\" ]; then\n+\t\t\t\tMESSAGE=\"$(cat \"$1\")\"\n+\t\t\telse\n+\t\t\t\tMESSAGE=\"$MESSAGE\n+\n+$(cat \"$1\")\"\n+\t\t\tfi\n+\t\t\tshift\n+\t\tfi\n+\t\t;;\n+\t-*)\n+\t\tusage\n+\t\t;;\n+\t*)\n+\t\tbreak\n+\t\t;;\n+\tesac\n+done\n+\n COMMIT=$(git rev-parse --verify --default HEAD \"$@\") ||\n die \"Invalid commit: $@\"\n \n@@ -29,19 +72,24 @@ edit)\n \t\ttest -f \"$GIT_INDEX_FILE\" && rm \"$GIT_INDEX_FILE\"\n \t' 0\n \n-\tGIT_NOTES_REF= git log -1 $COMMIT | sed \"s/^/#/\" > \"$MSG_FILE\"\n-\n \tCURRENT_HEAD=$(git show-ref \"$GIT_NOTES_REF\" | cut -f 1 -d ' ')\n \tif [ -z \"$CURRENT_HEAD\" ]; then\n \t\tPARENT=\n \telse\n \t\tPARENT=\"-p $CURRENT_HEAD\"\n \t\tgit read-tree \"$GIT_NOTES_REF\" || die \"Could not read index\"\n-\t\tgit cat-file blob :$COMMIT >> \"$MSG_FILE\" 2> /dev/null\n \tfi\n \n-\tcore_editor=\"$(git config core.editor)\"\n-\t${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} \"$MSG_FILE\"\n+\tif [ -z \"$MESSAGE\" ]; then\n+\t\tGIT_NOTES_REF= git log -1 $COMMIT | sed \"s/^/#/\" > \"$MSG_FILE\"\n+\t\tif [ ! -z \"$CURRENT_HEAD\" ]; then\n+\t\t\tgit cat-file blob :$COMMIT >> \"$MSG_FILE\" 2> /dev/null\n+\t\tfi\n+\t\tcore_editor=\"$(git config core.editor)\"\n+\t\t${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} \"$MSG_FILE\"\n+\telse\n+\t\techo \"$MESSAGE\" > \"$MSG_FILE\"\n+\tfi\n \n \tgrep -v ^# < \"$MSG_FILE\" | git stripspace > \"$MSG_FILE\".processed\n \tmv \"$MSG_FILE\".processed \"$MSG_FILE\"\ndiff --git a/t/t3301-notes.sh b/t/t3301-notes.sh\nindex 73e53be..1e34f48 100755\n--- a/t/t3301-notes.sh\n+++ b/t/t3301-notes.sh\n@@ -110,5 +110,41 @@ test_expect_success 'show multi-line notes' '\n \tgit log -2 > output &&\n \ttest_cmp expect-multiline output\n '\n+test_expect_success 'create -m and -F notes (setup)' '\n+\t: > a4 &&\n+\tgit add a4 &&\n+\ttest_tick &&\n+\tgit commit -m 4th &&\n+\techo \"xyzzy\" > note5 &&\n+\tgit notes edit -m spam -F note5 -m \"foo\n+bar\n+baz\"\n+'\n+\n+whitespace=\" \"\n+cat > expect-m-and-F << EOF\n+commit 15023535574ded8b1a89052b32673f84cf9582b8\n+Author: A U Thor \n+Date: Thu Apr 7 15:16:13 2005 -0700\n+\n+ 4th\n+\n+Notes:\n+ spam\n+$whitespace\n+ xyzzy\n+$whitespace\n+ foo\n+ bar\n+ baz\n+EOF\n+\n+printf \"\\n\" >> expect-m-and-F\n+cat expect-multiline >> expect-m-and-F\n+\n+test_expect_success 'show -m and -F notes' '\n+\tgit log -3 > output &&\n+\ttest_cmp expect-m-and-F output\n+'\n \n test_done\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121839","messageId":"1251337437-16947-7-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 06/12] fast-import: Add support for importing commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:51Z","receivedAt":"2009-08-27T01:43:51Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Introduce a 'notemodify' subcommand of the 'commit' command. This subcommand\nis similar to 'filemodify', except that no mode is supplied (all notes have\nmode 0644), and the path is set to the hex SHA1 of the given \"comittish\".\n\nThis enables fast import of note objects along with their associated commits,\nsince the notes can now be named using the mark references of their\ncorresponding commits.\n\nThe patch also includes a test case of the added functionality.\n\nSigned-off-by: Johan Herland \nAcked-by: Shawn O. Pearce \n---\n Documentation/git-fast-import.txt | 45 +++++++++--\n fast-import.c | 88 +++++++++++++++++++-\n t/t9300-fast-import.sh | 166 +++++++++++++++++++++++++++++++++++++\n 3 files changed, 289 insertions(+), 10 deletions(-)\n\ndiff --git a/Documentation/git-fast-import.txt b/Documentation/git-fast-import.txt\nindex c2f483a..288032c 100644\n--- a/Documentation/git-fast-import.txt\n+++ b/Documentation/git-fast-import.txt\n@@ -316,7 +316,7 @@ change to the project.\n \tdata\n \t('from' SP LF)?\n \t('merge' SP LF)?\n-\t(filemodify | filedelete | filecopy | filerename | filedeleteall)*\n+\t(filemodify | filedelete | filecopy | filerename | filedeleteall | notemodify)*\n \tLF?\n ....\n \n@@ -339,14 +339,13 @@ commit message use a 0 length data. Commit messages are free-form\n and are not interpreted by Git. Currently they must be encoded in\n UTF-8, as fast-import does not permit other encodings to be specified.\n \n-Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`\n-and `filedeleteall` commands\n+Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`,\n+`filedeleteall` and `notemodify` commands\n may be included to update the contents of the branch prior to\n creating the commit. These commands may be supplied in any order.\n However it is recommended that a `filedeleteall` command precede\n-all `filemodify`, `filecopy` and `filerename` commands in the same\n-commit, as `filedeleteall`\n-wipes the branch clean (see below).\n+all `filemodify`, `filecopy`, `filerename` and `notemodify` commands in\n+the same commit, as `filedeleteall` wipes the branch clean (see below).\n \n The `LF` after the command is optional (it used to be required).\n \n@@ -595,6 +594,40 @@ more memory per active branch (less than 1 MiB for even most large\n projects); so frontends that can easily obtain only the affected\n paths for a commit are encouraged to do so.\n \n+`notemodify`\n+^^^^^^^^^^^^\n+Included in a `commit` command to add a new note (annotating a given\n+commit) or change the content of an existing note. This command has\n+two different means of specifying the content of the note.\n+\n+External data format::\n+\tThe data content for the note was already supplied by a prior\n+\t`blob` command. The frontend just needs to connect it to the\n+\tcommit that is to be annotated.\n++\n+....\n+\t'N' SP SP LF\n+....\n++\n+Here `` can be either a mark reference (`:`)\n+set by a prior `blob` command, or a full 40-byte SHA-1 of an\n+existing Git blob object.\n+\n+Inline data format::\n+\tThe data content for the note has not been supplied yet.\n+\tThe frontend wants to supply it as part of this modify\n+\tcommand.\n++\n+....\n+\t'N' SP 'inline' SP LF\n+\tdata\n+....\n++\n+See below for a detailed description of the `data` command.\n+\n+In both formats `` is any of the commit specification\n+expressions also accepted by `from` (see above).\n+\n `mark`\n ~~~~~~\n Arranges for fast-import to save a reference to the current object, allowing\ndiff --git a/fast-import.c b/fast-import.c\nindex 7ef9865..97e6e9e 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -22,8 +22,8 @@ Format of STDIN stream:\n ('author' sp name sp '<' email '>' sp when lf)?\n 'committer' sp name sp '<' email '>' sp when lf\n commit_msg\n- ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?\n- ('merge' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)*\n+ ('from' sp committish lf)?\n+ ('merge' sp committish lf)*\n file_change*\n lf?;\n commit_msg ::= data;\n@@ -41,15 +41,18 @@ Format of STDIN stream:\n file_obm ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf;\n file_inm ::= 'M' sp mode sp 'inline' sp path_str lf\n data;\n+ note_obm ::= 'N' sp (hexsha1 | idnum) sp committish lf;\n+ note_inm ::= 'N' sp 'inline' sp committish lf\n+ data;\n \n new_tag ::= 'tag' sp tag_str lf\n- 'from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf\n+ 'from' sp committish lf\n ('tagger' sp name sp '<' email '>' sp when lf)?\n tag_msg;\n tag_msg ::= data;\n \n reset_branch ::= 'reset' sp ref_str lf\n- ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?\n+ ('from' sp committish lf)?\n lf?;\n \n checkpoint ::= 'checkpoint' lf\n@@ -88,6 +91,7 @@ Format of STDIN stream:\n # stream formatting is: \\, \" and LF. Otherwise these values\n # are UTF8.\n #\n+ committish ::= (ref_str | hexsha1 | sha1exp_str | idnum);\n ref_str ::= ref;\n sha1exp_str ::= sha1exp;\n tag_str ::= tag;\n@@ -2003,6 +2007,80 @@ 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+{\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+\tuint16_t inline_data = 0;\n+\n+\t/* or 'inline' */\n+\tif (*p == ':') {\n+\t\tchar *x;\n+\t\toe = find_mark(strtoumax(p + 1, &x, 10));\n+\t\thashcpy(sha1, oe->sha1);\n+\t\tp = x;\n+\t} else if (!prefixcmp(p, \"inline\")) {\n+\t\tinline_data = 1;\n+\t\tp += 6;\n+\t} else {\n+\t\tif (get_sha1_hex(p, sha1))\n+\t\t\tdie(\"Invalid SHA1: %s\", command_buf.buf);\n+\t\toe = find_object(sha1);\n+\t\tp += 40;\n+\t}\n+\tif (*p++ != ' ')\n+\t\tdie(\"Missing space after SHA1: %s\", command_buf.buf);\n+\n+\t/* */\n+\ts = lookup_branch(p);\n+\tif (s) {\n+\t\thashcpy(commit_sha1, s->sha1);\n+\t} else if (*p == ':') {\n+\t\tuintmax_t commit_mark = strtoumax(p + 1, NULL, 10);\n+\t\tstruct object_entry *commit_oe = find_mark(commit_mark);\n+\t\tif (commit_oe->type != OBJ_COMMIT)\n+\t\t\tdie(\"Mark :%\" PRIuMAX \" not a commit\", commit_mark);\n+\t\thashcpy(commit_sha1, commit_oe->sha1);\n+\t} else if (!get_sha1(p, commit_sha1)) {\n+\t\tunsigned long size;\n+\t\tchar *buf = read_object_with_reference(commit_sha1,\n+\t\t\tcommit_type, &size, commit_sha1);\n+\t\tif (!buf || size < 46)\n+\t\t\tdie(\"Not a valid commit: %s\", p);\n+\t\tfree(buf);\n+\t} else\n+\t\tdie(\"Invalid ref name or SHA1 expression: %s\", p);\n+\n+\tif (inline_data) {\n+\t\tstatic struct strbuf buf = STRBUF_INIT;\n+\n+\t\tif (p != uq.buf) {\n+\t\t\tstrbuf_addstr(&uq, p);\n+\t\t\tp = uq.buf;\n+\t\t}\n+\t\tread_next_command();\n+\t\tparse_data(&buf);\n+\t\tstore_object(OBJ_BLOB, &buf, &last_blob, sha1, 0);\n+\t} else if (oe) {\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\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+\t\tif (type != OBJ_BLOB)\n+\t\t\tdie(\"Not a blob (actually a %s): %s\",\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+}\n+\n static void file_change_deleteall(struct branch *b)\n {\n \trelease_tree_content_recursive(b->branch_tree.tree);\n@@ -2172,6 +2250,8 @@ static void parse_new_commit(void)\n \t\t\tfile_change_cr(b, 1);\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\telse if (!strcmp(\"deleteall\", command_buf.buf))\n \t\t\tfile_change_deleteall(b);\n \t\telse {\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex 821be7c..b49815d 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -1088,4 +1088,170 @@ INPUT_END\n test_expect_success 'P: fail on blob mark in gitlink' '\n test_must_fail git fast-import input < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data <expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+first (:3)\n+EOF\n+test_expect_success \\\n+\t'Q: verify first commit' \\\n+\t'git cat-file commit notes-test~2 | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+second (:5)\n+EOF\n+test_expect_success \\\n+\t'Q: verify second commit' \\\n+\t'git cat-file commit notes-test^ | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+third (:6)\n+EOF\n+test_expect_success \\\n+\t'Q: verify third commit' \\\n+\t'git cat-file commit notes-test | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\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+\ttest_cmp expect actual'\n+\n+cat >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 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+\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+\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+\n test_done\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121838","messageId":"1251337437-16947-8-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 07/12] t3302-notes-index-expensive: Speed up create_repo()","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:52Z","receivedAt":"2009-08-27T01:43:52Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Creating repos with 10/100/1000/10000 commits and notes takes a lot of time.\nHowever, using git-fast-import to do the job is a lot more efficient than\nusing plumbing commands to do the same.\n\nThis patch decreases the overall run-time of this test on my machine from\n~3 to ~1 minutes.\n\nSigned-off-by: Johan Herland \nAcked-by: Johannes Schindelin \n---\n t/t3302-notes-index-expensive.sh | 74 ++++++++++++++++++++++++--------------\n 1 files changed, 47 insertions(+), 27 deletions(-)\n\ndiff --git a/t/t3302-notes-index-expensive.sh b/t/t3302-notes-index-expensive.sh\nindex 0ef3e95..ee84fc4 100755\n--- a/t/t3302-notes-index-expensive.sh\n+++ b/t/t3302-notes-index-expensive.sh\n@@ -16,30 +16,50 @@ test -z \"$GIT_NOTES_TIMING_TESTS\" && {\n create_repo () {\n \tnumber_of_commits=$1\n \tnr=0\n-\tparent=\n \ttest -d .git || {\n \tgit init &&\n-\ttree=$(git write-tree) &&\n-\twhile [ $nr -lt $number_of_commits ]; do\n-\t\ttest_tick &&\n-\t\tcommit=$(echo $nr | git commit-tree $tree $parent) ||\n-\t\t\treturn\n-\t\tparent=\"-p $commit\"\n-\t\tnr=$(($nr+1))\n-\tdone &&\n-\tgit update-ref refs/heads/master $commit &&\n-\t{\n-\t\tGIT_INDEX_FILE=.git/temp; export GIT_INDEX_FILE;\n-\t\tgit rev-list HEAD | cat -n | sed \"s/^[ \t][ \t]*/ /g\" |\n-\t\twhile read nr sha1; do\n-\t\t\tblob=$(echo note $nr | git hash-object -w --stdin) &&\n-\t\t\techo $sha1 | sed \"s/^/0644 $blob 0\t/\"\n-\t\tdone | git update-index --index-info &&\n-\t\ttree=$(git write-tree) &&\n+\t(\n+\t\twhile [ $nr -lt $number_of_commits ]; do\n+\t\t\tnr=$(($nr+1))\n+\t\t\tmark=$(($nr+$nr))\n+\t\t\tnotemark=$(($mark+1))\n+\t\t\ttest_tick &&\n+\t\t\tcat < $GIT_COMMITTER_DATE\n+data <> note_commit\n+\t\tdone &&\n \t\ttest_tick &&\n-\t\tcommit=$(echo notes | git commit-tree $tree) &&\n-\t\tgit update-ref refs/notes/commits $commit\n-\t} &&\n+\t\tcat < $GIT_COMMITTER_DATE\n+data < output &&\n-\ti=1 &&\n-\twhile [ $i -le $count ]; do\n-\t\techo \" $(($count-$i))\" &&\n-\t\techo \" note $i\" &&\n-\t\ti=$(($i+1));\n+\ti=$count &&\n+\twhile [ $i -gt 0 ]; do\n+\t\techo \" commit #$i\" &&\n+\t\techo \" note for commit #$i\" &&\n+\t\ti=$(($i-1));\n \tdone > expect &&\n-\tgit diff expect output\n+\ttest_cmp expect output\n }\n \n cat > time_notes << \\EOF\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121840","messageId":"1251337437-16947-9-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:53Z","receivedAt":"2009-08-27T01:43:53Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"The semantics used when parsing notes trees (with regards to fanout subtrees)\nfollow Dscho's proposal fairly closely:\n- No concatenation/merging of notes is performed. If there are several notes\n objects referencing a given commit, only one of those objects are used.\n- If a notes object for a given commit is present in the \"root\" notes tree,\n no subtrees are consulted; the object in the root tree is used directly.\n- If there are more than one subtree that prefix-matches the given commit,\n only the subtree with the longest matching prefix is consulted. This\n means that if the given commit is e.g. \"deadbeef\", and the notes tree have\n subtrees \"de\" and \"dead\", then the following paths in the notes tree are\n searched: \"deadbeef\", \"dead/beef\". Note that \"de/adbeef\" is NOT searched.\n- Fanout directories (subtrees) must references a whole number of bytes\n from the SHA1 sum they subdivide. E.g. subtrees \"dead\" and \"de\" are\n acceptable; \"d\" and \"dea\" are not.\n- Multiple levels of fanout are allowed. All the above rules apply\n recursively. E.g. \"de/adbeef\" is preferred over \"de/adbe/ef\", etc.\n\nThis patch changes the in-memory datastructure for holding parsed notes:\nInstead of holding all note (and subtree) entries in a hash table, a\nsimple 16-tree structure is used instead. The tree structure consists of\n16-arrays as internal nodes, and note/subtree entries as leaf nodes. The\ntree is traversed by indexing subsequent nibbles of the search key until\na leaf node is encountered. If a subtree entry is encountered while\nsearching for a note, the subtree is unpacked into the 16-tree structure,\nand the search continues into that subtree.\n\nThe new algorithm performs significantly better in the cases where only\na fraction of the notes need to be looked up (this is assumed to be the\ncommon case for notes lookup). The new code even performs marginally\nbetter in the worst case (where _all_ the notes are looked up).\n\nIn addition to this, comes the massive performance win associated with\norganizing the notes tree according to some fanout scheme. Even a simple\n2/38 fanout scheme is dramatically quicker to traverse (going from tens of\nseconds to sub-second runtimes).\n\nAs for memory usage, the new code is marginally better than the old code in\nthe worst case, but in the case of looking up only some notes from a notes\ntree with proper fanout, the new code uses only a small fraction of the\nmemory needed to hold the entire notes tree.\n\nHowever, there is one casualty of this patch. The old notes lookup code was\nable to parse notes that were associated with non-SHA1s (e.g. refs). The new\ncode requires the referenced object to be named by a SHA1 sum. Still, this\nis not considered a major setback, since the notes infrastructure was not\noriginally intended to annotate objects outside the Git object database.\n\nCc: Johannes Schindelin \nSigned-off-by: Johan Herland \n---\n notes.c | 294 +++++++++++++++++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 228 insertions(+), 66 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 9172154..a637056 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -6,103 +6,265 @@\n #include \"strbuf.h\"\n #include \"tree-walk.h\"\n \n-struct entry {\n-\tunsigned char commit_sha1[20];\n-\tunsigned char notes_sha1[20];\n+/*\n+ * Use a non-balancing simple 16-tree structure with struct int_node as\n+ * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a\n+ * 16-array of pointers to its children.\n+ * The bottom 2 bits of each pointer is used to identify the pointer type\n+ * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)\n+ * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *\n+ * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *\n+ * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *\n+ *\n+ * The root node is a statically allocated struct int_node.\n+ */\n+struct int_node {\n+\tvoid *a[16];\n };\n \n-struct hash_map {\n-\tstruct entry *entries;\n-\toff_t count, size;\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+ * 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+ * the prefix. The value is the SHA1 of the tree object containing the notes\n+ * subtree.\n+ */\n+struct leaf_node {\n+\tunsigned char key_sha1[20];\n+\tunsigned char val_sha1[20];\n };\n \n+#define PTR_TYPE_NULL 0\n+#define PTR_TYPE_INTERNAL 1\n+#define PTR_TYPE_NOTE 2\n+#define PTR_TYPE_SUBTREE 3\n+\n+#define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)\n+#define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))\n+#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))\n+\n+#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((n & 0x01) << 2)) & 0x0f)\n+\n+#define MATCHING_SUBTREE(key_sha1, subtree_sha1) \\\n+\t(!memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))\n+\n static int initialized;\n-static struct hash_map hash_map;\n \n-static int hash_index(struct hash_map *map, const unsigned char *sha1)\n-{\n-\tint i = ((*(unsigned int *)sha1) % map->size);\n+static struct int_node root_node;\n \n-\tfor (;;) {\n-\t\tunsigned char *current = map->entries[i].commit_sha1;\n+static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n+\t\tunsigned int n);\n \n-\t\tif (!hashcmp(sha1, current))\n-\t\t\treturn i;\n+/*\n+ * To find a leaf_node:\n+ * 1. Start at the root node, with n = 0\n+ * 2. Use the nth nibble of the key as an index into a:\n+ * - If a[n] is an int_node, recurse into that node and increment n\n+ * - If a leaf_node with matching key, return leaf_node (assert note entry)\n+ * - If a matching subtree entry, unpack that subtree entry (and remove it);\n+ * restart search at the current level.\n+ * - Otherwise, we end up at a NULL pointer, or a non-matching leaf_node.\n+ * Backtrack out of the recursion, one level at a time and check a[0]:\n+ * - If a[0] at the current level is a matching subtree entry, unpack that\n+ * subtree entry (and remove it); restart search at the current level.\n+ */\n+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n+\t\tconst unsigned char *key_sha1)\n+{\n+\tstruct leaf_node *l;\n+\tunsigned char i = GET_NIBBLE(n, key_sha1);\n+\tvoid *p = tree->a[i];\n \n-\t\tif (is_null_sha1(current))\n-\t\t\treturn -1 - i;\n+\tswitch(GET_PTR_TYPE(p)) {\n+\tcase PTR_TYPE_INTERNAL:\n+\t\tl = note_tree_find(CLR_PTR_TYPE(p), n + 1, key_sha1);\n+\t\tif (l)\n+\t\t\treturn l;\n+\t\tbreak;\n+\tcase PTR_TYPE_NOTE:\n+\t\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\tif (!hashcmp(key_sha1, l->key_sha1))\n+\t\t\treturn l; /* return note object matching given key */\n+\t\tbreak;\n+\tcase PTR_TYPE_SUBTREE:\n+\t\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\tif (MATCHING_SUBTREE(key_sha1, l->key_sha1)) {\n+\t\t\t/* unpack tree and resume search */\n+\t\t\ttree->a[i] = NULL;\n+\t\t\tload_subtree(l, tree, n);\n+\t\t\tfree(l);\n+\t\t\treturn note_tree_find(tree, n, key_sha1);\n+\t\t}\n+\t\tbreak;\n+\tcase PTR_TYPE_NULL:\n+\tdefault:\n+\t\tassert(!p);\n+\t\tbreak;\n+\t}\n \n-\t\tif (++i == map->size)\n-\t\t\ti = 0;\n+\t/*\n+\t * Did not find key at this (or any lower) level.\n+\t * Check if there's a matching subtree entry in tree->a[0].\n+\t * If so, unpack tree and resume search.\n+\t */\n+\tp = tree->a[0];\n+\tif (GET_PTR_TYPE(p) != PTR_TYPE_SUBTREE)\n+\t\treturn NULL;\n+\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\tif (MATCHING_SUBTREE(key_sha1, l->key_sha1)) {\n+\t\t/* unpack tree and resume search */\n+\t\ttree->a[0] = NULL;\n+\t\tload_subtree(l, tree, n);\n+\t\tfree(l);\n+\t\treturn note_tree_find(tree, n, key_sha1);\n \t}\n+\treturn NULL;\n }\n \n-static void add_entry(const unsigned char *commit_sha1,\n-\t\tconst unsigned char *notes_sha1)\n+/*\n+ * To insert a leaf_node:\n+ * 1. Start at the root node, with n = 0\n+ * 2. Use the nth nibble of the key as an index into a:\n+ * - If a[n] is NULL, store the tweaked pointer directly into a[n]\n+ * - If a[n] is an int_node, recurse into that node and increment n\n+ * - If a[n] is a leaf_node:\n+ * 1. Check if they're equal, and handle that (abort? overwrite?)\n+ * 2. Create a new int_node, and store both leaf_nodes there\n+ * 3. Store the new int_node into a[n].\n+ */\n+static int note_tree_insert(struct int_node *tree, unsigned char n,\n+\t\tconst struct leaf_node *entry, unsigned char type)\n {\n-\tint index;\n-\n-\tif (hash_map.count + 1 > hash_map.size >> 1) {\n-\t\tint i, old_size = hash_map.size;\n-\t\tstruct entry *old = hash_map.entries;\n-\n-\t\thash_map.size = old_size ? old_size << 1 : 64;\n-\t\thash_map.entries = (struct entry *)\n-\t\t\txcalloc(sizeof(struct entry), hash_map.size);\n-\n-\t\tfor (i = 0; i < old_size; i++)\n-\t\t\tif (!is_null_sha1(old[i].commit_sha1)) {\n-\t\t\t\tindex = -1 - hash_index(&hash_map,\n-\t\t\t\t\t\told[i].commit_sha1);\n-\t\t\t\tmemcpy(hash_map.entries + index, old + i,\n-\t\t\t\t\tsizeof(struct entry));\n-\t\t\t}\n-\t\tfree(old);\n+\tstruct int_node *new_node;\n+\tconst struct leaf_node *l;\n+\tint ret;\n+\tunsigned char i = GET_NIBBLE(n, entry->key_sha1);\n+\tvoid *p = tree->a[i];\n+\tassert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);\n+\tswitch(GET_PTR_TYPE(p)) {\n+\tcase PTR_TYPE_NULL:\n+\t\tassert(!p);\n+\t\ttree->a[i] = SET_PTR_TYPE(entry, type);\n+\t\treturn 0;\n+\tcase PTR_TYPE_INTERNAL:\n+\t\treturn note_tree_insert(CLR_PTR_TYPE(p), n + 1, entry, type);\n+\tdefault:\n+\t\tassert(GET_PTR_TYPE(p) == PTR_TYPE_NOTE ||\n+\t\t\tGET_PTR_TYPE(p) == PTR_TYPE_SUBTREE);\n+\t\tl = (const struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\tif (!hashcmp(entry->key_sha1, l->key_sha1))\n+\t\t\treturn -1; /* abort insert on matching key */\n+\t\tnew_node = (struct int_node *)\n+\t\t\txcalloc(sizeof(struct int_node), 1);\n+\t\tret = note_tree_insert(new_node, n + 1,\n+\t\t\tCLR_PTR_TYPE(p), GET_PTR_TYPE(p));\n+\t\tif (ret) {\n+\t\t\tfree(new_node);\n+\t\t\treturn -1;\n+\t\t}\n+\t\ttree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);\n+\t\treturn note_tree_insert(new_node, n + 1, entry, type);\n \t}\n+}\n \n-\tindex = hash_index(&hash_map, commit_sha1);\n-\tif (index < 0) {\n-\t\tindex = -1 - index;\n-\t\thash_map.count++;\n+/*\n+ * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.\n+ * - hex - Partial SHA1 segment in ASCII hex format\n+ * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40\n+ * - sha1 - Partial SHA1 value is written here\n+ * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20\n+ * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format).\n+ * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).\n+ * Pads sha1 with NULs up to sha1_len (not included in returned length).\n+ */\n+static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,\n+\t\tunsigned char *sha1, unsigned int sha1_len)\n+{\n+\tunsigned int i, len = hex_len >> 1;\n+\tif (hex_len % 2 != 0 || len > sha1_len)\n+\t\treturn -1;\n+\tfor (i = 0; i < len; i++) {\n+\t\tunsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);\n+\t\tif (val & ~0xff)\n+\t\t\treturn -1;\n+\t\t*sha1++ = val;\n+\t\thex += 2;\n \t}\n+\tfor (; i < sha1_len; i++)\n+\t\t*sha1++ = 0;\n+\treturn len;\n+}\n+\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 int prefix_len;\n+\tint status;\n+\tvoid *buf;\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\n+\tbuf = fill_tree_descriptor(&desc, subtree->val_sha1);\n+\tif (!buf)\n+\t\tdie(\"Could not read %s for notes-index\",\n+\t\t sha1_to_hex(subtree->val_sha1));\n+\n+\tprefix_len = subtree->key_sha1[19];\n+\tassert(prefix_len * 2 >= n);\n+\tmemcpy(commit_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\tif (len < 0)\n+\t\t\tcontinue; /* entry.path is not a SHA1 sum. Skip */\n+\t\tlen += prefix_len;\n \n-\thashcpy(hash_map.entries[index].commit_sha1, commit_sha1);\n-\thashcpy(hash_map.entries[index].notes_sha1, notes_sha1);\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 */\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->val_sha1, entry.sha1);\n+\t\t\tif (len < 20) {\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\tstatus = note_tree_insert(node, n, l, type);\n+\t\t\tassert(!status);\n+\t\t}\n+\t}\n+\tfree(buf);\n }\n \n-static void initialize_hash_map(const char *notes_ref_name)\n+static void initialize_notes(const char *notes_ref_name)\n {\n \tunsigned char sha1[20], commit_sha1[20];\n \tunsigned mode;\n-\tstruct tree_desc desc;\n-\tstruct name_entry entry;\n-\tvoid *buf;\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 \t\treturn;\n \n-\tbuf = fill_tree_descriptor(&desc, sha1);\n-\tif (!buf)\n-\t\tdie(\"Could not read %s for notes-index\", sha1_to_hex(sha1));\n-\n-\twhile (tree_entry(&desc, &entry))\n-\t\tif (!get_sha1(entry.path, commit_sha1))\n-\t\t\tadd_entry(commit_sha1, entry.sha1);\n-\tfree(buf);\n+\thashclr(root_tree.key_sha1);\n+\thashcpy(root_tree.val_sha1, sha1);\n+\tload_subtree(&root_tree, &root_node, 0);\n }\n \n static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n {\n-\tint index;\n-\n-\tif (!hash_map.size)\n-\t\treturn NULL;\n-\n-\tindex = hash_index(&hash_map, commit_sha1);\n-\tif (index < 0)\n-\t\treturn NULL;\n-\treturn hash_map.entries[index].notes_sha1;\n+\tstruct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);\n+\tif (found)\n+\t\treturn found->val_sha1;\n+\treturn NULL;\n }\n \n void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n@@ -120,7 +282,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,\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_hash_map(notes_ref_name);\n+\t\tinitialize_notes(notes_ref_name);\n \t\tinitialized = 1;\n \t}\n \n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121844","messageId":"1251337437-16947-10-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 09/12] Selftests verifying semantics when loading notes trees with various fanouts","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:54Z","receivedAt":"2009-08-27T01:43:54Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Add selftests verifying:\n- that we are able to parse notes trees with various fanout schemes\n- that notes trees with conflicting fanout schemes are parsed as expected\n\nSigned-off-by: Johan Herland \n---\n t/t3303-notes-subtrees.sh | 206 +++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 206 insertions(+), 0 deletions(-)\n create mode 100755 t/t3303-notes-subtrees.sh\n\ndiff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh\nnew file mode 100755\nindex 0000000..40bb3f4\n--- /dev/null\n+++ b/t/t3303-notes-subtrees.sh\n@@ -0,0 +1,206 @@\n+#!/bin/sh\n+\n+test_description='Test commit notes organized in subtrees'\n+\n+. ./test-lib.sh\n+\n+number_of_commits=100\n+\n+start_note_commit () {\n+\ttest_tick &&\n+\tcat < $GIT_COMMITTER_DATE\n+data < output &&\n+\ti=$number_of_commits &&\n+\twhile [ $i -gt 0 ]; do\n+\t\techo \" commit #$i\" &&\n+\t\techo \" note for commit #$i\" &&\n+\t\ti=$(($i-1));\n+\tdone > expect &&\n+\ttest_cmp expect output\n+}\n+\n+test_expect_success 'setup: create $number_of_commits commits' '\n+\n+\t(\n+\t\tnr=0 &&\n+\t\twhile [ $nr -lt $number_of_commits ]; do\n+\t\t\tnr=$(($nr+1)) &&\n+\t\t\ttest_tick &&\n+\t\t\tcat < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data <\n---\n notes.c | 22 ++++++++++++++++++----\n 1 files changed, 18 insertions(+), 4 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex a637056..5d1ee17 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -55,6 +55,23 @@ static int initialized;\n \n static struct int_node root_node;\n \n+/* leaf nodes are allocated in simple memory pools */\n+#define LEAF_NODE_POOL_SIZE 100\n+static struct leaf_node *leaf_node_pool;\n+static unsigned int leaf_node_pool_used;\n+\n+\n+static struct leaf_node *new_leaf_node()\n+{\n+\tif (!leaf_node_pool || leaf_node_pool_used >= LEAF_NODE_POOL_SIZE) {\n+\t\t/* MEMORY LEAK: */\n+\t\tleaf_node_pool = (struct leaf_node *)\n+\t\t\txcalloc(sizeof(struct leaf_node), LEAF_NODE_POOL_SIZE);\n+\t\tleaf_node_pool_used = 0;\n+\t}\n+\treturn leaf_node_pool + leaf_node_pool_used++;\n+}\n+\n static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \t\tunsigned int n);\n \n@@ -95,7 +112,6 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n \t\t\t/* unpack tree and resume search */\n \t\t\ttree->a[i] = NULL;\n \t\t\tload_subtree(l, tree, n);\n-\t\t\tfree(l);\n \t\t\treturn note_tree_find(tree, n, key_sha1);\n \t\t}\n \t\tbreak;\n@@ -118,7 +134,6 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n \t\t/* unpack tree and resume search */\n \t\ttree->a[0] = NULL;\n \t\tload_subtree(l, tree, n);\n-\t\tfree(l);\n \t\treturn note_tree_find(tree, n, key_sha1);\n \t}\n \treturn NULL;\n@@ -229,8 +244,7 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\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\tstruct leaf_node *l = new_leaf_node();\n \t\t\thashcpy(l->key_sha1, commit_sha1);\n \t\t\thashcpy(l->val_sha1, entry.sha1);\n \t\t\tif (len < 20) {\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121842","messageId":"1251337437-16947-12-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 11/12] Add flags to get_commit_notes() to control the format of the note string","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:56Z","receivedAt":"2009-08-27T01:43:56Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This patch adds the following flags to get_commit_notes() for adjusting the\nformat of the produced note string:\n- NOTES_SHOW_HEADER: Print \"Notes:\" line before the notes contents\n- NOTES_INDENT: Indent notes contents by 4 spaces\n\nSuggested-by: Johannes Schindelin \nSigned-off-by: Johan Herland \n---\n notes.c | 8 +++++---\n notes.h | 5 ++++-\n pretty.c | 3 ++-\n 3 files changed, 11 insertions(+), 5 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 5d1ee17..bf520ae 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -282,7 +282,7 @@ static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n }\n \n void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n-\t\tconst char *output_encoding)\n+\t\tconst char *output_encoding, int flags)\n {\n \tstatic const char utf8[] = \"utf-8\";\n \tunsigned char *sha1;\n@@ -322,12 +322,14 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n \tif (msglen && msg[msglen - 1] == '\\n')\n \t\tmsglen--;\n \n-\tstrbuf_addstr(sb, \"\\nNotes:\\n\");\n+\tif (flags & NOTES_SHOW_HEADER)\n+\t\tstrbuf_addstr(sb, \"\\nNotes:\\n\");\n \n \tfor (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {\n \t\tlinelen = strchrnul(msg_p, '\\n') - msg_p;\n \n-\t\tstrbuf_addstr(sb, \" \");\n+\t\tif (flags & NOTES_INDENT)\n+\t\t\tstrbuf_addstr(sb, \" \");\n \t\tstrbuf_add(sb, msg_p, linelen);\n \t\tstrbuf_addch(sb, '\\n');\n \t}\ndiff --git a/notes.h b/notes.h\nindex 79d21b6..7f3eed4 100644\n--- a/notes.h\n+++ b/notes.h\n@@ -1,7 +1,10 @@\n #ifndef NOTES_H\n #define NOTES_H\n \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-\t\tconst char *output_encoding);\n+\t\tconst char *output_encoding, int flags);\n \n #endif\ndiff --git a/pretty.c b/pretty.c\nindex e25db81..01eadd0 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -978,7 +978,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\tget_commit_notes(commit, sb, encoding,\n+\t\t\t\t NOTES_SHOW_HEADER | NOTES_INDENT);\n \n \tfree(reencoded);\n }\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121843","messageId":"1251337437-16947-13-git-send-email-johan@herland.net","threadId":"20748","inReplyTo":"1251337437-16947-1-git-send-email-johan@herland.net","subject":"[PATCHv4 12/12] Add '%N'-format for pretty-printing commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T01:43:57Z","receivedAt":"2009-08-27T01:43:57Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nSigned-off-by: Johan Herland \n---\n Documentation/pretty-formats.txt | 1 +\n pretty.c | 4 ++++\n 2 files changed, 5 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt\nindex 2a845b1..5fb10b3 100644\n--- a/Documentation/pretty-formats.txt\n+++ b/Documentation/pretty-formats.txt\n@@ -123,6 +123,7 @@ The placeholders are:\n - '%s': subject\n - '%f': sanitized subject line, suitable for a filename\n - '%b': body\n+- '%N': commit notes\n - '%Cred': switch color to red\n - '%Cgreen': switch color to green\n - '%Cblue': switch color to blue\ndiff --git a/pretty.c b/pretty.c\nindex 01eadd0..7f350bb 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -702,6 +702,10 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,\n \tcase 'd':\n \t\tformat_decoration(sb, commit);\n \t\treturn 1;\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\treturn 1;\n \t}\n \n \t/* For the rest we have to parse the commit header. */\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121846","messageId":"7v7hwp6ebb.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"1251337437-16947-9-git-send-email-johan@herland.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-27T05:00:56Z","receivedAt":"2009-08-27T05:00:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n> The semantics used when parsing notes trees (with regards to fanout subtrees)\n> follow Dscho's proposal fairly closely:\n> - No concatenation/merging of notes is performed. If there are several notes\n> objects referencing a given commit, only one of those objects are used.\n> - If a notes object for a given commit is present in the \"root\" notes tree,\n> no subtrees are consulted; the object in the root tree is used directly.\n> - If there are more than one subtree that prefix-matches the given commit,\n> only the subtree with the longest matching prefix is consulted. This\n> means that if the given commit is e.g. \"deadbeef\", and the notes tree have\n> subtrees \"de\" and \"dead\", then the following paths in the notes tree are\n> searched: \"deadbeef\", \"dead/beef\". Note that \"de/adbeef\" is NOT searched.\n> - Fanout directories (subtrees) must references a whole number of bytes\n> from the SHA1 sum they subdivide. E.g. subtrees \"dead\" and \"de\" are\n> acceptable; \"d\" and \"dea\" are not.\n> - Multiple levels of fanout are allowed. All the above rules apply\n> recursively. E.g. \"de/adbeef\" is preferred over \"de/adbe/ef\", etc.\n\nIf I am reading this correctly, the earlier parts of the series were\naiming to let multiple people to add notes to the same commit more or less\nuncordinated while still allowing to merge them sensibly, but now such a\nworkflow becomes impossible with this change. \n\nThe above claims notes trees with different levels of fan-out are allowed,\nbut what it really means is that merging notes trees with different levels\nof fan-out will produce a useless result that records notes for the same\ncommit in different blobs all over the notes tree, and asking the notes\nmechanism to give the notes for one commit will give only one piece that\noriginates in the tree whose creator happened to have used the longest\nprefix while ignoring all others. It may _allow_ such a layout, but how\nwould such semantics be useful in the first place?\n\nI suspect that I am missing something but my gut feeling is that this\nchange turns an interesting hack (even though it might be expensive) into\na hack that is not useful at all in the real world, without some order,\ndiscipline, or guideline is applied.\n\nWhat's the recommended way to work with this system from the end user's\npoint of view in a distirbuted environment? Somebody up in the project is\nsupposed to decide what fan-out is to be used for the whole project and\neverybody should follow that structure? If a participant in the project\nforgets that rule (or makes a mistake), a notes tree that mistakenly\nmerges his notes tree becomes practically useless? If so, perhaps we\nwould need a mechanism to avoid such a mistake from happening?\n"},{"id":"121851","messageId":"81b0412b0908270039l7a937c3bmd745274c71526ce1@mail.gmail.com","threadId":"20748","inReplyTo":"1251337437-16947-11-git-send-email-johan@herland.net","subject":"Re: [PATCHv4 10/12] notes.c: Implement simple memory pooling of leaf nodes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2009-08-27T07:39:31Z","receivedAt":"2009-08-27T07:39:31Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Thu, Aug 27, 2009 at 03:43, Johan Herland wrote:\n> When allocating a new memory pool, the older pool is leaked, but this is\n> no worse than the current situation, where (pretty much) all leaf_nodes\n> are leaked anyway.\n\nCould you return the unused nodes back into tghe mempool?\nBy making the pool a preallocated list, perhaps?\n\nAnd then it is trivial to provide a deallocation function for the mempool,\nwhich something really concerned about the memleak can call (like when\nor if libgit get more usable in an application context).\n\n> @@ -95,7 +112,6 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n>                        /* unpack tree and resume search */\n>                        tree->a[i] = NULL;\n>                        load_subtree(l, tree, n);\n> -                       free(l);\n\nfree_leaf_node(l), which returns the node into mempool\n\n>                        return note_tree_find(tree, n, key_sha1);\n>                }\n>                break;\n> @@ -118,7 +134,6 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n>                /* unpack tree and resume search */\n>                tree->a[0] = NULL;\n>                load_subtree(l, tree, n);\n> -               free(l);\n\nfree_leaf_node(l);\n\n>                return note_tree_find(tree, n, key_sha1);\n>        }\n>        return NULL;\n"},{"id":"121854","messageId":"200908271135.31794.johan@herland.net","threadId":"20748","inReplyTo":"7v7hwp6ebb.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T09:35:31Z","receivedAt":"2009-08-27T09:35:31Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 27 August 2009, Junio C Hamano wrote:\n> Johan Herland writes:\n> > The semantics used when parsing notes trees (with regards to fanout\n> > subtrees) follow Dscho's proposal fairly closely:\n> > - No concatenation/merging of notes is performed. If there are several\n> > notes objects referencing a given commit, only one of those objects are\n> > used. - If a notes object for a given commit is present in the \"root\"\n> > notes tree, no subtrees are consulted; the object in the root tree is\n> > used directly. - If there are more than one subtree that prefix-matches\n> > the given commit, only the subtree with the longest matching prefix is\n> > consulted. This means that if the given commit is e.g. \"deadbeef\", and\n> > the notes tree have subtrees \"de\" and \"dead\", then the following paths\n> > in the notes tree are searched: \"deadbeef\", \"dead/beef\". Note that\n> > \"de/adbeef\" is NOT searched. - Fanout directories (subtrees) must\n> > references a whole number of bytes from the SHA1 sum they subdivide.\n> > E.g. subtrees \"dead\" and \"de\" are acceptable; \"d\" and \"dea\" are not.\n> > - Multiple levels of fanout are allowed. All the above rules apply\n> > recursively. E.g. \"de/adbeef\" is preferred over \"de/adbe/ef\", etc.\n>\n> If I am reading this correctly, the earlier parts of the series were\n> aiming to let multiple people to add notes to the same commit more or\n> less uncordinated while still allowing to merge them sensibly, but now\n> such a workflow becomes impossible with this change.\n>\n> The above claims notes trees with different levels of fan-out are\n> allowed, but what it really means is that merging notes trees with\n> different levels of fan-out will produce a useless result that records\n> notes for the same commit in different blobs all over the notes tree, and\n> asking the notes mechanism to give the notes for one commit will give\n> only one piece that originates in the tree whose creator happened to have\n> used the longest prefix while ignoring all others. It may _allow_ such a\n> layout, but how would such semantics be useful in the first place?\n>\n> I suspect that I am missing something but my gut feeling is that this\n> change turns an interesting hack (even though it might be expensive) into\n> a hack that is not useful at all in the real world, without some order,\n> discipline, or guideline is applied.\n\nAs you may remember, the major, remaining problem with the jh/notes patch \nseries was that as the number of notes in a repo grew, the runtime cost of \ndisplaying (even a single one of) them became prohibitive. This was the \nmajor reason why Dscho and me did NOT want you to merge this series earlier.\nThe solution to this performance problem (which has been discussed since \nalmost a year ago), is to use some fanout scheme in the notes tree, so that \nwe can load individual notes without necessarily parsing the entire notes \ntree. This patch implements the _reading_ of a notes trees with fanout.\n\nHowever, as you correctly identify, allowing fanout makes it possible to add \nmultiple notes for the same commit in the same notes tree.\n\nTherefore, we must now create the order/discipline/guideline you request by \ntaking away this extra freedom.\n\nThis will take the form of enforcing a chosen fanout scheme when _writing_ \nnotes. This code (yet to be written) will include:\n\n- refactoring the notes tree when the number of notes call for a different \nfanout scheme (e.g. create a 2/38 fanout scheme when the number of notes in \na (sub)tree exceed some threshold).\n\n- adding and editing notes while following the current fanout scheme.\n\n- adding a custom merge strategy for note trees, which reads notes trees \n\n\nCurrently I have a two different ideas on a suitable fanout scheme:\n\n1. Define a threshold where the number of notes in a (sub)tree becomes large \nenough warrant a fanout. For now, let's assume that threshold is 1024. Start \nwith en empty notes tree with no fanout. When we reach 1024 notes, split the \nnotes tree into 256 subdirs (2/38 fanout). As each of the subdirs reach 1024 \nnotes, split those subdirs further (2/2/36 fanout), and so on. In practice \n(since SHA1 gives us a uniform distribution), notes trees with up to:\n- < 1024 notes will have no fanout\n- < ~256K notes will have 2/38 fanout\n- < ~64M notes will have 2/2/36 fanout\n- < ~16G notes will have 2/2/2/34 fanout\n\n2. Simply decide on a constant 2/2/36 fanout. For the case with < 256K \nnotes, this is somewhat wasteful, but not prohibitively expensive. For the \ncase with > 64M notes, performance will start to degrade. The big advantage \nwith this approach is that when this is hardcoded into the notes code, we \nhave regained the property that notes for a given commit have exactly _one_ \nunique position in the notes tree across all installations (enabling us to \nfall back on the regular merge strategy).\n\n> What's the recommended way to work with this system from the end user's\n> point of view in a distirbuted environment?\n\nThe end user should not know or care about what fanout scheme is used. \nEverything should be handled seamlessly by the code.\n\n> Somebody up in the project is supposed to decide what fan-out is to be\n> used for the whole project and everybody should follow that structure?\n\nNope, the code should decide which fanout scheme to use.\n\n> If a participant in the project forgets that rule (or makes a mistake), a\n> notes tree that mistakenly merges his notes tree becomes practically\n> useless?\n\nNo. Again this should be invisible to the user.\n\n> If so, perhaps we would need a mechanism to avoid such a mistake from\n> happening?\n\nThe notes code should prevent notes that violate the fanout scheme from \nbeing created.\n\nThe fanout scheme is not something the user should have to worry about at \nall.\n\n\nI totally understand that you don't want to merge the notes feature before \nthe \"writing\" side is taken care of. As such, this iteration is simply yet \nanother iteration towards that final goal.\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121855","messageId":"200908271149.11003.johan@herland.net","threadId":"20748","inReplyTo":"81b0412b0908270039l7a937c3bmd745274c71526ce1@mail.gmail.com","subject":"Re: [PATCHv4 10/12] notes.c: Implement simple memory pooling of leaf nodes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T09:49:10Z","receivedAt":"2009-08-27T09:49:10Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 27 August 2009, Alex Riesen wrote:\n> On Thu, Aug 27, 2009 at 03:43, Johan Herland wrote:\n> > When allocating a new memory pool, the older pool is leaked, but this\n> > is no worse than the current situation, where (pretty much) all\n> > leaf_nodes are leaked anyway.\n>\n> Could you return the unused nodes back into the mempool?\n> By making the pool a preallocated list, perhaps?\n\nYes, maintaining a free-list is certainly possible. However, the number of \nfree()d leaf_nodes is relatively small (only subtree entries are free()d \nafter unpacking them into the tree structure), so I'm not sure it pays off, \nruntime-wise.\n\n> And then it is trivial to provide a deallocation function for the\n> mempool, which something really concerned about the memleak can call\n> (like when or if libgit get more usable in an application context).\n\nYes, I plan to provide a free_notes() function that free()s all the memory \nassociated with the notes data structure. This would of course keep \nreferences to all the mempools, and deallocate them (along with all the \nint_nodes).\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121858","messageId":"alpine.DEB.1.00.0908271139520.7562@intel-tinevez-2-302","threadId":"20748","inReplyTo":"7v7hwp6ebb.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-27T10:42:08Z","receivedAt":"2009-08-27T10:42:08Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 26 Aug 2009, Junio C Hamano wrote:\n\n> Johan Herland writes:\n> \n> > The semantics used when parsing notes trees (with regards to fanout subtrees)\n> > follow Dscho's proposal fairly closely:\n> > - No concatenation/merging of notes is performed. If there are several notes\n> > objects referencing a given commit, only one of those objects are used.\n> > - If a notes object for a given commit is present in the \"root\" notes tree,\n> > no subtrees are consulted; the object in the root tree is used directly.\n> > - If there are more than one subtree that prefix-matches the given commit,\n> > only the subtree with the longest matching prefix is consulted. This\n> > means that if the given commit is e.g. \"deadbeef\", and the notes tree have\n> > subtrees \"de\" and \"dead\", then the following paths in the notes tree are\n> > searched: \"deadbeef\", \"dead/beef\". Note that \"de/adbeef\" is NOT searched.\n> > - Fanout directories (subtrees) must references a whole number of bytes\n> > from the SHA1 sum they subdivide. E.g. subtrees \"dead\" and \"de\" are\n> > acceptable; \"d\" and \"dea\" are not.\n> > - Multiple levels of fanout are allowed. All the above rules apply\n> > recursively. E.g. \"de/adbeef\" is preferred over \"de/adbe/ef\", etc.\n> \n> If I am reading this correctly, the earlier parts of the series were\n> aiming to let multiple people to add notes to the same commit more or less\n> uncordinated while still allowing to merge them sensibly, but now such a\n> workflow becomes impossible with this change. \n> \n> The above claims notes trees with different levels of fan-out are allowed,\n> but what it really means is that merging notes trees with different levels\n> of fan-out will produce a useless result that records notes for the same\n> commit in different blobs all over the notes tree, and asking the notes\n> mechanism to give the notes for one commit will give only one piece that\n> originates in the tree whose creator happened to have used the longest\n> prefix while ignoring all others. It may _allow_ such a layout, but how\n> would such semantics be useful in the first place?\n> \n> I suspect that I am missing something but my gut feeling is that this\n> change turns an interesting hack (even though it might be expensive) into\n> a hack that is not useful at all in the real world, without some order,\n> discipline, or guideline is applied.\n> \n> What's the recommended way to work with this system from the end user's\n> point of view in a distirbuted environment? Somebody up in the project is\n> supposed to decide what fan-out is to be used for the whole project and\n> everybody should follow that structure? If a participant in the project\n> forgets that rule (or makes a mistake), a notes tree that mistakenly\n> merges his notes tree becomes practically useless? If so, perhaps we\n> would need a mechanism to avoid such a mistake from happening?\n\nHmm...\n\nMaybe you're right (and mugwump was right all along) that _all_ matching \nnotes should be shown...\n\nCiao,\nDscho\n"},{"id":"121859","messageId":"alpine.DEB.1.00.0908271243120.7562@intel-tinevez-2-302","threadId":"20748","inReplyTo":"200908271135.31794.johan@herland.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-27T10:47:49Z","receivedAt":"2009-08-27T10:47:49Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 27 Aug 2009, Johan Herland wrote:\n\n> On Thursday 27 August 2009, Junio C Hamano wrote:\n\n> > Somebody up in the project is supposed to decide what fan-out is to be \n> > used for the whole project and everybody should follow that structure?\n> \n> Nope, the code should decide which fanout scheme to use.\n\nI half-agree, the code should decide which fanout scheme to use, but \n_only_ when producing new notes.\n\nI imagine that it could merge the existing notes, and try to make sure \nthat there are no more blobs in a given subtree than a certain threshold; \nif that threshold is reached, it could fan-out using 2-digit subtrees, \nmerging what needs merging (by concatenation) along the way.\n\nThe natural precedence of shallower paths/longer basenames should cope \nwell with that (i.e. prefer to show abcd/... over ab/cd/...).\n\nCiao,\nDscho\n"},{"id":"121914","messageId":"7vtyztq8nv.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"200908271135.31794.johan@herland.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-27T20:55:00Z","receivedAt":"2009-08-27T20:55:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n> 2. Simply decide on a constant 2/2/36 fanout. For the case with < 256K \n> notes, this is somewhat wasteful, but not prohibitively expensive. For the \n> case with > 64M notes, performance will start to degrade. The big advantage \n> with this approach is that when this is hardcoded into the notes code, we \n> have regained the property that notes for a given commit have exactly _one_ \n> unique position in the notes tree across all installations (enabling us to \n> fall back on the regular merge strategy).\n\nI thought it was Gitney who suggested to use a top-level fan-out based on\nthe committer-date. If you typically have already parsed the commit when\nyou want to look up notes objects for it, it won't have extra overhead,\nand when looking at only recent history it will only need to access a\nsmall subset of trees. I thought it was a neat idea (except that the\nquestion becomes what the granularity of the top level fan-out should\nbe---one a day? one a month?---the optimum would depend on commit\ndensity). Was that idea shot down for some reason?\n"},{"id":"121915","messageId":"7vprahq8iv.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"alpine.DEB.1.00.0908271243120.7562@intel-tinevez-2-302","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-27T20:58:00Z","receivedAt":"2009-08-27T20:58:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> I half-agree, the code should decide which fanout scheme to use, but \n> _only_ when producing new notes.\n>\n> I imagine that it could merge the existing notes, and try to make sure \n> that there are no more blobs in a given subtree than a certain threshold; \n> if that threshold is reached, it could fan-out using 2-digit subtrees, \n> merging what needs merging (by concatenation) along the way.\n>\n> The natural precedence of shallower paths/longer basenames should cope \n> well with that (i.e. prefer to show abcd/... over ab/cd/...).\n\nOh, if the plan for merging the trees is such that it takes care of\n\"multiple notes pointing at the same commit\" issues like you outline, then\nI can see it would work nicely.\n\nAt that point, fan-out would become merely an implementation detail,\nsomething the end user never needs to worry about, just like what base\nobject is chosen to represent another object in a packfile.\n"},{"id":"121919","messageId":"20090827212710.GV1033@spearce.org","threadId":"20748","inReplyTo":"7vtyztq8nv.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-08-27T21:27:10Z","receivedAt":"2009-08-27T21:27:10Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Johan Herland writes:\n> > 2. Simply decide on a constant 2/2/36 fanout.\n> \n> I thought it was Gitney who suggested to use a top-level fan-out based on\n> the committer-date. If you typically have already parsed the commit when\n> you want to look up notes objects for it, it won't have extra overhead,\n> and when looking at only recent history it will only need to access a\n> small subset of trees. I thought it was a neat idea (except that the\n> question becomes what the granularity of the top level fan-out should\n> be---one a day? one a month?---the optimum would depend on commit\n> density). Was that idea shot down for some reason?\n\nYea, it was me. I still think it might be a useful idea, since\nit allows you better density of loading notes when parsing the\nrecent commits. In theory the last 256 commits can easly be in\neach of the 2/ fanout buckets, making 2/38 pointless for reducing\nthe search space. Commit date on the other hand can probably force\nall of them into the same bucket, making it easy to have the last\n256 commits in cache, from a single bucket.\n\nBut I thought you shot it down, by saying that we also wanted to\nsupport notes on blobs. I happen to see no value in a note on\na blob, a blob alone doesn't make much sense without at least an\nannotated tag or commit to provide it some named context, and the\nlatter two have dates.\n\n-- \nShawn.\n"},{"id":"121926","messageId":"7vy6p5ncz0.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"20090827212710.GV1033@spearce.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-27T21:50:11Z","receivedAt":"2009-08-27T21:50:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> Yea, it was me. I still think it might be a useful idea, since\n> it allows you better density of loading notes when parsing the\n> recent commits. In theory the last 256 commits can easly be in\n> each of the 2/ fanout buckets, making 2/38 pointless for reducing\n> the search space. Commit date on the other hand can probably force\n> all of them into the same bucket, making it easy to have the last\n> 256 commits in cache, from a single bucket.\n>\n> But I thought you shot it down, by saying that we also wanted to\n> support notes on blobs. I happen to see no value in a note on\n> a blob, a blob alone doesn't make much sense without at least an\n> annotated tag or commit to provide it some named context, and the\n> latter two have dates.\n\nYeah, and in this thread everybody seems to be talking about commits so I\nthink it is fine to limit notes only to commits.\n"},{"id":"121935","messageId":"200908280043.44261.johan@herland.net","threadId":"20748","inReplyTo":"200908271149.11003.johan@herland.net","subject":"Re: [PATCHv4 10/12] notes.c: Implement simple memory pooling of leaf nodes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T22:43:44Z","receivedAt":"2009-08-27T22:43:44Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 27 August 2009, Johan Herland wrote:\n> On Thursday 27 August 2009, Alex Riesen wrote:\n> > On Thu, Aug 27, 2009 at 03:43, Johan Herland wrote:\n> > > When allocating a new memory pool, the older pool is leaked, but this\n> > > is no worse than the current situation, where (pretty much) all\n> > > leaf_nodes are leaked anyway.\n> >\n> > Could you return the unused nodes back into the mempool?\n> > By making the pool a preallocated list, perhaps?\n>\n> Yes, maintaining a free-list is certainly possible. However, the number\n> of free()d leaf_nodes is relatively small (only subtree entries are\n> free()d after unpacking them into the tree structure), so I'm not sure it\n> pays off, runtime-wise.\n\nI played around with the free-list idea, but it cost more than the memory \npooling code saved in the first place. I'm leaning towards dropping the \nwhole memory pooling idea, as the small run-time improvement is probably not \nworth the added complexity. We'll see. I'll re-evaluate once I've refactored \nthe code according to the other threads of this discussion.\n\n> > And then it is trivial to provide a deallocation function for the\n> > mempool, which something really concerned about the memleak can call\n> > (like when or if libgit get more usable in an application context).\n>\n> Yes, I plan to provide a free_notes() function that free()s all the\n> memory associated with the notes data structure. This would of course\n> keep references to all the mempools, and deallocate them (along with all\n> the int_nodes).\n\nThis still stands, of course. Should be part of the next iteration.\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121937","messageId":"200908280103.06015.johan@herland.net","threadId":"20748","inReplyTo":"7vy6p5ncz0.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-27T23:03:05Z","receivedAt":"2009-08-27T23:03:05Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 27 August 2009, Junio C Hamano wrote:\n> \"Shawn O. Pearce\" writes:\n> > Yea, it was me. I still think it might be a useful idea, since\n> > it allows you better density of loading notes when parsing the\n> > recent commits. In theory the last 256 commits can easly be in\n> > each of the 2/ fanout buckets, making 2/38 pointless for reducing\n> > the search space. Commit date on the other hand can probably force\n> > all of them into the same bucket, making it easy to have the last\n> > 256 commits in cache, from a single bucket.\n> >\n> > But I thought you shot it down, by saying that we also wanted to\n> > support notes on blobs. I happen to see no value in a note on\n> > a blob, a blob alone doesn't make much sense without at least an\n> > annotated tag or commit to provide it some named context, and the\n> > latter two have dates.\n>\n> Yeah, and in this thread everybody seems to be talking about commits so I\n> think it is fine to limit notes only to commits.\n\nAgreed. I'm starting to come around to the idea of storing them in subtrees \nbased on commit dates. For one, you don't have multiple notes for one commit \nin the same notes tree. Also, the common-case access pattern seems tempting.\n\nDscho: Were there other problems with the date-based approach other than not \nsupporting notes on trees and blobs?\n\nIf not, I'll start preparing another series with the date-based approach.\n\n\nThanks for the input, guys. :)\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121940","messageId":"20090827233900.GA7347@coredump.intra.peff.net","threadId":"20748","inReplyTo":"200908280103.06015.johan@herland.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-08-27T23:39:00Z","receivedAt":"2009-08-27T23:39:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 28, 2009 at 01:03:05AM +0200, Johan Herland wrote:\n\n> Agreed. I'm starting to come around to the idea of storing them in subtrees \n> based on commit dates. For one, you don't have multiple notes for one commit \n> in the same notes tree. Also, the common-case access pattern seems tempting.\n> \n> Dscho: Were there other problems with the date-based approach other than not \n> supporting notes on trees and blobs?\n> \n> If not, I'll start preparing another series with the date-based approach.\n\nWould you ever want to load a note for a commit when you did not have\nthat commit present (in which case you would not know its date)?\n\n-Peff\n"},{"id":"121941","messageId":"7viqg8hj98.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"20090827233900.GA7347@coredump.intra.peff.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-28T00:30:59Z","receivedAt":"2009-08-28T00:30:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Aug 28, 2009 at 01:03:05AM +0200, Johan Herland wrote:\n>\n>> Agreed. I'm starting to come around to the idea of storing them in subtrees \n>> based on commit dates. For one, you don't have multiple notes for one commit \n>> in the same notes tree. Also, the common-case access pattern seems tempting.\n>> \n>> Dscho: Were there other problems with the date-based approach other than not \n>> supporting notes on trees and blobs?\n>> \n>> If not, I'll start preparing another series with the date-based approach.\n>\n> Would you ever want to load a note for a commit when you did not have\n> that commit present (in which case you would not know its date)?\n\nYou cannot \"git show\" nor \"git checkout\" it, nor have reached it via \"git\nbisect\". How did you get interested in the commit in the first place?\n\nWhat is the reason you are not fetching the commit after you somehow got\ninterested in the commit?\n\nHere is one possible scenario I can think of. The notes tree is published\nand distributed more widely than the project's main source. You fetch and\nusually follow notes tree (which would probably be more lightweight) but\nnot the source. Perhaps your bug tracking system is based on notes, and\nthe project is throwing all the bugs in one such notes tree. You are a\nbug tracking person, and you are following the notes tree closely, but are\nonly following the 'master' branch but not 'next' nor 'pu'.\n\nAnd you somehow browse through the 'notes' tree, and learn that a note\nrefers to an interesting commit. But the commit the note applies to is\nnot yet in 'master' so you do not have it. Even though you would want to\nfetch 'next' and 'pu', you are having connection problem and you cannot\nfetch the source until your ISP gets back online tomorrow morning.\n\nNah, that's not a plausible scenario---at that point you already have read\nthe note.\n\nSo, how?\n"},{"id":"121942","messageId":"fabb9a1e0908271740i53ec7d69td696d955366ad23c@mail.gmail.com","threadId":"20748","inReplyTo":"7viqg8hj98.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-08-28T00:40:20Z","receivedAt":"2009-08-28T00:40:20Z","isPatch":false,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Thu, Aug 27, 2009 at 17:30, Junio C Hamano wrote:\n> So, how?\n\nA note in branch foo (which you do not follow) was referenced by a\ncommit in branch bar (which you do follow)?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"121946","messageId":"7vocq0d86p.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"fabb9a1e0908271740i53ec7d69td696d955366ad23c@mail.gmail.com","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-28T01:43:42Z","receivedAt":"2009-08-28T01:43:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sverre Rabbelier writes:\n\n> Heya,\n>\n> On Thu, Aug 27, 2009 at 17:30, Junio C Hamano wrote:\n>> So, how?\n>\n> A note in branch foo (which you do not follow) was referenced by a\n> commit in branch bar (which you do follow)?\n\nSorry, I do not follow. How does a note be _in_ branch foo, and how does\na commit _reference_ a note?\n\nDid you mean \"a commit in branch bar referred to a commit in branch foo\",\nsimilar to the way the \"cherry-picked from X\" comment can refer to a\nmissing commit?\n"},{"id":"121950","messageId":"fabb9a1e0908271951t1f2db976jb1de1e7687ad9791@mail.gmail.com","threadId":"20748","inReplyTo":"7vocq0d86p.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-08-28T02:51:48Z","receivedAt":"2009-08-28T02:51:48Z","isPatch":false,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Thu, Aug 27, 2009 at 18:43, Junio C Hamano wrote:\n> Did you mean \"a commit in branch bar referred to a commit in branch foo\",\n> similar to the way the \"cherry-picked from X\" comment can refer to a\n> missing commit?\n\nYes, sorry, I meant referred to in the commit message.\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"121952","messageId":"7v4orsbpzd.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"fabb9a1e0908271951t1f2db976jb1de1e7687ad9791@mail.gmail.com","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-28T03:02:14Z","receivedAt":"2009-08-28T03:02:14Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sverre Rabbelier writes:\n\n> On Thu, Aug 27, 2009 at 18:43, Junio C Hamano wrote:\n>> Did you mean \"a commit in branch bar referred to a commit in branch foo\",\n>> similar to the way the \"cherry-picked from X\" comment can refer to a\n>> missing commit?\n>\n> Yes, sorry, I meant referred to in the commit message.\n\nIn such a case would you rather want to see the commit itself first, or at\nleast, commit _and_ notes _together_?\n\nI admit that this all depends on what application the notes are used for,\nbut I am suffering from lack of imagination to come up with a plausible\nscenario in which you would want to look at the notes to that missing\ncommit first, without getting the commit itself.\n"},{"id":"121953","messageId":"fabb9a1e0908272005i4bf9b906xba08a711d384dd83@mail.gmail.com","threadId":"20748","inReplyTo":"7v4orsbpzd.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-08-28T03:05:31Z","receivedAt":"2009-08-28T03:05:31Z","isPatch":false,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Thu, Aug 27, 2009 at 20:02, Junio C Hamano wrote:\n> In such a case would you rather want to see the commit itself first, or at\n> least, commit _and_ notes _together_?\n\nAssuming you do download all notes, I think it would be nice to be\nable to read the note; and since there's no way to download the commit\nseparately it would require one to guess which head the commit belongs\nto and fetch the entire branch...?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"121955","messageId":"7vmy5ka9w4.fsf@alter.siamese.dyndns.org","threadId":"20748","inReplyTo":"fabb9a1e0908272005i4bf9b906xba08a711d384dd83@mail.gmail.com","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-28T03:35:07Z","receivedAt":"2009-08-28T03:35:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sverre Rabbelier writes:\n\n> On Thu, Aug 27, 2009 at 20:02, Junio C Hamano wrote:\n>> In such a case would you rather want to see the commit itself first, or at\n>> least, commit _and_ notes _together_?\n>\n> Assuming you do download all notes, I think it would be nice to be\n> able to read the note; and since there's no way to download the commit\n> separately it would require one to guess which head the commit belongs\n> to and fetch the entire branch...?\n\nSome random thoughts...\n\n * If there are very many branches (in the worst case, they are so many\n that the upstream uses the expand extention to serve the project),\n maybe the notes namespace will also have many branches. It is unclear\n how a user is expected to know which notes branch a note to a\n particular commit is to be found.\n\n * Perhaps to solve that problem, such a project may use notes in the\n corresponding \"notes branch\"? Then your assumption does not hold, as\n you first guess which notes branch to fetch to find the note that may\n not even exist for this issue to become a real problem.\n\n * If you assume all the notes are downloaded in such a project, you can\n still go through all the top-level trees (that are date based fan-out)\n and find the note to the commit object you do not have. At that point,\n it only becomes performance issue for an unusual case where you have\n a note but the commit the note applies to.\n"},{"id":"121986","messageId":"alpine.DEB.1.00.0908281046560.7434@intel-tinevez-2-302","threadId":"20748","inReplyTo":"7vprahq8iv.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-28T08:48:08Z","receivedAt":"2009-08-28T08:48:08Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 27 Aug 2009, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > I half-agree, the code should decide which fanout scheme to use, but \n> > _only_ when producing new notes.\n> >\n> > I imagine that it could merge the existing notes, and try to make sure \n> > that there are no more blobs in a given subtree than a certain \n> > threshold; if that threshold is reached, it could fan-out using \n> > 2-digit subtrees, merging what needs merging (by concatenation) along \n> > the way.\n> >\n> > The natural precedence of shallower paths/longer basenames should cope \n> > well with that (i.e. prefer to show abcd/... over ab/cd/...).\n> \n> Oh, if the plan for merging the trees is such that it takes care of \n> \"multiple notes pointing at the same commit\" issues like you outline, \n> then I can see it would work nicely.\n> \n> At that point, fan-out would become merely an implementation detail, \n> something the end user never needs to worry about, just like what base \n> object is chosen to represent another object in a packfile.\n\nOh, that's where you're coming from! Now I understand your concerns; it \nnever occurred to me that the user should be encouraged to add notes to \nthe tree herself. I was always under the impression that the fan-out is \nan implementation detail best hidden from the user.\n\nCiao,\nDscho\n"},{"id":"121987","messageId":"alpine.DEB.1.00.0908281048320.7434@intel-tinevez-2-302","threadId":"20748","inReplyTo":"200908280103.06015.johan@herland.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-28T08:51:21Z","receivedAt":"2009-08-28T08:51:21Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 28 Aug 2009, Johan Herland wrote:\n\n> On Thursday 27 August 2009, Junio C Hamano wrote:\n> > \"Shawn O. Pearce\" writes:\n> > > Yea, it was me. I still think it might be a useful idea, since it \n> > > allows you better density of loading notes when parsing the recent \n> > > commits. In theory the last 256 commits can easly be in each of the \n> > > 2/ fanout buckets, making 2/38 pointless for reducing the search \n> > > space. Commit date on the other hand can probably force all of them \n> > > into the same bucket, making it easy to have the last 256 commits in \n> > > cache, from a single bucket.\n> > >\n> > > But I thought you shot it down, by saying that we also wanted to \n> > > support notes on blobs. I happen to see no value in a note on a \n> > > blob, a blob alone doesn't make much sense without at least an \n> > > annotated tag or commit to provide it some named context, and the \n> > > latter two have dates.\n> >\n> > Yeah, and in this thread everybody seems to be talking about commits \n> > so I think it is fine to limit notes only to commits.\n> \n> Agreed. I'm starting to come around to the idea of storing them in \n> subtrees based on commit dates. For one, you don't have multiple notes \n> for one commit in the same notes tree. Also, the common-case access \n> pattern seems tempting.\n> \n> Dscho: Were there other problems with the date-based approach other than \n> not supporting notes on trees and blobs?\n\nIt emphasized an implementation detail too much for my liking.\n\nAnd I would rather have some flexibility in the code as to _when_ it fans \nout and when not.\n\nSo I can easily imagine a full repository which has only, say, 5 notes. \nWhy not have a single tree for all of those?\n\nAnd I can easily imagine a repository that has a daily note generated by \nan automatic build, and no other notes. The date-based fan-out just \nwastes our time here, and even hurts performance.\n\nCiao,\nDscho\n"},{"id":"121993","messageId":"200908281240.13311.johan@herland.net","threadId":"20748","inReplyTo":"alpine.DEB.1.00.0908281048320.7434@intel-tinevez-2-302","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-28T10:40:12Z","receivedAt":"2009-08-28T10:40:12Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Friday 28 August 2009, Johannes Schindelin wrote:\n> Hi,\n>\n> On Fri, 28 Aug 2009, Johan Herland wrote:\n> > On Thursday 27 August 2009, Junio C Hamano wrote:\n> > > \"Shawn O. Pearce\" writes:\n> > > > Yea, it was me. I still think it might be a useful idea, since\n> > > > it allows you better density of loading notes when parsing the\n> > > > recent commits. In theory the last 256 commits can easly be in\n> > > > each of the 2/ fanout buckets, making 2/38 pointless for\n> > > > reducing the search space. Commit date on the other hand can\n> > > > probably force all of them into the same bucket, making it easy\n> > > > to have the last 256 commits in cache, from a single bucket.\n> > > >\n> > > > But I thought you shot it down, by saying that we also wanted\n> > > > to support notes on blobs. I happen to see no value in a note\n> > > > on a blob, a blob alone doesn't make much sense without at\n> > > > least an annotated tag or commit to provide it some named\n> > > > context, and the latter two have dates.\n> > >\n> > > Yeah, and in this thread everybody seems to be talking about\n> > > commits so I think it is fine to limit notes only to commits.\n> >\n> > Agreed. I'm starting to come around to the idea of storing them in\n> > subtrees based on commit dates. For one, you don't have multiple\n> > notes for one commit in the same notes tree. Also, the common-case\n> > access pattern seems tempting.\n> >\n> > Dscho: Were there other problems with the date-based approach other\n> > than not supporting notes on trees and blobs?\n>\n> It emphasized an implementation detail too much for my liking.\n>\n> And I would rather have some flexibility in the code as to _when_ it\n> fans out and when not.\n>\n> So I can easily imagine a full repository which has only, say, 5\n> notes. Why not have a single tree for all of those?\n\nYes, if you only have a handful of notes, the date-based approach is \ndefinitely overkill. On the other hand, if you only have a handful of \nnotes, performance is not going to be a problem in the first place, no \nmatter which notes structure you use...\n\n> And I can easily imagine a repository that has a daily note generated\n> by an automatic build, and no other notes. The date-based fan-out\n> just wastes our time here, and even hurts performance.\n\nWhat about a month-based fanout? Looking at the kernel repo with\n\n git log --all --date=iso --format=\"%ad\" |\n cut -c1-7 | sort | uniq -c | sort -n\n\nI find that commits are spread across 66 months, and the most active \nmonth (2008-07) has 5661 commits. If we assume the one-note-per-commit \nworst case, that gives up to 5661 notes per month-based subdir. Is that \ntoo much?\n\nDoing\n\n for subdir in $(find . -type d); do\n echo \"$(ls -1 $subdir | wc -l) $subdir\"\n done | sort -n\n\nshows me that the currently largest tree in the kernel has 985 entries \n(include/linux), so a 5661-entry tree is probably larger than what git \nis used to...\n\n...just thinking that we shold make things as simple as possible (but no \nsimpler), and if a month-based fanout works adequately in all practical \ncases, then we should go with that...\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121996","messageId":"alpine.DEB.1.00.0908281349270.7434@intel-tinevez-2-302","threadId":"20748","inReplyTo":"200908281240.13311.johan@herland.net","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-28T11:56:06Z","receivedAt":"2009-08-28T11:56:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 28 Aug 2009, Johan Herland wrote:\n\n> On Friday 28 August 2009, Johannes Schindelin wrote:\n>\n> > And I can easily imagine a repository that has a daily note generated \n> > by an automatic build, and no other notes. The date-based fan-out \n> > just wastes our time here, and even hurts performance.\n> \n> What about a month-based fanout?\n\nWell, I hoped to convince you that the date-based approach is too rigid. \nYou basically cannot adapt the optimal data layout to the available data.\n\n(I like to think of this issue as related to storing deltas: we let Git \nchoose relatively freely what to delta against, and do not force a delta \nagainst the parent commit like others do; I think it is pretty obvious \nthat our approach is more powerful.)\n\nSo the simplest (yet powerful-enough) way I could imagine is to teach the \nreading part to accept any fan-out (but that fan-out is really only based \non the object name, nothing else), and to adjust the writing/merging part \nsuch that it has a maximum bin size (i.e. it starts a new fan-out whenever \na tree object contains more than a config-specifyable limit).\n\nI was certainly not thinking of something as complicated as Huffman.\n\nCiao,\nDscho\n"},{"id":"122004","messageId":"200908281615.49465.johan@herland.net","threadId":"20748","inReplyTo":"alpine.DEB.1.00.0908281349270.7434@intel-tinevez-2-302","subject":"Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-28T14:15:48Z","receivedAt":"2009-08-28T14:15:48Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Friday 28 August 2009, Johannes Schindelin wrote:\n> On Fri, 28 Aug 2009, Johan Herland wrote:\n> > On Friday 28 August 2009, Johannes Schindelin wrote:\n> > > And I can easily imagine a repository that has a daily note\n> > > generated by an automatic build, and no other notes. The\n> > > date-based fan-out just wastes our time here, and even hurts\n> > > performance.\n> >\n> > What about a month-based fanout?\n>\n> Well, I hoped to convince you that the date-based approach is too\n> rigid. You basically cannot adapt the optimal data layout to the\n> available data.\n>\n> (I like to think of this issue as related to storing deltas: we let\n> Git choose relatively freely what to delta against, and do not force\n> a delta against the parent commit like others do; I think it is\n> pretty obvious that our approach is more powerful.)\n>\n> So the simplest (yet powerful-enough) way I could imagine is to teach\n> the reading part to accept any fan-out (but that fan-out is really\n> only based on the object name, nothing else), and to adjust the\n> writing/merging part such that it has a maximum bin size (i.e. it\n> starts a new fan-out whenever a tree object contains more than a\n> config-specifyable limit).\n\nI agree with your points on flexibility and not nailing down a structure \nthat might prove too rigid in the future.\n\nBut it seems the date-based approach might offer wins that an \nobject-name-based approach (flexible or not) simply cannot hope to \nmatch...\n\nAlso a rigid organization (with unique note locations) makes the \nimplementation simpler and faster: If you allow notes for a given \ncommit at several places in the notes tree (and require the result to \nbe the concatenation of those notes, which seems to be the saner \nchoice), the lookup procedure must keep looking even after it has found \nthe first match. This affects both runtime and memory consumption \nnegatively (more subtrees must be unpacked, etc.)\n\nI guess I'll code up both alternatives so that we can get some actual \nnumbers...\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"}]}