Pasting in the URL can be extremely expensive (quadratic on the length of the pasted string)

RESOLVED FIXED in mozilla21

Status

()

defect
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: nbp, Assigned: Ehsan)

Tracking

({hang})

unspecified
mozilla21
x86_64
Linux
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [Snappy])

Attachments

(1 attachment, 3 obsolete attachments)

Reporter

Description

6 years ago
I don't know precisely how I managed to produce this error, but this was when I attempt to copy & paste an URL in the URL bar.
The string length sounds wrong, but we can probably guard & warn against such Huge strings to prevent hangs.

(gdb) bt
#0  0x00007ffff6fbb152 in __memmove_ssse3 () from /nix/store/cj7a81wsm1ijwwpkks3725661h3263p5-glibc-2.13/lib/libc.so.6
#1  0x00007ffff3b1446f in nsAString_internal::ReplacePrepInternal (this=0x7fffffff57f0, cutStart=<optimized out>, 
    cutLen=<optimized out>, fragLen=0, newLen=33572283)
    at /home/nicolas/mozilla/mozilla-central/xpcom/string/src/nsTSubstring.cpp:202
#2  0x00007ffff3b149d6 in nsAString_internal::Replace (this=0x7fffffff57f0, cutStart=1189556, cutLength=1, data=0x7ffff53032c0, 
    length=0) at /home/nicolas/mozilla/mozilla-central/xpcom/string/src/nsTSubstring.cpp:484
#3  0x00007ffff34cb703 in nsTextEditRules::HandleNewLines (aString=..., aNewlineHandling=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsTextEditRules.cpp:529
#4  0x00007ffff34cd004 in nsTextEditRules::WillInsertText (this=0x7fffbdffd800, aAction=insertText, aSelection=0x7fffbf484ac0, 
    aCancel=<optimized out>, aHandled=<optimized out>, inString=<optimized out>, outString=0x7fffffff5970, aMaxLength=-1)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsTextEditRules.cpp:631
#5  0x00007ffff34cd3d2 in nsTextEditRules::WillDoAction (this=<optimized out>, aSelection=<optimized out>, aInfo=<optimized out>, 
    aCancel=<optimized out>, aHandled=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsTextEditRules.cpp:236
#6  0x00007ffff34c97c6 in nsPlaintextEditor::InsertText (this=<optimized out>, aStringToInsert=...)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsPlaintextEditor.cpp:720
#7  0x00007ffff34c6e1d in nsPlaintextEditor::InsertTextAt (this=0x7fffbf35f480, aStringToInsert=..., 
    aDestinationNode=<optimized out>, aDestOffset=0, aDoDeleteSelection=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsPlaintextDataTransfer.cpp:99
#8  0x00007ffff34c7195 in nsPlaintextEditor::InsertTextFromTransferable (this=0x7fffbf35f480, aTransferable=<optimized out>, 
    aDestinationNode=0x0, aDestOffset=0, aDoDeleteSelection=true)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsPlaintextDataTransfer.cpp:129
#9  0x00007ffff34c6545 in nsPlaintextEditor::Paste (this=0x7fffbf35f480, aSelectionType=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/editor/libeditor/text/nsPlaintextDataTransfer.cpp:349
#10 0x00007ffff3b0f87a in NS_InvokeByIndex_P (that=<optimized out>, methodIndex=<optimized out>, paramCount=<optimized out>, 
    params=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/xpcom/reflect/xptcall/src/md/unix/xptcinvoke_x86_64_unix.cpp:164
#11 0x00007ffff36c58a4 in Invoke (this=0x7fffffff5ea0)
    at /home/nicolas/mozilla/mozilla-central/js/xpconnect/src/XPCWrappedNative.cpp:3085
#12 Call (this=0x7fffffff5ea0) at /home/nicolas/mozilla/mozilla-central/js/xpconnect/src/XPCWrappedNative.cpp:2419
#13 XPCWrappedNative::CallMethod (ccx=<optimized out>, mode=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/js/xpconnect/src/XPCWrappedNative.cpp:2385
#14 0x00007ffff36c8c7c in XPC_WN_CallMethod (cx=0x7fffd9faecf0, argc=1, vp=<optimized out>)
    at /home/nicolas/mozilla/mozilla-central/js/xpconnect/src/XPCWrappedNativeJSOps.cpp:1488
#15 0x00007ffff4009ade in CallJSNative (args=..., native=<optimized out>, cx=0x7fffd9faecf0)
    at /home/nicolas/mozilla/mozilla-central/js/src/jscntxtinlines.h:373


(gdb) l
515       case nsIPlaintextEditor::eNewlinesStripSurroundingWhitespace:
516         {
517           // find each newline, and strip all the whitespace before
518           // and after it
519           int32_t firstCRLF = aString.FindCharInSet(CRLF);
520           while (firstCRLF >= 0)
521           {
522             uint32_t wsBegin = firstCRLF, wsEnd = firstCRLF + 1;
523             // look backwards for the first non-whitespace char
524             while (wsBegin > 0 && NS_IS_SPACE(aString[wsBegin - 1]))
(gdb) p firstCRLF
$11 = 3593538
(gdb) n
522             uint32_t wsBegin = firstCRLF, wsEnd = firstCRLF + 1;
(gdb) 
524             while (wsBegin > 0 && NS_IS_SPACE(aString[wsBegin - 1]))
(gdb) 
526             while (wsEnd < aString.Length() && NS_IS_SPACE(aString[wsEnd]))
(gdb) 
529             aString.Cut(wsBegin, wsEnd - wsBegin);
(gdb) 
531             firstCRLF = aString.FindCharInSet(CRLF);
(gdb) 
520           while (firstCRLF >= 0)
(gdb) p firstCRLF
$12 = 3593712
(gdb) p aString
$13 = (nsString &) @0x7fffffff57f0: {<nsAString_internal> = {mData = 0x7fff49900008, mLength = 33553993, 
    mFlags = 65541}, <No data fields>}

Found on https://hg.mozilla.org/integration/mozilla-inbound/log/117292
This algorithm is horrible, it's O(n^2).  We should be able to do an O(n) algorithm here.
Summary: Hang in nsTextEditRules::HandleNewLines, case eNewlinesStripSurroundingWhitespace → Pasting in the URL can be extremely expensive (quadratic on the length of the pasted string)
Whiteboard: [Snappy]
Posted patch Patch (v1) (obsolete) — Splinter Review
Assignee: nobody → ehsan
Status: NEW → ASSIGNED
Attachment #702143 - Flags: review?(roc)
Comment on attachment 702143 [details] [diff] [review]
Patch (v1)

Review of attachment 702143 [details] [diff] [review]:
-----------------------------------------------------------------

::: editor/libeditor/text/nsTextEditRules.cpp
@@ -527,5 @@
> -          ++wsEnd;
> -        // now cut this range out of the string
> -        aString.Cut(wsBegin, wsEnd - wsBegin);
> -        // look for another CR or LF
> -        firstCRLF = aString.FindCharInSet(CRLF);

Wouldn't it be much simpler to just start this search at the point where we just cut out the substring?

::: editor/libeditor/text/tests/test_bug830600.html
@@ +79,5 @@
> +                                                  test("\n abc  \n  def \n ", "abcdef", function() {
> +                                                    test(" \n abc  \n  def ", "abcdef ", function() {
> +                                                      test(" abc\n\ndef ", " abcdef ", function() {
> +                                                        test(" abc \n\n def ", " abcdef ", function() {
> +                                                          SimpleTest.finish();

Nice test, but it would look nicer if you just had an array of the values to be tested, instead of this callback nesting of doom.
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #5)
> Comment on attachment 702143 [details] [diff] [review]
> Patch (v1)
> 
> Review of attachment 702143 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: editor/libeditor/text/nsTextEditRules.cpp
> @@ -527,5 @@
> > -          ++wsEnd;
> > -        // now cut this range out of the string
> > -        aString.Cut(wsBegin, wsEnd - wsBegin);
> > -        // look for another CR or LF
> > -        firstCRLF = aString.FindCharInSet(CRLF);
> 
> Wouldn't it be much simpler to just start this search at the point where we
> just cut out the substring?

Hmm, I guess so.  In a pathological case, that would still be O(n^2) but I can do that if you want me to.

> ::: editor/libeditor/text/tests/test_bug830600.html
> @@ +79,5 @@
> > +                                                  test("\n abc  \n  def \n ", "abcdef", function() {
> > +                                                    test(" \n abc  \n  def ", "abcdef ", function() {
> > +                                                      test(" abc\n\ndef ", " abcdef ", function() {
> > +                                                        test(" abc \n\n def ", " abcdef ", function() {
> > +                                                          SimpleTest.finish();
> 
> Nice test, but it would look nicer if you just had an array of the values to
> be tested, instead of this callback nesting of doom.

OK.
Posted patch Patch (v2) (obsolete) — Splinter Review
Attachment #702143 - Attachment is obsolete: true
Attachment #702143 - Flags: review?(roc)
Attachment #702264 - Flags: review?(roc)
(In reply to :Ehsan Akhgari from comment #6)
> Hmm, I guess so.  In a pathological case, that would still be O(n^2) but I
> can do that if you want me to.

Every character in the original string can be scanned by FindCharInSet at most once, and by NS_IS_SPACE at most once.

However it still is O(N^2) because of the repeated Cut()s. Basically if there are K newlines, then we do K Cut()s each one of which may copy O(K) characters on average.

The solution should be simple. Instead of Cut()ing out of the original string, build up a replacement string and append the characters we want to keep into it.
Posted patch Patch (v3) (obsolete) — Splinter Review
Attachment #702264 - Attachment is obsolete: true
Attachment #702264 - Flags: review?(roc)
Attachment #702538 - Flags: review?(roc)
Comment on attachment 702538 [details] [diff] [review]
Patch (v3)

Review of attachment 702538 [details] [diff] [review]:
-----------------------------------------------------------------

This looks a lot more complicated than I think it would be if you followed my suggestion and just copied the text you want to keep into a new string instead of using Cut().

Also, it looks to me like your Cut() loop is still O(N^2).
Attachment #702538 - Flags: review?(roc) → review-
      nsString result;
      int32_t offset = 0;
      while (offset < aString.Length())
      {
        int32_t nextCRLF = aString.FindCharInSet(CRLF, offset);
        if (nextCRLF < 0) {
          result.Append(aString.Substring(offset));
          break;
        }
        uint32_t wsBegin = nextCRLF;
        // look backwards for the first non-whitespace char
        while (wsBegin > offset && NS_IS_SPACE(aString[wsBegin - 1]))
          --wsBegin;
        result.Append(aString.Substring(offset, wsBegin - offset));
        offset = nextCRLF + 1;
        while (offset < aString.Length() && NS_IS_SPACE(aString[offset]))
          ++offset;
      }
      aString = result;
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #11)
>       nsString result;
>       int32_t offset = 0;
>       while (offset < aString.Length())
>       {
>         int32_t nextCRLF = aString.FindCharInSet(CRLF, offset);
>         if (nextCRLF < 0) {
>           result.Append(aString.Substring(offset));
>           break;
>         }
>         uint32_t wsBegin = nextCRLF;
>         // look backwards for the first non-whitespace char
>         while (wsBegin > offset && NS_IS_SPACE(aString[wsBegin - 1]))
>           --wsBegin;
>         result.Append(aString.Substring(offset, wsBegin - offset));
>         offset = nextCRLF + 1;
>         while (offset < aString.Length() && NS_IS_SPACE(aString[offset]))
>           ++offset;
>       }
>       aString = result;

r+ (pretending that it builds out of the box!)
Attachment #702538 - Attachment is obsolete: true
Attachment #702551 - Flags: review?(roc)
Backed out, because, we treat warnings as errors :(

https://hg.mozilla.org/integration/mozilla-inbound/rev/fd0f3c10874d
https://hg.mozilla.org/mozilla-central/rev/f8c84724bacc
Status: ASSIGNED → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla21
You need to log in before you can comment on or make changes to this bug.