13 "github.com/mjl-/bstore"
15 "github.com/mjl-/mox/message"
16 "github.com/mjl-/mox/store"
19// If last search output was this long ago, we write an untagged inprogress
21var inProgressPeriod = time.Duration(10 * time.Second)
23// ESEARCH allows searching multiple mailboxes, referenced through mailbox filters
24// borrowed from the NOTIFY extension. Unlike the regular extended SEARCH/UID
25// SEARCH command that always returns an ESEARCH response, the ESEARCH command only
26// returns ESEARCH responses when there were matches in a mailbox.
29func (c *conn) cmdEsearch(tag, cmd string, p *parser) {
30 c.cmdxSearch(true, true, tag, cmd, p)
33// Search returns messages matching criteria specified in parameters.
35// State: Selected for SEARCH and UID SEARCH, Authenticated or selectd for ESEARCH.
36func (c *conn) cmdxSearch(isUID, isE bool, tag, cmd string, p *parser) {
41 // We will respond with ESEARCH instead of SEARCH if "RETURN" is present or for IMAP4rev2 or for isE (ESEARCH command).
42 var eargs map[string]bool // Options except SAVE. Nil means old-style SEARCH response.
43 var save bool // For SAVE option. Kept separately for easier handling of MIN/MAX later.
45 if c.enabled[capIMAP4rev2] || isE {
46 eargs = map[string]bool{}
49 // The ESEARCH command has various ways to specify which mailboxes are to be
50 // searched. We parse and gather the request first, and evaluate them to mailboxes
51 // after parsing, when we start and have a DB transaction.
52 type mailboxSpec struct {
56 var mailboxSpecs []mailboxSpec
59 if isE && p.take(" IN (") {
62 mbs.Kind = p.xtakelist("SELECTED", "INBOXES", "PERSONAL", "SUBSCRIBED", "SUBTREE-ONE", "SUBTREE", "MAILBOXES")
64 case "SUBTREE", "SUBTREE-ONE", "MAILBOXES":
68 mbs.Args = append(mbs.Args, p.xmailbox())
75 mbs.Args = []string{p.xmailbox()}
78 mailboxSpecs = append(mailboxSpecs, mbs)
85 // We are not parsing the scope-options since there aren't any defined yet.
../rfc/7377:469
88 if p.take(" RETURN (") {
89 eargs = map[string]bool{}
92 if len(eargs) > 0 || save {
95 if w, ok := p.takelist("MIN", "MAX", "ALL", "COUNT", "SAVE"); ok {
103 xsyntaxErrorf("ESEARCH result option %q not supported", w)
108 if eargs != nil && len(eargs) == 0 && !save {
112 // If UTF8=ACCEPT is enabled, we should not accept any charset. We are a bit more
114 if p.take(" CHARSET ") {
115 charset := strings.ToUpper(p.xastring())
116 if charset != "US-ASCII" && charset != "UTF-8" {
118 xusercodeErrorf("BADCHARSET", "only US-ASCII and UTF-8 supported")
123 searchKeys: []searchKey{*p.xsearchKey()},
127 sk.searchKeys = append(sk.searchKeys, *p.xsearchKey())
130 // Even in case of error, we ensure search result is changed.
132 c.searchResult = []store.UID{}
135 // We gather word and not-word searches from the top-level, turn them
136 // into a WordSearch for a more efficient search.
137 // todo optimize: also gather them out of AND searches.
138 var textWords, textNotWords, bodyWords, bodyNotWords []string
140 for _, xsk := range sk.searchKeys {
143 bodyWords = append(bodyWords, xsk.astring)
146 textWords = append(textWords, xsk.astring)
149 switch xsk.searchKey.op {
151 bodyNotWords = append(bodyNotWords, xsk.searchKey.astring)
154 textNotWords = append(textNotWords, xsk.searchKey.astring)
158 sk.searchKeys[n] = xsk
161 // We may be left with an empty but non-nil sk.searchKeys, which is important for
163 sk.searchKeys = sk.searchKeys[:n]
164 var bodySearch, textSearch *store.WordSearch
165 if len(bodyWords) > 0 || len(bodyNotWords) > 0 {
166 ws := store.PrepareWordSearch(bodyWords, bodyNotWords)
169 if len(textWords) > 0 || len(textNotWords) > 0 {
170 ws := store.PrepareWordSearch(textWords, textNotWords)
174 // Note: we only hold the account rlock for verifying the mailbox at the start.
176 runlock := c.account.RUnlock
177 // Note: in a defer because we replace it below.
182 // If we only have a MIN and/or MAX, we can stop processing as soon as we
183 // have those matches.
192 // We'll have one Result per mailbox we are searching. For regular (UID) SEARCH
193 // commands, we'll have just one, for the selected mailbox.
195 Mailbox store.Mailbox
196 MaxModSeq store.ModSeq
201 // We periodically send an untagged OK with INPROGRESS code while searching, to let
202 // clients doing slow searches know we're still working.
203 inProgressLast := time.Now()
204 // Only respond with tag if it can't be confused as end of response code.
../rfc/9585:122
205 inProgressTag := "nil"
206 if !strings.Contains(tag, "]") {
207 inProgressTag = dquote(tag).pack(c)
210 c.xdbread(func(tx *bstore.Tx) {
211 // Gather mailboxes to operate on. Usually just the selected mailbox. But with the
212 // ESEARCH command, we may be searching multiple.
213 var mailboxes []store.Mailbox
214 if len(mailboxSpecs) > 0 {
216 m := map[int64]store.Mailbox{}
217 for _, mbs := range mailboxSpecs {
221 if c.state != stateSelected {
222 xsyntaxErrorf("cannot use ESEARCH with selected when state is not selected")
225 mb := c.xmailboxID(tx, c.mailboxID) // Validate.
229 // Inbox and everything below. And we look at destinations and rulesets. We all
230 // mailboxes from the destinations, and all from the rulesets except when
231 // ListAllowDomain is non-empty.
233 q := bstore.QueryTx[store.Mailbox](tx)
234 q.FilterEqual("Expunged", false)
235 q.FilterGreaterEqual("Name", "Inbox")
237 for mb, err := range q.All() {
238 xcheckf(err, "list mailboxes")
239 if mb.Name != "Inbox" && !strings.HasPrefix(mb.Name, "Inbox/") {
245 conf, _ := c.account.Conf()
246 for _, dest := range conf.Destinations {
247 if dest.Mailbox != "" && dest.Mailbox != "Inbox" {
248 mb, err := c.account.MailboxFind(tx, dest.Mailbox)
249 xcheckf(err, "find mailbox from destination")
255 for _, rs := range dest.Rulesets {
256 if rs.ListAllowDomain != "" || rs.Mailbox == "" {
260 mb, err := c.account.MailboxFind(tx, rs.Mailbox)
261 xcheckf(err, "find mailbox from ruleset")
269 // All mailboxes in the personal namespace. Which is all mailboxes for us.
271 for mb, err := range bstore.QueryTx[store.Mailbox](tx).FilterEqual("Expunged", false).All() {
272 xcheckf(err, "list mailboxes")
277 // Mailboxes that are subscribed. Will typically be same as personal, since we
278 // subscribe to all mailboxes. But user can manage subscriptions differently.
280 for mb, err := range bstore.QueryTx[store.Mailbox](tx).FilterEqual("Expunged", false).All() {
281 xcheckf(err, "list mailboxes")
282 if err := tx.Get(&store.Subscription{Name: mb.Name}); err == nil {
284 } else if err != bstore.ErrAbsent {
285 xcheckf(err, "lookup subscription for mailbox")
289 case "SUBTREE", "SUBTREE-ONE":
291 // SUBTREE is arbitrarily deep, SUBTREE-ONE is one level deeper than requested
294 // We don't have to worry about loops. Mailboxes are not in the file system.
297 for _, name := range mbs.Args {
298 name = xcheckmailboxname(name, true)
300 one := mbs.Kind == "SUBTREE-ONE"
303 ntoken = len(strings.Split(name, "/"))
306 q := bstore.QueryTx[store.Mailbox](tx)
307 q.FilterEqual("Expunged", false)
308 q.FilterGreaterEqual("Name", name)
310 for mb, err := range q.All() {
311 xcheckf(err, "list mailboxes")
312 if mb.Name != name && !strings.HasPrefix(mb.Name, name+"/") {
315 if !one || mb.Name == name || len(strings.Split(mb.Name, "/")) == ntoken+1 {
323 for _, name := range mbs.Args {
324 name = xcheckmailboxname(name, true)
326 // If a mailbox doesn't exist, we don't treat it as an error. Seems reasonable
327 // giving we are searching. Messages may not exist. And likewise for the mailbox.
328 // Just results in no hits.
329 mb, err := c.account.MailboxFind(tx, name)
330 xcheckf(err, "looking up mailbox")
337 panic("missing case")
340 mailboxes = slices.Collect(maps.Values(m))
341 slices.SortFunc(mailboxes, func(a, b store.Mailbox) int {
342 return cmp.Compare(a.Name, b.Name)
345 // If no source mailboxes were specified (no mailboxSpecs), the selected mailbox is
348 mb := c.xmailboxID(tx, c.mailboxID) // Validate.
349 mailboxes = []store.Mailbox{mb}
352 if save && !(len(mailboxes) == 1 && mailboxes[0].ID == c.mailboxID) {
354 xsyntaxErrorf("can only use SAVE on selected mailbox")
360 // Determine if search has a sequence set without search results. If so, we need
361 // sequence numbers for matching, and we must always go through the messages in
362 // forward order. No reverse search for MAX only.
363 needSeq := (len(mailboxes) > 1 || len(mailboxes) == 1 && mailboxes[0].ID != c.mailboxID) && sk.needSeq()
365 forward := eargs == nil || max1 == 0 || len(eargs) != 1 || needSeq
366 reverse := max1 == 1 && (len(eargs) == 1 || min1+max1 == len(eargs)) && !needSeq
368 // We set a worst-case "goal" of having gone through all messages in all mailboxes.
369 // Sometimes, we can be faster, when we only do a MIN and/or MAX query and we can
370 // stop early. We'll account for that as we go. For the selected mailbox, we'll
371 // only look at those the session has already seen.
374 for _, mb := range mailboxes {
375 if mb.ID == c.mailboxID {
376 total += uint32(len(c.uids))
378 total += uint32(mb.Total + mb.Deleted)
383 goal = fmt.Sprintf("%d", total)
387 for _, mb := range mailboxes {
388 var lastUID store.UID
390 result := Result{Mailbox: mb}
392 msgCount := uint32(mb.MailboxCounts.Total + mb.MailboxCounts.Deleted)
393 if mb.ID == c.mailboxID {
394 msgCount = uint32(len(c.uids))
397 // Used for interpreting UID sets with a star, like "1:*" and "10:*". Only called
398 // for UIDs that are higher than the number, since "10:*" evaluates to "10:5" if 5
399 // is the highest UID, and UID 5-10 would all match.
400 var cachedHighestUID store.UID
401 highestUID := func() (store.UID, error) {
402 if cachedHighestUID > 0 {
403 return cachedHighestUID, nil
406 q := bstore.QueryTx[store.Message](tx)
407 q.FilterNonzero(store.Message{MailboxID: mb.ID})
408 q.FilterEqual("Expunged", false)
412 cachedHighestUID = m.UID
413 return cachedHighestUID, err
416 progressOrig := progress
419 // We track this for non-selected mailboxes. searchMatch will look the message
420 // sequence number for this session up if we are searching the selected mailbox.
423 q := bstore.QueryTx[store.Message](tx)
424 q.FilterNonzero(store.Message{MailboxID: mb.ID})
425 q.FilterEqual("Expunged", false)
427 for m, err := range q.All() {
428 xcheckf(err, "list messages in mailbox")
430 // We track this for the "reverse" case, we'll stop before seeing lastUID.
433 if time.Since(inProgressLast) > inProgressPeriod {
434 c.xwritelinef("* OK [INPROGRESS (%s %d %s)] still searching", inProgressTag, progress, goal)
435 inProgressLast = time.Now()
439 if c.searchMatch(tx, msgCount, seq, m, *sk, bodySearch, textSearch, highestUID) {
440 result.UIDs = append(result.UIDs, m.UID)
441 result.MaxModSeq = max(result.MaxModSeq, m.ModSeq)
442 if min1 == 1 && min1+max1 == len(eargs) {
446 // We only need a MIN and a MAX, but we also need sequence numbers so we are
447 // walking through and collecting all UIDs. Correct for that, keeping only the MIN
450 if len(result.UIDs) == 3 {
451 result.UIDs[1] = result.UIDs[2]
452 result.UIDs = result.UIDs[:2]
459 // And reverse search for MAX if we have only MAX or MAX combined with MIN, and
460 // don't need sequence numbers. We just need a single match, then we stop.
462 q := bstore.QueryTx[store.Message](tx)
463 q.FilterNonzero(store.Message{MailboxID: mb.ID})
464 q.FilterEqual("Expunged", false)
465 q.FilterGreater("UID", lastUID)
467 for m, err := range q.All() {
468 xcheckf(err, "list messages in mailbox")
470 if time.Since(inProgressLast) > inProgressPeriod {
471 c.xwritelinef("* OK [INPROGRESS (%s %d %s)] still searching", inProgressTag, progress, goal)
472 inProgressLast = time.Now()
476 var seq msgseq // Filled in by searchMatch for messages in selected mailbox.
477 if c.searchMatch(tx, msgCount, seq, m, *sk, bodySearch, textSearch, highestUID) {
478 result.UIDs = append(result.UIDs, m.UID)
479 result.MaxModSeq = max(result.MaxModSeq, m.ModSeq)
485 // We could have finished searching the mailbox with fewer
486 mailboxProcessed := progress - progressOrig
487 mailboxTotal := uint32(mb.MailboxCounts.Total + mb.MailboxCounts.Deleted)
488 progress += max(0, mailboxTotal-mailboxProcessed)
490 results = append(results, result)
495 // We'll only have a result for the one selected mailbox.
499 if len(result.UIDs) == 0 {
500 c.xbwritelinef("* SEARCH")
503 // Old-style SEARCH response. We must spell out each number. So we may be splitting
505 for len(result.UIDs) > 0 {
506 n := len(result.UIDs)
511 for _, v := range result.UIDs[:n] {
513 v = store.UID(c.xsequence(v))
515 s += " " + fmt.Sprintf("%d", v)
518 // Since we don't have the max modseq for the possibly partial uid range we're
519 // writing here within hand reach, we conveniently interpret the ambiguous "for all
521 // write. And that clients only commit this value after they have seen the tagged
527 modseq = fmt.Sprintf(" (MODSEQ %d)", result.MaxModSeq.Client())
530 c.xbwritelinef("* SEARCH%s%s", s, modseq)
531 result.UIDs = result.UIDs[n:]
538 c.searchResult = results[0].UIDs
540 checkUIDs(c.searchResult)
546 for _, result := range results {
547 // For the ESEARCH command, we must not return a response if there were no matching
548 // messages. This is unlike the later IMAP4rev2, where an ESEARCH response must be
550 if isE && len(result.UIDs) == 0 {
554 // The tag was originally a string, became an astring in IMAP4rev2, better stick to
557 fmt.Fprintf(c.xbw, `* ESEARCH (TAG "%s" MAILBOX %s UIDVALIDITY %d)`, tag, result.Mailbox.Name, result.Mailbox.UIDValidity)
559 fmt.Fprintf(c.xbw, `* ESEARCH (TAG "%s")`, tag)
562 fmt.Fprintf(c.xbw, " UID")
565 // NOTE: we are potentially converting UIDs to msgseq, but keep the store.UID type
569 // If searchResult is hanging on to the slice, we need to work on a copy.
571 nums = slices.Clone(nums)
573 for i, uid := range nums {
574 nums[i] = store.UID(c.xsequence(uid))
579 if eargs["MIN"] && len(nums) > 0 {
580 fmt.Fprintf(c.xbw, " MIN %d", nums[0])
582 if eargs["MAX"] && len(result.UIDs) > 0 {
583 fmt.Fprintf(c.xbw, " MAX %d", nums[len(nums)-1])
586 fmt.Fprintf(c.xbw, " COUNT %d", len(nums))
588 if eargs["ALL"] && len(nums) > 0 {
589 fmt.Fprintf(c.xbw, " ALL %s", compactUIDSet(nums).String())
593 // Summary: send the highest modseq of the returned messages.
594 if sk.hasModseq() && len(nums) > 0 {
595 fmt.Fprintf(c.xbw, " MODSEQ %d", result.MaxModSeq.Client())
609 msgCount uint32 // Number of messages in mailbox (or session when selected).
610 seq msgseq // Can be 0, for other mailboxes than selected in case of MAX.
614 highestUID func() (store.UID, error)
617func (c *conn) searchMatch(tx *bstore.Tx, msgCount uint32, seq msgseq, m store.Message, sk searchKey, bodySearch, textSearch *store.WordSearch, highestUID func() (store.UID, error)) bool {
618 if m.MailboxID == c.mailboxID {
619 seq = c.sequence(m.UID)
621 // Session has not yet seen this message, and is not expecting to get a result that
627 s := search{c: c, tx: tx, msgCount: msgCount, seq: seq, m: m, highestUID: highestUID}
631 c.xsanity(err, "closing messagereader")
635 return s.match(sk, bodySearch, textSearch)
638func (s *search) match(sk searchKey, bodySearch, textSearch *store.WordSearch) (match bool) {
640 if match && bodySearch != nil {
641 if !s.xensurePart() {
646 match, err = bodySearch.MatchPart(s.c.log, s.p, false)
647 xcheckf(err, "search words in bodies")
649 if match && textSearch != nil {
650 if !s.xensurePart() {
655 match, err = textSearch.MatchPart(s.c.log, s.p, true)
656 xcheckf(err, "search words in headers and bodies")
661// ensure message, reader and part are loaded. returns whether that was
663func (s *search) xensurePart() bool {
668 // Closed by searchMatch after all (recursive) search.match calls are finished.
669 s.mr = s.c.account.MessageReader(s.m)
671 if s.m.ParsedBuf == nil {
672 s.c.log.Error("missing parsed message")
675 p, err := s.m.LoadPart(s.mr)
676 xcheckf(err, "load parsed message")
681func (s *search) match0(sk searchKey) bool {
684 // Difference between sk.searchKeys nil and length 0 is important. Because we take
685 // out word/notword searches, the list may be empty but non-nil.
686 if sk.searchKeys != nil {
687 for _, ssk := range sk.searchKeys {
693 } else if sk.seqSet != nil {
694 if sk.seqSet.searchResult {
695 // Interpreting search results on a mailbox that isn't selected during multisearch
697 if s.m.MailboxID != c.mailboxID {
698 xuserErrorf("can only use search result with the selected mailbox")
700 return uidSearch(c.searchResult, s.m.UID) > 0
702 // For multisearch, we have arranged to have a seq for non-selected mailboxes too.
703 return sk.seqSet.containsSeqCount(s.seq, s.msgCount)
706 filterHeader := func(field, value string) bool {
707 lower := strings.ToLower(value)
708 h, err := s.p.Header()
710 c.log.Debugx("parsing message header", err, slog.Any("uid", s.m.UID), slog.Int64("msgid", s.m.ID))
713 for _, v := range h.Values(field) {
714 if strings.Contains(strings.ToLower(v), lower) {
721 // We handle ops by groups that need increasing details about the message.
727 // We do not implement the RECENT flag, so messages cannot be NEW.
730 // We treat all messages as non-recent, so this means all messages.
733 // We do not implement the RECENT flag. All messages are not recent.
736 return !s.match0(*sk.searchKey)
738 return s.match0(*sk.searchKey) || s.match0(*sk.searchKey2)
740 if sk.uidSet.searchResult && s.m.MailboxID != c.mailboxID {
741 // Interpreting search results on a mailbox that isn't selected during multisearch
743 xuserErrorf("cannot use search result from another mailbox")
745 match, err := sk.uidSet.containsKnownUID(s.m.UID, c.searchResult, s.highestUID)
746 xcheckf(err, "checking for presence in uid set")
751 if !s.xensurePart() {
755 // Parsed message, basic info.
764 kw := strings.ToLower(sk.atom)
777 return slices.Contains(s.m.Keywords, kw)
788 kw := strings.ToLower(sk.atom)
791 return !s.m.Forwarded
801 return !slices.Contains(s.m.Keywords, kw)
809 case "BEFORE", "ON", "SINCE":
810 skdt := sk.date.Format("2006-01-02")
811 rdt := s.m.Received.Format("2006-01-02")
820 panic("missing case")
822 return s.m.Size > sk.number
824 return s.m.Size < sk.number
827 return s.m.ModSeq.Client() >= *sk.clientModseq
828 case "SAVEDBEFORE", "SAVEDON", "SAVEDSINCE":
829 // If we don't have a savedate for this message (for messages received before we
830 // implemented this feature), we use the "internal date" (received timestamp) of
833 if s.m.SaveDate != nil {
837 skdt := sk.date.Format("2006-01-02")
838 rdt := rt.Format("2006-01-02")
847 panic("missing case")
848 case "SAVEDATESUPPORTED":
849 // We return whether we have a savedate for this message. We support it on all
850 // mailboxes, but we only have this metadata from the time we implemented this
852 return s.m.SaveDate != nil
855 seconds := int64(time.Since(s.m.Received) / time.Second)
856 return seconds >= sk.number
858 seconds := int64(time.Since(s.m.Received) / time.Second)
859 return seconds <= sk.number
863 c.log.Info("missing parsed message, not matching", slog.Any("uid", s.m.UID), slog.Int64("msgid", s.m.ID))
867 // Parsed message, more info.
870 return filterHeader("Bcc", sk.astring)
872 // We gathered word/notword searches from the top-level, but we can also get them
874 // todo optimize: handle deeper nested word/not-word searches more efficiently.
875 headerToo := sk.op == "TEXT"
876 match, err := store.PrepareWordSearch([]string{sk.astring}, nil).MatchPart(s.c.log, s.p, headerToo)
877 xcheckf(err, "word search")
880 return filterHeader("Cc", sk.astring)
882 return filterHeader("From", sk.astring)
884 return filterHeader("Subject", sk.astring)
886 return filterHeader("To", sk.astring)
889 lower := strings.ToLower(sk.astring)
890 h, err := s.p.Header()
892 c.log.Errorx("parsing header for search", err, slog.Any("uid", s.m.UID), slog.Int64("msgid", s.m.ID))
895 k := textproto.CanonicalMIMEHeaderKey(sk.headerField)
896 for _, v := range h.Values(k) {
897 if lower == "" || strings.Contains(strings.ToLower(v), lower) {
902 case "SENTBEFORE", "SENTON", "SENTSINCE":
903 if s.p.Envelope == nil || s.p.Envelope.Date.IsZero() {
906 dt := s.p.Envelope.Date.Format("2006-01-02")
907 skdt := sk.date.Format("2006-01-02")
916 panic("missing case")
918 panic(serverError{fmt.Errorf("missing case for search key op %q", sk.op)})