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