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

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

[Austin Clements]

This test delivers all possible (single-root) four-message threads in
all possible orders and checks that notmuch successfully links them
into threads in every case.

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.
---

I thought I saw a bug in the thread linking code.  It turned out to be
okay, but I wrote this test to convince myself.

As far as I can tell, we don't have any tests specifically for thread
linking.  We certainly don't have any that are this systematic.

 test/T051-new-linking.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 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..b6d778a
--- /dev/null
+++ b/test/T051-new-linking.sh
@@ -0,0 +1,43 @@
+#!/usr/bin/env bash
+test_description='"notmuch new" thread linking'
+
+. ./test-lib.sh
+
+test_begin_subtest "All four-message threads get linked in all delivery orders"
+# 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.
+THREADS=$(python -c '
+def mkTrees(free, tree={}):
+    if not free:
+        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)
+    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)))')
+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 '*' | notmuch_search_sanitize)
+nthreads=$(wc -l <<< "$THREADS")
+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_done
-- 
1.8.4.rc3

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

[David Bremner]

Austin Clements <amdragon@MIT.EDU> writes:
> +THREADS=$(python -c '
> +def mkTrees(free, tree={}):
> +    if not free:

I'm not sure if using not for an empty set is idiomatic python or not,
but it did confuse me a moment.

> +        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)
> +    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)))')

FWIW, it took me a while to understand this.  I might have twigged
faster if the initial comment said something like "via backtracking".

> +output=$(notmuch search '*' | 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"

It seems to me this summary line depends on the default search order.
It might be worth specifying the search order in the "notmuch search"
command just to make it a bit more robust.

d

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

[Austin Clements]

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

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

[Mark Walters]

Hi

Broadly this looks good but I am somewhat confused by the python
part. Is it intended to produce the same tree multiple times? It does
seem to produce all the possible trees (*) so it doesn't matter but
might be worth a comment.

Best wishes

Mark

(*) I think there should be 64 rooted trees (16 trees and 4 possible
roots) and the python generates 144 lines. Piping the output to sort and
uniq gives 64 lines.


 
On Mon, 21 Apr 2014, Austin Clements <amdragon@MIT.EDU> wrote:
> 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

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

[Austin Clements]

The intent was to produce distinct trees, but obviously combinatorics
is not my strong suit.  Any ideas how to fix/rewrite the algorithm,
other than just uniq'ing the output?

Quoth Mark Walters on Apr 22 at 10:31 pm:
> 
> Hi
> 
> Broadly this looks good but I am somewhat confused by the python
> part. Is it intended to produce the same tree multiple times? It does
> seem to produce all the possible trees (*) so it doesn't matter but
> might be worth a comment.
> 
> Best wishes
> 
> Mark
> 
> (*) I think there should be 64 rooted trees (16 trees and 4 possible
> roots) and the python generates 144 lines. Piping the output to sort and
> uniq gives 64 lines.
> 
> 
>  
> On Mon, 21 Apr 2014, Austin Clements <amdragon@MIT.EDU> wrote:
> > 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

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

[Austin Clements]

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.
---
This version addresses Mark's review by using a completely different
thread tree generation algorithm that directly generates distinct
trees.  This algorithm is a little longer, so I pulled it out into its
own script.  Since v2, I also realized we already had an equivalent
hand-written, but far less thorough test in T260-thread-order, so this
version simply replaces that test.

Separately, I have an implementation of my ghost message proposal,
which fixes the known-broken test introduced in this patch (among
other things).  I'll send that once I've cleaned it up a bit.

 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 6c3a4b3..b435d79 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]=\<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."
+# 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]="\<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 "Adding second child message"
-generate_message [body]=foo "[in-reply-to]=\<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."
+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="<m$parent@t$thread> $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 0000000..9fbb847
--- /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.0.0

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

[David Bremner]

Austin Clements <amdragon@MIT.EDU> writes:

> This version addresses Mark's review by using a completely different
> thread tree generation algorithm that directly generates distinct
> trees.  This algorithm is a little longer, so I pulled it out into its
> own script.  Since v2, I also realized we already had an equivalent
> hand-written, but far less thorough test in T260-thread-order, so this
> version simply replaces that test.

Well, it matches the first 8 terms of 

      http://oeis.org/A000169

So I guess that's good enough for me ;).

d

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

[David Bremner]

Austin Clements <amdragon@MIT.EDU> writes:

> 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.

pushed.

d