internal/texmath/texmath.go
759 lines · 18336 bytes
1// Package texmath converts a subset of TeX math to MathML.
2//
3// The subset: letters, numbers and operator characters; ^ and _; braces;
4// \frac and friends, \binom, \sqrt with an optional index; Greek letters and
5// the common symbols, relations and arrows in symbols.go; function names
6// (\sin, \lim, \operatorname{...}); large operators, which take their limits
7// above and below in display style; \left, \middle and \right; accents,
8// \overline, \underline and the braces; spacing commands; \text; the font
9// commands \mathrm, \mathbf, \mathbb, \mathcal, \mathscr, \mathfrak, \mathsf,
10// \mathtt, \mathit, \boldsymbol; and the environments matrix, pmatrix,
11// bmatrix, Bmatrix, vmatrix, Vmatrix, smallmatrix, cases, aligned, align,
12// gathered, gather, split, equation and displaymath.
13//
14// Anything else, including every command that defines macros, sets colors or
15// styles, or links, is an error; the caller shows the source instead. The
16// output uses only the elements and attributes listed in Elements and Attrs,
17// and its size is linear in the input, which is capped at MaxInput bytes and
18// MaxDepth levels of nesting.
19package texmath
20
21import (
22 "errors"
23 "fmt"
24 "html"
25 "strings"
26 "unicode"
27 "unicode/utf8"
28)
29
30// Limits on one expression.
31const (
32 MaxInput = 8 << 10
33 MaxDepth = 64
34)
35
36// Elements is every MathML element Convert emits.
37var Elements = []string{
38 "math", "mrow", "mi", "mn", "mo", "mtext", "mspace",
39 "mfrac", "msqrt", "mroot", "msub", "msup", "msubsup",
40 "munder", "mover", "munderover", "mtable", "mtr", "mtd",
41}
42
43// Attrs is every attribute Convert emits, by element, with the values it
44// can take: a fixed value, or "<length>" for an em length.
45var Attrs = map[string]map[string]string{
46 "math": {"display": "block"},
47 "mi": {"mathvariant": "normal"},
48 "mo": {"stretchy": "false"},
49 "mfrac": {"linethickness": "0"},
50 "mover": {"accent": "true"},
51 "mspace": {"width": "<length>"},
52}
53
54var (
55 ErrTooLong = errors.New("texmath: expression too long")
56 ErrTooDeep = errors.New("texmath: expression nested too deeply")
57)
58
59// Convert renders tex as one <math> element; display selects block layout
60// and display-style limits.
61func Convert(tex string, display bool) (string, error) {
62 if len(tex) > MaxInput {
63 return "", ErrTooLong
64 }
65 if !utf8.ValidString(tex) {
66 return "", errors.New("texmath: invalid UTF-8")
67 }
68 for _, r := range tex {
69 if r < 0x20 && r != '\t' && r != '\n' && r != '\r' || r == 0x7F || r == 0xFFFE || r == 0xFFFF {
70 return "", errors.New("texmath: control character")
71 }
72 }
73 p := &parser{src: tex, display: display}
74 kids, err := p.list(func(t token) bool { return false })
75 if err != nil {
76 return "", err
77 }
78 if t := p.peek(); t.kind != eof {
79 return "", p.unexpected(t)
80 }
81 root := &node{tag: "math", kids: kids}
82 if display {
83 root.attr("display", "block")
84 }
85 var b strings.Builder
86 root.write(&b)
87 return b.String(), nil
88}
89
90type node struct {
91 tag string
92 attrs [][2]string
93 text string
94 kids []*node
95 limits bool // a large operator: limits go under and over in display style
96 fn bool // a function name: a thin space follows unless a delimiter does
97}
98
99func (n *node) attr(k, v string) *node {
100 n.attrs = append(n.attrs, [2]string{k, v})
101 return n
102}
103
104func (n *node) write(b *strings.Builder) {
105 b.WriteByte('<')
106 b.WriteString(n.tag)
107 for _, a := range n.attrs {
108 b.WriteString(" " + a[0] + `="` + html.EscapeString(a[1]) + `"`)
109 }
110 b.WriteByte('>')
111 b.WriteString(html.EscapeString(n.text))
112 for _, k := range n.kids {
113 k.write(b)
114 }
115 b.WriteString("</" + n.tag + ">")
116}
117
118func el(tag string, kids ...*node) *node { return &node{tag: tag, kids: kids} }
119func leaf(tag, text string) *node { return &node{tag: tag, text: text} }
120func row(kids []*node) *node { return &node{tag: "mrow", kids: kids} }
121func space(w string) *node { return (&node{tag: "mspace"}).attr("width", w) }
122
123// fixed is an operator that must not stretch to the height of its row, the
124// way a bracket typed without \left does not in TeX.
125func fixed(s string) *node { return leaf("mo", s).attr("stretchy", "false") }
126
127type kind int
128
129const (
130 eof kind = iota
131 char // one character
132 cmd // a control sequence; val is its name without the backslash
133)
134
135type token struct {
136 kind kind
137 val string
138 pos int
139}
140
141type parser struct {
142 src string
143 pos int
144 depth int
145 display bool
146 font string
147}
148
149func (p *parser) skip() {
150 for p.pos < len(p.src) {
151 c := p.src[p.pos]
152 switch {
153 case c == ' ' || c == '\t' || c == '\n' || c == '\r':
154 p.pos++
155 case c == '%':
156 for p.pos < len(p.src) && p.src[p.pos] != '\n' {
157 p.pos++
158 }
159 default:
160 return
161 }
162 }
163}
164
165func (p *parser) peek() token {
166 save := p.pos
167 t := p.next()
168 p.pos = save
169 return t
170}
171
172func (p *parser) next() token {
173 p.skip()
174 start := p.pos
175 if p.pos >= len(p.src) {
176 return token{kind: eof, pos: start}
177 }
178 if p.src[p.pos] == '\\' {
179 p.pos++
180 if p.pos >= len(p.src) {
181 return token{kind: cmd, val: "", pos: start}
182 }
183 if isASCIILetter(p.src[p.pos]) {
184 end := p.pos
185 for end < len(p.src) && isASCIILetter(p.src[end]) {
186 end++
187 }
188 name := p.src[p.pos:end]
189 p.pos = end
190 // \operatorname* and friends: the star is part of the name.
191 if p.pos < len(p.src) && p.src[p.pos] == '*' && starred[name] {
192 p.pos++
193 name += "*"
194 }
195 return token{kind: cmd, val: name, pos: start}
196 }
197 r, n := utf8.DecodeRuneInString(p.src[p.pos:])
198 p.pos += n
199 return token{kind: cmd, val: string(r), pos: start}
200 }
201 r, n := utf8.DecodeRuneInString(p.src[p.pos:])
202 p.pos += n
203 return token{kind: char, val: string(r), pos: start}
204}
205
206var starred = map[string]bool{"operatorname": true}
207
208func isASCIILetter(c byte) bool { return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' }
209
210func (p *parser) unexpected(t token) error {
211 switch t.kind {
212 case eof:
213 return errors.New("texmath: unexpected end of input")
214 case cmd:
215 return fmt.Errorf(`texmath: unexpected \%s at %d`, t.val, t.pos)
216 }
217 return fmt.Errorf("texmath: unexpected %q at %d", t.val, t.pos)
218}
219
220func (p *parser) expect(kind kind, val string) error {
221 if t := p.next(); t.kind != kind || t.val != val {
222 return p.unexpected(t)
223 }
224 return nil
225}
226
227func isChar(t token, s string) bool { return t.kind == char && t.val == s }
228func isCmd(t token, s string) bool { return t.kind == cmd && t.val == s }
229
230// list parses atoms until the input ends or stop matches the next token,
231// which is left unread.
232func (p *parser) list(stop func(token) bool) ([]*node, error) {
233 var out []*node
234 for {
235 t := p.peek()
236 if t.kind == eof || stop(t) {
237 return out, nil
238 }
239 n, err := p.scripted()
240 if err != nil {
241 return nil, err
242 }
243 if n == nil {
244 continue
245 }
246 out = append(out, n)
247 if n.fn && !p.delimiterNext() {
248 out = append(out, space("0.1667em"))
249 }
250 }
251}
252
253// delimiterNext reports whether the next token closes a group or opens a
254// bracket, where TeX puts no space after a function name.
255func (p *parser) delimiterNext() bool {
256 t := p.peek()
257 if t.kind == eof {
258 return true
259 }
260 if t.kind == char {
261 return strings.Contains("()[]{}|&.,;", t.val)
262 }
263 switch t.val {
264 case "left", "right", "\\", "end", ",", ";", "!", "quad", "qquad", "{", "}":
265 return true
266 }
267 return false
268}
269
270// scripted parses one atom and any sub- and superscripts attached to it.
271func (p *parser) scripted() (*node, error) {
272 var base *node
273 if t := p.peek(); !isChar(t, "^") && !isChar(t, "_") {
274 var err error
275 if base, err = p.atom(); err != nil {
276 return nil, err
277 }
278 }
279 var sub, sup *node
280 limits := base != nil && base.limits && p.display
281 for {
282 t := p.peek()
283 switch {
284 case isCmd(t, "limits"):
285 p.next()
286 limits = base != nil && base.limits
287 continue
288 case isCmd(t, "nolimits"):
289 p.next()
290 limits = false
291 continue
292 case isChar(t, "^"), isChar(t, "_"):
293 default:
294 if sub == nil && sup == nil {
295 return base, nil
296 }
297 if base == nil {
298 base = row(nil)
299 }
300 return script(base, sub, sup, limits), nil
301 }
302 p.next()
303 arg, err := p.arg()
304 if err != nil {
305 return nil, err
306 }
307 if t.val == "^" {
308 if sup != nil {
309 return nil, fmt.Errorf("texmath: double superscript at %d", t.pos)
310 }
311 sup = arg
312 } else {
313 if sub != nil {
314 return nil, fmt.Errorf("texmath: double subscript at %d", t.pos)
315 }
316 sub = arg
317 }
318 }
319}
320
321func script(base, sub, sup *node, limits bool) *node {
322 fn := base.fn
323 var n *node
324 switch {
325 case limits && sub != nil && sup != nil:
326 n = el("munderover", base, sub, sup)
327 case limits && sub != nil:
328 n = el("munder", base, sub)
329 case limits:
330 n = el("mover", base, sup)
331 case sub != nil && sup != nil:
332 n = el("msubsup", base, sub, sup)
333 case sub != nil:
334 n = el("msub", base, sub)
335 default:
336 n = el("msup", base, sup)
337 }
338 n.fn = fn
339 return n
340}
341
342// arg parses a command's argument: a braced group, or else one token.
343func (p *parser) arg() (*node, error) {
344 t := p.peek()
345 switch {
346 case t.kind == eof:
347 return nil, p.unexpected(t)
348 case t.kind == char && strings.Contains("}&^_", t.val):
349 return nil, p.unexpected(t)
350 case t.kind == char && t.val >= "0" && t.val <= "9":
351 p.next()
352 return leaf("mn", p.styled(t.val)), nil
353 }
354 n, err := p.atom()
355 if err == nil && n == nil {
356 // \displaystyle and the like render nothing, so cannot be an argument.
357 return nil, fmt.Errorf(`texmath: \%s cannot be an argument at %d`, t.val, t.pos)
358 }
359 return n, err
360}
361
362func (p *parser) enter() error {
363 p.depth++
364 if p.depth > MaxDepth {
365 return ErrTooDeep
366 }
367 return nil
368}
369
370// atom parses one atom. A nil node with a nil error is a command that
371// renders nothing, such as \displaystyle.
372func (p *parser) atom() (*node, error) {
373 if err := p.enter(); err != nil {
374 return nil, err
375 }
376 defer func() { p.depth-- }()
377 t := p.next()
378 switch t.kind {
379 case eof:
380 return nil, p.unexpected(t)
381 case char:
382 return p.charAtom(t)
383 }
384 return p.command(t)
385}
386
387func (p *parser) charAtom(t token) (*node, error) {
388 r, _ := utf8.DecodeRuneInString(t.val)
389 switch {
390 case t.val == "{":
391 font := p.font
392 kids, err := p.list(func(t token) bool { return isChar(t, "}") })
393 p.font = font
394 if err != nil {
395 return nil, err
396 }
397 if err := p.expect(char, "}"); err != nil {
398 return nil, err
399 }
400 return row(kids), nil
401 case r >= '0' && r <= '9':
402 num := t.val
403 for p.pos < len(p.src) {
404 c := p.src[p.pos]
405 if c >= '0' && c <= '9' || c == '.' && p.pos+1 < len(p.src) && p.src[p.pos+1] >= '0' && p.src[p.pos+1] <= '9' {
406 num += string(c)
407 p.pos++
408 continue
409 }
410 break
411 }
412 return leaf("mn", p.styled(num)), nil
413 case unicode.IsLetter(r):
414 n := leaf("mi", p.styled(t.val))
415 if p.font == "rm" {
416 n.attr("mathvariant", "normal")
417 }
418 return n, nil
419 }
420 switch t.val {
421 case "}", "&", "$", "#", "\\":
422 return nil, p.unexpected(t)
423 case "(", ")", "[", "]", "|", "/":
424 return fixed(t.val), nil
425 case "-":
426 return leaf("mo", "−"), nil
427 case "*":
428 return leaf("mo", "∗"), nil
429 case "'":
430 return leaf("mo", "′"), nil
431 case "~":
432 return space("0.3333em"), nil
433 }
434 if r < 0x20 || r == utf8.RuneError {
435 return nil, p.unexpected(t)
436 }
437 return leaf("mo", t.val), nil
438}
439
440func (p *parser) command(t token) (*node, error) {
441 name := t.val
442 if s, ok := symbols[name]; ok {
443 n := leaf(s.tag, s.text)
444 if s.upright {
445 n.attr("mathvariant", "normal")
446 }
447 if s.fixed {
448 n.attr("stretchy", "false")
449 }
450 n.limits = s.limits
451 return n, nil
452 }
453 if w, ok := spaces[name]; ok {
454 return space(w), nil
455 }
456 if f, ok := functions[name]; ok {
457 n := leaf("mi", name)
458 n.limits, n.fn = f, true
459 return n, nil
460 }
461 if a, ok := accents[name]; ok {
462 arg, err := p.arg()
463 if err != nil {
464 return nil, err
465 }
466 if a.under {
467 return el("munder", arg, leaf("mo", a.mark)), nil
468 }
469 n := el("mover", arg, leaf("mo", a.mark))
470 if a.accent {
471 n.attr("accent", "true")
472 }
473 return n, nil
474 }
475 if f, ok := fonts[name]; ok {
476 font := p.font
477 p.font = f
478 arg, err := p.arg()
479 p.font = font
480 return arg, err
481 }
482 switch name {
483 case "frac", "dfrac", "tfrac", "cfrac":
484 num, err := p.arg()
485 if err != nil {
486 return nil, err
487 }
488 den, err := p.arg()
489 if err != nil {
490 return nil, err
491 }
492 return el("mfrac", num, den), nil
493 case "binom", "dbinom", "tbinom":
494 top, err := p.arg()
495 if err != nil {
496 return nil, err
497 }
498 bottom, err := p.arg()
499 if err != nil {
500 return nil, err
501 }
502 frac := el("mfrac", top, bottom).attr("linethickness", "0")
503 return row([]*node{leaf("mo", "("), frac, leaf("mo", ")")}), nil
504 case "sqrt":
505 var index *node
506 if isChar(p.peek(), "[") {
507 p.next()
508 kids, err := p.list(func(t token) bool { return isChar(t, "]") })
509 if err != nil {
510 return nil, err
511 }
512 if err := p.expect(char, "]"); err != nil {
513 return nil, err
514 }
515 index = row(kids)
516 }
517 arg, err := p.arg()
518 if err != nil {
519 return nil, err
520 }
521 if index != nil {
522 return el("mroot", arg, index), nil
523 }
524 return el("msqrt", arg), nil
525 case "left":
526 open, err := p.delimiter()
527 if err != nil {
528 return nil, err
529 }
530 kids, err := p.list(func(t token) bool { return isCmd(t, "right") })
531 if err != nil {
532 return nil, err
533 }
534 if err := p.expect(cmd, "right"); err != nil {
535 return nil, err
536 }
537 cls, err := p.delimiter()
538 if err != nil {
539 return nil, err
540 }
541 var out []*node
542 if open != "" {
543 out = append(out, leaf("mo", open))
544 }
545 out = append(out, kids...)
546 if cls != "" {
547 out = append(out, leaf("mo", cls))
548 }
549 return row(out), nil
550 case "middle":
551 d, err := p.delimiter()
552 if err != nil {
553 return nil, err
554 }
555 return leaf("mo", d), nil
556 case "text", "textrm", "textnormal", "mbox":
557 s, err := p.rawGroup()
558 if err != nil {
559 return nil, err
560 }
561 return leaf("mtext", s), nil
562 case "operatorname", "operatorname*":
563 s, err := p.rawGroup()
564 if err != nil {
565 return nil, err
566 }
567 n := leaf("mi", s)
568 if utf8.RuneCountInString(s) == 1 {
569 n.attr("mathvariant", "normal")
570 }
571 n.limits, n.fn = name == "operatorname*", true
572 return n, nil
573 case "begin":
574 return p.environment()
575 case "displaystyle", "textstyle", "scriptstyle", "scriptscriptstyle", "limits", "nolimits":
576 return nil, nil
577 }
578 return nil, p.unexpected(t)
579}
580
581// rawGroup reads a braced argument as text, for \text and \operatorname.
582// Nested braces must balance; \{, \}, \$, \%, \&, \#, \_ and \\ stand for
583// the character.
584func (p *parser) rawGroup() (string, error) {
585 if err := p.expect(char, "{"); err != nil {
586 return "", err
587 }
588 var b strings.Builder
589 depth := 0
590 for p.pos < len(p.src) {
591 c := p.src[p.pos]
592 switch {
593 case c == '\\' && p.pos+1 < len(p.src) && strings.IndexByte(`{}$%&#_\`, p.src[p.pos+1]) >= 0:
594 b.WriteByte(p.src[p.pos+1])
595 p.pos += 2
596 continue
597 case c == '{':
598 depth++
599 case c == '}':
600 if depth == 0 {
601 p.pos++
602 return b.String(), nil
603 }
604 depth--
605 }
606 b.WriteByte(c)
607 p.pos++
608 }
609 return "", errors.New("texmath: unterminated group")
610}
611
612// delimiter reads what follows \left, \middle or \right; "." is none.
613func (p *parser) delimiter() (string, error) {
614 t := p.next()
615 if t.kind == char {
616 switch t.val {
617 case ".":
618 return "", nil
619 case "<":
620 return "⟨", nil
621 case ">":
622 return "⟩", nil
623 case "(", ")", "[", "]", "|", "/":
624 return t.val, nil
625 }
626 }
627 if t.kind == cmd {
628 if d, ok := delimiters[t.val]; ok {
629 return d, nil
630 }
631 }
632 return "", p.unexpected(t)
633}
634
635type env struct {
636 open, close string
637 table bool
638}
639
640var environments = map[string]env{
641 "matrix": {table: true},
642 "smallmatrix": {table: true},
643 "pmatrix": {"(", ")", true},
644 "bmatrix": {"[", "]", true},
645 "Bmatrix": {"{", "}", true},
646 "vmatrix": {"|", "|", true},
647 "Vmatrix": {"‖", "‖", true},
648 "cases": {"{", "", true},
649 "aligned": {table: true},
650 "align": {table: true},
651 "align*": {table: true},
652 "gathered": {table: true},
653 "gather": {table: true},
654 "gather*": {table: true},
655 "split": {table: true},
656 "equation": {},
657 "equation*": {},
658 "displaymath": {},
659}
660
661func (p *parser) envName() (string, error) {
662 if err := p.expect(char, "{"); err != nil {
663 return "", err
664 }
665 end := strings.IndexByte(p.src[p.pos:], '}')
666 if end < 0 {
667 return "", errors.New("texmath: unterminated environment name")
668 }
669 name := p.src[p.pos : p.pos+end]
670 p.pos += end + 1
671 return name, nil
672}
673
674func (p *parser) environment() (*node, error) {
675 name, err := p.envName()
676 if err != nil {
677 return nil, err
678 }
679 e, ok := environments[name]
680 if !ok {
681 return nil, fmt.Errorf("texmath: unsupported environment %q", name)
682 }
683 var body *node
684 if e.table {
685 body, err = p.table()
686 } else {
687 var kids []*node
688 kids, err = p.list(func(t token) bool { return isCmd(t, "end") })
689 body = row(kids)
690 }
691 if err != nil {
692 return nil, err
693 }
694 if err := p.expect(cmd, "end"); err != nil {
695 return nil, err
696 }
697 if end, err := p.envName(); err != nil {
698 return nil, err
699 } else if end != name {
700 return nil, fmt.Errorf(`texmath: \begin{%s} ended by \end{%s}`, name, end)
701 }
702 if e.open == "" && e.close == "" {
703 return body, nil
704 }
705 out := []*node{}
706 if e.open != "" {
707 out = append(out, leaf("mo", e.open))
708 }
709 out = append(out, body)
710 if e.close != "" {
711 out = append(out, leaf("mo", e.close))
712 }
713 return row(out), nil
714}
715
716// table parses rows separated by \\ and cells separated by &, up to \end.
717func (p *parser) table() (*node, error) {
718 stop := func(t token) bool { return isChar(t, "&") || isCmd(t, "\\") || isCmd(t, "end") }
719 tbl := el("mtable")
720 cur := el("mtr")
721 for {
722 kids, err := p.list(stop)
723 if err != nil {
724 return nil, err
725 }
726 cur.kids = append(cur.kids, el("mtd", kids...))
727 t := p.peek()
728 switch {
729 case isChar(t, "&"):
730 p.next()
731 case isCmd(t, "\\"):
732 p.next()
733 tbl.kids = append(tbl.kids, cur)
734 cur = el("mtr")
735 case isCmd(t, "end"):
736 // A trailing \\ leaves one empty cell; it is not a row.
737 if len(cur.kids) > 1 || len(cur.kids[0].kids) > 0 {
738 tbl.kids = append(tbl.kids, cur)
739 }
740 return tbl, nil
741 default:
742 return nil, p.unexpected(t)
743 }
744 }
745}
746
747// styled maps letters and digits into the current font's Mathematical
748// Alphanumeric Symbols, which is how MathML Core spells \mathbb and the rest:
749// mathvariant is honoured only as "normal".
750func (p *parser) styled(s string) string {
751 if p.font == "" || p.font == "rm" {
752 return s
753 }
754 var b strings.Builder
755 for _, r := range s {
756 b.WriteRune(alphanumeric(p.font, r))
757 }
758 return b.String()
759}