src/librustc/middle/const_eval.rs

   1 // Copyright 2012-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 //#![allow(non_camel_case_types)]
  12
  13 use self::ConstVal::*;
  14 use self::ErrKind::*;
  15 use self::EvalHint::*;
  16
  17 use front::map as ast_map;
  18 use front::map::blocks::FnLikeNode;
  19 use metadata::csearch;
  20 use metadata::inline::InlinedItem;
  21 use middle::{astencode, def, infer, subst, traits};
  22 use middle::def_id::{DefId};
  23 use middle::pat_util::def_to_path;
  24 use middle::ty::{self, Ty};
  25 use middle::astconv_util::ast_ty_to_prim_ty;
  26 use util::num::ToPrimitive;
  27
  28 use syntax::ast;
  29 use rustc_front::hir::Expr;
  30 use rustc_front::hir;
  31 use rustc_front::visit::FnKind;
  32 use syntax::codemap::Span;
  33 use syntax::parse::token::InternedString;
  34 use syntax::ptr::P;
  35 use syntax::codemap;
  36
  37 use std::borrow::{Cow, IntoCow};
  38 use std::num::wrapping::OverflowingOps;
  39 use std::cmp::Ordering;
  40 use std::collections::hash_map::Entry::Vacant;
  41 use std::{i8, i16, i32, i64, u8, u16, u32, u64};
  42 use std::rc::Rc;
  43
  44 fn lookup_const<'a>(tcx: &'a ty::ctxt, e: &Expr) -> Option<&'a Expr> {
  45     let opt_def = tcx.def_map.borrow().get(&e.id).map(|d| d.full_def());
  46     match opt_def {
  47         Some(def::DefConst(def_id)) |
  48         Some(def::DefAssociatedConst(def_id)) => {
  49             lookup_const_by_id(tcx, def_id, Some(e.id))
  50         }
  51         Some(def::DefVariant(enum_def, variant_def, _)) => {
  52             lookup_variant_by_id(tcx, enum_def, variant_def)
  53         }
  54         _ => None
  55     }
  56 }
  57
  58 fn lookup_variant_by_id<'a>(tcx: &'a ty::ctxt,
  59                             enum_def: DefId,
  60                             variant_def: DefId)
  61                             -> Option<&'a Expr> {
  62     fn variant_expr<'a>(variants: &'a [P<hir::Variant>], id: ast::NodeId)
  63                         -> Option<&'a Expr> {
  64         for variant in variants {
  65             if variant.node.id == id {
  66                 return variant.node.disr_expr.as_ref().map(|e| &**e);
  67             }
  68         }
  69         None
  70     }
  71
  72     if enum_def.is_local() {
  73         match tcx.map.find(enum_def.node) {
  74             None => None,
  75             Some(ast_map::NodeItem(it)) => match it.node {
  76                 hir::ItemEnum(hir::EnumDef { ref variants }, _) => {
  77                     variant_expr(&variants[..], variant_def.node)
  78                 }
  79                 _ => None
  80             },
  81             Some(_) => None
  82         }
  83     } else {
  84         match tcx.extern_const_variants.borrow().get(&variant_def) {
  85             Some(&ast::DUMMY_NODE_ID) => return None,
  86             Some(&expr_id) => {
  87                 return Some(tcx.map.expect_expr(expr_id));
  88             }
  89             None => {}
  90         }
  91         let expr_id = match csearch::maybe_get_item_ast(tcx, enum_def,
  92             Box::new(|a, b, c, d| astencode::decode_inlined_item(a, b, c, d))) {
  93             csearch::FoundAst::Found(&InlinedItem::Item(ref item)) => match item.node {
  94                 hir::ItemEnum(hir::EnumDef { ref variants }, _) => {
  95                     // NOTE this doesn't do the right thing, it compares inlined
  96                     // NodeId's to the original variant_def's NodeId, but they
  97                     // come from different crates, so they will likely never match.
  98                     variant_expr(&variants[..], variant_def.node).map(|e| e.id)
  99                 }
 100                 _ => None
 101             },
 102             _ => None
 103         };
 104         tcx.extern_const_variants.borrow_mut().insert(variant_def,
 105                                                       expr_id.unwrap_or(ast::DUMMY_NODE_ID));
 106         expr_id.map(|id| tcx.map.expect_expr(id))
 107     }
 108 }
 109
 110 pub fn lookup_const_by_id<'a, 'tcx: 'a>(tcx: &'a ty::ctxt<'tcx>,
 111                                         def_id: DefId,
 112                                         maybe_ref_id: Option<ast::NodeId>)
 113                                         -> Option<&'tcx Expr> {
 114     if def_id.is_local() {
 115         match tcx.map.find(def_id.node) {
 116             None => None,
 117             Some(ast_map::NodeItem(it)) => match it.node {
 118                 hir::ItemConst(_, ref const_expr) => {
 119                     Some(&*const_expr)
 120                 }
 121                 _ => None
 122             },
 123             Some(ast_map::NodeTraitItem(ti)) => match ti.node {
 124                 hir::ConstTraitItem(_, _) => {
 125                     match maybe_ref_id {
 126                         // If we have a trait item, and we know the expression
 127                         // that's the source of the obligation to resolve it,
 128                         // `resolve_trait_associated_const` will select an impl
 129                         // or the default.
 130                         Some(ref_id) => {
 131                             let trait_id = tcx.trait_of_item(def_id)
 132                                               .unwrap();
 133                             let substs = tcx.node_id_item_substs(ref_id)
 134                                             .substs;
 135                             resolve_trait_associated_const(tcx, ti, trait_id,
 136                                                            substs)
 137                         }
 138                         // Technically, without knowing anything about the
 139                         // expression that generates the obligation, we could
 140                         // still return the default if there is one. However,
 141                         // it's safer to return `None` than to return some value
 142                         // that may differ from what you would get from
 143                         // correctly selecting an impl.
 144                         None => None
 145                     }
 146                 }
 147                 _ => None
 148             },
 149             Some(ast_map::NodeImplItem(ii)) => match ii.node {
 150                 hir::ConstImplItem(_, ref expr) => {
 151                     Some(&*expr)
 152                 }
 153                 _ => None
 154             },
 155             Some(_) => None
 156         }
 157     } else {
 158         match tcx.extern_const_statics.borrow().get(&def_id) {
 159             Some(&ast::DUMMY_NODE_ID) => return None,
 160             Some(&expr_id) => {
 161                 return Some(tcx.map.expect_expr(expr_id));
 162             }
 163             None => {}
 164         }
 165         let mut used_ref_id = false;
 166         let expr_id = match csearch::maybe_get_item_ast(tcx, def_id,
 167             Box::new(|a, b, c, d| astencode::decode_inlined_item(a, b, c, d))) {
 168             csearch::FoundAst::Found(&InlinedItem::Item(ref item)) => match item.node {
 169                 hir::ItemConst(_, ref const_expr) => Some(const_expr.id),
 170                 _ => None
 171             },
 172             csearch::FoundAst::Found(&InlinedItem::TraitItem(trait_id, ref ti)) => match ti.node {
 173                 hir::ConstTraitItem(_, _) => {
 174                     used_ref_id = true;
 175                     match maybe_ref_id {
 176                         // As mentioned in the comments above for in-crate
 177                         // constants, we only try to find the expression for
 178                         // a trait-associated const if the caller gives us
 179                         // the expression that refers to it.
 180                         Some(ref_id) => {
 181                             let substs = tcx.node_id_item_substs(ref_id)
 182                                             .substs;
 183                             resolve_trait_associated_const(tcx, ti, trait_id,
 184                                                            substs).map(|e| e.id)
 185                         }
 186                         None => None
 187                     }
 188                 }
 189                 _ => None
 190             },
 191             csearch::FoundAst::Found(&InlinedItem::ImplItem(_, ref ii)) => match ii.node {
 192                 hir::ConstImplItem(_, ref expr) => Some(expr.id),
 193                 _ => None
 194             },
 195             _ => None
 196         };
 197         // If we used the reference expression, particularly to choose an impl
 198         // of a trait-associated const, don't cache that, because the next
 199         // lookup with the same def_id may yield a different result.
 200         if !used_ref_id {
 201             tcx.extern_const_statics
 202                .borrow_mut().insert(def_id,
 203                                     expr_id.unwrap_or(ast::DUMMY_NODE_ID));
 204         }
 205         expr_id.map(|id| tcx.map.expect_expr(id))
 206     }
 207 }
 208
 209 fn inline_const_fn_from_external_crate(tcx: &ty::ctxt, def_id: DefId)
 210                                        -> Option<ast::NodeId> {
 211     match tcx.extern_const_fns.borrow().get(&def_id) {
 212         Some(&ast::DUMMY_NODE_ID) => return None,
 213         Some(&fn_id) => return Some(fn_id),
 214         None => {}
 215     }
 216
 217     if !csearch::is_const_fn(&tcx.sess.cstore, def_id) {
 218         tcx.extern_const_fns.borrow_mut().insert(def_id, ast::DUMMY_NODE_ID);
 219         return None;
 220     }
 221
 222     let fn_id = match csearch::maybe_get_item_ast(tcx, def_id,
 223         box |a, b, c, d| astencode::decode_inlined_item(a, b, c, d)) {
 224         csearch::FoundAst::Found(&InlinedItem::Item(ref item)) => Some(item.id),
 225         csearch::FoundAst::Found(&InlinedItem::ImplItem(_, ref item)) => Some(item.id),
 226         _ => None
 227     };
 228     tcx.extern_const_fns.borrow_mut().insert(def_id,
 229                                              fn_id.unwrap_or(ast::DUMMY_NODE_ID));
 230     fn_id
 231 }
 232
 233 pub fn lookup_const_fn_by_id<'tcx>(tcx: &ty::ctxt<'tcx>, def_id: DefId)
 234                                    -> Option<FnLikeNode<'tcx>>
 235 {
 236     let fn_id = if !def_id.is_local() {
 237         if let Some(fn_id) = inline_const_fn_from_external_crate(tcx, def_id) {
 238             fn_id
 239         } else {
 240             return None;
 241         }
 242     } else {
 243         def_id.node
 244     };
 245
 246     let fn_like = match FnLikeNode::from_node(tcx.map.get(fn_id)) {
 247         Some(fn_like) => fn_like,
 248         None => return None
 249     };
 250
 251     match fn_like.kind() {
 252         FnKind::ItemFn(_, _, _, hir::Constness::Const, _, _) => {
 253             Some(fn_like)
 254         }
 255         FnKind::Method(_, m, _) => {
 256             if m.constness == hir::Constness::Const {
 257                 Some(fn_like)
 258             } else {
 259                 None
 260             }
 261         }
 262         _ => None
 263     }
 264 }
 265
 266 #[derive(Clone, PartialEq)]
 267 pub enum ConstVal {
 268     Float(f64),
 269     Int(i64),
 270     Uint(u64),
 271     Str(InternedString),
 272     ByteStr(Rc<Vec<u8>>),
 273     Bool(bool),
 274     Struct(ast::NodeId),
 275     Tuple(ast::NodeId),
 276 }
 277
 278 impl ConstVal {
 279     pub fn description(&self) -> &'static str {
 280         match *self {
 281             Float(_) => "float",
 282             Int(i) if i < 0 => "negative integer",
 283             Int(_) => "positive integer",
 284             Uint(_) => "unsigned integer",
 285             Str(_) => "string literal",
 286             ByteStr(_) => "byte string literal",
 287             Bool(_) => "boolean",
 288             Struct(_) => "struct",
 289             Tuple(_) => "tuple",
 290         }
 291     }
 292 }
 293
 294 pub fn const_expr_to_pat(tcx: &ty::ctxt, expr: &Expr, span: Span) -> P<hir::Pat> {
 295     let pat = match expr.node {
 296         hir::ExprTup(ref exprs) =>
 297             hir::PatTup(exprs.iter().map(|expr| const_expr_to_pat(tcx, &**expr, span)).collect()),
 298
 299         hir::ExprCall(ref callee, ref args) => {
 300             let def = *tcx.def_map.borrow().get(&callee.id).unwrap();
 301             if let Vacant(entry) = tcx.def_map.borrow_mut().entry(expr.id) {
 302                entry.insert(def);
 303             }
 304             let path = match def.full_def() {
 305                 def::DefStruct(def_id) => def_to_path(tcx, def_id),
 306                 def::DefVariant(_, variant_did, _) => def_to_path(tcx, variant_did),
 307                 _ => unreachable!()
 308             };
 309             let pats = args.iter().map(|expr| const_expr_to_pat(tcx, &**expr, span)).collect();
 310             hir::PatEnum(path, Some(pats))
 311         }
 312
 313         hir::ExprStruct(ref path, ref fields, None) => {
 314             let field_pats = fields.iter().map(|field| codemap::Spanned {
 315                 span: codemap::DUMMY_SP,
 316                 node: hir::FieldPat {
 317                     ident: field.ident.node,
 318                     pat: const_expr_to_pat(tcx, &*field.expr, span),
 319                     is_shorthand: false,
 320                 },
 321             }).collect();
 322             hir::PatStruct(path.clone(), field_pats, false)
 323         }
 324
 325         hir::ExprVec(ref exprs) => {
 326             let pats = exprs.iter().map(|expr| const_expr_to_pat(tcx, &**expr, span)).collect();
 327             hir::PatVec(pats, None, vec![])
 328         }
 329
 330         hir::ExprPath(_, ref path) => {
 331             let opt_def = tcx.def_map.borrow().get(&expr.id).map(|d| d.full_def());
 332             match opt_def {
 333                 Some(def::DefStruct(..)) =>
 334                     hir::PatStruct(path.clone(), vec![], false),
 335                 Some(def::DefVariant(..)) =>
 336                     hir::PatEnum(path.clone(), None),
 337                 _ => {
 338                     match lookup_const(tcx, expr) {
 339                         Some(actual) => return const_expr_to_pat(tcx, actual, span),
 340                         _ => unreachable!()
 341                     }
 342                 }
 343             }
 344         }
 345
 346         _ => hir::PatLit(P(expr.clone()))
 347     };
 348     P(hir::Pat { id: expr.id, node: pat, span: span })
 349 }
 350
 351 pub fn eval_const_expr(tcx: &ty::ctxt, e: &Expr) -> ConstVal {
 352     match eval_const_expr_partial(tcx, e, ExprTypeChecked) {
 353         Ok(r) => r,
 354         Err(s) => tcx.sess.span_fatal(s.span, &s.description())
 355     }
 356 }
 357
 358
 359 #[derive(Clone)]
 360 pub struct ConstEvalErr {
 361     pub span: Span,
 362     pub kind: ErrKind,
 363 }
 364
 365 #[derive(Clone)]
 366 pub enum ErrKind {
 367     CannotCast,
 368     CannotCastTo(&'static str),
 369     InvalidOpForBools(hir::BinOp_),
 370     InvalidOpForFloats(hir::BinOp_),
 371     InvalidOpForIntUint(hir::BinOp_),
 372     InvalidOpForUintInt(hir::BinOp_),
 373     NegateOn(ConstVal),
 374     NotOn(ConstVal),
 375
 376     NegateWithOverflow(i64),
 377     AddiWithOverflow(i64, i64),
 378     SubiWithOverflow(i64, i64),
 379     MuliWithOverflow(i64, i64),
 380     AdduWithOverflow(u64, u64),
 381     SubuWithOverflow(u64, u64),
 382     MuluWithOverflow(u64, u64),
 383     DivideByZero,
 384     DivideWithOverflow,
 385     ModuloByZero,
 386     ModuloWithOverflow,
 387     ShiftLeftWithOverflow,
 388     ShiftRightWithOverflow,
 389     MissingStructField,
 390     NonConstPath,
 391     ExpectedConstTuple,
 392     ExpectedConstStruct,
 393     TupleIndexOutOfBounds,
 394
 395     MiscBinaryOp,
 396     MiscCatchAll,
 397 }
 398
 399 impl ConstEvalErr {
 400     pub fn description(&self) -> Cow<str> {
 401         use self::ErrKind::*;
 402
 403         match self.kind {
 404             CannotCast => "can't cast this type".into_cow(),
 405             CannotCastTo(s) => format!("can't cast this type to {}", s).into_cow(),
 406             InvalidOpForBools(_) =>  "can't do this op on bools".into_cow(),
 407             InvalidOpForFloats(_) => "can't do this op on floats".into_cow(),
 408             InvalidOpForIntUint(..) => "can't do this op on an isize and usize".into_cow(),
 409             InvalidOpForUintInt(..) => "can't do this op on a usize and isize".into_cow(),
 410             NegateOn(ref const_val) => format!("negate on {}", const_val.description()).into_cow(),
 411             NotOn(ref const_val) => format!("not on {}", const_val.description()).into_cow(),
 412
 413             NegateWithOverflow(..) => "attempted to negate with overflow".into_cow(),
 414             AddiWithOverflow(..) => "attempted to add with overflow".into_cow(),
 415             SubiWithOverflow(..) => "attempted to sub with overflow".into_cow(),
 416             MuliWithOverflow(..) => "attempted to mul with overflow".into_cow(),
 417             AdduWithOverflow(..) => "attempted to add with overflow".into_cow(),
 418             SubuWithOverflow(..) => "attempted to sub with overflow".into_cow(),
 419             MuluWithOverflow(..) => "attempted to mul with overflow".into_cow(),
 420             DivideByZero         => "attempted to divide by zero".into_cow(),
 421             DivideWithOverflow   => "attempted to divide with overflow".into_cow(),
 422             ModuloByZero         => "attempted remainder with a divisor of zero".into_cow(),
 423             ModuloWithOverflow   => "attempted remainder with overflow".into_cow(),
 424             ShiftLeftWithOverflow => "attempted left shift with overflow".into_cow(),
 425             ShiftRightWithOverflow => "attempted right shift with overflow".into_cow(),
 426             MissingStructField  => "nonexistent struct field".into_cow(),
 427             NonConstPath        => "non-constant path in constant expr".into_cow(),
 428             ExpectedConstTuple => "expected constant tuple".into_cow(),
 429             ExpectedConstStruct => "expected constant struct".into_cow(),
 430             TupleIndexOutOfBounds => "tuple index out of bounds".into_cow(),
 431
 432             MiscBinaryOp => "bad operands for binary".into_cow(),
 433             MiscCatchAll => "unsupported constant expr".into_cow(),
 434         }
 435     }
 436 }
 437
 438 pub type EvalResult = Result<ConstVal, ConstEvalErr>;
 439 pub type CastResult = Result<ConstVal, ErrKind>;
 440
 441 // FIXME: Long-term, this enum should go away: trying to evaluate
 442 // an expression which hasn't been type-checked is a recipe for
 443 // disaster.  That said, it's not clear how to fix ast_ty_to_ty
 444 // to avoid the ordering issue.
 445
 446 /// Hint to determine how to evaluate constant expressions which
 447 /// might not be type-checked.
 448 #[derive(Copy, Clone, Debug)]
 449 pub enum EvalHint<'tcx> {
 450     /// We have a type-checked expression.
 451     ExprTypeChecked,
 452     /// We have an expression which hasn't been type-checked, but we have
 453     /// an idea of what the type will be because of the context. For example,
 454     /// the length of an array is always `usize`. (This is referred to as
 455     /// a hint because it isn't guaranteed to be consistent with what
 456     /// type-checking would compute.)
 457     UncheckedExprHint(Ty<'tcx>),
 458     /// We have an expression which has not yet been type-checked, and
 459     /// and we have no clue what the type will be.
 460     UncheckedExprNoHint,
 461 }
 462
 463 #[derive(Copy, Clone, PartialEq, Debug)]
 464 pub enum IntTy { I8, I16, I32, I64 }
 465 #[derive(Copy, Clone, PartialEq, Debug)]
 466 pub enum UintTy { U8, U16, U32, U64 }
 467
 468 impl IntTy {
 469     pub fn from(tcx: &ty::ctxt, t: hir::IntTy) -> IntTy {
 470         let t = if let hir::TyIs = t {
 471             tcx.sess.target.int_type
 472         } else {
 473             t
 474         };
 475         match t {
 476             hir::TyIs => unreachable!(),
 477             hir::TyI8  => IntTy::I8,
 478             hir::TyI16 => IntTy::I16,
 479             hir::TyI32 => IntTy::I32,
 480             hir::TyI64 => IntTy::I64,
 481         }
 482     }
 483 }
 484
 485 impl UintTy {
 486     pub fn from(tcx: &ty::ctxt, t: hir::UintTy) -> UintTy {
 487         let t = if let hir::TyUs = t {
 488             tcx.sess.target.uint_type
 489         } else {
 490             t
 491         };
 492         match t {
 493             hir::TyUs => unreachable!(),
 494             hir::TyU8  => UintTy::U8,
 495             hir::TyU16 => UintTy::U16,
 496             hir::TyU32 => UintTy::U32,
 497             hir::TyU64 => UintTy::U64,
 498         }
 499     }
 500 }
 501
 502 macro_rules! signal {
 503     ($e:expr, $exn:expr) => {
 504         return Err(ConstEvalErr { span: $e.span, kind: $exn })
 505     }
 506 }
 507
 508 // The const_{int,uint}_checked_{neg,add,sub,mul,div,shl,shr} family
 509 // of functions catch and signal overflow errors during constant
 510 // evaluation.
 511 //
 512 // They all take the operator's arguments (`a` and `b` if binary), the
 513 // overall expression (`e`) and, if available, whole expression's
 514 // concrete type (`opt_ety`).
 515 //
 516 // If the whole expression's concrete type is None, then this is a
 517 // constant evaluation happening before type check (e.g. in the check
 518 // to confirm that a pattern range's left-side is not greater than its
 519 // right-side). We do not do arithmetic modulo the type's bitwidth in
 520 // such a case; we just do 64-bit arithmetic and assume that later
 521 // passes will do it again with the type information, and thus do the
 522 // overflow checks then.
 523
 524 pub fn const_int_checked_neg<'a>(
 525     a: i64, e: &'a Expr, opt_ety: Option<IntTy>) -> EvalResult {
 526
 527     let (min,max) = match opt_ety {
 528         // (-i8::MIN is itself not an i8, etc, but this is an easy way
 529         // to allow literals to pass the check. Of course that does
 530         // not work for i64::MIN.)
 531         Some(IntTy::I8) =>  (-(i8::MAX as i64), -(i8::MIN as i64)),
 532         Some(IntTy::I16) => (-(i16::MAX as i64), -(i16::MIN as i64)),
 533         Some(IntTy::I32) => (-(i32::MAX as i64), -(i32::MIN as i64)),
 534         None | Some(IntTy::I64) => (-i64::MAX, -(i64::MIN+1)),
 535     };
 536
 537     let oflo = a < min || a > max;
 538     if oflo {
 539         signal!(e, NegateWithOverflow(a));
 540     } else {
 541         Ok(Int(-a))
 542     }
 543 }
 544
 545 pub fn const_uint_checked_neg<'a>(
 546     a: u64, _e: &'a Expr, _opt_ety: Option<UintTy>) -> EvalResult {
 547     // This always succeeds, and by definition, returns `(!a)+1`.
 548     Ok(Uint((!a).wrapping_add(1)))
 549 }
 550
 551 fn const_uint_not(a: u64, opt_ety: Option<UintTy>) -> ConstVal {
 552     let mask = match opt_ety {
 553         Some(UintTy::U8) => u8::MAX as u64,
 554         Some(UintTy::U16) => u16::MAX as u64,
 555         Some(UintTy::U32) => u32::MAX as u64,
 556         None | Some(UintTy::U64) => u64::MAX,
 557     };
 558     Uint(!a & mask)
 559 }
 560
 561 macro_rules! overflow_checking_body {
 562     ($a:ident, $b:ident, $ety:ident, $overflowing_op:ident,
 563      lhs: $to_8_lhs:ident $to_16_lhs:ident $to_32_lhs:ident,
 564      rhs: $to_8_rhs:ident $to_16_rhs:ident $to_32_rhs:ident $to_64_rhs:ident,
 565      $EnumTy:ident $T8: ident $T16: ident $T32: ident $T64: ident,
 566      $result_type: ident) => { {
 567         let (a,b,opt_ety) = ($a,$b,$ety);
 568         match opt_ety {
 569             Some($EnumTy::$T8) => match (a.$to_8_lhs(), b.$to_8_rhs()) {
 570                 (Some(a), Some(b)) => {
 571                     let (a, oflo) = a.$overflowing_op(b);
 572                     (a as $result_type, oflo)
 573                 }
 574                 (None, _) | (_, None) => (0, true)
 575             },
 576             Some($EnumTy::$T16) => match (a.$to_16_lhs(), b.$to_16_rhs()) {
 577                 (Some(a), Some(b)) => {
 578                     let (a, oflo) = a.$overflowing_op(b);
 579                     (a as $result_type, oflo)
 580                 }
 581                 (None, _) | (_, None) => (0, true)
 582             },
 583             Some($EnumTy::$T32) => match (a.$to_32_lhs(), b.$to_32_rhs()) {
 584                 (Some(a), Some(b)) => {
 585                     let (a, oflo) = a.$overflowing_op(b);
 586                     (a as $result_type, oflo)
 587                 }
 588                 (None, _) | (_, None) => (0, true)
 589             },
 590             None | Some($EnumTy::$T64) => match b.$to_64_rhs() {
 591                 Some(b) => a.$overflowing_op(b),
 592                 None => (0, true),
 593             }
 594         }
 595     } }
 596 }
 597
 598 macro_rules! int_arith_body {
 599     ($a:ident, $b:ident, $ety:ident, $overflowing_op:ident) => {
 600         overflow_checking_body!(
 601             $a, $b, $ety, $overflowing_op,
 602             lhs: to_i8 to_i16 to_i32,
 603             rhs: to_i8 to_i16 to_i32 to_i64, IntTy I8 I16 I32 I64, i64)
 604     }
 605 }
 606
 607 macro_rules! uint_arith_body {
 608     ($a:ident, $b:ident, $ety:ident, $overflowing_op:ident) => {
 609         overflow_checking_body!(
 610             $a, $b, $ety, $overflowing_op,
 611             lhs: to_u8 to_u16 to_u32,
 612             rhs: to_u8 to_u16 to_u32 to_u64, UintTy U8 U16 U32 U64, u64)
 613     }
 614 }
 615
 616 macro_rules! int_shift_body {
 617     ($a:ident, $b:ident, $ety:ident, $overflowing_op:ident) => {
 618         overflow_checking_body!(
 619             $a, $b, $ety, $overflowing_op,
 620             lhs: to_i8 to_i16 to_i32,
 621             rhs: to_u32 to_u32 to_u32 to_u32, IntTy I8 I16 I32 I64, i64)
 622     }
 623 }
 624
 625 macro_rules! uint_shift_body {
 626     ($a:ident, $b:ident, $ety:ident, $overflowing_op:ident) => {
 627         overflow_checking_body!(
 628             $a, $b, $ety, $overflowing_op,
 629             lhs: to_u8 to_u16 to_u32,
 630             rhs: to_u32 to_u32 to_u32 to_u32, UintTy U8 U16 U32 U64, u64)
 631     }
 632 }
 633
 634 macro_rules! pub_fn_checked_op {
 635     {$fn_name:ident ($a:ident : $a_ty:ty, $b:ident : $b_ty:ty,.. $WhichTy:ident) {
 636         $ret_oflo_body:ident $overflowing_op:ident
 637             $const_ty:ident $signal_exn:expr
 638     }} => {
 639         pub fn $fn_name<'a>($a: $a_ty,
 640                             $b: $b_ty,
 641                             e: &'a Expr,
 642                             opt_ety: Option<$WhichTy>) -> EvalResult {
 643             let (ret, oflo) = $ret_oflo_body!($a, $b, opt_ety, $overflowing_op);
 644             if !oflo { Ok($const_ty(ret)) } else { signal!(e, $signal_exn) }
 645         }
 646     }
 647 }
 648
 649 pub_fn_checked_op!{ const_int_checked_add(a: i64, b: i64,.. IntTy) {
 650            int_arith_body overflowing_add Int AddiWithOverflow(a, b)
 651 }}
 652
 653 pub_fn_checked_op!{ const_int_checked_sub(a: i64, b: i64,.. IntTy) {
 654            int_arith_body overflowing_sub Int SubiWithOverflow(a, b)
 655 }}
 656
 657 pub_fn_checked_op!{ const_int_checked_mul(a: i64, b: i64,.. IntTy) {
 658            int_arith_body overflowing_mul Int MuliWithOverflow(a, b)
 659 }}
 660
 661 pub fn const_int_checked_div<'a>(
 662     a: i64, b: i64, e: &'a Expr, opt_ety: Option<IntTy>) -> EvalResult {
 663     if b == 0 { signal!(e, DivideByZero); }
 664     let (ret, oflo) = int_arith_body!(a, b, opt_ety, overflowing_div);
 665     if !oflo { Ok(Int(ret)) } else { signal!(e, DivideWithOverflow) }
 666 }
 667
 668 pub fn const_int_checked_rem<'a>(
 669     a: i64, b: i64, e: &'a Expr, opt_ety: Option<IntTy>) -> EvalResult {
 670     if b == 0 { signal!(e, ModuloByZero); }
 671     let (ret, oflo) = int_arith_body!(a, b, opt_ety, overflowing_rem);
 672     if !oflo { Ok(Int(ret)) } else { signal!(e, ModuloWithOverflow) }
 673 }
 674
 675 pub_fn_checked_op!{ const_int_checked_shl(a: i64, b: i64,.. IntTy) {
 676            int_shift_body overflowing_shl Int ShiftLeftWithOverflow
 677 }}
 678
 679 pub_fn_checked_op!{ const_int_checked_shl_via_uint(a: i64, b: u64,.. IntTy) {
 680            int_shift_body overflowing_shl Int ShiftLeftWithOverflow
 681 }}
 682
 683 pub_fn_checked_op!{ const_int_checked_shr(a: i64, b: i64,.. IntTy) {
 684            int_shift_body overflowing_shr Int ShiftRightWithOverflow
 685 }}
 686
 687 pub_fn_checked_op!{ const_int_checked_shr_via_uint(a: i64, b: u64,.. IntTy) {
 688            int_shift_body overflowing_shr Int ShiftRightWithOverflow
 689 }}
 690
 691 pub_fn_checked_op!{ const_uint_checked_add(a: u64, b: u64,.. UintTy) {
 692            uint_arith_body overflowing_add Uint AdduWithOverflow(a, b)
 693 }}
 694
 695 pub_fn_checked_op!{ const_uint_checked_sub(a: u64, b: u64,.. UintTy) {
 696            uint_arith_body overflowing_sub Uint SubuWithOverflow(a, b)
 697 }}
 698
 699 pub_fn_checked_op!{ const_uint_checked_mul(a: u64, b: u64,.. UintTy) {
 700            uint_arith_body overflowing_mul Uint MuluWithOverflow(a, b)
 701 }}
 702
 703 pub fn const_uint_checked_div<'a>(
 704     a: u64, b: u64, e: &'a Expr, opt_ety: Option<UintTy>) -> EvalResult {
 705     if b == 0 { signal!(e, DivideByZero); }
 706     let (ret, oflo) = uint_arith_body!(a, b, opt_ety, overflowing_div);
 707     if !oflo { Ok(Uint(ret)) } else { signal!(e, DivideWithOverflow) }
 708 }
 709
 710 pub fn const_uint_checked_rem<'a>(
 711     a: u64, b: u64, e: &'a Expr, opt_ety: Option<UintTy>) -> EvalResult {
 712     if b == 0 { signal!(e, ModuloByZero); }
 713     let (ret, oflo) = uint_arith_body!(a, b, opt_ety, overflowing_rem);
 714     if !oflo { Ok(Uint(ret)) } else { signal!(e, ModuloWithOverflow) }
 715 }
 716
 717 pub_fn_checked_op!{ const_uint_checked_shl(a: u64, b: u64,.. UintTy) {
 718            uint_shift_body overflowing_shl Uint ShiftLeftWithOverflow
 719 }}
 720
 721 pub_fn_checked_op!{ const_uint_checked_shl_via_int(a: u64, b: i64,.. UintTy) {
 722            uint_shift_body overflowing_shl Uint ShiftLeftWithOverflow
 723 }}
 724
 725 pub_fn_checked_op!{ const_uint_checked_shr(a: u64, b: u64,.. UintTy) {
 726            uint_shift_body overflowing_shr Uint ShiftRightWithOverflow
 727 }}
 728
 729 pub_fn_checked_op!{ const_uint_checked_shr_via_int(a: u64, b: i64,.. UintTy) {
 730            uint_shift_body overflowing_shr Uint ShiftRightWithOverflow
 731 }}
 732
 733 /// Evaluate a constant expression in a context where the expression isn't
 734 /// guaranteed to be evaluatable. `ty_hint` is usually ExprTypeChecked,
 735 /// but a few places need to evaluate constants during type-checking, like
 736 /// computing the length of an array. (See also the FIXME above EvalHint.)
 737 pub fn eval_const_expr_partial<'tcx>(tcx: &ty::ctxt<'tcx>,
 738                                      e: &Expr,
 739                                      ty_hint: EvalHint<'tcx>) -> EvalResult {
 740     fn fromb(b: bool) -> ConstVal { Int(b as i64) }
 741
 742     // Try to compute the type of the expression based on the EvalHint.
 743     // (See also the definition of EvalHint, and the FIXME above EvalHint.)
 744     let ety = match ty_hint {
 745         ExprTypeChecked => {
 746             // After type-checking, expr_ty is guaranteed to succeed.
 747             Some(tcx.expr_ty(e))
 748         }
 749         UncheckedExprHint(ty) => {
 750             // Use the type hint; it's not guaranteed to be right, but it's
 751             // usually good enough.
 752             Some(ty)
 753         }
 754         UncheckedExprNoHint => {
 755             // This expression might not be type-checked, and we have no hint.
 756             // Try to query the context for a type anyway; we might get lucky
 757             // (for example, if the expression was imported from another crate).
 758             tcx.expr_ty_opt(e)
 759         }
 760     };
 761
 762     // If type of expression itself is int or uint, normalize in these
 763     // bindings so that isize/usize is mapped to a type with an
 764     // inherently known bitwidth.
 765     let expr_int_type = ety.and_then(|ty| {
 766         if let ty::TyInt(t) = ty.sty {
 767             Some(IntTy::from(tcx, t)) } else { None }
 768     });
 769     let expr_uint_type = ety.and_then(|ty| {
 770         if let ty::TyUint(t) = ty.sty {
 771             Some(UintTy::from(tcx, t)) } else { None }
 772     });
 773
 774     let result = match e.node {
 775       hir::ExprUnary(hir::UnNeg, ref inner) => {
 776         match try!(eval_const_expr_partial(tcx, &**inner, ty_hint)) {
 777           Float(f) => Float(-f),
 778           Int(n) =>  try!(const_int_checked_neg(n, e, expr_int_type)),
 779           Uint(i) => {
 780               try!(const_uint_checked_neg(i, e, expr_uint_type))
 781           }
 782           const_val => signal!(e, NegateOn(const_val)),
 783         }
 784       }
 785       hir::ExprUnary(hir::UnNot, ref inner) => {
 786         match try!(eval_const_expr_partial(tcx, &**inner, ty_hint)) {
 787           Int(i) => Int(!i),
 788           Uint(i) => const_uint_not(i, expr_uint_type),
 789           Bool(b) => Bool(!b),
 790           const_val => signal!(e, NotOn(const_val)),
 791         }
 792       }
 793       hir::ExprBinary(op, ref a, ref b) => {
 794         let b_ty = match op.node {
 795             hir::BiShl | hir::BiShr => {
 796                 if let ExprTypeChecked = ty_hint {
 797                     ExprTypeChecked
 798                 } else {
 799                     UncheckedExprHint(tcx.types.usize)
 800                 }
 801             }
 802             _ => ty_hint
 803         };
 804         match (try!(eval_const_expr_partial(tcx, &**a, ty_hint)),
 805                try!(eval_const_expr_partial(tcx, &**b, b_ty))) {
 806           (Float(a), Float(b)) => {
 807             match op.node {
 808               hir::BiAdd => Float(a + b),
 809               hir::BiSub => Float(a - b),
 810               hir::BiMul => Float(a * b),
 811               hir::BiDiv => Float(a / b),
 812               hir::BiRem => Float(a % b),
 813               hir::BiEq => fromb(a == b),
 814               hir::BiLt => fromb(a < b),
 815               hir::BiLe => fromb(a <= b),
 816               hir::BiNe => fromb(a != b),
 817               hir::BiGe => fromb(a >= b),
 818               hir::BiGt => fromb(a > b),
 819               _ => signal!(e, InvalidOpForFloats(op.node))
 820             }
 821           }
 822           (Int(a), Int(b)) => {
 823             match op.node {
 824               hir::BiAdd => try!(const_int_checked_add(a,b,e,expr_int_type)),
 825               hir::BiSub => try!(const_int_checked_sub(a,b,e,expr_int_type)),
 826               hir::BiMul => try!(const_int_checked_mul(a,b,e,expr_int_type)),
 827               hir::BiDiv => try!(const_int_checked_div(a,b,e,expr_int_type)),
 828               hir::BiRem => try!(const_int_checked_rem(a,b,e,expr_int_type)),
 829               hir::BiAnd | hir::BiBitAnd => Int(a & b),
 830               hir::BiOr | hir::BiBitOr => Int(a | b),
 831               hir::BiBitXor => Int(a ^ b),
 832               hir::BiShl => try!(const_int_checked_shl(a,b,e,expr_int_type)),
 833               hir::BiShr => try!(const_int_checked_shr(a,b,e,expr_int_type)),
 834               hir::BiEq => fromb(a == b),
 835               hir::BiLt => fromb(a < b),
 836               hir::BiLe => fromb(a <= b),
 837               hir::BiNe => fromb(a != b),
 838               hir::BiGe => fromb(a >= b),
 839               hir::BiGt => fromb(a > b)
 840             }
 841           }
 842           (Uint(a), Uint(b)) => {
 843             match op.node {
 844               hir::BiAdd => try!(const_uint_checked_add(a,b,e,expr_uint_type)),
 845               hir::BiSub => try!(const_uint_checked_sub(a,b,e,expr_uint_type)),
 846               hir::BiMul => try!(const_uint_checked_mul(a,b,e,expr_uint_type)),
 847               hir::BiDiv => try!(const_uint_checked_div(a,b,e,expr_uint_type)),
 848               hir::BiRem => try!(const_uint_checked_rem(a,b,e,expr_uint_type)),
 849               hir::BiAnd | hir::BiBitAnd => Uint(a & b),
 850               hir::BiOr | hir::BiBitOr => Uint(a | b),
 851               hir::BiBitXor => Uint(a ^ b),
 852               hir::BiShl => try!(const_uint_checked_shl(a,b,e,expr_uint_type)),
 853               hir::BiShr => try!(const_uint_checked_shr(a,b,e,expr_uint_type)),
 854               hir::BiEq => fromb(a == b),
 855               hir::BiLt => fromb(a < b),
 856               hir::BiLe => fromb(a <= b),
 857               hir::BiNe => fromb(a != b),
 858               hir::BiGe => fromb(a >= b),
 859               hir::BiGt => fromb(a > b),
 860             }
 861           }
 862           // shifts can have any integral type as their rhs
 863           (Int(a), Uint(b)) => {
 864             match op.node {
 865               hir::BiShl => try!(const_int_checked_shl_via_uint(a,b,e,expr_int_type)),
 866               hir::BiShr => try!(const_int_checked_shr_via_uint(a,b,e,expr_int_type)),
 867               _ => signal!(e, InvalidOpForIntUint(op.node)),
 868             }
 869           }
 870           (Uint(a), Int(b)) => {
 871             match op.node {
 872               hir::BiShl => try!(const_uint_checked_shl_via_int(a,b,e,expr_uint_type)),
 873               hir::BiShr => try!(const_uint_checked_shr_via_int(a,b,e,expr_uint_type)),
 874               _ => signal!(e, InvalidOpForUintInt(op.node)),
 875             }
 876           }
 877           (Bool(a), Bool(b)) => {
 878             Bool(match op.node {
 879               hir::BiAnd => a && b,
 880               hir::BiOr => a || b,
 881               hir::BiBitXor => a ^ b,
 882               hir::BiBitAnd => a & b,
 883               hir::BiBitOr => a | b,
 884               hir::BiEq => a == b,
 885               hir::BiNe => a != b,
 886               _ => signal!(e, InvalidOpForBools(op.node)),
 887              })
 888           }
 889
 890           _ => signal!(e, MiscBinaryOp),
 891         }
 892       }
 893       hir::ExprCast(ref base, ref target_ty) => {
 894         let ety = ety.or_else(|| ast_ty_to_prim_ty(tcx, &**target_ty))
 895                 .unwrap_or_else(|| {
 896                     tcx.sess.span_fatal(target_ty.span,
 897                                         "target type not found for const cast")
 898                 });
 899
 900         let base_hint = if let ExprTypeChecked = ty_hint {
 901             ExprTypeChecked
 902         } else {
 903             // FIXME (#23833): the type-hint can cause problems,
 904             // e.g. `(i8::MAX + 1_i8) as u32` feeds in `u32` as result
 905             // type to the sum, and thus no overflow is signaled.
 906             match tcx.expr_ty_opt(&base) {
 907                 Some(t) => UncheckedExprHint(t),
 908                 None => ty_hint
 909             }
 910         };
 911
 912         let val = try!(eval_const_expr_partial(tcx, &**base, base_hint));
 913         match cast_const(tcx, val, ety) {
 914             Ok(val) => val,
 915             Err(kind) => return Err(ConstEvalErr { span: e.span, kind: kind }),
 916         }
 917       }
 918       hir::ExprPath(..) => {
 919           let opt_def = tcx.def_map.borrow().get(&e.id).map(|d| d.full_def());
 920           let (const_expr, const_ty) = match opt_def {
 921               Some(def::DefConst(def_id)) => {
 922                   if def_id.is_local() {
 923                       match tcx.map.find(def_id.node) {
 924                           Some(ast_map::NodeItem(it)) => match it.node {
 925                               hir::ItemConst(ref ty, ref expr) => {
 926                                   (Some(&**expr), Some(&**ty))
 927                               }
 928                               _ => (None, None)
 929                           },
 930                           _ => (None, None)
 931                       }
 932                   } else {
 933                       (lookup_const_by_id(tcx, def_id, Some(e.id)), None)
 934                   }
 935               }
 936               Some(def::DefAssociatedConst(def_id)) => {
 937                   if def_id.is_local() {
 938                       match tcx.impl_or_trait_item(def_id).container() {
 939                           ty::TraitContainer(trait_id) => match tcx.map.find(def_id.node) {
 940                               Some(ast_map::NodeTraitItem(ti)) => match ti.node {
 941                                   hir::ConstTraitItem(ref ty, _) => {
 942                                       if let ExprTypeChecked = ty_hint {
 943                                           let substs = tcx.node_id_item_substs(e.id).substs;
 944                                           (resolve_trait_associated_const(tcx,
 945                                                                           ti,
 946                                                                           trait_id,
 947                                                                           substs),
 948                                            Some(&**ty))
 949                                        } else {
 950                                            (None, None)
 951                                        }
 952                                   }
 953                                   _ => (None, None)
 954                               },
 955                               _ => (None, None)
 956                           },
 957                           ty::ImplContainer(_) => match tcx.map.find(def_id.node) {
 958                               Some(ast_map::NodeImplItem(ii)) => match ii.node {
 959                                   hir::ConstImplItem(ref ty, ref expr) => {
 960                                       (Some(&**expr), Some(&**ty))
 961                                   }
 962                                   _ => (None, None)
 963                               },
 964                               _ => (None, None)
 965                           },
 966                       }
 967                   } else {
 968                       (lookup_const_by_id(tcx, def_id, Some(e.id)), None)
 969                   }
 970               }
 971               Some(def::DefVariant(enum_def, variant_def, _)) => {
 972                   (lookup_variant_by_id(tcx, enum_def, variant_def), None)
 973               }
 974               Some(def::DefStruct(_)) => {
 975                   return Ok(ConstVal::Struct(e.id))
 976               }
 977               _ => (None, None)
 978           };
 979           let const_expr = match const_expr {
 980               Some(actual_e) => actual_e,
 981               None => signal!(e, NonConstPath)
 982           };
 983           let item_hint = if let UncheckedExprNoHint = ty_hint {
 984               match const_ty {
 985                   Some(ty) => match ast_ty_to_prim_ty(tcx, ty) {
 986                       Some(ty) => UncheckedExprHint(ty),
 987                       None => UncheckedExprNoHint
 988                   },
 989                   None => UncheckedExprNoHint
 990               }
 991           } else {
 992               ty_hint
 993           };
 994           try!(eval_const_expr_partial(tcx, const_expr, item_hint))
 995       }
 996       hir::ExprLit(ref lit) => {
 997           lit_to_const(&**lit, ety)
 998       }
 999       hir::ExprParen(ref e) => try!(eval_const_expr_partial(tcx, &**e, ty_hint)),
1000       hir::ExprBlock(ref block) => {
1001         match block.expr {
1002             Some(ref expr) => try!(eval_const_expr_partial(tcx, &**expr, ty_hint)),
1003             None => Int(0)
1004         }
1005       }
1006       hir::ExprTup(_) => Tuple(e.id),
1007       hir::ExprStruct(..) => Struct(e.id),
1008       hir::ExprTupField(ref base, index) => {
1009         let base_hint = if let ExprTypeChecked = ty_hint {
1010             ExprTypeChecked
1011         } else {
1012             UncheckedExprNoHint
1013         };
1014         if let Ok(c) = eval_const_expr_partial(tcx, base, base_hint) {
1015             if let Tuple(tup_id) = c {
1016                 if let hir::ExprTup(ref fields) = tcx.map.expect_expr(tup_id).node {
1017                     if index.node < fields.len() {
1018                         return eval_const_expr_partial(tcx, &fields[index.node], base_hint)
1019                     } else {
1020                         signal!(e, TupleIndexOutOfBounds);
1021                     }
1022                 } else {
1023                     unreachable!()
1024                 }
1025             } else {
1026                 signal!(base, ExpectedConstTuple);
1027             }
1028         } else {
1029             signal!(base, NonConstPath)
1030         }
1031       }
1032       hir::ExprField(ref base, field_name) => {
1033         // Get the base expression if it is a struct and it is constant
1034         let base_hint = if let ExprTypeChecked = ty_hint {
1035             ExprTypeChecked
1036         } else {
1037             UncheckedExprNoHint
1038         };
1039         if let Ok(c) = eval_const_expr_partial(tcx, base, base_hint) {
1040             if let Struct(struct_id) = c {
1041                 if let hir::ExprStruct(_, ref fields, _) = tcx.map.expect_expr(struct_id).node {
1042                     // Check that the given field exists and evaluate it
1043                     // if the idents are compared run-pass/issue-19244 fails
1044                     if let Some(f) = fields.iter().find(|f| f.ident.node.name
1045                                                          == field_name.node.name) {
1046                         return eval_const_expr_partial(tcx, &*f.expr, base_hint)
1047                     } else {
1048                         signal!(e, MissingStructField);
1049                     }
1050                 } else {
1051                     unreachable!()
1052                 }
1053             } else {
1054                 signal!(base, ExpectedConstStruct);
1055             }
1056         } else {
1057             signal!(base, NonConstPath);
1058         }
1059       }
1060       _ => signal!(e, MiscCatchAll)
1061     };
1062
1063     Ok(result)
1064 }
1065
1066 fn resolve_trait_associated_const<'a, 'tcx: 'a>(tcx: &'a ty::ctxt<'tcx>,
1067                                                 ti: &'tcx hir::TraitItem,
1068                                                 trait_id: DefId,
1069                                                 rcvr_substs: subst::Substs<'tcx>)
1070                                                 -> Option<&'tcx Expr>
1071 {
1072     let subst::SeparateVecsPerParamSpace {
1073         types: rcvr_type,
1074         selfs: rcvr_self,
1075         fns: _,
1076     } = rcvr_substs.types.split();
1077     let trait_substs =
1078         subst::Substs::erased(subst::VecPerParamSpace::new(rcvr_type,
1079                                                            rcvr_self,
1080                                                            Vec::new()));
1081     let trait_substs = tcx.mk_substs(trait_substs);
1082     debug!("resolve_trait_associated_const: trait_substs={:?}",
1083            trait_substs);
1084     let trait_ref = ty::Binder(ty::TraitRef { def_id: trait_id,
1085                                               substs: trait_substs });
1086
1087     tcx.populate_implementations_for_trait_if_necessary(trait_ref.def_id());
1088     let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
1089
1090     let mut selcx = traits::SelectionContext::new(&infcx);
1091     let obligation = traits::Obligation::new(traits::ObligationCause::dummy(),
1092                                              trait_ref.to_poly_trait_predicate());
1093     let selection = match selcx.select(&obligation) {
1094         Ok(Some(vtable)) => vtable,
1095         // Still ambiguous, so give up and let the caller decide whether this
1096         // expression is really needed yet. Some associated constant values
1097         // can't be evaluated until monomorphization is done in trans.
1098         Ok(None) => {
1099             return None
1100         }
1101         Err(e) => {
1102             tcx.sess.span_bug(ti.span,
1103                               &format!("Encountered error `{:?}` when trying \
1104                                         to select an implementation for \
1105                                         constant trait item reference.",
1106                                        e))
1107         }
1108     };
1109
1110     match selection {
1111         traits::VtableImpl(ref impl_data) => {
1112             match tcx.associated_consts(impl_data.impl_def_id)
1113                      .iter().find(|ic| ic.name == ti.ident.name) {
1114                 Some(ic) => lookup_const_by_id(tcx, ic.def_id, None),
1115                 None => match ti.node {
1116                     hir::ConstTraitItem(_, Some(ref expr)) => Some(&*expr),
1117                     _ => None,
1118                 },
1119             }
1120         }
1121         _ => {
1122             tcx.sess.span_bug(
1123                 ti.span,
1124                 &format!("resolve_trait_associated_const: unexpected vtable type"))
1125         }
1126     }
1127 }
1128
1129 fn cast_const<'tcx>(tcx: &ty::ctxt<'tcx>, val: ConstVal, ty: Ty) -> CastResult {
1130     macro_rules! convert_val {
1131         ($intermediate_ty:ty, $const_type:ident, $target_ty:ty) => {
1132             match val {
1133                 Bool(b) => Ok($const_type(b as u64 as $intermediate_ty as $target_ty)),
1134                 Uint(u) => Ok($const_type(u as $intermediate_ty as $target_ty)),
1135                 Int(i) => Ok($const_type(i as $intermediate_ty as $target_ty)),
1136                 Float(f) => Ok($const_type(f as $intermediate_ty as $target_ty)),
1137                 _ => Err(ErrKind::CannotCastTo(stringify!($const_type))),
1138             }
1139         }
1140     }
1141
1142     // Issue #23890: If isize/usize, then dispatch to appropriate target representation type
1143     match (&ty.sty, tcx.sess.target.int_type, tcx.sess.target.uint_type) {
1144         (&ty::TyInt(hir::TyIs), hir::TyI32, _) => return convert_val!(i32, Int, i64),
1145         (&ty::TyInt(hir::TyIs), hir::TyI64, _) => return convert_val!(i64, Int, i64),
1146         (&ty::TyInt(hir::TyIs), _, _) => panic!("unexpected target.int_type"),
1147
1148         (&ty::TyUint(hir::TyUs), _, hir::TyU32) => return convert_val!(u32, Uint, u64),
1149         (&ty::TyUint(hir::TyUs), _, hir::TyU64) => return convert_val!(u64, Uint, u64),
1150         (&ty::TyUint(hir::TyUs), _, _) => panic!("unexpected target.uint_type"),
1151
1152         _ => {}
1153     }
1154
1155     match ty.sty {
1156         ty::TyInt(hir::TyIs) => unreachable!(),
1157         ty::TyUint(hir::TyUs) => unreachable!(),
1158
1159         ty::TyInt(hir::TyI8) => convert_val!(i8, Int, i64),
1160         ty::TyInt(hir::TyI16) => convert_val!(i16, Int, i64),
1161         ty::TyInt(hir::TyI32) => convert_val!(i32, Int, i64),
1162         ty::TyInt(hir::TyI64) => convert_val!(i64, Int, i64),
1163
1164         ty::TyUint(hir::TyU8) => convert_val!(u8, Uint, u64),
1165         ty::TyUint(hir::TyU16) => convert_val!(u16, Uint, u64),
1166         ty::TyUint(hir::TyU32) => convert_val!(u32, Uint, u64),
1167         ty::TyUint(hir::TyU64) => convert_val!(u64, Uint, u64),
1168
1169         ty::TyFloat(hir::TyF32) => convert_val!(f32, Float, f64),
1170         ty::TyFloat(hir::TyF64) => convert_val!(f64, Float, f64),
1171         _ => Err(ErrKind::CannotCast),
1172     }
1173 }
1174
1175 fn lit_to_const(lit: &hir::Lit, ty_hint: Option<Ty>) -> ConstVal {
1176     match lit.node {
1177         hir::LitStr(ref s, _) => Str((*s).clone()),
1178         hir::LitByteStr(ref data) => {
1179             ByteStr(data.clone())
1180         }
1181         hir::LitByte(n) => Uint(n as u64),
1182         hir::LitChar(n) => Uint(n as u64),
1183         hir::LitInt(n, hir::SignedIntLit(_, hir::Plus)) => Int(n as i64),
1184         hir::LitInt(n, hir::UnsuffixedIntLit(hir::Plus)) => {
1185             match ty_hint.map(|ty| &ty.sty) {
1186                 Some(&ty::TyUint(_)) => Uint(n),
1187                 _ => Int(n as i64)
1188             }
1189         }
1190         hir::LitInt(n, hir::SignedIntLit(_, hir::Minus)) |
1191         hir::LitInt(n, hir::UnsuffixedIntLit(hir::Minus)) => Int(-(n as i64)),
1192         hir::LitInt(n, hir::UnsignedIntLit(_)) => Uint(n),
1193         hir::LitFloat(ref n, _) |
1194         hir::LitFloatUnsuffixed(ref n) => {
1195             Float(n.parse::<f64>().unwrap() as f64)
1196         }
1197         hir::LitBool(b) => Bool(b)
1198     }
1199 }
1200
1201 pub fn compare_const_vals(a: &ConstVal, b: &ConstVal) -> Option<Ordering> {
1202     Some(match (a, b) {
1203         (&Int(a), &Int(b)) => a.cmp(&b),
1204         (&Uint(a), &Uint(b)) => a.cmp(&b),
1205         (&Float(a), &Float(b)) => {
1206             // This is pretty bad but it is the existing behavior.
1207             if a == b {
1208                 Ordering::Equal
1209             } else if a < b {
1210                 Ordering::Less
1211             } else {
1212                 Ordering::Greater
1213             }
1214         }
1215         (&Str(ref a), &Str(ref b)) => a.cmp(b),
1216         (&Bool(a), &Bool(b)) => a.cmp(&b),
1217         (&ByteStr(ref a), &ByteStr(ref b)) => a.cmp(b),
1218         _ => return None
1219     })
1220 }
1221
1222 pub fn compare_lit_exprs<'tcx>(tcx: &ty::ctxt<'tcx>,
1223                                a: &Expr,
1224                                b: &Expr) -> Option<Ordering> {
1225     let a = match eval_const_expr_partial(tcx, a, ExprTypeChecked) {
1226         Ok(a) => a,
1227         Err(e) => {
1228             tcx.sess.span_err(a.span, &e.description());
1229             return None;
1230         }
1231     };
1232     let b = match eval_const_expr_partial(tcx, b, ExprTypeChecked) {
1233         Ok(b) => b,
1234         Err(e) => {
1235             tcx.sess.span_err(b.span, &e.description());
1236             return None;
1237         }
1238     };
1239     compare_const_vals(&a, &b)
1240 }