Auto merge of #40008 - eddyb:lazy-12, r=nikomatsakis

[12/12] On-demand type-checking, const-evaluation, MIR building & const-qualification.

_This is the last of a series ([prev](https://github.com/rust-lang/rust/pull/38813)) of patches designed to rework rustc into an out-of-order on-demand pipeline model for both better feature support (e.g. [MIR-based](https://github.com/solson/miri) early constant evaluation) and incremental execution of compiler passes (e.g. type-checking), with beneficial consequences to IDE support as well.
If any motivation is unclear, please ask for additional PR description clarifications or code comments._

<hr>

As this contains all of the changes that didn't fit neatly into other PRs, I'll be elaborating a bit:

### User-facing changes
* when determining whether an `impl Trait` type implements an auto-trait (e.g. `Send` or `Sync`), the function the `impl Trait` came from has to be inferred and type-checking, disallowing cycles
  * this results from not having an obvious place to put the "deferred obligation" in on-demand atm
  * while we could model side-effects like that and "post-processing passes" better, it's still more limiting than being able to know the result in the original function (e.g. specialization) *and* there are serious problems around region-checking (if a `Send` impl required `'static`, it wasn't enforced)
* early const-eval requires type-checking and const-qualification to be performed first, which means:
  * you get the intended errors before (if any) constant evaluation error that is simply fallout
  * associated consts should always work now, and `const fn` type parameters are properly tracked
    * don't get too excited, array lengths still can't depend on type parameters
* #38864 works as intended now, with `Self` being allowed in `impl` bounds
* #32205 is largely improved, with associated types being limited to "exact match" `impl`s (as opposed to traversing the specialization graph to resolve unspecified type parameters to their defaults in another `impl` or in the `trait`) *while* checking for overlaps building the specialization graph for that trait - once all the trait impls' have been checked for coherence (including ahead-of-time/on-demand), it's uniform
* [crater report](https://gist.github.com/eddyb/bbb869072468c7e08d6d808e75938051) looks clean (aside from `clippy` which broke due to `rustc` internal changes)

### Compiler-internal changes
* `ty::Generics`
  * no longer contains the actual type parameter defaults, instead they're associated with the type parameter's `DefId`, like associated types in a trait definition
    * this allows computing `ty::Generics` as a leaf (reading only its own HIR)
  * holds a mapping from `DefIndex` of type parameters to their indices
* `ty::AdtDef`
  * only tracks `#[repr(simd)]` in its `ReprOptions` `repr` field
  * doesn't contain `enum` discriminant values, but instead each variant either refers to either an explicit value for its discriminant, or the distance from the last explicit discriminant, if any
    * the `.discriminants(tcx)` method produces an iterator of `ConstInt` values, looking up explicit discriminants in a separate map, if necessary
    * this allows computing `ty::AdtDef` as a leaf (reading only its own HIR)
* Small note: the two above (`Generics`, `AdtDef`), `TraitDef` and `AssociatedItem` should probably end up as part of the HIR, eventually, as they're trivially constructed from it
* `ty::FnSig`
  * now also holds ABI and unsafety, alongside argument types, return type and C variadicity
  * `&ty::BareFnTy` and `ty::ClosureTy` have been replaced with `PolyFnSig = Binder<FnSig>`
    * `BareFnTy` was interned and `ClosureTy` was treated as non-trivial to `Clone` because they had a `PolyFnSig` and so used to contain a `Vec<Ty>` (now `&[Ty]`)
* `ty::maps`
  * all the `DepTrackingMap`s have been grouped in a structure available at `tcx.maps`
  * when creating the `tcx`, a set of `Providers` (one `fn` pointer per map) is required for the local crate, and one for all other crates (i.e. metadata loading), `librustc_driver` plugging the various crates (e.g. `librustc_metadata`, `librustc_typeck`, `librustc_mir`) into it
  * when a map is queried and the value is missing, the appropriate `fn` pointer from the `Providers` of that crate is called with the `TyCtxt` and the key being queried, to produce the value on-demand
* `rustc_const_eval`
  * demands both `typeck_tables` and `mir_const_qualif` (in preparation for miri)
  * tracks `Substs` in `ConstVal::Function` for `const fn` calls
  * returns `TypeckError` if type-checking has failed (or cases that can only be reached if it had)
    * this error kind is never reported, resulting in less noisy/redundant diagnostics
  * fixes #39548 (testcase by @larsluthman, taken from #39812, which this supersedes)
* on-demand has so far been hooked up to:
  * `rustc_metadata::cstore_impl`: `ty`, `generics`, `predicates`, `super_predicates`, `trait_def`, `adt_def`, `variances`, `associated_item_def_ids`, `associated_item`, `impl_trait_ref`, `custom_coerce_unsized_kind`, `mir`, `mir_const_qualif`, `typeck_tables`, `closure_kind`, `closure_type`
  * `rustc_typeck::collect`: `ty`, `generics`, `predicates`, `super_predicates`, `type_param_predicates`, `trait_def`, `adt_def`, `impl_trait_ref`
  * `rustc_typeck::coherence`: `coherent_trait`, `coherent_inherent_impls`
  * `rustc_typeck::check`: `typeck_tables`, `closure_type`, `closure_kind`
  * `rustc_mir::mir_map`: `mir`
  * `rustc_mir::transform::qualify_consts`: `mir_const_qualif`

1 files changed, 38 insertions, 8 deletions

diff --git a/src/libsyntax/parse/lexer/mod.rs b/src/libsyntax/parse/lexer/mod.rs
index 6bc15115b09..b7f6e6a2384 100644
--- a/src/libsyntax/parse/lexer/mod.rs
+++ b/src/libsyntax/parse/lexer/mod.rs
@@ -51,10 +51,10 @@ pub struct StringReader<'a> {
     pub filemap: Rc<syntax_pos::FileMap>,
     /// If Some, stop reading the source at this position (inclusive).
     pub terminator: Option<BytePos>,
-    /// Whether to record new-lines in filemap. This is only necessary the first
-    /// time a filemap is lexed. If part of a filemap is being re-lexed, this
-    /// should be set to false.
-    pub save_new_lines: bool,
+    /// Whether to record new-lines and multibyte chars in filemap.
+    /// This is only necessary the first time a filemap is lexed.
+    /// If part of a filemap is being re-lexed, this should be set to false.
+    pub save_new_lines_and_multibyte: bool,
     // cached:
     pub peek_tok: token::Token,
     pub peek_span: Span,
@@ -162,7 +162,7 @@ impl<'a> StringReader<'a> {
             ch: Some('\n'),
             filemap: filemap,
             terminator: None,
-            save_new_lines: true,
+            save_new_lines_and_multibyte: true,
             // dummy values; not read
             peek_tok: token::Eof,
             peek_span: syntax_pos::DUMMY_SP,
@@ -183,6 +183,31 @@ impl<'a> StringReader<'a> {
         sr
     }
 
+    pub fn retokenize(sess: &'a ParseSess, mut span: Span) -> Self {
+        let begin = sess.codemap().lookup_byte_offset(span.lo);
+        let end = sess.codemap().lookup_byte_offset(span.hi);
+
+        // Make the range zero-length if the span is invalid.
+        if span.lo > span.hi || begin.fm.start_pos != end.fm.start_pos {
+            span.hi = span.lo;
+        }
+
+        let mut sr = StringReader::new_raw_internal(sess, begin.fm);
+
+        // Seek the lexer to the right byte range.
+        sr.save_new_lines_and_multibyte = false;
+        sr.next_pos = span.lo;
+        sr.terminator = Some(span.hi);
+
+        sr.bump();
+
+        if let Err(_) = sr.advance_token() {
+            sr.emit_fatal_errors();
+            panic!(FatalError);
+        }
+        sr
+    }
+
     pub fn ch_is(&self, c: char) -> bool {
         self.ch == Some(c)
     }
@@ -378,7 +403,10 @@ impl<'a> StringReader<'a> {
     pub fn bump(&mut self) {
         let new_pos = self.next_pos;
         let new_byte_offset = self.byte_offset(new_pos).to_usize();
-        if new_byte_offset < self.source_text.len() {
+        let end = self.terminator.map_or(self.source_text.len(), |t| {
+            self.byte_offset(t).to_usize()
+        });
+        if new_byte_offset < end {
             let old_ch_is_newline = self.ch.unwrap() == '\n';
             let new_ch = char_at(&self.source_text, new_byte_offset);
             let new_ch_len = new_ch.len_utf8();
@@ -387,7 +415,7 @@ impl<'a> StringReader<'a> {
             self.pos = new_pos;
             self.next_pos = new_pos + Pos::from_usize(new_ch_len);
             if old_ch_is_newline {
-                if self.save_new_lines {
+                if self.save_new_lines_and_multibyte {
                     self.filemap.next_line(self.pos);
                 }
                 self.col = CharPos(0);
@@ -395,7 +423,9 @@ impl<'a> StringReader<'a> {
                 self.col = self.col + CharPos(1);
             }
             if new_ch_len > 1 {
-                self.filemap.record_multibyte_char(self.pos, new_ch_len);
+                if self.save_new_lines_and_multibyte {
+                    self.filemap.record_multibyte_char(self.pos, new_ch_len);
+                }
             }
         } else {
             self.ch = None;