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)
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)
void computeForestDist(clang::diff::SNodeId Id1,
clang::diff::SNodeId Id2)
Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:657
Parameters
¶void computeTreeDist()
void computeTreeDist()
Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:651
¶std::vector<std::pair<NodeId, NodeId>>
getMatchingNodes()
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)
double getUpdateCost(clang::diff::SNodeId Id1,
clang::diff::SNodeId Id2)
Declared at: clang/lib/Tooling/ASTDiff/ASTDiff.cpp:645