smarter blame assignment for lifetime inference errors

[nikomatsakis]

Consider this example (try it on play):

#![feature(match_default_bindings)]

use std::cell::RefCell;
use std::collections::HashMap;

struct Cx<'cx> {
  types: RefCell<HashMap<&'cx str, String>>,
}

enum Lvalue<'cx> {
  Var(&'cx str),
  Deref(Box<Lvalue<'cx>>),
}

impl<'cx> Lvalue<'cx> {
  fn ty(&self, cx: &Cx<'cx>) -> String {
    match self {
      Lvalue::Deref(base) => format!("&{}", base.ty(cx)),
      Lvalue::Var(v) => cx.types.borrow()[v].clone(),
    }
  }
}

fn describe<'cx>(lvalue: Lvalue, cx: &Cx<'cx>) -> String {
    match lvalue {
      Lvalue::Deref(base) => format!("deref of {} pointer", base.ty(cx)),
      Lvalue::Var(v) => format!("variable `{}`", v),
    }
}

fn main() { }

I get the error:

error[E0621]: explicit lifetime required in the type of `lvalue`
  --> src/main.rs:26:69
   |
24 | fn describe<'cx>(lvalue: Lvalue, cx: &Cx<'cx>) -> String {
   |                  ------ consider changing the type of `lvalue` to `Lvalue<'cx>`
25 |     match lvalue {
26 |       Lvalue::Deref(base) => format!("deref of {} pointer", base.ty(cx)),
   |                                                                     ^^ lifetime `'cx` required

This is pretty good, but I think it would be better if we moved the highlight off of cx, which has the correct type, and over perhaps to base, which does not, or perhaps to the function call ty:

error[E0621]: explicit lifetime required in the type of `lvalue`
  --> src/main.rs:26:69
   |
24 | fn describe<'cx>(lvalue: Lvalue, cx: &Cx<'cx>) -> String {
   |                  ------ consider changing the type of `lvalue` to `Lvalue<'cx>`
25 |     match lvalue {
26 |       Lvalue::Deref(base) => format!("deref of {} pointer", base.ty(cx)),
   |                                                                  ^^ lifetime `'cx` required

I think a better analysis of the region inference graph could tell us what to highlight. Right now I believe we blame the edge that introduced the unsatisfiable constraint. In this case, the edge that introduced 'cx corresponds to the parameter cx. But we really want to blame the edge that brought the unsatisfiable constraint into "tension", which I think is generally the point where contravariance is introduced (iow, parameters to function calls). But I suspect we can get decent results with just a simple weighting of the causes for introducing each edge.

[cengiz-io]

I'd like to work on this if possible

[estebank]

Fixed:

error[E0621]: explicit lifetime required in the type of `lvalue`
  --> src/main.rs:26:69
   |
24 | fn describe<'cx>(lvalue: Lvalue, cx: &Cx<'cx>) -> String {
   |                          ------ help: add explicit lifetime `'cx` to the type of `lvalue`: `Lvalue<'cx>`
25 |     match lvalue {
26 |       Lvalue::Deref(base) => format!("deref of {} pointer", base.ty(cx)),
   |                                                                     ^^ lifetime `'cx` required