Brunobkr/llama.cpp_AlgMor24_github

1/**2 * This file does the main work of building a domTree structure from a parse3 * tree. The entry point is the `buildHTML` function, which takes a parse tree.4 * Then, the buildExpression, buildGroup, and various groupBuilders functions5 * are called, to produce a final HTML tree.6 */7 8import ParseError from "./ParseError";9import Style from "./Style";10import {makeGlue, makeSpan, tryCombineChars} from "./buildCommon";11import {Span, Anchor} from "./domTree";12import {makeEm} from "./units";13import {spacings, tightSpacings} from "./spacingData";14import {_htmlGroupBuilders as groupBuilders} from "./defineFunction";15import {DocumentFragment} from "./tree";16 17import type Options from "./Options";18import type {AnyParseNode} from "./parseNode";19import type {HtmlDomNode, DomSpan} from "./domTree";20 21// Binary atoms (first class `mbin`) change into ordinary atoms (`mord`)22// depending on their surroundings. See TeXbook pg. 442-446, Rules 5 and 6,23// and the text before Rule 19.24const binLeftCanceller = new Set([25    "leftmost", "mbin", "mopen", "mrel", "mop", "mpunct",26]);27const binRightCanceller = new Set([28    "rightmost", "mrel", "mclose", "mpunct",29]);30 31const styleMap = {32    "display": Style.DISPLAY,33    "text": Style.TEXT,34    "script": Style.SCRIPT,35    "scriptscript": Style.SCRIPTSCRIPT,36};37 38type Side = "left" | "right";39 40const DomEnum = {41    mord: "mord",42    mop: "mop",43    mbin: "mbin",44    mrel: "mrel",45    mopen: "mopen",46    mclose: "mclose",47    mpunct: "mpunct",48    minner: "minner",49};50type DomType = keyof typeof DomEnum;51 52/**53 * Take a list of nodes, build them in order, and return a list of the built54 * nodes. documentFragments are flattened into their contents, so the55 * returned list contains no fragments. `isRealGroup` is true if `expression`56 * is a real group (no atoms will be added on either side), as opposed to57 * a partial group (e.g. one created by \color). `surrounding` is an array58 * consisting type of nodes that will be added to the left and right.59 */60export const buildExpression = function(61    expression: AnyParseNode[],62    options: Options,63    isRealGroup: boolean | "root",64    surrounding: [DomType | null | undefined, DomType | null | undefined] = [null, null],65): HtmlDomNode[] {66    // Parse expressions into `groups`.67    const groups: HtmlDomNode[] = [];68    for (let i = 0; i < expression.length; i++) {69        const output = buildGroup(expression[i], options);70        if (output instanceof DocumentFragment) {71            const children: ReadonlyArray<HtmlDomNode> = output.children;72            groups.push(...children);73        } else {74            groups.push(output);75        }76    }77 78    // Combine consecutive domTree.symbolNodes into a single symbolNode.79    tryCombineChars(groups);80 81    // If `expression` is a partial group, let the parent handle spacings82    // to avoid processing groups multiple times.83    if (!isRealGroup) {84        return groups;85    }86 87    let glueOptions = options;88    if (expression.length === 1) {89        const node = expression[0];90        if (node.type === "sizing") {91            glueOptions = options.havingSize(node.size);92        } else if (node.type === "styling") {93            glueOptions = options.havingStyle(styleMap[node.style]);94        }95    }96 97    // Dummy spans for determining spacings between surrounding atoms.98    // If `expression` has no atoms on the left or right, class "leftmost"99    // or "rightmost", respectively, is used to indicate it.100    const dummyPrev = makeSpan([surrounding[0] || "leftmost"], [], options);101    const dummyNext = makeSpan([surrounding[1] || "rightmost"], [], options);102 103    // TODO: These code assumes that a node's math class is the first element104    // of its `classes` array. A later cleanup should ensure this, for105    // instance by changing the signature of `makeSpan`.106 107    // Before determining what spaces to insert, perform bin cancellation.108    // Binary operators change to ordinary symbols in some contexts.109    const isRoot = (isRealGroup === "root");110    traverseNonSpaceNodes(groups, (node, prev): void => {111        const prevType = prev.classes[0];112        const type = node.classes[0];113        if (prevType === "mbin" && binRightCanceller.has(type)) {114            prev.classes[0] = "mord";115        } else if (type === "mbin" && binLeftCanceller.has(prevType)) {116            node.classes[0] = "mord";117        }118    }, {node: dummyPrev}, dummyNext, isRoot);119 120    traverseNonSpaceNodes(groups, (node, prev): HtmlDomNode | undefined => {121        const prevType = getTypeOfDomTree(prev);122        const type = getTypeOfDomTree(node);123 124        // 'mtight' indicates that the node is script or scriptscript style.125        const space = prevType && type ? (node.hasClass("mtight")126            ? tightSpacings[prevType]?.[type]127            : spacings[prevType]?.[type]) : null;128 129        if (space) { // Insert glue (spacing) after the `prev`.130            return makeGlue(space, glueOptions);131        }132    }, {node: dummyPrev}, dummyNext, isRoot);133 134    return groups;135};136 137// Depth-first traverse non-space `nodes`, calling `callback` with the current and138// previous node as arguments, optionally returning a node to insert after the139// previous node. `prev` is an object with the previous node and `insertAfter`140// function to insert after it. `next` is a node that will be added to the right.141// Used for bin cancellation and inserting spacings.142const traverseNonSpaceNodes = function(143    nodes: HtmlDomNode[],144    callback: (arg0: HtmlDomNode, arg1: HtmlDomNode) =>145        HtmlDomNode | null | void,146    prev: {147        node: HtmlDomNode,148        insertAfter?: (arg0: HtmlDomNode) => void,149    },150    next: HtmlDomNode | null | undefined,151    isRoot: boolean,152) {153    if (next) { // temporarily append the right node, if exists154        nodes.push(next);155    }156    let i = 0;157    for (; i < nodes.length; i++) {158        const node = nodes[i];159        const partialGroup = checkPartialGroup(node);160 161        if (partialGroup) { // Recursive DFS162            // TODO(ts): partialGroup.children is ReadonlyArray but this163            // function mutates the array (insertAfter splices into it).164            traverseNonSpaceNodes(partialGroup.children as HtmlDomNode[],165                callback, prev, null, isRoot);166            continue;167        }168 169        // Ignore explicit spaces (e.g., \;, \,) when determining what implicit170        // spacing should go between atoms of different classes171        const nonspace = !node.hasClass("mspace");172        if (nonspace) {173            const result = callback(node, prev.node);174            if (result) {175                if (prev.insertAfter) {176                    prev.insertAfter(result);177                } else { // insert at front178                    nodes.unshift(result);179                    i++;180                }181            }182        }183 184        if (nonspace) {185            prev.node = node;186        } else if (isRoot && node.hasClass("newline")) {187            prev.node = makeSpan(["leftmost"]); // treat like beginning of line188        }189        prev.insertAfter = (index => n => {190            nodes.splice(index + 1, 0, n);191            i++;192        })(i);193    }194 195    if (next) {196        nodes.pop();197    }198};199 200// Check if given node is a partial group, i.e., does not affect spacing around.201const checkPartialGroup = function(202    node: HtmlDomNode,203): DocumentFragment<HtmlDomNode> | Anchor | DomSpan | null | undefined {204    if (node instanceof DocumentFragment || node instanceof Anchor205        || (node instanceof Span && node.hasClass("enclosing"))) {206        return node;207    }208    return null;209};210 211// Return the outermost node of a domTree.212const getOutermostNode = function(213    node: HtmlDomNode,214    side: Side,215): HtmlDomNode {216    const partialGroup = checkPartialGroup(node);217    if (partialGroup) {218        const children = partialGroup.children;219        if (children.length) {220            if (side === "right") {221                return getOutermostNode(children[children.length - 1], "right");222            } else if (side === "left") {223                return getOutermostNode(children[0], "left");224            }225        }226    }227    return node;228};229 230// Return math atom class (mclass) of a domTree.231// If `side` is given, it will get the type of the outermost node at given side.232export const getTypeOfDomTree = function(233    node: HtmlDomNode | null | undefined,234    side?: Side | null | undefined,235): DomType | null | undefined {236    if (!node) {237        return null;238    }239    if (side) {240        node = getOutermostNode(node, side);241    }242    // This makes a lot of assumptions as to where the type of atom243    // appears.  We should do a better job of enforcing this.244    const className = node.classes[0] as keyof typeof DomEnum;245    return (DomEnum[className] as DomType | undefined) || null;246};247export const makeNullDelimiter = function(248    options: Options,249    classes: string[],250): DomSpan {251    const moreClasses = ["nulldelimiter"].concat(options.baseSizingClasses());252    return makeSpan(classes.concat(moreClasses));253};254 255/**256 * buildGroup is the function that takes a group and calls the correct groupType257 * function for it. It also handles the interaction of size and style changes258 * between parents and children.259 */260export const buildGroup = function(261    group: AnyParseNode | null | undefined,262    options: Options,263    baseOptions?: Options,264): HtmlDomNode {265    if (!group) {266        return makeSpan();267    }268 269    if (groupBuilders[group.type]) {270        // TODO(ts): groupBuilders is Record<string, HtmlBuilder<any>>;271        // a type-safe registry would need a mapped type keyed by NodeType.272        let groupNode: HtmlDomNode = groupBuilders[group.type](group, options);273 274        // If the size changed between the parent and the current group, account275        // for that size difference.276        if (baseOptions && options.size !== baseOptions.size) {277            groupNode = makeSpan(options.sizingClasses(baseOptions),278                [groupNode], options);279 280            const multiplier =281                options.sizeMultiplier / baseOptions.sizeMultiplier;282 283            groupNode.height *= multiplier;284            groupNode.depth *= multiplier;285        }286 287        return groupNode;288    } else {289        throw new ParseError(290            "Got group of unknown type: '" + group.type + "'");291    }292};293 294/**295 * Combine an array of HTML DOM nodes (e.g., the output of `buildExpression`)296 * into an unbreakable HTML node of class .base, with proper struts to297 * guarantee correct vertical extent.  `buildHTML` calls this repeatedly to298 * make up the entire expression as a sequence of unbreakable units.299 */300function buildHTMLUnbreakable(children: HtmlDomNode[], options: Options) {301    // Compute height and depth of this chunk.302    const body = makeSpan(["base"], children, options);303 304    // Add strut, which ensures that the top of the HTML element falls at305    // the height of the expression, and the bottom of the HTML element306    // falls at the depth of the expression.307    const strut = makeSpan(["strut"]);308    strut.style.height = makeEm(body.height + body.depth);309    if (body.depth) {310        strut.style.verticalAlign = makeEm(-body.depth);311    }312    body.children.unshift(strut);313 314    return body;315}316 317/**318 * Take an entire parse tree, and build it into an appropriate set of HTML319 * nodes.320 */321export default function buildHTML(tree: AnyParseNode[], options: Options): DomSpan {322    // Strip off outer tag wrapper for processing below.323    let tag = null;324    if (tree.length === 1 && tree[0].type === "tag") {325        tag = tree[0].tag;326        tree = tree[0].body;327    }328 329    // Build the expression contained in the tree330    const expression = buildExpression(tree, options, "root");331 332    let eqnNum;333    if (expression.length === 2 && expression[1].hasClass("tag")) {334        // An environment with automatic equation numbers, e.g. {gather}.335        eqnNum = expression.pop();336    }337 338    const children = [];339 340    // Create one base node for each chunk between potential line breaks.341    // The TeXBook [p.173] says "A formula will be broken only after a342    // relation symbol like $=$ or $<$ or $\rightarrow$, or after a binary343    // operation symbol like $+$ or $-$ or $\times$, where the relation or344    // binary operation is on the ``outer level'' of the formula (i.e., not345    // enclosed in {...} and not part of an \over construction)."346 347    let parts = [];348    for (let i = 0; i < expression.length; i++) {349        parts.push(expression[i]);350        if (expression[i].hasClass("mbin") ||351            expression[i].hasClass("mrel") ||352            expression[i].hasClass("allowbreak")) {353            // Put any post-operator glue on same line as operator.354            // Watch for \nobreak along the way, and stop at \newline.355            let nobreak = false;356            while (i < expression.length - 1 &&357                   expression[i + 1].hasClass("mspace") &&358                   !expression[i + 1].hasClass("newline")) {359                i++;360                parts.push(expression[i]);361                if (expression[i].hasClass("nobreak")) {362                    nobreak = true;363                }364            }365            // Don't allow break if \nobreak among the post-operator glue.366            if (!nobreak) {367                children.push(buildHTMLUnbreakable(parts, options));368                parts = [];369            }370        } else if (expression[i].hasClass("newline")) {371            // Write the line except the newline372            parts.pop();373            if (parts.length > 0) {374                children.push(buildHTMLUnbreakable(parts, options));375                parts = [];376            }377            // Put the newline at the top level378            children.push(expression[i]);379        }380    }381    if (parts.length > 0) {382        children.push(buildHTMLUnbreakable(parts, options));383    }384 385    // Now, if there was a tag, build it too and append it as a final child.386    let tagChild;387    if (tag) {388        tagChild = buildHTMLUnbreakable(389            buildExpression(tag, options, true),390            options,391        );392        tagChild.classes = ["tag"];393        children.push(tagChild);394    } else if (eqnNum) {395        children.push(eqnNum);396    }397 398    const htmlNode = makeSpan(["katex-html"], children);399    htmlNode.setAttribute("aria-hidden", "true");400 401    // Adjust the strut of the tag to be the maximum height of all children402    // (the height of the enclosing htmlNode) for proper vertical alignment.403    if (tagChild) {404        const strut = tagChild.children[0];405        strut.style.height = makeEm(htmlNode.height + htmlNode.depth);406        if (htmlNode.depth) {407            strut.style.verticalAlign = makeEm(-htmlNode.depth);408        }409    }410 411    return htmlNode;412}413