Exponential compilation time on chained "invalid left-hand side of assignment"

[jruderman]

This invalid code takes about 8 seconds to (not) compile:

fn main() {
    1=1=1=1=1=1=1=1=1;
}

Each added 1= doubles the compilation time. Memory use also grows, although not as quickly.

Found by fuzzing with a modified fuzz-rustc.

What is slow

Compiling with -Z time-passes says the slow pass is item_bodies_checking.

Full output with -Z time-passes

$ rustc -Z time-passes owl.rs
time:   0.006; rss:   21MB ->   21MB (   +0MB)	parse_crate
time:   0.000; rss:   22MB ->   22MB (   +0MB)	attributes_injection
time:   0.000; rss:   22MB ->   22MB (   +0MB)	plugin_loading
time:   0.002; rss:   22MB ->   22MB (   +0MB)	crate_injection
time:   0.067; rss:   22MB ->   25MB (   +3MB)	expand_crate
time:   0.000; rss:   25MB ->   25MB (   +0MB)	check_unused_macros
time:   0.067; rss:   22MB ->   25MB (   +3MB)	macro_expand_crate
time:   0.000; rss:   25MB ->   25MB (   +0MB)	maybe_building_test_harness
time:   0.002; rss:   25MB ->   26MB (   +0MB)	AST_validation
time:   0.000; rss:   26MB ->   26MB (   +0MB)	maybe_create_a_macro_crate
time:   0.000; rss:   26MB ->   26MB (   +0MB)	finalize_imports
time:   0.000; rss:   26MB ->   26MB (   +0MB)	resolve_access_levels
time:   0.006; rss:   26MB ->   26MB (   +0MB)	finalize_macro_resolutions
time:   0.001; rss:   26MB ->   26MB (   +0MB)	late_resolve_crate
time:   0.000; rss:   26MB ->   26MB (   +0MB)	resolve_main
time:   0.000; rss:   26MB ->   26MB (   +0MB)	resolve_check_unused
time:   0.000; rss:   26MB ->   26MB (   +0MB)	resolve_report_errors
time:   0.000; rss:   26MB ->   26MB (   +0MB)	resolve_postprocess
time:   0.007; rss:   26MB ->   26MB (   +1MB)	resolve_crate
time:   0.000; rss:   26MB ->   26MB (   +0MB)	complete_gated_feature_checking
time:   0.001; rss:   26MB ->   26MB (   +0MB)	early_lint_checks
time:   0.086; rss:   22MB ->   26MB (   +5MB)	configure_and_expand
time:   0.000; rss:   26MB ->   26MB (   +0MB)	prepare_outputs
time:   0.002; rss:   27MB ->   27MB (   +0MB)	setup_global_ctxt
time:   0.000; rss:   27MB ->   27MB (   +0MB)	drop_ast
time:   0.012; rss:   27MB ->   28MB (   +1MB)	looking_for_entry_point
time:   0.001; rss:   28MB ->   28MB (   +0MB)	looking_for_derive_registrar
time:   0.001; rss:   28MB ->   28MB (   +0MB)	unused_lib_feature_checking
time:   0.022; rss:   27MB ->   28MB (   +2MB)	misc_checking_1
time:   0.007; rss:   28MB ->   29MB (   +0MB)	type_collecting
time:   0.000; rss:   29MB ->   29MB (   +0MB)	impl_wf_inference
time:   0.001; rss:   29MB ->   29MB (   +0MB)	coherence_checking
time:   0.010; rss:   29MB ->   30MB (   +1MB)	wf_checking
time:   0.000; rss:   30MB ->   30MB (   +0MB)	item_types_checking
error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:20
  |
2 |     1=1=1=1=1=1=1=1=1;
  |                   -^
  |                   |
  |                   cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:18
  |
2 |     1=1=1=1=1=1=1=1=1;
  |                 -^
  |                 |
  |                 cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:16
  |
2 |     1=1=1=1=1=1=1=1=1;
  |               -^
  |               |
  |               cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:14
  |
2 |     1=1=1=1=1=1=1=1=1;
  |             -^
  |             |
  |             cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:12
  |
2 |     1=1=1=1=1=1=1=1=1;
  |           -^
  |           |
  |           cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:10
  |
2 |     1=1=1=1=1=1=1=1=1;
  |         -^
  |         |
  |         cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:8
  |
2 |     1=1=1=1=1=1=1=1=1;
  |       -^
  |       |
  |       cannot assign to this expression

error[E0070]: invalid left-hand side of assignment
 --> owl.rs:2:6
  |
2 |     1=1=1=1=1=1=1=1=1;
  |     -^
  |     |
  |     cannot assign to this expression

time:   9.628; rss:   30MB ->   63MB (  +34MB)	item_bodies_checking
time:   9.647; rss:   28MB ->   64MB (  +35MB)	type_check_crate
time:   0.001; rss:   64MB ->   64MB (   +0MB)	serialize_dep_graph
time:   0.002; rss:   64MB ->   54MB (  -10MB)	free_global_ctxt
error: aborting due to 8 previous errors

For more information about this error, try `rustc --explain E0070`.

Output from sample suggests that the problem involves the co-recursion between two functions in rustc_hir_analysis/: check_expr_kind and check_expr_with_expectation_and_args.

Meta

rustc --version --verbose:

rustc 1.66.0-nightly (b8b5caee0 2022-10-16)
binary: rustc
commit-hash: b8b5caee04116c7383eb1c6470fcf15c437a60d4
commit-date: 2022-10-16
host: x86_64-apple-darwin
release: 1.66.0-nightly
LLVM version: 15.0.2

@rustbot label +I-compiletime

[compiler-errors]

lol my fault

[compiler-errors]

regressed in d50d3fc, I'll put up a fix.