Line data Source code
1 : /* valaflowanalyzer.vala
2 : *
3 : * Copyright (C) 2008-2010 Jürg Billeter
4 : *
5 : * This library is free software; you can redistribute it and/or
6 : * modify it under the terms of the GNU Lesser General Public
7 : * License as published by the Free Software Foundation; either
8 : * version 2.1 of the License, or (at your option) any later version.
9 :
10 : * This library is distributed in the hope that it will be useful,
11 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 : * Lesser General Public License for more details.
14 :
15 : * You should have received a copy of the GNU Lesser General Public
16 : * License along with this library; if not, write to the Free Software
17 : * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 : *
19 : * Author:
20 : * Jürg Billeter <j@bitron.ch>
21 : */
22 :
23 : using GLib;
24 :
25 : /**
26 : * Code visitor building the control flow graph.
27 : */
28 4614 : public class Vala.FlowAnalyzer : CodeVisitor {
29 980410 : private class JumpTarget {
30 22749 : public bool is_break_target { get; set; }
31 10034 : public bool is_continue_target { get; set; }
32 313300 : public bool is_return_target { get; set; }
33 96424 : public bool is_exit_target { get; set; }
34 4326 : public bool is_error_target { get; set; }
35 219575 : public ErrorDomain? error_domain { get; set; }
36 211260 : public ErrorCode? error_code { get; set; }
37 209243 : public Class? error_class { get; set; }
38 111861 : public bool is_finally_clause { get; set; }
39 751156 : public BasicBlock basic_block { get; set; }
40 207269 : public BasicBlock? last_block { get; set; }
41 215445 : public CatchClause? catch_clause { get; set; }
42 :
43 29328 : public JumpTarget.break_target (BasicBlock basic_block) {
44 9776 : this.basic_block = basic_block;
45 9776 : is_break_target = true;
46 : }
47 :
48 29016 : public JumpTarget.continue_target (BasicBlock basic_block) {
49 9672 : this.basic_block = basic_block;
50 9672 : is_continue_target = true;
51 : }
52 :
53 278358 : public JumpTarget.return_target (BasicBlock basic_block) {
54 92786 : this.basic_block = basic_block;
55 92786 : is_return_target = true;
56 : }
57 :
58 278358 : public JumpTarget.exit_target (BasicBlock basic_block) {
59 92786 : this.basic_block = basic_block;
60 92786 : is_exit_target = true;
61 : }
62 :
63 6207 : public JumpTarget.error_target (BasicBlock basic_block, CatchClause catch_clause, ErrorDomain? error_domain, ErrorCode? error_code, Class? error_class) {
64 2069 : this.basic_block = basic_block;
65 2069 : this.catch_clause = catch_clause;
66 2069 : this.error_domain = error_domain;
67 2069 : this.error_code = error_code;
68 2069 : this.error_class = error_class;
69 2069 : is_error_target = true;
70 : }
71 :
72 132 : public JumpTarget.any_target (BasicBlock basic_block) {
73 44 : this.basic_block = basic_block;
74 44 : is_break_target = true;
75 44 : is_continue_target = true;
76 44 : is_return_target = true;
77 44 : is_exit_target = true;
78 44 : is_error_target = true;
79 : }
80 :
81 123 : public JumpTarget.finally_clause (BasicBlock basic_block, BasicBlock last_block) {
82 41 : this.basic_block = basic_block;
83 41 : this.last_block = last_block;
84 41 : is_finally_clause = true;
85 : }
86 : }
87 :
88 1538 : private CodeContext context;
89 1538 : private BasicBlock current_block;
90 : private bool unreachable_reported;
91 3076 : private List<JumpTarget> jump_stack = new ArrayList<JumpTarget> ();
92 1538 : private Set<BasicBlock> all_basic_blocks;
93 :
94 : // check_variables
95 1538 : Map<Symbol, List<Variable>> var_map;
96 1538 : Set<Variable> used_vars;
97 1538 : Map<Variable, PhiFunction> phi_functions;
98 :
99 3076 : public FlowAnalyzer () {
100 : }
101 :
102 : /**
103 : * Build control flow graph in the specified context.
104 : *
105 : * @param context a code context
106 : */
107 1942 : public void analyze (CodeContext context) {
108 971 : this.context = context;
109 971 : all_basic_blocks = new HashSet<BasicBlock> ();
110 :
111 11469 : var source_files = context.get_source_files ();
112 10117 : foreach (SourceFile file in source_files) {
113 4573 : file.accept (this);
114 : }
115 :
116 971 : all_basic_blocks = null;
117 971 : this.context = null;
118 : }
119 :
120 4573 : public override void visit_source_file (SourceFile source_file) {
121 4573 : source_file.accept_children (this);
122 : }
123 :
124 239165 : public override void visit_class (Class cl) {
125 239165 : cl.accept_children (this);
126 : }
127 :
128 91821 : public override void visit_struct (Struct st) {
129 91821 : st.accept_children (this);
130 : }
131 :
132 36883 : public override void visit_interface (Interface iface) {
133 36883 : iface.accept_children (this);
134 : }
135 :
136 133983 : public override void visit_enum (Enum en) {
137 133983 : en.accept_children (this);
138 : }
139 :
140 19456 : public override void visit_error_domain (ErrorDomain ed) {
141 19456 : ed.accept_children (this);
142 : }
143 :
144 379873 : public override void visit_field (Field f) {
145 379873 : if (f.is_internal_symbol () && !f.used && !f.external_package) {
146 85 : if (!f.is_private_symbol () && (context.internal_header_filename != null || context.use_fast_vapi)) {
147 : // do not warn if internal member may be used outside this compilation unit
148 : } else {
149 85 : Report.warning (f.source_reference, "Field `%s' never used", f.get_full_name ());
150 : }
151 : }
152 : }
153 :
154 8404 : public override void visit_lambda_expression (LambdaExpression le) {
155 3102435 : var old_current_block = current_block;
156 4202 : var old_unreachable_reported = unreachable_reported;
157 4202 : var old_jump_stack = jump_stack;
158 4202 : mark_unreachable ();
159 4202 : jump_stack = new ArrayList<JumpTarget> ();
160 :
161 4202 : le.accept_children (this);
162 :
163 8404 : current_block = old_current_block;
164 4202 : unreachable_reported = old_unreachable_reported;
165 8404 : jump_stack = old_jump_stack;
166 : }
167 :
168 4172621 : public override void visit_method (Method m) {
169 4172621 : if (m.is_internal_symbol () && !m.used && !m.entry_point && !m.external_package
170 421 : && !m.overrides && (m.base_interface_method == null || m.base_interface_method == m)
171 256 : && !(m is CreationMethod)) {
172 121 : if (!m.is_private_symbol () && (context.internal_header_filename != null || context.use_fast_vapi)) {
173 : // do not warn if internal member may be used outside this compilation unit
174 161 : } else if (m.parent_symbol != null && m.parent_symbol.has_attribute ("DBus")
175 40 : && m.get_attribute_bool ("DBus", "visible", true)) {
176 : // do not warn if internal member is a visible DBus method
177 : } else {
178 81 : Report.warning (m.source_reference, "Method `%s' never used", m.get_full_name ());
179 : }
180 : }
181 :
182 4172621 : visit_subroutine (m);
183 : }
184 :
185 88501 : public override void visit_signal (Signal sig) {
186 88501 : if (sig.default_handler != null) {
187 76762 : visit_subroutine (sig.default_handler);
188 : }
189 : }
190 :
191 4740414 : void visit_subroutine (Subroutine m) {
192 4740414 : if (m.body == null) {
193 : return;
194 : }
195 :
196 92786 : m.entry_block = new BasicBlock.entry ();
197 92786 : all_basic_blocks.add (m.entry_block);
198 92786 : m.return_block = new BasicBlock ();
199 92786 : all_basic_blocks.add (m.return_block);
200 92786 : m.exit_block = new BasicBlock.exit ();
201 92786 : all_basic_blocks.add (m.exit_block);
202 :
203 92786 : m.return_block.connect (m.exit_block);
204 :
205 92786 : if (m is Method) {
206 : // ensure out parameters are defined at end of method
207 343318 : foreach (var param in ((Method) m).get_parameters ()) {
208 147098 : if (param.direction == ParameterDirection.OUT) {
209 19359 : var param_ma = new MemberAccess.simple (param.name, param.source_reference);
210 19359 : param_ma.symbol_reference = param;
211 19359 : m.return_block.add_node (param_ma);
212 : }
213 : }
214 : }
215 :
216 92786 : current_block = new BasicBlock ();
217 92786 : all_basic_blocks.add (current_block);
218 :
219 92786 : m.entry_block.connect (current_block);
220 92786 : current_block.add_node (m);
221 :
222 92786 : jump_stack.add (new JumpTarget.return_target (m.return_block));
223 92786 : jump_stack.add (new JumpTarget.exit_target (m.exit_block));
224 :
225 92786 : m.accept_children (this);
226 :
227 92786 : jump_stack.remove_at (jump_stack.size - 1);
228 :
229 92786 : if (current_block != null) {
230 : // end of method body reachable
231 :
232 12220 : if (m.has_result) {
233 1 : Report.error (m.source_reference, "missing return statement at end of subroutine body");
234 1 : m.error = true;
235 : }
236 :
237 12220 : current_block.connect (m.return_block);
238 : } else {
239 80566 : m.body.unreachable_exit = true;
240 : }
241 :
242 92786 : analyze_body (m.entry_block);
243 : }
244 :
245 185572 : void analyze_body (BasicBlock entry_block) {
246 92786 : var block_list = get_depth_first_list (entry_block);
247 :
248 92786 : build_dominator_tree (block_list, entry_block);
249 92786 : build_dominator_frontier (block_list, entry_block);
250 92786 : insert_phi_functions (block_list, entry_block);
251 92786 : check_variables (entry_block);
252 : }
253 :
254 : // generates reverse postorder list
255 92786 : List<BasicBlock> get_depth_first_list (BasicBlock entry_block) {
256 92786 : var list = new ArrayList<BasicBlock> ();
257 92786 : depth_first_traverse (entry_block, list);
258 92786 : return list;
259 : }
260 :
261 758342 : void depth_first_traverse (BasicBlock current, List<BasicBlock> list) {
262 758342 : if (current.postorder_visited) {
263 : return;
264 : }
265 659518 : current.postorder_visited = true;
266 1325074 : foreach (weak BasicBlock succ in current.get_successors ()) {
267 665556 : depth_first_traverse (succ, list);
268 : }
269 659518 : current.postorder_number = list.size;
270 659518 : list.insert (0, current);
271 : }
272 :
273 185572 : void build_dominator_tree (List<BasicBlock> block_list, BasicBlock entry_block) {
274 : // immediate dominators
275 92786 : var idoms = new BasicBlock[block_list.size];
276 92786 : idoms[entry_block.postorder_number] = entry_block;
277 :
278 92786 : bool changed = true;
279 286668 : while (changed) {
280 193882 : changed = false;
281 2963692 : foreach (BasicBlock block in block_list) {
282 1481846 : if (block == entry_block) {
283 193882 : continue;
284 : }
285 :
286 : // new immediate dominator
287 1287964 : BasicBlock new_idom = null;
288 1287964 : bool first = true;
289 2811535 : foreach (weak BasicBlock pred in block.get_predecessors ()) {
290 1523571 : if (idoms[pred.postorder_number] != null) {
291 1513774 : if (first) {
292 2575928 : new_idom = pred;
293 : first = false;
294 : } else {
295 225810 : new_idom = intersect (idoms, pred, new_idom);
296 : }
297 : }
298 : }
299 1287964 : if (idoms[block.postorder_number] != new_idom) {
300 1170966 : idoms[block.postorder_number] = new_idom;
301 585483 : changed = true;
302 : }
303 : }
304 : }
305 :
306 : // build tree
307 1319036 : foreach (BasicBlock block in block_list) {
308 659518 : if (block == entry_block) {
309 92786 : continue;
310 : }
311 :
312 566732 : idoms[block.postorder_number].add_child (block);
313 : }
314 : }
315 :
316 225810 : BasicBlock intersect (BasicBlock[] idoms, BasicBlock b1, BasicBlock b2) {
317 645724 : while (b1 != b2) {
318 645468 : while (b1.postorder_number < b2.postorder_number) {
319 225554 : b1 = idoms[b2.postorder_number];
320 : }
321 842152 : while (b2.postorder_number < b1.postorder_number) {
322 422238 : b2 = idoms[b2.postorder_number];
323 : }
324 : }
325 225810 : return b1;
326 : }
327 :
328 92786 : void build_dominator_frontier (List<BasicBlock> block_list, BasicBlock entry_block) {
329 1411822 : for (int i = block_list.size - 1; i >= 0; i--) {
330 659518 : var block = block_list[i];
331 :
332 1325074 : foreach (weak BasicBlock succ in block.get_successors ()) {
333 : // if idom(succ) != block
334 665556 : if (succ.parent != block) {
335 194123 : block.add_dominator_frontier (succ);
336 : }
337 : }
338 :
339 1226250 : foreach (weak BasicBlock child in block.get_children ()) {
340 1453992 : foreach (weak BasicBlock child_frontier in child.get_dominator_frontier ()) {
341 : // if idom(child_frontier) != block
342 320528 : if (child_frontier.parent != block) {
343 213309 : block.add_dominator_frontier (child_frontier);
344 : }
345 : }
346 : }
347 : }
348 : }
349 :
350 92786 : Map<Variable, Set<BasicBlock>> get_assignment_map (List<BasicBlock> block_list, BasicBlock entry_block) {
351 92786 : var map = new HashMap<Variable, Set<BasicBlock>> ();
352 1411822 : foreach (BasicBlock block in block_list) {
353 659518 : var defined_variables = new ArrayList<Variable> ();
354 1966390 : foreach (CodeNode node in block.get_nodes ()) {
355 653436 : node.get_defined_variables (defined_variables);
356 : }
357 :
358 1059874 : foreach (Variable variable in defined_variables) {
359 200178 : var block_set = map.get (variable);
360 200178 : if (block_set == null) {
361 126291 : block_set = new HashSet<BasicBlock> ();
362 126291 : map.set (variable, block_set);
363 : }
364 200178 : block_set.add (block);
365 : }
366 : }
367 : return map;
368 : }
369 :
370 185572 : void insert_phi_functions (List<BasicBlock> block_list, BasicBlock entry_block) {
371 92786 : var assign = get_assignment_map (block_list, entry_block);
372 :
373 92786 : int counter = 0;
374 92786 : var work_list = new ArrayList<BasicBlock> ();
375 :
376 92786 : var added = new HashMap<BasicBlock, int> ();
377 92786 : var phi = new HashMap<BasicBlock, int> ();
378 1411822 : foreach (BasicBlock block in block_list) {
379 659518 : added.set (block, 0);
380 659518 : phi.set (block, 0);
381 : }
382 :
383 438154 : foreach (Variable variable in assign.get_keys ()) {
384 126291 : counter++;
385 450251 : foreach (BasicBlock block in assign.get (variable)) {
386 197669 : work_list.add (block);
387 197669 : added.set (block, counter);
388 : }
389 1043919 : while (work_list.size > 0) {
390 458814 : BasicBlock block = work_list.remove_at (0);
391 1647466 : foreach (BasicBlock frontier in block.get_dominator_frontier ()) {
392 364919 : int blockPhi = phi.get (frontier);
393 364919 : if (blockPhi < counter) {
394 267509 : frontier.add_phi_function (new PhiFunction (variable, frontier.get_predecessors ().size));
395 267509 : phi.set (frontier, counter);
396 267509 : int block_added = added.get (frontier);
397 267509 : if (block_added < counter) {
398 261145 : added.set (frontier, counter);
399 261145 : work_list.add (frontier);
400 : }
401 : }
402 : }
403 : }
404 : }
405 : }
406 :
407 185572 : void check_variables (BasicBlock entry_block) {
408 92786 : var_map = new HashMap<Symbol, List<Variable>>();
409 92786 : used_vars = new HashSet<Variable> ();
410 92786 : phi_functions = new HashMap<Variable, PhiFunction> ();
411 :
412 92786 : check_block_variables (entry_block);
413 :
414 : // check for variables used before initialization
415 92786 : var used_vars_queue = new ArrayList<Variable> ();
416 494304 : foreach (Variable variable in used_vars) {
417 154366 : used_vars_queue.add (variable);
418 : }
419 711484 : while (used_vars_queue.size > 0) {
420 309349 : Variable used_var = used_vars_queue.remove_at (0);
421 :
422 309349 : PhiFunction phi = phi_functions.get (used_var);
423 309349 : if (phi != null) {
424 602021 : foreach (Variable variable in phi.operands) {
425 241266 : if (variable == null) {
426 2 : if (used_var is LocalVariable) {
427 2 : Report.error (used_var.source_reference, "Use of possibly unassigned local variable `%s'", used_var.name);
428 : } else {
429 : // parameter
430 0 : Report.warning (used_var.source_reference, "Use of possibly unassigned parameter `%s'", used_var.name);
431 : }
432 2 : continue;
433 : }
434 241264 : if (!(variable in used_vars)) {
435 154983 : variable.source_reference = used_var.source_reference;
436 154983 : used_vars.add (variable);
437 154983 : used_vars_queue.add (variable);
438 : }
439 : }
440 : }
441 : }
442 :
443 92786 : phi_functions = null;
444 92786 : used_vars = null;
445 92786 : var_map = null;
446 : }
447 :
448 659518 : void check_block_variables (BasicBlock block) {
449 1854054 : foreach (PhiFunction phi in block.get_phi_functions ()) {
450 267509 : Variable versioned_var = process_assignment (var_map, phi.original_variable);
451 :
452 267509 : phi_functions.set (versioned_var, phi);
453 : }
454 :
455 1966390 : foreach (CodeNode node in block.get_nodes ()) {
456 653436 : var used_variables = new ArrayList<Variable> ();
457 653436 : node.get_used_variables (used_variables);
458 :
459 1129752 : foreach (Variable var_symbol in used_variables) {
460 238162 : var variable_stack = var_map.get (var_symbol);
461 238162 : if (variable_stack == null || variable_stack.size == 0) {
462 8 : if (var_symbol is LocalVariable) {
463 4 : Report.error (node.source_reference, "Use of possibly unassigned local variable `%s'", var_symbol.name);
464 : } else {
465 : // parameter
466 4 : Report.warning (node.source_reference, "Use of possibly unassigned parameter `%s'", var_symbol.name);
467 : }
468 8 : continue;
469 : }
470 238154 : var versioned_variable = variable_stack.get (variable_stack.size - 1);
471 238154 : if (!(versioned_variable in used_vars)) {
472 154366 : versioned_variable.source_reference = node.source_reference;
473 : }
474 238154 : used_vars.add (versioned_variable);
475 : }
476 :
477 653436 : var defined_variables = new ArrayList<Variable> ();
478 653436 : node.get_defined_variables (defined_variables);
479 :
480 1053792 : foreach (Variable variable in defined_variables) {
481 200178 : process_assignment (var_map, variable);
482 : }
483 : }
484 :
485 1325074 : foreach (weak BasicBlock succ in block.get_successors ()) {
486 665556 : int j = 0;
487 773665 : foreach (weak BasicBlock pred in succ.get_predecessors ()) {
488 773665 : if (pred == block) {
489 : break;
490 : }
491 108109 : j++;
492 : }
493 :
494 2466614 : foreach (PhiFunction phi in succ.get_phi_functions ()) {
495 567751 : var variable_stack = var_map.get (phi.original_variable);
496 567751 : if (variable_stack != null && variable_stack.size > 0) {
497 508197 : phi.operands.set (j, variable_stack.get (variable_stack.size - 1));
498 : }
499 : }
500 : }
501 :
502 1226250 : foreach (weak BasicBlock child in block.get_children ()) {
503 566732 : check_block_variables (child);
504 : }
505 :
506 1854054 : foreach (PhiFunction phi in block.get_phi_functions ()) {
507 267509 : var variable_stack = var_map.get (phi.original_variable);
508 267509 : variable_stack.remove_at (variable_stack.size - 1);
509 : }
510 1966390 : foreach (CodeNode node in block.get_nodes ()) {
511 653436 : var defined_variables = new ArrayList<Variable> ();
512 653436 : node.get_defined_variables (defined_variables);
513 :
514 1053792 : foreach (Variable variable in defined_variables) {
515 200178 : var variable_stack = var_map.get (variable);
516 200178 : variable_stack.remove_at (variable_stack.size - 1);
517 : }
518 : }
519 : }
520 :
521 467687 : Variable process_assignment (Map<Symbol, List<Variable>> var_map, Variable var_symbol) {
522 467687 : var variable_stack = var_map.get (var_symbol);
523 467687 : if (variable_stack == null) {
524 126291 : variable_stack = new ArrayList<Variable> ();
525 126291 : var_map.set (var_symbol, variable_stack);
526 126291 : var_symbol.single_assignment = true;
527 : } else {
528 341396 : var_symbol.single_assignment = false;
529 : }
530 : Variable versioned_var;
531 467687 : if (var_symbol is LocalVariable) {
532 407749 : versioned_var = new LocalVariable (var_symbol.variable_type.copy (), var_symbol.name, null, var_symbol.source_reference);
533 : } else {
534 : // parameter
535 59938 : versioned_var = new Parameter (var_symbol.name, var_symbol.variable_type.copy (), var_symbol.source_reference);
536 : }
537 467687 : variable_stack.add (versioned_var);
538 467687 : return versioned_var;
539 : }
540 :
541 360217 : public override void visit_creation_method (CreationMethod m) {
542 360217 : visit_method (m);
543 : }
544 :
545 290512 : public override void visit_property (Property prop) {
546 290512 : prop.accept_children (this);
547 : }
548 :
549 491031 : public override void visit_property_accessor (PropertyAccessor acc) {
550 491031 : visit_subroutine (acc);
551 : }
552 :
553 273412 : public override void visit_block (Block b) {
554 273412 : b.accept_children (this);
555 : }
556 :
557 104695 : public override void visit_declaration_statement (DeclarationStatement stmt) {
558 104695 : stmt.accept_children (this);
559 :
560 104695 : if (unreachable (stmt)) {
561 1 : stmt.declaration.unreachable = true;
562 1 : return;
563 : }
564 :
565 104694 : if (!stmt.declaration.used) {
566 197 : Report.warning (stmt.declaration.source_reference, "Local variable `%s' declared but never used", stmt.declaration.name);
567 : }
568 :
569 104694 : current_block.add_node (stmt);
570 :
571 104694 : unowned LocalVariable? local = stmt.declaration as LocalVariable;
572 104677 : if (local != null && local.initializer != null) {
573 58236 : handle_errors (local.initializer);
574 : }
575 : }
576 :
577 104692 : public override void visit_local_variable (LocalVariable local) {
578 104692 : if (local.initializer != null) {
579 58236 : local.initializer.accept (this);
580 : }
581 : }
582 :
583 215320 : public override void visit_expression_statement (ExpressionStatement stmt) {
584 215320 : stmt.accept_children (this);
585 :
586 215320 : if (unreachable (stmt)) {
587 : return;
588 : }
589 :
590 215294 : current_block.add_node (stmt);
591 :
592 215294 : handle_errors (stmt);
593 :
594 215294 : if (stmt.expression is MethodCall) {
595 66239 : unowned MethodCall expr = (MethodCall) stmt.expression;
596 66239 : unowned MemberAccess? ma = expr.call as MemberAccess;
597 65664 : if (ma != null && ma.symbol_reference != null && ma.symbol_reference.has_attribute ("NoReturn")) {
598 213 : mark_unreachable ();
599 213 : return;
600 : }
601 : }
602 : }
603 :
604 36 : public override void visit_with_statement (WithStatement stmt) {
605 36 : if (unreachable (stmt)) {
606 : return;
607 : }
608 :
609 35 : current_block.add_node (stmt.expression);
610 :
611 35 : handle_errors (stmt.expression);
612 :
613 35 : stmt.body.accept_children (this);
614 : }
615 :
616 191477 : public override void visit_if_statement (IfStatement stmt) {
617 95739 : if (unreachable (stmt)) {
618 : return;
619 : }
620 :
621 : // condition
622 95738 : current_block.add_node (stmt.condition);
623 :
624 95738 : handle_errors (stmt.condition);
625 :
626 : // true block
627 95738 : var last_block = current_block;
628 95738 : if (stmt.condition.is_always_false ()) {
629 7 : mark_unreachable ();
630 : } else {
631 95731 : current_block = new BasicBlock ();
632 95731 : all_basic_blocks.add (current_block);
633 95731 : last_block.connect (current_block);
634 : }
635 95738 : stmt.true_statement.accept (this);
636 :
637 : // false block
638 95738 : var last_true_block = current_block;
639 95738 : if (stmt.condition.is_always_true ()) {
640 9 : mark_unreachable ();
641 : } else {
642 95729 : current_block = new BasicBlock ();
643 95729 : all_basic_blocks.add (current_block);
644 95729 : last_block.connect (current_block);
645 : }
646 95738 : if (stmt.false_statement != null) {
647 65763 : stmt.false_statement.accept (this);
648 : }
649 :
650 : // after if/else
651 95738 : var last_false_block = current_block;
652 : // reachable?
653 95738 : if (last_true_block != null || last_false_block != null) {
654 72344 : current_block = new BasicBlock ();
655 72344 : all_basic_blocks.add (current_block);
656 72344 : if (last_true_block != null) {
657 57640 : last_true_block.connect (current_block);
658 : }
659 72344 : if (last_false_block != null) {
660 70332 : last_false_block.connect (current_block);
661 : }
662 : }
663 : }
664 :
665 208 : public override void visit_switch_statement (SwitchStatement stmt) {
666 104 : if (unreachable (stmt)) {
667 : return;
668 : }
669 :
670 104 : var after_switch_block = new BasicBlock ();
671 104 : all_basic_blocks.add (after_switch_block);
672 104 : jump_stack.add (new JumpTarget.break_target (after_switch_block));
673 :
674 : // condition
675 104 : current_block.add_node (stmt.expression);
676 104 : var condition_block = current_block;
677 :
678 104 : handle_errors (stmt.expression);
679 :
680 104 : bool has_default_label = false;
681 208 : bool is_enum_typed = stmt.expression.value_type is EnumValueType;
682 :
683 104 : unowned Enum? en = null;
684 39 : HashSet<unowned EnumValue>? enum_values = null;
685 65 : if (is_enum_typed) {
686 39 : en = (Enum) ((EnumValueType) stmt.expression.value_type).type_symbol;
687 39 : enum_values = new HashSet<unowned EnumValue> (direct_hash, direct_equal);
688 : }
689 :
690 1232 : foreach (SwitchSection section in stmt.get_sections ()) {
691 564 : current_block = new BasicBlock ();
692 564 : all_basic_blocks.add (current_block);
693 564 : condition_block.connect (current_block);
694 4960 : foreach (Statement section_stmt in section.get_statements ()) {
695 2198 : section_stmt.accept (this);
696 : }
697 :
698 564 : if (is_enum_typed) {
699 842 : foreach (SwitchLabel label in section.get_labels ()) {
700 287 : if (label.expression != null) {
701 257 : unowned EnumValue? val = label.expression.symbol_reference as EnumValue;
702 287 : if (val != null) {
703 257 : enum_values.add (val);
704 : }
705 : }
706 : }
707 : }
708 :
709 564 : if (section.has_default_label ()) {
710 71 : has_default_label = true;
711 : }
712 :
713 564 : if (current_block != null) {
714 : // end of switch section reachable
715 : // we don't allow fall-through
716 :
717 1 : Report.error (section.source_reference, "missing break statement at end of switch section");
718 1 : section.error = true;
719 :
720 1 : current_block.connect (after_switch_block);
721 : }
722 : }
723 :
724 113 : if (!has_default_label && is_enum_typed) {
725 : // Check if enum-based switching as fully covered, and if so,
726 : // handle it like there was a default-label given
727 :
728 9 : HashSet<EnumValue> remaining_values = new HashSet<EnumValue> ();
729 9 : remaining_values.add_all (en.get_values ());
730 85 : foreach (unowned EnumValue val in enum_values) {
731 76 : remaining_values.remove (val);
732 : }
733 11 : if (remaining_values.size > 0) {
734 2 : string[] missing_vals = {};
735 8 : foreach (var val in remaining_values) {
736 6 : missing_vals += val.name;
737 : }
738 2 : Report.warning (stmt.source_reference, "Switch does not handle `%s' of enum `%s'", string.joinv ("', `", missing_vals), en.get_full_name ());
739 : }
740 : }
741 :
742 104 : if (!has_default_label) {
743 33 : condition_block.connect (after_switch_block);
744 : }
745 :
746 : // after switch
747 : // reachable?
748 104 : if (after_switch_block.get_predecessors ().size > 0) {
749 184 : current_block = after_switch_block;
750 : } else {
751 12 : mark_unreachable ();
752 : }
753 :
754 104 : jump_stack.remove_at (jump_stack.size - 1);
755 : }
756 :
757 19010 : public override void visit_loop_statement (LoopStatement stmt) {
758 9505 : if (unreachable (stmt)) {
759 : return;
760 : }
761 :
762 9505 : var loop_block = new BasicBlock ();
763 9505 : all_basic_blocks.add (loop_block);
764 9505 : jump_stack.add (new JumpTarget.continue_target (loop_block));
765 9505 : var after_loop_block = new BasicBlock ();
766 9505 : all_basic_blocks.add (after_loop_block);
767 9505 : jump_stack.add (new JumpTarget.break_target (after_loop_block));
768 :
769 : // loop block
770 9505 : var last_block = current_block;
771 9505 : last_block.connect (loop_block);
772 19010 : current_block = loop_block;
773 :
774 9505 : stmt.body.accept (this);
775 : // end of loop block reachable?
776 9505 : if (current_block != null) {
777 9477 : current_block.connect (loop_block);
778 : }
779 :
780 : // after loop
781 : // reachable?
782 9505 : if (after_loop_block.get_predecessors ().size == 0) {
783 : // after loop block not reachable
784 4 : mark_unreachable ();
785 : } else {
786 : // after loop block reachable
787 19002 : current_block = after_loop_block;
788 : }
789 :
790 9505 : jump_stack.remove_at (jump_stack.size - 1);
791 9505 : jump_stack.remove_at (jump_stack.size - 1);
792 : }
793 :
794 334 : public override void visit_foreach_statement (ForeachStatement stmt) {
795 167 : if (unreachable (stmt)) {
796 : return;
797 : }
798 :
799 : // collection
800 167 : current_block.add_node (stmt.collection);
801 167 : handle_errors (stmt.collection);
802 :
803 167 : var loop_block = new BasicBlock ();
804 167 : all_basic_blocks.add (loop_block);
805 167 : jump_stack.add (new JumpTarget.continue_target (loop_block));
806 167 : var after_loop_block = new BasicBlock ();
807 167 : all_basic_blocks.add (after_loop_block);
808 167 : jump_stack.add (new JumpTarget.break_target (after_loop_block));
809 :
810 : // loop block
811 167 : var last_block = current_block;
812 167 : last_block.connect (loop_block);
813 334 : current_block = loop_block;
814 167 : current_block.add_node (stmt);
815 167 : stmt.body.accept (this);
816 167 : if (current_block != null) {
817 165 : current_block.connect (loop_block);
818 : }
819 :
820 : // after loop
821 167 : last_block.connect (after_loop_block);
822 167 : if (current_block != null) {
823 165 : current_block.connect (after_loop_block);
824 : }
825 334 : current_block = after_loop_block;
826 :
827 167 : jump_stack.remove_at (jump_stack.size - 1);
828 167 : jump_stack.remove_at (jump_stack.size - 1);
829 : }
830 :
831 12844 : public override void visit_break_statement (BreakStatement stmt) {
832 12844 : if (unreachable (stmt)) {
833 : return;
834 : }
835 :
836 12843 : current_block.add_node (stmt);
837 :
838 13017 : for (int i = jump_stack.size - 1; i >= 0; i--) {
839 12929 : var jump_target = jump_stack[i];
840 12929 : if (jump_target.is_break_target) {
841 12842 : current_block.connect (jump_target.basic_block);
842 12842 : mark_unreachable ();
843 12842 : return;
844 87 : } else if (jump_target.is_finally_clause) {
845 0 : current_block.connect (jump_target.basic_block);
846 0 : current_block = jump_target.last_block;
847 : }
848 : }
849 :
850 1 : Report.error (stmt.source_reference, "no enclosing loop or switch statement found");
851 1 : stmt.error = true;
852 : }
853 :
854 116 : public override void visit_continue_statement (ContinueStatement stmt) {
855 116 : if (unreachable (stmt)) {
856 : return;
857 : }
858 :
859 116 : current_block.add_node (stmt);
860 :
861 522 : for (int i = jump_stack.size - 1; i >= 0; i--) {
862 318 : var jump_target = jump_stack[i];
863 318 : if (jump_target.is_continue_target) {
864 115 : current_block.connect (jump_target.basic_block);
865 115 : mark_unreachable ();
866 115 : return;
867 203 : } else if (jump_target.is_finally_clause) {
868 0 : current_block.connect (jump_target.basic_block);
869 0 : current_block = jump_target.last_block;
870 : }
871 : }
872 :
873 1 : Report.error (stmt.source_reference, "no enclosing loop found");
874 1 : stmt.error = true;
875 : }
876 :
877 109061 : public override void visit_return_statement (ReturnStatement stmt) {
878 109061 : stmt.accept_children (this);
879 :
880 109061 : if (unreachable (stmt)) {
881 : return;
882 : }
883 :
884 109059 : current_block.add_node (stmt);
885 :
886 109059 : if (stmt.return_expression != null) {
887 108744 : handle_errors (stmt.return_expression);
888 : }
889 :
890 331881 : for (int i = jump_stack.size - 1; i >= 0; i--) {
891 220470 : var jump_target = jump_stack[i];
892 220470 : if (jump_target.is_return_target) {
893 109059 : current_block.connect (jump_target.basic_block);
894 109059 : mark_unreachable ();
895 109059 : return;
896 111411 : } else if (jump_target.is_finally_clause) {
897 4 : current_block.connect (jump_target.basic_block);
898 8 : current_block = jump_target.last_block;
899 : }
900 : }
901 :
902 0 : Report.error (stmt.source_reference, "no enclosing loop found");
903 0 : stmt.error = true;
904 : }
905 :
906 479339 : private void handle_errors (CodeNode node, bool always_fail = false) {
907 482793 : if (node.tree_can_fail) {
908 3454 : var last_block = current_block;
909 :
910 : // exceptional control flow
911 3454 : var error_types = new ArrayList<DataType> ();
912 3454 : node.get_error_types (error_types);
913 10386 : foreach (DataType error_data_type in error_types) {
914 3466 : unowned ErrorType? error_type = error_data_type as ErrorType;
915 3466 : unowned Class? error_class = error_data_type.type_symbol as Class;
916 6932 : current_block = last_block;
917 3466 : unreachable_reported = true;
918 :
919 3722 : for (int i = jump_stack.size - 1; i >= 0; i--) {
920 3594 : var jump_target = jump_stack[i];
921 3594 : if (jump_target.is_exit_target) {
922 1381 : current_block.connect (jump_target.basic_block);
923 1381 : mark_unreachable ();
924 1381 : break;
925 2213 : } else if (jump_target.is_error_target) {
926 2094 : if (context.profile == Profile.GOBJECT) {
927 2094 : if (jump_target.error_domain == null
928 2001 : || (jump_target.error_domain == error_type.error_domain
929 1998 : && (jump_target.error_code == null
930 7 : || jump_target.error_code == error_type.error_code))) {
931 : // error can always be caught by this catch clause
932 : // following catch clauses cannot be reached by this error
933 2085 : current_block.connect (jump_target.basic_block);
934 2085 : mark_unreachable ();
935 2085 : break;
936 9 : } else if (error_type.error_domain == null
937 8 : || (error_type.error_domain == jump_target.error_domain
938 6 : && (error_type.error_code == null
939 1 : || error_type.error_code == jump_target.error_code))) {
940 : // error might be caught by this catch clause
941 : // unknown at compile time
942 : // following catch clauses might still be reached by this error
943 6 : current_block.connect (jump_target.basic_block);
944 : }
945 0 : } else if (jump_target.error_class == null || jump_target.error_class == error_class) {
946 : // error can always be caught by this catch clause
947 : // following catch clauses cannot be reached by this error
948 0 : current_block.connect (jump_target.basic_block);
949 0 : mark_unreachable ();
950 0 : break;
951 0 : } else if (jump_target.error_class.is_subtype_of (error_class)) {
952 : // error might be caught by this catch clause
953 : // unknown at compile time
954 : // following catch clauses might still be reached by this error
955 0 : current_block.connect (jump_target.basic_block);
956 : }
957 119 : } else if (jump_target.is_finally_clause) {
958 9 : current_block.connect (jump_target.basic_block);
959 18 : current_block = jump_target.last_block;
960 : }
961 : }
962 : }
963 :
964 : // normal control flow
965 3454 : if (!always_fail) {
966 2433 : current_block = new BasicBlock ();
967 2433 : all_basic_blocks.add (current_block);
968 2433 : last_block.connect (current_block);
969 : }
970 : }
971 : }
972 :
973 17 : public override void visit_yield_statement (YieldStatement stmt) {
974 17 : if (unreachable (stmt)) {
975 : return;
976 : }
977 :
978 17 : stmt.accept_children (this);
979 : }
980 :
981 1021 : public override void visit_throw_statement (ThrowStatement stmt) {
982 1021 : if (unreachable (stmt)) {
983 : return;
984 : }
985 :
986 1021 : current_block.add_node (stmt);
987 1021 : handle_errors (stmt, true);
988 : }
989 :
990 4189 : public override void visit_try_statement (TryStatement stmt) {
991 2096 : if (unreachable (stmt)) {
992 : return;
993 : }
994 :
995 2096 : var before_try_block = current_block;
996 2096 : var after_try_block = new BasicBlock ();
997 2096 : all_basic_blocks.add (after_try_block);
998 :
999 2096 : BasicBlock finally_block = null;
1000 2138 : if (stmt.finally_body != null) {
1001 44 : finally_block = new BasicBlock ();
1002 44 : all_basic_blocks.add (finally_block);
1003 88 : current_block = finally_block;
1004 :
1005 : // trap all forbidden jumps
1006 44 : var invalid_block = new BasicBlock ();
1007 44 : all_basic_blocks.add (invalid_block);
1008 44 : jump_stack.add (new JumpTarget.any_target (invalid_block));
1009 :
1010 44 : stmt.finally_body.accept (this);
1011 :
1012 44 : jump_stack.remove_at (jump_stack.size - 1);
1013 :
1014 44 : if (invalid_block.get_predecessors ().size > 0) {
1015 : // don't allow finally blocks with e.g. return statements
1016 2 : Report.error (stmt.finally_body.source_reference, "jump out of finally block not permitted");
1017 2 : stmt.error = true;
1018 2 : return;
1019 : }
1020 :
1021 42 : if (current_block != null) {
1022 41 : jump_stack.add (new JumpTarget.finally_clause (finally_block, current_block));
1023 : }
1024 : }
1025 :
1026 2094 : int finally_jump_stack_size = jump_stack.size;
1027 :
1028 4188 : var catch_clauses = stmt.get_catch_clauses ();
1029 6232 : for (int i = catch_clauses.size - 1; i >= 0; i--) {
1030 2069 : var catch_clause = catch_clauses[i];
1031 2069 : var error_block = new BasicBlock ();
1032 2069 : all_basic_blocks.add (error_block);
1033 :
1034 2069 : if (catch_clause.error_type != null && !catch_clause.error) {
1035 2069 : if (context.profile == Profile.GOBJECT) {
1036 2069 : unowned ErrorType error_type = (ErrorType) catch_clause.error_type;
1037 4059 : jump_stack.add (new JumpTarget.error_target (error_block, catch_clause, catch_clause.error_type.type_symbol as ErrorDomain, error_type.error_code, null));
1038 : } else {
1039 0 : unowned Class? error_class = catch_clause.error_type.type_symbol as Class;
1040 0 : jump_stack.add (new JumpTarget.error_target (error_block, catch_clause, null, null, error_class));
1041 : }
1042 : } else {
1043 0 : jump_stack.add (new JumpTarget.error_target (error_block, catch_clause, null, null, null));
1044 : }
1045 : }
1046 :
1047 4188 : current_block = before_try_block;
1048 :
1049 2094 : stmt.body.accept (this);
1050 :
1051 2094 : if (current_block != null) {
1052 128 : if (finally_block != null) {
1053 39 : current_block.connect (finally_block);
1054 39 : current_block = finally_block;
1055 : }
1056 128 : current_block.connect (after_try_block);
1057 : }
1058 :
1059 : // remove catch clauses from jump stack
1060 2094 : List<JumpTarget> catch_stack = new ArrayList<JumpTarget> ();
1061 6232 : for (int i = jump_stack.size - 1; i >= finally_jump_stack_size; i--) {
1062 2069 : var jump_target = jump_stack.remove_at (i);
1063 2069 : catch_stack.add (jump_target);
1064 : }
1065 :
1066 6230 : foreach (JumpTarget jump_target in catch_stack) {
1067 :
1068 2089 : foreach (JumpTarget prev_target in catch_stack) {
1069 2079 : if (prev_target == jump_target) {
1070 2068 : break;
1071 : }
1072 :
1073 11 : if (context.profile == Profile.GOBJECT) {
1074 11 : if (prev_target.error_domain == jump_target.error_domain &&
1075 2 : prev_target.error_code == jump_target.error_code) {
1076 1 : Report.error (stmt.source_reference, "double catch clause of same error detected");
1077 1 : stmt.error = true;
1078 1 : return;
1079 : }
1080 0 : } else if (prev_target.error_class == jump_target.error_class) {
1081 0 : Report.error (stmt.source_reference, "double catch clause of same error detected");
1082 0 : stmt.error = true;
1083 0 : return;
1084 : }
1085 : }
1086 :
1087 2068 : if (jump_target.basic_block.get_predecessors ().size == 0) {
1088 : // unreachable
1089 3 : Report.warning (jump_target.catch_clause.source_reference, "unreachable catch clause detected");
1090 : } else {
1091 4130 : current_block = jump_target.basic_block;
1092 2065 : current_block.add_node (jump_target.catch_clause);
1093 2065 : jump_target.catch_clause.body.accept (this);
1094 2065 : if (current_block != null) {
1095 83 : if (finally_block != null) {
1096 4 : current_block.connect (finally_block);
1097 4 : current_block = finally_block;
1098 : }
1099 83 : current_block.connect (after_try_block);
1100 : }
1101 : }
1102 : }
1103 :
1104 2093 : if (finally_block != null) {
1105 42 : jump_stack.remove_at (jump_stack.size - 1);
1106 : }
1107 :
1108 : // after try statement
1109 : // reachable?
1110 2093 : if (after_try_block.get_predecessors ().size > 0) {
1111 314 : current_block = after_try_block;
1112 : } else {
1113 1936 : stmt.after_try_block_reachable = false;
1114 1936 : mark_unreachable ();
1115 : }
1116 : }
1117 :
1118 26 : public override void visit_lock_statement (LockStatement stmt) {
1119 26 : if (unreachable (stmt)) {
1120 : return;
1121 : }
1122 : }
1123 :
1124 26 : public override void visit_unlock_statement (UnlockStatement stmt) {
1125 26 : if (unreachable (stmt)) {
1126 : return;
1127 : }
1128 : }
1129 :
1130 1585780 : public override void visit_expression (Expression expr) {
1131 : // lambda expression is handled separately
1132 1585780 : if (!(expr is LambdaExpression)) {
1133 1581578 : expr.accept_children (this);
1134 : }
1135 : }
1136 :
1137 550773 : private bool unreachable (CodeNode node) {
1138 550773 : if (current_block == null) {
1139 32 : node.unreachable = true;
1140 32 : if (!unreachable_reported) {
1141 30 : Report.warning (node.source_reference, "unreachable code detected");
1142 30 : unreachable_reported = true;
1143 : }
1144 32 : return true;
1145 : }
1146 :
1147 550773 : return false;
1148 : }
1149 :
1150 131865 : void mark_unreachable () {
1151 131865 : current_block = null;
1152 131865 : unreachable_reported = false;
1153 : }
1154 : }
|
