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
46namespace ue2 {
47
48/** \brief Properties associated with each vertex in an NFAGraph. */
49struct 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. */
64struct 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. */
77enum 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 */
108class NGHolder : public ue2_graph<NGHolder, NFAGraphVertexProps,
109 NFAGraphEdgeProps> {
110public:
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;
118public:
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
127typedef NGHolder::vertex_descriptor NFAVertex;
128typedef NGHolder::edge_descriptor NFAEdge;
129
130/** \brief True if the vertex \p v is one of our special vertices. */
131template <typename GraphT>
132bool 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 */
142void 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 */
153template <class Iter>
154void 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 */
180template <class Container>
181void 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 */
194template <class Iter>
195void 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 */
217template <class Container>
218void remove_edges(const Container &c, NGHolder &h, bool renumber = true) {
219 remove_edges(c.begin(), c.end(), h, renumber);
220}
221
222inline
223bool is_triggered(const NGHolder &g) {
224 return is_triggered(g.kind);
225}
226
227inline
228bool generates_callbacks(const NGHolder &g) {
229 return generates_callbacks(g.kind);
230}
231
232inline
233bool has_managed_reports(const NGHolder &g) {
234 return has_managed_reports(g.kind);
235}
236
237inline
238bool inspects_states_for_accepts(const NGHolder &g) {
239 return inspects_states_for_accepts(g.kind);
240}
241
242} // namespace ue2
243
244#endif
245