Rewrite Text node attaching to not be N^2

Source/core/html/parser/HTMLTreeBuilder.cpp

 /*
  * Copyright (C) 2010 Google, Inc. All Rights Reserved.
  * Copyright (C) 2011 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
@@ skipping 340 matching lines @@
     ASSERT(!fragment->hasChildNodes());
 }
 
 HTMLTreeBuilder::FragmentParsingContext::~FragmentParsingContext()
 {
 }
 
 PassRefPtr<Element> HTMLTreeBuilder::takeScriptToProcess(TextPosition& scriptStartPosition)
 {
     ASSERT(m_scriptToProcess);
+    ASSERT(!m_tree.hasPendingTasks());
     // Unpause ourselves, callers may pause us again when processing the script.
     // The HTML5 spec is written as though scripts are executed inside the tree
     // builder.  We pause the parser to exit the tree builder, and then resume
     // before running scripts.
     scriptStartPosition = m_scriptToProcessStartPosition;
     m_scriptToProcessStartPosition = uninitializedPositionValue1();
     return m_scriptToProcess.release();
 }
 
 void HTMLTreeBuilder::constructTree(AtomicHTMLToken* token)
@@ skipping 20 matching lines @@
     // We might be detached now.
 }
 
 void HTMLTreeBuilder::processToken(AtomicHTMLToken* token)
 {
     if (token->type() == HTMLToken::Character) {
         processCharacter(token);
         return;
     }
 
+    // Any non-character token needs to cause us to flush any pending text immediately.
+    // NOTE: flush() can cause any queued tasks to execute, possibly re-entering the parser.
+    m_tree.flush();
     m_shouldSkipLeadingNewline = false;
 
     switch (token->type()) {
     case HTMLToken::Uninitialized:
     case HTMLToken::Character:
         ASSERT_NOT_REACHED();
         break;
     case HTMLToken::DOCTYPE:
         processDoctypeToken(token);
         break;
@@ skipping 2299 matching lines @@
         if (token->type() == HTMLToken::Character)
             return false;
     }
     if (token->type() == HTMLToken::EndOfFile)
         return false;
     return true;
 }
 
 void HTMLTreeBuilder::processTokenInForeignContent(AtomicHTMLToken* token)
 {
+    if (token->type() == HTMLToken::Character) {
+        const String& characters = token->characters();
+        m_tree.insertTextNode(characters);
+        if (m_framesetOk && !isAllWhitespaceOrReplacementCharacters(characters))
+            m_framesetOk = false;
+        return;
+    }
+
+    m_tree.flush();
     RefPtr<HTMLStackItem> adjustedCurrentNode = adjustedCurrentStackItem();
 
     switch (token->type()) {
     case HTMLToken::Uninitialized:
         ASSERT_NOT_REACHED();
         break;
     case HTMLToken::DOCTYPE:
         parseError(token);
         break;
     case HTMLToken::StartTag: {
@@ skipping 78 matching lines @@
                 if (nodeRecord->stackItem()->isInHTMLNamespace())
                     break;
             }
         }
         // Otherwise, process the token according to the rules given in the section corresponding to the current insertion mode in HTML content.
         processEndTag(token);
         break;
     }
     case HTMLToken::Comment:
         m_tree.insertComment(token);
-        return;
-    case HTMLToken::Character: {
-        const String& characters = token->characters();
-        m_tree.insertTextNode(characters);
-        if (m_framesetOk && !isAllWhitespaceOrReplacementCharacters(characters))
-            m_framesetOk = false;
         break;
-    }
+    case HTMLToken::Character:
     case HTMLToken::EndOfFile:
         ASSERT_NOT_REACHED();
         break;
     }
 }
 
 void HTMLTreeBuilder::finished()
 {
     if (isParsingFragment())
         return;
 
     ASSERT(m_templateInsertionModes.isEmpty());
     ASSERT(m_isAttached);
     // Warning, this may detach the parser. Do not do anything else after this.
     m_tree.finishedParsing();
 }
 
 void HTMLTreeBuilder::parseError(AtomicHTMLToken*)
 {
 }
 
 } // namespace WebCore