1/*
2 * Copyright © 2021 Google, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24#include <gtest/gtest.h>
25#include "util/dag.h"
26
27class dag_test : public ::testing::Test {
28protected:
29   dag_test();
30   ~dag_test();
31
32   void *mem_ctx;
33   struct util_dynarray expect, actual;
34   struct dag *dag;
35};
36
37dag_test::dag_test()
38{
39   mem_ctx = ralloc_context(NULL);
40   util_dynarray_init(&expect, mem_ctx);
41   util_dynarray_init(&actual, mem_ctx);
42   dag = dag_create(mem_ctx);
43}
44
45dag_test::~dag_test()
46{
47   ralloc_free(mem_ctx);
48}
49
50struct node: public dag_node {
51   int val;
52
53   /* Overload >> to make describing our test case graphs easier to read */
54   struct node &operator>>(struct node &child) {
55      dag_add_edge(static_cast<struct dag_node *>(this),
56                   static_cast<struct dag_node *>(&child), NULL);
57      return child;
58   }
59};
60
61static void output_cb(struct dag_node *dag_node, void *data)
62{
63   struct node *node = static_cast<struct node *>(dag_node);
64   struct util_dynarray *output = (struct util_dynarray *)data;
65   util_dynarray_append(output, int, node->val);
66}
67
68static void
69init_nodes(struct dag *dag, struct node *nodes, unsigned num_nodes)
70{
71   for (unsigned i = 0; i < num_nodes; i++) {
72      dag_init_node(dag, static_cast<struct dag_node *>(&nodes[i]));
73      nodes[i].val = i;
74   }
75}
76
77#define INIT_NODES(num_nodes)                            \
78   typedef struct { int order[num_nodes]; } result_type; \
79   struct node node[(num_nodes)];                        \
80   init_nodes(dag, node, (num_nodes))
81
82#define SET_EXPECTED(...) do {                           \
83	result_type res = {{ __VA_ARGS__ }};             \
84	util_dynarray_append(&expect, result_type, res); \
85} while (0)
86
87static bool
88int_dynarrays_equal(struct util_dynarray *a, struct util_dynarray *b)
89{
90   if (util_dynarray_num_elements(a, int) != util_dynarray_num_elements(b, int))
91      return false;
92
93   for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
94      if (*util_dynarray_element(a, int, i) !=
95          *util_dynarray_element(b, int, i)) {
96         return false;
97      }
98   }
99   return true;
100}
101
102static testing::AssertionResult
103int_dynarrays_equal_pred(const char *a_expr,
104                         const char *b_expr,
105                         struct util_dynarray *a,
106                         struct util_dynarray *b)
107{
108  if (int_dynarrays_equal(a, b)) return testing::AssertionSuccess();
109
110   testing::AssertionResult result = testing::AssertionFailure();
111
112   result << a_expr << " != " << b_expr;
113
114   result << ", (";
115   for (unsigned i = 0; i < util_dynarray_num_elements(a, int); i++) {
116      if (i != 0)
117         result << ", ";
118      result << *util_dynarray_element(a, int, i);
119   }
120
121   result << ") != (";
122   for (unsigned i = 0; i < util_dynarray_num_elements(b, int); i++) {
123      if (i != 0)
124         result << ", ";
125      result << *util_dynarray_element(b, int, i);
126   }
127
128   result << ")";
129
130   return result;
131}
132
133#define TEST_CHECK() EXPECT_PRED_FORMAT2(int_dynarrays_equal_pred, &expect, &actual)
134
135TEST_F(dag_test, simple)
136{
137   INIT_NODES(3);
138
139   /*     0
140    *    / \
141    *   1   2
142    */
143   node[0] >> node[1];
144   node[0] >> node[2];
145
146   /* Expected traversal order: [1, 2, 0] */
147   SET_EXPECTED(1, 2, 0);
148
149   dag_traverse_bottom_up(dag, output_cb, &actual);
150
151   TEST_CHECK();
152}
153
154TEST_F(dag_test, simple_many_children)
155{
156   INIT_NODES(6);
157
158   /*     _ 0 _
159    *    / /|\ \
160    *   / / | \ \
161    *  |  | | |  |
162    *  1  2 3 4  5
163    */
164   node[0] >> node[1];
165   node[0] >> node[2];
166   node[0] >> node[3];
167   node[0] >> node[4];
168   node[0] >> node[5];
169
170   /* Expected traversal order: [1, 2, 3, 4, 5, 0] */
171   SET_EXPECTED(1, 2, 3, 4, 5, 0);
172
173   dag_traverse_bottom_up(dag, output_cb, &actual);
174
175   TEST_CHECK();
176}
177
178TEST_F(dag_test, simple_many_parents)
179{
180   INIT_NODES(7);
181
182   /*     _ 0 _
183    *    / /|\ \
184    *   / / | \ \
185    *  |  | | |  |
186    *  1  2 3 4  5
187    *  |  | | |  |
188    *   \ \ | / /
189    *    \ \|/ /
190    *     ‾ 6 ‾
191    */
192   node[0] >> node[1] >> node[6];
193   node[0] >> node[2] >> node[6];
194   node[0] >> node[3] >> node[6];
195   node[0] >> node[4] >> node[6];
196   node[0] >> node[5] >> node[6];
197
198   /* Expected traversal order: [6, 1, 2, 3, 4, 5, 0] */
199   SET_EXPECTED(6, 1, 2, 3, 4, 5, 0);
200
201   dag_traverse_bottom_up(dag, output_cb, &actual);
202
203   TEST_CHECK();
204}
205
206TEST_F(dag_test, complex)
207{
208   INIT_NODES(6);
209
210   /*     0
211    *    / \
212    *   1   3
213    *  / \  |\
214    * 2  |  | \
215    *  \ / /   5
216    *   4 ‾
217    */
218   node[0] >> node[1] >> node[2] >> node[4];
219   node[1] >> node[4];
220   node[0] >> node[3];
221   node[3] >> node[4];
222   node[3] >> node[5];
223
224   /* Expected traversal order: [4, 2, 1, 5, 3, 0] */
225   SET_EXPECTED(4, 2, 1, 5, 3, 0);
226
227   dag_traverse_bottom_up(dag, output_cb, &actual);
228
229   TEST_CHECK();
230}
231