Proposal Details
(This is more of a "suggestion" or "request for comments" than a proposal.)
The current check for unbounded recursive instantiation in src/cmd/compile/internal/types2/mono.go uses an O(n^2) algorithm based on Bellman-Ford to find positive-weight cycles in a directed graph. There is a simple O(n) algorithm based on strongly-connected components (SCCs). Are you interested in switching to this algorithm?
Here is a contrived example that triggers the O(n^2) behaviour:
package main
func main() {}
type Unbounded[T any] struct{ x *Unbounded[Unbounded[T]] }
type S1[T any] struct{ s *S1[T] }
type S2[T any] struct{ s *S2[T] }
...
type S100000[T any] struct{ s *S100000[T] }The repetitive part can be generated in bash using
for ((i=1;i<=100000;i++)); do echo "type S$i[T any] struct{ s *S$i[T] }"; doneWith go1.26.3, it takes 30 seconds for the compiler to report the error. Obviously it's contrived. It looks like the precise worst-case time complexity is O(V*E) where V = total number of type parameters and E = total number of type arguments (roughly)* in the current package (across all generic type/function/method declarations); so I think the likelihood of this affecting people is fairly low, but the fast algorithm is pretty simple.
The idea is to use Tarjan's algorithm or similar to identify SCCs in O(n), and then for each positive-weight edge A-->B check whether A and B belong to the same SCC; if so, that edge is part of a positive-weight cycle.
(This algorithm can be further improved by doing these checks during the execution of Tarjan's algorithm, since after Tarjan's algorithm processes an edge we can tell whether or not that edge is part of an SCC. Some further modifications allow reconstructing the cycle containing the edge.)
*More precisely, it looks like E is the number of references to type parameters that occur in type arguments of instantiations of types/functions/methods defined in the current package.
Proposal Details
(This is more of a "suggestion" or "request for comments" than a proposal.)
The current check for unbounded recursive instantiation in src/cmd/compile/internal/types2/mono.go uses an O(n^2) algorithm based on Bellman-Ford to find positive-weight cycles in a directed graph. There is a simple O(n) algorithm based on strongly-connected components (SCCs). Are you interested in switching to this algorithm?
Here is a contrived example that triggers the O(n^2) behaviour:
The repetitive part can be generated in bash using
With go1.26.3, it takes 30 seconds for the compiler to report the error. Obviously it's contrived. It looks like the precise worst-case time complexity is O(V*E) where V = total number of type parameters and E = total number of type arguments (roughly)* in the current package (across all generic type/function/method declarations); so I think the likelihood of this affecting people is fairly low, but the fast algorithm is pretty simple.
The idea is to use Tarjan's algorithm or similar to identify SCCs in O(n), and then for each positive-weight edge A-->B check whether A and B belong to the same SCC; if so, that edge is part of a positive-weight cycle.
(This algorithm can be further improved by doing these checks during the execution of Tarjan's algorithm, since after Tarjan's algorithm processes an edge we can tell whether or not that edge is part of an SCC. Some further modifications allow reconstructing the cycle containing the edge.)
*More precisely, it looks like E is the number of references to type parameters that occur in type arguments of instantiations of types/functions/methods defined in the current package.