use crossbeam;
use num_bigint::Sign;
use num_traits::{FromPrimitive, ToPrimitive};
use std::io::{BufRead, Write};
use std::sync::mpsc;
use std::fmt::Display;
use std::str::FromStr;
use std::u8;
use program::{Program, Command, Integer, BigInteger};
use super::{WsError, WsErrorKind, Options};
mod cached_map;
mod simple_state;
use self::simple_state::SimpleState;
mod jit_state;
use self::jit_state::JitState;
mod bigint_state;
use self::bigint_state::BigIntState;
#[cfg(target_arch="x86_64")]
#[macro_use]
mod compiler_x64;
#[cfg(target_arch="x86")]
#[macro_use]
mod compiler_x86;
#[cfg(target_arch="x86_64")]
use self::compiler_x64::JitCompiler;
#[cfg(target_arch="x86")]
use self::compiler_x86::JitCompiler;
#[cfg(target_arch="x86_64")]
pub use self::compiler_x64::debug_compile;
#[cfg(target_arch="x86")]
pub use self::compiler_x86::debug_compile;
#[cfg(any(target_arch="x86_64", target_arch="x86"))]
mod allocator;
pub trait CheckedArith : Sized + Clone + Default + Display + FromStr + ToString + From<isize> {
fn overflowing_add(&self, rhs: &Self) -> (Self, bool);
fn overflowing_sub(&self, rhs: &Self) -> (Self, bool);
fn overflowing_mul(&self, rhs: &Self) -> (Self, bool);
fn checked_div(&self, rhs: &Self) -> Option<Self>;
fn checked_rem(&self, rhs: &Self) -> Option<Self>;
fn is_zero(&self) -> bool;
fn is_negative(&self) -> bool;
fn from_u8(from: u8) -> Self;
fn into_u8(&self) -> Option<u8>;
}
pub trait State<'a> {
type Var: CheckedArith;
type HeapIterator: Iterator<Item=(Self::Var, Self::Var)> + 'a;
fn options(&self) -> Options;
fn index(&mut self) -> &mut usize;
fn stack(&mut self) -> &mut Vec<Self::Var>;
fn set(&mut self, key: Self::Var, value: Self::Var);
fn get(&self, key: &Self::Var) -> Option<&Self::Var>;
fn iter_heap(&'a self) -> Self::HeapIterator;
fn call(&mut self, retloc: usize);
fn ret(&mut self) -> Option<usize>;
fn input(&mut self) -> &mut dyn BufRead;
fn output(&mut self) -> &mut dyn Write;
fn read_char(&mut self) -> Result<Self::Var, WsError> {
let mut s = [0; 1];
self.output().flush() .map_err(|e| WsError::wrap(e, WsErrorKind::IOError, "Could not flush the output file"))?;
self.input().read_exact(&mut s).map_err(|e| WsError::wrap(e, WsErrorKind::IOError, "Could not read from the input file"))?;
Ok(Self::Var::from_u8(s[0]))
}
fn read_num(&mut self) -> Result<String, WsError> {
let mut s = String::new();
self.output().flush() .map_err(|e| WsError::wrap(e, WsErrorKind::IOError, "Could not flush the output file"))?;
self.input().read_line(&mut s).map_err(|e| WsError::wrap(e, WsErrorKind::IOError, "Could not read a line from the input file"))?;
Ok(s)
}
fn write_char(&mut self, c: Self::Var) -> Result<(), WsError> {
if let Some(val) = c.into_u8() {
self.output().write_all(&[val]).map_err(|e| WsError::wrap(e, WsErrorKind::IOError, "Could not write to the output file"))
} else {
Err(WsError::new(WsErrorKind::RuntimeParseError, "The value is too large to be printed as a character"))
}
}
fn write_num(&mut self, c: Self::Var) -> Result<(), WsError> {
let c = c.to_string();
self.output().write_all(c.as_bytes()).map_err(|e| WsError::wrap(e, WsErrorKind::IOError, "Could not write to the output file"))
}
fn count_instruction(&mut self) { }
fn push_large(&mut self, _: &BigInteger) -> Result<(), WsError> {
Err(WsError::new(WsErrorKind::Overflow, "A large integer was pushed"))
}
fn input_num(&mut self) -> Result<(), WsError> {
let s = self.read_num()?;
let s = s.trim();
let value = s.parse::<Self::Var>().map_err(|_| WsError::new(WsErrorKind::RuntimeParseError, "Expected a number to parse"))?;
let key = self.stack().pop().unwrap();
self.set(key, value);
Ok(())
}
fn interpret_block(&mut self, commands: &[Command]) -> Result<bool, WsError> {
use ::program::Command::*;
let options = self.options();
while let Some(c) = commands.get(*self.index()) {
let len = self.stack().len();
self.count_instruction();
match *c {
Push {ref value} => self.stack().push(value.clone().into()),
PushBig {ref value} => self.push_large(value)?,
Duplicate => if let Some(value) = self.stack().last().cloned() {
self.stack().push(value);
} else {
return Err(WsError::new(WsErrorKind::StackError, "Tried to duplicate but stack is empty"));
},
Copy {index} => if index < self.stack().len() {
let stack = self.stack();
let index = stack.len() - 1 - index;
let value = stack[index].clone();
stack.push(value);
} else {
return Err(WsError::new(WsErrorKind::StackError, "Tried to copy from outside the stack"));
},
Swap => if len > 1 {
self.stack().swap(len - 1, len - 2);
} else {
return Err(WsError::new(WsErrorKind::StackError, "Cannot swap with empty stack"));
},
Discard => if let None = self.stack().pop() {
return Err(WsError::new(WsErrorKind::StackError, "Cannot pop from empty stack"));
},
Slide {amount} => if len > amount {
let top = self.stack().pop().unwrap();
self.stack().truncate(len - amount);
self.stack()[len - amount - 1] = top;
} else {
return Err(WsError::new(WsErrorKind::StackError, "Cannot discard more elements than items exist on stack"));
},
Add => if len > 1 {
let stack = self.stack();
let (val, overflow) = stack[len - 2].overflowing_add(&stack[len - 1]);
if overflow && !options.contains(Options::IGNORE_OVERFLOW) {
return Err(WsError::new(WsErrorKind::Overflow, format!("Overflow during addition: {} + {}", &stack[len - 2], &stack[len - 1])));
}
stack[len - 2] = val;
stack.pop();
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to add"));
},
Subtract => if len > 1 {
let stack = self.stack();
let (val, overflow) = stack[len - 2].overflowing_sub(&stack[len - 1]);
if overflow && !options.contains(Options::IGNORE_OVERFLOW) {
return Err(WsError::new(WsErrorKind::Overflow, format!("Overflow during subtraction: {} - {}", &stack[len - 2], &stack[len - 1])));
}
stack[len - 2] = val;
stack.pop();
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to subtract"));
},
Multiply => if len > 1 {
let stack = self.stack();
let (val, overflow) = stack[len - 2].overflowing_mul(&stack[len - 1]);
if overflow && !options.contains(Options::IGNORE_OVERFLOW) {
return Err(WsError::new(WsErrorKind::Overflow, format!("Overflow during multiplication: {} * {}", &stack[len - 2], &stack[len - 1])));
}
stack[len - 2] = val;
stack.pop();
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to multiply"));
},
Divide => if len > 1 {
let stack = self.stack();
if let Some(val) = stack[len - 2].checked_div(&stack[len - 1]) {
stack[len - 2] = val;
} else if stack[len - 1].is_zero() {
return Err(WsError::new(WsErrorKind::DivisionError, "Divide by zero"));
} else {
return Err(WsError::new(WsErrorKind::Overflow, format!("Overflow during division: {} / {}", stack[len - 2], stack[len - 1])));
}
stack.pop();
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to divide"));
},
Modulo => if len > 1 {
let stack = self.stack();
if let Some(val) = stack[len - 2].checked_rem(&stack[len - 1]) {
stack[len - 2] = val;
} else if stack[len - 1].is_zero() {
return Err(WsError::new(WsErrorKind::DivisionError, "Modulo by zero"));
} else {
return Err(WsError::new(WsErrorKind::Overflow, format!("Overflow during modulo: {} % {}", stack[len - 2], stack[len - 1])));
}
stack.pop();
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to modulo"));
},
Set => if len > 1 {
let value = self.stack().pop().unwrap();
let key = self.stack().pop().unwrap();
self.set(key, value);
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to set value"));
},
Get => if let Some(last) = self.stack().pop() {
if let Some(value) = self.get(&last).cloned() {
self.stack().push(value);
} else if options.contains(Options::UNCHECKED_HEAP) {
self.stack().push(Default::default());
} else {
let err = Err(WsError::new(WsErrorKind::KeyError, format!("Key does not exist on the heap: {}", &last)));
self.stack().push(last);
return err;
}
} else {
return Err(WsError::new(WsErrorKind::StackError, "not enough items on stack to get value"));
},
Label => {
*self.index() += 1;
return Ok(true);
},
Call {index} => {
let retloc = *self.index() + 1;
self.call(retloc);
*self.index() = index;
return Ok(true);
},
Jump {index} => {
*self.index() = index;
return Ok(true);
},
JumpIfZero {index} => if let Some(x) = self.stack().pop() {
if x.is_zero() {
*self.index() = index;
return Ok(true);
}
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to test if zero"));
},
JumpIfNegative {index} => if let Some(x) = self.stack().pop() {
if x.is_negative() {
*self.index() = index;
return Ok(true);
}
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to test if negative"));
},
EndSubroutine => if let Some(index) = self.ret() {
*self.index() = index;
return Ok(true);
} else {
return Err(WsError::new(WsErrorKind::CallStackError, "Not enough items on callstack to return"));
},
EndProgram => return Ok(false),
PrintChar => if let Some(c) = self.stack().pop() {
self.write_char(c)?;
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to print"));
},
PrintNum => if let Some(c) = self.stack().pop() {
self.write_num(c)?;
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to print"));
},
InputChar => if len > 0 {
let c = self.read_char()?;
let key = self.stack().pop().unwrap();
self.set(key, c);
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to input character"));
},
InputNum => if len > 0 {
self.input_num()?;
} else {
return Err(WsError::new(WsErrorKind::StackError, "Not enough items on stack to input number"));
}
};
*self.index() += 1;
}
if options.contains(Options::NO_IMPLICIT_EXIT) {
Err(WsError::new(WsErrorKind::InvalidIndex, "Invalid program counter"))
} else {
Ok(false)
}
}
}
pub trait SmallIntState<'a> : State<'a, Var=Integer> {
fn into_bigintstate(&'a mut self) -> BigIntState<'a>;
}
impl CheckedArith for BigInteger {
fn overflowing_add(&self, rhs: &Self) -> (Self, bool) {
(self + rhs, false)
}
fn overflowing_sub(&self, rhs: &Self) -> (Self, bool) {
(self - rhs, false)
}
fn overflowing_mul(&self, rhs: &Self) -> (Self, bool) {
(self * rhs, false)
}
fn checked_div(&self, rhs: &Self) -> Option<Self> {
BigInteger::checked_div(self, rhs)
}
fn checked_rem(&self, rhs: &Self) -> Option<Self> {
if rhs.sign() == Sign::NoSign {
return None;
}
Some(self % rhs)
}
fn is_zero(&self) -> bool {
self.sign() == Sign::NoSign
}
fn is_negative(&self) -> bool {
self.sign() == Sign::Minus
}
fn from_u8(from: u8) -> Self {
<Self as FromPrimitive>::from_u8(from).unwrap()
}
fn into_u8(&self) -> Option<u8> {
self.to_u8()
}
}
impl CheckedArith for Integer {
fn overflowing_add(&self, rhs: &Self) -> (Self, bool) {
Integer::overflowing_add(*self, *rhs)
}
fn overflowing_sub(&self, rhs: &Self) -> (Self, bool) {
Integer::overflowing_sub(*self, *rhs)
}
fn overflowing_mul(&self, rhs: &Self) -> (Self, bool) {
Integer::overflowing_mul(*self, *rhs)
}
fn checked_div(&self, rhs: &Self) -> Option<Self> {
Integer::checked_div(*self, *rhs)
}
fn checked_rem(&self, rhs: &Self) -> Option<Self> {
Integer::checked_rem(*self, *rhs)
}
fn is_zero(&self) -> bool {
*self == 0
}
fn is_negative(&self) -> bool {
*self < 0
}
fn from_u8(from: u8) -> Self {
from as Self
}
fn into_u8(&self) -> Option<u8> {
if *self <= u8::MAX as Self && *self >= 0 {
Some(*self as u8)
} else {
None
}
}
}
pub struct Interpreter<'a> {
program: &'a Program,
options: Options,
input: &'a mut (dyn BufRead + 'a),
output: &'a mut (dyn Write + 'a)
}
impl<'a> Interpreter<'a> {
pub fn new(program: &'a Program, options: Options, input: &'a mut (dyn BufRead + 'a), output: &'a mut (dyn Write + 'a)) -> Interpreter<'a> {
Interpreter {
program: program,
options: options,
input: input,
output: output,
}
}
fn interpret<'b, T: State<'b>>(state: &mut T, program: &Program) -> Result<(), WsError> {
loop {
match state.interpret_block(&program.commands) {
Ok(true) => continue,
Ok(false) => return Ok(()),
Err(mut e) => {
e.set_location(*state.index());
return Err(e)
}
}
}
}
fn bigint_fallback<'b, T: SmallIntState<'b>>(state: &'b mut T, program: &Program, e: WsError) -> Result<(), WsError> {
match e {
WsError {kind: WsErrorKind::Overflow, ..} => {
let mut state = state.into_bigintstate();
Self::interpret(&mut state, program)
}
WsError {kind: WsErrorKind::InumOverflow(key, val), ..} => {
let mut state = state.into_bigintstate();
state.set(key.into(), val);
Self::interpret(&mut state, program)
}
e => Err(e)
}
}
pub fn count_with_simple_state(&'a mut self) -> Result<usize, WsError> {
let mut state = SimpleState::new(self.options, &mut self.input, &mut self.output);
Self::interpret(&mut state, &self.program)?;
Ok(state.count)
}
pub fn interpret_with_simple_state(&'a mut self) -> Result<(), WsError> {
let mut state = SimpleState::new(self.options, &mut self.input, &mut self.output);
match Self::interpret(&mut state, &self.program) {
Ok(()) => Ok(()),
Err(e) => if self.options.contains(Options::NO_FALLBACK) {
Err(e)
} else {
Self::bigint_fallback(&mut state, &self.program, e)
}
}
}
pub fn interpret_with_fast_state(&'a mut self) -> Result<(), WsError> {
let mut state = JitState::new(self.options, &mut self.input, &mut self.output);
match Self::interpret(&mut state, &self.program) {
Ok(()) => Ok(()),
Err(e) => if self.options.contains(Options::NO_FALLBACK) {
Err(e)
} else {
Self::bigint_fallback(&mut state, &self.program, e)
}
}
}
pub fn interpret_with_bigint_state(&'a mut self) -> Result<(), WsError> {
let mut state = BigIntState::new(self.options, &mut self.input, &mut self.output);
Self::interpret(&mut state, &self.program)
}
#[cfg(any(target_arch="x86_64", target_arch="x86"))]
pub fn jit_aot(&mut self) -> Result<(), WsError> {
let program = &self.program;
let mut state = JitState::new(self.options, &mut self.input, &mut self.output);
let mut compiler = JitCompiler::new(program, self.options);
let mut jit_handles = vec![None; program.commands.len()];
use program::Command::*;
for (i, c) in program.commands.iter().enumerate() {
let i = match *c {
Label | Call {..} if i + 1 != program.commands.len() => i + 1,
_ => continue
};
if let Some(start) = compiler.compile_index(i) {
jit_handles[i] = Some(start);
}
}
compiler.commit();
let executor = compiler.executor();
let lock = executor.lock();
while let Some(&offset) = jit_handles.get(*state.index()) {
if let Some(offset) = offset {
let old_index = *state.index();
unsafe {
state.run_block(lock.ptr(offset));
}
if old_index != *state.index() {
continue;
}
}
match state.interpret_block(&program.commands) {
Ok(true) => (),
Ok(false) => return Ok(()),
Err(mut e) => if self.options.contains(Options::NO_FALLBACK) {
e.set_location(*state.index());
return Err(e)
} else {
e.set_location(*state.index());
return Self::bigint_fallback(&mut state, program, e)
}
}
}
if self.options.contains(Options::NO_IMPLICIT_EXIT) {
Err(WsError::new(WsErrorKind::InvalidIndex, "Invalid program counter"))
} else {
Ok(())
}
}
#[cfg(any(target_arch="x86_64", target_arch="x86"))]
pub fn jit_sync(&mut self) -> Result<(), WsError> {
let program = &self.program;
let mut state = JitState::new(self.options, &mut self.input, &mut self.output);
let mut compiler = JitCompiler::new(program, self.options);
let mut jit_handles = vec![None; self.program.commands.len()];
let executor = compiler.executor();
let mut lock = executor.lock();
match state.interpret_block(&program.commands) {
Ok(true) => (),
Ok(false) => return Ok(()),
Err(mut e) => if self.options.contains(Options::NO_FALLBACK) {
e.set_location(*state.index());
return Err(e)
} else {
e.set_location(*state.index());
return Self::bigint_fallback(&mut state, program, e)
}
}
while let Some(&offset) = jit_handles.get(*state.index()) {
if let Some(offset) = offset {
let old_index = *state.index();
unsafe {
let lock = executor.lock();
state.run_block(lock.ptr(offset));
}
if old_index != *state.index() {
continue;
}
} else if let Some(start) = compiler.compile_index(*state.index()) {
drop(lock);
compiler.commit();
lock = executor.lock();
let old_index = *state.index();
jit_handles[old_index] = Some(start);
unsafe {
state.run_block(lock.ptr(start));
}
if old_index != *state.index() {
continue;
}
}
match state.interpret_block(&program.commands) {
Ok(true) => (),
Ok(false) => return Ok(()),
Err(mut e) => if self.options.contains(Options::NO_FALLBACK) {
e.set_location(*state.index());
return Err(e)
} else {
e.set_location(*state.index());
return Self::bigint_fallback(&mut state, program, e)
}
}
}
if self.options.contains(Options::NO_IMPLICIT_EXIT) {
Err(WsError::new(WsErrorKind::InvalidIndex, "Invalid program counter"))
} else {
Ok(())
}
}
#[cfg(any(target_arch="x86_64", target_arch="x86"))]
pub fn jit_threaded(&mut self) -> Result<(), WsError> {
let mut compiler = JitCompiler::new(self.program, self.options);
let (jit_finished_send, jit_finished_receive) = mpsc::channel();
crossbeam::scope(|scope| {
let executor = compiler.executor();
scope.spawn(move |_| {
use program::Command::*;
for (i, c) in compiler.commands.iter().enumerate() {
let i = match *c {
Label | Call {..} if i + 1 != compiler.commands.len() => i + 1,
_ => continue
};
if let Some(start) = compiler.compile_index(i) {
compiler.commit();
if jit_finished_send.send((i, start)).is_err() {
break;
}
}
}
});
let mut state = JitState::new(self.options, &mut self.input, &mut self.output);
let mut jit_handles = vec![None; self.program.commands.len()];
while let Some(&offset) = jit_handles.get(*state.index()) {
if let Some(offset) = offset {
let old_index = *state.index();
unsafe {
let lock = executor.lock();
state.run_block(lock.ptr(offset));
}
if old_index != *state.index() {
continue;
}
}
while let Ok((index, offset)) = jit_finished_receive.try_recv() {
jit_handles[index] = Some(offset);
}
match state.interpret_block(&self.program.commands) {
Ok(true) => (),
Ok(false) => {
drop(jit_finished_receive);
return Ok(())
},
Err(mut e) => if self.options.contains(Options::NO_FALLBACK) {
drop(jit_finished_receive);
e.set_location(*state.index());
return Err(e);
} else {
drop(jit_finished_receive);
e.set_location(*state.index());
return Self::bigint_fallback(&mut state, self.program, e)
}
}
}
drop(jit_finished_receive);
if self.options.contains(Options::NO_IMPLICIT_EXIT) {
Err(WsError::new(WsErrorKind::InvalidIndex, "Invalid program counter"))
} else {
Ok(())
}
}).unwrap()
}
}