686497 - Hang [@ _cairo_bo_point32_compare] when spellchecking large string

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Martijn Wargers (dead)]

Attachment: log of hang

See url testcase, which is from bug 334814:
https://bugzilla.mozilla.org/attachment.cgi?id=219142 

Right-click on the the text input and click on "Check Spelling".

Result:
Hang

See hang log, that I attached from a Firefox debug build.
This is a regression from bug 629719.

Comment 1

[(no longer active)]

Can you only reproduce this on Windows?  From the log, it seems like this is a bug in Cairo...

Comment 2

[arno renevier]

Attachment: testcase with -moz-text-decoration-style: wavy;

I can reproduce on linux.
Actually, painting the wavy text decorations under the mispelled words results in a drawing many small segments (nearly 500000). Then, in cairo, _cairo_bo_event_queue_sort performs a n^2 sort. It's not an infinite loop, just a really long one. Probably after a few hours, paint will be finished :)

This can be reproduced, independently of bug 629719 by setting a -moz-text-decoration-style: wavy; to a long element. I'm attaching a testcase which does not rely on spellcheck.

Comment 3

[arno renevier]

For whatever reason, in this specific case, when this sort is performed, cairo still considers paths outside its clip region. That's why the bug appears even in first testcase when an important part of the string is not painted.

A first solution is therefore to not extend path outside the clip extent. But that would not fix the problem for second testcase, or for a big textarea.

Another solution is to work around the n^2 behaviour by stroking often. For example, if I call aGfxContext->Stroke() at the end of each while (pt.x < rightMost) loop, testcase (1 and 2) loads correctly without hanging Firefox. The painting of the waves takes about 120ms. But if I stroke less often, for example, every 10 loop iteration, it takes less time (about 45ms). So, there is probably a balance between calling stroke once, and hang because of the n^2 sort, and the overhead of stroking each time.
Here are the results I get on my system on testcase2:
stroking every 1 iteration : 120ms
         every 5 iterations: 60ms
              10 iterations: 45ms
              50 iterations: 40ms
             100 iterations: 33ms
             500 iterations: 43ms
            1000 iterations: 50ms
            5000 iterations: 577ms
           10000 iterations: 2300ms
But how to get a value correct on every system ?

Comment 4

[arno renevier]

Attachment: patch: call restore at each iteration

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I think this patch changes the rendering if the color of the wavy line was partially transparent; overlapping line ends will be drawn differently from before.

Jeff, can you say anything about comment #2 or #3? Why is cairo doing an O(N^2) sort?

Comment 6

[Jonathan Kew [:jfkthame]]

I don't think it's true that cairo is doing an O(n^2) sort - it uses combsort11, which should be O(n log n). The problem is simply that the testcase ends up with an "event queue" of a couple of million cairo_bo_event_t records, and that's enough to bring the machine to its knees for a significant period.

While it's true that "flushing" the line instead of constructing the entire thing and then stroking it all at once could alter the rendering at overlapping ends, I think we could reasonably pick a number like 1000 iterations and stroke when we reach this. It's hard to imagine a real-world use case where the potential visual glitch after 1000 waves of the line would really be significant.

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

True.

Another option is to pass in the dirty rect and skip path segments that we know are outside the dirty rect. There's no need to construct such a huge path.

Comment 8

[Jonathan Kew [:jfkthame]]

Attachment: patch, pass dirtyRect to nsCSSRendering::PaintDecorationLine and use it to limit the number of waves

Something like this, maybe? Using the dirty rect to trim the wavy underline requires propagating it down through the callers of this function, so it ends up impacting several classes, but it's probably worth doing, as the performance win in extreme cases is huge - we end up constructing a path of a few hundred segments, instead of hundreds of thousands, or even millions.

I'd like to retain the idea of stroking the wavy-line path and starting afresh if it reaches 1000 iterations, just as a safety measure. This shouldn't ever happen in "normal" cases, but I expect there may be ways to construct a diabolical testcase (perhaps using a transform, to effectively make the visible section of the text much longer) that would still run into problems, and the precautionary fix is simple and cheap.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 560552 [details] [diff] [review]
patch, pass dirtyRect to nsCSSRendering::PaintDecorationLine and use it to limit the number of waves

Review of attachment 560552 [details] [diff] [review]:
-----------------------------------------------------------------

Fantastic!

::: layout/generic/nsTextFrameThebes.cpp
@@ +5030,5 @@
>        pt.x = (aFramePt.x + xOffset -
>               (mTextRun->IsRightToLeft() ? advance : 0)) / app;
>        gfxFloat width = NS_ABS(advance) / app;
> +      gfxRect dirtyRect(aDirtyRect.x / app, aDirtyRect.y / app,
> +                        aDirtyRect.width / app, aDirtyRect.height / app);

Hoist this out of the loop

::: layout/xul/base/src/nsTextBoxFrame.cpp
@@ +501,5 @@
>  
> +    gfxRect dirtyRect(presContext->AppUnitsToGfxUnits(aDirtyRect.x),
> +                      presContext->AppUnitsToGfxUnits(aDirtyRect.y),
> +                      presContext->AppUnitsToGfxUnits(aDirtyRect.width),
> +                      presContext->AppUnitsToGfxUnits(aDirtyRect.height));

presContext->AppUnitsToGfxUnits(aDirtyRect)

Comment 10

[Jonathan Kew [:jfkthame]]

Pushed to -inbound, with fixes as per comment 9:
https://hg.mozilla.org/integration/mozilla-inbound/rev/1fc426aa485c

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/1fc426aa485c