xref: /llvm-project/clang/lib/Analysis/Consumed.cpp (revision 8121866bdbffff68763bcff3adb79e2425dc9ae2) 
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       InfoEntry Entry = PropagationMap.find(Call->getArg(0));
596 
597       if (Entry != PropagationMap.end()) {
598         PropagationMap.insert(PairType(Call, Entry->second));
599       }
600 
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     PropagationInfo PInfo =
694       PropagationMap.find(Call->getArg(0))->second;
695 
696     if (PInfo.isVar()) {
697       const VarDecl* Var = PInfo.getVar();
698 
699       PropagationMap.insert(PairType(Call,
700         PropagationInfo(StateMap->getState(Var), ThisType)));
701 
702       StateMap->setState(Var, consumed::CS_Consumed);
703 
704     } else {
705       PropagationMap.insert(PairType(Call, PInfo));
706     }
707 
708   } else if (Constructor->isCopyConstructor()) {
709     MapType::iterator Entry = PropagationMap.find(Call->getArg(0));
710 
711     if (Entry != PropagationMap.end())
712       PropagationMap.insert(PairType(Call, Entry->second));
713 
714   } else {
715     ConsumedState RetState = mapConsumableAttrState(ThisType);
716     PropagationMap.insert(PairType(Call, PropagationInfo(RetState, ThisType)));
717   }
718 }
719 
720 
721 void ConsumedStmtVisitor::VisitCXXMemberCallExpr(
722   const CXXMemberCallExpr *Call) {
723 
724   VisitCallExpr(Call);
725 
726   InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
727 
728   if (Entry != PropagationMap.end()) {
729     PropagationInfo PInfo = Entry->second;
730     const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
731 
732     checkCallability(PInfo, MethodDecl, Call->getExprLoc());
733 
734     if (PInfo.isVar()) {
735       if (isTestingFunction(MethodDecl))
736         PropagationMap.insert(PairType(Call,
737           PropagationInfo(PInfo.getVar(), testsFor(MethodDecl))));
738       else if (MethodDecl->hasAttr<SetTypestateAttr>())
739         StateMap->setState(PInfo.getVar(),
740           mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>()));
741     }
742   }
743 }
744 
745 void ConsumedStmtVisitor::VisitCXXOperatorCallExpr(
746   const CXXOperatorCallExpr *Call) {
747 
748   const FunctionDecl *FunDecl =
749     dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee());
750 
751   if (!FunDecl) return;
752 
753   if (isa<CXXMethodDecl>(FunDecl) &&
754       isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) {
755 
756     InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
757     InfoEntry REntry = PropagationMap.find(Call->getArg(1));
758 
759     PropagationInfo LPInfo, RPInfo;
760 
761     if (LEntry != PropagationMap.end() &&
762         REntry != PropagationMap.end()) {
763 
764       LPInfo = LEntry->second;
765       RPInfo = REntry->second;
766 
767       if (LPInfo.isVar() && RPInfo.isVar()) {
768         StateMap->setState(LPInfo.getVar(),
769           StateMap->getState(RPInfo.getVar()));
770 
771         StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
772 
773         PropagationMap.insert(PairType(Call, LPInfo));
774 
775       } else if (LPInfo.isVar() && !RPInfo.isVar()) {
776         StateMap->setState(LPInfo.getVar(), RPInfo.getState());
777 
778         PropagationMap.insert(PairType(Call, LPInfo));
779 
780       } else if (!LPInfo.isVar() && RPInfo.isVar()) {
781         PropagationMap.insert(PairType(Call,
782           PropagationInfo(StateMap->getState(RPInfo.getVar()),
783                           LPInfo.getTempType())));
784 
785         StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
786 
787       } else {
788         PropagationMap.insert(PairType(Call, RPInfo));
789       }
790 
791     } else if (LEntry != PropagationMap.end() &&
792                REntry == PropagationMap.end()) {
793 
794       LPInfo = LEntry->second;
795 
796       if (LPInfo.isVar()) {
797         StateMap->setState(LPInfo.getVar(), consumed::CS_Unknown);
798 
799         PropagationMap.insert(PairType(Call, LPInfo));
800 
801       } else if (LPInfo.isState()) {
802         PropagationMap.insert(PairType(Call,
803           PropagationInfo(consumed::CS_Unknown, LPInfo.getTempType())));
804       }
805 
806     } else if (LEntry == PropagationMap.end() &&
807                REntry != PropagationMap.end()) {
808 
809       if (REntry->second.isVar())
810         StateMap->setState(REntry->second.getVar(), consumed::CS_Consumed);
811     }
812 
813   } else {
814 
815     VisitCallExpr(Call);
816 
817     InfoEntry Entry = PropagationMap.find(Call->getArg(0));
818 
819     if (Entry != PropagationMap.end()) {
820       PropagationInfo PInfo = Entry->second;
821 
822       checkCallability(PInfo, FunDecl, Call->getExprLoc());
823 
824       if (PInfo.isVar()) {
825         if (isTestingFunction(FunDecl))
826           PropagationMap.insert(PairType(Call,
827             PropagationInfo(PInfo.getVar(), testsFor(FunDecl))));
828         else if (FunDecl->hasAttr<SetTypestateAttr>())
829           StateMap->setState(PInfo.getVar(),
830             mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>()));
831       }
832     }
833   }
834 }
835 
836 void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) {
837   if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
838     if (StateMap->getState(Var) != consumed::CS_None)
839       PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
840 }
841 
842 void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) {
843   for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(),
844        DE = DeclS->decl_end(); DI != DE; ++DI) {
845 
846     if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI));
847   }
848 
849   if (DeclS->isSingleDecl())
850     if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl()))
851       PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
852 }
853 
854 void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
855   const MaterializeTemporaryExpr *Temp) {
856 
857   InfoEntry Entry = PropagationMap.find(Temp->GetTemporaryExpr());
858 
859   if (Entry != PropagationMap.end())
860     PropagationMap.insert(PairType(Temp, Entry->second));
861 }
862 
863 void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
864   forwardInfo(MExpr->getBase(), MExpr);
865 }
866 
867 
868 void ConsumedStmtVisitor::VisitParmVarDecl(const ParmVarDecl *Param) {
869   QualType ParamType = Param->getType();
870   ConsumedState ParamState = consumed::CS_None;
871 
872   if (Param->hasAttr<ParamTypestateAttr>()) {
873     const ParamTypestateAttr *PTAttr = Param->getAttr<ParamTypestateAttr>();
874     ParamState = mapParamTypestateAttrState(PTAttr);
875 
876   } else if (isValueType(ParamType) && isConsumableType(ParamType)) {
877     ParamState = mapConsumableAttrState(ParamType);
878 
879   } else if (isRValueRefish(ParamType) &&
880              isConsumableType(ParamType->getPointeeType())) {
881 
882     ParamState = mapConsumableAttrState(ParamType->getPointeeType());
883 
884   } else if (ParamType->isReferenceType() &&
885              isConsumableType(ParamType->getPointeeType())) {
886     ParamState = consumed::CS_Unknown;
887   }
888 
889   if (ParamState != CS_None)
890     StateMap->setState(Param, ParamState);
891 }
892 
893 void ConsumedStmtVisitor::VisitReturnStmt(const ReturnStmt *Ret) {
894   ConsumedState ExpectedState = Analyzer.getExpectedReturnState();
895 
896   if (ExpectedState != CS_None) {
897     InfoEntry Entry = PropagationMap.find(Ret->getRetValue());
898 
899     if (Entry != PropagationMap.end()) {
900       assert(Entry->second.isState() || Entry->second.isVar());
901 
902       ConsumedState RetState = Entry->second.isState() ?
903         Entry->second.getState() : StateMap->getState(Entry->second.getVar());
904 
905       if (RetState != ExpectedState)
906         Analyzer.WarningsHandler.warnReturnTypestateMismatch(
907           Ret->getReturnLoc(), stateToString(ExpectedState),
908           stateToString(RetState));
909     }
910   }
911 
912   StateMap->checkParamsForReturnTypestate(Ret->getLocStart(),
913                                           Analyzer.WarningsHandler);
914 }
915 
916 void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) {
917   InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens());
918   if (Entry == PropagationMap.end()) return;
919 
920   switch (UOp->getOpcode()) {
921   case UO_AddrOf:
922     PropagationMap.insert(PairType(UOp, Entry->second));
923     break;
924 
925   case UO_LNot:
926     if (Entry->second.isTest() || Entry->second.isBinTest())
927       PropagationMap.insert(PairType(UOp, Entry->second.invertTest()));
928     break;
929 
930   default:
931     break;
932   }
933 }
934 
935 // TODO: See if I need to check for reference types here.
936 void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
937   if (isConsumableType(Var->getType())) {
938     if (Var->hasInit()) {
939       MapType::iterator VIT = PropagationMap.find(Var->getInit());
940       if (VIT != PropagationMap.end()) {
941         PropagationInfo PInfo = VIT->second;
942         ConsumedState St = getPInfoState(PInfo);
943         if (St != consumed::CS_None) {
944           StateMap->setState(Var, St);
945           return;
946         }
947       }
948     }
949     // Otherwise
950     StateMap->setState(Var, consumed::CS_Unknown);
951   }
952 }
953 }} // end clang::consumed::ConsumedStmtVisitor
954 
955 namespace clang {
956 namespace consumed {
957 
958 void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test,
959                         ConsumedStateMap *ThenStates,
960                         ConsumedStateMap *ElseStates) {
961 
962   ConsumedState VarState = ThenStates->getState(Test.Var);
963 
964   if (VarState == CS_Unknown) {
965     ThenStates->setState(Test.Var, Test.TestsFor);
966     ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
967 
968   } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) {
969     ThenStates->markUnreachable();
970 
971   } else if (VarState == Test.TestsFor) {
972     ElseStates->markUnreachable();
973   }
974 }
975 
976 void splitVarStateForIfBinOp(const PropagationInfo &PInfo,
977   ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) {
978 
979   const VarTestResult &LTest = PInfo.getLTest(),
980                       &RTest = PInfo.getRTest();
981 
982   ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None,
983                 RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None;
984 
985   if (LTest.Var) {
986     if (PInfo.testEffectiveOp() == EO_And) {
987       if (LState == CS_Unknown) {
988         ThenStates->setState(LTest.Var, LTest.TestsFor);
989 
990       } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) {
991         ThenStates->markUnreachable();
992 
993       } else if (LState == LTest.TestsFor && isKnownState(RState)) {
994         if (RState == RTest.TestsFor)
995           ElseStates->markUnreachable();
996         else
997           ThenStates->markUnreachable();
998       }
999 
1000     } else {
1001       if (LState == CS_Unknown) {
1002         ElseStates->setState(LTest.Var,
1003                              invertConsumedUnconsumed(LTest.TestsFor));
1004 
1005       } else if (LState == LTest.TestsFor) {
1006         ElseStates->markUnreachable();
1007 
1008       } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) &&
1009                  isKnownState(RState)) {
1010 
1011         if (RState == RTest.TestsFor)
1012           ElseStates->markUnreachable();
1013         else
1014           ThenStates->markUnreachable();
1015       }
1016     }
1017   }
1018 
1019   if (RTest.Var) {
1020     if (PInfo.testEffectiveOp() == EO_And) {
1021       if (RState == CS_Unknown)
1022         ThenStates->setState(RTest.Var, RTest.TestsFor);
1023       else if (RState == invertConsumedUnconsumed(RTest.TestsFor))
1024         ThenStates->markUnreachable();
1025 
1026     } else {
1027       if (RState == CS_Unknown)
1028         ElseStates->setState(RTest.Var,
1029                              invertConsumedUnconsumed(RTest.TestsFor));
1030       else if (RState == RTest.TestsFor)
1031         ElseStates->markUnreachable();
1032     }
1033   }
1034 }
1035 
1036 bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock,
1037                                             const CFGBlock *TargetBlock) {
1038 
1039   assert(CurrBlock && "Block pointer must not be NULL");
1040   assert(TargetBlock && "TargetBlock pointer must not be NULL");
1041 
1042   unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()];
1043   for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(),
1044        PE = TargetBlock->pred_end(); PI != PE; ++PI) {
1045     if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] )
1046       return false;
1047   }
1048   return true;
1049 }
1050 
1051 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1052                                 ConsumedStateMap *StateMap,
1053                                 bool &AlreadyOwned) {
1054 
1055   assert(Block && "Block pointer must not be NULL");
1056 
1057   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1058 
1059   if (Entry) {
1060     Entry->intersect(StateMap);
1061 
1062   } else if (AlreadyOwned) {
1063     StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap);
1064 
1065   } else {
1066     StateMapsArray[Block->getBlockID()] = StateMap;
1067     AlreadyOwned = true;
1068   }
1069 }
1070 
1071 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1072                                 ConsumedStateMap *StateMap) {
1073 
1074   assert(Block != NULL && "Block pointer must not be NULL");
1075 
1076   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1077 
1078   if (Entry) {
1079     Entry->intersect(StateMap);
1080     delete StateMap;
1081 
1082   } else {
1083     StateMapsArray[Block->getBlockID()] = StateMap;
1084   }
1085 }
1086 
1087 ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) {
1088   assert(Block && "Block pointer must not be NULL");
1089   assert(StateMapsArray[Block->getBlockID()] && "Block has no block info");
1090 
1091   return StateMapsArray[Block->getBlockID()];
1092 }
1093 
1094 void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) {
1095   unsigned int BlockID = Block->getBlockID();
1096   delete StateMapsArray[BlockID];
1097   StateMapsArray[BlockID] = NULL;
1098 }
1099 
1100 ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
1101   assert(Block && "Block pointer must not be NULL");
1102 
1103   ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()];
1104   if (isBackEdgeTarget(Block)) {
1105     return new ConsumedStateMap(*StateMap);
1106   } else {
1107     StateMapsArray[Block->getBlockID()] = NULL;
1108     return StateMap;
1109   }
1110 }
1111 
1112 bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) {
1113   assert(From && "From block must not be NULL");
1114   assert(To   && "From block must not be NULL");
1115 
1116   return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()];
1117 }
1118 
1119 bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) {
1120   assert(Block != NULL && "Block pointer must not be NULL");
1121 
1122   // Anything with less than two predecessors can't be the target of a back
1123   // edge.
1124   if (Block->pred_size() < 2)
1125     return false;
1126 
1127   unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()];
1128   for (CFGBlock::const_pred_iterator PI = Block->pred_begin(),
1129        PE = Block->pred_end(); PI != PE; ++PI) {
1130     if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()])
1131       return true;
1132   }
1133   return false;
1134 }
1135 
1136 void ConsumedStateMap::checkParamsForReturnTypestate(SourceLocation BlameLoc,
1137   ConsumedWarningsHandlerBase &WarningsHandler) const {
1138 
1139   ConsumedState ExpectedState;
1140 
1141   for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
1142        ++DMI) {
1143 
1144     if (isa<ParmVarDecl>(DMI->first)) {
1145       const ParmVarDecl *Param = cast<ParmVarDecl>(DMI->first);
1146 
1147       if (!Param->hasAttr<ReturnTypestateAttr>()) continue;
1148 
1149       ExpectedState =
1150         mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>());
1151 
1152       if (DMI->second != ExpectedState) {
1153         WarningsHandler.warnParamReturnTypestateMismatch(BlameLoc,
1154           Param->getNameAsString(), stateToString(ExpectedState),
1155           stateToString(DMI->second));
1156       }
1157     }
1158   }
1159 }
1160 
1161 ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const {
1162   MapType::const_iterator Entry = Map.find(Var);
1163 
1164   if (Entry != Map.end()) {
1165     return Entry->second;
1166 
1167   } else {
1168     return CS_None;
1169   }
1170 }
1171 
1172 void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
1173   ConsumedState LocalState;
1174 
1175   if (this->From && this->From == Other->From && !Other->Reachable) {
1176     this->markUnreachable();
1177     return;
1178   }
1179 
1180   for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
1181        DMI != DME; ++DMI) {
1182 
1183     LocalState = this->getState(DMI->first);
1184 
1185     if (LocalState == CS_None)
1186       continue;
1187 
1188     if (LocalState != DMI->second)
1189        Map[DMI->first] = CS_Unknown;
1190   }
1191 }
1192 
1193 void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead,
1194   const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates,
1195   ConsumedWarningsHandlerBase &WarningsHandler) {
1196 
1197   ConsumedState LocalState;
1198   SourceLocation BlameLoc = getLastStmtLoc(LoopBack);
1199 
1200   for (MapType::const_iterator DMI = LoopBackStates->Map.begin(),
1201        DME = LoopBackStates->Map.end(); DMI != DME; ++DMI) {
1202 
1203     LocalState = this->getState(DMI->first);
1204 
1205     if (LocalState == CS_None)
1206       continue;
1207 
1208     if (LocalState != DMI->second) {
1209       Map[DMI->first] = CS_Unknown;
1210       WarningsHandler.warnLoopStateMismatch(
1211         BlameLoc, DMI->first->getNameAsString());
1212     }
1213   }
1214 }
1215 
1216 void ConsumedStateMap::markUnreachable() {
1217   this->Reachable = false;
1218   Map.clear();
1219 }
1220 
1221 void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
1222   Map[Var] = State;
1223 }
1224 
1225 void ConsumedStateMap::remove(const VarDecl *Var) {
1226   Map.erase(Var);
1227 }
1228 
1229 bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const {
1230   for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
1231        DMI != DME; ++DMI) {
1232 
1233     if (this->getState(DMI->first) != DMI->second)
1234       return true;
1235   }
1236 
1237   return false;
1238 }
1239 
1240 void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC,
1241                                                     const FunctionDecl *D) {
1242   QualType ReturnType;
1243   if (const CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
1244     ASTContext &CurrContext = AC.getASTContext();
1245     ReturnType = Constructor->getThisType(CurrContext)->getPointeeType();
1246   } else
1247     ReturnType = D->getCallResultType();
1248 
1249   if (D->hasAttr<ReturnTypestateAttr>()) {
1250     const ReturnTypestateAttr *RTSAttr = D->getAttr<ReturnTypestateAttr>();
1251 
1252     const CXXRecordDecl *RD = ReturnType->getAsCXXRecordDecl();
1253     if (!RD || !RD->hasAttr<ConsumableAttr>()) {
1254       // FIXME: This should be removed when template instantiation propagates
1255       //        attributes at template specialization definition, not
1256       //        declaration. When it is removed the test needs to be enabled
1257       //        in SemaDeclAttr.cpp.
1258       WarningsHandler.warnReturnTypestateForUnconsumableType(
1259           RTSAttr->getLocation(), ReturnType.getAsString());
1260       ExpectedReturnState = CS_None;
1261     } else
1262       ExpectedReturnState = mapReturnTypestateAttrState(RTSAttr);
1263   } else if (isConsumableType(ReturnType))
1264     ExpectedReturnState = mapConsumableAttrState(ReturnType);
1265   else
1266     ExpectedReturnState = CS_None;
1267 }
1268 
1269 bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
1270                                   const ConsumedStmtVisitor &Visitor) {
1271 
1272   ConsumedStateMap *FalseStates = new ConsumedStateMap(*CurrStates);
1273   PropagationInfo PInfo;
1274 
1275   if (const IfStmt *IfNode =
1276     dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
1277 
1278     const Stmt *Cond = IfNode->getCond();
1279 
1280     PInfo = Visitor.getInfo(Cond);
1281     if (!PInfo.isValid() && isa<BinaryOperator>(Cond))
1282       PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS());
1283 
1284     if (PInfo.isTest()) {
1285       CurrStates->setSource(Cond);
1286       FalseStates->setSource(Cond);
1287       splitVarStateForIf(IfNode, PInfo.getTest(), CurrStates, FalseStates);
1288 
1289     } else if (PInfo.isBinTest()) {
1290       CurrStates->setSource(PInfo.testSourceNode());
1291       FalseStates->setSource(PInfo.testSourceNode());
1292       splitVarStateForIfBinOp(PInfo, CurrStates, FalseStates);
1293 
1294     } else {
1295       delete FalseStates;
1296       return false;
1297     }
1298 
1299   } else if (const BinaryOperator *BinOp =
1300     dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) {
1301 
1302     PInfo = Visitor.getInfo(BinOp->getLHS());
1303     if (!PInfo.isTest()) {
1304       if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) {
1305         PInfo = Visitor.getInfo(BinOp->getRHS());
1306 
1307         if (!PInfo.isTest()) {
1308           delete FalseStates;
1309           return false;
1310         }
1311 
1312       } else {
1313         delete FalseStates;
1314         return false;
1315       }
1316     }
1317 
1318     CurrStates->setSource(BinOp);
1319     FalseStates->setSource(BinOp);
1320 
1321     const VarTestResult &Test = PInfo.getTest();
1322     ConsumedState VarState = CurrStates->getState(Test.Var);
1323 
1324     if (BinOp->getOpcode() == BO_LAnd) {
1325       if (VarState == CS_Unknown)
1326         CurrStates->setState(Test.Var, Test.TestsFor);
1327       else if (VarState == invertConsumedUnconsumed(Test.TestsFor))
1328         CurrStates->markUnreachable();
1329 
1330     } else if (BinOp->getOpcode() == BO_LOr) {
1331       if (VarState == CS_Unknown)
1332         FalseStates->setState(Test.Var,
1333                               invertConsumedUnconsumed(Test.TestsFor));
1334       else if (VarState == Test.TestsFor)
1335         FalseStates->markUnreachable();
1336     }
1337 
1338   } else {
1339     delete FalseStates;
1340     return false;
1341   }
1342 
1343   CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
1344 
1345   if (*SI)
1346     BlockInfo.addInfo(*SI, CurrStates);
1347   else
1348     delete CurrStates;
1349 
1350   if (*++SI)
1351     BlockInfo.addInfo(*SI, FalseStates);
1352   else
1353     delete FalseStates;
1354 
1355   CurrStates = NULL;
1356   return true;
1357 }
1358 
1359 void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
1360   const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
1361   if (!D)
1362     return;
1363 
1364   CFG *CFGraph = AC.getCFG();
1365   if (!CFGraph)
1366     return;
1367 
1368   determineExpectedReturnState(AC, D);
1369 
1370   PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
1371   // AC.getCFG()->viewCFG(LangOptions());
1372 
1373   BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
1374 
1375   CurrStates = new ConsumedStateMap();
1376   ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
1377 
1378   // Add all trackable parameters to the state map.
1379   for (FunctionDecl::param_const_iterator PI = D->param_begin(),
1380        PE = D->param_end(); PI != PE; ++PI) {
1381     Visitor.VisitParmVarDecl(*PI);
1382   }
1383 
1384   // Visit all of the function's basic blocks.
1385   for (PostOrderCFGView::iterator I = SortedGraph->begin(),
1386        E = SortedGraph->end(); I != E; ++I) {
1387 
1388     const CFGBlock *CurrBlock = *I;
1389 
1390     if (CurrStates == NULL)
1391       CurrStates = BlockInfo.getInfo(CurrBlock);
1392 
1393     if (!CurrStates) {
1394       continue;
1395 
1396     } else if (!CurrStates->isReachable()) {
1397       delete CurrStates;
1398       CurrStates = NULL;
1399       continue;
1400     }
1401 
1402     Visitor.reset(CurrStates);
1403 
1404     // Visit all of the basic block's statements.
1405     for (CFGBlock::const_iterator BI = CurrBlock->begin(),
1406          BE = CurrBlock->end(); BI != BE; ++BI) {
1407 
1408       switch (BI->getKind()) {
1409       case CFGElement::Statement:
1410         Visitor.Visit(BI->castAs<CFGStmt>().getStmt());
1411         break;
1412 
1413       case CFGElement::TemporaryDtor: {
1414         const CFGTemporaryDtor DTor = BI->castAs<CFGTemporaryDtor>();
1415         const CXXBindTemporaryExpr *BTE = DTor.getBindTemporaryExpr();
1416         PropagationInfo PInfo = Visitor.getInfo(BTE);
1417 
1418         if (PInfo.isValid())
1419           Visitor.checkCallability(PInfo,
1420                                    DTor.getDestructorDecl(AC.getASTContext()),
1421                                    BTE->getExprLoc());
1422         break;
1423       }
1424 
1425       case CFGElement::AutomaticObjectDtor: {
1426         const CFGAutomaticObjDtor DTor = BI->castAs<CFGAutomaticObjDtor>();
1427 
1428         const VarDecl *Var = DTor.getVarDecl();
1429         ConsumedState VarState = CurrStates->getState(Var);
1430 
1431         if (VarState != CS_None) {
1432           PropagationInfo PInfo(Var);
1433 
1434           Visitor.checkCallability(PInfo,
1435                                    DTor.getDestructorDecl(AC.getASTContext()),
1436                                    getLastStmtLoc(CurrBlock));
1437 
1438           CurrStates->remove(Var);
1439         }
1440         break;
1441       }
1442 
1443       default:
1444         break;
1445       }
1446     }
1447 
1448     // TODO: Handle other forms of branching with precision, including while-
1449     //       and for-loops. (Deferred)
1450     if (!splitState(CurrBlock, Visitor)) {
1451       CurrStates->setSource(NULL);
1452 
1453       if (CurrBlock->succ_size() > 1 ||
1454           (CurrBlock->succ_size() == 1 &&
1455            (*CurrBlock->succ_begin())->pred_size() > 1)) {
1456 
1457         bool OwnershipTaken = false;
1458 
1459         for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
1460              SE = CurrBlock->succ_end(); SI != SE; ++SI) {
1461 
1462           if (*SI == NULL) continue;
1463 
1464           if (BlockInfo.isBackEdge(CurrBlock, *SI)) {
1465             BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock,
1466                                                            CurrStates,
1467                                                            WarningsHandler);
1468 
1469             if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock))
1470               BlockInfo.discardInfo(*SI);
1471           } else {
1472             BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
1473           }
1474         }
1475 
1476         if (!OwnershipTaken)
1477           delete CurrStates;
1478 
1479         CurrStates = NULL;
1480       }
1481     }
1482 
1483     if (CurrBlock == &AC.getCFG()->getExit() &&
1484         D->getCallResultType()->isVoidType())
1485       CurrStates->checkParamsForReturnTypestate(D->getLocation(),
1486                                                 WarningsHandler);
1487   } // End of block iterator.
1488 
1489   // Delete the last existing state map.
1490   delete CurrStates;
1491 
1492   WarningsHandler.emitDiagnostics();
1493 }
1494 }} // end namespace clang::consumed
1495