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