[PATCH v2] test: Test thread linking in all possible delivery orders

[Austin Clements <amdragon@MIT.EDU>]

These tests deliver all possible (single-root) four-message threads in
all possible orders and check that notmuch successfully links them
into threads.

There are two variants of the test: one delivers messages that
reference only their immediate parent and the other delivers messages
that reference all of their parents.  The latter test is currently
known-broken.

This is introduced as a new test (rather than just adding it to
T050-new) because it's much easier for this to start with an empty
database.
---

This version hopefully addresses David's comments in
id:87y4zhfmrn.fsf@maritornes.cs.unb.ca and adds a second test that
demonstrates the bug Mark in figured out in
id:8738h7kv2q.fsf@qmul.ac.uk.

test/T051-new-linking.sh | 91 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)
 create mode 100755 test/T051-new-linking.sh

diff --git a/test/T051-new-linking.sh b/test/T051-new-linking.sh
new file mode 100755
index 0000000..9ccbc52
--- /dev/null
+++ b/test/T051-new-linking.sh
@@ -0,0 +1,91 @@
+#!/usr/bin/env bash
+test_description='"notmuch new" thread linking'
+
+. ./test-lib.sh
+
+# Generate all possible single-root four message thread structures.
+# Each line in THREADS is a thread structure, where the n'th field is
+# the parent of message n.  We'll use this for multiple tests below.
+THREADS=$(python -c '
+def mkTrees(free, tree={}):
+    if free == set():
+        print(" ".join(map(str, [msg[1] for msg in sorted(tree.items())])))
+        return
+    # Attach each free message to each message in the tree (if there is
+    # no tree, make the free message the root), backtracking after each
+    for msg in sorted(free):
+        parents = sorted(tree.keys()) if tree else ["none"]
+        for parent in parents:
+            ntree = tree.copy()
+            ntree[msg] = parent
+            mkTrees(free - set([msg]), ntree)
+mkTrees(set(range(4)))')
+nthreads=$(wc -l <<< "$THREADS")
+
+test_begin_subtest "All four-message threads get linked in all delivery orders (one parent)"
+# In the first variant, this delivers messages that reference only
+# their immediate parent.  Hence, we should only expect threads to be
+# fully joined at the end.
+for ((n = 0; n < 4; n++)); do
+    # Deliver the n'th message of every thread
+    thread=0
+    while read -a parents; do
+        parent=${parents[$n]}
+        generate_message \
+            [id]=m$n@t$thread [in-reply-to]="\<m$parent@t$thread\>" \
+            [subject]=p$thread [from]=m$n
+        thread=$((thread + 1))
+    done <<< "$THREADS"
+    notmuch new > /dev/null
+done
+output=$(notmuch search --sort=newest-first '*' | notmuch_search_sanitize)
+expected=$(for ((i = 0; i < $nthreads; i++)); do
+        echo "thread:XXX   2001-01-05 [4/4] m3, m2, m1, m0; p$i (inbox unread)"
+    done)
+test_expect_equal "$output" "$expected"
+
+test_begin_subtest "The same (full parent linkage)"
+test_subtest_known_broken
+# Here we do the same thing as the previous test, but each message
+# references all of its parents.  Since every message references the
+# root of the thread, each thread should always be fully joined.  This
+# is currently broken because of the bug detailed in
+# id:8738h7kv2q.fsf@qmul.ac.uk.
+rm ${MAIL_DIR}/*
+notmuch new
+output=""
+expected=""
+for ((n = 0; n < 4; n++)); do
+    # Deliver the n'th message of every thread
+    thread=0
+    while read -a parents; do
+        references=""
+        parent=${parents[$n]}
+        while [[ $parent != none ]]; do
+            references="<m$parent@t$thread> $references"
+            parent=${parents[$parent]}
+        done
+
+        generate_message \
+            [id]=m$n@t$thread [references]="'$references'" \
+            [subject]=p$thread [from]=m$n
+        thread=$((thread + 1))
+    done <<< "$THREADS"
+    notmuch new > /dev/null
+
+    output="$output
+$(notmuch search --sort=newest-first '*' | notmuch_search_sanitize)"
+
+    # Construct expected output
+    template="thread:XXX   2001-01-05 [$((n+1))/$((n+1))]"
+    for ((m = n; m > 0; m--)); do
+        template="$template m$m,"
+    done
+    expected="$expected
+$(for ((i = 0; i < $nthreads; i++)); do
+        echo "$template m0; p$i (inbox unread)"
+    done)"
+done
+test_expect_equal "$output" "$expected"
+
+test_done
-- 
1.9.1