Sunday, February 14, 2016

Jsoup Code



https://github.com/jhy/jsoup
https://github.com/code4craft/jsoup-learning
http://my.oschina.net/flashsword/blog/156748
jsoup
├── examples #样例,包括一个将html转为纯文本和一个抽取所有链接地址的例子。    
├── helper #一些工具类,包括读取数据、处理连接以及字符串转换的工具
├── nodes #DOM节点定义
├── parser #解析html并转换为DOM树
├── safety #安全相关,包括白名单及html过滤
└── select #选择器,支持CSS Selector以及NodeVisitor格式的遍历
Jsoup的入口是Jsoup类。examples包里提供了两个例子,解析html后,分别用CSS Selector以及NodeVisitor来操作Dom元素。
这里用ListLinks里的例子来说明如何调用Jsoup:
Document doc = Jsoup.connect(url).get(); // 使用select方法选择元素,参数是CSS Selector表达式 Elements links = doc.select("a[href]"); print("\nLinks: (%d)", links.size()); for (Element link : links) { //使用abs:前缀取绝对url地址 print(" * a: <%s> (%s)", link.attr("abs:href"), trim(link.text(), 35)); }
Jsoup使用了自己的一套DOM代码体系,这里的Elements、Element等虽然名字和概念都与Java XML APIorg.w3c.dom类似,但并没有代码层面的关系。就是说你想用XML的一套API来操作Jsoup的结果是办不到的,但是正因为如此,才使得Jsoup可以抛弃xml里一些繁琐的API,使得代码更加简单。
还有一种方式是通过NodeVisitor来遍历DOM树,这个在对整个html做分析和替换时比较有用:
public interface NodeVisitor {
    //遍历到节点开始时,调用此方法
    public void head(Node node, int depth);
    //遍历到节点结束时(所有子节点都已遍历完),调用此方法
    public void tail(Node node, int depth);
}
public String getPlainText(Element element) {
    FormattingVisitor formatter = new FormattingVisitor();
    NodeTraversor traversor = new NodeTraversor(formatter);
    traversor.traverse(element); // walk the DOM, and call .head() and .tail() for each node

    return formatter.toString();
}

// the formatting rules, implemented in a breadth-first DOM traverse
private class FormattingVisitor implements NodeVisitor {
    private static final int maxWidth = 80;
    private int width = 0;
    private StringBuilder accum = new StringBuilder(); // holds the accumulated text

    // hit when the node is first seen
    public void head(Node node, int depth) {
        String name = node.nodeName();
        if (node instanceof TextNode)
            append(((TextNode) node).text()); // TextNodes carry all user-readable text in the DOM.
        else if (name.equals("li"))
            append("\n * ");
        else if (name.equals("dt"))
            append("  ");
        else if (StringUtil.in(name, "p", "h1", "h2", "h3", "h4", "h5", "tr"))
            append("\n");
    }

    // hit when all of the node's children (if any) have been visited
    public void tail(Node node, int depth) {
        String name = node.nodeName();
        if (StringUtil.in(name, "br", "dd", "dt", "p", "h1", "h2", "h3", "h4", "h5"))
            append("\n");
        else if (name.equals("a"))
            append(String.format(" <%s>", node.absUrl("href")));
    }

    // appends text to the string builder with a simple word wrap method
    private void append(String text) {
        if (text.startsWith("\n"))
            width = 0; // reset counter if starts with a newline. only from formats above, not in natural text
        if (text.equals(" ") &&
                (accum.length() == 0 || StringUtil.in(accum.substring(accum.length() - 1), " ", "\n")))
            return; // don't accumulate long runs of empty spaces

        if (text.length() + width > maxWidth) { // won't fit, needs to wrap
            String words[] = text.split("\\s+");
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                boolean last = i == words.length - 1;
                if (!last) // insert a space if not the last word
                    word = word + " ";
                if (word.length() + width > maxWidth) { // wrap and reset counter
                    accum.append("\n").append(word);
                    width = word.length();
                } else {
                    accum.append(word);
                    width += word.length();
                }
            }
        } else { // fits as is, without need to wrap text
            accum.append(text);
            width += text.length();
        }
    }
}
http://my.oschina.net/flashsword/blog/156798
我们先来看看nodes包的类图:
node类图
这里可以看到,核心无疑是Node类。
Node类是一个抽象类,它代表DOM树中的一个节点,它包含:
  • 父节点parentNode以及子节点childNodes的引用
  • 属性值集合attributes
  • 页面的uribaseUri,用于修正相对地址为绝对地址
  • 在兄弟节点中的位置siblingIndex,用于进行DOM操作
Node里面包含一些获取属性、父子节点、修改元素的方法,其中比较有意思的是absUrl()。我们知道,在很多html页面里,链接会使用相对地址,我们有时会需要将其转变为绝对地址。Jsoup的解决方案是在attr()的参数开始加"abs:“,例如attr(“abs:href”),而absUrl()就是其实现方式。
URL base;
try {
    try {
        base = new URL(baseUri);
    } catch (MalformedURLException e) {
        // the base is unsuitable, but the attribute may be abs on its own, so try that
        URL abs = new URL(relUrl);
        return abs.toExternalForm();
    }
    // workaround: java resolves '//path/file + ?foo' to '//path/?foo', not '//path/file?foo' as desired
    if (relUrl.startsWith("?"))
        relUrl = base.getPath() + relUrl;
    // java URL自带的相对路径解析    
    URL abs = new URL(base, relUrl);
    return abs.toExternalForm();
} catch (MalformedURLException e) {
    return "";
}
Node还有一个比较值得一提的方法是abstract String nodeName(),这个相当于定义了节点的类型名(例如Document是'#Document',Element则是对应的TagName)。
Element也是一个重要的类,它代表的是一个HTML元素。它包含一个字段tagclassNames。classNames是"class"属性解析出来的集合,因为CSS规范里,“class"属性允许设置多个,并用空格隔开,而在用Selector选择的时候,即使只指定其中一个,也能够选中其中的元素。所以这里就把"class"属性展开了。Element还有选取元素的入口,例如selectgetElementByXXX,这些都用到了select包中的内容,这个留到下篇文章select再说。
Document是代表整个文档,它也是一个特殊的Element,即根节点。Document除了Element的内容,还包括一些输出的方法。
Document还有一个属性quirksMode,大致意思是定义处理非标准HTML的几个级别,这个留到以后分析parser的时候再说。
Node还有一些方法,例如outerHtml(),用作节点及文档HTML的输出,用到了树的遍历。在DOM树的遍历上,用到了NodeVisitorNodeTraversor来对树的进行遍历。NodeVisitor在上一篇文章提到过了,head()和tail()分别是遍历开始和结束时的方法,而NodeTraversor的核心代码如下:
public void traverse(Node root) {
    Node node = root;
    int depth = 0;
    //这里对树进行后序(深度优先)遍历
    while (node != null) {
        //开始遍历node
        visitor.head(node, depth);
        if (node.childNodeSize() > 0) {
            node = node.childNode(0);
            depth++;
        } else {
            //没有下一个兄弟节点,退栈
            while (node.nextSibling() == null && depth > 0) {
                visitor.tail(node, depth);
                node = node.parent();
                depth--;
            }
            //结束遍历
            visitor.tail(node, depth);
            if (node == root)
                break;
            node = node.nextSibling();
        }
    }
}
这里使用循环+回溯来替换掉了我们常用的递归方式,从而避免了栈溢出的风险。
实际上,Jsoup的Selector机制也是基于NodeVisitor来实现的,可以说NodeVisitor是更加底层和灵活的API。
http://my.oschina.net/flashsword/blog/157031
分析代码前,我们不妨先想想,“tidy HTML"到底包括哪些东西:
  • 换行,块级标签习惯上都会独占一行
  • 缩进,根据HTML标签嵌套层数,行首缩进会不同
  • 严格的标签闭合,如果是可以自闭合的标签并且没有内容,则进行自闭合
  • HTML实体的转义
这里要补充一下HTML标签的知识。HTML Tag可以分为block和inline两类。关于Tag的inline和block的定义可以参考http://www.w3schools.com/html/html_blocks.asp,而Jsoup的Tag类则是对Java开发者非常好的学习资料。
//block tags,需要换行
private static final String[] blockTags = {
        "html", "head", "body", "frameset", "script", "noscript", "style", "meta", "link", "title", "frame",
        "noframes", "section", "nav", "aside", "hgroup", "header", "footer", "p", "h1", "h2", "h3", "h4", "h5", "h6",
        "ul", "ol", "pre", "div", "blockquote", "hr", "address", "figure", "figcaption", "form", "fieldset", "ins",
        "del", "s", "dl", "dt", "dd", "li", "table", "caption", "thead", "tfoot", "tbody", "colgroup", "col", "tr", "th",
        "td", "video", "audio", "canvas", "details", "menu", "plaintext"
};
//inline tags,无需换行
private static final String[] inlineTags = {
        "object", "base", "font", "tt", "i", "b", "u", "big", "small", "em", "strong", "dfn", "code", "samp", "kbd",
        "var", "cite", "abbr", "time", "acronym", "mark", "ruby", "rt", "rp", "a", "img", "br", "wbr", "map", "q",
        "sub", "sup", "bdo", "iframe", "embed", "span", "input", "select", "textarea", "label", "button", "optgroup",
        "option", "legend", "datalist", "keygen", "output", "progress", "meter", "area", "param", "source", "track",
        "summary", "command", "device"
};
//emptyTags是不能有内容的标签,这类标签都是可以自闭合的
private static final String[] emptyTags = {
        "meta", "link", "base", "frame", "img", "br", "wbr", "embed", "hr", "input", "keygen", "col", "command",
        "device"
};
private static final String[] formatAsInlineTags = {
        "title", "a", "p", "h1", "h2", "h3", "h4", "h5", "h6", "pre", "address", "li", "th", "td", "script", "style",
        "ins", "del", "s"
};
//在这些标签里,需要保留空格
private static final String[] preserveWhitespaceTags = {
        "pre", "plaintext", "title", "textarea"
};
另外,Jsoup的Entities类里包含了一些HTML实体转义的东西。这些转义的对应数据保存在entities-full.propertiesentities-base.properties里。
在Jsoup里,直接调用Document.toString()(继承自Element),即可对文档进行输出。另外OutputSettings可以控制输出格式,主要是prettyPrint(是否重新格式化)、outline(是否强制所有标签换行)、indentAmount(缩进长度)等。
里面的继承和互相调用关系略微复杂,大概是这样子:
Document.toString()=>Document.outerHtml()=>Element.html(),最终Element.html()又会循环调用所有子元素的outerHtml(),拼接起来作为输出。

private void html(StringBuilder accum) {
    for (Node node : childNodes)
        node.outerHtml(accum);
}
outerHtml()会使用一个OuterHtmlVisitor对所以子节点做遍历,并拼装起来作为结果。

protected void outerHtml(StringBuilder accum) {
    new NodeTraversor(new OuterHtmlVisitor(accum, getOutputSettings())).traverse(this);
}
OuterHtmlVisitor会对所有子节点做遍历,并调用node.outerHtmlHead()node.outerHtmlTail两个方法。

private static class OuterHtmlVisitor implements NodeVisitor {
    private StringBuilder accum;
    private Document.OutputSettings out;

    public void head(Node node, int depth) {
        node.outerHtmlHead(accum, depth, out);
    }

    public void tail(Node node, int depth) {
        if (!node.nodeName().equals("#text")) // saves a void hit.
            node.outerHtmlTail(accum, depth, out);
    }
}
我们终于找到了真正工作的代码,node.outerHtmlHead()node.outerHtmlTail。Jsoup里每种Node的输出方式都不太一样,这里只讲讲两种主要节点:ElementTextNodeElement是格式化的主要对象,它的两个方法代码如下:

void outerHtmlHead(StringBuilder accum, int depth, Document.OutputSettings out) {
    if (accum.length() > 0 && out.prettyPrint()
            && (tag.formatAsBlock() || (parent() != null && parent().tag().formatAsBlock()) || out.outline()) )
        //换行并调整缩进
        indent(accum, depth, out);
    accum
            .append("<")
            .append(tagName());
    attributes.html(accum, out);

    if (childNodes.isEmpty() && tag.isSelfClosing())
        accum.append(" />");
    else
        accum.append(">");
}

void outerHtmlTail(StringBuilder accum, int depth, Document.OutputSettings out) {
    if (!(childNodes.isEmpty() && tag.isSelfClosing())) {
        if (out.prettyPrint() && (!childNodes.isEmpty() && (
                tag.formatAsBlock() || (out.outline() && (childNodes.size()>1 || (childNodes.size()==1 && !(childNodes.get(0) instanceof TextNode))))
        )))
            //换行并调整缩进
            indent(accum, depth, out);
        accum.append("</").append(tagName()).append(">");
    }
}
而ident方法的代码只有一行:

protected void indent(StringBuilder accum, int depth, Document.OutputSettings out) {
    //out.indentAmount()是缩进长度,默认是1
    accum.append("\n").append(StringUtil.padding(depth * out.indentAmount()));
}
代码简单明了,就没什么好说的了。值得一提的是,StringUtil.padding()方法为了减少字符串生成,把常用的缩进保存到了一个数组中。
好了,水了一篇文章,下一篇将比较有技术含量的parser部分。
另外,通过本节的学习,我们学到了要把StringBuilder命名为accum,而不是sb

状态机

Jsoup的词法分析和语法分析都用到了状态机。状态机可以理解为一个特殊的程序模型,例如经常跟我们打交道的正则表达式就是用状态机实现的。
它由状态(state)和转移(transition)两部分构成。根据状态转移的可能性,状态机又分为DFA(确定有限状态机)和NFA(非确定有限状态自动机)。这里拿一个最简单的正则表达式"a[b]*“作为例子,我们先把它映射到一个状态机DFA,大概是这样子:
state machine
状态机本身是一个编程模型,这里我们尝试用程序去实现它,那么最直接的方式大概是这样:

public void process(StringReader reader) throws StringReader.EOFException {
    char ch;
    switch (state) {
        case Init:
            ch = reader.read();
            if (ch == 'a') {
                state = State.AfterA;
                accum.append(ch);
            }
            break;
        case AfterA:
            ...
            break;
        case AfterB:
            ...
            break;
        case Accept:
            ...
            break;
    }
}
这样写简单的状态机倒没有问题,但是复杂情况下就有点难受了。还有一种标准的状态机解法,先建立状态转移表,然后使用这个表建立状态机。这个方法的问题就是,只能做纯状态转移,无法在代码级别操作输入输出。
Jsoup里则使用了状态模式来实现状态机,初次看到时,确实让人眼前一亮。状态模式是设计模式的一种,它将状态和对应的行为绑定在一起。而在状态机的实现过程中,使用它来实现状态转移时的处理再合适不过了。
“a[b]*“的例子的状态模式实现如下,这里采用了与Jsoup相同的方式,用到了枚举来实现状态模式:

public class StateModelABStateMachine implements ABStateMachine {

    State state;

    StringBuilder accum;

    enum State {
        Init {
            @Override
            public void process(StateModelABStateMachine stateModelABStateMachine, StringReader reader) throws StringReader.EOFException {
                char ch = reader.read();
                if (ch == 'a') {
                    stateModelABStateMachine.state = AfterA;
                    stateModelABStateMachine.accum.append(ch);
                }
            }
        },
        Accept {
            ...
        },
        AfterA {
            ...
        },
        AfterB {
            ...
        };

        public void process(StateModelABStateMachine stateModelABStateMachine, StringReader reader) throws StringReader.EOFException {
        }
    }

    public void process(StringReader reader) throws StringReader.EOFException {
        state.process(this, reader);
    }
}
select机制
Jsoup的select包里,类结构如下:
uml
在最开始介绍Jsoup的时候,就已经说过NodeVisitorSelector了。Selector是select部分的对外facade,而NodeVisitor则是遍历树的底层API,CSS Selector也是根据NodeVisitor实现的遍历。
Jsoup的select核心是Evaluator。Selector所传递的表达式,会经过QueryParser,最终编译成一个EvaluatorEvaluator是一个抽象类,它只有一个方法:

public abstract boolean matches(Element root, Element element);
注意这里传入了root,是为了某些情况下对树进行遍历时用的。
Evaluator的设计简洁明了,所有的Selector表达式单词都会编译到对应的Evaluator。例如#xx对应Id.xx对应Class[]对应Attribute。这里补充一下w3c的CSS Selector规范:http://www.w3.org/TR/CSS2/selector.html
当然,只靠这几个还不够,Jsoup还定义了CombiningEvaluator(对Evaluator进行And/Or组合),StructuralEvaluator(结合DOM树结构进行筛选)。
这里我们可能最关心的是,“div ul li”这样的父子结构是如何实现的。这个的实现方式在StructuralEvaluator.Parent中,贴一下代码了:

static class Parent extends StructuralEvaluator {
    public Parent(Evaluator evaluator) {
        this.evaluator = evaluator;
    }

    public boolean matches(Element root, Element element) {
        if (root == element)
            return false;

        Element parent = element.parent();
        while (parent != root) {
            if (evaluator.matches(root, parent))
                return true;
            parent = parent.parent();
        }
        return false;
    }
}
这里Parent包含了一个evaluator属性,会根据这个evaluator去验证所有父节点。注意Parent是可以嵌套的,所以这个表达式"div ul li"最终会编译成And(Parent(And(Parent(Tag("div")),Tag("ul")),Tag("li")))这样的Evaluator组合。
select部分比想象的要简单,代码可读性也很高。经过了parser部分的研究,这部分应该算是驾轻就熟了。
cleaner是Jsoup的重要功能之一,我们常用它来进行富文本输入中的XSS防御。
我们知道,XSS攻击的一般方式是,通过在页面输入中嵌入一段恶意脚本,对输出时的DOM结构进行修改,从而达到执行这段脚本的目的。对于纯文本输入,过滤/转义HTML特殊字符<,>,",'是行之有效的办法,但是如果本身用户输入的就是一段HTML文本(例如博客文章),这种方式就不太有效了。这个时候,就是Jsoup大显身手的时候了。
在前面,我们已经知道了,Jsoup里怎么将HTML变成一棵DOM树,怎么对DOM树进行遍历,怎么对DOM文档进行输出,那么其实cleaner的实现方式,也能猜出大概了。使用Jsoup进行XSS防御,大致分为三个步骤:
  1. 将HTML解析为DOM树
    这一步可以过滤掉一些企图搞破坏的非闭合标签、非正常语法等。例如一些输入,会尝试用</textarea>闭合当前Tag,然后写入攻击脚本。而根据前面对Jsoup的parser的分析,这种时候,这些非闭合标签会被当做错误并丢弃。
  2. 过滤高风险标签/属性/属性值
    高风险标签是指<script>以及类似标签,对属性/属性值进行过滤是因为某些属性值里也可以写入javascript脚本,例如onclick='alert("xss!")'
  3. 重新将DOM树输出为HTML文本
    DOM树的输出,在前面(Jsoup代码解读之三)已经提到过了。

Cleaner与Whitelist

对于上述的两个步骤,1、3都已经分别在parser和输出中完成,现在只剩下步骤 2:过滤高风险标签等。
Jsoup给出的答案是白名单。下面是Whitelist的部分代码。

public class Whitelist {
    private Set<TagName> tagNames; // tags allowed, lower case. e.g. [p, br, span]
    private Map<TagName, Set<AttributeKey>> attributes; // tag -> attribute[]. allowed attributes [href] for a tag.
    private Map<TagName, Map<AttributeKey, AttributeValue>> enforcedAttributes; // always set these attribute values
    private Map<TagName, Map<AttributeKey, Set<Protocol>>> protocols; // allowed URL protocols for attributes
    private boolean preserveRelativeLinks; // option to preserve relative links
}
这里定义了标签名/属性名/属性值的白名单。
Cleaner是过滤的执行者。不出所料,Cleaner内部定义了CleaningVisitor来进行标签的过滤。CleaningVisitor的过滤过程并不改变原始DOM树的值,而是将符合条件的属性,加入到Element destination里去。

private final class CleaningVisitor implements NodeVisitor {
    private int numDiscarded = 0;
    private final Element root;
    private Element destination; // current element to append nodes to

    private CleaningVisitor(Element root, Element destination) {
        this.root = root;
        this.destination = destination;
    }

    public void head(Node source, int depth) {
        if (source instanceof Element) {
            Element sourceEl = (Element) source;

            if (whitelist.isSafeTag(sourceEl.tagName())) { // safe, clone and copy safe attrs
                ElementMeta meta = createSafeElement(sourceEl);
                Element destChild = meta.el;
                destination.appendChild(destChild);

                numDiscarded += meta.numAttribsDiscarded;
                destination = destChild;
            } else if (source != root) { // not a safe tag, so don't add. don't count root against discarded.
                numDiscarded++;
            }
        } else if (source instanceof TextNode) {
            TextNode sourceText = (TextNode) source;
            TextNode destText = new TextNode(sourceText.getWholeText(), source.baseUri());
            destination.appendChild(destText);
        } else { // else, we don't care about comments, xml proc instructions, etc
            numDiscarded++;
        }
    }

    public void tail(Node source, int depth) {
        if (source instanceof Element && whitelist.isSafeTag(source.nodeName())) {
            destination = destination.parent(); // would have descended, so pop destination stack
        }
    }
}

结束语

至此,Jsoup的全部模块都已经写完了。Jsoup源码并不多,只有14000多行,但是实现非常精巧,在读代码的过程中,除了相关知识,还验证几个很重要的思想:
  • 最好的代码抽象,是对现实概念的映射。
    这句话在看《代码大全》的时候印象很深刻。在Jsoup里,只要有相关知识,每个类的作用都能第一时间明白其作用。
  • 不要过度抽象
    在Jsoup里,只用到了两个接口,一个是NodeVisitor,一个是Connection,其他都是用抽象类或者直接用实现类代替。记得有次面试的时候被问到我们开发中每逢一个功能,都要先定义一个接口的做法是否必要?现在的答案是没有必要,过度的抽象反而会降低代码质量。
    另外,Jsoup的代码内聚性都很高,每个类的功能基本都定义在类的内部,这是一个典型的充血模型。同时有大量的facade使用,而避免了Factory、Configure等类的出现,个人感觉这点是非常好的。

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts