Diff

Save review time by focusing on changes that impact code execution

AST (Abstract Syntax Tree) diffing uses a graph representation to compute tree diffs.

Git Diff

AST Diff

How it Works

1. Initialization of Vertices and Edges

   • Creating an AST diff starts by detecting vertices that represent the current state of syntax nodes from both the left-hand side (LHS) and right-hand side (RHS) of the code.

   • Edges are defined to represent possible transformations or relationships between these vertices.

2. Identification of Syntax Nodes

   • Each vertex corresponds to specific syntax nodes in the code. The algorithm identifies the unmatched syntax nodes on both sides, setting up the initial conditions for the diffing process.

3. Neighbor Calculation

   • For each vertex, the algorithm calculates its neighbors by considering all possible edges (transformations). This includes unchanged nodes, novel atoms, and various types of replacements or delimiter entries.

   • Neighbors are determined based on potential paths the code could take, reflecting possible changes and their impacts.

4. Graph Traversal

   • The diffing algorithm traverses the graph, moving from one vertex to its neighbors based on the defined edges.

   • During traversal, it evaluates the cost associated with each edge, preferring paths that minimize changes while accurately reflecting the real impact on the code.

5. Change Map Population

   • As the traversal proceeds, the algorithm populates a change map with the identified changes. This map records details about unchanged nodes, replacements, and novel elements.

   • The change map provides a comprehensive view of the differences, allowing for precise understanding and analysis.

6. Impact Analysis

   • The populated change map is used to analyze the real impact of code changes. By examining the relationships and transformations recorded, the algorithm identifies significant changes that affect the code's functionality, readability, or structure.

   • This analysis helps developers understand the true implications of their changes, going beyond superficial differences to uncover deeper impacts.

AST diff saves you critical review time

The AST diffing process accurately identifies changes at a granular level, ensuring that even subtle modifications are captured and analyzed. By representing diffs as vertices and edges, the algorithm efficiently tracks changes and generates a comprehensive change map. This process is optimized to handle various syntax node types and parent-child relationships, ensuring accurate and meaningful diffs.