# I am overflowing with pain *handling non-fatal overflow in the new solver* ## Previous documents - [vibes while working towards the previous proposed solution](https://hackmd.io/QY0dfEOgSNWwU4oiGnVRLw) - [previous proposed solution](https://hackmd.io/ZsIHG5kSSti_PVyxGVG4xQ) - [vibes and ideas while working on towards this doc](https://hackmd.io/vzthTk4BThWoWrklkC3CWw) ## Constraints when handling non-fatal overflow 1. the handling of overflow has to be fully sound 1. the handling of overflow has to avoid query instability - this is not necessary in case we definitely emit an error 1. it should be as forward compatible as possible 2. hangs should be avoided or at least communicated to the user 3. it should be as performant as reasonably possible - overflow is very rare, especially for existing code as overflow is currently fatal, see [this table](https://hackmd.io/vzthTk4BThWoWrklkC3CWw?view#cache-usage-of-the-new-solver), the cost of checking for overflow should be minimal 4. it should not require too much additional design work to enable us to stabilize the new solver 5. it should not add significant "global" complexity to the solver, the complexity should be as localized as possible ## Background information ### Why do we have to support non-fatal overflow We removed the `match_fresh_trait_refs` hack in the old solver as it is dificult to support this correctly. The existing implementation breaks query stability. Removing this causes overflow in multiple crates, including typenum (https://github.com/rust-lang/trait-system-refactor-initiative/issues/73) and the standard library. ### Completely erasing all constraints on overflow is breaking Doing so would be incredible for performance, however, it would causes a regression: https://github.com/rust-lang/trait-system-refactor-initiative/issues/70 and https://github.com/AzureMarker/shaku ### Erasing constraints on overflow is desirable Returning constrains on overflow can easily cause `try_evaluate_added_goals` to hang. See https://github.com/rust-lang/rust/blob/master/tests/ui/traits/new-solver/cycles/inductive-fixpoint-hang.rs for an explanation of the issue. If we do not erase constraints, the depth at which overflow occured can easily change the response. Because of this [the remaining depth is part of the cache key on overflow](https://github.com/rust-lang/rust/blob/56d25ba5ea3515ba2b361b6c4636373734eb27cc/compiler/rustc_middle/src/traits/solve/cache.rs#L124). This can end up being incredibly costly by rendering the cache to be pretty much useless. In case overflowing goals result in no constraints, we can add an optimization to reuse the cache entry for a goal on future accesses with a lower remaining depth. ## What to do I believe the breakage is limited to `project` in the old solver. We do not eagerly evaluate nested goals when normalizing, allowing an error when equating the normalized alias with the expected term to hide the actual overflow. While we could return constraints in more cases, this would not significantly improve the expressiveness of the trait solver while negatively affecting perf. By only applying the constraints from overflow when normalizing, i.e. the current goal is `NormalizesTo`, while always ignoring constraints from nested where clauses, we should closely match the behavior of the old solver.