Segfault in safe code caused by a use after drop when using index sugar

[phsym]

I've been playing a bit around std::ops::Index and the associated sugar.
I found a case where it may cause a segfault. I tried to reproduce the issue in a simplified code and got the following one (also available on playpen)

use std::ops::Index;

struct Test<'a> {
    s: &'a String
}

impl <'a> Index<usize> for Test<'a> {
    type Output = Test<'a>;
    fn index(&self, _: usize) -> &Self::Output {
        return &Test { s: &self.s};
    }
}

fn main() {
    let s = "Hello World".to_string();
    let test = Test{s: &s};
    let r = &test[0];
    println!("{}", test.s); // OK since test is valid
    println!("{}", r.s); // Segfault since value pointed by r has already been dropped
}

I guess this code should not compile since on the last line, r points to a dropped value.

[alexcrichton]

Hm, this shouldn't compile because return &Test { s: &self.s}; is returning a temporary which can't live as long as self. Seems odd that it does though! I've confirmed that this compiles on all of stable/beta/nightly.

cc @rust-lang/compiler, perhaps this is a dupe of an existing bug?

[durka]

It doesn't actually have to do with the Index sugar: http://is.gd/6sCgIy. It seems like it has to do with copying the lifetime bound from the associated type into the function return type: if you manually substitute in Test<'a> for Self::Output on line 19, then it doesn't compile.

[eddyb]

@alexcrichton I would've guessed it's similar to #29861.

[nikomatsakis]

triage: P-high

[MagaTailor]

Why does it not compile on nightly in playpen?

[eddyb]

@petevine Could be #29861, or some other recent fix.

[durka]

So this seems like it can be closed?

[pnkfelix]

Unfortunately it seems like we didn't have nightly builds from 2015-12-15 through 2015-12-18.

I can confirm that this was broken in rust nightly-2015-12-14 and is rejected (correctly) by rust nightly-2015-12-19.

I'll do a quick bisect just to double check what fixed it.

[pnkfelix]

Bisection reveals that the fix was due to PR #30341.

While there is a test attached to PR #30341, to me the test there (which is a reduction of the code from #29793) seems different enough from the code here that I'm going to make an independent regression test for the code given here.

[pnkfelix]

Hmm. While writing the test and then "simplifying" it, I actually found a related program that continues to segfault:

http://is.gd/TpRMsz

trait Trait { type Out; fn method(&self) -> &Self::Out; }
struct Test<'a> { s: &'a String }

impl<'a> Trait for Test<'a> {
type Out = Test<'a>;
    fn method(&self) -> &Self::Out {
        &Test { s: &self.s }
    }
}

fn main() {
    let s = "Hello World".to_string();
    let test = Test { s: &s };
    let r = test.method();
    println!("{}", test.s); // OK since test is valid
    println!("{}", r.s); // Segfault (value ref'd by r dropped during index)
}

[pnkfelix]

(apparently the switch from explicit return &Test { s: &self.s }; to implicit return of &Test {s: &self.s } in the body of fn method is what is causing the regression to sneak in again. I'll investigate.)

[arielb1]

fn silly<'y, 'a>(s: &'y Test<'a>) -> &'y <Test<'a> as Trait>::Out {
    let x = Test { s: &s.s }; &x
}

what?

[pnkfelix]

There's some really funky interactions going on here with associated types and with lifetime bounds on the struct.

For example, this version of @arielb1's refined example is (correctly) rejected by the compiler: http://is.gd/NGHvkm
while this alternative is incorrectly accepted: http://is.gd/jbh1xd

but the only different between the two is that in the version that is rejected, we have a maximally parameteric blanket impl:

impl<T> Trait for T { type Out = T; }

while for the version that is accepted, we have instead a more narrowly focused impl (that happens to be lifetime parameterized):

impl<'b> Trait for Test<'b> { type Out = Test<'b>; }

[pnkfelix]

So far I think that something is funky in the region inference.

Looking at the output from -Z print-region-graph as well as what the debug output reports, I see evidence that the region graph is (properly) encoding a constraint of the form:

ConstrainRegSubVar(ReFree(CodeExtent(7/CallSiteScope { fn_id: 15, body_id: 32 }), BrNamed(DefId { krate: 0, node: DefIndex(11) => silly::'y }, 'y(76))), '_#11r))

• in other words, 'y is an existentially-bound region that we know must live at least as long as the CallSiteScope for the fn, and we are encoding that this 'y <: '_#11r (or if you prefer, "the region variable '_#11r outlives 'y")

Yet despite the above constraint, the region variable is eventually "solved" and resolves as follows:

resolve_var('_#11r) = ReScope(CodeExtent(18/Misc(38)))

But this does not make sense; the node id 38 is contained within the function that is being called, so that ReScope cannot possibly be long-lived enough to satisfy the above constraint (right?)

cc @nikomatsakis

---

Update: for some reason, during expansion when we encounter the above quoted ConstrainRegSubVar, it falls into the early check if a relationship is implied by the givens. I'll keep looking; I'd like to know what given is being employed here to deduce that, but such info is not yet included in the debug! instrumentation.

BTW, here is the region constraint graph as generated by -Z print-region-graph: https://gist.github.com/pnkfelix/e643048a742b096652ab ; you can pass that into something like http://www.webgraphviz.com/ to see the picture here (the immediately relevant part being the '_#11r region variable)

relevant lines from current debug! output (prefixed by their line numbers, for my own future reference)

 838: DEBUG:rustc::middle::infer::region_inference: expansion: 
    constraint=ConstrainRegSubVar(ReFree(CodeExtent(7/CallSiteScope { fn_id: 15, body_id: 32 }), 
    BrNamed(DefId { krate: 0, node: DefIndex(11) => silly::'y }, 'y(76))), '_#11r) 
    origin=Subtype(TypeTrace(ExprAssignable(issue-30438-d.rs:11:5: 11:7)))
 839: DEBUG:rustc::middle::infer::region_inference: 
    expand_node(ReFree(CodeExtent(7/CallSiteScope{ fn_id: 15, body_id: 32 }),
    BrNamed(DefId { krate: 0, node: DefIndex(11) => silly::'y }, 'y(76))),
     '_#11r == Value(ReScope(CodeExtent(18/Misc(38)))))
 840: DEBUG:rustc::middle::infer::region_inference: given

[eddyb]

@pnkfelix you might want to wrap some of that up in code fences, it's getting reinterpreted as markdown.

[pnkfelix]

@eddyb yeah I was debating; the lines are really long so that's why I didn't do code fences at first, since I figured it was better to let the lines wrap.

I'll manually wrap the lines and add fences.

[pnkfelix]

Okay I think I found the bug.

The actual region-graph representation (as opposed to what the -Z print-region-graph code works to present via graphviz) allocates one node for every region-variable, and then allocates just one more node, at the so-called dummy-idx, to represent all of the concrete (non inference variable) regions.

(Presumably the logic here is that all such concrete regions are existentially bound and thus we can abstract them into a single node, in terms of the reasoning that will be employed for the purposes of finding solutions to the constraint sets.)

• Also, for future code archaeologists: the use of a dummy-idx dates from back when niko first switched the region-inference code to use a standalone graph abstraction, back in e706590 (July 2013!). (This does not predate the introduction of explicit lifetime variables, the syntax for which was being discussed on rust-dev as late as February 2013.)

The problem is that other code in the region_inference module assumes that we aren't playing such games. In particular, the fn expand_givens(&self, graph: &RegionGraph) method is very simple code, because it is just calling directly out to graph.depth_traverse and looping over the resulting iterator.

But that depth-first traversal will then see all the edges that are going both into and out of the single dummy-idx node! So it ends up over-expanding the givens set to include way more assumed relationships than it should.