8.2.5. Tree Construction

The input to the tree construction stage is a sequence of tokens from the tokenization stage. The tree construction stage is associated with a DOM Document object when a parser is created. The "output" of this stage consists of dynamically modifying or extending that document's DOM tree.

This specification does not define when an interactive user agent has to render the Document so that it is available to the user, or when it has to begin accepting user input.

As each token is emitted from the tokenizer, the user agent must follow the appropriate steps from the following list:

If there is no current node

If the current node is an element in the HTML namespace

If the current node is a MathML text integration point and the token is a start tag whose tag name is neither "mglyph" nor "malignmark"

If the current node is a MathML text integration point and the token is a character token

If the current node is an annotation-xml element in the MathML namespace and the token is a start tag whose tag name is "svg"

If the current node is an HTML integration point and the token is a start tag

If the current node is an HTML integration point and the token is a character token

If the token is an end-of-file token

Process the token according to the rules given in the section corresponding to the current insertion mode in HTML content.

Otherwise

Process the token according to the rules given in the section for parsing tokens in foreign content.

When the specification says that a user agent is to act as if a token had been seen, it means that the user agent is to follow the appropriate steps from the above list.

The current node is a MathML text integration point if it is one of the following elements:

• An mi element in the MathML namespace
• An mo element in the MathML namespace
• An mn element in the MathML namespace
• An ms element in the MathML namespace
• An mtext element in the MathML namespace

The current node is an HTML integration point if it is one of the following elements:

• An annotation-xml element in the MathML namespace whose start tag token had an attribute with the name "encoding" whose value was an ASCII case-insensitive match for the string "text/html"
• An annotation-xml element in the MathML namespace whose start tag token had an attribute with the name "encoding" whose value was an ASCII case-insensitive match for the string "application/xhtml+xml"
• A foreignObject element in the SVG namespace
• A desc element in the SVG namespace
• A title element in the SVG namespace

When the steps below require the UA to insert a character into a node, if that node has a child immediately before where the character is to be inserted, and that child is a Text node, then the character must be appended to that Text node; otherwise, a new Text node whose data is just that character must be inserted in the appropriate place.

A<script>var script = document.getElementsByTagName('script')[0];document.body.removeChild(script);</script>B

A<script>var text = document.createTextNode('B');document.body.appendChild(text);</script>C

A<script>var text = document.getElementsByTagName('script')[0].firstChild;text.data = 'B';document.body.appendChild(text);</script>C

A<table>B<tr>C</tr>D</table>

A<table><tr> B</tr> C</table>

A<table><tr> B</tr> </em>C</table>

DOM mutation events must not fire for changes caused by the UA parsing the document. This includes the parsing of any content inserted using document.write() and document.writeln() calls. [DOMEVENTS]

However, mutation observers do fire, as required by the DOM Core specification.

Not all of the tag names mentioned below are conformant tag names in this specification; many are included to handle legacy content. They still form part of the algorithm that implementations are required to implement to claim conformance.

The algorithm described below places no limit on the depth of the DOM tree generated, or on the length of tag names, attribute names, attribute values, Text nodes, etc. While implementors are encouraged to avoid arbitrary limits, it is recognized that practical concerns will likely force user agents to impose nesting depth constraints.

8.2.5.1 Creating and inserting elements

When the steps below require the UA to create an element for a token in a particular namespace, the UA must create a node implementing the interface appropriate for the element type corresponding to the tag name of the token in the given namespace (as given in the specification that defines that element, e.g. for an a element in the HTML namespace, this specification defines it to be the HTMLAnchorElement interface), with the tag name being the name of that element, with the node being in the given namespace, and with the attributes on the node being those given in the given token.

The interface appropriate for an element in the HTML namespace that is not defined in this specification (or other applicable specifications) is HTMLUnknownElement. Elements in other namespaces whose interface is not defined by that namespace's specification must use the interface Element.

When a resettable element is created in this manner, its reset algorithm must be invoked once the attributes are set. (This initializes the element's value and checkedness based on the element's attributes.)

When the steps below require the UA to insert an HTML element for a token, the UA must first create an element for the token in the HTML namespace, and then append this node to the current node, and push it onto the stack of open elements so that it is the new current node.

The steps below may also require that the UA insert an HTML element in a particular place, in which case the UA must follow the same steps except that it must insert or append the new node in the location specified instead of appending it to the current node. (This happens in particular during the parsing of tables with invalid content.)

If an element created by the insert an HTML element algorithm is a form-associated element, and the form element pointer is not null, and the newly created element doesn't have a form attribute, the user agent must associate the newly created element with the form element pointed to by the form element pointer when the element is inserted, instead of running the reset the form owner algorithm.

When the steps below require the UA to insert a foreign element for a token, the UA must first create an element for the token in the given namespace, and then append this node to the current node, and push it onto the stack of open elements so that it is the new current node. If the newly created element has an xmlns attribute in the XMLNS namespace whose value is not exactly the same as the element's namespace, that is a parse error. Similarly, if the newly created element has an xmlns:xlink attribute in the XMLNS namespace whose value is not the XLink Namespace, that is a parse error.

When the steps below require the user agent to adjust MathML attributes for a token, then, if the token has an attribute named definitionurl, change its name to definitionURL (note the case difference).

When the steps below require the user agent to adjust SVG attributes for a token, then, for each attribute on the token whose attribute name is one of the ones in the first column of the following table, change the attribute's name to the name given in the corresponding cell in the second column. (This fixes the case of SVG attributes that are not all lowercase.)

When the steps below require the user agent to adjust foreign attributes for a token, then, if any of the attributes on the token match the strings given in the first column of the following table, let the attribute be a namespaced attribute, with the prefix being the string given in the corresponding cell in the second column, the local name being the string given in the corresponding cell in the third column, and the namespace being the namespace given in the corresponding cell in the fourth column. (This fixes the use of namespaced attributes, in particular lang attributes in the XML namespace.)

The generic raw text element parsing algorithm and the generic RCDATA element parsing algorithm consist of the following steps. These algorithms are always invoked in response to a start tag token.

1. Insert an HTML element for the token.

2. If the algorithm that was invoked is the generic raw text element parsing algorithm, switch the tokenizer to the RAWTEXT state; otherwise the algorithm invoked was the generic RCDATA element parsing algorithm, switch the tokenizer to the RCDATA state.

3. Let the original insertion mode be the current insertion mode.

4. Then, switch the insertion mode to "text".

8.2.5.2 Closing elements that have implied end tags

When the steps below require the UA to generate implied end tags, then, while the current node is a dd element, a dt element, an li element, an option element, an optgroup element, a p element, an rp element, or an rt element, the UA must pop the current node off the stack of open elements.

If a step requires the UA to generate implied end tags but lists an element to exclude from the process, then the UA must perform the above steps as if that element was not in the above list.

8.2.5.3 Foster parenting

Foster parenting happens when content is misnested in tables.

When a node node is to be foster parented, the node node must be inserted into the foster parent element.

This typically happens as part of the insert an HTML element algorithm above: when that algorithm would normally insert the newly created node into the current node, it gets inserted into the foster parent element instead.

The foster parent element is the parent element of the last table element in the stack of open elements, if there is a table element and it has such a parent element.

It might have no parent or some other kind parent if a script manipulated the DOM after the element was inserted by the parser.

If there is no table element in the stack of open elements (fragment case), then the foster parent element is the first element in the stack of open elements (the html element). Otherwise, if there is a table element in the stack of open elements, but the last table element in the stack of open elements has no parent, or its parent node is not an element, then the foster parent element is the element before the last table element in the stack of open elements.

If the foster parent element is the parent element of the last table element in the stack of open elements, then node must be inserted into the foster parent element, immediately before the last table element in the stack of open elements; otherwise, node must be appended to the foster parent element.

8.2.5.4 The rules for parsing tokens in HTML content

8.2.5.4.1 The "initial" insertion mode

When the user agent is to apply the rules for the "initial" insertion mode, the user agent must handle the token as follows:

A character token that is one of U+0009 CHARACTER TABULATION, "LF" (U+000A), "FF" (U+000C), "CR" (U+000D), or U+0020 SPACE

Ignore the token.

A comment token

Append a Comment node to the Document object with the data attribute set to the data given in the comment token.

A DOCTYPE token

If the DOCTYPE token's name is not a case-sensitive match for the string "html", or the token's public identifier is not missing, or the token's system identifier is neither missing nor a case-sensitive match for the string "about:legacy-compat", and none of the sets of conditions in the following list are matched, then there is a parse error.

• The DOCTYPE token's name is a case-sensitive match for the string "html", the token's public identifier is the case-sensitive string "-//W3C//DTD HTML 4.0//EN", and the token's system identifier is either missing or the case-sensitive string "http://www.w3.org/TR/REC-html40/strict.dtd".
• The DOCTYPE token's name is a case-sensitive match for the string "html", the token's public identifier is the case-sensitive string "-//W3C//DTD HTML 4.01//EN", and the token's system identifier is either missing or the case-sensitive string "http://www.w3.org/TR/html4/strict.dtd".
• The DOCTYPE token's name is a case-sensitive match for the string "html", the token's public identifier is the case-sensitive string "-//W3C//DTD XHTML 1.0 Strict//EN", and the token's system identifier is the case-sensitive string "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd".
• The DOCTYPE token's name is a case-sensitive match for the string "html", the token's public identifier is the case-sensitive string "-//W3C//DTD XHTML 1.1//EN", and the token's system identifier is the case-sensitive string "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd".

Conformance checkers may, based on the values (including presence or lack thereof) of the DOCTYPE token's name, public identifier, or system identifier, switch to a conformance checking mode for another language (e.g. based on the DOCTYPE token a conformance checker could recognize that the document is an HTML4-era document, and defer to an HTML4 conformance checker.)

Append a DocumentType node to the Document node, with the name attribute set to the name given in the DOCTYPE token, or the empty string if the name was missing; the publicId attribute set to the public identifier given in the DOCTYPE token, or the empty string if the public identifier was missing; the systemId attribute set to the system identifier given in the DOCTYPE token, or the empty string if the system identifier was missing; and the other attributes specific to DocumentType objects set to null and empty lists as appropriate. Associate the DocumentType node with the Document object so that it is returned as the value of the doctype attribute of the Document object.

Then, if the DOCTYPE token matches one of the conditions in the following list, then set the Document to quirks mode:

• The force-quirks flag is set to on.
• The name is set to anything other than "html" (compared case-sensitively).
• The public identifier starts with: "+//Silmaril//dtd html Pro v0r11 19970101//"
• The public identifier starts with: "-//AdvaSoft Ltd//DTD HTML 3.0 asWedit + extensions//"
• The public identifier starts with: "-//AS//DTD HTML 3.0 asWedit + extensions//"
• The public identifier starts with: "-//IETF//DTD HTML 2.0 Level 1//"
• The public identifier starts with: "-//IETF//DTD HTML 2.0 Level 2//"
• The public identifier starts with: "-//IETF//DTD HTML 2.0 Strict Level 1//"
• The public identifier starts with: "-//IETF//DTD HTML 2.0 Strict Level 2//"
• The public identifier starts with: "-//IETF//DTD HTML 2.0 Strict//"
• The public identifier starts with: "-//IETF//DTD HTML 2.0//"
• The public identifier starts with: "-//IETF//DTD HTML 2.1E//"
• The public identifier starts with: "-//IETF//DTD HTML 3.0//"
• The public identifier starts with: "-//IETF//DTD HTML 3.2 Final//"
• The public identifier starts with: "-//IETF//DTD HTML 3.2//"
• The public identifier starts with: "-//IETF//DTD HTML 3//"
• The public identifier starts with: "-//IETF//DTD HTML Level 0//"
• The public identifier starts with: "-//IETF//DTD HTML Level 1//"
• The public identifier starts with: "-//IETF//DTD HTML Level 2//"
• The public identifier starts with: "-//IETF//DTD HTML Level 3//"
• The public identifier starts with: "-//IETF//DTD HTML Strict Level 0//"
• The public identifier starts with: "-//IETF//DTD HTML Strict Level 1//"
• The public identifier starts with: "-//IETF//DTD HTML Strict Level 2//"
• The public identifier starts with: "-//IETF//DTD HTML Strict Level 3//"
• The public identifier starts with: "-//IETF//DTD HTML Strict//"
• The public identifier starts with: "-//IETF//DTD HTML//"
• The public identifier starts with: "-//Metrius//DTD Metrius Presentational//"
• The public identifier starts with: "-//Microsoft//DTD Internet Explorer 2.0 HTML Strict//"
• The public identifier starts with: "-//Microsoft//DTD Internet Explorer 2.0 HTML//"
• The public identifier starts with: "-//Microsoft//DTD Internet Explorer 2.0 Tables//"
• The public identifier starts with: "-//Microsoft//DTD Internet Explorer 3.0 HTML Strict//"
• The public identifier starts with: "-//Microsoft//DTD Internet Explorer 3.0 HTML//"
• The public identifier starts with: "-//Microsoft//DTD Internet Explorer 3.0 Tables//"
• The public identifier starts with: "-//Netscape Comm. Corp.//DTD HTML//"
• The public identifier starts with: "-//Netscape Comm. Corp.//DTD Strict HTML//"
• The public identifier starts with: "-//O'Reilly and Associates//DTD HTML 2.0//"
• The public identifier starts with: "-//O'Reilly and Associates//DTD HTML Extended 1.0//"
• The public identifier starts with: "-//O'Reilly and Associates//DTD HTML Extended Relaxed 1.0//"
• The public identifier starts with: "-//SoftQuad Software//DTD HoTMetaL PRO 6.0::19990601::extensions to HTML 4.0//"
• The public identifier starts with: "-//SoftQuad//DTD HoTMetaL PRO 4.0::19971010::extensions to HTML 4.0//"
• The public identifier starts with: "-//Spyglass//DTD HTML 2.0 Extended//"
• The public identifier starts with: "-//SQ//DTD HTML 2.0 HoTMetaL + extensions//"
• The public identifier starts with: "-//Sun Microsystems Corp.//DTD HotJava HTML//"
• The public identifier starts with: "-//Sun Microsystems Corp.//DTD HotJava Strict HTML//"
• The public identifier starts with: "-//W3C//DTD HTML 3 1995-03-24//"
• The public identifier starts with: "-//W3C//DTD HTML 3.2 Draft//"
• The public identifier starts with: "-//W3C//DTD HTML 3.2 Final//"
• The public identifier starts with: "-//W3C//DTD HTML 3.2//"
• The public identifier starts with: "-//W3C//DTD HTML 3.2S Draft//"
• The public identifier starts with: "-//W3C//DTD HTML 4.0 Frameset//"
• The public identifier starts with: "-//W3C//DTD HTML 4.0 Transitional//"
• The public identifier starts with: "-//W3C//DTD HTML Experimental 19960712//"
• The public identifier starts with: "-//W3C//DTD HTML Experimental 970421//"
• The public identifier starts with: "-//W3C//DTD W3 HTML//"
• The public identifier starts with: "-//W3O//DTD W3 HTML 3.0//"
• The public identifier is set to: "-//W3O//DTD W3 HTML Strict 3.0//EN//"
• The public identifier starts with: "-//WebTechs//DTD Mozilla HTML 2.0//"
• The public identifier starts with: "-//WebTechs//DTD Mozilla HTML//"
• The public identifier is set to: "-/W3C/DTD HTML 4.0 Transitional/EN"
• The public identifier is set to: "HTML"
• The system identifier is set to: "http://www.ibm.com/data/dtd/v11/ibmxhtml1-transitional.dtd"
• The system identifier is missing and the public identifier starts with: "-//W3C//DTD HTML 4.01 Frameset//"
• The system identifier is missing and the public identifier starts with: "-//W3C//DTD HTML 4.01 Transitional//"

Otherwise, if the DOCTYPE token matches one of the conditions in the following list, then set the Document to limited-quirks mode:

• The public identifier starts with: "-//W3C//DTD XHTML 1.0 Frameset//"
• The public identifier starts with: "-//W3C//DTD XHTML 1.0 Transitional//"
• The system identifier is not missing and the public identifier starts with: "-//W3C//DTD HTML 4.01 Frameset//"
• The system identifier is not missing and the public identifier starts with: "-//W3C//DTD HTML 4.01 Transitional//"

The system identifier and public identifier strings must be compared to the values given in the lists above in an ASCII case-insensitive manner. A system identifier whose value is the empty string is not considered missing for the purposes of the conditions above.

Then, switch the insertion mode to "before html".

Anything else

If the document is not an iframe srcdoc document, then this is a parse error; set the Document to quirks mode.

In any case, switch the insertion mode to "before html", then reprocess the current token.

8.2.5.4.2 The "before html" insertion mode

When the user agent is to apply the rules for the "before html" insertion mode, the user agent must handle the token as follows:

A DOCTYPE token

Parse error. Ignore the token.

A comment token

Append a Comment node to the Document object with the data attribute set to the data given in the comment token.

A character token that is one of U+0009 CHARACTER TABULATION, "LF" (U+000A), "FF" (U+000C), "CR" (U+000D), or U+0020 SPACE

Ignore the token.

A start tag whose tag name is "html"

Create an element for the token in the HTML namespace. Append it to the Document object. Put this element in the stack of open elements.

If the Document is being loaded as part of navigation of a browsing context, then: if the newly created element has a manifest attribute whose value is not the empty string, then resolve the value of that attribute to an absolute URL, relative to the newly created element, and if that is successful, run the application cache selection algorithm with the resulting absolute URL with any <fragment> component removed; otherwise, if there is no such attribute, or its value is the empty string, or resolving its value fails, run the application cache selection algorithm with no manifest. The algorithm must be passed the Document object.

Switch the insertion mode to "before head".

An end tag whose tag name is one of: "head", "body", "html", "br"

Act as described in the "anything else" entry below.

Any other end tag

Parse error. Ignore the token.

Anything else

Create an html element. Append it to the Document object. Put this element in the stack of open elements.

If the Document is being loaded as part of navigation of a browsing context, then: run the application cache selection algorithm with no manifest, passing it the Document object.

Switch the insertion mode to "before head", then reprocess the current token.

The root element can end up being removed from the Document object, e.g. by scripts; nothing in particular happens in such cases, content continues being appended to the nodes as described in the next section.

8.2.5.4.3 The "before head" insertion mode

When the user agent is to apply the rules for the "before head" insertion mode, the user agent must handle the token as follows:

A character token that is one of U+0009 CHARACTER TABULATION, "LF" (U+000A), "FF" (U+000C), "CR" (U+000D), or U+0020 SPACE

Ignore the token.

A comment token

Append a Comment node to the current node with the data attribute set to the data given in the comment token.

A DOCTYPE token

Parse error. Ignore the token.

A start tag whose tag name is "html"

Process the token using the rules for the "in body" insertion mode.

A start tag whose tag name is "head"

Insert an HTML element for the token.

Set the head element pointer to the newly created head element.

Switch the insertion mode to "in head".

An end tag whose tag name is one of: "head", "body", "html", "br"

Act as if a start tag token with the tag name "head" and no attributes had been seen, then reprocess the current token.

Any other end tag

Parse error. Ignore the token.

Anything else

Act as if a start tag token with the tag name "head" and no attributes had been seen, then reprocess the current token.

8.2.5.4.4 The "in head" insertion mode

When the user agent is to apply the rules for the "in head" insertion mode, the user agent must handle the token as follows:

A character token that is one of U+0009 CHARACTER TABULATION, "LF" (U+000A), "FF" (U+000C), "CR" (U+000D), or U+0020 SPACE

Insert the character into the current node.

A comment token

Append a Comment node to the current node with the data attribute set to the data given in the comment token.

A DOCTYPE token

Parse error. Ignore the token.

A start tag whose tag name is "html"

Process the token using the rules for the "in body" insertion mode.

A start tag whose tag name is one of: "base", "basefont", "bgsound", "command", "link"

Insert an HTML element for the token. Immediately pop the current node off the stack of open elements.

Acknowledge the token's self-closing flag, if it is set.

A start tag whose tag name is "meta"

Insert an HTML element for the token. Immediately pop the current node off the stack of open elements.

Acknowledge the token's self-closing flag, if it is set.

If the element has a charset attribute, and its value is either a supported ASCII-compatible character encoding or a UTF-16 encoding, and the confidence is currently tentative, then change the encoding to the encoding given by the value of the charset attribute.

Otherwise, if the element has an http-equiv attribute whose value is an ASCII case-insensitive match for the string "Content-Type", and the element has a content attribute, and applying the algorithm for extracting a character encoding from a meta element to that attribute's value returns a supported ASCII-compatible character encoding or a UTF-16 encoding, and the confidence is currently tentative, then change the encoding to the extracted encoding.

A start tag whose tag name is "title"

Follow the generic RCDATA element parsing algorithm.

A start tag whose tag name is "noscript", if the scripting flag is enabled

A start tag whose tag name is one of: "noframes", "style"

Follow the generic raw text element parsing algorithm.

A start tag whose tag name is "noscript", if the scripting flag is disabled

Insert an HTML element for the token.

Switch the insertion mode to "in head noscript".

A start tag whose tag name is "script"

Run these steps:

1. Create an element for the token in the HTML namespace.

2. Mark the element as being "parser-inserted" and unset the element's "force-async" flag.

   This ensures that, if the script is external, any document.write() calls in the script will execute in-line, instead of blowing the document away, as would happen in most other cases. It also prevents the script from executing until the end tag is seen.

3. If the parser was originally created for the HTML fragment parsing algorithm, then mark the script element as "already started". (fragment case)

4. Append the new element to the current node and push it onto the stack of open elements.

5. Switch the tokenizer to the script data state.

6. Let the original insertion mode be the current insertion mode.

7. Switch the insertion mode to "text".

An end tag whose tag name is "head"

Pop the current node (which will be the head element) off the stack of open elements.

Switch the insertion mode to "after head".

An end tag whose tag name is one of: "body", "html", "br"

Act as described in the "anything else" entry below.

A start tag whose tag name is "head"

Any other end tag

Parse error. Ignore the token.

Anything else

Act as if an end tag token with the tag name "head" had been seen, and reprocess the current token.

8.2.5.4.5 The "in head noscript" insertion mode

When the user agent is to apply the rules for the "in head noscript" insertion mode, the user agent must handle the token as follows:

A DOCTYPE token

Parse error. Ignore the token.

A start tag whose tag name is "html"

Process the token using the rules for the "in body" insertion mode.

An end tag whose tag name is "noscript"

Pop the current node (which will be a noscript element) from the stack of open elements; the new current node will be a head element.

Switch the insertion mode to "in head".

A character token that is one of U+0009 CHARACTER TABULATION, "LF" (U+000A), "FF" (U+000C), "CR" (U+000D), or U+0020 SPACE

A comment token

A start tag whose tag name is one of: "basefont", "bgsound", "link", "meta", "noframes", "style"

Process the token using the rules for the "in head" insertion mode.

An end tag whose tag name is "br"

Act as described in the "anything else" entry below.

A start tag whose tag name is one of: "head", "noscript"

Any other end tag

Parse error. Ignore the token.

Anything else

Parse error. Act as if an end tag with the tag name "noscript" had been seen and reprocess the current token.

8.2.5.4.6 The "after head" insertion mode

When the user agent is to apply the rules for the "after head" insertion mode, the user agent must handle the token as follows:

A character token that is one of U+0009 CHARACTER TABULATION, "LF" (U+000A), "FF" (U+000C), "CR" (U+000D), or U+0020 SPACE

Insert the character into the current node.

A comment token

Append a Comment node to the current node with the data attribute set to the data given in the comment token.

A DOCTYPE token

Parse error. Ignore the token.

A start tag whose tag name is "html"

Process the token using the rules for the "in body" insertion mode.

A start tag whose tag name is "body"

Insert an HTML element for the token.

Set the frameset-ok flag to "not ok".

Switch the insertion mode to "in body".

A start tag whose tag name is "frameset"

Insert an HTML element for the token.

Switch the insertion mode to "in frameset".

A start tag token whose tag name is one of: "base", "basefont", "bgsound", "link", "meta", "noframes", "script", "style", "title"

Parse error.

Push the node pointed to by the head element pointer onto the stack of open elements.

Process the token using the rules for the "in head" insertion mode.

Remove the node pointed to by the head element pointer from the stack of open elements.

The head element pointer cannot be null at this point.

An end tag whose tag name is one of: "body", "html", "br"

Act as described in the "anything else" entry below.

A start tag whose tag name is "head"

Any other end tag

Parse error. Ignore the token.

Anything else

Act as if a start tag token with the tag name "body" and no attributes had been seen, then set the frameset-ok flag back to "ok", and then reprocess the current token.