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