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