/src/mozilla-central/js/src/irregexp/RegExpAST.cpp

Source (jump to first uncovered line)
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99: */

// Copyright 2012 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "irregexp/RegExpAST.h"

using namespace js;
using namespace js::irregexp;

#define MAKE_ACCEPT(Name)                                            \
  void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
    return visitor->Visit##Name(this, data);                         \
  }
FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
#undef MAKE_ACCEPT

#define MAKE_TYPE_CASE(Name)                                         \
  RegExp##Name* RegExpTree::As##Name() {                             \
    return nullptr;                                                  \
  }                                                                  \
  bool RegExpTree::Is##Name() { return false; }
FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
#undef MAKE_TYPE_CASE

#define MAKE_TYPE_CASE(Name)                                        \
  RegExp##Name* RegExp##Name::As##Name() {                          \
    return this;                                                    \
  }                                                                 \
  bool RegExp##Name::Is##Name() { return true; }
FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
#undef MAKE_TYPE_CASE

static Interval
ListCaptureRegisters(const RegExpTreeVector& children)
{
    Interval result = Interval::Empty();
    for (size_t i = 0; i < children.length(); i++)
        result = result.Union(children[i]->CaptureRegisters());
    return result;
}

// ----------------------------------------------------------------------------
// RegExpDisjunction

RegExpDisjunction::RegExpDisjunction(RegExpTreeVector* alternatives)
  : alternatives_(alternatives)
{
    MOZ_ASSERT(alternatives->length() > 1);
    RegExpTree* first_alternative = (*alternatives)[0];
    min_match_ = first_alternative->min_match();
    max_match_ = first_alternative->max_match();
    for (size_t i = 1; i < alternatives->length(); i++) {
        RegExpTree* alternative = (*alternatives)[i];
        min_match_ = Min(min_match_, alternative->min_match());
        max_match_ = Max(max_match_, alternative->max_match());
    }
}

Interval
RegExpDisjunction::CaptureRegisters()
{
    return ListCaptureRegisters(alternatives());
}

bool
RegExpDisjunction::IsAnchoredAtStart()
{
    const RegExpTreeVector& alternatives = this->alternatives();
    for (size_t i = 0; i < alternatives.length(); i++) {
        if (!alternatives[i]->IsAnchoredAtStart())
            return false;
    }
    return true;
}

bool
RegExpDisjunction::IsAnchoredAtEnd()
{
    const RegExpTreeVector& alternatives = this->alternatives();
    for (size_t i = 0; i < alternatives.length(); i++) {
        if (!alternatives[i]->IsAnchoredAtEnd())
            return false;
    }
    return true;
}

// ----------------------------------------------------------------------------
// RegExpAlternative

static int IncreaseBy(int previous, int increase)
{
    if (RegExpTree::kInfinity - previous < increase)
        return RegExpTree::kInfinity;
    return previous + increase;
}

RegExpAlternative::RegExpAlternative(RegExpTreeVector* nodes)
  : nodes_(nodes),
    min_match_(0),
    max_match_(0)
{
    MOZ_ASSERT(nodes->length() > 1);
    for (size_t i = 0; i < nodes->length(); i++) {
        RegExpTree* node = (*nodes)[i];
        int node_min_match = node->min_match();
        min_match_ = IncreaseBy(min_match_, node_min_match);
        int node_max_match = node->max_match();
        max_match_ = IncreaseBy(max_match_, node_max_match);
    }
}

Interval
RegExpAlternative::CaptureRegisters()
{
    return ListCaptureRegisters(nodes());
}

bool
RegExpAlternative::IsAnchoredAtStart()
{
    const RegExpTreeVector& nodes = this->nodes();
    for (size_t i = 0; i < nodes.length(); i++) {
        RegExpTree* node = nodes[i];
        if (node->IsAnchoredAtStart()) { return true; }
        if (node->max_match() > 0) { return false; }
    }
    return false;
}

bool
RegExpAlternative::IsAnchoredAtEnd()
{
    const RegExpTreeVector& nodes = this->nodes();
    for (int i = nodes.length() - 1; i >= 0; i--) {
        RegExpTree* node = nodes[i];
        if (node->IsAnchoredAtEnd()) { return true; }
        if (node->max_match() > 0) { return false; }
    }
    return false;
}

// ----------------------------------------------------------------------------
// RegExpAssertion

bool
RegExpAssertion::IsAnchoredAtStart()
{
    return assertion_type() == RegExpAssertion::START_OF_INPUT;
}

bool
RegExpAssertion::IsAnchoredAtEnd()
{
    return assertion_type() == RegExpAssertion::END_OF_INPUT;
}

// ----------------------------------------------------------------------------
// RegExpCharacterClass

void
RegExpCharacterClass::AppendToText(RegExpText* text)
{
    text->AddElement(TextElement::CharClass(this));
}

CharacterRangeVector&
CharacterSet::ranges(LifoAlloc* alloc)
{
    if (ranges_ == nullptr) {
        ranges_ = alloc->newInfallible<CharacterRangeVector>(*alloc);
        CharacterRange::AddClassEscape(alloc, standard_set_type_, ranges_);
    }
    return *ranges_;
}

// ----------------------------------------------------------------------------
// RegExpAtom

void
RegExpAtom::AppendToText(RegExpText* text)
{
    text->AddElement(TextElement::Atom(this));
}

// ----------------------------------------------------------------------------
// RegExpText

void
RegExpText::AppendToText(RegExpText* text)
{
    for (size_t i = 0; i < elements().length(); i++)
        text->AddElement(elements()[i]);
}

// ----------------------------------------------------------------------------
// RegExpQuantifier

Interval
RegExpQuantifier::CaptureRegisters()
{
    return body()->CaptureRegisters();
}

// ----------------------------------------------------------------------------
// RegExpCapture

bool
RegExpCapture::IsAnchoredAtStart()
{
    return body()->IsAnchoredAtStart();
}

bool
RegExpCapture::IsAnchoredAtEnd()
{
    return body()->IsAnchoredAtEnd();
}

Interval
RegExpCapture::CaptureRegisters()
{
    Interval self(StartRegister(index()), EndRegister(index()));
    return self.Union(body()->CaptureRegisters());
}

// ----------------------------------------------------------------------------
// RegExpLookahead

Interval
RegExpLookahead::CaptureRegisters()
{
    return body()->CaptureRegisters();
}

bool
RegExpLookahead::IsAnchoredAtStart()
{
    return is_positive() && body()->IsAnchoredAtStart();
}

Coverage Report

Created: 2018-09-25 14:53

Line	Count	Source (jump to first uncovered line)
1		/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 --
2		* vim: set ts=8 sts=4 et sw=4 tw=99: */
3
4		// Copyright 2012 the V8 project authors. All rights reserved.
5		// Redistribution and use in source and binary forms, with or without
6		// modification, are permitted provided that the following conditions are
7		// met:
8		//
9		// * Redistributions of source code must retain the above copyright
10		// notice, this list of conditions and the following disclaimer.
11		// * Redistributions in binary form must reproduce the above
12		// copyright notice, this list of conditions and the following
13		// disclaimer in the documentation and/or other materials provided
14		// with the distribution.
15		// * Neither the name of Google Inc. nor the names of its
16		// contributors may be used to endorse or promote products derived
17		// from this software without specific prior written permission.
18		//
19		// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20		// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21		// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22		// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23		// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24		// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25		// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26		// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27		// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28		// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29		// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31		#include "irregexp/RegExpAST.h"
32
33		using namespace js;
34		using namespace js::irregexp;
35
36		#define MAKE_ACCEPT(Name) \
37	0	void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \
38	0	return visitor->Visit##Name(this, data); \
39	0	} Unexecuted instantiation: js::irregexp::RegExpDisjunction::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpAlternative::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpAssertion::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpCharacterClass::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpAtom::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpQuantifier::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpCapture::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpLookahead::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpBackReference::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpEmpty::Accept(js::irregexp::RegExpVisitor, void) Unexecuted instantiation: js::irregexp::RegExpText::Accept(js::irregexp::RegExpVisitor, void)
40		FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
41		#undef MAKE_ACCEPT
42
43		#define MAKE_TYPE_CASE(Name) \
44	0	RegExp##Name* RegExpTree::As##Name() { \
45	0	return nullptr; \
46	0	} \ Unexecuted instantiation: js::irregexp::RegExpTree::AsDisjunction() Unexecuted instantiation: js::irregexp::RegExpTree::AsAlternative() Unexecuted instantiation: js::irregexp::RegExpTree::AsAssertion() Unexecuted instantiation: js::irregexp::RegExpTree::AsCharacterClass() Unexecuted instantiation: js::irregexp::RegExpTree::AsAtom() Unexecuted instantiation: js::irregexp::RegExpTree::AsQuantifier() Unexecuted instantiation: js::irregexp::RegExpTree::AsCapture() Unexecuted instantiation: js::irregexp::RegExpTree::AsLookahead() Unexecuted instantiation: js::irregexp::RegExpTree::AsBackReference() Unexecuted instantiation: js::irregexp::RegExpTree::AsEmpty() Unexecuted instantiation: js::irregexp::RegExpTree::AsText()
47	0	bool RegExpTree::Is##Name() { return false; } Unexecuted instantiation: js::irregexp::RegExpTree::IsDisjunction() Unexecuted instantiation: js::irregexp::RegExpTree::IsAlternative() Unexecuted instantiation: js::irregexp::RegExpTree::IsAssertion() Unexecuted instantiation: js::irregexp::RegExpTree::IsCharacterClass() Unexecuted instantiation: js::irregexp::RegExpTree::IsAtom() Unexecuted instantiation: js::irregexp::RegExpTree::IsQuantifier() Unexecuted instantiation: js::irregexp::RegExpTree::IsCapture() Unexecuted instantiation: js::irregexp::RegExpTree::IsLookahead() Unexecuted instantiation: js::irregexp::RegExpTree::IsBackReference() Unexecuted instantiation: js::irregexp::RegExpTree::IsEmpty() Unexecuted instantiation: js::irregexp::RegExpTree::IsText()
48		FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
49		#undef MAKE_TYPE_CASE
50
51		#define MAKE_TYPE_CASE(Name) \
52	0	RegExp##Name* RegExp##Name::As##Name() { \
53	0	return this; \
54	0	} \ Unexecuted instantiation: js::irregexp::RegExpDisjunction::AsDisjunction() Unexecuted instantiation: js::irregexp::RegExpAlternative::AsAlternative() Unexecuted instantiation: js::irregexp::RegExpAssertion::AsAssertion() Unexecuted instantiation: js::irregexp::RegExpCharacterClass::AsCharacterClass() Unexecuted instantiation: js::irregexp::RegExpAtom::AsAtom() Unexecuted instantiation: js::irregexp::RegExpQuantifier::AsQuantifier() Unexecuted instantiation: js::irregexp::RegExpCapture::AsCapture() Unexecuted instantiation: js::irregexp::RegExpLookahead::AsLookahead() Unexecuted instantiation: js::irregexp::RegExpBackReference::AsBackReference() Unexecuted instantiation: js::irregexp::RegExpEmpty::AsEmpty() Unexecuted instantiation: js::irregexp::RegExpText::AsText()
55	0	bool RegExp##Name::Is##Name() { return true; } Unexecuted instantiation: js::irregexp::RegExpDisjunction::IsDisjunction() Unexecuted instantiation: js::irregexp::RegExpAlternative::IsAlternative() Unexecuted instantiation: js::irregexp::RegExpAssertion::IsAssertion() Unexecuted instantiation: js::irregexp::RegExpCharacterClass::IsCharacterClass() Unexecuted instantiation: js::irregexp::RegExpAtom::IsAtom() Unexecuted instantiation: js::irregexp::RegExpQuantifier::IsQuantifier() Unexecuted instantiation: js::irregexp::RegExpCapture::IsCapture() Unexecuted instantiation: js::irregexp::RegExpLookahead::IsLookahead() Unexecuted instantiation: js::irregexp::RegExpBackReference::IsBackReference() Unexecuted instantiation: js::irregexp::RegExpEmpty::IsEmpty() Unexecuted instantiation: js::irregexp::RegExpText::IsText()
56		FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
57		#undef MAKE_TYPE_CASE
58
59		static Interval
60		ListCaptureRegisters(const RegExpTreeVector& children)
61	0	{
62	0	Interval result = Interval::Empty();
63	0	for (size_t i = 0; i < children.length(); i++)
64	0	result = result.Union(children[i]->CaptureRegisters());
65	0	return result;
66	0	}
67
68		// ----------------------------------------------------------------------------
69		// RegExpDisjunction
70
71		RegExpDisjunction::RegExpDisjunction(RegExpTreeVector* alternatives)
72		: alternatives_(alternatives)
73	0	{
74	0	MOZ_ASSERT(alternatives->length() > 1);
75	0	RegExpTree* first_alternative = (*alternatives)[0];
76	0	min_match_ = first_alternative->min_match();
77	0	max_match_ = first_alternative->max_match();
78	0	for (size_t i = 1; i < alternatives->length(); i++) {
79	0	RegExpTree* alternative = (*alternatives)[i];
80	0	min_match_ = Min(min_match_, alternative->min_match());
81	0	max_match_ = Max(max_match_, alternative->max_match());
82	0	}
83	0	}
84
85		Interval
86		RegExpDisjunction::CaptureRegisters()
87	0	{
88	0	return ListCaptureRegisters(alternatives());
89	0	}
90
91		bool
92		RegExpDisjunction::IsAnchoredAtStart()
93	0	{
94	0	const RegExpTreeVector& alternatives = this->alternatives();
95	0	for (size_t i = 0; i < alternatives.length(); i++) {
96	0	if (!alternatives[i]->IsAnchoredAtStart())
97	0	return false;
98	0	}
99	0	return true;
100	0	}
101
102		bool
103		RegExpDisjunction::IsAnchoredAtEnd()
104	0	{
105	0	const RegExpTreeVector& alternatives = this->alternatives();
106	0	for (size_t i = 0; i < alternatives.length(); i++) {
107	0	if (!alternatives[i]->IsAnchoredAtEnd())
108	0	return false;
109	0	}
110	0	return true;
111	0	}
112
113		// ----------------------------------------------------------------------------
114		// RegExpAlternative
115
116		static int IncreaseBy(int previous, int increase)
117	0	{
118	0	if (RegExpTree::kInfinity - previous < increase)
119	0	return RegExpTree::kInfinity;
120	0	return previous + increase;
121	0	}
122
123		RegExpAlternative::RegExpAlternative(RegExpTreeVector* nodes)
124		: nodes_(nodes),
125		min_match_(0),
126		max_match_(0)
127	0	{
128	0	MOZ_ASSERT(nodes->length() > 1);
129	0	for (size_t i = 0; i < nodes->length(); i++) {
130	0	RegExpTree* node = (*nodes)[i];
131	0	int node_min_match = node->min_match();
132	0	min_match_ = IncreaseBy(min_match_, node_min_match);
133	0	int node_max_match = node->max_match();
134	0	max_match_ = IncreaseBy(max_match_, node_max_match);
135	0	}
136	0	}
137
138		Interval
139		RegExpAlternative::CaptureRegisters()
140	0	{
141	0	return ListCaptureRegisters(nodes());
142	0	}
143
144		bool
145		RegExpAlternative::IsAnchoredAtStart()
146	0	{
147	0	const RegExpTreeVector& nodes = this->nodes();
148	0	for (size_t i = 0; i < nodes.length(); i++) {
149	0	RegExpTree* node = nodes[i];
150	0	if (node->IsAnchoredAtStart()) { return true; }
151	0	if (node->max_match() > 0) { return false; }
152	0	}
153	0	return false;
154	0	}
155
156		bool
157		RegExpAlternative::IsAnchoredAtEnd()
158	0	{
159	0	const RegExpTreeVector& nodes = this->nodes();
160	0	for (int i = nodes.length() - 1; i >= 0; i--) {
161	0	RegExpTree* node = nodes[i];
162	0	if (node->IsAnchoredAtEnd()) { return true; }
163	0	if (node->max_match() > 0) { return false; }
164	0	}
165	0	return false;
166	0	}
167
168		// ----------------------------------------------------------------------------
169		// RegExpAssertion
170
171		bool
172		RegExpAssertion::IsAnchoredAtStart()
173	0	{
174	0	return assertion_type() == RegExpAssertion::START_OF_INPUT;
175	0	}
176
177		bool
178		RegExpAssertion::IsAnchoredAtEnd()
179	0	{
180	0	return assertion_type() == RegExpAssertion::END_OF_INPUT;
181	0	}
182
183		// ----------------------------------------------------------------------------
184		// RegExpCharacterClass
185
186		void
187		RegExpCharacterClass::AppendToText(RegExpText* text)
188	0	{
189	0	text->AddElement(TextElement::CharClass(this));
190	0	}
191
192		CharacterRangeVector&
193		CharacterSet::ranges(LifoAlloc* alloc)
194	0	{
195	0	if (ranges_ == nullptr) {
196	0	ranges_ = alloc->newInfallible<CharacterRangeVector>(*alloc);
197	0	CharacterRange::AddClassEscape(alloc, standard_set_type_, ranges_);
198	0	}
199	0	return *ranges_;
200	0	}
201
202		// ----------------------------------------------------------------------------
203		// RegExpAtom
204
205		void
206		RegExpAtom::AppendToText(RegExpText* text)
207	0	{
208	0	text->AddElement(TextElement::Atom(this));
209	0	}
210
211		// ----------------------------------------------------------------------------
212		// RegExpText
213
214		void
215		RegExpText::AppendToText(RegExpText* text)
216	0	{
217	0	for (size_t i = 0; i < elements().length(); i++)
218	0	text->AddElement(elements()[i]);
219	0	}
220
221		// ----------------------------------------------------------------------------
222		// RegExpQuantifier
223
224		Interval
225		RegExpQuantifier::CaptureRegisters()
226	0	{
227	0	return body()->CaptureRegisters();
228	0	}
229
230		// ----------------------------------------------------------------------------
231		// RegExpCapture
232
233		bool
234		RegExpCapture::IsAnchoredAtStart()
235	0	{
236	0	return body()->IsAnchoredAtStart();
237	0	}
238
239		bool
240		RegExpCapture::IsAnchoredAtEnd()
241	0	{
242	0	return body()->IsAnchoredAtEnd();
243	0	}
244
245		Interval
246		RegExpCapture::CaptureRegisters()
247	0	{
248	0	Interval self(StartRegister(index()), EndRegister(index()));
249	0	return self.Union(body()->CaptureRegisters());
250	0	}
251
252		// ----------------------------------------------------------------------------
253		// RegExpLookahead
254
255		Interval
256		RegExpLookahead::CaptureRegisters()
257	0	{
258	0	return body()->CaptureRegisters();
259	0	}
260
261		bool
262		RegExpLookahead::IsAnchoredAtStart()
263	0	{
264	0	return is_positive() && body()->IsAnchoredAtStart();
265	0	}