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 Functions for splitting NFAGraphs into LHS and RHS.
31 */
32#include "ng_split.h"
33
34#include "ng_holder.h"
35#include "ng_prune.h"
36#include "ng_util.h"
37#include "util/container.h"
38#include "util/graph.h"
39#include "util/graph_range.h"
40
41#include <map>
42#include <set>
43#include <vector>
44
45using namespace std;
46
47namespace ue2 {
48
49static
50void clearAccepts(NGHolder &g) {
51 for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
52 g[v].reports.clear();
53 }
54
55 for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
56 g[v].reports.clear();
57 }
58
59 clear_in_edges(g.accept, g);
60 clear_in_edges(g.acceptEod, g);
61 add_edge(g.accept, g.acceptEod, g);
62}
63
64static
65void filterSplitMap(const NGHolder &g,
66 unordered_map<NFAVertex, NFAVertex> *out_map) {
67 unordered_set<NFAVertex> verts;
68 insert(&verts, vertices(g));
69 auto it = out_map->begin();
70 while (it != out_map->end()) {
71 auto jt = it;
72 ++it;
73 if (!contains(verts, jt->second)) {
74 out_map->erase(jt);
75 }
76 }
77}
78
79static
80void splitLHS(const NGHolder &base, const vector<NFAVertex> &pivots,
81 const vector<NFAVertex> &rhs_pivots, NGHolder *lhs,
82 unordered_map<NFAVertex, NFAVertex> *lhs_map) {
83 assert(lhs && lhs_map);
84
85 cloneHolder(*lhs, base, lhs_map);
86
87 clearAccepts(*lhs);
88
89 for (auto pivot : pivots) {
90 DEBUG_PRINTF("pivot is %zu lv %zu lm %zu\n", base[pivot].index,
91 num_vertices(*lhs), lhs_map->size());
92 assert(contains(*lhs_map, pivot));
93
94 for (auto v : rhs_pivots) {
95 assert(contains(*lhs_map, v));
96 remove_edge((*lhs_map)[pivot], (*lhs_map)[v], *lhs);
97 }
98
99 (*lhs)[(*lhs_map)[pivot]].reports.insert(0);
100 add_edge((*lhs_map)[pivot], lhs->accept, *lhs);
101 }
102
103 /* should do the renumbering unconditionally as we know edges are already
104 * misnumbered */
105 pruneUseless(*lhs, false);
106 renumber_edges(*lhs);
107 renumber_vertices(*lhs);
108
109 filterSplitMap(*lhs, lhs_map);
110
111 switch (base.kind) {
112 case NFA_PREFIX:
113 case NFA_OUTFIX:
114 lhs->kind = NFA_PREFIX;
115 break;
116 case NFA_INFIX:
117 case NFA_SUFFIX:
118 lhs->kind = NFA_INFIX;
119 break;
120 case NFA_EAGER_PREFIX:
121 /* Current code should not be assigning eager until well after all the
122 * splitting is done. */
123 assert(0);
124 lhs->kind = NFA_EAGER_PREFIX;
125 break;
126 case NFA_REV_PREFIX:
127 case NFA_OUTFIX_RAW:
128 assert(0);
129 break;
130 }
131}
132
133void splitLHS(const NGHolder &base, NFAVertex pivot,
134 NGHolder *lhs, unordered_map<NFAVertex, NFAVertex> *lhs_map) {
135 vector<NFAVertex> pivots(1, pivot);
136 vector<NFAVertex> rhs_pivots;
137 insert(&rhs_pivots, rhs_pivots.end(), adjacent_vertices(pivot, base));
138 splitLHS(base, pivots, rhs_pivots, lhs, lhs_map);
139}
140
141void splitRHS(const NGHolder &base, const vector<NFAVertex> &pivots,
142 NGHolder *rhs, unordered_map<NFAVertex, NFAVertex> *rhs_map) {
143 assert(rhs && rhs_map);
144
145 cloneHolder(*rhs, base, rhs_map);
146
147 clear_out_edges(rhs->start, *rhs);
148 clear_out_edges(rhs->startDs, *rhs);
149 add_edge(rhs->start, rhs->startDs, *rhs);
150 add_edge(rhs->startDs, rhs->startDs, *rhs);
151
152 for (auto pivot : pivots) {
153 assert(contains(*rhs_map, pivot));
154 NFAEdge e = add_edge(rhs->start, (*rhs_map)[pivot], *rhs);
155 (*rhs)[e].tops.insert(DEFAULT_TOP);
156 }
157
158 /* should do the renumbering unconditionally as we know edges are already
159 * misnumbered */
160 pruneUseless(*rhs, false);
161 renumber_edges(*rhs);
162 renumber_vertices(*rhs);
163 filterSplitMap(*rhs, rhs_map);
164
165 switch (base.kind) {
166 case NFA_PREFIX:
167 case NFA_INFIX:
168 rhs->kind = NFA_INFIX;
169 break;
170 case NFA_SUFFIX:
171 case NFA_OUTFIX:
172 rhs->kind = NFA_SUFFIX;
173 break;
174 case NFA_EAGER_PREFIX:
175 /* Current code should not be assigning eager until well after all the
176 * splitting is done. */
177 assert(0);
178 rhs->kind = NFA_INFIX;
179 break;
180 case NFA_REV_PREFIX:
181 case NFA_OUTFIX_RAW:
182 assert(0);
183 break;
184 }
185}
186
187/** \brief Fills \a succ with the common successors of the vertices in \a
188 * pivots. */
189static
190void findCommonSuccessors(const NGHolder &g, const vector<NFAVertex> &pivots,
191 vector<NFAVertex> &succ) {
192 assert(!pivots.empty());
193
194 set<NFAVertex> adj;
195 set<NFAVertex> adj_temp;
196
197 insert(&adj, adjacent_vertices(pivots.at(0), g));
198
199 for (auto it = pivots.begin() + 1, ite = pivots.end(); it != ite; ++it) {
200 NFAVertex pivot = *it;
201 adj_temp.clear();
202 for (auto v : adjacent_vertices_range(pivot, g)) {
203 if (contains(adj, v)) {
204 adj_temp.insert(v);
205 }
206 }
207 adj.swap(adj_temp);
208 }
209
210 succ.insert(succ.end(), adj.begin(), adj.end());
211}
212
213void splitGraph(const NGHolder &base, const vector<NFAVertex> &pivots,
214 NGHolder *lhs, unordered_map<NFAVertex, NFAVertex> *lhs_map,
215 NGHolder *rhs, unordered_map<NFAVertex, NFAVertex> *rhs_map) {
216 DEBUG_PRINTF("splitting graph at %zu vertices\n", pivots.size());
217
218 assert(!has_parallel_edge(base));
219 assert(isCorrectlyTopped(base));
220
221 /* RHS pivots are built from the common set of successors of pivots. */
222 vector<NFAVertex> rhs_pivots;
223 findCommonSuccessors(base, pivots, rhs_pivots);
224
225 /* generate lhs */
226 splitLHS(base, pivots, rhs_pivots, lhs, lhs_map);
227
228 /* generate the rhs */
229 splitRHS(base, rhs_pivots, rhs, rhs_map);
230
231 assert(!has_parallel_edge(*lhs));
232 assert(!has_parallel_edge(*rhs));
233 assert(isCorrectlyTopped(*lhs));
234 assert(isCorrectlyTopped(*rhs));
235}
236
237void splitGraph(const NGHolder &base, NFAVertex pivot,
238 NGHolder *lhs, unordered_map<NFAVertex, NFAVertex> *lhs_map,
239 NGHolder *rhs, unordered_map<NFAVertex, NFAVertex> *rhs_map) {
240 vector<NFAVertex> pivots(1, pivot);
241 splitGraph(base, pivots, lhs, lhs_map, rhs, rhs_map);
242}
243
244} // namespace ue2
245