[NLL] used-mut lint has an O(n^2) loop

[nikomatsakis]

The following snippet of code is an O(n^2) loop:

https://gist.github.com/lqd/7e178cb9ac8302e24272965048627f21#file-mod-rs-L243-L256

The problem is that we are iterating over each temporary and then invoking find_assignments, which basically walks over the MIR again. What we really want to be doing is walking the MIR at most once (ideally, coallesced into some other walk) and registered the "used mut" assignments.

[nikomatsakis]

I actually find this loop a bit strange -- I'm not convinced it's the right way to handle whatever problem it is solving. =) (IIRC, it is aiming to address the fact that sometimes in MIR we operate on a temporary instead of the actual local -- but it'd be interesting to remove the loop and try to see what breaks and see if we can find another way to fix it.)

Regardless, if we just want to keep the current behavior "but faster", I think we can do it via a single visit. The visitor would work much like the existing FindAssignments visitor:

rust/src/librustc_mir/util/collect_writes.rs

Line 16 in 6ec1b62

crate trait FindAssignments {

In particular, it would override visit_local:

rust/src/librustc_mir/util/collect_writes.rs

Lines 38 to 41 in 6ec1b62

	fn visit_local(&mut self,
	local: &Local,
	place_context: PlaceContext<'tcx>,
	location: Location) {

But instead of having a specific "needle" it is looking for:

rust/src/librustc_mir/util/collect_writes.rs

Lines 42 to 44 in 6ec1b62

	if self.needle != *local {
	return;
	}

It would rather search for any assignment to a local that is in the temporary_used_locals set. When it finds one, it would execute propagation code:

rust/src/librustc_mir/borrow_check/mod.rs

Lines 287 to 295 in 6ec1b62

	for moi in &mbcx.move_data.loc_map[location] {
	let mpi = &mbcx.move_data.moves[*moi].path;
	let path = &mbcx.move_data.move_paths[*mpi];
	debug!("assignment of {:?} to {:?}, adding {:?} to used mutable set",
	path.place, local, path.place);
	if let Place::Local(user_local) = path.place {
	mbcx.used_mut.insert(user_local);
	}
	}