#534 bug
Thorbjørn Hermansen

String.sub() with empty pattern makes endless loop

Reported by Thorbjørn Hermansen | February 1st, 2009 @ 07:43 PM | in 1.7

Hello,

As I managed to send in empty pattern in some cases to "hello world".sub("", "Hi") (to my defense - the pattern was not hard coded as empty, but was calculated and in some cases obviously turned out to be a string with length of 0 :-p), the sub() seems to go into an endless loop. I do know that it makes no sense to send in an empty string as pattern, but if some manages to do it, it would be nice to get warning or sub() could return right away with the string untouched or something like that.

Comments and changes to this ticket

  • Tobie Langel

    Tobie Langel February 1st, 2009 @ 11:37 PM

    • Assigned user set to “Tobie Langel”
    • State changed from “new” to “bug”
    • Milestone set to 1.7
  • GitHub Robot

    GitHub Robot February 11th, 2009 @ 03:25 AM

    • State changed from “bug” to “resolved”

    (from [ceb7b72621e1dea71948571da642281c5decf30c]) Avoid String#sub with empty pattern to make endless loop [#534 state:resolved]

    Signed-off-by: Sam Stephenson sam@37signals.com http://github.com/sstephenson/pr...

  • Samuel Lebeau

    Samuel Lebeau February 13th, 2009 @ 03:55 PM

    I'm deeply sorry but unfortunately my patch doesn't fix all cases but only the empty string/regexp case.

    I just made a patch that fixes all cases, like for instance /()/ or /foo|/.

    I'll send a pull request ASAP.

  • Samuel Lebeau

    Samuel Lebeau February 15th, 2009 @ 11:36 PM

    I guess the desired behavior is the Ruby one, example from 1.9 :

    
    "foo bar".gsub(/foo|/, ".")
    # => ".. .b.a.r."
    

    Here a two String#gsub rewrite proposals, which both work as expected :

    
    while (match = source.match(pattern)) {
      result += source.slice(0, match.index);
      result += replacement(match);
      if (match[0].length) {
        source  = source.slice(match.index + match[0].length);
      } else {
        if (!source.length) break;
        result += source.slice(0, 1);
        source  = source.slice(1);
      }
    }
    
    result += source;
    
    
    while (source.length > 0) {
      if (match = source.match(pattern)) {
        result += source.slice(0, match.index);
        result += replacement(match);
        if (match[0].length) {
          source  = source.slice(match.index + match[0].length);
        } else {
          result += source.slice(0, 1);
          source  = source.slice(1);
        }
      } else {
        result += source, source = '';
      }
    }
    
    if (''.match(pattern)) {
      result += replacement('');
    }
    

    Which one do you guys prefer ?

  • Juriy Zaytsev

    Juriy Zaytsev February 16th, 2009 @ 05:57 PM

    I would prefer to use native String.prototype.replace (fixing it for older clients without support for function-as-a-replacement) and simply delegate sub/gsub to it.

    Why perform manual iteration when marginally faster native methods exist?

  • Samuel Lebeau

    Samuel Lebeau February 16th, 2009 @ 10:04 PM

    AFAIK, there is no spec-compliant way to tell String.prototype.replace to perform global substitution other than feeding it with a regexp with the global flag on.

    This mean that, if given pattern is a string or a non-global regexp, we have to compile another regexp from its source, which is a performance penalty too.

    I've done a few benchmarks and it seems worse...

  • Juriy Zaytsev

    Juriy Zaytsev February 16th, 2009 @ 11:31 PM

    Samuel, could you run your version against:

    
    (function(){
      function isGlobal(re, match) {
        return !!/\/(g?)i?m?$/.exec(re)[1];
      }
      String.prototype.gsub2 = function(pattern, replacement) {   
        // if string, construct global regex, replace and return
        if (typeof pattern == 'string') {
          pattern = new RegExp(RegExp.escape(pattern), 'g');
          return this.replace(pattern, replacement);
        }
        // non-string, if global, replace and return
        if (isGlobal(pattern)) {
          return this.replace(pattern, replacement);
        }
        // non-string and non-global, create global regex
        var match = /\/(.*)\//.exec(pattern);
        var re = new RegExp(match ? match[1] : pattern, 'g');
        return this.replace(re, replacement);
      }
    })()
    

    With regex engines becoming much faster in new JS engines, I really wouldn't want to miss on such optimization.

  • Samuel Lebeau

    Samuel Lebeau March 21st, 2009 @ 10:26 AM

    • Title changed from “String.sub() with emtpy pattern makes endless loop” to “String.sub() with empty pattern makes endless loop”

    As String#replace API is slightly different regarding callback arguments, replacement needs to be wrapped to create the match object expected by String#sub|gsub|scan callback.

    The attached patch fixes the empty-matching regexp issue (e.g. /foo|/), the global flag issue and refactors tests for substitution in edge cases.

  • Juriy Zaytsev

    Juriy Zaytsev March 22nd, 2009 @ 03:29 PM

    This still needs fix for String.prototype.replace to support a function replacement (Safari 2.x). Dean has such fix; there are no unit tests, but last time I asked, he said it's used throughout base2 so widely that any error would already be caught

    http://code.google.com/p/base2/s...

  • Samuel Lebeau

    Samuel Lebeau March 29th, 2009 @ 12:13 PM

    Unfortunately, String.prototype.replace from Base2 suffers from the same bug we are trying to fix here (try 'foo bar'.replace(/foo|/g, Prototype.K) for instance).

    I've been trying to fix this in a spec-compliant way on my fork, but Multi-Safari doesn't work anymore on my setup...

    Can someone test it on Safari < 2.0.3 as replaceHandlingReplacementFunction tests pass on other browsers.

    http://github.com/samleb/prototy...

  • Samuel Lebeau

    Samuel Lebeau May 25th, 2009 @ 06:40 PM

    The attached patch consists of two commits:
    * One that fixes replace with a replacement function in a spec-compliant way, and fixes gsub delegating to it. * One that promotes replace instead of gsub internally (especially in Template) to increase performance.

    Still needs test on Safari < 2.0.3, anyone ?

  • Tobie Langel
  • Samuel Lebeau

    Samuel Lebeau May 25th, 2009 @ 08:05 PM

    I know these but they don't work anymore on my computer, showing the spinning disc for hours...
    Are they working on yours?

  • Tobie Langel
  • Samuel Lebeau

    Samuel Lebeau May 26th, 2009 @ 09:37 AM

    OK finally Sebastien Gruhier was able to run tests against Safari < 2.0.3 and tests are passing fine.

    I attached a more atomic patch only fixing String#replace.
    I'll open another ticket for using replace over gsub through the framework.

  • Samuel Lebeau

    Samuel Lebeau June 5th, 2009 @ 04:51 PM

    • State changed from “resolved” to “bug”

    Still buggy in master : try 'foo bar'.sub(/foo|/, Prototype.K).

    As a remainder : my previous patch fixes it.

  • Tobie Langel

    Tobie Langel July 23rd, 2009 @ 03:44 AM

    • State changed from “bug” to “fixed_in_trunk”
    • Milestone changed from 1.7 to 1.6.1
  • Samuel Lebeau

    Samuel Lebeau July 23rd, 2009 @ 11:56 PM

    • Assigned user changed from “Tobie Langel” to “Samuel Lebeau”
    • State changed from “fixed_in_trunk” to “bug”
    • Tag cleared.
    • Milestone changed from 1.6.1 to 1.7

    Unfortunately this is not yet fixed on master (snippet on my above comment still hangs).
    The best way to fix it implies changes in Template.Pattern syntax, which is not desired for 1.6.1.

    Reopening it for 1.7.

  • Samuel Lebeau

    Samuel Lebeau July 24th, 2009 @ 12:01 AM

    • Tag set to needs_patch, needs_tests, string

    Sorry, didn't mean to clear tags...

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 02:26 AM

    • Tag changed from needs_patch, needs_tests, string to missing:tests, needs_patch, string

    [not-tagged:"needs_tests" tagged:"missing:tests" bulk edit command]

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 02:28 AM

    • Tag changed from missing:tests, needs_patch, string to missing:patch, missing:tests, string

    [not-tagged:"needs_patch" tagged:"missing:patch" bulk edit command]

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 03:36 AM

    • Tag changed from missing:patch, missing:tests, string to missing:patch, needs:tests, string

    [not-tagged:"missing:tests" tagged:"needs:tests" bulk edit command]

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 03:37 AM

    • Tag changed from missing:patch, needs:tests, string to needs:patch, needs:tests, string

    [not-tagged:"missing:patch" tagged:"needs:patch" bulk edit command]

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 12:36 PM

    • Tag changed from needs:patch, needs:tests, string to needs:patch, needs:tests
  • T.J. Crowder

    T.J. Crowder November 16th, 2009 @ 04:50 PM

    • Assigned user cleared.

    [responsible:none bulk edit command]

  • Samuel Lebeau

    Samuel Lebeau February 10th, 2010 @ 08:58 PM

    • Tag changed from needs:patch, needs:tests to needs:review
    • Assigned user set to “Juriy Zaytsev”

    As we've dropped Safari < 2.0.4 support, here is the same patch (rewrite String#gsub using String#replace) without the replaceHandlingReplacementFunction cruft.
    As far as I can remember, it significantly boosts both gsub and sub.
    I can take care of updating the documentation accordingly, as regexps with global flags doesn't cause infinite loops anymore, once my documentation branch will be merged in master.

    http://github.com/samleb/prototype/commit/b79f4da4f527fa0b2ce7369b0...

  • Tobie Langel

    Tobie Langel March 1st, 2010 @ 08:37 AM

    • Assigned user changed from “Juriy Zaytsev” to “Samuel Lebeau”
  • Tisho Georgiev

    Tisho Georgiev March 1st, 2010 @ 06:25 PM

    • Tag changed from needs:review to needs:review, section:lang
  • Micah Snyder

    Micah Snyder August 16th, 2012 @ 08:56 PM

    Have there been any updates to this fix? Prototype's unit tests are currently hanging because of an endless loop triggered by this bug in string_test.js.

    For now I've commented out the offending test on my branch, but I wanted to check in on any possible resolution here.

  • Jason Westbrook

Please Sign in or create a free account to add a new ticket.

With your very own profile, you can contribute to projects, track your activity, watch tickets, receive and update tickets through your email and much more.

New-ticket Create new ticket

Create your profile

Help contribute to this project by taking a few moments to create your personal profile. Create your profile »

The Prototype JavaScript library.

Shared Ticket Bins

Referenced by

Pages