alias_relate.rs

//! Implements the `AliasRelate` goal, which is used when unifying aliases.
//! Doing this via a separate goal is called "deferred alias relation" and part
//! of our more general approach to "lazy normalization".
//!
//! This goal, e.g. `A alias-relate B`, may be satisfied by one of three branches:
//! * normalizes-to: If `A` is a projection, we can prove the equivalent
//!   projection predicate with B as the right-hand side of the projection.
//!   This goal is computed in both directions, if both are aliases.
//! * subst-relate: Equate `A` and `B` by their substs, if they're both
//!   aliases with the same def-id.
//! * bidirectional-normalizes-to: If `A` and `B` are both projections, and both
//!   may apply, then we can compute the "intersection" of both normalizes-to by
//!   performing them together. This is used specifically to resolve ambiguities.
use super::{EvalCtxt, SolverMode};
use rustc_infer::traits::query::NoSolution;
use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
use rustc_middle::ty;

/// We may need to invert the alias relation direction if dealing an alias on the RHS.
#[derive(Debug)]
enum Invert {
    No,
    Yes,
}

impl<'tcx> EvalCtxt<'_, 'tcx> {
    #[instrument(level = "debug", skip(self), ret)]
    pub(super) fn compute_alias_relate_goal(
        &mut self,
        goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>, ty::AliasRelationDirection)>,
    ) -> QueryResult<'tcx> {
        let tcx = self.tcx();
        let Goal { param_env, predicate: (lhs, rhs, direction) } = goal;
        if lhs.is_infer() || rhs.is_infer() {
            bug!(
                "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated"
            );
        }

        match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) {
            (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"),

            // RHS is not a projection, only way this is true is if LHS normalizes-to RHS
            (Some(alias_lhs), None) => self.assemble_normalizes_to_candidate(
                param_env,
                alias_lhs,
                rhs,
                direction,
                Invert::No,
            ),

            // LHS is not a projection, only way this is true is if RHS normalizes-to LHS
            (None, Some(alias_rhs)) => self.assemble_normalizes_to_candidate(
                param_env,
                alias_rhs,
                lhs,
                direction,
                Invert::Yes,
            ),

            (Some(alias_lhs), Some(alias_rhs)) => {
                debug!("both sides are aliases");

                let mut candidates = Vec::new();
                // LHS normalizes-to RHS
                candidates.extend(self.assemble_normalizes_to_candidate(
                    param_env,
                    alias_lhs,
                    rhs,
                    direction,
                    Invert::No,
                ));
                // RHS normalizes-to RHS
                candidates.extend(self.assemble_normalizes_to_candidate(
                    param_env,
                    alias_rhs,
                    lhs,
                    direction,
                    Invert::Yes,
                ));
                // Relate via args
                candidates.extend(
                    self.assemble_subst_relate_candidate(
                        param_env, alias_lhs, alias_rhs, direction,
                    ),
                );
                debug!(?candidates);

                if let Some(merged) = self.try_merge_responses(&candidates) {
                    Ok(merged)
                } else {
                    // When relating two aliases and we have ambiguity, if both
                    // aliases can be normalized to something, we prefer
                    // "bidirectionally normalizing" both of them within the same
                    // candidate.
                    //
                    // See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/25>.
                    //
                    // As this is incomplete, we must not do so during coherence.
                    match self.solver_mode() {
                        SolverMode::Normal => {
                            if let Ok(bidirectional_normalizes_to_response) = self
                                .assemble_bidirectional_normalizes_to_candidate(
                                    param_env, lhs, rhs, direction,
                                )
                            {
                                Ok(bidirectional_normalizes_to_response)
                            } else {
                                self.flounder(&candidates)
                            }
                        }
                        SolverMode::Coherence => self.flounder(&candidates),
                    }
                }
            }
        }
    }

    #[instrument(level = "debug", skip(self), ret)]
    fn assemble_normalizes_to_candidate(
        &mut self,
        param_env: ty::ParamEnv<'tcx>,
        alias: ty::AliasTy<'tcx>,
        other: ty::Term<'tcx>,
        direction: ty::AliasRelationDirection,
        invert: Invert,
    ) -> QueryResult<'tcx> {
        self.probe_misc_candidate("normalizes-to").enter(|ecx| {
            ecx.normalizes_to_inner(param_env, alias, other, direction, invert)?;
            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
        })
    }

    // Computes the normalizes-to branch, with side-effects. This must be performed
    // in a probe in order to not taint the evaluation context.
    fn normalizes_to_inner(
        &mut self,
        param_env: ty::ParamEnv<'tcx>,
        alias: ty::AliasTy<'tcx>,
        other: ty::Term<'tcx>,
        direction: ty::AliasRelationDirection,
        invert: Invert,
    ) -> Result<(), NoSolution> {
        let other = match direction {
            // This is purely an optimization. No need to instantiate a new
            // infer var and equate the RHS to it.
            ty::AliasRelationDirection::Equate => other,

            // Instantiate an infer var and subtype our RHS to it, so that we
            // properly represent a subtype relation between the LHS and RHS
            // of the goal.
            ty::AliasRelationDirection::Subtype => {
                let fresh = self.next_term_infer_of_kind(other);
                let (sub, sup) = match invert {
                    Invert::No => (fresh, other),
                    Invert::Yes => (other, fresh),
                };
                self.sub(param_env, sub, sup)?;
                fresh
            }
        };
        self.add_goal(Goal::new(
            self.tcx(),
            param_env,
            ty::ProjectionPredicate { projection_ty: alias, term: other },
        ));

        Ok(())
    }

    fn assemble_subst_relate_candidate(
        &mut self,
        param_env: ty::ParamEnv<'tcx>,
        alias_lhs: ty::AliasTy<'tcx>,
        alias_rhs: ty::AliasTy<'tcx>,
        direction: ty::AliasRelationDirection,
    ) -> QueryResult<'tcx> {
        self.probe_misc_candidate("args relate").enter(|ecx| {
            match direction {
                ty::AliasRelationDirection::Equate => {
                    ecx.eq(param_env, alias_lhs, alias_rhs)?;
                }
                ty::AliasRelationDirection::Subtype => {
                    ecx.sub(param_env, alias_lhs, alias_rhs)?;
                }
            }

            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
        })
    }

    fn assemble_bidirectional_normalizes_to_candidate(
        &mut self,
        param_env: ty::ParamEnv<'tcx>,
        lhs: ty::Term<'tcx>,
        rhs: ty::Term<'tcx>,
        direction: ty::AliasRelationDirection,
    ) -> QueryResult<'tcx> {
        self.probe_misc_candidate("bidir normalizes-to").enter(|ecx| {
            ecx.normalizes_to_inner(
                param_env,
                lhs.to_alias_ty(ecx.tcx()).unwrap(),
                rhs,
                direction,
                Invert::No,
            )?;
            ecx.normalizes_to_inner(
                param_env,
                rhs.to_alias_ty(ecx.tcx()).unwrap(),
                lhs,
                direction,
                Invert::Yes,
            )?;
            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
        })
    }
}