Bug 13337 - Safari hangs loading html file with deeply nested tags
Summary: Safari hangs loading html file with deeply nested tags
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 523.x (Safari 3)
Hardware: Macintosh OS X 10.4
: P2 Normal
Assignee: Nobody
Depends on: 13351
  Show dependency treegraph
Reported: 2007-04-11 16:49 PDT by Gavin Sherlock
Modified: 2007-04-23 23:25 PDT (History)
2 users (show)

See Also:

html file demonstrating problem (701.04 KB, text/html)
2007-04-11 16:50 PDT, Gavin Sherlock
no flags Details
nesting test (1.48 KB, text/html)
2007-04-13 12:06 PDT, Geoffrey Garen
no flags Details
nesting test (1.37 KB, text/html)
2007-04-13 12:07 PDT, Geoffrey Garen
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Gavin Sherlock 2007-04-11 16:49:20 PDT
The attached file causes Safari to hang (tested on r20849, but same result on release version) for about a minute, on a quad MacPro.  Scrolling is also jerky after loading.  In Firefox, loading is instant, and scrolling is fine.
Comment 1 Gavin Sherlock 2007-04-11 16:50:00 PDT
Created attachment 14012 [details]
html file demonstrating problem
Comment 2 Gavin Sherlock 2007-04-11 16:52:21 PDT
Forgot to add - when file is open, memory increases by several hundred megabytes.  In contrast, Firefox uses less than 100Mb.
Comment 3 Dave Hyatt 2007-04-11 17:00:38 PDT
This page is extremely malformed and is nesting <span>s to an insane level.  Basically the spans not being closed properly is causing us to nest all the spans inside one another.  I'm not sure how Firefox is avoiding this... maybe by having a maximum allowed document tree depth.
Comment 4 Geoffrey Garen 2007-04-13 12:04:50 PDT
My testing shows that IE nests infinitely (and hangs), while Firefox nests up to 201 (where <html> counts as 0 and <body> counts as 1), parsing all subsequent nested tags as siblings.
Comment 5 Geoffrey Garen 2007-04-13 12:06:01 PDT
Created attachment 14029 [details]
nesting test

Test for how deeply a browser will nest tags, and the resulting DOM.
Comment 6 Geoffrey Garen 2007-04-13 12:07:35 PDT
Created attachment 14030 [details]
nesting test

Fixed test description.
Comment 7 Geoffrey Garen 2007-04-13 12:12:05 PDT
"IE" above means IE 6 and IE 7.
Comment 8 Geoffrey Garen 2007-04-13 14:10:30 PDT
Firefox does not restrict nesting in XML documents, but in HTML documents it restricts nesting in both quirks and standards modes.
Comment 9 Dave Hyatt 2007-04-13 14:47:21 PDT
That makes sense, since these nesting situations are always malformed, and you can't malform XML.
Comment 10 Geoffrey Garen 2007-04-13 14:56:30 PDT
Opera cuts you off at nesting depth 500 and throws away any further nested elements! (Then it hangs, anyway.)
Comment 11 Geoffrey Garen 2007-04-15 15:11:57 PDT
According to Mozilla's bugzilla (see 377056, 256180, and 58917 for starters), this kind of deep nesting often occurs as a result of broken HTML editors or PHP/PERL scripts.
Comment 12 Geoffrey Garen 2007-04-15 15:26:58 PDT
Other potential causes for this problem include a developer who serves XHTML as text/html, and a developer who simply doesn't understand that self-closing is an XML-only feature, and uses self-closing notation in plain HTML. In such cases, any nominally self-closed tags, like <div/>, will actually nest.
Comment 13 Geoffrey Garen 2007-04-15 16:29:32 PDT
The max nesting depth of attachment 14012 [details] is 4061 tags.
Comment 14 Geoffrey Garen 2007-04-15 16:45:18 PDT
If we define a hang as a pause > 10 seconds, then, on my MacBook Pro, depending on whether the nesting is a span, a div, or a span/div pair, WebKit can handle a nesting depth of 14,000, 9,000, or 1250, respectively.
Comment 15 Geoffrey Garen 2007-04-15 16:49:14 PDT
Those numbers also depend on the content of the tags and their style. For example, attachment 14012 [details] is only SPAN elements, but each is styled and contains substantial content. On my MacBook Pro, WebKit can only handle a depth of about 2,000.
Comment 16 Geoffrey Garen 2007-04-15 17:41:43 PDT
IE 6 and IE 7 honor the nesting in attachment 14012 [details] without any noticeable performance problems.
Comment 17 Dave Hyatt 2007-04-20 04:04:26 PDT
Here's another one:

Comment 18 Dave Hyatt 2007-04-20 04:07:39 PDT
This page loads in about 4-5 seconds with the fixes I described in 13351.  Scrolling is still super slow though (which is worthy of a separate bug).

Comment 19 Dave Hyatt 2007-04-20 04:08:09 PDT
By "this page" I meant the attachment, not the URL I just pasted in two comments ago,.
Comment 20 Dave Hyatt 2007-04-20 15:23:57 PDT
The long-term solution to the blocks-inside-inlines problem is to avoid the creation of excess RenderObjects.  Eliminate the concept of the continuation() and all of the inline splitting code and instead enable blocks to have a mixture of line and block children.  The block could then alternate between line and block layout, as it goes through its mixture of lines and blocks.

The line boxes of a single <span> would then be connected as though the blocks weren't present.

First-line could also be simplified, since later lines after subblocks would know they weren't really the first line.
Comment 21 Dave Hyatt 2007-04-20 15:29:55 PDT
I am essentially proposing the elimination of the anonymous block in favor of a RenderBlock that understands how to lay out mixtures and thus doesn't need to create anonymous blocks in the first place.
Comment 22 Dave Hyatt 2007-04-20 16:01:51 PDT
Just brainstorming, but the basic idea would be to allow blocks inside inlines in the render tree.  Do no fixups.  The enclosing block thinks its children are inline.  During line layout, hitting one of these blocks results in an end of the line.  Then block layout has to run until an inline is again encountered.  And so on, switching back and forth between the two layout models.
Comment 23 Dave Hyatt 2007-04-23 18:43:19 PDT
Here's the real stress test.


Pure inline nesting.  No blocks.
Comment 24 Dave Hyatt 2007-04-23 18:48:40 PDT
I have landed a fix that takes care of blocks inside inlines nesting badly.  Next up is a cap on the depth of the line box tree for a given single line.  This should resolve the original test case as well as the penguin test case I just added.

Comment 25 Dave Hyatt 2007-04-23 23:25:54 PDT
I'm declaring victory.

We can file individual bugs for more slowness.