1294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- C++ -*-===//
2294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
3294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//                     The LLVM Compiler Infrastructure
4294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
5294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// This file is distributed under the University of Illinois Open Source
6294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// License. See LICENSE.TXT for details.
7294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
8294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//===----------------------------------------------------------------------===//
9294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
10294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//  This file defines ExprEngine's support for calls and returns.
11294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
12294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//===----------------------------------------------------------------------===//
13294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
14294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
15ac7cc2d37e82181e73fcc265c1d0a619d18b7605Jordan Rose#include "PrettyStackTraceLocationContext.h"
1648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose#include "clang/AST/CXXInheritance.h"
17294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek#include "clang/AST/DeclCXX.h"
186fe4dfbc9e5a7018763b1d898876d9b2b8ec3425Jordan Rose#include "clang/AST/ParentMap.h"
1955fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Analysis/Analyses/LiveVariables.h"
2055fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/CheckerManager.h"
2155fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
224a5f724538cbc275370c9504e8169ce92503256cBenjamin Kramer#include "llvm/ADT/SmallSet.h"
23e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks#include "llvm/ADT/Statistic.h"
244a5f724538cbc275370c9504e8169ce92503256cBenjamin Kramer#include "llvm/Support/SaveAndRestore.h"
25294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
26294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekusing namespace clang;
27294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekusing namespace ento;
28294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#define DEBUG_TYPE "ExprEngine"
306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines
31e90d3f847dcce76237078b67db8895eb7a24189eAnna ZaksSTATISTIC(NumOfDynamicDispatchPathSplits,
32e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks  "The # of times we split the path due to imprecise dynamic dispatch info");
33e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks
34210f5a28227c90d739298e3e6729e827858fe397Anna ZaksSTATISTIC(NumInlinedCalls,
35210f5a28227c90d739298e3e6729e827858fe397Anna Zaks  "The # of times we inlined a call");
36210f5a28227c90d739298e3e6729e827858fe397Anna Zaks
377959671d456c916706a5f61af609d8f1fc95decfAnna ZaksSTATISTIC(NumReachedInlineCountMax,
387959671d456c916706a5f61af609d8f1fc95decfAnna Zaks  "The # of times we reached inline count maximum");
397959671d456c916706a5f61af609d8f1fc95decfAnna Zaks
403070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenekvoid ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
413070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Get the entry block in the CFG of the callee.
420849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  const StackFrameContext *calleeCtx = CE.getCalleeContext();
43ac7cc2d37e82181e73fcc265c1d0a619d18b7605Jordan Rose  PrettyStackTraceLocationContext CrashInfo(calleeCtx);
44ac7cc2d37e82181e73fcc265c1d0a619d18b7605Jordan Rose
450849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  const CFG *CalleeCFG = calleeCtx->getCFG();
463070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  const CFGBlock *Entry = &(CalleeCFG->getEntry());
473070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
483070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Validate the CFG.
493070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  assert(Entry->empty());
503070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  assert(Entry->succ_size() == 1);
513070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
52651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines  // Get the solitary successor.
533070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  const CFGBlock *Succ = *(Entry->succ_begin());
543070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
553070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Construct an edge representing the starting location in the callee.
560849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  BlockEdge Loc(Entry, Succ, calleeCtx);
573070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
58e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose  ProgramStateRef state = Pred->getState();
593070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
603070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Construct a new node and add it to the worklist.
613070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  bool isNew;
623070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  ExplodedNode *Node = G.getNode(Loc, state, false, &isNew);
633070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  Node->addPredecessor(Pred, G);
643070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  if (isNew)
653070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek    Engine.getWorkList()->enqueue(Node);
66294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
67294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
680b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks// Find the last statement on the path to the exploded node and the
690b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks// corresponding Block.
700b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaksstatic std::pair<const Stmt*,
710b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                 const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  const Stmt *S = nullptr;
736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  const CFGBlock *Blk = nullptr;
740b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const StackFrameContext *SF =
750b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks          Node->getLocation().getLocationContext()->getCurrentStackFrame();
76888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose
77632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose  // Back up through the ExplodedGraph until we reach a statement node in this
78632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose  // stack frame.
79256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  while (Node) {
80256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    const ProgramPoint &PP = Node->getLocation();
81888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose
82632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose    if (PP.getLocationContext()->getCurrentStackFrame() == SF) {
837a95de68c093991047ed8d339479ccad51b88663David Blaikie      if (Optional<StmtPoint> SP = PP.getAs<StmtPoint>()) {
84632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        S = SP->getStmt();
85888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose        break;
867a95de68c093991047ed8d339479ccad51b88663David Blaikie      } else if (Optional<CallExitEnd> CEE = PP.getAs<CallExitEnd>()) {
87632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        S = CEE->getCalleeContext()->getCallSite();
88632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        if (S)
89632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose          break;
90632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose
91632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        // If there is no statement, this is an implicitly-generated call.
92632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        // We'll walk backwards over it and then continue the loop to find
93632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        // an actual statement.
947a95de68c093991047ed8d339479ccad51b88663David Blaikie        Optional<CallEnter> CE;
95632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        do {
96632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose          Node = Node->getFirstPred();
97632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose          CE = Node->getLocationAs<CallEnter>();
98632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        } while (!CE || CE->getCalleeContext() != CEE->getCalleeContext());
99632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose
100632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose        // Continue searching the graph.
1017a95de68c093991047ed8d339479ccad51b88663David Blaikie      } else if (Optional<BlockEdge> BE = PP.getAs<BlockEdge>()) {
1024ecca28e20410f5e2816c5ddff5cdeaf45fb74b5Jordan Rose        Blk = BE->getSrc();
103632e5022f68fcae3b68bbc90538a60f3ba20229fJordan Rose      }
1047a95de68c093991047ed8d339479ccad51b88663David Blaikie    } else if (Optional<CallEnter> CE = PP.getAs<CallEnter>()) {
105888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose      // If we reached the CallEnter for this function, it has no statements.
106888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose      if (CE->getCalleeContext() == SF)
107888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose        break;
108256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    }
109888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose
1108501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks    if (Node->pred_empty())
1116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines      return std::make_pair(nullptr, nullptr);
1128501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks
113888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose    Node = *Node->pred_begin();
114256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  }
115888c90ac0ef6baf7d47e86cf5cc4715707d223b1Jordan Rose
1166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  return std::make_pair(S, Blk);
117256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek}
118256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
11948314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose/// Adjusts a return value when the called function's return type does not
12048314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose/// match the caller's expression type. This can happen when a dynamic call
12148314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose/// is devirtualized, and the overridding method has a covariant (more specific)
12248314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose/// return type than the parent's method. For C++ objects, this means we need
12348314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose/// to add base casts.
12448314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rosestatic SVal adjustReturnValue(SVal V, QualType ExpectedTy, QualType ActualTy,
12548314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose                              StoreManager &StoreMgr) {
12648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // For now, the only adjustments we handle apply only to locations.
1275251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie  if (!V.getAs<Loc>())
12848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose    return V;
12948314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
13048314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // If the types already match, don't do any unnecessary work.
131e7ad14e18247ec6fc3d46b208829e3dac6d85a1dAnna Zaks  ExpectedTy = ExpectedTy.getCanonicalType();
132e7ad14e18247ec6fc3d46b208829e3dac6d85a1dAnna Zaks  ActualTy = ActualTy.getCanonicalType();
13348314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  if (ExpectedTy == ActualTy)
13448314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose    return V;
13548314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
13648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // No adjustment is needed between Objective-C pointer types.
13748314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  if (ExpectedTy->isObjCObjectPointerType() &&
13848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose      ActualTy->isObjCObjectPointerType())
13948314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose    return V;
14048314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
14148314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // C++ object pointers may need "derived-to-base" casts.
14248314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  const CXXRecordDecl *ExpectedClass = ExpectedTy->getPointeeCXXRecordDecl();
14348314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  const CXXRecordDecl *ActualClass = ActualTy->getPointeeCXXRecordDecl();
14448314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  if (ExpectedClass && ActualClass) {
14548314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose    CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
14648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose                       /*DetectVirtual=*/false);
14748314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose    if (ActualClass->isDerivedFrom(ExpectedClass, Paths) &&
14848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose        !Paths.isAmbiguous(ActualTy->getCanonicalTypeUnqualified())) {
14948314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose      return StoreMgr.evalDerivedToBase(V, Paths.front());
15048314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose    }
15148314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  }
15248314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
15348314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // Unfortunately, Objective-C does not enforce that overridden methods have
15448314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // covariant return types, so we can't assert that that never happens.
15548314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // Be safe and return UnknownVal().
15648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  return UnknownVal();
15748314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose}
15848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
1598501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaksvoid ExprEngine::removeDeadOnEndOfFunction(NodeBuilderContext& BC,
1608501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks                                           ExplodedNode *Pred,
1618501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks                                           ExplodedNodeSet &Dst) {
1628501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks  // Find the last statement in the function and the corresponding basic block.
1636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  const Stmt *LastSt = nullptr;
1646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  const CFGBlock *Blk = nullptr;
165651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines  std::tie(LastSt, Blk) = getLastStmt(Pred);
1668501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks  if (!Blk || !LastSt) {
16784c484545c5906ba55143e212b4a5275ab55889fJordan Rose    Dst.Add(Pred);
1688501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks    return;
1698501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks  }
1708501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks
17163bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  // Here, we destroy the current location context. We use the current
17263bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  // function's entire body as a diagnostic statement, with which the program
17363bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  // point will be associated. However, we only want to use LastStmt as a
17463bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  // reference for what to clean up if it's a ReturnStmt; otherwise, everything
17563bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  // is dead.
17684c484545c5906ba55143e212b4a5275ab55889fJordan Rose  SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
17763bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  const LocationContext *LCtx = Pred->getLocationContext();
17863bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose  removeDead(Pred, Dst, dyn_cast<ReturnStmt>(LastSt), LCtx,
17963bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose             LCtx->getAnalysisDeclContext()->getBody(),
1808501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks             ProgramPoint::PostStmtPurgeDeadSymbolsKind);
1818501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks}
1828501b7a1c4c4a9ba0ea6cb8e500e601ef3759debAnna Zaks
183bae930d4c69a624881e66f1628ee615e149362f7Anna Zaksstatic bool wasDifferentDeclUsedForInlining(CallEventRef<> Call,
184d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks    const StackFrameContext *calleeCtx) {
185d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks  const Decl *RuntimeCallee = calleeCtx->getDecl();
186d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks  const Decl *StaticDecl = Call->getDecl();
187bae930d4c69a624881e66f1628ee615e149362f7Anna Zaks  assert(RuntimeCallee);
188bae930d4c69a624881e66f1628ee615e149362f7Anna Zaks  if (!StaticDecl)
189bae930d4c69a624881e66f1628ee615e149362f7Anna Zaks    return true;
190d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks  return RuntimeCallee->getCanonicalDecl() != StaticDecl->getCanonicalDecl();
191d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks}
192d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks
193bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose/// Returns true if the CXXConstructExpr \p E was intended to construct a
194bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose/// prvalue for the region in \p V.
195bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose///
196bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose/// Note that we can't just test for rvalue vs. glvalue because
197bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose/// CXXConstructExprs embedded in DeclStmts and initializers are considered
198bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose/// rvalues by the AST, and the analyzer would like to treat them as lvalues.
199bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rosestatic bool isTemporaryPRValue(const CXXConstructExpr *E, SVal V) {
200bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose  if (E->isGLValue())
201bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose    return false;
202bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose
203bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose  const MemRegion *MR = V.getAsRegion();
204bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose  if (!MR)
205bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose    return false;
206bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose
207bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose  return isa<CXXTempObjectRegion>(MR);
208bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose}
209bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose
2100b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// The call exit is simulated with a sequence of nodes, which occur between
2110b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// CallExitBegin and CallExitEnd. The following operations occur between the
2120b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// two program points:
2130b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 1. CallExitBegin (triggers the start of call exit sequence)
2140b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 2. Bind the return value
2150b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 3. Run Remove dead bindings to clean up the dead symbols from the callee.
2160b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 4. CallExitEnd (switch to the caller context)
2170b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 5. PostStmt<CallExpr>
2180b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaksvoid ExprEngine::processCallExit(ExplodedNode *CEBNode) {
2190b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Step 1 CEBNode was generated before the call.
220ac7cc2d37e82181e73fcc265c1d0a619d18b7605Jordan Rose  PrettyStackTraceLocationContext CrashInfo(CEBNode->getLocationContext());
2210b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const StackFrameContext *calleeCtx =
2220b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      CEBNode->getLocationContext()->getCurrentStackFrame();
2237fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
2247fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  // The parent context might not be a stack frame, so make sure we
2257fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  // look up the first enclosing stack frame.
2267fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const StackFrameContext *callerCtx =
2277fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    calleeCtx->getParent()->getCurrentStackFrame();
2287fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
229294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  const Stmt *CE = calleeCtx->getCallSite();
2300b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  ProgramStateRef state = CEBNode->getState();
2310b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Find the last statement in the function and the corresponding basic block.
2326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  const Stmt *LastSt = nullptr;
2336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  const CFGBlock *Blk = nullptr;
234651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines  std::tie(LastSt, Blk) = getLastStmt(CEBNode);
2350b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
23648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // Generate a CallEvent /before/ cleaning the state, so that we can get the
23748314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  // correct value for 'this' (if necessary).
23848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  CallEventManager &CEMgr = getStateManager().getCallEventManager();
23948314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose  CallEventRef<> Call = CEMgr.getCaller(calleeCtx, state);
24048314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
241852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose  // Step 2: generate node with bound return value: CEBNode -> BindedRetNode.
2420b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
243294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // If the callee returns an expression, bind its value to CallExpr.
244852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose  if (CE) {
245852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose    if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) {
246852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose      const LocationContext *LCtx = CEBNode->getLocationContext();
247852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose      SVal V = state->getSVal(RS, LCtx);
24848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
249d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks      // Ensure that the return type matches the type of the returned Expr.
250bae930d4c69a624881e66f1628ee615e149362f7Anna Zaks      if (wasDifferentDeclUsedForInlining(Call, calleeCtx)) {
251d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks        QualType ReturnedTy =
252d51db4935736fd943bfd46dfa74d41e9a3c2d41fAnna Zaks          CallEvent::getDeclaredResultType(calleeCtx->getDecl());
25348314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose        if (!ReturnedTy.isNull()) {
25448314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose          if (const Expr *Ex = dyn_cast<Expr>(CE)) {
25548314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose            V = adjustReturnValue(V, Ex->getType(), ReturnedTy,
25648314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose                                  getStoreManager());
25748314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose          }
25848314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose        }
25948314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose      }
26048314cf6a289bc5a082d8c769c58a38f924c93b7Jordan Rose
26157c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose      state = state->BindExpr(CE, callerCtx, V);
262852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose    }
2630b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
264852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose    // Bind the constructed object value to CXXConstructExpr.
265852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose    if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
266852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose      loc::MemRegionVal This =
267852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose        svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx);
268852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose      SVal ThisV = state->getSVal(This);
2690b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
270bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose      // If the constructed object is a temporary prvalue, get its bindings.
271bc403861bc4e6f7ad1371e9e129f0f25b38b3a9aJordan Rose      if (isTemporaryPRValue(CCE, ThisV))
2725251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie        ThisV = state->getSVal(ThisV.castAs<Loc>());
2730504a598a5dc8f3f45e79d4f8ea206a926507859Jordan Rose
27457c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose      state = state->BindExpr(CCE, callerCtx, ThisV);
275852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose    }
276294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  }
2770b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
2780b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Step 3: BindedRetNode -> CleanedNodes
2790b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // If we can find a statement and a block in the inlined function, run remove
2800b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // dead bindings before returning from the call. This is important to ensure
2810b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // that we report the issues such as leaks in the stack contexts in which
2820b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // they occurred.
2830b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  ExplodedNodeSet CleanedNodes;
284255d4d4226b24036ceb11228fbb74286e58620f7Ted Kremenek  if (LastSt && Blk && AMgr.options.AnalysisPurgeOpt != PurgeNone) {
285651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines    static SimpleProgramPointTag retValBind("ExprEngine", "Bind Return Value");
28648b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    PostStmt Loc(LastSt, calleeCtx, &retValBind);
28748b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    bool isNew;
28848b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew);
28948b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    BindedRetNode->addPredecessor(CEBNode, G);
29048b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    if (!isNew)
29148b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose      return;
29248b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose
2930b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode);
29466c486f275531df6362b3511fc3af6563561801bTed Kremenek    currBldrCtx = &Ctx;
29584c484545c5906ba55143e212b4a5275ab55889fJordan Rose    // Here, we call the Symbol Reaper with 0 statement and callee location
2960b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // context, telling it to clean up everything in the callee's context
29763bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose    // (and its children). We use the callee's function body as a diagnostic
29863bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose    // statement, with which the program point will be associated.
2996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines    removeDead(BindedRetNode, CleanedNodes, nullptr, calleeCtx,
30063bc186d6ac0b44ba4ec6fccb5f471b05c79b666Jordan Rose               calleeCtx->getAnalysisDeclContext()->getBody(),
3010b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks               ProgramPoint::PostStmtPurgeDeadSymbolsKind);
3026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines    currBldrCtx = nullptr;
303144e52be486a3906aec90c51b0ac94a30313152eAnna Zaks  } else {
304144e52be486a3906aec90c51b0ac94a30313152eAnna Zaks    CleanedNodes.Add(CEBNode);
3050b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  }
3060b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
3070b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
3080b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                                 E = CleanedNodes.end(); I != E; ++I) {
3090b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
3100b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Step 4: Generate the CallExit and leave the callee's context.
3110b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // CleanedNodes -> CEENode
312852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose    CallExitEnd Loc(calleeCtx, callerCtx);
3130b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    bool isNew;
31448b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    ProgramStateRef CEEState = (*I == CEBNode) ? state : (*I)->getState();
31548b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose    ExplodedNode *CEENode = G.getNode(Loc, CEEState, false, &isNew);
3160b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    CEENode->addPredecessor(*I, G);
3170b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    if (!isNew)
3180b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      return;
3190b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
3200b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Step 5: Perform the post-condition check of the CallExpr and enqueue the
3210b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // result onto the work list.
3220b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // CEENode -> Dst -> WorkList
3230b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode);
32466c486f275531df6362b3511fc3af6563561801bTed Kremenek    SaveAndRestore<const NodeBuilderContext*> NBCSave(currBldrCtx,
3250b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        &Ctx);
32666c486f275531df6362b3511fc3af6563561801bTed Kremenek    SaveAndRestore<unsigned> CBISave(currStmtIdx, calleeCtx->getIndex());
3270b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
3284e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose    CallEventRef<> UpdatedCall = Call.cloneWithState(CEEState);
32957c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose
33057c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose    ExplodedNodeSet DstPostCall;
3314e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose    getCheckerManager().runCheckersForPostCall(DstPostCall, CEENode,
3324e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose                                               *UpdatedCall, *this,
3334e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose                                               /*WasInlined=*/true);
33457c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose
33557c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose    ExplodedNodeSet Dst;
3364e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose    if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
3374e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose      getCheckerManager().runCheckersForPostObjCMessage(Dst, DstPostCall, *Msg,
3384e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose                                                        *this,
3394e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose                                                        /*WasInlined=*/true);
34057c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose    } else if (CE) {
34157c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose      getCheckerManager().runCheckersForPostStmt(Dst, DstPostCall, CE,
3424e79fdfe22db1c982e8fdf8397fee426a8c57821Jordan Rose                                                 *this, /*WasInlined=*/true);
34357c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose    } else {
34457c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose      Dst.insert(DstPostCall);
34557c033621dacd8720ac9ff65a09025f14f70e22fJordan Rose    }
3460b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
3470b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Enqueue the next element in the block.
3480b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
3490b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                                   PSI != PSE; ++PSI) {
3500b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
3510b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                                    calleeCtx->getIndex()+1);
3520b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    }
353242384ddb0e0b65dd7e9e0ac0cf3c31cf98b06a6Ted Kremenek  }
354294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
355294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
3564ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaksvoid ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx,
3577229d0011766c174beffe6a846d78f448f845b39Anna Zaks                               bool &IsRecursive, unsigned &StackDepth) {
3587229d0011766c174beffe6a846d78f448f845b39Anna Zaks  IsRecursive = false;
3597229d0011766c174beffe6a846d78f448f845b39Anna Zaks  StackDepth = 0;
3604ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks
3610849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  while (LCtx) {
3627229d0011766c174beffe6a846d78f448f845b39Anna Zaks    if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LCtx)) {
3634ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      const Decl *DI = SFC->getDecl();
3644ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks
3654ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      // Mark recursive (and mutually recursive) functions and always count
3664ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      // them when measuring the stack depth.
3674ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      if (DI == D) {
3687229d0011766c174beffe6a846d78f448f845b39Anna Zaks        IsRecursive = true;
3694ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks        ++StackDepth;
3704ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks        LCtx = LCtx->getParent();
3714ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks        continue;
3724ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      }
3734ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks
3744ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      // Do not count the small functions when determining the stack depth.
3754ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(DI);
3764ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      const CFG *CalleeCFG = CalleeADC->getCFG();
3774ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks      if (CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize())
3784ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks        ++StackDepth;
3797229d0011766c174beffe6a846d78f448f845b39Anna Zaks    }
3800849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek    LCtx = LCtx->getParent();
3810849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  }
3824ea9b89ff6dc50d5404eb56cad5e5870bce49ef2Anna Zaks
3830849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek}
3840849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek
38581fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rosestatic bool IsInStdNamespace(const FunctionDecl *FD) {
38681fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose  const DeclContext *DC = FD->getEnclosingNamespaceContext();
38781fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose  const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC);
38881fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose  if (!ND)
38981fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose    return false;
3906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines
39181fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose  while (const DeclContext *Parent = ND->getParent()) {
39281fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose    if (!isa<NamespaceDecl>(Parent))
39381fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose      break;
39481fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose    ND = cast<NamespaceDecl>(Parent);
39581fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose  }
39681fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose
3976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines  return ND->isStdNamespace();
39881fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose}
39981fb50e8b120fc95dc0245b4112972d4d7cca3b5Jordan Rose
400166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// The GDM component containing the dynamic dispatch bifurcation info. When
401166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// the exact type of the receiver is not known, we want to explore both paths -
402166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// one on which we do inline it and the other one on which we don't. This is
403166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// done to ensure we do not drop coverage.
404166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// This is the map from the receiver region to a bool, specifying either we
405166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose// consider this region's information precise or not along the given path.
406166d502d5367ceacd1313a33cac43b1048b8524dJordan Rosenamespace {
407166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose  enum DynamicDispatchMode {
408166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose    DynamicDispatchModeInlined = 1,
409166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose    DynamicDispatchModeConservative
410166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose  };
411166d502d5367ceacd1313a33cac43b1048b8524dJordan Rose}
41240d8551890bc8454c4e0a28c9072c9c1d1dd588aJordan RoseREGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap,
41340d8551890bc8454c4e0a28c9072c9c1d1dd588aJordan Rose                                 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *,
41440d8551890bc8454c4e0a28c9072c9c1d1dd588aJordan Rose                                                             unsigned))
415e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks
416e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaksbool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
417e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks                            NodeBuilder &Bldr, ExplodedNode *Pred,
418e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks                            ProgramStateRef State) {
419e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks  assert(D);
420ee158bc29bc12ce544996f7cdfde14aba63acf4dJordan Rose
421c36b30c92c78b95fd29fb5d9d6214d737b3bcb02Jordan Rose  const LocationContext *CurLC = Pred->getLocationContext();
422c36b30c92c78b95fd29fb5d9d6214d737b3bcb02Jordan Rose  const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
4238dadf15224f1a8df96793e5fc4e0b0e38a5ffbe4Anna Zaks  const LocationContext *ParentOfCallee = CallerSFC;
4248dadf15224f1a8df96793e5fc4e0b0e38a5ffbe4Anna Zaks  if (Call.getKind() == CE_Block) {
42569f87c956b3ac2b80124fd9604af012e1061473aJordan Rose    const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
426ee158bc29bc12ce544996f7cdfde14aba63acf4dJordan Rose    assert(BR && "If we have the block definition we should have its region");
42769f87c956b3ac2b80124fd9604af012e1061473aJordan Rose    AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D);
4287fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
42969f87c956b3ac2b80124fd9604af012e1061473aJordan Rose                                                         cast<BlockDecl>(D),
4307fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek                                                         BR);
431256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  }
4327fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
433852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose  // This may be NULL, but that's fine.
43469f87c956b3ac2b80124fd9604af012e1061473aJordan Rose  const Expr *CallE = Call.getOriginExpr();
43569f87c956b3ac2b80124fd9604af012e1061473aJordan Rose
4367fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  // Construct a new stack frame for the callee.
4377fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
4387fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const StackFrameContext *CalleeSFC =
43969f87c956b3ac2b80124fd9604af012e1061473aJordan Rose    CalleeADC->getStackFrame(ParentOfCallee, CallE,
44066c486f275531df6362b3511fc3af6563561801bTed Kremenek                             currBldrCtx->getBlock(),
44166c486f275531df6362b3511fc3af6563561801bTed Kremenek                             currStmtIdx);
4427fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
4438dadf15224f1a8df96793e5fc4e0b0e38a5ffbe4Anna Zaks
444c36b30c92c78b95fd29fb5d9d6214d737b3bcb02Jordan Rose  CallEnter Loc(CallE, CalleeSFC, CurLC);
445e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose
446e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose  // Construct a new state which contains the mapping from actual to
447e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose  // formal arguments.
448e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks  State = State->enterStackFrame(Call, CalleeSFC);
449e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose
4507fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  bool isNew;
451e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose  if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
4527fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    N->addPredecessor(Pred, G);
4537fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    if (isNew)
4547fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek      Engine.getWorkList()->enqueue(N);
4557fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  }
456e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks
457e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks  // If we decided to inline the call, the successor has been manually
458e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks  // added onto the work list so remove it from the node builder.
459e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks  Bldr.takeNodes(Pred);
460e90d3f847dcce76237078b67db8895eb7a24189eAnna Zaks
461210f5a28227c90d739298e3e6729e827858fe397Anna Zaks  NumInlinedCalls++;
462210f5a28227c90d739298e3e6729e827858fe397Anna Zaks
463fbcb3f11fc90e9f00e6074e9b118b8dc11ca604cAnna Zaks  // Mark the decl as visited.
464fbcb3f11fc90e9f00e6074e9b118b8dc11ca604cAnna Zaks  if (VisitedCallees)
465fbcb3f11fc90e9f00e6074e9b118b8dc11ca604cAnna Zaks    VisitedCallees->insert(D);
466fbcb3f11fc90e9f00e6074e9b118b8dc11ca604cAnna Zaks
4677fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  return true;
468256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek}
469256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
470e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaksstatic ProgramStateRef getInlineFailedState(ProgramStateRef State,
47169f87c956b3ac2b80124fd9604af012e1061473aJordan Rose                                            const Stmt *CallE) {
472bdc691f1d61765dd806d5ae3b75ae004f676a7c9Jordan Rose  const void *ReplayState = State->get<ReplayWithoutInlining>();
4735903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (!ReplayState)
4746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines    return nullptr;
47528038f33aa2db4833881fea757a1f0daf85ac02bJordan Rose
476bdc691f1d61765dd806d5ae3b75ae004f676a7c9Jordan Rose  assert(ReplayState == CallE && "Backtracked to the wrong call.");
47728038f33aa2db4833881fea757a1f0daf85ac02bJordan Rose  (void)CallE;
47828038f33aa2db4833881fea757a1f0daf85ac02bJordan Rose
479e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks  return State->remove<ReplayWithoutInlining>();
48010520d76044e8fff71d414f30c21b449fd104960Ted Kremenek}
48110520d76044e8fff71d414f30c21b449fd104960Ted Kremenek
482294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekvoid ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
483294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                               ExplodedNodeSet &dst) {
484294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Perform the previsit of the CallExpr.
485294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  ExplodedNodeSet dstPreVisit;
486294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
487500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
488d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // Get the call in its initial state. We use this as a template to perform
489d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // all the checks.
490d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  CallEventManager &CEMgr = getStateManager().getCallEventManager();
491645baeed6800f952e9ad1d5666e01080385531a2Jordan Rose  CallEventRef<> CallTemplate
492d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose    = CEMgr.getSimpleCall(CE, Pred->getState(), Pred->getLocationContext());
49369f87c956b3ac2b80124fd9604af012e1061473aJordan Rose
49469f87c956b3ac2b80124fd9604af012e1061473aJordan Rose  // Evaluate the function call.  We try each of the checkers
495294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // to see if the can evaluate the function call.
496294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  ExplodedNodeSet dstCallEvaluated;
49769f87c956b3ac2b80124fd9604af012e1061473aJordan Rose  for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
49869f87c956b3ac2b80124fd9604af012e1061473aJordan Rose       I != E; ++I) {
499d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose    evalCall(dstCallEvaluated, *I, *CallTemplate);
50069f87c956b3ac2b80124fd9604af012e1061473aJordan Rose  }
50169f87c956b3ac2b80124fd9604af012e1061473aJordan Rose
502294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Finally, perform the post-condition check of the CallExpr and store
503294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // the created nodes in 'Dst'.
50469f87c956b3ac2b80124fd9604af012e1061473aJordan Rose  // Note that if the call was inlined, dstCallEvaluated will be empty.
50569f87c956b3ac2b80124fd9604af012e1061473aJordan Rose  // The post-CallExpr check will occur in processCallExit.
506294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
507294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                                             *this);
508294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
509294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
51069f87c956b3ac2b80124fd9604af012e1061473aJordan Rosevoid ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
511645baeed6800f952e9ad1d5666e01080385531a2Jordan Rose                          const CallEvent &Call) {
512d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // WARNING: At this time, the state attached to 'Call' may be older than the
513d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // state in 'Pred'. This is a minor optimization since CheckerManager will
514d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // use an updated CallEvent instance when calling checkers, but if 'Call' is
515d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // ever used directly in this function all callers should be updated to pass
516d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // the most recent state. (It is probably not worth doing the work here since
517d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose  // for some callers this will not be necessary.)
518d563d3fb73879df7147b8a5302c3bf0e1402ba18Jordan Rose
51996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  // Run any pre-call checks using the generic call interface.
52096479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  ExplodedNodeSet dstPreVisit;
52196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this);
52296479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose
52396479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  // Actually evaluate the function call.  We try each of the checkers
52496479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  // to see if the can evaluate the function call, and get a callback at
52596479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  // defaultEvalCall if all of them fail.
52696479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  ExplodedNodeSet dstCallEvaluated;
52796479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit,
52896479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose                                             Call, *this);
52996479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose
53096479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  // Finally, run any post-call checks.
53196479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose  getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated,
53296479da6ad9d921d875e7be29fe1bfa127be8069Jordan Rose                                             Call, *this);
53369f87c956b3ac2b80124fd9604af012e1061473aJordan Rose}
53469f87c956b3ac2b80124fd9604af012e1061473aJordan Rose
535e81ce256b62717dd846bd19aecc4115a0dcd4995Anna ZaksProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call,
536e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks                                            const LocationContext *LCtx,
537e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks                                            ProgramStateRef State) {
538e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks  const Expr *E = Call.getOriginExpr();
539e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks  if (!E)
540e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    return State;
541e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks
542e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks  // Some method families have known return values.
543e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks  if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(&Call)) {
544e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    switch (Msg->getMethodFamily()) {
545e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    default:
546e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks      break;
547e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    case OMF_autorelease:
548e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    case OMF_retain:
549e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    case OMF_self: {
550e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks      // These methods return their receivers.
551e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks      return State->BindExpr(E, LCtx, Msg->getReceiverSVal());
552e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    }
553e81ce256b62717dd846bd19aecc4115a0dcd4995Anna Zaks    }
554