src/librustc/middle/const_eval.rs

   1 // Copyright 2012-2013 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
  12 use metadata::csearch;
  13 use middle::astencode;
  14 use middle::ty;
  15 use middle;
  16
  17 use syntax::{ast, ast_map, ast_util, oldvisit};
  18 use syntax::ast::*;
  19
  20 use std::float;
  21 use std::hashmap::{HashMap, HashSet};
  22
  23 //
  24 // This pass classifies expressions by their constant-ness.
  25 //
  26 // Constant-ness comes in 3 flavours:
  27 //
  28 //   - Integer-constants: can be evaluated by the frontend all the way down
  29 //     to their actual value. They are used in a few places (enum
  30 //     discriminants, switch arms) and are a subset of
  31 //     general-constants. They cover all the integer and integer-ish
  32 //     literals (nil, bool, int, uint, char, iNN, uNN) and all integer
  33 //     operators and copies applied to them.
  34 //
  35 //   - General-constants: can be evaluated by LLVM but not necessarily by
  36 //     the frontend; usually due to reliance on target-specific stuff such
  37 //     as "where in memory the value goes" or "what floating point mode the
  38 //     target uses". This _includes_ integer-constants, plus the following
  39 //     constructors:
  40 //
  41 //        fixed-size vectors and strings: [] and ""/_
  42 //        vector and string slices: &[] and &""
  43 //        tuples: (,)
  44 //        records: {...}
  45 //        enums: foo(...)
  46 //        floating point literals and operators
  47 //        & and * pointers
  48 //        copies of general constants
  49 //
  50 //        (in theory, probably not at first: if/match on integer-const
  51 //         conditions / descriminants)
  52 //
  53 //   - Non-constants: everything else.
  54 //
  55
  56 pub enum constness {
  57     integral_const,
  58     general_const,
  59     non_const
  60 }
  61
  62 pub fn join(a: constness, b: constness) -> constness {
  63     match (a, b) {
  64       (integral_const, integral_const) => integral_const,
  65       (integral_const, general_const)
  66       | (general_const, integral_const)
  67       | (general_const, general_const) => general_const,
  68       _ => non_const
  69     }
  70 }
  71
  72 pub fn join_all<It: Iterator<constness>>(mut cs: It) -> constness {
  73     cs.fold(integral_const, |a, b| join(a, b))
  74 }
  75
  76 pub fn classify(e: &expr,
  77                 tcx: ty::ctxt)
  78              -> constness {
  79     let did = ast_util::local_def(e.id);
  80     match tcx.ccache.find(&did) {
  81       Some(&x) => x,
  82       None => {
  83         let cn =
  84             match e.node {
  85               ast::expr_lit(lit) => {
  86                 match lit.node {
  87                   ast::lit_str(*) |
  88                   ast::lit_float(*) => general_const,
  89                   _ => integral_const
  90                 }
  91               }
  92
  93               ast::expr_unary(_, _, inner) |
  94               ast::expr_paren(inner) => {
  95                 classify(inner, tcx)
  96               }
  97
  98               ast::expr_binary(_, _, a, b) => {
  99                 join(classify(a, tcx),
 100                      classify(b, tcx))
 101               }
 102
 103               ast::expr_tup(ref es) |
 104               ast::expr_vec(ref es, ast::m_imm) => {
 105                 join_all(es.iter().map(|e| classify(*e, tcx)))
 106               }
 107
 108               ast::expr_vstore(e, vstore) => {
 109                   match vstore {
 110                       ast::expr_vstore_slice => classify(e, tcx),
 111                       ast::expr_vstore_uniq |
 112                       ast::expr_vstore_box |
 113                       ast::expr_vstore_mut_box |
 114                       ast::expr_vstore_mut_slice => non_const
 115                   }
 116               }
 117
 118               ast::expr_struct(_, ref fs, None) => {
 119                 let cs = do fs.iter().map |f| {
 120                     classify(f.expr, tcx)
 121                 };
 122                 join_all(cs)
 123               }
 124
 125               ast::expr_cast(base, _) => {
 126                 let ty = ty::expr_ty(tcx, e);
 127                 let base = classify(base, tcx);
 128                 if ty::type_is_integral(ty) {
 129                     join(integral_const, base)
 130                 } else if ty::type_is_fp(ty) {
 131                     join(general_const, base)
 132                 } else {
 133                     non_const
 134                 }
 135               }
 136
 137               ast::expr_field(base, _, _) => {
 138                 classify(base, tcx)
 139               }
 140
 141               ast::expr_index(_, base, idx) => {
 142                 join(classify(base, tcx),
 143                      classify(idx, tcx))
 144               }
 145
 146               ast::expr_addr_of(ast::m_imm, base) => {
 147                 classify(base, tcx)
 148               }
 149
 150               // FIXME: (#3728) we can probably do something CCI-ish
 151               // surrounding nonlocal constants. But we don't yet.
 152               ast::expr_path(_) => {
 153                 lookup_constness(tcx, e)
 154               }
 155
 156               ast::expr_repeat(*) => general_const,
 157
 158               _ => non_const
 159             };
 160         tcx.ccache.insert(did, cn);
 161         cn
 162       }
 163     }
 164 }
 165
 166 pub fn lookup_const(tcx: ty::ctxt, e: &expr) -> Option<@expr> {
 167     match tcx.def_map.find(&e.id) {
 168         Some(&ast::def_static(def_id, false)) => lookup_const_by_id(tcx, def_id),
 169         Some(&ast::def_variant(enum_def, variant_def)) => lookup_variant_by_id(tcx,
 170                                                                                enum_def,
 171                                                                                variant_def),
 172         _ => None
 173     }
 174 }
 175
 176 pub fn lookup_variant_by_id(tcx: ty::ctxt,
 177                             enum_def: ast::def_id,
 178                             variant_def: ast::def_id)
 179                        -> Option<@expr> {
 180     fn variant_expr(variants: &[ast::variant], id: ast::NodeId) -> Option<@expr> {
 181         for variant in variants.iter() {
 182             if variant.node.id == id {
 183                 return variant.node.disr_expr;
 184             }
 185         }
 186         None
 187     }
 188
 189     if ast_util::is_local(enum_def) {
 190         match tcx.items.find(&enum_def.node) {
 191             None => None,
 192             Some(&ast_map::node_item(it, _)) => match it.node {
 193                 item_enum(ast::enum_def { variants: ref variants }, _) => {
 194                     variant_expr(*variants, variant_def.node)
 195                 }
 196                 _ => None
 197             },
 198             Some(_) => None
 199         }
 200     } else {
 201         let maps = astencode::Maps {
 202             root_map: @mut HashMap::new(),
 203             method_map: @mut HashMap::new(),
 204             vtable_map: @mut HashMap::new(),
 205             write_guard_map: @mut HashSet::new(),
 206             capture_map: @mut HashMap::new()
 207         };
 208         match csearch::maybe_get_item_ast(tcx, enum_def,
 209             |a, b, c, d| astencode::decode_inlined_item(a,
 210                                                         b,
 211                                                         maps,
 212                                                         /*bad*/ c.clone(),
 213                                                         d)) {
 214             csearch::found(ast::ii_item(item)) => match item.node {
 215                 item_enum(ast::enum_def { variants: ref variants }, _) => {
 216                     variant_expr(*variants, variant_def.node)
 217                 }
 218                 _ => None
 219             },
 220             _ => None
 221         }
 222     }
 223 }
 224
 225 pub fn lookup_const_by_id(tcx: ty::ctxt,
 226                           def_id: ast::def_id)
 227                        -> Option<@expr> {
 228     if ast_util::is_local(def_id) {
 229         match tcx.items.find(&def_id.node) {
 230             None => None,
 231             Some(&ast_map::node_item(it, _)) => match it.node {
 232                 item_static(_, ast::m_imm, const_expr) => Some(const_expr),
 233                 _ => None
 234             },
 235             Some(_) => None
 236         }
 237     } else {
 238         let maps = astencode::Maps {
 239             root_map: @mut HashMap::new(),
 240             method_map: @mut HashMap::new(),
 241             vtable_map: @mut HashMap::new(),
 242             write_guard_map: @mut HashSet::new(),
 243             capture_map: @mut HashMap::new()
 244         };
 245         match csearch::maybe_get_item_ast(tcx, def_id,
 246             |a, b, c, d| astencode::decode_inlined_item(a, b, maps, c, d)) {
 247             csearch::found(ast::ii_item(item)) => match item.node {
 248                 item_static(_, ast::m_imm, const_expr) => Some(const_expr),
 249                 _ => None
 250             },
 251             _ => None
 252         }
 253     }
 254 }
 255
 256 pub fn lookup_constness(tcx: ty::ctxt, e: &expr) -> constness {
 257     match lookup_const(tcx, e) {
 258         Some(rhs) => {
 259             let ty = ty::expr_ty(tcx, rhs);
 260             if ty::type_is_integral(ty) {
 261                 integral_const
 262             } else {
 263                 general_const
 264             }
 265         }
 266         None => non_const
 267     }
 268 }
 269
 270 pub fn process_crate(crate: &ast::Crate,
 271                      tcx: ty::ctxt) {
 272     let v = oldvisit::mk_simple_visitor(@oldvisit::SimpleVisitor {
 273         visit_expr_post: |e| { classify(e, tcx); },
 274         .. *oldvisit::default_simple_visitor()
 275     });
 276     oldvisit::visit_crate(crate, ((), v));
 277     tcx.sess.abort_if_errors();
 278 }
 279
 280
 281 // FIXME (#33): this doesn't handle big integer/float literals correctly
 282 // (nor does the rest of our literal handling).
 283 #[deriving(Clone, Eq)]
 284 pub enum const_val {
 285     const_float(f64),
 286     const_int(i64),
 287     const_uint(u64),
 288     const_str(@str),
 289     const_bool(bool)
 290 }
 291
 292 pub fn eval_const_expr(tcx: middle::ty::ctxt, e: &expr) -> const_val {
 293     match eval_const_expr_partial(&tcx, e) {
 294         Ok(r) => r,
 295         Err(s) => tcx.sess.span_fatal(e.span, s)
 296     }
 297 }
 298
 299 pub fn eval_const_expr_partial<T: ty::ExprTyProvider>(tcx: &T, e: &expr)
 300                             -> Result<const_val, ~str> {
 301     use middle::ty;
 302     fn fromb(b: bool) -> Result<const_val, ~str> { Ok(const_int(b as i64)) }
 303     match e.node {
 304       expr_unary(_, neg, inner) => {
 305         match eval_const_expr_partial(tcx, inner) {
 306           Ok(const_float(f)) => Ok(const_float(-f)),
 307           Ok(const_int(i)) => Ok(const_int(-i)),
 308           Ok(const_uint(i)) => Ok(const_uint(-i)),
 309           Ok(const_str(_)) => Err(~"Negate on string"),
 310           Ok(const_bool(_)) => Err(~"Negate on boolean"),
 311           ref err => ((*err).clone())
 312         }
 313       }
 314       expr_unary(_, not, inner) => {
 315         match eval_const_expr_partial(tcx, inner) {
 316           Ok(const_int(i)) => Ok(const_int(!i)),
 317           Ok(const_uint(i)) => Ok(const_uint(!i)),
 318           Ok(const_bool(b)) => Ok(const_bool(!b)),
 319           _ => Err(~"Not on float or string")
 320         }
 321       }
 322       expr_binary(_, op, a, b) => {
 323         match (eval_const_expr_partial(tcx, a),
 324                eval_const_expr_partial(tcx, b)) {
 325           (Ok(const_float(a)), Ok(const_float(b))) => {
 326             match op {
 327               add => Ok(const_float(a + b)),
 328               subtract => Ok(const_float(a - b)),
 329               mul => Ok(const_float(a * b)),
 330               div => Ok(const_float(a / b)),
 331               rem => Ok(const_float(a % b)),
 332               eq => fromb(a == b),
 333               lt => fromb(a < b),
 334               le => fromb(a <= b),
 335               ne => fromb(a != b),
 336               ge => fromb(a >= b),
 337               gt => fromb(a > b),
 338               _ => Err(~"Can't do this op on floats")
 339             }
 340           }
 341           (Ok(const_int(a)), Ok(const_int(b))) => {
 342             match op {
 343               add => Ok(const_int(a + b)),
 344               subtract => Ok(const_int(a - b)),
 345               mul => Ok(const_int(a * b)),
 346               div if b == 0 => Err(~"attempted to divide by zero"),
 347               div => Ok(const_int(a / b)),
 348               rem if b == 0 => Err(~"attempted remainder with a divisor of zero"),
 349               rem => Ok(const_int(a % b)),
 350               and | bitand => Ok(const_int(a & b)),
 351               or | bitor => Ok(const_int(a | b)),
 352               bitxor => Ok(const_int(a ^ b)),
 353               shl => Ok(const_int(a << b)),
 354               shr => Ok(const_int(a >> b)),
 355               eq => fromb(a == b),
 356               lt => fromb(a < b),
 357               le => fromb(a <= b),
 358               ne => fromb(a != b),
 359               ge => fromb(a >= b),
 360               gt => fromb(a > b)
 361             }
 362           }
 363           (Ok(const_uint(a)), Ok(const_uint(b))) => {
 364             match op {
 365               add => Ok(const_uint(a + b)),
 366               subtract => Ok(const_uint(a - b)),
 367               mul => Ok(const_uint(a * b)),
 368               div if b == 0 => Err(~"attempted to divide by zero"),
 369               div => Ok(const_uint(a / b)),
 370               rem if b == 0 => Err(~"attempted remainder with a divisor of zero"),
 371               rem => Ok(const_uint(a % b)),
 372               and | bitand => Ok(const_uint(a & b)),
 373               or | bitor => Ok(const_uint(a | b)),
 374               bitxor => Ok(const_uint(a ^ b)),
 375               shl => Ok(const_uint(a << b)),
 376               shr => Ok(const_uint(a >> b)),
 377               eq => fromb(a == b),
 378               lt => fromb(a < b),
 379               le => fromb(a <= b),
 380               ne => fromb(a != b),
 381               ge => fromb(a >= b),
 382               gt => fromb(a > b),
 383             }
 384           }
 385           // shifts can have any integral type as their rhs
 386           (Ok(const_int(a)), Ok(const_uint(b))) => {
 387             match op {
 388               shl => Ok(const_int(a << b)),
 389               shr => Ok(const_int(a >> b)),
 390               _ => Err(~"Can't do this op on an int and uint")
 391             }
 392           }
 393           (Ok(const_uint(a)), Ok(const_int(b))) => {
 394             match op {
 395               shl => Ok(const_uint(a << b)),
 396               shr => Ok(const_uint(a >> b)),
 397               _ => Err(~"Can't do this op on a uint and int")
 398             }
 399           }
 400           (Ok(const_bool(a)), Ok(const_bool(b))) => {
 401             Ok(const_bool(match op {
 402               and => a && b,
 403               or => a || b,
 404               bitxor => a ^ b,
 405               bitand => a & b,
 406               bitor => a | b,
 407               eq => a == b,
 408               ne => a != b,
 409               _ => return Err(~"Can't do this op on bools")
 410              }))
 411           }
 412           _ => Err(~"Bad operands for binary")
 413         }
 414       }
 415       expr_cast(base, _) => {
 416         let ety = tcx.expr_ty(e);
 417         let base = eval_const_expr_partial(tcx, base);
 418         match base {
 419             Err(_) => base,
 420             Ok(val) => {
 421                 match ty::get(ety).sty {
 422                     ty::ty_float(_) => {
 423                         match val {
 424                             const_uint(u) => Ok(const_float(u as f64)),
 425                             const_int(i) => Ok(const_float(i as f64)),
 426                             const_float(f) => Ok(const_float(f)),
 427                             _ => Err(~"Can't cast float to str"),
 428                         }
 429                     }
 430                     ty::ty_uint(_) => {
 431                         match val {
 432                             const_uint(u) => Ok(const_uint(u)),
 433                             const_int(i) => Ok(const_uint(i as u64)),
 434                             const_float(f) => Ok(const_uint(f as u64)),
 435                             _ => Err(~"Can't cast str to uint"),
 436                         }
 437                     }
 438                     ty::ty_int(_) | ty::ty_bool => {
 439                         match val {
 440                             const_uint(u) => Ok(const_int(u as i64)),
 441                             const_int(i) => Ok(const_int(i)),
 442                             const_float(f) => Ok(const_int(f as i64)),
 443                             _ => Err(~"Can't cast str to int"),
 444                         }
 445                     }
 446                     _ => Err(~"Can't cast this type")
 447                 }
 448             }
 449         }
 450       }
 451       expr_path(_) => {
 452           match lookup_const(tcx.ty_ctxt(), e) {
 453               Some(actual_e) => eval_const_expr_partial(&tcx.ty_ctxt(), actual_e),
 454               None => Err(~"Non-constant path in constant expr")
 455           }
 456       }
 457       expr_lit(lit) => Ok(lit_to_const(lit)),
 458       // If we have a vstore, just keep going; it has to be a string
 459       expr_vstore(e, _) => eval_const_expr_partial(tcx, e),
 460       expr_paren(e)     => eval_const_expr_partial(tcx, e),
 461       _ => Err(~"Unsupported constant expr")
 462     }
 463 }
 464
 465 pub fn lit_to_const(lit: &lit) -> const_val {
 466     match lit.node {
 467       lit_str(s) => const_str(s),
 468       lit_int(n, _) => const_int(n),
 469       lit_uint(n, _) => const_uint(n),
 470       lit_int_unsuffixed(n) => const_int(n),
 471       lit_float(n, _) => const_float(float::from_str(n).unwrap() as f64),
 472       lit_float_unsuffixed(n) =>
 473         const_float(float::from_str(n).unwrap() as f64),
 474       lit_nil => const_int(0i64),
 475       lit_bool(b) => const_bool(b)
 476     }
 477 }
 478
 479 fn compare_vals<T : Eq + Ord>(a: T, b: T) -> Option<int> {
 480     Some(if a == b { 0 } else if a < b { -1 } else { 1 })
 481 }
 482 pub fn compare_const_vals(a: &const_val, b: &const_val) -> Option<int> {
 483     match (a, b) {
 484         (&const_int(a), &const_int(b)) => compare_vals(a, b),
 485         (&const_uint(a), &const_uint(b)) => compare_vals(a, b),
 486         (&const_float(a), &const_float(b)) => compare_vals(a, b),
 487         (&const_str(a), &const_str(b)) => compare_vals(a, b),
 488         (&const_bool(a), &const_bool(b)) => compare_vals(a, b),
 489         _ => None
 490     }
 491 }
 492
 493 pub fn compare_lit_exprs(tcx: middle::ty::ctxt, a: &expr, b: &expr) -> Option<int> {
 494     compare_const_vals(&eval_const_expr(tcx, a), &eval_const_expr(tcx, b))
 495 }
 496
 497 pub fn lit_expr_eq(tcx: middle::ty::ctxt, a: &expr, b: &expr) -> Option<bool> {
 498     compare_lit_exprs(tcx, a, b).map_move(|val| val == 0)
 499 }
 500
 501 pub fn lit_eq(a: &lit, b: &lit) -> Option<bool> {
 502     compare_const_vals(&lit_to_const(a), &lit_to_const(b)).map_move(|val| val == 0)
 503 }