Documentation
¶
Overview ¶
Package syntax provides unified AST representation for code duplication detection.
This package bridges the gap between language-specific AST parsers (golang/ast for Go code) and the language-agnostic suffix tree used by the detection algorithm.
Core Types: - Node: Unified syntax tree node representing any language construct - Match: Represents a clone match with fragments (group of nodes) - Frags: Slice of node sequences (each fragment is a sequence of nodes)
Design: - Language-agnostic: Works with any language that provides a parser - Type-safe: Uses int32 for types (see golang/constants for mapping) - Memory-optimized: Careful field ordering for cache efficiency - Position-aware: Tracks byte positions and line numbers for all nodes
Usage Flow: 1. Parse source files -> language-specific AST (go/ast, etc.) 2. Transform AST -> unified syntax.Node tree (see syntax/golang/) 3. Build suffix tree from Node sequence (suffixtree.Update()) 4. Find duplicates using suffix tree (FindDuplOver()) 5. Convert matches to complete syntax units (FindSyntaxUnits())
Key Functions: - FindSyntaxUnits(): Converts suffix tree matches to complete syntax units - hashSeq(): Creates hash of node sequence for duplicate detection - isCyclic/spansMultipleFiles(): Validation helpers
Performance: - maxChildrenSerial constant prevents goroutine stack overflow - Node struct is 40B (37.5% reduction from 64B) via int32 fields - See MEMORY_LAYOUT_OPTIMIZATION_PLAN.md for details
Index ¶
- func CountUniqueFiles(group [][]*Node) int
- func DecodeBaseType(t int32) int32
- func EncodeSemanticType(baseType int32, identifierName string, semanticEnabled bool) int32
- func HashIdentifier(name string) int32
- func InternFilename(filename string) string
- func Unique(group [][]*Node) [][]*Node
- type Match
- type Node
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CountUniqueFiles ¶
CountUniqueFiles returns the number of unique files in a clone group.
func DecodeBaseType ¶ added in v0.4.0
DecodeBaseType extracts the base AST node type from a semantic-encoded type.
func EncodeSemanticType ¶ added in v0.4.0
EncodeSemanticType combines a base node type with an identifier hash. Layout: [24 bits identifier hash][8 bits base type]. When semanticEnabled is false, returns baseType unchanged.
func HashIdentifier ¶ added in v0.4.0
HashIdentifier computes a 24-bit FNV-1a hash of an identifier name. The result fits in the upper 24 bits of int32 when shifted, allowing the lower 8 bits to store the base node type.
func InternFilename ¶ added in v0.4.0
InternFilename returns a canonicalized, deduplicated copy of the filename. Subsequent calls with equal strings return the same underlying string data, reducing memory usage for AST trees with repeated filenames.
Types ¶
type Match ¶
func FindSyntaxUnits ¶
func FindSyntaxUnits(data []*Node, m suffixtree.Match, threshold int) Match
FindSyntaxUnits finds all complete syntax units in the match group and returns them with the corresponding hash.
type Node ¶
type Node struct {
Type int32
Pos int32
End int32
Owns int32
Children []*Node
Filename string
Name string
Statement bool
Fingerprint int32
}
Node represents a syntax tree node.
Memory Layout Optimized with int32 fields: - int32 fields grouped for cache efficiency (4B each, 16B total) - pointer field (8B) - string headers at end (32B: Filename + Name) - Fingerprint int32 + Statement bool fit in trailing padding (4B+1B+3B) Total: 64B.
The Name field stores the original Go identifier for Ident, SelectorExpr, and FuncDecl nodes. It enables actionability analysis to distinguish `nil` from `err`, `Unlock` from `Close`, etc. Empty string means "not an identifier-bearing node" or structural-only mode.
The Statement field marks direct children of block-like nodes (BlockStmt, CaseClause.Body, CommClause.Body). When true, serial() fingerprints the entire subtree into a single composite Type token instead of emitting each descendant individually. This makes threshold mean "N duplicated statements" rather than "N arbitrary AST nodes.".
func NewSyntheticFileNode ¶
NewSyntheticFileNode creates a synthetic node representing an entire file. This is used for file-level duplicate detection where we want to match entire files rather than specific code fragments.
func SerializeWithMaxChildren ¶ added in v0.4.0
SerializeWithMaxChildren serializes a node tree with a caller-specified maximum children cap. This allows the job layer to thread config.MaxChildrenSerial into the serialization without a global variable.
func (*Node) AddChildren ¶
func (*Node) Clone ¶ added in v0.4.0
Clone returns a deep copy of the node subtree. The incremental cache stores serialized node trees that are shared across goroutines on a cache hit, where each file rewrites Filename; Clone yields an independent copy safe to mutate.
func (*Node) Val ¶
func (n *Node) Val() suffixtree.TokenValue
Val returns the token value for suffix tree compatibility. Implements the suffixtree.Token interface.
For statement nodes, returns the composite Fingerprint so the suffix tree matches at statement granularity. For non-statement nodes, returns the semantic-encoded Type.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package golang provides Go AST parsing and transformation for clone detection.
|
Package golang provides Go AST parsing and transformation for clone detection. |
|
Package templ provides AST parsing for templ files using the official templ parser.
|
Package templ provides AST parsing for templ files using the official templ parser. |