src/librustc/middle/const_eval.rs

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