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
54namespace ue2 {
55
56class NGHolder;
57struct raw_som_dfa;
58struct raw_dfa;
59
60enum RoseInVertexType {
61 RIV_LITERAL,
62 RIV_START,
63 RIV_ANCHORED_START,
64 RIV_ACCEPT,
65 RIV_ACCEPT_EOD
66};
67
68struct RoseInVertexProps {
69 RoseInVertexProps()
70 : type(RIV_LITERAL), delay(0), min_offset(0),
71 max_offset(ROSE_BOUND_INF) {}
72
73private:
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
88public:
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
133struct 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
189struct RoseInGraph
190 : public ue2_graph<RoseInGraph, RoseInVertexProps, RoseInEdgeProps> {
191};
192typedef RoseInGraph::vertex_descriptor RoseInVertex;
193typedef RoseInGraph::edge_descriptor RoseInEdge;
194
195} // namespace ue2
196
197#endif
198