Drop is called more than once for the same object

[glennw]

use std::mem;

struct Fragment {
    dummy: int
}

impl Fragment {
    fn new(d: int) -> Fragment {
        Fragment {
            dummy: d,
        }
    }
}

impl Drop for Fragment {
    fn drop(&mut self) {
        println!("drop {}", self.dummy);
    }
}

fn main() {
    let mut fragments = vec!();
    fragments.push(Fragment::new(1));
    fragments.push(Fragment::new(2));

    let new_fragments: Vec<Fragment> = mem::replace(&mut fragments, vec![])
        .move_iter()
        .skip_while(|fragment| {
            true
        }).collect();
}

Produces the following output:

drop 1
drop 2
drop 2

[metajack]

@zwarich reported this differs for him based on -O.

[lilyball]

On my machine (OS X) the presence of -O is irrelevant.

rustc 0.12.0-pre (7a25cf3f3 2014-07-30 17:06:18 +0000)

[metajack]

Discovered on rust @ 0582421.

[brson]

@dotdash Could this be caused by incorrect LLVM lifetime annotations?

[zwarich]

@brson The Rust we're using for the upgrade doesn't have the LLVM lifetime intrinsic changes.

[zwarich]

@metajack The example that differs for me depending on optimization settings was my further reduction, not the original:

struct Fragment;

impl Drop for Fragment {
    fn drop(&mut self) {
        println!("drop");
    }
}

fn main() {
    let mut fragments = Vec::new();
    fragments.push(Fragment);
    fragments.push(Fragment);

    fragments.move_iter()
             .skip_while(|fragment| {
                 true
             }).collect::<Vec<Fragment>>();
}

[brson]

@pnkfelix or @nick29581 do either of you have the bandwith to look into this? It's blocking servo.

[dotdash]

Adding some debug output, it looks like fragment 2 is dropped too early.

use std::mem;

struct Fragment {
    dummy: int
}

impl Fragment {
    fn new(d: int) -> Fragment {
        Fragment {
            dummy: d,
        }
    }
}

impl Drop for Fragment {
    fn drop(&mut self) {
        println!("drop {}", self.dummy);
    }
}

fn main() {
    let mut fragments = vec!();
    fragments.push(Fragment::new(1));
    fragments.push(Fragment::new(2));

    let new_fragments: Vec<Fragment> = mem::replace(&mut fragments, vec![])
        .move_iter()
        .skip_while(|fragment| {
            println!("Skip {}", fragment.dummy);
            true
        }).collect();
    std::io::println("End");
}

Gives:

Skip 1
drop 1
drop 2
Skip 0
drop 2
End

[lilyball]

After reading through the LLVM IR, the issue is in SkipWhile::next().

Here's the source of SkipWhile::next():

    fn next(&mut self) -> Option<A> {
        let mut next = self.iter.next();
        if self.flag {
            next
        } else {
            loop {
                match next {
                    Some(x) => {
                        if (self.predicate)(&x) {
                            next = self.iter.next();
                            continue
                        } else {
                            self.flag = true;
                            return Some(x)
                        }
                    }
                    None => return None
                }
            }
        }
    }

In the match case Some(x), instead of moving the Fragment out of the Option, it merely takes a pointer. Then when the predicate passes, on the line next = self.iter.next(), it drops the next value before reassigning. And then it drops x. But since x was merely a pointer into the old next, it actually ends up dropping the fragment from the new next value.

I'm not quite sure what the expected sequence here is. In the else block, both x and next get dropped, but x gets dropped after moving it into the return slot, and the drop flag is set, which causes the subsequent drop of next to do nothing. But in the then block, next gets dropped first, and x ends up pointing into the new value (and thus, very appropriately, doesn't have its zero flag set).

I suppose a fix would be to actually move the value out of next and into x (i.e. making x no longer a pointer), setting the drop flag on the fragment in next in the process. I assume the use of a pointer is deliberate though.

[lilyball]

I strongly suspect this was caused by #15076, which removed the extra alloca slot that was used to move the value out of the llmatch.

[lilyball]

cc @luqmana

[dotdash]

Yeah, that makes sense, as that is the only place that does zero-after-drop, while explains the "Skip 0" in the debugging output.

[larsbergstrom]

So, should we be trying to revert #15076 locally and everything that depends on it? Or is there a potential fix?

[lilyball]

I suspect it can be fixed by extending the Copy exception (where it still produces the second alloca) to anything that implements or contains a type that implements Drop.

There's probably some other fix that could be made that doesn't require the extra alloca, by changing when destructors are called, but that's probably complicated and may run the risk of being incorrect.

[dotdash]

No, that's not enough. If you use put Box<Fragment> into the vector, it evaluates the predicate only once, because it zeroes next and then sees a None.

[pcwalton]

Perhaps we should make allocas if you're matching and destructuring an lvalue which is mutated inside the match? Expr use visitor and mem cat should be able to tell you this.

[pcwalton]

Perhaps borrow check or a separate pass could build up a table to tell codegen when this occurs.

[pcwalton]

@larsbergstrom I suggest you work around it by just not using skip while.

[lilyball]

It occurs to me that the set of types that don't implement Copy is very nearly the same as the set of types that implement (or contain a value that implements) Drop. So skipping the alloca only for types that aren't Copy and aren't Drop leaves you with very little left.

[pcwalton]

Yes, which is why I think we should not fix this with a sledgehammer. This is an important optimization which I want to keep.

I believe this problem is specific to mutation of the matched lvalue. Rust has precise information about that, so let's use it to guide optimizations.

[lilyball]

@dotdash I'm not sure what you mean about Box<Fragment>. I just tested, and disabling the optimization for any ty::type_needs_drop(..) makes this work properly, both with Fragment and with Box<Fragment>.

However, since that effectively kills the optimization for almost all types, I agree that it's not the right fix.

Of course, disabling the optimization for all Copy types isn't great either. By tracking mutation of lvalues perhaps that restriction can be lifted as well.

[luqmana]

@kballard We're already reusing the alloca when it's a by value binding where the type would move. The problem here is reassigning to the expression you're matching on in the body of the match.

@pcwalton I'm working on this and have it working for a small no_std test. Just need to get through this ice while building libstd.

Also, this is essentially a dupe of #15571.

[lilyball]

@luqmana If you can track any mutation of the original expression, not just reassignment, then the Copy restriction can be lifted. At least according to the source comments, Copy doesn't reuse the alloca because of the worry of mutating the original value.

[dotdash]

@kballard Ah, damn, sorry. I forgot to fix that to say Box<int> (which doesn't implement Drop, but still needs drop glue). I had initially used removed the Drop impl for Fragment and used Box<Fragment>, that's why the text still said Fragment instead of int.

[lilyball]

@dotdash Ah. Well, I think ty::type_needs_drop() tests drop glue anyway, not the Drop trait.

[luqmana]

@pcwalton Ok, so I added a check using ExprUseVisitor to see if we reassign to the expr we're matching on in the arm body and if so then use a new alloca slot. Here's the diff: https://gist.github.com/76a232453cec85c1c861

Now this works for my no_std test case: https://gist.github.com/37257dd0036a7fa20085

# with master:
drop on: hi
drop on: bye
>

# with patch
drop on: hi
> bye
drop on: bye

But this ICE's while building libstd, since while looking up type_contents it encounters a ty_param whose DefId doesn't exist in p.def_id.node. Also, looking at RUST_LOG I see cat_def: id=90342 expr=fn(<generic #0>) -> core::result::Result<<generic #0>,sync::comm::stream::Failure<<generic #0>>> def=DefVariant(syntax::ast::DefId{krate: 2u32, node: 48433u32}, syntax::ast::DefId{krate: 2u32, node: 48434u32}, false) but at this stage in trans shouldn't we already have all the types?

[lilyball]

It occurs to me that just tracking mutable borrows would not be sufficient (not that @luqmana is doing that, but it was a suggestion), because UnsafeCell means that a value could be mutated without a mutable borrow.

[pcwalton]

@luqmana You may have to call monomorphize_type somewhere.

[pcwalton]

@kballard Yeah, we might need to look at Share kind

[lilyball]

@pcwalton Well, the whole point of the suggestion was to drop the Copy restriction. As long as Copy types still produce a new alloca then we don't have to do anything at all (because non-Copy types will move, and you can't mutate a moved value).

[nrc]

@brson I have time this week, but actually it looks like @luqmana has a fix. Let me know if I can be useful somehow.