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
44using namespace std;
45
46namespace ue2 {
47
48ComponentAlternation::ComponentAlternation() {
49 // empty
50}
51
52ComponentAlternation::~ComponentAlternation() {
53 // empty
54}
55
56ComponentAlternation::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
64ComponentAlternation * ComponentAlternation::clone() const {
65 return new ComponentAlternation(*this);
66}
67
68Component *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
93void 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
105void ComponentAlternation::append(unique_ptr<Component> component) {
106 children.push_back(move(component));
107}
108
109vector<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
121vector<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
131bool 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
142void 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
150void ComponentAlternation::buildFollowSet(GlushkovBuildState &bs,
151 const vector<PositionInfo> &lastPos) {
152 for (auto &c : children) {
153 c->buildFollowSet(bs, lastPos);
154 }
155}
156
157bool 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
166bool 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
175bool 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
184void ComponentAlternation::optimise(bool connected_to_sds) {
185 for (auto &c : children) {
186 c->optimise(connected_to_sds);
187 }
188}
189
190} // namespace ue2
191