1659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.org// Copyright 2012 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#ifndef V8_JSREGEXP_H_ 643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#define V8_JSREGEXP_H_ 743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 8196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/allocation.h" 9196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/assembler.h" 10196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/zone-inl.h" 119d58c2b1c27d8b2890b9bd46e57d3842b09e0292christian.plesner.hansen@gmail.com 1271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace v8 { 1371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace internal { 1443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 15659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.orgclass NodeVisitor; 16659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.orgclass RegExpCompiler; 17a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass RegExpMacroAssembler; 18659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.orgclass RegExpNode; 19659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.orgclass RegExpTree; 20ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.comclass BoyerMooreLookahead; 21a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 2243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenclass RegExpImpl { 2343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen public: 2468ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.org // Whether V8 is compiled with native regexp support or not. 2568ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.org static bool UsesNativeRegExp() { 26c9c80823e038328f2e1060d7feef0762a50adf06ricow@chromium.org#ifdef V8_INTERPRETED_REGEXP 2768ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.org return false; 28c9c80823e038328f2e1060d7feef0762a50adf06ricow@chromium.org#else 29c9c80823e038328f2e1060d7feef0762a50adf06ricow@chromium.org return true; 30bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org#endif 31bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org } 3268ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.org 3343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Creates a regular expression literal in the old space. 3443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // This function calls the garbage collector if necessary. 352ebef182c49d59eba907b120c3c2a50808bd1f12machenbach@chromium.org MUST_USE_RESULT static MaybeHandle<Object> CreateRegExpLiteral( 362ebef182c49d59eba907b120c3c2a50808bd1f12machenbach@chromium.org Handle<JSFunction> constructor, 372ebef182c49d59eba907b120c3c2a50808bd1f12machenbach@chromium.org Handle<String> pattern, 382ebef182c49d59eba907b120c3c2a50808bd1f12machenbach@chromium.org Handle<String> flags); 3943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 4043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Returns a string representation of a regular expression. 4143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Implements RegExp.prototype.toString, see ECMA-262 section 15.10.6.4. 4243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // This function calls the garbage collector if necessary. 4343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen static Handle<String> ToString(Handle<Object> value); 4443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 458bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org // Parses the RegExp pattern and prepares the JSRegExp object with 468bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org // generic data and choice of implementation - as well as what 478bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org // the implementation wants to store in the data field. 487be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // Returns false if compilation fails. 498496027a525ad457b6d5729faf41f29100a27264machenbach@chromium.org MUST_USE_RESULT static MaybeHandle<Object> Compile( 508496027a525ad457b6d5729faf41f29100a27264machenbach@chromium.org Handle<JSRegExp> re, 518496027a525ad457b6d5729faf41f29100a27264machenbach@chromium.org Handle<String> pattern, 528496027a525ad457b6d5729faf41f29100a27264machenbach@chromium.org Handle<String> flags); 5343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 5443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // See ECMA-262 section 15.10.6.2. 5543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // This function calls the garbage collector if necessary. 56a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org MUST_USE_RESULT static MaybeHandle<Object> Exec( 57a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org Handle<JSRegExp> regexp, 58a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org Handle<String> subject, 59a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org int index, 60a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org Handle<JSArray> lastMatchInfo); 6143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 628bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org // Prepares a JSRegExp object with Irregexp-specific data. 63cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org static void IrregexpInitialize(Handle<JSRegExp> re, 64cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org Handle<String> pattern, 65cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org JSRegExp::Flags flags, 66cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org int capture_register_count); 67a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 68a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 697be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static void AtomCompile(Handle<JSRegExp> re, 707be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org Handle<String> pattern, 717be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org JSRegExp::Flags flags, 727be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org Handle<String> match_pattern); 737be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 74355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 75355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org static int AtomExecRaw(Handle<JSRegExp> regexp, 76355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org Handle<String> subject, 77355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int index, 78355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int32_t* output, 79355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int output_size); 80355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 81355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 8241044eb0969b0d7d5c041a077519a36efa6aff27kasperl@chromium.org static Handle<Object> AtomExec(Handle<JSRegExp> regexp, 8341044eb0969b0d7d5c041a077519a36efa6aff27kasperl@chromium.org Handle<String> subject, 847be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org int index, 857be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org Handle<JSArray> lastMatchInfo); 8641044eb0969b0d7d5c041a077519a36efa6aff27kasperl@chromium.org 87cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org enum IrregexpResult { RE_FAILURE = 0, RE_SUCCESS = 1, RE_EXCEPTION = -1 }; 88cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 89cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // Prepare a RegExp for being executed one or more times (using 90cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // IrregexpExecOnce) on the subject. 91cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // This ensures that the regexp is compiled for the subject, and that 92cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // the subject is flat. 93cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // Returns the number of integer spaces required by IrregexpExecOnce 94355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // as its "registers" argument. If the regexp cannot be compiled, 95cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // an exception is set as pending, and this function returns negative. 96cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org static int IrregexpPrepare(Handle<JSRegExp> regexp, 975a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org Handle<String> subject); 98cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 9915613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org // Execute a regular expression on the subject, starting from index. 10015613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org // If matching succeeds, return the number of matches. This can be larger 10115613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org // than one in the case of global regular expressions. 10215613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org // The captures and subcaptures are stored into the registers vector. 103cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // If matching fails, returns RE_FAILURE. 104cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // If execution fails, sets a pending exception and returns RE_EXCEPTION. 10515613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org static int IrregexpExecRaw(Handle<JSRegExp> regexp, 10615613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org Handle<String> subject, 10715613d0b07bac19e341905ff374c930420b3b9c8mstarzinger@chromium.org int index, 108355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int32_t* output, 109355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int output_size); 110cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 111a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // Execute an Irregexp bytecode pattern. 11241826e77311db718135ef6517b846933dfd275f3ager@chromium.org // On a successful match, the result is a JSArray containing 113355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // captured positions. On a failure, the result is the null value. 11441826e77311db718135ef6517b846933dfd275f3ager@chromium.org // Returns an empty handle in case of an exception. 115a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org MUST_USE_RESULT static MaybeHandle<Object> IrregexpExec( 116a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org Handle<JSRegExp> regexp, 117a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org Handle<String> subject, 118a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org int index, 119a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org Handle<JSArray> lastMatchInfo); 120a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 121355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // Set last match info. If match is NULL, then setting captures is omitted. 122355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org static Handle<JSArray> SetLastMatchInfo(Handle<JSArray> last_match_info, 123355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org Handle<String> subject, 124355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int capture_count, 125355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int32_t* match); 126355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 127355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 128355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org class GlobalCache { 129355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org public: 130355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org GlobalCache(Handle<JSRegExp> regexp, 131355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org Handle<String> subject, 132355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org bool is_global, 133355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org Isolate* isolate); 134355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 1352f0efdebb142c00de6950453b4c2df20ceb8df6emmassi@chromium.org INLINE(~GlobalCache()); 136355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 137355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // Fetch the next entry in the cache for global regexp match results. 138355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // This does not set the last match info. Upon failure, NULL is returned. 139355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // The cause can be checked with Result(). The previous 140355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // result is still in available in memory when a failure happens. 1412f0efdebb142c00de6950453b4c2df20ceb8df6emmassi@chromium.org INLINE(int32_t* FetchNext()); 142355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 1432f0efdebb142c00de6950453b4c2df20ceb8df6emmassi@chromium.org INLINE(int32_t* LastSuccessfulMatch()); 144355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 1452f0efdebb142c00de6950453b4c2df20ceb8df6emmassi@chromium.org INLINE(bool HasException()) { return num_matches_ < 0; } 146355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 147355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org private: 148355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int num_matches_; 149355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int max_matches_; 150355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int current_match_index_; 151355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int registers_per_match_; 152355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org // Pointer to the last set of captures. 153355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int32_t* register_array_; 154355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org int register_array_size_; 155355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org Handle<JSRegExp> regexp_; 156355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org Handle<String> subject_; 157355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org }; 158355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 159355cfd19c23ac613f2738a40e356ea48297f7d5eyangguo@chromium.org 1600c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // Array index in the lastMatchInfo array. 1617be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static const int kLastCaptureCount = 0; 1627be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static const int kLastSubject = 1; 1637be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static const int kLastInput = 2; 164bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org static const int kFirstCapture = 3; 1657be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static const int kLastMatchOverhead = 3; 1667be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 1670c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // Direct offset into the lastMatchInfo array. 1680c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static const int kLastCaptureCountOffset = 1690c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org FixedArray::kHeaderSize + kLastCaptureCount * kPointerSize; 1700c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static const int kLastSubjectOffset = 1710c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org FixedArray::kHeaderSize + kLastSubject * kPointerSize; 1720c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static const int kLastInputOffset = 1730c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org FixedArray::kHeaderSize + kLastInput * kPointerSize; 1740c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static const int kFirstCaptureOffset = 1750c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org FixedArray::kHeaderSize + kFirstCapture * kPointerSize; 1760c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org 177bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org // Used to access the lastMatchInfo array. 1787be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static int GetCapture(FixedArray* array, int index) { 1797be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org return Smi::cast(array->get(index + kFirstCapture))->value(); 1807be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } 1817be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 1827be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static void SetLastCaptureCount(FixedArray* array, int to) { 1837be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org array->set(kLastCaptureCount, Smi::FromInt(to)); 1847be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } 1857be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 1867be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static void SetLastSubject(FixedArray* array, String* to) { 187bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org array->set(kLastSubject, to); 1887be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } 1897be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 1907be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static void SetLastInput(FixedArray* array, String* to) { 191bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org array->set(kLastInput, to); 1927be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } 1937be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 1947be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static void SetCapture(FixedArray* array, int index, int to) { 1957be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org array->set(index + kFirstCapture, Smi::FromInt(to)); 1967be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } 197a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 198bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org static int GetLastCaptureCount(FixedArray* array) { 199bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org return Smi::cast(array->get(kLastCaptureCount))->value(); 200bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org } 2017be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 202bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org // For acting on the JSRegExp data FixedArray. 2037be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static int IrregexpMaxRegisterCount(FixedArray* re); 2047be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static void SetIrregexpMaxRegisterCount(FixedArray* re, int value); 2057be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static int IrregexpNumberOfCaptures(FixedArray* re); 2067be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org static int IrregexpNumberOfRegisters(FixedArray* re); 2072c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org static ByteArray* IrregexpByteCode(FixedArray* re, bool is_one_byte); 2082c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org static Code* IrregexpNativeCode(FixedArray* re, bool is_one_byte); 20943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 21083a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org // Limit the space regexps take up on the heap. In order to limit this we 21183a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org // would like to keep track of the amount of regexp code on the heap. This 21283a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org // is not tracked, however. As a conservative approximation we track the 21383a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org // total regexp code compiled including code that has subsequently been freed 21483a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org // and the total executable memory at any point. 21583a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org static const int kRegExpExecutableMemoryLimit = 16 * MB; 21683a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org static const int kRegWxpCompiledLimit = 1 * MB; 21783a4728861129dc263ded92157f3e6389f851f19karlklose@chromium.org 218bb29dc9819bb6f495ab6eddd2543965eb97a8e43ager@chromium.org private: 2192c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org static bool CompileIrregexp(Handle<JSRegExp> re, 2202c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org Handle<String> sample_subject, bool is_one_byte); 2212c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org static inline bool EnsureCompiledIrregexp(Handle<JSRegExp> re, 2222c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org Handle<String> sample_subject, 2232c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org bool is_one_byte); 22443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen}; 22543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 22643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2270c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org// Represents the location of one element relative to the intersection of 2280c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org// two sets. Corresponds to the four areas of a Venn diagram. 2290c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.orgenum ElementInSetsRelation { 2300c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org kInsideNone = 0, 2310c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org kInsideFirst = 1, 2320c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org kInsideSecond = 2, 2330c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org kInsideBoth = 3 2340c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org}; 2350c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org 2360c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org 2371044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org// Represents code units in the range from from_ to to_, both ends are 2381044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org// inclusive. 239a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass CharacterRange { 240a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 241a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org CharacterRange() : from_(0), to_(0) { } 242a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // For compatibility with the CHECK_OK macro 243e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org CharacterRange(void* null) { DCHECK_EQ(NULL, null); } //NOLINT 244a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { } 2457028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges, 2467028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone); 247ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com static Vector<const int> GetWordBounds(); 248a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static inline CharacterRange Singleton(uc16 value) { 249a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return CharacterRange(value, value); 250a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 251a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static inline CharacterRange Range(uc16 from, uc16 to) { 252e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(from <= to); 253a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return CharacterRange(from, to); 254a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 255a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static inline CharacterRange Everything() { 256a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return CharacterRange(0, 0xFFFF); 257a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 258a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool Contains(uc16 i) { return from_ <= i && i <= to_; } 259a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 from() const { return from_; } 260a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_from(uc16 value) { from_ = value; } 261a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 to() const { return to_; } 262a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_to(uc16 value) { to_ = value; } 263a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool is_valid() { return from_ <= to_; } 2648bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; } 265a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool IsSingleton() { return (from_ == to_); } 2662c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org void AddCaseEquivalents(ZoneList<CharacterRange>* ranges, bool is_one_byte, 2677028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone); 268a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static void Split(ZoneList<CharacterRange>* base, 269ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com Vector<const int> overlay, 270a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<CharacterRange>** included, 2717028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org ZoneList<CharacterRange>** excluded, 2727028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone); 2730c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // Whether a range list is in canonical form: Ranges ordered by from value, 2740c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // and ranges non-overlapping and non-adjacent. 2750c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static bool IsCanonical(ZoneList<CharacterRange>* ranges); 2760c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // Convert range list to canonical form. The characters covered by the ranges 2770c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // will still be the same, but no character is in more than one range, and 2780c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // adjacent ranges are merged. The resulting list may be shorter than the 2790c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // original, but cannot be longer. 2800c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static void Canonicalize(ZoneList<CharacterRange>* ranges); 2810c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org // Negate the contents of a character range in canonical form. 2820c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static void Negate(ZoneList<CharacterRange>* src, 2837028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org ZoneList<CharacterRange>* dst, 2847028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone); 285a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static const int kStartMarker = (1 << 24); 286a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static const int kPayloadMask = (1 << 24) - 1; 287a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 288a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 289a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 from_; 290a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 to_; 291a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 292a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 293a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 294a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org// A set of unsigned integers that behaves especially well on small 295a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org// integers (< 32). May do zone-allocation. 296a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass OutSet: public ZoneObject { 297a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 298a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet() : first_(0), remaining_(NULL), successors_(NULL) { } 2997028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org OutSet* Extend(unsigned value, Zone* zone); 300196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org bool Get(unsigned value) const; 301a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static const unsigned kFirstLimit = 32; 302a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 303a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 304a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // Destructively set a value in this set. In most cases you want 305a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // to use Extend instead to ensure that only one instance exists 306a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // that contains the same values. 3077028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void Set(unsigned value, Zone* zone); 308a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 309a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // The successors are a list of sets that contain the same values 310a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // as this set and the one more value that is not present in this 311a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // set. 3127028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org ZoneList<OutSet*>* successors(Zone* zone) { return successors_; } 313a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 314a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet(uint32_t first, ZoneList<unsigned>* remaining) 315a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : first_(first), remaining_(remaining), successors_(NULL) { } 316a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uint32_t first_; 317a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<unsigned>* remaining_; 318a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<OutSet*>* successors_; 3193291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org friend class Trace; 320a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 321a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 322a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 323a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org// A mapping from integers, specified as ranges, to a set of integers. 324a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org// Used for mapping character ranges to choices. 325a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass DispatchTable : public ZoneObject { 326a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 3277028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org explicit DispatchTable(Zone* zone) : tree_(zone) { } 3287028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org 329a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org class Entry { 330a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 331a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Entry() : from_(0), to_(0), out_set_(NULL) { } 332a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Entry(uc16 from, uc16 to, OutSet* out_set) 333a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : from_(from), to_(to), out_set_(out_set) { } 334a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 from() { return from_; } 335a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 to() { return to_; } 336a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_to(uc16 value) { to_ = value; } 3377028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void AddValue(int value, Zone* zone) { 3387028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org out_set_ = out_set_->Extend(value, zone); 3397028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org } 340a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet* out_set() { return out_set_; } 341a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 342a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 from_; 343a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org uc16 to_; 344a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet* out_set_; 345a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org }; 346a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 347a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org class Config { 348a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 349a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org typedef uc16 Key; 350a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org typedef Entry Value; 351a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static const uc16 kNoKey; 352a8bb4d938869bdcdf759625ee868775ff24826d9svenpanne@chromium.org static const Entry NoValue() { return Value(); } 353a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static inline int Compare(uc16 a, uc16 b) { 354a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org if (a == b) 355a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return 0; 356a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org else if (a < b) 357a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return -1; 358a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org else 359a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return 1; 360a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 361a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org }; 362a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 3637028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void AddRange(CharacterRange range, int value, Zone* zone); 364a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet* Get(uc16 value); 365a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void Dump(); 366a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 367a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org template <typename Callback> 3687028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void ForEach(Callback* callback) { 3697028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return tree()->ForEach(callback); 3707028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org } 37183e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 372a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 373a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // There can't be a static empty set since it allocates its 374a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // successors in a zone and caches them. 375a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet* empty() { return &empty_; } 376a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org OutSet empty_; 377a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneSplayTree<Config>* tree() { return &tree_; } 378a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneSplayTree<Config> tree_; 379a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 380a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 381a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 382a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#define FOR_EACH_NODE_TYPE(VISIT) \ 383a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(End) \ 384a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Action) \ 385a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Choice) \ 386a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(BackReference) \ 387ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org VISIT(Assertion) \ 388a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Text) 389a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 390a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 391a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ 392a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Disjunction) \ 393a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Alternative) \ 394a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Assertion) \ 395a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(CharacterClass) \ 396a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Atom) \ 397a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Quantifier) \ 398a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Capture) \ 399a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Lookahead) \ 400a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(BackReference) \ 401a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Empty) \ 402a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org VISIT(Text) 403a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 404a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 405a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#define FORWARD_DECLARE(Name) class RegExp##Name; 406a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgFOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE) 407a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#undef FORWARD_DECLARE 408a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 409a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 410ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.orgclass TextElement FINAL BASE_EMBEDDED { 411a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 4129259716434187c932704601f700375e53d865de8rossberg@chromium.org enum TextType { 4139259716434187c932704601f700375e53d865de8rossberg@chromium.org ATOM, 4149259716434187c932704601f700375e53d865de8rossberg@chromium.org CHAR_CLASS 4159259716434187c932704601f700375e53d865de8rossberg@chromium.org }; 4169259716434187c932704601f700375e53d865de8rossberg@chromium.org 417a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static TextElement Atom(RegExpAtom* atom); 418a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static TextElement CharClass(RegExpCharacterClass* char_class); 4199259716434187c932704601f700375e53d865de8rossberg@chromium.org 4209259716434187c932704601f700375e53d865de8rossberg@chromium.org int cp_offset() const { return cp_offset_; } 4219259716434187c932704601f700375e53d865de8rossberg@chromium.org void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } 4229259716434187c932704601f700375e53d865de8rossberg@chromium.org int length() const; 4239259716434187c932704601f700375e53d865de8rossberg@chromium.org 4249259716434187c932704601f700375e53d865de8rossberg@chromium.org TextType text_type() const { return text_type_; } 4259259716434187c932704601f700375e53d865de8rossberg@chromium.org 4269259716434187c932704601f700375e53d865de8rossberg@chromium.org RegExpTree* tree() const { return tree_; } 4279259716434187c932704601f700375e53d865de8rossberg@chromium.org 4289259716434187c932704601f700375e53d865de8rossberg@chromium.org RegExpAtom* atom() const { 429e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(text_type() == ATOM); 4309259716434187c932704601f700375e53d865de8rossberg@chromium.org return reinterpret_cast<RegExpAtom*>(tree()); 4319259716434187c932704601f700375e53d865de8rossberg@chromium.org } 4329259716434187c932704601f700375e53d865de8rossberg@chromium.org 4339259716434187c932704601f700375e53d865de8rossberg@chromium.org RegExpCharacterClass* char_class() const { 434e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(text_type() == CHAR_CLASS); 4359259716434187c932704601f700375e53d865de8rossberg@chromium.org return reinterpret_cast<RegExpCharacterClass*>(tree()); 4369259716434187c932704601f700375e53d865de8rossberg@chromium.org } 4379259716434187c932704601f700375e53d865de8rossberg@chromium.org 4389259716434187c932704601f700375e53d865de8rossberg@chromium.org private: 4399259716434187c932704601f700375e53d865de8rossberg@chromium.org TextElement(TextType text_type, RegExpTree* tree) 4409259716434187c932704601f700375e53d865de8rossberg@chromium.org : cp_offset_(-1), text_type_(text_type), tree_(tree) {} 4419259716434187c932704601f700375e53d865de8rossberg@chromium.org 4429259716434187c932704601f700375e53d865de8rossberg@chromium.org int cp_offset_; 4439259716434187c932704601f700375e53d865de8rossberg@chromium.org TextType text_type_; 4449259716434187c932704601f700375e53d865de8rossberg@chromium.org RegExpTree* tree_; 445a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 446a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 447a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 4483291210ab99f306b74430ebbc4b7d939629e699fager@chromium.orgclass Trace; 4491af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.orgstruct PreloadState; 4501af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.orgclass GreedyLoopState; 4511af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.orgclass AlternativeGenerationList; 4528bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 453a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgstruct NodeInfo { 454a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org NodeInfo() 455a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : being_analyzed(false), 456a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org been_analyzed(false), 457a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_word_interest(false), 458a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_newline_interest(false), 459a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_start_interest(false), 460a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org at_end(false), 4611044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org visited(false), 4621044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org replacement_calculated(false) { } 463a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 464a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // Returns true if the interests and assumptions of this node 465a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // matches the given one. 466a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool Matches(NodeInfo* that) { 467a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return (at_end == that->at_end) && 468a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org (follows_word_interest == that->follows_word_interest) && 469a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org (follows_newline_interest == that->follows_newline_interest) && 47037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com (follows_start_interest == that->follows_start_interest); 471a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 472a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 473a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // Updates the interests of this node given the interests of the 474a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // node preceding it. 475a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void AddFromPreceding(NodeInfo* that) { 476a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org at_end |= that->at_end; 477a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_word_interest |= that->follows_word_interest; 478a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_newline_interest |= that->follows_newline_interest; 479a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_start_interest |= that->follows_start_interest; 480a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 481a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 4828bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org bool HasLookbehind() { 4838bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org return follows_word_interest || 4848bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org follows_newline_interest || 4858bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org follows_start_interest; 4868bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org } 4878bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 488a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // Sets the interests of this node to include the interests of the 489a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // following node. 490a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void AddFromFollowing(NodeInfo* that) { 491a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_word_interest |= that->follows_word_interest; 492a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_newline_interest |= that->follows_newline_interest; 493a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org follows_start_interest |= that->follows_start_interest; 494a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 495a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 496a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void ResetCompilationState() { 497a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org being_analyzed = false; 498a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org been_analyzed = false; 499a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 500a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 501a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool being_analyzed: 1; 502a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool been_analyzed: 1; 503a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 504a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // These bits are set of this node has to know what the preceding 505a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // character was. 506a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool follows_word_interest: 1; 507a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool follows_newline_interest: 1; 508a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool follows_start_interest: 1; 509a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 510a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool at_end: 1; 511a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool visited: 1; 5121044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org bool replacement_calculated: 1; 513a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 514a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 515a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 51637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com// Details of a quick mask-compare check that can look ahead in the 51737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com// input stream. 51837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.comclass QuickCheckDetails { 51937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com public: 52037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com QuickCheckDetails() 52137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com : characters_(0), 52237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com mask_(0), 523245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org value_(0), 524245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org cannot_match_(false) { } 52537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com explicit QuickCheckDetails(int characters) 52637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com : characters_(characters), 52737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com mask_(0), 528245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org value_(0), 529245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org cannot_match_(false) { } 5302c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org bool Rationalize(bool one_byte); 53137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // Merge in the information from another branch of an alternation. 53237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void Merge(QuickCheckDetails* other, int from_index); 53337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // Advance the current position by some amount. 5342c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org void Advance(int by, bool one_byte); 53537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void Clear(); 536245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool cannot_match() { return cannot_match_; } 537245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org void set_cannot_match() { cannot_match_ = true; } 53837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com struct Position { 53937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com Position() : mask(0), value(0), determines_perfectly(false) { } 54037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com uc16 mask; 54137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com uc16 value; 54237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool determines_perfectly; 54337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com }; 54437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int characters() { return characters_; } 54537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void set_characters(int characters) { characters_ = characters; } 54637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com Position* positions(int index) { 547e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(index >= 0); 548e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(index < characters_); 54937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com return positions_ + index; 55037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com } 55137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com uint32_t mask() { return mask_; } 55237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com uint32_t value() { return value_; } 55337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 55437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com private: 55537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // How many characters do we have quick check information from. This is 55637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // the same for all branches of a choice node. 55737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int characters_; 55837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com Position positions_[4]; 55937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // These values are the condensate of the above array after Rationalize(). 56037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com uint32_t mask_; 56137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com uint32_t value_; 562245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org // If set to true, there is no way this quick check can match at all. 563245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org // E.g., if it requires to be at the start of the input, and isn't. 564245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool cannot_match_; 56537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com}; 56637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 56737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 5681044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.orgextern int kUninitializedRegExpNodePlaceHolder; 5691044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 5701044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 571a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass RegExpNode: public ZoneObject { 572a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 573400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit RegExpNode(Zone* zone) 574400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : replacement_(NULL), trace_count_(0), zone_(zone) { 575ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bm_info_[0] = bm_info_[1] = NULL; 576ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 57737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual ~RegExpNode(); 578a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Accept(NodeVisitor* visitor) = 0; 579a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org // Generates a goto to this node or actually generates the code at this point. 580ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0; 58137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // How many characters must this node consume at a minimum in order to 582ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // succeed. If we have found at least 'still_to_find' characters that 583ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // must be consumed there is no need to ask any following nodes whether 584a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // they are sure to eat any more characters. The not_at_start argument is 585a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // used to indicate that we know we are not at the start of the input. In 586a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // this case anchored branches will always fail and can be ignored when 587a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // determining how many characters are consumed on success. 5884a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start) = 0; 58937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // Emits some quick code that checks whether the preloaded characters match. 59037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // Falls through on certain failure, jumps to the label on possible success. 59137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // If the node cannot make a quick check it does nothing and returns false. 59237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool EmitQuickCheck(RegExpCompiler* compiler, 593d3df75b4472c9d5d4d2615aaea74d2adce4160f8machenbach@chromium.org Trace* bounds_check_trace, 5943291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Trace* trace, 59537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool preload_has_checked_bounds, 59637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com Label* on_possible_success, 59737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com QuickCheckDetails* details_return, 59837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool fall_through_on_failure); 59937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // For a given number of characters this returns a mask and a value. The 60037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // next n characters are anded with the mask and compared with the value. 60137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // A comparison failure indicates the node cannot match the next n characters. 60237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // A comparison success indicates the node may match. 60337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 60437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 605245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 606245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start) = 0; 6078bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org static const int kNodeIsTooComplexForGreedyLoops = -1; 6088bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } 6097d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org // Only returns the successor for a text node of length 1 that matches any 6107d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org // character and that has no guards on it. 6117d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( 6127d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org RegExpCompiler* compiler) { 6137d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org return NULL; 6147d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org } 6157d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org 6167d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org // Collects information on the possible code units (mod 128) that can match if 6177d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org // we look forward. This is used for a Boyer-Moore-like string searching 6187d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org // implementation. TODO(erikcorry): This should share more code with 619400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // EatsAtLeast, GetQuickCheckDetails. The budget argument is used to limit 620400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org // the number of nodes we are willing to look at in order to create this data. 6214a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org static const int kRecursionBudget = 200; 62237141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 623400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 62437141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 62537141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start) { 6267d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org UNREACHABLE(); 6277d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org } 6281044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 6292c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org // If we know that the input is one-byte then there are some nodes that can 6301044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org // never match. This method returns a node that can be substituted for 6311044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org // itself, or NULL if the node can never match. 6322c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org virtual RegExpNode* FilterOneByte(int depth, bool ignore_case) { 6332c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org return this; 6342c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org } 6352c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org // Helper for FilterOneByte. 6361044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org RegExpNode* replacement() { 637e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(info()->replacement_calculated); 6381044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org return replacement_; 6391044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org } 6401044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org RegExpNode* set_replacement(RegExpNode* replacement) { 6411044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org info()->replacement_calculated = true; 6421044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org replacement_ = replacement; 6431044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org return replacement; // For convenience. 6441044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org } 6451044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 646ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // We want to avoid recalculating the lookahead info, so we store it on the 647ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // node. Only info that is for this node is stored. We can tell that the 648ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // info is for this node when offset == 0, so the information is calculated 649ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // relative to this node. 650ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void SaveBMInfo(BoyerMooreLookahead* bm, bool not_at_start, int offset) { 651ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com if (offset == 0) set_bm_info(not_at_start, bm); 652ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 6537d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org 6548bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org Label* label() { return &label_; } 6552efb900e7350b14be905abdeab077f3a64c583cfulan@chromium.org // If non-generic code is generated for a node (i.e. the node is not at the 6563291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // start of the trace) then it cannot be reused. This variable sets a limit 6573291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // on how often we allow that to happen before we insist on starting a new 6583291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // trace and generating generic code for a node that can be reused by flushing 6593291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // the deferred actions in the current trace and generating a goto. 6603291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static const int kMaxCopiesCodeGenerated = 10; 661a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 662a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org NodeInfo* info() { return &info_; } 663a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 664ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com BoyerMooreLookahead* bm_info(bool not_at_start) { 665ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com return bm_info_[not_at_start ? 1 : 0]; 666ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 6670c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org 6687028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone() const { return zone_; } 669400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org 670a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org protected: 671ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org enum LimitResult { DONE, CONTINUE }; 6721044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org RegExpNode* replacement_; 6730c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org 6743291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace); 675a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 676ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) { 677ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bm_info_[not_at_start ? 1 : 0] = bm; 678ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 679ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 680a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 6810c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org static const int kFirstCharBudget = 10; 682a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Label label_; 683a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org NodeInfo info_; 6843291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // This variable keeps track of how many times code has been generated for 6853291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // this node (in different traces). We don't keep track of where the 6863291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // generated code is located unless the code is generated at the start of 6873291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // a trace, in which case it is generic and can be reused by flushing the 6883291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // deferred operations in the current trace and generating a goto. 6893291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int trace_count_; 690ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com BoyerMooreLookahead* bm_info_[2]; 691400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org 692400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Zone* zone_; 6933291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org}; 6943291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org 6953291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org 6963291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// A simple closed interval. 6973291210ab99f306b74430ebbc4b7d939629e699fager@chromium.orgclass Interval { 6983291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org public: 6993291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Interval() : from_(kNone), to_(kNone) { } 7003291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Interval(int from, int to) : from_(from), to_(to) { } 7013291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Interval Union(Interval that) { 7023291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org if (that.from_ == kNone) 7033291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org return *this; 7043291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org else if (from_ == kNone) 7053291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org return that; 7063291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org else 7073291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org return Interval(Min(from_, that.from_), Max(to_, that.to_)); 7083291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org } 7093291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org bool Contains(int value) { 7103291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org return (from_ <= value) && (value <= to_); 7113291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org } 7123291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org bool is_empty() { return from_ == kNone; } 713ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int from() const { return from_; } 714ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int to() const { return to_; } 7153291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static Interval Empty() { return Interval(); } 7163291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static const int kNone = -1; 7173291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org private: 7183291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int from_; 7193291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int to_; 720a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 721a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 722a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 723a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass SeqRegExpNode: public RegExpNode { 724a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 725a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org explicit SeqRegExpNode(RegExpNode* on_success) 726400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : RegExpNode(on_success->zone()), on_success_(on_success) { } 727a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org RegExpNode* on_success() { return on_success_; } 728a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_on_success(RegExpNode* node) { on_success_ = node; } 7292c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); 73037141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 731400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 73237141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 73337141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start) { 7344a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org on_success_->FillInBMInfo(offset, budget - 1, bm, not_at_start); 735ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com if (offset == 0) set_bm_info(not_at_start, bm); 7367d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org } 7371044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 7381044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org protected: 73959297c735ad2a41156ae9c723a39ff259ad061e0jkummerow@chromium.org RegExpNode* FilterSuccessor(int depth, bool ignore_case); 7401044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 741a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 742a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org RegExpNode* on_success_; 743a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 744a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 745a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 746a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass ActionNode: public SeqRegExpNode { 747a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 748dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org enum ActionType { 7498bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org SET_REGISTER, 750a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org INCREMENT_REGISTER, 751a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org STORE_POSITION, 752a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org BEGIN_SUBMATCH, 7533291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org POSITIVE_SUBMATCH_SUCCESS, 7543291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org EMPTY_MATCH_CHECK, 7553291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org CLEAR_CAPTURES 756a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org }; 7578bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org static ActionNode* SetRegister(int reg, int val, RegExpNode* on_success); 758a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static ActionNode* IncrementRegister(int reg, RegExpNode* on_success); 759ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org static ActionNode* StorePosition(int reg, 760ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org bool is_capture, 761ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org RegExpNode* on_success); 7623291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success); 7633291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static ActionNode* BeginSubmatch(int stack_pointer_reg, 7643291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int position_reg, 7653291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org RegExpNode* on_success); 7663291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg, 7673291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int restore_reg, 768ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_capture_count, 769ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_capture_from, 7703291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org RegExpNode* on_success); 7713291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org static ActionNode* EmptyMatchCheck(int start_register, 7723291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int repetition_register, 7733291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int repetition_limit, 7743291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org RegExpNode* on_success); 775a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Accept(NodeVisitor* visitor); 776ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 7774a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); 77837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 77937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 780245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int filled_in, 781245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start) { 782245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org return on_success()->GetQuickCheckDetails( 783245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org details, compiler, filled_in, not_at_start); 78437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com } 78537141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 786400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 78737141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 78837141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start); 789dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org ActionType action_type() { return action_type_; } 7908bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org // TODO(erikcorry): We should allow some action nodes in greedy loops. 7918bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } 79283e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 793a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 794a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org union { 795a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org struct { 796a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int reg; 797a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int value; 798a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } u_store_register; 799a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org struct { 800a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int reg; 801a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } u_increment_register; 802a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org struct { 803a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int reg; 804ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org bool is_capture; 805a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } u_position_register; 806a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org struct { 807a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int stack_pointer_register; 808a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int current_position_register; 809ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_register_count; 810ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_register_from; 811a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } u_submatch; 8123291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org struct { 8133291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int start_register; 8143291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int repetition_register; 8153291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int repetition_limit; 8163291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org } u_empty_match_check; 8173291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org struct { 8183291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int range_from; 8193291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org int range_to; 8203291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org } u_clear_captures; 821a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } data_; 822dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org ActionNode(ActionType action_type, RegExpNode* on_success) 823a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : SeqRegExpNode(on_success), 824dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org action_type_(action_type) { } 825dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org ActionType action_type_; 826a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org friend class DotPrinter; 827a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 828a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 829a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 830a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass TextNode: public SeqRegExpNode { 831a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 832a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org TextNode(ZoneList<TextElement>* elms, 8338bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpNode* on_success) 834a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : SeqRegExpNode(on_success), 835a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org elms_(elms) { } 836a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org TextNode(RegExpCharacterClass* that, 8378bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpNode* on_success) 838a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : SeqRegExpNode(on_success), 8397028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org elms_(new(zone()) ZoneList<TextElement>(1, zone())) { 840400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org elms_->Add(TextElement::CharClass(that), zone()); 841a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 842a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Accept(NodeVisitor* visitor); 843ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 8444a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); 84537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 84637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 847245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 848245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start); 849a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<TextElement>* elements() { return elms_; } 8502c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org void MakeCaseIndependent(bool is_one_byte); 8518bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org virtual int GreedyLoopTextLength(); 8527d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( 8537d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org RegExpCompiler* compiler); 85437141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 855400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 85637141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 85737141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start); 8588bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void CalculateOffsets(); 8592c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); 86083e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 86137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com private: 86237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com enum TextEmitPassType { 8632c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org NON_LATIN1_MATCH, // Check for characters that can't match. 864381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. 865381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs. 866381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org CASE_CHARACTER_MATCH, // Case-independent single character check. 867381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org CHARACTER_CLASS_MATCH // Character class. 86837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com }; 869381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org static bool SkipPass(int pass, bool ignore_case); 870381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH; 871381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org static const int kLastPass = CHARACTER_CLASS_MATCH; 87237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void TextEmitPass(RegExpCompiler* compiler, 87337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com TextEmitPassType pass, 87437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool preloaded, 8753291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Trace* trace, 87637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool first_element_checked, 87737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int* checked_up_to); 87837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int Length(); 879a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<TextElement>* elms_; 880a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 881a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 882a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 883ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.orgclass AssertionNode: public SeqRegExpNode { 884ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org public: 885dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org enum AssertionType { 886ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org AT_END, 887ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org AT_START, 888ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org AT_BOUNDARY, 889ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org AT_NON_BOUNDARY, 890ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com AFTER_NEWLINE 891ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org }; 892ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org static AssertionNode* AtEnd(RegExpNode* on_success) { 8937028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return new(on_success->zone()) AssertionNode(AT_END, on_success); 894ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org } 895ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org static AssertionNode* AtStart(RegExpNode* on_success) { 8967028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return new(on_success->zone()) AssertionNode(AT_START, on_success); 897ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org } 898ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org static AssertionNode* AtBoundary(RegExpNode* on_success) { 8997028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return new(on_success->zone()) AssertionNode(AT_BOUNDARY, on_success); 900ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org } 901ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org static AssertionNode* AtNonBoundary(RegExpNode* on_success) { 9027028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return new(on_success->zone()) AssertionNode(AT_NON_BOUNDARY, on_success); 903ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org } 904ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org static AssertionNode* AfterNewline(RegExpNode* on_success) { 9057028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org return new(on_success->zone()) AssertionNode(AFTER_NEWLINE, on_success); 906ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org } 907ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Accept(NodeVisitor* visitor); 908ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 9094a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); 910ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void GetQuickCheckDetails(QuickCheckDetails* details, 911ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org RegExpCompiler* compiler, 912245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int filled_in, 913245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start); 91437141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 915400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 91637141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 91737141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start); 918dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org AssertionType assertion_type() { return assertion_type_; } 91983e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 920ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org private: 921ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace); 922ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com enum IfPrevious { kIsNonWord, kIsWord }; 923ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void BacktrackIfPrevious(RegExpCompiler* compiler, 924ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com Trace* trace, 925ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com IfPrevious backtrack_if_previous); 926dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org AssertionNode(AssertionType t, RegExpNode* on_success) 927dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org : SeqRegExpNode(on_success), assertion_type_(t) { } 928dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org AssertionType assertion_type_; 929ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org}; 930ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org 931ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org 932a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass BackReferenceNode: public SeqRegExpNode { 933a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 934a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org BackReferenceNode(int start_reg, 935a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int end_reg, 9368bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpNode* on_success) 937a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : SeqRegExpNode(on_success), 938a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org start_reg_(start_reg), 939a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org end_reg_(end_reg) { } 940a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Accept(NodeVisitor* visitor); 941a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int start_register() { return start_reg_; } 942a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int end_register() { return end_reg_; } 943ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 944a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org virtual int EatsAtLeast(int still_to_find, 945a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int recursion_depth, 946a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool not_at_start); 94737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 94837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 949245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 950245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start) { 95137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com return; 95237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com } 95337141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 954400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 95537141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 95637141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start); 95783e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 958a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 959a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int start_reg_; 960a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int end_reg_; 961a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 962a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 963a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 964a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass EndNode: public RegExpNode { 965a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 9668bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; 967400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit EndNode(Action action, Zone* zone) 968400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : RegExpNode(zone), action_(action) { } 969a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Accept(NodeVisitor* visitor); 970ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 971a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org virtual int EatsAtLeast(int still_to_find, 972a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int recursion_depth, 973a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool not_at_start) { return 0; } 97437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 97537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 976245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 977245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start) { 97837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // Returning 0 from EatsAtLeast should ensure we never get here. 97937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com UNREACHABLE(); 98037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com } 98137141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 982400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 98337141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 98437141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start) { 9857d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org // Returning 0 from EatsAtLeast should ensure we never get here. 9867d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org UNREACHABLE(); 9877d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org } 9881044a4d5f9e933d03cf05a0d7d49d8afccec0879danno@chromium.org 989a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 990a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Action action_; 991a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 992a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 993a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 9948bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.orgclass NegativeSubmatchSuccess: public EndNode { 9958bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 996ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org NegativeSubmatchSuccess(int stack_pointer_reg, 997ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int position_reg, 998ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_capture_count, 999400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int clear_capture_start, 1000400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Zone* zone) 1001400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : EndNode(NEGATIVE_SUBMATCH_SUCCESS, zone), 10028bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org stack_pointer_register_(stack_pointer_reg), 1003ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org current_position_register_(position_reg), 1004ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org clear_capture_count_(clear_capture_count), 1005ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org clear_capture_start_(clear_capture_start) { } 1006ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 10078bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 10088bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org private: 10098bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int stack_pointer_register_; 10108bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int current_position_register_; 1011ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_capture_count_; 1012ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int clear_capture_start_; 10138bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org}; 10148bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 10158bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 1016a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass Guard: public ZoneObject { 1017a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 1018a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org enum Relation { LT, GEQ }; 1019a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Guard(int reg, Relation op, int value) 1020a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : reg_(reg), 1021a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org op_(op), 1022a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org value_(value) { } 1023a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int reg() { return reg_; } 1024a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Relation op() { return op_; } 1025a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int value() { return value_; } 1026a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1027a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 1028a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int reg_; 1029a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Relation op_; 1030a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int value_; 1031a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1032a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1033a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1034a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass GuardedAlternative { 1035a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 1036a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { } 10377028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void AddGuard(Guard* guard, Zone* zone); 1038a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org RegExpNode* node() { return node_; } 1039a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_node(RegExpNode* node) { node_ = node; } 1040a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<Guard*>* guards() { return guards_; } 1041a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1042a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 1043a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org RegExpNode* node_; 1044a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<Guard*>* guards_; 1045a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1046a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1047a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 104837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.comclass AlternativeGeneration; 104937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 105037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 1051a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass ChoiceNode: public RegExpNode { 1052a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 1053400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit ChoiceNode(int expected_size, Zone* zone) 1054400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : RegExpNode(zone), 10557028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org alternatives_(new(zone) 10567028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org ZoneList<GuardedAlternative>(expected_size, zone)), 1057a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org table_(NULL), 1058245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org not_at_start_(false), 1059a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org being_calculated_(false) { } 1060a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Accept(NodeVisitor* visitor); 1061400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void AddAlternative(GuardedAlternative node) { 1062400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org alternatives()->Add(node, zone()); 1063400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 1064a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } 1065a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org DispatchTable* GetTable(bool ignore_case); 1066ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 10674a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); 1068ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org int EatsAtLeastHelper(int still_to_find, 10694a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org int budget, 1070a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org RegExpNode* ignore_this_node, 1071a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool not_at_start); 107237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 107337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 1074245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 1075245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start); 107637141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 1077400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 107837141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 107937141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start); 1080a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1081a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool being_calculated() { return being_calculated_; } 1082245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start() { return not_at_start_; } 1083245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org void set_not_at_start() { not_at_start_ = true; } 1084a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_being_calculated(bool b) { being_calculated_ = b; } 10851af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org virtual bool try_to_emit_quick_check_for_alternative(bool is_first) { 10861af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org return true; 10871af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org } 10882c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); 1089a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 10908bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org protected: 1091486075aa3f2e6d0031ff182961b9eab00e1081d8jkummerow@chromium.org int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative); 10928bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org ZoneList<GuardedAlternative>* alternatives_; 10938bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 1094a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 1095a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org friend class DispatchTableConstructor; 109637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com friend class Analysis; 1097a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void GenerateGuard(RegExpMacroAssembler* macro_assembler, 10985ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org Guard* guard, 10993291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Trace* trace); 11007d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org int CalculatePreloadCharacters(RegExpCompiler* compiler, int eats_at_least); 1101ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org void EmitOutOfLineContinuation(RegExpCompiler* compiler, 11023291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Trace* trace, 110337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com GuardedAlternative alternative, 110437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com AlternativeGeneration* alt_gen, 110537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int preload_characters, 110637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool next_expects_preload); 11071af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org void SetUpPreLoad(RegExpCompiler* compiler, 11081af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Trace* current_trace, 11091af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org PreloadState* preloads); 11101af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org void AssertGuardsMentionRegisters(Trace* trace); 11111af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org int EmitOptimizedUnanchoredSearch(RegExpCompiler* compiler, Trace* trace); 11121af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Trace* EmitGreedyLoop(RegExpCompiler* compiler, 11131af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Trace* trace, 11141af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org AlternativeGenerationList* alt_gens, 11151af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org PreloadState* preloads, 11161af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org GreedyLoopState* greedy_loop_state, 11171af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org int text_length); 11181af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org void EmitChoices(RegExpCompiler* compiler, 11191af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org AlternativeGenerationList* alt_gens, 11201af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org int first_choice, 11211af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Trace* trace, 11221af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org PreloadState* preloads); 1123a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org DispatchTable* table_; 1124245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org // If true, this node is never checked at the start of the input. 1125245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org // Allows a new trace to start with at_start() set to false. 1126245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start_; 1127a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool being_calculated_; 1128a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1129a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1130a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1131ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.orgclass NegativeLookaheadChoiceNode: public ChoiceNode { 1132ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org public: 1133ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail, 1134400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org GuardedAlternative then_do_this, 1135400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Zone* zone) 1136400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : ChoiceNode(2, zone) { 1137ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org AddAlternative(this_must_fail); 1138ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org AddAlternative(then_do_this); 1139ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org } 11404a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); 1141ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void GetQuickCheckDetails(QuickCheckDetails* details, 1142ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org RegExpCompiler* compiler, 1143245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 1144245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start); 114537141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 1146400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 114737141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 114837141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start) { 114937141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org alternatives_->at(1).node()->FillInBMInfo( 11504a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org offset, budget - 1, bm, not_at_start); 1151ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com if (offset == 0) set_bm_info(not_at_start, bm); 11527d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org } 1153ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // For a negative lookahead we don't emit the quick check for the 1154ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // alternative that is expected to fail. This is because quick check code 1155ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // starts by loading enough characters for the alternative that takes fewest 1156ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // characters, but on a negative lookahead the negative branch did not take 1157ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org // part in that calculation (EatsAtLeast) so the assumptions don't hold. 11581af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org virtual bool try_to_emit_quick_check_for_alternative(bool is_first) { 11591af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org return !is_first; 11601af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org } 11612c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); 1162ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org}; 1163ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org 1164ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org 11658bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.orgclass LoopChoiceNode: public ChoiceNode { 11668bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 1167400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit LoopChoiceNode(bool body_can_be_zero_length, Zone* zone) 1168400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org : ChoiceNode(2, zone), 116937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com loop_node_(NULL), 117037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com continue_node_(NULL), 11711af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org body_can_be_zero_length_(body_can_be_zero_length) 11721af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org { } 117337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void AddLoopAlternative(GuardedAlternative alt); 117437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void AddContinueAlternative(GuardedAlternative alt); 1175ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org virtual void Emit(RegExpCompiler* compiler, Trace* trace); 11764a9f6553038df6b893b3d3ccae351723f4cbbae7yangguo@chromium.org virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); 117737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void GetQuickCheckDetails(QuickCheckDetails* details, 117837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpCompiler* compiler, 1179245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org int characters_filled_in, 1180245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool not_at_start); 118137141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org virtual void FillInBMInfo(int offset, 1182400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org int budget, 118337141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org BoyerMooreLookahead* bm, 118437141398d9125c021d47ceb91e2b19efd35c89ddverwaest@chromium.org bool not_at_start); 118537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpNode* loop_node() { return loop_node_; } 118637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpNode* continue_node() { return continue_node_; } 118737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool body_can_be_zero_length() { return body_can_be_zero_length_; } 118837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void Accept(NodeVisitor* visitor); 11892c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); 119037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 119137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com private: 119237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // AddAlternative is made private for loop nodes because alternatives 119337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // should not be added freely, we need to keep track of which node 119437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com // goes back to the node itself. 119537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void AddAlternative(GuardedAlternative node) { 119637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com ChoiceNode::AddAlternative(node); 119737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com } 119837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 119937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpNode* loop_node_; 120037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com RegExpNode* continue_node_; 120137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool body_can_be_zero_length_; 12028bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org}; 12038bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 12048bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 1205ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// Improve the speed that we scan for an initial point where a non-anchored 1206ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// regexp can match by using a Boyer-Moore-like table. This is done by 1207ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// identifying non-greedy non-capturing loops in the nodes that eat any 1208ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// character one at a time. For example in the middle of the regexp 1209ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// /foo[\s\S]*?bar/ we find such a loop. There is also such a loop implicitly 1210ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// inserted at the start of any non-anchored regexp. 1211ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// 1212ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// When we have found such a loop we look ahead in the nodes to find the set of 1213ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// characters that can come at given distances. For example for the regexp 1214ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// /.?foo/ we know that there are at least 3 characters ahead of us, and the 1215ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// sets of characters that can occur are [any, [f, o], [o]]. We find a range in 1216ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// the lookahead info where the set of characters is reasonably constrained. In 1217ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// our example this is from index 1 to 2 (0 is not constrained). We can now 1218ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// look 3 characters ahead and if we don't find one of [f, o] (the union of 1219ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// [f, o] and [o]) then we can skip forwards by the range size (in this case 2). 1220ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// 1221ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// For Unicode input strings we do the same, but modulo 128. 1222ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// 1223ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// We also look at the first string fed to the regexp and use that to get a hint 1224ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// of the character frequencies in the inputs. This affects the assessment of 1225ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// whether the set of characters is 'reasonably constrained'. 1226ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// 1227ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// We also have another lookahead mechanism (called quick check in the code), 1228ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// which uses a wide load of multiple characters followed by a mask and compare 1229ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com// to determine whether a match is possible at this point. 1230ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.comenum ContainedInLattice { 1231ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com kNotYet = 0, 1232ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com kLatticeIn = 1, 1233ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com kLatticeOut = 2, 1234ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com kLatticeUnknown = 3 // Can also mean both in and out. 1235ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com}; 1236ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1237ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1238ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.cominline ContainedInLattice Combine(ContainedInLattice a, ContainedInLattice b) { 1239ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com return static_cast<ContainedInLattice>(a | b); 1240ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com} 1241ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1242ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1243ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.comContainedInLattice AddRange(ContainedInLattice a, 1244ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com const int* ranges, 1245ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int ranges_size, 1246ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com Interval new_range); 1247ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1248ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1249ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.comclass BoyerMoorePositionInfo : public ZoneObject { 1250ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com public: 1251400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit BoyerMoorePositionInfo(Zone* zone) 12527028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org : map_(new(zone) ZoneList<bool>(kMapSize, zone)), 1253ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com map_count_(0), 1254ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com w_(kNotYet), 1255ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com s_(kNotYet), 1256ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com d_(kNotYet), 1257ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com surrogate_(kNotYet) { 1258ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com for (int i = 0; i < kMapSize; i++) { 1259400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org map_->Add(false, zone); 1260ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1261ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1262ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1263ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bool& at(int i) { return map_->at(i); } 1264ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1265ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com static const int kMapSize = 128; 1266ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com static const int kMask = kMapSize - 1; 1267ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1268ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int map_count() const { return map_count_; } 1269ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1270ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void Set(int character); 1271ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void SetInterval(const Interval& interval); 1272ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void SetAll(); 1273ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bool is_non_word() { return w_ == kLatticeOut; } 1274ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bool is_word() { return w_ == kLatticeIn; } 1275ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1276ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com private: 1277ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com ZoneList<bool>* map_; 1278ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int map_count_; // Number of set bits in the map. 1279ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com ContainedInLattice w_; // The \w character class. 1280ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com ContainedInLattice s_; // The \s character class. 1281ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com ContainedInLattice d_; // The \d character class. 1282ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com ContainedInLattice surrogate_; // Surrogate UTF-16 code units. 1283ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com}; 1284ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1285ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1286ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.comclass BoyerMooreLookahead : public ZoneObject { 1287ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com public: 1288400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org BoyerMooreLookahead(int length, RegExpCompiler* compiler, Zone* zone); 1289ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1290ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int length() { return length_; } 1291ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int max_char() { return max_char_; } 1292ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com RegExpCompiler* compiler() { return compiler_; } 1293ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1294ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int Count(int map_number) { 1295ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com return bitmaps_->at(map_number)->map_count(); 1296ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1297ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1298ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com BoyerMoorePositionInfo* at(int i) { return bitmaps_->at(i); } 1299ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1300ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void Set(int map_number, int character) { 1301ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com if (character > max_char_) return; 1302ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com BoyerMoorePositionInfo* info = bitmaps_->at(map_number); 1303ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com info->Set(character); 1304ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1305ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1306ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void SetInterval(int map_number, const Interval& interval) { 1307ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com if (interval.from() > max_char_) return; 1308ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com BoyerMoorePositionInfo* info = bitmaps_->at(map_number); 1309ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com if (interval.to() > max_char_) { 1310ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com info->SetInterval(Interval(interval.from(), max_char_)); 1311ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } else { 1312ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com info->SetInterval(interval); 1313ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1314ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1315ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1316ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void SetAll(int map_number) { 1317ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bitmaps_->at(map_number)->SetAll(); 1318ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 1319ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1320ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com void SetRest(int from_map) { 1321ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com for (int i = from_map; i < length_; i++) SetAll(i); 1322ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com } 13231af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org void EmitSkipInstructions(RegExpMacroAssembler* masm); 1324ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1325ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com private: 1326ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // This is the value obtained by EatsAtLeast. If we do not have at least this 1327ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // many characters left in the sample string then the match is bound to fail. 1328ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // Therefore it is OK to read a character this far ahead of the current match 1329ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com // point. 1330ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int length_; 1331ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com RegExpCompiler* compiler_; 13322c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org // 0xff for Latin1, 0xffff for UTF-16. 1333ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int max_char_; 1334ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com ZoneList<BoyerMoorePositionInfo*>* bitmaps_; 1335ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1336ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int GetSkipTable(int min_lookahead, 1337ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int max_lookahead, 1338ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com Handle<ByteArray> boolean_skip_table); 1339ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com bool FindWorthwhileInterval(int* from, int* to); 1340ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int FindBestInterval( 1341ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com int max_number_of_chars, int old_biggest_points, int* from, int* to); 1342ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com}; 1343ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 1344ed49e965b5cafa35395084dbfb79f4e07930f10ferik.corry@gmail.com 13458bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// There are many ways to generate code for a node. This class encapsulates 13468bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// the current way we should be generating. In other words it encapsulates 13473291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// the current state of the code generator. The effect of this is that we 13483291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// generate code for paths that the matcher can take through the regular 13493291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// expression. A given node in the regexp can be code-generated several times 13503291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// as it can be part of several traces. For example for the regexp: 13513291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part 13523291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// of the foo-bar-baz trace and once as part of the foo-ip-baz trace. The code 13533291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// to match foo is generated only once (the traces have a common prefix). The 13543291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// code to store the capture is deferred and generated (twice) after the places 13553291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org// where baz has been matched. 13563291210ab99f306b74430ebbc4b7d939629e699fager@chromium.orgclass Trace { 13578bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 1358245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org // A value for a property that is either known to be true, know to be false, 1359245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org // or not known. 1360245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org enum TriBool { 1361bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org UNKNOWN = -1, FALSE_VALUE = 0, TRUE_VALUE = 1 1362245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org }; 1363245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org 13648bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org class DeferredAction { 13658bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 1366dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org DeferredAction(ActionNode::ActionType action_type, int reg) 1367dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org : action_type_(action_type), reg_(reg), next_(NULL) { } 13688bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org DeferredAction* next() { return next_; } 13693291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org bool Mentions(int reg); 13708bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int reg() { return reg_; } 1371dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org ActionNode::ActionType action_type() { return action_type_; } 13728bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org private: 1373dfe53073738bbf16023d96fce5118358a1037fd3ulan@chromium.org ActionNode::ActionType action_type_; 13748bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int reg_; 13758bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org DeferredAction* next_; 13763291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org friend class Trace; 13778bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org }; 13788bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 1379ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org class DeferredCapture : public DeferredAction { 13808bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 1381ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org DeferredCapture(int reg, bool is_capture, Trace* trace) 13828bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org : DeferredAction(ActionNode::STORE_POSITION, reg), 1383ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org cp_offset_(trace->cp_offset()), 1384ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org is_capture_(is_capture) { } 13858bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int cp_offset() { return cp_offset_; } 1386ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org bool is_capture() { return is_capture_; } 13878bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org private: 13888bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int cp_offset_; 1389ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org bool is_capture_; 13908bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } 13918bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org }; 13928bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 1393ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org class DeferredSetRegister : public DeferredAction { 13948bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 13958bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org DeferredSetRegister(int reg, int value) 13968bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org : DeferredAction(ActionNode::SET_REGISTER, reg), 13978bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org value_(value) { } 13988bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int value() { return value_; } 13998bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org private: 14008bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int value_; 14018bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org }; 14028bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 14033291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org class DeferredClearCaptures : public DeferredAction { 14043291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org public: 14053291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org explicit DeferredClearCaptures(Interval range) 14063291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org : DeferredAction(ActionNode::CLEAR_CAPTURES, -1), 14073291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org range_(range) { } 14083291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Interval range() { return range_; } 14093291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org private: 14103291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Interval range_; 14113291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org }; 14123291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org 1413ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org class DeferredIncrementRegister : public DeferredAction { 14148bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org public: 14158bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org explicit DeferredIncrementRegister(int reg) 14168bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { } 14178bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org }; 14188bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 14193291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org Trace() 14208bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org : cp_offset_(0), 14218bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org actions_(NULL), 14228bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org backtrack_(NULL), 14238bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org stop_node_(NULL), 142437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com loop_label_(NULL), 142537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com characters_preloaded_(0), 1426245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bound_checked_up_to_(0), 1427381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org flush_budget_(100), 1428245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org at_start_(UNKNOWN) { } 1429245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org 14303291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // End the trace. This involves flushing the deferred actions in the trace 14313291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // and pushing a backtrack location onto the backtrack stack. Once this is 14323291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // done we can start a new trace or go to one that has already been 14333291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // generated. 1434ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org void Flush(RegExpCompiler* compiler, RegExpNode* successor); 14358bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int cp_offset() { return cp_offset_; } 14368bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org DeferredAction* actions() { return actions_; } 14373291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // A trivial trace is one that has no deferred actions or other state that 14383291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // affects the assumptions used when generating code. There is no recorded 14393291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // backtrack location in a trivial trace, so with a trivial trace we will 14403291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // generate code that, on a failure to match, gets the backtrack location 14413291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // from the backtrack stack rather than using a direct jump instruction. We 14423291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // always start code generation with a trivial trace and non-trivial traces 14433291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // are created as we emit code for nodes or add to the list of deferred 14443291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // actions in the trace. The location of the code generated for a node using 14453291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // a trivial trace is recorded in a label in the node so that gotos can be 14463291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // generated to that code. 14478bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org bool is_trivial() { 144837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com return backtrack_ == NULL && 144937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com actions_ == NULL && 145037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com cp_offset_ == 0 && 145137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com characters_preloaded_ == 0 && 145237abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bound_checked_up_to_ == 0 && 1453245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org quick_check_performed_.characters() == 0 && 1454245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org at_start_ == UNKNOWN; 14558bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org } 1456245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org TriBool at_start() { return at_start_; } 1457bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org void set_at_start(bool at_start) { 1458bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org at_start_ = at_start ? TRUE_VALUE : FALSE_VALUE; 1459bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 14608bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org Label* backtrack() { return backtrack_; } 14618bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org Label* loop_label() { return loop_label_; } 14628bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpNode* stop_node() { return stop_node_; } 146337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int characters_preloaded() { return characters_preloaded_; } 146437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int bound_checked_up_to() { return bound_checked_up_to_; } 1465381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org int flush_budget() { return flush_budget_; } 146637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; } 146737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool mentions_reg(int reg); 14683291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // Returns true if a deferred position store exists to the specified 14693291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // register and stores the offset in the out-parameter. Otherwise 14703291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // returns false. 14713291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org bool GetStoredPosition(int reg, int* cp_offset); 14723291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // These set methods and AdvanceCurrentPositionInTrace should be used only on 14733291210ab99f306b74430ebbc4b7d939629e699fager@chromium.org // new traces - the intention is that traces are immutable after creation. 14748bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void add_action(DeferredAction* new_action) { 1475e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(new_action->next_ == NULL); 14768bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org new_action->next_ = actions_; 14778bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org actions_ = new_action; 14788bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org } 14798bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void set_backtrack(Label* backtrack) { backtrack_ = backtrack; } 14808bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void set_stop_node(RegExpNode* node) { stop_node_ = node; } 14818bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void set_loop_label(Label* label) { loop_label_ = label; } 14820c20e676f8a0209982ff89e5a9c707771748a585fschneider@chromium.org void set_characters_preloaded(int count) { characters_preloaded_ = count; } 148337abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; } 1484381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org void set_flush_budget(int to) { flush_budget_ = to; } 148537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com void set_quick_check_performed(QuickCheckDetails* d) { 148637abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com quick_check_performed_ = *d; 148737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com } 1488ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org void InvalidateCurrentCharacter(); 1489ddb913d619a6e602f53dd17b0fe71158ce66888dager@chromium.org void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler); 149083e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 14918bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org private: 14927028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org int FindAffectedRegisters(OutSet* affected_registers, Zone* zone); 14938bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void PerformDeferredActions(RegExpMacroAssembler* macro, 14947028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org int max_register, 1495196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org const OutSet& affected_registers, 14967028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org OutSet* registers_to_pop, 14977028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org OutSet* registers_to_clear, 14987028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone); 14998bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org void RestoreAffectedRegisters(RegExpMacroAssembler* macro, 15008bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int max_register, 1501196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org const OutSet& registers_to_pop, 1502196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org const OutSet& registers_to_clear); 15038bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org int cp_offset_; 15048bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org DeferredAction* actions_; 15058bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org Label* backtrack_; 15068bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpNode* stop_node_; 15078bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org Label* loop_label_; 150837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int characters_preloaded_; 150937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com int bound_checked_up_to_; 151037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com QuickCheckDetails quick_check_performed_; 1511381abbb58260f2fc7d346d0e2f83d0f132a4c14bager@chromium.org int flush_budget_; 1512245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org TriBool at_start_; 15138bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org}; 151437abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 151537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com 15161af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.orgclass GreedyLoopState { 15171af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org public: 15181af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org explicit GreedyLoopState(bool not_at_start); 15191af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org 15201af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Label* label() { return &label_; } 15211af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Trace* counter_backtrack_trace() { return &counter_backtrack_trace_; } 15221af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org 15231af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org private: 15241af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Label label_; 15251af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org Trace counter_backtrack_trace_; 15261af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org}; 15271af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org 15281af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org 15291af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.orgstruct PreloadState { 15301af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org static const int kEatsAtLeastNotYetInitialized = -1; 15311af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org bool preload_is_current_; 15321af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org bool preload_has_checked_bounds_; 15331af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org int preload_characters_; 15341af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org int eats_at_least_; 15351af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org void init() { 15361af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org eats_at_least_ = kEatsAtLeastNotYetInitialized; 15371af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org } 15381af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org}; 15391af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org 15401af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org 1541a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass NodeVisitor { 1542a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 1543a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual ~NodeVisitor() { } 1544a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#define DECLARE_VISIT(Type) \ 1545a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Visit##Type(Type##Node* that) = 0; 1546a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgFOR_EACH_NODE_TYPE(DECLARE_VISIT) 1547a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#undef DECLARE_VISIT 154837abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); } 1549a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1550a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1551a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1552a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org// Node visitor used to add the start set of the alternatives to the 1553a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org// dispatch table of a choice node. 1554a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass DispatchTableConstructor: public NodeVisitor { 1555a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 15567028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org DispatchTableConstructor(DispatchTable* table, bool ignore_case, 15577028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone) 1558a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org : table_(table), 1559a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org choice_index_(-1), 15607028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org ignore_case_(ignore_case), 15617028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org zone_(zone) { } 1562a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1563a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void BuildTable(ChoiceNode* node); 1564a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1565a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void AddRange(CharacterRange range) { 15667028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org table()->AddRange(range, choice_index_, zone_); 1567a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 1568a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1569a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void AddInverse(ZoneList<CharacterRange>* ranges); 1570a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1571a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#define DECLARE_VISIT(Type) \ 1572a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Visit##Type(Type##Node* that); 1573a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgFOR_EACH_NODE_TYPE(DECLARE_VISIT) 1574a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#undef DECLARE_VISIT 1575a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1576a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org DispatchTable* table() { return table_; } 1577a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void set_choice_index(int value) { choice_index_ = value; } 1578a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1579a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org protected: 15805ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org DispatchTable* table_; 1581a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int choice_index_; 1582a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool ignore_case_; 15837028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Zone* zone_; 1584a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1585a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1586a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 15878bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// Assertion propagation moves information about assertions such as 15888bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// \b to the affected nodes. For instance, in /.\b./ information must 15898bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// be propagated to the first '.' that whatever follows needs to know 15908bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// if it matched a word or a non-word, and to the second '.' that it 15918bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// has to check if it succeeds a word or non-word. In this case the 15928bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// result will be something like: 15938bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// 15948bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// +-------+ +------------+ 15958bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// | . | | . | 15968bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// +-------+ ---> +------------+ 15978bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// | word? | | check word | 15988bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org// +-------+ +------------+ 159937abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.comclass Analysis: public NodeVisitor { 1600a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 16012c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org Analysis(bool ignore_case, bool is_one_byte) 160238e4c715e3a3df4ef11ccd3b86525be8f686ecb5ager@chromium.org : ignore_case_(ignore_case), 16032c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org is_one_byte_(is_one_byte), 16042c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org error_message_(NULL) {} 1605a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void EnsureAnalyzed(RegExpNode* node); 1606a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1607a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#define DECLARE_VISIT(Type) \ 1608a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org virtual void Visit##Type(Type##Node* that); 1609a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgFOR_EACH_NODE_TYPE(DECLARE_VISIT) 1610a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org#undef DECLARE_VISIT 161137abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com virtual void VisitLoopChoice(LoopChoiceNode* that); 1612a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1613755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org bool has_failed() { return error_message_ != NULL; } 1614755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org const char* error_message() { 1615e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(error_message_ != NULL); 1616755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org return error_message_; 1617755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org } 1618755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org void fail(const char* error_message) { 1619755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org error_message_ = error_message; 1620755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org } 162183e168294456ca2f02db421a635f7d5f5d023966kmillikin@chromium.org 1622a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org private: 1623a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org bool ignore_case_; 16242c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org bool is_one_byte_; 1625755c5b1cc880bc54405d2652f934a941e8fcda4asgjesse@chromium.org const char* error_message_; 1626a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 162737abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis); 1628a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1629a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1630a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 16318bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.orgstruct RegExpCompileData { 16328bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpCompileData() 16338bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org : tree(NULL), 16348bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org node(NULL), 163537abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com simple(true), 1636245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org contains_anchor(false), 16378bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org capture_count(0) { } 1638a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org RegExpTree* tree; 16398bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org RegExpNode* node; 164037abdec9cad6edeba05b5c7a9ff73c25f5df2b70christian.plesner.hansen@gmail.com bool simple; 1641245aa859d34fd516161c48ef4c69d38d9b889284iposva@chromium.org bool contains_anchor; 1642a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Handle<String> error; 1643a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org int capture_count; 1644a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1645a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1646a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1647a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgclass RegExpEngine: public AllStatic { 1648a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org public: 16497be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org struct CompilationResult { 1650e97852de34e44a479f092bd2449134e707cd9cf1dslomov@chromium.org CompilationResult(Isolate* isolate, const char* error_message) 16517be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org : error_message(error_message), 1652e97852de34e44a479f092bd2449134e707cd9cf1dslomov@chromium.org code(isolate->heap()->the_hole_value()), 16537be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org num_registers(0) {} 16547be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org CompilationResult(Object* code, int registers) 16557be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org : error_message(NULL), 16567be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org code(code), 16577be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org num_registers(registers) {} 16587be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org const char* error_message; 16597be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org Object* code; 16607be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org int num_registers; 16617be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org }; 16627be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org 16632c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org static CompilationResult Compile(RegExpCompileData* input, bool ignore_case, 1664a2c0c1516848536a514b3178d2c040b7df0ceb5bmachenbach@chromium.org bool global, bool multiline, bool sticky, 16657be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org Handle<String> pattern, 16667d10be581a91ab5eefa1139ff0b86c64ac8f6e59fschneider@chromium.org Handle<String> sample_subject, 16672c81ceb7f1e1ccf5f304be0646f4c1375941a7f2machenbach@chromium.org bool is_one_byte, Zone* zone); 16688bb60585bafbf81564e6b30fcf18c82615a76f95ager@chromium.org 1669a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); 1670a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org}; 1671a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 1672a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 167343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} } // namespace v8::internal 167443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 167543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif // V8_JSREGEXP_H_ 1676