diff options
Diffstat (limited to 'lib/Sema/JumpDiagnostics.cpp')
-rw-r--r-- | lib/Sema/JumpDiagnostics.cpp | 378 |
1 files changed, 282 insertions, 96 deletions
diff --git a/lib/Sema/JumpDiagnostics.cpp b/lib/Sema/JumpDiagnostics.cpp index 0694294..543c1b6 100644 --- a/lib/Sema/JumpDiagnostics.cpp +++ b/lib/Sema/JumpDiagnostics.cpp @@ -12,6 +12,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/BitVector.h" #include "Sema.h" #include "clang/AST/Expr.h" #include "clang/AST/StmtObjC.h" @@ -39,33 +40,47 @@ class JumpScopeChecker { /// the parent scope is the function body. unsigned ParentScope; - /// Diag - The diagnostic to emit if there is a jump into this scope. - unsigned Diag; + /// InDiag - The diagnostic to emit if there is a jump into this scope. + unsigned InDiag; + + /// OutDiag - The diagnostic to emit if there is an indirect jump out + /// of this scope. Direct jumps always clean up their current scope + /// in an orderly way. + unsigned OutDiag; /// Loc - Location to emit the diagnostic. SourceLocation Loc; - GotoScope(unsigned parentScope, unsigned diag, SourceLocation L) - : ParentScope(parentScope), Diag(diag), Loc(L) {} + GotoScope(unsigned parentScope, unsigned InDiag, unsigned OutDiag, + SourceLocation L) + : ParentScope(parentScope), InDiag(InDiag), OutDiag(OutDiag), Loc(L) {} }; llvm::SmallVector<GotoScope, 48> Scopes; llvm::DenseMap<Stmt*, unsigned> LabelAndGotoScopes; llvm::SmallVector<Stmt*, 16> Jumps; + + llvm::SmallVector<IndirectGotoStmt*, 4> IndirectJumps; + llvm::SmallVector<LabelStmt*, 4> IndirectJumpTargets; public: JumpScopeChecker(Stmt *Body, Sema &S); private: void BuildScopeInformation(Stmt *S, unsigned ParentScope); void VerifyJumps(); + void VerifyIndirectJumps(); + void DiagnoseIndirectJump(IndirectGotoStmt *IG, unsigned IGScope, + LabelStmt *Target, unsigned TargetScope); void CheckJump(Stmt *From, Stmt *To, SourceLocation DiagLoc, unsigned JumpDiag); + + unsigned GetDeepestCommonScope(unsigned A, unsigned B); }; } // end anonymous namespace JumpScopeChecker::JumpScopeChecker(Stmt *Body, Sema &s) : S(s) { // Add a scope entry for function scope. - Scopes.push_back(GotoScope(~0U, ~0U, SourceLocation())); + Scopes.push_back(GotoScope(~0U, ~0U, ~0U, SourceLocation())); // Build information for the top level compound statement, so that we have a // defined scope record for every "goto" and label. @@ -73,29 +88,64 @@ JumpScopeChecker::JumpScopeChecker(Stmt *Body, Sema &s) : S(s) { // Check that all jumps we saw are kosher. VerifyJumps(); + VerifyIndirectJumps(); +} + +/// GetDeepestCommonScope - Finds the innermost scope enclosing the +/// two scopes. +unsigned JumpScopeChecker::GetDeepestCommonScope(unsigned A, unsigned B) { + while (A != B) { + // Inner scopes are created after outer scopes and therefore have + // higher indices. + if (A < B) { + assert(Scopes[B].ParentScope < B); + B = Scopes[B].ParentScope; + } else { + assert(Scopes[A].ParentScope < A); + A = Scopes[A].ParentScope; + } + } + return A; } /// GetDiagForGotoScopeDecl - If this decl induces a new goto scope, return a /// diagnostic that should be emitted if control goes over it. If not, return 0. -static unsigned GetDiagForGotoScopeDecl(const Decl *D, bool isCPlusPlus) { +static std::pair<unsigned,unsigned> + GetDiagForGotoScopeDecl(const Decl *D, bool isCPlusPlus) { if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { + unsigned InDiag = 0, OutDiag = 0; if (VD->getType()->isVariablyModifiedType()) - return diag::note_protected_by_vla; - if (VD->hasAttr<CleanupAttr>()) - return diag::note_protected_by_cleanup; - if (VD->hasAttr<BlocksAttr>()) - return diag::note_protected_by___block; - // FIXME: In C++0x, we have to check more conditions than "did we - // just give it an initializer?". See 6.7p3. - if (isCPlusPlus && VD->hasLocalStorage() && VD->hasInit()) - return diag::note_protected_by_variable_init; + InDiag = diag::note_protected_by_vla; + + if (VD->hasAttr<BlocksAttr>()) { + InDiag = diag::note_protected_by___block; + OutDiag = diag::note_exits___block; + } else if (VD->hasAttr<CleanupAttr>()) { + InDiag = diag::note_protected_by_cleanup; + OutDiag = diag::note_exits_cleanup; + } else if (isCPlusPlus) { + // FIXME: In C++0x, we have to check more conditions than "did we + // just give it an initializer?". See 6.7p3. + if (VD->hasLocalStorage() && VD->hasInit()) + InDiag = diag::note_protected_by_variable_init; + + CanQualType T = VD->getType()->getCanonicalTypeUnqualified(); + while (CanQual<ArrayType> AT = T->getAs<ArrayType>()) + T = AT->getElementType(); + if (CanQual<RecordType> RT = T->getAs<RecordType>()) + if (!cast<CXXRecordDecl>(RT->getDecl())->hasTrivialDestructor()) + OutDiag = diag::note_exits_dtor; + } - } else if (const TypedefDecl *TD = dyn_cast<TypedefDecl>(D)) { + return std::make_pair(InDiag, OutDiag); + } + + if (const TypedefDecl *TD = dyn_cast<TypedefDecl>(D)) { if (TD->getUnderlyingType()->isVariablyModifiedType()) - return diag::note_protected_by_vla_typedef; + return std::make_pair((unsigned) diag::note_protected_by_vla_typedef, 0); } - return 0; + return std::make_pair(0U, 0U); } @@ -106,14 +156,32 @@ static unsigned GetDiagForGotoScopeDecl(const Decl *D, bool isCPlusPlus) { void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { // If we found a label, remember that it is in ParentScope scope. - if (isa<LabelStmt>(S) || isa<DefaultStmt>(S) || isa<CaseStmt>(S)) { + switch (S->getStmtClass()) { + case Stmt::LabelStmtClass: + case Stmt::DefaultStmtClass: + case Stmt::CaseStmtClass: + LabelAndGotoScopes[S] = ParentScope; + break; + + case Stmt::AddrLabelExprClass: + IndirectJumpTargets.push_back(cast<AddrLabelExpr>(S)->getLabel()); + break; + + case Stmt::IndirectGotoStmtClass: LabelAndGotoScopes[S] = ParentScope; - } else if (isa<GotoStmt>(S) || isa<SwitchStmt>(S) || - isa<IndirectGotoStmt>(S) || isa<AddrLabelExpr>(S)) { + IndirectJumps.push_back(cast<IndirectGotoStmt>(S)); + break; + + case Stmt::GotoStmtClass: + case Stmt::SwitchStmtClass: // Remember both what scope a goto is in as well as the fact that we have // it. This makes the second scan not have to walk the AST again. LabelAndGotoScopes[S] = ParentScope; Jumps.push_back(S); + break; + + default: + break; } for (Stmt::child_iterator CI = S->child_begin(), E = S->child_end(); CI != E; @@ -131,8 +199,11 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { for (DeclStmt::decl_iterator I = DS->decl_begin(), E = DS->decl_end(); I != E; ++I) { // If this decl causes a new scope, push and switch to it. - if (unsigned Diag = GetDiagForGotoScopeDecl(*I, isCPlusPlus)) { - Scopes.push_back(GotoScope(ParentScope, Diag, (*I)->getLocation())); + std::pair<unsigned,unsigned> Diags + = GetDiagForGotoScopeDecl(*I, isCPlusPlus); + if (Diags.first || Diags.second) { + Scopes.push_back(GotoScope(ParentScope, Diags.first, Diags.second, + (*I)->getLocation())); ParentScope = Scopes.size()-1; } @@ -149,7 +220,9 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { // walking all sub-stmts in that scope. if (ObjCAtTryStmt *AT = dyn_cast<ObjCAtTryStmt>(SubStmt)) { // Recursively walk the AST for the @try part. - Scopes.push_back(GotoScope(ParentScope,diag::note_protected_by_objc_try, + Scopes.push_back(GotoScope(ParentScope, + diag::note_protected_by_objc_try, + diag::note_exits_objc_try, AT->getAtTryLoc())); if (Stmt *TryPart = AT->getTryBody()) BuildScopeInformation(TryPart, Scopes.size()-1); @@ -159,6 +232,7 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { ObjCAtCatchStmt *AC = AT->getCatchStmt(I); Scopes.push_back(GotoScope(ParentScope, diag::note_protected_by_objc_catch, + diag::note_exits_objc_catch, AC->getAtCatchLoc())); // @catches are nested and it isn't BuildScopeInformation(AC->getCatchBody(), Scopes.size()-1); @@ -168,6 +242,7 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { if (ObjCAtFinallyStmt *AF = AT->getFinallyStmt()) { Scopes.push_back(GotoScope(ParentScope, diag::note_protected_by_objc_finally, + diag::note_exits_objc_finally, AF->getAtFinallyLoc())); BuildScopeInformation(AF, Scopes.size()-1); } @@ -186,6 +261,7 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { // scope. Scopes.push_back(GotoScope(ParentScope, diag::note_protected_by_objc_synchronized, + diag::note_exits_objc_synchronized, AS->getAtSynchronizedLoc())); BuildScopeInformation(AS->getSynchBody(), Scopes.size()-1); continue; @@ -194,7 +270,9 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { // Disallow jumps into any part of a C++ try statement. This is pretty // much the same as for Obj-C. if (CXXTryStmt *TS = dyn_cast<CXXTryStmt>(SubStmt)) { - Scopes.push_back(GotoScope(ParentScope, diag::note_protected_by_cxx_try, + Scopes.push_back(GotoScope(ParentScope, + diag::note_protected_by_cxx_try, + diag::note_exits_cxx_try, TS->getSourceRange().getBegin())); if (Stmt *TryBlock = TS->getTryBlock()) BuildScopeInformation(TryBlock, Scopes.size()-1); @@ -204,6 +282,7 @@ void JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { CXXCatchStmt *CS = TS->getHandler(I); Scopes.push_back(GotoScope(ParentScope, diag::note_protected_by_cxx_catch, + diag::note_exits_cxx_catch, CS->getSourceRange().getBegin())); BuildScopeInformation(CS->getHandlerBlock(), Scopes.size()-1); } @@ -229,54 +308,178 @@ void JumpScopeChecker::VerifyJumps() { continue; } - if (SwitchStmt *SS = dyn_cast<SwitchStmt>(Jump)) { - for (SwitchCase *SC = SS->getSwitchCaseList(); SC; - SC = SC->getNextSwitchCase()) { - assert(LabelAndGotoScopes.count(SC) && "Case not visited?"); - CheckJump(SS, SC, SC->getLocStart(), - diag::err_switch_into_protected_scope); - } - continue; + SwitchStmt *SS = cast<SwitchStmt>(Jump); + for (SwitchCase *SC = SS->getSwitchCaseList(); SC; + SC = SC->getNextSwitchCase()) { + assert(LabelAndGotoScopes.count(SC) && "Case not visited?"); + CheckJump(SS, SC, SC->getLocStart(), + diag::err_switch_into_protected_scope); } + } +} - unsigned DiagnosticScope; - - // We don't know where an indirect goto goes, require that it be at the - // top level of scoping. - if (IndirectGotoStmt *IG = dyn_cast<IndirectGotoStmt>(Jump)) { - assert(LabelAndGotoScopes.count(Jump) && - "Jump didn't get added to scopes?"); - unsigned GotoScope = LabelAndGotoScopes[IG]; - if (GotoScope == 0) continue; // indirect jump is ok. - S.Diag(IG->getGotoLoc(), diag::err_indirect_goto_in_protected_scope); - DiagnosticScope = GotoScope; - } else { - // We model &&Label as a jump for purposes of scope tracking. We actually - // don't care *where* the address of label is, but we require the *label - // itself* to be in scope 0. If it is nested inside of a VLA scope, then - // it is possible for an indirect goto to illegally enter the VLA scope by - // indirectly jumping to the label. - assert(isa<AddrLabelExpr>(Jump) && "Unknown jump type"); - LabelStmt *TheLabel = cast<AddrLabelExpr>(Jump)->getLabel(); - - assert(LabelAndGotoScopes.count(TheLabel) && - "Referenced label didn't get added to scopes?"); - unsigned LabelScope = LabelAndGotoScopes[TheLabel]; - if (LabelScope == 0) continue; // Addr of label is ok. - - S.Diag(Jump->getLocStart(), diag::err_addr_of_label_in_protected_scope); - DiagnosticScope = LabelScope; +/// VerifyIndirectJumps - Verify whether any possible indirect jump +/// might cross a protection boundary. Unlike direct jumps, indirect +/// jumps count cleanups as protection boundaries: since there's no +/// way to know where the jump is going, we can't implicitly run the +/// right cleanups the way we can with direct jumps. +/// +/// Thus, an indirect jump is "trivial" if it bypasses no +/// initializations and no teardowns. More formally, an indirect jump +/// from A to B is trivial if the path out from A to DCA(A,B) is +/// trivial and the path in from DCA(A,B) to B is trivial, where +/// DCA(A,B) is the deepest common ancestor of A and B. +/// Jump-triviality is transitive but asymmetric. +/// +/// A path in is trivial if none of the entered scopes have an InDiag. +/// A path out is trivial is none of the exited scopes have an OutDiag. +/// +/// Under these definitions, this function checks that the indirect +/// jump between A and B is trivial for every indirect goto statement A +/// and every label B whose address was taken in the function. +void JumpScopeChecker::VerifyIndirectJumps() { + if (IndirectJumps.empty()) return; + + // If there aren't any address-of-label expressions in this function, + // complain about the first indirect goto. + if (IndirectJumpTargets.empty()) { + S.Diag(IndirectJumps[0]->getGotoLoc(), + diag::err_indirect_goto_without_addrlabel); + return; + } + + // Collect a single representative of every scope containing an + // indirect goto. For most code bases, this substantially cuts + // down on the number of jump sites we'll have to consider later. + typedef std::pair<unsigned, IndirectGotoStmt*> JumpScope; + llvm::SmallVector<JumpScope, 32> JumpScopes; + { + llvm::DenseMap<unsigned, IndirectGotoStmt*> JumpScopesMap; + for (llvm::SmallVectorImpl<IndirectGotoStmt*>::iterator + I = IndirectJumps.begin(), E = IndirectJumps.end(); I != E; ++I) { + IndirectGotoStmt *IG = *I; + assert(LabelAndGotoScopes.count(IG) && + "indirect jump didn't get added to scopes?"); + unsigned IGScope = LabelAndGotoScopes[IG]; + IndirectGotoStmt *&Entry = JumpScopesMap[IGScope]; + if (!Entry) Entry = IG; + } + JumpScopes.reserve(JumpScopesMap.size()); + for (llvm::DenseMap<unsigned, IndirectGotoStmt*>::iterator + I = JumpScopesMap.begin(), E = JumpScopesMap.end(); I != E; ++I) + JumpScopes.push_back(*I); + } + + // Collect a single representative of every scope containing a + // label whose address was taken somewhere in the function. + // For most code bases, there will be only one such scope. + llvm::DenseMap<unsigned, LabelStmt*> TargetScopes; + for (llvm::SmallVectorImpl<LabelStmt*>::iterator + I = IndirectJumpTargets.begin(), E = IndirectJumpTargets.end(); + I != E; ++I) { + LabelStmt *TheLabel = *I; + assert(LabelAndGotoScopes.count(TheLabel) && + "Referenced label didn't get added to scopes?"); + unsigned LabelScope = LabelAndGotoScopes[TheLabel]; + LabelStmt *&Target = TargetScopes[LabelScope]; + if (!Target) Target = TheLabel; + } + + // For each target scope, make sure it's trivially reachable from + // every scope containing a jump site. + // + // A path between scopes always consists of exitting zero or more + // scopes, then entering zero or more scopes. We build a set of + // of scopes S from which the target scope can be trivially + // entered, then verify that every jump scope can be trivially + // exitted to reach a scope in S. + llvm::BitVector Reachable(Scopes.size(), false); + for (llvm::DenseMap<unsigned,LabelStmt*>::iterator + TI = TargetScopes.begin(), TE = TargetScopes.end(); TI != TE; ++TI) { + unsigned TargetScope = TI->first; + LabelStmt *TargetLabel = TI->second; + + Reachable.reset(); + + // Mark all the enclosing scopes from which you can safely jump + // into the target scope. 'Min' will end up being the index of + // the shallowest such scope. + unsigned Min = TargetScope; + while (true) { + Reachable.set(Min); + + // Don't go beyond the outermost scope. + if (Min == 0) break; + + // Stop if we can't trivially enter the current scope. + if (Scopes[Min].InDiag) break; + + Min = Scopes[Min].ParentScope; } - // Report all the things that would be skipped over by this &&label or - // indirect goto. - while (DiagnosticScope != 0) { - S.Diag(Scopes[DiagnosticScope].Loc, Scopes[DiagnosticScope].Diag); - DiagnosticScope = Scopes[DiagnosticScope].ParentScope; + // Walk through all the jump sites, checking that they can trivially + // reach this label scope. + for (llvm::SmallVectorImpl<JumpScope>::iterator + I = JumpScopes.begin(), E = JumpScopes.end(); I != E; ++I) { + unsigned Scope = I->first; + + // Walk out the "scope chain" for this scope, looking for a scope + // we've marked reachable. For well-formed code this amortizes + // to O(JumpScopes.size() / Scopes.size()): we only iterate + // when we see something unmarked, and in well-formed code we + // mark everything we iterate past. + bool IsReachable = false; + while (true) { + if (Reachable.test(Scope)) { + // If we find something reachable, mark all the scopes we just + // walked through as reachable. + for (unsigned S = I->first; S != Scope; S = Scopes[S].ParentScope) + Reachable.set(S); + IsReachable = true; + break; + } + + // Don't walk out if we've reached the top-level scope or we've + // gotten shallower than the shallowest reachable scope. + if (Scope == 0 || Scope < Min) break; + + // Don't walk out through an out-diagnostic. + if (Scopes[Scope].OutDiag) break; + + Scope = Scopes[Scope].ParentScope; + } + + // Only diagnose if we didn't find something. + if (IsReachable) continue; + + DiagnoseIndirectJump(I->second, I->first, TargetLabel, TargetScope); } } } +/// Diagnose an indirect jump which is known to cross scopes. +void JumpScopeChecker::DiagnoseIndirectJump(IndirectGotoStmt *Jump, + unsigned JumpScope, + LabelStmt *Target, + unsigned TargetScope) { + assert(JumpScope != TargetScope); + + S.Diag(Jump->getGotoLoc(), diag::warn_indirect_goto_in_protected_scope); + S.Diag(Target->getIdentLoc(), diag::note_indirect_goto_target); + + unsigned Common = GetDeepestCommonScope(JumpScope, TargetScope); + + // Walk out the scope chain until we reach the common ancestor. + for (unsigned I = JumpScope; I != Common; I = Scopes[I].ParentScope) + if (Scopes[I].OutDiag) + S.Diag(Scopes[I].Loc, Scopes[I].OutDiag); + + // Now walk into the scopes containing the label whose address was taken. + for (unsigned I = TargetScope; I != Common; I = Scopes[I].ParentScope) + if (Scopes[I].InDiag) + S.Diag(Scopes[I].Loc, Scopes[I].InDiag); +} + /// CheckJump - Validate that the specified jump statement is valid: that it is /// jumping within or out of its current scope, not into a deeper one. void JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, @@ -290,42 +493,25 @@ void JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, // Common case: exactly the same scope, which is fine. if (FromScope == ToScope) return; - // The only valid mismatch jump case happens when the jump is more deeply - // nested inside the jump target. Do a quick scan to see if the jump is valid - // because valid code is more common than invalid code. - unsigned TestScope = Scopes[FromScope].ParentScope; - while (TestScope != ~0U) { - // If we found the jump target, then we're jumping out of our current scope, - // which is perfectly fine. - if (TestScope == ToScope) return; - - // Otherwise, scan up the hierarchy. - TestScope = Scopes[TestScope].ParentScope; - } + unsigned CommonScope = GetDeepestCommonScope(FromScope, ToScope); - // If we get here, then we know we have invalid code. Diagnose the bad jump, - // and then emit a note at each VLA being jumped out of. - S.Diag(DiagLoc, JumpDiag); + // It's okay to jump out from a nested scope. + if (CommonScope == ToScope) return; - // Eliminate the common prefix of the jump and the target. Start by - // linearizing both scopes, reversing them as we go. - std::vector<unsigned> FromScopes, ToScopes; - for (TestScope = FromScope; TestScope != ~0U; - TestScope = Scopes[TestScope].ParentScope) - FromScopes.push_back(TestScope); - for (TestScope = ToScope; TestScope != ~0U; - TestScope = Scopes[TestScope].ParentScope) - ToScopes.push_back(TestScope); - - // Remove any common entries (such as the top-level function scope). - while (!FromScopes.empty() && FromScopes.back() == ToScopes.back()) { - FromScopes.pop_back(); - ToScopes.pop_back(); - } + // Pull out (and reverse) any scopes we might need to diagnose skipping. + llvm::SmallVector<unsigned, 10> ToScopes; + for (unsigned I = ToScope; I != CommonScope; I = Scopes[I].ParentScope) + if (Scopes[I].InDiag) + ToScopes.push_back(I); + + // If the only scopes present are cleanup scopes, we're okay. + if (ToScopes.empty()) return; + + S.Diag(DiagLoc, JumpDiag); // Emit diagnostics for whatever is left in ToScopes. for (unsigned i = 0, e = ToScopes.size(); i != e; ++i) - S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].Diag); + S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].InDiag); } void Sema::DiagnoseInvalidJumps(Stmt *Body) { |