Merge branch 'jh/notes-fanout-fix'

The code to automatically shrink the fan-out in the notes tree had
an off-by-one bug, which has been killed.

* jh/notes-fanout-fix:
  notes.c: fix off-by-one error when decreasing notes fanout
  t3305: check notes fanout more carefully and robustly

diff --git a/notes.c b/notes.c
index a0349fa77831bcb79525e3f3a06132297857df87..d626ca596100a2c895cab793fe088b681b1f67f6 100644 (file)
--- a/notes.c
+++ b/notes.c
@@ -576,16 +576,16 @@ redo:
                         * the note tree that have not yet been explored. There
                         * is a direct relationship between subtree entries at
                         * level 'n' in the tree, and the 'fanout' variable:
-                        * Subtree entries at level 'n <= 2 * fanout' should be
+                        * Subtree entries at level 'n < 2 * fanout' should be
                         * preserved, since they correspond exactly to a fanout
                         * directory in the on-disk structure. However, subtree
-                        * entries at level 'n > 2 * fanout' should NOT be
+                        * entries at level 'n >= 2 * fanout' should NOT be
                         * preserved, but rather consolidated into the above
                         * notes tree level. We achieve this by unconditionally
                         * unpacking subtree entries that exist below the
                         * threshold level at 'n = 2 * fanout'.
                         */
-                       if (n <= 2 * fanout &&
+                       if (n < 2 * fanout &&
                            flags & FOR_EACH_NOTE_YIELD_SUBTREES) {
                                /* invoke callback with subtree */
                                unsigned int path_len =
@@ -602,7 +602,7 @@ redo:
                                         path,
                                         cb_data);
                        }
-                       if (n > fanout * 2 ||
+                       if (n >= 2 * fanout ||
                            !(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) {
                                /* unpack subtree and resume traversal */
                                tree->a[i] = NULL;
@@ -723,13 +723,15 @@ static int write_each_note_helper(struct tree_write_stack *tws,
 
 struct write_each_note_data {
        struct tree_write_stack *root;
-       struct non_note *next_non_note;
+       struct non_note **nn_list;
+       struct non_note *nn_prev;
 };
 
 static int write_each_non_note_until(const char *note_path,
                struct write_each_note_data *d)
 {
-       struct non_note *n = d->next_non_note;
+       struct non_note *p = d->nn_prev;
+       struct non_note *n = p ? p->next : *d->nn_list;
        int cmp = 0, ret;
        while (n && (!note_path || (cmp = strcmp(n->path, note_path)) <= 0)) {
                if (note_path && cmp == 0)
@@ -740,9 +742,10 @@ static int write_each_non_note_until(const char *note_path,
                        if (ret)
                                return ret;
                }
+               p = n;
                n = n->next;
        }
-       d->next_non_note = n;
+       d->nn_prev = p;
        return 0;
 }
 
@@ -1177,7 +1180,8 @@ int write_notes_tree(struct notes_tree *t, struct object_id *result)
        strbuf_init(&root.buf, 256 * (32 + the_hash_algo->hexsz)); /* assume 256 entries */
        root.path[0] = root.path[1] = '\0';
        cb_data.root = &root;
-       cb_data.next_non_note = t->first_non_note;
+       cb_data.nn_list = &(t->first_non_note);
+       cb_data.nn_prev = NULL;
 
        /* Write tree objects representing current notes tree */
        flags = FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |

diff --git a/t/t3305-notes-fanout.sh b/t/t3305-notes-fanout.sh
index 831f83d211b8c731558a717bb2b615e414b7022a..3b4753e1b479bdc9ecddb5a08565e056e9b10b14 100755 (executable)
--- a/t/t3305-notes-fanout.sh
+++ b/t/t3305-notes-fanout.sh
@@ -4,6 +4,38 @@ test_description='Test that adding/removing many notes triggers automatic fanout
 
 . ./test-lib.sh
 
+path_has_fanout() {
+       path=$1 &&
+       fanout=$2 &&
+       after_last_slash=$((40 - $fanout * 2)) &&
+       echo $path | grep -q "^\([0-9a-f]\{2\}/\)\{$fanout\}[0-9a-f]\{$after_last_slash\}$"
+}
+
+touched_one_note_with_fanout() {
+       notes_commit=$1 &&
+       modification=$2 &&  # 'A' for addition, 'D' for deletion
+       fanout=$3 &&
+       diff=$(git diff-tree --no-commit-id --name-status --root -r $notes_commit) &&
+       path=$(echo $diff | sed -e "s/^$modification[\t ]//") &&
+       path_has_fanout "$path" $fanout;
+}
+
+all_notes_have_fanout() {
+       notes_commit=$1 &&
+       fanout=$2 &&
+       git ls-tree -r --name-only $notes_commit 2>/dev/null |
+       while read path
+       do
+               path_has_fanout $path $fanout || return 1
+       done
+}
+
+test_expect_success 'tweak test environment' '
+       git checkout -b nondeterminism &&
+       test_commit A &&
+       git checkout --orphan with_notes;
+'
+
 test_expect_success 'creating many notes with git-notes' '
        num_notes=300 &&
        i=0 &&
@@ -20,7 +52,7 @@ test_expect_success 'creating many notes with git-notes' '
 
 test_expect_success 'many notes created correctly with git-notes' '
        git log | grep "^    " > output &&
-       i=300 &&
+       i=$num_notes &&
        while test $i -gt 0
        do
                echo "    commit #$i" &&
@@ -30,34 +62,46 @@ test_expect_success 'many notes created correctly with git-notes' '
        test_cmp expect output
 '
 
-test_expect_success 'many notes created with git-notes triggers fanout' '
-       # Expect entire notes tree to have a fanout == 1
-       git ls-tree -r --name-only refs/notes/commits |
-       while read path
+test_expect_success 'stable fanout 0 is followed by stable fanout 1' '
+       i=$num_notes &&
+       fanout=0 &&
+       while test $i -gt 0
        do
-               echo $path | grep "^../[0-9a-f]*$" || {
-                       echo "Invalid path \"$path\"" &&
-                       return 1;
-               }
-       done
+               i=$(($i - 1)) &&
+               if touched_one_note_with_fanout refs/notes/commits~$i A $fanout
+               then
+                       continue
+               elif test $fanout -eq 0
+               then
+                       fanout=1 &&
+                       if all_notes_have_fanout refs/notes/commits~$i $fanout
+                       then
+                               echo "Fanout 0 -> 1 at refs/notes/commits~$i" &&
+                               continue
+                       fi
+               fi &&
+               echo "Failed fanout=$fanout check at refs/notes/commits~$i" &&
+               git ls-tree -r --name-only refs/notes/commits~$i &&
+               return 1
+       done &&
+       all_notes_have_fanout refs/notes/commits 1
 '
 
 test_expect_success 'deleting most notes with git-notes' '
-       num_notes=250 &&
+       remove_notes=285 &&
        i=0 &&
        git rev-list HEAD |
-       while test $i -lt $num_notes && read sha1
+       while test $i -lt $remove_notes && read sha1
        do
                i=$(($i + 1)) &&
                test_tick &&
-               git notes remove "$sha1" ||
-               exit 1
+               git notes remove "$sha1" 2>/dev/null || return 1
        done
 '
 
 test_expect_success 'most notes deleted correctly with git-notes' '
-       git log HEAD~250 | grep "^    " > output &&
-       i=50 &&
+       git log HEAD~$remove_notes | grep "^    " > output &&
+       i=$(($num_notes - $remove_notes)) &&
        while test $i -gt 0
        do
                echo "    commit #$i" &&
@@ -67,16 +111,29 @@ test_expect_success 'most notes deleted correctly with git-notes' '
        test_cmp expect output
 '
 
-test_expect_success 'deleting most notes triggers fanout consolidation' '
-       # Expect entire notes tree to have a fanout == 0
-       git ls-tree -r --name-only refs/notes/commits |
-       while read path
+test_expect_success 'stable fanout 1 is followed by stable fanout 0' '
+       i=$remove_notes &&
+       fanout=1 &&
+       while test $i -gt 0
        do
-               echo $path | grep -v "^../.*" || {
-                       echo "Invalid path \"$path\"" &&
-                       return 1;
-               }
-       done
+               i=$(($i - 1)) &&
+               if touched_one_note_with_fanout refs/notes/commits~$i D $fanout
+               then
+                       continue
+               elif test $fanout -eq 1
+               then
+                       fanout=0 &&
+                       if all_notes_have_fanout refs/notes/commits~$i $fanout
+                       then
+                               echo "Fanout 1 -> 0 at refs/notes/commits~$i" &&
+                               continue
+                       fi
+               fi &&
+               echo "Failed fanout=$fanout check at refs/notes/commits~$i" &&
+               git ls-tree -r --name-only refs/notes/commits~$i &&
+               return 1
+       done &&
+       all_notes_have_fanout refs/notes/commits 0
 '
 
 test_done