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/**
30 * \file
31 * \brief Limex NFA construction code.
32 */
33
34#ifndef NG_LIMEX_H
35#define NG_LIMEX_H
36
37#include "ue2common.h"
38#include "som/som.h"
39#include "util/bytecode_ptr.h"
40
41#include <map>
42#include <memory>
43#include <vector>
44
45struct NFA;
46
47namespace ue2 {
48
49class CharReach;
50class NG;
51class NGHolder;
52class ReportManager;
53struct CompileContext;
54
55/**
56 * \brief Determine if the given graph is implementable as an NFA.
57 *
58 * Returns zero if the NFA is not implementable (usually because it has too
59 * many states for any of our models). Otherwise returns the number of states.
60 *
61 * ReportManager is used by NFA_SUFFIX and NFA_OUTFIX only. NFA_PREFIX and
62 * NFA_INFIX use unmanaged rose-local reports.
63 */
64u32 isImplementableNFA(const NGHolder &g, const ReportManager *rm,
65 const CompileContext &cc);
66
67/**
68 * \brief Late-stage graph reductions.
69 *
70 * This will call \ref removeRedundancy and apply its changes to the given
71 * holder only if it is implementable afterwards.
72 */
73void reduceImplementableGraph(NGHolder &g, som_type som,
74 const ReportManager *rm,
75 const CompileContext &cc);
76
77/**
78 * \brief For a given graph, count the number of accel states it will have in
79 * an implementation.
80 *
81 * \return the number of accel states, or NFA_MAX_ACCEL_STATES + 1 if an
82 * implementation would not be constructible.
83 */
84u32 countAccelStates(const NGHolder &g, const ReportManager *rm,
85 const CompileContext &cc);
86
87/**
88 * \brief Construct an NFA from the given graph.
89 *
90 * Returns zero if the NFA is not implementable (usually because it has too
91 * many states for any of our models). Otherwise returns the number of states.
92 *
93 * ReportManager is used by NFA_SUFFIX and NFA_OUTFIX only. NFA_PREFIX and
94 * NFA_INFIX use unmanaged rose-local reports.
95 *
96 * Note: this variant of the function allows a model to be specified with the
97 * \a hint parameter.
98 */
99bytecode_ptr<NFA>
100constructNFA(const NGHolder &g, const ReportManager *rm,
101 const std::map<u32, u32> &fixed_depth_tops,
102 const std::map<u32, std::vector<std::vector<CharReach>>> &triggers,
103 bool compress_state, const CompileContext &cc);
104
105/**
106 * \brief Build a reverse NFA from the graph given, which should have already
107 * been reversed.
108 *
109 * Used for reverse NFAs used in SOM mode.
110 */
111bytecode_ptr<NFA> constructReversedNFA(const NGHolder &h,
112 const CompileContext &cc);
113
114#ifndef RELEASE_BUILD
115
116/**
117 * \brief Construct an NFA (with model type hint) from the given graph.
118 *
119 * Returns zero if the NFA is not implementable (usually because it has too
120 * many states for any of our models). Otherwise returns the number of states.
121 *
122 * ReportManager is used by NFA_SUFFIX and NFA_OUTFIX only. NFA_PREFIX and
123 * NFA_INFIX use unmanaged rose-local reports.
124 *
125 * Note: this variant of the function allows a model to be specified with the
126 * \a hint parameter.
127 */
128bytecode_ptr<NFA>
129constructNFA(const NGHolder &g, const ReportManager *rm,
130 const std::map<u32, u32> &fixed_depth_tops,
131 const std::map<u32, std::vector<std::vector<CharReach>>> &triggers,
132 bool compress_state, u32 hint, const CompileContext &cc);
133
134/**
135 * \brief Build a reverse NFA (with model type hint) from the graph given,
136 * which should have already been reversed.
137 *
138 * Used for reverse NFAs used in SOM mode.
139 */
140bytecode_ptr<NFA> constructReversedNFA(const NGHolder &h, u32 hint,
141 const CompileContext &cc);
142
143#endif // RELEASE_BUILD
144
145} // namespace ue2
146
147#endif // NG_METEOR_H
148