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 ReportManager: tracks Report structures, exhaustion and dedupe keys.
31 */
32
33#include "report_manager.h"
34
35#include "grey.h"
36#include "ue2common.h"
37#include "compiler/compiler.h"
38#include "nfagraph/ng.h"
39#include "rose/rose_build.h"
40#include "util/compile_error.h"
41#include "util/container.h"
42
43#include <deque>
44#include <map>
45#include <sstream>
46#include <vector>
47
48using namespace std;
49
50namespace ue2 {
51
52ReportManager::ReportManager(const Grey &g)
53 : grey(g), freeEIndex(0), global_exhaust(true) {}
54
55u32 ReportManager::getInternalId(const Report &ir) {
56 auto it = reportIdToInternalMap.find(ir);
57 if (it != reportIdToInternalMap.end()) {
58 DEBUG_PRINTF("existing report %zu\n", it->second);
59 return it->second;
60 }
61
62 // Construct a new internal report and assign it a ReportID.
63
64 if (numReports() >= grey.limitReportCount) {
65 throw ResourceLimitError();
66 }
67
68 u32 size = reportIds.size();
69 reportIds.push_back(ir);
70 reportIdToInternalMap.emplace(ir, size);
71 DEBUG_PRINTF("new report %u\n", size);
72 return size;
73}
74
75const Report &ReportManager::getReport(u32 id) const {
76 assert(id < reportIds.size());
77 return reportIds.at(id);
78}
79
80size_t ReportManager::numReports() const {
81 return reportIds.size();
82}
83
84u32 ReportManager::getExhaustibleKey(u32 a) {
85 auto it = toExhaustibleKeyMap.find(a);
86 if (it == toExhaustibleKeyMap.end()) {
87 // get size before assigning to avoid wacky LHS shenanigans
88 u32 size = toExhaustibleKeyMap.size();
89 bool inserted;
90 tie(it, inserted) = toExhaustibleKeyMap.emplace(s64a{a}, size);
91 assert(inserted);
92 }
93
94 DEBUG_PRINTF("%lld -> ekey %u\n", it->first, it->second);
95 return it->second;
96}
97
98const set<u32> &ReportManager::getRelateCKeys(u32 lkey) {
99 auto it = pl.lkey2ckeys.find(lkey);
100 assert(it != pl.lkey2ckeys.end());
101 return it->second;
102}
103
104void ReportManager::logicalKeyRenumber() {
105 pl.logicalKeyRenumber();
106 // assign to corresponding report
107 for (u32 i = 0; i < reportIds.size(); i++) {
108 Report &ir = reportIds[i];
109 if (contains(pl.toLogicalKeyMap, ir.onmatch)) {
110 ir.lkey = pl.toLogicalKeyMap.at(ir.onmatch);
111 }
112 }
113}
114
115const vector<LogicalOp> &ReportManager::getLogicalTree() const {
116 return pl.logicalTree;
117}
118
119const vector<CombInfo> &ReportManager::getCombInfoMap() const {
120 return pl.combInfoMap;
121}
122
123u32 ReportManager::getUnassociatedExhaustibleKey(void) {
124 u32 rv = toExhaustibleKeyMap.size();
125 bool inserted;
126 map<s64a, u32>::const_iterator it;
127 tie(it, inserted) = toExhaustibleKeyMap.emplace(--freeEIndex, rv);
128 assert(inserted);
129 assert(it->second == rv);
130
131 return rv;
132}
133
134u32 ReportManager::numDkeys() const {
135 DEBUG_PRINTF("%zu dkeys\n", reportIdToDedupeKey.size());
136 return reportIdToDedupeKey.size();
137}
138
139u32 ReportManager::numEkeys() const {
140 return (u32) toExhaustibleKeyMap.size();
141}
142
143u32 ReportManager::numLogicalKeys() const {
144 return (u32) pl.toLogicalKeyMap.size();
145}
146
147u32 ReportManager::numLogicalOps() const {
148 return (u32) pl.logicalTree.size();
149}
150
151u32 ReportManager::numCkeys() const {
152 return (u32) pl.toCombKeyMap.size();
153}
154
155bool ReportManager::patternSetCanExhaust() const {
156 return global_exhaust && !toExhaustibleKeyMap.empty();
157}
158
159vector<ReportID> ReportManager::getDkeyToReportTable() const {
160 vector<ReportID> rv(reportIdToDedupeKey.size());
161
162 for (const auto &m : reportIdToDedupeKey) {
163 assert(m.second < rv.size());
164 rv[m.second] = m.first;
165 }
166
167 return rv;
168}
169
170void ReportManager::assignDkeys(const RoseBuild *rose) {
171 DEBUG_PRINTF("assigning...\n");
172
173 map<u32, flat_set<ReportID>> ext_to_int;
174
175 for (u32 i = 0; i < reportIds.size(); i++) {
176 const Report &ir = reportIds[i];
177
178 /* need to populate dkey */
179 if (isExternalReport(ir)) {
180 ext_to_int[ir.onmatch].insert(i);
181 }
182 }
183
184 auto dedupe = rose->generateDedupeAux();
185
186 for (const auto &m : ext_to_int) {
187 u32 ext = m.first;
188
189 if (!dedupe->requiresDedupeSupport(m.second)) {
190 DEBUG_PRINTF("%u does not require dedupe\n", ext);
191 continue; /* no dedupe required for this set */
192 }
193
194 u32 dkey = reportIdToDedupeKey.size();
195 reportIdToDedupeKey[ext] = dkey;
196 DEBUG_PRINTF("ext=%u -> dkey=%u\n", ext, dkey);
197 }
198}
199
200u32 ReportManager::getDkey(const Report &r) const {
201 if (!isExternalReport(r)) {
202 return ~u32{0};
203 }
204
205 auto it = reportIdToDedupeKey.find(r.onmatch);
206 if (it == reportIdToDedupeKey.end()) {
207 return ~u32{0};
208 }
209 return it->second;
210}
211
212void ReportManager::registerExtReport(ReportID id,
213 const external_report_info &ext) {
214 auto it = externalIdMap.find(id);
215 if (it != externalIdMap.end()) {
216 const external_report_info &eri = it->second;
217 if (eri.highlander != ext.highlander) {
218 /* we have a problem */
219 ostringstream out;
220 out << "Expression (index " << ext.first_pattern_index
221 << ") with match ID " << id << " ";
222 if (!ext.highlander) {
223 out << "did not specify ";
224 } else {
225 out << "specified ";
226 }
227 out << "HS_FLAG_SINGLEMATCH whereas previous expression (index "
228 << eri.first_pattern_index << ") with the same match ID did";
229 if (ext.highlander) {
230 out << " not";
231 }
232 out << ".";
233 throw CompileError(ext.first_pattern_index, out.str());
234 }
235 } else {
236 externalIdMap.emplace(id, ext);
237 }
238
239 // Any non-highlander pattern will render us not globally exhaustible.
240 if (!ext.highlander) {
241 global_exhaust = false;
242 }
243}
244
245Report ReportManager::getBasicInternalReport(const ExpressionInfo &expr,
246 s32 adj) {
247 /* validate that we are not violating highlander constraints, this will
248 * throw a CompileError if so. */
249 registerExtReport(expr.report,
250 external_report_info(expr.highlander, expr.index));
251
252 /* create the internal report */
253 u32 ekey = INVALID_EKEY;
254 if (expr.highlander) {
255 /* all patterns with the same report id share an ekey */
256 ekey = getExhaustibleKey(expr.report);
257 }
258
259 return makeECallback(expr.report, adj, ekey, expr.quiet);
260}
261
262void ReportManager::setProgramOffset(ReportID id, u32 programOffset) {
263 assert(id < reportIds.size());
264 assert(!contains(reportIdToProgramOffset, id));
265 reportIdToProgramOffset.emplace(id, programOffset);
266}
267
268u32 ReportManager::getProgramOffset(ReportID id) const {
269 assert(id < reportIds.size());
270 assert(contains(reportIdToProgramOffset, id));
271 return reportIdToProgramOffset.at(id);
272}
273
274static
275void ekeysUnion(std::set<u32> *ekeys, u32 more) {
276 if (!ekeys->empty()) {
277 if (more == INVALID_EKEY) {
278 ekeys->clear();
279 } else {
280 ekeys->insert(more);
281 }
282 }
283}
284
285set<u32> reportsToEkeys(const set<ReportID> &reports, const ReportManager &rm) {
286 assert(!reports.empty());
287
288 set<u32> ekeys;
289
290 for (auto it = reports.begin(), ite = reports.end(); it != ite; ++it) {
291 u32 e = rm.getReport(*it).ekey;
292 if (it == reports.begin()) {
293 if (e != INVALID_EKEY) {
294 ekeys.insert(e);
295 }
296 } else {
297 ekeysUnion(&ekeys, e);
298 }
299 }
300
301 return ekeys;
302}
303
304} // namespace ue2
305