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 
50 namespace ue2 {
51 
52 /** \brief role info structure for exclusive analysis */
53 template<typename role_id>
54 struct RoleInfo {
RoleInfoRoleInfo55     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  */
81 bool 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  */
87 bool 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  */
102 void 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  */
119 void 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