33668 – WebCore::InsertListCommand::modifyRange infinite loop (100% CPU usage)

Berend-Jan Wever

Reported 2010-01-14 04:08:38 PST

from WebKit›WebCore›editing›InsertListCommand.cpp: bool InsertListCommand::modifyRange() { VisibleSelection selection = selectionForParagraphIteration(endingSelection()); ASSERT(selection.isRange()); VisiblePosition startOfSelection = selection.visibleStart(); VisiblePosition endOfSelection = selection.visibleEnd(); VisiblePosition startOfLastParagraph = startOfParagraph(endOfSelection); if (startOfParagraph(startOfSelection) == startOfLastParagraph) return false; Node* startList = enclosingList(startOfSelection.deepEquivalent().node()); Node* endList = enclosingList(endOfSelection.deepEquivalent().node()); if (!startList || startList != endList) m_forceCreateList = true; setEndingSelection(startOfSelection); doApply(); // Fetch the start of the selection after moving the first paragraph, // because moving the paragraph will invalidate the original start. // We'll use the new start to restore the original selection after // we modified all selected paragraphs. startOfSelection = endingSelection().visibleStart(); VisiblePosition startOfCurrentParagraph = startOfNextParagraph(startOfSelection); while (startOfCurrentParagraph != startOfLastParagraph) { // doApply() may operate on and remove the last paragraph of the selection from the document // if it's in the same list item as startOfCurrentParagraph. Return early to avoid an // infinite loop and because there is no more work to be done. // FIXME(<rdar://problem/5983974>): The endingSelection() may be incorrect here. Compute // the new location of endOfSelection and use it as the end of the new selection. if (!startOfLastParagraph.deepEquivalent().node()->inDocument()) return true; setEndingSelection(startOfCurrentParagraph); doApply(); startOfCurrentParagraph = startOfNextParagraph(endingSelection().visibleStart()); } setEndingSelection(endOfSelection); doApply(); // Fetch the end of the selection, for the reason mentioned above. endOfSelection = endingSelection().visibleEnd(); setEndingSelection(VisibleSelection(startOfSelection, endOfSelection)); m_forceCreateList = false; return true; } The while loop will run forever using this repro: <BODY></BODY> <SCRIPT> document.execCommand("selectall",false,true); document.designMode="on"; document.execCommand("inserthorizontalrule",8); document.execCommand("InsertImage",false,""); document.execCommand("justifyleft",false,1); document.execCommand("insertparagraph",false); document.execCommand("SelectAll",false,undefined); document.execCommand("InsertOrderedList",false,null); </SCRIPT>

Berend-Jan Wever

Comment 1 2010-01-14 04:10:28 PST

Online repro

Ryosuke Niwa

Comment 2 2010-03-21 15:55:02 PDT

This bug seems to be caused in the modifyRange when startOfCurrentParagraph becomes null. The bug reproduces when trying to InsertOrderedList on the following HTML as well: <ul><ul><li>hello</li></ul>world<ol><li>WebKit</li></ol></ul> I could work-around the issue by adding a condition to while but I'm not sure startOfCurrentParagraph should ever be null. Because with that condition, "WebKit" moves before "world", which is obviously wrong behavior. We probably need to cleanup InsertListCommand first as we did in IndentOutdentCommand (filed as bug 36430).

Enrica Casucci

Comment 3 2010-03-22 09:26:25 PDT

Normally this happens when iterating over a range of nodes that has changed (namely nodes have been removed). I fixed a similar issue in IndentOutdentCommand a while ago.

Ryosuke Niwa

Comment 4 2010-03-22 11:36:14 PDT

(In reply to comment #3) > Normally this happens when iterating over a range of nodes that has changed > (namely nodes have been removed). I fixed a similar issue in > IndentOutdentCommand a while ago. Could you point me to the bug/patch or elaborate on how you fixed it?

Enrica Casucci

Comment 5 2010-03-22 11:46:31 PDT

(In reply to comment #4) > (In reply to comment #3) > > Normally this happens when iterating over a range of nodes that has changed > > (namely nodes have been removed). I fixed a similar issue in > > IndentOutdentCommand a while ago. > > Could you point me to the bug/patch or elaborate on how you fixed it? I think this is an example. http://trac.webkit.org/changeset/51704 I'll try to find another one.

Enrica Casucci

Comment 6 2010-03-22 11:48:43 PDT

Here is another one. http://trac.webkit.org/changeset/50536

Ryosuke Niwa

Comment 7 2010-03-22 13:10:01 PDT

(In reply to comment #6) > Here is another one. > http://trac.webkit.org/changeset/50536 Thanks for the reply. So it seems adding isNotNull check to http://trac.webkit.org/browser/trunk/WebCore/editing/InsertListCommand.cpp#L86 will suffice.

Ryosuke Niwa

Comment 8 2010-07-14 11:05:10 PDT

Created attachment 61540 [details] demonstrates the bug (crashes WebKit without a patch)

Ryosuke Niwa

Comment 9 2010-07-14 17:25:57 PDT

Created attachment 61587 [details] fixes the bug

Ryosuke Niwa

Comment 10 2010-07-14 17:32:02 PDT

(In reply to comment #9) > Created an attachment (id=61587) [details] Note that the expected result of this patch does NOT match that of MSIE and Firefox. When intending <ul> <ul><li>hello</li></ul> world <ol><li>WebKit</li></ol> </ul> Both MSIE and Firefox gives <OL> <OL><LI>hello</LI></OL> world <OL><LI>WebKit</LI></OL> </OL> But WebKit gives <ul> <ol><li>hello</li></ol> </ul> <ol> <li>world</li> </ol> <ul> <ol><li>WebKit</li></ol> </ul> I tried really hard to match new behavior to that of Firefox and MSIE but because we are iterating through multiple paragraphs, we cannot tell whether outer ul can be converted to ol or not when encountering "world". (i.e. if the user selected "world" alone, we should certainly not converting the outer ul to ol). One approach to solve this problem is to keep the original selection as a range and check whether outer list is contained within the range but this requires more refactoring and fixing, which was not feasible at this point.

Ryosuke Niwa

Comment 11 2010-07-22 12:30:23 PDT

Comment on attachment 61587 [details] fixes the bug I'm splitting this patch into a cleanup and the actual fix.

Ryosuke Niwa

Comment 12 2010-07-22 20:08:19 PDT

Created attachment 62374 [details] reflects the cleanup done in 42841

Ojan Vafai

Comment 13 2010-07-23 17:15:14 PDT

Comment on attachment 62374 [details] reflects the cleanup done in 42841 I didn't scrutinize the code too closely since the test output doesn't look right to me. > --- LayoutTests/ChangeLog (revision 63943) > + The behavior of WebKit when inserting ordered/unordered list on a list with > + an orphaned nested list at the end (5207369.html) is updated to match that of MSIE instead of Firefox. This doesn't match what I get in IE8. I get: <P>One</P> <P>Two</P> <UL> <LI>Three</LI> <LI>Four</LI></UL> > +++ LayoutTests/editing/execCommand/5207369-expected.txt (working copy) > -<ul><li>One</li><li>Two</li><li>Three</li><li>Four</li></ul> > +<ul><li>One</li><li>Two</li></ul><ol><ul><li>Three</li><li>Four</li></ul></ol> This output doesn't look right to me. Why is the ul wrapped in an ol? FWIW, our current behavior matches Opera. Firefox just inserts and LI at the top (clearly wrong). IE removes the outer list entirely. In either case, this new output doesn't match other browsers and seems worse than the old output. Seems like the ideal behavior, from a user perspective, would be to output something like <ul><li>One</li><li>Two</li><ul><li>Three</li><li>Four</li></ul></ul>. It would be good to try this in Word, TextEdit and WordPad to see what they do in this case. > +++ LayoutTests/editing/execCommand/insert-list-orphaned-item-with-nested-lists.html (revision 0) > +var e = document.getElementById('test') > +var r = document.createRange(); > +var s = window.getSelection(); One letter variable names are frowned upon in webkit code. The one exception is using "e" for the name of an event argument to a function might be OK since it's so common. > +r.setStart(e, 0); > +r.setEnd(e, e.childNodes.length); > +s.removeAllRanges(); > +s.addRange(r); These four lines can just be s.selectAllChildren(e); > +document.execCommand('InsertOrderedList', false, null); > + > +Markup.description("This tests crash when listifying nested lists with an orphaned list child in between (see bug 33668).") Technically, it's an infinite loop, not a crash, right?

Ryosuke Niwa

Comment 14 2010-07-23 22:58:53 PDT

Created attachment 62487 [details] fixed per ojan's comments (In reply to comment #13) > This doesn't match what I get in IE8. I get: > <P>One</P> > <P>Two</P> > <UL> > <LI>Three</LI> > <LI>Four</LI></UL> I think you did InsertOrderedList as supposed to InsertUnorderedList. When I do InsertUnorderedList on MSIE, I get: <ul> <li>one</li> <li>two</li> <ul> <li>three</li> <li>four</li> </ul> </ul> But this is visually identical to <ul> <li>one</li> <li>two</li> </ul> <ol> <ul> <li>three</li> <li>four</li> </ul> </ol> > > +++ LayoutTests/editing/execCommand/5207369-expected.txt (working copy) > > -<ul><li>One</li><li>Two</li><li>Three</li><li>Four</li></ul> > > +<ul><li>One</li><li>Two</li></ul><ol><ul><li>Three</li><li>Four</li></ul></ol> > > This output doesn't look right to me. Why is the ul wrapped in an ol? FWIW, our current behavior matches Opera. Firefox just inserts and LI at the top (clearly wrong). IE removes the outer list entirely. In either case, this new output doesn't match other browsers and seems worse than the old output. Again, I think you did InsertOrderedList. > Seems like the ideal behavior, from a user perspective, would be to output something like <ul><li>One</li><li>Two</li><ul><li>Three</li><li>Four</li></ul></ul>. Right. That's what I'm trying to accomplish here but with our current implementation, we can't tell if the outer list is contained within the selection because we modify the selection. So the best we can do is to leave the outer OL intact. I could add a logic to merge outer lists when the only content of the list is another list. That will produce the above HTML as desired. Ideally, when the entire list is selected, we can convert the type of the list element without having to work on each paragraph separately and then merge. > > +r.setStart(e, 0); > > +r.setEnd(e, e.childNodes.length); > > +s.removeAllRanges(); > > +s.addRange(r); > These four lines can just be s.selectAllChildren(e); Good point. > > +document.execCommand('InsertOrderedList', false, null); > > + > > +Markup.description("This tests crash when listifying nested lists with an orphaned list child in between (see bug 33668).") > Technically, it's an infinite loop, not a crash, right? Right.

Ojan Vafai

Comment 15 2010-07-26 17:01:12 PDT

Comment on attachment 62487 [details] fixed per ojan's comments > I think you did InsertOrderedList as supposed to InsertUnorderedList. When I do InsertUnorderedList on MSIE, I get: > <ul> > <li>one</li> > <li>two</li> > <ul> > <li>three</li> > <li>four</li> > </ul> > </ul> > > But this is visually identical to > <ul> > <li>one</li> > <li>two</li> > </ul> > <ol> > <ul> > <li>three</li> > <li>four</li> > </ul> > </ol> It's only visually identical in the absence of CSS, e.g., <style>ul, ol {border: 1px solid blue}</style> would render an extra border. > Right. That's what I'm trying to accomplish here but with our current implementation, we can't tell if the outer list is contained within the selection because we modify the selection. So the best we can do is to leave the outer OL intact. I could add a logic to merge outer lists when the only content of the list is another list. That will produce the above HTML as desired. Ideally, when the entire list is selected, we can convert the type of the list element without having to work on each paragraph separately and then merge. The old results for this test are clearly wrong and the new results for this test are wrong. But I worry that the new results are more wrong. I don't think you need to make this test match IE in this patch, but is there a way to avoid the infinite loop that doesn't change the results for this test?

Ryosuke Niwa

Comment 16 2010-07-26 18:15:15 PDT

Thanks for reviewing! (In reply to comment #15) > The old results for this test are clearly wrong and the new results for this test are wrong. But I worry that the new results are more wrong. I don't think you need to make this test match IE in this patch, but is there a way to avoid the infinite loop that doesn't change the results for this test? Okay, the real fix for this problem is to save the selection range and if a list is contained within the range, then we convert the entire list. We'll still need to walk through each paragraph after the conversion because inner lists still need to be converted. But I just think that's too much work / backlogging to fix this P1 bug. This would work perfectly well for: <ol> <li>hello</li> <ol> <li>world</li> </ol> <li>webkit</li> </ol> An alternative work-around we can take is to merge the outer list when we've inserted a list child into an inner list, and the outer list solely consists of the inner list. But this is too gross to my taste and won't work for the above case for various reasons. But I don't really see why this is more wrong than the original result. The inner UL was inside the outer OL to begin with. If we had only selected the inner UL, then we'll be only converting the inner list, leaving the outer OL intact. And we always split the list and only convert the parts of lists that are selected. That said, Firefox's behavior of converting all of OLs in the above HTML seems most reasonable to me.

Ryosuke Niwa

Comment 17 2010-07-28 15:08:07 PDT

Created attachment 62883 [details] new attempt I need to split this patch since it contains several fixes but this solves the problem ojan was addressing.

Ojan Vafai

Comment 18 2010-07-28 18:01:50 PDT

Comment on attachment 62883 [details] new attempt > Reviewed by Ojan Vafai. > Index: LayoutTests/editing/execCommand/insert-list-orphaned-item-with-nested-lists-expected.txt > =================================================================== > --- LayoutTests/editing/execCommand/insert-list-orphaned-item-with-nested-lists-expected.txt (revision 0) > +++ LayoutTests/editing/execCommand/insert-list-orphaned-item-with-nested-lists-expected.txt (revision 0) > @@ -0,0 +1,23 @@ > +This tests hang when listifying nested lists with an orphaned list child in between (see bug 33668). > + > +<DIV id="test" contentEditable=""> > +<#text> > +</#text> > +<OL> > +<UL> > +<OL> > +<LI> > +<#text><selection-caret>hello</#text> > +</LI> > +</OL> > +<#text>world</#text> > +<OL> > +<LI> > +<#text>WebKit</#text> > +</LI> > +</OL> > +</UL> > +</OL> > +<#text> > +</#text> > +</DIV> This is OK for now since it's an improvement over the current behavior of hanging. :) Although, it would be more correct if that stray <UL> weren't there, right? > +++ LayoutTests/editing/execCommand/5207369-expected.txt (working copy) > -<ul><li>One</li><li>Two</li><li>Three</li><li>Four</li></ul> > +<ul><li>One</li><li>Two</li><ul><li>Three</li><li>Four</li></ul></ul> Nice! > +++ LayoutTests/editing/execCommand/create-list-from-range-selection-expected.txt (working copy) > @@ -16,6 +16,8 @@ > <LI> > <#text>foo</#text> > </LI> > +</OL> > +<OL> > <LI> > <#text>bar</#text> > </LI> This doesn't look right to me. Does this match what other browsers do? Firefox does something insane with this HTML. But I would expect the following DOM (the nested ordered list would stay nested): <DIV id="test" contentEditable="true"> <OL> <LI> <#text>asd</#text> <SPAN id="start"> <#text>fo<selection-anchor>o</#text> </SPAN> </LI> <LI> <#text>bar</#text> </LI> <LI> <#text>baz</#text> </LI> <LI> <#text>foo</#text> </LI> <OL> <LI> <#text>bar</#text> </LI> </OL> <LI> <#text>ba<selection-focus>z</#text> </LI> </OL> </DIV> Is my expectation wrong? What do Word/PowerPoint do?

Ryosuke Niwa

Comment 19 2010-07-30 01:24:00 PDT

Created attachment 63036 [details] new approach

Darin Adler

Comment 20 2010-07-30 10:20:00 PDT

Comment on attachment 63036 [details] new approach > + ExceptionCode ec = 0; > + if (rangeStartIsInList && newList) > + currentSelection->setStart(newList->parentNode(), newList->nodeIndex(), ec); > + if (rangeEndIsInList && newList) > + currentSelection->setEnd(newList->parentNode(), newList->nodeIndex()+1, ec); There should be spaces around the "+" operator here where we do "+ 1". Since nodeIndex is potentially a O(n^2) operation, I suggest restructuring the code so we compute it only once. On the other hand, if you don't plan to do that optimization, it would be better to use the Range::setStartAfter and Range::setEndBefore functions instead of calling nodeIndex directly here. If you're going to ignore the exception code, there is no need to initialize it to 0. Are all the code changes here covered by this single test?

Ryosuke Niwa

Comment 21 2010-07-30 14:54:43 PDT

Created attachment 63104 [details] fixed various problems. (In reply to comment #20) > (From update of attachment 63036 [details]) > > + ExceptionCode ec = 0; > > + if (rangeStartIsInList && newList) > > + currentSelection->setStart(newList->parentNode(), newList->nodeIndex(), ec); > > + if (rangeEndIsInList && newList) > > + currentSelection->setEnd(newList->parentNode(), newList->nodeIndex()+1, ec); > > There should be spaces around the "+" operator here where we do "+ 1". Modified the approach. Used the positions inside the list instead. > If you're going to ignore the exception code, there is no need to initialize it to 0. Fixed. > Are all the code changes here covered by this single test? When I modified the test to make sure rangeEndIsInList, there were other problems with my code to convert the entire list. So I fixed them all and also this exposed a bug in doApply where endOfSelection / startOfLastParagraph can be orphaned / null. Decided to save indexForVisiblePosition and restore it later. I know it's a dirty trick but because moveParagraphWithClones removes the existing nodes, there is no other way to restore them. I'm really worn away by all sorts of bugs in editing. For example, TextIterator has a bug of not counting empty LI, which causes index to shit by 1. And that's the whole reason, I have that ugly if statement to execute that line only if necessary. But this bug in TextIterator will eventually expose if we added sufficiently more test cases. We need a better of keeping track of positions on nodes that are moved / removed. InsertListCommand / IndentOutdentCommand are very fragile preciously because moveParagraph / moveParagraphWithClones remove some nodes that these two commands are using to iterate through paragraphs.

Eric Seidel (no email)

Comment 22 2010-08-04 10:24:27 PDT

Comment on attachment 63036 [details] new approach Cleared Darin Adler's review+ from obsolete attachment 63036 [details] so that this bug does not appear in http://webkit.org/pending-commit.

Darin Adler

Comment 23 2010-08-24 12:47:49 PDT

Comment on attachment 63104 [details] fixed various problems. > +static Node* enclosingListChild(Node* node, Node* listNode) I think it’s a little confusing that this function is just named enclosingListChild even though it takes the two arguments. A clearer name might help. You didn't add the function, so the name is not your fault. > + // save and restore endOfSelection and startOfLastParagraph when necessary > + // since moveParagraph and movePragraphWithClones can remove nodes. The word "save" here should be capitalized. > + // FIXME: This is very inefficient and expensive operation. A better comment would explain why it's inefficient and why it's not easy to fix or something like that. Just saying it’s inefficient is strange. Doesn’t make clear what the tradeoff is. > + int indexForEndOfSelection = indexForVisiblePosition(endOfSelection); > doApplyForSingleParagraph(forceCreateList, listTag, currentSelection.get()); > + if (endOfSelection.isNull() || endOfSelection.isOrphan() || startOfLastParagraph.isNull() || startOfLastParagraph.isOrphan()) { > + RefPtr<Range> lastSelectionRange = TextIterator::rangeFromLocationAndLength(document()->documentElement(), indexForEndOfSelection, 0, true); > + endOfSelection = lastSelectionRange->startPosition(); > + startOfLastParagraph = startOfParagraph(endOfSelection); > + } This indexForEndOfSelection approach seems weak. It’s a sort of “I give up and can’t figure out any other way to make it work” approach. Not that I have anything better to suggest. As long as we have sufficient test coverage someone can come back and tackle this later I guess. > + // FIXME: moveParagraphWithClones (deleteSelection) does not remove the old list properly > + // See bug 33668 and the test editing/execCommand/insert-list-orphaned-item-with-nested-lists.html This comment is confusing. "Does not remove properly" doesn't tell you what it does. It says what it doesn't do. It would be better if the comment was more specific. It seems impossible for one test to cover all the new code paths here. I'm surprised you added only one test.

Ryosuke Niwa

Comment 24 2010-08-25 15:04:45 PDT

(In reply to comment #23) > (From update of attachment 63104 [details]) > > +static Node* enclosingListChild(Node* node, Node* listNode) > > I think it’s a little confusing that this function is just named enclosingListChild even though it takes the two arguments. A clearer name might help. You didn't add the function, so the name is not your fault. Actually, I'm the one who added that function. It finds the enclosing child of the specified list so I could have named it like enclosignListChildOfList but that seemed rather redundant. But I can change the name if you have a better alternative. > > + // save and restore endOfSelection and startOfLastParagraph when necessary > > + // since moveParagraph and movePragraphWithClones can remove nodes. > > The word "save" here should be capitalized. Will fix. > > + // FIXME: This is very inefficient and expensive operation. > > A better comment would explain why it's inefficient and why it's not easy to fix or something like that. Just saying it’s inefficient is strange. Doesn’t make clear what the tradeoff is. Changed to: This is an inefficient way to keep selection alive because indexForVisiblePosition walks from the beginning of the document to the endOfSelection everytime this code is executed. But not using index is hard because there are so many ways we can lose selection inside doApplyForSingleParagraph. > > + int indexForEndOfSelection = indexForVisiblePosition(endOfSelection); > > doApplyForSingleParagraph(forceCreateList, listTag, currentSelection.get()); > > + if (endOfSelection.isNull() || endOfSelection.isOrphan() || startOfLastParagraph.isNull() || startOfLastParagraph.isOrphan()) { > > + RefPtr<Range> lastSelectionRange = TextIterator::rangeFromLocationAndLength(document()->documentElement(), indexForEndOfSelection, 0, true); > > + endOfSelection = lastSelectionRange->startPosition(); > > + startOfLastParagraph = startOfParagraph(endOfSelection); > > + } > > This indexForEndOfSelection approach seems weak. It’s a sort of “I give up and can’t figure out any other way to make it work” approach. Not that I have anything better to suggest. As long as we have sufficient test coverage someone can come back and tackle this later I guess. It really is "I give up and can't figure out any other way to make it work". I tried many different ways but I can always find a test that crashes after adding 10-20 lines of code everywhere else. Until we invent a better way of iterating through paragraphs, we should stick to this rather inefficient and desperate approach. At least, it prevents us from crashing. > > + // FIXME: moveParagraphWithClones (deleteSelection) does not remove the old list properly > > + // See bug 33668 and the test editing/execCommand/insert-list-orphaned-item-with-nested-lists.html > > This comment is confusing. "Does not remove properly" doesn't tell you what it does. It says what it doesn't do. It would be better if the comment was more specific. Updated to: // Manually remove listNode because moveParagraphWithClones sometimes leaves it behind in the document. // See the bug 33668 and editing/execCommand/insert-list-orphaned-item-with-nested-lists.html. // FIXME: This might be a bug in moveParagraphWithClones or deleteSelection. > It seems impossible for one test to cover all the new code paths here. I'm surprised you added only one test. Fortunately, there are many existing tests that uses new code paths so all new code paths are covered. e.g. removing any line of new code will result in either crash or failure of some tests.

Ryosuke Niwa

Comment 25 2010-08-25 15:16:01 PDT

Committed r66048: <http://trac.webkit.org/changeset/66048>

Attachments
demonstrates the bug (crashes WebKit without a patch) (882 bytes, text/html) 2010-07-14 11:05 PDT, Ryosuke Niwa	no flags	Details
fixes the bug (13.79 KB, patch) 2010-07-14 17:25 PDT, Ryosuke Niwa	no flags	Details Formatted Diff Diff
reflects the cleanup done in 42841 (6.96 KB, patch) 2010-07-22 20:08 PDT, Ryosuke Niwa	ojan: review- ojan: commit-queue-	Details Formatted Diff Diff
fixed per ojan's comments (6.92 KB, patch) 2010-07-23 22:58 PDT, Ryosuke Niwa	ojan: review-	Details Formatted Diff Diff
new attempt (13.20 KB, patch) 2010-07-28 15:08 PDT, Ryosuke Niwa	no flags	Details Formatted Diff Diff
new approach (8.37 KB, patch) 2010-07-30 01:24 PDT, Ryosuke Niwa	no flags	Details Formatted Diff Diff
fixed various problems. (10.26 KB, patch) 2010-07-30 14:54 PDT, Ryosuke Niwa	darin: review+	Details Formatted Diff Diff
Show Obsolete (6) View All Add attachment proposed patch, testcase, etc.