lib/PublicInbox/IMAPsearchqp.pm

   1 # Copyright (C) 2020 all contributors <meta@public-inbox.org>
   2 # License: AGPL-3.0+ <https://www.gnu.org/licenses/agpl-3.0.txt>
   3 # IMAP search query parser.  cf RFC 3501
   4
   5 # We currently compile Xapian queries to a string which is fed
   6 # to Xapian's query parser.  However, we may use Xapian-provided
   7 # Query object API to build an optree, instead.
   8 package PublicInbox::IMAPsearchqp;
   9 use strict;
  10 use Parse::RecDescent;
  11 use Time::Local qw(timegm);
  12 use POSIX qw(strftime);
  13 our $q = bless {}, __PACKAGE__; # singleton, reachable in generated P::RD
  14 my @MoY = qw(JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC);
  15 my %MM = map {; $MoY[$_-1] => sprintf('%02u', $_) } (1..12);
  16
  17 # IMAP to Xapian header search key mapping
  18 my %IH2X = (
  19         SUBJECT => 's:',
  20         BODY => 'b:',
  21         FROM => 'f:',
  22         TO => 't:',
  23         CC => 'c:',
  24         # BCC => 'bcc:', # TODO
  25
  26         # IMAP allows searching arbitrary headers via
  27         # "HEADER $field_name $string" which gets silly expensive.
  28         # We only allow the headers we already index.
  29         'MESSAGE-ID' => 'm:',
  30         'LIST-ID' => 'l:',
  31         # KEYWORD # TODO ? dfpre,dfpost,...
  32 );
  33
  34 sub uid_set_xap ($$) {
  35         my ($self, $seq_set) = @_;
  36         my @u;
  37         do {
  38                 my $u = $self->{imap}->range_step(\$seq_set);
  39                 die $u unless ref($u); # break out of the parser on error
  40                 push @u, "uid:$u->[0]..$u->[1]";
  41         } while ($seq_set);
  42         push(@{$q->{xap}}, @u > 1 ? '('.join(' OR ', @u).')' : $u[0]);
  43 }
  44
  45 sub xap_only ($;$) {
  46         my ($self, $query) = @_;
  47         delete $self->{sql}; # query too complex for over.sqlite3
  48         push @{$self->{xap}}, $query if defined($query);
  49
  50         # looks like we can't use SQLite-only, convert SQLite UID
  51         # ranges to Xapian:
  52         if (my $uid = delete $self->{uid}) {
  53                 uid_set_xap($self, $_) for @$uid;
  54         }
  55         1;
  56 }
  57
  58 sub ih2x {
  59         my ($self, $field_name, $s) = @_; # $self == $q
  60         $s =~ /\A"(.*?)"\z/s and $s = $1;
  61
  62         # AFAIK Xapian can't handle [*"] in probabilistic terms,
  63         # and it relies on lowercase
  64         my $xk = defined($field_name) ? ($IH2X{$field_name} // '') : '';
  65         xap_only($self,
  66                 lc(join(' ', map { qq[$xk"$_"] } split(/[\*"\s]+/, $s))));
  67         1;
  68 }
  69
  70 sub subq_enter {
  71         xap_only($q);
  72         my $old = delete($q->{xap}) // [];
  73         my $nr = push @{$q->{stack}}, $old;
  74         die 'BAD deep recursion' if $nr > 10;
  75         $q->{xap} = [];
  76 }
  77
  78 sub subq_leave {
  79         my $child = delete $q->{xap};
  80         my $parent = $q->{xap} = pop @{$q->{stack}};
  81         push(@$parent, @$child > 1 ? '('.join(' ', @$child).')' : $child->[0]);
  82         1;
  83 }
  84
  85 sub yyyymmdd ($) {
  86         my ($item) = @_;
  87         my ($dd, $mon, $yyyy) = split(/-/, $item->{date}, 3);
  88         my $mm = $MM{$mon} // die "BAD month: $mon";
  89         wantarray ? ($yyyy, $mm, sprintf('%02u', $dd))
  90                 : timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
  91 }
  92
  93 sub SENTSINCE {
  94         my ($self, $item) = @_;
  95         my ($yyyy, $mm, $dd) = yyyymmdd($item);
  96         push @{$self->{xap}}, "d:$yyyy$mm$dd..";
  97         my $sql = $self->{sql} or return 1;
  98         my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
  99         $$sql .= " AND ds >= $ds";
 100 }
 101
 102 sub SENTON {
 103         my ($self, $item) = @_;
 104         my ($yyyy, $mm, $dd) = yyyymmdd($item);
 105         my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
 106         my $end = $ds + 86399; # no leap day
 107         my $dt_end = strftime('%Y%m%d%H%M%S', gmtime($end));
 108         push @{$self->{xap}}, "dt:$yyyy$mm$dd"."000000..$dt_end";
 109         my $sql = $self->{sql} or return 1;
 110         $$sql .= " AND ds >= $ds AND ds <= $end";
 111 }
 112
 113 sub SENTBEFORE {
 114         my ($self, $item) = @_;
 115         my ($yyyy, $mm, $dd) = yyyymmdd($item);
 116         push @{$self->{xap}}, "d:..$yyyy$mm$dd";
 117         my $sql = $self->{sql} or return 1;
 118         my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
 119         $$sql .= " AND ds <= $ds";
 120 }
 121
 122 sub ON {
 123         my ($self, $item) = @_;
 124         my $ts = yyyymmdd($item);
 125         my $end = $ts + 86399; # no leap day
 126         push @{$self->{xap}}, "ts:$ts..$end";
 127         my $sql = $self->{sql} or return 1;
 128         $$sql .= " AND ts >= $ts AND ts <= $end";
 129 }
 130
 131 sub BEFORE {
 132         my ($self, $item) = @_;
 133         my $ts = yyyymmdd($item);
 134         push @{$self->{xap}}, "ts:..$ts";
 135         my $sql = $self->{sql} or return 1;
 136         $$sql .= " AND ts <= $ts";
 137 }
 138
 139 sub SINCE {
 140         my ($self, $item) = @_;
 141         my $ts = yyyymmdd($item);
 142         push @{$self->{xap}}, "ts:$ts..";
 143         my $sql = $self->{sql} or return 1;
 144         $$sql .= " AND ts >= $ts";
 145 }
 146
 147 sub uid_set ($$) {
 148         my ($self, $seq_set) = @_;
 149         if ($self->{sql}) {
 150                 push @{$q->{uid}}, $seq_set;
 151         } else { # we've gone Xapian-only
 152                 uid_set_xap($self, $seq_set);
 153         }
 154         1;
 155 }
 156
 157 sub msn_set {
 158         my ($self, $seq_set) = @_;
 159         PublicInbox::IMAP::msn_to_uid_range(
 160                 $self->{msn2uid} //= $self->{imap}->msn2uid, $seq_set);
 161         uid_set($self, $seq_set);
 162 }
 163
 164 my $prd = Parse::RecDescent->new(<<'EOG');
 165 <nocheck>
 166 { my $q = $PublicInbox::IMAPsearchqp::q; }
 167 search_key : CHARSET(?) search_key1(s) { $return = $q }
 168 search_key1 : "ALL" | "RECENT" | "UNSEEN" | "NEW"
 169         | OR_search_keys
 170         | NOT_search_key
 171         | LARGER_number
 172         | SMALLER_number
 173         | SENTSINCE_date
 174         | SENTON_date
 175         | SENTBEFORE_date
 176         | SINCE_date
 177         | ON_date
 178         | BEFORE_date
 179         | FROM_string
 180         | HEADER_field_name_string
 181         | TO_string
 182         | CC_string
 183         | BCC_string
 184         | SUBJECT_string
 185         | TEXT_string
 186         | UID_set
 187         | MSN_set
 188         | sub_query
 189         | <error>
 190
 191 charset : /\S+/
 192 CHARSET : 'CHARSET' charset
 193 { $item{charset} =~ /\A(?:UTF-8|US-ASCII)\z/ ? 1 : die('NO [BADCHARSET]'); }
 194
 195 SENTSINCE_date : 'SENTSINCE' date { $q->SENTSINCE(\%item) }
 196 SENTON_date : 'SENTON' date { $q->SENTON(\%item) }
 197 SENTBEFORE_date : 'SENTBEFORE' date { $q->SENTBEFORE(\%item) }
 198
 199 SINCE_date : 'SINCE' date { $q->SINCE(\%item) }
 200 ON_date : 'ON' date { $q->ON(\%item) }
 201 BEFORE_date : 'BEFORE' date { $q->BEFORE(\%item) }
 202
 203 MSN_set : sequence_set { $q->msn_set($item{sequence_set}) }
 204 UID_set : "UID" sequence_set { $q->uid_set($item{sequence_set}) }
 205 LARGER_number : "LARGER" number { $q->xap_only("bytes:$item{number}..") }
 206 SMALLER_number : "SMALLER" number { $q->xap_only("bytes:..$item{number}") }
 207 # pass "NOT" through XXX is this right?
 208 OP_NOT : "NOT" { $q->xap_only('NOT') }
 209 NOT_search_key : OP_NOT search_key1
 210 OP_OR : "OR" {
 211         $q->xap_only('OP_OR');
 212         my $cur = delete $q->{xap};
 213         push @{$q->{stack}}, $cur;
 214         $q->{xap} = [];
 215 }
 216 search_key_a : search_key1
 217 {
 218         my $ka = delete $q->{xap};
 219         $q->{xap} = [];
 220         push @{$q->{stack}}, $ka;
 221 }
 222 OR_search_keys : OP_OR search_key_a search_key1
 223 {
 224         my $kb = delete $q->{xap};
 225         my $ka = pop @{$q->{stack}};
 226         my $xap = $q->{xap} = pop @{$q->{stack}};
 227         my $op = pop @$xap;
 228         $op eq 'OP_OR' or die "BAD expected OR: $op";
 229         $ka = @$ka > 1 ? '('.join(' ', @$ka).')' : $ka->[0];
 230         $kb = @$kb > 1 ? '('.join(' ', @$kb).')' : $kb->[0];
 231         push @$xap, "($ka OR $kb)";
 232 }
 233 HEADER_field_name_string : "HEADER" field_name string
 234 {
 235         $q->ih2x($item{field_name}, $item{string});
 236 }
 237 FROM_string : "FROM" string { $q->ih2x('FROM', $item{string}) }
 238 TO_string : "TO" string { $q->ih2x('TO', $item{string}) }
 239 CC_string : "CC" string { $q->ih2x('CC', $item{string}) }
 240 BCC_string : "BCC" string { $q->ih2x('BCC', $item{string}) }
 241 SUBJECT_string : "SUBJECT" string { $q->ih2x('SUBJECT', $item{string}) }
 242 TEXT_string : "TEXT" string { $q->ih2x(undef, $item{string}) }
 243 op_subq_enter : '(' { $q->subq_enter }
 244 sub_query : op_subq_enter search_key1(s) ')' { $q->subq_leave }
 245
 246 field_name : /[\x21-\x39\x3b-\x7e]+/
 247 string : quoted | literal
 248 literal : /[^"\(\) \t]+/ # bogus, I know
 249 quoted : /"[^"]*"/
 250 number : /[0-9]+/
 251 date : /[0123]?[0-9]-[A-Z]{3}-[0-9]{4,}/
 252 sequence_set : /\A[0-9][0-9,:]*[0-9\*]?\z/
 253 EOG
 254
 255 sub parse {
 256         my ($imap, $query) = @_;
 257         my $sql = '';
 258         %$q = (sql => \$sql, imap => $imap); # imap = PublicInbox::IMAP obj
 259         # $::RD_TRACE = 1;
 260         my $res = eval { $prd->search_key(uc($query)) };
 261         return $@ if $@ && $@ =~ /\A(?:BAD|NO) /;
 262         return 'BAD unexpected result' if !$res || $res != $q;
 263         if (exists $q->{sql}) {
 264                 delete $q->{xap};
 265                 if (my $uid = delete $q->{uid}) {
 266                         my @u;
 267                         for my $uid_set (@$uid) {
 268                                 my $u = $q->{imap}->range_step(\$uid_set);
 269                                 return $u if !ref($u);
 270                                 push @u, "num >= $u->[0] AND num <= $u->[1]";
 271                         }
 272                         $sql .= ' AND ('.join(' OR ', @u).')';
 273                 }
 274         } else {
 275                 $q->{xap} = join(' ', @{$q->{xap}});
 276         }
 277         delete @$q{qw(imap msn2uid)};
 278         $q;
 279 }
 280
 281 1