explain why pick-constraints can be an empty vector

add a FIXME related to the non-free-region case

I don't think it would actually be harmful to just ignore such cases
but I'm inclined not to take chances.

update the async-fn-multiple-lifetimes test

fix tests and remove outdated stderr files

integrate reverse graph and upper-bound computation

add a `depth_first_search` helper function

introduce a `VecGraph` abstraction that cheaply stores graphs

This is perhaps better than the linked list approach I was using
before. Lower memory overhead, Theta(N+E) storage. Does require a
sort. =)

implement the graph traits for SCC

improve tests with migration mode, mir mode

remove old error and add an explanation

preliminary integration of "pick constraints" into nll solver

construct pick-constraints and give them to region inference

implement PickConstraintSet type

pass more than outlives constraints to constraint conversion

[WIP] fix `Lift` impl for `Rc`

rename `ConstraintSet` to `OutlivesConstraintSet`

propagate the pick-constraints through queries

pass a `&mut QueryRegionConstraints` not just outlives constraints

remove deref impl and add an index impl

The constraint set is going to be more than just a set of outlives
constraints.

rename `ConstraintIndex` to `OutlivesConstraintIndex`

introduce `QueryRegionConstraints` struct

introduce `QueryRegionConstraints` struct (no-op)

rename `QueryRegionConstraint` to `QueryOutlivesConstraint`

enforce and report pick-constraint errors

The error message here is not great.

integrate pick constraints into lexical solver more completely

rename from "in constraint" to "pick constraint"

add some tests, currently ICE-ing

make `dup_vec` optional

lexical_region_resolve: rustfmt

introduce an "in" constraint instead of error

introduce `constrain_regions` helper

opaque_types/mod.rs: rustfmt

Use a single CtxtInterners

HashMap is UnwindSafe

Fixes https://github.com/rust-lang/rust/issues/62301, a regression in 1.36.0 which was caused by hashbrown using `NonZero<T>` where the older hashmap used `Unique<T>`.

Auto merge of #61922 - tmandry:moar-generator-optimization, r=matthewjasper

Don't store locals that have been moved from in generators

This avoids reserving storage in generators for locals that are moved
out of (and not re-initialized) prior to yield points. Fixes #59123.

This adds a new dataflow analysis, `RequiresStorage`, to determine whether the storage of a local can be destroyed without being observed by the program. The rules are:

1. StorageLive(x) => mark x live
2. StorageDead(x) => mark x dead
3. If a local is moved from, _and has never had its address taken_, mark it dead
4. If (any part of) a local is initialized, mark it live'

This is used to determine whether to save a local in the generator object at all, as well as which locals can be overlapped in the generator layout.

Here's the size in bytes of all testcases included in the change, before and after the change:

async fn test    |Size before |Size after
-----------------|------------|----------
single           | 1028       | 1028
single_with_noop | 2056       | 1032
joined           | 5132       | 3084
joined_with_noop | 8208       | 3084

generator test              |Size before |Size after
----------------------------|------------|----------
move_before_yield           | 1028       | 1028
move_before_yield_with_noop | 2056       | 1032
overlap_move_points         | 3080       | 2056

## Future work

Note that there is a possible extension to this optimization, which modifies rule 3 to read: "If a local is moved from, _**and either has never had its address taken, or is Freeze and has never been mutably borrowed**_, mark it dead." This was discussed at length in #59123 and then #61849. Because this would cause some behavior to be UB which was not UB before, it's a step that needs to be taken carefully.

A more immediate priority for me is inlining `std::mem::size_of_val(&x)` so it becomes apparent that the address of `x` is not taken. This way, using `size_of_val` to look at the size of your inner futures does not affect the size of your outer future.

cc @cramertj @eddyb @Matthias247 @nikomatsakis @RalfJung @Zoxc

refactor check_for_substitution

No behavior change, just flatter and simpler code

Auto merge of #61871 - Zoxc:no-lift-branch, r=eddyb

Don't use lift to detect local types

This overlaps with https://github.com/rust-lang/rust/pull/61392.

r? @eddyb

Fix import of take in collapse_docs.rs

Revert change in compiletest

Enable mem_take feature in relevant crates

Convert more usages over

Use mem::take instead of mem::replace with default

Fix michaelwoerister's mailmap

Auto merge of #62279 - pietroalbini:fix-azure-crlf, r=alexcrichton

ci: explicitly disable CRLF conversion on Windows

The Azure image enables CRLF conversion on Windows builders, but that caused regressions both in our test suite (the miri test suite broke) and in the ecosystem, since we started shipping install scripts with CRLF endings instead of the old LF. The [Godbolt Compiler Explorer](https://godbolt.org/) is one such case of breakage.

This adds a step to the build explicitly disabling the conversion before the repository is checked out.

r? @alexcrichton
cc @gnzlbg

miri realloc: do not require giving old size+align

ci: explicitly disable CRLF conversion on Windows

The Azure image enables CRLF conversion on Windows builders, but that
caused regressions both in our test suite (the miri test suite broke)
and in the ecosystem, since we started shipping install scripts with
CRLF endings instead of the old LF. The Godbolt Compiler Explorer is one
such case of breakage.

This adds a step to the build explicitly disabling the conversion before
the repository is checked out.

Clean up extra lifetime, add assertions

Auto merge of #62267 - GuillaumeGomez:revert-implicit-option-return, r=Centril

Revert "implicit `Option`-returning doctests"

Reverts #61279 as discussed in #61360.

cc @Centril

Auto merge of #62247 - pietroalbini:finish-azure-migration, r=Mark-Simulacrum

ci: finish the migration to azure

This moves to azure the last builders as we discussed on Discord last night.

r? @alexcrichton

bump miri to fix line endings on azure

Update RLS to disable spurious client_find_definitions test

Since switching CI to Azure Pipelines it seems that this test seems
to fail more consistently, so let's disable that for now. It helps
that we have less than a week before release - we disallow PRs that
break the tools to land in this period, so this makes landing critical
PRs smoother  now.

r? @alexcrichton

ci: finish the migration to azure

Revert "implicit `Option`-returning doctests"

This reverts commit 6bb6c001be34d0932a014df981ee18f165c43374.

Clean up inherent_impls

rustc: use a separate copy of P for HIR than for AST.

syntax: use `box` instead of `Box::new` in `ptr::P`.

rustc: always keep `hir::Path` behind a `P<...>`.

Address review comments

syntax: Unsupport `foo! bar { ... }` macros in the parser

Unreserve `macro_rules` as a macro name

Auto merge of #62253 - Centril:rollup-115uuuq, r=Centril

Rollup of 8 pull requests

Successful merges:

 - #62062 (Use a more efficient iteration order for forward dataflow)
 - #62063 (Use a more efficient iteration order for backward dataflow)
 - #62224 (rustdoc: remove unused derives and variants)
 - #62228 (Extend the #[must_use] lint to boxed types)
 - #62235 (Extend the `#[must_use]` lint to arrays)
 - #62239 (Fix a typo)
 - #62241 (Always parse 'async unsafe fn' + properly ban in 2015)
 - #62248 (before_exec actually will only get deprecated with 1.37)

Failed merges:

r? @ghost

Auto merge of #61682 - Centril:stabilize-type_alias_enum_variants, r=petrochenkov

Stabilize `type_alias_enum_variants` in Rust 1.37.0

Stabilize `#![feature(type_alias_enum_variants)]` which allows type-relative resolution with highest priority to `enum` variants in both expression and pattern contexts. For example, you may now write:

```rust
enum Option<T> {
    None,
    Some(T),
}

type OptAlias<T> = Option<T>;

fn work_on_alias(x: Option<u8>) -> u8 {
    match x {
        OptAlias::Some(y) => y + 1,
        OptAlias::None => 0,
    }
}
```

Closes https://github.com/rust-lang/rfcs/issues/2218
Closes https://github.com/rust-lang/rust/issues/52118

r? @petrochenkov

Switch tracking issue for 'slice_patterns'.

Rollup merge of #62248 - RalfJung:release-notes, r=Mark-Simulacrum

before_exec actually will only get deprecated with 1.37

Not sure if we usually fix old release notes, but I just found this when scrolling over them.

Rollup merge of #62241 - Centril:fix-async-unsafe-order, r=petrochenkov

Always parse 'async unsafe fn' + properly ban in 2015

Parse `async unsafe fn` not `unsafe async fn` in implementations. We also take the opportunity to properly ban `async fn` in Rust 2015 when they are inside implementations.

Closes https://github.com/rust-lang/rust/issues/62232.

cc https://github.com/rust-lang/rust/pull/61319, https://github.com/rust-lang/rust/issues/62121, and https://github.com/rust-lang/rust/issues/62149.

r? @petrochenkov

Rollup merge of #62239 - lcolaholicl:lcolaholicl-patch-1, r=kennytm

Fix a typo

The definition of 京 seems to be capital, but not capitol.
[reference](https://en.wiktionary.org/wiki/%E4%BA%AC#Etymology_1)
[another reference](https://jisho.org/word/%E4%BA%AC)

Rollup merge of #62235 - varkor:must_use-adt-components, r=Centril

Extend the `#[must_use]` lint to arrays

Based on top of https://github.com/rust-lang/rust/pull/62228.

r? @Centril

Rollup merge of #62228 - varkor:must_use-trait-in-box, r=Centril

Extend the #[must_use] lint to boxed types

Fixes https://github.com/rust-lang/rust/issues/55506#issuecomment-506940181 (cc @Nemo157).

This should have been included as part of https://github.com/rust-lang/rust/pull/55663, but was overlooked.

Rollup merge of #62224 - euclio:remove-derives, r=GuillaumeGomez

rustdoc: remove unused derives and variants

Though many structs in rustdoc derive `RustcEncodable` and `RustcDecodable`, the impls do not appear to be used by the crate or its dependents. Removing them revealed some enum variants that are never constructed, too.

r? @GuillaumeGomez

Rollup merge of #62063 - ecstatic-morse:dataflow-backward-order, r=nagisa

Use a more efficient iteration order for backward dataflow

This applies the same basic principle as #62062 to the reverse dataflow analysis used to compute liveness information. It is functionally equivalent, except that post-order is used instead of reverse post-order.

In the long-term, `BitDenotation` should probably be extended to support both forward and backward dataflow, but there's some more work needed to get to that point.

Rollup merge of #62062 - ecstatic-morse:dataflow-order, r=nagisa

Use a more efficient iteration order for forward dataflow

Currently, dataflow begins by visiting each block in order of ID (`BasicBlock(0)`, `BasicBlock(1)`, etc.). This PR changes that initial iteration to reverse post-order (see [this blog post](https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/#data-flow-analysis) for more info). This ensures that the effects of all predecessors will be applied before a basic block is visited if the CFG has no back-edges, and should result in less total iterations even when back-edges exist. This should not change the results of dataflow analysis.

The current ordering for basic blocks may be pretty close to RPO already--`BasicBlock(0)` is already the start block--in which case the cost of doing the traversal up front will outweigh the efficiency gains.
A perf run is needed to check this.

r? @pnkfelix (I think).

Update mem::replace example to not be identical to mem::take

This also adds assertions that the operations work as expected.

Improve box clone doctests to ensure the documentation is valid

Extend #[must_use] lint to arrays

Update miri

Fix run-pass tests

Improve error messages for boxed trait objects in tuples

Extend the #[must_use] lint to boxed types

before_exec actually will only get deprecated with 1.37

Auto merge of #59722 - Zoxc:query-cache, r=eddyb

Clean up query cache code

There are a couple of queries for which we do not promote saved results, which have been removed from caching here. This was likely the cause of the regression in https://github.com/rust-lang/rust/pull/57293#issuecomment-476421298.

r? @michaelwoerister

Keep caching for non-promoted queries

Clean up query cache code

Auto merge of #61252 - indygreg:upgrade-musl, r=alexcrichton

Update musl to 1.1.22

This is the latest available version. I noticed Rust wasn't using the
latest version when I attempted to have Cargo link object files produced
outside of Cargo / Rust's toolchain and was getting missing symbol
errors. Those missing symbols were added in 1.1.21 and 1.1.22.

I'm not fully sure of the implications of this change or how
comprehensive the test coverage is. Upstream changes in 1.1.21 and
1.1.22 can be found at
https://git.musl-libc.org/cgit/musl/tree/WHATSNEW?h=v1.1.22&id=e97681d6f2c44bf5fa9ecdd30607cb63c780062e#n1989.

Auto merge of #61767 - JohnTitor:update-smallvec, r=nikomatsakis

Update new_debug_unreachable

In latest master, smallvec has been updated. So we only update new_debug_unreachable to remove unmaintained dependencies.

Replace error by bug macro

Auto merge of #61459 - GuillaumeGomez:fix-rustdoc-sysroot-panic, r=ollie27,bjorn3,QuietMisdreavus

Prevent panic when sysroot cannot be computed

Fixes #61377.

cc @rotty @rust-lang/rustdoc

r? @Manishearth

Add missing type urls in Into trait

Add missing links for TryFrom docs

wfcheck: resolve the type-vars in `AdtField` types

Normalization can leave some type-vars unresolved in its return type.
Make sure to resolve them so we have an infcx-independent type that can
be used with `needs_drop`.

Fixes #61402.

Always parse 'async unsafe fn' + properly ban in 2015.

Simplify control flow

fix the same typo in doctest

Fix a typo
Fix a typo in `libcore/char/methods.rs`

Inline rust_printer

Remove unused import

Remove io::Result from syntax::print

Since we're now writing directly to the vector, there's no need to
thread results through the whole printing infrastructure

Replace pretty-printer Box<dyn Write> with &mut String

Delete now-unused methods

Privatize a bunch of methods

Use pointer size as the source size

Auto merge of #62226 - Centril:rollup-rcy1alx, r=Centril

Rollup of 7 pull requests

Successful merges:

 - #61199 (Revert "Set test flag when rustdoc is running with --test option" )
 - #61755 (Add `--pass $mode` to compiletest through `./x.py`)
 - #61818 (Issue #60709 test)
 - #62023 (publish_toolstate: don't use 'new' from inside the loop)
 - #62104 (Inform the query system about properties of queries at compile time)
 - #62163 (Avoid mem::uninitialized() in std::sys::unix)
 - #62204 (doc(libcore) Fix CS)

Failed merges:

r? @ghost