comply with the THRID draft instead of using arnt's gmail hack
[aox:aox.git] / imap / handlers / search.cpp
1 // Copyright 2009 The Archiveopteryx Developers <info@aox.org>
2
3 #include "search.h"
4
5 #include "imapsession.h"
6 #include "imapparser.h"
7 #include "annotation.h"
8 #include "integerset.h"
9 #include "listext.h"
10 #include "mailbox.h"
11 #include "message.h"
12 #include "codec.h"
13 #include "query.h"
14 #include "date.h"
15 #include "imap.h"
16 #include "list.h"
17 #include "log.h"
18 #include "utf.h"
19
20
21 static const char * legalAnnotationAttributes[] = {
22     "value",
23     "value.priv",
24     "value.shared",
25     0
26 };
27
28
29 class SearchData
30     : public Garbage
31 {
32 public:
33     SearchData()
34         : uid( false ), done( false ), codec( 0 ), root( 0 ),
35           query( 0 ), highestmodseq( 1 ),
36           firstmodseq( 1 ), lastmodseq( 1 ),
37           returnModseq( false ),
38           returnAll( false ), returnCount( false ),
39           returnMax( false ), returnMin( false )
40     {}
41
42     bool uid;
43     bool done;
44
45     EString charset;
46     Codec * codec;
47
48     Selector * root;
49
50     Query * query;
51     IntegerSet matches;
52     int64 highestmodseq;
53     int64 firstmodseq;
54     int64 lastmodseq;
55     bool returnModseq;
56
57     bool returnAll;
58     bool returnCount;
59     bool returnMax;
60     bool returnMin;
61 };
62
63
64 /*! \class Search search.h
65     Finds messages matching some criteria (RFC 3501 section 6.4.4)
66
67     The entirety of the basic syntax is handled, as well as ESEARCH
68     (RFC 4731 and RFC 4466), of CONDSTORE (RFC 4551), ANNOTATE (RFC
69     5257) and WITHIN (RFC 5032).
70
71     Searches are first run against the RAM cache, rudimentarily. If
72     the comparison is difficult, expensive or unsuccessful, it gives
73     up and uses the database.
74
75     If ESEARCH with only MIN, only MAX or only COUNT is used, we could
76     generate better SQL than we do. Let's do that optimisation when a
77     client benefits from it.
78 */
79
80
81 /*! Constructs an empty Search. If \a u is true, it's a UID SEARCH,
82     otherwise it's the MSN variety.
83 */
84
85 Search::Search( bool u )
86     : d( new SearchData )
87 {
88     d->uid = u;
89     if ( u )
90         setGroup( 1 );
91     else
92         setGroup( 2 );
93
94     d->root = new Selector;
95 }
96
97
98 void Search::parse()
99 {
100     space();
101     if ( present( "return" ) ) {
102         // RFC 4731 and RFC 4466 define ESEARCH together.
103         space();
104         require( "(" );
105         bool any = false;
106         while ( ok() && nextChar() != ')' &&
107                 nextChar() >= 'A' && nextChar() <= 'z' ) {
108             EString modifier = letters( 3, 5 ).lower();
109             any = true;
110             if ( modifier == "all" )
111                 d->returnAll = true;
112             else if ( modifier == "min" )
113                 d->returnMin = true;
114             else if ( modifier == "max" )
115                 d->returnMax = true;
116             else if ( modifier == "count" )
117                 d->returnCount = true;
118             else
119                 error( Bad, "Unknown search modifier option: " + modifier );
120             if ( nextChar() != ')' )
121                 space();
122         }
123         require( ")" );
124         if ( !any )
125             d->returnAll = true;
126         space();
127     }
128     if ( present ( "charset" ) ) {
129         space();
130         setCharset( astring() );
131         space();
132     }
133     d->root = new Selector;
134     d->root->add( parseKey() );
135     while ( ok() && !parser()->atEnd() ) {
136         space();
137         d->root->add( parseKey() );
138     }
139     end();
140
141     d->returnModseq = d->root->usesModseq();
142     d->root->simplify();
143     log( "Search for " + d->root->debugString() );
144 }
145
146
147 /*! Parse one search key (IMAP search-key) and returns a pointer to
148     the corresponding Selector. Leaves the cursor on the first
149     character following the search-key.
150 */
151
152 Selector * Search::parseKey()
153 {
154     char c = nextChar();
155     if ( c == '(' ) {
156         step();
157         // it's an "and" list.
158         Selector * s = new Selector( Selector::And );
159         s->add( parseKey() );
160         while ( ok() && !present( ")" ) ) {
161             space();
162             s->add( parseKey() );
163         }
164         return s;
165     }
166     else if ( c == '*' || ( c >= '0' && c <= '9' ) ) {
167         // it's a pure set
168         return new Selector( set( true ) );
169     }
170     else if ( present( "older" ) ) {
171         space();
172         return new Selector( Selector::Age, Selector::Larger, nzNumber() );
173     }
174     else if ( present( "younger" ) ) {
175         space();
176         return new Selector( Selector::Age, Selector::Smaller, nzNumber() );
177     }
178     else if ( present( "all" ) ) {
179         return new Selector( Selector::NoField, Selector::All );
180     }
181     else if ( present( "answered" ) ) {
182         return new Selector( Selector::Flags, Selector::Contains,
183                              "\\answered" );
184     }
185     else if ( present( "deleted" ) ) {
186         return new Selector( Selector::Flags, Selector::Contains,
187                              "\\deleted" );
188     }
189     else if ( present( "flagged" ) ) {
190         return new Selector( Selector::Flags, Selector::Contains,
191                              "\\flagged" );
192     }
193     else if ( present( "new" ) ) {
194         Selector * s = new Selector( Selector::And );
195         s->add( new Selector( Selector::Flags, Selector::Contains,
196                               "\\recent" ) );
197         Selector * n = new Selector( Selector::Not );
198         s->add( n );
199         n->add( new Selector( Selector::Flags, Selector::Contains,
200                               "\\seen" ) );
201         return s;
202     }
203     else if ( present( "old" ) ) {
204         Selector * s = new Selector( Selector::Not );
205         s->add( new Selector( Selector::Flags, Selector::Contains,
206                               "\\recent" ) );
207         return s;
208     }
209     else if ( present( "recent" ) ) {
210         return new Selector( Selector::Flags, Selector::Contains,
211                              "\\recent" );
212     }
213     else if ( present( "seen" ) ) {
214         return new Selector( Selector::Flags, Selector::Contains,
215                              "\\seen" );
216     }
217     else if ( present( "unanswered" ) ) {
218         Selector * s = new Selector( Selector::Not );
219         s->add(new Selector( Selector::Flags, Selector::Contains,
220                              "\\answered" ) );
221         return s;
222     }
223     else if ( present( "undeleted" ) ) {
224         Selector * s = new Selector( Selector::Not );
225         s->add( new Selector( Selector::Flags, Selector::Contains,
226                               "\\deleted" ) );
227         return s;
228     }
229     else if ( present( "unflagged" ) ) {
230         Selector * s = new Selector( Selector::Not );
231         s->add( new Selector( Selector::Flags, Selector::Contains,
232                               "\\flagged" ) );
233         return s;
234     }
235     else if ( present( "unseen" ) ) {
236         Selector * s = new Selector( Selector::Not );
237         s->add( new Selector( Selector::Flags, Selector::Contains,
238                               "\\seen" ) );
239         return s;
240     }
241     else if ( present( "draft" ) ) {
242         return new Selector( Selector::Flags, Selector::Contains,
243                              "\\draft" );
244     }
245     else if ( present( "undraft" ) ) {
246         Selector * s = new Selector( Selector::Not );
247         s->add( new Selector( Selector::Flags, Selector::Contains,
248                               "\\draft" ) );
249         return s;
250     }
251     else if ( present( "on" ) ) {
252         space();
253         return new Selector( Selector::InternalDate, Selector::OnDate,
254                              date() );
255     }
256     else if ( present( "before" ) ) {
257         space();
258         return new Selector( Selector::InternalDate, Selector::BeforeDate,
259                              date() );
260     }
261     else if ( present( "since" ) ) {
262         space();
263         return new Selector( Selector::InternalDate, Selector::SinceDate,
264                              date() );
265     }
266     else if ( present( "sentbefore" ) ) {
267         space();
268         return new Selector( Selector::Sent, Selector::BeforeDate, date() );
269     }
270     else if ( present( "senton" ) ) {
271         space();
272         return new Selector( Selector::Sent, Selector::OnDate, date() );
273     }
274     else if ( present( "sentsince" ) ) {
275         space();
276         return new Selector( Selector::Sent, Selector::SinceDate, date() );
277     }
278     else if ( present( "from" ) ) {
279         space();
280         return new Selector( Selector::Header, Selector::Contains,
281                              "from", ustring( AString ) );
282     }
283     else if ( present( "to" ) ) {
284         space();
285         return new Selector( Selector::Header, Selector::Contains,
286                              "to", ustring( AString ) );
287     }
288     else if ( present( "cc" ) ) {
289         space();
290         return new Selector( Selector::Header, Selector::Contains,
291                              "cc", ustring( AString ) );
292     }
293     else if ( present( "bcc" ) ) {
294         space();
295         return new Selector( Selector::Header, Selector::Contains,
296                              "bcc", ustring( AString ) );
297     }
298     else if ( present( "subject" ) ) {
299         space();
300         return new Selector( Selector::Header, Selector::Contains,
301                              "subject", ustring( AString ) );
302     }
303     else if ( present( "body" ) ) {
304         space();
305         return new Selector( Selector::Body, Selector::Contains,
306                              ustring( AString ) );
307     }
308     else if ( present( "text" ) ) {
309         space();
310         UString a = ustring( AString );
311         Selector * o = new Selector( Selector::Or );
312         o->add( new Selector( Selector::Body, Selector::Contains, a ) );
313         // field name is null for any-field searches
314         o->add( new Selector( Selector::Header, Selector::Contains, 0, a ) );
315         return o;
316     }
317     else if ( present( "keyword" ) ) {
318         space();
319         return new Selector( Selector::Flags, Selector::Contains,
320                              atom().lower() );
321     }
322     else if ( present( "unkeyword" ) ) {
323         space();
324         Selector * s = new Selector( Selector::Not );
325         s->add( new Selector( Selector::Flags, Selector::Contains, atom() ) );
326         return s;
327     }
328     else if ( present( "header" ) ) {
329         space();
330         EString s1 = astring();
331         space();
332         UString s2 = ustring( AString );
333         return new Selector( Selector::Header, Selector::Contains, s1, s2 );
334     }
335     else if ( present( "uid" ) ) {
336         space();
337         return new Selector( set( false ) );
338     }
339     else if ( present( "or" ) ) {
340         space();
341         Selector * s = new Selector( Selector::Or );
342         s->add( parseKey() );
343         space();
344         s->add( parseKey() );
345         return s;
346     }
347     else if ( present( "not" ) ) {
348         space();
349         Selector * s = new Selector( Selector::Not );
350         s->add( parseKey() );
351         return s;
352     }
353     else if ( present( "larger" ) ) {
354         space();
355         return new Selector( Selector::Rfc822Size, Selector::Larger,
356                              number() );
357     }
358     else if ( present( "smaller" ) ) {
359         space();
360         return new Selector( Selector::Rfc822Size, Selector::Smaller,
361                              number() );
362     }
363     else if ( present( "msgid" ) ) {
364         space();
365         return new Selector( Selector::DatabaseId, Selector::Equals,
366                              number() );
367     }
368     else if ( present( "thrid" ) ) {
369         space();
370         return new Selector( Selector::ThreadId, Selector::Equals,
371                              number() );
372     }
373     else if ( present( "annotation" ) ) {
374         space();
375         EString a = parser()->listMailbox();
376         if ( !parser()->ok() )
377             error( Bad, parser()->error() );
378         space();
379         EString b = atom();
380         space();
381         UString c = ustring( NString );
382
383         uint i = 0;
384         while ( ::legalAnnotationAttributes[i] &&
385                 b != ::legalAnnotationAttributes[i] )
386             i++;
387         if ( !::legalAnnotationAttributes[i] )
388             error( Bad, "Unknown annotation attribute: " + b );
389
390         return new Selector( Selector::Annotation, Selector::Contains,
391                              a, b, c );
392     }
393     else if ( present( "modseq" ) ) {
394         space();
395         if ( nextChar() == '"' ) {
396             // we don't store per-flag or per-annotation modseqs,
397             // so RFC 4551 3.4 says we MUST ignore these
398             (void)quoted(); // flag or annotation name
399             space();
400             (void)letters( 3, 6 ); // priv/shared/all
401             space();
402         }
403         return new Selector( Selector::Modseq, Selector::Larger,
404                              number() );
405     }
406     else if ( present( "inthread" ) ) {
407         space();
408         Selector * s = new Selector( Selector::InThread );
409         s->add( parseKey() );
410         return s;
411     }
412
413     error( Bad, "expected search key, saw: " + following() );
414     return new Selector;
415 }
416
417
418 void Search::execute()
419 {
420     if ( state() != Executing )
421         return;
422
423     if ( d->query &&
424          ( d->query->state() == Query::Submitted ||
425            d->query->state() == Query::Executing ) ) {
426         if ( imap()->Connection::state() != Connection::Connected ) {
427             Database::cancelQuery( d->query );
428             error( No, "Client disconnected" );
429             return;
430         }
431         else if ( imap()->state() == IMAP::Logout ) {
432             Database::cancelQuery( d->query );
433             error( No, "Client logged out" );
434             return;
435         }
436     }
437
438     ImapSession * s = session();
439
440     if ( !d->query ) {
441         considerCache();
442         if ( d->done ) {
443             sendResponse();
444             finish();
445             return;
446         }
447
448         d->query = d->root->query( imap()->user(), s->mailbox(),
449                                    s, this, false );
450         d->query->execute();
451     }
452
453     if ( !d->query->done() )
454         return;
455
456     if ( d->query->failed() ) {
457         error( No, "Database error: " + d->query->error() );
458         return;
459     }
460
461     bool firstRow = true;
462     Row * r;
463     while ( (r=d->query->nextRow()) != 0 ) {
464         d->matches.add( r->getInt( "uid" ) );
465         if ( d->returnModseq ) {
466             int64 ms = r->getBigint( "modseq" );
467             if ( firstRow )
468                 d->firstmodseq = ms;
469             d->lastmodseq = ms;
470             firstRow = false;
471             if ( ms > d->highestmodseq )
472                 d->highestmodseq = ms;
473         }
474     }
475
476     sendResponse();
477     finish();
478 }
479
480
481 /*! Considers whether this search can and should be solved using this
482     cache, and if so, finds all the matches.
483 */
484
485 void Search::considerCache()
486 {
487     if ( d->returnModseq )
488         return;
489     Session * s = imap()->session();
490     bool needDb = false;
491     if ( !s ) {
492         needDb = true;
493     }
494     else if ( d->root->field() == Selector::Uid &&
495               d->root->action() == Selector::Contains ) {
496         d->matches = s->messages().intersection( d->root->messageSet() );
497         log( "UID-only search matched " +
498              fn( d->matches.count() ) + " messages",
499              Log::Debug );
500     }
501     else {
502         uint max = s->count();
503          // don't consider more than 300 messages - pg does it better
504         if ( max > 300 )
505             needDb = true;
506         uint c = 0;
507         while ( c < max && !needDb ) {
508             c++;
509             uint uid = s->uid( c );
510             switch ( d->root->match( s, uid ) ) {
511             case Selector::Yes:
512                 d->matches.add( uid );
513                 break;
514             case Selector::No:
515                 break;
516             case Selector::Punt:
517                 log( "Search must go to database: message " + fn( uid ) +
518                      " could not be tested in RAM",
519                      Log::Debug );
520                 needDb = true;
521                 d->matches.clear();
522                 break;
523             }
524         }
525         log( "Search considered " + fn( c ) + " of " + fn( max ) +
526              " messages using cache", Log::Debug );
527     }
528     if ( !needDb )
529         d->done = true;
530 }
531
532
533
534 /*! Parses the IMAP date production and returns the string (sans
535     quotes). Month names are case-insensitive; RFC 3501 is not
536     entirely clear about that. */
537
538 EString Search::date()
539 {
540     // date-day "-" date-month "-" date-year
541     char c = nextChar();
542     bool q = false;
543     if ( c == '"' ) {
544         step();
545         q = true;
546         c = nextChar();
547     }
548     EString result;
549     result.append( digits( 1, 2 ) );
550     if ( nextChar() != '-' )
551         error( Bad, "expected -, saw " + following() );
552     uint day = result.number( 0 );
553     if ( result.length() < 2 )
554         result = "0" + result;
555     result.append( "-" );
556     step();
557     EString month = letters( 3, 3 ).lower();
558     if ( month == "jan" || month == "feb" || month == "mar" ||
559          month == "apr" || month == "may" || month == "jun" ||
560          month == "jul" || month == "aug" || month == "sep" ||
561          month == "oct" || month == "nov" || month == "dec" )
562         result.append( month );
563     else
564         error( Bad, "Expected three-letter month name, received " + month );
565     if ( nextChar() != '-' )
566         error( Bad, "expected -, saw " + following() );
567     result.append( "-" );
568     step();
569     uint year = digits( 4, 4 ).number( 0 );
570     if ( year < 1500 )
571         error( Bad, "Years before 1500 not supported" );
572     result.append( EString::fromNumber( year ) );
573     if ( q ) {
574         if ( nextChar() != '"' )
575             error( Bad, "Expected \", saw " + following() );
576         else
577             step();
578     }
579     Date tmp;
580     tmp.setDate( year, month, day, 0, 0, 0, 0 );
581     if ( !tmp.valid() )
582         error( Bad, "Invalid date: " + result );
583     return result;
584 }
585
586
587 /*! Reads an argument of type \a stringType (which may be AString,
588     NString, or PlainString) and returns it as unicode, using the
589     charset specified in the CHARSET argument to SEARCH.
590 */
591
592 UString Search::ustring( Command::QuoteMode stringType )
593 {
594     if ( d->codec )
595         ;
596     else if ( imap()->clientSupports( IMAP::Unicode ) )
597         d->codec = new Utf8Codec;
598     else if ( !d->codec )
599         d->codec = new AsciiCodec;
600
601     EString raw;
602     switch( stringType )
603     {
604     case AString:
605         raw = astring();
606         break;
607     case NString:
608         raw = nstring();
609         break;
610     case PlainString:
611         raw = string();
612         break;
613     }
614     UString canon = d->codec->toUnicode( raw );
615     if ( !d->codec->valid() )
616         error( Bad,
617                "astring not valid under encoding " + d->codec->name() +
618                ": " + raw );
619     return canon;
620 }
621
622
623 /*! This helper function is called by the parser to set the CHARSET for
624     this search to \a s.
625 */
626
627 void Search::setCharset( const EString &s )
628 {
629     d->charset = s;
630     d->codec = Codec::byName( d->charset );
631     if ( d->codec )
632         return;
633
634     EString r = "[BADCHARSET";
635     EStringList::Iterator i( Codec::allCodecNames() );
636     while ( i ) {
637         r.append( " " );
638         r.append( imapQuoted( *i, AString ) );
639         ++i;
640     }
641     r.append( "] Unknown character encoding: " );
642     r.append( d->charset.simplified() );
643
644     error( No, r );
645 }
646
647
648 /*! Returns the root Selector constructed while parsing this Search
649     command.
650 */
651
652 Selector * Search::selector() const
653 {
654     return d->root;
655 }
656
657
658 /*! This reimplementation of Command::set() simplifies the set by
659     including messages that don't exist. \a parseMsns is as for
660     Command::set().
661 */
662
663 IntegerSet Search::set( bool parseMsns )
664 {
665     IntegerSet s( Command::set( parseMsns ) );
666     return s;
667 }
668
669
670 static uint max( uint a, uint b )
671 {
672     if ( a > b )
673         return a;
674     return b;
675 }
676
677
678 /*! Makes sure a SEARCH or ESEARCH response is sent, whichever is
679     appropriate.
680 */
681
682 void Search::sendResponse()
683 {
684     int64 ms = d->highestmodseq;
685     if ( !d->returnModseq )
686         ms = 0; // means to send none
687     else if ( d->returnAll || d->returnCount )
688         ms = d->highestmodseq;
689     else if ( d->returnMin && d->returnMax )
690         ms = max( d->firstmodseq, d->lastmodseq );
691     else if ( d->returnMin )
692         ms = d->firstmodseq;
693     else if ( d->returnMax )
694         ms = d->lastmodseq;
695     waitFor( new ImapSearchResponse( session(), d->matches, ms, tag(),
696                                      d->uid,
697                                      d->returnMin,
698                                      d->returnMax,
699                                      d->returnCount,
700                                      d->returnAll ) );
701 }
702
703
704 /*! \class ImapSearchResponse search.h
705
706     The ImapSearchResponse models the SEARCH and ESEARCH responses. It
707     is responsible for sending the right one, and for using only
708     correct MSNs.
709 */
710
711
712
713 /*! Constructs a search response, able to send a SEARCH or ESEARCH
714     response for \a set within \a session.
715
716     If \a u is true, UIDs will be sent, if not, MSNs. If a modseq
717     needs to be sent, \a modseq will be. If the response is ESEARCH,
718     then \a tag will be included as command tag.
719
720     The \a rmin, \a rmax, \a rcount and \a rall response modifiers
721     correspond to the four result options in RFC 4731.
722 */
723
724 ImapSearchResponse::ImapSearchResponse( ImapSession * session,
725                                         const IntegerSet & set, int64 modseq,
726                                         const EString & tag,
727                                         bool u,
728                                         bool rmin, bool rmax,
729                                         bool rcount, bool rall )
730     : ImapResponse( session ), r( set ), ms( modseq ), t( tag ),
731       uid( u ), min( rmin ), max( rmax ), count( rcount ), all( rall )
732 {
733 }
734
735
736 static void appendUid( EString & r, Session * s, bool u, uint uid )
737 {
738     if ( u ) {
739         r.appendNumber( uid );
740     }
741     else {
742         uint m = s->msn( uid );
743         if ( m )
744             r.appendNumber( m );
745     }
746 }
747
748
749 /*! Constructs a SEARCH or ESEARCH response depending on. */
750
751 EString ImapSearchResponse::text() const
752 {
753     Session * s = session();
754     EString result;
755     result.reserve( r.count() * 10 );
756     if ( all || max || min || count ) {
757         result.append( "ESEARCH (tag " );
758         result.append( t.quoted() );
759         result.append( ")" );
760         if ( uid )
761             result.append( " uid" );
762         if ( count ) {
763             result.append( " count " );
764             result.appendNumber( r.count() );
765         }
766         if ( r.isEmpty() )
767             return result;
768
769         if ( min ) {
770             result.append( " min " );
771             appendUid( result, s, uid, r.smallest() );
772         }
773         if ( max ) {
774             result.append( " max " );
775             appendUid( result, s, uid, r.largest() );
776         }
777         if ( all ) {
778             result.append( " all " );
779             if ( uid ) {
780                 result.append( r.set() );
781             }
782             else {
783                 IntegerSet msns;
784                 uint i = 1;
785                 uint max = r.count();
786                 while ( i <= max ) {
787                     uint m = s->msn( r.value( i ) );
788                     if ( m )
789                         msns.add( m );
790                     i++;
791                 }
792                 result.append( msns.set() );
793             }
794         }
795         if ( ms ) {
796             result.append( " modseq " );
797             result.appendNumber( ms );
798         }
799     }
800     else {
801         result.reserve( r.count() * 10 );
802         result.append( "SEARCH" );
803         uint i = 1;
804         uint max = r.count();
805         while ( i <= max ) {
806             result.append( " " );
807             appendUid( result, s, uid, r.value( i ) );
808             i++;
809         }
810         if ( ms ) {
811             result.append( " (modseq " );
812             result.appendNumber( ms );
813             result.append( ")" );
814         }
815     }
816     return result;
817 }