//! Fallback of infer vars to `!` and `i32`/`f64`.

use intern::sym;
use petgraph::{
    Graph,
    visit::{Dfs, Walker},
};
use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet};
use rustc_type_ir::{
    TyVid,
    inherent::{IntoKind, Ty as _},
};
use tracing::debug;

use crate::{
    infer::InferenceContext,
    next_solver::{CoercePredicate, PredicateKind, SubtypePredicate, Ty, TyKind},
};

#[derive(Copy, Clone)]
pub(crate) enum DivergingFallbackBehavior {
    /// Always fallback to `()` (aka "always spontaneous decay")
    ToUnit,
    /// Sometimes fallback to `!`, but mainly fallback to `()` so that most of the crates are not broken.
    ContextDependent,
    /// Always fallback to `!` (which should be equivalent to never falling back + not making
    /// never-to-any coercions unless necessary)
    ToNever,
}

impl<'db> InferenceContext<'_, 'db> {
    pub(super) fn type_inference_fallback(&mut self) {
        debug!(
            "type-inference-fallback start obligations: {:#?}",
            self.table.fulfillment_cx.pending_obligations()
        );

        // All type checking constraints were added, try to fallback unsolved variables.
        self.table.select_obligations_where_possible();

        debug!(
            "type-inference-fallback post selection obligations: {:#?}",
            self.table.fulfillment_cx.pending_obligations()
        );

        let fallback_occurred = self.fallback_types();

        if !fallback_occurred {
            return;
        }

        // We now see if we can make progress. This might cause us to
        // unify inference variables for opaque types, since we may
        // have unified some other type variables during the first
        // phase of fallback. This means that we only replace
        // inference variables with their underlying opaque types as a
        // last resort.
        //
        // In code like this:
        //
        // ```rust
        // type MyType = impl Copy;
        // fn produce() -> MyType { true }
        // fn bad_produce() -> MyType { panic!() }
        // ```
        //
        // we want to unify the opaque inference variable in `bad_produce`
        // with the diverging fallback for `panic!` (e.g. `()` or `!`).
        // This will produce a nice error message about conflicting concrete
        // types for `MyType`.
        //
        // If we had tried to fallback the opaque inference variable to `MyType`,
        // we will generate a confusing type-check error that does not explicitly
        // refer to opaque types.
        self.table.select_obligations_where_possible();
    }

    fn diverging_fallback_behavior(&self) -> DivergingFallbackBehavior {
        if self.krate().data(self.db).edition.at_least_2024() {
            return DivergingFallbackBehavior::ToNever;
        }

        if self.resolver.def_map().is_unstable_feature_enabled(&sym::never_type_fallback) {
            return DivergingFallbackBehavior::ContextDependent;
        }

        DivergingFallbackBehavior::ToUnit
    }

    fn fallback_types(&mut self) -> bool {
        // Check if we have any unresolved variables. If not, no need for fallback.
        let unresolved_variables = self.table.infer_ctxt.unresolved_variables();

        if unresolved_variables.is_empty() {
            return false;
        }

        let diverging_fallback_behavior = self.diverging_fallback_behavior();

        let diverging_fallback =
            self.calculate_diverging_fallback(&unresolved_variables, diverging_fallback_behavior);

        // We do fallback in two passes, to try to generate
        // better error messages.
        // The first time, we do *not* replace opaque types.
        let mut fallback_occurred = false;
        for ty in unresolved_variables {
            debug!("unsolved_variable = {:?}", ty);
            fallback_occurred |= self.fallback_if_possible(ty, &diverging_fallback);
        }

        fallback_occurred
    }

    // Tries to apply a fallback to `ty` if it is an unsolved variable.
    //
    // - Unconstrained ints are replaced with `i32`.
    //
    // - Unconstrained floats are replaced with `f64`.
    //
    // - Non-numerics may get replaced with `()` or `!`, depending on
    //   how they were categorized by `calculate_diverging_fallback`
    //   (and the setting of `#![feature(never_type_fallback)]`).
    //
    // Fallback becomes very dubious if we have encountered
    // type-checking errors. In that case, fallback to Error.
    //
    // Sets `FnCtxt::fallback_has_occurred` if fallback is performed
    // during this call.
    fn fallback_if_possible(
        &mut self,
        ty: Ty<'db>,
        diverging_fallback: &FxHashMap<Ty<'db>, Ty<'db>>,
    ) -> bool {
        // Careful: we do NOT shallow-resolve `ty`. We know that `ty`
        // is an unsolved variable, and we determine its fallback
        // based solely on how it was created, not what other type
        // variables it may have been unified with since then.
        //
        // The reason this matters is that other attempts at fallback
        // may (in principle) conflict with this fallback, and we wish
        // to generate a type error in that case. (However, this
        // actually isn't true right now, because we're only using the
        // builtin fallback rules. This would be true if we were using
        // user-supplied fallbacks. But it's still useful to write the
        // code to detect bugs.)
        //
        // (Note though that if we have a general type variable `?T`
        // that is then unified with an integer type variable `?I`
        // that ultimately never gets resolved to a special integral
        // type, `?T` is not considered unsolved, but `?I` is. The
        // same is true for float variables.)
        let fallback = match ty.kind() {
            TyKind::Infer(rustc_type_ir::IntVar(_)) => self.types.types.i32,
            TyKind::Infer(rustc_type_ir::FloatVar(_)) => self.types.types.f64,
            _ => match diverging_fallback.get(&ty) {
                Some(&fallback_ty) => fallback_ty,
                None => return false,
            },
        };
        debug!("fallback_if_possible(ty={:?}): defaulting to `{:?}`", ty, fallback);

        _ = self.demand_eqtype_fixme_no_diag(ty, fallback);
        true
    }

    /// The "diverging fallback" system is rather complicated. This is
    /// a result of our need to balance 'do the right thing' with
    /// backwards compatibility.
    ///
    /// "Diverging" type variables are variables created when we
    /// coerce a `!` type into an unbound type variable `?X`. If they
    /// never wind up being constrained, the "right and natural" thing
    /// is that `?X` should "fallback" to `!`. This means that e.g. an
    /// expression like `Some(return)` will ultimately wind up with a
    /// type like `Option<!>` (presuming it is not assigned or
    /// constrained to have some other type).
    ///
    /// However, the fallback used to be `()` (before the `!` type was
    /// added). Moreover, there are cases where the `!` type 'leaks
    /// out' from dead code into type variables that affect live
    /// code. The most common case is something like this:
    ///
    /// ```rust
    /// # fn foo() -> i32 { 4 }
    /// match foo() {
    ///     22 => Default::default(), // call this type `?D`
    ///     _ => return, // return has type `!`
    /// } // call the type of this match `?M`
    /// ```
    ///
    /// Here, coercing the type `!` into `?M` will create a diverging
    /// type variable `?X` where `?X <: ?M`. We also have that `?D <:
    /// ?M`. If `?M` winds up unconstrained, then `?X` will
    /// fallback. If it falls back to `!`, then all the type variables
    /// will wind up equal to `!` -- this includes the type `?D`
    /// (since `!` doesn't implement `Default`, we wind up a "trait
    /// not implemented" error in code like this). But since the
    /// original fallback was `()`, this code used to compile with `?D
    /// = ()`. This is somewhat surprising, since `Default::default()`
    /// on its own would give an error because the types are
    /// insufficiently constrained.
    ///
    /// Our solution to this dilemma is to modify diverging variables
    /// so that they can *either* fallback to `!` (the default) or to
    /// `()` (the backwards compatibility case). We decide which
    /// fallback to use based on whether there is a coercion pattern
    /// like this:
    ///
    /// ```ignore (not-rust)
    /// ?Diverging -> ?V
    /// ?NonDiverging -> ?V
    /// ?V != ?NonDiverging
    /// ```
    ///
    /// Here `?Diverging` represents some diverging type variable and
    /// `?NonDiverging` represents some non-diverging type
    /// variable. `?V` can be any type variable (diverging or not), so
    /// long as it is not equal to `?NonDiverging`.
    ///
    /// Intuitively, what we are looking for is a case where a
    /// "non-diverging" type variable (like `?M` in our example above)
    /// is coerced *into* some variable `?V` that would otherwise
    /// fallback to `!`. In that case, we make `?V` fallback to `!`,
    /// along with anything that would flow into `?V`.
    ///
    /// The algorithm we use:
    /// * Identify all variables that are coerced *into* by a
    ///   diverging variable. Do this by iterating over each
    ///   diverging, unsolved variable and finding all variables
    ///   reachable from there. Call that set `D`.
    /// * Walk over all unsolved, non-diverging variables, and find
    ///   any variable that has an edge into `D`.
    fn calculate_diverging_fallback(
        &self,
        unresolved_variables: &[Ty<'db>],
        behavior: DivergingFallbackBehavior,
    ) -> FxHashMap<Ty<'db>, Ty<'db>> {
        debug!("calculate_diverging_fallback({:?})", unresolved_variables);

        // Construct a coercion graph where an edge `A -> B` indicates
        // a type variable is that is coerced
        let coercion_graph = self.create_coercion_graph();

        // Extract the unsolved type inference variable vids; note that some
        // unsolved variables are integer/float variables and are excluded.
        let unsolved_vids = unresolved_variables.iter().filter_map(|ty| ty.ty_vid());

        // Compute the diverging root vids D -- that is, the root vid of
        // those type variables that (a) are the target of a coercion from
        // a `!` type and (b) have not yet been solved.
        //
        // These variables are the ones that are targets for fallback to
        // either `!` or `()`.
        let diverging_roots: FxHashSet<TyVid> = self
            .table
            .diverging_type_vars
            .iter()
            .map(|&ty| self.shallow_resolve(ty))
            .filter_map(|ty| ty.ty_vid())
            .map(|vid| self.table.infer_ctxt.root_var(vid))
            .collect();
        debug!(
            "calculate_diverging_fallback: diverging_type_vars={:?}",
            self.table.diverging_type_vars
        );
        debug!("calculate_diverging_fallback: diverging_roots={:?}", diverging_roots);

        // Find all type variables that are reachable from a diverging
        // type variable. These will typically default to `!`, unless
        // we find later that they are *also* reachable from some
        // other type variable outside this set.
        let mut roots_reachable_from_diverging = Dfs::empty(&coercion_graph);
        let mut diverging_vids = vec![];
        let mut non_diverging_vids = vec![];
        for unsolved_vid in unsolved_vids {
            let root_vid = self.table.infer_ctxt.root_var(unsolved_vid);
            debug!(
                "calculate_diverging_fallback: unsolved_vid={:?} root_vid={:?} diverges={:?}",
                unsolved_vid,
                root_vid,
                diverging_roots.contains(&root_vid),
            );
            if diverging_roots.contains(&root_vid) {
                diverging_vids.push(unsolved_vid);
                roots_reachable_from_diverging.move_to(root_vid.as_u32().into());

                // drain the iterator to visit all nodes reachable from this node
                while roots_reachable_from_diverging.next(&coercion_graph).is_some() {}
            } else {
                non_diverging_vids.push(unsolved_vid);
            }
        }

        debug!(
            "calculate_diverging_fallback: roots_reachable_from_diverging={:?}",
            roots_reachable_from_diverging,
        );

        // Find all type variables N0 that are not reachable from a
        // diverging variable, and then compute the set reachable from
        // N0, which we call N. These are the *non-diverging* type
        // variables. (Note that this set consists of "root variables".)
        let mut roots_reachable_from_non_diverging = Dfs::empty(&coercion_graph);
        for &non_diverging_vid in &non_diverging_vids {
            let root_vid = self.table.infer_ctxt.root_var(non_diverging_vid);
            if roots_reachable_from_diverging.discovered.contains(root_vid.as_usize()) {
                continue;
            }
            roots_reachable_from_non_diverging.move_to(root_vid.as_u32().into());
            while roots_reachable_from_non_diverging.next(&coercion_graph).is_some() {}
        }
        debug!(
            "calculate_diverging_fallback: roots_reachable_from_non_diverging={:?}",
            roots_reachable_from_non_diverging,
        );

        debug!("obligations: {:#?}", self.table.fulfillment_cx.pending_obligations());

        // For each diverging variable, figure out whether it can
        // reach a member of N. If so, it falls back to `()`. Else
        // `!`.
        let mut diverging_fallback =
            FxHashMap::with_capacity_and_hasher(diverging_vids.len(), FxBuildHasher);

        for &diverging_vid in &diverging_vids {
            let diverging_ty = Ty::new_var(self.interner(), diverging_vid);
            let root_vid = self.table.infer_ctxt.root_var(diverging_vid);
            let can_reach_non_diverging = Dfs::new(&coercion_graph, root_vid.as_u32().into())
                .iter(&coercion_graph)
                .any(|n| roots_reachable_from_non_diverging.discovered.contains(n.index()));

            let mut fallback_to = |ty| {
                diverging_fallback.insert(diverging_ty, ty);
            };

            match behavior {
                DivergingFallbackBehavior::ToUnit => {
                    debug!("fallback to () - legacy: {:?}", diverging_vid);
                    fallback_to(self.types.types.unit);
                }
                DivergingFallbackBehavior::ContextDependent => {
                    // FIXME: rustc does the following, but given this is only relevant when the unstable
                    // `never_type_fallback` feature is active, I chose to not port this.
                    // if found_infer_var_info.self_in_trait && found_infer_var_info.output {
                    //     // This case falls back to () to ensure that the code pattern in
                    //     // tests/ui/never_type/fallback-closure-ret.rs continues to
                    //     // compile when never_type_fallback is enabled.
                    //     //
                    //     // This rule is not readily explainable from first principles,
                    //     // but is rather intended as a patchwork fix to ensure code
                    //     // which compiles before the stabilization of never type
                    //     // fallback continues to work.
                    //     //
                    //     // Typically this pattern is encountered in a function taking a
                    //     // closure as a parameter, where the return type of that closure
                    //     // (checked by `relationship.output`) is expected to implement
                    //     // some trait (checked by `relationship.self_in_trait`). This
                    //     // can come up in non-closure cases too, so we do not limit this
                    //     // rule to specifically `FnOnce`.
                    //     //
                    //     // When the closure's body is something like `panic!()`, the
                    //     // return type would normally be inferred to `!`. However, it
                    //     // needs to fall back to `()` in order to still compile, as the
                    //     // trait is specifically implemented for `()` but not `!`.
                    //     //
                    //     // For details on the requirements for these relationships to be
                    //     // set, see the relationship finding module in
                    //     // compiler/rustc_trait_selection/src/traits/relationships.rs.
                    //     debug!("fallback to () - found trait and projection: {:?}", diverging_vid);
                    //     fallback_to(self.types.types.unit);
                    // }
                    if can_reach_non_diverging {
                        debug!("fallback to () - reached non-diverging: {:?}", diverging_vid);
                        fallback_to(self.types.types.unit);
                    } else {
                        debug!("fallback to ! - all diverging: {:?}", diverging_vid);
                        fallback_to(self.types.types.never);
                    }
                }
                DivergingFallbackBehavior::ToNever => {
                    debug!(
                        "fallback to ! - `rustc_never_type_mode = \"fallback_to_never\")`: {:?}",
                        diverging_vid
                    );
                    fallback_to(self.types.types.never);
                }
            }
        }

        diverging_fallback
    }

    /// Returns a graph whose nodes are (unresolved) inference variables and where
    /// an edge `?A -> ?B` indicates that the variable `?A` is coerced to `?B`.
    fn create_coercion_graph(&self) -> Graph<(), ()> {
        let pending_obligations = self.table.fulfillment_cx.pending_obligations();
        let pending_obligations_len = pending_obligations.len();
        debug!("create_coercion_graph: pending_obligations={:?}", pending_obligations);
        let coercion_edges = pending_obligations
            .into_iter()
            .filter_map(|obligation| {
                // The predicates we are looking for look like `Coerce(?A -> ?B)`.
                // They will have no bound variables.
                obligation.predicate.kind().no_bound_vars()
            })
            .filter_map(|atom| {
                // We consider both subtyping and coercion to imply 'flow' from
                // some position in the code `a` to a different position `b`.
                // This is then used to determine which variables interact with
                // live code, and as such must fall back to `()` to preserve
                // soundness.
                //
                // In practice currently the two ways that this happens is
                // coercion and subtyping.
                let (a, b) = match atom {
                    PredicateKind::Coerce(CoercePredicate { a, b }) => (a, b),
                    PredicateKind::Subtype(SubtypePredicate { a_is_expected: _, a, b }) => (a, b),
                    _ => return None,
                };

                let a_vid = self.root_vid(a)?;
                let b_vid = self.root_vid(b)?;
                Some((a_vid.as_u32(), b_vid.as_u32()))
            });
        let num_ty_vars = self.table.infer_ctxt.num_ty_vars();
        let mut graph = Graph::with_capacity(num_ty_vars, pending_obligations_len);
        for _ in 0..num_ty_vars {
            graph.add_node(());
        }
        graph.extend_with_edges(coercion_edges);
        graph
    }

    /// If `ty` is an unresolved type variable, returns its root vid.
    fn root_vid(&self, ty: Ty<'db>) -> Option<TyVid> {
        Some(self.table.infer_ctxt.root_var(self.shallow_resolve(ty).ty_vid()?))
    }
}