1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "util/relation.h"
17
18 #include "util/tests/verifier_test.h"
19
20 #include "runtime/include/mem/panda_containers.h"
21
22 #include <gtest/gtest.h>
23
24 namespace panda::verifier::test {
25
TEST_F(VerifierTest,Relation0)26 TEST_F(VerifierTest, Relation0)
27 {
28 Relation relation;
29 using Set = PandaSet<size_t>;
30 relation.EnsureMinSize(8);
31
32 /*
33 +--> 2 --+
34 | |
35 | v
36 1 4
37 | ^
38 | |
39 +--> 3 --+
40 */
41 relation += {{1, 2}, {1, 3}, {2, 4}, {3, 4}};
42
43 auto get_set_from = [&relation](size_t from) {
44 Set result;
45 relation.ForAllFrom(from, [&result](size_t to) {
46 result.insert(to);
47 return true;
48 });
49 return result;
50 };
51
52 auto get_set_to = [&relation](size_t to) {
53 Set result;
54 relation.ForAllTo(to, [&result](size_t from) {
55 result.insert(from);
56 return true;
57 });
58 return result;
59 };
60
61 auto lhs = get_set_from(1);
62 auto rhs = (Set {2, 3, 4});
63 EXPECT_EQ(lhs, rhs);
64 EXPECT_EQ(get_set_from(1), (Set {2, 3, 4}));
65 EXPECT_EQ(get_set_from(2), (Set {4}));
66 EXPECT_EQ(get_set_from(3), (Set {4}));
67 EXPECT_EQ(get_set_to(4), (Set {1, 2, 3}));
68 EXPECT_EQ(get_set_to(2), (Set {1}));
69 EXPECT_EQ(get_set_to(3), (Set {1}));
70 }
71
TEST_F(VerifierTest,Relation1)72 TEST_F(VerifierTest, Relation1)
73 {
74 Relation relation;
75 using Set = PandaSet<size_t>;
76 relation.EnsureMinSize(8);
77 // check classes of equivalence, formed by loops in relation
78 // object in loop are relationally indistinguishable
79
80 /* +-----------+
81 v |
82 +--> 2 --+ |
83 | | +--> 5
84 | v /
85 1 4 -----> 6
86 | ^
87 | |
88 +--> 3 --+
89 */
90 relation += {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 2}, {4, 6}};
91
92 auto get_set_from = [&relation](size_t from) {
93 Set result;
94 relation.ForAllFrom(from, [&result](size_t to) {
95 result.insert(to);
96 return true;
97 });
98 return result;
99 };
100
101 auto get_set_to = [&relation](size_t to) {
102 Set result;
103 relation.ForAllTo(to, [&result](size_t from) {
104 result.insert(from);
105 return true;
106 });
107 return result;
108 };
109
110 EXPECT_EQ(get_set_to(4), get_set_to(5));
111 EXPECT_EQ(get_set_to(4), get_set_to(2));
112 EXPECT_EQ(get_set_from(4), get_set_from(5));
113 EXPECT_EQ(get_set_from(4), get_set_from(2));
114 }
115
TEST_F(VerifierTest,Relation2)116 TEST_F(VerifierTest, Relation2)
117 {
118 Relation relation;
119
120 using Set = PandaSet<size_t>;
121
122 relation.EnsureMinSize(8);
123 /* +-----------+
124 v |
125 +--> 2 --+ |
126 | | +--> 5
127 | v /
128 1 4 -----> 6 -----> 7
129 | ^ ^
130 | | /
131 +--> 3 --+ /
132 \------------------/
133 */
134
135 relation += {{6, 7}, {3, 7}, {1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 2}, {4, 6}};
136
137 auto get_set_between = [&relation](size_t from, size_t to) {
138 Set result;
139 relation.ForAllBetween(from, to, [&result](size_t elt) {
140 result.insert(elt);
141 return true;
142 });
143 return result;
144 };
145
146 EXPECT_EQ(get_set_between(3, 7), Set({2, 4, 5, 6}));
147 }
148 } // namespace panda::verifier::test
149