collections: optimize `HashMap`. Add `DefaultResizePolicy`.

Refactored the load factor and the minimum capacity out of HashMap.
The size of HashMap<K, V> is now 64 bytes by default on a 64-bit platform
(or 48 bytes, that is 2 words less, with FNV)
Added a documentation in a few places to clarify the behavior.
std: Improve non-task-based usage

A few notable improvements were implemented to cut down on the number of aborts
triggered by the standard library when a local task is not found.

* Primarily, the unwinding functionality was restructured to support an unsafe
  top-level function, `try`. This function invokes a closure, capturing any
  failure which occurs inside of it. The purpose of this function is to be as
  lightweight of a "try block" as possible for rust, intended for use when the
  runtime is difficult to set up.

  This function is *not* meant to be used by normal rust code, nor should it be
  consider for use with normal rust code.

* When invoking spawn(), a `fail!()` is triggered rather than an abort.

* When invoking LocalIo::borrow(), which is transitively called by all I/O
  constructors, None is returned rather than aborting to indicate that there is
  no local I/O implementation.

* Invoking get() on a TLD key will return None if no task is available

* Invoking replace() on a TLD key will fail if no task is available.

A test case was also added showing the variety of things that you can do without
a runtime or task set up now. In general, this is just a refactoring to abort
less quickly in the standard library when a local task is not found.
Fixes #14185.

This fix suppresses dead_code warnings from code generated by regex! when
the result of regex! is unused. Correct behavior should be a single
unused variable warning.

Regression tests are included for both `let` and `static` bound regex!
values.
auto merge of #14644 : alexcrichton/rust/more-no-runtime-use-cases, r=brson

A few notable improvements were implemented to cut down on the number of aborts
triggered by the standard library when a local task is not found.

* Primarily, the unwinding functionality was restructured to support an unsafe
  top-level function, `try`. This function invokes a closure, capturing any
  failure which occurs inside of it. The purpose of this function is to be as
  lightweight of a "try block" as possible for rust, intended for use when the
  runtime is difficult to set up.

  This function is *not* meant to be used by normal rust code, nor should it be
  consider for use with normal rust code.

* When invoking spawn(), a `fail!()` is triggered rather than an abort.

* When invoking LocalIo::borrow(), which is transitively called by all I/O
  constructors, None is returned rather than aborting to indicate that there is
  no local I/O implementation.

A test case was also added showing the variety of things that you can do without
a runtime or task set up now. In general, this is just a refactoring to abort
less quickly in the standard library when a local task is not found.
auto merge of #14526 : pczarn/rust/hashmap-opt, r=alexcrichton

An interface that gives a better control over the load factor and the minimum capacity for HashMap.
The size of `HashMap<K, V>` is now 64 bytes by default on a 64-bit platform (or at least 40 bytes, that is 3 words less, with FNV and without minimum capacity)

Unanswered questions about `ResizePolicy`

* should it control the `INITIAL_CAPACITY`?
* should it fully control the resizing behavior? Even though the capacity always changes by a factor of 2.
* is caching `grow_at` desirable?

special thanks to @eddyb and @pnkfelix
auto merge of #14647 : BurntSushi/rust/fix-14185, r=alexcrichton

This fix suppresses dead_code warnings from code generated by regex! when
the result of regex! is unused. Correct behavior should be a single
unused variable warning.

Regression tests are included for both `let` and `static` bound regex!
values.

see #14185
std: Recreate a `collections` module

As with the previous commit with `librand`, this commit shuffles around some
`collections` code. The new state of the world is similar to that of librand:

* The libcollections crate now only depends on libcore and liballoc.
* The standard library has a new module, `std::collections`. All functionality
  of libcollections is reexported through this module.

I would like to stress that this change is purely cosmetic. There are very few
alterations to these primitives.

There are a number of notable points about the new organization:

* std::{str, slice, string, vec} all moved to libcollections. There is no reason
  that these primitives shouldn't be necessarily usable in a freestanding
  context that has allocation. These are all reexported in their usual places in
  the standard library.

* The `hashmap`, and transitively the `lru_cache`, modules no longer reside in
  `libcollections`, but rather in libstd. The reason for this is because the
  `HashMap::new` contructor requires access to the OSRng for initially seeding
  the hash map. Beyond this requirement, there is no reason that the hashmap
  could not move to libcollections.

  I do, however, have a plan to move the hash map to the collections module. The
  `HashMap::new` function could be altered to require that the `H` hasher
  parameter ascribe to the `Default` trait, allowing the entire `hashmap` module
  to live in libcollections. The key idea would be that the default hasher would
  be different in libstd. Something along the lines of:

      // src/libstd/collections/mod.rs

      pub type HashMap<K, V, H = RandomizedSipHasher> =
            core_collections::HashMap<K, V, H>;

  This is not possible today because you cannot invoke static methods through
  type aliases. If we modified the compiler, however, to allow invocation of
  static methods through type aliases, then this type definition would
  essentially be switching the default hasher from `SipHasher` in libcollections
  to a libstd-defined `RandomizedSipHasher` type. This type's `Default`
  implementation would randomly seed the `SipHasher` instance, and otherwise
  perform the same as `SipHasher`.

  This future state doesn't seem incredibly far off, but until that time comes,
  the hashmap module will live in libstd to not compromise on functionality.

* In preparation for the hashmap moving to libcollections, the `hash` module has
  moved from libstd to libcollections. A previously snapshotted commit enables a
  distinct `Writer` trait to live in the `hash` module which `Hash`
  implementations are now parameterized over.

  Due to using a custom trait, the `SipHasher` implementation has lost its
  specialized methods for writing integers. These can be re-added
  backwards-compatibly in the future via default methods if necessary, but the
  FNV hashing should satisfy much of the need for speedier hashing.

A list of breaking changes:

* HashMap::{get, get_mut} no longer fails with the key formatted into the error
  message with `{:?}`, instead, a generic message is printed. With backtraces,
  it should still be not-too-hard to track down errors.

* The HashMap, HashSet, and LruCache types are now available through
  std::collections instead of the collections crate.

* Manual implementations of hash should be parameterized over `hash::Writer`
  instead of just `Writer`.

[breaking-change]
Fallout from the libcollections movement
auto merge of #14538 : alexcrichton/rust/libcollections, r=brson

As with the previous commit with `librand`, this commit shuffles around some
`collections` code. The new state of the world is similar to that of librand:

* The libcollections crate now only depends on libcore and liballoc.
* The standard library has a new module, `std::collections`. All functionality
  of libcollections is reexported through this module.

I would like to stress that this change is purely cosmetic. There are very few
alterations to these primitives.

There are a number of notable points about the new organization:

* std::{str, slice, string, vec} all moved to libcollections. There is no reason
  that these primitives shouldn't be necessarily usable in a freestanding
  context that has allocation. These are all reexported in their usual places in
  the standard library.

* The `hashmap`, and transitively the `lru_cache`, modules no longer reside in
  `libcollections`, but rather in libstd. The reason for this is because the
  `HashMap::new` contructor requires access to the OSRng for initially seeding
  the hash map. Beyond this requirement, there is no reason that the hashmap
  could not move to libcollections.

  I do, however, have a plan to move the hash map to the collections module. The
  `HashMap::new` function could be altered to require that the `H` hasher
  parameter ascribe to the `Default` trait, allowing the entire `hashmap` module
  to live in libcollections. The key idea would be that the default hasher would
  be different in libstd. Something along the lines of:

      // src/libstd/collections/mod.rs

      pub type HashMap<K, V, H = RandomizedSipHasher> =
            core_collections::HashMap<K, V, H>;

  This is not possible today because you cannot invoke static methods through
  type aliases. If we modified the compiler, however, to allow invocation of
  static methods through type aliases, then this type definition would
  essentially be switching the default hasher from `SipHasher` in libcollections
  to a libstd-defined `RandomizedSipHasher` type. This type's `Default`
  implementation would randomly seed the `SipHasher` instance, and otherwise
  perform the same as `SipHasher`.

  This future state doesn't seem incredibly far off, but until that time comes,
  the hashmap module will live in libstd to not compromise on functionality.

* In preparation for the hashmap moving to libcollections, the `hash` module has
  moved from libstd to libcollections. A previously snapshotted commit enables a
  distinct `Writer` trait to live in the `hash` module which `Hash`
  implementations are now parameterized over.

  Due to using a custom trait, the `SipHasher` implementation has lost its
  specialized methods for writing integers. These can be re-added
  backwards-compatibly in the future via default methods if necessary, but the
  FNV hashing should satisfy much of the need for speedier hashing.

A list of breaking changes:

* HashMap::{get, get_mut} no longer fails with the key formatted into the error
  message with `{:?}`, instead, a generic message is printed. With backtraces,
  it should still be not-too-hard to track down errors.

* The HashMap, HashSet, and LruCache types are now available through
  std::collections instead of the collections crate.

* Manual implementations of hash should be parameterized over `hash::Writer`
  instead of just `Writer`.

[breaking-change]
mk: Move rust_test_helpers out of libstd

There's no need to distribute these ABI helpers for tests with the standard rust
distribution they're only needed for our tests.

Closes #2665