Consumed.cpp revision b01e2da54178f1b1b6ef43bf3fa91dcdd3ff3094 
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/raw_ostream.h"
32
33// TODO: Mark variables as Unknown going into while- or for-loops only if they
34//       are referenced inside that block. (Deferred)
35// TODO: Add a method(s) to identify which method calls perform what state
36//       transitions. (Deferred)
37// TODO: Take notes on state transitions to provide better warning messages.
38//       (Deferred)
39// TODO: Test nested conditionals: A) Checking the same value multiple times,
40//       and 2) Checking different values. (Deferred)
41// TODO: Test IsFalseVisitor with values in the unknown state. (Deferred)
42// TODO: Look into combining IsFalseVisitor and TestedVarsVisitor. (Deferred)
43
44using namespace clang;
45using namespace consumed;
46
47// Key method definition
48ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
49
50static bool isTestingFunction(const FunctionDecl *FunDecl) {
51  return FunDecl->hasAttr<TestsUnconsumedAttr>();
52}
53
54static StringRef stateToString(ConsumedState State) {
55  switch (State) {
56  case consumed::CS_None:
57    return "none";
58
59  case consumed::CS_Unknown:
60    return "unknown";
61
62  case consumed::CS_Unconsumed:
63    return "unconsumed";
64
65  case consumed::CS_Consumed:
66    return "consumed";
67  }
68  llvm_unreachable("invalid enum");
69}
70
71namespace {
72class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> {
73
74  union PropagationUnion {
75    ConsumedState State;
76    const VarDecl *Var;
77  };
78
79  class PropagationInfo {
80    PropagationUnion StateOrVar;
81
82  public:
83    bool IsVar;
84
85    PropagationInfo() : IsVar(false) {
86      StateOrVar.State = consumed::CS_None;
87    }
88
89    PropagationInfo(ConsumedState State) : IsVar(false) {
90      StateOrVar.State = State;
91    }
92
93    PropagationInfo(const VarDecl *Var) : IsVar(true) {
94      StateOrVar.Var = Var;
95    }
96
97    ConsumedState getState() const { return StateOrVar.State; }
98
99    const VarDecl * getVar() const { return IsVar ? StateOrVar.Var : NULL; }
100  };
101
102  typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType;
103  typedef std::pair<const Stmt *, PropagationInfo> PairType;
104  typedef MapType::iterator InfoEntry;
105
106  AnalysisDeclContext &AC;
107  ConsumedAnalyzer &Analyzer;
108  ConsumedStateMap *StateMap;
109  MapType PropagationMap;
110
111  void checkCallability(const PropagationInfo &PInfo,
112                        const FunctionDecl *FunDecl,
113                        const CallExpr *Call);
114  void forwardInfo(const Stmt *From, const Stmt *To);
115  bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
116
117public:
118
119  void Visit(const Stmt *StmtNode);
120
121  void VisitBinaryOperator(const BinaryOperator *BinOp);
122  void VisitCallExpr(const CallExpr *Call);
123  void VisitCastExpr(const CastExpr *Cast);
124  void VisitCXXConstructExpr(const CXXConstructExpr *Call);
125  void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call);
126  void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call);
127  void VisitDeclRefExpr(const DeclRefExpr *DeclRef);
128  void VisitDeclStmt(const DeclStmt *DelcS);
129  void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp);
130  void VisitMemberExpr(const MemberExpr *MExpr);
131  void VisitUnaryOperator(const UnaryOperator *UOp);
132  void VisitVarDecl(const VarDecl *Var);
133
134  ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer,
135                      ConsumedStateMap *StateMap)
136      : AC(AC), Analyzer(Analyzer), StateMap(StateMap) {}
137
138  void reset() {
139    PropagationMap.clear();
140  }
141};
142
143// TODO: When we support CallableWhenConsumed this will have to check for
144//       the different attributes and change the behavior bellow. (Deferred)
145void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo,
146                                           const FunctionDecl *FunDecl,
147                                           const CallExpr *Call) {
148
149  if (!FunDecl->hasAttr<CallableWhenUnconsumedAttr>()) return;
150
151  if (PInfo.IsVar) {
152    const VarDecl *Var = PInfo.getVar();
153
154    switch (StateMap->getState(Var)) {
155    case CS_Consumed:
156      Analyzer.WarningsHandler.warnUseWhileConsumed(
157        FunDecl->getNameAsString(), Var->getNameAsString(),
158        Call->getExprLoc());
159      break;
160
161    case CS_Unknown:
162      Analyzer.WarningsHandler.warnUseInUnknownState(
163        FunDecl->getNameAsString(), Var->getNameAsString(),
164        Call->getExprLoc());
165      break;
166
167    case CS_None:
168    case CS_Unconsumed:
169      break;
170    }
171
172  } else {
173    switch (PInfo.getState()) {
174    case CS_Consumed:
175      Analyzer.WarningsHandler.warnUseOfTempWhileConsumed(
176        FunDecl->getNameAsString(), Call->getExprLoc());
177      break;
178
179    case CS_Unknown:
180      Analyzer.WarningsHandler.warnUseOfTempInUnknownState(
181        FunDecl->getNameAsString(), Call->getExprLoc());
182      break;
183
184    case CS_None:
185    case CS_Unconsumed:
186      break;
187    }
188  }
189}
190
191void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) {
192  InfoEntry Entry = PropagationMap.find(From);
193
194  if (Entry != PropagationMap.end()) {
195    PropagationMap.insert(PairType(To, PropagationInfo(Entry->second)));
196  }
197}
198
199bool ConsumedStmtVisitor::isLikeMoveAssignment(
200  const CXXMethodDecl *MethodDecl) {
201
202  return MethodDecl->isMoveAssignmentOperator() ||
203         (MethodDecl->getOverloadedOperator() == OO_Equal &&
204          MethodDecl->getNumParams() == 1 &&
205          MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType());
206}
207
208void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) {
209  switch (BinOp->getOpcode()) {
210  case BO_PtrMemD:
211  case BO_PtrMemI:
212    forwardInfo(BinOp->getLHS(), BinOp);
213    break;
214
215  default:
216    break;
217  }
218}
219
220void ConsumedStmtVisitor::Visit(const Stmt *StmtNode) {
221  ConstStmtVisitor<ConsumedStmtVisitor>::Visit(StmtNode);
222
223  for (Stmt::const_child_iterator CI = StmtNode->child_begin(),
224       CE = StmtNode->child_end(); CI != CE; ++CI) {
225
226    PropagationMap.erase(*CI);
227  }
228}
229
230void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) {
231  if (const FunctionDecl *FunDecl =
232    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
233
234    // Special case for the std::move function.
235    // TODO: Make this more specific. (Deferred)
236    if (FunDecl->getNameAsString() == "move") {
237      InfoEntry Entry = PropagationMap.find(Call->getArg(0));
238
239      if (Entry != PropagationMap.end()) {
240        PropagationMap.insert(PairType(Call, Entry->second));
241      }
242
243      return;
244    }
245
246    unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams();
247
248    for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) {
249      QualType ParamType = FunDecl->getParamDecl(Index - Offset)->getType();
250
251      InfoEntry Entry = PropagationMap.find(Call->getArg(Index));
252
253      if (Entry == PropagationMap.end() || !Entry->second.IsVar) {
254        continue;
255      }
256
257      PropagationInfo PInfo = Entry->second;
258
259      if (ParamType->isRValueReferenceType() ||
260          (ParamType->isLValueReferenceType() &&
261           !cast<LValueReferenceType>(*ParamType).isSpelledAsLValue())) {
262
263        StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
264
265      } else if (!(ParamType.isConstQualified() ||
266                   ((ParamType->isReferenceType() ||
267                     ParamType->isPointerType()) &&
268                    ParamType->getPointeeType().isConstQualified()))) {
269
270        StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
271      }
272    }
273  }
274}
275
276void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) {
277  InfoEntry Entry = PropagationMap.find(Cast->getSubExpr());
278
279  if (Entry != PropagationMap.end())
280    PropagationMap.insert(PairType(Cast, Entry->second));
281}
282
283void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) {
284  CXXConstructorDecl *Constructor = Call->getConstructor();
285
286  ASTContext &CurrContext = AC.getASTContext();
287  QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType();
288
289  if (Analyzer.isConsumableType(ThisType)) {
290    if (Constructor->hasAttr<ConsumesAttr>() ||
291        Constructor->isDefaultConstructor()) {
292
293      PropagationMap.insert(PairType(Call,
294        PropagationInfo(consumed::CS_Consumed)));
295
296    } else if (Constructor->isMoveConstructor()) {
297
298      PropagationInfo PInfo =
299        PropagationMap.find(Call->getArg(0))->second;
300
301      if (PInfo.IsVar) {
302        const VarDecl* Var = PInfo.getVar();
303
304        PropagationMap.insert(PairType(Call,
305          PropagationInfo(StateMap->getState(Var))));
306
307        StateMap->setState(Var, consumed::CS_Consumed);
308
309      } else {
310        PropagationMap.insert(PairType(Call, PInfo));
311      }
312
313    } else if (Constructor->isCopyConstructor()) {
314      MapType::iterator Entry = PropagationMap.find(Call->getArg(0));
315
316      if (Entry != PropagationMap.end())
317        PropagationMap.insert(PairType(Call, Entry->second));
318
319    } else {
320      PropagationMap.insert(PairType(Call,
321        PropagationInfo(consumed::CS_Unconsumed)));
322    }
323  }
324}
325
326void ConsumedStmtVisitor::VisitCXXMemberCallExpr(
327  const CXXMemberCallExpr *Call) {
328
329  VisitCallExpr(Call);
330
331  InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
332
333  if (Entry != PropagationMap.end()) {
334    PropagationInfo PInfo = Entry->second;
335    const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
336
337    checkCallability(PInfo, MethodDecl, Call);
338
339    if (PInfo.IsVar) {
340      if (MethodDecl->hasAttr<ConsumesAttr>())
341        StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
342      else if (!MethodDecl->isConst())
343        StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
344    }
345  }
346}
347
348void ConsumedStmtVisitor::VisitCXXOperatorCallExpr(
349  const CXXOperatorCallExpr *Call) {
350
351  const FunctionDecl *FunDecl =
352    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee());
353
354  if (!FunDecl) return;
355
356  if (isa<CXXMethodDecl>(FunDecl) &&
357      isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) {
358
359    InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
360    InfoEntry REntry = PropagationMap.find(Call->getArg(1));
361
362    PropagationInfo LPInfo, RPInfo;
363
364    if (LEntry != PropagationMap.end() &&
365        REntry != PropagationMap.end()) {
366
367      LPInfo = LEntry->second;
368      RPInfo = REntry->second;
369
370      if (LPInfo.IsVar && RPInfo.IsVar) {
371        StateMap->setState(LPInfo.getVar(),
372          StateMap->getState(RPInfo.getVar()));
373
374        StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
375
376        PropagationMap.insert(PairType(Call, LPInfo));
377
378      } else if (LPInfo.IsVar && !RPInfo.IsVar) {
379        StateMap->setState(LPInfo.getVar(), RPInfo.getState());
380
381        PropagationMap.insert(PairType(Call, LPInfo));
382
383      } else if (!LPInfo.IsVar && RPInfo.IsVar) {
384        PropagationMap.insert(PairType(Call,
385          PropagationInfo(StateMap->getState(RPInfo.getVar()))));
386
387        StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed);
388
389      } else {
390        PropagationMap.insert(PairType(Call, RPInfo));
391      }
392
393    } else if (LEntry != PropagationMap.end() &&
394               REntry == PropagationMap.end()) {
395
396      LPInfo = LEntry->second;
397
398      if (LPInfo.IsVar) {
399        StateMap->setState(LPInfo.getVar(), consumed::CS_Unknown);
400
401        PropagationMap.insert(PairType(Call, LPInfo));
402
403      } else {
404        PropagationMap.insert(PairType(Call,
405          PropagationInfo(consumed::CS_Unknown)));
406      }
407
408    } else if (LEntry == PropagationMap.end() &&
409               REntry != PropagationMap.end()) {
410
411      RPInfo = REntry->second;
412
413      if (RPInfo.IsVar) {
414        const VarDecl *Var = RPInfo.getVar();
415
416        PropagationMap.insert(PairType(Call,
417          PropagationInfo(StateMap->getState(Var))));
418
419        StateMap->setState(Var, consumed::CS_Consumed);
420
421      } else {
422        PropagationMap.insert(PairType(Call, RPInfo));
423      }
424    }
425
426  } else {
427
428    VisitCallExpr(Call);
429
430    InfoEntry Entry = PropagationMap.find(Call->getArg(0));
431
432    if (Entry != PropagationMap.end()) {
433      PropagationInfo PInfo = Entry->second;
434
435      checkCallability(PInfo, FunDecl, Call);
436
437      if (PInfo.IsVar) {
438        if (FunDecl->hasAttr<ConsumesAttr>()) {
439          // Handle consuming operators.
440          StateMap->setState(PInfo.getVar(), consumed::CS_Consumed);
441        } else if (const CXXMethodDecl *MethodDecl =
442          dyn_cast_or_null<CXXMethodDecl>(FunDecl)) {
443
444          // Handle non-constant member operators.
445          if (!MethodDecl->isConst())
446            StateMap->setState(PInfo.getVar(), consumed::CS_Unknown);
447        }
448      }
449    }
450  }
451}
452
453void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) {
454  if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
455    if (StateMap->getState(Var) != consumed::CS_None)
456      PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
457}
458
459void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) {
460  for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(),
461       DE = DeclS->decl_end(); DI != DE; ++DI) {
462
463    if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI));
464  }
465
466  if (DeclS->isSingleDecl())
467    if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl()))
468      PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
469}
470
471void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
472  const MaterializeTemporaryExpr *Temp) {
473
474  InfoEntry Entry = PropagationMap.find(Temp->GetTemporaryExpr());
475
476  if (Entry != PropagationMap.end())
477    PropagationMap.insert(PairType(Temp, Entry->second));
478}
479
480void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
481  forwardInfo(MExpr->getBase(), MExpr);
482}
483
484void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) {
485  if (UOp->getOpcode() == UO_AddrOf) {
486    InfoEntry Entry = PropagationMap.find(UOp->getSubExpr());
487
488    if (Entry != PropagationMap.end())
489      PropagationMap.insert(PairType(UOp, Entry->second));
490  }
491}
492
493void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
494  if (Analyzer.isConsumableType(Var->getType())) {
495    PropagationInfo PInfo =
496      PropagationMap.find(Var->getInit())->second;
497
498    StateMap->setState(Var, PInfo.IsVar ?
499      StateMap->getState(PInfo.getVar()) : PInfo.getState());
500  }
501}
502} // end anonymous::ConsumedStmtVisitor
503
504namespace {
505
506// TODO: Handle variable definitions, e.g. bool valid = x.isValid();
507//       if (valid) ...; (Deferred)
508class TestedVarsVisitor : public RecursiveASTVisitor<TestedVarsVisitor> {
509
510  bool Invert;
511  SourceLocation CurrTestLoc;
512
513  ConsumedStateMap *StateMap;
514
515public:
516  bool IsUsefulConditional;
517  VarTestResult Test;
518
519  TestedVarsVisitor(ConsumedStateMap *StateMap) : Invert(false),
520    StateMap(StateMap), IsUsefulConditional(false) {}
521
522  bool VisitCallExpr(CallExpr *Call);
523  bool VisitDeclRefExpr(DeclRefExpr *DeclRef);
524  bool VisitUnaryOperator(UnaryOperator *UnaryOp);
525};
526
527bool TestedVarsVisitor::VisitCallExpr(CallExpr *Call) {
528  if (const FunctionDecl *FunDecl =
529    dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
530
531    if (isTestingFunction(FunDecl)) {
532      CurrTestLoc = Call->getExprLoc();
533      IsUsefulConditional = true;
534      return true;
535    }
536
537    IsUsefulConditional = false;
538  }
539
540  return false;
541}
542
543bool TestedVarsVisitor::VisitDeclRefExpr(DeclRefExpr *DeclRef) {
544  if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
545    if (StateMap->getState(Var) != consumed::CS_None)
546      Test = VarTestResult(Var, CurrTestLoc, !Invert);
547
548  return true;
549}
550
551bool TestedVarsVisitor::VisitUnaryOperator(UnaryOperator *UnaryOp) {
552  if (UnaryOp->getOpcode() == UO_LNot) {
553    Invert = true;
554    TraverseStmt(UnaryOp->getSubExpr());
555
556  } else {
557    IsUsefulConditional = false;
558  }
559
560  return false;
561}
562} // end anonymouse::TestedVarsVisitor
563
564namespace clang {
565namespace consumed {
566
567void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
568                                ConsumedStateMap *StateMap,
569                                bool &AlreadyOwned) {
570
571  if (VisitedBlocks.alreadySet(Block)) return;
572
573  ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
574
575  if (Entry) {
576    Entry->intersect(StateMap);
577
578  } else if (AlreadyOwned) {
579    StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap);
580
581  } else {
582    StateMapsArray[Block->getBlockID()] = StateMap;
583    AlreadyOwned = true;
584  }
585}
586
587void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
588                                ConsumedStateMap *StateMap) {
589
590  if (VisitedBlocks.alreadySet(Block)) {
591    delete StateMap;
592    return;
593  }
594
595  ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
596
597  if (Entry) {
598    Entry->intersect(StateMap);
599    delete StateMap;
600
601  } else {
602    StateMapsArray[Block->getBlockID()] = StateMap;
603  }
604}
605
606ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
607  return StateMapsArray[Block->getBlockID()];
608}
609
610void ConsumedBlockInfo::markVisited(const CFGBlock *Block) {
611  VisitedBlocks.insert(Block);
612}
613
614ConsumedState ConsumedStateMap::getState(const VarDecl *Var) {
615  MapType::const_iterator Entry = Map.find(Var);
616
617  if (Entry != Map.end()) {
618    return Entry->second;
619
620  } else {
621    return CS_None;
622  }
623}
624
625void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
626  ConsumedState LocalState;
627
628  for (MapType::const_iterator DMI = Other->Map.begin(),
629       DME = Other->Map.end(); DMI != DME; ++DMI) {
630
631    LocalState = this->getState(DMI->first);
632
633    if (LocalState != CS_None && LocalState != DMI->second)
634      setState(DMI->first, CS_Unknown);
635  }
636}
637
638void ConsumedStateMap::makeUnknown() {
639  PairType Pair;
640
641  for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
642       ++DMI) {
643
644    Pair = *DMI;
645
646    Map.erase(Pair.first);
647    Map.insert(PairType(Pair.first, CS_Unknown));
648  }
649}
650
651void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
652  Map[Var] = State;
653}
654
655void ConsumedStateMap::remove(const VarDecl *Var) {
656  Map.erase(Var);
657}
658
659bool ConsumedAnalyzer::isConsumableType(QualType Type) {
660  const CXXRecordDecl *RD =
661    dyn_cast_or_null<CXXRecordDecl>(Type->getAsCXXRecordDecl());
662
663  if (!RD) return false;
664
665  std::pair<CacheMapType::iterator, bool> Entry =
666    ConsumableTypeCache.insert(std::make_pair(RD, false));
667
668  if (Entry.second)
669    Entry.first->second = hasConsumableAttributes(RD);
670
671  return Entry.first->second;
672}
673
674// TODO: Walk the base classes to see if any of them are unique types.
675//       (Deferred)
676bool ConsumedAnalyzer::hasConsumableAttributes(const CXXRecordDecl *RD) {
677  for (CXXRecordDecl::method_iterator MI = RD->method_begin(),
678       ME = RD->method_end(); MI != ME; ++MI) {
679
680    for (Decl::attr_iterator AI = (*MI)->attr_begin(), AE = (*MI)->attr_end();
681         AI != AE; ++AI) {
682
683      switch ((*AI)->getKind()) {
684      case attr::CallableWhenUnconsumed:
685      case attr::TestsUnconsumed:
686        return true;
687
688      default:
689        break;
690      }
691    }
692  }
693
694  return false;
695}
696
697// TODO: Handle other forms of branching with precision, including while- and
698//       for-loops. (Deferred)
699void ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
700                                  const IfStmt *Terminator) {
701
702  TestedVarsVisitor Visitor(CurrStates);
703  Visitor.TraverseStmt(const_cast<Expr*>(Terminator->getCond()));
704
705  bool HasElse = Terminator->getElse() != NULL;
706
707  ConsumedStateMap *ElseOrMergeStates = new ConsumedStateMap(*CurrStates);
708
709  if (Visitor.IsUsefulConditional) {
710    ConsumedState VarState = CurrStates->getState(Visitor.Test.Var);
711
712    if (VarState != CS_Unknown) {
713      // FIXME: Make this not warn if the test is from a macro expansion.
714      //        (Deferred)
715      WarningsHandler.warnUnnecessaryTest(Visitor.Test.Var->getNameAsString(),
716        stateToString(VarState), Visitor.Test.Loc);
717    }
718
719    if (Visitor.Test.UnconsumedInTrueBranch) {
720      CurrStates->setState(Visitor.Test.Var, CS_Unconsumed);
721      if (HasElse) ElseOrMergeStates->setState(Visitor.Test.Var, CS_Consumed);
722
723    } else {
724      CurrStates->setState(Visitor.Test.Var, CS_Consumed);
725      if (HasElse) ElseOrMergeStates->setState(Visitor.Test.Var, CS_Unconsumed);
726    }
727  }
728
729  CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
730
731  if (*SI)   BlockInfo.addInfo(*SI,        CurrStates);
732  if (*++SI) BlockInfo.addInfo(*SI, ElseOrMergeStates);
733}
734
735void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
736  const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
737
738  if (!D) return;
739
740  BlockInfo = ConsumedBlockInfo(AC.getCFG());
741
742  PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
743
744  CurrStates = new ConsumedStateMap();
745
746  // Visit all of the function's basic blocks.
747  for (PostOrderCFGView::iterator I = SortedGraph->begin(),
748       E = SortedGraph->end(); I != E; ++I) {
749
750    const CFGBlock *CurrBlock = *I;
751    BlockInfo.markVisited(CurrBlock);
752
753    if (CurrStates == NULL)
754      CurrStates = BlockInfo.getInfo(CurrBlock);
755
756    ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
757
758    // Visit all of the basic block's statements.
759    for (CFGBlock::const_iterator BI = CurrBlock->begin(),
760         BE = CurrBlock->end(); BI != BE; ++BI) {
761
762      switch (BI->getKind()) {
763      case CFGElement::Statement:
764        Visitor.Visit(BI->castAs<CFGStmt>().getStmt());
765        break;
766      case CFGElement::AutomaticObjectDtor:
767        CurrStates->remove(BI->castAs<CFGAutomaticObjDtor>().getVarDecl());
768      default:
769        break;
770      }
771    }
772
773    if (const IfStmt *Terminator =
774      dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
775
776      splitState(CurrBlock, Terminator);
777      CurrStates = NULL;
778
779    } else if (CurrBlock->succ_size() > 1) {
780      CurrStates->makeUnknown();
781
782      bool OwnershipTaken = false;
783
784      for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
785           SE = CurrBlock->succ_end(); SI != SE; ++SI) {
786
787        if (*SI) BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
788      }
789
790      if (!OwnershipTaken)
791        delete CurrStates;
792
793      CurrStates = NULL;
794
795    } else if (CurrBlock->succ_size() == 1 &&
796               (*CurrBlock->succ_begin())->pred_size() > 1) {
797
798      BlockInfo.addInfo(*CurrBlock->succ_begin(), CurrStates);
799      CurrStates = NULL;
800    }
801
802    Visitor.reset();
803  } // End of block iterator.
804
805  // Delete the last existing state map.
806  delete CurrStates;
807
808  WarningsHandler.emitDiagnostics();
809}
810}} // end namespace clang::consumed
811