Detailed Changes and Quirks in the New Trait Solver Implementation

By using canonicalization, the new implementation is able to merge *evaluation* and *fulfillment*, avoiding complexity and subtle differences in behavior. It greatly simplifies caching and prevents accidentally relying on untracked information. It allows us to avoid reevaluating candidates after selection and enables us to merge the responses of multiple candidates. However, canonicalizing goals during evaluation forces the new implementation to use a fixpoint algorithm when encountering cycles during trait solving: [source][cycle-fixpoint]. ### Deferred alias equality The new implementation emits `AliasRelate` goals when relating aliases while the old implementation structurally relates the aliases instead. This enables the new solver to stall equality until it is able to normalize the related aliases. The behavior of the old solver is incomplete and relies on eager normalization which replaces ambiguous aliases with inference variables. As this is not possible for aliases containing bound variables, the old implementation does not handle aliases inside of binders correctly, e.g. [#102048]. See the chapter on [normalization] for more details. ### Eagerly evaluating nested goals The new implementation eagerly handles nested goals instead of returning them to the caller. The old implementation does both. In evaluation nested goals [are eagerly handled][eval-nested], while fulfillment simply [returns them for later processing][fulfill-nested]. As the new implementation has to be able to eagerly handle nested goals for candidate selection, always doing so reduces complexity. It may also enable us to merge more candidates in the future. ### Nested goals are evaluated until reaching a fixpoint The new implementation always evaluates goals in a loop until reaching a fixpoint. The old implementation only does so in *fulfillment*, but not in *evaluation*. Always doing so strengthens inference and is reduces the order dependence of the trait solver. See [trait-system-refactor-initiative#102]. ### Proof trees and providing diagnostics information The new implementation does not track diagnostics information directly, instead providing [proof trees][trees] which are used to lazily compute the relevant information. This is not yet fully fleshed out and somewhat hacky. The goal is to avoid tracking this information in the happy path to improve performance and to avoid accidentally relying on diagnostics data for behavior. ## Major quirks of the new implementation ### Hiding impls if there are any env candidates If there is at least one `ParamEnv` or `AliasBound` candidate to prove some `Trait` goal, we discard all impl candidates for both `Trait` and `Projection` goals: [source][discard-from-env]. This prevents users from using an impl which is entirely covered by a `where`-bound, matching the behavior of the old implementation and avoiding some weird errors, e.g. [trait-system-refactor-initiative#76]. ### `NormalizesTo` goals are a function See the [normalization] chapter. We replace the expected term with an unconstrained inference variable before computing `NormalizesTo` goals to prevent it from affecting normalization. This means that `NormalizesTo` goals are handled somewhat differently from all other goal kinds and need some additional solver support. Most notably, their ambiguous nested goals are returned to the caller which then evaluates them. See [#122687] for more details.

This section elaborates on specific changes in the new trait solver, including deferred alias equality, eager evaluation of nested goals until a fixpoint is reached, and the use of proof trees for diagnostics. It also details quirks like hiding impls when environment candidates exist and treating `NormalizesTo` goals as a function, which necessitates special handling and returns ambiguous nested goals to the caller.