rust-lang / rust-lang/polonius

Document the intuition behind the optimized ruleset

Open
#175 2 comments 2 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
1.7k
Forks
86
PR merge metrics
No merged PRs in 30d

Description

The "optimized" variant of the borrow-checking rules—defined here—isn't explained in detail anywhere in this repo AFAICT. You can read through the relations one-by-one to get a sense of what's happening, but it's easy to miss the forest for the trees. For example, what is so special about "dying regions"? The book has only a short placeholder section that doesn't provide any answers:

A more detailed description of the rules in this Opt variant will be added later but it computes the same data as the Naive variant described above, more efficiently, by limiting where the subset transitive closure is computed: some origins are short-lived, or part of a subsection of the subset graph into which no loan ever flows, and therefore don't contribute to errors or loan propagation. There's no need to track these specific cases.

Niko is pretty busy, so I don't foresee him writing another sweet blog post like this one. There's actually a pretty good explanation in the first paragraph of one of Niko's comments on #153, but obviously that needs to be expanded upon.

I've developed my own intuition about what the optimized variant is doing, although I might be missing some of the subtleties, and @lqd has some insight as well from their work on #156. That should be enough to improve the state of things. During the sprint, Niko mentioned removing the optimized variant while still in the prototyping phase, since it's difficult to iterate on top of. Even if that happens, documenting its ideas is still important lest they fade into obscurity.

edit
I've written down my intuition for datafrog-opt below, although I'm not 100% sure that it's correct. We should discuss a bit before putting anything in the book. I've explained it by showing what happens when either the left or the right of a single subset relation ('a <: 'b) goes dead, but it may be clearer to talk the middle origin in a transitive subset relation ('a <: 'b <: 'c). Also, I've not documented which ideas correspond to specific relations in the optimized variant (e.g. dying_can_reach, dying_region_requires, etc.).

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with polonius-engine/src/output/datafrog_opt.rs, reading its relations alongside the Naive variant and the discussion linked from issue #153. Clarify the intuition behind optimized rules such as dying regions, map those ideas to relations like dying_can_reach and dying_region_requires, and update the book so the optimized and Naive variants are explained accurately.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
documentation
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.