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 | |
| 18 | use crate::message::ParsedMessage; |
| 19 | |
| 20 | pub use crate::sync::query::Day; |
| 21 | |
| 22 | use oxedyne_fe2o3_core::prelude::*; |
| 23 | use oxedyne_fe2o3_net::imap::search::{ |
| 24 | days_from_civil, |
| 25 | Flag, |
| 26 | SearchKey, |
| 27 | Segment, |
| 28 | }; |
| 29 | use 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 | |
| 47 | use std::fmt; |
| 48 | |
| 49 | |
| 50 | #[derive(Clone, Copy, Debug, Eq, PartialEq)] |
| 51 | pub 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)] |
| 58 | pub 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:`. |
| 69 | const 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 | |
| 79 | fn word_of(s: Scope) -> &'static str { |
| 80 | SCOPES.iter().find(|(x, _)| *x == s).map_or("", |(_, w)| w) |
| 81 | } |
| 82 | |
| 83 | fn 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)] |
| 89 | pub 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)] |
| 104 | pub enum Age { |
| 105 | Days(u32), |
| 106 | Months(u32), |
| 107 | Years(u32), |
| 108 | } |
| 109 | |
| 110 | impl 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 | |
| 145 | impl 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. |
| 156 | pub 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 | |
| 164 | impl 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. |
| 169 | impl 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. |
| 186 | impl 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 | |
| 216 | impl 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 | |
| 233 | impl Eq for Term {} |
| 234 | |
| 235 | // As typed, since a derived form would recurse. |
| 236 | impl 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)] |
| 243 | pub enum Folders { |
| 244 | #[default] |
| 245 | Selected, |
| 246 | List(Vec<String>), |
| 247 | All { junk_trash: bool }, |
| 248 | } |
| 249 | |
| 250 | #[derive(Clone, Debug, Default, Eq, PartialEq)] |
| 251 | pub 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. |
| 264 | fn 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 | |
| 282 | fn 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 | |
| 287 | fn 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)] |
| 297 | enum 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)] |
| 309 | enum 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. |
| 317 | const 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 | |
| 331 | const SWITCHES: [&str; 3] = ["in", "scope", "match"]; |
| 332 | |
| 333 | fn 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 | |
| 343 | fn 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? |
| 357 | fn 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? |
| 362 | fn 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 `/`. |
| 369 | fn 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. |
| 385 | fn 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. |
| 396 | fn 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 | |
| 442 | fn 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 | |
| 454 | impl 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. |
| 467 | struct 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 | |
| 477 | impl 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 | |
| 611 | impl 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 `/`. |
| 626 | fn 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. |
| 643 | fn 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 | |
| 653 | fn 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)] |
| 668 | enum 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 `-`. |
| 672 | fn 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. |
| 684 | fn 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 | |
| 707 | impl 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)] |
| 733 | pub 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 | |
| 748 | impl 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 | |
| 766 | impl 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)] |
| 772 | pub 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)] |
| 782 | pub 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)] |
| 789 | pub 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)] |
| 796 | pub struct HitPart { |
| 797 | pub scope: Scope, |
| 798 | pub snippets: Vec<Snippet>, |
| 799 | } |
| 800 | |
| 801 | #[derive(Clone, Debug, Default, Eq, PartialEq)] |
| 802 | pub 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. |
| 807 | enum 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 | |
| 815 | pub 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. |
| 821 | type Parts = Vec<(Scope, String)>; |
| 822 | |
| 823 | /// One message's evaluation: its parts, read when a leaf first needs them, and each node's answer. |
| 824 | struct Eval<'a> { |
| 825 | parts: Option<Parts>, |
| 826 | vals: Vec<Option<bool>>, |
| 827 | fetched: Option<&'a Fetched>, |
| 828 | } |
| 829 | |
| 830 | fn 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. |
| 836 | fn 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 | |
| 853 | impl 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`). |
| 1048 | fn 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. |
| 1067 | fn 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. |
| 1076 | fn 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. |
| 1088 | fn 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. |
| 1096 | pub 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 | |
| 1102 | impl 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 | |
| 1126 | impl 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. |
| 1180 | struct Clean { |
| 1181 | text: String, |
| 1182 | map: Vec<[usize; 4]>, |
| 1183 | } |
| 1184 | |
| 1185 | impl 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. |
| 1244 | fn 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")] |
| 1259 | mod 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)] |
| 1290 | pub 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)] |
| 1297 | pub enum Needs { |
| 1298 | Meta, // flags, size, INTERNALDATE |
| 1299 | Headers, |
| 1300 | Structure, // the attachments' names |
| 1301 | Text, |
| 1302 | } |
| 1303 | |
| 1304 | #[derive(Clone, Debug, Eq, PartialEq)] |
| 1305 | pub 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. |
| 1314 | const KEY_CUT: &str = "kKsS;`&<>\"'"; |
| 1315 | |
| 1316 | /// The mails a server can name: every one, none, or those a key selects. |
| 1317 | #[derive(Clone, Debug)] |
| 1318 | enum 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. |
| 1326 | struct 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. |
| 1338 | pub 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`. |
| 1356 | fn 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. |
| 1401 | fn 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 | |
| 1459 | fn 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. |
| 1472 | fn 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. |
| 1496 | fn 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. |
| 1505 | fn 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. |
| 1528 | fn 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`. |
| 1536 | fn 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 | } |