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