Normalize associated types when checking global bounds

Fix a typo

 Test that object bounds are preferred over global where clause bounds

Add tests for associated types and inconsistent bounds

Reenable trivial bounds

Removes extra global bounds at the winnowing stage rather than when
normalizing the param_env. This avoids breaking inference when there is
a global bound.

Auto merge of #51235 - nikomatsakis:issue-51117-borrowck-implicit-deref, r=eddyb

remove notion of Implicit derefs from mem-cat

`PointerKind` is included in `LoanPath` and hence forms part of the equality check; this led to having two unequal paths that both represent `*x`, depending on whether the `*` was inserted automatically or explicitly. Bad mojo.

Fixes #51117

r? @eddyb

change `PointerKind::Implicit` to a note

`PointerKind` is included in `LoanPath` and hence forms part of the
equality check; this led to having two unequal paths that both
represent `*x`, depending on whether the `*` was inserted
automatically or explicitly. Bad mojo. The `note` field, in contrast,
is intended more-or-less primarily for this purpose of adding extra
data.

Auto merge of #51203 - nnethercote:obligations-2, r=michaelwoerister

Two minor `obligation_forest` tweaks.

Pretty minimal improvements, but improvements nonetheless.

Auto merge of #51182 - eddyb:not-just-visibility, r=nikomatsakis

[MIR] Change "scopes" from "visibility scopes" to "source scopes".

These scopes are already used for source-oriented diagnostics, lint levels and unsafety checks.
This PR generalizes the naming around scopes, making the type `SourceScope`, and flips (across several commits) the relationship/priority between `LocalDecl`'s "visibility" and "syntactic" scopes.

r? @nikomatsakis

Auto merge of #51127 - frewsxcv:frewsxcv-discriminant, r=GuillaumeGomez

Add doc link from discriminant struct to function.

None

Add doc link from discriminant struct to function.

Auto merge of #51145 - petrochenkov:npbot, r=alexcrichton

resolve: Make sure indeterminate and inconsistent macro resolutions always generate errors

Addresses the issue described in https://github.com/rust-lang/rust/pull/50911#issuecomment-392560525

I haven't come up with a minimized reproduction yet, but confirmed that `npbot` now generates the correct error with `![feature(use_extern_macros)]`.

Auto merge of #51220 - nikomatsakis:issue-51008-false-positive-lifetime-must-be-declared, r=cramertj

reset anonymous-lifetime-mode as we enter `()` scopes

Background:

The anonymous lifetime mode is used to prohibit elided lifetimes where
they didn't used to be permitted, and instead require that `'_` be
used. For example:

```rust
impl Trait for Ref<T> { .. }
//             ^^^^^^ ERROR: should be `Ref<'_, T>`
```

When we are parsing the parts of the impl header, we enter into an alternate mode called `CreateParameter`. In this mode, we give an error for things like `Ref<T>`, but for elided lifetimes in a reference type like `&T` we make the elided lifetime into an in-band lifetime:

https://github.com/rust-lang/rust/blob/4f99f37b7e213d69a489884f651adfc6d217cef5/src/librustc/hir/lowering.rs#L4017-L4035

This was not intended to change behavior because we only enter into that mode in contexts where elision was not historically permitted. However, the problem is that we fail to reset the mode when we enter into bounds like `Fn(&u32)`, where elision *was* allowed -- the same occurs for fn types like `fn(&u32`). This PR restores the original mode in those contexts.

Fixes #51008

r? @cramertj

Inline `NodeIndex` methods.

Because they are small and hot.

Remove `ObligationForest::cache_list`.

It's never used in a meaningful way.

Auto merge of #51138 - spastorino:add-polonius-compare-mode, r=pnkfelix

Add polonius compare mode

**This is now ready to review/merge**

Auto merge of #51215 - eddyb:visit-for-a-lifetime, r=nikomatsakis

 rustc: don't visit lifetime parameters through visit_lifetime.

Ideally we'd also not use the `Lifetime` struct for parameters, but I'll leave that to @varkor (#48149).
Fixes #51185 (discovered while auditing all the `visit_lifetime` implementations).
r? @nikomatsakis

resolve: Make sure indeterminate and inconsistent macro resolutions always generate errors

also reset anon-param-mode for `fn()` types

reset the "anonymous lifetime mode" for parenthesized where clauses

Background:

The anonymous lifetime mode is used to prohibit elided lifetimes where
they didn't used to be permitted, and instead require that `'_` be
used. For example:

```rust
impl Trait for Ref<T> { .. }
//             ^^^^^^ ERROR: should be `Ref<'_, T>`
```

When we are parsing the parts of the impl header, we enter into an
alternate mode called `CreateParameter`. In this mode, we give an
error for things like `Ref<T>`, but for elided lifetimes in a
reference type like `&T` we make the elided lifetime into an in-band
lifetime:

https://github.com/rust-lang/rust/blob/4f99f37b7e213d69a489884f651adfc6d217cef5/src/librustc/hir/lowering.rs#L4017-L4035

This was not intended to change behavior because we only enter into
that mode in contexts where elision was not historically
permitted. However, the problem is that we fail to reset the mode when
we enter into bounds like `Fn(&u32)`, where elision *was* allowed --
the same occurs for fn types like `fn(&u32`). This PR restores the
original mode in those contexts.

Run rustfmt

Add compare-mode to x.py

rustc: rename mir::LocalDecl's syntactic_source_info to source_info.

rustc: turn mir::LocalDecl's visibility_source_info into a SourceScope.

rustc: use syntactic (instead of visibility) source info where appropriate.

rustc: rename mir::LocalDecl's source_info to visibility_source_info.

rustc: turn mir::LocalDecl's syntactic_scope into a SourceInfo.

rustc: rename mir::SourceScopeInfo to mir::SourceScopeLocalData.

rustc: rename mir::VisibilityScope to mir::SourceScope.

rustc: don't visit lifetime parameters through visit_lifetime.

syntax: remove overloading of fold_lifetime{,_def}{,s}.

Add polonius compare mode

Auto merge of #51100 - estebank:as-ref, r=oli-obk

Suggest using `as_ref` on some borrow errors [hack]

When encountering the following code:

```rust
struct Foo;
fn takes_ref(_: &Foo) {}
let ref opt = Some(Foo);

opt.map(|arg| takes_ref(arg));
```

Suggest using `opt.as_ref().map(|arg| takes_ref(arg));` instead.

This is a stop gap solution until we expand typeck to deal with these
cases in a more graceful way.

#43861

Suggest using `as_ref` on some borrow errors [hack]

When encountering the following code:

```rust
struct Foo;
fn takes_ref(_: &Foo) {}
let ref opt = Some(Foo);

opt.map(|arg| takes_ref(arg));
```

Suggest using `opt.as_ref().map(|arg| takes_ref(arg));` instead.

This is a stop gap solution until we expand typeck to deal with these
cases in a more graceful way.

Auto merge of #50955 - steveklabnik:update-libbacktrace, r=alexcrichton

Update libbacktrace

We haven't updated libbacktrace in two years. This is just blindly updating to the latest HEAD; I'd like to see what travis says. It at least builds on my machine, running some tests...

This perpetuates the patches from https://github.com/rust-lang/rust/pull/30908

Replace libbacktrace with a submodule

While we're at it update the `backtrace` crate from crates.io. It turns out that
the submodule's configure script has gotten a lot more finnicky as of late so
also switch over to using the `cc` crate manually which allows to avoid some
hacks around the configure script as well

std: Delete bundled libbacktrace module

Auto merge of #50880 - glandium:oom, r=SimonSapin

OOM handling changes

As discussed in https://github.com/rust-lang/rust/issues/49668#issuecomment-384893456 and subsequent.

This does have codegen implications. Even without the hooks, and with a handler that ignores the arguments, the compiler doesn't eliminate calling `rust_oom` with the `Layout`. Even if it managed to eliminate that, with the hooks, I don't know if the compiler would be able to figure out it can skip it if the hook is never set.

A couple implementation notes:
- I went with explicit enums rather than bools because it makes it clearer in callers what is being requested.
- I didn't know what `feature` to put the hook setting functions behind. (and surprisingly, the compile went through without any annotation on the functions)
- There's probably some bikeshedding to do on the naming.

Cc: @Simonsapin, @sfackler

Auto merge of #51106 - davidtwco:issue-50934, r=nikomatsakis

Optimize the way that loans are killed in borrowck dataflow

Fixes #50934.
r? @nikomatsakis

Auto merge of #51017 - estebank:crate-name-in-path, r=michaelwoerister

Use crate name for reexported `extern crate` paths

Fix #43189.

Auto merge of #50783 - pnkfelix:issue-27282-match-borrows-its-input-take-three, r=nikomatsakis

every match arm reads the match's borrowed input

This PR changes the `match` codegen under NLL (and just NLL, at least for now) to make the following adjustments:
 * It adds a `-Z disable-ast-check-for-mutation-in-guard` which, as described, turns off the naive (conservative but also not 100% sound) check for mutation in guards of match arms.
 * We now borrow the match input at the outset and emit a special `ReadForMatch` statement (that, according to the *static* semantics, reads that borrowed match input) at the start of each match arm. The intent here is to catch cases where the match guard mutates the match input, either via an independent borrow or via `ref mut` borrows in that arm's pattern.
 * In order to ensure that `ref mut` borrows do not actually conflict with the emitted `ReadForMatch` statements, I expanded the two-phase-borrow system slightly, and also changed the MIR code gen so that under NLL, when there is a guard on a match arm, then each pattern variable ends up having *three* temporaries associated with it:
   1. The first temporary will hold the substructure being matched; this is what we will move the (substructural) value into *if* the guard succeeds.
   2. The second temporary also corresponds to the same value as the first, but we are just constructing this temporarily for use during the scope of the guard; it is unaliased and its sole referrer is the third temporary.
   3. The third temporary is a reference to the second temporary.
   * (This sounds complicated, I know, but its actually *simpler* than what I was doing before and had checked into the repo, which was to sometimes construct the final value and then take a reference to it before evaluating the guard. See also PR #49870.)

Fix #27282

This also provides a path towards resolving #24535 aka rust-lang/rfcs#1006, at least once the `-Z disable-ast-check-for-mutation-in-guard` is just turned on by default (under NLL, that is. It is not sound under AST-borrowck).
 * But I did not want to make `#![feature(nll)]` imply that as part of this PR; that seemed like too drastic a change to me.

Add hooks allowing to override the `oom` behavior

Auto merge of #50772 - nicokoch:fastcopy, r=alexcrichton

fs: copy: use copy_file_range on Linux

Linux 4.5 introduced a new system call [copy_file_range](http://man7.org/linux/man-pages/man2/copy_file_range.2.html) to copy data from one file to another.

This PR uses the new system call (if available). This has several advantages:

1. No need to constantly copy data from userspace to kernel space, if the buffer is small or the file is large
2. On some filesystems, like BTRFS, the kernel can leverage internal fs mechanisms for huge performance gains
3. Filesystems on the network dont need to copy data between the host and the client machine (they have to in the current read/write implementation)

I have created a small library that also implements the new system call for some huge performance gains here: https://github.com/nicokoch/fastcopy
Benchmark results are in the README

Fix additional nits:
  - compute bytes_to_copy more elegantly
  - add assert that written is 0 in fallback case

Review feedback: Adding test cases suggested by arielb1.

Review feedback: Fix typo.

Review feedback, remove fixme comment.

Review feedback: Remove a fixme/tbd note and just add a note for the post-NLL future.

Driveby: just inline the two-line `fn inject_borrow` into its one call
site and remove its definition.

Review feedback: update fixme comment to reflect reality.

review feedback: fix indentation of pattern candidates to match code elsewhere in file.

Tests illustrating the bug fixes for #27282 and #24535.

Test update: Fallout from ReadForMatch statements + changes to codegen under NLL.

Expand two-phase-borrows so that a case like this still compiles:

```rust
fn main() {
    fn reuse<X>(_: &mut X) {}
    let mut t = 2f64;
    match t {
        ref mut _b if { false } => { reuse(_b); }
        _ => {}
    }
}
```

Note: The way this is currently written is confusing; when `autoref`
is off, then the arm body bindings (introduced by
`bind_matched_candidate_for_arm_body`) are *also* used for the guard.
(Any attempt to fix this needs to still ensure that the bindings used
by the guard are introduced before the guard is evaluated.)

(Once we turn NLL on by default, we can presumably simplify all of
that.)

Fallout from allowing some mutation in guards.

For some reason, allowing restricted mutation in match arms exposed an
obvious case where a unique borrow can indeed fail, namely something
like:

```rust
match b {
    ...
    ref mut r if { (|| { let bar = &mut *r; **bar = false; })(); false } => { &mut *r }
    //                             ~~~~~~~
    //                                |
    // This ends up holding a `&unique` borrow of `r`, but there ends up being an
    // implicit shared borrow in the guard thanks to rust-lang/rust#49870
    ...
}
```

rust-lang/rust#41962 has a new error with my new code. Incorporate that into my code.

In particular, I am adding an implicit injected borrow on the pattern
matches, and when we go around the loop, the compiler is reporting
that this injected borrow is conflicting with the move of the original
value when the match succeeds.

rust-lang/rust#27282: emit `ReadForMatch` on each match arm.

Also, turn on ReadForMatch emission by default (when using NLL).

rust-lang/rust#27282: Add `StatementKind::ReadForMatch` to MIR.

(This is just the data structure changes and some boilerplate match
code that followed from it; the actual emission of these statements
comes in a follow-up commit.)

Debug flag to bypass restriction of mutation in match guards.

Now, if you pass `-Z disable-ast-check-for-mutation-in-guard`, then we
will just allow you to mutably-borrow and assign in guards of `match`
arms.

This is wildly unsound with AST-borrowck. It is also unsound with
MIR-borrowck without further adjustments, which come in later in the
commit series on this Pull Request.

See also rust-lang/rust#24535 and rust-lang/rfcs#1006.

Pass a `Layout` to `oom`

As discussed in
https://github.com/rust-lang/rust/issues/49668#issuecomment-384893456
and subsequent, there are use-cases where the OOM handler needs to know
the size of the allocation that failed. The alignment might also be a
cause for allocation failure, so providing it as well can be useful.

fix off by one error

tweak debug output some more

Ensure that all statements in block are visited not just successors of a block.

add some debugging statements

Refactored DFS to be much cleaner. Added continue after noting that borrow is out of scope at location.

Auto merge of #51165 - SimonSapin:opt2, r=alexcrichton

Revert "Set opt-level to 3"

This reverts commit aad9840ad49c56830384e87bc8bd87fd0199dc44.

Level 3 (possibly indirectly, the underlying bug might be in XCode’s linker) causes unit tests to sefault when compiled with some versions of XCode: https://github.com/rust-lang/rust/issues/50867

It also appears to cause some segfaults on Windows: https://github.com/rust-lang/rust/pull/50329#issuecomment-386853473, and regressions in some rustc performance benchmarks: https://github.com/rust-lang/rust/pull/50329#issuecomment-388084894

Change the comment on `opt-level = 2` to point to https://github.com/rust-lang/rust/issues/50867

Auto merge of #51133 - spastorino:make_borrowck_use_output, r=nikomatsakis

Make borrowck use polonius output

WIP fix rustc-hash cargo.lock entry for polonius-engine

Whitelist datafrog on tidy

Run rustfmt

Use polonius_output

store output in FlowState

store polonius output in MirBorrowCtx

it compiles, but we do not use the output yet

expose -Zpolonius flag

bump polonius engine

Auto merge of #51134 - RalfJung:from_raw_parts, r=SimonSapin

extend from_raw_parts docs for slices and strs to mention alignment requirement

The documentation for `str::from_raw_parts_mut` seems to not be visible because that method is private, bit I figured it could still be fixed. I also removed the reference to the no-longer-existing `str::from_raw_parts` while I was at it.

Alternatively, should I remove `str::from_raw_parts_mut` completely? it is only used in `str::split_at_mut`, where it might as well be inlined.

Revert "Set opt-level to 3"

This reverts commit aad9840ad49c56830384e87bc8bd87fd0199dc44.

Level 3 (possibly indirectly, the underlying bug might be in XCode’s linker)
causes unit tests to sefault when compiled with some versions of XCode:
https://github.com/rust-lang/rust/issues/50867

It also appears to cause some segfaults on Windows:
https://github.com/rust-lang/rust/pull/50329#issuecomment-386853473

… and regressions in some rustc performance benchmarks:
https://github.com/rust-lang/rust/pull/50329#issuecomment-388084894

Auto merge of #51019 - Zoxc:hash-bytes, r=michaelwoerister

Hash up to 8 bytes at once with FxHasher

r? @michaelwoerister

Auto merge of #51142 - nickbabcock:doc-inspect, r=frewsxcv

Document additional use case for iter::inspect

Adds docs for `iter::inspect` showing the non-debug use case

Closes #49564

Auto merge of #51144 - tmccombs:unix-epoch-stable, r=Mark-Simulacrum

Stabilize SystemTime::UNIX_EPOCH

Fixes #49502

Auto merge of #50475 - csmoe:debr, r=nikomatsakis

Refactor DebruijnIndex to be 0-based

Fixes #49813

Stabilize SystemTime::UNIX_EPOCH

Document additional use case for iter::inspect

change to 0-based indices

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

make depth private

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

remove use of depth from `TyS` and replace with a debruijn index

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

replace `binder_depth` in `LateBoundRegionsDetector`

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

convert `LateBoundRegionsCollector` to track a debruijn index

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

replace use of DebruijnIndex in `for_each_free_region`

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

refactor `resolve_lifetime` to track outer-index, not depth

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

rewrite the hasher to not access `depth` field

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

port `nice_region_error` code to not track depth but rather index

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

stop invoking `DebruijnIndex::new` directly

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

make `shifted_in` and `shifted_out` const fns

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

port `fold_regions` and friends to use debruijn indices directly

They no longer talk about plain integers.

Co-authored-by: csmoe <35686186+csmoe@users.noreply.github.com>

Auto merge of #50465 - clarcharr:wrapping, r=KodrAus

Add missing Wrapping methods, use doc_comment!

Re-opened version of #49393 . Finishing touches for #32463.

Note that this adds `Shl` and `Shr` implementations for `Wrapping<i128>` and `Wrapping<u128>`, which were previously missed. This is technically insta-stable, but I don't know why this would be a problem.

get rid of str::from_raw_parts_mut

str::from_raw_parts has been removed long ago because it can be obtained via
str::from_utf8_unchecked and slice::from_raw_parts.  The same goes for
str::from_raw_parts_mut.

Auto merge of #50929 - zackmdavis:hiridification_initiative, r=michaelwoerister

operate on `HirId` instead of `NodeId` in `hir::Pat::each_binding`, and consequences of that

See #50928 for motivation.

Questions—

 * Is #50928 actually a good idea as a plan of record, or is there some reason to keep `NodeId`s?
 * Are the uses of `find_node_for_hir_id` in this initial submission OK (see the FIXME comments)?
 * Can we bikeshed a better method names `struct_span_lint_hir` _&c._? (Coined in analogy to the `struct_span_lint_node` and `NodeId`, but it feels kind of semantically clunky.)

r? @michaelwoerister

Update rustc-hash to hash up to 8 bytes at once with FxHasher