Stream: t-compiler

Topic: trait resolution regression #60010


pnkfelix (Apr 30 2019 at 13:41, on Zulip):

This topic is discussion regarding "april 2018 trait resolution regression #60010"

pnkfelix (Apr 30 2019 at 13:41, on Zulip):

@nikomatsakis the detail I was trying to outline, about composing constraints, is in this comment here: https://github.com/rust-lang/rust/issues/60010#issuecomment-484028251

pnkfelix (Apr 30 2019 at 13:42, on Zulip):

where I found it odd that the code would compile if you have either T: RefUnwindSafe or T: HasQueryGroup on their own.

pnkfelix (Apr 30 2019 at 13:42, on Zulip):

but putting them both on as a constraint would not allow the code to compile

pnkfelix (Apr 30 2019 at 13:43, on Zulip):

I think my basic reading of your response, is that I should not generally expect these things to compose in every case

pnkfelix (Apr 30 2019 at 13:44, on Zulip):

i.e. in some situations, even if the code compiles with where T: A, and separately with where T: B, that does not mean it will compile with the composition where T: A, T: B

pnkfelix (Apr 30 2019 at 13:44, on Zulip):

but I just wanted to double-check that this is indeed the correct general conclusion (i.e. that one should not expect that particular compositional property to hold when one is dealing with the mix of inductive and co-inductive reasoning that rustc uses)

centril (Apr 30 2019 at 13:50, on Zulip):

I certainly did expect this property to hold; TIL! (but I also didn't take coinductive stuff into account)

varkor (Apr 30 2019 at 14:31, on Zulip):

is there a minimal example?

pnkfelix (Apr 30 2019 at 14:58, on Zulip):

@varkor the best I was able to do is written in the issue

pnkfelix (Apr 30 2019 at 14:58, on Zulip):

(in the second comment)

nikomatsakis (Apr 30 2019 at 17:04, on Zulip):

@pnkfelix Hmm, well, I'm not sure if that is a valid takeaway from my comment.

nikomatsakis (Apr 30 2019 at 17:04, on Zulip):

I'll have to dig into this particular example more deeply

nikomatsakis (Apr 30 2019 at 17:05, on Zulip):

It is true that having a setup where:

is not provable, at least in the present setup. All participants in the cycle must be coinductive. But it's not clear to me how this leads to where T: A, t: B behaving differently from T:A and T:B (i.e., I'd expect the cycle to go through one of those two clauses, and for the cycle to be present regardless).

nikomatsakis (May 01 2019 at 15:12, on Zulip):

Hey @matklad -- what is the issue that was plaguing you re: incremental results messing up trait resolution or method dispatch?

nikomatsakis (May 01 2019 at 15:13, on Zulip):

I feel like it may be connected to this problem i'm investigating

matklad (May 01 2019 at 15:14, on Zulip):

https://github.com/rust-lang/rust/issues/58291

matklad (May 01 2019 at 15:14, on Zulip):

well, if you read the first line of issue description....

matklad (May 01 2019 at 15:14, on Zulip):

you'll see that it was spawned from that problem :D

nikomatsakis (May 01 2019 at 15:14, on Zulip):

Heh, oh, well, that makes sense, doesn't it

nikomatsakis (May 01 2019 at 15:15, on Zulip):

it seems like there is a problem with the caching in the case of cycles

nikomatsakis (May 01 2019 at 15:15, on Zulip):

among other things, I think it could lead to incorrect dep-node information

nikomatsakis (May 01 2019 at 15:49, on Zulip):

ok, taking some notes here

nikomatsakis (May 01 2019 at 15:49, on Zulip):

I think I see the problem

nikomatsakis (May 01 2019 at 15:50, on Zulip):

the evaluation cache is caching "over-eagerly"

nikomatsakis (May 01 2019 at 15:50, on Zulip):

this is causing other sorts of problems

nikomatsakis (May 01 2019 at 15:50, on Zulip):

I think @pnkfelix that the error we see invoking foo.probe() is actually the correct result

nikomatsakis (May 01 2019 at 15:50, on Zulip):

roughly for the reasons you already diagnosed

nikomatsakis (May 01 2019 at 15:58, on Zulip):

what we do now is this:

but now we're in a weird state. We cached that C: AutoTrait holds, but that wouldn't be true if we had started from C: AutoTrait.

Seems obvious that this is wrong. It's the same problem of cyclic caching we encounter in lots of places. (Actually, it makes me want to review how I integrated coinduction into Chalk's SLG solver... man, I'd like to remove co-induction from auto traits, but let's leave that for another day.)

nikomatsakis (May 01 2019 at 15:58, on Zulip):

I'm going to move this over into #wg-traits =)

pnkfelix (May 01 2019 at 16:00, on Zulip):

I’m going to have to go look up literature on mixing inductive and co-inductive reasoning

pnkfelix (May 01 2019 at 16:01, on Zulip):

this outcome remains non-obvious to me

pnkfelix (May 01 2019 at 16:02, on Zulip):

Well, that, or learn about how we would do auto traits without co-inductive reasoning

nikomatsakis (May 01 2019 at 16:48, on Zulip):

Well, that, or learn about how we would do auto traits without co-inductive reasoning

that is tricky; I had some ideas that I wanted to explore, but it's a complex topic

nikomatsakis (May 01 2019 at 16:48, on Zulip):

for now i'm aiming at a targeted fix for this caching problem

nikomatsakis (May 01 2019 at 16:48, on Zulip):

I think the proper fix is to either move to chalk or rewrite the solver in a more global way

nikomatsakis (May 01 2019 at 16:51, on Zulip):

I’m going to have to go look up literature on mixing inductive and co-inductive reasoning

there's not a lot on it, there's a paper or two

nikomatsakis (May 01 2019 at 17:19, on Zulip):

so I have a simple fix; the bad news is that this may mess up salsa :) but I guess we can fix it

nikomatsakis (May 01 2019 at 17:19, on Zulip):

(cc @matklad)

eddyb (May 01 2019 at 22:15, on Zulip):

someone had a trick for some form of "negative reasoning" with non-auto-traits (by relying on an auto trait), I wonder if it would be broken by this (sadly, I don't remember where it was)

pnkfelix (May 02 2019 at 09:31, on Zulip):

But it's not clear to me how this leads to where T: A, t: B behaving differently from T:A and T:B (i.e., I'd expect the cycle to go through one of those two clauses, and for the cycle to be present regardless)

Hey @nikomatsakis , how does your PR #60444 affect the question above? In particular, I think what it does is it changes the behavior for one of T: A or T: B when they are given on their own, but the test code you added did not exercise either of those cases, so I'm not certain.

nikomatsakis (May 02 2019 at 12:55, on Zulip):

@pnkfelix indeed, my PR restores the property that you expected: that T: A, T: B => T: A + B

nikomatsakis (May 02 2019 at 12:55, on Zulip):

the problem was that executing T: A was polluting the cache, such that T: B incorrectly succeeded (or something like that)

pnkfelix (May 02 2019 at 13:00, on Zulip):

that makes sense

pnkfelix (May 02 2019 at 13:00, on Zulip):

though

pnkfelix (May 02 2019 at 13:00, on Zulip):

I could have sworn I tried reordering the constraints in the source

pnkfelix (May 02 2019 at 13:01, on Zulip):

does such reordering not affect the order in which the clauses are traversed? I guess it would be silly for me to assume that would generally hold

nikomatsakis (May 02 2019 at 13:49, on Zulip):

we may do some reordering

nikomatsakis (May 02 2019 at 13:49, on Zulip):

and it may be that whichever one you did first

nikomatsakis (May 02 2019 at 13:49, on Zulip):

the pollution would affect the other

nikomatsakis (May 02 2019 at 13:50, on Zulip):

I was thinking aobut it this morning, I think i can make some simpler test cases

nikomatsakis (May 02 2019 at 13:50, on Zulip):

that also show the problem

nikomatsakis (May 02 2019 at 13:50, on Zulip):

which I might try to do, just to have more coverage of the subtle cases

pnkfelix (May 13 2019 at 11:31, on Zulip):

Hey @nikomatsakis , do you think 6 regressions according to crater is low-risk enough to land PR #60444 ?

pnkfelix (May 13 2019 at 11:33, on Zulip):

I think it falls into "acceptable fallout", especially given how bad the kinds of bugs are that happen without this fix.

lqd (May 13 2019 at 12:24, on Zulip):

@pnkfelix also they seemed to be mostly fixable (I assume) by increasing the recursion limit ?

lqd (May 13 2019 at 12:36, on Zulip):

(or maybe should we make sure those 6 are not uncovering an issue with the fix itself ?)

pnkfelix (May 13 2019 at 12:48, on Zulip):

@lqd yes I have been assuming (but have not verified) that the regressions would be addressed by increasing the recursion limit

pnkfelix (May 13 2019 at 12:48, on Zulip):

which makes me wonder whether we could/should make crater smart enough to attempt such responses

lqd (May 13 2019 at 12:49, on Zulip):

interesting thought, trying to rustfix the errors :)

Pietro Albini (May 13 2019 at 12:49, on Zulip):

@pnkfelix is it possible to change the recursion limit through a rustc compiler flag?

lqd (May 13 2019 at 12:49, on Zulip):

(also when I looked at them I thought one of these 6 was a dupe of one of the other 5)

Pietro Albini (May 13 2019 at 12:51, on Zulip):

if that's the case you could start another crater run with the compiler flag to increase the limit and see if it's fixed

Pietro Albini (May 13 2019 at 12:51, on Zulip):

(btw, crater is broken for all the new try builds until we figure out how to deal with a cargo regression)

pnkfelix (May 13 2019 at 12:52, on Zulip):

(i don't know whether the recursion-limit is accessible via a command line flag. It don't know of a reason why it shouldn't be, but that doesn't mean it is...)

nikomatsakis (May 13 2019 at 17:38, on Zulip):

it's possible that recursion limit would help, not necessarily true

nikomatsakis (May 13 2019 at 17:38, on Zulip):

in particular, if there is a legit cycle

nikomatsakis (May 13 2019 at 17:38, on Zulip):

I think we may still report it that way

matklad (May 18 2019 at 09:35, on Zulip):

Compiling rust-analyzer with the latest nightly takes a looong time, and fails with "overflowing evaluating requirenment". Could this be a side-effect of https://github.com/rust-lang/rust/pull/60444?

matklad (May 18 2019 at 09:44, on Zulip):

ra issue: https://github.com/rust-analyzer/rust-analyzer/issues/1283

matklad (May 18 2019 at 10:06, on Zulip):

I am sending https://github.com/rust-analyzer/rust-analyzer/pull/1284 to work around the issue, but I am curios to hear what is the proper fix?

pnkfelix (May 20 2019 at 07:47, on Zulip):

its certainly possible that the performance regression is due to PR #60444; see in particular issue #60846

nikomatsakis (May 30 2019 at 14:27, on Zulip):

@matklad we should take a look -- the cycle caching fix is basically closing off a soundness hole, so error described in rust-analyzer#1283 is probably correct, but we may be able to side-step it by adjusting other things

matklad (May 30 2019 at 14:37, on Zulip):

#1283 does not look like a proper error though: it just aborts a very long computation.

I was secretly hoping that fixing #60846 will give us a real error message here, which should help to fix the issue :-)

nikomatsakis (May 30 2019 at 14:43, on Zulip):

well, getting a better error may be something we could do more narrowly

matklad (May 30 2019 at 14:47, on Zulip):

I wonder if with move to panic-based cancellation we should just require that keys & values are unwind safe?

nikomatsakis (Jun 04 2019 at 15:50, on Zulip):

Do we have any kind of "minimized" example of the perf problem here? Seems like @Zoxc ran into something similar and a few others. I'm contemplating what I can do about it.

nikomatsakis (Jun 04 2019 at 15:51, on Zulip):

I think I know the fix I want to do but it will take too long :)

Last update: Nov 21 2019 at 14:35UTC