Changeset 720a007

Timestamp:

Mar 14, 2018, 2:06:29 PM (7 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, with_gc

Children:

753f13c9

Parents:

6a276a0

Message:

Implement new fallthrough semantics

Location:

src/ControlStruct

Files:

• MLEMutator.cc (modified) (15 diffs)
• MLEMutator.h (modified) (5 diffs)

src/ControlStruct/MLEMutator.cc

@@ -10 +10 @@
 // Created On       : Mon May 18 07:44:20 2015
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Aug  4 11:21:32 2016
-// Update Count     : 202
+// Last Modified On : Thu Mar  8 17:08:25 2018
+// Update Count     : 219
 //
 
@@ -38 +38 @@
         }
         namespace {
-                Statement * isLoop( Statement * stmt ) { return dynamic_cast< WhileStmt * >( stmt ) ? stmt : dynamic_cast< ForStmt * >( stmt ) ? stmt : 0; }
-        }
+                bool isLoop( const MLEMutator::Entry & e ) { return dynamic_cast< WhileStmt * >( e.get_controlStructure() ) || dynamic_cast< ForStmt * >( e.get_controlStructure() ); }
+                bool isSwitch( const MLEMutator::Entry & e ) { return dynamic_cast< SwitchStmt *>( e.get_controlStructure() ); }
+
+                bool isBreakTarget( const MLEMutator::Entry & e ) { return isLoop( e ) || isSwitch( e ) || dynamic_cast< CompoundStmt *>( e.get_controlStructure() ); }
+                bool isContinueTarget( const MLEMutator::Entry & e ) { return isLoop( e ); }
+                bool isFallthroughTarget( const MLEMutator::Entry & e ) { return dynamic_cast< CaseStmt *>( e.get_controlStructure() );; }
+                bool isFallthroughDefaultTarget( const MLEMutator::Entry & e ) { return isSwitch( e ); }
+        } // namespace
 
         // break labels have to come after the statement they break out of, so mutate a statement, then if they inform us
         // through the breakLabel field tha they need a place to jump to on a break statement, add the break label to the
         // body of statements
-        void MLEMutator::fixBlock( std::list< Statement * > &kids ) {
+        void MLEMutator::fixBlock( std::list< Statement * > &kids, bool caseClause ) {
+                SemanticErrorException errors;
+
                 for ( std::list< Statement * >::iterator k = kids.begin(); k != kids.end(); k++ ) {
-                        *k = (*k)->acceptMutator(*visitor);
+                        if ( caseClause ) {
+                                // once a label is seen, it's no longer a valid fallthrough target
+                                for ( Label & l : (*k)->labels ) {
+                                        fallthroughLabels.erase( l );
+                                }
+                        }
+
+                        // aggregate errors since the PassVisitor mutate loop was unrollled
+                        try {
+                                *k = (*k)->acceptMutator(*visitor);
+                        } catch( SemanticErrorException &e ) {
+                                errors.append( e );
+                        }
 
                         if ( ! get_breakLabel().empty() ) {
@@ -55 +75 @@
                         } // if
                 } // for
+
+                if ( ! errors.isEmpty() ) {
+                        throw errors;
+                }
         }
 
@@ -63 +87 @@
                         Label brkLabel = generator->newLabel("blockBreak", cmpndStmt);
                         enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
+                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
                 } // if
 
@@ -74 +99 @@
                                 set_breakLabel( enclosingControlStructures.back().useBreakExit() );
                         } // if
-                        enclosingControlStructures.pop_back();
                 } // if
         }
@@ -112 +136 @@
                                         if ( isContinue ) {
                                                 // continue target is outermost loop
-                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), [](Entry &e) { return isLoop( e.get_controlStructure() ); } );
+                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isContinueTarget );
                                         } else {
-                                                // break target is outmost control structure
-                                                if ( enclosingControlStructures.empty() ) SemanticError( branchStmt->location, "'break' outside a loop, switch, or labelled block" );
-                                                targetEntry = enclosingControlStructures.rbegin();
+                                                // break target is outermost loop, switch, or block control structure
+                                                if ( enclosingControlStructures.empty() ) SemanticError( branchStmt->location, "'break' outside a loop, 'switch', or labelled block" );
+                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isBreakTarget );
                                         } // if
                                 } else {
@@ -123 +147 @@
                                 } // if
                                 // ensure that selected target is valid
-                                if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isLoop( targetEntry->get_controlStructure() ) ) ) {
+                                if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isContinueTarget( *targetEntry ) ) ) {
                                         SemanticError( branchStmt->location, toString( (isContinue ? "'continue'" : "'break'"), " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), originalTarget ) );
                                 } // if
                                 break;
                         }
+                        case BranchStmt::FallThrough:
+                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughTarget );
+                                // ensure that selected target is valid
+                                if ( targetEntry == enclosingControlStructures.rend() ) {
+                                        SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
+                                } // if
+                                if ( branchStmt->get_target() != "" ) {
+                                        // labelled fallthrough
+                                        // target must be in the set of valid fallthrough labels
+                                        if ( ! fallthroughLabels.count( branchStmt->get_target() ) ) {
+                                                SemanticError( branchStmt->location, toString( "'fallthrough' target must be a later case statement: ", originalTarget ) );
+                                        }
+                                        return new BranchStmt( originalTarget, BranchStmt::Goto );
+                                }
+                                break;
+                        case BranchStmt::FallThroughDefault: {
+                                // fallthrough default
+                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughDefaultTarget );
+
+                                // ensure that fallthrough is within a switch or choose
+                                if ( targetEntry == enclosingControlStructures.rend() ) {
+                                        SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
+                                } // if
+
+                                // ensure that switch or choose has a default clause
+                                SwitchStmt * switchStmt = strict_dynamic_cast< SwitchStmt * >( targetEntry->get_controlStructure() );
+                                bool foundDefault = false;
+                                for ( Statement * stmt : switchStmt->statements ) {
+                                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
+                                        if ( caseStmt->isDefault() ) {
+                                                foundDefault = true;
+                                        } // if
+                                } // for
+                                if ( ! foundDefault ) {
+                                        SemanticError( branchStmt->location, "'fallthrough default' must be enclosed in a 'switch' or 'choose' control structure with a 'default' clause" );
+                                }
+                                break;
+                        }
+
                         default:
                                 assert( false );
@@ -142 +205 @@
                                 assert( targetEntry->useContExit() != "");
                                 exitLabel = targetEntry->useContExit();
+                                break;
+                  case BranchStmt::FallThrough:
+                                assert( targetEntry->useFallExit() != "");
+                                exitLabel = targetEntry->useFallExit();
+                                break;
+                  case BranchStmt::FallThroughDefault:
+                                assert( targetEntry->useFallDefaultExit() != "");
+                                exitLabel = targetEntry->useFallDefaultExit();
+                                // check that fallthrough default comes before the default clause
+                                if ( ! targetEntry->isFallDefaultValid() ) {
+                                        SemanticError( branchStmt->location, "'fallthrough default' must precede the 'default' clause" );
+                                }
                                 break;
                   default:
@@ -187 +262 @@
                 Label contLabel = generator->newLabel("loopContinue", loopStmt);
                 enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
+                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
         }
 
@@ -197 +273 @@
 
                 // this will take the necessary steps to add definitions of the previous two labels, if they are used.
-                loopStmt->set_body( mutateLoop( loopStmt->get_body(), e ) );
-                enclosingControlStructures.pop_back();
+                loopStmt->body = mutateLoop( loopStmt->get_body(), e );
                 return loopStmt;
         }
@@ -224 +299 @@
                         Label brkLabel = generator->newLabel("blockBreak", ifStmt);
                         enclosingControlStructures.push_back( Entry( ifStmt, brkLabel ) );
+                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
                 } // if
         }
@@ -233 +309 @@
                                 set_breakLabel( enclosingControlStructures.back().useBreakExit() );
                         } // if
-                        enclosingControlStructures.pop_back();
                 } // if
                 return ifStmt;
@@ -240 +315 @@
         void MLEMutator::premutate( CaseStmt *caseStmt ) {
                 visit_children = false;
+
+                // mark default as seen before visiting its statements to catch default loops
+                if ( caseStmt->isDefault() ) {
+                        enclosingControlStructures.back().seenDefault();
+                } // if
+
                 caseStmt->condition = maybeMutate( caseStmt->condition, *visitor );
-                fixBlock( caseStmt->stmts );
+                Label fallLabel = generator->newLabel( "fallThrough", caseStmt );
+                {
+                        // ensure that stack isn't corrupted by exceptions in fixBlock
+                        auto guard = makeFuncGuard( [&]() { enclosingControlStructures.push_back( Entry( caseStmt, fallLabel ) ); }, [this]() { enclosingControlStructures.pop_back(); } );
+
+                        // empty case statement
+                        if( ! caseStmt->stmts.empty() ) {
+                                // the parser ensures that all statements in a case are grouped into a block
+                                CompoundStmt * block = strict_dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
+                                fixBlock( block->kids, true );
+
+                                // add fallthrough label if necessary
+                                assert( ! enclosingControlStructures.empty() );
+                                if ( enclosingControlStructures.back().isFallUsed() ) {
+                                        std::list<Label> ls{ enclosingControlStructures.back().useFallExit() };
+                                        caseStmt->stmts.push_back( new NullStmt( ls ) );
+                                } // if
+                        } // if
+                }
+                assert( ! enclosingControlStructures.empty() );
+                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() ) );
+                if ( caseStmt->isDefault() ) {
+                        if ( enclosingControlStructures.back().isFallDefaultUsed() ) {
+                                // add fallthrough default label if necessary
+                                std::list<Label> ls{ enclosingControlStructures.back().useFallDefaultExit() };
+                                caseStmt->stmts.push_front( new NullStmt( ls ) );
+                        } // if
+                } // if
         }
 
@@ -247 +355 @@
                 // generate a label for breaking out of a labeled switch
                 Label brkLabel = generator->newLabel("switchBreak", switchStmt);
-                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel) );
+                auto it = std::find_if( switchStmt->statements.rbegin(), switchStmt->statements.rend(), [](Statement * stmt) {
+                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
+                        return caseStmt->isDefault();
+                });
+                CaseStmt * defaultCase = it != switchStmt->statements.rend() ? strict_dynamic_cast<CaseStmt *>( *it ) : nullptr;
+                Label fallDefaultLabel = defaultCase ? generator->newLabel( "fallThroughDefault", defaultCase ) : "";
+                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel, fallDefaultLabel) );
+                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
+
+                // Collect valid labels for fallthrough. This is initially all labels at the same level as a case statement.
+                // As labels are seen during traversal, they are removed, since fallthrough is not allowed to jump backwards.
+                for ( Statement * stmt : switchStmt->statements ) {
+                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
+                        if ( caseStmt->stmts.empty() ) continue;
+                        CompoundStmt * block = dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
+                        for ( Statement * stmt : block->kids ) {
+                                for ( Label & l : stmt->labels ) {
+                                        fallthroughLabels.insert( l );
+                                }
+                        }
+                }
         }
 
@@ -272 +400 @@
 
                 assert ( enclosingControlStructures.back() == switchStmt );
-                enclosingControlStructures.pop_back();
                 return switchStmt;
         }

src/ControlStruct/MLEMutator.h

@@ -10 +10 @@
 // Created On       : Mon May 18 07:44:20 2015
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:19:59 2017
-// Update Count     : 35
+// Last Modified On : Thu Mar  8 16:42:32 2018
+// Update Count     : 41
 //
 
@@ -19 +19 @@
 #include <map>                     // for map
 #include <string>                  // for string
+#include <set>                     // for unordered_set
 
 #include "Common/PassVisitor.h"
@@ -29 +30 @@
         class LabelGenerator;
 
-        class MLEMutator : public WithVisitorRef<MLEMutator>, public WithShortCircuiting {
+        class MLEMutator : public WithVisitorRef<MLEMutator>, public WithShortCircuiting, public WithGuards {
+          public:
                 class Entry;
-
-          public:
                 MLEMutator( std::map<Label, Statement *> *t, LabelGenerator *gen = 0 ) : targetTable( t ), breakLabel(std::string("")), generator( gen ) {}
                 ~MLEMutator();
@@ -52 +52 @@
                 Label &get_breakLabel() { return breakLabel; }
                 void set_breakLabel( Label newValue ) { breakLabel = newValue; }
-          private:
+
                 class Entry {
                   public:
-                        explicit Entry( Statement *_loop, Label _breakExit, Label _contExit = Label("") ) :
-                                loop( _loop ), breakExit( _breakExit ), contExit( _contExit ), breakUsed(false), contUsed(false) {}
+                        // specialized constructors for each combination of statement with labelled break/continue/fallthrough that is valid to cleanup the use cases
+                        explicit Entry( ForStmt *stmt, Label breakExit, Label contExit ) :
+                                stmt( stmt ), breakExit( breakExit ), contExit( contExit ) {}
 
-                        bool operator==( const Statement *stmt ) { return loop == stmt; }
-                        bool operator!=( const Statement *stmt ) { return loop != stmt; }
+                        explicit Entry( WhileStmt *stmt, Label breakExit, Label contExit ) :
+                                stmt( stmt ), breakExit( breakExit ), contExit( contExit ) {}
 
-                        bool operator==( const Entry &other ) { return loop == other.get_controlStructure(); }
+                        explicit Entry( CompoundStmt *stmt, Label breakExit ) :
+                                stmt( stmt ), breakExit( breakExit ) {}
 
-                        Statement *get_controlStructure() const { return loop; }
+                        explicit Entry( IfStmt *stmt, Label breakExit ) :
+                                stmt( stmt ), breakExit( breakExit ) {}
+
+                        explicit Entry( CaseStmt *stmt, Label fallExit ) :
+                                stmt( stmt ), fallExit( fallExit ) {}
+
+                        explicit Entry( SwitchStmt *stmt, Label breakExit, Label fallDefaultExit ) :
+                                stmt( stmt ), breakExit( breakExit ), fallDefaultExit( fallDefaultExit ) {}
+
+                        bool operator==( const Statement *other ) { return stmt == other; }
+                        bool operator!=( const Statement *other ) { return stmt != other; }
+
+                        bool operator==( const Entry &other ) { return stmt == other.get_controlStructure(); }
+
+                        Statement *get_controlStructure() const { return stmt; }
 
                         Label useContExit() { contUsed = true; return contExit; }
                         Label useBreakExit() { breakUsed = true; return breakExit; }
+                        Label useFallExit() { fallUsed = true; return fallExit; }
+                        Label useFallDefaultExit() { fallDefaultUsed = true; return fallDefaultExit; }
 
                         bool isContUsed() const { return contUsed; }
                         bool isBreakUsed() const { return breakUsed; }
+                        bool isFallUsed() const { return fallUsed; }
+                        bool isFallDefaultUsed() const { return fallDefaultUsed; }
+                        void seenDefault() { fallDefaultValid = false; }
+                        bool isFallDefaultValid() const { return fallDefaultValid; }
                   private:
-                        Statement *loop;
-                        Label breakExit, contExit;
-                        bool breakUsed, contUsed;
+                        Statement *stmt;
+                        Label breakExit, contExit, fallExit, fallDefaultExit;
+                        bool breakUsed = false, contUsed = false, fallUsed = false, fallDefaultUsed = false;
+                        bool fallDefaultValid = true;
                 };
 
+          private:
                 std::map< Label, Statement * > *targetTable;
+                std::set< Label > fallthroughLabels;
                 std::list< Entry > enclosingControlStructures;
                 Label breakLabel;
@@ -87 +112 @@
                 Statement * posthandleLoopStmt( LoopClass * loopStmt );
 
-                void fixBlock( std::list< Statement * > &kids );
+                void fixBlock( std::list< Statement * > &kids, bool caseClause = false );
         };
 } // namespace ControlStruct