use std::collections::{HashMap, HashSet};
use std::fmt::Debug;
use std::mem::size_of;
use std::rc::Rc;
use crate::codegen::TraitBuilder;
use crate::common::{ErrorKind, Location, RenderedSignature};
use crate::gc::{Gc, GcRaw, Memory};
use crate::value::{Closure, RawValue};
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Opr24 {
bytes: [u8; 3],
}
#[derive(Debug)]
pub struct U32TooBig(());
impl Opr24 {
pub const MAX: u32 = (1 << 24);
pub fn new(x: u32) -> Result<Self, U32TooBig> {
if x < Self::MAX {
Ok(Self {
bytes: [
(x & 0xFF) as u8,
((x >> 8) & 0xFF) as u8,
((x >> 16) & 0xFF) as u8,
],
})
} else {
Err(U32TooBig(()))
}
}
pub fn pack<T>(x: T) -> Self
where
T: PackableToOpr24,
{
x.pack_to_opr24()
}
pub fn unpack<T>(self) -> T
where
T: PackableToOpr24,
{
T::unpack_from_opr24(self)
}
}
impl From<u8> for Opr24 {
fn from(value: u8) -> Self {
Self {
bytes: [value, 0, 0],
}
}
}
impl TryFrom<usize> for Opr24 {
type Error = U32TooBig;
fn try_from(value: usize) -> Result<Self, Self::Error> {
Self::new(u32::try_from(value).map_err(|_| U32TooBig(()))?)
}
}
impl From<Opr24> for u32 {
fn from(opr: Opr24) -> u32 {
(opr.bytes[0] as u32) | ((opr.bytes[1] as u32) << 8) | ((opr.bytes[2] as u32) << 16)
}
}
impl From<Opr24> for usize {
fn from(opr: Opr24) -> usize {
(opr.bytes[0] as usize) | ((opr.bytes[1] as usize) << 8) | ((opr.bytes[2] as usize) << 16)
}
}
impl std::fmt::Debug for Opr24 {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{:x}", u32::from(*self))
}
}
impl std::fmt::Display for Opr24 {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{:?}", self)
}
}
pub trait PackableToOpr24 {
fn pack_to_opr24(self) -> Opr24;
fn unpack_from_opr24(opr: Opr24) -> Self;
}
impl PackableToOpr24 for (u16, u8) {
fn pack_to_opr24(self) -> Opr24 {
unsafe { Opr24::new((self.0 as u32) << 8 | self.1 as u32).unwrap_unchecked() }
}
fn unpack_from_opr24(opr: Opr24) -> Self {
let x = u32::from(opr);
let big = ((x & 0xFFFF00) >> 8) as u16;
let small = (x & 0x0000FF) as u8;
(big, small)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(u8)]
pub enum Opcode {
#[allow(unused)]
Nop,
PushNil,
PushTrue,
PushFalse,
PushNumber,
PushString,
CreateClosure,
CreateType,
CreateStruct,
CreateTrait,
CreateList,
CreateDict,
AssignGlobal,
SinkGlobal,
GetGlobal,
AssignLocal,
SinkLocal,
GetLocal,
AssignUpvalue,
SinkUpvalue,
GetUpvalue,
CloseLocal,
AssignField,
SinkField,
GetField,
Swap,
Discard,
JumpForward,
JumpForwardIfFalsy,
JumpForwardIfTruthy,
JumpBackward,
EnterBreakableBlock,
ExitBreakableBlock,
Call,
CallMethod,
Return,
Implement,
Negate,
Add,
Subtract,
Multiply,
Divide,
Not,
Equal,
Less,
LessEqual,
Halt,
}
#[derive(Debug)]
pub struct JumpTooFar(());
impl Opcode {
pub const INSTRUCTION_SIZE: usize = 4;
fn forward_jump_offset(from: usize, to: usize) -> Result<Opr24, JumpTooFar> {
assert!(to >= from);
let offset = to - from - Self::INSTRUCTION_SIZE;
if u32::try_from(offset).is_err() {
return Err(JumpTooFar(()));
}
Opr24::new(offset as u32).map_err(|_| JumpTooFar(()))
}
pub fn jump_forward(from: usize, to: usize) -> Result<(Self, Opr24), JumpTooFar> {
let offset = Self::forward_jump_offset(from, to)?;
Ok((Self::JumpForward, offset))
}
pub fn jump_forward_if_falsy(from: usize, to: usize) -> Result<(Self, Opr24), JumpTooFar> {
let offset = Self::forward_jump_offset(from, to)?;
Ok((Self::JumpForwardIfFalsy, offset))
}
pub fn jump_forward_if_truthy(from: usize, to: usize) -> Result<(Self, Opr24), JumpTooFar> {
let offset = Self::forward_jump_offset(from, to)?;
Ok((Self::JumpForwardIfTruthy, offset))
}
fn backward_jump_offset(from: usize, to: usize) -> Result<Opr24, JumpTooFar> {
assert!(to <= from);
let offset = from - to + Self::INSTRUCTION_SIZE;
if u32::try_from(offset).is_err() {
return Err(JumpTooFar(()));
}
Opr24::new(offset as u32).map_err(|_| JumpTooFar(()))
}
pub fn jump_backward(from: usize, to: usize) -> Result<(Self, Opr24), JumpTooFar> {
let offset = Self::backward_jump_offset(from, to)?;
Ok((Self::JumpBackward, offset))
}
}
pub struct Chunk {
pub module_name: Rc<str>,
bytes: Vec<u8>,
locations: Vec<Location>,
pub codegen_location: Location,
pub preallocate_stack_slots: u32,
}
impl Chunk {
pub fn new(module_name: Rc<str>) -> Self {
Self {
module_name,
bytes: Vec::new(),
locations: Vec::new(),
codegen_location: Location::UNINIT,
preallocate_stack_slots: 0,
}
}
pub fn emit(&mut self, what: impl EncodeInstruction) -> usize {
let position = self.bytes.len();
let mut bytes = [0; 4];
what.encode_instruction(&mut bytes);
self.bytes.extend_from_slice(&bytes);
let end = self.bytes.len();
let emitted = end - position;
for _ in 0..emitted / 4 {
self.locations.push(self.codegen_location);
}
position
}
pub fn emit_number(&mut self, number: f64) {
let bytes = number.to_le_bytes();
self.bytes.extend_from_slice(&bytes);
self.locations.push(self.codegen_location);
self.locations.push(self.codegen_location);
}
pub fn emit_string(&mut self, string: &str) {
let start = self.len();
let len = string.len() as u64;
let len_bytes: [u8; 8] = len.to_le_bytes();
self.bytes.extend_from_slice(&len_bytes);
self.bytes.extend(string.as_bytes());
let padded_len = (string.len() + 3) & !3;
let padding = padded_len - string.len();
for _ in 0..padding {
self.bytes.push(0);
}
let end = self.len();
for _ in (0..end - start).step_by(4) {
self.locations.push(self.codegen_location);
}
}
pub fn patch(&mut self, position: usize, instruction: impl EncodeInstruction) {
let mut bytes = [0; 4];
instruction.encode_instruction(&mut bytes);
self.bytes[position..position + Opcode::INSTRUCTION_SIZE].copy_from_slice(&bytes);
}
pub unsafe fn read_instruction(&self, pc: &mut usize) -> (Opcode, Opr24) {
let bytes = &self.bytes[*pc..*pc + Opcode::INSTRUCTION_SIZE];
let mut bytes = <[u8; Opcode::INSTRUCTION_SIZE]>::try_from(bytes).unwrap();
let opcode: Opcode = std::mem::transmute(bytes[0]);
bytes[0] = 0;
let operand = Opr24 {
bytes: [bytes[1], bytes[2], bytes[3]],
};
*pc += Opcode::INSTRUCTION_SIZE;
(opcode, operand)
}
pub unsafe fn read_number(&self, pc: &mut usize) -> f64 {
const SIZE: usize = std::mem::size_of::<f64>();
let bytes = &self.bytes[*pc..*pc + SIZE];
let bytes: [u8; SIZE] = bytes.try_into().unwrap();
let number = f64::from_le_bytes(bytes);
*pc += SIZE;
number
}
pub unsafe fn read_string(&self, pc: &mut usize) -> &str {
let len_bytes: [u8; 8] = self.bytes[*pc..*pc + size_of::<u64>()].try_into().unwrap();
let len = u64::from_le_bytes(len_bytes);
*pc += size_of::<u64>();
let string = &self.bytes[*pc..*pc + len as usize];
let padded_len = (len + 3) & !3;
*pc += padded_len as usize;
std::str::from_utf8_unchecked(string)
}
pub fn len(&self) -> usize {
self.bytes.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn location(&self, pc: usize) -> Location {
let index = pc >> 2;
self.locations.get(index).copied().unwrap_or(Location::UNINIT)
}
pub fn at_end(&self, pc: usize) -> bool {
pc >= self.bytes.len()
}
}
impl Debug for Chunk {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Chunk")
.field("module_name", &self.module_name)
.field("preallocate_stack_slots", &self.preallocate_stack_slots)
.finish()?;
writeln!(f)?;
let mut pc = 0;
while !self.at_end(pc) {
let location = self.location(pc);
let show_pc = pc;
let (opcode, operand) = unsafe { self.read_instruction(&mut pc) };
write!(f, "{show_pc:06x} {} {opcode:?}({operand:?}) ", location)?;
#[allow(clippy::single_match)]
match opcode {
Opcode::PushNumber => write!(f, "{}", unsafe { self.read_number(&mut pc) })?,
Opcode::PushString | Opcode::CreateType => {
write!(f, "{:?}", unsafe { self.read_string(&mut pc) })?
}
| Opcode::JumpForward | Opcode::JumpForwardIfFalsy | Opcode::JumpForwardIfTruthy => {
write!(
f,
"-> {:06x}",
pc + u32::from(operand) as usize + Opcode::INSTRUCTION_SIZE
)?;
}
Opcode::JumpBackward => {
write!(
f,
"-> {:06x}",
pc - u32::from(operand) as usize + Opcode::INSTRUCTION_SIZE
)?;
}
Opcode::CallMethod => {
let (method_index, argument_count) = operand.unpack();
let operand = u32::from(operand);
write!(f, "{operand:06x}:[mi={method_index}, ac={argument_count}]")?;
}
_ => (),
}
writeln!(f)?;
}
Ok(())
}
}
pub trait EncodeInstruction {
fn encode_instruction(&self, bytes: &mut [u8; Opcode::INSTRUCTION_SIZE]);
}
impl EncodeInstruction for (Opcode, Opr24) {
fn encode_instruction(&self, bytes: &mut [u8; Opcode::INSTRUCTION_SIZE]) {
bytes[0] = self.0 as u8;
bytes[1] = self.1.bytes[0];
bytes[2] = self.1.bytes[1];
bytes[3] = self.1.bytes[2];
}
}
impl EncodeInstruction for (Opcode, u16) {
fn encode_instruction(&self, bytes: &mut [u8; Opcode::INSTRUCTION_SIZE]) {
bytes[0] = self.0 as u8;
let ubytes = self.1.to_le_bytes();
bytes[1] = ubytes[0];
bytes[2] = ubytes[1];
bytes[3] = 0;
}
}
impl EncodeInstruction for Opcode {
fn encode_instruction(&self, bytes: &mut [u8; Opcode::INSTRUCTION_SIZE]) {
(*self, Opr24 { bytes: [0, 0, 0] }).encode_instruction(bytes)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum CaptureKind {
Local(Opr24),
Upvalue(Opr24),
}
pub type ForeignFunction = Box<dyn FnMut(&mut Memory, &[RawValue]) -> Result<RawValue, ErrorKind>>;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Control {
GcCollect,
}
pub enum FunctionKind {
Bytecode {
chunk: Rc<Chunk>,
captured_locals: Vec<CaptureKind>,
},
Foreign(ForeignFunction),
Control(Control),
}
impl std::fmt::Debug for FunctionKind {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Bytecode {
chunk,
captured_locals,
} => f
.debug_struct("Bytecode")
.field("chunk", chunk)
.field("captured_locals", captured_locals)
.finish(),
Self::Foreign(..) => f.debug_struct("Foreign").finish_non_exhaustive(),
Self::Control(ctl) => f.debug_tuple("Control").field(ctl).finish(),
}
}
}
#[derive(Debug)]
pub struct Function {
pub name: Rc<str>,
pub parameter_count: Option<u16>,
pub kind: FunctionKind,
pub hidden_in_stack_traces: bool,
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct FunctionSignature {
pub name: Rc<str>,
pub arity: Option<u16>,
pub trait_id: Option<Opr24>,
}
impl FunctionSignature {
pub fn new(name: impl Into<Rc<str>>, arity: impl Into<Option<u16>>) -> Self {
Self {
name: name.into(),
arity: arity.into(),
trait_id: None,
}
}
pub fn render(&self, env: &Environment) -> RenderedSignature {
RenderedSignature {
name: Rc::clone(&self.name),
arity: self.arity.map(|x| x - 1),
trait_name: self
.trait_id
.and_then(|index| env.get_trait(index))
.map(|prototype| Rc::clone(&prototype.name)),
}
}
}
#[derive(Debug)]
pub struct Environment {
globals: HashMap<String, Opr24>,
functions: Vec<Function>,
method_indices: HashMap<FunctionSignature, u16>,
method_signatures: Vec<FunctionSignature>,
pub builtin_dtables: BuiltinDispatchTables,
prototypes: Vec<Option<Prototype>>,
free_prototypes: Vec<Opr24>,
traits: Vec<TraitPrototype>,
}
impl Environment {
pub fn new(builtin_dtables: BuiltinDispatchTables) -> Self {
Self {
globals: HashMap::new(),
functions: Vec::new(),
method_indices: HashMap::new(),
method_signatures: Vec::new(),
builtin_dtables,
prototypes: Vec::new(),
free_prototypes: Vec::new(),
traits: Vec::new(),
}
}
pub fn create_global(&mut self, name: &str) -> Result<Opr24, ErrorKind> {
if self.globals.contains_key(name) {
Ok(*self.globals.get(name).unwrap())
} else {
let slot = Opr24::try_from(self.globals.len()).map_err(|_| ErrorKind::TooManyGlobals)?;
self.globals.insert(name.to_owned(), slot);
Ok(slot)
}
}
pub fn get_global(&self, name: &str) -> Option<Opr24> {
self.globals.get(name).copied()
}
pub fn create_function(&mut self, function: Function) -> Result<Opr24, ErrorKind> {
let slot = Opr24::try_from(self.functions.len()).map_err(|_| ErrorKind::TooManyFunctions)?;
self.functions.push(function);
Ok(slot)
}
pub(crate) unsafe fn get_function_unchecked(&self, id: Opr24) -> &Function {
self.functions.get_unchecked(u32::from(id) as usize)
}
pub(crate) unsafe fn get_function_unchecked_mut(&mut self, id: Opr24) -> &mut Function {
self.functions.get_unchecked_mut(u32::from(id) as usize)
}
pub fn get_method_index(&mut self, signature: &FunctionSignature) -> Result<u16, ErrorKind> {
if let Some(&index) = self.method_indices.get(signature) {
Ok(index)
} else {
let index =
u16::try_from(self.method_indices.len()).map_err(|_| ErrorKind::TooManyMethods)?;
self.method_indices.insert(signature.clone(), index);
self.method_signatures.push(signature.clone());
Ok(index)
}
}
pub fn get_method_signature(&self, method_index: u16) -> Option<&FunctionSignature> {
self.method_signatures.get(method_index as usize)
}
pub(crate) fn create_prototype(&mut self, proto: Prototype) -> Result<Opr24, ErrorKind> {
let slot = if let Some(slot) = self.free_prototypes.pop() {
self.prototypes[u32::from(slot) as usize] = Some(proto);
slot
} else {
let slot = Opr24::try_from(self.prototypes.len()).map_err(|_| ErrorKind::TooManyImpls)?;
self.prototypes.push(Some(proto));
slot
};
Ok(slot)
}
pub(crate) unsafe fn take_prototype_unchecked(&mut self, id: Opr24) -> Prototype {
let proto =
self.prototypes.get_unchecked_mut(u32::from(id) as usize).take().unwrap_unchecked();
self.free_prototypes.push(id);
proto
}
pub fn create_trait(&mut self, name: Rc<str>) -> Result<Opr24, ErrorKind> {
let slot_index = self.traits.len();
let slot = Opr24::try_from(slot_index).map_err(|_| ErrorKind::TooManyTraits)?;
self.traits.push(TraitPrototype {
name,
required: HashSet::new(),
shims: vec![],
});
Ok(slot)
}
pub fn get_trait(&self, id: Opr24) -> Option<&TraitPrototype> {
self.traits.get(usize::from(id))
}
pub fn get_trait_mut(&mut self, id: Opr24) -> Option<&mut TraitPrototype> {
self.traits.get_mut(usize::from(id))
}
}
#[derive(Debug)]
pub struct DispatchTable {
pub pretty_name: Rc<str>,
pub type_name: Rc<str>,
pub instance: Option<GcRaw<DispatchTable>>,
methods: Vec<Option<GcRaw<Closure>>>,
}
impl DispatchTable {
fn new(pretty_name: impl Into<Rc<str>>, type_name: impl Into<Rc<str>>) -> Self {
Self {
pretty_name: pretty_name.into(),
type_name: type_name.into(),
instance: None,
methods: Vec::new(),
}
}
pub fn new_for_type(type_name: impl Into<Rc<str>>) -> Self {
let type_name = type_name.into();
Self::new(format!("type {type_name}"), type_name)
}
pub fn new_for_instance(type_name: impl Into<Rc<str>>) -> Self {
let type_name = type_name.into();
Self::new(Rc::clone(&type_name), type_name)
}
pub fn get_method(&self, index: u16) -> Option<GcRaw<Closure>> {
self.methods.get(index as usize).into_iter().flatten().copied().next()
}
pub fn set_method(&mut self, index: u16, closure: GcRaw<Closure>) {
let index = index as usize;
if index >= self.methods.len() {
self.methods.resize(index + 1, None);
}
self.methods[index] = Some(closure);
}
pub(crate) fn methods(&self) -> impl Iterator<Item = GcRaw<Closure>> + '_ {
self.methods.iter().copied().flatten()
}
}
#[derive(Debug)]
pub struct BuiltinDispatchTables {
pub nil: Gc<DispatchTable>,
pub boolean: Gc<DispatchTable>,
pub number: Gc<DispatchTable>,
pub string: Gc<DispatchTable>,
pub function: Gc<DispatchTable>,
pub list: Gc<DispatchTable>,
pub dict: Gc<DispatchTable>,
}
impl BuiltinDispatchTables {
pub fn empty() -> Self {
Self {
nil: Gc::new(DispatchTable::new("Nil", "Nil")),
boolean: Gc::new(DispatchTable::new("Boolean", "Boolean")),
number: Gc::new(DispatchTable::new("Number", "Boolean")),
string: Gc::new(DispatchTable::new("String", "String")),
function: Gc::new(DispatchTable::new("Function", "Function")),
list: Gc::new(DispatchTable::new("List", "List")),
dict: Gc::new(DispatchTable::new("Dict", "Dict")),
}
}
}
pub struct BuiltinTraits {
pub iterator: Opr24,
pub iterator_has_next: u16,
pub iterator_next: u16,
}
impl BuiltinTraits {
fn try_register_in(env: &mut Environment) -> Result<Self, ErrorKind> {
let mut builder = TraitBuilder::new(env, None, Rc::from("Iterator"))?;
let iterator_has_next = builder.add_method(Rc::from("has_next"), 0)?;
let iterator_next = builder.add_method(Rc::from("next"), 0)?;
let (iterator, _) = builder.build();
Ok(Self {
iterator,
iterator_has_next,
iterator_next,
})
}
pub fn register_in(env: &mut Environment) -> Self {
Self::try_register_in(env).expect("environment should have enough space for built-in traits")
}
}
#[derive(Debug, Default)]
pub(crate) struct Prototype {
pub(crate) instance: HashMap<u16, Opr24>,
pub(crate) trait_instance: HashMap<(Rc<str>, u16, u16), Opr24>,
pub(crate) statics: HashMap<u16, Opr24>,
pub(crate) implemented_trait_count: u16,
}
#[derive(Debug)]
pub struct TraitPrototype {
pub name: Rc<str>,
pub required: HashSet<u16>,
pub shims: Vec<(u16, Opr24)>,
}