ITADN

Implement SCC-Based Cycle Detection for Typedefs

#308Closedtahadostifam 创建于 2026-01-23
T
tahadostifamcommented
# 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 条评论