Move PhantomData<T> from Shared<T> to users of both Shared and #[may_dangle]

After discussing [1] today with @pnkfelix and @Gankro,
we concluded that it’s ok for drop checking not to be much smarter
than the current `#[may_dangle]` design which requires an explicit
unsafe opt-in.

[1] https://github.com/rust-lang/rust/issues/27730#issuecomment-316432083

Auto merge of #46740 - oli-obk:rls, r=nrc

Update the rls and rustfmt submodules

r? @nrc

Update the rls and rustfmt submodules

Auto merge of #46706 - sunjay:gat-lifetimes, r=nikomatsakis

Lifetime Resolution for Generic Associated Types

Tracking Issue: https://github.com/rust-lang/rust/issues/44265

r? @nikomatsakis

This PR implements lifetime resolution for generic associated types. :tada:

## Remaining Work Before Merge

I'm going to go do these things in the next day or so. Please let me know if you spot anything in my changes until then.

- [x] If I'm not mistaken, at least some tests should pass now. I need to go through the tests and re-enable the ones that should work by removing the appropriate `~ ERROR` comments

Auto merge of #46653 - estebank:str-as-ch, r=petrochenkov

When attempting to write str with single quote suggest double quotes

Fix #26101.

When attempting to write str with single quote suggest double quotes

Auto merge of #46537 - pnkfelix:two-phase-borrows, r=arielb1

[MIR-borrowck] Two phase borrows

This adds limited support for two-phase borrows as described in
  http://smallcultfollowing.com/babysteps/blog/2017/03/01/nested-method-calls-via-two-phase-borrowing/

The support is off by default; you opt into it via the flag `-Z two-phase-borrows`

I have written "*limited* support" above because there are simple variants of the simple `v.push(v.len())` example that one would think should work but currently do not, such as the one documented in the test compile-fail/borrowck/two-phase-reservation-sharing-interference-2.rs

(To be clear, that test is not describing something that is unsound. It is just providing an explicit example of a limitation in the implementation given in this PR. I have ideas on how to fix, but I want to land the work that is in this PR first, so that I can stop repeatedly rebasing this branch.)

Auto merge of #46701 - eddyb:vector-newtypes, r=nagisa

rustc: unpack newtyped of #[repr(simd)] vector types.

Prerequisite for a `#[repr(transparent)]` implementation that works with SIMD vectors.

cc @rkruppe

Auto merge of #46641 - petrochenkov:nohelp2, r=nikomatsakis

Move compile-fail tests with NOTE/HELP annotations to UI

Remove NOTE/HELP annotations from UI tests

cc https://github.com/rust-lang/rust/issues/44844 @oli-obk @est31
r? @nikomatsakis

Address review feedback: don't treat "first" activation special.

Instead, filter out (non-)conflicts of activiations with themselves in
the same manner that we filter out non-conflict between an activation
and its reservation.

Review feedback: Added test with control flow merge of two borrows "before activation"

In reality the currently generated MIR has at least one of the activations
in a copy that occurs before the merge. But still, good to have a test,
in anticipation of that potentially changing...

Address review feedback: don't bother skipping reservations paired with activations.

Auto merge of #45047 - durka:trait-alias, r=petrochenkov

trait alias infrastructure

This will be an implementation of trait aliases (RFC 1733, #41517).

Progress so far:

- [x] Feature gate
- [x] Add to parser
  - [x] `where` clauses
    - [x] prohibit LHS type parameter bounds via AST validation https://github.com/rust-lang/rust/pull/45047#discussion_r143575575
- [x] Add to AST and HIR
  - [x] make a separate PathSource for trait alias contexts https://github.com/rust-lang/rust/pull/45047#discussion_r143353932
- [x] Stub out enough of typeck and resolve to just barely not ICE

Postponed:

- [ ] Actually implement the alias part
- [ ] #21903
- [ ] #24010

I need some pointers on where to start with that last one. The test currently does this:

```
error[E0283]: type annotations required: cannot resolve `_: CD`
  --> src/test/run-pass/trait-alias.rs:34:16
   |
34 |     let both = foo();
   |                ^^^
   |
   = note: required by `foo`
```

Fix rebase

Update docs for custom normalization of test output

Support regexes in custom normalization in UI tests

Do the same things for fulldeps tests

Remove NOTE/HELP annotations from UI tests

Move compile-fail tests with NOTE/HELP annotations to UI

Remove NOTE/HELP annotations from error index tests

Auto merge of #46562 - michaelwoerister:faster-span-hashing, r=eddyb

incr.comp.: Speed up span hashing by caching expansion context hashes.

This PR fixes the performance regressions from https://github.com/rust-lang/rust/pull/46338.

r? @nikomatsakis

rls depends on rustfmt

error for impl trait alias

trait alias fallout

feature gate trait aliases

error on any use of trait alias

add trait aliases to typeck

add trait aliases to HIR

stub out trait aliases in librustdoc

stub out trait aliases in save_analysis

stub out trait aliases in resolve

add trait aliases to AST

incr.comp.: Do less hashing per Span.

incr.comp.: Speed up span hashing by caching expansion context hashes.

Auto merge of #45002 - oli-obk:miri, r=eddyb

Validate miri against the HIR const evaluator

r? @eddyb

cc @alexcrichton @arielb1 @RalfJung

The interesting parts are the last few functions in `librustc_const_eval/eval.rs`

* We warn if miri produces an error while HIR const eval does not.
* We warn if miri produces a value that does not match the value produced by HIR const eval
* if miri succeeds and HIR const eval fails, nothing is emitted, but we still return the HIR error
* if both error, nothing is emitted and the HIR const eval error is returned

So there are no actual changes, except that miri is forced to produce the same values as the old const eval.

* This does **not** touch the const evaluator in trans at all. That will come in a future PR.
* This does **not** cause any code to compile that didn't compile before. That will also come in the future

It would be great if someone could start a crater run if travis passes

Address review note: `AccessErrorsReported` meant to track whether error reported at *any* point in past.

Do not produce debuginfo for tools

Auto merge of #46335 - oli-obk:cleanups, r=jseyfried

Use PathBuf instead of String where applicable

r? @jseyfried

Move mir validation out of tree

Use PathBuf instead of String where applicable

Auto merge of #46633 - estebank:arg-mismatch, r=arielb1

Point at whole method call instead of args

To avoid confusion in cases where the code is

```rust
fn foo() {}
/ foo(
|     bar()
|     ^^^ current diagnostics point here for arg count mismatch
| );
|_^ new diagnostic span points here
```

as this leads to confusion making people think that the diagnostic is
talking about `bar`'s arg count, not `foo`'s.

Point at `fn`s definition on arg mismatch, just like we do for closures.

Re #42855, Fix #45633.

Auto merge of #46605 - estebank:macro-backtrace-spans, r=pnkfelix

Use spans for -Z external-macro-backtrace

```
% rustc ui/type-check/cannot_infer_local_or_vec.rs -Z external-macro-backtrace
error[E0282]: type annotations needed
  --> <vec macros>:3:1
   |
1  | / ( $ elem : expr ; $ n : expr ) => (
2  | | $ crate :: vec :: from_elem ( $ elem , $ n ) ) ; ( $ ( $ x : expr ) , * ) => (
3  | | < [ _ ] > :: into_vec ( box [ $ ( $ x ) , * ] ) ) ; ( $ ( $ x : expr , ) * )
   | | ^^^^^^^^^^^^^^^^^^^^^
   | | |
   | | cannot infer type for `T`
4  | | => ( vec ! [ $ ( $ x ) , * ] )
   | |______________________________- in this expansion of `vec!`
   |
  ::: ui/type-check/cannot_infer_local_or_vec.rs
   |
12 |       let x = vec![];
   |           -   ------ in this macro invocation
   |           |
   |           consider giving `x` a type

error: aborting due to previous error
```

Auto merge of #46582 - nikomatsakis:nll-master-to-rust-master-4, r=arielb1

make MIR type checker handle a number of other cases

The existing type checker was primarily used to verify types, but was skipping over a number of details. For example, it was not checking that the predicates on functions were satisfied and so forth. This meant that the NLL region checker was not getting a lot of the constraints it needed. This PR closes those gaps. It also includes a bit of refactoring for the way that we store region values, encapsulating the bit matrix over into its own module and improving the data structures in use.

This is mostly work by @spastorino being ported over from nll-master.

r? @arielb1 or @pnkfelix

After discussion with ariel, replacing a guard within kill_loans_out_of_scope_at_location.

Instead we are "just" careful to invoke it (which sets up a bunch of kill bits)
before we go into the code that sets up the gen bits.

That way, when the gen bits are set up, they will override any
previously set kill-bits for those reservations or activations.

Address review comment: use `.get` instead of indexing to cope w/ terminators.

(Same net effect as code from before; just cleaner way to get there.)

Added test to make sure that undeclared lifetimes are in fact detected

Added test to make sure we can refer to the declared traits of a generic associated type

Auto merge of #46708 - pnkfelix:fix-issue-46112, r=arielb1

Fix visible_parent_map to choose globally minimal paths

Fix #46112: visible_parent_map construction needs a BFS over whole crate forest to get globally minimal paths.

(There are other latent bugs that were e.g. causing this test case to have weirdness like `<unnamed>` in the diagnostic output. Those bugs are not fixed here, since they are issues long-standing in the stable channel.)

Updating tests to remove all "undeclared lifetime" errors (since those should no longer occur)

Check activation points as the place where mutable borrows become relevant.

Since we are now checking activation points, I removed one of the
checks at the reservation point. (You can see the effect this had on
two-phase-reservation-sharing-interference-2.rs)

Also, since we now have checks at both the reservation point and the
activation point, we sometimes would observe duplicate errors (since
either one independently interferes with another mutable borrow).  To
deal with this, I used a similar strategy to one used as discussed on
issue #45360: keep a set of errors reported (in this case for
reservations), and then avoid doing the checks for the corresponding
activations. (This does mean that some errors could get masked, namely
for conflicting borrows that start after the reservation but still
conflict with the activation, which is unchecked when there was an
error for the reservation. But this seems like a reasonable price to
pay.)

Sidestep ICE from `MirBorrowckCtxt::find_closure_span`.

two-phase-reservation-sharing-interference.rs variant that is perhaps more surprising.

test describing a currently unsupported corner case.

tests transcribed from nikos blog post.

the minimal test for two-phase borrows: the core example from niko's blog post on it.

Incorporate active-borrows dataflow into MIR borrow check, yielding
two-phase `&mut`-borrow support.

This (new) support sits under `-Z two-phase-borrows` debugflag.

(Still needs tests. That's coming next.)

Add some doc to `struct Borrows`.

Add some doc to `each_borrow_involving_path` iteration function.

New `ActiveBorrows` dataflow for two-phase `&mut`; not yet borrowed-checked.

High-level picture: The old `Borrows` analysis is now called
`Reservations` (implemented as a newtype wrapper around `Borrows`);
this continues to compute whether a `Rvalue::Ref` can reach a
statement without an intervening `EndRegion`. In addition, we also
track what `Place` each such `Rvalue::Ref` was immediately assigned
to in a given borrow (yay for MIR-structural properties!).

The new `ActiveBorrows` analysis then tracks the initial use of any of
those assigned `Places` for a given borrow. I.e. a borrow becomes
"active" immediately after it starts being "used" in some way. (This
is conservative in the sense that we will treat a copy `x = y;` as a
use of `y`; in principle one might further delay activation in such
cases.)

The new `ActiveBorrows` analysis needs to take the `Reservations`
results as an initial input, because the reservation state influences
the gen/kill sets for `ActiveBorrows`. In particular, a use of `a`
activates a borrow `a = &b` if and only if there exists a path (in the
control flow graph) from the borrow to that use. So we need to know if
the borrow reaches a given use to know if it really gets a gen-bit or
not.

 * Incorporating the output from one dataflow analysis into the input
   of another required more changes to the infrastructure than I had
   expected, and even after those changes, the resulting code is still
   a bit subtle.

 * In particular, Since we need to know the intrablock reservation
   state, we need to dynamically update a bitvector for the
   reservations as we are also trying to compute the gen/kills
   bitvector for the active borrows.

 * The way I ended up deciding to do this (after also toying with at
   least two other designs) is to put both the reservation state and
   the active borrow state into a single bitvector. That is why we now
   have separate (but related) `BorrowIndex` and
   `ReserveOrActivateIndex`: each borrow index maps to a pair of
   neighboring reservation and activation indexes.

As noted above, these changes are solely adding the active borrows
dataflow analysis (and updating the existing code to cope with the
switch from `Borrows` to `Reservations`). The code to process the
bitvector in the borrow checker currently just skips over all of the
active borrow bits.

But atop this commit, one *can* observe the analysis results by
looking at the graphviz output, e.g. via

```rust
 #[rustc_mir(borrowck_graphviz_preflow="pre_two_phase.dot",
             borrowck_graphviz_postflow="post_two_phase.dot")]
```

Includes doc for `FindPlaceUses`, as well as `Reservations` and
`ActiveBorrows` structs, which are wrappers are the `Borrows` struct
that dictate which flow analysis should be performed.

Auto merge of #46715 - kennytm:download-crosstool-ng-from-github, r=TimNN

Download crosstool-ng from GitHub

Workaround the current problem where http://crosstool-ng.org was done, causing all non-x86 jobs to fail spuriously (cc #40474).

If http://crosstool-ng.org becomes online before this PR is merged, this PR should be closed and the tree should be reopened.

Download the crosstool from GitHub instead of crosstool-ng.org

Temporary workaround since crosstool-ng.org was down. Consider mirroring
the release tarball as a more permanent solution.

Allow `mir::Place` to be used as a key in hashtables.

Implement Borrow/BorrowMut/ToOwned relationships betweed IdxSetBuf and IdxSet.

Refactoring alpha-rename  `place` (`BorrowData` field) to `borrowed_place`.

Refactoring: Allow `BlockSets.on_entry` to denote locally accumulated intrablock state.

(Still musing about whether it could make sense to revise the design
here to make these constraints on usage explicit.)

Refactoring: pull bitvector initialization out from other parts of dataflow.

This is meant to ease development of multi-stage dataflow analyses
where the output from one analysis is used to initialize the state
for the next; in such a context, you cannot start with `bottom_value`
for all the bits.

Move error checks out of span for easier to follow `.stderr`

correct comment in test

add FIXME related to constant well-formedness

comments for `defining_ty` and `compute_indices`

Plus an extra assertion.

document return value of `add_live_point`

improve comments on `safe_to_unsafe_fn_ty` and `coerce_closure_fn_ty`

change to use an O(1) data structure for looking up point indices

Converting a `RegionElementIndex` to a `Location` is O(n) though could
trivially be O(log n), but we don't do it that much anyhow -- just on
error and debugging.

refactor region value bitmatrix

fix closure tests now that MIR typeck works properly

These tests had FIXMEs for errors that were not previously being
reported.

Auto merge of #46550 - jseyfried:cleanup_builtin_hygiene, r=nrc

macros: hygienize use of `core`/`std` in builtin macros

Today, if a builtin macro wants to access an item from `core` or `std` (depending `#![no_std]`), it generates `::core::path::to::item` or `::std::path::to::item` respectively (c.f. `fn std_path()` in `libsyntax/ext/base.rs`).

This PR refactors the builtin macros to instead always emit `$crate::path::to::item` here. That is, the def site of builtin macros is taken to be in `extern crate core;` or `extern crate std;`. Since builtin macros are macros 1.0 (i.e. mostly unhygienic), changing the def site can only effect the resolution of `$crate`.

r? @nrc

when reifying a safe fn as an unsafe fn ptr, insert two casts

Otherwise, `run-pass/typeck-fn-to-unsafe-fn-ptr.rs` fails the MIR type checker.

normalize fn sig as part of reification

Mir typeck Cast for Unsize value

Mir typeck Cast for ClosureFnPtr value

Extract coerce_closure_fn_ty function

Mir typeck Cast for UnsafeFnPtr value

Mir typeck Cast for ReifyFnPtr value

Restructure a bit check_aggregate_rvalue code

Add more debug logs

Check functions predicates

Check Aggregate predicates

Check NullaryOp Rvalue

fix universal regions to handle constant expressions like `[T; 22]`

Check Repeat Rvalue

Auto merge of #46419 - jseyfried:all_imports_in_metadata, r=nrc

Record all imports (`use`, `extern crate`) in the crate metadata

This PR adds non-`pub` `use` and `extern crate` imports in the crate metadata since hygienic macros invoked in other crates may use them. We already include all other non-`pub` items in the crate metadata. This improves import suggestions in some cases.

Fixes #42337.

r? @nrc

Improve pretty printing `$crate::` paths.

Expanded HIR `--unpretty hir,identified` to include HIR local id.

Having the HIR local id is useful for cases like understanding the
ReScope identifiers, which are now derived from the HIR local id, and
thus one can map an ReScope back to the HIR node, once one knows what
those local ids are.

Revised graphviz rendering API to avoid requiring borrowed state.

Made `do_dataflow` and related API `pub(crate)`.

Regression test for issue #46112.

Auto merge of #46616 - cramertj:impl-trait-elision, r=nikomatsakis

Implement impl Trait lifetime elision

Fixes #43396.

There's one weird ICE in the interaction with argument-position `impl Trait`. I'm still debugging it-- I've left a test for it commented out with a FIXME.

Also included a FIXME to ensure that `impl Trait` traits are caught under the lint in https://github.com/rust-lang/rust/issues/45992.

r? @nikomatsakis

Trait item lifetime resolution for GATs

Auto merge of #46613 - petrochenkov:absext, r=nikomatsakis

Resolve absolute paths as extern under a feature flag

cc https://github.com/rust-lang/rust/issues/44660
r? @nikomatsakis

Fix #46112: visible_parent_map construction needs a BFS over whole crate forest.

rustc: unpack newtyped of #[repr(simd)] vector types.

Auto merge of #46570 - AgustinCB:issue-46553, r=oli-obk

Ignore `unsopported constant expr` error

Fixes #46553