//===- ControlFlowContext.cpp ---------------------------------------------===//
//
// 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 ControlFlowContext class that is used by dataflow
//  analyses that run over Control-Flow Graphs (CFGs).
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/Decl.h"
#include "clang/AST/Stmt.h"
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/Support/Error.h"
#include <utility>

namespace clang {
namespace dataflow {

/// Returns a map from statements to basic blocks that contain them.
static llvm::DenseMap<const Stmt *, const CFGBlock *>
buildStmtToBasicBlockMap(const CFG &Cfg) {
  llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;
  for (const CFGBlock *Block : Cfg) {
    if (Block == nullptr)
      continue;

    for (const CFGElement &Element : *Block) {
      auto Stmt = Element.getAs<CFGStmt>();
      if (!Stmt)
        continue;

      StmtToBlock[Stmt->getStmt()] = Block;
    }
    if (const Stmt *TerminatorStmt = Block->getTerminatorStmt())
      StmtToBlock[TerminatorStmt] = Block;
  }
  return StmtToBlock;
}

static llvm::BitVector findReachableBlocks(const CFG &Cfg) {
  llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false);

  llvm::SmallVector<const CFGBlock *> BlocksToVisit;
  BlocksToVisit.push_back(&Cfg.getEntry());
  while (!BlocksToVisit.empty()) {
    const CFGBlock *Block = BlocksToVisit.back();
    BlocksToVisit.pop_back();

    if (BlockReachable[Block->getBlockID()])
      continue;

    BlockReachable[Block->getBlockID()] = true;

    for (const CFGBlock *Succ : Block->succs())
      if (Succ)
        BlocksToVisit.push_back(Succ);
  }

  return BlockReachable;
}

llvm::Expected<ControlFlowContext>
ControlFlowContext::build(const FunctionDecl &Func) {
  if (!Func.doesThisDeclarationHaveABody())
    return llvm::createStringError(
        std::make_error_code(std::errc::invalid_argument),
        "Cannot analyze function without a body");

  return build(Func, *Func.getBody(), Func.getASTContext());
}

llvm::Expected<ControlFlowContext>
ControlFlowContext::build(const Decl &D, Stmt &S, ASTContext &C) {
  if (D.isTemplated())
    return llvm::createStringError(
        std::make_error_code(std::errc::invalid_argument),
        "Cannot analyze templated declarations");

  // The shape of certain elements of the AST can vary depending on the
  // language. We currently only support C++.
  if (!C.getLangOpts().CPlusPlus)
    return llvm::createStringError(
        std::make_error_code(std::errc::invalid_argument),
        "Can only analyze C++");

  CFG::BuildOptions Options;
  Options.PruneTriviallyFalseEdges = true;
  Options.AddImplicitDtors = true;
  Options.AddTemporaryDtors = true;
  Options.AddInitializers = true;
  Options.AddCXXDefaultInitExprInCtors = true;
  Options.AddLifetime = true;

  // Ensure that all sub-expressions in basic blocks are evaluated.
  Options.setAllAlwaysAdd();

  auto Cfg = CFG::buildCFG(&D, &S, &C, Options);
  if (Cfg == nullptr)
    return llvm::createStringError(
        std::make_error_code(std::errc::invalid_argument),
        "CFG::buildCFG failed");

  llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
      buildStmtToBasicBlockMap(*Cfg);

  llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);

  return ControlFlowContext(D, std::move(Cfg), std::move(StmtToBlock),
                            std::move(BlockReachable));
}

} // namespace dataflow
} // namespace clang