Rust: non-lexical lifetimes (NLL) tracking issue

[nikomatsakis]

This issue tracks the status of the transition to non-lexical lifetimes and a MIR-based borrow-checker. Both of these are jargon-y terms for compiler authors: the effect of these features on end-users is, simply put, that the compiler accepts a wider range of code with fewer bugs (and, hopefully, better error messages). We will refer to the combination of the above as NLL.

Key facts for getting involved

• Weekly triage meeting Wednesdays at 3:30pm Boston time (see in your timezone)
  
  
  
  • Join the chat on Zulip
  
  
  • Notes in this dropbox paper document
  
  
  • If you are unable to attend, minutes and further discussion takes place on this internals thread.
  
  
  • Ask @nikomatsakis (on Zulip, ideally) to be added to the calendar invite.
  
  
• You can also find a YouTube playlist of pair programming videos; these are sessions where we are working through how to solve a particular problem, often explaining big parts of the system on the way.

Implementation plan

• [x] Initial prototype: features available on nightly builds with #![feature(nll)] for experimentation.
• [ ] Valid code works: (issues labeled with [NLL-complete])
  
  
  
  • [x] all run-pass tests pass
  
  
  • [x] bootstrap builds with nll enabled: see #51823.
    
    
    
    
    
    • summary: We have bootstrapped at least once. We need to integrate such bootstrapping into the CI to ensure it stops breaking.
    
    
    
  
  
  • [x] crater run with nll enabled passes without regressions
  
  
  • see #52217 for the set of ICEs from recent crater run.
  
  
• [ ] Invalid code gets errors: (issues labeled with [NLL-sound])
  
  
  
  • [ ] compile-fail/ui tests generate errors in the right places (possibly with bad diagnostics)
    
    
    
    
    
    • see #52663 as evidence that we generate errors in all cases where expected for the ui test suite. (Current plan for compile-fail suite is to port majority of those tests to ui)
    
    
    
  
  
• [ ] Performance is good (issues labeled with [NLL-performant])
  
  
  
  • see this dropbox paper which tracks profiling information
  
  
  • see also the NLL perf dashboard which compares running cargo check without and with NLL turned on, so that we can see a summary of the current performance impact on the compiler's static analyses in isolation.
  
  
• [x] Future compatibility warnings on stable: Once crater runs are clean, we can enable the future-compatibility warnings on stable: see #46908 and #52681
  
  
  
  • [x] currently, due to #52681, we are issuing compatibility warnings on the 2018 edition.
  
  
  • [x] next step is to migrate the 2015 edition in the same manner (#57804)
  
  
• [ ] Diagnostic parity: (issues labeled with [NLL-diagnostics]) Ensure that all diagnostics are "as good or better" than before.
  
  
  
  • We will primarily validate this from our test base, but also consider errors that are reported "from the wild".
  
  
  • [x] round one: #49862
  
  
  • [x] round two: #52663
  
  
  • [ ] round three: #54528; remaining work items are cards on https://github.com/rust-lang/rust/projects/10
  
  
• [ ] transition from migration mode to full NLL
  
  
  
  • [x] NLL warnings (downgraded from errors) become errors again
  
  
  • [x] as an intermediate step, potentially use a deny-by-default lint before making these hard errors
  
  
• [ ] Feature stabilized: NLL and MIR-based borrow checker enabled by default,
• [x] AST-based borrow checker removed: https://github.com/rust-lang/rust/pull/64790.

Many of the work items for unchecked bullets above are gathered into one place on #57895

How to join the working group

If you'd like to help, please join the NLL working group -- just leave a comment below or ping @nikomatsakis on gitter and you will be added to the @rust-lang/wg-compiler-nll team. You will then get occasional pings (e.g., when new mentoring instructions are available or when looking for help), as well as being eligible to be assigned to issues and so forth. We discuss things on the WG-compiler-nll channel on Gitter.

How to find an issue to work on

To find important issues, use one of the following queries:

• Top priority right now are issues tagged with NLL-Complete, corresponding to code that should be accepted but isn't right now.
• Next priority are issues tagged with NLL-sound, corresponding to code that should get errors, but isn't right now.
• Next priority are issues tagged with NLL-diagnostics, corresponding to low quality error messages.
• Issues tagged with NLL-performant, corresponding to cases where NLL analysis takes too long.

You may also wish to look for E-mentor issues, which means that they have mentoring instructions. Also, if an issue is assigned, then someone is supposed to be working on it, but it's worth checking if they have made progress and pinging them -- people often get busy with other things.

Issues tagged with [NLL-deferred] are low priority right now, but if one strikes your fancy, feel free to tackle it!

How are issues are organized

All issues related to NLL are tagged with WG-compiler-nll. They are further tagged with a NLL-foo label to indicate a subcategory. Issues that have [no NLL-label] are considered "untriaged" and need to be sorted. Issues tagged with [NLL-deferred] are low priority right now.

Finally, you can always take a look at the full list of NLL-related issues.

In particular, issues tagged with E-mentor are those that contain mentoring instructions that can help you get started.

Issues (and pull requests) tagged with I-nominated are meant to be reviewed by the WG-compiler-nll at each weekly meeting. Here's the current nominated list.

If you can't find anything, reach out to @nikomatsakis on gitter.

Other issues

This section tracks related issues and notes.

Bugs in AST borrow check fixed in MIR borrowck

https://github.com/rust-lang/rust/issues/47366 tracks known bugs from the AST borrow checker that were fixed in the MIR borrow checker. For each such bug, we have added a test to the repo with #![feature(nll)] and then closed the relevant issue (obviously, though, the bug will still be reproducable until the MIR-based borrow checker is stabilized, presuming one uses the AST-based borrow checker). You can also search for things tagged with [NLL-fixed-by-NLL].

Questions to be resolved before stabilization

• [x] #46036: infinite loop false edges
• [x] NLL should identify and respect the lifetime annotations that the user wrote #47184
  

Possible extensions

• [ ] refine liveness with maybe-initialized at greater resolution than a single variable
  

[nikomatsakis]

I've written up a gist with the initial draft of a plan. It lays out the first few steps anyway and some of the initial vision. I'll just copy-and-paste the end here, which lays out some of the PRs I think would make sense:

(list moved to header)

[nikomatsakis]

@Nashenas88 has expressed some interest in doing this! It occurs to me that this project may be big enough for multiple people, too.

cc @rust-lang/compiler

[spastorino]

have talked with @nikomatsakis and I'm joining this group 😄

[chrisvittal]

With #45013 pretty much set. I'm willing to work on testing infrastructure. I just need to know what we want and what parts of the code I need to look at.

[nikomatsakis]

For those who will hack on NLL: right now, the "tip" of NLL development has not yet landed in master. In order to keep things moving, we're adopting the following strategy.

There is a nll-master branch on my fork of Rust. This contains the NLL work that is considered "done". You can open PRs against that branch on my repository.

In terms of rebasing etc, this branch works like Rust master: that is, until your PR lands, you have to rebase it against nll-master. But once a PR lands there, you are done -- I will take care of rebasing it and keeping it up to date.

This branch is not intended to live permanently far from master -- I will rebase it as needed, and I will always be trying to land the next logical chunk from it. However, this removes main Rust master as the central "gate" for Rust development.

EDIT: This is no longer true.

[gaurikholkar]

Hi @nikomatsakis , I would like to join the group!

[nikomatsakis]

UPDATE: @pnkfelix and I talked over the plan today, and I updated the tracking issue with some new milestones. The major change is that our first push will be to get run-pass working without any ICEs. @spastorino did a run-pass run and found the set of ICEs and is working on opening up related issues.

cc @rust-lang/wg-compiler-nll

[jonhoo]

A minor point from a discussion with @nikomatsakis on Tuesday -- it'd be really neat if the compiler could warn when it detects an extra scope that is now unnecessary due to nll. Essentially when it sees something like:

let x = {
    // something that uses &mut foo
};
// something that uses &mut foo
// something that uses x

[SimonSapin]

It’d be great for that lint to exist, but I’d prefer it not to be enabled by default in Nightly until at least after NLL is enabled by default on Stable.

[akshaynanavati]

There is a stack overflow question here: https://stackoverflow.com/questions/50111949/mutable-borrow-in-a-loop. The solution is to use NLL. However, this does not work with the most recent nightly (1.28). Error below:

error[E0499]: cannot borrow `self.bar` as mutable more than once at a time
  --> src/bin/nll.rs:25:23
   |
25 |             let baz = self.bar.get_baz_mut();
   |                       ^^^^^^^^ mutable borrow starts here in previous iteration of loop
   |
note: borrowed value must be valid for the anonymous lifetime #1 defined on the method body at 23:5...
  --> src/bin/nll.rs:23:5
   |
23 | /     fn foo(&mut self) -> Option<&mut Baz> {
24 | |         for _i in 0..4 {
25 | |             let baz = self.bar.get_baz_mut();
26 | |             if baz.x == 0 {
...  |
30 | |         None
31 | |     }
   | |_____^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.
error: Could not compile `rust-playground`.

To learn more, run the command again with --verbose.

The code I am running is:

#![feature(nll)]

struct Baz {
    x: usize,
    y: usize,
}

struct Bar {
    baz: Baz,
}

impl Bar {
    fn get_baz_mut(&mut self) -> &mut Baz {
        &mut self.baz
    }
}

struct Foo {
    bar: Bar,
}

impl Foo {
    fn foo(&mut self) -> Option<&mut Baz> {
        for _i in 0..4 {
            let baz = self.bar.get_baz_mut();
            if baz.x == 0 {
                return Some(baz);
            }
        }
        None
    }
}

// Just here to get it to compile as a binary
fn main() {
    println!("Hello world");
}

Did anything change with the way nll works? Any help would be appreciated on how to get the above code to compile (it is a simplified version of real code I'm trying to write).

[pnkfelix]

@akshaynanavati we have had to cut back slightly on some of the ambititions of the original NLL plan, because the first draft of the analysis, while very expressive, was also too slow and thus would have caused too big of a hit to our compile times.

• In particular PR #50593 was the big case of where we cut back on our ambitions
• We anticipated this would regress certain cases, namely #51526

Our long-term plan is to (re)enable the more expressive analysis once we figure out how to make it fast enough. Our short-term plan is to deploy a less expressive analysis just to get a number of bug fixes to the borrow-checker (as well as what improvements are in this less expressive analysis) deployed as soon as possible.

Anyway, I am not 100% sure if the case you outline falls into the category of things that we plan to enable eventually, but it certainly seems similar to other such cases to my eye.

One final thing: NLL does allow this variant of your code to compile (playground:

#![feature(nll)]

struct Baz {
    x: usize,
    y: usize,
}

struct Bar {
    baz: Baz,
}

impl Bar {
    fn get_baz_mut(&mut self) -> &mut Baz {
        &mut self.baz
    }
}

struct Foo {
    bar: Bar,
}

impl Foo {
    fn foo(&mut self) -> Option<&mut Baz> {
        for _i in 0..4 {
            let baz = self.bar.get_baz_mut();
            if baz.x == 0 {
                return Some(self.bar.get_baz_mut()); // (note original code returned `baz` here)
            }
        }
        None
    }
}

// Just here to get it to compile as a binary
fn main() {
    println!("Hello world");
}

So, not ideal, but its still better than the old borrow-checker, which still rejects the variant I have written above.

[pnkfelix]

In language design team meeting last night, it was explained to me that if we intend for NLL to actually be turned on in stable Rust as part of the release of the 2018 edition, then we should be going through the approval process with the relevant stakeholders.

The first step to that, if I understand correctly, is to ensure the relevant stake holders are actually identified. In this case, I think that is both T-compiler and T-lang

So: I added language design team to this tracking issue

[pnkfelix]

So, in terms of the approval process for the NLL feature, the description on this issue describes the following overall goals. (There are some other milestones listed that I deemed to be "tasks" and so I'm not listing them here.)

• Valid code works (issues labeled with NLL-complete)
• Invalid code gets errors (issues labeled with NLL-sound)
• Performance is good (issues labeled with NLL-performant)
• Diagnostic parity (issues labeled with NLL-diagnostics)

Here is where I think we are on each goal:

• For "valid code works", we have addressed the most important issues here. The remaining items on NLL-complete can probably be considered "bugs to fix"; none of them are show stoppers.
  
  
  
  • It would be good to focus on trying to get our CI to bootstrap rustc with NLL turned on, just as a way to keep ourselves honest on this front. See #51823
  
  
• For "invalid code gets errors": I know of only one unresolved issue on NLL-sound that might cause us to abort stabilizing NLL, namely #47184: "NLL should identify and respect the lifetime annotations that the user wrote" (within a function body).
  
  
  
  • However, that depends on whether #47184 is considered an unsoundness in NLL itself.
    
    
    
    
    
    • It does break users' expectations (which is bad and should be fixed eventually).
    
    
    
    • But, does it imply the existence of an exploit one could use to witness undefined behavior?
    
    
    
    • In particular, is there a scenario where a crate could be using unsafe code and relying on certain types to be enforced, and NLL's failure to enforce certain lifetimes in internal type annotations could cause the invariants of that unsafe code to be broken?
    
    
    
    • It would be good (for the NLL working group and also the stake holders) to look at the cases that remain to be addressed and try to concoct such a scenario that exploits them. That would help us determine how to prioritize #47184, which has largely fallen by the wayside because the remaining cases are assumed to be relatively rare (and somewhat difficult to address in a clean manner)
    
    
    
  
  
• For "Performance is good", the NLL perf dashboard shows that for the majority of our benchmarks, NLL imposes less than a 1.15x hit to performance to cargo check.
  
  
  
  • There are a couple exceptional cases that hit us hard.
  
  
  • We do hope to improve performance further, but nothing is guaranteed.
  
  
  • The question for the stakeholders here: What level of performance impact is acceptable for initially stabilizing this feature?
    
    
    
    
    
    • For example, would a <= 1.2x hit to performance in 90% of the cases be acceptable?
    
    
    
  
  
• Finally, for "Diagnostic parity", I am frankly thrilled with where NLL currently stands with respect to diagnostics.
  
  
  
  • #52663 categorizes all of the known potential diagnostic regressions into buckets
  
  
  • The team has done great work on NLL's diagnostics
    
    
    
    
    
    • issues like #52663 tend to draw focus on the cases where NLL regresses diagnostics.
    
    
    
    • but many issues simply have no change to the UX at all
    
    
    
    • and its nice to note the places where NLL clearly presents an improved user experience. (Here is one recent example).
    
    
    
  
  
  • so, having said all that, there are these so-called "buckets" on #52663 ...
  
  
  • what the stakeholders need to determine is: if any or all of these buckets on #52663 were left unaddressed, would that warrant pulling the plug on letting NLL leak into stable Rust?
  
  

[pnkfelix]

Based on a conversation in the language design team meeting last night, and based on my evaluation of the current state of NLL (as well as the forward trajectory of its development), I think it would be good to encourage the stake-holders on T-compiler and T-lang to weigh in on whether they are comfortable with NLL riding the trains to stabilization.

The way things currently stand:

• there is an unstable #![feature(nll)] you can opt into to get NLL with hard errors on either the 2015 or 2018 edition
• if you don't do that, then currently the 2018 edition toggles on a "migration mode" (#52681) which is meant to be NLL with future-compatibilty warnings when warranted (modulo bugs like #53026); that's why I'm saying NLL will currently ride the trains to stabilization.
• if things look good overall, in some near-term future release we will turn on migration mode for both editions. But the timing for when we do that has not been established, in part because we want to first get feedback from the initial deployment as part of the 2018 edition.

So, lets see what people think about that plan given the status report immediately above.

@rfcbot fcp merge

[rfcbot]

Team member @pnkfelix has proposed to merge this. The next step is review by the rest of the tagged teams:

• [ ] @Zoxc
• [x] @aturon
• [x] @cramertj
• [x] @eddyb
• [ ] @estebank
• [x] @joshtriplett
• [x] @michaelwoerister
• [x] @nagisa
• [x] @nikomatsakis
• [x] @nrc
• [x] @oli-obk
• [x] @petrochenkov
• [x] @pnkfelix
• [x] @scottmcm
• [x] @varkor
• [x] @withoutboats

Concerns:

• box-is-special resolved by https://github.com/rust-lang/rust/issues/43234#issuecomment-411873910
• disjoint-liveness-ranges resolved by https://github.com/rust-lang/rust/issues/43234#issuecomment-411873978
• lifetime-annotations-get-no-respect resolved by https://github.com/rust-lang/rust/issues/43234#issuecomment-419058149
• match-vs-let resolved by https://github.com/rust-lang/rust/issues/43234#issuecomment-418832780
• need-perf-comparison-against-incremental resolved by https://github.com/rust-lang/rust/issues/43234#issuecomment-419058173

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[joshtriplett]

Reading through both this issue and https://github.com/rust-lang/rust/pull/52681 , I have a question for documentation purposes: does anyone have an example of correct code that NLL rejects but the old borrow checker accepts? Would any such code be considered a bug in NLL, or are there known cases that will stay that way?

[Mark-Simulacrum]

@joshtriplett I believe this is the correct search, but not sure: https://github.com/rust-lang/rust/issues?utf8=%E2%9C%93&q=is%3Aopen+is%3Aissue+label%3ANLL-fixed-by-NLL+label%3A%22I-unsound+%F0%9F%92%A5%22+

[cramertj]

@Mark-Simulacrum Those are examples of incorrect code that NLL rejects but the old borrow checker accepts. I think that @pnkfelix's above link to nll completeness is closer to what @joshtriplett is looking for, e.g. this regression due to two-phase borrows not being quite as permissive as they could be.

[pnkfelix]

@joshtriplett while @cramertj has the right idea in pointing to #52934, that isse was (I think) "just" a mistake in how I implemented link up into the 2018 edition.

I think a more worrisome example are these two tests that came from #40510 (and now tracked in #53040), both of which are accepted by the AST borrow-checker but are rejected by NLL.

https://github.com/rust-lang/rust/blob/59fa6bd6c14eebd213884da08a33639b4c848bb3/src/test/ui/issue-40510-1.rs

has no errors in AST-borrowck but has these errors in NLL:

https://github.com/rust-lang/rust/blob/59fa6bd6c14eebd213884da08a33639b4c848bb3/src/test/ui/issue-40510-1.nll.stderr#L1-L16

and

https://github.com/rust-lang/rust/blob/59fa6bd6c14eebd213884da08a33639b4c848bb3/src/test/ui/issue-40510-3.rs

has no errors in AST-borrowck but has these errors in NLL:

https://github.com/rust-lang/rust/blob/59fa6bd6c14eebd213884da08a33639b4c848bb3/src/test/ui/issue-40510-3.nll.stderr#L1-L19

[pnkfelix]

(having said that, there was some other somewhat similar looking construct with nested closures that niko argued was incorrect code. So I'd want to compare against that before I state with full confidence that these particular tests represent correct code.)

[pnkfelix]

ah yes, this is the argument from niko that I was thinking of: https://github.com/rust-lang/rust/issues/49824#issuecomment-384391152

[pnkfelix]

Filed #53040 so that we have a place to give more visibility to this particular change in semantics.

[alexreg]

@pnkfelix Those are odd definitions of "sound" and "complete". I would define "sound" as "NLL-valid code works (compiles and is memory-safe)" and "complete" as "all NLL-valid code is expressible" or "all NLLs are expressible in code".

[michaelwoerister]

I think we should measure how NLL performance stacks up with incremental builds. Right now, we only seem to measure NLL build times with non-incremental builds, but the two use-cases where it has the most impact (cargo check and debug builds) are incremental by default. cc @rust-lang/wg-compiler-performance

[nikomatsakis]

I think that the question which @joshtriplett raised is quite subtle. e.g., @cramertj wrote:

Those are examples of incorrect code that NLL rejects but the old borrow checker accepts. I think that @pnkfelix's above link to nll completeness is closer to what @joshtriplett is looking for, e.g. this regression due to two-phase borrows not being quite as permissive as they could be.

I would say something like this:

• Examples like the one in https://github.com/rust-lang/rust/issues/51915 ought never to have been accepted at all, but they were (incorrectly)
  
  
  
  • i.e., they violated the "intended" rules for the AST borrow checker
  
  
• The NLL type checker correctly rejects them
• However, we could make the NLL type checker accept them by extending 2-phase borrows

I guess it all hinges on what one means by "correct code" -- given that we could change the rules to accept the code, presumably it cannot actually "go wrong" at runtime (but variations on that same code might).

Anyway, this is the example from #51915:

struct S {
    a: &'static str,
}

fn f(_: &mut S, _: &str) {
}

fn main() {
    let mut s = S {
        a: "a",
    };

    f(&mut s, s.a); // ERROR!
}

Note that accessing s.a is not allowed because s is mutably borrowed at that point.

[nikomatsakis]

@pnkfelix

For "invalid code gets errors": I know of only one unresolved issue on NLL-sound that might cause us to abort stabilizing NLL, namely #47184: "NLL should identify and respect the lifetime annotations that the user wrote" (within a function body).

My opinion is that we have to fix this before stabilizing NLL — doing otherwise will allow us to accept code that we ought to be rejecting, and it's also just very confusing in practice. That is, I often try to illustrate small problems using hand-written annotations and wind up feeling confused because NLL is ignoring them.

That said, I think we will. It's "just engineering". That said, I don't know how to do it yet ;) but I think that should be a big priority for us.

[pnkfelix]

@nikomatsakis well heck lets use the rfcbot to track this properly then.

[pnkfelix]

@rfcbot concern lifetime-annotations-get-no-respect

We should resolve #47184 before stabilizing NLL

[nikomatsakis]

@rfcbot concern disjoint-liveness-ranges

There are some things I am concerned about with NLL that I'd like to resolve before we make any final decision regarding stabilization. These are cases where NLL perhaps accepts "too much". One such item has to do with the use of liveness, and in particular the implications of disjoint liveness ranges.

Consider this program, which is accepted by NLL today:

#![feature(nll)]

fn main() {
    let mut x;

    {
        let y = 33;
        x = &y;
        println!("{:?}", x);
    }

    {
        let z = 33;
        x = &z;
        println!("{:?}", x);
    }
}

You might ask, what is the lifetime of x here? The answer is that, since x is assigned twice, it has in a sense two disjoint lifetimes -- one covering part of the first block, where it references y, and one covering part of the second block, where it references z. It does not carry a live value anywhere else and hence it is not an error that y gets dropped while x is still "in use".

However, this treatment only extends to local variables. If you e.g. reassign fields, we still consider the local variable to be live. Therefore, this variant of the above program gets an error:

#![feature(nll)]

fn main() {
    let mut x = (&22,);

    {
        let y = 33;
        x.0 = &y;
        println!("{:?}", x);
    }

    {
        let z = 33;
        x.0 = &z;
        println!("{:?}", x);
    }
}

Here, we are assigning to x.0 -- this is considered a "use" of x, and hence x is still "live" in between blocks. Therefore, we get an error:

error[E0597]: `y` does not live long enough
  --> src/main.rs:8:15
   |
8  |         x.0 = &y;
   |               ^^ borrowed value does not live long enough
9  |         println!("{:?}", x);
10 |     }
   |     - `y` dropped here while still borrowed
...
14 |         x.0 = &y;
   |         -------- borrow later used here

I'm not sure yet how I feel about all of this.

I'm not sure how to be more conservative or what the impact would be. I could imagine trying to do something like forcing the variable to be "live" from the point where it is declared until its last use -- or perhaps forcing it to be live from the first assignment until final use, and not allowing it to get dead in between.

As an alternative, it is plausible that we could -- in the future -- extend the liveness analysis to operate not on entire variables (like x) but also on fields like x.0, which would allow us to accept the second program. @pnkfelix and I had rejected that idea because it seemed like it would be more complex and might also be surprising in cases like struct Foo<'a> { f: &'a u32, g: &'a u32 } -- here, if either f or g is live, they will link to the same lifetime ('a), and hence the user might be surprised by some of the resulting interactions.

[nikomatsakis]

cc @shepmaster on the previous point about disjoint liveness ranges, this is something that they encountered when answering stack overflow questions and hence they may have some thoughts about what behavior is best.

[nikomatsakis]

@rfcbot concern match-vs-let

This is not really specific to NLL, but I'm going to add that we should definitively resolve #53114 -- the behavior around match foo { _ => () } and let _ = ....

[joshtriplett]

@nikomatsakis FWIW, I don't feel like disjoint-liveness-ranges is a blocker. That seems like the compiler understanding the code well enough to confirm safety in one case, and just not in all similar cases. I don't think we should prevent the compiler from accepting the (correct) code for that case.

[shepmaster]

I don't feel like disjoint-liveness-ranges is a blocker.

Overall, I'd agree. The majority of people are going to trust the compiler. If it compiles successfully, they will accept that and move on. It's when then compiler fails that people get suspicious. Permit me a meme:

The big selling point of the NLL feature is that us normal, non-compiler-developer, non-type-theorists have found some cases and thought "hey, this should work" and we were right. These were common enough to come up regularly in various support avenues.

The two disjoint-liveness-ranges examples feel very uncommon, so it seems people are unlikely to even think to write them to start with... although of course they will, given a large enough sample size. Once enough people bang on it, eventually someone will wonder why case A works and B doesn't, but maybe you'll have updated the borrow checker by or before then! 😇

---

The thing that makes me sad about it is that it will weaken some of our teaching tools, or at least make them one step further from the truth. We can no longer say something akin to "x is a variable that is a reference with a lifetime corresponding from line X to line Y" and encompass the complete situation. Now either the variable's type changes over time ("reference to T valid X:Y" to "reference to T valid W:Z") or the type becomes more complicated ("reference to T valid (X:Y)∪(W:Z)").

Likewise, this is another case of the compiler being able to write something that the programmer cannot (although this is already true here, it's just moreso now).

[shepmaster]

The big selling point of the NLL feature

IMO, the big weakness of NLL is that it's been long enough in coming that it's morphed into a mystical "this will solve all deficiencies in the borrow checker" switch. This is exacerbated by being intertwined with the 2018 edition.

I'm dreading the influx of people saying "Rust 2018 has NLL and I tried my code again and it still doesn't work" and having to point towards Polonius and trying to explain the concepts of location-invariance that I don't understand well (at all?) myself. I understand the hard technical issues underlying it, but I wish that NLL could have been an undersold, slow burn of gradual improvement.

I don't know that anything can be done about this now, however. The allure of NLL permeates those who keep up with Rust, and the edition marketing is in swing. Perhaps I'm just being overly negative...

[nikomatsakis]

@rfcbot resolve disjoint-live-ranges

Per the comments of @joshtriplett @shepmaster, I am going to mark my concern as resolved. To elaborate a bit on what I'm thinking right now:

That seems like the compiler understanding the code well enough to confirm safety in one case, and just not in all similar cases.

I tend to agree, though I think it's tricky to figure out where to draw the line here.

As a bit of background, the lexical regions we have today were motivated by the idea that the workings of the borrow checker itself should be simple, so that people could understand the rules, even if they were imprecise, and have a clear model for how to fix them when errors arose.

I think time has shown that more precise rules would be better: people already have a sort of fuzzy view of how the inference and rules work as is, and having fewer errors can only help; besides, once you do have a precise picture, the limitations of the current rules are fairly substantial and hence even more annoying. That seems to suggest that having smarter and smarter rules is generally good.

But I do feel like there is some limit. I want the rules to be something where you can develop an "intuitive feel", hopefully, that works most of the time. This -- coupled hopefully with better and better error messages that help elucidate on how the compiler views things -- seems like the golden target.

I think what makes me feel ok about "disjoint uses" is basically that we are achieving this intuitive feel but not more. That is, the outlier here is really the x.0 = ... case, where we lose precision relative to this intuitive definition.

This gives us some metric now to judge various extensions: do they enable us to reach this "intuitive story" I told above in more cases, or do they go beyond that intuitive story? The former feel like "corrections" to the current NLL implementation in a sense (they are not fixing bugs of course, but they basically smooth out the mental model). The latter feel like "extensions".

I feel like our goal should be that deviations from the "intuitive story" are something you encounter relatively late and/or don't notice at first. Too many extensions and exceptions will be quite confusing.

(As an example of what I see as an "extension", 2-phase borrows goes beyond that mental model. It feels like an extension. This relates e.g. to the question of #51915 -- basically how often to apply 2PB. But I'll leave that for another comment.)

[nikomatsakis]

@rfcbot concern box-is-special

Something else I want to highlight is that the NLL codebase in general made the decision to stop trying to pretend that Box is not special. This affects other language design points as well so I want to get people's "blessing" here and make sure it doesn't occur silently.

Let me give an example. The following snippet only compiles with NLL enabled:

fn main() {
    let mut x = Box::new((vec![22], vec![44]));

    let y = &mut x.0;
    let z = &mut x.1;

    println!("{:?}", y);
    println!("{:?}", z);    
}

Here, the old AST-based borrow checker treats a borrow of x.0 as being a borrow of all of x, because x is a box. The NLL-based checker does not do that.

However, these AST-based checks are actually inconsistent. There are some cases where it still treats Box as special. For example, you can move out of a box with let y = x.0 (not true of any other "smart pointer" type). And this compiles:

fn foo(x: Box<&mut u32>) -> &mut u32 {
    &mut **x
}

The reason that this example is interesting is subtle: note that the box x will be freed when foo returns -- but we are returning a borrowed reference to the &mut within. This would ordinarily not be permitted. You can't have a destructor execute while the contents of the type are borrowed. However, we've since special-cased this for boxes. It can be considered (imo) a derived property of the #[may_dangle] attribute ("dangly paths"), but for the moment we've special-cased Box here rather than shoot for a more general extension (it's not relevant to things like Rc, since they only permit shared borrows; one could imagine though that writing a similar function that uses Vec<&mut u32> and having it work).

This also comes up with moves. For example, the AST-based checker rejects this program, but the MIR-based checker does not:

// #![feature(nll)]
#![allow(unused)]

fn foo(x: Box<(&mut u32, &mut u32)>) {
    let a = x.0;
    let b = x.1;
}

(I think there are still some cases where the MIR-based checker fails to treat Box as special -- and probably still other cases where the AST-based checker accidentally treats Box as a special. Presuming that we have decided to treat Box specially, though, this leaves us room to make improvements around Box.)

(I also think that it would be possible to extend this same treatment to other types in a fairly straightforward way. Some kind of "pure" trait or annotation would suffice. Basically what we need to know that dereferencing said smart pointer will act like a true pointer, and hence have no side-effects, always return the same memory, etc. But I'd rather approach that as a future extension.)

[nikomatsakis]

It's interesting to consider the box-is-special concern in light of my desire for a coherent mental model. I feel like this is a case where we correct a "deviation" from the mental model (i.e., I think of T and Box<T> as equivalent apart from memory layout), and hence a "correction", but smart pointers are common enough that the failure of other pointers to behave this way might be a concern.

Still, the most common smart pointers are Rc and Arc, and neither of those imparts ownership of its contents, hence these concerns don't really apply. In particular, shared derefs generally "just work".

[cramertj]

@nikomatsakis

I also think that it would be possible to extend this same treatment to other types in a fairly straightforward way. Some kind of "pure" trait or annotation would suffice. Basically what we need to know that dereferencing said smart pointer will act like a true pointer, and hence have no side-effects, always return the same memory, etc. But I'd rather approach that as a future extension.

I think this, along with DerefMove, is already something that we need at some point (e.g. to support overlapping borrows of disjoint fields), so I don't feel particularly concerned about extending the capabilities of Box and other hypothetical DerefMove + DerefPure types under NLL.

[nikomatsakis]

@cramertj makes sense, yes

[nikomatsakis]

@rfcbot resolve box-is-special

[nikomatsakis]

@rfcbot resolve disjoint-liveness-ranges

[pnkfelix]

@rfcbot concern need-perf-comparison-against-incremental

@michaelwoerister wrote in a comment above

I think we should measure how NLL performance stacks up with incremental builds. Right now, we only seem to measure NLL build times with non-incremental builds, but the two use-cases where it has the most impact (cargo check and debug builds) are incremental by default. cc @rust-lang/wg-compiler-performance

This seems like a legitimate concern, in that we should at least be able to easily evaluate the performance impact of NLL in these common cases before we stabilize it.

[pnkfelix]

@alexreg wrote:

@pnkfelix Those are odd definitions of "sound" and "complete". I would define "sound" as "NLL-valid code works (compiles and is memory-safe)" and "complete" as "all NLL-valid code is expressible" or "all NLLs are expressible in code".

I don't remember anymore who came up with the particular labels we are using, but the idea (in the context of type-systems) that "soundness" is about rejecting erroneous programs, while "completeness" is about accepting the error-free ones, is pretty well-established.

• A rule of thumb I like to keep the terms straight: a hypothetical type-system that rejects all programs is trivially sound; it is just far more incomplete than anyone would be willing to accept.
• And a type-system that accepts all programs (or parse trees, etc) is likewise trivially complete; it is also unsound (but apparenty there's a big audience of developers willing to accept that 😉 ).

In any case, and most important of all, I think we've found the labels useful for our own purposes.

[alexreg]

@pnkfelix Yeah, I see they're correct now. Just the phrasing caught me off guard, since a) I am more used to talking about soundness and completeness of logical systems (even though I know that using these terms for type systems is equivalent via the Curry-Howard correspondence), and moreover b) the soundness definition as you stated was the contrapositive of the standard definition (at least the one I'm used to) – so, together with the vagueness of the term "correct", I was thrown off a bit. :-)

[mark-i-m]

And a type-system that accepts all programs (or parse trees, etc) is likewise trivially complete; it is also unsound (but apparenty there's a big audience of developers willing to accept that 😉 ).

FYI, i believe this is called Perl

EDIT: or JavaScript?

[shepmaster]

@mark-i-m please remember to keep the Code of Conduct in mind. Denigrating other languages, even jokingly, can negatively impact those developers who use those languages and makes us all look bad.

[mark-i-m]

Sorry, no harm meant. And I certainly do appreciate the contributions of devs from other languages.

[petrochenkov]

My only large concern with this was performance, namely:

• whether it regresses compilation speed on average.
• whether this regresses compilation speed in important special cases - auto-generated code with large control flow graphs - huge switches, or huge number of branches.

I see there's some work this direction happens regularly, and there's a dashboard tracking performance, although I'm not sure whether it cover the second case.
Assuming there are no noticeable performance regressions, @rfcbot reviewed.

[nikomatsakis]

@petrochenkov

whether it regresses compilation speed on average.

The answer here is yes, but by relatively little. If you take a look at the NLL dashboard, you will see that the regression is always less than 20%, and typically "averages" more like 10% (I've not computed a real average, that's just an eyeball estimate). Note that this dashboard shows "cargo check" results, which is sort of the worst case, since borrow check overhead is not amortized with the time to run LLVM etc.

In fact, this dashboard somewhat exaggerates the "real world" impact, as for many of these crates, the current master builds significantly faster. @lqd did some measurements recently that covered the actual master, and you can see that the results look significantly better (for example, clap-rs is down to a 1.09 ratio):

lqd measurements

| crate | version | cargo check range | NLL cargo check range | min ratio |
| -----------|---------:| -------------:| -----------------:| -----:|
| cargo | perf.rlo – 0.29.0 69d61e | 8158 ms - 8879 ms | 8953 ms - 9139 ms | 1.09
| cargo | master – 0.30.0 4e53ce | 8512 ms - 8856 ms | 9342 ms - 9374 ms | 1.09
| clap-rs | perf.rlo – 2.29.0 | 4241 ms - 4486 ms | 5342 ms - 5552 ms | 1.26
| clap-rs | latest – 2.32.0 | 2674 ms - 2720 ms | 2936 ms - 2968 ms | 1.09
| html5ever | perf.rlo – 0.5.4 | 2203 ms - 2394 ms | TODO | TODO
| html5ever | latest – 0.22.3 | 1416 ms - 1449 ms | 1532 ms - 1564 ms | 1.08
| hyper | perf.rlo – 0.5.0 | 1584 ms - 1650 ms | 1687 ms - 1773 ms | 1.06
| hyper | latest – 0.12.7 | 2311 ms - 2464 ms | 2454 ms - 2742 ms | 1.06
| inflate | perf.rlo – 0.1.0 | 1836 ms - 1882 ms | 2286 ms - 2369 ms | 1.24
| inflate | latest – 0.4.3 | 507 ms - 537 ms | 540 ms - 629 ms | 1.06
| piston-image | perf.rlo – 0.10.3 | 2279 ms - 2490 ms | 2438 ms - 2597 ms |1.07
| piston-image | latest – 0.19.0 | 2727 ms - 2944 ms | 2912 ms - 2948 ms | 1.06
| ripgrep | perf.rlo – 0.8.1 a383d5 | 1284 ms - 1326 ms | 1374 ms - 1465 ms | 1.07
| ripgrep | master – 0.8.1 d857ad | 1310 ms - 1315 ms | 1404 ms - 1551 ms | 1.07
| serde | perf.rlo – 1.0.37 6e206c | 5273 ms - 5324 ms | 5886 ms - 6241 ms | 1.11
| serde | master – 1.0.70 4e54aa | 5785 ms - 6277 ms | 6023 ms - 6088 ms | 1.04
| style-servo | perf.rlo | 32209 ms - 33289 ms | 34631 ms - 35339 ms | 1.07
| syn | perf.rlo – 0.11.11 | 1131 ms - 1206 ms | 1217 ms - 1258 ms | 1.07
| syn | latest – 0.14.5 | 2031 ms - 2138 ms | 2111 ms - 2259 ms | 1.04
| ucd | perf.rlo | 6533 ms - 6809 ms | 54169 ms - 55417 ms | I don't wanna talk about it ok it's 8.29
| webrender | perf.rlo – 0.57.2 bb354a | 4152 ms - 4369 ms | 4480 ms - 4826 ms | 1.08
| webrender | master – 0.57.2 cf9b7803 | 4312 ms - 4609 ms | 4618 ms - 4816 ms | 1.07

whether this regresses compilation speed in important special cases - auto-generated code with large control flow graphs - huge switches, or huge number of branches.

We've encountered a few such cases. Mostly we've solved them, except for ucd:

• html5ever and ucd are cases of very large statics.
• keccak is a case of a really large control-flow graph (generated by macros)

We are working on ucd and making good progress. The "clincher" will presumably be https://github.com/rust-lang/rust/pull/53909, which needs a bit of work but brings UCD down to 116%.

[nikomatsakis]

@rfcbot resolved match-vs-let

I mostly filed this concern to raise https://github.com/rust-lang/rust/issues/53114 to everyone's attention. It's actually a fairly minor point though and we did discuss in lang team so I am going to remove my concern. (Feel free to comment on that issue if you have an opinion about the desired resolution.)

[pnkfelix]

@rfcbot resolved lifetime-annotations-get-no-respect

We've made progress on #47184 and it seems on track to be fully resolved before the actual release.

[pnkfelix]

@rfcbot resolved need-perf-comparison-against-incremental

discussion within WG-compiler-nll leads me to conclude that this issue should not block stabilization of NLL.

[lqd]

For the performance comparison to incremental uses cases @michaelwoerister mentioned, here's a test perf run with the NLL migrate mode enabled by default (that is, simulating opt-in to the 2018 edition in the coming Edition RC): comparison on perf.rlo.

As Niko mentioned earlier, the ucd case has a couple of open PRs improving things a lot.

The "baseline incremental-check" cases have lower overhead than the non-incremental "nll-check" cases (which are the worst-case benchmarks, tracked on the NLL dashboard) and the borrowck overhead is lower whenever codegen and LLVM are involved.

[nikomatsakis]

@lqd

The "baseline incremental-check" cases have lower overhead than the non-incremental "nll-check" cases (which are the worst-case benchmarks, tracked on the NLL dashboard) and the borrowck overhead is lower whenever codegen and LLVM are involved.

Great, thanks for doing that!

[mark-i-m]

Is there an expectation that the overhead will disappear entirely over time, or do we have to try to squeeze the time out elsewhere?

[arielb1]

@mark-i-m

First, currently we are doing NLL borrow-checking and AST region inference, we would expect things to get faster when AST region inference is done.

Second, there are probably some performance optimizations to be done, but I think that NLL is just doing more things than AST, and so will be slower for any given amount of optimization effort.

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

[orium]

Anyone knows what are the conditions for removing the old AST-based borrow checker? I'm curious about the performance gain it will cause :slightly_smiling_face:

[pnkfelix]

@orium Steps remaining, from what I remember/understand

1. turn on the borrow-checker's migrate (to NLL) mode for the 2015 edition (#57804).
2. switch the migrate mode so that it uses NLL's region inference algorithm rather than the old AST-based region inference.
3. update both 2018+2015 editions to issue hard errors from NLL rather than the soft-warnings generated by migrate mode.

(Issue #58781 captures both points 2 and 3 above.)

Once we do those things, then I think we'll be in a good position to actually remove the AST-borrowck code.

---

However: I do not expect this shift to yield a serious performance improvement. Or at least, not the one you might be expecting, based on how I interpret your comment. Removing the AST-borrowck code will only improve performance for code that is being rejected by the NLL checker (and thus falling back on running the AST-borrowck for determining if the NLL errors should be downgraded to warnings).

We do not run the AST-borrowck code (or at least not the bulk of it) when your code is successfully passing the NLL borrow checker. Thus, if you do not see any warnings or errors from your code, then you probably won't see a performance improvement from the eventual removal of the AST-borrowck code.

(The main exception I might imagine is whether there may be an impact from when we get rid of the AST-based region inference code and replace it with the NLL based one. But I don't know offhand if there is any serious performance impact associated with the AST-based region inference pass.)

[orium]

Thanks for clarifying that @pnkfelix. I was under the impression the old borrow checker was somehow more involved.