HTMLConstructionSite: avoid n^2 running time for large scripts.

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 213 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()
+void HTMLConstructionSite::flushPendingText(FlushMode mode)
 {
     if (m_pendingText.isEmpty())
         return;
 
+    if (mode == FlushIfAtTextLimit
+        && !shouldUseLengthLimit(*m_pendingText.parent))
+        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);
 
     unsigned currentPosition = 0;
@@ skipping 13 matching lines @@
 
         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();
+    flushPendingText(FlushAlways);
     ASSERT(m_pendingText.isEmpty());
     m_taskQueue.append(task);
 }
 
 void HTMLConstructionSite::attachLater(ContainerNode* parent, PassRefPtrWillBeRawPtr<Node> prpChild, bool selfClosing)
 {
     ASSERT(scriptingContentIsAllowed(m_parserContentPolicy) || !prpChild.get()->isElementNode() || !toScriptLoaderIfPossible(toElement(prpChild.get())));
     ASSERT(pluginContentIsAllowed(m_parserContentPolicy) || !isHTMLPlugInElement(prpChild));
 
     HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert);
@@ skipping 243 matching lines @@
         return;
     }
 
     // Otherwise we are No Quirks Mode.
     setCompatibilityMode(Document::NoQuirksMode);
 }
 
 void HTMLConstructionSite::processEndOfFile()
 {
     ASSERT(currentNode());
-    flush();
+    flush(FlushAlways);
     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();
+    flush(FlushAlways);
     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());
     RefPtrWillBeRawPtr<DocumentType> doctype = DocumentType::create(m_document, token->name(), publicId, systemId);
@@ skipping 127 matching lines @@
         findFosterSite(dummyTask);
 
     // FIXME: This probably doesn't need to be done both here and in insert(Task).
     if (isHTMLTemplateElement(*dummyTask.parent))
         dummyTask.parent = toHTMLTemplateElement(dummyTask.parent.get())->content();
 
     // 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();
+        flushPendingText(FlushAlways);
     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 168 matching lines @@
 }
 
 void HTMLConstructionSite::PendingText::trace(Visitor* visitor)
 {
     visitor->trace(parent);
     visitor->trace(nextChild);
 }
 
 
 }