Convert typeck constraints in location-sensitive polonius #134920

lqd · 2024-12-30T13:24:59Z

In this PR, we do a big chunk of the work of localizing regular outlives constraints.

The slightly annoying thing is handling effectful statements: usually the subset graph propagates loans at a single point between regions, and liveness propagates loans between points within a single region, but some statements have effects applied on exit.

This was also a problem before, in datalog polonius terms and Niko's solution at the time, this is about: the mid-point. The idea was to duplicate all MIR locations into two physical points, and orchestrate the effects with that. Somewhat easier to do, but double the CFG.

We've always believed we didn't need midpoints in principle, as we can represent changes on exit as on happening entry to the successor, but there's some difficulty in tracking the position information at sufficient granularity through outlives relation (especially since we also have bidirectional edges and time-traveling now).

Now, that is surely what we should be doing in the future. In the mean time, I infer this from the kind of statement/terminator where an outlives constraint arose. It's not particularly complicated but some explanation will help clarify the code.

Assignments (in their various forms) are the quintessential example of these crossover cases: loans that would flow into the LHS would not be visible on entry to the point but on exit -- so we'll localize these edges to the successor. Let's look at a real-world example, involving invariance for bidirectional edges:

let mut _1: HashMap<i32, &'7 i32>;
let mut _3: &'9 mut HashMap<i32, &'10 i32>;
...
/* at bb1[3]: */ _3 = &'3 mut _1;

Here, typeck expectedly produces 3 outlives constraints today:

'3 -> '9
'7 -> '10
'10 -> '7

And we localize them like so,

'3 -> '9 flows into the LHS and becomes: 3_bb1_3 -> 9_bb1_4
'7 -> '10 flows into the LHS and becomes: 7_bb1_3 -> 10_bb1_4
'10 -> '7 flows from the LHS and becomes: 10_bb1_4 -> 7_bb1_3 (time traveling 👌)

r? @jackh726

To keep you entertained during the holidays I also threw in a couple of small changes removing cruft in the borrow checker.

We're actually getting there. The next PR will be the last one needed to get end-to-end tests working.

jackh726 · 2024-12-31T20:49:45Z

compiler/rustc_borrowck/src/polonius/typeck_constraints.rs

+    tcx.for_each_free_region(value, |region| {
+        let region = universal_regions.to_region_vid(region);
+        if region == outlives_constraint.sub {
+            // This constraint flows into the result, its effects start becoming visible on exit.
+            to = successor_point;
+        } else if region == outlives_constraint.sup {
+            // This constraint flows from the result, its effects start becoming visible on exit.
+            from = successor_point;
+        }
+    });


I think this is right, but it feels off to me. The loop using for_each_free_region feels like the wrong construct to me.

I'd also prefer if this differentiation was done in MIR typeck instead, if that's what you mean. It wasn't trivial in the NLL days, according to Niko and some comments in the crate, but should still be possible I think?

I think given the FIXME further up in the file, we don't need to do anything in this PR, just wanted to point out that it sure does feel weird.

jackh726 · 2024-12-31T20:54:24Z

compiler/rustc_borrowck/src/polonius/typeck_constraints.rs

+                localized_outlives_constraints.push(LocalizedOutlivesConstraint {
+                    source: outlives_constraint.sup,
+                    from,
+                    target: outlives_constraint.sub,
+                    to,
+                });


I wonder if readability would be better here if you moved the LocalizedOutlivesConstraint construction deeper (into compute_constraint_direction), instead of propagating up a (PointIndex, PointIndex). It'll then be much more clear the matching of sup/sub to from/to.

I initially has something similar indeed, but the duplication was a bit much and I turned it into this. I can bring it back.

I've pushed a commit to do so, let me know what you think (especially if you didn't mean to also inline the helper function compute_constraint_direction) and I can then squash it in. Inlining the helper makes the link between the sub/sup and from/to clearer with the actual result type we're checking.

jackh726 · 2024-12-31T20:56:43Z

compiler/rustc_borrowck/src/polonius/typeck_constraints.rs

+        }
+        _ => {
+            // For the other cases, we localize an outlives constraint to where it arises.
+            (current_point, current_point)


To add to this, are these actually useful? (I think I remember that these get filtered somewhere? Or was that something else?)

If these aren't useful, then you can make this branch empty.

(I think I remember that these get filtered somewhere? Or was that something else?)

I think that may be something else? Only an edge from and to the same node is filtered out, if that's what you remembered: if the regions are different but from/to the same point, they're not filtered out.

To add to this, are these actually useful?

I think handling some statements should be needed in addition to assignments, like maybe fake reads and type ascriptions (but the latter should hold everywhere and not go through this code path here, but the Locations::All path).

I'll try to look into it soon; I don't think we'll have tests that exercise this anyways.

Okay, I do still even if these are needed that duplicating the LocalizedOutlivesConstraint (instead of propagating up the PointIndex tuple will improve readability.

it's still partially a skeleton, but works well enough for almost all tests to pass

this is to remove the entire `util` module

it's been simplified over the years, but now it's no longer useful. - document its replacement in `BorrowKind` - use that everywhere instead

push constraint creation to where the statement/terminator info is gathered

jackh726 · 2025-01-01T15:43:45Z

r=me with or without moving the LocalizedOutlivesConstraint construction deeper

rustbot assigned jackh726 Dec 30, 2024

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Dec 30, 2024

This was referenced Dec 31, 2024

Location-sensitive polonius prototype: endgame #134980

Draft

Scalable Polonius support on nightly rust-lang/rust-project-goals#118

Open

jackh726 reviewed Dec 31, 2024

View reviewed changes

lqd added 7 commits January 1, 2025 12:13

move typeck constraints conversion to its own module

eb7da16

localize typeck constraints

46154b2

it's still partially a skeleton, but works well enough for almost all tests to pass

move find_assignments to its only use site

56e7575

this is to remove the entire `util` module

remove empty util module

ff1aaa5

remove allow_two_phase_borrow

79d761d

it's been simplified over the years, but now it's no longer useful. - document its replacement in `BorrowKind` - use that everywhere instead

remove borrowck duplicate of std::ops::ControlFlow

9d444c2

address review comments

9eef43a

push constraint creation to where the statement/terminator info is gathered

lqd force-pushed the polonius-next-episode-6 branch from 490c17a to 9eef43a Compare January 1, 2025 15:37

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Convert typeck constraints in location-sensitive polonius #134920

Convert typeck constraints in location-sensitive polonius #134920

lqd commented Dec 30, 2024

jackh726 Dec 31, 2024

lqd Jan 1, 2025

jackh726 Jan 1, 2025

jackh726 Dec 31, 2024

lqd Jan 1, 2025

jackh726 Dec 31, 2024

lqd Jan 1, 2025

jackh726 Jan 1, 2025

jackh726 commented Jan 1, 2025

Convert typeck constraints in location-sensitive polonius #134920

Are you sure you want to change the base?

Convert typeck constraints in location-sensitive polonius #134920

Conversation

lqd commented Dec 30, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jackh726 commented Jan 1, 2025