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 Rose Input Graph: Used for ng_violet -> rose_build_add communication. |
31 | * |
32 | * The input graph MUST be a DAG. |
33 | * There MUST be exactly 1 START or ANCHORED_START vertex. |
34 | * The edges MUST be of the form START->LITERAL, LITERAL->LITERAL, |
35 | * LITERAL->ACCEPT or LITERAL->ACCEPT_EOD. |
36 | * Every non START/ANCHORED_START vertex MUST have an in-edge. |
37 | * Every non ACCEPT/ACCEPT_EOD vertex MUST have an out-edge. |
38 | * |
39 | * Edges are either a graph or have bounds associated with them. |
40 | * Graphs on edges to accepts use their internal report ids. |
41 | */ |
42 | |
43 | #ifndef ROSE_IN_GRAPH_H |
44 | #define ROSE_IN_GRAPH_H |
45 | |
46 | #include "ue2common.h" |
47 | #include "rose/rose_common.h" |
48 | #include "util/flat_containers.h" |
49 | #include "util/ue2_graph.h" |
50 | #include "util/ue2string.h" |
51 | |
52 | #include <memory> |
53 | |
54 | namespace ue2 { |
55 | |
56 | class NGHolder; |
57 | struct raw_som_dfa; |
58 | struct raw_dfa; |
59 | |
60 | enum RoseInVertexType { |
61 | RIV_LITERAL, |
62 | RIV_START, |
63 | RIV_ANCHORED_START, |
64 | RIV_ACCEPT, |
65 | RIV_ACCEPT_EOD |
66 | }; |
67 | |
68 | struct RoseInVertexProps { |
69 | RoseInVertexProps() |
70 | : type(RIV_LITERAL), delay(0), min_offset(0), |
71 | max_offset(ROSE_BOUND_INF) {} |
72 | |
73 | private: |
74 | template <class ReportContainer> |
75 | RoseInVertexProps(RoseInVertexType type_in, const ue2_literal &s_in, |
76 | const ReportContainer &reports_in, u32 min_offset_in, |
77 | u32 max_offset_in) |
78 | : type(type_in), s(s_in), delay(0), |
79 | reports(begin(reports_in), end(reports_in)), |
80 | min_offset(min_offset_in), max_offset(max_offset_in) {} |
81 | |
82 | // Constructor for a vertex with no reports. |
83 | RoseInVertexProps(RoseInVertexType type_in, const ue2_literal &s_in, |
84 | u32 min_offset_in, u32 max_offset_in) |
85 | : type(type_in), s(s_in), delay(0), min_offset(min_offset_in), |
86 | max_offset(max_offset_in) {} |
87 | |
88 | public: |
89 | static RoseInVertexProps makeLiteral(const ue2_literal &lit) { |
90 | DEBUG_PRINTF("making literal %s\n" , dumpString(lit).c_str()); |
91 | return RoseInVertexProps(RIV_LITERAL, lit, 0, ROSE_BOUND_INF); |
92 | } |
93 | |
94 | template <class ReportContainer> |
95 | static RoseInVertexProps makeAccept(const ReportContainer &rep) { |
96 | DEBUG_PRINTF("making accept for %zu reports\n" , rep.size()); |
97 | return RoseInVertexProps(RIV_ACCEPT, ue2_literal(), rep, 0, |
98 | ROSE_BOUND_INF); |
99 | } |
100 | |
101 | template <class ReportContainer> |
102 | static RoseInVertexProps makeAcceptEod(const ReportContainer &rep) { |
103 | DEBUG_PRINTF("making accept-eod for %zu reports\n" , rep.size()); |
104 | return RoseInVertexProps(RIV_ACCEPT_EOD, ue2_literal(), rep, 0, |
105 | ROSE_BOUND_INF); |
106 | } |
107 | |
108 | /* for when there is a suffix graph which handles the reports */ |
109 | static RoseInVertexProps makeAcceptEod() { |
110 | return RoseInVertexProps(RIV_ACCEPT_EOD, ue2_literal(), 0, |
111 | ROSE_BOUND_INF); |
112 | } |
113 | |
114 | static RoseInVertexProps makeStart(bool anchored) { |
115 | DEBUG_PRINTF("making %s\n" , anchored ? "anchored start" : "start" ); |
116 | if (anchored) { |
117 | return RoseInVertexProps(RIV_ANCHORED_START, ue2_literal(), 0, 0); |
118 | } else { |
119 | return RoseInVertexProps(RIV_START, ue2_literal(), 0, |
120 | ROSE_BOUND_INF); |
121 | } |
122 | } |
123 | |
124 | RoseInVertexType type; /* polymorphic vertices are probably a bad idea */ |
125 | ue2_literal s; /**< for RIV_LITERAL */ |
126 | u32 delay; /**< for RIV_LITERAL, delay applied to literal. */ |
127 | flat_set<ReportID> reports; /**< for RIV_ACCEPT/RIV_ACCEPT_EOD */ |
128 | u32 min_offset; /**< Minimum offset at which this vertex can match. */ |
129 | u32 max_offset; /**< Maximum offset at which this vertex can match. */ |
130 | size_t index = 0; /**< \brief Unique vertex index. */ |
131 | }; |
132 | |
133 | struct RoseInEdgeProps { |
134 | RoseInEdgeProps() |
135 | : minBound(0), maxBound(0), graph(), haig(), graph_lag(0) {} |
136 | |
137 | RoseInEdgeProps(u32 min_in, u32 max_in) |
138 | : minBound(min_in), maxBound(max_in), graph(), graph_lag(0) { |
139 | assert(minBound <= maxBound); |
140 | assert(minBound != ROSE_BOUND_INF); |
141 | } |
142 | |
143 | /* haig rosefixes (prefix/infix) require their corresponding holders */ |
144 | RoseInEdgeProps(std::shared_ptr<NGHolder> g, std::shared_ptr<raw_som_dfa> h, |
145 | u32 lag) |
146 | : minBound(0), maxBound(ROSE_BOUND_INF), graph(g), haig(h), |
147 | graph_lag(lag) { |
148 | assert(graph); |
149 | assert(haig); |
150 | } |
151 | |
152 | /* haig suffixes do not require their corresponding holders */ |
153 | explicit RoseInEdgeProps(std::shared_ptr<raw_som_dfa> h) |
154 | : minBound(0), maxBound(ROSE_BOUND_INF), haig(h), graph_lag(0) { |
155 | assert(haig); |
156 | } |
157 | |
158 | RoseInEdgeProps(std::shared_ptr<NGHolder> g, u32 lag) |
159 | : minBound(0), maxBound(ROSE_BOUND_INF), graph(g), graph_lag(lag) { |
160 | assert(graph); |
161 | } |
162 | |
163 | /** \brief Minimum bound on 'dot' repeat between literals. ie pred end -> |
164 | * succ begin. */ |
165 | u32 minBound; |
166 | |
167 | /** \brief Maximum bound on 'dot' repeat between literals. */ |
168 | u32 maxBound; |
169 | |
170 | /** \brief Graph on edge. Graph is end to (end - lag). */ |
171 | std::shared_ptr<NGHolder> graph; |
172 | |
173 | /** \brief DFA version of graph, if we have already determinised. */ |
174 | std::shared_ptr<raw_dfa> dfa; |
175 | |
176 | /** \brief Haig version of graph, if required. */ |
177 | std::shared_ptr<raw_som_dfa> haig; |
178 | |
179 | /** |
180 | * \brief Distance behind the match offset for the literal in the target |
181 | * vertex that the leftfix needs to be checked at. |
182 | */ |
183 | u32 graph_lag; |
184 | |
185 | /** \brief Unique edge index. */ |
186 | size_t index = 0; |
187 | }; |
188 | |
189 | struct RoseInGraph |
190 | : public ue2_graph<RoseInGraph, RoseInVertexProps, RoseInEdgeProps> { |
191 | }; |
192 | typedef RoseInGraph::vertex_descriptor RoseInVertex; |
193 | typedef RoseInGraph::edge_descriptor RoseInEdge; |
194 | |
195 | } // namespace ue2 |
196 | |
197 | #endif |
198 | |