Exponential (?) time complexity in evaluate_trait_predicate_recursively in rustdoc when proving Send/Sync

[Noratrieb]

There is a latent bug in parallel rustdoc that hangs in x.py doc compiler/rustc_driver --stage=1 when parallel_compiler is enabled.

This is currently blocking #104754 and #106745.

[m-ou-se]

From the thread on #106745:

It only happens when rust.parallel-compiler = true is enabled, which explains why it only happens in the -alt builder.

It gets stuck in rustc_trait_selection somehow. Here's a backtrace: backtrace.txt

No clue what is happening.

It looks like this recurses infinitely:

• evaluate_stack
• evaluate_candidate
• evaluate_predicates_recursively
• evaluate_predicate_recursively
• evaluate_trait_predicate_recursively
• evaluate_stack (and repeat)

Opened a Zulip thread about this.

[m-ou-se]

Temporary fix here: #107121

[m-ou-se]

Interestingly, ./x.py doc --stage 0 compiler/rustc_middle also gets stuck. I believe that runs the beta (non-parallel) rustdoc. So that'd mean that rustdoc gets stuck when documenting parallel rustc, not that parallel rustdoc gets stuck when documenting rustc.

[m-ou-se]

Both of the PRs that are blocked by this issue are changes that change the ast.

[m-ou-se]

It seems it's not an infinite loop, but just bad (exponential?) time complexity somewhere. @oli-obk suggested trying out what happens when explicitly implementing Send and Sync for the new ast node, and that indeed 'fixes' the problem in #106745:

#[cfg(parallel_compiler)]
unsafe impl Sync for FormatArgs {}

#[cfg(parallel_compiler)]
unsafe impl Send for FormatArgs {}

So this issue has almost nothing to do with parallel compiler. It occurs in regular non-parallel rustdoc. It's just that with cfg(parallel_compiler), the ast is Send and Sync, and apparently that takes a huge amount of time to prove when documenting rustc_middle.

(Oli is investigating.)

[oli-obk]

Data point: Adding the following snippet to rustc_middle will not stop it from compiling successfully, even though documenting the crate will never stop.

#[cfg(parallel_compiler)]
#[allow(rustc::usage_of_qualified_ty)]
pub fn check_for_send(tcx: ty::TyCtxt<'static>) -> impl Send {
    tcx
}

This makes me think the issue is very much rustdoc related, as it appears to get stuck on proving TyCtxt: Send.

[apiraino]

WG-prioritization assigning priority (Zulip discussion) (note: seems not a regression)

@rustbot label -I-prioritize +P-high

[jyn514]

cc #79103 (comment)

[jyn514]

and #78761 (comment), https://rust-lang.zulipchat.com/#narrow/stream/247081-t-compiler.2Fperformance/topic/rustdoc.20calls.20.60for_each_relevant_impl.60.20a.20lot

[SparrowLii]

#[Edit] I'm trying to solve this problem and what I'm currently observing is that the evaluation_cache does not store all the information when using rustdoc. This causes rustdoc to recalculate many times when collecting auto trait impl and blanket trait impl.

I guess it may be that rustdoc does not calculate the trait implementation on some data structures (such as TyCtxt) in advance, which resulting in too deep recursion

[SparrowLii]

A revealing phenomenon:
The following struct in rustc_const_eval will cause rustdoc to block while proving that tcx is send:

pub struct AllocRef<'a, 'tcx, Prov: Provenance, Extra, Bytes: AllocBytes = Box<[u8]>> {
    alloc: &'a Allocation<Prov, Extra, Bytes>,
    range: AllocRange,
    tcx: TyCtxt<'tcx>,
    alloc_id: AllocId,
}

But when the generics are instantiated, it will not cause blocking:

pub struct AllocRefFake<'a, 'tcx> {
    _alloc: &'a Allocation<AllocId, (), Box<[u8]>>,
    _range: AllocRange,
    _tcx: TyCtxt<'tcx>,
    _alloc_id: AllocId,
}

So I guess it is param_env that causes the values in evaluation_cache to not be reused. Because this cache needs inserting (predictions, param_env).

[jyn514]

@SparrowLii does this happen even with -Znormalize-docs disabled?

rust/src/bootstrap/doc.rs

Line 696 in 0f27161

cargo.rustdocflag("-Znormalize-docs");

rust/src/bootstrap/builder.rs

Line 1148 in d60c64a

cmd.arg("-Znormalize-docs");

[jyn514]

If so, this is probably related to get_auto_trait_impls. This is how we determine the param_env:

rust/src/librustdoc/clean/auto_trait.rs

Line 139 in 0f27161

let param_env = tcx.param_env(item_def_id);

[SparrowLii]

I can't reproduce this issue now, including my local test

Have there been any recent changes?