Ready? The challenging task finally came. We will build a tree this time so that you don’t have to traverse before it was built.😅TreeBuilder has two implementations, XmlTreeBuilder is relatively easy while HtmlTreeBuilder is much more complex. And we will go through them today.
Overview of Package
I will skip general introduction about Compiler, Lex, Parser as there are too many articles talking about them. We will go to Jsoup source code directly. Let’s have a quick look at several classes under package org.jsoup.parser.
Parser: Facade of Jsoup parsing.1
2
3private TreeBuilder treeBuilder; // this is the man who actually do the job
private ParseErrorList errors; // by default Jsoup didn't collect errors of html but you can enable this
private ParseSettings settings; // switches of preserveTagCase and preserveAttributeCaseToken: Parse tokens for the Tokeniser. It’s a abstract class with 6 subclasses:Doctype,StartTag,EndTag,Comment,Character,EOFTokeniser: Read input stream into tokens. It keeps currentstateandemitPendingas the token we are about to emit on next read, it also keepstagPending,startPending,endPending,charPending,doctypePending, andcommentPendingbefore tokens were filled up completelyCharacterReader: consumes tokens off a string, it might be inspired fromByteBufferof NIO as there are similar methods likeconsume()、unconsume()、mark()、rewindToMark()andconsumeTo()TokeniserStateandHtmlTreeBuilderState: Lexing/Parsing State Machine. Jsoup applied State Pattern to implement it using enumerations, which is a classic example of design pattern usage also. Using a transition table is easy for the transition between different states but would be difficult to perform extra work during the transitionHtmlTreeBuilderandXmlTreeBuilder: I list them in the end as they basically play a role like a manager, collaboratingTokeniserand Lexing, Parsing State Machine to finish the work
Lexing and Parsing State Pattern implementation would the most complex part of Jsoup. You can get to know this even just from lines of code statistics. Top 7 source files here!
| File | blank | comment | code |
|---|---|---|---|
| org.jsoup.parser.TokeniserState.java | 27 | 46 | 1671 |
| org.jsoup.parser.HtmlTreeBuilderState.java | 43 | 56 | 1429 |
| org.jsoup.helper.HttpConnection.java | 162 | 51 | 979 |
| org.jsoup.nodes.Element.java | 156 | 604 | 727 |
| org.jsoup.parser.HtmlTreeBuilder.java | 104 | 38 | 591 |
| org.jsoup.select.Evaluator.java | 139 | 107 | 532 |
| org.jsoup.parser.CharacterReader.java | 60 | 61 | 385 |
State Machine and State Pattern
1 | ⬇⬇ ⬇ ⬇ |

If we use a very short code snippet as an example, each arrow would point to a state like TagOpen, TagName, Data, EndTagOpen. I just list two of them in the below:
1 | /** |
Understand the idea of Token parse we can go to TreeBuilder process, we will go to the core section first, then go to XmlTreeReader which is easier. We will talk about HtmlTreeReader at last.
1 | protected void runParser() { |
As for Tokeniser#read():1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19Token read() {
while (!isEmitPending)
state.read(this, reader);
// if emit is pending, a non-character token was found: return any chars in buffer, and leave token for next read:
if (charsBuilder.length() > 0) {
String str = charsBuilder.toString();
charsBuilder.delete(0, charsBuilder.length());
charsString = null;
return charPending.data(str);
} else if (charsString != null) {
Token token = charPending.data(charsString);
charsString = null;
return token;
} else {
isEmitPending = false;
return emitPending;
}
}
XmlTreeBuilder First
After exploring the Lexing part we can go to the Parsing part now. We will go through the easier part XmlTreeBuilder first, focusing on its implementation of method process(token) in abstract class TreeBuilder.
XmlTreeBuilder basically maintains a stack and insert node according to token type:
1 |
|
As for insert, we will just use StartTag as an example in the below. The other insert methods accept different types of Token but the idea is the same.
1 | Element insert(Token.StartTag startTag) { |
HtmlTreeBuilder Last
Compared to XmlTreeBuilder, HtmlTreeBuilder is much more complex. It introduces HtmlTreeBuilderState to process transitions. As Html is relatively loose in syntax and error tolerance, Jsoup won’t simply quit when certain kinds of error detected, but choose to record them and continue. It will also try to close those tags not closed properly. Some nested tags have sequence restriction, such as a <td> must be under <th> or <tr>, while tr must be under <tbody> or <table.
There are currently 23 HtmlTreeBuilderState and we will use a typical Html snippet as an example, which came from Yihua Huang’s work. Comments like <!-- State: --> will indicate what kind of HtmlTreeBuilderState we are at.
1 | <!-- State: Initial --> |
As we said before, nested tags such as tr cannot be under body directly, they need to be organized under table or tbody. And DOCTYPE declaration also should not be seen in body. In method boolean process(Token t, HtmlTreeBuilder tb) of InBody, there is a case to handle this.
1 | case Doctype: { |
If head was not closed before body, Jsoup will auto-close it.1
2
3
4
5
6
7
8InHead {
boolean process(Token t, HtmlTreeBuilder tb) {...}
private boolean anythingElse(Token t, TreeBuilder tb) {
tb.processEndTag("head");
return tb.process(t);
}
}
As the State Pattern implementation needs to handle many different kinds of cases, one can be easily lost while reading the source code. Understanding the concept and general ideas first will be of help while debugging the code to know what Jsoup is doing, but still, it’s not easy and would hurt your brain😭
-To Be Continued-
