1 // Licensed to the Apache Software Foundation (ASF) under one
2 // or more contributor license agreements. See the NOTICE file
3 // distributed with this work for additional information
4 // regarding copyright ownership. The ASF licenses this file
5 // to you under the Apache License, Version 2.0 (the
6 // "License"); you may not use this file except in compliance
7 // with the License. You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing,
12 // software distributed under the License is distributed on an
13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, either express or implied. See the License for the
15 // specific language governing permissions and limitations
16 // under the License.
17
18 #include "gandiva/expr_decomposer.h"
19
20 #include <gtest/gtest.h>
21
22 #include "gandiva/annotator.h"
23 #include "gandiva/dex.h"
24 #include "gandiva/function_registry.h"
25 #include "gandiva/gandiva_aliases.h"
26 #include "gandiva/node.h"
27 #include "gandiva/tree_expr_builder.h"
28
29 namespace gandiva {
30
31 using arrow::int32;
32
33 class TestExprDecomposer : public ::testing::Test {
34 protected:
35 FunctionRegistry registry_;
36 };
37
TEST_F(TestExprDecomposer,TestStackSimple)38 TEST_F(TestExprDecomposer, TestStackSimple) {
39 Annotator annotator;
40 ExprDecomposer decomposer(registry_, annotator);
41
42 // if (a) _
43 // else _
44 IfNode node_a(nullptr, nullptr, nullptr, int32());
45
46 decomposer.PushConditionEntry(node_a);
47 decomposer.PopConditionEntry(node_a);
48
49 int idx_a = decomposer.PushThenEntry(node_a, false);
50 EXPECT_EQ(idx_a, 0);
51 decomposer.PopThenEntry(node_a);
52
53 decomposer.PushElseEntry(node_a, idx_a);
54 bool is_terminal_a = decomposer.PopElseEntry(node_a);
55 EXPECT_EQ(is_terminal_a, true);
56 EXPECT_EQ(decomposer.if_entries_stack_.empty(), true);
57 }
58
TEST_F(TestExprDecomposer,TestNested)59 TEST_F(TestExprDecomposer, TestNested) {
60 Annotator annotator;
61 ExprDecomposer decomposer(registry_, annotator);
62
63 // if (a) _
64 // else _
65 // if (b) _
66 // else _
67 IfNode node_a(nullptr, nullptr, nullptr, int32());
68 IfNode node_b(nullptr, nullptr, nullptr, int32());
69
70 decomposer.PushConditionEntry(node_a);
71 decomposer.PopConditionEntry(node_a);
72
73 int idx_a = decomposer.PushThenEntry(node_a, false);
74 EXPECT_EQ(idx_a, 0);
75 decomposer.PopThenEntry(node_a);
76
77 decomposer.PushElseEntry(node_a, idx_a);
78
79 { // start b
80 decomposer.PushConditionEntry(node_b);
81 decomposer.PopConditionEntry(node_b);
82
83 int idx_b = decomposer.PushThenEntry(node_b, true);
84 EXPECT_EQ(idx_b, 0); // must reuse bitmap.
85 decomposer.PopThenEntry(node_b);
86
87 decomposer.PushElseEntry(node_b, idx_b);
88 bool is_terminal_b = decomposer.PopElseEntry(node_b);
89 EXPECT_EQ(is_terminal_b, true);
90 } // end b
91
92 bool is_terminal_a = decomposer.PopElseEntry(node_a);
93 EXPECT_EQ(is_terminal_a, false); // there was a nested if.
94
95 EXPECT_EQ(decomposer.if_entries_stack_.empty(), true);
96 }
97
TEST_F(TestExprDecomposer,TestInternalIf)98 TEST_F(TestExprDecomposer, TestInternalIf) {
99 Annotator annotator;
100 ExprDecomposer decomposer(registry_, annotator);
101
102 // if (a) _
103 // if (b) _
104 // else _
105 // else _
106 IfNode node_a(nullptr, nullptr, nullptr, int32());
107 IfNode node_b(nullptr, nullptr, nullptr, int32());
108
109 decomposer.PushConditionEntry(node_a);
110 decomposer.PopConditionEntry(node_a);
111
112 int idx_a = decomposer.PushThenEntry(node_a, false);
113 EXPECT_EQ(idx_a, 0);
114
115 { // start b
116 decomposer.PushConditionEntry(node_b);
117 decomposer.PopConditionEntry(node_b);
118
119 int idx_b = decomposer.PushThenEntry(node_b, false);
120 EXPECT_EQ(idx_b, 1); // must not reuse bitmap.
121 decomposer.PopThenEntry(node_b);
122
123 decomposer.PushElseEntry(node_b, idx_b);
124 bool is_terminal_b = decomposer.PopElseEntry(node_b);
125 EXPECT_EQ(is_terminal_b, true);
126 } // end b
127
128 decomposer.PopThenEntry(node_a);
129 decomposer.PushElseEntry(node_a, idx_a);
130
131 bool is_terminal_a = decomposer.PopElseEntry(node_a);
132 EXPECT_EQ(is_terminal_a, true); // there was no nested if.
133
134 EXPECT_EQ(decomposer.if_entries_stack_.empty(), true);
135 }
136
TEST_F(TestExprDecomposer,TestParallelIf)137 TEST_F(TestExprDecomposer, TestParallelIf) {
138 Annotator annotator;
139 ExprDecomposer decomposer(registry_, annotator);
140
141 // if (a) _
142 // else _
143 // if (b) _
144 // else _
145 IfNode node_a(nullptr, nullptr, nullptr, int32());
146 IfNode node_b(nullptr, nullptr, nullptr, int32());
147
148 decomposer.PushConditionEntry(node_a);
149 decomposer.PopConditionEntry(node_a);
150
151 int idx_a = decomposer.PushThenEntry(node_a, false);
152 EXPECT_EQ(idx_a, 0);
153
154 decomposer.PopThenEntry(node_a);
155 decomposer.PushElseEntry(node_a, idx_a);
156
157 bool is_terminal_a = decomposer.PopElseEntry(node_a);
158 EXPECT_EQ(is_terminal_a, true); // there was no nested if.
159
160 // start b
161 decomposer.PushConditionEntry(node_b);
162 decomposer.PopConditionEntry(node_b);
163
164 int idx_b = decomposer.PushThenEntry(node_b, false);
165 EXPECT_EQ(idx_b, 1); // must not reuse bitmap.
166 decomposer.PopThenEntry(node_b);
167
168 decomposer.PushElseEntry(node_b, idx_b);
169 bool is_terminal_b = decomposer.PopElseEntry(node_b);
170 EXPECT_EQ(is_terminal_b, true);
171
172 EXPECT_EQ(decomposer.if_entries_stack_.empty(), true);
173 }
174
TEST_F(TestExprDecomposer,TestIfInCondition)175 TEST_F(TestExprDecomposer, TestIfInCondition) {
176 Annotator annotator;
177 ExprDecomposer decomposer(registry_, annotator);
178
179 // if (if _ else _) : a
180 // -
181 // else
182 // if (if _ else _) : b
183 // -
184 // else
185 // -
186 IfNode node_a(nullptr, nullptr, nullptr, int32());
187 IfNode node_b(nullptr, nullptr, nullptr, int32());
188 IfNode cond_node_a(nullptr, nullptr, nullptr, int32());
189 IfNode cond_node_b(nullptr, nullptr, nullptr, int32());
190
191 // start a
192 decomposer.PushConditionEntry(node_a);
193 {
194 // start cond_node_a
195 decomposer.PushConditionEntry(cond_node_a);
196 decomposer.PopConditionEntry(cond_node_a);
197
198 int idx_cond_a = decomposer.PushThenEntry(cond_node_a, false);
199 EXPECT_EQ(idx_cond_a, 0);
200 decomposer.PopThenEntry(cond_node_a);
201
202 decomposer.PushElseEntry(cond_node_a, idx_cond_a);
203 bool is_terminal = decomposer.PopElseEntry(cond_node_a);
204 EXPECT_EQ(is_terminal, true); // there was no nested if.
205 }
206 decomposer.PopConditionEntry(node_a);
207
208 int idx_a = decomposer.PushThenEntry(node_a, false);
209 EXPECT_EQ(idx_a, 1); // no re-use
210 decomposer.PopThenEntry(node_a);
211
212 decomposer.PushElseEntry(node_a, idx_a);
213
214 { // start b
215 decomposer.PushConditionEntry(node_b);
216 {
217 // start cond_node_b
218 decomposer.PushConditionEntry(cond_node_b);
219 decomposer.PopConditionEntry(cond_node_b);
220
221 int idx_cond_b = decomposer.PushThenEntry(cond_node_b, false);
222 EXPECT_EQ(idx_cond_b, 2); // no re-use
223 decomposer.PopThenEntry(cond_node_b);
224
225 decomposer.PushElseEntry(cond_node_b, idx_cond_b);
226 bool is_terminal = decomposer.PopElseEntry(cond_node_b);
227 EXPECT_EQ(is_terminal, true); // there was no nested if.
228 }
229 decomposer.PopConditionEntry(node_b);
230
231 int idx_b = decomposer.PushThenEntry(node_b, true);
232 EXPECT_EQ(idx_b, 1); // must reuse bitmap.
233 decomposer.PopThenEntry(node_b);
234
235 decomposer.PushElseEntry(node_b, idx_b);
236 bool is_terminal = decomposer.PopElseEntry(node_b);
237 EXPECT_EQ(is_terminal, true);
238 } // end b
239
240 bool is_terminal_a = decomposer.PopElseEntry(node_a);
241 EXPECT_EQ(is_terminal_a, false); // there was a nested if.
242
243 EXPECT_EQ(decomposer.if_entries_stack_.empty(), true);
244 }
245
TEST_F(TestExprDecomposer,TestFunctionBetweenNestedIf)246 TEST_F(TestExprDecomposer, TestFunctionBetweenNestedIf) {
247 Annotator annotator;
248 ExprDecomposer decomposer(registry_, annotator);
249
250 // if (a) _
251 // else
252 // function(
253 // if (b) _
254 // else _
255 // )
256
257 IfNode node_a(nullptr, nullptr, nullptr, int32());
258 IfNode node_b(nullptr, nullptr, nullptr, int32());
259
260 // start outer if
261 decomposer.PushConditionEntry(node_a);
262 decomposer.PopConditionEntry(node_a);
263
264 int idx_a = decomposer.PushThenEntry(node_a, false);
265 EXPECT_EQ(idx_a, 0);
266 decomposer.PopThenEntry(node_a);
267
268 decomposer.PushElseEntry(node_a, idx_a);
269 { // start b
270 decomposer.PushConditionEntry(node_b);
271 decomposer.PopConditionEntry(node_b);
272
273 int idx_b = decomposer.PushThenEntry(node_b, false); // not else node of parent if
274 EXPECT_EQ(idx_b, 1); // can't reuse bitmap.
275 decomposer.PopThenEntry(node_b);
276
277 decomposer.PushElseEntry(node_b, idx_b);
278 bool is_terminal_b = decomposer.PopElseEntry(node_b);
279 EXPECT_EQ(is_terminal_b, true);
280 }
281 bool is_terminal_a = decomposer.PopElseEntry(node_a);
282 EXPECT_EQ(is_terminal_a, true); // a else is also terminal
283
284 EXPECT_TRUE(decomposer.if_entries_stack_.empty());
285 }
286
TEST_F(TestExprDecomposer,TestComplexIfCondition)287 TEST_F(TestExprDecomposer, TestComplexIfCondition) {
288 Annotator annotator;
289 ExprDecomposer decomposer(registry_, annotator);
290
291 // if (if _
292 // else
293 // if _
294 // else _
295 // )
296 // then
297 // if _
298 // else
299 // if _
300 // else _
301 //
302 // else
303 // if _
304 // else
305 // if _
306 // else _
307
308 IfNode node_a(nullptr, nullptr, nullptr, int32());
309
310 IfNode cond_node_a(nullptr, nullptr, nullptr, int32());
311 IfNode cond_node_a_inner_if(nullptr, nullptr, nullptr, int32());
312
313 IfNode then_node_a(nullptr, nullptr, nullptr, int32());
314 IfNode then_node_a_inner_if(nullptr, nullptr, nullptr, int32());
315
316 IfNode else_node_a(nullptr, nullptr, nullptr, int32());
317 IfNode else_node_a_inner_if(nullptr, nullptr, nullptr, int32());
318
319 // start outer if
320 decomposer.PushConditionEntry(node_a);
321 {
322 // start the nested if inside the condition of a
323 decomposer.PushConditionEntry(cond_node_a);
324 decomposer.PopConditionEntry(cond_node_a);
325
326 int idx_cond_a = decomposer.PushThenEntry(cond_node_a, false);
327 EXPECT_EQ(idx_cond_a, 0);
328 decomposer.PopThenEntry(cond_node_a);
329
330 decomposer.PushElseEntry(cond_node_a, idx_cond_a);
331 {
332 decomposer.PushConditionEntry(cond_node_a_inner_if);
333 decomposer.PopConditionEntry(cond_node_a_inner_if);
334
335 int idx_cond_a_inner_if = decomposer.PushThenEntry(cond_node_a_inner_if, true);
336 EXPECT_EQ(idx_cond_a_inner_if,
337 0); // expect bitmap to be resused since nested if else
338 decomposer.PopThenEntry(cond_node_a_inner_if);
339
340 decomposer.PushElseEntry(cond_node_a_inner_if, idx_cond_a_inner_if);
341 bool is_terminal = decomposer.PopElseEntry(cond_node_a_inner_if);
342 EXPECT_TRUE(is_terminal);
343 }
344 EXPECT_FALSE(decomposer.PopElseEntry(cond_node_a));
345 }
346 decomposer.PopConditionEntry(node_a);
347
348 int idx_a = decomposer.PushThenEntry(node_a, false);
349 EXPECT_EQ(idx_a, 1);
350
351 {
352 // start the nested if inside the then node of a
353 decomposer.PushConditionEntry(then_node_a);
354 decomposer.PopConditionEntry(then_node_a);
355
356 int idx_then_a = decomposer.PushThenEntry(then_node_a, false);
357 EXPECT_EQ(idx_then_a, 2);
358 decomposer.PopThenEntry(then_node_a);
359
360 decomposer.PushElseEntry(then_node_a, idx_then_a);
361 {
362 decomposer.PushConditionEntry(then_node_a_inner_if);
363 decomposer.PopConditionEntry(then_node_a_inner_if);
364
365 int idx_then_a_inner_if = decomposer.PushThenEntry(then_node_a_inner_if, true);
366 EXPECT_EQ(idx_then_a_inner_if,
367 2); // expect bitmap to be resused since nested if else
368 decomposer.PopThenEntry(then_node_a_inner_if);
369
370 decomposer.PushElseEntry(then_node_a_inner_if, idx_then_a_inner_if);
371 bool is_terminal = decomposer.PopElseEntry(then_node_a_inner_if);
372 EXPECT_TRUE(is_terminal);
373 }
374 EXPECT_FALSE(decomposer.PopElseEntry(then_node_a));
375 }
376 decomposer.PopThenEntry(node_a);
377
378 decomposer.PushElseEntry(node_a, idx_a);
379 {
380 // start the nested if inside the else node of a
381 decomposer.PushConditionEntry(else_node_a);
382 decomposer.PopConditionEntry(else_node_a);
383
384 int idx_else_a =
385 decomposer.PushThenEntry(else_node_a, true); // else node is another if-node
386 EXPECT_EQ(idx_else_a, 1); // reuse the outer if node bitmap since nested if-else
387 decomposer.PopThenEntry(else_node_a);
388
389 decomposer.PushElseEntry(else_node_a, idx_else_a);
390 {
391 decomposer.PushConditionEntry(else_node_a_inner_if);
392 decomposer.PopConditionEntry(else_node_a_inner_if);
393
394 int idx_else_a_inner_if = decomposer.PushThenEntry(else_node_a_inner_if, true);
395 EXPECT_EQ(idx_else_a_inner_if,
396 1); // expect bitmap to be resused since nested if else
397 decomposer.PopThenEntry(else_node_a_inner_if);
398
399 decomposer.PushElseEntry(else_node_a_inner_if, idx_else_a_inner_if);
400 bool is_terminal = decomposer.PopElseEntry(else_node_a_inner_if);
401 EXPECT_TRUE(is_terminal);
402 }
403 EXPECT_FALSE(decomposer.PopElseEntry(else_node_a));
404 }
405 EXPECT_FALSE(decomposer.PopElseEntry(node_a));
406 EXPECT_TRUE(decomposer.if_entries_stack_.empty());
407 }
408
409 } // namespace gandiva
410