Port and integrate the irregexp engine from V8

runtime/lib/regexp_patch.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
+import "dart:collection" show LinkedList, LinkedListEntry;
+
 patch class RegExp {
   /* patch */ factory RegExp(String source,
                              {bool multiLine: false,
                               bool caseSensitive: true}) {
-    return new _JSSyntaxRegExp(source,
-                               multiLine: multiLine,
-                               caseSensitive: caseSensitive);
+    _JSSyntaxRegExpHashKey key = new _JSSyntaxRegExpHashKey(
+        source, multiLine, caseSensitive);
+    _JSSyntaxRegExpHashValue value = _cache[key];
+
+    if (value == null) {
+      if (_cache.length > _MAX_CACHE_SIZE) {
+        _JSSyntaxRegExpHashKey lastKey = _leastRecentlyUsed.last;
+        lastKey.unlink();
+        _cache.remove(lastKey);
+      }
+
+      value = new _JSSyntaxRegExpHashValue(
+          new _JSSyntaxRegExp(source,
+                              multiLine: multiLine,
+                              caseSensitive: caseSensitive),
+          key);
+      _cache[key] = value;
+    } else {
+      value.key.unlink();
+    }
+
+    assert(value != null);
+
+    _leastRecentlyUsed.addFirst(value.key);
+    assert(_leastRecentlyUsed.length == _cache.length);
+
+    return value.regexp;

[Vyacheslav Egorov (Google), 2014/10/01 20:13:21]

Please add TODO here that we might not want to "cannonicalize" regexp objects
themselves like that.

[jgruber1, 2014/10/03 18:59:52]

Done.

+  }
+
+  // Regular expression objects are stored in a cache of up to _MAX_CACHE_SIZE
+  // elements using an LRU eviction strategy.
+  // TODO(jgruber): Do not impose a fixed limit on the number of cached objects.
+  // Other possibilities could be limiting by the size of the regexp objects,
+  // or imposing a lower time bound for the most recent use under which a regexp
+  // may not be removed from the cache.
+  static const int _MAX_CACHE_SIZE = 256;
+  static final Map<_JSSyntaxRegExpHashKey, _JSSyntaxRegExp> _cache =
+      <_JSSyntaxRegExpHashKey, _JSSyntaxRegExpValue>{ };
+  static final LinkedList<_JSSyntaxRegExpHashKey> _leastRecentlyUsed =
+      new LinkedList<_JSSyntaxRegExpHashKey>();
+}
+
+
+// Represents both a key in the regular expression cache as well as its
+// corresponding entry in the LRU list.
+class _JSSyntaxRegExpHashKey extends LinkedListEntry<_JSSyntaxRegExpHashKey> {
+  final String pattern;
+  final bool multiLine;
+  final bool caseSensitive;
+
+  _JSSyntaxRegExpHashKey(this.pattern, this.multiLine, this.caseSensitive);
+
+  int get hashCode => pattern.hashCode;
+  bool operator==(_JSSyntaxRegExpHashKey that) {
+    return (pattern == that.pattern) &&

[Vyacheslav Egorov (Google), 2014/10/01 20:13:21]

this.pattern for consistency, or remove this. everywhere in this method

[jgruber1, 2014/10/03 18:59:52]

Done.

+           (this.multiLine == that.multiLine) &&
+           (this.caseSensitive == that.caseSensitive);
   }
 }
 
+
+// Represents a value in the regular expression cache. Contains a pointer
+// back to the key in order to access the corresponding LRU entry.
+class _JSSyntaxRegExpHashValue {
+  final _JSSyntaxRegExp regexp;
+  final _JSSyntaxRegExpHashKey key;
+
+  _JSSyntaxRegExpHashValue(this.regexp, this.key);
+}
+
+
 class _JSRegExpMatch implements Match {
   _JSRegExpMatch(this._regexp, this.input, this._match);
 
   int get start => _start(0);
   int get end => _end(0);
 
   int _start(int groupIdx) {
     return _match[(groupIdx * _MATCH_PAIR)];
   }
 
@@ skipping 37 matching lines @@
 }
 
 
 class _JSSyntaxRegExp implements RegExp {
   factory _JSSyntaxRegExp(
       String pattern,
       {bool multiLine: false,
        bool caseSensitive: true}) native "JSSyntaxRegExp_factory";
 
   Match firstMatch(String str) {
+    if (str is! String) throw new ArgumentError(str);
     List match = _ExecuteMatch(str, 0);
     if (match == null) {
       return null;
     }
     return new _JSRegExpMatch(this, str, match);
   }
 
   Iterable<Match> allMatches(String string, [int start = 0]) {
     if (string is! String) throw new ArgumentError(string);
     if (start is! int) throw new ArgumentError(start);
     if (0 > start || start > string.length) {
       throw new RangeError.range(start, 0, string.length);
     }
     return new _AllMatchesIterable(this, string, start);
   }
 
   Match matchAsPrefix(String string, [int start = 0]) {
+    if (string is! String) throw new ArgumentError(string);
+    if (start is! int) throw new ArgumentError(start);
     if (start < 0 || start > string.length) {
       throw new RangeError.range(start, 0, string.length);
     }
     // Inefficient check that searches for a later match too.
     // Change this when possible.
     List<int> list = _ExecuteMatch(string, start);
     if (list == null) return null;
     if (list[0] != start) return null;
     return new _JSRegExpMatch(this, string, list);
   }
 
   bool hasMatch(String str) {
+    if (str is! String) throw new ArgumentError(str);
     List match = _ExecuteMatch(str, 0);
     return (match == null) ? false : true;
   }
 
   String stringMatch(String str) {
+    if (str is! String) throw new ArgumentError(str);
     List match = _ExecuteMatch(str, 0);
     if (match == null) {
       return null;
     }
     return str._substringUnchecked(match[0], match[1]);
   }
 
   String get pattern native "JSSyntaxRegExp_getPattern";
 
   bool get isMultiLine native "JSSyntaxRegExp_getIsMultiLine";
 
   bool get isCaseSensitive native "JSSyntaxRegExp_getIsCaseSensitive";
 
   int get _groupCount native "JSSyntaxRegExp_getGroupCount";
 
+  // Byte map of one byte characters with a 0xff if the character is a word
+  // character (digit, letter or underscore) and 0x00 otherwise.
+  // Used by generated RegExp code.
+  static const List<int> _wordCharacterMap = const <int>[
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // '0' - '7'
+    0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // '8' - '9'
+
+    0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // 'A' - 'G'
+    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // 'H' - 'O'
+    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // 'P' - 'W'
+    0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xff,  // 'X' - 'Z', '_'
+
+    0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // 'a' - 'g'
+    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // 'h' - 'o'
+    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  // 'p' - 'w'
+    0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,  // 'x' - 'z'
+    // Latin-1 range
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  ];
+
   List _ExecuteMatch(String str, int start_index)
       native "JSSyntaxRegExp_ExecuteMatch";
 }
 
 class _AllMatchesIterable extends IterableBase<Match> {
   final _JSSyntaxRegExp _re;
   final String _str;
   final int _start;
 
   _AllMatchesIterable(this._re, this._str, this._start);
@@ skipping 23 matching lines @@
           _nextIndex++;
         }
         return true;
       }
     }
     _current = null;
     _re = null;
     return false;
   }
 }