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