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
43namespace ue2 {
44
45/** \brief Assign a region ID to every vertex in the graph. */
46std::unordered_map<NFAVertex, u32> assignRegions(const NGHolder &g);
47
48/** \brief True if vertices \p a and \p b are in the same region. */
49template <class Graph>
50bool inSameRegion(const Graph &g, NFAVertex a, NFAVertex b,
51 const std::unordered_map<NFAVertex, u32> &region_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. */
59template <class Graph>
60bool inLaterRegion(const Graph &g, NFAVertex a, NFAVertex b,
61 const std::unordered_map<NFAVertex, u32> &region_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. */
86template <class Graph>
87bool inEarlierRegion(const Graph &g, NFAVertex a, NFAVertex b,
88 const std::unordered_map<NFAVertex, u32> &region_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. */
113template <class Graph>
114bool isRegionEntry(const Graph &g, NFAVertex v,
115 const std::unordered_map<NFAVertex, u32> &region_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. */
128template <class Graph>
129bool isRegionExit(const Graph &g, NFAVertex v,
130 const std::unordered_map<NFAVertex, u32> &region_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. */
141template <class Graph>
142bool isSingletonRegion(const Graph &g, NFAVertex v,
143 const std::unordered_map<NFAVertex, u32> &region_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 */
179template <class Graph>
180bool isOptionalRegion(const Graph &g, NFAVertex v,
181 const std::unordered_map<NFAVertex, u32> &region_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