OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import "dart:collection" show LinkedList, LinkedListEntry; | 5 import "dart:collection" show LinkedList, LinkedListEntry; |
6 | 6 |
7 patch class RegExp { | 7 patch class RegExp { |
8 /* patch */ factory RegExp(String source, | 8 /* patch */ factory RegExp(String source, |
9 {bool multiLine: false, | 9 {bool multiLine: false, |
10 bool caseSensitive: true}) { | 10 bool caseSensitive: true}) { |
11 _JSSyntaxRegExpHashKey key = new _JSSyntaxRegExpHashKey( | 11 _RegExpHashKey key = new _RegExpHashKey( |
12 source, multiLine, caseSensitive); | 12 source, multiLine, caseSensitive); |
13 _JSSyntaxRegExpHashValue value = _cache[key]; | 13 _RegExpHashValue value = _cache[key]; |
14 | 14 |
15 if (value == null) { | 15 if (value == null) { |
16 if (_cache.length > _MAX_CACHE_SIZE) { | 16 if (_cache.length > _MAX_CACHE_SIZE) { |
17 _JSSyntaxRegExpHashKey lastKey = _recentlyUsed.last; | 17 _RegExpHashKey lastKey = _recentlyUsed.last; |
18 lastKey.unlink(); | 18 lastKey.unlink(); |
19 _cache.remove(lastKey); | 19 _cache.remove(lastKey); |
20 } | 20 } |
21 | 21 |
22 value = new _JSSyntaxRegExpHashValue( | 22 value = new _RegExpHashValue( |
23 new _JSSyntaxRegExp(source, | 23 new _RegExp(source, |
24 multiLine: multiLine, | 24 multiLine: multiLine, |
25 caseSensitive: caseSensitive), | 25 caseSensitive: caseSensitive), |
26 key); | 26 key); |
27 _cache[key] = value; | 27 _cache[key] = value; |
28 } else { | 28 } else { |
29 value.key.unlink(); | 29 value.key.unlink(); |
30 } | 30 } |
31 | 31 |
32 assert(value != null); | 32 assert(value != null); |
33 | 33 |
34 _recentlyUsed.addFirst(value.key); | 34 _recentlyUsed.addFirst(value.key); |
35 assert(_recentlyUsed.length == _cache.length); | 35 assert(_recentlyUsed.length == _cache.length); |
36 | 36 |
37 // TODO(zerny): We might not want to canonicalize regexp objects. | 37 // TODO(zerny): We might not want to canonicalize regexp objects. |
38 return value.regexp; | 38 return value.regexp; |
39 } | 39 } |
40 | 40 |
41 // Regular expression objects are stored in a cache of up to _MAX_CACHE_SIZE | 41 // Regular expression objects are stored in a cache of up to _MAX_CACHE_SIZE |
42 // elements using an LRU eviction strategy. | 42 // elements using an LRU eviction strategy. |
43 // TODO(zerny): Do not impose a fixed limit on the number of cached objects. | 43 // TODO(zerny): Do not impose a fixed limit on the number of cached objects. |
44 // Other possibilities could be limiting by the size of the regexp objects, | 44 // Other possibilities could be limiting by the size of the regexp objects, |
45 // or imposing a lower time bound for the most recent use under which a regexp | 45 // or imposing a lower time bound for the most recent use under which a regexp |
46 // may not be removed from the cache. | 46 // may not be removed from the cache. |
47 // TODO(zerny): Use self-sizing cache similar to _AccessorCache in | 47 // TODO(zerny): Use self-sizing cache similar to _AccessorCache in |
48 // mirrors_impl.dart. | 48 // mirrors_impl.dart. |
49 static const int _MAX_CACHE_SIZE = 256; | 49 static const int _MAX_CACHE_SIZE = 256; |
50 static final Map<_JSSyntaxRegExpHashKey, _JSSyntaxRegExpHashValue> _cache = | 50 static final Map<_RegExpHashKey, _RegExpHashValue> _cache = |
51 new HashMap<_JSSyntaxRegExpHashKey, _JSSyntaxRegExpHashValue>(); | 51 new HashMap<_RegExpHashKey, _RegExpHashValue>(); |
52 static final LinkedList<_JSSyntaxRegExpHashKey> _recentlyUsed = | 52 static final LinkedList<_RegExpHashKey> _recentlyUsed = |
53 new LinkedList<_JSSyntaxRegExpHashKey>(); | 53 new LinkedList<_RegExpHashKey>(); |
54 } | 54 } |
55 | 55 |
56 | 56 |
57 // Represents both a key in the regular expression cache as well as its | 57 // Represents both a key in the regular expression cache as well as its |
58 // corresponding entry in the LRU list. | 58 // corresponding entry in the LRU list. |
59 class _JSSyntaxRegExpHashKey extends LinkedListEntry<_JSSyntaxRegExpHashKey> { | 59 class _RegExpHashKey extends LinkedListEntry<_RegExpHashKey> { |
60 final String pattern; | 60 final String pattern; |
61 final bool multiLine; | 61 final bool multiLine; |
62 final bool caseSensitive; | 62 final bool caseSensitive; |
63 | 63 |
64 _JSSyntaxRegExpHashKey(this.pattern, this.multiLine, this.caseSensitive); | 64 _RegExpHashKey(this.pattern, this.multiLine, this.caseSensitive); |
65 | 65 |
66 int get hashCode => pattern.hashCode; | 66 int get hashCode => pattern.hashCode; |
67 bool operator==(_JSSyntaxRegExpHashKey that) { | 67 bool operator==(_RegExpHashKey that) { |
68 return (this.pattern == that.pattern) && | 68 return (this.pattern == that.pattern) && |
69 (this.multiLine == that.multiLine) && | 69 (this.multiLine == that.multiLine) && |
70 (this.caseSensitive == that.caseSensitive); | 70 (this.caseSensitive == that.caseSensitive); |
71 } | 71 } |
72 } | 72 } |
73 | 73 |
74 | 74 |
75 // Represents a value in the regular expression cache. Contains a pointer | 75 // Represents a value in the regular expression cache. Contains a pointer |
76 // back to the key in order to access the corresponding LRU entry. | 76 // back to the key in order to access the corresponding LRU entry. |
77 class _JSSyntaxRegExpHashValue { | 77 class _RegExpHashValue { |
78 final _JSSyntaxRegExp regexp; | 78 final _RegExp regexp; |
79 final _JSSyntaxRegExpHashKey key; | 79 final _RegExpHashKey key; |
80 | 80 |
81 _JSSyntaxRegExpHashValue(this.regexp, this.key); | 81 _RegExpHashValue(this.regexp, this.key); |
82 } | 82 } |
83 | 83 |
84 | 84 |
85 class _JSRegExpMatch implements Match { | 85 class _RegExpMatch implements Match { |
86 _JSRegExpMatch(this._regexp, this.input, this._match); | 86 _RegExpMatch(this._regexp, this.input, this._match); |
87 | 87 |
88 int get start => _start(0); | 88 int get start => _start(0); |
89 int get end => _end(0); | 89 int get end => _end(0); |
90 | 90 |
91 int _start(int groupIdx) { | 91 int _start(int groupIdx) { |
92 return _match[(groupIdx * _MATCH_PAIR)]; | 92 return _match[(groupIdx * _MATCH_PAIR)]; |
93 } | 93 } |
94 | 94 |
95 int _end(int groupIdx) { | 95 int _end(int groupIdx) { |
96 return _match[(groupIdx * _MATCH_PAIR) + 1]; | 96 return _match[(groupIdx * _MATCH_PAIR) + 1]; |
(...skipping 28 matching lines...) Expand all Loading... |
125 | 125 |
126 Pattern get pattern => _regexp; | 126 Pattern get pattern => _regexp; |
127 | 127 |
128 final RegExp _regexp; | 128 final RegExp _regexp; |
129 final String input; | 129 final String input; |
130 final List<int> _match; | 130 final List<int> _match; |
131 static const int _MATCH_PAIR = 2; | 131 static const int _MATCH_PAIR = 2; |
132 } | 132 } |
133 | 133 |
134 | 134 |
135 class _JSSyntaxRegExp implements RegExp { | 135 class _RegExp implements RegExp { |
136 factory _JSSyntaxRegExp( | 136 factory _RegExp( |
137 String pattern, | 137 String pattern, |
138 {bool multiLine: false, | 138 {bool multiLine: false, |
139 bool caseSensitive: true}) native "JSSyntaxRegExp_factory"; | 139 bool caseSensitive: true}) native "RegExp_factory"; |
140 | 140 |
141 Match firstMatch(String str) { | 141 Match firstMatch(String str) { |
142 if (str is! String) throw new ArgumentError(str); | 142 if (str is! String) throw new ArgumentError(str); |
143 List match = _ExecuteMatch(str, 0); | 143 List match = _ExecuteMatch(str, 0); |
144 if (match == null) { | 144 if (match == null) { |
145 return null; | 145 return null; |
146 } | 146 } |
147 return new _JSRegExpMatch(this, str, match); | 147 return new _RegExpMatch(this, str, match); |
148 } | 148 } |
149 | 149 |
150 Iterable<Match> allMatches(String string, [int start = 0]) { | 150 Iterable<Match> allMatches(String string, [int start = 0]) { |
151 if (string is! String) throw new ArgumentError(string); | 151 if (string is! String) throw new ArgumentError(string); |
152 if (start is! int) throw new ArgumentError(start); | 152 if (start is! int) throw new ArgumentError(start); |
153 if (0 > start || start > string.length) { | 153 if (0 > start || start > string.length) { |
154 throw new RangeError.range(start, 0, string.length); | 154 throw new RangeError.range(start, 0, string.length); |
155 } | 155 } |
156 return new _AllMatchesIterable(this, string, start); | 156 return new _AllMatchesIterable(this, string, start); |
157 } | 157 } |
158 | 158 |
159 Match matchAsPrefix(String string, [int start = 0]) { | 159 Match matchAsPrefix(String string, [int start = 0]) { |
160 if (string is! String) throw new ArgumentError(string); | 160 if (string is! String) throw new ArgumentError(string); |
161 if (start is! int) throw new ArgumentError(start); | 161 if (start is! int) throw new ArgumentError(start); |
162 if (start < 0 || start > string.length) { | 162 if (start < 0 || start > string.length) { |
163 throw new RangeError.range(start, 0, string.length); | 163 throw new RangeError.range(start, 0, string.length); |
164 } | 164 } |
165 // Inefficient check that searches for a later match too. | 165 // Inefficient check that searches for a later match too. |
166 // Change this when possible. | 166 // Change this when possible. |
167 List<int> list = _ExecuteMatch(string, start); | 167 List<int> list = _ExecuteMatch(string, start); |
168 if (list == null) return null; | 168 if (list == null) return null; |
169 if (list[0] != start) return null; | 169 if (list[0] != start) return null; |
170 return new _JSRegExpMatch(this, string, list); | 170 return new _RegExpMatch(this, string, list); |
171 } | 171 } |
172 | 172 |
173 bool hasMatch(String str) { | 173 bool hasMatch(String str) { |
174 if (str is! String) throw new ArgumentError(str); | 174 if (str is! String) throw new ArgumentError(str); |
175 List match = _ExecuteMatch(str, 0); | 175 List match = _ExecuteMatch(str, 0); |
176 return (match == null) ? false : true; | 176 return (match == null) ? false : true; |
177 } | 177 } |
178 | 178 |
179 String stringMatch(String str) { | 179 String stringMatch(String str) { |
180 if (str is! String) throw new ArgumentError(str); | 180 if (str is! String) throw new ArgumentError(str); |
181 List match = _ExecuteMatch(str, 0); | 181 List match = _ExecuteMatch(str, 0); |
182 if (match == null) { | 182 if (match == null) { |
183 return null; | 183 return null; |
184 } | 184 } |
185 return str._substringUnchecked(match[0], match[1]); | 185 return str._substringUnchecked(match[0], match[1]); |
186 } | 186 } |
187 | 187 |
188 String get pattern native "JSSyntaxRegExp_getPattern"; | 188 String get pattern native "RegExp_getPattern"; |
189 | 189 |
190 bool get isMultiLine native "JSSyntaxRegExp_getIsMultiLine"; | 190 bool get isMultiLine native "RegExp_getIsMultiLine"; |
191 | 191 |
192 bool get isCaseSensitive native "JSSyntaxRegExp_getIsCaseSensitive"; | 192 bool get isCaseSensitive native "RegExp_getIsCaseSensitive"; |
193 | 193 |
194 int get _groupCount native "JSSyntaxRegExp_getGroupCount"; | 194 int get _groupCount native "RegExp_getGroupCount"; |
195 | 195 |
196 // Byte map of one byte characters with a 0xff if the character is a word | 196 // Byte map of one byte characters with a 0xff if the character is a word |
197 // character (digit, letter or underscore) and 0x00 otherwise. | 197 // character (digit, letter or underscore) and 0x00 otherwise. |
198 // Used by generated RegExp code. | 198 // Used by generated RegExp code. |
199 static const List<int> _wordCharacterMap = const <int>[ | 199 static const List<int> _wordCharacterMap = const <int>[ |
200 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 200 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
201 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 201 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
202 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 202 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
203 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 203 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
204 | 204 |
(...skipping 27 matching lines...) Expand all Loading... |
232 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 232 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
233 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 233 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
234 | 234 |
235 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 235 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
236 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 236 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
237 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 237 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
238 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | 238 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, |
239 ]; | 239 ]; |
240 | 240 |
241 List _ExecuteMatch(String str, int start_index) | 241 List _ExecuteMatch(String str, int start_index) |
242 native "JSSyntaxRegExp_ExecuteMatch"; | 242 native "RegExp_ExecuteMatch"; |
243 } | 243 } |
244 | 244 |
245 class _AllMatchesIterable extends IterableBase<Match> { | 245 class _AllMatchesIterable extends IterableBase<Match> { |
246 final _JSSyntaxRegExp _re; | 246 final _RegExp _re; |
247 final String _str; | 247 final String _str; |
248 final int _start; | 248 final int _start; |
249 | 249 |
250 _AllMatchesIterable(this._re, this._str, this._start); | 250 _AllMatchesIterable(this._re, this._str, this._start); |
251 | 251 |
252 Iterator<Match> get iterator => new _AllMatchesIterator(_re, _str, _start); | 252 Iterator<Match> get iterator => new _AllMatchesIterator(_re, _str, _start); |
253 } | 253 } |
254 | 254 |
255 class _AllMatchesIterator implements Iterator<Match> { | 255 class _AllMatchesIterator implements Iterator<Match> { |
256 final String _str; | 256 final String _str; |
257 int _nextIndex; | 257 int _nextIndex; |
258 _JSSyntaxRegExp _re; | 258 _RegExp _re; |
259 Match _current; | 259 Match _current; |
260 | 260 |
261 _AllMatchesIterator(this._re, this._str, this._nextIndex); | 261 _AllMatchesIterator(this._re, this._str, this._nextIndex); |
262 | 262 |
263 Match get current => _current; | 263 Match get current => _current; |
264 | 264 |
265 bool moveNext() { | 265 bool moveNext() { |
266 if (_re == null) return false; // Cleared after a failed match. | 266 if (_re == null) return false; // Cleared after a failed match. |
267 if (_nextIndex <= _str.length) { | 267 if (_nextIndex <= _str.length) { |
268 var match = _re._ExecuteMatch(_str, _nextIndex); | 268 var match = _re._ExecuteMatch(_str, _nextIndex); |
269 if (match != null) { | 269 if (match != null) { |
270 _current = new _JSRegExpMatch(_re, _str, match); | 270 _current = new _RegExpMatch(_re, _str, match); |
271 _nextIndex = _current.end; | 271 _nextIndex = _current.end; |
272 if (_nextIndex == _current.start) { | 272 if (_nextIndex == _current.start) { |
273 // Zero-width match. Advance by one more. | 273 // Zero-width match. Advance by one more. |
274 _nextIndex++; | 274 _nextIndex++; |
275 } | 275 } |
276 return true; | 276 return true; |
277 } | 277 } |
278 } | 278 } |
279 _current = null; | 279 _current = null; |
280 _re = null; | 280 _re = null; |
281 return false; | 281 return false; |
282 } | 282 } |
283 } | 283 } |
OLD | NEW |