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 Definition of the NGHolder type used for to represent general nfa |
31 | * graphs as well as all associated types (vertex and edge properties, etc). |
32 | * |
33 | * The NGHolder also contains the special vertices used to represents starts and |
34 | * accepts. |
35 | */ |
36 | |
37 | #ifndef NG_HOLDER_H |
38 | #define NG_HOLDER_H |
39 | |
40 | #include "ue2common.h" |
41 | #include "nfa/nfa_kind.h" |
42 | #include "util/charreach.h" |
43 | #include "util/flat_containers.h" |
44 | #include "util/ue2_graph.h" |
45 | |
46 | namespace ue2 { |
47 | |
48 | /** \brief Properties associated with each vertex in an NFAGraph. */ |
49 | struct NFAGraphVertexProps { |
50 | /** \brief Set of characters on which this vertex is reachable. */ |
51 | CharReach char_reach; |
52 | |
53 | /** \brief Set of reports raised by this vertex. */ |
54 | flat_set<ReportID> reports; |
55 | |
56 | /** \brief Unique index for this vertex, used for BGL algorithms. */ |
57 | size_t index = 0; |
58 | |
59 | /** \brief Flags associated with assertions. */ |
60 | u32 assert_flags = 0; |
61 | }; |
62 | |
63 | /** \brief Properties associated with each edge in an NFAGraph. */ |
64 | struct NFAGraphEdgeProps { |
65 | /** \brief Unique index for this edge, used for BGL algorithms. */ |
66 | size_t index = 0; |
67 | |
68 | /** \brief For graphs that will be implemented as multi-top engines, this |
69 | * specifies the top events. Only used on edges from the start vertex. */ |
70 | flat_set<u32> tops; |
71 | |
72 | /** \brief Flags associated with assertions. */ |
73 | u32 assert_flags = 0; |
74 | }; |
75 | |
76 | /** \brief vertex_index values for special nodes in the NFAGraph. */ |
77 | enum SpecialNodes { |
78 | /** \brief Anchored start vertex. WARNING: this may be triggered at various |
79 | * locations (not just zero) for triggered graphs. */ |
80 | NODE_START, |
81 | |
82 | /** \brief Unanchored start-dotstar vertex. WARNING: this may not have a |
83 | * proper self-loop. */ |
84 | NODE_START_DOTSTAR, |
85 | |
86 | /** \brief Accept vertex. All vertices that can match at arbitrary offsets |
87 | * must have an edge to this vertex. */ |
88 | NODE_ACCEPT, |
89 | |
90 | /** \brief Accept-EOD vertex. Vertices that must raise a match at EOD only |
91 | * must have an edge to this vertex. */ |
92 | NODE_ACCEPT_EOD, |
93 | |
94 | /** \brief Sentinel, number of special vertices. */ |
95 | N_SPECIALS |
96 | }; |
97 | |
98 | /** \brief Encapsulates an NFAGraph, stores special vertices and other |
99 | * metadata. |
100 | * |
101 | * When constructed, the graph will have the following stylised "special" |
102 | * edges: |
103 | * |
104 | * - (start, startDs) |
105 | * - (startDs, startDs) (self-loop) |
106 | * - (accept, acceptEod) |
107 | */ |
108 | class NGHolder : public ue2_graph<NGHolder, NFAGraphVertexProps, |
109 | NFAGraphEdgeProps> { |
110 | public: |
111 | explicit NGHolder(nfa_kind kind); |
112 | NGHolder(void) : NGHolder(NFA_OUTFIX) {}; |
113 | virtual ~NGHolder(void); |
114 | |
115 | nfa_kind kind; /* Role that this plays in Rose */ |
116 | |
117 | static const size_t N_SPECIAL_VERTICES = N_SPECIALS; |
118 | public: |
119 | const vertex_descriptor start; //!< Anchored start vertex. |
120 | const vertex_descriptor startDs; //!< Unanchored start-dotstar vertex. |
121 | const vertex_descriptor accept; //!< Accept vertex. |
122 | const vertex_descriptor acceptEod; //!< Accept at EOD vertex. |
123 | |
124 | vertex_descriptor getSpecialVertex(u32 id) const; |
125 | }; |
126 | |
127 | typedef NGHolder::vertex_descriptor NFAVertex; |
128 | typedef NGHolder::edge_descriptor NFAEdge; |
129 | |
130 | /** \brief True if the vertex \p v is one of our special vertices. */ |
131 | template <typename GraphT> |
132 | bool is_special(const typename GraphT::vertex_descriptor v, const GraphT &g) { |
133 | return g[v].index < N_SPECIALS; |
134 | } |
135 | |
136 | /** |
137 | * \brief Clears all non-special vertices and edges from the graph. |
138 | * |
139 | * Note: not the same as the BGL's clear() function, which removes all vertices |
140 | * and edges. |
141 | */ |
142 | void clear_graph(NGHolder &h); |
143 | |
144 | /* |
145 | * \brief Clear and remove all of the vertices pointed to by the given iterator |
146 | * range. |
147 | * |
148 | * If renumber is false, no renumbering of vertex indices is done. |
149 | * |
150 | * Note: should not be called with iterators that will be invalidated by vertex |
151 | * removal (such as NFAGraph::vertex_iterator). |
152 | */ |
153 | template <class Iter> |
154 | void remove_vertices(Iter begin, Iter end, NGHolder &h, bool renumber = true) { |
155 | if (begin == end) { |
156 | return; |
157 | } |
158 | |
159 | for (Iter it = begin; it != end; ++it) { |
160 | NFAVertex v = *it; |
161 | if (!is_special(v, h)) { |
162 | clear_vertex(v, h); |
163 | remove_vertex(v, h); |
164 | } else { |
165 | assert(0); |
166 | } |
167 | } |
168 | |
169 | if (renumber) { |
170 | renumber_edges(h); |
171 | renumber_vertices(h); |
172 | } |
173 | } |
174 | |
175 | /** \brief Clear and remove all of the vertices pointed to by the vertex |
176 | * descriptors in the given container. |
177 | * |
178 | * This is a convenience wrapper around the iterator variant above. |
179 | */ |
180 | template <class Container> |
181 | void remove_vertices(const Container &c, NGHolder &h, bool renumber = true) { |
182 | remove_vertices(c.begin(), c.end(), h, renumber); |
183 | } |
184 | |
185 | /* |
186 | * \brief Clear and remove all of the edges pointed to by the given iterator |
187 | * range. |
188 | * |
189 | * If renumber is false, no renumbering of vertex indices is done. |
190 | * |
191 | * Note: should not be called with iterators that will be invalidated by vertex |
192 | * removal (such as NFAGraph::edge_iterator). |
193 | */ |
194 | template <class Iter> |
195 | void remove_edges(Iter begin, Iter end, NGHolder &h, bool renumber = true) { |
196 | if (begin == end) { |
197 | return; |
198 | } |
199 | |
200 | for (Iter it = begin; it != end; ++it) { |
201 | const NFAEdge &e = *it; |
202 | remove_edge(e, h); |
203 | } |
204 | |
205 | if (renumber) { |
206 | renumber_edges(h); |
207 | } |
208 | } |
209 | |
210 | #define DEFAULT_TOP 0U |
211 | |
212 | /** \brief Clear and remove all of the edges pointed to by the edge descriptors |
213 | * in the given container. |
214 | * |
215 | * This is a convenience wrapper around the iterator variant above. |
216 | */ |
217 | template <class Container> |
218 | void remove_edges(const Container &c, NGHolder &h, bool renumber = true) { |
219 | remove_edges(c.begin(), c.end(), h, renumber); |
220 | } |
221 | |
222 | inline |
223 | bool is_triggered(const NGHolder &g) { |
224 | return is_triggered(g.kind); |
225 | } |
226 | |
227 | inline |
228 | bool generates_callbacks(const NGHolder &g) { |
229 | return generates_callbacks(g.kind); |
230 | } |
231 | |
232 | inline |
233 | bool has_managed_reports(const NGHolder &g) { |
234 | return has_managed_reports(g.kind); |
235 | } |
236 | |
237 | inline |
238 | bool inspects_states_for_accepts(const NGHolder &g) { |
239 | return inspects_states_for_accepts(g.kind); |
240 | } |
241 | |
242 | } // namespace ue2 |
243 | |
244 | #endif |
245 | |