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