1 // RUN: %check_clang_tidy %s misc-no-recursion %t
2 
3 // We don't have the definition of this function,
4 // so we can't tell anything about it..
5 void external();
6 
7 // This function is obviously not recursive.
no_recursion()8 void no_recursion() {
9 }
10 
11 // Since we don't know what `external()` does,
12 // we don't know if this is recursive or not.
maybe_no_recursion()13 void maybe_no_recursion() {
14   external();
15 }
16 
17 // Function calls itself - obviously a recursion.
endless_recursion()18 void endless_recursion() {
19   endless_recursion();
20 }
21 
22 // CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is within a recursive call chain [misc-no-recursion]
23 // CHECK-NOTES: :[[@LINE-5]]:6: note: example recursive call chain, starting from function 'endless_recursion'
24 // CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
25 // CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
26 
27 bool external_oracle();
28 bool another_external_oracle();
29 
30 // Function calls itself if some external function said so - recursion.
maybe_endless_recursion()31 void maybe_endless_recursion() {
32   if (external_oracle())
33     maybe_endless_recursion();
34 }
35 
36 // CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is within a recursive call chain [misc-no-recursion]
37 // CHECK-NOTES: :[[@LINE-6]]:6: note: example recursive call chain, starting from function 'maybe_endless_recursion'
38 // CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
39 // CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
40 
41 // Obviously-constrained recursion.
recursive_countdown(unsigned x)42 void recursive_countdown(unsigned x) {
43   if (x == 0)
44     return;
45   recursive_countdown(x - 1);
46 }
47 
48 // CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is within a recursive call chain [misc-no-recursion]
49 // CHECK-NOTES: :[[@LINE-7]]:6: note: example recursive call chain, starting from function 'recursive_countdown'
50 // CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
51 // CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
52 
53 void indirect_recursion();
conditionally_executed()54 void conditionally_executed() {
55   if (external_oracle())
56     indirect_recursion();
57 }
indirect_recursion()58 void indirect_recursion() {
59   if (external_oracle())
60     conditionally_executed();
61 }
62 
63 // CHECK-NOTES: :[[@LINE-9]]:6: warning: function 'conditionally_executed' is within a recursive call chain [misc-no-recursion]
64 // CHECK-NOTES: :[[@LINE-6]]:6: note: example recursive call chain, starting from function 'indirect_recursion'
65 // CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
66 // CHECK-NOTES: :[[@LINE-10]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
67 // CHECK-NOTES: :[[@LINE-11]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
68 // CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is within a recursive call chain [misc-no-recursion]
69 
70 void taint();
maybe_selfrecursion_with_two_backedges()71 void maybe_selfrecursion_with_two_backedges() {
72   if (external_oracle())
73     maybe_selfrecursion_with_two_backedges();
74   taint();
75   if (another_external_oracle())
76     maybe_selfrecursion_with_two_backedges();
77 }
78 
79 // CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is within a recursive call chain [misc-no-recursion]
80 // CHECK-NOTES: :[[@LINE-9]]:6: note: example recursive call chain, starting from function 'maybe_selfrecursion_with_two_backedges'
81 // CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'maybe_selfrecursion_with_two_backedges' calls function 'maybe_selfrecursion_with_two_backedges' here:
82 // CHECK-NOTES: :[[@LINE-9]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
83 
84 void indirect_recursion_with_alternatives();
conditionally_executed_choice_0()85 void conditionally_executed_choice_0() {
86   if (external_oracle())
87     indirect_recursion_with_alternatives();
88 }
conditionally_executed_choice_1()89 void conditionally_executed_choice_1() {
90   if (external_oracle())
91     indirect_recursion_with_alternatives();
92 }
indirect_recursion_with_alternatives()93 void indirect_recursion_with_alternatives() {
94   if (external_oracle())
95     conditionally_executed_choice_0();
96   else
97     conditionally_executed_choice_1();
98 }
99 
100 // CHECK-NOTES: :[[@LINE-15]]:6: warning: function 'conditionally_executed_choice_0' is within a recursive call chain [misc-no-recursion]
101 // CHECK-NOTES: :[[@LINE-8]]:6: note: example recursive call chain, starting from function 'indirect_recursion_with_alternatives'
102 // CHECK-NOTES: :[[@LINE-7]]:5: note: Frame #1: function 'indirect_recursion_with_alternatives' calls function 'conditionally_executed_choice_0' here:
103 // CHECK-NOTES: :[[@LINE-16]]:5: note: Frame #2: function 'conditionally_executed_choice_0' calls function 'indirect_recursion_with_alternatives' here:
104 // CHECK-NOTES: :[[@LINE-17]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
105 // CHECK-NOTES: :[[@LINE-16]]:6: warning: function 'conditionally_executed_choice_1' is within a recursive call chain [misc-no-recursion]
106 // CHECK-NOTES: :[[@LINE-13]]:6: warning: function 'indirect_recursion_with_alternatives' is within a recursive call chain [misc-no-recursion]
107 
108 static void indirect_recursion_with_depth2();
conditionally_executed_depth1()109 static void conditionally_executed_depth1() {
110   if (external_oracle())
111     indirect_recursion_with_depth2();
112 }
conditionally_executed_depth0()113 static void conditionally_executed_depth0() {
114   if (external_oracle())
115     conditionally_executed_depth1();
116 }
indirect_recursion_with_depth2()117 void indirect_recursion_with_depth2() {
118   if (external_oracle())
119     conditionally_executed_depth0();
120 }
121 
122 // CHECK-NOTES: :[[@LINE-13]]:13: warning: function 'conditionally_executed_depth1' is within a recursive call chain [misc-no-recursion]
123 // CHECK-NOTES: :[[@LINE-10]]:13: note: example recursive call chain, starting from function 'conditionally_executed_depth0'
124 // CHECK-NOTES: :[[@LINE-9]]:5: note: Frame #1: function 'conditionally_executed_depth0' calls function 'conditionally_executed_depth1' here:
125 // CHECK-NOTES: :[[@LINE-14]]:5: note: Frame #2: function 'conditionally_executed_depth1' calls function 'indirect_recursion_with_depth2' here:
126 // CHECK-NOTES: :[[@LINE-7]]:5: note: Frame #3: function 'indirect_recursion_with_depth2' calls function 'conditionally_executed_depth0' here:
127 // CHECK-NOTES: :[[@LINE-8]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
128 // CHECK-NOTES: :[[@LINE-15]]:13: warning: function 'conditionally_executed_depth0' is within a recursive call chain [misc-no-recursion]
129 // CHECK-NOTES: :[[@LINE-12]]:6: warning: function 'indirect_recursion_with_depth2' is within a recursive call chain [misc-no-recursion]
130 
131 int boo();
foo(int x=boo ())132 void foo(int x = boo()) {}
bar()133 void bar() {
134   foo();
135   foo();
136 }
boo()137 int boo() {
138   bar();
139   return 0;
140 }
141 
142 // CHECK-NOTES: :[[@LINE-9]]:6: warning: function 'bar' is within a recursive call chain [misc-no-recursion]
143 // CHECK-NOTES: :[[@LINE-6]]:5: note: example recursive call chain, starting from function 'boo'
144 // CHECK-NOTES: :[[@LINE-6]]:3: note: Frame #1: function 'boo' calls function 'bar' here:
145 // CHECK-NOTES: :[[@LINE-13]]:18: note: Frame #2: function 'bar' calls function 'boo' here:
146 // CHECK-NOTES: :[[@LINE-14]]:18: note: ... which was the starting point of the recursive call chain; there may be other cycles
147 // CHECK-NOTES: :[[@LINE-10]]:5: warning: function 'boo' is within a recursive call chain [misc-no-recursion]
148 
recursion_through_function_ptr()149 int recursion_through_function_ptr() {
150   auto *ptr = &recursion_through_function_ptr;
151   if (external_oracle())
152     return ptr();
153   return 0;
154 }
155 
recursion_through_lambda()156 int recursion_through_lambda() {
157   auto zz = []() {
158     if (external_oracle())
159       return recursion_through_lambda();
160     return 0;
161   };
162   return zz();
163 }
164 
165 // CHECK-NOTES: :[[@LINE-9]]:5: warning: function 'recursion_through_lambda' is within a recursive call chain [misc-no-recursion]
166 // CHECK-NOTES: :[[@LINE-9]]:13: note: example recursive call chain, starting from function 'operator()'
167 // CHECK-NOTES: :[[@LINE-8]]:14: note: Frame #1: function 'operator()' calls function 'recursion_through_lambda' here:
168 // CHECK-NOTES: :[[@LINE-6]]:10: note: Frame #2: function 'recursion_through_lambda' calls function 'operator()' here:
169 // CHECK-NOTES: :[[@LINE-7]]:10: note: ... which was the starting point of the recursive call chain; there may be other cycles
170 // CHECK-NOTES: :[[@LINE-13]]:13: warning: function 'operator()' is within a recursive call chain [misc-no-recursion]
171 
172 struct recursion_through_destructor {
~recursion_through_destructorrecursion_through_destructor173   ~recursion_through_destructor() {
174     if (external_oracle()) {
175       recursion_through_destructor variable;
176       // variable goes out of scope, it's destructor runs, and we are back here.
177     }
178   }
179 };
180