Date: Tue, 22 Apr 2014 18:11:15 -0400
From: Austin Clements <amdragon@MIT.EDU>
To: Mark Walters <markwalters1009@gmail.com>
Subject: Re: [PATCH v2] test: Test thread linking in all possible delivery
	orders
Message-ID: <20140422221115.GH25817@mit.edu>
References: <87y4zhfmrn.fsf@maritornes.cs.unb.ca>
	<1398110291-15832-1-git-send-email-amdragon@mit.edu>
	<87wqehaw69.fsf@qmul.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <87wqehaw69.fsf@qmul.ac.uk>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: notmuch@notmuchmail.org
Precedence: list

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