1 //===- unittests/Analysis/FlowSensitive/DataflowAnalysisContextTest.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 "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
10 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
11 #include "gmock/gmock.h"
12 #include "gtest/gtest.h"
13 #include <memory>
14 
15 namespace {
16 
17 using namespace clang;
18 using namespace dataflow;
19 
20 class DataflowAnalysisContextTest : public ::testing::Test {
21 protected:
22   DataflowAnalysisContextTest()
23       : Context(std::make_unique<WatchedLiteralsSolver>()) {}
24 
25   DataflowAnalysisContext Context;
26 };
27 
28 TEST_F(DataflowAnalysisContextTest,
29        CreateAtomicBoolValueReturnsDistinctValues) {
30   auto &X = Context.createAtomicBoolValue();
31   auto &Y = Context.createAtomicBoolValue();
32   EXPECT_NE(&X, &Y);
33 }
34 
35 TEST_F(DataflowAnalysisContextTest,
36        GetOrCreateConjunctionValueReturnsSameExprGivenSameArgs) {
37   auto &X = Context.createAtomicBoolValue();
38   auto &XAndX = Context.getOrCreateConjunctionValue(X, X);
39   EXPECT_EQ(&XAndX, &X);
40 }
41 
42 TEST_F(DataflowAnalysisContextTest,
43        GetOrCreateConjunctionValueReturnsSameExprOnSubsequentCalls) {
44   auto &X = Context.createAtomicBoolValue();
45   auto &Y = Context.createAtomicBoolValue();
46   auto &XAndY1 = Context.getOrCreateConjunctionValue(X, Y);
47   auto &XAndY2 = Context.getOrCreateConjunctionValue(X, Y);
48   EXPECT_EQ(&XAndY1, &XAndY2);
49 
50   auto &YAndX = Context.getOrCreateConjunctionValue(Y, X);
51   EXPECT_EQ(&XAndY1, &YAndX);
52 
53   auto &Z = Context.createAtomicBoolValue();
54   auto &XAndZ = Context.getOrCreateConjunctionValue(X, Z);
55   EXPECT_NE(&XAndY1, &XAndZ);
56 }
57 
58 TEST_F(DataflowAnalysisContextTest,
59        GetOrCreateDisjunctionValueReturnsSameExprGivenSameArgs) {
60   auto &X = Context.createAtomicBoolValue();
61   auto &XOrX = Context.getOrCreateDisjunctionValue(X, X);
62   EXPECT_EQ(&XOrX, &X);
63 }
64 
65 TEST_F(DataflowAnalysisContextTest,
66        GetOrCreateDisjunctionValueReturnsSameExprOnSubsequentCalls) {
67   auto &X = Context.createAtomicBoolValue();
68   auto &Y = Context.createAtomicBoolValue();
69   auto &XOrY1 = Context.getOrCreateDisjunctionValue(X, Y);
70   auto &XOrY2 = Context.getOrCreateDisjunctionValue(X, Y);
71   EXPECT_EQ(&XOrY1, &XOrY2);
72 
73   auto &YOrX = Context.getOrCreateDisjunctionValue(Y, X);
74   EXPECT_EQ(&XOrY1, &YOrX);
75 
76   auto &Z = Context.createAtomicBoolValue();
77   auto &XOrZ = Context.getOrCreateDisjunctionValue(X, Z);
78   EXPECT_NE(&XOrY1, &XOrZ);
79 }
80 
81 TEST_F(DataflowAnalysisContextTest,
82        GetOrCreateNegationValueReturnsSameExprOnSubsequentCalls) {
83   auto &X = Context.createAtomicBoolValue();
84   auto &NotX1 = Context.getOrCreateNegationValue(X);
85   auto &NotX2 = Context.getOrCreateNegationValue(X);
86   EXPECT_EQ(&NotX1, &NotX2);
87 
88   auto &Y = Context.createAtomicBoolValue();
89   auto &NotY = Context.getOrCreateNegationValue(Y);
90   EXPECT_NE(&NotX1, &NotY);
91 }
92 
93 TEST_F(DataflowAnalysisContextTest, EmptyFlowCondition) {
94   auto &FC = Context.makeFlowConditionToken();
95   auto &C = Context.createAtomicBoolValue();
96   EXPECT_FALSE(Context.flowConditionImplies(FC, C));
97 }
98 
99 TEST_F(DataflowAnalysisContextTest, AddFlowConditionConstraint) {
100   auto &FC = Context.makeFlowConditionToken();
101   auto &C = Context.createAtomicBoolValue();
102   Context.addFlowConditionConstraint(FC, C);
103   EXPECT_TRUE(Context.flowConditionImplies(FC, C));
104 }
105 
106 TEST_F(DataflowAnalysisContextTest, ForkFlowCondition) {
107   auto &FC1 = Context.makeFlowConditionToken();
108   auto &C1 = Context.createAtomicBoolValue();
109   Context.addFlowConditionConstraint(FC1, C1);
110 
111   // Forked flow condition inherits the constraints of its parent flow
112   // condition.
113   auto &FC2 = Context.forkFlowCondition(FC1);
114   EXPECT_TRUE(Context.flowConditionImplies(FC2, C1));
115 
116   // Adding a new constraint to the forked flow condition does not affect its
117   // parent flow condition.
118   auto &C2 = Context.createAtomicBoolValue();
119   Context.addFlowConditionConstraint(FC2, C2);
120   EXPECT_TRUE(Context.flowConditionImplies(FC2, C2));
121   EXPECT_FALSE(Context.flowConditionImplies(FC1, C2));
122 }
123 
124 TEST_F(DataflowAnalysisContextTest, JoinFlowConditions) {
125   auto &C1 = Context.createAtomicBoolValue();
126   auto &C2 = Context.createAtomicBoolValue();
127   auto &C3 = Context.createAtomicBoolValue();
128 
129   auto &FC1 = Context.makeFlowConditionToken();
130   Context.addFlowConditionConstraint(FC1, C1);
131   Context.addFlowConditionConstraint(FC1, C3);
132 
133   auto &FC2 = Context.makeFlowConditionToken();
134   Context.addFlowConditionConstraint(FC2, C2);
135   Context.addFlowConditionConstraint(FC2, C3);
136 
137   auto &FC3 = Context.joinFlowConditions(FC1, FC2);
138   EXPECT_FALSE(Context.flowConditionImplies(FC3, C1));
139   EXPECT_FALSE(Context.flowConditionImplies(FC3, C2));
140   EXPECT_TRUE(Context.flowConditionImplies(FC3, C3));
141 }
142 
143 TEST_F(DataflowAnalysisContextTest, FlowConditionTautologies) {
144   // Fresh flow condition with empty/no constraints is always true.
145   auto &FC1 = Context.makeFlowConditionToken();
146   EXPECT_TRUE(Context.flowConditionIsTautology(FC1));
147 
148   // Literal `true` is always true.
149   auto &FC2 = Context.makeFlowConditionToken();
150   Context.addFlowConditionConstraint(FC2, Context.getBoolLiteralValue(true));
151   EXPECT_TRUE(Context.flowConditionIsTautology(FC2));
152 
153   // Literal `false` is never true.
154   auto &FC3 = Context.makeFlowConditionToken();
155   Context.addFlowConditionConstraint(FC3, Context.getBoolLiteralValue(false));
156   EXPECT_FALSE(Context.flowConditionIsTautology(FC3));
157 
158   // We can't prove that an arbitrary bool A is always true...
159   auto &C1 = Context.createAtomicBoolValue();
160   auto &FC4 = Context.makeFlowConditionToken();
161   Context.addFlowConditionConstraint(FC4, C1);
162   EXPECT_FALSE(Context.flowConditionIsTautology(FC4));
163 
164   // ... but we can prove A || !A is true.
165   auto &FC5 = Context.makeFlowConditionToken();
166   Context.addFlowConditionConstraint(
167       FC5, Context.getOrCreateDisjunctionValue(
168                C1, Context.getOrCreateNegationValue(C1)));
169   EXPECT_TRUE(Context.flowConditionIsTautology(FC5));
170 }
171 
172 } // namespace
173