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