[RFC/PATCHv7 00/22] git notes

[RFC/PATCHv7 00/22] git notes

[Johan Herland]

Hi,

(Feel free to put this on hold until v1.6.5 is released. In any case,
I'm going to Berlin for the weekend, and don't expect to read much
email...)

Here is the 7th iteration of the git-notes series. Changes in this
iteration are as follows:

- Rebased onto current 'next'

- Patch 1: Include minor leak fix

- Patch 10: Rename free_commit_notes() to free_notes() (Notes are
  no longer bound to commits only, see patch 15 for details)

- Patch 12: Remove tests that are invalidated by concatenation code
  in patch 13.

Overall, I consider the 12 first patches fairly stable at this point.
There's also a slew of new patches, that has more of an RFC status:

- Patches 13-14: Concatenation of multiple notes annotating the same
  commit/object. This was originally suggested by mugwump many months
  ago, and the suggestion was re-iterated by Dscho. This change has a
  minor perfomance impact (see [1]), but I still think it's worth it.

- Patch 15: Allow notes to be attached to any object (not just commits).
  Rename get_commit_notes() to format_note() to reflect this change.

- Patch 16-19: Expand notes API in preparation for querying and
  manipulating notes from elsewhere in Git (see patch 22 for examples).

- Patch 20: Add a new notes_tree struct, and use it as the first
  parameter to all functions in the notes API. This allows API users to
  maintain their own (multiple, concurrent) notes trees (see patch 22
  for an example). We still have a default notes tree in notes.c as a
  fallback (when NULL is passed as to an API function).

- Patch 21: The default behaviour when there are multiple notes for a
  given object is to concatenate them. However, some callers (see patch
  22) want to tweak this behaviour. This patch defines a new function
  type: combine_notes_fn, for combining two notes that reference the
  same object. The notes API is then expanded to allow the caller to
  specify a suitable combine_notes_fn. For convenience, three simple
  combine_notes functions are available in the notes API:
  - combine_notes_concatenate(): Concatenates the contents of the two
    notes. (This is the default behaviour)
  - combine_notes_overwrite(): Overwrite the existing note with the
    new note.
  - combine_notes_ignore(): Keep the existing note, and ignore the new
    note.

- Patch 22: This teaches fast-import to use the new notes API when
  adding note objects to a commit. Since adding a note to a notes tree
  might cause restructuring of that notes tree, the note objects must
  be handled differently from regular blobs.
  There are some testcases for the new behaviour in this patch, but not
  enough. These will be added later.
  This patch is still very much in RFC mode...


Although this iteration brings the jh/notes topic towards feature-
completion, there are still some things left to do before I consider
the git notes feature fully complete:

- Builtin-ify git-notes shell script to take advantage of notes API

- Garbage-collect notes whose referenced objects are unreachable

- Handle note objects that are not blobs, but trees (e.g.
  refs/notes/<topic>:<commit>/<subtopic>)

- Add a simple notation for referring to an object's note (e.g.
  "<object>^{note}")

- Probably more that I haven't thought of yet...

However, It might be a good idea to consider merging the early/stable
parts of jh/notes, instead of waiting for everything to complete.


Have fun! :)

...Johan


[1] Performance impact of the concatenation rewrite.

In order to concatenate notes correctly, the tree traversal code must be
changed to more proactively unpack subtree entries (so that we can safely
determine whether there are multiple notes for a given key).

As before, the test case is as follows:
Linux kernel repo with 157101 commits, 1 note per commit, organized into
various fanout schemes. Hardware is Intel Core 2 Quad with 4GB RAM.


Algorithm / Notes tree   git log -n10 (x100)   git log --all

next / no-notes                 4.78s             63.90s

before / no-notes               4.77s             63.61s
before / no-fanout             56.59s             65.19s

16tree / no-notes               4.73s             63.80s
16tree / no-fanout             30.21s             65.11s
16tree / 2_38                   5.53s             65.24s
16tree / 2_2_36                 5.15s             65.12s

concat / no-notes               4.80s             64.21s
concat / no-fanout             30.66s             65.35s
concat / 2_38                   5.64s             65.87s
concat / 2_2_36                 5.23s             66.44s

Conclusion: There is a small, but measurable impact (about .1s or so in
the 100 x 'git log -n10' case), but I think this is small enough to be
acceptable.


Johan Herland (17):
  Teach "-m <msg>" and "-F <file>" to "git notes edit"
  fast-import: Add support for importing commit notes
  t3302-notes-index-expensive: Speed up create_repo()
  Add flags to get_commit_notes() to control the format of the note string
  Teach notes code to free its internal data structures on request
  Teach the notes lookup code to parse notes trees with various fanout schemes
  Add selftests verifying that we can parse notes trees with various fanouts
  Refactor notes code to concatenate multiple notes annotating the same object
  Add selftests verifying concatenation of multiple notes for the same commit
  Notes API: get_commit_notes() -> format_note() + remove the commit restriction
  Notes API: init_notes(): Initialize the notes tree from the given notes ref
  Notes API: add_note(): Add note objects to the internal notes tree structure
  Notes API: get_note(): Return the note annotating the given object
  Notes API: for_each_note(): Traverse the entire notes tree with a callback
  Notes API: Allow multiple concurrent notes trees with new struct notes_tree
  Refactor notes concatenation into a flexible interface for combining notes
  fast-import: Proper notes tree manipulation using the notes API

Johannes Schindelin (5):
  Introduce commit notes
  Add a script to edit/inspect notes
  Speed up git notes lookup
  Add an expensive test for git-notes
  Add '%N'-format for pretty-printing commit notes

 .gitignore                        |    1 +
 Documentation/config.txt          |   13 +
 Documentation/git-fast-import.txt |   45 +++-
 Documentation/git-notes.txt       |   60 ++++
 Documentation/pretty-formats.txt  |    1 +
 Makefile                          |    3 +
 cache.h                           |    4 +
 command-list.txt                  |    1 +
 commit.c                          |    1 +
 config.c                          |    5 +
 environment.c                     |    1 +
 fast-import.c                     |  176 +++++++++++-
 git-notes.sh                      |  121 ++++++++
 notes.c                           |  579 +++++++++++++++++++++++++++++++++++++
 notes.h                           |  113 +++++++
 pretty.c                          |   10 +
 t/t3301-notes.sh                  |  150 ++++++++++
 t/t3302-notes-index-expensive.sh  |  118 ++++++++
 t/t3303-notes-subtrees.sh         |  188 ++++++++++++
 t/t9300-fast-import.sh            |  296 +++++++++++++++++++
 20 files changed, 1875 insertions(+), 11 deletions(-)
 create mode 100644 Documentation/git-notes.txt
 create mode 100755 git-notes.sh
 create mode 100644 notes.c
 create mode 100644 notes.h
 create mode 100755 t/t3301-notes.sh
 create mode 100755 t/t3302-notes-index-expensive.sh
 create mode 100755 t/t3303-notes-subtrees.sh

[RFC/PATCHv7 00/22] git notes

[Johan Herland]

Hi,

Here is the 7th iteration of the git-notes series. Changes in this
iteration are as follows:

- Rebased onto current 'next'

- Patch 1: Include minor leak fix

- Patch 10: Rename free_commit_notes() to free_notes() (Notes are
  no longer bound to only commits, see patch 15 for details)

- Patch 12: Remove tests that are invalidated by concatenation code
  in patch 13.

There's also a slew of new patches:

- Patches 13-14: Concatenation of multiple notes annotating the same
  commit/object. This was originally suggested by mugwump many months
  ago, and the suggestion was re-iterated by Dscho. This change has a
  minor perfomance impact (see [1]), but I still think it's worth it.

- Patch 15: Allow notes to be attached to any object (not just commits).
  Rename get_commit_notes() to format_note() to reflect this change.

- Patch 16-19: Expand notes API in preparation for querying and manipulating notes from other parts of Git.


TODO:
- Builtin-ify git-notes shell script to take advantage of notes API
- Garbage collect notes whose referenced object is unreachable (gc_notes())
- Handle note objects that are not blobs, but trees

Have fun! :)

...Johan


[1] Performance impact of the concatenation rewrite.

In order to concatenate notes correctly, the tree traversal code must be
changed to more proactively unpack subtree entries (so that we can safely
determine whether there are multiple notes for a given key).

As before, the test case is as follows:
Linux kernel repo with 157101 commits, 1 note per commit, organized into
various fanout schemes. Hardware is Intel Core 2 Quad with 4GB RAM.


Algorithm / Notes tree   git log -n10 (x100)   git log --all

next / no-notes                 4.78s             63.90s

before / no-notes               4.77s             63.61s
before / no-fanout             56.59s             65.19s

16tree / no-notes               4.73s             63.80s
16tree / no-fanout             30.21s             65.11s
16tree / 2_38                   5.53s             65.24s
16tree / 2_2_36                 5.15s             65.12s

concat / no-notes               4.80s             64.21s
concat / no-fanout             30.66s             65.35s
concat / 2_38                   5.64s             65.87s
concat / 2_2_36                 5.23s             66.44s

Conclusion: There is a measurable impact (about .1s or so in the 100 x
'git log -n10' case), but I think this is low enough to be acceptable.


Johan Herland (17):
  Teach "-m <msg>" and "-F <file>" to "git notes edit"
  fast-import: Add support for importing commit notes
  t3302-notes-index-expensive: Speed up create_repo()
  Add flags to get_commit_notes() to control the format of the note string
  Teach notes code to free its internal data structures on request.
  Teach the notes lookup code to parse notes trees with various fanout schemes
  Add selftests verifying that we can parse notes trees with various fanouts
  Refactor notes code to concatenate multiple notes annotating the same object
  Add selftests verifying that multiple notes for the same commits are concatenated correctly
  Notes API: get_commit_notes() -> format_note() + remove the commit restriction
  Notes API: init_notes(): Initialize the notes tree from the given notes ref
  Notes API: add_note(): Add note objects to the internal notes tree structure
  Notes API: get_note(): Return the note annotating the given object
  Notes API: for_each_note(): Traverse the entire notes tree with a callback
  Notes API: Allow multiple concurrent notes trees with new struct notes_tree
  Refactor notes concatenation into a flexible interface for combining notes
  fast-import: Proper notes tree manipulation using the notes API

Johannes Schindelin (5):
  Introduce commit notes
  Add a script to edit/inspect notes
  Speed up git notes lookup
  Add an expensive test for git-notes
  Add '%N'-format for pretty-printing commit notes

 .gitignore                        |    1 +
 Documentation/config.txt          |   13 +
 Documentation/git-fast-import.txt |   45 +++-
 Documentation/git-notes.txt       |   60 ++++
 Documentation/pretty-formats.txt  |    1 +
 Makefile                          |    3 +
 cache.h                           |    4 +
 command-list.txt                  |    1 +
 commit.c                          |    1 +
 config.c                          |    5 +
 environment.c                     |    1 +
 fast-import.c                     |  176 +++++++++++-
 git-notes.sh                      |  121 ++++++++
 notes.c                           |  579 +++++++++++++++++++++++++++++++++++++
 notes.h                           |  121 ++++++++
 pretty.c                          |   10 +
 t/t3301-notes.sh                  |  150 ++++++++++
 t/t3302-notes-index-expensive.sh  |  118 ++++++++
 t/t3303-notes-subtrees.sh         |  188 ++++++++++++
 t/t9300-fast-import.sh            |  296 +++++++++++++++++++
 20 files changed, 1883 insertions(+), 11 deletions(-)
 create mode 100644 Documentation/git-notes.txt
 create mode 100755 git-notes.sh
 create mode 100644 notes.c
 create mode 100644 notes.h
 create mode 100755 t/t3301-notes.sh
 create mode 100755 t/t3302-notes-index-expensive.sh
 create mode 100755 t/t3303-notes-subtrees.sh

[RFC/PATCHv7 01/22] Introduce commit notes

[Johan Herland]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

Commit notes are blobs which are shown together with the commit
message.  These blobs are taken from the notes ref, which you can
configure by the config variable core.notesRef, which in turn can
be overridden by the environment variable GIT_NOTES_REF.

The notes ref is a branch which contains "files" whose names are
the names of the corresponding commits (i.e. the SHA-1).

The rationale for putting this information into a ref is this: we
want to be able to fetch and possibly union-merge the notes,
maybe even look at the date when a note was introduced, and we
want to store them efficiently together with the other objects.

This patch has been improved by the following contributions:
- Thomas Rast: fix core.notesRef documentation
- Tor Arne Vestbø: fix printing of multi-line notes
- Alex Riesen: Using char array instead of char pointer costs less BSS
- Johan Herland: Plug leak when msg is good, but msglen or type causes return

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Tor Arne Vestbø <tavestbo@trolltech.com>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

get_commit_notes(): Plug memory leak when 'if' triggers, but not because of read_sha1_file() failure
---
 Documentation/config.txt |   13 ++++++++
 Makefile                 |    2 +
 cache.h                  |    4 ++
 commit.c                 |    1 +
 config.c                 |    5 +++
 environment.c            |    1 +
 notes.c                  |   70 ++++++++++++++++++++++++++++++++++++++++++++++
 notes.h                  |    7 ++++
 pretty.c                 |    5 +++
 9 files changed, 108 insertions(+), 0 deletions(-)
 create mode 100644 notes.c
 create mode 100644 notes.h

diff --git a/Documentation/config.txt b/Documentation/config.txt
index cc156b8..32b0cdf 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -458,6 +458,19 @@ On some file system/operating system combinations, this is unreliable.
 Set this config setting to 'rename' there; However, This will remove the
 check that makes sure that existing object files will not get overwritten.
 
+core.notesRef::
+	When showing commit messages, also show notes which are stored in
+	the given ref.  This ref is expected to contain files named
+	after the full SHA-1 of the commit they annotate.
++
+If such a file exists in the given ref, the referenced blob is read, and
+appended to the commit message, separated by a "Notes:" line.  If the
+given ref itself does not exist, it is not an error, but means that no
+notes should be printed.
++
+This setting defaults to "refs/notes/commits", and can be overridden by
+the `GIT_NOTES_REF` environment variable.
+
 add.ignore-errors::
 	Tells 'git-add' to continue adding files when some files cannot be
 	added due to indexing errors. Equivalent to the '--ignore-errors'
diff --git a/Makefile b/Makefile
index 8925b1d..9e414db 100644
--- a/Makefile
+++ b/Makefile
@@ -429,6 +429,7 @@ LIB_H += ll-merge.h
 LIB_H += log-tree.h
 LIB_H += mailmap.h
 LIB_H += merge-recursive.h
+LIB_H += notes.h
 LIB_H += object.h
 LIB_H += pack.h
 LIB_H += pack-refs.h
@@ -513,6 +514,7 @@ LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += name-hash.o
+LIB_OBJS += notes.o
 LIB_OBJS += object.o
 LIB_OBJS += pack-check.o
 LIB_OBJS += pack-refs.o
diff --git a/cache.h b/cache.h
index 96840c7..0343e8e 100644
--- a/cache.h
+++ b/cache.h
@@ -372,6 +372,8 @@ static inline enum object_type object_type(unsigned int mode)
 #define GITATTRIBUTES_FILE ".gitattributes"
 #define INFOATTRIBUTES_FILE "info/attributes"
 #define ATTRIBUTE_MACRO_PREFIX "[attr]"
+#define GIT_NOTES_REF_ENVIRONMENT "GIT_NOTES_REF"
+#define GIT_NOTES_DEFAULT_REF "refs/notes/commits"
 
 extern int is_bare_repository_cfg;
 extern int is_bare_repository(void);
@@ -567,6 +569,8 @@ enum object_creation_mode {
 
 extern enum object_creation_mode object_creation_mode;
 
+extern char *notes_ref_name;
+
 extern int grafts_replace_parents;
 
 #define GIT_REPO_VERSION 0
diff --git a/commit.c b/commit.c
index fedbd5e..5ade8ed 100644
--- a/commit.c
+++ b/commit.c
@@ -5,6 +5,7 @@
 #include "utf8.h"
 #include "diff.h"
 #include "revision.h"
+#include "notes.h"
 
 int save_commit_buffer = 1;
 
diff --git a/config.c b/config.c
index c644061..51f2208 100644
--- a/config.c
+++ b/config.c
@@ -467,6 +467,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.notesref")) {
+		notes_ref_name = xstrdup(value);
+		return 0;
+	}
+
 	if (!strcmp(var, "core.pager"))
 		return git_config_string(&pager_program, var, value);
 
diff --git a/environment.c b/environment.c
index 5de6837..571ab56 100644
--- a/environment.c
+++ b/environment.c
@@ -49,6 +49,7 @@ enum push_default_type push_default = PUSH_DEFAULT_MATCHING;
 #define OBJECT_CREATION_MODE OBJECT_CREATION_USES_HARDLINKS
 #endif
 enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;
+char *notes_ref_name;
 int grafts_replace_parents = 1;
 
 /* Parallel index stat data preload? */
diff --git a/notes.c b/notes.c
new file mode 100644
index 0000000..66379ff
--- /dev/null
+++ b/notes.c
@@ -0,0 +1,70 @@
+#include "cache.h"
+#include "commit.h"
+#include "notes.h"
+#include "refs.h"
+#include "utf8.h"
+#include "strbuf.h"
+
+static int initialized;
+
+void get_commit_notes(const struct commit *commit, struct strbuf *sb,
+		const char *output_encoding)
+{
+	static const char utf8[] = "utf-8";
+	struct strbuf name = STRBUF_INIT;
+	unsigned char sha1[20];
+	char *msg, *msg_p;
+	unsigned long linelen, msglen;
+	enum object_type type;
+
+	if (!initialized) {
+		const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
+		if (env)
+			notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
+		else if (!notes_ref_name)
+			notes_ref_name = GIT_NOTES_DEFAULT_REF;
+		if (notes_ref_name && read_ref(notes_ref_name, sha1))
+			notes_ref_name = NULL;
+		initialized = 1;
+	}
+
+	if (!notes_ref_name)
+		return;
+
+	strbuf_addf(&name, "%s:%s", notes_ref_name,
+			sha1_to_hex(commit->object.sha1));
+	if (get_sha1(name.buf, sha1))
+		return;
+
+	if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||
+			type != OBJ_BLOB) {
+		free(msg);
+		return;
+	}
+
+	if (output_encoding && *output_encoding &&
+			strcmp(utf8, output_encoding)) {
+		char *reencoded = reencode_string(msg, output_encoding, utf8);
+		if (reencoded) {
+			free(msg);
+			msg = reencoded;
+			msglen = strlen(msg);
+		}
+	}
+
+	/* we will end the annotation by a newline anyway */
+	if (msglen && msg[msglen - 1] == '\n')
+		msglen--;
+
+	strbuf_addstr(sb, "\nNotes:\n");
+
+	for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
+		linelen = strchrnul(msg_p, '\n') - msg_p;
+
+		strbuf_addstr(sb, "    ");
+		strbuf_add(sb, msg_p, linelen);
+		strbuf_addch(sb, '\n');
+	}
+
+	free(msg);
+}
diff --git a/notes.h b/notes.h
new file mode 100644
index 0000000..79d21b6
--- /dev/null
+++ b/notes.h
@@ -0,0 +1,7 @@
+#ifndef NOTES_H
+#define NOTES_H
+
+void get_commit_notes(const struct commit *commit, struct strbuf *sb,
+		const char *output_encoding);
+
+#endif
diff --git a/pretty.c b/pretty.c
index f5983f8..e25db81 100644
--- a/pretty.c
+++ b/pretty.c
@@ -6,6 +6,7 @@
 #include "string-list.h"
 #include "mailmap.h"
 #include "log-tree.h"
+#include "notes.h"
 #include "color.h"
 
 static char *user_format;
@@ -975,5 +976,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
 	 */
 	if (fmt == CMIT_FMT_EMAIL && sb->len <= beginning_of_body)
 		strbuf_addch(sb, '\n');
+
+	if (fmt != CMIT_FMT_ONELINE)
+		get_commit_notes(commit, sb, encoding);
+
 	free(reencoded);
 }
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 02/22] Add a script to edit/inspect notes

[Johan Herland]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

The script 'git notes' allows you to edit and show commit notes, by
calling either

	git notes show <commit>

or

	git notes edit <commit>

This patch has been improved by the following contributions:
- Tor Arne Vestbø: fix printing of multi-line notes
- Michael J Gruber: test and handle empty notes gracefully
- Thomas Rast:
  - only clean up message file when editing
  - use GIT_EDITOR and core.editor over VISUAL/EDITOR
  - t3301: fix confusing quoting in test for valid notes ref
  - t3301: use test_must_fail instead of !
  - refuse to edit notes outside refs/notes/
- Junio C Hamano: tests: fix "export var=val"
- Christian Couder: documentation: fix 'linkgit' macro in "git-notes.txt"
- Johan Herland: minor cleanup and bugfixing in git-notes.sh (v2)

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Tor Arne Vestbø <tavestbo@trolltech.com>
Signed-off-by: Michael J Gruber <git@drmicha.warpmail.net>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 .gitignore                  |    1 +
 Documentation/git-notes.txt |   46 +++++++++++++++++
 Makefile                    |    1 +
 command-list.txt            |    1 +
 git-notes.sh                |   73 +++++++++++++++++++++++++++
 t/t3301-notes.sh            |  114 +++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 236 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/git-notes.txt
 create mode 100755 git-notes.sh
 create mode 100755 t/t3301-notes.sh

diff --git a/.gitignore b/.gitignore
index 51a37b1..cbafa64 100644
--- a/.gitignore
+++ b/.gitignore
@@ -86,6 +86,7 @@ git-mktag
 git-mktree
 git-name-rev
 git-mv
+git-notes
 git-pack-redundant
 git-pack-objects
 git-pack-refs
diff --git a/Documentation/git-notes.txt b/Documentation/git-notes.txt
new file mode 100644
index 0000000..7136016
--- /dev/null
+++ b/Documentation/git-notes.txt
@@ -0,0 +1,46 @@
+git-notes(1)
+============
+
+NAME
+----
+git-notes - Add/inspect commit notes
+
+SYNOPSIS
+--------
+[verse]
+'git-notes' (edit | show) [commit]
+
+DESCRIPTION
+-----------
+This command allows you to add notes to commit messages, without
+changing the commit.  To discern these notes from the message stored
+in the commit object, the notes are indented like the message, after
+an unindented line saying "Notes:".
+
+To disable commit notes, you have to set the config variable
+core.notesRef to the empty string.  Alternatively, you can set it
+to a different ref, something like "refs/notes/bugzilla".  This setting
+can be overridden by the environment variable "GIT_NOTES_REF".
+
+
+SUBCOMMANDS
+-----------
+
+edit::
+	Edit the notes for a given commit (defaults to HEAD).
+
+show::
+	Show the notes for a given commit (defaults to HEAD).
+
+
+Author
+------
+Written by Johannes Schindelin <johannes.schindelin@gmx.de>
+
+Documentation
+-------------
+Documentation by Johannes Schindelin
+
+GIT
+---
+Part of the linkgit:git[7] suite
diff --git a/Makefile b/Makefile
index 9e414db..dadd814 100644
--- a/Makefile
+++ b/Makefile
@@ -318,6 +318,7 @@ SCRIPT_SH += git-merge-one-file.sh
 SCRIPT_SH += git-merge-resolve.sh
 SCRIPT_SH += git-mergetool.sh
 SCRIPT_SH += git-mergetool--lib.sh
+SCRIPT_SH += git-notes.sh
 SCRIPT_SH += git-parse-remote.sh
 SCRIPT_SH += git-pull.sh
 SCRIPT_SH += git-quiltimport.sh
diff --git a/command-list.txt b/command-list.txt
index fb03a2e..4296941 100644
--- a/command-list.txt
+++ b/command-list.txt
@@ -74,6 +74,7 @@ git-mktag                               plumbingmanipulators
 git-mktree                              plumbingmanipulators
 git-mv                                  mainporcelain common
 git-name-rev                            plumbinginterrogators
+git-notes                               mainporcelain
 git-pack-objects                        plumbingmanipulators
 git-pack-redundant                      plumbinginterrogators
 git-pack-refs                           ancillarymanipulators
diff --git a/git-notes.sh b/git-notes.sh
new file mode 100755
index 0000000..f06c254
--- /dev/null
+++ b/git-notes.sh
@@ -0,0 +1,73 @@
+#!/bin/sh
+
+USAGE="(edit | show) [commit]"
+. git-sh-setup
+
+test -n "$3" && usage
+
+test -z "$1" && usage
+ACTION="$1"; shift
+
+test -z "$GIT_NOTES_REF" && GIT_NOTES_REF="$(git config core.notesref)"
+test -z "$GIT_NOTES_REF" && GIT_NOTES_REF="refs/notes/commits"
+
+COMMIT=$(git rev-parse --verify --default HEAD "$@") ||
+die "Invalid commit: $@"
+
+case "$ACTION" in
+edit)
+	if [ "${GIT_NOTES_REF#refs/notes/}" = "$GIT_NOTES_REF" ]; then
+		die "Refusing to edit notes in $GIT_NOTES_REF (outside of refs/notes/)"
+	fi
+
+	MSG_FILE="$GIT_DIR/new-notes-$COMMIT"
+	GIT_INDEX_FILE="$MSG_FILE.idx"
+	export GIT_INDEX_FILE
+
+	trap '
+		test -f "$MSG_FILE" && rm "$MSG_FILE"
+		test -f "$GIT_INDEX_FILE" && rm "$GIT_INDEX_FILE"
+	' 0
+
+	GIT_NOTES_REF= git log -1 $COMMIT | sed "s/^/#/" > "$MSG_FILE"
+
+	CURRENT_HEAD=$(git show-ref "$GIT_NOTES_REF" | cut -f 1 -d ' ')
+	if [ -z "$CURRENT_HEAD" ]; then
+		PARENT=
+	else
+		PARENT="-p $CURRENT_HEAD"
+		git read-tree "$GIT_NOTES_REF" || die "Could not read index"
+		git cat-file blob :$COMMIT >> "$MSG_FILE" 2> /dev/null
+	fi
+
+	core_editor="$(git config core.editor)"
+	${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} "$MSG_FILE"
+
+	grep -v ^# < "$MSG_FILE" | git stripspace > "$MSG_FILE".processed
+	mv "$MSG_FILE".processed "$MSG_FILE"
+	if [ -s "$MSG_FILE" ]; then
+		BLOB=$(git hash-object -w "$MSG_FILE") ||
+			die "Could not write into object database"
+		git update-index --add --cacheinfo 0644 $BLOB $COMMIT ||
+			die "Could not write index"
+	else
+		test -z "$CURRENT_HEAD" &&
+			die "Will not initialise with empty tree"
+		git update-index --force-remove $COMMIT ||
+			die "Could not update index"
+	fi
+
+	TREE=$(git write-tree) || die "Could not write tree"
+	NEW_HEAD=$(echo Annotate $COMMIT | git commit-tree $TREE $PARENT) ||
+		die "Could not annotate"
+	git update-ref -m "Annotate $COMMIT" \
+		"$GIT_NOTES_REF" $NEW_HEAD $CURRENT_HEAD
+;;
+show)
+	git rev-parse -q --verify "$GIT_NOTES_REF":$COMMIT > /dev/null ||
+		die "No note for commit $COMMIT."
+	git show "$GIT_NOTES_REF":$COMMIT
+;;
+*)
+	usage
+esac
diff --git a/t/t3301-notes.sh b/t/t3301-notes.sh
new file mode 100755
index 0000000..73e53be
--- /dev/null
+++ b/t/t3301-notes.sh
@@ -0,0 +1,114 @@
+#!/bin/sh
+#
+# Copyright (c) 2007 Johannes E. Schindelin
+#
+
+test_description='Test commit notes'
+
+. ./test-lib.sh
+
+cat > fake_editor.sh << \EOF
+echo "$MSG" > "$1"
+echo "$MSG" >& 2
+EOF
+chmod a+x fake_editor.sh
+VISUAL=./fake_editor.sh
+export VISUAL
+
+test_expect_success 'cannot annotate non-existing HEAD' '
+	(MSG=3 && export MSG && test_must_fail git notes edit)
+'
+
+test_expect_success setup '
+	: > a1 &&
+	git add a1 &&
+	test_tick &&
+	git commit -m 1st &&
+	: > a2 &&
+	git add a2 &&
+	test_tick &&
+	git commit -m 2nd
+'
+
+test_expect_success 'need valid notes ref' '
+	(MSG=1 GIT_NOTES_REF=/ && export MSG GIT_NOTES_REF &&
+	 test_must_fail git notes edit) &&
+	(MSG=2 GIT_NOTES_REF=/ && export MSG GIT_NOTES_REF &&
+	 test_must_fail git notes show)
+'
+
+test_expect_success 'refusing to edit in refs/heads/' '
+	(MSG=1 GIT_NOTES_REF=refs/heads/bogus &&
+	 export MSG GIT_NOTES_REF &&
+	 test_must_fail git notes edit)
+'
+
+test_expect_success 'refusing to edit in refs/remotes/' '
+	(MSG=1 GIT_NOTES_REF=refs/remotes/bogus &&
+	 export MSG GIT_NOTES_REF &&
+	 test_must_fail git notes edit)
+'
+
+# 1 indicates caught gracefully by die, 128 means git-show barked
+test_expect_success 'handle empty notes gracefully' '
+	git notes show ; test 1 = $?
+'
+
+test_expect_success 'create notes' '
+	git config core.notesRef refs/notes/commits &&
+	MSG=b1 git notes edit &&
+	test ! -f .git/new-notes &&
+	test 1 = $(git ls-tree refs/notes/commits | wc -l) &&
+	test b1 = $(git notes show) &&
+	git show HEAD^ &&
+	test_must_fail git notes show HEAD^
+'
+
+cat > expect << EOF
+commit 268048bfb8a1fb38e703baceb8ab235421bf80c5
+Author: A U Thor <author@example.com>
+Date:   Thu Apr 7 15:14:13 2005 -0700
+
+    2nd
+
+Notes:
+    b1
+EOF
+
+test_expect_success 'show notes' '
+	! (git cat-file commit HEAD | grep b1) &&
+	git log -1 > output &&
+	test_cmp expect output
+'
+test_expect_success 'create multi-line notes (setup)' '
+	: > a3 &&
+	git add a3 &&
+	test_tick &&
+	git commit -m 3rd &&
+	MSG="b3
+c3c3c3c3
+d3d3d3" git notes edit
+'
+
+cat > expect-multiline << EOF
+commit 1584215f1d29c65e99c6c6848626553fdd07fd75
+Author: A U Thor <author@example.com>
+Date:   Thu Apr 7 15:15:13 2005 -0700
+
+    3rd
+
+Notes:
+    b3
+    c3c3c3c3
+    d3d3d3
+EOF
+
+printf "\n" >> expect-multiline
+cat expect >> expect-multiline
+
+test_expect_success 'show multi-line notes' '
+	git log -2 > output &&
+	test_cmp expect-multiline output
+'
+
+test_done
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 03/22] Speed up git notes lookup

[Johan Herland]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

To avoid looking up each and every commit in the notes ref's tree
object, which is very expensive, speed things up by slurping the tree
object's contents into a hash_map.

The idea for the hashmap singleton is from David Reiss, initial
benchmarking by Jeff King.

Note: the implementation allows for arbitrary entries in the notes
tree object, ignoring those that do not reference a valid object.  This
allows you to annotate arbitrary branches, or objects.

This patch has been improved by the following contributions:
- Junio C Hamano: fixed an obvious error in initialize_hash_map()

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 notes.c |  112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 102 insertions(+), 10 deletions(-)

diff --git a/notes.c b/notes.c
index 66379ff..2b66723 100644
--- a/notes.c
+++ b/notes.c
@@ -4,15 +4,112 @@
 #include "refs.h"
 #include "utf8.h"
 #include "strbuf.h"
+#include "tree-walk.h"
+
+struct entry {
+	unsigned char commit_sha1[20];
+	unsigned char notes_sha1[20];
+};
+
+struct hash_map {
+	struct entry *entries;
+	off_t count, size;
+};
 
 static int initialized;
+static struct hash_map hash_map;
+
+static int hash_index(struct hash_map *map, const unsigned char *sha1)
+{
+	int i = ((*(unsigned int *)sha1) % map->size);
+
+	for (;;) {
+		unsigned char *current = map->entries[i].commit_sha1;
+
+		if (!hashcmp(sha1, current))
+			return i;
+
+		if (is_null_sha1(current))
+			return -1 - i;
+
+		if (++i == map->size)
+			i = 0;
+	}
+}
+
+static void add_entry(const unsigned char *commit_sha1,
+		const unsigned char *notes_sha1)
+{
+	int index;
+
+	if (hash_map.count + 1 > hash_map.size >> 1) {
+		int i, old_size = hash_map.size;
+		struct entry *old = hash_map.entries;
+
+		hash_map.size = old_size ? old_size << 1 : 64;
+		hash_map.entries = (struct entry *)
+			xcalloc(sizeof(struct entry), hash_map.size);
+
+		for (i = 0; i < old_size; i++)
+			if (!is_null_sha1(old[i].commit_sha1)) {
+				index = -1 - hash_index(&hash_map,
+						old[i].commit_sha1);
+				memcpy(hash_map.entries + index, old + i,
+					sizeof(struct entry));
+			}
+		free(old);
+	}
+
+	index = hash_index(&hash_map, commit_sha1);
+	if (index < 0) {
+		index = -1 - index;
+		hash_map.count++;
+	}
+
+	hashcpy(hash_map.entries[index].commit_sha1, commit_sha1);
+	hashcpy(hash_map.entries[index].notes_sha1, notes_sha1);
+}
+
+static void initialize_hash_map(const char *notes_ref_name)
+{
+	unsigned char sha1[20], commit_sha1[20];
+	unsigned mode;
+	struct tree_desc desc;
+	struct name_entry entry;
+	void *buf;
+
+	if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
+	    get_tree_entry(commit_sha1, "", sha1, &mode))
+		return;
+
+	buf = fill_tree_descriptor(&desc, sha1);
+	if (!buf)
+		die("Could not read %s for notes-index", sha1_to_hex(sha1));
+
+	while (tree_entry(&desc, &entry))
+		if (!get_sha1(entry.path, commit_sha1))
+			add_entry(commit_sha1, entry.sha1);
+	free(buf);
+}
+
+static unsigned char *lookup_notes(const unsigned char *commit_sha1)
+{
+	int index;
+
+	if (!hash_map.size)
+		return NULL;
+
+	index = hash_index(&hash_map, commit_sha1);
+	if (index < 0)
+		return NULL;
+	return hash_map.entries[index].notes_sha1;
+}
 
 void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 		const char *output_encoding)
 {
 	static const char utf8[] = "utf-8";
-	struct strbuf name = STRBUF_INIT;
-	unsigned char sha1[20];
+	unsigned char *sha1;
 	char *msg, *msg_p;
 	unsigned long linelen, msglen;
 	enum object_type type;
@@ -23,17 +120,12 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 			notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
 		else if (!notes_ref_name)
 			notes_ref_name = GIT_NOTES_DEFAULT_REF;
-		if (notes_ref_name && read_ref(notes_ref_name, sha1))
-			notes_ref_name = NULL;
+		initialize_hash_map(notes_ref_name);
 		initialized = 1;
 	}
 
-	if (!notes_ref_name)
-		return;
-
-	strbuf_addf(&name, "%s:%s", notes_ref_name,
-			sha1_to_hex(commit->object.sha1));
-	if (get_sha1(name.buf, sha1))
+	sha1 = lookup_notes(commit->object.sha1);
+	if (!sha1)
 		return;
 
 	if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 04/22] Add an expensive test for git-notes

[Johan Herland]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

git-notes have the potential of being pretty expensive, so test with
a lot of commits.  A lot.  So to make things cheaper, you have to
opt-in explicitely, by setting the environment variable
GIT_NOTES_TIMING_TESTS.

This patch has been improved by the following contributions:
- Junio C Hamano: tests: fix "export var=val"

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 t/t3302-notes-index-expensive.sh |   98 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 98 insertions(+), 0 deletions(-)
 create mode 100755 t/t3302-notes-index-expensive.sh

diff --git a/t/t3302-notes-index-expensive.sh b/t/t3302-notes-index-expensive.sh
new file mode 100755
index 0000000..0ef3e95
--- /dev/null
+++ b/t/t3302-notes-index-expensive.sh
@@ -0,0 +1,98 @@
+#!/bin/sh
+#
+# Copyright (c) 2007 Johannes E. Schindelin
+#
+
+test_description='Test commit notes index (expensive!)'
+
+. ./test-lib.sh
+
+test -z "$GIT_NOTES_TIMING_TESTS" && {
+	say Skipping timing tests
+	test_done
+	exit
+}
+
+create_repo () {
+	number_of_commits=$1
+	nr=0
+	parent=
+	test -d .git || {
+	git init &&
+	tree=$(git write-tree) &&
+	while [ $nr -lt $number_of_commits ]; do
+		test_tick &&
+		commit=$(echo $nr | git commit-tree $tree $parent) ||
+			return
+		parent="-p $commit"
+		nr=$(($nr+1))
+	done &&
+	git update-ref refs/heads/master $commit &&
+	{
+		GIT_INDEX_FILE=.git/temp; export GIT_INDEX_FILE;
+		git rev-list HEAD | cat -n | sed "s/^[ 	][ 	]*/ /g" |
+		while read nr sha1; do
+			blob=$(echo note $nr | git hash-object -w --stdin) &&
+			echo $sha1 | sed "s/^/0644 $blob 0	/"
+		done | git update-index --index-info &&
+		tree=$(git write-tree) &&
+		test_tick &&
+		commit=$(echo notes | git commit-tree $tree) &&
+		git update-ref refs/notes/commits $commit
+	} &&
+	git config core.notesRef refs/notes/commits
+	}
+}
+
+test_notes () {
+	count=$1 &&
+	git config core.notesRef refs/notes/commits &&
+	git log | grep "^    " > output &&
+	i=1 &&
+	while [ $i -le $count ]; do
+		echo "    $(($count-$i))" &&
+		echo "    note $i" &&
+		i=$(($i+1));
+	done > expect &&
+	git diff expect output
+}
+
+cat > time_notes << \EOF
+	mode=$1
+	i=1
+	while [ $i -lt $2 ]; do
+		case $1 in
+		no-notes)
+			GIT_NOTES_REF=non-existing; export GIT_NOTES_REF
+		;;
+		notes)
+			unset GIT_NOTES_REF
+		;;
+		esac
+		git log >/dev/null
+		i=$(($i+1))
+	done
+EOF
+
+time_notes () {
+	for mode in no-notes notes
+	do
+		echo $mode
+		/usr/bin/time sh ../time_notes $mode $1
+	done
+}
+
+for count in 10 100 1000 10000; do
+
+	mkdir $count
+	(cd $count;
+
+	test_expect_success "setup $count" "create_repo $count"
+
+	test_expect_success 'notes work' "test_notes $count"
+
+	test_expect_success 'notes timing' "time_notes 100"
+	)
+done
+
+test_done
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 05/22] Teach "-m <msg>" and "-F <file>" to "git notes edit"

[Johan Herland]

The "-m" and "-F" options are already the established method
(in both git-commit and git-tag) to specify a commit/tag message
without invoking the editor. This patch teaches "git notes edit"
to respect the same options for specifying a notes message without
invoking the editor.

Multiple "-m" and/or "-F" options are concatenated as separate
paragraphs.

The patch also updates the "git notes" documentation and adds
selftests for the new functionality. Unfortunately, the added
selftests include a couple of lines with trailing whitespace
(without these the test will fail). This may cause git to warn
about "whitespace errors".

This patch has been improved by the following contributions:
- Thomas Rast: fix trailing whitespace in t3301

Signed-off-by: Johan Herland <johan@herland.net>
---
 Documentation/git-notes.txt |   16 ++++++++++-
 git-notes.sh                |   64 +++++++++++++++++++++++++++++++++++++-----
 t/t3301-notes.sh            |   36 ++++++++++++++++++++++++
 3 files changed, 107 insertions(+), 9 deletions(-)

diff --git a/Documentation/git-notes.txt b/Documentation/git-notes.txt
index 7136016..94cceb1 100644
--- a/Documentation/git-notes.txt
+++ b/Documentation/git-notes.txt
@@ -8,7 +8,7 @@ git-notes - Add/inspect commit notes
 SYNOPSIS
 --------
 [verse]
-'git-notes' (edit | show) [commit]
+'git-notes' (edit [-F <file> | -m <msg>] | show) [commit]
 
 DESCRIPTION
 -----------
@@ -33,6 +33,20 @@ show::
 	Show the notes for a given commit (defaults to HEAD).
 
 
+OPTIONS
+-------
+-m <msg>::
+	Use the given note message (instead of prompting).
+	If multiple `-m` (or `-F`) options are given, their
+	values are concatenated as separate paragraphs.
+
+-F <file>::
+	Take the note message from the given file.  Use '-' to
+	read the note message from the standard input.
+	If multiple `-F` (or `-m`) options are given, their
+	values are concatenated as separate paragraphs.
+
+
 Author
 ------
 Written by Johannes Schindelin <johannes.schindelin@gmx.de>
diff --git a/git-notes.sh b/git-notes.sh
index f06c254..e642e47 100755
--- a/git-notes.sh
+++ b/git-notes.sh
@@ -1,16 +1,59 @@
 #!/bin/sh
 
-USAGE="(edit | show) [commit]"
+USAGE="(edit [-F <file> | -m <msg>] | show) [commit]"
 . git-sh-setup
 
-test -n "$3" && usage
-
 test -z "$1" && usage
 ACTION="$1"; shift
 
 test -z "$GIT_NOTES_REF" && GIT_NOTES_REF="$(git config core.notesref)"
 test -z "$GIT_NOTES_REF" && GIT_NOTES_REF="refs/notes/commits"
 
+MESSAGE=
+while test $# != 0
+do
+	case "$1" in
+	-m)
+		test "$ACTION" = "edit" || usage
+		shift
+		if test "$#" = "0"; then
+			die "error: option -m needs an argument"
+		else
+			if [ -z "$MESSAGE" ]; then
+				MESSAGE="$1"
+			else
+				MESSAGE="$MESSAGE
+
+$1"
+			fi
+			shift
+		fi
+		;;
+	-F)
+		test "$ACTION" = "edit" || usage
+		shift
+		if test "$#" = "0"; then
+			die "error: option -F needs an argument"
+		else
+			if [ -z "$MESSAGE" ]; then
+				MESSAGE="$(cat "$1")"
+			else
+				MESSAGE="$MESSAGE
+
+$(cat "$1")"
+			fi
+			shift
+		fi
+		;;
+	-*)
+		usage
+		;;
+	*)
+		break
+		;;
+	esac
+done
+
 COMMIT=$(git rev-parse --verify --default HEAD "$@") ||
 die "Invalid commit: $@"
 
@@ -29,19 +72,24 @@ edit)
 		test -f "$GIT_INDEX_FILE" && rm "$GIT_INDEX_FILE"
 	' 0
 
-	GIT_NOTES_REF= git log -1 $COMMIT | sed "s/^/#/" > "$MSG_FILE"
-
 	CURRENT_HEAD=$(git show-ref "$GIT_NOTES_REF" | cut -f 1 -d ' ')
 	if [ -z "$CURRENT_HEAD" ]; then
 		PARENT=
 	else
 		PARENT="-p $CURRENT_HEAD"
 		git read-tree "$GIT_NOTES_REF" || die "Could not read index"
-		git cat-file blob :$COMMIT >> "$MSG_FILE" 2> /dev/null
 	fi
 
-	core_editor="$(git config core.editor)"
-	${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} "$MSG_FILE"
+	if [ -z "$MESSAGE" ]; then
+		GIT_NOTES_REF= git log -1 $COMMIT | sed "s/^/#/" > "$MSG_FILE"
+		if [ ! -z "$CURRENT_HEAD" ]; then
+			git cat-file blob :$COMMIT >> "$MSG_FILE" 2> /dev/null
+		fi
+		core_editor="$(git config core.editor)"
+		${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} "$MSG_FILE"
+	else
+		echo "$MESSAGE" > "$MSG_FILE"
+	fi
 
 	grep -v ^# < "$MSG_FILE" | git stripspace > "$MSG_FILE".processed
 	mv "$MSG_FILE".processed "$MSG_FILE"
diff --git a/t/t3301-notes.sh b/t/t3301-notes.sh
index 73e53be..1e34f48 100755
--- a/t/t3301-notes.sh
+++ b/t/t3301-notes.sh
@@ -110,5 +110,41 @@ test_expect_success 'show multi-line notes' '
 	git log -2 > output &&
 	test_cmp expect-multiline output
 '
+test_expect_success 'create -m and -F notes (setup)' '
+	: > a4 &&
+	git add a4 &&
+	test_tick &&
+	git commit -m 4th &&
+	echo "xyzzy" > note5 &&
+	git notes edit -m spam -F note5 -m "foo
+bar
+baz"
+'
+
+whitespace="    "
+cat > expect-m-and-F << EOF
+commit 15023535574ded8b1a89052b32673f84cf9582b8
+Author: A U Thor <author@example.com>
+Date:   Thu Apr 7 15:16:13 2005 -0700
+
+    4th
+
+Notes:
+    spam
+$whitespace
+    xyzzy
+$whitespace
+    foo
+    bar
+    baz
+EOF
+
+printf "\n" >> expect-m-and-F
+cat expect-multiline >> expect-m-and-F
+
+test_expect_success 'show -m and -F notes' '
+	git log -3 > output &&
+	test_cmp expect-m-and-F output
+'
 
 test_done
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 06/22] fast-import: Add support for importing commit notes

[Johan Herland]

Introduce a 'notemodify' subcommand of the 'commit' command. This subcommand
is similar to 'filemodify', except that no mode is supplied (all notes have
mode 0644), and the path is set to the hex SHA1 of the given "comittish".

This enables fast import of note objects along with their associated commits,
since the notes can now be named using the mark references of their
corresponding commits.

The patch also includes a test case of the added functionality.

Signed-off-by: Johan Herland <johan@herland.net>
Acked-by: Shawn O. Pearce <spearce@spearce.org>
---
 Documentation/git-fast-import.txt |   45 +++++++++--
 fast-import.c                     |   88 +++++++++++++++++++-
 t/t9300-fast-import.sh            |  166 +++++++++++++++++++++++++++++++++++++
 3 files changed, 289 insertions(+), 10 deletions(-)

diff --git a/Documentation/git-fast-import.txt b/Documentation/git-fast-import.txt
index f1c94b4..bb198c2 100644
--- a/Documentation/git-fast-import.txt
+++ b/Documentation/git-fast-import.txt
@@ -325,7 +325,7 @@ change to the project.
 	data
 	('from' SP <committish> LF)?
 	('merge' SP <committish> LF)?
-	(filemodify | filedelete | filecopy | filerename | filedeleteall)*
+	(filemodify | filedelete | filecopy | filerename | filedeleteall | notemodify)*
 	LF?
 ....
 
@@ -348,14 +348,13 @@ commit message use a 0 length data.  Commit messages are free-form
 and are not interpreted by Git.  Currently they must be encoded in
 UTF-8, as fast-import does not permit other encodings to be specified.
 
-Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`
-and `filedeleteall` commands
+Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`,
+`filedeleteall` and `notemodify` commands
 may be included to update the contents of the branch prior to
 creating the commit.  These commands may be supplied in any order.
 However it is recommended that a `filedeleteall` command precede
-all `filemodify`, `filecopy` and `filerename` commands in the same
-commit, as `filedeleteall`
-wipes the branch clean (see below).
+all `filemodify`, `filecopy`, `filerename` and `notemodify` commands in
+the same commit, as `filedeleteall` wipes the branch clean (see below).
 
 The `LF` after the command is optional (it used to be required).
 
@@ -604,6 +603,40 @@ more memory per active branch (less than 1 MiB for even most large
 projects); so frontends that can easily obtain only the affected
 paths for a commit are encouraged to do so.
 
+`notemodify`
+^^^^^^^^^^^^
+Included in a `commit` command to add a new note (annotating a given
+commit) or change the content of an existing note.  This command has
+two different means of specifying the content of the note.
+
+External data format::
+	The data content for the note was already supplied by a prior
+	`blob` command.  The frontend just needs to connect it to the
+	commit that is to be annotated.
++
+....
+	'N' SP <dataref> SP <committish> LF
+....
++
+Here `<dataref>` can be either a mark reference (`:<idnum>`)
+set by a prior `blob` command, or a full 40-byte SHA-1 of an
+existing Git blob object.
+
+Inline data format::
+	The data content for the note has not been supplied yet.
+	The frontend wants to supply it as part of this modify
+	command.
++
+....
+	'N' SP 'inline' SP <committish> LF
+	data
+....
++
+See below for a detailed description of the `data` command.
+
+In both formats `<committish>` is any of the commit specification
+expressions also accepted by `from` (see above).
+
 `mark`
 ~~~~~~
 Arranges for fast-import to save a reference to the current object, allowing
diff --git a/fast-import.c b/fast-import.c
index 992220e..fcdcfaa 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -22,8 +22,8 @@ Format of STDIN stream:
     ('author' sp name sp '<' email '>' sp when lf)?
     'committer' sp name sp '<' email '>' sp when lf
     commit_msg
-    ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?
-    ('merge' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)*
+    ('from' sp committish lf)?
+    ('merge' sp committish lf)*
     file_change*
     lf?;
   commit_msg ::= data;
@@ -41,15 +41,18 @@ Format of STDIN stream:
   file_obm ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf;
   file_inm ::= 'M' sp mode sp 'inline' sp path_str lf
     data;
+  note_obm ::= 'N' sp (hexsha1 | idnum) sp committish lf;
+  note_inm ::= 'N' sp 'inline' sp committish lf
+    data;
 
   new_tag ::= 'tag' sp tag_str lf
-    'from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf
+    'from' sp committish lf
     ('tagger' sp name sp '<' email '>' sp when lf)?
     tag_msg;
   tag_msg ::= data;
 
   reset_branch ::= 'reset' sp ref_str lf
-    ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?
+    ('from' sp committish lf)?
     lf?;
 
   checkpoint ::= 'checkpoint' lf
@@ -88,6 +91,7 @@ Format of STDIN stream:
      # stream formatting is: \, " and LF.  Otherwise these values
      # are UTF8.
      #
+  committish  ::= (ref_str | hexsha1 | sha1exp_str | idnum);
   ref_str     ::= ref;
   sha1exp_str ::= sha1exp;
   tag_str     ::= tag;
@@ -2056,6 +2060,80 @@ static void file_change_cr(struct branch *b, int rename)
 		leaf.tree);
 }
 
+static void note_change_n(struct branch *b)
+{
+	const char *p = command_buf.buf + 2;
+	static struct strbuf uq = STRBUF_INIT;
+	struct object_entry *oe = oe;
+	struct branch *s;
+	unsigned char sha1[20], commit_sha1[20];
+	uint16_t inline_data = 0;
+
+	/* <dataref> or 'inline' */
+	if (*p == ':') {
+		char *x;
+		oe = find_mark(strtoumax(p + 1, &x, 10));
+		hashcpy(sha1, oe->sha1);
+		p = x;
+	} else if (!prefixcmp(p, "inline")) {
+		inline_data = 1;
+		p += 6;
+	} else {
+		if (get_sha1_hex(p, sha1))
+			die("Invalid SHA1: %s", command_buf.buf);
+		oe = find_object(sha1);
+		p += 40;
+	}
+	if (*p++ != ' ')
+		die("Missing space after SHA1: %s", command_buf.buf);
+
+	/* <committish> */
+	s = lookup_branch(p);
+	if (s) {
+		hashcpy(commit_sha1, s->sha1);
+	} else if (*p == ':') {
+		uintmax_t commit_mark = strtoumax(p + 1, NULL, 10);
+		struct object_entry *commit_oe = find_mark(commit_mark);
+		if (commit_oe->type != OBJ_COMMIT)
+			die("Mark :%" PRIuMAX " not a commit", commit_mark);
+		hashcpy(commit_sha1, commit_oe->sha1);
+	} else if (!get_sha1(p, commit_sha1)) {
+		unsigned long size;
+		char *buf = read_object_with_reference(commit_sha1,
+			commit_type, &size, commit_sha1);
+		if (!buf || size < 46)
+			die("Not a valid commit: %s", p);
+		free(buf);
+	} else
+		die("Invalid ref name or SHA1 expression: %s", p);
+
+	if (inline_data) {
+		static struct strbuf buf = STRBUF_INIT;
+
+		if (p != uq.buf) {
+			strbuf_addstr(&uq, p);
+			p = uq.buf;
+		}
+		read_next_command();
+		parse_data(&buf);
+		store_object(OBJ_BLOB, &buf, &last_blob, sha1, 0);
+	} else if (oe) {
+		if (oe->type != OBJ_BLOB)
+			die("Not a blob (actually a %s): %s",
+				typename(oe->type), command_buf.buf);
+	} else {
+		enum object_type type = sha1_object_info(sha1, NULL);
+		if (type < 0)
+			die("Blob not found: %s", command_buf.buf);
+		if (type != OBJ_BLOB)
+			die("Not a blob (actually a %s): %s",
+			    typename(type), command_buf.buf);
+	}
+
+	tree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,
+		S_IFREG | 0644, NULL);
+}
+
 static void file_change_deleteall(struct branch *b)
 {
 	release_tree_content_recursive(b->branch_tree.tree);
@@ -2225,6 +2303,8 @@ static void parse_new_commit(void)
 			file_change_cr(b, 1);
 		else if (!prefixcmp(command_buf.buf, "C "))
 			file_change_cr(b, 0);
+		else if (!prefixcmp(command_buf.buf, "N "))
+			note_change_n(b);
 		else if (!strcmp("deleteall", command_buf.buf))
 			file_change_deleteall(b);
 		else {
diff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh
index d33fc55..2f5c323 100755
--- a/t/t9300-fast-import.sh
+++ b/t/t9300-fast-import.sh
@@ -1089,6 +1089,172 @@ test_expect_success 'P: fail on blob mark in gitlink' '
     test_must_fail git fast-import <input'
 
 ###
+### series Q (notes)
+###
+
+note1_data="Note for the first commit"
+note2_data="Note for the second commit"
+note3_data="Note for the third commit"
+
+test_tick
+cat >input <<INPUT_END
+blob
+mark :2
+data <<EOF
+$file2_data
+EOF
+
+commit refs/heads/notes-test
+mark :3
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+first (:3)
+COMMIT
+
+M 644 :2 file2
+
+blob
+mark :4
+data $file4_len
+$file4_data
+commit refs/heads/notes-test
+mark :5
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+second (:5)
+COMMIT
+
+M 644 :4 file4
+
+commit refs/heads/notes-test
+mark :6
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+third (:6)
+COMMIT
+
+M 644 inline file5
+data <<EOF
+$file5_data
+EOF
+
+M 755 inline file6
+data <<EOF
+$file6_data
+EOF
+
+blob
+mark :7
+data <<EOF
+$note1_data
+EOF
+
+blob
+mark :8
+data <<EOF
+$note2_data
+EOF
+
+commit refs/notes/foobar
+mark :9
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:9)
+COMMIT
+
+N :7 :3
+N :8 :5
+N inline :6
+data <<EOF
+$note3_data
+EOF
+
+INPUT_END
+test_expect_success \
+	'Q: commit notes' \
+	'git fast-import <input &&
+	 git whatchanged notes-test'
+test_expect_success \
+	'Q: verify pack' \
+	'for p in .git/objects/pack/*.pack;do git verify-pack $p||exit;done'
+
+commit1=$(git rev-parse notes-test~2)
+commit2=$(git rev-parse notes-test^)
+commit3=$(git rev-parse notes-test)
+
+cat >expect <<EOF
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+first (:3)
+EOF
+test_expect_success \
+	'Q: verify first commit' \
+	'git cat-file commit notes-test~2 | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect <<EOF
+parent $commit1
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+second (:5)
+EOF
+test_expect_success \
+	'Q: verify second commit' \
+	'git cat-file commit notes-test^ | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect <<EOF
+parent $commit2
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+third (:6)
+EOF
+test_expect_success \
+	'Q: verify third commit' \
+	'git cat-file commit notes-test | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect <<EOF
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:9)
+EOF
+test_expect_success \
+	'Q: verify notes commit' \
+	'git cat-file commit refs/notes/foobar | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit1
+100644 blob $commit2
+100644 blob $commit3
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+	'Q: verify notes tree' \
+	'git cat-file -p refs/notes/foobar^{tree} | sed "s/ [0-9a-f]*	/ /" >actual &&
+	 test_cmp expect actual'
+
+echo "$note1_data" >expect
+test_expect_success \
+	'Q: verify note for first commit' \
+	'git cat-file blob refs/notes/foobar:$commit1 >actual && test_cmp expect actual'
+
+echo "$note2_data" >expect
+test_expect_success \
+	'Q: verify note for second commit' \
+	'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'
+
+echo "$note3_data" >expect
+test_expect_success \
+	'Q: verify note for third commit' \
+	'git cat-file blob refs/notes/foobar:$commit3 >actual && test_cmp expect actual'
+
+###
 ### series R (feature and option)
 ###
 
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 07/22] t3302-notes-index-expensive: Speed up create_repo()

[Johan Herland]

Creating repos with 10/100/1000/10000 commits and notes takes a lot of time.
However, using git-fast-import to do the job is a lot more efficient than
using plumbing commands to do the same.

This patch decreases the overall run-time of this test on my machine from
~3 to ~1 minutes.

Signed-off-by: Johan Herland <johan@herland.net>
Acked-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 t/t3302-notes-index-expensive.sh |   74 ++++++++++++++++++++++++--------------
 1 files changed, 47 insertions(+), 27 deletions(-)

diff --git a/t/t3302-notes-index-expensive.sh b/t/t3302-notes-index-expensive.sh
index 0ef3e95..ee84fc4 100755
--- a/t/t3302-notes-index-expensive.sh
+++ b/t/t3302-notes-index-expensive.sh
@@ -16,30 +16,50 @@ test -z "$GIT_NOTES_TIMING_TESTS" && {
 create_repo () {
 	number_of_commits=$1
 	nr=0
-	parent=
 	test -d .git || {
 	git init &&
-	tree=$(git write-tree) &&
-	while [ $nr -lt $number_of_commits ]; do
-		test_tick &&
-		commit=$(echo $nr | git commit-tree $tree $parent) ||
-			return
-		parent="-p $commit"
-		nr=$(($nr+1))
-	done &&
-	git update-ref refs/heads/master $commit &&
-	{
-		GIT_INDEX_FILE=.git/temp; export GIT_INDEX_FILE;
-		git rev-list HEAD | cat -n | sed "s/^[ 	][ 	]*/ /g" |
-		while read nr sha1; do
-			blob=$(echo note $nr | git hash-object -w --stdin) &&
-			echo $sha1 | sed "s/^/0644 $blob 0	/"
-		done | git update-index --index-info &&
-		tree=$(git write-tree) &&
+	(
+		while [ $nr -lt $number_of_commits ]; do
+			nr=$(($nr+1))
+			mark=$(($nr+$nr))
+			notemark=$(($mark+1))
+			test_tick &&
+			cat <<INPUT_END &&
+commit refs/heads/master
+mark :$mark
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+commit #$nr
+COMMIT
+
+M 644 inline file
+data <<EOF
+file in commit #$nr
+EOF
+
+blob
+mark :$notemark
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+			echo "N :$notemark :$mark" >> note_commit
+		done &&
 		test_tick &&
-		commit=$(echo notes | git commit-tree $tree) &&
-		git update-ref refs/notes/commits $commit
-	} &&
+		cat <<INPUT_END &&
+commit refs/notes/commits
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes
+COMMIT
+
+INPUT_END
+
+		cat note_commit
+	) |
+	git fast-import --quiet &&
 	git config core.notesRef refs/notes/commits
 	}
 }
@@ -48,13 +68,13 @@ test_notes () {
 	count=$1 &&
 	git config core.notesRef refs/notes/commits &&
 	git log | grep "^    " > output &&
-	i=1 &&
-	while [ $i -le $count ]; do
-		echo "    $(($count-$i))" &&
-		echo "    note $i" &&
-		i=$(($i+1));
+	i=$count &&
+	while [ $i -gt 0 ]; do
+		echo "    commit #$i" &&
+		echo "    note for commit #$i" &&
+		i=$(($i-1));
 	done > expect &&
-	git diff expect output
+	test_cmp expect output
 }
 
 cat > time_notes << \EOF
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 08/22] Add flags to get_commit_notes() to control the format of the note string

[Johan Herland]

This patch adds the following flags to get_commit_notes() for adjusting the
format of the produced note string:
- NOTES_SHOW_HEADER: Print "Notes:" line before the notes contents
- NOTES_INDENT: Indent notes contents by 4 spaces

Suggested-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c  |    8 +++++---
 notes.h  |    5 ++++-
 pretty.c |    3 ++-
 3 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/notes.c b/notes.c
index 2b66723..b7d79e1 100644
--- a/notes.c
+++ b/notes.c
@@ -106,7 +106,7 @@ static unsigned char *lookup_notes(const unsigned char *commit_sha1)
 }
 
 void get_commit_notes(const struct commit *commit, struct strbuf *sb,
-		const char *output_encoding)
+		const char *output_encoding, int flags)
 {
 	static const char utf8[] = "utf-8";
 	unsigned char *sha1;
@@ -148,12 +148,14 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 	if (msglen && msg[msglen - 1] == '\n')
 		msglen--;
 
-	strbuf_addstr(sb, "\nNotes:\n");
+	if (flags & NOTES_SHOW_HEADER)
+		strbuf_addstr(sb, "\nNotes:\n");
 
 	for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
 		linelen = strchrnul(msg_p, '\n') - msg_p;
 
-		strbuf_addstr(sb, "    ");
+		if (flags & NOTES_INDENT)
+			strbuf_addstr(sb, "    ");
 		strbuf_add(sb, msg_p, linelen);
 		strbuf_addch(sb, '\n');
 	}
diff --git a/notes.h b/notes.h
index 79d21b6..7f3eed4 100644
--- a/notes.h
+++ b/notes.h
@@ -1,7 +1,10 @@
 #ifndef NOTES_H
 #define NOTES_H
 
+#define NOTES_SHOW_HEADER 1
+#define NOTES_INDENT 2
+
 void get_commit_notes(const struct commit *commit, struct strbuf *sb,
-		const char *output_encoding);
+		const char *output_encoding, int flags);
 
 #endif
diff --git a/pretty.c b/pretty.c
index e25db81..01eadd0 100644
--- a/pretty.c
+++ b/pretty.c
@@ -978,7 +978,8 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
 		strbuf_addch(sb, '\n');
 
 	if (fmt != CMIT_FMT_ONELINE)
-		get_commit_notes(commit, sb, encoding);
+		get_commit_notes(commit, sb, encoding,
+				 NOTES_SHOW_HEADER | NOTES_INDENT);
 
 	free(reencoded);
 }
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 09/22] Add '%N'-format for pretty-printing commit notes

[Johan Herland]

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>

Signed-off-by: Johan Herland <johan@herland.net>
---
 Documentation/pretty-formats.txt |    1 +
 pretty.c                         |    4 ++++
 2 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt
index 2a845b1..5fb10b3 100644
--- a/Documentation/pretty-formats.txt
+++ b/Documentation/pretty-formats.txt
@@ -123,6 +123,7 @@ The placeholders are:
 - '%s': subject
 - '%f': sanitized subject line, suitable for a filename
 - '%b': body
+- '%N': commit notes
 - '%Cred': switch color to red
 - '%Cgreen': switch color to green
 - '%Cblue': switch color to blue
diff --git a/pretty.c b/pretty.c
index 01eadd0..7f350bb 100644
--- a/pretty.c
+++ b/pretty.c
@@ -702,6 +702,10 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,
 	case 'd':
 		format_decoration(sb, commit);
 		return 1;
+	case 'N':
+		get_commit_notes(commit, sb, git_log_output_encoding ?
+			     git_log_output_encoding : git_commit_encoding, 0);
+		return 1;
 	}
 
 	/* For the rest we have to parse the commit header. */
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 10/22] Teach notes code to free its internal data structures on request

[Johan Herland]

There's no need to be rude to memory-concious callers...

This patch has been improved by the following contributions:
- Junio C Hamano: avoid old-style declaration

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |    7 +++++++
 notes.h |    3 +++
 2 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/notes.c b/notes.c
index b7d79e1..a5d888d 100644
--- a/notes.c
+++ b/notes.c
@@ -105,6 +105,13 @@ static unsigned char *lookup_notes(const unsigned char *commit_sha1)
 	return hash_map.entries[index].notes_sha1;
 }

+void free_notes(void)
+{
+	free(hash_map.entries);
+	memset(&hash_map, 0, sizeof(struct hash_map));
+	initialized = 0;
+}
+
 void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 		const char *output_encoding, int flags)
 {
diff --git a/notes.h b/notes.h
index 7f3eed4..a1421e3 100644
--- a/notes.h
+++ b/notes.h
@@ -1,6 +1,9 @@
 #ifndef NOTES_H
 #define NOTES_H

+/* Free (and de-initialize) the internal notes tree structure */
+void free_notes(void);
+
 #define NOTES_SHOW_HEADER 1
 #define NOTES_INDENT 2

--
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 11/22] Teach the notes lookup code to parse notes trees with various fanout schemes

[Johan Herland]

The semantics used when parsing notes trees (with regards to fanout subtrees)
follow Dscho's proposal fairly closely:
- No concatenation/merging of notes is performed. If there are several notes
  objects referencing a given commit, only one of those objects are used.
- If a notes object for a given commit is present in the "root" notes tree,
  no subtrees are consulted; the object in the root tree is used directly.
- If there are more than one subtree that prefix-matches the given commit,
  only the subtree with the longest matching prefix is consulted. This
  means that if the given commit is e.g. "deadbeef", and the notes tree have
  subtrees "de" and "dead", then the following paths in the notes tree are
  searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched.
- Fanout directories (subtrees) must references a whole number of bytes
  from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are
  acceptable; "d" and "dea" are not.
- Multiple levels of fanout are allowed. All the above rules apply
  recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc.

This patch changes the in-memory datastructure for holding parsed notes:
Instead of holding all note (and subtree) entries in a hash table, a
simple 16-tree structure is used instead. The tree structure consists of
16-arrays as internal nodes, and note/subtree entries as leaf nodes. The
tree is traversed by indexing subsequent nibbles of the search key until
a leaf node is encountered. If a subtree entry is encountered while
searching for a note, the subtree is unpacked into the 16-tree structure,
and the search continues into that subtree.

The new algorithm performs significantly better in the cases where only
a fraction of the notes need to be looked up (this is assumed to be the
common case for notes lookup). The new code even performs marginally
better in the worst case (where _all_ the notes are looked up).

In addition to this, comes the massive performance win associated with
organizing the notes tree according to some fanout scheme. Even a simple
2/38 fanout scheme is dramatically quicker to traverse (going from tens of
seconds to sub-second runtimes).

As for memory usage, the new code is marginally better than the old code in
the worst case, but in the case of looking up only some notes from a notes
tree with proper fanout, the new code uses only a small fraction of the
memory needed to hold the entire notes tree.

However, there is one casualty of this patch. The old notes lookup code was
able to parse notes that were associated with non-SHA1s (e.g. refs). The new
code requires the referenced object to be named by a SHA1 sum. Still, this
is not considered a major setback, since the notes infrastructure was not
originally intended to annotate objects outside the Git object database.

Cc: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |  317 +++++++++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 248 insertions(+), 69 deletions(-)

diff --git a/notes.c b/notes.c
index a5d888d..210c4b2 100644
--- a/notes.c
+++ b/notes.c
@@ -6,109 +6,288 @@
 #include "strbuf.h"
 #include "tree-walk.h"
 
-struct entry {
-	unsigned char commit_sha1[20];
-	unsigned char notes_sha1[20];
+/*
+ * Use a non-balancing simple 16-tree structure with struct int_node as
+ * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
+ * 16-array of pointers to its children.
+ * The bottom 2 bits of each pointer is used to identify the pointer type
+ * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
+ * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
+ * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
+ * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
+ *
+ * The root node is a statically allocated struct int_node.
+ */
+struct int_node {
+	void *a[16];
 };
 
-struct hash_map {
-	struct entry *entries;
-	off_t count, size;
+/*
+ * Leaf nodes come in two variants, note entries and subtree entries,
+ * distinguished by the LSb of the leaf node pointer (see above).
+ * As a note entry, the key is the SHA1 of the referenced commit, and the
+ * value is the SHA1 of the note object.
+ * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
+ * referenced commit, using the last byte of the key to store the length of
+ * the prefix. The value is the SHA1 of the tree object containing the notes
+ * subtree.
+ */
+struct leaf_node {
+	unsigned char key_sha1[20];
+	unsigned char val_sha1[20];
 };
 
-static int initialized;
-static struct hash_map hash_map;
+#define PTR_TYPE_NULL     0
+#define PTR_TYPE_INTERNAL 1
+#define PTR_TYPE_NOTE     2
+#define PTR_TYPE_SUBTREE  3
 
-static int hash_index(struct hash_map *map, const unsigned char *sha1)
-{
-	int i = ((*(unsigned int *)sha1) % map->size);
+#define GET_PTR_TYPE(ptr)       ((uintptr_t) (ptr) & 3)
+#define CLR_PTR_TYPE(ptr)       ((void *) ((uintptr_t) (ptr) & ~3))
+#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
 
-	for (;;) {
-		unsigned char *current = map->entries[i].commit_sha1;
+#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((~n & 0x01) << 2)) & 0x0f)
 
-		if (!hashcmp(sha1, current))
-			return i;
+#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
+	(memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
 
-		if (is_null_sha1(current))
-			return -1 - i;
+static struct int_node root_node;
 
-		if (++i == map->size)
-			i = 0;
+static int initialized;
+
+static void load_subtree(struct leaf_node *subtree, struct int_node *node,
+		unsigned int n);
+
+/*
+ * To find a leaf_node:
+ * 1. Start at the root node, with n = 0
+ * 2. Use the nth nibble of the key as an index into a:
+ *    - If a[n] is an int_node, recurse into that node and increment n
+ *    - If a leaf_node with matching key, return leaf_node (assert note entry)
+ *    - If a matching subtree entry, unpack that subtree entry (and remove it);
+ *      restart search at the current level.
+ *    - Otherwise, we end up at a NULL pointer, or a non-matching leaf_node.
+ *      Backtrack out of the recursion, one level at a time and check a[0]:
+ *      - If a[0] at the current level is a matching subtree entry, unpack that
+ *        subtree entry (and remove it); restart search at the current level.
+ */
+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
+		const unsigned char *key_sha1)
+{
+	struct leaf_node *l;
+	unsigned char i = GET_NIBBLE(n, key_sha1);
+	void *p = tree->a[i];
+
+	switch(GET_PTR_TYPE(p)) {
+	case PTR_TYPE_INTERNAL:
+		l = note_tree_find(CLR_PTR_TYPE(p), n + 1, key_sha1);
+		if (l)
+			return l;
+		break;
+	case PTR_TYPE_NOTE:
+		l = (struct leaf_node *) CLR_PTR_TYPE(p);
+		if (!hashcmp(key_sha1, l->key_sha1))
+			return l; /* return note object matching given key */
+		break;
+	case PTR_TYPE_SUBTREE:
+		l = (struct leaf_node *) CLR_PTR_TYPE(p);
+		if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
+			/* unpack tree and resume search */
+			tree->a[i] = NULL;
+			load_subtree(l, tree, n);
+			free(l);
+			return note_tree_find(tree, n, key_sha1);
+		}
+		break;
+	case PTR_TYPE_NULL:
+	default:
+		assert(!p);
+		break;
 	}
+
+	/*
+	 * Did not find key at this (or any lower) level.
+	 * Check if there's a matching subtree entry in tree->a[0].
+	 * If so, unpack tree and resume search.
+	 */
+	p = tree->a[0];
+	if (GET_PTR_TYPE(p) != PTR_TYPE_SUBTREE)
+		return NULL;
+	l = (struct leaf_node *) CLR_PTR_TYPE(p);
+	if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
+		/* unpack tree and resume search */
+		tree->a[0] = NULL;
+		load_subtree(l, tree, n);
+		free(l);
+		return note_tree_find(tree, n, key_sha1);
+	}
+	return NULL;
 }
 
-static void add_entry(const unsigned char *commit_sha1,
-		const unsigned char *notes_sha1)
+/*
+ * To insert a leaf_node:
+ * 1. Start at the root node, with n = 0
+ * 2. Use the nth nibble of the key as an index into a:
+ *    - If a[n] is NULL, store the tweaked pointer directly into a[n]
+ *    - If a[n] is an int_node, recurse into that node and increment n
+ *    - If a[n] is a leaf_node:
+ *      1. Check if they're equal, and handle that (abort? overwrite?)
+ *      2. Create a new int_node, and store both leaf_nodes there
+ *      3. Store the new int_node into a[n].
+ */
+static int note_tree_insert(struct int_node *tree, unsigned char n,
+		const struct leaf_node *entry, unsigned char type)
 {
-	int index;
-
-	if (hash_map.count + 1 > hash_map.size >> 1) {
-		int i, old_size = hash_map.size;
-		struct entry *old = hash_map.entries;
-
-		hash_map.size = old_size ? old_size << 1 : 64;
-		hash_map.entries = (struct entry *)
-			xcalloc(sizeof(struct entry), hash_map.size);
-
-		for (i = 0; i < old_size; i++)
-			if (!is_null_sha1(old[i].commit_sha1)) {
-				index = -1 - hash_index(&hash_map,
-						old[i].commit_sha1);
-				memcpy(hash_map.entries + index, old + i,
-					sizeof(struct entry));
-			}
-		free(old);
+	struct int_node *new_node;
+	const struct leaf_node *l;
+	int ret;
+	unsigned char i = GET_NIBBLE(n, entry->key_sha1);
+	void *p = tree->a[i];
+	assert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);
+	switch(GET_PTR_TYPE(p)) {
+	case PTR_TYPE_NULL:
+		assert(!p);
+		tree->a[i] = SET_PTR_TYPE(entry, type);
+		return 0;
+	case PTR_TYPE_INTERNAL:
+		return note_tree_insert(CLR_PTR_TYPE(p), n + 1, entry, type);
+	default:
+		assert(GET_PTR_TYPE(p) == PTR_TYPE_NOTE ||
+			GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE);
+		l = (const struct leaf_node *) CLR_PTR_TYPE(p);
+		if (!hashcmp(entry->key_sha1, l->key_sha1))
+			return -1; /* abort insert on matching key */
+		new_node = (struct int_node *)
+			xcalloc(sizeof(struct int_node), 1);
+		ret = note_tree_insert(new_node, n + 1,
+			CLR_PTR_TYPE(p), GET_PTR_TYPE(p));
+		if (ret) {
+			free(new_node);
+			return -1;
+		}
+		tree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
+		return note_tree_insert(new_node, n + 1, entry, type);
 	}
+}
 
-	index = hash_index(&hash_map, commit_sha1);
-	if (index < 0) {
-		index = -1 - index;
-		hash_map.count++;
+/* Free the entire notes data contained in the given tree */
+static void note_tree_free(struct int_node *tree)
+{
+	unsigned int i;
+	for (i = 0; i < 16; i++) {
+		void *p = tree->a[i];
+		switch(GET_PTR_TYPE(p)) {
+		case PTR_TYPE_INTERNAL:
+			note_tree_free(CLR_PTR_TYPE(p));
+			/* fall through */
+		case PTR_TYPE_NOTE:
+		case PTR_TYPE_SUBTREE:
+			free(CLR_PTR_TYPE(p));
+		}
 	}
+}
 
-	hashcpy(hash_map.entries[index].commit_sha1, commit_sha1);
-	hashcpy(hash_map.entries[index].notes_sha1, notes_sha1);
+/*
+ * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
+ * - hex      - Partial SHA1 segment in ASCII hex format
+ * - hex_len  - Length of above segment. Must be multiple of 2 between 0 and 40
+ * - sha1     - Partial SHA1 value is written here
+ * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
+ * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format).
+ * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
+ * Pads sha1 with NULs up to sha1_len (not included in returned length).
+ */
+static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
+		unsigned char *sha1, unsigned int sha1_len)
+{
+	unsigned int i, len = hex_len >> 1;
+	if (hex_len % 2 != 0 || len > sha1_len)
+		return -1;
+	for (i = 0; i < len; i++) {
+		unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
+		if (val & ~0xff)
+			return -1;
+		*sha1++ = val;
+		hex += 2;
+	}
+	for (; i < sha1_len; i++)
+		*sha1++ = 0;
+	return len;
 }
 
-static void initialize_hash_map(const char *notes_ref_name)
+static void load_subtree(struct leaf_node *subtree, struct int_node *node,
+		unsigned int n)
 {
-	unsigned char sha1[20], commit_sha1[20];
-	unsigned mode;
+	unsigned char commit_sha1[20];
+	unsigned int prefix_len;
+	int status;
+	void *buf;
 	struct tree_desc desc;
 	struct name_entry entry;
-	void *buf;
+
+	buf = fill_tree_descriptor(&desc, subtree->val_sha1);
+	if (!buf)
+		die("Could not read %s for notes-index",
+		     sha1_to_hex(subtree->val_sha1));
+
+	prefix_len = subtree->key_sha1[19];
+	assert(prefix_len * 2 >= n);
+	memcpy(commit_sha1, subtree->key_sha1, prefix_len);
+	while (tree_entry(&desc, &entry)) {
+		int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
+				commit_sha1 + prefix_len, 20 - prefix_len);
+		if (len < 0)
+			continue; /* entry.path is not a SHA1 sum. Skip */
+		len += prefix_len;
+
+		/*
+		 * If commit SHA1 is complete (len == 20), assume note object
+		 * If commit SHA1 is incomplete (len < 20), assume note subtree
+		 */
+		if (len <= 20) {
+			unsigned char type = PTR_TYPE_NOTE;
+			struct leaf_node *l = (struct leaf_node *)
+				xcalloc(sizeof(struct leaf_node), 1);
+			hashcpy(l->key_sha1, commit_sha1);
+			hashcpy(l->val_sha1, entry.sha1);
+			if (len < 20) {
+				l->key_sha1[19] = (unsigned char) len;
+				type = PTR_TYPE_SUBTREE;
+			}
+			status = note_tree_insert(node, n, l, type);
+			assert(!status);
+		}
+	}
+	free(buf);
+}
+
+static void initialize_notes(const char *notes_ref_name)
+{
+	unsigned char sha1[20], commit_sha1[20];
+	unsigned mode;
+	struct leaf_node root_tree;
 
 	if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
 	    get_tree_entry(commit_sha1, "", sha1, &mode))
 		return;
 
-	buf = fill_tree_descriptor(&desc, sha1);
-	if (!buf)
-		die("Could not read %s for notes-index", sha1_to_hex(sha1));
-
-	while (tree_entry(&desc, &entry))
-		if (!get_sha1(entry.path, commit_sha1))
-			add_entry(commit_sha1, entry.sha1);
-	free(buf);
+	hashclr(root_tree.key_sha1);
+	hashcpy(root_tree.val_sha1, sha1);
+	load_subtree(&root_tree, &root_node, 0);
 }
 
 static unsigned char *lookup_notes(const unsigned char *commit_sha1)
 {
-	int index;
-
-	if (!hash_map.size)
-		return NULL;
-
-	index = hash_index(&hash_map, commit_sha1);
-	if (index < 0)
-		return NULL;
-	return hash_map.entries[index].notes_sha1;
+	struct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);
+	if (found)
+		return found->val_sha1;
+	return NULL;
 }
 
 void free_notes(void)
 {
-	free(hash_map.entries);
-	memset(&hash_map, 0, sizeof(struct hash_map));
+	note_tree_free(&root_node);
+	memset(&root_node, 0, sizeof(struct int_node));
 	initialized = 0;
 }
 
@@ -127,7 +306,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 			notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
 		else if (!notes_ref_name)
 			notes_ref_name = GIT_NOTES_DEFAULT_REF;
-		initialize_hash_map(notes_ref_name);
+		initialize_notes(notes_ref_name);
 		initialized = 1;
 	}
 
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 12/22] Add selftests verifying that we can parse notes trees with various fanouts

[Johan Herland]

Signed-off-by: Johan Herland <johan@herland.net>
---
 t/t3303-notes-subtrees.sh |  104 +++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 104 insertions(+), 0 deletions(-)
 create mode 100755 t/t3303-notes-subtrees.sh

diff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh
new file mode 100755
index 0000000..cbb9d35
--- /dev/null
+++ b/t/t3303-notes-subtrees.sh
@@ -0,0 +1,104 @@
+#!/bin/sh
+
+test_description='Test commit notes organized in subtrees'
+
+. ./test-lib.sh
+
+number_of_commits=100
+
+start_note_commit () {
+	test_tick &&
+	cat <<INPUT_END
+commit refs/notes/commits
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes
+COMMIT
+
+from refs/notes/commits^0
+deleteall
+INPUT_END
+
+}
+
+verify_notes () {
+	git log | grep "^    " > output &&
+	i=$number_of_commits &&
+	while [ $i -gt 0 ]; do
+		echo "    commit #$i" &&
+		echo "    note for commit #$i" &&
+		i=$(($i-1));
+	done > expect &&
+	test_cmp expect output
+}
+
+test_expect_success "setup: create $number_of_commits commits" '
+
+	(
+		nr=0 &&
+		while [ $nr -lt $number_of_commits ]; do
+			nr=$(($nr+1)) &&
+			test_tick &&
+			cat <<INPUT_END
+commit refs/heads/master
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+commit #$nr
+COMMIT
+
+M 644 inline file
+data <<EOF
+file in commit #$nr
+EOF
+
+INPUT_END
+
+		done &&
+		test_tick &&
+		cat <<INPUT_END
+commit refs/notes/commits
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+no notes
+COMMIT
+
+deleteall
+
+INPUT_END
+
+	) |
+	git fast-import --quiet &&
+	git config core.notesRef refs/notes/commits
+'
+
+test_sha1_based () {
+	(
+		start_note_commit &&
+		nr=$number_of_commits &&
+		git rev-list refs/heads/master |
+		while read sha1; do
+			note_path=$(echo "$sha1" | sed "$1")
+			cat <<INPUT_END &&
+M 100644 inline $note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+			nr=$(($nr-1))
+		done
+	) |
+	git fast-import --quiet
+}
+
+test_expect_success 'test notes in 2/38-fanout' 'test_sha1_based "s|^..|&/|"'
+test_expect_success 'verify notes in 2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in 4/36-fanout' 'test_sha1_based "s|^....|&/|"'
+test_expect_success 'verify notes in 4/36-fanout' 'verify_notes'
+
+test_expect_success 'test notes in 2/2/36-fanout' 'test_sha1_based "s|^\(..\)\(..\)|\1/\2/|"'
+test_expect_success 'verify notes in 2/2/36-fanout' 'verify_notes'
+
+test_done
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 13/22] Refactor notes code to concatenate multiple notes annotating the same object

[Johan Herland]

Currently, having multiple notes referring to the same commit from various
locations in the notes tree is strongly discouraged, since only one of those
notes will be parsed and shown.

This patch teaches the notes code to _concatenate_ multiple notes that
annotate the same commit. Notes are concatenated by creating a new blob
object containing the concatenation of the notes in question, and
replacing them with the concatenated note in the internal notes tree
structure.

Getting the concatenation right requires being more proactive in unpacking
subtree entries in the internal notes tree structure, so that we don't return
a note prematurely (i.e. before having found all other notes that annotate
the same object). As such, this patch may incur a small performance penalty.

Suggested-by: Sam Vilain <sam@vilain.net>
Re-suggested-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |  243 +++++++++++++++++++++++++++++++++++++++++---------------------
 1 files changed, 161 insertions(+), 82 deletions(-)

diff --git a/notes.c b/notes.c
index 210c4b2..50a4672 100644
--- a/notes.c
+++ b/notes.c
@@ -59,115 +59,196 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 		unsigned int n);
 
 /*
- * To find a leaf_node:
+ * Search the tree until the appropriate location for the given key is found:
  * 1. Start at the root node, with n = 0
- * 2. Use the nth nibble of the key as an index into a:
- *    - If a[n] is an int_node, recurse into that node and increment n
- *    - If a leaf_node with matching key, return leaf_node (assert note entry)
+ * 2. If a[0] at the current level is a matching subtree entry, unpack that
+ *    subtree entry and remove it; restart search at the current level.
+ * 3. Use the nth nibble of the key as an index into a:
+ *    - If a[n] is an int_node, recurse from #2 into that node and increment n
  *    - If a matching subtree entry, unpack that subtree entry (and remove it);
  *      restart search at the current level.
- *    - Otherwise, we end up at a NULL pointer, or a non-matching leaf_node.
- *      Backtrack out of the recursion, one level at a time and check a[0]:
- *      - If a[0] at the current level is a matching subtree entry, unpack that
- *        subtree entry (and remove it); restart search at the current level.
+ *    - Otherwise, we have found one of the following:
+ *      - a subtree entry which does not match the key
+ *      - a note entry which may or may not match the key
+ *      - an unused leaf node (NULL)
+ *      In any case, set *tree and *n, and return pointer to the tree location.
  */
-static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
-		const unsigned char *key_sha1)
+static void **note_tree_search(struct int_node **tree,
+		unsigned char *n, const unsigned char *key_sha1)
 {
 	struct leaf_node *l;
-	unsigned char i = GET_NIBBLE(n, key_sha1);
-	void *p = tree->a[i];
+	unsigned char i;
+	void *p = (*tree)->a[0];
 
+	if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
+		l = (struct leaf_node *) CLR_PTR_TYPE(p);
+		if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
+			/* unpack tree and resume search */
+			(*tree)->a[0] = NULL;
+			load_subtree(l, *tree, *n);
+			free(l);
+			return note_tree_search(tree, n, key_sha1);
+		}
+	}
+
+	i = GET_NIBBLE(*n, key_sha1);
+	p = (*tree)->a[i];
 	switch(GET_PTR_TYPE(p)) {
 	case PTR_TYPE_INTERNAL:
-		l = note_tree_find(CLR_PTR_TYPE(p), n + 1, key_sha1);
-		if (l)
-			return l;
-		break;
-	case PTR_TYPE_NOTE:
-		l = (struct leaf_node *) CLR_PTR_TYPE(p);
-		if (!hashcmp(key_sha1, l->key_sha1))
-			return l; /* return note object matching given key */
-		break;
+		*tree = CLR_PTR_TYPE(p);
+		(*n)++;
+		return note_tree_search(tree, n, key_sha1);
 	case PTR_TYPE_SUBTREE:
 		l = (struct leaf_node *) CLR_PTR_TYPE(p);
 		if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
 			/* unpack tree and resume search */
-			tree->a[i] = NULL;
-			load_subtree(l, tree, n);
+			(*tree)->a[i] = NULL;
+			load_subtree(l, *tree, *n);
 			free(l);
-			return note_tree_find(tree, n, key_sha1);
+			return note_tree_search(tree, n, key_sha1);
 		}
-		break;
-	case PTR_TYPE_NULL:
+		/* fall through */
 	default:
-		assert(!p);
-		break;
+		return &((*tree)->a[i]);
 	}
+}
 
-	/*
-	 * Did not find key at this (or any lower) level.
-	 * Check if there's a matching subtree entry in tree->a[0].
-	 * If so, unpack tree and resume search.
-	 */
-	p = tree->a[0];
-	if (GET_PTR_TYPE(p) != PTR_TYPE_SUBTREE)
-		return NULL;
-	l = (struct leaf_node *) CLR_PTR_TYPE(p);
-	if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
-		/* unpack tree and resume search */
-		tree->a[0] = NULL;
-		load_subtree(l, tree, n);
-		free(l);
-		return note_tree_find(tree, n, key_sha1);
+/*
+ * To find a leaf_node:
+ * Search to the tree location appropriate for the given key:
+ * If a note entry with matching key, return the note entry, else return NULL.
+ */
+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
+		const unsigned char *key_sha1)
+{
+	void **p = note_tree_search(&tree, &n, key_sha1);
+	if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
+		struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
+		if (!hashcmp(key_sha1, l->key_sha1))
+			return l;
 	}
 	return NULL;
 }
 
+/* Create a new blob object by concatenating the two given blob objects */
+static int concatenate_notes(unsigned char *cur_sha1,
+		const unsigned char *new_sha1)
+{
+	char *cur_msg, *new_msg, *buf;
+	unsigned long cur_len, new_len, buf_len;
+	enum object_type cur_type, new_type;
+	int ret;
+
+	/* read in both note blob objects */
+	new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
+	if (!new_msg || !new_len || new_type != OBJ_BLOB) {
+		free(new_msg);
+		return 0;
+	}
+	cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
+	if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
+		free(cur_msg);
+		free(new_msg);
+		hashcpy(cur_sha1, new_sha1);
+		return 0;
+	}
+
+	/* we will separate the notes by a newline anyway */
+	if (cur_msg[cur_len - 1] == '\n')
+		cur_len--;
+
+	/* concatenate cur_msg and new_msg into buf */
+	buf_len = cur_len + 1 + new_len;
+	buf = (char *) xmalloc(buf_len);
+	memcpy(buf, cur_msg, cur_len);
+	buf[cur_len] = '\n';
+	memcpy(buf + cur_len + 1, new_msg, new_len);
+
+	free(cur_msg);
+	free(new_msg);
+
+	/* create a new blob object from buf */
+	ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
+	free(buf);
+	return ret;
+}
+
 /*
  * To insert a leaf_node:
- * 1. Start at the root node, with n = 0
- * 2. Use the nth nibble of the key as an index into a:
- *    - If a[n] is NULL, store the tweaked pointer directly into a[n]
- *    - If a[n] is an int_node, recurse into that node and increment n
- *    - If a[n] is a leaf_node:
- *      1. Check if they're equal, and handle that (abort? overwrite?)
- *      2. Create a new int_node, and store both leaf_nodes there
- *      3. Store the new int_node into a[n].
+ * Search to the tree location appropriate for the given leaf_node's key:
+ * - If location is unused (NULL), store the tweaked pointer directly there
+ * - If location holds a note entry that matches the note-to-be-inserted, then
+ *   concatenate the two notes.
+ * - If location holds a note entry that matches the subtree-to-be-inserted,
+ *   then unpack the subtree-to-be-inserted into the location.
+ * - If location holds a matching subtree entry, unpack the subtree at that
+ *   location, and restart the insert operation from that level.
+ * - Else, create a new int_node, holding both the node-at-location and the
+ *   node-to-be-inserted, and store the new int_node into the location.
  */
-static int note_tree_insert(struct int_node *tree, unsigned char n,
-		const struct leaf_node *entry, unsigned char type)
+static void note_tree_insert(struct int_node *tree, unsigned char n,
+		struct leaf_node *entry, unsigned char type)
 {
 	struct int_node *new_node;
-	const struct leaf_node *l;
-	int ret;
-	unsigned char i = GET_NIBBLE(n, entry->key_sha1);
-	void *p = tree->a[i];
-	assert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);
-	switch(GET_PTR_TYPE(p)) {
+	struct leaf_node *l;
+	void **p = note_tree_search(&tree, &n, entry->key_sha1);
+
+	assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
+	l = (struct leaf_node *) CLR_PTR_TYPE(*p);
+	switch(GET_PTR_TYPE(*p)) {
 	case PTR_TYPE_NULL:
-		assert(!p);
-		tree->a[i] = SET_PTR_TYPE(entry, type);
-		return 0;
-	case PTR_TYPE_INTERNAL:
-		return note_tree_insert(CLR_PTR_TYPE(p), n + 1, entry, type);
-	default:
-		assert(GET_PTR_TYPE(p) == PTR_TYPE_NOTE ||
-			GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE);
-		l = (const struct leaf_node *) CLR_PTR_TYPE(p);
-		if (!hashcmp(entry->key_sha1, l->key_sha1))
-			return -1; /* abort insert on matching key */
-		new_node = (struct int_node *)
-			xcalloc(sizeof(struct int_node), 1);
-		ret = note_tree_insert(new_node, n + 1,
-			CLR_PTR_TYPE(p), GET_PTR_TYPE(p));
-		if (ret) {
-			free(new_node);
-			return -1;
+		assert(!*p);
+		*p = SET_PTR_TYPE(entry, type);
+		return;
+	case PTR_TYPE_NOTE:
+		switch (type) {
+		case PTR_TYPE_NOTE:
+			if (!hashcmp(l->key_sha1, entry->key_sha1)) {
+				/* skip concatenation if l == entry */
+				if (!hashcmp(l->val_sha1, entry->val_sha1))
+					return;
+
+				if (concatenate_notes(l->val_sha1,
+						entry->val_sha1))
+					die("failed to concatenate note %s "
+					    "into note %s for commit %s",
+					    sha1_to_hex(entry->val_sha1),
+					    sha1_to_hex(l->val_sha1),
+					    sha1_to_hex(l->key_sha1));
+				free(entry);
+				return;
+			}
+			break;
+		case PTR_TYPE_SUBTREE:
+			if (!SUBTREE_SHA1_PREFIXCMP(l->key_sha1,
+						    entry->key_sha1)) {
+				/* unpack 'entry' */
+				load_subtree(entry, tree, n);
+				free(entry);
+				return;
+			}
+			break;
+		}
+		break;
+	case PTR_TYPE_SUBTREE:
+		if (!SUBTREE_SHA1_PREFIXCMP(entry->key_sha1, l->key_sha1)) {
+			/* unpack 'l' and restart insert */
+			*p = NULL;
+			load_subtree(l, tree, n);
+			free(l);
+			note_tree_insert(tree, n, entry, type);
+			return;
 		}
-		tree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
-		return note_tree_insert(new_node, n + 1, entry, type);
+		break;
 	}
+
+	/* non-matching leaf_node */
+	assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
+	       GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
+	new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
+	note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p));
+	*p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
+	note_tree_insert(new_node, n + 1, entry, type);
 }
 
 /* Free the entire notes data contained in the given tree */
@@ -220,7 +301,6 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 {
 	unsigned char commit_sha1[20];
 	unsigned int prefix_len;
-	int status;
 	void *buf;
 	struct tree_desc desc;
 	struct name_entry entry;
@@ -254,8 +334,7 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 				l->key_sha1[19] = (unsigned char) len;
 				type = PTR_TYPE_SUBTREE;
 			}
-			status = note_tree_insert(node, n, l, type);
-			assert(!status);
+			note_tree_insert(node, n, l, type);
 		}
 	}
 	free(buf);
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 14/22] Add selftests verifying concatenation of multiple notes for the same commit

[Johan Herland]

Also verify that multiple references to the _same_ note blob are _not_
concatenated.

Signed-off-by: Johan Herland <johan@herland.net>
---
 t/t3303-notes-subtrees.sh |   84 +++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 84 insertions(+), 0 deletions(-)

diff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh
index cbb9d35..edc4bc8 100755
--- a/t/t3303-notes-subtrees.sh
+++ b/t/t3303-notes-subtrees.sh
@@ -101,4 +101,88 @@ test_expect_success 'verify notes in 4/36-fanout' 'verify_notes'
 test_expect_success 'test notes in 2/2/36-fanout' 'test_sha1_based "s|^\(..\)\(..\)|\1/\2/|"'
 test_expect_success 'verify notes in 2/2/36-fanout' 'verify_notes'
 
+test_same_notes () {
+	(
+		start_note_commit &&
+		nr=$number_of_commits &&
+		git rev-list refs/heads/master |
+		while read sha1; do
+			first_note_path=$(echo "$sha1" | sed "$1")
+			second_note_path=$(echo "$sha1" | sed "$2")
+			cat <<INPUT_END &&
+M 100644 inline $second_note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+M 100644 inline $first_note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+			nr=$(($nr-1))
+		done
+	) |
+	git fast-import --quiet
+}
+
+test_expect_success 'test same notes in 4/36-fanout and 2/38-fanout' 'test_same_notes "s|^..|&/|" "s|^....|&/|"'
+test_expect_success 'verify same notes in 4/36-fanout and 2/38-fanout' 'verify_notes'
+
+test_expect_success 'test same notes in 2/38-fanout and 2/2/36-fanout' 'test_same_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^..|&/|"'
+test_expect_success 'verify same notes in 2/38-fanout and 2/2/36-fanout' 'verify_notes'
+
+test_expect_success 'test same notes in 4/36-fanout and 2/2/36-fanout' 'test_same_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^....|&/|"'
+test_expect_success 'verify same notes in 4/36-fanout and 2/2/36-fanout' 'verify_notes'
+
+test_concatenated_notes () {
+	(
+		start_note_commit &&
+		nr=$number_of_commits &&
+		git rev-list refs/heads/master |
+		while read sha1; do
+			first_note_path=$(echo "$sha1" | sed "$1")
+			second_note_path=$(echo "$sha1" | sed "$2")
+			cat <<INPUT_END &&
+M 100644 inline $second_note_path
+data <<EOF
+second note for commit #$nr
+EOF
+
+M 100644 inline $first_note_path
+data <<EOF
+first note for commit #$nr
+EOF
+
+INPUT_END
+
+			nr=$(($nr-1))
+		done
+	) |
+	git fast-import --quiet
+}
+
+verify_concatenated_notes () {
+    git log | grep "^    " > output &&
+    i=$number_of_commits &&
+    while [ $i -gt 0 ]; do
+        echo "    commit #$i" &&
+        echo "    first note for commit #$i" &&
+        echo "    second note for commit #$i" &&
+        i=$(($i-1));
+    done > expect &&
+    test_cmp expect output
+}
+
+test_expect_success 'test notes in 4/36-fanout concatenated with 2/38-fanout' 'test_concatenated_notes "s|^..|&/|" "s|^....|&/|"'
+test_expect_success 'verify notes in 4/36-fanout concatenated with 2/38-fanout' 'verify_concatenated_notes'
+
+test_expect_success 'test notes in 2/38-fanout concatenated with 2/2/36-fanout' 'test_concatenated_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^..|&/|"'
+test_expect_success 'verify notes in 2/38-fanout concatenated with 2/2/36-fanout' 'verify_concatenated_notes'
+
+test_expect_success 'test notes in 4/36-fanout concatenated with 2/2/36-fanout' 'test_concatenated_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^....|&/|"'
+test_expect_success 'verify notes in 4/36-fanout concatenated with 2/2/36-fanout' 'verify_concatenated_notes'
+
 test_done
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 15/22] Notes API: get_commit_notes() -> format_note() + remove the commit restriction

[Johan Herland]

There is really no reason why only commit objects can be annotated. By
changing the struct commit parameter to get_commit_notes() into a sha1 we
gain the ability to annotate any object type. To reflect this in the function
naming as well, we rename get_commit_notes() to format_note().

This patch also fixes comments and variable names throughout notes.c as a
consequence of the removal of the unnecessary 'commit' restriction.

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c  |   33 ++++++++++++++++-----------------
 notes.h  |   11 ++++++++++-
 pretty.c |    8 ++++----
 3 files changed, 30 insertions(+), 22 deletions(-)

diff --git a/notes.c b/notes.c
index 50a4672..0f7082f 100644
--- a/notes.c
+++ b/notes.c
@@ -1,5 +1,4 @@
 #include "cache.h"
-#include "commit.h"
 #include "notes.h"
 #include "refs.h"
 #include "utf8.h"
@@ -25,10 +24,10 @@ struct int_node {
 /*
  * Leaf nodes come in two variants, note entries and subtree entries,
  * distinguished by the LSb of the leaf node pointer (see above).
- * As a note entry, the key is the SHA1 of the referenced commit, and the
+ * As a note entry, the key is the SHA1 of the referenced object, and the
  * value is the SHA1 of the note object.
  * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
- * referenced commit, using the last byte of the key to store the length of
+ * referenced object, using the last byte of the key to store the length of
  * the prefix. The value is the SHA1 of the tree object containing the notes
  * subtree.
  */
@@ -211,7 +210,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
 				if (concatenate_notes(l->val_sha1,
 						entry->val_sha1))
 					die("failed to concatenate note %s "
-					    "into note %s for commit %s",
+					    "into note %s for object %s",
 					    sha1_to_hex(entry->val_sha1),
 					    sha1_to_hex(l->val_sha1),
 					    sha1_to_hex(l->key_sha1));
@@ -299,7 +298,7 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
 static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 		unsigned int n)
 {
-	unsigned char commit_sha1[20];
+	unsigned char object_sha1[20];
 	unsigned int prefix_len;
 	void *buf;
 	struct tree_desc desc;
@@ -312,23 +311,23 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 
 	prefix_len = subtree->key_sha1[19];
 	assert(prefix_len * 2 >= n);
-	memcpy(commit_sha1, subtree->key_sha1, prefix_len);
+	memcpy(object_sha1, subtree->key_sha1, prefix_len);
 	while (tree_entry(&desc, &entry)) {
 		int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
-				commit_sha1 + prefix_len, 20 - prefix_len);
+				object_sha1 + prefix_len, 20 - prefix_len);
 		if (len < 0)
 			continue; /* entry.path is not a SHA1 sum. Skip */
 		len += prefix_len;
 
 		/*
-		 * If commit SHA1 is complete (len == 20), assume note object
-		 * If commit SHA1 is incomplete (len < 20), assume note subtree
+		 * If object SHA1 is complete (len == 20), assume note object
+		 * If object SHA1 is incomplete (len < 20), assume note subtree
 		 */
 		if (len <= 20) {
 			unsigned char type = PTR_TYPE_NOTE;
 			struct leaf_node *l = (struct leaf_node *)
 				xcalloc(sizeof(struct leaf_node), 1);
-			hashcpy(l->key_sha1, commit_sha1);
+			hashcpy(l->key_sha1, object_sha1);
 			hashcpy(l->val_sha1, entry.sha1);
 			if (len < 20) {
 				l->key_sha1[19] = (unsigned char) len;
@@ -342,12 +341,12 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 
 static void initialize_notes(const char *notes_ref_name)
 {
-	unsigned char sha1[20], commit_sha1[20];
+	unsigned char sha1[20], object_sha1[20];
 	unsigned mode;
 	struct leaf_node root_tree;
 
-	if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
-	    get_tree_entry(commit_sha1, "", sha1, &mode))
+	if (!notes_ref_name || read_ref(notes_ref_name, object_sha1) ||
+	    get_tree_entry(object_sha1, "", sha1, &mode))
 		return;
 
 	hashclr(root_tree.key_sha1);
@@ -355,9 +354,9 @@ static void initialize_notes(const char *notes_ref_name)
 	load_subtree(&root_tree, &root_node, 0);
 }
 
-static unsigned char *lookup_notes(const unsigned char *commit_sha1)
+static unsigned char *lookup_notes(const unsigned char *object_sha1)
 {
-	struct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);
+	struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);
 	if (found)
 		return found->val_sha1;
 	return NULL;
@@ -370,7 +369,7 @@ void free_notes(void)
 	initialized = 0;
 }
 
-void get_commit_notes(const struct commit *commit, struct strbuf *sb,
+void format_note(const unsigned char *object_sha1, struct strbuf *sb,
 		const char *output_encoding, int flags)
 {
 	static const char utf8[] = "utf-8";
@@ -389,7 +388,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 		initialized = 1;
 	}
 
-	sha1 = lookup_notes(commit->object.sha1);
+	sha1 = lookup_notes(object_sha1);
 	if (!sha1)
 		return;
 
diff --git a/notes.h b/notes.h
index a1421e3..d745ed1 100644
--- a/notes.h
+++ b/notes.h
@@ -4,10 +4,19 @@
 /* Free (and de-initialize) the internal notes tree structure */
 void free_notes(void);
 
+/* Flags controlling how notes are formatted */
 #define NOTES_SHOW_HEADER 1
 #define NOTES_INDENT 2
 
-void get_commit_notes(const struct commit *commit, struct strbuf *sb,
+/*
+ * Fill the given strbuf with the notes associated with the given object.
+ *
+ * If the internal notes structure is not initialized, it will be auto-
+ * initialized to the default value (see documentation for init_notes() above).
+ *
+ * 'flags' is a bitwise combination of the above formatting flags.
+ */
+void format_note(const unsigned char *object_sha1, struct strbuf *sb,
 		const char *output_encoding, int flags);
 
 #endif
diff --git a/pretty.c b/pretty.c
index 7f350bb..81791f5 100644
--- a/pretty.c
+++ b/pretty.c
@@ -703,8 +703,8 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,
 		format_decoration(sb, commit);
 		return 1;
 	case 'N':
-		get_commit_notes(commit, sb, git_log_output_encoding ?
-			     git_log_output_encoding : git_commit_encoding, 0);
+		format_note(commit->object.sha1, sb, git_log_output_encoding ?
+			    git_log_output_encoding : git_commit_encoding, 0);
 		return 1;
 	}
 
@@ -982,8 +982,8 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
 		strbuf_addch(sb, '\n');
 
 	if (fmt != CMIT_FMT_ONELINE)
-		get_commit_notes(commit, sb, encoding,
-				 NOTES_SHOW_HEADER | NOTES_INDENT);
+		format_note(commit->object.sha1, sb, encoding,
+			    NOTES_SHOW_HEADER | NOTES_INDENT);
 
 	free(reencoded);
 }
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 16/22] Notes API: init_notes(): Initialize the notes tree from the given notes ref

[Johan Herland]

Created by a simple refactoring of initialize_notes().

Also add a new 'flags' parameter, which is a bitwise combination of notes
initialization flags. For now, there is only one flag - NOTES_INIT_EMPTY -
which indicates that the notes tree should not auto-load the contents of
the given (or default) notes ref, but rather should leave the notes tree
initialized to an empty state. This will become useful in the future when
manipulating the notes tree through the notes API.

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |   27 ++++++++++++++++-----------
 notes.h |   20 ++++++++++++++++++++
 2 files changed, 36 insertions(+), 11 deletions(-)

diff --git a/notes.c b/notes.c
index 0f7082f..f2bacbb 100644
--- a/notes.c
+++ b/notes.c
@@ -339,13 +339,25 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 	free(buf);
 }
 
-static void initialize_notes(const char *notes_ref_name)
+void init_notes(const char *notes_ref, int flags)
 {
 	unsigned char sha1[20], object_sha1[20];
 	unsigned mode;
 	struct leaf_node root_tree;
 
-	if (!notes_ref_name || read_ref(notes_ref_name, object_sha1) ||
+	assert(!initialized);
+	initialized = 1;
+
+	if (!notes_ref) {
+		const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
+		if (env)
+			notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
+		else
+			notes_ref = GIT_NOTES_DEFAULT_REF;
+	}
+
+	if (flags & NOTES_INIT_EMPTY || !notes_ref ||
+	    read_ref(notes_ref, object_sha1) ||
 	    get_tree_entry(object_sha1, "", sha1, &mode))
 		return;
 
@@ -378,15 +390,8 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
 	unsigned long linelen, msglen;
 	enum object_type type;
 
-	if (!initialized) {
-		const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
-		if (env)
-			notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
-		else if (!notes_ref_name)
-			notes_ref_name = GIT_NOTES_DEFAULT_REF;
-		initialize_notes(notes_ref_name);
-		initialized = 1;
-	}
+	if (!initialized)
+		init_notes(NULL, 0);
 
 	sha1 = lookup_notes(object_sha1);
 	if (!sha1)
diff --git a/notes.h b/notes.h
index d745ed1..6b52799 100644
--- a/notes.h
+++ b/notes.h
@@ -1,6 +1,26 @@
 #ifndef NOTES_H
 #define NOTES_H
 
+/*
+ * Flags controlling behaviour of notes tree initialization
+ *
+ * Default behaviour is to initialize the notes tree from the tree object
+ * specified by the given (or default) notes ref.
+ */
+#define NOTES_INIT_EMPTY 1
+
+/*
+ * Initialize internal notes tree structure with the notes tree at the given
+ * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment
+ * variable is used, and if that is missing, the default notes ref is used
+ * ("refs/notes/commits").
+ *
+ * If you need to re-intialize the internal notes tree structure (e.g. loading
+ * from a different notes ref), please first de-initialize the current notes
+ * tree by calling free_notes().
+ */
+void init_notes(const char *notes_ref, int flags);
+
 /* Free (and de-initialize) the internal notes tree structure */
 void free_notes(void);
 
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 17/22] Notes API: add_note(): Add note objects to the internal notes tree structure

[Johan Herland]

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |   11 +++++++++++
 notes.h |    4 ++++
 2 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/notes.c b/notes.c
index f2bacbb..49a3e86 100644
--- a/notes.c
+++ b/notes.c
@@ -366,6 +366,17 @@ void init_notes(const char *notes_ref, int flags)
 	load_subtree(&root_tree, &root_node, 0);
 }
 
+void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)
+{
+	struct leaf_node *l;
+
+	assert(initialized);
+	l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
+	hashcpy(l->key_sha1, object_sha1);
+	hashcpy(l->val_sha1, note_sha1);
+	note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);
+}
+
 static unsigned char *lookup_notes(const unsigned char *object_sha1)
 {
 	struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);
diff --git a/notes.h b/notes.h
index 6b52799..5f22852 100644
--- a/notes.h
+++ b/notes.h
@@ -21,6 +21,10 @@
  */
 void init_notes(const char *notes_ref, int flags);
 
+/* Add the given note object to the internal notes tree structure */
+void add_note(const unsigned char *object_sha1,
+		const unsigned char *note_sha1);
+
 /* Free (and de-initialize) the internal notes tree structure */
 void free_notes(void);
 
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 18/22] Notes API: get_note(): Return the note annotating the given object

[Johan Herland]

Created by a simple cleanup and rename of lookup_notes().

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |   15 ++++++++-------
 notes.h |    3 +++
 2 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/notes.c b/notes.c
index 49a3e86..2196a5f 100644
--- a/notes.c
+++ b/notes.c
@@ -377,12 +377,13 @@ void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)
 	note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);
 }
 
-static unsigned char *lookup_notes(const unsigned char *object_sha1)
+const unsigned char *get_note(const unsigned char *object_sha1)
 {
-	struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);
-	if (found)
-		return found->val_sha1;
-	return NULL;
+	struct leaf_node *found;
+
+	assert(initialized);
+	found = note_tree_find(&root_node, 0, object_sha1);
+	return found ? found->val_sha1 : NULL;
 }
 
 void free_notes(void)
@@ -396,7 +397,7 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
 		const char *output_encoding, int flags)
 {
 	static const char utf8[] = "utf-8";
-	unsigned char *sha1;
+	const unsigned char *sha1;
 	char *msg, *msg_p;
 	unsigned long linelen, msglen;
 	enum object_type type;
@@ -404,7 +405,7 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
 	if (!initialized)
 		init_notes(NULL, 0);
 
-	sha1 = lookup_notes(object_sha1);
+	sha1 = get_note(object_sha1);
 	if (!sha1)
 		return;
 
diff --git a/notes.h b/notes.h
index 5f22852..21a8930 100644
--- a/notes.h
+++ b/notes.h
@@ -25,6 +25,9 @@ void init_notes(const char *notes_ref, int flags);
 void add_note(const unsigned char *object_sha1,
 		const unsigned char *note_sha1);
 
+/* Get the note object SHA1 containing the note data for the given object */
+const unsigned char *get_note(const unsigned char *object_sha1);
+
 /* Free (and de-initialize) the internal notes tree structure */
 void free_notes(void);
 
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 19/22] Notes API: for_each_note(): Traverse the entire notes tree with a callback

[Johan Herland]

This includes a first attempt at creating an optimal fanout scheme (which
is created on-the-fly, while traversing).

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |  101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 notes.h |    9 +++++
 2 files changed, 110 insertions(+), 0 deletions(-)

diff --git a/notes.c b/notes.c
index 2196a5f..9581b98 100644
--- a/notes.c
+++ b/notes.c
@@ -339,6 +339,101 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 	free(buf);
 }
 
+/*
+ * Determine optimal on-disk fanout for this part of the notes tree
+ *
+ * Given a (sub)tree and the level in the internal tree structure, determine
+ * whether or not the given existing fanout should be expanded for this
+ * (sub)tree.
+ *
+ * Values of the 'fanout' variable:
+ * - 0: No fanout (all notes are stored directly in the root notes tree)
+ * - 1: 2/38 fanout
+ * - 2: 2/2/36 fanout
+ * - 3: 2/2/2/34 fanout
+ * etc.
+ */
+static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
+		unsigned char fanout)
+{
+	/*
+	 * The following is a simple heuristic that works well in practice:
+	 * For each even-numbered 16-tree level (remember that each on-disk
+	 * fanout level corresponds to two 16-tree levels), peek at all 16
+	 * entries at that tree level. If any of them are subtree entries, then
+	 * there are likely plenty of notes below this level, so we return an
+	 * incremented fanout immediately. Otherwise, we return an incremented
+	 * fanout only if all of the entries at this level are int_nodes.
+	 */
+	unsigned int i;
+	if ((n % 2) || (n > 2 * fanout))
+		return fanout;
+	for (i = 0; i < 16; i++) {
+		switch(GET_PTR_TYPE(tree->a[i])) {
+		case PTR_TYPE_SUBTREE:
+			return fanout + 1;
+		case PTR_TYPE_INTERNAL:
+			continue;
+		default:
+			return fanout;
+		}
+	}
+	return fanout + 1;
+}
+
+static void construct_path_with_fanout(const unsigned char *sha1,
+		unsigned char fanout, char *path)
+{
+	unsigned int i = 0, j = 0;
+	const char *hex_sha1 = sha1_to_hex(sha1);
+	assert(fanout < 20);
+	while (fanout) {
+		path[i++] = hex_sha1[j++];
+		path[i++] = hex_sha1[j++];
+		path[i++] = '/';
+		fanout--;
+	}
+	strcpy(path + i, hex_sha1 + j);
+}
+
+static int for_each_note_helper(struct int_node *tree, unsigned char n,
+		unsigned char fanout, each_note_fn fn, void *cb_data)
+{
+	unsigned int i;
+	void *p;
+	int ret = 0;
+	struct leaf_node *l;
+	static char path[40 + 19 + 1];  /* hex SHA1 + 19 * '/' + NUL */
+
+	fanout = determine_fanout(tree, n, fanout);
+	for (i = 0; i < 16; i++) {
+redo:
+		p = tree->a[i];
+		switch(GET_PTR_TYPE(p)) {
+		case PTR_TYPE_INTERNAL:
+			/* recurse into int_node */
+			ret = for_each_note_helper(
+				CLR_PTR_TYPE(p), n + 1, fanout, fn, cb_data);
+			break;
+		case PTR_TYPE_SUBTREE:
+			/* unpack subtree and resume traversal */
+			l = (struct leaf_node *) CLR_PTR_TYPE(p);
+			tree->a[i] = NULL;
+			load_subtree(l, tree, n);
+			free(l);
+			goto redo;
+		case PTR_TYPE_NOTE:
+			l = (struct leaf_node *) CLR_PTR_TYPE(p);
+			construct_path_with_fanout(l->key_sha1, fanout, path);
+			ret = fn(l->key_sha1, l->val_sha1, path, cb_data);
+			break;
+		}
+		if (ret)
+			return ret;
+	}
+	return 0;
+}
+
 void init_notes(const char *notes_ref, int flags)
 {
 	unsigned char sha1[20], object_sha1[20];
@@ -386,6 +481,12 @@ const unsigned char *get_note(const unsigned char *object_sha1)
 	return found ? found->val_sha1 : NULL;
 }
 
+int for_each_note(each_note_fn fn, void *cb_data)
+{
+	assert(initialized);
+	return for_each_note_helper(&root_node, 0, 0, fn, cb_data);
+}
+
 void free_notes(void)
 {
 	note_tree_free(&root_node);
diff --git a/notes.h b/notes.h
index 21a8930..28648fd 100644
--- a/notes.h
+++ b/notes.h
@@ -28,6 +28,15 @@ void add_note(const unsigned char *object_sha1,
 /* Get the note object SHA1 containing the note data for the given object */
 const unsigned char *get_note(const unsigned char *object_sha1);
 
+/*
+ * Calls the specified function for each note until it returns nonzero,
+ * and returns the value
+ */
+typedef int each_note_fn(const unsigned char *object_sha1,
+		const unsigned char *note_sha1, const char *note_tree_path,
+		void *cb_data);
+int for_each_note(each_note_fn fn, void *cb_data);
+
 /* Free (and de-initialize) the internal notes tree structure */
 void free_notes(void);
 
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 20/22] Notes API: Allow multiple concurrent notes trees with new struct notes_tree

[Johan Herland]

The new struct notes_tree encapsulates access to a specific notes tree.
It is provided to allow callers to interface with several different notes
trees simultaneously.

A struct notes_tree * parameter is added to every function in the notes API.
In all cases, NULL can be passed, in which case, a falback "default" notes
tree (declared in notes.c) is used.

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c  |   67 ++++++++++++++++++++++++++++++++++++++-----------------------
 notes.h  |   57 +++++++++++++++++++++++++++++++++++++--------------
 pretty.c |    4 +-
 3 files changed, 85 insertions(+), 43 deletions(-)

diff --git a/notes.c b/notes.c
index 9581b98..a5d9736 100644
--- a/notes.c
+++ b/notes.c
@@ -50,9 +50,7 @@ struct leaf_node {
 #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
 	(memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
 
-static struct int_node root_node;
-
-static int initialized;
+static struct notes_tree default_tree;
 
 static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 		unsigned int n);
@@ -434,14 +432,15 @@ redo:
 	return 0;
 }
 
-void init_notes(const char *notes_ref, int flags)
+void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
 {
 	unsigned char sha1[20], object_sha1[20];
 	unsigned mode;
 	struct leaf_node root_tree;
 
-	assert(!initialized);
-	initialized = 1;
+	if (!t)
+		t = &default_tree;
+	assert(!t->initialized);
 
 	if (!notes_ref) {
 		const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
@@ -451,6 +450,10 @@ void init_notes(const char *notes_ref, int flags)
 			notes_ref = GIT_NOTES_DEFAULT_REF;
 	}
 
+	t->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
+	t->ref = notes_ref ? xstrdup(notes_ref) : NULL;
+	t->initialized = 1;
+
 	if (flags & NOTES_INIT_EMPTY || !notes_ref ||
 	    read_ref(notes_ref, object_sha1) ||
 	    get_tree_entry(object_sha1, "", sha1, &mode))
@@ -458,44 +461,56 @@ void init_notes(const char *notes_ref, int flags)
 
 	hashclr(root_tree.key_sha1);
 	hashcpy(root_tree.val_sha1, sha1);
-	load_subtree(&root_tree, &root_node, 0);
+	load_subtree(&root_tree, t->root, 0);
 }
 
-void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)
+void add_note(struct notes_tree *t, const unsigned char *object_sha1,
+		const unsigned char *note_sha1)
 {
 	struct leaf_node *l;
 
-	assert(initialized);
+	if (!t)
+		t = &default_tree;
+	assert(t->initialized);
 	l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
 	hashcpy(l->key_sha1, object_sha1);
 	hashcpy(l->val_sha1, note_sha1);
-	note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);
+	note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);
 }
 
-const unsigned char *get_note(const unsigned char *object_sha1)
+const unsigned char *get_note(struct notes_tree *t,
+		const unsigned char *object_sha1)
 {
 	struct leaf_node *found;
 
-	assert(initialized);
-	found = note_tree_find(&root_node, 0, object_sha1);
+	if (!t)
+		t = &default_tree;
+	assert(t->initialized);
+	found = note_tree_find(t->root, 0, object_sha1);
 	return found ? found->val_sha1 : NULL;
 }
 
-int for_each_note(each_note_fn fn, void *cb_data)
+int for_each_note(struct notes_tree *t, each_note_fn fn, void *cb_data)
 {
-	assert(initialized);
-	return for_each_note_helper(&root_node, 0, 0, fn, cb_data);
+	if (!t)
+		t = &default_tree;
+	assert(t->initialized);
+	return for_each_note_helper(t->root, 0, 0, fn, cb_data);
 }
 
-void free_notes(void)
+void free_notes(struct notes_tree *t)
 {
-	note_tree_free(&root_node);
-	memset(&root_node, 0, sizeof(struct int_node));
-	initialized = 0;
+	if (!t)
+		t = &default_tree;
+	if (t->root)
+		note_tree_free(t->root);
+	free(t->root);
+	free(t->ref);
+	memset(t, 0, sizeof(struct notes_tree));
 }
 
-void format_note(const unsigned char *object_sha1, struct strbuf *sb,
-		const char *output_encoding, int flags)
+void format_note(struct notes_tree *t, const unsigned char *object_sha1,
+		struct strbuf *sb, const char *output_encoding, int flags)
 {
 	static const char utf8[] = "utf-8";
 	const unsigned char *sha1;
@@ -503,10 +518,12 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
 	unsigned long linelen, msglen;
 	enum object_type type;
 
-	if (!initialized)
-		init_notes(NULL, 0);
+	if (!t)
+		t = &default_tree;
+	if (!t->initialized)
+		init_notes(t, NULL, 0);
 
-	sha1 = get_note(object_sha1);
+	sha1 = get_note(t, object_sha1);
 	if (!sha1)
 		return;
 
diff --git a/notes.h b/notes.h
index 28648fd..181c3d6 100644
--- a/notes.h
+++ b/notes.h
@@ -2,6 +2,21 @@
 #define NOTES_H
 
 /*
+ * Notes tree object
+ *
+ * Encapsulates the internal notes tree structure associated with a notes ref.
+ * Whenever a struct notes_tree pointer is required below, you may pass NULL in
+ * order to use the default/internal notes tree. E.g. you only need to pass a
+ * non-NULL value if you need to refer to several different notes trees
+ * simultaneously.
+ */
+struct notes_tree {
+	struct int_node *root;
+	char *ref;
+	int initialized;
+};
+
+/*
  * Flags controlling behaviour of notes tree initialization
  *
  * Default behaviour is to initialize the notes tree from the tree object
@@ -10,35 +25,43 @@
 #define NOTES_INIT_EMPTY 1
 
 /*
- * Initialize internal notes tree structure with the notes tree at the given
+ * Initialize the given notes_tree with the notes tree structure at the given
  * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment
  * variable is used, and if that is missing, the default notes ref is used
  * ("refs/notes/commits").
  *
- * If you need to re-intialize the internal notes tree structure (e.g. loading
- * from a different notes ref), please first de-initialize the current notes
- * tree by calling free_notes().
+ * If you need to re-intialize a notes_tree structure (e.g. when switching from
+ * one notes ref to another), you must first de-initialize the notes_tree
+ * structure by calling free_notes(struct notes_tree *).
+ *
+ * If you pass t == NULL, the default internal notes_tree will be initialized.
+ *
+ * Precondition: The notes_tree structure is zeroed (this can be achieved with
+ * memset(t, 0, sizeof(struct notes_tree)))
  */
-void init_notes(const char *notes_ref, int flags);
+void init_notes(struct notes_tree *t, const char *notes_ref, int flags);
 
-/* Add the given note object to the internal notes tree structure */
-void add_note(const unsigned char *object_sha1,
+/* Add the given note object to the given notes_tree structure */
+void add_note(struct notes_tree *t, const unsigned char *object_sha1,
 		const unsigned char *note_sha1);
 
 /* Get the note object SHA1 containing the note data for the given object */
-const unsigned char *get_note(const unsigned char *object_sha1);
+const unsigned char *get_note(struct notes_tree *t,
+		const unsigned char *object_sha1);
 
 /*
- * Calls the specified function for each note until it returns nonzero,
- * and returns the value
+ * Calls the specified function for each note in the given notes_tree
+ *
+ * If the callback returns nonzero, the note walk is aborted, and the return
+ * value from the callback is returned from for_each_note().
  */
 typedef int each_note_fn(const unsigned char *object_sha1,
 		const unsigned char *note_sha1, const char *note_tree_path,
 		void *cb_data);
-int for_each_note(each_note_fn fn, void *cb_data);
+int for_each_note(struct notes_tree *t, each_note_fn fn, void *cb_data);
 
-/* Free (and de-initialize) the internal notes tree structure */
-void free_notes(void);
+/* Free (and de-initialize) the give notes_tree structure */
+void free_notes(struct notes_tree *t);
 
 /* Flags controlling how notes are formatted */
 #define NOTES_SHOW_HEADER 1
@@ -47,12 +70,14 @@ void free_notes(void);
 /*
  * Fill the given strbuf with the notes associated with the given object.
  *
- * If the internal notes structure is not initialized, it will be auto-
+ * If the given notes_tree structure is not initialized, it will be auto-
  * initialized to the default value (see documentation for init_notes() above).
+ * If the given notes_tree is NULL, the internal/default notes_tree will be
+ * used instead.
  *
  * 'flags' is a bitwise combination of the above formatting flags.
  */
-void format_note(const unsigned char *object_sha1, struct strbuf *sb,
-		const char *output_encoding, int flags);
+void format_note(struct notes_tree *t, const unsigned char *object_sha1,
+		struct strbuf *sb, const char *output_encoding, int flags);
 
 #endif
diff --git a/pretty.c b/pretty.c
index 81791f5..5ceb702 100644
--- a/pretty.c
+++ b/pretty.c
@@ -703,7 +703,7 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,
 		format_decoration(sb, commit);
 		return 1;
 	case 'N':
-		format_note(commit->object.sha1, sb, git_log_output_encoding ?
+		format_note(NULL, commit->object.sha1, sb, git_log_output_encoding ?
 			    git_log_output_encoding : git_commit_encoding, 0);
 		return 1;
 	}
@@ -982,7 +982,7 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
 		strbuf_addch(sb, '\n');
 
 	if (fmt != CMIT_FMT_ONELINE)
-		format_note(commit->object.sha1, sb, encoding,
+		format_note(NULL, commit->object.sha1, sb, encoding,
 			    NOTES_SHOW_HEADER | NOTES_INDENT);
 
 	free(reencoded);
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 21/22] Refactor notes concatenation into a flexible interface for combining notes

[Johan Herland]

When adding a note to an object that already has an existing note, the
current solution is to concatenate the contents of the two notes. However,
the caller may instead wish to _overwrite_ the existing note with the new
note, or maybe even _ignore_ the new note, and keep the existing one. There
might also be other ways of combining notes that are only known to the
caller.

Therefore, instead of unconditionally concatenating notes, we let the caller
specify how to combine notes, by passing in a pointer to a function for
combining notes. The caller may choose to implement its own function for
notes combining, but normally one of the following three conveniently
supplied notes combination functions will be sufficient:

- combine_notes_concatenate() combines the two notes by appending the
  contents of the new note to the contents of the existing note.

- combine_notes_overwrite() replaces the existing note with the new note.

- combine_notes_ignore() keeps the existing note, and ignores the new note.

A combine_notes function can be passed to init_notes() to choose a default
combine_notes function for that notes tree. If NULL is given, the notes tree
falls back to combine_notes_concatenate() as the ultimate default.

A combine_notes function can also be passed directly to add_note(), to
control the notes combining behaviour for a note addition in particular.
If NULL is passed, the combine_notes function registered for the given
notes tree is used.

Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |  132 +++++++++++++++++++++++++++++++++++---------------------------
 notes.h |   34 +++++++++++++++-
 2 files changed, 106 insertions(+), 60 deletions(-)

diff --git a/notes.c b/notes.c
index a5d9736..19ae492 100644
--- a/notes.c
+++ b/notes.c
@@ -127,55 +127,12 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
 	return NULL;
 }
 
-/* Create a new blob object by concatenating the two given blob objects */
-static int concatenate_notes(unsigned char *cur_sha1,
-		const unsigned char *new_sha1)
-{
-	char *cur_msg, *new_msg, *buf;
-	unsigned long cur_len, new_len, buf_len;
-	enum object_type cur_type, new_type;
-	int ret;
-
-	/* read in both note blob objects */
-	new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
-	if (!new_msg || !new_len || new_type != OBJ_BLOB) {
-		free(new_msg);
-		return 0;
-	}
-	cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
-	if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
-		free(cur_msg);
-		free(new_msg);
-		hashcpy(cur_sha1, new_sha1);
-		return 0;
-	}
-
-	/* we will separate the notes by a newline anyway */
-	if (cur_msg[cur_len - 1] == '\n')
-		cur_len--;
-
-	/* concatenate cur_msg and new_msg into buf */
-	buf_len = cur_len + 1 + new_len;
-	buf = (char *) xmalloc(buf_len);
-	memcpy(buf, cur_msg, cur_len);
-	buf[cur_len] = '\n';
-	memcpy(buf + cur_len + 1, new_msg, new_len);
-
-	free(cur_msg);
-	free(new_msg);
-
-	/* create a new blob object from buf */
-	ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
-	free(buf);
-	return ret;
-}
-
 /*
  * To insert a leaf_node:
  * Search to the tree location appropriate for the given leaf_node's key:
  * - If location is unused (NULL), store the tweaked pointer directly there
  * - If location holds a note entry that matches the note-to-be-inserted, then
- *   concatenate the two notes.
+ *   combine the two notes (by calling the given combine_notes function).
  * - If location holds a note entry that matches the subtree-to-be-inserted,
  *   then unpack the subtree-to-be-inserted into the location.
  * - If location holds a matching subtree entry, unpack the subtree at that
@@ -184,7 +141,8 @@ static int concatenate_notes(unsigned char *cur_sha1,
  *   node-to-be-inserted, and store the new int_node into the location.
  */
 static void note_tree_insert(struct int_node *tree, unsigned char n,
-		struct leaf_node *entry, unsigned char type)
+		struct leaf_node *entry, unsigned char type,
+		combine_notes_fn combine_notes)
 {
 	struct int_node *new_node;
 	struct leaf_node *l;
@@ -205,12 +163,11 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
 				if (!hashcmp(l->val_sha1, entry->val_sha1))
 					return;
 
-				if (concatenate_notes(l->val_sha1,
-						entry->val_sha1))
-					die("failed to concatenate note %s "
-					    "into note %s for object %s",
-					    sha1_to_hex(entry->val_sha1),
+				if (combine_notes(l->val_sha1, entry->val_sha1))
+					die("failed to combine notes %s and %s"
+					    " for object %s",
 					    sha1_to_hex(l->val_sha1),
+					    sha1_to_hex(entry->val_sha1),
 					    sha1_to_hex(l->key_sha1));
 				free(entry);
 				return;
@@ -233,7 +190,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
 			*p = NULL;
 			load_subtree(l, tree, n);
 			free(l);
-			note_tree_insert(tree, n, entry, type);
+			note_tree_insert(tree, n, entry, type, combine_notes);
 			return;
 		}
 		break;
@@ -243,9 +200,9 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
 	assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
 	       GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
 	new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
-	note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p));
+	note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p), combine_notes);
 	*p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
-	note_tree_insert(new_node, n + 1, entry, type);
+	note_tree_insert(new_node, n + 1, entry, type, combine_notes);
 }
 
 /* Free the entire notes data contained in the given tree */
@@ -331,7 +288,8 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 				l->key_sha1[19] = (unsigned char) len;
 				type = PTR_TYPE_SUBTREE;
 			}
-			note_tree_insert(node, n, l, type);
+			note_tree_insert(node, n, l, type,
+					combine_notes_concatenate);
 		}
 	}
 	free(buf);
@@ -432,7 +390,59 @@ redo:
 	return 0;
 }
 
-void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
+int combine_notes_concatenate(unsigned char *cur_sha1, const unsigned char *new_sha1)
+{
+	char *cur_msg, *new_msg, *buf;
+	unsigned long cur_len, new_len, buf_len;
+	enum object_type cur_type, new_type;
+	int ret;
+
+	/* read in both note blob objects */
+	new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
+	if (!new_msg || !new_len || new_type != OBJ_BLOB) {
+		free(new_msg);
+		return 0;
+	}
+	cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
+	if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
+		free(cur_msg);
+		free(new_msg);
+		hashcpy(cur_sha1, new_sha1);
+		return 0;
+	}
+
+	/* we will separate the notes by a newline anyway */
+	if (cur_msg[cur_len - 1] == '\n')
+		cur_len--;
+
+	/* concatenate cur_msg and new_msg into buf */
+	buf_len = cur_len + 1 + new_len;
+	buf = (char *) xmalloc(buf_len);
+	memcpy(buf, cur_msg, cur_len);
+	buf[cur_len] = '\n';
+	memcpy(buf + cur_len + 1, new_msg, new_len);
+	free(cur_msg);
+	free(new_msg);
+
+	/* create a new blob object from buf */
+	ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
+	free(buf);
+	return ret;
+}
+
+int combine_notes_overwrite(unsigned char *cur_sha1, const unsigned char *new_sha1)
+{
+	hashcpy(cur_sha1, new_sha1);
+	return 0;
+}
+
+int combine_notes_ignore(unsigned char *cur_sha1, const unsigned char *new_sha1)
+{
+	return 0;
+}
+
+void init_notes(struct notes_tree *t, const char *notes_ref,
+		combine_notes_fn combine_notes, int flags)
 {
 	unsigned char sha1[20], object_sha1[20];
 	unsigned mode;
@@ -450,8 +460,12 @@ void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
 			notes_ref = GIT_NOTES_DEFAULT_REF;
 	}
 
+	if (!combine_notes)
+		combine_notes = combine_notes_concatenate;
+
 	t->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
 	t->ref = notes_ref ? xstrdup(notes_ref) : NULL;
+	t->combine_notes = combine_notes;
 	t->initialized = 1;
 
 	if (flags & NOTES_INIT_EMPTY || !notes_ref ||
@@ -465,17 +479,19 @@ void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
 }
 
 void add_note(struct notes_tree *t, const unsigned char *object_sha1,
-		const unsigned char *note_sha1)
+		const unsigned char *note_sha1, combine_notes_fn combine_notes)
 {
 	struct leaf_node *l;
 
 	if (!t)
 		t = &default_tree;
 	assert(t->initialized);
+	if (!combine_notes)
+		combine_notes = t->combine_notes;
 	l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
 	hashcpy(l->key_sha1, object_sha1);
 	hashcpy(l->val_sha1, note_sha1);
-	note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);
+	note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE, combine_notes);
 }
 
 const unsigned char *get_note(struct notes_tree *t,
@@ -521,7 +537,7 @@ void format_note(struct notes_tree *t, const unsigned char *object_sha1,
 	if (!t)
 		t = &default_tree;
 	if (!t->initialized)
-		init_notes(t, NULL, 0);
+		init_notes(t, NULL, NULL, 0);
 
 	sha1 = get_note(t, object_sha1);
 	if (!sha1)
diff --git a/notes.h b/notes.h
index 181c3d6..f5d4ccd 100644
--- a/notes.h
+++ b/notes.h
@@ -2,6 +2,30 @@
 #define NOTES_H
 
 /*
+ * Function type for combining two notes annotating the same object.
+ *
+ * When adding a new note annotating the same object as an existing note, it is
+ * up to the caller to decide how to combine the two notes. The decision is
+ * made by passing in a function of the following form. The function accepts
+ * two SHA1s -- of the existing note and the new note, respectively. The
+ * function then combines the notes in whatever way it sees fit, and writes the
+ * resulting SHA1 into the first SHA1 argument (cur_sha1). A non-zero return
+ * value indicates failure.
+ *
+ * The two given SHA1s are guaranteed to be non-NULL and different.
+ *
+ * The default combine_notes function (you get this when passing NULL) is
+ * combine_notes_concatenate(), which appends the contents of the new note to
+ * the contents of the existing note.
+ */
+typedef int combine_notes_fn(unsigned char *cur_sha1, const unsigned char *new_sha1);
+
+/* Common notes combinators */
+int combine_notes_concatenate(unsigned char *cur_sha1, const unsigned char *new_sha1);
+int combine_notes_overwrite(unsigned char *cur_sha1, const unsigned char *new_sha1);
+int combine_notes_ignore(unsigned char *cur_sha1, const unsigned char *new_sha1);
+
+/*
  * Notes tree object
  *
  * Encapsulates the internal notes tree structure associated with a notes ref.
@@ -13,6 +37,7 @@
 struct notes_tree {
 	struct int_node *root;
 	char *ref;
+	combine_notes_fn *combine_notes;
 	int initialized;
 };
 
@@ -36,14 +61,19 @@ struct notes_tree {
  *
  * If you pass t == NULL, the default internal notes_tree will be initialized.
  *
+ * The combine_notes function that is passed becomes the default combine_notes
+ * function for the given notes_tree. If NULL is passed, the default
+ * combine_notes function is combine_notes_concatenate().
+ *
  * Precondition: The notes_tree structure is zeroed (this can be achieved with
  * memset(t, 0, sizeof(struct notes_tree)))
  */
-void init_notes(struct notes_tree *t, const char *notes_ref, int flags);
+void init_notes(struct notes_tree *t, const char *notes_ref,
+		combine_notes_fn combine_notes, int flags);
 
 /* Add the given note object to the given notes_tree structure */
 void add_note(struct notes_tree *t, const unsigned char *object_sha1,
-		const unsigned char *note_sha1);
+		const unsigned char *note_sha1, combine_notes_fn combine_notes);
 
 /* Get the note object SHA1 containing the note data for the given object */
 const unsigned char *get_note(struct notes_tree *t,
-- 
1.6.4.304.g1365c.dirty

[RFC/PATCHv7 22/22] fast-import: Proper notes tree manipulation using the notes API

[Johan Herland]

This patch teaches 'git fast-import' to use the notes API to organize
the manipulation of note objects through a fast-import stream. Note
objects are added to the notes tree through the 'N' command, and when
we're about to store the tree object for the current commit, we walk
through the notes tree and insert all the notes into the stored tree.

Signed-off-by: Johan Herland <johan@herland.net>
---
 fast-import.c          |   98 ++++++++++++++++++++++++++++--
 t/t9300-fast-import.sh |  156 ++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 235 insertions(+), 19 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index fcdcfaa..5837875 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -156,6 +156,7 @@ Format of STDIN stream:
 #include "csum-file.h"
 #include "quote.h"
 #include "exec_cmd.h"
+#include "notes.h"
 
 #define PACK_ID_BITS 16
 #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@ -246,6 +247,7 @@ struct branch
 	struct tree_entry branch_tree;
 	uintmax_t last_commit;
 	unsigned active : 1;
+	unsigned has_notes : 1;
 	unsigned pack_id : PACK_ID_BITS;
 	unsigned char sha1[20];
 };
@@ -277,6 +279,11 @@ struct recent_command
 	char *buf;
 };
 
+struct notes_tree_list {
+	struct notes_tree tree;
+	struct notes_tree_list *next;
+};
+
 /* Configured limits on output */
 static unsigned long max_depth = 10;
 static off_t max_packsize = (1LL << 32) - 1;
@@ -345,6 +352,9 @@ static struct branch *active_branches;
 static struct tag *first_tag;
 static struct tag *last_tag;
 
+/* Notes data */
+static struct notes_tree_list *notes_trees;
+
 /* Input stream parsing */
 static whenspec_type whenspec = WHENSPEC_RAW;
 static struct strbuf command_buf = STRBUF_INIT;
@@ -2060,7 +2070,7 @@ static void file_change_cr(struct branch *b, int rename)
 		leaf.tree);
 }
 
-static void note_change_n(struct branch *b)
+static void note_change_n(struct branch *b, struct notes_tree *notes)
 {
 	const char *p = command_buf.buf + 2;
 	static struct strbuf uq = STRBUF_INIT;
@@ -2130,8 +2140,8 @@ static void note_change_n(struct branch *b)
 			    typename(type), command_buf.buf);
 	}
 
-	tree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,
-		S_IFREG | 0644, NULL);
+	assert(notes);
+	add_note(notes, commit_sha1, sha1, NULL);
 }
 
 static void file_change_deleteall(struct branch *b)
@@ -2254,6 +2264,68 @@ static struct hash_list *parse_merge(unsigned int *count)
 	return list;
 }
 
+static struct notes_tree *new_notes_tree(struct branch *b)
+{
+	struct notes_tree_list *ret = (struct notes_tree_list *)
+		xcalloc(sizeof(struct notes_tree_list), 1);
+	init_notes(&ret->tree, b->name, combine_notes_overwrite, NOTES_INIT_EMPTY);
+	ret->next = notes_trees;
+	notes_trees = ret;
+	b->has_notes = 1;
+	return &ret->tree;
+}
+
+static struct notes_tree *get_notes_tree(struct branch *b)
+{
+	struct notes_tree_list *cur = notes_trees;
+	if (!b->has_notes)
+		return NULL;
+	while (cur && strcmp(cur->tree.ref, b->name))
+		cur = cur->next;
+	assert(cur);
+	return &cur->tree;
+}
+
+static void delete_notes_tree(struct branch *b, struct notes_tree **tree)
+{
+	struct notes_tree_list *cur = notes_trees, *prev = NULL;
+	while (cur && strcmp(cur->tree.ref, b->name)) {
+		prev = cur;
+		cur = cur->next;
+	}
+	assert(cur && &cur->tree == *tree);
+	if (prev)
+		prev->next = cur->next;
+	else
+		notes_trees = cur->next;
+	free_notes(&cur->tree);
+	free(cur);
+	*tree = NULL;
+	b->has_notes = 0;
+}
+
+static int write_notes_set_helper(
+	const unsigned char *object_sha1,
+	const unsigned char *note_sha1,
+	const char *note_tree_path,
+	void *cb_data)
+{
+	struct tree_entry *t = (struct tree_entry *) cb_data;
+	tree_content_set(t, note_tree_path, note_sha1, S_IFREG | 0644, NULL);
+	return 0;
+}
+
+static int write_notes_remove_helper(
+	const unsigned char *object_sha1,
+	const unsigned char *note_sha1,
+	const char *note_tree_path,
+	void *cb_data)
+{
+	struct tree_entry *t = (struct tree_entry *) cb_data;
+	tree_content_remove(t, note_tree_path, NULL);
+	return 0;
+}
+
 static void parse_new_commit(void)
 {
 	static struct strbuf msg = STRBUF_INIT;
@@ -2263,6 +2335,7 @@ static void parse_new_commit(void)
 	char *committer = NULL;
 	struct hash_list *merge_list = NULL;
 	unsigned int merge_count;
+	struct notes_tree *notes;
 
 	/* Obtain the branch name from the rest of our command */
 	sp = strchr(command_buf.buf, ' ') + 1;
@@ -2293,6 +2366,11 @@ static void parse_new_commit(void)
 		load_branch(b);
 	}
 
+	/* Retrieve notes tree, if needed */
+	notes = get_notes_tree(b);
+	if (notes)
+		for_each_note(notes, write_notes_remove_helper, &b->branch_tree);
+
 	/* file_change* */
 	while (command_buf.len > 0) {
 		if (!prefixcmp(command_buf.buf, "M "))
@@ -2303,10 +2381,16 @@ static void parse_new_commit(void)
 			file_change_cr(b, 1);
 		else if (!prefixcmp(command_buf.buf, "C "))
 			file_change_cr(b, 0);
-		else if (!prefixcmp(command_buf.buf, "N "))
-			note_change_n(b);
-		else if (!strcmp("deleteall", command_buf.buf))
+		else if (!prefixcmp(command_buf.buf, "N ")) {
+			if (!notes)
+				notes = new_notes_tree(b);
+			note_change_n(b, notes);
+		}
+		else if (!strcmp("deleteall", command_buf.buf)) {
+			if (notes)
+				delete_notes_tree(b, &notes);
 			file_change_deleteall(b);
+		}
 		else {
 			unread_command_buf = 1;
 			break;
@@ -2316,6 +2400,8 @@ static void parse_new_commit(void)
 	}
 
 	/* build the tree and the commit */
+	if (notes)
+		for_each_note(notes, write_notes_set_helper, &b->branch_tree);
 	store_tree(&b->branch_tree);
 	hashcpy(b->branch_tree.versions[0].sha1,
 		b->branch_tree.versions[1].sha1);
diff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh
index 2f5c323..50a2b8a 100755
--- a/t/t9300-fast-import.sh
+++ b/t/t9300-fast-import.sh
@@ -1092,9 +1092,12 @@ test_expect_success 'P: fail on blob mark in gitlink' '
 ### series Q (notes)
 ###
 
-note1_data="Note for the first commit"
-note2_data="Note for the second commit"
-note3_data="Note for the third commit"
+note1_data="The first note for the first commit"
+note2_data="The first note for the second commit"
+note3_data="The first note for the third commit"
+note1b_data="The second note for the first commit"
+note1c_data="The third note for the first commit"
+note2b_data="The second note for the second commit"
 
 test_tick
 cat >input <<INPUT_END
@@ -1169,7 +1172,45 @@ data <<EOF
 $note3_data
 EOF
 
+commit refs/notes/foobar
+mark :10
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:10)
+COMMIT
+
+N inline :3
+data <<EOF
+$note1b_data
+EOF
+
+commit refs/notes/foobar2
+mark :11
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:11)
+COMMIT
+
+N inline :3
+data <<EOF
+$note1c_data
+EOF
+
+commit refs/notes/foobar
+mark :12
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:12)
+COMMIT
+
+deleteall
+N inline :5
+data <<EOF
+$note2b_data
+EOF
+
 INPUT_END
+
 test_expect_success \
 	'Q: commit notes' \
 	'git fast-import <input &&
@@ -1224,8 +1265,8 @@ committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
 notes (:9)
 EOF
 test_expect_success \
-	'Q: verify notes commit' \
-	'git cat-file commit refs/notes/foobar | sed 1d >actual &&
+	'Q: verify first notes commit' \
+	'git cat-file commit refs/notes/foobar~2 | sed 1d >actual &&
 	test_cmp expect actual'
 
 cat >expect.unsorted <<EOF
@@ -1235,24 +1276,113 @@ cat >expect.unsorted <<EOF
 EOF
 cat expect.unsorted | sort >expect
 test_expect_success \
-	'Q: verify notes tree' \
-	'git cat-file -p refs/notes/foobar^{tree} | sed "s/ [0-9a-f]*	/ /" >actual &&
+	'Q: verify first notes tree' \
+	'git cat-file -p refs/notes/foobar~2^{tree} | sed "s/ [0-9a-f]*	/ /" >actual &&
 	 test_cmp expect actual'
 
 echo "$note1_data" >expect
 test_expect_success \
-	'Q: verify note for first commit' \
-	'git cat-file blob refs/notes/foobar:$commit1 >actual && test_cmp expect actual'
+	'Q: verify first note for first commit' \
+	'git cat-file blob refs/notes/foobar~2:$commit1 >actual && test_cmp expect actual'
 
 echo "$note2_data" >expect
 test_expect_success \
-	'Q: verify note for second commit' \
-	'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'
+	'Q: verify first note for second commit' \
+	'git cat-file blob refs/notes/foobar~2:$commit2 >actual && test_cmp expect actual'
+
+echo "$note3_data" >expect
+test_expect_success \
+	'Q: verify first note for third commit' \
+	'git cat-file blob refs/notes/foobar~2:$commit3 >actual && test_cmp expect actual'
+
+cat >expect <<EOF
+parent `git rev-parse --verify refs/notes/foobar~2`
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:10)
+EOF
+test_expect_success \
+	'Q: verify second notes commit' \
+	'git cat-file commit refs/notes/foobar^ | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit1
+100644 blob $commit2
+100644 blob $commit3
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+	'Q: verify second notes tree' \
+	'git cat-file -p refs/notes/foobar^^{tree} | sed "s/ [0-9a-f]*	/ /" >actual &&
+	 test_cmp expect actual'
+
+echo "$note1b_data" >expect
+test_expect_success \
+	'Q: verify second note for first commit' \
+	'git cat-file blob refs/notes/foobar^:$commit1 >actual && test_cmp expect actual'
+
+echo "$note2_data" >expect
+test_expect_success \
+	'Q: verify first note for second commit' \
+	'git cat-file blob refs/notes/foobar^:$commit2 >actual && test_cmp expect actual'
 
 echo "$note3_data" >expect
 test_expect_success \
-	'Q: verify note for third commit' \
-	'git cat-file blob refs/notes/foobar:$commit3 >actual && test_cmp expect actual'
+	'Q: verify first note for third commit' \
+	'git cat-file blob refs/notes/foobar^:$commit3 >actual && test_cmp expect actual'
+
+cat >expect <<EOF
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:11)
+EOF
+test_expect_success \
+	'Q: verify third notes commit' \
+	'git cat-file commit refs/notes/foobar2 | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit1
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+	'Q: verify third notes tree' \
+	'git cat-file -p refs/notes/foobar2^{tree} | sed "s/ [0-9a-f]*	/ /" >actual &&
+	 test_cmp expect actual'
+
+echo "$note1c_data" >expect
+test_expect_success \
+	'Q: verify third note for first commit' \
+	'git cat-file blob refs/notes/foobar2:$commit1 >actual && test_cmp expect actual'
+
+cat >expect <<EOF
+parent `git rev-parse --verify refs/notes/foobar^`
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:12)
+EOF
+test_expect_success \
+	'Q: verify fourth notes commit' \
+	'git cat-file commit refs/notes/foobar | sed 1d >actual &&
+	test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit2
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+	'Q: verify fourth notes tree' \
+	'git cat-file -p refs/notes/foobar^{tree} | sed "s/ [0-9a-f]*	/ /" >actual &&
+	 test_cmp expect actual'
+
+echo "$note2b_data" >expect
+test_expect_success \
+	'Q: verify second note for second commit' \
+	'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'
 
 ###
 ### series R (feature and option)
-- 
1.6.4.304.g1365c.dirty

Re: [RFC/PATCHv7 00/22] git notes

[Johan Herland]

On Friday 09 October 2009, Johan Herland wrote:
> Hi,
> 
> Here is the 7th iteration of the git-notes series. Changes in this
> iteration are as follows:

Oops... Diregard this one. Seems I had a stray 0000-*.patch.bak lying 
around...


...Johan

Re: [RFC/PATCHv7 22/22] fast-import: Proper notes tree manipulation using the notes API

[Shawn O. Pearce]

Johan Herland <johan@herland.net> wrote:
> This patch teaches 'git fast-import' to use the notes API to organize
> the manipulation of note objects through a fast-import stream. Note
> objects are added to the notes tree through the 'N' command, and when
> we're about to store the tree object for the current commit, we walk
> through the notes tree and insert all the notes into the stored tree.

Some high level comments about this patch:

- You don't destroy the struct notes_tree during unload_one_branch()
  which means notes trees stay in memory even if the branch table
  is overflowing.  I think you should discard the notes tree when
  a branch unloads, and recreate it when the branch loads.

- Destroying and adding back all notes is OK with ~20k notes, but
  doing that with ~150k-~800k notes is going to slow down a lot,
  losing the "fast" part.

-- 
Shawn.

Re: [RFC/PATCHv7 22/22] fast-import: Proper notes tree manipulation using the notes API

[Johan Herland]

On Friday 09 October 2009, Shawn O. Pearce wrote:
> Johan Herland <johan@herland.net> wrote:
> > This patch teaches 'git fast-import' to use the notes API to organize
> > the manipulation of note objects through a fast-import stream. Note
> > objects are added to the notes tree through the 'N' command, and when
> > we're about to store the tree object for the current commit, we walk
> > through the notes tree and insert all the notes into the stored tree.
> 
> Some high level comments about this patch:
> 
> - You don't destroy the struct notes_tree during unload_one_branch()
>   which means notes trees stay in memory even if the branch table
>   is overflowing.  I think you should discard the notes tree when
>   a branch unloads, and recreate it when the branch loads.
> 
> - Destroying and adding back all notes is OK with ~20k notes, but
>   doing that with ~150k-~800k notes is going to slow down a lot,
>   losing the "fast" part.

Thanks for the comments. I've tried to address them in the 8th iteration of 
this series (Patch 8/10 to be more precise), just submitted to the mailing 
list.


...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net

[RFC] fast-import: notemodify (N) command

[Jonathan Nieder]

Dear fast importers,

Another week, another fast-import protocol extension.

Most DVCSes do not allow one to non-disruptively change the log
message for a commit.  But sometimes people want to attach information to a
commit after the fact:

 - whether it was tested and worked correctly
 - who liked or disliked the commit (Acked-by, Reviewed-by)
 - corresponding revision number after export to another version
   control system
 - bug number
 - corresponding compiled binary

The N command allows such notes to be attached to commits, like so:

 1. first the commit is imported as usual (let's say it's ":1").
 2. commit annotations are added separately, like so:

	commit refs/notes/commits
	committer A. U. Thor <author@example.com> Mon, 31 Jan 2011 12:15:59 -0600
	data <<END
	Notes after review.
	END

	N inline :1
	data <<END
	Acked-by: me
	END

Details:

 - there can be multiple categories of notes: "refs/notes/commits"
   contains ordinary addenda to the commit message, but one might also
   see refs/notes/bugzilla, refs/notes/svn-commit, and so on.

 - each commit gets at most one blob of notes in each category.  Later
   notemodify (N) commands overwrite the effect from earlier ones.

 - the syntax of a notemodify command is as follows:

	'N' sp <dataref> sp <committish> lf

   The <dataref> represents a blob with the annotations to be used
   ("inline" is allowed, too, just like with filemodify).  The
   <committish> can be any expression allowed in a 'from' command
   (branch name, mark reference :<idnum>, other commit name) and
   represents the commit that is to be annotated.

 - this has been supported in git since v1.6.6.  There is no
   "feature" for it --- I don't think the feature declaration
   facility existed yet.

Do other DVCSes support something like this?  Should it get a
feature name?

Jonathan

Re: [Vcs-fast-import-devs] [RFC] fast-import: notemodify (N) command

[Sverre Rabbelier]

Heya,

On Mon, Jan 31, 2011 at 19:33, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Most DVCSes do not allow one to non-disruptively change the log
> message for a commit.  But sometimes people want to attach information to a
> commit after the fact:
>
>  - whether it was tested and worked correctly
>  - who liked or disliked the commit (Acked-by, Reviewed-by)
>  - corresponding revision number after export to another version
>   control system
>  - bug number
>  - corresponding compiled binary

I talked with Augie Fackler (from hg) about this on IM and he says:
> We don't support anything like that at present (no demand, when we check
> nobody really seems to use git notes for anything)
> so it doesn't seem relevant in fast-export

So at least HG doesn't (currently) have any functionality that they
could use to implement the importing of such a stream.

-- 
Cheers,

Sverre Rabbelier

Re: [RFC] fast-import: notemodify (N) command

[Jonathan Nieder]

Sverre Rabbelier wrote:
> I talked with Augie Fackler (from hg) about this on IM and he says:

>> We don't support anything like that at present (no demand, when we check
>> nobody really seems to use git notes for anything)
>> so it doesn't seem relevant in fast-export
>
> So at least HG doesn't (currently) have any functionality that they
> could use to implement the importing of such a stream.

Thanks, good to know.  I suppose this definitely needs a feature name,
then (I'll send a patch to make it "feature notes").

Jonathan

[Aside: I suspect part of the reason "git notes" adoption is not so
great is the lack of git notes fetch/git notes push.  Sample size
of 1: I use notes heavily as a consumer, to dig up mailing list
threads[1], but have put off sharing my own annotations until I can
figure out how to make it convenient for others to use.]

[1] http://thread.gmane.org/gmane.comp.version-control.git/109074/focus=109542

Re: [RFC] fast-import: notemodify (N) command

[Sverre Rabbelier]

Heya,

On Mon, Jan 31, 2011 at 20:01, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Thanks, good to know.  I suppose this definitely needs a feature name,
> then (I'll send a patch to make it "feature notes").

SGTM.

> [Aside: I suspect part of the reason "git notes" adoption is not so
> great is the lack of git notes fetch/git notes push.  Sample size
> of 1: I use notes heavily as a consumer, to dig up mailing list
> threads[1], but have put off sharing my own annotations until I can
> figure out how to make it convenient for others to use.]

That's another thing Augie mentioned that he (and I guess the hg
community at large) dislikes, the fact that they're not propagated.

-- 
Cheers,

Sverre Rabbelier

Re: [RFC] fast-import: notemodify (N) command

[Sam Vilain]

On 01/02/11 10:19, Sverre Rabbelier wrote:
> That's another thing Augie mentioned that he (and I guess the hg
> community at large) dislikes, the fact that they're not propagated.

This is not a "fact".

If you add configuration in your git config to fetch and push the refs,
then they are propagated.

Just because you disagree with the current interface or defaults doesn't
mean the design is wrong.  I hear the same arguments against submodules,
which is a shame because the message isn't getting through to people
that the porcelain can and should be extended to make people's lives
easier.  It's just that instead of second-guessing what shape they
should take, the design and plumbing are written so that people can
write scripts to make it work.

It's a slower path, but you end up with a better tool at the end of it.

Sam

Re: [RFC] fast-import: notemodify (N) command

[Sverre Rabbelier]

Heya,

On Mon, Jan 31, 2011 at 23:37, Sam Vilain <sam@vilain.net> wrote:
> This is not a "fact".
>
> If you add configuration in your git config to fetch and push the refs,
> then they are propagated.

Heh, I was contemplating whether to add "(by default)" or not, I guess
I should have.

-- 
Cheers,

Sverre Rabbelier