souffle  2.0.2-371-g6315b36
binary_relation_test.cpp
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2017, The Souffle Developers 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 binary_relation_test.cpp
12  *
13  * A test case testing the binary relation member functions
14  *
15  ***********************************************************************/
16 
17 #include "tests/test.h"
18 
19 #include "souffle/RamTypes.h"
20 #include "souffle/utility/ContainerUtil.h"
21 #include <algorithm>
22 #include <iostream>
23 #include <random>
24 #include <string>
25 #include <utility>
26 #include <vector>
27 
28 #include <cstddef>
29 
30 #ifdef _OPENMP
31 #include <omp.h>
32 #endif
33 
34 #include "souffle/datastructure/EquivalenceRelation.h"
35 
36 namespace souffle {
37 namespace test {
38 
39 TEST(EqRelTest, Scoping) {
40  // simply test that namespaces were setup correctly
41  souffle::EquivalenceRelation<souffle::Tuple<RamDomain, 2>> br;
42 }
43 
44 using EqRel = souffle::EquivalenceRelation<Tuple<RamDomain, 2>>;
45 
46 TEST(EqRelTest, Basic) {
47  EqRel br;
48  // empty bin rel should be exactly that
49  EXPECT_EQ(br.size(), 0);
50  EXPECT_FALSE(br.contains(1, 2));
51  EXPECT_FALSE(br.contains(0, 0));
52 
53  // test implicit rules
54  br.insert(1, 2);
55  EXPECT_EQ(br.size(), 4);
56  EXPECT_TRUE(br.contains(1, 2));
57  EXPECT_TRUE(br.contains(2, 1));
58  EXPECT_TRUE(br.contains(1, 1));
59  EXPECT_TRUE(br.contains(2, 2));
60 
61  // test insert of exactly one pair
62  br.insert(3, 3);
63  EXPECT_EQ(br.size(), 5);
64  EXPECT_TRUE(br.contains(3, 3));
65  EXPECT_FALSE(br.contains(1, 3));
66  EXPECT_FALSE(br.contains(3, 2));
67  size_t count = 0;
68  for (auto x : br) {
69  ++count;
70  testutil::ignore(x);
71  }
72  EXPECT_EQ(count, br.size());
73 }
74 
75 TEST(EqRelTest, Clear) {
76  EqRel br;
77  br.insert(0, 44);
78  br.insert(0, 1);
79 
80  EXPECT_EQ(9, br.size());
81  size_t count = 0;
82  for (auto x : br) {
83  ++count;
84  testutil::ignore(x);
85  }
86  EXPECT_EQ(count, br.size());
87  br.clear();
88  EXPECT_EQ(0, br.size());
89  count = 0;
90  for (auto x : br) {
91  ++count;
92  testutil::ignore(x);
93  }
94  EXPECT_EQ(count, br.size());
95 }
96 
97 TEST(EqRelTest, Duplicates) {
98  EqRel br;
99  // test inserting same pair
100  for (int i = 0; i < 10; ++i) {
101  br.insert(0, 0);
102  }
103  EXPECT_EQ(br.size(), 1);
104 
105  for (int i = 0; i < 10; ++i) {
106  EXPECT_TRUE(br.contains(0, 0));
107  }
108  EXPECT_EQ(br.size(), 1);
109  EXPECT_FALSE(br.contains(1, 1));
110 
111  // check iteration of duplicate is fine
112  Tuple<RamDomain, 2> tup;
113  tup[0] = 0;
114  tup[1] = 0;
115  auto x = br.begin();
116  EXPECT_EQ(tup, *x);
117  ++x;
118  EXPECT_EQ(x, br.end());
119 }
120 
121 TEST(EqRelTest, TransitivityTest) {
122  // test (a,b) && (b, c) => (a,c) etc
123  EqRel br;
124  br.insert(1, 2);
125  br.insert(2, 3);
126  EXPECT_EQ(br.size(), 9);
127  size_t count = 0;
128  for (auto x : br) {
129  ++count;
130  testutil::ignore(x);
131  }
132  EXPECT_EQ(count, br.size());
133  EXPECT_TRUE(br.contains(1, 1));
134  EXPECT_TRUE(br.contains(1, 2));
135  EXPECT_TRUE(br.contains(1, 3));
136  EXPECT_TRUE(br.contains(2, 1));
137  EXPECT_TRUE(br.contains(2, 2));
138  EXPECT_TRUE(br.contains(2, 3));
139  EXPECT_TRUE(br.contains(3, 1));
140  EXPECT_TRUE(br.contains(3, 2));
141  EXPECT_TRUE(br.contains(3, 3));
142 }
143 
144 TEST(EqRelTest, PairwiseIncremental) {
145  EqRel br;
146 
147  const size_t N = 100;
148  // test inserting ascending pairs still isolates them
149  for (size_t i = 1; i < N; ++i) {
150  br.insert(i, i);
151  EXPECT_TRUE(br.contains(i, i));
152  br.insert(i + (N + 1), i);
153  EXPECT_TRUE(br.contains(i, i + (N + 1)));
154  EXPECT_TRUE(br.contains(i + (N + 1), i + (N + 1)));
155  EXPECT_TRUE(br.contains(i + (N + 1), i));
156  }
157  EXPECT_EQ(br.size(), (N - 1) * 4);
158  size_t count = 0;
159  for (auto x : br) {
160  ++count;
161  testutil::ignore(x);
162  }
163  EXPECT_EQ(count, br.size());
164 }
165 
166 TEST(EqRelTest, PairwiseDecremental) {
167  EqRel br;
168 
169  const size_t N = 100;
170  // test inserting descending pairs still isolates them
171  for (size_t i = N; i > 1; --i) {
172  br.insert(i, i);
173  EXPECT_TRUE(br.contains(i, i));
174  br.insert(i + (N + 1), i);
175  EXPECT_TRUE(br.contains(i, i + (N + 1)));
176  EXPECT_TRUE(br.contains(i + (N + 1), i + (N + 1)));
177  EXPECT_TRUE(br.contains(i + (N + 1), i));
178  }
179 
180  EXPECT_EQ(br.size(), (N - 1) * 4);
181  size_t count = 0;
182  for (auto x : br) {
183  ++count;
184  testutil::ignore(x);
185  }
186  EXPECT_EQ(count, br.size());
187 }
188 
189 TEST(EqRelTest, Shuffled) {
190  EqRel br;
191 
192  size_t N = 100;
193  // test inserting data "out of order" keeps isolation
194  std::vector<int> data;
195  for (size_t i = 0; i < N; i++) {
196  data.push_back(i);
197  }
198  std::random_device rd;
199  std::mt19937 generator(rd());
200 
201  shuffle(data.begin(), data.end(), generator);
202 
203  for (auto x : data) {
204  br.insert(x, x);
205  }
206 
207  for (size_t i = 0; i < N; ++i) {
208  EXPECT_TRUE(br.contains(i, i));
209  }
210 
211  EXPECT_EQ(br.size(), N);
212 
213  // always check the iterator for size too
214  size_t count = 0;
215  for (auto x : br) {
216  ++count;
217  testutil::ignore(x);
218  }
219  EXPECT_EQ(count, br.size());
220 }
221 
222 TEST(EqRelTest, Extend) {
223  // test running extend for a relation
224 
225  // br is {{0,1,2,3,4,5,6}, {8,9}, {44, 70}, {11}}
226  EqRel br;
227 
228  br.insert(0, 1);
229  br.insert(0, 2);
230  br.insert(0, 3);
231  br.insert(0, 4);
232  br.insert(0, 5);
233  br.insert(0, 6);
234 
235  br.insert(8, 9);
236 
237  br.insert(44, 70);
238 
239  br.insert(11, 11);
240  EXPECT_EQ(br.size(), (7 * 7) + (2 * 2) + (2 * 2) + (1 * 1));
241 
242  // br2 is {{0,8,33,99}, {68,69,70}, {101, 102}}
243  EqRel br2;
244  br2.insert(33, 8);
245  br2.insert(33, 99);
246  br2.insert(33, 0);
247 
248  br2.insert(69, 68);
249  br2.insert(69, 70);
250 
251  br2.insert(101, 102);
252  EXPECT_EQ(br2.size(), (4 * 4) + (3 * 3) + (2 * 2));
253 
254  // let's say br2 the new knowledge, so we must extend it to actually contain the implied knowledge from
255  // new
256  br2.extend(br);
257 
258  // it should contain {0,1,2,3,4,5,6,8,9,33,99}, {44, 68, 69, 70}, {101, 102}
259  // shouldn't contain {11}.
260  EXPECT_TRUE(br2.contains(0, 0));
261  EXPECT_TRUE(br2.contains(0, 1));
262  EXPECT_TRUE(br2.contains(1, 8));
263  EXPECT_TRUE(br2.contains(9, 4));
264  EXPECT_TRUE(br2.contains(33, 4));
265  EXPECT_TRUE(br2.contains(33, 99));
266 
267  EXPECT_TRUE(br2.contains(68, 69));
268  EXPECT_TRUE(br2.contains(70, 44));
269 
270  EXPECT_FALSE(br2.contains(11, 11));
271 
272  EXPECT_FALSE(br2.contains(0, 69));
273  EXPECT_TRUE(br2.contains(101, 102));
274 
275  // check this hasn't changed size
276  EXPECT_EQ(br.size(), (7 * 7) + (2 * 2) + (2 * 2) + (1 * 1));
277  // check that it was properly extended
278  EXPECT_EQ(br2.size(), (11 * 11) + (4 * 4) + (2 * 2));
279 }
280 
281 TEST(EqRelTest, Merge) {
282  // test insertAll isolates data
283  EqRel br;
284 
285  int N = 100;
286 
287  std::vector<int> data;
288  for (int i = 0; i < N; i++) {
289  data.push_back(i);
290  }
291  std::random_device rd;
292  std::mt19937 generator(rd());
293 
294  shuffle(data.begin(), data.end(), generator);
295 
296  for (int i = 0; i < N; i++) {
297  br.insert(data[i], data[i]);
298  }
299 
300  // also insert a joint pair
301  br.insert(N - 1, N + 1);
302 
303  EXPECT_EQ((size_t)N + 3, br.size());
304 
305  EqRel br2;
306  EXPECT_EQ(0, br2.size());
307 
308  size_t count = 0;
309  for (auto x : br2) {
310  ++count;
311  testutil::ignore(x);
312  }
313  EXPECT_EQ(count, br2.size());
314 
315  br2.insertAll(br);
316  EXPECT_EQ((size_t)N + 3, br2.size());
317  EXPECT_EQ((size_t)N + 3, br.size());
318  count = 0;
319  for (auto x : br2) {
320  ++count;
321  testutil::ignore(x);
322  }
323  EXPECT_EQ(count, br2.size());
324 
325  br.clear();
326  EXPECT_EQ((size_t)N + 3, br2.size());
327  EXPECT_EQ(0, br.size());
328  EXPECT_FALSE(br.begin() != br.end());
329 
330  count = 0;
331  for (auto x : br) {
332  ++count;
333  testutil::ignore(x);
334  }
335  EXPECT_EQ(count, br.size());
336 
337  br2.clear();
338  EXPECT_EQ(0, br2.size());
339  EXPECT_EQ(0, br.size());
340 
341  count = 0;
342  for (auto x : br2) {
343  ++count;
344  testutil::ignore(x);
345  }
346  EXPECT_EQ(count, br2.size());
347 }
348 
349 TEST(EqRelTest, IterEmpty) {
350  // test iterating over an empty binrel fails
351  EqRel br;
352  for (auto x : br) {
353  EXPECT_FALSE(true);
354  testutil::ignore(x);
355  }
356  EXPECT_EQ(0, br.size());
357 }
358 
359 TEST(EqRelTest, IterBasic) {
360  EqRel br;
361  br.insert(0, 0);
362  br.insert(1, 1);
363  br.insert(2, 2);
364 
365  size_t count = 0;
366  for (auto x : br) {
367  ++count;
368  testutil::ignore(x);
369  }
370 
371  EXPECT_EQ(count, br.size());
372  // merge one disjoint set
373  br.insert(0, 1);
374  count = 0;
375  for (auto x : br) {
376  ++count;
377  testutil::ignore(x);
378  }
379 
380  EXPECT_EQ(count, br.size());
381 }
382 
383 TEST(EqRelTest, IterRange) {
384  // write some tests to use that templated range for different indexes too
385  EqRel br;
386  br.insert(0, 1);
387  br.insert(0, 2);
388  br.insert(0, 3);
389  br.insert(0, 4);
390  br.insert(0, 5);
391  br.insert(0, 6);
392 
393  br.insert(8, 9);
394  br.insert(8, 10);
395 
396  // this should return an iterator covering (3, 0), (3, 1), ..., (3, 6), it's a (3, *) iterator
397  auto rangeIt = br.getBoundaries<1>({{3, 18293018}});
398 
399  std::vector<size_t> posteriorsCovered;
400  for (auto tup : rangeIt) {
401  posteriorsCovered.push_back(tup[1]);
402  }
403  EXPECT_EQ(posteriorsCovered.size(), 7);
404 
405  // this should be of everything, so doesn't matter the args
406  rangeIt = br.getBoundaries<0>({{332, 888}});
407  posteriorsCovered.clear();
408  for (auto tup : rangeIt) {
409  posteriorsCovered.push_back(tup[1]);
410  }
411  EXPECT_EQ(posteriorsCovered.size(), (7 * 7) + (3 * 3));
412 
413  // and now iterate over two levels (exactly one pretty much)
414  rangeIt = br.getBoundaries<2>({{2, 3}});
415  posteriorsCovered.clear();
416  for (auto tup : rangeIt) {
417  posteriorsCovered.push_back(tup[1]);
418  }
419  EXPECT_EQ(posteriorsCovered.size(), 1);
420  EXPECT_EQ(posteriorsCovered.front(), 3);
421 
422  // and now the same, but for levels 1 and two, stuff that doesn't exist
423  rangeIt = br.getBoundaries<1>({{99, 99}});
424  posteriorsCovered.clear();
425  for (auto tup : rangeIt) {
426  posteriorsCovered.push_back(tup[1]);
427  }
428  EXPECT_EQ(posteriorsCovered.size(), 0);
429 
430  rangeIt = br.getBoundaries<2>({{8, 1}});
431  posteriorsCovered.clear();
432  for (auto tup : rangeIt) {
433  posteriorsCovered.push_back(tup[1]);
434  }
435  EXPECT_EQ(posteriorsCovered.size(), 0);
436 
437  // and now the same for an empty binary relation
438  br.clear();
439  // repeat the same, but notice that we expect the size to be 0 always
440  {
441  auto rangeIt = br.getBoundaries<1>({{3, 18293018}});
442 
443  std::vector<size_t> posteriorsCovered;
444  for (auto tup : rangeIt) {
445  posteriorsCovered.push_back(tup[1]);
446  }
447  EXPECT_EQ(posteriorsCovered.size(), 0);
448 
449  // this should be of everything, so doesn't matter the args
450  rangeIt = br.getBoundaries<0>({{332, 888}});
451  posteriorsCovered.clear();
452  for (auto tup : rangeIt) {
453  posteriorsCovered.push_back(tup[1]);
454  }
455  EXPECT_EQ(posteriorsCovered.size(), 0);
456 
457  // and now iterate over two levels (exactly one pretty much)
458  rangeIt = br.getBoundaries<2>({{2, 3}});
459  posteriorsCovered.clear();
460  for (auto tup : rangeIt) {
461  posteriorsCovered.push_back(tup[1]);
462  }
463  EXPECT_EQ(posteriorsCovered.size(), 0);
464 
465  // and now the same, but for levels 1 and two, stuff that doesn't exist
466  rangeIt = br.getBoundaries<1>({{99, 99}});
467  posteriorsCovered.clear();
468  for (auto tup : rangeIt) {
469  posteriorsCovered.push_back(tup[1]);
470  }
471  EXPECT_EQ(posteriorsCovered.size(), 0);
472 
473  rangeIt = br.getBoundaries<2>({{8, 1}});
474  posteriorsCovered.clear();
475  for (auto tup : rangeIt) {
476  posteriorsCovered.push_back(tup[1]);
477  }
478  EXPECT_EQ(posteriorsCovered.size(), 0);
479  }
480 }
481 
482 TEST(EqRelTest, IterPartition) {
483  // test that the union equals the input
484 
485  // test single set binary rel
486  EqRel br;
487  std::vector<std::pair<RamDomain, RamDomain>> values;
488  RamDomain N = 1000;
489  for (RamDomain i = 0; i < N; ++i) {
490  br.insert(i, i + 1);
491  }
492 
493  EXPECT_EQ(size_t((N + 1) * (N + 1)), br.size());
494 
495  auto chunks = br.partition(400);
496  // we can't make too many assumptions..
497  EXPECT_TRUE(chunks.size() > 0);
498 
499  for (auto chunk : chunks) {
500  for (auto x : chunk) {
501  values.push_back(std::make_pair(x[0], x[1]));
502  }
503  }
504 
505  EXPECT_EQ(br.size(), values.size());
506 
507  br.clear();
508  values.clear();
509  chunks.clear();
510 
511  // many disjoint sets (note, can't use N, because even & odd numbers don't work the same..)
512  for (RamDomain i = 0; i < 1000; i += 2) {
513  br.insert(i, i + 1);
514  }
515  EXPECT_EQ((size_t)4 * 1000 / 2, br.size());
516 
517  chunks = br.partition(400);
518  for (auto chunk : chunks) {
519  for (auto x : chunk) {
520  values.push_back(std::make_pair(x[0], x[1]));
521  }
522  }
523 
524  EXPECT_EQ(br.size(), values.size());
525 }
526 
527 TEST(EqRelTest, Scaling) {
528  const int N = 100;
529 
530  EqRel br;
531  for (int i = 0; i < N; ++i) {
532  br.insert(i, i);
533  }
534 
535  EXPECT_EQ(N, br.size());
536 }
537 
538 #ifdef _OPENMP
539 TEST(EqRelTest, ParallelScaling) {
540  // use OpenMP this time
541 
542  // test with varying number of threads (100000 will likely catch a race condition)
543  const int N = 100000;
544  std::vector<int> data1;
545  std::vector<int> data2;
546  for (int i = 0; i < N; ++i)
547  data1.push_back(i);
548  for (int i = 0; i < N; ++i)
549  data2.push_back(i);
550 
551  std::random_device rd;
552  std::mt19937 generator(rd());
553 
554  shuffle(data1.begin(), data1.end(), generator);
555  shuffle(data2.begin(), data2.end(), generator);
556 
557  std::cout << "number of threads: " << omp_get_max_threads() << std::endl;
558 
559  EqRel br;
560 #pragma omp parallel for
561  for (int i = 0; i < N; i++) {
562  // unfortunately, we can't do insert(data1, data2) as we won't know how many pairs...
563  br.insert(data1[i], data1[i]);
564  br.insert(data2[i], data2[i]);
565  }
566 
567  EXPECT_EQ(N, br.size());
568  if (N != br.size()) {
569  throw std::runtime_error("here's a gdb trap");
570  }
571 }
572 #endif
573 
574 } // namespace test
575 } // namespace souffle
EXPECT_TRUE
#define EXPECT_TRUE(a)
Definition: test.h:189
souffle::RamDomain
int32_t RamDomain
Definition: RamTypes.h:56
souffle::EquivalenceRelation::contains
bool contains(value_type x, value_type y) const
Returns whether there exists a pair with these two nodes.
Definition: EquivalenceRelation.h:199
EXPECT_EQ
#define EXPECT_EQ(a, b)
Definition: test.h:191
testutil::ignore
void ignore(const T &)
Definition: test.h:70
souffle::EquivalenceRelation::size
size_t size() const
Size of relation.
Definition: EquivalenceRelation.h:242
souffle::EquivalenceRelation::extend
void extend(const EquivalenceRelation< TupleType > &other)
Extend this relation with another relation, expanding this equivalence relation The supplied relation...
Definition: EquivalenceRelation.h:152
souffle::test::EqRel
souffle::EquivalenceRelation< Tuple< RamDomain, 2 > > EqRel
Definition: binary_relation_test.cpp:56
i
size_t i
Definition: json11.h:663
ContainerUtil.h
souffle::test::count
int count(const C &c)
Definition: table_test.cpp:40
test.h
souffle::Tuple
std::array< A, N > Tuple
Definition: RamTypes.h:36
souffle::EquivalenceRelation::insert
bool insert(value_type x, value_type y)
Insert the two values symbolically as a binary relation.
Definition: EquivalenceRelation.h:94
EquivalenceRelation.h
RamTypes.h
souffle
Definition: AggregateOp.h:25
TCB_SPAN_NAMESPACE_NAME::detail::data
constexpr auto data(C &c) -> decltype(c.data())
Definition: span.h:210
souffle::EquivalenceRelation
Definition: EquivalenceRelation.h:50
EXPECT_FALSE
#define EXPECT_FALSE(a)
Definition: test.h:190
souffle::test::TEST
TEST(EqRelTest, Scoping)
Definition: binary_relation_test.cpp:51
Generated by   doxygen 1.8.17