/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Eswara Rajesh Pinapala epinapala@live.com
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
/*
 * Reads a page written in wiki markup and gives back the html it stands
 * for, so a writer sees while writing what a reader will see. What it
 * makes is meant to match what the site makes of the same page. The
 * words it works on, and the scanner it reads them with, live here too,
 * since nothing else needs them.
 */
/**
 * Whether a character is whitespace in the wider sense: a space, tab,
 * newline, carriage return, vertical tab, or form feed. Used where the
 * parser skips any of these rather than only spaces and tabs.
 *
 * @param {string} character one character to test
 * @return {boolean} true when the character is one of those
 */
function isWhitespaceChar(character)
{
    return character !== "" && " \t\n\r\x0B\f".indexOf(character) !== -1;
}

/**
 * Whether a character is a space or tab, the horizontal whitespace the
 * parser treats as blank filler within a line.
 *
 * @param {string} character one character to test
 * @return {boolean} true when the character is a space or tab
 */
function isSpaceChar(character)
{
    return character === " " || character === "\t";
}

/**
 * Whether a character is an ascii letter.
 *
 * @param {string} character one character to test
 * @return {boolean} true when the character is a through z either case
 */
function isAlphaChar(character)
{
    return (character >= "a" && character <= "z") ||
        (character >= "A" && character <= "Z");
}

/**
 * Whether a character is an ascii letter or digit.
 *
 * @param {string} character one character to test
 * @return {boolean} true when the character is a letter or a digit
 */
function isAlnumChar(character)
{
    return isAlphaChar(character) ||
        (character >= "0" && character <= "9");
}

/**
 * Removes a fixed set of whitespace from both ends of a string: spaces,
 * tabs, newlines, carriage returns, null bytes, and vertical tabs. This
 * set is narrower than the one the built-in javascript trim removes, and
 * is the set the server parser trims.
 *
 * @param {string} text the text to trim
 * @return {string} the text without that leading or trailing whitespace
 */
function trim(text)
{
    return ltrim(rtrim(text));
}

/**
 * Removes that same set of whitespace from the start of a string only.
 *
 * @param {string} text the text to trim
 * @return {string} the text without that leading whitespace
 */
function ltrim(text)
{
    var start = 0;
    while (start < text.length &&
        " \t\n\r\0\x0B".indexOf(text.charAt(start)) !== -1) {
        start++;
    }
    return text.slice(start);
}

/**
 * Removes that same set of whitespace from the end of a string only.
 *
 * @param {string} text the text to trim
 * @return {string} the text without that trailing whitespace
 */
function rtrim(text)
{
    var end = text.length;
    while (end > 0 &&
        " \t\n\r\0\x0B".indexOf(text.charAt(end - 1)) !== -1) {
        end--;
    }
    return text.slice(0, end);
}

/**
 * Escapes the five characters html treats specially so a run of text can
 * sit safely in page content or an attribute, escaping both quote marks.
 * When double encoding is off an existing entity is left alone rather
 * than having its ampersand escaped again.
 *
 * @param {string} text the text to escape
 * @param {boolean} double_encode whether to escape an ampersand that
 *      already begins an entity
 * @return {string} the escaped text
 */
function htmlSpecialChars(text, double_encode)
{
    if (double_encode === undefined) {
        double_encode = true;
    }
    var out = "";
    var index = 0;
    while (index < text.length) {
        var character = text.charAt(index);
        if (character === "&") {
            if (!double_encode && entityStartsAt(text, index)) {
                out += "&";
            } else {
                out += "&amp;";
            }
        } else if (character === "\"") {
            out += "&quot;";
        } else if (character === "'") {
            out += "&#039;";
        } else if (character === "<") {
            out += "&lt;";
        } else if (character === ">") {
            out += "&gt;";
        } else {
            out += character;
        }
        index++;
    }
    return out;
}

/**
 * Whether an ampersand at the given offset already begins an html entity,
 * either a named one, a decimal reference, or a hexadecimal reference, so
 * htmlspecialchars can leave it alone when double encoding is off.
 *
 * @param {string} text the text being escaped
 * @param {number} at the offset of the ampersand
 * @return {boolean} true when a full entity begins at the ampersand
 */
function entityStartsAt(text, at)
{
    var rest = text.slice(at + 1);
    var match = rest.match(/^#[0-9]+;/) || rest.match(/^#[xX][0-9a-fA-F]+;/) ||
        rest.match(/^[a-zA-Z][a-zA-Z0-9]*;/);
    return match !== null;
}

/**
 * Undoes html escaping of the five special characters, both quote marks
 * included, so a document escaped on the way in can be read back before
 * it is parsed.
 *
 * @param {string} text the text to unescape
 * @return {string} the text with entities turned back into characters
 */
function htmlSpecialCharsDecode(text)
{
    return text.replace(/&lt;/g, "<").replace(/&gt;/g, ">").
        replace(/&quot;/g, "\"").replace(/&#0*39;/g, "'").
        replace(/&#0*39;/g, "'").replace(/&apos;/g, "'").
        replace(/&amp;/g, "&");
}

/**
 * Removes every html tag from a run of text, leaving only the text
 * between and around them, used where a heading's own text is needed
 * without any inline markup it carries.
 *
 * @param {string} text the text to strip tags from
 * @return {string} the text with tags removed
 */
function stripTags(text)
{
    return text.replace(/<[^>]*>/g, "");
}

/**
 * Splits a string on a separator into at most a given number of pieces,
 * where the final piece keeps any further separators, used for link and
 * template parts that must not be split past their first few fields.
 *
 * @param {string} separator the text to split on
 * @param {string} text the text to split
 * @param {number} limit the greatest number of pieces to return
 * @return {Array} the pieces
 */
function splitLimit(separator, text, limit)
{
    var parts = text.split(separator);
    if (limit > 0 && parts.length > limit) {
        var head = parts.slice(0, limit - 1);
        head.push(parts.slice(limit - 1).join(separator));
        return head;
    }
    return parts;
}

/**
 * Counts the non-overlapping times a needle occurs in a string, used to
 * weigh nowiki openers against closers.
 *
 * @param {string} haystack the text to search
 * @param {string} needle the text to count
 * @return {number} how many non-overlapping times needle occurs
 */
function substrCount(haystack, needle)
{
    if (needle === "") {
        return 0;
    }
    var count = 0;
    var pos = 0;
    while ((pos = haystack.indexOf(needle, pos)) !== -1) {
        count++;
        pos += needle.length;
    }
    return count;
}

/**
 * Reads markup one character at a time so a parser can hunt for the next
 * token without copying the rest of the document, a port of the php
 * MarkUpScanner class. It keeps the source and a single cursor position;
 * every read returns a small span cut from the source rather than a
 * rebuilt tail.
 */
class MarkUpScanner
{
    /**
     * Sets up a scanner over a piece of markup, first normalizing its
     * line endings to plain newlines so a stray carriage return cannot
     * ride along at the end of a line and defeat a block matcher.
     *
     * @param {string} source the markup to scan
     * @param {string} block_start_chars each character that may start a
     *      block for this markup flavor, concatenated
     */
    constructor(source, block_start_chars)
    {
        this.source = source.replace(/\r\n/g, "\n").replace(/\r/g, "\n");
        this.position = 0;
        this.length = this.source.length;
        this.block_start_chars = block_start_chars;
    }
    /**
     * Whether the cursor has reached the end of the source.
     * @return {boolean} true if nothing remains to read
     */
    atEnd()
    {
        return this.position >= this.length;
    }
    /**
     * The current cursor offset, so a caller can remember a spot and
     * later return to it.
     * @return {number} the offset into the source
     */
    tell()
    {
        return this.position;
    }
    /**
     * Moves the cursor back to a remembered offset.
     * @param {number} offset an offset previously returned by tell
     * @return {void}
     */
    seek(offset)
    {
        this.position = offset;
    }
    /**
     * Looks at a character near the cursor without consuming it.
     * @param {number} ahead how many characters past the cursor to look
     * @return {string} the character, or the empty string past the end
     */
    peek(ahead)
    {
        if (ahead === undefined) {
            ahead = 0;
        }
        var at = this.position + ahead;
        return at < this.length ? this.source.charAt(at) : "";
    }
    /**
     * Moves the cursor forward.
     * @param {number} count how many characters to consume
     * @return {void}
     */
    advance(count)
    {
        if (count === undefined) {
            count = 1;
        }
        this.position += count;
    }
    /**
     * Whether the source at the cursor begins with the given text.
     * @param {string} text the text to compare against
     * @return {boolean} true if the next characters match text exactly
     */
    startsWith(text)
    {
        return this.source.startsWith(text, this.position);
    }
    /**
     * Whether the cursor sits at the start of a line, meaning it is at
     * the very beginning of the source or just past a newline.
     * @return {boolean} true at a line start
     */
    atLineStart()
    {
        return this.position === 0 ||
            this.source.charAt(this.position - 1) === "\n";
    }
    /**
     * Returns the source from the cursor to the end without moving the
     * cursor, so a caller can inspect all that remains to be read.
     * @return {string} the unread remainder of the source
     */
    rest()
    {
        return this.source.slice(this.position);
    }
    /**
     * Returns the whole source the scanner runs over, so a caller that works
     * from an offset can be handed the text and the cursor rather than a
     * fresh copy of all that remains. The cursor is not moved.
     * @return {string} the full source
     */
    source_text()
    {
        return this.source;
    }
    /**
     * Consumes characters until one of the stop characters (or a newline,
     * or the end of the source) is reached, and returns what was consumed.
     *
     * @param {string} stops each character that ends the run, concatenated
     * @return {string} the characters read before the stop
     */
    readUntil(stops)
    {
        var start = this.position;
        while (this.position < this.length) {
            var current = this.source.charAt(this.position);
            if (current === "\n" || stops.indexOf(current) !== -1) {
                break;
            }
            this.position++;
        }
        return this.source.slice(start, this.position);
    }
    /**
     * Consumes the rest of the current line and returns it without the
     * trailing newline, leaving the cursor at the start of the next line.
     * @return {string} the line's text
     */
    readLine()
    {
        var start = this.position;
        while (this.position < this.length &&
            this.source.charAt(this.position) !== "\n") {
            this.position++;
        }
        var line = this.source.slice(start, this.position);
        if (this.position < this.length) {
            this.position++;
        }
        return line;
    }
    /**
     * Consumes a run of the same character and reports how many there
     * were, used for markers made of repeated characters.
     *
     * @param {string} character the single character to count
     * @return {number} how many copies were consumed
     */
    readRepeat(character)
    {
        var count = 0;
        while (this.position < this.length &&
            this.source.charAt(this.position) === character) {
            this.position++;
            count++;
        }
        return count;
    }
    /**
     * Skips a run of blank lines, leaving the cursor at the first line
     * that has content or at the end of the source.
     * @return {void}
     */
    skipBlankLines()
    {
        while (this.position < this.length) {
            var mark = this.position;
            while (this.position < this.length &&
                (this.source.charAt(this.position) === " " ||
                this.source.charAt(this.position) === "\t")) {
                this.position++;
            }
            if (this.position < this.length &&
                this.source.charAt(this.position) === "\n") {
                this.position++;
            } else if (this.position < this.length) {
                this.position = mark;
                break;
            } else {
                break;
            }
        }
    }
    /**
     * Whether the character at the cursor is one that can begin a block
     * for this markup flavor.
     * @return {boolean} true if the cursor's character may open a block
     */
    atBlockStartChar()
    {
        if (this.position >= this.length) {
            return false;
        }
        return this.block_start_chars.indexOf(
            this.source.charAt(this.position)) !== -1;
    }
    /**
     * Whether the line at the cursor is blank, that is empty or only
     * spaces and tabs before its newline.
     * @return {boolean} true when the current line has no visible content
     */
    atBlankLine()
    {
        var at = this.position;
        while (at < this.length && (this.source.charAt(at) === " " ||
            this.source.charAt(at) === "\t")) {
            at++;
        }
        return at >= this.length || this.source.charAt(at) === "\n";
    }
    /**
     * From a cursor sitting on an opening double brace, consumes through
     * the matching close, counting nested double braces, and returns the
     * text between them. When there is no match the cursor is left where
     * it began and false is returned.
     *
     * @return {(string|boolean)} the text between the braces, or false
     *      when the opening brace is never matched
     */
    matchBraces()
    {
        var start = this.position;
        var depth = 0;
        while (this.position < this.length - 1) {
            if (this.source.charAt(this.position) === "{" &&
                this.source.charAt(this.position + 1) === "{") {
                depth++;
                this.position += 2;
            } else if (this.source.charAt(this.position) === "}" &&
                this.source.charAt(this.position + 1) === "}") {
                depth--;
                this.position += 2;
                if (depth === 0) {
                    return this.source.slice(start + 2, this.position - 2);
                }
            } else {
                this.position++;
            }
        }
        this.position = start;
        return false;
    }
}

/**
 * Escapes a single quote, a double quote, a backslash, and a null byte,
 * used on the head variable fields so they are stored the same way the
 * server stores them.
 *
 * @param {string} text the text to escape
 * @return {string} the text with those characters backslash escaped
 */
function addSlashes(text)
{
    return text.replace(/\\/g, "\\\\").replace(/'/g, "\\'").
        replace(/"/g, "\\\"").replace(/\0/g, "\\0");
}

/**
 * Parses mediawiki markup into html, a port of the mediawiki engine of
 * the php WikiParser class. Only the mediawiki engine is ported; the
 * markdown engine the server class also holds is not needed for the
 * help pages this drives.
 */
class WikiParser
{
    /**
     * Sets up a parser.
     *
     * @param {string} base_address base url a page-name link is joined to
     * @param {boolean} minimal whether to skip head-variable handling
     */
    constructor(base_address, minimal)
    {
        this.base_address = base_address === undefined ? "" : base_address;
        /* How far the lines of what is being read stand from the
           lines of the page, which a template sets while the blocks it
           holds are read. */
        this.line_offset = 0;
        this.minimal = minimal === undefined ? false : minimal;
        this.extra_rules = [];
        this.cite_references = [];
        this.toc_headings = [];
        this.collecting_headings = false;
        this.parse_depth = 0;
        this.inline_absent = {};
    }
    /**
     * Splits text into the chunks that blank lines separate, where a blank
     * line holds nothing but whitespace, used to break a page's head
     * section into its separate settings.
     *
     * @param {string} text the text to split
     * @return {Array} the non-blank chunks, each with its lines rejoined
     */
    splitOnBlankLines(text)
    {
        var chunks = [];
        var current = "";
        var lines = text.split("\n");
        for (var i = 0; i < lines.length; i++) {
            if (trim(lines[i]) === "") {
                if (current !== "") {
                    chunks.push(current);
                    current = "";
                }
            } else {
                current += (current === "") ? lines[i] : "\n" + lines[i];
            }
        }
        if (current !== "") {
            chunks.push(current);
        }
        return chunks;
    }
    /**
     * Parses a mediawiki document to produce an html equivalent. The head
     * variable section, when present and asked for, is separated off and
     * put back afterward, and the body is read block by block through the
     * scanner, with a table of contents and reference list added.
     *
     * @param {string} document the markup to parse
     * @param {boolean} parse_head_vars whether to honor a head section
     * @return {string} the html
     */
    parse(document, parse_head_vars)
    {
        if (parse_head_vars === undefined) {
            parse_head_vars = true;
        }
        var head = "";
        var page_type = "standard";
        var head_vars = {};
        var draw_toc = (this.draw_toc_asked === undefined) ?
            true : this.draw_toc_asked;
        if (parse_head_vars && !this.minimal) {
            var document_parts = document.split(WikiParser.END_HEAD_VARS);
            if (document_parts.length > 1) {
                head = document_parts[0];
                document = document_parts[1];
                var head_lines = this.splitOnBlankLines(head);
                for (var i = 0; i < head_lines.length; i++) {
                    var line = head_lines[i];
                    var semi = line.indexOf(";");
                    var semi_pos = semi > 0 ? semi : line.length;
                    line = line.slice(0, semi_pos);
                    var line_parts = line.split("=");
                    if (line_parts.length === 2) {
                        head_vars[trim(addSlashes(line_parts[0]))] =
                            addSlashes(trim(line_parts[1]));
                    }
                }
                if (head_vars["page_type"] !== undefined) {
                    page_type = head_vars["page_type"];
                }
                if (head_vars["toc"] !== undefined) {
                    draw_toc = head_vars["toc"];
                }
            }
        }
        document = htmlSpecialCharsDecode(document);
        this.cite_references = [];
        this.toc_headings = [];
        this.collecting_headings = true;
        this.parse_depth = 0;
        var scanner = new MarkUpScanner(document,
            WikiParser.WIKI_BLOCK_START_CHARS);
        var body = (page_type == "presentation") ?
            this.parseSlides(scanner) : this.parseBlocks(scanner);
        var toc = (draw_toc && page_type != "presentation") ?
            this.tableOfContents(this.toc_headings) : "";
        document = this.insertTableOfContents(body, toc) +
            this.referenceList();
        if (head != "" && parse_head_vars) {
            document = head + WikiParser.END_HEAD_VARS + document;
        }
        return document;
    }
    /**
     * Tries each added rule against the text at the given offset and
     * returns the first that matches, or null when none apply.
     *
     * @param {string} text the text being read
     * @param {number} index the offset to try the rules at
     * @return {(Object|null)} the matching rule's result, or null
     */
    applyExtraRules(text, index)
    {
        for (var i = 0; i < this.extra_rules.length; i++) {
            var result = this.extra_rules[i](text, index);
            if (result !== null) {
                return result;
            }
        }
        return null;
    }
    /**
     * Finds the next place a marker appears at or after a point, giving the
     * same answer a plain search would but remembering once a marker is
     * known to be absent from a point through to the end, so a later look
     * from that point or beyond returns at once instead of scanning the tail
     * again. Without this an inline run full of openers whose closer never
     * comes would search to the end from each opener and cost the square of
     * the run's length. The note lives in inline_absent, which each inline
     * pass clears for its own text; since a pass only moves its cursor
     * forward, a marker missing from one point is missing from every later
     * one.
     *
     * @param {string} text the text being scanned
     * @param {string} marker the marker to look for
     * @param {number} from the offset to search from
     * @return {number} the marker's offset, or minus one when there is none
     */
    findMark(text, marker, from)
    {
        if (this.inline_absent[marker] !== undefined &&
            from >= this.inline_absent[marker]) {
            return -1;
        }
        var found = text.indexOf(marker, from);
        if (found === -1) {
            this.inline_absent[marker] = from;
        }
        return found;
    }
    /**
     * Parses a run of blocks from the scanner, emitting each block's html
     * as it is read. Blank lines between blocks are skipped.
     *
     * @param {MarkUpScanner} scanner the scanner positioned at a block
     * @return {string} the html for the blocks read
     */
    /**
     * parseSlides reads a whole presentation as a run of slides and
     * wraps it in the marks frise draws a deck from. A line holding only
     * four dots separates one slide from the next. Each slide's own text
     * is read by the ordinary block parse, so everything a wiki page may
     * hold works inside a slide.
     *
     * @param {MarkUpScanner} scanner at the start of the page
     * @return {string} the html for the whole deck
     */
    parseSlides(scanner)
    {
        let slides = "";
        while (!scanner.atEnd()) {
            slides += "<x-slide>\n" + this.parseSlide(scanner) +
                "</x-slide>\n";
            /* Step over the separator that ended the slide, so the next
               turn starts on the line after it. */
            if (!scanner.atEnd()) {
                scanner.readLine();
            }
        }
        return "<x-slides>\n" + slides + "</x-slides>\n";
    }
    /**
     * parseSlide reads the blocks of one slide, stopping at the line
     * that separates it from the next slide or at the end of the page.
     * The scanner is left on that separator line so the caller can step
     * over it.
     *
     * @param {MarkUpScanner} scanner at the slide's first line
     * @return {string} the html for that slide's blocks
     */
    parseSlide(scanner)
    {
        let html = "";
        while (!scanner.atEnd()) {
            scanner.skipBlankLines();
            if (scanner.atEnd() || this.atSlideBreak(scanner)) {
                break;
            }
            html += this.parseBlock(scanner);
        }
        return html;
    }
    /**
     * atSlideBreak says whether the scanner sits on the line that
     * separates one slide from the next. The scanner is left where it
     * was, since this only looks.
     *
     * @param {MarkUpScanner} scanner to look at
     * @return {boolean} true when the line ahead separates two slides
     */
    atSlideBreak(scanner)
    {
        if (!scanner.atLineStart()) {
            return false;
        }
        /* This scanner reads a line by consuming it, so the line is read
           and the reader put back where it was. */
        let mark = scanner.tell();
        let line = scanner.readLine();
        scanner.seek(mark);
        return line.replace(/\s+$/, "") === WikiParser.SLIDE_SEPARATOR;
    }
    parseBlocks(scanner)
    {
        this.parse_depth++;
        if (this.parse_depth > WikiParser.WIKI_MAX_PARSE_DEPTH) {
            this.parse_depth--;
            return this.escapeText(scanner.rest());
        }
        var html = "";
        while (!scanner.atEnd()) {
            scanner.skipBlankLines();
            if (scanner.atEnd()) {
                break;
            }
            /* While a preview is being drawn, each block is stamped with
               the line of the source it began on. That gives the two panes
               a common answer to "where am I", so lining them up is a
               lookup rather than a guess from the words. */
            if (wiki_preview_marks_lines && !this.stampsItsOwnLines(
                scanner)) {
                var began = scanner.source_text().slice(0,
                    scanner.position).split("\n").length +
                    this.line_offset;
                html += "<span class='wiki-line' id='wiki-line-" + began +
                    "' data-line='" + began + "'></span>";
            }
            html += this.parseBlock(scanner);
        }
        this.parse_depth--;
        return html;
    }
    /**
     * Reads and emits one block by looking at how its first line opens: a
     * template or table brace, a pre tag, a heading, a rule, an indent, a
     * list, or, when none of those fit, a paragraph.
     *
     * @param {MarkUpScanner} scanner the scanner at the block's first line
     * @return {string} the html for that block
     */
    parseBlock(scanner)
    {
        /* A slide separator met while reading blocks rather than slides
           is drawn as a rule across the page. The preview reads a
           presentation this way so that each block still stamps the
           source line it began on, which is what lines the two panes
           up. */
        if (this.atSlideBreak(scanner)) {
            scanner.readLine();
            return "<hr class='slide-break' />\n";
        }
        if (this.extra_rules.length > 0) {
            var rule_result = this.applyExtraRules(scanner.source_text(),
                scanner.tell());
            if (rule_result !== null) {
                scanner.seek(rule_result["next"]);
                return rule_result["html"];
            }
        }
        if (scanner.startsWith("{{")) {
            var template = this.parseTemplate(scanner);
            if (template !== null) {
                return template;
            }
        }
        if (scanner.startsWith("{|")) {
            return this.parseTable(scanner);
        }
        if (scanner.startsWith("<notoc>")) {
            return this.parseNotocRegion(scanner);
        }
        if (scanner.startsWith("<pre>")) {
            return this.parsePre(scanner);
        }
        if (scanner.startsWith("<code>")) {
            return this.parseCodeBlock(scanner);
        }
        var first = scanner.peek();
        if (first === " " && scanner.atLineStart()) {
            return this.parseSpacePre(scanner);
        }
        if (first === "=") {
            var heading = this.parseHeading(scanner);
            if (heading !== null) {
                return heading;
            }
        }
        if (first === "-") {
            var rule = this.parseRule(scanner);
            if (rule !== null) {
                return rule;
            }
        }
        if (first === ":" && this.startsBlock(scanner)) {
            return this.parseIndent(scanner);
        }
        if (first === ";" && this.startsBlock(scanner)) {
            return this.parseDefinitionList(scanner);
        }
        if (first === "*" || first === "#") {
            return this.parseList(scanner);
        }
        return this.parseParagraph(scanner);
    }
    /**
     * Reports whether the scanner sits at the start of a line that begins
     * a confirmed block, so a single newline inside running text does not
     * split it.
     *
     * @param {MarkUpScanner} scanner the scanner at a line start
     * @return {boolean} true when the line opens a new block
     */
    startsBlock(scanner)
    {
        var first = scanner.peek();
        /* A slide separator ends whatever block is being read, the same
           way a heading or a rule does. Without this a list or a
           paragraph running up to the separator takes it as one more of
           its own lines, and the slide never ends. */
        if (first === "." && this.atSlideBreak(scanner)) {
            return true;
        }
        if (first === "=" || first === "*" || first === "#" ||
            first === " ") {
            return true;
        }
        if (first === "-") {
            return scanner.startsWith("----");
        }
        if (first === "<") {
            return scanner.startsWith("<pre>") ||
                scanner.startsWith("<code>") ||
                scanner.startsWith("<notoc>");
        }
        if (first === "{") {
            return scanner.startsWith("{|") || scanner.startsWith("{{");
        }
        if (first === ":") {
            var ahead = 0;
            while (scanner.peek(ahead) === ":") {
                ahead++;
            }
            var after = scanner.peek(ahead);
            return after === " " || after === "\t";
        }
        if (first === ";") {
            var scan = 1;
            while (scanner.peek(scan) !== "" &&
                scanner.peek(scan) !== "\n") {
                if (scanner.peek(scan) === ":") {
                    return true;
                }
                scan++;
            }
            return false;
        }
        return false;
    }
    /**
     * Reads a heading line, one run of equals signs, the title, then a
     * closing run of equals signs; the smaller run count is its level. A
     * notoc marker keeps the heading out of the contents box. Returns null
     * when the line is not a heading.
     *
     * @param {MarkUpScanner} scanner the scanner at the heading line
     * @return {(string|null)} the heading html, or null when not a heading
     */
    parseHeading(scanner)
    {
        var mark = scanner.tell();
        var line = scanner.readLine();
        var in_contents = true;
        if (line.indexOf("<notoc>") !== -1) {
            in_contents = false;
            line = line.replace(/<notoc>/g, "").replace(/<\/notoc>/g, "");
        }
        var length = line.length;
        var open = 0;
        while (open < length && line.charAt(open) === "=") {
            open++;
        }
        var end = length;
        while (end > open && (line.charAt(end - 1) === " " ||
            line.charAt(end - 1) === "\t")) {
            end--;
        }
        var close = 0;
        while (close < end - open && line.charAt(end - 1 - close) === "=") {
            close++;
        }
        if (open === 0 || close === 0) {
            scanner.seek(mark);
            return null;
        }
        var level = Math.min(open, close, WikiParser.MAX_HEADING_LEVEL);
        var text = trim(line.slice(open, end - close));
        var inline = this.renderInline(text);
        var anchor = stripTags(inline);
        if (this.collecting_headings && in_contents) {
            this.toc_headings.push({level: level, text: anchor});
        }
        return "<h" + level + " id=\"" + anchor + "\">" + inline +
            "</h" + level + ">\n";
    }
    /**
     * Reads a horizontal rule, a line of four or more dashes and nothing
     * else. Returns null when the dashes are followed by other text.
     *
     * @param {MarkUpScanner} scanner the scanner at the dashed line
     * @return {(string|null)} the rule html, or null when not a rule
     */
    parseRule(scanner)
    {
        var mark = scanner.tell();
        var line = scanner.readLine();
        var length = line.length;
        var dashes = 0;
        while (dashes < length && line.charAt(dashes) === "-") {
            dashes++;
        }
        if (dashes >= 4 && rtrim(line.slice(dashes)) === "") {
            return "<hr />\n";
        }
        scanner.seek(mark);
        return null;
    }
    /**
     * Reads a colon indent: the leading colons set the depth and the rest
     * of the line, with any plain continuation lines, is the indented
     * text, shown as an indented paragraph.
     *
     * @param {MarkUpScanner} scanner the scanner at the colon line
     * @return {string} the indent html
     */
    parseIndent(scanner)
    {
        var line = scanner.readLine();
        var length = line.length;
        var colons = 0;
        while (colons < length && line.charAt(colons) === ":") {
            colons++;
        }
        var level = Math.min(colons, WikiParser.MAX_INDENT_LEVEL);
        var text = line.slice(colons + 1);
        var together = this.readSameUnit(text, scanner);
        if (together !== null) {
            return "<div class=\"indent" + level + "\">" + together +
                "</div>\n";
        }
        while (!scanner.atEnd() && !scanner.atBlankLine() &&
            !this.startsBlock(scanner)) {
            text += "\n" + scanner.readLine();
        }
        return "<p><span class=\"indent" + level + "\">&nbsp;</span>" +
            this.renderInline(text) + "</p>\n";
    }
    /**
     * Reads a definition list, a run of lines each naming a term, a colon,
     * then that term's meaning, and emits them as one description list.
     *
     * @param {MarkUpScanner} scanner the scanner at the first term line
     * @return {string} the definition-list html
     */
    parseDefinitionList(scanner)
    {
        var html = "<dl>\n";
        while (!scanner.atEnd() && scanner.peek() === ";" &&
            this.startsBlock(scanner)) {
            var rest = scanner.readLine().slice(1);
            var colon = rest.indexOf(":");
            var term = trim(rest.slice(0, colon));
            var meaning = trim(rest.slice(colon + 1));
            var together = this.readSameUnit(meaning, scanner);
            html += "<dt>" + this.renderInline(term) + "</dt>\n<dd>" +
                ((together === null) ? this.renderInline(meaning) :
                together) + "</dd>\n";
        }
        return html + "</dl>\n";
    }
    /**
     * Reads what a same-unit mark holds, where one opens what would
     * otherwise be a single line's worth of content.
     *
     * Some things a page is made of take only as much as fits on their own
     * line: the meaning beside a term in a definition list is one. A
     * writer who wants a list, or a second paragraph, inside such a thing
     * has nowhere to put it, since the next line starts something new. The
     * mark says the lines it holds are all the content of the thing being
     * read, however many there are, so what is inside is read as ordinary
     * blocks and handed back whole.
     *
     * Reading stops where the braces balance rather than at the end of a
     * line, so the mark may hold lists, paragraphs and further marks.
     *
     * @param {string} opening what was left of the line after the thing's
     *      own mark, which may or may not open a same-unit
     * @param {MarkUpScanner} scanner the scanner, just past that line
     * @return {string|null} the html of what the mark held, or null where
     *      the line did not open one
     */
    readSameUnitText(text)
    {
        var mark = "{{same-unit";
        var at = text.toLowerCase().indexOf(mark);
        if (at === -1) {
            return null;
        }
        var before = text.slice(0, at);
        var inner = text.slice(at + mark.length);
        var close = inner.lastIndexOf("}}");
        if (close !== -1) {
            inner = inner.slice(0, close);
        }
        var was = this.collecting_headings;
        this.collecting_headings = false;
        var content = new MarkUpScanner(trim(inner),
            WikiParser.WIKI_BLOCK_START_CHARS);
        var html = this.parseBlocks(content);
        this.collecting_headings = was;
        if (trim(before) !== "") {
            html = this.renderInline(trim(before)) + " " + html;
        }
        return html;
    }
    readSameUnit(opening, scanner)
    {
        var mark = "{{same-unit";
        /* The mark may come after words of the writer's own, as when a
           list item names what it is about and then holds the rest, so it
           is looked for anywhere in the line rather than only at its
           start. What comes before it is kept and read as it would have
           been. */
        var at = opening.toLowerCase().indexOf(mark);
        if (at === -1) {
            return null;
        }
        var before = opening.slice(0, at);
        var gathered = opening.slice(at);
        var opens = function (text, brace) {
            return text.split(brace).length - 1;
        };
        while (opens(gathered, "{{") > opens(gathered, "}}") &&
            !scanner.atEnd()) {
            gathered += "\n" + scanner.readLine();
        }
        var inner = gathered.slice(mark.length);
        var close = inner.lastIndexOf("}}");
        if (close !== -1) {
            inner = inner.slice(0, close);
        }
        var was = this.collecting_headings;
        this.collecting_headings = false;
        var content = new MarkUpScanner(trim(inner),
            WikiParser.WIKI_BLOCK_START_CHARS);
        /* The reader built above counts from the text the
           template holds, so the lines it stamps are moved on by
           where that text began in the page. */
        var html = this.parseBlocks(content);
        this.collecting_headings = was;
        if (trim(before) !== "") {
            html = this.renderInline(trim(before)) + " " + html;
        }
        return html;
    }
    /**
     * Reads a whole list, gathering its item lines and folding plain
     * continuation lines into the item above them, then hands the run to
     * the nesting builder.
     *
     * @param {MarkUpScanner} scanner the scanner at the first list line
     * @return {string} the list html
     */
    parseList(scanner)
    {
        var list_lines = [];
        while (!scanner.atEnd() && !scanner.atBlankLine()) {
            var first = scanner.peek();
            var began = (!wiki_preview_marks_lines) ? 0 :
                scanner.source_text().slice(0, scanner.position).split(
                "\n").length;
            if (first === "*" || first === "#") {
                var line = scanner.readLine();
                var length = line.length;
                var marker_length = 0;
                while (marker_length < length &&
                    (line.charAt(marker_length) === "*" ||
                    line.charAt(marker_length) === "#")) {
                    marker_length++;
                }
                var text = line.slice(marker_length);
                if (text !== "" && (text.charAt(0) === " " ||
                    text.charAt(0) === "\t")) {
                    text = text.slice(1);
                }
                list_lines.push({marker: line.slice(0, marker_length),
                    text: text, began: began,
                    held: this.readSameUnit(text, scanner)});
            } else if (!this.startsBlock(scanner)) {
                var last = list_lines.length - 1;
                list_lines[last]["text"] += "\n" + scanner.readLine();
            } else {
                break;
            }
        }
        return this.buildListHtml(list_lines, 1);
    }
    /**
     * Emits one list level from a run of list lines, recursing on the
     * deeper-marked lines that follow a line so they become its nested
     * list; the marker character at this depth sets numbered or bulleted.
     *
     * @param {Array} list_lines the run of list lines, each marker and text
     * @param {number} base_depth the depth of the level being emitted
     * @return {string} the html for this list level and those under it
     */
    buildListHtml(list_lines, base_depth)
    {
        var marker = list_lines[0]["marker"];
        var at_depth = marker.charAt(base_depth - 1);
        var tag = (at_depth === "#") ? "ol" : "ul";
        var html = "<" + tag + ">\n";
        var count = list_lines.length;
        var index = 0;
        while (index < count) {
            var next = index + 1;
            while (next < count &&
                list_lines[next]["marker"].length > base_depth) {
                next++;
            }
            html += "<li>" + ((wiki_preview_marks_lines &&
                list_lines[index]["began"]) ?
                "<span class='wiki-line' id='wiki-line-" +
                list_lines[index]["began"] + "' data-line='" +
                list_lines[index]["began"] + "'></span>" : "") +
                (list_lines[index]["held"] ?
                list_lines[index]["held"] :
                this.renderInline(list_lines[index]["text"]));
            if (next > index + 1) {
                html += "\n" + this.buildListHtml(list_lines.slice(
                    index + 1, next), base_depth + 1);
            }
            html += "</li>\n";
            index = next;
        }
        return html + "</" + tag + ">\n";
    }
    /**
     * Reads a run of inline text, turning nowiki and math spans, code
     * backticks, allowed inline tags, inline templates, emphasis, and
     * links into html and escaping everything else, so a block's text
     * carries its inline markup.
     *
     * @param {string} text the run of inline text
     * @return {string} the html for it
     */
    renderInline(text)
    {
        this.parse_depth++;
        if (this.parse_depth > WikiParser.WIKI_MAX_PARSE_DEPTH) {
            this.parse_depth--;
            return this.escapeText(text);
        }
        var html = "";
        var length = text.length;
        var index = 0;
        var saved_absent = this.inline_absent;
        this.inline_absent = {};
        while (index < length) {
            if (this.extra_rules.length > 0) {
                var rule_result = this.applyExtraRules(text, index);
                if (rule_result !== null) {
                    html += rule_result["html"];
                    index = rule_result["next"];
                    continue;
                }
            }
            var nowiki_open = "<nowiki>";
            var nowiki_close = "</nowiki>";
            if (text.substr(index, nowiki_open.length) === nowiki_open) {
                var start = index + nowiki_open.length;
                var close = this.findMark(text, nowiki_close, start);
                if (close !== -1) {
                    html += this.escapeVerbatim(text.slice(start, close));
                    index = close + nowiki_close.length;
                    continue;
                }
            }
            if (text.charAt(index) === "<") {
                var inline_tag = this.matchInlineTag(text, index);
                if (inline_tag !== null) {
                    html += inline_tag;
                    index += inline_tag.length;
                    continue;
                }
            }
            var math_open = "<math>";
            var math_close = "</math>";
            if (text.substr(index, math_open.length) === math_open) {
                var math_start = index + math_open.length;
                var math_end = this.findMark(text, math_close, math_start);
                if (math_end !== -1) {
                    html += "`" + this.escapeText(text.slice(math_start,
                        math_end)) + "`";
                    index = math_end + math_close.length;
                    continue;
                }
            }
            if (text.charAt(index) === "`") {
                var tick = this.findMark(text, "`", index + 1);
                if (tick !== -1) {
                    html += "`" + this.escapeText(text.slice(index + 1,
                        tick)) + "`";
                    index = tick + 1;
                    continue;
                }
            }
            if (text.substr(index, 2) === "{{") {
                var inline = this.readInlineTemplate(text, index);
                if (inline !== null) {
                    html += inline["html"];
                    index = inline["next"];
                    continue;
                }
            }
            var emphasis = this.readEmphasis(text, index);
            if (emphasis !== null) {
                html += emphasis["html"];
                index = emphasis["next"];
                continue;
            }
            if (text.substr(index, 2) === "[[") {
                var link_close = this.findMark(text, "]]", index + 2);
                if (link_close !== -1) {
                    html += this.renderLink(text.slice(index + 2,
                        link_close));
                    index = link_close + 2;
                    continue;
                }
            }
            html += this.escapeText(text.charAt(index));
            index++;
        }
        this.inline_absent = saved_absent;
        this.parse_depth--;
        return html;
    }
    /**
     * Reads one of the plain inline html tags the parser passes through
     * unchanged, such as a bold, italic, or break tag, when one starts at
     * the given position. Only the short allowed list is passed through;
     * the caller escapes anything else.
     *
     * @param {string} text the block text being scanned
     * @param {number} index the position of the opening angle bracket
     * @return {(string|null)} the tag text to pass through, or null when no
     *      allowed inline tag starts here
     */
    matchInlineTag(text, index)
    {
        var length = text.length;
        var cursor = index;
        if (cursor >= length || text.charAt(cursor) !== "<") {
            return null;
        }
        cursor++;
        if (cursor < length && text.charAt(cursor) === "/") {
            cursor++;
        }
        var name_start = cursor;
        while (cursor < length && isAlphaChar(text.charAt(cursor))) {
            cursor++;
        }
        var name = text.slice(name_start, cursor).toLowerCase();
        if (WikiParser.INLINE_TAGS.split("|").indexOf(name) === -1) {
            return null;
        }
        while (cursor < length && isWhitespaceChar(text.charAt(cursor))) {
            cursor++;
        }
        if (cursor < length && text.charAt(cursor) === "/") {
            cursor++;
        }
        if (cursor >= length || text.charAt(cursor) !== ">") {
            return null;
        }
        cursor++;
        return text.slice(index, cursor);
    }
    /**
     * Reads a bold, italic, or bold-italic span if one starts at the given
     * position. Bold-italic is five quotes, bold three, italic two; the
     * span runs to the next matching run of quotes and its body is parsed
     * for inline markup in turn.
     *
     * @param {string} text the block text being scanned
     * @param {number} index the position to look at
     * @return {(Object|null)} the span's html and the position after it, or
     *      null when no emphasis span starts here
     */
    readEmphasis(text, index)
    {
        var forms = [["'''''", "<b><i>", "</i></b>"],
            ["'''", "<b>", "</b>"], ["''", "<i>", "</i>"]];
        for (var form = 0; form < forms.length; form++) {
            var mark = forms[form][0];
            var width = mark.length;
            if (text.substr(index, width) !== mark) {
                continue;
            }
            var close = this.findMark(text, mark, index + width);
            if (close === -1) {
                continue;
            }
            var inner = text.slice(index + width, close);
            return {html: forms[form][1] + this.renderInline(inner) +
                forms[form][2], next: close + width};
        }
        return null;
    }
    /**
     * Renders one link between double brackets. A two-part link is
     * page|shown; a three-part link is relationship|page|shown and points
     * at the page, its middle part. A target on the scheme allowlist or a
     * same-page anchor is used as written; a group@page target becomes an
     * at-marker the view resolves to that group's read url; any other
     * target is treated as a page name in this group and joined to the base
     * address, so a scheme such as javascript cannot become an active url.
     *
     * @param {string} inner the text between the double brackets
     * @return {string} the html anchor for the link
     */
    renderLink(inner)
    {
        var parts = inner.split("|");
        var target;
        var shown;
        if (parts.length === 3) {
            target = trim(parts[1]);
            shown = parts[2];
        } else {
            var bar = inner.indexOf("|");
            if (bar === -1) {
                target = trim(inner);
                shown = inner;
            } else {
                target = trim(inner.slice(0, bar));
                shown = inner.slice(bar + 1);
            }
        }
        var scheme = this.linkScheme(target);
        var href;
        if (target.length > 0 && target.charAt(0) === "#") {
            href = target;
        } else if (WikiParser.ALLOWED_LINK_SCHEMES.indexOf(scheme) !== -1) {
            href = target;
        } else if (target.indexOf("@") !== -1) {
            href = "@@" + target + "@@";
        } else {
            href = this.base_address +
                this.linkPageAndLocale(target);
        }
        return "<a href=\"" + this.escapeText(href) + "\">" +
            this.renderInline(shown) + "</a>";
    }
    /*
     * Reads a wiki link target and gives back the address fields for
     * it. A writer may say which language of a page they mean by
     * writing a question mark and the language after the page name, as
     * in Endorsements?vi-VN or Endorsements?l=vi-VN. A page has a copy
     * in each language, so without this the whole of that text was
     * taken for the name of a page and no page answered to it.
     *
     * @param {string} target what a link names, which may carry a
     *      language after a question mark
     * @return {string} the page and, where one was named, its language
     */
    linkPageAndLocale(target)
    {
        var asked_at = target.indexOf("?");
        if (asked_at === -1) {
            return target;
        }
        var name = target.substring(0, asked_at);
        var said = target.substring(asked_at + 1);
        if (said.indexOf("l=") === 0) {
            said = said.substring(2);
        } else if (said.indexOf("page_locale=") === 0) {
            said = said.substring("page_locale=".length);
        }
        if (said === "" || !(/^[a-zA-Z\-_]{2,10}$/).test(said)) {
            return target;
        }
        return name + "[{locale}]" + encodeURIComponent(said);
    }
    /**
     * Reads a link target's uri scheme, the name and colon that can lead a
     * web address such as the leading part of an https address. A scheme
     * starts with a letter and may carry letters, digits, and a few
     * punctuation marks before its colon.
     *
     * @param {string} target the link target text
     * @return {string} the lower-case scheme, or the empty string when the
     *      target does not start with one
     */
    linkScheme(target)
    {
        var length = target.length;
        if (length === 0 || !isAlphaChar(target.charAt(0))) {
            return "";
        }
        var cursor = 1;
        while (cursor < length) {
            var character = target.charAt(cursor);
            if (isAlnumChar(character) || character === "+" ||
                character === "." || character === "-") {
                cursor++;
            } else {
                break;
            }
        }
        if (cursor < length && target.charAt(cursor) === ":") {
            return target.slice(0, cursor).toLowerCase();
        }
        return "";
    }
    /**
     * Escapes text so any html-special character is shown literally. An
     * entity already written by hand is left as it is rather than escaped
     * a second time, so it shows the character it stands for.
     *
     * @param {string} text the text to escape
     * @return {string} the escaped text
     */
    escapeText(text)
    {
        return htmlSpecialChars(text, false);
    }
    /**
     * Escapes verbatim text shown exactly as typed, and additionally
     * breaks up the opener of a display-time token so a token shown as an
     * example is not swapped for its widget when the page is drawn.
     *
     * @param {string} text the verbatim text to escape
     * @return {string} the escaped text with any token opener broken up
     */
    escapeVerbatim(text)
    {
        /* The opening parentheses of a resource are written as an entity
           for the same reason the opening brace of a token is: text kept
           verbatim is looked at again later for resources and tokens, and
           without this a resource shown as an example would be drawn
           instead of shown. It reads the same on screen either way. */
        return this.escapeText(text).replace(/\[\{/g, "[&#123;").replace(
            /\(\(/g, "(&#40;");
    }
    /**
     * Reads a template that sits inline in running text. The template
     * branches (toggle, citation, style span, search box, forms) are
     * ported after corpus parity is reached; the mediawiki corpus uses no
     * inline template, so returning null here gives the same result the
     * the parser does when it finds none, letting the caller show the braces
     * as text.
     *
     * @param {string} text the block text being scanned
     * @param {number} index the position of the opening double brace
     * @return {(Object|null)} the template result, or null
     */
    /**
     * Reads a template that sits inline in running text: a toggle link, a
     * citation footnote, a class, id, or style span, a search box, or a
     * form. Returns null for a double brace that starts some other
     * template, which the caller then leaves as text.
     *
     * @param {string} text the block text being scanned
     * @param {number} index the position of the opening double brace
     * @return {(Object|null)} the template's html and the position after
     *      it, or null when it is not an inline template
     */
    readInlineTemplate(text, index)
    {
        if (this.findMark(text, "}}", index + 2) === -1) {
            return null;
        }
        var close = this.matchBraces(text, index);
        if (close === false) {
            return null;
        }
        var inner = text.slice(index + 2, close);
        var next = close + 2;
        var head = this.readTemplateHead(inner);
        var name = head["name"];
        var separator = head["separator"];
        var rest = head["rest"];
        var lower = name.toLowerCase();
        if (separator === "|" && name === "toggle") {
            var bar = rest.indexOf("|");
            if (bar !== -1) {
                return {html: "<a href=\"javascript:toggleDisplay('" +
                    this.escapeText(trim(rest.slice(0, bar))) + "')\">" +
                    this.renderInline(rest.slice(bar + 1)) + "</a>",
                    next: next};
            }
        }
        if (separator === "|" && (lower.indexOf("cite") === 0 ||
            lower.indexOf("vcite") === 0)) {
            return {html: this.citeMarker(rest), next: next};
        }
        if ((separator === "=" || separator === ":") &&
            (name === "class" || name === "id" || name === "style")) {
            var parsed = this.readQuotedValue(rest);
            if (parsed !== null) {
                return {html: "<span " + name + "=\"" +
                    this.escapeText(parsed["value"]) + "\">" +
                    this.renderInline(parsed["content"]) + "</span>",
                    next: next};
            }
        }
        if (separator === ":" && lower === "search") {
            var token = this.searchWidgetToken(rest);
            if (token !== null) {
                return {html: token, next: next};
            }
        }
        var form = this.readFormTemplate(inner);
        if (form !== null) {
            return {html: form, next: next};
        }
        return null;
    }
    /**
     * Turns the body of a search tag into a deferred search-box token,
     * left for the view to fill in when the page is shown, since a library
     * parser has no page address or button helpers. Returns null when the
     * three parts are not all present.
     *
     * @param {string} rest the tag body after the search word
     * @return {(string|null)} the search token, or null when malformed
     */
    searchWidgetToken(rest)
    {
        var parts = rest.split("|");
        if (parts.length < 3) {
            return null;
        }
        var its = trim(parts[0]);
        var size = this.afterFirstColon(parts[1]);
        var placeholder = this.afterFirstColon(parts[2]);
        if (its === "" || size === "" || placeholder === "") {
            return null;
        }
        return "[{search|" + its + "|" + size + "|" + placeholder + "}]";
    }
    /**
     * Returns the text after the first colon in a string, trimmed, or the
     * whole trimmed string when there is no colon.
     *
     * @param {string} part the tag part to read
     * @return {string} the value after the first colon
     */
    afterFirstColon(part)
    {
        var colon = part.indexOf(":");
        if (colon === -1) {
            return trim(part);
        }
        return trim(part.slice(colon + 1));
    }
    /**
     * Reads a wiki table from its opening brace-bar line through its
     * closing bar-brace line. A plus line gives the caption, a dash line
     * starts a row, a bang line holds header cells, and a bar line holds
     * data cells; only the table's class and style survive.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening table line
     * @return {string} the table html
     */
    parseTable(scanner)
    {
        var open = scanner.readLine();
        var attributes = trim(open.slice(2));
        var caption = null;
        var rows = [];
        var cells = null;
        while (!scanner.atEnd()) {
            var line = scanner.readLine();
            if (line.slice(0, 2) === "|}") {
                break;
            }
            if (line.slice(0, 2) === "|+") {
                caption = trim(line.slice(2));
            } else if (line.slice(0, 2) === "|-") {
                if (cells !== null) {
                    rows.push(cells);
                }
                cells = [];
                cells.began = (!wiki_preview_marks_lines) ? 0 :
                    scanner.source_text().slice(0,
                    scanner.position).split("\n").length;
            } else if (line !== "" &&
                (line.charAt(0) === "!" || line.charAt(0) === "|")) {
                if (cells === null) {
                    cells = [];
                }
                var split = this.splitTableCells(line);
                for (var split_cell of split) {
                    cells.push(split_cell);
                }
            } else if (cells !== null && cells.length > 0) {
                var last = cells.length - 1;
                cells[last]["text"] += "\n" + line;
            }
        }
        if (cells !== null) {
            rows.push(cells);
        }
        var html = "<table" + this.safeTableAttributes(attributes) + ">\n";
        if (caption !== null) {
            html += "<caption>" + this.renderInline(caption) +
                "</caption>\n";
        }
        for (var row of rows) {
            html += "<tr>";
            if (wiki_preview_marks_lines && row.began) {
                html += "<span class='wiki-line' id='wiki-line-" +
                    row.began + "' data-line='" + row.began +
                    "'></span>";
            }
            for (var cell of row) {
                var tag = cell["header"] ? "th" : "td";
                html += "<" + tag + cell["attributes"] + ">" +
                    (this.readSameUnitText(cell["text"]) ||
                    this.renderInline(cell["text"])) + "</" + tag + ">";
            }
            html += "</tr>\n";
        }
        return html + "</table>\n";
    }
    /**
     * Reads the leading run of a cell as its attributes when that run
     * begins with one or more safe name-value pairs, returning the
     * attribute string and how many leading characters were attributes.
     *
     * @param {string} text the text before a cell's first single bar
     * @return {Object} the safe attributes under text and the count of
     *      leading characters that were attributes under length
     */
    readCellAttributes(text)
    {
        var allowed = ["align", "valign", "style", "class", "colspan",
            "rowspan", "scope", "width", "height", "bgcolor", "id"];
        var result = "";
        var length = text.length;
        var index = 0;
        var consumed = 0;
        while (index < length) {
            while (index < length && isWhitespaceChar(text.charAt(index))) {
                index++;
            }
            var start = index;
            while (index < length && (isAlphaChar(text.charAt(index)) ||
                text.charAt(index) === "-")) {
                index++;
            }
            var name = text.slice(start, index).toLowerCase();
            var after = index;
            while (after < length && isWhitespaceChar(text.charAt(after))) {
                after++;
            }
            if (name === "" || after >= length ||
                text.charAt(after) !== "=") {
                break;
            }
            after++;
            while (after < length && isWhitespaceChar(text.charAt(after))) {
                after++;
            }
            if (after >= length || (text.charAt(after) !== "\"" &&
                text.charAt(after) !== "'")) {
                break;
            }
            var quote = text.charAt(after);
            var value_start = after + 1;
            var end = text.indexOf(quote, value_start);
            if (end === -1) {
                break;
            }
            if (allowed.indexOf(name) !== -1) {
                result += " " + name + "=\"" +
                    this.escapeText(text.slice(value_start, end)) + "\"";
            }
            index = end + 1;
            consumed = index;
        }
        return {text: result, length: consumed};
    }
    /**
     * Splits one table line into its cells. A double bang starts another
     * header cell and a bar, single or double, starts a data cell. A bar
     * inside a wiki link or a nowiki span is part of that cell, not a
     * divider. A safe run of attributes at a cell's wall is kept.
     *
     * @param {string} line the cell line, opening with a bang or a bar
     * @return {Array} the cells, each a header flag, text, and attributes
     */
    splitTableCells(line)
    {
        var cells = [];
        var header = (line.charAt(0) === "!");
        var rest = line.slice(1);
        var current = "";
        var index = 0;
        var length = rest.length;
        var link_depth = 0;
        /* A file named on a page carries a bar of its own, between what
           it is called and what it is described as, so the depth of
           such a naming is followed the way a link's is and a bar
           inside one does not end a cell. */
        var resource_depth = 0;
        var in_nowiki = false;
        var attributes = "";
        var attr_done = false;
        while (index < length) {
            if (!in_nowiki && rest.startsWith("<nowiki>", index)) {
                in_nowiki = true;
                current += "<nowiki>";
                index += 8;
                continue;
            }
            if (in_nowiki && rest.startsWith("</nowiki>", index)) {
                in_nowiki = false;
                current += "</nowiki>";
                index += 9;
                continue;
            }
            if (!in_nowiki && link_depth === 0 && resource_depth === 0) {
                var pair = rest.substr(index, 2);
                if (pair === "((") {
                    resource_depth++;
                    current += "((";
                    index += 2;
                    continue;
                }
                if (pair === "[[") {
                    link_depth++;
                    current += "[[";
                    index += 2;
                    continue;
                }
                if (pair === "!!" || pair === "||") {
                    cells.push({header: header, text: trim(current),
                        attributes: attributes});
                    header = (pair === "!!");
                    current = "";
                    attributes = "";
                    attr_done = false;
                    index += 2;
                    continue;
                }
                if (rest.charAt(index) === "|") {
                    if (!attr_done) {
                        var parsed = this.readCellAttributes(current);
                        if (parsed["text"] !== "") {
                            attributes = parsed["text"];
                            attr_done = true;
                            current = current.slice(parsed["length"]);
                            index++;
                            continue;
                        }
                    }
                    cells.push({header: header, text: trim(current),
                        attributes: attributes});
                    header = false;
                    attributes = "";
                    attr_done = false;
                    current = "";
                    index++;
                    continue;
                }
            }
            if (!in_nowiki && resource_depth > 0 &&
                rest.startsWith("))", index)) {
                resource_depth--;
                current += "))";
                index += 2;
                continue;
            }
            if (!in_nowiki && link_depth > 0 &&
                rest.startsWith("]]", index)) {
                link_depth--;
                current += "]]";
                index += 2;
                continue;
            }
            current += rest.charAt(index);
            index++;
        }
        cells.push({header: header, text: trim(current),
            attributes: attributes});
        return cells;
    }
    /**
     * Pulls just the class and style out of a table's attribute text and
     * returns them as an escaped attribute string, dropping anything else.
     *
     * @param {string} attributes the raw attribute text after the {|
     * @return {string} a leading-space attribute string, or empty
     */
    safeTableAttributes(attributes)
    {
        var safe = "";
        var css_class = this.extractQuotedAttribute(attributes, "class");
        if (css_class !== null) {
            safe += " class=\"" + this.escapeText(css_class) + "\"";
        }
        var style = this.extractQuotedAttribute(attributes, "style");
        if (style !== null) {
            safe += " style=\"" + this.escapeText(style) + "\"";
        }
        return safe;
    }
    /**
     * Pulls the double-quoted value of a named attribute out of a run of
     * attribute text, matching the name without regard to case.
     *
     * @param {string} attributes the raw attribute text to search
     * @param {string} name the attribute name to look for, in lower case
     * @return {(string|null)} the value between the quotes, or null
     */
    extractQuotedAttribute(attributes, name)
    {
        var lower = attributes.toLowerCase();
        var length = attributes.length;
        var name_length = name.length;
        var offset = 0;
        var found = lower.indexOf(name, offset);
        while (found !== -1) {
            var cursor = found + name_length;
            while (cursor < length &&
                isWhitespaceChar(attributes.charAt(cursor))) {
                cursor++;
            }
            if (cursor < length && attributes.charAt(cursor) === "=") {
                cursor++;
                while (cursor < length &&
                    isWhitespaceChar(attributes.charAt(cursor))) {
                    cursor++;
                }
                if (cursor < length && attributes.charAt(cursor) === "\"") {
                    cursor++;
                    var close = attributes.indexOf("\"", cursor);
                    if (close !== -1) {
                        return attributes.slice(cursor, close);
                    }
                }
            }
            offset = found + 1;
            found = lower.indexOf(name, offset);
        }
        return null;
    }
    /**
     * Removes nowiki tags from preformatted text while keeping the
     * characters they wrap; an opener with no closer is left as written.
     *
     * @param {string} text the preformatted text that may hold nowiki
     * @return {string} the text with matched nowiki tags removed
     */
    stripNowiki(text)
    {
        var open = "<nowiki>";
        var close = "</nowiki>";
        var result = "";
        var index = 0;
        var length = text.length;
        while (index < length) {
            if (text.startsWith(open, index)) {
                var end = text.indexOf(close, index + open.length);
                if (end !== -1) {
                    result += text.slice(index + open.length, end);
                    index = end + close.length;
                    continue;
                }
            }
            result += text.charAt(index);
            index++;
        }
        return result;
    }
    /**
     * Reads a pre block through its closing tag and emits it as
     * preformatted text shown exactly as typed; a nowiki span inside has
     * its tags dropped and its characters kept.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening pre tag
     * @return {string} the pre block html
     */
    parsePre(scanner)
    {
        return this.parseVerbatimBlock(scanner, "pre");
    }
    /**
     * Reads a code block, from its opening code tag through its closing
     * one however many lines it spans, and emits it as code shown exactly
     * as typed. A wiki author uses it to show an example whose own lines,
     * such as a user-agent string laid out over several lines, should be
     * kept together and not read as wiki markup. It reads the same way a
     * pre block does, so a nowiki span inside has its tags dropped and its
     * characters kept and a closing code tag inside such a span does not
     * end the block.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening code tag
     * @return {string} the code block html
     */
    parseCodeBlock(scanner)
    {
        return this.parseVerbatimBlock(scanner, "code");
    }
    /**
     * Reads a verbatim block wrapped in a named tag, either pre or code,
     * from just after its opening tag through its closing tag however many
     * lines it spans, and emits it wrapped in that same tag with its text
     * shown exactly as typed. A nowiki span inside has its tags dropped and
     * its characters kept; a closing tag that falls inside such a span does
     * not end the block. Sharing one reader keeps pre and code identical
     * except for the tag they carry.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening tag
     * @param {string} tag the tag that opens and closes the block, "pre"
     *      or "code"
     * @return {string} the block html wrapped in that tag
     */
    parseVerbatimBlock(scanner, tag)
    {
        var began = (!wiki_preview_marks_lines) ? 0 :
            scanner.source_text().slice(0, scanner.position).split(
            "\n").length + this.line_offset;
        var open = "<" + tag + ">";
        var close = "</" + tag + ">";
        scanner.advance(open.length);
        var body = "";
        var nowiki_depth = 0;
        while (!scanner.atEnd()) {
            if (nowiki_depth === 0 && scanner.startsWith(close)) {
                scanner.advance(close.length);
                break;
            }
            if (scanner.startsWith("<nowiki>")) {
                nowiki_depth++;
                body += "<nowiki>";
                scanner.advance("<nowiki>".length);
                continue;
            }
            if (nowiki_depth > 0 && scanner.startsWith("</nowiki>")) {
                nowiki_depth--;
                body += "</nowiki>";
                scanner.advance("</nowiki>".length);
                continue;
            }
            body += scanner.peek();
            scanner.advance();
        }
        var shown = this.escapeVerbatim(this.stripNowiki(body));
        if (wiki_preview_marks_lines && began) {
            var pieces = shown.split("\n");
            shown = "";
            for (var index = 0; index < pieces.length; index++) {
                shown += "<span class='wiki-line' id='wiki-line-" +
                    (began + index) + "' data-line='" +
                    (began + index) + "'></span>" + pieces[index];
                if (index < pieces.length - 1) {
                    shown += "\n";
                }
            }
        }
        return "<" + tag + ">" + shown + "</" + tag + ">\n";
    }
    /**
     * Reads a run of lines that each open with a space, the shorthand for
     * preformatted text, and emits them as one pre block.
     *
     * @param {MarkUpScanner} scanner the scanner at the first spaced line
     * @return {string} the pre block html
     */
    parseSpacePre(scanner)
    {
        var began = (!wiki_preview_marks_lines) ? 0 :
            scanner.source_text().slice(0, scanner.position).split(
            "\n").length + this.line_offset;
        var lines = [];
        while (!scanner.atEnd() && scanner.peek() === " " &&
            !scanner.atBlankLine()) {
            lines.push(scanner.readLine().slice(1));
        }
        var shown = this.escapeVerbatim(
            this.stripNowiki(lines.join("\n")));
        if (wiki_preview_marks_lines && began) {
            var pieces = shown.split("\n");
            shown = "";
            for (var index = 0; index < pieces.length; index++) {
                shown += "<span class='wiki-line' id='wiki-line-" +
                    (began + index) + "' data-line='" +
                    (began + index) + "'></span>" + pieces[index];
                if (index < pieces.length - 1) {
                    shown += "\n";
                }
            }
        }
        return "<pre>" + shown + "</pre>\n";
    }
    /**
     * Reads a notoc region and emits its lines parsed as usual except that
     * no heading inside is added to the contents box.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening notoc tag
     * @return {string} the html for the region's contents
     */
    parseNotocRegion(scanner)
    {
        var open = "<notoc>";
        var close = "</notoc>";
        var line = scanner.readLine();
        var content = line.slice(line.indexOf(open) + open.length);
        var end = content.indexOf(close);
        if (end !== -1) {
            content = content.slice(0, end);
        } else {
            while (!scanner.atEnd()) {
                line = scanner.readLine();
                end = line.indexOf(close);
                if (end !== -1) {
                    content += "\n" + line.slice(0, end);
                    break;
                }
                content += "\n" + line;
            }
        }
        var was = this.collecting_headings;
        this.collecting_headings = false;
        var began = (!wiki_preview_marks_lines) ? 1 :
            scanner.source_text().slice(0, scanner.position).split(
            "\n").length + this.line_offset;
        var inside = new MarkUpScanner(content,
            WikiParser.WIKI_BLOCK_START_CHARS);
        /* The reader for what a template holds counts from that text,
           so the lines it stamps are moved on by where the template
           itself began in the page. */
        var held_from = this.line_offset;
        this.line_offset = began - 1;
        var html = this.parseBlocks(inside);
        this.line_offset = held_from;
        this.collecting_headings = was;
        return html;
    }
    /**
     * Reads a block template that opens with a double brace: a wrapped
     * block, an alignment or attribute wrapper, a transclusion note, or a
     * form. Returns null, leaving the scanner untouched, when the braces do
     * not form a block template.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening double brace
     * @return {(string|null)} the template html, or null
     */
    parseTemplate(scanner)
    {
        var mark = scanner.tell();
        var block = this.parseWrappedTemplate(scanner);
        if (block !== null) {
            return block;
        }
        var began = (!wiki_preview_marks_lines) ? 1 :
            scanner.source_text().slice(0, scanner.position).split(
            "\n").length + this.line_offset;
        var inner = scanner.matchBraces();
        if (inner === false) {
            scanner.seek(mark);
            return null;
        }
        var trailing = trim(scanner.readLine());
        var node = this.readBlockTemplate(inner);
        if (node !== null) {
            /* A form field with words after it on the same line is drawn
               and the words kept, which is what the site does. Anything
               else with words after it is left alone. */
            if (trailing !== "" && node["type"] === "html") {
                return rtrim(node["html"]) + this.renderInline(trailing) +
                    "\n";
            }
            if (trailing !== "") {
                scanner.seek(mark);
                return null;
            }
            if (node["type"] === "html") {
                return node["html"];
            }
            var was = this.collecting_headings;
            this.collecting_headings = false;
            var content = new MarkUpScanner(node["content"],
                WikiParser.WIKI_BLOCK_START_CHARS);
            /* The reader built here counts from the text the template
               holds, so the lines its blocks are stamped with are
               moved on by where that text began in the page. */
            var held_from = this.line_offset;
            this.line_offset = began - 1;
            var inside = this.parseBlocks(content);
            this.line_offset = held_from;
            this.collecting_headings = was;
            return "<" + node["tag"] + node["attributes"] + ">\n" +
                inside + "</" + node["tag"] + ">\n";
        }
        var form = this.readFormTemplate(inner);
        if (form !== null) {
            var tail = (trailing === "") ? "" :
                this.renderInline(trailing);
            if (form === "" && tail === "") {
                return "";
            }
            return form + tail + "\n";
        }
        scanner.seek(mark);
        return null;
    }
    /**
     * Reads the opening line of a block or inline-block wrapper template,
     * written as a block or inblock keyword with an id and style. Returns
     * null when the line is not a wrapper opening.
     *
     * @param {string} line the line to read
     * @return {(Object|null)} the keyword, id, and style, or null
     */
    matchWrappedTemplateOpen(line)
    {
        var trimmed = rtrim(line);
        if (trimmed.slice(0, 2) !== "{{" || trimmed.slice(-2) !== "}}") {
            return null;
        }
        var inner = trimmed.slice(2, trimmed.length - 2);
        var parts = inner.split("|");
        if (parts.length !== 3) {
            return null;
        }
        var keyword = parts[0];
        var id = parts[1];
        var style = parts[2];
        if (keyword !== "block" && keyword !== "inblock") {
            return null;
        }
        if (id === "" || id.indexOf("}") !== -1 ||
            style.indexOf("}") !== -1) {
            return null;
        }
        return {keyword: keyword, id: id, style: style};
    }
    /**
     * Reads the block-and-end-block or inblock form, wrapping the lines up
     * to a matching end marker in a div or span. Returns null when the
     * current line is not one of these openers.
     *
     * @param {MarkUpScanner} scanner the scanner at the opening double brace
     * @return {(string|null)} the wrapped html, or null
     */
    parseWrappedTemplate(scanner)
    {
        var mark = scanner.tell();
        var line = scanner.readLine();
        var open = this.matchWrappedTemplateOpen(line);
        if (open === null) {
            scanner.seek(mark);
            return null;
        }
        var tag = (open["keyword"] === "inblock") ? "span" : "div";
        var end_marker = "{{end-" + open["keyword"] + "}}";
        var began = (!wiki_preview_marks_lines) ? 1 :
            scanner.source_text().slice(0, scanner.position).split(
            "\n").length + this.line_offset;
        var collected = "";
        while (!scanner.atEnd()) {
            line = scanner.readLine();
            if (rtrim(line) === end_marker) {
                break;
            }
            collected += (collected === "" ? "" : "\n") + line;
        }
        var was = this.collecting_headings;
        this.collecting_headings = false;
        var content = new MarkUpScanner(collected,
            WikiParser.WIKI_BLOCK_START_CHARS);
        /* The reader built here counts from the text the template
           holds, so the lines its blocks are stamped with are moved
           on by where that text began in the page. */
        var held_from = this.line_offset;
        this.line_offset = began - 1;
        var inside = this.parseBlocks(content);
        this.line_offset = held_from;
        this.collecting_headings = was;
        return "<" + tag + " id=\"" + this.escapeText(open["id"]) +
            "\" style=\"" + this.escapeText(open["style"]) + "\">\n" +
            inside + "</" + tag + ">\n";
    }
    /*
     * Whether the block coming next stamps its own lines, so that no
     * stamp is put before it. A paragraph, a list, a table and both
     * forms of preformatted text each stamp their lines; a heading is
     * one line, and a template is stamped by the blocks within it.
     *
     * @param Object scanner the reader standing at the block
     * @return {boolean} true when the block stamps its own lines
     */
    stampsItsOwnLines(scanner)
    {
        if (!this.startsBlock(scanner)) {
            return true;
        }
        var first = scanner.peek();
        if (first === "*" || first === "#" || first === " " ||
            first === "\t") {
            return true;
        }
        var ahead = scanner.source_text().slice(scanner.position,
            scanner.position + 5);
        return ahead.slice(0, 2) === "{|" ||
            ahead.slice(0, 2) === "{{" ||
            ahead.slice(0, 5) === "<pre>";
    }
    /**
     * Reads a paragraph: the first line plus any plain continuation lines,
     * stopping at a blank line or a line that opens a new block.
     *
     * @param {MarkUpScanner} scanner the scanner at the paragraph's start
     * @return {string} the paragraph html
     */
    parseParagraph(scanner)
    {
        var began = (!wiki_preview_marks_lines) ? 0 :
            scanner.source_text().slice(0, scanner.position).split(
            "\n").length + this.line_offset;
        var lines = [scanner.readLine()];
        while (!scanner.atEnd()) {
            if (!this.hasOpenNowiki(lines.join("\n")) &&
                (scanner.atBlankLine() || this.startsBlock(scanner))) {
                break;
            }
            lines.push(scanner.readLine());
        }
        if (!wiki_preview_marks_lines) {
            return "<p>" + this.renderInline(lines.join("\n")) +
                "</p>\n";
        }
        /* While a preview is being drawn, each line of the paragraph is
           preceded by a stamp saying which line of the source it came
           from, so a caret anywhere in the paragraph has a place of its
           own in the preview to be brought to. The lines are rendered
           together, as they must be for markup that runs across them,
           and the stamps are put back at the newlines afterwards. */
        var drawn = this.renderInline(lines.join("\n"));
        var stamped = "";
        var at = 0;
        var pieces = drawn.split("\n");
        for (var index = 0; index < pieces.length; index++) {
            stamped += "<span class='wiki-line' id='wiki-line-" +
                (began + index) + "' data-line='" + (began + index) +
                "'></span>" + pieces[index];
            if (index < pieces.length - 1) {
                stamped += "\n";
            }
        }
        return "<p>" + stamped + "</p>\n";
    }
    /**
     * Reports whether the gathered text has a nowiki span still open, so a
     * paragraph keeps gathering lines even past what would begin a new
     * block while example markup inside nowiki is read as literal text.
     *
     * @param {string} text the paragraph text gathered so far
     * @return {boolean} true when a nowiki span is still open
     */
    hasOpenNowiki(text)
    {
        return substrCount(text, "<nowiki>") >
            substrCount(text, "</nowiki>");
    }
    /**
     * Finds the double-brace that closes the template opening at the given
     * position, counting nested templates so an inner close does not end
     * the outer one.
     *
     * @param {string} text the text being scanned
     * @param {number} start the position of the opening double brace
     * @return {(number|boolean)} the position of the matching close, or
     *      false when there is none
     */
    matchBraces(text, start)
    {
        var depth = 0;
        var length = text.length;
        var index = start;
        while (index < length - 1) {
            var pair = text.substr(index, 2);
            if (pair === "{{") {
                depth++;
                index += 2;
            } else if (pair === "}}") {
                depth--;
                if (depth === 0) {
                    return index;
                }
                index += 2;
            } else {
                index++;
            }
        }
        return false;
    }
    /**
     * Reads the head of a template's braces: the leading name, the first
     * separator after it (a bar, an equals, or a colon), and the rest.
     *
     * @param {string} inner the text between the template's braces
     * @return {Object} the name, the separator character, and the rest
     */
    readTemplateHead(inner)
    {
        var length = inner.length;
        var index = 0;
        while (index < length && isWhitespaceChar(inner.charAt(index))) {
            index++;
        }
        var start = index;
        while (index < length &&
            "|=:".indexOf(inner.charAt(index)) === -1) {
            index++;
        }
        var separator = (index < length) ? inner.charAt(index) : "";
        var rest = (index < length) ? inner.slice(index + 1) : "";
        return {name: trim(inner.slice(start, index)),
            separator: separator, rest: rest};
    }
    /**
     * Reads a quoted value and the text that follows it, used by the
     * class, id, and style forms. Returns null when the text does not open
     * with a quote.
     *
     * @param {string} text the text after the attribute's separator
     * @return {(Object|null)} the quoted value and following content, or
     *      null
     */
    readQuotedValue(text)
    {
        /* The site stores a quote as the name that stands for it, so
           both the mark itself and that name open a value here. */
        text = String(text).replace(/&quot;/g, '"')
            .replace(/&#0?39;|&apos;/g, "'");
        var length = text.length;
        var index = 0;
        while (index < length && isWhitespaceChar(text.charAt(index))) {
            index++;
        }
        if (index >= length || (text.charAt(index) !== "\"" &&
            text.charAt(index) !== "'")) {
            return null;
        }
        var quote = text.charAt(index);
        index++;
        var start = index;
        while (index < length && text.charAt(index) !== quote) {
            index++;
        }
        if (index >= length) {
            return null;
        }
        return {value: text.slice(start, index),
            content: ltrim(text.slice(index + 1))};
    }
    /**
     * Reads a styling template's inside into a template node, or returns
     * null when it is not one this reader handles: an alignment, a class,
     * id, or style wrapper, or a see or hatnote note.
     *
     * @param {string} inner the text between the double braces
     * @return {(Object|null)} a template node, or null when unhandled
     */
    readBlockTemplate(inner)
    {
        /* Standing on its own the mark has no enclosing thing to be the
           content of, so what it holds is simply read where it stands.
           It is matched on what it opens with rather than on a name, as
           what follows the mark is text rather than a value. */
        var mark = "same-unit";
        var trimmed = inner.replace(/^\s+/, "");
        if (trimmed.slice(0, mark.length).toLowerCase() === mark &&
            (trimmed.length == mark.length ||
            /\s/.test(trimmed.charAt(mark.length)))) {
            return {"type": "template", "tag": "div",
                "attributes": " class=\"same-unit\"",
                "content": trim(trimmed.slice(mark.length))};
        }
        var head = this.readTemplateHead(inner);
        var name = head["name"];
        var separator = head["separator"];
        var rest = head["rest"];
        var lower = name.toLowerCase();
        /* A mark saying what a page is filed under shows a reader
           nothing, so it draws nothing here either. */
        if (lower === "category" && separator === "|") {
            return {"type": "html", "html": ""};
        }
        /* The places a front page holds are answered by the site from
           what the group holds at the moment a page is read, which the
           browser cannot know. Each becomes an empty box carrying the
           mark, filled in once the preview is on screen. Reading them
           here rather than searching the finished page for them is what
           keeps a mark shown inside nowiki from being drawn. */
        if ((lower === "lead-story" || lower === "category-list" ||
            lower === "category-names") && separator === "|") {
            return {"type": "html", "html":
                '<div class="front-page-waiting" data-mark="{{' +
                name + "|" + rest.replace(/"/g, "&quot;") +
                '}}"></div>'};
        }
        var alignments = {center: "center", left: "align-left",
            right: "align-right"};
        var owns = Object.prototype.hasOwnProperty;
        /* A field of a form written into a page is drawn as the site
           draws it, so a writer sees the form taking shape rather than
           the words that ask for it. The site closes such a field with a
           line of its own, so this does too. */
        if (typeof wikiFormField === "function") {
            var drawn = wikiFormField(name,
                (rest === "") ? [] : rest.split("|"));
            if (drawn !== "") {
                return {type: "html", html: drawn + "\n"};
            }
        }
        if (separator === "|" && owns.call(alignments, name)) {
            return {type: "template", tag: "div",
                attributes: " class=\"" + alignments[name] + "\"",
                content: rest};
        }
        /* The site takes block-class, block-id and block-style as well
           as the plain names, so a page written with either reads the
           same here as it does once saved. */
        var block_named = BLOCK_ATTRIBUTE_DIRECTIVES[lower];
        if ((separator === "=" || separator === ":") &&
            (name === "class" || name === "id" || name === "style" ||
            block_named !== undefined)) {
            var parsed = this.readQuotedValue(rest);
            if (parsed !== null) {
                var attribute = (block_named !== undefined) ?
                    block_named : name;
                return {type: "template", tag: "div",
                    attributes: " " + attribute + "=\"" +
                    this.escapeText(parsed["value"]) + "\"",
                    content: parsed["content"]};
            }
        }
        if (separator === "|" && (lower === "main" || lower === "see" ||
            lower === "see also")) {
            var bar = rest.indexOf("|");
            var target = trim((bar === -1) ? rest : rest.slice(0, bar));
            return {type: "html", html:
                "<div class=\"indent\">(<a href=\"" +
                this.escapeText(this.base_address + target) + "\">" +
                this.escapeText(target) + "</a>)</div>\n"};
        }
        if (separator === "|" &&
            (lower === "hatnote" || lower === "dablink")) {
            return {type: "html",
                html: "(" + this.renderInline(rest) + ")\n"};
        }
        return null;
    }
    /**
     * Reads a form template. The form templates are ported after corpus
     * parity is reached; none appear in the mediawiki corpus, so returning
     * null is the same as finding no form template and lets a
     * plain block template be read as text.
     *
     * @param {string} inner the text between the template's braces
     * @return {(string|null)} the form html or marker, or null
     */
    readFormTemplate(inner)
    {
        if (typeof wikiFormField !== "function") {
            return null;
        }
        var head = this.readTemplateHead(inner);
        if (head["separator"] !== "|" && trim(head["rest"]) !== "") {
            return null;
        }
        var parts = (trim(head["rest"]) === "") ? [] :
            head["rest"].split("|");
        var built = wikiFormField(head["name"], parts);
        return (built === "" || built === undefined) ? null : built;
    }
    /**
     * Builds the table of contents that goes above a page, or the empty
     * string when the page has too few headings. A single top-level
     * heading is the page's title and is left out.
     *
     * @param {Array} headings the page's headings, each a level and text
     * @return {string} the html contents box, or empty when not drawn
     */
    tableOfContents(headings)
    {
        if (headings.length < WikiParser.MIN_SECTIONS_FOR_TOC) {
            return "";
        }
        var top_count = 0;
        for (var i = 0; i < headings.length; i++) {
            if (headings[i]["level"] === 1) {
                top_count++;
            }
        }
        if (top_count === 1) {
            var kept = [];
            for (var j = 0; j < headings.length; j++) {
                if (headings[j]["level"] !== 1) {
                    kept.push(headings[j]);
                }
            }
            headings = kept;
        }
        if (headings.length === 0) {
            return "";
        }
        var min_level = headings[0]["level"];
        for (var k = 1; k < headings.length; k++) {
            if (headings[k]["level"] < min_level) {
                min_level = headings[k]["level"];
            }
        }
        var items = this.nestHeadings(headings, min_level);
        return "<div class=\"toc top-color\">\n" +
            this.renderContents(items) + "</div>\n";
    }
    /**
     * Nests a flat list of headings into a tree by their levels, so a
     * heading a level deeper than the one before becomes its child.
     *
     * @param {Array} headings the headings, each a level and text
     * @param {number} base_level the level of the tier being built
     * @return {Array} the heading items at this tier
     */
    nestHeadings(headings, base_level)
    {
        var items = [];
        var count = headings.length;
        var index = 0;
        while (index < count) {
            var item = {text: headings[index]["text"], sublist: null};
            var next = index + 1;
            while (next < count &&
                headings[next]["level"] > base_level) {
                next++;
            }
            if (next > index + 1) {
                item["sublist"] = this.nestHeadings(
                    headings.slice(index + 1, next), base_level + 1);
            }
            items.push(item);
            index = next;
        }
        return items;
    }
    /**
     * Renders the nested heading items into an ordered list of anchor
     * links, each pointing at the matching heading's id.
     *
     * @param {Array} items the heading items from nestHeadings
     * @return {string} the html ordered list
     */
    renderContents(items)
    {
        var html = "<ol>\n";
        for (var i = 0; i < items.length; i++) {
            html += "<li><a href=\"#" + items[i]["text"] + "\">" +
                items[i]["text"] + "</a>";
            if (items[i]["sublist"] !== null) {
                html += "\n" + this.renderContents(items[i]["sublist"]);
            }
            html += "</li>\n";
        }
        return html + "</ol>\n";
    }
    /**
     * Inserts the table of contents just before the first level-two
     * heading of the page, the spot below the page's title.
     *
     * @param {string} page the rendered page body
     * @param {string} toc the contents box html
     * @return {string} the page with the contents box inserted
     */
    insertTableOfContents(page, toc)
    {
        var pos = page.indexOf("<h2");
        if (pos !== -1) {
            var start = page.slice(0, pos);
            var end = page.slice(pos);
            page = start + toc + end;
        }
        return page;
    }
    /**
     * Turns one citation into a numbered footnote marker and files the
     * citation away for the reference list.
     *
     * @param {string} content the citation's fields, after the cite word
     * @return {string} the html footnote marker
     */
    citeMarker(content)
    {
        this.cite_references.push(content);
        var number = this.cite_references.length;
        return "<sup id=\"cite_" + number + "\"><a href=\"#ref_" +
            number + "\">[" + number + "]</a></sup>";
    }
    /**
     * Builds the reference list at the foot of a page from the citations
     * gathered while it rendered, or the empty string when there were none.
     *
     * @return {string} the html reference list, or empty
     */
    referenceList()
    {
        if (this.cite_references.length === 0) {
            return "";
        }
        var shown_fields = ["title", "author", "publisher", "journal",
            "url", "quote"];
        var html = "<ol class=\"references\">\n";
        var number = 1;
        for (var reference of this.cite_references) {
            var fields = {};
            var parts = reference.split("|");
            for (var part of parts) {
                var pair = splitLimit("=", part, 2);
                if (pair.length === 2) {
                    fields[trim(pair[0]).toLowerCase()] = trim(pair[1]);
                }
            }
            var shown = [];
            var owns = Object.prototype.hasOwnProperty;
            for (var field of shown_fields) {
                if (owns.call(fields, field)) {
                    shown.push(this.renderInline(fields[field]));
                }
            }
            html += "<li id=\"ref_" + number + "\">" +
                "<a href=\"#cite_" + number + "\">^</a> " +
                shown.join(", ") + "</li>\n";
            number++;
        }
        return html + "</ol>\n";
    }
}
/*
 * Whether the parser should stamp each block with the line of the source
 * it began on. Only a preview wants these; a page being read does not.
 */
var wiki_preview_marks_lines = false;
/*
 * How many charts a preview has drawn, so each is given a name of its own.
 */
var wiki_preview_chart_count = 0;
/*
 * The class put on a stretch of the preview that answers what is picked
 * out in the source.
 */
var WIKI_PREVIEW_MARK_CLASS = "wiki-preview-mark";
/*
 * The words a writer may put before a block to give it a class, an id or
 * a style, and the attribute each stands for. The site takes these as
 * well as the plain names, so both are read here.
 */
/* ---- markup constants, mirrored from the server class ---- */
WikiParser.MAX_HEADING_LEVEL = 6;
WikiParser.INLINE_TAGS = "tt|u|s|strike|ins|del|sub|sup|b|i|br|code";
WikiParser.MAX_INDENT_LEVEL = 4;
WikiParser.MIN_SECTIONS_FOR_TOC = 4;
WikiParser.WIKI_BLOCK_START_CHARS = "=*#:;-{<.";
/* The line that separates one slide from the next on a
   presentation page: four dots on a line of their own, the same
   mark the wiki edit bar writes and the syntax page describes. */
WikiParser.SLIDE_SEPARATOR = "....";
WikiParser.WIKI_MAX_PARSE_DEPTH = 20;
WikiParser.ALLOWED_LINK_SCHEMES = ["http", "https", "mailto", "gopher",
    "ftp"];
WikiParser.END_HEAD_VARS = "END_HEAD_VARS";
var BLOCK_ATTRIBUTE_DIRECTIVES = {"block-class": "class",
    "block-id": "id", "block-style": "style"};
/*
 * Converts yioop wiki markup to html for the help panel. The body is
 * parsed by the ported WikiParser against the reading url for this group,
 * then any cross-group marker and resource reference is turned into a link,
 * matching how the wiki view assembles a read page.
 *
 * @param String wiki_text the wiki markup to parse
 * @param String group_id the id of the group the page belongs to
 * @param String page_id the id of the page, used for resource urls
 * @param String controller_name the controller a page link should target
 * @param String csrf_token_key the query variable name for the csrf token
 * @param String csrf_token_value the csrf token value
 * @param bool pretty whether the site serves pretty addresses, since a
 *      file kept with a page is asked for as a path where they are on
 * @param String base where the site is rooted
 * @return String the parsed html
 */
function parseWikiContent(wiki_text, group_id, page_id, controller_name,
    csrf_token_key, csrf_token_value, pretty, base, draw_toc)
{
    if (!wiki_text) {
        return "";
    }
    /* a page may carry a head-variable section ended by an END_HEAD_VARS
       marker; it holds settings such as the page title, not body text, so
       drop it before parsing the body */
    var end_marker = "END_HEAD_VARS";
    var marker_at = wiki_text.indexOf(end_marker);
    if (marker_at !== -1) {
        wiki_text = wiki_text.slice(marker_at + end_marker.length);
    }
    var read_address = "?c=" + controller_name +
        "&a=wiki&arg=read&group_id=" + group_id + "&" + csrf_token_key +
        "=" + csrf_token_value + "&page_name=";
    var parser = new WikiParser(read_address);
    /* A preview shows the words a writer is typing, not the head a page
       keeps its settings in, so whether that page draws a table of
       contents has to be handed in. Left out, one is drawn, which is what
       a page does when it says nothing. */
    parser.draw_toc_asked = (draw_toc === undefined) ? true : draw_toc;
    var html = parser.parse(wiki_text, false);
    /* resolve a cross-group marker left for a group@page link into that
       group's reading url, the way the wiki view does */
    var group_address = "?c=" + controller_name +
        "&amp;a=wiki&amp;arg=read&amp;" + csrf_token_key + "=" +
        csrf_token_value + "&amp;group_name=";
    html = html.replace(/@@(.*)@(.*)@@/g, function (match, group_part,
        page_part) {
        return group_address + group_part + "&amp;page_name=" + page_part;
    });
    /* a symbol written out as its own text needs nothing from the group's
       files either: the same squares the server would draw are drawn here
       from the same arithmetic */
    html = html.replace(/\(\(resource-qr:(.+?)\|(.+?)\)\)/g,
        function (match, said, description)
        {
            var named = wikiResourceFolder("", description);
            description = named.description;
            if (typeof qrSvg !== "function") {
                return match;
            }
            let drawn = qrSvg(said);
            if (drawn === false) {
                return description;
            }
            return "<img src=\"data:image/svg+xml;base64," + btoa(drawn) +
                "\" alt=\"" + description + "\" title=\"" + description +
                "\" class=\"wiki-resource-thumb\" >";
        });
    /* a chart written out as its own points needs nothing from the group's
       files either: the points are in the markup, so the drawing is asked
       for where it stands */
    html = html.replace(
        /\(\(resource-(bar|line|point)graph:(.+?)\|(.+?)\)\)/g,
        function (match, kind, carried, description)
        {
            var named = wikiResourceFolder("", description);
            description = named.description;
            var parts = carried.split("#");
            var points = parts.slice(2);
            var described = {};
            for (var index = 0; index < points.length; index++) {
                var found = points[index].match(/^\s*\((.+)\,(.+)\)\s*$/);
                if (!found) {
                    continue;
                }
                described[found[1].trim()] = parseFloat(found[2]);
            }
            if (Object.keys(described).length == 0) {
                return match;
            }
            /* The chart is drawn from two things kept apart: the points
               themselves, and how to draw them. Handing it one object
               holding both left it with no points and drew nothing. */
            var settings = {"points": described,
                "properties": {"type": kind.charAt(0).toUpperCase() +
                kind.slice(1) + "Graph", "title": description}};
            wiki_preview_chart_count++;
            return "<div id='wiki-preview-chart-" +
                wiki_preview_chart_count + "' data-chart='" +
                JSON.stringify(settings).replace(/'/g, "&#39;") +
                "'></div>";
        });
    /* a resource written out as its own data carries everything needed to
       draw it, so it becomes the image, video, table or link it names
       without the group's files being reached for at all */
    html = html.replace(/\(\(resource-data:(.+?)\|(.+?)\)\)/g,
        function (match, carried, description)
        {
            var named = wikiResourceFolder("", description);
            description = named.description;
            var options_at = carried.indexOf("#");
            var data = (options_at >= 0) ? carried.substring(0, options_at) :
                carried;
            var options = (options_at >= 0) ?
                carried.substring(options_at + 1).split("#") : [];
            var address = "data:" + data;
            if (data.substring(0, 9) == "text/csv;") {
                return wikiCommaTable(data, options, description);
            }
            if (data.substring(0, 6) == "image/") {
                return "<img src=\"" + address + "\" alt=\"" +
                    description + "\" class=\"wiki-resource-image\" >";
            }
            if (data.substring(0, 6) == "video/") {
                return "<video style=\"width:100%\" controls=\"controls\">" +
                    "<source src=\"" + address + "\">" + description +
                    "</video>";
            }
            return "<a href=\"" + address + "\">" + description + "</a>";
        });
    /* turn a resource reference into the image, video, or link it names,
       addressed to this page's resources */
    /* a resource named as a link is always a link, whatever kind of file
       it is, and one named as a thumb is the picture drawn small */
    html = html.replace(/\(\(resource-(link|thumb|nolink):(.+?)\|(.+?)\)\)/g,
        function (match, kind, resource_name, description)
        {
            var named = wikiResourceFolder(resource_name,
                description);
            resource_name = named.name;
            description = named.description;
            var resource_url = wikiResourceUrl(group_id, page_id,
                resource_name, csrf_token_key, csrf_token_value,
                pretty, base);
            /* A file asked for as a thumb stands as the small picture
               kept beside it, inside a link to the file itself. The
               small picture is what is drawn, so a document shows its
               front page rather than a bare link. */
            if (kind === "thumb") {
                return "<a class=\"image-list\" href=\"" + resource_url +
                    "\" ><img src=\"" +
                    wikiThumbUrl(resource_url, pretty) +
                    "\" loading=\"lazy\" alt=\"" + description +
                    "\" ></a>";
            }
            /* A picture asked for without a link is drawn on its own,
               where the plain form is wrapped in a link to itself. */
            if (kind === "nolink") {
                return "<img src=\"" + resource_url + "\" loading=\"lazy\"" +
                    " alt=\"" + description + "\" class=\"photo\" >";
            }
            return "<a href=\"" + resource_url + "\" title=\"" +
                description + "\" >" + description + "</a>";
        });
    html = html.replace(/\(\(resource:(.+?)\|(.+?)\)\)/g, function (match,
        resource_name, description) {
        var named = wikiResourceFolder(resource_name, description);
        resource_name = named.name;
        description = named.description;
        var resource_url = wikiResourceUrl(group_id, page_id,
            resource_name, csrf_token_key, csrf_token_value,
            pretty, base);
        /* webp, avif and the like are pictures the site already serves
           and browsers already draw; left out of this list they were
           shown in the preview as something to download rather than as
           the picture they are. */
        if ((/\.(avif|bmp|gif|heic|heif|jpeg|jpg|png|svg|tif|tiff|webp)$/i
            ).test(resource_name)) {
            return "<img src=\"" + resource_url + "\" alt=\"" +
                description + "\" class=\"wiki-resource-image\" >";
        }
        /* A document is shown in a frame of its own, as the site shows
           one, with its description standing in where a browser will
           not draw it. */
        if ((/\.(pdf|html?)$/i).test(resource_name)) {
            return "<iframe class=\"wiki-resource-object\" src=\"" +
                resource_url + "\" >" + description + "</iframe>";
        }
        if ((/\.(avi|flv|m4v|mov|mp4|mpg|ogg|webm|wmv)$/i).test(
            resource_name)) {
            return "<video style=\"width:100%\" controls=\"controls\">" +
                "<source src=\"" + resource_url +
                "\" type=\"video/mp4\">" + description + "</video>";
        }
        return "<a href=\"" + resource_url + "\" alt=\"" + description +
            "\" >" + description + "</a>";
    });
    /* A preview shows what a reader would see, so the marks the site
       fills in when it shows a page are filled here too. */
    if (typeof fillWikiStandIns === "function") {
        html = fillWikiStandIns(html);
    }
    return html;
}
/*
 * Fills a wiki-history revision into the page in the browser instead of on
 * the server. A historical revision never changes, yet a crawler viewing it
 * would make the server re-parse the whole page every request; doing the
 * render here moves that cost off the server. A mediawiki revision is run
 * through the ported parser; a markdown one is shown as its raw source,
 * since only the mediawiki engine is ported.
 *
 * @param String target_id id of the element the revision is placed into.
 * @param String source the raw wiki source of the revision.
 * @param bool is_mediawiki whether the revision uses the mediawiki engine.
 * @param String group_id id of the group the page belongs to.
 * @param String page_id id of the page the revision belongs to.
 * @param String controller controller name the page is read through.
 * @param String csrf_key name of the anti-cross-site-request token field.
 * @param String csrf_value value of the anti-cross-site-request token.
 */
function renderWikiHistory(target_id, source, is_mediawiki, group_id,
    page_id, controller, csrf_key, csrf_value)
{
    var target = elt(target_id);
    if (!target) {
        return;
    }
    if (is_mediawiki && typeof parseWikiContent === "function") {
        target.innerHTML = parseWikiContent(source, group_id, page_id,
            controller, csrf_key, csrf_value);
    } else if (!is_mediawiki &&
        typeof parseMarkdownContent === "function") {
        /* A revision of a page written in markdown is read the same way
           the live preview reads one. */
        target.innerHTML = parseMarkdownContent(source);
    } else {
        target.textContent = source;
    }
}
/*
 * Renders the line-by-line diff of two wiki-page revisions into the element
 * named by target_id. Doing this in the browser keeps the server from
 * building a longest-common-subsequence table on every visit to a diff url.
 *
 * @param String target_id id of the element to fill with the diff
 * @param String source1 raw source of the first revision
 * @param String source2 raw source of the second revision
 * @param int max_cells largest subsequence table computed exactly; a larger
 *      differing region is searched within a band instead
 * @param int band how far a banded search may drift from the diagonal
 */
function renderWikiDiff(target_id, source1, source2, max_cells, band)
{
    var target = elt(target_id);
    if (!target) {
        return;
    }
    target.innerHTML = wikiDiff(source1, source2, max_cells, band);
}
/*
 * Computes the html for the line-by-line diff of two strings. The output
 * matches the server diff(): removed lines in red, added lines in green,
 * shared context in light gray, each hunk led by an "@@" line. Common
 * leading and trailing lines are trimmed first; the differing middle is
 * aligned with an exact table when small enough, otherwise within a band.
 *
 * @param String data1 first string to compare
 * @param String data2 second string to compare
 * @param int max_cells largest table computed exactly
 * @param int band how far a banded search may drift from the diagonal
 * @return String html describing where data1 and data2 differ
 */
function wikiDiff(data1, data2, max_cells, band)
{
    var start = "<div>", start_same = "<div class='light-gray'>",
        start1 = "<div class='red'>", start2 = "<div class='green'>",
        end = "</div>";
    var lines1 = data1.replace(/\r\n?/g, "\n").split("\n");
    var lines2 = data2.replace(/\r\n?/g, "\n").split("\n");
    var num1 = lines1.length, num2 = lines2.length;
    var shorter = Math.min(num1, num2), longer = Math.max(num1, num2);
    var first_diff = 0, head_lcs = [], i;
    while (first_diff < shorter &&
        lines1[first_diff] === lines2[first_diff]) {
        head_lcs.push([first_diff, first_diff, lines1[first_diff]]);
        first_diff++;
    }
    if (first_diff === shorter) {
        if (num1 === num2) {
            return "";
        }
        var tmp = lines1, prefix = start1 + "-";
        if (num1 === shorter) {
            tmp = lines2;
            prefix = start2 + "+";
        }
        var out = start + "@@ -" + shorter + ",0 +" + shorter + "," +
            longer + " @@" + end + "\n";
        for (i = shorter; i < longer; i++) {
            out += prefix + tmp[i] + end + "\n";
        }
        return out;
    }
    var last_diff = 0, tail_lcs = [];
    var idx1 = num1 - 1, idx2 = num2 - 1;
    while (shorter - last_diff > first_diff &&
        lines1[idx1] === lines2[idx2]) {
        tail_lcs.unshift([idx1, idx2, lines1[idx1]]);
        last_diff++;
        idx1--;
        idx2--;
    }
    var trim1 = lines1.slice(first_diff, num1 - last_diff);
    var trim2 = lines2.slice(first_diff, num2 - last_diff);
    var cells = trim1.length * trim2.length, lcs;
    if (cells <= max_cells) {
        lcs = wikiDiffLcsFull(trim1, trim2, first_diff);
    } else {
        lcs = wikiDiffLcs(trim1, trim2, first_diff, band);
    }
    lcs = head_lcs.concat(lcs, tail_lcs);
    var previous_first = -1, previous_second = -1, current_first = 0,
        current_second = 0, old_line = "", out_string = "";
    if (lcs.length === 0) {
        out_string += start + "@@ -0," + num1 + "  +0," + num2 + " @@" +
            end + "\n";
        for (i = 0; i < num1; i++) {
            out_string += start1 + "-" + lines1[i] + end + "\n";
        }
        for (i = 0; i < num2; i++) {
            out_string += start2 + "+" + lines2[i] + end + "\n";
        }
        return out_string;
    }
    for (var k = 0; k < lcs.length; k++) {
        current_first = lcs[k][0];
        current_second = lcs[k][1];
        var line = lcs[k][2];
        var gap1 = current_first - previous_first;
        var gap2 = current_second - previous_second;
        if (gap1 > 1 || gap2 > 1) {
            gap1++;
            gap2++;
            out_string += start + "@@ -" + previous_first + "," + gap1 +
                "  +" + previous_second + "," + gap2 + " @@" + end + "\n";
            out_string += start_same + " " + old_line + end + "\n";
            for (i = previous_first + 1; i < current_first; i++) {
                out_string += start1 + "-" + lines1[i] + end + "\n";
            }
            for (i = previous_second + 1; i < current_second; i++) {
                out_string += start2 + "+" + lines2[i] + end + "\n";
            }
            out_string += start_same + " " + line + end + "\n";
        }
        previous_first = current_first;
        previous_second = current_second;
        old_line = line;
    }
    if (current_first < num1 - 1 || current_second < num2 - 1) {
        out_string += start_same + " " + old_line + end + "\n";
        for (i = current_first + 1; i < num1; i++) {
            out_string += start1 + "-" + lines1[i] + end + "\n";
        }
        for (i = current_second + 1; i < num2; i++) {
            out_string += start2 + "+" + lines2[i] + end + "\n";
        }
    }
    return out_string;
}
/*
 * Computes the exact longest common subsequence of two arrays of lines with
 * the full dynamic-programming table, giving the same result the server
 * computeLCS() would but kept memory-lean for the browser: the backtrack
 * directions are held one byte per cell in a typed array, and only two rows
 * of lengths are carried at a time, so a region of a few million cells costs
 * a few megabytes and finishes well under a second. The caller reaches this
 * routine only when the region fits under the client cell ceiling; a larger
 * region uses the banded wikiDiffLcs() below instead.
 *
 * @param Array lines1 first array of lines
 * @param Array lines2 second array of lines
 * @param int offset amount added to each output line number, used because
 *      the common leading lines were trimmed before the call
 * @return Array list of [index1, index2, line] triples in order
 */
function wikiDiffLcsFull(lines1, lines2, offset)
{
    var num1 = lines1.length, num2 = lines2.length;
    if (num1 === 0 || num2 === 0) {
        return [];
    }
    var stride = num2 + 1;
    var move_diagonal = 1, move_up = 2, move_left = 3;
    var moves = new Int8Array(stride * (num1 + 1));
    var row_prev = new Int32Array(stride);
    var row_cur = new Int32Array(stride);
    var i, j;
    for (i = 1; i <= num1; i++) {
        var base = i * stride;
        row_cur[0] = 0;
        for (j = 1; j <= num2; j++) {
            if (lines1[i - 1] === lines2[j - 1]) {
                row_cur[j] = row_prev[j - 1] + 1;
                moves[base + j] = move_diagonal;
            } else if (row_prev[j] >= row_cur[j - 1]) {
                row_cur[j] = row_prev[j];
                moves[base + j] = move_up;
            } else {
                row_cur[j] = row_cur[j - 1];
                moves[base + j] = move_left;
            }
        }
        var swap = row_prev;
        row_prev = row_cur;
        row_cur = swap;
    }
    var lcs = [];
    i = num1;
    j = num2;
    while (i > 0 && j > 0) {
        var move = moves[i * stride + j];
        if (move === move_diagonal) {
            lcs.unshift([i + offset - 1, j + offset - 1, lines1[i - 1]]);
            i--;
            j--;
        } else if (move === move_up) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}
/*
 * Computes the longest common subsequence of two arrays of lines within a
 * band around the diagonal, mirroring the server computeLCS() but bounded so
 * a large region cannot slow the browser. Returns an empty list when the two
 * lengths differ by more than the band, which the caller then renders as a
 * coarse block of removals followed by additions.
 *
 * @param Array lines1 first array of lines
 * @param Array lines2 second array of lines
 * @param int offset amount added to each output line number, used because
 *      the common leading lines were trimmed before the call
 * @param int band how far the search may drift from the diagonal
 * @return Array list of [index1, index2, line] triples in order
 */
function wikiDiffLcs(lines1, lines2, offset, band)
{
    var num1 = lines1.length, num2 = lines2.length;
    if (num1 === 0 || num2 === 0 || Math.abs(num1 - num2) > band) {
        return [];
    }
    var width = 2 * band + 1;
    var val = [], moves = [], i, j;
    for (i = 0; i <= num1; i++) {
        val[i] = new Array(width).fill(0);
        moves[i] = new Array(width).fill("");
    }
    function vget(row, col_line)
    {
        if (row < 0 || col_line < 0 || row > num1) {
            return 0;
        }
        var band_col = col_line - row + band;
        if (band_col < 0 || band_col >= width) {
            return 0;
        }
        return val[row][band_col];
    }
    for (i = 1; i <= num1; i++) {
        var low = Math.max(1, i - band), high = Math.min(num2, i + band);
        for (j = low; j <= high; j++) {
            var col = j - i + band;
            if (lines1[i - 1] === lines2[j - 1]) {
                val[i][col] = vget(i - 1, j - 1) + 1;
                moves[i][col] = "d";
            } else if (vget(i - 1, j) >= vget(i, j - 1)) {
                val[i][col] = vget(i - 1, j);
                moves[i][col] = "u";
            } else {
                val[i][col] = vget(i, j - 1);
                moves[i][col] = "l";
            }
        }
    }
    var lcs = [];
    i = num1;
    j = num2;
    while (i > 0 && j > 0) {
        var back_col = j - i + band;
        if (back_col < 0 || back_col >= width) {
            break;
        }
        var move = moves[i][back_col];
        if (move === "d") {
            lcs.unshift([i + offset - 1, j + offset - 1, lines1[i - 1]]);
            i--;
            j--;
        } else if (move === "u") {
            i--;
        } else if (move === "l") {
            j--;
        } else {
            break;
        }
    }
    return lcs;
}
/*
 * Draws comma separated values written out as their own data as a table.
 * The words after the data say how to read it: noheadings means the first
 * row is values rather than column names, and a pair of cell names such as
 * B2 and C3 says which corner of the sheet to show.
 *
 * @param String data the mime type and base64 text as written
 * @param Array options the words written after the data
 * @param String description what the table is, used as its caption
 * @return String the table as markup
 */
function wikiCommaTable(data, options, description)
{
    var comma_at = data.indexOf(",");
    var written = "";
    try {
        written = atob(data.substring(comma_at + 1));
    } catch (problem) {
        return description;
    }
    /* Every line is a row, blank ones included: a blank row still counts
       when a cell is named, so dropping it would move every row under it
       up one and answer with the wrong corner of the sheet. Only a final
       empty line, which a file ending in a newline leaves behind, is not a
       row. */
    var rows = [];
    var lines = written.split("\n");
    if (lines.length > 0 && lines[lines.length - 1] === "") {
        lines.pop();
    }
    for (var index = 0; index < lines.length; index++) {
        rows.push(lines[index].replace(/\r$/, "").split(","));
    }
    var headings = true;
    var corners = [];
    for (var which = 0; which < options.length; which++) {
        if (options[which] === "noheadings") {
            headings = false;
        } else if (/^[A-Za-z]+[0-9]+$/.test(options[which])) {
            corners.push(options[which]);
        }
    }
    if (corners.length == 2) {
        var first = wikiCellPlace(corners[0]);
        var last = wikiCellPlace(corners[1]);
        var kept = [];
        for (var down = first.row; down <= last.row; down++) {
            if (rows[down] === undefined) {
                continue;
            }
            kept.push(rows[down].slice(first.column, last.column + 1));
        }
        rows = kept;
    }
    var markup = "<table class='wiki-preview-table'><caption>" +
        description + "</caption>";
    for (var down = 0; down < rows.length; down++) {
        var cell = (headings && down == 0) ? "th" : "td";
        markup += "<tr>";
        for (var across = 0; across < rows[down].length; across++) {
            markup += "<" + cell + ">" + rows[down][across] + "</" + cell +
                ">";
        }
        markup += "</tr>";
    }
    return markup + "</table>";
}
/*
 * Turns a cell name such as B2 into the row and column it names, counting
 * from zero.
 *
 * @param String named the cell name
 * @return Object the row and column it names
 */
function wikiCellPlace(named)
{
    var letters = named.match(/^[A-Za-z]+/)[0].toUpperCase();
    var column = 0;
    for (var index = 0; index < letters.length; index++) {
        column = column * 26 + (letters.charCodeAt(index) - 64);
    }
    return {row: parseInt(named.match(/[0-9]+$/)[0], 10) - 1,
        column: column - 1};
}
/*
 * Turns the search-box token the parser leaves into the box itself. The
 * parser cannot build it, having no page address to point it at, so it
 * leaves a token behind and whoever shows the page fills it in; the page
 * being shown here is the preview.
 *
 * @param String html the parsed page, holding any tokens
 * @return String the same page with each token turned into a box
 */
function fillWikiSearchBoxes(html)
{
    return html.replace(/\[\{search\|(.+?)\|(.+?)\|(.+?)\}\]/g,
        function (match, its, size, placeholder)
        {
            /* Drawn as a division rather than a form: the editor is
               itself a form, and a browser drops a form written inside
               another, which left the box's parts loose on the page. It
               is not for searching from in any case. */
            return "<div class='search-box " + size + "-search-box' >" +
                "<div class='search-box-inner' tabindex='0'>" +
                "<input type='hidden' name='its' value='" + its + "' >" +
                "<input type='text' name='q' value='' placeholder='" +
                placeholder + "' title='" + placeholder +
                "' class='search-input' >" +
                "<button type='reset' class='search-reset-button' >" +
                "<span class='icon-glyph' aria-hidden='true'>X</span>" +
                "</button>" +
                "<button type='submit' class='search-button' >" +
                "<span class='icon-glyph' aria-hidden='true'>&#128269;" +
                "</span></button>" +
                "</div></div>";
        });
}
