From c2bbe9eb6c46b2f1723ce6c5e26816dd82e42c6f Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Wed, 9 Jul 2014 17:15:38 -0400 Subject: [PATCH] test: Test thread linking in all possible delivery orders These tests deliver all possible (single-root) four-message threads in all possible orders and check that notmuch successfully links them into threads. These tests supersede and replace the previous and much less thorough "T260-thread-order" tests. 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. --- test/T260-thread-order.sh | 86 +++++++++++++++++++++++++++++---------- test/gen-threads.py | 33 +++++++++++++++ 2 files changed, 98 insertions(+), 21 deletions(-) create mode 100644 test/gen-threads.py diff --git a/test/T260-thread-order.sh b/test/T260-thread-order.sh index 6c3a4b3f..b435d79f 100755 --- a/test/T260-thread-order.sh +++ b/test/T260-thread-order.sh @@ -2,31 +2,75 @@ test_description="threading when messages received out of order" . ./test-lib.sh -test_begin_subtest "Adding initial child message" -generate_message [body]=foo "[in-reply-to]=\" [subject]=brokenthreadtest '[date]="Sat, 01 Jan 2000 12:00:00 -0000"' -output=$(NOTMUCH_NEW) -test_expect_equal "$output" "Added 1 new message to the database." +# Generate all single-root four message thread structures. We'll use +# this for multiple tests below. +THREADS=$(python ${TEST_DIRECTORY}/gen-threads.py 4) +nthreads=$(wc -l <<< "$THREADS") -test_begin_subtest "Searching returns the message" -output=$(notmuch search foo | notmuch_search_sanitize) -test_expect_equal "$output" "thread:XXX 2000-01-01 [1/1] Notmuch Test Suite; brokenthreadtest (inbox unread)" +test_begin_subtest "Messages with one parent get linked in all delivery orders" +# 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]="\" \ + [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 "Adding second child message" -generate_message [body]=foo "[in-reply-to]=\" [subject]=brokenthreadtest '[date]="Sat, 01 Jan 2000 12:00:00 -0000"' -output=$(NOTMUCH_NEW) -test_expect_equal "$output" "Added 1 new message to the database." +test_begin_subtest "Messages with all parents get linked in all delivery orders" +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 > /dev/null +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=" $references" + parent=${parents[$parent]} + done -test_begin_subtest "Searching returns both messages in one thread" -output=$(notmuch search foo | notmuch_search_sanitize) -test_expect_equal "$output" "thread:XXX 2000-01-01 [2/2] Notmuch Test Suite; brokenthreadtest (inbox unread)" + generate_message \ + [id]=m$n@t$thread [references]="'$references'" \ + [subject]=p$thread [from]=m$n + thread=$((thread + 1)) + done <<< "$THREADS" + notmuch new > /dev/null -test_begin_subtest "Adding parent message" -generate_message [body]=foo [id]=parent-id [subject]=brokenthreadtest '[date]="Sat, 01 Jan 2000 12:00:00 -0000"' -output=$(NOTMUCH_NEW) -test_expect_equal "$output" "Added 1 new message to the database." + output="$output +$(notmuch search --sort=newest-first '*' | notmuch_search_sanitize)" -test_begin_subtest "Searching returns all three messages in one thread" -output=$(notmuch search foo | notmuch_search_sanitize) -test_expect_equal "$output" "thread:XXX 2000-01-01 [3/3] Notmuch Test Suite; brokenthreadtest (inbox unread)" + # 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 diff --git a/test/gen-threads.py b/test/gen-threads.py new file mode 100644 index 00000000..9fbb8474 --- /dev/null +++ b/test/gen-threads.py @@ -0,0 +1,33 @@ +# Generate all possible single-root message thread structures of size +# argv[1]. Each output line is a thread structure, where the n'th +# field is either a number giving the parent of message n or "None" +# for the root. + +import sys +from itertools import chain, combinations + +def subsets(s): + return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) + +nodes = set(range(int(sys.argv[1]))) + +# Queue of (tree, free, to_expand) where tree is a {node: parent} +# dictionary, free is a set of unattached nodes, and to_expand is +# itself a queue of nodes in the tree that need to be expanded. +# The queue starts with all single-node trees. +queue = [({root: None}, nodes - {root}, (root,)) for root in nodes] + +# Process queue +while queue: + tree, free, to_expand = queue.pop() + + if len(to_expand) == 0: + # Only print full-sized trees + if len(free) == 0: + print(" ".join(map(str, [msg[1] for msg in sorted(tree.items())]))) + else: + # Expand node to_expand[0] with each possible set of children + for children in subsets(free): + ntree = dict(tree, **{child: to_expand[0] for child in children}) + nfree = free.difference(children) + queue.append((ntree, nfree, to_expand[1:] + tuple(children))) -- 2.43.0