Implement SCC-Based Cycle Detection for Typedefs

[tahadostifam]

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 (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.