1 | /* |
2 | * Copyright (c) 2015-2018, 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 BGL graph structures used internally by the Rose build process. |
31 | * |
32 | * BGL graph structures used internally by the build-time portion of Rose. The |
33 | * graph used for input is in rose_in_graph.h since it's part of the RoseBuild |
34 | * external API. |
35 | */ |
36 | |
37 | #ifndef ROSE_GRAPH_H |
38 | #define ROSE_GRAPH_H |
39 | |
40 | #include "ue2common.h" |
41 | #include "rose_build.h" |
42 | #include "rose_internal.h" |
43 | #include "nfa/nfa_internal.h" // for MO_INVALID_IDX |
44 | #include "util/depth.h" |
45 | #include "util/flat_containers.h" |
46 | #include "util/ue2_graph.h" |
47 | |
48 | #include <memory> |
49 | #include <set> |
50 | |
51 | namespace ue2 { |
52 | |
53 | struct CastleProto; |
54 | struct raw_dfa; |
55 | struct raw_som_dfa; |
56 | struct TamaProto; |
57 | |
58 | /** \brief Table type for a literal. */ |
59 | enum rose_literal_table { |
60 | ROSE_ANCHORED, //!< literals anchored to start |
61 | ROSE_FLOATING, //!< general floating literals |
62 | ROSE_EOD_ANCHORED, //!< literals that match near EOD |
63 | ROSE_ANCHORED_SMALL_BLOCK, //!< anchored literals for small block table |
64 | ROSE_EVENT //!< "literal-like" events, such as EOD |
65 | }; |
66 | |
67 | /** \brief Edge history types. */ |
68 | enum RoseRoleHistory { |
69 | ROSE_ROLE_HISTORY_NONE, //!< no special history |
70 | ROSE_ROLE_HISTORY_ANCH, //!< previous role is at a fixed offset |
71 | ROSE_ROLE_HISTORY_LAST_BYTE, //!< previous role can only match at EOD |
72 | ROSE_ROLE_HISTORY_INVALID //!< history not yet assigned |
73 | }; |
74 | |
75 | #include "util/order_check.h" |
76 | |
77 | /** \brief Provides information about the (pre|in)fix engine to the left of a |
78 | * role. */ |
79 | struct LeftEngInfo { |
80 | std::shared_ptr<NGHolder> graph; |
81 | std::shared_ptr<CastleProto> castle; |
82 | std::shared_ptr<raw_dfa> dfa; |
83 | std::shared_ptr<raw_som_dfa> haig; |
84 | std::shared_ptr<TamaProto> tamarama; |
85 | u32 lag = 0U; |
86 | ReportID leftfix_report = MO_INVALID_IDX; |
87 | depth dfa_min_width{0}; |
88 | depth dfa_max_width = depth::infinity(); |
89 | |
90 | bool operator==(const LeftEngInfo &other) const { |
91 | return other.graph == graph |
92 | && other.castle == castle |
93 | && other.dfa == dfa |
94 | && other.haig == haig |
95 | && other.tamarama == tamarama |
96 | && other.lag == lag |
97 | && other.leftfix_report == leftfix_report; |
98 | } |
99 | bool operator!=(const LeftEngInfo &other) const { |
100 | return !(*this == other); |
101 | } |
102 | bool operator<(const LeftEngInfo &b) const { |
103 | const LeftEngInfo &a = *this; |
104 | ORDER_CHECK(graph); |
105 | ORDER_CHECK(castle); |
106 | ORDER_CHECK(dfa); |
107 | ORDER_CHECK(haig); |
108 | ORDER_CHECK(tamarama); |
109 | ORDER_CHECK(lag); |
110 | ORDER_CHECK(leftfix_report); |
111 | return false; |
112 | } |
113 | size_t hash() const; |
114 | void reset(void); |
115 | operator bool() const; |
116 | bool tracksSom() const { return !!haig; } |
117 | }; |
118 | |
119 | /** \brief Provides information about the suffix engine to the right of a |
120 | * role. */ |
121 | struct RoseSuffixInfo { |
122 | u32 top = 0; |
123 | std::shared_ptr<NGHolder> graph; /* if triggers a trailing nfa */ |
124 | std::shared_ptr<CastleProto> castle; |
125 | std::shared_ptr<raw_som_dfa> haig; |
126 | std::shared_ptr<raw_dfa> rdfa; |
127 | std::shared_ptr<TamaProto> tamarama; |
128 | depth dfa_min_width{0}; |
129 | depth dfa_max_width = depth::infinity(); |
130 | |
131 | bool operator==(const RoseSuffixInfo &b) const; |
132 | bool operator!=(const RoseSuffixInfo &b) const { return !(*this == b); } |
133 | bool operator<(const RoseSuffixInfo &b) const; |
134 | size_t hash() const; |
135 | void reset(void); |
136 | operator bool() const { return graph || castle || haig || rdfa || tamarama; } |
137 | }; |
138 | |
139 | /** \brief Properties attached to each Rose graph vertex. */ |
140 | struct RoseVertexProps { |
141 | /** \brief Unique dense vertex index. Used for BGL algorithms. */ |
142 | size_t index = ~size_t{0}; |
143 | |
144 | /** \brief IDs of literals in the Rose literal map. */ |
145 | flat_set<u32> literals; |
146 | |
147 | /** |
148 | * \brief If true, this vertex is a virtual vertex for firing reports at |
149 | * EOD. These vertices must have reports and have no associated literals. |
150 | */ |
151 | bool eod_accept = false; |
152 | |
153 | /** \brief Report IDs to fire. */ |
154 | flat_set<ReportID> reports; |
155 | |
156 | /** \brief Bitmask of groups that this role sets. */ |
157 | rose_group groups = 0; |
158 | |
159 | /** \brief Minimum role (end of literal) offset depth in bytes. */ |
160 | u32 min_offset = ~u32{0}; |
161 | |
162 | /** \brief Maximum role (end of literal) offset depth in bytes */ |
163 | u32 max_offset = 0; |
164 | |
165 | /** \brief SOM for the role is offset from end match offset */ |
166 | u32 som_adjust = 0; |
167 | |
168 | /** \brief Prefix/infix engine to the left of this role. */ |
169 | LeftEngInfo left; |
170 | |
171 | /** |
172 | * \brief Suffix engine to the right of this role. |
173 | * |
174 | * Note: information about triggered infixes is associated with the left of |
175 | * the destination role. |
176 | */ |
177 | RoseSuffixInfo suffix; |
178 | |
179 | bool isBoring(void) const; |
180 | bool fixedOffset(void) const; |
181 | }; |
182 | |
183 | /** \brief Properties attached to each Rose graph edge. */ |
184 | /* bounds are distance from end of prev to start of the next */ |
185 | struct RoseEdgeProps { |
186 | /** \brief Unique dense vertex index. Used for BGL algorithms. */ |
187 | size_t index = ~size_t{0}; |
188 | |
189 | /** |
190 | * \brief Minimum distance from the end of the source role's match to the |
191 | * start of the target role's match. |
192 | * |
193 | * Not used when the target has a left engine (as the engine represents |
194 | * bounds). |
195 | */ |
196 | u32 minBound = 0; |
197 | |
198 | /** |
199 | * \brief Maximum distance from the end of the source role's match to the |
200 | * start of the target role's match. |
201 | * |
202 | * Not used when the target has a left engine (as the engine represents |
203 | * bounds). |
204 | */ |
205 | u32 maxBound = 0; |
206 | |
207 | /** \brief Which top to trigger on the target role's left engine. */ |
208 | u32 rose_top = 0; |
209 | |
210 | /** \brief True if the rose_top can clear all other previous tops. */ |
211 | u8 rose_cancel_prev_top = false; |
212 | |
213 | /** \brief History required by this edge. */ |
214 | RoseRoleHistory history = ROSE_ROLE_HISTORY_INVALID; |
215 | }; |
216 | |
217 | bool operator<(const RoseEdgeProps &a, const RoseEdgeProps &b); |
218 | |
219 | /** |
220 | * \brief Core Rose graph structure. |
221 | */ |
222 | struct RoseGraph : public ue2_graph<RoseGraph, RoseVertexProps, RoseEdgeProps> { |
223 | friend class RoseBuildImpl; /* to allow index renumbering */ |
224 | }; |
225 | using RoseVertex = RoseGraph::vertex_descriptor; |
226 | using RoseEdge = RoseGraph::edge_descriptor; |
227 | |
228 | } // namespace ue2 |
229 | |
230 | #endif // ROSE_GRAPH_H |
231 | |