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
51namespace ue2 {
52
53struct CastleProto;
54struct raw_dfa;
55struct raw_som_dfa;
56struct TamaProto;
57
58/** \brief Table type for a literal. */
59enum 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. */
68enum 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. */
79struct 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. */
121struct 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. */
140struct 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 */
185struct 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
217bool operator<(const RoseEdgeProps &a, const RoseEdgeProps &b);
218
219/**
220 * \brief Core Rose graph structure.
221 */
222struct RoseGraph : public ue2_graph<RoseGraph, RoseVertexProps, RoseEdgeProps> {
223 friend class RoseBuildImpl; /* to allow index renumbering */
224};
225using RoseVertex = RoseGraph::vertex_descriptor;
226using RoseEdge = RoseGraph::edge_descriptor;
227
228} // namespace ue2
229
230#endif // ROSE_GRAPH_H
231