Changeset 53790 in webkit


Ignore:
Timestamp:
Jan 24, 2010 8:11:38 PM (14 years ago)
Author:
mjs@apple.com
Message:

2010-01-24 Maciej Stachowiak <mjs@apple.com>

Reviewed by Dan Bernstein.

Content with heavily nested residual style is so slow, it seems like a hang
https://bugs.webkit.org/show_bug.cgi?id=34059
<rdar://problem/7292906>


Test cast: fast/parser/residual-style-hang.html

  • html/HTMLParser.cpp: (WebCore::HTMLParser::handleResidualStyleCloseTagAcrossBlocks): Limit the number of iterations of the main loop to 5.


The reason this limit is necessary is that otherwise, N misnested open tags followed
by N misnested close tags will cause O(N2) of work due to cloning and attaching subtrees;
at a fixed limit, the cost is at worst O(N).


The code that was in the loop originally ran exactly once - the loop was added in
r21472 to fix <https://bugs.webkit.org/show_bug.cgi?id=13603>. I have verified that
with the iteration limit, the bug is still fixed, both with the original test case
and with the layout tests tht were added.

2010-01-24 Maciej Stachowiak <mjs@apple.com>

Reviewed by Dan Bernstein.

Content with heavily nested residual style is so slow, it seems like a hang
https://bugs.webkit.org/show_bug.cgi?id=34059
<rdar://problem/7292906>

Test case for the above bug fix.

  • fast/parser/residual-style-hang-expected.txt: Added.
  • fast/parser/residual-style-hang.html: Added.
Location:
trunk
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/LayoutTests/ChangeLog

    r53788 r53790  
     12010-01-24  Maciej Stachowiak  <mjs@apple.com>
     2
     3        Reviewed by Dan Bernstein.
     4
     5        Content with heavily nested residual style is so slow, it seems like a hang
     6        https://bugs.webkit.org/show_bug.cgi?id=34059
     7        <rdar://problem/7292906>
     8
     9        Test case for the above bug fix.
     10
     11        * fast/parser/residual-style-hang-expected.txt: Added.
     12        * fast/parser/residual-style-hang.html: Added.
     13
    1142010-01-24  Kent Tamura  <tkent@chromium.org>
    215
  • trunk/WebCore/ChangeLog

    r53787 r53790  
     12010-01-24  Maciej Stachowiak  <mjs@apple.com>
     2
     3        Reviewed by Dan Bernstein.
     4
     5        Content with heavily nested residual style is so slow, it seems like a hang
     6        https://bugs.webkit.org/show_bug.cgi?id=34059
     7        <rdar://problem/7292906>
     8       
     9        Test cast: fast/parser/residual-style-hang.html
     10
     11        * html/HTMLParser.cpp:
     12        (WebCore::HTMLParser::handleResidualStyleCloseTagAcrossBlocks):
     13        Limit the number of iterations of the main loop to 5.
     14       
     15        The reason this limit is necessary is that otherwise, N misnested open tags followed
     16        by N misnested close tags will cause O(N^2) of work due to cloning and attaching subtrees;
     17        at a fixed limit, the cost is at worst O(N).
     18       
     19        The code that was in the loop originally ran exactly once - the loop was added in
     20        r21472 to fix <https://bugs.webkit.org/show_bug.cgi?id=13603>. I have verified that
     21        with the iteration limit, the bug is still fixed, both with the original test case
     22        and with the layout tests tht were added.
     23
    1242010-01-24  Kent Tamura  <tkent@chromium.org>
    225
  • trunk/WebCore/html/HTMLParser.cpp

    r53659 r53790  
    6666static const unsigned cMaxRedundantTagDepth = 20;
    6767static const unsigned cResidualStyleMaxDepth = 200;
     68static const unsigned cResidualStyleIterationLimit = 5;
     69
    6870
    6971static const int minBlockLevelTagPriority = 3;
     
    11291131    bool strayTableContent = elem->strayTableContent;
    11301132
     1133    unsigned iterationCount = 0;
     1134
    11311135    m_handlingResidualStyleAcrossBlocks = true;
    1132     while (!finished) {
     1136    while (!finished && (iterationCount++ < cResidualStyleIterationLimit)) {
    11331137        // Find the outermost element that crosses over to a higher level. If there exists another higher-level
    11341138        // element, we will do another pass, until we have corrected the innermost one.
Note: See TracChangeset for help on using the changeset viewer.