Repository: rust-lang/rust
Pull request: Flip "region lattice" in RegionKind doc comment

If we assume that references take their region covariantly, and use that to define the subtyping relationship of regions, `'empty` is ⊤ (top) and `'static` is ⊥ (bottom), and that `'a <: 'b` is defined as `'a >= 'b`. However, the RegionKind doc comment's "region lattice" had `'static` at Top. While this is perhaps technically correct (a so-called "region lattice" is not a "type lattice"), it confused me a lot, and took me half an hour to be like "no, ok, I *do* understand things correctly, this region lattice is just flipped from the subtype lattice". Seems better to just have them be the same!

I also took the opportunity to rewrite some parts of the comment with notes that would have helped me when starting out.

Bikesheds welcome (as long as they don't go on forever)!

For context: the comment "`'static` is Top" was [written in 2013](https://github.com/rust-lang/rust/commit/a896440ca1b93cc5dc6edd827ea2ae89602bfa9e#diff-8780054cdf09361c4ac2540c7f544ecfdc52a9e610822aabb8bcd2964affcb1cR430), before there was a [discussion in 2014](https://github.com/rust-lang/rust/issues/15699) that clarified that references take their regions covariantly, and `'a <: 'b` is defined as `'a >= 'b`.

See also Zulip thread: https://rust-lang.zulipchat.com/#narrow/channel/131828-t-compiler/topic/RegionKind.20rustc.20doc.20comment

Changed files:
filename: compiler/rustc_type_ir/src/region_kind.rs
patch: @@ -34,26 +34,26 @@ rustc_index::newtype_index! {
 /// In general, the region lattice looks like
 ///
 /// ```text
-/// static ----------+-----...------+       (greatest)
+/// empty(Un) --------                      (smallest)
+/// |                 \
+/// ...                \
+/// |                   \
+/// empty(U1) --         \
+/// |           \         placeholder(Un)
+/// |            \                  |
+/// empty(root)   placeholder(U1)   |
 /// |                |              |
-/// param regions    |              |
 /// |                |              |
 /// |                |              |
+/// param regions    |              |
 /// |                |              |
-/// empty(root)   placeholder(U1)   |
-/// |            /                  |
-/// |           /         placeholder(Un)
-/// empty(U1) --         /
-/// |                   /
-/// ...                /
-/// |                 /
-/// empty(Un) --------                      (smallest)
+/// static ----------+-----...------+       (greatest)
 /// ```
 ///
-/// Early-bound/free regions are the named lifetimes in scope from the
-/// function declaration. They have relationships to one another
-/// determined based on the declared relationships from the
-/// function.
+/// Lifetimes in scope from a function declaration are represented via
+/// [`RegionKind::ReEarlyParam`]/[`RegionKind::ReLateParam`]. They
+/// have relationships to one another and `'static` based on the
+/// declared relationships from the function.
 ///
 /// Note that inference variables and bound regions are not included
 /// in this diagram. In the case of inference variables, they should
@@ -62,29 +62,36 @@ rustc_index::newtype_index! {
 /// include -- the diagram indicates the relationship between free
 /// regions.
 ///
+/// You can read more about the distinction between early and late bound
+/// parameters in the rustc dev guide: [Early vs Late bound parameters].
+///
+/// A note on subtyping: If we assume that references take their region
+/// covariantly, and use that to define the subtyping relationship of regions,
+/// it may be somewhat surprising that `'empty` is Top and `'static` is Bottom,
+/// and that "`'a` is a subtype of `'b`" is defined as "`'a` is bigger than
+/// `'b`" - good to keep in mind.
+///
 /// ## Inference variables
 ///
 /// During region inference, we sometimes create inference variables,
-/// represented as `ReVar`. These will be inferred by the code in
-/// `infer::lexical_region_resolve` to some free region from the
-/// lattice above (the minimal region that meets the
+/// represented as [`RegionKind::ReVar`]. These will be inferred by
+/// the code in `infer::lexical_region_resolve` to some free region
+/// from the lattice above (the minimal region that meets the
 /// constraints).
 ///
 /// During NLL checking, where regions are defined differently, we
-/// also use `ReVar` -- in that case, the index is used to index into
-/// the NLL region checker's data structures. The variable may in fact
-/// represent either a free region or an inference variable, in that
-/// case.
+/// also use [`RegionKind::ReVar`] -- in that case, the index is used
+/// to index into the NLL region checker's data structures. The
+/// variable may in fact represent either a free region or an
+/// inference variable, in that case.
 ///
 /// ## Bound Regions
 ///
 /// These are regions that are stored behind a binder and must be instantiated
-/// with some concrete region before being used. There are two kind of
-/// bound regions: early-bound, which are bound in an item's `Generics`,
-/// and are instantiated by an `GenericArgs`, and late-bound, which are part of
-/// higher-ranked types (e.g., `for<'a> fn(&'a ())`), and are instantiated by
-/// the likes of `liberate_late_bound_regions`. The distinction exists
-/// because higher-ranked lifetimes aren't supported in all places. See [1][2].
+/// with some concrete region before being used. A type can be wrapped in a
+/// `Binder`, which introduces new type/const/lifetime variables (e.g., `for<'a>
+/// fn(&'a ())`). These parameters are referred to via [`RegionKind::ReBound`].
+/// You can instantiate them by the likes of `liberate_late_bound_regions`.
 ///
 /// Unlike `Param`s, bound regions are not supposed to exist "in the wild"
 /// outside their binder, e.g., in types passed to type inference, and
@@ -123,8 +130,7 @@ rustc_index::newtype_index! {
 /// happen, you can use `leak_check`. This is more clearly explained
 /// by the [rustc dev guide].
 ///
-/// [1]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
-/// [2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
+/// [Early vs Late bound parameters]: https://rustc-dev-guide.rust-lang.org/early-late-parameters.html
 /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
 #[derive_where(Clone, Copy, Hash, PartialEq; I: Interner)]
 #[derive(GenericTypeVisitable)]
@@ -160,7 +166,7 @@ pub enum RegionKind<I: Interner> {
     /// more info about early and late bound lifetime parameters.
     ReLateParam(I::LateParamRegion),
 
-    /// Static data that has an "infinite" lifetime. Top in the region lattice.
+    /// Static data that has an "infinite" lifetime. Bottom in the region lattice.
     ReStatic,
 
     /// A region variable. Should not exist outside of type inference.

filename: src/doc/rustc-dev-guide/src/early-late-parameters.md
patch: @@ -3,6 +3,12 @@
 
 > **NOTE**: This chapter largely talks about early/late bound as being solely relevant when discussing function item types/function definitions. This is potentially not completely true, async blocks and closures should likely be discussed somewhat in this chapter.
 
+See also these blog posts from when the distinction between early and late bound parameters was
+introduced: [Intermingled parameter lists] and [Intermingled parameter lists, take 2].
+
+[Intermingled parameter lists]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
+[Intermingled parameter lists, take 2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
+
 ## What does it mean to be "early" bound or "late" bound
 
 Every function definition has a corresponding ZST that implements the `Fn*` traits known as a [function item type][function_item_type]. This part of the chapter will talk a little bit about the "desugaring" of function item types as it is useful context for explaining the difference between early bound and late bound generic parameters.