JumpDiagnostics.cpp revision c0e51be6ec0f57f9caaf16bdd3ef20a8b37466c9
1//===--- JumpDiagnostics.cpp - Analyze Jump Targets for VLA issues --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the JumpScopeChecker class, which is used to diagnose 11// jumps that enter a VLA scope in an invalid way. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/Sema/Sema.h" 16#include "clang/AST/Expr.h" 17#include "clang/AST/StmtObjC.h" 18#include "clang/AST/StmtCXX.h" 19#include "llvm/ADT/BitVector.h" 20using namespace clang; 21 22namespace { 23 24/// JumpScopeChecker - This object is used by Sema to diagnose invalid jumps 25/// into VLA and other protected scopes. For example, this rejects: 26/// goto L; 27/// int a[n]; 28/// L: 29/// 30class JumpScopeChecker { 31 Sema &S; 32 33 /// GotoScope - This is a record that we use to keep track of all of the 34 /// scopes that are introduced by VLAs and other things that scope jumps like 35 /// gotos. This scope tree has nothing to do with the source scope tree, 36 /// because you can have multiple VLA scopes per compound statement, and most 37 /// compound statements don't introduce any scopes. 38 struct GotoScope { 39 /// ParentScope - The index in ScopeMap of the parent scope. This is 0 for 40 /// the parent scope is the function body. 41 unsigned ParentScope; 42 43 /// InDiag - The diagnostic to emit if there is a jump into this scope. 44 unsigned InDiag; 45 46 /// OutDiag - The diagnostic to emit if there is an indirect jump out 47 /// of this scope. Direct jumps always clean up their current scope 48 /// in an orderly way. 49 unsigned OutDiag; 50 51 /// Loc - Location to emit the diagnostic. 52 SourceLocation Loc; 53 54 GotoScope(unsigned parentScope, unsigned InDiag, unsigned OutDiag, 55 SourceLocation L) 56 : ParentScope(parentScope), InDiag(InDiag), OutDiag(OutDiag), Loc(L) {} 57 }; 58 59 llvm::SmallVector<GotoScope, 48> Scopes; 60 llvm::DenseMap<Stmt*, unsigned> LabelAndGotoScopes; 61 llvm::SmallVector<Stmt*, 16> Jumps; 62 63 llvm::SmallVector<IndirectGotoStmt*, 4> IndirectJumps; 64 llvm::SmallVector<LabelStmt*, 4> IndirectJumpTargets; 65public: 66 JumpScopeChecker(Stmt *Body, Sema &S); 67private: 68 void BuildScopeInformation(Decl *D, unsigned &ParentScope); 69 void BuildScopeInformation(Stmt *S, unsigned ParentScope); 70 void VerifyJumps(); 71 void VerifyIndirectJumps(); 72 void DiagnoseIndirectJump(IndirectGotoStmt *IG, unsigned IGScope, 73 LabelStmt *Target, unsigned TargetScope); 74 void CheckJump(Stmt *From, Stmt *To, 75 SourceLocation DiagLoc, unsigned JumpDiag); 76 77 unsigned GetDeepestCommonScope(unsigned A, unsigned B); 78}; 79} // end anonymous namespace 80 81 82JumpScopeChecker::JumpScopeChecker(Stmt *Body, Sema &s) : S(s) { 83 // Add a scope entry for function scope. 84 Scopes.push_back(GotoScope(~0U, ~0U, ~0U, SourceLocation())); 85 86 // Build information for the top level compound statement, so that we have a 87 // defined scope record for every "goto" and label. 88 BuildScopeInformation(Body, 0); 89 90 // Check that all jumps we saw are kosher. 91 VerifyJumps(); 92 VerifyIndirectJumps(); 93} 94 95/// GetDeepestCommonScope - Finds the innermost scope enclosing the 96/// two scopes. 97unsigned JumpScopeChecker::GetDeepestCommonScope(unsigned A, unsigned B) { 98 while (A != B) { 99 // Inner scopes are created after outer scopes and therefore have 100 // higher indices. 101 if (A < B) { 102 assert(Scopes[B].ParentScope < B); 103 B = Scopes[B].ParentScope; 104 } else { 105 assert(Scopes[A].ParentScope < A); 106 A = Scopes[A].ParentScope; 107 } 108 } 109 return A; 110} 111 112/// GetDiagForGotoScopeDecl - If this decl induces a new goto scope, return a 113/// diagnostic that should be emitted if control goes over it. If not, return 0. 114static std::pair<unsigned,unsigned> 115 GetDiagForGotoScopeDecl(const Decl *D, bool isCPlusPlus) { 116 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 117 unsigned InDiag = 0, OutDiag = 0; 118 if (VD->getType()->isVariablyModifiedType()) 119 InDiag = diag::note_protected_by_vla; 120 121 if (VD->hasAttr<BlocksAttr>()) { 122 InDiag = diag::note_protected_by___block; 123 OutDiag = diag::note_exits___block; 124 } else if (VD->hasAttr<CleanupAttr>()) { 125 InDiag = diag::note_protected_by_cleanup; 126 OutDiag = diag::note_exits_cleanup; 127 } else if (isCPlusPlus) { 128 // FIXME: In C++0x, we have to check more conditions than "did we 129 // just give it an initializer?". See 6.7p3. 130 if (VD->hasLocalStorage() && VD->hasInit()) 131 InDiag = diag::note_protected_by_variable_init; 132 133 CanQualType T = VD->getType()->getCanonicalTypeUnqualified(); 134 if (!T->isDependentType()) { 135 while (CanQual<ArrayType> AT = T->getAs<ArrayType>()) 136 T = AT->getElementType(); 137 if (CanQual<RecordType> RT = T->getAs<RecordType>()) 138 if (!cast<CXXRecordDecl>(RT->getDecl())->hasTrivialDestructor()) 139 OutDiag = diag::note_exits_dtor; 140 } 141 } 142 143 return std::make_pair(InDiag, OutDiag); 144 } 145 146 if (const TypedefDecl *TD = dyn_cast<TypedefDecl>(D)) { 147 if (TD->getUnderlyingType()->isVariablyModifiedType()) 148 return std::make_pair((unsigned) diag::note_protected_by_vla_typedef, 0); 149 } 150 151 return std::make_pair(0U, 0U); 152} 153 154/// \brief Build scope information for a declaration that is part of a DeclStmt. 155void JumpScopeChecker::BuildScopeInformation(Decl *D, unsigned &ParentScope) { 156 bool isCPlusPlus = this->S.getLangOptions().CPlusPlus; 157 158 // If this decl causes a new scope, push and switch to it. 159 std::pair<unsigned,unsigned> Diags 160 = GetDiagForGotoScopeDecl(D, isCPlusPlus); 161 if (Diags.first || Diags.second) { 162 Scopes.push_back(GotoScope(ParentScope, Diags.first, Diags.second, 163 D->getLocation())); 164 ParentScope = Scopes.size()-1; 165 } 166 167 // If the decl has an initializer, walk it with the potentially new 168 // scope we just installed. 169 if (VarDecl *VD = dyn_cast<VarDecl>(D)) 170 if (Expr *Init = VD->getInit()) 171 BuildScopeInformation(Init, ParentScope); 172} 173 174/// BuildScopeInformation - The statements from CI to CE are known to form a 175/// coherent VLA scope with a specified parent node. Walk through the 176/// statements, adding any labels or gotos to LabelAndGotoScopes and recursively 177/// walking the AST as needed. 178void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { 179 bool SkipFirstSubStmt = false; 180 181 // If we found a label, remember that it is in ParentScope scope. 182 switch (S->getStmtClass()) { 183 case Stmt::AddrLabelExprClass: 184 IndirectJumpTargets.push_back(cast<AddrLabelExpr>(S)->getLabel()); 185 break; 186 187 case Stmt::IndirectGotoStmtClass: 188 LabelAndGotoScopes[S] = ParentScope; 189 IndirectJumps.push_back(cast<IndirectGotoStmt>(S)); 190 break; 191 192 case Stmt::SwitchStmtClass: 193 // Evaluate the condition variable before entering the scope of the switch 194 // statement. 195 if (VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) { 196 BuildScopeInformation(Var, ParentScope); 197 SkipFirstSubStmt = true; 198 } 199 // Fall through 200 201 case Stmt::GotoStmtClass: 202 // Remember both what scope a goto is in as well as the fact that we have 203 // it. This makes the second scan not have to walk the AST again. 204 LabelAndGotoScopes[S] = ParentScope; 205 Jumps.push_back(S); 206 break; 207 208 default: 209 break; 210 } 211 212 for (Stmt::child_iterator CI = S->child_begin(), E = S->child_end(); CI != E; 213 ++CI) { 214 if (SkipFirstSubStmt) { 215 SkipFirstSubStmt = false; 216 continue; 217 } 218 219 Stmt *SubStmt = *CI; 220 if (SubStmt == 0) continue; 221 222 // Cases, labels, and defaults aren't "scope parents". It's also 223 // important to handle these iteratively instead of recursively in 224 // order to avoid blowing out the stack. 225 while (true) { 226 Stmt *Next; 227 if (isa<CaseStmt>(SubStmt)) 228 Next = cast<CaseStmt>(SubStmt)->getSubStmt(); 229 else if (isa<DefaultStmt>(SubStmt)) 230 Next = cast<DefaultStmt>(SubStmt)->getSubStmt(); 231 else if (isa<LabelStmt>(SubStmt)) 232 Next = cast<LabelStmt>(SubStmt)->getSubStmt(); 233 else 234 break; 235 236 LabelAndGotoScopes[SubStmt] = ParentScope; 237 SubStmt = Next; 238 } 239 240 // If this is a declstmt with a VLA definition, it defines a scope from here 241 // to the end of the containing context. 242 if (DeclStmt *DS = dyn_cast<DeclStmt>(SubStmt)) { 243 // The decl statement creates a scope if any of the decls in it are VLAs 244 // or have the cleanup attribute. 245 for (DeclStmt::decl_iterator I = DS->decl_begin(), E = DS->decl_end(); 246 I != E; ++I) 247 BuildScopeInformation(*I, ParentScope); 248 continue; 249 } 250 251 // Disallow jumps into any part of an @try statement by pushing a scope and 252 // walking all sub-stmts in that scope. 253 if (ObjCAtTryStmt *AT = dyn_cast<ObjCAtTryStmt>(SubStmt)) { 254 // Recursively walk the AST for the @try part. 255 Scopes.push_back(GotoScope(ParentScope, 256 diag::note_protected_by_objc_try, 257 diag::note_exits_objc_try, 258 AT->getAtTryLoc())); 259 if (Stmt *TryPart = AT->getTryBody()) 260 BuildScopeInformation(TryPart, Scopes.size()-1); 261 262 // Jump from the catch to the finally or try is not valid. 263 for (unsigned I = 0, N = AT->getNumCatchStmts(); I != N; ++I) { 264 ObjCAtCatchStmt *AC = AT->getCatchStmt(I); 265 Scopes.push_back(GotoScope(ParentScope, 266 diag::note_protected_by_objc_catch, 267 diag::note_exits_objc_catch, 268 AC->getAtCatchLoc())); 269 // @catches are nested and it isn't 270 BuildScopeInformation(AC->getCatchBody(), Scopes.size()-1); 271 } 272 273 // Jump from the finally to the try or catch is not valid. 274 if (ObjCAtFinallyStmt *AF = AT->getFinallyStmt()) { 275 Scopes.push_back(GotoScope(ParentScope, 276 diag::note_protected_by_objc_finally, 277 diag::note_exits_objc_finally, 278 AF->getAtFinallyLoc())); 279 BuildScopeInformation(AF, Scopes.size()-1); 280 } 281 282 continue; 283 } 284 285 // Disallow jumps into the protected statement of an @synchronized, but 286 // allow jumps into the object expression it protects. 287 if (ObjCAtSynchronizedStmt *AS = dyn_cast<ObjCAtSynchronizedStmt>(SubStmt)){ 288 // Recursively walk the AST for the @synchronized object expr, it is 289 // evaluated in the normal scope. 290 BuildScopeInformation(AS->getSynchExpr(), ParentScope); 291 292 // Recursively walk the AST for the @synchronized part, protected by a new 293 // scope. 294 Scopes.push_back(GotoScope(ParentScope, 295 diag::note_protected_by_objc_synchronized, 296 diag::note_exits_objc_synchronized, 297 AS->getAtSynchronizedLoc())); 298 BuildScopeInformation(AS->getSynchBody(), Scopes.size()-1); 299 continue; 300 } 301 302 // Disallow jumps into any part of a C++ try statement. This is pretty 303 // much the same as for Obj-C. 304 if (CXXTryStmt *TS = dyn_cast<CXXTryStmt>(SubStmt)) { 305 Scopes.push_back(GotoScope(ParentScope, 306 diag::note_protected_by_cxx_try, 307 diag::note_exits_cxx_try, 308 TS->getSourceRange().getBegin())); 309 if (Stmt *TryBlock = TS->getTryBlock()) 310 BuildScopeInformation(TryBlock, Scopes.size()-1); 311 312 // Jump from the catch into the try is not allowed either. 313 for (unsigned I = 0, E = TS->getNumHandlers(); I != E; ++I) { 314 CXXCatchStmt *CS = TS->getHandler(I); 315 Scopes.push_back(GotoScope(ParentScope, 316 diag::note_protected_by_cxx_catch, 317 diag::note_exits_cxx_catch, 318 CS->getSourceRange().getBegin())); 319 BuildScopeInformation(CS->getHandlerBlock(), Scopes.size()-1); 320 } 321 322 continue; 323 } 324 325 // Recursively walk the AST. 326 BuildScopeInformation(SubStmt, ParentScope); 327 } 328} 329 330/// VerifyJumps - Verify each element of the Jumps array to see if they are 331/// valid, emitting diagnostics if not. 332void JumpScopeChecker::VerifyJumps() { 333 while (!Jumps.empty()) { 334 Stmt *Jump = Jumps.pop_back_val(); 335 336 // With a goto, 337 if (GotoStmt *GS = dyn_cast<GotoStmt>(Jump)) { 338 CheckJump(GS, GS->getLabel(), GS->getGotoLoc(), 339 diag::err_goto_into_protected_scope); 340 continue; 341 } 342 343 SwitchStmt *SS = cast<SwitchStmt>(Jump); 344 for (SwitchCase *SC = SS->getSwitchCaseList(); SC; 345 SC = SC->getNextSwitchCase()) { 346 assert(LabelAndGotoScopes.count(SC) && "Case not visited?"); 347 CheckJump(SS, SC, SC->getLocStart(), 348 diag::err_switch_into_protected_scope); 349 } 350 } 351} 352 353/// VerifyIndirectJumps - Verify whether any possible indirect jump 354/// might cross a protection boundary. Unlike direct jumps, indirect 355/// jumps count cleanups as protection boundaries: since there's no 356/// way to know where the jump is going, we can't implicitly run the 357/// right cleanups the way we can with direct jumps. 358/// 359/// Thus, an indirect jump is "trivial" if it bypasses no 360/// initializations and no teardowns. More formally, an indirect jump 361/// from A to B is trivial if the path out from A to DCA(A,B) is 362/// trivial and the path in from DCA(A,B) to B is trivial, where 363/// DCA(A,B) is the deepest common ancestor of A and B. 364/// Jump-triviality is transitive but asymmetric. 365/// 366/// A path in is trivial if none of the entered scopes have an InDiag. 367/// A path out is trivial is none of the exited scopes have an OutDiag. 368/// 369/// Under these definitions, this function checks that the indirect 370/// jump between A and B is trivial for every indirect goto statement A 371/// and every label B whose address was taken in the function. 372void JumpScopeChecker::VerifyIndirectJumps() { 373 if (IndirectJumps.empty()) return; 374 375 // If there aren't any address-of-label expressions in this function, 376 // complain about the first indirect goto. 377 if (IndirectJumpTargets.empty()) { 378 S.Diag(IndirectJumps[0]->getGotoLoc(), 379 diag::err_indirect_goto_without_addrlabel); 380 return; 381 } 382 383 // Collect a single representative of every scope containing an 384 // indirect goto. For most code bases, this substantially cuts 385 // down on the number of jump sites we'll have to consider later. 386 typedef std::pair<unsigned, IndirectGotoStmt*> JumpScope; 387 llvm::SmallVector<JumpScope, 32> JumpScopes; 388 { 389 llvm::DenseMap<unsigned, IndirectGotoStmt*> JumpScopesMap; 390 for (llvm::SmallVectorImpl<IndirectGotoStmt*>::iterator 391 I = IndirectJumps.begin(), E = IndirectJumps.end(); I != E; ++I) { 392 IndirectGotoStmt *IG = *I; 393 assert(LabelAndGotoScopes.count(IG) && 394 "indirect jump didn't get added to scopes?"); 395 unsigned IGScope = LabelAndGotoScopes[IG]; 396 IndirectGotoStmt *&Entry = JumpScopesMap[IGScope]; 397 if (!Entry) Entry = IG; 398 } 399 JumpScopes.reserve(JumpScopesMap.size()); 400 for (llvm::DenseMap<unsigned, IndirectGotoStmt*>::iterator 401 I = JumpScopesMap.begin(), E = JumpScopesMap.end(); I != E; ++I) 402 JumpScopes.push_back(*I); 403 } 404 405 // Collect a single representative of every scope containing a 406 // label whose address was taken somewhere in the function. 407 // For most code bases, there will be only one such scope. 408 llvm::DenseMap<unsigned, LabelStmt*> TargetScopes; 409 for (llvm::SmallVectorImpl<LabelStmt*>::iterator 410 I = IndirectJumpTargets.begin(), E = IndirectJumpTargets.end(); 411 I != E; ++I) { 412 LabelStmt *TheLabel = *I; 413 assert(LabelAndGotoScopes.count(TheLabel) && 414 "Referenced label didn't get added to scopes?"); 415 unsigned LabelScope = LabelAndGotoScopes[TheLabel]; 416 LabelStmt *&Target = TargetScopes[LabelScope]; 417 if (!Target) Target = TheLabel; 418 } 419 420 // For each target scope, make sure it's trivially reachable from 421 // every scope containing a jump site. 422 // 423 // A path between scopes always consists of exitting zero or more 424 // scopes, then entering zero or more scopes. We build a set of 425 // of scopes S from which the target scope can be trivially 426 // entered, then verify that every jump scope can be trivially 427 // exitted to reach a scope in S. 428 llvm::BitVector Reachable(Scopes.size(), false); 429 for (llvm::DenseMap<unsigned,LabelStmt*>::iterator 430 TI = TargetScopes.begin(), TE = TargetScopes.end(); TI != TE; ++TI) { 431 unsigned TargetScope = TI->first; 432 LabelStmt *TargetLabel = TI->second; 433 434 Reachable.reset(); 435 436 // Mark all the enclosing scopes from which you can safely jump 437 // into the target scope. 'Min' will end up being the index of 438 // the shallowest such scope. 439 unsigned Min = TargetScope; 440 while (true) { 441 Reachable.set(Min); 442 443 // Don't go beyond the outermost scope. 444 if (Min == 0) break; 445 446 // Stop if we can't trivially enter the current scope. 447 if (Scopes[Min].InDiag) break; 448 449 Min = Scopes[Min].ParentScope; 450 } 451 452 // Walk through all the jump sites, checking that they can trivially 453 // reach this label scope. 454 for (llvm::SmallVectorImpl<JumpScope>::iterator 455 I = JumpScopes.begin(), E = JumpScopes.end(); I != E; ++I) { 456 unsigned Scope = I->first; 457 458 // Walk out the "scope chain" for this scope, looking for a scope 459 // we've marked reachable. For well-formed code this amortizes 460 // to O(JumpScopes.size() / Scopes.size()): we only iterate 461 // when we see something unmarked, and in well-formed code we 462 // mark everything we iterate past. 463 bool IsReachable = false; 464 while (true) { 465 if (Reachable.test(Scope)) { 466 // If we find something reachable, mark all the scopes we just 467 // walked through as reachable. 468 for (unsigned S = I->first; S != Scope; S = Scopes[S].ParentScope) 469 Reachable.set(S); 470 IsReachable = true; 471 break; 472 } 473 474 // Don't walk out if we've reached the top-level scope or we've 475 // gotten shallower than the shallowest reachable scope. 476 if (Scope == 0 || Scope < Min) break; 477 478 // Don't walk out through an out-diagnostic. 479 if (Scopes[Scope].OutDiag) break; 480 481 Scope = Scopes[Scope].ParentScope; 482 } 483 484 // Only diagnose if we didn't find something. 485 if (IsReachable) continue; 486 487 DiagnoseIndirectJump(I->second, I->first, TargetLabel, TargetScope); 488 } 489 } 490} 491 492/// Diagnose an indirect jump which is known to cross scopes. 493void JumpScopeChecker::DiagnoseIndirectJump(IndirectGotoStmt *Jump, 494 unsigned JumpScope, 495 LabelStmt *Target, 496 unsigned TargetScope) { 497 assert(JumpScope != TargetScope); 498 499 S.Diag(Jump->getGotoLoc(), diag::warn_indirect_goto_in_protected_scope); 500 S.Diag(Target->getIdentLoc(), diag::note_indirect_goto_target); 501 502 unsigned Common = GetDeepestCommonScope(JumpScope, TargetScope); 503 504 // Walk out the scope chain until we reach the common ancestor. 505 for (unsigned I = JumpScope; I != Common; I = Scopes[I].ParentScope) 506 if (Scopes[I].OutDiag) 507 S.Diag(Scopes[I].Loc, Scopes[I].OutDiag); 508 509 // Now walk into the scopes containing the label whose address was taken. 510 for (unsigned I = TargetScope; I != Common; I = Scopes[I].ParentScope) 511 if (Scopes[I].InDiag) 512 S.Diag(Scopes[I].Loc, Scopes[I].InDiag); 513} 514 515/// CheckJump - Validate that the specified jump statement is valid: that it is 516/// jumping within or out of its current scope, not into a deeper one. 517void JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, 518 SourceLocation DiagLoc, unsigned JumpDiag) { 519 assert(LabelAndGotoScopes.count(From) && "Jump didn't get added to scopes?"); 520 unsigned FromScope = LabelAndGotoScopes[From]; 521 522 assert(LabelAndGotoScopes.count(To) && "Jump didn't get added to scopes?"); 523 unsigned ToScope = LabelAndGotoScopes[To]; 524 525 // Common case: exactly the same scope, which is fine. 526 if (FromScope == ToScope) return; 527 528 unsigned CommonScope = GetDeepestCommonScope(FromScope, ToScope); 529 530 // It's okay to jump out from a nested scope. 531 if (CommonScope == ToScope) return; 532 533 // Pull out (and reverse) any scopes we might need to diagnose skipping. 534 llvm::SmallVector<unsigned, 10> ToScopes; 535 for (unsigned I = ToScope; I != CommonScope; I = Scopes[I].ParentScope) 536 if (Scopes[I].InDiag) 537 ToScopes.push_back(I); 538 539 // If the only scopes present are cleanup scopes, we're okay. 540 if (ToScopes.empty()) return; 541 542 S.Diag(DiagLoc, JumpDiag); 543 544 // Emit diagnostics for whatever is left in ToScopes. 545 for (unsigned i = 0, e = ToScopes.size(); i != e; ++i) 546 S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].InDiag); 547} 548 549void Sema::DiagnoseInvalidJumps(Stmt *Body) { 550 (void)JumpScopeChecker(Body, *this); 551} 552