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

Status: RESOLVED FIXED

(Core :: DOM: Editor, defect)

Description

[Nicolas B. Pierron [:nbp] {away}]

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

Comment 1

[(no longer active)]

This algorithm is horrible, it's O(n^2).  We should be able to do an O(n) algorithm here.

Comment 2

[(no longer active)]

Attachment: Patch (v1)

Comment 3

[(no longer active)]

https://tbpl.mozilla.org/?tree=Try&rev=a24dadea0689

Comment 4

[(no longer active)]

https://tbpl.mozilla.org/?tree=Try&rev=e4ab7d0da5b7
https://tbpl.mozilla.org/?tree=Try&rev=5676b3241d75

Comment 5

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

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.

Comment 6

[(no longer active)]

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

Comment 7

[(no longer active)]

Attachment: Patch (v2)

Comment 8

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

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

Comment 9

[(no longer active)]

Attachment: Patch (v3)

Comment 10

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

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

Comment 11

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

      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;

Comment 12

[(no longer active)]

(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!)

Comment 13

[(no longer active)]

Attachment: Improve the performance of pasting into the location bar by rewriting the O(n^2) algorithm used there to be O(n); r=roc

Comment 14

[(no longer active)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/4c6024d6f725

Comment 15

[(no longer active)]

Backed out, because, we treat warnings as errors :(

https://hg.mozilla.org/integration/mozilla-inbound/rev/fd0f3c10874d

Comment 16

[(no longer active)]

Relanded: http://hg.mozilla.org/integration/mozilla-inbound/rev/f8c84724bacc

Comment 17

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/f8c84724bacc