1 Return-Path: <amdragon@mit.edu>
\r
2 X-Original-To: notmuch@notmuchmail.org
\r
3 Delivered-To: notmuch@notmuchmail.org
\r
4 Received: from localhost (localhost [127.0.0.1])
\r
5 by olra.theworths.org (Postfix) with ESMTP id 1E6DD431FB6
\r
6 for <notmuch@notmuchmail.org>; Wed, 9 Jul 2014 14:15:56 -0700 (PDT)
\r
7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org
\r
11 X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5
\r
12 tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled
\r
13 Received: from olra.theworths.org ([127.0.0.1])
\r
14 by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)
\r
15 with ESMTP id nVgLjLuoMOiq for <notmuch@notmuchmail.org>;
\r
16 Wed, 9 Jul 2014 14:15:48 -0700 (PDT)
\r
17 Received: from dmz-mailsec-scanner-2.mit.edu (dmz-mailsec-scanner-2.mit.edu
\r
19 (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
\r
20 (No client certificate requested)
\r
21 by olra.theworths.org (Postfix) with ESMTPS id 49118431FAF
\r
22 for <notmuch@notmuchmail.org>; Wed, 9 Jul 2014 14:15:48 -0700 (PDT)
\r
23 X-AuditID: 1209190d-f79c06d000002f07-42-53bdb10305cf
\r
24 Received: from mailhub-auth-4.mit.edu ( [18.7.62.39])
\r
25 (using TLS with cipher AES256-SHA (256/256 bits))
\r
26 (Client did not present a certificate)
\r
27 by dmz-mailsec-scanner-2.mit.edu (Symantec Messaging Gateway) with SMTP
\r
28 id 43.B3.12039.301BDB35; Wed, 9 Jul 2014 17:15:47 -0400 (EDT)
\r
29 Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11])
\r
30 by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id s69LFhD0004402;
\r
31 Wed, 9 Jul 2014 17:15:44 -0400
\r
32 Received: from drake.dyndns.org (26-4-172.dynamic.csail.mit.edu [18.26.4.172])
\r
33 (authenticated bits=0)
\r
34 (User authenticated as amdragon@ATHENA.MIT.EDU)
\r
35 by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id s69LFf9V024982
\r
36 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);
\r
37 Wed, 9 Jul 2014 17:15:42 -0400
\r
38 Received: from amthrax by drake.dyndns.org with local (Exim 4.77)
\r
39 (envelope-from <amdragon@mit.edu>)
\r
40 id 1X4zDJ-0005GS-8K; Wed, 09 Jul 2014 17:15:41 -0400
\r
41 From: Austin Clements <amdragon@MIT.EDU>
\r
42 To: notmuch@notmuchmail.org
\r
43 Subject: [PATCH v3] test: Test thread linking in all possible delivery orders
\r
44 Date: Wed, 9 Jul 2014 17:15:38 -0400
\r
45 Message-Id: <1404940538-19711-1-git-send-email-amdragon@mit.edu>
\r
46 X-Mailer: git-send-email 2.0.0
\r
47 In-Reply-To: <87wqehaw69.fsf@qmul.ac.uk>
\r
48 References: <87wqehaw69.fsf@qmul.ac.uk>
\r
49 X-Brightmail-Tracker:
\r
50 H4sIAAAAAAAAA+NgFjrKIsWRmVeSWpSXmKPExsUixG6nrsu8cW+wwetV6hY3WrsZLVbP5bG4
\r
51 fnMmswOzx85Zd9k9nq26xeyx5dB75gDmKC6blNSczLLUIn27BK6M/6seMRactahYskChgfGY
\r
52 bhcjJ4eEgIlEw7FrLBC2mMSFe+vZuhi5OIQEZjNJ3N/wlQnC2cAocW//K6jMYSaJ5s71UJm5
\r
53 jBLPr+9kA+lnE9CQ2LZ/OSOILSIgLbHz7mxWEJtZIFbi2vUDYDuEBXwllhxuA6rh4GARUJU4
\r
54 0cYLEuYVcJCYuHINK8QZchINNz6BjeQEGrnv0xpmEFtIQF3i/b49zBMY+RcwMqxilE3JrdLN
\r
55 TczMKU5N1i1OTszLSy3SNdLLzSzRS00p3cQICi1OSd4djO8OKh1iFOBgVOLh1ejaGyzEmlhW
\r
56 XJl7iFGSg0lJlPf8UqAQX1J+SmVGYnFGfFFpTmrxIUYJDmYlEd5bJUA53pTEyqrUonyYlDQH
\r
57 i5I471trq2AhgfTEktTs1NSC1CKYrAwHh5IEr+cGoEbBotT01Iq0zJwShDQTByfIcB6g4R/W
\r
58 gwwvLkjMLc5Mh8ifYlSUEue9sA4oIQCSyCjNg+uFxf4rRnGgV4R5g0BW8ADTBlz3K6DBTECD
\r
59 rS32gAwuSURISTUwnvXOfnP6f7Ypf5N0o8fPlVx6Surh6+QLuYV1Q3+HLfzaa2DwQK32Bdfy
\r
60 dbO+vWSNZu9/6XM6RDJUq5F9dYro9pJlLEqiO1+9ZNCrOzdNifmS7k0TlW9z+uW0emRij0TV
\r
61 R94JrXx2/96R7KMpPmsOLd+jcV5zAnuspk53pvP5OmuLP8X8Wx2UWIozEg21mIuKEwGoCJfG
\r
63 X-BeenThere: notmuch@notmuchmail.org
\r
64 X-Mailman-Version: 2.1.13
\r
66 List-Id: "Use and development of the notmuch mail system."
\r
67 <notmuch.notmuchmail.org>
\r
68 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,
\r
69 <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>
\r
70 List-Archive: <http://notmuchmail.org/pipermail/notmuch>
\r
71 List-Post: <mailto:notmuch@notmuchmail.org>
\r
72 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>
\r
73 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,
\r
74 <mailto:notmuch-request@notmuchmail.org?subject=subscribe>
\r
75 X-List-Received-Date: Wed, 09 Jul 2014 21:15:56 -0000
\r
77 These tests deliver all possible (single-root) four-message threads in
\r
78 all possible orders and check that notmuch successfully links them
\r
79 into threads. These tests supersede and replace the previous and much
\r
80 less thorough "T260-thread-order" tests.
\r
82 There are two variants of the test: one delivers messages that
\r
83 reference only their immediate parent and the other delivers messages
\r
84 that reference all of their parents. The latter test is currently
\r
87 This version addresses Mark's review by using a completely different
\r
88 thread tree generation algorithm that directly generates distinct
\r
89 trees. This algorithm is a little longer, so I pulled it out into its
\r
90 own script. Since v2, I also realized we already had an equivalent
\r
91 hand-written, but far less thorough test in T260-thread-order, so this
\r
92 version simply replaces that test.
\r
94 Separately, I have an implementation of my ghost message proposal,
\r
95 which fixes the known-broken test introduced in this patch (among
\r
96 other things). I'll send that once I've cleaned it up a bit.
\r
98 test/T260-thread-order.sh | 86 +++++++++++++++++++++++++++++++++++------------
\r
99 test/gen-threads.py | 33 ++++++++++++++++++
\r
100 2 files changed, 98 insertions(+), 21 deletions(-)
\r
101 create mode 100644 test/gen-threads.py
\r
103 diff --git a/test/T260-thread-order.sh b/test/T260-thread-order.sh
\r
104 index 6c3a4b3..b435d79 100755
\r
105 --- a/test/T260-thread-order.sh
\r
106 +++ b/test/T260-thread-order.sh
\r
108 test_description="threading when messages received out of order"
\r
111 -test_begin_subtest "Adding initial child message"
\r
112 -generate_message [body]=foo "[in-reply-to]=\<parent-id\>" [subject]=brokenthreadtest '[date]="Sat, 01 Jan 2000 12:00:00 -0000"'
\r
113 -output=$(NOTMUCH_NEW)
\r
114 -test_expect_equal "$output" "Added 1 new message to the database."
\r
115 +# Generate all single-root four message thread structures. We'll use
\r
116 +# this for multiple tests below.
\r
117 +THREADS=$(python ${TEST_DIRECTORY}/gen-threads.py 4)
\r
118 +nthreads=$(wc -l <<< "$THREADS")
\r
120 -test_begin_subtest "Searching returns the message"
\r
121 -output=$(notmuch search foo | notmuch_search_sanitize)
\r
122 -test_expect_equal "$output" "thread:XXX 2000-01-01 [1/1] Notmuch Test Suite; brokenthreadtest (inbox unread)"
\r
123 +test_begin_subtest "Messages with one parent get linked in all delivery orders"
\r
124 +# In the first variant, this delivers messages that reference only
\r
125 +# their immediate parent. Hence, we should only expect threads to be
\r
126 +# fully joined at the end.
\r
127 +for ((n = 0; n < 4; n++)); do
\r
128 + # Deliver the n'th message of every thread
\r
130 + while read -a parents; do
\r
131 + parent=${parents[$n]}
\r
132 + generate_message \
\r
133 + [id]=m$n@t$thread [in-reply-to]="\<m$parent@t$thread\>" \
\r
134 + [subject]=p$thread [from]=m$n
\r
135 + thread=$((thread + 1))
\r
136 + done <<< "$THREADS"
\r
137 + notmuch new > /dev/null
\r
139 +output=$(notmuch search --sort=newest-first '*' | notmuch_search_sanitize)
\r
140 +expected=$(for ((i = 0; i < $nthreads; i++)); do
\r
141 + echo "thread:XXX 2001-01-05 [4/4] m3, m2, m1, m0; p$i (inbox unread)"
\r
143 +test_expect_equal "$output" "$expected"
\r
145 -test_begin_subtest "Adding second child message"
\r
146 -generate_message [body]=foo "[in-reply-to]=\<parent-id\>" [subject]=brokenthreadtest '[date]="Sat, 01 Jan 2000 12:00:00 -0000"'
\r
147 -output=$(NOTMUCH_NEW)
\r
148 -test_expect_equal "$output" "Added 1 new message to the database."
\r
149 +test_begin_subtest "Messages with all parents get linked in all delivery orders"
\r
150 +test_subtest_known_broken
\r
151 +# Here we do the same thing as the previous test, but each message
\r
152 +# references all of its parents. Since every message references the
\r
153 +# root of the thread, each thread should always be fully joined. This
\r
154 +# is currently broken because of the bug detailed in
\r
155 +# id:8738h7kv2q.fsf@qmul.ac.uk.
\r
157 +notmuch new > /dev/null
\r
160 +for ((n = 0; n < 4; n++)); do
\r
161 + # Deliver the n'th message of every thread
\r
163 + while read -a parents; do
\r
165 + parent=${parents[$n]}
\r
166 + while [[ $parent != None ]]; do
\r
167 + references="<m$parent@t$thread> $references"
\r
168 + parent=${parents[$parent]}
\r
171 -test_begin_subtest "Searching returns both messages in one thread"
\r
172 -output=$(notmuch search foo | notmuch_search_sanitize)
\r
173 -test_expect_equal "$output" "thread:XXX 2000-01-01 [2/2] Notmuch Test Suite; brokenthreadtest (inbox unread)"
\r
174 + generate_message \
\r
175 + [id]=m$n@t$thread [references]="'$references'" \
\r
176 + [subject]=p$thread [from]=m$n
\r
177 + thread=$((thread + 1))
\r
178 + done <<< "$THREADS"
\r
179 + notmuch new > /dev/null
\r
181 -test_begin_subtest "Adding parent message"
\r
182 -generate_message [body]=foo [id]=parent-id [subject]=brokenthreadtest '[date]="Sat, 01 Jan 2000 12:00:00 -0000"'
\r
183 -output=$(NOTMUCH_NEW)
\r
184 -test_expect_equal "$output" "Added 1 new message to the database."
\r
186 +$(notmuch search --sort=newest-first '*' | notmuch_search_sanitize)"
\r
188 -test_begin_subtest "Searching returns all three messages in one thread"
\r
189 -output=$(notmuch search foo | notmuch_search_sanitize)
\r
190 -test_expect_equal "$output" "thread:XXX 2000-01-01 [3/3] Notmuch Test Suite; brokenthreadtest (inbox unread)"
\r
191 + # Construct expected output
\r
192 + template="thread:XXX 2001-01-05 [$((n+1))/$((n+1))]"
\r
193 + for ((m = n; m > 0; m--)); do
\r
194 + template="$template m$m,"
\r
196 + expected="$expected
\r
197 +$(for ((i = 0; i < $nthreads; i++)); do
\r
198 + echo "$template m0; p$i (inbox unread)"
\r
201 +test_expect_equal "$output" "$expected"
\r
204 diff --git a/test/gen-threads.py b/test/gen-threads.py
\r
205 new file mode 100644
\r
206 index 0000000..9fbb847
\r
208 +++ b/test/gen-threads.py
\r
210 +# Generate all possible single-root message thread structures of size
\r
211 +# argv[1]. Each output line is a thread structure, where the n'th
\r
212 +# field is either a number giving the parent of message n or "None"
\r
216 +from itertools import chain, combinations
\r
219 + return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
\r
221 +nodes = set(range(int(sys.argv[1])))
\r
223 +# Queue of (tree, free, to_expand) where tree is a {node: parent}
\r
224 +# dictionary, free is a set of unattached nodes, and to_expand is
\r
225 +# itself a queue of nodes in the tree that need to be expanded.
\r
226 +# The queue starts with all single-node trees.
\r
227 +queue = [({root: None}, nodes - {root}, (root,)) for root in nodes]
\r
231 + tree, free, to_expand = queue.pop()
\r
233 + if len(to_expand) == 0:
\r
234 + # Only print full-sized trees
\r
235 + if len(free) == 0:
\r
236 + print(" ".join(map(str, [msg[1] for msg in sorted(tree.items())])))
\r
238 + # Expand node to_expand[0] with each possible set of children
\r
239 + for children in subsets(free):
\r
240 + ntree = dict(tree, **{child: to_expand[0] for child in children})
\r
241 + nfree = free.difference(children)
\r
242 + queue.append((ntree, nfree, to_expand[1:] + tuple(children)))
\r