summaryrefslogtreecommitdiff
path: root/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
diff options
context:
space:
mode:
Diffstat (limited to 'clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h')
-rw-r--r--clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h574
1 files changed, 574 insertions, 0 deletions
diff --git a/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
new file mode 100644
index 00000000..a01678ef
--- /dev/null
+++ b/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -0,0 +1,574 @@
+//===- CoreEngine.h - Path-Sensitive Dataflow Engine ------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a generic engine for intraprocedural, path-sensitive,
+// dataflow analysis via graph reachability.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
+
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/ProgramPoint.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
+#include <memory>
+#include <utility>
+#include <vector>
+
+namespace clang {
+
+class AnalyzerOptions;
+class CXXBindTemporaryExpr;
+class Expr;
+class LabelDecl;
+
+namespace ento {
+
+class FunctionSummariesTy;
+class SubEngine;
+
+//===----------------------------------------------------------------------===//
+/// CoreEngine - Implements the core logic of the graph-reachability
+/// analysis. It traverses the CFG and generates the ExplodedGraph.
+/// Program "states" are treated as opaque void pointers.
+/// The template class CoreEngine (which subclasses CoreEngine)
+/// provides the matching component to the engine that knows the actual types
+/// for states. Note that this engine only dispatches to transfer functions
+/// at the statement and block-level. The analyses themselves must implement
+/// any transfer function logic and the sub-expression level (if any).
+class CoreEngine {
+ friend class CommonNodeBuilder;
+ friend class EndOfFunctionNodeBuilder;
+ friend class ExprEngine;
+ friend class IndirectGotoNodeBuilder;
+ friend class NodeBuilder;
+ friend struct NodeBuilderContext;
+ friend class SwitchNodeBuilder;
+
+public:
+ using BlocksExhausted =
+ std::vector<std::pair<BlockEdge, const ExplodedNode *>>;
+
+ using BlocksAborted =
+ std::vector<std::pair<const CFGBlock *, const ExplodedNode *>>;
+
+private:
+ SubEngine &SubEng;
+
+ /// G - The simulation graph. Each node is a (location,state) pair.
+ mutable ExplodedGraph G;
+
+ /// WList - A set of queued nodes that need to be processed by the
+ /// worklist algorithm. It is up to the implementation of WList to decide
+ /// the order that nodes are processed.
+ std::unique_ptr<WorkList> WList;
+
+ /// BCounterFactory - A factory object for created BlockCounter objects.
+ /// These are used to record for key nodes in the ExplodedGraph the
+ /// number of times different CFGBlocks have been visited along a path.
+ BlockCounter::Factory BCounterFactory;
+
+ /// The locations where we stopped doing work because we visited a location
+ /// too many times.
+ BlocksExhausted blocksExhausted;
+
+ /// The locations where we stopped because the engine aborted analysis,
+ /// usually because it could not reason about something.
+ BlocksAborted blocksAborted;
+
+ /// The information about functions shared by the whole translation unit.
+ /// (This data is owned by AnalysisConsumer.)
+ FunctionSummariesTy *FunctionSummaries;
+
+ void generateNode(const ProgramPoint &Loc,
+ ProgramStateRef State,
+ ExplodedNode *Pred);
+
+ void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
+ void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
+ void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
+
+ void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred);
+
+ void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
+
+ void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
+ ExplodedNode *Pred);
+ void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
+ const CFGBlock *B, ExplodedNode *Pred);
+
+ /// Handle conditional logic for running static initializers.
+ void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
+ ExplodedNode *Pred);
+
+private:
+ ExplodedNode *generateCallExitBeginNode(ExplodedNode *N,
+ const ReturnStmt *RS);
+
+public:
+ /// Construct a CoreEngine object to analyze the provided CFG.
+ CoreEngine(SubEngine &subengine,
+ FunctionSummariesTy *FS,
+ AnalyzerOptions &Opts);
+
+ CoreEngine(const CoreEngine &) = delete;
+ CoreEngine &operator=(const CoreEngine &) = delete;
+
+ /// getGraph - Returns the exploded graph.
+ ExplodedGraph &getGraph() { return G; }
+
+ /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
+ /// steps. Returns true if there is still simulation state on the worklist.
+ bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
+ ProgramStateRef InitState);
+
+ /// Returns true if there is still simulation state on the worklist.
+ bool ExecuteWorkListWithInitialState(const LocationContext *L,
+ unsigned Steps,
+ ProgramStateRef InitState,
+ ExplodedNodeSet &Dst);
+
+ /// Dispatch the work list item based on the given location information.
+ /// Use Pred parameter as the predecessor state.
+ void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
+ const WorkListUnit& WU);
+
+ // Functions for external checking of whether we have unfinished work
+ bool wasBlockAborted() const { return !blocksAborted.empty(); }
+ bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
+ bool hasWorkRemaining() const { return wasBlocksExhausted() ||
+ WList->hasWork() ||
+ wasBlockAborted(); }
+
+ /// Inform the CoreEngine that a basic block was aborted because
+ /// it could not be completely analyzed.
+ void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
+ blocksAborted.push_back(std::make_pair(block, node));
+ }
+
+ WorkList *getWorkList() const { return WList.get(); }
+
+ BlocksExhausted::const_iterator blocks_exhausted_begin() const {
+ return blocksExhausted.begin();
+ }
+
+ BlocksExhausted::const_iterator blocks_exhausted_end() const {
+ return blocksExhausted.end();
+ }
+
+ BlocksAborted::const_iterator blocks_aborted_begin() const {
+ return blocksAborted.begin();
+ }
+
+ BlocksAborted::const_iterator blocks_aborted_end() const {
+ return blocksAborted.end();
+ }
+
+ /// Enqueue the given set of nodes onto the work list.
+ void enqueue(ExplodedNodeSet &Set);
+
+ /// Enqueue nodes that were created as a result of processing
+ /// a statement onto the work list.
+ void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
+
+ /// enqueue the nodes corresponding to the end of function onto the
+ /// end of path / work list.
+ void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS);
+
+ /// Enqueue a single node created as a result of statement processing.
+ void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
+};
+
+// TODO: Turn into a calss.
+struct NodeBuilderContext {
+ const CoreEngine &Eng;
+ const CFGBlock *Block;
+ const LocationContext *LC;
+
+ NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
+ : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
+
+ /// Return the CFGBlock associated with this builder.
+ const CFGBlock *getBlock() const { return Block; }
+
+ /// Returns the number of times the current basic block has been
+ /// visited on the exploded graph path.
+ unsigned blockCount() const {
+ return Eng.WList->getBlockCounter().getNumVisited(
+ LC->getStackFrame(),
+ Block->getBlockID());
+ }
+};
+
+/// \class NodeBuilder
+/// This is the simplest builder which generates nodes in the
+/// ExplodedGraph.
+///
+/// The main benefit of the builder is that it automatically tracks the
+/// frontier nodes (or destination set). This is the set of nodes which should
+/// be propagated to the next step / builder. They are the nodes which have been
+/// added to the builder (either as the input node set or as the newly
+/// constructed nodes) but did not have any outgoing transitions added.
+class NodeBuilder {
+ virtual void anchor();
+
+protected:
+ const NodeBuilderContext &C;
+
+ /// Specifies if the builder results have been finalized. For example, if it
+ /// is set to false, autotransitions are yet to be generated.
+ bool Finalized;
+
+ bool HasGeneratedNodes = false;
+
+ /// The frontier set - a set of nodes which need to be propagated after
+ /// the builder dies.
+ ExplodedNodeSet &Frontier;
+
+ /// Checks if the results are ready.
+ virtual bool checkResults() {
+ return Finalized;
+ }
+
+ bool hasNoSinksInFrontier() {
+ for (const auto I : Frontier)
+ if (I->isSink())
+ return false;
+ return true;
+ }
+
+ /// Allow subclasses to finalize results before result_begin() is executed.
+ virtual void finalizeResults() {}
+
+ ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
+ ProgramStateRef State,
+ ExplodedNode *Pred,
+ bool MarkAsSink = false);
+
+public:
+ NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &Ctx, bool F = true)
+ : C(Ctx), Finalized(F), Frontier(DstSet) {
+ Frontier.Add(SrcNode);
+ }
+
+ NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &Ctx, bool F = true)
+ : C(Ctx), Finalized(F), Frontier(DstSet) {
+ Frontier.insert(SrcSet);
+ assert(hasNoSinksInFrontier());
+ }
+
+ virtual ~NodeBuilder() = default;
+
+ /// Generates a node in the ExplodedGraph.
+ ExplodedNode *generateNode(const ProgramPoint &PP,
+ ProgramStateRef State,
+ ExplodedNode *Pred) {
+ return generateNodeImpl(PP, State, Pred, false);
+ }
+
+ /// Generates a sink in the ExplodedGraph.
+ ///
+ /// When a node is marked as sink, the exploration from the node is stopped -
+ /// the node becomes the last node on the path and certain kinds of bugs are
+ /// suppressed.
+ ExplodedNode *generateSink(const ProgramPoint &PP,
+ ProgramStateRef State,
+ ExplodedNode *Pred) {
+ return generateNodeImpl(PP, State, Pred, true);
+ }
+
+ const ExplodedNodeSet &getResults() {
+ finalizeResults();
+ assert(checkResults());
+ return Frontier;
+ }
+
+ using iterator = ExplodedNodeSet::iterator;
+
+ /// Iterators through the results frontier.
+ iterator begin() {
+ finalizeResults();
+ assert(checkResults());
+ return Frontier.begin();
+ }
+
+ iterator end() {
+ finalizeResults();
+ return Frontier.end();
+ }
+
+ const NodeBuilderContext &getContext() { return C; }
+ bool hasGeneratedNodes() { return HasGeneratedNodes; }
+
+ void takeNodes(const ExplodedNodeSet &S) {
+ for (const auto I : S)
+ Frontier.erase(I);
+ }
+
+ void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
+ void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
+ void addNodes(ExplodedNode *N) { Frontier.Add(N); }
+};
+
+/// \class NodeBuilderWithSinks
+/// This node builder keeps track of the generated sink nodes.
+class NodeBuilderWithSinks: public NodeBuilder {
+ void anchor() override;
+
+protected:
+ SmallVector<ExplodedNode*, 2> sinksGenerated;
+ ProgramPoint &Location;
+
+public:
+ NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &Ctx, ProgramPoint &L)
+ : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
+
+ ExplodedNode *generateNode(ProgramStateRef State,
+ ExplodedNode *Pred,
+ const ProgramPointTag *Tag = nullptr) {
+ const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
+ return NodeBuilder::generateNode(LocalLoc, State, Pred);
+ }
+
+ ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
+ const ProgramPointTag *Tag = nullptr) {
+ const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
+ ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
+ if (N && N->isSink())
+ sinksGenerated.push_back(N);
+ return N;
+ }
+
+ const SmallVectorImpl<ExplodedNode*> &getSinks() const {
+ return sinksGenerated;
+ }
+};
+
+/// \class StmtNodeBuilder
+/// This builder class is useful for generating nodes that resulted from
+/// visiting a statement. The main difference from its parent NodeBuilder is
+/// that it creates a statement specific ProgramPoint.
+class StmtNodeBuilder: public NodeBuilder {
+ NodeBuilder *EnclosingBldr;
+
+public:
+ /// Constructs a StmtNodeBuilder. If the builder is going to process
+ /// nodes currently owned by another builder(with larger scope), use
+ /// Enclosing builder to transfer ownership.
+ StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &Ctx,
+ NodeBuilder *Enclosing = nullptr)
+ : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
+ if (EnclosingBldr)
+ EnclosingBldr->takeNodes(SrcNode);
+ }
+
+ StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &Ctx,
+ NodeBuilder *Enclosing = nullptr)
+ : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
+ if (EnclosingBldr)
+ for (const auto I : SrcSet)
+ EnclosingBldr->takeNodes(I);
+ }
+
+ ~StmtNodeBuilder() override;
+
+ using NodeBuilder::generateNode;
+ using NodeBuilder::generateSink;
+
+ ExplodedNode *generateNode(const Stmt *S,
+ ExplodedNode *Pred,
+ ProgramStateRef St,
+ const ProgramPointTag *tag = nullptr,
+ ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
+ const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
+ Pred->getLocationContext(), tag);
+ return NodeBuilder::generateNode(L, St, Pred);
+ }
+
+ ExplodedNode *generateSink(const Stmt *S,
+ ExplodedNode *Pred,
+ ProgramStateRef St,
+ const ProgramPointTag *tag = nullptr,
+ ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
+ const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
+ Pred->getLocationContext(), tag);
+ return NodeBuilder::generateSink(L, St, Pred);
+ }
+};
+
+/// BranchNodeBuilder is responsible for constructing the nodes
+/// corresponding to the two branches of the if statement - true and false.
+class BranchNodeBuilder: public NodeBuilder {
+ const CFGBlock *DstT;
+ const CFGBlock *DstF;
+
+ bool InFeasibleTrue;
+ bool InFeasibleFalse;
+
+ void anchor() override;
+
+public:
+ BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &C,
+ const CFGBlock *dstT, const CFGBlock *dstF)
+ : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
+ InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
+ // The branch node builder does not generate autotransitions.
+ // If there are no successors it means that both branches are infeasible.
+ takeNodes(SrcNode);
+ }
+
+ BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
+ const NodeBuilderContext &C,
+ const CFGBlock *dstT, const CFGBlock *dstF)
+ : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
+ InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
+ takeNodes(SrcSet);
+ }
+
+ ExplodedNode *generateNode(ProgramStateRef State, bool branch,
+ ExplodedNode *Pred);
+
+ const CFGBlock *getTargetBlock(bool branch) const {
+ return branch ? DstT : DstF;
+ }
+
+ void markInfeasible(bool branch) {
+ if (branch)
+ InFeasibleTrue = true;
+ else
+ InFeasibleFalse = true;
+ }
+
+ bool isFeasible(bool branch) {
+ return branch ? !InFeasibleTrue : !InFeasibleFalse;
+ }
+};
+
+class IndirectGotoNodeBuilder {
+ CoreEngine& Eng;
+ const CFGBlock *Src;
+ const CFGBlock &DispatchBlock;
+ const Expr *E;
+ ExplodedNode *Pred;
+
+public:
+ IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
+ const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
+ : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
+
+ class iterator {
+ friend class IndirectGotoNodeBuilder;
+
+ CFGBlock::const_succ_iterator I;
+
+ iterator(CFGBlock::const_succ_iterator i) : I(i) {}
+
+ public:
+ iterator &operator++() { ++I; return *this; }
+ bool operator!=(const iterator &X) const { return I != X.I; }
+
+ const LabelDecl *getLabel() const {
+ return cast<LabelStmt>((*I)->getLabel())->getDecl();
+ }
+
+ const CFGBlock *getBlock() const {
+ return *I;
+ }
+ };
+
+ iterator begin() { return iterator(DispatchBlock.succ_begin()); }
+ iterator end() { return iterator(DispatchBlock.succ_end()); }
+
+ ExplodedNode *generateNode(const iterator &I,
+ ProgramStateRef State,
+ bool isSink = false);
+
+ const Expr *getTarget() const { return E; }
+
+ ProgramStateRef getState() const { return Pred->State; }
+
+ const LocationContext *getLocationContext() const {
+ return Pred->getLocationContext();
+ }
+};
+
+class SwitchNodeBuilder {
+ CoreEngine& Eng;
+ const CFGBlock *Src;
+ const Expr *Condition;
+ ExplodedNode *Pred;
+
+public:
+ SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
+ const Expr *condition, CoreEngine* eng)
+ : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
+
+ class iterator {
+ friend class SwitchNodeBuilder;
+
+ CFGBlock::const_succ_reverse_iterator I;
+
+ iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
+
+ public:
+ iterator &operator++() { ++I; return *this; }
+ bool operator!=(const iterator &X) const { return I != X.I; }
+ bool operator==(const iterator &X) const { return I == X.I; }
+
+ const CaseStmt *getCase() const {
+ return cast<CaseStmt>((*I)->getLabel());
+ }
+
+ const CFGBlock *getBlock() const {
+ return *I;
+ }
+ };
+
+ iterator begin() { return iterator(Src->succ_rbegin()+1); }
+ iterator end() { return iterator(Src->succ_rend()); }
+
+ const SwitchStmt *getSwitch() const {
+ return cast<SwitchStmt>(Src->getTerminator());
+ }
+
+ ExplodedNode *generateCaseStmtNode(const iterator &I,
+ ProgramStateRef State);
+
+ ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
+ bool isSink = false);
+
+ const Expr *getCondition() const { return Condition; }
+
+ ProgramStateRef getState() const { return Pred->State; }
+
+ const LocationContext *getLocationContext() const {
+ return Pred->getLocationContext();
+ }
+};
+
+} // namespace ento
+
+} // namespace clang
+
+#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-20 19:16:24 +0000