compilation of unicode_segmentation crate hangs on nightly

[djudd]

https://github.com/unicode-rs/unicode-segmentation

Both on Travis.yml (seemingly) and on a local box. Locally, strace gives:

$ sudo strace -p 25340
Process 25340 attached
futex(0x7f4e823ff9d0, FUTEX_WAIT, 25342, NULL
^C

$ rustc --version
rustc 1.9.0-nightly (6d215fe04 2016-03-14)

Running Ubuntu 14.04 trusty.

[alexcrichton]

I unfortunately can't reproduce this on OSX:

$ multirust run nightly cargo build --release
   Compiling unicode-segmentation v0.1.2 (file:///Users/acrichton/code/unicode-segmentation)
$ multirust run nightly rustc -vV
rustc 1.9.0-nightly (6d215fe04 2016-03-14)
binary: rustc
commit-hash: 6d215fe04ce3f638d717d7fcea95c40d0a655ff9
commit-date: 2016-03-14
host: x86_64-apple-darwin
release: 1.9.0-nightly

Does this happen reproducibly for you in the repo on a normal cargo build on Linux?

[djudd]

Hmm, nope. cargo build on unicode_segmentation directly is fine.

I think it's not be unicode_segmentation at all, but something weird with the dependency structure of my library (which is where I saw the issue, on cargo build): https://github.com/djudd/human-name

I ran cargo clean then cargo build again, and this time it appears to be hanging on phf_macros.

I assumed because a hang also happens on Travis that it's not something local to my environment, but might have jumped the gun in assigning blame. FWIW, everything compiles fine on older nightlies, e.g. Feb 14.

[alexcrichton]

This appears to be pathological behavior in the unidecode crate, the 2016-03-09 nightly compiled that crate in ~4s while the 2016-03-11 nightly basically never returns. Unfortunately there was no 2016-03-10 nightly.

Some suspicious PRs merged during that time were:

• #32097 - cc @jseyfried
• #31710 - cc @eddyb
• #31618 - cc me!

After a few seconds the offending backtrace looks like:

Thread 2 (Thread 0x7fffedfff700 (LWP 4305)):
#0  0x00007ffff48a0467 in middle::infer::region_inference::RegionVarBindings$LT$$u27$a$C$$u20$$u27$tcx$GT$::infer_variable_values::h13047075df6ab7ca6zA ()
   from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc-18402db3.so
#1  0x00007ffff484ec4a in middle::infer::region_inference::RegionVarBindings$LT$$u27$a$C$$u20$$u27$tcx$GT$::resolve_regions::hd1aae808037814e6lsA ()
   from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc-18402db3.so
#2  0x00007ffff484eb97 in middle::infer::InferCtxt$LT$$u27$a$C$$u20$$u27$tcx$GT$::resolve_regions_and_report_errors::ha3c7008b38ce75654hE ()
   from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc-18402db3.so
#3  0x00007ffff6b2825e in check::regionck::regionck_expr::hd7cd1f3071a82f93Wmc () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#4  0x00007ffff6b280a2 in check::check_const_with_ty::h313c7bb2ab876a2e07s () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#5  0x00007ffff6ad503a in check::check_const::h337b7a49255e2b0cK6s () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#6  0x00007ffff6abde1f in check::check_item_type::h8475073b43b488e4h4o () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#7  0x00007ffff6abd1d2 in check::CheckItemTypesVisitor$LT$$u27$a$C$$u20$$u27$tcx$GT$.Visitor$LT$$u27$tcx$GT$::visit_item::hc7dbddc6e361f3d3KHo ()
   from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#8  0x00007ffff6abbb5d in check::check_item_types::h5114724f2e7fe669LJo () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#9  0x00007ffff6ab3355 in check_crate::hcd126beee06d4b43IGC () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_typeck-18402db3.so
#10 0x00007ffff7a7fa1d in driver::phase_3_run_analysis_passes::_$u7b$$u7b$closure$u7d$$u7d$::closure.30211 () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#11 0x00007ffff7a7e015 in middle::ty::context::TyCtxt$LT$$u27$tcx$GT$::create_and_enter::h17882283280588378896 () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#12 0x00007ffff7a7abf3 in driver::phase_3_run_analysis_passes::h13919317650711339916 () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#13 0x00007ffff7a4d3c0 in driver::compile_input::h148bbe225adb9061Pca () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#14 0x00007ffff7a3ab47 in run_compiler::h01319ef2912a48felQc () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#15 0x00007ffff7a382c2 in sys_common::unwind::try::try_fn::h15450783821430179622 () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#16 0x00007ffff753f47c in __rust_try () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/libstd-18402db3.so
#17 0x00007ffff753f40e in sys_common::unwind::inner_try::hfb91b5cfe185b795Ztu () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/libstd-18402db3.so
#18 0x00007ffff7a38b0b in boxed::F.FnBox$LT$A$GT$::call_box::h7115862480082857486 () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/librustc_driver-18402db3.so
#19 0x00007ffff7549e5a in sys::thread::Thread::new::thread_start::h33a79b9c7e674b88Huz () from /home/alex/.multirust/toolchains/nightly-2016-03-11/lib/libstd-18402db3.so
#20 0x00007fffefc9a182 in start_thread (arg=0x7fffedfff700) at pthread_create.c:312
#21 0x00007ffff71af47d in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:111

@eddyb, @jseyfried, thoughts?

[alexcrichton]

Also, nominating as this seems like a pretty serious regression

[alexcrichton]

also cc @nikomatsakis, region inference infinite loop maybe?

[Stebalien]

FYI, this also causes rustdoc to hang.

[nikomatsakis]

hmm I have yet to be able to reproduce this :(

[nikomatsakis]

ah, never mind.

[nikomatsakis]

I think what is happening is some kind of poor interaction with the new coercion logic that @eddyb introduced. In particular, we are spending a lot of energy creating least-upper-bounds where likely we never did before, and creating a ton of region variables -- the logic around LUB is not particularly smart right now. This leads to a problem checking the large [&'static str; 0xffff] constant.

[nikomatsakis]

Indeed just compiling this file as an rlib causes the problem.

[eddyb]

@nikomatsakis I tried avoiding quadratic behavior, assuming O(1) LUB - is it even hitting the loops of preceding expressions in coerce::try_find_lub?

[nikomatsakis]

@eddyb the problem is that LUB creates a ton of region variables, I think. we could surely solve this particular case by just some simple checks (e.g., when we enter coerce, we already know that the two types are equal, so even if a==b {return;} would work). But I'm sort of re-reading through trying to think where we can generalize.

[nikomatsakis]

In particular, each call to LUB creates a fresh region variable, at least. I'm not actually clear on why that scales up SO badly, perhaps region-inference just needs to be rewritten (that wouldn't surprise me, the cost is largely untouched for quite some time). I've been wanting to rewrite it anyway but mostly because it's model is outdated... but in any case here it seems like we should not generate these constraints to begin with.

[nikomatsakis]

/me closed by accident

[nikomatsakis]

(Yet another reason to pursue splitting typeck/regionck...)

[eddyb]

@nikomatsakis Right, just trying to make sure it's not hitting the worst possible case.
IIRC we wanted to always reborrow for some reason, but at least in LUB mode, the reborrows are pointless, so the equality check should just work.

[nikomatsakis]

OK, I think I've got this covered. Hopefully I'll have a patch up tomorrow, don't think I have time to finish it tonight.

[nikomatsakis]

triage: P-high