auto merge of #12899 : brson/rust/cleanbacktrace, r=alexcrichton

After `make clean` I'm seeing the build break with

```
cp: cannot stat ‘x86_64-unknown-linux-gnu/rt/libbacktrace/.libs/libbacktrace.a’: No such file or directory
```

Deleteing the libbacktrace dir entirely on clean fixes.

auto merge of #12791 : alexcrichton/rust/liblog, r=brson

The rationale and modifications can be found in the first commit message.

This does make logging a bit more painful to use initially because it involves a feature gate and some `phase` attributes, but I think it may be reasonable to not require the `phase` attribute for loading `macro_rules!` macros because defining them will still be gated.

Test fixes and rebase conflicts

This commit switches over the backtrace infrastructure from piggy-backing off
the RUST_LOG environment variable to using the RUST_BACKTRACE environment
variable (logging is now disabled in libstd).

rustc: Topographically sort rust dependencies

This commit starts to topographically sort rust dependencies on the linker
command line. The reason for this is that linkers use right-hand libraries to
resolve left-hand libraries symbols, which is especially crucial for us because
we're using --as-needed on linux.

rustc: Tweak where -lmorestack is on link commands

In removing many fields from the crate map, executables no longer always have an
explicit dependency on all upstream libraries. This means that the linker is no
longer picking them up as it used to.

To the best of my knowledge, the current situation is happening:

* On linux, we're passing the --as-needed flag to the linker, meaning that
  libraries are stripped out if there are no references to symbols in them.
* Executables may not reference libstd at all, such as "fn main() {}"
* When linking, the linker will discard libstd because there are no references
  to symbols in it. I presume that this means that all previous libs have had
  all their symbols resolved, so none of the libs are pulling in libstd as a
  dependency.
* The only real dependence on libstd comes from the rust_stack_exhausted symbol
  (which comes from libmorestack), but -lmorestack is at the end so by the time
  this comes up libstd is completely gone, leading to undefined references to
  rust_stack_exhausted

I'm not entirely convinced that this is what's happening, but it appears to be
along these lines. The one thing that I'm sure of is that removing the crate map
(and hence implicit dependency on all upstream libraries) has changed how
objects depend on upstream libraries.

rustc: Remove compiler support for __log_level()

This commit removes all internal support for the previously used __log_level()
expression. The logging subsystem was previously modified to not rely on this
magical expression. This also removes the only other function to use the
module_data map in trans, decl_gc_metadata. It appears that this is an ancient
function from a GC only used long ago.

This does not remove the crate map entirely, as libgreen still uses it to hook
in to the event loop provided by libgreen.

log: Introduce liblog, the old std::logging

This commit moves all logging out of the standard library into an external
crate. This crate is the new crate which is responsible for all logging macros
and logging implementation. A few reasons for this change are:

* The crate map has always been a bit of a code smell among rust programs. It
  has difficulty being loaded on almost all platforms, and it's used almost
  exclusively for logging and only logging. Removing the crate map is one of the
  end goals of this movement.

* The compiler has a fair bit of special support for logging. It has the
  __log_level() expression as well as generating a global word per module
  specifying the log level. This is unfairly favoring the built-in logging
  system, and is much better done purely in libraries instead of the compiler
  itself.

* Initialization of logging is much easier to do if there is no reliance on a
  magical crate map being available to set module log levels.

* If the logging library can be written outside of the standard library, there's
  no reason that it shouldn't be. It's likely that we're not going to build the
  highest quality logging library of all time, so third-party libraries should
  be able to provide just as high-quality logging systems as the default one
  provided in the rust distribution.

With a migration such as this, the change does not come for free. There are some
subtle changes in the behavior of liblog vs the previous logging macros:

* The core change of this migration is that there is no longer a physical
  log-level per module. This concept is still emulated (it is quite useful), but
  there is now only a global log level, not a local one. This global log level
  is a reflection of the maximum of all log levels specified. The previously
  generated logging code looked like:

    if specified_level <= __module_log_level() {
        println!(...)
    }

  The newly generated code looks like:

    if specified_level <= ::log::LOG_LEVEL {
        if ::log::module_enabled(module_path!()) {
            println!(...)
        }
    }

  Notably, the first layer of checking is still intended to be "super fast" in
  that it's just a load of a global word and a compare. The second layer of
  checking is executed to determine if the current module does indeed have
  logging turned on.

  This means that if any module has a debug log level turned on, all modules
  with debug log levels get a little bit slower (they all do more expensive
  dynamic checks to determine if they're turned on or not).

  Semantically, this migration brings no change in this respect, but
  runtime-wise, this will have a perf impact on some code.

* A `RUST_LOG=::help` directive will no longer print out a list of all modules
  that can be logged. This is because the crate map will no longer specify the
  log levels of all modules, so the list of modules is not known. Additionally,
  warnings can no longer be provided if a malformed logging directive was
  supplied.

The new "hello world" for logging looks like:

    #[phase(syntax, link)]
    extern crate log;

    fn main() {
        debug!("Hello, world!");
    }

auto merge of #12927 : sfackler/rust/test-warn, r=huonw

The use of `std::os::args` creates a deprecated_owned_vector warning
with a bogus span.

Squash test ~[] warning

The use of `std::os::args` creates a deprecated_owned_vector warning
with a bogus span.

auto merge of #12923 : sfackler/rust/vecify, r=brson

auto merge of #12922 : luqmana/rust/fix-arm, r=alexcrichton

mk: Clean libbacktrace w/ gusto

After `make clean' I'm seeing the build break with

```
cp: cannot stat ‘x86_64-unknown-linux-gnu/rt/libbacktrace/.libs/libbacktrace.a’: No such file or directory
```

Deleteing the libbacktrace dir entirely on clean fixes.

auto merge of #12921 : alexcrichton/rust/no-extra, r=sfackler

Forgot to remove this as part of the previous removal of libextra

libstd: Fix a typo. s/target_os/target_arch/

Remove ~[] from libsemver

doc: Remove reference to the 'extra' library

Forgot to remove this as part of the previous removal of libextra

Remove most ~[] usage in liburl

auto merge of #12918 : sfackler/rust/doc-html-attr, r=alexcrichton

Add rustdoc html crate info

auto merge of #12908 : alexcrichton/rust/issue-12897, r=thestinger

This is mostly just an implementation detail, and anyone worried about the stack
bounds doesn't need to be bothered with the red zone because it's not usable
anyway.

Closes #12897

auto merge of #12906 : sfackler/rust/timespec-total, r=thestinger

auto merge of #12896 : alexcrichton/rust/goodbye-extra, r=brson

This commit shreds all remnants of libextra from the compiler and standard
distribution. Two modules, c_vec/tempfile, were moved into libstd after some
cleanup, and the other modules were moved to separate crates as seen fit.

Closes #8784
Closes #12413
Closes #12576

green: Don't return the red zone in stack_bounds()

This is mostly just an implementation detail, and anyone worried about the stack
bounds doesn't need to be bothered with the red zone because it's not usable
anyway.

Closes #12897

Implement TotalEq and TotalOrd for Timespec

There's a test making sure that Ord works, so the order dependence
shouldn't be an issue

auto merge of #12895 : michaelwoerister/rust/limited-debuginfo, r=alexcrichton

Very minor modification of just one test case. Fixes #12787.

auto merge of #12887 : huonw/rust/danger-guide, r=alexcrichton

docs: begin a "low-level & unsafe code" guide.

This aims to cover the basics of writing safe unsafe code. At the moment
it is just designed to be a better place for the `asm!()` docs than the
detailed release notes wiki page, and I took the time to write up some
other things.

More examples are needed, especially of things that can subtly go wrong;
and vast areas of `unsafe`-ty aren't covered, e.g. `static mut`s and
thread-safety in general.

docs: begin a "low-level & unsafe code" guide.

This aims to cover the basics of writing safe unsafe code. At the moment
it is just designed to be a better place for the `asm!()` docs than the
detailed release notes wiki page, and I took the time to write up some
other things.

More examples are needed, especially of things that can subtly go wrong;
and vast areas of `unsafe`-ty aren't covered, e.g. `static mut`s and
thread-safety in general.

auto merge of #12893 : alexcrichton/rust/cfg-not, r=luqmana

The two commits have the details of the two fixes

auto merge of #12888 : aochagavia/rust/Fix-comment, r=alexcrichton

The old comment of as_mut_slice() did not describe the function correctly. The new one does.

Also refactored option::iter() and option::mut_iter() to use as_ref() and as_mut() instead of match.

auto merge of #12878 : crabtw/rust/mips, r=alexcrichton

I ignored AtomicU64 methods on MIPS target
because libgcc doesn't implement MIPS32 64-bit atomic operations.
Otherwise it would cause link failure.

By the way, the patched LLVM doesn't have MIPS split stack anymore.
Should I file an issue about that?

extra: Put the nail in the coffin, delete libextra

This commit shreds all remnants of libextra from the compiler and standard
distribution. Two modules, c_vec/tempfile, were moved into libstd after some
cleanup, and the other modules were moved to separate crates as seen fit.

Closes #8784
Closes #12413
Closes #12576

auto merge of #12869 : thestinger/rust/cmp, r=brson

The `Float` trait provides correct `min` and `max` methods on floating
point types, providing a consistent result regardless of the order the
parameters are passed.

These generic functions do not take the necessary performance hit to
correctly support a partial order, so the true requirement should be
given as a type bound.

Closes #12712

cmp: switch `min` and `max` to `TotalOrd`

The `Float` trait provides correct `min` and `max` methods on floating
point types, providing a consistent result regardless of the order the
parameters are passed.

These generic functions do not take the necessary performance hit to
correctly support a partial order, so the true requirement should be
given as a type bound.

Closes #12712

debuginfo: Make limited-debuginfo test case more robust against GDB output variations.

Fixes issue #12787.

std: Fix backtraces on arm linux

On android, libgcc is missing the _Unwind_GetIP symbol because it's defined as a
macro. This is the same case for arm linux, so this commit adds the necessary
cfgs in place to use the "expanded macro" in rust for arm linux.

rustc: Fix cfg(not(a, b)) to be not(a && b)

Previously, the cfg attribute `cfg(not(a, b))` was translated to `(!a && !b)`,
but this isn't very useful because that can already be expressed as
`cfg(not(a), not(b))`. This commit changes the translation to `!(a && b)` which
is more symmetrical of the rest of the `cfg` attribute.

Put another way, I would expect `cfg(clause)` to be the opposite of
`cfg(not(clause))`, but this is not currently the case with multiple element
clauses.

Refactored iter and mut_iter

Replaced match by self.as_ref() and self.as_mut()

auto merge of #12880 : tedhorst/rust/master, r=alexcrichton

Fix a test that was missed in the chan/port renaming (PR #12815).  This was missed because it is skipped on linux and windows, and the mac bots were moving at the time the PR landed.

Fixed comment of as_mut_slice (libstd/option.rs)

The old comment did not describe the function correctly

auto merge of #12764 : Kimundi/rust/partial_typehint, r=nikomatsakis

# Summary

This patch introduces the `_` token into the type grammar, with the meaning "infer this type".
With this change, the following two lines become equivalent:
```
let x = foo();
let x: _ = foo();
```
But due to its composability, it enables partial type hints like this:
```
let x: Bar<_> = baz();
```

Using it on the item level is explicitly forbidden, as the Rust language does not enable global type inference by design.

This implements the feature requested in https://github.com/mozilla/rust/issues/9508.

# Things requiring clarification

- The change to enable it is very small, but I have only limited understanding of the related code, so the approach here might be wrong.
  - In particular, while this patch works, it does so in a way not originally intended according to the code comments.
- This probably needs more tests, or rather feedback for which tests are still missing.
- I'm unsure how this interacts with lifetime parameters, and whether it is correct in regard to them.
- Partial type hints on the right side of `as` like `&foo as *_` work in both a normal function contexts and in constexprs like `static foo: *int = &'static 123 as *_`. The question is whether this should be allowed in general.

# Todo for this PR

- The manual and tutorial still needs updating.

# Bugs I'm unsure how to fix

- Requesting inference for the top level of the right hand side of a `as` fails to infer correctly, even if all possible hints are given:

  ```
.../type_hole_1.rs:35:18: 35:22 error: the type of this value must be known in this context
.../type_hole_1.rs:35     let a: int = 1u32 as _;
                                           ^~~~
```

Added support for type placeholders (explicit requested type
inference in a type with `_` ). This enables partial type inference.

auto merge of #12875 : alexcrichton/rust/demangle-more-things, r=brson

Add some more infrastructure support for demangling `$`-sequences, as well as fixing demangling of closure symbol names if there's more than one closure in a function.

auto merge of #12874 : huonw/rust/printier-rustc, r=alexcrichton

rustc: make stack traces print for .span_bug/.bug.

Previously a call to either of those to diagnostic printers would defer
to the `fatal` equivalents, which explicitly silence the stderr
printing, including a stack trace from `RUST_LOG=std::rt::backtrace`.

This splits the bug printers out to their own diagnostic type so that
things work properly.

Also, this removes the `Ok(...)` that was being printed around the
subtask's stderr output.

auto merge of #12871 : aochagavia/rust/Optimize-while_some, r=alexcrichton

The old 'while' needed to match 2 times for each iteration. With the new 'loop' there is just one match needed.

I have also replaced 'blk' by 'f' to be more consistent with parameter names in other functions that are implemented for Option<T>

auto merge of #12867 : alexcrichton/rust/issue-12860, r=thestinger

This switches a "tail call" to a manual loop to get around LLVM not optimizing
to a tail call.

Close #12860

auto merge of #12864 : huonw/rust/hash-docs, r=alexcrichton

collections: move hashmap's example to the struct.

Most people go straight to the struct, not looking at the module, so the
example was well hidden.

auto merge of #12861 : huonw/rust/lint-owned-vecs, r=thestinger

lint: add lint for use of a `~[T]`.

This is useless at the moment (since pretty much every crate uses
`~[]`), but should help avoid regressions once completely removed from a
crate.

fix a test that was missed in the chan/port renaming (PR #12815)

auto merge of #12855 : alexcrichton/rust/shutdown, r=brson

This is something that is plausibly useful, and is provided by libuv. This is
not currently surfaced as part of the `TcpStream` type, but it may possibly
appear in the future. For now only the raw functionality is provided through the
Rtio objects.

fix MIPS target

I ignored AtomicU64 methods on MIPS target
because libgcc doesn't implement MIPS32 64-bit atomic operations.
Otherwise it would cause link failure.

auto merge of #12798 : pczarn/rust/inline-asm, r=alexcrichton

## read+write modifier '+'
This small sugar was left out in the original implementation (#5359).

When an output operand with the '+' modifier is encountered, we store the index of that operand alongside the expression to create and append an input operand later. The following lines are equivalent:
```
asm!("" : "+m"(expr));
asm!("" : "=m"(expr) : "0"(expr));
```
## misplaced options and clobbers give a warning
It's really annoying when a small typo might change behavior without any warning.
```
asm!("mov $1, $0" : "=r"(x) : "r"(8u) : "cc" , "volatile");
//~^ WARNING expected a clobber, but found an option
```
## liveness
Fixed incorrect order of propagation.
Sometimes it caused spurious warnings in code: `warning: value assigned to `i` is never read, #[warn(dead_assignment)] on by default`

~~Note: Rebased on top of another PR. (uses other changes)~~

* [x] Implement read+write
* [x] Warn about misplaced options
* [x] Fix liveness (`dead_assignment` lint)
* [x] Add all tests

std: render the vec_ng docs.

These are wildly incomplete, but having something there is better than
nothing, e.g. so that people know it exists, and many of the functions
behaviour can be guessed from the name or by checking the source: it's
knowing they exist at all that's the hard part.

lint: add lint for use of a `~[T]`.

This is useless at the moment (since pretty much every crate uses
`~[]`), but should help avoid regressions once completely removed from a
crate.

rustc: Prevent collisions in names of closures

This commit goes back to using `gensym` to generate unique tokens to put into
the names of closures, allowing closures to be able to get demangled in
backtraces.

Closes #12400

std: Demangle more escapes in backtraces

The rust compiler not only outputs symbols in the form that C++ does, but it
also mangle symbols like '&' and '~' to special compiler-defined escape
sequences. For convenience, these symbols are demangled when printing
backtraces.

rustc: make stack traces print for .span_bug/.bug.

Previously a call to either of those to diagnostic printers would defer
to the `fatal` equivalents, which explicitly silence the stderr
printing, including a stack trace from `RUST_LOG=std::rt::backtrace`.

This splits the bug printers out to their own diagnostic type so that
things work properly.

Also, this removes the `Ok(...)` that was being printed around the
subtask's stderr output.

io: Bind to shutdown() for TCP streams

This is something that is plausibly useful, and is provided by libuv. This is
not currently surfaced as part of the `TcpStream` type, but it may possibly
appear in the future. For now only the raw functionality is provided through the
Rtio objects.

Fix and improve inline assembly.

Read+write modifier
Some documentation in asm.rs
rpass and cfail tests

auto merge of #12815 : alexcrichton/rust/chan-rename, r=brson

* Chan<T> => Sender<T>
* Port<T> => Receiver<T>
* Chan::new() => channel()
* constructor returns (Sender, Receiver) instead of (Receiver, Sender)
* local variables named `port` renamed to `rx`
* local variables named `chan` renamed to `tx`

Closes #11765

Refactored while_some (libstd/option.rs)

The old 'while' needed to match 2 times for each iteration. With the new
'loop' there is just one match needed.

I have also replaced 'blk' by 'f' to be more consistent with parameter
names in other functions that are implemented for Option

std: Rename Chan/Port types and constructor

* Chan<T> => Sender<T>
* Port<T> => Receiver<T>
* Chan::new() => channel()
* constructor returns (Sender, Receiver) instead of (Receiver, Sender)
* local variables named `port` renamed to `rx`
* local variables named `chan` renamed to `tx`

Closes #11765

auto merge of #12573 : lbonn/rust/unrecurs, r=alexcrichton

As mentioned in #6109, ```mkdir_recursive``` doesn't really need to use recursive calls, so here is an iterative version.
The other points of the proposed overhaul (renaming and existing permissions) still need to be resolved.

I also bundled an iterative ```rmdir_recursive```, for the same reason.

Please do not hesitate to provide feedback on style as this is my first code change in rust.

auto merge of #12561 : pzol/rust/char-case, r=alexcrichton

Added common and simple case folding, i.e. mapping one to one character mapping. For more information see http://www.unicode.org/faq/casemap_charprop.html

Removed auto-generated dead code which wasn't used.

collections: Don't recurse in hashmap robin_hood

This switches a "tail call" to a manual loop to get around LLVM not optimizing
to a tail call.

Close #12860

auto merge of #12238 : ktt3ja/rust/lifetime-error-msg, r=nikomatsakis

For the following code snippet:

```rust
struct Foo { bar: int }
fn foo1(x: &Foo) -> &int {
    &x.bar
}
```

This PR generates the following error message:

```rust
test.rs:2:1: 4:2 note: consider using an explicit lifetime parameter as shown: fn foo1<'a>(x: &'a Foo) -> &'a int
test.rs:2 fn foo1(x: &Foo) -> &int {
test.rs:3     &x.bar
test.rs:4 }
test.rs:3:5: 3:11 error: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
test.rs:3     &x.bar
              ^~~~~~
```

Currently it does not support methods.

auto merge of #12852 : itdaniher/rust/master, r=alexcrichton

This enables the lowering of llvm 64b intrinsics to hardware ops, resolving issues around `__kernel_cmpxchg64` on older kernels on ARM devices, and also enables use of the hardware floating point unit, resolving https://github.com/mozilla/rust/issues/10482.

auto merge of #12849 : nick29581/rust/doubles, r=alexcrichton

auto merge of #12610 : eddyb/rust/deref-now-auto, r=nikomatsakis

Enables the dereference overloads introduced by #12491 to be applied wherever automatic dereferences would be used (field accesses, method calls and indexing).

Tweak comments

compile-fail: Beef up borrowck test to include some scenarios where we borrow mutably twice in a row

Region + borrow checker support and tests for overloaded autoderef.

Apply @nikomatsakis' nits and comments patch.

Introduce a common recursion limit for auto-dereference and monomorphization.

Implement automatic overloaded dereference.
Closes #7141.

Remove Rc's borrow method to avoid conflicts with RefCell's borrow in Rc<RefCell<T>>.

auto merge of #12845 : eddyb/rust/vec-no-drop-flag, r=thestinger

collections: move hashmap's example to the struct.

Most people go straight to the struct, not looking at the module, so the
example was well hidden.

Remove code duplication

Remove whitespace

Update documentation for to_uppercase, to_lowercase

Implement lower, upper case conversion for char

std::unicode: remove unused category tables

auto merge of #12602 : alexcrichton/rust/backtrace, r=brson

Whenever a failure happens, if a program is run with
`RUST_LOG=std::rt::backtrace` a backtrace will be printed to the task's stderr
handle. Stack traces are uncondtionally printed on double-failure and
rtabort!().

This ended up having a nontrivial implementation, and here's some highlights of
it:

* We're bundling libbacktrace for everything but OSX and Windows
* We use libgcc_s and its libunwind apis to get a backtrace of instruction
  pointers
* On OSX we use dladdr() to go from an instruction pointer to a symbol
* On unix that isn't OSX, we use libbacktrace to get symbols
* Windows, as usual, has an entirely separate implementation

Lots more fun details and comments can be found in the source itself.

Closes #10128

Add basic backtrace functionality

Whenever a failure happens, if a program is run with
`RUST_LOG=std::rt::backtrace` a backtrace will be printed to the task's stderr
handle. Stack traces are uncondtionally printed on double-failure and
rtabort!().

This ended up having a nontrivial implementation, and here's some highlights of
it:

* We're bundling libbacktrace for everything but OSX and Windows
* We use libgcc_s and its libunwind apis to get a backtrace of instruction
  pointers
* On OSX we use dladdr() to go from an instruction pointer to a symbol
* On unix that isn't OSX, we use libbacktrace to get symbols
* Windows, as usual, has an entirely separate implementation

Lots more fun details and comments can be found in the source itself.

Closes #10128

auto merge of #12414 : DaGenix/rust/failing-iterator-wrappers, r=alexcrichton

Most IO related functions return an IoResult so that the caller can handle failure in whatever way is appropriate. However, the `lines`, `bytes`, and `chars` iterators all supress errors. This means that code that needs to handle errors can't use any of these iterators. All three of these iterators were updated to produce IoResults.

Fixes #12368

auto merge of #12823 : alexcrichton/rust/issue-12666, r=pcwalton

If a TTY fails to get initialized, it still needs to have uv_close invoked on
it. This fixes the problem by constructing the TtyWatcher struct before the call
to uv_tty_init. The struct has a destructor on it which will close the handle
properly.

Closes #12666

auto merge of #12822 : erickt/rust/cleanup, r=acrichto

This PR makes `std::io::FileStat` hashable, and `Path` serializable as a byte array.

Update io iterators to produce IoResults

Most IO related functions return an IoResult so that the caller can handle failure
in whatever way is appropriate. However, the `lines`, `bytes`, and `chars` iterators all
supress errors. This means that code that needs to handle errors can't use any of these
iterators. All three of these iterators were updated to produce IoResults.

Fixes #12368

auto merge of #12756 : pongad/rust/remove_owned_str_pat, r=alexcrichton

match-drop-strs-issue-4541.rs deleted as it's the same with issue-4541.rs

syntax: change the #[deriving(Hash)] typaram variable name

serialize: make Paths serializable

std: allow io::File* structs to be hashable

auto merge of #12081 : cgaebel/rust/robinhood-hashing, r=alexcrichton

Partially addresses #11783.

Previously, rust's hashtable was totally unoptimized. It used an Option
per key-value pair, and used very naive open allocation.

The old hashtable had very high variance in lookup time. For an example,
see the 'find_nonexisting' benchmark below. This is fixed by keys in
'lucky' spots with a low probe sequence length getting their good spots
stolen by keys with long probe sequence lengths. This reduces hashtable
probe length variance, while maintaining the same mean.

Also, other optimization liberties were taken. Everything is as cache
aware as possible, and this hashtable should perform extremely well for
both large and small keys and values.

Benchmarks:

```
comprehensive_old_hashmap         378 ns/iter (+/- 8)
comprehensive_new_hashmap         206 ns/iter (+/- 4)
1.8x faster

old_hashmap_as_queue              238 ns/iter (+/- 8)
new_hashmap_as_queue              119 ns/iter (+/- 2)
2x faster

old_hashmap_insert                172 ns/iter (+/- 8)
new_hashmap_insert                146 ns/iter (+/- 11)
1.17x faster

old_hashmap_find_existing         50 ns/iter (+/- 12)
new_hashmap_find_existing         35 ns/iter (+/- 6)
1.43x faster

old_hashmap_find_notexisting      49 ns/iter (+/- 49)
new_hashmap_find_notexisting      34 ns/iter (+/- 4)
1.44x faster

Memory usage of old hashtable (64-bit assumed):

aligned(8+sizeof(Option)+sizeof(K)+sizeof(V))/0.75 + 48ish bytes

Memory usage of new hashtable:

(aligned(sizeof(K))
+ aligned(sizeof(V))
+ 8)/0.9 + 112ish bytes

Timing of building librustc:

compile_and_link: x86_64-unknown-linux-gnu/stage0/lib/rustlib/x86_64-unknown-linux-gnu/lib/librustc
time: 0.457 s   parsing
time: 0.028 s   gated feature checking
time: 0.000 s   crate injection
time: 0.108 s   configuration 1
time: 1.049 s   expansion
time: 0.219 s   configuration 2
time: 0.222 s   maybe building test harness
time: 0.223 s   prelude injection
time: 0.268 s   assinging node ids and indexing ast
time: 0.075 s   external crate/lib resolution
time: 0.026 s   language item collection
time: 1.016 s   resolution
time: 0.038 s   lifetime resolution
time: 0.000 s   looking for entry point
time: 0.030 s   looking for macro registrar
time: 0.061 s   freevar finding
time: 0.138 s   region resolution
time: 0.110 s   type collecting
time: 0.072 s   variance inference
time: 0.126 s   coherence checking
time: 9.110 s   type checking
time: 0.186 s   const marking
time: 0.049 s   const checking
time: 0.418 s   privacy checking
time: 0.057 s   effect checking
time: 0.033 s   loop checking
time: 1.293 s   compute moves
time: 0.182 s   match checking
time: 0.242 s   liveness checking
time: 0.866 s   borrow checking
time: 0.150 s   kind checking
time: 0.013 s   reachability checking
time: 0.175 s   death checking
time: 0.461 s   lint checking
time: 13.112 s  translation
  time: 4.352 s llvm function passes
  time: 96.702 s    llvm module passes
  time: 50.574 s    codegen passes
time: 154.611 s LLVM passes
  time: 2.821 s running linker
time: 15.750 s  linking

compile_and_link: x86_64-unknown-linux-gnu/stage1/lib/rustlib/x86_64-unknown-linux-gnu/lib/librustc
time: 0.422 s   parsing
time: 0.031 s   gated feature checking
time: 0.000 s   crate injection
time: 0.126 s   configuration 1
time: 1.014 s   expansion
time: 0.251 s   configuration 2
time: 0.249 s   maybe building test harness
time: 0.273 s   prelude injection
time: 0.279 s   assinging node ids and indexing ast
time: 0.076 s   external crate/lib resolution
time: 0.033 s   language item collection
time: 1.028 s   resolution
time: 0.036 s   lifetime resolution
time: 0.000 s   looking for entry point
time: 0.029 s   looking for macro registrar
time: 0.063 s   freevar finding
time: 0.133 s   region resolution
time: 0.111 s   type collecting
time: 0.077 s   variance inference
time: 0.565 s   coherence checking
time: 8.953 s   type checking
time: 0.176 s   const marking
time: 0.050 s   const checking
time: 0.401 s   privacy checking
time: 0.063 s   effect checking
time: 0.032 s   loop checking
time: 1.291 s   compute moves
time: 0.172 s   match checking
time: 0.249 s   liveness checking
time: 0.831 s   borrow checking
time: 0.121 s   kind checking
time: 0.013 s   reachability checking
time: 0.179 s   death checking
time: 0.503 s   lint checking
time: 14.385 s  translation
  time: 4.495 s llvm function passes
  time: 92.234 s    llvm module passes
  time: 51.172 s    codegen passes
time: 150.809 s LLVM passes
  time: 2.542 s running linker
time: 15.109 s  linking
```

BUT accesses are much more cache friendly. In fact, if the probe
sequence length is below 8, only two cache lines worth of hashes will be
pulled into cache. This is unlike the old version which would have to
stride over the stoerd keys and values, and would be more cache
unfriendly the bigger the stored values got.

And did you notice the higher load factor? We can now reasonably get a
load factor of 0.9 with very good performance.

Please review this very closely. This is my first major contribution to Rust. Sorry for the ugly diff!

rustuv: Fix a use-after-free in TTY failure

If a TTY fails to get initialized, it still needs to have uv_close invoked on
it. This fixes the problem by constructing the TtyWatcher struct before the call
to uv_tty_init. The struct has a destructor on it which will close the handle
properly.

Closes #12666

rustc: Remove matching on ~str from the language

The `~str` type is not long for this world as it will be superseded by the
soon-to-come DST changes for the language. The new type will be
`~Str`, and matching over the allocation will no longer be supported.
Matching on `&str` will continue to work, in both a pre and post DST world.

Performance-oriented hashtable.

Previously, rust's hashtable was totally unoptimized. It used an Option
per key-value pair, and used very naive open allocation.

The old hashtable had very high variance in lookup time. For an example,
see the 'find_nonexisting' benchmark below. This is fixed by keys in
'lucky' spots with a low probe sequence length getting their good spots
stolen by keys with long probe sequence lengths. This reduces hashtable
probe length variance, while maintaining the same mean.

Also, other optimization liberties were taken. Everything is as cache
aware as possible, and this hashtable should perform extremely well for
both large and small keys and values.

Benchmarks:

comprehensive_old_hashmap         378 ns/iter (+/- 8)
comprehensive_new_hashmap         206 ns/iter (+/- 4)
1.8x faster

old_hashmap_as_queue              238 ns/iter (+/- 8)
new_hashmap_as_queue              119 ns/iter (+/- 2)
2x faster

old_hashmap_insert                172 ns/iter (+/- 8)
new_hashmap_insert                146 ns/iter (+/- 11)
1.17x faster

old_hashmap_find_existing         50 ns/iter (+/- 12)
new_hashmap_find_existing         35 ns/iter (+/- 6)
1.43x faster

old_hashmap_find_notexisting      49 ns/iter (+/- 49)
new_hashmap_find_notexisting      34 ns/iter (+/- 4)
1.44x faster

Memory usage of old hashtable (64-bit assumed):

aligned(8+sizeof(K)+sizeof(V))/0.75 + 6 words

Memory usage of new hashtable:

(aligned(sizeof(K))
+ aligned(sizeof(V))
+ 8)/0.9 + 6.5 words

BUT accesses are much more cache friendly. In fact, if the probe
sequence length is below 8, only two cache lines worth of hashes will be
pulled into cache. This is unlike the old version which would have to
stride over the stoerd keys and values, and would be more cache
unfriendly the bigger the stored values got.

And did you notice the higher load factor? We can now reasonably get a
load factor of 0.9 with very good performance.

auto merge of #12848 : alexcrichton/rust/rollup, r=alexcrichton

Test fixes from rolling up PRs

Closes #12803 (std: Relax an assertion in oneshot selection) r=brson
Closes #12818 (green: Fix a scheduler assertion on yielding) r=brson
Closes #12819 (doc: discuss try! in std::io) r=alexcrichton
Closes #12820 (Use generic impls for `Hash`) r=alexcrichton
Closes #12826 (Remove remaining nolink usages) r=alexcrichton
Closes #12835 (Emacs: always jump the cursor if needed on indent) r=brson
Closes #12838 (Json method cleanup) r=alexcrichton
Closes #12843 (rustdoc: whitelist the headers that get a § on hover) r=alexcrichton
Closes #12844 (docs: add two unlisted libraries to the index page) r=pnkfelix
Closes #12846 (Added a test that checks that unary structs can be mutably borrowed) r=sfackler
Closes #12847 (mk: Fix warnings about duplicated rules) r=nmatsakis

mk: Fix warnings about duplicated rules

The footer.tex rule didn't depend on $(1) of the macro it was being defined in,
so it was getting duplicated, causing many warnings.

Added a test that checks that unary structs can be mutably borrowed.

Closes #11267

docs: add two unlisted libraries to the index page.

rustdoc: whitelist the headers that get a § on hover.

Previously the :hover rules were making the links to the traits/types in
something like

    impl<K: Hash + Eq, V> ... { ... }

be displayed with a trailing `§` when hovered over. This commit
restricts that behaviour to specific headers, i.e. those that are known
to be section headers (like those rendered in markdown doc-comments, and
the "Modules", "Functions" etc. headings).