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 Castle: multi-tenant repeat engine, compiler code. |
32 | */ |
33 | |
34 | #ifndef NFA_CASTLECOMPILE_H |
35 | #define NFA_CASTLECOMPILE_H |
36 | |
37 | #include "nfa_kind.h" |
38 | #include "ue2common.h" |
39 | #include "nfagraph/ng_repeat.h" |
40 | #include "util/bytecode_ptr.h" |
41 | #include "util/depth.h" |
42 | #include "util/flat_containers.h" |
43 | |
44 | #include <map> |
45 | #include <memory> |
46 | #include <set> |
47 | #include <unordered_map> |
48 | #include <vector> |
49 | |
50 | struct NFA; |
51 | |
52 | namespace ue2 { |
53 | |
54 | class CharReach; |
55 | class NGHolder; |
56 | class ReportManager; |
57 | struct CompileContext; |
58 | |
59 | /** |
60 | * \brief Prototype for a Castle engine: contains at least one CastleRepeat. |
61 | * |
62 | * Currently, all repeats in a Castle must have the same character |
63 | * reachability. |
64 | * |
65 | * A CastleProto is converted into a single NFA, with each top triggering a |
66 | * unique repeat. A CastleProto can contain at most CastleProto::max_occupancy |
67 | * elements. |
68 | */ |
69 | struct CastleProto { |
70 | static constexpr size_t max_occupancy = 65536; // arbitrary limit |
71 | CastleProto(nfa_kind k, const PureRepeat &pr); |
72 | const CharReach &reach() const; |
73 | |
74 | /** \brief Add a new repeat. */ |
75 | u32 add(const PureRepeat &pr); |
76 | |
77 | /** \brief Remove a repeat. */ |
78 | void erase(u32 top); |
79 | |
80 | /** |
81 | * \brief Merge in the given repeat, returning the top used. |
82 | * |
83 | * If the repeat already exists in this castle, we will re-use (and return) |
84 | * the old top. If it doesn't, it will be added and assigned a new top. |
85 | * Returns \ref max_occupancy if capacity would be exceeded. |
86 | */ |
87 | u32 merge(const PureRepeat &pr); |
88 | |
89 | /** \brief Mapping from unique top id to repeat. */ |
90 | std::map<u32, PureRepeat> repeats; |
91 | |
92 | /** \brief Mapping from report to associated tops. */ |
93 | std::unordered_map<ReportID, flat_set<u32>> report_map; |
94 | |
95 | /** |
96 | * \brief Next top id to use. Repeats may be removed without top remapping, |
97 | * so we track this explicitly instead of using repeats.size(). |
98 | */ |
99 | u32 next_top = 1; |
100 | |
101 | /** \brief Kind for this engine. */ |
102 | nfa_kind kind; |
103 | }; |
104 | |
105 | std::set<ReportID> all_reports(const CastleProto &proto); |
106 | depth findMinWidth(const CastleProto &proto); |
107 | depth findMaxWidth(const CastleProto &proto); |
108 | depth findMinWidth(const CastleProto &proto, u32 top); |
109 | depth findMaxWidth(const CastleProto &proto, u32 top); |
110 | |
111 | /** |
112 | * \brief Remap tops to be contiguous. |
113 | * |
114 | * Remap the tops in the given CastleProto so that they're contiguous in the |
115 | * range [0 .. N-1]. |
116 | */ |
117 | void remapCastleTops(CastleProto &proto, std::map<u32, u32> &top_map); |
118 | |
119 | /** |
120 | * \brief Construct an NFA from a CastleProto. |
121 | * |
122 | * NOTE: Tops must be contiguous, i.e. \ref remapCastleTops must have been run |
123 | * first. |
124 | */ |
125 | bytecode_ptr<NFA> |
126 | buildCastle(const CastleProto &proto, |
127 | const std::map<u32, std::vector<std::vector<CharReach>>> &triggers, |
128 | const CompileContext &cc, const ReportManager &rm); |
129 | |
130 | /** |
131 | * \brief Merge two CastleProto prototypes together, if possible. If a |
132 | * particular repeat from c2 is already in c1, then it will be reused rather |
133 | * than adding a duplicate repeat. |
134 | * |
135 | * Returns true if merge of all repeats in c2 into c1 succeeds, and fills |
136 | * mapping with the repeat indices. |
137 | */ |
138 | bool mergeCastle(CastleProto &c1, const CastleProto &c2, |
139 | std::map<u32, u32> &top_map); |
140 | |
141 | /** |
142 | * \brief True if the two castles are identical with respect to the reports |
143 | * given; i.e. the same tops lead to the same repeats, just with report1 in c1 |
144 | * and report2 in c2. |
145 | * |
146 | * Repeats leading to other reports are ignored. |
147 | */ |
148 | bool is_equal(const CastleProto &c1, ReportID report1, const CastleProto &c2, |
149 | ReportID report2); |
150 | |
151 | /** |
152 | * \brief True if the two castles given are identical. |
153 | */ |
154 | bool is_equal(const CastleProto &c1, const CastleProto &c2); |
155 | |
156 | /** |
157 | * \brief True if the given castle contains more than a single instance of any |
158 | * of the reports in the given set. |
159 | */ |
160 | bool requiresDedupe(const CastleProto &proto, |
161 | const flat_set<ReportID> &reports); |
162 | |
163 | /** |
164 | * \brief Build an NGHolder from a CastleProto. |
165 | */ |
166 | std::unique_ptr<NGHolder> makeHolder(const CastleProto &castle, |
167 | const CompileContext &cc); |
168 | |
169 | } // namespace ue2 |
170 | |
171 | #endif // NFA_CASTLECOMPILE_H |
172 | |