Additionally, defined the NoteMap.getNote method which returns a Note
instance.  These changes were necessary to enable implementation of
the NoteMerger interface (the merge method needs to instantiate a
Note) and to enable direct use of NoteMerger which expects instances
of Note class as its paramters.  Implementing creation of code review
summary notes in Gerrit [1] will make use of both of these features.

[1] https://review.source.android.com/#change,20045

Change-Id: I627aefcedcd3434deecd63fa1d3e90e303b385ac
Signed-off-by: Sasa Zivkov <sasa.zivkov@sap.com>
Signed-off-by: Chris Aniszczyk <caniszczyk@gmail.com>

Merging Git notes branches has several differences from merging "normal"
branches. Although Git notes are initially stored as one flat tree the
tree may fanout when the number of notes becomes too large for efficient
access. In this case the first two hex digits of the note name will be
used as a subdirectory name and the rest 38 hex digits as the file name
under that directory. Similarly, when number of notes decreases a fanout
tree may collapse back into a flat tree. The Git notes merge algorithm
must take into account possibly different tree structures in different
note branches and must properly match them against each other.

Any conflict on a Git note is, by default, resolved by concatenating
the two conflicting versions of the note. A delete-edit conflict is, by
default, resolved by keeping the edit version.

The note merge logic is pluggable and the caller may provide custom
note merger that will perform different merging strategy.

Additionally, it is possible to have non-note entries inside a notes
tree. The merge algorithm must also take this fact into account and
will try to merge such non-note entries. However, in case of any merge
conflicts the merge operation will fail. Git notes merge algorithm is
currently not trying to do content merge of non-note entries.

Thanks to Shawn Pearce for patiently answering my questions related to
this topic, giving hints and providing code snippets.

Change-Id: I3b2335c76c766fd7ea25752e54087f9b19d69c88
Signed-off-by: Sasa Zivkov <sasa.zivkov@sap.com>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

We will need to iterate over all notes of a NoteMap, at least this will be
needed for testing purposes. This change also implied making the Note class
public.

Change-Id: I9b0639f9843f457ee9de43504b2499a673cd0e77
Signed-off-by: Sasa Zivkov <sasa.zivkov@sap.com>

Sasa pointed out we only ever use the length here, so instead of
holding onto the AbbreviatedObjectId, lets just hold onto the length
as a primitive int.

Change-Id: I2444f59f9fe5ddcaea4a3537d3f1064736ae3215
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
CC: Sasa Zivkov <zivkov@gmail.com>

This makes usage of a TreeFormatter more similar to a CommitBuilder or
a TagBuilder: populate the formatter and pass to the ObjectInserter.

Change-Id: I5a45ef3a35cc73f4905a34bc6f6228510df8eb2c
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
Reviewed-by: Chris Aniszczyk <caniszczyk@gmail.com>

Fanout level notes trees are combined back together into a flat leaf
level tree if during a removal of a subtree there are less than 3/4 of
the fanout subtrees still existing, and the size of the combined leaf
is under the 256 split limit noted above.

This rule is used because deletes are less common than insertions, and
SHA-1's relatively uniform distribution suggests that with only 192
subtrees existing in the fanout, there should be approximately 192
names in the combined replacement leaf tree.

Change-Id: Ia9d145ffd5454982509fc40906bc4dbbf2b13952
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

Leaf level notes trees are split into a new fan-out tree if an
insertion occurs and the tree already contains >= 256 notes in it.

The splitting may occur multiple times if all of the notes have the
same prefix; in the worst case this produces a tree path such as
"00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/be" if all
of the notes begin with zeros.

Change-Id: I2d7d98f35108def9ec49936ddbdc34b13822a3c7
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

Some algorithms need to be able to iterate through all notes within a
particular bucket, such as when splitting or combining a bucket.
Exposing an Iterator<Note> makes this traversal possible.

For a LeafBucket the iteration is simple, its over the sorted array of
elements.  For FanoutBucket its a bit more complex as the iteration
needs to union the iterators of each fanout bucket, lazily loading any
buckets that aren't already in-memory.

Change-Id: I3d5279b11984f44dcf0ddb14a82a4b4e51d4632d
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

This is necessary to allow applications to wrap the note tree in
a commit and update the note branch with the new state.

Change-Id: Idbd7ead4a1b16ae2b64a30a4a01a29cfed548cdf
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

NoteMap now supports editing in-memory, allowing applications to
modify the NoteMap once it has been loaded from the branch.  The
ability to write the branch back to tree objects is not yet done,
so the edits are strictly transient.

Change-Id: I63448954abfca2a8e3e95369cd84c0d1176cdb79
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

In order to safely edit a notes tree, NoteMap needs to retain any
non-note tree entries it read from the source tree and put them
back out into the modified tree when it commits a new version of
the note branch.

Remember any tree entries that didn't look like a note during
the parsing of the tree, so they can be put into a TreeFormatter
later when the tree writes to the repository.

Change-Id: Ia284af7e7866da35db35374c6c5869f00c857944
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

Instead of reading a note tree recursively up front when the NoteMap
is loaded, read only the root tree and load subtrees on demand when
they are accessed by the application.  This gives a lower latency
to read a note for the recent commits on a branch, as only the paths
that are needed get read.

Given a 2/38 style fanout, the tree will fully load when 256 objects
have been accessed by the application.  But unlike the prior version
of NoteMap, the NoteMap will load faster and answer lookups sooner,
as the loading time for all 256 levels is spread out across each of
the get() requests.

Given a 2/2/36 style fanout, the tree won't need to fully load until
about 65,536 objects are accessed.

To simplify the implementation we only support the flat layout (all
notes in the top level tree), or a 2/38, 2/2/36, 2/2/2/34, through
2/.../2 style fanout.  Unlike C Git we don't support reading the old
experimental 4/36 fanout.  This is sufficient because C Git won't
create the 4/36 style fanout when creating or updating a notes tree,
and there really aren't any in the wild today.

Change-Id: I6099b35916a8404762f31e9c11f632e43e0c1bfd
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

The NoteMap makes it easy to read a small notes tree as created by
the `git notes` command in C Git.  To make the initial implementation
simple a notes tree is read recursively into a map in memory.
This is reasonable if the application will need to access all notes,
or if there are less than 256 notes in the tree, but doesn't behave
well when the number of notes exceeds 256 and the application
doesn't need to access all of them.

We can later add support for lazily loading different subpaths,
thus fixing the large note tree problem described above.

Currently the implementation only supports reading.  Writing notes
is more complex because trees need to be expanded or collapsed at
the exact 256 entry cut-off in order to retain the same tree SHA-1
that C Git would use for the same content.  It also needs to retain
non-note tree entries such as ".gitignore" or ".gitattribute" files
that might randomly appear within a notes tree.  We can also add
writing support later.

Change-Id: I93704bd84ebf650d51de34da3f1577ef0f7a9144
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
Signed-off-by: Chris Aniszczyk <caniszczyk@gmail.com>