1/*
2 * Copyright (c) 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/** \file
30 * \brief exclusive analysis for infix and suffix engines.
31 * Two engines are considered as exclusive if they can never be alive
32 * at the same time. This analysis takes advantage of the property of
33 * triggering literal + engine graph. If the triggering literals of
34 * two engines can make all the states dead in each other's graph,
35 * then they are exclusive.
36 */
37#ifndef ROSE_BUILD_EXCLUSIVE_H
38#define ROSE_BUILD_EXCLUSIVE_H
39
40#include "ue2common.h"
41
42#include "rose_build_impl.h"
43#include "util/alloc.h"
44#include "util/charreach.h"
45
46#include <map>
47#include <set>
48#include <vector>
49
50namespace ue2 {
51
52/** \brief role info structure for exclusive analysis */
53template<typename role_id>
54struct RoleInfo {
55 RoleInfo(role_id role_in, u32 id_in) : role(role_in), id(id_in) {}
56 bool operator==(const RoleInfo &b) const {
57 return id == b.id;
58 }
59 bool operator!=(const RoleInfo &b) const { return !(*this == b); }
60 bool operator<(const RoleInfo &b) const {
61 const RoleInfo &a = *this;
62 if (a.score != b.score) {
63 return a.score > b.score;
64 }
65 ORDER_CHECK(id);
66 return false;
67 }
68
69 std::vector<std::vector<CharReach>> literals; // prefix literals
70 CharReach prefix_cr; // reach of prefix literals
71 CharReach last_cr; // reach of the last character of literals
72 CharReach cr; // reach of engine graph
73 const role_id role; // infix or suffix info
74 const u32 id; // infix or suffix id
75 u32 score = ~0U; // score for exclusive analysis
76};
77
78/**
79 * \brief add triggering literals to infix info.
80 */
81bool setTriggerLiteralsInfix(RoleInfo<left_id> &roleInfo,
82 const std::map<u32, std::vector<std::vector<CharReach>>> &triggers);
83
84/**
85 * \brief add triggering literals to suffix info.
86 */
87bool setTriggerLiteralsSuffix(RoleInfo<suffix_id> &roleInfo,
88 const std::map<u32, std::vector<std::vector<CharReach>>> &triggers);
89
90/**
91 * Exclusive analysis for infix engines.
92 *
93 * @param build rose build info mainly used to set exclusive chunk size here
94 * @param vertex_map mapping between engine id and rose vertices
95 * related to this engine
96 * @param roleInfoSet structure contains role properties including infix info,
97 * triggering literals and literal reachabilities.
98 * Used for exclusive analysis.
99 * @param exclusive_roles output mapping between engine id and its exclusive
100 * group id
101 */
102void exclusiveAnalysisInfix(const RoseBuildImpl &build,
103 const std::map<u32, std::vector<RoseVertex>> &vertex_map,
104 std::set<RoleInfo<left_id>> &roleInfoSet,
105 std::vector<std::vector<u32>> &exclusive_roles);
106
107/**
108 * Exclusive analysis for suffix engines.
109 *
110 * @param build rose build info mainly used to set exclusive chunk size here
111 * @param vertex_map mapping between engine id and rose vertices
112 * related to this engine
113 * @param roleInfoSet structure contains role properties including suffix info,
114 * triggering literals and literal reachabilities.
115 * Used for exclusive analysis.
116 * @param exclusive_roles output mapping between engine id and its exclusive
117 * group id
118 */
119void exclusiveAnalysisSuffix(const RoseBuildImpl &build,
120 const std::map<u32, std::vector<RoseVertex>> &vertex_map,
121 std::set<RoleInfo<suffix_id>> &roleInfoSet,
122 std::vector<std::vector<u32>> &exclusive_roles);
123
124} // namespace ue2
125
126#endif //ROSE_BUILD_EXCLUSIVE_H
127
128