JumpDiagnostics.cpp revision 210299
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 "llvm/ADT/BitVector.h" 16#include "Sema.h" 17#include "clang/AST/Expr.h" 18#include "clang/AST/StmtObjC.h" 19#include "clang/AST/StmtCXX.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::LabelStmtClass: 184 case Stmt::DefaultStmtClass: 185 case Stmt::CaseStmtClass: 186 LabelAndGotoScopes[S] = ParentScope; 187 break; 188 189 case Stmt::AddrLabelExprClass: 190 IndirectJumpTargets.push_back(cast<AddrLabelExpr>(S)->getLabel()); 191 break; 192 193 case Stmt::IndirectGotoStmtClass: 194 LabelAndGotoScopes[S] = ParentScope; 195 IndirectJumps.push_back(cast<IndirectGotoStmt>(S)); 196 break; 197 198 case Stmt::SwitchStmtClass: 199 // Evaluate the condition variable before entering the scope of the switch 200 // statement. 201 if (VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) { 202 BuildScopeInformation(Var, ParentScope); 203 SkipFirstSubStmt = true; 204 } 205 // Fall through 206 207 case Stmt::GotoStmtClass: 208 // Remember both what scope a goto is in as well as the fact that we have 209 // it. This makes the second scan not have to walk the AST again. 210 LabelAndGotoScopes[S] = ParentScope; 211 Jumps.push_back(S); 212 break; 213 214 default: 215 break; 216 } 217 218 for (Stmt::child_iterator CI = S->child_begin(), E = S->child_end(); CI != E; 219 ++CI) { 220 if (SkipFirstSubStmt) { 221 SkipFirstSubStmt = false; 222 continue; 223 } 224 225 Stmt *SubStmt = *CI; 226 if (SubStmt == 0) continue; 227 228 // If this is a declstmt with a VLA definition, it defines a scope from here 229 // to the end of the containing context. 230 if (DeclStmt *DS = dyn_cast<DeclStmt>(SubStmt)) { 231 // The decl statement creates a scope if any of the decls in it are VLAs 232 // or have the cleanup attribute. 233 for (DeclStmt::decl_iterator I = DS->decl_begin(), E = DS->decl_end(); 234 I != E; ++I) 235 BuildScopeInformation(*I, ParentScope); 236 continue; 237 } 238 239 // Disallow jumps into any part of an @try statement by pushing a scope and 240 // walking all sub-stmts in that scope. 241 if (ObjCAtTryStmt *AT = dyn_cast<ObjCAtTryStmt>(SubStmt)) { 242 // Recursively walk the AST for the @try part. 243 Scopes.push_back(GotoScope(ParentScope, 244 diag::note_protected_by_objc_try, 245 diag::note_exits_objc_try, 246 AT->getAtTryLoc())); 247 if (Stmt *TryPart = AT->getTryBody()) 248 BuildScopeInformation(TryPart, Scopes.size()-1); 249 250 // Jump from the catch to the finally or try is not valid. 251 for (unsigned I = 0, N = AT->getNumCatchStmts(); I != N; ++I) { 252 ObjCAtCatchStmt *AC = AT->getCatchStmt(I); 253 Scopes.push_back(GotoScope(ParentScope, 254 diag::note_protected_by_objc_catch, 255 diag::note_exits_objc_catch, 256 AC->getAtCatchLoc())); 257 // @catches are nested and it isn't 258 BuildScopeInformation(AC->getCatchBody(), Scopes.size()-1); 259 } 260 261 // Jump from the finally to the try or catch is not valid. 262 if (ObjCAtFinallyStmt *AF = AT->getFinallyStmt()) { 263 Scopes.push_back(GotoScope(ParentScope, 264 diag::note_protected_by_objc_finally, 265 diag::note_exits_objc_finally, 266 AF->getAtFinallyLoc())); 267 BuildScopeInformation(AF, Scopes.size()-1); 268 } 269 270 continue; 271 } 272 273 // Disallow jumps into the protected statement of an @synchronized, but 274 // allow jumps into the object expression it protects. 275 if (ObjCAtSynchronizedStmt *AS = dyn_cast<ObjCAtSynchronizedStmt>(SubStmt)){ 276 // Recursively walk the AST for the @synchronized object expr, it is 277 // evaluated in the normal scope. 278 BuildScopeInformation(AS->getSynchExpr(), ParentScope); 279 280 // Recursively walk the AST for the @synchronized part, protected by a new 281 // scope. 282 Scopes.push_back(GotoScope(ParentScope, 283 diag::note_protected_by_objc_synchronized, 284 diag::note_exits_objc_synchronized, 285 AS->getAtSynchronizedLoc())); 286 BuildScopeInformation(AS->getSynchBody(), Scopes.size()-1); 287 continue; 288 } 289 290 // Disallow jumps into any part of a C++ try statement. This is pretty 291 // much the same as for Obj-C. 292 if (CXXTryStmt *TS = dyn_cast<CXXTryStmt>(SubStmt)) { 293 Scopes.push_back(GotoScope(ParentScope, 294 diag::note_protected_by_cxx_try, 295 diag::note_exits_cxx_try, 296 TS->getSourceRange().getBegin())); 297 if (Stmt *TryBlock = TS->getTryBlock()) 298 BuildScopeInformation(TryBlock, Scopes.size()-1); 299 300 // Jump from the catch into the try is not allowed either. 301 for (unsigned I = 0, E = TS->getNumHandlers(); I != E; ++I) { 302 CXXCatchStmt *CS = TS->getHandler(I); 303 Scopes.push_back(GotoScope(ParentScope, 304 diag::note_protected_by_cxx_catch, 305 diag::note_exits_cxx_catch, 306 CS->getSourceRange().getBegin())); 307 BuildScopeInformation(CS->getHandlerBlock(), Scopes.size()-1); 308 } 309 310 continue; 311 } 312 313 // Recursively walk the AST. 314 BuildScopeInformation(SubStmt, ParentScope); 315 } 316} 317 318/// VerifyJumps - Verify each element of the Jumps array to see if they are 319/// valid, emitting diagnostics if not. 320void JumpScopeChecker::VerifyJumps() { 321 while (!Jumps.empty()) { 322 Stmt *Jump = Jumps.pop_back_val(); 323 324 // With a goto, 325 if (GotoStmt *GS = dyn_cast<GotoStmt>(Jump)) { 326 CheckJump(GS, GS->getLabel(), GS->getGotoLoc(), 327 diag::err_goto_into_protected_scope); 328 continue; 329 } 330 331 SwitchStmt *SS = cast<SwitchStmt>(Jump); 332 for (SwitchCase *SC = SS->getSwitchCaseList(); SC; 333 SC = SC->getNextSwitchCase()) { 334 assert(LabelAndGotoScopes.count(SC) && "Case not visited?"); 335 CheckJump(SS, SC, SC->getLocStart(), 336 diag::err_switch_into_protected_scope); 337 } 338 } 339} 340 341/// VerifyIndirectJumps - Verify whether any possible indirect jump 342/// might cross a protection boundary. Unlike direct jumps, indirect 343/// jumps count cleanups as protection boundaries: since there's no 344/// way to know where the jump is going, we can't implicitly run the 345/// right cleanups the way we can with direct jumps. 346/// 347/// Thus, an indirect jump is "trivial" if it bypasses no 348/// initializations and no teardowns. More formally, an indirect jump 349/// from A to B is trivial if the path out from A to DCA(A,B) is 350/// trivial and the path in from DCA(A,B) to B is trivial, where 351/// DCA(A,B) is the deepest common ancestor of A and B. 352/// Jump-triviality is transitive but asymmetric. 353/// 354/// A path in is trivial if none of the entered scopes have an InDiag. 355/// A path out is trivial is none of the exited scopes have an OutDiag. 356/// 357/// Under these definitions, this function checks that the indirect 358/// jump between A and B is trivial for every indirect goto statement A 359/// and every label B whose address was taken in the function. 360void JumpScopeChecker::VerifyIndirectJumps() { 361 if (IndirectJumps.empty()) return; 362 363 // If there aren't any address-of-label expressions in this function, 364 // complain about the first indirect goto. 365 if (IndirectJumpTargets.empty()) { 366 S.Diag(IndirectJumps[0]->getGotoLoc(), 367 diag::err_indirect_goto_without_addrlabel); 368 return; 369 } 370 371 // Collect a single representative of every scope containing an 372 // indirect goto. For most code bases, this substantially cuts 373 // down on the number of jump sites we'll have to consider later. 374 typedef std::pair<unsigned, IndirectGotoStmt*> JumpScope; 375 llvm::SmallVector<JumpScope, 32> JumpScopes; 376 { 377 llvm::DenseMap<unsigned, IndirectGotoStmt*> JumpScopesMap; 378 for (llvm::SmallVectorImpl<IndirectGotoStmt*>::iterator 379 I = IndirectJumps.begin(), E = IndirectJumps.end(); I != E; ++I) { 380 IndirectGotoStmt *IG = *I; 381 assert(LabelAndGotoScopes.count(IG) && 382 "indirect jump didn't get added to scopes?"); 383 unsigned IGScope = LabelAndGotoScopes[IG]; 384 IndirectGotoStmt *&Entry = JumpScopesMap[IGScope]; 385 if (!Entry) Entry = IG; 386 } 387 JumpScopes.reserve(JumpScopesMap.size()); 388 for (llvm::DenseMap<unsigned, IndirectGotoStmt*>::iterator 389 I = JumpScopesMap.begin(), E = JumpScopesMap.end(); I != E; ++I) 390 JumpScopes.push_back(*I); 391 } 392 393 // Collect a single representative of every scope containing a 394 // label whose address was taken somewhere in the function. 395 // For most code bases, there will be only one such scope. 396 llvm::DenseMap<unsigned, LabelStmt*> TargetScopes; 397 for (llvm::SmallVectorImpl<LabelStmt*>::iterator 398 I = IndirectJumpTargets.begin(), E = IndirectJumpTargets.end(); 399 I != E; ++I) { 400 LabelStmt *TheLabel = *I; 401 assert(LabelAndGotoScopes.count(TheLabel) && 402 "Referenced label didn't get added to scopes?"); 403 unsigned LabelScope = LabelAndGotoScopes[TheLabel]; 404 LabelStmt *&Target = TargetScopes[LabelScope]; 405 if (!Target) Target = TheLabel; 406 } 407 408 // For each target scope, make sure it's trivially reachable from 409 // every scope containing a jump site. 410 // 411 // A path between scopes always consists of exitting zero or more 412 // scopes, then entering zero or more scopes. We build a set of 413 // of scopes S from which the target scope can be trivially 414 // entered, then verify that every jump scope can be trivially 415 // exitted to reach a scope in S. 416 llvm::BitVector Reachable(Scopes.size(), false); 417 for (llvm::DenseMap<unsigned,LabelStmt*>::iterator 418 TI = TargetScopes.begin(), TE = TargetScopes.end(); TI != TE; ++TI) { 419 unsigned TargetScope = TI->first; 420 LabelStmt *TargetLabel = TI->second; 421 422 Reachable.reset(); 423 424 // Mark all the enclosing scopes from which you can safely jump 425 // into the target scope. 'Min' will end up being the index of 426 // the shallowest such scope. 427 unsigned Min = TargetScope; 428 while (true) { 429 Reachable.set(Min); 430 431 // Don't go beyond the outermost scope. 432 if (Min == 0) break; 433 434 // Stop if we can't trivially enter the current scope. 435 if (Scopes[Min].InDiag) break; 436 437 Min = Scopes[Min].ParentScope; 438 } 439 440 // Walk through all the jump sites, checking that they can trivially 441 // reach this label scope. 442 for (llvm::SmallVectorImpl<JumpScope>::iterator 443 I = JumpScopes.begin(), E = JumpScopes.end(); I != E; ++I) { 444 unsigned Scope = I->first; 445 446 // Walk out the "scope chain" for this scope, looking for a scope 447 // we've marked reachable. For well-formed code this amortizes 448 // to O(JumpScopes.size() / Scopes.size()): we only iterate 449 // when we see something unmarked, and in well-formed code we 450 // mark everything we iterate past. 451 bool IsReachable = false; 452 while (true) { 453 if (Reachable.test(Scope)) { 454 // If we find something reachable, mark all the scopes we just 455 // walked through as reachable. 456 for (unsigned S = I->first; S != Scope; S = Scopes[S].ParentScope) 457 Reachable.set(S); 458 IsReachable = true; 459 break; 460 } 461 462 // Don't walk out if we've reached the top-level scope or we've 463 // gotten shallower than the shallowest reachable scope. 464 if (Scope == 0 || Scope < Min) break; 465 466 // Don't walk out through an out-diagnostic. 467 if (Scopes[Scope].OutDiag) break; 468 469 Scope = Scopes[Scope].ParentScope; 470 } 471 472 // Only diagnose if we didn't find something. 473 if (IsReachable) continue; 474 475 DiagnoseIndirectJump(I->second, I->first, TargetLabel, TargetScope); 476 } 477 } 478} 479 480/// Diagnose an indirect jump which is known to cross scopes. 481void JumpScopeChecker::DiagnoseIndirectJump(IndirectGotoStmt *Jump, 482 unsigned JumpScope, 483 LabelStmt *Target, 484 unsigned TargetScope) { 485 assert(JumpScope != TargetScope); 486 487 S.Diag(Jump->getGotoLoc(), diag::warn_indirect_goto_in_protected_scope); 488 S.Diag(Target->getIdentLoc(), diag::note_indirect_goto_target); 489 490 unsigned Common = GetDeepestCommonScope(JumpScope, TargetScope); 491 492 // Walk out the scope chain until we reach the common ancestor. 493 for (unsigned I = JumpScope; I != Common; I = Scopes[I].ParentScope) 494 if (Scopes[I].OutDiag) 495 S.Diag(Scopes[I].Loc, Scopes[I].OutDiag); 496 497 // Now walk into the scopes containing the label whose address was taken. 498 for (unsigned I = TargetScope; I != Common; I = Scopes[I].ParentScope) 499 if (Scopes[I].InDiag) 500 S.Diag(Scopes[I].Loc, Scopes[I].InDiag); 501} 502 503/// CheckJump - Validate that the specified jump statement is valid: that it is 504/// jumping within or out of its current scope, not into a deeper one. 505void JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, 506 SourceLocation DiagLoc, unsigned JumpDiag) { 507 assert(LabelAndGotoScopes.count(From) && "Jump didn't get added to scopes?"); 508 unsigned FromScope = LabelAndGotoScopes[From]; 509 510 assert(LabelAndGotoScopes.count(To) && "Jump didn't get added to scopes?"); 511 unsigned ToScope = LabelAndGotoScopes[To]; 512 513 // Common case: exactly the same scope, which is fine. 514 if (FromScope == ToScope) return; 515 516 unsigned CommonScope = GetDeepestCommonScope(FromScope, ToScope); 517 518 // It's okay to jump out from a nested scope. 519 if (CommonScope == ToScope) return; 520 521 // Pull out (and reverse) any scopes we might need to diagnose skipping. 522 llvm::SmallVector<unsigned, 10> ToScopes; 523 for (unsigned I = ToScope; I != CommonScope; I = Scopes[I].ParentScope) 524 if (Scopes[I].InDiag) 525 ToScopes.push_back(I); 526 527 // If the only scopes present are cleanup scopes, we're okay. 528 if (ToScopes.empty()) return; 529 530 S.Diag(DiagLoc, JumpDiag); 531 532 // Emit diagnostics for whatever is left in ToScopes. 533 for (unsigned i = 0, e = ToScopes.size(); i != e; ++i) 534 S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].InDiag); 535} 536 537void Sema::DiagnoseInvalidJumps(Stmt *Body) { 538 (void)JumpScopeChecker(Body, *this); 539} 540