OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1945 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1956 } | 1956 } |
1957 | 1957 |
1958 // If we get here code has been generated for this node too many times or | 1958 // If we get here code has been generated for this node too many times or |
1959 // recursion is too deep. Time to switch to a generic version. The code for | 1959 // recursion is too deep. Time to switch to a generic version. The code for |
1960 // generic versions above can handle deep recursion properly. | 1960 // generic versions above can handle deep recursion properly. |
1961 bool ok = trace->Flush(compiler, this); | 1961 bool ok = trace->Flush(compiler, this); |
1962 return ok ? DONE : FAIL; | 1962 return ok ? DONE : FAIL; |
1963 } | 1963 } |
1964 | 1964 |
1965 | 1965 |
1966 int ActionNode::EatsAtLeast(int recursion_depth) { | 1966 int ActionNode::EatsAtLeast(int still_to_find, int recursion_depth) { |
1967 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 1967 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; |
1968 if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input! | 1968 if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input! |
1969 return on_success()->EatsAtLeast(recursion_depth + 1); | 1969 return on_success()->EatsAtLeast(still_to_find, recursion_depth + 1); |
1970 } | 1970 } |
1971 | 1971 |
1972 | 1972 |
1973 int AssertionNode::EatsAtLeast(int recursion_depth) { | 1973 int AssertionNode::EatsAtLeast(int still_to_find, int recursion_depth) { |
1974 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 1974 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; |
1975 return on_success()->EatsAtLeast(recursion_depth + 1); | 1975 return on_success()->EatsAtLeast(still_to_find, recursion_depth + 1); |
1976 } | 1976 } |
1977 | 1977 |
1978 | 1978 |
1979 int BackReferenceNode::EatsAtLeast(int recursion_depth) { | 1979 int BackReferenceNode::EatsAtLeast(int still_to_find, int recursion_depth) { |
1980 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 1980 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; |
1981 return on_success()->EatsAtLeast(recursion_depth + 1); | 1981 return on_success()->EatsAtLeast(still_to_find, recursion_depth + 1); |
1982 } | 1982 } |
1983 | 1983 |
1984 | 1984 |
1985 int TextNode::EatsAtLeast(int recursion_depth) { | 1985 int TextNode::EatsAtLeast(int still_to_find, int recursion_depth) { |
1986 int answer = Length(); | 1986 int answer = Length(); |
1987 if (answer >= 4) return answer; | 1987 if (answer >= still_to_find) return answer; |
1988 if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer; | 1988 if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer; |
1989 return answer + on_success()->EatsAtLeast(recursion_depth + 1); | 1989 return answer + on_success()->EatsAtLeast(still_to_find - answer, |
| 1990 recursion_depth + 1); |
1990 } | 1991 } |
1991 | 1992 |
1992 | 1993 |
1993 int NegativeLookaheadChoiceNode:: EatsAtLeast(int recursion_depth) { | 1994 int NegativeLookaheadChoiceNode:: EatsAtLeast(int still_to_find, int recursion_d
epth) { |
1994 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 1995 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; |
1995 // Alternative 0 is the negative lookahead, alternative 1 is what comes | 1996 // Alternative 0 is the negative lookahead, alternative 1 is what comes |
1996 // afterwards. | 1997 // afterwards. |
1997 RegExpNode* node = alternatives_->at(1).node(); | 1998 RegExpNode* node = alternatives_->at(1).node(); |
1998 return node->EatsAtLeast(recursion_depth + 1); | 1999 return node->EatsAtLeast(still_to_find, recursion_depth + 1); |
1999 } | 2000 } |
2000 | 2001 |
2001 | 2002 |
2002 void NegativeLookaheadChoiceNode::GetQuickCheckDetails( | 2003 void NegativeLookaheadChoiceNode::GetQuickCheckDetails( |
2003 QuickCheckDetails* details, | 2004 QuickCheckDetails* details, |
2004 RegExpCompiler* compiler, | 2005 RegExpCompiler* compiler, |
2005 int filled_in) { | 2006 int filled_in) { |
2006 // Alternative 0 is the negative lookahead, alternative 1 is what comes | 2007 // Alternative 0 is the negative lookahead, alternative 1 is what comes |
2007 // afterwards. | 2008 // afterwards. |
2008 RegExpNode* node = alternatives_->at(1).node(); | 2009 RegExpNode* node = alternatives_->at(1).node(); |
2009 return node->GetQuickCheckDetails(details, compiler, filled_in); | 2010 return node->GetQuickCheckDetails(details, compiler, filled_in); |
2010 } | 2011 } |
2011 | 2012 |
2012 | 2013 |
2013 int ChoiceNode::EatsAtLeastHelper(int recursion_depth, | 2014 int ChoiceNode::EatsAtLeastHelper(int still_to_find, |
| 2015 int recursion_depth, |
2014 RegExpNode* ignore_this_node) { | 2016 RegExpNode* ignore_this_node) { |
2015 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 2017 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; |
2016 int min = 100; | 2018 int min = 100; |
2017 int choice_count = alternatives_->length(); | 2019 int choice_count = alternatives_->length(); |
2018 for (int i = 0; i < choice_count; i++) { | 2020 for (int i = 0; i < choice_count; i++) { |
2019 RegExpNode* node = alternatives_->at(i).node(); | 2021 RegExpNode* node = alternatives_->at(i).node(); |
2020 if (node == ignore_this_node) continue; | 2022 if (node == ignore_this_node) continue; |
2021 int node_eats_at_least = node->EatsAtLeast(recursion_depth + 1); | 2023 int node_eats_at_least = node->EatsAtLeast(still_to_find, recursion_depth +
1); |
2022 if (node_eats_at_least < min) min = node_eats_at_least; | 2024 if (node_eats_at_least < min) min = node_eats_at_least; |
2023 } | 2025 } |
2024 return min; | 2026 return min; |
2025 } | 2027 } |
2026 | 2028 |
2027 | 2029 |
2028 int LoopChoiceNode::EatsAtLeast(int recursion_depth) { | 2030 int LoopChoiceNode::EatsAtLeast(int still_to_find, int recursion_depth) { |
2029 return EatsAtLeastHelper(recursion_depth, loop_node_); | 2031 return EatsAtLeastHelper(still_to_find, recursion_depth, loop_node_); |
2030 } | 2032 } |
2031 | 2033 |
2032 | 2034 |
2033 int ChoiceNode::EatsAtLeast(int recursion_depth) { | 2035 int ChoiceNode::EatsAtLeast(int still_to_find, int recursion_depth) { |
2034 return EatsAtLeastHelper(recursion_depth, NULL); | 2036 return EatsAtLeastHelper(still_to_find, recursion_depth, NULL); |
2035 } | 2037 } |
2036 | 2038 |
2037 | 2039 |
2038 // Takes the left-most 1-bit and smears it out, setting all bits to its right. | 2040 // Takes the left-most 1-bit and smears it out, setting all bits to its right. |
2039 static inline uint32_t SmearBitsRight(uint32_t v) { | 2041 static inline uint32_t SmearBitsRight(uint32_t v) { |
2040 v |= v >> 1; | 2042 v |= v >> 1; |
2041 v |= v >> 2; | 2043 v |= v >> 2; |
2042 v |= v >> 4; | 2044 v |= v >> 4; |
2043 v |= v >> 8; | 2045 v |= v >> 8; |
2044 v |= v >> 16; | 2046 v |= v >> 16; |
(...skipping 759 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2804 } | 2806 } |
2805 ASSERT(trace->stop_node() == NULL); | 2807 ASSERT(trace->stop_node() == NULL); |
2806 if (!trace->is_trivial()) { | 2808 if (!trace->is_trivial()) { |
2807 return trace->Flush(compiler, this); | 2809 return trace->Flush(compiler, this); |
2808 } | 2810 } |
2809 return ChoiceNode::Emit(compiler, trace); | 2811 return ChoiceNode::Emit(compiler, trace); |
2810 } | 2812 } |
2811 | 2813 |
2812 | 2814 |
2813 int ChoiceNode::CalculatePreloadCharacters(RegExpCompiler* compiler) { | 2815 int ChoiceNode::CalculatePreloadCharacters(RegExpCompiler* compiler) { |
2814 int preload_characters = EatsAtLeast(0); | 2816 int preload_characters = EatsAtLeast(4, 0); |
2815 #ifdef CAN_READ_UNALIGNED | 2817 #ifdef CAN_READ_UNALIGNED |
2816 bool ascii = compiler->ascii(); | 2818 bool ascii = compiler->ascii(); |
2817 if (ascii) { | 2819 if (ascii) { |
2818 if (preload_characters > 4) preload_characters = 4; | 2820 if (preload_characters > 4) preload_characters = 4; |
2819 // We can't preload 3 characters because there is no machine instruction | 2821 // We can't preload 3 characters because there is no machine instruction |
2820 // to do that. We can't just load 4 because we could be reading | 2822 // to do that. We can't just load 4 because we could be reading |
2821 // beyond the end of the string, which could cause a memory fault. | 2823 // beyond the end of the string, which could cause a memory fault. |
2822 if (preload_characters == 3) preload_characters = 2; | 2824 if (preload_characters == 3) preload_characters = 2; |
2823 } else { | 2825 } else { |
2824 if (preload_characters > 2) preload_characters = 2; | 2826 if (preload_characters > 2) preload_characters = 2; |
(...skipping 1858 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4683 EmbeddedVector<byte, 1024> codes; | 4685 EmbeddedVector<byte, 1024> codes; |
4684 RegExpMacroAssemblerIrregexp macro_assembler(codes); | 4686 RegExpMacroAssemblerIrregexp macro_assembler(codes); |
4685 return compiler.Assemble(¯o_assembler, | 4687 return compiler.Assemble(¯o_assembler, |
4686 node, | 4688 node, |
4687 data->capture_count, | 4689 data->capture_count, |
4688 pattern); | 4690 pattern); |
4689 } | 4691 } |
4690 | 4692 |
4691 | 4693 |
4692 }} // namespace v8::internal | 4694 }} // namespace v8::internal |
OLD | NEW |