虽然迟了点,还是祝有缘看到此文的朋友们新年快乐、技术进步、学有所成。当然,最重要的是都能身体健康。

Typecho中Markdown解析的思路

其实脑海中一想,Markdown本身的语法并不复杂,且大致上可以分为块区域和行内区域两种情况。块区域如典型的块级代码块、段落、标题,行内区域如强调、加粗、行内代码。事实上,Typecho所使用的HyperDown解析器就是按照这种思路去实现的。当然,这样子实现起来属于比较”松散”的实现,如果按照Markdown作者的语法文档作为参照,则HyperDown属于实现了一个子集同时有些许语法的不同可以当作是某种扩展,例如通过 !!! 包裹表示原始HTML内容、裸URL自动转换为a标签(这点有时反而带来不便)。Markdown语法细节还是比较多的,相应的解析代码也比较长同时有很多细节控制代码,这里不一一讨论,仅作整体分析并跟进小部分细节,抛砖引玉了。

HyperDown对外提供 makeHtml 方法,顾名思义用于将Markdown文本字符串转换为对应的HTML文本。Typecho中对HyperDown稍作了封装,看下面部分代码即可见:

/**
 * convert 
 * 
 * @param string $text 
 * @return string
 */
public static function convert($text)
{
    static $parser;

    if (empty($parser)) {
        $parser = new HyperDown();

        $parser->hook('afterParseCode', function ($html) {
            return preg_replace("/<code class=\"([_a-z0-9-]+)\">/i", "<code class=\"lang-\\1\">", $html);
        });

        $parser->enableHtml(true);
    }

    return str_replace('<p><!--more--></p>', '<!--more-->', $parser->makeHtml($text));
}

其中设置 hook 这里先不管,可见其时先实例化 HyperDown 并赋值给静态变量达到类似单例的效果,然后便直接调用 HyperDown 的接口,最后用 <p> 包裹了一下摘要分割符 <!--more--> 以作替换,直接跟进接口入口 makeHtml 进行分析即可。

/**
 * makeHtml
 *
 * @param mixed $text
 * @return string
 */
public function makeHtml($text)
{
    $this->_footnotes = array();
    $this->_definitions = array();
    $this->_holders = array();
    $this->_uniqid = md5(uniqid());
    $this->_id = 0;

    usort($this->blockParsers, function ($a, $b) {
        return $a[1] < $b[1] ? -1 : 1;
    });

    foreach ($this->blockParsers as $parser) {
        list ($name) = $parser;

        if (isset($parser[2])) {
            $this->_parsers[$name] = $parser[2];
        } else {
            $this->_parsers[$name] = array($this, 'parseBlock' . ucfirst($name));
        }
    }

    $text = $this->initText($text);
    $html = $this->parse($text);
    $html = $this->makeFootnotes($html);
    $html = $this->optimizeLines($html);

    return $this->call('makeHtml', $html);
}

初始化部分定义了很多后面有用到的数组,并生成了 _uniqid 其配合自增的 _id 达到唯一标识效果。初始化 _parsers 定义,这里都是前面提到的块级内容,例如 code 则将其解析模块定义为 $this->parseBlockCode 方法。这种乍一看会有种递归下降分析的感觉,但是其实并不是。随后进行文本初始化处理,跟进 initText 如下:

/**
 * @param $text
 * @return mixed
 */
private function initText($text)
{
    $text = str_replace(array("\t", "\r"),  array('    ', ''),  $text);
    return $text;
}

可见 tab 替换为4个空格,以便统一处理,同时去掉 "\r" 即统一用 "\n" 以免带来解析时候的混淆问题。首先对文本这么处理还是很有必要的,避免了很多麻烦。随后就是关键的 parse 操作即解析操作了。跟进 parse 可见:

/**
 * parse
 *
 * @param string $text
 * @param bool $inline
 * @param int $offset
 * @return string
 */
private function parse($text, $inline = false, $offset = 0)
{
    $blocks = $this->parseBlock($text, $lines);
    $html = '';

    // inline mode for single normal block
    if ($inline && count($blocks) == 1 && $blocks[0][0] == 'normal') {
        $blocks[0][3] = true;
    }

    foreach ($blocks as $block) {
        list ($type, $start, $end, $value) = $block;
        $extract = array_slice($lines, $start, $end - $start + 1);
        $method = 'parse' . ucfirst($type);

        $extract = $this->call('before' . ucfirst($method), $extract, $value);
        $result = $this->{$method}($extract, $value, $start + $offset, $end + $offset);
        $result = $this->call('after' . ucfirst($method), $result, $value);

        $html .= $result;
    } 

    return $html;
}

可见首先通过 $this->parseBlock($text, lines) 方法,将Markdown文本解析为了以块级分割的数组,数组的每个元素记录了这个块的类别、起始行、终止行和值信息。例如对于如下文本:

0:内容哦年通过
1:====
2:
3:### 三级标题
4:
5:<iframe id="music" frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="..."></iframe>
6:
7:一首歌曲:<audio id="music" src="..." controls="controls">
8:您的浏览器不支持 audio 标签。
9:</audio>
10:
11:> hahaaaaaaaaaaaa
12:>> bbbbbbbbbbbbbb

其解析出来的 blocks 数组如下:

array(7)
    0:array(4)
        0:"mh"
        1:0
        2:1
        3:1
    1:array(4)
        0:"normal"
        1:2
        2:2
        3:null
    2:array(4)
        0:"sh"
        1:3
        2:3
        3:3
    3:array(4)
        0:"normal"
        1:4
        2:4
        3:null
    4:array(4)
        0:"ahtml"
        1:5
        2:5
        3:null
    5:array(4)
        0:"normal"
        1:6
        2:10
        3:null
    6:array(4)
        0:"quote"
        1:11
        2:12
        3:null

当然了,这并不是直接按照顺序一行一行即可得出的。例如第一二行的 Setext 风格的header,解析第一行时是 normal 类型的文本,解析第二行之后就知道了需要与前面一行的结果合并并设置为 mh 类型(不知道Typecho开发者定的这个简写是怎么来的),并且第一个块记录为mh类型,1-2行,1级别标题。后面的块也是类似得出,直到解析完毕所有文本。除了有显示的块外,还有一些内容是不显示的,例如 URL 定义、图片 PATH 定义、 footnotes 设置等,这类内容则是直接解析并存储于对应的数组中即 $parser->_definitions$parser->_footnotes

而在所有块级内容解析完毕之后,如果还有行内的内容,则其必然是包含在块级内容里面的。而显然,不同类型的块其内部所包含的内容解析方式必然稍有不同。例如标题和代码块,显然代码块里面的内容实体化之后原样即可,而标题里面则可以有更多的行内样式,普通段落里面也是类似。由此可见,许多行内的解析是共通的可以单独提取出来作为一个模块,HyperDown将其命名为 parseInline ,这样在解析标题块和段落块时就不用写两遍,在对应的 parseMh 与 parseSh里面直接调用即可,同时标题块特殊的处理放在调用 parseInline 的前后即可。那么直接通过遍历块数组,并且根据块类型去调用块类型对应的处理模块去处理块的文本即可,这样有着适度的抽象与分离。具体流程在 $this->parse() 里面,上面已经贴过了代码,关键部分加上注释如下:

// 遍历各个块
foreach ($blocks as $block) {
    // 取出块信息
    list ($type, $start, $end, $value) = $block;
    $extract = array_slice($lines, $start, $end - $start + 1);

    // 根据块类型得出对应的处理方法名称
    $method = 'parse' . ucfirst($type);

    // 预留Hook接口,这里先不管
    $extract = $this->call('before' . ucfirst($method), $extract, $value);

    //调用对应的处理方法得到结果
    $result = $this->{$method}($extract, $value, $start + $offset, $end + $offset);

    // 预留Hook接口,这里先不管
    $result = $this->call('after' . ucfirst($method), $result, $value);

    // 与前面的结果连接在一起
    $html .= $result;
} 

到这里主要流程就完毕了,并且返回解析出来的 HTML 格式的文本。最后一步是处理最后的 HTML 文档,将前面解析出来的 _footnotes 信息转换为 HTML 添加到文本最后面。Markdown到此其实已经运行完了,但是 Hyperdown 中最后还有一步 —— $html = $this->optimizeLines($html); 。这一步其实并不是优化的作用,主要是对应前端达成后台编辑器预览同步滚动的效果,与Markdown解析本身没有太大关联,这里不进行额外分析。

HyperDown的一些细节

  • 状态的转移

在Typecho解析Markdown的过程中,解析器的状态是不断变化的。这个状态用于标识当前解析器处于什么样的上下文中,在Hyperdown中使用 $parser->_current 标识状态。块级内容的分析过程类似于NFA回退型遍历版的词法分析,不过由于实现的语法有限且构造比较简单同时使用了正则,所以整体来看代码还在可控制范围内。目前除了 Markdown table 语法比较复杂有用到外,只看到了Setext 风格的 header 解析会回退一个块并且合并为新 mh 类型的块,其他大部分地方直接正则匹配一次即可确定类型并且捕获需要的信息,然后根据情况更新上个块的结束行信息或者开新块。(把这些所谓的块想象成词法分析里面的Token就好理解了)

  • Setext 风格的 header 解析是如何回退的

既然上一点提到了这个,这里就仔细分析一下。这种风格的标题上一行就是普通文本,下一行官方文档说 Any number of underlining =’s or -’s will work. 但是Typecho的解析器定的是两个及以上才生效,具体过程如下代码所示:

private function parseBlockMh($block, $key, $line, &$state, $lines)
{
    if (preg_match("/^\s*((=|-){2,})\s*$/", $line, $matches)
                && ($block && $block[0] == "normal" && !preg_match("/^\s*$/", $lines[$block[2]]))) {    // check if last line isn't empty
        if ($this->isBlock('normal')) {
            $this->backBlock(1, 'mh', $matches[1][0] == '=' ? 1 : 2)
                ->setBlock($key)
                ->endBlock();
        } else {
            $this->startBlock('normal', $key);
        }

        return false;
    }

    return true;
}

过程很显然,首先当前行要符合其规则,同时上一行非空且当前状态要是 normal 即上一行上下文是普通文本,则可以认为回退并设置上一行和当前行为一个块 —— mh 类型的块(又想吐槽这个简写了)。如果符合其他规则但是当前状态不是 normal 则新开一个 normal 块,认为这只是一行普通的 =...= 或者 _..._ 。一想似乎有个问题,如果此时是 code 块状态呢?这行不是代码块结束本应该合并进去现在直接搞成了 normal 块,那不是gg,解析错误了?这就涉及另外一个问题了,请继续往下看。

  • 为什么 Markdown 各解析模块要有优先级

在解析 Markdown 的过程中,想一想就会明白,“容忍度”越大的块级类型越应当放在前面先尝试解析,因为他们可以接受很多特定的语法作为普通文本加进去不解析,而放在别的环境下可能就会被解析为新的块。显然 code 类型首当其冲, code 上下文环境,除非遇到 ``` 结束符或者文本结束,否则不管什么内容统统只让当前 code 块结束行 +1 。那么显然如果某一行已经尝试过 $parser->parseBlockCode() 等“容忍度”较高的块级类型解析模块了,再遇到 =...= 这种内容时,已经能够确保作出上一条描述的反应不会产生副作用了。具体优先级如何呢?Typecho 的 Hyperdown 解析器写在 $parser->$blockParsers 数组里,如下(数值越小的越在前面进行尝试):

public $blockParsers = array(
    array('code', 10),
    array('shtml', 20),
    array('pre', 30),
    array('ahtml', 40),
    array('list', 50),
    array('math', 60),
    array('html', 70),
    array('footnote', 80),
    array('definition', 90),
    array('quote', 100),
    array('table', 110),
    array('sh', 120),
    array('mh', 130),
    array('hr', 140),
    array('default', 9999)
);
  • Markdown table 语法是如何处理的

看完了感觉有点复杂,不太好描述,参照 $parser->parseBlockTable($block, $key, $line, &$state, $lines) 方法跟进去进行分析就好。

  • 特殊块级的处理

特殊的块级内容如各种定义、footnotes等。这里以定义为例,对应的解析模块如下:

private function parseBlockDefinition($block, $key, $line)
{
    if (preg_match("/^\s*\[((?:[^\]]|\\]|\\[)+?)\]:\s*(.+)$/", $line, $matches)) {
        $this->_definitions[$matches[1]] = $this->cleanUrl($matches[2]);
        $this->startBlock('definition', $key)
            ->endBlock();

        return false;
    }

    return true;
}

很显然,通过正则是否匹配决定是否时一个定义块内容,如果不是直接返回 true 进行其他尝试,否则开启新定义块,并且将其存储于 $parser->_definitions 数组中以备后面使用。同时在Typecho中,觉得定义不会换行永远只可能有一行所以直接结束了这个块,但其实按照 Markdown 官方语法存在两行的情况,这里不过多讨论。

在下一步解析行内内容的时候,如果用到使用了定义的内容,例如链接定义,则根据正则捕获的引用信息去 $parser->_definitions 数组里面去寻找对应的结果,并进行链接构造与替换原始引用信息即可,关键代码如下所示:

$text = preg_replace_callback(
    "/\[((?:[^\]]|\\\\\]|\\\\\[)+?)\]\[((?:[^\]]|\\\\\]|\\\\\[)+?)\]/",
    function ($matches) use ($self) {
        $escaped = $self->parseInline(
            $self->escapeBracket($matches[1]),  '',  false
        );
        $result = isset( $self->_definitions[$matches[2]] ) ?
            "<a href=\"{$self->_definitions[$matches[2]]}\">{$escaped}</a>"
            : $escaped;

        return $self->makeHolder($result);
    },
    $text
); 

这里把链接文字进行了递归分析,因为其也允许具备行内内容样式。比较有意思的是 return $self->makeHolder($result); 操作,似乎是多余的?又做了什么呢?请继续往下看。

  • _uniqid 与 _id 有什么用?

前面就有提到这两个东东,上一点提到的 makeHolder 操作正是使用他们进行的操作,具体如下:

/**
 * @param $str
 * @return string
 */
public function makeHolder($str)
{
    $key = "\r" . $this->_uniqid . $this->_id . "\r";
    $this->_id ++;
    $this->_holders[$key] = $str;

    return $key;
}

而前面在 makeHtml 里面初始化操作的时候:

$this->_uniqid = md5(uniqid());
$this->_id = 0;

所以可见,这整个就是一个替换操作而已,而且用前面提到的,一开始就整体删掉的 "\r" 符号分割,避免了换回来的时候可能的错误,同时这么替换目测是为了防止解析之后可能会有的特殊内容对后面的解析产生影响,导致不该有的错误解析。同时内容映射关系都存储于 $parser->_holders 数组, _uniqid 与 _id 用来保证 key 值不重复。那么根据名称一猜测就知道 releaseHoler 操作应该就是替换回来了,事实也是如此,代码如下:

/**
 * @param $text
 * @param $clearHolders
 * @return string
 */
private function releaseHolder($text, $clearHolders = true)
{
    $deep = 0;
    while (strpos($text, "\r") !== false && $deep < 10) {
        $text = str_replace(array_keys($this->_holders), array_values($this->_holders), $text);
        $deep ++;
    }

    if ($clearHolders) {
        $this->_holders = array();
    }

    return $text;
}
  • $parser->optimizeBlocks() 做了什么优化

在第一步解析成块的时候,在 parseBlock() 返回之前,对于解析出来的块会执行 return $this->optimizeBlocks($this->_blocks, $lines); 操作,内容如下:

/**
 * @param array $blocks
 * @param array $lines
 * @return array
 */
private function optimizeBlocks(array $blocks, array $lines)
{
    $blocks = $this->call('beforeOptimizeBlocks', $blocks, $lines);

    $key = 0;
    while (isset($blocks[$key])) {
        $moved = false;

        $block = &$blocks[$key];
        $prevBlock = isset($blocks[$key - 1]) ? $blocks[$key - 1] : NULL;
        $nextBlock = isset($blocks[$key + 1]) ? $blocks[$key + 1] : NULL;

        list ($type, $from, $to) = $block;

        if ('pre' == $type) {
            $isEmpty = array_reduce($lines, function ($result, $line) {
                return preg_match("/^\s*$/", $line) && $result;
            }, true);

            if ($isEmpty) {
                $block[0] = $type = 'normal';
            }
        }

        if ('normal' == $type) {
            // combine two blocks
            $types = array('list', 'quote');

            if ($from == $to && preg_match("/^\s*$/", $lines[$from])
                && !empty($prevBlock) && !empty($nextBlock)) {
                if ($prevBlock[0] == $nextBlock[0] && in_array($prevBlock[0], $types)) {
                    // combine 3 blocks
                    $blocks[$key - 1] = array(
                        $prevBlock[0],  $prevBlock[1],  $nextBlock[2],  NULL
                    );
                    array_splice($blocks, $key, 2);

                    // do not move
                    $moved = true;
                }
            }
        }

        if (!$moved) {
            $key ++;
        }
    }

    return $this->call('afterOptimizeBlocks', $blocks, $lines);
}

其实仔细看下来也不能称为优化(与前面提到的 optimizeLines 命名一样),同样很奇怪为啥这么起名。这里将空 pre 类型的块(针对的是空字符开头的 pre 语法),如果其内容为空则直接置换成 normal ,但是这里判断的是整个文档为空则置换,且置换的是当前块考察的块的类型,这里似乎存在一点问题,提了PR。后面一步则是将 list 对或 quote 对包裹的单行非空内容合并进去,例如如下内容:

- asdf


- asdf

最终解析出来依然是如下,而不是中间被空段落 <p> 分割为两个 <ol>

<ol>
    <li>asdf</li>
    <li>asdf</li>
</ol>

HyperDown的Hook扩展设计

在 Hyperdown 的代码中间,可以看到很多类似于: $this->call('afterOptimizeBlocks', $blocks, $lines); 的代码,前面遇到都是直接跳过,篇幅所限这里不废话了,贴出两处代码即可直到如何做到的 Hook 设计:

  • 在 Typecho 的 Markdown 封装里面有如下代码:
$parser->hook('afterParseCode', function ($html) {
    return preg_replace("/<code class=\"([_a-z0-9-]+)\">/i", "<code class=\"lang-\\1\">", $html);
});
  • HyperDown 的 hook 函数实现:
/**
 * @param $type
 * @param $callback
 */
public function hook($type, $callback)
{
    $this->_hooks[$type][] = $callback;
}
  • call 函数调用了什么:
/**
 * @param $type
 * @param $value
 * @return mixed
 */
public function call($type, $value)
{
    if (empty($this->_hooks[$type])) {
        return $value;
    }

    $args = func_get_args();
    $args = array_slice($args, 1);

    foreach ($this->_hooks[$type] as $callback) {
        $value = call_user_func_array($callback, $args);
        $args[0] = $value;
    }

    return $value;
}

总结与思考

优点 HyperDown 在自己的 README 里面已经写了,我这里就谈谈一些自己看到的不足。一个项目尤其是开源项目应当具备相应的较为完善的文档,但是 Typecho 的文档的确过于简陋。后来发现 HyperDown 是另外一个 Segmentfault 旗下的独立项目,同样文档简陋(没有文档)。另外个人感觉 HyperDown 的解析思路并不算好,这样解析需要用到大量的正则尝试,加上没有文档代码读起来比较费劲,同时这样去解析需要考虑很多特殊情况,而且没有完全依照、实现 Markdown 的语法,否则代码行数还要更多,代码结构更加复杂。除此之外,很多简写、命名、数组 key 没有见名知义,有些甚至有点误导,某些地方依赖尝试的先后顺序,语法简单还好,一旦语法增加、修改点什么,结果正确性不一定稳定甚至可能要改写很多。最后是全部集中在一个文件一个类里面还是有点太多了(1700+行),适当分割一下可能更易于维护也易于他人阅读、协作。

当然了,以上缺点也可能是我自己理解的问题,如果有不同看法欢迎指出,还是那句话,权当抛砖引玉。

MarkDown 解析的其他思路

MarkDown解析的方式很多,区别在于执行效率、代码复杂度、可维护性、扩展性等方面。 $( \LaTeX )$ 的一些引擎如 $(XeTex)$ 在每次解析的时候都会扫描文档两遍,第一遍扫描各种定义,同时加载对应的包、图片等资源准备好,第二便直接解析渲染出 PDF 或者 HTML (大致流程如此,描述并不严谨)。不知是否能学习这种思路,采用字符流式分析,第一遍扫描出定义、footnotes等暂存起来,第二遍采用类似于编译原理里面学习到的递归下降分析的思路(分析出的Token其实就是最后的部分结果),尽量规避大量使用正则去尝试匹配。如果有时间,我会尝试这么实现试试看,到时候再来更新哈哈!