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 use middle::def;
  17 use middle::pat_util::def_to_path;
  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, 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     const_nil
 304 }
 305
 306 pub fn const_expr_to_pat(tcx: &ty::ctxt, expr: Gc<Expr>) -> Gc<Pat> {
 307     let pat = match expr.node {
 308         ExprTup(ref exprs) =>
 309             PatTup(exprs.iter().map(|&expr| const_expr_to_pat(tcx, expr)).collect()),
 310
 311         ExprCall(callee, ref args) => {
 312             let def = tcx.def_map.borrow().get_copy(&callee.id);
 313             tcx.def_map.borrow_mut().find_or_insert(expr.id, def);
 314             let path = match def {
 315                 def::DefStruct(def_id) => def_to_path(tcx, def_id),
 316                 def::DefVariant(_, variant_did, _) => def_to_path(tcx, variant_did),
 317                 _ => unreachable!()
 318             };
 319             let pats = args.iter().map(|&expr| const_expr_to_pat(tcx, expr)).collect();
 320             PatEnum(path, Some(pats))
 321         }
 322
 323         ExprStruct(ref path, ref fields, None) => {
 324             let field_pats = fields.iter().map(|field| FieldPat {
 325                 ident: field.ident.node,
 326                 pat: const_expr_to_pat(tcx, field.expr)
 327             }).collect();
 328             PatStruct(path.clone(), field_pats, false)
 329         }
 330
 331         ExprVec(ref exprs) => {
 332             let pats = exprs.iter().map(|&expr| const_expr_to_pat(tcx, expr)).collect();
 333             PatVec(pats, None, vec![])
 334         }
 335
 336         ExprPath(ref path) => {
 337             let opt_def = tcx.def_map.borrow().find_copy(&expr.id);
 338             match opt_def {
 339                 Some(def::DefStruct(..)) =>
 340                     PatStruct(path.clone(), vec![], false),
 341                 Some(def::DefVariant(..)) =>
 342                     PatEnum(path.clone(), None),
 343                 _ => {
 344                     match lookup_const(tcx, &*expr) {
 345                         Some(actual) => return const_expr_to_pat(tcx, actual),
 346                         _ => unreachable!()
 347                     }
 348                 }
 349             }
 350         }
 351
 352         _ => PatLit(expr)
 353     };
 354     box (GC) Pat { id: expr.id, node: pat, span: expr.span }
 355 }
 356
 357 pub fn eval_const_expr(tcx: &ty::ctxt, e: &Expr) -> const_val {
 358     match eval_const_expr_partial(tcx, e) {
 359         Ok(r) => r,
 360         Err(s) => tcx.sess.span_fatal(e.span, s.as_slice())
 361     }
 362 }
 363
 364 pub fn eval_const_expr_partial<T: ty::ExprTyProvider>(tcx: &T, e: &Expr)
 365                             -> Result<const_val, String> {
 366     fn fromb(b: bool) -> Result<const_val, String> { Ok(const_int(b as i64)) }
 367     match e.node {
 368       ExprUnary(UnNeg, ref inner) => {
 369         match eval_const_expr_partial(tcx, &**inner) {
 370           Ok(const_float(f)) => Ok(const_float(-f)),
 371           Ok(const_int(i)) => Ok(const_int(-i)),
 372           Ok(const_uint(i)) => Ok(const_uint(-i)),
 373           Ok(const_str(_)) => Err("negate on string".to_string()),
 374           Ok(const_bool(_)) => Err("negate on boolean".to_string()),
 375           ref err => ((*err).clone())
 376         }
 377       }
 378       ExprUnary(UnNot, ref inner) => {
 379         match eval_const_expr_partial(tcx, &**inner) {
 380           Ok(const_int(i)) => Ok(const_int(!i)),
 381           Ok(const_uint(i)) => Ok(const_uint(!i)),
 382           Ok(const_bool(b)) => Ok(const_bool(!b)),
 383           _ => Err("not on float or string".to_string())
 384         }
 385       }
 386       ExprBinary(op, ref a, ref b) => {
 387         match (eval_const_expr_partial(tcx, &**a),
 388                eval_const_expr_partial(tcx, &**b)) {
 389           (Ok(const_float(a)), Ok(const_float(b))) => {
 390             match op {
 391               BiAdd => Ok(const_float(a + b)),
 392               BiSub => Ok(const_float(a - b)),
 393               BiMul => Ok(const_float(a * b)),
 394               BiDiv => Ok(const_float(a / b)),
 395               BiRem => Ok(const_float(a % b)),
 396               BiEq => fromb(a == b),
 397               BiLt => fromb(a < b),
 398               BiLe => fromb(a <= b),
 399               BiNe => fromb(a != b),
 400               BiGe => fromb(a >= b),
 401               BiGt => fromb(a > b),
 402               _ => Err("can't do this op on floats".to_string())
 403             }
 404           }
 405           (Ok(const_int(a)), Ok(const_int(b))) => {
 406             match op {
 407               BiAdd => Ok(const_int(a + b)),
 408               BiSub => Ok(const_int(a - b)),
 409               BiMul => Ok(const_int(a * b)),
 410               BiDiv if b == 0 => {
 411                   Err("attempted to divide by zero".to_string())
 412               }
 413               BiDiv => Ok(const_int(a / b)),
 414               BiRem if b == 0 => {
 415                   Err("attempted remainder with a divisor of \
 416                        zero".to_string())
 417               }
 418               BiRem => Ok(const_int(a % b)),
 419               BiAnd | BiBitAnd => Ok(const_int(a & b)),
 420               BiOr | BiBitOr => Ok(const_int(a | b)),
 421               BiBitXor => Ok(const_int(a ^ b)),
 422               BiShl => Ok(const_int(a << b as uint)),
 423               BiShr => Ok(const_int(a >> b as uint)),
 424               BiEq => fromb(a == b),
 425               BiLt => fromb(a < b),
 426               BiLe => fromb(a <= b),
 427               BiNe => fromb(a != b),
 428               BiGe => fromb(a >= b),
 429               BiGt => fromb(a > b)
 430             }
 431           }
 432           (Ok(const_uint(a)), Ok(const_uint(b))) => {
 433             match op {
 434               BiAdd => Ok(const_uint(a + b)),
 435               BiSub => Ok(const_uint(a - b)),
 436               BiMul => Ok(const_uint(a * b)),
 437               BiDiv if b == 0 => {
 438                   Err("attempted to divide by zero".to_string())
 439               }
 440               BiDiv => Ok(const_uint(a / b)),
 441               BiRem if b == 0 => {
 442                   Err("attempted remainder with a divisor of \
 443                        zero".to_string())
 444               }
 445               BiRem => Ok(const_uint(a % b)),
 446               BiAnd | BiBitAnd => Ok(const_uint(a & b)),
 447               BiOr | BiBitOr => Ok(const_uint(a | b)),
 448               BiBitXor => Ok(const_uint(a ^ b)),
 449               BiShl => Ok(const_uint(a << b as uint)),
 450               BiShr => Ok(const_uint(a >> b as uint)),
 451               BiEq => fromb(a == b),
 452               BiLt => fromb(a < b),
 453               BiLe => fromb(a <= b),
 454               BiNe => fromb(a != b),
 455               BiGe => fromb(a >= b),
 456               BiGt => fromb(a > b),
 457             }
 458           }
 459           // shifts can have any integral type as their rhs
 460           (Ok(const_int(a)), Ok(const_uint(b))) => {
 461             match op {
 462               BiShl => Ok(const_int(a << b as uint)),
 463               BiShr => Ok(const_int(a >> b as uint)),
 464               _ => Err("can't do this op on an int and uint".to_string())
 465             }
 466           }
 467           (Ok(const_uint(a)), Ok(const_int(b))) => {
 468             match op {
 469               BiShl => Ok(const_uint(a << b as uint)),
 470               BiShr => Ok(const_uint(a >> b as uint)),
 471               _ => Err("can't do this op on a uint and int".to_string())
 472             }
 473           }
 474           (Ok(const_bool(a)), Ok(const_bool(b))) => {
 475             Ok(const_bool(match op {
 476               BiAnd => a && b,
 477               BiOr => a || b,
 478               BiBitXor => a ^ b,
 479               BiBitAnd => a & b,
 480               BiBitOr => a | b,
 481               BiEq => a == b,
 482               BiNe => a != b,
 483               _ => return Err("can't do this op on bools".to_string())
 484              }))
 485           }
 486           _ => Err("bad operands for binary".to_string())
 487         }
 488       }
 489       ExprCast(ref base, ref target_ty) => {
 490         // This tends to get called w/o the type actually having been
 491         // populated in the ctxt, which was causing things to blow up
 492         // (#5900). Fall back to doing a limited lookup to get past it.
 493         let ety = ty::expr_ty_opt(tcx.ty_ctxt(), e)
 494                 .or_else(|| astconv::ast_ty_to_prim_ty(tcx.ty_ctxt(), &**target_ty))
 495                 .unwrap_or_else(|| {
 496                     tcx.ty_ctxt().sess.span_fatal(target_ty.span,
 497                                                   "target type not found for \
 498                                                    const cast")
 499                 });
 500
 501         let base = eval_const_expr_partial(tcx, &**base);
 502         match base {
 503             Err(_) => base,
 504             Ok(val) => {
 505                 match ty::get(ety).sty {
 506                     ty::ty_float(_) => {
 507                         match val {
 508                             const_uint(u) => Ok(const_float(u as f64)),
 509                             const_int(i) => Ok(const_float(i as f64)),
 510                             const_float(f) => Ok(const_float(f)),
 511                             _ => Err("can't cast float to str".to_string()),
 512                         }
 513                     }
 514                     ty::ty_uint(_) => {
 515                         match val {
 516                             const_uint(u) => Ok(const_uint(u)),
 517                             const_int(i) => Ok(const_uint(i as u64)),
 518                             const_float(f) => Ok(const_uint(f as u64)),
 519                             _ => Err("can't cast str to uint".to_string()),
 520                         }
 521                     }
 522                     ty::ty_int(_) | ty::ty_bool => {
 523                         match val {
 524                             const_uint(u) => Ok(const_int(u as i64)),
 525                             const_int(i) => Ok(const_int(i)),
 526                             const_float(f) => Ok(const_int(f as i64)),
 527                             _ => Err("can't cast str to int".to_string()),
 528                         }
 529                     }
 530                     _ => Err("can't cast this type".to_string())
 531                 }
 532             }
 533         }
 534       }
 535       ExprPath(_) => {
 536           match lookup_const(tcx.ty_ctxt(), e) {
 537               Some(actual_e) => eval_const_expr_partial(tcx.ty_ctxt(), &*actual_e),
 538               None => Err("non-constant path in constant expr".to_string())
 539           }
 540       }
 541       ExprLit(ref lit) => Ok(lit_to_const(&**lit)),
 542       // If we have a vstore, just keep going; it has to be a string
 543       ExprVstore(ref e, _) => eval_const_expr_partial(tcx, &**e),
 544       ExprParen(ref e)     => eval_const_expr_partial(tcx, &**e),
 545       ExprBlock(ref block) => {
 546         match block.expr {
 547             Some(ref expr) => eval_const_expr_partial(tcx, &**expr),
 548             None => Ok(const_int(0i64))
 549         }
 550       }
 551       _ => Err("unsupported constant expr".to_string())
 552     }
 553 }
 554
 555 pub fn lit_to_const(lit: &Lit) -> const_val {
 556     match lit.node {
 557         LitStr(ref s, _) => const_str((*s).clone()),
 558         LitBinary(ref data) => {
 559             const_binary(Rc::new(data.iter().map(|x| *x).collect()))
 560         }
 561         LitByte(n) => const_uint(n as u64),
 562         LitChar(n) => const_uint(n as u64),
 563         LitInt(n, _) => const_int(n),
 564         LitUint(n, _) => const_uint(n),
 565         LitIntUnsuffixed(n) => const_int(n),
 566         LitFloat(ref n, _) | LitFloatUnsuffixed(ref n) => {
 567             const_float(from_str::<f64>(n.get()).unwrap() as f64)
 568         }
 569         LitNil => const_nil,
 570         LitBool(b) => const_bool(b)
 571     }
 572 }
 573
 574 fn compare_vals<T: PartialOrd>(a: T, b: T) -> Option<int> {
 575     Some(if a == b { 0 } else if a < b { -1 } else { 1 })
 576 }
 577 pub fn compare_const_vals(a: &const_val, b: &const_val) -> Option<int> {
 578     match (a, b) {
 579         (&const_int(a), &const_int(b)) => compare_vals(a, b),
 580         (&const_uint(a), &const_uint(b)) => compare_vals(a, b),
 581         (&const_float(a), &const_float(b)) => compare_vals(a, b),
 582         (&const_str(ref a), &const_str(ref b)) => compare_vals(a, b),
 583         (&const_bool(a), &const_bool(b)) => compare_vals(a, b),
 584         (&const_binary(ref a), &const_binary(ref b)) => compare_vals(a, b),
 585         (&const_nil, &const_nil) => compare_vals((), ()),
 586         _ => None
 587     }
 588 }
 589
 590 pub fn compare_lit_exprs(tcx: &ty::ctxt, a: &Expr, b: &Expr) -> Option<int> {
 591     compare_const_vals(&eval_const_expr(tcx, a), &eval_const_expr(tcx, b))
 592 }