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