vala/valaflowanalyzer.vala

   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 public class Vala.FlowAnalyzer : CodeVisitor {
  29         private class JumpTarget {
  30                 public bool is_break_target { get; set; }
  31                 public bool is_continue_target { get; set; }
  32                 public bool is_return_target { get; set; }
  33                 public bool is_exit_target { get; set; }
  34                 public bool is_error_target { get; set; }
  35                 public ErrorDomain? error_domain { get; set; }
  36                 public ErrorCode? error_code { get; set; }
  37                 public Class? error_class { get; set; }
  38                 public bool is_finally_clause { get; set; }
  39                 public BasicBlock basic_block { get; set; }
  40                 public BasicBlock? last_block { get; set; }
  41                 public CatchClause? catch_clause { get; set; }
  42
  43                 public JumpTarget.break_target (BasicBlock basic_block) {
  44                         this.basic_block = basic_block;
  45                         is_break_target = true;
  46                 }
  47
  48                 public JumpTarget.continue_target (BasicBlock basic_block) {
  49                         this.basic_block = basic_block;
  50                         is_continue_target = true;
  51                 }
  52
  53                 public JumpTarget.return_target (BasicBlock basic_block) {
  54                         this.basic_block = basic_block;
  55                         is_return_target = true;
  56                 }
  57
  58                 public JumpTarget.exit_target (BasicBlock basic_block) {
  59                         this.basic_block = basic_block;
  60                         is_exit_target = true;
  61                 }
  62
  63                 public JumpTarget.error_target (BasicBlock basic_block, CatchClause catch_clause, ErrorDomain? error_domain, ErrorCode? error_code, Class? error_class) {
  64                         this.basic_block = basic_block;
  65                         this.catch_clause = catch_clause;
  66                         this.error_domain = error_domain;
  67                         this.error_code = error_code;
  68                         this.error_class = error_class;
  69                         is_error_target = true;
  70                 }
  71
  72                 public JumpTarget.any_target (BasicBlock basic_block) {
  73                         this.basic_block = basic_block;
  74                         is_break_target = true;
  75                         is_continue_target = true;
  76                         is_return_target = true;
  77                         is_exit_target = true;
  78                         is_error_target = true;
  79                 }
  80
  81                 public JumpTarget.finally_clause (BasicBlock basic_block, BasicBlock last_block) {
  82                         this.basic_block = basic_block;
  83                         this.last_block = last_block;
  84                         is_finally_clause = true;
  85                 }
  86         }
  87
  88         private CodeContext context;
  89         private BasicBlock current_block;
  90         private bool unreachable_reported;
  91         private List<JumpTarget> jump_stack = new ArrayList<JumpTarget> ();
  92
  93         Map<Symbol, List<LocalVariable>> var_map;
  94         Set<LocalVariable> used_vars;
  95         Map<LocalVariable, PhiFunction> phi_functions;
  96
  97         public FlowAnalyzer () {
  98         }
  99
 100         /**
 101          * Build control flow graph in the specified context.
 102          *
 103          * @param context a code context
 104          */
 105         public void analyze (CodeContext context) {
 106                 this.context = context;
 107
 108                 /* we're only interested in non-pkg source files */
 109                 var source_files = context.get_source_files ();
 110                 foreach (SourceFile file in source_files) {
 111                         if (file.file_type == SourceFileType.SOURCE) {
 112                                 file.accept (this);
 113                         }
 114                 }
 115         }
 116
 117         public override void visit_source_file (SourceFile source_file) {
 118                 source_file.accept_children (this);
 119         }
 120
 121         public override void visit_class (Class cl) {
 122                 cl.accept_children (this);
 123         }
 124
 125         public override void visit_struct (Struct st) {
 126                 st.accept_children (this);
 127         }
 128
 129         public override void visit_interface (Interface iface) {
 130                 iface.accept_children (this);
 131         }
 132
 133         public override void visit_enum (Enum en) {
 134                 en.accept_children (this);
 135         }
 136
 137         public override void visit_error_domain (ErrorDomain ed) {
 138                 ed.accept_children (this);
 139         }
 140
 141         public override void visit_field (Field f) {
 142                 if (f.is_internal_symbol () && !f.used) {
 143                         if (!f.is_private_symbol () && context.internal_header_filename != null) {
 144                                 // do not warn if internal member may be used outside this compilation unit
 145                         } else {
 146                                 Report.warning (f.source_reference, "field `%s' never used".printf (f.get_full_name ()));
 147                         }
 148                 }
 149         }
 150
 151         public override void visit_lambda_expression (LambdaExpression le) {
 152                 var old_current_block = current_block;
 153                 var old_unreachable_reported = unreachable_reported;
 154                 var old_jump_stack = jump_stack;
 155                 mark_unreachable ();
 156                 jump_stack = new ArrayList<JumpTarget> ();
 157
 158                 le.accept_children (this);
 159
 160                 current_block = old_current_block;
 161                 unreachable_reported = old_unreachable_reported;
 162                 jump_stack = old_jump_stack;
 163         }
 164
 165         public override void visit_method (Method m) {
 166                 if (m.is_internal_symbol () && !m.used && !m.entry_point
 167                     && !m.overrides && (m.base_interface_method == null || m.base_interface_method == m)
 168                     && !(m is CreationMethod)) {
 169                         if (!m.is_private_symbol () && context.internal_header_filename != null) {
 170                                 // do not warn if internal member may be used outside this compilation unit
 171                         } else {
 172                                 Report.warning (m.source_reference, "method `%s' never used".printf (m.get_full_name ()));
 173                         }
 174                 }
 175
 176                 visit_subroutine (m);
 177         }
 178
 179         public override void visit_signal (Signal sig) {
 180                 if (sig.default_handler != null) {
 181                         visit_subroutine (sig.default_handler);
 182                 }
 183         }
 184
 185         void visit_subroutine (Subroutine m) {
 186                 if (m.body == null) {
 187                         return;
 188                 }
 189
 190                 m.entry_block = new BasicBlock.entry ();
 191                 m.return_block = new BasicBlock ();
 192                 m.exit_block = new BasicBlock.exit ();
 193
 194                 m.return_block.connect (m.exit_block);
 195
 196                 if (context.profile == Profile.DOVA && m.result_var != null) {
 197                         // ensure result is defined at end of method
 198                         var result_ma = new MemberAccess.simple ("result", m.source_reference);
 199                         result_ma.symbol_reference = m.result_var;
 200                         m.return_block.add_node (result_ma);
 201                 }
 202
 203                 current_block = new BasicBlock ();
 204                 m.entry_block.connect (current_block);
 205                 current_block.add_node (m);
 206
 207                 jump_stack.add (new JumpTarget.return_target (m.return_block));
 208                 jump_stack.add (new JumpTarget.exit_target (m.exit_block));
 209
 210                 m.accept_children (this);
 211
 212                 jump_stack.remove_at (jump_stack.size - 1);
 213
 214                 if (current_block != null) {
 215                         // end of method body reachable
 216
 217                         if (context.profile != Profile.DOVA && m.has_result) {
 218                                 Report.error (m.source_reference, "missing return statement at end of subroutine body");
 219                                 m.error = true;
 220                         }
 221
 222                         current_block.connect (m.return_block);
 223                 }
 224
 225                 analyze_body (m.entry_block);
 226         }
 227
 228         void analyze_body (BasicBlock entry_block) {
 229                 var block_list = get_depth_first_list (entry_block);
 230
 231                 build_dominator_tree (block_list, entry_block);
 232                 build_dominator_frontier (block_list, entry_block);
 233                 insert_phi_functions (block_list, entry_block);
 234                 check_variables (entry_block);
 235         }
 236
 237         // generates reverse postorder list
 238         List<BasicBlock> get_depth_first_list (BasicBlock entry_block) {
 239                 var list = new ArrayList<BasicBlock> ();
 240                 depth_first_traverse (entry_block, list);
 241                 return list;
 242         }
 243
 244         void depth_first_traverse (BasicBlock current, List<BasicBlock> list) {
 245                 if (current.postorder_visited) {
 246                         return;
 247                 }
 248                 current.postorder_visited = true;
 249                 foreach (BasicBlock succ in current.get_successors ()) {
 250                         depth_first_traverse (succ, list);
 251                 }
 252                 current.postorder_number = list.size;
 253                 list.insert (0, current);
 254         }
 255
 256         void build_dominator_tree (List<BasicBlock> block_list, BasicBlock entry_block) {
 257                 // immediate dominators
 258                 var idoms = new BasicBlock[block_list.size];
 259                 idoms[entry_block.postorder_number] = entry_block;
 260
 261                 bool changed = true;
 262                 while (changed) {
 263                         changed = false;
 264                         foreach (BasicBlock block in block_list) {
 265                                 if (block == entry_block) {
 266                                         continue;
 267                                 }
 268
 269                                 // new immediate dominator
 270                                 BasicBlock new_idom = null;
 271                                 bool first = true;
 272                                 foreach (BasicBlock pred in block.get_predecessors ()) {
 273                                         if (idoms[pred.postorder_number] != null) {
 274                                                 if (first) {
 275                                                         new_idom = pred;
 276                                                         first = false;
 277                                                 } else {
 278                                                         new_idom = intersect (idoms, pred, new_idom);
 279                                                 }
 280                                         }
 281                                 }
 282                                 if (idoms[block.postorder_number] != new_idom) {
 283                                         idoms[block.postorder_number] = new_idom;
 284                                         changed = true;
 285                                 }
 286                         }
 287                 }
 288
 289                 // build tree
 290                 foreach (BasicBlock block in block_list) {
 291                         if (block == entry_block) {
 292                                 continue;
 293                         }
 294
 295                         idoms[block.postorder_number].add_child (block);
 296                 }
 297         }
 298
 299         BasicBlock intersect (BasicBlock[] idoms, BasicBlock b1, BasicBlock b2) {
 300                 while (b1 != b2) {
 301                         while (b1.postorder_number < b2.postorder_number) {
 302                                 b1 = idoms[b2.postorder_number];
 303                         }
 304                         while (b2.postorder_number < b1.postorder_number) {
 305                                 b2 = idoms[b2.postorder_number];
 306                         }
 307                 }
 308                 return b1;
 309         }
 310
 311         void build_dominator_frontier (List<BasicBlock> block_list, BasicBlock entry_block) {
 312                 for (int i = block_list.size - 1; i >= 0; i--) {
 313                         var block = block_list[i];
 314
 315                         foreach (BasicBlock succ in block.get_successors ()) {
 316                                 // if idom(succ) != block
 317                                 if (succ.parent != block) {
 318                                         block.add_dominator_frontier (succ);
 319                                 }
 320                         }
 321
 322                         foreach (BasicBlock child in block.get_children ()) {
 323                                 foreach (BasicBlock child_frontier in child.get_dominator_frontier ()) {
 324                                         // if idom(child_frontier) != block
 325                                         if (child_frontier.parent != block) {
 326                                                 block.add_dominator_frontier (child_frontier);
 327                                         }
 328                                 }
 329                         }
 330                 }
 331         }
 332
 333         Map<LocalVariable, Set<BasicBlock>> get_assignment_map (List<BasicBlock> block_list, BasicBlock entry_block) {
 334                 var map = new HashMap<LocalVariable, Set<BasicBlock>> ();
 335                 foreach (BasicBlock block in block_list) {
 336                         var defined_variables = new ArrayList<LocalVariable> ();
 337                         foreach (CodeNode node in block.get_nodes ()) {
 338                                 node.get_defined_variables (defined_variables);
 339                         }
 340
 341                         foreach (LocalVariable local in defined_variables) {
 342                                 var block_set = map.get (local);
 343                                 if (block_set == null) {
 344                                         block_set = new HashSet<BasicBlock> ();
 345                                         map.set (local, block_set);
 346                                 }
 347                                 block_set.add (block);
 348                         }
 349                 }
 350                 return map;
 351         }
 352
 353         void insert_phi_functions (List<BasicBlock> block_list, BasicBlock entry_block) {
 354                 var assign = get_assignment_map (block_list, entry_block);
 355
 356                 int counter = 0;
 357                 var work_list = new ArrayList<BasicBlock> ();
 358
 359                 var added = new HashMap<BasicBlock, int> ();
 360                 var phi = new HashMap<BasicBlock, int> ();
 361                 foreach (BasicBlock block in block_list) {
 362                         added.set (block, 0);
 363                         phi.set (block, 0);
 364                 }
 365
 366                 foreach (LocalVariable local in assign.get_keys ()) {
 367                         counter++;
 368                         foreach (BasicBlock block in assign.get (local)) {
 369                                 work_list.add (block);
 370                                 added.set (block, counter);
 371                         }
 372                         while (work_list.size > 0) {
 373                                 BasicBlock block = work_list.get (0);
 374                                 work_list.remove_at (0);
 375                                 foreach (BasicBlock frontier in block.get_dominator_frontier ()) {
 376                                         int blockPhi = phi.get (frontier);
 377                                         if (blockPhi < counter) {
 378                                                 frontier.add_phi_function (new PhiFunction (local, frontier.get_predecessors ().size));
 379                                                 phi.set (frontier, counter);
 380                                                 int block_added = added.get (frontier);
 381                                                 if (block_added < counter) {
 382                                                         added.set (frontier, counter);
 383                                                         work_list.add (frontier);
 384                                                 }
 385                                         }
 386                                 }
 387                         }
 388                 }
 389         }
 390
 391         void check_variables (BasicBlock entry_block) {
 392                 var_map = new HashMap<Symbol, List<LocalVariable>>();
 393                 used_vars = new HashSet<LocalVariable> ();
 394                 phi_functions = new HashMap<LocalVariable, PhiFunction> ();
 395
 396                 check_block_variables (entry_block);
 397
 398                 // check for variables used before initialization
 399                 var used_vars_queue = new ArrayList<LocalVariable> ();
 400                 foreach (LocalVariable local in used_vars) {
 401                         used_vars_queue.add (local);
 402                 }
 403                 while (used_vars_queue.size > 0) {
 404                         LocalVariable used_var = used_vars_queue[0];
 405                         used_vars_queue.remove_at (0);
 406
 407                         PhiFunction phi = phi_functions.get (used_var);
 408                         if (phi != null) {
 409                                 foreach (LocalVariable local in phi.operands) {
 410                                         if (local == null) {
 411                                                 Report.error (used_var.source_reference, "use of possibly unassigned local variable `%s'".printf (used_var.name));
 412                                                 continue;
 413                                         }
 414                                         if (!(local in used_vars)) {
 415                                                 local.source_reference = used_var.source_reference;
 416                                                 used_vars.add (local);
 417                                                 used_vars_queue.add (local);
 418                                         }
 419                                 }
 420                         }
 421                 }
 422         }
 423
 424         void check_block_variables (BasicBlock block) {
 425                 foreach (PhiFunction phi in block.get_phi_functions ()) {
 426                         LocalVariable versioned_var = process_assignment (var_map, phi.original_variable);
 427
 428                         phi_functions.set (versioned_var, phi);
 429                 }
 430
 431                 foreach (CodeNode node in block.get_nodes ()) {
 432                         var used_variables = new ArrayList<LocalVariable> ();
 433                         node.get_used_variables (used_variables);
 434
 435                         foreach (LocalVariable var_symbol in used_variables) {
 436                                 var variable_stack = var_map.get (var_symbol);
 437                                 if (variable_stack == null || variable_stack.size == 0) {
 438                                         Report.error (node.source_reference, "use of possibly unassigned local variable `%s'".printf (var_symbol.name));
 439                                         continue;
 440                                 }
 441                                 var versioned_local = variable_stack.get (variable_stack.size - 1);
 442                                 if (!(versioned_local in used_vars)) {
 443                                         versioned_local.source_reference = node.source_reference;
 444                                 }
 445                                 used_vars.add (versioned_local);
 446                         }
 447
 448                         var defined_variables = new ArrayList<LocalVariable> ();
 449                         node.get_defined_variables (defined_variables);
 450
 451                         foreach (LocalVariable local in defined_variables) {
 452                                 process_assignment (var_map, local);
 453                         }
 454                 }
 455
 456                 foreach (BasicBlock succ in block.get_successors ()) {
 457                         int j = 0;
 458                         foreach (BasicBlock pred in succ.get_predecessors ()) {
 459                                 if (pred == block) {
 460                                         break;
 461                                 }
 462                                 j++;
 463                         }
 464
 465                         foreach (PhiFunction phi in succ.get_phi_functions ()) {
 466                                 var variable_stack = var_map.get (phi.original_variable);
 467                                 if (variable_stack != null && variable_stack.size > 0) {
 468                                         phi.operands.set (j, variable_stack.get (variable_stack.size - 1));
 469                                 }
 470                         }
 471                 }
 472
 473                 foreach (BasicBlock child in block.get_children ()) {
 474                         check_block_variables (child);
 475                 }
 476
 477                 foreach (PhiFunction phi in block.get_phi_functions ()) {
 478                         var variable_stack = var_map.get (phi.original_variable);
 479                         variable_stack.remove_at (variable_stack.size - 1);
 480                 }
 481                 foreach (CodeNode node in block.get_nodes ()) {
 482                         var defined_variables = new ArrayList<LocalVariable> ();
 483                         node.get_defined_variables (defined_variables);
 484
 485                         foreach (LocalVariable local in defined_variables) {
 486                                 var variable_stack = var_map.get (local);
 487                                 variable_stack.remove_at (variable_stack.size - 1);
 488                         }
 489                 }
 490         }
 491
 492         LocalVariable process_assignment (Map<Symbol, List<LocalVariable>> var_map, LocalVariable var_symbol) {
 493                 var variable_stack = var_map.get (var_symbol);
 494                 if (variable_stack == null) {
 495                         variable_stack = new ArrayList<LocalVariable> ();
 496                         var_map.set (var_symbol, variable_stack);
 497                 }
 498                 LocalVariable versioned_var = new LocalVariable (var_symbol.variable_type, var_symbol.name, null, var_symbol.source_reference);
 499                 variable_stack.add (versioned_var);
 500                 return versioned_var;
 501         }
 502
 503         public override void visit_creation_method (CreationMethod m) {
 504                 visit_method (m);
 505         }
 506
 507         public override void visit_property (Property prop) {
 508                 prop.accept_children (this);
 509         }
 510
 511         public override void visit_property_accessor (PropertyAccessor acc) {
 512                 visit_subroutine (acc);
 513         }
 514
 515         public override void visit_block (Block b) {
 516                 b.accept_children (this);
 517         }
 518
 519         public override void visit_declaration_statement (DeclarationStatement stmt) {
 520                 if (unreachable (stmt)) {
 521                         stmt.declaration.unreachable = true;
 522                         return;
 523                 }
 524
 525                 if (!stmt.declaration.used) {
 526                         Report.warning (stmt.declaration.source_reference, "local variable `%s' declared but never used".printf (stmt.declaration.name));
 527                 }
 528
 529                 current_block.add_node (stmt);
 530
 531                 var local = stmt.declaration as LocalVariable;
 532                 if (local != null && local.initializer != null) {
 533                         handle_errors (local.initializer);
 534                 }
 535         }
 536
 537         public override void visit_expression_statement (ExpressionStatement stmt) {
 538                 stmt.accept_children (this);
 539
 540                 if (unreachable (stmt)) {
 541                         return;
 542                 }
 543
 544                 current_block.add_node (stmt);
 545
 546                 handle_errors (stmt);
 547
 548                 if (stmt.expression is MethodCall) {
 549                         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                                 mark_unreachable ();
 553                                 return;
 554                         }
 555                 }
 556         }
 557
 558         bool always_true (Expression condition) {
 559                 var literal = condition as BooleanLiteral;
 560                 return (literal != null && literal.value);
 561         }
 562
 563         bool always_false (Expression condition) {
 564                 var literal = condition as BooleanLiteral;
 565                 return (literal != null && !literal.value);
 566         }
 567
 568         public override void visit_if_statement (IfStatement stmt) {
 569                 if (unreachable (stmt)) {
 570                         return;
 571                 }
 572
 573                 // condition
 574                 current_block.add_node (stmt.condition);
 575
 576                 handle_errors (stmt.condition);
 577
 578                 // true block
 579                 var last_block = current_block;
 580                 if (always_false (stmt.condition)) {
 581                         mark_unreachable ();
 582                 } else {
 583                         current_block = new BasicBlock ();
 584                         last_block.connect (current_block);
 585                 }
 586                 stmt.true_statement.accept (this);
 587
 588                 // false block
 589                 var last_true_block = current_block;
 590                 if (always_true (stmt.condition)) {
 591                         mark_unreachable ();
 592                 } else {
 593                         current_block = new BasicBlock ();
 594                         last_block.connect (current_block);
 595                 }
 596                 if (stmt.false_statement != null) {
 597                         stmt.false_statement.accept (this);
 598                 }
 599
 600                 // after if/else
 601                 var last_false_block = current_block;
 602                 // reachable?
 603                 if (last_true_block != null || last_false_block != null) {
 604                         current_block = new BasicBlock ();
 605                         if (last_true_block != null) {
 606                                 last_true_block.connect (current_block);
 607                         }
 608                         if (last_false_block != null) {
 609                                 last_false_block.connect (current_block);
 610                         }
 611                 }
 612         }
 613
 614         public override void visit_switch_statement (SwitchStatement stmt) {
 615                 if (unreachable (stmt)) {
 616                         return;
 617                 }
 618
 619                 var after_switch_block = new BasicBlock ();
 620                 jump_stack.add (new JumpTarget.break_target (after_switch_block));
 621
 622                 // condition
 623                 current_block.add_node (stmt.expression);
 624                 var condition_block = current_block;
 625
 626                 handle_errors (stmt.expression);
 627
 628                 bool has_default_label = false;
 629
 630                 foreach (SwitchSection section in stmt.get_sections ()) {
 631                         current_block = new BasicBlock ();
 632                         condition_block.connect (current_block);
 633                         foreach (Statement section_stmt in section.get_statements ()) {
 634                                 section_stmt.accept (this);
 635                         }
 636
 637                         if (section.has_default_label ()) {
 638                                 has_default_label = true;
 639                         }
 640
 641                         if (current_block != null) {
 642                                 // end of switch section reachable
 643                                 // we don't allow fall-through
 644
 645                                 Report.error (section.source_reference, "missing break statement at end of switch section");
 646                                 section.error = true;
 647
 648                                 current_block.connect (after_switch_block);
 649                         }
 650                 }
 651
 652                 if (!has_default_label) {
 653                         condition_block.connect (after_switch_block);
 654                 }
 655
 656                 // after switch
 657                 // reachable?
 658                 if (after_switch_block.get_predecessors ().size > 0) {
 659                         current_block = after_switch_block;
 660                 } else {
 661                         mark_unreachable ();
 662                 }
 663
 664                 jump_stack.remove_at (jump_stack.size - 1);
 665         }
 666
 667         public override void visit_loop (Loop stmt) {
 668                 if (unreachable (stmt)) {
 669                         return;
 670                 }
 671
 672                 var loop_block = new BasicBlock ();
 673                 jump_stack.add (new JumpTarget.continue_target (loop_block));
 674                 var after_loop_block = new BasicBlock ();
 675                 jump_stack.add (new JumpTarget.break_target (after_loop_block));
 676
 677                 // loop block
 678                 var last_block = current_block;
 679                 last_block.connect (loop_block);
 680                 current_block = loop_block;
 681
 682                 stmt.body.accept (this);
 683                 // end of loop block reachable?
 684                 if (current_block != null) {
 685                         current_block.connect (loop_block);
 686                 }
 687
 688                 // after loop
 689                 // reachable?
 690                 if (after_loop_block.get_predecessors ().size == 0) {
 691                         // after loop block not reachable
 692                         mark_unreachable ();
 693                 } else {
 694                         // after loop block reachable
 695                         current_block = after_loop_block;
 696                 }
 697
 698                 jump_stack.remove_at (jump_stack.size - 1);
 699                 jump_stack.remove_at (jump_stack.size - 1);
 700         }
 701
 702         public override void visit_foreach_statement (ForeachStatement stmt) {
 703                 if (unreachable (stmt)) {
 704                         return;
 705                 }
 706
 707                 // collection
 708                 current_block.add_node (stmt.collection);
 709                 handle_errors (stmt.collection);
 710
 711                 var loop_block = new BasicBlock ();
 712                 jump_stack.add (new JumpTarget.continue_target (loop_block));
 713                 var after_loop_block = new BasicBlock ();
 714                 jump_stack.add (new JumpTarget.break_target (after_loop_block));
 715
 716                 // loop block
 717                 var last_block = current_block;
 718                 last_block.connect (loop_block);
 719                 current_block = loop_block;
 720                 current_block.add_node (stmt);
 721                 stmt.body.accept (this);
 722                 if (current_block != null) {
 723                         current_block.connect (loop_block);
 724                 }
 725
 726                 // after loop
 727                 last_block.connect (after_loop_block);
 728                 if (current_block != null) {
 729                         current_block.connect (after_loop_block);
 730                 }
 731                 current_block = after_loop_block;
 732
 733                 jump_stack.remove_at (jump_stack.size - 1);
 734                 jump_stack.remove_at (jump_stack.size - 1);
 735         }
 736
 737         public override void visit_break_statement (BreakStatement stmt) {
 738                 if (unreachable (stmt)) {
 739                         return;
 740                 }
 741
 742                 current_block.add_node (stmt);
 743
 744                 for (int i = jump_stack.size - 1; i >= 0; i--) {
 745                         var jump_target = jump_stack[i];
 746                         if (jump_target.is_break_target) {
 747                                 current_block.connect (jump_target.basic_block);
 748                                 mark_unreachable ();
 749                                 return;
 750                         } else if (jump_target.is_finally_clause) {
 751                                 current_block.connect (jump_target.basic_block);
 752                                 current_block = jump_target.last_block;
 753                         }
 754                 }
 755
 756                 Report.error (stmt.source_reference, "no enclosing loop or switch statement found");
 757                 stmt.error = true;
 758         }
 759
 760         public override void visit_continue_statement (ContinueStatement stmt) {
 761                 if (unreachable (stmt)) {
 762                         return;
 763                 }
 764
 765                 current_block.add_node (stmt);
 766
 767                 for (int i = jump_stack.size - 1; i >= 0; i--) {
 768                         var jump_target = jump_stack[i];
 769                         if (jump_target.is_continue_target) {
 770                                 current_block.connect (jump_target.basic_block);
 771                                 mark_unreachable ();
 772                                 return;
 773                         } else if (jump_target.is_finally_clause) {
 774                                 current_block.connect (jump_target.basic_block);
 775                                 current_block = jump_target.last_block;
 776                         }
 777                 }
 778
 779                 Report.error (stmt.source_reference, "no enclosing loop found");
 780                 stmt.error = true;
 781         }
 782
 783         public override void visit_return_statement (ReturnStatement stmt) {
 784                 stmt.accept_children (this);
 785
 786                 if (unreachable (stmt)) {
 787                         return;
 788                 }
 789
 790                 current_block.add_node (stmt);
 791
 792                 if (stmt.return_expression != null) {
 793                         handle_errors (stmt.return_expression);
 794                 }
 795
 796                 for (int i = jump_stack.size - 1; i >= 0; i--) {
 797                         var jump_target = jump_stack[i];
 798                         if (jump_target.is_return_target) {
 799                                 current_block.connect (jump_target.basic_block);
 800                                 mark_unreachable ();
 801                                 return;
 802                         } else if (jump_target.is_finally_clause) {
 803                                 current_block.connect (jump_target.basic_block);
 804                                 current_block = jump_target.last_block;
 805                         }
 806                 }
 807
 808                 Report.error (stmt.source_reference, "no enclosing loop found");
 809                 stmt.error = true;
 810         }
 811
 812         private void handle_errors (CodeNode node, bool always_fail = false) {
 813                 if (node.tree_can_fail) {
 814                         var last_block = current_block;
 815
 816                         // exceptional control flow
 817                         foreach (DataType error_data_type in node.get_error_types()) {
 818                                 var error_type = error_data_type as ErrorType;
 819                                 var error_class = error_data_type.data_type as Class;
 820                                 current_block = last_block;
 821                                 unreachable_reported = true;
 822
 823                                 for (int i = jump_stack.size - 1; i >= 0; i--) {
 824                                         var jump_target = jump_stack[i];
 825                                         if (jump_target.is_exit_target) {
 826                                                 current_block.connect (jump_target.basic_block);
 827                                                 mark_unreachable ();
 828                                                 break;
 829                                         } else if (jump_target.is_error_target) {
 830                                                 if (context.profile == Profile.GOBJECT) {
 831                                                         if (jump_target.error_domain == null
 832                                                             || (jump_target.error_domain == error_type.error_domain
 833                                                                 && (jump_target.error_code == null
 834                                                                     || jump_target.error_code == error_type.error_code))) {
 835                                                                 // error can always be caught by this catch clause
 836                                                                 // following catch clauses cannot be reached by this error
 837                                                                 current_block.connect (jump_target.basic_block);
 838                                                                 mark_unreachable ();
 839                                                                 break;
 840                                                         } else if (error_type.error_domain == null
 841                                                                    || (error_type.error_domain == jump_target.error_domain
 842                                                                        && (error_type.error_code == null
 843                                                                            || error_type.error_code == jump_target.error_code))) {
 844                                                                 // error might be caught by this catch clause
 845                                                                 // unknown at compile time
 846                                                                 // following catch clauses might still be reached by this error
 847                                                                 current_block.connect (jump_target.basic_block);
 848                                                         }
 849                                                 } else if (jump_target.error_class == null || jump_target.error_class == error_class) {
 850                                                         // error can always be caught by this catch clause
 851                                                         // following catch clauses cannot be reached by this error
 852                                                         current_block.connect (jump_target.basic_block);
 853                                                         mark_unreachable ();
 854                                                         break;
 855                                                 } else if (jump_target.error_class.is_subtype_of (error_class)) {
 856                                                         // error might be caught by this catch clause
 857                                                         // unknown at compile time
 858                                                         // following catch clauses might still be reached by this error
 859                                                         current_block.connect (jump_target.basic_block);
 860                                                 }
 861                                         } else if (jump_target.is_finally_clause) {
 862                                                 current_block.connect (jump_target.basic_block);
 863                                                 current_block = jump_target.last_block;
 864                                         }
 865                                 }
 866                         }
 867
 868                         // normal control flow
 869                         if (!always_fail) {
 870                                 current_block = new BasicBlock ();
 871                                 last_block.connect (current_block);
 872                         }
 873                 }
 874         }
 875
 876         public override void visit_yield_statement (YieldStatement stmt) {
 877                 if (unreachable (stmt)) {
 878                         return;
 879                 }
 880
 881                 stmt.accept_children (this);
 882         }
 883
 884         public override void visit_throw_statement (ThrowStatement stmt) {
 885                 if (unreachable (stmt)) {
 886                         return;
 887                 }
 888
 889                 current_block.add_node (stmt);
 890                 handle_errors (stmt, true);
 891         }
 892
 893         public override void visit_try_statement (TryStatement stmt) {
 894                 if (unreachable (stmt)) {
 895                         return;
 896                 }
 897
 898                 var before_try_block = current_block;
 899                 var after_try_block = new BasicBlock ();
 900
 901                 BasicBlock finally_block = null;
 902                 if (stmt.finally_body != null) {
 903                         finally_block = new BasicBlock ();
 904                         current_block = finally_block;
 905
 906                         // trap all forbidden jumps
 907                         var invalid_block = new BasicBlock ();
 908                         jump_stack.add (new JumpTarget.any_target (invalid_block));
 909
 910                         stmt.finally_body.accept (this);
 911
 912                         if (invalid_block.get_predecessors ().size > 0) {
 913                                 // don't allow finally blocks with e.g. return statements
 914                                 Report.error (stmt.source_reference, "jump out of finally block not permitted");
 915                                 stmt.error = true;
 916                                 return;
 917                         }
 918                         jump_stack.remove_at (jump_stack.size - 1);
 919
 920                         jump_stack.add (new JumpTarget.finally_clause (finally_block, current_block));
 921                 }
 922
 923                 int finally_jump_stack_size = jump_stack.size;
 924
 925                 var catch_clauses = stmt.get_catch_clauses ();
 926                 for (int i = catch_clauses.size - 1; i >= 0; i--) {
 927                         var catch_clause = catch_clauses[i];
 928                         if (catch_clause.error_type != null) {
 929                                 if (context.profile == Profile.GOBJECT) {
 930                                         var error_type = catch_clause.error_type as ErrorType;
 931                                         jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, catch_clause.error_type.data_type as ErrorDomain, error_type.error_code, null));
 932                                 } else {
 933                                         var error_class = catch_clause.error_type.data_type as Class;
 934                                         jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, null, null, error_class));
 935                                 }
 936                         } else {
 937                                 jump_stack.add (new JumpTarget.error_target (new BasicBlock (), catch_clause, null, null, null));
 938                         }
 939                 }
 940
 941                 current_block = before_try_block;
 942
 943                 stmt.body.accept (this);
 944
 945                 if (current_block != null) {
 946                         if (finally_block != null) {
 947                                 current_block.connect (finally_block);
 948                                 current_block = finally_block;
 949                         }
 950                         current_block.connect (after_try_block);
 951                 }
 952
 953                 // remove catch clauses from jump stack
 954                 List<JumpTarget> catch_stack = new ArrayList<JumpTarget> ();
 955                 for (int i = jump_stack.size - 1; i >= finally_jump_stack_size; i--) {
 956                         var jump_target = jump_stack[i];
 957                         catch_stack.add (jump_target);
 958                         jump_stack.remove_at (i);
 959                 }
 960
 961                 foreach (JumpTarget jump_target in catch_stack) {
 962
 963                         foreach (JumpTarget prev_target in catch_stack) {
 964                                 if (prev_target == jump_target) {
 965                                         break;
 966                                 }
 967
 968                                 if (context.profile == Profile.GOBJECT) {
 969                                         if (prev_target.error_domain == jump_target.error_domain &&
 970                                             prev_target.error_code == jump_target.error_code) {
 971                                                 Report.error (stmt.source_reference, "double catch clause of same error detected");
 972                                                 stmt.error = true;
 973                                                 return;
 974                                         }
 975                                 } else if (prev_target.error_class == jump_target.error_class) {
 976                                         Report.error (stmt.source_reference, "double catch clause of same error detected");
 977                                         stmt.error = true;
 978                                         return;
 979                                 }
 980                         }
 981
 982                         if (jump_target.basic_block.get_predecessors ().size == 0) {
 983                                 // unreachable
 984                                 Report.warning (jump_target.catch_clause.source_reference, "unreachable catch clause detected");
 985                         } else {
 986                                 current_block = jump_target.basic_block;
 987                                 current_block.add_node (jump_target.catch_clause);
 988                                 jump_target.catch_clause.body.accept (this);
 989                                 if (current_block != null) {
 990                                         if (finally_block != null) {
 991                                                 current_block.connect (finally_block);
 992                                                 current_block = finally_block;
 993                                         }
 994                                         current_block.connect (after_try_block);
 995                                 }
 996                         }
 997                 }
 998
 999                 if (finally_block != null) {
1000                         jump_stack.remove_at (jump_stack.size - 1);
1001                 }
1002
1003                 // after try statement
1004                 // reachable?
1005                 if (after_try_block.get_predecessors ().size > 0) {
1006                         current_block = after_try_block;
1007                 } else {
1008                         stmt.after_try_block_reachable = false;
1009                         mark_unreachable ();
1010                 }
1011         }
1012
1013         public override void visit_lock_statement (LockStatement stmt) {
1014                 if (unreachable (stmt)) {
1015                         return;
1016                 }
1017         }
1018
1019         public override void visit_unlock_statement (UnlockStatement stmt) {
1020                 if (unreachable (stmt)) {
1021                         return;
1022                 }
1023         }
1024
1025         public override void visit_expression (Expression expr) {
1026                 // lambda expression is handled separately
1027                 if (!(expr is LambdaExpression)) {
1028                         expr.accept_children (this);
1029                 }
1030         }
1031
1032         private bool unreachable (CodeNode node) {
1033                 if (current_block == null) {
1034                         node.unreachable = true;
1035                         if (!unreachable_reported) {
1036                                 Report.warning (node.source_reference, "unreachable code detected");
1037                                 unreachable_reported = true;
1038                         }
1039                         return true;
1040                 }
1041
1042                 return false;
1043         }
1044
1045         void mark_unreachable () {
1046                 current_block = null;
1047                 unreachable_reported = false;
1048         }
1049 }