changed 2 years ago  
Linked with GitHub

I am overflowing with pain

handling non-fatal overflow in the new solver

Previous documents

Constraints when handling non-fatal overflow

  1. the handling of overflow has to be fully sound
  2. the handling of overflow has to avoid query instability
    • this is not necessary in case we definitely emit an error
  3. it should be as forward compatible as possible
  4. hangs should be avoided or at least communicated to the user
  5. it should be as performant as reasonably possible
    • overflow is very rare, especially for existing code as overflow is currently fatal, see this table, the cost of checking for overflow should be minimal
  6. it should not require too much additional design work to enable us to stabilize the new solver
  7. 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. 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.

Select a repo