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