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