deps/v8/src/regexp.js

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // This file relies on the fact that the following declaration has been made
   6 // in runtime.js:
   7 // var $Object = global.Object;
   8 // var $Array = global.Array;
   9
  10 var $RegExp = global.RegExp;
  11
  12 // -------------------------------------------------------------------
  13
  14 // A recursive descent parser for Patterns according to the grammar of
  15 // ECMA-262 15.10.1, with deviations noted below.
  16 function DoConstructRegExp(object, pattern, flags) {
  17   // RegExp : Called as constructor; see ECMA-262, section 15.10.4.
  18   if (IS_REGEXP(pattern)) {
  19     if (!IS_UNDEFINED(flags)) {
  20       throw MakeTypeError('regexp_flags', []);
  21     }
  22     flags = (pattern.global ? 'g' : '')
  23         + (pattern.ignoreCase ? 'i' : '')
  24         + (pattern.multiline ? 'm' : '');
  25     if (harmony_unicode_regexps)
  26         flags += (pattern.unicode ? 'u' : '');
  27     if (harmony_regexps)
  28         flags += (pattern.sticky ? 'y' : '');
  29     pattern = pattern.source;
  30   }
  31
  32   pattern = IS_UNDEFINED(pattern) ? '' : ToString(pattern);
  33   flags = IS_UNDEFINED(flags) ? '' : ToString(flags);
  34
  35   %RegExpInitializeAndCompile(object, pattern, flags);
  36 }
  37
  38
  39 function RegExpConstructor(pattern, flags) {
  40   if (%_IsConstructCall()) {
  41     DoConstructRegExp(this, pattern, flags);
  42   } else {
  43     // RegExp : Called as function; see ECMA-262, section 15.10.3.1.
  44     if (IS_REGEXP(pattern) && IS_UNDEFINED(flags)) {
  45       return pattern;
  46     }
  47     return new $RegExp(pattern, flags);
  48   }
  49 }
  50
  51 // Deprecated RegExp.prototype.compile method.  We behave like the constructor
  52 // were called again.  In SpiderMonkey, this method returns the regexp object.
  53 // In JSC, it returns undefined.  For compatibility with JSC, we match their
  54 // behavior.
  55 function RegExpCompileJS(pattern, flags) {
  56   // Both JSC and SpiderMonkey treat a missing pattern argument as the
  57   // empty subject string, and an actual undefined value passed as the
  58   // pattern as the string 'undefined'.  Note that JSC is inconsistent
  59   // here, treating undefined values differently in
  60   // RegExp.prototype.compile and in the constructor, where they are
  61   // the empty string.  For compatibility with JSC, we match their
  62   // behavior.
  63   if (this == $RegExp.prototype) {
  64     // We don't allow recompiling RegExp.prototype.
  65     throw MakeTypeError('incompatible_method_receiver',
  66                         ['RegExp.prototype.compile', this]);
  67   }
  68   if (IS_UNDEFINED(pattern) && %_ArgumentsLength() != 0) {
  69     DoConstructRegExp(this, 'undefined', flags);
  70   } else {
  71     DoConstructRegExp(this, pattern, flags);
  72   }
  73 }
  74
  75
  76 function DoRegExpExec(regexp, string, index) {
  77   var result = %_RegExpExec(regexp, string, index, lastMatchInfo);
  78   if (result !== null) lastMatchInfoOverride = null;
  79   return result;
  80 }
  81
  82
  83 // This is kind of performance sensitive, so we want to avoid unnecessary
  84 // type checks on inputs. But we also don't want to inline it several times
  85 // manually, so we use a macro :-)
  86 macro RETURN_NEW_RESULT_FROM_MATCH_INFO(MATCHINFO, STRING)
  87   var numResults = NUMBER_OF_CAPTURES(MATCHINFO) >> 1;
  88   var start = MATCHINFO[CAPTURE0];
  89   var end = MATCHINFO[CAPTURE1];
  90   // Calculate the substring of the first match before creating the result array
  91   // to avoid an unnecessary write barrier storing the first result.
  92   var first = %_SubString(STRING, start, end);
  93   var result = %_RegExpConstructResult(numResults, start, STRING);
  94   result[0] = first;
  95   if (numResults == 1) return result;
  96   var j = REGEXP_FIRST_CAPTURE + 2;
  97   for (var i = 1; i < numResults; i++) {
  98     start = MATCHINFO[j++];
  99     if (start != -1) {
 100       end = MATCHINFO[j];
 101       result[i] = %_SubString(STRING, start, end);
 102     }
 103     j++;
 104   }
 105   return result;
 106 endmacro
 107
 108
 109 function RegExpExecNoTests(regexp, string, start) {
 110   // Must be called with RegExp, string and positive integer as arguments.
 111   var matchInfo = %_RegExpExec(regexp, string, start, lastMatchInfo);
 112   if (matchInfo !== null) {
 113     lastMatchInfoOverride = null;
 114     RETURN_NEW_RESULT_FROM_MATCH_INFO(matchInfo, string);
 115   }
 116   regexp.lastIndex = 0;
 117   return null;
 118 }
 119
 120
 121 function RegExpExec(string) {
 122   if (!IS_REGEXP(this)) {
 123     throw MakeTypeError('incompatible_method_receiver',
 124                         ['RegExp.prototype.exec', this]);
 125   }
 126
 127   string = TO_STRING_INLINE(string);
 128   var lastIndex = this.lastIndex;
 129
 130   // Conversion is required by the ES5 specification (RegExp.prototype.exec
 131   // algorithm, step 5) even if the value is discarded for non-global RegExps.
 132   var i = TO_INTEGER(lastIndex);
 133
 134   var updateLastIndex = this.global || (harmony_regexps && this.sticky);
 135   if (updateLastIndex) {
 136     if (i < 0 || i > string.length) {
 137       this.lastIndex = 0;
 138       return null;
 139     }
 140   } else {
 141     i = 0;
 142   }
 143
 144   // matchIndices is either null or the lastMatchInfo array.
 145   var matchIndices = %_RegExpExec(this, string, i, lastMatchInfo);
 146
 147   if (IS_NULL(matchIndices)) {
 148     this.lastIndex = 0;
 149     return null;
 150   }
 151
 152   // Successful match.
 153   lastMatchInfoOverride = null;
 154   if (updateLastIndex) {
 155     this.lastIndex = lastMatchInfo[CAPTURE1];
 156   }
 157   RETURN_NEW_RESULT_FROM_MATCH_INFO(matchIndices, string);
 158 }
 159
 160
 161 // One-element cache for the simplified test regexp.
 162 var regexp_key;
 163 var regexp_val;
 164
 165 // Section 15.10.6.3 doesn't actually make sense, but the intention seems to be
 166 // that test is defined in terms of String.prototype.exec. However, it probably
 167 // means the original value of String.prototype.exec, which is what everybody
 168 // else implements.
 169 function RegExpTest(string) {
 170   if (!IS_REGEXP(this)) {
 171     throw MakeTypeError('incompatible_method_receiver',
 172                         ['RegExp.prototype.test', this]);
 173   }
 174   string = TO_STRING_INLINE(string);
 175
 176   var lastIndex = this.lastIndex;
 177
 178   // Conversion is required by the ES5 specification (RegExp.prototype.exec
 179   // algorithm, step 5) even if the value is discarded for non-global RegExps.
 180   var i = TO_INTEGER(lastIndex);
 181
 182   if (this.global || (harmony_regexps && this.sticky)) {
 183     if (i < 0 || i > string.length) {
 184       this.lastIndex = 0;
 185       return false;
 186     }
 187     // matchIndices is either null or the lastMatchInfo array.
 188     var matchIndices = %_RegExpExec(this, string, i, lastMatchInfo);
 189     if (IS_NULL(matchIndices)) {
 190       this.lastIndex = 0;
 191       return false;
 192     }
 193     lastMatchInfoOverride = null;
 194     this.lastIndex = lastMatchInfo[CAPTURE1];
 195     return true;
 196   } else {
 197     // Non-global, non-sticky regexp.
 198     // Remove irrelevant preceeding '.*' in a test regexp.  The expression
 199     // checks whether this.source starts with '.*' and that the third char is
 200     // not a '?'.  But see https://code.google.com/p/v8/issues/detail?id=3560
 201     var regexp = this;
 202     if (regexp.source.length >= 3 &&
 203         %_StringCharCodeAt(regexp.source, 0) == 46 &&  // '.'
 204         %_StringCharCodeAt(regexp.source, 1) == 42 &&  // '*'
 205         %_StringCharCodeAt(regexp.source, 2) != 63) {  // '?'
 206       regexp = TrimRegExp(regexp);
 207     }
 208     // matchIndices is either null or the lastMatchInfo array.
 209     var matchIndices = %_RegExpExec(regexp, string, 0, lastMatchInfo);
 210     if (IS_NULL(matchIndices)) {
 211       this.lastIndex = 0;
 212       return false;
 213     }
 214     lastMatchInfoOverride = null;
 215     return true;
 216   }
 217 }
 218
 219 function TrimRegExp(regexp) {
 220   if (!%_ObjectEquals(regexp_key, regexp)) {
 221     regexp_key = regexp;
 222     regexp_val =
 223       new $RegExp(%_SubString(regexp.source, 2, regexp.source.length),
 224                   (regexp.ignoreCase ? regexp.multiline ? "im" : "i"
 225                                      : regexp.multiline ? "m" : ""));
 226   }
 227   return regexp_val;
 228 }
 229
 230
 231 function RegExpToString() {
 232   if (!IS_REGEXP(this)) {
 233     throw MakeTypeError('incompatible_method_receiver',
 234                         ['RegExp.prototype.toString', this]);
 235   }
 236   var result = '/' + this.source + '/';
 237   if (this.global) result += 'g';
 238   if (this.ignoreCase) result += 'i';
 239   if (this.multiline) result += 'm';
 240   if (harmony_unicode_regexps && this.unicode) result += 'u';
 241   if (harmony_regexps && this.sticky) result += 'y';
 242   return result;
 243 }
 244
 245
 246 // Getters for the static properties lastMatch, lastParen, leftContext, and
 247 // rightContext of the RegExp constructor.  The properties are computed based
 248 // on the captures array of the last successful match and the subject string
 249 // of the last successful match.
 250 function RegExpGetLastMatch() {
 251   if (lastMatchInfoOverride !== null) {
 252     return OVERRIDE_MATCH(lastMatchInfoOverride);
 253   }
 254   var regExpSubject = LAST_SUBJECT(lastMatchInfo);
 255   return %_SubString(regExpSubject,
 256                      lastMatchInfo[CAPTURE0],
 257                      lastMatchInfo[CAPTURE1]);
 258 }
 259
 260
 261 function RegExpGetLastParen() {
 262   if (lastMatchInfoOverride) {
 263     var override = lastMatchInfoOverride;
 264     if (override.length <= 3) return '';
 265     return override[override.length - 3];
 266   }
 267   var length = NUMBER_OF_CAPTURES(lastMatchInfo);
 268   if (length <= 2) return '';  // There were no captures.
 269   // We match the SpiderMonkey behavior: return the substring defined by the
 270   // last pair (after the first pair) of elements of the capture array even if
 271   // it is empty.
 272   var regExpSubject = LAST_SUBJECT(lastMatchInfo);
 273   var start = lastMatchInfo[CAPTURE(length - 2)];
 274   var end = lastMatchInfo[CAPTURE(length - 1)];
 275   if (start != -1 && end != -1) {
 276     return %_SubString(regExpSubject, start, end);
 277   }
 278   return "";
 279 }
 280
 281
 282 function RegExpGetLeftContext() {
 283   var start_index;
 284   var subject;
 285   if (!lastMatchInfoOverride) {
 286     start_index = lastMatchInfo[CAPTURE0];
 287     subject = LAST_SUBJECT(lastMatchInfo);
 288   } else {
 289     var override = lastMatchInfoOverride;
 290     start_index = OVERRIDE_POS(override);
 291     subject = OVERRIDE_SUBJECT(override);
 292   }
 293   return %_SubString(subject, 0, start_index);
 294 }
 295
 296
 297 function RegExpGetRightContext() {
 298   var start_index;
 299   var subject;
 300   if (!lastMatchInfoOverride) {
 301     start_index = lastMatchInfo[CAPTURE1];
 302     subject = LAST_SUBJECT(lastMatchInfo);
 303   } else {
 304     var override = lastMatchInfoOverride;
 305     subject = OVERRIDE_SUBJECT(override);
 306     var match = OVERRIDE_MATCH(override);
 307     start_index = OVERRIDE_POS(override) + match.length;
 308   }
 309   return %_SubString(subject, start_index, subject.length);
 310 }
 311
 312
 313 // The properties $1..$9 are the first nine capturing substrings of the last
 314 // successful match, or ''.  The function RegExpMakeCaptureGetter will be
 315 // called with indices from 1 to 9.
 316 function RegExpMakeCaptureGetter(n) {
 317   return function() {
 318     if (lastMatchInfoOverride) {
 319       if (n < lastMatchInfoOverride.length - 2) {
 320         return OVERRIDE_CAPTURE(lastMatchInfoOverride, n);
 321       }
 322       return '';
 323     }
 324     var index = n * 2;
 325     if (index >= NUMBER_OF_CAPTURES(lastMatchInfo)) return '';
 326     var matchStart = lastMatchInfo[CAPTURE(index)];
 327     var matchEnd = lastMatchInfo[CAPTURE(index + 1)];
 328     if (matchStart == -1 || matchEnd == -1) return '';
 329     return %_SubString(LAST_SUBJECT(lastMatchInfo), matchStart, matchEnd);
 330   };
 331 }
 332
 333
 334 // Property of the builtins object for recording the result of the last
 335 // regexp match.  The property lastMatchInfo includes the matchIndices
 336 // array of the last successful regexp match (an array of start/end index
 337 // pairs for the match and all the captured substrings), the invariant is
 338 // that there are at least two capture indeces.  The array also contains
 339 // the subject string for the last successful match.
 340 var lastMatchInfo = new InternalPackedArray(
 341     2,                 // REGEXP_NUMBER_OF_CAPTURES
 342     "",                // Last subject.
 343     UNDEFINED,         // Last input - settable with RegExpSetInput.
 344     0,                 // REGEXP_FIRST_CAPTURE + 0
 345     0                  // REGEXP_FIRST_CAPTURE + 1
 346 );
 347
 348 // Override last match info with an array of actual substrings.
 349 // Used internally by replace regexp with function.
 350 // The array has the format of an "apply" argument for a replacement
 351 // function.
 352 var lastMatchInfoOverride = null;
 353
 354 // -------------------------------------------------------------------
 355
 356 function SetUpRegExp() {
 357   %CheckIsBootstrapping();
 358   %FunctionSetInstanceClassName($RegExp, 'RegExp');
 359   %AddNamedProperty($RegExp.prototype, 'constructor', $RegExp, DONT_ENUM);
 360   %SetCode($RegExp, RegExpConstructor);
 361
 362   InstallFunctions($RegExp.prototype, DONT_ENUM, $Array(
 363     "exec", RegExpExec,
 364     "test", RegExpTest,
 365     "toString", RegExpToString,
 366     "compile", RegExpCompileJS
 367   ));
 368
 369   // The length of compile is 1 in SpiderMonkey.
 370   %FunctionSetLength($RegExp.prototype.compile, 1);
 371
 372   // The properties `input` and `$_` are aliases for each other.  When this
 373   // value is set the value it is set to is coerced to a string.
 374   // Getter and setter for the input.
 375   var RegExpGetInput = function() {
 376     var regExpInput = LAST_INPUT(lastMatchInfo);
 377     return IS_UNDEFINED(regExpInput) ? "" : regExpInput;
 378   };
 379   var RegExpSetInput = function(string) {
 380     LAST_INPUT(lastMatchInfo) = ToString(string);
 381   };
 382
 383   %OptimizeObjectForAddingMultipleProperties($RegExp, 22);
 384   %DefineAccessorPropertyUnchecked($RegExp, 'input', RegExpGetInput,
 385                                    RegExpSetInput, DONT_DELETE);
 386   %DefineAccessorPropertyUnchecked($RegExp, '$_', RegExpGetInput,
 387                                    RegExpSetInput, DONT_ENUM | DONT_DELETE);
 388
 389   // The properties multiline and $* are aliases for each other.  When this
 390   // value is set in SpiderMonkey, the value it is set to is coerced to a
 391   // boolean.  We mimic that behavior with a slight difference: in SpiderMonkey
 392   // the value of the expression 'RegExp.multiline = null' (for instance) is the
 393   // boolean false (i.e., the value after coercion), while in V8 it is the value
 394   // null (i.e., the value before coercion).
 395
 396   // Getter and setter for multiline.
 397   var multiline = false;
 398   var RegExpGetMultiline = function() { return multiline; };
 399   var RegExpSetMultiline = function(flag) { multiline = flag ? true : false; };
 400
 401   %DefineAccessorPropertyUnchecked($RegExp, 'multiline', RegExpGetMultiline,
 402                                    RegExpSetMultiline, DONT_DELETE);
 403   %DefineAccessorPropertyUnchecked($RegExp, '$*', RegExpGetMultiline,
 404                                    RegExpSetMultiline,
 405                                    DONT_ENUM | DONT_DELETE);
 406
 407
 408   var NoOpSetter = function(ignored) {};
 409
 410
 411   // Static properties set by a successful match.
 412   %DefineAccessorPropertyUnchecked($RegExp, 'lastMatch', RegExpGetLastMatch,
 413                                    NoOpSetter, DONT_DELETE);
 414   %DefineAccessorPropertyUnchecked($RegExp, '$&', RegExpGetLastMatch,
 415                                    NoOpSetter, DONT_ENUM | DONT_DELETE);
 416   %DefineAccessorPropertyUnchecked($RegExp, 'lastParen', RegExpGetLastParen,
 417                                    NoOpSetter, DONT_DELETE);
 418   %DefineAccessorPropertyUnchecked($RegExp, '$+', RegExpGetLastParen,
 419                                    NoOpSetter, DONT_ENUM | DONT_DELETE);
 420   %DefineAccessorPropertyUnchecked($RegExp, 'leftContext',
 421                                    RegExpGetLeftContext, NoOpSetter,
 422                                    DONT_DELETE);
 423   %DefineAccessorPropertyUnchecked($RegExp, '$`', RegExpGetLeftContext,
 424                                    NoOpSetter, DONT_ENUM | DONT_DELETE);
 425   %DefineAccessorPropertyUnchecked($RegExp, 'rightContext',
 426                                    RegExpGetRightContext, NoOpSetter,
 427                                    DONT_DELETE);
 428   %DefineAccessorPropertyUnchecked($RegExp, "$'", RegExpGetRightContext,
 429                                    NoOpSetter, DONT_ENUM | DONT_DELETE);
 430
 431   for (var i = 1; i < 10; ++i) {
 432     %DefineAccessorPropertyUnchecked($RegExp, '$' + i,
 433                                      RegExpMakeCaptureGetter(i), NoOpSetter,
 434                                      DONT_DELETE);
 435   }
 436   %ToFastProperties($RegExp);
 437 }
 438
 439 SetUpRegExp();