Compare Revisions

HTML parser threading

Change Revisions

Revision 65924:

Revision 65924 by Hsivonen on

Revision 65925:

Revision 65925 by Hsivonen on

Title:
HTML parser threading
HTML parser threading
Slug:
Gecko/HTML_parser_threading
Gecko/HTML_parser_threading
Tags:
Gecko
Gecko
Content:

Revision 65924
Revision 65925
n11      The HTML parser parses data received from the network off-tn11      The HTML parser parses data received from the network off-t
>he-main-thread. Data received from document.write() is parsed on >he-main-thread. Data received from <code>document.write()</code> 
>the main thread.>is parsed on the main thread.
n17      nsHtml5Parser contains the code for dealing with data from n17      <code>nsHtml5Parser</code> contains the code for dealing wi
>document.write(). (For historical reasons, it also contains unrel>th data from <code>document.write()</code>. (For historical reaso
>ated fragment parsing code that should be refactored into a separ>ns, it also contains unrelated fragment parsing code that should 
>ate class in due course.) nsHtml5StreamParser contains the code f>be refactored into a separate class in due course.) <code>nsHtml5
>or dealing with data from the network. nsHtml5Parser owns nsHtml5>StreamParser</code> contains the code for dealing with data from 
>StreamParser. Script-created parsers (i.e. parsers created using >the network. <code>nsHtml5Parser</code> owns <code>nsHtml5StreamP
>document.open()) don't have an nsHtml5StreamParser instance.>arser</code>. Script-created parsers (i.e. parsers created using 
 ><code>document.open()</code>) don't have an <code>nsHtml5StreamPa
 >rser</code> instance.
18    </p>
19    <p>18    </p>
20      nsHtml5Parser has one tokenizer/treebuilder pair for parsin
>g data from document.write(). It also has another lazily initiali 
>zed tokenizer/treebuilder for speculatively scanning the tail of  
>document.write() data when the parser blocks without parsing the  
>document.write() data to completion. 
21    </p>19    <p>
20      <code>nsHtml5Parser</code> has one tokenizer/tree builder p
 >air for parsing data from <code>document.write()</code>. It also 
 >has another lazily initialized tokenizer/tree builder for specula
 >tively scanning the tail of <code>document.write()</code> data wh
 >en the parser blocks without parsing the <code>document.write()</
 >code> data to completion.
22    <p>21    </p>
23      nsHtml5StreamParser has one tokenizer/treebuilder pair for 
>parsing data from the network. 
24    </p>22    <p>
23      <code>nsHtml5StreamParser</code> has one tokenizer/tree bui
 >lder pair for parsing data from the network.
25    <p>24    </p>
25    <p>
26      Additionally, each nsHtml5Parser has an associated nsHtml5T26      Additionally, each <code>nsHtml5Parser</code> has an associ
>reeOpExecutor that turns the output (tree operations; discussed l>ated <code>nsHtml5TreeOpExecutor</code> that turns the output (tr
>ater) of the portable parser core into actions performed on the G>ee operations; discussed later) of the portable parser core into 
>ecko DOM.>actions performed on the Gecko DOM.
n32      An nsHtml5Parser is constructed without an nsHtml5StreamParn32      An <code>nsHtml5Parser</code> is constructed without an <co
>ser due to legacy code structure around parser creation. If the p>de>nsHtml5StreamParser</code> due to legacy code structure around
>arser is not script-created, nsHtml5Parser::MarkAsNotScriptCreate> parser creation. If the parser is not script-created, <code>nsHt
>d() is called to create an nsHtml5StreamParser for the nsHtml5Par>ml5Parser::MarkAsNotScriptCreated()</code> is called to create an
>ser.> <code>nsHtml5StreamParser</code> for the <code>nsHtml5Parser.</c
 >ode>
33    </p>
34    <p>33    </p>
35      Due to legacy interface design oddities, an nsHtml5Parser i
>s initialized by calling nsHtml5Parser::Parse(nsIURI*, nsIRequest 
>Observer*, void*, nsDTDMode). That method call doesn't yet cause  
>anything to be parsed, though. Actual network data is passed to a 
>n nsIStreamListener. nsHtml5StreamParser is the nsIStreamListener 
> implementation obtained by calling nsHtml5Parser::GetStreamListe 
>ner(nsIStreamListener**). 
36    </p>34    <p>
35      Due to legacy interface design oddities, an <code>nsHtml5Pa
 >rser</code> is initialized by calling <code>nsHtml5Parser::Parse(
 >nsIURI*, nsIRequestObserver*, void*, nsDTDMode)</code>. That meth
 >od call doesn't yet cause anything to be parsed, though. Actual n
 >etwork data is passed to an <code>nsIStreamListener</code>. <code
 >>nsHtml5StreamParser</code> is the <code>nsIStreamListener</code>
 > implementation obtained by calling <code>nsHtml5Parser::GetStrea
 >mListener(nsIStreamListener**).</code>
37    <p>36    </p>
37    <p>
38      The nsIStreamListener methods (OnStartRequest, OnDataAvaila38      The <code>nsIStreamListener</code> methods (<code>OnStartRe
>ble and OnStopRequest) are called on the main thread. OnStartRequ>quest</code><code>OnDataAvailable</code> and <code>OnStopReques
>est does all sorts of initialization on the main thread. At that >t</code>) are called on the main thread. <code>OnStartRequest</co
>point, nothing has happened on the parser thread yet and the nsHt>de> does all sorts of initialization on the main thread. At that 
>ml5StreamParser lives fully on the main thread.>point, nothing has happened on the parser thread yet and the <cod
 >e>nsHtml5StreamParser</code> lives fully on the main thread.
n44      nsHtml5StreamParser gets some of its methods called on the n44      <code>nsHtml5StreamParser</code> gets some of its methods c
>main thread and some called on the parser thread. The method impl>alled on the main thread and some called on the parser thread. Th
>ementations assert which thread they are supposed to be called on>e method implementations assert which thread they are supposed to
>.> be called on.
45    </p>
46    <p>45    </p>
47      OnDataAvailable and OnStopRequest on the main thread post r
>unnables on to the parser thread. There runnables obtain mTokeniz 
>erMutex and call DoDataAvailable and DoStopRequest, repectively,  
>on the parser thread. These two methods along with TimerFlush (di 
>scussed later) are the entry points from the parser thread event  
>loop into nsHtml5StreamParser. 
48    </p>46    <p>
47      <code>OnDataAvailable</code> and <code>OnStopRequest</code>
 > on the main thread post runnables on to the parser thread. There
 > runnables obtain <code>mTokenizerMutex</code> and call <code>DoD
 >ataAvailable</code> and <code>DoStopRequest</code>, repectively, 
 >on the parser thread. These two methods along with <code>TimerFlu
 >sh</code> (discussed later) are the entry points from the parser 
 >thread event loop into <code>nsHtml5StreamParser.</code>
49    <p>48    </p>
50      The runnables hold mTokenizerMutex for the entire duration 
>of the DoDataAvailable or DoStopRequest call. mTokenizerMutex pro 
>tects most data structures on nsHtml5StreamParser from concurrent 
> access. 
51    </p>49    <p>
50      The runnables hold <code>mTokenizerMutex</code> for the ent
 >ire duration of the <code>DoDataAvailable</code> or <code>DoStopR
 >equest</code> call. <code>mTokenizerMutex</code> protects most da
 >ta structures on <code>nsHtml5StreamParser</code> from concurrent
 > access.
52    <p>51    </p>
53      The runnables need to keep the nsHtml5StreamParser instance52    <p>
> alive, so they have to AddRef it. However, if they Released on t 
>he parser thread, nsHtml5StreamParser could be deleted from the p 
>arser thread, which would lead to all sorts of badness, because n 
>sHtml5StreamParser has fields that hold objects that aren't safe  
>to Release except from the main thread. The runnables use nsHtml5 
>RefPtr&lt;nshtml5streamparser&gt;. nsHtml5RefPtr sends runnables  
>back to the main thread to call Release on nsHtml5StreamParser on 
> the main thread.&lt;/nshtml5streamparser&gt; 
53      The runnables need to keep the <code>nsHtml5StreamParser</c
 >ode> instance alive, so they have to <code>AddRef</code> it. Howe
 >ver, if they <code>Release</code>d on the parser thread, <code>ns
 >Html5StreamParser</code> could be <code>delete</code>d from the p
 >arser thread, which would lead to all sorts of badness, because <
 >code>nsHtml5StreamParser</code> has fields that hold objects that
 > aren't safe to <code>Release</code> except from the main thread.
 > The runnables use <code>nsHtml5RefPtr&lt;nsHtml5StreamParser&gt;
 ></code>. <code>nsHtml5RefPtr</code> sends runnables back to the m
 >ain thread to call Release on <code>nsHtml5StreamParser</code> on
 > the main thread.
n59      Initially, DoDataAvailable performs character encoding snifn59      Initially, <code>DoDataAvailable</code> performs character 
>fing on the data if an encoding wasn't declared on the enclosing >encoding sniffing on the data if an encoding wasn't declared on t
>protocol (HTTP) level. Once a Unicode decoder has been set up, Do>he enclosing protocol (HTTP) level. Once a Unicode decoder has be
>DataAvailable passes the byte data to the decoder whose output is>en set up, <code>DoDataAvailable</code> passes the byte data to t
> accumulated into a linked list of nsHtml5OwningUTF16Buffer objec>he decoder whose output is accumulated into a linked list of <cod
>ts.>e>nsHtml5OwningUTF16Buffer</code> objects.
60    </p>
61    <p>60    </p>
61    <p>
62      nsHtml5OwningUTF16Buffer objects are then passed to the tok62      <code>nsHtml5OwningUTF16Buffer</code> objects are then pass
>enizer in sequence by the ParseAvailableData() method. The tokeni>ed to the tokenizer in sequence by the <code>ParseAvailableData()
>zer calls into the tree builder which outputs nsHtml5TreeOperatio></code> method. The tokenizer calls into the tree builder which o
>n objects (tree ops) into a queue. Each tree op represents a smal>utputs <code>nsHtml5TreeOperation</code> objects (tree ops) into 
>l operation, such as element creation or appending a node into an>a queue. Each tree op represents a small operation, such as eleme
>other, that can later be performed on the main thread.>nt creation or appending a node into another, that can later be p
 >erformed on the main thread.
63    </p>
64    <p>63    </p>
65      Note that mTokenizerMutex is being held by the parser threa
>d for the entire time that the tokenizer runs. ParseAvailableData 
>() checks for parser termination or interruption from time to tim 
>e. The termination and interruption indicators are guarded by a m 
>ore narrowly scoped mTerminatedMutex, so ParseAvailableData() has 
> the opportunity to receive an order to terminate or interrupt ev 
>en while the parser thread is holding mTerminatedMutex. 
66    </p>64    <p>
65      Note that <code>mTokenizerMutex</code> is being held by the
 > parser thread for the entire time that the tokenizer runs. <code
 >>ParseAvailableData()</code> checks for parser termination or int
 >erruption from time to time. The termination and interruption ind
 >icators are guarded by a more narrowly scoped <code>mTerminatedMu
 >tex</code>, so <code>ParseAvailableData()</code> has the opportun
 >ity to receive an order to terminate or interrupt even while the 
 >parser thread is holding <code>mTerminatedMutex</code>.
67    <p>66    </p>
67    <p>
68      The tree op queue is flushed to the main thread from time t68      The tree op queue is flushed to the main thread from time t
>o time. There's a timer that calls TimerFlush() (which takes mTok>o time. There's a timer that calls <code>TimerFlush()</code> (whi
>enizerMutex). Tree ops from the queue in the tree builder are mov>ch takes <code>mTokenizerMutex</code>). Tree ops from the queue i
>ed to a tree op stage (nsHtml5TreeOpStage). The staging queue is >n the tree builder are moved to a tree op stage (<code>nsHtml5Tre
>protected by a mutex. This way, the queues into which tree ops ar>eOpStage)</code>. The staging queue is protected by a mutex. This
>e produced and the queues from which they are consumed don't need> way, the queues into which tree ops are produced and the queues 
> to involve a mutex on each modification. It's more efficient to >from which they are consumed don't need to involve a mutex on eac
>obtain a mutex only every once in a while when a whole bunch of t>h modification. It's more efficient to obtain a mutex only every 
>ree ops is moved to or from the staging queue.>once in a while when a whole bunch of tree ops is moved to or fro
 >m the staging queue.
69    </p>
70    <p>69    </p>
70    <p>
71      After some tree ops have been move the the staging queue, t71      After some tree ops have been move the the staging queue, t
>he nsIRunnable held in mExecutorFlusher is dispatched to the main>he <code>nsIRunnable</code> held in <code>mExecutorFlusher</code>
> thread. (The same runnable is used repeatedly in order to avoid > is dispatched to the main thread. (The same runnable is used rep
>cross-thread refcounting issues.)>eatedly in order to avoid cross-thread refcounting issues.)
n80      Attribute holders (nsHtml5HtmlAttributes objects) are allocn80      Attribute holders (<code>nsHtml5HtmlAttributes</code> objec
>ated using |new| by the tokenizer. The tree builder either transf>ts) are allocated using <code>new</code> by the tokenizer. The tr
>ers an attribute holder to a tree op whose destructor explicitly >ee builder either transfers an attribute holder to a tree op whos
>deletes the attribute holder or if the tree builder ends up ignor>e destructor explicitly <code>delete</code>s the attribute holder
>ing an attribute holder, the tree builder deletes the attribute h> or if the tree builder ends up ignoring an attribute holder, the
>older explicitly.> tree builder <code>delete</code>s the attribute holder explicitl
 >y.
81    </p>
82    <p>81    </p>
83      Attribute values, public identifiers (in doctype) and syste
>m identifiers (in doctype) are heap-allocated nsString objects (i 
>.e. pointed to by nsString*!). Attribute values nsStrings are del 
>eted by the attribute holder when it gets deleted. Public identif 
>iers and system identifiers are deleted by the tree op or by the  
>portable parser core if they don't make it as far a tree op. The  
>backing nsStringBuffers are thread-safely refcounted appropriatel 
>y when the nsString goes away. (Aside: It would make more sense t 
>o make the parser deal with nsStringBuffers directly without havi 
>ng heap-allocated nsStrings involved.) 
84    </p>82    <p>
83      Attribute values, public identifiers (in doctype) and syste
 >m identifiers (in doctype) are heap-allocated <code>nsString</cod
 >e> objects (i.e. pointed to by <code>nsString*</code>!). Attribut
 >e values <code>nsStrings</code> are deleted by the attribute hold
 >er when it gets deleted. Public identifiers and system identifier
 >s are deleted by the tree op or by the portable parser core if th
 >ey don't make it as far a tree op. The backing <code>nsStringBuff
 >er</code>s are thread-safely refcounted appropriately when the <c
 >ode>nsString</code> goes away. (Aside: It would make more sense t
 >o make the parser deal with <code>nsStringBuffer</code>s directly
 > without having heap-allocated <code>nsString</code>s involved.)
85    <p>84    </p>
86      Element names, attribute names and the doctype name are rep
>resented as nsIAtoms. Pre-interned attribute and element names ho 
>ld atoms that are actually app-wide nsStaticAtoms. Since nsStatic 
>Atoms are valid app-wide, these atoms work right app-wide on the  
>main thread. For other atoms, the parser use nsHtml5Atom objects  
>that are atomic only within the scope of an nsHtml5AtomTable. The 
>re is one nsHtml5AtomTable per each nsHtml5Parser and one per eac 
>h nsHtml5StreamParser. Thus, each tokenizer/tree builder pair see 
>s atoms that are atomic (pointer-comparable) within the tokenizer 
>/tree builder pair. However, when tree ops are executed, every at 
>om has to be tested for being a static atom (using IsStaticAtom() 
>). If the atom isn't static, a corresponding normal main-thread d 
>ynamically-allocated atom has to be obtained for the same string  
>and used instead of the nsHtml5Atom. nsHtml5Atom objects are guar 
>anteed be immutable and to stay alive for the lifetime of the par 
>ser instance, so it's safe for the main thread to call their meth 
>ods (as is necessary to find the corresponding normal atom). 
87    </p>85    <p>
86      Element names, attribute names and the doctype name are rep
 >resented as <code>nsIAtom</code>s. Pre-interned attribute and ele
 >ment names hold atoms that are actually app-wide <code>nsStaticAt
 >om</code>s. Since <code>nsStaticAtom</code>s are valid app-wide, 
 >these atoms work right app-wide on the main thread. For other ato
 >ms, the parser use <code>nsHtml5Atom</code> objects that are atom
 >ic only within the scope of an <code>nsHtml5AtomTable</code>. The
 >re is one <code>nsHtml5AtomTable</code> per each <code>nsHtml5Par
 >ser</code> and one per each <code>nsHtml5StreamParser</code>. Thu
 >s, each tokenizer/tree builder pair sees atoms that are atomic (p
 >ointer-comparable) within the tokenizer/tree builder pair. Howeve
 >r, when tree ops are executed, every atom has to be tested for be
 >ing a static atom (using <code>IsStaticAtom()</code>). If the ato
 >m isn't static, a corresponding normal main-thread dynamically-al
 >located atom has to be obtained for the same string and used inst
 >ead of the <code>nsHtml5Atom</code>. <code>nsHtml5Atom</code> obj
 >ects are guaranteed be immutable and to stay alive for the lifeti
 >me of the parser instance, so it's safe for the main thread to ca
 >ll their methods (as is necessary to find the corresponding norma
 >l atom).
88    <p>87    </p>
89      References to DOM nodes in tree ops are of type nsIContent*
>* and are called content handles. A handle points to memory alloc 
>ated by the tree builder and guaranteed to stick around for the l 
>ife time of the parser. The tree builder never deferences a conte 
>nt handle. In fact, a content handle won't have an actual node be 
>hind it initially. Only when the tree op executor executes a node 
> creation tree op, the nsIContent* that points to the node gets w 
>ritten to the memory location pointed to by the nsIContent**. For 
> any given content handle, the node creation tree op is always th 
>e first tree op in queue that uses that handle, so subsequent non 
>-creation tree ops can safely dereference the handle to obtain a  
>real node. Nodes created by tree ops owned by the parser for the  
>lifetime of the parser, so for refcounting purposes, the parser o 
>wns each nsIContent object it creates by one reference no matter  
>how many copies of the content handle for the node exist inside t 
>he parser. (This indeed means that removing parser-created nodes  
>from the DOM during parsing doesn't relase memory until the parse 
>r stops parsing, which is, in theory, a problem for long polling  
>using HTML in an iframe e.g. for a chat app.) 
90    </p>88    <p>
89      References to DOM nodes in tree ops are of type <code>nsICo
 >ntent**</code> and are called content handles. A handle points to
 > memory allocated by the tree builder and guaranteed to stick aro
 >und for the life time of the parser. The tree builder never deref
 >erences a content handle. In fact, a content handle won't have an
 > actual node behind it initially. Only when the tree op executor 
 >executes a node creation tree op, the <code>nsIContent*</code> th
 >at points to the node gets written to the memory location pointed
 > to by the <code>nsIContent**</code>. For any given content handl
 >e, the node creation tree op is always the first tree op in queue
 > that uses that handle, so subsequent non-creation tree ops can s
 >afely dereference the handle to obtain a real node. Nodes created
 > by tree ops owned by the parser for the lifetime of the parser, 
 >so for refcounting purposes, the parser owns each <code>nsIConten
 >t</code> object it creates by one reference no matter how many co
 >pies of the content handle for the node exist inside the parser. 
 >(This indeed means that removing parser-created nodes from the DO
 >M during parsing doesn't release memory until the parser stops pa
 >rsing, which is, in theory, a problem for long polling using HTML
 > in an iframe e.g. for a chat app.)
91    <p>90    </p>
91    <p>
92      Some tree ops hold char or PRUnichar arrays. Those arrays a92      Some tree ops hold <code>char</code> or <code>PRUnichar</co
>re allocated when creating the tree op and delete[]d by the destr>de> arrays. Those arrays are allocated when creating the tree op 
>uctor of nsHtml5TreeOperation. Hence, data gets copied to and fro>and <code>delete[]</code>d by the destructor of <code>nsHtml5Tree
>m these arrays.>Operation</code>. Hence, data gets copied to and from these array
 >s.
n98      When the executor flushing runnable fires on the main threan98      When the executor flushing runnable fires on the main threa
>d, it calls nsHtml5TreeOpExecutor::RunFlushLoop(). This method re>d, it calls <code>nsHtml5TreeOpExecutor::RunFlushLoop()</code>. T
>turns immediately if another invocation of it is already on the c>his method returns immediately if another invocation of it is alr
>all stack (nested event loop case). The method then enter a loop >eady on the call stack (nested event loop case). The method then 
>that has a bunch of return conditions (including parser terminati>enter a loop that has a bunch of return conditions (including par
>on).>ser termination).
99    </p>
100    <p>99    </p>
100    <p>
101      The loop first flushes speculative loads (creation discusse101      The loop first flushes speculative loads (creation discusse
>d later). If the executor is reading from a stage (i.e. the ops a>d later). If the executor is reading from a stage (i.e. the ops a
>re coming from the parser thread), the executor moves the tree op>re coming from the parser thread), the executor moves the tree op
>s from the staging queue into its own queue. (Again, here we get >s from the staging queue into its own queue. (Again, here we get 
>to move a bunch of tree ops by obtaining a mutex once instead of >to move a bunch of tree ops by obtaining a mutex once instead of 
>having to synchronize thread on a per-tree op basis.) If the exec>having to synchronize thread on a per-tree op basis.) If the exec
>utor isn't reading from a stage, it calls nsHtml5Parser::ParseUnt>utor isn't reading from a stage, it calls <code>nsHtml5Parser::Pa
>ilBlocked() to parse potential document.write()-generated data in>rseUntilBlocked()</code> to parse potential <code>document.write(
>to tree ops.>)</code>-generated data into tree ops.
102    </p>
103    <p>102    </p>
103    <p>
104      The outer loop then has an inner loop that iterates over th104      The outer loop then has an inner loop that iterates over th
>e tree ops in the executor's queue and calls Perform on each one.>e tree ops in the executor's queue and calls Perform on each one.
> Parser termination is checked before each tree op for an early r> Parser termination is checked before each tree op for an early r
>eturn, because, unfortunately, Gecko expects parsers to be able t>eturn, because, unfortunately, Gecko expects parsers to be able t
>o terminate immediately. After each tree op except the last one i>o terminate immediately. After each tree op except the last one i
>n the queue, the clock time is checked to see if RunFlushLoop() h>n the queue, the clock time is checked to see if <code>RunFlushLo
>as spent too much time without returning to the event loop. If to>op()</code> has spent too much time without returning to the even
>o much time has been spent, a runnable for calling RunFlushLoop()>t loop. If too much time has been spent, a runnable for calling <
> again is dispatched and an early return made before all tree ops>code>RunFlushLoop()</code> again is dispatched and an early retur
> have been executed. (Only the already executed ops are destructe>n made before all tree ops have been executed. (Only the already 
>d and the rest are left in the queue.)>executed ops are destructed and the rest are left in the queue.)
105    </p>
106    <p>105    </p>
106    <p>
107      The last op in the queue may be an op for attempting to exe107      The last op in the queue may be an op for attempting to exe
>cute a script that may blocks the parser (ops for attempting to e>cute a script that may blocks the parser (ops for attempting to e
>xecute async and defer scripts are normal tree ops and don't need>xecute async and defer scripts are normal tree ops and don't need
> to be the last op in a queue). The parts of the parser that driv> to be the last op in a queue). The parts of the parser that driv
>e the tokenizer/tree builder pairs guarantee to flush tree ops im>e the tokenizer/tree builder pairs guarantee to flush tree ops im
>mediately if a script execution tree op is generated. (The tree b>mediately if a script execution tree op is generated. (The tree b
>uilder makes the tokenizer return immediately when such an op is >uilder makes the tokenizer return immediately when such an op is 
>generated.) Thus, a tree op that may cause the parser to can only>generated.) Thus, a tree op that may cause the parser to can only
> occur as the last op a queue that RunFlushLoop sees.> occur as the last op a queue that <code>RunFlushLoop</code> sees
 >.
n113      When the parser thread sees that it has generated a tree opn113      When the parser thread sees that it has generated a tree op
> that attempts to execute a (non-async, non-defer) script, it sta> that attempts to execute a (non-async, non-defer) script, it sta
>rts speculating. It acquires mSpeculationMutex and while holding >rts speculating. It acquires <code>mSpeculationMutex</code> and w
>it, it creates a new speculation and adds it to the queue of spec>hile holding it, it creates a new speculation and adds it to the 
>ulations, flushes the tree ops to the main thread, marks the nsHt>queue of speculations, flushes the tree ops to the main thread, m
>ml5StreamParser as being in a speculating state and sets the newl>arks the <code>nsHtml5StreamParser</code> as being in a speculati
>y created speculation object as the tree op sink (instead of the >ng state and sets the newly created speculation object as the tre
>tree op stage described earlier) of the tree builder. The specula>e op sink (instead of the tree op stage described earlier) of the
>tion object has a queue of tree ops (into which the tree builder > tree builder. The speculation object has a queue of tree ops (in
>will now flush ops to instead of the tree op stage), an owning re>to which the tree builder will now flush ops to instead of the tr
>ference to the nsHtml5OwningUTF16Buffer that contains the startin>ee op stage), an owning reference to the <code>nsHtml5OwningUTF16
>g point of the speculation, an index into the nsHtml5OwningUTF16B>Buffer</code> that contains the starting point of the speculation
>uffer defining the exact starting point within the buffer, the li>, an index into the <code>nsHtml5OwningUTF16Buffer</code> definin
>ne number of the tokenizer at that point and a snapshop of the tr>g the exact starting point within the buffer, the line number of 
>ee op state. The line number and the snapshop are also added to t>the tokenizer at that point and a snapshop of the tree op state. 
>he tree op that attempts to execute scripts (before flushing it).>The line number and the snapshop are also added to the tree op th
 >at attempts to execute scripts (before flushing it).
n122      After the speculation has been started and mSpeculationMuten122      After the speculation has been started and <code>mSpeculati
>x released, the parser thread will parse incoming data and the tr>onMutex</code> released, the parser thread will parse incoming da
>ee builder will produce tree ops so that they get flushed into th>ta and the tree builder will produce tree ops so that they get fl
>e queue in the speculation object.>ushed into the queue in the speculation object.
n134      On the main thread, when the tree op executor executes a trn134      On the main thread, when the tree op executor executes a tr
>ee op that attempts to execute a script, the tree op is first che>ee op that attempts to execute a script, the tree op is first che
>cked for a tree builder state snapshot. There will be a snapshot >cked for a tree builder state snapshot. There will be a snapshot 
>if the tree op came from the parser thread. There won't be one if>if the tree op came from the parser thread. There won't be one if
> the tree op came from document.write() on the main thread (discu> the tree op came from <code>document.write()</code> on the main 
>ssed later). If there is a snapshot, the tokenizer used for parsi>thread (discussed later). If there is a snapshot, the tokenizer u
>ng document.write()-originating data on the main thread is reset >sed for parsing <code>document.write()</code>-originating data on
>to the data state. There's no need to snapshot the tokenizer stat> the main thread is reset to the data state. There's no need to s
>e, because the state of the tokenizer is always the same immediat>napshot the tokenizer state, because the state of the tokenizer i
>ely after the tokenizer has emitted a script end tag. Then the tr>s always the same immediately after the tokenizer has emitted a s
>ee builder that is used for parsing document.write()-originating >cript end tag. Then the tree builder that is used for parsing <co
>data is initialized from the state snapshot. Now the tokenizer/tr>de>document.write()</code>-originating data is initialized from t
>ee builder pair used for parsing document.write() data is in the >he state snapshot. Now the tokenizer/tree builder pair used for p
>same state that the off-the-main-thread tokenizer/tree builder pa>arsing <code>document.write()</code> data is in the same state th
>ir was immediately after processing the script end tag.>at the off-the-main-thread tokenizer/tree builder pair was immedi
 >ately after processing the script end tag.
135    </p>
136    <p>135    </p>
136    <p>
137      The tree op executor then attempts to execute the script. T137      The tree op executor then attempts to execute the script. T
>his operation either executes an inline script right away or tell>his operation either executes an inline script right away or tell
>s the parser to block (for external scripts). If the parser is to>s the parser to block (for external scripts). If the parser is to
>ld to block, the script loader will unblock the parser before the>ld to block, the script loader will unblock the parser before the
> external script executes. If the script was executed without blo> external script executes. If the script was executed without blo
>cking, the executor dispatches an event to reflush itself. (Remem>cking, the executor dispatches an event to reflush itself. (Remem
>ber that reflushing ends up calling nsHtml5Parser::ParseUntilBloc>ber that reflushing ends up calling <code>nsHtml5Parser::ParseUnt
>ked(). That method is responsible for moving back to consuming tr>ilBlocked()</code>. That method is responsible for moving back to
>ee ops from the parser thread via the staging area.)> consuming tree ops from the parser thread via the staging area.)
138    </p>
139    <h3>138    </p>
140      document.write()
141    </h3>139    <h3>
140      <code><code>document.write()</code></code>
142    <p>141    </h3>
143      Calls to document.write() push data to the tokenizer/tree b
>uilder pair that exists on the main thread solely for parsing dat 
>a from document.write(). If the parser isn't blocked, document.wr 
>ite() parses input into tree ops synchronously and flushes the tr 
>ee ops synchronously by calling nsHtml5TreeOpExecutor::FlushDocum 
>entWrite(). Unlike nsHtml5TreeOpExecutor::RunFlushLoop(), nsHtml5 
>TreeOpExecutor::FlushDocumentWrite() does not sample the clock to 
> return early. 
144    </p>142    <p>
143      Calls to <code>document.write()</code> push data to the tok
 >enizer/tree builder pair that exists on the main thread solely fo
 >r parsing data from <code>document.write()</code>. If the parser 
 >isn't blocked, <code>document.write()</code> parses input into tr
 >ee ops synchronously and flushes the tree ops synchronously by ca
 >lling <code>nsHtml5TreeOpExecutor::FlushDocumentWrite()</code>. U
 >nlike <code>nsHtml5TreeOpExecutor::RunFlushLoop()</code>, <code>n
 >sHtml5TreeOpExecutor::FlushDocumentWrite()</code> does not sample
 > the clock to return early.
145    <p>144    </p>
146      Inline scripts that arrive from document.write() are execut
>ed synchronously (if the parser isn't already blocked). External  
>scripts arriving from document.write() block the parser. 
147    </p>145    <p>
146      Inline scripts that arrive from <code>document.write()</cod
 >e> are executed synchronously (if the parser isn't already blocke
 >d). External scripts arriving from <code>document.write()</code> 
 >block the parser.
148    <p>147    </p>
149      If there is data in document.write() input after a an exter
>nal script (or any data at all if a previous document.write() cal 
>l has contained an external script and blocked the parser), the d 
>ata is left is a linked list of nsHtml5OwningUTF16Buffer objects. 
> (How exactly data is inserted into the buffer list depends on pa 
>rser keys when document.write() is invoked re-entrantly, but that 
>'s outside the scope of this document, since this document is abo 
>ut parser threading.) 
150    </p>148    <p>
149      If there is data in <code>document.write()</code> input aft
 >er a an external script (or any data at all if a previous <code>d
 >ocument.write()</code> call has contained an external script and 
 >blocked the parser), the data is left is a linked list of <code>n
 >sHtml5OwningUTF16Buffer</code> objects. (How exactly data is inse
 >rted into the buffer list depends on parser keys when <code>docum
 >ent.write()</code> is invoked re-entrantly, but that's outside th
 >e scope of this document, since this document is about parser thr
 >eading.)
151    <p>150    </p>
151    <p>
152      Whenever the argument of document.write() isn't tokenized t152      Whenever the argument of <code>document.write()</code> isn'
>o completion synchronously, the part left unprocessed by the main>t tokenized to completion synchronously, the part left unprocesse
> document.write() tokenizer/tree builder is processed by the thir>d by the main <code>document.write()</code> tokenizer/tree builde
>d tokenizer/tree builder pair. The tree ops from that processing >r is processed by the third tokenizer/tree builder pair. The tree
>are ignored and only speculative loads are used. (Speculative loa> ops from that processing are ignored and only speculative loads 
>ds are discussed later.) The third tokenizer/tree builder pair is>are used. (Speculative loads are discussed later.) The third toke
> initialized from the state of the main document.write() tokenize>nizer/tree builder pair is initialized from the state of the main
>r/tree builder pair but can get into an inconsistent state if doc> <code>document.write()</code> tokenizer/tree builder pair but ca
>ument.write() is invoked re-entrantly. This is OK, because the tr>n get into an inconsistent state if <code>document.write()</code>
>ee ops aren't used and it's mostly harmless if the speculative lo> is invoked re-entrantly. This is OK, because the tree ops aren't
>ads are wrong.> used and it's mostly harmless if the speculative loads are wrong
 >.
153    </p>
154    <p>153    </p>
155      After an external script finishes executing, it dispatches 
>an event to reflush the tree op executor. The reflush causes a ca 
>ll to nsHtml5Parser::ParseUntilBlocked(). ParseUntilBlocked() par 
>ses data left by document.write() in the linked list of buffers,  
>because the parser was blocked. This might cause more script exec 
>ution tree ops to be generated and executed and document.write()  
>to be called more times. 
156    </p>154    <p>
155      After an external script finishes executing, it dispatches 
 >an event to reflush the tree op executor. The reflush causes a ca
 >ll to <code>nsHtml5Parser::ParseUntilBlocked()</code>. <code>Pars
 >eUntilBlocked()</code> parses data left by <code>document.write()
 ></code> in the linked list of buffers, because the parser was blo
 >cked. This might cause more script execution tree ops to be gener
 >ated and executed and <code>document.write()</code> to be called 
 >more times.
157    <p>156    </p>
157    <p>
158      When ParseUntilBlocked() exhausts the data available to it,158      When <code>ParseUntilBlocked()</code> exhausts the data ava
> it calls nsHtml5StreamParser::ContinueAfterScripts to resume the>ilable to it, it calls <code>nsHtml5StreamParser::ContinueAfterSc
> consumption of data from the network.>ripts</code> to resume the consumption of data from the network.
n164      nsHtml5StreamParser::ContinueAfterScripts runs on the main n164      <code>nsHtml5StreamParser::ContinueAfterScripts</code> runs
>thread. It acquires mSpeculationMutex in order to be able to touc> on the main thread. It acquires <code>mSpeculationMutex</code> i
>h the queue of speculations. The mutex acquisition only blocks if>n order to be able to touch the queue of speculations. The mutex 
> the parser thread happens to be setting up a new speculation obj>acquisition only blocks if the parser thread happens to be settin
>ect at the same moment.>g up a new speculation object at the same moment.
165    </p>
166    <p>165    </p>
166    <p>
167      The first speculation in the speculation queue is examined.167      The first speculation in the speculation queue is examined.
> If the the last character seen by the document.write() tokenizer> If the the last character seen by the <code>document.write()</co
> was not a carriage return, if the document.write() tokenizer is >de> tokenizer was not a carriage return, if the <code>document.wr
>in the "data" state and if the tree builder state snapshot on the>ite()</code> tokenizer is in the "data" state and if the tree bui
> speculation matches the state of the document.write() tree build>lder state snapshot on the speculation matches the state of the <
>er, the speculation has succeeded. Otherwise it has failed.>code>document.write()</code> tree builder, the speculation has su
 >cceeded. Otherwise it has failed.
168    </p>
169    <p>168    </p>
170      If there are more than one speculation in the queue and if 
>the speculation is successful, we can dequeue the first speculati 
>on while holding mSpeculationMutex without bothering the parser t 
>hread. In this case, the tree ops from the speculation are flushe 
>d into the tree op executor and ContinueAfterScripts() return ear 
>ly. (nsHtml5TreeOpExecutor::RunFlushLoop is on the call stack alr 
>eady in this case and will loop around to start flushing the ops  
>right away.) 
171    </p>169    <p>
170      If there are more than one speculation in the queue and if 
 >the speculation is successful, we can dequeue the first speculati
 >on while holding <code>mSpeculationMutex</code> without bothering
 > the parser thread. In this case, the tree ops from the speculati
 >on are flushed into the tree op executor and <code>ContinueAfterS
 >cripts()</code> return early. (<code>nsHtml5TreeOpExecutor::RunFl
 >ushLoop</code> is on the call stack already in this case and will
 > loop around to start flushing the ops right away.)
172    <p>171    </p>
172    <p>
173      If there's only one speculation or the speculation failed, 173      If there's only one speculation or the speculation failed, 
>it's necessary to bother the parser thread. In that case, the mai>it's necessary to bother the parser thread. In that case, the mai
>n thread raises an interruption flag on the nsHtml5StreamParser o>n thread raises an interruption flag on the <code>nsHtml5StreamPa
>bject to make the parser thread release mTokenizerMutex earlier. >rser</code> object to make the parser thread release <code>mToken
>The main thread then attempts to acquire mTokenizerMutex.>izerMutex</code> earlier. The main thread then attempts to acquir
 ><code>mTokenizerMutex</code>.
n191      A runnable is dispatched to the parser thread to call to man191      A runnable is dispatched to the parser thread to call to ma
>rk the parser uninterrupted and to call nsHtml5StreamParser::Pars>rk the parser uninterrupted and to call <code>nsHtml5StreamParser
>eAvailableData() on the parser thread.>::ParseAvailableData()</code> on the parser thread.
192    </p>
193    <p>192    </p>
193    <p>
194      mTokenizerMutex is released.194      <code>mTokenizerMutex</code> is released.
n200      When the tree builder on the parser thread encounters HTML n200      When the tree builder on the parser thread encounters HTML 
>script, stylesheet link, video, base or img or SVG script, style ><code>script</code>, stylesheet <code>link</code><code>video</c
>or image elements, preload operations are appended to a speculati>ode> (with a poster frame)<code>base</code> or <code>img</code>
>ve load queue. There speculative load operations are flushed to t> or SVG <code>script</code><code>style</code> or <code>image</c
>he main thread (via the staging area) whenever tree ops are flush>ode> elements, preload operations are appended to a speculative l
>ed and alse whenever nsHtml5StreamParser::ParseAvailableData() is>oad queue. There speculative load operations are flushed to the m
> about to stop working. That is, when the parser thread is parsin>ain thread (via the staging area) whenever tree ops are flushed a
>g speculatively, speculative loads continue to be flushed to the >nd alse whenever <code>nsHtml5StreamParser::ParseAvailableData()<
>main thread even though tree ops accumulate into the speculations>/code> is about to stop working. That is, when the parser thread 
>.>is parsing speculatively, speculative loads continue to be flushe
 >d to the main thread even though tree ops accumulate into the spe
 >culations.
201    </p>
202    <p>201    </p>
203      On the main thread, the speculative tokenizer/tree builder 
>pair used for parsing document.write() input that didn't get pars 
>ed by the main document.write() tokenizer/tree builder syncronous 
>ly also send speculative loads to the tree op executor. 
204    </p>202    <p>
203      On the main thread, the speculative tokenizer/tree builder 
 >pair used for parsing <code>document.write()</code> input that di
 >dn't get parsed by the main <code>document.write()</code> tokeniz
 >er/tree builder synchronously also send speculative loads to the 
 >tree op executor.
205    <p>204    </p>
205    <p>
206      The executor acts on the speculative load queue when the ru206      The executor acts on the speculative load queue when the ru
>nnable dispatched by nsHtml5StreamParser::ParseAvailableData() fi>nnable dispatched by <code>nsHtml5StreamParser::ParseAvailableDat
>res and right before executing tree ops whenever tree ops are exe>a()</code> fires and right before executing tree ops whenever tre
>cuted.>e ops are executed.
t212      Additionally, the speculative load queue is used for transft212      Additionally, the speculative load queue is used for transf
>ering information from the parser thread to the main thread when >erring information from the parser thread to the main thread when
>the information needs to arrive before starting any speculative l> the information needs to arrive before starting any speculative 
>oads and when the information in known not to be speculative. The>loads and when the information in known not to be speculative. Th
>re are two such pieces of information: the manifest URL for an Ap>ere are two such pieces of information: the manifest URL for an A
>p Cache manifest and the character encoding for the document.>pp Cache manifest and the character encoding for the document.

Back to History