clone

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: 9 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CalculateConfidence 

func CalculateConfidence(f1, f2 *CodeFragment, similarity float64) float64

CalculateConfidence calculates confidence in a clone pair from similarity, fragment size, and complexity agreement.

func ItemKey 

func ItemKey[T GroupableItem](item T) string

ItemKey returns a stable identifier for an item based on its location.

func JaccardSimilarity 

func JaccardSimilarity(set1, set2 []string) float64

JaccardSimilarity computes the Jaccard coefficient between two string slices: Jaccard(A, B) = |A ∩ B| / |A ∪ B|. Sorted inputs (as produced by ASTFeatureExtractor.ExtractFeatures) are processed with an O(n+m) merge-join; unsorted inputs are sorted into a copy first so the result stays correct.

func LocationsOverlap 

func LocationsOverlap(a, b ItemLocation) bool

LocationsOverlap reports whether two locations overlap in the same file (inclusive line ranges). Detectors use this to reject same-file pairs of overlapping fragments, which describe containment rather than duplication.

func PairKey 

func PairKey[T GroupableItem](a, b T) string

PairKey returns a canonical key for a pair of items, independent of order.

func ShouldCompareFragments 

func ShouldCompareFragments(f1, f2 *CodeFragment) bool

ShouldCompareFragments applies cheap size/line prefilters: fragments whose node counts or line counts differ too much cannot be clones.

Types

type ASTFeatureExtractor 

type ASTFeatureExtractor struct {

	// PatternNames is the list of node type names to check for structural patterns.
	// Language-specific: set this to match your AST node types.
	// If nil, no pattern features are extracted.
	PatternNames []string
	// contains filtered or unexported fields
}

ASTFeatureExtractor implements FeatureExtractor for TreeNode.

func NewASTFeatureExtractor 

func NewASTFeatureExtractor() *ASTFeatureExtractor

NewASTFeatureExtractor creates a feature extractor with sensible defaults.

func (*ASTFeatureExtractor) ExtractFeatures 

func (a *ASTFeatureExtractor) ExtractFeatures(ast *apted.TreeNode) ([]string, error)

ExtractFeatures builds a mixed set of features from the tree.

func (*ASTFeatureExtractor) ExtractNodeSequences 

func (a *ASTFeatureExtractor) ExtractNodeSequences(ast *apted.TreeNode, k int) ([]string, error)

ExtractNodeSequences returns k-grams from pre-order traversal labels.

func (*ASTFeatureExtractor) ExtractSubtreeHashes 

func (a *ASTFeatureExtractor) ExtractSubtreeHashes(ast *apted.TreeNode, maxHeight int) ([]string, error)

ExtractSubtreeHashes computes bottom-up hashes of subtrees up to maxHeight.

func (*ASTFeatureExtractor) WithLiteralNames added in v0.2.1 

func (a *ASTFeatureExtractor) WithLiteralNames(names []string) *ASTFeatureExtractor

WithLiteralNames sets the base label names treated as identifier/literal payload carriers, which are excluded from label features when includeLiterals is false.

func (*ASTFeatureExtractor) WithOptions 

func (a *ASTFeatureExtractor) WithOptions(maxHeight, k int, includeTypes, includeLiterals bool) *ASTFeatureExtractor

WithOptions allows overriding defaults.

func (*ASTFeatureExtractor) WithPatterns 

func (a *ASTFeatureExtractor) WithPatterns(patterns []string) *ASTFeatureExtractor

WithPatterns sets the pattern names for structural feature extraction.

type CentroidGrouping 

type CentroidGrouping[T GroupableItem] struct {
	// contains filtered or unexported fields
}

CentroidGrouping uses BFS expansion with strict similarity to all existing members.

func NewCentroidGrouping 

func NewCentroidGrouping[T GroupableItem](threshold float64) *CentroidGrouping[T]

func (*CentroidGrouping[T]) GroupItems 

func (cg *CentroidGrouping[T]) GroupItems(pairs []*ItemPair[T]) []*ItemGroup[T]

func (*CentroidGrouping[T]) Name 

func (cg *CentroidGrouping[T]) Name() string

type ClassifierConfig 

type ClassifierConfig struct {
	Type1Threshold float64
	Type2Threshold float64
	Type3Threshold float64
	Type4Threshold float64
	EnableType1    bool
	EnableType2    bool
	EnableType3    bool
	EnableType4    bool
	// JaccardPreFilterThreshold is the feature Jaccard similarity below which
	// pairs are rejected before expensive structural analysis. Only used for
	// rejection — all non-rejected pairs proceed to structural classification.
	// Zero disables the pre-filter.
	JaccardPreFilterThreshold float64
}

ClassifierConfig holds configuration for clone pair classification.

func DefaultClassifierConfig 

func DefaultClassifierConfig() ClassifierConfig

DefaultClassifierConfig returns the default classifier configuration.

type CloneGroup 

type CloneGroup struct {
	ID            int
	Fragments     []*CodeFragment
	CloneType     domain.CloneType
	AvgSimilarity float64
}

CloneGroup represents a group of code fragments that are clones of each other.

type ClonePair 

type ClonePair struct {
	Fragment1    *CodeFragment
	Fragment2    *CodeFragment
	Similarity   float64
	CloneType    domain.CloneType
	Confidence   float64
	AnalyzerName string
}

ClonePair represents a detected clone pair between two code fragments.

type CloneStatistics 

type CloneStatistics struct {
	TotalFragments int
	TotalPairs     int
	TypeCounts     map[domain.CloneType]int
	AvgSimilarity  float64
}

CloneStatistics holds aggregate statistics about clone detection results.

type CodeFragment 

type CodeFragment struct {
	ID         int
	FilePath   string
	StartLine  int
	EndLine    int
	StartCol   int
	EndCol     int
	Content    string
	Hash       string // Hex hash of Type-1 normalized content; "" when no source content
	ASTNode    *apted.TreeNode
	NodeCount  int
	LineCount  int
	Complexity int      // Cyclomatic complexity (if applicable)
	Features   []string // Detector-populated clone feature cache for this fragment's tree
}

CodeFragment represents a code fragment for clone detection. It implements GroupableItem so it can be used with the grouping framework.

func (*CodeFragment) ItemID 

func (f *CodeFragment) ItemID() int

ItemID returns the fragment's unique ID for GroupableItem.

func (*CodeFragment) ItemKey 

func (f *CodeFragment) ItemKey() string

ItemKey returns a stable location-based key for the fragment.

func (*CodeFragment) ItemLocation 

func (f *CodeFragment) ItemLocation() ItemLocation

ItemLocation returns the fragment's source location for GroupableItem.

type CommentStripper 

type CommentStripper func(content string) string

CommentStripper removes language-specific comments from source content. Each language adapter provides its own implementation (e.g. `//` and `/* */` for JS/TS, `#` for Python). A nil stripper keeps comments.

type CompleteLinkageGrouping 

type CompleteLinkageGrouping[T GroupableItem] struct {
	// contains filtered or unexported fields
}

CompleteLinkageGrouping ensures all pairs within a group have similarity above threshold.

func NewCompleteLinkageGrouping 

func NewCompleteLinkageGrouping[T GroupableItem](threshold float64) *CompleteLinkageGrouping[T]

func (*CompleteLinkageGrouping[T]) GroupItems 

func (c *CompleteLinkageGrouping[T]) GroupItems(pairs []*ItemPair[T]) []*ItemGroup[T]

func (*CompleteLinkageGrouping[T]) Name 

func (c *CompleteLinkageGrouping[T]) Name() string

type ConnectedGrouping 

type ConnectedGrouping[T GroupableItem] struct {
	// contains filtered or unexported fields
}

ConnectedGrouping groups items by connected components using Union-Find.

func NewConnectedGrouping 

func NewConnectedGrouping[T GroupableItem](threshold float64) *ConnectedGrouping[T]

func (*ConnectedGrouping[T]) GroupItems 

func (c *ConnectedGrouping[T]) GroupItems(pairs []*ItemPair[T]) []*ItemGroup[T]

func (*ConnectedGrouping[T]) Name 

func (c *ConnectedGrouping[T]) Name() string

type FeatureExtractor 

type FeatureExtractor interface {
	ExtractFeatures(ast *apted.TreeNode) ([]string, error)
	ExtractSubtreeHashes(ast *apted.TreeNode, maxHeight int) ([]string, error)
	ExtractNodeSequences(ast *apted.TreeNode, k int) ([]string, error)
}

FeatureExtractor converts AST trees into feature sets for Jaccard similarity.

type GroupDedupeResult 

type GroupDedupeResult[T GroupableItem] struct {
	Groups          []*ItemGroup[T]
	Suppressed      map[string]struct{} // keyed by location and ItemID
	SuppressedPairs map[string]struct{} // keyed by PairKey
}

GroupDedupeResult carries the surviving groups plus the keys of suppressed members (by location and ItemID) and suppressed pairs (by PairKey).

func DedupeCoveredGroups 

func DedupeCoveredGroups[T GroupableItem](groups []*ItemGroup[T]) GroupDedupeResult[T]

DedupeCoveredGroups suppresses whole groups that are covered by another group: every member of the covered group fits inside a distinct member of the covering group (same file, containing line range), and the covering group's similarity is comparable or better. Such groups describe the same duplication relationship through slightly smaller windows and double-count it.

Why DedupeStrictSubsetGroupMembers does not catch this: that pass compares members *within* one group. Here the overlapping windows sit in *different* groups, which stay disconnected when detection forbids the direct same-file pair that would have linked them.

The group with the larger (covering) windows is kept, mirroring the maximal-window policy of filterMaximalPerFile. When two groups cover each other (identical member ranges), the earlier one in the slice wins.

func DedupeStrictSubsetGroupMembers 

func DedupeStrictSubsetGroupMembers[T GroupableItem](groups []*ItemGroup[T], pairs []*ItemPair[T]) GroupDedupeResult[T]

DedupeStrictSubsetGroupMembers removes group members whose source range is a strict subset of (or identical to) another member's range in the same file. Groups reduced to fewer than two members are dropped.

Why this exists: pair-detection paths typically reject *direct* pairs between overlapping same-file fragments, so pairs cannot contain a same-file `(A, B)` where one strictly covers the other. Union-Find grouping, however, still merges such fragments into one group via a shared distinct-file neighbor — e.g., pairs `(A=x.ts:512-542, C=y.ts:1-30)` and `(B=x.ts:515-542, C=y.ts:1-30)` are both legal yet transitively connect A and B. This post-pass collapses those overlapping windows back to the maximal one per file.

For exactly-equal ranges (which UF can produce in the same way), the first occurrence is kept; later duplicates are suppressed for deterministic output.

type GroupableItem 

type GroupableItem interface {
	ItemID() int
	ItemLocation() ItemLocation
}

GroupableItem represents an item that can be grouped (e.g. a code fragment or clone). Items passed to this package must be non-nil.

type GroupingConfig 

type GroupingConfig struct {
	Mode      GroupingMode
	Threshold float64
	KCoreK    int
}

GroupingConfig holds configuration for the grouping strategy.

type GroupingMode 

type GroupingMode string

GroupingMode selects the grouping algorithm. 

const (
	ModeConnected       GroupingMode = "connected"
	ModeKCore           GroupingMode = "k_core"
	ModeStarMedoid      GroupingMode = "star_medoid"
	ModeCompleteLinkage GroupingMode = "complete_linkage"
	ModeCentroid        GroupingMode = "centroid"
)

type GroupingStrategy 

type GroupingStrategy[T GroupableItem] interface {
	GroupItems(pairs []*ItemPair[T]) []*ItemGroup[T]
	Name() string
}

GroupingStrategy is the interface for grouping algorithms.

func NewGroupingStrategy 

func NewGroupingStrategy[T GroupableItem](config GroupingConfig) GroupingStrategy[T]

NewGroupingStrategy returns the appropriate strategy based on config.Mode.

type ItemGroup 

type ItemGroup[T GroupableItem] struct {
	ID         int
	Items      []T
	GroupType  domain.CloneType
	Similarity float64
}

ItemGroup represents a grouping result.

func FilterGroupsWithoutBackingPairs 

func FilterGroupsWithoutBackingPairs[T GroupableItem](groups []*ItemGroup[T], pairs []*ItemPair[T]) []*ItemGroup[T]

FilterGroupsWithoutBackingPairs drops groups whose refreshed metadata shows no positive-similarity pair actually backs them (e.g. every member pair was filtered out upstream), which would otherwise surface a group with zero similarity.

type ItemLocation 

type ItemLocation struct {
	FilePath  string
	StartLine int
	EndLine   int
	StartCol  int
	EndCol    int
}

ItemLocation is the source location of a groupable item. The zero value is valid; items with equal locations fall back to ItemID ordering.

type ItemPair 

type ItemPair[T GroupableItem] struct {
	Item1      T
	Item2      T
	Similarity float64
	PairType   domain.CloneType
}

ItemPair represents a pair of items with similarity information.

func FilterPairsWithSuppressedMembers 

func FilterPairsWithSuppressedMembers[T GroupableItem](pairs []*ItemPair[T], suppressed map[string]struct{}) []*ItemPair[T]

FilterPairsWithSuppressedMembers removes pairs that reference a suppressed member. Identity keys returned by DedupeStrictSubsetGroupMembers distinguish equal-location items; location-only ItemKey values remain accepted when a caller intentionally wants to suppress every item at a location.

func FilterSuppressedPairs 

func FilterSuppressedPairs[T GroupableItem](pairs []*ItemPair[T], suppressed map[string]struct{}) []*ItemPair[T]

FilterSuppressedPairs removes pairs whose PairKey is in the suppressed set.

type KCoreGrouping 

type KCoreGrouping[T GroupableItem] struct {
	// contains filtered or unexported fields
}

KCoreGrouping ensures each item has at least k similar neighbors.

func NewKCoreGrouping 

func NewKCoreGrouping[T GroupableItem](threshold float64, k int) *KCoreGrouping[T]

func (*KCoreGrouping[T]) GroupItems 

func (kg *KCoreGrouping[T]) GroupItems(pairs []*ItemPair[T]) []*ItemGroup[T]

func (*KCoreGrouping[T]) Name 

func (kg *KCoreGrouping[T]) Name() string

type PairClassifier 

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

PairClassifier classifies clone pairs from structural similarity, gating Type-1 on exact textual match and Type-2 on syntactic (normalized AST) similarity.

func NewPairClassifier 

func NewPairClassifier(config ClassifierConfig, textual *TextualSimilarityAnalyzer, syntactic *SyntacticSimilarityAnalyzer) *PairClassifier

NewPairClassifier creates a pair classifier. A nil textual analyzer disables the Type-1 gate (no pair can be confirmed as Type-1); a nil syntactic analyzer disables the Type-2 gate.

func (*PairClassifier) CapNonTextualSimilarity added in v0.2.7 

func (c *PairClassifier) CapNonTextualSimilarity(similarity float64) float64

CapNonTextualSimilarity caps similarity just below the Type-1 threshold so that pairs without an exact textual match never report a Type-1-level similarity. ClassifyPair applies it internally; callers that classify pairs outside ClassifyPair (e.g. a semantic Type-4 path) should apply it to the similarity they report so values stay comparable across clone types.

func (*PairClassifier) ClassifyPair 

func (c *PairClassifier) ClassifyPair(f1, f2 *CodeFragment, structuralSimilarity float64) (domain.CloneType, float64)

ClassifyPair classifies a clone pair from its precomputed structural (APTED) similarity. Returns the clone type (0 when the pair is not a significant clone) and the possibly capped similarity actually used for classification.

func (*PairClassifier) PassesJaccardPreFilter 

func (c *PairClassifier) PassesJaccardPreFilter(f1, f2 *CodeFragment) bool

PassesJaccardPreFilter reports whether a pair survives the cheap feature Jaccard rejection filter. Pairs without pre-computed features always pass.

type SimilarityAnalyzer 

type SimilarityAnalyzer interface {
	ComputeSimilarity(f1, f2 *CodeFragment) float64
	Name() string
}

SimilarityAnalyzer computes similarity between two code fragments.

type StarMedoidGrouping 

type StarMedoidGrouping[T GroupableItem] struct {
	// contains filtered or unexported fields
}

StarMedoidGrouping uses iterative medoid optimization for balanced precision/recall.

func NewStarMedoidGrouping 

func NewStarMedoidGrouping[T GroupableItem](threshold float64) *StarMedoidGrouping[T]

func (*StarMedoidGrouping[T]) GroupItems 

func (s *StarMedoidGrouping[T]) GroupItems(pairs []*ItemPair[T]) []*ItemGroup[T]

func (*StarMedoidGrouping[T]) Name 

func (s *StarMedoidGrouping[T]) Name() string

type StructuralAnalyzer 

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

StructuralAnalyzer computes structural similarity using APTED tree edit distance.

func NewStructuralAnalyzer 

func NewStructuralAnalyzer(costModel apted.CostModel, normMode apted.NormalizationMode) *StructuralAnalyzer

NewStructuralAnalyzer creates a new structural similarity analyzer.

func (*StructuralAnalyzer) ComputeDistanceAndSimilarity 

func (s *StructuralAnalyzer) ComputeDistanceAndSimilarity(f1, f2 *CodeFragment) (float64, float64)

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

func (*StructuralAnalyzer) ComputeSimilarity 

func (s *StructuralAnalyzer) ComputeSimilarity(f1, f2 *CodeFragment) float64

ComputeSimilarity computes the structural similarity between two fragments using APTED.

func (*StructuralAnalyzer) Name 

func (s *StructuralAnalyzer) Name() string

Name returns the name of this analyzer.

type SyntacticSimilarityAnalyzer 

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

SyntacticSimilarityAnalyzer computes syntactic similarity using normalized AST hash comparison with Jaccard coefficient. This is used for Type-2 clone detection (syntactically identical but with different identifiers/literals).

Unlike an APTED-based approach which measures tree edit distance, this implementation compares sets of normalized node hashes. This eliminates false positives from structurally similar but semantically different code, as only nodes with identical normalized structure contribute to similarity.

func NewSyntacticSimilarityAnalyzer 

func NewSyntacticSimilarityAnalyzer() *SyntacticSimilarityAnalyzer

NewSyntacticSimilarityAnalyzer creates a new syntactic similarity analyzer using normalized AST hash comparison that ignores identifier and literal differences.

func NewSyntacticSimilarityAnalyzerWithExtractor added in v0.2.1 

func NewSyntacticSimilarityAnalyzerWithExtractor(extractor *ASTFeatureExtractor) *SyntacticSimilarityAnalyzer

NewSyntacticSimilarityAnalyzerWithExtractor creates a syntactic similarity analyzer that uses a caller-configured feature extractor (e.g. with language-specific pattern and literal-like label names).

func (*SyntacticSimilarityAnalyzer) ComputeDistance 

func (s *SyntacticSimilarityAnalyzer) ComputeDistance(f1, f2 *CodeFragment) float64

ComputeDistance computes the syntactic distance between two code fragments. Returns 1 - similarity, so distance ranges from 0 (identical) to 1 (completely different). Returns 0.0 for nil inputs (no distance can be computed).

func (*SyntacticSimilarityAnalyzer) ComputeSimilarity 

func (s *SyntacticSimilarityAnalyzer) ComputeSimilarity(f1, f2 *CodeFragment) float64

ComputeSimilarity computes the syntactic similarity between two code fragments using Jaccard coefficient of normalized AST hash sets. It ignores differences in identifier names and literal values, focusing only on the structural syntax pattern. Pre-computed fragment features are used when available.

func (*SyntacticSimilarityAnalyzer) Name 

func (s *SyntacticSimilarityAnalyzer) Name() string

Name returns the name of this analyzer.

type TextualSimilarityAnalyzer 

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

TextualSimilarityAnalyzer computes textual similarity for Type-1 clone detection. Type-1 clones are identical code fragments except for whitespace and comments.

func NewTextualSimilarityAnalyzer 

func NewTextualSimilarityAnalyzer(stripComments CommentStripper) *TextualSimilarityAnalyzer

NewTextualSimilarityAnalyzer creates a textual similarity analyzer with whitespace normalization enabled and the given language comment stripper.

func NewTextualSimilarityAnalyzerWithConfig 

func NewTextualSimilarityAnalyzerWithConfig(config TextualSimilarityConfig) *TextualSimilarityAnalyzer

NewTextualSimilarityAnalyzerWithConfig creates a textual similarity analyzer with custom configuration.

func (*TextualSimilarityAnalyzer) ComputeSimilarity 

func (t *TextualSimilarityAnalyzer) ComputeSimilarity(f1, f2 *CodeFragment) float64

ComputeSimilarity computes the textual similarity between two code fragments. Returns 1.0 for identical content (after normalization), or a Levenshtein-based similarity score for near-matches.

func (*TextualSimilarityAnalyzer) HashFragmentContent 

func (t *TextualSimilarityAnalyzer) HashFragmentContent(content string) string

HashFragmentContent returns a hex-encoded FNV-64a hash of the Type-1 normalized content. Two fragments with the same hash are Type-1 clones of each other. Returns "" when the content is empty after normalization (e.g. the fragment was extracted without source content).

func (*TextualSimilarityAnalyzer) IsExactMatch 

func (t *TextualSimilarityAnalyzer) IsExactMatch(f1, f2 *CodeFragment) bool

IsExactMatch reports whether two fragments have identical source text after Type-1 normalization. Near matches are deliberately not treated as Type-1.

func (*TextualSimilarityAnalyzer) Name 

func (t *TextualSimilarityAnalyzer) Name() string

Name returns the name of this analyzer.

func (*TextualSimilarityAnalyzer) NormalizeContent 

func (t *TextualSimilarityAnalyzer) NormalizeContent(content string) string

NormalizeContent normalizes source code content for comparison: strips comments via the configured language stripper and collapses whitespace.

type TextualSimilarityConfig 

type TextualSimilarityConfig struct {
	NormalizeWhitespace bool
	StripComments       CommentStripper
}

TextualSimilarityConfig holds configuration for textual similarity analysis.

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.