nonbinary.computer
OR-1 dataflow CPU sketch
1"""Tests for the Resolve pass (name resolution in IRGraph).
2
3Tests verify:
4- Valid programs with all names resolved (AC4.1, AC4.2)
5- Undefined name references with "did you mean" suggestions (AC4.3)
6- Scope violations when cross-referencing function-local labels (AC4.4)
7- Levenshtein distance computation for suggestions (AC4.5)
8"""
9
10from tests.pipeline import parse_lower_resolve
11
12from asm.resolve import _levenshtein
13from asm.errors import ErrorCategory
14
15
16class TestValidResolution:
17 """Tests for successful name resolution (AC4.1, AC4.2)."""
18
19 def test_simple_two_node_edge_resolves(self, parser):
20 """Simple program with two nodes and an edge between them resolves with no errors."""
21 graph = parse_lower_resolve(
22 parser,
23 """\
24 &a <| pass
25 &b <| add
26 &a |> &b:L
27 """,
28 )
29
30 # Should have no resolution errors
31 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
32 scope_errors = [e for e in graph.errors if e.category == ErrorCategory.SCOPE]
33 assert len(name_errors) == 0, f"Unexpected NAME errors: {name_errors}"
34 assert len(scope_errors) == 0, f"Unexpected SCOPE errors: {scope_errors}"
35
36 def test_cross_function_wiring_via_global_nodes(self, parser):
37 """Cross-function wiring via @nodes resolves correctly.
38
39 Test that a global node can be wired to and from function-scoped labels.
40 After lowering, these are stored as region.body edges with simple names,
41 but when resolved, they reference the flattened qualified names.
42 """
43 graph = parse_lower_resolve(
44 parser,
45 """\
46 @bridge <| pass
47
48 $foo |> {
49 &a <| pass
50 &a |> @bridge:L
51 }
52
53 $bar |> {
54 &b <| add
55 @bridge |> &b:L
56 }
57 """,
58 )
59
60 # Should have no resolution errors
61 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
62 assert len(name_errors) == 0, f"Unexpected NAME errors: {name_errors}"
63
64 def test_function_scoped_labels_within_same_function_resolve(self, parser):
65 """Program with function-scoped labels and edges within same function resolve correctly."""
66 graph = parse_lower_resolve(
67 parser,
68 """\
69 $main |> {
70 &input <| pass
71 &process <| add
72 &output <| pass
73 &input |> &process:L
74 &process |> &output:L
75 }
76 """,
77 )
78
79 # Should have no resolution errors
80 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
81 assert len(name_errors) == 0, f"Unexpected NAME errors: {name_errors}"
82
83 def test_global_and_function_nodes_coexist(self, parser):
84 """Program with both global @nodes and function-scoped &labels resolves correctly."""
85 graph = parse_lower_resolve(
86 parser,
87 """\
88 @global <| pass
89
90 $worker |> {
91 &local <| add
92 &local |> @global:L
93 }
94 """,
95 )
96
97 # Should have no resolution errors
98 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
99 assert len(name_errors) == 0, f"Unexpected NAME errors: {name_errors}"
100
101
102class TestUndefinedReference:
103 """Tests for undefined name errors with suggestions (AC4.3)."""
104
105 def test_undefined_label_produces_name_error(self, parser):
106 """Edge referencing undefined &nonexistent produces error with NAME category."""
107 graph = parse_lower_resolve(
108 parser,
109 """\
110 &a <| pass
111 &b <| add
112 &a |> &nonexistent:L
113 """,
114 )
115
116 # Should have a NAME error
117 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
118 assert len(name_errors) == 1
119 error = name_errors[0]
120 assert "undefined" in error.message.lower()
121
122 def test_error_includes_source_location(self, parser):
123 """NAME error includes source location (line/column)."""
124 graph = parse_lower_resolve(
125 parser,
126 """\
127 &a <| pass
128 &b <| add
129 &a |> &nonexistent:L
130 """,
131 )
132
133 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
134 assert len(name_errors) == 1
135 error = name_errors[0]
136 # Error should have a valid location
137 assert error.loc.line > 0
138 assert error.loc.column >= 0
139
140 def test_suggestion_for_similar_name(self, parser):
141 """Reference to &nonexistant suggests &nonexistent if it exists."""
142 graph = parse_lower_resolve(
143 parser,
144 """\
145 &nonexistent <| pass
146 &a <| add
147 &a |> &nonexistant:L
148 """,
149 )
150
151 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
152 assert len(name_errors) == 1
153 error = name_errors[0]
154 # Should have suggestions
155 assert len(error.suggestions) > 0
156
157
158class TestScopeViolation:
159 """Tests for scope violation errors (AC4.4)."""
160
161 def test_cross_scope_reference_produces_scope_error(self, parser):
162 """Reference to function-local label from top level produces SCOPE error."""
163 graph = parse_lower_resolve(
164 parser,
165 """\
166 $foo |> {
167 &private <| pass
168 }
169
170 &top <| add
171 &top |> &private:L
172 """,
173 )
174
175 # Should have a SCOPE error, not NAME
176 scope_errors = [e for e in graph.errors if e.category == ErrorCategory.SCOPE]
177 assert len(scope_errors) == 1
178 error = scope_errors[0]
179 # Error should identify the function containing the label
180 assert "$foo" in error.message or "function" in error.message.lower()
181
182 def test_scope_error_mentions_actual_scope(self, parser):
183 """Scope error message mentions the function where label is actually defined."""
184 graph = parse_lower_resolve(
185 parser,
186 """\
187 $foo |> {
188 &private <| pass
189 }
190
191 $bar |> {
192 &x <| add
193 }
194
195 &top <| pass
196 &top |> &private:L
197 """,
198 )
199
200 scope_errors = [e for e in graph.errors if e.category == ErrorCategory.SCOPE]
201 assert len(scope_errors) == 1
202 error = scope_errors[0]
203 assert "$foo" in error.message
204
205 def test_reference_from_different_function_is_scope_error(self, parser):
206 """Reference to label in $foo from within $bar produces SCOPE error."""
207 graph = parse_lower_resolve(
208 parser,
209 """\
210 $foo |> {
211 &data <| const, 42
212 }
213
214 $bar |> {
215 &use <| add
216 &use |> &data:L
217 }
218 """,
219 )
220
221 # Should have a SCOPE error
222 scope_errors = [e for e in graph.errors if e.category == ErrorCategory.SCOPE]
223 assert len(scope_errors) == 1
224
225
226class TestLevenshteinSuggestions:
227 """Tests for Levenshtein distance suggestions (AC4.5)."""
228
229 def test_levenshtein_kitten_sitting(self):
230 """Direct test: _levenshtein("kitten", "sitting") == 3."""
231 distance = _levenshtein("kitten", "sitting")
232 assert distance == 3
233
234 def test_levenshtein_identical_strings(self):
235 """_levenshtein identical strings returns 0."""
236 assert _levenshtein("test", "test") == 0
237
238 def test_levenshtein_empty_string(self):
239 """_levenshtein empty string."""
240 assert _levenshtein("", "") == 0
241 assert _levenshtein("abc", "") == 3
242 assert _levenshtein("", "abc") == 3
243
244 def test_levenshtein_single_insertion(self):
245 """_levenshtein single character insertion."""
246 assert _levenshtein("add", "addd") == 1
247
248 def test_levenshtein_single_deletion(self):
249 """_levenshtein single character deletion."""
250 assert _levenshtein("addd", "add") == 1
251
252 def test_levenshtein_single_substitution(self):
253 """_levenshtein single character substitution."""
254 assert _levenshtein("cat", "bat") == 1
255
256 def test_suggestion_for_typo_one_char(self, parser):
257 """Reference to &ad suggests &add (distance 1)."""
258 graph = parse_lower_resolve(
259 parser,
260 """\
261 &add <| pass
262 &x <| pass
263 &x |> &ad:L
264 """,
265 )
266
267 # Should have NAME error with suggestion
268 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
269 assert len(name_errors) == 1
270 error = name_errors[0]
271 assert len(error.suggestions) > 0
272 # Suggestion should include &add
273 suggestion_text = " ".join(error.suggestions)
274 assert "add" in suggestion_text
275
276 def test_suggestion_for_typo_two_chars(self, parser):
277 """Reference to &addd suggests &add (distance 1)."""
278 graph = parse_lower_resolve(
279 parser,
280 """\
281 &add <| pass
282 &x <| pass
283 &x |> &addd:L
284 """,
285 )
286
287 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
288 assert len(name_errors) == 1
289 error = name_errors[0]
290 assert len(error.suggestions) > 0
291 suggestion_text = " ".join(error.suggestions)
292 assert "add" in suggestion_text
293
294 def test_no_suggestion_for_completely_wrong_name(self, parser):
295 """Reference to &completely_wrong with no similar names may have no suggestion."""
296 graph = parse_lower_resolve(
297 parser,
298 """\
299 &add <| pass
300 &x <| pass
301 &x |> &completely_wrong:L
302 """,
303 )
304
305 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
306 assert len(name_errors) == 1
307 # May or may not have suggestions depending on implementation
308 # (best-effort or distance threshold)
309
310 def test_multiple_errors_all_collected(self, parser):
311 """Multiple undefined references all produce errors (error accumulation)."""
312 graph = parse_lower_resolve(
313 parser,
314 """\
315 &a <| pass
316 &b <| add
317 &a |> &undef1:L
318 &b |> &undef2:R
319 """,
320 )
321
322 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
323 # Should have 2 NAME errors (both undefined refs)
324 assert len(name_errors) == 2
325
326
327class TestEdgeCases:
328 """Edge case tests for resolution."""
329
330 def test_empty_program_resolves(self, parser):
331 """Empty program resolves with no errors."""
332 graph = parse_lower_resolve(parser, "")
333 assert len(graph.errors) == 0
334
335 def test_program_only_defs_no_edges_resolves(self, parser):
336 """Program with only definitions and no edges resolves with no errors."""
337 graph = parse_lower_resolve(
338 parser,
339 """\
340 &a <| pass
341 &b <| add
342 &c <| sub
343 """,
344 )
345
346 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
347 assert len(name_errors) == 0
348
349 def test_circular_wiring_resolves(self, parser):
350 """Circular wiring (feedback loops) resolves correctly."""
351 graph = parse_lower_resolve(
352 parser,
353 """\
354 &a <| pass
355 &b <| add
356 &a |> &b:L
357 &b |> &a:R
358 """,
359 )
360
361 name_errors = [e for e in graph.errors if e.category == ErrorCategory.NAME]
362 assert len(name_errors) == 0