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