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