src/librustc/middle/const_eval.rs

   1 // Copyright 2012-2014 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 #![allow(unsigned_negate)]
  13
  14 use metadata::csearch;
  15 use middle::astencode;
  16
  17 use middle::def;
  18 use middle::ty;
  19 use middle::typeck::astconv;
  20 use util::nodemap::{DefIdMap};
  21
  22 use syntax::ast::*;
  23 use syntax::parse::token::InternedString;
  24 use syntax::visit::Visitor;
  25 use syntax::visit;
  26 use syntax::{ast, ast_map, ast_util};
  27
  28 use std::rc::Rc;
  29 use std::gc::Gc;
  30
  31 //
  32 // This pass classifies expressions by their constant-ness.
  33 //
  34 // Constant-ness comes in 3 flavours:
  35 //
  36 //   - Integer-constants: can be evaluated by the frontend all the way down
  37 //     to their actual value. They are used in a few places (enum
  38 //     discriminants, switch arms) and are a subset of
  39 //     general-constants. They cover all the integer and integer-ish
  40 //     literals (nil, bool, int, uint, char, iNN, uNN) and all integer
  41 //     operators and copies applied to them.
  42 //
  43 //   - General-constants: can be evaluated by LLVM but not necessarily by
  44 //     the frontend; usually due to reliance on target-specific stuff such
  45 //     as "where in memory the value goes" or "what floating point mode the
  46 //     target uses". This _includes_ integer-constants, plus the following
  47 //     constructors:
  48 //
  49 //        fixed-size vectors and strings: [] and ""/_
  50 //        vector and string slices: &[] and &""
  51 //        tuples: (,)
  52 //        enums: foo(...)
  53 //        floating point literals and operators
  54 //        & and * pointers
  55 //        copies of general constants
  56 //
  57 //        (in theory, probably not at first: if/match on integer-const
  58 //         conditions / descriminants)
  59 //
  60 //   - Non-constants: everything else.
  61 //
  62
  63 pub enum constness {
  64     integral_const,
  65     general_const,
  66     non_const
  67 }
  68
  69 type constness_cache = DefIdMap<constness>;
  70
  71 pub fn join(a: constness, b: constness) -> constness {
  72     match (a, b) {
  73       (integral_const, integral_const) => integral_const,
  74       (integral_const, general_const)
  75       | (general_const, integral_const)
  76       | (general_const, general_const) => general_const,
  77       _ => non_const
  78     }
  79 }
  80
  81 pub fn join_all<It: Iterator<constness>>(mut cs: It) -> constness {
  82     cs.fold(integral_const, |a, b| join(a, b))
  83 }
  84
  85 pub fn lookup_const(tcx: &ty::ctxt, e: &Expr) -> Option<Gc<Expr>> {
  86     let opt_def = tcx.def_map.borrow().find_copy(&e.id);
  87     match opt_def {
  88         Some(def::DefStatic(def_id, false)) => {
  89             lookup_const_by_id(tcx, def_id)
  90         }
  91         Some(def::DefVariant(enum_def, variant_def, _)) => {
  92             lookup_variant_by_id(tcx, enum_def, variant_def)
  93         }
  94         _ => None
  95     }
  96 }
  97
  98 pub fn lookup_variant_by_id(tcx: &ty::ctxt,
  99                             enum_def: ast::DefId,
 100                             variant_def: ast::DefId)
 101                        -> Option<Gc<Expr>> {
 102     fn variant_expr(variants: &[ast::P<ast::Variant>],
 103                     id: ast::NodeId) -> Option<Gc<Expr>> {
 104         for variant in variants.iter() {
 105             if variant.node.id == id {
 106                 return variant.node.disr_expr;
 107             }
 108         }
 109         None
 110     }
 111
 112     if ast_util::is_local(enum_def) {
 113         {
 114             match tcx.map.find(enum_def.node) {
 115                 None => None,
 116                 Some(ast_map::NodeItem(it)) => match it.node {
 117                     ItemEnum(ast::EnumDef { variants: ref variants }, _) => {
 118                         variant_expr(variants.as_slice(), variant_def.node)
 119                     }
 120                     _ => None
 121                 },
 122                 Some(_) => None
 123             }
 124         }
 125     } else {
 126         match tcx.extern_const_variants.borrow().find(&variant_def) {
 127             Some(&e) => return e,
 128             None => {}
 129         }
 130         let e = match csearch::maybe_get_item_ast(tcx, enum_def,
 131             |a, b, c, d| astencode::decode_inlined_item(a, b, c, d)) {
 132             csearch::found(ast::IIItem(item)) => match item.node {
 133                 ItemEnum(ast::EnumDef { variants: ref variants }, _) => {
 134                     variant_expr(variants.as_slice(), variant_def.node)
 135                 }
 136                 _ => None
 137             },
 138             _ => None
 139         };
 140         tcx.extern_const_variants.borrow_mut().insert(variant_def, e);
 141         return e;
 142     }
 143 }
 144
 145 pub fn lookup_const_by_id(tcx: &ty::ctxt, def_id: ast::DefId)
 146                           -> Option<Gc<Expr>> {
 147     if ast_util::is_local(def_id) {
 148         {
 149             match tcx.map.find(def_id.node) {
 150                 None => None,
 151                 Some(ast_map::NodeItem(it)) => match it.node {
 152                     ItemStatic(_, ast::MutImmutable, const_expr) => {
 153                         Some(const_expr)
 154                     }
 155                     _ => None
 156                 },
 157                 Some(_) => None
 158             }
 159         }
 160     } else {
 161         match tcx.extern_const_statics.borrow().find(&def_id) {
 162             Some(&e) => return e,
 163             None => {}
 164         }
 165         let e = match csearch::maybe_get_item_ast(tcx, def_id,
 166             |a, b, c, d| astencode::decode_inlined_item(a, b, c, d)) {
 167             csearch::found(ast::IIItem(item)) => match item.node {
 168                 ItemStatic(_, ast::MutImmutable, const_expr) => Some(const_expr),
 169                 _ => None
 170             },
 171             _ => None
 172         };
 173         tcx.extern_const_statics.borrow_mut().insert(def_id, e);
 174         return e;
 175     }
 176 }
 177
 178 struct ConstEvalVisitor<'a> {
 179     tcx: &'a ty::ctxt,
 180     ccache: constness_cache,
 181 }
 182
 183 impl<'a> ConstEvalVisitor<'a> {
 184     fn classify(&mut self, e: &Expr) -> constness {
 185         let did = ast_util::local_def(e.id);
 186         match self.ccache.find(&did) {
 187             Some(&x) => return x,
 188             None => {}
 189         }
 190         let cn = match e.node {
 191             ast::ExprLit(ref lit) => {
 192                 match lit.node {
 193                     ast::LitStr(..) | ast::LitFloat(..) => general_const,
 194                     _ => integral_const
 195                 }
 196             }
 197
 198             ast::ExprUnary(_, ref inner) | ast::ExprParen(ref inner) =>
 199                 self.classify(&**inner),
 200
 201             ast::ExprBinary(_, ref a, ref b) =>
 202                 join(self.classify(&**a), self.classify(&**b)),
 203
 204             ast::ExprTup(ref es) |
 205             ast::ExprVec(ref es) =>
 206                 join_all(es.iter().map(|e| self.classify(&**e))),
 207
 208             ast::ExprVstore(ref e, vstore) => {
 209                 match vstore {
 210                     ast::ExprVstoreSlice => self.classify(&**e),
 211                     ast::ExprVstoreUniq |
 212                     ast::ExprVstoreMutSlice => non_const
 213                 }
 214             }
 215
 216             ast::ExprStruct(_, ref fs, None) => {
 217                 let cs = fs.iter().map(|f| self.classify(&*f.expr));
 218                 join_all(cs)
 219             }
 220
 221             ast::ExprCast(ref base, _) => {
 222                 let ty = ty::expr_ty(self.tcx, e);
 223                 let base = self.classify(&**base);
 224                 if ty::type_is_integral(ty) {
 225                     join(integral_const, base)
 226                 } else if ty::type_is_fp(ty) {
 227                     join(general_const, base)
 228                 } else {
 229                     non_const
 230                 }
 231             }
 232
 233             ast::ExprField(ref base, _, _) => self.classify(&**base),
 234
 235             ast::ExprIndex(ref base, ref idx) =>
 236                 join(self.classify(&**base), self.classify(&**idx)),
 237
 238             ast::ExprAddrOf(ast::MutImmutable, ref base) =>
 239                 self.classify(&**base),
 240
 241             // FIXME: (#3728) we can probably do something CCI-ish
 242             // surrounding nonlocal constants. But we don't yet.
 243             ast::ExprPath(_) => self.lookup_constness(e),
 244
 245             ast::ExprRepeat(..) => general_const,
 246
 247             ast::ExprBlock(ref block) => {
 248                 match block.expr {
 249                     Some(ref e) => self.classify(&**e),
 250                     None => integral_const
 251                 }
 252             }
 253
 254             _ => non_const
 255         };
 256         self.ccache.insert(did, cn);
 257         cn
 258     }
 259
 260     fn lookup_constness(&self, e: &Expr) -> constness {
 261         match lookup_const(self.tcx, e) {
 262             Some(rhs) => {
 263                 let ty = ty::expr_ty(self.tcx, &*rhs);
 264                 if ty::type_is_integral(ty) {
 265                     integral_const
 266                 } else {
 267                     general_const
 268                 }
 269             }
 270             None => non_const
 271         }
 272     }
 273
 274 }
 275
 276 impl<'a> Visitor<()> for ConstEvalVisitor<'a> {
 277     fn visit_expr_post(&mut self, e: &Expr, _: ()) {
 278         self.classify(e);
 279     }
 280 }
 281
 282 pub fn process_crate(krate: &ast::Crate,
 283                      tcx: &ty::ctxt) {
 284     let mut v = ConstEvalVisitor {
 285         tcx: tcx,
 286         ccache: DefIdMap::new(),
 287     };
 288     visit::walk_crate(&mut v, krate, ());
 289     tcx.sess.abort_if_errors();
 290 }
 291
 292
 293 // FIXME (#33): this doesn't handle big integer/float literals correctly
 294 // (nor does the rest of our literal handling).
 295 #[deriving(Clone, PartialEq)]
 296 pub enum const_val {
 297     const_float(f64),
 298     const_int(i64),
 299     const_uint(u64),
 300     const_str(InternedString),
 301     const_binary(Rc<Vec<u8> >),
 302     const_bool(bool)
 303 }
 304
 305 pub fn eval_const_expr(tcx: &ty::ctxt, e: &Expr) -> const_val {
 306     match eval_const_expr_partial(tcx, e) {
 307         Ok(r) => r,
 308         Err(s) => tcx.sess.span_fatal(e.span, s.as_slice())
 309     }
 310 }
 311
 312 pub fn eval_const_expr_partial<T: ty::ExprTyProvider>(tcx: &T, e: &Expr)
 313                             -> Result<const_val, String> {
 314     fn fromb(b: bool) -> Result<const_val, String> { Ok(const_int(b as i64)) }
 315     match e.node {
 316       ExprUnary(UnNeg, ref inner) => {
 317         match eval_const_expr_partial(tcx, &**inner) {
 318           Ok(const_float(f)) => Ok(const_float(-f)),
 319           Ok(const_int(i)) => Ok(const_int(-i)),
 320           Ok(const_uint(i)) => Ok(const_uint(-i)),
 321           Ok(const_str(_)) => Err("negate on string".to_string()),
 322           Ok(const_bool(_)) => Err("negate on boolean".to_string()),
 323           ref err => ((*err).clone())
 324         }
 325       }
 326       ExprUnary(UnNot, ref inner) => {
 327         match eval_const_expr_partial(tcx, &**inner) {
 328           Ok(const_int(i)) => Ok(const_int(!i)),
 329           Ok(const_uint(i)) => Ok(const_uint(!i)),
 330           Ok(const_bool(b)) => Ok(const_bool(!b)),
 331           _ => Err("not on float or string".to_string())
 332         }
 333       }
 334       ExprBinary(op, ref a, ref b) => {
 335         match (eval_const_expr_partial(tcx, &**a),
 336                eval_const_expr_partial(tcx, &**b)) {
 337           (Ok(const_float(a)), Ok(const_float(b))) => {
 338             match op {
 339               BiAdd => Ok(const_float(a + b)),
 340               BiSub => Ok(const_float(a - b)),
 341               BiMul => Ok(const_float(a * b)),
 342               BiDiv => Ok(const_float(a / b)),
 343               BiRem => Ok(const_float(a % b)),
 344               BiEq => fromb(a == b),
 345               BiLt => fromb(a < b),
 346               BiLe => fromb(a <= b),
 347               BiNe => fromb(a != b),
 348               BiGe => fromb(a >= b),
 349               BiGt => fromb(a > b),
 350               _ => Err("can't do this op on floats".to_string())
 351             }
 352           }
 353           (Ok(const_int(a)), Ok(const_int(b))) => {
 354             match op {
 355               BiAdd => Ok(const_int(a + b)),
 356               BiSub => Ok(const_int(a - b)),
 357               BiMul => Ok(const_int(a * b)),
 358               BiDiv if b == 0 => {
 359                   Err("attempted to divide by zero".to_string())
 360               }
 361               BiDiv => Ok(const_int(a / b)),
 362               BiRem if b == 0 => {
 363                   Err("attempted remainder with a divisor of \
 364                        zero".to_string())
 365               }
 366               BiRem => Ok(const_int(a % b)),
 367               BiAnd | BiBitAnd => Ok(const_int(a & b)),
 368               BiOr | BiBitOr => Ok(const_int(a | b)),
 369               BiBitXor => Ok(const_int(a ^ b)),
 370               BiShl => Ok(const_int(a << b as uint)),
 371               BiShr => Ok(const_int(a >> b as uint)),
 372               BiEq => fromb(a == b),
 373               BiLt => fromb(a < b),
 374               BiLe => fromb(a <= b),
 375               BiNe => fromb(a != b),
 376               BiGe => fromb(a >= b),
 377               BiGt => fromb(a > b)
 378             }
 379           }
 380           (Ok(const_uint(a)), Ok(const_uint(b))) => {
 381             match op {
 382               BiAdd => Ok(const_uint(a + b)),
 383               BiSub => Ok(const_uint(a - b)),
 384               BiMul => Ok(const_uint(a * b)),
 385               BiDiv if b == 0 => {
 386                   Err("attempted to divide by zero".to_string())
 387               }
 388               BiDiv => Ok(const_uint(a / b)),
 389               BiRem if b == 0 => {
 390                   Err("attempted remainder with a divisor of \
 391                        zero".to_string())
 392               }
 393               BiRem => Ok(const_uint(a % b)),
 394               BiAnd | BiBitAnd => Ok(const_uint(a & b)),
 395               BiOr | BiBitOr => Ok(const_uint(a | b)),
 396               BiBitXor => Ok(const_uint(a ^ b)),
 397               BiShl => Ok(const_uint(a << b as uint)),
 398               BiShr => Ok(const_uint(a >> b as uint)),
 399               BiEq => fromb(a == b),
 400               BiLt => fromb(a < b),
 401               BiLe => fromb(a <= b),
 402               BiNe => fromb(a != b),
 403               BiGe => fromb(a >= b),
 404               BiGt => fromb(a > b),
 405             }
 406           }
 407           // shifts can have any integral type as their rhs
 408           (Ok(const_int(a)), Ok(const_uint(b))) => {
 409             match op {
 410               BiShl => Ok(const_int(a << b as uint)),
 411               BiShr => Ok(const_int(a >> b as uint)),
 412               _ => Err("can't do this op on an int and uint".to_string())
 413             }
 414           }
 415           (Ok(const_uint(a)), Ok(const_int(b))) => {
 416             match op {
 417               BiShl => Ok(const_uint(a << b as uint)),
 418               BiShr => Ok(const_uint(a >> b as uint)),
 419               _ => Err("can't do this op on a uint and int".to_string())
 420             }
 421           }
 422           (Ok(const_bool(a)), Ok(const_bool(b))) => {
 423             Ok(const_bool(match op {
 424               BiAnd => a && b,
 425               BiOr => a || b,
 426               BiBitXor => a ^ b,
 427               BiBitAnd => a & b,
 428               BiBitOr => a | b,
 429               BiEq => a == b,
 430               BiNe => a != b,
 431               _ => return Err("can't do this op on bools".to_string())
 432              }))
 433           }
 434           _ => Err("bad operands for binary".to_string())
 435         }
 436       }
 437       ExprCast(ref base, ref target_ty) => {
 438         // This tends to get called w/o the type actually having been
 439         // populated in the ctxt, which was causing things to blow up
 440         // (#5900). Fall back to doing a limited lookup to get past it.
 441         let ety = ty::expr_ty_opt(tcx.ty_ctxt(), e)
 442                 .or_else(|| astconv::ast_ty_to_prim_ty(tcx.ty_ctxt(), &**target_ty))
 443                 .unwrap_or_else(|| {
 444                     tcx.ty_ctxt().sess.span_fatal(target_ty.span,
 445                                                   "target type not found for \
 446                                                    const cast")
 447                 });
 448
 449         let base = eval_const_expr_partial(tcx, &**base);
 450         match base {
 451             Err(_) => base,
 452             Ok(val) => {
 453                 match ty::get(ety).sty {
 454                     ty::ty_float(_) => {
 455                         match val {
 456                             const_uint(u) => Ok(const_float(u as f64)),
 457                             const_int(i) => Ok(const_float(i as f64)),
 458                             const_float(f) => Ok(const_float(f)),
 459                             _ => Err("can't cast float to str".to_string()),
 460                         }
 461                     }
 462                     ty::ty_uint(_) => {
 463                         match val {
 464                             const_uint(u) => Ok(const_uint(u)),
 465                             const_int(i) => Ok(const_uint(i as u64)),
 466                             const_float(f) => Ok(const_uint(f as u64)),
 467                             _ => Err("can't cast str to uint".to_string()),
 468                         }
 469                     }
 470                     ty::ty_int(_) | ty::ty_bool => {
 471                         match val {
 472                             const_uint(u) => Ok(const_int(u as i64)),
 473                             const_int(i) => Ok(const_int(i)),
 474                             const_float(f) => Ok(const_int(f as i64)),
 475                             _ => Err("can't cast str to int".to_string()),
 476                         }
 477                     }
 478                     _ => Err("can't cast this type".to_string())
 479                 }
 480             }
 481         }
 482       }
 483       ExprPath(_) => {
 484           match lookup_const(tcx.ty_ctxt(), e) {
 485               Some(actual_e) => eval_const_expr_partial(tcx.ty_ctxt(), &*actual_e),
 486               None => Err("non-constant path in constant expr".to_string())
 487           }
 488       }
 489       ExprLit(ref lit) => Ok(lit_to_const(&**lit)),
 490       // If we have a vstore, just keep going; it has to be a string
 491       ExprVstore(ref e, _) => eval_const_expr_partial(tcx, &**e),
 492       ExprParen(ref e)     => eval_const_expr_partial(tcx, &**e),
 493       ExprBlock(ref block) => {
 494         match block.expr {
 495             Some(ref expr) => eval_const_expr_partial(tcx, &**expr),
 496             None => Ok(const_int(0i64))
 497         }
 498       }
 499       _ => Err("unsupported constant expr".to_string())
 500     }
 501 }
 502
 503 pub fn lit_to_const(lit: &Lit) -> const_val {
 504     match lit.node {
 505         LitStr(ref s, _) => const_str((*s).clone()),
 506         LitBinary(ref data) => {
 507             const_binary(Rc::new(data.iter().map(|x| *x).collect()))
 508         }
 509         LitByte(n) => const_uint(n as u64),
 510         LitChar(n) => const_uint(n as u64),
 511         LitInt(n, _) => const_int(n),
 512         LitUint(n, _) => const_uint(n),
 513         LitIntUnsuffixed(n) => const_int(n),
 514         LitFloat(ref n, _) | LitFloatUnsuffixed(ref n) => {
 515             const_float(from_str::<f64>(n.get()).unwrap() as f64)
 516         }
 517         LitNil => const_int(0i64),
 518         LitBool(b) => const_bool(b)
 519     }
 520 }
 521
 522 fn compare_vals<T: PartialOrd>(a: T, b: T) -> Option<int> {
 523     Some(if a == b { 0 } else if a < b { -1 } else { 1 })
 524 }
 525 pub fn compare_const_vals(a: &const_val, b: &const_val) -> Option<int> {
 526     match (a, b) {
 527         (&const_int(a), &const_int(b)) => compare_vals(a, b),
 528         (&const_uint(a), &const_uint(b)) => compare_vals(a, b),
 529         (&const_float(a), &const_float(b)) => compare_vals(a, b),
 530         (&const_str(ref a), &const_str(ref b)) => compare_vals(a, b),
 531         (&const_bool(a), &const_bool(b)) => compare_vals(a, b),
 532         (&const_binary(ref a), &const_binary(ref b)) => compare_vals(a, b),
 533         _ => None
 534     }
 535 }
 536
 537 pub fn compare_lit_exprs(tcx: &ty::ctxt, a: &Expr, b: &Expr) -> Option<int> {
 538     compare_const_vals(&eval_const_expr(tcx, a), &eval_const_expr(tcx, b))
 539 }