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(bool force)
 {
     if (m_pendingText.isEmpty())
         return;
 
+    if (!force && !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(true);
     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 399 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(true);

[eseidel, 2014/08/23 19:39:59]

We'll need to fix this to be an enum (bools make for unreadable callsites), and
I'll need to think harder about this patch on monday.  But I'm certainly open to
the idea. :)

[eustas, 2014/08/26 08:12:25]

Added enum.

Now codesearch is working again. I've found that some execution paths require
mandatory flush. I've added flush mode to ::flush itself and updated
HTMLTreeBuilder.

     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);
 }
 
 
 }