Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_mail/src/search.rs

65.6 KiB, 652 runs

created by r2968587332:77839, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Mail search: the query a person or a daimon asks, its typed operators, and the one matcher
2//! that decides every hit on every surface. A server's SEARCH only narrows the candidates.
3//!
4//! A query is a tree of terms, as Gmail's typed language and IMAP SEARCH both are: AND, OR and
5//! NOT over leaves, a leaf being text in a scope or a filter (a day, a relative age, a size, a
6//! flag, an attachment). The switches (folders, scopes, match case, whole word) apply to the
7//! whole query. A word shaped as an operator whose key this language does not know is refused,
8//! never searched as text. Each tree prints as text that reads back as the same tree. Its depth
9//! and leaves are bounded by the caller's `Limits`, at `parse` and at `Matcher::new`.
10//!
11//! The matcher reads a message's decoded headers (RFC 2047), its readable text and its
12//! attachments' names, never an attachment's bytes, in Unicode's form C, with the bidirectional
13//! controls removed so that one hidden in a name cannot split a word. A group stops at its first
14//! deciding child. Every pattern is compiled once by `fe2o3_text::regex`, whose search is linear
15//! in pattern times text; a search too wide for its visited set is an error, and an answer that
16//! depends on it is unknown, never a guessed hit or miss.
17
18use crate::message::ParsedMessage;
19
20pub use crate::sync::query::Day;
21
22use oxedyne_fe2o3_core::prelude::*;
23use oxedyne_fe2o3_net::imap::search::{
24 days_from_civil,
25 Flag,
26 SearchKey,
27 Segment,
28};
29use oxedyne_fe2o3_text::{
30 html::reference,
31 mime::{
32 decode_words,
33 field,
34 headers,
35 },
36 regex::{
37 quote,
38 Regex,
39 Span,
40 },
41 unicode::norm::{
42 combining_class,
43 nfc,
44 },
45};
46
47use std::fmt;
48
49
50#[derive(Clone, Copy, Debug, Eq, PartialEq)]
51pub enum Mode {
52 Word, // the text as typed, typed bare or quoted without whitespace
53 Phrase, // the words in order, any whitespace between them
54 Regex,
55}
56
57#[derive(Clone, Copy, Debug, Eq, PartialEq)]
58pub enum Scope {
59 From,
60 To,
61 Cc,
62 Bcc,
63 Subject,
64 Body, // the readable text parts
65 Attachment, // the attachments' names
66}
67
68// The words double as the typed operators `from:` .. `filename:`.
69const SCOPES: [(Scope, &str); 7] = [
70 (Scope::From, "from"),
71 (Scope::To, "to"),
72 (Scope::Cc, "cc"),
73 (Scope::Bcc, "bcc"),
74 (Scope::Subject, "subject"),
75 (Scope::Body, "body"),
76 (Scope::Attachment, "filename"),
77];
78
79fn word_of(s: Scope) -> &'static str {
80 SCOPES.iter().find(|(x, _)| *x == s).map_or("", |(_, w)| w)
81}
82
83fn scope_of(w: &str) -> Option<Scope> {
84 SCOPES.iter().find(|(_, x)| *x == w).map(|(s, _)| *s)
85}
86
87/// A condition on what the store knows beside the bytes, or on the attachments.
88#[derive(Clone, Copy, Debug, Eq, PartialEq)]
89pub enum Filter {
90 Since(Day), // on or after
91 Before(Day),
92 OlderThan(Age), // before the day this long before the matcher's day
93 NewerThan(Age), // on or after it
94 HasAttachment,
95 Seen,
96 Unseen,
97 Flagged,
98 Larger(u64), // bytes
99 Smaller(u64),
100}
101
102/// Gmail's `7d`, `2m`, `1y`.
103#[derive(Clone, Copy, Debug, Eq, PartialEq)]
104pub enum Age {
105 Days(u32),
106 Months(u32),
107 Years(u32),
108}
109
110impl Age {
111 pub fn parse(s: &str) -> Outcome<Self> {
112 let n = s.get(..s.len().saturating_sub(1)).filter(|n| !n.is_empty() && n.bytes().all(|b| b.is_ascii_digit()))
113 .and_then(|n| n.parse().ok());
114 match (n, s.chars().last()) {
115 (Some(n), Some('d')) => Ok(Self::Days(n)),
116 (Some(n), Some('m')) => Ok(Self::Months(n)),
117 (Some(n), Some('y')) => Ok(Self::Years(n)),
118 _ => Err(err!("'{}' is not an age; write 7d, 2m or 1y.", s; Invalid, Input)),
119 }
120 }
121
122 /// The day this long before `d`, a month's end clamped (31 March less a month is 28
123 /// February), and no earlier than the year 0.
124 fn before(self, d: Day) -> Day {
125 let back = |n: u32| {
126 let t = (d.year as i64 * 12 + d.month as i64 - 1 - n as i64).max(0); // fixed: months a year
127 let (year, month) = ((t / 12) as u16, (t % 12) as u8 + 1);
128 Day { year, month, day: d.day.min(Day::last(year, month)) }
129 };
130 let (mut d, mut n) = match self {
131 Self::Months(n) => return back(n),
132 Self::Years(n) => return back(n.saturating_mul(12)),
133 Self::Days(n) => (d, n),
134 };
135 while n >= d.day as u32 {
136 if d.year == 0 && d.month == 1 { return Day { day: 1, ..d }; }
137 n -= d.day as u32;
138 let (year, month) = if d.month == 1 { (d.year - 1, 12) } else { (d.year, d.month - 1) };
139 d = Day { year, month, day: Day::last(year, month) };
140 }
141 Day { day: d.day - n as u8, ..d }
142 }
143}
144
145impl fmt::Display for Age {
146 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
147 match self {
148 Self::Days(n) => write!(f, "{}d", n),
149 Self::Months(n) => write!(f, "{}m", n),
150 Self::Years(n) => write!(f, "{}y", n),
151 }
152 }
153}
154
155/// The query's condition: `All` of nothing is none.
156pub enum Term {
157 Text { scope: Option<Scope>, mode: Mode, text: String }, // `None`: the query's scopes
158 Filter(Filter),
159 Not(Box<Term>),
160 All(Vec<Term>),
161 Any(Vec<Term>),
162}
163
164impl Default for Term {
165 fn default() -> Self { Self::All(Vec::new()) }
166}
167
168// Freed from a stack of its own, so that a tree built deep in code does not exhaust the thread's.
169impl Drop for Term {
170 fn drop(&mut self) {
171 fn kids(t: &mut Term, st: &mut Vec<Term>) {
172 match t {
173 Term::Not(x) => st.push(std::mem::take(&mut **x)),
174 Term::All(v) | Term::Any(v) => st.append(v),
175 Term::Text { .. } | Term::Filter(_) => {}
176 }
177 }
178 let mut st = Vec::new();
179 kids(self, &mut st);
180 while let Some(mut t) = st.pop() { kids(&mut t, &mut st); }
181 }
182}
183
184// Clone, Eq and Debug, like Display and Drop, walk a stack of their own, so that a tree built
185// deep in code is copied, compared and shown without exhausting the thread's.
186impl Clone for Term {
187 fn clone(&self) -> Self {
188 enum W<'a> { Visit(&'a Term), Build(&'a Term) }
189 let (mut st, mut out) = (vec![W::Visit(self)], Vec::<Term>::new());
190 while let Some(w) = st.pop() {
191 match w {
192 W::Visit(t) => {
193 st.push(W::Build(t));
194 match t {
195 Term::Not(x) => st.push(W::Visit(x)),
196 Term::All(v) | Term::Any(v) => st.extend(v.iter().rev().map(W::Visit)),
197 Term::Text { .. } | Term::Filter(_) => {}
198 }
199 }
200 W::Build(t) => {
201 let n = match t {
202 Term::Text { scope, mode, text } => Term::Text { scope: *scope, mode: *mode, text: text.clone() },
203 Term::Filter(f) => Term::Filter(*f),
204 Term::Not(_) => Term::Not(Box::new(out.pop().unwrap_or_default())),
205 Term::All(v) => Term::All(out.split_off(out.len().saturating_sub(v.len()))),
206 Term::Any(v) => Term::Any(out.split_off(out.len().saturating_sub(v.len()))),
207 };
208 out.push(n);
209 }
210 }
211 }
212 out.pop().unwrap_or_default()
213 }
214}
215
216impl PartialEq for Term {
217 fn eq(&self, o: &Self) -> bool {
218 let mut st = vec![(self, o)];
219 while let Some(p) = st.pop() {
220 match p {
221 (Term::Text { scope: a, mode: b, text: c }, Term::Text { scope: x, mode: y, text: z })
222 if (a, b, c) == (x, y, z) => {}
223 (Term::Filter(a), Term::Filter(b)) if a == b => {}
224 (Term::Not(a), Term::Not(b)) => st.push((a, b)),
225 (Term::All(a), Term::All(b)) | (Term::Any(a), Term::Any(b)) if a.len() == b.len() => st.extend(a.iter().zip(b)),
226 _ => return false,
227 }
228 }
229 true
230 }
231}
232
233impl Eq for Term {}
234
235// As typed, since a derived form would recurse.
236impl fmt::Debug for Term {
237 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
238 write!(f, "Term({:?})", term(self))
239 }
240}
241
242#[derive(Clone, Debug, Default, Eq, PartialEq)]
243pub enum Folders {
244 #[default]
245 Selected,
246 List(Vec<String>),
247 All { junk_trash: bool },
248}
249
250#[derive(Clone, Debug, Default, Eq, PartialEq)]
251pub struct Query {
252 pub terms: Term,
253 pub whole_word: bool,
254 pub match_case: bool,
255 pub substring: bool, // a phrase matched exactly, its whitespace included
256 pub scopes: Vec<Scope>, // where an unscoped term is sought; empty is everywhere
257 pub folders: Folders, // for the corpus; the matcher sees one message
258}
259
260/// Refuses a tree nested deeper than `search_max_depth`, counting the levels its printed text
261/// opens (`(`, `{`, `-`) as `parse` counts them, or of more terms than `search_max_terms`, a
262/// leaf or an empty group each being one. It walks a stack of its own, before any walk that
263/// recurses meets the tree.
264fn bound(t: &Term, lim: &Limits) -> Outcome<()> {
265 let (mut st, mut terms) = (vec![(t, At::Top, 0)], 0);
266 while let Some((t, at, d)) = st.pop() {
267 let (kids, item, d) = match (t, group(t, at)) {
268 (Term::Not(x), _) => (std::slice::from_ref(&**x), At::One, d + 1),
269 (_, Some((v, open, _, _, item))) => (v, item, d + !open.is_empty() as usize),
270 _ => (&[][..], At::One, d),
271 };
272 if d > lim.search_max_depth { return too_deep(lim); }
273 if kids.is_empty() {
274 terms += 1;
275 if terms > lim.search_max_terms { return too_many(lim); }
276 }
277 st.extend(kids.iter().map(|x| (x, item, d)));
278 }
279 Ok(())
280}
281
282fn too_many<T>(lim: &Limits) -> Outcome<T> {
283 Err(err!("The query has more than the limit of {} terms (search_max_terms).",
284 lim.search_max_terms; Excessive, Input))
285}
286
287fn too_deep<T>(lim: &Limits) -> Outcome<T> {
288 Err(err!("The query nests deeper than the limit of {} levels (search_max_depth).",
289 lim.search_max_depth; Excessive, Input))
290}
291
292// ┌───────────────────────────────────────────────────────────────────────────┐
293// │ TYPED OPERATORS │
294// └───────────────────────────────────────────────────────────────────────────┘
295
296#[derive(Clone, Debug, Eq, PartialEq)]
297enum Tok {
298 Open(char), // `(` all of, `{` any of
299 Close(char),
300 Neg,
301 Or,
302 Key(String),
303 Word(String),
304 Quoted(String),
305 Slashed(String),
306}
307
308#[derive(Clone, Copy)]
309enum Arg {
310 Is(&'static str, Filter),
311 Day(fn(Day) -> Filter),
312 Size(fn(u64) -> Filter),
313 Age(fn(Age) -> Filter),
314}
315
316// Each filter's key and value: the one list that reads them and writes them back.
317const FILTERS: [(&str, Arg); 11] = [
318 ("has", Arg::Is("attachment", Filter::HasAttachment)),
319 ("is", Arg::Is("read", Filter::Seen)),
320 ("is", Arg::Is("unread", Filter::Unseen)),
321 ("is", Arg::Is("starred", Filter::Flagged)),
322 ("after", Arg::Day(Filter::Since)),
323 ("before", Arg::Day(Filter::Before)),
324 ("older_than", Arg::Age(Filter::OlderThan)),
325 ("newer_than", Arg::Age(Filter::NewerThan)),
326 ("larger", Arg::Size(Filter::Larger)),
327 ("smaller", Arg::Size(Filter::Smaller)),
328 ("size", Arg::Size(Filter::Larger)), // Gmail's, written back as larger:
329];
330
331const SWITCHES: [&str; 3] = ["in", "scope", "match"];
332
333fn read(k: &str, a: Arg, v: &str) -> Outcome<Filter> {
334 match a {
335 Arg::Is(w, f) if w == v => Ok(f),
336 Arg::Is(..) => Err(err!("'{}:{}' is not an operator this search knows.", k, v; Invalid, Input)),
337 Arg::Day(f) => Day::parse(v).map(f),
338 Arg::Size(f) => size(v).map(f),
339 Arg::Age(f) => Age::parse(v).map(f),
340 }
341}
342
343fn written(f: Filter) -> String {
344 let v = match f {
345 Filter::Since(d) | Filter::Before(d) => d.to_string(),
346 Filter::OlderThan(a) | Filter::NewerThan(a) => a.to_string(),
347 Filter::Larger(n) | Filter::Smaller(n) => n.to_string(),
348 Filter::HasAttachment | Filter::Seen | Filter::Unseen | Filter::Flagged => String::new(),
349 };
350 FILTERS.iter().find_map(|(k, a)| {
351 let v = match a { Arg::Is(w, _) => w.to_string(), _ => v.clone() };
352 (read(k, *a, &v).ok() == Some(f)).then(|| fmt!("{}:{}", k, v))
353 }).unwrap_or_default()
354}
355
356/// Is `w` a key this language reads?
357fn is_key(w: &str) -> bool {
358 FILTERS.iter().any(|(k, _)| *k == w) || SWITCHES.contains(&w) || scope_of(w).is_some()
359}
360
361/// Is `w` shaped as a key, so that `w:` before text is read as an operator?
362fn key_shaped(w: &str) -> bool {
363 w.starts_with(|c: char| c.is_ascii_alphabetic()) && w.chars().all(|c| c.is_ascii_alphanumeric() || c == '_')
364}
365
366/// The text up to the closing `q`, from the opening one at `i`. In quotes `\"` is `"` and `\\`
367/// is `\`; a regex keeps every escape as written, `\/` among them, since its own reader takes
368/// `\/` for `/`.
369fn delimited(cs: &[char], i: &mut usize, q: char) -> Outcome<String> {
370 let mut out = String::new();
371 *i += 1;
372 while let Some(&c) = cs.get(*i) {
373 *i += 1;
374 match (c, cs.get(*i).copied()) {
375 (c, _) if c == q => return Ok(out),
376 ('\\', Some(n)) if q == '/' => { out.push(c); out.push(n); *i += 1; }
377 ('\\', Some(n)) if n == q || n == c => { out.push(n); *i += 1; }
378 (c, _) => out.push(c),
379 }
380 }
381 Err(err!("A {} opened is never closed.", q; Invalid, Input))
382}
383
384/// Gmail's forms this language does not have, refused with the way to search for the text.
385fn foreign<T>(k: &str, w: &str) -> Outcome<T> {
386 let quote = fmt!("to search for the text, put it in quotes: \"{}\".", w);
387 Err(match k {
388 "label" => err!("'label:' is not an operator here: a folder is searched with in:<folder>; {}", quote; Invalid, Input),
389 "+" => err!("'{}': Gmail's + (this word exactly) is not this search's; {}", w, quote; Invalid, Input),
390 "AROUND"=> err!("AROUND, Gmail's distance between words, is not this search's; {}", quote; Invalid, Input),
391 _ => err!("'{}:' is not an operator this search knows; {}", k, quote; Invalid, Input),
392 })
393}
394
395/// The token at `i`, or `None` at the end; `after_key` when the one before was a key.
396fn token(cs: &[char], i: &mut usize, after_key: bool) -> Outcome<Option<Tok>> {
397 let need = || err!("An operator needs its value after the ':'."; Invalid, Input);
398 let ends = |c: &char| c.is_whitespace() || ")}".contains(*c);
399 while cs.get(*i).is_some_and(|c| c.is_whitespace()) {
400 if after_key { return Err(need()); }
401 *i += 1;
402 }
403 let c = match cs.get(*i) {
404 Some(&c) => c,
405 None if after_key => return Err(need()),
406 None => return Ok(None),
407 };
408 let one = match c {
409 '(' | '{' => Some(Tok::Open(c)),
410 ')' | '}' => Some(Tok::Close(c)),
411 '-' if cs.get(*i + 1).is_some_and(|n| !ends(n)) => Some(Tok::Neg),
412 '"' | '/' => return Ok(Some(match res!(delimited(cs, i, c)) {
413 t if c == '"' => Tok::Quoted(t),
414 t => Tok::Slashed(t),
415 })),
416 _ => None,
417 };
418 if one.is_some() {
419 *i += 1;
420 return Ok(one);
421 }
422 let (st, mut j, mut e) = (*i, *i, *i);
423 while cs.get(j).is_some_and(|c| c.is_ascii_alphanumeric() || *c == '_') { j += 1; }
424 while cs.get(e).is_some_and(|c| !ends(c)) { e += 1; }
425 let (k, w): (String, String) = (cs[st..j].iter().collect(), cs[st..e].iter().collect());
426 if cs.get(j) == Some(&':') && key_shaped(&k) {
427 match is_key(&k.to_ascii_lowercase()) {
428 true => { *i = j + 1; return Ok(Some(Tok::Key(k.to_ascii_lowercase()))); }
429 false if cs.get(j + 1) != Some(&'/') => return foreign(&k, &w),
430 false => {} // a URL is text
431 }
432 }
433 *i = e;
434 match w.as_str() {
435 "OR" => Ok(Some(Tok::Or)),
436 "AROUND" => foreign("AROUND", &w),
437 _ if w.len() > 1 && w.starts_with('+') => foreign("+", &w),
438 _ => Ok(Some(Tok::Word(w))),
439 }
440}
441
442fn size(s: &str) -> Outcome<u64> {
443 let (n, mul) = match s.char_indices().last() {
444 Some((i, c)) if c.is_ascii_alphabetic() => (&s[..i], match c.to_ascii_uppercase() {
445 'K' => 1 << 10, 'M' => 1 << 20, 'G' => 1 << 30, _ => 0 }), // fixed: binary units
446 _ => (s, 1),
447 };
448 match n.parse::<u64>().ok().and_then(|n| n.checked_mul(mul)) {
449 Some(b) if mul > 0 => Ok(b),
450 _ => Err(err!("'{}' is not a size; write 500K, 2M or bytes.", s; Invalid, Input)),
451 }
452}
453
454impl Folders {
455 fn with(self, v: &str) -> Outcome<Self> {
456 Ok(match (self, v) {
457 (Self::Selected, "all") => Self::All { junk_trash: false },
458 (Self::Selected, "anywhere") => Self::All { junk_trash: true },
459 (Self::Selected, f) => Self::List(vec![f.to_string()]),
460 (Self::List(mut l), f) if f != "all" && f != "anywhere" => { l.push(f.to_string()); Self::List(l) }
461 _ => return Err(err!("in:all and in:anywhere stand alone, not beside another in:."; Invalid, Input)),
462 })
463 }
464}
465
466/// Gmail's grammar: terms side by side are all required, `OR` binds tighter, `-` tighter still.
467struct Parser<'a> {
468 cs: Vec<char>,
469 i: usize, // the next char to read
470 ahead: Option<Tok>, // read one ahead, so that the input is read only while it is in bounds
471 q: Query,
472 lim: &'a Limits,
473 depth: usize, // groups and '-' open around the next token
474 leaves: usize, // read so far, refused past the bound before the rest is built
475}
476
477impl Parser<'_> {
478
479 fn peek(&self) -> Option<&Tok> { self.ahead.as_ref() }
480
481 fn next(&mut self) -> Outcome<Option<Tok>> {
482 let key = matches!(self.ahead, Some(Tok::Key(_)));
483 let t = self.ahead.take();
484 self.ahead = res!(token(&self.cs, &mut self.i, key));
485 Ok(t)
486 }
487
488 fn down(&mut self) -> Outcome<()> {
489 self.depth += 1;
490 if self.depth > self.lim.search_max_depth { return too_deep(self.lim); }
491 Ok(())
492 }
493
494 fn count(&mut self) -> Outcome<()> {
495 self.leaves += 1;
496 if self.leaves > self.lim.search_max_terms { return too_many(self.lim); }
497 Ok(())
498 }
499
500 /// Terms up to `close`, all required; the whole query of one term is that term. `( )` is
501 /// always an all-of and `{ }` an any-of, whatever they hold, so that each reads back.
502 fn seq(&mut self, close: Option<char>, scope: Option<Scope>) -> Outcome<Term> {
503 let mut v = Vec::new();
504 loop {
505 match (self.peek(), close) {
506 (None, None) => break,
507 (None, Some(c)) => return Err(err!("A '{}' is never closed.", c; Invalid, Input)),
508 (Some(Tok::Close(c)), Some(e)) if *c == e => { res!(self.next()); break; }
509 (Some(Tok::Close(c)), _) => return Err(err!("A '{}' closes nothing.", c; Invalid, Input)),
510 _ => if let Some(t) = res!(self.or(scope, close.is_none())) { v.push(t); },
511 }
512 }
513 if v.is_empty() { res!(self.count()); } // an empty group is a term
514 Ok(match (close, v.len()) {
515 (None, 1) => v.remove(0),
516 (Some('}'), _) => Term::Any(v),
517 _ => Term::All(v),
518 })
519 }
520
521 fn or(&mut self, scope: Option<Scope>, top: bool) -> Outcome<Option<Term>> {
522 let first = res!(self.unary(scope, top));
523 if self.peek() != Some(&Tok::Or) {
524 return Ok(first);
525 }
526 let whole = || err!("in:, scope: and match: apply to the whole query, not beside OR."; Invalid, Input);
527 let mut v = vec![res!(first.ok_or_else(whole))];
528 while self.peek() == Some(&Tok::Or) {
529 res!(self.next());
530 let t = res!(self.unary(scope, false));
531 v.push(res!(t.ok_or_else(whole)));
532 }
533 Ok(Some(Term::Any(v)))
534 }
535
536 /// A term, or `None` where a switch was read into the query.
537 fn unary(&mut self, scope: Option<Scope>, top: bool) -> Outcome<Option<Term>> {
538 let text = |mode, text: String| match text.trim().is_empty() {
539 true => Err(err!("An empty text searches nothing; give the text to search for."; Invalid, Input)),
540 false => Ok(Some(Term::Text { scope, mode, text })),
541 };
542 if matches!(self.peek(), Some(Tok::Word(_) | Tok::Quoted(_) | Tok::Slashed(_))) { res!(self.count()); }
543 Ok(match res!(self.next()) {
544 Some(Tok::Neg) => {
545 res!(self.down());
546 let t = res!(self.unary(scope, false));
547 self.depth -= 1;
548 match t {
549 Some(t) => Some(Term::Not(Box::new(t))),
550 None => return Err(err!("in:, scope: and match: take no '-'."; Invalid, Input)),
551 }
552 }
553 Some(Tok::Open(c)) => {
554 res!(self.down());
555 let t = res!(self.seq(Some(if c == '(' { ')' } else { '}' }), scope));
556 self.depth -= 1;
557 Some(t)
558 }
559 Some(Tok::Word(w)) => res!(text(Mode::Word, w)),
560 Some(Tok::Quoted(s)) => res!(text(if s.contains(char::is_whitespace) { Mode::Phrase } else { Mode::Word }, s)),
561 Some(Tok::Slashed(s)) => { res!(Regex::new(&s)); res!(text(Mode::Regex, s)) }
562 // Below a scope only text stands, so this recursion is one step.
563 Some(Tok::Key(k)) => match (scope, scope_of(&k)) {
564 (Some(s), _) => return Err(err!("'{}:' takes text, not another operator.", word_of(s); Invalid, Input)),
565 (None, Some(s)) => res!(self.unary(Some(s), false)),
566 (None, None) => {
567 let t = res!(self.filter(&k, top));
568 if t.is_some() { res!(self.count()); }
569 t
570 }
571 },
572 Some(Tok::Or) => return Err(err!("OR stands between two terms: 'a OR b'."; Invalid, Input)),
573 Some(Tok::Close(c)) => return Err(err!("A '{}' closes nothing.", c; Invalid, Input)),
574 None => return Err(err!("The query ends where a term was due."; Invalid, Input)),
575 })
576 }
577
578 /// A filter leaf, or `None` where a switch of the whole query was set.
579 fn filter(&mut self, k: &str, top: bool) -> Outcome<Option<Term>> {
580 let v = match res!(self.next()) {
581 Some(Tok::Word(v)) | Some(Tok::Quoted(v)) if !v.is_empty() => v,
582 _ => return Err(err!("'{}:' needs a value.", k; Invalid, Input)),
583 };
584 let mut no = None;
585 for (_, a) in FILTERS.iter().filter(|(x, _)| *x == k) {
586 match read(k, *a, &v) {
587 Ok(f) => return Ok(Some(Term::Filter(f))),
588 Err(e) => no = Some(e),
589 }
590 }
591 if let Some(e) = no {
592 return Err(e);
593 }
594 let q = &mut self.q;
595 match (k, v.as_str()) {
596 ("in" | "scope" | "match", _) if !top => return Err(err!(
597 "'{}:' applies to the whole query; it cannot stand in ( ) or beside OR.", k; Invalid, Input)),
598 ("in", _) => q.folders = res!(std::mem::take(&mut q.folders).with(&v)),
599 ("scope", _) => for w in v.split(',') {
600 q.scopes.push(res!(scope_of(w).ok_or_else(|| err!("'{}' is not a scope.", w; Invalid, Input))));
601 },
602 ("match", "case") => q.match_case = true,
603 ("match", "word") => q.whole_word = true,
604 ("match", "substring") => q.substring = true,
605 _ => return Err(err!("'{}:{}' is not an operator this search knows.", k, v; Invalid, Input)),
606 }
607 Ok(None)
608 }
609}
610
611impl Query {
612 /// Reads Gmail's typed operators and this search's own switches (`match:case`,
613 /// `match:word`, `match:substring`, `scope:subject,body`); `Display` writes them back.
614 pub fn parse(s: &str, lim: &Limits) -> Outcome<Self> {
615 let cs: Vec<char> = s.chars().collect();
616 let (mut i, q) = (0, Self::default());
617 let ahead = res!(token(&cs, &mut i, false));
618 let mut p = Parser { cs, i, ahead, q, lim, depth: 0, leaves: 0 };
619 p.q.terms = res!(p.seq(None, None));
620 res!(bound(&p.q.terms, lim));
621 Ok(p.q)
622 }
623}
624
625/// In quotes, or a regex between slashes with an escape added only to a bare `/`.
626fn quoted(s: &str, q: char) -> String {
627 let mut out = String::from(q);
628 let mut esc = false;
629 for c in s.chars() {
630 match (q, c) {
631 ('"', '\\' | '"') => out.push('\\'),
632 ('/', '/') if !esc => out.push('\\'),
633 _ => {}
634 }
635 esc = q == '/' && c == '\\' && !esc;
636 out.push(c);
637 }
638 out.push(q);
639 out
640}
641
642/// A word bare where it reads back as the same word, else quoted.
643fn value(s: &str) -> String {
644 let key = s.split_once(':').is_some_and(|(k, _)| key_shaped(k));
645 match s.is_empty() || s == "OR" || s == "AROUND" || key || s.starts_with(['-', '/', '+'])
646 || s.contains(|c: char| c.is_whitespace() || "\"(){}".contains(c))
647 {
648 true => quoted(s, '"'),
649 false => s.to_string(),
650 }
651}
652
653fn leaf(t: &Term) -> String {
654 match t {
655 Term::Text { scope, mode, text } => fmt!("{}{}", scope.map_or(String::new(), |s| fmt!("{}:", word_of(s))),
656 match mode {
657 Mode::Word => value(text),
658 Mode::Phrase => quoted(text, '"'),
659 Mode::Regex => quoted(text, '/'),
660 }),
661 Term::Filter(f) => written(*f),
662 Term::Not(_) | Term::All(_) | Term::Any(_) => String::new(),
663 }
664}
665
666/// Where a term is written: the whole query, an item of a sequence, or an operand of `-` or `OR`.
667#[derive(Clone, Copy, Eq, PartialEq)]
668enum At { Top, Seq, One }
669
670/// A group's brackets, separator and its items' place, as written where it stands; `None` for a
671/// leaf or `-`.
672fn group(t: &Term, at: At) -> Option<(&[Term], &'static str, &'static str, &'static str, At)> {
673 Some(match t {
674 Term::All(v) if at == At::Top && v.len() != 1 => (v, "", " ", "", At::Seq),
675 Term::All(v) => (v, "(", " ", ")", At::Seq),
676 Term::Any(v) if at != At::One && v.len() > 1 => (v, "", " OR ", "", At::One),
677 Term::Any(v) => (v, "{", " ", "}", At::Seq),
678 Term::Text { .. } | Term::Filter(_) | Term::Not(_) => return None,
679 })
680}
681
682/// The typed text of a tree, each form reading back as the same tree. Written from a stack of its
683/// own, so that a tree built deep in code prints.
684fn term(t: &Term) -> String {
685 enum W<'a> { T(&'a Term, At), S(&'static str) }
686 let (mut out, mut st) = (String::new(), vec![W::T(t, At::Top)]);
687 while let Some(w) = st.pop() {
688 let (t, at) = match w {
689 W::S(s) => { out.push_str(s); continue; }
690 W::T(t, at) => (t, at),
691 };
692 let (v, open, sep, close, item) = match (t, group(t, at)) {
693 (Term::Not(x), _) => { out.push('-'); st.push(W::T(x, At::One)); continue; }
694 (_, Some(g)) => g,
695 (_, None) => { out.push_str(&leaf(t)); continue; }
696 };
697 out.push_str(open);
698 st.push(W::S(close));
699 for (i, x) in v.iter().enumerate().rev() {
700 st.push(W::T(x, item));
701 if i > 0 { st.push(W::S(sep)); }
702 }
703 }
704 out
705}
706
707impl fmt::Display for Query {
708 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
709 let mut out: Vec<String> = vec![term(&self.terms)];
710 match &self.folders {
711 Folders::Selected => {}
712 Folders::List(l) => out.extend(l.iter().map(|x| fmt!("in:{}", value(x)))),
713 Folders::All { junk_trash: false } => out.push("in:all".into()),
714 Folders::All { junk_trash: true } => out.push("in:anywhere".into()),
715 }
716 if !self.scopes.is_empty() {
717 out.push(fmt!("scope:{}", self.scopes.iter().map(|s| word_of(*s)).collect::<Vec<_>>().join(",")));
718 }
719 if self.match_case { out.push("match:case".into()); }
720 if self.whole_word { out.push("match:word".into()); }
721 if self.substring { out.push("match:substring".into()); }
722 out.retain(|x| !x.is_empty());
723 write!(f, "{}", out.join(" "))
724 }
725}
726
727// ┌───────────────────────────────────────────────────────────────────────────┐
728// │ THE MATCHER │
729// └───────────────────────────────────────────────────────────────────────────┘
730
731/// The bounds of one search, from the caller's configuration.
732#[derive(Clone, Debug)]
733pub struct Limits {
734 pub search_regex_max_len: usize, // characters of one pattern before it is compiled
735 pub search_max_depth: usize, // groups and '-' nested, sized to the smallest stack that parses
736 pub search_max_terms: usize, // text and filter leaves of one query
737 pub snippet_chars: usize,
738 pub snippets_per_part: usize,
739 pub search_marks_max: usize, // marks in one message's text, and again in its HTML; the rest counted
740 pub search_regex_min_literal: usize, // characters of a cut or regex literal worth a server key
741 pub search_key_max_bytes: usize, // of the SEARCH arguments `plan` writes
742 pub search_page_rows: usize, // hits of one page of a server search
743 pub search_confirm_max_bytes: u32, // fetched to confirm one page's candidates
744 pub search_scan_max_messages: usize, // candidates a page checks; UIDs it spans where the key is not complete
745 pub search_max_folders: usize, // of one run; the rest named as skipped
746}
747
748impl Limits {
749 /// The defaults a configuration overrides, until `routes.mail` serves them (design I10).
750 pub const DEFAULT: Self = Self {
751 search_regex_max_len: 200,
752 search_max_depth: 16,
753 search_max_terms: 50,
754 snippet_chars: 80,
755 snippets_per_part: 3,
756 search_marks_max: 500,
757 search_regex_min_literal: 3,
758 search_key_max_bytes: 8192, // RFC 7162 §4's advice for a command line
759 search_page_rows: 20,
760 search_confirm_max_bytes: 2 << 20,
761 search_scan_max_messages: 2000,
762 search_max_folders: 50,
763 };
764}
765
766impl Default for Limits {
767 fn default() -> Self { Self::DEFAULT }
768}
769
770/// A message as the matcher reads it: its bytes and what the store knows beside them.
771#[derive(Clone, Debug)]
772pub struct Mail<'a> {
773 pub raw: &'a [u8],
774 pub seen: bool,
775 pub flagged: bool,
776 pub size: u64,
777 pub day: Option<Day>, // INTERNALDATE's, or the Date: field's where only that is held
778}
779
780/// A message's text as a server corpus fetches it by part (the header block is `Mail::raw`).
781#[derive(Clone, Debug, Default)]
782pub struct Fetched {
783 pub body: String, // `message::readable` of the text bodies fetched
784 pub names: Vec<String>, // the attachments' names
785 pub unknown: Vec<Scope>, // not read whole: a body cut at the byte bound, a name the structure lacks
786}
787
788#[derive(Clone, Debug, Eq, PartialEq)]
789pub struct Snippet {
790 pub text: String,
791 pub spans: Vec<Span>, // within `text`
792 pub cut: bool, // the last span runs on past the end of `text`
793}
794
795#[derive(Clone, Debug, Eq, PartialEq)]
796pub struct HitPart {
797 pub scope: Scope,
798 pub snippets: Vec<Snippet>,
799}
800
801#[derive(Clone, Debug, Default, Eq, PartialEq)]
802pub struct Hit {
803 pub parts: Vec<HitPart>, // empty for a query with no text
804}
805
806/// `Term` with each text compiled, its children by index into the matcher's nodes.
807enum Node {
808 Leaf(Regex, Vec<Scope>), // scopes empty: everywhere
809 Filter(Filter),
810 Not(usize),
811 All(Vec<usize>),
812 Any(Vec<usize>),
813}
814
815pub struct Matcher {
816 nodes: Vec<Node>, // each child before its parent, the root last
817 lim: Limits,
818}
819
820/// The message as the text leaves read it.
821type Parts = Vec<(Scope, String)>;
822
823/// One message's evaluation: its parts, read when a leaf first needs them, and each node's answer.
824struct Eval<'a> {
825 parts: Option<Parts>,
826 vals: Vec<Option<bool>>,
827 fetched: Option<&'a Fetched>,
828}
829
830fn is_bidi(c: char) -> bool {
831 matches!(c, '\u{061C}' | '\u{200E}' | '\u{200F}' | '\u{202A}'..='\u{202E}' | '\u{2066}'..='\u{2069}')
832}
833
834/// The one reading of a message's text, from its bytes or, with `f`, from its header block and
835/// the parts a corpus fetched.
836fn parts(raw: &[u8], f: Option<&Fetched>) -> Parts {
837 let pm = ParsedMessage::parse(raw);
838 let bcc = decode_words(&field(&headers(raw), "bcc").unwrap_or_default());
839 let (body, names) = match f {
840 Some(f) => (f.body.clone(), f.names.clone()),
841 None => (pm.body, pm.attachments),
842 };
843 let mut text = vec![(Scope::From, pm.from), (Scope::To, pm.to), (Scope::Cc, pm.cc),
844 (Scope::Bcc, bcc), (Scope::Subject, pm.subject), (Scope::Body, body)];
845 text.extend(names.into_iter().map(|a| (Scope::Attachment, a)));
846 for (_, t) in text.iter_mut() {
847 if t.contains(is_bidi) { t.retain(|c| !is_bidi(c)); }
848 if !t.is_ascii() { *t = nfc(t); }
849 }
850 text
851}
852
853impl Matcher {
854
855 /// `today` is the caller's day, against which `older_than:` and `newer_than:` are resolved.
856 pub fn new(q: &Query, lim: &Limits, today: Day) -> Outcome<Self> {
857 res!(bound(&q.terms, lim));
858 let mut m = Self { nodes: Vec::new(), lim: lim.clone() };
859 res!(m.node(&q.terms, q, today));
860 Ok(m)
861 }
862
863 fn node(&mut self, t: &Term, q: &Query, today: Day) -> Outcome<usize> {
864 let n = match t {
865 Term::Filter(Filter::OlderThan(a)) => Node::Filter(Filter::Before(a.before(today))),
866 Term::Filter(Filter::NewerThan(a)) => Node::Filter(Filter::Since(a.before(today))),
867 Term::Filter(f) => Node::Filter(*f),
868 Term::Not(x) => Node::Not(res!(self.node(x, q, today))),
869 Term::All(v) | Term::Any(v) => {
870 let mut ids = Vec::with_capacity(v.len());
871 for x in v { ids.push(res!(self.node(x, q, today))); }
872 if matches!(t, Term::All(_)) { Node::All(ids) } else { Node::Any(ids) }
873 }
874 Term::Text { scope, mode, text } => {
875 if text.trim().is_empty() {
876 return Err(err!("An empty text searches nothing; give the text to search for."; Invalid, Input));
877 }
878 let text = &res!(leaf_text(text, &self.lim));
879 let src = match mode {
880 Mode::Phrase if !q.substring => text.split_whitespace().map(quote).collect::<Vec<_>>().join(r"\s+"),
881 Mode::Word | Mode::Phrase => quote(text),
882 Mode::Regex => text.clone(),
883 };
884 let src = match q.whole_word {
885 true => fmt!(r"\b{{start-half}}(?:{})\b{{end-half}}", src),
886 false => src,
887 };
888 Node::Leaf(res!(Regex::with_case(&src, !q.match_case)), scope.map_or(q.scopes.clone(), |s| vec![s]))
889 }
890 };
891 self.nodes.push(n);
892 Ok(self.nodes.len() - 1)
893 }
894
895 /// The hit, or `None`. An error means the answer depends on what could not be known (a
896 /// search that could not finish, a day the store does not hold), so it is unknown.
897 pub fn matches(&self, mail: &Mail) -> Outcome<Option<Hit>> {
898 self.decide(mail, None)
899 }
900
901 /// As `matches`, of a message a corpus fetched by part, `mail.raw` its header block. A scope
902 /// `f` could not read whole makes a leaf over it unknown only where nothing matched.
903 pub fn matches_fetched(&self, mail: &Mail, f: &Fetched) -> Outcome<Option<Hit>> {
904 self.decide(mail, Some(f))
905 }
906
907 /// Could an attachment fact of the query (a text over the names, `has:attachment`) hold on a
908 /// message of these names? True where one holds or cannot be decided.
909 pub fn names_may_hold(&self, f: &Fetched) -> bool {
910 let names = parts(b"", Some(f));
911 let unread = f.unknown.contains(&Scope::Attachment);
912 self.nodes.iter().any(|n| match n {
913 Node::Leaf(re, sc) if sc.is_empty() || sc.contains(&Scope::Attachment) => unread
914 || names.iter().any(|(s, x)| *s == Scope::Attachment && !matches!(re.find(x), Ok(None))),
915 Node::Filter(Filter::HasAttachment) => unread || names.iter().any(|(s, _)| *s == Scope::Attachment),
916 _ => false,
917 })
918 }
919
920 fn decide(&self, mail: &Mail, fetched: Option<&Fetched>) -> Outcome<Option<Hit>> {
921 let mut e = Eval { parts: None, vals: vec![None; self.nodes.len()], fetched };
922 let root = self.nodes.len() - 1;
923 if !res!(self.eval(root, mail, &mut e)) {
924 return Ok(None);
925 }
926 self.settle(root, mail, &mut e);
927 let parts = match e.parts {
928 None => return Ok(Some(Hit { parts: Vec::new() })),
929 Some(p) => p,
930 };
931 let mut spans = vec![Vec::new(); parts.len()];
932 self.mark(root, &e.vals, &parts, &mut spans);
933 Ok(Some(Hit { parts: parts.iter().zip(spans).filter(|(_, v)| !v.is_empty())
934 .map(|((s, t), mut v)| {
935 v.sort_by_key(|x| x.start);
936 HitPart { scope: *s, snippets: self.snippets(t, &v) }
937 })
938 .collect() }))
939 }
940
941 /// Three-valued, each answer kept for the marks.
942 fn eval(&self, i: usize, mail: &Mail, e: &mut Eval<'_>) -> Outcome<bool> {
943 let b = match &self.nodes[i] {
944 Node::Not(x) => !res!(self.eval(*x, mail, e)),
945 Node::All(v) => res!(self.group(v, false, mail, e)),
946 Node::Any(v) => res!(self.group(v, true, mail, e)),
947 Node::Leaf(re, scopes) => {
948 let f = e.fetched;
949 res!(leaf_holds(re, scopes, e.parts.get_or_insert_with(|| parts(mail.raw, f)),
950 f.map_or(&[][..], |f| &f.unknown)))
951 }
952 Node::Filter(f) => match (f, mail.day) {
953 (Filter::Since(d), Some(m)) => m >= *d,
954 (Filter::Before(d), Some(m)) => m < *d,
955 (Filter::Since(_) | Filter::Before(_), None) => return Err(err!(
956 "The mail's day is not known, so a date bound cannot be decided."; Missing, Input)),
957 (Filter::Seen, _) => mail.seen,
958 (Filter::Unseen, _) => !mail.seen,
959 (Filter::OlderThan(_) | Filter::NewerThan(_), _) => return Err(err!(
960 "A relative day reached the matcher unresolved."; Bug)),
961 (Filter::Flagged, _) => mail.flagged,
962 (Filter::Larger(b), _) => mail.size > *b,
963 (Filter::Smaller(b), _) => mail.size < *b,
964 (Filter::HasAttachment, _) => {
965 let f = e.fetched;
966 f.is_some_and(|f| f.unknown.contains(&Scope::Attachment))
967 || e.parts.get_or_insert_with(|| parts(mail.raw, f)).iter().any(|(s, _)| *s == Scope::Attachment)
968 }
969 },
970 };
971 if let Some(x) = e.vals.get_mut(i) { *x = Some(b); }
972 Ok(b)
973 }
974
975 /// Stops at the first child that decides the group; unknown (an error) only when none does
976 /// and one could not be decided.
977 fn group(&self, v: &[usize], any: bool, mail: &Mail, e: &mut Eval<'_>) -> Outcome<bool> {
978 let mut unknown = None;
979 for &x in v {
980 match self.eval(x, mail, e) {
981 Ok(b) if b == any => return Ok(any),
982 Ok(_) => {}
983 Err(err) => unknown = Some(err),
984 }
985 }
986 unknown.map_or(Ok(!any), Err)
987 }
988
989 /// On a hit, searches the children a group's stop left unsearched below each group that held,
990 /// so that every alternative that holds is marked. The answer is already decided; each leaf
991 /// is still searched at most once.
992 fn settle(&self, i: usize, mail: &Mail, e: &mut Eval<'_>) {
993 if let Node::All(v) | Node::Any(v) = &self.nodes[i] {
994 for &x in v {
995 if e.vals.get(x) == Some(&None) { self.eval(x, mail, e).ok(); } // unknown marks nothing
996 if e.vals.get(x) == Some(&Some(true)) { self.settle(x, mail, e); }
997 }
998 }
999 }
1000
1001 /// The spans of the leaves that held on the road that decided the hit: each child that held
1002 /// below a node that held, never below a `Not`.
1003 fn mark(&self, i: usize, vals: &[Option<bool>], parts: &Parts, spans: &mut [Vec<Span>]) {
1004 match &self.nodes[i] {
1005 Node::Leaf(re, scopes) => for (j, (s, t)) in parts.iter().enumerate() {
1006 if !scopes.is_empty() && !scopes.contains(s) { continue; }
1007 for m in re.find_iter(t).take(self.lim.snippets_per_part.max(1)) {
1008 match (m, spans.get_mut(j)) {
1009 (Ok(m), Some(v)) => v.push(m),
1010 _ => break, // the hit stands; its marks end here
1011 }
1012 }
1013 },
1014 Node::All(v) | Node::Any(v) => for &x in v {
1015 if vals.get(x) == Some(&Some(true)) { self.mark(x, vals, parts, spans); }
1016 },
1017 Node::Not(_) | Node::Filter(_) => {}
1018 }
1019 }
1020
1021 /// Windows of `snippet_chars` round the spans, each centred on a span that fits it, a span
1022 /// inside a window joining it, and a span longer than its window clipped to it.
1023 fn snippets(&self, t: &str, spans: &[Span]) -> Vec<Snippet> {
1024 let mut out: Vec<Snippet> = Vec::new();
1025 let (mut a, mut b) = (0, 0);
1026 for s in spans {
1027 if let (true, Some(l)) = (s.start >= a && s.end <= b, out.last_mut()) {
1028 l.spans.push(Span { start: s.start - a, end: s.end - a });
1029 continue;
1030 }
1031 if out.len() >= self.lim.snippets_per_part { break; }
1032 let w = self.lim.snippet_chars;
1033 let span = t.get(s.start..s.end).map_or(0, |x| x.chars().take(w + 1).count());
1034 a = off_mark(t, back(t, s.start, w.saturating_sub(span) / 2), s.start, true);
1035 b = off_mark(t, fwd(t, a, w), s.end, false);
1036 out.push(Snippet {
1037 text: t.get(a..b).unwrap_or("").to_string(),
1038 spans: vec![Span { start: s.start - a, end: s.end.min(b) - a }],
1039 cut: s.end > b,
1040 });
1041 }
1042 out
1043 }
1044}
1045
1046/// True once any part in scope holds the pattern; unknown only when none does and one could not
1047/// be searched to its end, or was not read whole (`unread`).
1048fn leaf_holds(re: &Regex, scopes: &[Scope], parts: &Parts, unread: &[Scope]) -> Outcome<bool> {
1049 let mut unknown = None;
1050 for (s, t) in parts {
1051 if !scopes.is_empty() && !scopes.contains(s) { continue; }
1052 match re.find(t) {
1053 Ok(Some(_)) => return Ok(true),
1054 Ok(None) => {}
1055 Err(e) => unknown = Some(err!(e,
1056 "The search of {} could not finish; the answer is unknown.", word_of(*s); Excessive, Input)),
1057 }
1058 }
1059 match (unknown, unread.iter().find(|s| scopes.is_empty() || scopes.contains(s))) {
1060 (Some(e), _) => Err(e),
1061 (None, Some(s)) => Err(err!("The {} was not read whole; the answer is unknown.", word_of(*s); Excessive, Input)),
1062 (None, None) => Ok(false),
1063 }
1064}
1065
1066/// The byte offset `n` characters before `at`, or 0.
1067fn back(t: &str, at: usize, n: usize) -> usize {
1068 match n {
1069 0 => at,
1070 _ => t.get(..at).and_then(|h| h.char_indices().rev().nth(n - 1)).map_or(0, |(i, _)| i),
1071 }
1072}
1073
1074/// `at` moved off a combining mark, so that a window never parts one from its letter: forward
1075/// to `lim` for a window's start, back to it for its end.
1076fn off_mark(t: &str, mut at: usize, lim: usize, start: bool) -> usize {
1077 while t.get(at..).and_then(|x| x.chars().next()).is_some_and(|c| combining_class(c) != 0) {
1078 match start {
1079 true if at < lim => at = fwd(t, at, 1),
1080 false if at > lim => at = back(t, at, 1),
1081 _ => break,
1082 }
1083 }
1084 at
1085}
1086
1087/// The byte offset `n` characters after `at`, or the end.
1088fn fwd(t: &str, at: usize, n: usize) -> usize {
1089 t.get(at..).and_then(|h| h.char_indices().nth(n)).map_or(t.len(), |(i, _)| at + i)
1090}
1091
1092
1093// ── Marks on the text a reader is shown ─────────────────────────────────
1094
1095/// The leaves on the road that decided a hit, to mark the text a reader is shown with.
1096pub struct Road<'a> {
1097 m: &'a Matcher,
1098 leaves: Vec<usize>,
1099 pub scopes: Vec<Scope>, // the message's own parts it holds a span in, in their order
1100}
1101
1102impl Matcher {
1103
1104 /// The road that decided a hit on `mail`, with every alternative that held on it (the second
1105 /// pass), or `None` on a miss.
1106 pub fn road(&self, mail: &Mail) -> Outcome<Option<Road<'_>>> {
1107 let mut e = Eval { parts: None, vals: vec![None; self.nodes.len()], fetched: None };
1108 let root = self.nodes.len() - 1;
1109 if !res!(self.eval(root, mail, &mut e)) {
1110 return Ok(None);
1111 }
1112 self.settle(root, mail, &mut e);
1113 let parts = e.parts.unwrap_or_default();
1114 let mut spans = vec![Vec::new(); parts.len()];
1115 self.mark(root, &e.vals, &parts, &mut spans);
1116 let mut scopes = Vec::new();
1117 for ((s, _), v) in parts.iter().zip(spans) {
1118 if !v.is_empty() && !scopes.contains(s) { scopes.push(*s); }
1119 }
1120 let mut r = Road { m: self, leaves: Vec::new(), scopes };
1121 r.walk(root, &e.vals);
1122 Ok(Some(r))
1123 }
1124}
1125
1126impl Road<'_> {
1127
1128 fn walk(&mut self, i: usize, vals: &[Option<bool>]) {
1129 let m = self.m;
1130 match &m.nodes[i] {
1131 Node::Leaf(..) => self.leaves.push(i),
1132 Node::All(v) | Node::Any(v) => for &x in v {
1133 if vals.get(x) == Some(&Some(true)) { self.walk(x, vals); }
1134 },
1135 Node::Not(_) | Node::Filter(_) => {}
1136 }
1137 }
1138
1139 /// The spans of the road's leaves for scope `s` in `shown`, overlaps joined, in `shown`'s own
1140 /// offsets: the matcher's cleaning and, with `html`, the character references of one text
1141 /// node of HTML are mapped back. At most `max` spans, and the number found.
1142 pub fn spans(&self, s: Scope, shown: &str, html: bool, max: usize) -> (Vec<Span>, usize) {
1143 let c;
1144 let (text, map) = match shown.is_ascii() && !(html && shown.contains('&')) {
1145 true => (shown, &[][..]),
1146 false => { c = Clean::new(shown, html); (c.text.as_str(), &c.map[..]) }
1147 };
1148 let mut its: Vec<_> = self.leaves.iter().filter_map(|&l| match &self.m.nodes[l] {
1149 Node::Leaf(re, sc) if sc.is_empty() || sc.contains(&s) => Some(re.find_iter(text)
1150 .map_while(|x| x.ok()).filter(|x| x.end > x.start).peekable()), // unfinished: its marks end
1151 _ => None,
1152 }).collect();
1153 let (mut out, mut n, mut cur) = (Vec::new(), 0, None::<Span>);
1154 loop {
1155 let next = its.iter_mut().enumerate().filter_map(|(k, it)| it.peek().map(|x| (x.start, k))).min();
1156 let x = match next.and_then(|(_, k)| its.get_mut(k)).and_then(|it| it.next()) {
1157 Some(x) => x,
1158 None => break,
1159 };
1160 if let Some(p) = cur.as_mut().filter(|p| x.start < p.end) {
1161 p.end = p.end.max(x.end);
1162 continue;
1163 }
1164 if let Some(p) = cur.replace(x) {
1165 n += 1;
1166 if out.len() < max { out.push(shown_span(map, p)); }
1167 }
1168 }
1169 if let Some(p) = cur {
1170 n += 1;
1171 if out.len() < max { out.push(shown_span(map, p)); }
1172 }
1173 (out, n)
1174 }
1175}
1176
1177/// A shown text as `parts` reads it, bidirectional controls removed and in form C, with each
1178/// stretch that changed as [from, to] in `text` and [from, to] in the shown text, in order;
1179/// between them the two run on together.
1180struct Clean {
1181 text: String,
1182 map: Vec<[usize; 4]>,
1183}
1184
1185impl Clean {
1186
1187 fn new(shown: &str, html: bool) -> Self {
1188 let mut c = Self { text: String::with_capacity(shown.len()), map: Vec::new() };
1189 let mut i = 0;
1190 while let Some(ch) = shown.get(i..).and_then(|r| r.chars().next()) {
1191 if let Some((n, t)) = if html && ch == '&' { reference(&shown[i..]) } else { None } {
1192 c.put(&nfc(&t.replace(is_bidi, "")), i, i + n);
1193 i += n;
1194 continue;
1195 }
1196 // To the next ASCII character: form C never joins across one.
1197 let w = i + ch.len_utf8();
1198 let j = shown[w..].find(|x: char| x.is_ascii()).map_or(shown.len(), |k| w + k);
1199 c.stretch(&shown[i..j], i);
1200 i = j;
1201 }
1202 c
1203 }
1204
1205 /// Each starter with its marks apart where form C keeps them apart, else the stretch whole.
1206 fn stretch(&mut self, seg: &str, at: usize) {
1207 let end = at + seg.len();
1208 if !seg.contains(is_bidi) && (seg.is_ascii() || nfc(seg) == seg) {
1209 return self.text.push_str(seg);
1210 }
1211 let mut subs: Vec<(usize, usize, String)> = Vec::new(); // shown from, to; the kept text
1212 for (k, ch) in seg.char_indices().filter(|(_, x)| !is_bidi(*x)) {
1213 let b = at + k + ch.len_utf8();
1214 match subs.last_mut() {
1215 Some(l) if combining_class(ch) != 0 => { l.1 = b; l.2.push(ch); }
1216 _ => subs.push((at + k, b, ch.to_string())),
1217 }
1218 }
1219 let whole = nfc(&subs.iter().map(|x| x.2.as_str()).collect::<String>());
1220 let each: Vec<String> = subs.iter().map(|x| nfc(&x.2)).collect();
1221 if each.concat() != whole {
1222 return self.put(&whole, at, end);
1223 }
1224 let mut s = at;
1225 for ((a, b, t), n) in subs.iter().zip(each) {
1226 if *a > s { self.put("", s, *a); }
1227 match *t == n && b - a == n.len() {
1228 true => self.text.push_str(&n),
1229 false => self.put(&n, *a, *b),
1230 }
1231 s = *b;
1232 }
1233 if s < end { self.put("", s, end); }
1234 }
1235
1236 fn put(&mut self, t: &str, a: usize, b: usize) {
1237 let c = self.text.len();
1238 self.text.push_str(t);
1239 self.map.push([c, self.text.len(), a, b]);
1240 }
1241}
1242
1243/// A span of the cleaned text in the shown text's offsets, widened to any stretch it cuts.
1244fn shown_span(map: &[[usize; 4]], p: Span) -> Span {
1245 let at = |c: usize, end: bool| {
1246 let k = map.partition_point(|r| r[0] < c || (!end && r[0] == c));
1247 match k.checked_sub(1).and_then(|k| map.get(k)) {
1248 Some(r) if c < r[1] || (end && c == r[1]) => if end { r[3] } else { r[2] },
1249 Some(r) => c - r[1] + r[3],
1250 None => c,
1251 }
1252 };
1253 Span { start: at(p.start, false), end: at(p.end, true) }
1254}
1255
1256/// The JDAT form is the typed text, so a page, a daimon and a config file write one language.
1257/// Reading it takes the caller's `Limits`, as `parse` does.
1258#[cfg(feature = "jdat")]
1259mod jdat {
1260 use super::{
1261 Limits,
1262 Query,
1263 };
1264
1265 use oxedyne_fe2o3_core::prelude::*;
1266 use oxedyne_fe2o3_jdat::prelude::*;
1267
1268 impl ToDat for Query {
1269 fn to_dat(&self) -> Outcome<Dat> {
1270 Ok(dat!(self.to_string()))
1271 }
1272 }
1273
1274 impl Query {
1275 pub fn from_dat(d: Dat, lim: &Limits) -> Outcome<Self> {
1276 match d {
1277 Dat::Str(s) => Query::parse(&s, lim),
1278 d => Err(err!("A query is a string of search text, not {:?}.", d.kind(); Invalid, Input)),
1279 }
1280 }
1281 }
1282}
1283
1284// ┌───────────────────────────────────────────────────────────────────────────┐
1285// │ THE SERVER'S KEY │
1286// └───────────────────────────────────────────────────────────────────────────┘
1287
1288/// What the planner knows of the server it narrows on.
1289#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1290pub struct Server {
1291 pub gmail: bool, // `X-GM-EXT-1`: SEARCH by word, and `X-GM-RAW`
1292 pub names: bool, // false: each attachment fact (a text over the names, `has:attachment`) taken as false
1293}
1294
1295/// The least the confirm must fetch of a candidate, each including those before it.
1296#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
1297pub enum Needs {
1298 Meta, // flags, size, INTERNALDATE
1299 Headers,
1300 Structure, // the attachments' names
1301 Text,
1302}
1303
1304#[derive(Clone, Debug, Eq, PartialEq)]
1305pub struct Plan {
1306 pub key: Option<SearchKey>, // `None`: nothing can match, so nothing is sent
1307 pub complete: bool, // every leaf narrowed the key; else the run is a bounded scan
1308 pub needs: Needs,
1309}
1310
1311// fixed: ASCII that a server may read otherwise than the matcher: `k` and `s`, which KELVIN SIGN
1312// and LONG S fold to; `;` and the backtick, which NFC makes of U+037E and U+1FEF; and what HTML
1313// writes as an entity. A key's text is cut at each.
1314const KEY_CUT: &str = "kKsS;`&<>\"'";
1315
1316/// The mails a server can name: every one, none, or those a key selects.
1317#[derive(Clone, Debug)]
1318enum Set {
1319 Every,
1320 Empty,
1321 Key(SearchKey),
1322}
1323
1324/// A term's keys: a superset of the mails it holds for, a subset, and whether each was made with
1325/// every leaf below it.
1326struct Keys {
1327 sup: Set,
1328 sub: Set,
1329 sup_full: bool,
1330 sub_full: bool,
1331}
1332
1333/// The server's key for a query: a superset of the mails that can be the matcher's hits (S2), a
1334/// subset under each `-`. A server reads a mail's text otherwise than the matcher (no attachment's
1335/// name in TEXT, HTML's tags and URLs in BODY, NFC, a field given twice), so no text key is exact
1336/// and an attachment's name has none; a word split by a tag or a bidirectional control is missed
1337/// by a server search. A pure function of its arguments; `today` is the matcher's day.
1338pub fn plan(q: &Query, srv: &Server, lim: &Limits, today: Day) -> Outcome<Plan> {
1339 res!(bound(&q.terms, lim));
1340 let mut needs = Needs::Meta;
1341 let k = res!(keys(&q.terms, q, srv, lim, today, &mut needs));
1342 let (sup, fits) = fit(k.sup, true, lim);
1343 Ok(Plan {
1344 key: match sup {
1345 Set::Every => Some(SearchKey::All),
1346 Set::Empty => None,
1347 Set::Key(k) => Some(k),
1348 },
1349 complete: k.sup_full && fits,
1350 needs,
1351 })
1352}
1353
1354/// By polarity: `-x` takes the complement of the subset of `x` as its superset, and of the
1355/// superset as its subset. Bounded by `bound`.
1356fn keys(t: &Term, q: &Query, srv: &Server, lim: &Limits, today: Day, needs: &mut Needs) -> Outcome<Keys> {
1357 let day = |d: Day, n: i64| days_from_civil(d.year as i32, d.month as u32, d.day as u32) + n;
1358 let exact = |k: SearchKey| Keys { sup: Set::Key(k.clone()), sub: Set::Key(k), sup_full: true, sub_full: true };
1359 Ok(match t {
1360 Term::Not(x) => {
1361 let k = res!(keys(x, q, srv, lim, today, needs));
1362 Keys { sup: not(k.sub), sub: not(k.sup), sup_full: k.sub_full, sub_full: k.sup_full }
1363 }
1364 Term::All(v) | Term::Any(v) => {
1365 let mut ks = Vec::with_capacity(v.len());
1366 for x in v { ks.push(res!(keys(x, q, srv, lim, today, needs))); }
1367 let full = (ks.iter().all(|k| k.sup_full), ks.iter().all(|k| k.sub_full));
1368 let (sups, subs): (Vec<Set>, Vec<Set>) = ks.into_iter().map(|k| (k.sup, k.sub)).unzip();
1369 let any = matches!(t, Term::Any(_));
1370 let ((sup, a), (sub, b)) = (join(sups, any, true, lim), join(subs, any, false, lim));
1371 Keys { sup, sub, sup_full: full.0 && a, sub_full: full.1 && b }
1372 }
1373 // The server takes SINCE and BEFORE by its own day, at most a day from the matcher's.
1374 Term::Filter(f) => match f {
1375 Filter::Since(d) => Keys { sup: Set::Key(SearchKey::Since(day(*d, -1))),
1376 sub: Set::Key(SearchKey::Since(day(*d, 1))), sup_full: true, sub_full: true },
1377 Filter::Before(d) => Keys { sup: Set::Key(SearchKey::Before(day(*d, 1))),
1378 sub: Set::Key(SearchKey::Before(day(*d, -1))), sup_full: true, sub_full: true },
1379 Filter::OlderThan(a) => res!(keys(&Term::Filter(Filter::Before(a.before(today))), q, srv, lim, today, needs)),
1380 Filter::NewerThan(a) => res!(keys(&Term::Filter(Filter::Since(a.before(today))), q, srv, lim, today, needs)),
1381 Filter::Seen => exact(SearchKey::Flag(Flag::Seen, true)),
1382 Filter::Unseen => exact(SearchKey::Flag(Flag::Seen, false)),
1383 Filter::Flagged => exact(SearchKey::Flag(Flag::Flagged, true)),
1384 Filter::Larger(n) => exact(SearchKey::Larger(*n)),
1385 Filter::Smaller(n) => exact(SearchKey::Smaller(*n)),
1386 Filter::HasAttachment if !srv.names => Keys { sup: Set::Empty, sub: Set::Empty, sup_full: true, sub_full: true },
1387 Filter::HasAttachment => {
1388 *needs = (*needs).max(Needs::Structure);
1389 match srv.gmail {
1390 true => Keys { sup: Set::Key(SearchKey::GmRaw("has:attachment".into())), sub: Set::Empty,
1391 sup_full: true, sub_full: false },
1392 false => Keys { sup: Set::Every, sub: Set::Empty, sup_full: false, sub_full: false },
1393 }
1394 }
1395 },
1396 Term::Text { scope, mode, text } => res!(text_keys(*scope, *mode, text, q, srv, lim, needs)),
1397 })
1398}
1399
1400/// A text leaf's superset: in some scope, every piece of text each of its hits holds.
1401fn text_keys(scope: Option<Scope>, mode: Mode, text: &str, q: &Query, srv: &Server, lim: &Limits, needs: &mut Needs)
1402 -> Outcome<Keys>
1403{
1404 let text = res!(leaf_text(text, lim));
1405 let scopes = match (scope, q.scopes.is_empty()) {
1406 (Some(s), _) => vec![s],
1407 (None, true) => SCOPES.iter().map(|(s, _)| *s).collect(),
1408 (None, false) => q.scopes.clone(),
1409 };
1410 let scopes: Vec<Scope> = scopes.into_iter().filter(|s| srv.names || *s != Scope::Attachment).collect();
1411 if scopes.is_empty() {
1412 return Ok(Keys { sup: Set::Empty, sub: Set::Empty, sup_full: true, sub_full: true }); // its names only, taken as false
1413 }
1414 for s in &scopes {
1415 *needs = (*needs).max(match s { Scope::Body => Needs::Text, Scope::Attachment => Needs::Structure, _ => Needs::Headers });
1416 }
1417 let words: Vec<String> = match mode {
1418 Mode::Regex => res!(Regex::required_literal(&text, !q.match_case)).into_iter().collect(),
1419 Mode::Word | Mode::Phrase => text.split_whitespace().map(String::from).collect(),
1420 };
1421 // Gmail searches by word, so only whole words of word characters, uncut.
1422 let gm = srv.gmail && q.whole_word && mode != Mode::Regex
1423 && words.iter().all(|w| w.bytes().all(|b| b.is_ascii_alphanumeric() && !KEY_CUT.contains(b as char)));
1424 let mut pieces: Vec<String> = Vec::new();
1425 for w in &words {
1426 let runs: Vec<&str> = w.split(|c: char| !c.is_ascii() || c.is_ascii_whitespace() || c.is_ascii_control()
1427 || KEY_CUT.contains(c)).filter(|r| !r.is_empty()).collect();
1428 let whole = mode != Mode::Regex && runs.len() == 1 && runs[0].len() == w.len();
1429 for r in runs {
1430 let r = r.to_ascii_lowercase();
1431 if (whole || r.len() >= lim.search_regex_min_literal) && !pieces.contains(&r) { pieces.push(r); }
1432 }
1433 }
1434 if pieces.is_empty() || (srv.gmail && !gm) {
1435 return Ok(Keys { sup: Set::Every, sub: Set::Empty, sup_full: false, sub_full: false });
1436 }
1437 // TEXT stands for the five headers and the body together.
1438 let all = SCOPES.iter().filter(|(s, _)| *s != Scope::Attachment).all(|(s, _)| scopes.contains(s));
1439 let (mut ors, mut fits) = (Vec::new(), true);
1440 for s in scopes.iter().filter(|s| !all || **s == Scope::Attachment).map(Some).chain(all.then_some(None)) {
1441 let mut ands = Vec::new();
1442 for p in &pieces {
1443 ands.push(match s {
1444 None => Set::Key(SearchKey::Text(p.clone())),
1445 Some(Scope::Body) => Set::Key(SearchKey::Body(p.clone())),
1446 Some(Scope::Attachment) => Set::Every, // the matcher's names are not all a server's
1447 Some(h) => Set::Key(SearchKey::Header(word_of(*h).into(), p.clone())),
1448 });
1449 }
1450 let (and, f) = join(ands, false, true, lim);
1451 ors.push(and);
1452 fits &= f;
1453 }
1454 let (sup, f) = join(ors, true, true, lim);
1455 let sup_full = fits && f && !matches!(sup, Set::Every);
1456 Ok(Keys { sup, sub: Set::Empty, sup_full, sub_full: false })
1457}
1458
1459fn not(s: Set) -> Set {
1460 match s {
1461 Set::Every => Set::Empty,
1462 Set::Empty => Set::Every,
1463 Set::Key(SearchKey::Not(k)) => Set::Key(*k),
1464 Set::Key(k) => Set::Key(SearchKey::Not(Box::new(k))),
1465 }
1466}
1467
1468/// The AND or OR of sets, as a superset (`sup`) or a subset, held under `search_key_max_bytes`:
1469/// where leaving a key out errs the safe way (a superset's AND, a subset's OR) the keys that do
1470/// not fit are left out, else the whole is widened (a superset) or emptied (a subset). With
1471/// whether every key was kept.
1472fn join(sets: Vec<Set>, any: bool, sup: bool, lim: &Limits) -> (Set, bool) {
1473 let mut ks = Vec::with_capacity(sets.len());
1474 for s in sets {
1475 match (s, any) {
1476 (Set::Key(k), _) => ks.push(k),
1477 (Set::Every, true) => return (Set::Every, true),
1478 (Set::Empty, false) => return (Set::Empty, true),
1479 _ => {}
1480 }
1481 }
1482 let unit = if any { Set::Empty } else { Set::Every };
1483 if any == sup { return fit(combine(ks, any).map_or(unit, Set::Key), sup, lim); }
1484 let (mut kept, mut used, mut all) = (Vec::new(), 2, true);
1485 for k in ks {
1486 match bytes(&k).map(|n| used + n + 4) { // fixed: at most a separator and an OR's three letters
1487 Some(n) if n <= lim.search_key_max_bytes => { used = n; kept.push(k); }
1488 _ => all = false,
1489 }
1490 }
1491 (combine(kept, any).map_or(unit, Set::Key), all)
1492}
1493
1494/// The key itself, or where its arguments are over `search_key_max_bytes` or cannot be written
1495/// (a day outside RFC 3501's four-digit years), every mail for a superset and none for a subset.
1496fn fit(s: Set, sup: bool, lim: &Limits) -> (Set, bool) {
1497 match &s {
1498 Set::Key(k) if bytes(k).map_or(true, |n| n > lim.search_key_max_bytes) =>
1499 (if sup { Set::Every } else { Set::Empty }, false),
1500 _ => (s, true),
1501 }
1502}
1503
1504/// An OR as a balanced tree, so that its depth grows with the log of its keys.
1505fn combine(mut v: Vec<SearchKey>, any: bool) -> Option<SearchKey> {
1506 match (v.len(), any) {
1507 (0, _) => return None,
1508 (1, _) => return v.pop(),
1509 (_, false) => return Some(SearchKey::And(v)),
1510 (_, true) => {}
1511 }
1512 while v.len() > 1 {
1513 let mut it = v.into_iter();
1514 let mut next = Vec::new();
1515 while let Some(a) = it.next() {
1516 next.push(match it.next() {
1517 Some(b) => SearchKey::Or(Box::new(a), Box::new(b)),
1518 None => a,
1519 });
1520 }
1521 v = next;
1522 }
1523 v.pop()
1524}
1525
1526/// The bytes of a key's arguments as sent, a literal with its `{n}` and line end; `None` where
1527/// the key cannot be written.
1528fn bytes(k: &SearchKey) -> Option<usize> {
1529 k.wire().ok().map(|v| v.iter().map(|s| match s {
1530 Segment::Text(t) => t.len(),
1531 Segment::Literal(l) => l.len() + l.len().to_string().len() + 4,
1532 }).sum())
1533}
1534
1535/// A leaf's text as the matcher reads it, in form C, refused over `search_regex_max_len`.
1536fn leaf_text(text: &str, lim: &Limits) -> Outcome<String> {
1537 let t = if text.is_ascii() { text.to_string() } else { nfc(text) };
1538 match t.chars().count() > lim.search_regex_max_len {
1539 true => Err(err!("A search text of {} characters is over the limit of {}.",
1540 t.chars().count(), lim.search_regex_max_len; Excessive, Input)),
1541 false => Ok(t),
1542 }
1543}