Implement SCC-Based Cycle Detection for Typedefs
# Implement SCC-Based Cycle Detection for Typedefs
### Description
Currently, our compiler detects type cycles dynamically during type resolution using a DFS-based stack guard. While this works for small-to-medium projects, it can produce multiple errors per cycle and does not provide a global view of mutually recursive typedefs.
We should consider implementing a Strongly Connected Component (SCC) based cycle detection pass in the future.
### Current System:
Uses ty_caches.cache per symbol.
DFS-based stack guard detects cycles during resolve_symbol_type.
Cycles are reported immediately upon revisiting a symbol.
No global typedef graph exists; edges are temporary during resolution.
Integrates naturally with type normalization but may report multiple errors for mutual recursion.
### Proposed SCC Approach:
Build a global graph of typedef references: SymbolID -> Vec<SymbolID> (using sema_ty_symbol_refs). Run Tarjan’s SCC algorithm to identify cycles. Report one error per SCC (size > 1 or self-loop), optionally displaying the full cycle path.
### Pros:
- Cleaner diagnostics (single error per cycle).
- Can display full cycle paths.
- Detects mutual recursion more explicitly.
### Cons / Considerations:
- Requires separate graph-building pass before full type resolution.
- Must decouple cycle detection from type normalization.
- May increase memory usage (graph edges + stack).
- Handling generic instantiations or nested types adds complexity.
References:
Current DFS cycle detection: `ty_caches.push(symbol_id)` in `resolve_symbol_type`.
Potential SCC implementation: Tarjan’s algorithm over SymbolID graph.
关闭于 2026-05-08 1 条评论