371839 - Improve SetSelected setup in nsTextFrame

Status: RESOLVED FIXED

(Core :: Layout, defect, P1)

Description

[Boris Zbarsky [:bzbarsky]]

Right now, calling SetSelected on an nsTextFrame also calls it on all continuations.  If bug 240933 is fixed, a large textarea may contain a single textnode with lots of textframes.  In that situation, doing selection stuff (e.g. the way spellcheck does it) becomes rather expensive.

Right now we do this in a particularly inane way, but even a better algorithm (using nsIRange, bailing out once we're outside the range, etc) would be O(K*N) where N is the number of ranges added/removed and K is the number of continuations.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Said better algorithm

With this change, the time spent in nsTextFrame::SetSelected goes to almost 0 (212 hits when doing "Edit as comment" on <http://bugzilla.mozilla.org/attachment.cgi?id=143917&action=edit>, down from more like 200,000 hits).  I think we're being somewhat saved by the 4KB limit on text nodes.

If we decide we need something a little better (e.g. if we remove that 4KB limit), we could change the way we get the |start| pointer to use a cursor or something.  Or come with a cleverer way to do things, maybe...

Comment 2

[Eli Friedman]

> If we decide we need something a little better (e.g. if we remove that 4KB
> limit), we could change the way we get the |start| pointer to use a cursor or
> something.  Or come with a cleverer way to do things, maybe...

I think if we got rid of the 4kb limit, we'd have bigger problems than selection... try typing in the middle of a 250k text node.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Sure.  We'd need to address that....

Note that such nodes can _already_ be created, just not via the parser.

Comment 4

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

+    if (cur->mContentOffset >= startOffset) {
+      cur->DoSetSelected(aSelected, empty);

Shouldn't this be "cur->mContentOffset + cur->mContentLength > startOffset"?

+    if (cur->mContentOffset < startOffset) {
+      cur->DoSetSelected(aSelected, empty);
+    }

Shouldn't this be "cur->mContentOffset < endOffset"?

Comment 5

[Boris Zbarsky [:bzbarsky]]

Attachment: Doh!

Yes on both counts.

Doesn't really affect the performance results.  ;)

Comment 6

[Boris Zbarsky [:bzbarsky]]

Checked in.

Comment 7

[Boris Zbarsky [:bzbarsky]]

I backed this out to fix bug 372139.  I'll revisit this once bug 367177 lands.

The problem is that we have consumers that set a range, and then start mutating the text in the textframe.  It sorta works right now, sorta, because we mark all the existing continuations as maybe having a selection.  But with this patch, it failed if the textframe started out _empty_ and then got some text.

We could probably deal with that by propagating more of the CharacterDataChanged info into the textframe and probably adding a "reget selected state" bit on whatever frames we mark dirty based on that data.  Or something.  Need to think a little more about it.

Comment 8

[Boris Zbarsky [:bzbarsky]]

Bug 385270 will make some changes to the offset setup that we would want for anything reasonable here.

Comment 9

[Serge Gautherie (:sgautherie)]

(All (3) blocking bugs fixed ! Good time for a (patch) update ?)

Comment 10

[Boris Zbarsky [:bzbarsky]]

Yeah, if I can find the time.  Or if someone else does.  And whats needed is time to think about how to do this right, not just updating the patch or something silly like that.

Comment 11

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

My solution to the issue in comment #7 is to have text frames re-get their selection state after we've reflowed them. I use a flag on the content text node to indicate if any frames for the node have a selection, and only re-get the selection state if that flag is set.

Comment 12

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

Attachment: Part 1: Don't let debug-only code add O(N) to our algorithms

Assertions that loop over all continuations should just bail out conservatively after a fixed number of iterations. Otherwise it's impossible to get remotely meaningful performance from debug builds.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 387374 [details] [diff] [review]
Part 1: Don't let debug-only code add O(N) to our algorithms

Could we make that '10' an env var or something?  Ideally Jesse can then fuzz with it set higher if needed.

I assume the most common case is in fact that things would be close on the continuation chain if we were to screw this up?

Comment 14

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

Oops, there's an additional fix that landed in the wrong part of my patch queue:
 PRBool nsSplittableFrame::IsInPrevContinuationChain(nsIFrame* aFrame1, nsIFrame* aFrame2)
 {
   PRInt32 iterations = 0;
   while (aFrame1 && iterations < 10) {
     // Bail out after 10 iterations so we don't bog down debug builds too much
     if (aFrame1 == aFrame2)
       return PR_TRUE;
     aFrame1 = aFrame1->GetPrevContinuation();
+    ++iterations;
   }
   return PR_FALSE;
 }

/me chuckles quietly that Boris didn't catch it :-)

(In reply to comment #13)
> Could we make that '10' an env var or something?  Ideally Jesse can then fuzz
> with it set higher if needed.
> 
> I assume the most common case is in fact that things would be close on the
> continuation chain if we were to screw this up?

I think that any bug in our code is catchable with a testcase that uses continuation chains of length 10 or less, so this should be OK as-is.

Comment 15

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

Attachment: Part 2: treat \n as space as far as the line breaker is concerned

The main impact of this is the effect on TextContainsLineBreakerWhiteSpace --- it will now return true for lines that contain a \n. Without this, in long text files where each line contains no spaces, we look back all the way to the start of the file when trying to find a line to start linebreak analysis and textrun construction on --- very bad.

Comment 16

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

Attachment: Part 3: Remove some useless, yet confusing, code

In nsFrame::SetSelected, GetOffsets always returns 0,0 (because only nsTextFrame overrides GetOffsets, and nsTextFrame never calls nsFrame::SetSelected). So the IBMBIDI code in nsFrame::SetSelected never does anything.

nsTableCellFrame::SetSelected just calls nsFrame::SetSelected and then sometimes calls InvalidateOverflowRect. But nsFrame::SetSelected already did InvalidateOverflowRect (unless the frame is not selectable, in which case nsTableCellFrame shouldn't do it either). So nsTableCellFrame::SetSelected is superfluous.

nsTableFrame::SetSelected just calls nsFrame::SetSelected and is superfluous.

Comment 17

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

Attachment: Part 4: change SetSelected API and reimplement it for nsTextFrame

-- nsFirstLetterFrame::SetSelected is never called, since we only call SetSelected on primary frames, and nsFirstLetterFrame is never the primary frame for a content node. Remove it. (I guess this should have gone in the last patch.)

-- Change nsIFrame::SetSelected so it is documented to only be called on the primary frame. Remove the spread argument and the range argument and define it to select the entire node. Fix nsIFrame::SetSelected implementation accordingly.

-- Remove overloading of nsTypedSelection::selectFrames, renaming one to SelectFramesAll to reflect its purpose better.

-- nsTypedSelection::SelectFramesAll does not need the half-baked code to walk over all in-flows. That is weird (the height/width checks), wrong (doesn't cross fixed continuations) and unnecessary with the new definition of SetSelected.

-- nsTypedSelection::selectFrames handles partially selected text nodes explicitly, by casting them to nsTextFrame and calling a special nsTextFrame::SetSelectedRange interface.

-- nsTextFrame::SetSelectedRange takes the start and end offsets explicitly so text frames don't have to pick apart the range.

-- Implement nsTextFrame::SetSelectedRange. It's straightforward, once we know that it's only called on the primary frame. I also keep track of whether there's any selected content in the entire continuation chain, so I can set NS_TEXT_IN_SELECTION on the text node.

-- I use NS_TEXT_IN_SELECTION in nsTextFrame::Reflow to decide whether to recompute the frame's NS_FRAME_SELECTED_CONTENT bit. That recomputation should take care of the problems we had here before.

Using NS_TEXT_IN_SELECTION on the node is a bit naughty here because with multiple presentations, that would break. However, you can't select text in print/print-preview presentations so I don't think this is a problem. Anyway, we'll be getting rid of multiple presentations.

Comment 18

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

Attachment: Part 5: Remove even more useless, confusing code

nsFrame::ParentDisablesSelection always returns false. So, calling it from nsTextFrame is pointless. And no-one ever calls the nsTableCellFrame/nsTableFrame versions.

Comment 19

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

Attachment: Part 6: some tests

Not much here, just reftest versions of the tests in bug 372139.

Comment 20

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

I checked in part 1:
http://hg.mozilla.org/mozilla-central/rev/4b6956941f36
and part 2:
http://hg.mozilla.org/mozilla-central/rev/92cc21ed9634

Part 2 seemed to cause some test failures:
http://tinderbox.mozilla.org/showlog.cgi?log=Firefox/1247199195.1247205665.8856.gz#err0
so I backed it out.

Comment 21

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

Part 2 fails because adding \n to nsLineBreaker::IsSpace causes the linebreaker to treat "foo \n" as only having a linebreak opportunity after the \n. But gfxTextRun::BreakAndMeasureText does not treat \n as trailing whitespace so we treat "foo \n" as being wider than "foo", so it doesn't fit in the preferred width and tests fail. I'll post a better patch in a new bug.

Comment 22

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 387384 [details] [diff] [review]
Part 4: change SetSelected API and reimplement it for nsTextFrame

>+++ b/layout/generic/nsSelection.cpp
>+  nsresult     SelectFramesAll(nsIContentIterator *aInnerIter,
>+                               nsIContent *aContent,
>+                               PRBool aSelected);

The naming here is sort of suboptimal.  Maybe "SelectAllFramesForContent" or some such?

It's worth double-checking the iterator mess in selectFrames (maybe in a separate bug).  I _think_ what it's doing is walking the "toplevel" kids of range and then for each one walking the entire subtree under your SelectFramesAll.  But "toplevel" kids of a range include all ancestors of the start node and end node up to but not including the common ancestor.  So if a selection has deep endpoints with a not-deep common ancestor, we'll end up doing a lot more work than we need to around the selection endpoints, I think.  And possibly calling SetSelected on some nodes that are actually outside the selection (kids of the endpoint ancestor that come before the endpoint in its child list, say).

Again, followup bug on all this.  None of it is really new with your code, and I might be wrong about how this works; maybe it's sane after all...

>@@ -4287,46 +4263,57 @@ nsTypedSelection::selectFrames(nsPresCon
>+      if (frame && frame->GetType() == nsGkAtoms::textFrame)

I guess it could also be an SVG glyph frame?  It might be worth documenting that.

>+        PRUint32 endOffset = content->GetText()->GetLength();
>+        if (aRange->GetEndParent() == content) {
>+          endOffset = aRange->EndOffset();
>+        }

Worth initing to GetText()->GetLength() in the else to avoid the extra virtual call?  Or not worth worrying about?

>+++ b/layout/generic/nsTextFrameThebes.cpp
>+nsTextFrame::SetSelectedRange(PRUint32 aStart,

>+  // XXXroc This is stupid, ParentDisablesSelection just returns true. Let's
>+  // kill it.

it just returns false, but yes.  Let's kill it.  Followup?

>+    } else { // we need to see if any other selection is available.
>+      SelectionDetails *details = f->GetSelectionDetails();

So bug 449167 is still relevant after this change, right?

>@@ -6414,17 +6392,28 @@ nsTextFrame::Reflow(nsPresContext*      
>+    // XXXroc Watch out, this could be slow!!! Speed up GetSelectionDetails?

Yes.  In fact, I'm not sure the patch really makes things better in the bad cases, given this.  With large textareas, GetSelectionDetils will at best be O(# of spellcheck underlines) and if you type we'll likely reflow all the text....

It really feels like there should be a better approach here, somehow.  One that won't make typing a single character O((# spellcheck selections) * (#lines)).

Comment 23

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

(In reply to comment #22)
> (From update of attachment 387384 [details] [diff] [review])
> >+++ b/layout/generic/nsSelection.cpp
> >+  nsresult     SelectFramesAll(nsIContentIterator *aInnerIter,
> >+                               nsIContent *aContent,
> >+                               PRBool aSelected);
> 
> The naming here is sort of suboptimal.  Maybe "SelectAllFramesForContent" or
> some such?

OK.

> It's worth double-checking the iterator mess in selectFrames (maybe in a
> separate bug).  I _think_ what it's doing is walking the "toplevel" kids of
> range and then for each one walking the entire subtree under your
> SelectFramesAll.  But "toplevel" kids of a range include all ancestors of the
> start node and end node up to but not including the common ancestor.  So if a
> selection has deep endpoints with a not-deep common ancestor, we'll end up
> doing a lot more work than we need to around the selection endpoints, I think. 
> And possibly calling SetSelected on some nodes that are actually outside the
> selection (kids of the endpoint ancestor that come before the endpoint in its
> child list, say).
> 
> Again, followup bug on all this.  None of it is really new with your code, and
> I might be wrong about how this works; maybe it's sane after all...

I think you're right.

> >@@ -4287,46 +4263,57 @@ nsTypedSelection::selectFrames(nsPresCon
> >+      if (frame && frame->GetType() == nsGkAtoms::textFrame)
> 
> I guess it could also be an SVG glyph frame?  It might be worth documenting
> that.

OK.

> >+        PRUint32 endOffset = content->GetText()->GetLength();
> >+        if (aRange->GetEndParent() == content) {
> >+          endOffset = aRange->EndOffset();
> >+        }
> 
> Worth initing to GetText()->GetLength() in the else to avoid the extra virtual
> call?  Or not worth worrying about?

I'll fix that.

> >+++ b/layout/generic/nsTextFrameThebes.cpp
> >+nsTextFrame::SetSelectedRange(PRUint32 aStart,
> 
> >+  // XXXroc This is stupid, ParentDisablesSelection just returns true. Let's
> >+  // kill it.
> 
> it just returns false, but yes.  Let's kill it.  Followup?

That was Part 5 in this bug.
 
> >+    } else { // we need to see if any other selection is available.
> >+      SelectionDetails *details = f->GetSelectionDetails();
> 
> So bug 449167 is still relevant after this change, right?

Yes.

> >@@ -6414,17 +6392,28 @@ nsTextFrame::Reflow(nsPresContext*      
> >+    // XXXroc Watch out, this could be slow!!! Speed up GetSelectionDetails?
> 
> Yes.  In fact, I'm not sure the patch really makes things better in the bad
> cases, given this.  With large textareas, GetSelectionDetils will at best be
> O(# of spellcheck underlines) and if you type we'll likely reflow all the
> text....
> 
> It really feels like there should be a better approach here, somehow.  One
> that won't make typing a single character O((# spellcheck selections) *
> (#lines)).

I wasn't really trying to improve the "huge number of spellcheck ranges" case in this patch, I was more focused on making selection in huge non-spellchecked text nodes fast (and saner).

However, it seems to me that thanks to the fix for bug 348681, each GetSelectionDetails will only be O(log num_spellcheck_underlines). So I think this is OK.

Comment 24

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

Really I'd like to have selection bits in content, not frames, so we wouldn't need to to any of this.

Comment 25

[Boris Zbarsky [:bzbarsky]]

> thanks to the fix for bug 348681, each GetSelectionDetails will only be O(log
> num_spellcheck_underlines)

Hmm.... Yeah, I think you might be right.  That should hopefully work out.

Note that you can see how spellcheck behaves by applying the "sort of start" patch in bug 240933 and then trying the steps in comment 1 of this bug.  Heck, I'd be interested in how your patch behaves on that testcase without the stuff from bug 240933...

Comment 26

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

Separately I'd like to fix things so that inserting a character doesn't have to dirty all following continuations. I've got a patch to pass CharacterChangeInfo directly into the text frame, from there it should be pretty easy. I'll finish it in another bug.

> if you type we'll likely reflow all the text....

What do you mean exactly? In a BR-less world, with all the text in one node, we might. But today we'll only dirty the affected line, or is there something I'm missing?

Comment 27

[Boris Zbarsky [:bzbarsky]]

> I've got a patch to pass CharacterChangeInfo directly into the text frame

Sounds good.

Oh, the BR-less world is what I'm worried about (and why this bug was filed; see comment 0. I just realized that comment 1 is predicated on applying the patch in bug 240933, so that testcase isn't likely to really exercise this code much)....  I guess we can file a separate bug on making that work better.

Comment 28

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

Attachment: Part 4 v2

I made those (fairly minor) changes. Is there anything else I should do?

Comment 29

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 388882 [details] [diff] [review]
Part 4 v2

That looks fine, since you plan to remove the incorrect "returns true" comment, though it might be nice to change it to "returns false" in both patches (the one that adds the comment, and the one that removes it).

I do still think it's worth having a bug on a faster GetSelectionDetails version that will just say whether a selection overlaps us instead of trying to be exhaustive...

Comment 30

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

http://hg.mozilla.org/mozilla-central/rev/a0b42fa6b477
http://hg.mozilla.org/mozilla-central/rev/21085f671314
http://hg.mozilla.org/mozilla-central/rev/063330fb2f27
http://hg.mozilla.org/mozilla-central/rev/ca9a91599197

Comment 31

[Boris Zbarsky [:bzbarsky]]

> I think you're right.

Did we ever file a followup bug on that?