//===- ThreadSafetyCommon.h -------------------------------------*- C++ -*-===//

//

// 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

//

//===----------------------------------------------------------------------===//

//

// Parts of thread safety analysis that are not specific to thread safety

// itself have been factored into classes here, where they can be potentially

// used by other analyses.  Currently these include:

//

// * Generalize clang CFG visitors.

// * Conversion of the clang CFG to SSA form.

// * Translation of clang Exprs to TIL SExprs

//

// UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H

#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H

#include "clang/AST/Decl.h"

#include "clang/Analysis/Analyses/PostOrderCFGView.h"

#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"

#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"

#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"

#include "clang/Analysis/AnalysisDeclContext.h"

#include "clang/Analysis/CFG.h"

#include "clang/Basic/LLVM.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/Support/Casting.h"

#include <sstream>

#include <string>

#include <utility>

#include <vector>

namespace clang {

class AbstractConditionalOperator;

class ArraySubscriptExpr;

class BinaryOperator;

class CallExpr;

class CastExpr;

class CXXDestructorDecl;

class CXXMemberCallExpr;

class CXXOperatorCallExpr;

class CXXThisExpr;

class DeclRefExpr;

class DeclStmt;

class Expr;

class MemberExpr;

class Stmt;

class UnaryOperator;

namespace threadSafety {

// Various helper functions on til::SExpr

namespace sx {

inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {

  return til::EqualsComparator::compareExprs(E1, E2);

}

inline bool matches(const til::SExpr *E1, const til::SExpr *E2) {

  // We treat a top-level wildcard as the "univsersal" lock.

  // It matches everything for the purpose of checking locks, but not

  // for unlocking them.

  if (isa<til::Wildcard>(E1))

    return isa<til::Wildcard>(E2);

  if (isa<til::Wildcard>(E2))

    return isa<til::Wildcard>(E1);

  return til::MatchComparator::compareExprs(E1, E2);

}

inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {

  const auto *PE1 = dyn_cast_or_null<til::Project>(E1);

  if (!PE1)

    return false;

  const auto *PE2 = dyn_cast_or_null<til::Project>(E2);

  if (!PE2)

    return false;

  return PE1->clangDecl() == PE2->clangDecl();

}

inline std::string toString(const til::SExpr *E) {

  std::stringstream ss;

  til::StdPrinter::print(E, ss);

  return ss.str();

}

}  // namespace sx

// This class defines the interface of a clang CFG Visitor.

// CFGWalker will invoke the following methods.

// Note that methods are not virtual; the visitor is templatized.

class CFGVisitor {

  // Enter the CFG for Decl D, and perform any initial setup operations.

  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}

  // Enter a CFGBlock.

  void enterCFGBlock(const CFGBlock *B) {}

  // Returns true if this visitor implements handlePredecessor

  bool visitPredecessors() { return true; }

  // Process a predecessor edge.

  void handlePredecessor(const CFGBlock *Pred) {}

  // Process a successor back edge to a previously visited block.

  void handlePredecessorBackEdge(const CFGBlock *Pred) {}

  // Called just before processing statements.

  void enterCFGBlockBody(const CFGBlock *B) {}

  // Process an ordinary statement.

  void handleStatement(const Stmt *S) {}

  // Process a destructor call

  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}

  // Called after all statements have been handled.

  void exitCFGBlockBody(const CFGBlock *B) {}

  // Return true

  bool visitSuccessors() { return true; }

  // Process a successor edge.

  void handleSuccessor(const CFGBlock *Succ) {}

  // Process a successor back edge to a previously visited block.

  void handleSuccessorBackEdge(const CFGBlock *Succ) {}

  // Leave a CFGBlock.

  void exitCFGBlock(const CFGBlock *B) {}

  // Leave the CFG, and perform any final cleanup operations.

  void exitCFG(const CFGBlock *Last) {}

};

// Walks the clang CFG, and invokes methods on a given CFGVisitor.

class CFGWalker {

public:

  CFGWalker() = default;

  // Initialize the CFGWalker.  This setup only needs to be done once, even

  // if there are multiple passes over the CFG.

  bool init(AnalysisDeclContext &AC) {

    ACtx = ∾

    CFGraph = AC.getCFG();

    if (!CFGraph)

      return false;

    // Ignore anonymous functions.

    if (!dyn_cast_or_null<NamedDecl>(AC.getDecl()))

      return false;

    SortedGraph = AC.getAnalysis<PostOrderCFGView>();

    if (!SortedGraph)

      return false;

    return true;

  }

  // Traverse the CFG, calling methods on V as appropriate.

  template <class Visitor>

  void walk(Visitor &V) {

    PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);

    V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());

    for (const auto *CurrBlock : *SortedGraph) {

      VisitedBlocks.insert(CurrBlock);

      V.enterCFGBlock(CurrBlock);

      // Process predecessors, handling back edges last

      if (V.visitPredecessors()) {

        SmallVector<CFGBlock*, 4> BackEdges;

        // Process successors

        for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),

                                           SE = CurrBlock->pred_end();

             SI != SE; ++SI) {

          if (*SI == nullptr)

            continue;

          if (!VisitedBlocks.alreadySet(*SI)) {

            BackEdges.push_back(*SI);

            continue;

          }

          V.handlePredecessor(*SI);

        }

        for (auto *Blk : BackEdges)

          V.handlePredecessorBackEdge(Blk);

      }

      V.enterCFGBlockBody(CurrBlock);

      // Process statements

      for (const auto &BI : *CurrBlock) {

        switch (BI.getKind()) {

        case CFGElement::Statement:

          V.handleStatement(BI.castAs<CFGStmt>().getStmt());

          break;

        case CFGElement::AutomaticObjectDtor: {

          CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();

          auto *DD = const_cast<CXXDestructorDecl *>(

              AD.getDestructorDecl(ACtx->getASTContext()));

          auto *VD = const_cast<VarDecl *>(AD.getVarDecl());

          V.handleDestructorCall(VD, DD);

          break;

        }

        default:

          break;

        }

      }

      V.exitCFGBlockBody(CurrBlock);

      // Process successors, handling back edges first.

      if (V.visitSuccessors()) {

        SmallVector<CFGBlock*, 8> ForwardEdges;

        // Process successors

        for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),

                                           SE = CurrBlock->succ_end();

             SI != SE; ++SI) {

          if (*SI == nullptr)

            continue;

          if (!VisitedBlocks.alreadySet(*SI)) {

            ForwardEdges.push_back(*SI);

            continue;

          }

          V.handleSuccessorBackEdge(*SI);

        }

        for (auto *Blk : ForwardEdges)

          V.handleSuccessor(Blk);

      }

      V.exitCFGBlock(CurrBlock);

    }

    V.exitCFG(&CFGraph->getExit());

  }

  const CFG *getGraph() const { return CFGraph; }

  CFG *getGraph() { return CFGraph; }

  const NamedDecl *getDecl() const {

    return dyn_cast<NamedDecl>(ACtx->getDecl());

  }

  const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }

private:

  CFG *CFGraph = nullptr;

  AnalysisDeclContext *ACtx = nullptr;

  PostOrderCFGView *SortedGraph = nullptr;

};

// TODO: move this back into ThreadSafety.cpp

// This is specific to thread safety.  It is here because

// translateAttrExpr needs it, but that should be moved too.

class CapabilityExpr {

private:

  /// The capability expression.

  const til::SExpr* CapExpr;

  /// True if this is a negative capability.

  bool Negated;

public:

  CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}

  const til::SExpr* sexpr() const { return CapExpr; }

  bool negative() const { return Negated; }

  CapabilityExpr operator!() const {

    return CapabilityExpr(CapExpr, !Negated);

  }

  bool equals(const CapabilityExpr &other) const {

    return (Negated == other.Negated) && 
sx::equals(CapExpr, other.CapExpr)1.09k
;

  }

  bool matches(const CapabilityExpr &other) const {

    return (Negated == other.Negated) && 
sx::matches(CapExpr, other.CapExpr)13.0k
;

  }

  bool matchesUniv(const CapabilityExpr &CapE) const {

    return isUniversal() || 
matches(CapE)2.85k
;

  }

  bool partiallyMatches(const CapabilityExpr &other) const {

    return (Negated == other.Negated) &&

            sx::partiallyMatches(CapExpr, other.CapExpr);

  }

  const ValueDecl* valueDecl() const {

    if (Negated || 
CapExpr == nullptr2.37k
)

      return nullptr;

    if (const auto *P = dyn_cast<til::Project>(CapExpr))

      return P->clangDecl();

    if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr))

      return P->clangDecl();

    return nullptr;

  }

  std::string toString() const {

    if (Negated)

      return "!" + sx::toString(CapExpr);

    return sx::toString(CapExpr);

  }

  bool shouldIgnore() const { return CapExpr == nullptr; }

  bool isInvalid() const { return sexpr() && 
isa<til::Undefined>(sexpr())8.04k
; }

  bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }

};

// Translate clang::Expr to til::SExpr.

class SExprBuilder {

public:

  /// Encapsulates the lexical context of a function call.  The lexical

  /// context includes the arguments to the call, including the implicit object

  /// argument.  When an attribute containing a mutex expression is attached to

  /// a method, the expression may refer to formal parameters of the method.

  /// Actual arguments must be substituted for formal parameters to derive

  /// the appropriate mutex expression in the lexical context where the function

  /// is called.  PrevCtx holds the context in which the arguments themselves

  /// should be evaluated; multiple calling contexts can be chained together

  /// by the lock_returned attribute.

  struct CallingContext {

    // The previous context; or 0 if none.

    CallingContext  *Prev;

    // The decl to which the attr is attached.

    const NamedDecl *AttrDecl;

    // Implicit object argument -- e.g. 'this'

    const Expr *SelfArg = nullptr;

    // Number of funArgs

    unsigned NumArgs = 0;

    // Function arguments

    const Expr *const *FunArgs = nullptr;

    // is Self referred to with -> or .?

    bool SelfArrow = false;

    CallingContext(CallingContext *P, const NamedDecl *D = nullptr)

        : Prev(P), AttrDecl(D) {}

  };

  SExprBuilder(til::MemRegionRef A) : Arena(A) {

    // FIXME: we don't always have a self-variable.

    SelfVar = new (Arena) til::Variable(nullptr);

    SelfVar->setKind(til::Variable::VK_SFun);

  }

  // Translate a clang expression in an attribute to a til::SExpr.

  // Constructs the context from D, DeclExp, and SelfDecl.

  CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,

                                   const Expr *DeclExp, VarDecl *SelfD=nullptr);

  CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);

  // Translate a clang statement or expression to a TIL expression.

  // Also performs substitution of variables; Ctx provides the context.

  // Dispatches on the type of S.

  til::SExpr *translate(const Stmt *S, CallingContext *Ctx);

  til::SCFG  *buildCFG(CFGWalker &Walker);

  til::SExpr *lookupStmt(const Stmt *S);

  til::BasicBlock *lookupBlock(const CFGBlock *B) {

    return BlockMap[B->getBlockID()];

  }

  const til::SCFG *getCFG() const { return Scfg; }

  til::SCFG *getCFG() { return Scfg; }

private:

  // We implement the CFGVisitor API

  friend class CFGWalker;

  til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,

                                   CallingContext *Ctx) ;

  til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);

  til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);

  til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,

                                       CallingContext *Ctx);

  til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,

                                const Expr *SelfE = nullptr);

  til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,

                                         CallingContext *Ctx);

  til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,

                                           CallingContext *Ctx);

  til::SExpr *translateUnaryOperator(const UnaryOperator *UO,

                                     CallingContext *Ctx);

  til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,

                             const BinaryOperator *BO,

                             CallingContext *Ctx, bool Reverse = false);

  til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,

                                 const BinaryOperator *BO,

                                 CallingContext *Ctx, bool Assign = false);

  til::SExpr *translateBinaryOperator(const BinaryOperator *BO,

                                      CallingContext *Ctx);

  til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);

  til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,

                                          CallingContext *Ctx);

  til::SExpr *translateAbstractConditionalOperator(

      const AbstractConditionalOperator *C, CallingContext *Ctx);

  til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);

  // Map from statements in the clang CFG to SExprs in the til::SCFG.

  using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>;

  // Map from clang local variables to indices in a LVarDefinitionMap.

  using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>;

  // Map from local variable indices to SSA variables (or constants).

  using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>;

  using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>;

  struct BlockInfo {

    LVarDefinitionMap ExitMap;

    bool HasBackEdges = false;

    // Successors yet to be processed

    unsigned UnprocessedSuccessors = 0;

    // Predecessors already processed

    unsigned ProcessedPredecessors = 0;

    BlockInfo() = default;

    BlockInfo(BlockInfo &&) = default;

    BlockInfo &operator=(BlockInfo &&) = default;

  };

  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);

  void enterCFGBlock(const CFGBlock *B);

  bool visitPredecessors() { return true; }

  void handlePredecessor(const CFGBlock *Pred);

  void handlePredecessorBackEdge(const CFGBlock *Pred);

  void enterCFGBlockBody(const CFGBlock *B);

  void handleStatement(const Stmt *S);

  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);

  void exitCFGBlockBody(const CFGBlock *B);

  bool visitSuccessors() { return true; }

  void handleSuccessor(const CFGBlock *Succ);

  void handleSuccessorBackEdge(const CFGBlock *Succ);

  void exitCFGBlock(const CFGBlock *B);

  void exitCFG(const CFGBlock *Last);

  void insertStmt(const Stmt *S, til::SExpr *E) {

    SMap.insert(std::make_pair(S, E));

  }

  til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);

  til::SExpr *addStatement(til::SExpr *E, const Stmt *S,

                           const ValueDecl *VD = nullptr);

  til::SExpr *lookupVarDecl(const ValueDecl *VD);

  til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);

  til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);

  void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);

  void mergeEntryMap(LVarDefinitionMap Map);

  void mergeEntryMapBackEdge();

  void mergePhiNodesBackEdge(const CFGBlock *Blk);

private:

  // Set to true when parsing capability expressions, which get translated

  // inaccurately in order to hack around smart pointers etc.

  static const bool CapabilityExprMode = true;

  til::MemRegionRef Arena;

  // Variable to use for 'this'.  May be null.

  til::Variable *SelfVar = nullptr;

  til::SCFG *Scfg = nullptr;

  // Map from Stmt to TIL Variables

  StatementMap SMap;

  // Indices of clang local vars.

  LVarIndexMap LVarIdxMap;

  // Map from clang to til BBs.

  std::vector<til::BasicBlock *> BlockMap;

  // Extra information per BB. Indexed by clang BlockID.

  std::vector<BlockInfo> BBInfo;

  LVarDefinitionMap CurrentLVarMap;

  std::vector<til::Phi *> CurrentArguments;

  std::vector<til::SExpr *> CurrentInstructions;

  std::vector<til::Phi *> IncompleteArgs;

  til::BasicBlock *CurrentBB = nullptr;

  BlockInfo *CurrentBlockInfo = nullptr;

};

// Dump an SCFG to llvm::errs().

void printSCFG(CFGWalker &Walker);

} // namespace threadSafety

} // namespace clang

#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H