Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_mail/tests/mailqx2_cases.rs

18.6 KiB, 7 runs

created by r2946818238:78316, 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//! MAILq-x2: part A of MAIL-q's fix (bounds and evaluation). Each case prints what it saw.
2
3use oxedyne_fe2o3_core::prelude::*;
4use oxedyne_fe2o3_mail::search::{
5 Day,
6 Filter,
7 Limits,
8 Mail,
9 Matcher,
10 Mode,
11 Query,
12 Scope,
13 Term,
14};
15
16use oxedyne_fe2o3_text::unicode::norm::combining_class;
17
18use std::collections::BTreeSet;
19use std::time::Instant;
20
21const TODAY: Day = Day { year: 2026, month: 3, day: 4 };
22const LIM: Limits = Limits { search_regex_max_len: 200, search_max_depth: 4, search_max_terms: 6,
23 snippet_chars: 10, snippets_per_part: 2, ..Limits::DEFAULT };
24const WIDE: Limits = Limits { search_regex_max_len: 200, search_max_depth: 16, search_max_terms: 500,
25 snippet_chars: 10, snippets_per_part: 2, ..Limits::DEFAULT };
26
27const SLOW: &str = "(?:a+b+c+d+e+f+g+h+){4}x"; // over 5 MB of "abcdefgh": cannot finish
28
29fn msg(subject: &str, body: &str) -> Vec<u8> {
30 format!("From: Ada <ada@x.example>\r\nTo: Bob <bob@x.example>\r\nSubject: {}\r\n\
31 Content-Type: text/plain; charset=utf-8\r\n\r\n{}\r\n", subject, body).into_bytes()
32}
33
34fn msg_att(subject: &str, body: &str, name: &str) -> Vec<u8> {
35 format!("From: a@x\r\nSubject: {}\r\nContent-Type: multipart/mixed; boundary=B\r\n\r\n--B\r\n\
36 Content-Type: text/plain\r\n\r\n{}\r\n--B\r\nContent-Type: application/octet-stream\r\n\
37 Content-Disposition: attachment; filename=\"{}\"\r\n\r\nbytes\r\n--B--\r\n", subject, body, name).into_bytes()
38}
39
40fn mail(raw: &[u8], seen: bool, flagged: bool, day: Option<Day>) -> Mail<'_> {
41 Mail { raw, seen, flagged, size: raw.len() as u64, day }
42}
43
44fn plain(raw: &[u8]) -> Mail<'_> { mail(raw, false, false, Day::parse("2026/03/04").ok()) }
45
46fn word(t: &str) -> Term { Term::Text { scope: None, mode: Mode::Word, text: t.into() } }
47fn rx(s: Option<Scope>, t: &str) -> Term { Term::Text { scope: s, mode: Mode::Regex, text: t.into() } }
48fn q(t: Term) -> Query { Query { terms: t, ..Query::default() } }
49
50/// 'T', 'F' or 'U'.
51fn tri(qr: &Query, m: &Mail, lim: &Limits) -> char {
52 match Matcher::new(qr, lim, TODAY) {
53 Err(e) => panic!("not compiled: {}", e),
54 Ok(x) => match x.matches(m) { Ok(Some(_)) => 'T', Ok(None) => 'F', Err(_) => 'U' },
55 }
56}
57
58fn marks(s: &str, raw: &[u8]) -> Vec<String> {
59 let qr = match Query::parse(s, &WIDE) { Ok(x) => x, Err(e) => panic!("{}", e) };
60 let h = match Matcher::new(&qr, &WIDE, TODAY).and_then(|m| m.matches(&plain(raw))) {
61 Ok(Some(h)) => h,
62 x => return vec![fmt!("NO HIT {:?}", x.map(|_| ()))],
63 };
64 let mut v: Vec<String> = h.parts.iter().flat_map(|p| p.snippets.iter())
65 .flat_map(|s| s.spans.iter().map(|x| s.text.get(x.start..x.end).unwrap_or("?").to_lowercase()).collect::<Vec<_>>()).collect();
66 v.sort();
67 v.dedup();
68 v
69}
70
71// Q2: bounds exactly at the limit and one over; the refusal's words; a built tree the matcher
72// takes, printed and read back.
73#[test]
74fn x2_bound_edges() {
75 for s in ["((((a b))))", "(((((a b)))))", "----a", "-----a", "-({-(a b)})", "-({-(-a b)})", "{(a b) (c d)}",
76 "a b c d e f", "a b c d e f g", "a (b c) {d e} -f", "a (b c) {d e} -f g", "is:unread is:read a b c d",
77 "is:unread is:read a b c d e"] {
78 eprintln!("QX2 edge parse {:>22?}: {}", s, match Query::parse(s, &LIM) { Ok(_) => "ok".into(), Err(e) => fmt!("refused: {}", e) });
79 }
80 for k in 3..=6 {
81 let mut t = word("a");
82 for _ in 0..k { t = Term::Not(Box::new(Term::All(vec![t]))); }
83 let qr = q(t);
84 let s = qr.to_string();
85 let new = Matcher::new(&qr, &LIM, TODAY).map(|_| ());
86 let back = Query::parse(&s, &LIM).map(|_| ());
87 eprintln!("QX2 edge built Not(All)^{} prints {:?}: matcher {} | its text parses {}", k, s,
88 if new.is_ok() { "takes it" } else { "refuses" }, if back.is_ok() { "ok" } else { "REFUSED" });
89 assert_eq!(new.is_ok(), back.is_ok(), "built Not(All)^{}: the matcher and the parser bound it apart", k);
90 }
91 for k in 3..=6 {
92 let mut t = word("a");
93 for _ in 0..k { t = Term::Not(Box::new(t)); }
94 let qr = q(t);
95 let s = qr.to_string();
96 let new = Matcher::new(&qr, &LIM, TODAY).map(|_| ());
97 let back = Query::parse(&s, &LIM).map(|_| ());
98 eprintln!("QX2 edge built Not^{} prints {:?}: matcher {} | its text parses {}", k, s,
99 if new.is_ok() { "takes it" } else { "refuses" }, if back.is_ok() { "ok" } else { "REFUSED" });
100 assert_eq!(new.is_ok(), back.is_ok(), "built Not^{}: the matcher and the parser bound it apart", k);
101 }
102 let five = (0..5).fold(word("a"), |t, _| Term::Not(Box::new(t)));
103 assert!(Matcher::new(&q(five), &LIM, TODAY).is_err(), "Not^5(a) taken at search_max_depth 4");
104 let nested = Term::Any(vec![Term::All(vec![word("a"), word("b"), Term::Any(vec![word("c"), word("d")])]),
105 Term::Not(Box::new(Term::All(vec![word("e"), Term::Filter(Filter::Seen), word("g")])))]);
106 eprintln!("QX2 edge built 7 leaves nested: {:?}", Matcher::new(&q(nested), &LIM, TODAY).map(|_| ()).err().map(|e| e.to_string()));
107}
108
109// Q2: the parser builds every leaf before it counts them.
110#[test]
111fn x2_parse_cost_before_bound() {
112 for n in [100_000usize, 1_000_000, 4_000_000] {
113 let s = "a ".repeat(n);
114 let t = Instant::now();
115 let r = Query::parse(&s, &LIM).map(|_| ());
116 eprintln!("QX2 parse {} bytes ({} leaves) with search_max_terms {}: {} in {:?}", s.len(), n, LIM.search_max_terms,
117 if r.is_ok() { "accepted" } else { "refused" }, t.elapsed());
118 }
119}
120
121struct Rng(u64);
122impl Rng {
123 fn n(&mut self, k: usize) -> usize {
124 self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17;
125 (self.0 % k as u64) as usize
126 }
127}
128
129const WORDS: [&str; 3] = ["alpha", "beta", "gamma"];
130
131fn gen(r: &mut Rng, d: usize) -> Term {
132 match if d == 0 { r.n(5) } else { r.n(8) } {
133 0 | 1 => Term::Text { scope: [None, Some(Scope::Subject), Some(Scope::Body)][r.n(3)], mode: Mode::Word,
134 text: WORDS[r.n(3)].into() },
135 2 => Term::Filter(Filter::Seen),
136 3 => Term::Filter(Filter::Since(Day { year: 2026, month: 1, day: 1 })), // unknown when no day
137 4 => Term::Filter(Filter::Flagged),
138 5 => Term::Not(Box::new(gen(r, d - 1))),
139 6 => Term::All((0..1 + r.n(4)).map(|_| gen(r, d - 1)).collect()),
140 _ => Term::Any((0..1 + r.n(4)).map(|_| gen(r, d - 1)).collect()),
141 }
142}
143
144fn kleene(t: &Term, m: &Mail, lim: &Limits) -> char {
145 match t {
146 Term::Not(x) => match kleene(x, m, lim) { 'T' => 'F', 'F' => 'T', _ => 'U' },
147 Term::All(v) => {
148 let a: Vec<char> = v.iter().map(|x| kleene(x, m, lim)).collect();
149 if a.contains(&'F') { 'F' } else if a.contains(&'U') { 'U' } else { 'T' }
150 }
151 Term::Any(v) => {
152 let a: Vec<char> = v.iter().map(|x| kleene(x, m, lim)).collect();
153 if a.contains(&'T') { 'T' } else if a.contains(&'U') { 'U' } else { 'F' }
154 }
155 leaf => tri(&q(leaf.clone()), m, lim),
156 }
157}
158
159/// The words of leaves that hold on a road where every node holds, never below a `Not`; every
160/// child of a holding group that holds, whatever the order.
161fn ideal(t: &Term, m: &Mail, lim: &Limits, out: &mut BTreeSet<String>) {
162 match t {
163 Term::Text { text, .. } => { out.insert(text.to_lowercase()); }
164 Term::All(v) | Term::Any(v) => for x in v { if kleene(x, m, lim) == 'T' { ideal(x, m, lim, out); } },
165 Term::Not(_) | Term::Filter(_) => {}
166 }
167}
168
169// Q3, Q4: the matcher against a naive three-valued evaluator over generated trees and mails.
170#[test]
171fn x2_against_naive() {
172 let mut r = Rng(0x9e37_79b9_7f4a_7c15);
173 let (mut n, mut wrong, mut mark_short, mut mark_extra, mut shown) = (0, 0, 0, 0, 0);
174 for _ in 0..600 {
175 let t = gen(&mut r, 3);
176 let subj: Vec<&str> = WORDS.iter().filter(|_| r.n(2) == 0).copied().collect();
177 let body: Vec<&str> = WORDS.iter().filter(|_| r.n(2) == 0).copied().collect();
178 let raw = msg(&(subj.join(" ") + " s"), &(body.join(" ") + " b"));
179 let day = if r.n(3) == 0 { None } else { Day::parse("2026/03/04").ok() };
180 let m = mail(&raw, r.n(2) == 0, r.n(2) == 0, day);
181 let qr = q(t.clone());
182 let want = kleene(&t, &m, &WIDE);
183 let mx = match Matcher::new(&qr, &WIDE, TODAY) { Ok(x) => x, Err(_) => continue };
184 let got = match mx.matches(&m) { Ok(Some(_)) => 'T', Ok(None) => 'F', Err(_) => 'U' };
185 n += 1;
186 if got != want {
187 wrong += 1;
188 if shown < 5 { shown += 1; eprintln!("QX2 naive WRONG {:?}: matcher {} naive {} | {:?}", qr.to_string(), got, want, (subj, body, m.seen, m.flagged, m.day)); }
189 }
190 if let Ok(Some(h)) = mx.matches(&m) {
191 let got: BTreeSet<String> = h.parts.iter().flat_map(|p| p.snippets.iter())
192 .flat_map(|s| s.spans.iter().map(|x| s.text[x.start..x.end].to_lowercase()).collect::<Vec<_>>()).collect();
193 let mut want = BTreeSet::new();
194 ideal(&t, &m, &WIDE, &mut want);
195 if got.iter().any(|w| !want.contains(w)) { mark_extra += 1; }
196 if want.iter().any(|w| !got.contains(w)) {
197 mark_short += 1;
198 if mark_short <= 3 { eprintln!("QX2 naive marks short {:?}: marked {:?} held {:?}", qr.to_string(), got, want); }
199 }
200 }
201 }
202 eprintln!("QX2 naive: {} trees, {} answers differ, marks: {} with a word not held, {} missing a word that held", n, wrong, mark_extra, mark_short);
203 assert_eq!(wrong, 0);
204}
205
206// Q3: an unknown leaf (a part too large to search) first, last and in the middle.
207#[test]
208fn x2_unknown_placement() {
209 let raw = msg("hello", &"abcdefgh".repeat(5 * 1024 * 1024 / 8));
210 let m = plain(&raw);
211 let (u, t, f) = (|| rx(None, SLOW), || word("abcdefgh"), || word("zzzz"));
212 let cases: Vec<(&str, Term, char)> = vec![
213 ("U T", Term::All(vec![u(), t()]), 'U'), ("T U", Term::All(vec![t(), u()]), 'U'),
214 ("U F", Term::All(vec![u(), f()]), 'F'), ("F U", Term::All(vec![f(), u()]), 'F'),
215 ("T U F", Term::All(vec![t(), u(), f()]), 'F'), ("T U T", Term::All(vec![t(), u(), t()]), 'U'),
216 ("U OR T", Term::Any(vec![u(), t()]), 'T'), ("T OR U", Term::Any(vec![t(), u()]), 'T'),
217 ("U OR F", Term::Any(vec![u(), f()]), 'U'), ("F OR U", Term::Any(vec![f(), u()]), 'U'),
218 ("F OR U OR T", Term::Any(vec![f(), u(), t()]), 'T'), ("-U", Term::Not(Box::new(u())), 'U'),
219 ("-(U OR T)", Term::Not(Box::new(Term::Any(vec![u(), t()]))), 'F'),
220 ("-(F U)", Term::Not(Box::new(Term::All(vec![f(), u()]))), 'T'),
221 ("-(U T)", Term::Not(Box::new(Term::All(vec![u(), t()]))), 'U'),
222 ("-U OR T", Term::Any(vec![Term::Not(Box::new(u())), t()]), 'T'),
223 ];
224 let mut bad = Vec::new();
225 for (name, term, want) in cases {
226 let got = tri(&q(term), &m, &WIDE);
227 eprintln!("QX2 unknown {:>12}: {} (want {})", name, got, want);
228 if got != want { bad.push(name); }
229 }
230 assert!(bad.is_empty(), "{:?}", bad);
231}
232
233// Q4: marks.
234#[test]
235fn x2_marks() {
236 let raw = msg("x", "alpha one beta two");
237 let mut bad = Vec::new();
238 for (s, want) in [("alpha OR beta", "alpha beta"), ("beta OR alpha", "alpha beta"), ("alpha beta", "alpha beta"),
239 ("beta alpha", "alpha beta"), ("-zeta alpha", "alpha"), ("-(alpha zeta) beta", "beta"), ("{alpha beta}", "alpha beta"),
240 ("(alpha OR zeta) beta", "alpha beta"), ("alpha OR (beta zeta)", "alpha"), ("-(-alpha) beta", "beta"),
241 ("zeta OR alpha OR beta", "alpha beta")] {
242 let got = marks(s, &raw).join(" ");
243 eprintln!("QX2 marks {:>24?}: {:?} (held: {:?})", s, got, want);
244 if got != want { bad.push(s); }
245 }
246 assert!(bad.is_empty(), "marks differ from the words that held: {:?}", bad);
247}
248
249// Q5: snippets in characters, clipped, `cut` true only when cut, no panic at a boundary.
250#[test]
251fn x2_snippets() {
252 let lim = &WIDE;
253 let cases: Vec<(String, &str)> = vec![
254 ("é".repeat(30) + "target" + &"日本".repeat(30), "target"),
255 ("target".to_string() + &"é".repeat(30), "target"),
256 ("é".repeat(30) + "target", "target"),
257 ("x".repeat(1000), "/x+/"),
258 ("日".repeat(1000), "/日+/"),
259 ("e\u{301}".repeat(20) + "target" + &"e\u{301}".repeat(20), "target"),
260 ("aa ".repeat(50), "aa"),
261 ("ab".to_string(), "ab"),
262 ("😀".repeat(9) + "q" + &"😀".repeat(9), "q"),
263 ("😀".repeat(9) + "qq", "/q+/"),
264 ("q\u{301}".repeat(20) + "target" + &"q\u{301}".repeat(20), "target"),
265 ("zz é zz é zz".to_string(), "/z*/"),
266 ];
267 let mut bad = Vec::new();
268 for (body, s) in &cases {
269 let raw = msg("x", body);
270 let qr = match Query::parse(s, lim) { Ok(x) => x, Err(e) => panic!("{}", e) };
271 let h = match Matcher::new(&qr, lim, TODAY).and_then(|m| m.matches(&plain(&raw))) {
272 Ok(Some(h)) => h,
273 x => { bad.push(fmt!("{:?}: no hit {:?}", s, x.map(|_| ()))); continue; }
274 };
275 for p in &h.parts {
276 if p.snippets.len() > lim.snippets_per_part { bad.push(fmt!("{:?}: {} snippets", s, p.snippets.len())); }
277 for sn in &p.snippets {
278 let chars = sn.text.chars().count();
279 let ok_spans = sn.spans.iter().all(|x| x.start <= x.end && sn.text.get(x.start..x.end).is_some());
280 let ran_on = sn.spans.last().map_or(false, |x| x.end == sn.text.len());
281 eprintln!("QX2 snip {:>8?} in {:?}: {:?} ({} chars) spans {:?} cut {}", s, p.scope, sn.text, chars, sn.spans, sn.cut);
282 if chars > lim.snippet_chars { bad.push(fmt!("{:?}: {} chars", s, chars)); }
283 if !ok_spans { bad.push(fmt!("{:?}: a span off a boundary or past the text", s)); }
284 if sn.cut && !ran_on { bad.push(fmt!("{:?}: cut, but the last span ends inside", s)); }
285 let mark = |c: Option<char>| c.is_some_and(|c| combining_class(c) != 0);
286 if mark(sn.text.chars().next()) || mark(p_after(body, &sn.text)) {
287 bad.push(fmt!("{:?}: a window's end splits a mark from its letter", s));
288 }
289 if let [x] = &sn.spans[..] {
290 let (pre, post) = (sn.text[..x.start].chars().count(), sn.text[x.end..].chars().count());
291 let span = sn.text[x.start..x.end].chars().count();
292 if span < lim.snippet_chars && (sn.cut || (inside(body, &sn.text) && pre.abs_diff(post) > 2)) {
293 bad.push(fmt!("{:?}: a span that fits not centred: {} before, {} after", s, pre, post));
294 }
295 }
296 }
297 }
298 }
299 eprintln!("QX2 snip faults: {:?}", bad);
300 assert!(bad.is_empty());
301}
302
303// Q6: a leaf over two parts, each part matching (M), not (N), or unfinishable (U).
304#[test]
305fn x2_parts_states() {
306 let big = "abcdefgh".repeat(5 * 1024 * 1024 / 8);
307 let hit = "abcdefgh".repeat(4) + "x";
308 let text = |c: char| match c { 'M' => hit.clone(), 'N' => "hello".to_string(), _ => big.clone() };
309 let mut bad = Vec::new();
310 for (a, b, sa, sb) in [("Subject", "Body", Scope::Subject, Scope::Body), ("Body", "Attachment", Scope::Body, Scope::Attachment),
311 ("Subject", "Attachment", Scope::Subject, Scope::Attachment)] {
312 for x in ['M', 'N', 'U'] {
313 for y in ['M', 'N', 'U'] {
314 let (mut subj, mut body, mut name) = ("s".to_string(), "b".to_string(), "n.pdf".to_string());
315 for (sc, c) in [(sa, x), (sb, y)] {
316 match sc { Scope::Subject => subj = text(c), Scope::Body => body = text(c), _ => name = text(c) }
317 }
318 let raw = msg_att(&subj, &body, &name);
319 let m = plain(&raw);
320 let one_a = tri(&q(rx(Some(sa), SLOW)), &m, &WIDE);
321 let one_b = tri(&q(rx(Some(sb), SLOW)), &m, &WIDE);
322 let mut both = Query { terms: rx(None, SLOW), ..Query::default() };
323 both.scopes = vec![sa, sb];
324 let got = tri(&both, &m, &WIDE);
325 let want = if x == 'M' || y == 'M' { 'T' } else if x == 'U' || y == 'U' { 'U' } else { 'F' };
326 let parts_ok = (one_a, one_b) == ([x, y].map(|c| match c { 'M' => 'T', 'N' => 'F', _ => 'U' })[0],
327 [x, y].map(|c| match c { 'M' => 'T', 'N' => 'F', _ => 'U' })[1]);
328 eprintln!("QX2 parts {}={} {}={}: alone {} {} (as set: {}) | together {} want {}", a, x, b, y, one_a, one_b,
329 parts_ok, got, want);
330 if parts_ok && got != want { bad.push(fmt!("{}={} {}={}", a, x, b, y)); }
331 }
332 }
333 }
334 assert!(bad.is_empty(), "{:?}", bad);
335}
336
337// Q7: work per message, leaf length times text (print only; run with --release).
338#[test]
339fn x2_cost_long_leaves() {
340 let raw = msg("x", &"lorem ipsum ".repeat(1024 * 1024 / 12));
341 let m = plain(&raw);
342 let lim = Limits { search_regex_max_len: 200, search_max_depth: 16, search_max_terms: 500, snippet_chars: 40, snippets_per_part: 2, ..Limits::DEFAULT };
343 let mut r = Rng(7);
344 for (len, n) in [(4usize, 1usize), (4, 20), (190, 1), (190, 5), (190, 20)] {
345 let leaves: Vec<String> = (0..n).map(|_| (0..len).map(|_| (b'a' + r.n(26) as u8) as char).collect()).collect();
346 let s = leaves.join(" OR ");
347 let qr = match Query::parse(&s, &lim) { Ok(x) => x, Err(e) => panic!("{}", e) };
348 let mx = match Matcher::new(&qr, &lim, TODAY) { Ok(x) => x, Err(e) => panic!("{}", e) };
349 let t = Instant::now();
350 let a = match mx.matches(&m) { Ok(Some(_)) => "hit", Ok(None) => "miss", Err(_) => "unknown" };
351 eprintln!("QX2 cost: {} leaves of {} chars OR'd over 1 MB: {} in {:?}", n, len, a, t.elapsed());
352 }
353 let s = (0..20).map(|_| fmt!("/{}/", "[a-z]".repeat(30))).collect::<Vec<_>>().join(" OR ") + " OR zzzz";
354 if let Ok(qr) = Query::parse(&s, &lim) {
355 if let Ok(mx) = Matcher::new(&qr, &lim, TODAY) {
356 let t = Instant::now();
357 let a = match mx.matches(&m) { Ok(Some(_)) => "hit", Ok(None) => "miss", Err(_) => "unknown" };
358 eprintln!("QX2 cost: 20 regex leaves of 150 chars over 1 MB: {} in {:?}", a, t.elapsed());
359 }
360 }
361}
362
363/// The char after a snippet's text in the body it was cut from, where it is found once.
364fn p_after(body: &str, text: &str) -> Option<char> {
365 let nb = oxedyne_fe2o3_text::unicode::norm::nfc(body);
366 match nb.matches(text).count() {
367 1 => nb.find(text).and_then(|i| nb[i + text.len()..].chars().next()),
368 _ => None,
369 }
370}
371
372/// Does the snippet's text stand inside the body, with text before and after it?
373fn inside(body: &str, text: &str) -> bool {
374 let nb = oxedyne_fe2o3_text::unicode::norm::nfc(body);
375 nb.find(text).is_some_and(|i| i > 0 && i + text.len() < nb.len())
376}