Bug 36037 - REGRESSION(51522): typing at the end of a line in designMode documents is *very* slow
Summary: REGRESSION(51522): typing at the end of a line in designMode documents is *ve...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P1 Normal
Assignee: Nobody
URL:
Keywords: GoogleBug, InRadar, Regression
: 40165 (view as bug list)
Depends on:
Blocks:
 
Reported: 2010-03-11 15:46 PST by Ojan Vafai
Modified: 2010-06-05 00:50 PDT (History)
10 users (show)

See Also:


Attachments
Test case (153 bytes, text/html)
2010-03-11 16:00 PST, Ojan Vafai
no flags Details
Patch (4.32 KB, patch)
2010-04-22 15:52 PDT, Ojan Vafai
no flags Details | Formatted Diff | Diff
Patch2 (2.61 KB, patch)
2010-05-24 17:42 PDT, Enrica Casucci
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ojan Vafai 2010-03-11 15:46:30 PST
This affects the script editor in Google Spreadsheets (which uses http://marijn.haverbeke.nl/codemirror/).

Test case attached. Typing a character at the end of the line takes seconds on my machine. The while loop in previousCandidate(const Position& position) in htmlediting.cpp seems to be where all the time is going. Not sure yet what exactly is going wrong.
Comment 1 James Robinson 2010-03-11 15:55:38 PST
I think you forgot to attach the test case.
Comment 2 Ojan Vafai 2010-03-11 16:00:41 PST
Created attachment 50555 [details]
Test case

I blame bugzilla!
Comment 3 Ojan Vafai 2010-03-11 16:50:25 PST
I think the bug is in PositionIterator::isCandidate. Still not sure though. The call to endOfBlock is normally constant-time in the average case, but this is hitting the worst-case where it never finds a candidate, so it loops over every node in the body.

The offending block looks to be:
    if (!m_anchorNode->hasTagName(htmlTag) && renderer->isBlockFlow()) {
        if (toRenderBlock(renderer)->height() || m_anchorNode->hasTagName(bodyTag)) {
            if (!Position::hasRenderedNonAnonymousDescendantsWithHeight(renderer))
                return atStartOfNode() && !Position::nodeIsUserSelectNone(m_anchorNode);
            return m_anchorNode->isContentEditable() && !Position::nodeIsUserSelectNone(m_anchorNode) && Position(*this).atEditingBoundary();
        }
    }

The return statement at the end is wrong I think. This is the case where we're in the body element and it assumes that a position should only be in the body element if we're at an editing boundary (i.e. on the end of a node that's not editable). But this case where all the nodes are children of the body clearly should return true here and doesn't.

Still not sure what the right fix is.
Comment 4 Ojan Vafai 2010-03-11 16:57:04 PST
Actually, I take it back. I misread the code. The problem is definitely that endOfBlock is looping through each node in the body element, still not quite sure where the bug is though.
Comment 5 Ojan Vafai 2010-03-11 17:14:00 PST
Looks this is a recent regression. http://trac.webkit.org/changeset/51522
Comment 6 Ojan Vafai 2010-03-11 17:17:06 PST
I confirmed looking at nightlies that the bug doesn't happen at r51490 and does happen at r51559.
Comment 7 Ojan Vafai 2010-03-11 18:14:44 PST
So, it turns out that without the extra early return added in r51522, we still loop over every node in the body element, but we do so much much faster. It's the call to Position(*this).atEditingBoundary() that takes almost all the time. Not sure what's so slow about it.

Also, it really sucks that we loop over every node in the body element just to find the end of the block. Seems like that should be fixable.
Comment 8 Enrica Casucci 2010-03-12 10:34:16 PST
(In reply to comment #7)
> So, it turns out that without the extra early return added in r51522, we still
> loop over every node in the body element, but we do so much much faster. It's
> the call to Position(*this).atEditingBoundary() that takes almost all the time.
> Not sure what's so slow about it.
> 
> Also, it really sucks that we loop over every node in the body element just to
> find the end of the block. Seems like that should be fixable.

I changed the code to support a scenario that was not covered before. There is not much that can be done in that place if we want to be able to support sophisticated mix of editable and non editable elements and be able to place the caret in empty editable elements.

The right fix is to avoid looping through every node.
Comment 9 Ojan Vafai 2010-04-22 15:52:29 PDT
Created attachment 54101 [details]
Patch
Comment 10 Ojan Vafai 2010-04-22 15:54:21 PDT
Comment on attachment 54101 [details]
Patch

This is a speculative patch that eseidel and I wrote. It makes iterating over positions more correct. We were skipping many positions before.

This does fix the hang, but it causes a number of layout tests to fail. I haven't had time to look into whether they are actual regressions and won't anytime soon. Posting this patch in the hopes that someone else can take it up.
Comment 11 Enrica Casucci 2010-05-24 17:42:05 PDT
Created attachment 56949 [details]
Patch2
Comment 12 Enrica Casucci 2010-05-24 17:57:28 PDT
Radar bug <rdar://problem/8022887>
Comment 13 mitz 2010-05-24 18:06:55 PDT
Comment on attachment 56949 [details]
Patch2

Should you also patch the PositionIterator constructor for consistency so that whenever m_anchorNode has child nodes, m_offsetInAnchor is 0?
Comment 14 Darin Adler 2010-05-25 10:11:49 PDT
Comment on attachment 56949 [details]
Patch2

> +        m_offsetInAnchor = (m_anchorNode->hasChildNodes())? 0: lastOffsetForEditing(m_anchorNode);

Formatting nitpick: Please write it like this:

    m_offsetInAnchor = m_anchorNode->hasChildNodes() ? 0: lastOffsetForEditing(m_anchorNode);

But also, it seems wasteful to call lastOffsetForEditing in a case where we already know the node is non-null and we know that hasChildNodes is false. The special editingIgnoresContent behavior is the main reason we have the lastOffsetForEditing function. If we're not trying to implement that rule, then I think the code above is equivalent to this:

    m_offsetInAnchor = m_anchorNode->offsetInCharacters() ? m_anchorNode->maxCharacterOffset() : 0;

For efficiency we could optimize it like this:

    m_offsetInAnchor = (m_anchorNode->hasChildNodes() || !m_anchorNode->offsetInCharacters()) ? 0 : m_anchorNode->maxCharacterOffset();

I'm not sure which is the best way to write it, but I do think that calling lastOffsetForEditing is a little strange. On the other hand, using it consistently might be clearer from a code readability point of view.

r=me even if you don't agree with my comments. It's OK to just fix the formatting nitpick.
Comment 15 Enrica Casucci 2010-05-25 10:57:47 PDT
(In reply to comment #13)
> (From update of attachment 56949 [details])
> Should you also patch the PositionIterator constructor for consistency so that whenever m_anchorNode has child nodes, m_offsetInAnchor is 0?

I tried that initially, but a lot of tests fail, some crashing too.
Comment 16 Enrica Casucci 2010-05-25 11:08:22 PDT
(In reply to comment #14)
> (From update of attachment 56949 [details])
> > +        m_offsetInAnchor = (m_anchorNode->hasChildNodes())? 0: lastOffsetForEditing(m_anchorNode);
> 
> Formatting nitpick: Please write it like this:
> 
>     m_offsetInAnchor = m_anchorNode->hasChildNodes() ? 0: lastOffsetForEditing(m_anchorNode);
> 
sure, I'll fix it.

> But also, it seems wasteful to call lastOffsetForEditing in a case where we already know the node is non-null and we know that hasChildNodes is false. The special editingIgnoresContent behavior is the main reason we have the lastOffsetForEditing function. If we're not trying to implement that rule, then I think the code above is equivalent to this:
> 
>     m_offsetInAnchor = m_anchorNode->offsetInCharacters() ? m_anchorNode->maxCharacterOffset() : 0;
> 
I agree that we don't need the test on the children, since we know already. but how can we be sure we don't need the editingIgnoresContent behavior?
If you look at the code above this for the case where m_nodeAfterPositionInAnchor is not null, lastOffsetForEditing is used there too. I don't have any reason to believe we can ignore editingIgnoresContent. Could you please explain?
I'll try what you're suggesting and see if it breaks any of the tests.

> For efficiency we could optimize it like this:
> 
>     m_offsetInAnchor = (m_anchorNode->hasChildNodes() || !m_anchorNode->offsetInCharacters()) ? 0 : m_anchorNode->maxCharacterOffset();
> 
> I'm not sure which is the best way to write it, but I do think that calling lastOffsetForEditing is a little strange. On the other hand, using it consistently might be clearer from a code readability point of view.
> 
> r=me even if you don't agree with my comments. It's OK to just fix the formatting nitpick.
Comment 17 Enrica Casucci 2010-05-25 11:21:53 PDT
Committed revision 60176.
Comment 18 Eric Seidel (no email) 2010-05-25 11:33:36 PDT
It seems there are more fixes in attachment 54101 [details] which we should eventually make in PositionIterator.
Comment 19 Enrica Casucci 2010-05-25 11:45:27 PDT
(In reply to comment #18)
> It seems there are more fixes in attachment 54101 [details] which we should eventually make in PositionIterator.

I'm not sure I agree. That patch broke a number of tests and some crashed. The behavior of increment is correct, what was wrong was the behavior of decrement that was causing to iterate over the wrong positions.
I don't think there is anything wrong with the intended behavior of PositionIterator, there was just a bug in the implementation.
Comment 20 Eric Seidel (no email) 2010-05-25 12:00:06 PDT
Perhaps we made a mistake when typing up attachment 54101 [details] then.  I am too far removed from context to really comment.
Comment 21 Ojan Vafai 2010-05-25 12:16:13 PDT
(In reply to comment #19)
> (In reply to comment #18)
> > It seems there are more fixes in attachment 54101 [details] [details] which we should eventually make in PositionIterator.
> 
> I'm not sure I agree. That patch broke a number of tests and some crashed. The behavior of increment is correct, what was wrong was the behavior of decrement that was causing to iterate over the wrong positions.
> I don't think there is anything wrong with the intended behavior of PositionIterator, there was just a bug in the implementation.

PositionIterator should iterate over all possible Positions, right? I don't think increment does currently. It just doesn't happen to hit in this case. The code in attachment 54101 [details] may well have been wrong, but I'm pretty sure the existing increment implementation skips over some positions. Unless you think I'm wrong, I think it deserves a FIXME.
Comment 22 WebKit Review Bot 2010-05-25 12:17:42 PDT
http://trac.webkit.org/changeset/60176 might have broken Tiger Intel Release
Comment 23 Enrica Casucci 2010-05-25 12:29:11 PDT
(In reply to comment #21)
> (In reply to comment #19)
> > (In reply to comment #18)
> > > It seems there are more fixes in attachment 54101 [details] [details] [details] which we should eventually make in PositionIterator.
> > 
> > I'm not sure I agree. That patch broke a number of tests and some crashed. The behavior of increment is correct, what was wrong was the behavior of decrement that was causing to iterate over the wrong positions.
> > I don't think there is anything wrong with the intended behavior of PositionIterator, there was just a bug in the implementation.
> 
> PositionIterator should iterate over all possible Positions, right? I don't think increment does currently. It just doesn't happen to hit in this case. The code in attachment 54101 [details] may well have been wrong, but I'm pretty sure the existing increment implementation skips over some positions. Unless you think I'm wrong, I think it deserves a FIXME.

I'll be happy to look into this while this is still fresh in my mind. Do you have an example of a case where increment skips positions? Keep in mind that m_anchorNode and m_offsetInAnchor only represent the current iterator position. To get the real position we need to use the Position() operator.
Moreover lastOffsetForEditing calls editingIgnoresContent internally to skip some positions on purpose.
Comment 24 Alexey Proskuryakov 2010-06-05 00:50:22 PDT
*** Bug 40165 has been marked as a duplicate of this bug. ***