593211 - Optimize caret movement without caching the caret frame and frame offset

Status: RESOLVED FIXED

(Core :: DOM: Editor, defect)

Description

[Jim Jeffery not reading bug-mail 1/2/11]

Go to the URL above, or even use Bugzilla - as I'm seeing the issue here also:

1. Enter text into the Description box and note that the cursor does not follow the typing, and only plays catch-up when you stop/pause typing. 

Tested using the latest hourly build based on cset: 
http://hg.mozilla.org/mozilla-central/rev/ba1849f86ade

Not sure what bug caused the regression, any of:
bug 240933 , bug 570192 , bug 590554

Comment 1

[(no longer active)]

I don't know how on Earth I managed to miss this.  Anyway, I've backed out bug 240933 for now.

Comment 3

[(no longer active)]

bisect tells me that this is a regression from attachment 459123 [details] [diff] [review].  I'm going to investigate (and fix) this tomorrow.

Comment 4

[(no longer active)]

This is actually a regression from bug 581585.  When we try to use the cached frame and frame offset for the caret, we don't check to see if the content subtree for mLastContent is the same as it was before the call.  I have a test case which demonstrates this happening without even using a textarea.

Comment 5

[(no longer active)]

Attachment: Test case not using textarea

In this test case, we put the selection on the second child of the div, and then mutate the first child.  The caret doesn't update its position after this mutation.

This works correctly before bug 581585.  I also tested this on Chrome, which was affected by the same bug.

Comment 6

[(no longer active)]

Attachment: WIP

This is a WIP, which mostly works, but it crashes when running the editor tests.  The crash happens when nsNodeUtils::LastRelease tries to call the mutation observers for a LI element.  I haven't been able to track down the crash for now, but I thought I'd post the patch here to have roc's feedback on it.

Comment 7

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

I think instead we should probably back out bug 581585 and fix the performance issues in GetCaretFrameForNodeOffset another way. In retrospect, GetCaretFrameForNodeOffset is complicated and making sure we always detect a change in its inputs so we can flush the frame cache is going to be too fragile.

I think we could make nsBlockInFlowLineIterator::nsBlockInFlowLineIterator(nsBlockFrame* aFrame, nsIFrame* aFindFrame, PRBool* aFoundValidLine)
always start its search from the block's line cursor, if there is one. Lines are doubly-linked so you can search forward and backward at the same rate and find the line containing the frame in time proportional to the number of lines between the target line and the cursor. I think this would work well because the line cursor is the first line of the block that's visible. The caret is usually near there.

Comment 8

[(no longer active)]

Attachment: Part 1: back out the code parts of bug 585922

Comment 9

[(no longer active)]

Attachment: Part 2: back out bug 581585

Comment 10

[(no longer active)]

Attachment: Part 3: Use the line cursor

(In reply to comment #7)
> I think we could make
> nsBlockInFlowLineIterator::nsBlockInFlowLineIterator(nsBlockFrame* aFrame,
> nsIFrame* aFindFrame, PRBool* aFoundValidLine)
> always start its search from the block's line cursor, if there is one. Lines
> are doubly-linked so you can search forward and backward at the same rate and
> find the line containing the frame in time proportional to the number of lines
> between the target line and the cursor. I think this would work well because
> the line cursor is the first line of the block that's visible. The caret is
> usually near there.

Like this?

Comment 11

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

+  nsIFrame *scrollFrame =
+    nsLayoutUtils::GetClosestFrameOfType(aFrame, nsGkAtoms::scrollFrame);
+  if (scrollFrame) {
+    nsIScrollableFrame *sf = do_QueryFrame(scrollFrame);
+    nsIFrame *scrolledFrame = sf->GetScrolledFrame();
+    nscoord offsetY = aFrame->GetOffsetTo(scrolledFrame).y;
+
+    // Don't use the line cursor if we might have a descendant placeholder ...
+    // it might skip lines that contain placeholders but don't themselves
+    // intersect with the dirty area.
+    nsLineBox* cursor = aFrame->GetStateBits() & NS_FRAME_FORCE_DISPLAY_LIST_DESCEND_INTO
+      ? nsnull : aFrame->GetFirstLineContaining(offsetY);
+    if (cursor) {

You don't need any of this. Just grab the LineCursorProperty() for the block and use it if it's there.

+  // If we reach here, it means that the cursor based search has failed,
+  // so we fall back to the dumb search strategy of starting from the first
+  // line and iterate over all of the lines linearly.
+
+  mLine = aFrame->begin_lines();

This means if the frame is in the overflow lines and not the in-flow lines, we will iterate over the main set of lines again. That's a bit wasteful.

I suggest we start with LineCursorProperty() and if that doesn't exist, start with mLines.begin(), and search all the in-flow lines the way you have it now. If that fails, instead of calling FindValidLine() just go ahead and start searching the overflow lines.

Comment 12

[(no longer active)]

(In reply to comment #11)
> I suggest we start with LineCursorProperty() and if that doesn't exist, start
> with mLines.begin(), and search all the in-flow lines the way you have it now.
> If that fails, instead of calling FindValidLine() just go ahead and start
> searching the overflow lines.

Unless I'm missing something, this version of the iterator constructor will always set mInOverflowLines to null, which should means that it should never search the overflow lines.  Is that right?  If yes, then I think the old search code can be completely replaced with the new one.

Comment 13

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

FindValidLine() and Next() can set mInOverflowLines and search the overflow lines.

Comment 14

[(no longer active)]

Right...

Comment 15

[(no longer active)]

Attachment: Part 3: Use the line cursor

In order to prevent code duplication, I decided to just set mLine to the end iterator and use the existing code to iterate over the overflow lines.  Hope I haven't missed anything...

Comment 16

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

(In reply to comment #15)
> In order to prevent code duplication, I decided to just set mLine to the end
> iterator

You did?

+  mLine = aFrame->begin_lines();

Looks to me like you need to add mLine = aFrame->end_lines() at the end of the "if (cursor)" block, and set mLine to begin_lines if !cursor.

Comment 17

[(no longer active)]

(In reply to comment #16)
> (In reply to comment #15)
> > In order to prevent code duplication, I decided to just set mLine to the end
> > iterator
> 
> You did?
> 
> +  mLine = aFrame->begin_lines();
> 
> Looks to me like you need to add mLine = aFrame->end_lines() at the end of the
> "if (cursor)" block,

Well, what I said was technically true, I _decided_ to do that, I just didn't do it! :-)

> and set mLine to begin_lines if !cursor.

Why is that needed?  I don't iterate over mLine if cursor is not null.

Comment 18

[(no longer active)]

Attachment: Part 3: Use the line cursor

Comment 19

[(no longer active)]

Attachment: Part 3: Use the line cursor

Actually, I just realized that I had qrefreshed my changes on another patch in my mq, so the "begin_lines" version didn't include any of my changes, including the "end_lines" fix.  Turns out that I had actually made that change after all.

Comment 20

[(no longer active)]

Attachment: Part 3: Use the line cursor

Arghhh.  Note to self: patch -p1 --dry-run is not really useful for fixing mistakes!

Comment 21

[(no longer active)]

Attachment: Rolled up patch

Comment 22

[(no longer active)]

Attachment: Part 3: Use the line cursor

Actually, the frame's line iterator could be invalid when we try to dereference it, which would abort the program in debug builds.  This version of the patch checks the iterator before setting cursor to its current value to make sure that doesn't happen.

Comment 23

[(no longer active)]

Attachment: Part 3: Use the line cursor

One further correction: we shouldn't return at the end of the for loop iterating over |line| and |rline|, we should fall back to searching the overflow lines, like this:

--- a/layout/generic/nsBlockFrame.cpp
+++ b/layout/generic/nsBlockFrame.cpp
@@ -5092,18 +5092,17 @@ nsBlockInFlowLineIterator::nsBlockInFlow
     // line cursor.
     nsBlockFrame::line_iterator line = aFrame->line(cursor);
     nsBlockFrame::reverse_line_iterator rline = aFrame->rline(cursor);
     nsBlockFrame::line_iterator line_end = aFrame->end_lines();
     nsBlockFrame::reverse_line_iterator rline_end = aFrame->rend_lines();
     for (--rline;;) {
       if (line == line_end && rline == rline_end) {
         // Didn't find the line
-        mLine = line;
-        return;
+        break;
       }
       if (line != line_end) {
         if (line->Contains(child)) {
           *aFoundValidLine = PR_TRUE;
           mLine = line;
           return;
         }
         ++line;

This version of the patch adds the above change.

Comment 24

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

No it doesn't! but r=me with that change.

Comment 25

[(no longer active)]

Attachment: Part 3: Use the line cursor

This time with the actual change included in the patch...

Comment 26

[(no longer active)]

http://hg.mozilla.org/mozilla-central/rev/1e0a9cf6dc53
http://hg.mozilla.org/mozilla-central/rev/251816ad0480
http://hg.mozilla.org/mozilla-central/rev/0f5a2dce1aa5