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::queries::TaggedQueryKey;
use rustc_middle::query::QueryCycle;
use rustc_middle::ty::{self, Ty, TyCtxt};
use rustc_span::def_id::{DefId, LocalDefId};
use rustc_span::{DUMMY_SP, ErrorGuaranteed, Span, bug};

// Default cycle handler used for all queries that don't use the `handle_cycle_error` query
// modifier.
pub(crate) fn default(err: Diag<'_>) -> ! {
    let guar = err.emit_err();
    guar.raise_fatal()
}

pub(crate) fn fn_sig<'tcx>(
    tcx: TyCtxt<'tcx>,
    def_id: DefId,
    _: QueryCycle<'tcx>,
    err: Diag<'_>,
) -> ty::EarlyBinder<'tcx, ty::PolyFnSig<'tcx>> {
    let guar = err.delay_as_bug();

    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(
        tcx,
        ty::Binder::dummy(tcx.mk_fn_sig_safe_rust_abi(std::iter::repeat_n(err, arity), err)),
    )
}

pub(crate) fn check_representability<'tcx>(
    tcx: TyCtxt<'tcx>,
    _key: LocalDefId,
    cycle: QueryCycle<'tcx>,
    _err: Diag<'_>,
) {
    check_representability_inner(tcx, cycle);
}

pub(crate) fn check_representability_adt_ty<'tcx>(
    tcx: TyCtxt<'tcx>,
    _key: Ty<'tcx>,
    cycle: QueryCycle<'tcx>,
    _err: Diag<'_>,
) {
    check_representability_inner(tcx, cycle);
}

fn check_representability_inner<'tcx>(tcx: TyCtxt<'tcx>, cycle: QueryCycle<'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()
}

pub(crate) fn variances_of<'tcx>(
    tcx: TyCtxt<'tcx>,
    def_id: DefId,
    _cycle: QueryCycle<'tcx>,
    err: Diag<'_>,
) -> &'tcx [ty::Variance] {
    let _guar = err.delay_as_bug();
    let n = tcx.generics_of(def_id).count();
    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()
}

pub(crate) fn layout_of<'tcx>(
    tcx: TyCtxt<'tcx>,
    _key: ty::PseudoCanonicalInput<'tcx, Ty<'tcx>>,
    cycle: QueryCycle<'tcx>,
    err: Diag<'_>,
) -> Result<ty::layout::TyAndLayout<'tcx>, &'tcx ty::layout::LayoutError<'tcx>> {
    let _guar = err.delay_as_bug();
    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, false),
    );

    diag.emit_err().raise_fatal()
}

// 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_err()
}

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))
        }
        _ => {}
    }
}

#[inline(never)]
#[cold]
pub(crate) fn create_cycle_error<'tcx>(
    tcx: TyCtxt<'tcx>,
    QueryCycle { usage, frames }: &QueryCycle<'tcx>,
    nested: bool,
) -> Diag<'tcx> {
    assert!(!frames.is_empty());

    let span = frames[0].tagged_key.catch_default_span(tcx, frames[1 % frames.len()].span);

    let mut cycle_stack = Vec::new();

    use crate::diagnostics::StackCount;
    let stack_bottom = frames[0].tagged_key.catch_description(tcx);
    let stack_count = if frames.len() == 1 {
        StackCount::Single { stack_bottom: stack_bottom.clone() }
    } else {
        StackCount::Multiple { stack_bottom: stack_bottom.clone() }
    };

    let mut prev = span;
    for i in 1..frames.len() {
        let frame = &frames[i];
        let span = frame.tagged_key.catch_default_span(tcx, frames[(i + 1) % frames.len()].span);
        cycle_stack.push(crate::diagnostics::CycleStack {
            span: if span == prev { DUMMY_SP } else { span },
            desc: frame.tagged_key.catch_description(tcx),
        });
        prev = span;
    }

    let cycle_usage = usage.as_ref().map(|usage| {
        let cycle_span = usage.tagged_key.catch_default_span(tcx, usage.span);
        crate::diagnostics::CycleUsage {
            span: if cycle_span != span { cycle_span } else { DUMMY_SP },
            usage: usage.tagged_key.catch_description(tcx),
        }
    });

    let is_all_def_kind = |def_kind| {
        // Trivial type alias and trait alias cycles consists of `type_of` and
        // `explicit_implied_clauses_of` queries, so we just check just these here.
        frames.iter().all(|frame| match frame.tagged_key {
            TaggedQueryKey::type_of(def_id)
            | TaggedQueryKey::explicit_implied_clauses_of(def_id)
                if tcx.def_kind(def_id) == def_kind =>
            {
                true
            }
            _ => false,
        })
    };

    let alias = if !nested {
        if is_all_def_kind(DefKind::TyAlias) {
            Some(crate::diagnostics::Alias::Ty)
        } else if is_all_def_kind(DefKind::TraitAlias) {
            Some(crate::diagnostics::Alias::Trait)
        } else {
            None
        }
    } else {
        None
    };

    if nested {
        tcx.sess.dcx().create_err(crate::diagnostics::NestedCycle {
            span,
            cycle_stack,
            stack_bottom: crate::diagnostics::NestedCycleBottom { stack_bottom },
            cycle_usage,
            stack_count,
            note_span: (),
        })
    } else {
        tcx.sess.dcx().create_err(crate::diagnostics::Cycle {
            span,
            cycle_stack,
            stack_bottom,
            alias,
            cycle_usage,
            stack_count,
            note_span: (),
        })
    }
}