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