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);
NGHolder(void)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>
is_special(const typename GraphT::vertex_descriptor v,const GraphT & g)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
is_triggered(const NGHolder & g)223 bool is_triggered(const NGHolder &g) {
224 return is_triggered(g.kind);
225 }
226
227 inline
generates_callbacks(const NGHolder & g)228 bool generates_callbacks(const NGHolder &g) {
229 return generates_callbacks(g.kind);
230 }
231
232 inline
has_managed_reports(const NGHolder & g)233 bool has_managed_reports(const NGHolder &g) {
234 return has_managed_reports(g.kind);
235 }
236
237 inline
inspects_states_for_accepts(const NGHolder & g)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