OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 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 1731 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1742 #define MAKE_CASE(Name) \ | 1742 #define MAKE_CASE(Name) \ |
1743 virtual void* Visit##Name(RegExp##Name*, void* data) = 0; | 1743 virtual void* Visit##Name(RegExp##Name*, void* data) = 0; |
1744 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) | 1744 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) |
1745 #undef MAKE_CASE | 1745 #undef MAKE_CASE |
1746 }; | 1746 }; |
1747 | 1747 |
1748 | 1748 |
1749 class RegExpTree: public ZoneObject { | 1749 class RegExpTree: public ZoneObject { |
1750 public: | 1750 public: |
1751 static const int kInfinity = kMaxInt; | 1751 static const int kInfinity = kMaxInt; |
1752 RegExpTree() : contains_expanded_quantifier_(false) { } | |
1753 virtual ~RegExpTree() { } | 1752 virtual ~RegExpTree() { } |
1754 virtual void* Accept(RegExpVisitor* visitor, void* data) = 0; | 1753 virtual void* Accept(RegExpVisitor* visitor, void* data) = 0; |
1755 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1754 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1756 RegExpNode* on_success) = 0; | 1755 RegExpNode* on_success) = 0; |
1757 virtual bool IsTextElement() { return false; } | 1756 virtual bool IsTextElement() { return false; } |
1758 virtual bool IsAnchoredAtStart() { return false; } | 1757 virtual bool IsAnchoredAtStart() { return false; } |
1759 virtual bool IsAnchoredAtEnd() { return false; } | 1758 virtual bool IsAnchoredAtEnd() { return false; } |
1760 virtual int min_match() = 0; | 1759 virtual int min_match() = 0; |
1761 virtual int max_match() = 0; | 1760 virtual int max_match() = 0; |
1762 virtual bool ContainsExpandedQuantifier() { | |
1763 return contains_expanded_quantifier_; | |
1764 } | |
1765 void set_contains_expanded_quantifier(bool value) { | |
1766 contains_expanded_quantifier_ = value; | |
1767 } | |
1768 // Returns the interval of registers used for captures within this | 1761 // Returns the interval of registers used for captures within this |
1769 // expression. | 1762 // expression. |
1770 virtual Interval CaptureRegisters() { return Interval::Empty(); } | 1763 virtual Interval CaptureRegisters() { return Interval::Empty(); } |
1771 virtual void AppendToText(RegExpText* text); | 1764 virtual void AppendToText(RegExpText* text); |
1772 SmartPointer<const char> ToString(); | 1765 SmartPointer<const char> ToString(); |
1773 #define MAKE_ASTYPE(Name) \ | 1766 #define MAKE_ASTYPE(Name) \ |
1774 virtual RegExp##Name* As##Name(); \ | 1767 virtual RegExp##Name* As##Name(); \ |
1775 virtual bool Is##Name(); | 1768 virtual bool Is##Name(); |
1776 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE) | 1769 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE) |
1777 #undef MAKE_ASTYPE | 1770 #undef MAKE_ASTYPE |
1778 | |
1779 protected: | |
1780 bool contains_expanded_quantifier_; | |
1781 }; | 1771 }; |
1782 | 1772 |
1783 | 1773 |
1784 class RegExpDisjunction: public RegExpTree { | 1774 class RegExpDisjunction: public RegExpTree { |
1785 public: | 1775 public: |
1786 explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives); | 1776 explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives); |
1787 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1777 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1788 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1778 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1789 RegExpNode* on_success); | 1779 RegExpNode* on_success); |
1790 virtual RegExpDisjunction* AsDisjunction(); | 1780 virtual RegExpDisjunction* AsDisjunction(); |
1791 virtual Interval CaptureRegisters(); | 1781 virtual Interval CaptureRegisters(); |
1792 virtual bool IsDisjunction(); | 1782 virtual bool IsDisjunction(); |
1793 virtual bool IsAnchoredAtStart(); | 1783 virtual bool IsAnchoredAtStart(); |
1794 virtual bool IsAnchoredAtEnd(); | 1784 virtual bool IsAnchoredAtEnd(); |
1795 virtual int min_match() { return min_match_; } | 1785 virtual int min_match() { return min_match_; } |
1796 virtual int max_match() { return max_match_; } | 1786 virtual int max_match() { return max_match_; } |
1797 virtual bool ContainsExpandedQuantifier(); | |
1798 ZoneList<RegExpTree*>* alternatives() { return alternatives_; } | 1787 ZoneList<RegExpTree*>* alternatives() { return alternatives_; } |
1799 private: | 1788 private: |
1800 ZoneList<RegExpTree*>* alternatives_; | 1789 ZoneList<RegExpTree*>* alternatives_; |
1801 int min_match_; | 1790 int min_match_; |
1802 int max_match_; | 1791 int max_match_; |
1803 }; | 1792 }; |
1804 | 1793 |
1805 | 1794 |
1806 class RegExpAlternative: public RegExpTree { | 1795 class RegExpAlternative: public RegExpTree { |
1807 public: | 1796 public: |
1808 explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes); | 1797 explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes); |
1809 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1798 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1810 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1799 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1811 RegExpNode* on_success); | 1800 RegExpNode* on_success); |
1812 virtual RegExpAlternative* AsAlternative(); | 1801 virtual RegExpAlternative* AsAlternative(); |
1813 virtual Interval CaptureRegisters(); | 1802 virtual Interval CaptureRegisters(); |
1814 virtual bool IsAlternative(); | 1803 virtual bool IsAlternative(); |
1815 virtual bool IsAnchoredAtStart(); | 1804 virtual bool IsAnchoredAtStart(); |
1816 virtual bool IsAnchoredAtEnd(); | 1805 virtual bool IsAnchoredAtEnd(); |
1817 virtual int min_match() { return min_match_; } | 1806 virtual int min_match() { return min_match_; } |
1818 virtual int max_match() { return max_match_; } | 1807 virtual int max_match() { return max_match_; } |
1819 virtual bool ContainsExpandedQuantifier(); | |
1820 ZoneList<RegExpTree*>* nodes() { return nodes_; } | 1808 ZoneList<RegExpTree*>* nodes() { return nodes_; } |
1821 private: | 1809 private: |
1822 ZoneList<RegExpTree*>* nodes_; | 1810 ZoneList<RegExpTree*>* nodes_; |
1823 int min_match_; | 1811 int min_match_; |
1824 int max_match_; | 1812 int max_match_; |
1825 }; | 1813 }; |
1826 | 1814 |
1827 | 1815 |
1828 class RegExpAssertion: public RegExpTree { | 1816 class RegExpAssertion: public RegExpTree { |
1829 public: | 1817 public: |
(...skipping 129 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1959 | 1947 |
1960 | 1948 |
1961 class RegExpQuantifier: public RegExpTree { | 1949 class RegExpQuantifier: public RegExpTree { |
1962 public: | 1950 public: |
1963 enum Type { GREEDY, NON_GREEDY, POSSESSIVE }; | 1951 enum Type { GREEDY, NON_GREEDY, POSSESSIVE }; |
1964 RegExpQuantifier(int min, int max, Type type, RegExpTree* body) | 1952 RegExpQuantifier(int min, int max, Type type, RegExpTree* body) |
1965 : body_(body), | 1953 : body_(body), |
1966 min_(min), | 1954 min_(min), |
1967 max_(max), | 1955 max_(max), |
1968 min_match_(min * body->min_match()), | 1956 min_match_(min * body->min_match()), |
1969 type_(type), | 1957 type_(type) { |
1970 contains_expanded_quantifier_(false) { | |
1971 if (max > 0 && body->max_match() > kInfinity / max) { | 1958 if (max > 0 && body->max_match() > kInfinity / max) { |
1972 max_match_ = kInfinity; | 1959 max_match_ = kInfinity; |
1973 } else { | 1960 } else { |
1974 max_match_ = max * body->max_match(); | 1961 max_match_ = max * body->max_match(); |
1975 } | 1962 } |
1976 } | 1963 } |
1977 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1964 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1978 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1965 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1979 RegExpNode* on_success); | 1966 RegExpNode* on_success); |
1980 static RegExpNode* ToNode(int min, | 1967 static RegExpNode* ToNode(int min, |
1981 int max, | 1968 int max, |
1982 bool is_greedy, | 1969 bool is_greedy, |
1983 RegExpTree* body, | 1970 RegExpTree* body, |
1984 RegExpCompiler* compiler, | 1971 RegExpCompiler* compiler, |
1985 RegExpNode* on_success, | 1972 RegExpNode* on_success, |
1986 bool not_at_start = false); | 1973 bool not_at_start = false); |
1987 virtual RegExpQuantifier* AsQuantifier(); | 1974 virtual RegExpQuantifier* AsQuantifier(); |
1988 virtual Interval CaptureRegisters(); | 1975 virtual Interval CaptureRegisters(); |
1989 virtual bool IsQuantifier(); | 1976 virtual bool IsQuantifier(); |
1990 virtual int min_match() { return min_match_; } | 1977 virtual int min_match() { return min_match_; } |
1991 virtual int max_match() { return max_match_; } | 1978 virtual int max_match() { return max_match_; } |
1992 virtual bool ContainsExpandedQuantifier() { | |
1993 return contains_expanded_quantifier_ || body_->ContainsExpandedQuantifier(); | |
1994 } | |
1995 int min() { return min_; } | 1979 int min() { return min_; } |
1996 int max() { return max_; } | 1980 int max() { return max_; } |
1997 bool is_possessive() { return type_ == POSSESSIVE; } | 1981 bool is_possessive() { return type_ == POSSESSIVE; } |
1998 bool is_non_greedy() { return type_ == NON_GREEDY; } | 1982 bool is_non_greedy() { return type_ == NON_GREEDY; } |
1999 bool is_greedy() { return type_ == GREEDY; } | 1983 bool is_greedy() { return type_ == GREEDY; } |
2000 RegExpTree* body() { return body_; } | 1984 RegExpTree* body() { return body_; } |
2001 | 1985 |
2002 private: | 1986 private: |
2003 RegExpTree* body_; | 1987 RegExpTree* body_; |
2004 int min_; | 1988 int min_; |
2005 int max_; | 1989 int max_; |
2006 int min_match_; | 1990 int min_match_; |
2007 int max_match_; | 1991 int max_match_; |
2008 Type type_; | 1992 Type type_; |
2009 bool contains_expanded_quantifier_; | |
2010 }; | 1993 }; |
2011 | 1994 |
2012 | 1995 |
2013 class RegExpCapture: public RegExpTree { | 1996 class RegExpCapture: public RegExpTree { |
2014 public: | 1997 public: |
2015 explicit RegExpCapture(RegExpTree* body, int index) | 1998 explicit RegExpCapture(RegExpTree* body, int index) |
2016 : body_(body), index_(index) { } | 1999 : body_(body), index_(index) { } |
2017 virtual void* Accept(RegExpVisitor* visitor, void* data); | 2000 virtual void* Accept(RegExpVisitor* visitor, void* data); |
2018 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 2001 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
2019 RegExpNode* on_success); | 2002 RegExpNode* on_success); |
2020 static RegExpNode* ToNode(RegExpTree* body, | 2003 static RegExpNode* ToNode(RegExpTree* body, |
2021 int index, | 2004 int index, |
2022 RegExpCompiler* compiler, | 2005 RegExpCompiler* compiler, |
2023 RegExpNode* on_success); | 2006 RegExpNode* on_success); |
2024 virtual RegExpCapture* AsCapture(); | 2007 virtual RegExpCapture* AsCapture(); |
2025 virtual bool IsAnchoredAtStart(); | 2008 virtual bool IsAnchoredAtStart(); |
2026 virtual bool IsAnchoredAtEnd(); | 2009 virtual bool IsAnchoredAtEnd(); |
2027 virtual Interval CaptureRegisters(); | 2010 virtual Interval CaptureRegisters(); |
2028 virtual bool IsCapture(); | 2011 virtual bool IsCapture(); |
2029 virtual int min_match() { return body_->min_match(); } | 2012 virtual int min_match() { return body_->min_match(); } |
2030 virtual int max_match() { return body_->max_match(); } | 2013 virtual int max_match() { return body_->max_match(); } |
2031 virtual bool ContainsExpandedQuantifier() { | |
2032 return contains_expanded_quantifier_ || body_->ContainsExpandedQuantifier(); | |
2033 } | |
2034 RegExpTree* body() { return body_; } | 2014 RegExpTree* body() { return body_; } |
2035 int index() { return index_; } | 2015 int index() { return index_; } |
2036 static int StartRegister(int index) { return index * 2; } | 2016 static int StartRegister(int index) { return index * 2; } |
2037 static int EndRegister(int index) { return index * 2 + 1; } | 2017 static int EndRegister(int index) { return index * 2 + 1; } |
2038 | 2018 |
2039 private: | 2019 private: |
2040 RegExpTree* body_; | 2020 RegExpTree* body_; |
2041 int index_; | 2021 int index_; |
2042 }; | 2022 }; |
2043 | 2023 |
(...skipping 11 matching lines...) Expand all Loading... |
2055 | 2035 |
2056 virtual void* Accept(RegExpVisitor* visitor, void* data); | 2036 virtual void* Accept(RegExpVisitor* visitor, void* data); |
2057 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 2037 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
2058 RegExpNode* on_success); | 2038 RegExpNode* on_success); |
2059 virtual RegExpLookahead* AsLookahead(); | 2039 virtual RegExpLookahead* AsLookahead(); |
2060 virtual Interval CaptureRegisters(); | 2040 virtual Interval CaptureRegisters(); |
2061 virtual bool IsLookahead(); | 2041 virtual bool IsLookahead(); |
2062 virtual bool IsAnchoredAtStart(); | 2042 virtual bool IsAnchoredAtStart(); |
2063 virtual int min_match() { return 0; } | 2043 virtual int min_match() { return 0; } |
2064 virtual int max_match() { return 0; } | 2044 virtual int max_match() { return 0; } |
2065 virtual bool ContainsExpandedQuantifier() { | |
2066 return contains_expanded_quantifier_ || body_->ContainsExpandedQuantifier(); | |
2067 } | |
2068 RegExpTree* body() { return body_; } | 2045 RegExpTree* body() { return body_; } |
2069 bool is_positive() { return is_positive_; } | 2046 bool is_positive() { return is_positive_; } |
2070 int capture_count() { return capture_count_; } | 2047 int capture_count() { return capture_count_; } |
2071 int capture_from() { return capture_from_; } | 2048 int capture_from() { return capture_from_; } |
2072 | 2049 |
2073 private: | 2050 private: |
2074 RegExpTree* body_; | 2051 RegExpTree* body_; |
2075 bool is_positive_; | 2052 bool is_positive_; |
2076 int capture_count_; | 2053 int capture_count_; |
2077 int capture_from_; | 2054 int capture_from_; |
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2153 | 2130 |
2154 private: | 2131 private: |
2155 Isolate* isolate_; | 2132 Isolate* isolate_; |
2156 bool stack_overflow_; | 2133 bool stack_overflow_; |
2157 }; | 2134 }; |
2158 | 2135 |
2159 | 2136 |
2160 } } // namespace v8::internal | 2137 } } // namespace v8::internal |
2161 | 2138 |
2162 #endif // V8_AST_H_ | 2139 #endif // V8_AST_H_ |
OLD | NEW |