<commit_before>//===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains definitons for the AST differencing interface.
//
//===----------------------------------------------------------------------===//

#include "clang/Tooling/ASTDiff/ASTDiff.h"

#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/Lex/Lexer.h"
#include "llvm/ADT/PriorityQueue.h"

#include <limits>
#include <memory>
#include <unordered_set>

using namespace llvm;
using namespace clang;

namespace clang {
namespace diff {

namespace {
/// Maps nodes of the left tree to ones on the right, and vice versa.
class Mapping {
public:
  Mapping() = default;
  Mapping(Mapping &&Other) = default;
  Mapping &operator=(Mapping &&Other) = default;

  Mapping(size_t Size) {
    SrcToDst = llvm::make_unique<NodeId[]>(Size);
    DstToSrc = llvm::make_unique<NodeId[]>(Size);
  }

  void link(NodeId Src, NodeId Dst) {
    SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
  }

  NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
  NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
  bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
  bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }

private:
  std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
};
} // end anonymous namespace

class ASTDiff::Impl {
public:
  SyntaxTree::Impl &T1, &T2;
  Mapping TheMapping;

  Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
       const ComparisonOptions &Options);

  /// Matches nodes one-by-one based on their similarity.
  void computeMapping();

  // Compute Change for each node based on similarity.
  void computeChangeKinds(Mapping &M);

  NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
                   NodeId Id) const {
    if (&*Tree == &T1)
      return TheMapping.getDst(Id);
    assert(&*Tree == &T2 && "Invalid tree.");
    return TheMapping.getSrc(Id);
  }

private:
  // Returns true if the two subtrees are identical.
  bool identical(NodeId Id1, NodeId Id2) const;

  // Returns false if the nodes must not be mached.
  bool isMatchingPossible(NodeId Id1, NodeId Id2) const;

  // Returns true if the nodes' parents are matched.
  bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;

  // Uses an optimal albeit slow algorithm to compute a mapping between two
  // subtrees, but only if both have fewer nodes than MaxSize.
  void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;

  // Computes the ratio of common descendants between the two nodes.
  // Descendants are only considered to be equal when they are mapped in M.
  double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;

  // Returns the node that has the highest degree of similarity.
  NodeId findCandidate(const Mapping &M, NodeId Id1) const;

  // Returns a mapping of identical subtrees.
  Mapping matchTopDown() const;

  // Tries to match any yet unmapped nodes, in a bottom-up fashion.
  void matchBottomUp(Mapping &M) const;

  const ComparisonOptions &Options;

  friend class ZhangShashaMatcher;
};

/// Represents the AST of a TranslationUnit.
class SyntaxTree::Impl {
public:
  /// Constructs a tree from an AST node.
  Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
  Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
  template <class T>
  Impl(SyntaxTree *Parent,
       typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
       ASTContext &AST)
      : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
  template <class T>
  Impl(SyntaxTree *Parent,
       typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
       ASTContext &AST)
      : Impl(Parent, dyn_cast<Decl>(Node), AST) {}

  SyntaxTree *Parent;
  ASTContext &AST;
  std::vector<NodeId> Leaves;
  // Maps preorder indices to postorder ones.
  std::vector<int> PostorderIds;
  std::vector<NodeId> NodesBfs;

  int getSize() const { return Nodes.size(); }
  NodeId getRootId() const { return 0; }
  PreorderIterator begin() const { return getRootId(); }
  PreorderIterator end() const { return getSize(); }

  const Node &getNode(NodeId Id) const { return Nodes[Id]; }
  Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
  bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
  void addNode(Node &N) { Nodes.push_back(N); }
  int getNumberOfDescendants(NodeId Id) const;
  bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
  int findPositionInParent(NodeId Id, bool Shifted = false) const;

  std::string getRelativeName(const NamedDecl *ND,
                              const DeclContext *Context) const;
  std::string getRelativeName(const NamedDecl *ND) const;

  std::string getNodeValue(NodeId Id) const;
  std::string getNodeValue(const Node &Node) const;
  std::string getDeclValue(const Decl *D) const;
  std::string getStmtValue(const Stmt *S) const;

private:
  /// Nodes in preorder.
  std::vector<Node> Nodes;

  void initTree();
  void setLeftMostDescendants();
};

static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }

template <class T>
static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
  if (!N)
    return true;
  SourceLocation SLoc = N->getLocStart();
  if (SLoc.isValid()) {
    // Ignore everything from other files.
    if (!SrcMgr.isInMainFile(SLoc))
      return true;
    // Ignore macros.
    if (SLoc != SrcMgr.getSpellingLoc(SLoc))
      return true;
  }
  return isSpecializedNodeExcluded(N);
}

namespace {
/// Counts the number of nodes that will be compared.
struct NodeCountVisitor : public RecursiveASTVisitor<NodeCountVisitor> {
  int Count = 0;
  const SyntaxTree::Impl &Tree;
  NodeCountVisitor(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
  bool TraverseDecl(Decl *D) {
    if (isNodeExcluded(Tree.AST.getSourceManager(), D))
      return true;
    ++Count;
    RecursiveASTVisitor<NodeCountVisitor>::TraverseDecl(D);
    return true;
  }
  bool TraverseStmt(Stmt *S) {
    if (S)
      S = S->IgnoreImplicit();
    if (isNodeExcluded(Tree.AST.getSourceManager(), S))
      return true;
    ++Count;
    RecursiveASTVisitor<NodeCountVisitor>::TraverseStmt(S);
    return true;
  }
  bool TraverseType(QualType T) { return true; }
};
} // end anonymous namespace

namespace {
// Sets Height, Parent and Children for each node.
struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
  int Id = 0, Depth = 0;
  NodeId Parent;
  SyntaxTree::Impl &Tree;

  PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}

  template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
    NodeId MyId = Id;
    Node &N = Tree.getMutableNode(MyId);
    N.Parent = Parent;
    N.Depth = Depth;
    N.ASTNode = DynTypedNode::create(*ASTNode);
    assert(!N.ASTNode.getNodeKind().isNone() &&
           "Expected nodes to have a valid kind.");
    if (Parent.isValid()) {
      Node &P = Tree.getMutableNode(Parent);
      P.Children.push_back(MyId);
    }
    Parent = MyId;
    ++Id;
    ++Depth;
    return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
  }
  void PostTraverse(std::tuple<NodeId, NodeId> State) {
    NodeId MyId, PreviousParent;
    std::tie(MyId, PreviousParent) = State;
    assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
    Parent = PreviousParent;
    --Depth;
    Node &N = Tree.getMutableNode(MyId);
    N.RightMostDescendant = Id - 1;
    assert(N.RightMostDescendant >= 0 &&
           N.RightMostDescendant < Tree.getSize() &&
           "Rightmost descendant must be a valid tree node.");
    if (N.isLeaf())
      Tree.Leaves.push_back(MyId);
    N.Height = 1;
    for (NodeId Child : N.Children)
      N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
  }
  bool TraverseDecl(Decl *D) {
    if (isNodeExcluded(Tree.AST.getSourceManager(), D))
      return true;
    auto SavedState = PreTraverse(D);
    RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
    PostTraverse(SavedState);
    return true;
  }
  bool TraverseStmt(Stmt *S) {
    if (S)
      S = S->IgnoreImplicit();
    if (isNodeExcluded(Tree.AST.getSourceManager(), S))
      return true;
    auto SavedState = PreTraverse(S);
    RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
    PostTraverse(SavedState);
    return true;
  }
  bool TraverseType(QualType T) { return true; }
};
} // end anonymous namespace

SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
    : Parent(Parent), AST(AST) {
  NodeCountVisitor NodeCounter(*this);
  NodeCounter.TraverseDecl(N);
  Nodes.resize(NodeCounter.Count);
  PreorderVisitor PreorderWalker(*this);
  PreorderWalker.TraverseDecl(N);
  initTree();
}

SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
    : Parent(Parent), AST(AST) {
  NodeCountVisitor NodeCounter(*this);
  NodeCounter.TraverseStmt(N);
  Nodes.resize(NodeCounter.Count);
  PreorderVisitor PreorderWalker(*this);
  PreorderWalker.TraverseStmt(N);
  initTree();
}

static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,<commit_msg>[clang-diff] Remove NodeCountVisitor, NFC<commit_after>//===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains definitons for the AST differencing interface.
//
//===----------------------------------------------------------------------===//

#include "clang/Tooling/ASTDiff/ASTDiff.h"

#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/Lex/Lexer.h"
#include "llvm/ADT/PriorityQueue.h"

#include <limits>
#include <memory>
#include <unordered_set>

using namespace llvm;
using namespace clang;

namespace clang {
namespace diff {

namespace {
/// Maps nodes of the left tree to ones on the right, and vice versa.
class Mapping {
public:
  Mapping() = default;
  Mapping(Mapping &&Other) = default;
  Mapping &operator=(Mapping &&Other) = default;

  Mapping(size_t Size) {
    SrcToDst = llvm::make_unique<NodeId[]>(Size);
    DstToSrc = llvm::make_unique<NodeId[]>(Size);
  }

  void link(NodeId Src, NodeId Dst) {
    SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
  }

  NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
  NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
  bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
  bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }

private:
  std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
};
} // end anonymous namespace

class ASTDiff::Impl {
public:
  SyntaxTree::Impl &T1, &T2;
  Mapping TheMapping;

  Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
       const ComparisonOptions &Options);

  /// Matches nodes one-by-one based on their similarity.
  void computeMapping();

  // Compute Change for each node based on similarity.
  void computeChangeKinds(Mapping &M);

  NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
                   NodeId Id) const {
    if (&*Tree == &T1)
      return TheMapping.getDst(Id);
    assert(&*Tree == &T2 && "Invalid tree.");
    return TheMapping.getSrc(Id);
  }

private:
  // Returns true if the two subtrees are identical.
  bool identical(NodeId Id1, NodeId Id2) const;

  // Returns false if the nodes must not be mached.
  bool isMatchingPossible(NodeId Id1, NodeId Id2) const;

  // Returns true if the nodes' parents are matched.
  bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;

  // Uses an optimal albeit slow algorithm to compute a mapping between two
  // subtrees, but only if both have fewer nodes than MaxSize.
  void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;

  // Computes the ratio of common descendants between the two nodes.
  // Descendants are only considered to be equal when they are mapped in M.
  double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;

  // Returns the node that has the highest degree of similarity.
  NodeId findCandidate(const Mapping &M, NodeId Id1) const;

  // Returns a mapping of identical subtrees.
  Mapping matchTopDown() const;

  // Tries to match any yet unmapped nodes, in a bottom-up fashion.
  void matchBottomUp(Mapping &M) const;

  const ComparisonOptions &Options;

  friend class ZhangShashaMatcher;
};

/// Represents the AST of a TranslationUnit.
class SyntaxTree::Impl {
public:
  /// Constructs a tree from an AST node.
  Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
  Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
  template <class T>
  Impl(SyntaxTree *Parent,
       typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
       ASTContext &AST)
      : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
  template <class T>
  Impl(SyntaxTree *Parent,
       typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
       ASTContext &AST)
      : Impl(Parent, dyn_cast<Decl>(Node), AST) {}

  SyntaxTree *Parent;
  ASTContext &AST;
  /// Nodes in preorder.
  std::vector<Node> Nodes;
  std::vector<NodeId> Leaves;
  // Maps preorder indices to postorder ones.
  std::vector<int> PostorderIds;
  std::vector<NodeId> NodesBfs;

  int getSize() const { return Nodes.size(); }
  NodeId getRootId() const { return 0; }
  PreorderIterator begin() const { return getRootId(); }
  PreorderIterator end() const { return getSize(); }

  const Node &getNode(NodeId Id) const { return Nodes[Id]; }
  Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
  bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
  void addNode(Node &N) { Nodes.push_back(N); }
  int getNumberOfDescendants(NodeId Id) const;
  bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
  int findPositionInParent(NodeId Id, bool Shifted = false) const;

  std::string getRelativeName(const NamedDecl *ND,
                              const DeclContext *Context) const;
  std::string getRelativeName(const NamedDecl *ND) const;

  std::string getNodeValue(NodeId Id) const;
  std::string getNodeValue(const Node &Node) const;
  std::string getDeclValue(const Decl *D) const;
  std::string getStmtValue(const Stmt *S) const;

private:
  void initTree();
  void setLeftMostDescendants();
};

static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }

template <class T>
static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
  if (!N)
    return true;
  SourceLocation SLoc = N->getLocStart();
  if (SLoc.isValid()) {
    // Ignore everything from other files.
    if (!SrcMgr.isInMainFile(SLoc))
      return true;
    // Ignore macros.
    if (SLoc != SrcMgr.getSpellingLoc(SLoc))
      return true;
  }
  return isSpecializedNodeExcluded(N);
}

namespace {
// Sets Height, Parent and Children for each node.
struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
  int Id = 0, Depth = 0;
  NodeId Parent;
  SyntaxTree::Impl &Tree;

  PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}

  template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
    NodeId MyId = Id;
    Tree.Nodes.emplace_back();
    Node &N = Tree.getMutableNode(MyId);
    N.Parent = Parent;
    N.Depth = Depth;
    N.ASTNode = DynTypedNode::create(*ASTNode);
    assert(!N.ASTNode.getNodeKind().isNone() &&
           "Expected nodes to have a valid kind.");
    if (Parent.isValid()) {
      Node &P = Tree.getMutableNode(Parent);
      P.Children.push_back(MyId);
    }
    Parent = MyId;
    ++Id;
    ++Depth;
    return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
  }
  void PostTraverse(std::tuple<NodeId, NodeId> State) {
    NodeId MyId, PreviousParent;
    std::tie(MyId, PreviousParent) = State;
    assert(MyId.isValid() && "Expecting to only traverse valid nodes.");
    Parent = PreviousParent;
    --Depth;
    Node &N = Tree.getMutableNode(MyId);
    N.RightMostDescendant = Id - 1;
    assert(N.RightMostDescendant >= 0 &&
           N.RightMostDescendant < Tree.getSize() &&
           "Rightmost descendant must be a valid tree node.");
    if (N.isLeaf())
      Tree.Leaves.push_back(MyId);
    N.Height = 1;
    for (NodeId Child : N.Children)
      N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
  }
  bool TraverseDecl(Decl *D) {
    if (isNodeExcluded(Tree.AST.getSourceManager(), D))
      return true;
    auto SavedState = PreTraverse(D);
    RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
    PostTraverse(SavedState);
    return true;
  }
  bool TraverseStmt(Stmt *S) {
    if (S)
      S = S->IgnoreImplicit();
    if (isNodeExcluded(Tree.AST.getSourceManager(), S))
      return true;
    auto SavedState = PreTraverse(S);
    RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
    PostTraverse(SavedState);
    return true;
  }
  bool TraverseType(QualType T) { return true; }
};
} // end anonymous namespace

SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
    : Parent(Parent), AST(AST) {
  PreorderVisitor PreorderWalker(*this);
  PreorderWalker.TraverseDecl(N);
  initTree();
}

SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
    : Parent(Parent), AST(AST) {
  PreorderVisitor PreorderWalker(*this);
  PreorderWalker.TraverseStmt(N);
  initTree();
}

static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
{'fraction_non_alphanumeric': 0.14040579062098263, 'fraction_numerical': 0.002850595271365491, 'mean_word_length': 3.529620253164557, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 71, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4416915', 'n_tokens_mistral': 5922, 'n_tokens_neox': 5754, 'n_words': 1585}