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