valaflowanalyzer.vala 31 KB
Newer Older
1
/* valaflowanalyzer.vala
2
 *
3
 * Copyright (C) 2008-2010  Jürg Billeter
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.

 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
 *
 * Author:
 * 	Jürg Billeter <j@bitron.ch>
 */

using GLib;

/**
 * Code visitor building the control flow graph.
 */
28
public class Vala.FlowAnalyzer : CodeVisitor {
29
	private class JumpTarget {
30 31 32
		public bool is_break_target { get; set; }
		public bool is_continue_target { get; set; }
		public bool is_return_target { get; set; }
33
		public bool is_exit_target { get; set; }
34
		public bool is_error_target { get; set; }
35 36
		public ErrorDomain? error_domain { get; set; }
		public ErrorCode? error_code { get; set; }
37
		public Class? error_class { get; set; }
38
		public bool is_finally_clause { get; set; }
39 40 41 42
		public BasicBlock basic_block { get; set; }
		public BasicBlock? last_block { get; set; }
		public CatchClause? catch_clause { get; set; }

43 44
		public JumpTarget.break_target (BasicBlock basic_block) {
			this.basic_block = basic_block;
45
			is_break_target = true;
46 47
		}

48 49
		public JumpTarget.continue_target (BasicBlock basic_block) {
			this.basic_block = basic_block;
50
			is_continue_target = true;
51 52
		}

53 54
		public JumpTarget.return_target (BasicBlock basic_block) {
			this.basic_block = basic_block;
55
			is_return_target = true;
56 57
		}

58 59 60 61 62
		public JumpTarget.exit_target (BasicBlock basic_block) {
			this.basic_block = basic_block;
			is_exit_target = true;
		}

63
		public JumpTarget.error_target (BasicBlock basic_block, CatchClause catch_clause, ErrorDomain? error_domain, ErrorCode? error_code, Class? error_class) {
64 65 66 67
			this.basic_block = basic_block;
			this.catch_clause = catch_clause;
			this.error_domain = error_domain;
			this.error_code = error_code;
68
			this.error_class = error_class;
69
			is_error_target = true;
70 71
		}

72 73 74 75 76
		public JumpTarget.any_target (BasicBlock basic_block) {
			this.basic_block = basic_block;
			is_break_target = true;
			is_continue_target = true;
			is_return_target = true;
77
			is_exit_target = true;
78 79 80
			is_error_target = true;
		}

81 82 83
		public JumpTarget.finally_clause (BasicBlock basic_block, BasicBlock last_block) {
			this.basic_block = basic_block;
			this.last_block = last_block;
84
			is_finally_clause = true;
85 86 87
		}
	}

88 89 90
	private CodeContext context;
	private BasicBlock current_block;
	private bool unreachable_reported;
91
	private List<JumpTarget> jump_stack = new ArrayList<JumpTarget> ();
92

93
	Map<Symbol, List<LocalVariable>> var_map;
94 95 96 97
	Set<LocalVariable> used_vars;
	Map<LocalVariable, PhiFunction> phi_functions;

	public FlowAnalyzer () {
98 99 100 101 102 103 104
	}

	/**
	 * Build control flow graph in the specified context.
	 *
	 * @param context a code context
	 */
105
	public void analyze (CodeContext context) {
106 107 108 109 110
		this.context = context;

		/* we're only interested in non-pkg source files */
		var source_files = context.get_source_files ();
		foreach (SourceFile file in source_files) {
111
			if (!file.external_package) {
112 113 114 115 116
				file.accept (this);
			}
		}
	}

117
	public override void visit_source_file (SourceFile source_file) {
118 119 120
		source_file.accept_children (this);
	}

121
	public override void visit_class (Class cl) {
122 123 124
		cl.accept_children (this);
	}

125
	public override void visit_struct (Struct st) {
126 127 128
		st.accept_children (this);
	}

129
	public override void visit_interface (Interface iface) {
130 131 132
		iface.accept_children (this);
	}

133
	public override void visit_enum (Enum en) {
134 135 136
		en.accept_children (this);
	}

137 138 139 140
	public override void visit_error_domain (ErrorDomain ed) {
		ed.accept_children (this);
	}

141
	public override void visit_field (Field f) {
142
		if (f.is_internal_symbol () && !f.used) {
143 144 145 146 147
			if (!f.is_private_symbol () && context.internal_header_filename != null) {
				// do not warn if internal member may be used outside this compilation unit
			} else {
				Report.warning (f.source_reference, "field `%s' never used".printf (f.get_full_name ()));
			}
148 149 150
		}
	}

151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
	public override void visit_lambda_expression (LambdaExpression le) {
		var old_current_block = current_block;
		var old_unreachable_reported = unreachable_reported;
		var old_jump_stack = jump_stack;
		current_block = null;
		unreachable_reported = false;
		jump_stack = new ArrayList<JumpTarget> ();

		le.accept_children (this);

		current_block = old_current_block;
		unreachable_reported = old_unreachable_reported;
		jump_stack = old_jump_stack;
	}

166
	public override void visit_method (Method m) {
167 168 169
		if (m.is_internal_symbol () && !m.used && !m.entry_point
		    && !m.overrides && (m.base_interface_method == null || m.base_interface_method == m)
		    && !(m is CreationMethod)) {
170 171 172 173 174
			if (!m.is_private_symbol () && context.internal_header_filename != null) {
				// do not warn if internal member may be used outside this compilation unit
			} else {
				Report.warning (m.source_reference, "method `%s' never used".printf (m.get_full_name ()));
			}
175 176
		}

177 178 179 180 181
		if (m.body == null) {
			return;
		}

		m.entry_block = new BasicBlock.entry ();
182
		m.return_block = new BasicBlock ();
183 184
		m.exit_block = new BasicBlock.exit ();

185 186
		m.return_block.connect (m.exit_block);

187 188 189 190
		if (context.profile == Profile.DOVA && !(m.return_type is VoidType)) {
			// ensure result is defined at end of method
			var result_ma = new MemberAccess.simple ("result", m.source_reference);
			result_ma.symbol_reference = m.result_var;
191
			m.return_block.add_node (result_ma);
192 193
		}

194 195
		current_block = new BasicBlock ();
		m.entry_block.connect (current_block);
196
		current_block.add_node (m);
197

198 199
		jump_stack.add (new JumpTarget.return_target (m.return_block));
		jump_stack.add (new JumpTarget.exit_target (m.exit_block));
200

201 202
		m.accept_children (this);

203 204
		jump_stack.remove_at (jump_stack.size - 1);

205 206 207
		if (current_block != null) {
			// end of method body reachable

208
			if (context.profile != Profile.DOVA && !(m.return_type is VoidType)) {
209
				Report.error (m.source_reference, "missing return statement at end of method or lambda body");
210 211 212
				m.error = true;
			}

213
			current_block.connect (m.return_block);
214
		}
215

216 217 218 219
		analyze_body (m.entry_block);
	}

	void analyze_body (BasicBlock entry_block) {
220 221 222 223 224
		var block_list = get_depth_first_list (entry_block);

		build_dominator_tree (block_list, entry_block);
		build_dominator_frontier (block_list, entry_block);
		insert_phi_functions (block_list, entry_block);
225
		check_variables (entry_block);
226 227
	}

228
	// generates reverse postorder list
229
	List<BasicBlock> get_depth_first_list (BasicBlock entry_block) {
230
		var list = new ArrayList<BasicBlock> ();
231
		depth_first_traverse (entry_block, list);
232 233 234
		return list;
	}

235
	void depth_first_traverse (BasicBlock current, List<BasicBlock> list) {
236
		if (current.postorder_visited) {
237 238
			return;
		}
239
		current.postorder_visited = true;
240 241 242
		foreach (BasicBlock succ in current.get_successors ()) {
			depth_first_traverse (succ, list);
		}
243
		current.postorder_number = list.size;
244
		list.insert (0, current);
245 246
	}

247
	void build_dominator_tree (List<BasicBlock> block_list, BasicBlock entry_block) {
248 249 250
		// immediate dominators
		var idoms = new BasicBlock[block_list.size];
		idoms[entry_block.postorder_number] = entry_block;
251

252 253 254
		bool changed = true;
		while (changed) {
			changed = false;
255
			foreach (BasicBlock block in block_list) {
256 257 258 259 260 261
				if (block == entry_block) {
					continue;
				}

				// new immediate dominator
				BasicBlock new_idom = null;
262 263
				bool first = true;
				foreach (BasicBlock pred in block.get_predecessors ()) {
264 265 266 267 268 269
					if (idoms[pred.postorder_number] != null) {
						if (first) {
							new_idom = pred;
							first = false;
						} else {
							new_idom = intersect (idoms, pred, new_idom);
270 271 272
						}
					}
				}
273 274 275
				if (idoms[block.postorder_number] != new_idom) {
					idoms[block.postorder_number] = new_idom;
					changed = true;
276 277 278 279 280 281
				}
			}
		}

		// build tree
		foreach (BasicBlock block in block_list) {
282
			if (block == entry_block) {
283 284 285
				continue;
			}

286 287 288
			idoms[block.postorder_number].add_child (block);
		}
	}
289

290 291 292 293 294 295 296
	BasicBlock intersect (BasicBlock[] idoms, BasicBlock b1, BasicBlock b2) {
		while (b1 != b2) {
			while (b1.postorder_number < b2.postorder_number) {
				b1 = idoms[b2.postorder_number];
			}
			while (b2.postorder_number < b1.postorder_number) {
				b2 = idoms[b2.postorder_number];
297 298
			}
		}
299
		return b1;
300 301
	}

302
	void build_dominator_frontier (List<BasicBlock> block_list, BasicBlock entry_block) {
303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323
		for (int i = block_list.size - 1; i >= 0; i--) {
			var block = block_list[i];

			foreach (BasicBlock succ in block.get_successors ()) {
				// if idom(succ) != block
				if (succ.parent != block) {
					block.add_dominator_frontier (succ);
				}
			}

			foreach (BasicBlock child in block.get_children ()) {
				foreach (BasicBlock child_frontier in child.get_dominator_frontier ()) {
					// if idom(child_frontier) != block
					if (child_frontier.parent != block) {
						block.add_dominator_frontier (child_frontier);
					}
				}
			}
		}
	}

324
	Map<LocalVariable, Set<BasicBlock>> get_assignment_map (List<BasicBlock> block_list, BasicBlock entry_block) {
325
		var map = new HashMap<LocalVariable, Set<BasicBlock>> ();
326
		foreach (BasicBlock block in block_list) {
327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343
			var defined_variables = new ArrayList<LocalVariable> ();
			foreach (CodeNode node in block.get_nodes ()) {
				node.get_defined_variables (defined_variables);
			}

			foreach (LocalVariable local in defined_variables) {
				var block_set = map.get (local);
				if (block_set == null) {
					block_set = new HashSet<BasicBlock> ();
					map.set (local, block_set);
				}
				block_set.add (block);
			}
		}
		return map;
	}

344 345
	void insert_phi_functions (List<BasicBlock> block_list, BasicBlock entry_block) {
		var assign = get_assignment_map (block_list, entry_block);
346 347 348 349 350 351

		int counter = 0;
		var work_list = new ArrayList<BasicBlock> ();

		var added = new HashMap<BasicBlock, int> ();
		var phi = new HashMap<BasicBlock, int> ();
352
		foreach (BasicBlock block in block_list) {
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381
			added.set (block, 0);
			phi.set (block, 0);
		}

		foreach (LocalVariable local in assign.get_keys ()) {
			counter++;
			foreach (BasicBlock block in assign.get (local)) {
				work_list.add (block);
				added.set (block, counter);
			}
			while (work_list.size > 0) {
				BasicBlock block = work_list.get (0);
				work_list.remove_at (0);
				foreach (BasicBlock frontier in block.get_dominator_frontier ()) {
					int blockPhi = phi.get (frontier);
					if (blockPhi < counter) {
						frontier.add_phi_function (new PhiFunction (local, frontier.get_predecessors ().size));
						phi.set (frontier, counter);
						int block_added = added.get (frontier);
						if (block_added < counter) {
							added.set (frontier, counter);
							work_list.add (frontier);
						}
					}
				}
			}
		}
	}

382
	void check_variables (BasicBlock entry_block) {
383
		var_map = new HashMap<Symbol, List<LocalVariable>>();
384 385 386
		used_vars = new HashSet<LocalVariable> ();
		phi_functions = new HashMap<LocalVariable, PhiFunction> ();

387
		check_block_variables (entry_block);
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414

		// check for variables used before initialization
		var used_vars_queue = new ArrayList<LocalVariable> ();
		foreach (LocalVariable local in used_vars) {
			used_vars_queue.add (local);
		}
		while (used_vars_queue.size > 0) {
			LocalVariable used_var = used_vars_queue[0];
			used_vars_queue.remove_at (0);

			PhiFunction phi = phi_functions.get (used_var);
			if (phi != null) {
				foreach (LocalVariable local in phi.operands) {
					if (local == null) {
						Report.error (used_var.source_reference, "use of possibly unassigned local variable `%s'".printf (used_var.name));
						continue;
					}
					if (!(local in used_vars)) {
						local.source_reference = used_var.source_reference;
						used_vars.add (local);
						used_vars_queue.add (local);
					}
				}
			}
		}
	}

415
	void check_block_variables (BasicBlock block) {
416
		foreach (PhiFunction phi in block.get_phi_functions ()) {
417
			LocalVariable versioned_var = process_assignment (var_map, phi.original_variable);
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442

			phi_functions.set (versioned_var, phi);
		}

		foreach (CodeNode node in block.get_nodes ()) {
			var used_variables = new ArrayList<LocalVariable> ();
			node.get_used_variables (used_variables);
			
			foreach (LocalVariable var_symbol in used_variables) {
				var variable_stack = var_map.get (var_symbol);
				if (variable_stack == null || variable_stack.size == 0) {
					Report.error (node.source_reference, "use of possibly unassigned local variable `%s'".printf (var_symbol.name));
					continue;
				}
				var versioned_local = variable_stack.get (variable_stack.size - 1);
				if (!(versioned_local in used_vars)) {
					versioned_local.source_reference = node.source_reference;
				}
				used_vars.add (versioned_local);
			}

			var defined_variables = new ArrayList<LocalVariable> ();
			node.get_defined_variables (defined_variables);

			foreach (LocalVariable local in defined_variables) {
443
				process_assignment (var_map, local);
444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464
			}
		}

		foreach (BasicBlock succ in block.get_successors ()) {
			int j = 0;
			foreach (BasicBlock pred in succ.get_predecessors ()) {
				if (pred == block) {
					break;
				}
				j++;
			}

			foreach (PhiFunction phi in succ.get_phi_functions ()) {
				var variable_stack = var_map.get (phi.original_variable);
				if (variable_stack != null && variable_stack.size > 0) {
					phi.operands.set (j, variable_stack.get (variable_stack.size - 1));
				}
			}
		}

		foreach (BasicBlock child in block.get_children ()) {
465
			check_block_variables (child);
466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482
		}

		foreach (PhiFunction phi in block.get_phi_functions ()) {
			var variable_stack = var_map.get (phi.original_variable);
			variable_stack.remove_at (variable_stack.size - 1);
		}
		foreach (CodeNode node in block.get_nodes ()) {
			var defined_variables = new ArrayList<LocalVariable> ();
			node.get_defined_variables (defined_variables);

			foreach (LocalVariable local in defined_variables) {
				var variable_stack = var_map.get (local);
				variable_stack.remove_at (variable_stack.size - 1);
			}
		}
	}

483
	LocalVariable process_assignment (Map<Symbol, List<LocalVariable>> var_map, LocalVariable var_symbol) {
484 485 486 487 488 489 490 491
		var variable_stack = var_map.get (var_symbol);
		if (variable_stack == null) {
			variable_stack = new ArrayList<LocalVariable> ();
			var_map.set (var_symbol, variable_stack);
		}
		LocalVariable versioned_var = new LocalVariable (var_symbol.variable_type, var_symbol.name, null, var_symbol.source_reference);
		variable_stack.add (versioned_var);
		return versioned_var;
492 493
	}

494 495 496 497
	public override void visit_creation_method (CreationMethod m) {
		visit_method (m);
	}

498
	public override void visit_property (Property prop) {
499 500 501
		prop.accept_children (this);
	}

502
	public override void visit_property_accessor (PropertyAccessor acc) {
503 504 505 506 507
		if (acc.body == null) {
			return;
		}

		acc.entry_block = new BasicBlock.entry ();
508
		acc.return_block = new BasicBlock ();
509 510
		acc.exit_block = new BasicBlock.exit ();

511 512
		acc.return_block.connect (acc.exit_block);

513 514 515 516
		if (context.profile == Profile.DOVA && acc.readable) {
			// ensure result is defined at end of method
			var result_ma = new MemberAccess.simple ("result", acc.source_reference);
			result_ma.symbol_reference = acc.result_var;
517
			acc.return_block.add_node (result_ma);
518 519
		}

520 521
		current_block = new BasicBlock ();
		acc.entry_block.connect (current_block);
522

523 524
		jump_stack.add (new JumpTarget.return_target (acc.return_block));
		jump_stack.add (new JumpTarget.exit_target (acc.exit_block));
525 526 527 528 529 530 531 532

		acc.accept_children (this);

		jump_stack.remove_at (jump_stack.size - 1);

		if (current_block != null) {
			// end of property accessor body reachable

533
			if (context.profile != Profile.DOVA && acc.readable) {
534 535 536 537
				Report.error (acc.source_reference, "missing return statement at end of property getter body");
				acc.error = true;
			}

538
			current_block.connect (acc.return_block);
539
		}
540

541
		analyze_body (acc.entry_block);
542 543
	}

544
	public override void visit_block (Block b) {
545 546 547
		b.accept_children (this);
	}

548
	public override void visit_declaration_statement (DeclarationStatement stmt) {
549
		if (unreachable (stmt)) {
550
			stmt.declaration.unreachable = true;
551 552 553
			return;
		}

554 555 556 557
		if (!stmt.declaration.used) {
			Report.warning (stmt.declaration.source_reference, "local variable `%s' declared but never used".printf (stmt.declaration.name));
		}

558
		current_block.add_node (stmt);
559

560 561 562
		var local = stmt.declaration as LocalVariable;
		if (local != null && local.initializer != null) {
			handle_errors (local.initializer);
563
		}
564 565
	}

566
	public override void visit_expression_statement (ExpressionStatement stmt) {
567 568
		stmt.accept_children (this);

569 570 571 572 573
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
574 575

		handle_errors (stmt);
576

577 578
		if (stmt.expression is MethodCall) {
			var expr = (MethodCall) stmt.expression;
579
			var ma = expr.call as MemberAccess;
580
			if (ma != null && ma.symbol_reference != null && ma.symbol_reference.get_attribute ("NoReturn") != null) {
581 582 583 584 585
				current_block = null;
				unreachable_reported = false;
				return;
			}
		}
586 587
	}

588 589 590 591 592 593 594 595 596 597
	bool always_true (Expression condition) {
		var literal = condition as BooleanLiteral;
		return (literal != null && literal.value);
	}

	bool always_false (Expression condition) {
		var literal = condition as BooleanLiteral;
		return (literal != null && !literal.value);
	}

598
	public override void visit_if_statement (IfStatement stmt) {
599 600 601 602 603 604 605
		if (unreachable (stmt)) {
			return;
		}

		// condition
		current_block.add_node (stmt.condition);

606 607
		handle_errors (stmt.condition);

608 609
		// true block
		var last_block = current_block;
610 611 612 613 614 615 616
		if (always_false (stmt.condition)) {
			current_block = null;
			unreachable_reported = false;
		} else {
			current_block = new BasicBlock ();
			last_block.connect (current_block);
		}
617 618 619 620
		stmt.true_statement.accept (this);

		// false block
		var last_true_block = current_block;
621 622 623 624 625 626 627
		if (always_true (stmt.condition)) {
			current_block = null;
			unreachable_reported = false;
		} else {
			current_block = new BasicBlock ();
			last_block.connect (current_block);
		}
628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
		if (stmt.false_statement != null) {
			stmt.false_statement.accept (this);
		}

		// after if/else
		var last_false_block = current_block;
		// reachable?
		if (last_true_block != null || last_false_block != null) {
			current_block = new BasicBlock ();
			if (last_true_block != null) {
				last_true_block.connect (current_block);
			}
			if (last_false_block != null) {
				last_false_block.connect (current_block);
			}
		}
	}

646
	public override void visit_switch_statement (SwitchStatement stmt) {
647 648 649 650 651
		if (unreachable (stmt)) {
			return;
		}

		var after_switch_block = new BasicBlock ();
652
		jump_stack.add (new JumpTarget.break_target (after_switch_block));
653 654 655 656 657

		// condition
		current_block.add_node (stmt.expression);
		var condition_block = current_block;

658 659
		handle_errors (stmt.expression);

660 661 662 663 664
		bool has_default_label = false;

		foreach (SwitchSection section in stmt.get_sections ()) {
			current_block = new BasicBlock ();
			condition_block.connect (current_block);
665 666
			foreach (Statement section_stmt in section.get_statements ()) {
				section_stmt.accept (this);
667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683
			}

			if (section.has_default_label ()) {
				has_default_label = true;
			}

			if (current_block != null) {
				// end of switch section reachable
				// we don't allow fall-through

				Report.error (section.source_reference, "missing break statement at end of switch section");
				section.error = true;

				current_block.connect (after_switch_block);
			}
		}

684 685 686 687
		if (!has_default_label) {
			condition_block.connect (after_switch_block);
		}

688 689
		// after switch
		// reachable?
690
		if (after_switch_block.get_predecessors ().size > 0) {
691 692 693 694 695 696
			current_block = after_switch_block;
		} else {
			current_block = null;
			unreachable_reported = false;
		}

697
		jump_stack.remove_at (jump_stack.size - 1);
698 699
	}

700
	public override void visit_loop (Loop stmt) {
701 702 703 704
		if (unreachable (stmt)) {
			return;
		}

705 706
		var loop_block = new BasicBlock ();
		jump_stack.add (new JumpTarget.continue_target (loop_block));
707
		var after_loop_block = new BasicBlock ();
708
		jump_stack.add (new JumpTarget.break_target (after_loop_block));
709

710
		// loop block
711
		var last_block = current_block;
712 713
		last_block.connect (loop_block);
		current_block = loop_block;
714 715 716 717

		stmt.body.accept (this);
		// end of loop block reachable?
		if (current_block != null) {
718
			current_block.connect (loop_block);
719 720 721
		}

		// after loop
722
		// reachable?
723 724
		if (after_loop_block.get_predecessors ().size == 0) {
			// after loop block not reachable
725 726 727
			current_block = null;
			unreachable_reported = false;
		} else {
728
			// after loop block reachable
729 730
			current_block = after_loop_block;
		}
731

732 733
		jump_stack.remove_at (jump_stack.size - 1);
		jump_stack.remove_at (jump_stack.size - 1);
734 735
	}

736
	public override void visit_foreach_statement (ForeachStatement stmt) {
737 738 739 740
		if (unreachable (stmt)) {
			return;
		}

741 742 743 744
		// collection
		current_block.add_node (stmt.collection);
		handle_errors (stmt.collection);

745
		var loop_block = new BasicBlock ();
746
		jump_stack.add (new JumpTarget.continue_target (loop_block));
747
		var after_loop_block = new BasicBlock ();
748
		jump_stack.add (new JumpTarget.break_target (after_loop_block));
749 750 751 752 753

		// loop block
		var last_block = current_block;
		last_block.connect (loop_block);
		current_block = loop_block;
754
		current_block.add_node (stmt);
755 756 757 758 759 760 761 762 763 764 765 766
		stmt.body.accept (this);
		if (current_block != null) {
			current_block.connect (loop_block);
		}

		// after loop
		last_block.connect (after_loop_block);
		if (current_block != null) {
			current_block.connect (after_loop_block);
		}
		current_block = after_loop_block;

767 768
		jump_stack.remove_at (jump_stack.size - 1);
		jump_stack.remove_at (jump_stack.size - 1);
769 770
	}

771
	public override void visit_break_statement (BreakStatement stmt) {
772 773 774 775 776
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
777 778 779

		for (int i = jump_stack.size - 1; i >= 0; i--) {
			var jump_target = jump_stack[i];
780
			if (jump_target.is_break_target) {
781 782 783 784
				current_block.connect (jump_target.basic_block);
				current_block = null;
				unreachable_reported = false;
				return;
785
			} else if (jump_target.is_finally_clause) {
786 787 788 789 790 791 792
				current_block.connect (jump_target.basic_block);
				current_block = jump_target.last_block;
			}
		}

		Report.error (stmt.source_reference, "no enclosing loop or switch statement found");
		stmt.error = true;
793 794
	}

795
	public override void visit_continue_statement (ContinueStatement stmt) {
796 797 798 799 800
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
801 802 803

		for (int i = jump_stack.size - 1; i >= 0; i--) {
			var jump_target = jump_stack[i];
804
			if (jump_target.is_continue_target) {
805 806 807 808
				current_block.connect (jump_target.basic_block);
				current_block = null;
				unreachable_reported = false;
				return;
809
			} else if (jump_target.is_finally_clause) {
810 811 812 813 814 815 816
				current_block.connect (jump_target.basic_block);
				current_block = jump_target.last_block;
			}
		}

		Report.error (stmt.source_reference, "no enclosing loop found");
		stmt.error = true;
817 818
	}

819
	public override void visit_return_statement (ReturnStatement stmt) {
820 821
		stmt.accept_children (this);

822 823 824 825 826
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
827

828 829 830 831
		if (stmt.return_expression != null) {
			handle_errors (stmt.return_expression);
		}

832 833
		for (int i = jump_stack.size - 1; i >= 0; i--) {
			var jump_target = jump_stack[i];
834
			if (jump_target.is_return_target) {
835 836 837 838
				current_block.connect (jump_target.basic_block);
				current_block = null;
				unreachable_reported = false;
				return;
839
			} else if (jump_target.is_finally_clause) {
840 841 842 843 844 845 846 847 848
				current_block.connect (jump_target.basic_block);
				current_block = jump_target.last_block;
			}
		}

		Report.error (stmt.source_reference, "no enclosing loop found");
		stmt.error = true;
	}

849
	private void handle_errors (CodeNode node, bool always_fail = false) {
850 851 852 853
		if (node.tree_can_fail) {
			var last_block = current_block;

			// exceptional control flow
854 855
			foreach (DataType error_data_type in node.get_error_types()) {
				var error_type = error_data_type as ErrorType;
856
				var error_class = error_data_type.data_type as Class;
857 858 859 860 861
				current_block = last_block;
				unreachable_reported = true;

				for (int i = jump_stack.size - 1; i >= 0; i--) {
					var jump_target = jump_stack[i];
862
					if (jump_target.is_exit_target) {
863
						current_block.connect (jump_target.basic_block);
864 865 866
						current_block = null;
						unreachable_reported = false;
						break;
867
					} else if (jump_target.is_error_target) {
868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888
						if (context.profile == Profile.GOBJECT) {
							if (jump_target.error_domain == null
							    || (jump_target.error_domain == error_type.error_domain
								&& (jump_target.error_code == null
								    || jump_target.error_code == error_type.error_code))) {
								// error can always be caught by this catch clause
								// following catch clauses cannot be reached by this error
								current_block.connect (jump_target.basic_block);
								current_block = null;
								unreachable_reported = false;
								break;
							} else if (error_type.error_domain == null
								   || (error_type.error_domain == jump_target.error_domain
								       && (error_type.error_code == null
								           || error_type.error_code == jump_target.error_code))) {
								// error might be caught by this catch clause
								// unknown at compile time
								// following catch clauses might still be reached by this error
								current_block.connect (jump_target.basic_block);
							}
						} else if (jump_target.error_class == null || jump_target.error_class == error_class) {
889 890
							// error can always be caught by this catch clause
							// following catch clauses cannot be reached by this error
891 892 893 894
							current_block.connect (jump_target.basic_block);
							current_block = null;
							unreachable_reported = false;
							break;
895
						} else if (jump_target.error_class.is_subtype_of (error_class)) {
896 897 898 899
							// error might be caught by this catch clause
							// unknown at compile time
							// following catch clauses might still be reached by this error
							current_block.connect (jump_target.basic_block);
900 901 902 903
						}
					} else if (jump_target.is_finally_clause) {
						current_block.connect (jump_target.basic_block);
						current_block = jump_target.last_block;
904 905 906 907 908
					}
				}
			}

			// normal control flow
909 910 911 912
			if (!always_fail) {
				current_block = new BasicBlock ();
				last_block.connect (current_block);
			}
913
		}
914 915
	}

Jürg Billeter's avatar
Jürg Billeter committed
916 917 918 919 920 921 922 923
	public override void visit_yield_statement (YieldStatement stmt) {
		if (unreachable (stmt)) {
			return;
		}

		stmt.accept_children (this);
	}

924
	public override void visit_throw_statement (ThrowStatement stmt) {
925 926 927 928 929
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
930
		handle_errors (stmt, true);
931 932
	}

933
	public override void visit_try_statement (TryStatement stmt) {
934 935 936 937
		if (unreachable (stmt)) {
			return;
		}

938
		var before_try_block = current_block;
939 940 941 942 943 944
		var after_try_block = new BasicBlock ();

		BasicBlock finally_block = null;
		if (stmt.finally_body != null) {
			finally_block = new BasicBlock ();
			current_block = finally_block;
945 946 947 948 949

			// trap all forbidden jumps
			var invalid_block = new BasicBlock ();
			jump_stack.add (new JumpTarget.any_target (invalid_block));

950 951
			stmt.finally_body.accept (this);

952
			if (invalid_block.get_predecessors ().size > 0) {
953
				// don't allow finally blocks with e.g. return statements
954
				Report.error (stmt.source_reference, "jump out of finally block not permitted");
955 956 957
				stmt.error = true;
				return;
			}
958
			jump_stack.remove_at (jump_stack.size - 1);
959 960 961 962 963 964 965 966 967

			jump_stack.add (new JumpTarget.finally_clause (finally_block, current_block));
		}

		int finally_jump_stack_size = jump_stack.size;

		var catch_clauses = stmt.get_catch_clauses ();
		for (int i = catch_clauses.size - 1; i >= 0; i--) {
			var catch_clause = catch_clauses[i];
968
			if (catch_clause.error_type != null) {
969 970 971 972 973 974 975
				if (context.profile == Profile.GOBJECT) {
					var error_type = catch_clause.error_type as ErrorType;
					jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, catch_clause.error_type.data_type as ErrorDomain, error_type.error_code, null));
				} else {
					var error_class = catch_clause.error_type.data_type as Class;
					jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, null, null, error_class));
				}
976
			} else {
977
				jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, null, null, null));
978
			}
979 980
		}

981 982
		current_block = before_try_block;

983 984
		stmt.body.accept (this);

985 986 987 988 989 990 991 992 993
		if (current_block != null) {
			if (finally_block != null) {
				current_block.connect (finally_block);
				current_block = finally_block;
			}
			current_block.connect (after_try_block);
		}

		// remove catch clauses from jump stack
994
		List<JumpTarget> catch_stack = new ArrayList<JumpTarget> ();
995 996 997 998 999 1000 1001
		for (int i = jump_stack.size - 1; i >= finally_jump_stack_size; i--) {
			var jump_target = jump_stack[i];
			catch_stack.add (jump_target);
			jump_stack.remove_at (i);
		}

		foreach (JumpTarget jump_target in catch_stack) {
1002 1003

			foreach (JumpTarget prev_target in catch_stack) {
1004
				if (prev_target == jump_target) {
1005
					break;
1006
				}
1007

1008 1009 1010 1011 1012 1013 1014 1015
				if (context.profile == Profile.GOBJECT) {
					if (prev_target.error_domain == jump_target.error_domain &&
					    prev_target.error_code == jump_target.error_code) {
						Report.error (stmt.source_reference, "double catch clause of same error detected");
						stmt.error = true;
						return;
					}
				} else if (prev_target.error_class == jump_target.error_class) {
1016 1017 1018 1019 1020 1021
					Report.error (stmt.source_reference, "double catch clause of same error detected");
					stmt.error = true;
					return;
				}
			}

1022 1023 1024 1025 1026
			if (jump_target.basic_block.get_predecessors ().size == 0) {
				// unreachable
				Report.warning (jump_target.catch_clause.source_reference, "unreachable catch clause detected");
			} else {
				current_block = jump_target.basic_block;
1027
				current_block.add_node (jump_target.catch_clause);
1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
				jump_target.catch_clause.body.accept (this);
				if (current_block != null) {
					if (finally_block != null) {
						current_block.connect (finally_block);
						current_block = finally_block;
					}
					current_block.connect (after_try_block);
				}
			}
		}

		if (finally_block != null) {
			jump_stack.remove_at (jump_stack.size - 1);
		}

		// after try statement
		// reachable?
		if (after_try_block.get_predecessors ().size > 0) {
			current_block = after_try_block;
		} else {
1048
			stmt.after_try_block_reachable = false;
1049 1050 1051
			current_block = null;
			unreachable_reported = false;
		}
1052 1053
	}

1054
	public override void visit_lock_statement (LockStatement stmt) {
1055 1056 1057
		if (unreachable (stmt)) {
			return;
		}
Jiří Zárevúcky's avatar
Jiří Zárevúcky committed
1058
	}
1059

Jiří Zárevúcky's avatar
Jiří Zárevúcky committed
1060 1061 1062 1063
	public override void visit_unlock_statement (UnlockStatement stmt) {
		if (unreachable (stmt)) {
			return;
		}
1064 1065
	}

1066 1067 1068 1069 1070 1071 1072
	public override void visit_expression (Expression expr) {
		// lambda expression is handled separately
		if (!(expr is LambdaExpression)) {
			expr.accept_children (this);
		}
	}

1073 1074
	private bool unreachable (CodeNode node) {
		if (current_block == null) {
1075
			node.unreachable = true;
1076 1077 1078 1079 1080 1081 1082 1083 1084 1085
			if (!unreachable_reported) {
				Report.warning (node.source_reference, "unreachable code detected");
				unreachable_reported = true;
			}
			return true;
		}

		return false;
	}
}