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