Help us shape the future of Go! Take the 2026 Go Developer Survey

apted

package
v0.2.9 Latest Latest
Warning

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

 Go to latest Published: Oct 15, 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.