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