Bug 36037 – REGRESSION(51522): typing at the end of a line in designMode documents is *very* slow

• Component: HTML Editing
• Status: RESOLVED FIXED

[Ojan Vafai]

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.

[James Robinson]

I think you forgot to attach the test case.

[Ojan Vafai]

Created attachment 50555 [details]
Test case

I blame bugzilla!

[Ojan Vafai]

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.

[Ojan Vafai]

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.

[Ojan Vafai]

Looks this is a recent regression. http://trac.webkit.org/changeset/51522

[Ojan Vafai]

I confirmed looking at nightlies that the bug doesn't happen at r51490 and does happen at r51559.

[Ojan Vafai]

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.

[Enrica Casucci]

(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.

[Ojan Vafai]

Created attachment 54101 [details]
Patch

[Ojan Vafai]

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.

[Enrica Casucci]

Created attachment 56949 [details]
Patch2

[Enrica Casucci]

Radar bug <rdar://problem/8022887>

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?

[Darin Adler]

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.

[Enrica Casucci]

(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.

[Enrica Casucci]

(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.

[Enrica Casucci]

Committed revision 60176.

[Eric Seidel (no email)]

It seems there are more fixes in attachment 54101 [details] which we should eventually make in PositionIterator.

[Enrica Casucci]

(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.

[Eric Seidel (no email)]

Perhaps we made a mistake when typing up attachment 54101 [details] then.  I am too far removed from context to really comment.

[Ojan Vafai]

(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.

[WebKit Review Bot]

http://trac.webkit.org/changeset/60176 might have broken Tiger Intel Release

[Enrica Casucci]

(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.

[Alexey Proskuryakov]

*** Bug 40165 has been marked as a duplicate of this bug. ***