You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Experiment with backtracking in the new solver #15908
Depend on #15906. This is a follow-up for series started by #15287
Currently when getting both upper and lower bounds for a type variable we randomly choose the lower one. This is not always the best choice and can lead to inference failures. A possible example is:
S <: List[float], S <: List[T], T <: float, T :> int
They split into two SCCs each containing one variable {T} and {S}, and the second depends on first one. So we would first solve T = int and then we will get updated constraints for S: S <: List[float], S <: List[int], with the only solution S = <nothing>. At the same time T = float, S = List[float] is a totally valid solution. We could get it by backtracking when we get <nothing> and trying different bound(s) in the previous SCC.
One possible problem I see is that this backtracking is exponential in worst case of inference failure (e.g. due to actual user error). Another problem is that backtracking can make implementation much less readable.
I would only start looking at this after we have real-world examples where backtracking would help -- or more generally, once we have a better understanding of the biggest remaining limitations of the new type inference algorithm. Otherwise we might be introducing unnecessary complexity.
Activity
JukkaL commentedon Aug 24, 2023
I would only start looking at this after we have real-world examples where backtracking would help -- or more generally, once we have a better understanding of the biggest remaining limitations of the new type inference algorithm. Otherwise we might be introducing unnecessary complexity.