Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Dropped variables still included in generator type #57478

Open
Tracked in #69663
Nemo157 opened this issue Jan 9, 2019 · 17 comments
Open
Tracked in #69663

Dropped variables still included in generator type #57478

Nemo157 opened this issue Jan 9, 2019 · 17 comments
Assignees
Labels
A-async-await A-generators A-typesystem AsyncAwait-Triaged C-enhancement P-low T-compiler T-lang

Comments

@Nemo157
Copy link
Member

@Nemo157 Nemo157 commented Jan 9, 2019

struct Foo;
impl !Send for Foo {}

let _: impl Send = || {
    let guard = Foo;
    drop(guard);
    yield;
};

(full playground) fails with

error[E0277]: `Foo` cannot be sent between threads safely
  --> src/main.rs:14:12
   |
14 |     let _: impl Send = || {
   |            ^^^^^^^^^ `Foo` cannot be sent between threads safely
   |
   = help: within `[generator@src/main.rs:14:24: 18:6 {Foo, ()}]`, the trait `std::marker::Send` is not implemented for `Foo`
   = note: required because it appears within the type `{Foo, ()}`
   = note: required because it appears within the type `[generator@src/main.rs:14:24: 18:6 {Foo, ()}]`

The guard should be dead and deallocated before the yield point so shouldn't appear in the generator type and affect the Sendness. Wrapping the guard in a new scope before the yield avoids this (included in the playground). First noticed in relation to async functions on u.rl.o.

@estebank estebank added C-bug A-generators labels Jan 9, 2019
@Aaron1011
Copy link
Member

@Aaron1011 Aaron1011 commented Jan 23, 2019

I'd like to work on this.

@Aaron1011
Copy link
Member

@Aaron1011 Aaron1011 commented Jan 23, 2019

This is going to be tricky.

The error is occurring due to the computed generator witness type including Foo. This is done during initial type checking, before any MIR has been generated.

Making this work would require type resolution to depend on the results of NLL. Specifically, the computed generator witness type would have to depend on which locals are computed to be live during mir-borrowck.

@Zoxc @nikomatsakis: Thoughts?

@Zoxc
Copy link
Contributor

@Zoxc Zoxc commented Jan 26, 2019

My plan for this is just to generate MIR for just the generator during type checking and then do the analysis on MIR. Currently that isn't very feasible given the current compiler structure.

Aaron1011 added a commit to Aaron1011/rust that referenced this issue Jun 7, 2019
Compound operators (e.g. 'a += b') have two different possible
evaluation orders. When the left-hand side is a primitive type, the
expression is evaluated right-to-left. However, when the left-hand side
is a non-primitive type, the expression is evaluated left-to-right.

This causes problems when we try to determine if a type is live across a
yield point. Since we need to perform this computation before typecheck
has run, we can't simply check the types of the operands.

This commit calculates the most 'pessimistic' scenario - that is,
erring on the side of treating more types as live, rather than fewer.
This is perfectly safe - in fact, this initial liveness computation is
already overly conservative (e.g. issue rust-lang#57478). The important thing is
that we compute a superset of the types that are actually live across
yield points. When we generate MIR, we'll determine which types actually
need to stay live across a given yield point, and which ones cam
actually be dropped.

Concretely, we force the computed HIR traversal index for
right-hand-side yield expression to be equal to the maximum index for
the left-hand side. This covers both possible execution orders:

* If the expression is evalauted right-to-left, our 'pessismitic' index
is unecessary, but safe. We visit the expressions in an
ExprKind::AssignOp from right to left, so it actually would have been
safe to do nothing. However, while increasing the index of a yield point
might cause the compiler to reject code that could actually compile, it
will never cause incorrect code to be accepted.
* If the expression is evaluated left-to-right, our 'pessimistic' index
correctly ensures that types in the left-hand-side are seen as occuring
before the yield - which is exactly what we want
@tmandry
Copy link
Contributor

@tmandry tmandry commented Jun 12, 2019

cc @rust-lang/lang, are we 100% sure we want to support this? The implication is there is going to be a "sharp edge" here when drops for certain locals move around relative to yield points (or vice versa).

It's also possible to work around it by turning your scope into a function call (possibly a closure that is immediately called).

@Nemo157
Copy link
Member Author

@Nemo157 Nemo157 commented Jun 12, 2019

You don't need a function call, just adding an actual scope around the variable that's dropped between yields is enough (this is included in the playground):

let _: impl Send = || {
    {
        let guard = Foo;
        drop(guard);
    }
    yield;
};

It makes sense to me why this is as it is and the solution could be just improved diagnostics telling users to add these extra scopes, it just seems like an unnecessary pain point for async functions.

Aaron1011 added a commit to Aaron1011/rust that referenced this issue Jun 22, 2019
Compound operators (e.g. 'a += b') have two different possible
evaluation orders. When the left-hand side is a primitive type, the
expression is evaluated right-to-left. However, when the left-hand side
is a non-primitive type, the expression is evaluated left-to-right.

This causes problems when we try to determine if a type is live across a
yield point. Since we need to perform this computation before typecheck
has run, we can't simply check the types of the operands.

This commit calculates the most 'pessimistic' scenario - that is,
erring on the side of treating more types as live, rather than fewer.
This is perfectly safe - in fact, this initial liveness computation is
already overly conservative (e.g. issue rust-lang#57478). The important thing is
that we compute a superset of the types that are actually live across
yield points. When we generate MIR, we'll determine which types actually
need to stay live across a given yield point, and which ones cam
actually be dropped.

Concretely, we force the computed HIR traversal index for
right-hand-side yield expression to be equal to the maximum index for
the left-hand side. This covers both possible execution orders:

* If the expression is evalauted right-to-left, our 'pessismitic' index
is unecessary, but safe. We visit the expressions in an
ExprKind::AssignOp from right to left, so it actually would have been
safe to do nothing. However, while increasing the index of a yield point
might cause the compiler to reject code that could actually compile, it
will never cause incorrect code to be accepted.
* If the expression is evaluated left-to-right, our 'pessimistic' index
correctly ensures that types in the left-hand-side are seen as occuring
before the yield - which is exactly what we want
@Nemo157
Copy link
Member Author

@Nemo157 Nemo157 commented Aug 21, 2019

After being reminded of this I realised this isn't really about "dropping" variables, it's about moving the variables out of the generator, any function that takes ownership should cause the variable to no longer be alive in the generator (this is the same thing since drop is just a trivial function to move the variable out, but being explicit about it might help others like me that didn't instantly make the connection):

struct Foo;
impl !Send for Foo {}

fn use_foo(_: Foo) {}

let _: impl Send = || {
    let guard = Foo;
    use_foo(guard);
    yield;
};

@oconnor663
Copy link
Contributor

@oconnor663 oconnor663 commented Aug 21, 2019

Another twist on the same problem might be using something like ManuallyDrop:

struct Foo;
impl !Send for Foo {}

let _: impl Send = || {
    let guard = ManuallyDrop::new(Foo);
    yield;
};

@jonas-schievink jonas-schievink added A-async-await T-compiler T-lang labels Jan 19, 2020
@tmandry tmandry added AsyncAwait-OnDeck AsyncAwait-Triaged labels Jan 21, 2020
@tmandry
Copy link
Contributor

@tmandry tmandry commented Jan 21, 2020

Marking as AsyncAwait-OnDeck - this error can be confusing, and it may not be obvious how to work around it.

@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Jan 24, 2020

What exactly is the bug here? To improve error report, or to do more precise drops? If the latter, that's a tricky problem indeed, but also duplicated by other issues.

@tmandry
Copy link
Contributor

@tmandry tmandry commented Feb 11, 2020

The way I read the issue, it is about tracking drops more precisely. (What issues duplicate this?)

We should open a separate issue to track improving the error message.

@tmandry tmandry added this to To do in wg-async work Feb 11, 2020
@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Feb 24, 2020

@tmandry I'm not sure what issue is the "best duplicate" but I think we've been using #57017 as a kind of stand-in for "more precise generator captures". It'd probably be good to create a generalized tracking issue that dives into the different sorts of cases, since it doesn't look like we're likely to get a generalized fix in the near-ish term.

@tmandry tmandry added C-enhancement and removed C-bug labels Mar 3, 2020
@tmandry tmandry added the P-low label Mar 3, 2020
eholk added a commit to eholk/rust that referenced this issue Nov 18, 2021
This is needed to handle cases like `[a, b.await, c]`. `ExprUseVisitor`
considers `a` to be consumed when it is passed to the array, but the
array is not quite live yet at that point. This means we were missing
the `a` value across the await point. Attributing drops to the parent
expression means we do not consider the value consumed until the
consuming expression has finished.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Nov 18, 2021
This adds support for branching and merging control flow and uses this
to correctly handle the case where a value is dropped in one branch of
an if expression but not another.

There are other cases we need to handle, which will come in follow up
patches.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Nov 22, 2021
eholk added a commit to eholk/rust that referenced this issue Nov 22, 2021
This change adds the basic infrastructure for tracking drop ranges in
generator interior analysis, which allows us to exclude dropped types
from the generator type.

Not yet complete, but many of the async/await and generator tests pass.
The main missing piece is tracking branching control flow (e.g. around
an `if` expression). The patch does include support, however, for
multiple yields in th e same block.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Nov 22, 2021
The main change needed to make this work is to do a pessimistic over-
approximation for AssignOps. The existing ScopeTree analysis in
region.rs works by doing both left to right and right to left order and
then choosing the most conservative ordering. This behavior is needed
because AssignOp's evaluation order depends on whether it is a primitive
type or an overloaded operator, which runs as a method call.

This change mimics the same behavior as region.rs in
generator_interior.rs.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Nov 22, 2021
This is needed to handle cases like `[a, b.await, c]`. `ExprUseVisitor`
considers `a` to be consumed when it is passed to the array, but the
array is not quite live yet at that point. This means we were missing
the `a` value across the await point. Attributing drops to the parent
expression means we do not consider the value consumed until the
consuming expression has finished.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Nov 22, 2021
This adds support for branching and merging control flow and uses this
to correctly handle the case where a value is dropped in one branch of
an if expression but not another.

There are other cases we need to handle, which will come in follow up
patches.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 6, 2021
eholk added a commit to eholk/rust that referenced this issue Dec 6, 2021
This change adds the basic infrastructure for tracking drop ranges in
generator interior analysis, which allows us to exclude dropped types
from the generator type.

Not yet complete, but many of the async/await and generator tests pass.
The main missing piece is tracking branching control flow (e.g. around
an `if` expression). The patch does include support, however, for
multiple yields in th e same block.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 6, 2021
The main change needed to make this work is to do a pessimistic over-
approximation for AssignOps. The existing ScopeTree analysis in
region.rs works by doing both left to right and right to left order and
then choosing the most conservative ordering. This behavior is needed
because AssignOp's evaluation order depends on whether it is a primitive
type or an overloaded operator, which runs as a method call.

This change mimics the same behavior as region.rs in
generator_interior.rs.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 6, 2021
This is needed to handle cases like `[a, b.await, c]`. `ExprUseVisitor`
considers `a` to be consumed when it is passed to the array, but the
array is not quite live yet at that point. This means we were missing
the `a` value across the await point. Attributing drops to the parent
expression means we do not consider the value consumed until the
consuming expression has finished.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 6, 2021
This adds support for branching and merging control flow and uses this
to correctly handle the case where a value is dropped in one branch of
an if expression but not another.

There are other cases we need to handle, which will come in follow up
patches.

Issue rust-lang#57478
@eholk eholk moved this from In progress (current sprint) to Claimed in wg-async work Dec 9, 2021
eholk added a commit to eholk/rust that referenced this issue Dec 15, 2021
eholk added a commit to eholk/rust that referenced this issue Dec 15, 2021
This change adds the basic infrastructure for tracking drop ranges in
generator interior analysis, which allows us to exclude dropped types
from the generator type.

Not yet complete, but many of the async/await and generator tests pass.
The main missing piece is tracking branching control flow (e.g. around
an `if` expression). The patch does include support, however, for
multiple yields in th e same block.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 15, 2021
The main change needed to make this work is to do a pessimistic over-
approximation for AssignOps. The existing ScopeTree analysis in
region.rs works by doing both left to right and right to left order and
then choosing the most conservative ordering. This behavior is needed
because AssignOp's evaluation order depends on whether it is a primitive
type or an overloaded operator, which runs as a method call.

This change mimics the same behavior as region.rs in
generator_interior.rs.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 15, 2021
This is needed to handle cases like `[a, b.await, c]`. `ExprUseVisitor`
considers `a` to be consumed when it is passed to the array, but the
array is not quite live yet at that point. This means we were missing
the `a` value across the await point. Attributing drops to the parent
expression means we do not consider the value consumed until the
consuming expression has finished.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Dec 15, 2021
This adds support for branching and merging control flow and uses this
to correctly handle the case where a value is dropped in one branch of
an if expression but not another.

There are other cases we need to handle, which will come in follow up
patches.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Jan 18, 2022
eholk added a commit to eholk/rust that referenced this issue Jan 18, 2022
This change adds the basic infrastructure for tracking drop ranges in
generator interior analysis, which allows us to exclude dropped types
from the generator type.

Not yet complete, but many of the async/await and generator tests pass.
The main missing piece is tracking branching control flow (e.g. around
an `if` expression). The patch does include support, however, for
multiple yields in th e same block.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Jan 18, 2022
The main change needed to make this work is to do a pessimistic over-
approximation for AssignOps. The existing ScopeTree analysis in
region.rs works by doing both left to right and right to left order and
then choosing the most conservative ordering. This behavior is needed
because AssignOp's evaluation order depends on whether it is a primitive
type or an overloaded operator, which runs as a method call.

This change mimics the same behavior as region.rs in
generator_interior.rs.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Jan 18, 2022
This is needed to handle cases like `[a, b.await, c]`. `ExprUseVisitor`
considers `a` to be consumed when it is passed to the array, but the
array is not quite live yet at that point. This means we were missing
the `a` value across the await point. Attributing drops to the parent
expression means we do not consider the value consumed until the
consuming expression has finished.

Issue rust-lang#57478
eholk added a commit to eholk/rust that referenced this issue Jan 18, 2022
This adds support for branching and merging control flow and uses this
to correctly handle the case where a value is dropped in one branch of
an if expression but not another.

There are other cases we need to handle, which will come in follow up
patches.

Issue rust-lang#57478
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jan 20, 2022
…komatsakis

Introduce drop range tracking to generator interior analysis

This PR addresses cases such as this one from rust-lang#57478:
```rust
struct Foo;
impl !Send for Foo {}

let _: impl Send = || {
    let guard = Foo;
    drop(guard);
    yield;
};
```

Previously, the `generator_interior` pass would unnecessarily include the type `Foo` in the generator because it was not aware of the behavior of `drop`. We fix this issue by introducing a drop range analysis that finds portions of the code where a value is guaranteed to be dropped. If a value is dropped at all suspend points, then it is no longer included in the generator type. Note that we are using "dropped" in a generic sense to include any case in which a value has been moved. That is, we do not only look at calls to the `drop` function.

There are several phases to the drop tracking algorithm, and we'll go into more detail below.
1. Use `ExprUseVisitor` to find values that are consumed and borrowed.
2. `DropRangeVisitor` uses consume and borrow information to gather drop and reinitialization events, as well as build a control flow graph.
3. We then propagate drop and reinitialization information through the CFG until we reach a fix point (see `DropRanges::propagate_to_fixpoint`).
4. When recording a type (see `InteriorVisitor::record`), we check the computed drop ranges to see if that value is definitely dropped at the suspend point. If so, we skip including it in the type.

## 1. Use `ExprUseVisitor` to find values that are consumed and borrowed.

We use `ExprUseVisitor` to identify the places where values are consumed. We track both the `hir_id` of the value, and the `hir_id` of the expression that consumes it. For example, in the expression `[Foo]`, the `Foo` is consumed by the array expression, so after the array expression we can consider the `Foo` temporary to be dropped.

In this process, we also collect values that are borrowed. The reason is that the MIR transform for generators conservatively assumes anything borrowed is live across a suspend point (see `rustc_mir_transform::generator::locals_live_across_suspend_points`). We match this behavior here as well.

## 2. Gather drop events, reinitialization events, and control flow graph

After finding the values of interest, we perform a post-order traversal over the HIR tree to find the points where these values are dropped or reinitialized. We use the post-order index of each event because this is how the existing generator interior analysis refers to the position of suspend points and the scopes of variables.

During this traversal, we also record branching and merging information to handle control flow constructs such as `if`, `match`, and `loop`. This is necessary because values may be dropped along some control flow paths but not others.

## 3. Iterate to fixed point

The previous pass found the interesting events and locations, but now we need to find the actual ranges where things are dropped. Upon entry, we have a list of nodes ordered by their position in the post-order traversal. Each node has a set of successors. For each node we additionally keep a bitfield with one bit per potentially consumed value. The bit is set if we the value is dropped along all paths entering this node.

To compute the drop information, we first reverse the successor edges to find each node's predecessors. Then we iterate through each node, and for each node we set its dropped value bitfield to the intersection of all incoming dropped value bitfields.

If any bitfield for any node changes, we re-run the propagation loop again.

## 4. Ignore dropped values across suspend points

At this point we have a data structure where we can ask whether a value is guaranteed to be dropped at any post order index for the HIR tree. We use this information in `InteriorVisitor` to check whether a value in question is dropped at a particular suspend point. If it is, we do not include that value's type in the generator type.

Note that we had to augment the region scope tree to include all yields in scope, rather than just the last one as we did before.

r? `@nikomatsakis`
@camsteffen
Copy link
Contributor

@camsteffen camsteffen commented Jan 25, 2022

Yes, the liveness analysis I'm working on will fix this issue too.

@eholk How does this relate to #51003?

@eholk
Copy link
Contributor

@eholk eholk commented Jan 27, 2022

@camsteffen - I would say not very much. Originally I approached this issue in terms of liveness, but that ran into enough problems that I gave up on it. For example, in something like

let x = foo();
let y = &x;
use(y);

it's hard to realize that y being live implies that x is live too.

The solution I ended up going with works by tracking the ranges for which values are not dropped (see #91032).

I wouldn't let my work here deter you from working on #51003, and a lot of things about the liveness analysis pass will be tidier in MIR, so I'm supportive of moving the analysis there.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-async-await A-generators A-typesystem AsyncAwait-Triaged C-enhancement P-low T-compiler T-lang
Projects
wg-async work
In progress (current sprint)
Development

No branches or pull requests