Rewrite Text node attaching to not be N^2

Source/core/html/parser/HTMLConstructionSite.h

Index: Source/core/html/parser/HTMLConstructionSite.h
diff --git a/Source/core/html/parser/HTMLConstructionSite.h b/Source/core/html/parser/HTMLConstructionSite.h
index cac778c02c85fffa9c32b77cda5a94dea932bc09..46173e6e20c4b4a38408d178cfcbe729f53ec809 100644
--- a/Source/core/html/parser/HTMLConstructionSite.h
+++ b/Source/core/html/parser/HTMLConstructionSite.h
@@ -41,6 +41,7 @@ namespace WebCore {
 struct HTMLConstructionSiteTask {
     enum Operation {
         Insert,
+        InsertText, // Handles possible merging of text nodes.
         InsertAlreadyParsedChild, // Insert w/o calling begin/end parsing.
         Reparent,
         TakeAllChildren,
@@ -96,8 +97,18 @@ public:
     ~HTMLConstructionSite();
 
     void detach();
+
+    // executeQueuedTasks empties the queue but does not flush pending text.
+    // NOTE: Possible reentrancy via JavaScript execution.
     void executeQueuedTasks();
 
+    // flushPendingText turns pending text into queued Text insertions, but does not execute them.
+    void flushPendingText();
+
+    // flush calls both flushPendingText and executeQueuedTasks.
+    // NOTE: Possible reentrancy via JavaScript execution.
+    void flush();
+
     void setDefaultCompatibilityMode();
     void processEndOfFile();
     void finishedParsing();
@@ -216,6 +227,47 @@ private:
 
     TaskQueue m_taskQueue;
 
+    struct PendingText {
+        PendingText()
+            : whitespaceMode(WhitespaceUnknown)
+        {
+        }
+
+        void append(PassRefPtr<ContainerNode> newParent, PassRefPtr<Node> newNextChild, const String& newString, WhitespaceMode newWhitespaceMode)
+        {
+            ASSERT(!parent || parent == newParent);
+            parent = newParent;
+            ASSERT(!nextChild || nextChild == newNextChild);
+            nextChild = newNextChild;
+            stringBuilder.append(newString);
+            whitespaceMode = std::min(whitespaceMode, newWhitespaceMode);
+        }
+
+        void swap(PendingText& other)
+        {
+            std::swap(whitespaceMode, other.whitespaceMode);
+            parent.swap(other.parent);
+            nextChild.swap(other.nextChild);
+            stringBuilder.swap(other.stringBuilder);
+        }
+
+        bool isEmpty()
+        {
+            // When the stringbuilder is empty, the parent and whitespace should also be "empty".
+            ASSERT(stringBuilder.isEmpty() == !parent);
+            ASSERT(!stringBuilder.isEmpty() || !nextChild);
+            ASSERT(!stringBuilder.isEmpty() || (whitespaceMode == WhitespaceUnknown));
+            return stringBuilder.isEmpty();
+        }
+
+        RefPtr<ContainerNode> parent;
+        RefPtr<Node> nextChild;
+        StringBuilder stringBuilder;
+        WhitespaceMode whitespaceMode;
+    };
+
+    PendingText m_pendingText;
+
     ParserContentPolicy m_parserContentPolicy;
     bool m_isParsingFragment;