Rewrite Text node attaching to not be N^2

Source/core/html/parser/HTMLConstructionSite.h

 /*
  * 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 23 matching lines @@
 #include "wtf/PassRefPtr.h"
 #include "wtf/RefPtr.h"
 #include "wtf/Vector.h"
 #include "wtf/text/StringBuilder.h"
 
 namespace WebCore {
 
 struct HTMLConstructionSiteTask {
     enum Operation {
         Insert,
+        InsertText, // Handles possible merging of text nodes.
         InsertAlreadyParsedChild, // Insert w/o calling begin/end parsing.
         Reparent,
         TakeAllChildren,
     };
 
     explicit HTMLConstructionSiteTask(Operation op)
         : operation(op)
         , selfClosing(false)
     {
     }
@@ skipping 35 matching lines @@
 class HTMLFormElement;
 
 class HTMLConstructionSite {
     WTF_MAKE_NONCOPYABLE(HTMLConstructionSite);
 public:
     HTMLConstructionSite(Document*, ParserContentPolicy);
     HTMLConstructionSite(DocumentFragment*, ParserContentPolicy);
     ~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();
+
+    // Called before every token in HTMLTreeBuilder::processToken, thus inlined:
+    void flush()
+    {
+        if (!hasPendingTasks())
+            return;
+        flushPendingText();
+        executeQueuedTasks(); // NOTE: Possible reentrancy via JavaScript execution.
+        ASSERT(!hasPendingTasks());
+    }
+
+    bool hasPendingTasks()
+    {
+        return !m_pendingText.isEmpty() || !m_taskQueue.isEmpty();
+    }
+
     void setDefaultCompatibilityMode();
     void processEndOfFile();
     void finishedParsing();
 
     void insertDoctype(AtomicHTMLToken*);
     void insertComment(AtomicHTMLToken*);
     void insertCommentOnDocument(AtomicHTMLToken*);
     void insertCommentOnHTMLHtmlElement(AtomicHTMLToken*);
     void insertHTMLElement(AtomicHTMLToken*);
     void insertSelfClosingHTMLElement(AtomicHTMLToken*);
@@ skipping 98 matching lines @@
     // and a Document in all other cases.
     ContainerNode* m_attachmentRoot;
 
     RefPtr<HTMLStackItem> m_head;
     RefPtr<HTMLFormElement> m_form;
     mutable HTMLElementStack m_openElements;
     mutable HTMLFormattingElementList m_activeFormattingElements;
 
     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);
+        }
+
+        void discard()
+        {
+            PendingText discardedText;
+            swap(discardedText);
+        }
+
+        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;
 
     // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-intable
     // In the "in table" insertion mode, we sometimes get into a state where
     // "whenever a node would be inserted into the current node, it must instead
     // be foster parented."  This flag tracks whether we're in that state.
     bool m_redirectAttachToFosterParent;
 
     bool m_inQuirksMode;
 };
 
 } // namespace WebCore
 
 #endif