Debian Codegraph @

llvm-project/clang/unittests/Analysis/FlowSensitive/SolverTest.cpp

raw
1 //===- unittests/Analysis/FlowSensitive/SolverTest.cpp --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include <utility>
10
11 #include "TestingSupport.h"
12 #include "clang/Analysis/FlowSensitive/Solver.h"
13 #include "clang/Analysis/FlowSensitive/Value.h"
14 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
15 #include "gmock/gmock.h"
16 #include "gtest/gtest.h"
17
18 namespace {
19
20 using namespace clang;
21 using namespace dataflow;
22
23 using test::ConstraintContext;
24 using testing::_;
25 using testing::AnyOf;
26 using testing::IsEmpty;
27 using testing::Optional;
28 using testing::Pair;
29 using testing::UnorderedElementsAre;
30
31 // Checks if the conjunction of `Vals` is satisfiable and returns the
32 // corresponding result.
33 Solver::Result solve(llvm::DenseSet<BoolValue *> Vals) {
34 return WatchedLiteralsSolver().solve(std::move(Vals));
35 }
36
37 void expectUnsatisfiable(Solver::Result Result) {
38 EXPECT_EQ(Result.getStatus(), Solver::Result::Status::Unsatisfiable);
39 EXPECT_FALSE(Result.getSolution().has_value());
40 }
41
42 template <typename Matcher>
43 void expectSatisfiable(Solver::Result Result, Matcher Solution) {
44 EXPECT_EQ(Result.getStatus(), Solver::Result::Status::Satisfiable);
45 EXPECT_THAT(Result.getSolution(), Optional(Solution));
46 }
47
48 TEST(SolverTest, Var) {
49 ConstraintContext Ctx;
50 auto X = Ctx.atom();
51
52 // X
53 expectSatisfiable(
54 solve({X}),
55 UnorderedElementsAre(Pair(X, Solver::Result::Assignment::AssignedTrue)));
56 }
57
58 TEST(SolverTest, NegatedVar) {
59 ConstraintContext Ctx;
60 auto X = Ctx.atom();
61 auto NotX = Ctx.neg(X);
62
63 // !X
64 expectSatisfiable(
65 solve({NotX}),
66 UnorderedElementsAre(Pair(X, Solver::Result::Assignment::AssignedFalse)));
67 }
68
69 TEST(SolverTest, UnitConflict) {
70 ConstraintContext Ctx;
71 auto X = Ctx.atom();
72 auto NotX = Ctx.neg(X);
73
74 // X ^ !X
75 expectUnsatisfiable(solve({X, NotX}));
76 }
77
78 TEST(SolverTest, DistinctVars) {
79 ConstraintContext Ctx;
80 auto X = Ctx.atom();
81 auto Y = Ctx.atom();
82 auto NotY = Ctx.neg(Y);
83
84 // X ^ !Y
85 expectSatisfiable(
86 solve({X, NotY}),
87 UnorderedElementsAre(Pair(X, Solver::Result::Assignment::AssignedTrue),
88 Pair(Y, Solver::Result::Assignment::AssignedFalse)));
89 }
90
91 TEST(SolverTest, Top) {
92 ConstraintContext Ctx;
93 auto X = Ctx.top();
94
95 // X. Since Top is anonymous, we do not get any results in the solution.
96 expectSatisfiable(solve({X}), IsEmpty());
97 }
98
99 TEST(SolverTest, NegatedTop) {
100 ConstraintContext Ctx;
101 auto X = Ctx.top();
102
103 // !X
104 expectSatisfiable(solve({Ctx.neg(X)}), IsEmpty());
105 }
106
107 TEST(SolverTest, DistinctTops) {
108 ConstraintContext Ctx;
109 auto X = Ctx.top();
110 auto Y = Ctx.top();
111 auto NotY = Ctx.neg(Y);
112
113 // X ^ !Y
114 expectSatisfiable(solve({X, NotY}), IsEmpty());
115 }
116
117 TEST(SolverTest, DoubleNegation) {
118 ConstraintContext Ctx;
119 auto X = Ctx.atom();
120 auto NotX = Ctx.neg(X);
121 auto NotNotX = Ctx.neg(NotX);
122
123 // !!X ^ !X
124 expectUnsatisfiable(solve({NotNotX, NotX}));
125 }
126
127 TEST(SolverTest, NegatedDisjunction) {
128 ConstraintContext Ctx;
129 auto X = Ctx.atom();
130 auto Y = Ctx.atom();
131 auto XOrY = Ctx.disj(X, Y);
132 auto NotXOrY = Ctx.neg(XOrY);
133
134 // !(X v Y) ^ (X v Y)
135 expectUnsatisfiable(solve({NotXOrY, XOrY}));
136 }
137
138 TEST(SolverTest, NegatedConjunction) {
139 ConstraintContext Ctx;
140 auto X = Ctx.atom();
141 auto Y = Ctx.atom();
142 auto XAndY = Ctx.conj(X, Y);
143 auto NotXAndY = Ctx.neg(XAndY);
144
145 // !(X ^ Y) ^ (X ^ Y)
146 expectUnsatisfiable(solve({NotXAndY, XAndY}));
147 }
148
149 TEST(SolverTest, DisjunctionSameVarWithNegation) {
150 ConstraintContext Ctx;
151 auto X = Ctx.atom();
152 auto NotX = Ctx.neg(X);
153 auto XOrNotX = Ctx.disj(X, NotX);
154
155 // X v !X
156 expectSatisfiable(solve({XOrNotX}), _);
157 }
158
159 TEST(SolverTest, DisjunctionSameVar) {
160 ConstraintContext Ctx;
161 auto X = Ctx.atom();
162 auto XOrX = Ctx.disj(X, X);
163
164 // X v X
165 expectSatisfiable(solve({XOrX}), _);
166 }
167
168 TEST(SolverTest, ConjunctionSameVarsConflict) {
169 ConstraintContext Ctx;
170 auto X = Ctx.atom();
171 auto NotX = Ctx.neg(X);
172 auto XAndNotX = Ctx.conj(X, NotX);
173
174 // X ^ !X
175 expectUnsatisfiable(solve({XAndNotX}));
176 }
177
178 TEST(SolverTest, ConjunctionSameVar) {
179 ConstraintContext Ctx;
180 auto X = Ctx.atom();
181 auto XAndX = Ctx.conj(X, X);
182
183 // X ^ X
184 expectSatisfiable(solve({XAndX}), _);
185 }
186
187 TEST(SolverTest, PureVar) {
188 ConstraintContext Ctx;
189 auto X = Ctx.atom();
190 auto Y = Ctx.atom();
191 auto NotX = Ctx.neg(X);
192 auto NotXOrY = Ctx.disj(NotX, Y);
193 auto NotY = Ctx.neg(Y);
194 auto NotXOrNotY = Ctx.disj(NotX, NotY);
195
196 // (!X v Y) ^ (!X v !Y)
197 expectSatisfiable(
198 solve({NotXOrY, NotXOrNotY}),
199 UnorderedElementsAre(Pair(X, Solver::Result::Assignment::AssignedFalse),
200 Pair(Y, _)));
201 }
202
203 TEST(SolverTest, MustAssumeVarIsFalse) {
204 ConstraintContext Ctx;
205 auto X = Ctx.atom();
206 auto Y = Ctx.atom();
207 auto XOrY = Ctx.disj(X, Y);
208 auto NotX = Ctx.neg(X);
209 auto NotXOrY = Ctx.disj(NotX, Y);
210 auto NotY = Ctx.neg(Y);
211 auto NotXOrNotY = Ctx.disj(NotX, NotY);
212
213 // (X v Y) ^ (!X v Y) ^ (!X v !Y)
214 expectSatisfiable(
215 solve({XOrY, NotXOrY, NotXOrNotY}),
216 UnorderedElementsAre(Pair(X, Solver::Result::Assignment::AssignedFalse),
217 Pair(Y, Solver::Result::Assignment::AssignedTrue)));
218 }
219
220 TEST(SolverTest, DeepConflict) {
221 ConstraintContext Ctx;
222 auto X = Ctx.atom();
223 auto Y = Ctx.atom();
224 auto XOrY = Ctx.disj(X, Y);
225 auto NotX = Ctx.neg(X);
226 auto NotXOrY = Ctx.disj(NotX, Y);
227 auto NotY = Ctx.neg(Y);
228 auto NotXOrNotY = Ctx.disj(NotX, NotY);
229 auto XOrNotY = Ctx.disj(X, NotY);
230
231 // (X v Y) ^ (!X v Y) ^ (!X v !Y) ^ (X v !Y)
232 expectUnsatisfiable(solve({XOrY, NotXOrY, NotXOrNotY, XOrNotY}));
233 }
234
235 TEST(SolverTest, IffIsEquivalentToDNF) {
236 ConstraintContext Ctx;
237 auto X = Ctx.atom();
238 auto Y = Ctx.atom();
239 auto NotX = Ctx.neg(X);
240 auto NotY = Ctx.neg(Y);
241 auto XIffY = Ctx.iff(X, Y);
242 auto XIffYDNF = Ctx.disj(Ctx.conj(X, Y), Ctx.conj(NotX, NotY));
243 auto NotEquivalent = Ctx.neg(Ctx.iff(XIffY, XIffYDNF));
244
245 // !((X <=> Y) <=> ((X ^ Y) v (!X ^ !Y)))
246 expectUnsatisfiable(solve({NotEquivalent}));
247 }
248
249 TEST(SolverTest, IffSameVars) {
250 ConstraintContext Ctx;
251 auto X = Ctx.atom();
252 auto XEqX = Ctx.iff(X, X);
253
254 // X <=> X
255 expectSatisfiable(solve({XEqX}), _);
256 }
257
258 TEST(SolverTest, IffDistinctVars) {
259 ConstraintContext Ctx;
260 auto X = Ctx.atom();
261 auto Y = Ctx.atom();
262 auto XEqY = Ctx.iff(X, Y);
263
264 // X <=> Y
265 expectSatisfiable(
266 solve({XEqY}),
267 AnyOf(UnorderedElementsAre(
268 Pair(X, Solver::Result::Assignment::AssignedTrue),
269 Pair(Y, Solver::Result::Assignment::AssignedTrue)),
270 UnorderedElementsAre(
271 Pair(X, Solver::Result::Assignment::AssignedFalse),
272 Pair(Y, Solver::Result::Assignment::AssignedFalse))));
273 }
274
275 TEST(SolverTest, IffWithUnits) {
276 ConstraintContext Ctx;
277 auto X = Ctx.atom();
278 auto Y = Ctx.atom();
279 auto XEqY = Ctx.iff(X, Y);
280
281 // (X <=> Y) ^ X ^ Y
282 expectSatisfiable(
283 solve({XEqY, X, Y}),
284 UnorderedElementsAre(Pair(X, Solver::Result::Assignment::AssignedTrue),
285 Pair(Y, Solver::Result::Assignment::AssignedTrue)));
286 }
287
288 TEST(SolverTest, IffWithUnitsConflict) {
289 ConstraintContext Ctx;
290 auto X = Ctx.atom();
291 auto Y = Ctx.atom();
292 auto XEqY = Ctx.iff(X, Y);
293 auto NotY = Ctx.neg(Y);
294
295 // (X <=> Y) ^ X !Y
296 expectUnsatisfiable(solve({XEqY, X, NotY}));
297 }
298
299 TEST(SolverTest, IffTransitiveConflict) {
300 ConstraintContext Ctx;
301 auto X = Ctx.atom();
302 auto Y = Ctx.atom();
303 auto Z = Ctx.atom();
304 auto XEqY = Ctx.iff(X, Y);
305 auto YEqZ = Ctx.iff(Y, Z);
306 auto NotX = Ctx.neg(X);
307
308 // (X <=> Y) ^ (Y <=> Z) ^ Z ^ !X
309 expectUnsatisfiable(solve({XEqY, YEqZ, Z, NotX}));
310 }
311
312 TEST(SolverTest, DeMorgan) {
313 ConstraintContext Ctx;
314 auto X = Ctx.atom();
315 auto Y = Ctx.atom();
316 auto Z = Ctx.atom();
317 auto W = Ctx.atom();
318
319 // !(X v Y) <=> !X ^ !Y
320 auto A = Ctx.iff(Ctx.neg(Ctx.disj(X, Y)), Ctx.conj(Ctx.neg(X), Ctx.neg(Y)));
321
322 // !(Z ^ W) <=> !Z v !W
323 auto B = Ctx.iff(Ctx.neg(Ctx.conj(Z, W)), Ctx.disj(Ctx.neg(Z), Ctx.neg(W)));
324
325 // A ^ B
326 expectSatisfiable(solve({A, B}), _);
327 }
328
329 TEST(SolverTest, RespectsAdditionalConstraints) {
330 ConstraintContext Ctx;
331 auto X = Ctx.atom();
332 auto Y = Ctx.atom();
333 auto XEqY = Ctx.iff(X, Y);
334 auto NotY = Ctx.neg(Y);
335
336 // (X <=> Y) ^ X ^ !Y
337 expectUnsatisfiable(solve({XEqY, X, NotY}));
338 }
339
340 TEST(SolverTest, ImplicationIsEquivalentToDNF) {
341 ConstraintContext Ctx;
342 auto X = Ctx.atom();
343 auto Y = Ctx.atom();
344 auto XImpliesY = Ctx.impl(X, Y);
345 auto XImpliesYDNF = Ctx.disj(Ctx.neg(X), Y);
346 auto NotEquivalent = Ctx.neg(Ctx.iff(XImpliesY, XImpliesYDNF));
347
348 // !((X => Y) <=> (!X v Y))
349 expectUnsatisfiable(solve({NotEquivalent}));
350 }
351
352 TEST(SolverTest, ImplicationConflict) {
353 ConstraintContext Ctx;
354 auto X = Ctx.atom();
355 auto Y = Ctx.atom();
356 auto *XImplY = Ctx.impl(X, Y);
357 auto *XAndNotY = Ctx.conj(X, Ctx.neg(Y));
358
359 // X => Y ^ X ^ !Y
360 expectUnsatisfiable(solve({XImplY, XAndNotY}));
361 }
362
363 } // namespace