]> Sergey Matveev's repositories - public-inbox.git/blob - lib/PublicInbox/IMAPsearchqp.pm
solver: support sha256 coderepos
[public-inbox.git] / lib / PublicInbox / IMAPsearchqp.pm
1 # Copyright (C) 2020-2021 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         # TEXT => undef, # => everything
22         FROM => 'f:',
23         TO => 't:',
24         CC => 'c:',
25         # BCC => 'bcc:', # TODO
26
27         # IMAP allows searching arbitrary headers via
28         # "HEADER $field_name $string" which gets silly expensive.
29         # We only allow the headers we already index.
30         'MESSAGE-ID' => 'm:',
31         'LIST-ID' => 'l:',
32         # KEYWORD # TODO ? dfpre,dfpost,...
33 );
34
35 sub uid_set_xap ($$) {
36         my ($self, $seq_set) = @_;
37         my @u;
38         do {
39                 my $u = $self->{imap}->range_step(\$seq_set);
40                 die $u unless ref($u); # break out of the parser on error
41                 push @u, "uid:$u->[0]..$u->[1]";
42         } while ($seq_set);
43         push(@{$q->{xap}}, @u > 1 ? '('.join(' OR ', @u).')' : $u[0]);
44 }
45
46 sub xap_only ($;$) {
47         my ($self, $query) = @_;
48         delete $self->{sql}; # query too complex for over.sqlite3
49         push @{$self->{xap}}, $query if defined($query);
50
51         # looks like we can't use SQLite-only, convert SQLite UID
52         # ranges to Xapian:
53         if (my $uid = delete $self->{uid}) {
54                 uid_set_xap($self, $_) for @$uid;
55         }
56         1;
57 }
58
59 sub ih2x {
60         my ($self, $field_name, $s) = @_; # $self == $q
61         $s =~ /\A"(.*?)"\z/s and $s = $1;
62
63         # AFAIK Xapian can't handle [*"] in probabilistic terms,
64         # and it relies on lowercase
65         my $xk = defined($field_name) ? ($IH2X{$field_name} // '') : '';
66         xap_only($self,
67                 lc(join(' ', map { qq[$xk"$_"] } split(/[\*"\s]+/, $s))));
68         1;
69 }
70
71 sub subq_enter {
72         xap_only($q);
73         my $old = delete($q->{xap}) // [];
74         my $nr = push @{$q->{stack}}, $old;
75         die 'BAD deep recursion' if $nr > 10;
76         $q->{xap} = [];
77 }
78
79 sub subq_leave {
80         my $child = delete $q->{xap};
81         my $parent = $q->{xap} = pop @{$q->{stack}};
82         push(@$parent, @$child > 1 ? '('.join(' ', @$child).')' : $child->[0]);
83         1;
84 }
85
86 sub yyyymmdd ($) {
87         my ($item) = @_;
88         my ($dd, $mon, $yyyy) = split(/-/, $item->{date}, 3);
89         my $mm = $MM{$mon} // die "BAD month: $mon";
90         wantarray ? ($yyyy, $mm, sprintf('%02u', $dd))
91                 : timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
92 }
93
94 sub SENTSINCE {
95         my ($self, $item) = @_;
96         my ($yyyy, $mm, $dd) = yyyymmdd($item);
97         push @{$self->{xap}}, "d:$yyyy$mm$dd..";
98         my $sql = $self->{sql} or return 1;
99         my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
100         $$sql .= " AND ds >= $ds";
101 }
102
103 sub SENTON {
104         my ($self, $item) = @_;
105         my ($yyyy, $mm, $dd) = yyyymmdd($item);
106         my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
107         my $end = $ds + 86399; # no leap day
108         my $dt_end = strftime('%Y%m%d%H%M%S', gmtime($end));
109         push @{$self->{xap}}, "dt:$yyyy$mm$dd"."000000..$dt_end";
110         my $sql = $self->{sql} or return 1;
111         $$sql .= " AND ds >= $ds AND ds <= $end";
112 }
113
114 sub SENTBEFORE {
115         my ($self, $item) = @_;
116         my ($yyyy, $mm, $dd) = yyyymmdd($item);
117         push @{$self->{xap}}, "d:..$yyyy$mm$dd";
118         my $sql = $self->{sql} or return 1;
119         my $ds = timegm(0, 0, 0, $dd, $mm - 1, $yyyy);
120         $$sql .= " AND ds <= $ds";
121 }
122
123 sub ON {
124         my ($self, $item) = @_;
125         my $ts = yyyymmdd($item);
126         my $end = $ts + 86399; # no leap day
127         push @{$self->{xap}}, "rt:$ts..$end";
128         my $sql = $self->{sql} or return 1;
129         $$sql .= " AND ts >= $ts AND ts <= $end";
130 }
131
132 sub BEFORE {
133         my ($self, $item) = @_;
134         my $ts = yyyymmdd($item);
135         push @{$self->{xap}}, "rt:..$ts";
136         my $sql = $self->{sql} or return 1;
137         $$sql .= " AND ts <= $ts";
138 }
139
140 sub SINCE {
141         my ($self, $item) = @_;
142         my $ts = yyyymmdd($item);
143         push @{$self->{xap}}, "rt:$ts..";
144         my $sql = $self->{sql} or return 1;
145         $$sql .= " AND ts >= $ts";
146 }
147
148 sub uid_set ($$) {
149         my ($self, $seq_set) = @_;
150         if ($self->{sql}) {
151                 push @{$q->{uid}}, $seq_set;
152         } else { # we've gone Xapian-only
153                 uid_set_xap($self, $seq_set);
154         }
155         1;
156 }
157
158 sub msn_set {
159         my ($self, $seq_set) = @_;
160         PublicInbox::IMAP::msn_to_uid_range(
161                 $self->{msn2uid} //= $self->{imap}->msn2uid, $seq_set);
162         uid_set($self, $seq_set);
163 }
164
165 # things that should not match
166 sub impossible {
167         my ($self) = @_;
168         push @{$self->{xap}}, 'z:..0';
169         my $sql = $self->{sql} or return 1;
170         $$sql .= ' AND num < 0';
171 }
172
173 my $prd = Parse::RecDescent->new(<<'EOG');
174 <nocheck>
175 { my $q = $PublicInbox::IMAPsearchqp::q; }
176 search_key : CHARSET(?) search_key1(s) { $return = $q }
177
178 # n.b. we silently ignore most per-message flags right now;
179 # they're here for now to not dump parser errors.
180 search_key1 : "ALL" | "ANSWERED" | "RECENT" | "UNSEEN" | "SEEN" | "NEW"
181         | "UNANSWERED" | "UNDELETED" | "UNDRAFT" | "UNFLAGGED"
182         | DELETED | DRAFT | FLAGGED | OLD
183         | OR_search_keys
184         | NOT_search_key
185         | LARGER_number
186         | SMALLER_number
187         | SENTSINCE_date
188         | SENTON_date
189         | SENTBEFORE_date
190         | SINCE_date
191         | ON_date
192         | BEFORE_date
193         | FROM_string
194         | HEADER_field_name_string
195         | TO_string
196         | CC_string
197         | BCC_string
198         | SUBJECT_string
199         | BODY_string
200         | TEXT_string
201         | UID_set
202         | MSN_set
203         | sub_query
204         | <error>
205
206 charset : /\S+/
207 CHARSET : 'CHARSET' charset
208 { $item{charset} =~ /\A(?:UTF-8|US-ASCII)\z/ ? 1 : die('NO [BADCHARSET]'); }
209
210 SENTSINCE_date : 'SENTSINCE' date { $q->SENTSINCE(\%item) }
211 SENTON_date : 'SENTON' date { $q->SENTON(\%item) }
212 SENTBEFORE_date : 'SENTBEFORE' date { $q->SENTBEFORE(\%item) }
213
214 SINCE_date : 'SINCE' date { $q->SINCE(\%item) }
215 ON_date : 'ON' date { $q->ON(\%item) }
216 BEFORE_date : 'BEFORE' date { $q->BEFORE(\%item) }
217
218 MSN_set : sequence_set { $q->msn_set($item{sequence_set}) }
219 UID_set : "UID" sequence_set { $q->uid_set($item{sequence_set}) }
220 LARGER_number : "LARGER" number { $q->xap_only("z:$item{number}..") }
221 SMALLER_number : "SMALLER" number { $q->xap_only("z:..$item{number}") }
222
223 DELETED : "DELETED" { $q->impossible }
224 OLD : "OLD" { $q->impossible }
225 FLAGGED : "FLAGGED" { $q->impossible }
226 DRAFT : "DRAFT" { $q->impossible }
227
228 # pass "NOT" through XXX is this right?
229 OP_NOT : "NOT" { $q->xap_only('NOT') }
230 NOT_search_key : OP_NOT search_key1
231 OP_OR : "OR" {
232         $q->xap_only('OP_OR');
233         my $cur = delete $q->{xap};
234         push @{$q->{stack}}, $cur;
235         $q->{xap} = [];
236 }
237 search_key_a : search_key1
238 {
239         my $ka = delete $q->{xap};
240         $q->{xap} = [];
241         push @{$q->{stack}}, $ka;
242 }
243 OR_search_keys : OP_OR search_key_a search_key1
244 {
245         my $kb = delete $q->{xap};
246         my $ka = pop @{$q->{stack}};
247         my $xap = $q->{xap} = pop @{$q->{stack}};
248         my $op = pop @$xap;
249         $op eq 'OP_OR' or die "BAD expected OR: $op";
250         $ka = @$ka > 1 ? '('.join(' ', @$ka).')' : $ka->[0];
251         $kb = @$kb > 1 ? '('.join(' ', @$kb).')' : $kb->[0];
252         push @$xap, "($ka OR $kb)";
253 }
254 HEADER_field_name_string : "HEADER" field_name string
255 {
256         $q->ih2x($item{field_name}, $item{string});
257 }
258 FROM_string : "FROM" string { $q->ih2x('FROM', $item{string}) }
259 TO_string : "TO" string { $q->ih2x('TO', $item{string}) }
260 CC_string : "CC" string { $q->ih2x('CC', $item{string}) }
261 BCC_string : "BCC" string { $q->ih2x('BCC', $item{string}) }
262 SUBJECT_string : "SUBJECT" string { $q->ih2x('SUBJECT', $item{string}) }
263 BODY_string : "BODY" string { $q->ih2x('BODY', $item{string}) }
264 TEXT_string : "TEXT" string { $q->ih2x(undef, $item{string}) }
265 op_subq_enter : '(' { $q->subq_enter }
266 sub_query : op_subq_enter search_key1(s) ')' { $q->subq_leave }
267
268 field_name : /[\x21-\x39\x3b-\x7e]+/
269 string : quoted | literal
270 literal : /[^"\(\) \t]+/ # bogus, I know
271 quoted : /"[^"]*"/
272 number : /[0-9]+/
273 date : /[0123]?[0-9]-[A-Z]{3}-[0-9]{4,}/
274 sequence_set : /\A[0-9][0-9,:]*[0-9\*]?\z/
275 EOG
276
277 sub parse {
278         my ($imap, $query) = @_;
279         my $sql = '';
280         %$q = (sql => \$sql, imap => $imap); # imap = PublicInbox::IMAP obj
281         # $::RD_TRACE = 1;
282         my $res = eval { $prd->search_key(uc($query)) };
283         return $@ if $@ && $@ =~ /\A(?:BAD|NO) /;
284         return 'BAD unexpected result' if !$res || $res != $q;
285         if (exists $q->{sql}) {
286                 delete $q->{xap};
287                 if (my $uid = delete $q->{uid}) {
288                         my @u;
289                         for my $uid_set (@$uid) {
290                                 my $u = $q->{imap}->range_step(\$uid_set);
291                                 return $u if !ref($u);
292                                 push @u, "num >= $u->[0] AND num <= $u->[1]";
293                         }
294                         $sql .= ' AND ('.join(' OR ', @u).')';
295                 }
296         } else {
297                 $q->{xap} = join(' ', @{$q->{xap}});
298         }
299         delete @$q{qw(imap msn2uid)};
300         $q;
301 }
302
303 1