Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/ControlStruct/MLEMutator.cc

    rba3706f r720a007  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug  4 11:21:32 2016
    13 // Update Count     : 202
     12// Last Modified On : Thu Mar  8 17:08:25 2018
     13// Update Count     : 219
    1414//
    1515
    … …  
    3838        }
    3939        namespace {
    40                 Statement * isLoop( Statement * stmt ) { return dynamic_cast< WhileStmt * >( stmt ) ? stmt : dynamic_cast< ForStmt * >( stmt ) ? stmt : 0; }
    41         }
     40                bool isLoop( const MLEMutator::Entry & e ) { return dynamic_cast< WhileStmt * >( e.get_controlStructure() ) || dynamic_cast< ForStmt * >( e.get_controlStructure() ); }
     41                bool isSwitch( const MLEMutator::Entry & e ) { return dynamic_cast< SwitchStmt *>( e.get_controlStructure() ); }
     42
     43                bool isBreakTarget( const MLEMutator::Entry & e ) { return isLoop( e ) || isSwitch( e ) || dynamic_cast< CompoundStmt *>( e.get_controlStructure() ); }
     44                bool isContinueTarget( const MLEMutator::Entry & e ) { return isLoop( e ); }
     45                bool isFallthroughTarget( const MLEMutator::Entry & e ) { return dynamic_cast< CaseStmt *>( e.get_controlStructure() );; }
     46                bool isFallthroughDefaultTarget( const MLEMutator::Entry & e ) { return isSwitch( e ); }
     47        } // namespace
    4248
    4349        // break labels have to come after the statement they break out of, so mutate a statement, then if they inform us
    4450        // through the breakLabel field tha they need a place to jump to on a break statement, add the break label to the
    4551        // body of statements
    46         void MLEMutator::fixBlock( std::list< Statement * > &kids ) {
     52        void MLEMutator::fixBlock( std::list< Statement * > &kids, bool caseClause ) {
     53                SemanticErrorException errors;
     54
    4755                for ( std::list< Statement * >::iterator k = kids.begin(); k != kids.end(); k++ ) {
    48                         *k = (*k)->acceptMutator(*this);
     56                        if ( caseClause ) {
     57                                // once a label is seen, it's no longer a valid fallthrough target
     58                                for ( Label & l : (*k)->labels ) {
     59                                        fallthroughLabels.erase( l );
     60                                }
     61                        }
     62
     63                        // aggregate errors since the PassVisitor mutate loop was unrollled
     64                        try {
     65                                *k = (*k)->acceptMutator(*visitor);
     66                        } catch( SemanticErrorException &e ) {
     67                                errors.append( e );
     68                        }
    4969
    5070                        if ( ! get_breakLabel().empty() ) {
    … …  
    5575                        } // if
    5676                } // for
    57         }
    58 
    59         CompoundStmt* MLEMutator::mutate( CompoundStmt *cmpndStmt ) {
    60                 bool labeledBlock = !(cmpndStmt->get_labels().empty());
     77
     78                if ( ! errors.isEmpty() ) {
     79                        throw errors;
     80                }
     81        }
     82
     83        void MLEMutator::premutate( CompoundStmt *cmpndStmt ) {
     84                visit_children = false;
     85                bool labeledBlock = !(cmpndStmt->labels.empty());
    6186                if ( labeledBlock ) {
    6287                        Label brkLabel = generator->newLabel("blockBreak", cmpndStmt);
    6388                        enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
     89                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
    6490                } // if
    6591
    6692                // a child statement may set the break label - if they do, attach it to the next statement
    67                 std::list< Statement * > &kids = cmpndStmt->get_kids();
     93                std::list< Statement * > &kids = cmpndStmt->kids;
    6894                fixBlock( kids );
    6995
    … …  
    7399                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
    74100                        } // if
    75                         enclosingControlStructures.pop_back();
    76                 } // if
    77 
    78                 return cmpndStmt;
    79         }
    80 
    81         template< typename LoopClass >
    82         Statement *MLEMutator::handleLoopStmt( LoopClass *loopStmt ) {
    83                 // remember this as the most recent enclosing loop, then mutate the body of the loop -- this will determine
    84                 // whether brkLabel and contLabel are used with branch statements and will recursively do the same to nested
    85                 // loops
    86                 Label brkLabel = generator->newLabel("loopBreak", loopStmt);
    87                 Label contLabel = generator->newLabel("loopContinue", loopStmt);
    88                 enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
    89                 loopStmt->set_body ( loopStmt->get_body()->acceptMutator( *this ) );
    90 
    91                 assert( ! enclosingControlStructures.empty() );
    92                 Entry &e = enclosingControlStructures.back();
    93                 // sanity check that the enclosing loops have been popped correctly
    94                 assert ( e == loopStmt );
    95 
    96                 // this will take the necessary steps to add definitions of the previous two labels, if they are used.
    97                 loopStmt->set_body( mutateLoop( loopStmt->get_body(), e ) );
    98                 enclosingControlStructures.pop_back();
    99 
    100                 return loopStmt;
    101         }
    102 
    103         Statement *MLEMutator::mutate( CaseStmt *caseStmt ) {
    104                 caseStmt->set_condition( maybeMutate( caseStmt->get_condition(), *this ) );
    105                 fixBlock( caseStmt->get_statements() );
    106 
    107                 return caseStmt;
    108         }
    109 
    110         template< typename IfClass >
    111         Statement *MLEMutator::handleIfStmt( IfClass *ifStmt ) {
    112                 // generate a label for breaking out of a labeled if
    113                 bool labeledBlock = !(ifStmt->get_labels().empty());
    114                 if ( labeledBlock ) {
    115                         Label brkLabel = generator->newLabel("blockBreak", ifStmt);
    116                         enclosingControlStructures.push_back( Entry( ifStmt, brkLabel ) );
    117                 } // if
    118 
    119                 Parent::mutate( ifStmt );
    120 
    121                 if ( labeledBlock ) {
    122                         if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
    123                                 set_breakLabel( enclosingControlStructures.back().useBreakExit() );
    124                         } // if
    125                         enclosingControlStructures.pop_back();
    126                 } // if
    127                 return ifStmt;
    128         }
    129 
    130         template< typename SwitchClass >
    131         Statement *MLEMutator::handleSwitchStmt( SwitchClass *switchStmt ) {
    132                 // generate a label for breaking out of a labeled switch
    133                 Label brkLabel = generator->newLabel("switchBreak", switchStmt);
    134                 enclosingControlStructures.push_back( Entry(switchStmt, brkLabel) );
    135                 mutateAll( switchStmt->get_statements(), *this );
    136 
    137                 Entry &e = enclosingControlStructures.back();
    138                 assert ( e == switchStmt );
    139 
    140                 // only generate break label if labeled break is used
    141                 if ( e.isBreakUsed() ) {
    142                         // for the purposes of keeping switch statements uniform (i.e. all statements that are direct children of a
    143                         // switch should be CastStmts), append the exit label + break to the last case statement; create a default
    144                         // case if there are no cases
    145                         std::list< Statement * > &statements = switchStmt->get_statements();
    146                         if ( statements.empty() ) {
    147                                 statements.push_back( CaseStmt::makeDefault() );
    148                         } // if
    149 
    150                         if ( CaseStmt * c = dynamic_cast< CaseStmt * >( statements.back() ) ) {
    151                                 Statement * stmt = new BranchStmt( Label("brkLabel"), BranchStmt::Break );
    152                                 stmt->labels.push_back( brkLabel );
    153                                 c->get_statements().push_back( stmt );
    154                         } else assert(0); // as of this point, all statements of a switch are still CaseStmts
    155                 } // if
    156 
    157                 assert ( enclosingControlStructures.back() == switchStmt );
    158                 enclosingControlStructures.pop_back();
    159                 return switchStmt;
    160         }
     101                } // if
     102        }
     103
    161104
    162105        void addUnused( Statement * stmt, const Label & originalTarget ) {
    … …  
    179122
    180123
    181         Statement *MLEMutator::mutate( BranchStmt *branchStmt ) throw ( SemanticError ) {
    182                 std::string originalTarget = branchStmt->get_originalTarget();
     124        Statement *MLEMutator::postmutate( BranchStmt *branchStmt ) throw ( SemanticErrorException ) {
     125                std::string originalTarget = branchStmt->originalTarget;
    183126
    184127                std::list< Entry >::reverse_iterator targetEntry;
    … …  
    193136                                        if ( isContinue ) {
    194137                                                // continue target is outermost loop
    195                                                 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), [](Entry &e) { return isLoop( e.get_controlStructure() ); } );
     138                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isContinueTarget );
    196139                                        } else {
    197                                                 // break target is outmost control structure
    198                                                 if ( enclosingControlStructures.empty() ) throw SemanticError( "'break' outside a loop, switch, or labelled block" );
    199                                                 targetEntry = enclosingControlStructures.rbegin();
     140                                                // break target is outermost loop, switch, or block control structure
     141                                                if ( enclosingControlStructures.empty() ) SemanticError( branchStmt->location, "'break' outside a loop, 'switch', or labelled block" );
     142                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isBreakTarget );
    200143                                        } // if
    201144                                } else {
    … …  
    204147                                } // if
    205148                                // ensure that selected target is valid
    206                                 if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isLoop( targetEntry->get_controlStructure() ) ) ) {
    207                                         throw SemanticError( toString( (isContinue ? "'continue'" : "'break'"), " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), originalTarget ) );
     149                                if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isContinueTarget( *targetEntry ) ) ) {
     150                                        SemanticError( branchStmt->location, toString( (isContinue ? "'continue'" : "'break'"), " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), originalTarget ) );
    208151                                } // if
    209152                                break;
    210153                        }
     154                        case BranchStmt::FallThrough:
     155                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughTarget );
     156                                // ensure that selected target is valid
     157                                if ( targetEntry == enclosingControlStructures.rend() ) {
     158                                        SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
     159                                } // if
     160                                if ( branchStmt->get_target() != "" ) {
     161                                        // labelled fallthrough
     162                                        // target must be in the set of valid fallthrough labels
     163                                        if ( ! fallthroughLabels.count( branchStmt->get_target() ) ) {
     164                                                SemanticError( branchStmt->location, toString( "'fallthrough' target must be a later case statement: ", originalTarget ) );
     165                                        }
     166                                        return new BranchStmt( originalTarget, BranchStmt::Goto );
     167                                }
     168                                break;
     169                        case BranchStmt::FallThroughDefault: {
     170                                // fallthrough default
     171                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughDefaultTarget );
     172
     173                                // ensure that fallthrough is within a switch or choose
     174                                if ( targetEntry == enclosingControlStructures.rend() ) {
     175                                        SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
     176                                } // if
     177
     178                                // ensure that switch or choose has a default clause
     179                                SwitchStmt * switchStmt = strict_dynamic_cast< SwitchStmt * >( targetEntry->get_controlStructure() );
     180                                bool foundDefault = false;
     181                                for ( Statement * stmt : switchStmt->statements ) {
     182                                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
     183                                        if ( caseStmt->isDefault() ) {
     184                                                foundDefault = true;
     185                                        } // if
     186                                } // for
     187                                if ( ! foundDefault ) {
     188                                        SemanticError( branchStmt->location, "'fallthrough default' must be enclosed in a 'switch' or 'choose' control structure with a 'default' clause" );
     189                                }
     190                                break;
     191                        }
     192
    211193                        default:
    212194                                assert( false );
    … …  
    215197                // branch error checks, get the appropriate label name and create a goto
    216198                Label exitLabel;
    217                 switch ( branchStmt->get_type() ) {
     199                switch ( branchStmt->type ) {
    218200                  case BranchStmt::Break:
    219201                                assert( targetEntry->useBreakExit() != "");
    … …  
    224206                                exitLabel = targetEntry->useContExit();
    225207                                break;
     208                  case BranchStmt::FallThrough:
     209                                assert( targetEntry->useFallExit() != "");
     210                                exitLabel = targetEntry->useFallExit();
     211                                break;
     212                  case BranchStmt::FallThroughDefault:
     213                                assert( targetEntry->useFallDefaultExit() != "");
     214                                exitLabel = targetEntry->useFallDefaultExit();
     215                                // check that fallthrough default comes before the default clause
     216                                if ( ! targetEntry->isFallDefaultValid() ) {
     217                                        SemanticError( branchStmt->location, "'fallthrough default' must precede the 'default' clause" );
     218                                }
     219                                break;
    226220                  default:
    227221                                assert(0);                                      // shouldn't be here
    … …  
    229223
    230224                // add unused attribute to label to silence warnings
    231                 addUnused( targetEntry->get_controlStructure(), branchStmt->get_originalTarget() );
     225                addUnused( targetEntry->get_controlStructure(), branchStmt->originalTarget );
    232226
    233227                // transform break/continue statements into goto to simplify later handling of branches
    … …  
    260254        }
    261255
    262         Statement *MLEMutator::mutate( WhileStmt *whileStmt ) {
    263                 return handleLoopStmt( whileStmt );
    264         }
    265 
    266         Statement *MLEMutator::mutate( ForStmt *forStmt ) {
    267                 return handleLoopStmt( forStmt );
    268         }
    269 
    270         Statement *MLEMutator::mutate( IfStmt *ifStmt ) {
    271                 return handleIfStmt( ifStmt );
    272         }
    273 
    274         Statement *MLEMutator::mutate( SwitchStmt *switchStmt ) {
    275                 return handleSwitchStmt( switchStmt );
     256        template< typename LoopClass >
     257        void MLEMutator::prehandleLoopStmt( LoopClass * loopStmt ) {
     258                // remember this as the most recent enclosing loop, then mutate the body of the loop -- this will determine
     259                // whether brkLabel and contLabel are used with branch statements and will recursively do the same to nested
     260                // loops
     261                Label brkLabel = generator->newLabel("loopBreak", loopStmt);
     262                Label contLabel = generator->newLabel("loopContinue", loopStmt);
     263                enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
     264                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
     265        }
     266
     267        template< typename LoopClass >
     268        Statement * MLEMutator::posthandleLoopStmt( LoopClass * loopStmt ) {
     269                assert( ! enclosingControlStructures.empty() );
     270                Entry &e = enclosingControlStructures.back();
     271                // sanity check that the enclosing loops have been popped correctly
     272                assert ( e == loopStmt );
     273
     274                // this will take the necessary steps to add definitions of the previous two labels, if they are used.
     275                loopStmt->body = mutateLoop( loopStmt->get_body(), e );
     276                return loopStmt;
     277        }
     278
     279        void MLEMutator::premutate( WhileStmt * whileStmt ) {
     280                return prehandleLoopStmt( whileStmt );
     281        }
     282
     283        void MLEMutator::premutate( ForStmt * forStmt ) {
     284                return prehandleLoopStmt( forStmt );
     285        }
     286
     287        Statement * MLEMutator::postmutate( WhileStmt * whileStmt ) {
     288                return posthandleLoopStmt( whileStmt );
     289        }
     290
     291        Statement * MLEMutator::postmutate( ForStmt * forStmt ) {
     292                return posthandleLoopStmt( forStmt );
     293        }
     294
     295        void MLEMutator::premutate( IfStmt * ifStmt ) {
     296                // generate a label for breaking out of a labeled if
     297                bool labeledBlock = !(ifStmt->get_labels().empty());
     298                if ( labeledBlock ) {
     299                        Label brkLabel = generator->newLabel("blockBreak", ifStmt);
     300                        enclosingControlStructures.push_back( Entry( ifStmt, brkLabel ) );
     301                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
     302                } // if
     303        }
     304
     305        Statement * MLEMutator::postmutate( IfStmt * ifStmt ) {
     306                bool labeledBlock = !(ifStmt->get_labels().empty());
     307                if ( labeledBlock ) {
     308                        if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
     309                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
     310                        } // if
     311                } // if
     312                return ifStmt;
     313        }
     314
     315        void MLEMutator::premutate( CaseStmt *caseStmt ) {
     316                visit_children = false;
     317
     318                // mark default as seen before visiting its statements to catch default loops
     319                if ( caseStmt->isDefault() ) {
     320                        enclosingControlStructures.back().seenDefault();
     321                } // if
     322
     323                caseStmt->condition = maybeMutate( caseStmt->condition, *visitor );
     324                Label fallLabel = generator->newLabel( "fallThrough", caseStmt );
     325                {
     326                        // ensure that stack isn't corrupted by exceptions in fixBlock
     327                        auto guard = makeFuncGuard( [&]() { enclosingControlStructures.push_back( Entry( caseStmt, fallLabel ) ); }, [this]() { enclosingControlStructures.pop_back(); } );
     328
     329                        // empty case statement
     330                        if( ! caseStmt->stmts.empty() ) {
     331                                // the parser ensures that all statements in a case are grouped into a block
     332                                CompoundStmt * block = strict_dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
     333                                fixBlock( block->kids, true );
     334
     335                                // add fallthrough label if necessary
     336                                assert( ! enclosingControlStructures.empty() );
     337                                if ( enclosingControlStructures.back().isFallUsed() ) {
     338                                        std::list<Label> ls{ enclosingControlStructures.back().useFallExit() };
     339                                        caseStmt->stmts.push_back( new NullStmt( ls ) );
     340                                } // if
     341                        } // if
     342                }
     343                assert( ! enclosingControlStructures.empty() );
     344                assertf( dynamic_cast<SwitchStmt *>( enclosingControlStructures.back().get_controlStructure() ), "Control structure enclosing a case clause must be a switch, but is: %s", toCString( enclosingControlStructures.back().get_controlStructure() ) );
     345                if ( caseStmt->isDefault() ) {
     346                        if ( enclosingControlStructures.back().isFallDefaultUsed() ) {
     347                                // add fallthrough default label if necessary
     348                                std::list<Label> ls{ enclosingControlStructures.back().useFallDefaultExit() };
     349                                caseStmt->stmts.push_front( new NullStmt( ls ) );
     350                        } // if
     351                } // if
     352        }
     353
     354        void MLEMutator::premutate( SwitchStmt *switchStmt ) {
     355                // generate a label for breaking out of a labeled switch
     356                Label brkLabel = generator->newLabel("switchBreak", switchStmt);
     357                auto it = std::find_if( switchStmt->statements.rbegin(), switchStmt->statements.rend(), [](Statement * stmt) {
     358                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
     359                        return caseStmt->isDefault();
     360                });
     361                CaseStmt * defaultCase = it != switchStmt->statements.rend() ? strict_dynamic_cast<CaseStmt *>( *it ) : nullptr;
     362                Label fallDefaultLabel = defaultCase ? generator->newLabel( "fallThroughDefault", defaultCase ) : "";
     363                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel, fallDefaultLabel) );
     364                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
     365
     366                // Collect valid labels for fallthrough. This is initially all labels at the same level as a case statement.
     367                // As labels are seen during traversal, they are removed, since fallthrough is not allowed to jump backwards.
     368                for ( Statement * stmt : switchStmt->statements ) {
     369                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
     370                        if ( caseStmt->stmts.empty() ) continue;
     371                        CompoundStmt * block = dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
     372                        for ( Statement * stmt : block->kids ) {
     373                                for ( Label & l : stmt->labels ) {
     374                                        fallthroughLabels.insert( l );
     375                                }
     376                        }
     377                }
     378        }
     379
     380        Statement * MLEMutator::postmutate( SwitchStmt * switchStmt ) {
     381                Entry &e = enclosingControlStructures.back();
     382                assert ( e == switchStmt );
     383
     384                // only generate break label if labeled break is used
     385                if ( e.isBreakUsed() ) {
     386                        // for the purposes of keeping switch statements uniform (i.e. all statements that are direct children of a
     387                        // switch should be CastStmts), append the exit label + break to the last case statement; create a default
     388                        // case if there are no cases
     389                        std::list< Statement * > &statements = switchStmt->statements;
     390                        if ( statements.empty() ) {
     391                                statements.push_back( CaseStmt::makeDefault() );
     392                        } // if
     393
     394                        if ( CaseStmt * c = dynamic_cast< CaseStmt * >( statements.back() ) ) {
     395                                Statement * stmt = new BranchStmt( Label("brkLabel"), BranchStmt::Break );
     396                                stmt->labels.push_back( e.useBreakExit() );
     397                                c->stmts.push_back( stmt );
     398                        } else assert(0); // as of this point, all statements of a switch are still CaseStmts
     399                } // if
     400
     401                assert ( enclosingControlStructures.back() == switchStmt );
     402                return switchStmt;
    276403        }
    277404} // namespace ControlStruct
Note: See TracChangeset for help on using the changeset viewer.