llvm/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

//===- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -------------===//
//
// 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 the template classes ExplodedNode and ExplodedGraph,
//  which represent a path-sensitive, intra-procedural "exploded graph."
//
//===----------------------------------------------------------------------===//

#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ExprObjC.h"
#include "clang/AST/ParentMap.h"
#include "clang/AST/Stmt.h"
#include "clang/Analysis/CFGStmtMap.h"
#include "clang/Analysis/ProgramPoint.h"
#include "clang/Analysis/Support/BumpVector.h"
#include "clang/Basic/LLVM.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Casting.h"
#include <cassert>
#include <memory>
#include <optional>

usingnamespaceclang;
usingnamespaceento;

//===----------------------------------------------------------------------===//
// Cleanup.
//===----------------------------------------------------------------------===//

ExplodedGraph::ExplodedGraph() = default;

ExplodedGraph::~ExplodedGraph() = default;

//===----------------------------------------------------------------------===//
// Node reclamation.
//===----------------------------------------------------------------------===//

bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) { … }

bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { … }

void ExplodedGraph::collectNode(ExplodedNode *node) { … }

void ExplodedGraph::reclaimRecentlyAllocatedNodes() { … }

//===----------------------------------------------------------------------===//
// ExplodedNode.
//===----------------------------------------------------------------------===//

// An NodeGroup's storage type is actually very much like a TinyPtrVector:
// it can be either a pointer to a single ExplodedNode, or a pointer to a
// BumpVector allocated with the ExplodedGraph's allocator. This allows the
// common case of single-node NodeGroups to be implemented with no extra memory.
//
// Consequently, each of the NodeGroup methods have up to four cases to handle:
// 1. The flag is set and this group does not actually contain any nodes.
// 2. The group is empty, in which case the storage value is null.
// 3. The group contains a single node.
// 4. The group contains more than one node.
ExplodedNodeVector;
GroupStorage;

void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) { … }

void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) { … }

void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) { … }

unsigned ExplodedNode::NodeGroup::size() const { … }

ExplodedNode * const *ExplodedNode::NodeGroup::begin() const { … }

ExplodedNode * const *ExplodedNode::NodeGroup::end() const { … }

bool ExplodedNode::isTrivial() const { … }

const CFGBlock *ExplodedNode::getCFGBlock() const { … }

static const LocationContext *
findTopAutosynthesizedParentContext(const LocationContext *LC) { … }

const Stmt *ExplodedNode::getStmtForDiagnostics() const { … }

const Stmt *ExplodedNode::getNextStmtForDiagnostics() const { … }

const Stmt *ExplodedNode::getPreviousStmtForDiagnostics() const { … }

const Stmt *ExplodedNode::getCurrentOrPreviousStmtForDiagnostics() const { … }

ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
                                     ProgramStateRef State,
                                     bool IsSink,
                                     bool* IsNew) { … }

ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
                                                ProgramStateRef State,
                                                int64_t Id,
                                                bool IsSink) { … }

std::unique_ptr<ExplodedGraph>
ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
                    InterExplodedGraphMap *ForwardMap,
                    InterExplodedGraphMap *InverseMap) const { … }