contrib/llvm/tools/clang/lib/Analysis/Consumed.cpp

   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/OwningPtr.h"
  31 #include "llvm/ADT/SmallVector.h"
  32 #include "llvm/Support/Compiler.h"
  33 #include "llvm/Support/raw_ostream.h"
  34
  35 // TODO: Adjust states of args to constructors in the same way that arguments to
  36 //       function calls are handled.
  37 // TODO: Use information from tests in for- and while-loop conditional.
  38 // TODO: Add notes about the actual and expected state for
  39 // TODO: Correctly identify unreachable blocks when chaining boolean operators.
  40 // TODO: Adjust the parser and AttributesList class to support lists of
  41 //       identifiers.
  42 // TODO: Warn about unreachable code.
  43 // TODO: Switch to using a bitmap to track unreachable blocks.
  44 // TODO: Handle variable definitions, e.g. bool valid = x.isValid();
  45 //       if (valid) ...; (Deferred)
  46 // TODO: Take notes on state transitions to provide better warning messages.
  47 //       (Deferred)
  48 // TODO: Test nested conditionals: A) Checking the same value multiple times,
  49 //       and 2) Checking different values. (Deferred)
  50
  51 using namespace clang;
  52 using namespace consumed;
  53
  54 // Key method definition
  55 ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
  56
  57 static SourceLocation getFirstStmtLoc(const CFGBlock *Block) {
  58   // Find the source location of the first statement in the block, if the block
  59   // is not empty.
  60   for (CFGBlock::const_iterator BI = Block->begin(), BE = Block->end();
  61        BI != BE; ++BI) {
  62     if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
  63       return CS->getStmt()->getLocStart();
  64   }
  65
  66   // Block is empty.
  67   // If we have one successor, return the first statement in that block
  68   if (Block->succ_size() == 1 && *Block->succ_begin())
  69     return getFirstStmtLoc(*Block->succ_begin());
  70
  71   return SourceLocation();
  72 }
  73
  74 static SourceLocation getLastStmtLoc(const CFGBlock *Block) {
  75   // Find the source location of the last statement in the block, if the block
  76   // is not empty.
  77   if (const Stmt *StmtNode = Block->getTerminator()) {
  78     return StmtNode->getLocStart();
  79   } else {
  80     for (CFGBlock::const_reverse_iterator BI = Block->rbegin(),
  81          BE = Block->rend(); BI != BE; ++BI) {
  82       if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
  83         return CS->getStmt()->getLocStart();
  84     }
  85   }
  86
  87   // If we have one successor, return the first statement in that block
  88   SourceLocation Loc;
  89   if (Block->succ_size() == 1 && *Block->succ_begin())
  90     Loc = getFirstStmtLoc(*Block->succ_begin());
  91   if (Loc.isValid())
  92     return Loc;
  93
  94   // If we have one predecessor, return the last statement in that block
  95   if (Block->pred_size() == 1 && *Block->pred_begin())
  96     return getLastStmtLoc(*Block->pred_begin());
  97
  98   return Loc;
  99 }
 100
 101 static ConsumedState invertConsumedUnconsumed(ConsumedState State) {
 102   switch (State) {
 103   case CS_Unconsumed:
 104     return CS_Consumed;
 105   case CS_Consumed:
 106     return CS_Unconsumed;
 107   case CS_None:
 108     return CS_None;
 109   case CS_Unknown:
 110     return CS_Unknown;
 111   }
 112   llvm_unreachable("invalid enum");
 113 }
 114
 115 static bool isCallableInState(const CallableWhenAttr *CWAttr,
 116                               ConsumedState State) {
 117
 118   CallableWhenAttr::callableState_iterator I = CWAttr->callableState_begin(),
 119                                            E = CWAttr->callableState_end();
 120
 121   for (; I != E; ++I) {
 122
 123     ConsumedState MappedAttrState = CS_None;
 124
 125     switch (*I) {
 126     case CallableWhenAttr::Unknown:
 127       MappedAttrState = CS_Unknown;
 128       break;
 129
 130     case CallableWhenAttr::Unconsumed:
 131       MappedAttrState = CS_Unconsumed;
 132       break;
 133
 134     case CallableWhenAttr::Consumed:
 135       MappedAttrState = CS_Consumed;
 136       break;
 137     }
 138
 139     if (MappedAttrState == State)
 140       return true;
 141   }
 142
 143   return false;
 144 }
 145
 146 static bool isConsumableType(const QualType &QT) {
 147   if (QT->isPointerType() || QT->isReferenceType())
 148     return false;
 149
 150   if (const CXXRecordDecl *RD = QT->getAsCXXRecordDecl())
 151     return RD->hasAttr<ConsumableAttr>();
 152
 153   return false;
 154 }
 155
 156 static bool isKnownState(ConsumedState State) {
 157   switch (State) {
 158   case CS_Unconsumed:
 159   case CS_Consumed:
 160     return true;
 161   case CS_None:
 162   case CS_Unknown:
 163     return false;
 164   }
 165   llvm_unreachable("invalid enum");
 166 }
 167
 168 static bool isRValueRefish(QualType ParamType) {
 169   return ParamType->isRValueReferenceType() ||
 170         (ParamType->isLValueReferenceType() &&
 171          !cast<LValueReferenceType>(
 172            ParamType.getCanonicalType())->isSpelledAsLValue());
 173 }
 174
 175 static bool isTestingFunction(const FunctionDecl *FunDecl) {
 176   return FunDecl->hasAttr<TestTypestateAttr>();
 177 }
 178
 179 static bool isValueType(QualType ParamType) {
 180   return !(ParamType->isPointerType() || ParamType->isReferenceType());
 181 }
 182
 183 static ConsumedState mapConsumableAttrState(const QualType QT) {
 184   assert(isConsumableType(QT));
 185
 186   const ConsumableAttr *CAttr =
 187       QT->getAsCXXRecordDecl()->getAttr<ConsumableAttr>();
 188
 189   switch (CAttr->getDefaultState()) {
 190   case ConsumableAttr::Unknown:
 191     return CS_Unknown;
 192   case ConsumableAttr::Unconsumed:
 193     return CS_Unconsumed;
 194   case ConsumableAttr::Consumed:
 195     return CS_Consumed;
 196   }
 197   llvm_unreachable("invalid enum");
 198 }
 199
 200 static ConsumedState
 201 mapParamTypestateAttrState(const ParamTypestateAttr *PTAttr) {
 202   switch (PTAttr->getParamState()) {
 203   case ParamTypestateAttr::Unknown:
 204     return CS_Unknown;
 205   case ParamTypestateAttr::Unconsumed:
 206     return CS_Unconsumed;
 207   case ParamTypestateAttr::Consumed:
 208     return CS_Consumed;
 209   }
 210   llvm_unreachable("invalid_enum");
 211 }
 212
 213 static ConsumedState
 214 mapReturnTypestateAttrState(const ReturnTypestateAttr *RTSAttr) {
 215   switch (RTSAttr->getState()) {
 216   case ReturnTypestateAttr::Unknown:
 217     return CS_Unknown;
 218   case ReturnTypestateAttr::Unconsumed:
 219     return CS_Unconsumed;
 220   case ReturnTypestateAttr::Consumed:
 221     return CS_Consumed;
 222   }
 223   llvm_unreachable("invalid enum");
 224 }
 225
 226 static ConsumedState mapSetTypestateAttrState(const SetTypestateAttr *STAttr) {
 227   switch (STAttr->getNewState()) {
 228   case SetTypestateAttr::Unknown:
 229     return CS_Unknown;
 230   case SetTypestateAttr::Unconsumed:
 231     return CS_Unconsumed;
 232   case SetTypestateAttr::Consumed:
 233     return CS_Consumed;
 234   }
 235   llvm_unreachable("invalid_enum");
 236 }
 237
 238 static StringRef stateToString(ConsumedState State) {
 239   switch (State) {
 240   case consumed::CS_None:
 241     return "none";
 242
 243   case consumed::CS_Unknown:
 244     return "unknown";
 245
 246   case consumed::CS_Unconsumed:
 247     return "unconsumed";
 248
 249   case consumed::CS_Consumed:
 250     return "consumed";
 251   }
 252   llvm_unreachable("invalid enum");
 253 }
 254
 255 static ConsumedState testsFor(const FunctionDecl *FunDecl) {
 256   assert(isTestingFunction(FunDecl));
 257   switch (FunDecl->getAttr<TestTypestateAttr>()->getTestState()) {
 258   case TestTypestateAttr::Unconsumed:
 259     return CS_Unconsumed;
 260   case TestTypestateAttr::Consumed:
 261     return CS_Consumed;
 262   }
 263   llvm_unreachable("invalid enum");
 264 }
 265
 266 namespace {
 267 struct VarTestResult {
 268   const VarDecl *Var;
 269   ConsumedState TestsFor;
 270 };
 271 } // end anonymous::VarTestResult
 272
 273 namespace clang {
 274 namespace consumed {
 275
 276 enum EffectiveOp {
 277   EO_And,
 278   EO_Or
 279 };
 280
 281 class PropagationInfo {
 282   enum {
 283     IT_None,
 284     IT_State,
 285     IT_VarTest,
 286     IT_BinTest,
 287     IT_Var,
 288     IT_Tmp
 289   } InfoType;
 290
 291   struct BinTestTy {
 292     const BinaryOperator *Source;
 293     EffectiveOp EOp;
 294     VarTestResult LTest;
 295     VarTestResult RTest;
 296   };
 297
 298   union {
 299     ConsumedState State;
 300     VarTestResult VarTest;
 301     const VarDecl *Var;
 302     const CXXBindTemporaryExpr *Tmp;
 303     BinTestTy BinTest;
 304   };
 305
 306 public:
 307   PropagationInfo() : InfoType(IT_None) {}
 308
 309   PropagationInfo(const VarTestResult &VarTest)
 310     : InfoType(IT_VarTest), VarTest(VarTest) {}
 311
 312   PropagationInfo(const VarDecl *Var, ConsumedState TestsFor)
 313     : InfoType(IT_VarTest) {
 314
 315     VarTest.Var      = Var;
 316     VarTest.TestsFor = TestsFor;
 317   }
 318
 319   PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
 320                   const VarTestResult &LTest, const VarTestResult &RTest)
 321     : InfoType(IT_BinTest) {
 322
 323     BinTest.Source  = Source;
 324     BinTest.EOp     = EOp;
 325     BinTest.LTest   = LTest;
 326     BinTest.RTest   = RTest;
 327   }
 328
 329   PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp,
 330                   const VarDecl *LVar, ConsumedState LTestsFor,
 331                   const VarDecl *RVar, ConsumedState RTestsFor)
 332     : InfoType(IT_BinTest) {
 333
 334     BinTest.Source         = Source;
 335     BinTest.EOp            = EOp;
 336     BinTest.LTest.Var      = LVar;
 337     BinTest.LTest.TestsFor = LTestsFor;
 338     BinTest.RTest.Var      = RVar;
 339     BinTest.RTest.TestsFor = RTestsFor;
 340   }
 341
 342   PropagationInfo(ConsumedState State)
 343     : InfoType(IT_State), State(State) {}
 344
 345   PropagationInfo(const VarDecl *Var) : InfoType(IT_Var), Var(Var) {}
 346   PropagationInfo(const CXXBindTemporaryExpr *Tmp)
 347     : InfoType(IT_Tmp), Tmp(Tmp) {}
 348
 349   const ConsumedState & getState() const {
 350     assert(InfoType == IT_State);
 351     return State;
 352   }
 353
 354   const VarTestResult & getVarTest() const {
 355     assert(InfoType == IT_VarTest);
 356     return VarTest;
 357   }
 358
 359   const VarTestResult & getLTest() const {
 360     assert(InfoType == IT_BinTest);
 361     return BinTest.LTest;
 362   }
 363
 364   const VarTestResult & getRTest() const {
 365     assert(InfoType == IT_BinTest);
 366     return BinTest.RTest;
 367   }
 368
 369   const VarDecl * getVar() const {
 370     assert(InfoType == IT_Var);
 371     return Var;
 372   }
 373
 374   const CXXBindTemporaryExpr * getTmp() const {
 375     assert(InfoType == IT_Tmp);
 376     return Tmp;
 377   }
 378
 379   ConsumedState getAsState(const ConsumedStateMap *StateMap) const {
 380     assert(isVar() || isTmp() || isState());
 381
 382     if (isVar())
 383       return StateMap->getState(Var);
 384     else if (isTmp())
 385       return StateMap->getState(Tmp);
 386     else if (isState())
 387       return State;
 388     else
 389       return CS_None;
 390   }
 391
 392   EffectiveOp testEffectiveOp() const {
 393     assert(InfoType == IT_BinTest);
 394     return BinTest.EOp;
 395   }
 396
 397   const BinaryOperator * testSourceNode() const {
 398     assert(InfoType == IT_BinTest);
 399     return BinTest.Source;
 400   }
 401
 402   inline bool isValid()   const { return InfoType != IT_None;    }
 403   inline bool isState()   const { return InfoType == IT_State;   }
 404   inline bool isVarTest() const { return InfoType == IT_VarTest; }
 405   inline bool isBinTest() const { return InfoType == IT_BinTest; }
 406   inline bool isVar()     const { return InfoType == IT_Var;     }
 407   inline bool isTmp()     const { return InfoType == IT_Tmp;     }
 408
 409   bool isTest() const {
 410     return InfoType == IT_VarTest || InfoType == IT_BinTest;
 411   }
 412
 413   bool isPointerToValue() const {
 414     return InfoType == IT_Var || InfoType == IT_Tmp;
 415   }
 416
 417   PropagationInfo invertTest() const {
 418     assert(InfoType == IT_VarTest || InfoType == IT_BinTest);
 419
 420     if (InfoType == IT_VarTest) {
 421       return PropagationInfo(VarTest.Var,
 422                              invertConsumedUnconsumed(VarTest.TestsFor));
 423
 424     } else if (InfoType == IT_BinTest) {
 425       return PropagationInfo(BinTest.Source,
 426         BinTest.EOp == EO_And ? EO_Or : EO_And,
 427         BinTest.LTest.Var, invertConsumedUnconsumed(BinTest.LTest.TestsFor),
 428         BinTest.RTest.Var, invertConsumedUnconsumed(BinTest.RTest.TestsFor));
 429     } else {
 430       return PropagationInfo();
 431     }
 432   }
 433 };
 434
 435 static inline void
 436 setStateForVarOrTmp(ConsumedStateMap *StateMap, const PropagationInfo &PInfo,
 437                     ConsumedState State) {
 438
 439   assert(PInfo.isVar() || PInfo.isTmp());
 440
 441   if (PInfo.isVar())
 442     StateMap->setState(PInfo.getVar(), State);
 443   else
 444     StateMap->setState(PInfo.getTmp(), State);
 445 }
 446
 447 class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> {
 448
 449   typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType;
 450   typedef std::pair<const Stmt *, PropagationInfo> PairType;
 451   typedef MapType::iterator InfoEntry;
 452   typedef MapType::const_iterator ConstInfoEntry;
 453
 454   AnalysisDeclContext &AC;
 455   ConsumedAnalyzer &Analyzer;
 456   ConsumedStateMap *StateMap;
 457   MapType PropagationMap;
 458   void forwardInfo(const Stmt *From, const Stmt *To);
 459   bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl);
 460   void propagateReturnType(const Stmt *Call, const FunctionDecl *Fun,
 461                            QualType ReturnType);
 462
 463 public:
 464   void checkCallability(const PropagationInfo &PInfo,
 465                         const FunctionDecl *FunDecl,
 466                         SourceLocation BlameLoc);
 467
 468   void VisitBinaryOperator(const BinaryOperator *BinOp);
 469   void VisitCallExpr(const CallExpr *Call);
 470   void VisitCastExpr(const CastExpr *Cast);
 471   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *Temp);
 472   void VisitCXXConstructExpr(const CXXConstructExpr *Call);
 473   void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call);
 474   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call);
 475   void VisitDeclRefExpr(const DeclRefExpr *DeclRef);
 476   void VisitDeclStmt(const DeclStmt *DelcS);
 477   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp);
 478   void VisitMemberExpr(const MemberExpr *MExpr);
 479   void VisitParmVarDecl(const ParmVarDecl *Param);
 480   void VisitReturnStmt(const ReturnStmt *Ret);
 481   void VisitUnaryOperator(const UnaryOperator *UOp);
 482   void VisitVarDecl(const VarDecl *Var);
 483
 484   ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer,
 485                       ConsumedStateMap *StateMap)
 486       : AC(AC), Analyzer(Analyzer), StateMap(StateMap) {}
 487
 488   PropagationInfo getInfo(const Stmt *StmtNode) const {
 489     ConstInfoEntry Entry = PropagationMap.find(StmtNode);
 490
 491     if (Entry != PropagationMap.end())
 492       return Entry->second;
 493     else
 494       return PropagationInfo();
 495   }
 496
 497   void reset(ConsumedStateMap *NewStateMap) {
 498     StateMap = NewStateMap;
 499   }
 500 };
 501
 502 void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo,
 503                                            const FunctionDecl *FunDecl,
 504                                            SourceLocation BlameLoc) {
 505   assert(!PInfo.isTest());
 506
 507   if (!FunDecl->hasAttr<CallableWhenAttr>())
 508     return;
 509
 510   const CallableWhenAttr *CWAttr = FunDecl->getAttr<CallableWhenAttr>();
 511
 512   if (PInfo.isVar()) {
 513     ConsumedState VarState = StateMap->getState(PInfo.getVar());
 514
 515     if (VarState == CS_None || isCallableInState(CWAttr, VarState))
 516       return;
 517
 518     Analyzer.WarningsHandler.warnUseInInvalidState(
 519       FunDecl->getNameAsString(), PInfo.getVar()->getNameAsString(),
 520       stateToString(VarState), BlameLoc);
 521
 522   } else {
 523     ConsumedState TmpState = PInfo.getAsState(StateMap);
 524
 525     if (TmpState == CS_None || isCallableInState(CWAttr, TmpState))
 526       return;
 527
 528     Analyzer.WarningsHandler.warnUseOfTempInInvalidState(
 529       FunDecl->getNameAsString(), stateToString(TmpState), BlameLoc);
 530   }
 531 }
 532
 533 void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) {
 534   InfoEntry Entry = PropagationMap.find(From);
 535
 536   if (Entry != PropagationMap.end())
 537     PropagationMap.insert(PairType(To, Entry->second));
 538 }
 539
 540 bool ConsumedStmtVisitor::isLikeMoveAssignment(
 541   const CXXMethodDecl *MethodDecl) {
 542
 543   return MethodDecl->isMoveAssignmentOperator() ||
 544          (MethodDecl->getOverloadedOperator() == OO_Equal &&
 545           MethodDecl->getNumParams() == 1 &&
 546           MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType());
 547 }
 548
 549 void ConsumedStmtVisitor::propagateReturnType(const Stmt *Call,
 550                                               const FunctionDecl *Fun,
 551                                               QualType ReturnType) {
 552   if (isConsumableType(ReturnType)) {
 553
 554     ConsumedState ReturnState;
 555
 556     if (Fun->hasAttr<ReturnTypestateAttr>())
 557       ReturnState = mapReturnTypestateAttrState(
 558         Fun->getAttr<ReturnTypestateAttr>());
 559     else
 560       ReturnState = mapConsumableAttrState(ReturnType);
 561
 562     PropagationMap.insert(PairType(Call, PropagationInfo(ReturnState)));
 563   }
 564 }
 565
 566 void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) {
 567   switch (BinOp->getOpcode()) {
 568   case BO_LAnd:
 569   case BO_LOr : {
 570     InfoEntry LEntry = PropagationMap.find(BinOp->getLHS()),
 571               REntry = PropagationMap.find(BinOp->getRHS());
 572
 573     VarTestResult LTest, RTest;
 574
 575     if (LEntry != PropagationMap.end() && LEntry->second.isVarTest()) {
 576       LTest = LEntry->second.getVarTest();
 577
 578     } else {
 579       LTest.Var      = NULL;
 580       LTest.TestsFor = CS_None;
 581     }
 582
 583     if (REntry != PropagationMap.end() && REntry->second.isVarTest()) {
 584       RTest = REntry->second.getVarTest();
 585
 586     } else {
 587       RTest.Var      = NULL;
 588       RTest.TestsFor = CS_None;
 589     }
 590
 591     if (!(LTest.Var == NULL && RTest.Var == NULL))
 592       PropagationMap.insert(PairType(BinOp, PropagationInfo(BinOp,
 593         static_cast<EffectiveOp>(BinOp->getOpcode() == BO_LOr), LTest, RTest)));
 594
 595     break;
 596   }
 597
 598   case BO_PtrMemD:
 599   case BO_PtrMemI:
 600     forwardInfo(BinOp->getLHS(), BinOp);
 601     break;
 602
 603   default:
 604     break;
 605   }
 606 }
 607
 608 static bool isStdNamespace(const DeclContext *DC) {
 609   if (!DC->isNamespace()) return false;
 610   while (DC->getParent()->isNamespace())
 611     DC = DC->getParent();
 612   const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC);
 613
 614   return ND && ND->getName() == "std" &&
 615          ND->getDeclContext()->isTranslationUnit();
 616 }
 617
 618 void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) {
 619   if (const FunctionDecl *FunDecl =
 620     dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) {
 621
 622     // Special case for the std::move function.
 623     // TODO: Make this more specific. (Deferred)
 624     if (Call->getNumArgs() == 1 &&
 625         FunDecl->getNameAsString() == "move" &&
 626         isStdNamespace(FunDecl->getDeclContext())) {
 627       forwardInfo(Call->getArg(0), Call);
 628       return;
 629     }
 630
 631     unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams();
 632
 633     for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) {
 634       const ParmVarDecl *Param = FunDecl->getParamDecl(Index - Offset);
 635       QualType ParamType = Param->getType();
 636
 637       InfoEntry Entry = PropagationMap.find(Call->getArg(Index));
 638
 639       if (Entry == PropagationMap.end() || Entry->second.isTest())
 640         continue;
 641
 642       PropagationInfo PInfo = Entry->second;
 643
 644       // Check that the parameter is in the correct state.
 645
 646       if (Param->hasAttr<ParamTypestateAttr>()) {
 647         ConsumedState ParamState = PInfo.getAsState(StateMap);
 648
 649         ConsumedState ExpectedState =
 650           mapParamTypestateAttrState(Param->getAttr<ParamTypestateAttr>());
 651
 652         if (ParamState != ExpectedState)
 653           Analyzer.WarningsHandler.warnParamTypestateMismatch(
 654             Call->getArg(Index - Offset)->getExprLoc(),
 655             stateToString(ExpectedState), stateToString(ParamState));
 656       }
 657
 658       if (!(Entry->second.isVar() || Entry->second.isTmp()))
 659         continue;
 660
 661       // Adjust state on the caller side.
 662
 663       if (isRValueRefish(ParamType)) {
 664         setStateForVarOrTmp(StateMap, PInfo, consumed::CS_Consumed);
 665
 666       } else if (Param->hasAttr<ReturnTypestateAttr>()) {
 667         setStateForVarOrTmp(StateMap, PInfo,
 668           mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>()));
 669
 670       } else if (!isValueType(ParamType) &&
 671                  !ParamType->getPointeeType().isConstQualified()) {
 672
 673         setStateForVarOrTmp(StateMap, PInfo, consumed::CS_Unknown);
 674       }
 675     }
 676
 677     QualType RetType = FunDecl->getCallResultType();
 678     if (RetType->isReferenceType())
 679       RetType = RetType->getPointeeType();
 680
 681     propagateReturnType(Call, FunDecl, RetType);
 682   }
 683 }
 684
 685 void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) {
 686   forwardInfo(Cast->getSubExpr(), Cast);
 687 }
 688
 689 void ConsumedStmtVisitor::VisitCXXBindTemporaryExpr(
 690   const CXXBindTemporaryExpr *Temp) {
 691
 692   InfoEntry Entry = PropagationMap.find(Temp->getSubExpr());
 693
 694   if (Entry != PropagationMap.end() && !Entry->second.isTest()) {
 695     StateMap->setState(Temp, Entry->second.getAsState(StateMap));
 696     PropagationMap.insert(PairType(Temp, PropagationInfo(Temp)));
 697   }
 698 }
 699
 700 void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) {
 701   CXXConstructorDecl *Constructor = Call->getConstructor();
 702
 703   ASTContext &CurrContext = AC.getASTContext();
 704   QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType();
 705
 706   if (!isConsumableType(ThisType))
 707     return;
 708
 709   // FIXME: What should happen if someone annotates the move constructor?
 710   if (Constructor->hasAttr<ReturnTypestateAttr>()) {
 711     // TODO: Adjust state of args appropriately.
 712
 713     ReturnTypestateAttr *RTAttr = Constructor->getAttr<ReturnTypestateAttr>();
 714     ConsumedState RetState = mapReturnTypestateAttrState(RTAttr);
 715     PropagationMap.insert(PairType(Call, PropagationInfo(RetState)));
 716
 717   } else if (Constructor->isDefaultConstructor()) {
 718
 719     PropagationMap.insert(PairType(Call,
 720       PropagationInfo(consumed::CS_Consumed)));
 721
 722   } else if (Constructor->isMoveConstructor()) {
 723
 724     InfoEntry Entry = PropagationMap.find(Call->getArg(0));
 725
 726     if (Entry != PropagationMap.end()) {
 727       PropagationInfo PInfo = Entry->second;
 728
 729       if (PInfo.isVar()) {
 730         const VarDecl* Var = PInfo.getVar();
 731
 732         PropagationMap.insert(PairType(Call,
 733           PropagationInfo(StateMap->getState(Var))));
 734
 735         StateMap->setState(Var, consumed::CS_Consumed);
 736
 737       } else if (PInfo.isTmp()) {
 738         const CXXBindTemporaryExpr *Tmp = PInfo.getTmp();
 739
 740         PropagationMap.insert(PairType(Call,
 741           PropagationInfo(StateMap->getState(Tmp))));
 742
 743         StateMap->setState(Tmp, consumed::CS_Consumed);
 744
 745       } else {
 746         PropagationMap.insert(PairType(Call, PInfo));
 747       }
 748     }
 749   } else if (Constructor->isCopyConstructor()) {
 750     forwardInfo(Call->getArg(0), Call);
 751
 752   } else {
 753     // TODO: Adjust state of args appropriately.
 754
 755     ConsumedState RetState = mapConsumableAttrState(ThisType);
 756     PropagationMap.insert(PairType(Call, PropagationInfo(RetState)));
 757   }
 758 }
 759
 760 void ConsumedStmtVisitor::VisitCXXMemberCallExpr(
 761   const CXXMemberCallExpr *Call) {
 762
 763   VisitCallExpr(Call);
 764
 765   InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens());
 766
 767   if (Entry != PropagationMap.end()) {
 768     PropagationInfo PInfo = Entry->second;
 769     const CXXMethodDecl *MethodDecl = Call->getMethodDecl();
 770
 771     checkCallability(PInfo, MethodDecl, Call->getExprLoc());
 772
 773     if (PInfo.isVar()) {
 774       if (isTestingFunction(MethodDecl))
 775         PropagationMap.insert(PairType(Call,
 776           PropagationInfo(PInfo.getVar(), testsFor(MethodDecl))));
 777       else if (MethodDecl->hasAttr<SetTypestateAttr>())
 778         StateMap->setState(PInfo.getVar(),
 779           mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>()));
 780     } else if (PInfo.isTmp() && MethodDecl->hasAttr<SetTypestateAttr>()) {
 781       StateMap->setState(PInfo.getTmp(),
 782         mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>()));
 783     }
 784   }
 785 }
 786
 787 void ConsumedStmtVisitor::VisitCXXOperatorCallExpr(
 788   const CXXOperatorCallExpr *Call) {
 789
 790   const FunctionDecl *FunDecl =
 791     dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee());
 792
 793   if (!FunDecl) return;
 794
 795   if (isa<CXXMethodDecl>(FunDecl) &&
 796       isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) {
 797
 798     InfoEntry LEntry = PropagationMap.find(Call->getArg(0));
 799     InfoEntry REntry = PropagationMap.find(Call->getArg(1));
 800
 801     PropagationInfo LPInfo, RPInfo;
 802
 803     if (LEntry != PropagationMap.end() &&
 804         REntry != PropagationMap.end()) {
 805
 806       LPInfo = LEntry->second;
 807       RPInfo = REntry->second;
 808
 809       if (LPInfo.isPointerToValue() && RPInfo.isPointerToValue()) {
 810         setStateForVarOrTmp(StateMap, LPInfo, RPInfo.getAsState(StateMap));
 811         PropagationMap.insert(PairType(Call, LPInfo));
 812         setStateForVarOrTmp(StateMap, RPInfo, consumed::CS_Consumed);
 813
 814       } else if (RPInfo.isState()) {
 815         setStateForVarOrTmp(StateMap, LPInfo, RPInfo.getState());
 816         PropagationMap.insert(PairType(Call, LPInfo));
 817
 818       } else {
 819         setStateForVarOrTmp(StateMap, RPInfo, consumed::CS_Consumed);
 820       }
 821
 822     } else if (LEntry != PropagationMap.end() &&
 823                REntry == PropagationMap.end()) {
 824
 825       LPInfo = LEntry->second;
 826
 827       assert(!LPInfo.isTest());
 828
 829       if (LPInfo.isPointerToValue()) {
 830         setStateForVarOrTmp(StateMap, LPInfo, consumed::CS_Unknown);
 831         PropagationMap.insert(PairType(Call, LPInfo));
 832
 833       } else {
 834         PropagationMap.insert(PairType(Call,
 835           PropagationInfo(consumed::CS_Unknown)));
 836       }
 837
 838     } else if (LEntry == PropagationMap.end() &&
 839                REntry != PropagationMap.end()) {
 840
 841       RPInfo = REntry->second;
 842
 843       if (RPInfo.isPointerToValue())
 844         setStateForVarOrTmp(StateMap, RPInfo, consumed::CS_Consumed);
 845     }
 846
 847   } else {
 848
 849     VisitCallExpr(Call);
 850
 851     InfoEntry Entry = PropagationMap.find(Call->getArg(0));
 852
 853     if (Entry != PropagationMap.end()) {
 854       PropagationInfo PInfo = Entry->second;
 855
 856       checkCallability(PInfo, FunDecl, Call->getExprLoc());
 857
 858       if (PInfo.isVar()) {
 859         if (isTestingFunction(FunDecl))
 860           PropagationMap.insert(PairType(Call,
 861             PropagationInfo(PInfo.getVar(), testsFor(FunDecl))));
 862         else if (FunDecl->hasAttr<SetTypestateAttr>())
 863           StateMap->setState(PInfo.getVar(),
 864             mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>()));
 865
 866       } else if (PInfo.isTmp() && FunDecl->hasAttr<SetTypestateAttr>()) {
 867         StateMap->setState(PInfo.getTmp(),
 868           mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>()));
 869     }
 870     }
 871   }
 872 }
 873
 874 void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) {
 875   if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl()))
 876     if (StateMap->getState(Var) != consumed::CS_None)
 877       PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var)));
 878 }
 879
 880 void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) {
 881   for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(),
 882        DE = DeclS->decl_end(); DI != DE; ++DI) {
 883
 884     if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI));
 885   }
 886
 887   if (DeclS->isSingleDecl())
 888     if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl()))
 889       PropagationMap.insert(PairType(DeclS, PropagationInfo(Var)));
 890 }
 891
 892 void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr(
 893   const MaterializeTemporaryExpr *Temp) {
 894
 895   forwardInfo(Temp->GetTemporaryExpr(), Temp);
 896 }
 897
 898 void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) {
 899   forwardInfo(MExpr->getBase(), MExpr);
 900 }
 901
 902
 903 void ConsumedStmtVisitor::VisitParmVarDecl(const ParmVarDecl *Param) {
 904   QualType ParamType = Param->getType();
 905   ConsumedState ParamState = consumed::CS_None;
 906
 907   if (Param->hasAttr<ParamTypestateAttr>()) {
 908     const ParamTypestateAttr *PTAttr = Param->getAttr<ParamTypestateAttr>();
 909     ParamState = mapParamTypestateAttrState(PTAttr);
 910
 911   } else if (isConsumableType(ParamType)) {
 912     ParamState = mapConsumableAttrState(ParamType);
 913
 914   } else if (isRValueRefish(ParamType) &&
 915              isConsumableType(ParamType->getPointeeType())) {
 916
 917     ParamState = mapConsumableAttrState(ParamType->getPointeeType());
 918
 919   } else if (ParamType->isReferenceType() &&
 920              isConsumableType(ParamType->getPointeeType())) {
 921     ParamState = consumed::CS_Unknown;
 922   }
 923
 924   if (ParamState != CS_None)
 925     StateMap->setState(Param, ParamState);
 926 }
 927
 928 void ConsumedStmtVisitor::VisitReturnStmt(const ReturnStmt *Ret) {
 929   ConsumedState ExpectedState = Analyzer.getExpectedReturnState();
 930
 931   if (ExpectedState != CS_None) {
 932     InfoEntry Entry = PropagationMap.find(Ret->getRetValue());
 933
 934     if (Entry != PropagationMap.end()) {
 935       ConsumedState RetState = Entry->second.getAsState(StateMap);
 936
 937       if (RetState != ExpectedState)
 938         Analyzer.WarningsHandler.warnReturnTypestateMismatch(
 939           Ret->getReturnLoc(), stateToString(ExpectedState),
 940           stateToString(RetState));
 941     }
 942   }
 943
 944   StateMap->checkParamsForReturnTypestate(Ret->getLocStart(),
 945                                           Analyzer.WarningsHandler);
 946 }
 947
 948 void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) {
 949   InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens());
 950   if (Entry == PropagationMap.end()) return;
 951
 952   switch (UOp->getOpcode()) {
 953   case UO_AddrOf:
 954     PropagationMap.insert(PairType(UOp, Entry->second));
 955     break;
 956
 957   case UO_LNot:
 958     if (Entry->second.isTest())
 959       PropagationMap.insert(PairType(UOp, Entry->second.invertTest()));
 960     break;
 961
 962   default:
 963     break;
 964   }
 965 }
 966
 967 // TODO: See if I need to check for reference types here.
 968 void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) {
 969   if (isConsumableType(Var->getType())) {
 970     if (Var->hasInit()) {
 971       MapType::iterator VIT = PropagationMap.find(
 972         Var->getInit()->IgnoreImplicit());
 973       if (VIT != PropagationMap.end()) {
 974         PropagationInfo PInfo = VIT->second;
 975         ConsumedState St = PInfo.getAsState(StateMap);
 976
 977         if (St != consumed::CS_None) {
 978           StateMap->setState(Var, St);
 979           return;
 980         }
 981       }
 982     }
 983     // Otherwise
 984     StateMap->setState(Var, consumed::CS_Unknown);
 985   }
 986 }
 987 }} // end clang::consumed::ConsumedStmtVisitor
 988
 989 namespace clang {
 990 namespace consumed {
 991
 992 void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test,
 993                         ConsumedStateMap *ThenStates,
 994                         ConsumedStateMap *ElseStates) {
 995
 996   ConsumedState VarState = ThenStates->getState(Test.Var);
 997
 998   if (VarState == CS_Unknown) {
 999     ThenStates->setState(Test.Var, Test.TestsFor);
1000     ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor));
1001
1002   } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) {
1003     ThenStates->markUnreachable();
1004
1005   } else if (VarState == Test.TestsFor) {
1006     ElseStates->markUnreachable();
1007   }
1008 }
1009
1010 void splitVarStateForIfBinOp(const PropagationInfo &PInfo,
1011   ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) {
1012
1013   const VarTestResult &LTest = PInfo.getLTest(),
1014                       &RTest = PInfo.getRTest();
1015
1016   ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None,
1017                 RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None;
1018
1019   if (LTest.Var) {
1020     if (PInfo.testEffectiveOp() == EO_And) {
1021       if (LState == CS_Unknown) {
1022         ThenStates->setState(LTest.Var, LTest.TestsFor);
1023
1024       } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) {
1025         ThenStates->markUnreachable();
1026
1027       } else if (LState == LTest.TestsFor && isKnownState(RState)) {
1028         if (RState == RTest.TestsFor)
1029           ElseStates->markUnreachable();
1030         else
1031           ThenStates->markUnreachable();
1032       }
1033
1034     } else {
1035       if (LState == CS_Unknown) {
1036         ElseStates->setState(LTest.Var,
1037                              invertConsumedUnconsumed(LTest.TestsFor));
1038
1039       } else if (LState == LTest.TestsFor) {
1040         ElseStates->markUnreachable();
1041
1042       } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) &&
1043                  isKnownState(RState)) {
1044
1045         if (RState == RTest.TestsFor)
1046           ElseStates->markUnreachable();
1047         else
1048           ThenStates->markUnreachable();
1049       }
1050     }
1051   }
1052
1053   if (RTest.Var) {
1054     if (PInfo.testEffectiveOp() == EO_And) {
1055       if (RState == CS_Unknown)
1056         ThenStates->setState(RTest.Var, RTest.TestsFor);
1057       else if (RState == invertConsumedUnconsumed(RTest.TestsFor))
1058         ThenStates->markUnreachable();
1059
1060     } else {
1061       if (RState == CS_Unknown)
1062         ElseStates->setState(RTest.Var,
1063                              invertConsumedUnconsumed(RTest.TestsFor));
1064       else if (RState == RTest.TestsFor)
1065         ElseStates->markUnreachable();
1066     }
1067   }
1068 }
1069
1070 bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock,
1071                                             const CFGBlock *TargetBlock) {
1072
1073   assert(CurrBlock && "Block pointer must not be NULL");
1074   assert(TargetBlock && "TargetBlock pointer must not be NULL");
1075
1076   unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()];
1077   for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(),
1078        PE = TargetBlock->pred_end(); PI != PE; ++PI) {
1079     if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] )
1080       return false;
1081   }
1082   return true;
1083 }
1084
1085 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1086                                 ConsumedStateMap *StateMap,
1087                                 bool &AlreadyOwned) {
1088
1089   assert(Block && "Block pointer must not be NULL");
1090
1091   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1092
1093   if (Entry) {
1094     Entry->intersect(StateMap);
1095
1096   } else if (AlreadyOwned) {
1097     StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap);
1098
1099   } else {
1100     StateMapsArray[Block->getBlockID()] = StateMap;
1101     AlreadyOwned = true;
1102   }
1103 }
1104
1105 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
1106                                 ConsumedStateMap *StateMap) {
1107
1108   assert(Block != NULL && "Block pointer must not be NULL");
1109
1110   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
1111
1112   if (Entry) {
1113     Entry->intersect(StateMap);
1114     delete StateMap;
1115
1116   } else {
1117     StateMapsArray[Block->getBlockID()] = StateMap;
1118   }
1119 }
1120
1121 ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) {
1122   assert(Block && "Block pointer must not be NULL");
1123   assert(StateMapsArray[Block->getBlockID()] && "Block has no block info");
1124
1125   return StateMapsArray[Block->getBlockID()];
1126 }
1127
1128 void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) {
1129   unsigned int BlockID = Block->getBlockID();
1130   delete StateMapsArray[BlockID];
1131   StateMapsArray[BlockID] = NULL;
1132 }
1133
1134 ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
1135   assert(Block && "Block pointer must not be NULL");
1136
1137   ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()];
1138   if (isBackEdgeTarget(Block)) {
1139     return new ConsumedStateMap(*StateMap);
1140   } else {
1141     StateMapsArray[Block->getBlockID()] = NULL;
1142     return StateMap;
1143   }
1144 }
1145
1146 bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) {
1147   assert(From && "From block must not be NULL");
1148   assert(To   && "From block must not be NULL");
1149
1150   return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()];
1151 }
1152
1153 bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) {
1154   assert(Block != NULL && "Block pointer must not be NULL");
1155
1156   // Anything with less than two predecessors can't be the target of a back
1157   // edge.
1158   if (Block->pred_size() < 2)
1159     return false;
1160
1161   unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()];
1162   for (CFGBlock::const_pred_iterator PI = Block->pred_begin(),
1163        PE = Block->pred_end(); PI != PE; ++PI) {
1164     if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()])
1165       return true;
1166   }
1167   return false;
1168 }
1169
1170 void ConsumedStateMap::checkParamsForReturnTypestate(SourceLocation BlameLoc,
1171   ConsumedWarningsHandlerBase &WarningsHandler) const {
1172
1173   ConsumedState ExpectedState;
1174
1175   for (VarMapType::const_iterator DMI = VarMap.begin(), DME = VarMap.end();
1176        DMI != DME; ++DMI) {
1177
1178     if (isa<ParmVarDecl>(DMI->first)) {
1179       const ParmVarDecl *Param = cast<ParmVarDecl>(DMI->first);
1180
1181       if (!Param->hasAttr<ReturnTypestateAttr>()) continue;
1182
1183       ExpectedState =
1184         mapReturnTypestateAttrState(Param->getAttr<ReturnTypestateAttr>());
1185
1186       if (DMI->second != ExpectedState) {
1187         WarningsHandler.warnParamReturnTypestateMismatch(BlameLoc,
1188           Param->getNameAsString(), stateToString(ExpectedState),
1189           stateToString(DMI->second));
1190       }
1191     }
1192   }
1193 }
1194
1195 void ConsumedStateMap::clearTemporaries() {
1196   TmpMap.clear();
1197 }
1198
1199 ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const {
1200   VarMapType::const_iterator Entry = VarMap.find(Var);
1201
1202   if (Entry != VarMap.end())
1203     return Entry->second;
1204
1205   return CS_None;
1206 }
1207
1208 ConsumedState
1209 ConsumedStateMap::getState(const CXXBindTemporaryExpr *Tmp) const {
1210   TmpMapType::const_iterator Entry = TmpMap.find(Tmp);
1211
1212   if (Entry != TmpMap.end())
1213     return Entry->second;
1214
1215   return CS_None;
1216 }
1217
1218 void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
1219   ConsumedState LocalState;
1220
1221   if (this->From && this->From == Other->From && !Other->Reachable) {
1222     this->markUnreachable();
1223     return;
1224   }
1225
1226   for (VarMapType::const_iterator DMI = Other->VarMap.begin(),
1227        DME = Other->VarMap.end(); DMI != DME; ++DMI) {
1228
1229     LocalState = this->getState(DMI->first);
1230
1231     if (LocalState == CS_None)
1232       continue;
1233
1234     if (LocalState != DMI->second)
1235        VarMap[DMI->first] = CS_Unknown;
1236   }
1237 }
1238
1239 void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead,
1240   const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates,
1241   ConsumedWarningsHandlerBase &WarningsHandler) {
1242
1243   ConsumedState LocalState;
1244   SourceLocation BlameLoc = getLastStmtLoc(LoopBack);
1245
1246   for (VarMapType::const_iterator DMI = LoopBackStates->VarMap.begin(),
1247        DME = LoopBackStates->VarMap.end(); DMI != DME; ++DMI) {
1248
1249     LocalState = this->getState(DMI->first);
1250
1251     if (LocalState == CS_None)
1252       continue;
1253
1254     if (LocalState != DMI->second) {
1255       VarMap[DMI->first] = CS_Unknown;
1256       WarningsHandler.warnLoopStateMismatch(
1257         BlameLoc, DMI->first->getNameAsString());
1258     }
1259   }
1260 }
1261
1262 void ConsumedStateMap::markUnreachable() {
1263   this->Reachable = false;
1264   VarMap.clear();
1265   TmpMap.clear();
1266 }
1267
1268 void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
1269   VarMap[Var] = State;
1270 }
1271
1272 void ConsumedStateMap::setState(const CXXBindTemporaryExpr *Tmp,
1273                                 ConsumedState State) {
1274   TmpMap[Tmp] = State;
1275 }
1276
1277 void ConsumedStateMap::remove(const VarDecl *Var) {
1278   VarMap.erase(Var);
1279 }
1280
1281 bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const {
1282   for (VarMapType::const_iterator DMI = Other->VarMap.begin(),
1283        DME = Other->VarMap.end(); DMI != DME; ++DMI) {
1284
1285     if (this->getState(DMI->first) != DMI->second)
1286       return true;
1287   }
1288
1289   return false;
1290 }
1291
1292 void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC,
1293                                                     const FunctionDecl *D) {
1294   QualType ReturnType;
1295   if (const CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) {
1296     ASTContext &CurrContext = AC.getASTContext();
1297     ReturnType = Constructor->getThisType(CurrContext)->getPointeeType();
1298   } else
1299     ReturnType = D->getCallResultType();
1300
1301   if (D->hasAttr<ReturnTypestateAttr>()) {
1302     const ReturnTypestateAttr *RTSAttr = D->getAttr<ReturnTypestateAttr>();
1303
1304     const CXXRecordDecl *RD = ReturnType->getAsCXXRecordDecl();
1305     if (!RD || !RD->hasAttr<ConsumableAttr>()) {
1306       // FIXME: This should be removed when template instantiation propagates
1307       //        attributes at template specialization definition, not
1308       //        declaration. When it is removed the test needs to be enabled
1309       //        in SemaDeclAttr.cpp.
1310       WarningsHandler.warnReturnTypestateForUnconsumableType(
1311           RTSAttr->getLocation(), ReturnType.getAsString());
1312       ExpectedReturnState = CS_None;
1313     } else
1314       ExpectedReturnState = mapReturnTypestateAttrState(RTSAttr);
1315   } else if (isConsumableType(ReturnType))
1316     ExpectedReturnState = mapConsumableAttrState(ReturnType);
1317   else
1318     ExpectedReturnState = CS_None;
1319 }
1320
1321 bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock,
1322                                   const ConsumedStmtVisitor &Visitor) {
1323
1324   OwningPtr<ConsumedStateMap> FalseStates(new ConsumedStateMap(*CurrStates));
1325   PropagationInfo PInfo;
1326
1327   if (const IfStmt *IfNode =
1328     dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) {
1329
1330     const Stmt *Cond = IfNode->getCond();
1331
1332     PInfo = Visitor.getInfo(Cond);
1333     if (!PInfo.isValid() && isa<BinaryOperator>(Cond))
1334       PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS());
1335
1336     if (PInfo.isVarTest()) {
1337       CurrStates->setSource(Cond);
1338       FalseStates->setSource(Cond);
1339       splitVarStateForIf(IfNode, PInfo.getVarTest(), CurrStates,
1340                          FalseStates.get());
1341
1342     } else if (PInfo.isBinTest()) {
1343       CurrStates->setSource(PInfo.testSourceNode());
1344       FalseStates->setSource(PInfo.testSourceNode());
1345       splitVarStateForIfBinOp(PInfo, CurrStates, FalseStates.get());
1346
1347     } else {
1348       return false;
1349     }
1350
1351   } else if (const BinaryOperator *BinOp =
1352     dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) {
1353
1354     PInfo = Visitor.getInfo(BinOp->getLHS());
1355     if (!PInfo.isVarTest()) {
1356       if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) {
1357         PInfo = Visitor.getInfo(BinOp->getRHS());
1358
1359         if (!PInfo.isVarTest())
1360           return false;
1361
1362       } else {
1363         return false;
1364       }
1365     }
1366
1367     CurrStates->setSource(BinOp);
1368     FalseStates->setSource(BinOp);
1369
1370     const VarTestResult &Test = PInfo.getVarTest();
1371     ConsumedState VarState = CurrStates->getState(Test.Var);
1372
1373     if (BinOp->getOpcode() == BO_LAnd) {
1374       if (VarState == CS_Unknown)
1375         CurrStates->setState(Test.Var, Test.TestsFor);
1376       else if (VarState == invertConsumedUnconsumed(Test.TestsFor))
1377         CurrStates->markUnreachable();
1378
1379     } else if (BinOp->getOpcode() == BO_LOr) {
1380       if (VarState == CS_Unknown)
1381         FalseStates->setState(Test.Var,
1382                               invertConsumedUnconsumed(Test.TestsFor));
1383       else if (VarState == Test.TestsFor)
1384         FalseStates->markUnreachable();
1385     }
1386
1387   } else {
1388     return false;
1389   }
1390
1391   CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin();
1392
1393   if (*SI)
1394     BlockInfo.addInfo(*SI, CurrStates);
1395   else
1396     delete CurrStates;
1397
1398   if (*++SI)
1399     BlockInfo.addInfo(*SI, FalseStates.take());
1400
1401   CurrStates = NULL;
1402   return true;
1403 }
1404
1405 void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
1406   const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl());
1407   if (!D)
1408     return;
1409
1410   CFG *CFGraph = AC.getCFG();
1411   if (!CFGraph)
1412     return;
1413
1414   determineExpectedReturnState(AC, D);
1415
1416   PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
1417   // AC.getCFG()->viewCFG(LangOptions());
1418
1419   BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
1420
1421   CurrStates = new ConsumedStateMap();
1422   ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
1423
1424   // Add all trackable parameters to the state map.
1425   for (FunctionDecl::param_const_iterator PI = D->param_begin(),
1426        PE = D->param_end(); PI != PE; ++PI) {
1427     Visitor.VisitParmVarDecl(*PI);
1428   }
1429
1430   // Visit all of the function's basic blocks.
1431   for (PostOrderCFGView::iterator I = SortedGraph->begin(),
1432        E = SortedGraph->end(); I != E; ++I) {
1433
1434     const CFGBlock *CurrBlock = *I;
1435
1436     if (CurrStates == NULL)
1437       CurrStates = BlockInfo.getInfo(CurrBlock);
1438
1439     if (!CurrStates) {
1440       continue;
1441
1442     } else if (!CurrStates->isReachable()) {
1443       delete CurrStates;
1444       CurrStates = NULL;
1445       continue;
1446     }
1447
1448     Visitor.reset(CurrStates);
1449
1450     // Visit all of the basic block's statements.
1451     for (CFGBlock::const_iterator BI = CurrBlock->begin(),
1452          BE = CurrBlock->end(); BI != BE; ++BI) {
1453
1454       switch (BI->getKind()) {
1455       case CFGElement::Statement:
1456         Visitor.Visit(BI->castAs<CFGStmt>().getStmt());
1457         break;
1458
1459       case CFGElement::TemporaryDtor: {
1460         const CFGTemporaryDtor DTor = BI->castAs<CFGTemporaryDtor>();
1461         const CXXBindTemporaryExpr *BTE = DTor.getBindTemporaryExpr();
1462
1463         Visitor.checkCallability(PropagationInfo(BTE),
1464                                  DTor.getDestructorDecl(AC.getASTContext()),
1465                                  BTE->getExprLoc());
1466         break;
1467       }
1468
1469       case CFGElement::AutomaticObjectDtor: {
1470         const CFGAutomaticObjDtor DTor = BI->castAs<CFGAutomaticObjDtor>();
1471         SourceLocation Loc = DTor.getTriggerStmt()->getLocEnd();
1472         const VarDecl *Var = DTor.getVarDecl();
1473
1474         Visitor.checkCallability(PropagationInfo(Var),
1475                                  DTor.getDestructorDecl(AC.getASTContext()),
1476                                  Loc);
1477         break;
1478       }
1479
1480       default:
1481         break;
1482       }
1483     }
1484
1485     CurrStates->clearTemporaries();
1486
1487     // TODO: Handle other forms of branching with precision, including while-
1488     //       and for-loops. (Deferred)
1489     if (!splitState(CurrBlock, Visitor)) {
1490       CurrStates->setSource(NULL);
1491
1492       if (CurrBlock->succ_size() > 1 ||
1493           (CurrBlock->succ_size() == 1 &&
1494            (*CurrBlock->succ_begin())->pred_size() > 1)) {
1495
1496         bool OwnershipTaken = false;
1497
1498         for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
1499              SE = CurrBlock->succ_end(); SI != SE; ++SI) {
1500
1501           if (*SI == NULL) continue;
1502
1503           if (BlockInfo.isBackEdge(CurrBlock, *SI)) {
1504             BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock,
1505                                                            CurrStates,
1506                                                            WarningsHandler);
1507
1508             if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock))
1509               BlockInfo.discardInfo(*SI);
1510           } else {
1511             BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
1512           }
1513         }
1514
1515         if (!OwnershipTaken)
1516           delete CurrStates;
1517
1518         CurrStates = NULL;
1519       }
1520     }
1521
1522     if (CurrBlock == &AC.getCFG()->getExit() &&
1523         D->getCallResultType()->isVoidType())
1524       CurrStates->checkParamsForReturnTypestate(D->getLocation(),
1525                                                 WarningsHandler);
1526   } // End of block iterator.
1527
1528   // Delete the last existing state map.
1529   delete CurrStates;
1530
1531   WarningsHandler.emitDiagnostics();
1532 }
1533 }} // end namespace clang::consumed