CoreEngine.h revision cfa88f893915ceb8ae4ce2f17c46c24a4d67502f
12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-// 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The LLVM Compiler Infrastructure 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// License. See LICENSE.TXT for details. 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This file defines a generic engine for intraprocedural, path-sensitive, 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// dataflow analysis via graph reachability. 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef LLVM_CLANG_GR_COREENGINE 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define LLVM_CLANG_GR_COREENGINE 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/AST/Expr.h" 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/Analysis/AnalysisContext.h" 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/OwningPtr.h" 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace clang { 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class ProgramPointTag; 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace ento { 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class NodeBuilder; 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// CoreEngine - Implements the core logic of the graph-reachability 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// analysis. It traverses the CFG and generates the ExplodedGraph. 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// Program "states" are treated as opaque void pointers. 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// The template class CoreEngine (which subclasses CoreEngine) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// provides the matching component to the engine that knows the actual types 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// for states. Note that this engine only dispatches to transfer functions 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// at the statement and block-level. The analyses themselves must implement 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/// any transfer function logic and the sub-expression level (if any). 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class CoreEngine { 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend struct NodeBuilderContext; 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class NodeBuilder; 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class ExprEngine; 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class CommonNodeBuilder; 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class IndirectGotoNodeBuilder; 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class SwitchNodeBuilder; 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) friend class EndOfFunctionNodeBuilder; 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)public: 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> > 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BlocksExhausted; 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> > 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BlocksAborted; 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)private: 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SubEngine& SubEng; 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// G - The simulation graph. Each node is a (location,state) pair. 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) OwningPtr<ExplodedGraph> G; 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// WList - A set of queued nodes that need to be processed by the 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// worklist algorithm. It is up to the implementation of WList to decide 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// the order that nodes are processed. 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) OwningPtr<WorkList> WList; 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// BCounterFactory - A factory object for created BlockCounter objects. 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// These are used to record for key nodes in the ExplodedGraph the 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// number of times different CFGBlocks have been visited along a path. 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BlockCounter::Factory BCounterFactory; 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// The locations where we stopped doing work because we visited a location 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// too many times. 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BlocksExhausted blocksExhausted; 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// The locations where we stopped because the engine aborted analysis, 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// usually because it could not reason about something. 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BlocksAborted blocksAborted; 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// The information about functions shared by the whole translation unit. 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// (This data is owned by AnalysisConsumer.) 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FunctionSummariesTy *FunctionSummaries; 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void generateNode(const ProgramPoint &Loc, 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramStateRef State, 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNode *Pred); 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNode *Pred); 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)private: 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CoreEngine(const CoreEngine &) LLVM_DELETED_FUNCTION; 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void operator=(const CoreEngine &) LLVM_DELETED_FUNCTION; 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNode *generateCallExitBeginNode(ExplodedNode *N); 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)public: 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// Construct a CoreEngine object to analyze the provided CFG. 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CoreEngine(SubEngine& subengine, 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FunctionSummariesTy *FS) 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : SubEng(subengine), G(new ExplodedGraph()), 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WList(WorkList::makeDFS()), 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BCounterFactory(G->getAllocator()), 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FunctionSummaries(FS){} 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// getGraph - Returns the exploded graph. 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedGraph& getGraph() { return *G.get(); } 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// takeGraph - Returns the exploded graph. Ownership of the graph is 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// transferred to the caller. 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedGraph* takeGraph() { return G.take(); } 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 121 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 122 /// steps. Returns true if there is still simulation state on the worklist. 123 bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 124 ProgramStateRef InitState); 125 /// Returns true if there is still simulation state on the worklist. 126 bool ExecuteWorkListWithInitialState(const LocationContext *L, 127 unsigned Steps, 128 ProgramStateRef InitState, 129 ExplodedNodeSet &Dst); 130 131 /// Dispatch the work list item based on the given location information. 132 /// Use Pred parameter as the predecessor state. 133 void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 134 const WorkListUnit& WU); 135 136 // Functions for external checking of whether we have unfinished work 137 bool wasBlockAborted() const { return !blocksAborted.empty(); } 138 bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } 139 bool hasWorkRemaining() const { return wasBlocksExhausted() || 140 WList->hasWork() || 141 wasBlockAborted(); } 142 143 /// Inform the CoreEngine that a basic block was aborted because 144 /// it could not be completely analyzed. 145 void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 146 blocksAborted.push_back(std::make_pair(block, node)); 147 } 148 149 WorkList *getWorkList() const { return WList.get(); } 150 151 BlocksExhausted::const_iterator blocks_exhausted_begin() const { 152 return blocksExhausted.begin(); 153 } 154 BlocksExhausted::const_iterator blocks_exhausted_end() const { 155 return blocksExhausted.end(); 156 } 157 BlocksAborted::const_iterator blocks_aborted_begin() const { 158 return blocksAborted.begin(); 159 } 160 BlocksAborted::const_iterator blocks_aborted_end() const { 161 return blocksAborted.end(); 162 } 163 164 /// \brief Enqueue the given set of nodes onto the work list. 165 void enqueue(ExplodedNodeSet &Set); 166 167 /// \brief Enqueue nodes that were created as a result of processing 168 /// a statement onto the work list. 169 void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx); 170 171 /// \brief enqueue the nodes corresponding to the end of function onto the 172 /// end of path / work list. 173 void enqueueEndOfFunction(ExplodedNodeSet &Set); 174 175 /// \brief Enqueue a single node created as a result of statement processing. 176 void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx); 177}; 178 179// TODO: Turn into a calss. 180struct NodeBuilderContext { 181 const CoreEngine &Eng; 182 const CFGBlock *Block; 183 const LocationContext *LC; 184 NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N) 185 : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); } 186 187 /// \brief Return the CFGBlock associated with this builder. 188 const CFGBlock *getBlock() const { return Block; } 189 190 /// \brief Returns the number of times the current basic block has been 191 /// visited on the exploded graph path. 192 unsigned blockCount() const { 193 return Eng.WList->getBlockCounter().getNumVisited( 194 LC->getCurrentStackFrame(), 195 Block->getBlockID()); 196 } 197}; 198 199/// \class NodeBuilder 200/// \brief This is the simplest builder which generates nodes in the 201/// ExplodedGraph. 202/// 203/// The main benefit of the builder is that it automatically tracks the 204/// frontier nodes (or destination set). This is the set of nodes which should 205/// be propagated to the next step / builder. They are the nodes which have been 206/// added to the builder (either as the input node set or as the newly 207/// constructed nodes) but did not have any outgoing transitions added. 208class NodeBuilder { 209 virtual void anchor(); 210protected: 211 const NodeBuilderContext &C; 212 213 /// Specifies if the builder results have been finalized. For example, if it 214 /// is set to false, autotransitions are yet to be generated. 215 bool Finalized; 216 bool HasGeneratedNodes; 217 /// \brief The frontier set - a set of nodes which need to be propagated after 218 /// the builder dies. 219 ExplodedNodeSet &Frontier; 220 221 /// Checkes if the results are ready. 222 virtual bool checkResults() { 223 if (!Finalized) 224 return false; 225 return true; 226 } 227 228 bool hasNoSinksInFrontier() { 229 for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) { 230 if ((*I)->isSink()) 231 return false; 232 } 233 return true; 234 } 235 236 /// Allow subclasses to finalize results before result_begin() is executed. 237 virtual void finalizeResults() {} 238 239 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 240 ProgramStateRef State, 241 ExplodedNode *Pred, 242 bool MarkAsSink = false); 243 244public: 245 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 246 const NodeBuilderContext &Ctx, bool F = true) 247 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 248 Frontier.Add(SrcNode); 249 } 250 251 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 252 const NodeBuilderContext &Ctx, bool F = true) 253 : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) { 254 Frontier.insert(SrcSet); 255 assert(hasNoSinksInFrontier()); 256 } 257 258 virtual ~NodeBuilder() {} 259 260 /// \brief Generates a node in the ExplodedGraph. 261 ExplodedNode *generateNode(const ProgramPoint &PP, 262 ProgramStateRef State, 263 ExplodedNode *Pred) { 264 return generateNodeImpl(PP, State, Pred, false); 265 } 266 267 /// \brief Generates a sink in the ExplodedGraph. 268 /// 269 /// When a node is marked as sink, the exploration from the node is stopped - 270 /// the node becomes the last node on the path and certain kinds of bugs are 271 /// suppressed. 272 ExplodedNode *generateSink(const ProgramPoint &PP, 273 ProgramStateRef State, 274 ExplodedNode *Pred) { 275 return generateNodeImpl(PP, State, Pred, true); 276 } 277 278 const ExplodedNodeSet &getResults() { 279 finalizeResults(); 280 assert(checkResults()); 281 return Frontier; 282 } 283 284 typedef ExplodedNodeSet::iterator iterator; 285 /// \brief Iterators through the results frontier. 286 inline iterator begin() { 287 finalizeResults(); 288 assert(checkResults()); 289 return Frontier.begin(); 290 } 291 inline iterator end() { 292 finalizeResults(); 293 return Frontier.end(); 294 } 295 296 const NodeBuilderContext &getContext() { return C; } 297 bool hasGeneratedNodes() { return HasGeneratedNodes; } 298 299 void takeNodes(const ExplodedNodeSet &S) { 300 for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I ) 301 Frontier.erase(*I); 302 } 303 void takeNodes(ExplodedNode *N) { Frontier.erase(N); } 304 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } 305 void addNodes(ExplodedNode *N) { Frontier.Add(N); } 306}; 307 308/// \class NodeBuilderWithSinks 309/// \brief This node builder keeps track of the generated sink nodes. 310class NodeBuilderWithSinks: public NodeBuilder { 311 virtual void anchor(); 312protected: 313 SmallVector<ExplodedNode*, 2> sinksGenerated; 314 ProgramPoint &Location; 315 316public: 317 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, 318 const NodeBuilderContext &Ctx, ProgramPoint &L) 319 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} 320 321 ExplodedNode *generateNode(ProgramStateRef State, 322 ExplodedNode *Pred, 323 const ProgramPointTag *Tag = 0) { 324 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location); 325 return NodeBuilder::generateNode(LocalLoc, State, Pred); 326 } 327 328 ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred, 329 const ProgramPointTag *Tag = 0) { 330 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location); 331 ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred); 332 if (N && N->isSink()) 333 sinksGenerated.push_back(N); 334 return N; 335 } 336 337 const SmallVectorImpl<ExplodedNode*> &getSinks() const { 338 return sinksGenerated; 339 } 340}; 341 342/// \class StmtNodeBuilder 343/// \brief This builder class is useful for generating nodes that resulted from 344/// visiting a statement. The main difference from its parent NodeBuilder is 345/// that it creates a statement specific ProgramPoint. 346class StmtNodeBuilder: public NodeBuilder { 347 NodeBuilder *EnclosingBldr; 348public: 349 350 /// \brief Constructs a StmtNodeBuilder. If the builder is going to process 351 /// nodes currently owned by another builder(with larger scope), use 352 /// Enclosing builder to transfer ownership. 353 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 354 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 355 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { 356 if (EnclosingBldr) 357 EnclosingBldr->takeNodes(SrcNode); 358 } 359 360 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 361 const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0) 362 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { 363 if (EnclosingBldr) 364 for (ExplodedNodeSet::iterator I = SrcSet.begin(), 365 E = SrcSet.end(); I != E; ++I ) 366 EnclosingBldr->takeNodes(*I); 367 } 368 369 virtual ~StmtNodeBuilder(); 370 371 using NodeBuilder::generateNode; 372 using NodeBuilder::generateSink; 373 374 ExplodedNode *generateNode(const Stmt *S, 375 ExplodedNode *Pred, 376 ProgramStateRef St, 377 const ProgramPointTag *tag = 0, 378 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 379 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 380 Pred->getLocationContext(), tag); 381 return NodeBuilder::generateNode(L, St, Pred); 382 } 383 384 ExplodedNode *generateSink(const Stmt *S, 385 ExplodedNode *Pred, 386 ProgramStateRef St, 387 const ProgramPointTag *tag = 0, 388 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 389 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 390 Pred->getLocationContext(), tag); 391 return NodeBuilder::generateSink(L, St, Pred); 392 } 393}; 394 395/// \brief BranchNodeBuilder is responsible for constructing the nodes 396/// corresponding to the two branches of the if statement - true and false. 397class BranchNodeBuilder: public NodeBuilder { 398 virtual void anchor(); 399 const CFGBlock *DstT; 400 const CFGBlock *DstF; 401 402 bool InFeasibleTrue; 403 bool InFeasibleFalse; 404 405public: 406 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 407 const NodeBuilderContext &C, 408 const CFGBlock *dstT, const CFGBlock *dstF) 409 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 410 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 411 // The branch node builder does not generate autotransitions. 412 // If there are no successors it means that both branches are infeasible. 413 takeNodes(SrcNode); 414 } 415 416 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 417 const NodeBuilderContext &C, 418 const CFGBlock *dstT, const CFGBlock *dstF) 419 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 420 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 421 takeNodes(SrcSet); 422 } 423 424 ExplodedNode *generateNode(ProgramStateRef State, bool branch, 425 ExplodedNode *Pred); 426 427 const CFGBlock *getTargetBlock(bool branch) const { 428 return branch ? DstT : DstF; 429 } 430 431 void markInfeasible(bool branch) { 432 if (branch) 433 InFeasibleTrue = true; 434 else 435 InFeasibleFalse = true; 436 } 437 438 bool isFeasible(bool branch) { 439 return branch ? !InFeasibleTrue : !InFeasibleFalse; 440 } 441}; 442 443class IndirectGotoNodeBuilder { 444 CoreEngine& Eng; 445 const CFGBlock *Src; 446 const CFGBlock &DispatchBlock; 447 const Expr *E; 448 ExplodedNode *Pred; 449 450public: 451 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 452 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 453 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 454 455 class iterator { 456 CFGBlock::const_succ_iterator I; 457 458 friend class IndirectGotoNodeBuilder; 459 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 460 public: 461 462 iterator &operator++() { ++I; return *this; } 463 bool operator!=(const iterator &X) const { return I != X.I; } 464 465 const LabelDecl *getLabel() const { 466 return cast<LabelStmt>((*I)->getLabel())->getDecl(); 467 } 468 469 const CFGBlock *getBlock() const { 470 return *I; 471 } 472 }; 473 474 iterator begin() { return iterator(DispatchBlock.succ_begin()); } 475 iterator end() { return iterator(DispatchBlock.succ_end()); } 476 477 ExplodedNode *generateNode(const iterator &I, 478 ProgramStateRef State, 479 bool isSink = false); 480 481 const Expr *getTarget() const { return E; } 482 483 ProgramStateRef getState() const { return Pred->State; } 484 485 const LocationContext *getLocationContext() const { 486 return Pred->getLocationContext(); 487 } 488}; 489 490class SwitchNodeBuilder { 491 CoreEngine& Eng; 492 const CFGBlock *Src; 493 const Expr *Condition; 494 ExplodedNode *Pred; 495 496public: 497 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 498 const Expr *condition, CoreEngine* eng) 499 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 500 501 class iterator { 502 CFGBlock::const_succ_reverse_iterator I; 503 504 friend class SwitchNodeBuilder; 505 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 506 507 public: 508 iterator &operator++() { ++I; return *this; } 509 bool operator!=(const iterator &X) const { return I != X.I; } 510 bool operator==(const iterator &X) const { return I == X.I; } 511 512 const CaseStmt *getCase() const { 513 return cast<CaseStmt>((*I)->getLabel()); 514 } 515 516 const CFGBlock *getBlock() const { 517 return *I; 518 } 519 }; 520 521 iterator begin() { return iterator(Src->succ_rbegin()+1); } 522 iterator end() { return iterator(Src->succ_rend()); } 523 524 const SwitchStmt *getSwitch() const { 525 return cast<SwitchStmt>(Src->getTerminator()); 526 } 527 528 ExplodedNode *generateCaseStmtNode(const iterator &I, 529 ProgramStateRef State); 530 531 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, 532 bool isSink = false); 533 534 const Expr *getCondition() const { return Condition; } 535 536 ProgramStateRef getState() const { return Pred->State; } 537 538 const LocationContext *getLocationContext() const { 539 return Pred->getLocationContext(); 540 } 541}; 542 543} // end ento namespace 544} // end clang namespace 545 546#endif 547