What algorithm is used to detect infinite sized structs? I'm working on a tool that generates Rust code and need to detect such cases so I can add a level of indirection.
I realize that this is simple enough for code without generics, but adding them makes this more complicated and I would like to align my checks more closely with the compiler.
The obvious way to do it is cycle detection in a graph, where vertices are types and edges are "contains" relationships. There are many algorithms for cycle detection, but the naïve one (BFS or DFS-based with a set) is probably good enough for all intents and purposes. I don't know whether that's exactly how Rustc does it.
You can delay cycle detection until every type is concretized.
Sadly, I do have type parameters in my language so I'll need to make the check happen even for arbitrary type parameters. That said, now I'm thinking if I treat type parameters as a concrete type, I can probably get something to work.
Heads-up that Rust doesn't permit infinitely long types in addition to infinitely large ADTs.
That doesn't surprise me. I plan to put together some test cases with some of these pathological cases.
What I'm saying is you can perform the check after instantiation of generics, once type parameters are substituted with concrete types. I'm not suggesting you to get rid of generics in your language.
The classic way to remove cycles from a graph is to compute the feedback arc set and remove it.
petgraph contains a generic implementation of this
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.