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 | |
45 | using namespace std; |
46 | |
47 | namespace ue2 { |
48 | |
49 | static |
50 | void 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 | |
64 | static |
65 | void 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 | |
79 | static |
80 | void 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 | |
133 | void 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 | |
141 | void 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. */ |
189 | static |
190 | void 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 | |
213 | void 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 | |
237 | void 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 | |