search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
99.09k stars 12.79k forks source link

Regression in usable type complexity: overflow representing the type `...` #71359

Open chrysn opened 4 years ago

chrysn commented 4 years ago

I tried building the iron example of typed-html (version 810fc820, but it's not changing frequently) the code is heavy with (partially recursive) generic types.

With the latest beta (1.43) or stable (1.42), builds succeed; with nightly, they fail with:

$ cargo +nightly build --verbose
[...]
error: overflow representing the type `std::option::Option<&T>`

error: aborting due to previous error

error: could not compile `typed-html`.

Caused by:
  process didn't exit successfully: `rustc --crate-name typed_html --edition=2018 typed-html/src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C debuginfo=2 -C metadata=d47a854ad488ad21 -C extra-filename=-d47a854ad488ad21 --out-dir /tmp/typed-html/target/debug/deps -C incremental=/tmp/typed-html/target/debug/incremental -L dependency=/tmp/typed-html/target/debug/deps --extern htmlescape=/tmp/typed-html/target/debug/deps/libhtmlescape-93c9e1d0e3ad1b35.rmeta --extern language_tags=/tmp/typed-html/target/debug/deps/liblanguage_tags-25ca56886cd3e2ae.rmeta --extern mime=/tmp/typed-html/target/debug/deps/libmime-c67f239ef9444378.rmeta --extern proc_macro_hack=/tmp/typed-html/target/debug/deps/libproc_macro_hack-6271c07fb42254ec.so --extern proc_macro_nested=/tmp/typed-html/target/debug/deps/libproc_macro_nested-a84f2a4ba9005aa7.rmeta --extern strum=/tmp/typed-html/target/debug/deps/libstrum-13ea7f88aaf14180.rmeta --extern strum_macros=/tmp/typed-html/target/debug/deps/libstrum_macros-5e348577b435118e.so --extern typed_html_macros=/tmp/typed-html/target/debug/deps/libtyped_html_macros-3ce45005b6c7b859.so` (exit code: 1)

The iron example is comparatively simple typed-html usage. I've originally observed the same kind of regression in a game that uses typed-html.

Meta

This might be an occurrence of #32498; the behavior changing from stable/beta to nightly indicates a new issue and is thus reported anew.

rustc +nightly --version --verbose:

rustc 1.44.0-nightly (dbf8b6bf1 2020-04-19)
binary: rustc
commit-hash: dbf8b6bf116c7bece2987ff4bd2792f008a6ee77
commit-date: 2020-04-19
host: x86_64-unknown-linux-gnu
release: 1.44.0-nightly
LLVM version: 9.0

(Running with RUST_BACKTRACE does not change the output.)

Bisection results

I'm running cargo bisect-rustc on the code, which has narrowed it down to a regression in nightly-2020-04-10. I'll update this with a more detailled bisection result when it's ready, but that might be a while.

chrysn commented 4 years ago

Here's what cargo bisect-rustc says about it:

Regression found in the compiler

searched nightlies: from nightly-2020-04-05 to nightly-2020-04-12 regressed nightly: nightly-2020-04-10 searched commits: from https://github.com/rust-lang/rust/commit/485c5fb6e1bf12cd11a8fac5ee94962e17cff74b to https://github.com/rust-lang/rust/commit/94d346360da50f159e0dc777dc9bc3c5b6b51a00 regressed commit: https://github.com/rust-lang/rust/commit/93dc97a85381cc52eb872d27e50e4d518926a27c

jonas-schievink commented 4 years ago

Maybe https://github.com/rust-lang/rust/pull/70896?

chrysn commented 4 years ago

I've built cargo with current master (2dc5b602eee35d70e8e6e506a7ea07b6c7e0197d) with the commits ce8abc63a7e1fcac4b69574e00a70352e583cec8, 2c4cffde3bdc36d9634ebf24e512f19aa6fe1ccb, 8aac1077ed495ef8d1241ce76d4b64d7eb13a856 and 859b8da21fc82c08fde8b3aafefc12881a0c3f09 reverted.

(Workflow, just to ensure I don't get things wrong methodically as this is the first time I build rust: Clone rust recursively, ./x.py build, test, revet the commits, ./x.py build, test again. The test step happens in a checkout of the failing code with PATH=.../build/${triple}/stage2/bin/:.../build/${triple}/stage0/bin/:$PATH, where the stage0 path gives me a cargo; tests get a cargo clear in-between due to changed std library and compiler).

While on master the error is present, and vanishes with the reverts.

[edit: For context, this confirms Jonas' assumption that #70896 caused the regression]

spastorino commented 4 years ago

Assigning P-medium as discussed as part of the Prioritization Working Group process, removing I-prioritize and also nominating for discussion on our next weekly meeting.

spastorino commented 4 years ago

cc @cuviper

chrysn commented 4 years ago

Reading up on the archived convesation, I've tried with an increased recursion limit. Setting the recursion limit inside the typed_html crate up did the trick; I'll bisect around a bit there to see how much the limit demands have raised.

If this is deemed acceptable breakage, it might be helpful to have an error message in the overflow message that says which crate is being compiled, and that the recursion limit should be incremented there.

chrysn commented 4 years ago

For the case of the typed-html crate, the recursion limit transition is between

(Note I had to clean some target/**/typed?html* out between tests, as some build artifacts survived the recursion limit change).

This indicates that the usual recommendation to double the recursion limit is valid for this case (as was to be expected).

One (not sure if relevant, but maybe) lesson learned from the process is that sometimes when you hit the limit edge-on (as it is with typed-html, where the limit of 128 was 2 short of working), you get short error outputs that don't indicate the large type (as was the original std::option::Option<&T>, or just &T when the limit is set to 129. In other cases, the nesting depth of the reported type was proportional to the size of missing recursion stack (eg. 

overflow representing the type `std::option::Option<std::iter::Chain<std::iter::Chain<std::iter::Empty<(&str, &T)>, std::iter::Map<std::option::Iter<T>, [closure@typed-html/src/events.rs:41:30: 41:64]>>, std::iter::Map<std::option::Iter<T>, [closure@typed-html/src/events.rs:41:30: 41:64]>>>`

when 10 below the limit, nesting deeper with greater depth).

cuviper commented 4 years ago

Wow, that's a big chain! It's constructed in macro_rules! declare_events_struct here:

        impl<T: Send> Events<T> {
            pub fn iter(&self) -> impl Iterator<Item = (&'static str, &T)> {
                iter::empty()
                $(
                    .chain(
                        self.$name.iter()
                        .map(|value| (stringify!($name), value))
                    )
                )*
            }

And that macro is invoked here with 63 repetitions! Since #70896 added a new Option layer to each Chain field, I suppose it makes sense that this nested type got much deeper, but I'm not sure there's anything I can do about it (besides revert).

I'd be curious to know if the change had any positive effect on that mega-Chain though. It may be smaller due to niche layout with Option versus the separate ChainState, and I'm interested in what that does to performance too.

Or if they care to try avoiding such a huge chain, I expect it would work perfectly well for that method to just push to a local Vec and return that as the iterator.

cuviper commented 4 years ago

Or if they care to try avoiding such a huge chain, I expect it would work perfectly well for that method to just push to a local Vec and return that as the iterator.

I submitted this as https://github.com/bodil/typed-html/pull/117.

However, I also see that the repo declares it is not currently maintained.

chrysn commented 4 years ago

I won't speculate here about the vec improvements that could be made (that belongs in https://github.com/bodil/typed-html/pull/117), but had a look at the change from 2020-04-09 to 2020-04-10 nightlies on an example I built into my application that actually uses the deeply nested chaining event iterator (as it was not actually used in any examples I found). Given that it fails to compile in finite time (well, 15 minutes) on the 2020-04-09 nightly and works well on the 2020-04-10 one, that's all I can report but is a pretty vast improvement.

All I see fit to do from there is speculate that other crates affected by this might have unbuildable code inside them as well, which might be a small pointer in the direction of allowing the regression (possibly with an enhanced error message).

cuviper commented 4 years ago

Given that it fails to compile in finite time (well, 15 minutes) on the 2020-04-09 nightly and works well on the 2020-04-10 one, that's all I can report but is a pretty vast improvement.

That apparent hang may be akin to #70749. I'm happy that the new Chain avoids that problem, but it still deserves some compiler investigation.

Mark-Simulacrum commented 4 years ago

Closed the crater-found regression issue (https://github.com/rust-lang/rust/issues/71764) in favor of this one, they seem to be the same, though it's not 100% clear.

spastorino commented 4 years ago

This is really a libs-impl thing, fixing labels accordingly.

kilork commented 4 years ago

Have similar issue, but cannot solve it with #![recursion_limit = "256"] or more.

It worked fine, when all structures and traits were in a single file, but does not work, if I split it into modules.

Single file: https://github.com/rsbt/rsbt/blob/8322411dc2a219216eb92ae8a9a06dce690acea0/rsbt-app/src/experiments.rs (here is App and Handler structs are in the same module).

Broken revision: https://github.com/rsbt/rsbt/commit/93f00734f9170d9471dd696cd0bc785088b6215c (IncommingConnectionsManager is basically same idea as Handler before).

I was able to make it working by removing Debug requirement. I do not need any specific recursion_limit if it is in the same file or does not have Debug requirement.

cuviper commented 4 years ago

@kilork is yours a regression, or a more general occurrence of that error? This specific issue was associated with a change in the Chain implementation. At a glance it doesn't look like your code is chaining anything, so it may be a different cause. The fact that the module split affects it sounds like a very different thing.

kilork commented 4 years ago

@cuviper I do not think so. Checked with 1.40, it is the same error. I think it is just coincedence and another issue.

cuviper commented 4 years ago

The new Chain released in 1.45 -- are we accepting (or resigned to) that type complexity?

arekbulski commented 3 years ago

I tried importing almost every version that was release. Every damn single one of them fails, for one reason or another. Is there any version that I can safely import while retaining html! macro? Could you recommend an alternative module?

m-ou-se commented 3 years ago

Started a Zulip thread here to discuss what to do with this issue: https://rust-lang.zulipchat.com/#narrow/stream/131828-t-compiler/topic/Type.20complexity.20regression/near/249126680

m-ou-se commented 3 years ago

Reassigning from compiler, as there's not much we can do in the library. We'll leave it up to the compiler team to decide on a possible solution, or close otherwise.