Rewrite Text node attaching to not be N^2

Source/core/html/parser/HTMLConstructionSite.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 101 matching lines @@
     ASSERT(task.operation == HTMLConstructionSiteTask::Insert);
 
     insert(task);
 
     task.child->beginParsingChildren();
 
     if (task.selfClosing)
         task.child->finishParsingChildren();
 }
 
+static inline void executeInsertTextTask(HTMLConstructionSiteTask& task)
+{
+    ASSERT(task.operation == HTMLConstructionSiteTask::InsertText);
+    ASSERT(task.child->isTextNode());
+
+    // Merge text nodes into previous ones if possible:
+    // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#insert-a-character
+    Text* newText = toText(task.child.get());
+    Node* previousChild = task.nextChild ? task.nextChild->previousSibling() : task.parent->lastChild();
+    if (previousChild && previousChild->isTextNode()) {
+        Text* previousText = toText(previousChild);
+        unsigned lengthLimit = textLengthLimitForContainer(task.parent.get());
+        if (previousText->length() + newText->length() < lengthLimit) {
+            previousText->parserAppendData(newText->data());
+            return;
+        }
+    }
+
+    insert(task);
+}
+
 static inline void executeReparentTask(HTMLConstructionSiteTask& task)
 {
     ASSERT(task.operation == HTMLConstructionSiteTask::Reparent);
 
     if (ContainerNode* parent = task.child->parentNode())
         parent->parserRemoveChild(*task.child);
 
     task.parent->parserAppendChild(task.child);
 }
 
@@ skipping 10 matching lines @@
 
     task.parent->parserTakeAllChildrenFrom(*task.oldParent());
 }
 
 void HTMLConstructionSite::executeTask(HTMLConstructionSiteTask& task)
 {
     ASSERT(m_taskQueue.isEmpty());
     if (task.operation == HTMLConstructionSiteTask::Insert)
         return executeInsertTask(task);
 
+    if (task.operation == HTMLConstructionSiteTask::InsertText)
+        return executeInsertTextTask(task);
+
     // All the cases below this point are only used by the adoption agency.
 
     if (task.operation == HTMLConstructionSiteTask::InsertAlreadyParsedChild)
         return executeInsertAlreadyParsedChildTask(task);
 
     if (task.operation == HTMLConstructionSiteTask::Reparent)
         return executeReparentTask(task);
 
     if (task.operation == HTMLConstructionSiteTask::TakeAllChildren)
         return executeTakeAllChildrenTask(task);
 
     ASSERT_NOT_REACHED();
 }
 
 // This is only needed for TextDocuments where we might have text nodes
 // approaching the default length limit (~64k) and we don't want to
 // break a text node in the middle of a combining character.
-static unsigned findBreakIndexBetween(const String& string, unsigned currentPosition, unsigned proposedBreakIndex)
+static unsigned findBreakIndexBetween(const StringBuilder& string, unsigned currentPosition, unsigned proposedBreakIndex)
 {
     ASSERT(currentPosition < proposedBreakIndex);
     ASSERT(proposedBreakIndex <= string.length());
     // The end of the string is always a valid break.
     if (proposedBreakIndex == string.length())
         return proposedBreakIndex;
 
     // Latin-1 does not have breakable boundaries. If we ever moved to a differnet 8-bit encoding this could be wrong.
     if (string.is8Bit())
         return proposedBreakIndex;
@@ skipping 15 matching lines @@
 
 static String atomizeIfAllWhitespace(const String& string, WhitespaceMode whitespaceMode)
 {
     // Strings composed entirely of whitespace are likely to be repeated.
     // Turn them into AtomicString so we share a single string for each.
     if (whitespaceMode == AllWhitespace || (whitespaceMode == WhitespaceUnknown && isAllWhitespace(string)))
         return AtomicString(string).string();
     return string;
 }
 
+void HTMLConstructionSite::flushPendingText()
+{
+    if (m_pendingText.isEmpty())
+        return;
+
+    PendingText pendingText;
+    // Hold onto the current pending text on the stack so that queueTask doesn't recurse infinitely.
+    m_pendingText.swap(pendingText);
+    ASSERT(m_pendingText.isEmpty());
+
+    // Splitting text nodes into smaller chunks contradicts HTML5 spec, but is necessary
+    // for performance, see: https://bugs.webkit.org/show_bug.cgi?id=55898
+    unsigned lengthLimit = textLengthLimitForContainer(pendingText.parent.get());
+
+    unsigned currentPosition = 0;
+    const StringBuilder& string = pendingText.stringBuilder;
+    while (currentPosition < string.length()) {
+        unsigned proposedBreakIndex = std::min(currentPosition + lengthLimit, string.length());
+        unsigned breakIndex = findBreakIndexBetween(string, currentPosition, proposedBreakIndex);
+        ASSERT(breakIndex <= string.length());
+        String substring = string.substring(currentPosition, breakIndex - currentPosition);
+        substring = atomizeIfAllWhitespace(substring, pendingText.whitespaceMode);
+
+        HTMLConstructionSiteTask task(HTMLConstructionSiteTask::InsertText);
+        task.parent = pendingText.parent;
+        task.nextChild = pendingText.nextChild;
+        task.child = Text::create(task.parent->document(), substring);
+        queueTask(task);
+
+        ASSERT(breakIndex > currentPosition);
+        ASSERT(breakIndex - currentPosition == substring.length());
+        ASSERT(toText(task.child.get())->length() == substring.length());
+        currentPosition = breakIndex;
+    }
+}
+
 void HTMLConstructionSite::queueTask(const HTMLConstructionSiteTask& task)
 {
+    flushPendingText();
+    ASSERT(m_pendingText.isEmpty());
     m_taskQueue.append(task);
 }
 
 void HTMLConstructionSite::attachLater(ContainerNode* parent, PassRefPtr<Node> prpChild, bool selfClosing)
 {
     ASSERT(scriptingContentIsAllowed(m_parserContentPolicy) || !prpChild.get()->isElementNode() || !toScriptLoaderIfPossible(toElement(prpChild.get())));
     ASSERT(pluginContentIsAllowed(m_parserContentPolicy) || !prpChild->isPluginElement());
 
     HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert);
     task.parent = parent;
     task.child = prpChild;
     task.selfClosing = selfClosing;
 
     if (shouldFosterParent()) {
         fosterParent(task.child);
         return;
     }
 
     // Add as a sibling of the parent if we have reached the maximum depth allowed.
     if (m_openElements.stackDepth() > maximumHTMLParserDOMTreeDepth && task.parent->parentNode())
         task.parent = task.parent->parentNode();
 
     ASSERT(task.parent);
     queueTask(task);
 }
 
 void HTMLConstructionSite::executeQueuedTasks()
 {
+    // This has no affect on pendingText, and we may have pendingText
+    // remaining after executing all other queued tasks.
     const size_t size = m_taskQueue.size();
     if (!size)
         return;
 
     // Copy the task queue into a local variable in case executeTask
     // re-enters the parser.
     TaskQueue queue;
     queue.swap(m_taskQueue);
 
     for (size_t i = 0; i < size; ++i)
@@ skipping 22 matching lines @@
     , m_inQuirksMode(fragment->document().inQuirksMode())
 {
     ASSERT(m_document->isHTMLDocument() || m_document->isXHTMLDocument());
 }
 
 HTMLConstructionSite::~HTMLConstructionSite()
 {
     // Depending on why we're being destroyed it might be OK
     // to forget queued tasks, but currently we don't expect to.
     ASSERT(m_taskQueue.isEmpty());
+    // Currently we assume that text will never be the last token in the
+    // document and that we'll always queue some additional task to cause it to flush.
+    ASSERT(m_pendingText.isEmpty());
 }
 
 void HTMLConstructionSite::detach()
 {
+    // FIXME: We'd like to ASSERT here that we're canceling and not just discarding
+    // text that really should have made it into the DOM earlier, but there
+    // doesn't seem to be a nice way to do that.
+    m_pendingText.discard();
     m_document = 0;
     m_attachmentRoot = 0;
 }
 
 void HTMLConstructionSite::setForm(HTMLFormElement* form)
 {
     // This method should only be needed for HTMLTreeBuilder in the fragment case.
     ASSERT(!m_form);
     m_form = form;
 }
@@ skipping 149 matching lines @@
         return;
     }
 
     // Otherwise we are No Quirks Mode.
     setCompatibilityMode(Document::NoQuirksMode);
 }
 
 void HTMLConstructionSite::processEndOfFile()
 {
     ASSERT(currentNode());
+    flush();
     openElements()->popAll();
 }
 
 void HTMLConstructionSite::finishedParsing()
 {
+    // We shouldn't have any queued tasks but we might have pending text which we need to promote to tasks and execute.
     ASSERT(m_taskQueue.isEmpty());
+    flush();
     m_document->finishedParsing();
 }
 
 void HTMLConstructionSite::insertDoctype(AtomicHTMLToken* token)
 {
     ASSERT(token->type() == HTMLToken::DOCTYPE);
 
     const String& publicId = StringImpl::create8BitIfPossible(token->publicIdentifier());
     const String& systemId = StringImpl::create8BitIfPossible(token->systemIdentifier());
     RefPtr<DocumentType> doctype = DocumentType::create(m_document, token->name(), publicId, systemId);
@@ skipping 113 matching lines @@
 
     RefPtr<Element> element = createElement(token, namespaceURI);
     if (scriptingContentIsAllowed(m_parserContentPolicy) || !toScriptLoaderIfPossible(element.get()))
         attachLater(currentNode(), element, token->selfClosing());
     if (!token->selfClosing())
         m_openElements.push(HTMLStackItem::create(element.release(), token, namespaceURI));
 }
 
 void HTMLConstructionSite::insertTextNode(const String& string, WhitespaceMode whitespaceMode)
 {
-    HTMLConstructionSiteTask protoTask(HTMLConstructionSiteTask::Insert);
-    protoTask.parent = currentNode();
+    HTMLConstructionSiteTask dummyTask(HTMLConstructionSiteTask::Insert);
+    dummyTask.parent = currentNode();
 
     if (shouldFosterParent())
-        findFosterSite(protoTask);
+        findFosterSite(dummyTask);
 
     // FIXME: This probably doesn't need to be done both here and in insert(Task).
-    if (protoTask.parent->hasTagName(templateTag))
-        protoTask.parent = toHTMLTemplateElement(protoTask.parent.get())->content();
+    if (dummyTask.parent->hasTagName(templateTag))
+        dummyTask.parent = toHTMLTemplateElement(dummyTask.parent.get())->content();
 
-    // Splitting text nodes into smaller chunks contradicts HTML5 spec, but is necessary
-    // for performance, see: https://bugs.webkit.org/show_bug.cgi?id=55898
-    unsigned lengthLimit = textLengthLimitForContainer(protoTask.parent.get());
-    unsigned currentPosition = 0;
-
-    // Merge text nodes into previous ones if possible:
-    // http://www.whatwg.org/specs/web-apps/current-work/multipage/tree-construction.html#insert-a-character
-    Node* previousChild = protoTask.nextChild ? protoTask.nextChild->previousSibling() : protoTask.parent->lastChild();
-    if (previousChild && previousChild->isTextNode()) {
-        Text* previousText = toText(previousChild);
-        unsigned appendLengthLimit = lengthLimit - previousText->length();
-
-        unsigned proposedBreakIndex = std::min(currentPosition + appendLengthLimit, string.length());
-        unsigned breakIndex = findBreakIndexBetween(string, currentPosition, proposedBreakIndex);
-        ASSERT(breakIndex <= string.length());
-        // If we didn't find a breable piece to append, forget it.
-        if (breakIndex) {
-            String substring = string.substring(currentPosition, breakIndex - currentPosition);
-            substring = atomizeIfAllWhitespace(substring, whitespaceMode);
-            previousText->parserAppendData(substring);
-            currentPosition += substring.length();
-        }
-    }
-
-    while (currentPosition < string.length()) {
-        unsigned proposedBreakIndex = std::min(currentPosition + lengthLimit, string.length());
-        unsigned breakIndex = findBreakIndexBetween(string, currentPosition, proposedBreakIndex);
-        // We failed to find a breakable boudary between the minimum and the proposed, just give up and break at the proposed index.
-        // We could go searching after the proposed index, but current callers are attempting to break after 65k chars!
-        // 65k of unbreakable characters isn't worth trying to handle "correctly".
-        if (!breakIndex)
-            breakIndex = proposedBreakIndex;
-        ASSERT(breakIndex <= string.length());
-        String substring = string.substring(currentPosition, breakIndex - currentPosition);
-        substring = atomizeIfAllWhitespace(substring, whitespaceMode);
-
-        HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert);
-        task.parent = protoTask.parent;
-        task.nextChild = protoTask.nextChild;
-        task.child = Text::create(task.parent->document(), substring);
-        queueTask(task);
-
-        ASSERT(breakIndex > currentPosition);
-        ASSERT(breakIndex - currentPosition == substring.length());
-        ASSERT(toText(task.child)->length() == substring.length());
-        currentPosition = breakIndex;
-    }
+    // Unclear when parent != case occurs. Somehow we insert text into two separate nodes while processing the same Token.
+    // The nextChild != dummy.nextChild case occurs whenever foster parenting happened and we hit a new text node "<table>a</table>b"
+    // In either case we have to flush the pending text into the task queue before making more.
+    if (!m_pendingText.isEmpty() && (m_pendingText.parent != dummyTask.parent ||  m_pendingText.nextChild != dummyTask.nextChild))
+        flushPendingText();
+    m_pendingText.append(dummyTask.parent, dummyTask.nextChild, string, whitespaceMode);
 }
 
 void HTMLConstructionSite::reparent(HTMLElementStack::ElementRecord* newParent, HTMLElementStack::ElementRecord* child)
 {
     HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Reparent);
     task.parent = newParent->node();
     task.child = child->node();
     queueTask(task);
 }
 
@@ skipping 162 matching lines @@
 void HTMLConstructionSite::fosterParent(PassRefPtr<Node> node)
 {
     HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert);
     findFosterSite(task);
     task.child = node;
     ASSERT(task.parent);
     queueTask(task);
 }
 
 }