Marcos Paulo
273 lines
12 KiB
Rust
273 lines
12 KiB
Rust
//! Second-pass math scanning: the delimiters the `CommonMark` scanner misses
|
|
//! (`\(..\)`, `\[..\]`, and `$..$` / `$$..$$` with unbalanced braces), and the
|
|
//! Obsidian rules that keep ordinary text out of math.
|
|
|
|
use notescraft_markdown::{ItemKind, parse};
|
|
|
|
/// `(source, (display, expected slice) pairs in order of appearance)`.
|
|
const CASES: &[(&str, &[(bool, &str)])] = &[
|
|
// Inline `\(..\)`.
|
|
("a \\(x\\) b\n", &[(false, "\\(x\\)")]),
|
|
("\\(x^2_3 + \\frac{1}{2}\\)\n", &[(false, "\\(x^2_3 + \\frac{1}{2}\\)")]),
|
|
("\\(x\\) \\(y\\)\n", &[(false, "\\(x\\)"), (false, "\\(y\\)")]),
|
|
("é\\(x\\)é\n", &[(false, "\\(x\\)")]),
|
|
("\\(x\\)y\\(z\\)\n", &[(false, "\\(x\\)"), (false, "\\(z\\)")]),
|
|
("\\(\n", &[]),
|
|
("\\(x\n", &[]),
|
|
("\\( \n", &[]),
|
|
("\\(\\)\n", &[]),
|
|
("\\(a\nb\\)\n", &[(false, "\\(a\nb\\)")]),
|
|
("\\(a\n\nb\\)\n", &[]),
|
|
("\\(a\\\\b\\)\n", &[(false, "\\(a\\\\b\\)")]),
|
|
("\\(with \"quotes\" x\\) text\n", &[(false, "\\(with \"quotes\" x\\)")]),
|
|
("text \\(with [[link]] x\\) text\n", &[]),
|
|
("\\( \\)\n", &[(false, "\\( \\)")]),
|
|
("\\( \\frac{1}{\\} \\)\n", &[(false, "\\( \\frac{1}{\\} \\)")]),
|
|
("\\( \\frac{1}{ \\) \\)\n", &[(false, "\\( \\frac{1}{ \\)")]),
|
|
// display `\[..\]`.
|
|
("x \\[y\\] z\n", &[(true, "\\[y\\]")]),
|
|
("\\[a\nb\\]\n", &[(true, "\\[a\nb\\]")]),
|
|
("\\[a\n\nb\\]\n", &[(true, "\\[a\n\nb\\]")]),
|
|
("\\[a\n\n\nb\\]\n", &[(true, "\\[a\n\n\nb\\]")]),
|
|
("\\[\\frac{1}{2}\\]\n", &[(true, "\\[\\frac{1}{2}\\]")]),
|
|
("\\[\\]\n", &[]),
|
|
("\\[x\n", &[]),
|
|
("\\[x\\] \\[y\\]\n", &[(true, "\\[x\\]"), (true, "\\[y\\]")]),
|
|
("\\(x\\)\\[y\\]\n", &[(false, "\\(x\\)"), (true, "\\[y\\]")]),
|
|
("(a) [b] no backslash\n", &[]),
|
|
("x\\[y\\]\n", &[(true, "\\[y\\]")]),
|
|
(r"\\\(x\)", &[(false, r"\(x\)")]),
|
|
(r"\\\\\(x\)", &[(false, r"\(x\)")]),
|
|
(r"\\\\\\(x\)", &[]),
|
|
(r"\\\\[x\]", &[]),
|
|
("\\[ \\frac{1}{\\} \\]\n", &[(true, "\\[ \\frac{1}{\\} \\]")]),
|
|
// Unbalanced TeX braces inside `$..$` / `$$..$$`.
|
|
("$\\frac{1}{$\n", &[(false, "$\\frac{1}{$")]),
|
|
("$\\frac{1}{$ b\n", &[(false, "$\\frac{1}{$")]),
|
|
("$$\\frac{1}{$$\n", &[(true, "$$\\frac{1}{$$")]),
|
|
("$\\frac{1}{$\\frac{2}{$\n", &[(false, "$\\frac{1}{$")]),
|
|
("$a$$b$\n", &[(false, "$a$"), (false, "$b$")]),
|
|
("$\\foo{\\bar{$\n", &[(false, "$\\foo{\\bar{$")]),
|
|
("$\\sqrt{\\frac{x}{y}\n", &[]),
|
|
("$\\frac{1}{$ inside \\(y\\) plain\n", &[(false, "$\\frac{1}{$"), (false, "\\(y\\)")]),
|
|
// Currency.
|
|
("$5 and $10\n", &[]),
|
|
("$5$ is five\n", &[(false, "$5$")]),
|
|
("$5 x$\n", &[(false, "$5 x$")]),
|
|
("$$100$$\n", &[(true, "$$100$$")]),
|
|
("$5 and $10$ x\n", &[(false, "$10$")]),
|
|
("$1 2 3 $b$\n", &[(false, "$b$")]),
|
|
("$x$ costs 5 dollars\n", &[(false, "$x$")]),
|
|
("$10\n", &[]),
|
|
// Whitespace around the inline delimiter.
|
|
("$ x$\n", &[]),
|
|
("$x $\n", &[]),
|
|
("$x$\n", &[(false, "$x$")]),
|
|
("$x$", &[(false, "$x$")]),
|
|
("$x\ty$\n", &[(false, "$x\ty$")]),
|
|
("$$\n", &[]),
|
|
("\n$\n", &[]),
|
|
("$ \n", &[]),
|
|
// Escapes.
|
|
("\\$x$\n", &[]),
|
|
("$a\\$b$\n", &[(false, "$a\\$b$")]),
|
|
("\\\\$x$\n", &[(false, "$x$")]),
|
|
("$a\\\\$$b$\n", &[(false, "$a\\\\$"), (false, "$b$")]),
|
|
("$x\\$\n", &[]),
|
|
("\\(x\\)\\$y$\n", &[(false, "\\(x\\)")]),
|
|
("$\\$$\n", &[(false, "$\\$$")]),
|
|
// Code and markup contexts that stay untouched.
|
|
("`$x$`\n", &[]),
|
|
("```\n$x$\n```\n", &[]),
|
|
("a\n\n $y$\n", &[]),
|
|
("<div>\n$x$\n</div>\n", &[]),
|
|
("a<b class='$x$'>c\n", &[]),
|
|
("---\ntitle: $x$\n---\n$y$\n", &[(false, "$y$")]),
|
|
("\n", &[(false, "$x$")]),
|
|
("\n", &[(false, "$x$")]),
|
|
("[a](file $ x.md)\n", &[]),
|
|
("[a]($x$.md)\n", &[]),
|
|
("[a]: http://x/$y$.md\n", &[]),
|
|
("`$` and `$`\n", &[]),
|
|
("[- $x$ -]\n", &[(false, "$x$")]),
|
|
// Adjacent and nested formulas.
|
|
("$a$ $b$\n", &[(false, "$a$"), (false, "$b$")]),
|
|
("$a$\\(b\\)\n", &[(false, "$a$"), (false, "\\(b\\)")]),
|
|
("$x$ and $y$ and $z$\n", &[(false, "$x$"), (false, "$y$"), (false, "$z$")]),
|
|
("$x$y$\n", &[(false, "$x$")]),
|
|
("$$x$$y$$z$$\n", &[(true, "$$x$$"), (true, "$$z$$")]),
|
|
("a $$ $ b $$ c\n", &[(true, "$$ $ b $$")]),
|
|
("$$x$$\ny$$z$$\n", &[(true, "$$x$$"), (true, "$$z$$")]),
|
|
("\\(a$x$b\\)\n", &[(false, "$x$")]),
|
|
("$ a \\(b\\) c$\n", &[(false, "\\(b\\)")]),
|
|
("$x$\\[y\\]$z$\n", &[(false, "$x$"), (true, "\\[y\\]"), (false, "$z$")]),
|
|
("1$$2$$3\n", &[(true, "$$2$$")]),
|
|
("a $$$b$ c\n", &[(false, "$b$")]),
|
|
("$$x$$$y$\n", &[(true, "$$x$$"), (false, "$y$")]),
|
|
("$x$\\$y$\n", &[(false, "$x$")]),
|
|
("$$a$$\n$$\nb\n$$\n", &[(true, "$$a$$"), (true, "$$\nb\n$$")]),
|
|
("$\\$$\n", &[(false, "$\\$$")]),
|
|
// Line endings and blank lines.
|
|
("$a\nb$\r\n", &[(false, "$a\nb$")]),
|
|
("$a\r\n\rb$\r\n", &[]),
|
|
("$$a\r\n$$\r\n", &[(true, "$$a\r\n$$")]),
|
|
("\\(x\\)\r\n", &[(false, "\\(x\\)")]),
|
|
("$a$ $b$\r\n", &[(false, "$a$"), (false, "$b$")]),
|
|
("\\[a\r\nb\\]\r\n", &[(true, "\\[a\r\nb\\]")]),
|
|
("$$a\n\nb$$\n", &[(true, "$$a\n\nb$$")]),
|
|
("a $$ b\n\n$$\n", &[(true, "$$ b\n\n$$")]),
|
|
("$$\n$$\n", &[(true, "$$\n$$")]),
|
|
// Structural contexts.
|
|
("- \\(x\\)\n- $y$\n", &[(false, "\\(x\\)"), (false, "$y$")]),
|
|
("# \\(x\\)\n", &[]),
|
|
("%%\\(x\\)%%\n", &[]),
|
|
("==\\(x\\)==\n", &[]),
|
|
("> \\(x\\) y\n", &[(false, "\\(x\\)")]),
|
|
("^id\n\\(x\\)\n", &[(false, "\\(x\\)")]),
|
|
("| \\(x\\) |\n|---|\n| \\[y\\] |\n", &[(false, "\\(x\\)"), (true, "\\[y\\]")]),
|
|
];
|
|
|
|
/// The invariant of every table row: lossless, items on char boundaries,
|
|
/// math ranges never overlapping each other.
|
|
fn check_shape(src: &str) {
|
|
let doc = parse(src);
|
|
assert_eq!(doc.write(), src, "parsing must stay lossless");
|
|
let mut math: Vec<(usize, usize)> = doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })).map(|i| (i.range.start, i.range.end)).collect();
|
|
for &(s, e) in &math {
|
|
assert!(doc.source.is_char_boundary(s) && doc.source.is_char_boundary(e), "math range {s}..{e} splits a char");
|
|
}
|
|
math.sort_unstable();
|
|
for pair in math.windows(2) {
|
|
assert!(pair[0].1 <= pair[1].0, "math items overlap: {pair:?} of {src:?}, {doc:?}");
|
|
}
|
|
}
|
|
|
|
/// Every table row yields exactly the expected math, inline or display.
|
|
#[test]
|
|
fn cases() {
|
|
let mut ran = 0usize;
|
|
for (source, expected) in CASES {
|
|
check_shape(source);
|
|
let doc = parse(source);
|
|
let math: Vec<(bool, String)> = doc
|
|
.items
|
|
.iter()
|
|
.filter_map(|i| match i.kind {
|
|
ItemKind::Math { display } => doc.source.get(i.range.clone()).map(|slice| (display, slice.to_owned())),
|
|
_ => None,
|
|
})
|
|
.collect();
|
|
let expected: Vec<(bool, String)> = expected.iter().map(|(display, text)| (*display, text.to_string())).collect();
|
|
assert_eq!(math, expected, "case {ran}: {source:?}");
|
|
ran += 1;
|
|
}
|
|
assert!(ran >= 80, "the table shrank to {ran} cases");
|
|
}
|
|
|
|
/// A body of exactly the cap forms a 20 000 char formula; one char more is plain text.
|
|
#[test]
|
|
fn formula_length_cap() {
|
|
let body = |n: usize| "a".repeat(n);
|
|
// The boundary is this pass's to decide: balanced `$..$` bodies are
|
|
// found by the CommonMark scanner first, so build the bodies with an
|
|
// unbalanced brace. `$` + `\frac{` + extras + `$` is `8 + n` bytes.
|
|
for (extra, expected) in [(19_992, true), (19_993, false)] {
|
|
let src = format!("$\\frac{{{}$\n", body(extra));
|
|
let math = parse(&src).items.iter().any(|i| matches!(i.kind, ItemKind::Math { .. }));
|
|
assert_eq!(math, expected, "$ body with `{extra}` extras");
|
|
if expected {
|
|
let doc = parse(&src);
|
|
let found = doc.items.iter().find(|i| matches!(i.kind, ItemKind::Math { .. }));
|
|
assert_eq!(found.map(|i| i.range.end - i.range.start), Some(20_000));
|
|
}
|
|
}
|
|
// `$$…$$`, `\(…)` and `\[…]`: `2 + (6 + n) + 2 = 10 + n` chars.
|
|
for (extra, expected) in [(19_990, true), (19_991, false)] {
|
|
for (open, close) in [("$$", "$$"), (r"\(", r"\)"), (r"\[", r"\]")] {
|
|
let src = format!("{open}\\frac{{{}{close}\n", body(extra));
|
|
let math = parse(&src).items.iter().any(|i| matches!(i.kind, ItemKind::Math { .. }));
|
|
assert_eq!(math, expected, "`{open}` body with `{extra}` extras");
|
|
}
|
|
}
|
|
}
|
|
|
|
/// At most 10 000 missed formulas become items per document.
|
|
#[test]
|
|
fn formula_count_cap() {
|
|
let one = r"\(x\) ";
|
|
let src = format!("{one}{}", one.repeat(10_000));
|
|
let doc = parse(&src);
|
|
let math = doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })).count();
|
|
assert_eq!(math, 10_000);
|
|
for (i, item) in doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })).enumerate() {
|
|
assert_eq!(doc.source.get(item.range.clone()), Some(r"\(x\)"), "item {i} at {}", item.range.start);
|
|
assert_eq!(item.range.start, 6 * i, "item {i} sits where the one {i} formulas of `\\(x\\) ` bytes end");
|
|
}
|
|
}
|
|
|
|
/// A 1 MiB document of bare `$` characters parses in bounded time and space
|
|
/// (single left-to-right scan, no quadratic behaviour), stays lossless.
|
|
#[test]
|
|
fn huge_dollar_run_is_bounded() {
|
|
let src = "$".repeat(1_000_000);
|
|
let doc = parse(&src);
|
|
assert_eq!(doc.write(), src.as_str());
|
|
let math = doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })).count();
|
|
assert!(math <= 500_001, "at most one item per delimiter pair: {math}");
|
|
}
|
|
|
|
/// Dense unclosed `\(..` openers must not rescans; the scan stays linear.
|
|
#[test]
|
|
fn dense_unclosed_parens_are_bounded() {
|
|
let src = format!("{}\n", "\\( ".repeat(100_000));
|
|
let doc = parse(&src);
|
|
assert_eq!(doc.write(), src.as_str());
|
|
assert_eq!(doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })).count(), 0);
|
|
}
|
|
|
|
/// `$x$` pairs in a big document: every one is found, in bounded time.
|
|
#[test]
|
|
fn many_formulas_are_bounded() {
|
|
let one = "$x$\n";
|
|
let src = one.repeat(25_000);
|
|
let doc = parse(&src);
|
|
assert_eq!(doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })).count(), 25_000);
|
|
assert_eq!(doc.write(), src.as_str());
|
|
}
|
|
|
|
/// Round trip on pseudo-random input: lossless, and the ranges of math items
|
|
/// sit on char boundaries, describe a delimiter pair and never overlap.
|
|
#[test]
|
|
fn xorshift_round_trip_stays_lossless_and_well_formed() {
|
|
let alphabet: &[char] = &['$', '\\', '(', ')', '[', ']', '{', '}', 'a', ' ', '\n'];
|
|
let mut seed = 0x2545_F491_4F6C_DD1D_u64;
|
|
let mut next = || {
|
|
seed ^= seed << 13;
|
|
seed ^= seed >> 7;
|
|
seed ^= seed << 17;
|
|
seed
|
|
};
|
|
for _ in 0..2_000 {
|
|
let len = 1 + (next() % 60) as usize;
|
|
let src: String = (0..len)
|
|
.map(|_| {
|
|
let pick = usize::try_from(next() % alphabet.len() as u64).unwrap_or(0);
|
|
*alphabet.get(pick).unwrap_or(&'a')
|
|
})
|
|
.collect();
|
|
check_shape(&src);
|
|
let doc = parse(&src);
|
|
for item in doc.items.iter().filter(|i| matches!(i.kind, ItemKind::Math { .. })) {
|
|
let slice = doc.source.get(item.range.clone()).unwrap_or("");
|
|
let matching = |open: &str, close: &str, wanted: bool| {
|
|
slice.starts_with(open) && slice.ends_with(close) && matches!(item.kind, ItemKind::Math { display } if display == wanted)
|
|
};
|
|
assert!(
|
|
matching("$", "$", false) || matching("$$", "$$", true) || matching("\\(", "\\)", false) || matching("\\[", "\\]", true),
|
|
"math slice {slice:?} is not a delimiter pair: {}",
|
|
doc.items.len()
|
|
);
|
|
}
|
|
}
|
|
}
|