operator.rs

use rustc::mir;
use rustc::ty::{Ty};
use rustc_const_math::ConstFloat;
use syntax::ast::FloatTy;
use std::cmp::Ordering;

use error::{EvalError, EvalResult};
use eval_context::{EvalContext, ValTy};
use lvalue::Lvalue;
use memory::{MemoryPointer, PointerOffset, SByte};
use value::{
    PrimVal,
    PrimValKind,
    Value,
    bytes_to_f32,
    bytes_to_f64,
    f32_to_bytes,
    f64_to_bytes,
    bytes_to_bool,
};

impl<'a, 'tcx> EvalContext<'a, 'tcx> {
    fn binop_with_overflow(
        &mut self,
        op: mir::BinOp,
        left: &mir::Operand<'tcx>,
        right: &mir::Operand<'tcx>,
    ) -> EvalResult<'tcx, (PrimVal, bool)> {
        let left_ty    = self.operand_ty(left);
        let right_ty   = self.operand_ty(right);
        let left_val   = self.eval_operand_to_primval(left)?;
        let right_val  = self.eval_operand_to_primval(right)?;
        self.binary_op(op, left_val, left_ty, right_val, right_ty)
    }

    /// Applies the binary operation `op` to the two operands and writes a tuple of the result
    /// and a boolean signifying the potential overflow to the destination.
    pub(super) fn intrinsic_with_overflow(
        &mut self,
        op: mir::BinOp,
        left: &mir::Operand<'tcx>,
        right: &mir::Operand<'tcx>,
        dest: Lvalue<'tcx>,
        dest_ty: Ty<'tcx>,
    ) -> EvalResult<'tcx> {
        let (val, overflowed) = self.binop_with_overflow(op, left, right)?;
        let val = Value::ByValPair(val, PrimVal::from_bool(overflowed));
        self.write_value(ValTy { value: val, ty: dest_ty}, dest)
    }

    /// Applies the binary operation `op` to the arguments and writes the result to the
    /// destination. Returns `true` if the operation overflowed.
    pub(super) fn intrinsic_overflowing(
        &mut self,
        op: mir::BinOp,
        left: &mir::Operand<'tcx>,
        right: &mir::Operand<'tcx>,
        dest: Lvalue<'tcx>,
        dest_ty: Ty<'tcx>,
    ) -> EvalResult<'tcx, bool> {
        let (val, overflowed) = self.binop_with_overflow(op, left, right)?;
        self.write_primval(dest, val, dest_ty)?;
        Ok(overflowed)
    }
}

macro_rules! overflow {
    ($op:ident, $l:expr, $r:expr) => ({
        let (val, overflowed) = $l.$op($r);
        let primval = PrimVal::Bytes(val as u128);
        Ok((primval, overflowed))
    })
}

macro_rules! int_arithmetic {
    ($kind:expr, $int_op:ident, $l:expr, $r:expr) => ({
        let l = $l;
        let r = $r;
        match $kind {
            I8  => overflow!($int_op, l as i8,  r as i8),
            I16 => overflow!($int_op, l as i16, r as i16),
            I32 => overflow!($int_op, l as i32, r as i32),
            I64 => overflow!($int_op, l as i64, r as i64),
            I128 => overflow!($int_op, l as i128, r as i128),
            U8  => overflow!($int_op, l as u8,  r as u8),
            U16 => overflow!($int_op, l as u16, r as u16),
            U32 => overflow!($int_op, l as u32, r as u32),
            U64 => overflow!($int_op, l as u64, r as u64),
            U128 => overflow!($int_op, l as u128, r as u128),
            _ => bug!("int_arithmetic should only be called on int primvals"),
        }
    })
}

macro_rules! int_shift {
    ($kind:expr, $int_op:ident, $l:expr, $r:expr) => ({
        let l = $l;
        let r = $r;
        match $kind {
            I8  => overflow!($int_op, l as i8,  r),
            I16 => overflow!($int_op, l as i16, r),
            I32 => overflow!($int_op, l as i32, r),
            I64 => overflow!($int_op, l as i64, r),
            I128 => overflow!($int_op, l as i128, r),
            U8  => overflow!($int_op, l as u8,  r),
            U16 => overflow!($int_op, l as u16, r),
            U32 => overflow!($int_op, l as u32, r),
            U64 => overflow!($int_op, l as u64, r),
            U128 => overflow!($int_op, l as u128, r),
            _ => bug!("int_shift should only be called on int primvals"),
        }
    })
}

impl<'a, 'tcx> EvalContext<'a, 'tcx> {

    /// Returns the result of the specified operation and whether it overflowed.
    pub fn binary_op(
        &mut self,
        bin_op: mir::BinOp,
        left: PrimVal,
        left_ty: Ty<'tcx>,
        right: PrimVal,
        right_ty: Ty<'tcx>,
    ) -> EvalResult<'tcx, (PrimVal, bool)> {
        use rustc::mir::BinOp::*;
        use value::PrimValKind::*;

        let left_kind  = self.ty_to_primval_kind(left_ty)?;
        let right_kind = self.ty_to_primval_kind(right_ty)?;

        // I: Handle operations that support pointers
        let usize = PrimValKind::from_uint_size(self.memory.pointer_size());
        let isize = PrimValKind::from_int_size(self.memory.pointer_size());

        if !left.is_concrete() || !right.is_concrete() {
            return self.abstract_binary_op(bin_op,
                                           left, left_kind,
                                           right, right_kind);
        }

        match (left, right) {
            (PrimVal::Ptr(lptr), PrimVal::Ptr(rptr)) => {
                if !lptr.has_concrete_offset() || !rptr.has_concrete_offset() {
                    return self.abstract_ptr_ops(bin_op, lptr, left_kind, rptr, right_kind);
                }
            }
            _ => {

            }
        }

        if !left_kind.is_float() && !right_kind.is_float() {
            match bin_op {
                Offset if left_kind == Ptr && right_kind == usize => {
                    let pointee_ty = left_ty.builtin_deref(true).expect("Offset called on non-ptr type").ty;
                    let ptr = self.pointer_offset(left, pointee_ty, right.to_bytes()? as i64)?;
                    return Ok((ptr, false));
                },
                // These work on anything
                Eq if left_kind == right_kind => {
                    let result = match (left, right) {
                        (PrimVal::Bytes(left), PrimVal::Bytes(right)) => left == right,
                        (PrimVal::Ptr(left), PrimVal::Ptr(right)) => left == right,
                        (PrimVal::Undef, _) | (_, PrimVal::Undef) => return Err(EvalError::ReadUndefBytes),
                        _ => false,
                    };
                    return Ok((PrimVal::from_bool(result), false));
                }
                Ne if left_kind == right_kind => {
                    let result = match (left, right) {
                        (PrimVal::Bytes(left), PrimVal::Bytes(right)) => left != right,
                        (PrimVal::Ptr(left), PrimVal::Ptr(right)) => left != right,
                        (PrimVal::Undef, _) | (_, PrimVal::Undef) => return Err(EvalError::ReadUndefBytes),
                        _ => true,
                    };
                    return Ok((PrimVal::from_bool(result), false));
                }
                // These need both pointers to be in the same allocation
                Lt | Le | Gt | Ge | Sub
                if left_kind == right_kind
                && (left_kind == Ptr || left_kind == usize || left_kind == isize)
                && left.is_ptr() && right.is_ptr() => {
                    let left = left.to_ptr()?;
                    let right = right.to_ptr()?;
                    let (left_offset, right_offset) = match (left.offset, right.offset) {
                        (PointerOffset::Concrete(l), PointerOffset::Concrete(r)) => (l, r),
                        _ => unimplemented!(),
                    };


                    if left.alloc_id == right.alloc_id {
                        let res = match bin_op {
                            Lt => left_offset < right_offset,
                            Le => left_offset <= right_offset,
                            Gt => left_offset > right_offset,
                            Ge => left_offset >= right_offset,
                            Sub => {
                                return int_arithmetic!(left_kind, overflowing_sub, left_offset, right_offset);
                            }
                            _ => bug!("We already established it has to be one of these operators."),
                        };
                        return Ok((PrimVal::from_bool(res), false));
                    } else {
                        // Both are pointers, but from different allocations.
                        return Err(EvalError::InvalidPointerMath);
                    }
                }
                // These work if one operand is a pointer, the other an integer
                Add | BitAnd | Sub
                if left_kind == right_kind && (left_kind == usize || left_kind == isize)
                && left.is_ptr() && right.is_bytes() => {
                    // Cast to i128 is fine as we checked the kind to be ptr-sized
                    return self.ptr_int_arithmetic(bin_op, left.to_ptr()?, right.to_bytes()? as i128, left_kind == isize);
                }
                Add | BitAnd
                if left_kind == right_kind && (left_kind == usize || left_kind == isize)
                && left.is_bytes() && right.is_ptr() => {
                    // This is a commutative operation, just swap the operands
                    return self.ptr_int_arithmetic(bin_op, right.to_ptr()?, left.to_bytes()? as i128, left_kind == isize);
                }
                _ => {}
            }
        }

        // II: From now on, everything must be bytes, no pointers
        let l = left.to_bytes()?;
        let r = right.to_bytes()?;

        // These ops can have an RHS with a different numeric type.
        if bin_op == Shl || bin_op == Shr {
            return match bin_op {
                Shl => int_shift!(left_kind, overflowing_shl, l, r as u32),
                Shr => int_shift!(left_kind, overflowing_shr, l, r as u32),
                _ => bug!("it has already been checked that this is a shift op"),
            };
        }

        if left_kind != right_kind {
            let msg = format!("unimplemented binary op: {:?}, {:?}, {:?}", left, right, bin_op);
            return Err(EvalError::Unimplemented(msg));
        }

        let float_op = |op, l, r, ty| {
            let l = ConstFloat {
                bits: l,
                ty,
            };
            let r = ConstFloat {
                bits: r,
                ty,
            };
            match op {
                Eq => PrimVal::from_bool(l.try_cmp(r).unwrap() == Ordering::Equal),
                Ne => PrimVal::from_bool(l.try_cmp(r).unwrap() != Ordering::Equal),
                Lt => PrimVal::from_bool(l.try_cmp(r).unwrap() == Ordering::Less),
                Le => PrimVal::from_bool(l.try_cmp(r).unwrap() != Ordering::Greater),
                Gt => PrimVal::from_bool(l.try_cmp(r).unwrap() == Ordering::Greater),
                Ge => PrimVal::from_bool(l.try_cmp(r).unwrap() != Ordering::Less),
                Add => PrimVal::Bytes((l + r).unwrap().bits),
                Sub => PrimVal::Bytes((l - r).unwrap().bits),
                Mul => PrimVal::Bytes((l * r).unwrap().bits),
                Div => PrimVal::Bytes((l / r).unwrap().bits),
                Rem => PrimVal::Bytes((l % r).unwrap().bits),
                _ => bug!("invalid float op: `{:?}`", op),
            }
        };

        let val = match (bin_op, left_kind) {
            (_, F32) => float_op(bin_op, l, r, FloatTy::F32),
            (_, F64) => float_op(bin_op, l, r, FloatTy::F64),

            (Eq, _) => PrimVal::from_bool(l == r),
            (Ne, _) => PrimVal::from_bool(l != r),
            (Lt, k) if k.is_signed_int() => PrimVal::from_bool((l as i128) < (r as i128)),
            (Lt, _) => PrimVal::from_bool(l <  r),
            (Le, k) if k.is_signed_int() => PrimVal::from_bool((l as i128) <= (r as i128)),
            (Le, _) => PrimVal::from_bool(l <= r),
            (Gt, k) if k.is_signed_int() => PrimVal::from_bool((l as i128) > (r as i128)),
            (Gt, _) => PrimVal::from_bool(l >  r),
            (Ge, k) if k.is_signed_int() => PrimVal::from_bool((l as i128) >= (r as i128)),
            (Ge, _) => PrimVal::from_bool(l >= r),

            (BitOr,  _) => PrimVal::Bytes(l | r),
            (BitAnd, _) => PrimVal::Bytes(l & r),
            (BitXor, _) => PrimVal::Bytes(l ^ r),

            (Add, k) if k.is_int() => return int_arithmetic!(k, overflowing_add, l, r),
            (Sub, k) if k.is_int() => return int_arithmetic!(k, overflowing_sub, l, r),
            (Mul, k) if k.is_int() => return int_arithmetic!(k, overflowing_mul, l, r),
            (Div, k) if k.is_int() => return int_arithmetic!(k, overflowing_div, l, r),
            (Rem, k) if k.is_int() => return int_arithmetic!(k, overflowing_rem, l, r),

            _ => {
                let msg = format!("unimplemented binary op {:?}: {:?} ({:?}), {:?} ({:?})", bin_op, left, left_kind, right, right_kind);
                return Err(EvalError::Unimplemented(msg));
            }
        };

        Ok((val, false))
    }

    fn ptr_int_arithmetic(
        &self,
        bin_op: mir::BinOp,
        left: MemoryPointer,
        right: i128,
        signed: bool,
    ) -> EvalResult<'tcx, (PrimVal, bool)> {
        use rustc::mir::BinOp::*;

        fn map_to_primval((res, over) : (MemoryPointer, bool)) -> (PrimVal, bool) {
            (PrimVal::Ptr(res), over)
        }

        let left_offset = match left.offset {
            PointerOffset::Concrete(n) => n,
            _ => unimplemented!(),
        };

        Ok(match bin_op {
            Sub =>
                // The only way this can overflow is by underflowing, so signdeness of the right operands does not matter
                map_to_primval(left.overflowing_signed_offset(-right, self.memory.layout)),
            Add if signed =>
                map_to_primval(left.overflowing_signed_offset(right, self.memory.layout)),
            Add if !signed =>
                map_to_primval(left.overflowing_offset(right as u64, self.memory.layout)),

            BitAnd if !signed => {
                let base_mask : u64 = !(self.memory.get(left.alloc_id)?.align - 1);
                let right = right as u64;
                if right & base_mask == base_mask {
                    // Case 1: The base address bits are all preserved, i.e., right is all-1 there
                    (PrimVal::Ptr(MemoryPointer::new(left.alloc_id, left_offset & right)), false)
                } else if right & base_mask == 0 {
                    // Case 2: The base address bits are all taken away, i.e., right is all-0 there
                    (PrimVal::from_u128((left_offset & right) as u128), false)
                } else {
                    return Err(EvalError::ReadPointerAsBytes);
                }
            }

            _ => {
                let msg = format!("unimplemented binary op on pointer {:?}: {:?}, {:?} ({})", bin_op, left, right, if signed { "signed" } else { "unsigned" });
                return Err(EvalError::Unimplemented(msg));
            }
        })
    }

    pub fn abstract_binary_op(
        &mut self,
        bin_op: mir::BinOp,
        left: PrimVal,
        left_kind: PrimValKind,
        right: PrimVal,
        mut right_kind: PrimValKind,
    ) -> EvalResult<'tcx, (PrimVal, bool)> {

        // These ops can have an RHS with a different numeric type.
        if bin_op == mir::BinOp::Shl || bin_op == mir::BinOp::Shr {
            match (left, right) {
                (PrimVal::Abstract(abytes), PrimVal::Bytes(rn)) if rn % 8 == 0 => {
                    let num_bytes = (rn / 8) as usize;
                    match bin_op {
                        mir::BinOp::Shl => {
                            let mut buffer = [SByte::Concrete(0); 8];
                            for idx in num_bytes .. 8 {
                                buffer[idx] = abytes[idx - num_bytes];
                            }
                            return Ok((PrimVal::Abstract(buffer), false));
                        }
                        mir::BinOp::Shr => {
                            if !left_kind.is_signed_int() {
                                let mut buffer = [SByte::Concrete(0); 8];
                                for idx in num_bytes .. 8 {
                                    buffer[idx - num_bytes] = abytes[idx];
                                }
                                return Ok((PrimVal::Abstract(buffer), false));
                            }
                        }
                        _ => unimplemented!(),
                    }
                }
                _ => (),
            }

            if right_kind.num_bytes() == left_kind.num_bytes() {
                right_kind = left_kind;
            } else if right_kind.num_bytes() < left_kind.num_bytes() {
                right_kind = left_kind;
            } else {
                if let PrimVal::Bytes(n) = right {
                    if n < 256 {
                        // HACK
                        right_kind = left_kind;
                    } else {
                        unimplemented!()
                    }
                } else {
                    unimplemented!()
                }
            }
        }

        if left_kind != right_kind {
            let msg = format!("unimplemented binary op: {:?}, {:?}, {:?}", left, right, bin_op);
            return Err(EvalError::Unimplemented(msg));
        }
        Ok((self.memory.constraints.add_binop_constraint(bin_op, left, right, left_kind), false))
    }

    fn abstract_ptr_ops(
        &mut self,
        bin_op: mir::BinOp,
        left: MemoryPointer,
        _left_kind: PrimValKind,
        right: MemoryPointer,
        _right_kind: PrimValKind,
    ) -> EvalResult<'tcx, (PrimVal, bool)> {
        use rustc::mir::BinOp::*;
        use value::PrimValKind::*;
        if left.alloc_id != right.alloc_id {
            if let Eq = bin_op {
                unimplemented!()
            } else {
                unimplemented!()
            }
        } else {
            let result = self.memory.constraints.add_binop_constraint(
                bin_op, left.offset.as_primval(), right.offset.as_primval(), U64);
            Ok((result, false))
        }
    }

    pub fn unary_op(
        &mut self,
        un_op: mir::UnOp,
        val: PrimVal,
        val_kind: PrimValKind,
    ) -> EvalResult<'tcx, PrimVal> {
        use rustc::mir::UnOp::*;
        use value::PrimValKind::*;

        if !val.is_concrete() {
            return
                Ok(self.memory.constraints.add_unop_constraint(
                    un_op, val, val_kind))
        }

        let bytes = val.to_bytes()?;

        let result_bytes = match (un_op, val_kind) {
            (Not, Bool) => !bytes_to_bool(bytes) as u128,

            (Not, U8)  => !(bytes as u8) as u128,
            (Not, U16) => !(bytes as u16) as u128,
            (Not, U32) => !(bytes as u32) as u128,
            (Not, U64) => !(bytes as u64) as u128,
            (Not, U128) => !bytes,

            (Not, I8)  => !(bytes as i8) as u128,
            (Not, I16) => !(bytes as i16) as u128,
            (Not, I32) => !(bytes as i32) as u128,
            (Not, I64) => !(bytes as i64) as u128,
            (Not, I128) => !(bytes as i128) as u128,

            (Neg, I8)  => -(bytes as i8) as u128,
            (Neg, I16) => -(bytes as i16) as u128,
            (Neg, I32) => -(bytes as i32) as u128,
            (Neg, I64) => -(bytes as i64) as u128,
            (Neg, I128) => -(bytes as i128) as u128,

            (Neg, F32) => f32_to_bytes(-bytes_to_f32(bytes)),
            (Neg, F64) => f64_to_bytes(-bytes_to_f64(bytes)),

            _ => {
                let msg = format!("unimplemented unary op: {:?}, {:?}", un_op, val);
                return Err(EvalError::Unimplemented(msg));
            }
        };

        Ok(PrimVal::Bytes(result_bytes))
    }
}