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
46 using namespace std;
47
48 namespace ue2 {
49
50 namespace {
51
52 /** Concrete implementation of NFABuilder interface. */
53 class NFABuilderImpl : public NFABuilder {
54 public:
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
numVertices() const79 u32 numVertices() const override { return vertIdx; }
80
81 void cloneRegion(Position first, Position last,
82 unsigned posOffset) override;
83
84 BuiltExpression getGraph() override;
85
86 private:
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
NFABuilderImpl(ReportManager & rm_in,const Grey & grey_in,const ParsedExpression & parsed)115 NFABuilderImpl::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
~NFABuilderImpl()129 NFABuilderImpl::~NFABuilderImpl() {
130 // empty
131 }
132
getVertex(Position pos) const133 NFAVertex 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
addVertex(Position pos)141 void 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
getGraph()155 BuiltExpression 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
setNodeReportID(Position pos,int offsetAdjust)169 void 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
addCharReach(Position pos,const CharReach & cr)180 void NFABuilderImpl::addCharReach(Position pos, const CharReach &cr) {
181 NFAVertex v = getVertex(pos);
182 (*graph)[v].char_reach |= cr;
183 }
184
setAssertFlag(Position pos,u32 flag)185 void NFABuilderImpl::setAssertFlag(Position pos, u32 flag) {
186 NFAVertex v = getVertex(pos);
187 (*graph)[v].assert_flags |= flag;
188 }
189
getAssertFlag(Position pos)190 u32 NFABuilderImpl::getAssertFlag(Position pos) {
191 NFAVertex v = getVertex(pos);
192 return (*graph)[v].assert_flags;
193 }
194
addEdge(NFAVertex u,NFAVertex v)195 pair<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
addEdge(Position startPos,Position endPos)202 void 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
hasEdge(Position startPos,Position endPos) const220 bool NFABuilderImpl::hasEdge(Position startPos, Position endPos) const {
221 return edge(getVertex(startPos), getVertex(endPos), *graph).second;
222 }
223
getStart() const224 Position NFABuilderImpl::getStart() const {
225 return NODE_START;
226 }
227
getStartDotStar() const228 Position NFABuilderImpl::getStartDotStar() const {
229 return NODE_START_DOTSTAR;
230 }
231
getAccept() const232 Position NFABuilderImpl::getAccept() const {
233 return NODE_ACCEPT;
234 }
235
getAcceptEOD() const236 Position NFABuilderImpl::getAcceptEOD() const {
237 return NODE_ACCEPT_EOD;
238 }
239
isSpecialState(Position p) const240 bool NFABuilderImpl::isSpecialState(Position p) const {
241 return (p == NODE_START || p == NODE_START_DOTSTAR ||
242 p == NODE_ACCEPT || p == NODE_ACCEPT_EOD);
243 }
244
makePositions(size_t nPositions)245 Position 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
cloneRegion(Position first,Position last,unsigned posOffset)254 void 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
makeNFABuilder(ReportManager & rm,const CompileContext & cc,const ParsedExpression & expr)271 unique_ptr<NFABuilder> makeNFABuilder(ReportManager &rm, const CompileContext &cc,
272 const ParsedExpression &expr) {
273 return ue2::make_unique<NFABuilderImpl>(rm, cc.grey, expr);
274 }
275
~NFABuilder()276 NFABuilder::~NFABuilder() { }
277
278 } // namespace ue2
279