/// Look through a chain of LocationContexts to either find the
/// StackFrameContext that matches a DeclContext, or find a VarRegion
/// for a variable captured by a block.
static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
                                      const DeclContext *DC,
                                      const VarDecl *VD) {
  while (LC) {
    if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
      if (cast<DeclContext>(SFC->getDecl()) == DC)
        return SFC;
    }
    if (const BlockInvocationContext *BC =
        dyn_cast<BlockInvocationContext>(LC)) {
      const BlockDataRegion *BR =
        static_cast<const BlockDataRegion*>(BC->getContextData());
      // FIXME: This can be made more efficient.
      for (BlockDataRegion::referenced_vars_iterator
           I = BR->referenced_vars_begin(),
           E = BR->referenced_vars_end(); I != E; ++I) {
        if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion()))
          if (VR->getDecl() == VD)
            return cast<VarRegion>(I.getCapturedRegion());
      }
    }
    
    LC = LC->getParent();
  }
  return (const StackFrameContext*)0;
}

void BlockDataRegion::dumpToStream(raw_ostream &os) const {
  os << "block_data{" << BC;
  os << "; ";
  for (BlockDataRegion::referenced_vars_iterator
         I = referenced_vars_begin(),
         E = referenced_vars_end(); I != E; ++I)
    os << "(" << I.getCapturedRegion() << "," <<
                 I.getOriginalRegion() << ") ";
  os << '}';
}

SmallVector<const MemRegion *, 4>
StackAddrEscapeChecker::getCapturedStackRegions(const BlockDataRegion &B,
                                                CheckerContext &C) {
  SmallVector<const MemRegion *, 4> Regions;
  BlockDataRegion::referenced_vars_iterator I = B.referenced_vars_begin();
  BlockDataRegion::referenced_vars_iterator E = B.referenced_vars_end();
  for (; I != E; ++I) {
    SVal Val = C.getState()->getSVal(I.getCapturedRegion());
    const MemRegion *Region = Val.getAsRegion();
    if (Region && isa<StackSpaceRegion>(Region->getMemorySpace()))
      Regions.push_back(Region);
  }
  return Regions;
}

void
UndefCapturedBlockVarChecker::checkPostStmt(const BlockExpr *BE,
                                            CheckerContext &C) const {
  if (!BE->getBlockDecl()->hasCaptures())
    return;

  ProgramStateRef state = C.getState();
  const BlockDataRegion *R =
    cast<BlockDataRegion>(state->getSVal(BE,
                                         C.getLocationContext()).getAsRegion());

  BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
                                            E = R->referenced_vars_end();

  for (; I != E; ++I) {
    // This VarRegion is the region associated with the block; we need
    // the one associated with the encompassing context.
    const VarRegion *VR = I.getCapturedRegion();
    const VarDecl *VD = VR->getDecl();

    if (VD->hasAttr<BlocksAttr>() || !VD->hasLocalStorage())
      continue;

    // Get the VarRegion associated with VD in the local stack frame.
    if (Optional<UndefinedVal> V =
          state->getSVal(I.getOriginalRegion()).getAs<UndefinedVal>()) {
      if (ExplodedNode *N = C.generateSink()) {
        if (!BT)
          BT.reset(
              new BuiltinBug(this, "uninitialized variable captured by block"));

        // Generate a bug report.
        SmallString<128> buf;
        llvm::raw_svector_ostream os(buf);

        os << "Variable '" << VD->getName()
           << "' is uninitialized when captured by block";

        BugReport *R = new BugReport(*BT, os.str(), N);
        if (const Expr *Ex = FindBlockDeclRefExpr(BE->getBody(), VD))
          R->addRange(Ex->getSourceRange());
        R->addVisitor(llvm::make_unique<FindLastStoreBRVisitor>(
            *V, VR, /*EnableNullFPSuppression*/ false));
        R->disablePathPruning();
        // need location of block
        C.emitReport(R);
      }
    }
  }
}

bool ScanReachableSymbols::scan(const MemRegion *R) {
  if (isa<MemSpaceRegion>(R))
    return true;
  
  unsigned &isVisited = visited[R];
  if (isVisited)
    return true;
  isVisited = 1;
  
  
  if (!visitor.VisitMemRegion(R))
    return false;

  // If this is a symbolic region, visit the symbol for the region.
  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
    if (!visitor.VisitSymbol(SR->getSymbol()))
      return false;

  // If this is a subregion, also visit the parent regions.
  if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
    const MemRegion *Super = SR->getSuperRegion();
    if (!scan(Super))
      return false;

    // When we reach the topmost region, scan all symbols in it.
    if (isa<MemSpaceRegion>(Super)) {
      StoreManager &StoreMgr = state->getStateManager().getStoreManager();
      if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
        return false;
    }
  }

  // Regions captured by a block are also implicitly reachable.
  if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
    BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
                                              E = BDR->referenced_vars_end();
    for ( ; I != E; ++I) {
      if (!scan(I.getCapturedRegion()))
        return false;
    }
  }

  return true;
}

bool ScanReachableSymbols::scan(const MemRegion *R) {
  if (isa<MemSpaceRegion>(R))
    return true;
  
  unsigned &isVisited = visited[R];
  if (isVisited)
    return true;
  isVisited = 1;
  
  
  if (!visitor.VisitMemRegion(R))
    return false;

  // If this is a symbolic region, visit the symbol for the region.
  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
    if (!visitor.VisitSymbol(SR->getSymbol()))
      return false;

  // If this is a subregion, also visit the parent regions.
  if (const SubRegion *SR = dyn_cast<SubRegion>(R))
    if (!scan(SR->getSuperRegion()))
      return false;

  // Regions captured by a block are also implicitly reachable.
  if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
    BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
                                              E = BDR->referenced_vars_end();
    for ( ; I != E; ++I) {
      if (!scan(I.getCapturedRegion()))
        return false;
    }
  }

  // Now look at the binding to this region (if any).
  if (!scan(state->getSValAsScalarOrLoc(R)))
    return false;

  // Now look at the subregions.
  if (!SRM.get())
    SRM.reset(state->getStateManager().getStoreManager().
                                           getSubRegionMap(state->getStore()));

  return SRM->iterSubRegions(R, *this);
}

void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
                                ExplodedNodeSet &Dst) {

  CanQualType T = getContext().getCanonicalType(BE->getType());

  // Get the value of the block itself.
  SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T,
                                       Pred->getLocationContext(),
                                       currBldrCtx->blockCount());

  ProgramStateRef State = Pred->getState();

  // If we created a new MemRegion for the block, we should explicitly bind
  // the captured variables.
  if (const BlockDataRegion *BDR =
      dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) {

    BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
                                              E = BDR->referenced_vars_end();

    for (; I != E; ++I) {
      const MemRegion *capturedR = I.getCapturedRegion();
      const MemRegion *originalR = I.getOriginalRegion();
      if (capturedR != originalR) {
        SVal originalV = State->getSVal(loc::MemRegionVal(originalR));
        State = State->bindLoc(loc::MemRegionVal(capturedR), originalV);
      }
    }
  }

  ExplodedNodeSet Tmp;
  StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
  Bldr.generateNode(BE, Pred,
                    State->BindExpr(BE, Pred->getLocationContext(), V),
                    nullptr, ProgramPoint::PostLValueKind);

  // FIXME: Move all post/pre visits to ::Visit().
  getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);
}

void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
                                ExplodedNodeSet &Dst) {

  CanQualType T = getContext().getCanonicalType(BE->getType());

  const BlockDecl *BD = BE->getBlockDecl();
  // Get the value of the block itself.
  SVal V = svalBuilder.getBlockPointer(BD, T,
                                       Pred->getLocationContext(),
                                       currBldrCtx->blockCount());

  ProgramStateRef State = Pred->getState();

  // If we created a new MemRegion for the block, we should explicitly bind
  // the captured variables.
  if (const BlockDataRegion *BDR =
      dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) {

    BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
                                              E = BDR->referenced_vars_end();

    auto CI = BD->capture_begin();
    auto CE = BD->capture_end();
    for (; I != E; ++I) {
      const VarRegion *capturedR = I.getCapturedRegion();
      const VarRegion *originalR = I.getOriginalRegion();

      // If the capture had a copy expression, use the result of evaluating
      // that expression, otherwise use the original value.
      // We rely on the invariant that the block declaration's capture variables
      // are a prefix of the BlockDataRegion's referenced vars (which may include
      // referenced globals, etc.) to enable fast lookup of the capture for a
      // given referenced var.
      const Expr *copyExpr = nullptr;
      if (CI != CE) {
        assert(CI->getVariable() == capturedR->getDecl());
        copyExpr = CI->getCopyExpr();
        CI++;
      }

      if (capturedR != originalR) {
        SVal originalV;
        const LocationContext *LCtx = Pred->getLocationContext();
        if (copyExpr) {
          originalV = State->getSVal(copyExpr, LCtx);
        } else {
          originalV = State->getSVal(loc::MemRegionVal(originalR));
        }
        State = State->bindLoc(loc::MemRegionVal(capturedR), originalV, LCtx);
      }
    }
  }

  ExplodedNodeSet Tmp;
  StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
  Bldr.generateNode(BE, Pred,
                    State->BindExpr(BE, Pred->getLocationContext(), V),
                    nullptr, ProgramPoint::PostLValueKind);

  // FIXME: Move all post/pre visits to ::Visit().
  getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);
}