<?php
/**
 * 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 Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\library\wiki;

use seekquarry\yioop\configs as C;
use seekquarry\yioop\library\processors\TextProcessor;
use seekquarry\yioop\library\CrawlConstants;

/** For Yioop global defines */
require_once __DIR__."/../../configs/Config.php";
/**
 * Class with methods to parse mediawiki documents, both within Yioop, and
 * when Yioop indexes mediawiki dumps as from Wikipedia.
 *
 * @author Chris Pollett
 */
class WikiParser implements CrawlConstants
{
    /**
     * String used to separate the head variables of a Yioop wiki page from
     * the page contents.
     */
    const END_HEAD_VARS = "END_HEAD_VARS";
    /**
     * Wiki directives that wrap what follows them in a block of its own,
     * and the HTML attribute each one sets on it. Writing class or id on
     * its own wraps the content in a span, which is what is wanted in the
     * middle of a sentence; these say the content is a block instead, so
     * it is wrapped in a div wherever it appears. The name of the
     * directive is what the page author writes, and the value is what
     * the attribute is called in the HTML.
     */
    const BLOCK_ATTRIBUTE_DIRECTIVES = ["block-class" => "class",
        "block-id" => "id", "block-style" => "style"];
    /**
     * Escape string to try to prevent incorrect nesting of div for some of the
     * substitutions;
     */
    const ESC=",[}";
    /**
     * Wiki page header field used for Yioop wiki pages and the default
     * values (field => value pairs).
     */
    const PAGE_DEFAULTS = [
        'alternative_path' => '',
        'anonymous_issue_reporting' => 'moderated',
        'author' => '',
        'article_date' => '',
        'article_date_kind' => 'date',
        'banner_caption' => '',
        'banner_rights' => '',
        'default_sort' => 'aname',
        'description' => '',
        'directory_indexes' => true,
        'index_file' => 'index.html',
        'media_list_index' => false,
        'media_list_index_file' => 'index.html',
        'static_html_folder' => false,
        'page_alias' => '',
        'page_border' => 'solid',
        'page_header' => '',
        'page_footer' => '',
        'page_theme' => '',
        'page_type' => 'standard',
        'public_source' => true,
        'properties' => '',
        'robots' => '',
        'share_expires' => C\FOREVER,
        'title' => '',
        'toc' => true,
        'url_shortener' => '',
        'update_description' => false
    ];
    /**
     * Whether the parser should be configured only to do minimal substitutions
     * or all available (minimal might be used for posts in discussion groups)
     * @var bool
     */
    public $minimal;
    /**
     * Base url address to be used in urls that occur in wiki substitutions
     * @var string
     */
    public $base_address;
    /**
     * Rules a caller has added, each a callable that inspects the text at a
     * position and returns ready-made html for a construct the base parser
     * does not handle, or null. It lets dump-only markup, such as an
     * archived wiki's image links and redirects, be folded into the parse
     * so its html reaches the reader as html rather than as escaped text.
     * @var array
     */
    public $extra_rules = [];
    /**
     * Sets up a wiki parser with the base address that links resolve
     * against and whether the shorter rule set suited to discussion posts
     * is wanted.
     *
     * @param string $base_address base url for link substitutions
     * @param bool $minimal substitution list is shorter - suitable for
     *      posting to discussion
     */
    public function __construct($base_address = "", $minimal = false)
    {
        $this->minimal = $minimal;
        $this->base_address = $base_address;
    }
    /**
     * Adds a rule the parser will try before its own handling, both at the
     * start of a block and at each spot within a line. A rule is a callable
     * given the text and an offset into it; it returns an array with the
     * html to emit as-is and the offset just past what it consumed, or null
     * when it does not apply there. This is how a caller such as an
     * archived wiki reader teaches the parser constructs of its own without
     * their html being escaped as plain text.
     *
     * @param callable $rule the rule to add
     */
    public function addRule($rule)
    {
        $this->extra_rules[] = $rule;
    }
    /**
     * Tries each added rule against the text at the given offset and
     * returns the first that matches, or null when none apply. A match is
     * an array holding the html to emit as-is and the offset just past what
     * the rule used.
     *
     * @param string $text the text being read
     * @param int $index the offset to try the rules at
     * @return array|null the matching rule's result, or null
     */
    protected function applyExtraRules($text, $index)
    {
        foreach ($this->extra_rules as $rule) {
            $result = $rule($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 -- many back-ticks with no closing back-tick, say -- 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 int $from the offset to search from
     * @return int|false the marker's offset, or false when there is none
     */
    protected function findMark($text, $marker, $from)
    {
        if (isset($this->inline_absent[$marker]) &&
            $from >= $this->inline_absent[$marker]) {
            return false;
        }
        $found = strpos($text, $marker, $from);
        if ($found === false) {
            $this->inline_absent[$marker] = $from;
        }
        return $found;
    }
    /**
     * Records, for every opening square and round bracket in an inline text,
     * the offset of the bracket that closes it, so a link reader can look up
     * where its label or destination ends rather than scanning for it from
     * each opener, which over a run of brackets would cost the square of the
     * run's length. One left-to-right pass pairs each closer with the
     * nearest still-open opener, skipping the character after a backslash so
     * an escaped bracket does not pair, exactly as the readers scanned by
     * hand before. An opener with no closer is left absent, read back as no
     * match.
     *
     * @param string $text the inline text a pass is about to scan
     * @return void
     */
    protected function buildInlineBrackets($text)
    {
        $this->bracket_match = [];
        $this->paren_match = [];
        $length = strlen($text);
        $square = [];
        $round = [];
        for ($i = 0; $i < $length; $i++) {
            $char = $text[$i];
            if ($char === "\\" && $i + 1 < $length) {
                $i++;
                continue;
            }
            if ($char === "[") {
                $square[] = $i;
            } else if ($char === "]") {
                if (!empty($square)) {
                    $this->bracket_match[array_pop($square)] = $i;
                }
            } else if ($char === "(") {
                $round[] = $i;
            } else if ($char === ")") {
                if (!empty($round)) {
                    $this->paren_match[array_pop($round)] = $i;
                }
            }
        }
    }
    /**
     * Splits text into the chunks that blank lines separate, where a blank
     * line is one holding nothing but whitespace. A run of blank lines
     * separates the same as a single one, and leading or trailing blank
     * lines fall away. This is how a page's head section is broken into its
     * separate settings without a regular expression.
     *
     * @param string $text the text to split
     * @return array the non-blank chunks, each with its lines rejoined by
     *      newlines
     */
    protected function splitOnBlankLines($text)
    {
        $chunks = [];
        $current = "";
        $lines = explode("\n", $text);
        foreach ($lines as $line) {
            if (trim($line) === "") {
                if ($current !== "") {
                    $chunks[] = $current;
                    $current = "";
                }
            } else {
                $current .= ($current === "") ? $line : "\n" . $line;
            }
        }
        if ($current !== "") {
            $chunks[] = $current;
        }
        return $chunks;
    }
    /**
     * Parses a mediawiki document to produce an HTML equivalent
     *
     * @param string $document a document which might have mediawiki markup
     * @param bool $parse_head_vars header variables are an extension of
     *     mediawiki syntax used to add meta variable and titles to
     *     the head tag of an html document. This flag controls whether to
     *     support this extension or not
     * @param bool $handle_big_files for indexing purposes Yioop by default
     *     truncates long documents before indexing them. If true, this
     *     method does not do this default truncation. The true value
     *     is more useful when using Yioop's built-in wiki.
     * @param int $render_engine 0 = mediawiki, 1 = markdown
     * @return string HTML document obtained by parsing mediawiki
     *     markup in $document
     */
    public function parse($document, $parse_head_vars = true,
        $handle_big_files = false, $render_engine = 0)
    {
        $head = "";
        $page_type = "standard";
        $head_vars = [];
        $draw_toc = true;
        if ($parse_head_vars && !$this->minimal) {
            $document_parts = explode(self::END_HEAD_VARS, $document);
            if (count($document_parts) > 1) {
                $head = $document_parts[0];
                $document = $document_parts[1];
                $head_lines = $this->splitOnBlankLines($head);
                foreach ($head_lines as $line) {
                    $semi_pos = (strpos($line, ";")) ? strpos($line, ";"):
                        strlen($line);
                    $line = substr($line, 0, $semi_pos);
                    $line_parts = explode("=", $line);
                    if (count($line_parts) == 2) {
                        $head_vars[trim(addslashes($line_parts[0]))] =
                            addslashes(trim($line_parts[1]));
                    }
                }
                if (isset($head_vars['page_type'])) {
                    $page_type = $head_vars['page_type'];
                }
                if (isset($head_vars['toc'])) {
                    $draw_toc = $head_vars['toc'];
                }
            }
        }
        if ($render_engine == 1) {
            $document = $this->parseMarkdown($document, $draw_toc,
                $page_type);
        } else {
            $document = htmlspecialchars_decode($document, ENT_QUOTES);
            $this->cite_references = [];
            $this->toc_headings = [];
            $this->collecting_headings = true;
            $this->parse_depth = 0;
            $scanner = new MarkUpScanner($document,
                self::WIKI_BLOCK_START_CHARS);
            $body = ($page_type == "presentation") ?
                $this->parseSlides($scanner) : $this->parseBlocks($scanner);
            $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 . self::END_HEAD_VARS . $document;
        }
        if (!$handle_big_files &&
            strlen($document) > 0.9 * C\MAX_GROUP_PAGE_LEN) {
            $document = substr($document, 0,
                (int)(0.9 * C\MAX_GROUP_PAGE_LEN));
            TextProcessor::closeDanglingTags($document);
            $document .= "...";
        }
        return $document;
    }
    /**
     * Largest heading level html defines; deeper markup clamps to it.
     */
    const MAX_HEADING_LEVEL = 6;
    /**
     * Inline html tags a wiki author may use directly, as an alternation
     * for a pattern. These are passed through as written; any other tag is
     * escaped so it cannot introduce active markup.
     */
    const INLINE_TAGS = "tt|u|s|strike|ins|del|sub|sup|b|i|br|code";
    /**
     * Deepest indent level the colon prefix supports; deeper markup
     * clamps to it, matching the indent one through four style classes.
     */
    const MAX_INDENT_LEVEL = 4;
    /**
     * How many headings a page needs before a table of contents is drawn
     * above it. Below this a contents box would be more clutter than help.
     */
    const MIN_SECTIONS_FOR_TOC = 4;
    /**
     * The characters that can begin a wiki block: heading, list, indent,
     * definition-list term, rule, brace (a table or template), and tag.
     * The scanner is given these so it can tell a line that opens a block
     * from one that continues the current block.
     */
    /**
     * SLIDE_SEPARATOR is the line that separates one slide from the next
     * on a presentation page: four dots on a line of their own. The slide
     * button in the wiki edit bar writes it, and the wiki syntax page
     * describes it, so the parsers read the same mark a writer is told
     * to use.
     */
    const SLIDE_SEPARATOR = "....";
    const WIKI_BLOCK_START_CHARS = "=*#:;-{<.";
    /**
     * The deepest the block and inline readers may nest before the parser
     * stops going further and passes the rest of the current piece through
     * as escaped literal text. Deeply nested wiki markup, whether written
     * by hand or crafted to make the parser call itself without end, is
     * held to this many levels so a page can never exhaust the call stack.
     */
    const WIKI_MAX_PARSE_DEPTH = 20;
    /**
     * The characters that can begin a markdown block: a heading hash, a
     * block-quote sign, a code fence in either fence character, a list
     * bullet or ordered-list digit, a rule or list character, a table
     * bar, and a template brace. The scanner is handed these so a fresh
     * line can be told from one that continues the current block.
     */
    const MARKDOWN_BLOCK_START_CHARS = "#>`~*-+_0123456789|{.";
    /**
     * The fewest fence characters that open or close a fenced code block,
     * and the fewest rule characters that make a horizontal rule; three of
     * either, the count GitHub's markdown uses.
     */
    const MARKDOWN_MIN_FENCE = 3;
    /**
     * The number of leading spaces that opens an indented code block, four,
     * the width GitHub's markdown uses; a leading tab counts as this much.
     */
    const MARKDOWN_CODE_INDENT = 4;
    /**
     * The punctuation a backslash may turn into a plain character in
     * markdown, so a writer can show one of these literally rather than
     * have it read as markup.
     */
    const MARKDOWN_ESCAPABLE = "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~";
    /**
     * Citations gathered while a page is rendered, in the order they
     * appear, so the reference list at the foot of the page can be built
     * from them.
     * @var array
     */
    protected $cite_references = [];
    /**
     * Headings gathered while the page body is parsed, each a level and
     * its plain text, used to build the table of contents.
     * @var array
     */
    protected $toc_headings = [];
    /**
     * Whether headings met while parsing should be gathered for the table
     * of contents. True for the page body, false inside a template so a
     * heading there does not appear in the contents box.
     * @var bool
     */
    protected $collecting_headings = false;
    /**
     * How many block or inline readers are currently nested, counted up on
     * entry and down on exit so the parser can stop once it passes
     * WIKI_MAX_PARSE_DEPTH and never runs the call stack out on deeply
     * nested or hostile markup.
     * @var int
     */
    protected $parse_depth = 0;
    /**
     * For the inline text an inline pass is scanning, the offsets from which
     * a closing marker is known to be absent to the end, keyed by marker, so
     * a run of openers whose closer never comes is read in linear rather than
     * quadratic time. Each inline pass clears this for its own text.
     * @var array
     */
    protected $inline_absent = [];
    /**
     * For the inline text an inline pass is scanning, the offset of the
     * closing square bracket that matches each opening one, keyed by the
     * opener's offset, built once for the pass so a link reader looks up its
     * label's end rather than scanning for it from every opening bracket.
     * @var array
     */
    protected $bracket_match = [];
    /**
     * For the inline text an inline pass is scanning, the offset of the
     * closing round bracket that matches each opening one, keyed by the
     * opener's offset, built once for the pass so a link reader looks up its
     * destination's end rather than scanning for it from every parenthesis.
     * @var array
     */
    protected $paren_match = [];
    /**
     * Link reference definitions collected from the markdown before it is
     * parsed, keyed by lower-cased reference name, each a url and title, so
     * a reference-style link may point at a definition given anywhere on the
     * page, including further down than the link itself.
     * @var array
     */
    protected $markdown_references = [];
    /**
     * Footnote definitions collected from the markdown before it is parsed,
     * keyed by lower-cased footnote name, each the footnote's text.
     * @var array
     */
    protected $markdown_footnote_defs = [];
    /**
     * The footnote names in the order they are first referred to, which
     * fixes the number each footnote is shown with and the order they are
     * listed at the foot of the page.
     * @var array
     */
    protected $markdown_footnote_order = [];
    /**
     * The number given to each footnote label, kept beside the order list
     * so a label's number is found by a direct lookup rather than by
     * searching the list, which would cost the square of the footnote
     * count over a page.
     * @var array
     */
    protected $markdown_footnote_numbers = [];
    /**
     * Url schemes a wiki link may use directly. A link target carrying
     * any other scheme, javascript included, is treated as a page name
     * and joined to the base address instead, so it can never become an
     * active script url.
     */
    const ALLOWED_LINK_SCHEMES = ["http", "https", "mailto", "gopher",
        "ftp"];
    /**
     * The smallest byte value that leads a two-byte utf-8 character; a
     * byte below it is either a plain ascii character or a stray
     * continuation byte, each read as one byte on its own.
     */
    const UTF8_LEAD_TWO = 0xC0;
    /**
     * The smallest byte value that leads a three-byte utf-8 character.
     */
    const UTF8_LEAD_THREE = 0xE0;
    /**
     * The smallest byte value that leads a four-byte utf-8 character.
     */
    const UTF8_LEAD_FOUR = 0xF0;
    /**
     * Parses a run of blocks from the scanner, emitting each block's html
     * as it is read so no tree of the whole document is held. Blank lines
     * between blocks are skipped. Used both for the page body and for the
     * content inside a template.
     *
     * @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, which is what the slide
     * button in the edit bar writes and what the wiki syntax page
     * describes. Each slide's own text is read by the ordinary block
     * parse, so everything a wiki page may hold works inside a slide.
     * A presentation with no separator at all is one slide.
     *
     * @param MarkUpScanner $scanner the scanner at the start of the page
     * @return string the html for the whole deck
     */
    protected function parseSlides($scanner)
    {
        $slides = "";
        while (!$scanner->atEnd()) {
            $slides .= "<x-slide>\n" . $this->parseSlide($scanner) .
                "</x-slide>\n";
            /* The separator that ended the slide is stepped over here,
               so the next turn starts on the line after it. At the end
               of the page there is nothing to step over. */
            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. Blocks are read by the same parse the rest of a wiki page uses.
     *
     * @param MarkUpScanner $scanner the scanner at the slide's first line
     * @return string the html for that slide's blocks
     */
    protected function parseSlide($scanner)
    {
        $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: a line holding four dots and
     * nothing else but space. The scanner is left where it was, since
     * this only looks.
     *
     * @param MarkUpScanner $scanner the scanner to look at
     * @return bool true when the line ahead separates two slides
     */
    protected function atSlideBreak($scanner)
    {
        if (!$scanner->atLineStart()) {
            return false;
        }
        return rtrim($scanner->peekLine()) === self::SLIDE_SEPARATOR;
    }
    /**
     * parseBlocks reads every block from where the scanner stands to the
     * end of what it holds, one after another, and joins their html. The
     * page body and every nested region, such as the inside of a table
     * cell or a template, is read through here, so the depth is counted
     * and a page nested past the limit is left as plain text rather than
     * read for ever.
     *
     * @param MarkUpScanner $scanner the scanner at the first block
     * @return string the html for all the blocks read
     */
    protected function parseBlocks($scanner)
    {
        $this->parse_depth++;
        if ($this->parse_depth > self::WIKI_MAX_PARSE_DEPTH) {
            $this->parse_depth--;
            return $this->escapeText($scanner->rest());
        }
        $html = "";
        while (!$scanner->atEnd()) {
            $scanner->skipBlankLines();
            if ($scanner->atEnd()) {
                break;
            }
            $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
     */
    protected function parseBlock($scanner)
    {
        /* A slide separator met while reading blocks rather than slides
           is drawn as a rule across the page, which is what a reader of
           a presentation sees when every slide is shown at once. Reading
           slides never reaches here with one, since the slide level
           stops at each separator and steps over it. */
        if ($this->atSlideBreak($scanner)) {
            $scanner->readLine();
            return "<hr class='slide-break' />\n";
        }
        if (!empty($this->extra_rules)) {
            $rule_result = $this->applyExtraRules($scanner->source(),
                $scanner->tell());
            if ($rule_result !== null) {
                $scanner->seek($rule_result["next"]);
                return $rule_result["html"];
            }
        }
        if ($scanner->startsWith("{{")) {
            $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->parseVerbatimBlock($scanner, "pre"));
        }
        if ($scanner->startsWith("<code>")) {
            return ($this->parseVerbatimBlock($scanner, "code"));
        }
        $first = $scanner->peek();
        if ($first === " " && $scanner->atLineStart()) {
            return $this->parseSpacePre($scanner);
        }
        if ($first === "=") {
            $heading = $this->parseHeading($scanner);
            if ($heading !== null) {
                return $heading;
            }
        }
        if ($first === "-") {
            $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: a heading run of equals signs, a list marker, a
     * rule of four or more dashes, a colon indent whose colons are
     * followed by a space or tab, a definition-list line naming a term and
     * a colon and its meaning, a line opening with a space for
     * preformatted text, a pre tag, or a table or template brace. A line
     * that does not is a continuation of the block being read, so a single
     * newline inside running text does not split it.
     *
     * @param MarkUpScanner $scanner the scanner at a line start
     * @return bool true when the line opens a new block
     */
    protected function startsBlock($scanner)
    {
        $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 === ":") {
            $ahead = 0;
            while ($scanner->peek($ahead) === ":") {
                $ahead++;
            }
            $after = $scanner->peek($ahead);
            return $after === " " || $after === "\t";
        }
        if ($first === ";") {
            $ahead = 1;
            while ($scanner->peek($ahead) !== "" &&
                $scanner->peek($ahead) !== "\n") {
                if ($scanner->peek($ahead) === ":") {
                    return true;
                }
                $ahead++;
            }
            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. The
     * title's plain text becomes the heading's anchor and its contents-box
     * entry, unless the line carries a notoc marker, which keeps the
     * heading out of the contents box while still showing it. Returns null
     * when the line is not actually a heading.
     *
     * @param MarkUpScanner $scanner the scanner at the heading line
     * @return string|null the heading html, or null when not a heading
     */
    protected function parseHeading($scanner)
    {
        $mark = $scanner->tell();
        $line = $scanner->readLine();
        /* a notoc marker anywhere on the line keeps this heading out of
           the contents box; the marker is dropped so the heading itself
           still shows */
        $in_contents = true;
        if (strpos($line, "<notoc>") !== false) {
            $in_contents = false;
            $line = str_replace(["<notoc>", "</notoc>"], "", $line);
        }
        $length = strlen($line);
        $open = 0;
        while ($open < $length && $line[$open] === "=") {
            $open++;
        }
        if ($open === 0) {
            $scanner->seek($mark);
            return null;
        }
        $end = $length;
        while ($end > $open && ($line[$end - 1] === " " ||
            $line[$end - 1] === "\t")) {
            $end--;
        }
        $close = 0;
        while ($close < $end - $open && $line[$end - 1 - $close] === "=") {
            $close++;
        }
        if ($close === 0) {
            /* The opening = has no closing = on its own line, so the
               heading text may run over several lines, for example a
               heading built from links and styled spans written one per
               line. Gather lines until one ends in the closing =; leave
               the block to ordinary parsing if a blank line or the end of
               input comes first. */
            return $this->parseMultilineHeading($scanner, $mark, $line,
                $open, $in_contents);
        }
        $level = min($open, $close, self::MAX_HEADING_LEVEL);
        $text = trim(substr($line, $open, $end - $open - $close));
        return $this->headingHtml($level, $text, $in_contents);
    }
    /**
     * Gathers a heading whose text spans several lines, the opening line
     * having no closing = of its own. Reads on until a line ends in an =,
     * which closes the heading, and builds the heading from the text
     * between the opening and closing = runs. A blank line or the end of
     * input with no closing = means this was not a heading, so the scanner
     * is put back and null returned.
     *
     * @param MarkUpScanner $scanner the scanner, positioned after the
     *      opening line
     * @param mixed $mark the scanner position of the opening =, to rewind
     *      to when no close is found
     * @param string $first_line the opening line, its leading = included
     * @param int $open the count of = characters that opened the heading
     * @param bool $in_contents whether the heading may enter the contents
     *      box
     * @return string|null the heading html, or null when not a heading
     */
    protected function parseMultilineHeading($scanner, $mark, $first_line,
        $open, $in_contents)
    {
        $lines = [$first_line];
        while (!$scanner->atEnd()) {
            $next = $scanner->readLine();
            if (strpos($next, "<notoc>") !== false) {
                $in_contents = false;
                $next = str_replace(["<notoc>", "</notoc>"], "", $next);
            }
            if (trim($next) === "") {
                $scanner->seek($mark);
                return null;
            }
            $end = strlen($next);
            while ($end > 0 && ($next[$end - 1] === " " ||
                $next[$end - 1] === "\t")) {
                $end--;
            }
            $close = 0;
            while ($close < $end && $next[$end - 1 - $close] === "=") {
                $close++;
            }
            if ($close > 0) {
                $lines[] = substr($next, 0, $end - $close);
                $lines[0] = substr($lines[0], $open);
                $level = min($open, $close, self::MAX_HEADING_LEVEL);
                return $this->headingHtml($level, implode("\n", $lines),
                    $in_contents);
            }
            $lines[] = $next;
        }
        $scanner->seek($mark);
        return null;
    }
    /**
     * Builds a heading's html from its level and its raw text, rendering
     * the text as inline markup and deriving an anchor id from the plain
     * words with any newlines flattened to spaces. Records the heading for
     * the contents box when one is being gathered and the heading is not
     * held out of it.
     *
     * @param int $level the heading level, 1 through the maximum
     * @param string $text the heading's raw text between its = runs
     * @param bool $in_contents whether the heading may enter the contents
     *      box
     * @return string the heading html
     */
    protected function headingHtml($level, $text, $in_contents)
    {
        $inline = $this->renderInline($text);
        $anchor = str_replace(["\r\n", "\n", "\r"], " ",
            strip_tags($inline));
        if ($this->collecting_headings && $in_contents) {
            $this->toc_headings[] = ["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, so
     * such a line is left to be read as a paragraph.
     *
     * @param MarkUpScanner $scanner the scanner at the dashed line
     * @return string|null the rule html, or null when not a rule
     */
    protected function parseRule($scanner)
    {
        $mark = $scanner->tell();
        $line = $scanner->readLine();
        $length = strlen($line);
        $dashes = 0;
        while ($dashes < $length && $line[$dashes] === "-") {
            $dashes++;
        }
        if ($dashes >= 4 && rtrim(substr($line, $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, together with any plain continuation lines, is the
     * indented text. Each indent is its own block, shown as an indented
     * paragraph.
     *
     * @param MarkUpScanner $scanner the scanner at the colon line
     * @return string the indent html
     */
    protected function parseIndent($scanner)
    {
        $line = $scanner->readLine();
        $length = strlen($line);
        $colons = 0;
        while ($colons < $length && $line[$colons] === ":") {
            $colons++;
        }
        $level = min($colons, self::MAX_INDENT_LEVEL);
        $text = substr($line, $colons + 1);
        $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 so
     * consecutive terms and meanings sit together. The term and the
     * meaning are each parsed for inline markup.
     *
     * @param MarkUpScanner $scanner the scanner at the first term line
     * @return string the definition-list html
     */
    protected function parseDefinitionList($scanner)
    {
        $html = "<dl>\n";
        while (!$scanner->atEnd() && $scanner->peek() === ";" &&
            $this->startsBlock($scanner)) {
            $rest = substr($scanner->readLine(), 1);
            $colon = strpos($rest, ":");
            $term = trim(substr($rest, 0, $colon));
            $meaning = trim(substr($rest, $colon + 1));
            $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
     * @param bool $as_markdown whether what the mark holds is markdown
     *      rather than wiki markup
     * @return mixed the html of what the mark held, or null where the
     *      line did not open one
     */
    protected function readSameUnit($opening, $scanner, $as_markdown = false)
    {
        $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. */
        $at = stripos($opening, $mark);
        if ($at === false) {
            return null;
        }
        $before = substr($opening, 0, $at);
        $gathered = substr($opening, $at);
        while (substr_count($gathered, "{{") > substr_count($gathered, "}}")
            && !$scanner->atEnd()) {
            $gathered .= "\n" . $scanner->readLine();
        }
        $inner = substr($gathered, strlen($mark));
        $close = strrpos($inner, "}}");
        if ($close !== false) {
            $inner = substr($inner, 0, $close);
        }
        $was = $this->collecting_headings;
        $this->collecting_headings = false;
        $content = new MarkUpScanner(trim($inner),
            self::WIKI_BLOCK_START_CHARS);
        $html = ($as_markdown) ? $this->parseMarkdownBlocks($content) :
            $this->parseBlocks($content);
        $this->collecting_headings = $was;
        if (trim($before) !== "") {
            $html = $this->renderInline(trim($before)) . " " . $html;
        }
        return $html;
    }
    /**
     * Reads what a same-unit mark holds where the lines it holds have
     * already been gathered, as in a table cell, so there is no scanner
     * left to read on from.
     *
     * @param string $text the gathered lines, which may open a same-unit
     * @param bool $as_markdown whether what the mark holds is markdown
     * @return mixed the html of what the mark held, or null where the
     *      text did not open one
     */
    protected function readSameUnitText($text, $as_markdown = false)
    {
        $mark = "{{same-unit";
        if (strncasecmp(ltrim($text), $mark, strlen($mark)) !== 0) {
            return null;
        }
        $inner = substr(ltrim($text), strlen($mark));
        $close = strrpos($inner, "}}");
        if ($close !== false) {
            $inner = substr($inner, 0, $close);
        }
        $was = $this->collecting_headings;
        $this->collecting_headings = false;
        $content = new MarkUpScanner(trim($inner),
            self::WIKI_BLOCK_START_CHARS);
        $html = ($as_markdown) ? $this->parseMarkdownBlocks($content) :
            $this->parseBlocks($content);
        $this->collecting_headings = $was;
        return $html;
    }
    /**
     * Gives what a markdown definition line says, where the line is one.
     * A definition is a line opening with a colon, the way markdown's
     * extended syntax writes one beneath the term it explains.
     *
     * @param string $line the line to look at
     * @return mixed what the line says after its colon, or null where the
     *      line is not a definition
     */
    protected function markdownDefinitionSays($line)
    {
        $trimmed = ltrim($line);
        if ($trimmed === "" || $trimmed[0] !== ":") {
            return null;
        }
        return trim(substr($trimmed, 1));
    }
    /**
     * Reads a markdown definition list: a term on a line of its own, then
     * one or more lines each opening with a colon giving a meaning. A
     * meaning may open a same-unit mark, in which case it holds whole
     * blocks rather than only what fits on the line.
     *
     * @param MarkUpScanner $scanner cursor at the first term line
     * @return string the description-list html
     */
    protected function readMarkdownDefinitionList($scanner)
    {
        $html = "<dl>\n";
        while (!$scanner->atEnd() &&
            $this->markdownDefinitionSays($scanner->peekLine()) === null &&
            $this->markdownDefinitionSays($scanner->peekLine(1)) !== null) {
            $term = trim($scanner->readLine());
            $html .= "<dt>" . $this->renderMarkdownInline($term) .
                "</dt>\n";
            while (!$scanner->atEnd() && ($says =
                $this->markdownDefinitionSays($scanner->peekLine())) !==
                null) {
                $scanner->readLine();
                $together = $this->readSameUnit($says, $scanner, true);
                $html .= "<dd>" . (($together === null) ?
                    $this->renderMarkdownInline($says) : $together) .
                    "</dd>\n";
            }
            $scanner->skipBlankLines();
        }
        return $html . "</dl>\n";
    }
    /**
     * Reads a whole list, gathering its item lines (each a marker of stars
     * or hashes and the item's text) 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
     */
    protected function parseList($scanner)
    {
        $list_lines = [];
        while (!$scanner->atEnd() && !$scanner->atBlankLine()) {
            $first = $scanner->peek();
            if ($first === "*" || $first === "#") {
                $line = $scanner->readLine();
                $length = strlen($line);
                $marker_length = 0;
                while ($marker_length < $length &&
                    ($line[$marker_length] === "*" ||
                    $line[$marker_length] === "#")) {
                    $marker_length++;
                }
                $text = substr($line, $marker_length);
                if ($text !== "" && ($text[0] === " " ||
                    $text[0] === "\t")) {
                    $text = substr($text, 1);
                }
                $together = $this->readSameUnit($text, $scanner);
                $list_lines[] = ["marker" =>
                    substr($line, 0, $marker_length), "text" => $text,
                    "held" => $together];
            } else if (!$this->startsBlock($scanner)) {
                $last = count($list_lines) - 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. This is what lets lists nest to any depth with no fixed
     * ceiling; whether the level is numbered or bulleted comes from the
     * marker character at this depth.
     *
     * @param array $list_lines the run of list lines, each a marker and
     *      text
     * @param int $base_depth the depth of the level being emitted, from one
     * @return string the html for this list level and those under it
     */
    protected function buildListHtml($list_lines, $base_depth)
    {
        $marker = $list_lines[0]["marker"];
        $tag = (($marker[$base_depth - 1] ?? "*") === "#") ? "ol" : "ul";
        $html = "<$tag>\n";
        $count = count($list_lines);
        $index = 0;
        while ($index < $count) {
            $next = $index + 1;
            while ($next < $count &&
                strlen($list_lines[$next]["marker"]) > $base_depth) {
                $next++;
            }
            $html .= "<li>" .
                (empty($list_lines[$index]["held"]) ?
                $this->renderInline($list_lines[$index]["text"]) :
                $list_lines[$index]["held"]);
            if ($next > $index + 1) {
                $html .= "\n" . $this->buildListHtml(array_slice(
                    $list_lines, $index + 1, $next - $index - 1),
                    $base_depth + 1);
            }
            $html .= "</li>\n";
            $index = $next;
        }
        return $html . "</$tag>\n";
    }
    /**
     * Reads a wiki table from its opening brace-bar line through its
     * closing bar-brace line and emits the table html. A plus line gives
     * the caption, a dash line starts a row, a bang line holds header
     * cells split on double bangs, and a bar line holds data cells split
     * on double bars; only the table's class and style survive.
     *
     * @param MarkUpScanner $scanner the scanner at the opening {| line
     * @return string the table html
     */
    protected function parseTable($scanner)
    {
        $open = $scanner->readLine();
        $attributes = trim(substr($open, 2));
        $caption = null;
        $rows = [];
        $cells = null;
        while (!$scanner->atEnd()) {
            $line = $scanner->readLine();
            if (substr($line, 0, 2) === "|}") {
                break;
            }
            if (substr($line, 0, 2) === "|+") {
                $caption = trim(substr($line, 2));
            } else if (substr($line, 0, 2) === "|-") {
                if ($cells !== null) {
                    $rows[] = $cells;
                }
                $cells = [];
            } else if ($line !== "" &&
                ($line[0] === "!" || $line[0] === "|")) {
                if ($cells === null) {
                    $cells = [];
                }
                foreach ($this->splitTableCells($line) as $cell) {
                    $cells[] = $cell;
                }
            } else if (!empty($cells)) {
                $last = count($cells) - 1;
                $cells[$last]["text"] .= "\n" . $line;
            }
        }
        if ($cells !== null) {
            $rows[] = $cells;
        }
        $html = "<table" . $this->safeTableAttributes($attributes) .
            ">\n";
        if ($caption !== null) {
            $html .= "<caption>" . $this->renderInline($caption) .
                "</caption>\n";
        }
        foreach ($rows as $row) {
            $html .= "<tr>";
            foreach ($row as $cell) {
                $tag = $cell["header"] ? "th" : "td";
                /* A cell holds one line's worth unless its text opens a
                   same-unit, in which case it holds whole blocks. The
                   cell's lines are already gathered by the time this
                   runs, so what the mark holds is read from them rather
                   than from the scanner. */
                $held = $this->readSameUnitText($cell["text"]);
                $html .= "<$tag" . $cell["attributes"] . ">" .
                    (($held === null) ? $this->renderInline($cell["text"]) :
                    $held) . "</$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 both the
     * attribute string and how many leading characters were attributes. A
     * name outside the safe list is read but left out; the first token that
     * is not a name="value" pair ends the read, and whatever follows stays
     * as cell content rather than being lost. This is what lets a cell tell
     * an attribute run at its wall apart from ordinary content that merely
     * holds a bar.
     *
     * @param string $text the text before a cell's first single bar
     * @return array the safe attributes as an html attribute string under
     *      "text", and the count of leading characters that were attributes
     *      under "length"; text is empty and length is 0 when the run holds
     *      no attribute
     */
    protected function readCellAttributes($text)
    {
        $allowed = ["align", "valign", "style", "class", "colspan",
            "rowspan", "scope", "width", "height", "bgcolor", "id"];
        $result = "";
        $length = strlen($text);
        $index = 0;
        $consumed = 0;
        while ($index < $length) {
            while ($index < $length && ctype_space($text[$index])) {
                $index++;
            }
            $start = $index;
            while ($index < $length && (ctype_alpha($text[$index]) ||
                $text[$index] === "-")) {
                $index++;
            }
            $name = strtolower(substr($text, $start, $index - $start));
            $after = $index;
            while ($after < $length && ctype_space($text[$after])) {
                $after++;
            }
            if ($name === "" || $after >= $length ||
                $text[$after] !== "=") {
                break;
            }
            $after++;
            while ($after < $length && ctype_space($text[$after])) {
                $after++;
            }
            if ($after >= $length ||
                ($text[$after] !== "\"" && $text[$after] !== "'")) {
                break;
            }
            $quote = $text[$after];
            $value_start = $after + 1;
            $end = strpos($text, $quote, $value_start);
            if ($end === false) {
                break;
            }
            if (in_array($name, $allowed)) {
                $result .= " " . $name . "=\"" .
                    $this->escapeText(substr($text, $value_start,
                    $end - $value_start)) . "\"";
            }
            $index = $end + 1;
            $consumed = $index;
        }
        return ["text" => $result, "length" => $consumed];
    }
    /**
     * Splits one table line into its cells. The line opens with a bang for
     * a header cell or a bar for a data cell; within the line a double bang
     * starts another header cell and a bar, single or double, starts a data
     * cell, so a row can pair a header with the data beside it or lay out
     * several cells with single bars. 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, before the bar that ends it, is kept as that cell's
     * attributes. Each returned cell keeps whether it is a header.
     *
     * @param string $line the cell line, opening with a bang or a bar
     * @return array the cells, each a header flag, its text, and its
     *      attribute string
     */
    protected function splitTableCells($line)
    {
        $cells = [];
        $header = ($line[0] === "!");
        $rest = substr($line, 1);
        $current = "";
        $index = 0;
        $length = strlen($rest);
        $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. */
        $resource_depth = 0;
        $in_nowiki = false;
        $attributes = "";
        $attr_done = false;
        while ($index < $length) {
            if (!$in_nowiki &&
                substr_compare($rest, "<nowiki>", $index, 8) === 0) {
                $in_nowiki = true;
                $current .= "<nowiki>";
                $index += 8;
                continue;
            }
            if ($in_nowiki &&
                substr_compare($rest, "</nowiki>", $index, 9) === 0) {
                $in_nowiki = false;
                $current .= "</nowiki>";
                $index += 9;
                continue;
            }
            if (!$in_nowiki && $link_depth === 0 && $resource_depth === 0) {
                $pair = substr($rest, $index, 2);
                if ($pair === "((") {
                    $resource_depth++;
                    $current .= "((";
                    $index += 2;
                    continue;
                }
                if ($pair === "[[") {
                    $link_depth++;
                    $current .= "[[";
                    $index += 2;
                    continue;
                }
                if ($pair === "!!" || $pair === "||") {
                    $cells[] = ["header" => $header,
                        "text" => trim($current),
                        "attributes" => $attributes];
                    $header = ($pair === "!!");
                    $current = "";
                    $attributes = "";
                    $attr_done = false;
                    $index += 2;
                    continue;
                }
                if ($rest[$index] === "|") {
                    if (!$attr_done) {
                        $parsed = $this->readCellAttributes($current);
                        if ($parsed["text"] !== "") {
                            $attributes = $parsed["text"];
                            $attr_done = true;
                            $current = substr($current, $parsed["length"]);
                            $index++;
                            continue;
                        }
                    }
                    $cells[] = ["header" => $header,
                        "text" => trim($current),
                        "attributes" => $attributes];
                    $header = false;
                    $attributes = "";
                    $attr_done = false;
                    $current = "";
                    $index++;
                    continue;
                }
            }
            if (!$in_nowiki && $resource_depth > 0 &&
                substr_compare($rest, "))", $index, 2) === 0) {
                $resource_depth--;
                $current .= "))";
                $index += 2;
                continue;
            }
            if (!$in_nowiki && $link_depth > 0 &&
                substr_compare($rest, "]]", $index, 2) === 0) {
                $link_depth--;
                $current .= "]]";
                $index += 2;
                continue;
            }
            $current .= $rest[$index];
            $index++;
        }
        $cells[] = ["header" => $header, "text" => trim($current),
            "attributes" => $attributes];
        return $cells;
    }
    /**
     * Removes nowiki tags from a stretch of preformatted text while keeping
     * the characters they wrap. A pre block already shows its text exactly
     * as typed, so a nowiki span within it needs only its opening and
     * closing tags taken out; an opener with no closer is left as written.
     *
     * @param string $text the preformatted text that may hold nowiki spans
     * @return string the text with matched nowiki tags removed
     */
    protected function stripNowiki($text)
    {
        $open = "<nowiki>";
        $close = "</nowiki>";
        $result = "";
        $index = 0;
        $length = strlen($text);
        while ($index < $length) {
            if (substr_compare($text, $open, $index, strlen($open)) === 0) {
                $end = strpos($text, $close, $index + strlen($open));
                if ($end !== false) {
                    $result .= substr($text, $index + strlen($open),
                        $end - $index - strlen($open));
                    $index = $end + strlen($close);
                    continue;
                }
            }
            $result .= $text[$index];
            $index++;
        }
        return $result;
    }
    /**
     * 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, so example markup wrapped in nowiki shows as
     * plain characters; 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
     */
    protected function parseVerbatimBlock($scanner, $tag)
    {
        $open = "<$tag>";
        $close = "</$tag>";
        $scanner->advance(strlen($open));
        $body = "";
        $nowiki_depth = 0;
        while (!$scanner->atEnd()) {
            if ($nowiki_depth === 0 && $scanner->startsWith($close)) {
                $scanner->advance(strlen($close));
                break;
            }
            if ($scanner->startsWith("<nowiki>")) {
                $nowiki_depth++;
                $body .= "<nowiki>";
                $scanner->advance(strlen("<nowiki>"));
                continue;
            }
            if ($nowiki_depth > 0 && $scanner->startsWith("</nowiki>")) {
                $nowiki_depth--;
                $body .= "</nowiki>";
                $scanner->advance(strlen("</nowiki>"));
                continue;
            }
            $body .= $scanner->peek();
            $scanner->advance();
        }
        return "<$tag>" . $this->escapeVerbatim($this->stripNowiki($body)) .
            "</$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. The single
     * opening space is dropped from each line and the rest is shown exactly
     * as typed; a blank line or a line that does not open with a space ends
     * the block. A nowiki span within has its tags dropped and its
     * characters kept, the same as in a tagged pre block.
     *
     * @param MarkUpScanner $scanner the scanner at the first spaced line
     * @return string the pre block html
     */
    protected function parseSpacePre($scanner)
    {
        $lines = [];
        $gathered = "";
        while (!$scanner->atEnd()) {
            if ((substr_count($gathered,
                "<nowiki>") > substr_count($gathered, "</nowiki>"))) {
                /* a nowiki span opened on an earlier line of this run is
                   still open, so the run keeps taking lines as typed until
                   it closes, including lines that do not open with a space,
                   the way nowiki content is always shown verbatim */
                $line = $scanner->readLine();
            } else if ($scanner->peek() === " " &&
                !$scanner->atBlankLine()) {
                $line = substr($scanner->readLine(), 1);
            } else {
                break;
            }
            $lines[] = $line;
            if ($gathered === "") {
                $gathered = $line;
            } else {
                $gathered .= "\n" . $line;
            }
        }
        return "<pre>" . $this->escapeVerbatim(
            $this->stripNowiki(implode("\n", $lines))) . "</pre>\n";
    }
    /**
     * Reads a notoc region, the lines from a notoc tag to its closing tag,
     * and emits them parsed as usual except that no heading inside is added
     * to the contents box. It lets a page keep a stretch of headings, such
     * as a set of examples, out of the contents box without marking each
     * one.
     *
     * @param MarkUpScanner $scanner the scanner at the opening notoc tag
     * @return string the html for the region's contents
     */
    protected function parseNotocRegion($scanner)
    {
        $open = "<notoc>";
        $close = "</notoc>";
        $line = $scanner->readLine();
        $content = substr($line, strpos($line, $open) + strlen($open));
        $end = strpos($content, $close);
        if ($end !== false) {
            $content = substr($content, 0, $end);
        } else {
            while (!$scanner->atEnd()) {
                $line = $scanner->readLine();
                $end = strpos($line, $close);
                if ($end !== false) {
                    $content .= "\n" . substr($line, 0, $end);
                    break;
                }
                $content .= "\n" . $line;
            }
        }
        $was = $this->collecting_headings;
        $this->collecting_headings = false;
        $inside = new MarkUpScanner($content,
            self::WIKI_BLOCK_START_CHARS);
        $html = $this->parseBlocks($inside);
        $this->collecting_headings = $was;
        return $html;
    }
    /**
     * Reads a block template that opens with a double brace. The
     * block-and-end-block and inblock forms wrap the lines up to their end
     * marker in a div or span; the alignment, class, id, and style forms
     * and the transclusion forms wrap the braced content. A form template,
     * whose html is block level, may be followed on its line by inline
     * content such as a line break, which is rendered and kept with it; a
     * plain block template must stand alone on its line. Returns null, and
     * leaves the scanner untouched, when the braces do not form a template
     * the block reader handles so the caller can read the line as text.
     *
     * @param MarkUpScanner $scanner the scanner at the opening double brace
     * @return string|null the template html, or null when not a block
     *      template
     */
    protected function parseTemplate($scanner)
    {
        $mark = $scanner->tell();
        $block = $this->parseWrappedTemplate($scanner);
        if ($block !== null) {
            return $block;
        }
        $inner = $scanner->matchBraces();
        if ($inner === false) {
            $scanner->seek($mark);
            return null;
        }
        $trailing = trim($scanner->readLine());
        $node = $this->readBlockTemplate($inner);
        if ($node !== null) {
            if ($trailing !== "") {
                $scanner->seek($mark);
                return null;
            }
            if ($node["type"] === "html") {
                return $node["html"];
            }
            $was = $this->collecting_headings;
            $this->collecting_headings = false;
            $content = new MarkUpScanner($node["content"],
                self::WIKI_BLOCK_START_CHARS);
            $inside = $this->parseBlocks($content);
            $this->collecting_headings = $was;
            return "<" . $node["tag"] . $node["attributes"] . ">\n" .
                $inside . "</" . $node["tag"] . ">\n";
        }
        $form = $this->readFormTemplate($inner);
        if ($form !== null) {
            $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,
     * one written as {{block|id|style}} or {{inblock|id|style}} alone on
     * its line. The id must be present and the style may be empty; neither
     * may hold a bar or a brace. This tells the wrapper parser what tag to
     * open and with what id and style, without a regular expression.
     *
     * @param string $line the line to read
     * @return array|null the keyword, id, and style, or null when the line
     *      is not a wrapper opening
     */
    protected function matchWrappedTemplateOpen($line)
    {
        $trimmed = rtrim($line);
        if (substr($trimmed, 0, 2) !== "{{" ||
            substr($trimmed, -2) !== "}}") {
            return null;
        }
        $inner = substr($trimmed, 2, strlen($trimmed) - 4);
        $parts = explode("|", $inner);
        if (count($parts) !== 3) {
            return null;
        }
        list($keyword, $id, $style) = $parts;
        if ($keyword !== "block" && $keyword !== "inblock") {
            return null;
        }
        if ($id === "" || strpos($id, "}") !== false ||
            strpos($style, "}") !== false) {
            return null;
        }
        return ["keyword" => $keyword, "id" => $id, "style" => $style];
    }
    /**
     * Reads the block-and-end-block or inblock-and-end-inblock form, in
     * which an opening line names an id and style and the lines up to a
     * matching end marker are wrapped 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 when not this form
     */
    protected function parseWrappedTemplate($scanner)
    {
        $mark = $scanner->tell();
        $line = $scanner->readLine();
        $open = $this->matchWrappedTemplateOpen($line);
        if ($open === null) {
            $scanner->seek($mark);
            return null;
        }
        $tag = ($open["keyword"] === "inblock") ? "span" : "div";
        $end_marker = "{{end-" . $open["keyword"] . "}}";
        $collected = "";
        while (!$scanner->atEnd()) {
            $mark_line = $scanner->tell();
            $line = $scanner->readLine();
            if (rtrim($line) === $end_marker) {
                break;
            }
            $collected .= ($collected === "" ? "" : "\n") . $line;
        }
        $was = $this->collecting_headings;
        $this->collecting_headings = false;
        $content = new MarkUpScanner($collected,
            self::WIKI_BLOCK_START_CHARS);
        $inside = $this->parseBlocks($content);
        $this->collecting_headings = $was;
        return "<$tag id=\"" . $this->escapeText($open["id"]) .
            "\" style=\"" . $this->escapeText($open["style"]) . "\">\n" .
            $inside . "</$tag>\n";
    }
    /**
     * Reads a paragraph: the first line plus any plain continuation lines,
     * stopping at a blank line or a line that opens a new block. The
     * gathered text is parsed for inline markup.
     *
     * @param MarkUpScanner $scanner the scanner at the paragraph's start
     * @return string the paragraph html
     */
    protected function parseParagraph($scanner)
    {
        $text = $scanner->readLine();
        while (!$scanner->atEnd()) {
            if (!(substr_count($text, "<nowiki>") > substr_count($text,
                "</nowiki>")) &&
                ($scanner->atBlankLine() || $this->startsBlock($scanner))) {
                break;
            }
            $text .= "\n" . $scanner->readLine();
        }
        return "<p>" . $this->renderInline($text) . "</p>\n";
    }
    /**
     * Pulls just the class and style out of a table's attribute text and
     * returns them as an escaped attribute string, dropping anything else
     * so a table cannot carry an event handler or other active attribute.
     *
     * @param string $attributes the raw attribute text after the {|
     * @return string a leading-space attribute string, or the empty
     *      string when neither class nor style is present
     */
    protected function safeTableAttributes($attributes)
    {
        $safe = "";
        $class = $this->extractQuotedAttribute($attributes, "class");
        if ($class !== null) {
            $safe .= " class=\"" . $this->escapeText($class) . "\"";
        }
        $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. The name is matched without regard to case, spaces
     * are allowed around the equals sign, and the value is read up to the
     * next double quote. This lets the table code lift out just the class
     * or style it trusts without a regular expression.
     *
     * @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 when the
     *      named attribute with a quoted value is not present
     */
    protected function extractQuotedAttribute($attributes, $name)
    {
        $lower = strtolower($attributes);
        $length = strlen($attributes);
        $name_length = strlen($name);
        $offset = 0;
        while (($found = strpos($lower, $name, $offset)) !== false) {
            $cursor = $found + $name_length;
            while ($cursor < $length && ctype_space($attributes[$cursor])) {
                $cursor++;
            }
            if ($cursor < $length && $attributes[$cursor] === "=") {
                $cursor++;
                while ($cursor < $length &&
                    ctype_space($attributes[$cursor])) {
                    $cursor++;
                }
                if ($cursor < $length && $attributes[$cursor] === "\"") {
                    $cursor++;
                    $close = strpos($attributes, "\"", $cursor);
                    if ($close !== false) {
                        return substr($attributes, $cursor,
                            $close - $cursor);
                    }
                }
            }
            $offset = $found + 1;
        }
        return null;
    }
    /**
     * Finds the double-brace that closes the double-brace template
     * opening at the given position, counting nested templates so an
     * inner }} does not end the outer one. This is what lets a template
     * hold another template to any depth.
     *
     * @param string $text the text being scanned
     * @param int $start the position of the opening {{
     * @return int|false the position of the matching }} or false when
     *      there is none
     */
    protected function matchBraces($text, $start)
    {
        $depth = 0;
        $length = strlen($text);
        $index = $start;
        while ($index < $length - 1) {
            $pair = substr($text, $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 text
     * beyond that separator. Reading the head by hand, rather than with a
     * pattern, lets each template form parse what follows its own way.
     *
     * @param string $inner the text between the template's braces
     * @return array the name, the separator character, and the rest
     */
    protected function readTemplateHead($inner)
    {
        $length = strlen($inner);
        $index = 0;
        while ($index < $length && ctype_space($inner[$index])) {
            $index++;
        }
        $start = $index;
        while ($index < $length &&
            strpos("|=:", $inner[$index]) === false) {
            $index++;
        }
        $separator = ($index < $length) ? $inner[$index] : "";
        $rest = ($index < $length) ? substr($inner, $index + 1) : "";
        return ["name" => trim(substr($inner, $start, $index - $start)),
            "separator" => $separator, "rest" => $rest];
    }
    /**
     * Reads a quoted value and the text that follows it, used by the class,
     * id, and style forms whose value is wrapped in single or double
     * quotes. Returns null when the text does not open with a quote.
     *
     * @param string $text the text after the attribute's separator
     * @return array|null the quoted value and the content after it, or null
     */
    protected function readQuotedValue($text)
    {
        /* What a writer types is kept as the site stores it, and the
           site stores a quote as the name that stands for it, so both
           the mark itself and that name open a value here. Without
           this, a block written with quotes came back from a save
           unreadable to the very parser that had accepted it. */
        $text = str_replace(["&quot;", "&#039;", "&#39;", "&apos;"],
            ["\"", "'", "'", "'"], $text);
        $length = strlen($text);
        $index = 0;
        while ($index < $length && ctype_space($text[$index])) {
            $index++;
        }
        if ($index >= $length ||
            ($text[$index] !== "\"" && $text[$index] !== "'")) {
            return null;
        }
        $quote = $text[$index];
        $index++;
        $start = $index;
        while ($index < $length && $text[$index] !== $quote) {
            $index++;
        }
        if ($index >= $length) {
            return null;
        }
        return ["value" => substr($text, $start, $index - $start),
            "content" => ltrim(substr($text, $index + 1))];
    }
    /**
     * Reads a styling template's inside into a template node, or returns
     * null when it is not one this reader handles. The alignment forms are
     * center, left, and right before a bar; the class, id, and style forms
     * name an attribute, an equals or colon, a quoted value, then the
     * content; the see and hatnote forms make an indented note.
     *
     * @param string $inner the text between the {{ and the }}
     * @return array|null a template node, or null when unhandled
     */
    protected function 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. */
        $mark = "same-unit";
        $trimmed = ltrim($inner);
        if (strncasecmp($trimmed, $mark, strlen($mark)) === 0 &&
            (strlen($trimmed) == strlen($mark) ||
            ctype_space($trimmed[strlen($mark)]))) {
            return ["type" => "template", "tag" => "div",
                "attributes" => " class=\"same-unit\"",
                "content" => trim(substr($trimmed, strlen($mark)))];
        }
        $head = $this->readTemplateHead($inner);
        $name = $head["name"];
        $separator = $head["separator"];
        $rest = $head["rest"];
        $lower = strtolower($name);
        $alignments = ["center" => "center", "left" => "align-left",
            "right" => "align-right"];
        if ($separator === "|" && isset($alignments[$name])) {
            return ["type" => "template", "tag" => "div",
                "attributes" => " class=\"" . $alignments[$name] . "\"",
                "content" => $rest];
        }
        if (($separator === "=" || $separator === ":") &&
            ($name === "class" || $name === "id" || $name === "style" ||
            isset(self::BLOCK_ATTRIBUTE_DIRECTIVES[$lower]))) {
            $parsed = $this->readQuotedValue($rest);
            if ($parsed !== null) {
                $attribute = self::BLOCK_ATTRIBUTE_DIRECTIVES[$lower] ??
                    $name;
                return ["type" => "template", "tag" => "div",
                    "attributes" => " " . $attribute . "=\"" .
                    $this->escapeText($parsed["value"]) . "\"",
                    "content" => $parsed["content"]];
            }
        }
        if ($separator === "|" && ($lower === "main" || $lower === "see" ||
            $lower === "see also")) {
            $bar = strpos($rest, "|");
            $target = trim(($bar === false) ? $rest :
                substr($rest, 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;
    }
    /**
     * Builds the table of contents that goes above a page, or the empty
     * string when the page has too few headings to need one. Each entry
     * shows the heading's plain text with its markup stripped, so a link
     * inside a heading reads as its words rather than as raw link markup,
     * and points at the heading's own anchor.
     *
     * @param array $headings the page's headings, each a level and its
     *      plain text, gathered while the body was parsed
     * @return string the html contents box, or "" when not drawn
     */
    protected function tableOfContents($headings)
    {
        if (count($headings) < self::MIN_SECTIONS_FOR_TOC) {
            return "";
        }
        /* a single top-level heading is the page's title, so it is left
           out of the contents box; two or more are kept, as are all the
           deeper headings */
        $top_count = 0;
        foreach ($headings as $heading) {
            if ($heading["level"] === 1) {
                $top_count++;
            }
        }
        if ($top_count === 1) {
            $kept = [];
            foreach ($headings as $heading) {
                if ($heading["level"] !== 1) {
                    $kept[] = $heading;
                }
            }
            $headings = $kept;
        }
        if (empty($headings)) {
            return "";
        }
        $min_level = min(array_column($headings, "level"));
        $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 it becomes a child of
     * it and the contents box mirrors the page's outline.
     *
     * @param array $headings the headings, each a level and plain text,
     *      all at least $base_level deep
     * @param int $base_level the level of the tier being built
     * @return array the heading items at this tier, each with any nested
     *      items under it
     */
    protected function nestHeadings($headings, $base_level)
    {
        $items = [];
        $count = count($headings);
        $index = 0;
        while ($index < $count) {
            $item = ["text" => $headings[$index]["text"],
                "sublist" => null];
            $next = $index + 1;
            while ($next < $count &&
                $headings[$next]["level"] > $base_level) {
                $next++;
            }
            if ($next > $index + 1) {
                $item["sublist"] = $this->nestHeadings(
                    array_slice($headings, $index + 1,
                    $next - $index - 1), $base_level + 1);
            }
            $items[] = $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
     */
    protected function renderContents($items)
    {
        $html = "<ol>\n";
        foreach ($items as $item) {
            $html .= "<li><a href=\"#" . $item["text"] . "\">" .
                $item["text"] . "</a>";
            if ($item["sublist"] !== null) {
                $html .= "\n" . $this->renderContents($item["sublist"]);
            }
            $html .= "</li>\n";
        }
        return $html . "</ol>\n";
    }
    /**
     * Renders a document node, or any block node under it, to html,
     * parsing the inline markup inside each block's text as it goes.
     *
     * @param array $node a node produced by scanBlocks
     * @return string the html for that node and everything under it
     */
    /**
     * Parses the inline markup inside a block's text: bold and italic
     * emphasis and links, with everything else escaped so it cannot be
     * read as html. The body of an emphasis span or a link's shown text is
     * parsed for inline markup in turn, which is how bold inside a link, or
     * a link inside bold, comes out right. Math, written either in a math
     * tag or between backticks, is handed to the math renderer whole and
     * not read for wiki markup, so brackets in a matrix stay a matrix
     * rather than becoming a link. The allowed html tags, nowiki, and the
     * inline templates are handled here too.
     *
     * @param string $text the raw text of one block
     * @return string the html for that text
     */
    protected function renderInline($text)
    {
        $this->parse_depth++;
        if ($this->parse_depth > self::WIKI_MAX_PARSE_DEPTH) {
            $this->parse_depth--;
            return $this->escapeText($text);
        }
        $html = "";
        $length = strlen($text);
        $index = 0;
        $saved_absent = $this->inline_absent;
        $this->inline_absent = [];
        while ($index < $length) {
            if (!empty($this->extra_rules)) {
                $rule_result = $this->applyExtraRules($text, $index);
                if ($rule_result !== null) {
                    $html .= $rule_result["html"];
                    $index = $rule_result["next"];
                    continue;
                }
            }
            $nowiki_open = "<nowiki>";
            $nowiki_close = "</nowiki>";
            if (substr($text, $index, strlen($nowiki_open)) ===
                $nowiki_open) {
                $start = $index + strlen($nowiki_open);
                $close = $this->findMark($text, $nowiki_close, $start);
                if ($close !== false) {
                    $html .= $this->escapeVerbatim(substr($text, $start,
                        $close - $start));
                    $index = $close + strlen($nowiki_close);
                    continue;
                }
            }
            if ($text[$index] === "<") {
                $inline_tag = $this->matchInlineTag($text, $index);
                if ($inline_tag !== null) {
                    $html .= $inline_tag;
                    $index += strlen($inline_tag);
                    continue;
                }
            }
            $math_open = "<math>";
            $math_close = "</math>";
            if (substr($text, $index, strlen($math_open)) ===
                $math_open) {
                $start = $index + strlen($math_open);
                $close = $this->findMark($text, $math_close, $start);
                if ($close !== false) {
                    $html .= "`" . $this->escapeText(substr($text,
                        $start, $close - $start)) . "`";
                    $index = $close + strlen($math_close);
                    continue;
                }
            }
            if ($text[$index] === "`") {
                $close = $this->findMark($text, "`", $index + 1);
                if ($close !== false) {
                    $html .= "`" . $this->escapeText(substr($text,
                        $index + 1, $close - $index - 1)) . "`";
                    $index = $close + 1;
                    continue;
                }
            }
            if (substr($text, $index, 2) === "{{") {
                $inline = $this->readInlineTemplate($text, $index);
                if ($inline !== null) {
                    $html .= $inline["html"];
                    $index = $inline["next"];
                    continue;
                }
            }
            $emphasis = $this->readEmphasis($text, $index);
            if ($emphasis !== null) {
                $html .= $emphasis["html"];
                $index = $emphasis["next"];
                continue;
            }
            if (substr($text, $index, 2) === "[[") {
                $close = $this->findMark($text, "]]", $index + 2);
                if ($close !== false) {
                    $html .= $this->renderLink(substr($text,
                        $index + 2, $close - $index - 2));
                    $index = $close + 2;
                    continue;
                }
            }
            $char = $this->utf8CharAt($text, $index);
            $html .= $this->escapeText($char);
            $index += strlen($char);
        }
        $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 <b>, </i>, or <br />, when one starts at the
     * given position. The tag may open or close, may carry a trailing
     * slash, and carries no attributes. Only the short allowed list is
     * passed through; the caller escapes anything else. This replaces a
     * regular expression with a direct read.
     *
     * @param string $text the block text being scanned
     * @param int $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
     */
    protected function matchInlineTag($text, $index)
    {
        $length = strlen($text);
        $cursor = $index;
        if ($cursor >= $length || $text[$cursor] !== "<") {
            return null;
        }
        $cursor++;
        if ($cursor < $length && $text[$cursor] === "/") {
            $cursor++;
        }
        $name_start = $cursor;
        while ($cursor < $length && ctype_alpha($text[$cursor])) {
            $cursor++;
        }
        $name = strtolower(substr($text, $name_start,
            $cursor - $name_start));
        if (!in_array($name, explode("|", self::INLINE_TAGS))) {
            return null;
        }
        while ($cursor < $length && ctype_space($text[$cursor])) {
            $cursor++;
        }
        if ($cursor < $length && $text[$cursor] === "/") {
            $cursor++;
        }
        if ($cursor >= $length || $text[$cursor] !== ">") {
            return null;
        }
        $cursor++;
        return substr($text, $index, $cursor - $index);
    }
    /**
     * 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 int $index the position to look at
     * @return array|null the span's html and the position after it, or
     *      null when no emphasis span starts here
     */
    protected function readEmphasis($text, $index)
    {
        $forms = ["'''''" => ["<b><i>", "</i></b>"],
            "'''" => ["<b>", "</b>"], "''" => ["<i>", "</i>"]];
        foreach ($forms as $mark => $tags) {
            $width = strlen($mark);
            if (substr($text, $index, $width) !== $mark) {
                continue;
            }
            $close = $this->findMark($text, $mark, $index + $width);
            if ($close === false) {
                continue;
            }
            $inner = substr($text, $index + $width,
                $close - $index - $width);
            return ["html" => $tags[0] . $this->renderInline($inner) .
                $tags[1], "next" => $close + $width];
        }
        return null;
    }
    /**
     * Renders one [[...]] link. A two-part link is page|shown; a three-part
     * link is relationship|page|shown and points at the page, its middle
     * part, not the leading relationship, which is instead recorded by
     * fetchLinks. A target whose scheme is on the allowlist, or that is a
     * same-page anchor, is used as written; a target that names another
     * group as group@page becomes an @@group@page@@ marker the view
     * resolves to that group's read url, since a library parser cannot look
     * a group id up; 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 [[ and the ]]
     * @return string the html anchor for the link
     */
    protected function renderLink($inner)
    {
        $bars = $this->topLevelBarPositions($inner);
        if (count($bars) === 2) {
            $target = trim(substr($inner, $bars[0] + 1,
                $bars[1] - $bars[0] - 1));
            $shown = substr($inner, $bars[1] + 1);
        } else if (count($bars) >= 1) {
            $target = trim(substr($inner, 0, $bars[0]));
            $shown = substr($inner, $bars[0] + 1);
        } else {
            $target = trim($inner);
            $shown = $inner;
        }
        $scheme = $this->linkScheme($target);
        if (isset($target[0]) && $target[0] === "#") {
            $href = $target;
        } else if (in_array($scheme, self::ALLOWED_LINK_SCHEMES)) {
            $href = $target;
        } else if (strpos($target, "@") !== false) {
            $href = "@@" . $target . "@@";
        } else {
            $href = $this->base_address . $this->linkPageAndLocale(
                $target);
        }
        return "<a href=\"" . $this->escapeText($href) . "\">" .
            $this->renderInline($shown) . "</a>";
    }
    /**
     * linkPageAndLocale reads a wiki link's 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's 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.
     *
     * The language is given back as the stand-in [{locale}] followed by
     * the tag, because the address this is joined to is itself a
     * stand-in here: the same parsed page becomes a group address, which
     * is a query, or a static page address, which is a path. Whoever
     * resolves the address resolves this too, with the separator its own
     * address wants, and turns it into page_locale, the field Yioop
     * reads a page's language from.
     *
     * @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,
     *      ready to follow the base address
     */
    protected function linkPageAndLocale($target)
    {
        $asked_at = strpos($target, "?");
        if ($asked_at === false) {
            return $target;
        }
        $name = substr($target, 0, $asked_at);
        $said = substr($target, $asked_at + 1);
        if (str_starts_with($said, "l=")) {
            $said = substr($said, 2);
        } else if (str_starts_with($said, "page_locale=")) {
            $said = substr($said, strlen("page_locale="));
        }
        if ($said === "" || !preg_match('/^[a-zA-Z\-_]{2,10}$/', $said)) {
            return $target;
        }
        return $name . "[{locale}]" . urlencode($said);
    }
    /**
     * Finds the byte offsets of the bars that separate a link's fields,
     * counting only the bars that sit at the top level of the link text.
     * A bar nested inside a resource ((...)), a template {{...}}, or an
     * inner link [[...]] belongs to that construct, not to the link, so
     * it is skipped. This lets a shown text such as a resource with its
     * own name-and-caption bar sit in a two-field link without being read
     * as the three-field relationship form.
     *
     * @param string $inner the text between the [[ and the ]]
     * @return array the offsets of the top-level bars, in order
     */
    protected function topLevelBarPositions($inner)
    {
        $positions = [];
        $length = strlen($inner);
        $paren = 0;
        $brace = 0;
        $bracket = 0;
        $index = 0;
        while ($index < $length) {
            $two = substr($inner, $index, 2);
            if ($two === "((") {
                $paren++;
                $index += 2;
                continue;
            }
            if ($two === "))") {
                if ($paren > 0) {
                    $paren--;
                }
                $index += 2;
                continue;
            }
            if ($two === "{{") {
                $brace++;
                $index += 2;
                continue;
            }
            if ($two === "}}") {
                if ($brace > 0) {
                    $brace--;
                }
                $index += 2;
                continue;
            }
            if ($two === "[[") {
                $bracket++;
                $index += 2;
                continue;
            }
            if ($two === "]]") {
                if ($bracket > 0) {
                    $bracket--;
                }
                $index += 2;
                continue;
            }
            if ($inner[$index] === "|" && $paren === 0 && $brace === 0 &&
                $bracket === 0) {
                $positions[] = $index;
            }
            $index++;
        }
        return $positions;
    }
    /**
     * Reads a link target's uri scheme, the name and colon that can lead a
     * web address such as the "https" in "https://example.com". A scheme
     * starts with a letter and may carry letters, digits, and a few
     * punctuation marks before its colon. This tells the link code whether
     * a target points off site rather than to another wiki page, without a
     * regular expression.
     *
     * @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
     */
    protected function linkScheme($target)
    {
        $length = strlen($target);
        if ($length === 0 || !ctype_alpha($target[0])) {
            return "";
        }
        $cursor = 1;
        while ($cursor < $length) {
            $char = $target[$cursor];
            if (ctype_alnum($char) || $char === "+" || $char === "." ||
                $char === "-") {
                $cursor++;
            } else {
                break;
            }
        }
        if ($cursor < $length && $target[$cursor] === ":") {
            return strtolower(substr($target, 0, $cursor));
        }
        return "";
    }
    /**
     * Escapes text so any html-special character in it is shown literally
     * rather than read as markup. An entity that is already escaped, such
     * as one an author wrote by hand to show a tag as an example, is left
     * as it is rather than escaped a second time, so it shows the tag it
     * stands for instead of the raw entity text.
     *
     * @param string $text the text to escape
     * @return string the escaped text
     */
    protected function escapeText($text)
    {
        return htmlspecialchars($text, ENT_QUOTES, "UTF-8", false);
    }
    /**
     * Escapes text that is being shown exactly as typed, inside a nowiki
     * span or a pre block, and additionally breaks up the "[{" that opens a
     * display-time token such as [{recent_places}]. Without this a token
     * shown as an example would still be swapped for its widget when the
     * page is drawn, because those swaps run over the finished html and
     * cannot see that the token sat inside nowiki. The broken opener still
     * shows as the two characters themselves.
     *
     * @param string $text the verbatim text to escape
     * @return string the escaped text with any token opener broken up
     */
    protected function 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 afterwards for resources and tokens,
           and without this a resource shown as an example would be drawn
           rather than shown. It reads the same on screen either way. The
           marks a front page uses are not broken here: they are read while
           the page is being scanned, so a mark inside nowiki never becomes
           one, and breaking it would show a writer something they did not
           type. */
        return str_replace(["[{", "(("], ["[&#123;", "(&#40;"],
            $this->escapeText($text));
    }
    /**
     * Returns the whole utf-8 character that begins at a byte offset, one
     * to four bytes wide as the character's lead byte says, so a multibyte
     * character is read and escaped as a unit rather than one byte at a
     * time. Escaping a lone byte of a multibyte character would drop it,
     * since that byte is not valid utf-8 on its own and htmlspecialchars
     * returns the empty string for it.
     *
     * @param string $text the text being read
     * @param int $index the byte offset the character begins at
     * @return string the character at that offset
     */
    protected function utf8CharAt($text, $index)
    {
        $lead = ord($text[$index]);
        if ($lead < self::UTF8_LEAD_TWO) {
            $width = 1;
        } else if ($lead < self::UTF8_LEAD_THREE) {
            $width = 2;
        } else if ($lead < self::UTF8_LEAD_FOUR) {
            $width = 3;
        } else {
            $width = 4;
        }
        return substr($text, $index, $width);
    }
    /**
     * Reads a template that sits inline in running text: a toggle link
     * that shows or hides a block, or a citation that becomes a numbered
     * footnote. Returns null for a {{ that starts some other template,
     * which the caller then leaves as text.
     *
     * @param string $text the block text being scanned
     * @param int $index the position of the opening {{
     * @return array|null the template's html and the position after it,
     *      or null when it is not an inline template
     */
    protected function readInlineTemplate($text, $index)
    {
        if ($this->findMark($text, "}}", $index + 2) === false) {
            return null;
        }
        $close = $this->matchBraces($text, $index);
        if ($close === false) {
            return null;
        }
        $inner = substr($text, $index + 2, $close - $index - 2);
        $next = $close + 2;
        $head = $this->readTemplateHead($inner);
        $name = $head["name"];
        $separator = $head["separator"];
        $rest = $head["rest"];
        $lower = strtolower($name);
        if ($separator === "|" && $name === "toggle") {
            $bar = strpos($rest, "|");
            if ($bar !== false) {
                return ["html" => "<a href=\"javascript:toggleDisplay('" .
                    $this->escapeText(trim(substr($rest, 0, $bar))) .
                    "')\">" .
                    $this->renderInline(substr($rest, $bar + 1)) .
                    "</a>", "next" => $next];
            }
        }
        if ($separator === "|" && (strpos($lower, "cite") === 0 ||
            strpos($lower, "vcite") === 0)) {
            return ["html" => $this->citeMarker($rest), "next" => $next];
        }
        if (($separator === "=" || $separator === ":") &&
            isset(self::BLOCK_ATTRIBUTE_DIRECTIVES[$lower])) {
            $parsed = $this->readQuotedValue($rest);
            if ($parsed !== null) {
                return ["html" => "<div " .
                    self::BLOCK_ATTRIBUTE_DIRECTIVES[$lower] . "=\"" .
                    $this->escapeText($parsed["value"]) . "\">" .
                    $this->renderInline($parsed["content"]) . "</div>",
                    "next" => $next];
            }
        }
        if (($separator === "=" || $separator === ":") &&
            ($name === "class" || $name === "id" || $name === "style")) {
            $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") {
            $token = $this->searchWidgetToken($rest);
            if ($token !== null) {
                return ["html" => $token, "next" => $next];
            }
        }
        $form = $this->readFormTemplate($inner);
        if ($form !== null) {
            return ["html" => $form, "next" => $next];
        }
        return null;
    }
    /**
     * Turns the body of a
     * <code>{{search:its|size:name|placeholder:text}}</code> tag into a
     * deferred search-box token. The real form cannot be built here because
     * a library parser has no page address or button helpers, so a
     * <code>[{search|its|size|text}]</code> token is left for the view
     * to fill in when the page is shown. Returns null when the three parts
     * are not all present.
     *
     * @param string $rest the tag body after "search:"
     * @return string|null the search token, or null when malformed
     */
    protected function searchWidgetToken($rest)
    {
        $parts = explode("|", $rest);
        if (count($parts) < 3) {
            return null;
        }
        $its = trim($parts[0]);
        $size = $this->afterFirstColon($parts[1]);
        $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. Used to read the value
     * out of a <code>name:value</code> tag part.
     *
     * @param string $part the tag part to read
     * @return string the value after the first colon
     */
    protected function afterFirstColon($part)
    {
        $colon = strpos($part, ":");
        if ($colon === false) {
            return trim($part);
        }
        return trim(substr($part, $colon + 1));
    }
    /**
     * Turns a form template into what a form page needs. Most name a form
     * action and become a bracketed marker the group controller later
     * fills in; a few emit the hidden or visible input a csv form field
     * needs. The name is read from the front of the braces and the rest is
     * its arguments, split on bars or, for the check forms, on double
     * bangs. Returns null when the braces are not a form template, so the
     * caller can try the next rule or show them as text.
     *
     * @param string $inner the text between the template's braces
     * @return string|null the form html or marker, or null when not a form
     */
    protected function readFormTemplate($inner)
    {
        $inner = trim($inner);
        $bar = strpos($inner, "|");
        $name = ($bar === false) ? $inner : substr($inner, 0, $bar);
        $name = trim($name);
        $rest = ($bar === false) ? "" : substr($inner, $bar + 1);
        $marker_names = ["require-signin" => "require-signin",
            "secret-ballot" => "secret-ballot", "presubmit" => "presubmit",
            "onsubmit" => "onsubmit", "share-edited-form" => "",
            "user-record-form" => "", "hash-record-form" => ""];
        if ($name === "category") {
            return "";
        }
        /* A page that collects what is filed under a name leaves a mark
           for the site to fill in once it knows which pages those are.
           Without this the words asking for a list stood on the page as
           words, since nothing turned them into the mark the site looks
           for. */
        if ($name === "category-names") {
            return "[{category-names|" . trim($rest) . "}]";
        }
        if ($name === "category-list" || $name === "lead-story") {
            /* Both are answered when the page is read rather than when it
               is written, since what they stand for depends on what else
               the group holds at that moment. */
            return "[{" . $name . "|" . trim($rest) . "}]";
        }
        if (isset($marker_names[$name])) {
            if ($marker_names[$name] === "") {
                return "[{" . $name . "}]";
            }
            return "[{" . $name . "|" . $rest . "}]";
        }
        if ($name === "alias" || $name === "a") {
            return "[{a~" . trim($rest) . "}]";
        }
        if ($name === "alias-def" || $name === "a-def") {
            return "[{a-def|" . $rest . "}]";
        }
        if ($name === "session-set" || $name === "s-set") {
            return "[{s-set|" . $rest . "}]";
        }
        if ($name === "session-unset" || $name === "s-unset") {
            return "[{s-unset|" . trim($rest) . "}]";
        }
        return $this->readCheckOrFieldTemplate($name, $rest, $inner);
    }
    /**
     * Handles the check forms and the csv form-field forms, the second and
     * larger half of the form templates. A check form re-wraps its
     * double-bang arguments as a marker; a field form emits the label,
     * input, and the hidden CSVFORM input that names the field's kind, with
     * a bracketed marker where the saved value goes. Returns null when the
     * name is not one of these.
     *
     * @param string $name the template's leading name
     * @param string $rest the text after the name and its first bar
     * @param string $inner the whole text between the braces
     * @return string|null the form html, or null when not one of these
     */
    protected function readCheckOrFieldTemplate($name, $rest, $inner)
    {
        if (strpos($inner, "!!") !== false) {
            $bang = explode("!!", $inner);
            $bang[0] = trim($bang[0]);
            if (in_array($bang[0],
                ["r-ck", "request-ck", "request-check"]) &&
                count($bang) >= 5) {
                return "[{r-ck!!" . $bang[1] . "!!" . $bang[2] . "!!" .
                    $bang[3] . "!!" . $bang[4] . "}]";
            }
            if (in_array($bang[0],
                ["s-ck", "session-ck", "session-check"]) &&
                count($bang) >= 5) {
                return "[{s-ck!!" . $bang[1] . "!!" . $bang[2] . "!!" .
                    $bang[3] . "!!" . $bang[4] . "}]";
            }
        }
        if (str_starts_with($name, "required-")) {
            $name = "r-" . substr($name, strlen("required-"));
        }
        $args = ($rest === "") ? [] : explode("|", $rest);
        $count = count($args);
        if ($name === "timestamp" || $name === "date") {
            $field = ($count === 0) ? $name : $args[0];
            $value = ($name === "date") ? date("r") : time();
            return "<input type='hidden' name='$field' value='$value' >" .
                $this->csvHidden($field, "textfield");
        }
        if ($name === "username") {
            $field = ($count === 0) ? "username" : $args[0];
            return "<input type='hidden' name='$field' " .
                "value='[{username}]' >" .
                $this->csvHidden($field, "textfield");
        }
        if ($name === "keyword-captcha" && $count >= 2) {
            return "<div class='csv-captcha'>[{keyword-captcha|" .
                $args[1] . "}]<label for='user_captcha_text'>" . $args[0] .
                "</label><input id='captcha-id' type='text' " .
                "name='user_captcha_text' value='[{csv-user_captcha_text}]'>" .
                "<span class='csv-star'>*</span></div>" .
                $this->csvHidden("user_captcha_text", "textfield");
        }
        if ($name === "textfield" || $name === "r-textfield") {
            $required = ($name === "r-textfield");
            $length = ($count >= 3) ? $args[2] : C\LONG_NAME_LEN;
            $kind = $required ? "r-textfield" : "textfield";
            $star = $required ? "<span class='csv-star'>*</span>" : "";
            return "<div class='csv-form-field'><label for='" . $args[1] .
                "-id'>" . $args[0] . "</label><input id='" . $args[1] .
                "-id' type='text' name='" . $args[1] . "' maxlength='" .
                $length . "' value='[{csv-" . $args[1] . "}]'>" .
                $this->csvHidden($args[1], $kind) . $star .
                "<span class='gray'  id='" . $args[1] . "-ctr' data-ctr='" .
                $args[1] . "-id'></span></div>";
        }
        if (($name === "textarea" || $name === "r-textarea") &&
            $count >= 2) {
            $required = ($name === "r-textarea");
            $kind = $required ? "r-textarea" : "textarea";
            $star = $required ? "<span class='csv-star'>*</span>" :
                "<br>";
            $count_field = $required ? "" : "data-count-field='true' ";
            return "<div class='csv-form-field'><label for='" . $args[1] .
                "-id'>" . $args[0] . "</label>$star<textarea id='" .
                $args[1] . "-id' name='" . $args[1] . "' " . $count_field .
                "class='short-text-area' maxlength='" .
                C\CVS_FORM_TEXTAREA_LEN . "'>[{csv-" . $args[1] .
                "}]</textarea><div class='gray align-opposite'  id='" .
                $args[1] . "-ctr' data-ctr='" . $args[1] . "-id'></div>" .
                $this->csvHidden($args[1], $kind) . "</div>";
        }
        if ($name === "data-block" && $count >= 1) {
            return "<x-data-block style='display:none' id='" . $args[0] .
                "' >";
        }
        if ($name === "end-data-block") {
            return "</x-data-block>";
        }
        if ($name === "dropdown" || $name === "r-dropdown") {
            $kind = ($name === "r-dropdown") ? "r-textfield" : "textfield";
            $block = ($count >= 2) ? " data-block='" . $args[1] . "'" : "";
            return "<div class='csv-form-field'>" .
                $this->csvHidden($args[0], $kind) . "<select name='" .
                $args[0] . "' data-value='[{csv-" . $args[0] . "}]'$block>";
        }
        if ($name === "sorter" || $name === "r-sorter") {
            $block = ($count >= 2) ? " data-block='" . $args[1] . "'" : "";
            $kind = ($count >= 2) ? "sorter" : "textfield";
            /* A field a page marks as required says so in what it
               writes down for itself, since that is what the site reads
               when the form comes back. Left off, a form asking for one
               of these was taken as filled in however empty it was. */
            $kind = ($name === "r-sorter") ? "r-" . $kind : $kind;
            return "<div class='csv-form-field'>" .
                $this->csvHidden($args[0], $kind) . "<select name='" .
                $args[0] . "' data-sortable='true' data-value='[{csv-" .
                $args[0] . "}]'$block>";
        }
        if ($name === "choosek" || $name === "r-choosek") {
            $kind = ($count >= 3) ? "choosek" : "textfield";
            $kind = ($name === "r-choosek") ? "r-" . $kind : $kind;
            $block = ($count >= 3) ? " data-block='" . $args[2] . "'" : "";
            $cutoff = ($count >= 2) ? " data-cutoff='" . $args[1] . "'" :
                "";
            return "<div class='csv-form-field'>" .
                $this->csvHidden($args[0], $kind) . "<select name='" .
                $args[0] . "' data-sortable='true' data-value='[{csv-" .
                $args[0] . "}]'$cutoff$block>";
        }
        if ($name === "option" && $count >= 2) {
            return "<option value='" . $args[1] . "'>" . $args[0] .
                "</option>";
        }
        if ($name === "end-dropdown" || $name === "end-choosek" ||
            $name === "end-sorter") {
            return "</select></div>";
        }
        if ($name === "end-r-dropdown" || $name === "end-r-choosek" ||
            $name === "end-r-sorter") {
            return "</select><span class='csv-star'>*</span></div>";
        }
        if ($name === "checkbox" || $name === "r-checkbox") {
            $kind = ($name === "r-checkbox") ? "r-checkbox" : "checkbox";
            return "<div class='csv-form-field'><label for='" . $args[1] .
                "-id'>" . $args[0] . "</label><input id='" . $args[1] .
                "-id' type='checkbox' name='" . $args[1] .
                "' [{csv-checked-" . $args[1] . "}] >" .
                $this->csvHidden($args[1], $kind) . "</div>";
        }
        if ($name === "lcheckbox" || $name === "r-lcheckbox") {
            $kind = ($name === "r-lcheckbox") ? "r-checkbox" : "checkbox";
            return "<div class='csv-form-field'><input id='" . $args[1] .
                "-id' type='checkbox' name='" . $args[1] .
                "' [{csv-checked-" . $args[1] . "}] ><label for='" .
                $args[1] . "-id'>" . $args[0] . "</label>" .
                $this->csvHidden($args[1], $kind) . "</div>";
        }
        if (($name === "radio" || $name === "r-radio") && $count >= 3) {
            $kind = ($name === "r-radio") ? "r-radio" : "radio";
            $star = ($name === "r-radio") ?
                "<span class='csv-star'>*</span>" : "";
            return "<div class='csv-form-field'><label for='" . $args[1] .
                "-" . $args[2] . "-id'>" . $args[0] . "</label><input id='" .
                $args[1] . "-" . $args[2] . "-id' type='radio' name='" .
                $args[1] . "' value='" . $args[2] . "' [{csv-checked-" .
                $args[1] . "}] >" . $this->csvHidden($args[1], $kind) .
                $star . "</div>";
        }
        if (($name === "lradio" || $name === "r-lradio") && $count >= 3) {
            $kind = ($name === "r-lradio") ? "r-radio" : "radio";
            $star = ($name === "r-lradio") ?
                "<span class='csv-star'>*</span>" : "";
            return "<div class='csv-form-field'><input id='" . $args[1] .
                "-" . $args[2] . "-id' type='radio' name='" . $args[1] .
                "' value='" . $args[2] . "' [{csv-checked-" . $args[1] .
                "}] ><label for='" . $args[1] . "-" . $args[2] . "-id'>" .
                $args[0] . "</label>" . $this->csvHidden($args[1], $kind) .
                $star . "</div>";
        }
        if ($name === "submit" && $count >= 2) {
            return "<div class='csv-form-field'><input id='" . $args[0] .
                "-id' type='submit' name='" . $args[1] . "' value='" .
                $args[0] . "' >" . $this->csvHidden($args[0], "submit") .
                "</div>";
        }
        return null;
    }
    /**
     * Builds the hidden input that tells the form handler what kind of
     * field a csv form field is, the piece every field form ends with.
     *
     * @param string $field the field's name
     * @param string $kind the field kind the handler expects
     * @return string the hidden input html
     */
    protected function csvHidden($field, $kind)
    {
        return "<input type='hidden' name='CSVFORM[$field]' " .
            "value='$kind' >";
    }
    /**
     * Turns one citation into a small numbered footnote marker and files
     * the citation away for the reference list. The marker links down to
     * the matching reference, which links back up to the marker.
     *
     * @param string $content the citation's fields, after the cite word
     * @return string the html footnote marker
     */
    protected function citeMarker($content)
    {
        $this->cite_references[] = $content;
        $number = count($this->cite_references);
        return "<sup id=\"cite_$number\"><a href=\"#ref_$number\">[" .
            $number . "]</a></sup>";
    }
    /**
     * Builds the reference list shown at the foot of a page from the
     * citations gathered while it rendered, or the empty string when
     * there were none. Each entry links back up to its footnote marker
     * and shows the citation's named fields.
     *
     * @return string the html reference list, or "" when there are none
     */
    protected function referenceList()
    {
        if (empty($this->cite_references)) {
            return "";
        }
        $shown_fields = ["title", "author", "publisher", "journal",
            "url", "quote"];
        $html = "<ol class=\"references\">\n";
        $number = 1;
        foreach ($this->cite_references as $reference) {
            $fields = [];
            foreach (explode("|", $reference) as $part) {
                $pair = explode("=", $part, 2);
                if (count($pair) === 2) {
                    $fields[strtolower(trim($pair[0]))] =
                        trim($pair[1]);
                }
            }
            $shown = [];
            foreach ($shown_fields as $field) {
                if (isset($fields[$field])) {
                    $shown[] = $this->renderInline($fields[$field]);
                }
            }
            $html .= "<li id=\"ref_$number\">" .
                "<a href=\"#cite_$number\">^</a> " .
                implode(", ", $shown) . "</li>\n";
            $number++;
        }
        return $html . "</ol>\n";
    }
    /**
     * Parse mediawiki to html
     *
     * @param string $document mediawiki string to parse
     * @param bool $draw_toc whether to inject a table-of-contents block
     *     before the parsed body (skipped for "presentation" pages)
     * @param string $page_type one of the wiki page-type strings (e.g.
     *     "standard", "presentation", "media_list"); affects layout
     *     decisions such as whether to draw the TOC
     * @param bool $handle_big_files whether to truncate documents that
     *     exceed MAX_GROUP_PAGE_LEN with a "..." suffix
     * @return string equivalent parsed html text
     */
    /**
     * Parse markdown text to html. The block structure &mdash; headings,
     * fenced code, block quotes, rules, lists, tables and paragraphs
     * &mdash; is read a line at a time with a scanner, and the inline run
     * inside a block is read a character at a time; no regular expression
     * is used. Wiki <code>{{...}}</code> templates are handed to the same
     * readers the wiki path uses, so a template behaves the same in a
     * markdown readme as on a wiki page. The flavor followed is GitHub's,
     * so a page written for GitHub renders the same way here.
     *
     * @param string $document markdown text to parse
     * @param bool $draw_toc whether to place a table of contents before
     *  the markdown page
     * @param string $page_type which kind of wiki page this is, so that a
     *  presentation is read as a run of slides rather than as one page
     * @return string equivalent parsed html text
     */
    public function parseMarkdown($document, $draw_toc = false,
        $page_type = "")
    {
        $this->parse_depth = 0;
        $this->collecting_headings = $draw_toc;
        $this->toc_headings = [];
        $this->markdown_references = [];
        $this->markdown_footnote_defs = [];
        $this->markdown_footnote_order = [];
        $this->markdown_footnote_numbers = [];
        $document = str_replace("\r\n", "\n", $document);
        $document = str_replace("\r", "\n", $document);
        $document = $this->collectMarkdownReferences($document);
        $scanner = new MarkUpScanner($document,
            self::MARKDOWN_BLOCK_START_CHARS);
        $html = ($page_type == "presentation") ?
            $this->parseMarkdownSlides($scanner) :
            $this->parseMarkdownBlocks($scanner);
        $html .= $this->markdownFootnotesSection();
        if ($draw_toc) {
            $html = $this->insertTableOfContents($html,
                $this->tableOfContents($this->toc_headings));
        }
        return $html;
    }
    /**
     * Builds the html for a markdown heading of a given level and text,
     * recording it for the table of contents. The anchor id is the heading
     * text with any inline markup stripped, the same scheme the wiki path
     * uses, so a contents entry and its heading share one anchor.
     *
     * @param int $level the heading level, one through six
     * @param string $text the raw heading text
     * @return string the heading html
     */
    protected function markdownHeadingHtml($level, $text)
    {
        $inline = $this->renderMarkdownInline($text);
        $anchor = strip_tags($inline);
        if ($this->collecting_headings) {
            $this->toc_headings[] = ["level" => $level, "text" => $anchor];
        }
        return "<h" . $level . " id=\"" . $anchor . "\">" . $inline .
            "</h" . $level . ">";
    }
    /**
     * Removes link and footnote definition lines from the markdown before
     * it is parsed, remembering each so a reference used anywhere on the
     * page can be resolved. Lines inside a fenced code block are left alone,
     * and a line indented as code is not treated as a definition, so real
     * code is never mistaken for one.
     *
     * @param string $document the markdown to scan for definitions
     * @return string the markdown with its definition lines removed
     */
    protected function collectMarkdownReferences($document)
    {
        $scanner = new MarkUpScanner($document,
            self::MARKDOWN_BLOCK_START_CHARS);
        $kept = [];
        $fence = "";
        while (!$scanner->atEnd()) {
            $line = $scanner->readLine();
            $trimmed = ltrim($line);
            if ($fence !== "") {
                $kept[] = $line;
                if (strpos($trimmed, $fence) === 0) {
                    $fence = "";
                }
                continue;
            }
            $open = $this->markdownFenceLength($trimmed);
            if ($open > 0) {
                $fence = str_repeat($trimmed[0], $open);
                $kept[] = $line;
                continue;
            }
            $definition = $this->matchMarkdownDefinition($line);
            if ($definition === null) {
                $kept[] = $line;
                continue;
            }
            if ($definition["type"] === "footnote") {
                if (!isset(
                    $this->markdown_footnote_defs[$definition["id"]])) {
                    $this->markdown_footnote_defs[$definition["id"]] =
                        $definition["text"];
                }
            } else if (!isset(
                $this->markdown_references[$definition["id"]])) {
                $this->markdown_references[$definition["id"]] =
                    ["url" => $definition["url"],
                    "title" => $definition["title"]];
            }
        }
        return implode("\n", $kept);
    }
    /**
     * Reads a link or footnote definition line, that is a bracketed name
     * followed by a colon and then a url and optional title for a link, or
     * the note's text for a footnote whose name opens with a caret. Returns
     * null when the line is not a definition.
     *
     * @param string $line the line to test
     * @return array|null the parsed definition, or null
     */
    protected function matchMarkdownDefinition($line)
    {
        if (strspn($line, " ") >= self::MARKDOWN_CODE_INDENT) {
            return null;
        }
        $trimmed = ltrim($line, " ");
        if (strlen($trimmed) < 4 || $trimmed[0] !== "[") {
            return null;
        }
        $close = strpos($trimmed, "]:");
        if ($close === false) {
            return null;
        }
        $label = substr($trimmed, 1, $close - 1);
        if ($label === "" || strpos($label, "[") !== false) {
            return null;
        }
        $rest = trim(substr($trimmed, $close + 2));
        if ($rest === "") {
            return null;
        }
        if ($label[0] === "^") {
            return ["type" => "footnote",
                "id" => strtolower(substr($label, 1)), "text" => $rest];
        }
        $url = $rest;
        $title = "";
        $space = strpos($rest, " ");
        if ($space !== false) {
            $url = substr($rest, 0, $space);
            $title = trim(substr($rest, $space + 1), " \"'");
        }
        return ["type" => "link", "id" => strtolower(trim($label)),
            "url" => $url, "title" => $title];
    }
    /**
     * Reads a footnote reference, that is a <code>[^name]</code> whose name
     * has a matching definition, and returns it as a small superscript link
     * down to the note. Returns null when there is no such definition, so
     * the brackets are read as an ordinary link or as text.
     *
     * @param string $text the inline text being read
     * @param int $index the offset of the opening bracket
     * @return array|null the html and offset past it, or null
     */
    protected function readMarkdownFootnoteRef($text, $index)
    {
        if (substr($text, $index, 2) !== "[^") {
            return null;
        }
        $close = $this->findMark($text, "]", $index + 2);
        if ($close === false) {
            return null;
        }
        $label = strtolower(substr($text, $index + 2, $close - $index - 2));
        if ($label === "" ||
            !isset($this->markdown_footnote_defs[$label])) {
            return null;
        }
        $safe = $this->escapeText($label);
        $number = $this->markdownFootnoteNumber($label);
        return ["html" => "<sup class=\"footnote-ref\"><a href=\"#fn-" .
            $safe . "\" id=\"fnref-" . $safe . "\">" . $number .
            "</a></sup>", "next" => $close + 1];
    }
    /**
     * The number a footnote is shown with, assigning the next number the
     * first time a footnote is referred to and reusing it after, so numbers
     * follow the order footnotes appear in the text.
     *
     * @param string $label the lower-cased footnote name
     * @return int the footnote's number
     */
    protected function markdownFootnoteNumber($label)
    {
        if (!isset($this->markdown_footnote_numbers[$label])) {
            $this->markdown_footnote_order[] = $label;
            $this->markdown_footnote_numbers[$label] =
                count($this->markdown_footnote_order);
        }
        return $this->markdown_footnote_numbers[$label];
    }
    /**
     * Builds the list of footnotes shown at the foot of the page, in the
     * order the footnotes were first referred to, each ending in a link
     * back up to where it was referred to. Returns an empty string when no
     * footnote was used.
     *
     * @return string the footnotes html, or empty when there are none
     */
    protected function markdownFootnotesSection()
    {
        if (empty($this->markdown_footnote_order)) {
            return "";
        }
        $items = "";
        foreach ($this->markdown_footnote_order as $label) {
            $safe = $this->escapeText($label);
            $note = $this->markdown_footnote_defs[$label] ?? "";
            $items .= "<li id=\"fn-" . $safe . "\">" .
                $this->renderMarkdownInline($note) . " <a href=\"#fnref-" .
                $safe . "\">&#8617;</a></li>\n";
        }
        return "\n<section class=\"footnotes\"><ol>\n" . $items .
            "</ol></section>";
    }
    /**
     * Reads a markdown document block by block from the scanner, turning
     * each block into html and joining the pieces with a blank line.
     * Reading stops going deeper once it has nested past the parser's depth
     * limit, handing the rest back as escaped text so nesting can never run
     * the call stack out.
     *
     * @param MarkUpScanner $scanner cursor over the markdown to read
     * @return string the html for every block read
     */
    /**
     * parseMarkdownSlides reads a whole markdown 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, the same
     * mark the wiki syntax uses, so a writer moving between the two
     * engines writes slides the same way. Each slide's own text is read
     * by the ordinary markdown block parse.
     *
     * @param MarkUpScanner $scanner the scanner at the start of the page
     * @return string the html for the whole deck
     */
    protected function parseMarkdownSlides($scanner)
    {
        $slides = "";
        while (!$scanner->atEnd()) {
            $slides .= "<x-slide>\n" .
                $this->parseMarkdownSlide($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";
    }
    /**
     * parseMarkdownSlide reads the markdown 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 the scanner at the slide's first line
     * @return string the html for that slide's blocks
     */
    protected function parseMarkdownSlide($scanner)
    {
        $blocks = [];
        while (!$scanner->atEnd()) {
            $scanner->skipBlankLines();
            if ($scanner->atEnd() || $this->atSlideBreak($scanner)) {
                break;
            }
            $block = $this->parseMarkdownBlock($scanner);
            if ($block !== "") {
                $blocks[] = $block;
            }
        }
        return implode("\n", $blocks) . "\n";
    }
    /**
     * parseMarkdownBlocks reads every markdown block from where the
     * scanner stands to the end of what it holds and joins their html
     * with newlines. The page body and every nested region, such as the
     * inside of a block quote, is read through here, so the depth is
     * counted and a page nested past the limit is left as plain text
     * rather than read for ever.
     *
     * @param MarkUpScanner $scanner the scanner at the first block
     * @return string the html for all the blocks read
     */
    protected function parseMarkdownBlocks($scanner)
    {
        $this->parse_depth++;
        if ($this->parse_depth > self::WIKI_MAX_PARSE_DEPTH) {
            $this->parse_depth--;
            return $this->escapeText($scanner->rest());
        }
        $blocks = [];
        while (!$scanner->atEnd()) {
            $scanner->skipBlankLines();
            if ($scanner->atEnd()) {
                break;
            }
            $block = $this->parseMarkdownBlock($scanner);
            if ($block !== "") {
                $blocks[] = $block;
            }
        }
        $this->parse_depth--;
        return implode("\n", $blocks);
    }
    /**
     * Reads one markdown block from the scanner and returns its html. The
     * kind of block is chosen from how the line at the cursor begins: a
     * fence opens code, a hash a heading, a greater-than sign a block
     * quote, a run of dashes stars or underscores a rule, a bullet or a
     * number a list, a bar with a divider row beneath it a table, a
     * wrapping template a template block, and anything else a paragraph.
     *
     * @param MarkUpScanner $scanner cursor over the markdown to read
     * @return string the html for the one block read
     */
    protected function parseMarkdownBlock($scanner)
    {
        $kind = $this->markdownBlockKind($scanner);
        if ($kind === "fence") {
            return $this->readMarkdownFence($scanner);
        }
        if ($kind === "heading") {
            return $this->readMarkdownHeading($scanner);
        }
        if ($kind === "quote") {
            return $this->readMarkdownBlockQuote($scanner);
        }
        if ($kind === "rule") {
            $scanner->readLine();
            return "<hr>";
        }
        if ($kind === "list") {
            return $this->readMarkdownList($scanner);
        }
        if ($kind === "template") {
            return $this->readMarkdownWrappedTemplate($scanner);
        }
        if ($kind === "blocktemplate") {
            return $this->readMarkdownTemplateBlock($scanner);
        }
        if ($kind === "spreadtemplate") {
            return $this->readMarkdownSpreadTemplate($scanner);
        }
        if ($kind === "table") {
            return $this->readMarkdownTable($scanner);
        }
        if ($kind === "indentcode") {
            return $this->readMarkdownIndentedCode($scanner);
        }
        if ($kind === "deflist") {
            return $this->readMarkdownDefinitionList($scanner);
        }
        return $this->readMarkdownParagraph($scanner);
    }
    /**
     * Names the kind of block that begins at the cursor without consuming
     * anything, used both to pick a reader and to tell whether a fresh line
     * inside a paragraph starts a new block. The names returned are fence,
     * heading, quote, rule, list, template, table, and paragraph.
     *
     * @param MarkUpScanner $scanner cursor over the markdown to inspect
     * @return string the block kind at the cursor
     */
    protected function markdownBlockKind($scanner)
    {
        $line = $this->peekMarkdownLine($scanner);
        /* A slide separator ends whatever block is being read. Named
           before the indent test, since a separator is a whole line of
           its own and nothing may take it as its continuation. */
        if (rtrim($line) === self::SLIDE_SEPARATOR) {
            return "slidebreak";
        }
        if (strspn($line, " ") >= self::MARKDOWN_CODE_INDENT ||
            (strlen($line) > 0 && $line[0] === "\t")) {
            return "indentcode";
        }
        $trimmed = ltrim($line);
        if ($this->markdownFenceLength($trimmed) > 0) {
            return "fence";
        }
        if ($this->markdownHeadingLevel($trimmed) > 0) {
            return "heading";
        }
        if (strlen($trimmed) > 0 && $trimmed[0] === ">") {
            return "quote";
        }
        if ($this->isMarkdownRule($trimmed)) {
            return "rule";
        }
        if ($this->markdownListMarker($line) !== null) {
            return "list";
        }
        if ($this->matchWrappedTemplateOpen(rtrim($line)) !== null) {
            return "template";
        }
        $template_inner = $this->markdownTemplateBlockInner($line);
        if ($template_inner !== null &&
            $this->readBlockTemplate($template_inner) !== null) {
            return "blocktemplate";
        }
        if ($this->markdownOpensTemplateBlock($scanner)) {
            return "spreadtemplate";
        }
        if ($this->isMarkdownTableStart($scanner)) {
            return "table";
        }
        /* A term with a colon line beneath it opens a definition list,
           which markdown's extended syntax writes that way round. */
        if (trim($line) !== "" &&
            $this->markdownDefinitionSays($line) === null &&
            $this->markdownDefinitionSays($scanner->peekLine(1)) !== null) {
            return "deflist";
        }
        return "paragraph";
    }
    /**
     * Returns the current line at the cursor without moving it, so a reader
     * can look at a line before deciding whether to consume it.
     *
     * @param MarkUpScanner $scanner cursor over the markdown to inspect
     * @return string the line the cursor is on, without its newline
     */
    protected function peekMarkdownLine($scanner)
    {
        return $scanner->peekLine();
    }
    /**
     * How many fence characters open a fenced code block at the start of a
     * line, or zero when the line is not a fence. A fence is three or more
     * back-ticks or tildes; a back-tick fence may not carry a back-tick in
     * its info string, which would otherwise close it at once.
     *
     * @param string $line the left-trimmed line to test
     * @return int the fence length, or zero when not a fence
     */
    protected function markdownFenceLength($line)
    {
        if ($line === "") {
            return 0;
        }
        $fence_char = $line[0];
        if ($fence_char !== "`" && $fence_char !== "~") {
            return 0;
        }
        $run = strspn($line, $fence_char);
        if ($run < self::MARKDOWN_MIN_FENCE) {
            return 0;
        }
        if ($fence_char === "`" &&
            strpos(substr($line, $run), "`") !== false) {
            return 0;
        }
        return $run;
    }
    /**
     * Reads a fenced code block from the cursor. The info word after the
     * opening fence, if any, names the language for a class. Every line up
     * to a closing fence of the same character and at least the opening
     * length is taken as code and escaped so it shows verbatim.
     *
     * @param MarkUpScanner $scanner cursor sitting on the opening fence
     * @return string the code block html
     */
    protected function readMarkdownFence($scanner)
    {
        $line = $scanner->readLine();
        $trimmed = ltrim($line);
        $fence_char = $trimmed[0];
        $fence_length = strspn($trimmed, $fence_char);
        $info = trim(substr($trimmed, $fence_length));
        $language = "";
        if ($info !== "") {
            $space = strpos($info, " ");
            $word = ($space === false) ? $info : substr($info, 0, $space);
            $language = " class=\"language-" . $this->escapeText($word) .
                "\"";
        }
        $lines = [];
        while (!$scanner->atEnd()) {
            $next = $this->peekMarkdownLine($scanner);
            $next_trimmed = ltrim($next);
            $run = strspn($next_trimmed, $fence_char);
            if ($run >= $fence_length &&
                rtrim(substr($next_trimmed, $run)) === "") {
                $scanner->readLine();
                break;
            }
            $lines[] = $scanner->readLine();
        }
        $code = implode("\n", $lines);
        return "<pre><code" . $language . ">" . $this->escapeText($code) .
            "</code></pre>";
    }
    /**
     * Reads an indented code block from the cursor: a run of lines each
     * indented at least four spaces or by a tab, with blank lines kept when
     * more code follows. The indent is removed and the lines are escaped so
     * they show verbatim.
     *
     * @param MarkUpScanner $scanner cursor sitting on the first code line
     * @return string the code block html
     */
    protected function readMarkdownIndentedCode($scanner)
    {
        $lines = [];
        while (!$scanner->atEnd()) {
            $line = $this->peekMarkdownLine($scanner);
            if (trim($line) === "") {
                $save = $scanner->tell();
                $scanner->readLine();
                $after = $this->peekMarkdownLine($scanner);
                if (strspn($after, " ") >= self::MARKDOWN_CODE_INDENT ||
                    (strlen($after) > 0 && $after[0] === "\t")) {
                    $lines[] = "";
                    continue;
                }
                $scanner->seek($save);
                break;
            }
            if (strspn($line, " ") < self::MARKDOWN_CODE_INDENT &&
                !(strlen($line) > 0 && $line[0] === "\t")) {
                break;
            }
            $lines[] = $this->stripMarkdownCodeIndent($scanner->readLine());
        }
        return "<pre><code>" . $this->escapeText(implode("\n", $lines)) .
            "</code></pre>";
    }
    /**
     * Removes one code-block indent from a line, that is a leading tab or up
     * to four leading spaces, leaving the rest of the line as it stands.
     *
     * @param string $line the code line to strip
     * @return string the line with one indent removed
     */
    protected function stripMarkdownCodeIndent($line)
    {
        if (strlen($line) > 0 && $line[0] === "\t") {
            return substr($line, 1);
        }
        return substr($line, min(self::MARKDOWN_CODE_INDENT,
            strspn($line, " ")));
    }
    /**
     * The level of an at-x heading (the leading-hash kind) at the start of
     * a line, or zero when the line is not one. One to six hashes followed
     * by a space or the line end open a heading of that level.
     *
     * @param string $line the left-trimmed line to test
     * @return int the heading level one through six, or zero
     */
    protected function markdownHeadingLevel($line)
    {
        $level = strspn($line, "#");
        if ($level < 1 || $level > self::MAX_HEADING_LEVEL) {
            return 0;
        }
        if (strlen($line) === $level || $line[$level] === " ") {
            return $level;
        }
        return 0;
    }
    /**
     * Reads an at-x heading from the cursor. The hashes set the level, any
     * closing hashes are dropped, the text is rendered inline, and the top
     * few levels are given an id built from the raw heading text so a table
     * of contents can link to them.
     *
     * @param MarkUpScanner $scanner cursor sitting on the heading line
     * @return string the heading html
     */
    protected function readMarkdownHeading($scanner)
    {
        $line = ltrim($scanner->readLine());
        $level = strspn($line, "#");
        $text = trim(substr($line, $level));
        $text = rtrim(rtrim($text, "#"));
        return $this->markdownHeadingHtml($level, $text);
    }
    /**
     * The level of a setext heading underline, that is a line of only
     * equals signs (level one) or only dashes (level two) that turns the
     * paragraph text above it into a heading, or zero when the line is not
     * such an underline.
     *
     * @param string $line the line beneath a paragraph to test
     * @return int one, two, or zero
     */
    protected function markdownSetextLevel($line)
    {
        $trimmed = rtrim($line);
        if (strlen($trimmed) === 0) {
            return 0;
        }
        if (strspn($trimmed, "=") === strlen($trimmed)) {
            return 1;
        }
        if (strspn($trimmed, "-") === strlen($trimmed)) {
            return 2;
        }
        return 0;
    }
    /**
     * Reads a block quote from the cursor. Each quoted line drops its
     * leading greater-than sign and one following space, and the gathered
     * lines are parsed as markdown in their own right so a quote may hold
     * paragraphs, lists, and more.
     *
     * @param MarkUpScanner $scanner cursor sitting on the first quote line
     * @return string the block quote html
     */
    protected function readMarkdownBlockQuote($scanner)
    {
        $lines = [];
        while (!$scanner->atEnd()) {
            $line = $this->peekMarkdownLine($scanner);
            $trimmed = ltrim($line);
            if ($trimmed === "" || $trimmed[0] !== ">") {
                break;
            }
            $scanner->readLine();
            $content = substr($trimmed, 1);
            if (strlen($content) > 0 && $content[0] === " ") {
                $content = substr($content, 1);
            }
            $lines[] = $content;
        }
        $inner = new MarkUpScanner(implode("\n", $lines),
            self::MARKDOWN_BLOCK_START_CHARS);
        return "<blockquote>" . $this->parseMarkdownBlocks($inner) .
            "</blockquote>";
    }
    /**
     * Whether a line is a horizontal rule: three or more dashes, stars, or
     * underscores of one kind, with any spaces between them ignored and
     * nothing else on the line.
     *
     * @param string $line the left-trimmed line to test
     * @return bool true when the line is a rule
     */
    protected function isMarkdownRule($line)
    {
        $stripped = str_replace(" ", "", rtrim($line));
        if (strlen($stripped) < self::MARKDOWN_MIN_FENCE) {
            return false;
        }
        $rule_char = $stripped[0];
        if ($rule_char !== "-" && $rule_char !== "*" && $rule_char !== "_") {
            return false;
        }
        return strspn($stripped, $rule_char) === strlen($stripped);
    }
    /**
     * Reads the marker of a list item at the start of a line, returning its
     * kind (ul for a bullet, ol for a number), the width of the marker, and
     * the count of spaces indenting it, or null when the line does not
     * begin a list item.
     *
     * @param string $line the line to test, leading spaces kept
     * @return array|null the marker description, or null when not a marker
     */
    protected function markdownListMarker($line)
    {
        $indent = strspn($line, " ");
        $rest = substr($line, $indent);
        if ($rest === "") {
            return null;
        }
        $bullet = $rest[0];
        if (($bullet === "-" || $bullet === "*" || $bullet === "+") &&
            (strlen($rest) === 1 || $rest[1] === " ")) {
            return ["type" => "ul", "width" => 1, "indent" => $indent];
        }
        $digits = strspn($rest, "0123456789");
        if ($digits > 0 && $digits < strlen($rest) &&
            ($rest[$digits] === "." || $rest[$digits] === ")") &&
            ($digits + 1 === strlen($rest) || $rest[$digits + 1] === " ")) {
            return ["type" => "ol", "width" => $digits + 1,
                "indent" => $indent];
        }
        return null;
    }
    /**
     * Reads a whole list from the cursor. Sibling items share the marker's
     * indent and kind; a blank line between items is allowed as long as the
     * list goes on afterward. Each item's body is handed to
     * readMarkdownListItem, which parses it as markdown so nested lists and
     * multi-line items come out right.
     *
     * @param MarkUpScanner $scanner cursor sitting on the first item
     * @return string the list html
     */
    protected function readMarkdownList($scanner)
    {
        $marker = $this->markdownListMarker(
            $this->peekMarkdownLine($scanner));
        $tag = $marker["type"];
        $base_indent = $marker["indent"];
        $items = [];
        while (!$scanner->atEnd()) {
            $line = $this->peekMarkdownLine($scanner);
            if (trim($line) === "") {
                $save = $scanner->tell();
                $scanner->skipBlankLines();
                $ahead = $this->markdownListMarker(
                    $this->peekMarkdownLine($scanner));
                if ($ahead === null || $ahead["indent"] !== $base_indent ||
                    $ahead["type"] !== $tag) {
                    $scanner->seek($save);
                    break;
                }
                continue;
            }
            $line_marker = $this->markdownListMarker($line);
            if ($line_marker === null ||
                $line_marker["indent"] !== $base_indent ||
                $line_marker["type"] !== $tag) {
                break;
            }
            $items[] = $this->readMarkdownListItem($scanner, $line_marker);
        }
        $html = "<" . $tag . ">\n";
        foreach ($items as $item) {
            $html .= "<li>" . $item . "</li>\n";
        }
        return $html . "</" . $tag . ">";
    }
    /**
     * Reads one list item from the cursor. The marker line's remainder and
     * any following lines indented under it form the item's body, which is
     * parsed as markdown. A body that comes out as a single paragraph is
     * unwrapped so a plain item does not gain a paragraph tag.
     *
     * @param MarkUpScanner $scanner cursor sitting on the item's marker line
     * @param array $marker the marker description from markdownListMarker
     * @return string the item body html
     */
    protected function readMarkdownListItem($scanner, $marker)
    {
        $indent = $marker["indent"];
        $content_indent = $indent + $marker["width"] + 1;
        $line = $scanner->readLine();
        $item_lines = [substr($line, min($content_indent, strlen($line)))];
        while (!$scanner->atEnd()) {
            $next = $this->peekMarkdownLine($scanner);
            if (trim($next) === "") {
                $save = $scanner->tell();
                $scanner->readLine();
                $after = $this->peekMarkdownLine($scanner);
                if (trim($after) !== "" &&
                    strspn($after, " ") >= $content_indent) {
                    $item_lines[] = "";
                    continue;
                }
                $scanner->seek($save);
                break;
            }
            $next_marker = $this->markdownListMarker($next);
            if ($next_marker !== null && $next_marker["indent"] <= $indent) {
                break;
            }
            if ($next_marker === null &&
                strspn($next, " ") < $content_indent) {
                break;
            }
            $line = $scanner->readLine();
            $item_lines[] = substr($line,
                min(strspn($line, " "), $content_indent));
        }
        $inner = new MarkUpScanner(implode("\n", $item_lines),
            self::MARKDOWN_BLOCK_START_CHARS);
        return $this->tightenMarkdownItem(
            $this->parseMarkdownBlocks($inner));
    }
    /**
     * Unwraps a list item body that is a single paragraph, dropping the
     * paragraph tags so a plain one-line item is not padded, while a body
     * with more than one block is left as it is.
     *
     * @param string $html the parsed item body
     * @return string the body, unwrapped when it is a lone paragraph
     */
    protected function tightenMarkdownItem($html)
    {
        $trimmed = trim($html);
        if (substr($trimmed, 0, 3) !== "<p>") {
            return $trimmed;
        }
        $close = strpos($trimmed, "</p>");
        if ($close === false) {
            return $trimmed;
        }
        $first = substr($trimmed, 3, $close - 3);
        if (strpos($first, "<p>") !== false) {
            return $trimmed;
        }
        return $first . substr($trimmed, $close + 4);
    }
    /**
     * Returns the text inside a standalone <code>{{...}}</code> template
     * that fills a whole line, or null when the line is not one template
     * from its first brace to its last. Used to tell a block-level template
     * such as a centered division from ordinary text.
     *
     * @param string $line the line to inspect
     * @return string|null the text between the braces, or null
     */
    protected function markdownTemplateBlockInner($line)
    {
        $trimmed = rtrim($line);
        if (substr($trimmed, 0, 2) !== "{{") {
            return null;
        }
        $close = $this->matchBraces($trimmed, 0);
        if ($close === false || $close + 2 !== strlen($trimmed)) {
            return null;
        }
        return substr($trimmed, 2, $close - 2);
    }
    /**
     * Says whether the line the cursor is on opens a template whose
     * braces close on a later line, as in a block-class laid out over
     * several lines with its words between. Such a form was left as
     * plain words, quotes and all, since only the one-line form was
     * looked for.
     *
     * @param MarkUpScanner $scanner cursor over the markdown
     * @return bool true when a template opens here and closes later
     */
    protected function markdownOpensTemplateBlock($scanner)
    {
        $line = rtrim($this->peekMarkdownLine($scanner));
        if (substr($line, 0, 2) !== "{{" || substr($line, -2) === "}}") {
            return false;
        }
        $mark = $scanner->tell();
        $found = false;
        $scanner->readLine();
        while (!$scanner->atEnd()) {
            if (rtrim($this->peekMarkdownLine($scanner)) === "}}") {
                $found = true;
                break;
            }
            $scanner->readLine();
        }
        $scanner->seek($mark);
        return $found &&
            $this->readBlockTemplate(substr($line, 2)) !== null;
    }
    /**
     * Reads a template whose braces close on a later line, wrapping
     * everything between in what the template asks for.
     *
     * @param MarkUpScanner $scanner cursor over the markdown
     * @return string the html of the wrapping
     */
    protected function readMarkdownSpreadTemplate($scanner)
    {
        $line = rtrim($scanner->readLine());
        $node = $this->readBlockTemplate(substr($line, 2));
        $gathered = "";
        while (!$scanner->atEnd()) {
            if (rtrim($this->peekMarkdownLine($scanner)) === "}}") {
                $scanner->readLine();
                break;
            }
            $gathered .= rtrim($scanner->readLine(), "\n") . "\n";
        }
        if ($node["type"] === "html") {
            return $node["html"];
        }
        $content = new MarkUpScanner($gathered,
            self::MARKDOWN_BLOCK_START_CHARS);
        return "<" . $node["tag"] . $node["attributes"] . ">\n" .
            $this->parseMarkdownBlocks($content) . "</" . $node["tag"] .
            ">";
    }
    /**
     * Reads a block-level <code>{{...}}</code> template from the cursor and
     * returns its html, using the same reader the wiki path uses so a
     * template behaves the same either way. A template that stands for
     * ready html emits that html; one that wraps content emits its tag
     * around the content parsed as markdown.
     *
     * @param MarkUpScanner $scanner cursor sitting on the template line
     * @return string the template html
     */
    protected function readMarkdownTemplateBlock($scanner)
    {
        $inner = $this->markdownTemplateBlockInner(
            $this->peekMarkdownLine($scanner));
        $scanner->readLine();
        $node = $this->readBlockTemplate($inner);
        if ($node["type"] === "html") {
            return $node["html"];
        }
        $content = new MarkUpScanner($node["content"],
            self::MARKDOWN_BLOCK_START_CHARS);
        return "<" . $node["tag"] . $node["attributes"] . ">\n" .
            $this->parseMarkdownBlocks($content) . "</" . $node["tag"] . ">";
    }
    /**
     * Reads a wrapping <code>{{block|...}}...{{end-block}}</code> or its
     * inline-span twin from the cursor, emitting a division or span with
     * the given id and style around its content. The content is parsed as
     * markdown, so markdown inside a wrapper renders as markdown rather than
     * as wiki text.
     *
     * @param MarkUpScanner $scanner cursor sitting on the opening line
     * @return string the wrapper html
     */
    protected function readMarkdownWrappedTemplate($scanner)
    {
        $open = $this->matchWrappedTemplateOpen($scanner->readLine());
        $tag = ($open["keyword"] === "inblock") ? "span" : "div";
        $end_marker = "{{end-" . $open["keyword"] . "}}";
        $lines = [];
        while (!$scanner->atEnd()) {
            $line = $scanner->readLine();
            if (rtrim($line) === $end_marker) {
                break;
            }
            $lines[] = $line;
        }
        $content = new MarkUpScanner(implode("\n", $lines),
            self::MARKDOWN_BLOCK_START_CHARS);
        return "<" . $tag . " id=\"" . $this->escapeText($open["id"]) .
            "\" style=\"" . $this->escapeText($open["style"]) . "\">\n" .
            $this->parseMarkdownBlocks($content) . "</" . $tag . ">";
    }
    /**
     * Whether a table begins at the cursor: the current line carries a bar
     * and the line just below it is a divider row of dashes and optional
     * colons, the shape GitHub uses to open a table.
     *
     * @param MarkUpScanner $scanner cursor to inspect without moving it
     * @return bool true when a table starts here
     */
    protected function isMarkdownTableStart($scanner)
    {
        $header = $scanner->peekLine(0);
        if (strpos($header, "|") === false) {
            return false;
        }
        return $this->isMarkdownTableDivider($scanner->peekLine(1));
    }
    /**
     * Whether a line is a table divider row, that is every cell is made of
     * dashes with an optional leading or trailing colon marking alignment
     * and nothing else.
     *
     * @param string $line the line to test
     * @return bool true when the line is a divider row
     */
    protected function isMarkdownTableDivider($line)
    {
        $trimmed = trim($line);
        if (strpos($trimmed, "-") === false ||
            strspn($trimmed, " |:-") !== strlen($trimmed)) {
            return false;
        }
        $cells = $this->splitTableRow($trimmed);
        foreach ($cells as $cell) {
            $cell = trim($cell);
            if ($cell === "" || strpos($cell, "-") === false ||
                strspn($cell, ":-") !== strlen($cell)) {
                return false;
            }
        }
        return count($cells) > 0;
    }
    /**
     * Splits a table row into its cells on unescaped bars, dropping a bar
     * at the very start or end so that both bordered and borderless rows
     * split the same way. A bar written as a backslash-bar is kept as a
     * literal bar in the cell.
     *
     * @param string $line the row to split
     * @return array the cells, still to be trimmed by the caller
     */
    protected function splitTableRow($line)
    {
        $line = trim($line);
        if (strlen($line) > 0 && $line[0] === "|") {
            $line = substr($line, 1);
        }
        if (strlen($line) > 0 && substr($line, -1) === "|") {
            $line = substr($line, 0, -1);
        }
        $cells = [];
        $current = "";
        $length = strlen($line);
        for ($i = 0; $i < $length; $i++) {
            if ($line[$i] === "\\" && $i + 1 < $length &&
                $line[$i + 1] === "|") {
                $current .= "|";
                $i++;
                continue;
            }
            if ($line[$i] === "|") {
                $cells[] = $current;
                $current = "";
                continue;
            }
            $current .= $line[$i];
        }
        $cells[] = $current;
        return $cells;
    }
    /**
     * Reads a table from the cursor. The first line gives the header cells,
     * the divider row gives each column's alignment, and the rows beneath
     * give the body until a blank line or a line without a bar. Cells are
     * rendered inline and padded or trimmed to the header's column count.
     *
     * @param MarkUpScanner $scanner cursor sitting on the header row
     * @return string the table html
     */
    protected function readMarkdownTable($scanner)
    {
        $headers = $this->splitTableRow($scanner->readLine());
        $dividers = $this->splitTableRow($scanner->readLine());
        $alignments = [];
        foreach ($dividers as $cell) {
            $cell = trim($cell);
            $left = (strlen($cell) > 0 && $cell[0] === ":");
            $right = (strlen($cell) > 0 && substr($cell, -1) === ":");
            if ($left && $right) {
                $alignments[] = " style=\"text-align:center\"";
            } else if ($right) {
                $alignments[] = " style=\"text-align:right\"";
            } else if ($left) {
                $alignments[] = " style=\"text-align:left\"";
            } else {
                $alignments[] = "";
            }
        }
        $column_count = count($headers);
        $html = "<table>\n<thead>\n<tr>";
        for ($i = 0; $i < $column_count; $i++) {
            $html .= "<th" . ($alignments[$i] ?? "") . ">" .
                $this->renderMarkdownInline(trim($headers[$i])) . "</th>";
        }
        $html .= "</tr>\n</thead>\n<tbody>\n";
        while (!$scanner->atEnd()) {
            $line = $this->peekMarkdownLine($scanner);
            if (trim($line) === "" || strpos($line, "|") === false) {
                break;
            }
            $cells = $this->splitTableRow($scanner->readLine());
            $html .= "<tr>";
            for ($i = 0; $i < $column_count; $i++) {
                $value = isset($cells[$i]) ? trim($cells[$i]) : "";
                $html .= "<td" . ($alignments[$i] ?? "") . ">" .
                    $this->renderMarkdownInline($value) . "</td>";
            }
            $html .= "</tr>\n";
        }
        return $html . "</tbody>\n</table>";
    }
    /**
     * Reads a paragraph from the cursor: it gathers lines up to a blank
     * line or a line that starts another kind of block. If the very next
     * line under the gathered text is a setext underline the paragraph
     * becomes a heading instead; otherwise the gathered text is rendered
     * inline and wrapped in a paragraph tag.
     *
     * @param MarkUpScanner $scanner cursor sitting on the paragraph's start
     * @return string the paragraph or setext-heading html
     */
    protected function readMarkdownParagraph($scanner)
    {
        $lines = [];
        while (!$scanner->atEnd()) {
            $line = $this->peekMarkdownLine($scanner);
            if (trim($line) === "") {
                break;
            }
            $level = $this->markdownSetextLevel(ltrim($line));
            if (count($lines) > 0 && $level > 0) {
                $scanner->readLine();
                return $this->markdownHeadingHtml($level,
                    trim(implode("\n", $lines)));
            }
            if (count($lines) > 0) {
                $kind = $this->markdownBlockKind($scanner);
                if ($kind !== "paragraph" && $kind !== "indentcode") {
                    break;
                }
            }
            $scanner->readLine();
            $lines[] = $line;
        }
        if (count($lines) === 0) {
            return "";
        }
        return "<p>" . $this->renderMarkdownInline(implode("\n", $lines)) .
            "</p>";
    }
    /**
     * Renders the inline run inside a block a character at a time, with no
     * regular expression: back-tick code, dollar-sign math, emphasis in
     * stars underscores and double tildes, links and images, angle-bracket
     * autolinks and the passed-through inline tags, wiki
     * <code>{{...}}</code> templates, a two-space line break, and backslash
     * escapes. Everything else is escaped so it shows as written. The run
     * counts against the parser's depth limit and bails to escaped text
     * past it.
     *
     * @param string $text the inline text of a block
     * @return string the html for the inline run
     */
    protected function renderMarkdownInline($text)
    {
        $this->parse_depth++;
        if ($this->parse_depth > self::WIKI_MAX_PARSE_DEPTH) {
            $this->parse_depth--;
            return $this->escapeText($text);
        }
        $nodes = $this->markdownInlineNodes($text);
        $html = $this->resolveMarkdownEmphasis($nodes);
        $this->parse_depth--;
        return $html;
    }
    /**
     * Breaks a run of inline markdown into a list of nodes. Everything but
     * emphasis is turned into a finished piece of html right away; a run of
     * emphasis stars or underscores becomes a delimiter node carrying
     * whether it may open or close, to be matched up afterwards by the
     * delimiter-stack pass the way GitHub's markdown does.
     *
     * @param string $text the inline markdown to break up
     * @return array the list of text and delimiter nodes
     */
    protected function markdownInlineNodes($text)
    {
        $nodes = [];
        $length = strlen($text);
        $index = 0;
        $saved_absent = $this->inline_absent;
        $saved_bracket = $this->bracket_match;
        $saved_paren = $this->paren_match;
        $this->inline_absent = [];
        $this->buildInlineBrackets($text);
        while ($index < $length) {
            $char = $text[$index];
            if ($char === "\\" && $index + 1 < $length &&
                strpos(self::MARKDOWN_ESCAPABLE, $text[$index + 1]) !==
                false) {
                $nodes[] = ["type" => "text",
                    "html" => $this->escapeText($text[$index + 1])];
                $index += 2;
                continue;
            }
            if ($char === " ") {
                $spaces = strspn($text, " ", $index);
                if ($index + $spaces < $length &&
                    $text[$index + $spaces] === "\n" && $spaces >= 2) {
                    $nodes[] = ["type" => "text", "html" => "<br>"];
                    $index += $spaces;
                    continue;
                }
            }
            if ($char === "`") {
                $parsed = $this->readMarkdownCode($text, $index);
                if ($parsed !== null) {
                    $nodes[] = ["type" => "text", "html" => $parsed["html"]];
                    $index = $parsed["next"];
                    continue;
                }
            }
            if ($char === "$") {
                $close = $this->findMark($text, "$", $index + 1);
                if ($close !== false && $close > $index + 1) {
                    $nodes[] = ["type" => "text", "html" => "<code>" .
                        $this->escapeText(substr($text, $index + 1,
                        $close - $index - 1)) . "</code>"];
                    $index = $close + 1;
                    continue;
                }
            }
            if ($char === "!" && $index + 1 < $length &&
                $text[$index + 1] === "[") {
                $parsed = $this->readMarkdownLink($text, $index + 1, true);
                if ($parsed !== null) {
                    $nodes[] = ["type" => "text", "html" => $parsed["html"]];
                    $index = $parsed["next"];
                    continue;
                }
            }
            if ($char === "[") {
                $footnote = $this->readMarkdownFootnoteRef($text, $index);
                if ($footnote !== null) {
                    $nodes[] = ["type" => "text",
                        "html" => $footnote["html"]];
                    $index = $footnote["next"];
                    continue;
                }
                $parsed = $this->readMarkdownLink($text, $index, false);
                if ($parsed !== null) {
                    $nodes[] = ["type" => "text", "html" => $parsed["html"]];
                    $index = $parsed["next"];
                    continue;
                }
            }
            if ($char === "<") {
                $parsed = $this->readMarkdownAutolink($text, $index);
                if ($parsed !== null) {
                    $nodes[] = ["type" => "text", "html" => $parsed["html"]];
                    $index = $parsed["next"];
                    continue;
                }
                $tag = $this->matchInlineTag($text, $index);
                if ($tag !== null) {
                    $nodes[] = ["type" => "text", "html" => $tag];
                    $index += strlen($tag);
                    continue;
                }
            }
            if ($char === "{" && $index + 1 < $length &&
                $text[$index + 1] === "{") {
                $parsed = $this->readInlineTemplate($text, $index);
                if ($parsed !== null) {
                    $nodes[] = ["type" => "text", "html" => $parsed["html"]];
                    $index = $parsed["next"];
                    continue;
                }
            }
            if ($char === "~") {
                $parsed = $this->readMarkdownStrike($text, $index);
                if ($parsed !== null) {
                    $nodes[] = ["type" => "text", "html" => $parsed["html"]];
                    $index = $parsed["next"];
                    continue;
                }
            }
            if ($char === "*" || $char === "_") {
                $run = strspn($text, $char, $index);
                $nodes[] = ["type" => "delim", "cc" => $char,
                    "length" => $run, "orig" => $run,
                    "can_open" => $this->markdownCanOpen($text, $index,
                        $run, $char),
                    "can_close" => $this->markdownCanClose($text, $index,
                        $run, $char), "in_stack" => true];
                $index += $run;
                continue;
            }
            $nodes[] = ["type" => "text",
                "html" => $this->escapeText($char)];
            $index++;
        }
        $this->inline_absent = $saved_absent;
        $this->bracket_match = $saved_bracket;
        $this->paren_match = $saved_paren;
        return $nodes;
    }
    /**
     * Reads an inline code span that opens at the cursor with a run of
     * back-ticks and closes at the next run of the same length. One leading
     * and trailing space is dropped and the middle is escaped. Returns null
     * when there is no closing run so the back-ticks show as text.
     *
     * @param string $text the inline text being read
     * @param int $index the offset of the opening back-tick run
     * @return array|null the html and the offset past the span, or null
     */
    protected function readMarkdownCode($text, $index)
    {
        $run = strspn($text, "`", $index);
        $fence = str_repeat("`", $run);
        $close = $this->findMark($text, $fence, $index + $run);
        if ($close === false) {
            return null;
        }
        $code = substr($text, $index + $run, $close - $index - $run);
        if (strlen($code) > 1 && $code[0] === " " &&
            substr($code, -1) === " ") {
            $code = substr($code, 1, -1);
        }
        return ["html" => "<code>" . $this->escapeText($code) . "</code>",
            "next" => $close + $run];
    }
    /**
     * Reads a link or an image whose label opens at the cursor. Nested
     * square brackets in the label are matched so a label may itself hold
     * brackets, the destination and an optional quoted title follow in
     * parentheses, and an unsafe destination scheme is dropped. Returns null
     * when the shape is not a link so the bracket shows as text.
     *
     * @param string $text the inline text being read
     * @param int $index the offset of the opening square bracket
     * @param bool $is_image whether an image was asked for rather than a link
     * @return array|null the html and the offset past it, or null
     */
    protected function readMarkdownLink($text, $index, $is_image)
    {
        $length = strlen($text);
        $label_end = $this->bracket_match[$index] ?? -1;
        if ($label_end === -1) {
            return null;
        }
        $label = substr($text, $index + 1, $label_end - $index - 1);
        if ($label_end + 1 < $length && $text[$label_end + 1] === "(") {
            return $this->readMarkdownInlineLink($text, $label,
                $label_end + 1, $is_image);
        }
        return $this->readMarkdownReferenceLink($text, $label,
            $label_end + 1, $is_image);
    }
    /**
     * Reads the parenthesized destination and optional title of an inline
     * link or image whose label has already been read, matching balanced
     * parentheses so a destination may hold its own parentheses.
     *
     * @param string $text the inline text being read
     * @param string $label the link or image label
     * @param int $paren_start the offset of the opening parenthesis
     * @param bool $is_image whether an image was asked for
     * @return array|null the html and offset past it, or null
     */
    protected function readMarkdownInlineLink($text, $label, $paren_start,
        $is_image)
    {
        $paren_end = $this->paren_match[$paren_start] ?? -1;
        if ($paren_end === -1) {
            return null;
        }
        $target = trim(substr($text, $paren_start + 1,
            $paren_end - $paren_start - 1));
        $title = "";
        $space = strpos($target, " ");
        if ($space !== false) {
            $title = trim(substr($target, $space + 1), " \"'");
            $target = substr($target, 0, $space);
        }
        return $this->buildMarkdownLink($label, $target, $title, $is_image,
            $paren_end + 1);
    }
    /**
     * Resolves a reference link or image, that is a label backed by a
     * definition given elsewhere in the document. The reference name is a
     * following <code>[name]</code>, or the label itself when that is
     * empty or absent. Returns null when no matching definition was
     * collected, so the brackets show as text.
     *
     * @param string $text the inline text being read
     * @param string $label the link or image label
     * @param int $after the offset just past the label's closing bracket
     * @param bool $is_image whether an image was asked for
     * @return array|null the html and offset past it, or null
     */
    protected function readMarkdownReferenceLink($text, $label, $after,
        $is_image)
    {
        $length = strlen($text);
        $reference_id = $label;
        $next = $after;
        if ($after < $length && $text[$after] === "[") {
            $close = strpos($text, "]", $after + 1);
            if ($close === false) {
                return null;
            }
            $inner = substr($text, $after + 1, $close - $after - 1);
            if (trim($inner) !== "") {
                $reference_id = $inner;
            }
            $next = $close + 1;
        }
        $key = strtolower(trim($reference_id));
        if (!isset($this->markdown_references[$key])) {
            return null;
        }
        $reference = $this->markdown_references[$key];
        return $this->buildMarkdownLink($label, $reference["url"],
            $reference["title"], $is_image, $next);
    }
    /**
     * Builds the html for a link or image from its label, destination,
     * title, and the offset to resume reading at, sanitizing the
     * destination and rendering a link's label inline.
     *
     * @param string $label the link or image label
     * @param string $target the destination read from the markdown
     * @param string $title the title, or empty when there is none
     * @param bool $is_image whether an image was asked for
     * @param int $next the offset just past what was read
     * @return array the html and offset past it
     */
    protected function buildMarkdownLink($label, $target, $title, $is_image,
        $next)
    {
        $title_attribute = ($title !== "") ? " title=\"" .
            $this->escapeText($title) . "\"" : "";
        if ($is_image) {
            return ["html" => "<img src=\"" . $this->markdownUrl($target) .
                "\" alt=\"" . $this->escapeText($label) . "\"" .
                $title_attribute . ">", "next" => $next];
        }
        return ["html" => "<a href=\"" . $this->markdownUrl($target, true) .
            "\"" . $title_attribute . ">" .
            $this->renderMarkdownInline($label) .
            "</a>", "next" => $next];
    }
    /**
     * Reads an angle-bracket autolink at the cursor, that is a bare url or
     * email address wrapped in angle brackets, and returns it as a link.
     * An email address is given a mailto destination. Returns null when the
     * brackets do not hold a url or address so a tag reader can try next.
     *
     * @param string $text the inline text being read
     * @param int $index the offset of the opening angle bracket
     * @return array|null the html and the offset past it, or null
     */
    protected function readMarkdownAutolink($text, $index)
    {
        $close = $this->findMark($text, ">", $index + 1);
        if ($close === false) {
            return null;
        }
        $inner = substr($text, $index + 1, $close - $index - 1);
        if ($inner === "" || strpos($inner, " ") !== false ||
            strpos($inner, "<") !== false) {
            return null;
        }
        $scheme = $this->linkScheme($inner);
        $is_email = ($scheme === "" && strpos($inner, "@") !== false &&
            strpos($inner, ".") !== false);
        if ($scheme === "" && !$is_email) {
            return null;
        }
        $href = $is_email ? ("mailto:" . $inner) : $inner;
        return ["html" => "<a href=\"" . $this->escapeText($href) . "\">" .
            $this->escapeText($inner) . "</a>", "next" => $close + 1];
    }
    /**
     * Reads an emphasis run that opens at the cursor. One star or
     * underscore gives italics, two give bold, and two tildes give
     * strike-through; the run closes at the next matching marker and its
     * body is rendered inline. Returns null when nothing closes it so the
     * marker shows as text.
     *
     * @param string $text the inline text being read
     * @param int $index the offset of the opening marker
     * @return array|null the html and the offset past it, or null
     */
    protected function readMarkdownStrike($text, $index)
    {
        $run = strspn($text, "~", $index);
        if ($run < 1 || $run > 2 ||
            !$this->markdownCanOpen($text, $index, $run, "~")) {
            return null;
        }
        $open = str_repeat("~", $run);
        $length = strlen($text);
        $scan = $index + $run;
        while ($scan < $length) {
            $close = $this->findMark($text, $open, $scan);
            if ($close === false) {
                return null;
            }
            if (strspn($text, "~", $close) === $run &&
                $this->markdownCanClose($text, $close, $run, "~")) {
                $inner = substr($text, $index + $run,
                    $close - $index - $run);
                if (trim($inner) === "") {
                    return null;
                }
                return ["html" => "<del>" .
                    $this->renderMarkdownInline($inner) . "</del>",
                    "next" => $close + $run];
            }
            $scan = $close + 1;
        }
        return null;
    }
    /**
     * Matches up the emphasis delimiters in a node list and returns the
     * finished html. This is GitHub markdown's delimiter-stack pass: each
     * closing run is paired with the nearest earlier opening run of the same
     * character, skipping a pairing the rule of three forbids, wrapping what
     * lies between in <em> or <strong>, and taking two characters at a time
     * so a triple run nests emphasis inside strong. Leftover delimiter
     * characters are shown as plain text.
     *
     * @param array $nodes the text and delimiter nodes to resolve
     * @return string the finished inline html
     */
    protected function resolveMarkdownEmphasis($nodes)
    {
        $count = count($nodes);
        if ($count === 0) {
            return "";
        }
        $next = [];
        $prev = [];
        $delims = [];
        for ($i = 0; $i < $count; $i++) {
            $next[$i] = ($i + 1 < $count) ? $i + 1 : -1;
            $prev[$i] = $i - 1;
            if ($nodes[$i]["type"] === "delim") {
                $delims[] = $i;
            }
        }
        $this->processMarkdownDelimiters($nodes, $next, $prev, $delims);
        $html = "";
        $node = 0;
        while ($node !== -1) {
            $current = $nodes[$node];
            if ($current["type"] === "text") {
                $html .= $current["html"];
            } else if ($current["length"] > 0) {
                $html .= str_repeat($current["cc"], $current["length"]);
            }
            $node = $next[$node];
        }
        return $html;
    }
    /**
     * Walks the delimiter runs from left to right pairing each closer with
     * an opener, the heart of the emphasis pass. The <em> and <strong> tags
     * are spliced into the node list around each match, and a lower bound
     * per character and run length keeps the search from repeatedly
     * rescanning openers that cannot match.
     *
     * @param array &$nodes the node list, extended with tag nodes
     * @param array &$next each node's following node, by node index
     * @param array &$prev each node's preceding node, by node index
     * @param array $delims the indices of the delimiter nodes, in order
     * @return void
     */
    protected function processMarkdownDelimiters(&$nodes, &$next, &$prev,
        $delims)
    {
        $openers_bottom = [];
        $closer_i = 0;
        $delim_count = count($delims);
        while ($closer_i < $delim_count) {
            $closer = $delims[$closer_i];
            if (!$nodes[$closer]["in_stack"] ||
                !$nodes[$closer]["can_close"] ||
                $nodes[$closer]["length"] === 0) {
                $closer_i++;
                continue;
            }
            $cc = $nodes[$closer]["cc"];
            $mod = $nodes[$closer]["orig"] % 3;
            $bottom = $openers_bottom[$cc][$mod] ?? -1;
            $opener_i = $closer_i - 1;
            $found = false;
            while ($opener_i > $bottom) {
                $opener = $delims[$opener_i];
                if ($nodes[$opener]["in_stack"] &&
                    $nodes[$opener]["can_open"] &&
                    $nodes[$opener]["length"] > 0 &&
                    $nodes[$opener]["cc"] === $cc) {
                    $either_both = $nodes[$closer]["can_open"] ||
                        $nodes[$opener]["can_close"];
                    $odd = $either_both &&
                        ($nodes[$closer]["orig"] % 3 !== 0) &&
                        (($nodes[$opener]["orig"] +
                        $nodes[$closer]["orig"]) % 3 === 0);
                    if (!$odd) {
                        $found = true;
                        break;
                    }
                }
                $opener_i--;
            }
            if (!$found) {
                $openers_bottom[$cc][$mod] = $closer_i - 1;
                if (!$nodes[$closer]["can_open"]) {
                    $nodes[$closer]["in_stack"] = false;
                }
                $closer_i++;
                continue;
            }
            $opener = $delims[$opener_i];
            $use = ($nodes[$opener]["length"] >= 2 &&
                $nodes[$closer]["length"] >= 2) ? 2 : 1;
            $tag = ($use === 2) ? "strong" : "em";
            $open_marker = count($nodes);
            $nodes[] = ["type" => "text", "html" => "<" . $tag . ">"];
            $close_marker = count($nodes);
            $nodes[] = ["type" => "text", "html" => "</" . $tag . ">"];
            $this->spliceMarkdownAfter($next, $prev, $opener, $open_marker);
            $this->spliceMarkdownBefore($next, $prev, $closer,
                $close_marker);
            $nodes[$opener]["length"] -= $use;
            $nodes[$closer]["length"] -= $use;
            for ($between = $opener_i + 1; $between < $closer_i;
                $between++) {
                $nodes[$delims[$between]]["in_stack"] = false;
            }
            if ($nodes[$opener]["length"] === 0) {
                $nodes[$opener]["in_stack"] = false;
            }
            if ($nodes[$closer]["length"] === 0) {
                $nodes[$closer]["in_stack"] = false;
                $closer_i++;
            }
        }
    }
    /**
     * Links a new node into the list just after a given node.
     *
     * @param array &$next each node's following node, by node index
     * @param array &$prev each node's preceding node, by node index
     * @param int $reference the node to insert after
     * @param int $inserted the new node's index
     * @return void
     */
    protected function spliceMarkdownAfter(&$next, &$prev, $reference,
        $inserted)
    {
        $after = $next[$reference];
        $next[$reference] = $inserted;
        $prev[$inserted] = $reference;
        $next[$inserted] = $after;
        if ($after !== -1) {
            $prev[$after] = $inserted;
        }
    }
    /**
     * Links a new node into the list just before a given node.
     *
     * @param array &$next each node's following node, by node index
     * @param array &$prev each node's preceding node, by node index
     * @param int $reference the node to insert before
     * @param int $inserted the new node's index
     * @return void
     */
    protected function spliceMarkdownBefore(&$next, &$prev, $reference,
        $inserted)
    {
        $before = $prev[$reference];
        $prev[$reference] = $inserted;
        $next[$inserted] = $reference;
        $prev[$inserted] = $before;
        if ($before !== -1) {
            $next[$before] = $inserted;
        }
    }
    /**
     * Describes a run of emphasis characters by whether the run can sit at
     * the left or right edge of emphasized text, the left-flanking and
     * right-flanking tests markdown uses to tell an opening marker from a
     * closing one, along with whether the characters just outside the run
     * are punctuation.
     *
     * @param string $text the inline text being read
     * @param int $start the offset of the run
     * @param int $length how many marker characters the run has
     * @return array the left, right, before-punctuation, and
     *      after-punctuation flags
     */
    protected function markdownFlanking($text, $start, $length)
    {
        $before = ($start > 0) ? $text[$start - 1] : " ";
        $after_index = $start + $length;
        $after = ($after_index < strlen($text)) ?
            $text[$after_index] : " ";
        $before_space = ($before === " " || $before === "\n" ||
            $before === "\t");
        $after_space = ($after === " " || $after === "\n" ||
            $after === "\t");
        $before_punct = ctype_punct($before);
        $after_punct = ctype_punct($after);
        $left = !$after_space &&
            (!$after_punct || $before_space || $before_punct);
        $right = !$before_space &&
            (!$before_punct || $after_space || $after_punct);
        return ["left" => $left, "right" => $right,
            "before_punct" => $before_punct, "after_punct" => $after_punct];
    }
    /**
     * Whether an emphasis run may open emphasis. A star run opens when it is
     * left-flanking; an underscore run must also not be inside a word, so a
     * name written with underscores is left alone.
     *
     * @param string $text the inline text being read
     * @param int $start the offset of the run
     * @param int $length how many marker characters the run has
     * @param string $marker the run's character
     * @return bool true when the run may open emphasis
     */
    protected function markdownCanOpen($text, $start, $length, $marker)
    {
        $flank = $this->markdownFlanking($text, $start, $length);
        if ($marker === "_") {
            return $flank["left"] &&
                (!$flank["right"] || $flank["before_punct"]);
        }
        return $flank["left"];
    }
    /**
     * Whether an emphasis run may close emphasis. A star run closes when it
     * is right-flanking; an underscore run must also not be inside a word,
     * the mirror of the opening test.
     *
     * @param string $text the inline text being read
     * @param int $start the offset of the run
     * @param int $length how many marker characters the run has
     * @param string $marker the run's character
     * @return bool true when the run may close emphasis
     */
    protected function markdownCanClose($text, $start, $length, $marker)
    {
        $flank = $this->markdownFlanking($text, $start, $length);
        if ($marker === "_") {
            return $flank["right"] &&
                (!$flank["left"] || $flank["after_punct"]);
        }
        return $flank["right"];
    }
    /**
     * Turns a link or image destination into a safe, escaped url. A
     * destination whose scheme could run script or read a local file is
     * dropped to an empty destination. For a link (not an image) a
     * group@page destination becomes an @@group@page@@ marker the view
     * resolves to that group's read url at display time, the same as a
     * mediawiki [[group@page]] link; anything else is escaped so it can sit
     * in an attribute.
     *
     * @param string $target the raw destination read from the markdown
     * @param bool $is_link whether the destination is a link, as opposed to
     *      an image, so the cross-group marker is only formed for links
     * @return string the escaped destination, or empty when unsafe
     */
    protected function markdownUrl($target, $is_link = false)
    {
        $scheme = $this->linkScheme($target);
        $unsafe = ["javascript", "vbscript", "data", "file"];
        if ($scheme !== "" && in_array($scheme, $unsafe)) {
            return "";
        }
        if ($is_link && $scheme === "" &&
            (!isset($target[0]) || $target[0] !== "#") &&
            strpos($target, "@") !== false) {
            return $this->escapeText("@@" . $target . "@@");
        }
        return $this->escapeText($target);
    }
    /**
     * Replaces with underscores, links with spaces, fixes newline issues
     * within span tags
     * @param string $document wiki document to fix
     * @param string $page_name name of the page being scanned, so a
     *      category tag files that page under the category
     * @return string document after substitutions
     */
    /**
     * Used to make a reference list for a wiki page based on the
     * cite tags on that page.
     *
     * @param string $page a wiki document
     * @return string HTML reference list to be inserted after wiki
     *     page processed
     */
    /**
     * After regex processing has been done on a wiki page this function
     * inserts into the resulting page a table of contents just before
     * the first h2 tag, then returns the result page
     *
     * @param string $page page in which to insert table of contents
     * @param string $toc HTML table of contents
     * @return string resulting page after insert
     */
    public function insertTableOfContents($page, $toc)
    {
        $pos = strpos($page, "<h2");
        if ($pos !== false) {
            $start = substr($page, 0, $pos);
            $end = substr($page, $pos);
            $page = $start . $toc. $end;
        }
        return $page;
    }
    /**
     * After regex processing has been done on a wiki page this function
     * inserts into the resulting page a reference at
     * {{reflist locations, then returns the result page
     *
     * @param string $page page in which to insert the reference lists
     * @param string $references HTML table of contents
     * @return string resulting page after insert
     */
    /**
     * Fetches internal links from wiki syntax.
     *
     * @param array $document a wiki document
     * @param string $page_name name of the page being read, so a category
     *      tag files that page under the category
     * @return array of linked page names in the format
     *  page_name|relationship_type
     */
    function fetchLinks($document, $page_name = "")
    {
        $links = $this->collectLinkTokens($document, $page_name);
        foreach ($links as $key => $link) {
            $internal_link = trim($link, "[] \t\n\r\0\x0B");
            /* drop links that point off the wiki */
            $as_url = parse_url($internal_link);
            if (!empty($as_url) && !empty($as_url['scheme']) &&
                !empty($as_url['host'])) {
                unset($links[$key]);
                continue;
            }
            /* put the link in page_name|relationship_type form */
            $internal_parts = explode('|', $internal_link);
            if (count($internal_parts) == 3) {
                $internal_link = trim($internal_parts[1]) . "|" .
                    trim(mb_strtolower($internal_parts[0]));
            } else {
                $internal_link = trim($internal_parts[0]) . "|";
            }
            $internal_link = str_replace(" ", "_", $internal_link);
            $links[$key] = $internal_link;
        }
        $links = array_unique($links);
        return $links;
    }
    /**
     * Scans a wiki document for every link it points at: the [[...]] links
     * and the {{category|X}} tags, each of which stands for a link to page
     * X marked as a main relationship. A [[...]] that holds a square
     * bracket is passed over, matching what the old link patterns accepted.
     * This finds the links by scanning instead of by a set of regular
     * expressions.
     *
     * @param string $document the wiki document to scan
     * @param string $page_name name of the page being scanned, which a
     *      category tag files under itself
     * @return array the raw link tokens, each still in [[...]] form
     */
    protected function collectLinkTokens($document, $page_name = "")
    {
        $links = [];
        $lower = strtolower($document);
        $category = "{{category|";
        $category_length = strlen($category);
        $offset = 0;
        while (($start = strpos($lower, $category, $offset)) !== false) {
            $inner_start = $start + $category_length;
            $close = strpos($document, "}}", $inner_start);
            if ($close === false) {
                break;
            }
            $name = trim(substr($document, $inner_start,
                $close - $inner_start));
            /* Filing a page under a name is a link from the page to
               itself carrying that name, so the page it points at is the
               page being read. Naming a page called Main here filed every
               article under whatever page happened to be called that,
               and left one waiting where no such page existed. */
            if ($page_name !== "") {
                $links[] = "[[" . $name . "|" . $page_name . "|" .
                    $page_name . "]]";
            }
            $offset = $close + 2;
        }
        $offset = 0;
        while (($start = strpos($document, "[[", $offset)) !== false) {
            $inner_start = $start + 2;
            $close = strpos($document, "]]", $inner_start);
            if ($close === false) {
                break;
            }
            $inner = substr($document, $inner_start, $close - $inner_start);
            if ($inner !== "" && strpos($inner, "[") === false &&
                strpos($inner, "]") === false) {
                $links[] = "[[" . $inner . "]]";
                $offset = $close + 2;
            } else {
                $offset = $start + 2;
            }
        }
        return array_unique($links);
    }
    /**
     * Builds the hidden form fields that gate a wiki form against
     * automated submissions.
     *
     * Every wiki form gets a proof-of-work check: the
     * <code>[{proof-of-work}]</code> token is expanded at render time into
     * fields whose browser must solve a small hash challenge before the
     * form will submit. A decoy (honeypot) text field is also added,
     * hidden from people and from screen readers, so that an automated
     * form-filler that blindly populates inputs gives itself away. Unless
     * the form already collects an answer field (for example when the
     * author added a keyword captcha), a hidden answer field is also
     * included so the form has a key column for saving and de-duplicating
     * rows.
     *
     * @param bool $include_answer_field whether to add the hidden answer
     *     field used as the form's key column; pass false when the form
     *     already supplies one
     * @return string the markup to splice into the form
     */
    public static function proofOfWorkFormFields($include_answer_field = true)
    {
        $fields = "[{proof-of-work}]";
        $fields .= "<div aria-hidden='true' style='position:absolute;" .
            "left:-9999px;top:-9999px;width:1px;height:1px;" .
            "overflow:hidden;'><input type='text' name='" .
            C\WIKI_FORM_HONEYPOT_FIELD . "' tabindex='-1' " .
            "autocomplete='off' value='' ></div>";
        if ($include_answer_field) {
            $fields .= "<input type='hidden' name='user_captcha_text' " .
                "value='[{csv-user_captcha_text}]' >" .
                "<input type='hidden' name='CSVFORM[user_captcha_text]' " .
                "value='textfield' >";
        }
        return $fields;
    }
    /**
     * Used to make a stringified form of the head setting variables for a wiki
     * page.
     *
     * @param array $head_vars head variables want specific values other
     *  than the defaults for
     * @return string of the head settings of a wiki page
     */
    public static function makeWikiPageHead($head_vars = [])
    {
        $head_string = "";
        foreach (self::PAGE_DEFAULTS as $key => $default) {
            $head_string .= urlencode($key) . "=" .
                urlencode($head_vars[$key] ?? $default) . "\n\n";
        }
        return $head_string;
    }
    /**
     * Used to parse head meta variables out of a data string provided either
     * from a wiki page or a static page. Meta data is stored in lines
     * before the first occurrence of END_HEAD_VARS. Head variables
     * are name=value pairs. An example of head
     * variable might be:
     * title = This web page's title
     * Anything after a semi-colon on a line in the head section is treated as
     * a comment
     *
     * @param string $page_data this is the actual content of a wiki or
     *      static page
     * @param bool $with_body whether to output just an array of head
     *      variables or if output a pair [head vars, page body]
     * @return array the associative array of head variables or pair
     *      [head vars, page body]
     */
    public static function parsePageHeadVars($page_data, $with_body = false)
    {
        $page_parts = explode(self::END_HEAD_VARS, $page_data);
        $head_object = [];
        if (count($page_parts) > 1) {
            $head_lines = explode("\n\n", array_shift($page_parts));
            $page_data = implode(self::END_HEAD_VARS, $page_parts);
            foreach ($head_lines as $line) {
                $semi_pos =  (strpos($line, ";")) ? strpos($line, ";"):
                    strlen($line);
                $line = substr($line, 0, $semi_pos);
                $line_parts = explode("=", $line);
                if (count($line_parts) == 2) {
                    $key = trim(urldecode($line_parts[0]));
                    $value = urldecode(trim($line_parts[1]));
                    if ($key == 'page_alias') {
                        $value = str_replace(" ", "_", $value);
                    }
                    $head_object[$key] = $value;
                }
            }
        } else {
            $page_data = $page_parts[0];
        }
        if ($with_body) {
            return [$head_object, $page_data];
        }
        return $head_object;
    }
}
