Use different datastructure for MIRI relocations

This PR makes relocations in MIRI used a sorted vector instead of a `BTreeMap` which should make a few common operations more efficient. Let's see if that's true.

r? @oli-obk

Remove attribute_cache from CrateMetadata

This PR will fix #50508 by removing the `attribute_cache` from the `CrateMetadata` struct. Seeing as performance was referenced in the original issue, I also cleaned up a `self.entry(node_id);` call which might have occasionally happened redundantly.

r? @michaelwoerister

Generate "invalidates" facts when -Znll-facts is passed

Most of the new code is copied directly from the heart of the MIR borrowchecker. I was expecting more fundamental structural changes, hence the copying. This appears to work as it stands, but I'd like to submit a follow-up PR to reduce code duplication. I figured that could wait though, since this is blocking a large amount of work in the borrow check repository and I'm out of time for tonight =).

r? @nikomatsakis

Add lint for multiple associated types

Fix https://github.com/rust-lang/rust/issues/50589. cc @abonander

rustc: Fix another double-lint issue with `crate::`

This commit fixes another issue in the `absolute_path_not_starting_with_crate`
lint where it warns twice about an import which may contain `self`. It turns out
there were a few more locations that needed updating to use `root_id` and
`root_span` introduced in #50970 and after that it looks to work like a charm!

Closes #50978

This commit fixes another issue in the `absolute_path_not_starting_with_crate`
lint where it warns twice about an import which may contain `self`. It turns out
there were a few more locations that needed updating to use `root_id` and
`root_span` introduced in #50970 and after that it looks to work like a charm!

Closes #50978

Update rustfix

- Update compiletest to use rustfix 0.3.1

r? @Manishearth

fix suggestions with nested paths

Fixes #50673

cc @Manishearth @petrochenkov
r? @alexcrichton

Rollup of 15 pull requests

Successful merges:

 - #50846 (Add E0665)
 - #50849 (CheckLoopVisitor: also visit closure arguments)
 - #50863 (Make `[T]::len` and `str::len` const fn)
 - #50875 (rustdoc: use "short form" doc(cfg) printing even when combined with other conditionals)
 - #50913 (Fix typo in cell.rs)
 - #50914 (Issue #50636: Improve error diagnostic with missing commas after struct fields.)
 - #50931 (Inline `try_get`.)
 - #50932 (Optimize seen Predicate filtering.)
 - #50945 (Stabilize feature from_ref)
 - #50946 (rustc: Fix procedural macros generating lifetime tokens)
 - #50947 (rustdoc: set tab width in rust source blocks)
 - #50952 (Add the 2018 edition of the book to doc.rust-lang.org)
 - #50958 (Micro-optimization on PR#50697)
 - #50961 (Fix FileCheck finding with MSVC)
 - #50963 (Right-size the `VecDeque` in `coerce_unsized`.)

Failed merges:

Right-size the `VecDeque` in `coerce_unsized`.

The default capacity of a VecDeque is 8, which is excessive here. In a
"base incremental" check build of rustc-perf's tuple-stress benchmark,
this decreases total heap allocation by 26%. I couldn't see a clear
speedup, but it can't hurt.

Fix FileCheck finding with MSVC

Micro-optimization on PR#50697

We should stop iterating through the indices in the `init_path_map` once we've already found a match for the local.

r? @nikomatsakis or @pnkfelix

Add the 2018 edition of the book to doc.rust-lang.org

The second edition of the book is on its way to the printers, and as such, is frozen. We've forked off the 2018 edition to add new stuff to; this PR now builds it so that people can read it on doc.rust-lang.org.

rustdoc: set tab width in rust source blocks

cc https://github.com/rust-lang/rust/issues/49155 (fixes it?)

This sets the tab width ([in supported browsers](https://developer.mozilla.org/en-US/docs/Web/CSS/tab-size)) in Rust source blocks to 4 spaces wide (instead of the default 8), to correspond with the style guidelines.

rustc: Fix procedural macros generating lifetime tokens

This commit fixes an accidental regression from #50473 where lifetime tokens
produced by procedural macros ended up getting lost in translation in the
compiler and not actually producing parseable code. The issue lies in the fact
that a lifetime's `Ident` is prefixed with `'`. The `glue` implementation for
gluing joint tokens together forgot to take this into account so the lifetime
inside of `Ident` was missing the leading tick!

The `glue` implementation here is updated to create a new `Symbol` in these
situations to manufacture a new `Ident` with a leading tick to ensure it parses
correctly.

Closes #50942

Stabilize feature from_ref

Function `from_ref_mut` is now renamed to `from_mut`, as discussed in #45703.

Closes #45703.

r? @SimonSapin

Optimize seen Predicate filtering.

This speeds up a few rustc-perf benchmark runs, most notably ones
involving 'coercions', the best by 2%.

Inline `try_get`.

This speeds up lots of rustc-perf benchmark runs. The maximum
improvement is 1%, but there are a lot in the 0.5--1.0% range.

Issue #50636: Improve error diagnostic with missing commas after struct fields.

Fixes #50636

Fix typo in cell.rs

rustdoc: use "short form" doc(cfg) printing even when combined with other conditionals

Fixes https://github.com/rust-lang/rust/issues/49334

The original "short form" printing was introduced when `target_feature` was added to the `doc(cfg)` handling. However, it didn't properly propagate the "short form" indicator if the cfg was a combination of multiple conditionals, so the linked issue happened. This changes the handling to use a bool in the original `Html` wrapper, rather than a separate wrapper struct that defers to the original one.

Make `[T]::len` and `str::len` const fn

r? @Gankro

CheckLoopVisitor: also visit closure arguments

This turns the ICE #50581 in this code:

```rust
fn main() {
    |_: [u8; break]| ();
}
```

from
```
    'assertion failed: self.tcx.sess.err_count() > 0', librustc_typeck/check/mod.rs
```
to
```
    librustc_mir/hair/cx/expr.rs:543: invalid loop id for break: not inside loop scope
```

which is an ICE as well but at a later stage during compilation and most importantly
fixes of bug #50576 will fix this as well.

As this "only" moves an ICE to a later stage, I didn't add any tests.

Now I have manually verified the default impls of the visitor trait to check whether we have missed any other opportunity to visit more stuff and coudln't find anything (except the missing `break` visit I've fixed in #50829 but that one was already r+'d so I didn't want to push more commits).

Add E0665

Remove SortedMap::iter_mut() since that allows to break the element sorting order which lookup relies on.

Allow let bindings and destructuring in constants and const fn

r? @EddyB

cc https://github.com/rust-lang/rust/issues/48821

Misc changes related to Miri allocations

This builds on top of https://github.com/rust-lang/rust/pull/50249

r? @oli-obk