1package imapserver
2
3import (
4 "fmt"
5 "log/slog"
6 "net/textproto"
7 "strings"
8
9 "github.com/mjl-/bstore"
10
11 "github.com/mjl-/mox/message"
12 "github.com/mjl-/mox/store"
13)
14
15// Search returns messages matching criteria specified in parameters.
16//
17// State: Selected
18func (c *conn) cmdxSearch(isUID bool, tag, cmd string, p *parser) {
19 // Command: ../rfc/9051:3716 ../rfc/4731:31 ../rfc/4466:354 ../rfc/3501:2723
20 // Examples: ../rfc/9051:3986 ../rfc/4731:153 ../rfc/3501:2975
21 // Syntax: ../rfc/9051:6918 ../rfc/4466:611 ../rfc/3501:4954
22
23 // We will respond with ESEARCH instead of SEARCH if "RETURN" is present or for IMAP4rev2.
24 var eargs map[string]bool // Options except SAVE. Nil means old-style SEARCH response.
25 var save bool // For SAVE option. Kept separately for easier handling of MIN/MAX later.
26
27 // IMAP4rev2 always returns ESEARCH, even with absent RETURN.
28 if c.enabled[capIMAP4rev2] {
29 eargs = map[string]bool{}
30 }
31 // ../rfc/9051:6967
32 if p.take(" RETURN (") {
33 eargs = map[string]bool{}
34
35 for !p.take(")") {
36 if len(eargs) > 0 || save {
37 p.xspace()
38 }
39 if w, ok := p.takelist("MIN", "MAX", "ALL", "COUNT", "SAVE"); ok {
40 if w == "SAVE" {
41 save = true
42 } else {
43 eargs[w] = true
44 }
45 } else {
46 // ../rfc/4466:378 ../rfc/9051:3745
47 xsyntaxErrorf("ESEARCH result option %q not supported", w)
48 }
49 }
50 }
51 // ../rfc/4731:149 ../rfc/9051:3737
52 if eargs != nil && len(eargs) == 0 && !save {
53 eargs["ALL"] = true
54 }
55
56 // If UTF8=ACCEPT is enabled, we should not accept any charset. We are a bit more
57 // relaxed (reasonable?) and still allow US-ASCII and UTF-8. ../rfc/6855:198
58 if p.take(" CHARSET ") {
59 charset := strings.ToUpper(p.xastring())
60 if charset != "US-ASCII" && charset != "UTF-8" {
61 // ../rfc/3501:2771 ../rfc/9051:3836
62 xusercodeErrorf("BADCHARSET", "only US-ASCII and UTF-8 supported")
63 }
64 }
65 p.xspace()
66 sk := &searchKey{
67 searchKeys: []searchKey{*p.xsearchKey()},
68 }
69 for !p.empty() {
70 p.xspace()
71 sk.searchKeys = append(sk.searchKeys, *p.xsearchKey())
72 }
73
74 // Even in case of error, we ensure search result is changed.
75 if save {
76 c.searchResult = []store.UID{}
77 }
78
79 // We gather word and not-word searches from the top-level, turn them
80 // into a WordSearch for a more efficient search.
81 // todo optimize: also gather them out of AND searches.
82 var textWords, textNotWords, bodyWords, bodyNotWords []string
83 n := 0
84 for _, xsk := range sk.searchKeys {
85 switch xsk.op {
86 case "BODY":
87 bodyWords = append(bodyWords, xsk.astring)
88 continue
89 case "TEXT":
90 textWords = append(textWords, xsk.astring)
91 continue
92 case "NOT":
93 switch xsk.searchKey.op {
94 case "BODY":
95 bodyNotWords = append(bodyNotWords, xsk.searchKey.astring)
96 continue
97 case "TEXT":
98 textNotWords = append(textNotWords, xsk.searchKey.astring)
99 continue
100 }
101 }
102 sk.searchKeys[n] = xsk
103 n++
104 }
105 // We may be left with an empty but non-nil sk.searchKeys, which is important for
106 // matching.
107 sk.searchKeys = sk.searchKeys[:n]
108 var bodySearch, textSearch *store.WordSearch
109 if len(bodyWords) > 0 || len(bodyNotWords) > 0 {
110 ws := store.PrepareWordSearch(bodyWords, bodyNotWords)
111 bodySearch = &ws
112 }
113 if len(textWords) > 0 || len(textNotWords) > 0 {
114 ws := store.PrepareWordSearch(textWords, textNotWords)
115 textSearch = &ws
116 }
117
118 // Note: we only hold the account rlock for verifying the mailbox at the start.
119 c.account.RLock()
120 runlock := c.account.RUnlock
121 // Note: in a defer because we replace it below.
122 defer func() {
123 runlock()
124 }()
125
126 // If we only have a MIN and/or MAX, we can stop processing as soon as we
127 // have those matches.
128 var min, max int
129 if eargs["MIN"] {
130 min = 1
131 }
132 if eargs["MAX"] {
133 max = 1
134 }
135
136 var expungeIssued bool
137 var maxModSeq store.ModSeq
138
139 var uids []store.UID
140 c.xdbread(func(tx *bstore.Tx) {
141 c.xmailboxID(tx, c.mailboxID) // Validate.
142 runlock()
143 runlock = func() {}
144
145 // Normal forward search when we don't have MAX only.
146 var lastIndex = -1
147 if eargs == nil || max == 0 || len(eargs) != 1 {
148 for i, uid := range c.uids {
149 lastIndex = i
150 if match, modseq := c.searchMatch(tx, msgseq(i+1), uid, *sk, bodySearch, textSearch, &expungeIssued); match {
151 uids = append(uids, uid)
152 if modseq > maxModSeq {
153 maxModSeq = modseq
154 }
155 if min == 1 && min+max == len(eargs) {
156 break
157 }
158 }
159 }
160 }
161 // And reverse search for MAX if we have only MAX or MAX combined with MIN.
162 if max == 1 && (len(eargs) == 1 || min+max == len(eargs)) {
163 for i := len(c.uids) - 1; i > lastIndex; i-- {
164 if match, modseq := c.searchMatch(tx, msgseq(i+1), c.uids[i], *sk, bodySearch, textSearch, &expungeIssued); match {
165 uids = append(uids, c.uids[i])
166 if modseq > maxModSeq {
167 maxModSeq = modseq
168 }
169 break
170 }
171 }
172 }
173 })
174
175 if eargs == nil {
176 // In IMAP4rev1, an untagged SEARCH response is required. ../rfc/3501:2728
177 if len(uids) == 0 {
178 c.bwritelinef("* SEARCH")
179 }
180
181 // Old-style SEARCH response. We must spell out each number. So we may be splitting
182 // into multiple responses. ../rfc/9051:6809 ../rfc/3501:4833
183 for len(uids) > 0 {
184 n := len(uids)
185 if n > 100 {
186 n = 100
187 }
188 s := ""
189 for _, v := range uids[:n] {
190 if !isUID {
191 v = store.UID(c.xsequence(v))
192 }
193 s += " " + fmt.Sprintf("%d", v)
194 }
195
196 // Since we don't have the max modseq for the possibly partial uid range we're
197 // writing here within hand reach, we conveniently interpret the ambiguous "for all
198 // messages being returned" in ../rfc/7162:1107 as meaning over all lines that we
199 // write. And that clients only commit this value after they have seen the tagged
200 // end of the command. Appears to be recommended behaviour, ../rfc/7162:2323.
201 // ../rfc/7162:1077 ../rfc/7162:1101
202 var modseq string
203 if sk.hasModseq() {
204 // ../rfc/7162:2557
205 modseq = fmt.Sprintf(" (MODSEQ %d)", maxModSeq.Client())
206 }
207
208 c.bwritelinef("* SEARCH%s%s", s, modseq)
209 uids = uids[n:]
210 }
211 } else {
212 // New-style ESEARCH response syntax: ../rfc/9051:6546 ../rfc/4466:522
213
214 if save {
215 // ../rfc/9051:3784 ../rfc/5182:13
216 c.searchResult = uids
217 if sanityChecks {
218 checkUIDs(c.searchResult)
219 }
220 }
221
222 // No untagged ESEARCH response if nothing was requested. ../rfc/9051:4160
223 if len(eargs) > 0 {
224 // The tag was originally a string, became an astring in IMAP4rev2, better stick to
225 // string. ../rfc/4466:707 ../rfc/5259:1163 ../rfc/9051:7087
226 resp := fmt.Sprintf(`* ESEARCH (TAG "%s")`, tag)
227 if isUID {
228 resp += " UID"
229 }
230
231 // NOTE: we are converting UIDs to msgseq in the uids slice (if needed) while
232 // keeping the "uids" name!
233 if !isUID {
234 // If searchResult is hanging on to the slice, we need to work on a copy.
235 if save {
236 nuids := make([]store.UID, len(uids))
237 copy(nuids, uids)
238 uids = nuids
239 }
240 for i, uid := range uids {
241 uids[i] = store.UID(c.xsequence(uid))
242 }
243 }
244
245 // If no matches, then no MIN/MAX response. ../rfc/4731:98 ../rfc/9051:3758
246 if eargs["MIN"] && len(uids) > 0 {
247 resp += fmt.Sprintf(" MIN %d", uids[0])
248 }
249 if eargs["MAX"] && len(uids) > 0 {
250 resp += fmt.Sprintf(" MAX %d", uids[len(uids)-1])
251 }
252 if eargs["COUNT"] {
253 resp += fmt.Sprintf(" COUNT %d", len(uids))
254 }
255 if eargs["ALL"] && len(uids) > 0 {
256 resp += fmt.Sprintf(" ALL %s", compactUIDSet(uids).String())
257 }
258
259 // Interaction between ESEARCH and CONDSTORE: ../rfc/7162:1211 ../rfc/4731:273
260 // Summary: send the highest modseq of the returned messages.
261 if sk.hasModseq() && len(uids) > 0 {
262 resp += fmt.Sprintf(" MODSEQ %d", maxModSeq.Client())
263 }
264
265 c.bwritelinef("%s", resp)
266 }
267 }
268 if expungeIssued {
269 // ../rfc/9051:5102
270 c.writeresultf("%s OK [EXPUNGEISSUED] done", tag)
271 } else {
272 c.ok(tag, cmd)
273 }
274}
275
276type search struct {
277 c *conn
278 tx *bstore.Tx
279 seq msgseq
280 uid store.UID
281 mr *store.MsgReader
282 m store.Message
283 p *message.Part
284 expungeIssued *bool
285 hasModseq bool
286}
287
288func (c *conn) searchMatch(tx *bstore.Tx, seq msgseq, uid store.UID, sk searchKey, bodySearch, textSearch *store.WordSearch, expungeIssued *bool) (bool, store.ModSeq) {
289 s := search{c: c, tx: tx, seq: seq, uid: uid, expungeIssued: expungeIssued, hasModseq: sk.hasModseq()}
290 defer func() {
291 if s.mr != nil {
292 err := s.mr.Close()
293 c.xsanity(err, "closing messagereader")
294 s.mr = nil
295 }
296 }()
297 return s.match(sk, bodySearch, textSearch)
298}
299
300func (s *search) match(sk searchKey, bodySearch, textSearch *store.WordSearch) (match bool, modseq store.ModSeq) {
301 // Instead of littering all the cases in match0 with calls to get modseq, we do it once
302 // here in case of a match.
303 defer func() {
304 if match && s.hasModseq {
305 if s.m.ID == 0 {
306 match = s.xensureMessage()
307 }
308 modseq = s.m.ModSeq
309 }
310 }()
311
312 match = s.match0(sk)
313 if match && bodySearch != nil {
314 if !s.xensurePart() {
315 match = false
316 return
317 }
318 var err error
319 match, err = bodySearch.MatchPart(s.c.log, s.p, false)
320 xcheckf(err, "search words in bodies")
321 }
322 if match && textSearch != nil {
323 if !s.xensurePart() {
324 match = false
325 return
326 }
327 var err error
328 match, err = textSearch.MatchPart(s.c.log, s.p, true)
329 xcheckf(err, "search words in headers and bodies")
330 }
331 return
332}
333
334func (s *search) xensureMessage() bool {
335 if s.m.ID > 0 {
336 return true
337 }
338
339 q := bstore.QueryTx[store.Message](s.tx)
340 q.FilterNonzero(store.Message{MailboxID: s.c.mailboxID, UID: s.uid})
341 m, err := q.Get()
342 if err == bstore.ErrAbsent || err == nil && m.Expunged {
343 // ../rfc/2180:607
344 *s.expungeIssued = true
345 return false
346 }
347 xcheckf(err, "get message")
348 s.m = m
349 return true
350}
351
352// ensure message, reader and part are loaded. returns whether that was
353// successful.
354func (s *search) xensurePart() bool {
355 if s.mr != nil {
356 return s.p != nil
357 }
358
359 if !s.xensureMessage() {
360 return false
361 }
362
363 // Closed by searchMatch after all (recursive) search.match calls are finished.
364 s.mr = s.c.account.MessageReader(s.m)
365
366 if s.m.ParsedBuf == nil {
367 s.c.log.Error("missing parsed message")
368 return false
369 }
370 p, err := s.m.LoadPart(s.mr)
371 xcheckf(err, "load parsed message")
372 s.p = &p
373 return true
374}
375
376func (s *search) match0(sk searchKey) bool {
377 c := s.c
378
379 // Difference between sk.searchKeys nil and length 0 is important. Because we take
380 // out word/notword searches, the list may be empty but non-nil.
381 if sk.searchKeys != nil {
382 for _, ssk := range sk.searchKeys {
383 if !s.match0(ssk) {
384 return false
385 }
386 }
387 return true
388 } else if sk.seqSet != nil {
389 return sk.seqSet.containsSeq(s.seq, c.uids, c.searchResult)
390 }
391
392 filterHeader := func(field, value string) bool {
393 lower := strings.ToLower(value)
394 h, err := s.p.Header()
395 if err != nil {
396 c.log.Debugx("parsing message header", err, slog.Any("uid", s.uid))
397 return false
398 }
399 for _, v := range h.Values(field) {
400 if strings.Contains(strings.ToLower(v), lower) {
401 return true
402 }
403 }
404 return false
405 }
406
407 // We handle ops by groups that need increasing details about the message.
408
409 switch sk.op {
410 case "ALL":
411 return true
412 case "NEW":
413 // We do not implement the RECENT flag, so messages cannot be NEW.
414 return false
415 case "OLD":
416 // We treat all messages as non-recent, so this means all messages.
417 return true
418 case "RECENT":
419 // We do not implement the RECENT flag. All messages are not recent.
420 return false
421 case "NOT":
422 return !s.match0(*sk.searchKey)
423 case "OR":
424 return s.match0(*sk.searchKey) || s.match0(*sk.searchKey2)
425 case "UID":
426 return sk.uidSet.containsUID(s.uid, c.uids, c.searchResult)
427 }
428
429 // Parsed part.
430 if !s.xensurePart() {
431 return false
432 }
433
434 // Parsed message, basic info.
435 switch sk.op {
436 case "ANSWERED":
437 return s.m.Answered
438 case "DELETED":
439 return s.m.Deleted
440 case "FLAGGED":
441 return s.m.Flagged
442 case "KEYWORD":
443 kw := strings.ToLower(sk.atom)
444 switch kw {
445 case "$forwarded":
446 return s.m.Forwarded
447 case "$junk":
448 return s.m.Junk
449 case "$notjunk":
450 return s.m.Notjunk
451 case "$phishing":
452 return s.m.Phishing
453 case "$mdnsent":
454 return s.m.MDNSent
455 default:
456 for _, k := range s.m.Keywords {
457 if k == kw {
458 return true
459 }
460 }
461 return false
462 }
463 case "SEEN":
464 return s.m.Seen
465 case "UNANSWERED":
466 return !s.m.Answered
467 case "UNDELETED":
468 return !s.m.Deleted
469 case "UNFLAGGED":
470 return !s.m.Flagged
471 case "UNKEYWORD":
472 kw := strings.ToLower(sk.atom)
473 switch kw {
474 case "$forwarded":
475 return !s.m.Forwarded
476 case "$junk":
477 return !s.m.Junk
478 case "$notjunk":
479 return !s.m.Notjunk
480 case "$phishing":
481 return !s.m.Phishing
482 case "$mdnsent":
483 return !s.m.MDNSent
484 default:
485 for _, k := range s.m.Keywords {
486 if k == kw {
487 return false
488 }
489 }
490 return true
491 }
492 case "UNSEEN":
493 return !s.m.Seen
494 case "DRAFT":
495 return s.m.Draft
496 case "UNDRAFT":
497 return !s.m.Draft
498 case "BEFORE", "ON", "SINCE":
499 skdt := sk.date.Format("2006-01-02")
500 rdt := s.m.Received.Format("2006-01-02")
501 switch sk.op {
502 case "BEFORE":
503 return rdt < skdt
504 case "ON":
505 return rdt == skdt
506 case "SINCE":
507 return rdt >= skdt
508 }
509 panic("missing case")
510 case "LARGER":
511 return s.m.Size > sk.number
512 case "SMALLER":
513 return s.m.Size < sk.number
514 case "MODSEQ":
515 // ../rfc/7162:1045
516 return s.m.ModSeq.Client() >= *sk.clientModseq
517 }
518
519 if s.p == nil {
520 c.log.Info("missing parsed message, not matching", slog.Any("uid", s.uid))
521 return false
522 }
523
524 // Parsed message, more info.
525 switch sk.op {
526 case "BCC":
527 return filterHeader("Bcc", sk.astring)
528 case "BODY", "TEXT":
529 // We gathered word/notword searches from the top-level, but we can also get them
530 // nested.
531 // todo optimize: handle deeper nested word/not-word searches more efficiently.
532 headerToo := sk.op == "TEXT"
533 match, err := store.PrepareWordSearch([]string{sk.astring}, nil).MatchPart(s.c.log, s.p, headerToo)
534 xcheckf(err, "word search")
535 return match
536 case "CC":
537 return filterHeader("Cc", sk.astring)
538 case "FROM":
539 return filterHeader("From", sk.astring)
540 case "SUBJECT":
541 return filterHeader("Subject", sk.astring)
542 case "TO":
543 return filterHeader("To", sk.astring)
544 case "HEADER":
545 // ../rfc/9051:3895
546 lower := strings.ToLower(sk.astring)
547 h, err := s.p.Header()
548 if err != nil {
549 c.log.Errorx("parsing header for search", err, slog.Any("uid", s.uid))
550 return false
551 }
552 k := textproto.CanonicalMIMEHeaderKey(sk.headerField)
553 for _, v := range h.Values(k) {
554 if lower == "" || strings.Contains(strings.ToLower(v), lower) {
555 return true
556 }
557 }
558 return false
559 case "SENTBEFORE", "SENTON", "SENTSINCE":
560 if s.p.Envelope == nil || s.p.Envelope.Date.IsZero() {
561 return false
562 }
563 dt := s.p.Envelope.Date.Format("2006-01-02")
564 skdt := sk.date.Format("2006-01-02")
565 switch sk.op {
566 case "SENTBEFORE":
567 return dt < skdt
568 case "SENTON":
569 return dt == skdt
570 case "SENTSINCE":
571 return dt > skdt
572 }
573 panic("missing case")
574 }
575 panic(serverError{fmt.Errorf("missing case for search key op %q", sk.op)})
576}
577