Regression in usable type complexity: overflow representing the type ...

[chrysn]

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]

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 485c5fb to 94d3463
regressed commit: 93dc97a

[jonas-schievink]

Maybe #70896?

[chrysn]

I've built cargo with current master (2dc5b60) with the commits ce8abc6, 2c4cffd, 8aac107 and 859b8da 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]

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]

cc @cuviper

[chrysn]

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]

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

• for stable (rustc 1.42.0 (b8cedc0 2020-03-09)): between 68 and 69
• for beta (rustc 1.44.0-beta.752 (a7d891e 2020-04-21)): between 129 and 130

(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]

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]

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 bodil/typed-html#117.

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

[chrysn]

I won't speculate here about the vec improvements that could be made (that belongs in bodil/typed-html#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]

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]

Closed the crater-found regression issue (#71764) in favor of this one, they seem to be the same, though it's not 100% clear.

[spastorino]

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

[kilork]

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: rsbt/rsbt@93f0073 (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]

@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]

@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]

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

[arekbulski]

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]

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]

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.