create a sensible comparison trait hierarchy

* `Ord` inherits from `Eq`
* `TotalOrd` inherits from `TotalEq`
* `TotalOrd` inherits from `Ord`
* `TotalEq` inherits from `Eq`

This is a partial implementation of #12517.

auto merge of #12753 : huonw/rust/vec-macro, r=cmr

If no arguments are given to `vec!` then no pushes are emitted and
so the compiler (rightly) complains that the mutability of `temp` is
never used.

This behaviour is rather annoying for users.

auto merge of #12750 : liigo/rust/De-extern-mod, r=alexcrichton

rename ast::ViewItemExternMod to ast::ViewItemExternCrate
rename rustdoc::clean::ExternMod to rustdoc::clean::ExternCrate
because `extern mod` is out.

rename ast::ViewItemExternMod to ast::ViewItemExternCrate, and clean::ExternMod to clean::ExternCrate

auto merge of #12749 : tedhorst/rust/master, r=huonw

Minor change to the FVN hashing function based on recommendation on: http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash

cc @alexcrichton

change FVN hash function to the FVN-1a variant

std: stop `vec!()` warning about unused mutability.

If no arguments are given to `vec!` then no pushes are emitted and
so the compiler (rightly) complains that the mutability of `temp` is
never used.

This behaviour is rather annoying for users.

auto merge of #12746 : alexcrichton/rust/issue-12743, r=brson

The arguments were accidentally swapped in the wrong order.

Closes #12743

auto merge of #12635 : alexcrichton/rust/speedy-hash, r=brson

This leverages the new hashing framework and hashmap implementation to provide a
much speedier hashing algorithm for node ids and def ids. The hash algorithm
used is currentl FNV hashing, but it's quite easy to swap out.

I originally implemented hashing as the identity function, but this actually
ended up in slowing down rustc compiling libstd from 8s to 13s. I would suspect
that this is a result of a large number of collisions.

With FNV hashing, we get these timings (compiling with --no-trans, in seconds):

|           |  before  |  after  |
|-----------|---------:|--------:|
| libstd    |   8.324  |  6.703  |
| stdtest   |  47.674  | 46.857  |
| libsyntax |   9.918  |  8.400  |

syntax: Conditionally deriving(Hash) with Writers

If #[feature(default_type_parameters)] is enabled for a crate, then
deriving(Hash) will expand with Hash<W: Writer> instead of Hash<SipState> so
more hash algorithms can be used.

collections: Correct with_capacity_and_hasher

The arguments were accidentally swapped in the wrong order.

Closes #12743

rustc: Move to FNV hashing for node/def ids

This leverages the new hashing framework and hashmap implementation to provide a
much speedier hashing algorithm for node ids and def ids. The hash algorithm
used is currentl FNV hashing, but it's quite easy to swap out.

I originally implemented hashing as the identity function, but this actually
ended up in slowing down rustc compiling libstd from 8s to 13s. I would suspect
that this is a result of a large number of collisions.

With FNV hashing, we get these timings (compiling with --no-trans, in seconds):

|           |  before  |  after  |
|-----------|---------:|--------:|
| libstd    |   8.324  |  6.703  |
| stdtest   |  47.674  | 46.857  |
| libsyntax |   9.918  |  8.400  |

auto merge of #12738 : alexcrichton/rust/needstest, r=brson,just

Closes #6738
Closes #7061
Closes #7899
Closes #9719
Closes #10028
Closes #10228
Closes #10401
Closes #11192
Closes #11508
Closes #11529
Closes #11873
Closes #11925

auto merge of #12737 : alexcrichton/rust/issue-12736, r=brson

Turns out sundown has already escaped this content for us, so there's no need
for us to escape it again.

Closes #12736

auto merge of #12732 : klutzy/rust/this-is-windows, r=alexcrichton

On Windows, `LLVMRustGetLastError()` may return non-utf8 mojibake string
if system uses non-English locale. It caused ICE when llvm fails.
This patch doesn't fix the real problem, but just make rustc not die.

test: Add some tests for closed issues

Closes #6738
Closes #7061
Closes #7899
Closes #9719
Closes #10028
Closes #10228
Closes #10401
Closes #11192
Closes #11508
Closes #11529
Closes #11873
Closes #11925

auto merge of #12720 : iliekturtles/rust/master, r=alexcrichton

rustdoc: Don't escape contents of headers

Turns out sundown has already escaped this content for us, so there's no need
for us to escape it again.

Closes #12736

Added missing possessive apostrophe.

rustc: Get LLVM error message safely

On Windows, `LLVMRustGetLastError()` may return non-utf8 mojibake string
if system uses non-English locale. It caused ICE when llvm fails.
This patch doesn't fix the real problem, but just make rustc not die.

auto merge of #12727 : lifthrasiir/rust/buffalo-buffalo, r=huonw

Cosmetic changes at best, but there are so many such typos that I couldn't ignore them. :) Some occurrences of typos are linked to the generated documentations but no changes should break the builds.

auto merge of #12726 : alexcrichton/rust/travis, r=brson

This version is slightly more up to date and is closer to the 3.5 that we're
using. This also updates the travis config to have a build matrix which tests
rust against LLVM 3.3 and 3.4. For pull requests only LLVM 3.4 is tested to
reduce the load on travis.

This is mostly just fluff, there's no real reason to gate rust on these results,
it's more of just a nice thing to know when we break compatibility with LLVM 3.3
and 3.4 (and eventually 3.5). This turns off notifications of failed commits
(which are sent out for pushes to master).

fix typos with with repeated words, just like this sentence.

auto merge of #12719 : alexcrichton/rust/fix-llvm-33, r=brson

The llvm.copysign and llvm.round intrinsics weren't added until LLVM 3.4, so if
we're on LLVM 3.3 we lower these to calls in libm instead of LLVM intrinsics.

This should fix our travis failures.

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

This PR brings back limited debuginfo which allows for nice backtraces and breakpoints, but omits any info about variables and types.

The `-g` and `--debuginfo` command line options have been extended to take an optional argument:
`-g0` means no debug info.
`-g1` means line-tables only.
`-g2` means full debug info.

Specifying `-g` without argument is equivalent to `-g2`.

Fixes #12280

auto merge of #12705 : alexcrichton/rust/issue-12692, r=brson

Details are in the commit messages, but this closes a few issues seen with `libnative` recently.

travis: Use LLVM 3.4 instead of LLVM 3.3

This version is slightly more up to date and is closer to the 3.5 that we're
using. This also updates the travis config to have a build matrix which tests
rust against LLVM 3.3 and 3.4. For pull requests only LLVM 3.4 is tested to
reduce the load on travis.

This is mostly just fluff, there's no real reason to gate rust on these results,
it's more of just a nice thing to know when we break compatibility with LLVM 3.3
and 3.4 (and eventually 3.5). This turns off notifications of failed commits
(which are sent out for pushes to master).

auto merge of #12687 : alexcrichton/rust/issue-12681, r=huonw

This commit adds a appear-on-over link to all section headers to generated
documentation. Each header also receives an id now, even those generated through
markdown. The purpose of this is to provide easy to link to sections.

This modifies the default header markdown generation because the default id
added looks like "toc_NN" which is difficult to reconcile among all sections (by
default each section gets a "toc_0" id), and it's also not very descriptive of
where you're going.

This chooses to adopt the github-style anchors by taking the contents of the
title and hyphen-separating them (after lower casing).

Closes #12681

debuginfo: Add test case for limited debuginfo

debuginfo: Expose limited debuginfo in command line options

debuginfo: Re-introduce the notion of line-table-only debuginfo.

rustdoc: Add anchors to section headers

This commit adds a appear-on-over link to all section headers to generated
documentation. Each header also receives an id now, even those generated through
markdown. The purpose of this is to provide easy to link to sections.

This modifies the default header markdown generation because the default id
added looks like "toc_NN" which is difficult to reconcile among all sections (by
default each section gets a "toc_0" id), and it's also not very descriptive of
where you're going.

This chooses to adopt the github-style anchors by taking the contents of the
title and hyphen-separating them (after lower casing).

Closes #12681

auto merge of #12703 : jld/rust/issue-8506, r=alexcrichton

Closes #8506.

std: Move libnative task count bookkeeping to std

When using tasks in Rust, the expectation is that the runtime does not exit
before all tasks have exited. This is enforced in libgreen through the
`SchedPool` type, and it is enforced in libnative through a `bookkeeping` module
and a global count/mutex pair. Unfortunately, this means that a process which
originates with libgreen will not wait for spawned native tasks.

In order to fix this problem, the bookkeeping module was moved from libnative to
libstd so the runtime itself can wait for native tasks to exit. Green tasks do
not manage themselves through this bookkeeping module, but native tasks will
continue to manage themselves through this module.

Closes #12684

Fix ICE on statics with fancy nullable enums.

Closes #8506.

The `trans::adt` code for statics uses fields with `C_undef` values to
insert alignment padding (because LLVM's own alignment padding isn't
always sufficient for aggregate constants), and assumes that all fields
in the actual Rust value are represented by non-undef LLVM values, to
distinguish them from that padding.

But for nullable pointer enums, if non-null variant has fields other
than the pointer used as the discriminant, they would be set to undef in
the null case, to reflect that they're never accessed.

To avoid the obvious conflict between these two items, the latter undefs
were wrapped in unary LLVM structs to distinguish them from the former
undefs.  Except this doesn't actually work -- LLVM, not unreasonably,
treats the "wrapped undef" as a regular undef.

So this commit just sets all fields to null in the null pointer case of
a nullable pointer enum static, because the other fields don't really
need to be undef in the first place.

rustc: Fix support for LLVM 3.3

The llvm.copysign and llvm.round intrinsics weren't added until LLVM 3.4, so if
we're on LLVM 3.3 we lower these to calls in libm instead of LLVM intrinsics.

This should fix our travis failures.

auto merge of #12718 : thestinger/rust/min_max, r=alexcrichton

stats: fix handling of NaN in `min` and `max`

The `cmp::min` and `cmp::max` functions are not correct with partially
ordered values. #12712

add tests for `min` and `max` from `Float`

auto merge of #12715 : dmski/rust/no-extern-fn-pat, r=alexcrichton

Fixes #10877

There was another PR which attempted to fix this in the parser (#11804) and which was closed due to inactivity.
This PR modifies typeck instead (as suggested in #11804), which indeed seems to be simpler than modifying the parser and allows for a better error message.

Disallowed patterns in extern fn declarations.

Closes #10877

auto merge of #12711 : edwardw/rust/mtwt, r=pcwalton

- Moves mtwt hygiene code into its own file
- Fixes FIXME's which leads to ~2x speed gain in expansion pass
- It is now @-free

auto merge of #12709 : aepsil0n/rust/update_man_version, r=alexcrichton

Just realized that these were quite outdated and quickly fixed it. I have to admit that I did not run the test suite on this one though…

native: Fix usage of a deallocated mutex

When the timer_helper thread exited, it would attempt to re-acquire the global
task count mutex, but the mutex had previously been deallocated, leading to
undefined behavior of the mutex, and in some cases deadlock.

Another mutex is used to coordinate shutting down the timer helper thread.

Closes #12699

native: Move from usleep() to nanosleep()

Using nanosleep() allows us to gracefully recover from EINTR because on error it
fills in the second parameter with the remaining time to sleep.

Closes #12689

native: Stop using readdir()

This function is not threadsafe, and is deprecated in favor of the threadsafe
readdir_r variant.

Closes #12692

auto merge of #12700 : thestinger/rust/float, r=cmr

consistently use LLVM floating point intrinsics

add correct floating point `min` and `max` methods.

The `std::cmp` functions are not correct for floating point types.

`min(NaN, 2.0)` and `min(2.0, NaN)` return different values, because
these functions assume a total order. Floating point types need special
`min`, `max` and `clamp` functions.

Refactor and fix FIXME's in mtwt hygiene code

- Moves mtwt hygiene code into its own file
- Fixes FIXME's which leads to ~2x speed gain in expansion pass
- It is now @-free

auto merge of #12708 : SimonSapin/rust/patch-6, r=huonw

Feel free to reject this if I’m mistaken, but the `count` in the for loop does look like it’s going from 0 to `end`.

Update version and date info in man pages

Both for rustc and rustdoc the man pages contained out-of-date version info.

Str::slice_chars() is O(end), not O(end - begin)

auto merge of #12491 : eddyb/rust/deref, r=nikomatsakis

Add the `Deref` and `DerefMut` traits and implement overloading explicit dereferences.

auto merge of #12300 : DaGenix/rust/uppercase-variable-lint, r=alexcrichton

I added a new lint for variables whose names contain uppercase characters, since, by convention, variable names should be all lowercase. What motivated me to work on this was when I ran into something like the following:

```rust
use std::io::File;
use std::io::IoError;

fn main() {
    let mut f = File::open(&Path::new("/something.txt"));
    let mut buff = [0u8, ..16];
    match f.read(buff) {
        Ok(cnt) => println!("read this many bytes: {}", cnt),
        Err(IoError{ kind: EndOfFile, .. }) => println!("Got end of file: {}", EndOfFile.to_str()),
    }
}
```

I then got compile errors when I tried to add a wildcard match pattern at the end which I found very confusing since I believed that the 2nd match arm was only matching the EndOfFile condition. The problem is that I hadn't imported io::EndOfFile into the local scope. So, I thought that I was using EndOfFile as a sub-pattern, however, what I was actually doing was creating a new local variable named EndOfFile. This lint makes this error easier to spot by providing a warning that the variable name EndOfFile contains a uppercase characters which provides a nice hint as to why the code isn't doing what is intended.

The lint warns on local bindings as well:

```rust
let Hi = 0;
```

And also struct fields:

```rust
struct Something {
    X: uint
}
```

Emit the uppercase variable lint for struct fields that have names with uppercase characters

Allow uppercase_variables in libstd/libc.rs

auto merge of #12671 : nick29581/rust/expand, r=sfackler

Fixes a regression from #4913 which causes items to be exanded with spans lacking expn_info from the context's current backtrace.

auto merge of #12688 : alexcrichton/rust/fix-some-link-args, r=brson

Linker argument order with respect to libraries is important enough that we
shouldn't be attempting to filter out libraries getting passed through to the
linker. When linking with a native library that has multiple dependant native
libraries, it's useful to have control over the link argument order.

Rename struct fields with uppercase characters in their names to use lowercase

Add lint for variable names that contain uppercase characters

Rename all variables that have uppercase characters in their names to use only lowercase characters

Expand nested items within a backtrace.

Fixes a regression from #4913 which causes items to be exanded with spans lacking expn_info from the context's current backtrace.

auto merge of #12697 : thestinger/rust/vec, r=huonw

This exists for the sake of compatibility during the ~[T] -> Vec<T>
transition. It will be removed in the future.

mark the `map` method on Vec<T> as deprecated

This exists for the sake of compatibility during the ~[T] -> Vec<T>
transition. It will be removed in the future.

auto merge of #12694 : thestinger/rust/mut_iter, r=huonw

This become `Pod` when it was switched to using marker types.

make `MutItems` iterator sound again

This become `Pod` when it was switched to using marker types.

Allow overloading explicit dereferences.

auto merge of #12667 : Kimundi/rust/any_improv, r=cmr

- Added `TraitObject` representation to `std::raw`.
- Added doc to `std::raw`.
- Removed `Any::as_void_ptr()` and `Any::as_mut_void_ptr()`
  methods as they are uneccessary now after the removal of
  headers on owned boxes. This reduces the number of virtual calls needed from 2 to 1.
- Made the `..Ext` implementations work directly with the repr of
  a trait object.
- Removed `Any`-related traits from the prelude.
- Added bench.

Bench before/after:
~~~
7 ns/iter (+/- 0)
4 ns/iter (+/- 0)
~~~

Cleaned up `std::any`

- Added `TraitObject` representation to `std::raw`.
- Added doc to `std::raw`.
- Removed `Any::as_void_ptr()` and `Any::as_mut_void_ptr()`
  methods as they are uneccessary now after the removal of
  headers on owned boxes. This reduces the number of virtual calls needed.
- Made the `..Ext` implementations work directly with the repr of
  a trait object.
- Removed `Any`-related traits from the prelude.

- Added bench for `Any`

auto merge of #12649 : adrientetar/rust/highlight, r=alexcrichton

[Here is](http://adrientetar.legtux.org/cached/rust-doc/to_str.rs.html) an example.

Closes #12648.

@alexcrichton, @huonw

doc: use the newer favicon

rustdoc: tweak highlighting

Implement DerefImm for Rc and DerefImm/DerefMut for RefCell's Ref/RefMut.

Add the DerefImm and DerefMut traits.

auto merge of #12678 : lifthrasiir/rust/pluralize, r=alexcrichton

While we are not yet ready for compiler i18n, this also keeps the error handling code clean. The set of altered error messages was obtained by grepping for `"s"` and `(s)`, so there might be some missing messages.

rustc: Streamline error messages for i18n, using `plural` whenever possible.

auto merge of #12669 : huonw/rust/de-block-arms, r=alexcrichton

syntax: make match arms store the expr directly.

Previously `ast::Arm` was always storing a single `ast::Expr` wrapped in an
`ast::Block` (for historical reasons, AIUI), so we might as just store
that expr directly.

Closes #3085.

auto merge of #12672 : korenchkin/rust/checked-bigint, r=alexcrichton

auto merge of #12674 : alexcrichton/rust/snapshots, r=Aatch

This should fix the travis builds.

Register new snapshots

This should fix the travis builds.

auto merge of #12673 : huonw/rust/extendable-vec, r=Aatch

std: add reserve_additional and an Extendable impl to Vec.

std: add reserve_additional and an Extendable impl to Vec.

Implemented checked arithmetic for Big(U)Ints

auto merge of #12665 : alexcrichton/rust/fix-snap-again, r=huonw

This should get us a passing snapshot again.

syntax: make match arms store the expr directly.

Previously `ast::Arm` was always storing a single `ast::Expr` wrapped in an
`ast::Block` (for historical reasons, AIUI), so we might as just store
that expr directly.

Closes #3085.

test: Ignore some more syntax extension tests

This should get us a passing snapshot again.

auto merge of #12663 : MicahChalmer/rust/emacs-remove-ws-bug-warning, r=brson

The incompatibility of rust-mode with global-whitespace-mode warned
about in the README was actually fixed by commit 581b3db3b3.  Remove the
warning from the README and close #3994.

Emacs: Remove README warning of old whitespace bug

The incompatibility of rust-mode with global-whitespace-mode warned
about in the README was actually fixed by commit 581b3db3b3.  Remove the
warning from the README and close #3994.

auto merge of #12662 : sfackler/rust/unexported-type, r=cmr

auto merge of #12659 : alexcrichton/rust/fix-snap, r=sfackler

These tests are failing on the snap builders, and are now tagged with a FIXME.

cc #12102

Make visible types public in rustc

auto merge of #12658 : sfackler/rust/asm-expand, r=alexcrichton

A couple of syntax extensions manually expanded expressions, but it
wasn't done universally, most noticably inside of asm!().

There's also a bit of random cleanup.

test: Ignore some phase(syntax) tests

These tests are failing on the snap builders, and are now tagged with a FIXME.

cc #12102

Expand string literals and exprs inside of macros

A couple of syntax extensions manually expanded expressions, but it
wasn't done universally, most noticably inside of asm!().

There's also a bit of random cleanup.

auto merge of #12656 : Armavica/rust/terminfo, r=sfackler

According to `/etc/terminfo/README`,
```
This directory is for system-local terminfo descriptions. By default,
ncurses will search ${HOME}/.terminfo first, then /etc/terminfo (this
directory), then /lib/terminfo, and last not least /usr/share/terminfo.
```

Add /etc/terminfo to the terminfo search paths

auto merge of #12651 : lucab/rust/llvmdep-ldflags, r=alexcrichton

This commit let librustc automatically pickup LDFLAGS dependencies
inherited from LLVM, which may otherwise result in undefined
references to external symbols under certain linking environment.

A symptom of this issue is eg. a failure when trying to link against
librustc (due to unresolved ffi_* symbols), while using a system-wide
LLVM.

Signed-off-by: Luca Bruno <lucab@debian.org>

travis: remove manually added RUSTFLAGS

Indirect dependencies should now be picked up through the
autogenerated llvmdeps.rs instead.

Signed-off-by: Luca Bruno <lucab@debian.org>

auto merge of #12637 : pcwalton/rust/devecing, r=alexcrichton

r? @alexcrichton