//===- AnalysisDeclContext.cpp - Analysis context for Path Sens analysis --===//
//
// 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 AnalysisDeclContext, a class that manages the analysis
// context data for path sensitive analysis.
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/Expr.h"
#include "clang/AST/LambdaCapture.h"
#include "clang/AST/ParentMap.h"
#include "clang/AST/PrettyPrinter.h"
#include "clang/AST/Stmt.h"
#include "clang/AST/StmtCXX.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
#include "clang/Analysis/BodyFarm.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/CFGStmtMap.h"
#include "clang/Analysis/Support/BumpVector.h"
#include "clang/Basic/JsonSupport.h"
#include "clang/Basic/LLVM.h"
#include "clang/Basic/SourceLocation.h"
#include "clang/Basic/SourceManager.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/SaveAndRestore.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <memory>

using namespace clang;

using ManagedAnalysisMap = llvm::DenseMap<const void *, std::unique_ptr<ManagedAnalysis>>;

AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
                                         const Decl *D,
                                         const CFG::BuildOptions &Options)
    : ADCMgr(ADCMgr), D(D), cfgBuildOptions(Options) {
  cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
}

AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
                                         const Decl *D)
    : ADCMgr(ADCMgr), D(D) {
  cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
}

AnalysisDeclContextManager::AnalysisDeclContextManager(
    ASTContext &ASTCtx, bool useUnoptimizedCFG, bool addImplicitDtors,
    bool addInitializers, bool addTemporaryDtors, bool addLifetime,
    bool addLoopExit, bool addScopes, bool synthesizeBodies,
    bool addStaticInitBranch, bool addCXXNewAllocator,
    bool addRichCXXConstructors, bool markElidedCXXConstructors,
    bool addVirtualBaseBranches, std::unique_ptr<CodeInjector> injector)
    : Injector(std::move(injector)), FunctionBodyFarm(ASTCtx, Injector.get()),
      SynthesizeBodies(synthesizeBodies) {
  cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
  cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
  cfgBuildOptions.AddInitializers = addInitializers;
  cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
  cfgBuildOptions.AddLifetime = addLifetime;
  cfgBuildOptions.AddLoopExit = addLoopExit;
  cfgBuildOptions.AddScopes = addScopes;
  cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
  cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
  cfgBuildOptions.AddRichCXXConstructors = addRichCXXConstructors;
  cfgBuildOptions.MarkElidedCXXConstructors = markElidedCXXConstructors;
  cfgBuildOptions.AddVirtualBaseBranches = addVirtualBaseBranches;
}

void AnalysisDeclContextManager::clear() { Contexts.clear(); }

Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const {
  IsAutosynthesized = false;
  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
    Stmt *Body = FD->getBody();
    if (auto *CoroBody = dyn_cast_or_null<CoroutineBodyStmt>(Body))
      Body = CoroBody->getBody();
    if (ADCMgr && ADCMgr->synthesizeBodies()) {
      Stmt *SynthesizedBody = ADCMgr->getBodyFarm().getBody(FD);
      if (SynthesizedBody) {
        Body = SynthesizedBody;
        IsAutosynthesized = true;
      }
    }
    return Body;
  }
  else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
    Stmt *Body = MD->getBody();
    if (ADCMgr && ADCMgr->synthesizeBodies()) {
      Stmt *SynthesizedBody = ADCMgr->getBodyFarm().getBody(MD);
      if (SynthesizedBody) {
        Body = SynthesizedBody;
        IsAutosynthesized = true;
      }
    }
    return Body;
  } else if (const auto *BD = dyn_cast<BlockDecl>(D))
    return BD->getBody();
  else if (const auto *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
    return FunTmpl->getTemplatedDecl()->getBody();
  else if (const auto *VD = dyn_cast_or_null<VarDecl>(D)) {
    if (VD->isFileVarDecl()) {
      return const_cast<Stmt *>(dyn_cast_or_null<Stmt>(VD->getInit()));
    }
  }

  llvm_unreachable("unknown code decl");
}

Stmt *AnalysisDeclContext::getBody() const {
  bool Tmp;
  return getBody(Tmp);
}

bool AnalysisDeclContext::isBodyAutosynthesized() const {
  bool Tmp;
  getBody(Tmp);
  return Tmp;
}

bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
  bool Tmp;
  Stmt *Body = getBody(Tmp);
  return Tmp && Body->getBeginLoc().isValid();
}

/// Returns true if \param VD is an Objective-C implicit 'self' parameter.
static bool isSelfDecl(const VarDecl *VD) {
  return isa_and_nonnull<ImplicitParamDecl>(VD) && VD->getName() == "self";
}

const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
  if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
    return MD->getSelfDecl();
  if (const auto *BD = dyn_cast<BlockDecl>(D)) {
    // See if 'self' was captured by the block.
    for (const auto &I : BD->captures()) {
      const VarDecl *VD = I.getVariable();
      if (isSelfDecl(VD))
        return dyn_cast<ImplicitParamDecl>(VD);
    }
  }

  auto *CXXMethod = dyn_cast<CXXMethodDecl>(D);
  if (!CXXMethod)
    return nullptr;

  const CXXRecordDecl *parent = CXXMethod->getParent();
  if (!parent->isLambda())
    return nullptr;

  for (const auto &LC : parent->captures()) {
    if (!LC.capturesVariable())
      continue;

    ValueDecl *VD = LC.getCapturedVar();
    if (isSelfDecl(dyn_cast<VarDecl>(VD)))
      return dyn_cast<ImplicitParamDecl>(VD);
  }

  return nullptr;
}

void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
  if (!forcedBlkExprs)
    forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
  // Default construct an entry for 'stmt'.
  if (const auto *e = dyn_cast<Expr>(stmt))
    stmt = e->IgnoreParens();
  (void) (*forcedBlkExprs)[stmt];
}

const CFGBlock *
AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
  assert(forcedBlkExprs);
  if (const auto *e = dyn_cast<Expr>(stmt))
    stmt = e->IgnoreParens();
  CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
    forcedBlkExprs->find(stmt);
  assert(itr != forcedBlkExprs->end());
  return itr->second;
}

/// Add each synthetic statement in the CFG to the parent map, using the
/// source statement's parent.
static void addParentsForSyntheticStmts(const CFG *TheCFG, ParentMap &PM) {
  if (!TheCFG)
    return;

  for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
                                    E = TheCFG->synthetic_stmt_end();
       I != E; ++I) {
    PM.setParent(I->first, PM.getParent(I->second));
  }
}

CFG *AnalysisDeclContext::getCFG() {
  if (!cfgBuildOptions.PruneTriviallyFalseEdges)
    return getUnoptimizedCFG();

  if (!builtCFG) {
    cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
    // Even when the cfg is not successfully built, we don't
    // want to try building it again.
    builtCFG = true;

    if (PM)
      addParentsForSyntheticStmts(cfg.get(), *PM);

    // The Observer should only observe one build of the CFG.
    getCFGBuildOptions().Observer = nullptr;
  }
  return cfg.get();
}

CFG *AnalysisDeclContext::getUnoptimizedCFG() {
  if (!builtCompleteCFG) {
    SaveAndRestore NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges, false);
    completeCFG =
        CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
    // Even when the cfg is not successfully built, we don't
    // want to try building it again.
    builtCompleteCFG = true;

    if (PM)
      addParentsForSyntheticStmts(completeCFG.get(), *PM);

    // The Observer should only observe one build of the CFG.
    getCFGBuildOptions().Observer = nullptr;
  }
  return completeCFG.get();
}

const CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
  if (cfgStmtMap)
    return &*cfgStmtMap;

  if (const CFG *c = getCFG()) {
    cfgStmtMap.emplace(*c, getParentMap());
    return &*cfgStmtMap;
  }

  return nullptr;
}

CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
  if (CFA)
    return CFA.get();

  if (CFG *c = getCFG()) {
    CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
    return CFA.get();
  }

  return nullptr;
}

void AnalysisDeclContext::dumpCFG(bool ShowColors) {
  getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
}

ParentMap &AnalysisDeclContext::getParentMap() {
  if (!PM) {
    PM.reset(new ParentMap(getBody()));
    if (const auto *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
      for (const auto *I : C->inits()) {
        PM->addStmt(I->getInit());
      }
    }
    if (builtCFG)
      addParentsForSyntheticStmts(getCFG(), *PM);
    if (builtCompleteCFG)
      addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
  }
  return *PM;
}

AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
    // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
    // that has the body.
    FD->hasBody(FD);
    D = FD;
  }

  std::unique_ptr<AnalysisDeclContext> &AC = Contexts[D];
  if (!AC)
    AC = std::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
  return AC.get();
}

BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }

const StackFrame *
AnalysisDeclContext::getStackFrame(const StackFrame *ParentSF, const void *Data,
                                   const Expr *E, const CFGBlock *Blk,
                                   unsigned BlockCount, unsigned Index) {
  return getStackFrameManager().getStackFrame(this, ParentSF, Data, E, Blk,
                                              BlockCount, Index);
}

bool AnalysisDeclContext::isInStdNamespace(const Decl *D) {
  const DeclContext *DC = D->getDeclContext()->getEnclosingNamespaceContext();
  const auto *ND = dyn_cast<NamespaceDecl>(DC);
  if (!ND)
    return false;

  while (const DeclContext *Parent = ND->getParent()) {
    if (!isa<NamespaceDecl>(Parent))
      break;
    ND = cast<NamespaceDecl>(Parent);
  }

  return ND->isStdNamespace();
}

std::string AnalysisDeclContext::getFunctionName(const Decl *D) {
  std::string Str;
  llvm::raw_string_ostream OS(Str);
  const ASTContext &Ctx = D->getASTContext();

  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
    OS << FD->getQualifiedNameAsString();

    // In C++, there are overloads.

    if (Ctx.getLangOpts().CPlusPlus) {
      OS << '(';
      for (const auto &P : FD->parameters()) {
        if (P != *FD->param_begin())
          OS << ", ";
        OS << P->getType();
      }
      OS << ')';
    }

  } else if (isa<BlockDecl>(D)) {
    PresumedLoc Loc = Ctx.getSourceManager().getPresumedLoc(D->getLocation());

    if (Loc.isValid()) {
      OS << "block (line: " << Loc.getLine() << ", col: " << Loc.getColumn()
         << ')';
    }

  } else if (const ObjCMethodDecl *OMD = dyn_cast<ObjCMethodDecl>(D)) {

    // FIXME: copy-pasted from CGDebugInfo.cpp.
    OS << (OMD->isInstanceMethod() ? '-' : '+') << '[';
    const DeclContext *DC = OMD->getDeclContext();
    if (const auto *OID = dyn_cast<ObjCImplementationDecl>(DC)) {
      OS << OID->getName();
    } else if (const auto *OID = dyn_cast<ObjCInterfaceDecl>(DC)) {
      OS << OID->getName();
    } else if (const auto *OC = dyn_cast<ObjCCategoryDecl>(DC)) {
      if (OC->IsClassExtension()) {
        OS << OC->getClassInterface()->getName();
      } else {
        OS << OC->getIdentifier()->getNameStart() << '('
           << OC->getIdentifier()->getNameStart() << ')';
      }
    } else if (const auto *OCD = dyn_cast<ObjCCategoryImplDecl>(DC)) {
      OS << OCD->getClassInterface()->getName() << '(' << OCD->getName() << ')';
    }
    OS << ' ' << OMD->getSelector().getAsString() << ']';
  }

  return Str;
}

StackFrameManager &AnalysisDeclContext::getStackFrameManager() {
  assert(ADCMgr &&
         "Cannot create StackFrames without an AnalysisDeclContextManager!");
  return ADCMgr->getStackFrameManager();
}

//===----------------------------------------------------------------------===//
// FoldingSet profiling.
//===----------------------------------------------------------------------===//

void StackFrame::Profile(llvm::FoldingSetNodeID &ID) {
  Profile(ID, getAnalysisDeclContext(), getParent(), Data, CallSite, Block,
          BlockCount, Index);
}

//===----------------------------------------------------------------------===//
// StackFrame creation.
//===----------------------------------------------------------------------===//

const StackFrame *StackFrameManager::getStackFrame(
    AnalysisDeclContext *Ctx, const StackFrame *Parent, const void *Data,
    const Expr *E, const CFGBlock *B, unsigned BlockCount, unsigned StmtIdx) {
  llvm::FoldingSetNodeID ID;
  StackFrame::Profile(ID, Ctx, Parent, Data, E, B, BlockCount, StmtIdx);
  void *InsertPos;
  StackFrame *SF = Frames.FindNodeOrInsertPos(ID, InsertPos);
  if (!SF) {
    SF = new StackFrame(Ctx, Parent, Data, E, B, BlockCount, StmtIdx, ++NewID);
    Frames.InsertNode(SF, InsertPos);
  }
  return SF;
}

//===----------------------------------------------------------------------===//
// StackFrame methods.
//===----------------------------------------------------------------------===//

bool StackFrame::isParentOf(const StackFrame *SF) const {
  return llvm::any_of(SF->parents(),
                      [this](const StackFrame &A) { return &A == this; });
}

static void printLocation(raw_ostream &Out, const SourceManager &SM,
                          SourceLocation Loc) {
  if (Loc.isFileID() && SM.isInMainFile(Loc))
    Out << SM.getExpansionLineNumber(Loc);
  else
    Loc.print(Out, SM);
}

void StackFrame::dumpStack(raw_ostream &Out) const {
  ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
  PrintingPolicy PP(Ctx.getLangOpts());
  PP.TerseOutput = 1;

  const SourceManager &SM =
      getAnalysisDeclContext()->getASTContext().getSourceManager();

  for (auto [Idx, SF] : llvm::enumerate(parentsIncludingSelf())) {
    Out << "\t#" << Idx << ' ';
    if (const auto *D = dyn_cast<NamedDecl>(SF.getDecl()))
      Out << "Calling " << AnalysisDeclContext::getFunctionName(D);
    else
      Out << "Calling anonymous code";
    if (const Expr *E = SF.getCallSite()) {
      Out << " at line ";
      printLocation(Out, SM, E->getBeginLoc());
    }
    Out << '\n';
  }
}

void StackFrame::printJson(
    raw_ostream &Out, const char *NL, unsigned int Space, bool IsDot,
    std::function<void(const StackFrame *)> printMoreInfoPerStackFrame) const {
  ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
  PrintingPolicy PP(Ctx.getLangOpts());
  PP.TerseOutput = 1;

  const SourceManager &SM =
      getAnalysisDeclContext()->getASTContext().getSourceManager();

  for (auto [Idx, SF] : llvm::enumerate(parentsIncludingSelf())) {
    Indent(Out, Space, IsDot)
        << "{ \"lctx_id\": " << SF.getID() << ", \"location_context\": \"";
    Out << '#' << Idx << " Call\", \"calling\": \"";
    if (const auto *D = dyn_cast<NamedDecl>(SF.getDecl()))
      Out << D->getQualifiedNameAsString();
    else
      Out << "anonymous code";

    Out << "\", \"location\": ";
    if (const Expr *E = SF.getCallSite()) {
      printSourceLocationAsJson(Out, E->getBeginLoc(), SM);
    } else {
      Out << "null";
    }

    Out << ", \"items\": ";

    printMoreInfoPerStackFrame(&SF);

    Out << '}';
    if (SF.getParent())
      Out << ',';
    Out << NL;
  }
}

LLVM_DUMP_METHOD void StackFrame::dump() const { printJson(llvm::errs()); }

//===----------------------------------------------------------------------===//
// Lazily generated map to query the external variables referenced by a Block.
//===----------------------------------------------------------------------===//

namespace {

class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
  BumpVector<const VarDecl *> &BEVals;
  BumpVectorContext &BC;
  llvm::SmallPtrSet<const VarDecl *, 4> Visited;
  llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;

public:
  FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
                            BumpVectorContext &bc)
      : BEVals(bevals), BC(bc) {}

  void VisitStmt(Stmt *S) {
    for (auto *Child : S->children())
      if (Child)
        Visit(Child);
  }

  void VisitDeclRefExpr(DeclRefExpr *DR) {
    // Non-local variables are also directly modified.
    if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
      if (!VD->hasLocalStorage()) {
        if (Visited.insert(VD).second)
          BEVals.push_back(VD, BC);
      }
    }
  }

  void VisitBlockExpr(BlockExpr *BR) {
    // Blocks containing blocks can transitively capture more variables.
    IgnoredContexts.insert(BR->getBlockDecl());
    Visit(BR->getBlockDecl()->getBody());
  }

  void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
    for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
         et = PE->semantics_end(); it != et; ++it) {
      Expr *Semantic = *it;
      if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
        Semantic = OVE->getSourceExpr();
      Visit(Semantic);
    }
  }
};

} // namespace

using DeclVec = BumpVector<const VarDecl *>;

static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
                                              void *&Vec,
                                              llvm::BumpPtrAllocator &A) {
  if (Vec)
    return (DeclVec*) Vec;

  BumpVectorContext BC(A);
  DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
  new (BV) DeclVec(BC, 10);

  // Go through the capture list.
  for (const auto &CI : BD->captures()) {
    BV->push_back(CI.getVariable(), BC);
  }

  // Find the referenced global/static variables.
  FindBlockDeclRefExprsVals F(*BV, BC);
  F.Visit(BD->getBody());

  Vec = BV;
  return BV;
}

llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
  if (!ReferencedBlockVars)
    ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();

  const DeclVec *V =
      LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
  return llvm::make_range(V->begin(), V->end());
}

std::unique_ptr<ManagedAnalysis> &AnalysisDeclContext::getAnalysisImpl(const void *tag) {
  if (!ManagedAnalyses)
    ManagedAnalyses = new ManagedAnalysisMap();
  ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
  return (*M)[tag];
}

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

ManagedAnalysis::~ManagedAnalysis() = default;

AnalysisDeclContext::~AnalysisDeclContext() {
  delete forcedBlkExprs;
  delete ReferencedBlockVars;
  delete (ManagedAnalysisMap*) ManagedAnalyses;
}

StackFrameManager::~StackFrameManager() { clear(); }

void StackFrameManager::clear() {
  for (llvm::FoldingSet<StackFrame>::iterator I = Frames.begin(),
                                              E = Frames.end();
       I != E;) {
    StackFrame *SF = &*I;
    ++I;
    delete SF;
  }
  Frames.clear();
}