Quantinuum / Quantinuum/guppylang

[Feature]: Rich cycle diagnostics for recursive structs, enums, and type aliases

Open
#1,908 0 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

A-compiler C-feature-accepted D-medium P-help-wanted
Dominant language
Python
Stars
147
Forks
42
Avg merge
1d 9h
Merged PRs (30d)
60

Description

Problem Statement

When a recursive (cyclic) struct, enum, or type alias is detected, Guppy currently reports a single generic diagnostic:

Error: Unsupported (at recursive.py:6:14)
  |
4 | @guppy.struct
5 | class MyStruct:
6 |     x: "tuple[MyStruct, int]"
  |               ^^^^^^^^ Recursive definitions are not supported

Guppy compilation failed due to 1 previous error

This is fine for a direct self-reference, but for cycles that span several definitions the message only points at a single edge of the cycle. The user is left to reconstruct the rest of the cycle by hand, e.g. for a mutually-recursive chain Alias1 -> Alias2 -> Alias3 -> Alias2 the error only underlines one type_alias(...) line and never names the other members of the cycle.

This affects all three recursive type definitions equally: structs, enums, and (newly) type aliases.

Proposed Solution

Produce a richer cycle diagnostic that:

  1. Names every definition that participates in the cycle, in order, e.g. Type cycle detected: `Alias1` -> `Alias2` -> `Alias3` -> `Alias1`.
  2. Attaches a sub-diagnostic note at each definition site in the cycle (`Alias2` defined here, etc.), Rust-style.
  3. Handles cycles whose members live in different files (today these notes are skipped because add_sub_diagnostic requires all notes to share the error's file — see diagnostic.py).

An earlier iteration of the type-alias PR (#1645) implemented exactly this for aliases via a RecursiveTypeAliasError with per-member notes. For example a mutually-recursive alias pair rendered as:

Error: Recursive type alias (at mutual_recursive.py:5:0)
  |
3 |
4 | Alias1 = guppy.type_alias("Alias1", "Alias2")
5 | Alias2 = guppy.type_alias("Alias2", "Alias1")
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Type alias cycle detected:
  |                                               `Alias1` -> `Alias2` -> `Alias1`

Note:
  |
3 |
4 | Alias1 = guppy.type_alias("Alias1", "Alias2")
5 | Alias2 = guppy.type_alias("Alias2", "Alias1")
  | --------------------------------------------- `Alias1` defined here

Guppy compilation failed due to 1 previous error

…and a partial cycle (an alias that merely leads into a cycle) correctly reported only the members actually on the cycle:

Error: Recursive type alias (at partial_cycle.py:6:0)
  |
4 | Alias1 = guppy.type_alias("Alias1", "Alias2")
5 | Alias2 = guppy.type_alias("Alias2", "Alias3")
6 | Alias3 = guppy.type_alias("Alias3", "Alias2")
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Type alias cycle detected:
  |                                               `Alias2` -> `Alias3` -> `Alias2`

Note:
  |
4 | Alias1 = guppy.type_alias("Alias1", "Alias2")
5 | Alias2 = guppy.type_alias("Alias2", "Alias3")
  | --------------------------------------------- `Alias2` defined here

Guppy compilation failed due to 1 previous error

That alias-specific implementation was deliberately removed in favour of reusing the shared check_not_recursive helper in guppylang_internals/definition/util.py, so that aliases stay consistent with structs and enums. The right place to add rich notes is therefore that shared helper, so all three definition kinds benefit at once.

The DFS in _check_not_recursive already has the full path of DefIds when it detects a cycle, so the cycle members are readily available; the work is mainly in constructing the diagnostic (and resolving the cross-file note limitation).

Component

Guppy Compiler

Effort Estimate

Medium - Moderate complexity

Additional Context
  • Shared recursion check: guppylang_internals/definition/util.py (check_not_recursive / _check_not_recursive).
  • Cross-file note limitation: add_sub_diagnostic in diagnostic.py asserts all notes share the error's file.
  • Existing test fixtures that would gain richer output:
    • tests/error/alias_errors/{recursive,mutual_recursive,partial_cycle,struct_cycle,enum_cycle}.py
    • tests/error/struct_errors/{recursive,mutual_recursive,...}.py
    • tests/error/enum_errors/{recursive,mutual_recursive,...}.py
  • Related: #1645 (type aliases), #1809 (shared recursive-definition validation).

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in guppylang_internals/definition/util.py at check_not_recursive and _check_not_recursive, then read add_sub_diagnostic in diagnostic.py to understand the cross-file limitation. Run the recursive, mutual_recursive, and partial_cycle fixtures under tests/error/alias_errors, struct_errors, and enum_errors. Done means cycle members and definition-site notes appear for structs, enums, and aliases, including cycles spanning files.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
compilers
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.