Rust-analyzer: Introduce hir::Expr

[matklad]

Currently, name resolution and type inference is based on the concrete syntax trees (and LocalSyntaxPtrs). This is suboptimal for three reasons:

• syntax trees change after each change to the text of the file, causing recomputation of name res and type inference
• syntax trees are a heavy-weight immutable data structure, with a high memory overhead. We should miminize the scope where syntax trees are used
• syntax trees represent (and will probably always represent) a pre-expansion source code, so macro expansion would have to be handled explicitly.

One solution to this problem is to lower SyntaxNodes into a hir::Expr, defined as follows:

pub type Expr = Id<ExprData>;
#[derive(Eq, PartialEq)] // for salsa
pub struct ExprTable { // ExprTable for a specific item, most commonly function
    exprs: Arena<ExprData>,
}

#[derive(Eq, PartialEq)]
enum ExprData {
    /// This is produced if syntax tree does not have a required expression piece
    Missing,
    Path(hir::Path),
    Binary { lhs: Expr, rhs: Expr, op: BinOp }   
}

This representation is position-independent and salsa friendly. To be able to map to concrete syntas though, we'll need the following pair of queries:

// This one is syntax-dependent, we'll need to GC it
fn compute_def_expr_table(def_id: DefId) -> (ExprTable, FxHashMap<LocalSyntaxPtr, Expr>, FxHashMap<Expr, LocalSyntaxPtr>) {
}

// This is a salsa-friendly projection
fn def_expr_table(def_id: DefId) -> ExprTable {
    compute_def_expr_table(def_id).0
}

[matklad]

I'll work on initial macro expansion support next, and after that I can do hir::Expr, if @flodiebold doesn't beat me to it :) I feel like we should introduce hir::Expr before diving too deep into type inference, so as to avoid rewriting too much of the match expressions

[flodiebold]

Here's some more random notes about this:

• there's a few things we will probably want to desugar when going from AST to HIR:
  
  
  
  • field shorthand in struct literals
  
  
  • there's no need for ParenExpr in HIR
  
  
  • rustc desugars for and while let loops into loop when lowering to its HIR, I'm not sure if we want to do the same
  
  
  • similar for if let -> match
  
  
  • self params should probably be represented explicitly (i.e. &self should result in the same HIR as self: &Self etc.) (though that's not directly related to expressions, I guess...)
  
  
  • I think we'll need hir::Pat for patterns at the same time (since they'll appear in match expressions etc.)
  
  
  • ast::TypeRefs should be turned into hir::TypeRefs, of course
  
  

[flodiebold]

I'll have a go at this now.

[flodiebold]

This is done now.