apted

package
v0.2.7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 7, 2026 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ComputeKeyRoots 

func ComputeKeyRoots(root *TreeNode) []int

ComputeKeyRoots identifies key roots for path decomposition.

func ComputeLeftMostLeaves 

func ComputeLeftMostLeaves(root *TreeNode)

ComputeLeftMostLeaves computes left-most leaf descendants for all nodes.

func PostOrderTraversal 

func PostOrderTraversal(root *TreeNode)

PostOrderTraversal performs post-order traversal and assigns post-order IDs.

func PrepareTreeForAPTED 

func PrepareTreeForAPTED(root *TreeNode) []int

PrepareTreeForAPTED prepares a tree for APTED algorithm by computing all necessary indices.

Types

type APTEDAnalyzer 

type APTEDAnalyzer struct {
	// contains filtered or unexported fields
}

APTEDAnalyzer implements the APTED (All Path Tree Edit Distance) algorithm. Based on Pawlik & Augsten's optimal O(n^2 log n) algorithm.

func NewAPTEDAnalyzer 

func NewAPTEDAnalyzer(costModel CostModel) *APTEDAnalyzer

NewAPTEDAnalyzer creates a new APTED analyzer with the given cost model. Default normalization mode is NormalizeByMax.

func NewAPTEDAnalyzerWithNormalization 

func NewAPTEDAnalyzerWithNormalization(costModel CostModel, mode NormalizationMode) *APTEDAnalyzer

NewAPTEDAnalyzerWithNormalization creates an APTED analyzer with a specific normalization mode.

func (*APTEDAnalyzer) BatchComputeDistances 

func (a *APTEDAnalyzer) BatchComputeDistances(pairs [][2]*TreeNode) []float64

BatchComputeDistances computes distances between multiple tree pairs.

func (*APTEDAnalyzer) ClusterSimilarTrees 

func (a *APTEDAnalyzer) ClusterSimilarTrees(trees []*TreeNode, similarityThreshold float64) *ClusterResult

ClusterSimilarTrees clusters trees based on similarity threshold.

func (*APTEDAnalyzer) ComputeDetailedDistance 

func (a *APTEDAnalyzer) ComputeDetailedDistance(tree1, tree2 *TreeNode) *TreeEditResult

ComputeDetailedDistance computes detailed tree edit distance information.

func (*APTEDAnalyzer) ComputeDistance 

func (a *APTEDAnalyzer) ComputeDistance(tree1, tree2 *TreeNode) float64

ComputeDistance computes the tree edit distance between two trees.

func (*APTEDAnalyzer) ComputeDistanceAndSimilarity 

func (a *APTEDAnalyzer) ComputeDistanceAndSimilarity(tree1, tree2 *TreeNode) (float64, float64)

ComputeDistanceAndSimilarity computes both APTED distance and normalized similarity from one distance pass.

func (*APTEDAnalyzer) ComputeSimilarity 

func (a *APTEDAnalyzer) ComputeSimilarity(tree1, tree2 *TreeNode) float64

ComputeSimilarity computes similarity score between two trees (0.0 to 1.0). The normalization mode is controlled by the analyzer's NormalizationMode setting.

type ClusterResult 

type ClusterResult struct {
	Groups    [][]int
	Distances [][]float64
	Threshold float64
}

ClusterResult represents the result of tree clustering.

type CostModel 

type CostModel interface {
	Insert(node *TreeNode) float64
	Delete(node *TreeNode) float64
	Rename(node1, node2 *TreeNode) float64
}

CostModel defines the interface for calculating edit operation costs. Language-specific cost models (e.g. PythonCostModel, JavaScriptCostModel) should implement this interface in their respective projects.

type DefaultCostModel 

type DefaultCostModel struct{}

DefaultCostModel implements a uniform cost model where all operations cost 1.0.

func NewDefaultCostModel 

func NewDefaultCostModel() *DefaultCostModel

func (*DefaultCostModel) Delete 

func (c *DefaultCostModel) Delete(node *TreeNode) float64

func (*DefaultCostModel) Insert 

func (c *DefaultCostModel) Insert(node *TreeNode) float64

func (*DefaultCostModel) Rename 

func (c *DefaultCostModel) Rename(node1, node2 *TreeNode) float64

type NormalizationMode 

type NormalizationMode int

NormalizationMode controls how similarity is normalized from distance. 

const (
	// NormalizeByMax uses max(size1, size2) — stricter, reduces false positives.
	// Used by both pyscn and jscan.
	NormalizeByMax NormalizationMode = iota
	// NormalizeBySum uses size1 + size2 (Jaccard-like).
	NormalizeBySum
)

type OptimizedAPTEDAnalyzer 

type OptimizedAPTEDAnalyzer struct {
	*APTEDAnalyzer
	// contains filtered or unexported fields
}

OptimizedAPTEDAnalyzer extends APTEDAnalyzer with early stopping.

func NewOptimizedAPTEDAnalyzer 

func NewOptimizedAPTEDAnalyzer(costModel CostModel, maxDistance float64) *OptimizedAPTEDAnalyzer

NewOptimizedAPTEDAnalyzer creates an optimized APTED analyzer.

func (*OptimizedAPTEDAnalyzer) ComputeDetailedDistance added in v0.2.2 

func (a *OptimizedAPTEDAnalyzer) ComputeDetailedDistance(tree1, tree2 *TreeNode) *TreeEditResult

ComputeDetailedDistance computes detailed tree edit distance information with the analyzer's early-stopping cap applied (see ComputeDistanceAndSimilarity).

func (*OptimizedAPTEDAnalyzer) ComputeDistance 

func (a *OptimizedAPTEDAnalyzer) ComputeDistance(tree1, tree2 *TreeNode) float64

ComputeDistance computes tree edit distance with early stopping optimization.

func (*OptimizedAPTEDAnalyzer) ComputeDistanceAndSimilarity added in v0.2.2 

func (a *OptimizedAPTEDAnalyzer) ComputeDistanceAndSimilarity(tree1, tree2 *TreeNode) (float64, float64)

ComputeDistanceAndSimilarity computes both distance and similarity with the analyzer's early-stopping cap applied. Without this override, the method promoted from the embedded APTEDAnalyzer would bypass the cap and return the full uncapped distance.

type TreeEditResult 

type TreeEditResult struct {
	Distance   float64
	Similarity float64
	Tree1Size  int
	Tree2Size  int
	Operations int
}

TreeEditResult holds the result of tree edit distance computation.

type TreeNode 

type TreeNode struct {
	ID    int
	Label string

	Children []*TreeNode
	Parent   *TreeNode

	// APTED-specific fields for optimization
	PostOrderID  int
	LeftMostLeaf int
	KeyRoot      bool

	// OriginalNode holds the original language-specific AST node.
	// This field is opaque to polyscan core; language adapters store their
	// own node type here and recover it via type assertion:
	//
	//   // pyscn
	//   pyNode := treeNode.OriginalNode.(*parser.Node)
	//
	// Populating it is a deliberate choice, not a default. A parser node that
	// carries a parent pointer pins its whole file AST for as long as the
	// converted tree lives, which is the entire run for clone detection —
	// jscan's converter therefore leaves this empty, so do not assume an
	// adapter has filled it in.
	OriginalNode any
	// contains filtered or unexported fields
}

TreeNode represents a node in the ordered tree for APTED algorithm. This is a language-agnostic representation; language-specific parsers should convert their AST nodes into TreeNode via a TreeConverter.

func GetNodeByPostOrderID 

func GetNodeByPostOrderID(root *TreeNode, postOrderID int) *TreeNode

GetNodeByPostOrderID finds a node by its post-order ID.

func GetSubtreeNodes 

func GetSubtreeNodes(root *TreeNode) []*TreeNode

GetSubtreeNodes returns all nodes in the subtree rooted at the given node.

func GetSubtreeNodesWithDepthLimit 

func GetSubtreeNodesWithDepthLimit(root *TreeNode, maxDepth int) []*TreeNode

GetSubtreeNodesWithDepthLimit returns all nodes with maximum recursion depth limit.

func NewTreeNode 

func NewTreeNode(id int, label string) *TreeNode

NewTreeNode creates a new tree node with the given ID and label.

func (*TreeNode) AddChild 

func (t *TreeNode) AddChild(child *TreeNode)

AddChild adds a child node to this node.

func (*TreeNode) Height 

func (t *TreeNode) Height() int

Height returns the height of the subtree rooted at this node.

func (*TreeNode) HeightWithDepthLimit 

func (t *TreeNode) HeightWithDepthLimit(maxDepth int) int

HeightWithDepthLimit returns the height with maximum recursion depth limit.

func (*TreeNode) IsLeaf 

func (t *TreeNode) IsLeaf() bool

IsLeaf returns true if this node has no children.

func (*TreeNode) Size 

func (t *TreeNode) Size() int

Size returns the size of the subtree rooted at this node.

func (*TreeNode) SizeWithDepthLimit 

func (t *TreeNode) SizeWithDepthLimit(maxDepth int) int

SizeWithDepthLimit returns the size with maximum recursion depth limit.

func (*TreeNode) String 

func (t *TreeNode) String() string

String returns a string representation of the node.

type WeightedCostModel 

type WeightedCostModel struct {
	InsertWeight  float64
	DeleteWeight  float64
	RenameWeight  float64
	BaseCostModel CostModel
}

WeightedCostModel allows custom weights for different operation types.

func NewWeightedCostModel 

func NewWeightedCostModel(insertWeight, deleteWeight, renameWeight float64, baseCostModel CostModel) *WeightedCostModel

func (*WeightedCostModel) Delete 

func (c *WeightedCostModel) Delete(node *TreeNode) float64

func (*WeightedCostModel) Insert 

func (c *WeightedCostModel) Insert(node *TreeNode) float64

func (*WeightedCostModel) Rename 

func (c *WeightedCostModel) Rename(node1, node2 *TreeNode) float64

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.