bors [Wed, 14 Dec 2016 14:35:42 +0000 (14:35 +0000)]
Auto merge of #38351 - sanxiyn:doc-test-args, r=alexcrichton
Document --test-args for rustbuild
There are three changes:
* Replace --filter with --test-args
* Delete `./x.py test src/test/run-pass/assert-*` example, which doesn't work
* As driveby, update Buildbot URLs to https
bors [Wed, 14 Dec 2016 09:56:38 +0000 (09:56 +0000)]
Auto merge of #38340 - alexcrichton:fix-travis, r=alexcrichton
Fix travis builds
After reading some articles [1] [2] yesterday about Docker and the "init"
process I got to thinking about the problems that we've been seeing on Travis.
The basic problem is that a Linux system may need an "init" process to work
properly when processes become zombies. Docker by default doesn't handle this
and the root process typically isn't an init process, so this can occasionally
cause quite a few problems.
We've been seeing spurious errors on Travis inside containers which look like
OOM and such, but my guess is that zombie processes were being reparented to the
top-level shell. The shell didn't expect the zombies and then behaved very
strangely.
This commit fixes these problems by using Yelp's "dumb-init" program [2] as the
init process in all of our containers. This ensures that there's a valid init
ready to reap children when they're reparented, which our test suite apparently
generates a bunch of throughout the tests and such.
bors [Wed, 14 Dec 2016 00:31:48 +0000 (00:31 +0000)]
Auto merge of #38181 - jsgf:test-filter-exact, r=alexcrichton
libtest: add --exact to make filter matching exact
Filter matching is by substring by default. This makes it impossible
to run a single test if its name is a substring of some other test.
For example, its not possible to run just `mymod::test` with these
tests:
bors [Tue, 13 Dec 2016 18:29:22 +0000 (18:29 +0000)]
Auto merge of #38353 - alexcrichton:fix-nightiles, r=alexcrichton
Another round of nightly fixes
Another three separate errors happened last night:
* Race condition in save analysis failed the OX build
* Packaging docs that don't exist failed the Android build
* Packaging save-analysis that doesn't exist failed the cross host builds
Alex Crichton [Tue, 13 Dec 2016 17:17:33 +0000 (09:17 -0800)]
rustbuild: Skip some more non-relevant dist steps
This commit skips a few more dist tragets during compilation which shouldn't be
necessary.
* First, when packaging std we only take action when the host target is the
build target. Otherwise we package the same artifacts a number of times, which
shouldn't be necessary.
* Next, we apply the same logic to the save-analysis build. This is actually
required for correctness as the build compiler is the only one which actually
has save analysis information. This should fix an error seen on nightlies.
Alex Crichton [Tue, 13 Dec 2016 17:12:39 +0000 (09:12 -0800)]
rustc: Use `create_dir_racy` in save analysis
The OSX bots failed last night due a race condition in save analysis where
concurrent calls to `fs::create_dir_all` conflicted with one another. This
replaces the relevant function call with `fs::create_dir_racy` which is defined
internally to the compiler.
Alex Crichton [Tue, 13 Dec 2016 04:01:13 +0000 (20:01 -0800)]
Fix travis builds
After reading some articles [1] [2] yesterday about Docker and the "init"
process I got to thinking about the problems that we've been seeing on Travis.
The basic problem is that a Linux system may need an "init" process to work
properly when processes become zombies. Docker by default doesn't handle this
and the root process typically isn't an init process, so this can occasionally
cause quite a few problems.
We've been seeing spurious errors on Travis inside containers which look like
OOM and such, but my guess is that zombie processes were being reparented to the
top-level shell. The shell didn't expect the zombies and then behaved very
strangely.
This commit fixes these problems by using Yelp's "dumb-init" program [2] as the
init process in all of our containers. This ensures that there's a valid init
ready to reap children when they're reparented, which our test suite apparently
generates a bunch of throughout the tests and such.
bors [Tue, 13 Dec 2016 06:29:25 +0000 (06:29 +0000)]
Auto merge of #38179 - michael-zapata:rf/harmonise_rustdoc_errors, r=GuillaumeGomez
feat(rustdoc): harmonise error messages
Based on unix tools wording, it follows a standard format: `program_name: context: error message`, potentially prompting the user to use the `--help` option.
This is clearly meant to trigger some discussion on #38084, as messages still use `stdout` and `stderr` somewhat arbitrarily, and there are a few `error!()` calls as well.
Corey Farwell [Mon, 12 Dec 2016 19:10:33 +0000 (14:10 -0500)]
Rollup merge of #38264 - ollie27:rustdoc_src_macro, r=brson
rustdoc: Remove broken src links from reexported items from macros
When an item is defined in an external macro it doesn't get a real
filename so we need to filter out these when generating src links for
reexported items.
Corey Farwell [Mon, 12 Dec 2016 19:10:32 +0000 (14:10 -0500)]
Rollup merge of #37941 - Cobrand:docfix-issue-37915, r=GuillaumeGomez
Improve and fix mpsc documentation
Closes #37915
This commit enhances documentation with several links and
fixes an error in the `sync_channel` documentation as well:
`send` doesn't panic when the senders are all disconnected
Alex Crichton [Mon, 12 Dec 2016 17:28:13 +0000 (09:28 -0800)]
rustbuild: Check for .git as a dir
Git worktrees have this as a file and typically won't work inside docker
containers, but that's ok, so instead of just checking for existence check for a
directory to see if the git commands will succeed.
Alex Crichton [Mon, 12 Dec 2016 17:27:14 +0000 (09:27 -0800)]
rustbuild: Update gcc-rs to 0.3.40
This commit updates the gcc-rs dependency to 0.3.40 to pick up a fix for i686
musl where we needed to pass an extra linker flag to get autoconf's detection of
executables working correctly.
Michael Zapata [Mon, 5 Dec 2016 02:21:08 +0000 (03:21 +0100)]
feat(rustdoc): harmonise error messages
Based on unix tools wording, it follows a standard format:
`program_name: context: error message` on stderr, prompting the user
to use the `--help` option in case of misuse.
bors [Sun, 11 Dec 2016 21:19:34 +0000 (21:19 +0000)]
Auto merge of #38265 - bluss:mir-deaggregator-loop, r=nagisa
Reinstate while loop in deaggregator pass
A previous commit must have removed the `while let` loop here by
mistake; for each basic block, it should find and deaggregate multiple
statements in their index order, and the `curr` index tracks the
progress through the block.
This fixes both the case of deaggregating statements in separate
basic blocks (preserving `curr` could prevent that) as well
as multiple times in the same block (missing loop prevented that).
bors [Sun, 11 Dec 2016 09:33:05 +0000 (09:33 +0000)]
Auto merge of #38249 - arielb1:special-substs, r=nikomatsakis
erase lifetimes when translating specialized substs
Projections can generate lifetime variables with equality constraints,
that will not be resolved by `resolve_type_vars_if_possible`, so substs
need to be lifetime-erased after that.
bors [Sun, 11 Dec 2016 06:37:19 +0000 (06:37 +0000)]
Auto merge of #38250 - michaelwoerister:trait-methods-in-reachable, r=alexcrichton
Consider provided trait methods in middle::reachable
Fixes https://github.com/rust-lang/rust/issues/38226 by also considering trait methods with default implementation instead of just methods provided in an impl.
Ulrik Sverdrup [Fri, 9 Dec 2016 15:28:54 +0000 (16:28 +0100)]
mir: Reinstate while loop in deaggregator pass
A previous commit must have removed the `while let` loop here by
mistake; for each basic block, it should find and deaggregate multiple
statements in their index order, and the `curr` index tracks the
progress through the block.
This fixes both the case of deaggregating statements in separate
basic blocks (preserving `curr` could prevent that) as well
as multiple times in the same block (missing loop prevented that).
bors [Fri, 9 Dec 2016 15:45:41 +0000 (15:45 +0000)]
Auto merge of #38197 - mneumann:dragonfly-fixes-2016-12-06, r=alexcrichton
Fix current_exe() on DragonFly (again)
This is a follow up on [this pull request][1].
Since DragonFly 4.6.1 ([this commit][2]), the ```kern.proc.pathname```
sysctl works correctly, i.e. it does not return paths including a ```:```
(see [here][3]). Use it and don't try to fix old versions of DragonFly!
There are not many DragonFly installations out there that we can't
control and no one is compiling Rust from source. If someone wants to
run Rust on a pre-4.6.1 DragonFly system, the ports system should
provide a patch.
rustdoc: Remove broken src links from reexported items from macros
When an item is defined in an external macro it doesn't get a real
filename so we need to filter out these when generating src links for
reexported items.
bors [Fri, 9 Dec 2016 10:00:25 +0000 (10:00 +0000)]
Auto merge of #38192 - stjepang:faster-sort-algorithm, r=bluss
Implement a faster sort algorithm
Hi everyone, this is my first PR.
I've made some changes to the standard sort algorithm, starting out with a few tweaks here and there, but in the end this endeavour became a complete rewrite of it.
#### Summary
Changes:
* Improved performance, especially on partially sorted inputs.
* Performs less comparisons on both random and partially sorted inputs.
* Decreased the size of temporary memory: the new sort allocates 4x less.
First, let me just do a quick brain dump to discuss what I learned along the way.
The official documentation says that the standard sort in Rust is a stable sort. This constraint is thus set in stone and immediately rules out many popular sorting algorithms. Essentially, the only algorithms we might even take into consideration are:
1. [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)
2. [Block sort](https://en.wikipedia.org/wiki/Block_sort) (famous implementations are [WikiSort](https://github.com/BonzaiThePenguin/WikiSort) and [GrailSort](https://github.com/Mrrl/GrailSort))
3. [TimSort](https://en.wikipedia.org/wiki/Timsort)
Actually, all of those are just merge sort flavors. :) The current standard sort in Rust is a simple iterative merge sort. It has three problems. First, it's slow on partially sorted inputs (even though #29675 helped quite a bit). Second, it always makes around `log(n)` iterations copying the entire array between buffers, no matter what. Third, it allocates huge amounts of temporary memory (a buffer of size `2*n`, where `n` is the size of input).
The problem of auxilliary memory allocation is a tough one. Ideally, it would be best for our sort to allocate `O(1)` additional memory. This is what block sort (and it's variants) does. However, it's often very complicated (look at [this](https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.cpp)) and even then performs rather poorly. The author of WikiSort claims good performance, but that must be taken with a grain of salt. It performs well in comparison to `std::stable_sort` in C++. It can even beat `std::sort` on partially sorted inputs, but on random inputs it's always far worse. My rule of thumb is: high performance, low memory overhead, stability - choose two.
TimSort is another option. It allocates a buffer of size `n/2`, which is not great, but acceptable. Performs extremelly well on partially sorted inputs. However, it seems pretty much all implementations suck on random inputs. I benchmarked implementations in [Rust](https://github.com/notriddle/rust-timsort), [C++](https://github.com/gfx/cpp-TimSort), and [D](https://github.com/dlang/phobos/blob/fd518eb310a9494cccf28c54892542b052c49669/std/algorithm/sorting.d#L2062). The results were a bit disappointing. It seems bad performance is due to complex galloping procedures in hot loops. Galloping noticeably improves performance on partially sorted inputs, but worsens it on random ones.
#### The new algorithm
Choosing the best algorithm is not easy. Plain merge sort is bad on partially sorted inputs. TimSort is bad on random inputs and block sort is even worse. However, if we take the main ideas from TimSort (intelligent merging strategy of sorted runs) and drop galloping, then we'll have great performance on random inputs and it won't be bad on partially sorted inputs either.
That is exactly what this new algorithm does. I can't call it TimSort, since it steals just a few of it's ideas. Complete TimSort would be a much more complex and elaborate implementation. In case we in the future figure out how to incorporate more of it's ideas into this implementation without crippling performance on random inputs, it's going to be very easy to extend. I also did several other minor improvements, like reworked insertion sort to make it faster.
There are also new, more thorough benchmarks and panic safety tests.
The final code is not terribly complex and has less unsafe code than I anticipated, but there's still plenty of it that should be carefully reviewed. I did my best at documenting non-obvious code.
I'd like to notify several people of this PR, since they might be interested and have useful insights:
1. @huonw because he wrote the [original merge sort](https://github.com/rust-lang/rust/pull/11064).
2. @alexcrichton because he was involved in multiple discussions of it.
3. @veddan because he wrote [introsort](https://github.com/veddan/rust-introsort) in Rust.
4. @notriddle because he wrote [TimSort](https://github.com/notriddle/rust-timsort) in Rust.
5. @bluss because he had an attempt at writing WikiSort in Rust.
6. @gnzlbg, @rkruppe, and @mark-i-m because they were involved in discussion #36318.
**P.S.** [quickersort](https://github.com/notriddle/quickersort) describes itself as being universally [faster](https://github.com/notriddle/quickersort/blob/master/perf.txt) than the standard sort, which is true. However, if this PR gets merged, things might [change](https://gist.github.com/stjepang/b9f0c3eaa0e1f1280b61b963dae19a30) a bit. ;)
bors [Fri, 9 Dec 2016 07:08:29 +0000 (07:08 +0000)]
Auto merge of #38256 - alexcrichton:distcheck, r=brson
rustbuild: Implement distcheck
This commit implements the `distcheck` target for rustbuild which is only ever
run on our nightly bots. This essentially just creates a tarball, un-tars it,
and then runs a full build, validating that the release tarballs do indeed have
everything they need to build Rust.
Alex Crichton [Fri, 9 Dec 2016 01:13:55 +0000 (17:13 -0800)]
rustbuild: Implement distcheck
This commit implements the `distcheck` target for rustbuild which is only ever
run on our nightly bots. This essentially just creates a tarball, un-tars it,
and then runs a full build, validating that the release tarballs do indeed have
everything they need to build Rust.
Stjepan Glavina [Thu, 8 Dec 2016 21:37:36 +0000 (22:37 +0100)]
Inline nested fn collapse
Since merge_sort is generic and collapse isn't, that means calls to
collapse won't be inlined. inlined. Therefore, we must stick an
`#[inline]` above `fn collapse`.