https://bugs.webkit.org/show_bug.cgi?id=110786

Reviewed by Darin Adler.

Source/WebCore:

// This takes 216 msec.
for (var i = 0; i < 1500; ++i) {
  document.body.appendChild(document.createTextNode('x'));
  document.body.appendChild(document.createElement('div'));
  document.body.appendChild(document.createTextNode('x'));
}

// But this takes 25.3 seconds.
for (var i = 0; i < 1500; ++i) {
  document.body.appendChild(document.createTextNode(' '));
  document.body.appendChild(document.createElement('div'));
  document.body.appendChild(document.createTextNode(' '));
}

The reason is that we do not create renderers for empty text
nodes and thus we are hitting the worst O(N^2) case in Node::attach().
(See FIXME in Node::attach().)

This patch adds a logic to bail out the loop to avoid the O(N^2) case.
Specifically, the patch bails out the loop if we encounter a text node
for which we again decided not to create a renderer. This bail out is
reasonable because the fact that we again decided not to create a renderer
for the text node indicates that there will be no affect of the result
of Text::textRendererIsNeeded() of the rest of the sibling nodes.

Performance test: https://bugs.webkit.org/attachment.cgi?id=190545
Performance result in Chromium/Linux: 25.3 sec => 48 msec !

Test: perf/append-text-nodes-without-renderers.html (for performance)
      fast/dynamic/create-renderer-for-whitespace-only-text.html (for correctness)

The loop was introduced in r29054. We have to make sure that
all layout tests that were updated in r29054 pass with this patch.
See http://trac.webkit.org/changeset/29054.

* dom/Node.cpp:
(WebCore::Node::attach):

LayoutTests:

* fast/html/details-nested-2-expected.txt: Sometimes anonymous blocks are left without
being cleaned up (for some reason). With this patch, one anonymouse block is removed at
the clean-up phase (for some reason). Anyway the new behavior is an expected behavior.
* platform/chromium-mac/fast/html/details-nested-2-expected.txt: Ditto.
* platform/chromium-win/fast/html/details-nested-2-expected.txt: Ditto.
* platform/efl/fast/html/details-nested-2-expected.txt: Ditto.
* platform/mac/fast/html/details-nested-2-expected.txt: Ditto.
* platform/qt/fast/html/details-nested-2-expected.txt: Ditto.
* perf/append-text-nodes-without-renderers-expected.txt: Added. For performance test.
* perf/append-text-nodes-without-renderers.html: Added. Ditto.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@144526 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=97825

Reviewed by Ryosuke Niwa.

Source/WebCore:

Adds a DocumentOrderedMap to TreeScope that allows accessibility to
quickly map from an id to the label for that id. This speeds up
AccessibilityNode::labelForElement, which was a bottleneck in Chromium
when accessibility was on.

Tests: accessibility/title-ui-element-correctness.html
       perf/accessibility-title-ui-element.html

* accessibility/AccessibilityNodeObject.cpp:
(WebCore::AccessibilityNodeObject::labelForElement):
* dom/DocumentOrderedMap.cpp:
(WebCore::keyMatchesLabelForAttribute):
(WebCore):
(WebCore::DocumentOrderedMap::get):
(WebCore::DocumentOrderedMap::getElementByLabelForAttribute):
* dom/DocumentOrderedMap.h:
(DocumentOrderedMap):
* dom/Element.cpp:
(WebCore::Element::insertedInto):
(WebCore::Element::removedFrom):
(WebCore::Element::updateLabel):
(WebCore):
(WebCore::Element::willModifyAttribute):
* dom/Element.h:
(Element):
* dom/TreeScope.cpp:
(WebCore::TreeScope::TreeScope):
(WebCore::TreeScope::destroyTreeScopeData):
(WebCore::TreeScope::addLabel):
(WebCore):
(WebCore::TreeScope::removeLabel):
(WebCore::TreeScope::labelElementForId):
* dom/TreeScope.h:
(WebCore):
(TreeScope):
(WebCore::TreeScope::shouldCacheLabelsByForAttribute):

Tools:

Implement titleUIElement in the chromium port of DRT, and
fix getAccessibleElementById so that it ensures the backing store
is up-to-date.

* DumpRenderTree/chromium/TestRunner/AccessibilityControllerChromium.cpp:
(AccessibilityController::getAccessibleElementById):
* DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:
(AccessibilityUIElement::titleUIElementCallback):

LayoutTests:

Adds two new tests for titleUIElement that run on both Mac and
Chromium. One tests correctness, the other tests speed.

Fixes one test so that it passes on Chromium.
Enables other tests that now pass on Chromium.

* accessibility/secure-textfield-title-ui.html:
* accessibility/title-ui-element-correctness-expected.txt: Added.
* accessibility/title-ui-element-correctness.html: Added.
* perf/accessibility-title-ui-element-expected.txt: Added.
* perf/accessibility-title-ui-element.html: Added.
* platform/chromium/TestExpectations:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@131871 268f45cc-cd09-0410-ab3c-d52691b4dbfc

http://trac.webkit.org/changeset/131107
https://bugs.webkit.org/show_bug.cgi?id=99126

Causes an ASSERT (Requested by abarth|gardening on #webkit).

Patch by Sheriff Bot <webkit.review.bot@gmail.com> on 2012-10-11

Source/WebCore:

* accessibility/AccessibilityNodeObject.cpp:
(WebCore::AccessibilityNodeObject::labelForElement):
* dom/DocumentOrderedMap.cpp:
* dom/DocumentOrderedMap.h:
(DocumentOrderedMap):
* dom/Element.cpp:
(WebCore::Element::insertedInto):
(WebCore::Element::removedFrom):
(WebCore):
(WebCore::Element::willModifyAttribute):
* dom/Element.h:
(Element):
* dom/TreeScope.cpp:
(WebCore::TreeScope::TreeScope):
* dom/TreeScope.h:
(WebCore):
(TreeScope):

Tools:

* DumpRenderTree/chromium/TestRunner/AccessibilityControllerChromium.cpp:
(AccessibilityController::getAccessibleElementById):
* DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:
(AccessibilityUIElement::titleUIElementCallback):

LayoutTests:

* accessibility/secure-textfield-title-ui.html:
* accessibility/title-ui-element-correctness-expected.txt: Removed.
* accessibility/title-ui-element-correctness.html: Removed.
* perf/accessibility-title-ui-element-expected.txt: Removed.
* perf/accessibility-title-ui-element.html: Removed.
* platform/chromium/TestExpectations:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@131124 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=97825

Reviewed by Ryosuke Niwa.

Source/WebCore:

Adds a DocumentOrderedMap to TreeScope that allows accessibility to
quickly map from an id to the label for that id. This speeds up
AccessibilityNode::labelForElement, which was a bottleneck in Chromium
when accessibility was on.

Tests: accessibility/title-ui-element-correctness.html
       perf/accessibility-title-ui-element.html

* accessibility/AccessibilityNodeObject.cpp:
(WebCore::AccessibilityNodeObject::labelForElement):
* dom/DocumentOrderedMap.cpp:
(WebCore::keyMatchesLabelForAttribute):
(WebCore):
(WebCore::DocumentOrderedMap::getElementByLabelForAttribute):
* dom/DocumentOrderedMap.h:
(DocumentOrderedMap):
* dom/Element.cpp:
(WebCore::Element::insertedInto):
(WebCore::Element::removedFrom):
(WebCore::Element::updateLabel):
(WebCore):
(WebCore::Element::willModifyAttribute):
* dom/Element.h:
(Element):
* dom/TreeScope.cpp:
(WebCore::TreeScope::TreeScope):
(WebCore::TreeScope::addLabel):
(WebCore):
(WebCore::TreeScope::removeLabel):
(WebCore::TreeScope::labelElementForId):
* dom/TreeScope.h:
(WebCore):
(TreeScope):
(WebCore::TreeScope::shouldCacheLabelsByForAttribute):

Tools:

Implement titleUIElement in the chromium port of DRT, and
fix getAccessibleElementById so that it ensures the backing store
is up-to-date.

* DumpRenderTree/chromium/TestRunner/AccessibilityControllerChromium.cpp:
(AccessibilityController::getAccessibleElementById):
* DumpRenderTree/chromium/TestRunner/AccessibilityUIElementChromium.cpp:
(AccessibilityUIElement::titleUIElementCallback):

LayoutTests:

Adds two new tests for titleUIElement that run on both Mac and
Chromium. One tests correctness, the other tests speed.

Fixes one test so that it passes on Chromium.
Enables other tests that now pass on Chromium.

* accessibility/secure-textfield-title-ui.html:
* accessibility/title-ui-element-correctness-expected.txt: Added.
* accessibility/title-ui-element-correctness.html: Added.
* perf/accessibility-title-ui-element-expected.txt: Added.
* perf/accessibility-title-ui-element.html: Added.
* platform/chromium/TestExpectations:


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@131107 268f45cc-cd09-0410-ab3c-d52691b4dbfc

* perf/adding-radio-buttons-expected.txt:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@130528 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=98305

Reviewed by Ryosuke Niwa.

-Remove the chromium.Interval stuff. This API no longer exists.
-Reduce the number of iterations to 8.
-Start magnitude at 1 instead of 0.
-Remove all the iterationsPerRun junk. This complexity was not achieving the goal of
reducing flakiness.

With these changes, the perf tests are not flaky for me locally.
I ran all the perf tests with --iterations=100 and had no failures,
All the complexity was increasing flakiness.

This also reduces the runtime of the tests by >2x.

* perf/adding-radio-buttons.html:
This test is clearly linear. It should never have been marked constant.
The patch that landed it was fixing an n^2 behavior.

* perf/array-binary-search.html:
Search for the first item in the array so that the search is always actually log n.

* perf/nested-combined-selectors.html:
Now that we run fewer iterations, we don't need to artificially limit this test.

* resources/magnitude-perf.js:
(Magnitude.run):
(Magnitude._run):
(Magnitude._rSquared):
(Magnitude._logIterationInfo):
(Magnitude._bigOGuess):
(Magnitude._runIteration):
(Magnitude):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@130337 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=94048

Reviewed by Nikolas Zimmermann.

Paths in SVG can be specified with a String (with the d attribute) or
with an SVGPathSegList. In SVGPathElement a single representation is
maintained: an SVGPathByteStream. To keep the byte stream synchronized with
the d attribute and the PathSegList, this byte stream is
rebuilt on every operation. As a result, any modification to the
path is an O(n) operation.

This patch takes advantage of the stream aspect of SVGPathByteStream
to make SVGPathSegList.append an O(1) operation instead of O(n).
When an SVGPathSeg is appended to an SVGPathSegList, this patch parses
the SVGPathSeg and directly appends the resulting bytes to the
byte stream.

To achieve this some plumbing has been added to pass more information
about the actual path changes from the SVGPathSegListTearOff to the
SVGPathElement: instead of the generic commitChange() this patch adds
commitChange(ListModification type). If we decide to change our
internal path data structure in the future, this additional commitChange
function can be used to pass the information needed to make
SVGPathSegList synchronization faster.

SVG Path Benchmark (http://bl.ocks.org/1296930) showing just the
appendItem() time used in building a 5000 segment path (avg of 3 runs):
WebKit without patch: 562 ms
Firefox 18.01a:       55 ms
Opera 12.50 internal: 27 ms
WebKit with patch:    7 ms

Test: perf/svg-path-appenditem.html

    This test proves the claim: SVGPathSegList.appendItem is now O(1).
    Additional tests that appendItem works are covered with existing tests.

* svg/SVGPathByteStream.h:
(WebCore::SVGPathByteStream::append):

    This additional append method allows an SVGPathByteStream to be
    appended to another.

* svg/SVGPathElement.cpp:
(WebCore::SVGPathElement::pathSegListChanged):

    By passing the extra ListModification type to pathSegListChanged,
    SVGPathElement is now able to only synchronize the parts of the byte stream
    that actually changed. In this patch only append is treated
    differently but one can imagine other performance improvements this
    additional information allows.

* svg/SVGPathElement.h:
(SVGPathElement):
* svg/SVGPathParser.cpp:
(WebCore::SVGPathParser::parsePathDataFromSource):

    During normal SVGPathSegList parsing we enforce that the path start with a moveto
    command. This function has been expanded to make that optional so that parsing
    can be performed elsewhere in the path (e.g., in the middle).

* svg/SVGPathParser.h:
(SVGPathParser):
* svg/SVGPathSegList.cpp:
(WebCore::SVGPathSegList::commitChange):
* svg/SVGPathSegList.h:
(SVGPathSegList):
* svg/SVGPathSegWithContext.h:
(WebCore::SVGPathSegWithContext::commitChange):
* svg/SVGPathUtilities.cpp:
(WebCore::appendSVGPathByteStreamFromSVGPathSeg):

    This function reuses the SVGPathSegList parsing infrastructure
    to parse an SVGPathSegList with just the single SVGPathSeg that
    is being appended. The resulting byte stream can then be appended
    to the result path byte stream.

(WebCore):
* svg/SVGPathUtilities.h:
(WebCore):
* svg/properties/SVGListProperty.h:
(WebCore::SVGListProperty::appendItemValues):
(WebCore::SVGListProperty::appendItemValuesAndWrappers):
(WebCore::SVGListProperty::commitChange):
(SVGListProperty):
* svg/properties/SVGPathSegListPropertyTearOff.h:
(WebCore::SVGPathSegListPropertyTearOff::commitChange):
(SVGPathSegListPropertyTearOff):

LayoutTests: Make SVGPathSegList.append O(1) instead of O(n)
https://bugs.webkit.org/show_bug.cgi?id=94048

Reviewed by Nikolas Zimmermann.

Add performance test to prove this patch works. The rest of SVGPathSegList.append should be covered
in existing tests.

* perf/svg-path-appenditem-expected.txt: Added.
* perf/svg-path-appenditem.html: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@128729 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=91320

Reviewed by Ojan Vafai.

Source/WebCore: 

Traverse nodes from the last item when the target offset we're looking for is closer to the last item
than to the cached item. e.g. if the cached item was at offset 0 in the collection and length was 100,
we should not be looking for the item at offset 95 from the cached item.

Note that this trick can be only used in HTML collection that supports itemBefore and when the length
cache is available.

Also broke shouldSearchFromFirstItem into smaller logical pieces to clarify the intents.

Test: perf/htmlcollection-last-item.html

* html/HTMLCollection.cpp:
(WebCore):
(WebCore::HTMLCollection::isLastItemCloserThanLastOrCachedItem):
(WebCore::HTMLCollection::isFirstItemCloserThanCachedItem):
(WebCore::HTMLCollection::item):
* html/HTMLCollection.h:
(HTMLCollection):

LayoutTests: 

Added an asymptotic time complexity test.

* perf/htmlcollection-last-item-expected.txt: Added.
* perf/htmlcollection-last-item.html: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@122672 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=91306

Reviewed by Anders Carlsson.

Source/WebCore: 

Fixed the bug by introducing itemBefore that iterates nodes backwards to complement itemAfter.
Unfortunately, some HTML collections such as HTMLFormCollection and HTMLTableRowsCollection have
its own itemAfter function and writing an equivalent itemBefore is somewhat tricky. For now,
added a new boolean flag indicating whether a given HTML collection supports itemBefore or not,
and left those HTML collections that override itemAfter alone.

This also paves our way to share more code between DynamicNodeList and HTMLCollection.

Test: perf/htmlcollection-backwards-iteration.html

* dom/DynamicNodeList.h:
(WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes ItemBeforeSupportType.
(WebCore::DynamicNodeListCacheBase::supportsItemBefore): Added.
(DynamicNodeListCacheBase):
(WebCore::DynamicNodeListCacheBase::setItemCache): Replaced a FIXME by an assertion now that
we can.
* html/HTMLAllCollection.cpp:
(WebCore::HTMLAllCollection::HTMLAllCollection): Supports itemBefore since it doesn't override
itemAfter.
* html/HTMLCollection.cpp:
(WebCore::HTMLCollection::HTMLCollection):
(WebCore::HTMLCollection::create):
(WebCore::isAcceptableElement): Made it a static local function instead of a static member.
(WebCore::nextNode): Templatized.
(WebCore::itemBeforeOrAfter): Extracted from itemAfter and templatized.
(WebCore::HTMLCollection::itemBefore): Added.
(WebCore::HTMLCollection::itemAfter):
(WebCore::HTMLCollection::shouldSearchFromFirstItem): Added. Determines whether we should reset
the item cache to the first item. We obviously do if the cache is invalid. If the target offset
is after the cached offset, then we shouldn't go back regardless of availability of itemBefore.
Otherwise, we go back to the first item iff itemBefore is not available or the distance from
the cached offset to the target offset is greater than the target offset itself.
(WebCore::HTMLCollection::length):
(WebCore::HTMLCollection::item): Use the term "offset" to match the terminology elsewhere.
(WebCore::HTMLCollection::itemBeforeOrAfterCachedItem): Ditto. Also added the logic to iterate
nodes backwards using itemBefore. Once we're in this branch, we should always find a matching
item since the target offset was less than the cached offset, and offsets are non-negative.
If we had ever reached the end of the loop without finding an item, it indicates that the cache
has been invalid and we have some serious bug elsewhere.
* html/HTMLCollection.h:
(WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
(HTMLCollection):
* html/HTMLOptionsCollection.cpp:
(WebCore::HTMLOptionsCollection::HTMLOptionsCollection): Supports itemBefore since it doesn't
override itemAfter.
* html/HTMLFormCollection.cpp:
(WebCore::HTMLFormCollection::HTMLFormCollection): Doesn't support itemBefore as it overrides
itemAfter.
* html/HTMLNameCollection.cpp:
(WebCore::HTMLNameCollection::HTMLNameCollection): Ditto.
* html/HTMLPropertiesCollection.cpp:
(WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
* html/HTMLTableRowsCollection.cpp:
(WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):

LayoutTests: 

Add an asymptotic time complexity test.

* perf/htmlcollection-backwards-iteration-expected.txt: Added.
* perf/htmlcollection-backwards-iteration.html: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@122660 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Use testRunner instead of layoutTestController in networkinformation, perf, plugins, pointer-lock, printing, scrollbars, and security tests
https://bugs.webkit.org/show_bug.cgi?id=89181

Reviewed by Kent Tamura.

* perf/clone-with-focus.html:
* perf/nested-combined-selectors.html:
* perf/table-rows-length-caching.html:
* platform/chromium/plugins/call-as-function.html:
* platform/chromium/plugins/get-url-with-blank-target2.html:
* platform/chromium/plugins/get-url-with-iframe-target-no-crash.html:
* platform/chromium/printing/custom-page-size-style-expected.txt:
* platform/chromium/printing/custom-page-size-style.html:
* platform/gtk/plugins/invalidate-rect-with-null-npp-argument.html:
* platform/gtk/scrollbars/overflow-scrollbar-horizontal-wheel-scroll.html:
* platform/mac-wk2/plugins/contents-scale-factor.html:
* platform/mac-wk2/plugins/mouse-events-scaled.html:
* platform/mac/plugins/bindings-array-apply-crash.html:
* platform/mac/plugins/bindings-objc-long-method-name.html:
* platform/mac/plugins/bindings-objc-method-name-conversion.html:
* platform/mac/plugins/bindings-test-objc.html:
* platform/mac/plugins/call-as-function-test.html:
* platform/mac/plugins/convert-point.html:
* platform/mac/plugins/disable-plugins.html:
* platform/mac/plugins/jsobjc-dom-wrappers.html:
* platform/mac/plugins/jsobjc-simple.html:
* platform/mac/plugins/pluginDocumentView-deallocated-dataSource.html-disabled:
* platform/mac/plugins/root-object-premature-delete-crash.html:
* platform/mac/plugins/supports-carbon-event-model.html:
* platform/mac/plugins/testplugin-onnew-onpaint.html:
* platform/mac/plugins/throw-on-dealloc.html:
* platform/mac/plugins/undefined-property-crash.html:
* platform/mac/plugins/update-widget-from-style-recalc.html:
* platform/mac/plugins/webScriptObject-exception-deadlock.html:
* platform/mac/scrollbars/key-window-not-first-responder.html:
* platform/qt/plugins/application-plugin-plugins-disabled.html:
* platform/win/plugins/call-javascript-that-destroys-plugin.html:
* platform/win/plugins/get-value-netscape-window.html:
* platform/win/plugins/iframe-inside-overflow.html:
* platform/win/plugins/npn-invalidate-rect-invalidates-window.html:
* platform/win/plugins/visibility-hidden.html:
* platform/win/plugins/window-geometry-initialized-before-set-window.html:
* platform/win/plugins/window-region-is-set-to-clip-rect.html:
* platform/win/plugins/windowless-paint-rect-coordinates.html:
* plugins/:
* pointer-lock/lock-fail-responses-expected.txt:
* pointer-lock/lock-fail-responses.html:
* pointer-lock/pointer-lock-api.html:
* pointer-lock/pointerlockchange-pointerlockerror-events-expected.txt:
* pointer-lock/pointerlockchange-pointerlockerror-events.html:
* pointer-lock/pointerlocklost-event-expected.txt:
* pointer-lock/pointerlocklost-event.html:
* printing/compositing-layer-printing.html:
* printing/css2.1/README.txt:
* printing/css2.1/page-break-after-000.html:
* printing/css2.1/page-break-after-001.html:
* printing/css2.1/page-break-after-002.html:
* printing/css2.1/page-break-after-003.html:
* printing/css2.1/page-break-after-004.html:
* printing/css2.1/page-break-before-000.html:
* printing/css2.1/page-break-before-001.html:
* printing/css2.1/page-break-before-002.html:
* printing/css2.1/page-break-inside-000.html:
* printing/iframe-print.html:
* printing/media-queries-print.html:
* printing/numberOfPages-expected.txt:
* printing/page-count-layout-overflow.html:
* printing/page-count-relayout-shrink.html:
* printing/page-count-with-one-word.html:
* printing/page-format-data-display-none.html:
* printing/page-format-data-expected.txt:
* printing/page-format-data.html:
* printing/page-rule-css-text.html:
* printing/page-rule-in-media-query.html:
* printing/page-rule-selection-expected.txt:
* printing/page-rule-selection.html:
* printing/pageNumerForElementById-expected.txt:
* printing/print-close-crash.html:
* printing/pseudo-class-outside-page.html:
* printing/resources/paged-media-test-utils.js:
(pageNumberForElementShouldBe):
(numberOfPagesShouldBe):
(runPrintingTest):
* printing/return-from-printing-mode.html:
* printing/script-tests/numberOfPages.js:
* printing/script-tests/pageNumerForElementById.js:
* printing/setPrinting.html:
* printing/simultaneous-position-float-change.html:
* printing/single-line-must-not-be-split-into-two-pages.html:
* printing/width-overflow.html:
* printing/zoomed-document.html:
* scrollbars/hidden-iframe-scrollbar-crash.html:
* scrollbars/hidden-iframe-scrollbar-crash2.html:
* scrollbars/hidden-scrollbar-prevents-layout.html:
* scrollbars/overflow-custom-scrollbar-crash.html:
* scrollbars/resources/hidden-iframe-scrollbar-crash2.html:
* scrollbars/scroll-rtl-or-bt-layer.html:
* scrollbars/scrollable-iframe-remove-crash.html:
* scrollbars/scrollbar-click-does-not-blur-content.html:
* scrollbars/scrollbar-crash-on-refresh.html:
* scrollbars/scrollbar-drag-thumb-with-large-content.html:
* scrollbars/scrollbar-gradient-crash.html:
* scrollbars/scrollbar-iframe-click-does-not-blur-content.html:
* scrollbars/scrollbar-initial-position.html:
* scrollbars/scrollbar-middleclick-nopaste.html:
* scrollbars/scrollbar-miss-mousemove-disabled.html:
* scrollbars/scrollbar-miss-mousemove.html:
* scrollbars/scrollbar-owning-renderer-crash.html:
* scrollbars/scrollbar-part-created-with-no-parent-crash.html:
* scrollbars/scrollbar-percent-padding-crash.html:
* scrollbars/scrollbar-scrollbarparts-repaint-crash.html:
* scrollbars/scrollevent-iframe-no-scrolling-wheel.html:
* scrollbars/scrollevent-iframe-no-scrolling.html:
* security/autocomplete-cleared-on-back.html:
* security/block-test-no-port.html:
* security/block-test.html:
* security/set-form-autocomplete-attribute.html:


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@120417 268f45cc-cd09-0410-ab3c-d52691b4dbfc

http://trac.webkit.org/changeset/105885
https://bugs.webkit.org/show_bug.cgi?id=77027

Causes assertions in Position. (Requested by leviw|gardening
on #webkit).

Patch by Sheriff Bot <webkit.review.bot@gmail.com> on 2012-01-25

Source/WebCore: 

* dom/Position.cpp:
(WebCore::Position::upstream):
(WebCore::Position::downstream):
* dom/PositionIterator.cpp:
* dom/PositionIterator.h:
(PositionIterator):
* editing/htmlediting.cpp:
(WebCore::nextCandidate):
(WebCore::nextVisuallyDistinctCandidate):
(WebCore::previousCandidate):
(WebCore::previousVisuallyDistinctCandidate):

LayoutTests: 

* perf/selection-skip-hidden-node-expected.txt: Removed.
* perf/selection-skip-hidden-node.html: Removed.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@105902 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Skip the entire node when it is right to do so, instead of stepping
through every character, so we save CPU time on checking every position
unnecessarily.

Patch by Yong Li <yoli@rim.com> on 2012-01-25
Reviewed by Darin Adler.

Source/WebCore:

Test: perf/selection-skip-hidden-node.html

* dom/Position.cpp:
(WebCore::Position::upstream):
(WebCore::Position::downstream):
* dom/PositionIterator.cpp:
(WebCore::PositionIterator::moveToLeafNodeStart):
(WebCore::PositionIterator::moveToLeafNodeEnd):
* dom/PositionIterator.h:
* editing/htmlediting.cpp:
(WebCore::nextCandidate):
(WebCore::nextVisuallyDistinctCandidate):
(WebCore::previousCandidate):
(WebCore::previousVisuallyDistinctCandidate):

LayoutTests:

* perf/selection-skip-hidden-node-expected.txt: Added.
* perf/selection-skip-hidden-node.html: Added.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@105885 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=74909

Reviewed by Darin Adler.

Source/WebCore:

RadioButtonGroup contains a set of member radio buttons in the group,
and "required" status of the group. This helps implementing correct
radio button validity, and improving performance of updating validity
status of radio buttons.

This change fixes the following bugs:
- A radio button should be "required" if one of a member of the same
  group has the "required" attribute.
  https://bugs.webkit.org/show_bug.cgi?id=76365
- :invalid style is not applied when a checked radio button is removed
  from its radio group
  https://bugs.webkit.org/show_bug.cgi?id=74914
- Loading a page with N radio buttons in a group takes O(N^2) time.

Tests: fast/forms/radio/radio-live-validation-style.html
       perf/adding-radio-buttons.html

* dom/CheckedRadioButtons.cpp:
(WebCore::RadioButtonGroup::isEmpty):
(WebCore::RadioButtonGroup::isRequired):
(WebCore::RadioButtonGroup::checkedButton):
(WebCore::RadioButtonGroup::RadioButtonGroup):
(WebCore::RadioButtonGroup::create):
(WebCore::RadioButtonGroup::isValid):
(WebCore::RadioButtonGroup::setCheckedButton):
(WebCore::RadioButtonGroup::add):
(WebCore::RadioButtonGroup::updateCheckedState):
(WebCore::RadioButtonGroup::requiredAttributeChanged):
(WebCore::RadioButtonGroup::remove):
(WebCore::RadioButtonGroup::setNeedsValidityCheckForAllButtons):
Add RadioButtonGroup class. It keeps track of pointers to member radio
buttons and required status of the group in addition to the checked
radio button pointer.

(WebCore::CheckedRadioButtons::CheckedRadioButtons):
(WebCore::CheckedRadioButtons::~CheckedRadioButtons):
Define empty constructor and destructor in order to avoid exposing
RadioButtonGroup class.

(WebCore::CheckedRadioButtons::addButton):
(WebCore::CheckedRadioButtons::updateCheckedState):
(WebCore::CheckedRadioButtons::requiredAttributeChanged):
(WebCore::CheckedRadioButtons::checkedButtonForGroup):
(WebCore::CheckedRadioButtons::isInRequiredGroup):
(WebCore::CheckedRadioButtons::removeButton):
Change the HashMap member of this class so that it maps a group name to
a RadioButtonGroup object. These functions just get a RadioButtonGroup
object and call a corresponding member function of RadioButtonGroup.

* dom/CheckedRadioButtons.h: Update declarations.

* html/HTMLFormControlElement.cpp:
(WebCore::HTMLFormControlElement::parseMappedAttribute):
(WebCore::HTMLFormControlElement::requiredAttributeChanged):
Move a part of parseMappedAttribute() into requiredAttributeChanged().
* html/HTMLFormControlElement.h: Add requiredAttributeChanged().
* html/HTMLInputElement.cpp:
(WebCore::HTMLInputElement::valueMissing):
Move required check code to InputType::valueMissing implementations.
RadioInputType needs special handling for checking required state.
readOnly() and disabled() are unnecessary because willValidate() checks them.
(WebCore::HTMLInputElement::setChecked):
Call new function CheckedRadioButtons::updateCheckedState() instead of
removeButton() and updateCheckedRadioButtons().
(WebCore::HTMLInputElement::requiredAttributeChanged):
Override this to call CheckedRadioButtons::requiredAttributeChanged().
* html/HTMLInputElement.h: Add requiredAttributeChanged().
* html/RadioInputType.cpp:
(WebCore::RadioInputType::valueMissing):
Check required state by CheckedRadioButtons::isInRequiredGroup().
* html/RadioInputType.h: Remove attach().

* html/CheckboxInputType.cpp:
(WebCore::CheckboxInputType::valueMissing):
  Move required check from HTMLInputElement::valueMissing().
* html/FileInputType.cpp:
(WebCore::FileInputType::valueMissing): ditto.
* html/TextFieldInputType.cpp:
(WebCore::TextFieldInputType::valueMissing): ditto.

LayoutTests:

* fast/forms/radio/radio-live-validation-style-expected.txt: Added.
* fast/forms/radio/radio-live-validation-style.html: Added.

* fast/forms/script-tests/ValidityState-valueMissing-radio.js:
- Update the expectation for the behavior change of
  https://bugs.webkit.org/show_bug.cgi?id=76365
- Add test cases for radio buttons not in a radio button group.
* fast/forms/ValidityState-valueMissing-radio-expected.txt: ditto.

* perf/adding-radio-buttons-expected.txt: Added.
* perf/adding-radio-buttons.html: Added.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@105710 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=75083

Patch by Allan Sandfeld Jensen <allan.jensen@nokia.com> on 2012-01-05
Reviewed by Antti Koivisto.

A sequence of indirect adjencency combinator such as "li ~ li ~ la" could with the
former algorithm potentially do an quadratic number of element matches.
The recursive matching algorithm now detects cases where all siblings have
failed one indirect sibling match and fails the entire selector.

Test: perf/nested-combined-selectors.html

* css/SelectorChecker.cpp:
(WebCore::SelectorChecker::checkSelector): Return SelectorFailsAllSiblings when
all siblings have failed a selector component.
* css/SelectorChecker.h: Add SelectorFailsAllSiblings enum value

LayoutTests:        Test of styling performance of selectors with multiple indirect combinators
       https://bugs.webkit.org/show_bug.cgi?id=75083

       Reviewed by Antti Koivisto.

       * perf/nested-combined-selectors.html: Added.

Patch by Allan Sandfeld Jensen <allan.jensen@nokia.com> on 2012-01-05

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@104133 268f45cc-cd09-0410-ab3c-d52691b4dbfc

REGRESSION (r87351): toggling display of lots (thousands) of elements with display:none is very slow
https://bugs.webkit.org/show_bug.cgi?id=67581

Reviewed by Darin Adler.

Source/WebCore:

Test: perf/show-hide-table-rows.html

* dom/NodeRenderingContext.cpp:
(WebCore::NodeRendererFactory::createRendererAndStyle): Moved style-creating code into createRendererIfNeeded, renamed
    to createRenderer.
(WebCore::NodeRendererFactory::createRendererIfNeeded): Re-arrange code to avoid unnecessary creation of renderers.

LayoutTests:

* perf/show-hide-table-rows-expected.txt: Added.
* perf/show-hide-table-rows.html: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@94938 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=67651

Reviewed by Darin Adler.

This moves the contains method from Element to Node as in the DOM4 working draft:
http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#dom-node-contains

This also special cases Document contains to make it O(1) instead of O(depth).

Source/WebCore:

Tests: fast/dom/Node/contains-method.html
       perf/document-contains.html

* bindings/objc/PublicDOMInterfaces.h: Move contains from DOMElement to DOMNode.
* dom/Element.idl:
* dom/Node.cpp:
(WebCore::Node::contains): Added document special case.
* dom/Node.idl:
* editing/DeleteSelectionCommand.cpp:
(WebCore::DeleteSelectionCommand::mergeParagraphs): Added a null check.

LayoutTests:

* fast/dom/Element/contains-method-expected.txt: Removed.
* fast/dom/Element/script-tests/contains-method.js: Removed.
* fast/dom/Node/contains-method-expected.txt: Added.
* fast/dom/Node/contains-method.html: Renamed from LayoutTests/fast/dom/Element/contains-method.html.
* fast/dom/Node/script-tests/contains-method.js: Added. Expanded tests.
* fast/dom/Window/window-properties-expected.txt:
* perf/document-contains-expected.txt: Added.
* perf/document-contains.html: Added.
                               Perf test to ensure that document.contains is O(1).
* platform/gtk/fast/dom/Window/window-properties-expected.txt:
* platform/mac/fast/dom/Window/window-properties-expected.txt:
* platform/qt-wk2/fast/dom/Window/window-properties-expected.txt:
* platform/qt/fast/dom/Window/window-properties-expected.txt:


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@94898 268f45cc-cd09-0410-ab3c-d52691b4dbfc

http://trac.webkit.org/changeset/94781
https://bugs.webkit.org/show_bug.cgi?id=67806

Broke Objective-C binding on Mac (Requested by rniwa on
#webkit).

Patch by Sheriff Bot <webkit.review.bot@gmail.com> on 2011-09-08

Source/WebCore:

* dom/Element.idl:
* dom/Node.cpp:
(WebCore::Node::contains):
* dom/Node.idl:
* editing/DeleteSelectionCommand.cpp:
(WebCore::DeleteSelectionCommand::mergeParagraphs):

LayoutTests:

* fast/dom/Element/contains-method-expected.txt: Added.
* fast/dom/Element/contains-method.html: Renamed from LayoutTests/fast/dom/Node/contains-method.html.
* fast/dom/Element/script-tests/contains-method.js: Added.
* fast/dom/Node/contains-method-expected.txt: Removed.
* fast/dom/Node/script-tests/contains-method.js: Removed.
* fast/dom/Window/window-properties-expected.txt:
* perf/document-contains-expected.txt: Removed.
* perf/document-contains.html: Removed.
* platform/gtk/fast/dom/Window/window-properties-expected.txt:
* platform/mac/fast/dom/Window/window-properties-expected.txt:
* platform/qt-wk2/fast/dom/Window/window-properties-expected.txt:
* platform/qt/fast/dom/Window/window-properties-expected.txt:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@94805 268f45cc-cd09-0410-ab3c-d52691b4dbfc

https://bugs.webkit.org/show_bug.cgi?id=67651

Reviewed by Darin Adler.

This moves the contains method from Element to Node as in the DOM4 working draft:
http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#dom-node-contains

This also special cases Document contains to make it O(1) instead of O(depth).

Source/WebCore:

Tests: fast/dom/Node/contains-method.html
       perf/document-contains.html

* dom/Element.idl:
* dom/Node.cpp:
(WebCore::Node::contains): Added document special case.
* dom/Node.idl:
* editing/DeleteSelectionCommand.cpp:
(WebCore::DeleteSelectionCommand::mergeParagraphs): Added a null check.

LayoutTests:

* fast/dom/Element/contains-method-expected.txt: Removed.
* fast/dom/Element/script-tests/contains-method.js: Removed.
* fast/dom/Node/contains-method-expected.txt: Added.
* fast/dom/Node/contains-method.html: Renamed from LayoutTests/fast/dom/Element/contains-method.html.
* fast/dom/Node/script-tests/contains-method.js: Added. Expanded tests.
* fast/dom/Window/window-properties-expected.txt:
* perf/document-contains-expected.txt: Added.
* perf/document-contains.html: Added.
                               Perf test to ensure that document.contains is O(1).
* platform/gtk/fast/dom/Window/window-properties-expected.txt:
* platform/mac/fast/dom/Window/window-properties-expected.txt:
* platform/qt-wk2/fast/dom/Window/window-properties-expected.txt:
* platform/qt/fast/dom/Window/window-properties-expected.txt:


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@94781 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Darin Adler.

        HTMLTable should cache its 'rows' collection results
        https://bugs.webkit.org/show_bug.cgi?id=62800

        * perf/table-rows-length-caching-expected.txt: Added.
        * perf/table-rows-length-caching.html: Added.
        This test checks that the call to table.rows is CONSTANT once it has
        been populated once (and the DOM is not mutated).
2011-06-16  Julien Chaffraix  <jchaffraix@webkit.org>

        Reviewed by Darin Adler.

        HTMLTable should cache its 'rows' collection results
        https://bugs.webkit.org/show_bug.cgi?id=62800

        Test: perf/table-rows-length-caching.html

        Currently all our HTMLCollection's are recreated on call. This means that
        we don't cache the information about the collection between calls to, for
        example, table.rows.

        This change adds a CollectionCache to HTMLTableElement. It is similar to what
        is done for HTMLFormElement.

        * html/HTMLTableElement.cpp:
        (WebCore::HTMLTableElement::collectionCache): This method does
        lazy initialization of the table's collectionCache.
        * html/HTMLTableElement.h: Added a new member and the previous
        method.

        * html/HTMLTableRowsCollection.cpp:
        (WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection): Pass
        the HTMLTableElement's CollectionCache so that we reuse the cached
        results.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@89035 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Dimitri Glazkov.

        input field with focus makes appendChild operation ~42x slower
        https://bugs.webkit.org/show_bug.cgi?id=57059

        Add performance test for cloneNode when an input field has focus.

        * perf/clone-with-focus-expected.txt: Added.
        * perf/clone-with-focus.html: Added.
2011-04-15  Emil A Eklund  <eae@chromium.org>

        Reviewed by Dimitri Glazkov.

        input field with focus makes appendChild operation ~42x slower
        https://bugs.webkit.org/show_bug.cgi?id=57059

        Change ContainerNode::cloneChildNodes to only disable the
        deleteButtonController if the container itself (or any of its children)
        is being edited. Thus avoiding a reflow in cases where it's not.

        Test: perf/clone-with-focus.html

        * dom/ContainerNode.cpp:
        (WebCore::ContainerNode::cloneChildNodes):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@84056 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Dimitri Glazkov.

        Relative mouse coordinates recalculated for target
        https://bugs.webkit.org/show_bug.cgi?id=57130

        Add mouse event performance test.

        * fast/events/mouse-relative-position-expected.txt: Added.
        * fast/events/mouse-relative-position.html: Added.
        * perf/mouse-event-expected.txt: Added.
        * perf/mouse-event.html: Added.
2011-03-29  Emil A Eklund  <eae@chromium.org>

        Reviewed by Dimitri Glazkov.

        Relative mouse coordinates recalculated for each target
        https://bugs.webkit.org/show_bug.cgi?id=57130

        Calculate relative coordinates lazily for mouse events instead of doing
        it for each target. Speeds up dispatching of mouse events in deep dom
        structures significantly, O(n^2) to O(n).

        Also fixes https://bugs.webkit.org/show_bug.cgi?id=34973

        Tests: fast/events/mouse-relative-position.html
               perf/mouse-event.html

        * dom/Event.cpp:
        (WebCore::Event::setTarget):
        * dom/MouseRelatedEvent.cpp:
        (WebCore::MouseRelatedEvent::MouseRelatedEvent):
        (WebCore::MouseRelatedEvent::initCoordinates):
        (WebCore::pageZoomFactor):
        (WebCore::MouseRelatedEvent::receivedTarget):
        (WebCore::MouseRelatedEvent::computeRelativePosition):
        (WebCore::MouseRelatedEvent::layerX):
        (WebCore::MouseRelatedEvent::layerY):
        (WebCore::MouseRelatedEvent::offsetX):
        (WebCore::MouseRelatedEvent::offsetY):
        * dom/MouseRelatedEvent.h:
        * dom/UIEvent.cpp:
        (WebCore::UIEvent::layerX):
        (WebCore::UIEvent::layerY):
        * dom/UIEvent.h:
2011-03-29  Emil A Eklund  <eae@chromium.org>

        Reviewed by Dimitri Glazkov.

        Relative mouse coordinates recalculated for each target
        https://bugs.webkit.org/show_bug.cgi?id=57130

        * public/WebDOMMouseEvent.h:
        * src/WebDOMMouseEvent.cpp:
        (WebKit::WebDOMMouseEvent::layerX):
        (WebKit::WebDOMMouseEvent::layerY):
        (WebKit::WebDOMMouseEvent::offsetX):
        (WebKit::WebDOMMouseEvent::offsetY):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@82225 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Dimitri Glazkov.

        Fix for classList perf test, failing due to typo.
        https://bugs.webkit.org/show_bug.cgi?id=50578

        * perf/class-list-remove.html: Changed to use the right value.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@73418 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Ojan Vafai.

        Fix perf/class-list-remove test
        https://bugs.webkit.org/show_bug.cgi?id=46745

        Make sure we precompute the className in the setup functions and that
        we reset it before calling classList.remove.

        * perf/class-list-remove.html:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@68596 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Darin Adler.

        Implement HTML 5's HTMLElement.classList property
        https://bugs.webkit.org/show_bug.cgi?id=20709

        * fast/dom/HTMLElement/class-list-expected.txt: Added.
        * fast/dom/HTMLElement/class-list-gc-expected.txt: Added.
        * fast/dom/HTMLElement/class-list-gc.html: Added.
        * fast/dom/HTMLElement/class-list-quirks-expected.txt: Added.
        * fast/dom/HTMLElement/class-list-quirks.html: Added.
        * fast/dom/HTMLElement/class-list.html: Added.
        * fast/dom/HTMLElement/script-tests/class-list-gc.js: Added.
        (gc):
        * fast/dom/HTMLElement/script-tests/class-list.js: Added.
        (createElement):
        * fast/dom/Window/window-properties-expected.txt:
        * fast/dom/Window/window-property-descriptors-expected.txt:
        * fast/dom/prototype-inheritance-2-expected.txt:
        * fast/dom/prototype-inheritance-expected.txt:
        * fast/js/global-constructors-expected.txt:
        * perf/class-list-remove-expected.txt: Added.
        * perf/class-list-remove.html: Added.
2010-09-27  Erik Arvidsson  <arv@chromium.org>

        Reviewed by Darin Adler.

        Implement HTML 5's HTMLElement.classList property
        https://bugs.webkit.org/show_bug.cgi?id=20709

        This adds a DOMTokenList class that is used for the classList property. DOMTokenList uses a SpaceSplitString for fast
        contains check. In standards mode the existing classNames is used but in quirks mode we use an internal SpaceSplitString
        because classList is always case sensitive.

        Tests: fast/dom/HTMLElement/class-list-gc.html
               fast/dom/HTMLElement/class-list-quirks.html
               fast/dom/HTMLElement/class-list.html
               perf/class-list-remove.html

        * Android.derived.jscbindings.mk:
        * Android.derived.v8bindings.mk:
        * Android.jscbindings.mk:
        * CMakeLists.txt:
        * DerivedSources.cpp:
        * DerivedSources.make:
        * GNUmakefile.am:
        * WebCore.gypi:
        * WebCore.pri:
        * WebCore.pro:
        * WebCore.vcproj/WebCore.vcproj:
        * WebCore.xcodeproj/project.pbxproj:
        * bindings/gobject/GNUmakefile.am:
        * bindings/js/JSElementCustom.cpp:
        (WebCore::JSElement::markChildren): Make sure that we keep the wrapper while the element is alive.
        * bindings/scripts/CodeGeneratorJS.pm: DOMTokenList has a string indexed getter.
        * bindings/scripts/CodeGeneratorV8.pm:
        * bindings/v8/custom/V8DOMTokenListCustom.cpp: Added.
        (WebCore::toV8):
        * dom/Element.cpp:
        (WebCore::Element::classList):
        (WebCore::Element::optionalClassList):
        * dom/Element.h:
        * dom/ElementRareData.h: This now has an OwnPtr to a ClassList if the Element::classList is ever called.
        * dom/SpaceSplitString.h:
        (WebCore::SpaceSplitString::isNull):
        * dom/StyledElement.cpp:
        (WebCore::StyledElement::classAttributeChanged): Update the classList if it exists.
        * dom/StyledElement.h:
        * html/DOMTokenList.cpp: Added.
        (WebCore::validateToken):
        (WebCore::DOMTokenList::DOMTokenList):
        (WebCore::DOMTokenList::ref):
        (WebCore::DOMTokenList::deref):
        (WebCore::DOMTokenList::length):
        (WebCore::DOMTokenList::item):
        (WebCore::DOMTokenList::contains):
        (WebCore::DOMTokenList::containsInternal): The internal methods do no validation of the token.
        (WebCore::DOMTokenList::add):
        (WebCore::DOMTokenList::addInternal):
        (WebCore::DOMTokenList::remove):
        (WebCore::DOMTokenList::removeInternal):
        (WebCore::DOMTokenList::toggle):
        (WebCore::DOMTokenList::toString):
        (WebCore::DOMTokenList::reset):
        (WebCore::DOMTokenList::classNames):
        * html/DOMTokenList.h: Added.
        (WebCore::DOMTokenList::create):
        (WebCore::DOMTokenList::element):
        * html/DOMTokenList.idl: Added.
        * html/HTMLElement.idl:
        * page/DOMWindow.cpp:
        * page/DOMWindow.idl:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@68440 268f45cc-cd09-0410-ab3c-d52691b4dbfc

        Reviewed by Darin Adler.

        add ability to test order-of-magnitude in layout tests
        https://bugs.webkit.org/show_bug.cgi?id=43997

        Uses the R^2 value to determine likelihood the performance
        is linear and then logs the x and y axis appropriately to determine
        log n and n^2 cases. These are all estimates though, so we try
        up to three times if we don't get the correct expected result.

        In practice, with the tests below, we almost always get the correct
        result, but sometimes the O(1) tests get registered as O(n) or indeterminate.

        * perf/array-binary-search-expected.txt: Added.
        * perf/array-binary-search.html: Added.
        * perf/array-nested-loop-expected.txt: Added.
        * perf/array-nested-loop.html: Added.
        * perf/array-push-pop-expected.txt: Added.
        * perf/array-push-pop.html: Added.
        * perf/array-reverse-expected.txt: Added.
        * perf/array-reverse.html: Added.
        * perf/object-keys-expected.txt: Added.
        * perf/object-keys.html: Added.
        * perf/set-attribute-expected.txt: Added.
        * perf/set-attribute.html: Added.
        * perf/typing-at-end-of-line-expected.txt: Added.
        * perf/typing-at-end-of-line.html: Added.
        * resources/magnitude-perf.js: Added.
        (Magnitude.description):
        (Magnitude._log):
        (Magnitude._debug):
        (Magnitude.run):
        (Magnitude._run):
        (Magnitude._rSquared):
        (Magnitude._logIterationInfo):
        (Magnitude._bigOGuess):
        (Magnitude._runIteration):
        (Magnitude):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@65614 268f45cc-cd09-0410-ab3c-d52691b4dbfc