xref: /llvm-project/clang/lib/Analysis/Consumed.cpp (revision 93edffa8fe3d1e042dcceecda6d62dc090fee346) 
1 //===- Consumed.cpp --------------------------------------------*- C++ --*-===//
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 // A intra-procedural analysis for checking consumed properties.  This is based,
11 // in part, on research on linear types.
12 //
13 //===----------------------------------------------------------------------===//
14 
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"
34 
35 // TODO: Use information from tests in while-loop conditional.
36 // TODO: Add notes about the actual and expected state for
37 // TODO: Correctly identify unreachable blocks when chaining boolean operators.
38 // TODO: Adjust the parser and AttributesList class to support lists of
39 //       identifiers.
40 // TODO: Warn about unreachable code.
41 // TODO: Switch to using a bitmap to track unreachable blocks.
42 // TODO: Handle variable definitions, e.g. bool valid = x.isValid();
43 //       if (valid) ...; (Deferred)
44 // TODO: Take notes on state transitions to provide better warning messages.
45 //       (Deferred)
46 // TODO: Test nested conditionals: A) Checking the same value multiple times,
47 //       and 2) Checking different values. (Deferred)
48 
49 using namespace clang;
50 using namespace consumed;
51 
52 // Key method definition
53 ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
54 
55 static SourceLocation getFirstStmtLoc(const CFGBlock *Block) {
56   // Find the source location of the first statement in the block, if the block
57   // is not empty.
58   for (CFGBlock::const_iterator BI = Block->begin(), BE = Block->end();
59        BI != BE; ++BI) {
60     if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
61       return CS->getStmt()->getLocStart();
62   }
63 
64   // Block is empty.
65   // If we have one successor, return the first statement in that block
66   if (Block->succ_size() == 1 && *Block->succ_begin())
67     return getFirstStmtLoc(*Block->succ_begin());
68 
69   return SourceLocation();
70 }
71 
72 static SourceLocation getLastStmtLoc(const CFGBlock *Block) {
73   // Find the source location of the last statement in the block, if the block
74   // is not empty.
75   if (const Stmt *StmtNode = Block->getTerminator()) {
76     return StmtNode->getLocStart();
77   } else {
78     for (CFGBlock::const_reverse_iterator BI = Block->rbegin(),
79          BE = Block->rend(); BI != BE; ++BI) {
80       if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
81         return CS->getStmt()->getLocStart();
82     }
83   }
84 
85   // If we have one successor, return the first statement in that block
86   SourceLocation Loc;
87   if (Block->succ_size() == 1 && *Block->succ_begin())
88     Loc = getFirstStmtLoc(*Block->succ_begin());
89   if (Loc.isValid())
90     return Loc;
91 
92   // If we have one predecessor, return the last statement in that block
93   if (Block->pred_size() == 1 && *Block->pred_begin())
94     return getLastStmtLoc(*Block->pred_begin());
95 
96   return Loc;
97 }
98 
99 static ConsumedState invertConsumedUnconsumed(ConsumedState State) {
100   switch (State) {
101   case CS_Unconsumed:
102     return CS_Consumed;
103   case CS_Consumed:
104     return CS_Unconsumed;
105   case CS_None:
106     return CS_None;
107   case CS_Unknown:
108     return CS_Unknown;
109   }
110   llvm_unreachable("invalid enum");
111 }
112 
113 static bool isCallableInState(const CallableWhenAttr *CWAttr,
114                               ConsumedState State) {
115 
116   CallableWhenAttr::callableState_iterator I = CWAttr->callableState_begin(),
117                                            E = CWAttr->callableState_end();
118 
119   for (; I != E; ++I) {
120 
121     ConsumedState MappedAttrState = CS_None;
122 
123     switch (*I) {
124     case CallableWhenAttr::Unknown:
125       MappedAttrState = CS_Unknown;
126       break;
127 
128     case CallableWhenAttr::Unconsumed:
129       MappedAttrState = CS_Unconsumed;
130       break;
131 
132     case CallableWhenAttr::Consumed:
133       MappedAttrState = CS_Consumed;
134       break;
135     }
136 
137     if (MappedAttrState == State)
138       return true;
139   }
140 
141   return false;
142 }
143 
144 static bool isConsumableType(const QualType &QT) {
145   if (QT->isPointerType() || QT->isReferenceType())
146     return false;
147 
148   if (const CXXRecordDecl *RD = QT->getAsCXXRecordDecl())
149     return RD->hasAttr<ConsumableAttr>();
150 
151   return false;
152 }
153 
154 static bool isKnownState(ConsumedState State) {
155   switch (State) {
156   case CS_Unconsumed:
157   case CS_Consumed:
158     return true;
159   case CS_None:
160   case CS_Unknown:
161     return false;
162   }
163   llvm_unreachable("invalid enum");
164 }
165 
166 static bool isRValueRefish(QualType ParamType) {
167   return ParamType->isRValueReferenceType() ||
168         (ParamType->isLValueReferenceType() &&
169          !cast<LValueReferenceType>(
170            ParamType.getCanonicalType())->isSpelledAsLValue());
171 }
172 
173 static bool isTestingFunction(const FunctionDecl *FunDecl) {
174   return FunDecl->hasAttr<TestTypestateAttr>();
175 }
176 
177 static bool isValueType(QualType ParamType) {
178   return !(ParamType->isPointerType() || ParamType->isReferenceType());
179 }
180 
181 static ConsumedState mapConsumableAttrState(const QualType QT) {
182   assert(isConsumableType(QT));
183 
184   const ConsumableAttr *CAttr =
185       QT->getAsCXXRecordDecl()->getAttr<ConsumableAttr>();
186 
187   switch (CAttr->getDefaultState()) {
188   case ConsumableAttr::Unknown:
189     return CS_Unknown;
190   case ConsumableAttr::Unconsumed:
191     return CS_Unconsumed;
192   case ConsumableAttr::Consumed:
193     return CS_Consumed;
194   }
195   llvm_unreachable("invalid enum");
196 }
197 
198 static ConsumedState
199 mapParamTypestateAttrState(const ParamTypestateAttr *PTAttr) {
200   switch (PTAttr->getParamState()) {
201   case ParamTypestateAttr::Unknown:
202     return CS_Unknown;
203   case ParamTypestateAttr::Unconsumed:
204     return CS_Unconsumed;
205   case ParamTypestateAttr::Consumed:
206     return CS_Consumed;
207   }
208   llvm_unreachable("invalid_enum");
209 }
210 
211 static ConsumedState
212 mapReturnTypestateAttrState(const ReturnTypestateAttr *RTSAttr) {
213   switch (RTSAttr->getState()) {
214   case ReturnTypestateAttr::Unknown:
215     return CS_Unknown;
216   case ReturnTypestateAttr::Unconsumed:
217     return CS_Unconsumed;
218   case ReturnTypestateAttr::Consumed:
219     return CS_Consumed;
220   }
221   llvm_unreachable("invalid enum");
222 }
223 
224 static ConsumedState mapSetTypestateAttrState(const SetTypestateAttr *STAttr) {
225   switch (STAttr->getNewState()) {
226   case SetTypestateAttr::Unknown:
227     return CS_Unknown;
228   case SetTypestateAttr::Unconsumed:
229     return CS_Unconsumed;
230   case SetTypestateAttr::Consumed:
231     return CS_Consumed;
232   }
233   llvm_unreachable("invalid_enum");
234 }
235 
236 static StringRef stateToString(ConsumedState State) {
237   switch (State) {
238   case consumed::CS_None:
239     return "none";
240 
241   case consumed::CS_Unknown:
242     return "unknown";
243 
244   case consumed::CS_Unconsumed:
245     return "unconsumed";
246 
247   case consumed::CS_Consumed:
248     return "consumed";
249   }
250   llvm_unreachable("invalid enum");
251 }
252 
253 static ConsumedState testsFor(const FunctionDecl *FunDecl) {
254   assert(isTestingFunction(FunDecl));
255   switch (FunDecl->getAttr<TestTypestateAttr>()->getTestState()) {
256   case TestTypestateAttr::Unconsumed:
257     return CS_Unconsumed;
258   case TestTypestateAttr::Consumed:
259     return CS_Consumed;
260   }
261   llvm_unreachable("invalid enum");
262 }
263 
264 namespace {
265 struct VarTestResult {
266   const VarDecl *Var;
267   ConsumedState TestsFor;
268 };
269 } // end anonymous::VarTestResult
270 
271 namespace clang {
272 namespace consumed {
273 
274 enum EffectiveOp {
275   EO_And,
276   EO_Or
277 };
278 
279 class PropagationInfo {
280   enum {
281     IT_None,
282     IT_State,
283     IT_Test,
284     IT_BinTest,
285     IT_Var
286   } InfoType;
287 
288   struct BinTestTy {
289     const BinaryOperator *Source;
290     EffectiveOp EOp;
291     VarTestResult LTest;
292     VarTestResult RTest;
293   };
294 
295   union {
296     ConsumedState State;
297     VarTestResult Test;
298     const VarDecl *Var;
299     BinTestTy BinTest;
300   };
301 
302   QualType TempType;
303 
304 public:
305   PropagationInfo() : InfoType(IT_None) {}
306 
307   PropagationInfo(const VarTestResult &Test) : InfoType(IT_Test), Test(Test) {}
308   PropagationInfo(const VarDecl *Var, ConsumedState TestsFor)
309     : InfoType(IT_Test) {
310 
311     Test.Var      = Var;
312     Test.TestsFor = TestsFor;
313   }
314 
315   PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
316                   const VarTestResult &LTest, const VarTestResult &RTest)
317     : InfoType(IT_BinTest) {
318 
319     BinTest.Source  = Source;
320     BinTest.EOp     = EOp;
321     BinTest.LTest   = LTest;
322     BinTest.RTest   = RTest;
323   }
324 
325   PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
326                   const VarDecl *LVar, ConsumedState LTestsFor,
327                   const VarDecl *RVar, ConsumedState RTestsFor)
328     : InfoType(IT_BinTest) {
329 
330     BinTest.Source         = Source;
331     BinTest.EOp            = EOp;
332     BinTest.LTest.Var      = LVar;
333     BinTest.LTest.TestsFor = LTestsFor;
334     BinTest.RTest.Var      = RVar;
335     BinTest.RTest.TestsFor = RTestsFor;
336   }
337 
338   PropagationInfo(ConsumedState State, QualType TempType)
339     : InfoType(IT_State), State(State), TempType(TempType) {}
340 
341   PropagationInfo(const VarDecl *Var) : InfoType(IT_Var), Var(Var) {}
342 
343   const ConsumedState & getState() const {
344     assert(InfoType == IT_State);
345     return State;
346   }
347 
348   const QualType & getTempType() const {
349     assert(InfoType == IT_State);
350     return TempType;
351   }
352 
353   const VarTestResult & getTest() const {
354     assert(InfoType == IT_Test);
355     return Test;
356   }
357 
358   const VarTestResult & getLTest() const {
359     assert(InfoType == IT_BinTest);
360     return BinTest.LTest;
361   }
362 
363   const VarTestResult & getRTest() const {
364     assert(InfoType == IT_BinTest);
365     return BinTest.RTest;
366   }
367 
368   const VarDecl * getVar() const {
369     assert(InfoType == IT_Var);
370     return Var;
371   }
372 
373   EffectiveOp testEffectiveOp() const {
374     assert(InfoType == IT_BinTest);
375     return BinTest.EOp;
376   }
377 
378   const BinaryOperator * testSourceNode() const {
379     assert(InfoType == IT_BinTest);
380     return BinTest.Source;
381   }
382 
383   bool isValid()   const { return InfoType != IT_None;     }
384   bool isState()   const { return InfoType == IT_State;    }
385   bool isTest()    const { return InfoType == IT_Test;     }
386   bool isBinTest() const { return InfoType == IT_BinTest;  }
387   bool isVar()     const { return InfoType == IT_Var;      }
388 
389   PropagationInfo invertTest() const {
390     assert(InfoType == IT_Test || InfoType == IT_BinTest);
391 
392     if (InfoType == IT_Test) {
393       return PropagationInfo(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
394 
395     } else if (InfoType == IT_BinTest) {
396       return PropagationInfo(BinTest.Source,
397         BinTest.EOp == EO_And ? EO_Or : EO_And,
398         BinTest.LTest.Var, invertConsumedUnconsumed(BinTest.LTest.TestsFor),
399         BinTest.RTest.Var, invertConsumedUnconsumed(BinTest.RTest.TestsFor));
400     } else {
401       return PropagationInfo();
402     }
403   }
404 };
405 
406 class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> {
407 
408   typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType;
409   typedef std::pair<const Stmt *, PropagationInfo> PairType;
410   typedef MapType::iterator InfoEntry;
411   typedef MapType::const_iterator ConstInfoEntry;
412 
413   AnalysisDeclContext &AC;
414   ConsumedAnalyzer &Analyzer;
415   ConsumedStateMap *StateMap;
416   MapType PropagationMap;
417   void forwardInfo(const Stmt *From, const Stmt *To);
418   bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
419   void propagateReturnType(const Stmt *Call, const FunctionDecl *Fun,
420                            QualType ReturnType);
421 
422   inline ConsumedState getPInfoState(const PropagationInfo& PInfo) {
423     if (PInfo.isVar())
424       return StateMap->getState(PInfo.getVar());
425     else if (PInfo.isState())
426       return PInfo.getState();
427     else
428       return CS_None;
429   }
430 
431 public:
432   void checkCallability(const PropagationInfo &PInfo,
433                         const FunctionDecl *FunDecl,
434                         SourceLocation BlameLoc);
435 
436   void Visit(const Stmt *StmtNode);
437 
438   void VisitBinaryOperator(const BinaryOperator *BinOp);
439   void VisitCallExpr(const CallExpr *Call);
440   void VisitCastExpr(const CastExpr *Cast);
441   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *Temp);
442   void VisitCXXConstructExpr(const CXXConstructExpr *Call);
443   void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call);
444   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call);
445   void VisitDeclRefExpr(const DeclRefExpr *DeclRef);
446   void VisitDeclStmt(const DeclStmt *DelcS);
447   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp);
448   void VisitMemberExpr(const MemberExpr *MExpr);
449   void VisitParmVarDecl(const ParmVarDecl *Param);
450   void VisitReturnStmt(const ReturnStmt *Ret);
451   void VisitUnaryOperator(const UnaryOperator *UOp);
452   void VisitVarDecl(const VarDecl *Var);
453 
454   ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer,
455                       ConsumedStateMap *StateMap)
456       : AC(AC), Analyzer(Analyzer), StateMap(StateMap) {}
457 
458   PropagationInfo getInfo(const Stmt *StmtNode) const {
459     ConstInfoEntry Entry = PropagationMap.find(StmtNode);
460 
461     if (Entry != PropagationMap.end())
462       return Entry->second;
463     else
464       return PropagationInfo();
465   }
466 
467   void reset(ConsumedStateMap *NewStateMap) {
468     StateMap = NewStateMap;
469   }
470 };
471 
472 void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo,
473                                            const FunctionDecl *FunDecl,
474                                            SourceLocation BlameLoc) {
475 
476   if (!FunDecl->hasAttr<CallableWhenAttr>())
477     return;
478 
479   const CallableWhenAttr *CWAttr = FunDecl->getAttr<CallableWhenAttr>();
480 
481   if (PInfo.isVar()) {
482     const VarDecl *Var = PInfo.getVar();
483     ConsumedState VarState = StateMap->getState(Var);
484 
485     assert(VarState != CS_None && "Invalid state");
486 
487     if (isCallableInState(CWAttr, VarState))
488       return;
489 
490     Analyzer.WarningsHandler.warnUseInInvalidState(
491       FunDecl->getNameAsString(), Var->getNameAsString(),
492       stateToString(VarState), BlameLoc);
493 
494   } else if (PInfo.isState()) {
495 
496     assert(PInfo.getState() != CS_None && "Invalid state");
497 
498     if (isCallableInState(CWAttr, PInfo.getState()))
499       return;
500 
501     Analyzer.WarningsHandler.warnUseOfTempInInvalidState(
502       FunDecl->getNameAsString(), stateToString(PInfo.getState()), BlameLoc);
503   }
504 }
505 
506 void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) {
507   InfoEntry Entry = PropagationMap.find(From);
508 
509   if (Entry != PropagationMap.end())
510     PropagationMap.insert(PairType(To, Entry->second));
511 }
512 
513 bool ConsumedStmtVisitor::isLikeMoveAssignment(
514   const CXXMethodDecl *MethodDecl) {
515 
516   return MethodDecl->isMoveAssignmentOperator() ||
517          (MethodDecl->getOverloadedOperator() == OO_Equal &&
518           MethodDecl->getNumParams() == 1 &&
519           MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType());
520 }
521 
522 void ConsumedStmtVisitor::propagateReturnType(const Stmt *Call,
523                                               const FunctionDecl *Fun,
524                                               QualType ReturnType) {
525   if (isConsumableType(ReturnType)) {
526 
527     ConsumedState ReturnState;
528 
529     if (Fun->hasAttr<ReturnTypestateAttr>())
530       ReturnState = mapReturnTypestateAttrState(
531         Fun->getAttr<ReturnTypestateAttr>());
532     else
533       ReturnState = mapConsumableAttrState(ReturnType);
534 
535     PropagationMap.insert(PairType(Call,
536       PropagationInfo(ReturnState, ReturnType)));
537   }
538 }
539 
540 void ConsumedStmtVisitor::Visit(const Stmt *StmtNode) {
541 
542   ConstStmtVisitor<ConsumedStmtVisitor>::Visit(StmtNode);
543 
544   for (Stmt::const_child_iterator CI = StmtNode->child_begin(),
545        CE = StmtNode->child_end(); CI != CE; ++CI) {
546 
547     PropagationMap.erase(*CI);
548   }
549 }
550 
551 void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) {
552   switch (BinOp->getOpcode()) {
553   case BO_LAnd:
554   case BO_LOr : {
555     InfoEntry LEntry = PropagationMap.find(BinOp->getLHS()),
556               REntry = PropagationMap.find(BinOp->getRHS());
557 
558     VarTestResult LTest, RTest;
559 
560     if (LEntry != PropagationMap.end() && LEntry->second.isTest()) {
561       LTest = LEntry->second.getTest();
562 
563     } else {
564       LTest.Var      = NULL;
565       LTest.TestsFor = CS_None;
566     }
567 
568     if (REntry != PropagationMap.end() && REntry->second.isTest()) {
569       RTest = REntry->second.getTest();
570 
571     } else {
572       RTest.Var      = NULL;
573       RTest.TestsFor = CS_None;
574     }
575 
576     if (!(LTest.Var == NULL && RTest.Var == NULL))
577       PropagationMap.insert(PairType(BinOp, PropagationInfo(BinOp,
578         static_cast<EffectiveOp>(BinOp->getOpcode() == BO_LOr), LTest, RTest)));
579 
580     break;
581   }
582 
583   case BO_PtrMemD:
584   case BO_PtrMemI:
585     forwardInfo(BinOp->getLHS(), BinOp);
586     break;
587 
588   default:
589     break;
590   }
591 }
592 
593 void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) {
594   if (const FunctionDecl *FunDecl =
595     dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
596 
597     // Special case for the std::move function.
598     // TODO: Make this more specific. (Deferred)
599     if (FunDecl->getNameAsString() == "move") {
600       forwardInfo(Call->getArg(0), Call);
601       return;
602     }
603 
604     unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams();
605 
606     for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) {
607       const ParmVarDecl *Param = FunDecl->getParamDecl(Index - Offset);
608       QualType ParamType = Param->getType();
609 
610       InfoEntry Entry = PropagationMap.find(Call->getArg(Index));
611 
612       if (Entry == PropagationMap.end() ||
613           !(Entry->second.isState() || Entry->second.isVar()))
614         continue;
615 
616       PropagationInfo PInfo = Entry->second;
617 
618       // Check that the parameter is in the correct state.
619 
620       if (Param->hasAttr<ParamTypestateAttr>()) {
621         ConsumedState ParamState =
622           PInfo.isState() ? PInfo.getState() :
623                             StateMap->getState(PInfo.getVar());
624 
625         ConsumedState ExpectedState =
626           mapParamTypestateAttrState(Param->getAttr<ParamTypestateAttr>());
627 
628         if (ParamState != ExpectedState)
629           Analyzer.WarningsHandler.warnParamTypestateMismatch(
630             Call->getArg(Index - Offset)->getExprLoc(),
631             stateToString(ExpectedState), stateToString(ParamState));
632       }
633 
634       if (!Entry->second.isVar())
635         continue;
636 
637       // Adjust state on the caller side.
638 
639       if (isRValueRefish(ParamType)) {
640         StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
641 
642       } else if (Param->hasAttr<ReturnTypestateAttr>()) {
643         StateMap->setState(PInfo.getVar(),
644           mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>()));
645 
646       } else if (!isValueType(ParamType) &&
647                  !ParamType->getPointeeType().isConstQualified()) {
648 
649         StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
650       }
651     }
652 
653     QualType RetType = FunDecl->getCallResultType();
654     if (RetType->isReferenceType())
655       RetType = RetType->getPointeeType();
656 
657     propagateReturnType(Call, FunDecl, RetType);
658   }
659 }
660 
661 void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) {
662   forwardInfo(Cast->getSubExpr(), Cast);
663 }
664 
665 void ConsumedStmtVisitor::VisitCXXBindTemporaryExpr(
666   const CXXBindTemporaryExpr *Temp) {
667 
668   forwardInfo(Temp->getSubExpr(), Temp);
669 }
670 
671 void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) {
672   CXXConstructorDecl *Constructor = Call->getConstructor();
673 
674   ASTContext &CurrContext = AC.getASTContext();
675   QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType();
676 
677   if (!isConsumableType(ThisType))
678     return;
679 
680   // FIXME: What should happen if someone annotates the move constructor?
681   if (Constructor->hasAttr<ReturnTypestateAttr>()) {
682     ReturnTypestateAttr *RTAttr = Constructor->getAttr<ReturnTypestateAttr>();
683     ConsumedState RetState = mapReturnTypestateAttrState(RTAttr);
684     PropagationMap.insert(PairType(Call, PropagationInfo(RetState, ThisType)));
685 
686   } else if (Constructor->isDefaultConstructor()) {
687 
688     PropagationMap.insert(PairType(Call,
689       PropagationInfo(consumed::CS_Consumed, ThisType)));
690 
691   } else if (Constructor->isMoveConstructor()) {
692 
693     InfoEntry Entry = PropagationMap.find(Call->getArg(0));
694 
695     if (Entry != PropagationMap.end()) {
696       PropagationInfo PInfo = Entry->second;
697 
698       if (PInfo.isVar()) {
699         const VarDecl* Var = PInfo.getVar();
700 
701         PropagationMap.insert(PairType(Call,
702           PropagationInfo(StateMap->getState(Var), ThisType)));
703 
704         StateMap->setState(Var, consumed::CS_Consumed);
705 
706       } else {
707         PropagationMap.insert(PairType(Call, PInfo));
708       }
709     }
710   } else if (Constructor->isCopyConstructor()) {
711     forwardInfo(Call->getArg(0), Call);
712 
713   } else {
714     ConsumedState RetState = mapConsumableAttrState(ThisType);
715     PropagationMap.insert(PairType(Call, PropagationInfo(RetState, ThisType)));
716   }
717 }
718 
719 void ConsumedStmtVisitor::VisitCXXMemberCallExpr(
720   const CXXMemberCallExpr *Call) {
721 
722   VisitCallExpr(Call);
723 
724   InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
725 
726   if (Entry != PropagationMap.end()) {
727     PropagationInfo PInfo = Entry->second;
728     const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
729 
730     checkCallability(PInfo, MethodDecl, Call->getExprLoc());
731 
732     if (PInfo.isVar()) {
733       if (isTestingFunction(MethodDecl))
734         PropagationMap.insert(PairType(Call,
735           PropagationInfo(PInfo.getVar(), testsFor(MethodDecl))));
736       else if (MethodDecl->hasAttr<SetTypestateAttr>())
737         StateMap->setState(PInfo.getVar(),
738           mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>()));
739     }
740   }
741 }
742 
743 void ConsumedStmtVisitor::VisitCXXOperatorCallExpr(
744   const CXXOperatorCallExpr *Call) {
745 
746   const FunctionDecl *FunDecl =
747     dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee());
748 
749   if (!FunDecl) return;
750 
751   if (isa<CXXMethodDecl>(FunDecl) &&
752       isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) {
753 
754     InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
755     InfoEntry REntry = PropagationMap.find(Call->getArg(1));
756 
757     PropagationInfo LPInfo, RPInfo;
758 
759     if (LEntry != PropagationMap.end() &&
760         REntry != PropagationMap.end()) {
761 
762       LPInfo = LEntry->second;
763       RPInfo = REntry->second;
764 
765       if (LPInfo.isVar() && RPInfo.isVar()) {
766         StateMap->setState(LPInfo.getVar(),
767           StateMap->getState(RPInfo.getVar()));
768 
769         StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
770 
771         PropagationMap.insert(PairType(Call, LPInfo));
772 
773       } else if (LPInfo.isVar() && !RPInfo.isVar()) {
774         StateMap->setState(LPInfo.getVar(), RPInfo.getState());
775 
776         PropagationMap.insert(PairType(Call, LPInfo));
777 
778       } else if (!LPInfo.isVar() && RPInfo.isVar()) {
779         PropagationMap.insert(PairType(Call,
780           PropagationInfo(StateMap->getState(RPInfo.getVar()),
781                           LPInfo.getTempType())));
782 
783         StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
784 
785       } else {
786         PropagationMap.insert(PairType(Call, RPInfo));
787       }
788 
789     } else if (LEntry != PropagationMap.end() &&
790                REntry == PropagationMap.end()) {
791 
792       LPInfo = LEntry->second;
793 
794       if (LPInfo.isVar()) {
795         StateMap->setState(LPInfo.getVar(), consumed::CS_Unknown);
796 
797         PropagationMap.insert(PairType(Call, LPInfo));
798 
799       } else if (LPInfo.isState()) {
800         PropagationMap.insert(PairType(Call,
801           PropagationInfo(consumed::CS_Unknown, LPInfo.getTempType())));
802       }
803 
804     } else if (LEntry == PropagationMap.end() &&
805                REntry != PropagationMap.end()) {
806 
807       if (REntry->second.isVar())
808         StateMap->setState(REntry->second.getVar(), consumed::CS_Consumed);
809     }
810 
811   } else {
812 
813     VisitCallExpr(Call);
814 
815     InfoEntry Entry = PropagationMap.find(Call->getArg(0));
816 
817     if (Entry != PropagationMap.end()) {
818       PropagationInfo PInfo = Entry->second;
819 
820       checkCallability(PInfo, FunDecl, Call->getExprLoc());
821 
822       if (PInfo.isVar()) {
823         if (isTestingFunction(FunDecl))
824           PropagationMap.insert(PairType(Call,
825             PropagationInfo(PInfo.getVar(), testsFor(FunDecl))));
826         else if (FunDecl->hasAttr<SetTypestateAttr>())
827           StateMap->setState(PInfo.getVar(),
828             mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>()));
829       }
830     }
831   }
832 }
833 
834 void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) {
835   if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
836     if (StateMap->getState(Var) != consumed::CS_None)
837       PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
838 }
839 
840 void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) {
841   for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(),
842        DE = DeclS->decl_end(); DI != DE; ++DI) {
843 
844     if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI));
845   }
846 
847   if (DeclS->isSingleDecl())
848     if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl()))
849       PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
850 }
851 
852 void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
853   const MaterializeTemporaryExpr *Temp) {
854 
855   forwardInfo(Temp->GetTemporaryExpr(), Temp);
856 }
857 
858 void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
859   forwardInfo(MExpr->getBase(), MExpr);
860 }
861 
862 
863 void ConsumedStmtVisitor::VisitParmVarDecl(const ParmVarDecl *Param) {
864   QualType ParamType = Param->getType();
865   ConsumedState ParamState = consumed::CS_None;
866 
867   if (Param->hasAttr<ParamTypestateAttr>()) {
868     const ParamTypestateAttr *PTAttr = Param->getAttr<ParamTypestateAttr>();
869     ParamState = mapParamTypestateAttrState(PTAttr);
870 
871   } else if (isConsumableType(ParamType)) {
872     ParamState = mapConsumableAttrState(ParamType);
873 
874   } else if (isRValueRefish(ParamType) &&
875              isConsumableType(ParamType->getPointeeType())) {
876 
877     ParamState = mapConsumableAttrState(ParamType->getPointeeType());
878 
879   } else if (ParamType->isReferenceType() &&
880              isConsumableType(ParamType->getPointeeType())) {
881     ParamState = consumed::CS_Unknown;
882   }
883 
884   if (ParamState != CS_None)
885     StateMap->setState(Param, ParamState);
886 }
887 
888 void ConsumedStmtVisitor::VisitReturnStmt(const ReturnStmt *Ret) {
889   ConsumedState ExpectedState = Analyzer.getExpectedReturnState();
890 
891   if (ExpectedState != CS_None) {
892     InfoEntry Entry = PropagationMap.find(Ret->getRetValue());
893 
894     if (Entry != PropagationMap.end()) {
895       assert(Entry->second.isState() || Entry->second.isVar());
896 
897       ConsumedState RetState = Entry->second.isState() ?
898         Entry->second.getState() : StateMap->getState(Entry->second.getVar());
899 
900       if (RetState != ExpectedState)
901         Analyzer.WarningsHandler.warnReturnTypestateMismatch(
902           Ret->getReturnLoc(), stateToString(ExpectedState),
903           stateToString(RetState));
904     }
905   }
906 
907   StateMap->checkParamsForReturnTypestate(Ret->getLocStart(),
908                                           Analyzer.WarningsHandler);
909 }
910 
911 void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) {
912   InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens());
913   if (Entry == PropagationMap.end()) return;
914 
915   switch (UOp->getOpcode()) {
916   case UO_AddrOf:
917     PropagationMap.insert(PairType(UOp, Entry->second));
918     break;
919 
920   case UO_LNot:
921     if (Entry->second.isTest() || Entry->second.isBinTest())
922       PropagationMap.insert(PairType(UOp, Entry->second.invertTest()));
923     break;
924 
925   default:
926     break;
927   }
928 }
929 
930 // TODO: See if I need to check for reference types here.
931 void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
932   if (isConsumableType(Var->getType())) {
933     if (Var->hasInit()) {
934       MapType::iterator VIT = PropagationMap.find(Var->getInit());
935       if (VIT != PropagationMap.end()) {
936         PropagationInfo PInfo = VIT->second;
937         ConsumedState St = getPInfoState(PInfo);
938         if (St != consumed::CS_None) {
939           StateMap->setState(Var, St);
940           return;
941         }
942       }
943     }
944     // Otherwise
945     StateMap->setState(Var, consumed::CS_Unknown);
946   }
947 }
948 }} // end clang::consumed::ConsumedStmtVisitor
949 
950 namespace clang {
951 namespace consumed {
952 
953 void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test,
954                         ConsumedStateMap *ThenStates,
955                         ConsumedStateMap *ElseStates) {
956 
957   ConsumedState VarState = ThenStates->getState(Test.Var);
958 
959   if (VarState == CS_Unknown) {
960     ThenStates->setState(Test.Var, Test.TestsFor);
961     ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
962 
963   } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) {
964     ThenStates->markUnreachable();
965 
966   } else if (VarState == Test.TestsFor) {
967     ElseStates->markUnreachable();
968   }
969 }
970 
971 void splitVarStateForIfBinOp(const PropagationInfo &PInfo,
972   ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) {
973 
974   const VarTestResult &LTest = PInfo.getLTest(),
975                       &RTest = PInfo.getRTest();
976 
977   ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None,
978                 RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None;
979 
980   if (LTest.Var) {
981     if (PInfo.testEffectiveOp() == EO_And) {
982       if (LState == CS_Unknown) {
983         ThenStates->setState(LTest.Var, LTest.TestsFor);
984 
985       } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) {
986         ThenStates->markUnreachable();
987 
988       } else if (LState == LTest.TestsFor && isKnownState(RState)) {
989         if (RState == RTest.TestsFor)
990           ElseStates->markUnreachable();
991         else
992           ThenStates->markUnreachable();
993       }
994 
995     } else {
996       if (LState == CS_Unknown) {
997         ElseStates->setState(LTest.Var,
998                              invertConsumedUnconsumed(LTest.TestsFor));
999 
1000       } else if (LState == LTest.TestsFor) {
1001         ElseStates->markUnreachable();
1002 
1003       } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) &&
1004                  isKnownState(RState)) {
1005 
1006         if (RState == RTest.TestsFor)
1007           ElseStates->markUnreachable();
1008         else
1009           ThenStates->markUnreachable();
1010       }
1011     }
1012   }
1013 
1014   if (RTest.Var) {
1015     if (PInfo.testEffectiveOp() == EO_And) {
1016       if (RState == CS_Unknown)
1017         ThenStates->setState(RTest.Var, RTest.TestsFor);
1018       else if (RState == invertConsumedUnconsumed(RTest.TestsFor))
1019         ThenStates->markUnreachable();
1020 
1021     } else {
1022       if (RState == CS_Unknown)
1023         ElseStates->setState(RTest.Var,
1024                              invertConsumedUnconsumed(RTest.TestsFor));
1025       else if (RState == RTest.TestsFor)
1026         ElseStates->markUnreachable();
1027     }
1028   }
1029 }
1030 
1031 bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock,
1032                                             const CFGBlock *TargetBlock) {
1033 
1034   assert(CurrBlock && "Block pointer must not be NULL");
1035   assert(TargetBlock && "TargetBlock pointer must not be NULL");
1036 
1037   unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()];
1038   for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(),
1039        PE = TargetBlock->pred_end(); PI != PE; ++PI) {
1040     if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] )
1041       return false;
1042   }
1043   return true;
1044 }
1045 
1046 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1047                                 ConsumedStateMap *StateMap,
1048                                 bool &AlreadyOwned) {
1049 
1050   assert(Block && "Block pointer must not be NULL");
1051 
1052   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1053 
1054   if (Entry) {
1055     Entry->intersect(StateMap);
1056 
1057   } else if (AlreadyOwned) {
1058     StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap);
1059 
1060   } else {
1061     StateMapsArray[Block->getBlockID()] = StateMap;
1062     AlreadyOwned = true;
1063   }
1064 }
1065 
1066 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1067                                 ConsumedStateMap *StateMap) {
1068 
1069   assert(Block != NULL && "Block pointer must not be NULL");
1070 
1071   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1072 
1073   if (Entry) {
1074     Entry->intersect(StateMap);
1075     delete StateMap;
1076 
1077   } else {
1078     StateMapsArray[Block->getBlockID()] = StateMap;
1079   }
1080 }
1081 
1082 ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) {
1083   assert(Block && "Block pointer must not be NULL");
1084   assert(StateMapsArray[Block->getBlockID()] && "Block has no block info");
1085 
1086   return StateMapsArray[Block->getBlockID()];
1087 }
1088 
1089 void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) {
1090   unsigned int BlockID = Block->getBlockID();
1091   delete StateMapsArray[BlockID];
1092   StateMapsArray[BlockID] = NULL;
1093 }
1094 
1095 ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
1096   assert(Block && "Block pointer must not be NULL");
1097 
1098   ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()];
1099   if (isBackEdgeTarget(Block)) {
1100     return new ConsumedStateMap(*StateMap);
1101   } else {
1102     StateMapsArray[Block->getBlockID()] = NULL;
1103     return StateMap;
1104   }
1105 }
1106 
1107 bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) {
1108   assert(From && "From block must not be NULL");
1109   assert(To   && "From block must not be NULL");
1110 
1111   return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()];
1112 }
1113 
1114 bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) {
1115   assert(Block != NULL && "Block pointer must not be NULL");
1116 
1117   // Anything with less than two predecessors can't be the target of a back
1118   // edge.
1119   if (Block->pred_size() < 2)
1120     return false;
1121 
1122   unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()];
1123   for (CFGBlock::const_pred_iterator PI = Block->pred_begin(),
1124        PE = Block->pred_end(); PI != PE; ++PI) {
1125     if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()])
1126       return true;
1127   }
1128   return false;
1129 }
1130 
1131 void ConsumedStateMap::checkParamsForReturnTypestate(SourceLocation BlameLoc,
1132   ConsumedWarningsHandlerBase &WarningsHandler) const {
1133 
1134   ConsumedState ExpectedState;
1135 
1136   for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
1137        ++DMI) {
1138 
1139     if (isa<ParmVarDecl>(DMI->first)) {
1140       const ParmVarDecl *Param = cast<ParmVarDecl>(DMI->first);
1141 
1142       if (!Param->hasAttr<ReturnTypestateAttr>()) continue;
1143 
1144       ExpectedState =
1145         mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>());
1146 
1147       if (DMI->second != ExpectedState) {
1148         WarningsHandler.warnParamReturnTypestateMismatch(BlameLoc,
1149           Param->getNameAsString(), stateToString(ExpectedState),
1150           stateToString(DMI->second));
1151       }
1152     }
1153   }
1154 }
1155 
1156 ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const {
1157   MapType::const_iterator Entry = Map.find(Var);
1158 
1159   if (Entry != Map.end()) {
1160     return Entry->second;
1161 
1162   } else {
1163     return CS_None;
1164   }
1165 }
1166 
1167 void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
1168   ConsumedState LocalState;
1169 
1170   if (this->From && this->From == Other->From && !Other->Reachable) {
1171     this->markUnreachable();
1172     return;
1173   }
1174 
1175   for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
1176        DMI != DME; ++DMI) {
1177 
1178     LocalState = this->getState(DMI->first);
1179 
1180     if (LocalState == CS_None)
1181       continue;
1182 
1183     if (LocalState != DMI->second)
1184        Map[DMI->first] = CS_Unknown;
1185   }
1186 }
1187 
1188 void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead,
1189   const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates,
1190   ConsumedWarningsHandlerBase &WarningsHandler) {
1191 
1192   ConsumedState LocalState;
1193   SourceLocation BlameLoc = getLastStmtLoc(LoopBack);
1194 
1195   for (MapType::const_iterator DMI = LoopBackStates->Map.begin(),
1196        DME = LoopBackStates->Map.end(); DMI != DME; ++DMI) {
1197 
1198     LocalState = this->getState(DMI->first);
1199 
1200     if (LocalState == CS_None)
1201       continue;
1202 
1203     if (LocalState != DMI->second) {
1204       Map[DMI->first] = CS_Unknown;
1205       WarningsHandler.warnLoopStateMismatch(
1206         BlameLoc, DMI->first->getNameAsString());
1207     }
1208   }
1209 }
1210 
1211 void ConsumedStateMap::markUnreachable() {
1212   this->Reachable = false;
1213   Map.clear();
1214 }
1215 
1216 void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
1217   Map[Var] = State;
1218 }
1219 
1220 void ConsumedStateMap::remove(const VarDecl *Var) {
1221   Map.erase(Var);
1222 }
1223 
1224 bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const {
1225   for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
1226        DMI != DME; ++DMI) {
1227 
1228     if (this->getState(DMI->first) != DMI->second)
1229       return true;
1230   }
1231 
1232   return false;
1233 }
1234 
1235 void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC,
1236                                                     const FunctionDecl *D) {
1237   QualType ReturnType;
1238   if (const CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
1239     ASTContext &CurrContext = AC.getASTContext();
1240     ReturnType = Constructor->getThisType(CurrContext)->getPointeeType();
1241   } else
1242     ReturnType = D->getCallResultType();
1243 
1244   if (D->hasAttr<ReturnTypestateAttr>()) {
1245     const ReturnTypestateAttr *RTSAttr = D->getAttr<ReturnTypestateAttr>();
1246 
1247     const CXXRecordDecl *RD = ReturnType->getAsCXXRecordDecl();
1248     if (!RD || !RD->hasAttr<ConsumableAttr>()) {
1249       // FIXME: This should be removed when template instantiation propagates
1250       //        attributes at template specialization definition, not
1251       //        declaration. When it is removed the test needs to be enabled
1252       //        in SemaDeclAttr.cpp.
1253       WarningsHandler.warnReturnTypestateForUnconsumableType(
1254           RTSAttr->getLocation(), ReturnType.getAsString());
1255       ExpectedReturnState = CS_None;
1256     } else
1257       ExpectedReturnState = mapReturnTypestateAttrState(RTSAttr);
1258   } else if (isConsumableType(ReturnType))
1259     ExpectedReturnState = mapConsumableAttrState(ReturnType);
1260   else
1261     ExpectedReturnState = CS_None;
1262 }
1263 
1264 bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
1265                                   const ConsumedStmtVisitor &Visitor) {
1266 
1267   OwningPtr<ConsumedStateMap> FalseStates(new ConsumedStateMap(*CurrStates));
1268   PropagationInfo PInfo;
1269 
1270   if (const IfStmt *IfNode =
1271     dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
1272 
1273     const Stmt *Cond = IfNode->getCond();
1274 
1275     PInfo = Visitor.getInfo(Cond);
1276     if (!PInfo.isValid() && isa<BinaryOperator>(Cond))
1277       PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS());
1278 
1279     if (PInfo.isTest()) {
1280       CurrStates->setSource(Cond);
1281       FalseStates->setSource(Cond);
1282       splitVarStateForIf(IfNode, PInfo.getTest(), CurrStates,
1283                          FalseStates.get());
1284 
1285     } else if (PInfo.isBinTest()) {
1286       CurrStates->setSource(PInfo.testSourceNode());
1287       FalseStates->setSource(PInfo.testSourceNode());
1288       splitVarStateForIfBinOp(PInfo, CurrStates, FalseStates.get());
1289 
1290     } else {
1291       return false;
1292     }
1293 
1294   } else if (const BinaryOperator *BinOp =
1295     dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) {
1296 
1297     PInfo = Visitor.getInfo(BinOp->getLHS());
1298     if (!PInfo.isTest()) {
1299       if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) {
1300         PInfo = Visitor.getInfo(BinOp->getRHS());
1301 
1302         if (!PInfo.isTest())
1303           return false;
1304 
1305       } else {
1306         return false;
1307       }
1308     }
1309 
1310     CurrStates->setSource(BinOp);
1311     FalseStates->setSource(BinOp);
1312 
1313     const VarTestResult &Test = PInfo.getTest();
1314     ConsumedState VarState = CurrStates->getState(Test.Var);
1315 
1316     if (BinOp->getOpcode() == BO_LAnd) {
1317       if (VarState == CS_Unknown)
1318         CurrStates->setState(Test.Var, Test.TestsFor);
1319       else if (VarState == invertConsumedUnconsumed(Test.TestsFor))
1320         CurrStates->markUnreachable();
1321 
1322     } else if (BinOp->getOpcode() == BO_LOr) {
1323       if (VarState == CS_Unknown)
1324         FalseStates->setState(Test.Var,
1325                               invertConsumedUnconsumed(Test.TestsFor));
1326       else if (VarState == Test.TestsFor)
1327         FalseStates->markUnreachable();
1328     }
1329 
1330   } else {
1331     return false;
1332   }
1333 
1334   CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
1335 
1336   if (*SI)
1337     BlockInfo.addInfo(*SI, CurrStates);
1338   else
1339     delete CurrStates;
1340 
1341   if (*++SI)
1342     BlockInfo.addInfo(*SI, FalseStates.take());
1343 
1344   CurrStates = NULL;
1345   return true;
1346 }
1347 
1348 void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
1349   const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
1350   if (!D)
1351     return;
1352 
1353   CFG *CFGraph = AC.getCFG();
1354   if (!CFGraph)
1355     return;
1356 
1357   determineExpectedReturnState(AC, D);
1358 
1359   PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
1360   // AC.getCFG()->viewCFG(LangOptions());
1361 
1362   BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
1363 
1364   CurrStates = new ConsumedStateMap();
1365   ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
1366 
1367   // Add all trackable parameters to the state map.
1368   for (FunctionDecl::param_const_iterator PI = D->param_begin(),
1369        PE = D->param_end(); PI != PE; ++PI) {
1370     Visitor.VisitParmVarDecl(*PI);
1371   }
1372 
1373   // Visit all of the function's basic blocks.
1374   for (PostOrderCFGView::iterator I = SortedGraph->begin(),
1375        E = SortedGraph->end(); I != E; ++I) {
1376 
1377     const CFGBlock *CurrBlock = *I;
1378 
1379     if (CurrStates == NULL)
1380       CurrStates = BlockInfo.getInfo(CurrBlock);
1381 
1382     if (!CurrStates) {
1383       continue;
1384 
1385     } else if (!CurrStates->isReachable()) {
1386       delete CurrStates;
1387       CurrStates = NULL;
1388       continue;
1389     }
1390 
1391     Visitor.reset(CurrStates);
1392 
1393     // Visit all of the basic block's statements.
1394     for (CFGBlock::const_iterator BI = CurrBlock->begin(),
1395          BE = CurrBlock->end(); BI != BE; ++BI) {
1396 
1397       switch (BI->getKind()) {
1398       case CFGElement::Statement:
1399         Visitor.Visit(BI->castAs<CFGStmt>().getStmt());
1400         break;
1401 
1402       case CFGElement::TemporaryDtor: {
1403         const CFGTemporaryDtor DTor = BI->castAs<CFGTemporaryDtor>();
1404         const CXXBindTemporaryExpr *BTE = DTor.getBindTemporaryExpr();
1405         PropagationInfo PInfo = Visitor.getInfo(BTE);
1406 
1407         if (PInfo.isValid())
1408           Visitor.checkCallability(PInfo,
1409                                    DTor.getDestructorDecl(AC.getASTContext()),
1410                                    BTE->getExprLoc());
1411         break;
1412       }
1413 
1414       case CFGElement::AutomaticObjectDtor: {
1415         const CFGAutomaticObjDtor DTor = BI->castAs<CFGAutomaticObjDtor>();
1416 
1417         const VarDecl *Var = DTor.getVarDecl();
1418         ConsumedState VarState = CurrStates->getState(Var);
1419 
1420         if (VarState != CS_None) {
1421           PropagationInfo PInfo(Var);
1422 
1423           Visitor.checkCallability(PInfo,
1424                                    DTor.getDestructorDecl(AC.getASTContext()),
1425                                    getLastStmtLoc(CurrBlock));
1426 
1427           CurrStates->remove(Var);
1428         }
1429         break;
1430       }
1431 
1432       default:
1433         break;
1434       }
1435     }
1436 
1437     // TODO: Handle other forms of branching with precision, including while-
1438     //       and for-loops. (Deferred)
1439     if (!splitState(CurrBlock, Visitor)) {
1440       CurrStates->setSource(NULL);
1441 
1442       if (CurrBlock->succ_size() > 1 ||
1443           (CurrBlock->succ_size() == 1 &&
1444            (*CurrBlock->succ_begin())->pred_size() > 1)) {
1445 
1446         bool OwnershipTaken = false;
1447 
1448         for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
1449              SE = CurrBlock->succ_end(); SI != SE; ++SI) {
1450 
1451           if (*SI == NULL) continue;
1452 
1453           if (BlockInfo.isBackEdge(CurrBlock, *SI)) {
1454             BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock,
1455                                                            CurrStates,
1456                                                            WarningsHandler);
1457 
1458             if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock))
1459               BlockInfo.discardInfo(*SI);
1460           } else {
1461             BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
1462           }
1463         }
1464 
1465         if (!OwnershipTaken)
1466           delete CurrStates;
1467 
1468         CurrStates = NULL;
1469       }
1470     }
1471 
1472     if (CurrBlock == &AC.getCFG()->getExit() &&
1473         D->getCallResultType()->isVoidType())
1474       CurrStates->checkParamsForReturnTypestate(D->getLocation(),
1475                                                 WarningsHandler);
1476   } // End of block iterator.
1477 
1478   // Delete the last existing state map.
1479   delete CurrStates;
1480 
1481   WarningsHandler.emitDiagnostics();
1482 }
1483 }} // end namespace clang::consumed
1484