mizchi/similarity

The project uses a hybrid parsing approach to balance high performance with multi-language support.

• JavaScript/TypeScript: Uses oxc_parser to maintain maximum performance with zero regression.
• Python: Uses tree-sitter to provide language support.
• Multi-language Support: A common abstraction layer allows the project to analyze mixed codebases (e.g., JS/TS and Python) using shared similarity calculation logic.

While Python parsing is slower than the oxc implementation (roughly 9x-10x slower for parsing and 2.5x-3.7x slower for function extraction), the absolute speeds (e.g., ~65µs for medium Python files) remain practical for real-world use.

The similarity detection library is built as a Rust workspace designed for multi-language support. It separates core logic from language-specific implementations using a trait-based architecture.

• similarity-core: Contains the language-agnostic core algorithms and utilities.
• similarity-ts: Provides TypeScript/JavaScript specific implementations.
• similarity-py: Provides Python specific implementations.
• similarity-rs: Provides Rust specific implementations.

Language-specific crates implement the LanguageParser trait defined in the core library to allow the core algorithms to operate on different programming languages.

The --experimental-overlap flag enables detection of partial code overlaps within or across functions. This is useful for finding copy-pasted fragments inside larger functions.

Experimental Parameters:

• --overlap-min-window: Minimum AST nodes to consider (default: 8)
• --overlap-max-window: Maximum AST nodes to consider (default: 25)
• --overlap-size-tolerance: Size variation tolerance (default: 0.25)

# Basic overlap detection
similarity-ts ./src --experimental-overlap

# Custom overlap parameters
similarity-ts ./src --experimental-overlap \
  --threshold 0.75 \
  --overlap-min-window 8 \
  --overlap-max-window 25 \
  --overlap-size-tolerance 0.25

When using similarity-rs for Rust code, be aware of the following:

1. Test Code False Positives: Test functions are structurally similar and often trigger false positives. Always use --skip-test if possible.
2. Importance of min-tokens: Failing to set a min-tokens value (recommended: 50+) will increase false positives in short functions.
3. Language Specifics:
   • Code generated by macro expansion is not detected.
   • Generic specialization (monomorphization) is treated as separate functions.

TSED is a metric used to evaluate code similarity by analyzing the Abstract Syntax Tree (AST) of code rather than just raw text. It is designed to capture structural similarity, making it more effective for evaluating code generation tasks (like LLM outputs) than traditional statistical metrics like BLEU or Jaccard similarity.

How TSED works:

1. Code Analysis: Uses tree-sitter to convert source code into an AST.
2. Tree Edit Distance Calculation: Employs the APTED algorithm to calculate the minimum operations required to transform one tree into another.
3. Normalization: The resulting distance is normalized to a score between 0 and 1.

Mathematical Formula:

$$\Delta(G_1, G_2) = \min_{ops} \sum w(op_i)$$

$$\text{TSED} = \max{1 - \delta / \text{MaxNodes}(G_1, G_2), 0}$$

Features

• CSS and SCSS parsing: Uses tree-sitter for AST analysis.
• BEM Support: Flattens nested SCSS syntax using BEM notation.
• Detection Types: Identifies exact duplicates, style duplicates (same styles, different selectors), BEM variations, and selector conflicts.
• Advanced Analysis: Includes shorthand property expansion and CSS specificity calculation.
• Output Formats: Supports standard, vscode, and json.

Limitations

• No SCSS Variable Resolution: Variables are not resolved during analysis.
• No Mixin Expansion: Mixins are not expanded.
• No Import Resolution: Import statements are not followed.
• Limited Cross-file BEM Detection: Detection of BEM components across different files is limited.

MinHash combined with Locality-Sensitive Hashing (LSH) is used for fast, approximate similarity search based on token sets. It is best suited for token-based similarity and detecting variable renaming.

Workflow:

1. Tokens are extracted from each file's AST.
2. MinHash signatures (fixed-size fingerprints) are generated.
3. LSH groups similar signatures into buckets.
4. Only files within the same buckets are compared, making the query time O(1) and preprocessing O(N).

Characteristics:

• Accuracy: Approximates Jaccard similarity.
• Best for: Token-based similarity and variable renaming detection.

const repo = new CodeRepository();
await repo.loadFiles("**/*.ts");
const similar = repo.findSimilarByMinHash("file.ts", 0.7);

The tool outputs results in a VSCode-compatible format. This allows you to click on file paths in the terminal to jump directly to the offending code.

Output Structure:

• File Path & Line: Shows the file and the line range where the duplicate was found.
• Similarity Details: Displays the similarity percentage and a priority score (calculated as lines × similarity).
• Sorting: Results are sorted by priority to highlight the most impactful duplications first.

Duplicates in src/utils.ts:
────────────────────────────────────────────────────────────
  src/utils.ts:10 | L10-15 similar-function: calculateSum
  src/utils.ts:20 | L20-25 similar-function: addNumbers
  Similarity: 85.00%, Priority: 8.5 (lines: 10)

The tool uses Tree Structure Edit Distance (TSED) to compare the Abstract Syntax Trees (AST) of Elixir functions.

Key Capabilities

• AST-based comparison: Uses Tree-sitter for fast, structural analysis.
• Language features: Supports pattern matching, guard clauses, pipe operators, and anonymous functions.
• Definitions: Recognizes module, protocol, and implementation definitions.
• Configurable logic: You can adjust the --rename-cost (default 1.0) to change how much weight is given to identifier changes during comparison and --min-lines (default 5) to ignore very small functions.