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

• Initial prototype: features available on nightly builds with #![feature(nll)] for experimentation.
• Valid code works: (issues labeled with NLL-complete)
  • all run-pass tests pass
  • 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.
  • 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.
• Future compatibility warnings on stable: Once crater runs are clean, we can enable the future-compatibility warnings on stable: see #46908 and #52681
  • currently, due to #52681, we are issuing compatibility warnings on the 2018 edition.
  • 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".
  • round one: #49862
  • 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
  • NLL warnings (downgraded from errors) become errors again
  • 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, AST-based borrow checker removed: #57895

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

#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

• #46036: infinite loop false edges
• 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.

[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]

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

[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 🙂

[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.