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