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