爬虫选择器算法漫谈
爬虫选择器其实就是CSS选择器，和前端开发关系密切，这里先简单介绍一下，让没做过web开发的有个大概了解。
前端开发涉及到的东西很多，虽然最终只是展示一个web页面，然而混合了各种技术，标签语言HTML，样式语言CSS，脚本语言Javascript，这3个结合在一起堪称完美，Web GUI可以算是一个UI系统的典范，至少目前看来是没有更加先进的理念能够打破这个规范。
今天主要时一起来了解下CSS语言规则，如果你写过一些CSS样式，对其规则肯定不陌生，CSS规则看起来是这样的：
.text-content pre,.text-content pre[class*=language-],pre.syntaxbox,pre.twopartsyntaxbox {
border-left-width: 5px
}
.text-content html[dir=rtl] pre,html[dir=rtl] .text-content pre,html[dir=rtl] pre.syntaxbox,html[dir=rtl] pre.twopartsyntaxbox {
border-left-width: 0;
border-right-width: 5px
}
.text-content pre>:last-child,pre.syntaxbox>:last-child,pre.twopartsyntaxbox>:last-child {
margin-bottom: 0
}
.text-content pre>:last-child,pre.syntaxbox>:last-child,pre.twopartsyntaxbox>:last-child {
padding-bottom: 0
}
.text-content pre p,.text-content pre[class*=language-] p,pre.syntaxbox p,pre.twopartsyntaxbox p {
box-sizing: border-box;
width: 100%;
max-width: 100%
}
对于每一个HTML元素，可能有一个或者多个CSS样式能够与之匹配，这个匹配的过程就叫做CSS Select，每一项规则都是一个Selector，对于一个页面来说，可能存在大量的CSS Selector，CSS的匹配规则可能很复杂（你永远不知道前端同学会怎样折腾），也因此CSS匹配需要非常高效才行。
对于匹配，第一感觉能够比较高效进行表达的应该是编译原理的语法树，如果能够定义一套正确的BNF范式，说不定会很合适。
BNF范式非常清晰，用来表达程序语言再自然不过，而且找问题也很方便直观，但是真正用Flex和Yacc来写语言的却很少见过，因为不够高效，另外这两个工具生成的代码量很大，写语言的程序员一般功力深厚都是直接撸代码完成词法和语法分析，可能会借鉴BNF的思路，具体实现一般会用C语言或者汇编。
网上其实很少有人手写一个CSS规则匹配算法，可能是用到的场景不多，另外一个也是因为实现起来有一定的工作量，做到高效并不容易。翻了一遍Github也没找到合适的库，碰到一个用Flex做的解析器，功能应该比较完善，但是没找到纯C/C++实现的，看来还是只能从谷歌浏览器的源代码里找标准答案了。
使用VSCode打开8000多个工程4万多个源代码文件的Chromium源码（深吸一口气）。
Chromium浏览器里面的CSS规则匹配是用C++代码实现的，一个完整的实现差不多有几千行，代码量不算很多，那就一起看一下吧。
我们从测试代码开始看，Chromium的代码都非常健壮，每个模块和类都会有专门的单元测试，测试代码也很简单清晰。CSS匹配的测试用例在Webkit的dom子目录中，Chromium的页面渲染引擎虽然叫做Blink，但是大部分代码还是Webkit。找到SelectorQueryTest.cpp，里面的代码如下：
TEST(SelectorQueryTest, NotMatchingPseudoElement)
{
// 构造一个document
Document* document = Document::create();
// 构造一个element元素，估计是根节点
HTMLHtmlElement* html = HTMLHtmlElement::create(*document);
document->appendChild(html);
// 设置html内容
document->documentElement()->setInnerHTML("<body><style>span::before { content: 'X' }</style><span></span></body>", ASSERT_NO_EXCEPTION);
// 查询span::before元素
CSSSelectorList selectorList = CSSParser::parseSelector(CSSParserContext(*document, nullptr), nullptr, "span::before");
// 构建query查询器
std::unique_ptr<SelectorQuery> query = SelectorQuery::adopt(std::move(selectorList));
// 查询第一个元素
Element* elm = query->queryFirst(*document);
// 断言为nullptr
EXPECT_EQ(nullptr, elm);
// 查询span元素
selectorList = CSSParser::parseSelector(CSSParserContext(*document, nullptr), nullptr, "span");
// 构建query查询器
query = SelectorQuery::adopt(std::move(selectorList));
// 查询第一个元素
elm = query->queryFirst(*document);
// 断言为找到元素
EXPECT_NE(nullptr, elm);
}
流程很简单，也就是通过需要查询的内容构造一个CSSSelectorList，然后通过CSSSelectorList构造一个query对象，通过query查询document里面是否有匹配的元素。
这里面分了2步来做查询，第一步是需要创建CSSSelectorList，这个CSSSelectorList是干啥的呢？不难想象，这个对象可以简单的看作是存储CSS规则的数据结构，也就是将前端开发人员的CSS规则转换为内部的C++对象，这个转换过程理想情况下应该是O(n)复杂度，n为规则字符串长度，也就是一次遍历，Chromium的实现也确实是做到了这种程度。
第2步就要复杂一些了，因为要在整棵HTML DOM树上进行查找，Chromium在这一步上做了一点优化，查询分为快查和慢查，对于比较简单的规则，比如只是查个id，或者查class、element，就是快查，快查是直接使用dom树的根节点遍历所有节点，这样可以不用走树结构。
慢查也可以说是标准树形查找，从根节点出发，依次匹配规则。如下代码
// 在element元素下匹配满足selector的节点
inline bool SelectorDataList::selectorMatches(const CSSSelector& selector, Element& element, const ContainerNode& rootNode) const
{
SelectorChecker::Init init;
init.mode = SelectorChecker::QueryingRules;
init.isQuerySelector = true;
// 构造SelectorChecker（检查器）
SelectorChecker checker(init);
SelectorChecker::SelectorCheckingContext context(&element, SelectorChecker::VisitedMatchDisabled);
context.selector = &selector;
context.scope = &rootNode;
// 开始查找
return checker.match(context);
}
最终调用了SelectorChecker对象来进行查找操作。接着看这个match方法，
bool match(const SelectorCheckingContext& context, MatchResult& result) const
{
ASSERT(context.selector);
return matchSelector(context, result) == SelectorMatches;
}
继续看matchSelector函数会发现，匹配的过程最重要的是处理好节点父子关系(relation)，然后是Pseudo这种伪类产生的特殊处理。
处理relation的函数是matchForRelation，这个函数会递归调用matchSelector，也就是一层一层的往叶子节点查找，如果匹配上了就放到result对象中。这个过程细节很多，CSS的规则有几十种类型，每个类型都要处理，所以就不细讲了。
回过头来，让我们再看一下CSS规则文本是如何转换为C++中的数据结构CSSSelectorList的。
selectorList = CSSParser::parseSelector(CSSParserContext(*document, nullptr), nullptr, "span");
显然是parseSelector函数作为模块的对外API，这个函数最终会调用CSSSelectorParser的parseSelector函数。如下：
// 解析CSS规则，range可以理解为词法分析遍历器，有peek和consume这种函数很方便处理字符串
CSSSelectorList CSSSelectorParser::parseSelector(CSSParserTokenRange range, const CSSParserContext& context, StyleSheetContents* styleSheet)
{
CSSSelectorParser parser(context, styleSheet);
// 消耗掉空白
range.consumeWhitespace();
// 消耗一个复杂的select list
CSSSelectorList result = parser.consumeComplexSelectorList(range);
if (!range.atEnd())
return CSSSelectorList();
recordSelectorStats(context, result);
return result;
}
重点函数consumeComplexSelectorList:
//组合类型会造成list多个元素
CSSSelectorList CSSSelectorParser::consumeComplexSelectorList(CSSParserTokenRange& range)
{
Vector<std::unique_ptr<CSSParserSelector>> selectorList;
// 解析一个selector
std::unique_ptr<CSSParserSelector> selector = consumeComplexSelector(range);
if (!selector)
return CSSSelectorList();
selectorList.append(std::move(selector));
// 碰到逗号，组合类型，继续解析一个个selector
while (!range.atEnd() && range.peek().type() == CommaToken) {
// consume掉空白
range.consumeIncludingWhitespace();
selector = consumeComplexSelector(range);
if (!selector)
return CSSSelectorList();
selectorList.append(std::move(selector));
}
// 失败处理
if (m_failedParsing)
return CSSSelectorList();
// 返回list
return CSSSelectorList::adoptSelectorVector(selectorList);
}
consumeComplexSelector里面是解析单个的selector，其实就是词法分析取token，只不过都是C++直接处理各种类型，虽然琐碎，但是很高效。
代码看到这里其实已经能够看得清CSS匹配的全貌了，细节处理虽然复杂，大体思路却比较简单直接。
CSS匹配的用途最典型的是网页爬虫，如果哪天出了一个新的程序设计语言，这个语言又没有现成的爬虫组件，那么你自己来实现一个简单或复杂的CSS选择器，参考Chromium的源码思路就能很好的解决问题。
Python语言中有一个BeatifulSoup的库，主要是做这样的事情，但是很多语言都没有这么完善的库，比如Lua语言。Lua语言简短精悍，比较适合作为C/C++的辅助语言，在我的笔记软件中，将Lua语言作为插件语言，为了能够提供一个CSS匹配的接口，参考了上面所讲的思路，最终实现的接口如下示例：
local content = download_codeforces(problem)
local root = html:parse(content)
local markdown = ""
local title = root:select("div.header div.title")
if title then
markdown = markdown.."# "..title:markdown().."\n"
end
local body = title.parent:next_sibling()
if body then
markdown = markdown..body:markdown().."\n"
end
local input_node = root:select("div.input-specification")
if input_node then
markdown = markdown.."### "..input_node:markdown().."\n"
end
这段脚本的功能是解析codeforces题目页面，通过CSS选择器匹配标题、内容、输入3个部分的element，然后将其转换为markdown文本插入到笔记中，用起来和python一样方便。
我这里写的比较简短，能大概理解过程就行，说不定哪天面试会问你这种问题的思路。如果你有更好的思路欢迎留言。
另外后面dansen小编会开始写一个C++方面的读书笔记专题，先从Effective C++这本书开始，因为最近深受多线程问题的困扰，为了修改笔记软件崩溃问题，查了比较多的资料，虽然最终发现问题和多线程安全关系不大，但是还是学到了很多能够提高编写C++程序的知识。本号读者大部分都会C/C++，所以讨论C++的编写心得还是很有意义的，读书笔记重点围绕代码安全（包括内存安全和线程安全两方面）来展开。