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