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