Stream: wg-traits

Topic: #58451 ICE related to lifetimes and traits


tmandry (Feb 14 2019 at 17:38, on Zulip):

Looking at this issue, it seems to be caused by the fact that a type error leads to an incomplete constraint graph.
By the use of placeholders, we can already tell that there is a region error, since we expanded one of the region vars to 'static
However, during error reporting, we cannot trace that error back to a concrete region (in this case, a scope) due to the graph being incomplete (it doesn't contain the scope at all).

tmandry (Feb 14 2019 at 17:40, on Zulip):

So maybe the correct behavior is to replace this span_bug! with delay_span_bug

tmandry (Feb 14 2019 at 17:40, on Zulip):

..since this is caused by an already-reported error

tmandry (Feb 14 2019 at 17:41, on Zulip):

Does this seem right? cc @nikomatsakis @lqd

nikomatsakis (Feb 14 2019 at 17:44, on Zulip):

Hmm

nikomatsakis (Feb 14 2019 at 17:44, on Zulip):

I was just looking at that

lqd (Feb 14 2019 at 17:44, on Zulip):

so was I

nikomatsakis (Feb 14 2019 at 17:45, on Zulip):

I dont' think that's quite the right assesment

nikomatsakis (Feb 14 2019 at 17:45, on Zulip):

but I could be remembering wrong

nikomatsakis (Feb 14 2019 at 17:45, on Zulip):

I think what is happening is that, when the error is found, we go traversing the graph looking for the "causes" of the error, but that search isn't taking into account the effects of crossing universes

lqd (Feb 14 2019 at 17:46, on Zulip):

the lower bounds and upper bounds seemed to be the same right ?

nikomatsakis (Feb 14 2019 at 17:46, on Zulip):

the way the algorithm works -- iirc -- is that, given some node X that has an error, it finds all the regions that X must outlive (i.e., all regions R where X: R) and all regions that outlive X. If you think of there being a graph where A: B means A <- B, we are basically finding all things that can reach Xand all things reachable from X

nikomatsakis (Feb 14 2019 at 17:47, on Zulip):

we assume that there will be two regions R1, R2 where R2: X: R1 but R2: R1 is false

nikomatsakis (Feb 14 2019 at 17:47, on Zulip):

but I'm not sure that's true when universes come into play

nikomatsakis (Feb 14 2019 at 17:47, on Zulip):

we had similar ICEs in the NLL code IIRC

nikomatsakis (Feb 14 2019 at 17:48, on Zulip):

among other things, an edge X: R1 can result in X becoming 'static if R1 is a placeholder, even though there is no direct edge betweenX and 'static

nikomatsakis (Feb 14 2019 at 17:48, on Zulip):

I think that's the root cause of the ICE

nikomatsakis (Feb 14 2019 at 17:48, on Zulip):

not sure @lqd if that is what you meant =)

lqd (Feb 14 2019 at 17:50, on Zulip):

it might be way ahead of me :)

lqd (Feb 14 2019 at 17:50, on Zulip):

that is:

lqd (Feb 14 2019 at 17:51, on Zulip):

I think what I was seeing was only one region in both the upper and lower bounds

tmandry (Feb 14 2019 at 17:52, on Zulip):

Yes, it is happening that our X is becoming 'static

tmandry (Feb 14 2019 at 17:52, on Zulip):

Just that when you get rid of the other error in the code (by replacing f(&[f()]); with f(&[()]);, for instance)

tmandry (Feb 14 2019 at 17:54, on Zulip):

..the error reporting mechanism is able to trace the conflict down to the scope of our &

tmandry (Feb 14 2019 at 17:54, on Zulip):

and as a result it reports an error that seems "correct"

tmandry (Feb 14 2019 at 17:55, on Zulip):

my point is that it is unable to do this in the original example, because the scope is nowhere in the constraint graph

lqd (Feb 14 2019 at 17:55, on Zulip):

ah yes interesting point indeed

nikomatsakis (Feb 14 2019 at 17:55, on Zulip):

hmm

tmandry (Feb 14 2019 at 17:55, on Zulip):

but maybe your point @nikomatsakis is that it should be able to find and report an error regardless

nikomatsakis (Feb 14 2019 at 17:55, on Zulip):

that is my point, basically

nikomatsakis (Feb 14 2019 at 17:56, on Zulip):

it's possible I am mistaken

lqd (Feb 14 2019 at 17:56, on Zulip):

that would mean the problem should be earlier than this function, correct ?

nikomatsakis (Feb 14 2019 at 17:56, on Zulip):

but I still sorta suspect I am not ;)

nikomatsakis (Feb 14 2019 at 17:56, on Zulip):

I have to run in a bit but let me share one thought:

nikomatsakis (Feb 14 2019 at 17:56, on Zulip):

the ICE is

error: internal compiler error: src/librustc/infer/lexical_region_resolve/mod.rs:632: collect_error_for_expanding_node() could not find error for var '_#4r in universe U6, lower_bounds=[
    RegionAndOrigin(RePlaceholder(Placeholder { universe: U6, name: BrNamed(crate0:DefIndex(1:10), 'a) }),Subtype(TypeTrace(ObligationCause { span: /home/nmatsakis/tmp/issue-58451.rs:8:5: 8:6, body_id: HirId { owner: DefIndex(0:4), loca\
l_id: 11 }, code: ItemObligation(DefId(0/0:3 ~ issue_58451[317d]::f[0])) }))),
    RegionAndOrigin(RePlaceholder(Placeholder { universe: U6, name: BrNamed(crate0:DefIndex(1:10), 'a) }),Subtype(TypeTrace(ObligationCause { span: /home/nmatsakis/tmp/issue-58451.rs:8:5: 8:6, body_id: HirId { owner: DefIndex(0:4), loca\
l_id: 11 }, code: ItemObligation(DefId(0/0:3 ~ issue_58451[317d]::f[0])) })))
], upper_bounds=[
    RegionAndOrigin(RePlaceholder(Placeholder { universe: U6, name: BrNamed(crate0:DefIndex(1:10), 'a) }),Subtype(TypeTrace(ObligationCause { span: /home/nmatsakis/tmp/issue-58451.rs:8:5: 8:6, body_id: HirId { owner: DefIndex(0:4), loca\
l_id: 11 }, code: ItemObligation(DefId(0/0:3 ~ issue_58451[317d]::f[0])) }))),
    RegionAndOrigin(RePlaceholder(Placeholder { universe: U6, name: BrNamed(crate0:DefIndex(1:10), 'a) }),Subtype(TypeTrace(ObligationCause { span: /home/nmatsakis/tmp/issue-58451.rs:8:5: 8:6, body_id: HirId { owner: DefIndex(0:4), loca\
l_id: 11 }, code: ItemObligation(DefId(0/0:3 ~ issue_58451[317d]::f[0])) })))
]
nikomatsakis (Feb 14 2019 at 17:57, on Zulip):

in particular the error is listeing our the "lower" and "upper" bounds:

nikomatsakis (Feb 14 2019 at 17:57, on Zulip):

those regions are not in conflict

nikomatsakis (Feb 14 2019 at 17:57, on Zulip):

but the conflict arises -- I think -- because the variable '_#4 can't name that placeholder (or some variable it's related to)

nikomatsakis (Feb 14 2019 at 17:58, on Zulip):

basically I think that algorithm of walking the graph to find "leaf nodes" and comparing them is flawed

nikomatsakis (Feb 14 2019 at 17:58, on Zulip):

in this context

nikomatsakis (Feb 14 2019 at 17:58, on Zulip):

but it should be possible to extend it without too much difficult I suspect

lqd (Feb 14 2019 at 17:59, on Zulip):

quick Q: is this the graph walking algorithm you're mentioning (I assume it is), or something else upstream ?

nikomatsakis (Feb 14 2019 at 18:01, on Zulip):

@lqd that's the one

lqd (Feb 14 2019 at 18:02, on Zulip):

great, thank you

lqd (Feb 14 2019 at 19:16, on Zulip):

@tmandry does this match your understanding ? we have '_#4r (== 'static), and the placeholder. The former should be a subregion of the latter, which we can't verify so this should be an error. We don't emit it immediately in collect_errors, and leave it for later, to do so in collect_var_errors. There, we'll later try to find the error for '_#4r, but it is in U6, which is the same universe as the placeholder: since it’s universe it can name itself, and the lower and upper bounds are the same (the placeholder), there's no conflict — and we're in the ICE territory. So I wondered (and could be very wrong, I know very little about this compared to you) whether in this case maybe the effective_lower_bound should still be 'static (as if the placeholder’s universe couldn't be named by the var’s universe). I tried 1) your earlier suggestion to delay_span_bug here – and confusingly it didn't end up emitting the region conflict (so there was ultimately only the "missing parameter" error here), and 2) also tried this 'static effective lower bound, which similarly didn't end up emitting an error either, even though (and this was different from just using delay_span_bug) there's a SubSupConflict, for '_#4r and the placeholder in U6, "region inference error" downstream. I only saw this latter one in the logs and not emitted by rustc, confusingly.

lqd (Feb 14 2019 at 19:17, on Zulip):

(gotta head out to dinner rn, will check back later :)

tmandry (Feb 14 2019 at 19:43, on Zulip):

we have '_#4r (== 'static), and the placeholder. The former should be a subregion of the latter, which we can't verify so this should be an error, which we don't emit immediately in collect_errors, and leave for later to do so in collect_var_errors.

yep!

There, we'll later try to find the error for '_#4r, but it is in U6

I don't believe '_#4r is in U6. If it were, it would not have been expanded to 'static in this code during the expand stage

tmandry (Feb 14 2019 at 19:43, on Zulip):

(I believe it that's the reason you see ='static)

lqd (Feb 14 2019 at 19:47, on Zulip):

I added a log in the if (on my phone rn so will get a link shortly) and saw: DEBUG 2019-02-14T19:07:53Z: rustc::infer::lexical_region_resolve: collect_error_for_expanding_node - node_universe=U6 can name universe=U6

lqd (Feb 14 2019 at 19:49, on Zulip):

à la:

if node_universe.cannot_name(p.universe) {
    debug!("collect_error_for_expanding_node - node_universe={:?} cannot name universe={:?}", node_universe, p.universe);
    self.tcx().types.re_static
} else {
    debug!("collect_error_for_expanding_node - node_universe={:?} can name universe={:?}", node_universe, p.universe);
    lower_bound.region
}
tmandry (Feb 14 2019 at 19:50, on Zulip):

maybe the effective_lower_bound should still be 'static (as if the placeholder’s universe couldn't be named by the var’s universe).

This.. seems right to me, but I don't fully understand the code myself

lqd (Feb 14 2019 at 19:50, on Zulip):

I saw the = ‘static in some contraction logs

tmandry (Feb 14 2019 at 19:51, on Zulip):

You can use triple-backticks to denote code blocks, same as github :)

lqd (Feb 14 2019 at 19:52, on Zulip):

(i know but can’t find back ticks on my phone keyboard sorry :p)

tmandry (Feb 14 2019 at 19:52, on Zulip):

ah, no problem :)

lqd (Feb 14 2019 at 19:52, on Zulip):

(I’ll edit it as soon as I get to a proper keyboard soon)

tmandry (Feb 14 2019 at 19:53, on Zulip):

are you sure the log you're seeing is for '_#4r?

lqd (Feb 14 2019 at 19:54, on Zulip):

I’ll double check

tmandry (Feb 14 2019 at 19:55, on Zulip):

I tried 1) your earlier suggestion to delay_span_bug here – and confusingly it didn't end up emitting the region conflict (so there was ultimately only the "missing parameter" error here)

This I expect.. basically we get here because we fail to emit a diagnostic for the error. The assumption of delay_span_bug being that we can _only_ get here if there was some other error in the compilation causing this

tmandry (Feb 14 2019 at 19:55, on Zulip):

(But it sounds like this isn't the right way to go)

tmandry (Feb 14 2019 at 19:57, on Zulip):

also tried this 'static effective lower bound, which similarly didn't end up emitting an error either, even though (and this was different from just using delay_span_bug) there's a SubSupConflict, for '_#4r and the placeholder in U6, "region inference error" downstream. I only saw this latter one in the logs and not emitted by rustc, confusingly.

This I find surprising, personally

lqd (Feb 14 2019 at 19:57, on Zulip):

haha yeah so did I

lqd (Feb 14 2019 at 20:07, on Zulip):

the only node_universe I see here in my logs is U6 :/ (but I haven't logged the node_idx so I'm not even sure it's '_#4r anymore) I don't know if these have shared information, and if so, wondered if there could be a mismatch between some information self.var_infos and var_data which is set here to mark the var in error to collect later.

tmandry (Feb 14 2019 at 20:09, on Zulip):

So, I get the following log:
Expanding value of '_#4r from RePlaceholder(Placeholder { universe: U6, name: BrNamed(crate0:DefIndex(1:10), 'a) }) to ReStatic
the question is, what is causing that :)

lqd (Feb 14 2019 at 20:13, on Zulip):

is there a chain like '4: '2: '1: '0 ?

tmandry (Feb 14 2019 at 20:23, on Zulip):

wait I think I see

tmandry (Feb 14 2019 at 20:23, on Zulip):

I thought you were logging in expand_node, but the log code you pasted looks like it's in collect_error_for_expanding_node

tmandry (Feb 14 2019 at 20:24, on Zulip):

I bet if you log on the conditional in expand_node (I linked to above), you will see '_#4r cannot name our placeholder at first

lqd (Feb 14 2019 at 20:30, on Zulip):

yeah maybe indeed — I was thinking all these mutations would have made 'static show up in the lower/upper bounds in collect_error_for_expanding_node, but apparently not. I'll have to check this more closely tomorrow.... (I'm in Europe, so "tomorrow" is a bit sooner than one might think :)

lqd (Feb 15 2019 at 14:29, on Zulip):

how I understand this: lexical_resolve_region log there are RegSubVar/VarSubReg constraints between '_#4r and the placeholder, there are VarSubVar constraints between '_#4r and '_#2r. '_#4r is indeed in U6, as is the placeholder, so the universe can be named. However, '_#2r is in U4 and can't name U6. This expands '_#2r to 'static, in turn updating '_#4r to 'static. We cannot verify that '_#4r <= the placeholder, and is the error we'll want to emit later. In collect_error_for_expanding_node we look for the two regions R1, R2 where R2: X: R1 but R2: R1 is false. In our case, R1 == R2 == the placeholder, X is 'static, the placeholder being in the same universe as the var in error '_#4r, and there is no such lower and upper bound creating the SubSupConflict (so this is where we ICE). Does that kind of make sense @nikomatsakis ?

lqd (Feb 15 2019 at 15:35, on Zulip):

however since these specific regions are not in conflict, which error we should emit is more of a mystery to me

nikomatsakis (Feb 15 2019 at 19:51, on Zulip):

@lqd ps sorry I will try to read that shortly :)

lqd (Feb 19 2019 at 09:19, on Zulip):

@pnkfelix salut Felix :) IIRC you're familiar with AST borrowck pre-Universes ? would you happen to know what kind of error #58451 is supposed to produce (instead of ICE-ing). I've summarized my understanding in this thread (just the message before this one) and there's more information from earlier with Tyler and Niko. In this particular situation, the lower and upper bounds do not conflict but there still needs to be an error of some kind (and IIRC blindly pushing a SubSupConflict error for the non-conflicting regions does not produce a UI error, so I'd assume it's filtered somewhere down the line and is a direction I could investigate for sure). If you happen to have ideas I could try or look up it'd be awesome

pnkfelix (Feb 19 2019 at 09:43, on Zulip):

I'll try to look

lqd (Feb 19 2019 at 09:44, on Zulip):

thanks a bunch

pnkfelix (Feb 19 2019 at 09:44, on Zulip):

I take it you are not interesting the actual diagnostic that used to be produced

pnkfelix (Feb 19 2019 at 09:44, on Zulip):

since you can readily observe that via the stable channel

lqd (Feb 19 2019 at 09:47, on Zulip):

I can observe the older output but not easily infer how to reproduce it post-Universes (or in general, with my current knowledge of rustc)

lqd (Feb 19 2019 at 09:49, on Zulip):

I can surely investigate more in that direction by rebuilding an older rustc, if that's what you're proposing ?

lqd (Feb 19 2019 at 09:51, on Zulip):

that would indeed show more details on the error we used to produce if we wanted/needed to duplicate it

pnkfelix (Feb 19 2019 at 09:53, on Zulip):

I suppose having a locally-built older rustc is certainly a straight-forward step, assuming you have spare hardware (cycles+memory) around to dedicate to that task.

lqd (Feb 19 2019 at 09:56, on Zulip):

I can try yeah, it's gonna take a while ofc, so I was hoping to avoid it as long as I could. I guess it can't be helped if we want to reproduce the same exact error, which I didn't know was what we needed (or if that's "possible")

lqd (Feb 19 2019 at 10:00, on Zulip):

alright I'll see what I can do with this, thanks @pnkfelix

nikomatsakis (Feb 19 2019 at 11:20, on Zulip):

@lqd I finally your update. Yes, that sounds like exactly what I expected, and I think perhaps reveals the flaw in the existing algorithm. Well, one caveat. You wrote this:

we look for the two regions R1, R2 where R2: X: R1 but R2: R1 is false. In our case, R1 == R2 == the placeholder, X is 'static

but I think X here is always going to be some inference variable whose current value is 'static, does that sound right?

lqd (Feb 19 2019 at 11:21, on Zulip):

yeah

nikomatsakis (Feb 19 2019 at 11:21, on Zulip):

I think how I might extend the algorithm would be to say that if a "predecessor" of X (i.e., some lower bound) is a placeholder in a universe that X cannot name, then when we are testing for a predecessor that is greater than a successor (i.e., an upper bound), we test instead for 'static

lqd (Feb 19 2019 at 11:21, on Zulip):

at least in this specific configuration of placeholder bounds I mean

nikomatsakis (Feb 19 2019 at 11:21, on Zulip):

does that make sense?

nikomatsakis (Feb 19 2019 at 11:22, on Zulip):

I've not looked at the code itself just now to assess how easy/hard that would be

lqd (Feb 19 2019 at 11:23, on Zulip):

would another VarSubVar constraint like we have here between '_#4r and '_#2r be considered a precedessor ?

lqd (Feb 19 2019 at 11:23, on Zulip):

since this is the one turning X ('_#4r) into 'static while still being able to name the bounds' universe

nikomatsakis (Feb 19 2019 at 11:26, on Zulip):

would another VarSubVar constraint like we have here between '_#4r and '_#2r be considered a precedessor ?

ok I see

nikomatsakis (Feb 19 2019 at 11:26, on Zulip):

it would not I thnk

nikomatsakis (Feb 19 2019 at 11:26, on Zulip):

though we could change that

nikomatsakis (Feb 19 2019 at 11:26, on Zulip):

and indeed this may be the thing to do

nikomatsakis (Feb 19 2019 at 11:26, on Zulip):

that is, I think right now we walk the graph until we encounter constraints that are NOT from variables

nikomatsakis (Feb 19 2019 at 11:26, on Zulip):

but we might have to think more carefully about var-var edges

lqd (Feb 19 2019 at 11:28, on Zulip):

I'll look at the graph walking more carefully as I seem to remember some traversal due to VarSubVar constraints but can't remember more; and this is where it might be more interesting indeed to look at them to see if they should be terminal

lqd (Feb 19 2019 at 11:31, on Zulip):

sweet, thanks Niko

lqd (Feb 21 2019 at 14:22, on Zulip):

so #58592 will fix this ICE, but I did have a WIP fix here. I'm not happy with it yet as it's very ad-hoc and specific to this issue. I'll work to generalize it so we can use it if/when the leak check revival is removed again, but at least tests currently pass with this fix. The error now generated for the code in the issue is ignored later anyway (the infcx is "tainted").

lqd (Feb 21 2019 at 14:24, on Zulip):

it does have this artful diagram tho

       +--------+
       v        |
       '1 +---> '2 +---> '!1
                ^         |
                +---------+

so at least there's that :)

Last update: Nov 12 2019 at 15:30UTC