class ZhangShashaMatcher

Declaration

class ZhangShashaMatcher { /* full declaration omitted */ };

Description

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).

Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:559

Member Variables

private const ASTDiff::Impl& DiffImpl
private clang::diff::Subtree S1
private clang::diff::Subtree S2
private std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist
private std::unique_ptr<std::unique_ptr<double[]>[]> ForestDist
private static const double DeletionCost = 1
We use a simple cost model for edit actions, which seems good enough. Simple cost model for edit actions. This seems to make the matching algorithm perform reasonably well. The values range between 0 and 1, or infinity if this edit action should always be avoided.
private static const double InsertionCost = 1

Method Overview

  • public ZhangShashaMatcher(const ASTDiff::Impl & DiffImpl, const SyntaxTree::Impl & T1, const SyntaxTree::Impl & T2, clang::diff::NodeId Id1, clang::diff::NodeId Id2)
  • private void computeForestDist(clang::diff::SNodeId Id1, clang::diff::SNodeId Id2)
  • private void computeTreeDist()
  • public std::vector<std::pair<NodeId, NodeId>> getMatchingNodes()
  • private double getUpdateCost(clang::diff::SNodeId Id1, clang::diff::SNodeId Id2)

Methods

ZhangShashaMatcher(const ASTDiff::Impl& DiffImpl,
                   const SyntaxTree::Impl& T1,
                   const SyntaxTree::Impl& T2,
                   clang::diff::NodeId Id1,
                   clang::diff::NodeId Id2)

Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:566

Parameters

const ASTDiff::Impl& DiffImpl
const SyntaxTree::Impl& T1
const SyntaxTree::Impl& T2
clang::diff::NodeId Id1
clang::diff::NodeId Id2

void computeForestDist(clang::diff::SNodeId Id1,
                       clang::diff::SNodeId Id2)

Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:657

Parameters

clang::diff::SNodeId Id1
clang::diff::SNodeId Id2

void computeTreeDist()

Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:651

std::vector<std::pair<NodeId, NodeId>>
getMatchingNodes()

Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:579

double getUpdateCost(clang::diff::SNodeId Id1,
                     clang::diff::SNodeId Id2)

Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:645

Parameters

clang::diff::SNodeId Id1
clang::diff::SNodeId Id2