Merge branch 'master' of https://github.com/rust-analyzer/rust-analyzer into feature/themes

5 files changed, 1283 insertions, 20 deletions

diff --git a/crates/ra_hir_def/src/body.rs b/crates/ra_hir_def/src/body.rs
new file mode 100644
index 000000000..ac8f8261b
--- /dev/null
+++ b/crates/ra_hir_def/src/body.rs
@@ -0,0 +1,144 @@
+//! FIXME: write short doc here
+mod lower;
+
+use std::{ops::Index, sync::Arc};
+
+use hir_expand::{either::Either, HirFileId, MacroDefId, Source};
+use ra_arena::{map::ArenaMap, Arena};
+use ra_syntax::{ast, AstPtr};
+use rustc_hash::FxHashMap;
+
+use crate::{
+    db::DefDatabase2,
+    expr::{Expr, ExprId, Pat, PatId},
+    nameres::CrateDefMap,
+    path::Path,
+    ModuleId,
+};
+
+pub struct MacroResolver {
+    crate_def_map: Arc<CrateDefMap>,
+    module: ModuleId,
+}
+
+impl MacroResolver {
+    pub fn new(db: &impl DefDatabase2, module: ModuleId) -> MacroResolver {
+        MacroResolver { crate_def_map: db.crate_def_map(module.krate), module }
+    }
+
+    pub(crate) fn resolve_path_as_macro(
+        &self,
+        db: &impl DefDatabase2,
+        path: &Path,
+    ) -> Option<MacroDefId> {
+        self.crate_def_map.resolve_path(db, self.module.module_id, path).0.get_macros()
+    }
+}
+
+/// The body of an item (function, const etc.).
+#[derive(Debug, Eq, PartialEq)]
+pub struct Body {
+    exprs: Arena<ExprId, Expr>,
+    pats: Arena<PatId, Pat>,
+    /// The patterns for the function's parameters. While the parameter types are
+    /// part of the function signature, the patterns are not (they don't change
+    /// the external type of the function).
+    ///
+    /// If this `Body` is for the body of a constant, this will just be
+    /// empty.
+    params: Vec<PatId>,
+    /// The `ExprId` of the actual body expression.
+    body_expr: ExprId,
+}
+
+pub type ExprPtr = Either<AstPtr<ast::Expr>, AstPtr<ast::RecordField>>;
+pub type ExprSource = Source<ExprPtr>;
+
+pub type PatPtr = Either<AstPtr<ast::Pat>, AstPtr<ast::SelfParam>>;
+pub type PatSource = Source<PatPtr>;
+
+/// An item body together with the mapping from syntax nodes to HIR expression
+/// IDs. This is needed to go from e.g. a position in a file to the HIR
+/// expression containing it; but for type inference etc., we want to operate on
+/// a structure that is agnostic to the actual positions of expressions in the
+/// file, so that we don't recompute types whenever some whitespace is typed.
+///
+/// One complication here is that, due to macro expansion, a single `Body` might
+/// be spread across several files. So, for each ExprId and PatId, we record
+/// both the HirFileId and the position inside the file. However, we only store
+/// AST -> ExprId mapping for non-macro files, as it is not clear how to handle
+/// this properly for macros.
+#[derive(Default, Debug, Eq, PartialEq)]
+pub struct BodySourceMap {
+    expr_map: FxHashMap<ExprPtr, ExprId>,
+    expr_map_back: ArenaMap<ExprId, ExprSource>,
+    pat_map: FxHashMap<PatPtr, PatId>,
+    pat_map_back: ArenaMap<PatId, PatSource>,
+    field_map: FxHashMap<(ExprId, usize), AstPtr<ast::RecordField>>,
+}
+
+impl Body {
+    pub fn new(
+        db: &impl DefDatabase2,
+        resolver: MacroResolver,
+        file_id: HirFileId,
+        params: Option<ast::ParamList>,
+        body: Option<ast::Expr>,
+    ) -> (Body, BodySourceMap) {
+        lower::lower(db, resolver, file_id, params, body)
+    }
+
+    pub fn params(&self) -> &[PatId] {
+        &self.params
+    }
+
+    pub fn body_expr(&self) -> ExprId {
+        self.body_expr
+    }
+
+    pub fn exprs(&self) -> impl Iterator<Item = (ExprId, &Expr)> {
+        self.exprs.iter()
+    }
+
+    pub fn pats(&self) -> impl Iterator<Item = (PatId, &Pat)> {
+        self.pats.iter()
+    }
+}
+
+impl Index<ExprId> for Body {
+    type Output = Expr;
+
+    fn index(&self, expr: ExprId) -> &Expr {
+        &self.exprs[expr]
+    }
+}
+
+impl Index<PatId> for Body {
+    type Output = Pat;
+
+    fn index(&self, pat: PatId) -> &Pat {
+        &self.pats[pat]
+    }
+}
+
+impl BodySourceMap {
+    pub fn expr_syntax(&self, expr: ExprId) -> Option<ExprSource> {
+        self.expr_map_back.get(expr).copied()
+    }
+
+    pub fn node_expr(&self, node: &ast::Expr) -> Option<ExprId> {
+        self.expr_map.get(&Either::A(AstPtr::new(node))).cloned()
+    }
+
+    pub fn pat_syntax(&self, pat: PatId) -> Option<PatSource> {
+        self.pat_map_back.get(pat).copied()
+    }
+
+    pub fn node_pat(&self, node: &ast::Pat) -> Option<PatId> {
+        self.pat_map.get(&Either::A(AstPtr::new(node))).cloned()
+    }
+
+    pub fn field_syntax(&self, expr: ExprId, field: usize) -> AstPtr<ast::RecordField> {
+        self.field_map[&(expr, field)]
+    }
+}
diff --git a/crates/ra_hir_def/src/body/lower.rs b/crates/ra_hir_def/src/body/lower.rs
new file mode 100644
index 000000000..2aa863c9e
--- /dev/null
+++ b/crates/ra_hir_def/src/body/lower.rs
@@ -0,0 +1,631 @@
+//! FIXME: write short doc here
+
+use hir_expand::{
+    either::Either,
+    hygiene::Hygiene,
+    name::{self, AsName, Name},
+    AstId, HirFileId, MacroCallLoc, MacroFileKind, Source,
+};
+use ra_arena::Arena;
+use ra_syntax::{
+    ast::{
+        self, ArgListOwner, ArrayExprKind, LiteralKind, LoopBodyOwner, NameOwner,
+        TypeAscriptionOwner,
+    },
+    AstNode, AstPtr,
+};
+
+use crate::{
+    body::{Body, BodySourceMap, MacroResolver, PatPtr},
+    builtin_type::{BuiltinFloat, BuiltinInt},
+    db::DefDatabase2,
+    expr::{
+        ArithOp, Array, BinaryOp, BindingAnnotation, CmpOp, Expr, ExprId, Literal, LogicOp,
+        MatchArm, Ordering, Pat, PatId, RecordFieldPat, RecordLitField, Statement,
+    },
+    path::GenericArgs,
+    path::Path,
+    type_ref::{Mutability, TypeRef},
+};
+
+pub(super) fn lower(
+    db: &impl DefDatabase2,
+    resolver: MacroResolver,
+    file_id: HirFileId,
+    params: Option<ast::ParamList>,
+    body: Option<ast::Expr>,
+) -> (Body, BodySourceMap) {
+    ExprCollector {
+        resolver,
+        db,
+        original_file_id: file_id,
+        current_file_id: file_id,
+        source_map: BodySourceMap::default(),
+        body: Body {
+            exprs: Arena::default(),
+            pats: Arena::default(),
+            params: Vec::new(),
+            body_expr: ExprId::dummy(),
+        },
+    }
+    .collect(params, body)
+}
+
+struct ExprCollector<DB> {
+    db: DB,
+    resolver: MacroResolver,
+    original_file_id: HirFileId,
+    current_file_id: HirFileId,
+
+    body: Body,
+    source_map: BodySourceMap,
+}
+
+impl<'a, DB> ExprCollector<&'a DB>
+where
+    DB: DefDatabase2,
+{
+    fn collect(
+        mut self,
+        param_list: Option<ast::ParamList>,
+        body: Option<ast::Expr>,
+    ) -> (Body, BodySourceMap) {
+        if let Some(param_list) = param_list {
+            if let Some(self_param) = param_list.self_param() {
+                let ptr = AstPtr::new(&self_param);
+                let param_pat = self.alloc_pat(
+                    Pat::Bind {
+                        name: name::SELF_PARAM,
+                        mode: BindingAnnotation::Unannotated,
+                        subpat: None,
+                    },
+                    Either::B(ptr),
+                );
+                self.body.params.push(param_pat);
+            }
+
+            for param in param_list.params() {
+                let pat = match param.pat() {
+                    None => continue,
+                    Some(pat) => pat,
+                };
+                let param_pat = self.collect_pat(pat);
+                self.body.params.push(param_pat);
+            }
+        };
+
+        self.body.body_expr = self.collect_expr_opt(body);
+        (self.body, self.source_map)
+    }
+
+    fn alloc_expr(&mut self, expr: Expr, ptr: AstPtr<ast::Expr>) -> ExprId {
+        let ptr = Either::A(ptr);
+        let id = self.body.exprs.alloc(expr);
+        if self.current_file_id == self.original_file_id {
+            self.source_map.expr_map.insert(ptr, id);
+        }
+        self.source_map
+            .expr_map_back
+            .insert(id, Source { file_id: self.current_file_id, ast: ptr });
+        id
+    }
+    // desugared exprs don't have ptr, that's wrong and should be fixed
+    // somehow.
+    fn alloc_expr_desugared(&mut self, expr: Expr) -> ExprId {
+        self.body.exprs.alloc(expr)
+    }
+    fn alloc_expr_field_shorthand(&mut self, expr: Expr, ptr: AstPtr<ast::RecordField>) -> ExprId {
+        let ptr = Either::B(ptr);
+        let id = self.body.exprs.alloc(expr);
+        if self.current_file_id == self.original_file_id {
+            self.source_map.expr_map.insert(ptr, id);
+        }
+        self.source_map
+            .expr_map_back
+            .insert(id, Source { file_id: self.current_file_id, ast: ptr });
+        id
+    }
+    fn alloc_pat(&mut self, pat: Pat, ptr: PatPtr) -> PatId {
+        let id = self.body.pats.alloc(pat);
+        if self.current_file_id == self.original_file_id {
+            self.source_map.pat_map.insert(ptr, id);
+        }
+        self.source_map.pat_map_back.insert(id, Source { file_id: self.current_file_id, ast: ptr });
+        id
+    }
+
+    fn empty_block(&mut self) -> ExprId {
+        let block = Expr::Block { statements: Vec::new(), tail: None };
+        self.body.exprs.alloc(block)
+    }
+
+    fn missing_expr(&mut self) -> ExprId {
+        self.body.exprs.alloc(Expr::Missing)
+    }
+
+    fn missing_pat(&mut self) -> PatId {
+        self.body.pats.alloc(Pat::Missing)
+    }
+
+    fn collect_expr(&mut self, expr: ast::Expr) -> ExprId {
+        let syntax_ptr = AstPtr::new(&expr);
+        match expr {
+            ast::Expr::IfExpr(e) => {
+                let then_branch = self.collect_block_opt(e.then_branch());
+
+                let else_branch = e.else_branch().map(|b| match b {
+                    ast::ElseBranch::Block(it) => self.collect_block(it),
+                    ast::ElseBranch::IfExpr(elif) => {
+                        let expr: ast::Expr = ast::Expr::cast(elif.syntax().clone()).unwrap();
+                        self.collect_expr(expr)
+                    }
+                });
+
+                let condition = match e.condition() {
+                    None => self.missing_expr(),
+                    Some(condition) => match condition.pat() {
+                        None => self.collect_expr_opt(condition.expr()),
+                        // if let -- desugar to match
+                        Some(pat) => {
+                            let pat = self.collect_pat(pat);
+                            let match_expr = self.collect_expr_opt(condition.expr());
+                            let placeholder_pat = self.missing_pat();
+                            let arms = vec![
+                                MatchArm { pats: vec![pat], expr: then_branch, guard: None },
+                                MatchArm {
+                                    pats: vec![placeholder_pat],
+                                    expr: else_branch.unwrap_or_else(|| self.empty_block()),
+                                    guard: None,
+                                },
+                            ];
+                            return self
+                                .alloc_expr(Expr::Match { expr: match_expr, arms }, syntax_ptr);
+                        }
+                    },
+                };
+
+                self.alloc_expr(Expr::If { condition, then_branch, else_branch }, syntax_ptr)
+            }
+            ast::Expr::TryBlockExpr(e) => {
+                let body = self.collect_block_opt(e.body());
+                self.alloc_expr(Expr::TryBlock { body }, syntax_ptr)
+            }
+            ast::Expr::BlockExpr(e) => self.collect_block(e),
+            ast::Expr::LoopExpr(e) => {
+                let body = self.collect_block_opt(e.loop_body());
+                self.alloc_expr(Expr::Loop { body }, syntax_ptr)
+            }
+            ast::Expr::WhileExpr(e) => {
+                let body = self.collect_block_opt(e.loop_body());
+
+                let condition = match e.condition() {
+                    None => self.missing_expr(),
+                    Some(condition) => match condition.pat() {
+                        None => self.collect_expr_opt(condition.expr()),
+                        // if let -- desugar to match
+                        Some(pat) => {
+                            let pat = self.collect_pat(pat);
+                            let match_expr = self.collect_expr_opt(condition.expr());
+                            let placeholder_pat = self.missing_pat();
+                            let break_ = self.alloc_expr_desugared(Expr::Break { expr: None });
+                            let arms = vec![
+                                MatchArm { pats: vec![pat], expr: body, guard: None },
+                                MatchArm { pats: vec![placeholder_pat], expr: break_, guard: None },
+                            ];
+                            let match_expr =
+                                self.alloc_expr_desugared(Expr::Match { expr: match_expr, arms });
+                            return self.alloc_expr(Expr::Loop { body: match_expr }, syntax_ptr);
+                        }
+                    },
+                };
+
+                self.alloc_expr(Expr::While { condition, body }, syntax_ptr)
+            }
+            ast::Expr::ForExpr(e) => {
+                let iterable = self.collect_expr_opt(e.iterable());
+                let pat = self.collect_pat_opt(e.pat());
+                let body = self.collect_block_opt(e.loop_body());
+                self.alloc_expr(Expr::For { iterable, pat, body }, syntax_ptr)
+            }
+            ast::Expr::CallExpr(e) => {
+                let callee = self.collect_expr_opt(e.expr());
+                let args = if let Some(arg_list) = e.arg_list() {
+                    arg_list.args().map(|e| self.collect_expr(e)).collect()
+                } else {
+                    Vec::new()
+                };
+                self.alloc_expr(Expr::Call { callee, args }, syntax_ptr)
+            }
+            ast::Expr::MethodCallExpr(e) => {
+                let receiver = self.collect_expr_opt(e.expr());
+                let args = if let Some(arg_list) = e.arg_list() {
+                    arg_list.args().map(|e| self.collect_expr(e)).collect()
+                } else {
+                    Vec::new()
+                };
+                let method_name = e.name_ref().map(|nr| nr.as_name()).unwrap_or_else(Name::missing);
+                let generic_args = e.type_arg_list().and_then(GenericArgs::from_ast);
+                self.alloc_expr(
+                    Expr::MethodCall { receiver, method_name, args, generic_args },
+                    syntax_ptr,
+                )
+            }
+            ast::Expr::MatchExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                let arms = if let Some(match_arm_list) = e.match_arm_list() {
+                    match_arm_list
+                        .arms()
+                        .map(|arm| MatchArm {
+                            pats: arm.pats().map(|p| self.collect_pat(p)).collect(),
+                            expr: self.collect_expr_opt(arm.expr()),
+                            guard: arm
+                                .guard()
+                                .and_then(|guard| guard.expr())
+                                .map(|e| self.collect_expr(e)),
+                        })
+                        .collect()
+                } else {
+                    Vec::new()
+                };
+                self.alloc_expr(Expr::Match { expr, arms }, syntax_ptr)
+            }
+            ast::Expr::PathExpr(e) => {
+                let path = e
+                    .path()
+                    .and_then(|path| self.parse_path(path))
+                    .map(Expr::Path)
+                    .unwrap_or(Expr::Missing);
+                self.alloc_expr(path, syntax_ptr)
+            }
+            ast::Expr::ContinueExpr(_e) => {
+                // FIXME: labels
+                self.alloc_expr(Expr::Continue, syntax_ptr)
+            }
+            ast::Expr::BreakExpr(e) => {
+                let expr = e.expr().map(|e| self.collect_expr(e));
+                self.alloc_expr(Expr::Break { expr }, syntax_ptr)
+            }
+            ast::Expr::ParenExpr(e) => {
+                let inner = self.collect_expr_opt(e.expr());
+                // make the paren expr point to the inner expression as well
+                self.source_map.expr_map.insert(Either::A(syntax_ptr), inner);
+                inner
+            }
+            ast::Expr::ReturnExpr(e) => {
+                let expr = e.expr().map(|e| self.collect_expr(e));
+                self.alloc_expr(Expr::Return { expr }, syntax_ptr)
+            }
+            ast::Expr::RecordLit(e) => {
+                let path = e.path().and_then(|path| self.parse_path(path));
+                let mut field_ptrs = Vec::new();
+                let record_lit = if let Some(nfl) = e.record_field_list() {
+                    let fields = nfl
+                        .fields()
+                        .inspect(|field| field_ptrs.push(AstPtr::new(field)))
+                        .map(|field| RecordLitField {
+                            name: field
+                                .name_ref()
+                                .map(|nr| nr.as_name())
+                                .unwrap_or_else(Name::missing),
+                            expr: if let Some(e) = field.expr() {
+                                self.collect_expr(e)
+                            } else if let Some(nr) = field.name_ref() {
+                                // field shorthand
+                                self.alloc_expr_field_shorthand(
+                                    Expr::Path(Path::from_name_ref(&nr)),
+                                    AstPtr::new(&field),
+                                )
+                            } else {
+                                self.missing_expr()
+                            },
+                        })
+                        .collect();
+                    let spread = nfl.spread().map(|s| self.collect_expr(s));
+                    Expr::RecordLit { path, fields, spread }
+                } else {
+                    Expr::RecordLit { path, fields: Vec::new(), spread: None }
+                };
+
+                let res = self.alloc_expr(record_lit, syntax_ptr);
+                for (i, ptr) in field_ptrs.into_iter().enumerate() {
+                    self.source_map.field_map.insert((res, i), ptr);
+                }
+                res
+            }
+            ast::Expr::FieldExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                let name = match e.field_access() {
+                    Some(kind) => kind.as_name(),
+                    _ => Name::missing(),
+                };
+                self.alloc_expr(Expr::Field { expr, name }, syntax_ptr)
+            }
+            ast::Expr::AwaitExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                self.alloc_expr(Expr::Await { expr }, syntax_ptr)
+            }
+            ast::Expr::TryExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                self.alloc_expr(Expr::Try { expr }, syntax_ptr)
+            }
+            ast::Expr::CastExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                let type_ref = TypeRef::from_ast_opt(e.type_ref());
+                self.alloc_expr(Expr::Cast { expr, type_ref }, syntax_ptr)
+            }
+            ast::Expr::RefExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                let mutability = Mutability::from_mutable(e.is_mut());
+                self.alloc_expr(Expr::Ref { expr, mutability }, syntax_ptr)
+            }
+            ast::Expr::PrefixExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                if let Some(op) = e.op_kind() {
+                    self.alloc_expr(Expr::UnaryOp { expr, op }, syntax_ptr)
+                } else {
+                    self.alloc_expr(Expr::Missing, syntax_ptr)
+                }
+            }
+            ast::Expr::LambdaExpr(e) => {
+                let mut args = Vec::new();
+                let mut arg_types = Vec::new();
+                if let Some(pl) = e.param_list() {
+                    for param in pl.params() {
+                        let pat = self.collect_pat_opt(param.pat());
+                        let type_ref = param.ascribed_type().map(TypeRef::from_ast);
+                        args.push(pat);
+                        arg_types.push(type_ref);
+                    }
+                }
+                let body = self.collect_expr_opt(e.body());
+                self.alloc_expr(Expr::Lambda { args, arg_types, body }, syntax_ptr)
+            }
+            ast::Expr::BinExpr(e) => {
+                let lhs = self.collect_expr_opt(e.lhs());
+                let rhs = self.collect_expr_opt(e.rhs());
+                let op = e.op_kind().map(BinaryOp::from);
+                self.alloc_expr(Expr::BinaryOp { lhs, rhs, op }, syntax_ptr)
+            }
+            ast::Expr::TupleExpr(e) => {
+                let exprs = e.exprs().map(|expr| self.collect_expr(expr)).collect();
+                self.alloc_expr(Expr::Tuple { exprs }, syntax_ptr)
+            }
+            ast::Expr::BoxExpr(e) => {
+                let expr = self.collect_expr_opt(e.expr());
+                self.alloc_expr(Expr::Box { expr }, syntax_ptr)
+            }
+
+            ast::Expr::ArrayExpr(e) => {
+                let kind = e.kind();
+
+                match kind {
+                    ArrayExprKind::ElementList(e) => {
+                        let exprs = e.map(|expr| self.collect_expr(expr)).collect();
+                        self.alloc_expr(Expr::Array(Array::ElementList(exprs)), syntax_ptr)
+                    }
+                    ArrayExprKind::Repeat { initializer, repeat } => {
+                        let initializer = self.collect_expr_opt(initializer);
+                        let repeat = self.collect_expr_opt(repeat);
+                        self.alloc_expr(
+                            Expr::Array(Array::Repeat { initializer, repeat }),
+                            syntax_ptr,
+                        )
+                    }
+                }
+            }
+
+            ast::Expr::Literal(e) => {
+                let lit = match e.kind() {
+                    LiteralKind::IntNumber { suffix } => {
+                        let known_name = suffix.and_then(|it| BuiltinInt::from_suffix(&it));
+
+                        Literal::Int(Default::default(), known_name)
+                    }
+                    LiteralKind::FloatNumber { suffix } => {
+                        let known_name = suffix.and_then(|it| BuiltinFloat::from_suffix(&it));
+
+                        Literal::Float(Default::default(), known_name)
+                    }
+                    LiteralKind::ByteString => Literal::ByteString(Default::default()),
+                    LiteralKind::String => Literal::String(Default::default()),
+                    LiteralKind::Byte => Literal::Int(Default::default(), Some(BuiltinInt::U8)),
+                    LiteralKind::Bool => Literal::Bool(Default::default()),
+                    LiteralKind::Char => Literal::Char(Default::default()),
+                };
+                self.alloc_expr(Expr::Literal(lit), syntax_ptr)
+            }
+            ast::Expr::IndexExpr(e) => {
+                let base = self.collect_expr_opt(e.base());
+                let index = self.collect_expr_opt(e.index());
+                self.alloc_expr(Expr::Index { base, index }, syntax_ptr)
+            }
+
+            // FIXME implement HIR for these:
+            ast::Expr::Label(_e) => self.alloc_expr(Expr::Missing, syntax_ptr),
+            ast::Expr::RangeExpr(_e) => self.alloc_expr(Expr::Missing, syntax_ptr),
+            ast::Expr::MacroCall(e) => {
+                let ast_id = AstId::new(
+                    self.current_file_id,
+                    self.db.ast_id_map(self.current_file_id).ast_id(&e),
+                );
+
+                if let Some(path) = e.path().and_then(|path| self.parse_path(path)) {
+                    if let Some(def) = self.resolver.resolve_path_as_macro(self.db, &path) {
+                        let call_id = self.db.intern_macro(MacroCallLoc { def, ast_id });
+                        let file_id = call_id.as_file(MacroFileKind::Expr);
+                        if let Some(node) = self.db.parse_or_expand(file_id) {
+                            if let Some(expr) = ast::Expr::cast(node) {
+                                log::debug!("macro expansion {:#?}", expr.syntax());
+                                let old_file_id =
+                                    std::mem::replace(&mut self.current_file_id, file_id);
+                                let id = self.collect_expr(expr);
+                                self.current_file_id = old_file_id;
+                                return id;
+                            }
+                        }
+                    }
+                }
+                // FIXME: Instead of just dropping the error from expansion
+                // report it
+                self.alloc_expr(Expr::Missing, syntax_ptr)
+            }
+        }
+    }
+
+    fn collect_expr_opt(&mut self, expr: Option<ast::Expr>) -> ExprId {
+        if let Some(expr) = expr {
+            self.collect_expr(expr)
+        } else {
+            self.missing_expr()
+        }
+    }
+
+    fn collect_block(&mut self, expr: ast::BlockExpr) -> ExprId {
+        let syntax_node_ptr = AstPtr::new(&expr.clone().into());
+        let block = match expr.block() {
+            Some(block) => block,
+            None => return self.alloc_expr(Expr::Missing, syntax_node_ptr),
+        };
+        let statements = block
+            .statements()
+            .map(|s| match s {
+                ast::Stmt::LetStmt(stmt) => {
+                    let pat = self.collect_pat_opt(stmt.pat());
+                    let type_ref = stmt.ascribed_type().map(TypeRef::from_ast);
+                    let initializer = stmt.initializer().map(|e| self.collect_expr(e));
+                    Statement::Let { pat, type_ref, initializer }
+                }
+                ast::Stmt::ExprStmt(stmt) => Statement::Expr(self.collect_expr_opt(stmt.expr())),
+            })
+            .collect();
+        let tail = block.expr().map(|e| self.collect_expr(e));
+        self.alloc_expr(Expr::Block { statements, tail }, syntax_node_ptr)
+    }
+
+    fn collect_block_opt(&mut self, expr: Option<ast::BlockExpr>) -> ExprId {
+        if let Some(block) = expr {
+            self.collect_block(block)
+        } else {
+            self.missing_expr()
+        }
+    }
+
+    fn collect_pat(&mut self, pat: ast::Pat) -> PatId {
+        let pattern = match &pat {
+            ast::Pat::BindPat(bp) => {
+                let name = bp.name().map(|nr| nr.as_name()).unwrap_or_else(Name::missing);
+                let annotation = BindingAnnotation::new(bp.is_mutable(), bp.is_ref());
+                let subpat = bp.pat().map(|subpat| self.collect_pat(subpat));
+                Pat::Bind { name, mode: annotation, subpat }
+            }
+            ast::Pat::TupleStructPat(p) => {
+                let path = p.path().and_then(|path| self.parse_path(path));
+                let args = p.args().map(|p| self.collect_pat(p)).collect();
+                Pat::TupleStruct { path, args }
+            }
+            ast::Pat::RefPat(p) => {
+                let pat = self.collect_pat_opt(p.pat());
+                let mutability = Mutability::from_mutable(p.is_mut());
+                Pat::Ref { pat, mutability }
+            }
+            ast::Pat::PathPat(p) => {
+                let path = p.path().and_then(|path| self.parse_path(path));
+                path.map(Pat::Path).unwrap_or(Pat::Missing)
+            }
+            ast::Pat::TuplePat(p) => {
+                let args = p.args().map(|p| self.collect_pat(p)).collect();
+                Pat::Tuple(args)
+            }
+            ast::Pat::PlaceholderPat(_) => Pat::Wild,
+            ast::Pat::RecordPat(p) => {
+                let path = p.path().and_then(|path| self.parse_path(path));
+                let record_field_pat_list =
+                    p.record_field_pat_list().expect("every struct should have a field list");
+                let mut fields: Vec<_> = record_field_pat_list
+                    .bind_pats()
+                    .filter_map(|bind_pat| {
+                        let ast_pat =
+                            ast::Pat::cast(bind_pat.syntax().clone()).expect("bind pat is a pat");
+                        let pat = self.collect_pat(ast_pat);
+                        let name = bind_pat.name()?.as_name();
+                        Some(RecordFieldPat { name, pat })
+                    })
+                    .collect();
+                let iter = record_field_pat_list.record_field_pats().filter_map(|f| {
+                    let ast_pat = f.pat()?;
+                    let pat = self.collect_pat(ast_pat);
+                    let name = f.name()?.as_name();
+                    Some(RecordFieldPat { name, pat })
+                });
+                fields.extend(iter);
+
+                Pat::Record { path, args: fields }
+            }
+
+            // FIXME: implement
+            ast::Pat::DotDotPat(_) => Pat::Missing,
+            ast::Pat::BoxPat(_) => Pat::Missing,
+            ast::Pat::LiteralPat(_) => Pat::Missing,
+            ast::Pat::SlicePat(_) | ast::Pat::RangePat(_) => Pat::Missing,
+        };
+        let ptr = AstPtr::new(&pat);
+        self.alloc_pat(pattern, Either::A(ptr))
+    }
+
+    fn collect_pat_opt(&mut self, pat: Option<ast::Pat>) -> PatId {
+        if let Some(pat) = pat {
+            self.collect_pat(pat)
+        } else {
+            self.missing_pat()
+        }
+    }
+
+    fn parse_path(&mut self, path: ast::Path) -> Option<Path> {
+        let hygiene = Hygiene::new(self.db, self.current_file_id);
+        Path::from_src(path, &hygiene)
+    }
+}
+
+impl From<ast::BinOp> for BinaryOp {
+    fn from(ast_op: ast::BinOp) -> Self {
+        match ast_op {
+            ast::BinOp::BooleanOr => BinaryOp::LogicOp(LogicOp::Or),
+            ast::BinOp::BooleanAnd => BinaryOp::LogicOp(LogicOp::And),
+            ast::BinOp::EqualityTest => BinaryOp::CmpOp(CmpOp::Eq { negated: false }),
+            ast::BinOp::NegatedEqualityTest => BinaryOp::CmpOp(CmpOp::Eq { negated: true }),
+            ast::BinOp::LesserEqualTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Less, strict: false })
+            }
+            ast::BinOp::GreaterEqualTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Greater, strict: false })
+            }
+            ast::BinOp::LesserTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Less, strict: true })
+            }
+            ast::BinOp::GreaterTest => {
+                BinaryOp::CmpOp(CmpOp::Ord { ordering: Ordering::Greater, strict: true })
+            }
+            ast::BinOp::Addition => BinaryOp::ArithOp(ArithOp::Add),
+            ast::BinOp::Multiplication => BinaryOp::ArithOp(ArithOp::Mul),
+            ast::BinOp::Subtraction => BinaryOp::ArithOp(ArithOp::Sub),
+            ast::BinOp::Division => BinaryOp::ArithOp(ArithOp::Div),
+            ast::BinOp::Remainder => BinaryOp::ArithOp(ArithOp::Rem),
+            ast::BinOp::LeftShift => BinaryOp::ArithOp(ArithOp::Shl),
+            ast::BinOp::RightShift => BinaryOp::ArithOp(ArithOp::Shr),
+            ast::BinOp::BitwiseXor => BinaryOp::ArithOp(ArithOp::BitXor),
+            ast::BinOp::BitwiseOr => BinaryOp::ArithOp(ArithOp::BitOr),
+            ast::BinOp::BitwiseAnd => BinaryOp::ArithOp(ArithOp::BitAnd),
+            ast::BinOp::Assignment => BinaryOp::Assignment { op: None },
+            ast::BinOp::AddAssign => BinaryOp::Assignment { op: Some(ArithOp::Add) },
+            ast::BinOp::DivAssign => BinaryOp::Assignment { op: Some(ArithOp::Div) },
+            ast::BinOp::MulAssign => BinaryOp::Assignment { op: Some(ArithOp::Mul) },
+            ast::BinOp::RemAssign => BinaryOp::Assignment { op: Some(ArithOp::Rem) },
+            ast::BinOp::ShlAssign => BinaryOp::Assignment { op: Some(ArithOp::Shl) },
+            ast::BinOp::ShrAssign => BinaryOp::Assignment { op: Some(ArithOp::Shr) },
+            ast::BinOp::SubAssign => BinaryOp::Assignment { op: Some(ArithOp::Sub) },
+            ast::BinOp::BitOrAssign => BinaryOp::Assignment { op: Some(ArithOp::BitOr) },
+            ast::BinOp::BitAndAssign => BinaryOp::Assignment { op: Some(ArithOp::BitAnd) },
+            ast::BinOp::BitXorAssign => BinaryOp::Assignment { op: Some(ArithOp::BitXor) },
+        }
+    }
+}
diff --git a/crates/ra_hir_def/src/builtin_type.rs b/crates/ra_hir_def/src/builtin_type.rs
index 2ec0c83fe..5e8157144 100644
--- a/crates/ra_hir_def/src/builtin_type.rs
+++ b/crates/ra_hir_def/src/builtin_type.rs
@@ -30,12 +30,23 @@ pub enum FloatBitness {
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct BuiltinInt {
+    pub signedness: Signedness,
+    pub bitness: IntBitness,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct BuiltinFloat {
+    pub bitness: FloatBitness,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub enum BuiltinType {
     Char,
     Bool,
     Str,
-    Int { signedness: Signedness, bitness: IntBitness },
-    Float { bitness: FloatBitness },
+    Int(BuiltinInt),
+    Float(BuiltinFloat),
 }
 
 impl BuiltinType {
@@ -45,22 +56,22 @@ impl BuiltinType {
         (name::BOOL, BuiltinType::Bool),
         (name::STR,  BuiltinType::Str ),
 
-        (name::ISIZE, BuiltinType::Int { signedness: Signedness::Signed,   bitness: IntBitness::Xsize }),
-        (name::I8,    BuiltinType::Int { signedness: Signedness::Signed,   bitness: IntBitness::X8    }),
-        (name::I16,   BuiltinType::Int { signedness: Signedness::Signed,   bitness: IntBitness::X16   }),
-        (name::I32,   BuiltinType::Int { signedness: Signedness::Signed,   bitness: IntBitness::X32   }),
-        (name::I64,   BuiltinType::Int { signedness: Signedness::Signed,   bitness: IntBitness::X64   }),
-        (name::I128,  BuiltinType::Int { signedness: Signedness::Signed,   bitness: IntBitness::X128  }),
-
-        (name::USIZE, BuiltinType::Int { signedness: Signedness::Unsigned, bitness: IntBitness::Xsize }),
-        (name::U8,    BuiltinType::Int { signedness: Signedness::Unsigned, bitness: IntBitness::X8    }),
-        (name::U16,   BuiltinType::Int { signedness: Signedness::Unsigned, bitness: IntBitness::X16   }),
-        (name::U32,   BuiltinType::Int { signedness: Signedness::Unsigned, bitness: IntBitness::X32   }),
-        (name::U64,   BuiltinType::Int { signedness: Signedness::Unsigned, bitness: IntBitness::X64   }),
-        (name::U128,  BuiltinType::Int { signedness: Signedness::Unsigned, bitness: IntBitness::X128  }),
-
-        (name::F32, BuiltinType::Float { bitness: FloatBitness::X32 }),
-        (name::F64, BuiltinType::Float { bitness: FloatBitness::X64 }),
+        (name::ISIZE, BuiltinType::Int(BuiltinInt::ISIZE)),
+        (name::I8,    BuiltinType::Int(BuiltinInt::I8)),
+        (name::I16,   BuiltinType::Int(BuiltinInt::I16)),
+        (name::I32,   BuiltinType::Int(BuiltinInt::I32)),
+        (name::I64,   BuiltinType::Int(BuiltinInt::I64)),
+        (name::I128,  BuiltinType::Int(BuiltinInt::I128)),
+
+        (name::USIZE, BuiltinType::Int(BuiltinInt::USIZE)),
+        (name::U8,    BuiltinType::Int(BuiltinInt::U8)),
+        (name::U16,   BuiltinType::Int(BuiltinInt::U16)),
+        (name::U32,   BuiltinType::Int(BuiltinInt::U32)),
+        (name::U64,   BuiltinType::Int(BuiltinInt::U64)),
+        (name::U128,  BuiltinType::Int(BuiltinInt::U128)),
+
+        (name::F32, BuiltinType::Float(BuiltinFloat::F32)),
+        (name::F64, BuiltinType::Float(BuiltinFloat::F64)),
     ];
 }
 
@@ -70,7 +81,7 @@ impl fmt::Display for BuiltinType {
             BuiltinType::Char => "char",
             BuiltinType::Bool => "bool",
             BuiltinType::Str => "str",
-            BuiltinType::Int { signedness, bitness } => match (signedness, bitness) {
+            BuiltinType::Int(BuiltinInt { signedness, bitness }) => match (signedness, bitness) {
                 (Signedness::Signed, IntBitness::Xsize) => "isize",
                 (Signedness::Signed, IntBitness::X8) => "i8",
                 (Signedness::Signed, IntBitness::X16) => "i16",
@@ -85,7 +96,7 @@ impl fmt::Display for BuiltinType {
                 (Signedness::Unsigned, IntBitness::X64) => "u64",
                 (Signedness::Unsigned, IntBitness::X128) => "u128",
             },
-            BuiltinType::Float { bitness } => match bitness {
+            BuiltinType::Float(BuiltinFloat { bitness }) => match bitness {
                 FloatBitness::X32 => "f32",
                 FloatBitness::X64 => "f64",
             },
@@ -93,3 +104,57 @@ impl fmt::Display for BuiltinType {
         f.write_str(type_name)
     }
 }
+
+#[rustfmt::skip]
+impl BuiltinInt {
+    pub const ISIZE: BuiltinInt = BuiltinInt { signedness: Signedness::Signed, bitness: IntBitness::Xsize   };
+    pub const I8   : BuiltinInt = BuiltinInt { signedness: Signedness::Signed, bitness: IntBitness::X8      };
+    pub const I16  : BuiltinInt = BuiltinInt { signedness: Signedness::Signed, bitness: IntBitness::X16     };
+    pub const I32  : BuiltinInt = BuiltinInt { signedness: Signedness::Signed, bitness: IntBitness::X32     };
+    pub const I64  : BuiltinInt = BuiltinInt { signedness: Signedness::Signed, bitness: IntBitness::X64     };
+    pub const I128 : BuiltinInt = BuiltinInt { signedness: Signedness::Signed, bitness: IntBitness::X128    };
+
+    pub const USIZE: BuiltinInt = BuiltinInt { signedness: Signedness::Unsigned, bitness: IntBitness::Xsize };
+    pub const U8   : BuiltinInt = BuiltinInt { signedness: Signedness::Unsigned, bitness: IntBitness::X8    };
+    pub const U16  : BuiltinInt = BuiltinInt { signedness: Signedness::Unsigned, bitness: IntBitness::X16   };
+    pub const U32  : BuiltinInt = BuiltinInt { signedness: Signedness::Unsigned, bitness: IntBitness::X32   };
+    pub const U64  : BuiltinInt = BuiltinInt { signedness: Signedness::Unsigned, bitness: IntBitness::X64   };
+    pub const U128 : BuiltinInt = BuiltinInt { signedness: Signedness::Unsigned, bitness: IntBitness::X128  };
+
+
+    pub fn from_suffix(suffix: &str) -> Option<BuiltinInt> {
+        let res = match suffix {
+            "isize" => Self::ISIZE,
+            "i8"    => Self::I8,
+            "i16"   => Self::I16,
+            "i32"   => Self::I32,
+            "i64"   => Self::I64,
+            "i128"  => Self::I128,
+
+            "usize" => Self::USIZE,
+            "u8"    => Self::U8,
+            "u16"   => Self::U16,
+            "u32"   => Self::U32,
+            "u64"   => Self::U64,
+            "u128"  => Self::U128,
+
+            _ => return None,
+        };
+        Some(res)
+    }
+}
+
+#[rustfmt::skip]
+impl BuiltinFloat {
+    pub const F32: BuiltinFloat = BuiltinFloat { bitness: FloatBitness::X32 };
+    pub const F64: BuiltinFloat = BuiltinFloat { bitness: FloatBitness::X64 };
+
+    pub fn from_suffix(suffix: &str) -> Option<BuiltinFloat> {
+        let res = match suffix {
+            "f32" => BuiltinFloat::F32,
+            "f64" => BuiltinFloat::F64,
+            _ => return None,
+        };
+        Some(res)
+    }
+}
diff --git a/crates/ra_hir_def/src/expr.rs b/crates/ra_hir_def/src/expr.rs
new file mode 100644
index 000000000..04c1d8f69
--- /dev/null
+++ b/crates/ra_hir_def/src/expr.rs
@@ -0,0 +1,421 @@
+//! This module describes hir-level representation of expressions.
+//!
+//! This representaion is:
+//!
+//! 1. Identity-based. Each expression has an `id`, so we can distinguish
+//!    between different `1` in `1 + 1`.
+//! 2. Independent of syntax. Though syntactic provenance information can be
+//!    attached separately via id-based side map.
+//! 3. Unresolved. Paths are stored as sequences of names, and not as defs the
+//!    names refer to.
+//! 4. Desugared. There's no `if let`.
+//!
+//! See also a neighboring `body` module.
+
+use hir_expand::name::Name;
+use ra_arena::{impl_arena_id, RawId};
+
+use crate::{
+    builtin_type::{BuiltinFloat, BuiltinInt},
+    path::{GenericArgs, Path},
+    type_ref::{Mutability, TypeRef},
+};
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ExprId(RawId);
+impl_arena_id!(ExprId);
+
+impl ExprId {
+    pub fn dummy() -> ExprId {
+        ExprId((!0).into())
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct PatId(RawId);
+impl_arena_id!(PatId);
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Literal {
+    String(String),
+    ByteString(Vec<u8>),
+    Char(char),
+    Bool(bool),
+    Int(u64, Option<BuiltinInt>),
+    Float(u64, Option<BuiltinFloat>), // FIXME: f64 is not Eq
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Expr {
+    /// This is produced if syntax tree does not have a required expression piece.
+    Missing,
+    Path(Path),
+    If {
+        condition: ExprId,
+        then_branch: ExprId,
+        else_branch: Option<ExprId>,
+    },
+    Block {
+        statements: Vec<Statement>,
+        tail: Option<ExprId>,
+    },
+    Loop {
+        body: ExprId,
+    },
+    While {
+        condition: ExprId,
+        body: ExprId,
+    },
+    For {
+        iterable: ExprId,
+        pat: PatId,
+        body: ExprId,
+    },
+    Call {
+        callee: ExprId,
+        args: Vec<ExprId>,
+    },
+    MethodCall {
+        receiver: ExprId,
+        method_name: Name,
+        args: Vec<ExprId>,
+        generic_args: Option<GenericArgs>,
+    },
+    Match {
+        expr: ExprId,
+        arms: Vec<MatchArm>,
+    },
+    Continue,
+    Break {
+        expr: Option<ExprId>,
+    },
+    Return {
+        expr: Option<ExprId>,
+    },
+    RecordLit {
+        path: Option<Path>,
+        fields: Vec<RecordLitField>,
+        spread: Option<ExprId>,
+    },
+    Field {
+        expr: ExprId,
+        name: Name,
+    },
+    Await {
+        expr: ExprId,
+    },
+    Try {
+        expr: ExprId,
+    },
+    TryBlock {
+        body: ExprId,
+    },
+    Cast {
+        expr: ExprId,
+        type_ref: TypeRef,
+    },
+    Ref {
+        expr: ExprId,
+        mutability: Mutability,
+    },
+    Box {
+        expr: ExprId,
+    },
+    UnaryOp {
+        expr: ExprId,
+        op: UnaryOp,
+    },
+    BinaryOp {
+        lhs: ExprId,
+        rhs: ExprId,
+        op: Option<BinaryOp>,
+    },
+    Index {
+        base: ExprId,
+        index: ExprId,
+    },
+    Lambda {
+        args: Vec<PatId>,
+        arg_types: Vec<Option<TypeRef>>,
+        body: ExprId,
+    },
+    Tuple {
+        exprs: Vec<ExprId>,
+    },
+    Array(Array),
+    Literal(Literal),
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum BinaryOp {
+    LogicOp(LogicOp),
+    ArithOp(ArithOp),
+    CmpOp(CmpOp),
+    Assignment { op: Option<ArithOp> },
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum LogicOp {
+    And,
+    Or,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum CmpOp {
+    Eq { negated: bool },
+    Ord { ordering: Ordering, strict: bool },
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum Ordering {
+    Less,
+    Greater,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum ArithOp {
+    Add,
+    Mul,
+    Sub,
+    Div,
+    Rem,
+    Shl,
+    Shr,
+    BitXor,
+    BitOr,
+    BitAnd,
+}
+
+pub use ra_syntax::ast::PrefixOp as UnaryOp;
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Array {
+    ElementList(Vec<ExprId>),
+    Repeat { initializer: ExprId, repeat: ExprId },
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct MatchArm {
+    pub pats: Vec<PatId>,
+    pub guard: Option<ExprId>,
+    pub expr: ExprId,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct RecordLitField {
+    pub name: Name,
+    pub expr: ExprId,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Statement {
+    Let { pat: PatId, type_ref: Option<TypeRef>, initializer: Option<ExprId> },
+    Expr(ExprId),
+}
+
+impl Expr {
+    pub fn walk_child_exprs(&self, mut f: impl FnMut(ExprId)) {
+        match self {
+            Expr::Missing => {}
+            Expr::Path(_) => {}
+            Expr::If { condition, then_branch, else_branch } => {
+                f(*condition);
+                f(*then_branch);
+                if let Some(else_branch) = else_branch {
+                    f(*else_branch);
+                }
+            }
+            Expr::Block { statements, tail } => {
+                for stmt in statements {
+                    match stmt {
+                        Statement::Let { initializer, .. } => {
+                            if let Some(expr) = initializer {
+                                f(*expr);
+                            }
+                        }
+                        Statement::Expr(e) => f(*e),
+                    }
+                }
+                if let Some(expr) = tail {
+                    f(*expr);
+                }
+            }
+            Expr::TryBlock { body } => f(*body),
+            Expr::Loop { body } => f(*body),
+            Expr::While { condition, body } => {
+                f(*condition);
+                f(*body);
+            }
+            Expr::For { iterable, body, .. } => {
+                f(*iterable);
+                f(*body);
+            }
+            Expr::Call { callee, args } => {
+                f(*callee);
+                for arg in args {
+                    f(*arg);
+                }
+            }
+            Expr::MethodCall { receiver, args, .. } => {
+                f(*receiver);
+                for arg in args {
+                    f(*arg);
+                }
+            }
+            Expr::Match { expr, arms } => {
+                f(*expr);
+                for arm in arms {
+                    f(arm.expr);
+                }
+            }
+            Expr::Continue => {}
+            Expr::Break { expr } | Expr::Return { expr } => {
+                if let Some(expr) = expr {
+                    f(*expr);
+                }
+            }
+            Expr::RecordLit { fields, spread, .. } => {
+                for field in fields {
+                    f(field.expr);
+                }
+                if let Some(expr) = spread {
+                    f(*expr);
+                }
+            }
+            Expr::Lambda { body, .. } => {
+                f(*body);
+            }
+            Expr::BinaryOp { lhs, rhs, .. } => {
+                f(*lhs);
+                f(*rhs);
+            }
+            Expr::Index { base, index } => {
+                f(*base);
+                f(*index);
+            }
+            Expr::Field { expr, .. }
+            | Expr::Await { expr }
+            | Expr::Try { expr }
+            | Expr::Cast { expr, .. }
+            | Expr::Ref { expr, .. }
+            | Expr::UnaryOp { expr, .. }
+            | Expr::Box { expr } => {
+                f(*expr);
+            }
+            Expr::Tuple { exprs } => {
+                for expr in exprs {
+                    f(*expr);
+                }
+            }
+            Expr::Array(a) => match a {
+                Array::ElementList(exprs) => {
+                    for expr in exprs {
+                        f(*expr);
+                    }
+                }
+                Array::Repeat { initializer, repeat } => {
+                    f(*initializer);
+                    f(*repeat)
+                }
+            },
+            Expr::Literal(_) => {}
+        }
+    }
+}
+
+/// Explicit binding annotations given in the HIR for a binding. Note
+/// that this is not the final binding *mode* that we infer after type
+/// inference.
+#[derive(Clone, PartialEq, Eq, Debug, Copy)]
+pub enum BindingAnnotation {
+    /// No binding annotation given: this means that the final binding mode
+    /// will depend on whether we have skipped through a `&` reference
+    /// when matching. For example, the `x` in `Some(x)` will have binding
+    /// mode `None`; if you do `let Some(x) = &Some(22)`, it will
+    /// ultimately be inferred to be by-reference.
+    Unannotated,
+
+    /// Annotated with `mut x` -- could be either ref or not, similar to `None`.
+    Mutable,
+
+    /// Annotated as `ref`, like `ref x`
+    Ref,
+
+    /// Annotated as `ref mut x`.
+    RefMut,
+}
+
+impl BindingAnnotation {
+    pub fn new(is_mutable: bool, is_ref: bool) -> Self {
+        match (is_mutable, is_ref) {
+            (true, true) => BindingAnnotation::RefMut,
+            (false, true) => BindingAnnotation::Ref,
+            (true, false) => BindingAnnotation::Mutable,
+            (false, false) => BindingAnnotation::Unannotated,
+        }
+    }
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct RecordFieldPat {
+    pub name: Name,
+    pub pat: PatId,
+}
+
+/// Close relative to rustc's hir::PatKind
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Pat {
+    Missing,
+    Wild,
+    Tuple(Vec<PatId>),
+    Record {
+        path: Option<Path>,
+        args: Vec<RecordFieldPat>,
+        // FIXME: 'ellipsis' option
+    },
+    Range {
+        start: ExprId,
+        end: ExprId,
+    },
+    Slice {
+        prefix: Vec<PatId>,
+        rest: Option<PatId>,
+        suffix: Vec<PatId>,
+    },
+    Path(Path),
+    Lit(ExprId),
+    Bind {
+        mode: BindingAnnotation,
+        name: Name,
+        subpat: Option<PatId>,
+    },
+    TupleStruct {
+        path: Option<Path>,
+        args: Vec<PatId>,
+    },
+    Ref {
+        pat: PatId,
+        mutability: Mutability,
+    },
+}
+
+impl Pat {
+    pub fn walk_child_pats(&self, mut f: impl FnMut(PatId)) {
+        match self {
+            Pat::Range { .. } | Pat::Lit(..) | Pat::Path(..) | Pat::Wild | Pat::Missing => {}
+            Pat::Bind { subpat, .. } => {
+                subpat.iter().copied().for_each(f);
+            }
+            Pat::Tuple(args) | Pat::TupleStruct { args, .. } => {
+                args.iter().copied().for_each(f);
+            }
+            Pat::Ref { pat, .. } => f(*pat),
+            Pat::Slice { prefix, rest, suffix } => {
+                let total_iter = prefix.iter().chain(rest.iter()).chain(suffix.iter());
+                total_iter.copied().for_each(f);
+            }
+            Pat::Record { args, .. } => {
+                args.iter().map(|f| f.pat).for_each(f);
+            }
+        }
+    }
+}
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index 239317efe..4a758bb83 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -14,6 +14,8 @@ pub mod type_ref;
 pub mod builtin_type;
 pub mod adt;
 pub mod diagnostics;
+pub mod expr;
+pub mod body;
 
 #[cfg(test)]
 mod test_db;