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 and utility functions. |
31 | */ |
32 | |
33 | #ifndef NG_REGION_H |
34 | #define NG_REGION_H |
35 | |
36 | #include "ng_holder.h" |
37 | #include "util/container.h" |
38 | #include "util/graph_range.h" |
39 | |
40 | #include <unordered_map> |
41 | #include <vector> |
42 | |
43 | namespace ue2 { |
44 | |
45 | /** \brief Assign a region ID to every vertex in the graph. */ |
46 | std::unordered_map<NFAVertex, u32> assignRegions(const NGHolder &g); |
47 | |
48 | /** \brief True if vertices \p a and \p b are in the same region. */ |
49 | template <class Graph> |
50 | bool inSameRegion(const Graph &g, NFAVertex a, NFAVertex b, |
51 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
52 | assert(contains(region_map, a) && contains(region_map, b)); |
53 | |
54 | return region_map.at(a) == region_map.at(b) && |
55 | is_special(a, g) == is_special(b, g); |
56 | } |
57 | |
58 | /** \brief True if vertex \p b is in a later region than vertex \p a. */ |
59 | template <class Graph> |
60 | bool inLaterRegion(const Graph &g, NFAVertex a, NFAVertex b, |
61 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
62 | assert(contains(region_map, a) && contains(region_map, b)); |
63 | |
64 | u32 aa = g[a].index; |
65 | u32 bb = g[b].index; |
66 | |
67 | if (bb == NODE_START || bb == NODE_START_DOTSTAR) { |
68 | return false; |
69 | } |
70 | |
71 | if (aa == NODE_START || aa == NODE_START_DOTSTAR) { |
72 | return true; |
73 | } |
74 | |
75 | if (bb == NODE_ACCEPT || bb == NODE_ACCEPT_EOD) { |
76 | return true; |
77 | } |
78 | if (aa == NODE_ACCEPT || aa == NODE_ACCEPT_EOD) { |
79 | return false; |
80 | } |
81 | |
82 | return region_map.at(a) < region_map.at(b); |
83 | } |
84 | |
85 | /** \brief True if vertex \p b is in an earlier region than vertex \p a. */ |
86 | template <class Graph> |
87 | bool inEarlierRegion(const Graph &g, NFAVertex a, NFAVertex b, |
88 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
89 | assert(contains(region_map, a) && contains(region_map, b)); |
90 | |
91 | u32 aa = g[a].index; |
92 | u32 bb = g[b].index; |
93 | |
94 | if (bb == NODE_START || bb == NODE_START_DOTSTAR) { |
95 | return true; |
96 | } |
97 | |
98 | if (aa == NODE_START || aa == NODE_START_DOTSTAR) { |
99 | return false; |
100 | } |
101 | |
102 | if (bb == NODE_ACCEPT || bb == NODE_ACCEPT_EOD) { |
103 | return false; |
104 | } |
105 | if (aa == NODE_ACCEPT || aa == NODE_ACCEPT_EOD) { |
106 | return true; |
107 | } |
108 | |
109 | return region_map.at(b) < region_map.at(a); |
110 | } |
111 | |
112 | /** \brief True if vertex \p v is an entry vertex for its region. */ |
113 | template <class Graph> |
114 | bool isRegionEntry(const Graph &g, NFAVertex v, |
115 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
116 | // Note that some graph types do not have inv_adjacent_vertices, so we must |
117 | // use in_edges here. |
118 | for (const auto &e : in_edges_range(v, g)) { |
119 | if (!inSameRegion(g, v, source(e, g), region_map)) { |
120 | return true; |
121 | } |
122 | } |
123 | |
124 | return false; |
125 | } |
126 | |
127 | /** \brief True if vertex \p v is an exit vertex for its region. */ |
128 | template <class Graph> |
129 | bool isRegionExit(const Graph &g, NFAVertex v, |
130 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
131 | for (auto w : adjacent_vertices_range(v, g)) { |
132 | if (!inSameRegion(g, v, w, region_map)) { |
133 | return true; |
134 | } |
135 | } |
136 | |
137 | return false; |
138 | } |
139 | |
140 | /** \brief True if vertex \p v is in a region all on its own. */ |
141 | template <class Graph> |
142 | bool isSingletonRegion(const Graph &g, NFAVertex v, |
143 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
144 | for (const auto &e : in_edges_range(v, g)) { |
145 | auto u = source(e, g); |
146 | if (u != v && inSameRegion(g, v, u, region_map)) { |
147 | return false; |
148 | } |
149 | |
150 | for (auto w : ue2::adjacent_vertices_range(u, g)) { |
151 | if (w != v && inSameRegion(g, v, w, region_map)) { |
152 | return false; |
153 | } |
154 | } |
155 | } |
156 | |
157 | for (auto w : adjacent_vertices_range(v, g)) { |
158 | if (w != v && inSameRegion(g, v, w, region_map)) { |
159 | return false; |
160 | } |
161 | |
162 | for (const auto &e : in_edges_range(w, g)) { |
163 | auto u = source(e, g); |
164 | if (u != v && inSameRegion(g, v, u, region_map)) { |
165 | return false; |
166 | } |
167 | } |
168 | |
169 | return true; |
170 | } |
171 | |
172 | return true; |
173 | } |
174 | |
175 | /** |
176 | * \brief True if the region containing vertex \p v is optional. The vertex \p v |
177 | * should be a region leader. |
178 | */ |
179 | template <class Graph> |
180 | bool isOptionalRegion(const Graph &g, NFAVertex v, |
181 | const std::unordered_map<NFAVertex, u32> ®ion_map) { |
182 | assert(isRegionEntry(g, v, region_map)); |
183 | |
184 | DEBUG_PRINTF("check if r%u is optional (inspecting v%zu)\n" , |
185 | region_map.at(v), g[v].index); |
186 | |
187 | // Region zero is never optional. |
188 | assert(contains(region_map, v)); |
189 | if (region_map.at(v) == 0) { |
190 | return false; |
191 | } |
192 | |
193 | // Optional if v has a predecessor in an earlier region that has a |
194 | // successor in a later one. |
195 | |
196 | for (const auto &e : in_edges_range(v, g)) { |
197 | auto u = source(e, g); |
198 | if (inSameRegion(g, v, u, region_map)) { |
199 | continue; |
200 | } |
201 | DEBUG_PRINTF(" searching from u=%zu\n" , g[u].index); |
202 | |
203 | assert(inEarlierRegion(g, v, u, region_map)); |
204 | |
205 | for (auto w : adjacent_vertices_range(u, g)) { |
206 | DEBUG_PRINTF(" searching to w=%zu\n" , g[w].index); |
207 | if (inLaterRegion(g, v, w, region_map)) { |
208 | return true; |
209 | } |
210 | } |
211 | return false; |
212 | } |
213 | |
214 | return false; |
215 | } |
216 | |
217 | } // namespace ue2 |
218 | |
219 | #endif |
220 | |