Consumed.cpp revision f30e194f9d797ebeb2f6c3f96e88160ed1a6519a
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- Consumed.cpp --------------------------------------------*- C++ --*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A intra-procedural analysis for checking consumed properties. This is based, 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in part, on research on linear types. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/ASTContext.h" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/Attr.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/DeclCXX.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/ExprCXX.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/RecursiveASTVisitor.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/StmtVisitor.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/StmtCXX.h" 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/Type.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/Analyses/PostOrderCFGView.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/AnalysisContext.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/CFG.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/Analyses/Consumed.h" 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Basic/OperatorKinds.h" 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Basic/SourceLocation.h" 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/DenseMap.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/Compiler.h" 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Support/raw_ostream.h" 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Use information from tests in while-loop conditional. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Add notes about the actual and expected state for 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Correctly identify unreachable blocks when chaining boolean operators. 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Adjust the parser and AttributesList class to support lists of 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// identifiers. 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Warn about unreachable code. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Switch to using a bitmap to track unreachable blocks. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Handle variable definitions, e.g. bool valid = x.isValid(); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// if (valid) ...; (Deferred) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Take notes on state transitions to provide better warning messages. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (Deferred) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO: Test nested conditionals: A) Checking the same value multiple times, 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and 2) Checking different values. (Deferred) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace clang; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace consumed; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Key method definition 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {} 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SourceLocation getLastStmtLoc(const CFGBlock *Block) { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find the source location of the last statement in the block, if the block 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is not empty. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (const Stmt *StmtNode = Block->getTerminator()) { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return StmtNode->getLocStart(); 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (CFGBlock::const_reverse_iterator BI = Block->rbegin(), 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BE = Block->rend(); BI != BE; ++BI) { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FIXME: Handle other CFGElement kinds. 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS->getStmt()->getLocStart(); 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The block is empty, and has a single predecessor. Use its exit location. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(Block->pred_size() == 1 && *Block->pred_begin() && 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Block->succ_size() != 0); 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return getLastStmtLoc(*Block->pred_begin()); 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static ConsumedState invertConsumedUnconsumed(ConsumedState State) { 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (State) { 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_Unconsumed: 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Consumed; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_Consumed: 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unconsumed; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_None: 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_None; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_Unknown: 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unknown; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm_unreachable("invalid enum"); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool isCallableInState(const CallableWhenAttr *CWAttr, 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ConsumedState State) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CallableWhenAttr::callableState_iterator I = CWAttr->callableState_begin(), 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = CWAttr->callableState_end(); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; I != E; ++I) { 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ConsumedState MappedAttrState = CS_None; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (*I) { 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CallableWhenAttr::Unknown: 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MappedAttrState = CS_Unknown; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CallableWhenAttr::Unconsumed: 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MappedAttrState = CS_Unconsumed; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CallableWhenAttr::Consumed: 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MappedAttrState = CS_Consumed; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (MappedAttrState == State) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool isConsumableType(const QualType &QT) { 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (const CXXRecordDecl *RD = QT->getAsCXXRecordDecl()) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return RD->hasAttr<ConsumableAttr>(); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool isKnownState(ConsumedState State) { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (State) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_Unconsumed: 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_Consumed: 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_None: 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case CS_Unknown: 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm_unreachable("invalid enum"); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool isTestingFunction(const FunctionDecl *FunDecl) { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return FunDecl->hasAttr<TestsTypestateAttr>(); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static ConsumedState mapConsumableAttrState(const QualType QT) { 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(isConsumableType(QT)); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ConsumableAttr *CAttr = 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QT->getAsCXXRecordDecl()->getAttr<ConsumableAttr>(); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (CAttr->getDefaultState()) { 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ConsumableAttr::Unknown: 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unknown; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ConsumableAttr::Unconsumed: 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unconsumed; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ConsumableAttr::Consumed: 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Consumed; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm_unreachable("invalid enum"); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static ConsumedState mapSetTypestateAttrState(const SetTypestateAttr *STAttr) { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (STAttr->getNewState()) { 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case SetTypestateAttr::Unknown: 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unknown; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case SetTypestateAttr::Unconsumed: 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unconsumed; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case SetTypestateAttr::Consumed: 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Consumed; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm_unreachable("invalid_enum"); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static ConsumedState 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)mapReturnTypestateAttrState(const ReturnTypestateAttr *RTSAttr) { 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (RTSAttr->getState()) { 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ReturnTypestateAttr::Unknown: 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unknown; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ReturnTypestateAttr::Unconsumed: 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Unconsumed; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ReturnTypestateAttr::Consumed: 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CS_Consumed; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm_unreachable("invalid enum"); 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static StringRef stateToString(ConsumedState State) { 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (State) { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case consumed::CS_None: 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return "none"; 189 190 case consumed::CS_Unknown: 191 return "unknown"; 192 193 case consumed::CS_Unconsumed: 194 return "unconsumed"; 195 196 case consumed::CS_Consumed: 197 return "consumed"; 198 } 199 llvm_unreachable("invalid enum"); 200} 201 202static ConsumedState testsFor(const FunctionDecl *FunDecl) { 203 assert(isTestingFunction(FunDecl)); 204 switch (FunDecl->getAttr<TestsTypestateAttr>()->getTestState()) { 205 case TestsTypestateAttr::Unconsumed: 206 return CS_Unconsumed; 207 case TestsTypestateAttr::Consumed: 208 return CS_Consumed; 209 } 210 llvm_unreachable("invalid enum"); 211} 212 213namespace { 214struct VarTestResult { 215 const VarDecl *Var; 216 ConsumedState TestsFor; 217}; 218} // end anonymous::VarTestResult 219 220namespace clang { 221namespace consumed { 222 223enum EffectiveOp { 224 EO_And, 225 EO_Or 226}; 227 228class PropagationInfo { 229 enum { 230 IT_None, 231 IT_State, 232 IT_Test, 233 IT_BinTest, 234 IT_Var 235 } InfoType; 236 237 struct BinTestTy { 238 const BinaryOperator *Source; 239 EffectiveOp EOp; 240 VarTestResult LTest; 241 VarTestResult RTest; 242 }; 243 244 union { 245 ConsumedState State; 246 VarTestResult Test; 247 const VarDecl *Var; 248 BinTestTy BinTest; 249 }; 250 251 QualType TempType; 252 253public: 254 PropagationInfo() : InfoType(IT_None) {} 255 256 PropagationInfo(const VarTestResult &Test) : InfoType(IT_Test), Test(Test) {} 257 PropagationInfo(const VarDecl *Var, ConsumedState TestsFor) 258 : InfoType(IT_Test) { 259 260 Test.Var = Var; 261 Test.TestsFor = TestsFor; 262 } 263 264 PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp, 265 const VarTestResult <est, const VarTestResult &RTest) 266 : InfoType(IT_BinTest) { 267 268 BinTest.Source = Source; 269 BinTest.EOp = EOp; 270 BinTest.LTest = LTest; 271 BinTest.RTest = RTest; 272 } 273 274 PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp, 275 const VarDecl *LVar, ConsumedState LTestsFor, 276 const VarDecl *RVar, ConsumedState RTestsFor) 277 : InfoType(IT_BinTest) { 278 279 BinTest.Source = Source; 280 BinTest.EOp = EOp; 281 BinTest.LTest.Var = LVar; 282 BinTest.LTest.TestsFor = LTestsFor; 283 BinTest.RTest.Var = RVar; 284 BinTest.RTest.TestsFor = RTestsFor; 285 } 286 287 PropagationInfo(ConsumedState State, QualType TempType) 288 : InfoType(IT_State), State(State), TempType(TempType) {} 289 290 PropagationInfo(const VarDecl *Var) : InfoType(IT_Var), Var(Var) {} 291 292 const ConsumedState & getState() const { 293 assert(InfoType == IT_State); 294 return State; 295 } 296 297 const QualType & getTempType() const { 298 assert(InfoType == IT_State); 299 return TempType; 300 } 301 302 const VarTestResult & getTest() const { 303 assert(InfoType == IT_Test); 304 return Test; 305 } 306 307 const VarTestResult & getLTest() const { 308 assert(InfoType == IT_BinTest); 309 return BinTest.LTest; 310 } 311 312 const VarTestResult & getRTest() const { 313 assert(InfoType == IT_BinTest); 314 return BinTest.RTest; 315 } 316 317 const VarDecl * getVar() const { 318 assert(InfoType == IT_Var); 319 return Var; 320 } 321 322 EffectiveOp testEffectiveOp() const { 323 assert(InfoType == IT_BinTest); 324 return BinTest.EOp; 325 } 326 327 const BinaryOperator * testSourceNode() const { 328 assert(InfoType == IT_BinTest); 329 return BinTest.Source; 330 } 331 332 bool isValid() const { return InfoType != IT_None; } 333 bool isState() const { return InfoType == IT_State; } 334 bool isTest() const { return InfoType == IT_Test; } 335 bool isBinTest() const { return InfoType == IT_BinTest; } 336 bool isVar() const { return InfoType == IT_Var; } 337 338 PropagationInfo invertTest() const { 339 assert(InfoType == IT_Test || InfoType == IT_BinTest); 340 341 if (InfoType == IT_Test) { 342 return PropagationInfo(Test.Var, invertConsumedUnconsumed(Test.TestsFor)); 343 344 } else if (InfoType == IT_BinTest) { 345 return PropagationInfo(BinTest.Source, 346 BinTest.EOp == EO_And ? EO_Or : EO_And, 347 BinTest.LTest.Var, invertConsumedUnconsumed(BinTest.LTest.TestsFor), 348 BinTest.RTest.Var, invertConsumedUnconsumed(BinTest.RTest.TestsFor)); 349 } else { 350 return PropagationInfo(); 351 } 352 } 353}; 354 355class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> { 356 357 typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType; 358 typedef std::pair<const Stmt *, PropagationInfo> PairType; 359 typedef MapType::iterator InfoEntry; 360 typedef MapType::const_iterator ConstInfoEntry; 361 362 AnalysisDeclContext &AC; 363 ConsumedAnalyzer &Analyzer; 364 ConsumedStateMap *StateMap; 365 MapType PropagationMap; 366 void forwardInfo(const Stmt *From, const Stmt *To); 367 bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl); 368 void propagateReturnType(const Stmt *Call, const FunctionDecl *Fun, 369 QualType ReturnType); 370 371public: 372 void checkCallability(const PropagationInfo &PInfo, 373 const FunctionDecl *FunDecl, 374 SourceLocation BlameLoc); 375 376 void Visit(const Stmt *StmtNode); 377 378 void VisitBinaryOperator(const BinaryOperator *BinOp); 379 void VisitCallExpr(const CallExpr *Call); 380 void VisitCastExpr(const CastExpr *Cast); 381 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *Temp); 382 void VisitCXXConstructExpr(const CXXConstructExpr *Call); 383 void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call); 384 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call); 385 void VisitDeclRefExpr(const DeclRefExpr *DeclRef); 386 void VisitDeclStmt(const DeclStmt *DelcS); 387 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp); 388 void VisitMemberExpr(const MemberExpr *MExpr); 389 void VisitParmVarDecl(const ParmVarDecl *Param); 390 void VisitReturnStmt(const ReturnStmt *Ret); 391 void VisitUnaryOperator(const UnaryOperator *UOp); 392 void VisitVarDecl(const VarDecl *Var); 393 394 ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer, 395 ConsumedStateMap *StateMap) 396 : AC(AC), Analyzer(Analyzer), StateMap(StateMap) {} 397 398 PropagationInfo getInfo(const Stmt *StmtNode) const { 399 ConstInfoEntry Entry = PropagationMap.find(StmtNode); 400 401 if (Entry != PropagationMap.end()) 402 return Entry->second; 403 else 404 return PropagationInfo(); 405 } 406 407 void reset(ConsumedStateMap *NewStateMap) { 408 StateMap = NewStateMap; 409 } 410}; 411 412void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo, 413 const FunctionDecl *FunDecl, 414 SourceLocation BlameLoc) { 415 416 if (!FunDecl->hasAttr<CallableWhenAttr>()) 417 return; 418 419 const CallableWhenAttr *CWAttr = FunDecl->getAttr<CallableWhenAttr>(); 420 421 if (PInfo.isVar()) { 422 const VarDecl *Var = PInfo.getVar(); 423 ConsumedState VarState = StateMap->getState(Var); 424 425 assert(VarState != CS_None && "Invalid state"); 426 427 if (isCallableInState(CWAttr, VarState)) 428 return; 429 430 Analyzer.WarningsHandler.warnUseInInvalidState( 431 FunDecl->getNameAsString(), Var->getNameAsString(), 432 stateToString(VarState), BlameLoc); 433 434 } else if (PInfo.isState()) { 435 436 assert(PInfo.getState() != CS_None && "Invalid state"); 437 438 if (isCallableInState(CWAttr, PInfo.getState())) 439 return; 440 441 Analyzer.WarningsHandler.warnUseOfTempInInvalidState( 442 FunDecl->getNameAsString(), stateToString(PInfo.getState()), BlameLoc); 443 } 444} 445 446void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) { 447 InfoEntry Entry = PropagationMap.find(From); 448 449 if (Entry != PropagationMap.end()) 450 PropagationMap.insert(PairType(To, Entry->second)); 451} 452 453bool ConsumedStmtVisitor::isLikeMoveAssignment( 454 const CXXMethodDecl *MethodDecl) { 455 456 return MethodDecl->isMoveAssignmentOperator() || 457 (MethodDecl->getOverloadedOperator() == OO_Equal && 458 MethodDecl->getNumParams() == 1 && 459 MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType()); 460} 461 462void ConsumedStmtVisitor::propagateReturnType(const Stmt *Call, 463 const FunctionDecl *Fun, 464 QualType ReturnType) { 465 if (isConsumableType(ReturnType)) { 466 467 ConsumedState ReturnState; 468 469 if (Fun->hasAttr<ReturnTypestateAttr>()) 470 ReturnState = mapReturnTypestateAttrState( 471 Fun->getAttr<ReturnTypestateAttr>()); 472 else 473 ReturnState = mapConsumableAttrState(ReturnType); 474 475 PropagationMap.insert(PairType(Call, 476 PropagationInfo(ReturnState, ReturnType))); 477 } 478} 479 480void ConsumedStmtVisitor::Visit(const Stmt *StmtNode) { 481 482 ConstStmtVisitor<ConsumedStmtVisitor>::Visit(StmtNode); 483 484 for (Stmt::const_child_iterator CI = StmtNode->child_begin(), 485 CE = StmtNode->child_end(); CI != CE; ++CI) { 486 487 PropagationMap.erase(*CI); 488 } 489} 490 491void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) { 492 switch (BinOp->getOpcode()) { 493 case BO_LAnd: 494 case BO_LOr : { 495 InfoEntry LEntry = PropagationMap.find(BinOp->getLHS()), 496 REntry = PropagationMap.find(BinOp->getRHS()); 497 498 VarTestResult LTest, RTest; 499 500 if (LEntry != PropagationMap.end() && LEntry->second.isTest()) { 501 LTest = LEntry->second.getTest(); 502 503 } else { 504 LTest.Var = NULL; 505 LTest.TestsFor = CS_None; 506 } 507 508 if (REntry != PropagationMap.end() && REntry->second.isTest()) { 509 RTest = REntry->second.getTest(); 510 511 } else { 512 RTest.Var = NULL; 513 RTest.TestsFor = CS_None; 514 } 515 516 if (!(LTest.Var == NULL && RTest.Var == NULL)) 517 PropagationMap.insert(PairType(BinOp, PropagationInfo(BinOp, 518 static_cast<EffectiveOp>(BinOp->getOpcode() == BO_LOr), LTest, RTest))); 519 520 break; 521 } 522 523 case BO_PtrMemD: 524 case BO_PtrMemI: 525 forwardInfo(BinOp->getLHS(), BinOp); 526 break; 527 528 default: 529 break; 530 } 531} 532 533void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) { 534 if (const FunctionDecl *FunDecl = 535 dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) { 536 537 // Special case for the std::move function. 538 // TODO: Make this more specific. (Deferred) 539 if (FunDecl->getNameAsString() == "move") { 540 InfoEntry Entry = PropagationMap.find(Call->getArg(0)); 541 542 if (Entry != PropagationMap.end()) { 543 PropagationMap.insert(PairType(Call, Entry->second)); 544 } 545 546 return; 547 } 548 549 unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams(); 550 551 for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) { 552 QualType ParamType = FunDecl->getParamDecl(Index - Offset)->getType(); 553 554 InfoEntry Entry = PropagationMap.find(Call->getArg(Index)); 555 556 if (Entry == PropagationMap.end() || !Entry->second.isVar()) { 557 continue; 558 } 559 560 PropagationInfo PInfo = Entry->second; 561 562 if (ParamType->isRValueReferenceType() || 563 (ParamType->isLValueReferenceType() && 564 !cast<LValueReferenceType>(*ParamType).isSpelledAsLValue())) { 565 566 StateMap->setState(PInfo.getVar(), consumed::CS_Consumed); 567 568 } else if (!(ParamType.isConstQualified() || 569 ((ParamType->isReferenceType() || 570 ParamType->isPointerType()) && 571 ParamType->getPointeeType().isConstQualified()))) { 572 573 StateMap->setState(PInfo.getVar(), consumed::CS_Unknown); 574 } 575 } 576 577 QualType RetType = FunDecl->getCallResultType(); 578 if (RetType->isReferenceType()) 579 RetType = RetType->getPointeeType(); 580 581 propagateReturnType(Call, FunDecl, RetType); 582 } 583} 584 585void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) { 586 forwardInfo(Cast->getSubExpr(), Cast); 587} 588 589void ConsumedStmtVisitor::VisitCXXBindTemporaryExpr( 590 const CXXBindTemporaryExpr *Temp) { 591 592 forwardInfo(Temp->getSubExpr(), Temp); 593} 594 595void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) { 596 CXXConstructorDecl *Constructor = Call->getConstructor(); 597 598 ASTContext &CurrContext = AC.getASTContext(); 599 QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType(); 600 601 if (isConsumableType(ThisType)) { 602 if (Constructor->isDefaultConstructor()) { 603 604 PropagationMap.insert(PairType(Call, 605 PropagationInfo(consumed::CS_Consumed, ThisType))); 606 607 } else if (Constructor->isMoveConstructor()) { 608 609 PropagationInfo PInfo = 610 PropagationMap.find(Call->getArg(0))->second; 611 612 if (PInfo.isVar()) { 613 const VarDecl* Var = PInfo.getVar(); 614 615 PropagationMap.insert(PairType(Call, 616 PropagationInfo(StateMap->getState(Var), ThisType))); 617 618 StateMap->setState(Var, consumed::CS_Consumed); 619 620 } else { 621 PropagationMap.insert(PairType(Call, PInfo)); 622 } 623 624 } else if (Constructor->isCopyConstructor()) { 625 MapType::iterator Entry = PropagationMap.find(Call->getArg(0)); 626 627 if (Entry != PropagationMap.end()) 628 PropagationMap.insert(PairType(Call, Entry->second)); 629 630 } else { 631 propagateReturnType(Call, Constructor, ThisType); 632 } 633 } 634} 635 636 637void ConsumedStmtVisitor::VisitCXXMemberCallExpr( 638 const CXXMemberCallExpr *Call) { 639 640 VisitCallExpr(Call); 641 642 InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens()); 643 644 if (Entry != PropagationMap.end()) { 645 PropagationInfo PInfo = Entry->second; 646 const CXXMethodDecl *MethodDecl = Call->getMethodDecl(); 647 648 checkCallability(PInfo, MethodDecl, Call->getExprLoc()); 649 650 if (PInfo.isVar()) { 651 if (isTestingFunction(MethodDecl)) 652 PropagationMap.insert(PairType(Call, 653 PropagationInfo(PInfo.getVar(), testsFor(MethodDecl)))); 654 else if (MethodDecl->hasAttr<SetTypestateAttr>()) 655 StateMap->setState(PInfo.getVar(), 656 mapSetTypestateAttrState(MethodDecl->getAttr<SetTypestateAttr>())); 657 } 658 } 659} 660 661void ConsumedStmtVisitor::VisitCXXOperatorCallExpr( 662 const CXXOperatorCallExpr *Call) { 663 664 const FunctionDecl *FunDecl = 665 dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee()); 666 667 if (!FunDecl) return; 668 669 if (isa<CXXMethodDecl>(FunDecl) && 670 isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) { 671 672 InfoEntry LEntry = PropagationMap.find(Call->getArg(0)); 673 InfoEntry REntry = PropagationMap.find(Call->getArg(1)); 674 675 PropagationInfo LPInfo, RPInfo; 676 677 if (LEntry != PropagationMap.end() && 678 REntry != PropagationMap.end()) { 679 680 LPInfo = LEntry->second; 681 RPInfo = REntry->second; 682 683 if (LPInfo.isVar() && RPInfo.isVar()) { 684 StateMap->setState(LPInfo.getVar(), 685 StateMap->getState(RPInfo.getVar())); 686 687 StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed); 688 689 PropagationMap.insert(PairType(Call, LPInfo)); 690 691 } else if (LPInfo.isVar() && !RPInfo.isVar()) { 692 StateMap->setState(LPInfo.getVar(), RPInfo.getState()); 693 694 PropagationMap.insert(PairType(Call, LPInfo)); 695 696 } else if (!LPInfo.isVar() && RPInfo.isVar()) { 697 PropagationMap.insert(PairType(Call, 698 PropagationInfo(StateMap->getState(RPInfo.getVar()), 699 LPInfo.getTempType()))); 700 701 StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed); 702 703 } else { 704 PropagationMap.insert(PairType(Call, RPInfo)); 705 } 706 707 } else if (LEntry != PropagationMap.end() && 708 REntry == PropagationMap.end()) { 709 710 LPInfo = LEntry->second; 711 712 if (LPInfo.isVar()) { 713 StateMap->setState(LPInfo.getVar(), consumed::CS_Unknown); 714 715 PropagationMap.insert(PairType(Call, LPInfo)); 716 717 } else if (LPInfo.isState()) { 718 PropagationMap.insert(PairType(Call, 719 PropagationInfo(consumed::CS_Unknown, LPInfo.getTempType()))); 720 } 721 722 } else if (LEntry == PropagationMap.end() && 723 REntry != PropagationMap.end()) { 724 725 if (REntry->second.isVar()) 726 StateMap->setState(REntry->second.getVar(), consumed::CS_Consumed); 727 } 728 729 } else { 730 731 VisitCallExpr(Call); 732 733 InfoEntry Entry = PropagationMap.find(Call->getArg(0)); 734 735 if (Entry != PropagationMap.end()) { 736 PropagationInfo PInfo = Entry->second; 737 738 checkCallability(PInfo, FunDecl, Call->getExprLoc()); 739 740 if (PInfo.isVar()) { 741 if (isTestingFunction(FunDecl)) 742 PropagationMap.insert(PairType(Call, 743 PropagationInfo(PInfo.getVar(), testsFor(FunDecl)))); 744 else if (FunDecl->hasAttr<SetTypestateAttr>()) 745 StateMap->setState(PInfo.getVar(), 746 mapSetTypestateAttrState(FunDecl->getAttr<SetTypestateAttr>())); 747 } 748 } 749 } 750} 751 752void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) { 753 if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl())) 754 if (StateMap->getState(Var) != consumed::CS_None) 755 PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var))); 756} 757 758void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) { 759 for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(), 760 DE = DeclS->decl_end(); DI != DE; ++DI) { 761 762 if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI)); 763 } 764 765 if (DeclS->isSingleDecl()) 766 if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl())) 767 PropagationMap.insert(PairType(DeclS, PropagationInfo(Var))); 768} 769 770void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr( 771 const MaterializeTemporaryExpr *Temp) { 772 773 InfoEntry Entry = PropagationMap.find(Temp->GetTemporaryExpr()); 774 775 if (Entry != PropagationMap.end()) 776 PropagationMap.insert(PairType(Temp, Entry->second)); 777} 778 779void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) { 780 forwardInfo(MExpr->getBase(), MExpr); 781} 782 783 784void ConsumedStmtVisitor::VisitParmVarDecl(const ParmVarDecl *Param) { 785 QualType ParamType = Param->getType(); 786 ConsumedState ParamState = consumed::CS_None; 787 788 if (!(ParamType->isPointerType() || ParamType->isReferenceType()) && 789 isConsumableType(ParamType)) 790 ParamState = mapConsumableAttrState(ParamType); 791 else if (ParamType->isReferenceType() && 792 isConsumableType(ParamType->getPointeeType())) 793 ParamState = consumed::CS_Unknown; 794 795 if (ParamState) 796 StateMap->setState(Param, ParamState); 797} 798 799void ConsumedStmtVisitor::VisitReturnStmt(const ReturnStmt *Ret) { 800 if (ConsumedState ExpectedState = Analyzer.getExpectedReturnState()) { 801 InfoEntry Entry = PropagationMap.find(Ret->getRetValue()); 802 803 if (Entry != PropagationMap.end()) { 804 assert(Entry->second.isState() || Entry->second.isVar()); 805 806 ConsumedState RetState = Entry->second.isState() ? 807 Entry->second.getState() : StateMap->getState(Entry->second.getVar()); 808 809 if (RetState != ExpectedState) 810 Analyzer.WarningsHandler.warnReturnTypestateMismatch( 811 Ret->getReturnLoc(), stateToString(ExpectedState), 812 stateToString(RetState)); 813 } 814 } 815} 816 817void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) { 818 InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens()); 819 if (Entry == PropagationMap.end()) return; 820 821 switch (UOp->getOpcode()) { 822 case UO_AddrOf: 823 PropagationMap.insert(PairType(UOp, Entry->second)); 824 break; 825 826 case UO_LNot: 827 if (Entry->second.isTest() || Entry->second.isBinTest()) 828 PropagationMap.insert(PairType(UOp, Entry->second.invertTest())); 829 break; 830 831 default: 832 break; 833 } 834} 835 836// TODO: See if I need to check for reference types here. 837void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) { 838 if (isConsumableType(Var->getType())) { 839 if (Var->hasInit()) { 840 PropagationInfo PInfo = 841 PropagationMap.find(Var->getInit())->second; 842 843 StateMap->setState(Var, PInfo.isVar() ? 844 StateMap->getState(PInfo.getVar()) : PInfo.getState()); 845 846 } else { 847 StateMap->setState(Var, consumed::CS_Unknown); 848 } 849 } 850} 851}} // end clang::consumed::ConsumedStmtVisitor 852 853namespace clang { 854namespace consumed { 855 856void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test, 857 ConsumedStateMap *ThenStates, 858 ConsumedStateMap *ElseStates) { 859 860 ConsumedState VarState = ThenStates->getState(Test.Var); 861 862 if (VarState == CS_Unknown) { 863 ThenStates->setState(Test.Var, Test.TestsFor); 864 ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor)); 865 866 } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) { 867 ThenStates->markUnreachable(); 868 869 } else if (VarState == Test.TestsFor) { 870 ElseStates->markUnreachable(); 871 } 872} 873 874void splitVarStateForIfBinOp(const PropagationInfo &PInfo, 875 ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) { 876 877 const VarTestResult <est = PInfo.getLTest(), 878 &RTest = PInfo.getRTest(); 879 880 ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None, 881 RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None; 882 883 if (LTest.Var) { 884 if (PInfo.testEffectiveOp() == EO_And) { 885 if (LState == CS_Unknown) { 886 ThenStates->setState(LTest.Var, LTest.TestsFor); 887 888 } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) { 889 ThenStates->markUnreachable(); 890 891 } else if (LState == LTest.TestsFor && isKnownState(RState)) { 892 if (RState == RTest.TestsFor) 893 ElseStates->markUnreachable(); 894 else 895 ThenStates->markUnreachable(); 896 } 897 898 } else { 899 if (LState == CS_Unknown) { 900 ElseStates->setState(LTest.Var, 901 invertConsumedUnconsumed(LTest.TestsFor)); 902 903 } else if (LState == LTest.TestsFor) { 904 ElseStates->markUnreachable(); 905 906 } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) && 907 isKnownState(RState)) { 908 909 if (RState == RTest.TestsFor) 910 ElseStates->markUnreachable(); 911 else 912 ThenStates->markUnreachable(); 913 } 914 } 915 } 916 917 if (RTest.Var) { 918 if (PInfo.testEffectiveOp() == EO_And) { 919 if (RState == CS_Unknown) 920 ThenStates->setState(RTest.Var, RTest.TestsFor); 921 else if (RState == invertConsumedUnconsumed(RTest.TestsFor)) 922 ThenStates->markUnreachable(); 923 924 } else { 925 if (RState == CS_Unknown) 926 ElseStates->setState(RTest.Var, 927 invertConsumedUnconsumed(RTest.TestsFor)); 928 else if (RState == RTest.TestsFor) 929 ElseStates->markUnreachable(); 930 } 931 } 932} 933 934bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock, 935 const CFGBlock *TargetBlock) { 936 937 assert(CurrBlock && "Block pointer must not be NULL"); 938 assert(TargetBlock && "TargetBlock pointer must not be NULL"); 939 940 unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()]; 941 for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(), 942 PE = TargetBlock->pred_end(); PI != PE; ++PI) { 943 if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] ) 944 return false; 945 } 946 return true; 947} 948 949void ConsumedBlockInfo::addInfo(const CFGBlock *Block, 950 ConsumedStateMap *StateMap, 951 bool &AlreadyOwned) { 952 953 assert(Block && "Block pointer must not be NULL"); 954 955 ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()]; 956 957 if (Entry) { 958 Entry->intersect(StateMap); 959 960 } else if (AlreadyOwned) { 961 StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap); 962 963 } else { 964 StateMapsArray[Block->getBlockID()] = StateMap; 965 AlreadyOwned = true; 966 } 967} 968 969void ConsumedBlockInfo::addInfo(const CFGBlock *Block, 970 ConsumedStateMap *StateMap) { 971 972 assert(Block != NULL && "Block pointer must not be NULL"); 973 974 ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()]; 975 976 if (Entry) { 977 Entry->intersect(StateMap); 978 delete StateMap; 979 980 } else { 981 StateMapsArray[Block->getBlockID()] = StateMap; 982 } 983} 984 985ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) { 986 assert(Block && "Block pointer must not be NULL"); 987 assert(StateMapsArray[Block->getBlockID()] && "Block has no block info"); 988 989 return StateMapsArray[Block->getBlockID()]; 990} 991 992void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) { 993 unsigned int BlockID = Block->getBlockID(); 994 delete StateMapsArray[BlockID]; 995 StateMapsArray[BlockID] = NULL; 996} 997 998ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) { 999 assert(Block && "Block pointer must not be NULL"); 1000 1001 ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()]; 1002 if (isBackEdgeTarget(Block)) { 1003 return new ConsumedStateMap(*StateMap); 1004 } else { 1005 StateMapsArray[Block->getBlockID()] = NULL; 1006 return StateMap; 1007 } 1008} 1009 1010bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) { 1011 assert(From && "From block must not be NULL"); 1012 assert(To && "From block must not be NULL"); 1013 1014 return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()]; 1015} 1016 1017bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) { 1018 assert(Block != NULL && "Block pointer must not be NULL"); 1019 1020 // Anything with less than two predecessors can't be the target of a back 1021 // edge. 1022 if (Block->pred_size() < 2) 1023 return false; 1024 1025 unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()]; 1026 for (CFGBlock::const_pred_iterator PI = Block->pred_begin(), 1027 PE = Block->pred_end(); PI != PE; ++PI) { 1028 if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()]) 1029 return true; 1030 } 1031 return false; 1032} 1033 1034ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const { 1035 MapType::const_iterator Entry = Map.find(Var); 1036 1037 if (Entry != Map.end()) { 1038 return Entry->second; 1039 1040 } else { 1041 return CS_None; 1042 } 1043} 1044 1045void ConsumedStateMap::intersect(const ConsumedStateMap *Other) { 1046 ConsumedState LocalState; 1047 1048 if (this->From && this->From == Other->From && !Other->Reachable) { 1049 this->markUnreachable(); 1050 return; 1051 } 1052 1053 for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end(); 1054 DMI != DME; ++DMI) { 1055 1056 LocalState = this->getState(DMI->first); 1057 1058 if (LocalState == CS_None) 1059 continue; 1060 1061 if (LocalState != DMI->second) 1062 Map[DMI->first] = CS_Unknown; 1063 } 1064} 1065 1066void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead, 1067 const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates, 1068 ConsumedWarningsHandlerBase &WarningsHandler) { 1069 1070 ConsumedState LocalState; 1071 SourceLocation BlameLoc = getLastStmtLoc(LoopBack); 1072 1073 for (MapType::const_iterator DMI = LoopBackStates->Map.begin(), 1074 DME = LoopBackStates->Map.end(); DMI != DME; ++DMI) { 1075 1076 LocalState = this->getState(DMI->first); 1077 1078 if (LocalState == CS_None) 1079 continue; 1080 1081 if (LocalState != DMI->second) { 1082 Map[DMI->first] = CS_Unknown; 1083 WarningsHandler.warnLoopStateMismatch( 1084 BlameLoc, DMI->first->getNameAsString()); 1085 } 1086 } 1087} 1088 1089void ConsumedStateMap::markUnreachable() { 1090 this->Reachable = false; 1091 Map.clear(); 1092} 1093 1094void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) { 1095 Map[Var] = State; 1096} 1097 1098void ConsumedStateMap::remove(const VarDecl *Var) { 1099 Map.erase(Var); 1100} 1101 1102bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const { 1103 for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end(); 1104 DMI != DME; ++DMI) { 1105 1106 if (this->getState(DMI->first) != DMI->second) 1107 return true; 1108 } 1109 1110 return false; 1111} 1112 1113void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC, 1114 const FunctionDecl *D) { 1115 QualType ReturnType; 1116 if (const CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(D)) { 1117 ASTContext &CurrContext = AC.getASTContext(); 1118 ReturnType = Constructor->getThisType(CurrContext)->getPointeeType(); 1119 } else 1120 ReturnType = D->getCallResultType(); 1121 1122 if (D->hasAttr<ReturnTypestateAttr>()) { 1123 const ReturnTypestateAttr *RTSAttr = D->getAttr<ReturnTypestateAttr>(); 1124 1125 const CXXRecordDecl *RD = ReturnType->getAsCXXRecordDecl(); 1126 if (!RD || !RD->hasAttr<ConsumableAttr>()) { 1127 // FIXME: This should be removed when template instantiation propagates 1128 // attributes at template specialization definition, not 1129 // declaration. When it is removed the test needs to be enabled 1130 // in SemaDeclAttr.cpp. 1131 WarningsHandler.warnReturnTypestateForUnconsumableType( 1132 RTSAttr->getLocation(), ReturnType.getAsString()); 1133 ExpectedReturnState = CS_None; 1134 } else 1135 ExpectedReturnState = mapReturnTypestateAttrState(RTSAttr); 1136 } else if (isConsumableType(ReturnType)) 1137 ExpectedReturnState = mapConsumableAttrState(ReturnType); 1138 else 1139 ExpectedReturnState = CS_None; 1140} 1141 1142bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock, 1143 const ConsumedStmtVisitor &Visitor) { 1144 1145 ConsumedStateMap *FalseStates = new ConsumedStateMap(*CurrStates); 1146 PropagationInfo PInfo; 1147 1148 if (const IfStmt *IfNode = 1149 dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) { 1150 1151 const Stmt *Cond = IfNode->getCond(); 1152 1153 PInfo = Visitor.getInfo(Cond); 1154 if (!PInfo.isValid() && isa<BinaryOperator>(Cond)) 1155 PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS()); 1156 1157 if (PInfo.isTest()) { 1158 CurrStates->setSource(Cond); 1159 FalseStates->setSource(Cond); 1160 splitVarStateForIf(IfNode, PInfo.getTest(), CurrStates, FalseStates); 1161 1162 } else if (PInfo.isBinTest()) { 1163 CurrStates->setSource(PInfo.testSourceNode()); 1164 FalseStates->setSource(PInfo.testSourceNode()); 1165 splitVarStateForIfBinOp(PInfo, CurrStates, FalseStates); 1166 1167 } else { 1168 delete FalseStates; 1169 return false; 1170 } 1171 1172 } else if (const BinaryOperator *BinOp = 1173 dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) { 1174 1175 PInfo = Visitor.getInfo(BinOp->getLHS()); 1176 if (!PInfo.isTest()) { 1177 if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) { 1178 PInfo = Visitor.getInfo(BinOp->getRHS()); 1179 1180 if (!PInfo.isTest()) { 1181 delete FalseStates; 1182 return false; 1183 } 1184 1185 } else { 1186 delete FalseStates; 1187 return false; 1188 } 1189 } 1190 1191 CurrStates->setSource(BinOp); 1192 FalseStates->setSource(BinOp); 1193 1194 const VarTestResult &Test = PInfo.getTest(); 1195 ConsumedState VarState = CurrStates->getState(Test.Var); 1196 1197 if (BinOp->getOpcode() == BO_LAnd) { 1198 if (VarState == CS_Unknown) 1199 CurrStates->setState(Test.Var, Test.TestsFor); 1200 else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) 1201 CurrStates->markUnreachable(); 1202 1203 } else if (BinOp->getOpcode() == BO_LOr) { 1204 if (VarState == CS_Unknown) 1205 FalseStates->setState(Test.Var, 1206 invertConsumedUnconsumed(Test.TestsFor)); 1207 else if (VarState == Test.TestsFor) 1208 FalseStates->markUnreachable(); 1209 } 1210 1211 } else { 1212 delete FalseStates; 1213 return false; 1214 } 1215 1216 CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(); 1217 1218 if (*SI) 1219 BlockInfo.addInfo(*SI, CurrStates); 1220 else 1221 delete CurrStates; 1222 1223 if (*++SI) 1224 BlockInfo.addInfo(*SI, FalseStates); 1225 else 1226 delete FalseStates; 1227 1228 CurrStates = NULL; 1229 return true; 1230} 1231 1232void ConsumedAnalyzer::run(AnalysisDeclContext &AC) { 1233 const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl()); 1234 if (!D) 1235 return; 1236 1237 CFG *CFGraph = AC.getCFG(); 1238 if (!CFGraph) 1239 return; 1240 1241 determineExpectedReturnState(AC, D); 1242 1243 PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 1244 // AC.getCFG()->viewCFG(LangOptions()); 1245 1246 BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph); 1247 1248 CurrStates = new ConsumedStateMap(); 1249 ConsumedStmtVisitor Visitor(AC, *this, CurrStates); 1250 1251 // Add all trackable parameters to the state map. 1252 for (FunctionDecl::param_const_iterator PI = D->param_begin(), 1253 PE = D->param_end(); PI != PE; ++PI) { 1254 Visitor.VisitParmVarDecl(*PI); 1255 } 1256 1257 // Visit all of the function's basic blocks. 1258 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1259 E = SortedGraph->end(); I != E; ++I) { 1260 1261 const CFGBlock *CurrBlock = *I; 1262 1263 if (CurrStates == NULL) 1264 CurrStates = BlockInfo.getInfo(CurrBlock); 1265 1266 if (!CurrStates) { 1267 continue; 1268 1269 } else if (!CurrStates->isReachable()) { 1270 delete CurrStates; 1271 CurrStates = NULL; 1272 continue; 1273 } 1274 1275 Visitor.reset(CurrStates); 1276 1277 // Visit all of the basic block's statements. 1278 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1279 BE = CurrBlock->end(); BI != BE; ++BI) { 1280 1281 switch (BI->getKind()) { 1282 case CFGElement::Statement: 1283 Visitor.Visit(BI->castAs<CFGStmt>().getStmt()); 1284 break; 1285 1286 case CFGElement::TemporaryDtor: { 1287 const CFGTemporaryDtor DTor = BI->castAs<CFGTemporaryDtor>(); 1288 const CXXBindTemporaryExpr *BTE = DTor.getBindTemporaryExpr(); 1289 PropagationInfo PInfo = Visitor.getInfo(BTE); 1290 1291 if (PInfo.isValid()) 1292 Visitor.checkCallability(PInfo, 1293 DTor.getDestructorDecl(AC.getASTContext()), 1294 BTE->getExprLoc()); 1295 break; 1296 } 1297 1298 case CFGElement::AutomaticObjectDtor: { 1299 const CFGAutomaticObjDtor DTor = BI->castAs<CFGAutomaticObjDtor>(); 1300 1301 const VarDecl *Var = DTor.getVarDecl(); 1302 ConsumedState VarState = CurrStates->getState(Var); 1303 1304 if (VarState != CS_None) { 1305 PropagationInfo PInfo(Var); 1306 1307 Visitor.checkCallability(PInfo, 1308 DTor.getDestructorDecl(AC.getASTContext()), 1309 getLastStmtLoc(CurrBlock)); 1310 1311 CurrStates->remove(Var); 1312 } 1313 break; 1314 } 1315 1316 default: 1317 break; 1318 } 1319 } 1320 1321 // TODO: Handle other forms of branching with precision, including while- 1322 // and for-loops. (Deferred) 1323 if (!splitState(CurrBlock, Visitor)) { 1324 CurrStates->setSource(NULL); 1325 1326 if (CurrBlock->succ_size() > 1 || 1327 (CurrBlock->succ_size() == 1 && 1328 (*CurrBlock->succ_begin())->pred_size() > 1)) { 1329 1330 bool OwnershipTaken = false; 1331 1332 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 1333 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 1334 1335 if (*SI == NULL) continue; 1336 1337 if (BlockInfo.isBackEdge(CurrBlock, *SI)) { 1338 BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock, 1339 CurrStates, 1340 WarningsHandler); 1341 1342 if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock)) 1343 BlockInfo.discardInfo(*SI); 1344 } else { 1345 BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken); 1346 } 1347 } 1348 1349 if (!OwnershipTaken) 1350 delete CurrStates; 1351 1352 CurrStates = NULL; 1353 } 1354 } 1355 } // End of block iterator. 1356 1357 // Delete the last existing state map. 1358 delete CurrStates; 1359 1360 WarningsHandler.emitDiagnostics(); 1361} 1362}} // end namespace clang::consumed 1363