souffle  2.0.2-371-g6315b36
type_system_test.cpp
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file type_system_test.cpp
12  *
13  * Tests souffle's type system operations.
14  *
15  ***********************************************************************/
16 
17 #include "tests/test.h"
18 
19 #include "ast/analysis/TypeSystem.h"
20 #include "souffle/TypeAttribute.h"
21 #include "souffle/utility/ContainerUtil.h"
22 #include "souffle/utility/StringUtil.h"
23 #include <algorithm>
24 #include <cstddef>
25 #include <string>
26 #include <vector>
27 
28 namespace souffle::ast::test {
29 using namespace analysis;
30 
31 TEST(TypeSystem, Basic) {
32  TypeEnvironment env;
33 
34  const analysis::Type& A = env.createType<SubsetType>("A", env.getType("number"));
35  const analysis::Type& B = env.createType<SubsetType>("B", env.getType("symbol"));
36 
37  auto& U = env.createType<UnionType>("U", toVector(&A, &B));
38 
39  auto& R = env.createType<RecordType>("R");
40  R.setFields(toVector(&A, &B));
41 
42  EXPECT_EQ("A <: number", toString(A));
43  EXPECT_EQ("B <: symbol", toString(B));
44 
45  EXPECT_EQ("U = A | B", toString(U));
46  EXPECT_EQ("R = (A, B)", toString(R));
47 }
48 
49 TEST(TypeSystem, isNumberType) {
50  TypeEnvironment env;
51 
52  const analysis::Type& N = env.getType("number");
53 
54  const analysis::Type& A = env.createType<SubsetType>("A", env.getType("number"));
55  const analysis::Type& B = env.createType<SubsetType>("B", env.getType("number"));
56 
57  const analysis::Type& C = env.createType<SubsetType>("C", env.getType("symbol"));
58 
59  EXPECT_TRUE(isOfKind(N, TypeAttribute::Signed));
60  EXPECT_TRUE(isOfKind(A, TypeAttribute::Signed));
61  EXPECT_TRUE(isOfKind(B, TypeAttribute::Signed));
62  EXPECT_TRUE(isOfKind(C, TypeAttribute::Symbol));
63 
64  EXPECT_FALSE(isOfKind(N, TypeAttribute::Symbol));
65  EXPECT_FALSE(isOfKind(A, TypeAttribute::Symbol));
66  EXPECT_FALSE(isOfKind(B, TypeAttribute::Symbol));
67  EXPECT_FALSE(isOfKind(C, TypeAttribute::Signed));
68 
69  // check the union type
70  {
71  const analysis::Type& U = env.createType<UnionType>("U", toVector(&A, &B));
72  EXPECT_TRUE(isOfKind(U, TypeAttribute::Signed));
73  EXPECT_FALSE(isOfKind(U, TypeAttribute::Symbol));
74  const analysis::Type& U2 = env.createType<UnionType>("U2", toVector(&A, &B, &C));
75  EXPECT_FALSE(isOfKind(U2, TypeAttribute::Signed));
76  EXPECT_FALSE(isOfKind(U2, TypeAttribute::Symbol));
77  }
78  {
79  const analysis::Type& U3 = env.createType<UnionType>("U3", toVector(&A));
80  EXPECT_TRUE(isOfKind(U3, TypeAttribute::Signed));
81  }
82 }
83 
84 bool isNotSubtypeOf(const analysis::Type& a, const analysis::Type& b) {
85  return !isSubtypeOf(a, b);
86 }
87 
88 TEST(TypeSystem, isSubtypeOf_Basic) {
89  TypeEnvironment env;
90 
91  // start with the two predefined types
92 
93  const analysis::Type& N = env.getType("number");
94  const analysis::Type& S = env.getType("symbol");
95 
96  EXPECT_PRED2(isSubtypeOf, N, N);
97  EXPECT_PRED2(isSubtypeOf, S, S);
98 
99  EXPECT_PRED2(isNotSubtypeOf, N, S);
100  EXPECT_PRED2(isNotSubtypeOf, S, N);
101 
102  // check primitive type
103 
104  const analysis::Type& A = env.createType<SubsetType>("A", env.getType("number"));
105  const analysis::Type& B = env.createType<SubsetType>("B", env.getType("number"));
106 
107  EXPECT_PRED2(isSubtypeOf, A, A);
108  EXPECT_PRED2(isSubtypeOf, B, B);
109 
110  EXPECT_PRED2(isNotSubtypeOf, A, B);
111  EXPECT_PRED2(isNotSubtypeOf, B, A);
112 
113  EXPECT_PRED2(isSubtypeOf, A, N);
114  EXPECT_PRED2(isSubtypeOf, B, N);
115 
116  EXPECT_PRED2(isNotSubtypeOf, A, S);
117  EXPECT_PRED2(isNotSubtypeOf, B, S);
118 
119  // check union types
120 
121  const analysis::Type& U = env.createType<UnionType>("U", toVector(&A, &B));
122 
123  EXPECT_PRED2(isSubtypeOf, U, U);
124  EXPECT_PRED2(isSubtypeOf, A, U);
125  EXPECT_PRED2(isSubtypeOf, B, U);
126  EXPECT_PRED2(isSubtypeOf, U, N);
127 
128  EXPECT_PRED2(isNotSubtypeOf, U, A);
129  EXPECT_PRED2(isNotSubtypeOf, U, B);
130  EXPECT_PRED2(isNotSubtypeOf, N, U);
131 
132  auto& V = env.createType<UnionType>("V", toVector(&A, &B, &U));
133 
134  EXPECT_PRED2(isSubtypeOf, V, U);
135  EXPECT_PRED2(isSubtypeOf, U, V);
136 }
137 
138 TEST(TypeSystem, isSubtypeOf_Records) {
139  TypeEnvironment env;
140 
141  const analysis::Type& A = env.createType<SubsetType>("A", env.getType("number"));
142  const analysis::Type& B = env.createType<SubsetType>("B", env.getType("number"));
143 
144  auto& R1 = env.createType<RecordType>("R1");
145  auto& R2 = env.createType<RecordType>("R2");
146 
147  EXPECT_FALSE(isSubtypeOf(R1, R2));
148  EXPECT_FALSE(isSubtypeOf(R2, R1));
149 
150  R1.setFields(toVector(&A));
151  R2.setFields(toVector(&B));
152 
153  EXPECT_FALSE(isSubtypeOf(R1, R2));
154  EXPECT_FALSE(isSubtypeOf(R2, R1));
155 }
156 
157 TEST(TypeSystem, GreatestCommonSubtype) {
158  TypeEnvironment env;
159 
160  const analysis::Type& N = env.getType("number");
161 
162  const analysis::Type& A = env.createType<SubsetType>("A", env.getType("number"));
163  const analysis::Type& B = env.createType<SubsetType>("B", env.getType("number"));
164  const analysis::Type& C = env.createType<SubsetType>("C", env.getType("symbol"));
165 
166  EXPECT_EQ("{number}", toString(getGreatestCommonSubtypes(N, N)));
167 
168  EXPECT_EQ("{A}", toString(getGreatestCommonSubtypes(A, A)));
169  EXPECT_EQ("{B}", toString(getGreatestCommonSubtypes(B, B)));
170  EXPECT_EQ("{C}", toString(getGreatestCommonSubtypes(C, C)));
171 
172  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(A, B)));
173  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(A, C)));
174  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(B, C)));
175 
176  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(A, B, C)));
177 
178  EXPECT_EQ("{A}", toString(getGreatestCommonSubtypes(A, N)));
179  EXPECT_EQ("{A}", toString(getGreatestCommonSubtypes(N, A)));
180 
181  EXPECT_EQ("{B}", toString(getGreatestCommonSubtypes(B, N)));
182  EXPECT_EQ("{B}", toString(getGreatestCommonSubtypes(N, B)));
183 
184  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(C, N)));
185  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(N, C)));
186 
187  // // bring in unions
188 
189  auto& U = env.createType<UnionType>("U");
190  auto& S = env.createType<UnionType>("S");
191 
192  U.setElements(toVector(&A));
193  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(U, S)));
194 
195  S.setElements(toVector(&A));
196  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, S)));
197 
198  U.setElements(toVector(&A, &B));
199  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(U, S)));
200  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(U, S, N)));
201 
202  S.setElements(toVector(&A, &B));
203  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, S)));
204  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, S, N)));
205 
206  // bring in a union of unions
207  auto& R = env.createType<UnionType>("R");
208 
209  EXPECT_EQ("{R}", toString(getGreatestCommonSubtypes(U, R)));
210  EXPECT_EQ("{R}", toString(getGreatestCommonSubtypes(S, R)));
211 
212  EXPECT_EQ("{R}", toString(getGreatestCommonSubtypes(U, R, N)));
213  EXPECT_EQ("{R}", toString(getGreatestCommonSubtypes(S, R, N)));
214 
215  R.setElements(toVector(static_cast<const analysis::Type*>(&U))); // R = U = S
216 
217  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, R)));
218  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(S, R)));
219 
220  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, R, N)));
221  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(S, R, N)));
222 
223  R.setElements(toVector(static_cast<const analysis::Type*>(&U), static_cast<const analysis::Type*>(&S)));
224 
225  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, R)));
226  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(S, R)));
227 
228  EXPECT_EQ("{U}", toString(getGreatestCommonSubtypes(U, R, N)));
229  EXPECT_EQ("{S}", toString(getGreatestCommonSubtypes(S, R, N)));
230 }
231 
232 TEST(TypeSystem, complexSubsetTypes) {
233  TypeEnvironment env;
234 
235  auto& A = env.createType<SubsetType>("A", env.getType("number"));
236  auto& BfromA = env.createType<SubsetType>("B", A);
237  auto& CfromA = env.createType<SubsetType>("C", A);
238 
239  EXPECT_EQ("{B}", toString(getGreatestCommonSubtypes(A, BfromA)));
240  EXPECT_EQ("{C}", toString(getGreatestCommonSubtypes(A, CfromA)));
241  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(A, BfromA, CfromA)));
242  EXPECT_EQ("{}", toString(getGreatestCommonSubtypes(BfromA, CfromA)));
243 
244  auto* base = &env.createType<SubsetType>("B0", BfromA);
245  for (size_t i = 1; i <= 10; ++i) {
246  base = &env.createType<SubsetType>("B" + std::to_string(i), *base);
247  EXPECT_PRED2(isSubtypeOf, *base, A);
248  }
249 }
250 
251 TEST(TypeSystem, RecordSubsets) {
252  TypeEnvironment env;
253 
254  auto& R = env.createType<RecordType>("R");
255 
256  auto& A = env.createType<SubsetType>("A", R);
257  EXPECT_PRED2(isSubtypeOf, A, R);
258 
259  EXPECT_EQ("{A}", toString(getGreatestCommonSubtypes(A, R)));
260 }
261 
262 TEST(TypeSystem, EquivTypes) {
263  TypeEnvironment env;
264 
265  auto& A = env.createType<SubsetType>("A", env.getType("number"));
266  auto& U = env.createType<UnionType>("U", toVector(dynamic_cast<const analysis::Type*>(&A)));
267 
268  EXPECT_TRUE(areEquivalentTypes(A, U));
269 }
270 
271 TEST(TypeSystem, AlgebraicDataType) {
272  TypeEnvironment env;
273 
274  auto& A = env.createType<AlgebraicDataType>("A");
275 
276  EXPECT_TRUE(isSubtypeOf(A, A));
277  EXPECT_EQ("{A}", toString(getGreatestCommonSubtypes(A, A)));
278 }
279 
280 } // namespace souffle::ast::test
souffle::ast::test
Definition: ast_parser_utils_test.cpp:38
souffle::ast::analysis::isOfKind
bool isOfKind(const Type &type, TypeAttribute kind)
Check if the type is of a kind corresponding to the TypeAttribute.
Definition: TypeSystem.cpp:189
EXPECT_TRUE
#define EXPECT_TRUE(a)
Definition: test.h:189
souffle::ast::analysis::areEquivalentTypes
bool areEquivalentTypes(const Type &a, const Type &b)
Determine if two types are equivalent.
Definition: TypeSystem.cpp:373
souffle::ast::test::TEST
TEST(RuleBody, Basic)
Definition: ast_parser_utils_test.cpp:46
souffle::ast::analysis::TypeEnvironment::getType
const Type & getType(const QualifiedName &) const
Definition: TypeSystem.cpp:81
souffle::TypeAttribute::Symbol
@ Symbol
EXPECT_EQ
#define EXPECT_EQ(a, b)
Definition: test.h:191
S
#define S(x)
Definition: test.h:179
souffle::ast::analysis::SubsetType
A type being a subset of another type.
Definition: TypeSystem.h:108
base
T & base
Definition: Reader.h:60
souffle::ast::analysis::UnionType
A union type combining a list of types into a new, aggregated type.
Definition: TypeSystem.h:146
souffle::ast::analysis::Type
An abstract base class for types to be covered within a type environment.
Definition: TypeSystem.h:51
souffle::ast::test::isNotSubtypeOf
bool isNotSubtypeOf(const analysis::Type &a, const analysis::Type &b)
Definition: type_system_test.cpp:90
souffle::ast::analysis::RecordType
A record type combining a list of fields into a new, aggregated type.
Definition: TypeSystem.h:170
souffle::TypeAttribute::Signed
@ Signed
souffle::ast::analysis::getGreatestCommonSubtypes
TypeSet getGreatestCommonSubtypes(const Type &a, const Type &b)
Computes the greatest common sub types of the two given types.
Definition: TypeSystem.cpp:254
souffle::toString
const std::string & toString(const std::string &str)
A generic function converting strings into strings (trivial case).
Definition: StringUtil.h:234
souffle::ast::analysis::isSubtypeOf
static TypeConstraint isSubtypeOf(const TypeVar &a, const TypeVar &b)
A constraint factory ensuring that all the types associated to the variable a are subtypes of the var...
Definition: TypeConstraints.cpp:27
i
size_t i
Definition: json11.h:663
ContainerUtil.h
StringUtil.h
souffle::ast::analysis::TypeEnvironment
A type environment is a set of types.
Definition: TypeSystem.h:401
test.h
EXPECT_PRED2
#define EXPECT_PRED2(p, a, b)
Definition: test.h:207
souffle::toVector
std::vector< T > toVector()
A utility function enabling the creation of a vector with a fixed set of elements within a single exp...
Definition: ContainerUtil.h:128
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::ast::analysis::TypeEnvironment::createType
T & createType(const QualifiedName &name, Args &&... args)
create type in this environment
Definition: TypeSystem.h:411
souffle::ast::analysis::RecordType::setFields
void setFields(std::vector< const Type * > newFields)
Definition: TypeSystem.h:172
souffle::ast::AlgebraicDataType
Combination of types using sums and products.
Definition: AlgebraicDataType.h:55
EXPECT_FALSE
#define EXPECT_FALSE(a)
Definition: test.h:190
TypeAttribute.h
TypeSystem.h
souffle::ast::analysis::UnionType::setElements
void setElements(std::vector< const Type * > elements)
Definition: TypeSystem.h:152
Generated by   doxygen 1.8.17