src/librustc/hir/lowering.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Lowers the AST to the HIR.
  12 //!
  13 //! Since the AST and HIR are fairly similar, this is mostly a simple procedure,
  14 //! much like a fold. Where lowering involves a bit more work things get more
  15 //! interesting and there are some invariants you should know about. These mostly
  16 //! concern spans and ids.
  17 //!
  18 //! Spans are assigned to AST nodes during parsing and then are modified during
  19 //! expansion to indicate the origin of a node and the process it went through
  20 //! being expanded. Ids are assigned to AST nodes just before lowering.
  21 //!
  22 //! For the simpler lowering steps, ids and spans should be preserved. Unlike
  23 //! expansion we do not preserve the process of lowering in the spans, so spans
  24 //! should not be modified here. When creating a new node (as opposed to
  25 //! 'folding' an existing one), then you create a new id using `next_id()`.
  26 //!
  27 //! You must ensure that ids are unique. That means that you should only use the
  28 //! id from an AST node in a single HIR node (you can assume that AST node ids
  29 //! are unique). Every new node must have a unique id. Avoid cloning HIR nodes.
  30 //! If you do, you must then set the new node's id to a fresh one.
  31 //!
  32 //! Spans are used for error messages and for tools to map semantics back to
  33 //! source code. It is therefore not as important with spans as ids to be strict
  34 //! about use (you can't break the compiler by screwing up a span). Obviously, a
  35 //! HIR node can only have a single span. But multiple nodes can have the same
  36 //! span and spans don't need to be kept in order, etc. Where code is preserved
  37 //! by lowering, it should have the same span as in the AST. Where HIR nodes are
  38 //! new it is probably best to give a span for the whole AST node being lowered.
  39 //! All nodes should have real spans, don't use dummy spans. Tools are likely to
  40 //! get confused if the spans from leaf AST nodes occur in multiple places
  41 //! in the HIR, especially for multiple identifiers.
  42
  43 use dep_graph::DepGraph;
  44 use hir;
  45 use hir::HirVec;
  46 use hir::map::{Definitions, DefKey, DefPathData};
  47 use hir::def_id::{DefIndex, DefId, CRATE_DEF_INDEX, DefIndexAddressSpace};
  48 use hir::def::{Def, PathResolution};
  49 use lint::builtin::PARENTHESIZED_PARAMS_IN_TYPES_AND_MODULES;
  50 use middle::cstore::CrateStore;
  51 use rustc_data_structures::indexed_vec::IndexVec;
  52 use session::Session;
  53 use util::common::FN_OUTPUT_NAME;
  54 use util::nodemap::{DefIdMap, FxHashMap, NodeMap};
  55
  56 use std::collections::{BTreeMap, HashSet};
  57 use std::fmt::Debug;
  58 use std::iter;
  59 use std::mem;
  60 use syntax::attr;
  61 use syntax::ast::*;
  62 use syntax::errors;
  63 use syntax::ext::hygiene::{Mark, SyntaxContext};
  64 use syntax::print::pprust;
  65 use syntax::ptr::P;
  66 use syntax::codemap::{self, respan, Spanned, CompilerDesugaringKind};
  67 use syntax::std_inject;
  68 use syntax::symbol::{Symbol, keywords};
  69 use syntax::tokenstream::{TokenStream, TokenTree, Delimited};
  70 use syntax::parse::token::Token;
  71 use syntax::util::small_vector::SmallVector;
  72 use syntax::visit::{self, Visitor};
  73 use syntax_pos::Span;
  74
  75 const HIR_ID_COUNTER_LOCKED: u32 = 0xFFFFFFFF;
  76
  77 pub struct LoweringContext<'a> {
  78     crate_root: Option<&'static str>,
  79
  80     // Use to assign ids to hir nodes that do not directly correspond to an ast node
  81     sess: &'a Session,
  82
  83     cstore: &'a CrateStore,
  84
  85     // As we walk the AST we must keep track of the current 'parent' def id (in
  86     // the form of a DefIndex) so that if we create a new node which introduces
  87     // a definition, then we can properly create the def id.
  88     parent_def: Option<DefIndex>,
  89     resolver: &'a mut Resolver,
  90     name_map: FxHashMap<Ident, Name>,
  91
  92     /// The items being lowered are collected here.
  93     items: BTreeMap<NodeId, hir::Item>,
  94
  95     trait_items: BTreeMap<hir::TraitItemId, hir::TraitItem>,
  96     impl_items: BTreeMap<hir::ImplItemId, hir::ImplItem>,
  97     bodies: BTreeMap<hir::BodyId, hir::Body>,
  98     exported_macros: Vec<hir::MacroDef>,
  99
 100     trait_impls: BTreeMap<DefId, Vec<NodeId>>,
 101     trait_auto_impl: BTreeMap<DefId, NodeId>,
 102
 103     is_generator: bool,
 104
 105     catch_scopes: Vec<NodeId>,
 106     loop_scopes: Vec<NodeId>,
 107     is_in_loop_condition: bool,
 108     is_in_trait_impl: bool,
 109
 110     // This is a list of in-band type definitions being generated by
 111     // Argument-position `impl Trait`.
 112     // When traversing a signature such as `fn foo(x: impl Trait)`,
 113     // we record `impl Trait` as a new type parameter, then later
 114     // add it on to `foo`s generics.
 115     in_band_ty_params: Vec<hir::TyParam>,
 116
 117     // Used to create lifetime definitions from in-band lifetime usages.
 118     // e.g. `fn foo(x: &'x u8) -> &'x u8` to `fn foo<'x>(x: &'x u8) -> &'x u8`
 119     // When a named lifetime is encountered in a function or impl header and
 120     // has not been defined
 121     // (i.e. it doesn't appear in the in_scope_lifetimes list), it is added
 122     // to this list. The results of this list are then added to the list of
 123     // lifetime definitions in the corresponding impl or function generics.
 124     lifetimes_to_define: Vec<(Span, Name)>,
 125     // Whether or not in-band lifetimes are being collected. This is used to
 126     // indicate whether or not we're in a place where new lifetimes will result
 127     // in in-band lifetime definitions, such a function or an impl header.
 128     // This will always be false unless the `in_band_lifetimes` feature is
 129     // enabled.
 130     is_collecting_in_band_lifetimes: bool,
 131     // Currently in-scope lifetimes defined in impl headers, fn headers, or HRTB.
 132     // When `is_collectin_in_band_lifetimes` is true, each lifetime is checked
 133     // against this list to see if it is already in-scope, or if a definition
 134     // needs to be created for it.
 135     in_scope_lifetimes: Vec<Name>,
 136
 137     type_def_lifetime_params: DefIdMap<usize>,
 138
 139     current_hir_id_owner: Vec<(DefIndex, u32)>,
 140     item_local_id_counters: NodeMap<u32>,
 141     node_id_to_hir_id: IndexVec<NodeId, hir::HirId>,
 142 }
 143
 144 pub trait Resolver {
 145     /// Resolve a hir path generated by the lowerer when expanding `for`, `if let`, etc.
 146     fn resolve_hir_path(&mut self, path: &mut hir::Path, is_value: bool);
 147
 148     /// Obtain the resolution for a node id
 149     fn get_resolution(&mut self, id: NodeId) -> Option<PathResolution>;
 150
 151     /// We must keep the set of definitions up to date as we add nodes that weren't in the AST.
 152     /// This should only return `None` during testing.
 153     fn definitions(&mut self) -> &mut Definitions;
 154
 155     /// Given suffix ["b","c","d"], creates a HIR path for `[::crate_root]::b::c::d` and resolves
 156     /// it based on `is_value`.
 157     fn resolve_str_path(&mut self, span: Span, crate_root: Option<&str>,
 158                 components: &[&str], is_value: bool) -> hir::Path {
 159         let mut path = hir::Path {
 160             span,
 161             def: Def::Err,
 162             segments: iter::once(keywords::CrateRoot.name()).chain({
 163                 crate_root.into_iter().chain(components.iter().cloned()).map(Symbol::intern)
 164             }).map(hir::PathSegment::from_name).collect(),
 165         };
 166
 167         self.resolve_hir_path(&mut path, is_value);
 168         path
 169     }
 170 }
 171
 172 #[derive(Clone, Copy, Debug)]
 173 enum ImplTraitContext {
 174     /// Treat `impl Trait` as shorthand for a new universal generic parameter.
 175     /// Example: `fn foo(x: impl Debug)`, where `impl Debug` is conceptually
 176     /// equivalent to a fresh universal parameter like `fn foo<T: Debug>(x: T)`.
 177     ///
 178     /// We store a DefId here so we can look up necessary information later
 179     Universal(DefId),
 180
 181     /// Treat `impl Trait` as shorthand for a new universal existential parameter.
 182     /// Example: `fn foo() -> impl Debug`, where `impl Debug` is conceptually
 183     /// equivalent to a fresh existential parameter like `abstract type T; fn foo() -> T`.
 184     Existential,
 185
 186     /// `impl Trait` is not accepted in this position.
 187     Disallowed,
 188 }
 189
 190 pub fn lower_crate(sess: &Session,
 191                    cstore: &CrateStore,
 192                    dep_graph: &DepGraph,
 193                    krate: &Crate,
 194                    resolver: &mut Resolver)
 195                    -> hir::Crate {
 196     // We're constructing the HIR here; we don't care what we will
 197     // read, since we haven't even constructed the *input* to
 198     // incr. comp. yet.
 199     dep_graph.assert_ignored();
 200
 201     LoweringContext {
 202         crate_root: std_inject::injected_crate_name(),
 203         sess,
 204         cstore,
 205         parent_def: None,
 206         resolver,
 207         name_map: FxHashMap(),
 208         items: BTreeMap::new(),
 209         trait_items: BTreeMap::new(),
 210         impl_items: BTreeMap::new(),
 211         bodies: BTreeMap::new(),
 212         trait_impls: BTreeMap::new(),
 213         trait_auto_impl: BTreeMap::new(),
 214         exported_macros: Vec::new(),
 215         catch_scopes: Vec::new(),
 216         loop_scopes: Vec::new(),
 217         is_in_loop_condition: false,
 218         type_def_lifetime_params: DefIdMap(),
 219         current_hir_id_owner: vec![(CRATE_DEF_INDEX, 0)],
 220         item_local_id_counters: NodeMap(),
 221         node_id_to_hir_id: IndexVec::new(),
 222         is_generator: false,
 223         is_in_trait_impl: false,
 224         in_band_ty_params: Vec::new(),
 225         lifetimes_to_define: Vec::new(),
 226         is_collecting_in_band_lifetimes: false,
 227         in_scope_lifetimes: Vec::new(),
 228     }.lower_crate(krate)
 229 }
 230
 231 #[derive(Copy, Clone, PartialEq, Eq)]
 232 enum ParamMode {
 233     /// Any path in a type context.
 234     Explicit,
 235     /// The `module::Type` in `module::Type::method` in an expression.
 236     Optional
 237 }
 238
 239 struct LoweredNodeId {
 240     node_id: NodeId,
 241     hir_id: hir::HirId,
 242 }
 243
 244 enum ParenthesizedGenericArgs {
 245     Ok,
 246     Warn,
 247     Err,
 248 }
 249
 250 impl<'a> LoweringContext<'a> {
 251     fn lower_crate(mut self, c: &Crate) -> hir::Crate {
 252         /// Full-crate AST visitor that inserts into a fresh
 253         /// `LoweringContext` any information that may be
 254         /// needed from arbitrary locations in the crate.
 255         /// E.g. The number of lifetime generic parameters
 256         /// declared for every type and trait definition.
 257         struct MiscCollector<'lcx, 'interner: 'lcx> {
 258             lctx: &'lcx mut LoweringContext<'interner>,
 259         }
 260
 261         impl<'lcx, 'interner> Visitor<'lcx> for MiscCollector<'lcx, 'interner> {
 262             fn visit_item(&mut self, item: &'lcx Item) {
 263                 self.lctx.allocate_hir_id_counter(item.id, item);
 264
 265                 match item.node {
 266                     ItemKind::Struct(_, ref generics) |
 267                     ItemKind::Union(_, ref generics) |
 268                     ItemKind::Enum(_, ref generics) |
 269                     ItemKind::Ty(_, ref generics) |
 270                     ItemKind::Trait(_, _, ref generics, ..) => {
 271                         let def_id = self.lctx.resolver.definitions().local_def_id(item.id);
 272                         let count = generics.params.iter()
 273                             .filter(|param| param.is_lifetime_param())
 274                             .count();
 275                         self.lctx.type_def_lifetime_params.insert(def_id, count);
 276                     }
 277                     _ => {}
 278                 }
 279                 visit::walk_item(self, item);
 280             }
 281
 282             fn visit_trait_item(&mut self, item: &'lcx TraitItem) {
 283                 self.lctx.allocate_hir_id_counter(item.id, item);
 284                 visit::walk_trait_item(self, item);
 285             }
 286
 287             fn visit_impl_item(&mut self, item: &'lcx ImplItem) {
 288                 self.lctx.allocate_hir_id_counter(item.id, item);
 289                 visit::walk_impl_item(self, item);
 290             }
 291         }
 292
 293         struct ItemLowerer<'lcx, 'interner: 'lcx> {
 294             lctx: &'lcx mut LoweringContext<'interner>,
 295         }
 296
 297         impl<'lcx, 'interner> ItemLowerer<'lcx, 'interner> {
 298             fn with_trait_impl_ref<F>(&mut self, trait_impl_ref: &Option<TraitRef>, f: F)
 299                 where F: FnOnce(&mut Self)
 300             {
 301                 let old = self.lctx.is_in_trait_impl;
 302                 self.lctx.is_in_trait_impl = if let &None = trait_impl_ref {
 303                     false
 304                 } else {
 305                     true
 306                 };
 307                 f(self);
 308                 self.lctx.is_in_trait_impl = old;
 309             }
 310         }
 311
 312         impl<'lcx, 'interner> Visitor<'lcx> for ItemLowerer<'lcx, 'interner> {
 313             fn visit_item(&mut self, item: &'lcx Item) {
 314                 let mut item_lowered = true;
 315                 self.lctx.with_hir_id_owner(item.id, |lctx| {
 316                     if let Some(hir_item) = lctx.lower_item(item) {
 317                         lctx.items.insert(item.id, hir_item);
 318                     } else {
 319                         item_lowered = false;
 320                     }
 321                 });
 322
 323                 if item_lowered {
 324                     let item_lifetimes = match self.lctx.items.get(&item.id).unwrap().node {
 325                         hir::Item_::ItemImpl(_,_,_,ref generics,..) |
 326                         hir::Item_::ItemTrait(_,_,ref generics,..) =>
 327                             generics.lifetimes().cloned().collect::<Vec<_>>(),
 328                         _ => Vec::new(),
 329                     };
 330
 331                     self.lctx.with_parent_impl_lifetime_defs(&item_lifetimes, |this| {
 332                         let this = &mut ItemLowerer { lctx: this };
 333                         if let ItemKind::Impl(_,_,_,_,ref opt_trait_ref,_,_) = item.node {
 334                             this.with_trait_impl_ref(opt_trait_ref, |this| {
 335                                 visit::walk_item(this, item)
 336                             });
 337                         } else {
 338                             visit::walk_item(this, item);
 339                         }
 340                     });
 341                 }
 342             }
 343
 344             fn visit_trait_item(&mut self, item: &'lcx TraitItem) {
 345                 self.lctx.with_hir_id_owner(item.id, |lctx| {
 346                     let id = hir::TraitItemId { node_id: item.id };
 347                     let hir_item = lctx.lower_trait_item(item);
 348                     lctx.trait_items.insert(id, hir_item);
 349                 });
 350
 351                 visit::walk_trait_item(self, item);
 352             }
 353
 354             fn visit_impl_item(&mut self, item: &'lcx ImplItem) {
 355                 self.lctx.with_hir_id_owner(item.id, |lctx| {
 356                     let id = hir::ImplItemId { node_id: item.id };
 357                     let hir_item = lctx.lower_impl_item(item);
 358                     lctx.impl_items.insert(id, hir_item);
 359                 });
 360                 visit::walk_impl_item(self, item);
 361             }
 362         }
 363
 364         self.lower_node_id(CRATE_NODE_ID);
 365         debug_assert!(self.node_id_to_hir_id[CRATE_NODE_ID] == hir::CRATE_HIR_ID);
 366
 367         visit::walk_crate(&mut MiscCollector { lctx: &mut self }, c);
 368         visit::walk_crate(&mut ItemLowerer { lctx: &mut self }, c);
 369
 370         let module = self.lower_mod(&c.module);
 371         let attrs = self.lower_attrs(&c.attrs);
 372         let body_ids = body_ids(&self.bodies);
 373
 374         self.resolver
 375             .definitions()
 376             .init_node_id_to_hir_id_mapping(self.node_id_to_hir_id);
 377
 378         hir::Crate {
 379             module,
 380             attrs,
 381             span: c.span,
 382             exported_macros: hir::HirVec::from(self.exported_macros),
 383             items: self.items,
 384             trait_items: self.trait_items,
 385             impl_items: self.impl_items,
 386             bodies: self.bodies,
 387             body_ids,
 388             trait_impls: self.trait_impls,
 389             trait_auto_impl: self.trait_auto_impl,
 390         }
 391     }
 392
 393     fn allocate_hir_id_counter<T: Debug>(&mut self,
 394                                          owner: NodeId,
 395                                          debug: &T) {
 396         if self.item_local_id_counters.insert(owner, 0).is_some() {
 397             bug!("Tried to allocate item_local_id_counter for {:?} twice", debug);
 398         }
 399         // Always allocate the first HirId for the owner itself
 400         self.lower_node_id_with_owner(owner, owner);
 401     }
 402
 403     fn lower_node_id_generic<F>(&mut self,
 404                                 ast_node_id: NodeId,
 405                                 alloc_hir_id: F)
 406                                 -> LoweredNodeId
 407         where F: FnOnce(&mut Self) -> hir::HirId
 408     {
 409         if ast_node_id == DUMMY_NODE_ID {
 410             return LoweredNodeId {
 411                 node_id: DUMMY_NODE_ID,
 412                 hir_id: hir::DUMMY_HIR_ID,
 413             }
 414         }
 415
 416         let min_size = ast_node_id.as_usize() + 1;
 417
 418         if min_size > self.node_id_to_hir_id.len() {
 419             self.node_id_to_hir_id.resize(min_size, hir::DUMMY_HIR_ID);
 420         }
 421
 422         let existing_hir_id = self.node_id_to_hir_id[ast_node_id];
 423
 424         if existing_hir_id == hir::DUMMY_HIR_ID {
 425             // Generate a new HirId
 426             let hir_id = alloc_hir_id(self);
 427             self.node_id_to_hir_id[ast_node_id] = hir_id;
 428             LoweredNodeId {
 429                 node_id: ast_node_id,
 430                 hir_id,
 431             }
 432         } else {
 433             LoweredNodeId {
 434                 node_id: ast_node_id,
 435                 hir_id: existing_hir_id,
 436             }
 437         }
 438     }
 439
 440     fn with_hir_id_owner<F>(&mut self, owner: NodeId, f: F)
 441         where F: FnOnce(&mut Self)
 442     {
 443         let counter = self.item_local_id_counters
 444                           .insert(owner, HIR_ID_COUNTER_LOCKED)
 445                           .unwrap();
 446         let def_index = self.resolver.definitions().opt_def_index(owner).unwrap();
 447         self.current_hir_id_owner.push((def_index, counter));
 448         f(self);
 449         let (new_def_index, new_counter) = self.current_hir_id_owner.pop().unwrap();
 450
 451         debug_assert!(def_index == new_def_index);
 452         debug_assert!(new_counter >= counter);
 453
 454         let prev = self.item_local_id_counters.insert(owner, new_counter).unwrap();
 455         debug_assert!(prev == HIR_ID_COUNTER_LOCKED);
 456     }
 457
 458     /// This method allocates a new HirId for the given NodeId and stores it in
 459     /// the LoweringContext's NodeId => HirId map.
 460     /// Take care not to call this method if the resulting HirId is then not
 461     /// actually used in the HIR, as that would trigger an assertion in the
 462     /// HirIdValidator later on, which makes sure that all NodeIds got mapped
 463     /// properly. Calling the method twice with the same NodeId is fine though.
 464     fn lower_node_id(&mut self, ast_node_id: NodeId) -> LoweredNodeId {
 465         self.lower_node_id_generic(ast_node_id, |this| {
 466             let &mut (def_index, ref mut local_id_counter) = this.current_hir_id_owner
 467                                                                  .last_mut()
 468                                                                  .unwrap();
 469             let local_id = *local_id_counter;
 470             *local_id_counter += 1;
 471             hir::HirId {
 472                 owner: def_index,
 473                 local_id: hir::ItemLocalId(local_id),
 474             }
 475         })
 476     }
 477
 478     fn lower_node_id_with_owner(&mut self,
 479                                 ast_node_id: NodeId,
 480                                 owner: NodeId)
 481                                 -> LoweredNodeId {
 482         self.lower_node_id_generic(ast_node_id, |this| {
 483             let local_id_counter = this.item_local_id_counters
 484                                        .get_mut(&owner)
 485                                        .unwrap();
 486             let local_id = *local_id_counter;
 487
 488             // We want to be sure not to modify the counter in the map while it
 489             // is also on the stack. Otherwise we'll get lost updates when writing
 490             // back from the stack to the map.
 491             debug_assert!(local_id != HIR_ID_COUNTER_LOCKED);
 492
 493             *local_id_counter += 1;
 494             let def_index = this.resolver.definitions().opt_def_index(owner).unwrap();
 495
 496             hir::HirId {
 497                 owner: def_index,
 498                 local_id: hir::ItemLocalId(local_id),
 499             }
 500         })
 501     }
 502
 503     fn record_body(&mut self, value: hir::Expr, decl: Option<&FnDecl>)
 504                    -> hir::BodyId {
 505         let body = hir::Body {
 506             arguments: decl.map_or(hir_vec![], |decl| {
 507                 decl.inputs.iter().map(|x| self.lower_arg(x)).collect()
 508             }),
 509             is_generator: self.is_generator,
 510             value,
 511         };
 512         let id = body.id();
 513         self.bodies.insert(id, body);
 514         id
 515     }
 516
 517     fn next_id(&mut self) -> LoweredNodeId {
 518         self.lower_node_id(self.sess.next_node_id())
 519     }
 520
 521     fn expect_full_def(&mut self, id: NodeId) -> Def {
 522         self.resolver.get_resolution(id).map_or(Def::Err, |pr| {
 523             if pr.unresolved_segments() != 0 {
 524                 bug!("path not fully resolved: {:?}", pr);
 525             }
 526             pr.base_def()
 527         })
 528     }
 529
 530     fn diagnostic(&self) -> &errors::Handler {
 531         self.sess.diagnostic()
 532     }
 533
 534     fn str_to_ident(&self, s: &'static str) -> Name {
 535         Symbol::gensym(s)
 536     }
 537
 538     fn allow_internal_unstable(&self, reason: CompilerDesugaringKind, span: Span) -> Span
 539     {
 540         let mark = Mark::fresh(Mark::root());
 541         mark.set_expn_info(codemap::ExpnInfo {
 542             call_site: span,
 543             callee: codemap::NameAndSpan {
 544                 format: codemap::CompilerDesugaring(reason),
 545                 span: Some(span),
 546                 allow_internal_unstable: true,
 547                 allow_internal_unsafe: false,
 548             },
 549         });
 550         span.with_ctxt(SyntaxContext::empty().apply_mark(mark))
 551     }
 552
 553     // Creates a new hir::GenericParam for every new lifetime and type parameter
 554     // encountered while evaluating `f`. Definitions are created with the parent
 555     // provided. If no `parent_id` is provided, no definitions will be returned.
 556     fn collect_in_band_defs<T, F>(
 557         &mut self,
 558         parent_id: Option<DefId>,
 559         f: F
 560     ) -> (Vec<hir::GenericParam>, T) where F: FnOnce(&mut LoweringContext) -> T
 561     {
 562         assert!(!self.is_collecting_in_band_lifetimes);
 563         assert!(self.lifetimes_to_define.is_empty());
 564         self.is_collecting_in_band_lifetimes = self.sess.features.borrow().in_band_lifetimes;
 565
 566         assert!(self.in_band_ty_params.is_empty());
 567
 568         let res = f(self);
 569
 570         self.is_collecting_in_band_lifetimes = false;
 571
 572         let in_band_ty_params = self.in_band_ty_params.split_off(0);
 573         let lifetimes_to_define = self.lifetimes_to_define.split_off(0);
 574
 575         let mut params = match parent_id {
 576             Some(parent_id) => lifetimes_to_define.into_iter().map(|(span, name)| {
 577                     let def_node_id = self.next_id().node_id;
 578
 579                     // Add a definition for the in-band lifetime def
 580                     self.resolver.definitions().create_def_with_parent(
 581                         parent_id.index,
 582                         def_node_id,
 583                         DefPathData::LifetimeDef(name.as_str()),
 584                         DefIndexAddressSpace::High,
 585                         Mark::root()
 586                     );
 587
 588                     hir::GenericParam::Lifetime(hir::LifetimeDef {
 589                         lifetime: hir::Lifetime {
 590                             id: def_node_id,
 591                             span,
 592                             name: hir::LifetimeName::Name(name),
 593                         },
 594                         bounds: Vec::new().into(),
 595                         pure_wrt_drop: false,
 596                         in_band: true,
 597                     })
 598                 }).collect(),
 599             None => Vec::new(),
 600         };
 601
 602         params.extend(in_band_ty_params.into_iter().map(|tp| hir::GenericParam::Type(tp)));
 603
 604         (params, res)
 605     }
 606
 607     // Evaluates `f` with the lifetimes in `lt_defs` in-scope.
 608     // This is used to track which lifetimes have already been defined, and
 609     // which are new in-band lifetimes that need to have a definition created
 610     // for them.
 611     fn with_in_scope_lifetime_defs<T, F>(
 612         &mut self,
 613         lt_defs: &[LifetimeDef],
 614         f: F
 615     ) -> T where F: FnOnce(&mut LoweringContext) -> T
 616     {
 617         let old_len = self.in_scope_lifetimes.len();
 618         let lt_def_names = lt_defs.iter().map(|lt_def| lt_def.lifetime.ident.name);
 619         self.in_scope_lifetimes.extend(lt_def_names);
 620
 621         let res = f(self);
 622
 623         self.in_scope_lifetimes.truncate(old_len);
 624         res
 625     }
 626
 627     // Same as the method above, but accepts `hir::LifetimeDef`s
 628     // instead of `ast::LifetimeDef`s.
 629     // This should only be used with generics that have already had their
 630     // in-band lifetimes added. In practice, this means that this function is
 631     // only used when lowering a child item of a trait or impl.
 632     fn with_parent_impl_lifetime_defs<T, F>(
 633         &mut self,
 634         lt_defs: &[hir::LifetimeDef],
 635         f: F
 636     ) -> T where F: FnOnce(&mut LoweringContext) -> T
 637     {
 638         let old_len = self.in_scope_lifetimes.len();
 639         let lt_def_names = lt_defs.iter().map(|lt_def| lt_def.lifetime.name.name());
 640         self.in_scope_lifetimes.extend(lt_def_names);
 641
 642         let res = f(self);
 643
 644         self.in_scope_lifetimes.truncate(old_len);
 645         res
 646     }
 647
 648     // Appends in-band lifetime defs and argument-position `impl Trait` defs
 649     // to the existing set of generics.
 650     fn add_in_band_defs<F, T>(
 651         &mut self,
 652         generics: &Generics,
 653         parent_id: Option<DefId>,
 654         f: F
 655     ) -> (hir::Generics, T)
 656         where F: FnOnce(&mut LoweringContext) -> T
 657     {
 658         let (in_band_defs, (mut lowered_generics, res)) =
 659             self.with_in_scope_lifetime_defs(
 660                 &generics.params
 661                     .iter()
 662                     .filter_map(|p| match *p {
 663                         GenericParam::Lifetime(ref ld) => Some(ld.clone()),
 664                         _ => None,
 665                     })
 666                     .collect::<Vec<_>>(),
 667                 |this| {
 668                     this.collect_in_band_defs(parent_id, |this| {
 669                         (this.lower_generics(generics), f(this))
 670                     })
 671                 }
 672             );
 673
 674         lowered_generics.params =
 675             lowered_generics.params.iter().cloned().chain(in_band_defs).collect();
 676
 677         (lowered_generics, res)
 678     }
 679
 680     fn with_catch_scope<T, F>(&mut self, catch_id: NodeId, f: F) -> T
 681         where F: FnOnce(&mut LoweringContext) -> T
 682     {
 683         let len = self.catch_scopes.len();
 684         self.catch_scopes.push(catch_id);
 685
 686         let result = f(self);
 687         assert_eq!(len + 1, self.catch_scopes.len(),
 688             "catch scopes should be added and removed in stack order");
 689
 690         self.catch_scopes.pop().unwrap();
 691
 692         result
 693     }
 694
 695     fn lower_body<F>(&mut self, decl: Option<&FnDecl>, f: F) -> hir::BodyId
 696         where F: FnOnce(&mut LoweringContext) -> hir::Expr
 697     {
 698         let prev = mem::replace(&mut self.is_generator, false);
 699         let result = f(self);
 700         let r = self.record_body(result, decl);
 701         self.is_generator = prev;
 702         return r
 703     }
 704
 705     fn with_loop_scope<T, F>(&mut self, loop_id: NodeId, f: F) -> T
 706         where F: FnOnce(&mut LoweringContext) -> T
 707     {
 708         // We're no longer in the base loop's condition; we're in another loop.
 709         let was_in_loop_condition = self.is_in_loop_condition;
 710         self.is_in_loop_condition = false;
 711
 712         let len = self.loop_scopes.len();
 713         self.loop_scopes.push(loop_id);
 714
 715         let result = f(self);
 716         assert_eq!(len + 1, self.loop_scopes.len(),
 717             "Loop scopes should be added and removed in stack order");
 718
 719         self.loop_scopes.pop().unwrap();
 720
 721         self.is_in_loop_condition = was_in_loop_condition;
 722
 723         result
 724     }
 725
 726     fn with_loop_condition_scope<T, F>(&mut self, f: F) -> T
 727         where F: FnOnce(&mut LoweringContext) -> T
 728     {
 729         let was_in_loop_condition = self.is_in_loop_condition;
 730         self.is_in_loop_condition = true;
 731
 732         let result = f(self);
 733
 734         self.is_in_loop_condition = was_in_loop_condition;
 735
 736         result
 737     }
 738
 739     fn with_new_scopes<T, F>(&mut self, f: F) -> T
 740         where F: FnOnce(&mut LoweringContext) -> T
 741     {
 742         let was_in_loop_condition = self.is_in_loop_condition;
 743         self.is_in_loop_condition = false;
 744
 745         let catch_scopes = mem::replace(&mut self.catch_scopes, Vec::new());
 746         let loop_scopes = mem::replace(&mut self.loop_scopes, Vec::new());
 747         let result = f(self);
 748         self.catch_scopes = catch_scopes;
 749         self.loop_scopes = loop_scopes;
 750
 751         self.is_in_loop_condition = was_in_loop_condition;
 752
 753         result
 754     }
 755
 756     fn with_parent_def<T, F>(&mut self, parent_id: NodeId, f: F) -> T
 757         where F: FnOnce(&mut LoweringContext) -> T
 758     {
 759         let old_def = self.parent_def;
 760         self.parent_def = {
 761             let defs = self.resolver.definitions();
 762             Some(defs.opt_def_index(parent_id).unwrap())
 763         };
 764
 765         let result = f(self);
 766
 767         self.parent_def = old_def;
 768         result
 769     }
 770
 771     fn def_key(&mut self, id: DefId) -> DefKey {
 772         if id.is_local() {
 773             self.resolver.definitions().def_key(id.index)
 774         } else {
 775             self.cstore.def_key(id)
 776         }
 777     }
 778
 779     fn lower_ident(&mut self, ident: Ident) -> Name {
 780         let ident = ident.modern();
 781         if ident.ctxt == SyntaxContext::empty() {
 782             return ident.name;
 783         }
 784         *self.name_map.entry(ident).or_insert_with(|| Symbol::from_ident(ident))
 785     }
 786
 787     fn lower_opt_sp_ident(&mut self, o_id: Option<Spanned<Ident>>) -> Option<Spanned<Name>> {
 788         o_id.map(|sp_ident| respan(sp_ident.span, sp_ident.node.name))
 789     }
 790
 791     fn lower_loop_destination(&mut self, destination: Option<(NodeId, Spanned<Ident>)>)
 792         -> hir::Destination
 793     {
 794         match destination {
 795             Some((id, label_ident)) => {
 796                 let target = if let Def::Label(loop_id) = self.expect_full_def(id) {
 797                     hir::LoopIdResult::Ok(self.lower_node_id(loop_id).node_id)
 798                 } else {
 799                     hir::LoopIdResult::Err(hir::LoopIdError::UnresolvedLabel)
 800                 };
 801                 hir::Destination {
 802                     ident: Some(label_ident),
 803                     target_id: hir::ScopeTarget::Loop(target),
 804                 }
 805             },
 806             None => {
 807                 let loop_id = self.loop_scopes
 808                                   .last()
 809                                   .map(|innermost_loop_id| *innermost_loop_id);
 810
 811                 hir::Destination {
 812                     ident: None,
 813                     target_id: hir::ScopeTarget::Loop(
 814                         loop_id.map(|id| Ok(self.lower_node_id(id).node_id))
 815                                .unwrap_or(Err(hir::LoopIdError::OutsideLoopScope))
 816                                .into())
 817                 }
 818             }
 819         }
 820     }
 821
 822     fn lower_attrs(&mut self, attrs: &Vec<Attribute>) -> hir::HirVec<Attribute> {
 823         attrs.iter().map(|a| self.lower_attr(a)).collect::<Vec<_>>().into()
 824     }
 825
 826     fn lower_attr(&mut self, attr: &Attribute) -> Attribute {
 827         Attribute {
 828             id: attr.id,
 829             style: attr.style,
 830             path: attr.path.clone(),
 831             tokens: self.lower_token_stream(attr.tokens.clone()),
 832             is_sugared_doc: attr.is_sugared_doc,
 833             span: attr.span,
 834         }
 835     }
 836
 837     fn lower_token_stream(&mut self, tokens: TokenStream) -> TokenStream {
 838         tokens.into_trees()
 839             .flat_map(|tree| self.lower_token_tree(tree).into_trees())
 840             .collect()
 841     }
 842
 843     fn lower_token_tree(&mut self, tree: TokenTree) -> TokenStream {
 844         match tree {
 845             TokenTree::Token(span, token) => {
 846                 self.lower_token(token, span)
 847             }
 848             TokenTree::Delimited(span, delimited) => {
 849                 TokenTree::Delimited(span, Delimited {
 850                     delim: delimited.delim,
 851                     tts: self.lower_token_stream(delimited.tts.into()).into(),
 852                 }).into()
 853             }
 854         }
 855     }
 856
 857     fn lower_token(&mut self, token: Token, span: Span) -> TokenStream {
 858         match token {
 859             Token::Interpolated(_) => {}
 860             other => return TokenTree::Token(span, other).into(),
 861         }
 862
 863         let tts = token.interpolated_to_tokenstream(&self.sess.parse_sess, span);
 864         self.lower_token_stream(tts)
 865     }
 866
 867     fn lower_arm(&mut self, arm: &Arm) -> hir::Arm {
 868         hir::Arm {
 869             attrs: self.lower_attrs(&arm.attrs),
 870             pats: arm.pats.iter().map(|x| self.lower_pat(x)).collect(),
 871             guard: arm.guard.as_ref().map(|ref x| P(self.lower_expr(x))),
 872             body: P(self.lower_expr(&arm.body)),
 873         }
 874     }
 875
 876     fn lower_ty_binding(&mut self, b: &TypeBinding, itctx: ImplTraitContext) -> hir::TypeBinding {
 877         hir::TypeBinding {
 878             id: self.lower_node_id(b.id).node_id,
 879             name: self.lower_ident(b.ident),
 880             ty: self.lower_ty(&b.ty, itctx),
 881             span: b.span,
 882         }
 883     }
 884
 885     fn lower_ty(&mut self, t: &Ty, itctx: ImplTraitContext) -> P<hir::Ty> {
 886         let kind = match t.node {
 887             TyKind::Infer => hir::TyInfer,
 888             TyKind::Err => hir::TyErr,
 889             TyKind::Slice(ref ty) => hir::TySlice(self.lower_ty(ty, itctx)),
 890             TyKind::Ptr(ref mt) => hir::TyPtr(self.lower_mt(mt, itctx)),
 891             TyKind::Rptr(ref region, ref mt) => {
 892                 let span = t.span.with_hi(t.span.lo());
 893                 let lifetime = match *region {
 894                     Some(ref lt) => self.lower_lifetime(lt),
 895                     None => self.elided_lifetime(span)
 896                 };
 897                 hir::TyRptr(lifetime, self.lower_mt(mt, itctx))
 898             }
 899             TyKind::BareFn(ref f) => {
 900                 self.with_in_scope_lifetime_defs(
 901                     &f.generic_params
 902                         .iter()
 903                         .filter_map(|p| match *p {
 904                             GenericParam::Lifetime(ref ld) => Some(ld.clone()),
 905                             _ => None,
 906                         })
 907                         .collect::<Vec<_>>(),
 908                     |this| hir::TyBareFn(P(hir::BareFnTy {
 909                         generic_params: this.lower_generic_params(&f.generic_params, &NodeMap()),
 910                         unsafety: this.lower_unsafety(f.unsafety),
 911                         abi: f.abi,
 912                         decl: this.lower_fn_decl(&f.decl, None, false),
 913                         arg_names: this.lower_fn_args_to_names(&f.decl),
 914                     })))
 915             }
 916             TyKind::Never => hir::TyNever,
 917             TyKind::Tup(ref tys) => {
 918                 hir::TyTup(tys.iter().map(|ty| self.lower_ty(ty, itctx)).collect())
 919             }
 920             TyKind::Paren(ref ty) => {
 921                 return self.lower_ty(ty, itctx);
 922             }
 923             TyKind::Path(ref qself, ref path) => {
 924                 let id = self.lower_node_id(t.id);
 925                 let qpath = self.lower_qpath(t.id, qself, path, ParamMode::Explicit, itctx);
 926                 return self.ty_path(id, t.span, qpath);
 927             }
 928             TyKind::ImplicitSelf => {
 929                 hir::TyPath(hir::QPath::Resolved(None, P(hir::Path {
 930                     def: self.expect_full_def(t.id),
 931                     segments: hir_vec![
 932                         hir::PathSegment::from_name(keywords::SelfType.name())
 933                     ],
 934                     span: t.span,
 935                 })))
 936             }
 937             TyKind::Array(ref ty, ref length) => {
 938                 let length = self.lower_body(None, |this| this.lower_expr(length));
 939                 hir::TyArray(self.lower_ty(ty, itctx), length)
 940             }
 941             TyKind::Typeof(ref expr) => {
 942                 let expr = self.lower_body(None, |this| this.lower_expr(expr));
 943                 hir::TyTypeof(expr)
 944             }
 945             TyKind::TraitObject(ref bounds, ..) => {
 946                 let mut lifetime_bound = None;
 947                 let bounds = bounds.iter().filter_map(|bound| {
 948                     match *bound {
 949                         TraitTyParamBound(ref ty, TraitBoundModifier::None) => {
 950                             Some(self.lower_poly_trait_ref(ty, itctx))
 951                         }
 952                         TraitTyParamBound(_, TraitBoundModifier::Maybe) => None,
 953                         RegionTyParamBound(ref lifetime) => {
 954                             if lifetime_bound.is_none() {
 955                                 lifetime_bound = Some(self.lower_lifetime(lifetime));
 956                             }
 957                             None
 958                         }
 959                     }
 960                 }).collect();
 961                 let lifetime_bound = lifetime_bound.unwrap_or_else(|| {
 962                     self.elided_lifetime(t.span)
 963                 });
 964                 hir::TyTraitObject(bounds, lifetime_bound)
 965             }
 966             TyKind::ImplTrait(ref bounds) => {
 967                 use syntax::feature_gate::{emit_feature_err, GateIssue};
 968                 let span = t.span;
 969                 match itctx {
 970                     ImplTraitContext::Existential => {
 971                         let has_feature = self.sess.features.borrow().conservative_impl_trait;
 972                         if !t.span.allows_unstable() && !has_feature {
 973                             emit_feature_err(&self.sess.parse_sess, "conservative_impl_trait",
 974                                              t.span, GateIssue::Language,
 975                                              "`impl Trait` in return position is experimental");
 976                         }
 977                         let def_index = self.resolver.definitions().opt_def_index(t.id).unwrap();
 978                         let hir_bounds = self.lower_bounds(bounds, itctx);
 979                         let (lifetimes, lifetime_defs) =
 980                             self.lifetimes_from_impl_trait_bounds(def_index, &hir_bounds);
 981
 982                         hir::TyImplTraitExistential(hir::ExistTy {
 983                             generics: hir::Generics {
 984                                 params: lifetime_defs,
 985                                 where_clause: hir::WhereClause {
 986                                     id: self.next_id().node_id,
 987                                     predicates: Vec::new().into(),
 988                                 },
 989                                 span,
 990                             },
 991                             bounds: hir_bounds,
 992                         }, lifetimes)
 993                     },
 994                     ImplTraitContext::Universal(def_id) => {
 995                         let has_feature = self.sess.features.borrow().universal_impl_trait;
 996                         if !t.span.allows_unstable() && !has_feature {
 997                             emit_feature_err(&self.sess.parse_sess, "universal_impl_trait",
 998                                              t.span, GateIssue::Language,
 999                                              "`impl Trait` in argument position is experimental");
1000                         }
1001
1002                         let def_node_id = self.next_id().node_id;
1003
1004                         // Add a definition for the in-band TyParam
1005                         let def_index = self.resolver.definitions().create_def_with_parent(
1006                             def_id.index,
1007                             def_node_id,
1008                             DefPathData::ImplTrait,
1009                             DefIndexAddressSpace::High,
1010                             Mark::root()
1011                         );
1012
1013                         let hir_bounds = self.lower_bounds(bounds, itctx);
1014                         // Set the name to `impl Bound1 + Bound2`
1015                         let name = Symbol::intern(&pprust::ty_to_string(t));
1016                         self.in_band_ty_params.push(hir::TyParam {
1017                             name,
1018                             id: def_node_id,
1019                             bounds: hir_bounds,
1020                             default: None,
1021                             span,
1022                             pure_wrt_drop: false,
1023                             synthetic: Some(hir::SyntheticTyParamKind::ImplTrait),
1024                         });
1025
1026                         hir::TyPath(hir::QPath::Resolved(None, P(hir::Path {
1027                             span,
1028                             def: Def::TyParam(DefId::local(def_index)),
1029                             segments: hir_vec![hir::PathSegment::from_name(name)],
1030                         })))
1031                     },
1032                     ImplTraitContext::Disallowed => {
1033                         span_err!(self.sess, t.span, E0562,
1034                                   "`impl Trait` not allowed outside of function \
1035                                   and inherent method return types");
1036                         hir::TyErr
1037                     }
1038                 }
1039             }
1040             TyKind::Mac(_) => panic!("TyMac should have been expanded by now."),
1041         };
1042
1043         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(t.id);
1044         P(hir::Ty {
1045             id: node_id,
1046             node: kind,
1047             span: t.span,
1048             hir_id,
1049         })
1050     }
1051
1052     fn lifetimes_from_impl_trait_bounds(
1053         &mut self,
1054         parent_index: DefIndex,
1055         bounds: &hir::TyParamBounds
1056     ) -> (HirVec<hir::Lifetime>, HirVec<hir::GenericParam>) {
1057
1058         // This visitor walks over impl trait bounds and creates defs for all lifetimes which
1059         // appear in the bounds, excluding lifetimes that are created within the bounds.
1060         // e.g. 'a, 'b, but not 'c in `impl for<'c> SomeTrait<'a, 'b, 'c>`
1061         struct ImplTraitLifetimeCollector<'r, 'a: 'r> {
1062             context: &'r mut LoweringContext<'a>,
1063             parent: DefIndex,
1064             collect_elided_lifetimes: bool,
1065             currently_bound_lifetimes: Vec<hir::LifetimeName>,
1066             already_defined_lifetimes: HashSet<hir::LifetimeName>,
1067             output_lifetimes: Vec<hir::Lifetime>,
1068             output_lifetime_params: Vec<hir::GenericParam>,
1069         }
1070
1071         impl<'r, 'a: 'r, 'v> hir::intravisit::Visitor<'v> for ImplTraitLifetimeCollector<'r, 'a> {
1072             fn nested_visit_map<'this>(&'this mut self)
1073                 -> hir::intravisit::NestedVisitorMap<'this, 'v> {
1074                 hir::intravisit::NestedVisitorMap::None
1075             }
1076
1077             fn visit_path_parameters(&mut self, span: Span, parameters: &'v hir::PathParameters) {
1078                 // Don't collect elided lifetimes used inside of `Fn()` syntax.
1079                 if parameters.parenthesized {
1080                     let old_collect_elided_lifetimes = self.collect_elided_lifetimes;
1081                     self.collect_elided_lifetimes = false;
1082                     hir::intravisit::walk_path_parameters(self, span, parameters);
1083                     self.collect_elided_lifetimes = old_collect_elided_lifetimes;
1084                 } else {
1085                     hir::intravisit::walk_path_parameters(self, span, parameters);
1086                 }
1087             }
1088
1089             fn visit_ty(&mut self, t: &'v hir::Ty) {
1090                 // Don't collect elided lifetimes used inside of `fn()` syntax
1091                 if let &hir::Ty_::TyBareFn(_) = &t.node {
1092                     let old_collect_elided_lifetimes = self.collect_elided_lifetimes;
1093                     self.collect_elided_lifetimes = false;
1094                     hir::intravisit::walk_ty(self, t);
1095                     self.collect_elided_lifetimes = old_collect_elided_lifetimes;
1096                 } else {
1097                     hir::intravisit::walk_ty(self, t);
1098                 }
1099             }
1100
1101             fn visit_poly_trait_ref(&mut self,
1102                                     polytr: &'v hir::PolyTraitRef,
1103                                     _: hir::TraitBoundModifier) {
1104                 let old_len = self.currently_bound_lifetimes.len();
1105
1106                 // Record the introduction of 'a in `for<'a> ...`
1107                 for param in &polytr.bound_generic_params {
1108                     if let hir::GenericParam::Lifetime(ref lt_def) = *param {
1109                         // Introduce lifetimes one at a time so that we can handle
1110                         // cases like `fn foo<'d>() -> impl for<'a, 'b: 'a, 'c: 'b + 'd>`
1111                         self.currently_bound_lifetimes.push(lt_def.lifetime.name);
1112
1113                         // Visit the lifetime bounds
1114                         for lt_bound in &lt_def.bounds {
1115                             self.visit_lifetime(&lt_bound);
1116                         }
1117                     }
1118                 }
1119
1120                 hir::intravisit::walk_trait_ref(self, &polytr.trait_ref);
1121
1122                 self.currently_bound_lifetimes.truncate(old_len);
1123             }
1124
1125             fn visit_lifetime(&mut self, lifetime: &'v hir::Lifetime) {
1126                 let name = match lifetime.name {
1127                     hir::LifetimeName::Implicit |
1128                     hir::LifetimeName::Underscore =>
1129                         if self.collect_elided_lifetimes {
1130                             // Use `'_` for both implicit and underscore lifetimes in
1131                             // `abstract type Foo<'_>: SomeTrait<'_>;`
1132                             hir::LifetimeName::Underscore
1133                         } else {
1134                             return
1135                         }
1136                     name @ hir::LifetimeName::Name(_) => name,
1137                     hir::LifetimeName::Static => return,
1138                 };
1139
1140                 if !self.currently_bound_lifetimes.contains(&name) &&
1141                    !self.already_defined_lifetimes.contains(&name)
1142                 {
1143                     self.already_defined_lifetimes.insert(name);
1144
1145                     self.output_lifetimes.push(hir::Lifetime {
1146                         id: self.context.next_id().node_id,
1147                         span: lifetime.span,
1148                         name,
1149                     });
1150
1151                     let def_node_id = self.context.next_id().node_id;
1152                     self.context.resolver.definitions().create_def_with_parent(
1153                         self.parent,
1154                         def_node_id,
1155                         DefPathData::LifetimeDef(name.name().as_str()),
1156                         DefIndexAddressSpace::High,
1157                         Mark::root()
1158                     );
1159                     let def_lifetime = hir::Lifetime {
1160                         id: def_node_id,
1161                         span: lifetime.span,
1162                         name: name,
1163                     };
1164                     self.output_lifetime_params.push(hir::GenericParam::Lifetime(hir::LifetimeDef {
1165                         lifetime: def_lifetime,
1166                         bounds: Vec::new().into(),
1167                         pure_wrt_drop: false,
1168                         in_band: false,
1169                     }));
1170                 }
1171             }
1172         }
1173
1174         let mut lifetime_collector = ImplTraitLifetimeCollector {
1175             context: self,
1176             parent: parent_index,
1177             collect_elided_lifetimes: true,
1178             currently_bound_lifetimes: Vec::new(),
1179             already_defined_lifetimes: HashSet::new(),
1180             output_lifetimes: Vec::new(),
1181             output_lifetime_params: Vec::new(),
1182         };
1183
1184         for bound in bounds {
1185             hir::intravisit::walk_ty_param_bound(&mut lifetime_collector, &bound);
1186         }
1187
1188         (
1189             lifetime_collector.output_lifetimes.into(),
1190             lifetime_collector.output_lifetime_params.into()
1191         )
1192     }
1193
1194     fn lower_foreign_mod(&mut self, fm: &ForeignMod) -> hir::ForeignMod {
1195         hir::ForeignMod {
1196             abi: fm.abi,
1197             items: fm.items.iter().map(|x| self.lower_foreign_item(x)).collect(),
1198         }
1199     }
1200
1201     fn lower_global_asm(&mut self, ga: &GlobalAsm) -> P<hir::GlobalAsm> {
1202         P(hir::GlobalAsm {
1203             asm: ga.asm,
1204             ctxt: ga.ctxt,
1205         })
1206     }
1207
1208     fn lower_variant(&mut self, v: &Variant) -> hir::Variant {
1209         Spanned {
1210             node: hir::Variant_ {
1211                 name: v.node.name.name,
1212                 attrs: self.lower_attrs(&v.node.attrs),
1213                 data: self.lower_variant_data(&v.node.data),
1214                 disr_expr: v.node.disr_expr.as_ref().map(|e| {
1215                     self.lower_body(None, |this| this.lower_expr(e))
1216                 }),
1217             },
1218             span: v.span,
1219         }
1220     }
1221
1222     fn lower_qpath(&mut self,
1223                    id: NodeId,
1224                    qself: &Option<QSelf>,
1225                    p: &Path,
1226                    param_mode: ParamMode,
1227                    itctx: ImplTraitContext)
1228                    -> hir::QPath {
1229         let qself_position = qself.as_ref().map(|q| q.position);
1230         let qself = qself.as_ref().map(|q| self.lower_ty(&q.ty, itctx));
1231
1232         let resolution = self.resolver.get_resolution(id)
1233                                       .unwrap_or(PathResolution::new(Def::Err));
1234
1235         let proj_start = p.segments.len() - resolution.unresolved_segments();
1236         let path = P(hir::Path {
1237             def: resolution.base_def(),
1238             segments: p.segments[..proj_start].iter().enumerate().map(|(i, segment)| {
1239                 let param_mode = match (qself_position, param_mode) {
1240                     (Some(j), ParamMode::Optional) if i < j => {
1241                         // This segment is part of the trait path in a
1242                         // qualified path - one of `a`, `b` or `Trait`
1243                         // in `<X as a::b::Trait>::T::U::method`.
1244                         ParamMode::Explicit
1245                     }
1246                     _ => param_mode
1247                 };
1248
1249                 // Figure out if this is a type/trait segment,
1250                 // which may need lifetime elision performed.
1251                 let parent_def_id = |this: &mut Self, def_id: DefId| {
1252                     DefId {
1253                         krate: def_id.krate,
1254                         index: this.def_key(def_id).parent.expect("missing parent")
1255                     }
1256                 };
1257                 let type_def_id = match resolution.base_def() {
1258                     Def::AssociatedTy(def_id) if i + 2 == proj_start => {
1259                         Some(parent_def_id(self, def_id))
1260                     }
1261                     Def::Variant(def_id) if i + 1 == proj_start => {
1262                         Some(parent_def_id(self, def_id))
1263                     }
1264                     Def::Struct(def_id) |
1265                     Def::Union(def_id) |
1266                     Def::Enum(def_id) |
1267                     Def::TyAlias(def_id) |
1268                     Def::Trait(def_id) if i + 1 == proj_start => Some(def_id),
1269                     _ => None
1270                 };
1271                 let parenthesized_generic_args = match resolution.base_def() {
1272                     // `a::b::Trait(Args)`
1273                     Def::Trait(..) if i + 1 == proj_start => ParenthesizedGenericArgs::Ok,
1274                     // `a::b::Trait(Args)::TraitItem`
1275                     Def::Method(..) |
1276                     Def::AssociatedConst(..) |
1277                     Def::AssociatedTy(..) if i + 2 == proj_start => ParenthesizedGenericArgs::Ok,
1278                     // Avoid duplicated errors
1279                     Def::Err => ParenthesizedGenericArgs::Ok,
1280                     // An error
1281                     Def::Struct(..) | Def::Enum(..) | Def::Union(..) | Def::TyAlias(..) |
1282                     Def::Variant(..) if i + 1 == proj_start => ParenthesizedGenericArgs::Err,
1283                     // A warning for now, for compatibility reasons
1284                     _ => ParenthesizedGenericArgs::Warn,
1285                 };
1286
1287                 let num_lifetimes = type_def_id.map_or(0, |def_id| {
1288                     if let Some(&n) = self.type_def_lifetime_params.get(&def_id) {
1289                         return n;
1290                     }
1291                     assert!(!def_id.is_local());
1292                     let n = self.cstore
1293                                 .item_generics_cloned_untracked(def_id, self.sess)
1294                                 .regions
1295                                 .len();
1296                     self.type_def_lifetime_params.insert(def_id, n);
1297                     n
1298                 });
1299                 self.lower_path_segment(p.span, segment, param_mode, num_lifetimes,
1300                                         parenthesized_generic_args, itctx)
1301             }).collect(),
1302             span: p.span,
1303         });
1304
1305         // Simple case, either no projections, or only fully-qualified.
1306         // E.g. `std::mem::size_of` or `<I as Iterator>::Item`.
1307         if resolution.unresolved_segments() == 0 {
1308             return hir::QPath::Resolved(qself, path);
1309         }
1310
1311         // Create the innermost type that we're projecting from.
1312         let mut ty = if path.segments.is_empty() {
1313             // If the base path is empty that means there exists a
1314             // syntactical `Self`, e.g. `&i32` in `<&i32>::clone`.
1315             qself.expect("missing QSelf for <T>::...")
1316         } else {
1317             // Otherwise, the base path is an implicit `Self` type path,
1318             // e.g. `Vec` in `Vec::new` or `<I as Iterator>::Item` in
1319             // `<I as Iterator>::Item::default`.
1320             let new_id = self.next_id();
1321             self.ty_path(new_id, p.span, hir::QPath::Resolved(qself, path))
1322         };
1323
1324         // Anything after the base path are associated "extensions",
1325         // out of which all but the last one are associated types,
1326         // e.g. for `std::vec::Vec::<T>::IntoIter::Item::clone`:
1327         // * base path is `std::vec::Vec<T>`
1328         // * "extensions" are `IntoIter`, `Item` and `clone`
1329         // * type nodes are:
1330         //   1. `std::vec::Vec<T>` (created above)
1331         //   2. `<std::vec::Vec<T>>::IntoIter`
1332         //   3. `<<std::vec::Vec<T>>::IntoIter>::Item`
1333         // * final path is `<<<std::vec::Vec<T>>::IntoIter>::Item>::clone`
1334         for (i, segment) in p.segments.iter().enumerate().skip(proj_start) {
1335             let segment = P(self.lower_path_segment(p.span, segment, param_mode, 0,
1336                                                     ParenthesizedGenericArgs::Warn,
1337                                                     itctx));
1338             let qpath = hir::QPath::TypeRelative(ty, segment);
1339
1340             // It's finished, return the extension of the right node type.
1341             if i == p.segments.len() - 1 {
1342                 return qpath;
1343             }
1344
1345             // Wrap the associated extension in another type node.
1346             let new_id = self.next_id();
1347             ty = self.ty_path(new_id, p.span, qpath);
1348         }
1349
1350         // Should've returned in the for loop above.
1351         span_bug!(p.span, "lower_qpath: no final extension segment in {}..{}",
1352                   proj_start, p.segments.len())
1353     }
1354
1355     fn lower_path_extra(&mut self,
1356                         id: NodeId,
1357                         p: &Path,
1358                         name: Option<Name>,
1359                         param_mode: ParamMode,
1360                         defaults_to_global: bool)
1361                         -> hir::Path {
1362         let mut segments = p.segments.iter();
1363         if defaults_to_global && p.is_global() {
1364             segments.next();
1365         }
1366
1367         hir::Path {
1368             def: self.expect_full_def(id),
1369             segments: segments.map(|segment| {
1370                 self.lower_path_segment(p.span, segment, param_mode, 0,
1371                                         ParenthesizedGenericArgs::Err,
1372                                         ImplTraitContext::Disallowed)
1373             }).chain(name.map(|name| hir::PathSegment::from_name(name)))
1374               .collect(),
1375             span: p.span,
1376         }
1377     }
1378
1379     fn lower_path(&mut self,
1380                   id: NodeId,
1381                   p: &Path,
1382                   param_mode: ParamMode,
1383                   defaults_to_global: bool)
1384                   -> hir::Path {
1385         self.lower_path_extra(id, p, None, param_mode, defaults_to_global)
1386     }
1387
1388     fn lower_path_segment(&mut self,
1389                           path_span: Span,
1390                           segment: &PathSegment,
1391                           param_mode: ParamMode,
1392                           expected_lifetimes: usize,
1393                           parenthesized_generic_args: ParenthesizedGenericArgs,
1394                           itctx: ImplTraitContext)
1395                           -> hir::PathSegment {
1396         let (mut parameters, infer_types) = if let Some(ref parameters) = segment.parameters {
1397             let msg = "parenthesized parameters may only be used with a trait";
1398             match **parameters {
1399                 PathParameters::AngleBracketed(ref data) => {
1400                     self.lower_angle_bracketed_parameter_data(data, param_mode, itctx)
1401                 }
1402                 PathParameters::Parenthesized(ref data) => match parenthesized_generic_args {
1403                     ParenthesizedGenericArgs::Ok =>
1404                         self.lower_parenthesized_parameter_data(data),
1405                     ParenthesizedGenericArgs::Warn => {
1406                         self.sess.buffer_lint(PARENTHESIZED_PARAMS_IN_TYPES_AND_MODULES,
1407                                               CRATE_NODE_ID, data.span, msg.into());
1408                         (hir::PathParameters::none(), true)
1409                     }
1410                     ParenthesizedGenericArgs::Err => {
1411                         struct_span_err!(self.sess, data.span, E0214, "{}", msg)
1412                             .span_label(data.span, "only traits may use parentheses").emit();
1413                         (hir::PathParameters::none(), true)
1414                     }
1415                 }
1416             }
1417         } else {
1418             self.lower_angle_bracketed_parameter_data(&Default::default(), param_mode, itctx)
1419         };
1420
1421         if !parameters.parenthesized && parameters.lifetimes.is_empty() {
1422             parameters.lifetimes = (0..expected_lifetimes).map(|_| {
1423                 self.elided_lifetime(path_span)
1424             }).collect();
1425         }
1426
1427         hir::PathSegment::new(
1428             self.lower_ident(segment.identifier),
1429             parameters,
1430             infer_types
1431         )
1432     }
1433
1434     fn lower_angle_bracketed_parameter_data(&mut self,
1435                                             data: &AngleBracketedParameterData,
1436                                             param_mode: ParamMode,
1437                                             itctx: ImplTraitContext)
1438                                             -> (hir::PathParameters, bool) {
1439         let &AngleBracketedParameterData { ref lifetimes, ref types, ref bindings, .. } = data;
1440         (hir::PathParameters {
1441             lifetimes: self.lower_lifetimes(lifetimes),
1442             types: types.iter().map(|ty| self.lower_ty(ty, itctx)).collect(),
1443             bindings: bindings.iter().map(|b| self.lower_ty_binding(b, itctx)).collect(),
1444             parenthesized: false,
1445         }, types.is_empty() && param_mode == ParamMode::Optional)
1446     }
1447
1448     fn lower_parenthesized_parameter_data(&mut self,
1449                                           data: &ParenthesizedParameterData)
1450                                           -> (hir::PathParameters, bool) {
1451         const DISALLOWED: ImplTraitContext = ImplTraitContext::Disallowed;
1452         let &ParenthesizedParameterData { ref inputs, ref output, span } = data;
1453         let inputs = inputs.iter().map(|ty| self.lower_ty(ty, DISALLOWED)).collect();
1454         let mk_tup = |this: &mut Self, tys, span| {
1455             let LoweredNodeId { node_id, hir_id } = this.next_id();
1456             P(hir::Ty { node: hir::TyTup(tys), id: node_id, hir_id, span })
1457         };
1458
1459         (hir::PathParameters {
1460             lifetimes: hir::HirVec::new(),
1461             types: hir_vec![mk_tup(self, inputs, span)],
1462             bindings: hir_vec![hir::TypeBinding {
1463                 id: self.next_id().node_id,
1464                 name: Symbol::intern(FN_OUTPUT_NAME),
1465                 ty: output.as_ref().map(|ty| self.lower_ty(&ty, DISALLOWED))
1466                                    .unwrap_or_else(|| mk_tup(self, hir::HirVec::new(), span)),
1467                 span: output.as_ref().map_or(span, |ty| ty.span),
1468             }],
1469             parenthesized: true,
1470         }, false)
1471     }
1472
1473     fn lower_local(&mut self, l: &Local) -> P<hir::Local> {
1474         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(l.id);
1475         P(hir::Local {
1476             id: node_id,
1477             hir_id,
1478             ty: l.ty.as_ref().map(|t| self.lower_ty(t, ImplTraitContext::Disallowed)),
1479             pat: self.lower_pat(&l.pat),
1480             init: l.init.as_ref().map(|e| P(self.lower_expr(e))),
1481             span: l.span,
1482             attrs: l.attrs.clone(),
1483             source: hir::LocalSource::Normal,
1484         })
1485     }
1486
1487     fn lower_mutability(&mut self, m: Mutability) -> hir::Mutability {
1488         match m {
1489             Mutability::Mutable => hir::MutMutable,
1490             Mutability::Immutable => hir::MutImmutable,
1491         }
1492     }
1493
1494     fn lower_arg(&mut self, arg: &Arg) -> hir::Arg {
1495         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(arg.id);
1496         hir::Arg {
1497             id: node_id,
1498             hir_id,
1499             pat: self.lower_pat(&arg.pat),
1500         }
1501     }
1502
1503     fn lower_fn_args_to_names(&mut self, decl: &FnDecl)
1504                               -> hir::HirVec<Spanned<Name>> {
1505         decl.inputs.iter().map(|arg| {
1506             match arg.pat.node {
1507                 PatKind::Ident(_, ident, None) => {
1508                     respan(ident.span, ident.node.name)
1509                 }
1510                 _ => respan(arg.pat.span, keywords::Invalid.name()),
1511             }
1512         }).collect()
1513     }
1514
1515
1516     fn lower_fn_decl(&mut self,
1517                      decl: &FnDecl,
1518                      fn_def_id: Option<DefId>,
1519                      impl_trait_return_allow: bool)
1520                      -> P<hir::FnDecl> {
1521         // NOTE: The two last parameters here have to do with impl Trait. If fn_def_id is Some,
1522         //       then impl Trait arguments are lowered into generic parameters on the given
1523         //       fn_def_id, otherwise impl Trait is disallowed. (for now)
1524         //
1525         //       Furthermore, if impl_trait_return_allow is true, then impl Trait may be used in
1526         //       return positions as well. This guards against trait declarations and their impls
1527         //       where impl Trait is disallowed. (again for now)
1528         P(hir::FnDecl {
1529             inputs: decl.inputs.iter()
1530                 .map(|arg| if let Some(def_id) = fn_def_id {
1531                     self.lower_ty(&arg.ty, ImplTraitContext::Universal(def_id))
1532                 } else {
1533                     self.lower_ty(&arg.ty, ImplTraitContext::Disallowed)
1534                 }).collect(),
1535             output: match decl.output {
1536                 FunctionRetTy::Ty(ref ty) => match fn_def_id {
1537                     Some(_) if impl_trait_return_allow =>
1538                         hir::Return(self.lower_ty(ty, ImplTraitContext::Existential)),
1539                     _ => hir::Return(self.lower_ty(ty, ImplTraitContext::Disallowed)),
1540                 },
1541                 FunctionRetTy::Default(span) => hir::DefaultReturn(span),
1542             },
1543             variadic: decl.variadic,
1544             has_implicit_self: decl.inputs.get(0).map_or(false, |arg| {
1545                 match arg.ty.node {
1546                     TyKind::ImplicitSelf => true,
1547                     TyKind::Rptr(_, ref mt) => mt.ty.node == TyKind::ImplicitSelf,
1548                     _ => false
1549                 }
1550             })
1551         })
1552     }
1553
1554     fn lower_ty_param_bound(&mut self, tpb: &TyParamBound, itctx: ImplTraitContext)
1555                             -> hir::TyParamBound {
1556         match *tpb {
1557             TraitTyParamBound(ref ty, modifier) => {
1558                 hir::TraitTyParamBound(self.lower_poly_trait_ref(ty, itctx),
1559                                        self.lower_trait_bound_modifier(modifier))
1560             }
1561             RegionTyParamBound(ref lifetime) => {
1562                 hir::RegionTyParamBound(self.lower_lifetime(lifetime))
1563             }
1564         }
1565     }
1566
1567     fn lower_ty_param(&mut self, tp: &TyParam, add_bounds: &[TyParamBound]) -> hir::TyParam {
1568         let mut name = self.lower_ident(tp.ident);
1569
1570         // Don't expose `Self` (recovered "keyword used as ident" parse error).
1571         // `rustc::ty` expects `Self` to be only used for a trait's `Self`.
1572         // Instead, use gensym("Self") to create a distinct name that looks the same.
1573         if name == keywords::SelfType.name() {
1574             name = Symbol::gensym("Self");
1575         }
1576
1577         let itctx = ImplTraitContext::Universal(self.resolver.definitions().local_def_id(tp.id));
1578         let mut bounds = self.lower_bounds(&tp.bounds, itctx);
1579         if !add_bounds.is_empty() {
1580             bounds = bounds.into_iter().chain(
1581                 self.lower_bounds(add_bounds, itctx).into_iter()
1582             ).collect();
1583         }
1584
1585         hir::TyParam {
1586             id: self.lower_node_id(tp.id).node_id,
1587             name,
1588             bounds,
1589             default: tp.default.as_ref().map(|x| self.lower_ty(x, ImplTraitContext::Disallowed)),
1590             span: tp.span,
1591             pure_wrt_drop: attr::contains_name(&tp.attrs, "may_dangle"),
1592             synthetic: tp.attrs.iter()
1593                                .filter(|attr| attr.check_name("rustc_synthetic"))
1594                                .map(|_| hir::SyntheticTyParamKind::ImplTrait)
1595                                .nth(0),
1596         }
1597     }
1598
1599     fn lower_lifetime(&mut self, l: &Lifetime) -> hir::Lifetime {
1600         let name = match self.lower_ident(l.ident) {
1601             x if x == "'_" => hir::LifetimeName::Underscore,
1602             x if x == "'static" => hir::LifetimeName::Static,
1603             name => {
1604                 if  self.is_collecting_in_band_lifetimes &&
1605                     !self.in_scope_lifetimes.contains(&name) &&
1606                     self.lifetimes_to_define.iter()
1607                         .find(|&&(_, lt_name)| lt_name == name)
1608                         .is_none()
1609                 {
1610                     self.lifetimes_to_define.push((l.span, name));
1611                 }
1612
1613                 hir::LifetimeName::Name(name)
1614             }
1615         };
1616
1617         hir::Lifetime {
1618             id: self.lower_node_id(l.id).node_id,
1619             name,
1620             span: l.span,
1621         }
1622     }
1623
1624     fn lower_lifetime_def(&mut self, l: &LifetimeDef) -> hir::LifetimeDef {
1625         let was_collecting_in_band = self.is_collecting_in_band_lifetimes;
1626         self.is_collecting_in_band_lifetimes = false;
1627
1628         let def = hir::LifetimeDef {
1629             lifetime: self.lower_lifetime(&l.lifetime),
1630             bounds: self.lower_lifetimes(&l.bounds),
1631             pure_wrt_drop: attr::contains_name(&l.attrs, "may_dangle"),
1632             in_band: false,
1633         };
1634
1635         self.is_collecting_in_band_lifetimes = was_collecting_in_band;
1636
1637         def
1638     }
1639
1640     fn lower_lifetimes(&mut self, lts: &Vec<Lifetime>) -> hir::HirVec<hir::Lifetime> {
1641         lts.iter().map(|l| self.lower_lifetime(l)).collect()
1642     }
1643
1644     fn lower_generic_params(
1645         &mut self,
1646         params: &Vec<GenericParam>,
1647         add_bounds: &NodeMap<Vec<TyParamBound>>,
1648     ) -> hir::HirVec<hir::GenericParam> {
1649         params.iter()
1650             .map(|param| match *param {
1651                 GenericParam::Lifetime(ref lifetime_def) => {
1652                     hir::GenericParam::Lifetime(self.lower_lifetime_def(lifetime_def))
1653                 }
1654                 GenericParam::Type(ref ty_param) => {
1655                     hir::GenericParam::Type(self.lower_ty_param(
1656                         ty_param,
1657                         add_bounds.get(&ty_param.id).map_or(&[][..], |x| &x)
1658                     ))
1659                 }
1660             })
1661             .collect()
1662     }
1663
1664     fn lower_generics(&mut self, g: &Generics) -> hir::Generics {
1665         // Collect `?Trait` bounds in where clause and move them to parameter definitions.
1666         // FIXME: This could probably be done with less rightward drift. Also looks like two control
1667         //        paths where report_error is called are also the only paths that advance to after
1668         //        the match statement, so the error reporting could probably just be moved there.
1669         let mut add_bounds = NodeMap();
1670         for pred in &g.where_clause.predicates {
1671             if let WherePredicate::BoundPredicate(ref bound_pred) = *pred {
1672                 'next_bound: for bound in &bound_pred.bounds {
1673                     if let TraitTyParamBound(_, TraitBoundModifier::Maybe) = *bound {
1674                         let report_error = |this: &mut Self| {
1675                             this.diagnostic().span_err(bound_pred.bounded_ty.span,
1676                                                        "`?Trait` bounds are only permitted at the \
1677                                                         point where a type parameter is declared");
1678                         };
1679                         // Check if the where clause type is a plain type parameter.
1680                         match bound_pred.bounded_ty.node {
1681                             TyKind::Path(None, ref path)
1682                                     if path.segments.len() == 1 &&
1683                                        bound_pred.bound_generic_params.is_empty() => {
1684                                 if let Some(Def::TyParam(def_id)) =
1685                                         self.resolver.get_resolution(bound_pred.bounded_ty.id)
1686                                                      .map(|d| d.base_def()) {
1687                                     if let Some(node_id) =
1688                                             self.resolver.definitions().as_local_node_id(def_id) {
1689                                         for param in &g.params {
1690                                             if let GenericParam::Type(ref ty_param) = *param {
1691                                                 if node_id == ty_param.id {
1692                                                     add_bounds.entry(ty_param.id)
1693                                                         .or_insert(Vec::new())
1694                                                         .push(bound.clone());
1695                                                     continue 'next_bound;
1696                                                 }
1697                                             }
1698                                         }
1699                                     }
1700                                 }
1701                                 report_error(self)
1702                             }
1703                             _ => report_error(self)
1704                         }
1705                     }
1706                 }
1707             }
1708         }
1709
1710         hir::Generics {
1711             params: self.lower_generic_params(&g.params, &add_bounds),
1712             where_clause: self.lower_where_clause(&g.where_clause),
1713             span: g.span,
1714         }
1715     }
1716
1717     fn lower_where_clause(&mut self, wc: &WhereClause) -> hir::WhereClause {
1718         hir::WhereClause {
1719             id: self.lower_node_id(wc.id).node_id,
1720             predicates: wc.predicates
1721                           .iter()
1722                           .map(|predicate| self.lower_where_predicate(predicate))
1723                           .collect(),
1724         }
1725     }
1726
1727     fn lower_where_predicate(&mut self, pred: &WherePredicate) -> hir::WherePredicate {
1728         match *pred {
1729             WherePredicate::BoundPredicate(WhereBoundPredicate{ ref bound_generic_params,
1730                                                                 ref bounded_ty,
1731                                                                 ref bounds,
1732                                                                 span}) => {
1733                 self.with_in_scope_lifetime_defs(
1734                     &bound_generic_params.iter()
1735                         .filter_map(|p| match *p {
1736                             GenericParam::Lifetime(ref ld) => Some(ld.clone()),
1737                             _ => None,
1738                         })
1739                         .collect::<Vec<_>>(),
1740                     |this| {
1741                         hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
1742                             bound_generic_params:
1743                                 this.lower_generic_params(bound_generic_params, &NodeMap()),
1744                             bounded_ty: this.lower_ty(bounded_ty, ImplTraitContext::Disallowed),
1745                             bounds: bounds.iter().filter_map(|bound| match *bound {
1746                                 // Ignore `?Trait` bounds.
1747                                 // Tthey were copied into type parameters already.
1748                                 TraitTyParamBound(_, TraitBoundModifier::Maybe) => None,
1749                                 _ => Some(this.lower_ty_param_bound(
1750                                         bound, ImplTraitContext::Disallowed))
1751                             }).collect(),
1752                             span,
1753                         })
1754                     }
1755                 )
1756             }
1757             WherePredicate::RegionPredicate(WhereRegionPredicate{ ref lifetime,
1758                                                                   ref bounds,
1759                                                                   span}) => {
1760                 hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
1761                     span,
1762                     lifetime: self.lower_lifetime(lifetime),
1763                     bounds: bounds.iter().map(|bound| self.lower_lifetime(bound)).collect(),
1764                 })
1765             }
1766             WherePredicate::EqPredicate(WhereEqPredicate{ id,
1767                                                           ref lhs_ty,
1768                                                           ref rhs_ty,
1769                                                           span}) => {
1770                 hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
1771                     id: self.lower_node_id(id).node_id,
1772                     lhs_ty: self.lower_ty(lhs_ty, ImplTraitContext::Disallowed),
1773                     rhs_ty: self.lower_ty(rhs_ty, ImplTraitContext::Disallowed),
1774                     span,
1775                 })
1776             }
1777         }
1778     }
1779
1780     fn lower_variant_data(&mut self, vdata: &VariantData) -> hir::VariantData {
1781         match *vdata {
1782             VariantData::Struct(ref fields, id) => {
1783                 hir::VariantData::Struct(fields.iter()
1784                                                .enumerate()
1785                                                .map(|f| self.lower_struct_field(f))
1786                                                .collect(),
1787                                          self.lower_node_id(id).node_id)
1788             }
1789             VariantData::Tuple(ref fields, id) => {
1790                 hir::VariantData::Tuple(fields.iter()
1791                                               .enumerate()
1792                                               .map(|f| self.lower_struct_field(f))
1793                                               .collect(),
1794                                         self.lower_node_id(id).node_id)
1795             }
1796             VariantData::Unit(id) => hir::VariantData::Unit(self.lower_node_id(id).node_id),
1797         }
1798     }
1799
1800     fn lower_trait_ref(&mut self, p: &TraitRef, itctx: ImplTraitContext) -> hir::TraitRef {
1801         let path = match self.lower_qpath(p.ref_id, &None, &p.path, ParamMode::Explicit, itctx) {
1802             hir::QPath::Resolved(None, path) => path.and_then(|path| path),
1803             qpath => bug!("lower_trait_ref: unexpected QPath `{:?}`", qpath)
1804         };
1805         hir::TraitRef {
1806             path,
1807             ref_id: self.lower_node_id(p.ref_id).node_id,
1808         }
1809     }
1810
1811     fn lower_poly_trait_ref(&mut self,
1812                             p: &PolyTraitRef,
1813                             itctx: ImplTraitContext)
1814                             -> hir::PolyTraitRef {
1815         let bound_generic_params = self.lower_generic_params(&p.bound_generic_params, &NodeMap());
1816         let trait_ref = self.with_parent_impl_lifetime_defs(
1817             &bound_generic_params.iter()
1818                 .filter_map(|p| match *p {
1819                     hir::GenericParam::Lifetime(ref ld) => Some(ld.clone()),
1820                     _ => None,
1821                 })
1822                 .collect::<Vec<_>>(),
1823             |this| this.lower_trait_ref(&p.trait_ref, itctx),
1824         );
1825
1826         hir::PolyTraitRef {
1827             bound_generic_params,
1828             trait_ref,
1829             span: p.span,
1830         }
1831     }
1832
1833     fn lower_struct_field(&mut self, (index, f): (usize, &StructField)) -> hir::StructField {
1834         hir::StructField {
1835             span: f.span,
1836             id: self.lower_node_id(f.id).node_id,
1837             name: self.lower_ident(match f.ident {
1838                 Some(ident) => ident,
1839                 // FIXME(jseyfried) positional field hygiene
1840                 None => Ident { name: Symbol::intern(&index.to_string()), ctxt: f.span.ctxt() },
1841             }),
1842             vis: self.lower_visibility(&f.vis, None),
1843             ty: self.lower_ty(&f.ty, ImplTraitContext::Disallowed),
1844             attrs: self.lower_attrs(&f.attrs),
1845         }
1846     }
1847
1848     fn lower_field(&mut self, f: &Field) -> hir::Field {
1849         hir::Field {
1850             name: respan(f.ident.span, self.lower_ident(f.ident.node)),
1851             expr: P(self.lower_expr(&f.expr)),
1852             span: f.span,
1853             is_shorthand: f.is_shorthand,
1854         }
1855     }
1856
1857     fn lower_mt(&mut self, mt: &MutTy, itctx: ImplTraitContext) -> hir::MutTy {
1858         hir::MutTy {
1859             ty: self.lower_ty(&mt.ty, itctx),
1860             mutbl: self.lower_mutability(mt.mutbl),
1861         }
1862     }
1863
1864     fn lower_bounds(&mut self, bounds: &[TyParamBound], itctx: ImplTraitContext)
1865                     -> hir::TyParamBounds {
1866         bounds.iter().map(|bound| self.lower_ty_param_bound(bound, itctx)).collect()
1867     }
1868
1869     fn lower_block(&mut self, b: &Block, targeted_by_break: bool) -> P<hir::Block> {
1870         let mut expr = None;
1871
1872         let mut stmts = vec![];
1873
1874         for (index, stmt) in b.stmts.iter().enumerate() {
1875             if index == b.stmts.len() - 1 {
1876                 if let StmtKind::Expr(ref e) = stmt.node {
1877                     expr = Some(P(self.lower_expr(e)));
1878                 } else {
1879                     stmts.extend(self.lower_stmt(stmt));
1880                 }
1881             } else {
1882                 stmts.extend(self.lower_stmt(stmt));
1883             }
1884         }
1885
1886         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(b.id);
1887
1888         P(hir::Block {
1889             id: node_id,
1890             hir_id,
1891             stmts: stmts.into(),
1892             expr,
1893             rules: self.lower_block_check_mode(&b.rules),
1894             span: b.span,
1895             targeted_by_break,
1896             recovered: b.recovered,
1897         })
1898     }
1899
1900     fn lower_item_kind(&mut self,
1901                        id: NodeId,
1902                        name: &mut Name,
1903                        attrs: &hir::HirVec<Attribute>,
1904                        vis: &mut hir::Visibility,
1905                        i: &ItemKind)
1906                        -> hir::Item_ {
1907         match *i {
1908             ItemKind::ExternCrate(string) => hir::ItemExternCrate(string),
1909             ItemKind::Use(ref use_tree) => {
1910                 // Start with an empty prefix
1911                 let prefix = Path {
1912                     segments: vec![],
1913                     span: use_tree.span,
1914                 };
1915
1916                 self.lower_use_tree(use_tree, &prefix, id, vis, name, attrs)
1917             }
1918             ItemKind::Static(ref t, m, ref e) => {
1919                 let value = self.lower_body(None, |this| this.lower_expr(e));
1920                 hir::ItemStatic(self.lower_ty(t, ImplTraitContext::Disallowed),
1921                                 self.lower_mutability(m),
1922                                 value)
1923             }
1924             ItemKind::Const(ref t, ref e) => {
1925                 let value = self.lower_body(None, |this| this.lower_expr(e));
1926                 hir::ItemConst(self.lower_ty(t, ImplTraitContext::Disallowed), value)
1927             }
1928             ItemKind::Fn(ref decl, unsafety, constness, abi, ref generics, ref body) => {
1929                 let fn_def_id = self.resolver.definitions().opt_local_def_id(id);
1930                 self.with_new_scopes(|this| {
1931                     let body_id = this.lower_body(Some(decl), |this| {
1932                         let body = this.lower_block(body, false);
1933                         this.expr_block(body, ThinVec::new())
1934                     });
1935                     let (generics, fn_decl) =
1936                         this.add_in_band_defs(generics, fn_def_id, |this|
1937                             this.lower_fn_decl(decl, fn_def_id, true));
1938
1939                     hir::ItemFn(fn_decl,
1940                                 this.lower_unsafety(unsafety),
1941                                 this.lower_constness(constness),
1942                                 abi,
1943                                 generics,
1944                                 body_id)
1945                 })
1946             }
1947             ItemKind::Mod(ref m) => hir::ItemMod(self.lower_mod(m)),
1948             ItemKind::ForeignMod(ref nm) => hir::ItemForeignMod(self.lower_foreign_mod(nm)),
1949             ItemKind::GlobalAsm(ref ga) => hir::ItemGlobalAsm(self.lower_global_asm(ga)),
1950             ItemKind::Ty(ref t, ref generics) => {
1951                 hir::ItemTy(self.lower_ty(t, ImplTraitContext::Disallowed),
1952                             self.lower_generics(generics))
1953             }
1954             ItemKind::Enum(ref enum_definition, ref generics) => {
1955                 hir::ItemEnum(hir::EnumDef {
1956                                   variants: enum_definition.variants
1957                                                            .iter()
1958                                                            .map(|x| self.lower_variant(x))
1959                                                            .collect(),
1960                               },
1961                               self.lower_generics(generics))
1962             }
1963             ItemKind::Struct(ref struct_def, ref generics) => {
1964                 let struct_def = self.lower_variant_data(struct_def);
1965                 hir::ItemStruct(struct_def, self.lower_generics(generics))
1966             }
1967             ItemKind::Union(ref vdata, ref generics) => {
1968                 let vdata = self.lower_variant_data(vdata);
1969                 hir::ItemUnion(vdata, self.lower_generics(generics))
1970             }
1971             ItemKind::Impl(unsafety,
1972                            polarity,
1973                            defaultness,
1974                            ref ast_generics,
1975                            ref ifce,
1976                            ref ty,
1977                            ref impl_items) => {
1978                 let def_id = self.resolver.definitions().opt_local_def_id(id);
1979                 let (generics, (ifce, lowered_ty)) =
1980                     self.add_in_band_defs(ast_generics, def_id, |this| {
1981                         let ifce = ifce.as_ref().map(|trait_ref| {
1982                             this.lower_trait_ref(trait_ref, ImplTraitContext::Disallowed)
1983                         });
1984
1985                         if let Some(ref trait_ref) = ifce {
1986                             if let Def::Trait(def_id) = trait_ref.path.def {
1987                                 this.trait_impls.entry(def_id).or_insert(vec![]).push(id);
1988                             }
1989                         }
1990
1991                         let lowered_ty = this.lower_ty(ty, ImplTraitContext::Disallowed);
1992
1993                         (ifce, lowered_ty)
1994                     });
1995
1996                 let new_impl_items = self.with_in_scope_lifetime_defs(
1997                     &ast_generics.params
1998                         .iter()
1999                         .filter_map(|p| match *p {
2000                             GenericParam::Lifetime(ref ld) => Some(ld.clone()),
2001                             _ => None,
2002                         })
2003                         .collect::<Vec<_>>(),
2004                     |this| {
2005                         impl_items.iter()
2006                             .map(|item| this.lower_impl_item_ref(item))
2007                             .collect()
2008                     }
2009                 );
2010
2011
2012                 hir::ItemImpl(self.lower_unsafety(unsafety),
2013                               self.lower_impl_polarity(polarity),
2014                               self.lower_defaultness(defaultness, true /* [1] */),
2015                               generics,
2016                               ifce,
2017                               lowered_ty,
2018                               new_impl_items)
2019             }
2020             ItemKind::Trait(is_auto, unsafety, ref generics, ref bounds, ref items) => {
2021                 let bounds = self.lower_bounds(bounds, ImplTraitContext::Disallowed);
2022                 let items = items.iter().map(|item| self.lower_trait_item_ref(item)).collect();
2023                 hir::ItemTrait(self.lower_is_auto(is_auto),
2024                                self.lower_unsafety(unsafety),
2025                                self.lower_generics(generics),
2026                                bounds,
2027                                items)
2028             }
2029             ItemKind::TraitAlias(ref generics, ref bounds) => {
2030                 hir::ItemTraitAlias(self.lower_generics(generics),
2031                                     self.lower_bounds(bounds, ImplTraitContext::Disallowed))
2032             }
2033             ItemKind::MacroDef(..) | ItemKind::Mac(..) => panic!("Shouldn't still be around"),
2034         }
2035
2036         // [1] `defaultness.has_value()` is never called for an `impl`, always `true` in order to
2037         //     not cause an assertion failure inside the `lower_defaultness` function
2038     }
2039
2040     fn lower_use_tree(&mut self,
2041                        tree: &UseTree,
2042                        prefix: &Path,
2043                        id: NodeId,
2044                        vis: &mut hir::Visibility,
2045                        name: &mut Name,
2046                        attrs: &hir::HirVec<Attribute>)
2047                        -> hir::Item_ {
2048         let path = &tree.prefix;
2049
2050         match tree.kind {
2051             UseTreeKind::Simple(ident) => {
2052                 *name = ident.name;
2053
2054                 // First apply the prefix to the path
2055                 let mut path = Path {
2056                     segments: prefix.segments
2057                         .iter()
2058                         .chain(path.segments.iter())
2059                         .cloned()
2060                         .collect(),
2061                     span: path.span
2062                 };
2063
2064                 // Correctly resolve `self` imports
2065                 if path.segments.len() > 1 &&
2066                    path.segments.last().unwrap().identifier.name == keywords::SelfValue.name() {
2067                     let _ = path.segments.pop();
2068                     if ident.name == keywords::SelfValue.name() {
2069                         *name = path.segments.last().unwrap().identifier.name;
2070                     }
2071                 }
2072
2073                 let path = P(self.lower_path(id, &path, ParamMode::Explicit, true));
2074                 hir::ItemUse(path, hir::UseKind::Single)
2075             }
2076             UseTreeKind::Glob => {
2077                 let path = P(self.lower_path(id, &Path {
2078                     segments: prefix.segments
2079                         .iter()
2080                         .chain(path.segments.iter())
2081                         .cloned()
2082                         .collect(),
2083                     span: path.span,
2084                 }, ParamMode::Explicit, true));
2085                 hir::ItemUse(path, hir::UseKind::Glob)
2086             }
2087             UseTreeKind::Nested(ref trees) => {
2088                 let prefix = Path {
2089                     segments: prefix.segments
2090                         .iter()
2091                         .chain(path.segments.iter())
2092                         .cloned()
2093                         .collect(),
2094                     span: prefix.span.to(path.span),
2095                 };
2096
2097                 // Add all the nested PathListItems in the HIR
2098                 for &(ref use_tree, id) in trees {
2099                     self.allocate_hir_id_counter(id, &use_tree);
2100                     let LoweredNodeId {
2101                         node_id: new_id,
2102                         hir_id: new_hir_id,
2103                     } = self.lower_node_id(id);
2104
2105                     let mut vis = vis.clone();
2106                     let mut name = name.clone();
2107                     let item = self.lower_use_tree(
2108                         use_tree, &prefix, new_id, &mut vis, &mut name, &attrs,
2109                     );
2110
2111                     self.with_hir_id_owner(new_id, |this| {
2112                         let vis = match vis {
2113                             hir::Visibility::Public => hir::Visibility::Public,
2114                             hir::Visibility::Crate => hir::Visibility::Crate,
2115                             hir::Visibility::Inherited => hir::Visibility::Inherited,
2116                             hir::Visibility::Restricted { ref path, id: _  } => {
2117                                 hir::Visibility::Restricted {
2118                                     path: path.clone(),
2119                                     // We are allocating a new NodeId here
2120                                     id: this.next_id().node_id,
2121                                 }
2122                             }
2123                         };
2124
2125                         this.items.insert(new_id, hir::Item {
2126                             id: new_id,
2127                             hir_id: new_hir_id,
2128                             name: name,
2129                             attrs: attrs.clone(),
2130                             node: item,
2131                             vis,
2132                             span: use_tree.span,
2133                         });
2134                     });
2135                 }
2136
2137                 // Privatize the degenerate import base, used only to check
2138                 // the stability of `use a::{};`, to avoid it showing up as
2139                 // a re-export by accident when `pub`, e.g. in documentation.
2140                 let path = P(self.lower_path(id, &prefix, ParamMode::Explicit, true));
2141                 *vis = hir::Inherited;
2142                 hir::ItemUse(path, hir::UseKind::ListStem)
2143             }
2144         }
2145     }
2146
2147     fn lower_trait_item(&mut self, i: &TraitItem) -> hir::TraitItem {
2148         self.with_parent_def(i.id, |this| {
2149             let LoweredNodeId { node_id, hir_id } = this.lower_node_id(i.id);
2150             let fn_def_id = this.resolver.definitions().opt_local_def_id(node_id);
2151
2152             let (generics, node) = match i.node {
2153                 TraitItemKind::Const(ref ty, ref default) => {
2154                     (
2155                         this.lower_generics(&i.generics),
2156                         hir::TraitItemKind::Const(
2157                             this.lower_ty(ty, ImplTraitContext::Disallowed),
2158                             default.as_ref().map(|x| {
2159                                 this.lower_body(None, |this| this.lower_expr(x))
2160                             }))
2161                     )
2162                 }
2163                 TraitItemKind::Method(ref sig, None) => {
2164                     let names = this.lower_fn_args_to_names(&sig.decl);
2165                     this.add_in_band_defs(&i.generics, fn_def_id, |this|
2166                         hir::TraitItemKind::Method(
2167                             this.lower_method_sig(sig, fn_def_id, false),
2168                             hir::TraitMethod::Required(names)))
2169                 }
2170                 TraitItemKind::Method(ref sig, Some(ref body)) => {
2171                     let body_id = this.lower_body(Some(&sig.decl), |this| {
2172                         let body = this.lower_block(body, false);
2173                         this.expr_block(body, ThinVec::new())
2174                     });
2175
2176                     this.add_in_band_defs(&i.generics, fn_def_id, |this|
2177                         hir::TraitItemKind::Method(
2178                             this.lower_method_sig(sig, fn_def_id, false),
2179                            hir::TraitMethod::Provided(body_id)))
2180                 }
2181                 TraitItemKind::Type(ref bounds, ref default) => {
2182                     (
2183                         this.lower_generics(&i.generics),
2184                         hir::TraitItemKind::Type(
2185                             this.lower_bounds(bounds, ImplTraitContext::Disallowed),
2186                             default.as_ref().map(|x| {
2187                                 this.lower_ty(x, ImplTraitContext::Disallowed)
2188                             }))
2189                     )
2190                 }
2191                 TraitItemKind::Macro(..) => panic!("Shouldn't exist any more"),
2192             };
2193
2194             hir::TraitItem {
2195                 id: node_id,
2196                 hir_id,
2197                 name: this.lower_ident(i.ident),
2198                 attrs: this.lower_attrs(&i.attrs),
2199                 generics,
2200                 node,
2201                 span: i.span,
2202             }
2203         })
2204     }
2205
2206     fn lower_trait_item_ref(&mut self, i: &TraitItem) -> hir::TraitItemRef {
2207         let (kind, has_default) = match i.node {
2208             TraitItemKind::Const(_, ref default) => {
2209                 (hir::AssociatedItemKind::Const, default.is_some())
2210             }
2211             TraitItemKind::Type(_, ref default) => {
2212                 (hir::AssociatedItemKind::Type, default.is_some())
2213             }
2214             TraitItemKind::Method(ref sig, ref default) => {
2215                 (hir::AssociatedItemKind::Method {
2216                     has_self: sig.decl.has_self(),
2217                  }, default.is_some())
2218             }
2219             TraitItemKind::Macro(..) => unimplemented!(),
2220         };
2221         hir::TraitItemRef {
2222             id: hir::TraitItemId { node_id: i.id },
2223             name: self.lower_ident(i.ident),
2224             span: i.span,
2225             defaultness: self.lower_defaultness(Defaultness::Default, has_default),
2226             kind,
2227         }
2228     }
2229
2230     fn lower_impl_item(&mut self, i: &ImplItem) -> hir::ImplItem {
2231         self.with_parent_def(i.id, |this| {
2232             let LoweredNodeId { node_id, hir_id } = this.lower_node_id(i.id);
2233             let fn_def_id = this.resolver.definitions().opt_local_def_id(node_id);
2234
2235             let (generics, node) = match i.node {
2236                 ImplItemKind::Const(ref ty, ref expr) => {
2237                     let body_id = this.lower_body(None, |this| this.lower_expr(expr));
2238                     (
2239                         this.lower_generics(&i.generics),
2240                         hir::ImplItemKind::Const(
2241                             this.lower_ty(ty, ImplTraitContext::Disallowed),
2242                             body_id
2243                         )
2244                     )
2245                 }
2246                 ImplItemKind::Method(ref sig, ref body) => {
2247                     let body_id = this.lower_body(Some(&sig.decl), |this| {
2248                         let body = this.lower_block(body, false);
2249                         this.expr_block(body, ThinVec::new())
2250                     });
2251                     let impl_trait_return_allow = !this.is_in_trait_impl;
2252
2253                     this.add_in_band_defs(&i.generics, fn_def_id, |this|
2254                         hir::ImplItemKind::Method(
2255                             this.lower_method_sig(sig, fn_def_id, impl_trait_return_allow),
2256                             body_id))
2257                 }
2258                 ImplItemKind::Type(ref ty) => (
2259                     this.lower_generics(&i.generics),
2260                     hir::ImplItemKind::Type(
2261                         this.lower_ty(ty, ImplTraitContext::Disallowed)),
2262                 ),
2263                 ImplItemKind::Macro(..) => panic!("Shouldn't exist any more"),
2264             };
2265
2266             hir::ImplItem {
2267                 id: node_id,
2268                 hir_id,
2269                 name: this.lower_ident(i.ident),
2270                 attrs: this.lower_attrs(&i.attrs),
2271                 generics,
2272                 vis: this.lower_visibility(&i.vis, None),
2273                 defaultness: this.lower_defaultness(i.defaultness, true /* [1] */),
2274                 node,
2275                 span: i.span,
2276             }
2277         })
2278
2279         // [1] since `default impl` is not yet implemented, this is always true in impls
2280     }
2281
2282     fn lower_impl_item_ref(&mut self, i: &ImplItem) -> hir::ImplItemRef {
2283         hir::ImplItemRef {
2284             id: hir::ImplItemId { node_id: i.id },
2285             name: self.lower_ident(i.ident),
2286             span: i.span,
2287             vis: self.lower_visibility(&i.vis, Some(i.id)),
2288             defaultness: self.lower_defaultness(i.defaultness, true /* [1] */),
2289             kind: match i.node {
2290                 ImplItemKind::Const(..) => hir::AssociatedItemKind::Const,
2291                 ImplItemKind::Type(..) => hir::AssociatedItemKind::Type,
2292                 ImplItemKind::Method(ref sig, _) => {
2293                     hir::AssociatedItemKind::Method {
2294                         has_self: sig.decl.has_self(),
2295                     }
2296                 },
2297                 ImplItemKind::Macro(..) => unimplemented!(),
2298             },
2299         }
2300
2301         // [1] since `default impl` is not yet implemented, this is always true in impls
2302     }
2303
2304     fn lower_mod(&mut self, m: &Mod) -> hir::Mod {
2305         hir::Mod {
2306             inner: m.inner,
2307             item_ids: m.items.iter().flat_map(|x| self.lower_item_id(x)).collect(),
2308         }
2309     }
2310
2311     fn lower_item_id(&mut self, i: &Item) -> SmallVector<hir::ItemId> {
2312         match i.node {
2313             ItemKind::Use(ref use_tree) => {
2314                 let mut vec = SmallVector::one(hir::ItemId { id: i.id });
2315                 self.lower_item_id_use_tree(use_tree, &mut vec);
2316                 return vec;
2317             }
2318             ItemKind::MacroDef(..) => return SmallVector::new(),
2319             _ => {}
2320         }
2321         SmallVector::one(hir::ItemId { id: i.id })
2322     }
2323
2324     fn lower_item_id_use_tree(&self, tree: &UseTree, vec: &mut SmallVector<hir::ItemId>) {
2325         match tree.kind {
2326             UseTreeKind::Nested(ref nested_vec) => {
2327                 for &(ref nested, id) in nested_vec {
2328                     vec.push(hir::ItemId { id, });
2329                     self.lower_item_id_use_tree(nested, vec);
2330                 }
2331             }
2332             UseTreeKind::Glob => {}
2333             UseTreeKind::Simple(..) => {}
2334         }
2335     }
2336
2337     pub fn lower_item(&mut self, i: &Item) -> Option<hir::Item> {
2338         let mut name = i.ident.name;
2339         let mut vis = self.lower_visibility(&i.vis, None);
2340         let attrs = self.lower_attrs(&i.attrs);
2341         if let ItemKind::MacroDef(ref def) = i.node {
2342             if !def.legacy || attr::contains_name(&i.attrs, "macro_export") {
2343                 let body = self.lower_token_stream(def.stream());
2344                 self.exported_macros.push(hir::MacroDef {
2345                     name,
2346                     vis,
2347                     attrs,
2348                     id: i.id,
2349                     span: i.span,
2350                     body,
2351                     legacy: def.legacy,
2352                 });
2353             }
2354             return None;
2355         }
2356
2357         let node = self.with_parent_def(i.id, |this| {
2358             this.lower_item_kind(i.id, &mut name, &attrs, &mut vis, &i.node)
2359         });
2360
2361         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(i.id);
2362
2363         Some(hir::Item {
2364             id: node_id,
2365             hir_id,
2366             name,
2367             attrs,
2368             node,
2369             vis,
2370             span: i.span,
2371         })
2372     }
2373
2374     fn lower_foreign_item(&mut self, i: &ForeignItem) -> hir::ForeignItem {
2375         self.with_parent_def(i.id, |this| {
2376             let node_id = this.lower_node_id(i.id).node_id;
2377             let def_id = this.resolver.definitions().local_def_id(node_id);
2378             hir::ForeignItem {
2379                 id: node_id,
2380                 name: i.ident.name,
2381                 attrs: this.lower_attrs(&i.attrs),
2382                 node: match i.node {
2383                     ForeignItemKind::Fn(ref fdec, ref generics) => {
2384                         // Disallow impl Trait in foreign items
2385                         let (generics, (fn_dec, fn_args)) =
2386                             this.add_in_band_defs(
2387                                 generics,
2388                                 Some(def_id),
2389                                 |this| (
2390                                     this.lower_fn_decl(fdec, None, false),
2391                                     this.lower_fn_args_to_names(fdec)
2392                                 )
2393                             );
2394
2395                         hir::ForeignItemFn(fn_dec, fn_args, generics)
2396                     }
2397                     ForeignItemKind::Static(ref t, m) => {
2398                         hir::ForeignItemStatic(this.lower_ty(t, ImplTraitContext::Disallowed), m)
2399                     }
2400                     ForeignItemKind::Ty => {
2401                         hir::ForeignItemType
2402                     }
2403                 },
2404                 vis: this.lower_visibility(&i.vis, None),
2405                 span: i.span,
2406             }
2407         })
2408     }
2409
2410     fn lower_method_sig(&mut self,
2411                         sig: &MethodSig,
2412                         fn_def_id: Option<DefId>,
2413                         impl_trait_return_allow: bool)
2414                         -> hir::MethodSig {
2415         hir::MethodSig {
2416             abi: sig.abi,
2417             unsafety: self.lower_unsafety(sig.unsafety),
2418             constness: self.lower_constness(sig.constness),
2419             decl: self.lower_fn_decl(&sig.decl, fn_def_id, impl_trait_return_allow),
2420         }
2421     }
2422
2423     fn lower_is_auto(&mut self, a: IsAuto) -> hir::IsAuto {
2424         match a {
2425             IsAuto::Yes => hir::IsAuto::Yes,
2426             IsAuto::No => hir::IsAuto::No,
2427         }
2428     }
2429
2430     fn lower_unsafety(&mut self, u: Unsafety) -> hir::Unsafety {
2431         match u {
2432             Unsafety::Unsafe => hir::Unsafety::Unsafe,
2433             Unsafety::Normal => hir::Unsafety::Normal,
2434         }
2435     }
2436
2437     fn lower_constness(&mut self, c: Spanned<Constness>) -> hir::Constness {
2438         match c.node {
2439             Constness::Const => hir::Constness::Const,
2440             Constness::NotConst => hir::Constness::NotConst,
2441         }
2442     }
2443
2444     fn lower_unop(&mut self, u: UnOp) -> hir::UnOp {
2445         match u {
2446             UnOp::Deref => hir::UnDeref,
2447             UnOp::Not => hir::UnNot,
2448             UnOp::Neg => hir::UnNeg,
2449         }
2450     }
2451
2452     fn lower_binop(&mut self, b: BinOp) -> hir::BinOp {
2453         Spanned {
2454             node: match b.node {
2455                 BinOpKind::Add => hir::BiAdd,
2456                 BinOpKind::Sub => hir::BiSub,
2457                 BinOpKind::Mul => hir::BiMul,
2458                 BinOpKind::Div => hir::BiDiv,
2459                 BinOpKind::Rem => hir::BiRem,
2460                 BinOpKind::And => hir::BiAnd,
2461                 BinOpKind::Or => hir::BiOr,
2462                 BinOpKind::BitXor => hir::BiBitXor,
2463                 BinOpKind::BitAnd => hir::BiBitAnd,
2464                 BinOpKind::BitOr => hir::BiBitOr,
2465                 BinOpKind::Shl => hir::BiShl,
2466                 BinOpKind::Shr => hir::BiShr,
2467                 BinOpKind::Eq => hir::BiEq,
2468                 BinOpKind::Lt => hir::BiLt,
2469                 BinOpKind::Le => hir::BiLe,
2470                 BinOpKind::Ne => hir::BiNe,
2471                 BinOpKind::Ge => hir::BiGe,
2472                 BinOpKind::Gt => hir::BiGt,
2473             },
2474             span: b.span,
2475         }
2476     }
2477
2478     fn lower_pat(&mut self, p: &Pat) -> P<hir::Pat> {
2479         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(p.id);
2480
2481         P(hir::Pat {
2482             id: node_id,
2483             hir_id,
2484             node: match p.node {
2485                 PatKind::Wild => hir::PatKind::Wild,
2486                 PatKind::Ident(ref binding_mode, pth1, ref sub) => {
2487                     match self.resolver.get_resolution(p.id).map(|d| d.base_def()) {
2488                         // `None` can occur in body-less function signatures
2489                         def @ None | def @ Some(Def::Local(_)) => {
2490                             let canonical_id = match def {
2491                                 Some(Def::Local(id)) => id,
2492                                 _ => p.id
2493                             };
2494                             hir::PatKind::Binding(self.lower_binding_mode(binding_mode),
2495                                                   canonical_id,
2496                                                   respan(pth1.span, pth1.node.name),
2497                                                   sub.as_ref().map(|x| self.lower_pat(x)))
2498                         }
2499                         Some(def) => {
2500                             hir::PatKind::Path(hir::QPath::Resolved(None, P(hir::Path {
2501                                 span: pth1.span,
2502                                 def,
2503                                 segments: hir_vec![
2504                                     hir::PathSegment::from_name(pth1.node.name)
2505                                 ],
2506                             })))
2507                         }
2508                     }
2509                 }
2510                 PatKind::Lit(ref e) => hir::PatKind::Lit(P(self.lower_expr(e))),
2511                 PatKind::TupleStruct(ref path, ref pats, ddpos) => {
2512                     let qpath = self.lower_qpath(p.id, &None, path, ParamMode::Optional,
2513                                                  ImplTraitContext::Disallowed);
2514                     hir::PatKind::TupleStruct(qpath,
2515                                               pats.iter().map(|x| self.lower_pat(x)).collect(),
2516                                               ddpos)
2517                 }
2518                 PatKind::Path(ref qself, ref path) => {
2519                     hir::PatKind::Path(self.lower_qpath(p.id, qself, path, ParamMode::Optional,
2520                                                         ImplTraitContext::Disallowed))
2521                 }
2522                 PatKind::Struct(ref path, ref fields, etc) => {
2523                     let qpath = self.lower_qpath(p.id, &None, path, ParamMode::Optional,
2524                                                  ImplTraitContext::Disallowed);
2525
2526                     let fs = fields.iter()
2527                                    .map(|f| {
2528                                        Spanned {
2529                                            span: f.span,
2530                                            node: hir::FieldPat {
2531                                                name: self.lower_ident(f.node.ident),
2532                                                pat: self.lower_pat(&f.node.pat),
2533                                                is_shorthand: f.node.is_shorthand,
2534                                            },
2535                                        }
2536                                    })
2537                                    .collect();
2538                     hir::PatKind::Struct(qpath, fs, etc)
2539                 }
2540                 PatKind::Tuple(ref elts, ddpos) => {
2541                     hir::PatKind::Tuple(elts.iter().map(|x| self.lower_pat(x)).collect(), ddpos)
2542                 }
2543                 PatKind::Box(ref inner) => hir::PatKind::Box(self.lower_pat(inner)),
2544                 PatKind::Ref(ref inner, mutbl) => {
2545                     hir::PatKind::Ref(self.lower_pat(inner), self.lower_mutability(mutbl))
2546                 }
2547                 PatKind::Range(ref e1, ref e2, ref end) => {
2548                     hir::PatKind::Range(P(self.lower_expr(e1)),
2549                                         P(self.lower_expr(e2)),
2550                                         self.lower_range_end(end))
2551                 }
2552                 PatKind::Slice(ref before, ref slice, ref after) => {
2553                     hir::PatKind::Slice(before.iter().map(|x| self.lower_pat(x)).collect(),
2554                                 slice.as_ref().map(|x| self.lower_pat(x)),
2555                                 after.iter().map(|x| self.lower_pat(x)).collect())
2556                 }
2557                 PatKind::Mac(_) => panic!("Shouldn't exist here"),
2558             },
2559             span: p.span,
2560         })
2561     }
2562
2563     fn lower_range_end(&mut self, e: &RangeEnd) -> hir::RangeEnd {
2564         match *e {
2565             RangeEnd::Included(_) => hir::RangeEnd::Included,
2566             RangeEnd::Excluded => hir::RangeEnd::Excluded,
2567         }
2568     }
2569
2570     fn lower_expr(&mut self, e: &Expr) -> hir::Expr {
2571         let kind = match e.node {
2572             // Issue #22181:
2573             // Eventually a desugaring for `box EXPR`
2574             // (similar to the desugaring above for `in PLACE BLOCK`)
2575             // should go here, desugaring
2576             //
2577             // to:
2578             //
2579             // let mut place = BoxPlace::make_place();
2580             // let raw_place = Place::pointer(&mut place);
2581             // let value = $value;
2582             // unsafe {
2583             //     ::std::ptr::write(raw_place, value);
2584             //     Boxed::finalize(place)
2585             // }
2586             //
2587             // But for now there are type-inference issues doing that.
2588             ExprKind::Box(ref inner) => {
2589                 hir::ExprBox(P(self.lower_expr(inner)))
2590             }
2591
2592             // Desugar ExprBox: `in (PLACE) EXPR`
2593             ExprKind::InPlace(ref placer, ref value_expr) => {
2594                 // to:
2595                 //
2596                 // let p = PLACE;
2597                 // let mut place = Placer::make_place(p);
2598                 // let raw_place = Place::pointer(&mut place);
2599                 // push_unsafe!({
2600                 //     std::intrinsics::move_val_init(raw_place, pop_unsafe!( EXPR ));
2601                 //     InPlace::finalize(place)
2602                 // })
2603                 let placer_expr = P(self.lower_expr(placer));
2604                 let value_expr = P(self.lower_expr(value_expr));
2605
2606                 let placer_ident = self.str_to_ident("placer");
2607                 let place_ident = self.str_to_ident("place");
2608                 let p_ptr_ident = self.str_to_ident("p_ptr");
2609
2610                 let make_place = ["ops", "Placer", "make_place"];
2611                 let place_pointer = ["ops", "Place", "pointer"];
2612                 let move_val_init = ["intrinsics", "move_val_init"];
2613                 let inplace_finalize = ["ops", "InPlace", "finalize"];
2614
2615                 let unstable_span =
2616                     self.allow_internal_unstable(CompilerDesugaringKind::BackArrow, e.span);
2617                 let make_call = |this: &mut LoweringContext, p, args| {
2618                     let path = P(this.expr_std_path(unstable_span, p, ThinVec::new()));
2619                     P(this.expr_call(e.span, path, args))
2620                 };
2621
2622                 let mk_stmt_let = |this: &mut LoweringContext, bind, expr| {
2623                     this.stmt_let(e.span, false, bind, expr)
2624                 };
2625
2626                 let mk_stmt_let_mut = |this: &mut LoweringContext, bind, expr| {
2627                     this.stmt_let(e.span, true, bind, expr)
2628                 };
2629
2630                 // let placer = <placer_expr> ;
2631                 let (s1, placer_binding) = {
2632                     mk_stmt_let(self, placer_ident, placer_expr)
2633                 };
2634
2635                 // let mut place = Placer::make_place(placer);
2636                 let (s2, place_binding) = {
2637                     let placer = self.expr_ident(e.span, placer_ident, placer_binding);
2638                     let call = make_call(self, &make_place, hir_vec![placer]);
2639                     mk_stmt_let_mut(self, place_ident, call)
2640                 };
2641
2642                 // let p_ptr = Place::pointer(&mut place);
2643                 let (s3, p_ptr_binding) = {
2644                     let agent = P(self.expr_ident(e.span, place_ident, place_binding));
2645                     let args = hir_vec![self.expr_mut_addr_of(e.span, agent)];
2646                     let call = make_call(self, &place_pointer, args);
2647                     mk_stmt_let(self, p_ptr_ident, call)
2648                 };
2649
2650                 // pop_unsafe!(EXPR));
2651                 let pop_unsafe_expr = {
2652                     self.signal_block_expr(hir_vec![],
2653                                            value_expr,
2654                                            e.span,
2655                                            hir::PopUnsafeBlock(hir::CompilerGenerated),
2656                                            ThinVec::new())
2657                 };
2658
2659                 // push_unsafe!({
2660                 //     std::intrinsics::move_val_init(raw_place, pop_unsafe!( EXPR ));
2661                 //     InPlace::finalize(place)
2662                 // })
2663                 let expr = {
2664                     let ptr = self.expr_ident(e.span, p_ptr_ident, p_ptr_binding);
2665                     let call_move_val_init =
2666                         hir::StmtSemi(
2667                             make_call(self, &move_val_init, hir_vec![ptr, pop_unsafe_expr]),
2668                             self.next_id().node_id);
2669                     let call_move_val_init = respan(e.span, call_move_val_init);
2670
2671                     let place = self.expr_ident(e.span, place_ident, place_binding);
2672                     let call = make_call(self, &inplace_finalize, hir_vec![place]);
2673                     P(self.signal_block_expr(hir_vec![call_move_val_init],
2674                                              call,
2675                                              e.span,
2676                                              hir::PushUnsafeBlock(hir::CompilerGenerated),
2677                                              ThinVec::new()))
2678                 };
2679
2680                 let block = self.block_all(e.span, hir_vec![s1, s2, s3], Some(expr));
2681                 hir::ExprBlock(P(block))
2682             }
2683
2684             ExprKind::Array(ref exprs) => {
2685                 hir::ExprArray(exprs.iter().map(|x| self.lower_expr(x)).collect())
2686             }
2687             ExprKind::Repeat(ref expr, ref count) => {
2688                 let expr = P(self.lower_expr(expr));
2689                 let count = self.lower_body(None, |this| this.lower_expr(count));
2690                 hir::ExprRepeat(expr, count)
2691             }
2692             ExprKind::Tup(ref elts) => {
2693                 hir::ExprTup(elts.iter().map(|x| self.lower_expr(x)).collect())
2694             }
2695             ExprKind::Call(ref f, ref args) => {
2696                 let f = P(self.lower_expr(f));
2697                 hir::ExprCall(f, args.iter().map(|x| self.lower_expr(x)).collect())
2698             }
2699             ExprKind::MethodCall(ref seg, ref args) => {
2700                 let hir_seg = self.lower_path_segment(e.span, seg, ParamMode::Optional, 0,
2701                                                       ParenthesizedGenericArgs::Err,
2702                                                       ImplTraitContext::Disallowed);
2703                 let args = args.iter().map(|x| self.lower_expr(x)).collect();
2704                 hir::ExprMethodCall(hir_seg, seg.span, args)
2705             }
2706             ExprKind::Binary(binop, ref lhs, ref rhs) => {
2707                 let binop = self.lower_binop(binop);
2708                 let lhs = P(self.lower_expr(lhs));
2709                 let rhs = P(self.lower_expr(rhs));
2710                 hir::ExprBinary(binop, lhs, rhs)
2711             }
2712             ExprKind::Unary(op, ref ohs) => {
2713                 let op = self.lower_unop(op);
2714                 let ohs = P(self.lower_expr(ohs));
2715                 hir::ExprUnary(op, ohs)
2716             }
2717             ExprKind::Lit(ref l) => hir::ExprLit(P((**l).clone())),
2718             ExprKind::Cast(ref expr, ref ty) => {
2719                 let expr = P(self.lower_expr(expr));
2720                 hir::ExprCast(expr, self.lower_ty(ty, ImplTraitContext::Disallowed))
2721             }
2722             ExprKind::Type(ref expr, ref ty) => {
2723                 let expr = P(self.lower_expr(expr));
2724                 hir::ExprType(expr, self.lower_ty(ty, ImplTraitContext::Disallowed))
2725             }
2726             ExprKind::AddrOf(m, ref ohs) => {
2727                 let m = self.lower_mutability(m);
2728                 let ohs = P(self.lower_expr(ohs));
2729                 hir::ExprAddrOf(m, ohs)
2730             }
2731             // More complicated than you might expect because the else branch
2732             // might be `if let`.
2733             ExprKind::If(ref cond, ref blk, ref else_opt) => {
2734                 let else_opt = else_opt.as_ref().map(|els| {
2735                     match els.node {
2736                         ExprKind::IfLet(..) => {
2737                             // wrap the if-let expr in a block
2738                             let span = els.span;
2739                             let els = P(self.lower_expr(els));
2740                             let LoweredNodeId {
2741                                 node_id,
2742                                 hir_id,
2743                             } = self.next_id();
2744                             let blk = P(hir::Block {
2745                                 stmts: hir_vec![],
2746                                 expr: Some(els),
2747                                 id: node_id,
2748                                 hir_id,
2749                                 rules: hir::DefaultBlock,
2750                                 span,
2751                                 targeted_by_break: false,
2752                                 recovered: blk.recovered,
2753                             });
2754                             P(self.expr_block(blk, ThinVec::new()))
2755                         }
2756                         _ => P(self.lower_expr(els)),
2757                     }
2758                 });
2759
2760                 let then_blk = self.lower_block(blk, false);
2761                 let then_expr = self.expr_block(then_blk, ThinVec::new());
2762
2763                 hir::ExprIf(P(self.lower_expr(cond)), P(then_expr), else_opt)
2764             }
2765             ExprKind::While(ref cond, ref body, opt_ident) => {
2766                 self.with_loop_scope(e.id, |this|
2767                     hir::ExprWhile(
2768                         this.with_loop_condition_scope(|this| P(this.lower_expr(cond))),
2769                         this.lower_block(body, false),
2770                         this.lower_opt_sp_ident(opt_ident)))
2771             }
2772             ExprKind::Loop(ref body, opt_ident) => {
2773                 self.with_loop_scope(e.id, |this|
2774                     hir::ExprLoop(this.lower_block(body, false),
2775                                   this.lower_opt_sp_ident(opt_ident),
2776                                   hir::LoopSource::Loop))
2777             }
2778             ExprKind::Catch(ref body) => {
2779                 self.with_catch_scope(body.id, |this|
2780                     hir::ExprBlock(this.lower_block(body, true)))
2781             }
2782             ExprKind::Match(ref expr, ref arms) => {
2783                 hir::ExprMatch(P(self.lower_expr(expr)),
2784                                arms.iter().map(|x| self.lower_arm(x)).collect(),
2785                                hir::MatchSource::Normal)
2786             }
2787             ExprKind::Closure(capture_clause, ref decl, ref body, fn_decl_span) => {
2788                 self.with_new_scopes(|this| {
2789                     this.with_parent_def(e.id, |this| {
2790                         let mut is_generator = false;
2791                         let body_id = this.lower_body(Some(decl), |this| {
2792                             let e = this.lower_expr(body);
2793                             is_generator = this.is_generator;
2794                             e
2795                         });
2796                         if is_generator && !decl.inputs.is_empty() {
2797                             span_err!(this.sess, fn_decl_span, E0628,
2798                                       "generators cannot have explicit arguments");
2799                             this.sess.abort_if_errors();
2800                         }
2801                         hir::ExprClosure(this.lower_capture_clause(capture_clause),
2802                                          this.lower_fn_decl(decl, None, false),
2803                                          body_id,
2804                                          fn_decl_span,
2805                                          is_generator)
2806                     })
2807                 })
2808             }
2809             ExprKind::Block(ref blk) => hir::ExprBlock(self.lower_block(blk, false)),
2810             ExprKind::Assign(ref el, ref er) => {
2811                 hir::ExprAssign(P(self.lower_expr(el)), P(self.lower_expr(er)))
2812             }
2813             ExprKind::AssignOp(op, ref el, ref er) => {
2814                 hir::ExprAssignOp(self.lower_binop(op),
2815                                   P(self.lower_expr(el)),
2816                                   P(self.lower_expr(er)))
2817             }
2818             ExprKind::Field(ref el, ident) => {
2819                 hir::ExprField(P(self.lower_expr(el)),
2820                                respan(ident.span, self.lower_ident(ident.node)))
2821             }
2822             ExprKind::TupField(ref el, ident) => {
2823                 hir::ExprTupField(P(self.lower_expr(el)), ident)
2824             }
2825             ExprKind::Index(ref el, ref er) => {
2826                 hir::ExprIndex(P(self.lower_expr(el)), P(self.lower_expr(er)))
2827             }
2828             ExprKind::Range(ref e1, ref e2, lims) => {
2829                 use syntax::ast::RangeLimits::*;
2830
2831                 let path = match (e1, e2, lims) {
2832                     (&None, &None, HalfOpen) => "RangeFull",
2833                     (&Some(..), &None, HalfOpen) => "RangeFrom",
2834                     (&None, &Some(..), HalfOpen) => "RangeTo",
2835                     (&Some(..), &Some(..), HalfOpen) => "Range",
2836                     (&None, &Some(..), Closed) => "RangeToInclusive",
2837                     (&Some(..), &Some(..), Closed) => "RangeInclusive",
2838                     (_, &None, Closed) =>
2839                         panic!(self.diagnostic().span_fatal(
2840                             e.span, "inclusive range with no end")),
2841                 };
2842
2843                 let fields =
2844                     e1.iter().map(|e| ("start", e)).chain(e2.iter().map(|e| ("end", e)))
2845                     .map(|(s, e)| {
2846                         let expr = P(self.lower_expr(&e));
2847                         let unstable_span =
2848                             self.allow_internal_unstable(CompilerDesugaringKind::DotFill, e.span);
2849                         self.field(Symbol::intern(s), expr, unstable_span)
2850                     }).collect::<P<[hir::Field]>>();
2851
2852                 let is_unit = fields.is_empty();
2853                 let unstable_span =
2854                     self.allow_internal_unstable(CompilerDesugaringKind::DotFill, e.span);
2855                 let struct_path =
2856                     iter::once("ops").chain(iter::once(path))
2857                     .collect::<Vec<_>>();
2858                 let struct_path = self.std_path(unstable_span, &struct_path, is_unit);
2859                 let struct_path = hir::QPath::Resolved(None, P(struct_path));
2860
2861                 let LoweredNodeId { node_id, hir_id } = self.lower_node_id(e.id);
2862
2863                 return hir::Expr {
2864                     id: node_id,
2865                     hir_id,
2866                     node: if is_unit {
2867                         hir::ExprPath(struct_path)
2868                     } else {
2869                         hir::ExprStruct(struct_path, fields, None)
2870                     },
2871                     span: unstable_span,
2872                     attrs: e.attrs.clone(),
2873                 };
2874             }
2875             ExprKind::Path(ref qself, ref path) => {
2876                 hir::ExprPath(self.lower_qpath(e.id, qself, path, ParamMode::Optional,
2877                                                ImplTraitContext::Disallowed))
2878             }
2879             ExprKind::Break(opt_ident, ref opt_expr) => {
2880                 let label_result = if self.is_in_loop_condition && opt_ident.is_none() {
2881                     hir::Destination {
2882                         ident: opt_ident,
2883                         target_id: hir::ScopeTarget::Loop(
2884                                 Err(hir::LoopIdError::UnlabeledCfInWhileCondition).into()),
2885                     }
2886                 } else {
2887                     self.lower_loop_destination(opt_ident.map(|ident| (e.id, ident)))
2888                 };
2889                 hir::ExprBreak(
2890                         label_result,
2891                         opt_expr.as_ref().map(|x| P(self.lower_expr(x))))
2892             }
2893             ExprKind::Continue(opt_ident) =>
2894                 hir::ExprAgain(
2895                     if self.is_in_loop_condition && opt_ident.is_none() {
2896                         hir::Destination {
2897                             ident: opt_ident,
2898                             target_id: hir::ScopeTarget::Loop(Err(
2899                                 hir::LoopIdError::UnlabeledCfInWhileCondition).into()),
2900                         }
2901                     } else {
2902                         self.lower_loop_destination(opt_ident.map( |ident| (e.id, ident)))
2903                     }),
2904             ExprKind::Ret(ref e) => hir::ExprRet(e.as_ref().map(|x| P(self.lower_expr(x)))),
2905             ExprKind::InlineAsm(ref asm) => {
2906                 let hir_asm = hir::InlineAsm {
2907                     inputs: asm.inputs.iter().map(|&(ref c, _)| c.clone()).collect(),
2908                     outputs: asm.outputs.iter().map(|out| {
2909                         hir::InlineAsmOutput {
2910                             constraint: out.constraint.clone(),
2911                             is_rw: out.is_rw,
2912                             is_indirect: out.is_indirect,
2913                         }
2914                     }).collect(),
2915                     asm: asm.asm.clone(),
2916                     asm_str_style: asm.asm_str_style,
2917                     clobbers: asm.clobbers.clone().into(),
2918                     volatile: asm.volatile,
2919                     alignstack: asm.alignstack,
2920                     dialect: asm.dialect,
2921                     ctxt: asm.ctxt,
2922                 };
2923                 let outputs =
2924                     asm.outputs.iter().map(|out| self.lower_expr(&out.expr)).collect();
2925                 let inputs =
2926                     asm.inputs.iter().map(|&(_, ref input)| self.lower_expr(input)).collect();
2927                 hir::ExprInlineAsm(P(hir_asm), outputs, inputs)
2928             }
2929             ExprKind::Struct(ref path, ref fields, ref maybe_expr) => {
2930                 hir::ExprStruct(self.lower_qpath(e.id, &None, path, ParamMode::Optional,
2931                                                  ImplTraitContext::Disallowed),
2932                                 fields.iter().map(|x| self.lower_field(x)).collect(),
2933                                 maybe_expr.as_ref().map(|x| P(self.lower_expr(x))))
2934             }
2935             ExprKind::Paren(ref ex) => {
2936                 let mut ex = self.lower_expr(ex);
2937                 // include parens in span, but only if it is a super-span.
2938                 if e.span.contains(ex.span) {
2939                     ex.span = e.span;
2940                 }
2941                 // merge attributes into the inner expression.
2942                 let mut attrs = e.attrs.clone();
2943                 attrs.extend::<Vec<_>>(ex.attrs.into());
2944                 ex.attrs = attrs;
2945                 return ex;
2946             }
2947
2948             ExprKind::Yield(ref opt_expr) => {
2949                 self.is_generator = true;
2950                 let expr = opt_expr.as_ref().map(|x| self.lower_expr(x)).unwrap_or_else(|| {
2951                     self.expr(e.span, hir::ExprTup(hir_vec![]), ThinVec::new())
2952                 });
2953                 hir::ExprYield(P(expr))
2954             }
2955
2956             // Desugar ExprIfLet
2957             // From: `if let <pat> = <sub_expr> <body> [<else_opt>]`
2958             ExprKind::IfLet(ref pat, ref sub_expr, ref body, ref else_opt) => {
2959                 // to:
2960                 //
2961                 //   match <sub_expr> {
2962                 //     <pat> => <body>,
2963                 //     _ => [<else_opt> | ()]
2964                 //   }
2965
2966                 let mut arms = vec![];
2967
2968                 // `<pat> => <body>`
2969                 {
2970                     let body = self.lower_block(body, false);
2971                     let body_expr = P(self.expr_block(body, ThinVec::new()));
2972                     let pat = self.lower_pat(pat);
2973                     arms.push(self.arm(hir_vec![pat], body_expr));
2974                 }
2975
2976                 // _ => [<else_opt>|()]
2977                 {
2978                     let wildcard_arm: Option<&Expr> = else_opt.as_ref().map(|p| &**p);
2979                     let wildcard_pattern = self.pat_wild(e.span);
2980                     let body = if let Some(else_expr) = wildcard_arm {
2981                         P(self.lower_expr(else_expr))
2982                     } else {
2983                         self.expr_tuple(e.span, hir_vec![])
2984                     };
2985                     arms.push(self.arm(hir_vec![wildcard_pattern], body));
2986                 }
2987
2988                 let contains_else_clause = else_opt.is_some();
2989
2990                 let sub_expr = P(self.lower_expr(sub_expr));
2991
2992                 hir::ExprMatch(
2993                     sub_expr,
2994                     arms.into(),
2995                     hir::MatchSource::IfLetDesugar {
2996                         contains_else_clause,
2997                     })
2998             }
2999
3000             // Desugar ExprWhileLet
3001             // From: `[opt_ident]: while let <pat> = <sub_expr> <body>`
3002             ExprKind::WhileLet(ref pat, ref sub_expr, ref body, opt_ident) => {
3003                 // to:
3004                 //
3005                 //   [opt_ident]: loop {
3006                 //     match <sub_expr> {
3007                 //       <pat> => <body>,
3008                 //       _ => break
3009                 //     }
3010                 //   }
3011
3012                 // Note that the block AND the condition are evaluated in the loop scope.
3013                 // This is done to allow `break` from inside the condition of the loop.
3014                 let (body, break_expr, sub_expr) = self.with_loop_scope(e.id, |this| (
3015                     this.lower_block(body, false),
3016                     this.expr_break(e.span, ThinVec::new()),
3017                     this.with_loop_condition_scope(|this| P(this.lower_expr(sub_expr))),
3018                 ));
3019
3020                 // `<pat> => <body>`
3021                 let pat_arm = {
3022                     let body_expr = P(self.expr_block(body, ThinVec::new()));
3023                     let pat = self.lower_pat(pat);
3024                     self.arm(hir_vec![pat], body_expr)
3025                 };
3026
3027                 // `_ => break`
3028                 let break_arm = {
3029                     let pat_under = self.pat_wild(e.span);
3030                     self.arm(hir_vec![pat_under], break_expr)
3031                 };
3032
3033                 // `match <sub_expr> { ... }`
3034                 let arms = hir_vec![pat_arm, break_arm];
3035                 let match_expr = self.expr(e.span,
3036                                            hir::ExprMatch(sub_expr,
3037                                                           arms,
3038                                                           hir::MatchSource::WhileLetDesugar),
3039                                            ThinVec::new());
3040
3041                 // `[opt_ident]: loop { ... }`
3042                 let loop_block = P(self.block_expr(P(match_expr)));
3043                 let loop_expr = hir::ExprLoop(loop_block, self.lower_opt_sp_ident(opt_ident),
3044                                               hir::LoopSource::WhileLet);
3045                 // add attributes to the outer returned expr node
3046                 loop_expr
3047             }
3048
3049             // Desugar ExprForLoop
3050             // From: `[opt_ident]: for <pat> in <head> <body>`
3051             ExprKind::ForLoop(ref pat, ref head, ref body, opt_ident) => {
3052                 // to:
3053                 //
3054                 //   {
3055                 //     let result = match ::std::iter::IntoIterator::into_iter(<head>) {
3056                 //       mut iter => {
3057                 //         [opt_ident]: loop {
3058                 //           let mut __next;
3059                 //           match ::std::iter::Iterator::next(&mut iter) {
3060                 //             ::std::option::Option::Some(val) => __next = val,
3061                 //             ::std::option::Option::None => break
3062                 //           };
3063                 //           let <pat> = __next;
3064                 //           StmtExpr(<body>);
3065                 //         }
3066                 //       }
3067                 //     };
3068                 //     result
3069                 //   }
3070
3071                 // expand <head>
3072                 let head = self.lower_expr(head);
3073
3074                 let iter = self.str_to_ident("iter");
3075
3076                 let next_ident = self.str_to_ident("__next");
3077                 let next_pat = self.pat_ident_binding_mode(e.span,
3078                                                            next_ident,
3079                                                            hir::BindingAnnotation::Mutable);
3080
3081                 // `::std::option::Option::Some(val) => next = val`
3082                 let pat_arm = {
3083                     let val_ident = self.str_to_ident("val");
3084                     let val_pat = self.pat_ident(e.span, val_ident);
3085                     let val_expr = P(self.expr_ident(e.span, val_ident, val_pat.id));
3086                     let next_expr = P(self.expr_ident(e.span, next_ident, next_pat.id));
3087                     let assign = P(self.expr(e.span,
3088                                              hir::ExprAssign(next_expr, val_expr),
3089                                              ThinVec::new()));
3090                     let some_pat = self.pat_some(e.span, val_pat);
3091                     self.arm(hir_vec![some_pat], assign)
3092                 };
3093
3094                 // `::std::option::Option::None => break`
3095                 let break_arm = {
3096                     let break_expr = self.with_loop_scope(e.id, |this|
3097                         this.expr_break(e.span, ThinVec::new()));
3098                     let pat = self.pat_none(e.span);
3099                     self.arm(hir_vec![pat], break_expr)
3100                 };
3101
3102                 // `mut iter`
3103                 let iter_pat = self.pat_ident_binding_mode(e.span,
3104                                                            iter,
3105                                                            hir::BindingAnnotation::Mutable);
3106
3107                 // `match ::std::iter::Iterator::next(&mut iter) { ... }`
3108                 let match_expr = {
3109                     let iter = P(self.expr_ident(e.span, iter, iter_pat.id));
3110                     let ref_mut_iter = self.expr_mut_addr_of(e.span, iter);
3111                     let next_path = &["iter", "Iterator", "next"];
3112                     let next_path = P(self.expr_std_path(e.span, next_path, ThinVec::new()));
3113                     let next_expr = P(self.expr_call(e.span, next_path,
3114                                       hir_vec![ref_mut_iter]));
3115                     let arms = hir_vec![pat_arm, break_arm];
3116
3117                     P(self.expr(e.span,
3118                                 hir::ExprMatch(next_expr, arms,
3119                                                hir::MatchSource::ForLoopDesugar),
3120                                 ThinVec::new()))
3121                 };
3122                 let match_stmt = respan(e.span, hir::StmtExpr(match_expr, self.next_id().node_id));
3123
3124                 let next_expr = P(self.expr_ident(e.span, next_ident, next_pat.id));
3125
3126                 // `let mut __next`
3127                 let next_let = self.stmt_let_pat(e.span,
3128                     None,
3129                     next_pat,
3130                     hir::LocalSource::ForLoopDesugar);
3131
3132                 // `let <pat> = __next`
3133                 let pat = self.lower_pat(pat);
3134                 let pat_let = self.stmt_let_pat(e.span,
3135                     Some(next_expr),
3136                     pat,
3137                     hir::LocalSource::ForLoopDesugar);
3138
3139                 let body_block = self.with_loop_scope(e.id,
3140                                                         |this| this.lower_block(body, false));
3141                 let body_expr = P(self.expr_block(body_block, ThinVec::new()));
3142                 let body_stmt = respan(e.span, hir::StmtExpr(body_expr, self.next_id().node_id));
3143
3144                 let loop_block = P(self.block_all(e.span,
3145                                                   hir_vec![next_let,
3146                                                            match_stmt,
3147                                                            pat_let,
3148                                                            body_stmt],
3149                                                   None));
3150
3151                 // `[opt_ident]: loop { ... }`
3152                 let loop_expr = hir::ExprLoop(loop_block, self.lower_opt_sp_ident(opt_ident),
3153                                               hir::LoopSource::ForLoop);
3154                 let LoweredNodeId { node_id, hir_id } = self.lower_node_id(e.id);
3155                 let loop_expr = P(hir::Expr {
3156                     id: node_id,
3157                     hir_id,
3158                     node: loop_expr,
3159                     span: e.span,
3160                     attrs: ThinVec::new(),
3161                 });
3162
3163                 // `mut iter => { ... }`
3164                 let iter_arm = self.arm(hir_vec![iter_pat], loop_expr);
3165
3166                 // `match ::std::iter::IntoIterator::into_iter(<head>) { ... }`
3167                 let into_iter_expr = {
3168                     let into_iter_path = &["iter", "IntoIterator", "into_iter"];
3169                     let into_iter = P(self.expr_std_path(e.span, into_iter_path,
3170                                                          ThinVec::new()));
3171                     P(self.expr_call(e.span, into_iter, hir_vec![head]))
3172                 };
3173
3174                 let match_expr = P(self.expr_match(e.span,
3175                                                    into_iter_expr,
3176                                                    hir_vec![iter_arm],
3177                                                    hir::MatchSource::ForLoopDesugar));
3178
3179                 // `{ let _result = ...; _result }`
3180                 // underscore prevents an unused_variables lint if the head diverges
3181                 let result_ident = self.str_to_ident("_result");
3182                 let (let_stmt, let_stmt_binding) =
3183                     self.stmt_let(e.span, false, result_ident, match_expr);
3184
3185                 let result = P(self.expr_ident(e.span, result_ident, let_stmt_binding));
3186                 let block = P(self.block_all(e.span, hir_vec![let_stmt], Some(result)));
3187                 // add the attributes to the outer returned expr node
3188                 return self.expr_block(block, e.attrs.clone());
3189             }
3190
3191             // Desugar ExprKind::Try
3192             // From: `<expr>?`
3193             ExprKind::Try(ref sub_expr) => {
3194                 // to:
3195                 //
3196                 // match Try::into_result(<expr>) {
3197                 //     Ok(val) => #[allow(unreachable_code)] val,
3198                 //     Err(err) => #[allow(unreachable_code)]
3199                 //                 // If there is an enclosing `catch {...}`
3200                 //                 break 'catch_target Try::from_error(From::from(err)),
3201                 //                 // Otherwise
3202                 //                 return Try::from_error(From::from(err)),
3203                 // }
3204
3205                 let unstable_span =
3206                     self.allow_internal_unstable(CompilerDesugaringKind::QuestionMark, e.span);
3207
3208                 // Try::into_result(<expr>)
3209                 let discr = {
3210                     // expand <expr>
3211                     let sub_expr = self.lower_expr(sub_expr);
3212
3213                     let path = &["ops", "Try", "into_result"];
3214                     let path = P(self.expr_std_path(unstable_span, path, ThinVec::new()));
3215                     P(self.expr_call(e.span, path, hir_vec![sub_expr]))
3216                 };
3217
3218                 // #[allow(unreachable_code)]
3219                 let attr = {
3220                     // allow(unreachable_code)
3221                     let allow = {
3222                         let allow_ident = self.str_to_ident("allow");
3223                         let uc_ident = self.str_to_ident("unreachable_code");
3224                         let uc_meta_item = attr::mk_spanned_word_item(e.span, uc_ident);
3225                         let uc_nested = NestedMetaItemKind::MetaItem(uc_meta_item);
3226                         let uc_spanned = respan(e.span, uc_nested);
3227                         attr::mk_spanned_list_item(e.span, allow_ident, vec![uc_spanned])
3228                     };
3229                     attr::mk_spanned_attr_outer(e.span, attr::mk_attr_id(), allow)
3230                 };
3231                 let attrs = vec![attr];
3232
3233                 // Ok(val) => #[allow(unreachable_code)] val,
3234                 let ok_arm = {
3235                     let val_ident = self.str_to_ident("val");
3236                     let val_pat = self.pat_ident(e.span, val_ident);
3237                     let val_expr = P(self.expr_ident_with_attrs(e.span,
3238                                                                 val_ident,
3239                                                                 val_pat.id,
3240                                                                 ThinVec::from(attrs.clone())));
3241                     let ok_pat = self.pat_ok(e.span, val_pat);
3242
3243                     self.arm(hir_vec![ok_pat], val_expr)
3244                 };
3245
3246                 // Err(err) => #[allow(unreachable_code)]
3247                 //             return Try::from_error(From::from(err)),
3248                 let err_arm = {
3249                     let err_ident = self.str_to_ident("err");
3250                     let err_local = self.pat_ident(e.span, err_ident);
3251                     let from_expr = {
3252                         let path = &["convert", "From", "from"];
3253                         let from = P(self.expr_std_path(e.span, path, ThinVec::new()));
3254                         let err_expr = self.expr_ident(e.span, err_ident, err_local.id);
3255
3256                         self.expr_call(e.span, from, hir_vec![err_expr])
3257                     };
3258                     let from_err_expr = {
3259                         let path = &["ops", "Try", "from_error"];
3260                         let from_err = P(self.expr_std_path(unstable_span, path,
3261                                                             ThinVec::new()));
3262                         P(self.expr_call(e.span, from_err, hir_vec![from_expr]))
3263                     };
3264
3265                     let thin_attrs = ThinVec::from(attrs);
3266                     let catch_scope = self.catch_scopes.last().map(|x| *x);
3267                     let ret_expr = if let Some(catch_node) = catch_scope {
3268                         P(self.expr(
3269                             e.span,
3270                             hir::ExprBreak(
3271                                 hir::Destination {
3272                                     ident: None,
3273                                     target_id: hir::ScopeTarget::Block(catch_node),
3274                                 },
3275                                 Some(from_err_expr)
3276                             ),
3277                             thin_attrs))
3278                     } else {
3279                         P(self.expr(e.span,
3280                                     hir::Expr_::ExprRet(Some(from_err_expr)),
3281                                     thin_attrs))
3282                     };
3283
3284
3285                     let err_pat = self.pat_err(e.span, err_local);
3286                     self.arm(hir_vec![err_pat], ret_expr)
3287                 };
3288
3289                 hir::ExprMatch(discr,
3290                                hir_vec![err_arm, ok_arm],
3291                                hir::MatchSource::TryDesugar)
3292             }
3293
3294             ExprKind::Mac(_) => panic!("Shouldn't exist here"),
3295         };
3296
3297         let LoweredNodeId { node_id, hir_id } = self.lower_node_id(e.id);
3298
3299         hir::Expr {
3300             id: node_id,
3301             hir_id,
3302             node: kind,
3303             span: e.span,
3304             attrs: e.attrs.clone(),
3305         }
3306     }
3307
3308     fn lower_stmt(&mut self, s: &Stmt) -> SmallVector<hir::Stmt> {
3309         SmallVector::one(match s.node {
3310             StmtKind::Local(ref l) => Spanned {
3311                 node: hir::StmtDecl(P(Spanned {
3312                     node: hir::DeclLocal(self.lower_local(l)),
3313                     span: s.span,
3314                 }), self.lower_node_id(s.id).node_id),
3315                 span: s.span,
3316             },
3317             StmtKind::Item(ref it) => {
3318                 // Can only use the ID once.
3319                 let mut id = Some(s.id);
3320                 return self.lower_item_id(it).into_iter().map(|item_id| Spanned {
3321                     node: hir::StmtDecl(P(Spanned {
3322                         node: hir::DeclItem(item_id),
3323                         span: s.span,
3324                     }), id.take()
3325                           .map(|id| self.lower_node_id(id).node_id)
3326                           .unwrap_or_else(|| self.next_id().node_id)),
3327                     span: s.span,
3328                 }).collect();
3329             }
3330             StmtKind::Expr(ref e) => {
3331                 Spanned {
3332                     node: hir::StmtExpr(P(self.lower_expr(e)),
3333                                           self.lower_node_id(s.id).node_id),
3334                     span: s.span,
3335                 }
3336             }
3337             StmtKind::Semi(ref e) => {
3338                 Spanned {
3339                     node: hir::StmtSemi(P(self.lower_expr(e)),
3340                                           self.lower_node_id(s.id).node_id),
3341                     span: s.span,
3342                 }
3343             }
3344             StmtKind::Mac(..) => panic!("Shouldn't exist here"),
3345         })
3346     }
3347
3348     fn lower_capture_clause(&mut self, c: CaptureBy) -> hir::CaptureClause {
3349         match c {
3350             CaptureBy::Value => hir::CaptureByValue,
3351             CaptureBy::Ref => hir::CaptureByRef,
3352         }
3353     }
3354
3355     /// If an `explicit_owner` is given, this method allocates the `HirId` in
3356     /// the address space of that item instead of the item currently being
3357     /// lowered. This can happen during `lower_impl_item_ref()` where we need to
3358     /// lower a `Visibility` value although we haven't lowered the owning
3359     /// `ImplItem` in question yet.
3360     fn lower_visibility(&mut self,
3361                         v: &Visibility,
3362                         explicit_owner: Option<NodeId>)
3363                         -> hir::Visibility {
3364         match *v {
3365             Visibility::Public => hir::Public,
3366             Visibility::Crate(..) => hir::Visibility::Crate,
3367             Visibility::Restricted { ref path, id } => {
3368                 hir::Visibility::Restricted {
3369                     path: P(self.lower_path(id, path, ParamMode::Explicit, true)),
3370                     id: if let Some(owner) = explicit_owner {
3371                         self.lower_node_id_with_owner(id, owner).node_id
3372                     } else {
3373                         self.lower_node_id(id).node_id
3374                     }
3375                 }
3376             }
3377             Visibility::Inherited => hir::Inherited,
3378         }
3379     }
3380
3381     fn lower_defaultness(&mut self, d: Defaultness, has_value: bool) -> hir::Defaultness {
3382         match d {
3383             Defaultness::Default => hir::Defaultness::Default { has_value: has_value },
3384             Defaultness::Final => {
3385                 assert!(has_value);
3386                 hir::Defaultness::Final
3387             }
3388         }
3389     }
3390
3391     fn lower_block_check_mode(&mut self, b: &BlockCheckMode) -> hir::BlockCheckMode {
3392         match *b {
3393             BlockCheckMode::Default => hir::DefaultBlock,
3394             BlockCheckMode::Unsafe(u) => hir::UnsafeBlock(self.lower_unsafe_source(u)),
3395         }
3396     }
3397
3398     fn lower_binding_mode(&mut self, b: &BindingMode) -> hir::BindingAnnotation {
3399         match *b {
3400             BindingMode::ByValue(Mutability::Immutable) =>
3401                 hir::BindingAnnotation::Unannotated,
3402             BindingMode::ByRef(Mutability::Immutable) => hir::BindingAnnotation::Ref,
3403             BindingMode::ByValue(Mutability::Mutable) => hir::BindingAnnotation::Mutable,
3404             BindingMode::ByRef(Mutability::Mutable) => hir::BindingAnnotation::RefMut,
3405         }
3406     }
3407
3408     fn lower_unsafe_source(&mut self, u: UnsafeSource) -> hir::UnsafeSource {
3409         match u {
3410             CompilerGenerated => hir::CompilerGenerated,
3411             UserProvided => hir::UserProvided,
3412         }
3413     }
3414
3415     fn lower_impl_polarity(&mut self, i: ImplPolarity) -> hir::ImplPolarity {
3416         match i {
3417             ImplPolarity::Positive => hir::ImplPolarity::Positive,
3418             ImplPolarity::Negative => hir::ImplPolarity::Negative,
3419         }
3420     }
3421
3422     fn lower_trait_bound_modifier(&mut self, f: TraitBoundModifier) -> hir::TraitBoundModifier {
3423         match f {
3424             TraitBoundModifier::None => hir::TraitBoundModifier::None,
3425             TraitBoundModifier::Maybe => hir::TraitBoundModifier::Maybe,
3426         }
3427     }
3428
3429     // Helper methods for building HIR.
3430
3431     fn arm(&mut self, pats: hir::HirVec<P<hir::Pat>>, expr: P<hir::Expr>) -> hir::Arm {
3432         hir::Arm {
3433             attrs: hir_vec![],
3434             pats,
3435             guard: None,
3436             body: expr,
3437         }
3438     }
3439
3440     fn field(&mut self, name: Name, expr: P<hir::Expr>, span: Span) -> hir::Field {
3441         hir::Field {
3442             name: Spanned {
3443                 node: name,
3444                 span,
3445             },
3446             span,
3447             expr,
3448             is_shorthand: false,
3449         }
3450     }
3451
3452     fn expr_break(&mut self, span: Span, attrs: ThinVec<Attribute>) -> P<hir::Expr> {
3453         let expr_break = hir::ExprBreak(self.lower_loop_destination(None), None);
3454         P(self.expr(span, expr_break, attrs))
3455     }
3456
3457     fn expr_call(&mut self, span: Span, e: P<hir::Expr>, args: hir::HirVec<hir::Expr>)
3458                  -> hir::Expr {
3459         self.expr(span, hir::ExprCall(e, args), ThinVec::new())
3460     }
3461
3462     fn expr_ident(&mut self, span: Span, id: Name, binding: NodeId) -> hir::Expr {
3463         self.expr_ident_with_attrs(span, id, binding, ThinVec::new())
3464     }
3465
3466     fn expr_ident_with_attrs(&mut self, span: Span,
3467                                         id: Name,
3468                                         binding: NodeId,
3469                                         attrs: ThinVec<Attribute>) -> hir::Expr {
3470         let expr_path = hir::ExprPath(hir::QPath::Resolved(None, P(hir::Path {
3471             span,
3472             def: Def::Local(binding),
3473             segments: hir_vec![hir::PathSegment::from_name(id)],
3474         })));
3475
3476         self.expr(span, expr_path, attrs)
3477     }
3478
3479     fn expr_mut_addr_of(&mut self, span: Span, e: P<hir::Expr>) -> hir::Expr {
3480         self.expr(span, hir::ExprAddrOf(hir::MutMutable, e), ThinVec::new())
3481     }
3482
3483     fn expr_std_path(&mut self,
3484                      span: Span,
3485                      components: &[&str],
3486                      attrs: ThinVec<Attribute>)
3487                      -> hir::Expr {
3488         let path = self.std_path(span, components, true);
3489         self.expr(span, hir::ExprPath(hir::QPath::Resolved(None, P(path))), attrs)
3490     }
3491
3492     fn expr_match(&mut self,
3493                   span: Span,
3494                   arg: P<hir::Expr>,
3495                   arms: hir::HirVec<hir::Arm>,
3496                   source: hir::MatchSource)
3497                   -> hir::Expr {
3498         self.expr(span, hir::ExprMatch(arg, arms, source), ThinVec::new())
3499     }
3500
3501     fn expr_block(&mut self, b: P<hir::Block>, attrs: ThinVec<Attribute>) -> hir::Expr {
3502         self.expr(b.span, hir::ExprBlock(b), attrs)
3503     }
3504
3505     fn expr_tuple(&mut self, sp: Span, exprs: hir::HirVec<hir::Expr>) -> P<hir::Expr> {
3506         P(self.expr(sp, hir::ExprTup(exprs), ThinVec::new()))
3507     }
3508
3509     fn expr(&mut self, span: Span, node: hir::Expr_, attrs: ThinVec<Attribute>) -> hir::Expr {
3510         let LoweredNodeId { node_id, hir_id } = self.next_id();
3511         hir::Expr {
3512             id: node_id,
3513             hir_id,
3514             node,
3515             span,
3516             attrs,
3517         }
3518     }
3519
3520     fn stmt_let_pat(&mut self,
3521                     sp: Span,
3522                     ex: Option<P<hir::Expr>>,
3523                     pat: P<hir::Pat>,
3524                     source: hir::LocalSource)
3525                     -> hir::Stmt {
3526         let LoweredNodeId { node_id, hir_id } = self.next_id();
3527
3528         let local = P(hir::Local {
3529             pat,
3530             ty: None,
3531             init: ex,
3532             id: node_id,
3533             hir_id,
3534             span: sp,
3535             attrs: ThinVec::new(),
3536             source,
3537         });
3538         let decl = respan(sp, hir::DeclLocal(local));
3539         respan(sp, hir::StmtDecl(P(decl), self.next_id().node_id))
3540     }
3541
3542     fn stmt_let(&mut self, sp: Span, mutbl: bool, ident: Name, ex: P<hir::Expr>)
3543                 -> (hir::Stmt, NodeId) {
3544         let pat = if mutbl {
3545             self.pat_ident_binding_mode(sp, ident, hir::BindingAnnotation::Mutable)
3546         } else {
3547             self.pat_ident(sp, ident)
3548         };
3549         let pat_id = pat.id;
3550         (self.stmt_let_pat(sp, Some(ex), pat, hir::LocalSource::Normal), pat_id)
3551     }
3552
3553     fn block_expr(&mut self, expr: P<hir::Expr>) -> hir::Block {
3554         self.block_all(expr.span, hir::HirVec::new(), Some(expr))
3555     }
3556
3557     fn block_all(&mut self, span: Span, stmts: hir::HirVec<hir::Stmt>, expr: Option<P<hir::Expr>>)
3558                  -> hir::Block {
3559         let LoweredNodeId { node_id, hir_id } = self.next_id();
3560
3561         hir::Block {
3562             stmts,
3563             expr,
3564             id: node_id,
3565             hir_id,
3566             rules: hir::DefaultBlock,
3567             span,
3568             targeted_by_break: false,
3569             recovered: false,
3570         }
3571     }
3572
3573     fn pat_ok(&mut self, span: Span, pat: P<hir::Pat>) -> P<hir::Pat> {
3574         self.pat_std_enum(span, &["result", "Result", "Ok"], hir_vec![pat])
3575     }
3576
3577     fn pat_err(&mut self, span: Span, pat: P<hir::Pat>) -> P<hir::Pat> {
3578         self.pat_std_enum(span, &["result", "Result", "Err"], hir_vec![pat])
3579     }
3580
3581     fn pat_some(&mut self, span: Span, pat: P<hir::Pat>) -> P<hir::Pat> {
3582         self.pat_std_enum(span, &["option", "Option", "Some"], hir_vec![pat])
3583     }
3584
3585     fn pat_none(&mut self, span: Span) -> P<hir::Pat> {
3586         self.pat_std_enum(span, &["option", "Option", "None"], hir_vec![])
3587     }
3588
3589     fn pat_std_enum(&mut self,
3590                     span: Span,
3591                     components: &[&str],
3592                     subpats: hir::HirVec<P<hir::Pat>>)
3593                     -> P<hir::Pat> {
3594         let path = self.std_path(span, components, true);
3595         let qpath = hir::QPath::Resolved(None, P(path));
3596         let pt = if subpats.is_empty() {
3597             hir::PatKind::Path(qpath)
3598         } else {
3599             hir::PatKind::TupleStruct(qpath, subpats, None)
3600         };
3601         self.pat(span, pt)
3602     }
3603
3604     fn pat_ident(&mut self, span: Span, name: Name) -> P<hir::Pat> {
3605         self.pat_ident_binding_mode(span, name, hir::BindingAnnotation::Unannotated)
3606     }
3607
3608     fn pat_ident_binding_mode(&mut self, span: Span, name: Name, bm: hir::BindingAnnotation)
3609                               -> P<hir::Pat> {
3610         let LoweredNodeId { node_id, hir_id } = self.next_id();
3611
3612         P(hir::Pat {
3613             id: node_id,
3614             hir_id,
3615             node: hir::PatKind::Binding(bm,
3616                                         node_id,
3617                                         Spanned {
3618                                             span,
3619                                             node: name,
3620                                         },
3621                                         None),
3622             span,
3623         })
3624     }
3625
3626     fn pat_wild(&mut self, span: Span) -> P<hir::Pat> {
3627         self.pat(span, hir::PatKind::Wild)
3628     }
3629
3630     fn pat(&mut self, span: Span, pat: hir::PatKind) -> P<hir::Pat> {
3631         let LoweredNodeId { node_id, hir_id } = self.next_id();
3632         P(hir::Pat {
3633             id: node_id,
3634             hir_id,
3635             node: pat,
3636             span,
3637         })
3638     }
3639
3640     /// Given suffix ["b","c","d"], returns path `::std::b::c::d` when
3641     /// `fld.cx.use_std`, and `::core::b::c::d` otherwise.
3642     /// The path is also resolved according to `is_value`.
3643     fn std_path(&mut self, span: Span, components: &[&str], is_value: bool) -> hir::Path {
3644         self.resolver.resolve_str_path(span, self.crate_root, components, is_value)
3645     }
3646
3647     fn signal_block_expr(&mut self,
3648                          stmts: hir::HirVec<hir::Stmt>,
3649                          expr: P<hir::Expr>,
3650                          span: Span,
3651                          rule: hir::BlockCheckMode,
3652                          attrs: ThinVec<Attribute>)
3653                          -> hir::Expr {
3654         let LoweredNodeId { node_id, hir_id } = self.next_id();
3655
3656         let block = P(hir::Block {
3657             rules: rule,
3658             span,
3659             id: node_id,
3660             hir_id,
3661             stmts,
3662             expr: Some(expr),
3663             targeted_by_break: false,
3664             recovered: false,
3665         });
3666         self.expr_block(block, attrs)
3667     }
3668
3669     fn ty_path(&mut self, id: LoweredNodeId, span: Span, qpath: hir::QPath) -> P<hir::Ty> {
3670         let mut id = id;
3671         let node = match qpath {
3672             hir::QPath::Resolved(None, path) => {
3673                 // Turn trait object paths into `TyTraitObject` instead.
3674                 if let Def::Trait(_) = path.def {
3675                     let principal = hir::PolyTraitRef {
3676                         bound_generic_params: hir::HirVec::new(),
3677                         trait_ref: hir::TraitRef {
3678                             path: path.and_then(|path| path),
3679                             ref_id: id.node_id,
3680                         },
3681                         span,
3682                     };
3683
3684                     // The original ID is taken by the `PolyTraitRef`,
3685                     // so the `Ty` itself needs a different one.
3686                     id = self.next_id();
3687
3688                     hir::TyTraitObject(hir_vec![principal], self.elided_lifetime(span))
3689                 } else {
3690                     hir::TyPath(hir::QPath::Resolved(None, path))
3691                 }
3692             }
3693             _ => hir::TyPath(qpath)
3694         };
3695         P(hir::Ty { id: id.node_id, hir_id: id.hir_id, node, span })
3696     }
3697
3698     fn elided_lifetime(&mut self, span: Span) -> hir::Lifetime {
3699         hir::Lifetime {
3700             id: self.next_id().node_id,
3701             span,
3702             name: hir::LifetimeName::Implicit,
3703         }
3704     }
3705 }
3706
3707 fn body_ids(bodies: &BTreeMap<hir::BodyId, hir::Body>) -> Vec<hir::BodyId> {
3708     // Sorting by span ensures that we get things in order within a
3709     // file, and also puts the files in a sensible order.
3710     let mut body_ids: Vec<_> = bodies.keys().cloned().collect();
3711     body_ids.sort_by_key(|b| bodies[b].value.span);
3712     body_ids
3713 }