| 1 | #!/usr/bin/env python3 |
| 2 | """ |
| 3 | PPT Master - Native Formula Abstract Syntax Tree |
| 4 | |
| 5 | Define the internal math nodes shared by the Microsoft 365 LaTeX parser, |
| 6 | chemistry parser, and OMML emitter. |
| 7 | |
| 8 | See references/native-formula.md for the owning authoring contract. |
| 9 | |
| 10 | Usage: |
| 11 | Imported by native formula compiler modules. |
| 12 | |
| 13 | Examples: |
| 14 | expression = Sequence((Text("x"),)) |
| 15 | |
| 16 | Dependencies: |
| 17 | None (only uses standard library) |
| 18 | """ |
| 19 | |
| 20 | from __future__ import annotations |
| 21 | |
| 22 | from dataclasses import dataclass |
| 23 | |
| 24 | |
| 25 | @dataclass(frozen=True) |
| 26 | class RunStyle: |
| 27 | style: str | None = None |
| 28 | normal: bool | None = None |
| 29 | script: str | None = None |
| 30 | color: str | None = None |
| 31 | bold: bool | None = None |
| 32 | italic: bool | None = None |
| 33 | typeface: str | None = None |
| 34 | is_default: bool = False |
| 35 | |
| 36 | |
| 37 | @dataclass(frozen=True) |
| 38 | class Text: |
| 39 | value: str |
| 40 | style: RunStyle | None = None |
| 41 | literal: bool = False |
| 42 | |
| 43 | |
| 44 | @dataclass(frozen=True) |
| 45 | class Sequence: |
| 46 | children: tuple[Node, ...] |
| 47 | |
| 48 | |
| 49 | @dataclass(frozen=True) |
| 50 | class Styled: |
| 51 | body: Sequence |
| 52 | style: RunStyle |
| 53 | |
| 54 | |
| 55 | @dataclass(frozen=True) |
| 56 | class Fraction: |
| 57 | numerator: Sequence |
| 58 | denominator: Sequence |
| 59 | kind: str = "bar" |
| 60 | |
| 61 | |
| 62 | @dataclass(frozen=True) |
| 63 | class Radical: |
| 64 | body: Sequence |
| 65 | degree: Sequence | None = None |
| 66 | |
| 67 | |
| 68 | @dataclass(frozen=True) |
| 69 | class Script: |
| 70 | base: Node |
| 71 | subscript: Sequence | None = None |
| 72 | superscript: Sequence | None = None |
| 73 | |
| 74 | |
| 75 | @dataclass(frozen=True) |
| 76 | class Prescript: |
| 77 | base: Node |
| 78 | subscript: Sequence | None = None |
| 79 | superscript: Sequence | None = None |
| 80 | |
| 81 | |
| 82 | @dataclass(frozen=True) |
| 83 | class Nary: |
| 84 | symbol: str |
| 85 | category: str |
| 86 | subscript: Sequence | None = None |
| 87 | superscript: Sequence | None = None |
| 88 | body: Sequence | None = None |
| 89 | limit_modifier: str | None = None |
| 90 | |
| 91 | |
| 92 | @dataclass(frozen=True) |
| 93 | class Delimiter: |
| 94 | left: str |
| 95 | right: str |
| 96 | segments: tuple[Sequence, ...] |
| 97 | separator: str = "" |
| 98 | |
| 99 | |
| 100 | @dataclass(frozen=True) |
| 101 | class Matrix: |
| 102 | environment: str |
| 103 | rows: tuple[tuple[Sequence, ...], ...] |
| 104 | column_alignments: tuple[str, ...] = () |
| 105 | |
| 106 | |
| 107 | @dataclass(frozen=True) |
| 108 | class AlignmentPoint: |
| 109 | pass |
| 110 | |
| 111 | |
| 112 | @dataclass(frozen=True) |
| 113 | class EquationArray: |
| 114 | rows: tuple[Sequence, ...] |
| 115 | |
| 116 | |
| 117 | @dataclass(frozen=True) |
| 118 | class Accent: |
| 119 | character: str |
| 120 | body: Sequence |
| 121 | |
| 122 | |
| 123 | @dataclass(frozen=True) |
| 124 | class Bar: |
| 125 | position: str |
| 126 | body: Sequence |
| 127 | |
| 128 | |
| 129 | @dataclass(frozen=True) |
| 130 | class GroupChar: |
| 131 | character: str |
| 132 | position: str |
| 133 | vertical_justification: str |
| 134 | body: Sequence |
| 135 | |
| 136 | |
| 137 | @dataclass(frozen=True) |
| 138 | class Limit: |
| 139 | base: Node |
| 140 | lower: Sequence | None = None |
| 141 | upper: Sequence | None = None |
| 142 | |
| 143 | |
| 144 | @dataclass(frozen=True) |
| 145 | class Function: |
| 146 | name: Sequence |
| 147 | body: Sequence | None = None |
| 148 | subscript: Sequence | None = None |
| 149 | superscript: Sequence | None = None |
| 150 | limit_style: bool = False |
| 151 | limit_modifier: str | None = None |
| 152 | |
| 153 | |
| 154 | @dataclass(frozen=True) |
| 155 | class OperatorEmulator: |
| 156 | body: Sequence |
| 157 | |
| 158 | |
| 159 | @dataclass(frozen=True) |
| 160 | class Phantom: |
| 161 | body: Sequence |
| 162 | kind: str |
| 163 | |
| 164 | |
| 165 | @dataclass(frozen=True) |
| 166 | class BorderBox: |
| 167 | body: Sequence |
| 168 | kind: str |
| 169 | |
| 170 | |
| 171 | @dataclass(frozen=True) |
| 172 | class FormulaVerticalExtent: |
| 173 | """Conservative formula bounds relative to the surrounding baseline.""" |
| 174 | |
| 175 | ascent_em: float |
| 176 | descent_em: float |
| 177 | |
| 178 | @property |
| 179 | def height_em(self) -> float: |
| 180 | """Return total vertical extent in units of the owning font size.""" |
| 181 | return self.ascent_em + self.descent_em |
| 182 | |
| 183 | |
| 184 | Node = ( |
| 185 | Text |
| 186 | | Sequence |
| 187 | | Styled |
| 188 | | Fraction |
| 189 | | Radical |
| 190 | | Script |
| 191 | | Prescript |
| 192 | | Nary |
| 193 | | Delimiter |
| 194 | | Matrix |
| 195 | | AlignmentPoint |
| 196 | | EquationArray |
| 197 | | Accent |
| 198 | | Bar |
| 199 | | GroupChar |
| 200 | | Limit |
| 201 | | Function |
| 202 | | OperatorEmulator |
| 203 | | Phantom |
| 204 | | BorderBox |
| 205 | ) |
| 206 | |
| 207 | |
| 208 | _BASE_VERTICAL_EXTENT = FormulaVerticalExtent(0.85, 0.35) |
| 209 | # These ratios model Office Math topology rather than any one installed font. |
| 210 | # The ordinary-text floor matches the exporter/checker baseline contract. |
| 211 | _SCRIPT_SCALE = 0.62 |
| 212 | _FRACTION_SCALE = 0.68 |
| 213 | |
| 214 | |
| 215 | def _max_vertical_extent( |
| 216 | *extents: FormulaVerticalExtent, |
| 217 | ) -> FormulaVerticalExtent: |
| 218 | if not extents: |
| 219 | return FormulaVerticalExtent(0.0, 0.0) |
| 220 | return FormulaVerticalExtent( |
| 221 | max(extent.ascent_em for extent in extents), |
| 222 | max(extent.descent_em for extent in extents), |
| 223 | ) |
| 224 | |
| 225 | |
| 226 | def _scaled_vertical_extent( |
| 227 | extent: FormulaVerticalExtent, |
| 228 | scale: float, |
| 229 | ) -> FormulaVerticalExtent: |
| 230 | return FormulaVerticalExtent( |
| 231 | extent.ascent_em * scale, |
| 232 | extent.descent_em * scale, |
| 233 | ) |
| 234 | |
| 235 | |
| 236 | def _script_vertical_extent( |
| 237 | base: FormulaVerticalExtent, |
| 238 | subscript: Sequence | None, |
| 239 | superscript: Sequence | None, |
| 240 | ) -> FormulaVerticalExtent: |
| 241 | ascent = base.ascent_em |
| 242 | descent = base.descent_em |
| 243 | if superscript is not None: |
| 244 | upper = _scaled_vertical_extent( |
| 245 | _node_vertical_extent(superscript), |
| 246 | _SCRIPT_SCALE, |
| 247 | ) |
| 248 | baseline_shift = 0.55 |
| 249 | ascent = max(ascent, baseline_shift + upper.ascent_em) |
| 250 | descent = max(descent, upper.descent_em - baseline_shift) |
| 251 | if subscript is not None: |
| 252 | lower = _scaled_vertical_extent( |
| 253 | _node_vertical_extent(subscript), |
| 254 | _SCRIPT_SCALE, |
| 255 | ) |
| 256 | baseline_shift = 0.30 |
| 257 | ascent = max(ascent, lower.ascent_em - baseline_shift) |
| 258 | descent = max(descent, baseline_shift + lower.descent_em) |
| 259 | return FormulaVerticalExtent(ascent, descent) |
| 260 | |
| 261 | |
| 262 | def _limit_vertical_extent( |
| 263 | base: FormulaVerticalExtent, |
| 264 | lower: Sequence | None, |
| 265 | upper: Sequence | None, |
| 266 | ) -> FormulaVerticalExtent: |
| 267 | ascent = base.ascent_em |
| 268 | descent = base.descent_em |
| 269 | if upper is not None: |
| 270 | upper_extent = _node_vertical_extent(upper) |
| 271 | ascent += 0.14 + _SCRIPT_SCALE * upper_extent.height_em |
| 272 | if lower is not None: |
| 273 | lower_extent = _node_vertical_extent(lower) |
| 274 | descent += 0.14 + _SCRIPT_SCALE * lower_extent.height_em |
| 275 | return FormulaVerticalExtent(ascent, descent) |
| 276 | |
| 277 | |
| 278 | def _rows_vertical_extent( |
| 279 | rows: tuple[tuple[Sequence, ...], ...] | tuple[Sequence, ...], |
| 280 | ) -> FormulaVerticalExtent: |
| 281 | row_heights: list[float] = [] |
| 282 | for row in rows: |
| 283 | cells = row if isinstance(row, tuple) else (row,) |
| 284 | row_extent = _max_vertical_extent( |
| 285 | *(_node_vertical_extent(cell) for cell in cells) |
| 286 | ) |
| 287 | row_heights.append( |
| 288 | max(_BASE_VERTICAL_EXTENT.height_em, row_extent.height_em) |
| 289 | ) |
| 290 | if not row_heights: |
| 291 | return _BASE_VERTICAL_EXTENT |
| 292 | total_height = sum(row_heights) + 0.18 * (len(row_heights) - 1) |
| 293 | return FormulaVerticalExtent( |
| 294 | max(_BASE_VERTICAL_EXTENT.ascent_em, total_height * 0.55), |
| 295 | max(_BASE_VERTICAL_EXTENT.descent_em, total_height * 0.45), |
| 296 | ) |
| 297 | |
| 298 | |
| 299 | def _node_vertical_extent(node: Node) -> FormulaVerticalExtent: |
| 300 | if isinstance(node, Text): |
| 301 | return _BASE_VERTICAL_EXTENT |
| 302 | if isinstance(node, AlignmentPoint): |
| 303 | return FormulaVerticalExtent(0.0, 0.0) |
| 304 | if isinstance(node, Sequence): |
| 305 | return _max_vertical_extent( |
| 306 | *(_node_vertical_extent(child) for child in node.children) |
| 307 | ) |
| 308 | if isinstance(node, Styled): |
| 309 | return _node_vertical_extent(node.body) |
| 310 | if isinstance(node, Fraction): |
| 311 | numerator = _node_vertical_extent(node.numerator) |
| 312 | denominator = _node_vertical_extent(node.denominator) |
| 313 | return FormulaVerticalExtent( |
| 314 | max( |
| 315 | _BASE_VERTICAL_EXTENT.ascent_em, |
| 316 | 0.28 + _FRACTION_SCALE * numerator.height_em, |
| 317 | ), |
| 318 | max( |
| 319 | _BASE_VERTICAL_EXTENT.descent_em, |
| 320 | 0.06 + _FRACTION_SCALE * denominator.height_em, |
| 321 | ), |
| 322 | ) |
| 323 | if isinstance(node, Radical): |
| 324 | body = _node_vertical_extent(node.body) |
| 325 | ascent = body.ascent_em + 0.20 |
| 326 | if node.degree is not None: |
| 327 | degree = _scaled_vertical_extent( |
| 328 | _node_vertical_extent(node.degree), |
| 329 | 0.50, |
| 330 | ) |
| 331 | ascent = max(ascent, 0.55 + degree.ascent_em) |
| 332 | return FormulaVerticalExtent(ascent, max(body.descent_em, 0.40)) |
| 333 | if isinstance(node, (Script, Prescript)): |
| 334 | return _script_vertical_extent( |
| 335 | _node_vertical_extent(node.base), |
| 336 | node.subscript, |
| 337 | node.superscript, |
| 338 | ) |
| 339 | if isinstance(node, Nary): |
| 340 | base = _max_vertical_extent( |
| 341 | FormulaVerticalExtent(1.05, 0.45), |
| 342 | _node_vertical_extent(node.body) |
| 343 | if node.body is not None else FormulaVerticalExtent(0.0, 0.0), |
| 344 | ) |
| 345 | if node.limit_modifier == "limits": |
| 346 | return _limit_vertical_extent( |
| 347 | base, |
| 348 | node.subscript, |
| 349 | node.superscript, |
| 350 | ) |
| 351 | return _script_vertical_extent( |
| 352 | base, |
| 353 | node.subscript, |
| 354 | node.superscript, |
| 355 | ) |
| 356 | if isinstance(node, Delimiter): |
| 357 | body = _max_vertical_extent( |
| 358 | *(_node_vertical_extent(segment) for segment in node.segments) |
| 359 | ) |
| 360 | return FormulaVerticalExtent( |
| 361 | max(_BASE_VERTICAL_EXTENT.ascent_em, body.ascent_em + 0.05), |
| 362 | max(_BASE_VERTICAL_EXTENT.descent_em, body.descent_em + 0.05), |
| 363 | ) |
| 364 | if isinstance(node, Matrix): |
| 365 | return _rows_vertical_extent(node.rows) |
| 366 | if isinstance(node, EquationArray): |
| 367 | return _rows_vertical_extent(node.rows) |
| 368 | if isinstance(node, Accent): |
| 369 | body = _node_vertical_extent(node.body) |
| 370 | return FormulaVerticalExtent(body.ascent_em + 0.24, body.descent_em) |
| 371 | if isinstance(node, Bar): |
| 372 | body = _node_vertical_extent(node.body) |
| 373 | if node.position in {"bot", "bottom"}: |
| 374 | return FormulaVerticalExtent(body.ascent_em, body.descent_em + 0.16) |
| 375 | return FormulaVerticalExtent(body.ascent_em + 0.16, body.descent_em) |
| 376 | if isinstance(node, GroupChar): |
| 377 | body = _node_vertical_extent(node.body) |
| 378 | if node.position in {"bot", "bottom"}: |
| 379 | return FormulaVerticalExtent(body.ascent_em, body.descent_em + 0.30) |
| 380 | return FormulaVerticalExtent(body.ascent_em + 0.30, body.descent_em) |
| 381 | if isinstance(node, Limit): |
| 382 | return _limit_vertical_extent( |
| 383 | _node_vertical_extent(node.base), |
| 384 | node.lower, |
| 385 | node.upper, |
| 386 | ) |
| 387 | if isinstance(node, Function): |
| 388 | name = _node_vertical_extent(node.name) |
| 389 | if node.subscript is not None or node.superscript is not None: |
| 390 | if node.limit_modifier == "limits": |
| 391 | name = _limit_vertical_extent( |
| 392 | name, |
| 393 | node.subscript, |
| 394 | node.superscript, |
| 395 | ) |
| 396 | else: |
| 397 | name = _script_vertical_extent( |
| 398 | name, |
| 399 | node.subscript, |
| 400 | node.superscript, |
| 401 | ) |
| 402 | if node.body is None: |
| 403 | return name |
| 404 | return _max_vertical_extent(name, _node_vertical_extent(node.body)) |
| 405 | if isinstance(node, OperatorEmulator): |
| 406 | return _node_vertical_extent(node.body) |
| 407 | if isinstance(node, Phantom): |
| 408 | if node.kind == "hphantom": |
| 409 | return FormulaVerticalExtent(0.0, 0.0) |
| 410 | return _node_vertical_extent(node.body) |
| 411 | if isinstance(node, BorderBox): |
| 412 | body = _node_vertical_extent(node.body) |
| 413 | return FormulaVerticalExtent( |
| 414 | body.ascent_em + 0.08, |
| 415 | body.descent_em + 0.08, |
| 416 | ) |
| 417 | return _BASE_VERTICAL_EXTENT |
| 418 | |
| 419 | |
| 420 | def formula_vertical_extent(root: Node) -> FormulaVerticalExtent: |
| 421 | """Estimate native math ascent/descent from the parsed formula structure.""" |
| 422 | extent = _node_vertical_extent(root) |
| 423 | return FormulaVerticalExtent( |
| 424 | max(_BASE_VERTICAL_EXTENT.ascent_em, extent.ascent_em), |
| 425 | max(_BASE_VERTICAL_EXTENT.descent_em, extent.descent_em), |
| 426 | ) |
| 427 | |
| 428 | |
| 429 | def merge_run_styles(base: RunStyle | None, override: RunStyle | None) -> RunStyle | None: |
| 430 | """Merge inherited and local run style without clearing unrelated fields.""" |
| 431 | if base is None: |
| 432 | return override |
| 433 | if override is None: |
| 434 | return base |
| 435 | if override.is_default: |
| 436 | return RunStyle( |
| 437 | style=base.style if base.style is not None else override.style, |
| 438 | normal=base.normal if base.normal is not None else override.normal, |
| 439 | script=base.script if base.script is not None else override.script, |
| 440 | color=base.color if base.color is not None else override.color, |
| 441 | bold=base.bold if base.bold is not None else override.bold, |
| 442 | italic=base.italic if base.italic is not None else override.italic, |
| 443 | typeface=( |
| 444 | base.typeface |
| 445 | if base.typeface is not None |
| 446 | else override.typeface |
| 447 | ), |
| 448 | is_default=base.is_default, |
| 449 | ) |
| 450 | return RunStyle( |
| 451 | style=override.style if override.style is not None else base.style, |
| 452 | normal=override.normal if override.normal is not None else base.normal, |
| 453 | script=override.script if override.script is not None else base.script, |
| 454 | color=override.color if override.color is not None else base.color, |
| 455 | bold=override.bold if override.bold is not None else base.bold, |
| 456 | italic=override.italic if override.italic is not None else base.italic, |
| 457 | typeface=( |
| 458 | override.typeface |
| 459 | if override.typeface is not None |
| 460 | else base.typeface |
| 461 | ), |
| 462 | is_default=override.is_default, |
| 463 | ) |
| 464 | |
| 465 | |
| 466 | def append_child(children: list[Node], node: Node) -> None: |
| 467 | """Append one node while coalescing adjacent text with equal style.""" |
| 468 | if isinstance(node, Sequence) and not node.children: |
| 469 | return |
| 470 | if ( |
| 471 | isinstance(node, Text) |
| 472 | and children |
| 473 | and isinstance(children[-1], Text) |
| 474 | and children[-1].style == node.style |
| 475 | and children[-1].literal == node.literal |
| 476 | ): |
| 477 | previous = children[-1] |
| 478 | children[-1] = Text( |
| 479 | previous.value + node.value, |
| 480 | node.style, |
| 481 | literal=node.literal, |
| 482 | ) |
| 483 | return |
| 484 | children.append(node) |
| 485 | |
| 486 | |
| 487 | def is_empty(node: Node) -> bool: |
| 488 | """Return whether a node contains no visible or structural content.""" |
| 489 | if isinstance(node, Text): |
| 490 | return not node.value |
| 491 | if isinstance(node, Sequence): |
| 492 | return not node.children or all(is_empty(child) for child in node.children) |
| 493 | if isinstance(node, Styled): |
| 494 | return is_empty(node.body) |
| 495 | return False |
| 496 | |
| 497 | |
| 498 | def formula_node_count(root: Node, *, maximum: int) -> int: |
| 499 | """Return iterative AST size and reject formulas above the supplied limit.""" |
| 500 | pending: list[Node] = [root] |
| 501 | count = 0 |
| 502 | while pending: |
| 503 | node = pending.pop() |
| 504 | count += 1 |
| 505 | if count > maximum: |
| 506 | raise ValueError(f"Formula exceeds the {maximum}-node complexity limit") |
| 507 | if isinstance(node, Sequence): |
| 508 | pending.extend(reversed(node.children)) |
| 509 | elif isinstance(node, Styled): |
| 510 | pending.append(node.body) |
| 511 | elif isinstance(node, Fraction): |
| 512 | pending.extend((node.denominator, node.numerator)) |
| 513 | elif isinstance(node, Radical): |
| 514 | pending.append(node.body) |
| 515 | if node.degree is not None: |
| 516 | pending.append(node.degree) |
| 517 | elif isinstance(node, (Script, Prescript)): |
| 518 | pending.append(node.base) |
| 519 | if node.subscript is not None: |
| 520 | pending.append(node.subscript) |
| 521 | if node.superscript is not None: |
| 522 | pending.append(node.superscript) |
| 523 | elif isinstance(node, Nary): |
| 524 | if node.subscript is not None: |
| 525 | pending.append(node.subscript) |
| 526 | if node.superscript is not None: |
| 527 | pending.append(node.superscript) |
| 528 | if node.body is not None: |
| 529 | pending.append(node.body) |
| 530 | elif isinstance(node, Delimiter): |
| 531 | pending.extend(reversed(node.segments)) |
| 532 | elif isinstance(node, Matrix): |
| 533 | for row in reversed(node.rows): |
| 534 | pending.extend(reversed(row)) |
| 535 | elif isinstance(node, EquationArray): |
| 536 | pending.extend(reversed(node.rows)) |
| 537 | elif isinstance(node, ( |
| 538 | Accent, |
| 539 | Bar, |
| 540 | GroupChar, |
| 541 | OperatorEmulator, |
| 542 | Phantom, |
| 543 | BorderBox, |
| 544 | )): |
| 545 | pending.append(node.body) |
| 546 | elif isinstance(node, Limit): |
| 547 | pending.append(node.base) |
| 548 | if node.lower is not None: |
| 549 | pending.append(node.lower) |
| 550 | if node.upper is not None: |
| 551 | pending.append(node.upper) |
| 552 | elif isinstance(node, Function): |
| 553 | pending.append(node.name) |
| 554 | if node.body is not None: |
| 555 | pending.append(node.body) |
| 556 | if node.subscript is not None: |
| 557 | pending.append(node.subscript) |
| 558 | if node.superscript is not None: |
| 559 | pending.append(node.superscript) |
| 560 | return count |
| 561 | |
| 562 | |
| 563 | __all__ = [ |
| 564 | "Accent", |
| 565 | "AlignmentPoint", |
| 566 | "Bar", |
| 567 | "BorderBox", |
| 568 | "Delimiter", |
| 569 | "EquationArray", |
| 570 | "Fraction", |
| 571 | "FormulaVerticalExtent", |
| 572 | "Function", |
| 573 | "GroupChar", |
| 574 | "Limit", |
| 575 | "Matrix", |
| 576 | "Nary", |
| 577 | "Node", |
| 578 | "OperatorEmulator", |
| 579 | "Phantom", |
| 580 | "Prescript", |
| 581 | "Radical", |
| 582 | "RunStyle", |
| 583 | "Script", |
| 584 | "Sequence", |
| 585 | "Styled", |
| 586 | "Text", |
| 587 | "append_child", |
| 588 | "formula_node_count", |
| 589 | "formula_vertical_extent", |
| 590 | "is_empty", |
| 591 | "merge_run_styles", |
| 592 | ] |
| 593 |