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 | /** \file |
30 | * \brief Loose equality testing for NGHolder graphs. |
31 | * |
32 | * Loose equality check for holders' graph structure and vertex_index, |
33 | * vertex_char_reach and (optionally reports). |
34 | */ |
35 | #include "ng_is_equal.h" |
36 | |
37 | #include "grey.h" |
38 | #include "ng_holder.h" |
39 | #include "ng_util.h" |
40 | #include "ue2common.h" |
41 | #include "util/container.h" |
42 | #include "util/flat_containers.h" |
43 | #include "util/graph_range.h" |
44 | #include "util/make_unique.h" |
45 | |
46 | using namespace std; |
47 | |
48 | namespace ue2 { |
49 | |
50 | namespace { |
51 | struct check_report { |
52 | virtual ~check_report() {} |
53 | virtual bool operator()(const flat_set<ReportID> &reports_a, |
54 | const flat_set<ReportID> &reports_b) const = 0; |
55 | }; |
56 | |
57 | struct full_check_report : public check_report { |
58 | bool operator()(const flat_set<ReportID> &reports_a, |
59 | const flat_set<ReportID> &reports_b) const override { |
60 | return reports_a == reports_b; |
61 | } |
62 | }; |
63 | |
64 | struct equiv_check_report : public check_report { |
65 | equiv_check_report(ReportID a_in, ReportID b_in) |
66 | : a_rep(a_in), b_rep(b_in) {} |
67 | |
68 | bool operator()(const flat_set<ReportID> &reports_a, |
69 | const flat_set<ReportID> &reports_b) const override { |
70 | return contains(reports_a, a_rep) == contains(reports_b, b_rep); |
71 | } |
72 | private: |
73 | ReportID a_rep; |
74 | ReportID b_rep; |
75 | }; |
76 | |
77 | /** Comparison functor used to sort by vertex_index. */ |
78 | template<typename Graph> |
79 | struct VertexIndexOrdering { |
80 | explicit VertexIndexOrdering(const Graph &g_in) : g(g_in) {} |
81 | bool operator()(typename Graph::vertex_descriptor a, |
82 | typename Graph::vertex_descriptor b) const { |
83 | assert(a == b || g[a].index != g[b].index); |
84 | return g[a].index < g[b].index; |
85 | } |
86 | private: |
87 | const Graph &g; |
88 | }; |
89 | |
90 | template<typename Graph> |
91 | static |
92 | VertexIndexOrdering<Graph> make_index_ordering(const Graph &g) { |
93 | return VertexIndexOrdering<Graph>(g); |
94 | } |
95 | |
96 | } |
97 | |
98 | static |
99 | bool is_equal_i(const NGHolder &a, const NGHolder &b, |
100 | const check_report &check_rep) { |
101 | assert(hasCorrectlyNumberedVertices(a)); |
102 | assert(hasCorrectlyNumberedVertices(b)); |
103 | |
104 | size_t num_verts = num_vertices(a); |
105 | if (num_verts != num_vertices(b)) { |
106 | return false; |
107 | } |
108 | |
109 | vector<NFAVertex> vert_a; |
110 | vector<NFAVertex> vert_b; |
111 | vector<NFAVertex> adj_a; |
112 | vector<NFAVertex> adj_b; |
113 | |
114 | vert_a.reserve(num_verts); |
115 | vert_b.reserve(num_verts); |
116 | adj_a.reserve(num_verts); |
117 | adj_b.reserve(num_verts); |
118 | |
119 | insert(&vert_a, vert_a.end(), vertices(a)); |
120 | insert(&vert_b, vert_b.end(), vertices(b)); |
121 | |
122 | sort(vert_a.begin(), vert_a.end(), make_index_ordering(a)); |
123 | sort(vert_b.begin(), vert_b.end(), make_index_ordering(b)); |
124 | |
125 | for (size_t i = 0; i < vert_a.size(); i++) { |
126 | NFAVertex va = vert_a[i]; |
127 | NFAVertex vb = vert_b[i]; |
128 | DEBUG_PRINTF("vertex %zu\n" , a[va].index); |
129 | |
130 | // Vertex index must be the same. |
131 | if (a[va].index != b[vb].index) { |
132 | DEBUG_PRINTF("bad index\n" ); |
133 | return false; |
134 | } |
135 | |
136 | // Reach must be the same. |
137 | if (a[va].char_reach != b[vb].char_reach) { |
138 | DEBUG_PRINTF("bad reach\n" ); |
139 | return false; |
140 | } |
141 | |
142 | if (!check_rep(a[va].reports, b[vb].reports)) { |
143 | DEBUG_PRINTF("bad reports\n" ); |
144 | return false; |
145 | } |
146 | |
147 | // Other vertex properties may vary. |
148 | |
149 | /* Check successors */ |
150 | adj_a.clear(); |
151 | adj_b.clear(); |
152 | insert(&adj_a, adj_a.end(), adjacent_vertices(va, a)); |
153 | insert(&adj_b, adj_b.end(), adjacent_vertices(vb, b)); |
154 | |
155 | if (adj_a.size() != adj_b.size()) { |
156 | DEBUG_PRINTF("bad adj\n" ); |
157 | return false; |
158 | } |
159 | |
160 | sort(adj_a.begin(), adj_a.end(), make_index_ordering(a)); |
161 | sort(adj_b.begin(), adj_b.end(), make_index_ordering(b)); |
162 | |
163 | for (size_t j = 0; j < adj_a.size(); j++) { |
164 | if (a[adj_a[j]].index != b[adj_b[j]].index) { |
165 | DEBUG_PRINTF("bad adj\n" ); |
166 | return false; |
167 | } |
168 | } |
169 | } |
170 | |
171 | /* check top for edges out of start */ |
172 | vector<pair<u32, flat_set<u32>>> top_a; |
173 | vector<pair<u32, flat_set<u32>>> top_b; |
174 | |
175 | for (const auto &e : out_edges_range(a.start, a)) { |
176 | top_a.emplace_back(a[target(e, a)].index, a[e].tops); |
177 | } |
178 | for (const auto &e : out_edges_range(b.start, b)) { |
179 | top_b.emplace_back(b[target(e, b)].index, b[e].tops); |
180 | } |
181 | |
182 | sort(top_a.begin(), top_a.end()); |
183 | sort(top_b.begin(), top_b.end()); |
184 | |
185 | if (top_a != top_b) { |
186 | DEBUG_PRINTF("bad top\n" ); |
187 | return false; |
188 | } |
189 | |
190 | DEBUG_PRINTF("good\n" ); |
191 | return true; |
192 | } |
193 | |
194 | /** \brief loose hash of an NGHolder; equal if is_equal would return true. */ |
195 | u64a hash_holder(const NGHolder &g) { |
196 | size_t rv = 0; |
197 | |
198 | for (auto v : vertices_range(g)) { |
199 | hash_combine(rv, g[v].index); |
200 | hash_combine(rv, g[v].char_reach); |
201 | |
202 | for (auto w : adjacent_vertices_range(v, g)) { |
203 | hash_combine(rv, g[w].index); |
204 | } |
205 | } |
206 | |
207 | return rv; |
208 | } |
209 | |
210 | bool is_equal(const NGHolder &a, const NGHolder &b) { |
211 | DEBUG_PRINTF("testing %p %p\n" , &a, &b); |
212 | |
213 | if (&a == &b) { |
214 | return true; |
215 | } |
216 | |
217 | return is_equal_i(a, b, full_check_report()); |
218 | } |
219 | |
220 | bool is_equal(const NGHolder &a, ReportID a_rep, |
221 | const NGHolder &b, ReportID b_rep) { |
222 | DEBUG_PRINTF("testing %p %p\n" , &a, &b); |
223 | |
224 | if (&a == &b && a_rep == b_rep) { |
225 | return true; |
226 | } |
227 | |
228 | return is_equal_i(a, b, equiv_check_report(a_rep, b_rep)); |
229 | } |
230 | |
231 | } // namespace ue2 |
232 | |