JumpDiagnostics.cpp revision 218893
11541Srgrimes//===--- JumpDiagnostics.cpp - Analyze Jump Targets for VLA issues --------===// 21541Srgrimes// 31541Srgrimes// The LLVM Compiler Infrastructure 41541Srgrimes// 51541Srgrimes// This file is distributed under the University of Illinois Open Source 61541Srgrimes// License. See LICENSE.TXT for details. 71541Srgrimes// 81541Srgrimes//===----------------------------------------------------------------------===// 91541Srgrimes// 101541Srgrimes// This file implements the JumpScopeChecker class, which is used to diagnose 111541Srgrimes// jumps that enter a VLA scope in an invalid way. 121541Srgrimes// 131541Srgrimes//===----------------------------------------------------------------------===// 141541Srgrimes 151541Srgrimes#include "clang/Sema/SemaInternal.h" 161541Srgrimes#include "clang/AST/DeclCXX.h" 171541Srgrimes#include "clang/AST/Expr.h" 181541Srgrimes#include "clang/AST/StmtObjC.h" 191541Srgrimes#include "clang/AST/StmtCXX.h" 201541Srgrimes#include "llvm/ADT/BitVector.h" 211541Srgrimesusing namespace clang; 221541Srgrimes 231541Srgrimesnamespace { 241541Srgrimes 251541Srgrimes/// JumpScopeChecker - This object is used by Sema to diagnose invalid jumps 261541Srgrimes/// into VLA and other protected scopes. For example, this rejects: 271541Srgrimes/// goto L; 281541Srgrimes/// int a[n]; 291541Srgrimes/// L: 301541Srgrimes/// 311541Srgrimesclass JumpScopeChecker { 321541Srgrimes Sema &S; 331541Srgrimes 3450477Speter /// GotoScope - This is a record that we use to keep track of all of the 351541Srgrimes /// scopes that are introduced by VLAs and other things that scope jumps like 361541Srgrimes /// gotos. This scope tree has nothing to do with the source scope tree, 372168Spaul /// because you can have multiple VLA scopes per compound statement, and most 384507Sbde /// compound statements don't introduce any scopes. 392168Spaul struct GotoScope { 40104355Smike /// ParentScope - The index in ScopeMap of the parent scope. This is 0 for 41104355Smike /// the parent scope is the function body. 4297024Siedowse unsigned ParentScope; 4379103Sbrooks 4497024Siedowse /// InDiag - The diagnostic to emit if there is a jump into this scope. 4579103Sbrooks unsigned InDiag; 46104355Smike 471541Srgrimes /// OutDiag - The diagnostic to emit if there is an indirect jump out 4834750Speter /// of this scope. Direct jumps always clean up their current scope 4972093Sasmodai /// in an orderly way. 5034750Speter unsigned OutDiag; 5155205Speter 5234750Speter /// Loc - Location to emit the diagnostic. 5334750Speter SourceLocation Loc; 5434750Speter 5579103Sbrooks GotoScope(unsigned parentScope, unsigned InDiag, unsigned OutDiag, 56104355Smike SourceLocation L) 5779103Sbrooks : ParentScope(parentScope), InDiag(InDiag), OutDiag(OutDiag), Loc(L) {} 5834750Speter }; 5979103Sbrooks 6079103Sbrooks llvm::SmallVector<GotoScope, 48> Scopes; 6179103Sbrooks llvm::DenseMap<Stmt*, unsigned> LabelAndGotoScopes; 62104355Smike llvm::SmallVector<Stmt*, 16> Jumps; 63104355Smike 64104355Smike llvm::SmallVector<IndirectGotoStmt*, 4> IndirectJumps; 6592081Smux llvm::SmallVector<LabelDecl*, 4> IndirectJumpTargets; 66104355Smikepublic: 6779103Sbrooks JumpScopeChecker(Stmt *Body, Sema &S); 6897024Siedowseprivate: 6979103Sbrooks void BuildScopeInformation(Decl *D, unsigned &ParentScope); 7079103Sbrooks void BuildScopeInformation(Stmt *S, unsigned ParentScope); 7179103Sbrooks void VerifyJumps(); 7279103Sbrooks void VerifyIndirectJumps(); 7379103Sbrooks void DiagnoseIndirectJump(IndirectGotoStmt *IG, unsigned IGScope, 7479103Sbrooks LabelDecl *Target, unsigned TargetScope); 7579103Sbrooks void CheckJump(Stmt *From, Stmt *To, 7697289Sbrooks SourceLocation DiagLoc, unsigned JumpDiag); 7792081Smux 7892081Smux unsigned GetDeepestCommonScope(unsigned A, unsigned B); 7992081Smux}; 8079103Sbrooks} // end anonymous namespace 8192081Smux 8297289Sbrooks 8379103SbrooksJumpScopeChecker::JumpScopeChecker(Stmt *Body, Sema &s) : S(s) { 8479103Sbrooks // Add a scope entry for function scope. 8597289Sbrooks Scopes.push_back(GotoScope(~0U, ~0U, ~0U, SourceLocation())); 8697289Sbrooks 8797024Siedowse // Build information for the top level compound statement, so that we have a 8879103Sbrooks // defined scope record for every "goto" and label. 89104355Smike BuildScopeInformation(Body, 0); 90104355Smike 9179103Sbrooks // Check that all jumps we saw are kosher. 9279103Sbrooks VerifyJumps(); 9379103Sbrooks VerifyIndirectJumps(); 9479103Sbrooks} 9579103Sbrooks 9679103Sbrooks/// GetDeepestCommonScope - Finds the innermost scope enclosing the 9779103Sbrooks/// two scopes. 9879103Sbrooksunsigned JumpScopeChecker::GetDeepestCommonScope(unsigned A, unsigned B) { 9979103Sbrooks while (A != B) { 10079103Sbrooks // Inner scopes are created after outer scopes and therefore have 10179103Sbrooks // higher indices. 10219079Sfenner if (A < B) { 10319079Sfenner assert(Scopes[B].ParentScope < B); 10419079Sfenner B = Scopes[B].ParentScope; 1059457Sjoerg } else { 1069457Sjoerg assert(Scopes[A].ParentScope < A); 1079457Sjoerg A = Scopes[A].ParentScope; 1089457Sjoerg } 1099457Sjoerg } 1109457Sjoerg return A; 11117352Swollman} 11217352Swollman 1139457Sjoerg/// GetDiagForGotoScopeDecl - If this decl induces a new goto scope, return a 1149457Sjoerg/// diagnostic that should be emitted if control goes over it. If not, return 0. 1159457Sjoergstatic std::pair<unsigned,unsigned> 1169457Sjoerg GetDiagForGotoScopeDecl(const Decl *D, bool isCPlusPlus) { 1179457Sjoerg if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 1189457Sjoerg unsigned InDiag = 0, OutDiag = 0; 1199457Sjoerg if (VD->getType()->isVariablyModifiedType()) 1209457Sjoerg InDiag = diag::note_protected_by_vla; 1219457Sjoerg 1229457Sjoerg if (VD->hasAttr<BlocksAttr>()) { 1239457Sjoerg InDiag = diag::note_protected_by___block; 1249457Sjoerg OutDiag = diag::note_exits___block; 1259457Sjoerg } else if (VD->hasAttr<CleanupAttr>()) { 1269457Sjoerg InDiag = diag::note_protected_by_cleanup; 1279457Sjoerg OutDiag = diag::note_exits_cleanup; 12858698Sjlemon } else if (isCPlusPlus) { 12958698Sjlemon // FIXME: In C++0x, we have to check more conditions than "did we 13016287Sgpalmer // just give it an initializer?". See 6.7p3. 1319457Sjoerg if (VD->hasLocalStorage() && VD->hasInit()) 1329457Sjoerg InDiag = diag::note_protected_by_variable_init; 1331541Srgrimes 1341541Srgrimes CanQualType T = VD->getType()->getCanonicalTypeUnqualified(); 1351541Srgrimes if (!T->isDependentType()) { 1361541Srgrimes while (CanQual<ArrayType> AT = T->getAs<ArrayType>()) 1371541Srgrimes T = AT->getElementType(); 13847777Sphk if (CanQual<RecordType> RT = T->getAs<RecordType>()) 1391541Srgrimes if (!cast<CXXRecordDecl>(RT->getDecl())->hasTrivialDestructor()) 1401541Srgrimes OutDiag = diag::note_exits_dtor; 1411541Srgrimes } 1421541Srgrimes } 1431541Srgrimes 1441541Srgrimes return std::make_pair(InDiag, OutDiag); 1451541Srgrimes } 1461541Srgrimes 1471541Srgrimes if (const TypedefDecl *TD = dyn_cast<TypedefDecl>(D)) { 1483274Swollman if (TD->getUnderlyingType()->isVariablyModifiedType()) 1491541Srgrimes return std::make_pair((unsigned) diag::note_protected_by_vla_typedef, 0); 15087902Sluigi } 151102099Ssobomax 152104044Sphk return std::make_pair(0U, 0U); 15387902Sluigi} 1541541Srgrimes 1551541Srgrimes/// \brief Build scope information for a declaration that is part of a DeclStmt. 1561541Srgrimesvoid JumpScopeChecker::BuildScopeInformation(Decl *D, unsigned &ParentScope) { 157102526Ssobomax bool isCPlusPlus = this->S.getLangOptions().CPlusPlus; 158102526Ssobomax 1591541Srgrimes // If this decl causes a new scope, push and switch to it. 16083624Sjlemon std::pair<unsigned,unsigned> Diags 16183636Sjlemon = GetDiagForGotoScopeDecl(D, isCPlusPlus); 16283636Sjlemon if (Diags.first || Diags.second) { 16383636Sjlemon Scopes.push_back(GotoScope(ParentScope, Diags.first, Diags.second, 16483624Sjlemon D->getLocation())); 16583636Sjlemon ParentScope = Scopes.size()-1; 16683636Sjlemon } 1671541Srgrimes 1681541Srgrimes // If the decl has an initializer, walk it with the potentially new 1691541Srgrimes // scope we just installed. 1701541Srgrimes if (VarDecl *VD = dyn_cast<VarDecl>(D)) 1711541Srgrimes if (Expr *Init = VD->getInit()) 1721541Srgrimes BuildScopeInformation(Init, ParentScope); 1731541Srgrimes} 1741541Srgrimes 1751541Srgrimes/// BuildScopeInformation - The statements from CI to CE are known to form a 17672093Sasmodai/// coherent VLA scope with a specified parent node. Walk through the 1771541Srgrimes/// statements, adding any labels or gotos to LabelAndGotoScopes and recursively 1781541Srgrimes/// walking the AST as needed. 1791541Srgrimesvoid JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { 1801541Srgrimes bool SkipFirstSubStmt = false; 1811541Srgrimes 1821541Srgrimes // If we found a label, remember that it is in ParentScope scope. 1831541Srgrimes switch (S->getStmtClass()) { 1841541Srgrimes case Stmt::AddrLabelExprClass: 1851541Srgrimes IndirectJumpTargets.push_back(cast<AddrLabelExpr>(S)->getLabel()); 1861541Srgrimes break; 1871541Srgrimes 1881541Srgrimes case Stmt::IndirectGotoStmtClass: 1891541Srgrimes // "goto *&&lbl;" is a special case which we treat as equivalent 19072093Sasmodai // to a normal goto. In addition, we don't calculate scope in the 1911541Srgrimes // operand (to avoid recording the address-of-label use), which 1921541Srgrimes // works only because of the restricted set of expressions which 1931541Srgrimes // we detect as constant targets. 1941541Srgrimes if (cast<IndirectGotoStmt>(S)->getConstantTarget()) { 1951541Srgrimes LabelAndGotoScopes[S] = ParentScope; 1961541Srgrimes Jumps.push_back(S); 1971541Srgrimes return; 1981541Srgrimes } 19921666Swollman 20021666Swollman LabelAndGotoScopes[S] = ParentScope; 20121666Swollman IndirectJumps.push_back(cast<IndirectGotoStmt>(S)); 20221666Swollman break; 20321666Swollman 20472093Sasmodai case Stmt::SwitchStmtClass: 20521666Swollman // Evaluate the condition variable before entering the scope of the switch 20621666Swollman // statement. 20721666Swollman if (VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) { 20821666Swollman BuildScopeInformation(Var, ParentScope); 20921666Swollman SkipFirstSubStmt = true; 21021666Swollman } 21121666Swollman // Fall through 21289498Sru 21389498Sru case Stmt::GotoStmtClass: 21489498Sru // Remember both what scope a goto is in as well as the fact that we have 21589498Sru // it. This makes the second scan not have to walk the AST again. 21689498Sru LabelAndGotoScopes[S] = ParentScope; 21789498Sru Jumps.push_back(S); 21889498Sru break; 21989498Sru 22089498Sru default: 22189498Sru break; 22289498Sru } 22389498Sru 22489498Sru for (Stmt::child_range CI = S->children(); CI; ++CI) { 22589498Sru if (SkipFirstSubStmt) { 22689498Sru SkipFirstSubStmt = false; 2271541Srgrimes continue; 2281541Srgrimes } 2291541Srgrimes 2301541Srgrimes Stmt *SubStmt = *CI; 2311541Srgrimes if (SubStmt == 0) continue; 2321541Srgrimes 2331541Srgrimes // Cases, labels, and defaults aren't "scope parents". It's also 2341541Srgrimes // important to handle these iteratively instead of recursively in 2351541Srgrimes // order to avoid blowing out the stack. 2361541Srgrimes while (true) { 2371541Srgrimes Stmt *Next; 23844144Sphk if (CaseStmt *CS = dyn_cast<CaseStmt>(SubStmt)) 23985079Sjlemon Next = CS->getSubStmt(); 2401541Srgrimes else if (DefaultStmt *DS = dyn_cast<DefaultStmt>(SubStmt)) 2411941Sdg Next = DS->getSubStmt(); 2425184Swollman else if (LabelStmt *LS = dyn_cast<LabelStmt>(SubStmt)) 24325434Speter Next = LS->getSubStmt(); 2441541Srgrimes else 24583624Sjlemon break; 2461541Srgrimes 2471541Srgrimes LabelAndGotoScopes[SubStmt] = ParentScope; 2481541Srgrimes SubStmt = Next; 2491541Srgrimes } 250102052Ssobomax 251102052Ssobomax // If this is a declstmt with a VLA definition, it defines a scope from here 2521541Srgrimes // to the end of the containing context. 2531941Sdg if (DeclStmt *DS = dyn_cast<DeclStmt>(SubStmt)) { 2545187Sdg // The decl statement creates a scope if any of the decls in it are VLAs 25525434Speter // or have the cleanup attribute. 2561541Srgrimes for (DeclStmt::decl_iterator I = DS->decl_begin(), E = DS->decl_end(); 25783624Sjlemon I != E; ++I) 25883624Sjlemon BuildScopeInformation(*I, ParentScope); 25985079Sjlemon continue; 2601541Srgrimes } 2611541Srgrimes 26232491Swollman // Disallow jumps into any part of an @try statement by pushing a scope and 26332491Swollman // walking all sub-stmts in that scope. 26432491Swollman if (ObjCAtTryStmt *AT = dyn_cast<ObjCAtTryStmt>(SubStmt)) { 26532491Swollman // Recursively walk the AST for the @try part. 26632491Swollman Scopes.push_back(GotoScope(ParentScope, 2671541Srgrimes diag::note_protected_by_objc_try, 2681541Srgrimes diag::note_exits_objc_try, 2691541Srgrimes AT->getAtTryLoc())); 2701541Srgrimes if (Stmt *TryPart = AT->getTryBody()) 2711541Srgrimes BuildScopeInformation(TryPart, Scopes.size()-1); 2721541Srgrimes 2731541Srgrimes // Jump from the catch to the finally or try is not valid. 27425434Speter for (unsigned I = 0, N = AT->getNumCatchStmts(); I != N; ++I) { 27525434Speter ObjCAtCatchStmt *AC = AT->getCatchStmt(I); 27625434Speter Scopes.push_back(GotoScope(ParentScope, 27725434Speter diag::note_protected_by_objc_catch, 27825434Speter diag::note_exits_objc_catch, 27925434Speter AC->getAtCatchLoc())); 28025434Speter // @catches are nested and it isn't 28125434Speter BuildScopeInformation(AC->getCatchBody(), Scopes.size()-1); 28225434Speter } 28348021Sphk 28448021Sphk // Jump from the finally to the try or catch is not valid. 28548021Sphk if (ObjCAtFinallyStmt *AF = AT->getFinallyStmt()) { 28648589Sbde Scopes.push_back(GotoScope(ParentScope, 28748021Sphk diag::note_protected_by_objc_finally, 28848589Sbde diag::note_exits_objc_finally, 28948021Sphk AF->getAtFinallyLoc())); 29048021Sphk BuildScopeInformation(AF, Scopes.size()-1); 29148589Sbde } 29248021Sphk 29348589Sbde continue; 29448589Sbde } 29548021Sphk 29648021Sphk // Disallow jumps into the protected statement of an @synchronized, but 2971541Srgrimes // allow jumps into the object expression it protects. 2981541Srgrimes if (ObjCAtSynchronizedStmt *AS = dyn_cast<ObjCAtSynchronizedStmt>(SubStmt)){ 2991541Srgrimes // Recursively walk the AST for the @synchronized object expr, it is 3001541Srgrimes // evaluated in the normal scope. 3011541Srgrimes BuildScopeInformation(AS->getSynchExpr(), ParentScope); 3021541Srgrimes 3031541Srgrimes // Recursively walk the AST for the @synchronized part, protected by a new 3041541Srgrimes // scope. 3051541Srgrimes Scopes.push_back(GotoScope(ParentScope, 3061541Srgrimes diag::note_protected_by_objc_synchronized, 3071541Srgrimes diag::note_exits_objc_synchronized, 3081541Srgrimes AS->getAtSynchronizedLoc())); 3091541Srgrimes BuildScopeInformation(AS->getSynchBody(), Scopes.size()-1); 3101541Srgrimes continue; 3111541Srgrimes } 3121541Srgrimes 31352904Sshin // Disallow jumps into any part of a C++ try statement. This is pretty 31452904Sshin // much the same as for Obj-C. 31552904Sshin if (CXXTryStmt *TS = dyn_cast<CXXTryStmt>(SubStmt)) { 31652904Sshin Scopes.push_back(GotoScope(ParentScope, 31752904Sshin diag::note_protected_by_cxx_try, 31852904Sshin diag::note_exits_cxx_try, 31952904Sshin TS->getSourceRange().getBegin())); 32052904Sshin if (Stmt *TryBlock = TS->getTryBlock()) 32152904Sshin BuildScopeInformation(TryBlock, Scopes.size()-1); 32252904Sshin 32352904Sshin // Jump from the catch into the try is not allowed either. 32452904Sshin for (unsigned I = 0, E = TS->getNumHandlers(); I != E; ++I) { 32552904Sshin CXXCatchStmt *CS = TS->getHandler(I); 326104355Smike Scopes.push_back(GotoScope(ParentScope, 327104355Smike diag::note_protected_by_cxx_catch, 32855205Speter diag::note_exits_cxx_catch, 32930354Sphk CS->getSourceRange().getBegin())); 33030354Sphk BuildScopeInformation(CS->getHandlerBlock(), Scopes.size()-1); 33130354Sphk } 33230354Sphk 33330354Sphk continue; 33430354Sphk } 33555205Speter 33652904Sshin // Recursively walk the AST. 337104355Smike BuildScopeInformation(SubStmt, ParentScope); 338104360Smike } 33952904Sshin} 34052904Sshin 34152904Sshin/// VerifyJumps - Verify each element of the Jumps array to see if they are 342104360Smike/// valid, emitting diagnostics if not. 343104360Smikevoid JumpScopeChecker::VerifyJumps() { 344104360Smike while (!Jumps.empty()) { 345104360Smike Stmt *Jump = Jumps.pop_back_val(); 34652904Sshin 34752904Sshin // With a goto, 34852904Sshin if (GotoStmt *GS = dyn_cast<GotoStmt>(Jump)) { 34955205Speter CheckJump(GS, GS->getLabel()->getStmt(), GS->getGotoLoc(), 35083366Sjulian diag::err_goto_into_protected_scope); 35148589Sbde continue; 35248589Sbde } 35321259Swollman 3541541Srgrimes // We only get indirect gotos here when they have a constant target. 3551541Srgrimes if (IndirectGotoStmt *IGS = dyn_cast<IndirectGotoStmt>(Jump)) { 3564507Sbde LabelDecl *Target = IGS->getConstantTarget(); 357 CheckJump(IGS, Target->getStmt(), IGS->getGotoLoc(), 358 diag::err_goto_into_protected_scope); 359 continue; 360 } 361 362 SwitchStmt *SS = cast<SwitchStmt>(Jump); 363 for (SwitchCase *SC = SS->getSwitchCaseList(); SC; 364 SC = SC->getNextSwitchCase()) { 365 assert(LabelAndGotoScopes.count(SC) && "Case not visited?"); 366 CheckJump(SS, SC, SC->getLocStart(), 367 diag::err_switch_into_protected_scope); 368 } 369 } 370} 371 372/// VerifyIndirectJumps - Verify whether any possible indirect jump 373/// might cross a protection boundary. Unlike direct jumps, indirect 374/// jumps count cleanups as protection boundaries: since there's no 375/// way to know where the jump is going, we can't implicitly run the 376/// right cleanups the way we can with direct jumps. 377/// 378/// Thus, an indirect jump is "trivial" if it bypasses no 379/// initializations and no teardowns. More formally, an indirect jump 380/// from A to B is trivial if the path out from A to DCA(A,B) is 381/// trivial and the path in from DCA(A,B) to B is trivial, where 382/// DCA(A,B) is the deepest common ancestor of A and B. 383/// Jump-triviality is transitive but asymmetric. 384/// 385/// A path in is trivial if none of the entered scopes have an InDiag. 386/// A path out is trivial is none of the exited scopes have an OutDiag. 387/// 388/// Under these definitions, this function checks that the indirect 389/// jump between A and B is trivial for every indirect goto statement A 390/// and every label B whose address was taken in the function. 391void JumpScopeChecker::VerifyIndirectJumps() { 392 if (IndirectJumps.empty()) return; 393 394 // If there aren't any address-of-label expressions in this function, 395 // complain about the first indirect goto. 396 if (IndirectJumpTargets.empty()) { 397 S.Diag(IndirectJumps[0]->getGotoLoc(), 398 diag::err_indirect_goto_without_addrlabel); 399 return; 400 } 401 402 // Collect a single representative of every scope containing an 403 // indirect goto. For most code bases, this substantially cuts 404 // down on the number of jump sites we'll have to consider later. 405 typedef std::pair<unsigned, IndirectGotoStmt*> JumpScope; 406 llvm::SmallVector<JumpScope, 32> JumpScopes; 407 { 408 llvm::DenseMap<unsigned, IndirectGotoStmt*> JumpScopesMap; 409 for (llvm::SmallVectorImpl<IndirectGotoStmt*>::iterator 410 I = IndirectJumps.begin(), E = IndirectJumps.end(); I != E; ++I) { 411 IndirectGotoStmt *IG = *I; 412 assert(LabelAndGotoScopes.count(IG) && 413 "indirect jump didn't get added to scopes?"); 414 unsigned IGScope = LabelAndGotoScopes[IG]; 415 IndirectGotoStmt *&Entry = JumpScopesMap[IGScope]; 416 if (!Entry) Entry = IG; 417 } 418 JumpScopes.reserve(JumpScopesMap.size()); 419 for (llvm::DenseMap<unsigned, IndirectGotoStmt*>::iterator 420 I = JumpScopesMap.begin(), E = JumpScopesMap.end(); I != E; ++I) 421 JumpScopes.push_back(*I); 422 } 423 424 // Collect a single representative of every scope containing a 425 // label whose address was taken somewhere in the function. 426 // For most code bases, there will be only one such scope. 427 llvm::DenseMap<unsigned, LabelDecl*> TargetScopes; 428 for (llvm::SmallVectorImpl<LabelDecl*>::iterator 429 I = IndirectJumpTargets.begin(), E = IndirectJumpTargets.end(); 430 I != E; ++I) { 431 LabelDecl *TheLabel = *I; 432 assert(LabelAndGotoScopes.count(TheLabel->getStmt()) && 433 "Referenced label didn't get added to scopes?"); 434 unsigned LabelScope = LabelAndGotoScopes[TheLabel->getStmt()]; 435 LabelDecl *&Target = TargetScopes[LabelScope]; 436 if (!Target) Target = TheLabel; 437 } 438 439 // For each target scope, make sure it's trivially reachable from 440 // every scope containing a jump site. 441 // 442 // A path between scopes always consists of exitting zero or more 443 // scopes, then entering zero or more scopes. We build a set of 444 // of scopes S from which the target scope can be trivially 445 // entered, then verify that every jump scope can be trivially 446 // exitted to reach a scope in S. 447 llvm::BitVector Reachable(Scopes.size(), false); 448 for (llvm::DenseMap<unsigned,LabelDecl*>::iterator 449 TI = TargetScopes.begin(), TE = TargetScopes.end(); TI != TE; ++TI) { 450 unsigned TargetScope = TI->first; 451 LabelDecl *TargetLabel = TI->second; 452 453 Reachable.reset(); 454 455 // Mark all the enclosing scopes from which you can safely jump 456 // into the target scope. 'Min' will end up being the index of 457 // the shallowest such scope. 458 unsigned Min = TargetScope; 459 while (true) { 460 Reachable.set(Min); 461 462 // Don't go beyond the outermost scope. 463 if (Min == 0) break; 464 465 // Stop if we can't trivially enter the current scope. 466 if (Scopes[Min].InDiag) break; 467 468 Min = Scopes[Min].ParentScope; 469 } 470 471 // Walk through all the jump sites, checking that they can trivially 472 // reach this label scope. 473 for (llvm::SmallVectorImpl<JumpScope>::iterator 474 I = JumpScopes.begin(), E = JumpScopes.end(); I != E; ++I) { 475 unsigned Scope = I->first; 476 477 // Walk out the "scope chain" for this scope, looking for a scope 478 // we've marked reachable. For well-formed code this amortizes 479 // to O(JumpScopes.size() / Scopes.size()): we only iterate 480 // when we see something unmarked, and in well-formed code we 481 // mark everything we iterate past. 482 bool IsReachable = false; 483 while (true) { 484 if (Reachable.test(Scope)) { 485 // If we find something reachable, mark all the scopes we just 486 // walked through as reachable. 487 for (unsigned S = I->first; S != Scope; S = Scopes[S].ParentScope) 488 Reachable.set(S); 489 IsReachable = true; 490 break; 491 } 492 493 // Don't walk out if we've reached the top-level scope or we've 494 // gotten shallower than the shallowest reachable scope. 495 if (Scope == 0 || Scope < Min) break; 496 497 // Don't walk out through an out-diagnostic. 498 if (Scopes[Scope].OutDiag) break; 499 500 Scope = Scopes[Scope].ParentScope; 501 } 502 503 // Only diagnose if we didn't find something. 504 if (IsReachable) continue; 505 506 DiagnoseIndirectJump(I->second, I->first, TargetLabel, TargetScope); 507 } 508 } 509} 510 511/// Diagnose an indirect jump which is known to cross scopes. 512void JumpScopeChecker::DiagnoseIndirectJump(IndirectGotoStmt *Jump, 513 unsigned JumpScope, 514 LabelDecl *Target, 515 unsigned TargetScope) { 516 assert(JumpScope != TargetScope); 517 518 S.Diag(Jump->getGotoLoc(), diag::err_indirect_goto_in_protected_scope); 519 S.Diag(Target->getStmt()->getIdentLoc(), diag::note_indirect_goto_target); 520 521 unsigned Common = GetDeepestCommonScope(JumpScope, TargetScope); 522 523 // Walk out the scope chain until we reach the common ancestor. 524 for (unsigned I = JumpScope; I != Common; I = Scopes[I].ParentScope) 525 if (Scopes[I].OutDiag) 526 S.Diag(Scopes[I].Loc, Scopes[I].OutDiag); 527 528 // Now walk into the scopes containing the label whose address was taken. 529 for (unsigned I = TargetScope; I != Common; I = Scopes[I].ParentScope) 530 if (Scopes[I].InDiag) 531 S.Diag(Scopes[I].Loc, Scopes[I].InDiag); 532} 533 534/// CheckJump - Validate that the specified jump statement is valid: that it is 535/// jumping within or out of its current scope, not into a deeper one. 536void JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, 537 SourceLocation DiagLoc, unsigned JumpDiag) { 538 assert(LabelAndGotoScopes.count(From) && "Jump didn't get added to scopes?"); 539 unsigned FromScope = LabelAndGotoScopes[From]; 540 541 assert(LabelAndGotoScopes.count(To) && "Jump didn't get added to scopes?"); 542 unsigned ToScope = LabelAndGotoScopes[To]; 543 544 // Common case: exactly the same scope, which is fine. 545 if (FromScope == ToScope) return; 546 547 unsigned CommonScope = GetDeepestCommonScope(FromScope, ToScope); 548 549 // It's okay to jump out from a nested scope. 550 if (CommonScope == ToScope) return; 551 552 // Pull out (and reverse) any scopes we might need to diagnose skipping. 553 llvm::SmallVector<unsigned, 10> ToScopes; 554 for (unsigned I = ToScope; I != CommonScope; I = Scopes[I].ParentScope) 555 if (Scopes[I].InDiag) 556 ToScopes.push_back(I); 557 558 // If the only scopes present are cleanup scopes, we're okay. 559 if (ToScopes.empty()) return; 560 561 S.Diag(DiagLoc, JumpDiag); 562 563 // Emit diagnostics for whatever is left in ToScopes. 564 for (unsigned i = 0, e = ToScopes.size(); i != e; ++i) 565 S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].InDiag); 566} 567 568void Sema::DiagnoseInvalidJumps(Stmt *Body) { 569 (void)JumpScopeChecker(Body, *this); 570} 571