make: Add all the make support for lib{native,green}

This should now begin distribution of lib{green,native} in rlib/dylib format as
well as building them as part of the normal build process.

std: Update std::rt::thread to specify stack sizes

It's now possible to spawn an OS thread with a stack that has a specific size.

std: Fix a bug where Local::take() didn't zero out

In the compiled version of local_ptr (that with #[thread_local]), the take()
funciton didn't zero-out the previous pointer, allowing for multiple takes (with
fewer runtime assertions being tripped).

green: Rip the bandaid off, introduce libgreen

This extracts everything related to green scheduling from libstd and introduces
a new libgreen crate. This mostly involves deleting most of std::rt and moving
it to libgreen.

Along with the movement of code, this commit rearchitects many functions in the
scheduler in order to adapt to the fact that Local::take now *only* works on a
Task, not a scheduler. This mostly just involved threading the current green
task through in a few locations, but there were one or two spots where things
got hairy.

There are a few repercussions of this commit:

* tube/rc have been removed (the runtime implementation of rc)
* There is no longer a "single threaded" spawning mode for tasks. This is now
  encompassed by 1:1 scheduling + communication. Convenience methods have been
  introduced that are specific to libgreen to assist in the spawning of pools of
  schedulers.

native: Introduce libnative

This commit introduces a new crate called "native" which will be the crate that
implements the 1:1 runtime of rust. This currently entails having an
implementation of std::rt::Runtime inside of libnative as well as moving all of
the native I/O implementations to libnative.

The current snag is that the start lang item must currently be defined in
libnative in order to start running, but this will change in the future.

Cool fact about this crate, there are no extra features that are enabled.

Note that this commit does not include any makefile support necessary for
building libnative, that's all coming in a later commit.

std: Reimplement std::comm without the scheduler

Like the librustuv refactoring, this refactors std::comm to sever all ties with
the scheduler. This means that the entire `comm::imp` module can be deleted in
favor of implementations outside of libstd.

std: Move management of the exit code to std::os

Previously this functionality was located in std::rt::util, but there's no real
reason for it to be located in there.

rustuv: Reimplement without using std::rt::sched

This reimplements librustuv without using the interfaces provided by the
scheduler in libstd. This solely uses the new Runtime trait in order to
interface with the local task and perform the necessary scheduling operations.

The largest snag in this refactoring is reimplementing homing. The new runtime
trait exposes no concept of "homing" a task or forcibly sending a task to a
remote scheduler (there is no concept of a scheduler). In order to reimplement
homing, the transferrence of tasks is now done at the librustuv level instead of
the scheduler level. This means that all I/O loops now have a concurrent queue
which receives homing messages and requests.

This allows the entire implementation of librustuv to be only dependent on the
runtime trait, severing all dependence of librustuv on the scheduler and related
green-thread functions.

This is all in preparation of the introduction of libgreen and libnative.

At the same time, I also took the liberty of removing all glob imports from
librustuv.

std: Change Any::move to never consume the object

If the dynamic cast fails, this now returns the ~Any instance back to the
caller.

std: Make logging safely implemented

This commit fixes the logging function to be safely implemented, as well as
forcibly requiring a task to be present to use logging macros. This is safely
implemented by transferring ownership of the logger from the task to the local
stack frame in order to perform the print. This means that if a logger does more
logging while logging a new one will be initialized and then will get
overwritten once the initial logging function returns.

Without a scheme such as this, it is possible to unsafely alias two loggers by
logging twice (unsafely borrows from the task twice).

std: Handle prints with literally no context

Printing is an incredibly useful debugging utility, and it's not much help if
your debugging prints just trigger an obscure abort when you need them most. In
order to handle this case, forcibly fall back to a libc::write implementation of
printing whenever a local task is not available.

Note that this is *not* a 1:1 fallback. All 1:1 rust tasks will still have a
local Task that it can go through (and stdio will be created through the local
IO factory), this is only a fallback for "no context" rust code (such as that
setting up the context).

std: Expose that LocalIo may not always be available

It is not the case that all programs will always be able to acquire an instance
of the LocalIo borrow, so this commit exposes this limitation by returning
Option<LocalIo> from LocalIo::borrow().

At the same time, a helper method LocalIo::maybe_raise() has been added in order
to encapsulate the functionality of raising on io_error if there is on local I/O
available.

std: Introduce std::sync

For now, this moves the following modules to std::sync

* UnsafeArc (also removed unwrap method)
* mpsc_queue
* spsc_queue
* atomics
* mpmc_bounded_queue
* deque

We may want to remove some of the queues, but for now this moves things out of
std::rt into std::sync

std: Delete rt::test

This module contains many M:N specific concepts. This will no longer be
available with libgreen, and most functions aren't really that necessary today
anyway. New testing primitives will be introduced as they become available for
1:1 and M:N.

A new io::test module is introduced with the new ip4/ip6 address helpers to
continue usage in io tests.

std: Introduce an unstable::stack module

This module will be used to manage the OS-specific TLS registers used to specify
the bounds of the current rust stack (useful in 1:1 and M:N)

std: Introduce a Runtime trait

This trait is used to abstract the differences between 1:1 and M:N scheduling
and is the sole dispatch point for the differences between these two scheduling
modes.

This, and the following series of commits, is not intended to compile. Only
after the entire transition is complete are programs expected to compile.

auto merge of #11121 : vadimcn/rust/no-c++2, r=alexcrichton

This PR removes Rust's dependency on C++ for exception handling. Instead, it will use the unwind library API directly.

closes #10469

Stop using C++ exceptions for stack unwinding.

auto merge of #11130 : olsonjeffery/rust/master, r=alexcrichton

So that `Uuid` can be used as the key in a `HashMap` or in a `HashSet`, etc

The only question I have about this is: Is endianness an issue, here? If so, what's the correct way to proceed?

auto merge of #11091 : brson/rust/cratelinkattr, r=brson

This is set to *forbid* and prints a note explaining how to fix the problem.

extra: impl IterBytes for uuid::Uuid

rustc: Add a lint for the obsolete crate-level link attribute

auto merge of #11022 : spaolacci/rust/0read, r=alexcrichton

Could prevent callers from catching the situation and lead to e.g early
iterator terminations (cf. `Reader::read_byte`) since `None` is only to
be returned only on EOF.

auto merge of #11120 : alexcrichton/rust/rustdoc-test, r=brson

This commit adds a `--test` flag to rustdoc to expose the ability to test code examples in doc strings. This work by using sundown's `lang` attribute to figure out how a code block should be tested. The format for this is:

```
1. ```rust
2. ```rust,ignore
3. ```rust,notest
4. ```rust,should_fail
```

Where `rust` means that rustdoc will attempt to test is, `ignore` means that it will not execute the test but it will compile it, `notest` means that rustdoc completely ignores it, and `should_fail` means that the test should fail. This commit also leverages `extra::test` for the testing harness in order to allow parallelization and whatnot.

I have fixed all existing code examples in libstd and libextra, but I have not made a pass through the crates in order to change code blocks to testable code blocks.

It may also be a questionable decision to require opting-in to a testable code block.

Finally, I kept our sugar in the doc suite to omit lines starting with `#` in documentation but still process them during tests.

Closes #2925

Fixing more doc tests

doc: Expand rustdoc's documentation for testing

mk: Run doc tests as part of 'make check'

Don't run doc tests during make check-fast because it involves spawning lots of
processes.

extra: Fix all code examples

std: Fix all code examples

rustdoc: Add the ability to test code in comments

This adds support for the `--test` flag to rustdoc which will parse a crate,
extract all code examples in doc comments, and then run each test in the
extra::test driver.

Add tests for 0-byte read propagation.

The two `Some(0)' used to be `None' before the patch, a zero-byte long
read exhausting a reader (and thereafter) still produce a `None'.

auto merge of #11069 : alexcrichton/rust/issue-11067, r=brson

Turns out libuv's build system doesn't like us telling them that the build
directory is a relative location, as it always spits out a warning about a
circular dependency being dropped. By using an absolute path, turns out the
warnings isn't spit out, who knew?

Closes #11067

uv: Suppress a warning by using an absolute path

Turns out libuv's build system doesn't like us telling them that the build
directory is a relative location, as it always spits out a warning about a
circular dependency being dropped. By using an absolute path, turns out the
warnings isn't spit out, who knew?

Closes #11067

auto merge of #11111 : alexcrichton/rust/issue-11039, r=brson

None of these primitives should be Freeze because sharing them in an Arc is a
very bad idea.

Closes #11039

auto merge of #11109 : sfackler/rust/arc, r=alexcrichton

Closes #11097

auto merge of #11046 : zargony/rust/dep-info, r=alexcrichton

Using --dep-info writes Makefile-compatible dependency info to a file that is by default named based on the crate source filename. This adds an optional string argument to the --dep-info option which allows to write dependency info to an arbitrary filename.

cc #10698

auto merge of #11101 : jhasse/rust/patch-msys-quickfix, r=luqmana

I had this fixed but somehow forgot to commit it in my final patch. Sorry!

Allow optional filename argument for --dep-info

Use --crate-file-name to find out the library filename in dep-info test

auto merge of #11096 : brson/rust/pp, r=alexcrichton

auto merge of #11082 : brson/rust/noat, r=alexcrichton

auto merge of #11114 : klutzy/rust/a, r=cmr

mk: Clean .lib files

auto merge of #11064 : huonw/rust/vec-sort, r=alexcrichton

This uses quite a bit of unsafe code for speed and failure safety, and allocates `2*n` temporary storage.

[Performance](https://gist.github.com/huonw/5547f2478380288a28c2):

|      n |      new | priority_queue |   quick3 |
|-------:|---------:|---------------:|---------:|
|      5 |      200 |            155 |      106 |
|    100 |     6490 |           8750 |     5810 |
|  10000 |  1300000 |        1790000 |  1060000 |
| 100000 | 16700000 |       23600000 | 12700000 |
| sorted |   520000 |        1380000 | 53900000 |
|  trend |  1310000 |        1690000 |  1100000 |

(The times are in nanoseconds, having subtracted the set-up time (i.e. the `just_generate` bench target).)

I imagine that there is still significant room for improvement, particularly because both priority_queue and quick3 are doing a static call via `Ord` or `TotalOrd` for the comparisons, while this is using a (boxed) closure.

Also, this code does not `clone`, unlike `quick_sort3`; and is stable, unlike both of the others.

fix check-fast tests.

std::vec: make the sorting closure use `Ordering` rather than just being
(implicitly) less_eq.

auto merge of #10997 : cadencemarseille/rust/issue-10755-ICE-for-missing-linker, r=alexcrichton

Trap the io_error condition so that a more informative error message is
displayed when the linker program cannot be started, such as when the
name of the linker binary is accidentally mistyped.

closes #10755

Guarantee comm primitives are not Freeze

None of these primitives should be Freeze because sharing them in an Arc is a
very bad idea.

Closes #11039

auto merge of #11110 : alexcrichton/rust/attempt-to-fix-osx-segfaulting, r=brson

Upon inspecting the core dumps, they're all segfaulting at the same instruction
with the same value in a register that looks fishy. It appears to be indexing
into an array with a -1 index and then getting some weird overflow and dying.

I have attempted to fix this as part of
alexcrichton/libuv@fd5308383c575472edb2163d823dc6670bf59609,
but I am unsure of whether this is the actual cause of the problem, so I am not
going to upstream it just yet. I have a fairly high confidence that this is
indeed the problem, but I want to make sure that the bots to segfault all over
the place before upstreaming.

Attempt to fix the segfaulting osx bots

Upon inspecting the core dumps, they're all segfaulting at the same instruction
with the same value in a register that looks fishy. It appears to be indexing
into an array with a -1 index and then getting some weird overflow and dying.

I have attempted to fix this as part of
alexcrichton/libuv@fd5308383c575472edb2163d823dc6670bf59609,
but I am unsure of whether this is the actual cause of the problem, so I am not
going to upstream it just yet. I have a fairly high confidence that this is
indeed the problem, but I want to make sure that the bots to segfault all over
the place before upstreaming.

Remove unneccessary mut from arc

Don't poison ARCs that are used while unwinding

Closes #11097

auto merge of #11095 : brson/rust/issue-11094, r=alexcrichton

std: Remove some @-boxes

Remove unnecessary semicolon

auto merge of #11100 : klutzy/rust/win-no-pthread-2, r=alexcrichton

rustuv: Stop link to pthread on Windows

auto merge of #10930 : DaGenix/rust/remove-unnecessary-fields, r=alexcrichton

3 minor clean-ups now that #9629 is fixed:

* Update MutChunkIter to remove the ```remainder``` that existed just to allow the size_hint() method to be implemented. This is no longer necessary since we can just access the length of the slice directly.
* Update MutSplitIterator to address the FIXME in its size_hint() method. This method was only partially implemented due to the issue. Also, implement a minor optimization in the case that its the last iteration.
* Update ByRef iterator to implement the size_hint() method.

I noticed that MutSplitIterator returns an empty slice if called on an empty slice. I don't know if this is intended or not, but I left the ```finished``` field in-place to preserve this behavior.

@TeXitoi @blake2-ppc

auto merge of #11079 : chris-morgan/rust/fix-11072-regressions, r=brson

(#11072)

There, concrete evidence that I shouldn't try doing such things at 1:30am.

mk: Remove obsolete source reformatting rules

mk: Work around problem with run-make tests on multiple targets. #11094

Implement size_hint() for ByRef iterator

Update next() and size_hint() for MutSpliterIterator

Update the next() method to just return self.v in the case that we've reached
the last element that the iterator will yield. This produces equivalent
behavior as before, but without the cost of updating the field.

Update the size_hint() method to return a better hint now that #9629 is fixed.

Remove remainder field from MutChunkIter

This field is no longer necessary now that #9629 is fixed since we can just
access the length of the remaining slice directly.

auto merge of #11031 : jhasse/rust/patch-msys-3, r=cmr

Enable ANSI colors if TERM is set to cygwin and terminfo is not available (msys terminal on Windows). See #2807

auto merge of #11077 : alexcrichton/rust/crate-id, r=cmr

Right now the --crate-id and related flags are all process *after* the entire
crate is parsed. This is less than desirable when used with makefiles because it
means that just to learn the output name of the crate you have to parse the
entire crate (unnecessary).

This commit changes the behavior to lift the handling of these flags much sooner
in the compilation process. This allows us to not have to parse the entire crate
and only have to worry about parsing the crate attributes themselves. The
related methods have all been updated to take an array of attributes rather than
a crate.

Additionally, this ceases duplication of the "what output are we producing"
logic in order to correctly handle things in the case of --test.

Finally, this adds tests for all of this functionality to ensure that it does
not regress.

std::vec: add a sugary .sort() method for plain Ord sorting.

This moves the custom sorting to `.sort_by`.

Support ANSI colors in msys terminals. See #2807

auto merge of #10986 : adridu59/rust/patch-new, r=alexcrichton

Thanks to @huonw for some mentoring. :cake:

doc: forward-port the conditions tutorial + fixup libstd example

auto merge of #11075 : alexcrichton/rust/issue-10392, r=brson

We decided in the 12/10/13 weekly meeting that trailing commas should be
accepted pretty much anywhere. They are currently not allowed in struct
patterns, and this commit adds support for that.

Closes #10392

rustc: Improve crate id extraction

Right now the --crate-id and related flags are all process *after* the entire
crate is parsed. This is less than desirable when used with makefiles because it
means that just to learn the output name of the crate you have to parse the
entire crate (unnecessary).

This commit changes the behavior to lift the handling of these flags much sooner
in the compilation process. This allows us to not have to parse the entire crate
and only have to worry about parsing the crate attributes themselves. The
related methods have all been updated to take an array of attributes rather than
a crate.

Additionally, this ceases duplication of the "what output are we producing"
logic in order to correctly handle things in the case of --test.

Finally, this adds tests for all of this functionality to ensure that it does
not regress.

auto merge of #11081 : alexcrichton/rust/comm-adapters, r=huonw

I accidentally removed this module from compilation awhile back, this adds it
back in.

Closes #11076

auto merge of #11017 : alexcrichton/rust/faster-read, r=thestinger

We were previously reading metadata via `ar p`, but as learned from rustdoc
awhile back, spawning a process to do something is pretty slow. Turns out LLVM
has an Archive class to read archives, but it cannot write archives.

This commits adds bindings to the read-only version of the LLVM archive class
(with a new type that only has a read() method), and then it uses this class
when reading the metadata out of rlibs. When you put this in tandem of not
compressing the metadata, reading the metadata is 4x faster than it used to be
The timings I got for reading metadata from the respective libraries was:

    libstd-04ff901e-0.9-pre.dylib    => 100ms
    libstd-04ff901e-0.9-pre.rlib     => 23ms
    librustuv-7945354c-0.9-pre.dylib => 4ms
    librustuv-7945354c-0.9-pre.rlib  => 1ms
    librustc-5b94a16f-0.9-pre.dylib  => 87ms
    librustc-5b94a16f-0.9-pre.rlib   => 35ms
    libextra-a6ebb16f-0.9-pre.dylib  => 63ms
    libextra-a6ebb16f-0.9-pre.rlib   => 15ms
    libsyntax-2e4c0458-0.9-pre.dylib => 86ms
    libsyntax-2e4c0458-0.9-pre.rlib  => 22ms

In order to always take advantage of these faster metadata read-times, I sort
the files in filesearch based on whether they have an rlib extension or not
(prefer all rlib files first).

Overall, this halved the compile time for a `fn main() {}` crate from 0.185s to
0.095s on my system (when preferring dynamic linking). Reading metadata is still
the slowest pass of the compiler at 0.035s, but it's getting pretty close to
linking at 0.021s! The next best optimization is to just not copy the metadata
from LLVM because that's the most expensive part of reading metadata right now.

rustc: Optimize reading metadata by 4x

We were previously reading metadata via `ar p`, but as learned from rustdoc
awhile back, spawning a process to do something is pretty slow. Turns out LLVM
has an Archive class to read archives, but it cannot write archives.

This commits adds bindings to the read-only version of the LLVM archive class
(with a new type that only has a read() method), and then it uses this class
when reading the metadata out of rlibs. When you put this in tandem of not
compressing the metadata, reading the metadata is 4x faster than it used to be
The timings I got for reading metadata from the respective libraries was:

    libstd-04ff901e-0.9-pre.dylib    => 100ms
    libstd-04ff901e-0.9-pre.rlib     => 23ms
    librustuv-7945354c-0.9-pre.dylib => 4ms
    librustuv-7945354c-0.9-pre.rlib  => 1ms
    librustc-5b94a16f-0.9-pre.dylib  => 87ms
    librustc-5b94a16f-0.9-pre.rlib   => 35ms
    libextra-a6ebb16f-0.9-pre.dylib  => 63ms
    libextra-a6ebb16f-0.9-pre.rlib   => 15ms
    libsyntax-2e4c0458-0.9-pre.dylib => 86ms
    libsyntax-2e4c0458-0.9-pre.rlib  => 22ms

In order to always take advantage of these faster metadata read-times, I sort
the files in filesearch based on whether they have an rlib extension or not
(prefer all rlib files first).

Overall, this halved the compile time for a `fn main() {}` crate from 0.185s to
0.095s on my system (when preferring dynamic linking). Reading metadata is still
the slowest pass of the compiler at 0.035s, but it's getting pretty close to
linking at 0.021s! The next best optimization is to just not copy the metadata
from LLVM because that's the most expensive part of reading metadata right now.

auto merge of #11073 : klutzy/rust/issue-10978, r=alexcrichton

This patchset fixes small glitches which caused #10978.

auto merge of #11071 : huonw/rust/quiet-test, r=cmr

extra: remove sort in favour of the std method.

Fixes #9676.

std::vec: implement a stable merge sort, deferring to insertion sort for
very small runs.

This uses a lot of unsafe code for speed, otherwise we would be having
to sort by sorting lists of indices and then do a pile of swaps to put
everything in the correct place.

Fixes #9819.

auto merge of #11057 : alexcrichton/rust/no-at-in-ebml, r=pcwalton

Now that the metadata is an owned value with a lifetime of a borrowed byte
slice, it's possible to have future optimizations where the metadata doesn't
need to be copied around (very expensive operation).

Purge @-boxes from the reading half of EBML

Now that the metadata is an owned value with a lifetime of a borrowed byte
slice, it's possible to have future optimizations where the metadata doesn't
need to be copied around (very expensive operation).

Get comm_adapters building again

I accidentally removed this module from compilation awhile back, this adds it
back in.

Closes #11076

auto merge of #11060 : pcwalton/rust/tydecode-pod, r=pcwalton

r? @brson

Fix two regressions introduced by #11072.

There, concrete evidence that I shouldn't try doing such things at 1:30am.

librustc: Add missing case for the `Pod` bound in `tydecode`.

auto merge of #11072 : chris-morgan/rust/ctags-tweaks, r=cmr

Anchoring the keyword as the first non-whitespace on a line may mean
that the occasional genuine-but-unconventionally-formatted tag is
missed, but it avoids a large number of false positives.

I changed the type descriptive texts about a bit too. That part's purely
cosmetic.

I also changed the ignored file list to use a filename matching the make
rule, `TAGS.vi` instead of `TAGS.vim`.

auto merge of #11070 : ezyang/rust/better-errors, r=alexcrichton

On the advice of @huonw, I've just replaced item_span outright.

Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Accept trailing commas in struct patterns

We decided in the 12/10/13 weekly meeting that trailing commas should be
accepted pretty much anywhere. They are currently not allowed in struct
patterns, and this commit adds support for that.

Closes #10392

mklldeps.py: Ignore extra whitespaces of argument

rustc: Handle `#[link(name = "")]` error

auto merge of #11041 : cmr/rust/pkgid_changes, r=cmr,metajack

Add some things to inspect crate-id's

Rename pkgid to crate_id

Closes #11035

Remove many false positives from the ctags results

Anchoring the keyword as the first non-whitespace on a line may mean
that the occasional genuine-but-unconventionally-formatted tag is
missed, but it avoids a large number of false positives.

I changed the type descriptive texts about a bit too. That part's purely
cosmetic.

I also changed the ignored file list to use a filename matching the make
rule, `TAGS.vi` instead of `TAGS.vim`.

extra: silence warnings during testing.

std: silence warnings when compiling test.

auto merge of #11061 : huonw/rust/opt-unsafe-vec, r=alexcrichton

Before:

```
test vec::bench::random_inserts                     ... bench:     15025 ns/iter (+/- 409)
test vec::bench::random_removes                     ... bench:     16063 ns/iter (+/- 276)
```

After:

```
test vec::bench::random_inserts                     ... bench:      5257 ns/iter (+/- 321)
test vec::bench::random_removes                     ... bench:      4980 ns/iter (+/- 94)
```

std::vec: use some unsafe code to optimise `remove`.

Also, add `.remove_opt` and replace `.unshift` with `.remove(0)`. The
code size reduction seem to compensate for not having the optimised
special cases.

This makes the included benchmark more than 3 times faster.

Generalize item_span into node_span, which works on more types.

Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

auto merge of #11065 : huonw/rust/slice-chars-example, r=cmr