Catching unnecessary clones

[Manishearth]

Not sure what the heuristics for this should be. Will have to think.

[llogiq]

As you recently noted that you are currently thinking on how to implement this, why not pool our neuronal resources and think in the open?

To create a good lint against unnecessary clones, we have a few problems ranging from very easy to near impossible:

'1. (ridiculously easy) Finding a .clone() call.
'2. (easy enough) Finding out the status of the cloned value pertaining to the current code (borrowed / mutably borrowed / owned)
'3. (easy enough) Finding out how the operation / call / ... takes the value (borrow / mutable borrow / by value)
'4. (medium) Finding out if the value is internally mutable

At this point we could already lint against clones of non internally mutable values just for borrowing them immutably. It's not much, but it's a start. There is one caveat however: We'd somehow need to be sure to rule out side effects on cloning or mutating the value (e.g. some global registry could be updated).

'5. (medium) Finding out if the original value is used elsewhere afterwards

At this point we could lint against clones for those by-value ops, with the aforementioned caveat.

'6. (hard) Finding out if the op/call mutates the value (if it is internally mutable or borrowed mutably)

At this point we could add cases where the value isn't mutated to our lint (for mutably borrowed or internally mutable values). The caveat against side effects from above applies here, too.

'7. (near impossible) Finding out if cloning or the checked operation on the value has any side effects.

If we can rule this out, the caveat no longer applies, and we have a lint that warns against unnecessary clones without any false positives.

There is still one problem left:

'8. (near impossible) Creating a good suggestion depending on how the value is available and is used – for example we may have to make lifetimes line up to ensure the original value can even be used.

Perhaps we should add an [E-impossible] label for such things?

[llogiq]

At least for '4, '6 and '7, blacklisting would give us a good bang for quite little buck. For those cases, '8 would probably also be tractable.

Perhaps we should ask the compiler to annotate types with "is internally mutable" flags (edit: On the other hand, it would probably suffice to look at the public fields and look for mutable interior there), method arguments with "is mutated during this method" and methods with "mutate global state". This would allow us to do all the above analysis (apart from '8, which I think is still hard) in a reliable way.

[Manishearth]

Oh, that's not the type of lint I meant. I was focusing on moving and clones. Basically, in many cases folks clone things when the variable could be moved out.

For example:

fn main() {
  let x = vec![];
  foo(x.clone());
  bar(x.clone()); // should have been just `x`
 // x no longer used here
}

Such things can lead to massive perf improvements are actually quite a common pitfall since Rust often makes folks clone() until it works.

I suspect the "unused variable" lint (which uses ExprUseVisitor) can be tweaked so that a clone is not counted as a "use" (this fixes the above case). But, this may not be perfect when it comes to branching (I need to think about this more).

The alternative is to set up a bit vector framework similar to live variables analysis with a couple more states, and feed it the control flow graph. This isn't too hard either, but needs me to sit down with a whiteboard.

[llogiq]

But what if too or bar modify the vec?

[llogiq]

Oops, wrong button.

[birkenfeld]

We just have to take care not to count clone()s on references. I would actually be very interested in how this:

The alternative is to set up a bit vector framework similar to live variables analysis with a couple more states, and feed it the control flow graph. This isn't too hard either, but needs me to sit down with a whiteboard.

would be done within the rustc framework.

[birkenfeld]

But what if too or bar modify the vec?

Well, you can't use the vec after the function ends anyway, so it doesn't matter if bar modifies it. And foo has to get a clone in any case.

[llogiq]

True that. In that case the analysis is actually easier than I thought.

[Manishearth]

Yep. We don't care about mutation. This is about liveness/use.