From 1f4dc0bb3ee6762a313d8889e0c79c587add320c Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Thu, 10 Jul 2014 17:15:38 +2000 Subject: [PATCH] [PATCH v3] test: Test thread linking in all possible delivery orders --- 47/12c717de7e15c3a43f6448da9ee932e20da10d | 245 ++++++++++++++++++++++ 1 file changed, 245 insertions(+) create mode 100644 47/12c717de7e15c3a43f6448da9ee932e20da10d diff --git a/47/12c717de7e15c3a43f6448da9ee932e20da10d b/47/12c717de7e15c3a43f6448da9ee932e20da10d new file mode 100644 index 000000000..50dc2eb24 --- /dev/null +++ b/47/12c717de7e15c3a43f6448da9ee932e20da10d @@ -0,0 +1,245 @@ +Return-Path: +X-Original-To: notmuch@notmuchmail.org +Delivered-To: notmuch@notmuchmail.org +Received: from localhost (localhost [127.0.0.1]) + by olra.theworths.org (Postfix) with ESMTP id 1E6DD431FB6 + for ; Wed, 9 Jul 2014 14:15:56 -0700 (PDT) +X-Virus-Scanned: Debian amavisd-new at olra.theworths.org +X-Spam-Flag: NO +X-Spam-Score: -0.7 +X-Spam-Level: +X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5 + tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled +Received: from olra.theworths.org ([127.0.0.1]) + by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id nVgLjLuoMOiq for ; + Wed, 9 Jul 2014 14:15:48 -0700 (PDT) +Received: from dmz-mailsec-scanner-2.mit.edu (dmz-mailsec-scanner-2.mit.edu + [18.9.25.13]) + (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) + (No client certificate requested) + by olra.theworths.org (Postfix) with ESMTPS id 49118431FAF + for ; Wed, 9 Jul 2014 14:15:48 -0700 (PDT) +X-AuditID: 1209190d-f79c06d000002f07-42-53bdb10305cf +Received: from mailhub-auth-4.mit.edu ( [18.7.62.39]) + (using TLS with cipher AES256-SHA (256/256 bits)) + (Client did not present a certificate) + by dmz-mailsec-scanner-2.mit.edu (Symantec Messaging Gateway) with SMTP + id 43.B3.12039.301BDB35; Wed, 9 Jul 2014 17:15:47 -0400 (EDT) +Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) + by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id s69LFhD0004402; + Wed, 9 Jul 2014 17:15:44 -0400 +Received: from drake.dyndns.org (26-4-172.dynamic.csail.mit.edu [18.26.4.172]) + (authenticated bits=0) + (User authenticated as amdragon@ATHENA.MIT.EDU) + by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id s69LFf9V024982 + (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT); + Wed, 9 Jul 2014 17:15:42 -0400 +Received: from amthrax by drake.dyndns.org with local (Exim 4.77) + (envelope-from ) + id 1X4zDJ-0005GS-8K; Wed, 09 Jul 2014 17:15:41 -0400 +From: Austin Clements +To: notmuch@notmuchmail.org +Subject: [PATCH v3] test: Test thread linking in all possible delivery orders +Date: Wed, 9 Jul 2014 17:15:38 -0400 +Message-Id: <1404940538-19711-1-git-send-email-amdragon@mit.edu> +X-Mailer: git-send-email 2.0.0 +In-Reply-To: <87wqehaw69.fsf@qmul.ac.uk> +References: <87wqehaw69.fsf@qmul.ac.uk> +X-Brightmail-Tracker: + H4sIAAAAAAAAA+NgFjrKIsWRmVeSWpSXmKPExsUixG6nrsu8cW+wwetV6hY3WrsZLVbP5bG4 + fnMmswOzx85Zd9k9nq26xeyx5dB75gDmKC6blNSczLLUIn27BK6M/6seMRactahYskChgfGY + bhcjJ4eEgIlEw7FrLBC2mMSFe+vZuhi5OIQEZjNJ3N/wlQnC2cAocW//K6jMYSaJ5s71UJm5 + jBLPr+9kA+lnE9CQ2LZ/OSOILSIgLbHz7mxWEJtZIFbi2vUDYDuEBXwllhxuA6rh4GARUJU4 + 0cYLEuYVcJCYuHINK8QZchINNz6BjeQEGrnv0xpmEFtIQF3i/b49zBMY+RcwMqxilE3JrdLN + TczMKU5N1i1OTszLSy3SNdLLzSzRS00p3cQICi1OSd4djO8OKh1iFOBgVOLh1ejaGyzEmlhW + XJl7iFGSg0lJlPf8UqAQX1J+SmVGYnFGfFFpTmrxIUYJDmYlEd5bJUA53pTEyqrUonyYlDQH + i5I471trq2AhgfTEktTs1NSC1CKYrAwHh5IEr+cGoEbBotT01Iq0zJwShDQTByfIcB6g4R/W + gwwvLkjMLc5Mh8ifYlSUEue9sA4oIQCSyCjNg+uFxf4rRnGgV4R5g0BW8ADTBlz3K6DBTECD + rS32gAwuSURISTUwnvXOfnP6f7Ypf5N0o8fPlVx6Surh6+QLuYV1Q3+HLfzaa2DwQK32Bdfy + dbO+vWSNZu9/6XM6RDJUq5F9dYro9pJlLEqiO1+9ZNCrOzdNifmS7k0TlW9z+uW0emRij0TV + R94JrXx2/96R7KMpPmsOLd+jcV5zAnuspk53pvP5OmuLP8X8Wx2UWIozEg21mIuKEwGoCJfG + 2AIAAA== +X-BeenThere: notmuch@notmuchmail.org +X-Mailman-Version: 2.1.13 +Precedence: list +List-Id: "Use and development of the notmuch mail system." + +List-Unsubscribe: , + +List-Archive: +List-Post: +List-Help: +List-Subscribe: , + +X-List-Received-Date: Wed, 09 Jul 2014 21:15:56 -0000 + +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]=\" [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 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 + -- 2.26.2