Removed redundant code, improve performance

closes #10535
auto merge of #11546 : huonw/rust/trie-insert, r=alexcrichton

This reduces the number of moves/memcpy's we do, which makes insert
faster, especially in cases of keys with long equal prefixes (the
\_low_bits tests):

Before:

    bench_insert_large                ... bench:    553966 ns/iter (+/- 64050)
    bench_insert_large_low_bits       ... bench:   1048151 ns/iter (+/- 92484)
    bench_insert_small                ... bench:    168840 ns/iter (+/- 22410)
    bench_insert_small_low_bits       ... bench:    185069 ns/iter (+/- 38332)

After:

    bench_insert_large                ... bench:    422132 ns/iter (+/- 35112)
    bench_insert_large_low_bits       ... bench:    339083 ns/iter (+/- 34421)
    bench_insert_small                ... bench:    134539 ns/iter (+/- 15254)
    bench_insert_small_low_bits       ... bench:     88775 ns/iter (+/- 5746)

Notably: no unsafe code.
remove reference counting headers from ~

Unique pointers and vectors currently contain a reference counting
header when containing a managed pointer.

This `{ ref_count, type_desc, prev, next }` header is not necessary and
not a sensible foundation for tracing. It adds needless complexity to
library code and is responsible for breakage in places where the branch
has been left out.

The `borrow_offset` field can now be removed from `TyDesc` along with
the associated handling in the compiler.

Closes #9510
Closes #11533
remove `borrow_offset` as ~ is now free of headers
add implementation of `Repr` for `~[T]`
auto merge of #11547 : b1nd/rust/rust-doc, r=alexcrichton

closes #10535
auto merge of #11535 : thestinger/rust/header, r=alexcrichton

Unique pointers and vectors currently contain a reference counting
header when containing a managed pointer.

This `{ ref_count, type_desc, prev, next }` header is not necessary and
not a sensible foundation for tracing. It adds needless complexity to
library code and is responsible for breakage in places where the branch
 has been left out.

The `borrow_offset` field can now be removed from `TyDesc` along with
the associated handling in the compiler.

Closes #9510
Closes #11533
std::trie: remove each_{key,value}_reverse internal iterators.

This are *trivial* to reimplement in terms of each_reverse if that extra
little bit of performance is needed.
std::trie: use unsafe code to give a 3x speed up to the iterator.

This stores the stack of iterators inline (we have a maximum depth with
`uint` keys), and then uses direct pointer offsetting to manipulate it,
in a blazing fast way:

Before:

    bench_iter_large          ... bench:     43187 ns/iter (+/- 3082)
    bench_iter_small          ... bench:       618 ns/iter (+/- 288)

After:

    bench_iter_large          ... bench:     13497 ns/iter (+/- 1575)
    bench_iter_small          ... bench:       220 ns/iter (+/- 91)
rustc: Implement the #[managed] attribute and add an intrinsic
to detect this.

Renames owns_managed -> owns_at_managed, and adds owns_new_managed.
std::gc: add a true garbage collector and use it for  `Gc<T>`.

The garbage collector is a naive mark-and-sweep collector that is
conservative on the stack and mostly conservative on the heap.

This currently will not scan through ~, @, ~[] or @[], nor in any of the
global or task/thread local storages. Hence, `Gc<T>` placed in the wrong
spot may be deallocated while still live, and so all borrowing methods
are marked unsafe. (And `Gc<T>` is marked `#[experimental]`.)
std::gc: support running destructors on values in Gc<T>.
std::gc: add root registration functions, using type information to
shortcircuit when possible.

In theory, this design (using `owns_new_managed` to detect when a type
contains `Gc<T>`) means a smart pointer/alternate vector can just
unconditionally call `register_changes_root` and not worry about whether
this is actually necessary (that is, whether the memory regions actually
needs to be scanned for pointers) because those two functions do it
themselves.
Add the library defined vector type from rust-core.
std::libvec: make it GC safe.
std: add Uniq<T>, a GC-safe version of ~.
std::gc: cache small(ish) allocations to avoid thrashing the pointer
trie.

Allocations are rounded to the next power of two and cached when they
become unreachable. Except for those above 1 MB.
std::gc: flip an external reachability bit instead of the reachability
of every pointer individually.

This makes collections 15% faster.
std::gc: allow finalisers to touch the GC (in a restricted way).

This allows Gc<Vec<Gc<T>>> to work by allow it to register changes to
the GC roots. An unsafe pointer to the GC is stored in the borrowed
version, so any users should be careful they understand the
implementation details of the GC before calling anything on that GC via
that pointer.
rustc: convert owns_new_managed to reaches_new_managed.

When we're tracing, we don't just care about what's stored unboxed in a
value, but whether we can possibly get to a #[managed] value via
pointers.