Description
Match type reduction can loop. We currently handle that by catching stack-overflows and deciding in that case that a match does not reduce. This is problematic, since catching SOs is somewhat undefined behavior on JVMs. It's not guaranteed that we we don't get follow-on exceptions, and we might also get large slow-downs in general after an SO is caught.
It would be better to do implement divergence checking without running into stack-overflows or limiting recursion depth by some arbitrary number. Scala 3 does have a state of the art divergence check for implicit search. See the chapter in the language spec and search for "open implicit types". This algorithm should in principle also be usable for match types, after some adaptation.
The goal of the project is to implement a divergence check for match types that follows the divergence check for implicit resolution. To do this you need to
- understand the algorithm
- read the code of the Dotty compiler dealing with the implementation
- work out what adaptations are needed for match type reduction
- implement the checks in the match type checker
This requires some good knowledge of compilers and the Scala compiler in general. The project is suitable for an advanced master project or a master thesis.