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