[package]

name = "reowolf_rs"

authors = [

	"Max Henger <henger@cwi.nl>",

	"Christopher Esterhuyse <esterhuy@cwi.nl>",

	"Hans-Dieter Hiep <hdh@cwi.nl>"

]

edition = "2018"

[dependencies]

# convenience macros

maplit = "1.0.2"

derive_more = "0.99.2"

# runtime

bincode = "1.3.1"

serde = { version = "1.0.114", features = ["derive"] }

getrandom = "0.1.14" # tiny crate. used to guess controller-id

# network

mio = { version = "0.7.0", package = "mio", features = ["udp", "tcp", "os-poll"] }

socket2 = { version = "0.3.12", optional = true }

# protocol

backtrace = "0.3"

lazy_static = "1.4.0"

# ffi

# socket ffi

libc = { version = "^0.2", optional = true }

os_socketaddr = { version = "0.1.0", optional = true }

[dev-dependencies]

# test-generator = "0.3.0"

crossbeam-utils = "0.7.2"

lazy_static = "1.4.0"

[lib]

crate-type = [

	"rlib", # for use as a Rust dependency.

]

use std::ptr::null_mut;

use std::hash::{Hash, Hasher};

use std::marker::PhantomData;

const SLAB_SIZE: usize = u16::MAX as usize;

#[derive(Clone)]

pub struct StringRef<'a> {

    data: *const u8,

    length: usize,

    _phantom: PhantomData<&'a [u8]>,

}

// As the StringRef is an immutable thing:

unsafe impl Sync for StringRef<'_> {}

unsafe impl Send for StringRef<'_> {}

impl<'a> StringRef<'a> {

    /// `new` constructs a new StringRef whose data is not owned by the

    /// `StringPool`, hence cannot have a `'static` lifetime.

    pub(crate) fn new(data: &'a [u8]) -> StringRef<'a> {

        // This is an internal (compiler) function: so debug_assert that the

        // string is valid ascii. Most commonly the input will come from the

        // code's source file, which is checked for ASCII-ness anyway.

        debug_assert!(data.is_ascii());

        let length = data.len();

        let data = data.as_ptr();

        StringRef{ data, length, _phantom: PhantomData }

    }

    pub fn as_str(&self) -> &'a str {

        unsafe {

            let slice = std::slice::from_raw_parts::<'a, u8>(self.data, self.length);

            std::str::from_utf8_unchecked(slice)

        }

    }

    pub fn as_bytes(&self) -> &'a [u8] {

        unsafe {

            std::slice::from_raw_parts::<'a, u8>(self.data, self.length)

        }

    }

}

impl<'a> Debug for StringRef<'a> {

    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {

        f.write_str("StringRef{ value: ")?;

        f.write_str(self.as_str())?;

        f.write_str(" }")

    }

}

impl<'a> Display for StringRef<'a> {

    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {

        f.write_str(self.as_str())

    }

}

impl PartialEq for StringRef<'_> {

    fn eq(&self, other: &StringRef) -> bool {

        self.as_str() == other.as_str()

    }

}

impl Eq for StringRef<'_> {}

impl Hash for StringRef<'_> {

    fn hash<H: Hasher>(&self, state: &mut H) {

        state.write(self.as_bytes());

    }

}

struct StringPoolSlab {

    prev: *mut StringPoolSlab,

    data: Vec<u8>,

    remaining: usize,

}

impl StringPoolSlab {

    fn new(prev: *mut StringPoolSlab) -> Self {

        Self{ prev, data: Vec::with_capacity(SLAB_SIZE), remaining: SLAB_SIZE }

    }

}

/// StringPool is a ever-growing pool of strings. Strings have a maximum size

/// equal to the slab size. The slabs are essentially a linked list to maintain

/// pointer-stability of the strings themselves.

/// All `StringRef` instances are invalidated when the string pool is dropped

pub(crate) struct StringPool {

    last: *mut StringPoolSlab,

}

impl StringPool {

    pub(crate) fn new() -> Self {

        // To have some stability we just turn a box into a raw ptr.

        let initial_slab = Box::new(StringPoolSlab::new(null_mut()));

        let initial_slab = Box::into_raw(initial_slab);

        StringPool{

            last: initial_slab,

        }

    }

    /// Interns a string to the `StringPool`, returning a reference to it. The

    /// pointer owned by `StringRef` is `'static` as the `StringPool` doesn't

    /// reallocate/deallocate until dropped (which only happens at the end of

    /// the program.)

    pub(crate) fn intern(&mut self, data: &[u8]) -> StringRef<'static> {

        let data_len = data.len();

        assert!(data_len <= SLAB_SIZE, "string is too large for slab"); // if you hit this, create logic for large-string allocations

        debug_assert!(std::str::from_utf8(data).is_ok(), "string to intern is not valid UTF-8 encoded");

        let mut last = unsafe{&mut *self.last};

        if data.len() > last.remaining {

            // Doesn't fit: allocate new slab

            self.alloc_new_slab();

            last = unsafe{&mut *self.last};

        }

        // Must fit now, compute hash and put in buffer

        debug_assert!(data_len <= last.remaining);

        let range_start = last.data.len();

        last.data.extend_from_slice(data);

        last.remaining -= data_len;

        debug_assert_eq!(range_start + data_len, last.data.len());

        unsafe {

            let start = last.data.as_ptr().offset(range_start as isize);

            StringRef{ data: start, length: data_len, _phantom: PhantomData }

        }

    }

    fn alloc_new_slab(&mut self) {

        let new_slab = Box::new(StringPoolSlab::new(self.last));

        let new_slab = Box::into_raw(new_slab);

        self.last = new_slab;

    }

}

impl Drop for StringPool {

    fn drop(&mut self) {

        let mut new_slab = self.last;

        while !new_slab.is_null() {

            let cur_slab = new_slab;

            unsafe {

                new_slab = (*cur_slab).prev;

                Box::from_raw(cur_slab); // consume and deallocate

            }

        }

    }

}

// String pool cannot be cloned, and the created `StringRef` instances remain

// allocated until the end of the program, so it is always safe to send. It is

// also sync in the sense that it becomes an immutable thing after compilation,

// but lets not derive that if we would ever become a multithreaded compiler in

// the future.

unsafe impl Send for StringPool {}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test_string_just_fits() {

        let large = "0".repeat(SLAB_SIZE);

        let mut pool = StringPool::new();

        let interned = pool.intern(large.as_bytes());

        assert_eq!(interned.as_str(), large);

    }

    #[test]

    #[should_panic]

    fn test_string_too_large() {

        let large = "0".repeat(SLAB_SIZE + 1);

        let mut pool = StringPool::new();

        let _interned = pool.intern(large.as_bytes());

    }

    #[test]

    fn test_lots_of_small_allocations() {

        const NUM_PER_SLAB: usize = 32;

        const NUM_SLABS: usize = 4;

        let to_intern = "0".repeat(SLAB_SIZE / NUM_PER_SLAB);

        let mut pool = StringPool::new();

        let mut last_slab = pool.last;

        let mut all_refs = Vec::new();

        // Fill up first slab

        for _alloc_idx in 0..NUM_PER_SLAB {

            let interned = pool.intern(to_intern.as_bytes());

            all_refs.push(interned);

            assert!(std::ptr::eq(last_slab, pool.last));

        }

        for _slab_idx in 0..NUM_SLABS-1 {

            for alloc_idx in 0..NUM_PER_SLAB {

                let interned = pool.intern(to_intern.as_bytes());

                all_refs.push(interned);

                if alloc_idx == 0 {

                    // First allocation produces a new slab

                    assert!(!std::ptr::eq(last_slab, pool.last));

                    last_slab = pool.last;

                } else {

                    assert!(std::ptr::eq(last_slab, pool.last));

                }

            }

        }

        // All strings are still correct

        for string_ref in all_refs {

            assert_eq!(string_ref.as_str(), to_intern);

        }

    }

}

#[macro_use]

mod macros;

mod protocol;

mod collections;

pub use protocol::ProtocolDescription;

macro_rules! enabled_debug_print {

    (false, $name:literal, $format:literal) => {};

    (false, $name:literal, $format:literal, $($args:expr),*) => {};

    (true, $name:literal, $format:literal) => {

        println!("[{}] {}", $name, $format)

    };

    (true, $name:literal, $format:literal, $($args:expr),*) => {

        println!("[{}] {}", $name, format!($format, $($args),*))

    };

}

use core::hash::Hash;

use core::marker::PhantomData;

pub struct Id<T> {

    // Not actually a signed index into the heap. But the index is set to -1 if

    // we don't know an ID yet. This is checked during debug mode.

    pub(crate) index: i32,

    _phantom: PhantomData<T>,

}

impl<T> Id<T> {

    #[inline] pub(crate) fn new_invalid() -> Self     { Self{ index: -1, _phantom: Default::default() } }

    #[inline] pub(crate) fn new(index: i32) -> Self   { Self{ index, _phantom: Default::default() } }

    #[inline] pub(crate) fn is_invalid(&self) -> bool { self.index < 0 }

}

#[derive(Debug)]

pub(crate) struct Arena<T> {

    store: Vec<T>,

}

//////////////////////////////////

impl<T> Debug for Id<T> {

    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {

        f.debug_struct("Id").field("index", &self.index).finish()

    }

}

impl<T> Clone for Id<T> {

    fn clone(&self) -> Self {

        *self

    }

}

impl<T> Copy for Id<T> {}

impl<T> PartialEq for Id<T> {

    fn eq(&self, other: &Self) -> bool {

        self.index.eq(&other.index)

    }

}

impl<T> Eq for Id<T> {}

impl<T> Hash for Id<T> {

    fn hash<H: std::hash::Hasher>(&self, h: &mut H) {

        self.index.hash(h);

    }

}

impl<T> Arena<T> {

    pub fn new() -> Self {

        Self { store: vec![] }

    }

    pub fn alloc_with_id(&mut self, f: impl FnOnce(Id<T>) -> T) -> Id<T> {

        // Lets keep this a runtime assert.

        assert!(self.store.len() < i32::max_value() as usize, "Arena out of capacity");

        let id = Id::new(self.store.len() as i32);

        self.store.push(f(id));

        id

    }

    // Compiler-internal direct retrieval

    pub(crate) fn get_id(&self, idx: usize) -> Id<T> {

        debug_assert!(idx < self.store.len());

        return Id::new(idx as i32);

    }

    pub fn iter(&self) -> impl Iterator<Item = &T> {

        self.store.iter()

    }

    pub fn len(&self) -> usize {

        self.store.len()

    }

}

impl<T> core::ops::Index<Id<T>> for Arena<T> {

    type Output = T;

    fn index(&self, id: Id<T>) -> &Self::Output {

        debug_assert!(!id.is_invalid(), "attempted to index into Arena with an invalid id (index < 0)");

        self.store.index(id.index as usize)

    }

}

impl<T> core::ops::IndexMut<Id<T>> for Arena<T> {

    fn index_mut(&mut self, id: Id<T>) -> &mut Self::Output {

        debug_assert!(!id.is_invalid(), "attempted to index_mut into Arena with an invalid id (index < 0)");

        self.store.index_mut(id.index as usize)

    }

}

/// eval

///

/// Evaluator of the generated AST. Note that we use some misappropriated terms

/// to describe where values live and what they do. This is a temporary

/// implementation of an evaluator until some kind of appropriate bytecode or

/// machine code is generated.

///

/// Code is always executed within a "frame". For Reowolf the first frame is

/// usually an executed component. All subsequent frames are function calls.

/// Simple values live on the "stack". Each variable/parameter has a place on

/// the stack where its values are stored. If the value is not a primitive, then

/// its value will be stored in the "heap". Expressions are treated differently

/// and use a separate "stack" for their evaluation.

///

/// Since this is a value-based language, most values are copied. One has to be

/// careful with values that reside in the "heap" and make sure that copies are

/// properly removed from the heap..

///

/// Just to reiterate: this is a temporary wasteful implementation. A proper

/// implementation would fully fill out the type table with alignment/size/

/// offset information and lay out bytecode.

pub(crate) mod value;

pub(crate) mod store;

pub(crate) mod executor;

pub(crate) mod error;

pub use error::EvalError;

pub use executor::{EvalContinuation, Prompt};

use std::collections::VecDeque;

use super::store::*;

use crate::protocol::ast::{

    AssignmentOperator,

    BinaryOperator,

    UnaryOperator,

    ConcreteType,

    ConcreteTypePart,

};

use crate::protocol::parser::token_parsing::*;

pub type StackPos = u32;

pub type HeapPos = u32;

#[derive(Debug, Copy, Clone)]

pub enum ValueId {

    Stack(StackPos), // place on stack

    Heap(HeapPos, u32), // allocated region + values within that region

}

/// Represents a value stored on the stack or on the heap. Some values contain

/// a `HeapPos`, implying that they're stored in the store's `Heap`. Clearing

/// a `Value` with a `HeapPos` from a stack must also clear the associated

/// region from the `Heap`.

#[derive(Debug, Clone)]

pub enum Value {

    // Special types, never encountered during evaluation if the compiler works correctly

    Unassigned,                 // Marker when variables are first declared, immediately followed by assignment

    PrevStackBoundary(isize),   // Marker for stack frame beginning, so we can pop stack values

    Ref(ValueId),               // Reference to a value, used by expressions producing references

    Binding(StackPos),          // Reference to a binding variable (reserved on the stack)

    // Builtin types

    Input(PortId),

    Output(PortId),

    Message(HeapPos),

    Null,

    Bool(bool),

    Char(char),

    String(HeapPos),

    UInt8(u8),

    UInt16(u16),

    UInt32(u32),

    UInt64(u64),

    SInt8(i8),

    SInt16(i16),

    SInt32(i32),

    SInt64(i64),

    Array(HeapPos),

    // Instances of user-defined types

    Enum(i64),

    Union(i64, HeapPos),

    Struct(HeapPos),

}

macro_rules! impl_union_unpack_as_value {

    ($func_name:ident, $variant_name:path, $return_type:ty) => {

        impl Value {

            pub(crate) fn $func_name(&self) -> $return_type {

                match self {

                    $variant_name(v) => *v,

                    _ => panic!(concat!("called ", stringify!($func_name()), " on {:?}"), self),

                }

            }

        }

    }

}

impl_union_unpack_as_value!(as_stack_boundary, Value::PrevStackBoundary, isize);

impl_union_unpack_as_value!(as_ref,     Value::Ref,     ValueId);

impl_union_unpack_as_value!(as_input,   Value::Input,   PortId);

impl_union_unpack_as_value!(as_output,  Value::Output,  PortId);

impl_union_unpack_as_value!(as_message, Value::Message, HeapPos);

impl_union_unpack_as_value!(as_bool,    Value::Bool,    bool);

impl_union_unpack_as_value!(as_char,    Value::Char,    char);

impl_union_unpack_as_value!(as_string,  Value::String,  HeapPos);

impl_union_unpack_as_value!(as_uint8,   Value::UInt8,   u8);

impl_union_unpack_as_value!(as_uint16,  Value::UInt16,  u16);

impl_union_unpack_as_value!(as_uint32,  Value::UInt32,  u32);

impl_union_unpack_as_value!(as_uint64,  Value::UInt64,  u64);

impl_union_unpack_as_value!(as_sint8,   Value::SInt8,   i8);

impl_union_unpack_as_value!(as_sint16,  Value::SInt16,  i16);

impl_union_unpack_as_value!(as_sint32,  Value::SInt32,  i32);

impl_union_unpack_as_value!(as_sint64,  Value::SInt64,  i64);

impl_union_unpack_as_value!(as_array,   Value::Array,   HeapPos);

impl_union_unpack_as_value!(as_enum,    Value::Enum,    i64);

impl_union_unpack_as_value!(as_struct,  Value::Struct,  HeapPos);

impl Value {

    pub(crate) fn as_union(&self) -> (i64, HeapPos) {

        match self {

            Value::Union(tag, v) => (*tag, *v),

            _ => panic!("called as_union on {:?}", self),

        }

    }

    pub(crate) fn is_integer(&self) -> bool {

        match self {

            Value::UInt8(_) | Value::UInt16(_) | Value::UInt32(_) | Value::UInt64(_) |

            Value::SInt8(_) | Value::SInt16(_) | Value::SInt32(_) | Value::SInt64(_) => true,

            _ => false

        }

    }

    pub(crate) fn is_unsigned_integer(&self) -> bool {

        match self {

            Value::UInt8(_) | Value::UInt16(_) | Value::UInt32(_) | Value::UInt64(_) => true,

            _ => false

        }

    }

    pub(crate) fn is_signed_integer(&self) -> bool {

        match self {

            Value::SInt8(_) | Value::SInt16(_) | Value::SInt32(_) | Value::SInt64(_) => true,

            _ => false

        }

    }