ASTDiff.cpp | Explore in Territory

//===- ASTDiff.cpp - AST differencing implementation-----------*- 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
//
//===----------------------------------------------------------------------===//
//
// This file contains definitons for the AST differencing interface.
//
//===----------------------------------------------------------------------===//

#include "clang/Tooling/ASTDiff/ASTDiff.h"
#include "clang/AST/ParentMapContext.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Lex/Lexer.h"
#include "llvm/ADT/PriorityQueue.h"

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

usingnamespacellvm;
usingnamespaceclang;

namespace clang {
namespace diff {

namespace {
/// Maps nodes of the left tree to ones on the right, and vice versa.
class Mapping { … };
} // end anonymous namespace

class ASTDiff::Impl { … };

/// Represents the AST of a TranslationUnit.
class SyntaxTree::Impl { … };

static bool isSpecializedNodeExcluded(const Decl *D) { … }
static bool isSpecializedNodeExcluded(const Stmt *S) { … }
static bool isSpecializedNodeExcluded(CXXCtorInitializer *I) { … }

template <class T>
static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) { … }

namespace {
// Sets Height, Parent and Children for each node.
struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> { … };
} // end anonymous namespace

SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTContext &AST)
    : … { … }

SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
    : … { … }

SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
    : … { … }

static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
                                               NodeId Root) { … }

static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
                                         NodeId Root) { … }

void SyntaxTree::Impl::initTree() { … }

void SyntaxTree::Impl::setLeftMostDescendants() { … }

int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const { … }

bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const { … }

int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const { … }

// Returns the qualified name of ND. If it is subordinate to Context,
// then the prefix of the latter is removed from the returned value.
std::string
SyntaxTree::Impl::getRelativeName(const NamedDecl *ND,
                                  const DeclContext *Context) const { … }

std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const { … }

static const DeclContext *getEnclosingDeclContext(ASTContext &AST,
                                                  const Stmt *S) { … }

static std::string getInitializerValue(const CXXCtorInitializer *Init,
                                       const PrintingPolicy &TypePP) { … }

std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const { … }

std::string SyntaxTree::Impl::getNodeValue(const Node &N) const { … }

std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const { … }

std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const { … }

/// Identifies a node in a subtree by its postorder offset, starting at 1.
struct SNodeId { … };

class Subtree { … };

/// Implementation of Zhang and Shasha's Algorithm for tree edit distance.
/// Computes an optimal mapping between two trees using only insertion,
/// deletion and update as edit actions (similar to the Levenshtein distance).
class ZhangShashaMatcher { … };

ASTNodeKind Node::getType() const { … }

StringRef Node::getTypeLabel() const { … }

std::optional<std::string> Node::getQualifiedIdentifier() const { … }

std::optional<StringRef> Node::getIdentifier() const { … }

namespace {
// Compares nodes by their depth.
struct HeightLess { … };
} // end anonymous namespace

namespace {
// Priority queue for nodes, sorted descendingly by their height.
class PriorityList { … };
} // end anonymous namespace

bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const { … }

bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const { … }

bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
                                    NodeId Id2) const { … }

void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
                                      NodeId Id2) const { … }

double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
                                           NodeId Id2) const { … }

NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const { … }

void ASTDiff::Impl::matchBottomUp(Mapping &M) const { … }

Mapping ASTDiff::Impl::matchTopDown() const { … }

ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
                    const ComparisonOptions &Options)
    : … { … }

void ASTDiff::Impl::computeMapping() { … }

void ASTDiff::Impl::computeChangeKinds(Mapping &M) { … }

ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
                 const ComparisonOptions &Options)
    : … { … }

ASTDiff::~ASTDiff() = default;

NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const { … }

SyntaxTree::SyntaxTree(ASTContext &AST)
    : … { … }

SyntaxTree::~SyntaxTree() = default;

const ASTContext &SyntaxTree::getASTContext() const { … }

const Node &SyntaxTree::getNode(NodeId Id) const { … }

int SyntaxTree::getSize() const { … }
NodeId SyntaxTree::getRootId() const { … }
SyntaxTree::PreorderIterator SyntaxTree::begin() const { … }
SyntaxTree::PreorderIterator SyntaxTree::end() const { … }

int SyntaxTree::findPositionInParent(NodeId Id) const { … }

std::pair<unsigned, unsigned>
SyntaxTree::getSourceRangeOffsets(const Node &N) const { … }

std::string SyntaxTree::getNodeValue(NodeId Id) const { … }

std::string SyntaxTree::getNodeValue(const Node &N) const { … }

} // end namespace diff
} // end namespace clang
llvm/clang/lib/Tooling/ASTDiff/ASTDiff.cpp
