valaflowanalyzer.vala 27.6 KB
Newer Older
1
/* valaflowanalyzer.vala
2
 *
3
 * Copyright (C) 2008-2009  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 28
 *
 * 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;
using Gee;

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

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

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

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

57
		public JumpTarget.error_target (BasicBlock basic_block, CatchClause catch_clause, ErrorDomain? error_domain, ErrorCode? error_code) {
58 59 60 61
			this.basic_block = basic_block;
			this.catch_clause = catch_clause;
			this.error_domain = error_domain;
			this.error_code = error_code;
62
			is_error_target = true;
63 64
		}

65 66 67 68 69 70 71 72
		public JumpTarget.any_target (BasicBlock basic_block) {
			this.basic_block = basic_block;
			is_break_target = true;
			is_continue_target = true;
			is_return_target = true;
			is_error_target = true;
		}

73 74 75
		public JumpTarget.finally_clause (BasicBlock basic_block, BasicBlock last_block) {
			this.basic_block = basic_block;
			this.last_block = last_block;
76
			is_finally_clause = true;
77 78 79
		}
	}

80 81 82
	private CodeContext context;
	private BasicBlock current_block;
	private bool unreachable_reported;
83
	private Gee.List<JumpTarget> jump_stack = new ArrayList<JumpTarget> ();
84

85 86 87 88 89
	Map<Symbol, Gee.List<LocalVariable>> var_map;
	Set<LocalVariable> used_vars;
	Map<LocalVariable, PhiFunction> phi_functions;

	public FlowAnalyzer () {
90 91 92 93 94 95 96
	}

	/**
	 * Build control flow graph in the specified context.
	 *
	 * @param context a code context
	 */
97
	public void analyze (CodeContext context) {
98 99 100 101 102
		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) {
103
			if (!file.external_package) {
104 105 106 107 108
				file.accept (this);
			}
		}
	}

109
	public override void visit_source_file (SourceFile source_file) {
110 111 112
		source_file.accept_children (this);
	}

113
	public override void visit_class (Class cl) {
114 115 116
		cl.accept_children (this);
	}

117
	public override void visit_struct (Struct st) {
118 119 120
		st.accept_children (this);
	}

121
	public override void visit_interface (Interface iface) {
122 123 124
		iface.accept_children (this);
	}

125
	public override void visit_enum (Enum en) {
126 127 128
		en.accept_children (this);
	}

129 130 131 132
	public override void visit_error_domain (ErrorDomain ed) {
		ed.accept_children (this);
	}

133
	public override void visit_field (Field f) {
134
		if (f.is_internal_symbol () && !f.used) {
135 136 137 138
			Report.warning (f.source_reference, "field `%s' never used".printf (f.get_full_name ()));
		}
	}

139
	public override void visit_method (Method m) {
140 141 142
		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)) {
143 144 145
			Report.warning (m.source_reference, "method `%s' never used".printf (m.get_full_name ()));
		}

146 147 148 149 150 151 152 153 154 155
		if (m.body == null) {
			return;
		}

		m.entry_block = new BasicBlock.entry ();
		m.exit_block = new BasicBlock.exit ();

		current_block = new BasicBlock ();
		m.entry_block.connect (current_block);

156 157
		jump_stack.add (new JumpTarget.return_target (m.exit_block));

158 159
		m.accept_children (this);

160 161
		jump_stack.remove_at (jump_stack.size - 1);

162 163 164 165 166 167 168 169 170 171
		if (current_block != null) {
			// end of method body reachable

			if (!(m.return_type is VoidType)) {
				Report.error (m.source_reference, "missing return statement at end of method body");
				m.error = true;
			}

			current_block.connect (m.exit_block);
		}
172

173 174 175 176
		build_dominator_tree (m.entry_block);
		build_dominator_frontier (m.entry_block);
		insert_phi_functions (m.entry_block);
		check_variables (m.entry_block);
177 178
	}

179
	Gee.List<BasicBlock> get_depth_first_list (BasicBlock entry_block) {
180
		var list = new ArrayList<BasicBlock> ();
181
		depth_first_traverse (entry_block, list);
182 183 184 185 186 187 188 189 190 191 192 193 194
		return list;
	}

	void depth_first_traverse (BasicBlock current, Gee.List<BasicBlock> list) {
		if (current in list) {
			return;
		}
		list.add (current);
		foreach (BasicBlock succ in current.get_successors ()) {
			depth_first_traverse (succ, list);
		}
	}

195
	void build_dominator_tree (BasicBlock entry_block) {
196 197
		// set dom(n) = {E,1,2...,N,X} forall n
		var dom = new HashMap<BasicBlock, Set<BasicBlock>> ();
198
		var block_list = get_depth_first_list (entry_block);
199 200 201 202 203 204 205 206 207 208
		foreach (BasicBlock block in block_list) {
			var block_set = new HashSet<BasicBlock> ();
			foreach (BasicBlock b in block_list) {
				block_set.add (b);
			}
			dom.set (block, block_set);
		}

		// set dom(E) = {E}
		var entry_dom_set = new HashSet<BasicBlock> ();
209 210
		entry_dom_set.add (entry_block);
		dom.set (entry_block, entry_dom_set);
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257

		bool changes = true;
		while (changes) {
			changes = false;
			foreach (BasicBlock block in block_list) {
				// intersect dom(pred) forall pred: pred = predecessor(s)
				var dom_set = new HashSet<BasicBlock> ();
				bool first = true;
				foreach (BasicBlock pred in block.get_predecessors ()) {
					var pred_dom_set = dom.get (pred);
					if (first) {
						foreach (BasicBlock dom_block in pred_dom_set) {
							dom_set.add (dom_block);
						}
						first = false;
					} else {
						var remove_queue = new ArrayList<BasicBlock> ();
						foreach (BasicBlock dom_block in dom_set) {
							if (!(dom_block in pred_dom_set)) {
								remove_queue.add (dom_block);
							}
						}
						foreach (BasicBlock dom_block in remove_queue) {
							dom_set.remove (dom_block);
						}
					}
				}
				// unite with s
				dom_set.add (block);

				// check for changes
				if (dom.get (block).size != dom_set.size) {
					changes = true;
				} else {
					foreach (BasicBlock dom_block in dom.get (block)) {
						if (!(dom_block in dom_set)) {
							changes = true;
						}
					}
				}
				// update set in map
				dom.set (block, dom_set);
			}
		}

		// build tree
		foreach (BasicBlock block in block_list) {
258
			if (block == entry_block) {
259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
				continue;
			}

			BasicBlock immediate_dominator = null;
			foreach (BasicBlock dominator in dom.get (block)) {
				if (dominator == block) {
					continue;
				}

				if (immediate_dominator == null) {
					immediate_dominator = dominator;
				} else {
					// if immediate_dominator dominates dominator,
					// update immediate_dominator
					if (immediate_dominator in dom.get (dominator)) {
						immediate_dominator = dominator;
					}
				}
			}

			immediate_dominator.add_child (block);
		}
	}

283 284
	void build_dominator_frontier (BasicBlock entry_block) {
		var block_list = get_depth_first_list (entry_block);
285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
		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);
					}
				}
			}
		}
	}

306
	Map<LocalVariable, Set<BasicBlock>> get_assignment_map (BasicBlock entry_block) {
307
		var map = new HashMap<LocalVariable, Set<BasicBlock>> ();
308
		foreach (BasicBlock block in get_depth_first_list (entry_block)) {
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
			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;
	}

326 327
	void insert_phi_functions (BasicBlock entry_block) {
		var assign = get_assignment_map (entry_block);
328 329 330 331 332 333

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

		var added = new HashMap<BasicBlock, int> ();
		var phi = new HashMap<BasicBlock, int> ();
334
		foreach (BasicBlock block in get_depth_first_list (entry_block)) {
335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363
			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);
						}
					}
				}
			}
		}
	}

364
	void check_variables (BasicBlock entry_block) {
365 366 367 368
		var_map = new HashMap<Symbol, Gee.List<LocalVariable>>();
		used_vars = new HashSet<LocalVariable> ();
		phi_functions = new HashMap<LocalVariable, PhiFunction> ();

369
		check_block_variables (entry_block);
370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396

		// 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);
					}
				}
			}
		}
	}

397
	void check_block_variables (BasicBlock block) {
398
		foreach (PhiFunction phi in block.get_phi_functions ()) {
399
			LocalVariable versioned_var = process_assignment (var_map, phi.original_variable);
400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424

			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) {
425
				process_assignment (var_map, local);
426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446
			}
		}

		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 ()) {
447
			check_block_variables (child);
448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464
		}

		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);
			}
		}
	}

465
	LocalVariable process_assignment (Map<Symbol, Gee.List<LocalVariable>> var_map, LocalVariable var_symbol) {
466 467 468 469 470 471 472 473
		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;
474 475
	}

476 477 478 479
	public override void visit_creation_method (CreationMethod m) {
		visit_method (m);
	}

480
	public override void visit_property (Property prop) {
481 482 483
		prop.accept_children (this);
	}

484
	public override void visit_property_accessor (PropertyAccessor acc) {
485 486 487 488 489 490 491 492 493
		if (acc.body == null) {
			return;
		}

		acc.entry_block = new BasicBlock.entry ();
		acc.exit_block = new BasicBlock.exit ();

		current_block = new BasicBlock ();
		acc.entry_block.connect (current_block);
494

495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
		jump_stack.add (new JumpTarget.return_target (acc.exit_block));

		acc.accept_children (this);

		jump_stack.remove_at (jump_stack.size - 1);

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

			if (acc.readable) {
				Report.error (acc.source_reference, "missing return statement at end of property getter body");
				acc.error = true;
			}

			current_block.connect (acc.exit_block);
		}
511 512 513 514 515

		build_dominator_tree (acc.entry_block);
		build_dominator_frontier (acc.entry_block);
		insert_phi_functions (acc.entry_block);
		check_variables (acc.entry_block);
516 517
	}

518
	public override void visit_block (Block b) {
519 520 521
		b.accept_children (this);
	}

522
	public override void visit_declaration_statement (DeclarationStatement stmt) {
523 524 525 526
		if (unreachable (stmt)) {
			return;
		}

527 528 529 530
		if (!stmt.declaration.used) {
			Report.warning (stmt.declaration.source_reference, "local variable `%s' declared but never used".printf (stmt.declaration.name));
		}

531
		current_block.add_node (stmt);
532

533 534 535
		var local = stmt.declaration as LocalVariable;
		if (local != null && local.initializer != null) {
			handle_errors (local.initializer);
536
		}
537 538
	}

539
	public override void visit_expression_statement (ExpressionStatement stmt) {
540 541 542 543 544
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
545 546

		handle_errors (stmt);
547

548 549
		if (stmt.expression is MethodCall) {
			var expr = (MethodCall) stmt.expression;
550
			var ma = expr.call as MemberAccess;
551
			if (ma != null && ma.symbol_reference != null && ma.symbol_reference.get_attribute ("NoReturn") != null) {
552 553 554 555 556
				current_block = null;
				unreachable_reported = false;
				return;
			}
		}
557 558
	}

559 560 561 562 563 564 565 566 567 568
	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);
	}

569
	public override void visit_if_statement (IfStatement stmt) {
570 571 572 573 574 575 576
		if (unreachable (stmt)) {
			return;
		}

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

577 578
		handle_errors (stmt.condition);

579 580
		// true block
		var last_block = current_block;
581 582 583 584 585 586 587
		if (always_false (stmt.condition)) {
			current_block = null;
			unreachable_reported = false;
		} else {
			current_block = new BasicBlock ();
			last_block.connect (current_block);
		}
588 589 590 591
		stmt.true_statement.accept (this);

		// false block
		var last_true_block = current_block;
592 593 594 595 596 597 598
		if (always_true (stmt.condition)) {
			current_block = null;
			unreachable_reported = false;
		} else {
			current_block = new BasicBlock ();
			last_block.connect (current_block);
		}
599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616
		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);
			}
		}
	}

617
	public override void visit_switch_statement (SwitchStatement stmt) {
618 619 620 621 622
		if (unreachable (stmt)) {
			return;
		}

		var after_switch_block = new BasicBlock ();
623
		jump_stack.add (new JumpTarget.break_target (after_switch_block));
624 625 626 627 628

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

629 630
		handle_errors (stmt.expression);

631 632 633 634 635
		bool has_default_label = false;

		foreach (SwitchSection section in stmt.get_sections ()) {
			current_block = new BasicBlock ();
			condition_block.connect (current_block);
636 637
			foreach (Statement section_stmt in section.get_statements ()) {
				section_stmt.accept (this);
638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654
			}

			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);
			}
		}

655 656 657 658
		if (!has_default_label) {
			condition_block.connect (after_switch_block);
		}

659 660
		// after switch
		// reachable?
661
		if (after_switch_block.get_predecessors ().size > 0) {
662 663 664 665 666 667
			current_block = after_switch_block;
		} else {
			current_block = null;
			unreachable_reported = false;
		}

668
		jump_stack.remove_at (jump_stack.size - 1);
669 670
	}

671
	public override void visit_loop (Loop stmt) {
672 673 674 675
		if (unreachable (stmt)) {
			return;
		}

676 677
		var loop_block = new BasicBlock ();
		jump_stack.add (new JumpTarget.continue_target (loop_block));
678
		var after_loop_block = new BasicBlock ();
679
		jump_stack.add (new JumpTarget.break_target (after_loop_block));
680

681
		// loop block
682
		var last_block = current_block;
683 684
		last_block.connect (loop_block);
		current_block = loop_block;
685 686 687 688

		stmt.body.accept (this);
		// end of loop block reachable?
		if (current_block != null) {
689
			current_block.connect (loop_block);
690 691 692
		}

		// after loop
693
		// reachable?
694 695
		if (after_loop_block.get_predecessors ().size == 0) {
			// after loop block not reachable
696 697 698
			current_block = null;
			unreachable_reported = false;
		} else {
699
			// after loop block reachable
700 701
			current_block = after_loop_block;
		}
702

703 704
		jump_stack.remove_at (jump_stack.size - 1);
		jump_stack.remove_at (jump_stack.size - 1);
705 706
	}

707
	public override void visit_foreach_statement (ForeachStatement stmt) {
708 709 710 711
		if (unreachable (stmt)) {
			return;
		}

712 713 714 715
		// collection
		current_block.add_node (stmt.collection);
		handle_errors (stmt.collection);

716
		var loop_block = new BasicBlock ();
717
		jump_stack.add (new JumpTarget.continue_target (loop_block));
718
		var after_loop_block = new BasicBlock ();
719
		jump_stack.add (new JumpTarget.break_target (after_loop_block));
720 721 722 723 724

		// loop block
		var last_block = current_block;
		last_block.connect (loop_block);
		current_block = loop_block;
725
		current_block.add_node (stmt);
726 727 728 729 730 731 732 733 734 735 736 737
		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;

738 739
		jump_stack.remove_at (jump_stack.size - 1);
		jump_stack.remove_at (jump_stack.size - 1);
740 741
	}

742
	public override void visit_break_statement (BreakStatement stmt) {
743 744 745 746 747
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
748 749 750

		for (int i = jump_stack.size - 1; i >= 0; i--) {
			var jump_target = jump_stack[i];
751
			if (jump_target.is_break_target) {
752 753 754 755
				current_block.connect (jump_target.basic_block);
				current_block = null;
				unreachable_reported = false;
				return;
756
			} else if (jump_target.is_finally_clause) {
757 758 759 760 761 762 763
				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;
764 765
	}

766
	public override void visit_continue_statement (ContinueStatement stmt) {
767 768 769 770 771
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
772 773 774

		for (int i = jump_stack.size - 1; i >= 0; i--) {
			var jump_target = jump_stack[i];
775
			if (jump_target.is_continue_target) {
776 777 778 779
				current_block.connect (jump_target.basic_block);
				current_block = null;
				unreachable_reported = false;
				return;
780
			} else if (jump_target.is_finally_clause) {
781 782 783 784 785 786 787
				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;
788 789
	}

790
	public override void visit_return_statement (ReturnStatement stmt) {
791 792 793 794 795
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
796

797 798 799 800
		if (stmt.return_expression != null) {
			handle_errors (stmt.return_expression);
		}

801 802
		for (int i = jump_stack.size - 1; i >= 0; i--) {
			var jump_target = jump_stack[i];
803
			if (jump_target.is_return_target) {
804 805 806 807
				current_block.connect (jump_target.basic_block);
				current_block = null;
				unreachable_reported = false;
				return;
808
			} else if (jump_target.is_finally_clause) {
809 810 811 812 813 814 815 816 817
				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;
	}

818
	private void handle_errors (CodeNode node, bool always_fail = false) {
819 820 821 822
		if (node.tree_can_fail) {
			var last_block = current_block;

			// exceptional control flow
823 824 825 826 827 828 829 830 831
			foreach (DataType error_data_type in node.get_error_types()) {
				var error_type = error_data_type as ErrorType;
				current_block = last_block;
				unreachable_reported = true;

				for (int i = jump_stack.size - 1; i >= 0; i--) {
					var jump_target = jump_stack[i];
					if (jump_target.is_return_target) {
						current_block.connect (jump_target.basic_block);
832 833 834
						current_block = null;
						unreachable_reported = false;
						break;
835 836 837 838 839 840 841 842 843 844 845 846 847
					} else if (jump_target.is_error_target) {
						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))) {
							current_block.connect (jump_target.basic_block);
							current_block = null;
							unreachable_reported = false;
							break;
						}
					} else if (jump_target.is_finally_clause) {
						current_block.connect (jump_target.basic_block);
						current_block = jump_target.last_block;
848 849 850 851 852
					}
				}
			}

			// normal control flow
853 854 855 856
			if (!always_fail) {
				current_block = new BasicBlock ();
				last_block.connect (current_block);
			}
857
		}
858 859
	}

Jürg Billeter's avatar
Jürg Billeter committed
860 861 862 863 864 865 866 867
	public override void visit_yield_statement (YieldStatement stmt) {
		if (unreachable (stmt)) {
			return;
		}

		stmt.accept_children (this);
	}

868
	public override void visit_throw_statement (ThrowStatement stmt) {
869 870 871 872 873
		if (unreachable (stmt)) {
			return;
		}

		current_block.add_node (stmt);
874
		handle_errors (stmt, true);
875 876
	}

877
	public override void visit_try_statement (TryStatement stmt) {
878 879 880 881
		if (unreachable (stmt)) {
			return;
		}

882
		var before_try_block = current_block;
883 884 885 886 887 888
		var after_try_block = new BasicBlock ();

		BasicBlock finally_block = null;
		if (stmt.finally_body != null) {
			finally_block = new BasicBlock ();
			current_block = finally_block;
889 890 891 892 893

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

894 895
			stmt.finally_body.accept (this);

896
			if (invalid_block.get_predecessors ().size > 0) {
897
				// don't allow finally blocks with e.g. return statements
898
				Report.error (stmt.source_reference, "jump out of finally block not permitted");
899 900 901
				stmt.error = true;
				return;
			}
902
			jump_stack.remove_at (jump_stack.size - 1);
903 904 905 906 907 908 909 910 911

			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];
912
			if (catch_clause.error_type != null) {
913 914
				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));
915 916 917
			} else {
				jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, null, null));
			}
918 919
		}

920 921
		current_block = before_try_block;

922 923
		stmt.body.accept (this);

924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940
		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
		Gee.List<JumpTarget> catch_stack = new ArrayList<JumpTarget> ();
		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) {
941 942

			foreach (JumpTarget prev_target in catch_stack) {
943
				if (prev_target == jump_target) {
944
					break;
945
				}
946 947 948 949 950 951 952 953 954

				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;
				}
			}

955 956 957 958 959
			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;
960
				current_block.add_node (jump_target.catch_clause);
961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983
				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 {
			current_block = null;
			unreachable_reported = false;
		}
984 985
	}

986
	public override void visit_lock_statement (LockStatement stmt) {
987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005
		if (unreachable (stmt)) {
			return;
		}

		stmt.body.accept (this);
	}

	private bool unreachable (CodeNode node) {
		if (current_block == null) {
			if (!unreachable_reported) {
				Report.warning (node.source_reference, "unreachable code detected");
				unreachable_reported = true;
			}
			return true;
		}

		return false;
	}
}