1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
|
package main
// Reconstructing a thread out of headers that cannot be trusted.
//
// Every case below is one the archive actually contains, and the reason this
// file is as long as it is: threading looks like a lookup and is really a set of
// failures to handle. A message may name a parent that is not here (6076 of
// them), name none at all (9798), carry no Message-ID so that nothing can ever
// name it (71), or share a Message-ID with two other rows. The interesting tests
// are not the ones where a thread reconstructs; they are the ones where it must
// not.
import (
"database/sql"
"path/filepath"
"strings"
"testing"
)
// newThreadDB builds an empty database and returns it for direct insertion.
//
// The messages are written with explicit ids and identifiers rather than through
// the IMAP sync, because what is under test is the join and not the mirror: a
// test that had to produce a real envelope to state "this message has no
// Message-ID" would be testing go-imap.
func newThreadDB(t *testing.T) *sql.DB {
t.Helper()
db, err := openDB(filepath.Join(t.TempDir(), "thread.db"))
if err != nil {
t.Fatalf("open db: %v", err)
}
t.Cleanup(func() { db.Close() })
return db
}
// insertThreadMsg writes one message. uid is derived from id so the
// (mailbox, uid, uidvalidity) unique constraint never collides.
func insertThreadMsg(t *testing.T, db *sql.DB, id int64, mailbox, from, subject, messageID, inReplyTo string, date int64) {
t.Helper()
_, err := db.Exec(
`INSERT INTO messages
(id, mailbox, uid, uidvalidity, subject, from_addr, date,
message_id, in_reply_to, references_, to_addrs, cc_addrs, bcc_addrs)
VALUES (?,?,?,1,?,?,?,?,?,'','[]','[]','[]')`,
id, mailbox, id, subject, from, date, messageID, inReplyTo)
if err != nil {
t.Fatalf("insert message %d: %v", id, err)
}
}
// TestThreadLinksParentAndReply is the shape of the mail that prompted all of
// this: a message sent to one address, answered by somebody else, where the
// reply names the original in In-Reply-To.
func TestThreadLinksParentAndReply(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "Sent", "me@example.org", "Parking data please", "orig@example.org", "", 1000)
insertThreadMsg(t, db, 2, "INBOX", "Andre <andre@example.org>", "AW: Parking data please", "reply@example.org", "orig@example.org", 2000)
// Downwards, from the message this account sent.
links, err := loadThreadLinks(db, 1)
if err != nil {
t.Fatalf("load links for 1: %v", err)
}
if links.Parent != nil || links.ParentMissing {
t.Errorf("message 1 began the thread, got parent=%v missing=%v",
links.Parent, links.ParentMissing)
}
if len(links.Replies) != 1 || links.Replies[0].ID != 2 {
t.Fatalf("want one reply (id 2), got %+v", links.Replies)
}
if links.Replies[0].Outgoing {
t.Error("the reply was written by somebody else; Outgoing must be false")
}
// Upwards, from the reply.
links, err = loadThreadLinks(db, 2)
if err != nil {
t.Fatalf("load links for 2: %v", err)
}
if links.Parent == nil {
t.Fatalf("message 2 names a mirrored parent, got none (missing=%v)", links.ParentMissing)
}
if links.Parent.ID != 1 {
t.Errorf("parent id = %d, want 1", links.Parent.ID)
}
if !links.Parent.Outgoing {
t.Error("the parent was written by this account; Outgoing must be true")
}
if len(links.Replies) != 0 {
t.Errorf("nothing answers message 2, got %+v", links.Replies)
}
}
// TestThreadLinksParentMissing pins the 6076 case. A claimed parent that is not
// mirrored must be reported as missing, never as absent: the two render
// identically only if the second is a lie.
func TestThreadLinksParentMissing(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "INBOX", "klara@example.org", "Re: something older",
"here@example.org", "gone@example.org", 1000)
links, err := loadThreadLinks(db, 1)
if err != nil {
t.Fatalf("load links: %v", err)
}
if links.Parent != nil {
t.Errorf("the parent is not in the mirror, got %+v", links.Parent)
}
if !links.ParentMissing {
t.Error("ParentMissing must be set: a claimed parent that cannot be found is " +
"not the same as claiming none, and a view showing nothing for both would " +
"say this message began the thread")
}
if links.ParentID != "gone@example.org" {
t.Errorf("ParentID = %q, want the identifier that was claimed", links.ParentID)
}
}
// TestThreadLinksNoParentClaimed is the 9798 case, and must be distinguishable
// from the one above.
func TestThreadLinksNoParentClaimed(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "INBOX", "klara@example.org", "Hello", "here@example.org", "", 1000)
links, err := loadThreadLinks(db, 1)
if err != nil {
t.Fatalf("load links: %v", err)
}
if links.Parent != nil || links.ParentMissing || links.ParentID != "" {
t.Errorf("a message claiming no parent must report none, got parent=%v missing=%v id=%q",
links.Parent, links.ParentMissing, links.ParentID)
}
if links.HasAny() {
t.Error("nothing to say about this message's thread; HasAny must be false so " +
"the view omits the region rather than drawing an empty one")
}
}
// TestThreadLinksEmptyIdentifiersDoNotJoin is the test this file exists for.
//
// 71 messages here carry no Message-ID and 9798 name no parent. Both are stored
// as the empty string, so a join written as `in_reply_to = message_id` matches
// every one of them against every other: each becomes a reply to all the rest.
// That is not a hypothetical — it is what the obvious query does.
func TestThreadLinksEmptyIdentifiersDoNotJoin(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
// Three messages with nothing to thread on, which the naive join would make
// into one thread of three.
insertThreadMsg(t, db, 1, "INBOX", "a@example.org", "No identifier at all", "", "", 1000)
insertThreadMsg(t, db, 2, "INBOX", "b@example.org", "Also none", "", "", 2000)
insertThreadMsg(t, db, 3, "INBOX", "c@example.org", "Names no parent", "three@example.org", "", 3000)
for _, id := range []int64{1, 2, 3} {
links, err := loadThreadLinks(db, id)
if err != nil {
t.Fatalf("load links for %d: %v", id, err)
}
if links.Parent != nil || links.ParentMissing {
t.Errorf("message %d: an empty In-Reply-To names no parent, got parent=%v missing=%v",
id, links.Parent, links.ParentMissing)
}
if len(links.Replies) != 0 {
t.Errorf("message %d: an empty Message-ID can be named by nothing, got %+v replies",
id, links.Replies)
}
}
}
// TestThreadLinksDuplicateMessageID pins that a Message-ID is not a key. One
// identifier in this archive names three rows; the parent link must be stable
// across requests rather than whichever row the engine reached first.
func TestThreadLinksDuplicateMessageID(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
// The same message filed in two mailboxes, as a copy would be.
insertThreadMsg(t, db, 1, "INBOX", "klara@example.org", "Original", "dup@example.org", "", 1000)
insertThreadMsg(t, db, 2, "Archive", "klara@example.org", "Original", "dup@example.org", "", 2000)
insertThreadMsg(t, db, 3, "INBOX", "me@example.org", "Re: Original", "mine@example.org", "dup@example.org", 3000)
for i := 0; i < 5; i++ {
links, err := loadThreadLinks(db, 3)
if err != nil {
t.Fatalf("load links: %v", err)
}
if links.Parent == nil {
t.Fatal("a duplicated parent is still a parent")
}
// Oldest wins: the original is what the reply was written against, and a
// later copy is the duplicate.
if links.Parent.ID != 1 {
t.Errorf("parent id = %d, want 1 (the oldest of the duplicates) — an "+
"arbitrary row would make this link change between requests",
links.Parent.ID)
}
}
}
// TestThreadLinksSelfReferenceIgnored covers a message naming itself as its own
// parent, which a broken client reusing one Message-ID produces. Left alone it
// is a link to the page you are on, and in any walk it is a cycle.
func TestThreadLinksSelfReference(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "INBOX", "klara@example.org", "Loop", "same@example.org", "same@example.org", 1000)
links, err := loadThreadLinks(db, 1)
if err != nil {
t.Fatalf("load links: %v", err)
}
if links.Parent != nil {
t.Errorf("a message is not its own parent, got a link to %d", links.Parent.ID)
}
if len(links.Replies) != 0 {
t.Errorf("nor its own reply, got %+v", links.Replies)
}
// It did claim one, and the claim cannot be satisfied, so saying so is
// right: the alternative is silently rendering nothing.
if !links.ParentMissing {
t.Error("the claim was made and could not be met; ParentMissing must say so")
}
}
// TestThreadLinksSeveralReplies pins that several answers to one message is
// ordinary and that they come back oldest first.
func TestThreadLinksSeveralReplies(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "Sent", "me@example.org", "Question", "q@example.org", "", 1000)
insertThreadMsg(t, db, 2, "INBOX", "b@example.org", "Re: Question", "b@example.org", "q@example.org", 3000)
insertThreadMsg(t, db, 3, "INBOX", "a@example.org", "Re: Question", "a@example.org", "q@example.org", 2000)
links, err := loadThreadLinks(db, 1)
if err != nil {
t.Fatalf("load links: %v", err)
}
if len(links.Replies) != 2 {
t.Fatalf("want 2 replies, got %d", len(links.Replies))
}
if links.Replies[0].ID != 3 || links.Replies[1].ID != 2 {
t.Errorf("replies must be oldest first, got ids %d then %d",
links.Replies[0].ID, links.Replies[1].ID)
}
}
// TestThreadLinksPartialIndexIsUsed is a performance test written as a
// correctness one, because here the difference is not a constant factor.
//
// The indexes from migration014 are partial, and SQLite uses a partial index
// only where it can prove the query implies the predicate. A lookup that omits
// the `<> ”` clause scans the whole messages table — 340 MB on the live
// archive, and a thread walk does it once per message. The clause looks
// redundant and is the entire reason the queries are affordable, so a plan that
// stops saying SEARCH is a regression nothing else would catch.
func TestThreadLinksPartialIndexIsUsed(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "INBOX", "klara@example.org", "x", "a@example.org", "b@example.org", 1000)
cases := []struct {
what string
query string
}{
{"parent lookup", `SELECT id FROM messages WHERE message_id = 'x' AND message_id <> ''`},
{"reply lookup", `SELECT id FROM messages WHERE in_reply_to = 'x' AND in_reply_to <> ''`},
}
for _, c := range cases {
var detail string
row := db.QueryRow(`EXPLAIN QUERY PLAN ` + c.query)
var a, b, d int
if err := row.Scan(&a, &b, &d, &detail); err != nil {
t.Fatalf("%s: explain: %v", c.what, err)
}
if !containsAll(detail, "SEARCH", "INDEX") {
t.Errorf("%s uses no index: %q\n"+
"The partial indexes in migration014 require the `<> ''` predicate in "+
"the query. Without it this is a full scan of the messages table.",
c.what, detail)
}
}
}
func containsAll(s string, subs ...string) bool {
for _, sub := range subs {
found := false
for i := 0; i+len(sub) <= len(s); i++ {
if s[i:i+len(sub)] == sub {
found = true
break
}
}
if !found {
return false
}
}
return true
}
// TestThreadWalkDrivesFromTheThread guards the CROSS JOIN in collectThreadAddresses.
//
// Written as an ordinary join, the walk drives from messages and scans every row
// — 210ms per walk on the live archive against 2.7ms, a 77x difference that no
// functional test can see, because the results are identical. CROSS JOIN is the
// only thing fixing the order, and it reads like a mistake, so it is exactly the
// kind of thing somebody tidies away.
func TestThreadWalkDrivesFromTheThread(t *testing.T) {
setTestAccount(t)
db := newThreadDB(t)
insertThreadMsg(t, db, 1, "INBOX", "a@example.org", "x", "root@example.org", "", 1000)
insertThreadMsg(t, db, 2, "INBOX", "b@example.org", "y", "kid@example.org", "root@example.org", 2000)
// The plan of the same walk the function runs. Kept in step with it by the
// behavioural tests above: if the query changes shape, those fail too.
rows, err := db.Query(`EXPLAIN QUERY PLAN `+threadWalkSQL, "root@example.org",
threadMaxDepth, threadMaxDepth, int64(2))
if err != nil {
t.Fatalf("explain: %v", err)
}
defer rows.Close()
var plan []string
for rows.Next() {
var a, b, c int
var detail string
if err := rows.Scan(&a, &b, &c, &detail); err != nil {
t.Fatalf("scan plan: %v", err)
}
plan = append(plan, detail)
}
joined := strings.Join(plan, "\n")
// The final step must probe messages through the Message-ID index rather than
// scanning the table.
if !strings.Contains(joined, "SEARCH m USING INDEX idx_messages_message_id") {
t.Errorf("the thread walk no longer probes messages through "+
"idx_messages_message_id. Check the CROSS JOIN is still there: an "+
"ordinary join lets SQLite drive from messages and scan it.\nplan:\n%s",
joined)
}
// And the scan it does do must be of the materialised thread, which is small.
if !strings.Contains(joined, "SCAN tree") {
t.Errorf("the walk should drive from the thread rows.\nplan:\n%s", joined)
}
}
|