Consumed.cpp revision b7dc1f5f30e1e46e44389b036d48f9614cfd5fe3 
1//===- Consumed.cpp --------------------------------------------*- C++ --*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// A intra-procedural analysis for checking consumed properties.  This is based,
11// in part, on research on linear types.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/Attr.h"
17#include "clang/AST/DeclCXX.h"
18#include "clang/AST/ExprCXX.h"
19#include "clang/AST/RecursiveASTVisitor.h"
20#include "clang/AST/StmtVisitor.h"
21#include "clang/AST/StmtCXX.h"
22#include "clang/AST/Type.h"
23#include "clang/Analysis/Analyses/PostOrderCFGView.h"
24#include "clang/Analysis/AnalysisContext.h"
25#include "clang/Analysis/CFG.h"
26#include "clang/Analysis/Analyses/Consumed.h"
27#include "clang/Basic/OperatorKinds.h"
28#include "clang/Basic/SourceLocation.h"
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/Support/Compiler.h"
32#include "llvm/Support/raw_ostream.h"
33
34// TODO: Correctly identify unreachable blocks when chaining boolean operators.
35// TODO: Warn about unreachable code.
36// TODO: Switch to using a bitmap to track unreachable blocks.
37// TODO: Mark variables as Unknown going into while- or for-loops only if they
38//       are referenced inside that block. (Deferred)
39// TODO: Handle variable definitions, e.g. bool valid = x.isValid();
40//       if (valid) ...; (Deferred)
41// TODO: Add a method(s) to identify which method calls perform what state
42//       transitions. (Deferred)
43// TODO: Take notes on state transitions to provide better warning messages.
44//       (Deferred)
45// TODO: Test nested conditionals: A) Checking the same value multiple times,
46//       and 2) Checking different values. (Deferred)
47// TODO: Test IsFalseVisitor with values in the unknown state. (Deferred)
48// TODO: Look into combining IsFalseVisitor and TestedVarsVisitor. (Deferred)
49
50using namespace clang;
51using namespace consumed;
52
53// Key method definition
54ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
55
56static ConsumedState invertConsumedUnconsumed(ConsumedState State) {
57  switch (State) {
58  case CS_Unconsumed:
59    return CS_Consumed;
60  case CS_Consumed:
61    return CS_Unconsumed;
62  case CS_None:
63    return CS_None;
64  case CS_Unknown:
65    return CS_Unknown;
66  }
67  llvm_unreachable("invalid enum");
68}
69
70static bool isKnownState(ConsumedState State) {
71  switch (State) {
72  case CS_Unconsumed:
73  case CS_Consumed:
74    return true;
75  case CS_None:
76  case CS_Unknown:
77    return false;
78  }
79}
80
81static bool isTestingFunction(const FunctionDecl *FunDecl) {
82  return FunDecl->hasAttr<TestsUnconsumedAttr>();
83}
84
85static StringRef stateToString(ConsumedState State) {
86  switch (State) {
87  case consumed::CS_None:
88    return "none";
89
90  case consumed::CS_Unknown:
91    return "unknown";
92
93  case consumed::CS_Unconsumed:
94    return "unconsumed";
95
96  case consumed::CS_Consumed:
97    return "consumed";
98  }
99  llvm_unreachable("invalid enum");
100}
101
102namespace {
103struct VarTestResult {
104  const VarDecl *Var;
105  ConsumedState TestsFor;
106};
107} // end anonymous::VarTestResult
108
109namespace clang {
110namespace consumed {
111
112enum EffectiveOp {
113  EO_And,
114  EO_Or
115};
116
117class PropagationInfo {
118  enum {
119    IT_None,
120    IT_State,
121    IT_Test,
122    IT_BinTest,
123    IT_Var
124  } InfoType;
125
126  union {
127    ConsumedState State;
128    VarTestResult Test;
129    const VarDecl *Var;
130    struct {
131      const BinaryOperator *Source;
132      EffectiveOp EOp;
133      VarTestResult LTest;
134      VarTestResult RTest;
135    } BinTest;
136  };
137
138public:
139  PropagationInfo() : InfoType(IT_None) {}
140
141  PropagationInfo(const VarTestResult &Test) : InfoType(IT_Test), Test(Test) {}
142  PropagationInfo(const VarDecl *Var, ConsumedState TestsFor)
143    : InfoType(IT_Test) {
144
145    Test.Var      = Var;
146    Test.TestsFor = TestsFor;
147  }
148
149  PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
150                  const VarTestResult &LTest, const VarTestResult &RTest)
151    : InfoType(IT_BinTest) {
152
153    BinTest.Source  = Source;
154    BinTest.EOp     = EOp;
155    BinTest.LTest   = LTest;
156    BinTest.RTest   = RTest;
157  }
158
159  PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
160                  const VarDecl *LVar, ConsumedState LTestsFor,
161                  const VarDecl *RVar, ConsumedState RTestsFor)
162    : InfoType(IT_BinTest) {
163
164    BinTest.Source         = Source;
165    BinTest.EOp            = EOp;
166    BinTest.LTest.Var      = LVar;
167    BinTest.LTest.TestsFor = LTestsFor;
168    BinTest.RTest.Var      = RVar;
169    BinTest.RTest.TestsFor = RTestsFor;
170  }
171
172  PropagationInfo(ConsumedState State) : InfoType(IT_State), State(State) {}
173  PropagationInfo(const VarDecl *Var) : InfoType(IT_Var), Var(Var) {}
174
175  const ConsumedState & getState() const {
176    assert(InfoType == IT_State);
177    return State;
178  }
179
180  const VarTestResult & getTest() const {
181    assert(InfoType == IT_Test);
182    return Test;
183  }
184
185  const VarTestResult & getLTest() const {
186    assert(InfoType == IT_BinTest);
187    return BinTest.LTest;
188  }
189
190  const VarTestResult & getRTest() const {
191    assert(InfoType == IT_BinTest);
192    return BinTest.RTest;
193  }
194
195  const VarDecl * getVar() const {
196    assert(InfoType == IT_Var);
197    return Var;
198  }
199
200  EffectiveOp testEffectiveOp() const {
201    assert(InfoType == IT_BinTest);
202    return BinTest.EOp;
203  }
204
205  const BinaryOperator * testSourceNode() const {
206    assert(InfoType == IT_BinTest);
207    return BinTest.Source;
208  }
209
210  bool isValid()   const { return InfoType != IT_None;     }
211  bool isState()   const { return InfoType == IT_State;    }
212  bool isTest()    const { return InfoType == IT_Test;     }
213  bool isBinTest() const { return InfoType == IT_BinTest;  }
214  bool isVar()     const { return InfoType == IT_Var;      }
215
216  PropagationInfo invertTest() const {
217    assert(InfoType == IT_Test || InfoType == IT_BinTest);
218
219    if (InfoType == IT_Test) {
220      return PropagationInfo(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
221
222    } else if (InfoType == IT_BinTest) {
223      return PropagationInfo(BinTest.Source,
224        BinTest.EOp == EO_And ? EO_Or : EO_And,
225        BinTest.LTest.Var, invertConsumedUnconsumed(BinTest.LTest.TestsFor),
226        BinTest.RTest.Var, invertConsumedUnconsumed(BinTest.RTest.TestsFor));
227    } else {
228      return PropagationInfo();
229    }
230  }
231};
232
233class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> {
234
235  typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType;
236  typedef std::pair<const Stmt *, PropagationInfo> PairType;
237  typedef MapType::iterator InfoEntry;
238  typedef MapType::const_iterator ConstInfoEntry;
239
240  AnalysisDeclContext &AC;
241  ConsumedAnalyzer &Analyzer;
242  ConsumedStateMap *StateMap;
243  MapType PropagationMap;
244
245  void checkCallability(const PropagationInfo &PInfo,
246                        const FunctionDecl *FunDecl,
247                        const CallExpr *Call);
248  void forwardInfo(const Stmt *From, const Stmt *To);
249  void handleTestingFunctionCall(const CallExpr *Call, const VarDecl *Var);
250  bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
251
252public:
253
254  void Visit(const Stmt *StmtNode);
255
256  void VisitBinaryOperator(const BinaryOperator *BinOp);
257  void VisitCallExpr(const CallExpr *Call);
258  void VisitCastExpr(const CastExpr *Cast);
259  void VisitCXXConstructExpr(const CXXConstructExpr *Call);
260  void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call);
261  void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call);
262  void VisitDeclRefExpr(const DeclRefExpr *DeclRef);
263  void VisitDeclStmt(const DeclStmt *DelcS);
264  void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp);
265  void VisitMemberExpr(const MemberExpr *MExpr);
266  void VisitUnaryOperator(const UnaryOperator *UOp);
267  void VisitVarDecl(const VarDecl *Var);
268
269  ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer)
270      : AC(AC), Analyzer(Analyzer), StateMap(NULL) {}
271
272  PropagationInfo getInfo(const Stmt *StmtNode) const {
273    ConstInfoEntry Entry = PropagationMap.find(StmtNode);
274
275    if (Entry != PropagationMap.end())
276      return Entry->second;
277    else
278      return PropagationInfo();
279  }
280
281  void reset(ConsumedStateMap *NewStateMap) {
282    StateMap = NewStateMap;
283  }
284};
285
286// TODO: When we support CallableWhenConsumed this will have to check for
287//       the different attributes and change the behavior bellow. (Deferred)
288void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo,
289                                           const FunctionDecl *FunDecl,
290                                           const CallExpr *Call) {
291
292  if (!FunDecl->hasAttr<CallableWhenUnconsumedAttr>()) return;
293
294  if (PInfo.isVar()) {
295    const VarDecl *Var = PInfo.getVar();
296
297    switch (StateMap->getState(Var)) {
298    case CS_Consumed:
299      Analyzer.WarningsHandler.warnUseWhileConsumed(
300        FunDecl->getNameAsString(), Var->getNameAsString(),
301        Call->getExprLoc());
302      break;
303
304    case CS_Unknown:
305      Analyzer.WarningsHandler.warnUseInUnknownState(
306        FunDecl->getNameAsString(), Var->getNameAsString(),
307        Call->getExprLoc());
308      break;
309
310    case CS_None:
311    case CS_Unconsumed:
312      break;
313    }
314
315  } else {
316    switch (PInfo.getState()) {
317    case CS_Consumed:
318      Analyzer.WarningsHandler.warnUseOfTempWhileConsumed(
319        FunDecl->getNameAsString(), Call->getExprLoc());
320      break;
321
322    case CS_Unknown:
323      Analyzer.WarningsHandler.warnUseOfTempInUnknownState(
324        FunDecl->getNameAsString(), Call->getExprLoc());
325      break;
326
327    case CS_None:
328    case CS_Unconsumed:
329      break;
330    }
331  }
332}
333
334void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) {
335  InfoEntry Entry = PropagationMap.find(From);
336
337  if (Entry != PropagationMap.end())
338    PropagationMap.insert(PairType(To, Entry->second));
339}
340
341void ConsumedStmtVisitor::handleTestingFunctionCall(const CallExpr *Call,
342                                                    const VarDecl  *Var) {
343
344  ConsumedState VarState = StateMap->getState(Var);
345
346  if (VarState != CS_Unknown) {
347    SourceLocation CallLoc = Call->getExprLoc();
348
349    if (!CallLoc.isMacroID())
350      Analyzer.WarningsHandler.warnUnnecessaryTest(Var->getNameAsString(),
351        stateToString(VarState), CallLoc);
352  }
353
354  PropagationMap.insert(PairType(Call, PropagationInfo(Var, CS_Unconsumed)));
355}
356
357bool ConsumedStmtVisitor::isLikeMoveAssignment(
358  const CXXMethodDecl *MethodDecl) {
359
360  return MethodDecl->isMoveAssignmentOperator() ||
361         (MethodDecl->getOverloadedOperator() == OO_Equal &&
362          MethodDecl->getNumParams() == 1 &&
363          MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType());
364}
365
366void ConsumedStmtVisitor::Visit(const Stmt *StmtNode) {
367
368  ConstStmtVisitor<ConsumedStmtVisitor>::Visit(StmtNode);
369
370  for (Stmt::const_child_iterator CI = StmtNode->child_begin(),
371       CE = StmtNode->child_end(); CI != CE; ++CI) {
372
373    PropagationMap.erase(*CI);
374  }
375}
376
377void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) {
378  switch (BinOp->getOpcode()) {
379  case BO_LAnd:
380  case BO_LOr : {
381    InfoEntry LEntry = PropagationMap.find(BinOp->getLHS()),
382              REntry = PropagationMap.find(BinOp->getRHS());
383
384    VarTestResult LTest, RTest;
385
386    if (LEntry != PropagationMap.end() && LEntry->second.isTest()) {
387      LTest = LEntry->second.getTest();
388
389    } else {
390      LTest.Var      = NULL;
391      LTest.TestsFor = CS_None;
392    }
393
394    if (REntry != PropagationMap.end() && REntry->second.isTest()) {
395      RTest = REntry->second.getTest();
396
397    } else {
398      RTest.Var      = NULL;
399      RTest.TestsFor = CS_None;
400    }
401
402    if (!(LTest.Var == NULL && RTest.Var == NULL))
403      PropagationMap.insert(PairType(BinOp, PropagationInfo(BinOp,
404        static_cast<EffectiveOp>(BinOp->getOpcode() == BO_LOr), LTest, RTest)));
405
406    break;
407  }
408
409  case BO_PtrMemD:
410  case BO_PtrMemI:
411    forwardInfo(BinOp->getLHS(), BinOp);
412    break;
413
414  default:
415    break;
416  }
417}
418
419void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) {
420  if (const FunctionDecl *FunDecl =
421    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
422
423    // Special case for the std::move function.
424    // TODO: Make this more specific. (Deferred)
425    if (FunDecl->getNameAsString() == "move") {
426      InfoEntry Entry = PropagationMap.find(Call->getArg(0));
427
428      if (Entry != PropagationMap.end()) {
429        PropagationMap.insert(PairType(Call, Entry->second));
430      }
431
432      return;
433    }
434
435    unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams();
436
437    for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) {
438      QualType ParamType = FunDecl->getParamDecl(Index - Offset)->getType();
439
440      InfoEntry Entry = PropagationMap.find(Call->getArg(Index));
441
442      if (Entry == PropagationMap.end() || !Entry->second.isVar()) {
443        continue;
444      }
445
446      PropagationInfo PInfo = Entry->second;
447
448      if (ParamType->isRValueReferenceType() ||
449          (ParamType->isLValueReferenceType() &&
450           !cast<LValueReferenceType>(*ParamType).isSpelledAsLValue())) {
451
452        StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
453
454      } else if (!(ParamType.isConstQualified() ||
455                   ((ParamType->isReferenceType() ||
456                     ParamType->isPointerType()) &&
457                    ParamType->getPointeeType().isConstQualified()))) {
458
459        StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
460      }
461    }
462  }
463}
464
465void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) {
466  forwardInfo(Cast->getSubExpr(), Cast);
467}
468
469void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) {
470  CXXConstructorDecl *Constructor = Call->getConstructor();
471
472  ASTContext &CurrContext = AC.getASTContext();
473  QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType();
474
475  if (Analyzer.isConsumableType(ThisType)) {
476    if (Constructor->hasAttr<ConsumesAttr>() ||
477        Constructor->isDefaultConstructor()) {
478
479      PropagationMap.insert(PairType(Call,
480        PropagationInfo(consumed::CS_Consumed)));
481
482    } else if (Constructor->isMoveConstructor()) {
483
484      PropagationInfo PInfo =
485        PropagationMap.find(Call->getArg(0))->second;
486
487      if (PInfo.isVar()) {
488        const VarDecl* Var = PInfo.getVar();
489
490        PropagationMap.insert(PairType(Call,
491          PropagationInfo(StateMap->getState(Var))));
492
493        StateMap->setState(Var, consumed::CS_Consumed);
494
495      } else {
496        PropagationMap.insert(PairType(Call, PInfo));
497      }
498
499    } else if (Constructor->isCopyConstructor()) {
500      MapType::iterator Entry = PropagationMap.find(Call->getArg(0));
501
502      if (Entry != PropagationMap.end())
503        PropagationMap.insert(PairType(Call, Entry->second));
504
505    } else {
506      PropagationMap.insert(PairType(Call,
507        PropagationInfo(consumed::CS_Unconsumed)));
508    }
509  }
510}
511
512void ConsumedStmtVisitor::VisitCXXMemberCallExpr(
513  const CXXMemberCallExpr *Call) {
514
515  VisitCallExpr(Call);
516
517  InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
518
519  if (Entry != PropagationMap.end()) {
520    PropagationInfo PInfo = Entry->second;
521    const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
522
523    checkCallability(PInfo, MethodDecl, Call);
524
525    if (PInfo.isVar()) {
526      if (isTestingFunction(MethodDecl))
527        handleTestingFunctionCall(Call, PInfo.getVar());
528      else if (MethodDecl->hasAttr<ConsumesAttr>())
529        StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
530      else if (!MethodDecl->isConst())
531        StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
532    }
533  }
534}
535
536void ConsumedStmtVisitor::VisitCXXOperatorCallExpr(
537  const CXXOperatorCallExpr *Call) {
538
539  const FunctionDecl *FunDecl =
540    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee());
541
542  if (!FunDecl) return;
543
544  if (isa<CXXMethodDecl>(FunDecl) &&
545      isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) {
546
547    InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
548    InfoEntry REntry = PropagationMap.find(Call->getArg(1));
549
550    PropagationInfo LPInfo, RPInfo;
551
552    if (LEntry != PropagationMap.end() &&
553        REntry != PropagationMap.end()) {
554
555      LPInfo = LEntry->second;
556      RPInfo = REntry->second;
557
558      if (LPInfo.isVar() && RPInfo.isVar()) {
559        StateMap->setState(LPInfo.getVar(),
560          StateMap->getState(RPInfo.getVar()));
561
562        StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
563
564        PropagationMap.insert(PairType(Call, LPInfo));
565
566      } else if (LPInfo.isVar() && !RPInfo.isVar()) {
567        StateMap->setState(LPInfo.getVar(), RPInfo.getState());
568
569        PropagationMap.insert(PairType(Call, LPInfo));
570
571      } else if (!LPInfo.isVar() && RPInfo.isVar()) {
572        PropagationMap.insert(PairType(Call,
573          PropagationInfo(StateMap->getState(RPInfo.getVar()))));
574
575        StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
576
577      } else {
578        PropagationMap.insert(PairType(Call, RPInfo));
579      }
580
581    } else if (LEntry != PropagationMap.end() &&
582               REntry == PropagationMap.end()) {
583
584      LPInfo = LEntry->second;
585
586      if (LPInfo.isVar()) {
587        StateMap->setState(LPInfo.getVar(), consumed::CS_Unknown);
588
589        PropagationMap.insert(PairType(Call, LPInfo));
590
591      } else {
592        PropagationMap.insert(PairType(Call,
593          PropagationInfo(consumed::CS_Unknown)));
594      }
595
596    } else if (LEntry == PropagationMap.end() &&
597               REntry != PropagationMap.end()) {
598
599      RPInfo = REntry->second;
600
601      if (RPInfo.isVar()) {
602        const VarDecl *Var = RPInfo.getVar();
603
604        PropagationMap.insert(PairType(Call,
605          PropagationInfo(StateMap->getState(Var))));
606
607        StateMap->setState(Var, consumed::CS_Consumed);
608
609      } else {
610        PropagationMap.insert(PairType(Call, RPInfo));
611      }
612    }
613
614  } else {
615
616    VisitCallExpr(Call);
617
618    InfoEntry Entry = PropagationMap.find(Call->getArg(0));
619
620    if (Entry != PropagationMap.end()) {
621      PropagationInfo PInfo = Entry->second;
622
623      checkCallability(PInfo, FunDecl, Call);
624
625      if (PInfo.isVar()) {
626        if (isTestingFunction(FunDecl)) {
627          handleTestingFunctionCall(Call, PInfo.getVar());
628
629        } else if (FunDecl->hasAttr<ConsumesAttr>()) {
630          StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
631
632        } else if (const CXXMethodDecl *MethodDecl =
633                     dyn_cast_or_null<CXXMethodDecl>(FunDecl)) {
634
635          if (!MethodDecl->isConst())
636            StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
637        }
638      }
639    }
640  }
641}
642
643void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) {
644  if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
645    if (StateMap->getState(Var) != consumed::CS_None)
646      PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
647}
648
649void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) {
650  for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(),
651       DE = DeclS->decl_end(); DI != DE; ++DI) {
652
653    if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI));
654  }
655
656  if (DeclS->isSingleDecl())
657    if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl()))
658      PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
659}
660
661void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
662  const MaterializeTemporaryExpr *Temp) {
663
664  InfoEntry Entry = PropagationMap.find(Temp->GetTemporaryExpr());
665
666  if (Entry != PropagationMap.end())
667    PropagationMap.insert(PairType(Temp, Entry->second));
668}
669
670void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
671  forwardInfo(MExpr->getBase(), MExpr);
672}
673
674void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) {
675  InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens());
676  if (Entry == PropagationMap.end()) return;
677
678  switch (UOp->getOpcode()) {
679  case UO_AddrOf:
680    PropagationMap.insert(PairType(UOp, Entry->second));
681    break;
682
683  case UO_LNot:
684    if (Entry->second.isTest() || Entry->second.isBinTest())
685      PropagationMap.insert(PairType(UOp, Entry->second.invertTest()));
686    break;
687
688  default:
689    break;
690  }
691}
692
693void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
694  if (Analyzer.isConsumableType(Var->getType())) {
695    PropagationInfo PInfo =
696      PropagationMap.find(Var->getInit())->second;
697
698    StateMap->setState(Var, PInfo.isVar() ?
699      StateMap->getState(PInfo.getVar()) : PInfo.getState());
700  }
701}
702}} // end clang::consumed::ConsumedStmtVisitor
703
704namespace clang {
705namespace consumed {
706
707void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test,
708                        ConsumedStateMap *ThenStates,
709                        ConsumedStateMap *ElseStates) {
710
711  ConsumedState VarState = ThenStates->getState(Test.Var);
712
713  if (VarState == CS_Unknown) {
714    ThenStates->setState(Test.Var, Test.TestsFor);
715    if (ElseStates)
716      ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
717
718  } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) {
719    ThenStates->markUnreachable();
720
721  } else if (VarState == Test.TestsFor && ElseStates) {
722    ElseStates->markUnreachable();
723  }
724}
725
726void splitVarStateForIfBinOp(const PropagationInfo &PInfo,
727  ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) {
728
729  const VarTestResult &LTest = PInfo.getLTest(),
730                      &RTest = PInfo.getRTest();
731
732  ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None,
733                RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None;
734
735  if (LTest.Var) {
736    if (PInfo.testEffectiveOp() == EO_And) {
737      if (LState == CS_Unknown) {
738        ThenStates->setState(LTest.Var, LTest.TestsFor);
739
740      } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) {
741        ThenStates->markUnreachable();
742
743      } else if (LState == LTest.TestsFor && isKnownState(RState)) {
744        if (RState == RTest.TestsFor) {
745          if (ElseStates)
746            ElseStates->markUnreachable();
747        } else {
748          ThenStates->markUnreachable();
749        }
750      }
751
752    } else {
753      if (LState == CS_Unknown && ElseStates) {
754        ElseStates->setState(LTest.Var,
755                             invertConsumedUnconsumed(LTest.TestsFor));
756
757      } else if (LState == LTest.TestsFor && ElseStates) {
758        ElseStates->markUnreachable();
759
760      } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) &&
761                 isKnownState(RState)) {
762
763        if (RState == RTest.TestsFor) {
764          if (ElseStates)
765            ElseStates->markUnreachable();
766        } else {
767          ThenStates->markUnreachable();
768        }
769      }
770    }
771  }
772
773  if (RTest.Var) {
774    if (PInfo.testEffectiveOp() == EO_And) {
775      if (RState == CS_Unknown)
776        ThenStates->setState(RTest.Var, RTest.TestsFor);
777      else if (RState == invertConsumedUnconsumed(RTest.TestsFor))
778        ThenStates->markUnreachable();
779
780    } else if (ElseStates) {
781      if (RState == CS_Unknown)
782        ElseStates->setState(RTest.Var,
783                             invertConsumedUnconsumed(RTest.TestsFor));
784      else if (RState == RTest.TestsFor)
785        ElseStates->markUnreachable();
786    }
787  }
788}
789
790void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
791                                ConsumedStateMap *StateMap,
792                                bool &AlreadyOwned) {
793
794  if (VisitedBlocks.alreadySet(Block)) return;
795
796  ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
797
798  if (Entry) {
799    Entry->intersect(StateMap);
800
801  } else if (AlreadyOwned) {
802    StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap);
803
804  } else {
805    StateMapsArray[Block->getBlockID()] = StateMap;
806    AlreadyOwned = true;
807  }
808}
809
810void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
811                                ConsumedStateMap *StateMap) {
812
813  if (VisitedBlocks.alreadySet(Block)) {
814    delete StateMap;
815    return;
816  }
817
818  ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
819
820  if (Entry) {
821    Entry->intersect(StateMap);
822    delete StateMap;
823
824  } else {
825    StateMapsArray[Block->getBlockID()] = StateMap;
826  }
827}
828
829ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
830  return StateMapsArray[Block->getBlockID()];
831}
832
833void ConsumedBlockInfo::markVisited(const CFGBlock *Block) {
834  VisitedBlocks.insert(Block);
835}
836
837ConsumedState ConsumedStateMap::getState(const VarDecl *Var) {
838  MapType::const_iterator Entry = Map.find(Var);
839
840  if (Entry != Map.end()) {
841    return Entry->second;
842
843  } else {
844    return CS_None;
845  }
846}
847
848void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
849  ConsumedState LocalState;
850
851  if (this->From && this->From == Other->From && !Other->Reachable) {
852    this->markUnreachable();
853    return;
854  }
855
856  for (MapType::const_iterator DMI = Other->Map.begin(),
857       DME = Other->Map.end(); DMI != DME; ++DMI) {
858
859    LocalState = this->getState(DMI->first);
860
861    if (LocalState == CS_None)
862      continue;
863
864    if (LocalState != DMI->second)
865       Map[DMI->first] = CS_Unknown;
866  }
867}
868
869void ConsumedStateMap::markUnreachable() {
870  this->Reachable = false;
871  Map.clear();
872}
873
874void ConsumedStateMap::makeUnknown() {
875  for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
876       ++DMI) {
877
878    Map[DMI->first] = CS_Unknown;
879  }
880}
881
882void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
883  Map[Var] = State;
884}
885
886void ConsumedStateMap::remove(const VarDecl *Var) {
887  Map.erase(Var);
888}
889
890bool ConsumedAnalyzer::isConsumableType(QualType Type) {
891  const CXXRecordDecl *RD =
892    dyn_cast_or_null<CXXRecordDecl>(Type->getAsCXXRecordDecl());
893
894  if (!RD) return false;
895
896  std::pair<CacheMapType::iterator, bool> Entry =
897    ConsumableTypeCache.insert(std::make_pair(RD, false));
898
899  if (Entry.second)
900    Entry.first->second = hasConsumableAttributes(RD);
901
902  return Entry.first->second;
903}
904
905// TODO: Walk the base classes to see if any of them are unique types.
906//       (Deferred)
907bool ConsumedAnalyzer::hasConsumableAttributes(const CXXRecordDecl *RD) {
908  for (CXXRecordDecl::method_iterator MI = RD->method_begin(),
909       ME = RD->method_end(); MI != ME; ++MI) {
910
911    for (Decl::attr_iterator AI = (*MI)->attr_begin(), AE = (*MI)->attr_end();
912         AI != AE; ++AI) {
913
914      switch ((*AI)->getKind()) {
915      case attr::CallableWhenUnconsumed:
916      case attr::TestsUnconsumed:
917        return true;
918
919      default:
920        break;
921      }
922    }
923  }
924
925  return false;
926}
927
928bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
929                                  const ConsumedStmtVisitor &Visitor) {
930
931  ConsumedStateMap *FalseStates = new ConsumedStateMap(*CurrStates);
932  PropagationInfo PInfo;
933
934  if (const IfStmt *IfNode =
935    dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
936
937    bool HasElse = IfNode->getElse() != NULL;
938    const Stmt *Cond = IfNode->getCond();
939
940    PInfo = Visitor.getInfo(Cond);
941    if (!PInfo.isValid() && isa<BinaryOperator>(Cond))
942      PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS());
943
944    if (PInfo.isTest()) {
945      CurrStates->setSource(Cond);
946      FalseStates->setSource(Cond);
947
948      splitVarStateForIf(IfNode, PInfo.getTest(), CurrStates,
949                         HasElse ? FalseStates : NULL);
950
951    } else if (PInfo.isBinTest()) {
952      CurrStates->setSource(PInfo.testSourceNode());
953      FalseStates->setSource(PInfo.testSourceNode());
954
955      splitVarStateForIfBinOp(PInfo, CurrStates, HasElse ? FalseStates : NULL);
956
957    } else {
958      delete FalseStates;
959      return false;
960    }
961
962  } else if (const BinaryOperator *BinOp =
963    dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) {
964
965    PInfo = Visitor.getInfo(BinOp->getLHS());
966    if (!PInfo.isTest()) {
967      if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) {
968        PInfo = Visitor.getInfo(BinOp->getRHS());
969
970        if (!PInfo.isTest()) {
971          delete FalseStates;
972          return false;
973        }
974
975      } else {
976        delete FalseStates;
977        return false;
978      }
979    }
980
981    CurrStates->setSource(BinOp);
982    FalseStates->setSource(BinOp);
983
984    const VarTestResult &Test = PInfo.getTest();
985    ConsumedState VarState = CurrStates->getState(Test.Var);
986
987    if (BinOp->getOpcode() == BO_LAnd) {
988      if (VarState == CS_Unknown)
989        CurrStates->setState(Test.Var, Test.TestsFor);
990      else if (VarState == invertConsumedUnconsumed(Test.TestsFor))
991        CurrStates->markUnreachable();
992
993    } else if (BinOp->getOpcode() == BO_LOr) {
994      if (VarState == CS_Unknown)
995        FalseStates->setState(Test.Var,
996                              invertConsumedUnconsumed(Test.TestsFor));
997      else if (VarState == Test.TestsFor)
998        FalseStates->markUnreachable();
999    }
1000
1001  } else {
1002    delete FalseStates;
1003    return false;
1004  }
1005
1006  CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
1007
1008  if (*SI)
1009    BlockInfo.addInfo(*SI, CurrStates);
1010  else
1011    delete CurrStates;
1012
1013  if (*++SI)
1014    BlockInfo.addInfo(*SI, FalseStates);
1015  else
1016    delete FalseStates;
1017
1018  CurrStates = NULL;
1019  return true;
1020}
1021
1022void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
1023  const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
1024
1025  if (!D) return;
1026
1027  BlockInfo = ConsumedBlockInfo(AC.getCFG());
1028
1029  PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
1030
1031  CurrStates = new ConsumedStateMap();
1032  ConsumedStmtVisitor Visitor(AC, *this);
1033
1034  // Visit all of the function's basic blocks.
1035  for (PostOrderCFGView::iterator I = SortedGraph->begin(),
1036       E = SortedGraph->end(); I != E; ++I) {
1037
1038    const CFGBlock *CurrBlock = *I;
1039    BlockInfo.markVisited(CurrBlock);
1040
1041    if (CurrStates == NULL)
1042      CurrStates = BlockInfo.getInfo(CurrBlock);
1043
1044    if (!CurrStates) {
1045      continue;
1046
1047    } else if (!CurrStates->isReachable()) {
1048      delete CurrStates;
1049      CurrStates = NULL;
1050      continue;
1051    }
1052
1053    Visitor.reset(CurrStates);
1054
1055    // Visit all of the basic block's statements.
1056    for (CFGBlock::const_iterator BI = CurrBlock->begin(),
1057         BE = CurrBlock->end(); BI != BE; ++BI) {
1058
1059      switch (BI->getKind()) {
1060      case CFGElement::Statement:
1061        Visitor.Visit(BI->castAs<CFGStmt>().getStmt());
1062        break;
1063      case CFGElement::AutomaticObjectDtor:
1064        CurrStates->remove(BI->castAs<CFGAutomaticObjDtor>().getVarDecl());
1065      default:
1066        break;
1067      }
1068    }
1069
1070    // TODO: Handle other forms of branching with precision, including while-
1071    //       and for-loops. (Deferred)
1072    if (!splitState(CurrBlock, Visitor)) {
1073      CurrStates->setSource(NULL);
1074
1075      if (CurrBlock->succ_size() > 1) {
1076        CurrStates->makeUnknown();
1077
1078        bool OwnershipTaken = false;
1079
1080        for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
1081             SE = CurrBlock->succ_end(); SI != SE; ++SI) {
1082
1083          if (*SI) BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
1084        }
1085
1086        if (!OwnershipTaken)
1087          delete CurrStates;
1088
1089        CurrStates = NULL;
1090
1091      } else if (CurrBlock->succ_size() == 1 &&
1092                 (*CurrBlock->succ_begin())->pred_size() > 1) {
1093
1094        BlockInfo.addInfo(*CurrBlock->succ_begin(), CurrStates);
1095        CurrStates = NULL;
1096      }
1097    }
1098  } // End of block iterator.
1099
1100  // Delete the last existing state map.
1101  delete CurrStates;
1102
1103  WarningsHandler.emitDiagnostics();
1104}
1105}} // end namespace clang::consumed
1106