make causal tracking lazy

[nikomatsakis]

The current NLL code tracks "causal" information so that we can give nice errors (see #45988 for more information). The intention is that we will only compute this information once an error is detected. At present, though, we compute it all the time. We should not do that.

The causal tracking code can be found in values.rs. In fact, the RegionValues::new method already takes a boolean parameter track_causes indicating whether to track causes, but the RegionInferenceContext, which creates the value sets, currently always passes true.

We have to think on the best way to do this. My preference would be to package this "extended causal information" up as a kind of query, so that the MIR borrowck can perform the query only when needed. We would alter the NLL analysis so that it passes false for causal information, but then this new query would re-run the NLL analysis, but passing true (like we do today). There are some challenges here though: what format should the result of the query be in, for example?

(The reason I wanted a query is that I wanted IDEs and other things to be able to query this information for borrow visualization, and having it be "local" to the borrowck wouldn't offer any visibility for those tools.)

It may however be easier to start by having the borrowck itself just re-run the NLL analysis locally (with tracking enabled) when needed.

[nikomatsakis]

Before we make things lazy, we could also just do some optimization here. The current causal tracking maintains "maximal information", basically, by keeping the entire "cause chain". The current code uses an Rc to share the chain. This requires a lot of allocation and work that is pretty expensive. But when we report errors we only use the last link in the chain.

I propose that we alter the definition of the Cause enum to something like:

pub(crate) struct Cause {
    /// Length of the outlives chain. This is intentionally first so that we
    /// prefer causes that are more directly related (fewer outlives links).
    outlives: u32,

    /// The "root cause" -- basically, what is live?
    root_cause: RootCause,
}

// (this is the old cause enum, minus the `Outlives` variant)
pub(crate) enum RootCause {
    /// point inserted because Local was live at the given Location
    LiveVar(Local, Location),

    /// point inserted because Local was dropped at the given Location
    DropVar(Local, Location),

    /// point inserted because the type was live at the given Location,
    /// but not as part of some local variable
    LiveOther(Location),

    /// part of the initial set of values for a universally quantified region
    UniversalRegion(RegionVid),
}

This only tracks the root cause and the number of outlives obligations it took to get there. We can then alter the cause map type to remove the Rc:

type CauseMap = FxHashMap<(RegionVid, RegionElementIndex), Cause>;

In fact, since the number of regions and region-elements are fixed, we could change it to a big vector:

Vec<Option<Cause>>

If the old key was (r, e), this would then correspond to the vector index of r * elements.num_elements() + e.

Finally, we would no longer need the Rc::new calls in add_internal.

[nikomatsakis]

It'd be good to measure the running time on various examples. Just test by configuring -Znll-dump-causes.

[chrisvittal]

I'll take a look here. If you don't mind.

[nikomatsakis]

OK, so, I talked to @spastorino a bunch in a private chat on how to implement this. I want to leave some brief notes on the plan I drew up. It doesn't yet support a query for use by IDEs, but it should let us fix the immediate problem of not having good diagnostic output.

The key ideas are:

Always enable causal tracking when creating the liveness_constraints value

When propagating constraints, instead of just cloning liveness_constraints to get a starting point, we will add a new method to RegionValues that copies the core data but not the causal data and use that.

Add a new type RegionCausalInfo in the nll::region_infer module:

crate struct RegionCausalInfo {
    inferred_values: RegionValues
}

and add a method to RegionInferenceContext to compute it:

impl RegionInferenceContext {
    crate fn compute_causal_info(&self) -> RegionCausalInfo {
        // same thing as `propagate_constraints` today:
        // - clone the liveness values (keeping the causal information this time!)
        // - propagate the constraints on those values
    }
}

Move the why_borrow_contains_point function onto this type.

Then add a field to MirBorrowckContext:

nonlexical_cause_info: Option<RegionCauseInfo<'tcx>>

and modify explain_why_borrow_containts_point to be &mut self. It can then lazilly initialize this field:

if self.nonlexical_cause_info.is_none() {
    let region_cx = self.nonlexical_regioncx.as_ref().unwrap();
    self.nonlexical_cause_info = Some(region_cx.compute_cause_info());
}

Then it can invoke why_borrow_contains_point on the nonlexical_cause_info instead of the inference context.

Fin.

[nikomatsakis]

For reference, @chrisvittal made the Rc-improvements I described: they posted a link on gitter to their branch

[chrisvittal]

After a bit of work, I've put my changes on top of @spastorino's branch, and also squashed them. That branch is here