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
46using namespace std;
47
48namespace ue2 {
49
50namespace {
51struct 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
57struct 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
64struct 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 }
72private:
73 ReportID a_rep;
74 ReportID b_rep;
75};
76
77/** Comparison functor used to sort by vertex_index. */
78template<typename Graph>
79struct 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 }
86private:
87 const Graph &g;
88};
89
90template<typename Graph>
91static
92VertexIndexOrdering<Graph> make_index_ordering(const Graph &g) {
93 return VertexIndexOrdering<Graph>(g);
94}
95
96}
97
98static
99bool 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. */
195u64a 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
210bool 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
220bool 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