This removes the expand_derives function, and sprinkles
the functionality throughout the Invocation Collector,
Expander and Resolver.

This allows builtin derives to be registered and
resolved, just like other derive types.

rewrite the predecessors code to create a reduced graph

The old code created a flat listing of "HIR -> WorkProduct" edges.
While perfectly general, this could lead to a lot of repetition if the
same HIR nodes affect many work-products. This is set to be a problem
when we start to skip typeck, since we will be adding a lot more
"work-product"-like nodes.

The newer code uses an alternative strategy: it "reduces" the graph
instead. Basically we walk the dep-graph and convert it to a DAG, where
we only keep intermediate nodes if they are used by multiple
work-products.

This DAG does not contain the same set of nodes as the original graph,
but it is guaranteed that (a) every output node is included in the graph
and (b) the set of input nodes that can reach each output node is
unchanged.

(Input nodes are basically HIR nodes and foreign metadata; output nodes
are nodes that have assocaited state which we will persist to disk in
some way. These are assumed to be disjoint sets.)

r? @michaelwoerister

Fixes #39494

Rollup of 3 pull requests

- Successful merges: #39486, #39506, #39517
- Failed merges:

Update relnotes for 1.15.1

I already checked this into stable, but it needs to be on master/beta too.

Add missing urls in HashMap

r? @frewsxcv

Tiny doc wording change

Fix https://github.com/rust-lang/rust/issues/39366

Miscellaneous refactors around how lints and typeck interact

This is preparation for making incr. comp. skip typeck. The main gist of is trying to rationalize the outputs from typeck that are not part of tables:

- one bit of output is the `used_trait_imports` set, which becomes something we track for dependencies
- the other big of output are various lints; we used to store these into a table on sess, but this work stores them into the`TypeckTables`, and then makes the lint pass consult that
    - I think it probably makes sense to handle errors similarly, eventually, but that's not necessary now

r? @EddyB

Fixes #39495

std: Add ToString trait specialization for Cow<'a, str> and String

There is a specialized version of ToString for str type in std. I think there are other types can also benefit from specialization. `Cow` and `String` are the most obvious one.

r? @bluss

Don't build gcc_personality_v0.c on NetBSD either

Add Iterator::rfind.

I found it weird that `Iterator` has `rpostition` but not `rfind`. This adds that method.

Add information in case of markdown block code test failure

r? @steveklabnik

cc @jonathandturner

I already checked this into stable, but it needs to be on master/beta too.

Bump version, upgrade bootstrap

This commit updates the version number to 1.17.0 as we're not on that version of
the nightly compiler, and at the same time this updates src/stage0.txt to
bootstrap from freshly minted beta compiler and beta Cargo.

This commit updates the version number to 1.17.0 as we're not on that version of
the nightly compiler, and at the same time this updates src/stage0.txt to
bootstrap from freshly minted beta compiler and beta Cargo.

Use `String::with_capacity` in `format!`

Add an `Arguments::estimated_capacity` to estimate the length of formatted text and use it in `std::fmt::format` as the initial capacity of the buffer.

The capacity is calculated based on the literal parts of format string, see the details in the implementation.

Some benches:
```rust
empty:       format!("{}", black_box(""))
literal:     format!("Literal")
long:        format!("Hello Hello Hello Hello, {}!", black_box("world"))
long_rev:    format!("{}, hello hello hello hello!", black_box("world"))
long_rev_2:  format!("{}{}, hello hello hello hello!", 1, black_box("world"))
short:       format!("Hello, {}!", black_box("world"))
short_rev:   format!("{}, hello!", black_box("world"))
short_rev_2: format!("{}{}, hello!", 1, black_box("world"))
surround:    format!("aaaaa{}ccccc{}eeeee", black_box("bbbbb"), black_box("eeeee"))
two_spaced:  format!("{} {}", black_box("bbbbb"), black_box("eeeee"))
worst_case:  format!("{} a long piece...", black_box("and even longer argument. not sure why it has to be so long"))
```
```
 empty        25            28                      3   12.00%
 literal      35            29                     -6  -17.14%
 long         80            46                    -34  -42.50%
 long_rev     79            45                    -34  -43.04%
 long_rev_2   111           66                    -45  -40.54%
 short        73            46                    -27  -36.99%
 short_rev    74            76                      2    2.70%
 short_rev_2  107           108                     1    0.93%
 surround     142           65                    -77  -54.23%
 two_spaced   111           115                     4    3.60%
 worst_case   89            101                    12   13.48%
```

Add dev and ino to MetadataExt

This adds .dev() and .ino() to MetadataExt on Redox

The old algorithm was O(graph)