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 Calculate dominator and post-dominator trees. |
31 | * |
32 | * A small wrapper around the BGL's lengauer_tarjan_dominator_tree algorithm. |
33 | */ |
34 | #include "ng_dominators.h" |
35 | |
36 | #include "ue2common.h" |
37 | #include "ng_holder.h" |
38 | #include "ng_util.h" |
39 | |
40 | #include <boost-patched/graph/dominator_tree.hpp> // locally patched version |
41 | #include <boost-patched/graph/reverse_graph.hpp> |
42 | |
43 | using namespace std; |
44 | using boost::make_assoc_property_map; |
45 | using boost::make_iterator_property_map; |
46 | |
47 | namespace ue2 { |
48 | |
49 | template <class Graph> |
50 | unordered_map<NFAVertex, NFAVertex> calcDominators(const Graph &g, |
51 | typename Graph::vertex_descriptor source) { |
52 | using Vertex = typename Graph::vertex_descriptor; |
53 | const size_t num_verts = num_vertices(g); |
54 | auto index_map = get(&NFAGraphVertexProps::index, g); |
55 | |
56 | vector<size_t> dfnum(num_verts, 0); |
57 | vector<Vertex> parents(num_verts, Graph::null_vertex()); |
58 | |
59 | auto dfnum_map = make_iterator_property_map(dfnum.begin(), index_map); |
60 | auto parent_map = make_iterator_property_map(parents.begin(), index_map); |
61 | vector<Vertex> vertices_by_dfnum(num_verts, Graph::null_vertex()); |
62 | |
63 | // Output map. |
64 | vector<Vertex> doms(num_verts, Graph::null_vertex()); |
65 | auto dom_map = make_iterator_property_map(doms.begin(), index_map); |
66 | |
67 | boost_ue2::lengauer_tarjan_dominator_tree(g, source, index_map, dfnum_map, |
68 | parent_map, vertices_by_dfnum, |
69 | dom_map); |
70 | |
71 | /* Translate back to an NFAVertex map */ |
72 | unordered_map<NFAVertex, NFAVertex> doms2; |
73 | doms2.reserve(num_verts); |
74 | for (auto v : vertices_range(g)) { |
75 | auto dom_of_v = doms[g[v].index]; |
76 | if (dom_of_v) { |
77 | doms2.emplace(v, dom_of_v); |
78 | } |
79 | } |
80 | return doms2; |
81 | } |
82 | |
83 | unordered_map<NFAVertex, NFAVertex> findDominators(const NGHolder &g) { |
84 | assert(hasCorrectlyNumberedVertices(g)); |
85 | return calcDominators(g, g.start); |
86 | } |
87 | |
88 | unordered_map<NFAVertex, NFAVertex> findPostDominators(const NGHolder &g) { |
89 | assert(hasCorrectlyNumberedVertices(g)); |
90 | return calcDominators(boost::reverse_graph<NGHolder, const NGHolder &>(g), |
91 | g.acceptEod); |
92 | } |
93 | |
94 | } // namespace ue2 |
95 | |