imap: *SEARCH: use Parse::RecDescent

For properly parsing IMAP search requests, it's easier to use a
recursive descent parser generator to deal with subqueries and
the "OR" statement.

Parse::RecDescent was chosen since it's mature, well-known,
widely available and already used by our optional dependencies:
Inline::C and Mail::IMAPClient.  While it's possible to build
Xapian queries without using the Xapian string query parser;
this iteration of the IMAP parser still builds a string which is
passed to Xapian's query parser for ease-of-diagnostics.

Since this is a recursive descent parser dealing with untrusted
inputs, subqueries have a nesting limit of 10.  I expect that is
more than adequate for real-world use.

2 files changed, 292 insertions, 85 deletions

diff --git a/lib/PublicInbox/IMAP.pm b/lib/PublicInbox/IMAP.pm
index 4631ea7e..dd983dfd 100644
--- a/lib/PublicInbox/IMAP.pm
+++ b/lib/PublicInbox/IMAP.pm
@@ -34,10 +34,9 @@ use PublicInbox::Syscall qw(EPOLLIN EPOLLONESHOT);
 use PublicInbox::GitAsyncCat;
 use Text::ParseWords qw(parse_line);
 use Errno qw(EAGAIN);
-use Time::Local qw(timegm);
-use POSIX qw(strftime);
 use Hash::Util qw(unlock_hash); # dependency of fields for perl 5.10+, anyways
 use PublicInbox::Search;
+use PublicInbox::IMAPsearchqp;
 *mdocid = \&PublicInbox::Search::mdocid;
 
 my $Address;
@@ -97,10 +96,6 @@ undef %FETCH_NEED;
 my $valid_range = '[0-9]+|[0-9]+:[0-9]+|[0-9]+:\*';
 $valid_range = qr/\A(?:$valid_range)(?:,(?:$valid_range))*\z/;
 
-my @MoY = qw(Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec);
-my %MoY;
-@MoY{@MoY} = (0..11);
-
 # RFC 3501 5.4. Autologout Timer needs to be >= 30min
 $PublicInbox::DS::EXPTIME = 60 * 30;
 
@@ -1076,16 +1071,6 @@ sub cmd_fetch ($$$$;@) {
         long_response($self, $cb, $tag, [], $range_info, $ops, $partial);
 }
 
-sub parse_date ($) { # 02-Oct-1993
-        my ($date_text) = @_;
-        my ($dd, $mon, $yyyy) = split(/-/, $_[0], 3);
-        defined($yyyy) or return;
-        my $mm = $MoY{$mon} // return;
-        $dd =~ /\A[0123]?[0-9]\z/ or return;
-        $yyyy =~ /\A[0-9]{4,}\z/ or return; # Y10K-compatible!
-        timegm(0, 0, 0, $dd, $mm, $yyyy);
-}
-
 sub msn_convert ($$) {
         my ($self, $uids) = @_;
         my $adj = $self->{uid_base} + 1;
@@ -1168,81 +1153,20 @@ sub xap_append ($$$$) {
         undef;
 }
 
-sub parse_query {
+sub parse_query ($$) {
         my ($self, $rest) = @_;
         if (uc($rest->[0]) eq 'CHARSET') {
                 shift @$rest;
                 defined(my $c = shift @$rest) or return 'BAD missing charset';
                 $c =~ /\A(?:UTF-8|US-ASCII)\z/ or return 'NO [BADCHARSET]';
         }
-
-        my $sql = ''; # date conditions, {sql} deleted if Xapian is needed
-        my $xap = '';
-        my $q = { sql => \$sql, xap => \$xap };
-        my $msn2uid;
-        while (@$rest) {
-                my $k = uc(shift @$rest);
-                # default criteria
-                next if $k =~ /\A(?:ALL|RECENT|UNSEEN|NEW)\z/;
-                next if $k eq 'AND'; # the default, until we support OR
-                if ($k =~ $valid_range) { # convert sequence numbers to UIDs
-                        msn_to_uid_range($msn2uid //= msn2uid($self), $k);
-                        push @{$q->{uid}}, $k;
-                } elsif ($k eq 'UID') {
-                        $k = shift(@$rest) // '';
-                        $k =~ $valid_range or return 'BAD UID range';
-                        push @{$q->{uid}}, $k;
-                } elsif ($k =~ /\A(?:SENT)?(?:SINCE|ON|BEFORE)\z/) {
-                        my $d = parse_date(shift(@$rest) // '');
-                        defined $d or return "BAD $k date format";
-                        date_search($q, $k, $d);
-                } elsif ($k =~ /\A(?:SMALLER|LARGER)\z/) {
-                        delete $q->{sql}; # can't use over.sqlite3
-                        my $bytes = shift(@$rest) // '';
-                        $bytes =~ /\A[0-9]+\z/ or return "BAD $k not a number";
-                        $xap .= ' bytes:' . ($k eq 'SMALLER' ?
-                                                        '..'.(--$bytes) :
-                                                        (++$bytes).'..');
-                } elsif ($k eq 'HEADER') {
-                        $k = uc(shift(@$rest) // '');
-                        my $xk = $H2X{$k} or
-                                return "BAD HEADER $k not supported";
-                        my $err = xap_append($q, $rest, $k, $xk);
-                        return $err if $err;
-                } elsif (defined(my $xk = $I2X{$k})) {
-                        my $err = xap_append($q, $rest, $k, $xk);
-                        return $err if $err;
-                } else {
-                        # TODO: parentheses, OR, NOT ...
-                        return "BAD $k not supported (yet?)";
-                }
-        }
-
-        # favor using over.sqlite3 if possible, since Xapian is optional
-        if (exists $q->{sql}) {
-                delete($q->{xap});
-                delete($q->{sql}) if $sql eq '';
-        } elsif (!$self->{ibx}->search) {
-                return 'BAD Xapian not configured for mailbox';
-        }
-        my $max = $self->{ibx}->over->max;
-        if (my $uid = delete $q->{uid}) {
-                my $range_csv = join(',', @$uid);
-                do {
-                        my $nxt = range_step($self, \$range_csv);
-                        my ($beg, $end) = @$nxt;
-                        if ($xap) {
-                                $xap .= " uid:$beg..$end";
-                        } elsif ($beg == $end) {
-                                $sql .= " AND num = $beg";
-                        } else {
-                                $sql .= " AND num >= $beg AND num <= $end";
-                        }
-                } while ($range_csv);
+        my $q = PublicInbox::IMAPsearchqp::parse($self, join(' ', @$rest));
+        if (ref($q)) {
+                my $max = $self->{ibx}->over->max;
+                my $beg = 1;
+                uid_clamp($self, \$beg, \$max);
+                $q->{range_info} = [ $beg, $max ];
         }
-        my $beg = 1;
-        uid_clamp($self, \$beg, \$max);
-        $q->{range_info} = [ $beg, $max ];
         $q;
 }
 
@@ -1253,7 +1177,7 @@ sub refill_xap ($$$$) {
         my $opt = { mset => 2, limit => 1000 };
         my $nshard = $srch->{nshard} // 1;
         while (1) {
-                my $mset = $srch->query("$$q uid:$beg..$end", $opt);
+                my $mset = $srch->query("$q uid:$beg..$end", $opt);
                 @$uids = map { mdocid($nshard, $_) } $mset->items;
                 if (@$uids) {
                         $range_info->[0] = $uids->[-1] + 1; # update $beg
@@ -1288,6 +1212,8 @@ sub search_common {
                 long_response($self, \&search_uid_range,
                                 $tag, $sql, $range_info, $want_msn);
         } elsif ($q = $q->{xap}) {
+                $self->{ibx}->search or
+                        return "$tag BAD search not available for mailbox\r\n";
                 $self->msg_more('* SEARCH');
                 long_response($self, \&search_xap_range,
                                 $tag, $q, $range_info, $want_msn);
@@ -1321,6 +1247,7 @@ sub process_line ($$) {
 
         # TODO: IMAP allows literals for big requests to upload messages
         # (which we don't support) but maybe some big search queries use it.
+        # RFC 3501 9 (2) doesn't permit TAB or multiple SP
         my ($tag, $req, @args) = parse_line('[ \t]+', 0, $l);
         pop(@args) if (@args && !defined($args[-1]));
         if (@args && uc($req) eq 'UID') {
@@ -1332,6 +1259,10 @@ sub process_line ($$) {
                                 idle_done($self, $tag) :
                                 "$idle_tag BAD expected DONE\r\n";
                 } elsif (my $cmd = $self->can('cmd_'.lc($req // ''))) {
+                        if ($cmd == \&cmd_uid_search || $cmd == \&cmd_search) {
+                                # preserve user-supplied quotes for search
+                                (undef, @args) = split(/ search /i, $l, 2);
+                        }
                         $cmd->($self, $tag, @args);
                 } else { # this is weird
                         auth_challenge_ok($self) //
diff --git a/lib/PublicInbox/IMAPsearchqp.pm b/lib/PublicInbox/IMAPsearchqp.pm
new file mode 100644
index 00000000..fba3bacc
--- /dev/null
+++ b/lib/PublicInbox/IMAPsearchqp.pm
@@ -0,0 +1,276 @@
+# Copyright (C) 2020 all contributors <meta@public-inbox.org>
+# License: AGPL-3.0+ <https://www.gnu.org/licenses/agpl-3.0.txt>
+# IMAP search query parser.  cf RFC 3501
+
+# We currently compile Xapian queries to a string which is fed
+# to Xapian's query parser.  However, we may use Xapian-provided
+# Query object API to build an optree, instead.
+package PublicInbox::IMAPsearchqp;
+use strict;
+use Parse::RecDescent;
+use Time::Local qw(timegm);
+use POSIX qw(strftime);
+our $q = bless {}, __PACKAGE__; # singleton, reachable in generated P::RD
+my @MoY = qw(JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC);
+my %MM = map {; $MoY[$_-1] => sprintf('%02u', $_) } (1..12);
+
+# IMAP to Xapian header search key mapping
+my %IH2X = (
+        TEXT => '',
+        SUBJECT => 's:',
+        BODY => 'b:',
+        FROM => 'f:',
+        TO => 't:',
+        CC => 'c:',
+        # BCC => 'bcc:', # TODO
+
+        # IMAP allows searching arbitrary headers via
+        # "HEADER $field_name $string" which gets silly expensive.
+        # We only allow the headers we already index.
+        'MESSAGE-ID' => 'm:',
+        'LIST-ID' => 'l:',
+        # KEYWORD # TODO ? dfpre,dfpost,...
+);
+
+sub uid_set_xap ($$) {
+        my ($self, $seq_set) = @_;
+        my @u;
+        do {
+                my $u = $self->{imap}->range_step(\$seq_set);
+                die $u unless ref($u); # break out of the parser on error
+                push @u, "uid:$u->[0]..$u->[1]";
+        } while ($seq_set);
+        push(@{$q->{xap}}, @u > 1 ? '('.join(' OR ', @u).')' : $u[0]);
+}
+
+sub xap_only ($;$) {
+        my ($self, $query) = @_;
+        delete $self->{sql}; # query too complex for over.sqlite3
+        push @{$self->{xap}}, $query if defined($query);
+
+        # looks like we can't use SQLite-only, convert SQLite UID
+        # ranges to Xapian:
+        if (my $uid = delete $self->{uid}) {
+                uid_set_xap($self, $_) for @$uid;
+        }
+        1;
+}
+
+sub ih2x {
+        my ($self, $field_name, $s) = @_; # $self == $q
+        $s =~ /\A"(.*?)"\z/s and $s = $1;
+
+        # AFAIK Xapian can't handle [*"] in probabilistic terms,
+        # and it relies on lowercase
+        my $xk = defined($field_name) ? ($IH2X{$field_name} // '') : '';
+        xap_only($self,
+                lc(join(' ', map { qq[$xk"$_"] } split(/[\*"\s]+/, $s))));
+        1;
+}
+
+sub subq_enter {
+        xap_only($q);
+        my $old = delete($q->{xap}) // [];
+        my $nr = push @{$q->{stack}}, $old;
+        die 'BAD deep recursion' if $nr > 10;
+        $q->{xap} = [];
+}
+
+sub subq_leave {
+        my $child = delete $q->{xap};
+        my $parent = $q->{xap} = pop @{$q->{stack}};
+        push(@$parent, @$child > 1 ? '('.join(' ', @$child).')' : $child->[0]);
+        1;
+}
+
+sub yyyymmdd ($) {
+        my ($item) = @_;
+        my ($dd, $mon, $yyyy) = split(/-/, $item->{date}, 3);
+        my $mm = $MM{$mon} // die "BAD month: $mon";
+        wantarray ? ($yyyy, $mm, sprintf('%02u', $dd))
+                : timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
+}
+
+sub SENTSINCE {
+        my ($self, $item) = @_;
+        my ($yyyy, $mm, $dd) = yyyymmdd($item);
+        push @{$self->{xap}}, "d:$yyyy$mm$dd..";
+        my $sql = $self->{sql} or return 1;
+        my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
+        $$sql .= " AND ds >= $ds";
+}
+
+sub SENTON {
+        my ($self, $item) = @_;
+        my ($yyyy, $mm, $dd) = yyyymmdd($item);
+        my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
+        my $end = $ds + 86399; # no leap day
+        my $dt_end = strftime('%Y%m%d%H%M%S', gmtime($end));
+        push @{$self->{xap}}, "dt:$yyyy$mm$dd"."000000..$dt_end";
+        my $sql = $self->{sql} or return 1;
+        $$sql .= " AND ds >= $ds AND ds <= $end";
+}
+
+sub SENTBEFORE {
+        my ($self, $item) = @_;
+        my ($yyyy, $mm, $dd) = yyyymmdd($item);
+        push @{$self->{xap}}, "d:..$yyyy$mm$dd";
+        my $sql = $self->{sql} or return 1;
+        my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
+        $$sql .= " AND ds <= $ds";
+}
+
+sub ON {
+        my ($self, $item) = @_;
+        my $ts = yyyymmdd($item);
+        my $end = $ts + 86399; # no leap day
+        push @{$self->{xap}}, "ts:$ts..$end";
+        my $sql = $self->{sql} or return 1;
+        $$sql .= " AND ts >= $ts AND ts <= $end";
+}
+
+sub BEFORE {
+        my ($self, $item) = @_;
+        my $ts = yyyymmdd($item);
+        push @{$self->{xap}}, "ts:..$ts";
+        my $sql = $self->{sql} or return 1;
+        $$sql .= " AND ts <= $ts";
+}
+
+sub SINCE {
+        my ($self, $item) = @_;
+        my $ts = yyyymmdd($item);
+        push @{$self->{xap}}, "ts:$ts..";
+        my $sql = $self->{sql} or return 1;
+        $$sql .= " AND ts >= $ts";
+}
+
+sub uid_set ($$) {
+        my ($self, $seq_set) = @_;
+        if ($self->{sql}) {
+                push @{$q->{uid}}, $seq_set;
+        } else { # we've gone Xapian-only
+                uid_set_xap($self, $seq_set);
+        }
+        1;
+}
+
+sub msn_set {
+        my ($self, $seq_set) = @_;
+        PublicInbox::IMAP::msn_to_uid_range(
+                $self->{msn2uid} //= $self->{imap}->msn2uid, $seq_set);
+        uid_set($self, $seq_set);
+}
+
+my $prd = Parse::RecDescent->new(<<'EOG');
+<nocheck>
+{ my $q = $PublicInbox::IMAPsearchqp::q; }
+search_key : search_key1(s) { $return = $q }
+search_key1 : "ALL" | "RECENT" | "UNSEEN" | "NEW"
+        | OR_search_keys
+        | NOT_search_key
+        | LARGER_number
+        | SMALLER_number
+        | SENTSINCE_date
+        | SENTON_date
+        | SENTBEFORE_date
+        | SINCE_date
+        | ON_date
+        | BEFORE_date
+        | FROM_string
+        | HEADER_field_name_string
+        | TO_string
+        | CC_string
+        | BCC_string
+        | SUBJECT_string
+        | UID_set
+        | MSN_set
+        | sub_query
+        | <error>
+
+SENTSINCE_date : 'SENTSINCE' date { $q->SENTSINCE(\%item) }
+SENTON_date : 'SENTON' date { $q->SENTON(\%item) }
+SENTBEFORE_date : 'SENTBEFORE' date { $q->SENTBEFORE(\%item) }
+
+SINCE_date : 'SINCE' date { $q->SINCE(\%item) }
+ON_date : 'ON' date { $q->ON(\%item) }
+BEFORE_date : 'BEFORE' date { $q->BEFORE(\%item) }
+
+MSN_set : sequence_set { $q->msn_set($item{sequence_set}) }
+UID_set : "UID" sequence_set { $q->uid_set($item{sequence_set}) }
+LARGER_number : "LARGER" number { $q->xap_only("bytes:$item{number}..") }
+SMALLER_number : "SMALLER" number { $q->xap_only("bytes:..$item{number}") }
+# pass "NOT" through XXX is this right?
+OP_NOT : "NOT" { $q->xap_only('NOT') }
+NOT_search_key : OP_NOT search_key1
+OP_OR : "OR" {
+        $q->xap_only('OP_OR');
+        my $cur = delete $q->{xap};
+        push @{$q->{stack}}, $cur;
+        $q->{xap} = [];
+}
+search_key_a : search_key1
+{
+        my $ka = delete $q->{xap};
+        $q->{xap} = [];
+        push @{$q->{stack}}, $ka;
+}
+OR_search_keys : OP_OR search_key_a search_key1
+{
+        my $kb = delete $q->{xap};
+        my $ka = pop @{$q->{stack}};
+        my $xap = $q->{xap} = pop @{$q->{stack}};
+        my $op = pop @$xap;
+        $op eq 'OP_OR' or die "BAD expected OR: $op";
+        $ka = @$ka > 1 ? '('.join(' ', @$ka).')' : $ka->[0];
+        $kb = @$kb > 1 ? '('.join(' ', @$kb).')' : $kb->[0];
+        push @$xap, "($ka OR $kb)";
+}
+HEADER_field_name_string : "HEADER" field_name string
+{
+        $q->ih2x($item{field_name}, $item{string});
+}
+FROM_string : "FROM" string { $q->ih2x('FROM', $item{string}) }
+TO_string : "TO" string { $q->ih2x('TO', $item{string}) }
+CC_string : "CC" string { $q->ih2x('CC', $item{string}) }
+BCC_string : "BCC" string { $q->ih2x('BCC', $item{string}) }
+SUBJECT_string : "SUBJECT" string { $q->ih2x('SUBJECT', $item{string}) }
+op_subq_enter : '(' { $q->subq_enter }
+sub_query : op_subq_enter search_key1(s) ')' { $q->subq_leave }
+
+field_name : /[\x21-\x39\x3b-\x7e]+/
+string : quoted | literal
+literal : /[^"\(\) \t]+/ # bogus, I know
+quoted : /"[^"]*"/
+number : /[0-9]+/
+date : /[0123]?[0-9]-[A-Z]{3}-[0-9]{4,}/
+sequence_set : /\A[0-9][0-9,:]*[0-9\*]?\z/
+EOG
+
+sub parse {
+        my ($imap, $query) = @_;
+        my $sql = '';
+        %$q = (sql => \$sql, imap => $imap); # imap = PublicInbox::IMAP obj
+        # $::RD_TRACE = 1;
+        my $res = eval { $prd->search_key(uc($query)) };
+        return $@ if $@ && $@ =~ /\ABAD /;
+        return 'BAD unexpected result' if !$res || $res != $q;
+        if (exists $q->{sql}) {
+                delete $q->{xap};
+                if (my $uid = delete $q->{uid}) {
+                        my @u;
+                        for my $uid_set (@$uid) {
+                                my $u = $q->{imap}->range_step(\$uid_set);
+                                return $u if !ref($u);
+                                push @u, "num >= $u->[0] AND num <= $u->[1]";
+                        }
+                        $sql .= ' AND ('.join(' OR ', @u).')';
+                }
+        } else {
+                $q->{xap} = join(' ', @{$q->{xap}});
+        }
+        delete @$q{qw(imap msn2uid)};
+        $q;
+}
+
+1