290939 - 100% cpu when selecting text with unicode character with the mouse

Status: RESOLVED WORKSFORME

(Core :: DOM: Selection, defect)

Description

[antoine d]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.7) Gecko/20050414 Firefox/1.0.3
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b2) Gecko/20050418

When rendering this page (http://motscousus.com/dl/charTest.html) at some point
mozilla start rendering the text from right to left, the page only content are
all the unicode chars like $#xx; from 0 to 10000.

The point is starts rendering the text backward can be found right after the
character 8233, then if you start selecting the text around this character then
eventually mozilla will stop responding and all the cpu

Reproducible: Always

Steps to Reproduce:
1.load the page http://motscousus.com/dl/charTest.html
2.scroll down to character 8233
3.start with the mouse to select text containing this character, eventually
mozilla will hang. You may have to do it more than once but I've always "succeed"

Actual Results:  
mozilla stop responding
100% CPU taken by the mozilla process

Expected Results:  
nothing
I also don't know if the rendering is correct (to reverse the flow when
encountering some character seems a weird behaviour to me but I don't know what
are the guidelines for this). As a comparison IE does not reverse the flow.

the crash occured first within firefox so I test tried it with the latest
mozilla build, brand new install, the results are the same.
This has been successfully tested under firefox 20050414, mozilla 20050418 on 3
differents computers, all running windows XP.

Comment 1

[antoine d]

hum forgot to say the characters &#8234 to &#8239 are not rendered (I cannot
find them anywhere on the page) by the browser, this may be another bug and have
something to do with the text flow being reversed.

Comment 2

[Gabriel Chadwick]

I confirm this with Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b2)
Gecko/20050417 Firefox/1.0+ and 1.0.3 .

Comment 3

[Boris Zbarsky [:bzbarsky]]

Minimal testcase needed....

Comment 4

[Simon Montagu :smontagu]

(In reply to comment #1)
> hum forgot to say the characters &#8234 to &#8239 are not rendered (I cannot
> find them anywhere on the page) by the browser, this may be another bug and have
> something to do with the text flow being reversed.

It's not a bug, because they have no renderable form (they are Bidi control
characters) but by the same token they certainly do have something to do with
the text flow being reversed. IE also reverses the text flow after these
characters, but only up to the end of the line in which they appear (or rather,
don't appear), which I can see no justification for.

Comment 5

[antoine d]

(In reply to comment #4)
> It's not a bug
> [...] 
> they certainly do have something to do with
> the text flow being reversed. 

It appears it's not that simple, I've just tested with a shorter version of the
same page containing  only the characters &#8000 to &#9000 and:
- Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.7) Gecko/20050414
Firefox/1.0.3 do not reverse the textflow anymore after &#8233 (you then find
&#8240 on its right), cannot trigger the bug by selecting text
- Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8b2) Gecko/20050418 still
reverse the text flow after &#8233, and trying to trigger the bug by selecting
text will lead to high cpu use (50%-80%) for a few seconds but nothing like
100%/hanging.

I cannot post the shorter version of the page right now, will make that happen
later if nobody does it before.

Comment 6

[antoine d]

(In reply to comment #5)
shorter version : http://legazon.be/stuff/testChar_8000to9000.html

Comment 7

[Simon Montagu :smontagu]

> It appears it's not that simple

You're right :-) The behaviour is affected by bug 177148: in trunk builds before
20050409, or builds from the 1.7 or Firefox 1.0.x branches, the Bidi control
characters have no effect if there are no visible right-to-left characters. This
explains the difference you are seeing.

Comment 8

[Simon Montagu :smontagu]

Attachment: Patch

The patch removes some unnecessary calls to FindLineContaining() which were
making selection O(n^2). This is probably not sufficient, but it makes a
visibly huge difference.

Comment 9

[Boris Zbarsky [:bzbarsky]]

So... I don't really know this code, so it'll take me some time to review. 
Could you maybe explain in words what the patch is doing?  That might help....

Comment 10

[Simon Montagu :smontagu]

Attachment: better (?) patch

I wrote a long comment explaining the previous patch, but as I was doing so it
stopped making sense to me. I now think the whole test being made is
tautologous and can be removed. I need to put in some assertions (not for
checkin) and test it thoroughly before I ask for review again.

Comment 11

[Simon Montagu :smontagu]

Ok, we do need these tests (at least for a superfical definition of "need", in
that sometimes they come out false and sometimes they come out true. So going
back to the first patch, what it does is pretty simple: 

The code I am changing calls nsLineIterator::FindLineContaining(frame, result),
which iterates through every nsLineBox in the block frame and calls
nsLineBox::Contains(frame) on each of them until one returns true, and then
returns the number of that line. It then compares the returned line number with
the number of a given line.

What I am doing instead is taking the nsLineBox at the given line number and
calling nsLineBox::Contains(frame) on it directly. As far as I can see the
semantics of this should be exactly the same as the original.

Comment 12

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 181273 [details] [diff] [review]
Patch

>Index: layout/generic/nsLineBox.cpp
>@@ -861,20 +855,19 @@ nsLineIterator::FindFrameAt(PRInt32 aLin
>-          if (NS_SUCCEEDED(FindLineContaining(tempFrame, &testLine))

This makes |testLine| unused, right?  Remove it, please.

That said, I don't really understand why we have this code.  Consider the
following (for the first hunk of the patch):

1)  We're using line->Contains() on something that's on the
    NextSibling() chain of the line's first frame and isn't more
    than line->GetChildCount() frames along it.
2)  All Contains() does is check that IndexOf() != -1.
3)  IndexOf starts with the first child and walks the sibling chain
    at most GetChildCount times.

So it looks to me like that first Contains() test should always test true....
If it doesn't then I'm clearly missing something (and then this patch may be
wrong...).

Comment 13

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 181273 [details] [diff] [review]
Patch

Marking r- to hopefully get an answer to my question.

Comment 14

[Simon Montagu :smontagu]

I think you're right about the first hunk. When I get a moment I plan to make a
new patch without it.

Comment 15

[Wayne Mery (:wsmwk)]

I can't get to any of the testcase URLs

Comment 16

[antoine d]

Attachment: html file which can trigger the bug

Comment 17

[Boris Zbarsky [:bzbarsky]]

roc, know anyone who can pick this up?

Comment 18

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

It'll have to be Simon.

Comment 19

[Simon Montagu :smontagu]

Do we know that this problem still exists? Uri made a lot of improvements to bidi selection code since it was reported.

Comment 20

[Boris Zbarsky [:bzbarsky]]

Given that the bug reporter attached a file all of a week ago that he says triggers the bug, I would assume the problem still exists, yes.

That said, I'd like instructions on how to trigger the bug with that file, if possible.

Comment 21

[Simon Montagu :smontagu]

(In reply to comment #20)
> Given that the bug reporter attached a file all of a week ago that he says
> triggers the bug, I would assume the problem still exists, yes.

I'm not so sure. I understood comment 16 as implying that the attachment was a reconstruction of the original testcase that triggered the bug back when it was reported, not necessarily that the problem can still be reproduced.

> That said, I'd like instructions on how to trigger the bug with that file, if
> possible.

Yeah, me too. I tried several times to select to and fro in the attachment and didn't see any kind of hang or high CPU usage. I guess it would be worth testing with a less minimized version also.

Comment 22

[Simon Montagu :smontagu]

So, I experimented with a version of attachment 368107 [details] containing characters from U+2020 - U+CFFF and saw serious performance problems with selection, but that turns out to be a different issue: firstly the problems persisted when I started with U+2030, i.e. with no characters that would trigger bidi processing, and secondly I isolated a regression range http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=all&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2006-07-27+10%3A00&maxdate=2006-07-28+04%3A00&cvsroot=%2Fcvsroot, which looks like regression from bug 345099.

That needs its own bug (if it doesn't exist already), but it makes it hard to test this one in isolation.

Comment 23

[Simon Montagu :smontagu]

Filed bug 486072 on that issue.

Comment 24

[Ioana (away)]

Tested with the attached testcase on:
Mozilla/5.0 (Windows NT 5.1; rv:29.0) Gecko/20100101 Firefox/29.0 (20131212030202)

I can't reproduce increase of CPU usage (so no hang either), but there is reversed text flow and missing characters.

Comment 25

[Simon Montagu :smontagu]

reversed text flow and missing characters are expected, see comment 4