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