source: src/ControlStruct/MLEMutator.cc @ 9bdb8b7

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 9bdb8b7 was 9bdb8b7, checked in by Peter A. Buhr <pabuhr@…>, 2 years ago

allow labelled break from within the body of a try statement

  • Property mode set to 100644
File size: 17.6 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// MLEMutator.cc --
8//
9// Author           : Rodolfo G. Esteves
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Tue Oct 22 17:22:44 2019
13// Update Count     : 220
14//
15
16// NOTE: There are two known subtle differences from the code that uC++ generates for the same input
17//   -CFA puts the break label inside at the end of a switch, uC++ puts it after
18//   -CFA puts the break label after a block, uC++ puts it inside at the end
19// It is unclear if these differences are important, but if they are, then the fix would go in this file, since this is
20// where these labels are generated.
21
22#include <ext/alloc_traits.h>              // for __alloc_traits<>::value_type
23#include <algorithm>                       // for find, find_if
24#include <cassert>                         // for assert, assertf
25#include <memory>                          // for allocator_traits<>::value_...
26
27#include "Common/utility.h"                // for toString, operator+
28#include "ControlStruct/LabelGenerator.h"  // for LabelGenerator
29#include "MLEMutator.h"
30#include "SynTree/Attribute.h"             // for Attribute
31#include "SynTree/Expression.h"            // for Expression
32#include "SynTree/Statement.h"             // for BranchStmt, CompoundStmt
33
34namespace ControlStruct {
35        MLEMutator::~MLEMutator() {
36                delete targetTable;
37                targetTable = 0;
38        }
39        namespace {
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
48
49        // break labels have to come after the statement they break out of, so mutate a statement, then if they inform us
50        // through the breakLabel field tha they need a place to jump to on a break statement, add the break label to the
51        // body of statements
52        void MLEMutator::fixBlock( std::list< Statement * > &kids, bool caseClause ) {
53                SemanticErrorException errors;
54
55                for ( std::list< Statement * >::iterator k = kids.begin(); k != kids.end(); k++ ) {
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                        }
69
70                        if ( ! get_breakLabel().empty() ) {
71                                std::list< Statement * >::iterator next = k+1;
72                                std::list<Label> ls; ls.push_back( get_breakLabel() );
73                                kids.insert( next, new NullStmt( ls ) );
74                                set_breakLabel("");
75                        } // if
76                } // for
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());
86                if ( labeledBlock ) {
87                        Label brkLabel = generator->newLabel("blockBreak", cmpndStmt);
88                        enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
89                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
90                } // if
91
92                // a child statement may set the break label - if they do, attach it to the next statement
93                std::list< Statement * > &kids = cmpndStmt->kids;
94                fixBlock( kids );
95
96                if ( labeledBlock ) {
97                        assert( ! enclosingControlStructures.empty() );
98                        if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
99                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
100                        } // if
101                } // if
102        }
103
104
105        void addUnused( Statement * stmt, const Label & originalTarget ) {
106                // break/continue without a label doesn't need unused attribute
107                if ( originalTarget == "" ) return;
108                // add unused attribute to the originalTarget of a labelled break/continue
109                for ( Label & l : stmt->get_labels() ) {
110                        // find the label to add unused attribute to
111                        if ( l == originalTarget ) {
112                                for ( Attribute * attr : l.get_attributes() ) {
113                                        // ensure attribute isn't added twice
114                                        if ( attr->get_name() == "unused" ) return;
115                                }
116                                l.get_attributes().push_back( new Attribute( "unused" ) );
117                                return;
118                        }
119                }
120                assertf( false, "Could not find label '%s' on statement %s", originalTarget.get_name().c_str(), toString( stmt ).c_str() );
121        }
122
123
124        Statement *MLEMutator::postmutate( BranchStmt *branchStmt ) throw ( SemanticErrorException ) {
125                std::string originalTarget = branchStmt->originalTarget;
126
127                std::list< Entry >::reverse_iterator targetEntry;
128                switch ( branchStmt->get_type() ) {
129                        case BranchStmt::Goto:
130                                return branchStmt;
131                        case BranchStmt::Continue:
132                        case BranchStmt::Break: {
133                                bool isContinue = branchStmt->get_type() == BranchStmt::Continue;
134                                // unlabeled break/continue
135                                if ( branchStmt->get_target() == "" ) {
136                                        if ( isContinue ) {
137                                                // continue target is outermost loop
138                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isContinueTarget );
139                                        } else {
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 );
143                                        } // if
144                                } else {
145                                        // labeled break/continue - lookup label in table to find attached control structure
146                                        targetEntry = std::find( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), (*targetTable)[branchStmt->get_target()] );
147                                } // if
148                                // ensure that selected target is valid
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 ) );
151                                } // if
152                                break;
153                        }
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
193                        default:
194                                assert( false );
195                } // switch
196
197                // branch error checks, get the appropriate label name and create a goto
198                Label exitLabel;
199                switch ( branchStmt->type ) {
200                  case BranchStmt::Break:
201                                assert( targetEntry->useBreakExit() != "");
202                                exitLabel = targetEntry->useBreakExit();
203                                break;
204                  case BranchStmt::Continue:
205                                assert( targetEntry->useContExit() != "");
206                                exitLabel = targetEntry->useContExit();
207                                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;
220                  default:
221                                assert(0);                                      // shouldn't be here
222                } // switch
223
224                // add unused attribute to label to silence warnings
225                addUnused( targetEntry->get_controlStructure(), branchStmt->originalTarget );
226
227                // transform break/continue statements into goto to simplify later handling of branches
228                delete branchStmt;
229                return new BranchStmt( exitLabel, BranchStmt::Goto );
230        }
231
232        Statement *MLEMutator::mutateLoop( Statement *bodyLoop, Entry &e ) {
233                // ensure loop body is a block
234                CompoundStmt *newBody;
235                if ( ! (newBody = dynamic_cast<CompoundStmt *>( bodyLoop )) ) {
236                        newBody = new CompoundStmt();
237                        newBody->get_kids().push_back( bodyLoop );
238                } // if
239
240                // only generate these when needed
241
242                if ( e.isContUsed() ) {
243                        // continue label goes in the body as the last statement
244                        std::list< Label > labels; labels.push_back( e.useContExit() );
245                        newBody->get_kids().push_back( new NullStmt( labels ) );
246                } // if
247
248                if ( e.isBreakUsed() ) {
249                        // break label goes after the loop -- it'll get set by the outer mutator if we do this
250                        set_breakLabel( e.useBreakExit() );
251                } // if
252
253                return newBody;
254        }
255
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( TryStmt * tryStmt ) {
316                // generate a label for breaking out of a labeled if
317                bool labeledBlock = !(tryStmt->get_labels().empty());
318                if ( labeledBlock ) {
319                        Label brkLabel = generator->newLabel("blockBreak", tryStmt);
320                        enclosingControlStructures.push_back( Entry( tryStmt, brkLabel ) );
321                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
322                } // if
323        }
324
325        Statement * MLEMutator::postmutate( TryStmt * tryStmt ) {
326                bool labeledBlock = !(tryStmt->get_labels().empty());
327                if ( labeledBlock ) {
328                        if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
329                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
330                        } // if
331                } // if
332                return tryStmt;
333        }
334
335        void MLEMutator::premutate( CaseStmt *caseStmt ) {
336                visit_children = false;
337
338                // mark default as seen before visiting its statements to catch default loops
339                if ( caseStmt->isDefault() ) {
340                        enclosingControlStructures.back().seenDefault();
341                } // if
342
343                caseStmt->condition = maybeMutate( caseStmt->condition, *visitor );
344                Label fallLabel = generator->newLabel( "fallThrough", caseStmt );
345                {
346                        // ensure that stack isn't corrupted by exceptions in fixBlock
347                        auto guard = makeFuncGuard( [&]() { enclosingControlStructures.push_back( Entry( caseStmt, fallLabel ) ); }, [this]() { enclosingControlStructures.pop_back(); } );
348
349                        // empty case statement
350                        if( ! caseStmt->stmts.empty() ) {
351                                // the parser ensures that all statements in a case are grouped into a block
352                                CompoundStmt * block = strict_dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
353                                fixBlock( block->kids, true );
354
355                                // add fallthrough label if necessary
356                                assert( ! enclosingControlStructures.empty() );
357                                if ( enclosingControlStructures.back().isFallUsed() ) {
358                                        std::list<Label> ls{ enclosingControlStructures.back().useFallExit() };
359                                        caseStmt->stmts.push_back( new NullStmt( ls ) );
360                                } // if
361                        } // if
362                }
363                assert( ! enclosingControlStructures.empty() );
364                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() ) );
365                if ( caseStmt->isDefault() ) {
366                        if ( enclosingControlStructures.back().isFallDefaultUsed() ) {
367                                // add fallthrough default label if necessary
368                                std::list<Label> ls{ enclosingControlStructures.back().useFallDefaultExit() };
369                                caseStmt->stmts.push_front( new NullStmt( ls ) );
370                        } // if
371                } // if
372        }
373
374        void MLEMutator::premutate( SwitchStmt *switchStmt ) {
375                // generate a label for breaking out of a labeled switch
376                Label brkLabel = generator->newLabel("switchBreak", switchStmt);
377                auto it = std::find_if( switchStmt->statements.rbegin(), switchStmt->statements.rend(), [](Statement * stmt) {
378                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
379                        return caseStmt->isDefault();
380                });
381                CaseStmt * defaultCase = it != switchStmt->statements.rend() ? strict_dynamic_cast<CaseStmt *>( *it ) : nullptr;
382                Label fallDefaultLabel = defaultCase ? generator->newLabel( "fallThroughDefault", defaultCase ) : "";
383                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel, fallDefaultLabel) );
384                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
385
386                // Collect valid labels for fallthrough. This is initially all labels at the same level as a case statement.
387                // As labels are seen during traversal, they are removed, since fallthrough is not allowed to jump backwards.
388                for ( Statement * stmt : switchStmt->statements ) {
389                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
390                        if ( caseStmt->stmts.empty() ) continue;
391                        CompoundStmt * block = dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
392                        for ( Statement * stmt : block->kids ) {
393                                for ( Label & l : stmt->labels ) {
394                                        fallthroughLabels.insert( l );
395                                }
396                        }
397                }
398        }
399
400        Statement * MLEMutator::postmutate( SwitchStmt * switchStmt ) {
401                Entry &e = enclosingControlStructures.back();
402                assert ( e == switchStmt );
403
404                // only generate break label if labeled break is used
405                if ( e.isBreakUsed() ) {
406                        // for the purposes of keeping switch statements uniform (i.e. all statements that are direct children of a
407                        // switch should be CastStmts), append the exit label + break to the last case statement; create a default
408                        // case if there are no cases
409                        std::list< Statement * > &statements = switchStmt->statements;
410                        if ( statements.empty() ) {
411                                statements.push_back( CaseStmt::makeDefault() );
412                        } // if
413
414                        if ( CaseStmt * c = dynamic_cast< CaseStmt * >( statements.back() ) ) {
415                                Statement * stmt = new BranchStmt( Label("brkLabel"), BranchStmt::Break );
416                                stmt->labels.push_back( e.useBreakExit() );
417                                c->stmts.push_back( stmt );
418                        } else assert(0); // as of this point, all statements of a switch are still CaseStmts
419                } // if
420
421                assert ( enclosingControlStructures.back() == switchStmt );
422                return switchStmt;
423        }
424} // namespace ControlStruct
425
426// Local Variables: //
427// tab-width: 4 //
428// mode: c++ //
429// compile-command: "make install" //
430// End: //
Note: See TracBrowser for help on using the repository browser.