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 Region analysis.
31 *
32 * Definition: a \a region is a subset of vertices in a graph such that:
33 * - the edges entering the region are a cutset of the graph
34 * - for every in-edge (u, v) to the region there exist edges (u, w) for all
35 * w in {w : w in region and w has an in-edge}
36 * - the regions in a graph partition the graph
37 *
38 * Note:
39 * - we partition a graph into the maximal number of regions
40 * - similar properties for exit edges should hold as a consequence
41 * - graph == sequence of regions
42 * - a region is considered to have an epsilon vertex to allow jumps
43 * - vertices which only lead to back edges need to be floated up in the topo
44 * order
45 *
46 * Algorithm overview:
47 * -# topo-order over the DAG skeleton;
48 * -# incrementally add vertices to the current region until the boundary edges
49 * form a valid cut-set;
50 * -# for each back-edge, if the source and target are in different regions,
51 * merge the regions (and all intervening regions) into a common region.
52 */
53#include "ng_region.h"
54
55#include "ng_holder.h"
56#include "ng_util.h"
57#include "ue2common.h"
58#include "util/container.h"
59#include "util/flat_containers.h"
60#include "util/graph_range.h"
61#include "util/graph_small_color_map.h"
62
63#include <set>
64#include <utility>
65#include <vector>
66
67#include <boost/graph/filtered_graph.hpp>
68#include <boost/graph/topological_sort.hpp>
69
70using namespace std;
71
72namespace ue2 {
73
74using BackEdgeSet = unordered_set<NFAEdge>;
75using AcyclicGraph =
76 boost::filtered_graph<NGHolder, bad_edge_filter<BackEdgeSet>>;
77
78namespace {
79struct exit_info {
80 explicit exit_info(NFAVertex v) : exit(v) {}
81
82 NFAVertex exit;
83 flat_set<NFAVertex> open;
84};
85}
86
87static
88void checkAndAddExitCandidate(const AcyclicGraph &g,
89 const unordered_set<NFAVertex> &r, NFAVertex v,
90 vector<exit_info> &exits) {
91 exit_info v_exit(v);
92 auto &open = v_exit.open;
93
94 /* find the set of vertices reachable from v which are not in r */
95 for (auto w : adjacent_vertices_range(v, g)) {
96 if (!contains(r, w)) {
97 open.insert(w);
98 }
99 }
100
101 if (!open.empty()) {
102 DEBUG_PRINTF("exit %zu\n", g[v].index);
103 exits.push_back(move(v_exit));
104 }
105}
106
107static
108void findExits(const AcyclicGraph &g, const unordered_set<NFAVertex> &r,
109 vector<exit_info> &exits) {
110 exits.clear();
111 for (auto v : r) {
112 checkAndAddExitCandidate(g, r, v, exits);
113 }
114}
115
116static
117void refineExits(const AcyclicGraph &g, const unordered_set<NFAVertex> &r,
118 NFAVertex new_v, vector<exit_info> &exits) {
119 /* new_v is no long an open edge */
120 for (auto &exit : exits) {
121 exit.open.erase(new_v);
122 }
123
124 /* no open edges: no longer an exit */
125 exits.erase(remove_if(exits.begin(), exits.end(),
126 [&](const exit_info &exit) { return exit.open.empty(); }),
127 exits.end());
128
129 checkAndAddExitCandidate(g, r, new_v, exits);
130}
131
132/** the set of exits from a candidate region are valid if: FIXME: document
133 */
134static
135bool exitValid(UNUSED const AcyclicGraph &g, const vector<exit_info> &exits,
136 const flat_set<NFAVertex> &open_jumps) {
137 if (exits.empty() || (exits.size() < 2 && open_jumps.empty())) {
138 return true;
139 }
140 if (exits.size() == 1 && open_jumps.size() == 1) {
141 DEBUG_PRINTF("oj %zu, e %zu\n", g[*open_jumps.begin()].index,
142 g[exits[0].exit].index);
143 if (*open_jumps.begin() == exits[0].exit) {
144 return true;
145 }
146 }
147
148 assert(!exits.empty());
149 const auto &enters = exits.front().open;
150
151 if (!open_jumps.empty() && enters != open_jumps) {
152 return false;
153 }
154
155 for (auto it = begin(exits) + 1; it != end(exits); ++it) {
156 if (it->open != enters) {
157 return false;
158 }
159 }
160
161 return true;
162}
163
164static
165void setRegion(const unordered_set<NFAVertex> &r, u32 rid,
166 unordered_map<NFAVertex, u32> &regions) {
167 for (auto v : r) {
168 regions[v] = rid;
169 }
170}
171
172static
173void buildInitialCandidate(const AcyclicGraph &g,
174 vector<NFAVertex>::const_reverse_iterator &it,
175 const vector<NFAVertex>::const_reverse_iterator &ite,
176 unordered_set<NFAVertex> &candidate,
177 /* in exits of prev region;
178 * out exits from candidate */
179 vector<exit_info> &exits,
180 flat_set<NFAVertex> &open_jumps) {
181 if (it == ite) {
182 candidate.clear();
183 exits.clear();
184 return;
185 }
186
187 if (exits.empty()) {
188 DEBUG_PRINTF("odd\n");
189 candidate.clear();
190 DEBUG_PRINTF("adding %zu to initial\n", g[*it].index);
191 candidate.insert(*it);
192 open_jumps.erase(*it);
193 checkAndAddExitCandidate(g, candidate, *it, exits);
194 ++it;
195 return;
196 }
197
198 // Note: findExits() will clear exits, so it's safe to mutate/move its
199 // elements here.
200 auto &enters = exits.front().open;
201 candidate.clear();
202
203 for (; it != ite; ++it) {
204 DEBUG_PRINTF("adding %zu to initial\n", g[*it].index);
205 candidate.insert(*it);
206 if (contains(enters, *it)) {
207 break;
208 }
209 }
210
211 if (it != ite) {
212 enters.erase(*it);
213 open_jumps = move(enters);
214 DEBUG_PRINTF("oj size = %zu\n", open_jumps.size());
215 ++it;
216 } else {
217 open_jumps.clear();
218 }
219
220 findExits(g, candidate, exits);
221}
222
223static
224void findDagLeaders(const NGHolder &h, const AcyclicGraph &g,
225 const vector<NFAVertex> &topo,
226 unordered_map<NFAVertex, u32> &regions) {
227 assert(!topo.empty());
228 u32 curr_id = 0;
229 auto t_it = topo.rbegin();
230 unordered_set<NFAVertex> candidate;
231 flat_set<NFAVertex> open_jumps;
232 DEBUG_PRINTF("adding %zu to current\n", g[*t_it].index);
233 assert(t_it != topo.rend());
234 candidate.insert(*t_it++);
235 DEBUG_PRINTF("adding %zu to current\n", g[*t_it].index);
236 assert(t_it != topo.rend());
237 candidate.insert(*t_it++);
238
239 vector<exit_info> exits;
240 findExits(g, candidate, exits);
241
242 while (t_it != topo.rend()) {
243 assert(!candidate.empty());
244
245 if (exitValid(g, exits, open_jumps)) {
246 if (contains(candidate, h.accept) && !open_jumps.empty()) {
247 /* we have tried to make an optional region containing accept as
248 * we have an open jump to eod. This candidate region needs to
249 * be put in with the previous region. */
250 curr_id--;
251 DEBUG_PRINTF("merging in with region %u\n", curr_id);
252 } else {
253 DEBUG_PRINTF("setting region %u\n", curr_id);
254 }
255 setRegion(candidate, curr_id++, regions);
256 buildInitialCandidate(g, t_it, topo.rend(), candidate, exits,
257 open_jumps);
258 } else {
259 NFAVertex curr = *t_it;
260 DEBUG_PRINTF("adding %zu to current\n", g[curr].index);
261 candidate.insert(curr);
262 open_jumps.erase(curr);
263 refineExits(g, candidate, *t_it, exits);
264 DEBUG_PRINTF(" open jumps %zu exits %zu\n", open_jumps.size(),
265 exits.size());
266 ++t_it;
267 }
268 }
269 /* assert exits valid */
270 setRegion(candidate, curr_id, regions);
271}
272
273static
274void mergeUnderBackEdges(const NGHolder &g, const vector<NFAVertex> &topo,
275 const BackEdgeSet &backEdges,
276 unordered_map<NFAVertex, u32> &regions) {
277 for (const auto &e : backEdges) {
278 NFAVertex u = source(e, g);
279 NFAVertex v = target(e, g);
280
281 u32 ru = regions[u];
282 u32 rv = regions[v];
283 if (ru == rv) {
284 continue;
285 }
286
287 DEBUG_PRINTF("merging v = %zu(%u), u = %zu(%u)\n", g[v].index, rv,
288 g[u].index, ru);
289 assert(rv < ru);
290
291 for (auto t : topo) {
292 u32 r = regions[t];
293 if (r <= ru && r > rv) {
294 regions[t] = rv;
295 } else if (r > ru) {
296 regions[t] = rv + r - ru;
297 }
298 }
299 }
300}
301
302static
303void reorderSpecials(const NGHolder &w, const AcyclicGraph &acyclic_g,
304 vector<NFAVertex> &topoOrder) {
305 // Start is last element of reverse topo ordering.
306 auto it = find(topoOrder.begin(), topoOrder.end(), w.start);
307 if (it != topoOrder.end() - 1) {
308 DEBUG_PRINTF("repositioning start\n");
309 assert(it != topoOrder.end());
310 topoOrder.erase(it);
311 topoOrder.insert(topoOrder.end(), w.start);
312 }
313
314 // StartDs is second-to-last element of reverse topo ordering.
315 it = find(topoOrder.begin(), topoOrder.end(), w.startDs);
316 if (it != topoOrder.end() - 2) {
317 DEBUG_PRINTF("repositioning start ds\n");
318 assert(it != topoOrder.end());
319 topoOrder.erase(it);
320 topoOrder.insert(topoOrder.end() - 1, w.startDs);
321 }
322
323 // AcceptEOD is first element of reverse topo ordering.
324 it = find(topoOrder.begin(), topoOrder.end(), w.acceptEod);
325 if (it != topoOrder.begin()) {
326 DEBUG_PRINTF("repositioning accept\n");
327 assert(it != topoOrder.end());
328 topoOrder.erase(it);
329 topoOrder.insert(topoOrder.begin(), w.acceptEod);
330 }
331
332 // Accept is second element of reverse topo ordering, if it's connected.
333 it = find(topoOrder.begin(), topoOrder.end(), w.accept);
334 if (it != topoOrder.begin() + 1) {
335 DEBUG_PRINTF("repositioning accept\n");
336 assert(it != topoOrder.end());
337 topoOrder.erase(it);
338 if (in_degree(w.accept, acyclic_g) != 0) {
339 topoOrder.insert(topoOrder.begin() + 1, w.accept);
340 }
341 }
342}
343
344static
345void liftSinks(const AcyclicGraph &acyclic_g, vector<NFAVertex> &topoOrder) {
346 unordered_set<NFAVertex> sinks;
347 for (auto v : vertices_range(acyclic_g)) {
348 if (is_special(v, acyclic_g)) {
349 continue;
350 }
351
352 if (isLeafNode(v, acyclic_g)) {
353 DEBUG_PRINTF("sink found %zu\n", acyclic_g[v].index);
354 sinks.insert(NFAVertex(v));
355 }
356 }
357
358 if (sinks.empty()) {
359 DEBUG_PRINTF("no sinks found\n");
360 return;
361 }
362
363 bool changed;
364 do {
365 DEBUG_PRINTF("look\n");
366 changed = false;
367 for (auto v : vertices_range(acyclic_g)) {
368 if (is_special(v, acyclic_g) || contains(sinks, NFAVertex(v))) {
369 continue;
370 }
371
372 for (auto w : adjacent_vertices_range(v, acyclic_g)) {
373 if (!contains(sinks, NFAVertex(w))) {
374 goto next;
375 }
376 }
377
378 DEBUG_PRINTF("sink found %zu\n", acyclic_g[v].index);
379 sinks.insert(NFAVertex(v));
380 changed = true;
381 next:;
382 }
383 } while (changed);
384
385 for (auto ri = topoOrder.rbegin() + 1; ri != topoOrder.rend(); ++ri) {
386 if (!contains(sinks, *ri)) {
387 continue;
388 }
389 NFAVertex s = *ri;
390 DEBUG_PRINTF("handling sink %zu\n", acyclic_g[s].index);
391 unordered_set<NFAVertex> parents;
392 for (const auto &e : in_edges_range(s, acyclic_g)) {
393 parents.insert(NFAVertex(source(e, acyclic_g)));
394 }
395
396 /* vertex has no children not reachable on a back edge, bubble the
397 * vertex up the topo order to be near its parents */
398 vector<NFAVertex>::reverse_iterator rj = ri;
399 --rj;
400 while (rj != topoOrder.rbegin() && !contains(parents, *rj)) {
401 /* sink is in rj + 1 */
402 assert(*(rj + 1) == s);
403 DEBUG_PRINTF("lifting\n");
404 using std::swap;
405 swap(*rj, *(rj + 1));
406 --rj;
407 }
408 }
409}
410
411using ColorMap = decltype(make_small_color_map(NGHolder()));
412
413/** Build a reverse topo ordering (with only the specials that are in use). We
414 * also want to ensure vertices which only lead to back edges are placed near
415 * their parents. */
416static
417vector<NFAVertex> buildTopoOrder(const NGHolder &w,
418 const AcyclicGraph &acyclic_g,
419 ColorMap &colours) {
420 vector<NFAVertex> topoOrder;
421 topoOrder.reserve(num_vertices(w));
422
423 topological_sort(acyclic_g, back_inserter(topoOrder),
424 color_map(colours));
425
426 reorderSpecials(w, acyclic_g, topoOrder);
427
428 if (topoOrder.empty()) {
429 return topoOrder;
430 }
431
432 liftSinks(acyclic_g, topoOrder);
433
434 DEBUG_PRINTF("TOPO ORDER\n");
435 for (auto ri = topoOrder.rbegin(); ri != topoOrder.rend(); ++ri) {
436 DEBUG_PRINTF("[%zu]\n", acyclic_g[*ri].index);
437 }
438 DEBUG_PRINTF("----------\n");
439
440 return topoOrder;
441}
442
443unordered_map<NFAVertex, u32> assignRegions(const NGHolder &g) {
444 assert(hasCorrectlyNumberedVertices(g));
445 const u32 numVertices = num_vertices(g);
446 DEBUG_PRINTF("assigning regions for %u vertices in holder\n", numVertices);
447
448 auto colours = make_small_color_map(g);
449
450 // Build an acyclic graph for this NGHolder.
451 BackEdgeSet deadEdges;
452 depth_first_search(g,
453 visitor(BackEdges<BackEdgeSet>(deadEdges))
454 .root_vertex(g.start)
455 .color_map(colours));
456
457 auto af = make_bad_edge_filter(&deadEdges);
458 AcyclicGraph acyclic_g(g, af);
459
460 // Build a (reverse) topological ordering.
461 vector<NFAVertex> topoOrder = buildTopoOrder(g, acyclic_g, colours);
462
463 // Everybody starts in region 0.
464 unordered_map<NFAVertex, u32> regions;
465 regions.reserve(numVertices);
466 for (auto v : vertices_range(g)) {
467 regions.emplace(v, 0);
468 }
469
470 findDagLeaders(g, acyclic_g, topoOrder, regions);
471 mergeUnderBackEdges(g, topoOrder, deadEdges, regions);
472
473 return regions;
474}
475
476} // namespace ue2
477