Use a HashMap for UniverseInfo in mir borrowck

Fixes #88446

r? `@nikomatsakis`

Rollup of 7 pull requests

Successful merges:

 - #88336 ( Detect stricter constraints on gats where clauses in impls vs trait)
 - #88677 (rustc: Remove local variable IDs from `Export`s)
 - #88699 (Remove extra unshallow from cherry-pick checker)
 - #88709 (generic_const_exprs: use thir for abstract consts instead of mir)
 - #88711 (Rework DepthFirstSearch API)
 - #88810 (rustdoc: Cleanup `clean` part 1)
 - #88813 (explicitly link to external `ena` docs)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup

explicitly link to external `ena` docs

we currently do not link to the docs of `ena`: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_infer/infer/struct.InferCtxtInner.html#method.const_unification_table

rustdoc: Cleanup `clean` part 1

Split out from #88379.

These commits are completely independent of each other, and each is a fairly
small change (the last few are new commits; they are not from #88379):

- Remove unnecessary `Cache.*_did` fields
- rustdoc: Get symbol for `TyParam` directly
- Create a valid `Res` in `external_path()`
- Remove unused `hir_id` parameter from `resolve_type`
- Fix redundant arguments in `external_path()`
- Remove unnecessary `is_trait` argument
- rustdoc: Cleanup a pattern match in `external_generic_args()`

r? ``@jyn514``

Rework DepthFirstSearch API

This expands the API to be more flexible, allowing for more visitation patterns
on graphs. This will be useful to avoid extra datasets (and allocations) in
cases where the expanded DFS API is sufficient.

This also fixes a bug with the previous DFS constructor, which left the start
node not marked as visited (even though it was immediately returned).

Commit written by ```@nikomatsakis``` originally, cherry picked from several commits in work on never type stabilization, but stands alone.

generic_const_exprs: use thir for abstract consts instead of mir

Changes `AbstractConst` building to use `thir` instead of `mir` so that there's less chance of consts unifying when they shouldn't because lowering to mir dropped information (see `abstract-consts-as-cast-5.rs` test)

r? `@lcnr`

Remove extra unshallow from cherry-pick checker

This is already done by https://github.com/rust-lang/rust/blob/13db8440bbbe42870bc828d4ec3e965b38670277/src/ci/init_repo.sh#L32-L36 on the beta channel, and git throws an error if you attempt to unshallow an already non-shallow repository.

r? ```@pietroalbini```

rustc: Remove local variable IDs from `Export`s

Local variables can never be exported.

 Detect stricter constraints on gats where clauses in impls vs trait

I might try to see if I can do a bit more to improve these diagnostics, but any initial feedback is appreciated. I can also do any additional work in a followup PR.

r? `@estebank`

Use FxHashSet instead of Vec for well formed tys

Trying to recover perf from #88312

r? `@ghost`

Update LLVM submodule

This merges upstream `release/13.x` changes to our fork. In particular,
this includes the bugfix https://reviews.llvm.org/D108608 (see also
https://bugs.llvm.org/show_bug.cgi?id=51637).

The motivation for this is fixing Rust coverage in Fuchsia: https://fxbug.dev/77427.

Fix rustdoc handling of primitive items

This is a complicated PR and does a lot of things. I'm willing to split it up a little more if it would help reviewing, but it would be tricky and I'd rather not unless it's necessary.

 ## What does this do?

- Fixes https://github.com/rust-lang/rust/issues/73423.
- Fixes https://github.com/rust-lang/rust/issues/79630. I'm not sure how to test this for the standard library explicitly, but you can see from some of the diffs from the `no_std` tests. I also tested it locally and it works correctly: ![image](https://user-images.githubusercontent.com/23638587/125214383-e1fdd000-e284-11eb-8048-76b5df958aad.png)
- Fixes https://github.com/rust-lang/rust/issues/83083.

## Why are these changes interconnected?

- Allowing anchors (https://github.com/rust-lang/rust/issues/83083) without fixing the online/offline problem (https://github.com/rust-lang/rust/issues/79630) will actually just silently discard the anchors, that's not a fix. The online/offline problem is directly related to the fragment hack; links need to go through `fn href()` to be fixed.
- Technically I could fix the online/offline problem without removing the error on anchors; I am willing to separate that out if it would be helpful for reviewing. However I can't fix the anchor problem without adding docs to core, since rustdoc needs all those primitives to have docs to avoid a fallback, and currently `#![no_std]` crates don't have docs for primitives. I also can't fix the online/offline problem without removing the fragment hack, since otherwise diffs like this will be wrong for some primitives but not others:
```diff
`@@` -385,7 +381,7 `@@` fn resolve_primitive_associated_item(
                         ty::AssocKind::Const => "associatedconstant",
                         ty::AssocKind::Type => "associatedtype",
                     };
-                    let fragment = format!("{}#{}.{}", prim_ty.as_sym(), out, item_name);
+                    let fragment = format!("{}.{}", out, item_name);
                     (Res::Primitive(prim_ty), fragment, Some((kind.as_def_kind(), item.def_id)))
                 })
         })
```
- Adding primitive docs to core without making any other change will cause links to go to `core` instead of `std`, even for crates with `extern crate std`. See "Breaking changes to doc(primitive)" below for why this is the case. That said, I could add some special casing to rustdoc at the same time that would let me separate this change from the others (it would fix https://github.com/rust-lang/rust/issues/73423 but still special-case intra-doc links). I'm willing to separate that out if helpful for reviewing.

### Add primitive documentation to libcore

This works by reusing the same `include!("primitive_docs.rs")` file in both core and std, and then special-casing links in core to use relative links instead of intra-doc links. This doesn't use purely intra-doc links because some of the primitive docs links to items only in std; this doesn't use purely relative links because that introduces new broken links when the docs are re-exported (e.g. String's `&str` deref impl, or Vec's slice deref impl).

Note that this copies the whole file to core, to avoid anyone compiling core to have to set `CARGO_PKG_NAME`. See https://rust-lang.zulipchat.com/#narrow/stream/122651-general/topic/Who.20should.20review.20changes.20to.20linkchecker.3F/near/249939598 for more context. It also adds a tidy check to make sure the two files are kept in sync.

### Fix inconsistent online/offline primitive docs

This does four things:
- Records modules with `doc(primitive)` in `cache.external_paths`. This is necessary for `href()` to find them later.
- Makes `cache.primitive_locations` available to the intra-doc link pass, by refactoring out a `PrimitiveType::primitive_locations` function that only uses `TyCtxt`.
- Special cases modules with `doc(primitive)` to be treated as always public for the purpose of links.
- Removes the fragment hack. cc `@notriddle,` I know you added some comments about this in the code (thank you for that!)

### Breaking changes to `doc(primitive)`

"Breaking" is a little misleading here - these are changes in behavior, none of them will cause code to fail to compile.

Let me preface this by saying I think stabilizing `doc(primitive)` was a uniquely terrible idea. As far as I can tell, it was stabilized by oversight; it's been stable since 1.0. No one should have need to use it except the standard library, and a crater run shows that in fact no one is using it: https://github.com/rust-lang/rust/pull/87050#issuecomment-886166706. I hope to actually make `doc(primitive)` a no-op unless you opt-in with a nightly feature, which will keep crates compiling without forcing rustdoc into trying to keep somewhat arbitrary behavior guarantees; but for now, this just subtly changes some of the behavior if you use `doc(primitive)` in a dependency.

That said, here are the changes:
-  Refactoring out `primitive_locations()` is technically a change in behavior, since it no longer looks for primitives in crates that were passed through `--extern`, but not used by the crate; however, that seems like such an unlikely edge case it's not worth dealing with.
- The precedence given to primitive locations is no longer just arbitrary, it can also be inconsistent from run to run. Let me explain that more: previously, primitive locations were sorted by the `CrateNum`; the comment on that sort said "Favor linking to as local extern as possible, so iterate all crates in reverse topological order." Unfortunately, that's not actually what CrateNum tracks: it measures the order crates are loaded, not the number of intermediate crates between that dependency and the root crate. It happened to work as intended before because the compiler injects `extern crate std;` at the top of every crate, which ensured it would have the first CrateNum other than the current, but every other CrateNum was completely arbitrary (for example, `core` often had a later CrateNum than `std`). This now removes the sort on CrateNum completely and special-cases core instead. In particular, if you depend on both `std` and a crate which defines a `doc(primitive)` module, it's arbitrary whether rustdoc will use the docs from std or the ones from the other crate. cc `@alexcrichton,` you wrote this originally.

cc `@rust-lang/rustdoc`
cc `@rust-lang/libs` for the addition to `core` (the commit you're interested in is https://github.com/rust-lang/rust/pull/87073/commits/91346c8293bb5f41d8e1d2ec9336433664652c53)

This prevents the following (very strange) errors:

```
error: linking with `link.exe` failed: exit code: 1120
  |
  = note: "C:\\Program Files (x86)\\Microsoft Visual Studio\\2019\\Enterprise\\VC\\Tools\\MSVC\\14.29.30133\\bin\\HostX64\\x86\\link.exe" "/DEF:C:\\Users\\runneradmin\\AppData\\Local\\Temp\\rustcJih4fa\\lib.def" "/NOLOGO" "/LARGEADDRESSAWARE" "/SAFESEH" "D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\test\\rustdoc\\issue-15318-2\\auxiliary\\issue-15318.issue_15318.0a2a8554-cgu.0.rcgu.o" "D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\test\\rustdoc\\issue-15318-2\\auxiliary\\issue-15318.1na9aylmt25n6w3f.rcgu.o" "/LIBPATH:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\native\\rust-test-helpers" "/LIBPATH:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\test\\rustdoc\\issue-15318-2\\auxiliary" "/LIBPATH:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\i686-pc-windows-msvc\\lib" "vcruntime.lib" "ucrt.lib" "/WHOLEARCHIVE:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\i686-pc-windows-msvc\\lib\\librustc_std_workspace_core-78744e1360284b1e.rlib" "/WHOLEARCHIVE:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\i686-pc-windows-msvc\\lib\\libcore-a900fa3d16956226.rlib" "D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\i686-pc-windows-msvc\\lib\\libcompiler_builtins-eb97e6b4dfd2f421.rlib" "/NXCOMPAT" "/LIBPATH:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\i686-pc-windows-msvc\\lib" "/OUT:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\test\\rustdoc\\issue-15318-2\\auxiliary\\issue_15318.dll" "/OPT:REF,ICF" "/DLL" "/IMPLIB:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\test\\rustdoc\\issue-15318-2\\auxiliary\\issue_15318.dll.lib" "/DEBUG" "/NATVIS:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\etc\\intrinsic.natvis" "/NATVIS:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\etc\\liballoc.natvis" "/NATVIS:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\etc\\libcore.natvis" "/NATVIS:D:\\a\\rust\\rust\\build\\i686-pc-windows-msvc\\stage2\\lib\\rustlib\\etc\\libstd.natvis"
  = note: LINK : warning LNK4216: Exported entry point __DllMainCRTStartup@12
             Creating library D:\a\rust\rust\build\i686-pc-windows-msvc\test\rustdoc\issue-15318-2\auxiliary\issue_15318.dll.lib and object D:\a\rust\rust\build\i686-pc-windows-msvc\test\rustdoc\issue-15318-2\auxiliary\issue_15318.dll.exp
          libcore-a900fa3d16956226.rlib(core-a900fa3d16956226.core.95dedc69-cgu.0.rcgu.o) : error LNK2019: unresolved external symbol __aulldiv referenced in function __ZN4core3num7dec2flt7decimal7Decimal10left_shift17hfb9b6c23d6ff0383E
          libcompiler_builtins-eb97e6b4dfd2f421.rlib(compiler_builtins-eb97e6b4dfd2f421.compiler_builtins.a5ef280a-cgu.51.rcgu.o) : error LNK2001: unresolved external symbol __aulldiv
          libcore-a900fa3d16956226.rlib(core-a900fa3d16956226.core.95dedc69-cgu.0.rcgu.o) : error LNK2019: unresolved external symbol __aullrem referenced in function __ZN4core3fmt3num14parse_u64_into17h90eb20517ec3bd86E
          D:\a\rust\rust\build\i686-pc-windows-msvc\test\rustdoc\issue-15318-2\auxiliary\issue_15318.dll : fatal error LNK1120: 2 unresolved externals

```

Most of these are because alloc uses `#[lang_item]` to define methods,
but core documents primitives before those methods are available.

- Fix rustdoc-js-std test

  For some reason this change made CStr not show up in the results for
  `str,u8`. Since it still shows up for str, and since it wasn't a great
  match for that query anyway, I think this is ok to let slide.

- Add test that all primitives can be linked to
- Enable `doc(primitive)` in `core` as well
- Add linkcheck exception specifically for Windows

  Ideally this would be done automatically by the linkchecker by
  replacing `\\` with forward slashes, but this PR is already a ton of
  work ...

- Don't forcibly fail linkchecking if there's a broken intra-doc link on Windows

  Previously, it would exit with a hard error if a missing file had `::`
  in it. This changes it to report a missing file instead, which allows
  adding an exception.

- Fix broken handling of primitive associated items
- Remove fragment hack

  Fixes 83083

- more logging
- Update CrateNum hacks

  The CrateNum has no relation to where in the dependency tree the crate
  is, only when it's loaded. Explicitly special-case core instead of
  assuming it will be the first DefId.

- Update and add tests
- Cache calculation of primitive locations

  This could possibly be avoided by passing a Cache into
  collect_intra_doc_links; but that's a much larger change, and doesn't
  seem valuable other than for this.

This works by doing two things:
- Adding links that are specific to the crate. Since not all primitive
  items are defined in `core` (due to lang_items), these need to use
  relative links and not intra-doc links.
- Duplicating `primitive_docs` in both core and std. This allows not needing CARGO_PKG_NAME to build the standard library. It also adds a tidy check to make sure they stay the same.

Encode spans relative to the enclosing item

The aim of this PR is to avoid recomputing queries when code is moved without modification.

MCP at https://github.com/rust-lang/compiler-team/issues/443

This is achieved by :
1. storing the HIR owner LocalDefId information inside the span;
2. encoding and decoding spans relative to the enclosing item in the incremental on-disk cache;
3. marking a dependency to the `source_span(LocalDefId)` query when we translate a span from the short (`Span`) representation to its explicit (`SpanData`) representation.

Since all client code uses `Span`, step 3 ensures that all manipulations
of span byte positions actually create the dependency edge between
the caller and the `source_span(LocalDefId)`.
This query return the actual absolute span of the parent item.
As a consequence, any source code motion that changes the absolute byte position of a node will either:
- modify the distance to the parent's beginning, so change the relative span's hash;
- dirty `source_span`, and trigger the incremental recomputation of all code that
  depends on the span's absolute byte position.

With this scheme, I believe the dependency tracking to be accurate.

For the moment, the spans are marked during lowering.
I'd rather do this during def-collection,
but the AST MutVisitor is not practical enough just yet.
The only difference is that we attach macro-expanded spans
to their expansion point instead of the macro itself.

It was only used for sugaring `Fn` trait bounds, and rustdoc already
checks that the `did` is for a `Fn` (or `FnMut`, `FnOnce`) lang item,
so it's not necessary to also check that the `did` belongs to a trait.

If the path is for a trait, it is always true that `trait_did ==
Some(did)`, so instead, `external_path()` now takes an `is_trait`
boolean.

Refactor query forcing

The control flow in those functions was very complex, with several layers of continuations.

I tried to simplify the implementation, while keeping essentially the same logic.
Now, all code paths go through `try_execute_query` for the actual query execution.
Communication with the `dep_graph` and the live caches are the only difference between query getting/ensuring/forcing.

The order of the `where` bounds on auto trait impls changed because
rustdoc currently sorts auto trait `where` bounds based on the `Debug`
output for the bound. Now that the bounds have an actual `Res`, they are
being unintentionally sorted by their `DefId` rather than their path.
So, I had to update a test for the change in ordering of the rendered
bounds.

Rollup of 10 pull requests

Successful merges:

 - #87904 (Reword description of automatic impls of `Unsize`.)
 - #88147 (Fix non-capturing closure return type coercion)
 - #88209 (Improve error message when _ is used for in/inout asm operands)
 - #88668 (Change more x64 size checks to not apply to x32.)
 - #88733 (Fix ICE for functions with more than 65535 arguments)
 - #88757 (Suggest wapping expr in parentheses on invalid unary negation)
 - #88779 (Use more accurate spans for "unused delimiter" lint)
 - #88830 (Add help for E0463)
 - #88849 (don't clone types that are Copy (clippy::clone_on_copy))
 - #88850 (don't convert types into identical types)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup

don't convert types into identical types

example: let x: String = String::new().into();

don't clone types that are Copy (clippy::clone_on_copy)

Add help for E0463

Fixes #87871.

r? ```@estebank```

Use more accurate spans for "unused delimiter" lint

Suggest wapping expr in parentheses on invalid unary negation

Fixes #88701

Fix ICE for functions with more than 65535 arguments

This pull request fixes #88577 by changing the `param_idx` field in the `Param` variant of `WellFormedLoc` from `u16` to `u32`, thus allowing for more than 65,535 arguments in a function. Note that I also added a regression test, but needed to add `// ignore-tidy-filelength` because the test is more than 8000 lines long.

Change more x64 size checks to not apply to x32.

Commit 95e096d6 changed a bunch of size checks already, but more have
been added, so this fixes the new ones the same way: the various size
checks that are conditional on target_arch = "x86_64" were not intended
to apply to x86_64-unknown-linux-gnux32, so add
target_pointer_width = "64" to the conditions.

Improve error message when _ is used for in/inout asm operands

As suggested by ```@Commeownist``` in https://github.com/rust-lang/rust/issues/72016#issuecomment-903102415.

Fix non-capturing closure return type coercion

Fixes #88097. For the example given there:
```rust
fn peculiar() -> impl Fn(u8) -> u8 {
    return |x| x + 1
}
```
which incorrectly reports an error, I noticed something weird in the debug log:
```
DEBUG rustc_typeck::check::coercion coercion::try_find_coercion_lub([closure@test.rs:2:12: 2:21], [closure@test.rs:2:12: 2:21], exprs=1 exprs)
```
Apparently, `try_find_coercion_lub()` thinks that the LUB for two closure types always has to be a function pointer (which explains the `expected closure, found fn pointer` error in #88097). There is one corner case where that isn't true, though — namely, when the two closure types are equal, in which case the trivial LUB is the type itself. This PR fixes this by inserting an explicit check for type equality in `try_find_coercion_lub()`.

Reword description of automatic impls of `Unsize`.

The existing documentation felt a little unhelpfully concise, so this change tries to improve it by using longer sentences, each of which specifies which kinds of types it applies to as early as possible. In particular, the third item starts with “Structs ...” instead of saying “Foo is a struct” later.

Also, the previous list items “Only the last field has a type involving `T`” and “`T` is not part of the type of any other fields” are, as far as I see, redundant with each other, so I removed the latter.

I have no particular knowledge of `Unsize`; I have attempted to leave the meaning entirely unchanged but may have missed a nuance.

Markdown preview of the edited documentation:

> All implementations of `Unsize` are provided automatically by the compiler.
> Those implementations are:
>
> - Arrays `[T; N]` implement `Unsize<[T]>`.
> - Types implementing a trait `Trait` also implement `Unsize<dyn Trait>`.
> - Structs `Foo<..., T, ...>` implement `Unsize<Foo<..., U, ...>>` if all of these conditions
>   are met:
>   - `T: Unsize<U>`.
>   - Only the last field of `Foo` has a type involving `T`.
>   - `Bar<T>: Unsize<Bar<U>>`, where `Bar<T>` stands for the actual type of that last field.

`WrappingRange` (#88242) follow-up (`is_full_for`, `Scalar: Copy`, etc.)

Some changes related to feedback during #88242
r? `@RalfJung`