1//! Equations in the linear format of OneNote's equation editor (UnicodeMath): what Linear
2//! shows and what typing builds up. `Math::from_linear` reads the typed or shown text into the
3//! tree `Math::paragraph` stores; `Math::linear` writes a tree the way Linear shows it. Both
4//! follow the equation editor as observed (`corpus/math-edit/native-linear`): a space that
5//! ends a built object is consumed, other spaces stay, and an n-ary operator takes the rest
6//! of its row as its body.
7
8use super::Math;
9use super::math::{italic, plain};
10use super::text::Paragraph;
11use crate::document::Format;
12
13/// N-ary operators, which take limits and a body when a script follows them.
14const NARY: &[char] = &[
15 '∑', '∏', '∐', '∫', '∬', '∭', '∮', '∯', '∰', '⋀', '⋁', '⋂', '⋃', '⨀', '⨁', '⨂', '⨄', '⨅', '⨆',
16];
17
18/// Function names the equation editor sets upright; those that take a limit below take it
19/// from a subscript.
20const FUNCTIONS: &[&str] = &[
21 "lim", "max", "min", "sup", "inf", "det", "gcd", "sin", "cos", "tan", "sec", "csc", "cot",
22 "sinh", "cosh", "tanh", "log", "ln", "exp", "arg",
23];
24const LIMITS: &[&str] = &["lim", "max", "min", "sup", "inf", "det", "gcd"];
25
26/// The equation editor's control words: `\name` and the space after it become the symbol.
27const CONTROL_WORDS: &[(&str, char)] = &[
28 ("alpha", 'α'),
29 ("beta", 'β'),
30 ("gamma", 'γ'),
31 ("delta", 'δ'),
32 ("epsilon", 'ϵ'),
33 ("varepsilon", 'ε'),
34 ("zeta", 'ζ'),
35 ("eta", 'η'),
36 ("theta", 'θ'),
37 ("vartheta", 'ϑ'),
38 ("iota", 'ι'),
39 ("kappa", 'κ'),
40 ("lambda", 'λ'),
41 ("mu", 'μ'),
42 ("nu", 'ν'),
43 ("xi", 'ξ'),
44 ("pi", 'π'),
45 ("rho", 'ρ'),
46 ("sigma", 'σ'),
47 ("tau", 'τ'),
48 ("upsilon", 'υ'),
49 ("phi", 'ϕ'),
50 ("varphi", 'φ'),
51 ("chi", 'χ'),
52 ("psi", 'ψ'),
53 ("omega", 'ω'),
54 ("Gamma", 'Γ'),
55 ("Delta", 'Δ'),
56 ("Theta", 'Θ'),
57 ("Lambda", 'Λ'),
58 ("Xi", 'Ξ'),
59 ("Pi", 'Π'),
60 ("Sigma", 'Σ'),
61 ("Upsilon", 'Υ'),
62 ("Phi", 'Φ'),
63 ("Psi", 'Ψ'),
64 ("Omega", 'Ω'),
65 ("to", '→'),
66 ("rightarrow", '→'),
67 ("leftarrow", '←'),
68 ("times", '×'),
69 ("div", '÷'),
70 ("pm", '±'),
71 ("mp", '∓'),
72 ("infty", '∞'),
73 ("le", '≤'),
74 ("ge", '≥'),
75 ("ne", '≠'),
76 ("approx", '≈'),
77 ("equiv", '≡'),
78 ("sim", '∼'),
79 ("propto", '∝'),
80 ("cdot", '⋅'),
81 ("partial", '∂'),
82 ("nabla", '∇'),
83 ("in", '∈'),
84 ("notin", '∉'),
85 ("subset", '⊂'),
86 ("supset", '⊃'),
87 ("cup", '∪'),
88 ("cap", '∩'),
89 ("forall", '∀'),
90 ("exists", '∃'),
91 ("ll", '≪'),
92 ("gg", '≫'),
93 ("ldots", '…'),
94 ("cdots", '⋯'),
95 ("sum", '∑'),
96 ("prod", '∏'),
97 ("coprod", '∐'),
98 ("int", '∫'),
99 ("iint", '∬'),
100 ("iiint", '∭'),
101 ("oint", '∮'),
102 ("bigcap", '⋂'),
103 ("bigcup", '⋃'),
104 ("sqrt", '√'),
105 ("cbrt", '∛'),
106 ("qdrt", '∜'),
107 ("matrix", '■'),
108 ("eqarray", '█'),
109 ("box", '□'),
110 ("rect", '▭'),
111 ("overline", '¯'),
112 ("above", '┴'),
113 ("below", '┬'),
114 ("naryand", '▒'),
115 ("hat", '\u{302}'),
116 ("tilde", '\u{303}'),
117 ("bar", '\u{305}'),
118 ("dot", '\u{307}'),
119 ("ddot", '\u{308}'),
120 ("check", '\u{30c}'),
121 ("vec", '\u{20d7}'),
122];
123
124fn object(kind: u32, symbols: Vec<char>, columns: Option<u8>, arguments: Vec<Vec<Math>>) -> Math {
125 Math::Object {
126 kind,
127 symbols,
128 columns,
129 arguments,
130 }
131}
132
133fn accent(c: char) -> bool {
134 matches!(u32::from(c), 0x300..=0x36f | 0x20d0..=0x20ff)
135}
136
137fn closing(open: char) -> Option<char> {
138 Some(match open {
139 '(' => ')',
140 '[' => ']',
141 '{' => '}',
142 '⟨' => '⟩',
143 '〖' => '〗',
144 _ => return None,
145 })
146}
147
148struct Parser {
149 chars: Vec<char>,
150 at: usize,
151 /// Text still being typed: a construct whose last operand is missing stays as typed.
152 typing: bool,
153}
154
155impl Parser {
156 fn peek(&self) -> Option<char> {
157 self.chars.get(self.at).copied()
158 }
159
160 /// A space ending a built object triggered the build and is not kept.
161 fn built(&mut self, out: &mut Vec<Math>, node: Math) {
162 out.push(node);
163 if self.peek() == Some(' ') {
164 self.at += 1;
165 }
166 }
167
168 fn sequence(&mut self, stops: &[char]) -> Vec<Math> {
169 let mut out = Vec::new();
170 while let Some(c) = self.peek() {
171 if stops.contains(&c) {
172 break;
173 }
174 self.element(&mut out, stops);
175 }
176 out
177 }
178
179 fn element(&mut self, out: &mut Vec<Math>, stops: &[char]) {
180 let c = self.peek().unwrap();
181 let next = self.chars.get(self.at + 1).copied();
182 match c {
183 '/' => {
184 self.at += 1;
185 let denominator = stripped(self.run(stops));
186 if self.typing && denominator.is_empty() {
187 out.push(Math::Operator(c));
188 return;
189 }
190 let start = out
191 .iter()
192 .rposition(|node| matches!(node, Math::Operator(_)))
193 .map_or(0, |at| at + 1);
194 let numerator = stripped(out.split_off(start));
195 self.built(
196 out,
197 object(16, vec!['/'], None, vec![numerator, denominator]),
198 );
199 }
200 '^' | '_' => self.script(out),
201 '┴' | '┬' => {
202 self.at += 1;
203 let argument = self.operand();
204 if self.typing && argument.is_empty() {
205 out.push(Math::Operator(c));
206 return;
207 }
208 let base = out.pop().into_iter().collect();
209 let kind = if c == '┴' { 33 } else { 19 };
210 self.built(out, object(kind, vec![c], None, vec![base, argument]));
211 }
212 '\u{a0}' if next.is_some_and(accent) => self.at += 1,
213 c if accent(c) => {
214 self.at += 1;
215 if matches!(out.last(), Some(Math::Operator(' ' | '\u{a0}'))) {
216 out.pop();
217 }
218 let base = stripped(out.pop().into_iter().collect());
219 self.built(out, object(10, vec![c], None, vec![base]));
220 }
221 c if NARY.contains(&c) && matches!(next, Some('_' | '^' | '▒')) => {
222 self.at += 1;
223 let limits = self.at;
224 let (mut lower, mut upper) = (None, None);
225 loop {
226 match self.peek() {
227 Some('_') if lower.is_none() => {
228 self.at += 1;
229 lower = Some(self.operand());
230 }
231 Some('^') if upper.is_none() => {
232 self.at += 1;
233 upper = Some(self.operand());
234 }
235 _ => break,
236 }
237 }
238 if self.typing && [&lower, &upper].contains(&&Some(Vec::new())) {
239 self.at = limits;
240 out.push(Math::Operator(c));
241 return;
242 }
243 let body = match self.peek() {
244 Some('▒') => {
245 self.at += 1;
246 self.operand()
247 }
248 Some(' ') => {
249 self.at += 1;
250 self.sequence(stops)
251 }
252 _ => self.sequence(stops),
253 };
254 out.push(object(
255 21,
256 vec![c],
257 None,
258 vec![lower.unwrap_or_default(), upper.unwrap_or_default(), body],
259 ));
260 }
261 '〖' => {
262 self.at += 1;
263 let inner = self.sequence(&['〗']);
264 if self.peek() == Some('〗') {
265 self.at += 1;
266 }
267 out.extend(inner);
268 }
269 _ => {
270 let node = self.factor();
271 if matches!(node, Math::Object { .. }) {
272 self.built(out, node);
273 } else {
274 out.push(node);
275 }
276 }
277 }
278 }
279
280 fn script(&mut self, out: &mut Vec<Math>) {
281 let first = self.peek().unwrap();
282 self.at += 1;
283 let script = self.operand();
284 if self.typing && script.is_empty() {
285 out.push(Math::Operator(first));
286 return;
287 }
288 let base: Vec<Math> = out.pop().into_iter().collect();
289 let other = if first == '_' { '^' } else { '_' };
290 let node = if self.peek() == Some(other) {
291 self.at += 1;
292 let second = self.operand();
293 let (lower, upper) = if first == '_' {
294 (script, second)
295 } else {
296 (second, script)
297 };
298 object(30, vec!['_'], None, vec![base, lower, upper])
299 } else if first == '_'
300 && matches!(&base[..], [Math::Function(name)] if LIMITS.contains(&name.as_str()))
301 {
302 object(19, vec!['_'], None, vec![base, script])
303 } else {
304 let kind = if first == '^' { 31 } else { 29 };
305 object(kind, vec![first], None, vec![base, script])
306 };
307 self.built(out, node);
308 }
309
310 /// One factor as an object's argument: parentheses and the invisible grouping brackets
311 /// only group it.
312 fn operand(&mut self) -> Vec<Math> {
313 match self.peek() {
314 Some(open @ ('(' | '〖')) => {
315 let start = self.at;
316 self.at += 1;
317 let close = closing(open).unwrap();
318 let inner = self.sequence(&[close]);
319 if self.peek() == Some(close) {
320 self.at += 1;
321 } else if self.typing {
322 // A group still open is still being typed.
323 self.at = start;
324 return Vec::new();
325 }
326 inner
327 }
328 // An argument not typed yet stays empty for the caret.
329 Some(' ') | None => Vec::new(),
330 Some(_) => vec![self.factor()],
331 }
332 }
333
334 /// Juxtaposed factors with their scripts, as a fraction's denominator.
335 fn run(&mut self, stops: &[char]) -> Vec<Math> {
336 let mut out = Vec::new();
337 while let Some(c) = self.peek() {
338 if stops.contains(&c) {
339 break;
340 }
341 let starts = c.is_alphanumeric()
342 || closing(c).is_some()
343 || matches!(c, '√' | '∛' | '∜' | '■' | '█' | '□' | '▭' | '¯');
344 if matches!(c, '^' | '_') && !out.is_empty() {
345 self.script(&mut out);
346 } else if starts {
347 out.push(self.factor());
348 } else {
349 break;
350 }
351 }
352 out
353 }
354
355 fn factor(&mut self) -> Math {
356 let c = self.peek().unwrap();
357 self.at += 1;
358 if c.is_ascii_digit() {
359 let mut number = c.to_string();
360 while let Some(digit) = self.peek().filter(char::is_ascii_digit) {
361 number.push(digit);
362 self.at += 1;
363 }
364 return Math::Number(number);
365 }
366 if c.is_ascii_alphabetic() {
367 let word: String = self.chars[self.at - 1..]
368 .iter()
369 .take_while(|c| c.is_ascii_alphabetic())
370 .collect();
371 if FUNCTIONS.contains(&word.as_str()) {
372 self.at += word.len() - 1;
373 return Math::Function(word);
374 }
375 return Math::Identifier(c);
376 }
377 if c.is_alphabetic() {
378 return Math::Identifier(plain(c));
379 }
380 if let Some(close) = closing(c) {
381 let start = self.at;
382 let inner = self.sequence(&[close]);
383 if self.peek() == Some(close) {
384 self.at += 1;
385 return object(13, vec![c, close], None, vec![inner]);
386 }
387 self.at = start;
388 return Math::Operator(c);
389 }
390 match c {
391 '√' | '∛' | '∜' => {
392 let degree = match c {
393 '∛' => vec![Math::Number("3".into())],
394 '∜' => vec![Math::Number("4".into())],
395 _ => Vec::new(),
396 };
397 let (degree, radicand) = if c == '√' && self.peek() == Some('(') {
398 self.at += 1;
399 let first = self.sequence(&[')', '&']);
400 let parts = if self.peek() == Some('&') {
401 self.at += 1;
402 (first, self.sequence(&[')']))
403 } else {
404 (degree, first)
405 };
406 if self.peek() == Some(')') {
407 self.at += 1;
408 }
409 parts
410 } else {
411 (degree, self.operand())
412 };
413 if self.typing && radicand.is_empty() {
414 return Math::Operator(c);
415 }
416 object(25, vec!['√'], None, vec![degree, radicand])
417 }
418 '■' | '█' if self.peek() == Some('(') => {
419 self.at += 1;
420 let matrix = c == '■';
421 let mut rows = vec![Vec::new()];
422 loop {
423 let stops: &[char] = if matrix {
424 &[')', '&', '@']
425 } else {
426 &[')', '@']
427 };
428 let cell = self.sequence(stops);
429 rows.last_mut().unwrap().push(cell);
430 match self.peek() {
431 Some('&') => self.at += 1,
432 Some('@') => {
433 self.at += 1;
434 rows.push(Vec::new());
435 }
436 Some(_) => {
437 self.at += 1;
438 break;
439 }
440 None => break,
441 }
442 }
443 if matrix {
444 let columns = rows.iter().map(Vec::len).max().unwrap_or(1);
445 let arguments = rows
446 .into_iter()
447 .flat_map(|mut row| {
448 row.resize(columns, Vec::new());
449 row
450 })
451 .collect();
452 object(20, vec!['■'], u8::try_from(columns).ok(), arguments)
453 } else {
454 let arguments = rows.into_iter().flatten().collect();
455 object(15, vec!['█'], Some(1), arguments)
456 }
457 }
458 '□' | '▭' | '¯' => {
459 let kind = match c {
460 '□' => 11,
461 '▭' => 12,
462 _ => 23,
463 };
464 let inner = self.operand();
465 if self.typing && inner.is_empty() {
466 return Math::Operator(c);
467 }
468 object(kind, vec![c], None, vec![inner])
469 }
470 c => Math::Operator(c),
471 }
472 }
473}
474
475/// A lone parenthesized group as an argument only groups it.
476fn stripped(nodes: Vec<Math>) -> Vec<Math> {
477 match <[Math; 1]>::try_from(nodes) {
478 Ok(
479 [
480 Math::Object {
481 kind: 13,
482 symbols,
483 mut arguments,
484 ..
485 },
486 ],
487 ) if symbols == ['(', ')'] && arguments.len() == 1 => arguments.pop().unwrap(),
488 Ok([node]) => vec![node],
489 Err(nodes) => nodes,
490 }
491}
492
493/// Replaces control words with their symbols; an unknown one stays as typed.
494fn expand(text: &str) -> Vec<char> {
495 let chars: Vec<char> = text.chars().collect();
496 let mut out = Vec::with_capacity(chars.len());
497 let mut at = 0;
498 while at < chars.len() {
499 if chars[at] == '\\' {
500 let name: String = chars[at + 1..]
501 .iter()
502 .take_while(|c| c.is_ascii_alphabetic())
503 .collect();
504 if let Some((_, symbol)) = CONTROL_WORDS.iter().find(|(word, _)| *word == name) {
505 out.push(*symbol);
506 at += 1 + name.len();
507 if chars.get(at) == Some(&' ') {
508 at += 1;
509 }
510 continue;
511 }
512 }
513 out.push(chars[at]);
514 at += 1;
515 }
516 out
517}
518
519impl Math {
520 /// The equation typed or shown as `text` in the linear format, built up.
521 pub fn from_linear(text: &str) -> Vec<Math> {
522 Parser {
523 chars: expand(text),
524 at: 0,
525 typing: false,
526 }
527 .sequence(&[])
528 }
529
530 /// What the equation editor builds as `text` is typed: as [`Math::from_linear`], but a
531 /// construct still missing its last operand stays as typed, and an n-ary operator's
532 /// empty body waits for the caret.
533 pub fn typed(text: &str) -> Vec<Math> {
534 Parser {
535 chars: expand(text),
536 at: 0,
537 typing: true,
538 }
539 .sequence(&[])
540 }
541
542 /// The paragraph OneNote stores for an equation shown in the linear format: its linear
543 /// text in one run of math over `base`.
544 pub fn linear_paragraph(nodes: &[Math], base: &Format) -> Option<Paragraph> {
545 Some(Paragraph::new(Self::linear(nodes)?, Self::format(base)))
546 }
547
548 /// The linear format Linear shows for `nodes`, letters in mathematical italic; `None`
549 /// where an object has no linear form here.
550 pub fn linear(nodes: &[Math]) -> Option<String> {
551 let mut out = String::new();
552 write(nodes, &mut out)?;
553 Some(out)
554 }
555}
556
557fn write(nodes: &[Math], out: &mut String) -> Option<()> {
558 let mut after_object = false;
559 for node in nodes {
560 match node {
561 Math::Identifier(c) => out.push(italic(*c)),
562 Math::Function(name) => out.push_str(name),
563 Math::Number(n) => out.push_str(n),
564 // Reading consumes one space after an object.
565 Math::Operator(' ') if after_object => out.push_str(" "),
566 Math::Operator(c) => out.push(*c),
567 Math::Object {
568 kind,
569 symbols,
570 arguments,
571 columns,
572 } => write_object(*kind, symbols, *columns, arguments, out)?,
573 }
574 after_object = matches!(node, Math::Object { .. });
575 }
576 Some(())
577}
578
579/// An argument that reads back as one factor stands bare; others are parenthesized.
580fn argument(nodes: &[Math], out: &mut String) -> Option<()> {
581 let bare = match nodes {
582 [Math::Identifier(_) | Math::Number(_) | Math::Function(_)] => true,
583 [Math::Object { kind, symbols, .. }] => {
584 matches!(kind, 11 | 12 | 15 | 20 | 23 | 25) || *kind == 13 && symbols[..] != ['(', ')']
585 }
586 _ => false,
587 };
588 if bare {
589 return write(nodes, out);
590 }
591 out.push('(');
592 write(nodes, out)?;
593 out.push(')');
594 Some(())
595}
596
597/// A fraction's part stands bare when it reads back as one run of factors.
598fn part(nodes: &[Math], out: &mut String) -> Option<()> {
599 let bare = !nodes.is_empty()
600 && !matches!(nodes, [Math::Object { kind: 13, symbols, .. }] if symbols[..] == ['(', ')'])
601 && nodes.iter().all(|node| match node {
602 Math::Operator(_) => false,
603 Math::Object { kind, .. } => !matches!(kind, 10 | 16 | 19 | 21 | 33),
604 _ => true,
605 });
606 if bare {
607 return write(nodes, out);
608 }
609 out.push('(');
610 write(nodes, out)?;
611 out.push(')');
612 Some(())
613}
614
615fn write_object(
616 kind: u32,
617 symbols: &[char],
618 columns: Option<u8>,
619 arguments: &[Vec<Math>],
620 out: &mut String,
621) -> Option<()> {
622 match (kind, arguments) {
623 (31, [base, sup]) => {
624 argument(base, out)?;
625 out.push('^');
626 argument(sup, out)
627 }
628 (29, [base, sub]) => {
629 argument(base, out)?;
630 out.push('_');
631 argument(sub, out)
632 }
633 (30, [base, sub, sup]) => {
634 argument(base, out)?;
635 out.push('_');
636 argument(sub, out)?;
637 out.push('^');
638 argument(sup, out)
639 }
640 (16, [numerator, denominator]) => {
641 part(numerator, out)?;
642 out.push('/');
643 part(denominator, out)
644 }
645 (13, [inner]) => {
646 out.push(symbols.first().copied().unwrap_or('('));
647 write(inner, out)?;
648 out.push(symbols.get(1).copied().unwrap_or(')'));
649 Some(())
650 }
651 (21, [lower, upper, body]) => {
652 out.push(symbols.first().copied().unwrap_or('∑'));
653 if !lower.is_empty() {
654 out.push('_');
655 argument(lower, out)?;
656 }
657 if !upper.is_empty() {
658 out.push('^');
659 argument(upper, out)?;
660 }
661 out.push('▒');
662 match &body[..] {
663 [Math::Identifier(_) | Math::Number(_)] => write(body, out),
664 _ => {
665 out.push('〖');
666 write(body, out)?;
667 out.push('〗');
668 Some(())
669 }
670 }
671 }
672 (25, [degree, radicand]) => {
673 match &degree[..] {
674 [] => out.push('√'),
675 [Math::Number(n)] if n == "3" => out.push('∛'),
676 [Math::Number(n)] if n == "4" => out.push('∜'),
677 _ => {
678 out.push_str("√(");
679 write(degree, out)?;
680 out.push('&');
681 write(radicand, out)?;
682 out.push(')');
683 return Some(());
684 }
685 }
686 argument(radicand, out)
687 }
688 (19, [base, below]) => {
689 argument(base, out)?;
690 out.push(if symbols == ['_'] { '_' } else { '┬' });
691 argument(below, out)
692 }
693 (33, [base, above]) => {
694 argument(base, out)?;
695 out.push('┴');
696 argument(above, out)
697 }
698 (10, [base]) => {
699 argument(base, out)?;
700 out.push('\u{a0}');
701 out.push(*symbols.first()?);
702 Some(())
703 }
704 (11, [inner]) if symbols == ['□'] => {
705 out.push('□');
706 argument(inner, out)
707 }
708 (12, [inner]) if symbols == ['▭'] => {
709 out.push('▭');
710 argument(inner, out)
711 }
712 (23, [inner]) if symbols == ['¯'] => {
713 out.push('¯');
714 argument(inner, out)
715 }
716 (20, cells) => {
717 let width = usize::from(columns?.max(1));
718 out.push_str("■(");
719 for (index, cell) in cells.iter().enumerate() {
720 if index > 0 {
721 out.push(if index % width == 0 { '@' } else { '&' });
722 }
723 write(cell, out)?;
724 }
725 out.push(')');
726 Some(())
727 }
728 (15, rows) => {
729 out.push_str("█(");
730 for (index, row) in rows.iter().enumerate() {
731 if index > 0 {
732 out.push('@');
733 }
734 write(row, out)?;
735 }
736 out.push(')');
737 Some(())
738 }
739 _ => None,
740 }
741}