1 /*
2 * Copyright (c) 2015, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /** \file
30 * \brief Alternations (foo|bar|baz).
31 */
32
33
34 #include "ComponentAlternation.h"
35
36 #include "buildstate.h"
37 #include "position.h"
38 #include "position_info.h"
39 #include "nfagraph/ng_builder.h"
40 #include "ue2common.h"
41
42 #include <algorithm>
43
44 using namespace std;
45
46 namespace ue2 {
47
ComponentAlternation()48 ComponentAlternation::ComponentAlternation() {
49 // empty
50 }
51
~ComponentAlternation()52 ComponentAlternation::~ComponentAlternation() {
53 // empty
54 }
55
ComponentAlternation(const ComponentAlternation & other)56 ComponentAlternation::ComponentAlternation(const ComponentAlternation &other)
57 : Component(other) {
58 for (const auto &c : other.children) {
59 assert(c);
60 children.push_back(unique_ptr<Component>(c->clone()));
61 }
62 }
63
clone() const64 ComponentAlternation * ComponentAlternation::clone() const {
65 return new ComponentAlternation(*this);
66 }
67
accept(ComponentVisitor & v)68 Component *ComponentAlternation::accept(ComponentVisitor &v) {
69 Component *c = v.visit(this);
70 if (c != this) {
71 v.post(this);
72 return c;
73 }
74
75 for (auto i = children.begin(), e = children.end(); i != e; ++i) {
76 Component *child = i->get();
77 c = (*i)->accept(v);
78 if (c != child) {
79 // Child has been replaced (new Component pointer) or we've been
80 // instructed to delete it (null).
81 i->reset(c);
82 }
83 }
84
85 // Remove deleted children.
86 children.erase(remove(children.begin(), children.end(), nullptr),
87 children.end());
88
89 v.post(this);
90 return this;
91 }
92
accept(ConstComponentVisitor & v) const93 void ComponentAlternation::accept(ConstComponentVisitor &v) const {
94 v.pre(*this);
95 for (auto i = children.begin(), e = children.end(); i != e; ++i) {
96 (*i)->accept(v);
97 if (i + 1 != e) {
98 v.during(*this);
99 }
100 }
101
102 v.post(*this);
103 }
104
append(unique_ptr<Component> component)105 void ComponentAlternation::append(unique_ptr<Component> component) {
106 children.push_back(move(component));
107 }
108
first() const109 vector<PositionInfo> ComponentAlternation::first() const {
110 // firsts come from all our subcomponents in position order. This will
111 // maintain left-to-right priority order.
112 vector<PositionInfo> firsts, subfirsts;
113
114 for (const auto &c : children) {
115 subfirsts = c->first();
116 firsts.insert(firsts.end(), subfirsts.begin(), subfirsts.end());
117 }
118 return firsts;
119 }
120
last() const121 vector<PositionInfo> ComponentAlternation::last() const {
122 vector<PositionInfo> lasts, sublasts;
123
124 for (const auto &c : children) {
125 sublasts = c->last();
126 lasts.insert(lasts.end(), sublasts.begin(), sublasts.end());
127 }
128 return lasts;
129 }
130
empty(void) const131 bool ComponentAlternation::empty(void) const {
132 // an alternation can be empty if any of its components are empty
133 for (const auto &c : children) {
134 if (c->empty()) {
135 return true;
136 }
137 }
138
139 return false;
140 }
141
notePositions(GlushkovBuildState & bs)142 void ComponentAlternation::notePositions(GlushkovBuildState &bs) {
143 u32 pb = bs.getBuilder().numVertices();
144 for (auto &c : children) {
145 c->notePositions(bs);
146 }
147 recordPosBounds(pb, bs.getBuilder().numVertices());
148 }
149
buildFollowSet(GlushkovBuildState & bs,const vector<PositionInfo> & lastPos)150 void ComponentAlternation::buildFollowSet(GlushkovBuildState &bs,
151 const vector<PositionInfo> &lastPos) {
152 for (auto &c : children) {
153 c->buildFollowSet(bs, lastPos);
154 }
155 }
156
checkEmbeddedStartAnchor(bool at_start) const157 bool ComponentAlternation::checkEmbeddedStartAnchor(bool at_start) const {
158 bool rv = at_start;
159 for (const auto &c : children) {
160 rv &= c->checkEmbeddedStartAnchor(at_start);
161 }
162
163 return rv;
164 }
165
checkEmbeddedEndAnchor(bool at_end) const166 bool ComponentAlternation::checkEmbeddedEndAnchor(bool at_end) const {
167 bool rv = at_end;
168 for (const auto &c : children) {
169 rv &= c->checkEmbeddedEndAnchor(at_end);
170 }
171
172 return rv;
173 }
174
vacuous_everywhere(void) const175 bool ComponentAlternation::vacuous_everywhere(void) const {
176 for (const auto &c : children) {
177 if (c->vacuous_everywhere()) {
178 return true;
179 }
180 }
181 return false;
182 }
183
optimise(bool connected_to_sds)184 void ComponentAlternation::optimise(bool connected_to_sds) {
185 for (auto &c : children) {
186 c->optimise(connected_to_sds);
187 }
188 }
189
190 } // namespace ue2
191