// Panopticon - A libre program analysis library for machine code
// Copyright (C) 2014-2018  The Panopticon Developers
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

use std::ops::Range;
use std::fmt;
use smallvec::SmallVec;
use quickcheck::{Arbitrary, Gen};
use ron_uuid::UUID;

use {
    StrRef, Str,
    Variable, Value, Constant, Segment,
    Result, Constraint
};

/// Address range with sub-byte pecision. Used to order instructions that don't occupy any space in
/// the binary (e.g. Phi).
#[derive(Clone,PartialEq,Eq)]
pub struct Area {
    /// First byte (inclusive).
    pub start: u64,
    /// Last byte (exclusive).
    pub end: u64,
    /// Logic order inside the first byte (inclusive).
    pub offset_start: usize,
    /// Logic order inside the last byte (exclusive).
    pub offset_end: usize,
}

impl From<Range<u64>> for Area {
    fn from(r: Range<u64>) -> Self {
        Area{
            start: r.start,
            end: r.end,
            offset_start: 0,
            offset_end: if r.end == r.start { 1 } else { 0 },
        }
    }
}

impl fmt::Debug for Area {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.offset_start != 0 {
            write!(f, "{}.{}..", self.start, self.offset_start)?;
        } else {
            write!(f, "{}..", self.start)?;
        }
        if self.offset_end != 0 {
            write!(f, "{}.{}", self.end, self.offset_end)
        } else {
            write!(f, "{}", self.end)
        }
    }
}

/// Byte order.
#[derive(Debug,Clone,Copy,PartialEq,Eq)]
pub enum Endianess {
    /// Least significant byte first.
    Little,
    /// Most significant byte first.
    Big,
}

impl Arbitrary for Endianess {
    fn arbitrary<G: Gen>(g: &mut G) -> Self {
        match g.gen_range(0, 1) {
            0 => Endianess::Little,
            1 => Endianess::Big,
            _ => unreachable!(),
        }
    }
}

/// A RREIL operation.
#[derive(Clone,PartialEq,Eq,Debug)]
pub enum Operation {
    /// Integer addition
    Add(Value, Value),
    /// Integer subtraction
    Subtract(Value, Value),
    /// Unsigned integer multiplication
    Multiply(Value, Value),
    /// Unsigned integer division
    DivideUnsigned(Value, Value),
    /// Signed integer division
    DivideSigned(Value, Value),
    /// Bitwise left shift
    ShiftLeft(Value, Value),
    /// Bitwise logical right shift
    ShiftRightUnsigned(Value, Value),
    /// Bitwise arithmetic right shift
    ShiftRightSigned(Value, Value),
    /// Integer modulo
    Modulo(Value, Value),
    /// Bitwise logical and
    And(Value, Value),
    /// Bitwise logical or
    InclusiveOr(Value, Value),
    /// Bitwise logical xor
    ExclusiveOr(Value, Value),

    /// Compare both operands for equality and returns `1` or `0`
    Equal(Value, Value),
    /// Returns `1` if the first operand is less than or equal to the second and `0` otherwise.
    /// Comparison assumes unsigned values.
    LessOrEqualUnsigned(Value, Value),
    /// Returns `1` if the first operand is less than or equal to the second and `0` otherwise.
    /// Comparison assumes signed values.
    LessOrEqualSigned(Value, Value),
    /// Returns `1` if the first operand is less than the second and `0` otherwise.
    /// Comparison assumes unsigned values.
    LessUnsigned(Value, Value),
    /// Returns `1` if the first operand is less than the second and `0` otherwise.
    /// Comparison assumes signed values.
    LessSigned(Value, Value),

    /// Zero extends the operand.
    ZeroExtend(usize, Value),
    /// Sign extends the operand.
    SignExtend(usize, Value),
    /// Copies the operand without modification.
    Move(Value),
    /// Initializes a global variable.
    Initialize(StrRef,usize),
    /// Copies only the range [self.0, self.0 + self.1] of bits from the operand.
    Select(usize, usize, Value),
    /// Asserts that the second operand is constraint by the first.
    Assume(Constraint,Value),
    /// Reads a memory cell
    Load(Segment,Endianess,usize,Value),

    /// SSA Phi function
    Phi(Value,Value,Value),
}

impl Operation {
    /// Returns references values that are read by the operation.
    pub fn reads<'x>(&'x self) -> SmallVec<[&'x Value; 3]> {
        use Operation::*;

        let mut ret = SmallVec::new();

        match self {
            &Add(ref a, ref b) => { ret.push(a); ret.push(b); }
            &Subtract(ref a, ref b) => { ret.push(a); ret.push(b); }
            &Multiply(ref a, ref b) => { ret.push(a); ret.push(b); }
            &DivideUnsigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &DivideSigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &ShiftLeft(ref a, ref b) => { ret.push(a); ret.push(b); }
            &ShiftRightUnsigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &ShiftRightSigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &Modulo(ref a, ref b) => { ret.push(a); ret.push(b); }
            &And(ref a, ref b) => { ret.push(a); ret.push(b); }
            &InclusiveOr(ref a, ref b) => { ret.push(a); ret.push(b); }
            &ExclusiveOr(ref a, ref b) => { ret.push(a); ret.push(b); }

            &Equal(ref a, ref b) => { ret.push(a); ret.push(b); }
            &LessOrEqualUnsigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &LessOrEqualSigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &LessUnsigned(ref a, ref b) => { ret.push(a); ret.push(b); }
            &LessSigned(ref a, ref b) => { ret.push(a); ret.push(b); }

            &ZeroExtend(_, ref a) => { ret.push(a); }
            &SignExtend(_, ref a) => { ret.push(a); }
            &Move(ref a) => { ret.push(a); }
            &Initialize(_,_) => {}
            &Select(_, _, ref a) => { ret.push(a); }
            &Assume(_, ref a) => { ret.push(a); }

            &Load(_, _, _, ref a) => { ret.push(a); }

            &Phi(ref a, ref b, ref c) => {
                ret.push(a); ret.push(b); ret.push(c);
            }
        }

        ret
    }

    /// Returns mutables references values that are read by the operation.
    pub fn reads_mut<'x>(&'x mut self) -> SmallVec<[&'x mut Value; 3]> {
        use Operation::*;

        let mut ret = SmallVec::new();

        match self {
            &mut Add(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut Subtract(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut Multiply(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut DivideUnsigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut DivideSigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut ShiftLeft(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut ShiftRightUnsigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut ShiftRightSigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut Modulo(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut And(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut InclusiveOr(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut ExclusiveOr(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }

            &mut Equal(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut LessOrEqualUnsigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut LessOrEqualSigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut LessUnsigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }
            &mut LessSigned(ref mut a, ref mut b) => { ret.push(a); ret.push(b); }

            &mut ZeroExtend(_, ref mut a) => { ret.push(a); }
            &mut SignExtend(_, ref mut a) => { ret.push(a); }
            &mut Move(ref mut a) => { ret.push(a); }
            &mut Initialize(_,_) => {}
            &mut Select(_, _, ref mut a) => { ret.push(a); }
            &mut Assume(_, ref mut a) => { ret.push(a); }

            &mut Load(_, _, _, ref mut a) => { ret.push(a); }

            &mut Phi(ref mut a, ref mut b, ref mut c) => {
                ret.push(a); ret.push(b); ret.push(c);
            }
        }

        ret
    }

    /// Executes a RREIL operation returning the result.
    pub fn execute(&self) -> Result<Value> {
        use std::num::Wrapping;
        use Operation::*;
        use std::u64;

        match self.clone() {
            Add(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to add value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();
                Value::val(((a + b) & mask).0, bits)
            }
            Add(Value::Constant(Constant { value: 0, .. }), b) => Ok(b),
            Add(a, Value::Constant(Constant { value: 0, .. })) => Ok(a),
            Add(_, _) => Ok(Value::Undefined),

            Subtract(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to subtract value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();
                Value::val(((a - b) & mask).0, bits)
            }
            Subtract(a, Value::Constant(Constant { value: 0, .. })) => Ok(a),
            Subtract(_, _) => Ok(Value::Undefined),

            Multiply(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to multiply value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();
                Value::val(((a * b) & mask).0, bits)
            }
            Multiply(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            Multiply(_, Value::Constant(Constant { value: 0, bits: s })) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            Multiply(Value::Constant(Constant { value: 1, .. }), b) => Ok(b),
            Multiply(a, Value::Constant(Constant { value: 1, .. })) => Ok(a),
            Multiply(_, _) => Ok(Value::Undefined),

            DivideUnsigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to divide value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                if b == Wrapping(0) {
                    Ok(Value::Undefined)
                } else {
                    Value::val(((a / b) & mask).0, bits)
                }
            }
            DivideUnsigned(a, Value::Constant(Constant { value: 1, .. })) => Ok(a),
            DivideUnsigned(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            DivideUnsigned(_, _) => Ok(Value::Undefined),

            DivideSigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to divide value of {} and {} bits",a.bits,b.bits).into());
                }

                let bits = a.bits;
                let mut a = Wrapping(a.value as i64);
                let mut b = Wrapping(b.value as i64);

                if bits < 64 {
                    let sign_bit = Wrapping(1 << (bits - 1));
                    let m = Wrapping(1 << bits);

                    if sign_bit & a != Wrapping(0) {
                        a = a - m;
                    }
                    if sign_bit & b != Wrapping(0) {
                        b = b - m;
                    }
                    a = a % m;
                    b = b % m;
                }

                if b == Wrapping(0) {
                    Ok(Value::Undefined)
                } else {
                    if bits < 64 {
                        let m = 1 << bits;
                        Value::val((a / b).0 as u64 % m, bits)
                    } else {
                        Value::val((a / b).0 as u64, bits)
                    }
                }
            }
            DivideSigned(a, Value::Constant(Constant { value: 1, .. })) => Ok(a),
            DivideSigned(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            DivideSigned(_, _) => Ok(Value::Undefined),

            Modulo(_, Value::Constant(Constant { value: 0, .. })) => Ok(Value::Undefined),
            Modulo(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to mod value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                if b == Wrapping(0) {
                    Ok(Value::Undefined)
                } else {
                    Value::val(((a % b) & mask).0, bits)
                }
            }
            Modulo(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            Modulo(_, Value::Constant(Constant { value: 1, bits: s })) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            Modulo(_, _) => Ok(Value::Undefined),

            ShiftLeft(Value::Constant(a), Value::Constant(b)) => {
                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                Value::val(((a << (b.0 as usize)) & mask).0, bits)
            }
            ShiftLeft(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            ShiftLeft(a, Value::Constant(Constant { value: 0, .. })) => Ok(a),
            ShiftLeft(_, _) => Ok(Value::Undefined),

            ShiftRightUnsigned(Value::Constant(a), Value::Constant(b)) => {
                use std::cmp;

                if a.bits != b.bits {
                    return Err(format!("tried to mod value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                if b.0 >= bits as u64 {
                    Value::val(0, bits)
                } else {
                    Value::val(((a >> cmp::min(cmp::min(64, bits), b.0 as usize)) & mask).0,bits)
                }
            }
            ShiftRightUnsigned(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            ShiftRightUnsigned(a, Value::Constant(Constant { value: 0, .. })) => Ok(a),
            ShiftRightUnsigned(_, _) => Ok(Value::Undefined),

            ShiftRightSigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to mod value of {} and {} bits",a.bits,b.bits).into());
                }

                let mask = a.mask();
                let bits = a.bits;
                let mut a = Wrapping(a.value as i64);
                let b = Wrapping(b.value as i64);

                if bits < 64 {
                    let sign_bit = Wrapping(1 << (bits - 1));
                    if sign_bit & a != Wrapping(0) {
                        a = a | Wrapping(-1i64 << bits);
                    }
                }

                if b.0 as u64 >= bits as u64 {
                    let ret = if a < Wrapping(0) {
                        if bits < 64 {
                            Value::Constant(Constant { value: (1 << bits) - 1, bits: bits })
                        } else {
                            Value::Constant(Constant { value: u64::MAX, bits: bits })
                        }
                    } else {
                        Value::Constant(Constant { value: 0, bits: bits })
                    };
                    Ok(ret)
                } else {
                    if bits < 64 {
                        Value::val((a >> (b.0 as usize)).0 as u64 & mask.0, bits)
                    } else {
                        Value::val((a >> (b.0 as usize)).0 as u64, bits)
                    }
                }
            }
            ShiftRightSigned(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            ShiftRightSigned(a, Value::Constant(Constant { value: 0, .. })) => Ok(a),
            ShiftRightSigned(_, _) => Ok(Value::Undefined),

            And(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to and value of {} and {} bits",a.bits,b.bits).into());
                }

                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                Value::val((a & b).0 as u64, bits)
            }
            And(_, Value::Constant(Constant { value: 0, bits: s })) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            And(Value::Constant(Constant { value: 0, bits: s }), _) => Ok(Value::Constant(Constant { value: 0, bits: s })),
            And(_, _) => Ok(Value::Undefined),

            InclusiveOr(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to or value of {} and {} bits",a.bits,b.bits).into());
                }

                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                Value::val((a | b).0 as u64, bits)
            }
            InclusiveOr(a, Value::Constant(Constant { value: 0, .. })) => Ok(a),
            InclusiveOr(Value::Constant(Constant { value: 0, .. }), b) => Ok(b),
            InclusiveOr(_, _) => Ok(Value::Undefined),

            ExclusiveOr(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to xor value of {} and {} bits",a.bits,b.bits).into());
                }

                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                Value::val((a ^ b).0 as u64, bits)
            }
            ExclusiveOr(_, _) => Ok(Value::Undefined),

            Equal(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to compare value of {} and {} bits",a.bits,b.bits).into());
                }

                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                if a == b {
                    Value::val(1, 1)
                } else {
                    Value::val(0, 1)
                }
            }
            Equal(_, _) => Ok(Value::Undefined),

            LessOrEqualUnsigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to compare value of {} and {} bits",a.bits,b.bits).into());
                }

                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                if a <= b {
                    Value::val(1, 1)
                } else {
                    Value::val(0, 1)
                }
            }
            LessOrEqualUnsigned(Value::Constant(Constant { value: 0, .. }), _) => Ok(Value::Constant(Constant { value: 1, bits: 1 })),
            LessOrEqualUnsigned(_, _) => Ok(Value::Undefined),

            LessOrEqualSigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to compare value of {} and {} bits",a.bits,b.bits).into());
                }

                let bits = a.bits;
                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();
                let mask = Wrapping(if bits < 64 {
                    (1u64 << (bits - 1)) - 1
                } else {
                    u64::MAX
                });
                let sign_mask = Wrapping(if bits < 64 { 1u64 << (bits - 1) } else { 0 });
                if (a & sign_mask) ^ (b & sign_mask) != Wrapping(0) {
                    Value::val(if a & sign_mask != Wrapping(0) { 1 } else { 0 },1)
                } else {
                    Value::val(if (a & mask) <= (b & mask) { 1 } else { 0 },1)
                }
            }
            LessOrEqualSigned(_, _) => Ok(Value::Undefined),

            LessUnsigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to compare value of {} and {} bits",a.bits,b.bits).into());
                }

                let a: Wrapping<_> = a.into();
                let b: Wrapping<_> = b.into();

                if a < b {
                    Value::val(1, 1)
                } else {
                    Value::val(0, 1)
                }
            }
            LessUnsigned(_, _) => Ok(Value::Undefined),

            LessSigned(Value::Constant(a), Value::Constant(b)) => {
                if a.bits != b.bits {
                    return Err(format!("tried to compare value of {} and {} bits",a.bits,b.bits).into());
                }

                let bits = a.bits;
                let mut a: Wrapping<_> = a.into();
                let mut b: Wrapping<_> = b.into();

                if bits < 64 {
                    let sign_bit = Wrapping(1 << (bits - 1));
                    let m = Wrapping(1 << bits);

                    if sign_bit & a != Wrapping(0) {
                        a = a - m;
                    }
                    if sign_bit & b != Wrapping(0) {
                        b = b - m;
                    }
                    a = a % m;
                    b = b % m;
                }

                if a < b {
                    Value::val(1,1)
                } else {
                    Value::val(0,1)
                }
            }
            LessSigned(_, _) => Ok(Value::Undefined),

            ZeroExtend(s1, Value::Constant(Constant { value: v, bits: s0 })) => {
                let mask1 = if s1 < 64 { (1u64 << s1) - 1 } else { u64::MAX };
                let mask0 = if s0 < 64 { (1u64 << s0) - 1 } else { u64::MAX };
                Value::val((v & mask0) & mask1,s1)
            }
            ZeroExtend(s, Value::Variable(Variable { name, .. })) => {
                Value::var(name,s)
            }
            ZeroExtend(_, Value::Undefined) => Ok(Value::Undefined),

            SignExtend(t, Value::Constant(Constant { value: v, bits: s })) => {
                let mask0 = if s < 64 { (1u64 << s) - 1 } else { u64::MAX };
                let mask1 = if t < 64 { (1u64 << t) - 1 } else { u64::MAX };
                let sign = if s < 64 { 1u64 << (s - 1) } else { 0 };

                if v & sign == 0 {
                    Value::val((v & mask0) & mask1, t)
                } else {
                    let mask = mask1 & !mask0;
                    Value::val((v & mask0) | mask, t)
                }
            }
            SignExtend(s, Value::Variable(Variable { name, .. })) => {
                Value::var(name,s)
            }
            SignExtend(_, Value::Undefined) => Ok(Value::Undefined),

            Move(a) => Ok(a),

            Initialize(_, _) => Ok(Value::Undefined),

            Select(off, sz, Value::Constant(a)) => {
                let Constant{ value: a_value, bits: a_bits } = a;

                if off + sz < 64 && a_bits <= off + sz {
                    let val = a_value >> off;
                    let mask = (1 << sz) - 1;

                    Value::val(val & mask, sz)
                } else {
                    Ok(Value::Undefined)
                }
            }
            Select(_, _, _) => Ok(Value::Undefined),
            Assume(_, _) => Ok(Value::Undefined),

            Load(_, _, _, _) => Ok(Value::Undefined),

            Phi(ref a@Value::Variable(_),Value::Undefined,Value::Undefined) => Ok(a.clone()),
            Phi(ref a@Value::Variable(_),ref b@Value::Variable(_),Value::Undefined) if *a == *b => Ok(a.clone()),
            Phi(ref a@Value::Variable(_),ref b@Value::Variable(_),ref c@Value::Variable(_)) if *a == *b && *b == *c => Ok(a.clone()),
            Phi(_,_,_) => Ok(Value::Undefined),
        }
    }
}

impl Arbitrary for Operation {
    fn arbitrary<G: Gen>(g: &mut G) -> Self {
        loop {
            let op = match g.gen_range(0, 26) {
                0 => Operation::Add(Value::arbitrary(g), Value::arbitrary(g)),
                1 => Operation::Subtract(Value::arbitrary(g), Value::arbitrary(g)),
                2 => Operation::Multiply(Value::arbitrary(g), Value::arbitrary(g)),
                3 => Operation::DivideUnsigned(Value::arbitrary(g), Value::arbitrary(g)),
                4 => Operation::DivideSigned(Value::arbitrary(g), Value::arbitrary(g)),
                5 => Operation::ShiftLeft(Value::arbitrary(g), Value::arbitrary(g)),
                6 => Operation::ShiftRightUnsigned(Value::arbitrary(g), Value::arbitrary(g)),
                7 => Operation::ShiftRightSigned(Value::arbitrary(g), Value::arbitrary(g)),
                8 => Operation::Modulo(Value::arbitrary(g), Value::arbitrary(g)),
                9 => Operation::And(Value::arbitrary(g), Value::arbitrary(g)),
                10 => Operation::InclusiveOr(Value::arbitrary(g), Value::arbitrary(g)),
                11 => Operation::ExclusiveOr(Value::arbitrary(g), Value::arbitrary(g)),

                12 => Operation::Equal(Value::arbitrary(g), Value::arbitrary(g)),
                13 => Operation::LessOrEqualUnsigned(Value::arbitrary(g), Value::arbitrary(g)),
                14 => Operation::LessOrEqualSigned(Value::arbitrary(g), Value::arbitrary(g)),
                15 => Operation::LessUnsigned(Value::arbitrary(g), Value::arbitrary(g)),
                16 => Operation::LessSigned(Value::arbitrary(g), Value::arbitrary(g)),

                17 => Operation::ZeroExtend(g.gen(), Value::arbitrary(g)),
                18 => Operation::SignExtend(g.gen(), Value::arbitrary(g)),

                19 => Operation::Move(Value::arbitrary(g)),
                20 => Operation::Initialize(StrRef::arbitrary(g),g.gen()),

                21 => {
                    let v = Value::arbitrary(g);
                    let off = g.gen_range(0, v.bits().unwrap_or(0) + 1);
                    let sz = g.gen_range(0, v.bits().unwrap_or(0) + 1 - off);
                    Operation::Select(off, sz, v)
                }
                22 => Operation::Assume(Constraint::arbitrary(g), Value::arbitrary(g)),

                23 => Operation::Load(Segment::arbitrary(g), Endianess::arbitrary(g), g.gen(), Value::arbitrary(g)),

                24 => {
                    // XXX: make sizes equal?
                    let a = Value::arbitrary(g);
                    let b = Value::arbitrary(g);
                    Operation::Phi(a,b,Value::undef())
                }
                25 => {
                    let a = Value::arbitrary(g);
                    let b = Value::arbitrary(g);
                    let c = Value::arbitrary(g);
                    Operation::Phi(a,b,c)
                }

                _ => unreachable!(),
            };

            match op {
                Operation::Add(Value::Undefined, Value::Undefined) => {}
                Operation::Subtract(Value::Undefined, Value::Undefined) => {}
                Operation::Multiply(Value::Undefined, Value::Undefined) => {}
                Operation::DivideUnsigned(Value::Undefined, Value::Undefined) => {}
                Operation::DivideSigned(Value::Undefined, Value::Undefined) => {}
                Operation::Modulo(Value::Undefined, Value::Undefined) => {}
                Operation::ShiftLeft(Value::Undefined, Value::Undefined) => {}
                Operation::ShiftRightUnsigned(Value::Undefined, Value::Undefined) => {}
                Operation::ShiftRightSigned(Value::Undefined, Value::Undefined) => {}
                Operation::And(Value::Undefined, Value::Undefined) => {}
                Operation::InclusiveOr(Value::Undefined, Value::Undefined) => {}
                Operation::ExclusiveOr(Value::Undefined, Value::Undefined) => {}
                Operation::Equal(Value::Undefined, Value::Undefined) => {}
                Operation::LessOrEqualUnsigned(Value::Undefined, Value::Undefined) => {}
                Operation::LessOrEqualSigned(Value::Undefined, Value::Undefined) => {}
                Operation::LessUnsigned(Value::Undefined, Value::Undefined) => {}
                Operation::LessSigned(Value::Undefined, Value::Undefined) => {}
                Operation::ZeroExtend(_, Value::Undefined) => {}
                Operation::SignExtend(_, Value::Undefined) => {}
                Operation::Select(_, _, Value::Undefined) => {}
                Operation::Phi(Value::Undefined, _, _) => {}
                Operation::Phi(_, Value::Undefined, _) => {}
                Operation::Phi(_, Value::Constant(_), _) => {}
                Operation::Phi(_, _, Value::Constant(_)) => {}

                _ => { return op; }
            }
        }
    }
}

/// Things that can be called.
#[derive(Clone,PartialEq,Eq,Debug,Hash)]
pub enum CallTarget {
    /// A known, analysied function.
    Function(UUID),
    /// An external, unknown function.
    External(Str),
}

/// A memory operation.
#[derive(Clone,PartialEq,Eq,Debug)]
pub enum MemoryOperation {
    /// Writes a memory cell
    Store{
        /// Memory segment before the store.
        segment: Segment,
        /// Byte order if `bytes` > 1
        endianess: Endianess,
        /// Number of bytes to be written.
        bytes: usize,
        /// Address inside `segment` written to.
        address: Value,
        /// Value that is written.
        value: Value,
    },

    /// Memory phi. Merges up to three memory segments.
    MemoryPhi(Option<Segment>,Option<Segment>,Option<Segment>),

    /// Introduces a new memory segment into the function context.
    Allocate{
        /// Segment base name.
        base: StrRef,
    }
}

/// Call/Return operations.
#[derive(Clone,PartialEq,Eq,Debug)]
pub enum FlowOperation {
    /// Function call.
    Call{
        /// Function call target.
        function: UUID,
    },
    /// Call to an imported function.
    ExternalCall{
        /// Name of the imported function.
        external: StrRef,
    },
    /// Call to an unknown value.
    IndirectCall{
        /// Call target
        target: Variable,
    },
    /// Return.
    Return,
}

/// A single IL statement.
#[derive(Clone,PartialEq,Eq,Debug)]
pub enum Statement {
    /// A single RREIL statement.
    Expression{
        /// Value that the operation result is assigned to
        result: Variable,
        /// Operation and its arguments
        op: Operation,
    },
    /// Interprocedural control flow operation
    Flow{
        /// Operation
        op: FlowOperation,
    },
    /// A memory operation
    Memory{
        /// Operation
        op: MemoryOperation,
        /// Memory segment resulting from the memory operation.
        result: Segment,
    },
}

impl Statement {
    /// Does a simple sanity check. The functions returns Err if
    /// - The argument size are not equal
    /// - The result has not the same size as `assignee`
    /// - The select operation arguments are out of range
    pub fn sanity_check(&self) -> Result<()> {
        use std::cmp;
        use errors::ResultExt;

        // check that argument sizes match
        let typecheck_binop = |a: &Value, b: &Value, result: &Variable| -> Result<()> {
            if !(a.bits() == None || b.bits() == None || a.bits() == b.bits()) {
                return Err(format!("Argument sizes mismatch: {:?} vs. {:?}", a, b).into());
            }

            if cmp::max(a.bits().unwrap_or(0), b.bits().unwrap_or(0)) != result.bits {
                return Err(format!("Operation result and result sizes mismatch ({:?})",self).into());
            }

            Ok(())
        };
        let typecheck_cmpop = |a: &Value, b: &Value, result: &Variable| -> Result<()> {
            if !(a.bits() == None || b.bits() == None || a.bits() == b.bits()) {
                return Err("Argument sizes mismatch".into());
            }

            if result.bits != 1 {
                return Err("Compare operation result not a flag".into());
            }

            Ok(())
        };
        let typecheck_unop = |a: &Value, sz: Option<usize>, result: &Variable| -> Result<()> {
            if sz.is_none() {
                // zext?
                if !(a.bits() == None || Some(result.bits) <= a.bits()) {
                    return Err("Operation result and result sizes mismatch".into());
                }
            } else {
                if !(a.bits() == None || Some(result.bits) == sz) {
                    return Err("Operation result and result sizes mismatch".into());
                }
            }
            Ok(())
        };

        match self {
            &Statement::Expression { op: Operation::Add(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::Subtract(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::Multiply(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::DivideUnsigned(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::DivideSigned(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::ShiftLeft(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression {
                op: Operation::ShiftRightUnsigned(ref a, ref b),
                ref result,
            } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::ShiftRightSigned(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::Modulo(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::And(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::ExclusiveOr(ref a, ref b), ref result } => typecheck_binop(a, b, result),
            &Statement::Expression { op: Operation::InclusiveOr(ref a, ref b), ref result } => typecheck_binop(a, b, result),

            &Statement::Expression { op: Operation::Equal(ref a, ref b), ref result } => typecheck_cmpop(a, b, result),
            &Statement::Expression {
                op: Operation::LessOrEqualUnsigned(ref a, ref b),
                ref result,
            } => typecheck_cmpop(a, b, result),
            &Statement::Expression { op: Operation::LessOrEqualSigned(ref a, ref b), ref result } => typecheck_cmpop(a, b, result),
            &Statement::Expression { op: Operation::LessUnsigned(ref a, ref b), ref result } => typecheck_cmpop(a, b, result),
            &Statement::Expression { op: Operation::LessSigned(ref a, ref b), ref result } => typecheck_cmpop(a, b, result),

            &Statement::Expression { op: Operation::SignExtend(ref a, ref b), ref result } => typecheck_unop(b, Some(*a), result),
            &Statement::Expression { op: Operation::ZeroExtend(ref a, ref b), ref result } => typecheck_unop(b, Some(*a), result),
            &Statement::Expression { op: Operation::Move(ref a), ref result } => typecheck_unop(a, None, result),
            &Statement::Expression { op: Operation::Select(off, sz, ref a), ref result } => {
                if !(result.bits == sz && off + sz <= a.bits().unwrap_or(off + sz)) {
                    Err("Ill-sized Select operation".into())
                } else {
                    Ok(())
                }
            }

            &Statement::Expression{ op: Operation::Initialize(_,ref sz), ref result } => {
                if result.bits != *sz {
                    Err("Operation result and result sizes mismatch".into())
                } else {
                    Ok(())
                }
            }

            /*
            &Statement::Expression { op: Operation::Call(_), ref result } => {
                if !(result == &Lvalue::Undefined) {
                    return Err("Call operation can only be assigned to Undefined".into());
                } else {
                    Ok(())
                }
            }

            &Statement::Expression{ op: Operation::Load(_,_,ref sz,_), ref result } => {
                if !result.bits.is_none() && result.bits != Some(*sz) {
                    return Err(format!("Memory operation with invalid size. Expected {:?} got {:?}",Some(*sz),result.bits).into());
                } else if *sz == 0 {
                    return Err("Memory operation of size 0".into());
                } else if *sz % 8 != 0 {
                    return Err("Memory operation not byte aligned".into());
                } else {
                    Ok(())
                }
            }

            &Statement::Expression{ op: Operation::Store(_,_,sz,_,ref val), ref result } => {
                if val.bits().is_some() && result.bits.is_some() && val.bits() != result.bits {
                    return Err("Memory store value with inconsitend size".into());
                } else if sz == 0 {
                    return Err("Memory operation of size 0".into());
                } else if val.bits().is_some() && val.bits() != Some(sz) {
                    return Err(format!("Memory store value with inconsitend size: {:?} != {}",val.bits(),sz).into());
                } else if sz % 8 != 0 {
                    return Err("Memory operation not byte aligned".into());
                } else {
                    Ok(())
                }
            }


            &Statement::Expression { op: Operation::Phi(ref vec), ref result } => {
                if !(vec.iter().all(|rv| rv.bits() == result.bits) && result.bits != None) {
                    return Err("Phi arguments must have equal sizes and can't be Undefined".into());
                } else {
                    Ok(())
                }
            }
            */
            _ => { Ok(()) }
        }.chain_err(|| format!("Failed sanity check for {:?}", self))?;

        Ok(())
    }
}

impl Arbitrary for Statement {
    fn arbitrary<G: Gen>(g: &mut G) -> Self {
        loop {
            let stmt = match g.gen_range(0, 7) {
                0 => Statement::Expression{
                    result: Variable::arbitrary(g),
                    op: Operation::arbitrary(g),
                },
                1 => Statement::Flow{ op: FlowOperation::Call{ function: UUID::arbitrary(g) }, },
                2 => Statement::Flow{ op: FlowOperation::ExternalCall{ external: StrRef::arbitrary(g) }, },
                3 => Statement::Flow{ op: FlowOperation::IndirectCall{ target: Variable::arbitrary(g) }, },
                4 => Statement::Flow{ op: FlowOperation::Return },
                5 => {
                    let mut addr = Value::arbitrary(g);
                    let mut val = Value::arbitrary(g);

                    while addr == Value::Undefined && val == Value::Undefined {
                        addr = Value::arbitrary(g);
                        val = Value::arbitrary(g);
                    }

                    Statement::Memory{
                        op: MemoryOperation::Store{
                            segment: Segment::arbitrary(g),
                            endianess: Endianess::arbitrary(g),
                            bytes: g.gen_range(1,11),
                            address: addr,
                            value: val,
                        },
                        result: Segment::arbitrary(g),
                    }
                }
                6 => {
                    let op = match g.gen_range(0,4) {
                        0 => MemoryOperation::MemoryPhi(
                            None,
                            None,
                            None),
                        1 => MemoryOperation::MemoryPhi(
                            Some(Segment::arbitrary(g)),
                            None,
                            None),
                        2 => MemoryOperation::MemoryPhi(
                            Some(Segment::arbitrary(g)),
                            Some(Segment::arbitrary(g)),
                            None),
                        3 => MemoryOperation::MemoryPhi(
                            Some(Segment::arbitrary(g)),
                            Some(Segment::arbitrary(g)),
                            Some(Segment::arbitrary(g))),
                        _ => unreachable!(),
                    };

                    Statement::Memory{
                        op: op,
                        result: Segment::arbitrary(g),
                    }
                }
                _ => unreachable!(),
            };

            if stmt.sanity_check().is_ok() {
                return stmt;
            }
        }
    }
}

#[macro_export]
macro_rules! rreil2 {
    ( ( $names:tt , $segs:tt ) { } ) => {Ok(vec![])};
    ( ( $names:tt , $segs:tt ) { add $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # Add # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { sub $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # Subtract # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { mul $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # Multiply # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { div $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # DivideUnsigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { divs $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # DivideSigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { shl $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # ShiftLeft # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { shr $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # ShiftRightUnsigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { shrs $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # ShiftRightSigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { mod $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # Modulo # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { and $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # And # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { xor $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # ExclusiveOr # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { or $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # InclusiveOr # $($cdr)*) };

    ( ( $names:tt , $segs:tt ) { cmpeq $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # Equal # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { cmpleu $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # LessOrEqualUnsigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { cmples $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # LessOrEqualSigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { cmpltu $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # LessUnsigned # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { cmplts $($cdr:tt)* } ) => { rreil2_binop!($names # $segs # LessSigned # $($cdr)*) };

    ( ( $names:tt , $segs:tt ) { sel / $off:tt / $sz:tt $($cdr:tt)* } ) => { rreil2_selop!($names # $segs # Select # $off # $sz # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { sext / $sz:tt $($cdr:tt)* } ) => { rreil2_extop!($names # $segs # SignExtend # $sz # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { zext / $sz:tt $($cdr:tt)* } ) => { rreil2_extop!($names # $segs # ZeroExtend # $sz # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { mov $($cdr:tt)* } ) => { rreil2_unop!($names # $segs # Move # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { call $($cdr:tt)* } ) => { rreil2_callop!($names # $segs # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { ret $($cdr:tt)* } ) => { rreil2_retop!($names # $segs # $($cdr)*) };

    ( ( $names:tt , $segs:tt ) { load / $r:ident / $en:ident / $sz:tt $($cdr:tt)* } ) => { rreil_load!($names # $segs # $r # $en # $sz # $($cdr)*) };
    ( ( $names:tt , $segs:tt ) { store / $r:ident / $en:ident / $sz:tt $($cdr:tt)* } ) => { rreil_store!($names # $segs # $r # $en # $sz # $($cdr)*) };
}

include!(concat!(env!("OUT_DIR"), "/rreil.rs"));

#[macro_export]
macro_rules! rreil_var {
    ( $names:tt # ( $a:expr ) ) =>
        { ($a).clone().into() };
    ( $names:tt # $a:ident : $a_w:tt ) => {
        $crate::Variable{
            name: $names.insert(&$crate::Name::new(stringify!($a).into(),None)),
            bits: rreil_imm!($a_w)
        }
    };
}

#[macro_export]
macro_rules! rreil_val {
    ( $names:tt # ? ) => { $crate::Value::Undefined };
    ( $names:tt # ( $a:expr ) ) => { ($a).clone().into() };
    ( $names:tt # [ $a:tt ] : $a_w:tt ) => {
        $crate::Value::Constant($crate::Constant{
            value: rreil_imm!($a) as u64,
            bits: rreil_imm!($a_w)
        })
    };
    ( $names:tt # $a:ident : $a_w:tt ) => {
        $crate::Value::Variable($crate::Variable{
            name: $names.insert(&$crate::Name::new(stringify!($a).into(),None)),
            bits: rreil_imm!($a_w)
        })
    };
}

#[macro_export]
macro_rules! rreil_imm {
    ($x:expr) => ($x as usize);
}

#[cfg(test)]
mod tests {
    use super::*;
    use {Value};

    #[test]
    fn rreil_macro() {
        use {Name,Names,Segments};

        let mut names = Names::default();
        let mut segs = Segments::default();
        let eax = Value::var(names.insert(&Name::new("eax".into(),None)),12).unwrap();
        let t0 = Variable::new(names.insert(&Name::new("eax".into(),None)),12).unwrap();
        let val = Value::val(1337,12).unwrap();

        let _ = rreil2!{
            (names,segs) {
                add (t0), (val), (eax);
                and t0:32, [2147483648]:32, eax:32;
                and t1:32, [2147483648]:32, ebx:32;
                sub t2:32, ebx : 32 , eax:32;
                and t3:32, [2147483648]:32, t2:32;
                shr SF:8, [31]:8, t3:8;
                xor t4:32, t1:32, t0:32;
                xor t5:32, t3:32, t0:32;
                and t6:32, t5:32, t4:32;
                shr OF:8, [31]:8, t6:8;
                and t7:64, [4294967296]:64, t2:64;
                shr CF:8, [32]:8, t7:8;
                and t8:32, [4294967295]:32, t2:32;
                xor t9:8, OF:8, SF:8;
                sel/0/32 ebx:32, rax:64;
            }
        }.unwrap();

        let _ = rreil2!{
            (names,segs) {
                sub t0:32, eax:32, ebx:32;
                cmpltu CF:1, eax:32, ebx:32;
                cmpleu CForZF:1, eax:32, ebx:32;
                cmplts SFxorOF:1, eax:32, ebx:32;
                cmples SFxorOForZF:1, eax:32, ebx:32;
                cmpeq  ZF:1, eax:32, ebx:32;
                cmplts SF:1, t0:32, [0]:32;
                xor OF:1, SFxorOF:1, SF:1;
            }
        }.unwrap();

        let _ = rreil2!{
            (names,segs) {
                sub rax:32, rax:32, [1]:32;
                mov rax:32, [0]:32;
            }
        }.unwrap();

        let _ = rreil2!{
            (names,segs) {
                store/ram/le/32 rax:32, [0]:32;
                load/ram/le/32 rax:32, [0]:32;
            }
        }.unwrap();

        let _ = rreil2!{
            (names,segs) {
                sext/32 rax:32, ax:16;
                zext/32 rax:32, ax:16;
                mov rax:32, tbx:32;
            }
        };
    }
}