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 | |
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 | |
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 | |
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 | |
129 | NFABuilderImpl::~NFABuilderImpl() { |
130 | // empty |
131 | } |
132 | |
133 | 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 | |
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 | |
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 | |
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 | |
180 | void NFABuilderImpl::addCharReach(Position pos, const CharReach &cr) { |
181 | NFAVertex v = getVertex(pos); |
182 | (*graph)[v].char_reach |= cr; |
183 | } |
184 | |
185 | void NFABuilderImpl::setAssertFlag(Position pos, u32 flag) { |
186 | NFAVertex v = getVertex(pos); |
187 | (*graph)[v].assert_flags |= flag; |
188 | } |
189 | |
190 | u32 NFABuilderImpl::getAssertFlag(Position pos) { |
191 | NFAVertex v = getVertex(pos); |
192 | return (*graph)[v].assert_flags; |
193 | } |
194 | |
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 | |
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 | |
220 | bool NFABuilderImpl::hasEdge(Position startPos, Position endPos) const { |
221 | return edge(getVertex(startPos), getVertex(endPos), *graph).second; |
222 | } |
223 | |
224 | Position NFABuilderImpl::getStart() const { |
225 | return NODE_START; |
226 | } |
227 | |
228 | Position NFABuilderImpl::getStartDotStar() const { |
229 | return NODE_START_DOTSTAR; |
230 | } |
231 | |
232 | Position NFABuilderImpl::getAccept() const { |
233 | return NODE_ACCEPT; |
234 | } |
235 | |
236 | Position NFABuilderImpl::getAcceptEOD() const { |
237 | return NODE_ACCEPT_EOD; |
238 | } |
239 | |
240 | 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 | |
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 | |
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 | |
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 | |
276 | NFABuilder::~NFABuilder() { } |
277 | |
278 | } // namespace ue2 |
279 | |