Trait evaluation cache interacts badly with incremental compilation

[Aaron1011]

PR #83220 solved one issue with the trait evaluation cache, but I've found another one.

On the perf server, syn is currently causing the following ICE:

Compiling syn v0.11.11 (/tmp/.tmpnHQAja) ...

thread 'rustc' panicked at 'found unstable fingerprints for evaluate_obligation(e3352ed64d6e2ccd-c82ee1c6b3ce2c20): Ok(EvaluatedToOk)', /rustc/b8719c51e0e44483cff9b6975a830f6e51812a48/compiler/rustc_query_system/src/query/plumbing.rs:593:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.53.0-nightly (b8719c51e 2021-03-26) running on x86_64-unknown-linux-gnu

note: compiler flags: -Z self-profile=/tmp/.tmpnHQAja/self-profile-output -C opt-level=3 -C embed-bitcode=no -C incremental --crate-type lib

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
#0 [evaluate_obligation] evaluating trait selection obligation `quote::Tokens: std::marker::Unpin`
#1 [is_unpin_raw] computing whether `quote::Tokens` is `Unpin`
end of query stack
warning: 49 warnings emitted

thread 'main' panicked at 'assertion failed: status.success()', collector/src/rustc-fake.rs:76:17
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: could not compile `syn`

I've created a standalone repository that reproduces this crash: https://github.com/Aaron1011/syn-crash

The following shell script can be used to reproduce the ICE:

set -xe

cargo clean -p syn
cargo clean --release -p syn
git checkout ee2bcdef16fc2b23a7becdcd5dcb361e085db75a
cargo build --release -j 1
git checkout 9ba859003d06df084b860fa62780dbf9169870d6
cargo build --release -j 1

EDIT: This appears to be due to the way we handle caching for a coinductive cycle.

The root cause appears to be here:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 390 to 407 in 5e65467

	fn evaluation_probe(
	&mut self,
	op: impl FnOnce(&mut Self) -> Result<EvaluationResult, OverflowError>,
	) -> Result<EvaluationResult, OverflowError> {
	self.infcx.probe(|snapshot| -> Result<EvaluationResult, OverflowError> {
	let result = op(self)?;
	match self.infcx.leak_check(true, snapshot) {
	Ok(()) => {}
	Err(_) => return Ok(EvaluatedToErr),
	}
	match self.infcx.region_constraints_added_in_snapshot(snapshot) {
	None => Ok(result),
	Some(_) => Ok(result.max(EvaluatedToOkModuloRegions)),
	}
	})
	}

The evaluation_probe method is used (among other things) to wrap the call to evaluate_predicate_recursively when we are trying to evaluate a root obligation. This means that any region constraints that get created during evaluation (including the recursive evaluation of other predicates) will cause us to return EvaluatedToOkModuloRegions.

However, whether or not we end up creating region constraints depends on the state of the evaluation cache - if we get a cache hit, we may skip creating a region constraint that would have otherwise been created. This means that re-running predicate evaluation during incremental compilation may produce a different result.

I see a few different ways of fixing this:

1. When we store a result in the evaluation cache, also store whether or not it caused any region constraints to get created. We then use this information when recursively processing predicates to ensure that we return EvaluatedToOkModuloRegions even if we got a cache hit.
2. Always return EvaluatedToOk when there are no erased regions in our original predicate (in this case, quote::Tokens: Unpin. I don't actually know if this is sound - there are no 'input' region variables to worry about, but I'm not sure if safe to ignore any 'internal' region constraints that get added.
3. Remove EvaluatedToOk entirely, and always return EvaluatedToOkModuloRegions. I'm not sure what the performance impact of doing this would be, or how much refactoring it would require. However, this would eliminate a large source of potential ICEs.

I'm not familiar enough with the trait evaluation code to know which, if any, of those options is the best choice.

cc @nikomatsakis @matthewjasper

[Aaron1011]

Always return EvaluatedToOk when there are no erased regions in our original predicate (in this case, quote::Tokens: Unpin. I don't actually know if this is sound - there are no 'input' regi

This option would make our choice of EvaluatedToOk/EvaluatedToOkModuloRegions depend entirely on the input predicate - if the predicate has any regions, we'll return EvaluatedToOkModuloRegions. Otherwise, we'll return EvaluatedToOk (assuming that evaluation succeeds).

[m-ou-se]

Can we revert whatever caused this (#83007, i think?) until a solution is available?

[Aaron1011]

@m-ou-se: These ICEs occur when we would otherwise produce an incorrect result. Given that there's already once case of that leading to unsoundness, I'd be concerned that we'd be simply covering up miscompilations.

[Aaron1011]

I opened #83719 to measure the performance impact of only ever returning EvaluatedToOkModuloRegions (and never using EvaluatedToOk). There were many large regressions, so I think we'll need to use a different option.

[Aaron1011]

Many people are running into this, and this is blocking us from getting full syn benchmarks on the perf server. I'm not familiar enough with the relevant trait system code to propose a fix (other than #83719, which has a very bad perf impact).

[Aaron1011]

I've opened #83913 with a potential fix