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]

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

cc #15294

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

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.

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

lexer tests: makefile/configure

auto merge of #15217 : steveklabnik/rust/range, r=huonw

Inspired by http://www.reddit.com/r/rust/comments/298js2/what_is_the_rationale_behind_the_second_parameter/

Guide: fix headings

Clarify range's exclusivity.

Inspired by http://www.reddit.com/r/rust/comments/298js2/what_is_the_rationale_behind_the_second_parameter/

Refactoring: Only use `MacroExpander` for expanding outside of
`syntax::ext::expand`

Fix rustdoc --passes list

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

Moved `syntax::ext::base::SyntaxEnv` into `syntax::ext::base::ExtCtx`

Update LLVM to address an issue with range metadata in hoisted loads

Fixes #15793.

Use fewer instructions for `fail!`

Adds a special-case fail function, rustrt::unwind::begin_unwind_no_time_to_explain,
that encapsulates the printing of the words "explicit failure".

The before/after optimized assembly:

```
        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
```

```
        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
```

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

auto merge of #15700 : jakub-/rust/match-fail-removal, r=pcwalton

It's an artifact of the old refutable version of `match` and is no longer necessary.

Allow merging of statics generated by format!()

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

rustc: Append platform exe suffix to output files

Closes #15828

ignore-lexer-test to broken files and remove some tray hyphens

I blame @ChrisMorgan for the hyphens.

Byte/raw binary literal fixes

Refine the tooling, handle comments

First pass at line comment correctness

Add raw string literal ambiguity document

Lexer; subtly wrong; no makefile

Test fixes from the rollup

Closes #15690 (Guide: improve error handling)
Closes #15729 (Guide: guessing game)
Closes #15751 (repair macro docs)
Closes #15766 (rustc: Print a smaller hash on -v)
Closes #15815 (Add unit test for rlibc)
Closes #15820 (Minor refactoring and features in rustc driver for embedders)
Closes #15822 (rustdoc: Add an --extern flag analagous to rustc's)
Closes #15824 (Document Deque trait and bitv.)
Closes #15832 (syntax: Join consecutive string literals in format strings together)
Closes #15837 (Update LLVM to include NullCheckElimination pass)
Closes #15841 (Rename to_str to to_string)
Closes #15847 (Purge #[!resolve_unexported] from the compiler)
Closes #15848 (privacy: Add publically-reexported foreign item to exported item set)
Closes #15849 (fix string in from_utf8_lossy_100_multibyte benchmark)
Closes #15850 (Get rid of few warnings in tests)
Closes #15852 (Clarify the std::vec::Vec::with_capacity docs)

Clarify the std::vec::Vec docs regarding capacity

Get rid of few warnings in tests

fix string in from_utf8_lossy_100_multibyte benchmark

privacy: Add publically-reexported foreign item to exported item set

Close #15740

Don't create reexport module if there are none

Purge !resolve_unexported

Restructure test harness

We now build up a set of modules that reexport everything the test
framework needs, instead of turning off privacy.

Remove useless RefCells

Rename to_str to to_string

Closes #15796.

[breaking-change]

Update LLVM to include NullCheckElimination pass

Fixes #11751

syntax: Join consecutive string literals in format strings together

Emit a single rt::Piece per consecutive string literals. String literals
are split on {{ or }} escapes.

Saves a small amount of static storage and emitted code size.

Simplify and cleanup bitv examples.

Describe BitPositions and TwoBitPositions.

Polish bitv docs.

Enclose None as `None`.

Main bitv example: prime sieve.

Move intersection above difference and symmetric_differance.

So all comes in the order union, intersection, difference and
symmetric_difference.

Document BitvSet.

Document Bitv.

Group union, intersect and difference in Bitv.

Place union as the first function, for consistency.

Move in-place functions below their iterator variants.

Document Deque.

rustdoc: Add an --extern flag analagous to rustc's

This adds an `--extern` flag to `rustdoc` much like the compiler's to
specify the path where a given crate can be found.

Address review feedback

rustc: Allow the crate linked to as 'std' to be customized

This adds the alt_std_name field to the Session's Options type.
I'm using this in an external tool to control which libraries
a crate links to.

rustc: Pass optional additional plugins to compile_input

This provides a way for clients of the rustc library to add
their own features to the pipeline.

rustc: Extract --crate-type parsing to its own function

Helpful for users of rustc as a library.

rustc: Make `monitor` public.

It's harder to run rustc correctly without it.

rlibc: add unit tests

rlibc: fix bug in `memcmp()`

rustc: Print a smaller hash on -v

The long hash just takes up space and you can discover the main hash through the
`rustc --version verbose` command.

repair macro docs

In f1ad425199b0d89dab275a8c8f6f29a73d316f70, I changed the handling
of macros, to prevent macro invocations from occurring in fully expanded
source. Instead, I added a side table. It contained only the
spans of the macros, because this was the only information required
in order to make macro export work.

However, librustdoc was also affected by this change, since it
extracts macro information in a similar way. As a result of the earlier
change, exported macros were no longer documented.

In order to repair this, I've adjusted the side table to contain whole
items, rather than just the spans.

Guessing game explanation

We now build the game at the end of the first section.

I wanted to do it as we went along, but it's too hard with these fundamentals
not in place. The rest will do the 'as we go' approach, but I think this is
better.

Guide: improve error handling

auto merge of #15450 : chris-morgan/rust/vim-misc-2014-07-04, r=kballard

Remove runtime failure from pattern matching

It's an artifact of the old refutable version of `match`
and is no longer necessary.

Fix :syn-include usage of Vim filetype.

Here’s what the Vim manual says in *:syn-include*:

    :sy[ntax] include [@{grouplist-name}] {file-name}

All syntax items declared in the included file will have the
"contained" flag added.  In addition, if a group list is
specified, all top-level syntax items in the included file will
be added to that list.

We had two rules for `rustModPath`, one `contained` and the other not.
The effect was that the second (now renamed to `rustModPathInUse`) was
being included in the group list, and thus that all identifiers were
being highlighted as `Include`, which is definitely not what we wanted.

Highlight $(…)* and $foo in Vim.

auto merge of #15810 : SimonSapin/rust/base64-from-bytes, r=alexcrichton

The algorithm was already based on bytes internally.

Also use byte literals instead of casting u8 to char for matching.

[breaking-change] The `InvalidBase64Character` variant of the `FromBase64Error` enum was renamed to `InvalidBase64Byte`, and contains a `u8` instead of a `char`.

r? @alexcrichton

auto merge of #15808 : jakub-/rust/use-mod, r=alexcrichton

Implements RFC #168.

auto merge of #15805 : Sawyer47/rust/issue-8709, r=alexcrichton

Closes #8709