1 #![allow(cast_possible_truncation)]
3 use rustc::lint::LateContext;
4 use rustc::middle::const_eval::lookup_const_by_id;
5 use rustc::middle::def::PathResolution;
6 use rustc::middle::def::Def::*;
7 use rustc_front::hir::*;
10 use std::cmp::PartialOrd;
11 use std::cmp::Ordering::{self, Greater, Less, Equal};
15 use self::Constant::*;
16 use self::FloatWidth::*;
18 use syntax::ast::Lit_::*;
19 use syntax::ast::Lit_;
20 use syntax::ast::LitIntType::*;
21 use syntax::ast::LitIntType;
22 use syntax::ast::{UintTy, FloatTy, StrStyle};
23 use syntax::ast::FloatTy::*;
24 use syntax::ast::Sign::{self, Plus, Minus};
27 #[derive(PartialEq, Eq, Debug, Copy, Clone)]
34 impl From<FloatTy> for FloatWidth {
35 fn from(ty: FloatTy) -> FloatWidth {
43 /// a Lit_-like enum to fold constant `Expr`s into
44 #[derive(Eq, Debug, Clone)]
47 ConstantStr(String, StrStyle),
48 /// a Binary String b"abc"
49 ConstantBinary(Rc<Vec<u8>>),
50 /// a single byte b'a'
55 ConstantInt(u64, LitIntType),
56 /// a float with given type
57 ConstantFloat(String, FloatWidth),
60 /// an array of constants
61 ConstantVec(Vec<Constant>),
62 /// also an array, but with only one constant, repeated N times
63 ConstantRepeat(Box<Constant>, usize),
64 /// a tuple of constants
65 ConstantTuple(Vec<Constant>),
69 /// convert to u64 if possible
73 /// if the constant could not be converted to u64 losslessly
74 fn as_u64(&self) -> u64 {
75 if let ConstantInt(val, _) = *self {
76 val // TODO we may want to check the sign if any
78 panic!("Could not convert a {:?} to u64", self);
82 /// convert this constant to a f64, if possible
83 #[allow(cast_precision_loss)]
84 pub fn as_float(&self) -> Option<f64> {
86 ConstantByte(b) => Some(b as f64),
87 ConstantFloat(ref s, _) => s.parse().ok(),
88 ConstantInt(i, ty) => Some(if is_negative(ty) {
89 -(i as f64) } else { i as f64 }),
95 impl PartialEq for Constant {
96 fn eq(&self, other: &Constant) -> bool {
98 (&ConstantStr(ref ls, ref lsty), &ConstantStr(ref rs, ref rsty)) =>
99 ls == rs && lsty == rsty,
100 (&ConstantBinary(ref l), &ConstantBinary(ref r)) => l == r,
101 (&ConstantByte(l), &ConstantByte(r)) => l == r,
102 (&ConstantChar(l), &ConstantChar(r)) => l == r,
103 (&ConstantInt(lv, lty), &ConstantInt(rv, rty)) => lv == rv &&
104 (is_negative(lty) & (lv != 0)) == (is_negative(rty) & (rv != 0)),
105 (&ConstantFloat(ref ls, lw), &ConstantFloat(ref rs, rw)) =>
107 (FwAny, _) | (_, FwAny) | (Fw32, Fw32) | (Fw64, Fw64) => true,
110 match (ls.parse::<f64>(), rs.parse::<f64>()) {
111 (Ok(l), Ok(r)) => l.eq(&r),
115 (&ConstantBool(l), &ConstantBool(r)) => l == r,
116 (&ConstantVec(ref l), &ConstantVec(ref r)) => l == r,
117 (&ConstantRepeat(ref lv, ref ls), &ConstantRepeat(ref rv, ref rs)) =>
118 ls == rs && lv == rv,
119 (&ConstantTuple(ref l), &ConstantTuple(ref r)) => l == r,
120 _ => false, //TODO: Are there inter-type equalities?
125 impl PartialOrd for Constant {
126 fn partial_cmp(&self, other: &Constant) -> Option<Ordering> {
127 match (self, other) {
128 (&ConstantStr(ref ls, ref lsty), &ConstantStr(ref rs, ref rsty)) =>
129 if lsty != rsty { None } else { Some(ls.cmp(rs)) },
130 (&ConstantByte(ref l), &ConstantByte(ref r)) => Some(l.cmp(r)),
131 (&ConstantChar(ref l), &ConstantChar(ref r)) => Some(l.cmp(r)),
132 (&ConstantInt(ref lv, lty), &ConstantInt(ref rv, rty)) =>
133 Some(match (is_negative(lty) && *lv != 0,
134 is_negative(rty) && *rv != 0) {
135 (true, true) => rv.cmp(lv),
136 (false, false) => lv.cmp(rv),
137 (true, false) => Less,
138 (false, true) => Greater,
140 (&ConstantFloat(ref ls, lw), &ConstantFloat(ref rs, rw)) =>
142 (FwAny, _) | (_, FwAny) | (Fw32, Fw32) | (Fw64, Fw64) => true,
145 match (ls.parse::<f64>(), rs.parse::<f64>()) {
146 (Ok(ref l), Ok(ref r)) => l.partial_cmp(r),
150 (&ConstantBool(ref l), &ConstantBool(ref r)) => Some(l.cmp(r)),
151 (&ConstantVec(ref l), &ConstantVec(ref r)) => l.partial_cmp(&r),
152 (&ConstantRepeat(ref lv, ref ls), &ConstantRepeat(ref rv, ref rs)) =>
153 match lv.partial_cmp(rv) {
154 Some(Equal) => Some(ls.cmp(rs)),
157 (&ConstantTuple(ref l), &ConstantTuple(ref r)) => l.partial_cmp(r),
158 _ => None, //TODO: Are there any useful inter-type orderings?
163 fn format_byte(fmt: &mut fmt::Formatter, b: u8) -> fmt::Result {
166 } else if 0x20 <= b && b <= 0x7e {
167 write!(fmt, "{}", char::from_u32(b as u32).expect("all u8 are valid char"))
168 } else if b == 0x0a {
170 } else if b == 0x0d {
173 write!(fmt, "\\x{:02x}", b)
177 impl fmt::Display for Constant {
178 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
180 ConstantStr(ref s, _) => write!(fmt, "{:?}", s),
181 ConstantByte(ref b) =>
182 write!(fmt, "b'").and_then(|_| format_byte(fmt, *b))
183 .and_then(|_| write!(fmt, "'")),
184 ConstantBinary(ref bs) => {
185 try!(write!(fmt, "b\""));
187 try!(format_byte(fmt, *b));
191 ConstantChar(ref c) => write!(fmt, "'{}'", c),
192 ConstantInt(ref i, ref ity) => {
193 let (sign, suffix) = match *ity {
194 LitIntType::SignedIntLit(ref sity, ref sign) =>
195 (if let Sign::Minus = *sign { "-" } else { "" },
196 sity.ty_to_string()),
197 LitIntType::UnsignedIntLit(ref uity) =>
198 ("", uity.ty_to_string()),
199 LitIntType::UnsuffixedIntLit(ref sign) =>
200 (if let Sign::Minus = *sign { "-" } else { "" },
203 write!(fmt, "{}{}{}", sign, i, suffix)
205 ConstantFloat(ref s, ref fw) => {
206 let suffix = match *fw {
207 FloatWidth::Fw32 => "f32",
208 FloatWidth::Fw64 => "f64",
209 FloatWidth::FwAny => "",
211 write!(fmt, "{}{}", s, suffix)
213 ConstantBool(ref b) => write!(fmt, "{}", b),
214 ConstantRepeat(ref c, ref n) => write!(fmt, "[{}; {}]", c, n),
215 ConstantVec(ref v) => write!(fmt, "[{}]",
216 v.iter().map(|i| format!("{}", i))
217 .collect::<Vec<_>>().join(", ")),
218 ConstantTuple(ref t) => write!(fmt, "({})",
219 t.iter().map(|i| format!("{}", i))
220 .collect::<Vec<_>>().join(", ")),
226 fn lit_to_constant(lit: &Lit_) -> Constant {
228 LitStr(ref is, style) => ConstantStr(is.to_string(), style),
229 LitByte(b) => ConstantByte(b),
230 LitByteStr(ref s) => ConstantBinary(s.clone()),
231 LitChar(c) => ConstantChar(c),
232 LitInt(value, ty) => ConstantInt(value, ty),
233 LitFloat(ref is, ty) => ConstantFloat(is.to_string(), ty.into()),
234 LitFloatUnsuffixed(ref is) => ConstantFloat(is.to_string(), FwAny),
235 LitBool(b) => ConstantBool(b),
239 fn constant_not(o: Constant) -> Option<Constant> {
241 ConstantBool(b) => ConstantBool(!b),
242 ConstantInt(value, ty) => {
243 let (nvalue, nty) = match ty {
244 SignedIntLit(ity, Plus) => {
245 if value == ::std::u64::MAX { return None; }
246 (value + 1, SignedIntLit(ity, Minus))
248 SignedIntLit(ity, Minus) => {
250 (1, SignedIntLit(ity, Minus))
252 (value - 1, SignedIntLit(ity, Plus))
255 UnsignedIntLit(ity) => {
256 let mask = match ity {
257 UintTy::TyU8 => ::std::u8::MAX as u64,
258 UintTy::TyU16 => ::std::u16::MAX as u64,
259 UintTy::TyU32 => ::std::u32::MAX as u64,
260 UintTy::TyU64 => ::std::u64::MAX,
261 UintTy::TyUs => { return None; } // refuse to guess
263 (!value & mask, UnsignedIntLit(ity))
265 UnsuffixedIntLit(_) => { return None; } // refuse to guess
267 ConstantInt(nvalue, nty)
269 _ => { return None; }
273 fn constant_negate(o: Constant) -> Option<Constant> {
275 ConstantInt(value, ty) =>
276 ConstantInt(value, match ty {
277 SignedIntLit(ity, sign) =>
278 SignedIntLit(ity, neg_sign(sign)),
279 UnsuffixedIntLit(sign) => UnsuffixedIntLit(neg_sign(sign)),
280 _ => { return None; }
282 ConstantFloat(is, ty) =>
283 ConstantFloat(neg_float_str(is), ty),
284 _ => { return None; }
288 fn neg_sign(s: Sign) -> Sign {
290 Sign::Plus => Sign::Minus,
291 Sign::Minus => Sign::Plus,
295 fn neg_float_str(s: String) -> String {
296 if s.starts_with('-') {
303 /// is the given LitIntType negative?
308 /// assert!(is_negative(UnsuffixedIntLit(Minus)));
310 pub fn is_negative(ty: LitIntType) -> bool {
312 SignedIntLit(_, sign) | UnsuffixedIntLit(sign) => sign == Minus,
313 UnsignedIntLit(_) => false,
317 fn unify_int_type(l: LitIntType, r: LitIntType, s: Sign) -> Option<LitIntType> {
319 (SignedIntLit(lty, _), SignedIntLit(rty, _)) => if lty == rty {
320 Some(SignedIntLit(lty, s)) } else { None },
321 (UnsignedIntLit(lty), UnsignedIntLit(rty)) =>
322 if s == Plus && lty == rty {
323 Some(UnsignedIntLit(lty))
325 (UnsuffixedIntLit(_), UnsuffixedIntLit(_)) => Some(UnsuffixedIntLit(s)),
326 (SignedIntLit(lty, _), UnsuffixedIntLit(_)) => Some(SignedIntLit(lty, s)),
327 (UnsignedIntLit(lty), UnsuffixedIntLit(rs)) => if rs == Plus {
328 Some(UnsignedIntLit(lty)) } else { None },
329 (UnsuffixedIntLit(_), SignedIntLit(rty, _)) => Some(SignedIntLit(rty, s)),
330 (UnsuffixedIntLit(ls), UnsignedIntLit(rty)) => if ls == Plus {
331 Some(UnsignedIntLit(rty)) } else { None },
336 fn add_neg_int(pos: u64, pty: LitIntType, neg: u64, nty: LitIntType) ->
339 unify_int_type(nty, pty, Minus).map(|ty| ConstantInt(neg - pos, ty))
341 unify_int_type(nty, pty, Plus).map(|ty| ConstantInt(pos - neg, ty))
345 fn sub_int(l: u64, lty: LitIntType, r: u64, rty: LitIntType, neg: bool) ->
347 unify_int_type(lty, rty, if neg { Minus } else { Plus }).and_then(
348 |ty| l.checked_sub(r).map(|v| ConstantInt(v, ty)))
352 pub fn constant(lcx: &LateContext, e: &Expr) -> Option<(Constant, bool)> {
353 let mut cx = ConstEvalLateContext { lcx: Some(lcx), needed_resolution: false };
354 cx.expr(e).map(|cst| (cst, cx.needed_resolution))
357 pub fn constant_simple(e: &Expr) -> Option<Constant> {
358 let mut cx = ConstEvalLateContext { lcx: None, needed_resolution: false };
362 struct ConstEvalLateContext<'c, 'cc: 'c> {
363 lcx: Option<&'c LateContext<'c, 'cc>>,
364 needed_resolution: bool
367 impl<'c, 'cc> ConstEvalLateContext<'c, 'cc> {
369 /// simple constant folding: Insert an expression, get a constant or none.
370 fn expr(&mut self, e: &Expr) -> Option<Constant> {
372 ExprPath(_, _) => self.fetch_path(e),
373 ExprBlock(ref block) => self.block(block),
374 ExprIf(ref cond, ref then, ref otherwise) =>
375 self.ifthenelse(cond, then, otherwise),
376 ExprLit(ref lit) => Some(lit_to_constant(&lit.node)),
377 ExprVec(ref vec) => self.multi(vec).map(ConstantVec),
378 ExprTup(ref tup) => self.multi(tup).map(ConstantTuple),
379 ExprRepeat(ref value, ref number) =>
380 self.binop_apply(value, number, |v, n|
381 Some(ConstantRepeat(Box::new(v), n.as_u64() as usize))),
382 ExprUnary(op, ref operand) => self.expr(operand).and_then(
384 UnNot => constant_not(o),
385 UnNeg => constant_negate(o),
388 ExprBinary(op, ref left, ref right) =>
389 self.binop(op, left, right),
390 //TODO: add other expressions
395 /// create `Some(Vec![..])` of all constants, unless there is any
396 /// non-constant part
397 fn multi<E: Deref<Target=Expr> + Sized>(&mut self, vec: &[E]) ->
398 Option<Vec<Constant>> {
399 vec.iter().map(|elem| self.expr(elem))
400 .collect::<Option<_>>()
403 /// lookup a possibly constant expression from a ExprPath
404 fn fetch_path(&mut self, e: &Expr) -> Option<Constant> {
405 if let Some(lcx) = self.lcx {
406 let mut maybe_id = None;
407 if let Some(&PathResolution { base_def: DefConst(id), ..}) =
408 lcx.tcx.def_map.borrow().get(&e.id) {
411 // separate if lets to avoid doubleborrowing the defmap
412 if let Some(id) = maybe_id {
413 if let Some(const_expr) = lookup_const_by_id(lcx.tcx, id, None) {
414 let ret = self.expr(const_expr);
416 self.needed_resolution = true;
425 /// A block can only yield a constant if it only has one constant expression
426 fn block(&mut self, block: &Block) -> Option<Constant> {
427 if block.stmts.is_empty() {
428 block.expr.as_ref().and_then(|ref b| self.expr(b))
432 fn ifthenelse(&mut self, cond: &Expr, then: &Block, otherwise: &Option<P<Expr>>)
433 -> Option<Constant> {
434 if let Some(ConstantBool(b)) = self.expr(cond) {
438 otherwise.as_ref().and_then(|expr| self.expr(expr))
443 fn binop(&mut self, op: BinOp, left: &Expr, right: &Expr) -> Option<Constant> {
445 BiAdd => self.binop_apply(left, right, |l, r|
447 (ConstantByte(l8), ConstantByte(r8)) =>
448 l8.checked_add(r8).map(ConstantByte),
449 (ConstantInt(l64, lty), ConstantInt(r64, rty)) => {
450 let (ln, rn) = (is_negative(lty), is_negative(rty));
452 unify_int_type(lty, rty, if ln { Minus } else { Plus })
453 .and_then(|ty| l64.checked_add(r64).map(
454 |v| ConstantInt(v, ty)))
457 add_neg_int(r64, rty, l64, lty)
459 add_neg_int(l64, lty, r64, rty)
463 // TODO: float (would need bignum library?)
466 BiSub => self.binop_apply(left, right, |l, r|
468 (ConstantByte(l8), ConstantByte(r8)) => if r8 > l8 {
469 None } else { Some(ConstantByte(l8 - r8)) },
470 (ConstantInt(l64, lty), ConstantInt(r64, rty)) =>
471 match (is_negative(lty), is_negative(rty)) {
472 (false, false) => sub_int(l64, lty, r64, rty, r64 > l64),
473 (true, true) => sub_int(l64, lty, r64, rty, l64 > r64),
474 (true, false) => unify_int_type(lty, rty, Minus)
475 .and_then(|ty| l64.checked_add(r64).map(
476 |v| ConstantInt(v, ty))),
477 (false, true) => unify_int_type(lty, rty, Plus)
478 .and_then(|ty| l64.checked_add(r64).map(
479 |v| ConstantInt(v, ty))),
483 BiMul => self.divmul(left, right, u64::checked_mul),
484 BiDiv => self.divmul(left, right, u64::checked_div),
486 BiAnd => self.short_circuit(left, right, false),
487 BiOr => self.short_circuit(left, right, true),
488 BiBitXor => self.bitop(left, right, |x, y| x ^ y),
489 BiBitAnd => self.bitop(left, right, |x, y| x & y),
490 BiBitOr => self.bitop(left, right, |x, y| (x | y)),
491 BiShl => self.bitop(left, right, |x, y| x << y),
492 BiShr => self.bitop(left, right, |x, y| x >> y),
493 BiEq => self.binop_apply(left, right,
494 |l, r| Some(ConstantBool(l == r))),
495 BiNe => self.binop_apply(left, right,
496 |l, r| Some(ConstantBool(l != r))),
497 BiLt => self.cmp(left, right, Less, true),
498 BiLe => self.cmp(left, right, Greater, false),
499 BiGe => self.cmp(left, right, Less, false),
500 BiGt => self.cmp(left, right, Greater, true),
505 fn divmul<F>(&mut self, left: &Expr, right: &Expr, f: F)
506 -> Option<Constant> where F: Fn(u64, u64) -> Option<u64> {
507 self.binop_apply(left, right, |l, r|
509 (ConstantInt(l64, lty), ConstantInt(r64, rty)) => {
510 f(l64, r64).and_then(|value|
511 unify_int_type(lty, rty, if is_negative(lty) ==
512 is_negative(rty) { Plus } else { Minus })
513 .map(|ty| ConstantInt(value, ty)))
519 fn bitop<F>(&mut self, left: &Expr, right: &Expr, f: F)
520 -> Option<Constant> where F: Fn(u64, u64) -> u64 {
521 self.binop_apply(left, right, |l, r| match (l, r) {
522 (ConstantBool(l), ConstantBool(r)) =>
523 Some(ConstantBool(f(l as u64, r as u64) != 0)),
524 (ConstantByte(l8), ConstantByte(r8)) =>
525 Some(ConstantByte(f(l8 as u64, r8 as u64) as u8)),
526 (ConstantInt(l, lty), ConstantInt(r, rty)) =>
527 unify_int_type(lty, rty, Plus).map(|ty| ConstantInt(f(l, r), ty)),
532 fn cmp(&mut self, left: &Expr, right: &Expr, ordering: Ordering, b: bool) -> Option<Constant> {
533 self.binop_apply(left, right, |l, r| l.partial_cmp(&r).map(|o|
534 ConstantBool(b == (o == ordering))))
537 fn binop_apply<F>(&mut self, left: &Expr, right: &Expr, op: F) -> Option<Constant>
538 where F: Fn(Constant, Constant) -> Option<Constant> {
539 if let (Some(lc), Some(rc)) = (self.expr(left), self.expr(right)) {
544 fn short_circuit(&mut self, left: &Expr, right: &Expr, b: bool) -> Option<Constant> {
545 self.expr(left).and_then(|left|
546 if let ConstantBool(lbool) = left {
550 self.expr(right).and_then(|right|
551 if let ConstantBool(_) = right {