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