0
# AST Verification
1

2
AST verification utilities for ensuring code transformations preserve semantic equivalence. These functions validate that reformatting doesn't change the abstract syntax tree structure of Python code.
3

4
## Capabilities
5

6
### AST Verification Classes
7

8
Core classes for verifying AST equivalence between original and reformatted code.
9

10
```python { .api }
11
class ASTVerifier:
12
    """
13
    Verify if reformatted TextDocument is AST-equivalent to baseline.
14
    
15
    Keeps in-memory data about previous comparisons to improve performance.
16
    """
17
    
18
    def __init__(self, baseline: TextDocument) -> None:
19
        """
20
        Initialize verifier with baseline document.
21
        
22
        Parameters:
23
        - baseline: The baseline document to compare against
24
        """
25
    
26
    def is_equivalent_to_baseline(self, document: TextDocument) -> bool:
27
        """
28
        Returns true if document is AST-equivalent to baseline.
29
        
30
        Parameters:
31
        - document: Document to compare against baseline
32
        
33
        Returns:
34
        True if documents are AST-equivalent, False otherwise
35
        """
36

37
class BinarySearch:
38
    """
39
    Effectively search the first index for which a condition is True.
40
    
41
    Used for finding the minimal change that breaks AST equivalence.
42
    """
43
    
44
    def __init__(self, low: int, high: int) -> None:
45
        """
46
        Initialize binary search with range bounds.
47
        
48
        Parameters:
49
        - low: Lower bound of search range
50
        - high: Upper bound of search range
51
        """
52
    
53
    def get_next(self) -> int:
54
        """Get the next integer index to try."""
55
    
56
    def respond(self, value: bool) -> None:
57
        """
58
        Provide a False or True answer for the current integer index.
59
        
60
        Parameters:
61
        - value: Response for current index
62
        """
63
    
64
    @property
65
    def found(self) -> bool:
66
        """Return True if the lowest True response index has been found."""
67
    
68
    @property
69
    def result(self) -> int:
70
        """Return the lowest index with a True response."""
71
```
72

73
### AST Parsing and Comparison
74

75
Functions for parsing and comparing Python ASTs with error handling.
76

77
```python { .api }
78
def parse_ast(src: str) -> ast.AST:
79
    """
80
    Parse source code with fallback for type comments.
81
    
82
    This function tries multiple Python version feature sets
83
    and handles both type comments and syntax variations.
84
    
85
    Parameters:
86
    - src: Python source code to parse
87
    
88
    Returns:
89
    Parsed AST node
90
    
91
    Raises:
92
    SyntaxError: If source cannot be parsed with any supported syntax
93
    """
94

95
def stringify_ast(node: ast.AST) -> Iterator[str]:
96
    """
97
    Generate strings to compare ASTs by content using a simple visitor.
98
    
99
    Parameters:
100
    - node: Root AST node to stringify
101
    
102
    Yields:
103
    String representations of AST nodes for comparison
104
    """
105
```
106

107
### Exception Types
108

109
Exceptions specific to AST verification operations.
110

111
```python { .api }
112
class NotEquivalentError(Exception):
113
    """Exception to raise if two ASTs being compared are not equivalent."""
114
```
115

116
## Usage Examples
117

118
### Basic AST Verification
119

120
```python
121
from darker.verification import ASTVerifier
122
from darkgraylib.utils import TextDocument
123

124
# Set up verification with baseline code
125
original_code = TextDocument.from_str('''
126
def hello(name):
127
    print(f"Hello, {name}!")
128
''')
129

130
verifier = ASTVerifier(original_code)
131

132
# Check if reformatted code is equivalent
133
formatted_code = TextDocument.from_str('''
134
def hello(name):
135
    print(f"Hello, {name}!")
136
''')
137

138
is_equivalent = verifier.is_equivalent_to_baseline(formatted_code)
139
print(f"Code is AST-equivalent: {is_equivalent}")
140
```
141

142
### Binary Search for Error Location
143

144
```python
145
from darker.verification import BinarySearch
146

147
# Find first line where condition becomes true
148
search = BinarySearch(0, 100)
149

150
while not search.found:
151
    line_num = search.get_next()
152
    # Test some condition on line_num
153
    condition_met = some_test_function(line_num)
154
    search.respond(condition_met)
155

156
print(f"First line where condition is true: {search.result}")
157
```
158

159
### Custom AST Parsing
160

161
```python
162
from darker.verification import parse_ast, stringify_ast
163

164
try:
165
    source = '''
166
    def example() -> None:
167
        x: int = 42
168
        return None
169
    '''
170
    
171
    ast_tree = parse_ast(source)
172
    ast_strings = list(stringify_ast(ast_tree))
173
    
174
    print("AST structure:")
175
    for line in ast_strings[:10]:  # Show first 10 lines
176
        print(line)
177
        
178
except SyntaxError as e:
179
    print(f"Could not parse source: {e}")
180
```