1 //===- Consumed.cpp --------------------------------------------*- C++ --*-===//
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 // A intra-procedural analysis for checking consumed properties. This is based,
11 // in part, on research on linear types.
13 //===----------------------------------------------------------------------===//
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Attr.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/ExprCXX.h"
19 #include "clang/AST/RecursiveASTVisitor.h"
20 #include "clang/AST/StmtVisitor.h"
21 #include "clang/AST/StmtCXX.h"
22 #include "clang/AST/Type.h"
23 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
24 #include "clang/Analysis/AnalysisContext.h"
25 #include "clang/Analysis/CFG.h"
26 #include "clang/Analysis/Analyses/Consumed.h"
27 #include "clang/Basic/OperatorKinds.h"
28 #include "clang/Basic/SourceLocation.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/OwningPtr.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Support/Compiler.h"
33 #include "llvm/Support/raw_ostream.h"
35 // TODO: Adjust states of args to constructors in the same way that arguments to
36 // function calls are handled.
37 // TODO: Use information from tests in for- and while-loop conditional.
38 // TODO: Add notes about the actual and expected state for
39 // TODO: Correctly identify unreachable blocks when chaining boolean operators.
40 // TODO: Adjust the parser and AttributesList class to support lists of
42 // TODO: Warn about unreachable code.
43 // TODO: Switch to using a bitmap to track unreachable blocks.
44 // TODO: Handle variable definitions, e.g. bool valid = x.isValid();
45 // if (valid) ...; (Deferred)
46 // TODO: Take notes on state transitions to provide better warning messages.
48 // TODO: Test nested conditionals: A) Checking the same value multiple times,
49 // and 2) Checking different values. (Deferred)
51 using namespace clang;
52 using namespace consumed;
54 // Key method definition
55 ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
57 static SourceLocation getFirstStmtLoc(const CFGBlock *Block) {
58 // Find the source location of the first statement in the block, if the block
60 for (CFGBlock::const_iterator BI = Block->begin(), BE = Block->end();
62 if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
63 return CS->getStmt()->getLocStart();
67 // If we have one successor, return the first statement in that block
68 if (Block->succ_size() == 1 && *Block->succ_begin())
69 return getFirstStmtLoc(*Block->succ_begin());
71 return SourceLocation();
74 static SourceLocation getLastStmtLoc(const CFGBlock *Block) {
75 // Find the source location of the last statement in the block, if the block
77 if (const Stmt *StmtNode = Block->getTerminator()) {
78 return StmtNode->getLocStart();
80 for (CFGBlock::const_reverse_iterator BI = Block->rbegin(),
81 BE = Block->rend(); BI != BE; ++BI) {
82 if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
83 return CS->getStmt()->getLocStart();
87 // If we have one successor, return the first statement in that block
89 if (Block->succ_size() == 1 && *Block->succ_begin())
90 Loc = getFirstStmtLoc(*Block->succ_begin());
94 // If we have one predecessor, return the last statement in that block
95 if (Block->pred_size() == 1 && *Block->pred_begin())
96 return getLastStmtLoc(*Block->pred_begin());
101 static ConsumedState invertConsumedUnconsumed(ConsumedState State) {
106 return CS_Unconsumed;
112 llvm_unreachable("invalid enum");
115 static bool isCallableInState(const CallableWhenAttr *CWAttr,
116 ConsumedState State) {
118 CallableWhenAttr::callableState_iterator I = CWAttr->callableState_begin(),
119 E = CWAttr->callableState_end();
121 for (; I != E; ++I) {
123 ConsumedState MappedAttrState = CS_None;
126 case CallableWhenAttr::Unknown:
127 MappedAttrState = CS_Unknown;
130 case CallableWhenAttr::Unconsumed:
131 MappedAttrState = CS_Unconsumed;
134 case CallableWhenAttr::Consumed:
135 MappedAttrState = CS_Consumed;
139 if (MappedAttrState == State)
146 static bool isConsumableType(const QualType &QT) {
147 if (QT->isPointerType() || QT->isReferenceType())
150 if (const CXXRecordDecl *RD = QT->getAsCXXRecordDecl())
151 return RD->hasAttr<ConsumableAttr>();
156 static bool isKnownState(ConsumedState State) {
165 llvm_unreachable("invalid enum");
168 static bool isRValueRefish(QualType ParamType) {
169 return ParamType->isRValueReferenceType() ||
170 (ParamType->isLValueReferenceType() &&
171 !cast<LValueReferenceType>(
172 ParamType.getCanonicalType())->isSpelledAsLValue());
175 static bool isTestingFunction(const FunctionDecl *FunDecl) {
176 return FunDecl->hasAttr<TestTypestateAttr>();
179 static bool isValueType(QualType ParamType) {
180 return !(ParamType->isPointerType() || ParamType->isReferenceType());
183 static ConsumedState mapConsumableAttrState(const QualType QT) {
184 assert(isConsumableType(QT));
186 const ConsumableAttr *CAttr =
187 QT->getAsCXXRecordDecl()->getAttr<ConsumableAttr>();
189 switch (CAttr->getDefaultState()) {
190 case ConsumableAttr::Unknown:
192 case ConsumableAttr::Unconsumed:
193 return CS_Unconsumed;
194 case ConsumableAttr::Consumed:
197 llvm_unreachable("invalid enum");
201 mapParamTypestateAttrState(const ParamTypestateAttr *PTAttr) {
202 switch (PTAttr->getParamState()) {
203 case ParamTypestateAttr::Unknown:
205 case ParamTypestateAttr::Unconsumed:
206 return CS_Unconsumed;
207 case ParamTypestateAttr::Consumed:
210 llvm_unreachable("invalid_enum");
214 mapReturnTypestateAttrState(const ReturnTypestateAttr *RTSAttr) {
215 switch (RTSAttr->getState()) {
216 case ReturnTypestateAttr::Unknown:
218 case ReturnTypestateAttr::Unconsumed:
219 return CS_Unconsumed;
220 case ReturnTypestateAttr::Consumed:
223 llvm_unreachable("invalid enum");
226 static ConsumedState mapSetTypestateAttrState(const SetTypestateAttr *STAttr) {
227 switch (STAttr->getNewState()) {
228 case SetTypestateAttr::Unknown:
230 case SetTypestateAttr::Unconsumed:
231 return CS_Unconsumed;
232 case SetTypestateAttr::Consumed:
235 llvm_unreachable("invalid_enum");
238 static StringRef stateToString(ConsumedState State) {
240 case consumed::CS_None:
243 case consumed::CS_Unknown:
246 case consumed::CS_Unconsumed:
249 case consumed::CS_Consumed:
252 llvm_unreachable("invalid enum");
255 static ConsumedState testsFor(const FunctionDecl *FunDecl) {
256 assert(isTestingFunction(FunDecl));
257 switch (FunDecl->getAttr<TestTypestateAttr>()->getTestState()) {
258 case TestTypestateAttr::Unconsumed:
259 return CS_Unconsumed;
260 case TestTypestateAttr::Consumed:
263 llvm_unreachable("invalid enum");
267 struct VarTestResult {
269 ConsumedState TestsFor;
271 } // end anonymous::VarTestResult
281 class PropagationInfo {
292 const BinaryOperator *Source;
300 VarTestResult VarTest;
302 const CXXBindTemporaryExpr *Tmp;
307 PropagationInfo() : InfoType(IT_None) {}
309 PropagationInfo(const VarTestResult &VarTest)
310 : InfoType(IT_VarTest), VarTest(VarTest) {}
312 PropagationInfo(const VarDecl *Var, ConsumedState TestsFor)
313 : InfoType(IT_VarTest) {
316 VarTest.TestsFor = TestsFor;
319 PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
320 const VarTestResult <est, const VarTestResult &RTest)
321 : InfoType(IT_BinTest) {
323 BinTest.Source = Source;
325 BinTest.LTest = LTest;
326 BinTest.RTest = RTest;
329 PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
330 const VarDecl *LVar, ConsumedState LTestsFor,
331 const VarDecl *RVar, ConsumedState RTestsFor)
332 : InfoType(IT_BinTest) {
334 BinTest.Source = Source;
336 BinTest.LTest.Var = LVar;
337 BinTest.LTest.TestsFor = LTestsFor;
338 BinTest.RTest.Var = RVar;
339 BinTest.RTest.TestsFor = RTestsFor;
342 PropagationInfo(ConsumedState State)
343 : InfoType(IT_State), State(State) {}
345 PropagationInfo(const VarDecl *Var) : InfoType(IT_Var), Var(Var) {}
346 PropagationInfo(const CXXBindTemporaryExpr *Tmp)
347 : InfoType(IT_Tmp), Tmp(Tmp) {}
349 const ConsumedState & getState() const {
350 assert(InfoType == IT_State);
354 const VarTestResult & getVarTest() const {
355 assert(InfoType == IT_VarTest);
359 const VarTestResult & getLTest() const {
360 assert(InfoType == IT_BinTest);
361 return BinTest.LTest;
364 const VarTestResult & getRTest() const {
365 assert(InfoType == IT_BinTest);
366 return BinTest.RTest;
369 const VarDecl * getVar() const {
370 assert(InfoType == IT_Var);
374 const CXXBindTemporaryExpr * getTmp() const {
375 assert(InfoType == IT_Tmp);
379 ConsumedState getAsState(const ConsumedStateMap *StateMap) const {
380 assert(isVar() || isTmp() || isState());
383 return StateMap->getState(Var);
385 return StateMap->getState(Tmp);
392 EffectiveOp testEffectiveOp() const {
393 assert(InfoType == IT_BinTest);
397 const BinaryOperator * testSourceNode() const {
398 assert(InfoType == IT_BinTest);
399 return BinTest.Source;
402 inline bool isValid() const { return InfoType != IT_None; }
403 inline bool isState() const { return InfoType == IT_State; }
404 inline bool isVarTest() const { return InfoType == IT_VarTest; }
405 inline bool isBinTest() const { return InfoType == IT_BinTest; }
406 inline bool isVar() const { return InfoType == IT_Var; }
407 inline bool isTmp() const { return InfoType == IT_Tmp; }
409 bool isTest() const {
410 return InfoType == IT_VarTest || InfoType == IT_BinTest;
413 bool isPointerToValue() const {
414 return InfoType == IT_Var || InfoType == IT_Tmp;
417 PropagationInfo invertTest() const {
418 assert(InfoType == IT_VarTest || InfoType == IT_BinTest);
420 if (InfoType == IT_VarTest) {
421 return PropagationInfo(VarTest.Var,
422 invertConsumedUnconsumed(VarTest.TestsFor));
424 } else if (InfoType == IT_BinTest) {
425 return PropagationInfo(BinTest.Source,
426 BinTest.EOp == EO_And ? EO_Or : EO_And,
427 BinTest.LTest.Var, invertConsumedUnconsumed(BinTest.LTest.TestsFor),
428 BinTest.RTest.Var, invertConsumedUnconsumed(BinTest.RTest.TestsFor));
430 return PropagationInfo();
436 setStateForVarOrTmp(ConsumedStateMap *StateMap, const PropagationInfo &PInfo,
437 ConsumedState State) {
439 assert(PInfo.isVar() || PInfo.isTmp());
442 StateMap->setState(PInfo.getVar(), State);
444 StateMap->setState(PInfo.getTmp(), State);
447 class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> {
449 typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType;
450 typedef std::pair<const Stmt *, PropagationInfo> PairType;
451 typedef MapType::iterator InfoEntry;
452 typedef MapType::const_iterator ConstInfoEntry;
454 AnalysisDeclContext &AC;
455 ConsumedAnalyzer &Analyzer;
456 ConsumedStateMap *StateMap;
457 MapType PropagationMap;
458 void forwardInfo(const Stmt *From, const Stmt *To);
459 bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
460 void propagateReturnType(const Stmt *Call, const FunctionDecl *Fun,
461 QualType ReturnType);
464 void checkCallability(const PropagationInfo &PInfo,
465 const FunctionDecl *FunDecl,
466 SourceLocation BlameLoc);
468 void VisitBinaryOperator(const BinaryOperator *BinOp);
469 void VisitCallExpr(const CallExpr *Call);
470 void VisitCastExpr(const CastExpr *Cast);
471 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *Temp);
472 void VisitCXXConstructExpr(const CXXConstructExpr *Call);
473 void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call);
474 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call);
475 void VisitDeclRefExpr(const DeclRefExpr *DeclRef);
476 void VisitDeclStmt(const DeclStmt *DelcS);
477 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp);
478 void VisitMemberExpr(const MemberExpr *MExpr);
479 void VisitParmVarDecl(const ParmVarDecl *Param);
480 void VisitReturnStmt(const ReturnStmt *Ret);
481 void VisitUnaryOperator(const UnaryOperator *UOp);
482 void VisitVarDecl(const VarDecl *Var);
484 ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer,
485 ConsumedStateMap *StateMap)
486 : AC(AC), Analyzer(Analyzer), StateMap(StateMap) {}
488 PropagationInfo getInfo(const Stmt *StmtNode) const {
489 ConstInfoEntry Entry = PropagationMap.find(StmtNode);
491 if (Entry != PropagationMap.end())
492 return Entry->second;
494 return PropagationInfo();
497 void reset(ConsumedStateMap *NewStateMap) {
498 StateMap = NewStateMap;
502 void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo,
503 const FunctionDecl *FunDecl,
504 SourceLocation BlameLoc) {
505 assert(!PInfo.isTest());
507 if (!FunDecl->hasAttr<CallableWhenAttr>())
510 const CallableWhenAttr *CWAttr = FunDecl->getAttr<CallableWhenAttr>();
513 ConsumedState VarState = StateMap->getState(PInfo.getVar());
515 if (VarState == CS_None || isCallableInState(CWAttr, VarState))
518 Analyzer.WarningsHandler.warnUseInInvalidState(
519 FunDecl->getNameAsString(), PInfo.getVar()->getNameAsString(),
520 stateToString(VarState), BlameLoc);
523 ConsumedState TmpState = PInfo.getAsState(StateMap);
525 if (TmpState == CS_None || isCallableInState(CWAttr, TmpState))
528 Analyzer.WarningsHandler.warnUseOfTempInInvalidState(
529 FunDecl->getNameAsString(), stateToString(TmpState), BlameLoc);
533 void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) {
534 InfoEntry Entry = PropagationMap.find(From);
536 if (Entry != PropagationMap.end())
537 PropagationMap.insert(PairType(To, Entry->second));
540 bool ConsumedStmtVisitor::isLikeMoveAssignment(
541 const CXXMethodDecl *MethodDecl) {
543 return MethodDecl->isMoveAssignmentOperator() ||
544 (MethodDecl->getOverloadedOperator() == OO_Equal &&
545 MethodDecl->getNumParams() == 1 &&
546 MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType());
549 void ConsumedStmtVisitor::propagateReturnType(const Stmt *Call,
550 const FunctionDecl *Fun,
551 QualType ReturnType) {
552 if (isConsumableType(ReturnType)) {
554 ConsumedState ReturnState;
556 if (Fun->hasAttr<ReturnTypestateAttr>())
557 ReturnState = mapReturnTypestateAttrState(
558 Fun->getAttr<ReturnTypestateAttr>());
560 ReturnState = mapConsumableAttrState(ReturnType);
562 PropagationMap.insert(PairType(Call, PropagationInfo(ReturnState)));
566 void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) {
567 switch (BinOp->getOpcode()) {
570 InfoEntry LEntry = PropagationMap.find(BinOp->getLHS()),
571 REntry = PropagationMap.find(BinOp->getRHS());
573 VarTestResult LTest, RTest;
575 if (LEntry != PropagationMap.end() && LEntry->second.isVarTest()) {
576 LTest = LEntry->second.getVarTest();
580 LTest.TestsFor = CS_None;
583 if (REntry != PropagationMap.end() && REntry->second.isVarTest()) {
584 RTest = REntry->second.getVarTest();
588 RTest.TestsFor = CS_None;
591 if (!(LTest.Var == NULL && RTest.Var == NULL))
592 PropagationMap.insert(PairType(BinOp, PropagationInfo(BinOp,
593 static_cast<EffectiveOp>(BinOp->getOpcode() == BO_LOr), LTest, RTest)));
600 forwardInfo(BinOp->getLHS(), BinOp);
608 void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) {
609 if (const FunctionDecl *FunDecl =
610 dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
612 // Special case for the std::move function.
613 // TODO: Make this more specific. (Deferred)
614 if (FunDecl->getNameAsString() == "move") {
615 forwardInfo(Call->getArg(0), Call);
619 unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams();
621 for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) {
622 const ParmVarDecl *Param = FunDecl->getParamDecl(Index - Offset);
623 QualType ParamType = Param->getType();
625 InfoEntry Entry = PropagationMap.find(Call->getArg(Index));
627 if (Entry == PropagationMap.end() || Entry->second.isTest())
630 PropagationInfo PInfo = Entry->second;
632 // Check that the parameter is in the correct state.
634 if (Param->hasAttr<ParamTypestateAttr>()) {
635 ConsumedState ParamState = PInfo.getAsState(StateMap);
637 ConsumedState ExpectedState =
638 mapParamTypestateAttrState(Param->getAttr<ParamTypestateAttr>());
640 if (ParamState != ExpectedState)
641 Analyzer.WarningsHandler.warnParamTypestateMismatch(
642 Call->getArg(Index - Offset)->getExprLoc(),
643 stateToString(ExpectedState), stateToString(ParamState));
646 if (!(Entry->second.isVar() || Entry->second.isTmp()))
649 // Adjust state on the caller side.
651 if (isRValueRefish(ParamType)) {
652 setStateForVarOrTmp(StateMap, PInfo, consumed::CS_Consumed);
654 } else if (Param->hasAttr<ReturnTypestateAttr>()) {
655 setStateForVarOrTmp(StateMap, PInfo,
656 mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>()));
658 } else if (!isValueType(ParamType) &&
659 !ParamType->getPointeeType().isConstQualified()) {
661 setStateForVarOrTmp(StateMap, PInfo, consumed::CS_Unknown);
665 QualType RetType = FunDecl->getCallResultType();
666 if (RetType->isReferenceType())
667 RetType = RetType->getPointeeType();
669 propagateReturnType(Call, FunDecl, RetType);
673 void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) {
674 forwardInfo(Cast->getSubExpr(), Cast);
677 void ConsumedStmtVisitor::VisitCXXBindTemporaryExpr(
678 const CXXBindTemporaryExpr *Temp) {
680 InfoEntry Entry = PropagationMap.find(Temp->getSubExpr());
682 if (Entry != PropagationMap.end() && !Entry->second.isTest()) {
683 StateMap->setState(Temp, Entry->second.getAsState(StateMap));
684 PropagationMap.insert(PairType(Temp, PropagationInfo(Temp)));
688 void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) {
689 CXXConstructorDecl *Constructor = Call->getConstructor();
691 ASTContext &CurrContext = AC.getASTContext();
692 QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType();
694 if (!isConsumableType(ThisType))
697 // FIXME: What should happen if someone annotates the move constructor?
698 if (Constructor->hasAttr<ReturnTypestateAttr>()) {
699 // TODO: Adjust state of args appropriately.
701 ReturnTypestateAttr *RTAttr = Constructor->getAttr<ReturnTypestateAttr>();
702 ConsumedState RetState = mapReturnTypestateAttrState(RTAttr);
703 PropagationMap.insert(PairType(Call, PropagationInfo(RetState)));
705 } else if (Constructor->isDefaultConstructor()) {
707 PropagationMap.insert(PairType(Call,
708 PropagationInfo(consumed::CS_Consumed)));
710 } else if (Constructor->isMoveConstructor()) {
712 InfoEntry Entry = PropagationMap.find(Call->getArg(0));
714 if (Entry != PropagationMap.end()) {
715 PropagationInfo PInfo = Entry->second;
718 const VarDecl* Var = PInfo.getVar();
720 PropagationMap.insert(PairType(Call,
721 PropagationInfo(StateMap->getState(Var))));
723 StateMap->setState(Var, consumed::CS_Consumed);
725 } else if (PInfo.isTmp()) {
726 const CXXBindTemporaryExpr *Tmp = PInfo.getTmp();
728 PropagationMap.insert(PairType(Call,
729 PropagationInfo(StateMap->getState(Tmp))));
731 StateMap->setState(Tmp, consumed::CS_Consumed);
734 PropagationMap.insert(PairType(Call, PInfo));
737 } else if (Constructor->isCopyConstructor()) {
738 forwardInfo(Call->getArg(0), Call);
741 // TODO: Adjust state of args appropriately.
743 ConsumedState RetState = mapConsumableAttrState(ThisType);
744 PropagationMap.insert(PairType(Call, PropagationInfo(RetState)));
748 void ConsumedStmtVisitor::VisitCXXMemberCallExpr(
749 const CXXMemberCallExpr *Call) {
753 InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
755 if (Entry != PropagationMap.end()) {
756 PropagationInfo PInfo = Entry->second;
757 const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
759 checkCallability(PInfo, MethodDecl, Call->getExprLoc());
762 if (isTestingFunction(MethodDecl))
763 PropagationMap.insert(PairType(Call,
764 PropagationInfo(PInfo.getVar(), testsFor(MethodDecl))));
765 else if (MethodDecl->hasAttr<SetTypestateAttr>())
766 StateMap->setState(PInfo.getVar(),
767 mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>()));
768 } else if (PInfo.isTmp() && MethodDecl->hasAttr<SetTypestateAttr>()) {
769 StateMap->setState(PInfo.getTmp(),
770 mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>()));
775 void ConsumedStmtVisitor::VisitCXXOperatorCallExpr(
776 const CXXOperatorCallExpr *Call) {
778 const FunctionDecl *FunDecl =
779 dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee());
781 if (!FunDecl) return;
783 if (isa<CXXMethodDecl>(FunDecl) &&
784 isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) {
786 InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
787 InfoEntry REntry = PropagationMap.find(Call->getArg(1));
789 PropagationInfo LPInfo, RPInfo;
791 if (LEntry != PropagationMap.end() &&
792 REntry != PropagationMap.end()) {
794 LPInfo = LEntry->second;
795 RPInfo = REntry->second;
797 if (LPInfo.isPointerToValue() && RPInfo.isPointerToValue()) {
798 setStateForVarOrTmp(StateMap, LPInfo, RPInfo.getAsState(StateMap));
799 PropagationMap.insert(PairType(Call, LPInfo));
800 setStateForVarOrTmp(StateMap, RPInfo, consumed::CS_Consumed);
802 } else if (RPInfo.isState()) {
803 setStateForVarOrTmp(StateMap, LPInfo, RPInfo.getState());
804 PropagationMap.insert(PairType(Call, LPInfo));
807 setStateForVarOrTmp(StateMap, RPInfo, consumed::CS_Consumed);
810 } else if (LEntry != PropagationMap.end() &&
811 REntry == PropagationMap.end()) {
813 LPInfo = LEntry->second;
815 assert(!LPInfo.isTest());
817 if (LPInfo.isPointerToValue()) {
818 setStateForVarOrTmp(StateMap, LPInfo, consumed::CS_Unknown);
819 PropagationMap.insert(PairType(Call, LPInfo));
822 PropagationMap.insert(PairType(Call,
823 PropagationInfo(consumed::CS_Unknown)));
826 } else if (LEntry == PropagationMap.end() &&
827 REntry != PropagationMap.end()) {
829 RPInfo = REntry->second;
831 if (RPInfo.isPointerToValue())
832 setStateForVarOrTmp(StateMap, RPInfo, consumed::CS_Consumed);
839 InfoEntry Entry = PropagationMap.find(Call->getArg(0));
841 if (Entry != PropagationMap.end()) {
842 PropagationInfo PInfo = Entry->second;
844 checkCallability(PInfo, FunDecl, Call->getExprLoc());
847 if (isTestingFunction(FunDecl))
848 PropagationMap.insert(PairType(Call,
849 PropagationInfo(PInfo.getVar(), testsFor(FunDecl))));
850 else if (FunDecl->hasAttr<SetTypestateAttr>())
851 StateMap->setState(PInfo.getVar(),
852 mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>()));
854 } else if (PInfo.isTmp() && FunDecl->hasAttr<SetTypestateAttr>()) {
855 StateMap->setState(PInfo.getTmp(),
856 mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>()));
862 void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) {
863 if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
864 if (StateMap->getState(Var) != consumed::CS_None)
865 PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
868 void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) {
869 for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(),
870 DE = DeclS->decl_end(); DI != DE; ++DI) {
872 if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI));
875 if (DeclS->isSingleDecl())
876 if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl()))
877 PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
880 void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
881 const MaterializeTemporaryExpr *Temp) {
883 forwardInfo(Temp->GetTemporaryExpr(), Temp);
886 void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
887 forwardInfo(MExpr->getBase(), MExpr);
891 void ConsumedStmtVisitor::VisitParmVarDecl(const ParmVarDecl *Param) {
892 QualType ParamType = Param->getType();
893 ConsumedState ParamState = consumed::CS_None;
895 if (Param->hasAttr<ParamTypestateAttr>()) {
896 const ParamTypestateAttr *PTAttr = Param->getAttr<ParamTypestateAttr>();
897 ParamState = mapParamTypestateAttrState(PTAttr);
899 } else if (isConsumableType(ParamType)) {
900 ParamState = mapConsumableAttrState(ParamType);
902 } else if (isRValueRefish(ParamType) &&
903 isConsumableType(ParamType->getPointeeType())) {
905 ParamState = mapConsumableAttrState(ParamType->getPointeeType());
907 } else if (ParamType->isReferenceType() &&
908 isConsumableType(ParamType->getPointeeType())) {
909 ParamState = consumed::CS_Unknown;
912 if (ParamState != CS_None)
913 StateMap->setState(Param, ParamState);
916 void ConsumedStmtVisitor::VisitReturnStmt(const ReturnStmt *Ret) {
917 ConsumedState ExpectedState = Analyzer.getExpectedReturnState();
919 if (ExpectedState != CS_None) {
920 InfoEntry Entry = PropagationMap.find(Ret->getRetValue());
922 if (Entry != PropagationMap.end()) {
923 ConsumedState RetState = Entry->second.getAsState(StateMap);
925 if (RetState != ExpectedState)
926 Analyzer.WarningsHandler.warnReturnTypestateMismatch(
927 Ret->getReturnLoc(), stateToString(ExpectedState),
928 stateToString(RetState));
932 StateMap->checkParamsForReturnTypestate(Ret->getLocStart(),
933 Analyzer.WarningsHandler);
936 void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) {
937 InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens());
938 if (Entry == PropagationMap.end()) return;
940 switch (UOp->getOpcode()) {
942 PropagationMap.insert(PairType(UOp, Entry->second));
946 if (Entry->second.isTest())
947 PropagationMap.insert(PairType(UOp, Entry->second.invertTest()));
955 // TODO: See if I need to check for reference types here.
956 void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
957 if (isConsumableType(Var->getType())) {
958 if (Var->hasInit()) {
959 MapType::iterator VIT = PropagationMap.find(
960 Var->getInit()->IgnoreImplicit());
961 if (VIT != PropagationMap.end()) {
962 PropagationInfo PInfo = VIT->second;
963 ConsumedState St = PInfo.getAsState(StateMap);
965 if (St != consumed::CS_None) {
966 StateMap->setState(Var, St);
972 StateMap->setState(Var, consumed::CS_Unknown);
975 }} // end clang::consumed::ConsumedStmtVisitor
980 void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test,
981 ConsumedStateMap *ThenStates,
982 ConsumedStateMap *ElseStates) {
984 ConsumedState VarState = ThenStates->getState(Test.Var);
986 if (VarState == CS_Unknown) {
987 ThenStates->setState(Test.Var, Test.TestsFor);
988 ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
990 } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) {
991 ThenStates->markUnreachable();
993 } else if (VarState == Test.TestsFor) {
994 ElseStates->markUnreachable();
998 void splitVarStateForIfBinOp(const PropagationInfo &PInfo,
999 ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) {
1001 const VarTestResult <est = PInfo.getLTest(),
1002 &RTest = PInfo.getRTest();
1004 ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None,
1005 RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None;
1008 if (PInfo.testEffectiveOp() == EO_And) {
1009 if (LState == CS_Unknown) {
1010 ThenStates->setState(LTest.Var, LTest.TestsFor);
1012 } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) {
1013 ThenStates->markUnreachable();
1015 } else if (LState == LTest.TestsFor && isKnownState(RState)) {
1016 if (RState == RTest.TestsFor)
1017 ElseStates->markUnreachable();
1019 ThenStates->markUnreachable();
1023 if (LState == CS_Unknown) {
1024 ElseStates->setState(LTest.Var,
1025 invertConsumedUnconsumed(LTest.TestsFor));
1027 } else if (LState == LTest.TestsFor) {
1028 ElseStates->markUnreachable();
1030 } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) &&
1031 isKnownState(RState)) {
1033 if (RState == RTest.TestsFor)
1034 ElseStates->markUnreachable();
1036 ThenStates->markUnreachable();
1042 if (PInfo.testEffectiveOp() == EO_And) {
1043 if (RState == CS_Unknown)
1044 ThenStates->setState(RTest.Var, RTest.TestsFor);
1045 else if (RState == invertConsumedUnconsumed(RTest.TestsFor))
1046 ThenStates->markUnreachable();
1049 if (RState == CS_Unknown)
1050 ElseStates->setState(RTest.Var,
1051 invertConsumedUnconsumed(RTest.TestsFor));
1052 else if (RState == RTest.TestsFor)
1053 ElseStates->markUnreachable();
1058 bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock,
1059 const CFGBlock *TargetBlock) {
1061 assert(CurrBlock && "Block pointer must not be NULL");
1062 assert(TargetBlock && "TargetBlock pointer must not be NULL");
1064 unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()];
1065 for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(),
1066 PE = TargetBlock->pred_end(); PI != PE; ++PI) {
1067 if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] )
1073 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1074 ConsumedStateMap *StateMap,
1075 bool &AlreadyOwned) {
1077 assert(Block && "Block pointer must not be NULL");
1079 ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1082 Entry->intersect(StateMap);
1084 } else if (AlreadyOwned) {
1085 StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap);
1088 StateMapsArray[Block->getBlockID()] = StateMap;
1089 AlreadyOwned = true;
1093 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1094 ConsumedStateMap *StateMap) {
1096 assert(Block != NULL && "Block pointer must not be NULL");
1098 ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1101 Entry->intersect(StateMap);
1105 StateMapsArray[Block->getBlockID()] = StateMap;
1109 ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) {
1110 assert(Block && "Block pointer must not be NULL");
1111 assert(StateMapsArray[Block->getBlockID()] && "Block has no block info");
1113 return StateMapsArray[Block->getBlockID()];
1116 void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) {
1117 unsigned int BlockID = Block->getBlockID();
1118 delete StateMapsArray[BlockID];
1119 StateMapsArray[BlockID] = NULL;
1122 ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
1123 assert(Block && "Block pointer must not be NULL");
1125 ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()];
1126 if (isBackEdgeTarget(Block)) {
1127 return new ConsumedStateMap(*StateMap);
1129 StateMapsArray[Block->getBlockID()] = NULL;
1134 bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) {
1135 assert(From && "From block must not be NULL");
1136 assert(To && "From block must not be NULL");
1138 return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()];
1141 bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) {
1142 assert(Block != NULL && "Block pointer must not be NULL");
1144 // Anything with less than two predecessors can't be the target of a back
1146 if (Block->pred_size() < 2)
1149 unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()];
1150 for (CFGBlock::const_pred_iterator PI = Block->pred_begin(),
1151 PE = Block->pred_end(); PI != PE; ++PI) {
1152 if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()])
1158 void ConsumedStateMap::checkParamsForReturnTypestate(SourceLocation BlameLoc,
1159 ConsumedWarningsHandlerBase &WarningsHandler) const {
1161 ConsumedState ExpectedState;
1163 for (VarMapType::const_iterator DMI = VarMap.begin(), DME = VarMap.end();
1164 DMI != DME; ++DMI) {
1166 if (isa<ParmVarDecl>(DMI->first)) {
1167 const ParmVarDecl *Param = cast<ParmVarDecl>(DMI->first);
1169 if (!Param->hasAttr<ReturnTypestateAttr>()) continue;
1172 mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>());
1174 if (DMI->second != ExpectedState) {
1175 WarningsHandler.warnParamReturnTypestateMismatch(BlameLoc,
1176 Param->getNameAsString(), stateToString(ExpectedState),
1177 stateToString(DMI->second));
1183 void ConsumedStateMap::clearTemporaries() {
1187 ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const {
1188 VarMapType::const_iterator Entry = VarMap.find(Var);
1190 if (Entry != VarMap.end())
1191 return Entry->second;
1197 ConsumedStateMap::getState(const CXXBindTemporaryExpr *Tmp) const {
1198 TmpMapType::const_iterator Entry = TmpMap.find(Tmp);
1200 if (Entry != TmpMap.end())
1201 return Entry->second;
1206 void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
1207 ConsumedState LocalState;
1209 if (this->From && this->From == Other->From && !Other->Reachable) {
1210 this->markUnreachable();
1214 for (VarMapType::const_iterator DMI = Other->VarMap.begin(),
1215 DME = Other->VarMap.end(); DMI != DME; ++DMI) {
1217 LocalState = this->getState(DMI->first);
1219 if (LocalState == CS_None)
1222 if (LocalState != DMI->second)
1223 VarMap[DMI->first] = CS_Unknown;
1227 void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead,
1228 const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates,
1229 ConsumedWarningsHandlerBase &WarningsHandler) {
1231 ConsumedState LocalState;
1232 SourceLocation BlameLoc = getLastStmtLoc(LoopBack);
1234 for (VarMapType::const_iterator DMI = LoopBackStates->VarMap.begin(),
1235 DME = LoopBackStates->VarMap.end(); DMI != DME; ++DMI) {
1237 LocalState = this->getState(DMI->first);
1239 if (LocalState == CS_None)
1242 if (LocalState != DMI->second) {
1243 VarMap[DMI->first] = CS_Unknown;
1244 WarningsHandler.warnLoopStateMismatch(
1245 BlameLoc, DMI->first->getNameAsString());
1250 void ConsumedStateMap::markUnreachable() {
1251 this->Reachable = false;
1256 void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
1257 VarMap[Var] = State;
1260 void ConsumedStateMap::setState(const CXXBindTemporaryExpr *Tmp,
1261 ConsumedState State) {
1262 TmpMap[Tmp] = State;
1265 void ConsumedStateMap::remove(const VarDecl *Var) {
1269 bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const {
1270 for (VarMapType::const_iterator DMI = Other->VarMap.begin(),
1271 DME = Other->VarMap.end(); DMI != DME; ++DMI) {
1273 if (this->getState(DMI->first) != DMI->second)
1280 void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC,
1281 const FunctionDecl *D) {
1282 QualType ReturnType;
1283 if (const CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
1284 ASTContext &CurrContext = AC.getASTContext();
1285 ReturnType = Constructor->getThisType(CurrContext)->getPointeeType();
1287 ReturnType = D->getCallResultType();
1289 if (D->hasAttr<ReturnTypestateAttr>()) {
1290 const ReturnTypestateAttr *RTSAttr = D->getAttr<ReturnTypestateAttr>();
1292 const CXXRecordDecl *RD = ReturnType->getAsCXXRecordDecl();
1293 if (!RD || !RD->hasAttr<ConsumableAttr>()) {
1294 // FIXME: This should be removed when template instantiation propagates
1295 // attributes at template specialization definition, not
1296 // declaration. When it is removed the test needs to be enabled
1297 // in SemaDeclAttr.cpp.
1298 WarningsHandler.warnReturnTypestateForUnconsumableType(
1299 RTSAttr->getLocation(), ReturnType.getAsString());
1300 ExpectedReturnState = CS_None;
1302 ExpectedReturnState = mapReturnTypestateAttrState(RTSAttr);
1303 } else if (isConsumableType(ReturnType))
1304 ExpectedReturnState = mapConsumableAttrState(ReturnType);
1306 ExpectedReturnState = CS_None;
1309 bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
1310 const ConsumedStmtVisitor &Visitor) {
1312 OwningPtr<ConsumedStateMap> FalseStates(new ConsumedStateMap(*CurrStates));
1313 PropagationInfo PInfo;
1315 if (const IfStmt *IfNode =
1316 dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
1318 const Stmt *Cond = IfNode->getCond();
1320 PInfo = Visitor.getInfo(Cond);
1321 if (!PInfo.isValid() && isa<BinaryOperator>(Cond))
1322 PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS());
1324 if (PInfo.isVarTest()) {
1325 CurrStates->setSource(Cond);
1326 FalseStates->setSource(Cond);
1327 splitVarStateForIf(IfNode, PInfo.getVarTest(), CurrStates,
1330 } else if (PInfo.isBinTest()) {
1331 CurrStates->setSource(PInfo.testSourceNode());
1332 FalseStates->setSource(PInfo.testSourceNode());
1333 splitVarStateForIfBinOp(PInfo, CurrStates, FalseStates.get());
1339 } else if (const BinaryOperator *BinOp =
1340 dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) {
1342 PInfo = Visitor.getInfo(BinOp->getLHS());
1343 if (!PInfo.isVarTest()) {
1344 if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) {
1345 PInfo = Visitor.getInfo(BinOp->getRHS());
1347 if (!PInfo.isVarTest())
1355 CurrStates->setSource(BinOp);
1356 FalseStates->setSource(BinOp);
1358 const VarTestResult &Test = PInfo.getVarTest();
1359 ConsumedState VarState = CurrStates->getState(Test.Var);
1361 if (BinOp->getOpcode() == BO_LAnd) {
1362 if (VarState == CS_Unknown)
1363 CurrStates->setState(Test.Var, Test.TestsFor);
1364 else if (VarState == invertConsumedUnconsumed(Test.TestsFor))
1365 CurrStates->markUnreachable();
1367 } else if (BinOp->getOpcode() == BO_LOr) {
1368 if (VarState == CS_Unknown)
1369 FalseStates->setState(Test.Var,
1370 invertConsumedUnconsumed(Test.TestsFor));
1371 else if (VarState == Test.TestsFor)
1372 FalseStates->markUnreachable();
1379 CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
1382 BlockInfo.addInfo(*SI, CurrStates);
1387 BlockInfo.addInfo(*SI, FalseStates.take());
1393 void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
1394 const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
1398 CFG *CFGraph = AC.getCFG();
1402 determineExpectedReturnState(AC, D);
1404 PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
1405 // AC.getCFG()->viewCFG(LangOptions());
1407 BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
1409 CurrStates = new ConsumedStateMap();
1410 ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
1412 // Add all trackable parameters to the state map.
1413 for (FunctionDecl::param_const_iterator PI = D->param_begin(),
1414 PE = D->param_end(); PI != PE; ++PI) {
1415 Visitor.VisitParmVarDecl(*PI);
1418 // Visit all of the function's basic blocks.
1419 for (PostOrderCFGView::iterator I = SortedGraph->begin(),
1420 E = SortedGraph->end(); I != E; ++I) {
1422 const CFGBlock *CurrBlock = *I;
1424 if (CurrStates == NULL)
1425 CurrStates = BlockInfo.getInfo(CurrBlock);
1430 } else if (!CurrStates->isReachable()) {
1436 Visitor.reset(CurrStates);
1438 // Visit all of the basic block's statements.
1439 for (CFGBlock::const_iterator BI = CurrBlock->begin(),
1440 BE = CurrBlock->end(); BI != BE; ++BI) {
1442 switch (BI->getKind()) {
1443 case CFGElement::Statement:
1444 Visitor.Visit(BI->castAs<CFGStmt>().getStmt());
1447 case CFGElement::TemporaryDtor: {
1448 const CFGTemporaryDtor DTor = BI->castAs<CFGTemporaryDtor>();
1449 const CXXBindTemporaryExpr *BTE = DTor.getBindTemporaryExpr();
1451 Visitor.checkCallability(PropagationInfo(BTE),
1452 DTor.getDestructorDecl(AC.getASTContext()),
1457 case CFGElement::AutomaticObjectDtor: {
1458 const CFGAutomaticObjDtor DTor = BI->castAs<CFGAutomaticObjDtor>();
1459 SourceLocation Loc = DTor.getTriggerStmt()->getLocEnd();
1460 const VarDecl *Var = DTor.getVarDecl();
1462 Visitor.checkCallability(PropagationInfo(Var),
1463 DTor.getDestructorDecl(AC.getASTContext()),
1473 CurrStates->clearTemporaries();
1475 // TODO: Handle other forms of branching with precision, including while-
1476 // and for-loops. (Deferred)
1477 if (!splitState(CurrBlock, Visitor)) {
1478 CurrStates->setSource(NULL);
1480 if (CurrBlock->succ_size() > 1 ||
1481 (CurrBlock->succ_size() == 1 &&
1482 (*CurrBlock->succ_begin())->pred_size() > 1)) {
1484 bool OwnershipTaken = false;
1486 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
1487 SE = CurrBlock->succ_end(); SI != SE; ++SI) {
1489 if (*SI == NULL) continue;
1491 if (BlockInfo.isBackEdge(CurrBlock, *SI)) {
1492 BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock,
1496 if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock))
1497 BlockInfo.discardInfo(*SI);
1499 BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
1503 if (!OwnershipTaken)
1510 if (CurrBlock == &AC.getCFG()->getExit() &&
1511 D->getCallResultType()->isVoidType())
1512 CurrStates->checkParamsForReturnTypestate(D->getLocation(),
1514 } // End of block iterator.
1516 // Delete the last existing state map.
1519 WarningsHandler.emitDiagnostics();
1521 }} // end namespace clang::consumed