Bug 10735

Summary: Clicking in SVG results causes WebKit to consume 100% CPU for several minutes
Product: WebKit Reporter: Mark Rowe (bdash) <mrowe>
Component: SVGAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: justin.garcia, mitz
Priority: P1 Keywords: InRadar, NeedsReduction, SVGHitList
Version: 420+   
Hardware: Mac   
OS: OS X 10.4   
URL: http://bdash.net.nz/files/auckland.svg
Attachments:
Description Flags
Sample during the hang.
none
[WIP] use an iterator that doesn't maintain child indices
none
Use an iterator that doesn't maintain child indices
none
Use an iterator that doesn't maintain child indices
none
Use an iterator that doesn't maintain child indices
darin: review+
Use an iterator that doesn't maintain child indices sam: review+

Description Mark Rowe (bdash) 2006-09-04 21:36:24 PDT
Steps to reproduce:

1) Load URL
2) Wait for it to finish downloading + rendering
3) Click in the middle of the image
4) Note that Safari has become unresponsive
5) Wait patiently for it to finish processing
Comment 1 Mark Rowe (bdash) 2006-09-04 21:37:05 PDT
I have tested with r16068 and r16225 and see the problem in both.
Comment 2 mitz 2006-09-09 00:40:50 PDT
Most of the time is spent in one call to VisiblePosition::canonicalPosition(), and under that in one call to each of Position::upstream(), Position::downstream(), nextCandidate() and previousCandidate(). The position to canonicalize is sitting in a very wide tree of unrendered content. The above 4 calls are O(n^2) since they essentially loop using Position::next() which in turn half the time uses Node::nodeIndex() which is O(n).
Comment 3 Eric Seidel (no email) 2006-09-12 23:32:34 PDT
I'm raising this to a P1 since this is effectively a crash.

It looks like SVG (possibly because of how many nodes it generates as opposed to HTML) just sent the position code off the deep end.  It's also possible that this is caused by bounding-box calculation issues in SVG.
Comment 4 Eric Seidel (no email) 2006-09-12 23:33:03 PDT
Created attachment 10523 [details]
Sample during the hang.
Comment 5 Dave Hyatt 2007-01-10 04:01:46 PST
Maybe try subclassing positionForCoordinates on all SVG objects to return an empty VisiblePosition... with no element at all.... e.g., VisiblePosition(0, 0, DOWNSTREAM);

Comment 6 Stephanie Lewis 2007-01-22 16:51:06 PST
In Radar
<rdar://problem/4946826>
Comment 7 mitz 2007-02-17 15:26:05 PST
Created attachment 13216 [details]
[WIP] use an iterator that doesn't maintain child indices

Passes all the editing tests but I need to review it once more to verify that it is correct, look for more places that can benefit from using the new PositionIterator, possibly split it out into its own files, and figure out if PositionIterator needs to be optimized for the common(?) case of not iterating at all (the optimization would be to cache the initial Position in the PositionIterator, not initialize its other member variables until the first increment/decrement, and if those were never called, do the conversion to Position by returning the cached one).

Some bits of correctness I'm concerned about include editingIgnoresContent()-positive nodes, <br>s and negative offsets.
Comment 8 mitz 2007-02-18 12:38:28 PST
Created attachment 13228 [details]
Use an iterator that doesn't maintain child indices

No layout test regressions.

Note that there used to be a PositionIterator class in WebCore, but it was quite different than the proposed one.
Comment 9 mitz 2007-02-19 08:03:44 PST
Created attachment 13237 [details]
Use an iterator that doesn't maintain child indices

See comment #8. Fixed typos and removed one redundant statement.
Comment 10 Darin Adler 2007-02-19 08:27:39 PST
Comment on attachment 13237 [details]
Use an iterator that doesn't maintain child indices

+friend class PositionIterator;

Normaly we'd indent this kind of friend declaration.

Could we make the helper functions public instead of private? Then PositionIterator would not need to be a friend.

Why does Position need to be a friend of PositionIterator?

r=me, anyway
Comment 11 mitz 2007-02-19 11:18:03 PST
Comment on attachment 13237 [details]
Use an iterator that doesn't maintain child indices

Going to make a new patch
Comment 12 mitz 2007-02-19 11:56:24 PST
Created attachment 13243 [details]
Use an iterator that doesn't maintain child indices

(In reply to comment #10)
> Could we make the helper functions public instead of private? Then
> PositionIterator would not need to be a friend.

Done.

> Why does Position need to be a friend of PositionIterator?

The Position(const PositionIterator&) constructor accesses private members. I left it this way in this patch because it's the lesser evil of the alternatives I could think of.

Also fixed the indentation of the friend declaration and moved another star.
Comment 13 Darin Adler 2007-02-19 15:04:29 PST
Comment on attachment 13243 [details]
Use an iterator that doesn't maintain child indices

r=me

I'd like to see makefiles updated for platforms other than Mac.
Comment 14 mitz 2007-02-19 17:07:47 PST
Created attachment 13258 [details]
Use an iterator that doesn't maintain child indices

(In reply to comment #13)
> I'd like to see makefiles updated for platforms other than Mac.

Done.
Comment 15 Sam Weinig 2007-02-19 17:12:51 PST
Comment on attachment 13258 [details]
Use an iterator that doesn't maintain child indices

Really only reviewing the updates to the makefiles/build systems for non-mac platforms.  r=me!
Comment 16 Sam Weinig 2007-02-20 08:12:05 PST
Landed in r19734.