xref: /llvm-project/clang/lib/Analysis/Consumed.cpp (revision c2ecf0d815450b8a4c8ff3f9f78ecd9bd29b57ab) 
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 
44 using namespace clang;
45 using namespace consumed;
46 
47 // Key method definition
48 ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
49 
50 static bool isTestingFunction(const FunctionDecl *FunDecl) {
51   return FunDecl->hasAttr<TestsUnconsumedAttr>();
52 }
53 
54 static 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 
71 namespace {
72 class 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 &PState,
112                         const FunctionDecl *FunDecl,
113                         const CallExpr *Call);
114   void forwardInfo(const Stmt *From, const Stmt *To);
115   bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
116 
117 public:
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)
145 void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PState,
146                                            const FunctionDecl *FunDecl,
147                                            const CallExpr *Call) {
148 
149   if (!FunDecl->hasAttr<CallableWhenUnconsumedAttr>()) return;
150 
151   if (PState.IsVar) {
152     const VarDecl *Var = PState.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 (PState.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 
191 void 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 
199 bool 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 
208 void 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 
220 void 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 
230 void 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 PState = Entry->second;
258 
259       if (ParamType->isRValueReferenceType() ||
260           (ParamType->isLValueReferenceType() &&
261            !cast<LValueReferenceType>(*ParamType).isSpelledAsLValue())) {
262 
263         StateMap->setState(PState.getVar(), consumed::CS_Consumed);
264 
265       } else if (!(ParamType.isConstQualified() ||
266                    ((ParamType->isReferenceType() ||
267                      ParamType->isPointerType()) &&
268                     ParamType->getPointeeType().isConstQualified()))) {
269 
270         StateMap->setState(PState.getVar(), consumed::CS_Unknown);
271       }
272     }
273   }
274 }
275 
276 void 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 
283 void 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 PState =
299         PropagationMap.find(Call->getArg(0))->second;
300 
301       if (PState.IsVar) {
302         const VarDecl* Var = PState.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, PState));
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 
326 void 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 PState = Entry->second;
335     const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
336 
337     checkCallability(PState, MethodDecl, Call);
338 
339     if (PState.IsVar) {
340       if (MethodDecl->hasAttr<ConsumesAttr>())
341         StateMap->setState(PState.getVar(), consumed::CS_Consumed);
342       else if (!MethodDecl->isConst())
343         StateMap->setState(PState.getVar(), consumed::CS_Unknown);
344     }
345   }
346 }
347 
348 void 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 LPState, RPState;
363 
364     if (LEntry != PropagationMap.end() &&
365         REntry != PropagationMap.end()) {
366 
367       LPState = LEntry->second;
368       RPState = REntry->second;
369 
370       if (LPState.IsVar && RPState.IsVar) {
371         StateMap->setState(LPState.getVar(),
372           StateMap->getState(RPState.getVar()));
373 
374         StateMap->setState(RPState.getVar(), consumed::CS_Consumed);
375 
376         PropagationMap.insert(PairType(Call, LPState));
377 
378       } else if (LPState.IsVar && !RPState.IsVar) {
379         StateMap->setState(LPState.getVar(), RPState.getState());
380 
381         PropagationMap.insert(PairType(Call, LPState));
382 
383       } else if (!LPState.IsVar && RPState.IsVar) {
384         PropagationMap.insert(PairType(Call,
385           PropagationInfo(StateMap->getState(RPState.getVar()))));
386 
387         StateMap->setState(RPState.getVar(), consumed::CS_Consumed);
388 
389       } else {
390         PropagationMap.insert(PairType(Call, RPState));
391       }
392 
393     } else if (LEntry != PropagationMap.end() &&
394                REntry == PropagationMap.end()) {
395 
396       LPState = LEntry->second;
397 
398       if (LPState.IsVar) {
399         StateMap->setState(LPState.getVar(), consumed::CS_Unknown);
400 
401         PropagationMap.insert(PairType(Call, LPState));
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       RPState = REntry->second;
412 
413       if (RPState.IsVar) {
414         const VarDecl *Var = RPState.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, RPState));
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 PState = Entry->second;
434 
435       checkCallability(PState, FunDecl, Call);
436 
437       if (PState.IsVar) {
438         if (FunDecl->hasAttr<ConsumesAttr>()) {
439           // Handle consuming operators.
440           StateMap->setState(PState.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(PState.getVar(), consumed::CS_Unknown);
447         }
448       }
449     }
450   }
451 }
452 
453 void 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 
459 void 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 
471 void 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 
480 void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
481   forwardInfo(MExpr->getBase(), MExpr);
482 }
483 
484 void 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 
493 void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
494   if (Analyzer.isConsumableType(Var->getType())) {
495     PropagationInfo PState =
496       PropagationMap.find(Var->getInit())->second;
497 
498     StateMap->setState(Var, PState.IsVar ?
499       StateMap->getState(PState.getVar()) : PState.getState());
500   }
501 }
502 } // end anonymous::ConsumedStmtVisitor
503 
504 namespace {
505 
506 // TODO: Handle variable definitions, e.g. bool valid = x.isValid();
507 //       if (valid) ...; (Deferred)
508 class TestedVarsVisitor : public RecursiveASTVisitor<TestedVarsVisitor> {
509 
510   bool Invert;
511   SourceLocation CurrTestLoc;
512 
513   ConsumedStateMap *StateMap;
514 
515 public:
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 
527 bool 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 
543 bool 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 
551 bool 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 
564 namespace clang {
565 namespace consumed {
566 
567 void 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 
587 void 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 
606 ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
607   return StateMapsArray[Block->getBlockID()];
608 }
609 
610 void ConsumedBlockInfo::markVisited(const CFGBlock *Block) {
611   VisitedBlocks.insert(Block);
612 }
613 
614 ConsumedState 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 
625 void 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 
638 void 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 
651 void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
652   Map[Var] = State;
653 }
654 
655 void ConsumedStateMap::remove(const VarDecl *Var) {
656   Map.erase(Var);
657 }
658 
659 bool 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)
676 bool 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)
699 void 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 
735 void 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