diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-07 05:48:48 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-07 05:48:48 +0000 |
| commit | ef24de24a82fe681581cc130f342363c47c0969a (patch) | |
| tree | 0d494f7e1a38b95c92426f58fe6eaa877303a86c /src/doc/rustc-dev-guide | |
| parent | Releasing progress-linux version 1.74.1+dfsg1-1~progress7.99u1. (diff) | |
| download | rustc-ef24de24a82fe681581cc130f342363c47c0969a.tar.xz rustc-ef24de24a82fe681581cc130f342363c47c0969a.zip | |
Merging upstream version 1.75.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/doc/rustc-dev-guide')
21 files changed, 466 insertions, 171 deletions
diff --git a/src/doc/rustc-dev-guide/examples/rustc-driver-example.rs b/src/doc/rustc-dev-guide/examples/rustc-driver-example.rs index 70e77fd5b..fc0a5f469 100644 --- a/src/doc/rustc-dev-guide/examples/rustc-driver-example.rs +++ b/src/doc/rustc-dev-guide/examples/rustc-driver-example.rs @@ -63,6 +63,8 @@ fn main() { // Registry of diagnostics codes. registry: registry::Registry::new(&rustc_error_codes::DIAGNOSTICS), make_codegen_backend: None, + expanded_args: Vec::new(), + ice_file: None, }; rustc_interface::run_compiler(config, |compiler| { compiler.enter(|queries| { diff --git a/src/doc/rustc-dev-guide/examples/rustc-driver-getting-diagnostics.rs b/src/doc/rustc-dev-guide/examples/rustc-driver-getting-diagnostics.rs index 888674aaf..0195224de 100644 --- a/src/doc/rustc-dev-guide/examples/rustc-driver-getting-diagnostics.rs +++ b/src/doc/rustc-dev-guide/examples/rustc-driver-getting-diagnostics.rs @@ -73,6 +73,8 @@ fn main() { override_queries: None, registry: registry::Registry::new(&rustc_error_codes::DIAGNOSTICS), make_codegen_backend: None, + expanded_args: Vec::new(), + ice_file: None, }; rustc_interface::run_compiler(config, |compiler| { compiler.enter(|queries| { diff --git a/src/doc/rustc-dev-guide/examples/rustc-driver-interacting-with-the-ast.rs b/src/doc/rustc-dev-guide/examples/rustc-driver-interacting-with-the-ast.rs index df0e0385d..3d3827e5d 100644 --- a/src/doc/rustc-dev-guide/examples/rustc-driver-interacting-with-the-ast.rs +++ b/src/doc/rustc-dev-guide/examples/rustc-driver-interacting-with-the-ast.rs @@ -51,6 +51,8 @@ fn main() { override_queries: None, make_codegen_backend: None, registry: registry::Registry::new(&rustc_error_codes::DIAGNOSTICS), + expanded_args: Vec::new(), + ice_file: None, }; rustc_interface::run_compiler(config, |compiler| { compiler.enter(|queries| { diff --git a/src/doc/rustc-dev-guide/src/SUMMARY.md b/src/doc/rustc-dev-guide/src/SUMMARY.md index 41e16c5e6..4a7fd2b77 100644 --- a/src/doc/rustc-dev-guide/src/SUMMARY.md +++ b/src/doc/rustc-dev-guide/src/SUMMARY.md @@ -124,6 +124,7 @@ - [Goals and clauses](./traits/goals-and-clauses.md) - [Canonical queries](./traits/canonical-queries.md) - [Next-gen trait solving](./solve/trait-solving.md) + - [Invariants of the type system](./solve/invariants.md) - [The solver](./solve/the-solver.md) - [Canonicalization](./solve/canonicalization.md) - [Coinduction](./solve/coinduction.md) @@ -135,6 +136,7 @@ - [Opaque Types](./opaque-types-type-alias-impl-trait.md) - [Inference details](./opaque-types-impl-trait-inference.md) - [Return Position Impl Trait In Trait](./return-position-impl-trait-in-trait.md) +- [Effect checking](./effects.md) - [Pattern and Exhaustiveness Checking](./pat-exhaustive-checking.md) - [MIR dataflow](./mir/dataflow.md) - [Drop elaboration](./mir/drop-elaboration.md) diff --git a/src/doc/rustc-dev-guide/src/appendix/bibliography.md b/src/doc/rustc-dev-guide/src/appendix/bibliography.md index c2bb00e3b..cc262abef 100644 --- a/src/doc/rustc-dev-guide/src/appendix/bibliography.md +++ b/src/doc/rustc-dev-guide/src/appendix/bibliography.md @@ -79,7 +79,7 @@ Rust, as well as publications about Rust. Rust](https://munksgaard.me/papers/laumann-munksgaard-larsen.pdf). Philip Munksgaard's master's thesis. Research for Servo. * [Ownership is Theft: Experiences Building an Embedded OS in Rust - Amit Levy, et. al.](https://amitlevy.com/papers/tock-plos2015.pdf) -* [You can't spell trust without Rust](https://raw.githubusercontent.com/Gankro/thesis/master/thesis.pdf). Alexis Beingessner's master's thesis. +* [You can't spell trust without Rust](https://faultlore.com/blah/papers/thesis.pdf). Aria Beingessner's master's thesis. * [Rust-Bio: a fast and safe bioinformatics library](https://academic.oup.com/bioinformatics/article/32/3/444/1743419). Johannes Köster * [Safe, Correct, and Fast Low-Level Networking](https://octarineparrot.com/assets/msci_paper.pdf). Robert Clipsham's master's thesis. * [Formalizing Rust traits](https://open.library.ubc.ca/cIRcle/collections/ubctheses/24/items/1.0220521). Jonatan Milewski's master's thesis. diff --git a/src/doc/rustc-dev-guide/src/appendix/glossary.md b/src/doc/rustc-dev-guide/src/appendix/glossary.md index 27b6cddf2..ee3a3a720 100644 --- a/src/doc/rustc-dev-guide/src/appendix/glossary.md +++ b/src/doc/rustc-dev-guide/src/appendix/glossary.md @@ -25,6 +25,7 @@ Term | Meaning <span id="drop-glue">drop glue</span> | (internal) compiler-generated instructions that handle calling the destructors (`Drop`) for data types. <span id="dst">DST</span> | Short for Dynamically-Sized Type, this is a type for which the compiler cannot statically know the size in memory (e.g. `str` or `[u8]`). Such types don't implement `Sized` and cannot be allocated on the stack. They can only occur as the last field in a struct. They can only be used behind a pointer (e.g. `&str` or `&[u8]`). <span id="ebl">early-bound lifetime</span> | A lifetime region that is substituted at its definition site. Bound in an item's `Generics` and substituted using a `GenericArgs`. Contrast with **late-bound lifetime**. ([see more](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_type_ir/sty/enum.RegionKind.html#bound-regions)) +<span id="effect">effects</span> | Right now only means const traits and `~const` bounds. ([see more](../effects.md)) <span id="empty-type">empty type</span> | see "uninhabited type". <span id="fat-ptr">fat pointer</span> | A two word value carrying the address of some value, along with some further information necessary to put the value to use. Rust includes two kinds of "fat pointers": references to slices, and trait objects. A reference to a slice carries the starting address of the slice and its length. A trait object carries a value's address and a pointer to the trait's implementation appropriate to that value. "Fat pointers" are also known as "wide pointers", and "double pointers". <span id="free-var">free variable</span> | A "free variable" is one that is not bound within an expression or term; see [the background chapter for more](./background.md#free-vs-bound) @@ -93,6 +94,7 @@ Term | Meaning <span id="upvar">upvar</span> | A variable captured by a closure from outside the closure. <span id="variance">variance</span> | Determines how changes to a generic type/lifetime parameter affect subtyping; for example, if `T` is a subtype of `U`, then `Vec<T>` is a subtype `Vec<U>` because `Vec` is *covariant* in its generic parameter. See [the background chapter](./background.md#variance) for a more general explanation. See the [variance chapter](../variance.md) for an explanation of how type checking handles variance. <span id="variant-idx">variant index</span> | In an enum, identifies a variant by assigning them indices starting at 0. This is purely internal and not to be confused with the ["discriminant"](#discriminant) which can be overwritten by the user (e.g. `enum Bool { True = 42, False = 0 }`). +<span id="WF">Well-formedness</span> | Semantically:An expression that evaluates to meaningful result. In Type Systems: A type related construct which follows rules of the type system. <span id="wide-ptr">wide pointer</span> | A pointer with additional metadata. See "fat pointer" for more. <span id="zst">ZST</span> | Zero-Sized Type. A type whose values have size 0 bytes. Since `2^0 = 1`, such types can have exactly one value. For example, `()` (unit) is a ZST. `struct Foo;` is also a ZST. The compiler can do some nice optimizations around ZSTs. diff --git a/src/doc/rustc-dev-guide/src/building/suggested.md b/src/doc/rustc-dev-guide/src/building/suggested.md index cb722696e..1336ff629 100644 --- a/src/doc/rustc-dev-guide/src/building/suggested.md +++ b/src/doc/rustc-dev-guide/src/building/suggested.md @@ -277,7 +277,6 @@ let # `config.toml.example`) from `1bd30ce2aac40c7698aa4a1b9520aa649ff2d1c5` config = pkgs.writeText "rustc-config" '' profile = "compiler" # you may want to choose a different profile, like `library` or `tools` - changelog-seen = 2 [build] patch-binaries-for-nix = true diff --git a/src/doc/rustc-dev-guide/src/effects.md b/src/doc/rustc-dev-guide/src/effects.md new file mode 100644 index 000000000..1fda7bcbb --- /dev/null +++ b/src/doc/rustc-dev-guide/src/effects.md @@ -0,0 +1,66 @@ +# Effects and effect checking + +Note: all of this describes the implementation of the unstable `effects` and +`const_trait_impl` features. None of this implementation is usable or visible from +stable Rust. + +The implementation of const traits and `~const` bounds is a limited effect system. +It is used to allow trait bounds on `const fn` to be used within the `const fn` for +method calls. Within the function, in order to know whether a method on a trait +bound is `const`, we need to know whether there is a `~const` bound for the trait. +In order to know whether we can instantiate a `~const` bound on a `const fn`, we +need to know whether there is a `const_trait` impl for the type and trait being +used (or whether the `const fn` is used at runtime, then any type implementing the +trait is ok, just like with other bounds). + +We perform these checks via a const generic boolean that gets attached to all +`const fn` and `const trait`. The following sections will explain the desugarings +and the way we perform the checks at call sites. + +The const generic boolean is inverted to the meaning of `const`. In the compiler +it is called `host`, because it enables "host APIs" like `static` items, network +access, disk access, random numbers and everything else that isn't available in +`const` contexts. So `false` means "const", `true` means "not const" and if it's +a generic parameter, it means "maybe const" (meaning we're in a const fn or const +trait). + +## `const fn` + +All `const fn` have a `#[rustc_host] const host: bool` generic parameter that is +hidden from users. Any `~const Trait` bounds in the generics list or `where` bounds +of a `const fn` get converted to `Trait<host> + Trait<true>` bounds. The `Trait<true>` +exists so that associated types of the generic param can be used from projections +like `<T as Trait>::Assoc`, because there are no `<T as ~const Trait>` projections for now. + +## `#[const_trait] trait`s + +The `#[const_trait]` attribute gives the marked trait a `#[rustc_host] const host: bool` +generic parameter. All functions of the trait "inherit" this generic parameter, just like +they have all the regular generic parameters of the trait. Any `~const Trait` super-trait +bounds get desugared to `Trait<host> + Trait<true>` in order to allow using associated +types and consts of the super traits in the trait declaration. This is necessary, because +`<Self as SuperTrait>::Assoc` is always `<Self as SuperTrait<true>>::Assoc` as there is +no `<Self as ~const SuperTrait>` syntax. + +## `typeck` performing method and function call checks. + +When generic parameters are instantiated for any items, the `host` generic parameter +is always instantiated as an inference variable. This is a special kind of inference var +that is not part of the type or const inference variables, similar to how we have +special inference variables for type variables that we know to be an integer, but not +yet which one. These separate inference variables fall back to `true` at +the end of typeck (in `fallback_effects`) to ensure that `let _ = some_fn_item_name;` +will keep compiling. + +All actually used (in function calls, casts, or anywhere else) function items, will +have the `enforce_context_effects` method invoked. +It trivially returns if the function being called has no `host` generic parameter. + +In order to error if a non-const function is called in a const context, we have not +yet disabled the const-check logic that happens on MIR, because +`enforce_context_effects` does not yet perform this check. + +The function call's `host` parameter is then equated to the context's `host` value, +which almost always trivially succeeds, as it was an inference var. If the inference +var has already been bound (since the function item is invoked twice), the second +invocation checks it against the first. diff --git a/src/doc/rustc-dev-guide/src/feature-gates.md b/src/doc/rustc-dev-guide/src/feature-gates.md index 8ad4fea1f..788f93d66 100644 --- a/src/doc/rustc-dev-guide/src/feature-gates.md +++ b/src/doc/rustc-dev-guide/src/feature-gates.md @@ -20,12 +20,12 @@ See ["Stability in code"][adding] in the "Implementing new features" section for To remove a feature gate, follow these steps: -1. Remove the feature gate declaration in `rustc_feature/src/active.rs`. +1. Remove the feature gate declaration in `rustc_feature/src/unstable.rs`. It will look like this: ```rust,ignore /// description of feature - (active, $feature_name, "$version", Some($tracking_issue_number), $edition) + (unstable, $feature_name, "$version", Some($tracking_issue_number), $edition) ``` 2. Add a modified version of the feature gate declaration that you just @@ -45,12 +45,12 @@ To remove a feature gate, follow these steps: To rename a feature gate, follow these steps (the first two are the same steps to follow when [removing a feature gate][removing]): -1. Remove the old feature gate declaration in `rustc_feature/src/active.rs`. +1. Remove the old feature gate declaration in `rustc_feature/src/unstable.rs`. It will look like this: ```rust,ignore /// description of feature - (active, $old_feature_name, "$version", Some($tracking_issue_number), $edition) + (unstable, $old_feature_name, "$version", Some($tracking_issue_number), $edition) ``` 2. Add a modified version of the old feature gate declaration that you just @@ -64,12 +64,12 @@ to follow when [removing a feature gate][removing]): ``` 3. Add a feature gate declaration with the new name to - `rustc_feature/src/active.rs`. It should look very similar to the old + `rustc_feature/src/unstable.rs`. It should look very similar to the old declaration: ```rust,ignore /// description of feature - (active, $new_feature_name, "$version", Some($tracking_issue_number), $edition) + (unstable, $new_feature_name, "$version", Some($tracking_issue_number), $edition) ``` diff --git a/src/doc/rustc-dev-guide/src/hir-debugging.md b/src/doc/rustc-dev-guide/src/hir-debugging.md index c25a558a0..5a0bda208 100644 --- a/src/doc/rustc-dev-guide/src/hir-debugging.md +++ b/src/doc/rustc-dev-guide/src/hir-debugging.md @@ -1,6 +1,13 @@ # HIR Debugging -The `-Z unpretty=hir-tree` flag will dump out the HIR. +Use the `-Z unpretty=hir` flag to produce a human-readable representation of the HIR. +For cargo projects this can be done with `cargo rustc -- -Z unpretty=hir`. +This output is useful when you need to see at a glance how your code was desugared and transformed +during AST lowering. + +For a full `Debug` dump of the data in the HIR, use the `-Z unpretty=hir-tree` flag. +This may be useful when you need to see the full structure of the HIR from the perspective of the +compiler. If you are trying to correlate `NodeId`s or `DefId`s with source code, the `-Z unpretty=expanded,identified` flag may be useful. diff --git a/src/doc/rustc-dev-guide/src/implementing_new_features.md b/src/doc/rustc-dev-guide/src/implementing_new_features.md index 01508889f..427589dab 100644 --- a/src/doc/rustc-dev-guide/src/implementing_new_features.md +++ b/src/doc/rustc-dev-guide/src/implementing_new_features.md @@ -123,12 +123,12 @@ a new unstable feature: 1. Add the feature name to `rustc_span/src/symbol.rs` in the `Symbols {...}` block. -1. Add a feature gate declaration to `rustc_feature/src/active.rs` in the active +1. Add a feature gate declaration to `rustc_feature/src/unstable.rs` in the unstable `declare_features` block. ```rust ignore /// description of feature - (active, $feature_name, "CURRENT_RUSTC_VERSION", Some($tracking_issue_number), $edition) + (unstable, $feature_name, "CURRENT_RUSTC_VERSION", Some($tracking_issue_number), $edition) ``` where `$edition` has the type `Option<Edition>`, and is typically just `None`. If you haven't yet @@ -140,7 +140,7 @@ a new unstable feature: ```rust ignore /// Allows defining identifiers beyond ASCII. - (active, non_ascii_idents, "CURRENT_RUSTC_VERSION", Some(55467), None), + (unstable, non_ascii_idents, "CURRENT_RUSTC_VERSION", Some(55467), None), ``` Features can be marked as incomplete, and trigger the warn-by-default [`incomplete_features` diff --git a/src/doc/rustc-dev-guide/src/llvm-coverage-instrumentation.md b/src/doc/rustc-dev-guide/src/llvm-coverage-instrumentation.md index 9379a57f6..fd215e3e9 100644 --- a/src/doc/rustc-dev-guide/src/llvm-coverage-instrumentation.md +++ b/src/doc/rustc-dev-guide/src/llvm-coverage-instrumentation.md @@ -73,21 +73,21 @@ When compiling with `-C instrument-coverage`, Coverage instrumentation is performed on the MIR with a [MIR pass][mir-passes] called [`InstrumentCoverage`][mir-instrument-coverage]. This MIR pass analyzes the control flow graph (CFG)--represented by MIR `BasicBlock`s--to identify -code branches, and injects additional [`Coverage`][coverage-statement] -statements into the `BasicBlock`s. +code branches, attaches [`FunctionCoverageInfo`] to the function's body, +and injects additional [`Coverage`][coverage-statement] statements into the +`BasicBlock`s. A MIR `Coverage` statement is a virtual instruction that indicates a counter should be incremented when its adjacent statements are executed, to count a span of code ([`CodeRegion`][code-region]). It counts the number of times a -branch is executed, and also specifies the exact location of that code span in -the Rust source code. +branch is executed, and is referred to by coverage mappings in the function's +coverage-info struct. -Note that many of these `Coverage` statements will _not_ be converted into +Note that many coverage counters will _not_ be converted into physical counters (or any other executable instructions) in the final binary. -Some of them will be (see [`CoverageKind::Counter`]), +Some of them will be (see [`CoverageKind::CounterIncrement`]), but other counters can be computed on the fly, when generating a coverage -report, by mapping a `CodeRegion` to a -[`CoverageKind::Expression`]. +report, by mapping a `CodeRegion` to a coverage-counter _expression_. As an example: @@ -121,8 +121,8 @@ determines when to break out of a loop (a `while` condition, or an `if` or `match` with a `break`). In MIR, this is typically lowered to a `SwitchInt`, with one branch to stay in the loop, and another branch to break out of the loop. The branch that breaks out will almost always execute less often, -so `InstrumentCoverage` chooses to add a `Counter` to that branch, and an -`Expression(continue) = Counter(loop) - Counter(break)` to the branch that +so `InstrumentCoverage` chooses to add a `CounterIncrement` to that branch, and +uses an expression (`Counter(loop) - Counter(break)`) for the branch that continues. The `InstrumentCoverage` MIR pass is documented in @@ -130,9 +130,9 @@ The `InstrumentCoverage` MIR pass is documented in [mir-passes]: mir/passes.md [mir-instrument-coverage]: https://github.com/rust-lang/rust/tree/master/compiler/rustc_mir_transform/src/coverage +[`FunctionCoverageInfo`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/coverage/struct.FunctionCoverageInfo.html [code-region]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/coverage/struct.CodeRegion.html -[`CoverageKind::Counter`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/coverage/enum.CoverageKind.html#variant.Counter -[`CoverageKind::Expression`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/coverage/enum.CoverageKind.html#variant.Expression +[`CoverageKind::CounterIncrement`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/coverage/enum.CoverageKind.html#variant.CounterIncrement [coverage-statement]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.StatementKind.html#variant.Coverage [instrument-coverage-pass-details]: #implementation-details-of-the-instrumentcoverage-mir-pass @@ -150,40 +150,38 @@ MIR `Statement` into some backend-specific action or instruction. match statement.kind { ... mir::StatementKind::Coverage(box ref coverage) => { - self.codegen_coverage(&mut bx, coverage.clone(), statement.source_info.scope); - bx + self.codegen_coverage(bx, coverage, statement.source_info.scope); } ``` -`codegen_coverage()` handles each `CoverageKind` as follows: +`codegen_coverage()` handles inlined statements and then forwards the coverage +statement to [`Builder::add_coverage`], which handles each `CoverageKind` as +follows: -- For all `CoverageKind`s, Coverage data (counter ID, expression equation - and ID, and code regions) are passed to the backend's `Builder`, to - populate data structures that will be used to generate the crate's - "Coverage Map". (See the [`FunctionCoverage`][function-coverage] `struct`.) -- For `CoverageKind::Counter`s, an instruction is injected in the backend + +- For both `CounterIncrement` and `ExpressionUsed`, the underlying counter or + expression ID is passed through to the corresponding [`FunctionCoverage`] + struct to indicate that the corresponding regions of code were not removed + by MIR optimizations. +- For `CoverageKind::CounterIncrement`s, an instruction is injected in the backend IR to increment the physical counter, by calling the `BuilderMethod` [`instrprof_increment()`][instrprof-increment]. ```rust - pub fn codegen_coverage(&self, bx: &mut Bx, coverage: Coverage, scope: SourceScope) { + fn add_coverage(&mut self, instance: Instance<'tcx>, coverage: &Coverage) { ... - let instance = ... // the scoped instance (current or inlined function) - let Coverage { kind, code_region } = coverage; - match kind { - CoverageKind::Counter { function_source_hash, id } => { - ... - bx.add_coverage_counter(instance, id, code_region); + let Coverage { kind } = coverage; + match *kind { + CoverageKind::CounterIncrement { id } => { + func_coverage.mark_counter_id_seen(id); ... bx.instrprof_increment(fn_name, hash, num_counters, index); } - CoverageKind::Expression { id, lhs, op, rhs } => { - bx.add_coverage_counter_expression(instance, id, lhs, op, rhs, code_region); + CoverageKind::ExpressionUsed { id } => { + func_coverage.mark_expression_id_seen(id); } - CoverageKind::Unreachable => { - bx.add_coverage_unreachable( - instance, - code_region.expect(... + } + } ``` > The function name `instrprof_increment()` is taken from the LLVM intrinsic @@ -199,7 +197,8 @@ statements is only implemented for LLVM, at this time. [backend-lowering-mir]: backend/lowering-mir.md [codegen-statement]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_ssa/mir/struct.FunctionCx.html#method.codegen_statement [codegen-coverage]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_ssa/mir/struct.FunctionCx.html#method.codegen_coverage -[function-coverage]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_llvm/coverageinfo/map_data/struct.FunctionCoverage.html +[`Builder::add_coverage`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_llvm/builder/struct.Builder.html#method.add_coverage +[`FunctionCoverage`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_llvm/coverageinfo/map_data/struct.FunctionCoverage.html [instrprof-increment]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_ssa/traits/trait.BuilderMethods.html#tymethod.instrprof_increment ### Coverage Map Generation @@ -327,9 +326,10 @@ Instrumentor::new(&self.name(), tcx, mir_body).inject_counters(); The `CoverageGraph` is a coverage-specific simplification of the MIR control flow graph (CFG). Its nodes are [`BasicCoverageBlock`s][bcb], which encompass one or more sequentially-executed MIR `BasicBlock`s -(with no internal branching), plus a `CoverageKind` counter (to -be added, via coverage analysis), and an optional set of additional counters -to count incoming edges (if there are more than one). +(with no internal branching). + +Nodes and edges in the graph can have associated [`BcbCounter`]s, which are +stored in [`CoverageCounters`]. The `Instrumentor`'s `inject_counters()` uses the `CoverageGraph` to compute the best places to inject coverage counters, as MIR `Statement`s, @@ -338,16 +338,15 @@ with the following steps: 1. [`generate_coverage_spans()`][generate-coverage-spans] computes the minimum set of distinct, non-branching code regions, from the MIR. These `CoverageSpan`s represent a span of code that must be counted. -2. [`make_bcb_counters()`][make-bcb-counters] generates `CoverageKind::Counter`s and - `CoverageKind::Expression`s for each `CoverageSpan`, plus additional - `intermediate_expressions`[^intermediate-expressions], not associated with any `CodeRegion`, but +2. [`make_bcb_counters()`][make-bcb-counters] generates `BcbCounter::Counter`s and + `BcbCounter::Expression`s for each `CoverageSpan`, plus additional + _intermediate expressions_[^intermediate-expressions] that are not associated + with any `CodeRegion`, but are required to compute a final `Expression` value for a `CodeRegion`. 3. Inject the new counters into the MIR, as new `StatementKind::Coverage` - statements. This is done by three distinct functions: - - `inject_coverage_span_counters()` - - `inject_indirect_counters()` - - `inject_intermediate_expression()`, called for each intermediate expression - returned from `make_bcb_counters()` + statements. +4. Attach all other necessary coverage information to the function's body as + [`FunctionCoverageInfo`]. [^intermediate-expressions]: Intermediate expressions are sometimes required because `Expression`s are limited to binary additions or subtractions. For @@ -359,7 +358,8 @@ intermediate expression for `B - C`. [coverage-graph]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/graph/struct.CoverageGraph.html [inject-counters]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/struct.Instrumentor.html#method.inject_counters [bcb]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/graph/struct.BasicCoverageBlock.html -[debug]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/debug +[`BcbCounter`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/counters/enum.BcbCounter.html +[`CoverageCounters`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/counters/struct.CoverageCounters.html [generate-coverage-spans]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/spans/struct.CoverageSpans.html#method.generate_coverage_spans [make-bcb-counters]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/counters/struct.BcbCounters.html#method.make_bcb_counters @@ -505,34 +505,3 @@ its `Counter` or `Expression`. [bcb-counters]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/counters/struct.BcbCounters.html [traverse-coverage-graph-with-loops]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/graph/struct.TraverseCoverageGraphWithLoops.html - -### Injecting counters into a MIR `BasicBlock` - -With the refined `CoverageSpan`s, and after all `Counter`s and `Expression`s are -created, the final step is to inject the `StatementKind::Coverage` statements -into the MIR. There are three distinct sources, handled by the following -functions: - -- [`inject_coverage_span_counters()`][inject-coverage-span-counters] injects the - counter from each `CoverageSpan`'s BCB. -- [`inject_indirect_counters()`][inject-indirect-counters] injects counters - for any BCB not assigned to a `CoverageSpan`, and for all edge counters. - These counters don't have `CoverageSpan`s. -- [`inject_intermediate_expression()`][inject-intermediate-expression] injects - the intermediate expressions returned from `make_bcb_counters()`. These - counters aren't associated with any BCB, edge, or `CoverageSpan`. - -These three functions inject the `Coverage` statements into the MIR. -`Counter`s and `Expression`s with `CoverageSpan`s add `Coverage` statements -to a corresponding `BasicBlock`, with a `CodeRegion` computed from the -refined `Span` and current `SourceMap`. - -All other `Coverage` statements have a `CodeRegion` of `None`, but they -still must be injected because they contribute to other `Expression`s. - -Finally, edge's with a `CoverageKind::Counter` require a new `BasicBlock`, -so the counter is only incremented when traversing the branch edge. - -[inject-coverage-span-counters]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/struct.Instrumentor.html#method.inject_coverage_span_counters -[inject-indirect-counters]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/struct.Instrumentor.html#method.inject_indirect_counters -[inject-intermediate-expression]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_transform/coverage/fn.inject_intermediate_expression.html diff --git a/src/doc/rustc-dev-guide/src/return-position-impl-trait-in-trait.md b/src/doc/rustc-dev-guide/src/return-position-impl-trait-in-trait.md index 03c7fb6b7..9ed62c87c 100644 --- a/src/doc/rustc-dev-guide/src/return-position-impl-trait-in-trait.md +++ b/src/doc/rustc-dev-guide/src/return-position-impl-trait-in-trait.md @@ -298,6 +298,24 @@ types in the impl, since this mapping describes the type that should come after the `=` in `type Assoc = ...` for each RPITIT. </details> +##### Implied bounds in RPITIT hidden type inference + +Since `collect_return_position_impl_trait_in_trait_tys` does fulfillment and +region resolution, we must provide it `assumed_wf_types` so that we can prove +region obligations with the same expected implied bounds as +`compare_method_predicate_entailment` does. + +Since the return type of a method is understood to be one of the assumed WF +types, and we eagerly fold the return type with inference variables to do +opaque type inference, after opaque type inference, the return type will +resolve to contain the hidden types of the RPITITs. this would mean that the +hidden types of the RPITITs would be assumed to be well-formed without having +independently proven that they are. This resulted in a +[subtle unsoundness bug](https://github.com/rust-lang/rust/pull/116072). In +order to prevent this cyclic reasoning, we instead replace the hidden types of +the RPITITs in the return type of the method with *placeholders*, which lead +to no implied well-formedness bounds. + #### Default trait body Type-checking a default trait body, like: diff --git a/src/doc/rustc-dev-guide/src/rustc-driver-getting-diagnostics.md b/src/doc/rustc-dev-guide/src/rustc-driver-getting-diagnostics.md index 47b9fb5d9..95e3c7cc8 100644 --- a/src/doc/rustc-dev-guide/src/rustc-driver-getting-diagnostics.md +++ b/src/doc/rustc-dev-guide/src/rustc-driver-getting-diagnostics.md @@ -7,7 +7,7 @@ To get diagnostics from the compiler, configure `rustc_interface::Config` to output diagnostic to a buffer, and run `TyCtxt.analysis`. The following was tested -with <!-- date-check: mar 2023 --> `nightly-2023-03-27`: +with <!-- date-check: oct 2023 --> `nightly-2023-10-03`: ```rust {{#include ../examples/rustc-driver-getting-diagnostics.rs}} diff --git a/src/doc/rustc-dev-guide/src/rustc-driver-interacting-with-the-ast.md b/src/doc/rustc-dev-guide/src/rustc-driver-interacting-with-the-ast.md index 4edbbca00..fc119c1ec 100644 --- a/src/doc/rustc-dev-guide/src/rustc-driver-interacting-with-the-ast.md +++ b/src/doc/rustc-dev-guide/src/rustc-driver-interacting-with-the-ast.md @@ -5,7 +5,7 @@ ## Getting the type of an expression To get the type of an expression, use the `global_ctxt` to get a `TyCtxt`. -The following was tested with <!-- date-check: mar 2023 --> `nightly-2023-03-27`: +The following was tested with <!-- date-check: oct 2023 --> `nightly-2023-10-03`: ```rust {{#include ../examples/rustc-driver-interacting-with-the-ast.rs}} diff --git a/src/doc/rustc-dev-guide/src/solve/invariants.md b/src/doc/rustc-dev-guide/src/solve/invariants.md new file mode 100644 index 000000000..75ae53070 --- /dev/null +++ b/src/doc/rustc-dev-guide/src/solve/invariants.md @@ -0,0 +1,154 @@ +# Invariants of the type system + +FIXME: This file talks about invariants of the type system as a whole, not only the solver + +There are a lot of invariants - things the type system guarantees to be true at all times - +which are desirable or expected from other languages and type systems. Unfortunately, quite +a few of them do not hold in Rust right now. This is either a fundamental to its design or +caused by bugs and something that may change in the future. + +It is important to know about the things you can assume while working on - and with - the +type system, so here's an incomplete and inofficial list of invariants of +the core type system: + +- ✅: this invariant mostly holds, with some weird exceptions, you can rely on it outside +of these cases +- ❌: this invariant does not hold, either due to bugs or by design, you must not rely on +it for soundness or have to be incredibly careful when doing so + +### `wf(X)` implies `wf(normalize(X))` ✅ + +If a type containing aliases is well-formed, it should also be +well-formed after normalizing said aliases. We rely on this as +otherwise we would have to re-check for well-formedness for these +types. + +This is unfortunately broken for `<fndef as FnOnce<..>>::Output` due to implied bounds, +resulting in [#114936]. + +### Structural equality modulo regions implies semantic equality ✅ + +If you have a some type and equate it to itself after replacing any regions with unique +inference variables in both the lhs and rhs, the now potentially structurally different +types should still be equal to each other. + +Needed to prevent goals from succeeding in HIR typeck and then failing in MIR borrowck. +If this does invariant is broken MIR typeck ends up failing with an ICE. + +### Applying inference results from a goal does not change its result ❌ + +TODO: this invariant is formulated in a weird way and needs to be elaborated. +Pretty much: I would like this check to only fail if there's a solver bug: +https://github.com/rust-lang/rust/blob/2ffeb4636b4ae376f716dc4378a7efb37632dc2d/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs#L391-L407 + +If we prove some goal/equate types/whatever, apply the resulting inference constraints, +and then redo the original action, the result should be the same. + +This unfortunately does not hold - at least in the new solver - due to a few annoying reasons. + +### The trait solver has to be *locally sound* ✅ + +This means that we must never return *success* for goals for which no `impl` exists. That would +mean we assume a trait is implemented even though it is not, which is very likely to result in +actual unsoundness. When using `where`-bounds to prove a goal, the `impl` will be provided by the +user of the item. + +This invariant only holds if we check region constraints. As we do not check region constraints +during implicit negative overlap check in coherence, this invariant is broken there. As this check +relies on *completeness* of the trait solver, it is not able to use the current region constraints +check - `InferCtxt::resolve_regions` - as its handling of type outlives goals is incomplete. + +### Normalization of semantically equal aliases in empty environments results in a unique type ✅ + +Normalization for alias types/consts has to have a unique result. Otherwise we can easily +implement transmute in safe code. Given the following function, we have to make sure that +the input and output types always get normalized to the same concrete type. + +```rust +fn foo<T: Trait>( + x: <T as Trait>::Assoc +) -> <T as Trait>::Assoc { + x +} +``` + +Many of the currently known unsound issues end up relying on this invariant being broken. +It is however very difficult to imagine a sound type system without this invariant, so +the issue is that the invariant is broken, not that we incorrectly rely on it. + +### Generic goals and their instantiations have the same result ✅ + +Pretty much: If we successfully typecheck a generic function concrete instantiations +of that function should also typeck. We should not get errors post-monomorphization. +We can however get overflow errors at that point. + +TODO: example for overflow error post-monomorphization + +This invariant is relied on to allow the normalization of generic aliases. Breaking +it can easily result in unsoundness, e.g. [#57893](https://github.com/rust-lang/rust/issues/57893) + +### Trait goals in empty environments are proven by a unique impl ✅ + +If a trait goal holds with an empty environment, there should be a unique `impl`, +either user-defined or builtin, which is used to prove that goal. This is +necessary to select a unique method. It + +We do however break this invariant in few cases, some of which are due to bugs, +some by design: +- *marker traits* are allowed to overlap as they do not have associated items +- *specialization* allows specializing impls to overlap with their parent +- the builtin trait object trait implementation can overlap with a user-defined impl: +[#57893] + +### The type system is complete ❌ + +The type system is not complete, it often adds unnecessary inference constraints, and errors +even though the goal could hold. + +- method selection +- opaque type inference +- handling type outlives constraints +- preferring `ParamEnv` candidates over `Impl` candidates during candidate selection +in the trait solver + +#### The type system is complete during the implicit negative overlap check in coherence ✅ + +During the implicit negative overlap check in coherence we must never return *error* for +goals which can be proven. This would allow for overlapping impls with potentially different +associated items, breaking a bunch of other invariants. + +This invariant is currently broken in many different ways while actually something we rely on. +We have to be careful as it is quite easy to break: +- generalization of aliases +- generalization during subtyping binders (luckily not exploitable in coherence) + +### Trait solving must be (free) lifetime agnostic ✅ + +Trait solving during codegen should have the same result as during typeck. As we erase +all free regions during codegen we must not rely on them during typeck. A noteworthy example +is special behavior for `'static`. + +We also have to be careful with relying on equality of regions in the trait solver. +This is fine for codegen, as we treat all erased regions as equal. We can however +lose equality information from HIR to MIR typeck. + +The new solver "uniquifies regions" during canonicalization, canonicalizing `u32: Trait<'x, 'x>` +as `exists<'0, '1> u32: Trait<'0, '1>`, to make it harder to rely on this property. + +### Removing ambiguity makes strictly more things compile ❌ + +Ideally we *should* not rely on ambiguity for things to compile. +Not doing that will cause future improvements to be breaking changes. + +Due to *incompleteness* this is not the case and improving inference can result in inference +changes, breaking existing projects. + +### Semantic equality implies structural equality ✅ + +Two types being equal in the type system must mean that they have the +same `TypeId` after instantiating their generic parameters with concrete +arguments. This currently does not hold: [#97156]. + +[#57893]: https://github.com/rust-lang/rust/issues/57893 +[#97156]: https://github.com/rust-lang/rust/issues/97156 +[#114936]: https://github.com/rust-lang/rust/issues/114936
\ No newline at end of file diff --git a/src/doc/rustc-dev-guide/src/solve/the-solver.md b/src/doc/rustc-dev-guide/src/solve/the-solver.md index 61e6cad1c..f7d82d117 100644 --- a/src/doc/rustc-dev-guide/src/solve/the-solver.md +++ b/src/doc/rustc-dev-guide/src/solve/the-solver.md @@ -6,12 +6,71 @@ approach. [chalk]: https://rust-lang.github.io/chalk/book/recursive.html -The basic structure of the solver is a pure function -`fn evaluate_goal(goal: Goal<'tcx>) -> Response`. -While the actual solver is not fully pure to deal with overflow and cycles, we are -going to defer that for now. +## A rough walkthrough -To deal with inference variables and to improve caching, we use -[canonicalization](./canonicalization.md). +The entry-point of the solver is `InferCtxtEvalExt::evaluate_root_goal`. This +function sets up the root `EvalCtxt` and then calls `EvalCtxt::evaluate_goal`, +to actually enter the trait solver. -TODO: write the remaining code for this as well. +`EvalCtxt::evaluate_goal` handles [canonicalization](./canonicalization.md), caching, +overflow, and solver cycles. Once that is done, it creates a nested `EvalCtxt` with a +separate local `InferCtxt` and calls `EvalCtxt::compute_goal`, which is responsible for the +'actual solver behavior'. We match on the `PredicateKind`, delegating to a separate function +for each one. + +For trait goals, such a `Vec<T>: Clone`, `EvalCtxt::compute_trait_goal` has +to collect all the possible ways this goal can be proven via +`EvalCtxt::assemble_and_evaluate_candidates`. Each candidate is handled in +a separate "probe", to not leak inference constraints to the other candidates. +We then try to merge the assembled candidates via `EvalCtxt::merge_candidates`. + + +## Important concepts and design pattern + +### `EvalCtxt::add_goal` + +To prove nested goals, we don't directly call `EvalCtxt::compute_goal`, but instead +add the goal to the `EvalCtxt` with `EvalCtxt::all_goal`. We then prove all nested +goals together in either `EvalCtxt::try_evaluate_added_goals` or +`EvalCtxt::evaluate_added_goals_and_make_canonical_response`. This allows us to handle +inference constraints from later goals. + +E.g. if we have both `?x: Debug` and `(): ConstrainToU8<?x>` as nested goals, +then proving `?x: Debug` is initially ambiguous, but after proving `(): ConstrainToU8<?x>` +we constrain `?x` to `u8` and proving `u8: Debug` succeeds. + +### Matching on `TyKind` + +We lazily normalize types in the solver, so we always have to assume that any types +and constants are potentially unnormalized. This means that matching on `TyKind` can easily +be incorrect. + +We handle normalization in two different ways. When proving `Trait` goals when normalizing +associated types, we separately assemble candidates depending on whether they structurally +match the self type. Candidates which match on the self type are handled in +`EvalCtxt::assemble_candidates_via_self_ty` which recurses via +`EvalCtxt::assemble_candidates_after_normalizing_self_ty`, which normalizes the self type +by one level. In all other cases we have to match on a `TyKind` we first use +`EvalCtxt::try_normalize_ty` to normalize the type as much as possible. + +### Higher ranked goals + +In case the goal is higher-ranked, e.g. `for<'a> F: FnOnce(&'a ())`, `EvalCtxt::compute_goal` +eagerly instantiates `'a` with a placeholder and then recursively proves +`F: FnOnce(&'!a ())` as a nested goal. + +### Dealing with choice + +Some goals can be proven in multiple ways. In these cases we try each option in +a separate "probe" and then attempt to merge the resulting responses by using +`EvalCtxt::try_merge_responses`. If merging the responses fails, we use +`EvalCtxt::flounder` instead, returning ambiguity. For some goals, we try +incompletely prefer some choices over others in case `EvalCtxt::try_merge_responses` +fails. + +## Learning more + +The solver should be fairly self-contained. I hope that the above information provides a +good foundation when looking at the code itself. Please reach out on zulip if you get stuck +while doing so or there are some quirks and design decisions which were unclear and deserve +better comments or should be mentioned here. diff --git a/src/doc/rustc-dev-guide/src/solve/trait-solving.md b/src/doc/rustc-dev-guide/src/solve/trait-solving.md index c3089f4a8..7c1e0b684 100644 --- a/src/doc/rustc-dev-guide/src/solve/trait-solving.md +++ b/src/doc/rustc-dev-guide/src/solve/trait-solving.md @@ -39,77 +39,6 @@ which does not have any nested goals. Therefore `Vec<T>: Clone` holds. The trait solver can either return success, ambiguity or an error as a [`CanonicalResponse`]. For success and ambiguity it also returns constraints inference and region constraints. -## Requirements - -Before we dive into the new solver lets first take the time to go through all of our requirements -on the trait system. We can then use these to guide our design later on. - -TODO: elaborate on these rules and get more precise about their meaning. -Also add issues where each of these rules have been broken in the past -(or still are). - -### 1. The trait solver has to be *sound* - -This means that we must never return *success* for goals for which no `impl` exists. That would -simply be unsound by assuming a trait is implemented even though it is not. When using predicates -from the `where`-bounds, the `impl` will be proved by the user of the item. - -### 2. If type checker solves generic goal concrete instantiations of that goal have the same result - -Pretty much: If we successfully typecheck a generic function concrete instantiations -of that function should also typeck. We should not get errors post-monomorphization. -We can however get overflow as in the following snippet: - -```rust -fn foo<T: Trait>(x: ) -``` - -### 3. Trait goals in empty environments are proven by a unique impl - -If a trait goal holds with an empty environment, there is a unique `impl`, -either user-defined or builtin, which is used to prove that goal. - -This is necessary for codegen to select a unique method. -An exception here are *marker traits* which are allowed to overlap. - -### 4. Normalization in empty environments results in a unique type - -Normalization for alias types/consts has a unique result. Otherwise we can easily implement -transmute in safe code. Given the following function, we have to make sure that the input and -output types always get normalized to the same concrete type. -```rust -fn foo<T: Trait>( - x: <T as Trait>::Assoc -) -> <T as Trait>::Assoc { - x -} -``` - -### 5. During coherence trait solving has to be complete - -During coherence we never return *error* for goals which can be proven. This allows overlapping -impls which would break rule 3. - -### 6. Trait solving must be (free) lifetime agnostic - -Trait solving during codegen should have the same result as during typeck. As we erase -all free regions during codegen we must not rely on them during typeck. A noteworthy example -is special behavior for `'static`. - -We also have to be careful with relying on equality of regions in the trait solver. -This is fine for codegen, as we treat all erased regions as equal. We can however -lose equality information from HIR to MIR typeck. - -### 7. Removing ambiguity makes strictly more things compile - -We *should* not rely on ambiguity for things to compile. -Not doing that will cause future improvements to be breaking changes. - -### 8. semantic equality implies structural equality - -Two types being equal in the type system must mean that they have the same `TypeId`. - - [solve]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_trait_selection/solve/index.html [`Goal`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_trait_selection/traits/solve/struct.Goal.html [`Predicate`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.Predicate.html diff --git a/src/doc/rustc-dev-guide/src/stabilization_guide.md b/src/doc/rustc-dev-guide/src/stabilization_guide.md index 001ed25a5..9bc70f65c 100644 --- a/src/doc/rustc-dev-guide/src/stabilization_guide.md +++ b/src/doc/rustc-dev-guide/src/stabilization_guide.md @@ -109,7 +109,7 @@ to stabilize, something like (this example is taken from ```rust,ignore // pub(restricted) visibilities (RFC 1422) -(active, pub_restricted, "CURRENT_RUSTC_VERSION", Some(32409)), +(unstable, pub_restricted, "CURRENT_RUSTC_VERSION", Some(32409)), ``` The above line should be moved down to the area for "accepted" diff --git a/src/doc/rustc-dev-guide/src/tests/headers.md b/src/doc/rustc-dev-guide/src/tests/headers.md index f066dbbb5..fce2397e5 100644 --- a/src/doc/rustc-dev-guide/src/tests/headers.md +++ b/src/doc/rustc-dev-guide/src/tests/headers.md @@ -190,7 +190,7 @@ The following headers are generally available, and not specific to particular test suites. * `compile-flags` passes extra command-line args to the compiler, - e.g. `compile-flags -g` which forces debuginfo to be enabled. + e.g. `// compile-flags: -g` which forces debuginfo to be enabled. * `run-flags` passes extra args to the test if the test is to be executed. * `edition` controls the edition the test should be compiled with (defaults to 2015). Example usage: `// edition:2018`. diff --git a/src/doc/rustc-dev-guide/src/traits/unsize.md b/src/doc/rustc-dev-guide/src/traits/unsize.md new file mode 100644 index 000000000..b11760992 --- /dev/null +++ b/src/doc/rustc-dev-guide/src/traits/unsize.md @@ -0,0 +1,84 @@ +# [`CoerceUnsized`](https://doc.rust-lang.org/std/ops/trait.CoerceUnsized.html) + +`CoerceUnsized` is primarily concerned with data containers. When a struct +(typically, a smart pointer) implements `CoerceUnsized`, that means that the +data it points to is being unsized. + +Some implementors of `CoerceUnsized` include: +* `&T` +* `Arc<T>` +* `Box<T>` + +This trait is (eventually) intended to be implemented by user-written smart +pointers, and there are rules about when a type is allowed to implement +`CoerceUnsized` that are explained in the trait's documentation. + +# [`Unsize`](https://doc.rust-lang.org/std/marker/trait.Unsize.html) + +To contrast, the `Unsize` trait is concerned the actual types that are allowed +to be unsized. + +This is not intended to be implemented by users ever, since `Unsize` does not +instruct the compiler (namely codegen) *how* to unsize a type, just whether it +is allowed to be unsized. This is paired somewhat intimately with codegen +which must understand how types are represented and unsized. + +## Primitive unsizing implementations + +Built-in implementations are provided for: +* `T` -> `dyn Trait + 'a` when `T: Trait` (and `T: Sized + 'a`, and `Trait` + is object safe). +* `[T; N]` -> `[T]` + +## Structural implementations + +There are two implementations of `Unsize` which can be thought of as +structural: +* `(A1, A2, .., An): Unsize<(A1, A2, .., U)>` given `An: Unsize<U>`, which + allows the tail field of a tuple to be unsized. This is gated behind the + [`unsized_tuple_coercion`] feature. +* `Struct<.., Pi, .., Pj, ..>: Unsize<Struct<.., Ui, .., Uj, ..>>` given + `TailField<Pi, .., Pj>: Unsize<Ui, .. Uj>`, which allows the tail field of a + struct to be unsized if it is the only field that mentions generic parameters + `Pi`, .., `Pj` (which don't need to be contiguous). + +The rules for the latter implementation are slightly complicated, since they +may allow more than one parameter to be changed (not necessarily unsized) and +are best stated in terms of the tail field of the struct. + +[`unsized_tuple_coercion`]: https://doc.rust-lang.org/beta/unstable-book/language-features/unsized-tuple-coercion.html + +## Upcasting implementations + +Two things are called "upcasting" internally: +1. True upcasting `dyn SubTrait` -> `dyn SuperTrait` (this also allows + dropping auto traits and adjusting lifetimes, as below). +2. Dropping auto traits and adjusting the lifetimes of dyn trait + *without changing the principal[^1]*: + `dyn Trait + AutoTraits... + 'a` -> `dyn Trait + NewAutoTraits... + 'b` + when `AutoTraits` ⊇ `NewAutoTraits`, and `'a: 'b`. + +These may seem like different operations, since (1.) includes adjusting the +vtable of a dyn trait, while (2.) is a no-op. However, to the type system, +these are handled with much the same code. + +This built-in implementation of `Unsize` is the most involved, particularly +after [it was reworked](https://github.com/rust-lang/rust/pull/114036) to +support the complexities of associated types. + +Specifically, the upcasting algorithm involves: For each supertrait of the +source dyn trait's principal (including itself)... +1. Unify the super trait ref with the principal of the target (making sure + we only ever upcast to a true supertrait, and never [via an impl]). +2. For every auto trait in the source, check that it's present in the principal + (allowing us to drop auto traits, but never gain new ones). +3. For every projection in the source, check that it unifies with a single + projection in the target (since there may be more than one given + `trait Sub: Sup<.., A = i32> + Sup<.., A = u32>`). + +[via an impl]: https://github.com/rust-lang/rust/blob/f3457dbf84cd86d284454d12705861398ece76c3/tests/ui/traits/trait-upcasting/illegal-upcast-from-impl.rs#L19 + +Specifically, (3.) prevents a choice of projection bound to guide inference +unnecessarily, though it may guide inference when it is unambiguous. + +[^1]: The principal is the one non-auto trait of a `dyn Trait`.
\ No newline at end of file |