markdown_prose_hooks/
fuzz.rs

1//! Document generator for the differential fuzzer.
2//!
3//! Enumerated cases prove the two implementations agree about what was
4//! anticipated. Only a fuzzer speaks to what was not, and shipping a second
5//! implementation means shipping the claim that they agree.
6//!
7//! **A seed does not name a stable document.** Any change to the bank, to the
8//! draw order, or to a denominator renames every seed, because the fragment
9//! index is drawn modulo the bank's length. The fixed seed range CI runs is a
10//! regression net only while the generator is frozen; it is not a corpus, and a
11//! divergence worth keeping is promoted into `corpus/` rather than left as a
12//! seed number.
13
14/// xorshift64\*, so the generator is deterministic without a dependency.
15pub struct Rng {
16    state: u64,
17}
18
19impl Rng {
20    /// Seed the generator. Zero is a fixed point of xorshift, so it is mapped.
21    #[must_use]
22    pub fn new(seed: u64) -> Self {
23        Self {
24            state: if seed == 0 {
25                0x9E37_79B9_7F4A_7C15
26            } else {
27                seed
28            },
29        }
30    }
31
32    /// The next raw value.
33    pub fn next_u64(&mut self) -> u64 {
34        let mut x = self.state;
35        x ^= x << 13;
36        x ^= x >> 7;
37        x ^= x << 17;
38        self.state = x;
39        x
40    }
41
42    /// A value below `bound`, which must not be zero.
43    pub fn below(&mut self, bound: u64) -> u64 {
44        self.next_u64() % bound
45    }
46}
47
48/// The lines a generated document is built from.
49///
50/// Chosen so the generator can reach every hazard the port has a comment about.
51/// A bank that cannot reach a hazard is worse than no bank, because it reports
52/// coverage it does not have — which is what `the_bank_reaches_its_hazards`
53/// below exists to check.
54pub const FRAGMENTS: &[&str] = &[
55    // Ordinary prose, and prose carrying the four C0 separators that Python
56    // calls whitespace and Rust does not. The trailing one is the fragment that
57    // discriminates: a separator in the middle of a line survives either
58    // reading, and only one at an edge tells `str.strip` from `str::trim`.
59    // Mutation testing found that gap; the mid-line fragment alone did not.
60    "ordinary prose that wraps",
61    "a second prose line",
62    "prose\u{1c}with\u{1d}four\u{1e}C0\u{1f}separators",
63    "prose ending in a separator\u{1c}",
64    "prose ending in a unit separator\u{1f}",
65    "",
66    "   ",
67    // Fence openers of both characters and several lengths, indented and not.
68    "```",
69    "````",
70    "~~~",
71    "~~~~~",
72    "```rust",
73    "   ```",
74    "    ```",
75    "``` ```",
76    // Blockquote prefixes at several depths, with and without the space.
77    "> quoted prose",
78    ">no space after the marker",
79    "> > deeper prose",
80    ">>> deepest",
81    ">",
82    "   > indented marker",
83    ">     indented code inside a quote",
84    "> ```",
85    "> <!-- quoted comment",
86    "> <div>",
87    "> | a | b |",
88    // A quoted speaker turn, which opens a row of its own rather than
89    // continuing the quoted paragraph above it. Also a mutation-testing find:
90    // an unquoted speaker line cannot reach that branch.
91    "> Alex: a quoted utterance",
92    "> Jordan: another quoted utterance",
93    // List markers: bullets, both ordered spellings, and non-ASCII digits,
94    // which are markers to no renderer and must not open a list.
95    "- bullet item",
96    "* star item",
97    "+ plus item",
98    "1. ordered item",
99    "12) ordered item",
100    "\u{663}. item",
101    "\u{967}\u{968}) item",
102    "  continuation at the content column",
103    "    deeper continuation",
104    // Alphabetic sub-enumerators, which CommonMark does not call list markers
105    // and which are still load-bearing layout.
106    "a. lettered subitem",
107    "b) lettered subitem",
108    // Label rows in all four shapes.
109    "**Label:** value",
110    "**Label**: value",
111    "**Whole line bold**",
112    "Alex: an utterance",
113    "Alex Jordan Morgan Casey: four words",
114    "Alex Jordan Morgan Casey Drew: five words",
115    "[a stage direction]",
116    "[a stage direction].",
117    // Tables, and pipes hidden inside code spans of one, two and three ticks.
118    "| a | b |",
119    "| - | - |",
120    "a `x | y` span",
121    "a ``x | y`` span",
122    "a ```x | y``` span",
123    "an `unterminated run",
124    "a `a``` closing run",
125    // Hard breaks, both spellings.
126    "a hard break  ",
127    "a hard break\\",
128    // HTML in every shape the loop distinguishes.
129    "<div>",
130    "</div>",
131    "<div>closed on its own line</div>",
132    "<br/>",
133    "<pre>",
134    "</pre>",
135    "<!-- an open comment",
136    "-->",
137    "<!-- a closed comment -->",
138    "<?php",
139    "?>",
140    "<![CDATA[",
141    "]]>",
142    "<!DOCTYPE html",
143    "<!DOCTYPE html>",
144    // Front matter openers and closers, with and without a byte order mark.
145    "---",
146    "\u{feff}---",
147    "...",
148    "title: a value",
149    // Structural lines the prose branch has to decline.
150    "# a heading",
151    "===",
152    "- - -",
153    "***",
154    "[label]: https://example.com",
155    "[!NOTE]",
156    "[![badge](s.svg)][ref]",
157    "[another](https://example.com)",
158    ":: an admonition",
159    "!!! note",
160    "{% raw %}",
161    "{{ template }}",
162    // Speaker headings at the `{0,39}` boundary, and a timestamped one whose
163    // digits are the counted quantifier the specification narrowed to ASCII.
164    concat!(
165        "A",
166        "eeeeeeeeee",
167        "eeeeeeeeee",
168        "eeeeeeeeee",
169        "eeeeeeeee",
170        ":"
171    ),
172    concat!(
173        "A",
174        "eeeeeeeeee",
175        "eeeeeeeeee",
176        "eeeeeeeeee",
177        "eeeeeeeeee",
178        ":"
179    ),
180    "MC 0:15",
181    "MC \u{660}:\u{661}\u{665}",
182    "JR 12:34",
183];
184
185/// Build the document for `seed`.
186///
187/// Every draw is unconditional, so the number of values consumed depends only
188/// on the line count — which is itself the first draw. That keeps a seed's
189/// document stable under edits to *this function's* branches, though not under
190/// edits to the bank.
191#[must_use]
192pub fn document(seed: u64) -> String {
193    let mut rng = Rng::new(seed);
194    let line_count = 1 + rng.below(24);
195    let mut out = String::new();
196    for _ in 0..line_count {
197        let index = rng.below(FRAGMENTS.len() as u64) as usize;
198        out.push_str(FRAGMENTS[index]);
199        // Mixed line endings within one document, which is where the CRLF
200        // handling actually gets tested.
201        match rng.below(16) {
202            0 => out.push_str("\r\n"),
203            1 => out.push('\r'),
204            _ => out.push('\n'),
205        }
206    }
207    // A document that does not end in a newline is its own case.
208    if rng.below(8) == 0 {
209        while out.ends_with(['\n', '\r']) {
210            out.pop();
211        }
212    }
213    out
214}
215
216/// A whole run: the tree to lay down, and the arguments to run in it.
217///
218/// [`document`] alone reaches the transform. It cannot reach what surrounds the
219/// transform — several files at once, an ignore file, `--files-from`, and the
220/// interaction between them, which is where the CLI corpus has cases and the
221/// generator had nothing.
222pub struct Scenario {
223    /// Relative path to contents. Parent directories are the caller's to create.
224    pub files: Vec<(String, String)>,
225    /// The arguments after the program name.
226    pub argv: Vec<String>,
227}
228
229/// Paths worth generating: nested, not nested, and one the patterns spare.
230const NAMES: [&str; 4] = ["note.md", "keep.md", "sub/nested.md", "docs/deep.md"];
231
232/// Ignore-file lines, including the shapes whose interaction decides an answer.
233const PATTERNS: [&str; 10] = [
234    "*.md",
235    "!keep.md",
236    "keep.md",
237    "sub/",
238    "docs/deep.md",
239    "/note.md",
240    "**/nested.md",
241    "# a comment",
242    "no-such-file.md",
243    "*.m?",
244];
245
246/// Build the whole scenario for `seed`.
247///
248/// Drawn from a stream of its own, so a scenario and a document with the same
249/// seed number share nothing. Every draw is unconditional for the reason
250/// [`document`] gives.
251#[must_use]
252pub fn scenario(seed: u64) -> Scenario {
253    let mut rng = Rng::new(seed ^ 0x5DEE_CE66_D000_0001);
254    let file_count = 1 + rng.below(NAMES.len() as u64 - 1) as usize;
255    // Taken in order so the names are distinct without a shuffle, which would
256    // make the draw count depend on values.
257    let mut files: Vec<(String, String)> = NAMES[..file_count]
258        .iter()
259        .map(|name| ((*name).to_owned(), document(rng.next_u64())))
260        .collect();
261
262    let pattern_count = rng.below(3) as usize;
263    let patterns: Vec<&str> = (0..pattern_count)
264        .map(|_| PATTERNS[rng.below(PATTERNS.len() as u64) as usize])
265        .collect();
266    if !patterns.is_empty() {
267        files.push((
268            ".unwrapignore".to_owned(),
269            format!("{}\n", patterns.join("\n")),
270        ));
271    }
272
273    let mut argv: Vec<String> = Vec::new();
274    if rng.below(2) == 0 {
275        argv.push("--write".to_owned());
276    }
277    if rng.below(2) == 0 {
278        argv.push("--json".to_owned());
279    }
280    if rng.below(3) == 0 {
281        argv.push("--fail-on-change".to_owned());
282    }
283    let exclude = rng.below(4);
284    if exclude < PATTERNS.len() as u64 {
285        argv.push("--exclude".to_owned());
286        argv.push(PATTERNS[exclude as usize].to_owned());
287    }
288    // Named arguments, a `--files-from` list, or both. All three reach the same
289    // filter, and that they do is the thing worth checking.
290    let names: Vec<String> = files
291        .iter()
292        .map(|(name, _)| name.clone())
293        .filter(|name| name != ".unwrapignore")
294        .collect();
295    match rng.below(3) {
296        0 => argv.extend(names),
297        1 => {
298            files.push(("list.txt".to_owned(), format!("{}\n", names.join("\n"))));
299            argv.push("--files-from".to_owned());
300            argv.push("list.txt".to_owned());
301        }
302        _ => {
303            files.push(("list.txt".to_owned(), format!("{}\n", names.join("\n"))));
304            argv.push("--files-from".to_owned());
305            argv.push("list.txt".to_owned());
306            argv.extend(names);
307        }
308    }
309    Scenario { files, argv }
310}
311
312#[cfg(test)]
313mod tests {
314    use super::*;
315    use crate::label::is_speaker_prefix;
316    use crate::scan::{is_list_line, match_list_marker};
317
318    #[test]
319    fn the_bank_reaches_its_hazards() {
320        let has = |predicate: fn(&str) -> bool| FRAGMENTS.iter().any(|f| predicate(f));
321        assert!(has(|f| f.contains('\u{1c}')), "no C0 separator");
322        assert!(has(|f| f.contains('\u{feff}')), "no byte order mark");
323        assert!(has(|f| f.ends_with("  ")), "no two-space hard break");
324        assert!(has(|f| f.ends_with('\\')), "no backslash hard break");
325        assert!(has(|f| f.contains("```")), "no backtick fence");
326        assert!(has(|f| f.contains("~~~")), "no tilde fence");
327        assert!(has(|f| f.contains("<![CDATA[")), "no CDATA");
328        assert!(has(|f| f.contains("<?")), "no processing instruction");
329        assert!(has(|f| f.starts_with("<!DOCTYPE")), "no declaration");
330        assert!(has(|f| f.contains('|')), "no table pipe");
331        assert!(has(|f| f.starts_with("> ")), "no blockquote");
332        assert!(has(is_speaker_prefix), "no speaker prefix");
333        assert!(has(|f| match_list_marker(f).is_some()), "no list marker");
334    }
335
336    #[test]
337    fn the_bank_carries_a_non_ascii_digit_that_is_not_a_marker() {
338        // The narrowing to `[0-9]` is only tested if something reaches it.
339        let digits: Vec<&&str> = FRAGMENTS
340            .iter()
341            .filter(|f| f.chars().any(|c| c.is_numeric() && !c.is_ascii_digit()))
342            .collect();
343        assert!(digits.len() >= 3, "found {digits:?}");
344        assert!(!is_list_line("\u{663}. item"));
345        assert!(match_list_marker("\u{967}\u{968}) item").is_none());
346    }
347
348    #[test]
349    fn the_speaker_boundary_pair_really_straddles_the_boundary() {
350        // `[A-Z][a-zA-Z0-9_. -]{0,39}:` — 39 characters after the first is a
351        // heading and 40 is not. Asserted rather than counted by eye.
352        let short = FRAGMENTS
353            .iter()
354            .find(|f| f.starts_with("Ae") && f.len() == 41)
355            .expect("no 39-character heading");
356        let long = FRAGMENTS
357            .iter()
358            .find(|f| f.starts_with("Ae") && f.len() == 42)
359            .expect("no 40-character heading");
360        assert_eq!(short.matches('e').count(), 39);
361        assert_eq!(long.matches('e').count(), 40);
362    }
363
364    #[test]
365    fn the_generator_is_deterministic_and_never_empty() {
366        for seed in 1..200 {
367            assert_eq!(document(seed), document(seed));
368        }
369        // Zero is a fixed point of xorshift, so it has to be mapped away.
370        assert_eq!(
371            Rng::new(0).next_u64(),
372            Rng::new(0x9E37_79B9_7F4A_7C15).next_u64()
373        );
374        let mut zero = Rng::new(0);
375        assert_ne!(zero.next_u64(), 0);
376    }
377
378    #[test]
379    fn the_generator_reaches_every_fragment() {
380        // A bank entry no seed can draw is dead weight that reports coverage.
381        let mut seen = vec![false; FRAGMENTS.len()];
382        for seed in 1..4000 {
383            let doc = document(seed);
384            for (index, fragment) in FRAGMENTS.iter().enumerate() {
385                if !fragment.is_empty() && doc.contains(fragment) {
386                    seen[index] = true;
387                }
388            }
389        }
390        let missed: Vec<&&str> = FRAGMENTS
391            .iter()
392            .zip(&seen)
393            .filter(|(fragment, hit)| !**hit && !fragment.is_empty())
394            .map(|(fragment, _)| fragment)
395            .collect();
396        assert!(missed.is_empty(), "never generated: {missed:?}");
397    }
398}
markdown_prose_hooks/fuzz.rs

markdown_prose_hooks/
fuzz.rs
