1/*
2 * Copyright (c) 2015-2017, 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: NFA Graph Builder: used by Glushkov construction to construct an
31 * NGHolder from a parsed expression.
32 */
33
34#include "ng_builder.h"
35
36#include "grey.h"
37#include "ng.h"
38#include "ng_util.h"
39#include "ue2common.h"
40#include "compiler/compiler.h" // for ParsedExpression
41#include "util/compile_error.h"
42#include "util/make_unique.h"
43
44#include <cassert>
45
46using namespace std;
47
48namespace ue2 {
49
50namespace {
51
52/** Concrete implementation of NFABuilder interface. */
53class NFABuilderImpl : public NFABuilder {
54public:
55 NFABuilderImpl(ReportManager &rm, const Grey &grey,
56 const ParsedExpression &expr);
57
58 ~NFABuilderImpl() override;
59
60 Position makePositions(size_t nPositions) override;
61 Position getStart() const override;
62 Position getStartDotStar() const override;
63 Position getAccept() const override;
64 Position getAcceptEOD() const override;
65
66 bool isSpecialState(Position p) const override;
67
68 void setNodeReportID(Position position, int offsetAdjust) override;
69 void addCharReach(Position position, const CharReach &cr) override;
70 void setAssertFlag(Position position, u32 flag) override;
71 u32 getAssertFlag(Position position) override;
72
73 void addVertex(Position p) override;
74
75 void addEdge(Position start, Position end) override;
76
77 bool hasEdge(Position start, Position end) const override;
78
79 u32 numVertices() const override { return vertIdx; }
80
81 void cloneRegion(Position first, Position last,
82 unsigned posOffset) override;
83
84 BuiltExpression getGraph() override;
85
86private:
87 /** fetch a vertex given its Position ID. */
88 NFAVertex getVertex(Position pos) const;
89
90 /** \brief Internal convenience function to add an edge (u, v). */
91 pair<NFAEdge, bool> addEdge(NFAVertex u, NFAVertex v);
92
93 /** \brief We use the ReportManager to hand out new internal reports. */
94 ReportManager &rm;
95
96 /** \brief Greybox: used for resource limits. */
97 const Grey &grey;
98
99 /** \brief Underlying graph. */
100 unique_ptr<NGHolder> graph;
101
102 /** \brief Underlying expression info. */
103 ExpressionInfo expr;
104
105 /** \brief mapping from position to vertex. Use \ref getVertex for access.
106 * */
107 vector<NFAVertex> id2vertex;
108
109 /** \brief Index of next vertex. */
110 u32 vertIdx;
111}; // class NFABuilderImpl
112
113} // namespace
114
115NFABuilderImpl::NFABuilderImpl(ReportManager &rm_in, const Grey &grey_in,
116 const ParsedExpression &parsed)
117 : rm(rm_in), grey(grey_in), graph(ue2::make_unique<NGHolder>()),
118 expr(parsed.expr), vertIdx(N_SPECIALS) {
119
120 // Reserve space for a reasonably-sized NFA
121 id2vertex.reserve(64);
122 id2vertex.resize(N_SPECIALS);
123 id2vertex[NODE_START] = graph->start;
124 id2vertex[NODE_START_DOTSTAR] = graph->startDs;
125 id2vertex[NODE_ACCEPT] = graph->accept;
126 id2vertex[NODE_ACCEPT_EOD] = graph->acceptEod;
127}
128
129NFABuilderImpl::~NFABuilderImpl() {
130 // empty
131}
132
133NFAVertex NFABuilderImpl::getVertex(Position pos) const {
134 assert(id2vertex.size() >= pos);
135 const NFAVertex v = id2vertex[pos];
136 assert(v != NGHolder::null_vertex());
137 assert((*graph)[v].index == pos);
138 return v;
139}
140
141void NFABuilderImpl::addVertex(Position pos) {
142 // Enforce resource limit.
143 if (pos > grey.limitGraphVertices) {
144 throw CompileError("Pattern too large.");
145 }
146
147 NFAVertex v = add_vertex(*graph);
148 if (id2vertex.size() <= pos) {
149 id2vertex.resize(pos + 1);
150 }
151 id2vertex[pos] = v;
152 (*graph)[v].index = pos;
153}
154
155BuiltExpression NFABuilderImpl::getGraph() {
156 DEBUG_PRINTF("built graph has %zu vertices and %zu edges\n",
157 num_vertices(*graph), num_edges(*graph));
158
159 if (num_edges(*graph) > grey.limitGraphEdges) {
160 throw CompileError("Pattern too large.");
161 }
162 if (num_vertices(*graph) > grey.limitGraphVertices) {
163 throw CompileError("Pattern too large.");
164 }
165
166 return { expr, move(graph) };
167}
168
169void NFABuilderImpl::setNodeReportID(Position pos, int offsetAdjust) {
170 Report ir = rm.getBasicInternalReport(expr, offsetAdjust);
171 DEBUG_PRINTF("setting report id on %u = (%u, %d, %u)\n",
172 pos, expr.report, offsetAdjust, ir.ekey);
173
174 NFAVertex v = getVertex(pos);
175 auto &reports = (*graph)[v].reports;
176 reports.clear();
177 reports.insert(rm.getInternalId(ir));
178}
179
180void NFABuilderImpl::addCharReach(Position pos, const CharReach &cr) {
181 NFAVertex v = getVertex(pos);
182 (*graph)[v].char_reach |= cr;
183}
184
185void NFABuilderImpl::setAssertFlag(Position pos, u32 flag) {
186 NFAVertex v = getVertex(pos);
187 (*graph)[v].assert_flags |= flag;
188}
189
190u32 NFABuilderImpl::getAssertFlag(Position pos) {
191 NFAVertex v = getVertex(pos);
192 return (*graph)[v].assert_flags;
193}
194
195pair<NFAEdge, bool> NFABuilderImpl::addEdge(NFAVertex u, NFAVertex v) {
196 // assert that the edge doesn't already exist
197 assert(edge(u, v, *graph).second == false);
198
199 return add_edge(u, v, *graph);
200}
201
202void NFABuilderImpl::addEdge(Position startPos, Position endPos) {
203 DEBUG_PRINTF("%u -> %u\n", startPos, endPos);
204 assert(startPos < vertIdx);
205 assert(endPos < vertIdx);
206
207 NFAVertex u = getVertex(startPos);
208 NFAVertex v = getVertex(endPos);
209
210 if ((u == graph->start || u == graph->startDs) && v == graph->startDs) {
211 /* standard special -> special edges already exist */
212 assert(edge(u, v, *graph).second == true);
213 return;
214 }
215
216 assert(edge(u, v, *graph).second == false);
217 addEdge(u, v);
218}
219
220bool NFABuilderImpl::hasEdge(Position startPos, Position endPos) const {
221 return edge(getVertex(startPos), getVertex(endPos), *graph).second;
222}
223
224Position NFABuilderImpl::getStart() const {
225 return NODE_START;
226}
227
228Position NFABuilderImpl::getStartDotStar() const {
229 return NODE_START_DOTSTAR;
230}
231
232Position NFABuilderImpl::getAccept() const {
233 return NODE_ACCEPT;
234}
235
236Position NFABuilderImpl::getAcceptEOD() const {
237 return NODE_ACCEPT_EOD;
238}
239
240bool NFABuilderImpl::isSpecialState(Position p) const {
241 return (p == NODE_START || p == NODE_START_DOTSTAR ||
242 p == NODE_ACCEPT || p == NODE_ACCEPT_EOD);
243}
244
245Position NFABuilderImpl::makePositions(size_t nPositions) {
246 Position base = vertIdx;
247 for (size_t i = 0; i < nPositions; i++) {
248 addVertex(vertIdx++);
249 }
250 DEBUG_PRINTF("built %zu positions from base %u\n", nPositions, base);
251 return base;
252}
253
254void NFABuilderImpl::cloneRegion(Position first, Position last, unsigned posOffset) {
255 NGHolder &g = *graph;
256 assert(posOffset > 0);
257
258 // walk the nodes between first and last and copy their vertex properties
259 DEBUG_PRINTF("cloning nodes in [%u, %u], offset %u\n", first, last,
260 posOffset);
261 for (Position i = first; i <= last; ++i) {
262 NFAVertex orig = getVertex(i);
263 Position destIdx = i + posOffset;
264 assert(destIdx < vertIdx);
265 NFAVertex dest = getVertex(destIdx);
266 g[dest] = g[orig]; // all properties
267 g[dest].index = destIdx;
268 }
269}
270
271unique_ptr<NFABuilder> makeNFABuilder(ReportManager &rm, const CompileContext &cc,
272 const ParsedExpression &expr) {
273 return ue2::make_unique<NFABuilderImpl>(rm, cc.grey, expr);
274}
275
276NFABuilder::~NFABuilder() { }
277
278} // namespace ue2
279