compiler/rustc_query_impl/src/handle_cycle_error.rs

use std::collections::VecDeque;
use std::fmt::Write;
use std::iter;
use std::ops::ControlFlow;

use rustc_data_structures::fx::FxHashSet;
use rustc_errors::codes::*;
use rustc_errors::{Applicability, Diag, MultiSpan, pluralize, struct_span_code_err};
use rustc_hir as hir;
use rustc_hir::def::{DefKind, Res};
use rustc_middle::bug;
use rustc_middle::queries::{QueryVTables, TaggedQueryKey};
use rustc_middle::query::Cycle;
use rustc_middle::query::erase::erase_val;
use rustc_middle::ty::layout::LayoutError;
use rustc_middle::ty::{self, Ty, TyCtxt};
use rustc_span::def_id::{DefId, LocalDefId};
use rustc_span::{ErrorGuaranteed, Span};

use crate::job::create_cycle_error;

pub(crate) fn specialize_query_vtables<'tcx>(vtables: &mut QueryVTables<'tcx>) {
    vtables.fn_sig.handle_cycle_error_fn = |tcx, key, _, err| {
        let guar = err.delay_as_bug();
        erase_val(fn_sig(tcx, key, guar))
    };

    vtables.check_representability.handle_cycle_error_fn =
        |tcx, _, cycle, _err| check_representability(tcx, cycle);

    vtables.check_representability_adt_ty.handle_cycle_error_fn =
        |tcx, _, cycle, _err| check_representability(tcx, cycle);

    vtables.variances_of.handle_cycle_error_fn = |tcx, key, _, err| {
        let _guar = err.delay_as_bug();
        erase_val(variances_of(tcx, key))
    };

    vtables.layout_of.handle_cycle_error_fn = |tcx, _, cycle, err| {
        let _guar = err.delay_as_bug();
        erase_val(Err(layout_of(tcx, cycle)))
    }
}

pub(crate) fn default(err: Diag<'_>) -> ! {
    let guar = err.emit();
    guar.raise_fatal()
}

fn fn_sig<'tcx>(
    tcx: TyCtxt<'tcx>,
    def_id: DefId,
    guar: ErrorGuaranteed,
) -> ty::EarlyBinder<'tcx, ty::PolyFnSig<'tcx>> {
    let err = Ty::new_error(tcx, guar);

    let arity = if let Some(node) = tcx.hir_get_if_local(def_id)
        && let Some(sig) = node.fn_sig()
    {
        sig.decl.inputs.len()
    } else {
        tcx.dcx().abort_if_errors();
        unreachable!()
    };

    ty::EarlyBinder::bind(ty::Binder::dummy(tcx.mk_fn_sig(
        std::iter::repeat_n(err, arity),
        err,
        false,
        rustc_hir::Safety::Safe,
        rustc_abi::ExternAbi::Rust,
    )))
}

fn check_representability<'tcx>(tcx: TyCtxt<'tcx>, cycle: Cycle<'tcx>) -> ! {
    let mut item_and_field_ids = Vec::new();
    let mut representable_ids = FxHashSet::default();
    for frame in &cycle.frames {
        if let TaggedQueryKey::check_representability(def_id) = frame.tagged_key
            && tcx.def_kind(def_id) == DefKind::Field
        {
            let field_id: LocalDefId = def_id;
            let parent_id = tcx.parent(field_id.to_def_id());
            let item_id = match tcx.def_kind(parent_id) {
                DefKind::Variant => tcx.parent(parent_id),
                _ => parent_id,
            };
            item_and_field_ids.push((item_id.expect_local(), field_id));
        }
    }
    for frame in &cycle.frames {
        if let TaggedQueryKey::check_representability_adt_ty(key) = frame.tagged_key
            && let Some(adt) = key.ty_adt_def()
            && let Some(def_id) = adt.did().as_local()
            && !item_and_field_ids.iter().any(|&(id, _)| id == def_id)
        {
            representable_ids.insert(def_id);
        }
    }
    // We used to continue here, but the cycle error printed next is actually less useful than
    // the error produced by `recursive_type_error`.
    let guar = recursive_type_error(tcx, item_and_field_ids, &representable_ids);
    guar.raise_fatal()
}

fn variances_of<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> &'tcx [ty::Variance] {
    let n = tcx.generics_of(def_id).own_params.len();
    tcx.arena.alloc_from_iter(iter::repeat_n(ty::Bivariant, n))
}

// Take a cycle of `Q` and try `try_cycle` on every permutation, falling back to `otherwise`.
fn search_for_cycle_permutation<Q, T>(
    cycle: &[Q],
    try_cycle: impl Fn(&mut VecDeque<&Q>) -> ControlFlow<T, ()>,
    otherwise: impl FnOnce() -> T,
) -> T {
    let mut cycle: VecDeque<_> = cycle.iter().collect();
    for _ in 0..cycle.len() {
        match try_cycle(&mut cycle) {
            ControlFlow::Continue(_) => {
                cycle.rotate_left(1);
            }
            ControlFlow::Break(t) => return t,
        }
    }

    otherwise()
}

fn layout_of<'tcx>(tcx: TyCtxt<'tcx>, cycle: Cycle<'tcx>) -> &'tcx ty::layout::LayoutError<'tcx> {
    let diag = search_for_cycle_permutation(
        &cycle.frames,
        |frames| {
            if let TaggedQueryKey::layout_of(key) = frames[0].tagged_key
                && let ty::Coroutine(def_id, _) = key.value.kind()
                && let Some(def_id) = def_id.as_local()
                && let def_kind = tcx.def_kind(def_id)
                && matches!(def_kind, DefKind::Closure)
                && let Some(coroutine_kind) = tcx.coroutine_kind(def_id)
            {
                // FIXME: `def_span` for an fn-like coroutine will point to the fn's body
                // due to interactions between the desugaring into a closure expr and the
                // def_span code. I'm not motivated to fix it, because I tried and it was
                // not working, so just hack around it by grabbing the parent fn's span.
                let span = if coroutine_kind.is_fn_like() {
                    tcx.def_span(tcx.local_parent(def_id))
                } else {
                    tcx.def_span(def_id)
                };
                let mut diag = struct_span_code_err!(
                    tcx.sess.dcx(),
                    span,
                    E0733,
                    "recursion in {} {} requires boxing",
                    tcx.def_kind_descr_article(def_kind, def_id.to_def_id()),
                    tcx.def_kind_descr(def_kind, def_id.to_def_id()),
                );
                for (i, frame) in frames.iter().enumerate() {
                    let TaggedQueryKey::layout_of(frame_key) = frame.tagged_key else {
                        continue;
                    };
                    let &ty::Coroutine(frame_def_id, _) = frame_key.value.kind() else {
                        continue;
                    };
                    let Some(frame_coroutine_kind) = tcx.coroutine_kind(frame_def_id) else {
                        continue;
                    };
                    let frame_span =
                        frame.tagged_key.default_span(tcx, frames[(i + 1) % frames.len()].span);
                    if frame_span.is_dummy() {
                        continue;
                    }
                    if i == 0 {
                        diag.span_label(frame_span, "recursive call here");
                    } else {
                        let coroutine_span: Span = if frame_coroutine_kind.is_fn_like() {
                            tcx.def_span(tcx.parent(frame_def_id))
                        } else {
                            tcx.def_span(frame_def_id)
                        };
                        let mut multispan = MultiSpan::from_span(coroutine_span);
                        multispan.push_span_label(frame_span, "...leading to this recursive call");
                        diag.span_note(
                            multispan,
                            format!("which leads to this {}", tcx.def_descr(frame_def_id)),
                        );
                    }
                }
                // FIXME: We could report a structured suggestion if we had
                // enough info here... Maybe we can use a hacky HIR walker.
                if matches!(
                    coroutine_kind,
                    hir::CoroutineKind::Desugared(hir::CoroutineDesugaring::Async, _)
                ) {
                    diag.note("a recursive `async fn` call must introduce indirection such as `Box::pin` to avoid an infinitely sized future");
                }

                ControlFlow::Break(diag)
            } else {
                ControlFlow::Continue(())
            }
        },
        || create_cycle_error(tcx, &cycle),
    );

    let guar = diag.emit();
    tcx.arena.alloc(LayoutError::Cycle(guar))
}

// item_and_field_ids should form a cycle where each field contains the
// type in the next element in the list
fn recursive_type_error(
    tcx: TyCtxt<'_>,
    mut item_and_field_ids: Vec<(LocalDefId, LocalDefId)>,
    representable_ids: &FxHashSet<LocalDefId>,
) -> ErrorGuaranteed {
    const ITEM_LIMIT: usize = 5;

    // Rotate the cycle so that the item with the lowest span is first
    let start_index = item_and_field_ids
        .iter()
        .enumerate()
        .min_by_key(|&(_, &(id, _))| tcx.def_span(id))
        .unwrap()
        .0;
    item_and_field_ids.rotate_left(start_index);

    let cycle_len = item_and_field_ids.len();
    let show_cycle_len = cycle_len.min(ITEM_LIMIT);

    let mut err_span = MultiSpan::from_spans(
        item_and_field_ids[..show_cycle_len]
            .iter()
            .map(|(id, _)| tcx.def_span(id.to_def_id()))
            .collect(),
    );
    let mut suggestion = Vec::with_capacity(show_cycle_len * 2);
    for i in 0..show_cycle_len {
        let (_, field_id) = item_and_field_ids[i];
        let (next_item_id, _) = item_and_field_ids[(i + 1) % cycle_len];
        // Find the span(s) that contain the next item in the cycle
        let hir::Node::Field(field) = tcx.hir_node_by_def_id(field_id) else {
            bug!("expected field")
        };
        let mut found = Vec::new();
        find_item_ty_spans(tcx, field.ty, next_item_id, &mut found, representable_ids);

        // Couldn't find the type. Maybe it's behind a type alias?
        // In any case, we'll just suggest boxing the whole field.
        if found.is_empty() {
            found.push(field.ty.span);
        }

        for span in found {
            err_span.push_span_label(span, "recursive without indirection");
            // FIXME(compiler-errors): This suggestion might be erroneous if Box is shadowed
            suggestion.push((span.shrink_to_lo(), "Box<".to_string()));
            suggestion.push((span.shrink_to_hi(), ">".to_string()));
        }
    }
    let items_list = {
        let mut s = String::new();
        for (i, &(item_id, _)) in item_and_field_ids.iter().enumerate() {
            let path = tcx.def_path_str(item_id);
            write!(&mut s, "`{path}`").unwrap();
            if i == (ITEM_LIMIT - 1) && cycle_len > ITEM_LIMIT {
                write!(&mut s, " and {} more", cycle_len - 5).unwrap();
                break;
            }
            if cycle_len > 1 && i < cycle_len - 2 {
                s.push_str(", ");
            } else if cycle_len > 1 && i == cycle_len - 2 {
                s.push_str(" and ")
            }
        }
        s
    };
    struct_span_code_err!(
        tcx.dcx(),
        err_span,
        E0072,
        "recursive type{} {} {} infinite size",
        pluralize!(cycle_len),
        items_list,
        pluralize!("has", cycle_len),
    )
    .with_multipart_suggestion(
        "insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle",
        suggestion,
        Applicability::HasPlaceholders,
    )
    .emit()
}

fn find_item_ty_spans(
    tcx: TyCtxt<'_>,
    ty: &hir::Ty<'_>,
    needle: LocalDefId,
    spans: &mut Vec<Span>,
    seen_representable: &FxHashSet<LocalDefId>,
) {
    match ty.kind {
        hir::TyKind::Path(hir::QPath::Resolved(_, path)) => {
            if let Res::Def(kind, def_id) = path.res
                && matches!(kind, DefKind::Enum | DefKind::Struct | DefKind::Union)
            {
                let check_params = def_id.as_local().is_none_or(|def_id| {
                    if def_id == needle {
                        spans.push(ty.span);
                    }
                    seen_representable.contains(&def_id)
                });
                if check_params && let Some(args) = path.segments.last().unwrap().args {
                    let params_in_repr = tcx.params_in_repr(def_id);
                    // the domain size check is needed because the HIR may not be well-formed at this point
                    for (i, arg) in args.args.iter().enumerate().take(params_in_repr.domain_size())
                    {
                        if let hir::GenericArg::Type(ty) = arg
                            && params_in_repr.contains(i as u32)
                        {
                            find_item_ty_spans(
                                tcx,
                                ty.as_unambig_ty(),
                                needle,
                                spans,
                                seen_representable,
                            );
                        }
                    }
                }
            }
        }
        hir::TyKind::Array(ty, _) => find_item_ty_spans(tcx, ty, needle, spans, seen_representable),
        hir::TyKind::Tup(tys) => {
            tys.iter().for_each(|ty| find_item_ty_spans(tcx, ty, needle, spans, seen_representable))
        }
        _ => {}
    }
}