// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

// Lowers the AST to the HIR.
//
// Since the AST and HIR are fairly similar, this is mostly a simple procedure,
// much like a fold. Where lowering involves a bit more work things get more
// interesting and there are some invariants you should know about. These mostly
// concern spans and ids.
//
// Spans are assigned to AST nodes during parsing and then are modified during
// expansion to indicate the origin of a node and the process it went through
// being expanded. Ids are assigned to AST nodes just before lowering.
//
// For the simpler lowering steps, ids and spans should be preserved. Unlike
// expansion we do not preserve the process of lowering in the spans, so spans
// should not be modified here. When creating a new node (as opposed to
// 'folding' an existing one), then you create a new id using `next_id()`.
//
// You must ensure that ids are unique. That means that you should only use the
// id from an AST node in a single HIR node (you can assume that AST node ids
// are unique). Every new node must have a unique id. Avoid cloning HIR nodes.
// If you do, you must then set the new node's id to a fresh one.
//
// Spans are used for error messages and for tools to map semantics back to
// source code. It is therefore not as important with spans as ids to be strict
// about use (you can't break the compiler by screwing up a span). Obviously, a
// HIR node can only have a single span. But multiple nodes can have the same
// span and spans don't need to be kept in order, etc. Where code is preserved
// by lowering, it should have the same span as in the AST. Where HIR nodes are
// new it is probably best to give a span for the whole AST node being lowered.
// All nodes should have real spans, don't use dummy spans. Tools are likely to
// get confused if the spans from leaf AST nodes occur in multiple places
// in the HIR, especially for multiple identifiers.

use hir;
use hir::map::Definitions;
use hir::map::definitions::DefPathData;
use hir::def_id::{DefIndex, DefId};
use hir::def::{Def, PathResolution};
use session::Session;

use std::collections::BTreeMap;
use std::iter;
use syntax::ast::*;
use syntax::errors;
use syntax::ptr::P;
use syntax::codemap::{respan, Spanned};
use syntax::parse::token;
use syntax::std_inject;
use syntax::visit::{self, Visitor};
use syntax_pos::Span;

pub struct LoweringContext<'a> {
    crate_root: Option<&'static str>,
    // Use to assign ids to hir nodes that do not directly correspond to an ast node
    sess: Option<&'a Session>,
    // As we walk the AST we must keep track of the current 'parent' def id (in
    // the form of a DefIndex) so that if we create a new node which introduces
    // a definition, then we can properly create the def id.
    parent_def: Option<DefIndex>,
    resolver: &'a mut Resolver,
}

pub trait Resolver {
    // Resolve a global hir path generated by the lowerer when expanding `for`, `if let`, etc.
    fn resolve_generated_global_path(&mut self, path: &hir::Path, is_value: bool) -> Def;

    // Obtain the resolution for a node id
    fn get_resolution(&mut self, id: NodeId) -> Option<PathResolution>;

    // Record the resolution of a path or binding generated by the lowerer when expanding.
    fn record_resolution(&mut self, id: NodeId, def: Def);

    // We must keep the set of definitions up to date as we add nodes that weren't in the AST.
    // This should only return `None` during testing.
    fn definitions(&mut self) -> Option<&mut Definitions>;
}

pub struct DummyResolver;
impl Resolver for DummyResolver {
    fn resolve_generated_global_path(&mut self, _path: &hir::Path, _is_value: bool) -> Def {
        Def::Err
    }
    fn get_resolution(&mut self, _id: NodeId) -> Option<PathResolution> {
        None
    }
    fn record_resolution(&mut self, _id: NodeId, _def: Def) {}
    fn definitions(&mut self) -> Option<&mut Definitions> {
        None
    }
}

pub fn lower_crate(sess: &Session,
                   krate: &Crate,
                   resolver: &mut Resolver)
                   -> hir::Crate {
    // We're constructing the HIR here; we don't care what we will
    // read, since we haven't even constructed the *input* to
    // incr. comp. yet.
    let _ignore = sess.dep_graph.in_ignore();

    LoweringContext {
        crate_root: if std_inject::no_core(krate) {
            None
        } else if std_inject::no_std(krate) {
            Some("core")
        } else {
            Some("std")
        },
        sess: Some(sess),
        parent_def: None,
        resolver: resolver,
    }.lower_crate(krate)
}

impl<'a> LoweringContext<'a> {
    pub fn testing_context(resolver: &'a mut Resolver) -> Self {
        LoweringContext {
            crate_root: None,
            sess: None,
            parent_def: None,
            resolver: resolver,
        }
    }

    fn lower_crate(&mut self, c: &Crate) -> hir::Crate {
        struct ItemLowerer<'lcx, 'interner: 'lcx> {
            items: BTreeMap<NodeId, hir::Item>,
            lctx: &'lcx mut LoweringContext<'interner>,
        }

        impl<'lcx, 'interner> Visitor for ItemLowerer<'lcx, 'interner> {
            fn visit_item(&mut self, item: &Item) {
                self.items.insert(item.id, self.lctx.lower_item(item));
                visit::walk_item(self, item);
            }
        }

        let items = {
            let mut item_lowerer = ItemLowerer { items: BTreeMap::new(), lctx: self };
            visit::walk_crate(&mut item_lowerer, c);
            item_lowerer.items
        };

        hir::Crate {
            module: self.lower_mod(&c.module),
            attrs: self.lower_attrs(&c.attrs),
            config: c.config.clone().into(),
            span: c.span,
            exported_macros: c.exported_macros.iter().map(|m| self.lower_macro_def(m)).collect(),
            items: items,
        }
    }

    fn next_id(&self) -> NodeId {
        self.sess.map(Session::next_node_id).unwrap_or(0)
    }

    fn diagnostic(&self) -> &errors::Handler {
        self.sess.map(Session::diagnostic)
                 .unwrap_or_else(|| panic!("this lowerer cannot emit diagnostics"))
    }

    fn str_to_ident(&self, s: &'static str) -> Name {
        token::gensym(s)
    }

    fn with_parent_def<T, F>(&mut self, parent_id: NodeId, f: F) -> T
        where F: FnOnce(&mut LoweringContext) -> T
    {
        let old_def = self.parent_def;
        self.parent_def = match self.resolver.definitions() {
            Some(defs) => Some(defs.opt_def_index(parent_id).unwrap()),
            None => old_def,
        };

        let result = f(self);

        self.parent_def = old_def;
        result
    }

    fn lower_opt_sp_ident(&mut self, o_id: Option<Spanned<Ident>>) -> Option<Spanned<Name>> {
        o_id.map(|sp_ident| respan(sp_ident.span, sp_ident.node.name))
    }

    fn lower_attrs(&mut self, attrs: &Vec<Attribute>) -> hir::HirVec<Attribute> {
        attrs.clone().into()
    }

    fn lower_view_path(&mut self, view_path: &ViewPath) -> P<hir::ViewPath> {
        P(Spanned {
            node: match view_path.node {
                ViewPathSimple(ident, ref path) => {
                    hir::ViewPathSimple(ident.name, self.lower_path(path))
                }
                ViewPathGlob(ref path) => {
                    hir::ViewPathGlob(self.lower_path(path))
                }
                ViewPathList(ref path, ref path_list_idents) => {
                    hir::ViewPathList(self.lower_path(path),
                                      path_list_idents.iter()
                                                      .map(|item| self.lower_path_list_item(item))
                                                      .collect())
                }
            },
            span: view_path.span,
        })
    }

    fn lower_path_list_item(&mut self, path_list_ident: &PathListItem) -> hir::PathListItem {
        Spanned {
            node: match path_list_ident.node {
                PathListItemKind::Ident { id, name, rename } => hir::PathListIdent {
                    id: id,
                    name: name.name,
                    rename: rename.map(|x| x.name),
                },
                PathListItemKind::Mod { id, rename } => hir::PathListMod {
                    id: id,
                    rename: rename.map(|x| x.name),
                },
            },
            span: path_list_ident.span,
        }
    }

    fn lower_arm(&mut self, arm: &Arm) -> hir::Arm {
        hir::Arm {
            attrs: self.lower_attrs(&arm.attrs),
            pats: arm.pats.iter().map(|x| self.lower_pat(x)).collect(),
            guard: arm.guard.as_ref().map(|ref x| self.lower_expr(x)),
            body: self.lower_expr(&arm.body),
        }
    }

    fn lower_ty_binding(&mut self, b: &TypeBinding) -> hir::TypeBinding {
        hir::TypeBinding {
            id: b.id,
            name: b.ident.name,
            ty: self.lower_ty(&b.ty),
            span: b.span,
        }
    }

    fn lower_ty(&mut self, t: &Ty) -> P<hir::Ty> {
        use syntax::ast::TyKind::*;
        P(hir::Ty {
            id: t.id,
            node: match t.node {
                Infer | ImplicitSelf => hir::TyInfer,
                Vec(ref ty) => hir::TyVec(self.lower_ty(ty)),
                Ptr(ref mt) => hir::TyPtr(self.lower_mt(mt)),
                Rptr(ref region, ref mt) => {
                    hir::TyRptr(self.lower_opt_lifetime(region), self.lower_mt(mt))
                }
                BareFn(ref f) => {
                    hir::TyBareFn(P(hir::BareFnTy {
                        lifetimes: self.lower_lifetime_defs(&f.lifetimes),
                        unsafety: self.lower_unsafety(f.unsafety),
                        abi: f.abi,
                        decl: self.lower_fn_decl(&f.decl),
                    }))
                }
                Tup(ref tys) => hir::TyTup(tys.iter().map(|ty| self.lower_ty(ty)).collect()),
                Paren(ref ty) => {
                    return self.lower_ty(ty);
                }
                Path(ref qself, ref path) => {
                    let qself = qself.as_ref().map(|&QSelf { ref ty, position }| {
                        hir::QSelf {
                            ty: self.lower_ty(ty),
                            position: position,
                        }
                    });
                    hir::TyPath(qself, self.lower_path(path))
                }
                ObjectSum(ref ty, ref bounds) => {
                    hir::TyObjectSum(self.lower_ty(ty), self.lower_bounds(bounds))
                }
                FixedLengthVec(ref ty, ref e) => {
                    hir::TyFixedLengthVec(self.lower_ty(ty), self.lower_expr(e))
                }
                Typeof(ref expr) => {
                    hir::TyTypeof(self.lower_expr(expr))
                }
                PolyTraitRef(ref bounds) => {
                    let bounds = bounds.iter().map(|b| self.lower_ty_param_bound(b)).collect();
                    hir::TyPolyTraitRef(bounds)
                }
                Mac(_) => panic!("TyMac should have been expanded by now."),
            },
            span: t.span,
        })
    }

    fn lower_foreign_mod(&mut self, fm: &ForeignMod) -> hir::ForeignMod {
        hir::ForeignMod {
            abi: fm.abi,
            items: fm.items.iter().map(|x| self.lower_foreign_item(x)).collect(),
        }
    }

    fn lower_variant(&mut self, v: &Variant) -> hir::Variant {
        Spanned {
            node: hir::Variant_ {
                name: v.node.name.name,
                attrs: self.lower_attrs(&v.node.attrs),
                data: self.lower_variant_data(&v.node.data),
                disr_expr: v.node.disr_expr.as_ref().map(|e| self.lower_expr(e)),
            },
            span: v.span,
        }
    }

    fn lower_path(&mut self, p: &Path) -> hir::Path {
        hir::Path {
            global: p.global,
            segments: p.segments
                       .iter()
                       .map(|&PathSegment { identifier, ref parameters }| {
                           hir::PathSegment {
                               name: identifier.name,
                               parameters: self.lower_path_parameters(parameters),
                           }
                       })
                       .collect(),
            span: p.span,
        }
    }

    fn lower_path_parameters(&mut self, path_parameters: &PathParameters) -> hir::PathParameters {
        match *path_parameters {
            PathParameters::AngleBracketed(ref data) =>
                hir::AngleBracketedParameters(self.lower_angle_bracketed_parameter_data(data)),
            PathParameters::Parenthesized(ref data) =>
                hir::ParenthesizedParameters(self.lower_parenthesized_parameter_data(data)),
        }
    }

    fn lower_angle_bracketed_parameter_data(&mut self,
                                            data: &AngleBracketedParameterData)
                                            -> hir::AngleBracketedParameterData {
        let &AngleBracketedParameterData { ref lifetimes, ref types, ref bindings } = data;
        hir::AngleBracketedParameterData {
            lifetimes: self.lower_lifetimes(lifetimes),
            types: types.iter().map(|ty| self.lower_ty(ty)).collect(),
            bindings: bindings.iter().map(|b| self.lower_ty_binding(b)).collect(),
        }
    }

    fn lower_parenthesized_parameter_data(&mut self,
                                          data: &ParenthesizedParameterData)
                                          -> hir::ParenthesizedParameterData {
        let &ParenthesizedParameterData { ref inputs, ref output, span } = data;
        hir::ParenthesizedParameterData {
            inputs: inputs.iter().map(|ty| self.lower_ty(ty)).collect(),
            output: output.as_ref().map(|ty| self.lower_ty(ty)),
            span: span,
        }
    }

    fn lower_local(&mut self, l: &Local) -> P<hir::Local> {
        P(hir::Local {
            id: l.id,
            ty: l.ty.as_ref().map(|t| self.lower_ty(t)),
            pat: self.lower_pat(&l.pat),
            init: l.init.as_ref().map(|e| self.lower_expr(e)),
            span: l.span,
            attrs: l.attrs.clone(),
        })
    }

    fn lower_mutability(&mut self, m: Mutability) -> hir::Mutability {
        match m {
            Mutability::Mutable => hir::MutMutable,
            Mutability::Immutable => hir::MutImmutable,
        }
    }

    fn lower_arg(&mut self, arg: &Arg) -> hir::Arg {
        hir::Arg {
            id: arg.id,
            pat: self.lower_pat(&arg.pat),
            ty: self.lower_ty(&arg.ty),
        }
    }

    fn lower_fn_decl(&mut self, decl: &FnDecl) -> P<hir::FnDecl> {
        P(hir::FnDecl {
            inputs: decl.inputs.iter().map(|x| self.lower_arg(x)).collect(),
            output: match decl.output {
                FunctionRetTy::Ty(ref ty) => hir::Return(self.lower_ty(ty)),
                FunctionRetTy::Default(span) => hir::DefaultReturn(span),
                FunctionRetTy::None(span) => hir::NoReturn(span),
            },
            variadic: decl.variadic,
        })
    }

    fn lower_ty_param_bound(&mut self, tpb: &TyParamBound) -> hir::TyParamBound {
        match *tpb {
            TraitTyParamBound(ref ty, modifier) => {
                hir::TraitTyParamBound(self.lower_poly_trait_ref(ty),
                                       self.lower_trait_bound_modifier(modifier))
            }
            RegionTyParamBound(ref lifetime) => {
                hir::RegionTyParamBound(self.lower_lifetime(lifetime))
            }
        }
    }

    fn lower_ty_param(&mut self, tp: &TyParam) -> hir::TyParam {
        hir::TyParam {
            id: tp.id,
            name: tp.ident.name,
            bounds: self.lower_bounds(&tp.bounds),
            default: tp.default.as_ref().map(|x| self.lower_ty(x)),
            span: tp.span,
        }
    }

    fn lower_ty_params(&mut self, tps: &P<[TyParam]>) -> hir::HirVec<hir::TyParam> {
        tps.iter().map(|tp| self.lower_ty_param(tp)).collect()
    }

    fn lower_lifetime(&mut self, l: &Lifetime) -> hir::Lifetime {
        hir::Lifetime {
            id: l.id,
            name: l.name,
            span: l.span,
        }
    }

    fn lower_lifetime_def(&mut self, l: &LifetimeDef) -> hir::LifetimeDef {
        hir::LifetimeDef {
            lifetime: self.lower_lifetime(&l.lifetime),
            bounds: self.lower_lifetimes(&l.bounds),
        }
    }

    fn lower_lifetimes(&mut self, lts: &Vec<Lifetime>) -> hir::HirVec<hir::Lifetime> {
        lts.iter().map(|l| self.lower_lifetime(l)).collect()
    }

    fn lower_lifetime_defs(&mut self, lts: &Vec<LifetimeDef>) -> hir::HirVec<hir::LifetimeDef> {
        lts.iter().map(|l| self.lower_lifetime_def(l)).collect()
    }

    fn lower_opt_lifetime(&mut self, o_lt: &Option<Lifetime>) -> Option<hir::Lifetime> {
        o_lt.as_ref().map(|lt| self.lower_lifetime(lt))
    }

    fn lower_generics(&mut self, g: &Generics) -> hir::Generics {
        hir::Generics {
            ty_params: self.lower_ty_params(&g.ty_params),
            lifetimes: self.lower_lifetime_defs(&g.lifetimes),
            where_clause: self.lower_where_clause(&g.where_clause),
        }
    }

    fn lower_where_clause(&mut self, wc: &WhereClause) -> hir::WhereClause {
        hir::WhereClause {
            id: wc.id,
            predicates: wc.predicates
                          .iter()
                          .map(|predicate| self.lower_where_predicate(predicate))
                          .collect(),
        }
    }

    fn lower_where_predicate(&mut self, pred: &WherePredicate) -> hir::WherePredicate {
        match *pred {
            WherePredicate::BoundPredicate(WhereBoundPredicate{ ref bound_lifetimes,
                                                                ref bounded_ty,
                                                                ref bounds,
                                                                span}) => {
                hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
                    bound_lifetimes: self.lower_lifetime_defs(bound_lifetimes),
                    bounded_ty: self.lower_ty(bounded_ty),
                    bounds: bounds.iter().map(|x| self.lower_ty_param_bound(x)).collect(),
                    span: span,
                })
            }
            WherePredicate::RegionPredicate(WhereRegionPredicate{ ref lifetime,
                                                                  ref bounds,
                                                                  span}) => {
                hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
                    span: span,
                    lifetime: self.lower_lifetime(lifetime),
                    bounds: bounds.iter().map(|bound| self.lower_lifetime(bound)).collect(),
                })
            }
            WherePredicate::EqPredicate(WhereEqPredicate{ id,
                                                          ref path,
                                                          ref ty,
                                                          span}) => {
                hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
                    id: id,
                    path: self.lower_path(path),
                    ty: self.lower_ty(ty),
                    span: span,
                })
            }
        }
    }

    fn lower_variant_data(&mut self, vdata: &VariantData) -> hir::VariantData {
        match *vdata {
            VariantData::Struct(ref fields, id) => {
                hir::VariantData::Struct(fields.iter()
                                               .enumerate()
                                               .map(|f| self.lower_struct_field(f))
                                               .collect(),
                                         id)
            }
            VariantData::Tuple(ref fields, id) => {
                hir::VariantData::Tuple(fields.iter()
                                              .enumerate()
                                              .map(|f| self.lower_struct_field(f))
                                              .collect(),
                                        id)
            }
            VariantData::Unit(id) => hir::VariantData::Unit(id),
        }
    }

    fn lower_trait_ref(&mut self, p: &TraitRef) -> hir::TraitRef {
        hir::TraitRef {
            path: self.lower_path(&p.path),
            ref_id: p.ref_id,
        }
    }

    fn lower_poly_trait_ref(&mut self, p: &PolyTraitRef) -> hir::PolyTraitRef {
        hir::PolyTraitRef {
            bound_lifetimes: self.lower_lifetime_defs(&p.bound_lifetimes),
            trait_ref: self.lower_trait_ref(&p.trait_ref),
            span: p.span,
        }
    }

    fn lower_struct_field(&mut self, (index, f): (usize, &StructField)) -> hir::StructField {
        hir::StructField {
            span: f.span,
            id: f.id,
            name: f.ident.map(|ident| ident.name).unwrap_or(token::intern(&index.to_string())),
            vis: self.lower_visibility(&f.vis),
            ty: self.lower_ty(&f.ty),
            attrs: self.lower_attrs(&f.attrs),
        }
    }

    fn lower_field(&mut self, f: &Field) -> hir::Field {
        hir::Field {
            name: respan(f.ident.span, f.ident.node.name),
            expr: self.lower_expr(&f.expr),
            span: f.span,
        }
    }

    fn lower_mt(&mut self, mt: &MutTy) -> hir::MutTy {
        hir::MutTy {
            ty: self.lower_ty(&mt.ty),
            mutbl: self.lower_mutability(mt.mutbl),
        }
    }

    fn lower_bounds(&mut self, bounds: &TyParamBounds) -> hir::TyParamBounds {
        bounds.iter().map(|bound| self.lower_ty_param_bound(bound)).collect()
    }

    fn lower_block(&mut self, b: &Block) -> P<hir::Block> {
        let mut stmts = Vec::new();
        let mut expr = None;

        if let Some((last, rest)) = b.stmts.split_last() {
            stmts = rest.iter().map(|s| self.lower_stmt(s)).collect::<Vec<_>>();
            let last = self.lower_stmt(last);
            if let hir::StmtExpr(e, _) = last.node {
                expr = Some(e);
            } else {
                stmts.push(last);
            }
        }

        P(hir::Block {
            id: b.id,
            stmts: stmts.into(),
            expr: expr,
            rules: self.lower_block_check_mode(&b.rules),
            span: b.span,
        })
    }

    fn lower_item_kind(&mut self, i: &ItemKind) -> hir::Item_ {
        match *i {
            ItemKind::ExternCrate(string) => hir::ItemExternCrate(string),
            ItemKind::Use(ref view_path) => {
                hir::ItemUse(self.lower_view_path(view_path))
            }
            ItemKind::Static(ref t, m, ref e) => {
                hir::ItemStatic(self.lower_ty(t),
                                self.lower_mutability(m),
                                self.lower_expr(e))
            }
            ItemKind::Const(ref t, ref e) => {
                hir::ItemConst(self.lower_ty(t), self.lower_expr(e))
            }
            ItemKind::Fn(ref decl, unsafety, constness, abi, ref generics, ref body) => {
                hir::ItemFn(self.lower_fn_decl(decl),
                            self.lower_unsafety(unsafety),
                            self.lower_constness(constness),
                            abi,
                            self.lower_generics(generics),
                            self.lower_block(body))
            }
            ItemKind::Mod(ref m) => hir::ItemMod(self.lower_mod(m)),
            ItemKind::ForeignMod(ref nm) => hir::ItemForeignMod(self.lower_foreign_mod(nm)),
            ItemKind::Ty(ref t, ref generics) => {
                hir::ItemTy(self.lower_ty(t), self.lower_generics(generics))
            }
            ItemKind::Enum(ref enum_definition, ref generics) => {
                hir::ItemEnum(hir::EnumDef {
                                  variants: enum_definition.variants
                                                           .iter()
                                                           .map(|x| self.lower_variant(x))
                                                           .collect(),
                              },
                              self.lower_generics(generics))
            }
            ItemKind::Struct(ref struct_def, ref generics) => {
                let struct_def = self.lower_variant_data(struct_def);
                hir::ItemStruct(struct_def, self.lower_generics(generics))
            }
            ItemKind::DefaultImpl(unsafety, ref trait_ref) => {
                hir::ItemDefaultImpl(self.lower_unsafety(unsafety),
                                     self.lower_trait_ref(trait_ref))
            }
            ItemKind::Impl(unsafety, polarity, ref generics, ref ifce, ref ty, ref impl_items) => {
                let new_impl_items = impl_items.iter()
                                               .map(|item| self.lower_impl_item(item))
                                               .collect();
                let ifce = ifce.as_ref().map(|trait_ref| self.lower_trait_ref(trait_ref));
                hir::ItemImpl(self.lower_unsafety(unsafety),
                              self.lower_impl_polarity(polarity),
                              self.lower_generics(generics),
                              ifce,
                              self.lower_ty(ty),
                              new_impl_items)
            }
            ItemKind::Trait(unsafety, ref generics, ref bounds, ref items) => {
                let bounds = self.lower_bounds(bounds);
                let items = items.iter().map(|item| self.lower_trait_item(item)).collect();
                hir::ItemTrait(self.lower_unsafety(unsafety),
                               self.lower_generics(generics),
                               bounds,
                               items)
            }
            ItemKind::Mac(_) => panic!("Shouldn't still be around"),
        }
    }

    fn lower_trait_item(&mut self, i: &TraitItem) -> hir::TraitItem {
        self.with_parent_def(i.id, |this| {
            hir::TraitItem {
                id: i.id,
                name: i.ident.name,
                attrs: this.lower_attrs(&i.attrs),
                node: match i.node {
                    TraitItemKind::Const(ref ty, ref default) => {
                        hir::ConstTraitItem(this.lower_ty(ty),
                                            default.as_ref().map(|x| this.lower_expr(x)))
                    }
                    TraitItemKind::Method(ref sig, ref body) => {
                        hir::MethodTraitItem(this.lower_method_sig(sig),
                                             body.as_ref().map(|x| this.lower_block(x)))
                    }
                    TraitItemKind::Type(ref bounds, ref default) => {
                        hir::TypeTraitItem(this.lower_bounds(bounds),
                                           default.as_ref().map(|x| this.lower_ty(x)))
                    }
                    TraitItemKind::Macro(..) => panic!("Shouldn't exist any more"),
                },
                span: i.span,
            }
        })
    }

    fn lower_impl_item(&mut self, i: &ImplItem) -> hir::ImplItem {
        self.with_parent_def(i.id, |this| {
            hir::ImplItem {
                id: i.id,
                name: i.ident.name,
                attrs: this.lower_attrs(&i.attrs),
                vis: this.lower_visibility(&i.vis),
                defaultness: this.lower_defaultness(i.defaultness),
                node: match i.node {
                    ImplItemKind::Const(ref ty, ref expr) => {
                        hir::ImplItemKind::Const(this.lower_ty(ty), this.lower_expr(expr))
                    }
                    ImplItemKind::Method(ref sig, ref body) => {
                        hir::ImplItemKind::Method(this.lower_method_sig(sig),
                                                  this.lower_block(body))
                    }
                    ImplItemKind::Type(ref ty) => hir::ImplItemKind::Type(this.lower_ty(ty)),
                    ImplItemKind::Macro(..) => panic!("Shouldn't exist any more"),
                },
                span: i.span,
            }
        })
    }

    fn lower_mod(&mut self, m: &Mod) -> hir::Mod {
        hir::Mod {
            inner: m.inner,
            item_ids: m.items.iter().map(|x| self.lower_item_id(x)).collect(),
        }
    }

    fn lower_macro_def(&mut self, m: &MacroDef) -> hir::MacroDef {
        hir::MacroDef {
            name: m.ident.name,
            attrs: self.lower_attrs(&m.attrs),
            id: m.id,
            span: m.span,
            imported_from: m.imported_from.map(|x| x.name),
            export: m.export,
            use_locally: m.use_locally,
            allow_internal_unstable: m.allow_internal_unstable,
            body: m.body.clone().into(),
        }
    }

    fn lower_item_id(&mut self, i: &Item) -> hir::ItemId {
        hir::ItemId { id: i.id }
    }

    pub fn lower_item(&mut self, i: &Item) -> hir::Item {
        let node = self.with_parent_def(i.id, |this| {
            this.lower_item_kind(&i.node)
        });

        hir::Item {
            id: i.id,
            name: i.ident.name,
            attrs: self.lower_attrs(&i.attrs),
            node: node,
            vis: self.lower_visibility(&i.vis),
            span: i.span,
        }
    }

    fn lower_foreign_item(&mut self, i: &ForeignItem) -> hir::ForeignItem {
        self.with_parent_def(i.id, |this| {
            hir::ForeignItem {
                id: i.id,
                name: i.ident.name,
                attrs: this.lower_attrs(&i.attrs),
                node: match i.node {
                    ForeignItemKind::Fn(ref fdec, ref generics) => {
                        hir::ForeignItemFn(this.lower_fn_decl(fdec), this.lower_generics(generics))
                    }
                    ForeignItemKind::Static(ref t, m) => {
                        hir::ForeignItemStatic(this.lower_ty(t), m)
                    }
                },
                vis: this.lower_visibility(&i.vis),
                span: i.span,
            }
        })
    }

    fn lower_method_sig(&mut self, sig: &MethodSig) -> hir::MethodSig {
        let hir_sig = hir::MethodSig {
            generics: self.lower_generics(&sig.generics),
            abi: sig.abi,
            unsafety: self.lower_unsafety(sig.unsafety),
            constness: self.lower_constness(sig.constness),
            decl: self.lower_fn_decl(&sig.decl),
        };
        // Check for `self: _` and `self: &_`
        if let Some(SelfKind::Explicit(..)) = sig.decl.get_self().map(|eself| eself.node) {
            match hir_sig.decl.get_self().map(|eself| eself.node) {
                Some(hir::SelfKind::Value(..)) | Some(hir::SelfKind::Region(..)) => {
                    self.diagnostic().span_err(sig.decl.inputs[0].ty.span,
                        "the type placeholder `_` is not allowed within types on item signatures");
                }
                _ => {}
            }
        }
        hir_sig
    }

    fn lower_unsafety(&mut self, u: Unsafety) -> hir::Unsafety {
        match u {
            Unsafety::Unsafe => hir::Unsafety::Unsafe,
            Unsafety::Normal => hir::Unsafety::Normal,
        }
    }

    fn lower_constness(&mut self, c: Constness) -> hir::Constness {
        match c {
            Constness::Const => hir::Constness::Const,
            Constness::NotConst => hir::Constness::NotConst,
        }
    }

    fn lower_unop(&mut self, u: UnOp) -> hir::UnOp {
        match u {
            UnOp::Deref => hir::UnDeref,
            UnOp::Not => hir::UnNot,
            UnOp::Neg => hir::UnNeg,
        }
    }

    fn lower_binop(&mut self, b: BinOp) -> hir::BinOp {
        Spanned {
            node: match b.node {
                BinOpKind::Add => hir::BiAdd,
                BinOpKind::Sub => hir::BiSub,
                BinOpKind::Mul => hir::BiMul,
                BinOpKind::Div => hir::BiDiv,
                BinOpKind::Rem => hir::BiRem,
                BinOpKind::And => hir::BiAnd,
                BinOpKind::Or => hir::BiOr,
                BinOpKind::BitXor => hir::BiBitXor,
                BinOpKind::BitAnd => hir::BiBitAnd,
                BinOpKind::BitOr => hir::BiBitOr,
                BinOpKind::Shl => hir::BiShl,
                BinOpKind::Shr => hir::BiShr,
                BinOpKind::Eq => hir::BiEq,
                BinOpKind::Lt => hir::BiLt,
                BinOpKind::Le => hir::BiLe,
                BinOpKind::Ne => hir::BiNe,
                BinOpKind::Ge => hir::BiGe,
                BinOpKind::Gt => hir::BiGt,
            },
            span: b.span,
        }
    }

    fn lower_pat(&mut self, p: &Pat) -> P<hir::Pat> {
        P(hir::Pat {
            id: p.id,
            node: match p.node {
                PatKind::Wild => hir::PatKind::Wild,
                PatKind::Ident(ref binding_mode, pth1, ref sub) => {
                    self.with_parent_def(p.id, |this| {
                        match this.resolver.get_resolution(p.id).map(|d| d.base_def) {
                            // `None` can occur in body-less function signatures
                            None | Some(Def::Local(..)) => {
                                hir::PatKind::Binding(this.lower_binding_mode(binding_mode),
                                                      respan(pth1.span, pth1.node.name),
                                                      sub.as_ref().map(|x| this.lower_pat(x)))
                            }
                            _ => hir::PatKind::Path(None, hir::Path::from_name(pth1.span,
                                                                               pth1.node.name))
                        }
                    })
                }
                PatKind::Lit(ref e) => hir::PatKind::Lit(self.lower_expr(e)),
                PatKind::TupleStruct(ref pth, ref pats, ddpos) => {
                    hir::PatKind::TupleStruct(self.lower_path(pth),
                                              pats.iter().map(|x| self.lower_pat(x)).collect(),
                                              ddpos)
                }
                PatKind::Path(ref opt_qself, ref path) => {
                    let opt_qself = opt_qself.as_ref().map(|qself| {
                        hir::QSelf { ty: self.lower_ty(&qself.ty), position: qself.position }
                    });
                    hir::PatKind::Path(opt_qself, self.lower_path(path))
                }
                PatKind::Struct(ref pth, ref fields, etc) => {
                    let pth = self.lower_path(pth);
                    let fs = fields.iter()
                                   .map(|f| {
                                       Spanned {
                                           span: f.span,
                                           node: hir::FieldPat {
                                               name: f.node.ident.name,
                                               pat: self.lower_pat(&f.node.pat),
                                               is_shorthand: f.node.is_shorthand,
                                           },
                                       }
                                   })
                                   .collect();
                    hir::PatKind::Struct(pth, fs, etc)
                }
                PatKind::Tuple(ref elts, ddpos) => {
                    hir::PatKind::Tuple(elts.iter().map(|x| self.lower_pat(x)).collect(), ddpos)
                }
                PatKind::Box(ref inner) => hir::PatKind::Box(self.lower_pat(inner)),
                PatKind::Ref(ref inner, mutbl) => {
                    hir::PatKind::Ref(self.lower_pat(inner), self.lower_mutability(mutbl))
                }
                PatKind::Range(ref e1, ref e2) => {
                    hir::PatKind::Range(self.lower_expr(e1), self.lower_expr(e2))
                }
                PatKind::Vec(ref before, ref slice, ref after) => {
                    hir::PatKind::Vec(before.iter().map(|x| self.lower_pat(x)).collect(),
                                slice.as_ref().map(|x| self.lower_pat(x)),
                                after.iter().map(|x| self.lower_pat(x)).collect())
                }
                PatKind::Mac(_) => panic!("Shouldn't exist here"),
            },
            span: p.span,
        })
    }

    fn lower_expr(&mut self, e: &Expr) -> P<hir::Expr> {
        P(hir::Expr {
            id: e.id,
            node: match e.node {
                // Issue #22181:
                // Eventually a desugaring for `box EXPR`
                // (similar to the desugaring above for `in PLACE BLOCK`)
                // should go here, desugaring
                //
                // to:
                //
                // let mut place = BoxPlace::make_place();
                // let raw_place = Place::pointer(&mut place);
                // let value = $value;
                // unsafe {
                //     ::std::ptr::write(raw_place, value);
                //     Boxed::finalize(place)
                // }
                //
                // But for now there are type-inference issues doing that.
                ExprKind::Box(ref e) => {
                    hir::ExprBox(self.lower_expr(e))
                }

                // Desugar ExprBox: `in (PLACE) EXPR`
                ExprKind::InPlace(ref placer, ref value_expr) => {
                    // to:
                    //
                    // let p = PLACE;
                    // let mut place = Placer::make_place(p);
                    // let raw_place = Place::pointer(&mut place);
                    // push_unsafe!({
                    //     std::intrinsics::move_val_init(raw_place, pop_unsafe!( EXPR ));
                    //     InPlace::finalize(place)
                    // })
                    let placer_expr = self.lower_expr(placer);
                    let value_expr = self.lower_expr(value_expr);

                    let placer_ident = self.str_to_ident("placer");
                    let place_ident = self.str_to_ident("place");
                    let p_ptr_ident = self.str_to_ident("p_ptr");

                    let make_place = ["ops", "Placer", "make_place"];
                    let place_pointer = ["ops", "Place", "pointer"];
                    let move_val_init = ["intrinsics", "move_val_init"];
                    let inplace_finalize = ["ops", "InPlace", "finalize"];

                    let make_call = |this: &mut LoweringContext, p, args| {
                        let path = this.core_path(e.span, p);
                        let path = this.expr_path(path, ThinVec::new());
                        this.expr_call(e.span, path, args)
                    };

                    let mk_stmt_let = |this: &mut LoweringContext, bind, expr| {
                        this.stmt_let(e.span, false, bind, expr)
                    };

                    let mk_stmt_let_mut = |this: &mut LoweringContext, bind, expr| {
                        this.stmt_let(e.span, true, bind, expr)
                    };

                    // let placer = <placer_expr> ;
                    let (s1, placer_binding) = {
                        let placer_expr = self.signal_block_expr(hir_vec![],
                                                                 placer_expr,
                                                                 e.span,
                                                                 hir::PopUnstableBlock,
                                                                 ThinVec::new());
                        mk_stmt_let(self, placer_ident, placer_expr)
                    };

                    // let mut place = Placer::make_place(placer);
                    let (s2, place_binding) = {
                        let placer = self.expr_ident(e.span, placer_ident, placer_binding);
                        let call = make_call(self, &make_place, hir_vec![placer]);
                        mk_stmt_let_mut(self, place_ident, call)
                    };

                    // let p_ptr = Place::pointer(&mut place);
                    let (s3, p_ptr_binding) = {
                        let agent = self.expr_ident(e.span, place_ident, place_binding);
                        let args = hir_vec![self.expr_mut_addr_of(e.span, agent)];
                        let call = make_call(self, &place_pointer, args);
                        mk_stmt_let(self, p_ptr_ident, call)
                    };

                    // pop_unsafe!(EXPR));
                    let pop_unsafe_expr = {
                        let value_expr = self.signal_block_expr(hir_vec![],
                                                                value_expr,
                                                                e.span,
                                                                hir::PopUnstableBlock,
                                                                ThinVec::new());
                        self.signal_block_expr(hir_vec![],
                                               value_expr,
                                               e.span,
                                               hir::PopUnsafeBlock(hir::CompilerGenerated),
                                               ThinVec::new())
                    };

                    // push_unsafe!({
                    //     std::intrinsics::move_val_init(raw_place, pop_unsafe!( EXPR ));
                    //     InPlace::finalize(place)
                    // })
                    let expr = {
                        let ptr = self.expr_ident(e.span, p_ptr_ident, p_ptr_binding);
                        let call_move_val_init =
                            hir::StmtSemi(
                                make_call(self, &move_val_init, hir_vec![ptr, pop_unsafe_expr]),
                                self.next_id());
                        let call_move_val_init = respan(e.span, call_move_val_init);

                        let place = self.expr_ident(e.span, place_ident, place_binding);
                        let call = make_call(self, &inplace_finalize, hir_vec![place]);
                        self.signal_block_expr(hir_vec![call_move_val_init],
                                               call,
                                               e.span,
                                               hir::PushUnsafeBlock(hir::CompilerGenerated),
                                               ThinVec::new())
                    };

                    return self.signal_block_expr(hir_vec![s1, s2, s3],
                                                  expr,
                                                  e.span,
                                                  hir::PushUnstableBlock,
                                                  e.attrs.clone());
                }

                ExprKind::Vec(ref exprs) => {
                    hir::ExprVec(exprs.iter().map(|x| self.lower_expr(x)).collect())
                }
                ExprKind::Repeat(ref expr, ref count) => {
                    let expr = self.lower_expr(expr);
                    let count = self.lower_expr(count);
                    hir::ExprRepeat(expr, count)
                }
                ExprKind::Tup(ref elts) => {
                    hir::ExprTup(elts.iter().map(|x| self.lower_expr(x)).collect())
                }
                ExprKind::Call(ref f, ref args) => {
                    let f = self.lower_expr(f);
                    hir::ExprCall(f, args.iter().map(|x| self.lower_expr(x)).collect())
                }
                ExprKind::MethodCall(i, ref tps, ref args) => {
                    let tps = tps.iter().map(|x| self.lower_ty(x)).collect();
                    let args = args.iter().map(|x| self.lower_expr(x)).collect();
                    hir::ExprMethodCall(respan(i.span, i.node.name), tps, args)
                }
                ExprKind::Binary(binop, ref lhs, ref rhs) => {
                    let binop = self.lower_binop(binop);
                    let lhs = self.lower_expr(lhs);
                    let rhs = self.lower_expr(rhs);
                    hir::ExprBinary(binop, lhs, rhs)
                }
                ExprKind::Unary(op, ref ohs) => {
                    let op = self.lower_unop(op);
                    let ohs = self.lower_expr(ohs);
                    hir::ExprUnary(op, ohs)
                }
                ExprKind::Lit(ref l) => hir::ExprLit(P((**l).clone())),
                ExprKind::Cast(ref expr, ref ty) => {
                    let expr = self.lower_expr(expr);
                    hir::ExprCast(expr, self.lower_ty(ty))
                }
                ExprKind::Type(ref expr, ref ty) => {
                    let expr = self.lower_expr(expr);
                    hir::ExprType(expr, self.lower_ty(ty))
                }
                ExprKind::AddrOf(m, ref ohs) => {
                    let m = self.lower_mutability(m);
                    let ohs = self.lower_expr(ohs);
                    hir::ExprAddrOf(m, ohs)
                }
                // More complicated than you might expect because the else branch
                // might be `if let`.
                ExprKind::If(ref cond, ref blk, ref else_opt) => {
                    let else_opt = else_opt.as_ref().map(|els| {
                        match els.node {
                            ExprKind::IfLet(..) => {
                                // wrap the if-let expr in a block
                                let span = els.span;
                                let els = self.lower_expr(els);
                                let id = self.next_id();
                                let blk = P(hir::Block {
                                    stmts: hir_vec![],
                                    expr: Some(els),
                                    id: id,
                                    rules: hir::DefaultBlock,
                                    span: span,
                                });
                                self.expr_block(blk, ThinVec::new())
                            }
                            _ => self.lower_expr(els),
                        }
                    });

                    hir::ExprIf(self.lower_expr(cond), self.lower_block(blk), else_opt)
                }
                ExprKind::While(ref cond, ref body, opt_ident) => {
                    hir::ExprWhile(self.lower_expr(cond), self.lower_block(body),
                                   self.lower_opt_sp_ident(opt_ident))
                }
                ExprKind::Loop(ref body, opt_ident) => {
                    hir::ExprLoop(self.lower_block(body), self.lower_opt_sp_ident(opt_ident))
                }
                ExprKind::Match(ref expr, ref arms) => {
                    hir::ExprMatch(self.lower_expr(expr),
                                   arms.iter().map(|x| self.lower_arm(x)).collect(),
                                   hir::MatchSource::Normal)
                }
                ExprKind::Closure(capture_clause, ref decl, ref body, fn_decl_span) => {
                    self.with_parent_def(e.id, |this| {
                        hir::ExprClosure(this.lower_capture_clause(capture_clause),
                                         this.lower_fn_decl(decl),
                                         this.lower_block(body),
                                         fn_decl_span)
                    })
                }
                ExprKind::Block(ref blk) => hir::ExprBlock(self.lower_block(blk)),
                ExprKind::Assign(ref el, ref er) => {
                    hir::ExprAssign(self.lower_expr(el), self.lower_expr(er))
                }
                ExprKind::AssignOp(op, ref el, ref er) => {
                    hir::ExprAssignOp(self.lower_binop(op),
                                      self.lower_expr(el),
                                      self.lower_expr(er))
                }
                ExprKind::Field(ref el, ident) => {
                    hir::ExprField(self.lower_expr(el), respan(ident.span, ident.node.name))
                }
                ExprKind::TupField(ref el, ident) => {
                    hir::ExprTupField(self.lower_expr(el), ident)
                }
                ExprKind::Index(ref el, ref er) => {
                    hir::ExprIndex(self.lower_expr(el), self.lower_expr(er))
                }
                ExprKind::Range(ref e1, ref e2, lims) => {
                    fn make_struct(this: &mut LoweringContext,
                                   ast_expr: &Expr,
                                   path: &[&str],
                                   fields: &[(&str, &P<Expr>)]) -> P<hir::Expr> {
                        let strs = this.std_path(&iter::once(&"ops")
                                                        .chain(path)
                                                        .map(|s| *s)
                                                        .collect::<Vec<_>>());

                        let structpath = this.path_global(ast_expr.span, strs);

                        let hir_expr = if fields.len() == 0 {
                            this.expr_path(structpath, ast_expr.attrs.clone())
                        } else {
                            let fields = fields.into_iter().map(|&(s, e)| {
                                let expr = this.lower_expr(&e);
                                let signal_block = this.signal_block_expr(hir_vec![],
                                                                          expr,
                                                                          e.span,
                                                                          hir::PopUnstableBlock,
                                                                          ThinVec::new());
                                this.field(token::intern(s), signal_block, ast_expr.span)
                            }).collect();
                            let attrs = ast_expr.attrs.clone();

                            this.expr_struct(ast_expr.span, structpath, fields, None, attrs)
                        };

                        this.signal_block_expr(hir_vec![],
                                               hir_expr,
                                               ast_expr.span,
                                               hir::PushUnstableBlock,
                                               ThinVec::new())
                    }

                    use syntax::ast::RangeLimits::*;

                    return match (e1, e2, lims) {
                        (&None,         &None,         HalfOpen) =>
                            make_struct(self, e, &["RangeFull"], &[]),

                        (&Some(ref e1), &None,         HalfOpen) =>
                            make_struct(self, e, &["RangeFrom"],
                                                 &[("start", e1)]),

                        (&None,         &Some(ref e2), HalfOpen) =>
                            make_struct(self, e, &["RangeTo"],
                                                 &[("end", e2)]),

                        (&Some(ref e1), &Some(ref e2), HalfOpen) =>
                            make_struct(self, e, &["Range"],
                                                 &[("start", e1), ("end", e2)]),

                        (&None,         &Some(ref e2), Closed)   =>
                            make_struct(self, e, &["RangeToInclusive"],
                                                 &[("end", e2)]),

                        (&Some(ref e1), &Some(ref e2), Closed)   =>
                            make_struct(self, e, &["RangeInclusive", "NonEmpty"],
                                                 &[("start", e1), ("end", e2)]),

                        _ => panic!(self.diagnostic()
                                        .span_fatal(e.span, "inclusive range with no end")),
                    };
                }
                ExprKind::Path(ref qself, ref path) => {
                    let hir_qself = qself.as_ref().map(|&QSelf { ref ty, position }| {
                        hir::QSelf {
                            ty: self.lower_ty(ty),
                            position: position,
                        }
                    });
                    hir::ExprPath(hir_qself, self.lower_path(path))
                }
                ExprKind::Break(opt_ident) => hir::ExprBreak(self.lower_opt_sp_ident(opt_ident)),
                ExprKind::Continue(opt_ident) => hir::ExprAgain(self.lower_opt_sp_ident(opt_ident)),
                ExprKind::Ret(ref e) => hir::ExprRet(e.as_ref().map(|x| self.lower_expr(x))),
                ExprKind::InlineAsm(InlineAsm {
                        ref inputs,
                        ref outputs,
                        ref asm,
                        asm_str_style,
                        ref clobbers,
                        volatile,
                        alignstack,
                        dialect,
                        expn_id,
                    }) => hir::ExprInlineAsm(hir::InlineAsm {
                    inputs: inputs.iter().map(|&(ref c, _)| c.clone()).collect(),
                    outputs: outputs.iter()
                                    .map(|out| {
                                        hir::InlineAsmOutput {
                                            constraint: out.constraint.clone(),
                                            is_rw: out.is_rw,
                                            is_indirect: out.is_indirect,
                                        }
                                    })
                                    .collect(),
                    asm: asm.clone(),
                    asm_str_style: asm_str_style,
                    clobbers: clobbers.clone().into(),
                    volatile: volatile,
                    alignstack: alignstack,
                    dialect: dialect,
                    expn_id: expn_id,
                }, outputs.iter().map(|out| self.lower_expr(&out.expr)).collect(),
                   inputs.iter().map(|&(_, ref input)| self.lower_expr(input)).collect()),
                ExprKind::Struct(ref path, ref fields, ref maybe_expr) => {
                    hir::ExprStruct(self.lower_path(path),
                                    fields.iter().map(|x| self.lower_field(x)).collect(),
                                    maybe_expr.as_ref().map(|x| self.lower_expr(x)))
                }
                ExprKind::Paren(ref ex) => {
                    return self.lower_expr(ex).map(|mut ex| {
                        // include parens in span, but only if it is a super-span.
                        if e.span.contains(ex.span) {
                            ex.span = e.span;
                        }
                        // merge attributes into the inner expression.
                        let mut attrs = e.attrs.clone();
                        attrs.extend::<Vec<_>>(ex.attrs.into());
                        ex.attrs = attrs;
                        ex
                    });
                }

                // Desugar ExprIfLet
                // From: `if let <pat> = <sub_expr> <body> [<else_opt>]`
                ExprKind::IfLet(ref pat, ref sub_expr, ref body, ref else_opt) => {
                    // to:
                    //
                    //   match <sub_expr> {
                    //     <pat> => <body>,
                    //     [_ if <else_opt_if_cond> => <else_opt_if_body>,]
                    //     _ => [<else_opt> | ()]
                    //   }

                    // `<pat> => <body>`
                    let pat_arm = {
                        let body = self.lower_block(body);
                        let body_expr = self.expr_block(body, ThinVec::new());
                        let pat = self.lower_pat(pat);
                        self.arm(hir_vec![pat], body_expr)
                    };

                    // `[_ if <else_opt_if_cond> => <else_opt_if_body>,]`
                    let mut else_opt = else_opt.as_ref().map(|e| self.lower_expr(e));
                    let else_if_arms = {
                        let mut arms = vec![];
                        loop {
                            let else_opt_continue = else_opt.and_then(|els| {
                                els.and_then(|els| {
                                    match els.node {
                                        // else if
                                        hir::ExprIf(cond, then, else_opt) => {
                                            let pat_under = self.pat_wild(e.span);
                                            arms.push(hir::Arm {
                                                attrs: hir_vec![],
                                                pats: hir_vec![pat_under],
                                                guard: Some(cond),
                                                body: self.expr_block(then, ThinVec::new()),
                                            });
                                            else_opt.map(|else_opt| (else_opt, true))
                                        }
                                        _ => Some((P(els), false)),
                                    }
                                })
                            });
                            match else_opt_continue {
                                Some((e, true)) => {
                                    else_opt = Some(e);
                                }
                                Some((e, false)) => {
                                    else_opt = Some(e);
                                    break;
                                }
                                None => {
                                    else_opt = None;
                                    break;
                                }
                            }
                        }
                        arms
                    };

                    let contains_else_clause = else_opt.is_some();

                    // `_ => [<else_opt> | ()]`
                    let else_arm = {
                        let pat_under = self.pat_wild(e.span);
                        let else_expr =
                            else_opt.unwrap_or_else(|| self.expr_tuple(e.span, hir_vec![]));
                        self.arm(hir_vec![pat_under], else_expr)
                    };

                    let mut arms = Vec::with_capacity(else_if_arms.len() + 2);
                    arms.push(pat_arm);
                    arms.extend(else_if_arms);
                    arms.push(else_arm);

                    let sub_expr = self.lower_expr(sub_expr);
                    // add attributes to the outer returned expr node
                    return self.expr(e.span,
                                     hir::ExprMatch(sub_expr,
                                                    arms.into(),
                                                    hir::MatchSource::IfLetDesugar {
                                                        contains_else_clause: contains_else_clause,
                                                    }),
                                     e.attrs.clone());
                }

                // Desugar ExprWhileLet
                // From: `[opt_ident]: while let <pat> = <sub_expr> <body>`
                ExprKind::WhileLet(ref pat, ref sub_expr, ref body, opt_ident) => {
                    // to:
                    //
                    //   [opt_ident]: loop {
                    //     match <sub_expr> {
                    //       <pat> => <body>,
                    //       _ => break
                    //     }
                    //   }

                    // `<pat> => <body>`
                    let pat_arm = {
                        let body = self.lower_block(body);
                        let body_expr = self.expr_block(body, ThinVec::new());
                        let pat = self.lower_pat(pat);
                        self.arm(hir_vec![pat], body_expr)
                    };

                    // `_ => break`
                    let break_arm = {
                        let pat_under = self.pat_wild(e.span);
                        let break_expr = self.expr_break(e.span, ThinVec::new());
                        self.arm(hir_vec![pat_under], break_expr)
                    };

                    // `match <sub_expr> { ... }`
                    let arms = hir_vec![pat_arm, break_arm];
                    let sub_expr = self.lower_expr(sub_expr);
                    let match_expr = self.expr(e.span,
                                               hir::ExprMatch(sub_expr,
                                                              arms,
                                                              hir::MatchSource::WhileLetDesugar),
                                               ThinVec::new());

                    // `[opt_ident]: loop { ... }`
                    let loop_block = self.block_expr(match_expr);
                    let loop_expr = hir::ExprLoop(loop_block, self.lower_opt_sp_ident(opt_ident));
                    // add attributes to the outer returned expr node
                    let attrs = e.attrs.clone();
                    return P(hir::Expr { id: e.id, node: loop_expr, span: e.span, attrs: attrs });
                }

                // Desugar ExprForLoop
                // From: `[opt_ident]: for <pat> in <head> <body>`
                ExprKind::ForLoop(ref pat, ref head, ref body, opt_ident) => {
                    // to:
                    //
                    //   {
                    //     let result = match ::std::iter::IntoIterator::into_iter(<head>) {
                    //       mut iter => {
                    //         [opt_ident]: loop {
                    //           match ::std::iter::Iterator::next(&mut iter) {
                    //             ::std::option::Option::Some(<pat>) => <body>,
                    //             ::std::option::Option::None => break
                    //           }
                    //         }
                    //       }
                    //     };
                    //     result
                    //   }

                    // expand <head>
                    let head = self.lower_expr(head);

                    let iter = self.str_to_ident("iter");

                    // `::std::option::Option::Some(<pat>) => <body>`
                    let pat_arm = {
                        let body_block = self.lower_block(body);
                        let body_span = body_block.span;
                        let body_expr = P(hir::Expr {
                            id: self.next_id(),
                            node: hir::ExprBlock(body_block),
                            span: body_span,
                            attrs: ThinVec::new(),
                        });
                        let pat = self.lower_pat(pat);
                        let some_pat = self.pat_some(e.span, pat);

                        self.arm(hir_vec![some_pat], body_expr)
                    };

                    // `::std::option::Option::None => break`
                    let break_arm = {
                        let break_expr = self.expr_break(e.span, ThinVec::new());
                        let pat = self.pat_none(e.span);
                        self.arm(hir_vec![pat], break_expr)
                    };

                    // `mut iter`
                    let iter_pat = self.pat_ident_binding_mode(e.span, iter,
                                                               hir::BindByValue(hir::MutMutable));

                    // `match ::std::iter::Iterator::next(&mut iter) { ... }`
                    let match_expr = {
                        let next_path = {
                            let strs = self.std_path(&["iter", "Iterator", "next"]);

                            self.path_global(e.span, strs)
                        };
                        let iter = self.expr_ident(e.span, iter, iter_pat.id);
                        let ref_mut_iter = self.expr_mut_addr_of(e.span, iter);
                        let next_path = self.expr_path(next_path, ThinVec::new());
                        let next_expr = self.expr_call(e.span, next_path, hir_vec![ref_mut_iter]);
                        let arms = hir_vec![pat_arm, break_arm];

                        self.expr(e.span,
                                  hir::ExprMatch(next_expr, arms, hir::MatchSource::ForLoopDesugar),
                                  ThinVec::new())
                    };

                    // `[opt_ident]: loop { ... }`
                    let loop_block = self.block_expr(match_expr);
                    let loop_expr = hir::ExprLoop(loop_block, self.lower_opt_sp_ident(opt_ident));
                    let loop_expr = P(hir::Expr {
                        id: e.id,
                        node: loop_expr,
                        span: e.span,
                        attrs: ThinVec::new(),
                    });

                    // `mut iter => { ... }`
                    let iter_arm = self.arm(hir_vec![iter_pat], loop_expr);

                    // `match ::std::iter::IntoIterator::into_iter(<head>) { ... }`
                    let into_iter_expr = {
                        let into_iter_path = {
                            let strs = self.std_path(&["iter", "IntoIterator", "into_iter"]);

                            self.path_global(e.span, strs)
                        };

                        let into_iter = self.expr_path(into_iter_path, ThinVec::new());
                        self.expr_call(e.span, into_iter, hir_vec![head])
                    };

                    let match_expr = self.expr_match(e.span,
                                                     into_iter_expr,
                                                     hir_vec![iter_arm],
                                                     hir::MatchSource::ForLoopDesugar);

                    // `{ let _result = ...; _result }`
                    // underscore prevents an unused_variables lint if the head diverges
                    let result_ident = self.str_to_ident("_result");
                    let (let_stmt, let_stmt_binding) =
                        self.stmt_let(e.span, false, result_ident, match_expr);

                    let result = self.expr_ident(e.span, result_ident, let_stmt_binding);
                    let block = self.block_all(e.span, hir_vec![let_stmt], Some(result));
                    // add the attributes to the outer returned expr node
                    return self.expr_block(block, e.attrs.clone());
                }

                // Desugar ExprKind::Try
                // From: `<expr>?`
                ExprKind::Try(ref sub_expr) => {
                    // to:
                    //
                    // {
                    //     match <expr> {
                    //         Ok(val) => val,
                    //         Err(err) => {
                    //             return Err(From::from(err))
                    //         }
                    //     }
                    // }

                    // expand <expr>
                    let sub_expr = self.lower_expr(sub_expr);

                    // Ok(val) => val
                    let ok_arm = {
                        let val_ident = self.str_to_ident("val");
                        let val_pat = self.pat_ident(e.span, val_ident);
                        let val_expr = self.expr_ident(e.span, val_ident, val_pat.id);
                        let ok_pat = self.pat_ok(e.span, val_pat);

                        self.arm(hir_vec![ok_pat], val_expr)
                    };

                    // Err(err) => return Err(From::from(err))
                    let err_arm = {
                        let err_ident = self.str_to_ident("err");
                        let err_local = self.pat_ident(e.span, err_ident);
                        let from_expr = {
                            let path = self.std_path(&["convert", "From", "from"]);
                            let path = self.path_global(e.span, path);
                            let from = self.expr_path(path, ThinVec::new());
                            let err_expr = self.expr_ident(e.span, err_ident, err_local.id);

                            self.expr_call(e.span, from, hir_vec![err_expr])
                        };
                        let err_expr = {
                            let path = self.std_path(&["result", "Result", "Err"]);
                            let path = self.path_global(e.span, path);
                            let err_ctor = self.expr_path(path, ThinVec::new());
                            self.expr_call(e.span, err_ctor, hir_vec![from_expr])
                        };
                        let err_pat = self.pat_err(e.span, err_local);
                        let ret_expr = self.expr(e.span,
                                                 hir::Expr_::ExprRet(Some(err_expr)),
                                                 ThinVec::new());
                        self.arm(hir_vec![err_pat], ret_expr)
                    };

                    return self.expr_match(e.span, sub_expr, hir_vec![err_arm, ok_arm],
                                           hir::MatchSource::TryDesugar);
                }

                ExprKind::Mac(_) => panic!("Shouldn't exist here"),
            },
            span: e.span,
            attrs: e.attrs.clone(),
        })
    }

    fn lower_stmt(&mut self, s: &Stmt) -> hir::Stmt {
        match s.node {
            StmtKind::Local(ref l) => Spanned {
                node: hir::StmtDecl(P(Spanned {
                    node: hir::DeclLocal(self.lower_local(l)),
                    span: s.span,
                }), s.id),
                span: s.span,
            },
            StmtKind::Item(ref it) => Spanned {
                node: hir::StmtDecl(P(Spanned {
                    node: hir::DeclItem(self.lower_item_id(it)),
                    span: s.span,
                }), s.id),
                span: s.span,
            },
            StmtKind::Expr(ref e) => {
                Spanned {
                    node: hir::StmtExpr(self.lower_expr(e), s.id),
                    span: s.span,
                }
            }
            StmtKind::Semi(ref e) => {
                Spanned {
                    node: hir::StmtSemi(self.lower_expr(e), s.id),
                    span: s.span,
                }
            }
            StmtKind::Mac(..) => panic!("Shouldn't exist here"),
        }
    }

    fn lower_capture_clause(&mut self, c: CaptureBy) -> hir::CaptureClause {
        match c {
            CaptureBy::Value => hir::CaptureByValue,
            CaptureBy::Ref => hir::CaptureByRef,
        }
    }

    fn lower_visibility(&mut self, v: &Visibility) -> hir::Visibility {
        match *v {
            Visibility::Public => hir::Public,
            Visibility::Crate(_) => hir::Visibility::Crate,
            Visibility::Restricted { ref path, id } =>
                hir::Visibility::Restricted { path: P(self.lower_path(path)), id: id },
            Visibility::Inherited => hir::Inherited,
        }
    }

    fn lower_defaultness(&mut self, d: Defaultness) -> hir::Defaultness {
        match d {
            Defaultness::Default => hir::Defaultness::Default,
            Defaultness::Final => hir::Defaultness::Final,
        }
    }

    fn lower_block_check_mode(&mut self, b: &BlockCheckMode) -> hir::BlockCheckMode {
        match *b {
            BlockCheckMode::Default => hir::DefaultBlock,
            BlockCheckMode::Unsafe(u) => hir::UnsafeBlock(self.lower_unsafe_source(u)),
        }
    }

    fn lower_binding_mode(&mut self, b: &BindingMode) -> hir::BindingMode {
        match *b {
            BindingMode::ByRef(m) => hir::BindByRef(self.lower_mutability(m)),
            BindingMode::ByValue(m) => hir::BindByValue(self.lower_mutability(m)),
        }
    }

    fn lower_unsafe_source(&mut self, u: UnsafeSource) -> hir::UnsafeSource {
        match u {
            CompilerGenerated => hir::CompilerGenerated,
            UserProvided => hir::UserProvided,
        }
    }

    fn lower_impl_polarity(&mut self, i: ImplPolarity) -> hir::ImplPolarity {
        match i {
            ImplPolarity::Positive => hir::ImplPolarity::Positive,
            ImplPolarity::Negative => hir::ImplPolarity::Negative,
        }
    }

    fn lower_trait_bound_modifier(&mut self, f: TraitBoundModifier) -> hir::TraitBoundModifier {
        match f {
            TraitBoundModifier::None => hir::TraitBoundModifier::None,
            TraitBoundModifier::Maybe => hir::TraitBoundModifier::Maybe,
        }
    }

    // Helper methods for building HIR.

    fn arm(&mut self, pats: hir::HirVec<P<hir::Pat>>, expr: P<hir::Expr>) -> hir::Arm {
        hir::Arm {
            attrs: hir_vec![],
            pats: pats,
            guard: None,
            body: expr,
        }
    }

    fn field(&mut self, name: Name, expr: P<hir::Expr>, span: Span) -> hir::Field {
        hir::Field {
            name: Spanned {
                node: name,
                span: span,
            },
            span: span,
            expr: expr,
        }
    }

    fn expr_break(&mut self, span: Span, attrs: ThinVec<Attribute>) -> P<hir::Expr> {
        self.expr(span, hir::ExprBreak(None), attrs)
    }

    fn expr_call(&mut self, span: Span, e: P<hir::Expr>, args: hir::HirVec<P<hir::Expr>>)
                 -> P<hir::Expr> {
        self.expr(span, hir::ExprCall(e, args), ThinVec::new())
    }

    fn expr_ident(&mut self, span: Span, id: Name, binding: NodeId) -> P<hir::Expr> {
        let expr_path = hir::ExprPath(None, self.path_ident(span, id));
        let expr = self.expr(span, expr_path, ThinVec::new());

        let def = self.resolver.definitions().map(|defs| {
            Def::Local(defs.local_def_id(binding), binding)
        }).unwrap_or(Def::Err);
        self.resolver.record_resolution(expr.id, def);

        expr
    }

    fn expr_mut_addr_of(&mut self, span: Span, e: P<hir::Expr>) -> P<hir::Expr> {
        self.expr(span, hir::ExprAddrOf(hir::MutMutable, e), ThinVec::new())
    }

    fn expr_path(&mut self, path: hir::Path, attrs: ThinVec<Attribute>) -> P<hir::Expr> {
        let def = self.resolver.resolve_generated_global_path(&path, true);
        let expr = self.expr(path.span, hir::ExprPath(None, path), attrs);
        self.resolver.record_resolution(expr.id, def);
        expr
    }

    fn expr_match(&mut self,
                  span: Span,
                  arg: P<hir::Expr>,
                  arms: hir::HirVec<hir::Arm>,
                  source: hir::MatchSource)
                  -> P<hir::Expr> {
        self.expr(span, hir::ExprMatch(arg, arms, source), ThinVec::new())
    }

    fn expr_block(&mut self, b: P<hir::Block>, attrs: ThinVec<Attribute>) -> P<hir::Expr> {
        self.expr(b.span, hir::ExprBlock(b), attrs)
    }

    fn expr_tuple(&mut self, sp: Span, exprs: hir::HirVec<P<hir::Expr>>) -> P<hir::Expr> {
        self.expr(sp, hir::ExprTup(exprs), ThinVec::new())
    }

    fn expr_struct(&mut self,
                   sp: Span,
                   path: hir::Path,
                   fields: hir::HirVec<hir::Field>,
                   e: Option<P<hir::Expr>>,
                   attrs: ThinVec<Attribute>) -> P<hir::Expr> {
        let def = self.resolver.resolve_generated_global_path(&path, false);
        let expr = self.expr(sp, hir::ExprStruct(path, fields, e), attrs);
        self.resolver.record_resolution(expr.id, def);
        expr
    }

    fn expr(&mut self, span: Span, node: hir::Expr_, attrs: ThinVec<Attribute>) -> P<hir::Expr> {
        P(hir::Expr {
            id: self.next_id(),
            node: node,
            span: span,
            attrs: attrs,
        })
    }

    fn stmt_let(&mut self, sp: Span, mutbl: bool, ident: Name, ex: P<hir::Expr>)
                -> (hir::Stmt, NodeId) {
        let pat = if mutbl {
            self.pat_ident_binding_mode(sp, ident, hir::BindByValue(hir::MutMutable))
        } else {
            self.pat_ident(sp, ident)
        };
        let pat_id = pat.id;
        let local = P(hir::Local {
            pat: pat,
            ty: None,
            init: Some(ex),
            id: self.next_id(),
            span: sp,
            attrs: ThinVec::new(),
        });
        let decl = respan(sp, hir::DeclLocal(local));
        (respan(sp, hir::StmtDecl(P(decl), self.next_id())), pat_id)
    }

    fn block_expr(&mut self, expr: P<hir::Expr>) -> P<hir::Block> {
        self.block_all(expr.span, hir::HirVec::new(), Some(expr))
    }

    fn block_all(&mut self, span: Span, stmts: hir::HirVec<hir::Stmt>, expr: Option<P<hir::Expr>>)
                 -> P<hir::Block> {
        P(hir::Block {
            stmts: stmts,
            expr: expr,
            id: self.next_id(),
            rules: hir::DefaultBlock,
            span: span,
        })
    }

    fn pat_ok(&mut self, span: Span, pat: P<hir::Pat>) -> P<hir::Pat> {
        let ok = self.std_path(&["result", "Result", "Ok"]);
        let path = self.path_global(span, ok);
        self.pat_enum(span, path, hir_vec![pat])
    }

    fn pat_err(&mut self, span: Span, pat: P<hir::Pat>) -> P<hir::Pat> {
        let err = self.std_path(&["result", "Result", "Err"]);
        let path = self.path_global(span, err);
        self.pat_enum(span, path, hir_vec![pat])
    }

    fn pat_some(&mut self, span: Span, pat: P<hir::Pat>) -> P<hir::Pat> {
        let some = self.std_path(&["option", "Option", "Some"]);
        let path = self.path_global(span, some);
        self.pat_enum(span, path, hir_vec![pat])
    }

    fn pat_none(&mut self, span: Span) -> P<hir::Pat> {
        let none = self.std_path(&["option", "Option", "None"]);
        let path = self.path_global(span, none);
        self.pat_enum(span, path, hir_vec![])
    }

    fn pat_enum(&mut self, span: Span, path: hir::Path, subpats: hir::HirVec<P<hir::Pat>>)
                -> P<hir::Pat> {
        let def = self.resolver.resolve_generated_global_path(&path, true);
        let pt = if subpats.is_empty() {
            hir::PatKind::Path(None, path)
        } else {
            hir::PatKind::TupleStruct(path, subpats, None)
        };
        let pat = self.pat(span, pt);
        self.resolver.record_resolution(pat.id, def);
        pat
    }

    fn pat_ident(&mut self, span: Span, name: Name) -> P<hir::Pat> {
        self.pat_ident_binding_mode(span, name, hir::BindByValue(hir::MutImmutable))
    }

    fn pat_ident_binding_mode(&mut self, span: Span, name: Name, bm: hir::BindingMode)
                              -> P<hir::Pat> {
        let pat_ident = hir::PatKind::Binding(bm,
                                            Spanned {
                                                span: span,
                                                node: name,
                                            },
                                            None);

        let pat = self.pat(span, pat_ident);

        let parent_def = self.parent_def;
        let def = self.resolver.definitions().map(|defs| {
            let def_path_data = DefPathData::Binding(name);
            let def_index = defs.create_def_with_parent(parent_def, pat.id, def_path_data);
            Def::Local(DefId::local(def_index), pat.id)
        }).unwrap_or(Def::Err);
        self.resolver.record_resolution(pat.id, def);

        pat
    }

    fn pat_wild(&mut self, span: Span) -> P<hir::Pat> {
        self.pat(span, hir::PatKind::Wild)
    }

    fn pat(&mut self, span: Span, pat: hir::PatKind) -> P<hir::Pat> {
        P(hir::Pat {
            id: self.next_id(),
            node: pat,
            span: span,
        })
    }

    fn path_ident(&mut self, span: Span, id: Name) -> hir::Path {
        self.path(span, vec![id])
    }

    fn path(&mut self, span: Span, strs: Vec<Name>) -> hir::Path {
        self.path_all(span, false, strs, hir::HirVec::new(), hir::HirVec::new(), hir::HirVec::new())
    }

    fn path_global(&mut self, span: Span, strs: Vec<Name>) -> hir::Path {
        self.path_all(span, true, strs, hir::HirVec::new(), hir::HirVec::new(), hir::HirVec::new())
    }

    fn path_all(&mut self,
                sp: Span,
                global: bool,
                mut names: Vec<Name>,
                lifetimes: hir::HirVec<hir::Lifetime>,
                types: hir::HirVec<P<hir::Ty>>,
                bindings: hir::HirVec<hir::TypeBinding>)
                -> hir::Path {
        let last_identifier = names.pop().unwrap();
        let mut segments: Vec<hir::PathSegment> = names.into_iter().map(|name| {
            hir::PathSegment {
                name: name,
                parameters: hir::PathParameters::none(),
           }
        }).collect();

        segments.push(hir::PathSegment {
            name: last_identifier,
            parameters: hir::AngleBracketedParameters(hir::AngleBracketedParameterData {
                lifetimes: lifetimes,
                types: types,
                bindings: bindings,
            }),
        });
        hir::Path {
            span: sp,
            global: global,
            segments: segments.into(),
        }
    }

    fn std_path(&mut self, components: &[&str]) -> Vec<Name> {
        let mut v = Vec::new();
        if let Some(s) = self.crate_root {
            v.push(token::intern(s));
        }
        v.extend(components.iter().map(|s| token::intern(s)));
        return v;
    }

    // Given suffix ["b","c","d"], returns path `::std::b::c::d` when
    // `fld.cx.use_std`, and `::core::b::c::d` otherwise.
    fn core_path(&mut self, span: Span, components: &[&str]) -> hir::Path {
        let idents = self.std_path(components);
        self.path_global(span, idents)
    }

    fn signal_block_expr(&mut self,
                         stmts: hir::HirVec<hir::Stmt>,
                         expr: P<hir::Expr>,
                         span: Span,
                         rule: hir::BlockCheckMode,
                         attrs: ThinVec<Attribute>)
                         -> P<hir::Expr> {
        let id = self.next_id();
        let block = P(hir::Block {
            rules: rule,
            span: span,
            id: id,
            stmts: stmts,
            expr: Some(expr),
        });
        self.expr_block(block, attrs)
    }
}