auto merge of #15809 : pcwalton/rust/dedesugar-for, r=pnkfelix

librustc: Stop desugaring `for` expressions and translate them directly.

This makes edge cases in which the `Iterator` trait was not in scope
and/or `Option` or its variants were not in scope work properly.

This breaks code that looks like:

    struct MyStruct { ... }

    impl MyStruct {
        fn next(&mut self) -> Option<int> { ... }
    }

    for x in MyStruct { ... } { ... }

Change ad-hoc `next` methods like the above to implementations of the
`Iterator` trait. For example:

    impl Iterator<int> for MyStruct {
        fn next(&mut self) -> Option<int> { ... }
    }

Closes #15392.

[breaking-change]

librustc: Stop desugaring `for` expressions and translate them directly.

This makes edge cases in which the `Iterator` trait was not in scope
and/or `Option` or its variants were not in scope work properly.

This breaks code that looks like:

    struct MyStruct { ... }

    impl MyStruct {
        fn next(&mut self) -> Option<int> { ... }
    }

    for x in MyStruct { ... } { ... }

Change ad-hoc `next` methods like the above to implementations of the
`Iterator` trait. For example:

    impl Iterator<int> for MyStruct {
        fn next(&mut self) -> Option<int> { ... }
    }

Closes #15392.

[breaking-change]

auto merge of #15951 : edwardw/rust/issue-15896, r=alexcrichton

Fix ICE when there's an incorrect enum variant constructor in match arm.

Closes #15896.

auto merge of #15945 : treeman/rust/doc-smallint-update, r=alexcrichton

Forgot two methods, but @alexcrichton was a bit too quick to accept  #15943, so I made a new PR.

auto merge of #15779 : alexcrichton/rust/no-nul-terminator, r=pcwalton

Apparently the default getFile implementation for a memory buffer in LLVM ends
up requiring a null terminator at the end of the file. This isn't true a good
bit of the time apparently on OSX. There have been a number of failed
nightly/snapshot builds recently with this strange assertion.

This modifies the calls to MemoryBuffer::getFile to explicitly not ask for a
null terminator.

rustllvm: Don't require null terminators in files

Apparently the default getFile implementation for a memory buffer in LLVM ends
up requiring a null terminator at the end of the file. This isn't true a good
bit of the time apparently on OSX. There have been a number of failed
nightly/snapshot builds recently with this strange assertion.

This modifies the calls to MemoryBuffer::getFile to explicitly not ask for a
null terminator.

auto merge of #15424 : TeXitoi/rust/relicense-shootout-threadring, r=brson

Everyone agreed.

Related to #14248, close #15328

@brson OK?

Fix #15896

Fix ICE when there's an incorrect enum variant constructor in match arm.

Closes #15896.

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

Test fixes from the rollup

Closes #15807 (Deprecate some unsafe functions in `str::raw` and remove `OwnedStr` trait)
Closes #15859 (Implement `Show` for `CString` and fix warning compiling tests for libcollections)
Closes #15911 (Updated LLVM for iOS)
Closes #15925 (libsyntax: Remove `~self` and `mut ~self` from the language.)
Closes #15930 (Add examples for Checked[Add|Sub|Mul|Div])
Closes #15933 (rustdoc: make table of contents optional)
Closes #15937 (librustc: Make bare functions implement the `FnMut` trait.)
Closes #15938 (librustc: Check structure constructors against their types.)
Closes #15939 (rustdoc: Add a --crate-name option)
Closes #15942 (Document trie collections)
Closes #15943 (Document SmallIntMap)

Document update and update_with_key in SmallIntMap.

Move update above for better docs progression.

Document SmallIntMap with examples.

Format documentation for SmallIntMap.

Main examples for TrieSet and TrieMap.

Document TrieSet and TrieMap methods.

rustdoc: Add a --crate-name option

Like rustc, this is required by cargo to build documentation.

librustc: Check structure constructors against their types.

This breaks code like:

    struct Point<T> {
        x: T,
        y: T,
    }

    let pt = Point::<bool> {
        x: 1,
        y: 2,
    };

Change this code to not contain a type error. For example:

    let pt = Point::<int> {
        x: 1,
        y: 2,
    };

Closes #9620.
Closes #15875.

[breaking-change]

librustc: Make bare functions implement the `FnMut` trait.

This is done entirely in the libraries for functions up to 16 arguments.
A macro is used so that more arguments can be easily added if we need.
Note that I had to adjust the overloaded call algorithm to not try
calling the overloaded call operator if the callee is a built-in
function type, to prevent loops.

Closes #15448.

rustdoc: make table of contents optional

rustdoc currently determines whether to produce a table of
contents (along with numbered sections) from the input type: yes for
markdown input, no for Rust input. This commit adds a flag to disable
the table of contents for markdown input, which is useful for embedding
the output in a larger context.

Add examples for Checked[Add|Sub|Mul|Div]

libsyntax: Remove `~self` and `mut ~self` from the language.

This eliminates the last vestige of the `~` syntax.

Instead of `~self`, write `self: Box<TypeOfSelf>`; instead of `mut
~self`, write `mut self: Box<TypeOfSelf>`, replacing `TypeOfSelf` with
the self-type parameter as specified in the implementation.

Closes #13885.

[breaking-change]

Updated LLVM for iOS

There should be no more problems during SjLj pass

Add a null pointer check to CString::new

This also removes checks in other methods of `CString`

Breaking changes:
* `CString::new` now fails if `buf` is null. To avoid this add a check
before creatng a new `CString` .
* The `is_null` and `is_not_null` methods are deprecated, because a
`CString` cannot be null.
* Other methods which used to fail if the `CString` was null do not fail anymore

[breaking-change]

Implement Show for CString

We use use `from_utf8_lossy` to convert it to a MaybeOwned string, to
avoid failing in case the CString contains invalid UTF-8

Fix deprecation warning in deque.rs

Add `string::raw::from_buf`

Fix travis errors

Deprecated `String::from_raw_parts`

Replaced by `string::raw::from_parts`

[breaking-change]

Deprecated `str::raw::from_buf_len`

Replaced by `string::raw::from_buf_len`

[breaking-change]

Deprecated `str::raw::from_byte`

Use `string:raw::from_utf8` instead

[breaking-change]

Deprecated `str::raw::from_utf8_owned`

Replaced by `string::raw::from_utf8`

[breaking-change]

Deprecated `str::raw::from_c_str`

Use `string::raw::from_buf` instead

[breaking-change]

Remove OwnedStr trait

This trait was only implemented by `String`. It provided the methods
`into_bytes` and `append`, both of which **are already implemented as normal
methods** of `String` (not as trait methods). This change improves the
consistency of strings.

This shouldn't break any code, except if somebody has implemented
`OwnedStr` for a user-defined type.

auto merge of #15922 : poiru/rust/remove-whitespace-mk-backslash, r=brson

The alignment of the line continuation backslashes is rather inconsistent. These commits solve that by removing the extra whitespace and adding a space where there previously was none. An alternative solution would be to fix the alignment.

auto merge of #15856 : treeman/rust/doc-priorityqueue, r=huonw

Add examples to methods.

auto merge of #15921 : dotdash/rust/match_lifetimes, r=pcwalton

The allocas used in match expression currently don't get good lifetime
markers, in fact they only get lifetime start markers, because their
lifetimes don't match to cleanup scopes.

While the bindings themselves are bog standard and just need a matching
pair of start and end markers, they might need them twice, once for a
guard clause and once for the match body.

The __llmatch alloca OTOH needs a single lifetime start marker, but
when there's a guard clause, it needs two end markers, because its
lifetime ends either when the guard doesn't match or after the match
body.

With these intrinsics in place, LLVM can now, for example, optimize
code like this:

````rust
enum E {
  A1(int),
  A2(int),
  A3(int),
  A4(int),
}

pub fn variants(x: E) {
  match x {
    A1(m) => bar(&m),
    A2(m) => bar(&m),
    A3(m) => bar(&m),
    A4(m) => bar(&m),
  }
}
````

To a single call to bar, using only a single stack slot. It still fails
to eliminate some of checks.

````gas
.Ltmp5:
.cfi_def_cfa_offset 16
movb (%rdi), %al
testb %al, %al
je .LBB3_5
movzbl %al, %eax
cmpl $1, %eax
je .LBB3_5
cmpl $2, %eax
.LBB3_5:
movq 8(%rdi), %rax
movq %rax, (%rsp)
leaq (%rsp), %rdi
callq _ZN3bar20hcb7a0d8be8e17e37daaE@PLT
popq %rax
retq
````

Refs #15665

Document PriorityQueue.

Move contructors to the top of PriorityQueue.

auto merge of #15909 : colemickens/rust/patch-3, r=alexcrichton

Tested this on the playground, the range specifies range(0u, 3), so it should be okay to remove this cast.

auto merge of #15862 : jakub-/rust/issue-15774, r=alexcrichton

Fixed #15774.

auto merge of #15781 : alexcrichton/rust/issue-15758, r=bblum

Semaphores are not currently designed to handle this case correctly, leading to
very strange behavior. Semaphores as written are intended to count *resources*
and it's not possible to have a negative number of resources.

This alters the behavior and documentation to note that the task will be failed
if the initial count is 0.

Closes #15758

auto merge of #15407 : sneves/rust/master, r=aturon

At the moment, writing generic functions for integer types that involve shifting is rather verbose. For example, a function at shifts an integer left by 1 currently requires

    use std::num::One;
    fn f<T: Int>(x : T) -> T {
        x << One::one()
    }

If the shift amount is not 1, it's even worse:

    use std::num::FromPrimitive;
    fn f<T: Int + FromPrimitive>(x: T) -> T {
        x << FromPrimitive::from_int(2).unwrap()
    }

This patch allows the much simpler implementation

    fn f<T: Int>(x: T) -> T {
        x << 2
    }

It accomplishes this by changing the built-in integer types (and the `Int` trait) to implement `Shl<uint, T>` instead of `Shl<T, T>` as it currently is defined. Note that the internal implementations of `shl` already cast the right-hand side to `uint`. `BigInt` also implements `Shl<uint, BigInt>`, so this increases consistency.

All of the above applies similarly to right shifts, i.e., `Shr<uint, T>`.

auto merge of #15611 : brson/rust/pushpop, r=alexcrichton

This fixes naming conventions for `push`/`pop` from either end of a structure by partially implementing @erickt's suggestion from https://github.com/rust-lang/rust/issues/10852#issuecomment-30823343, namely:

* push/pop from the 'back' are called `push` and `pop`.
* push/pop from the 'front' are called `push_front` and `pop_front`.
* `push`/`pop` are declared on the `MutableSeq` trait.
* Implement `MutableSeq` for `Vec`, `DList`, and `RingBuf`.
* Add `MutableSeq` to the prelude.

I did not make any further refactorings because there is some more extensive thought that needs to be put into the collections traits. This is an easy first step that should close https://github.com/rust-lang/rust/issues/10852.

I left the `push_back` and `pop_back` methods on `DList` and `RingBuf` deprecated. Because `MutableSeq` is in the prelude it shouldn't break many, but it is a breaking change.

Just land already

Remove stray llvmdeps.rs

collections: Tweak docs for push

Remove kludgy imports from vec! macro

collections: Deprecate shift/unshift

Use insert/remove instead.

collections: Make push_back/pop_back default methods

vim: Add MutableSeq

collections: Move push/pop docs to MutableSeq

Convert some push_back users to push

collections: Deprecate push_back/pop_back

collections: Move push/pop to MutableSeq

Implement for Vec, DList, RingBuf. Add MutableSeq to the prelude.

Since the collections traits are in the prelude most consumers of
these methods will continue to work without change.

[breaking-change]

Parser: Global single-segment paths should be represented as PatEnum

Fixed #15774.

auto merge of #15928 : brson/rust/dist, r=alexcrichton,alexcrichton

The first commit reverts a similar fix that only solves the `make install` case. This adds the `--enable-dist-host-only` flag to configure to preserve the old behavior, which the nightly bots rely on. The bots will need to be updated soon after this lands (or they will ~double in size).

Closes https://github.com/rust-lang/rust/issues/15711

mk: Have the various flavors of 'dist' install all targets by default

Closes #15711

configure: Add --enable-dist-host-only flag

This preserves the current behavior of `make dist` where we only
distribute bins for the host architecture. The bots need this.

auto merge of #15902 : nham/rust/hash_triemap, r=alexcrichton

cc #15294

mk: Add space before line continuation backslash

mk: Remove extra whitespace before line continuation backslashes

Improve usage of lifetime intrinsics in match expressions

The allocas used in match expression currently don't get good lifetime
markers, in fact they only get lifetime start markers, because their
lifetimes don't match to cleanup scopes.

While the bindings themselves are bog standard and just need a matching
pair of start and end markers, they might need them twice, once for a
guard clause and once for the match body.

The __llmatch alloca OTOH needs a single lifetime start marker, but
when there's a guard clause, it needs two end markers, because its
lifetime ends either when the guard doesn't match or after the match
body.

With these intrinsics in place, LLVM can now, for example, optimize
code like this:

````rust
enum E {
  A1(int),
  A2(int),
  A3(int),
  A4(int),
}

pub fn variants(x: E) {
  match x {
    A1(m) => bar(&m),
    A2(m) => bar(&m),
    A3(m) => bar(&m),
    A4(m) => bar(&m),
  }
}
````

To a single call to bar, using only a single stack slot. It still fails
to eliminate some of checks.

````gas
.Ltmp5:
.cfi_def_cfa_offset 16
movb (%rdi), %al
testb %al, %al
je .LBB3_5
movzbl %al, %eax
cmpl $1, %eax
je .LBB3_5
cmpl $2, %eax
.LBB3_5:
movq 8(%rdi), %rax
movq %rax, (%rsp)
leaq (%rsp), %rdi
callq _ZN3bar20hcb7a0d8be8e17e37daaE@PLT
popq %rax
retq
````

auto merge of #15749 : vhbit/rust/treemap-doc-fixes, r=alexcrichton

1. Removed obsolete comment regarding recursive/iteration implementations of tree_find_with/tree_find_mut_with
2. Replaced easy breakable find_with example with simpler one (which only removes redundant allocation during search)

auto merge of #15910 : sfackler/rust/nogc, r=cmr

auto merge of #15900 : tbu-/rust/pr_numcleanup, r=kballard

This removes the special casing for `float`s where it was not necessary, as
`-0.0 == 0.0`.

TreeMap examples fixes

1. Removed obsolete comment regarding recursive/iteration implementations of tree_find_with/tree_find_mut_with
2. Replaced easy breakable find_with example with simpler one (which only removes redundant allocation during search)

auto merge of #15899 : aochagavia/rust/guide, r=kballard

The removed code caused confusion because it is not clear that the type of `y` is actually `()`

Remove ancient GC cfg flags

Remove unnecessary cast from intro

auto merge of #15897 : Gankro/rust/it-docs, r=kballard

I found these things to be ambiguous, or at least worth stating explicitly to reduce the amount a user/developer needs to think about the API.

Revert "Made 'make install' include libs for additional targets"

This reverts commit 87334fb05ff2a665419241d877c13d6c4770a3f4.

Conflicts:
mk/install.mk

auto merge of #15272 : jakub-/rust/issue-13041, r=pcwalton

Fixes #13041.

Add Drop support for enums

Fixes #13041.

auto merge of #15894 : treeman/rust/vec-doc, r=alexcrichton

Fill in examples for missing methods. Opt for `vec![]` instead of `vec!()`.

Implement PartialEq, Eq for TrieMap, TrieSet

Derive Hash for TrieMap and TrieSet

auto merge of #15869 : alexcrichton/rust/issue-15828, r=kballard

Closes #15828

Clean up some trait impls in core::num.

This removes the special casing for `float`s where it was not necessary, as
`-0.0 == 0.0`.

Remove misleading code example from The Guide

The removed code caused confusion because it is not clear that the type of `y` is actually `()`

clarifying iterator trait documentation

auto merge of #15863 : dotdash/rust/lifetimes3, r=alexcrichton

Lifetime intrinsics help to reduce stack usage, because LLVM can apply
stack coloring to reuse the stack slots of dead allocas for new ones.

For example these functions now both use the same amount of stack, while
previous `bar()` used five times as much as `foo()`:

````rust
fn foo() {
  println("{}", 5);
}

fn bar() {
  println("{}", 5);
  println("{}", 5);
  println("{}", 5);
  println("{}", 5);
  println("{}", 5);
}
````

On top of that, LLVM can also optimize out certain operations when it
knows that memory is dead after a certain point. For example, it can
sometimes remove the zeroing used to cancel the drop glue. This is
possible when the glue drop itself was already removed because the
zeroing dominated the drop glue call. For example in:

````rust
pub fn bar(x: (Box<int>, int)) -> (Box<int>, int) {
    x
}
````

With optimizations, this currently results in:

````llvm
define void @_ZN3bar20h330fa42547df8179niaE({ i64*, i64 }* noalias nocapture nonnull sret, { i64*, i64 }* noalias nocapture nonnull) unnamed_addr #0 {
"_ZN29_$LP$Box$LT$int$GT$$C$int$RP$39glue_drop.$x22glue_drop$x22$LP$1347$RP$17h88cf42702e5a322aE.exit":
  %2 = bitcast { i64*, i64 }* %1 to i8*
  %3 = bitcast { i64*, i64 }* %0 to i8*
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %3, i8* %2, i64 16, i32 8, i1 false)
  tail call void @llvm.memset.p0i8.i64(i8* %2, i8 0, i64 16, i32 8, i1 false)
  ret void
}
````

But with lifetime intrinsics we get:

````llvm
define void @_ZN3bar20h330fa42547df8179niaE({ i64*, i64 }* noalias nocapture nonnull sret, { i64*, i64 }* noalias nocapture nonnull) unnamed_addr #0 {
"_ZN29_$LP$Box$LT$int$GT$$C$int$RP$39glue_drop.$x22glue_drop$x22$LP$1347$RP$17h88cf42702e5a322aE.exit":
  %2 = bitcast { i64*, i64 }* %1 to i8*
  %3 = bitcast { i64*, i64 }* %0 to i8*
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %3, i8* %2, i64 16, i32 8, i1 false)
  tail call void @llvm.lifetime.end(i64 16, i8* %2)
  ret void
}
````

Fixes #15665

auto merge of #15857 : treeman/rust/doc-dijkstra-example, r=alexcrichton

I wanted to have a slightly larger example compared to the method examples, but I'm unsure how it worked out.

Feedback would nice.

Main example for priority queue using dijkstra's algorithm.

auto merge of #15888 : mprobinson/rust/rustdoc-fixes, r=cmr

Allow "rustdoc --passes list" to work without specifying input files,
as shown in the examples section of the man page.

auto merge of #15884 : steveklabnik/rust/guide_fix_headings, r=huonw

I screwed this up a while back, and now that I have no outstanding PRs, it's a good time to fix this.

doc: Normalize example style

Remove unnecessary `use std::vec::Vec`. Use ``` code blocks
with rust as default instead of spelling it out.

doc: Vec::from_raw_parts.

Also more explicit raw pointer handling in unsafe examples.

auto merge of #15876 : brson/rust/failfat, r=pcwalton

Adds a new runtime unwinding function that encapsulates the printing of the words "explicit failure" when `fail!()` is called w/o arguments.

The before/after optimized assembly:

```
        leaq    "str\"str\"(1412)"(%rip), %rax
        movq    %rax, 24(%rsp)
        movq    $16, 32(%rsp)
        leaq    "str\"str\"(1413)"(%rip), %rax
        movq    %rax, 8(%rsp)
        movq    $19, 16(%rsp)
        leaq    24(%rsp), %rdi
        leaq    8(%rsp), %rsi
        movl    $11, %edx
        callq   _ZN6unwind12begin_unwind21h15836560661922107792E
```

```
        leaq    "str\"str\"(1369)"(%rip), %rax
        movq    %rax, 8(%rsp)
        movq    $19, 16(%rsp)
        leaq    8(%rsp), %rdi
        movl    $11, %esi
        callq   _ZN6unwind31begin_unwind_no_time_to_explain20hd1c720cdde6a116480dE@PLT
```

Before/after filesizes:

rwxrwxr-x 1 brian brian 21479503 Jul 20 22:09 stage2-old/lib/librustc-4e7c5e5c.so
rwxrwxr-x 1 brian brian 21475415 Jul 20 22:30 x86_64-unknown-linux-gnu/stage2/lib/librustc-4e7c5e5c.so

This is the lowest-hanging fruit in the fail-bloat wars. Further fixes are going to require harder tradeoffs.

r? @pcwalton

doc: Fill vec documentation with examples.

Add more useful functions to main example.

auto merge of #15871 : dotdash/rust/unnamed_fmtstr, r=pcwalton

doc: Use vec![] instead of vec!() in Vec.

Emit LLVM lifetime intrinsics to improve stack usage and codegen in general

Lifetime intrinsics help to reduce stack usage, because LLVM can apply
stack coloring to reuse the stack slots of dead allocas for new ones.

For example these functions now both use the same amount of stack, while
previous `bar()` used five times as much as `foo()`:

````rust
fn foo() {
  println("{}", 5);
}

fn bar() {
  println("{}", 5);
  println("{}", 5);
  println("{}", 5);
  println("{}", 5);
  println("{}", 5);
}
````

On top of that, LLVM can also optimize out certain operations when it
knows that memory is dead after a certain point. For example, it can
sometimes remove the zeroing used to cancel the drop glue. This is
possible when the glue drop itself was already removed because the
zeroing dominated the drop glue call. For example in:

````rust
pub fn bar(x: (Box<int>, int)) -> (Box<int>, int) {
    x
}
````

With optimizations, this currently results in:

````llvm
define void @_ZN3bar20h330fa42547df8179niaE({ i64*, i64 }* noalias nocapture nonnull sret, { i64*, i64 }* noalias nocapture nonnull) unnamed_addr #0 {
"_ZN29_$LP$Box$LT$int$GT$$C$int$RP$39glue_drop.$x22glue_drop$x22$LP$1347$RP$17h88cf42702e5a322aE.exit":
  %2 = bitcast { i64*, i64 }* %1 to i8*
  %3 = bitcast { i64*, i64 }* %0 to i8*
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %3, i8* %2, i64 16, i32 8, i1 false)
  tail call void @llvm.memset.p0i8.i64(i8* %2, i8 0, i64 16, i32 8, i1 false)
  ret void
}
````

But with lifetime intrinsics we get:

````llvm
define void @_ZN3bar20h330fa42547df8179niaE({ i64*, i64 }* noalias nocapture nonnull sret, { i64*, i64 }* noalias nocapture nonnull) unnamed_addr #0 {
"_ZN29_$LP$Box$LT$int$GT$$C$int$RP$39glue_drop.$x22glue_drop$x22$LP$1347$RP$17h88cf42702e5a322aE.exit":
  %2 = bitcast { i64*, i64 }* %1 to i8*
  %3 = bitcast { i64*, i64 }* %0 to i8*
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %3, i8* %2, i64 16, i32 8, i1 false)
  tail call void @llvm.lifetime.end(i64 16, i8* %2)
  ret void
}
````

Fixes #15665

auto merge of #15867 : cmr/rust/rewrite-lexer4, r=alexcrichton

Fix pretty test

auto merge of #15870 : jakub-/rust/issue-15793, r=alexcrichton

Fixes #15793.

Don't run lexer tests by default

auto merge of #15834 : Kimundi/rust/moved_syntax_env, r=cmr

- Made custom syntax extensions capable of expanding custom macros by moving `SyntaxEnv` into `ExtCtx`
- Added convenience method on `ExtCtx` for getting a macro expander.
- Made a few things private to force only a single way to use them (through `ExtCtx`)
- Removed some ancient commented-out code

Closes #14946

Add a ton of ignore-lexer-test

Shuffle around check-lexer conditions

Break apart long lines in verify.rs