Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/tests/regex.rs

13.5 KiB, 1 run

created by r1870400018:60332, 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//! The regular expression engine and the Unicode property tables, held to an external oracle.
2//!
3//! `tests/regex_oracle/expected.txt` is what Perl's engine says of every pattern and haystack in
4//! `corpus.txt`, written by `oracle.pl`; `props_expected.txt` is Perl's own Unicode property data,
5//! written by `props.pl`. Neither answer comes from fe2o3_text, so agreement is evidence rather
6//! than self-consistency. Rerun the scripts after changing the corpus.
7
8use oxedyne_fe2o3_text::{
9 regex::{
10 Regex,
11 Span,
12 },
13 unicode::{
14 lookup::Partitioned,
15 property::{
16 Binary,
17 CharClass,
18 Extensions,
19 },
20 prop::{
21 GeneralCategory,
22 Script,
23 },
24 },
25};
26
27use oxedyne_fe2o3_core::prelude::*;
28
29use std::{
30 collections::BTreeMap,
31 fs,
32 path::PathBuf,
33};
34
35
36fn data(name: &str) -> String {
37 let path = PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("tests").join("regex_oracle").join(name);
38 match fs::read_to_string(&path) {
39 Ok(s) => s,
40 Err(e) => panic!("reading {:?}: {}", path, e),
41 }
42}
43
44fn unesc(s: &str) -> String {
45 let mut out = String::with_capacity(s.len());
46 let mut it = s.chars();
47 while let Some(c) = it.next() {
48 if c != '\\' {
49 out.push(c);
50 continue;
51 }
52 match it.next() {
53 Some('t') => out.push('\t'),
54 Some('n') => out.push('\n'),
55 Some('r') => out.push('\r'),
56 Some(x) => out.push(x),
57 None => out.push('\\'),
58 }
59 }
60 out
61}
62
63/// The oracle's notation for one match's groups: `start,end` per group, `-` for one that took no
64/// part.
65fn spans(v: &[Option<Span>]) -> String {
66 v.iter()
67 .map(|s| match s {
68 Some(s) => fmt!("{},{}", s.start, s.end),
69 None => "-".to_string(),
70 })
71 .collect::<Vec<_>>()
72 .join(" ")
73}
74
75#[test]
76fn test_regex_agrees_with_the_perl_oracle() {
77 let text = data("expected.txt");
78 let mut fails: Vec<String> = Vec::new();
79 let (mut cases, mut searches, mut hits, mut grouped, mut matches, mut reps) = (0, 0, 0, 0, 0, 0);
80
81 let mut pat = String::new();
82 let mut hay = String::new();
83 let mut re: Option<Regex> = None;
84 let mut want_m: Vec<String> = Vec::new();
85
86 for line in text.lines() {
87 let (tag, rest) = match line.split_once('\t') {
88 Some(x) => x,
89 None => (line, ""),
90 };
91 match tag {
92 "P" => {
93 pat = unesc(rest);
94 re = match Regex::new(&pat) {
95 Ok(r) => Some(r),
96 Err(e) => {
97 fails.push(fmt!("'{}' did not compile: {}", pat, e));
98 None
99 },
100 };
101 },
102 "H" => {
103 hay = unesc(rest);
104 want_m.clear();
105 cases += 1;
106 },
107 "A" => {
108 let (at, want) = match rest.split_once('\t') {
109 Some(x) => x,
110 None => panic!("bad A line: {}", line),
111 };
112 let at: usize = match at.parse() {
113 Ok(n) => n,
114 Err(e) => panic!("bad offset in {}: {}", line, e),
115 };
116 let r = match &re {
117 Some(r) => r,
118 None => continue,
119 };
120 searches += 1;
121 let got = match r.captures_at(&hay, at) {
122 Ok(Some(c)) => {
123 hits += 1;
124 if c.len() > 1 && c.spans()[1..].iter().any(|s| s.is_some()) {
125 grouped += 1;
126 }
127 spans(c.spans())
128 },
129 Ok(None) => "none".to_string(),
130 Err(e) => fmt!("error {}", e),
131 };
132 if got != want {
133 fails.push(fmt!("'{}' on {:?} from byte {}: got {}, Perl says {}",
134 pat, hay, at, got, want));
135 }
136 },
137 "M" => want_m.push(rest.to_string()),
138 "S" => {
139 let r = match &re {
140 Some(r) => r,
141 None => continue,
142 };
143 let mut got_m = Vec::new();
144 for c in r.captures_iter(&hay) {
145 match c {
146 Ok(c) => got_m.push(spans(c.spans())),
147 Err(e) => got_m.push(fmt!("error {}", e)),
148 }
149 }
150 matches += want_m.len();
151 if got_m != want_m {
152 fails.push(fmt!("'{}' on {:?} iterates to {:?}, Perl's emulation of the regex \
153 crate says {:?}", pat, hay, got_m, want_m));
154 }
155 let want_s: Vec<String> = rest.split('\u{1F}').map(unesc).collect();
156 match r.split(&hay) {
157 Ok(got_s) => if got_s != want_s {
158 fails.push(fmt!("'{}' splits {:?} into {:?}, not {:?}",
159 pat, hay, got_s, want_s));
160 },
161 Err(e) => fails.push(fmt!("'{}' could not split {:?}: {}", pat, hay, e)),
162 }
163 },
164 "R" => {
165 let r = match &re {
166 Some(r) => r,
167 None => continue,
168 };
169 let (tpl, want) = match rest.split_once('\t') {
170 Some((t, w)) => (unesc(t), unesc(w)),
171 None => panic!("bad R line: {}", line),
172 };
173 reps += 1;
174 match r.replace_all(&hay, &tpl) {
175 Ok(got) => if got != want {
176 fails.push(fmt!("'{}' with '{}' on {:?} gives {:?}, not {:?}",
177 pat, tpl, hay, got, want));
178 },
179 Err(e) => fails.push(fmt!("'{}' could not replace in {:?}: {}", pat, hay, e)),
180 }
181 },
182 _ => {},
183 }
184 }
185
186 // The comparison must have had something to compare: a truncated or empty oracle file would
187 // otherwise pass.
188 assert!(cases >= 150, "only {} cases were read", cases);
189 assert!(searches >= 1100 && hits >= 800, "{} searches, {} hits", searches, hits);
190 assert!(grouped >= 80, "only {} searches exercised capture groups", grouped);
191 assert!(matches >= 250 && reps >= 4, "{} iterated matches, {} replacements", matches, reps);
192 if !fails.is_empty() {
193 panic!("{} disagreements with Perl, the first:\n{}", fails.len(),
194 fails.iter().take(40).cloned().collect::<Vec<_>>().join("\n"));
195 }
196}
197
198/// A run table from props_expected.txt: start code point and value, sorted.
199fn runs(text: &str, tag: &str) -> Vec<(u32, String)> {
200 let mut out = Vec::new();
201 for line in text.lines() {
202 let f: Vec<&str> = line.splitn(3, '\t').collect();
203 if f.len() == 3 && f[0] == tag {
204 match u32::from_str_radix(f[1], 16) {
205 Ok(cp) => out.push((cp, f[2].to_string())),
206 Err(e) => panic!("bad code point in {}: {}", line, e),
207 }
208 }
209 }
210 out
211}
212
213fn at(runs: &[(u32, String)], cp: u32) -> &str {
214 let i = runs.partition_point(|(s, _)| *s <= cp);
215 match i.checked_sub(1).and_then(|i| runs.get(i)) {
216 Some((_, v)) => v.as_str(),
217 None => "",
218 }
219}
220
221#[test]
222fn test_unicode_properties_agree_with_perl() {
223 let text = data("props_expected.txt");
224 let gc = runs(&text, "GC");
225 let sc = runs(&text, "SC");
226 let scx = runs(&text, "SCX");
227 assert!(gc.len() > 3000 && sc.len() > 1500 && scx.len() > 1500,
228 "the oracle file is short: {} {} {}", gc.len(), sc.len(), scx.len());
229
230 let mut bins: Vec<(Binary, Vec<u32>)> = Vec::new();
231 for line in text.lines() {
232 let f: Vec<&str> = line.split('\t').collect();
233 if f.len() != 3 || f[0] != "BIN" || f[2] == "unknown" {
234 continue;
235 }
236 let b = match Binary::find(f[1]) {
237 Some(b) => b,
238 None => panic!("Perl knows the binary property {} and the tables do not", f[1]),
239 };
240 let inv: Vec<u32> = f[2].split(' ').map(|x| match u32::from_str_radix(x, 16) {
241 Ok(v) => v,
242 Err(e) => panic!("bad inversion list entry {}: {}", x, e),
243 }).collect();
244 bins.push((b, inv));
245 }
246 assert!(bins.len() >= 50, "only {} binary properties compared", bins.len());
247
248 // Perl's Unicode is older than the tables', so a disagreement is accepted only where
249 // props_changed.txt, a diff of the two UCD releases' own files, says Unicode changed that
250 // property of that code point.
251 let mut changed: std::collections::BTreeSet<(String, u32)> = std::collections::BTreeSet::new();
252 for line in data("props_changed.txt").lines() {
253 if let Some((p, cp)) = line.split_once('\t') {
254 match u32::from_str_radix(cp, 16) {
255 Ok(v) => { changed.insert((p.to_string(), v)); },
256 Err(e) => panic!("bad code point in {}: {}", line, e),
257 }
258 }
259 }
260 assert!(changed.len() > 500, "the change list is short: {}", changed.len());
261
262 let mut diffs: BTreeMap<String, Vec<String>> = BTreeMap::new();
263 let mut explained = 0usize;
264 let mut note = |prop: &str, cp: u32, what: String| {
265 if changed.contains(&(prop.to_string(), cp)) {
266 explained += 1;
267 } else {
268 diffs.entry(prop.to_string()).or_default().push(fmt!("U+{:04X} {}", cp, what));
269 }
270 };
271 let mut compared = 0u32;
272 for cp in 0..=0x10FFFFu32 {
273 let c = match char::from_u32(cp) {
274 Some(c) => c,
275 None => continue,
276 };
277 let pgc = at(&gc, cp);
278 if pgc == "Cn" {
279 continue;
280 }
281 compared += 1;
282 let ours = GeneralCategory::of(c).abbr();
283 if ours != pgc {
284 note("gc", cp, fmt!("{} vs {}", ours, pgc));
285 }
286 let ours = Script::of(c).name();
287 let psc = at(&sc, cp);
288 if ours != psc {
289 note("sc", cp, fmt!("{} vs {}", ours, psc));
290 }
291 let mut ours: Vec<&str> = Extensions::of(c).as_slice().iter().map(|s| s.name()).collect();
292 ours.sort();
293 let ours = ours.join(" ");
294 let pscx = at(&scx, cp);
295 if ours != pscx {
296 note("scx", cp, fmt!("{} vs {}", ours, pscx));
297 }
298 for (b, inv) in &bins {
299 let theirs = inv.partition_point(|s| *s <= cp) % 2 == 1;
300 if b.contains(c) != theirs {
301 note(b.name(), cp, fmt!("{} vs {}", b.contains(c), theirs));
302 }
303 }
304 }
305 assert!(compared > 280_000, "only {} code points compared", compared);
306
307 let total: usize = diffs.values().map(|v| v.len()).sum();
308 let report = diffs.iter()
309 .map(|(k, v)| fmt!("{}: {} ({})", k, v.len(), v.iter().take(6).cloned().collect::<Vec<_>>().join(", ")))
310 .collect::<Vec<_>>()
311 .join("\n");
312 assert!(total == 0, "{} differences from Perl's Unicode data that Unicode did not make \
313 ({} that it did):\n{}", total, explained, report);
314}
315
316#[test]
317fn test_property_names_resolve_as_the_regex_crate_resolves_them() {
318 for (name, want) in [
319 ("L", CharClass::parse("gc=L")),
320 ("Greek", CharClass::parse("sc=Greek")),
321 ("isGreek", CharClass::parse("Script=Grek")),
322 ("cf", CharClass::parse("gc=Cf")),
323 ("sc", CharClass::parse("gc=Sc")),
324 ("lc", CharClass::parse("gc=LC")),
325 ("White Space", CharClass::parse("wspace")),
326 ] {
327 let got = CharClass::parse(name);
328 match (got, want) {
329 (Ok(g), Ok(w)) => assert_eq!(g, w, "'{}'", name),
330 (g, w) => panic!("'{}': {:?} vs {:?}", name, g, w),
331 }
332 }
333 assert!(CharClass::parse("scx=Greek").is_ok());
334 assert!(CharClass::parse("Age=6.0").is_err(), "an unsupported property is refused, not guessed");
335 assert!(CharClass::parse("Klingon").is_err());
336}
337
338#[test]
339fn test_regex_agrees_with_the_regex_crate_suite() {
340 // rust_suite.txt is the Rust `regex` crate's own test data, converted by rust_suite.py: the
341 // answers Typst's `regex(...)` gives, stated by the crate that gives them.
342 let text = data("rust_suite.txt");
343 let mut fails: Vec<String> = Vec::new();
344 let mut lenient: Vec<String> = Vec::new();
345 let (mut cases, mut compared) = (0, 0);
346
347 let (mut name, mut flags, mut pat, mut hay) = (String::new(), String::new(), String::new(), String::new());
348 let mut refuse = false;
349 let mut limit: Option<usize> = None;
350 let mut want: Vec<String> = Vec::new();
351
352 for line in text.lines() {
353 let f: Vec<&str> = line.splitn(3, '\t').collect();
354 match f.first().copied() {
355 Some("T") => {
356 name = f.get(1).copied().unwrap_or("").to_string();
357 flags = f.get(2).copied().unwrap_or("").to_string();
358 refuse = false;
359 limit = None;
360 want.clear();
361 },
362 Some("P") => pat = unesc(f.get(1).copied().unwrap_or("")),
363 Some("H") => hay = unesc(f.get(1).copied().unwrap_or("")),
364 Some("C") => refuse = true,
365 Some("L") => limit = f.get(1).and_then(|n| n.parse().ok()),
366 Some("M") => want.push(f.get(1).copied().unwrap_or("").to_string()),
367 Some("E") => {
368 cases += 1;
369 let re = match Regex::with_case(&pat, flags.contains('i')) {
370 Ok(r) => {
371 if refuse {
372 lenient.push(fmt!("{}: '{}'", name, pat));
373 continue;
374 }
375 r
376 },
377 Err(e) => {
378 if !refuse {
379 fails.push(fmt!("{}: '{}' did not compile: {}", name, pat, e));
380 }
381 continue;
382 },
383 };
384 let mut got: Vec<String> = Vec::new();
385 for c in re.captures_iter(&hay) {
386 if limit.map(|n| got.len() >= n).unwrap_or(false) {
387 break;
388 }
389 match c {
390 Ok(c) => {
391 // An anchored search may only begin at the start.
392 if flags.contains('a') && c.whole().start != 0 {
393 break;
394 }
395 // The crate states some cases by the whole match alone.
396 let whole_only = want.first().map(|w| !w.contains(' ')).unwrap_or(true);
397 got.push(if whole_only { spans(&c.spans()[..1]) } else { spans(c.spans()) });
398 },
399 Err(e) => {
400 got.push(fmt!("error {}", e));
401 break;
402 },
403 }
404 if flags.contains('a') {
405 break;
406 }
407 }
408 compared += 1;
409 if got != want {
410 fails.push(fmt!("{}: '{}' on {:?} gives {:?}, the crate says {:?}",
411 name, pat, hay, got, want));
412 }
413 },
414 _ => {},
415 }
416 }
417 assert!(cases >= 700 && compared >= 650, "{} cases, {} compared", cases, compared);
418 // Where the crate refuses a pattern this engine reads, the difference is a documented
419 // leniency; list them so a new one is seen.
420 assert!(lenient.len() <= LENIENT, "accepted what the crate refuses:\n{}", lenient.join("\n"));
421 if !fails.is_empty() {
422 panic!("{} disagreements with the regex crate, the first:\n{}", fails.len(),
423 fails.iter().take(60).cloned().collect::<Vec<_>>().join("\n"));
424 }
425}
426
427/// Patterns the `regex` crate refuses and this engine reads; see the module notes on `{`.
428const LENIENT: usize = 0;
429
430#[test]
431fn test_a_group_in_a_repetition_keeps_its_last_capture() {
432 // Perl clears a group's capture on each new iteration of an enclosing repetition; the regex
433 // crate, like Python's `re`, keeps it. These answers are Python 3's:
434 // re.search(r'(a(b)?)+', 'aba') -> spans (0,3) (2,3) (1,2)
435 // re.search(r'((a)|b)+', 'ab') -> spans (0,2) (1,2) (0,1)
436 // re.search(r'(?:(a)|b)*', 'ab') -> spans (0,2) (0,1)
437 // re.search(r'(a|(b))+', 'ba') -> spans (0,2) (1,2) (0,1)
438 for (pat, hay, want) in [
439 ("(a(b)?)+", "aba", "0,3 2,3 1,2"),
440 ("((a)|b)+", "ab", "0,2 1,2 0,1"),
441 ("(?:(a)|b)*", "ab", "0,2 0,1"),
442 ("(a|(b))+", "ba", "0,2 1,2 0,1"),
443 ] {
444 let re = Regex::new(pat).expect("compile");
445 let c = re.captures(hay).expect("search").expect("a match");
446 assert_eq!(spans(c.spans()), want, "'{}' on '{}'", pat, hay);
447 }
448}