449167 - Speed up removing ranges from a selection

Status: NEW

(Core :: DOM: Selection, defect, P3)

Description

[Boris Zbarsky [:bzbarsky]]

Attachment: Proposed fix

Removing a range from an nsTypedSelection unselects all the frames that the range covers, then reselects all the frames that the other ranges in the selection cover.  Clearing an nsTypedSelection unselects all the frames that the ranges cover.

The thing is, nsTextFrame's SetSelection(PR_FALSE) checks whether there are any selections still overlapping the frame, and if so keeps the SELECTED_CONTENT bit.

This means three things:

1) Clearing an nsTypedSelection is O(N^2) in number of ranges (since we do the "still overlapping the frame" check for each range for each selectFrames call, and call selectFrames once for each range).
2) Clearing an nsTypedSelection doesn't correctly remove the SELECTED_CONTENT bits if there are multiple ranges.
3) Removing a range from a selection does extra work, since we'll reselect the other ranges in the selection anyway.

The attached patch fixes all three issues.

Comment 1

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

Does this mean that nsIFrame::SetSelected with aSelected==PR_FALSE effectively removes all ranges, so aRange is irrelevant?

It seems to me that the way removing a range was intended to work is that we'd just remove the range and then call SetSelected on that range, passing in aSelected=PR_FALSE. Is it impossible to get it to work that way?

Comment 2

[Boris Zbarsky [:bzbarsky]]

aRange is used to decide which frames to propagate the SetSelected call to, as far as I can tell.  That's the only reason it's passed to the frame.

It seems to me that that's how it's intended to work as well, and that's basically what we do.  The problem is that:

1)  A single nsTypedSelection can have overlapping ranges (this needs to be fixed)
2)  A single nsFrameSelection can have nsTypedSelections with overlapping ranges (this will continue to be the case).

Note that most SetSelected impls don't do what nsTextFrame does; I'm pretty sure all the ones that munge NS_FRAME_SELECTED_CONTENT but are not nsTextFrame screw up if there are multiple nsTypedSelections that include them.

Comment 3

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

> It seems to me that that's how it's intended to work as well, and that's
> basically what we do.

No, as you said in comment #0 we deselect all the ranges and then select all but the one we removed.

What if we make SetSelected into SelectionChanged, don't pass aSelected, aRange or aSourceSelection, and make the implementors responsible for calling GetSelectionDetails/LookUpSelection to figure out what their state is? Then we should be able to get away with doing a single SelectionChanged when we remove a range. It seems simpler.

Comment 4

[Boris Zbarsky [:bzbarsky]]

We just deselect the one range and reselect all the others...  That's what I said in comment 0, no?

SelectionChanged might work; I need to think about how that would interact with textframes with lots of continuations.

Comment 5

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

Oh, OK. Still, reselecting all the others should not be necessary.

Comment 6

[Boris Zbarsky [:bzbarsky]]

We need to either do that or do what textframe does right now (without skipping the "current" selection).  We definitely don't want to do both.

I agree that it would be nice if the frames just dealt.

Comment 7

[Boris Zbarsky [:bzbarsky]]

cpearce, you might be interested in this bug too.  I'm sort of assuming at this point that roc's comments constitute r- on the patch above, but...

Comment 8

[Boris Zbarsky [:bzbarsky]]

Attachment: Merge to m-c tip

Comment 9

[Graeme McCutcheon [:graememcc]]

> 1)  A single nsTypedSelection can have overlapping ranges (this needs to be
> fixed)

Fixed! Landed bug 348681.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Attachment: Merged to bug 371839

Re-setting the review request, but if we want to do other things before this, please just r-.

Comment 11

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

+nsTextFrame::GetSelectionDetails(nsISelection* aSelectionToSkip)
 {
   const nsFrameSelection* frameSelection = GetConstFrameSelection();
   if (!(GetStateBits() & NS_FRAME_GENERATED_CONTENT)) {
     SelectionDetails* details =
       frameSelection->LookUpSelection(mContent, GetContentOffset(),
-                                      GetContentLength(), PR_FALSE);
+                                      GetContentLength(), PR_FALSE,
+                                      aSelectionToSkip);

Is this actually right?

If we have a selection with two ranges that are both in the same text frame, and we remove one of those ranges, we don't want GetSelectionDetails to return nothing, do we?

Why add aSourceSelection to SetSelected, since none of the implementations seem to use it?

Comment 12

[Boris Zbarsky [:bzbarsky]]

> If we have a selection with two ranges that are both in the same text frame,
> and we remove one of those ranges, we don't want GetSelectionDetails to return
> nothing, do we?

Maybe, given this code in nsTypedSelection::RemoveRange:

5046   // clear the selected bit from the removed range's frames
5047   nsCOMPtr<nsPresContext>  presContext;
5048   GetPresContext(getter_AddRefs(presContext));
5049   selectFrames(presContext, aRange, PR_FALSE);
5050 
5051   // add back the selected bit for each range touching our nodes
5052   nsCOMArray<nsIRange> affectedRanges;
5053   rv = GetRangesForIntervalCOMArray(beginNode, beginOffset,
5054                                     endNode, endOffset,
5055                                     PR_TRUE, &affectedRanges);
5056   NS_ENSURE_SUCCESS(rv, rv);
5057   for (PRInt32 i = 0; i < affectedRanges.Count(); i ++) {
5058     selectFrames(presContext, affectedRanges[i], PR_TRUE);
5059   }

See also comment 0.

Now if we can change things so we didn't have to do that, that would be lovely.  Can we?  For textframe it's pretty easy (just remove that second hunk).  What about other frames?

That said, does that second hunk even do anything given the non-overlapping thing we have going on now?  I guess it can because we pass aAllowAdjacent == true here. This might mean the patch (which predates the business with non-overlapping ranges) is no longer really relevant or needed for this part, since we'd have at most two ranges in the details, not hundreds to thousands as before.

We should still fix issues 2 and 3 from comment 0, but that's a much smaller patch.  If you think that the one-range removal is sane now, I'll just do that.

> Why add aSourceSelection to SetSelected

You're right; that's not needed.

Comment 13

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

(In reply to comment #12)
> We should still fix issues 2 and 3 from comment 0, but that's a much smaller
> patch.  If you think that the one-range removal is sane now, I'll just do that.

It's definitely the sane thing to do. The only question is whether anything not-sane is still around that will break. I say let's do it!

Comment 14

[Boris Zbarsky [:bzbarsky]]

No, what I meant is that if you think one-range removal doesn't do way too much work like it used to.  I don't see why we need to first selectFrames(false) and then selectFrames(true).  And I'm not sure that we don't end up doing too much work for all those selectFrames() calls even now... Thats' the part whose sanity I'm worried about.

Comment 15

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

Now I'm even more confused.

Can't we remove this?
5057   for (PRInt32 i = 0; i < affectedRanges.Count(); i ++) {
5058     selectFrames(presContext, affectedRanges[i], PR_TRUE);
5059   }

Comment 16

[Boris Zbarsky [:bzbarsky]]

That was my question in comment 12.  nsTextFrame is obviously ok with that.  But nsFrame will remove the NS_FRAME_SELECTED_CONTENT bit if we call the selectFrames(...., PR_FALSE) and not the PR_TRUE.  And if the selection has multiple ranges that all intersect a single nsFrame (say a block, or worse a table cell) it seems like we'd get the wrong behavior.

Comment 17

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

OK, so we'd also need to modify the SetSelected implementations to call back to get the selection details if necessary.

Comment 18

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

Comment on attachment 390765 [details] [diff] [review]
Merged to bug 371839

We probably need a deeper fix here.

Comment 19

[Boris Zbarsky [:bzbarsky]]

Not going to get to this. Mats, do you know whether this is even still an issue?