1use std::collections::HashMap;
2
3use byteorder::{BigEndian, ByteOrder};
4use compiler::compiler::Bytecode;
5use compiler::op_code::{cast_u8_to_opcode, Opcode};
6use object::builtins::BuiltIns;
7use object::Object;
8
9use crate::frame::Frame;
10use crate::value::{
11 alloc_value, call_builtin, export_object, get_value, import_object, GcClosure, HashKey, Value,
12};
13use crate::{GcHeap, GcRef};
14
15const STACK_SIZE: usize = 2048;
16pub const GLOBAL_SIZE: usize = 65536;
17const MAX_FRAMES: usize = 1024;
18
19enum CalleeKind {
20 Closure(GcClosure),
21 Builtin(object::BuiltinFunc),
22}
23
24pub struct GcVM {
25 heap: GcHeap,
26 constants: Vec<GcRef>,
27 stack: Vec<GcRef>,
28 sp: usize,
29 globals: Vec<GcRef>,
30 frames: Vec<Frame>,
31 frame_index: usize,
32 null: GcRef,
33 last_popped: GcRef,
34}
35
36impl GcVM {
37 pub fn new(bytecode: Bytecode) -> Self {
38 let mut heap = GcHeap::new();
39 let null = alloc_value(&mut heap, Value::Null);
40 let constants = bytecode
41 .constants
42 .iter()
43 .map(|constant| import_object(&mut heap, constant))
44 .collect();
45
46 let main_fn = alloc_value(
47 &mut heap,
48 Value::CompiledFunction(object::CompiledFunction {
49 instructions: bytecode.instructions.data,
50 num_locals: 0,
51 num_parameters: 0,
52 }),
53 );
54 let main_instructions = compiled_instructions(&heap, main_fn);
55 let main_frame = Frame::new(
58 GcClosure {
59 func: main_fn,
60 free: vec![],
61 },
62 main_instructions,
63 0,
64 );
65
66 let empty_frame = Frame::new(
67 GcClosure {
68 func: main_fn,
69 free: vec![],
70 },
71 vec![],
72 0,
73 );
74
75 let mut frames = vec![empty_frame; MAX_FRAMES];
76 frames[0] = main_frame;
77
78 let stack = (0..STACK_SIZE).map(|_| heap.dup(null)).collect();
79 let globals = (0..GLOBAL_SIZE).map(|_| heap.dup(null)).collect();
80 let last_popped = heap.dup(null);
81
82 GcVM {
83 heap,
84 constants,
85 stack,
86 sp: 0,
87 globals,
88 frames,
89 frame_index: 1,
90 null,
91 last_popped,
92 }
93 }
94
95 pub fn heap(&self) -> &GcHeap {
96 &self.heap
97 }
98
99 pub fn heap_mut(&mut self) -> &mut GcHeap {
100 &mut self.heap
101 }
102
103 pub fn run(&mut self) {
104 while self.current_frame().ip < self.current_frame().instructions.len() as i32 - 1 {
105 self.current_frame().ip += 1;
106 let ip = self.current_frame().ip as usize;
107 let ins = self.current_frame().instructions.clone();
108 let op = *ins.get(ip).unwrap();
109 let opcode = cast_u8_to_opcode(op);
110
111 match opcode {
112 Opcode::OpConst => {
113 let const_index = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
114 self.current_frame().ip += 2;
115 self.dup_and_push(self.constants[const_index]);
116 }
117 Opcode::OpAdd | Opcode::OpSub | Opcode::OpMul | Opcode::OpDiv => {
118 self.execute_binary_operation(opcode);
119 }
120 Opcode::OpPop => {
121 self.pop_discard();
122 }
123 Opcode::OpTrue => {
124 self.alloc_and_push(Value::Boolean(true));
125 }
126 Opcode::OpFalse => {
127 self.alloc_and_push(Value::Boolean(false));
128 }
129 Opcode::OpEqual | Opcode::OpNotEqual | Opcode::OpGreaterThan => {
130 self.execute_comparison(opcode);
131 }
132 Opcode::OpMinus => {
133 self.execute_minus_operation();
134 }
135 Opcode::OpBang => {
136 self.execute_bang_operation();
137 }
138 Opcode::OpJump => {
139 let pos = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
140 self.current_frame().ip = pos as i32 - 1;
141 }
142 Opcode::OpJumpNotTruthy => {
143 let pos = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
144 self.current_frame().ip += 2;
145 let condition = self.pop_owned();
146 if !is_truthy(&self.heap, condition) {
147 self.current_frame().ip = pos as i32 - 1;
148 }
149 self.heap.free(condition);
150 }
151 Opcode::OpNull => {
152 self.dup_and_push(self.null);
153 }
154 Opcode::OpGetGlobal => {
155 let global_index = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
156 self.current_frame().ip += 2;
157 self.dup_and_push(self.globals[global_index]);
158 }
159 Opcode::OpSetGlobal => {
160 let global_index = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
161 self.current_frame().ip += 2;
162 let value = self.pop_owned();
163 self.heap.free(self.globals[global_index]);
164 self.globals[global_index] = value;
165 }
166 Opcode::OpArray => {
167 let count = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
168 self.current_frame().ip += 2;
169 let start = self.sp - count;
170 let elements = self.build_array(start, self.sp);
171 let array = alloc_value(&mut self.heap, Value::Array(elements));
172 self.clear_stack_range(start, self.sp);
173 self.sp = start;
174 self.push_raw(array);
175 }
176 Opcode::OpHash => {
177 let count = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
178 self.current_frame().ip += 2;
179 let start = self.sp - count;
180 let elements = self.build_hash(start, self.sp);
181 let hash = alloc_value(&mut self.heap, Value::Hash(elements));
182 self.clear_stack_range(start, self.sp);
183 self.sp = start;
184 self.push_raw(hash);
185 }
186 Opcode::OpIndex => {
187 let index = self.pop_owned();
188 let left = self.pop_owned();
189 self.execute_index_operation(left, index);
190 self.heap.free(index);
191 self.heap.free(left);
192 }
193 Opcode::OpReturnValue => {
194 let return_value = self.pop_owned();
195 let frame = self.pop_frame();
196 let new_sp = frame.base_pointer - 1;
197 self.clear_stack_range(new_sp, self.sp);
198 self.sp = new_sp;
199 self.push_raw(return_value);
200 }
201 Opcode::OpReturn => {
202 let frame = self.pop_frame();
203 let new_sp = frame.base_pointer - 1;
204 self.clear_stack_range(new_sp, self.sp);
205 self.sp = new_sp;
206 self.dup_and_push(self.null);
207 }
208 Opcode::OpCall => {
209 let num_args = ins[ip + 1] as usize;
210 self.current_frame().ip += 1;
211 self.execute_call(num_args);
212 }
213 Opcode::OpSetLocal => {
214 let local_index = ins[ip + 1] as usize;
215 self.current_frame().ip += 1;
216 let base = self.current_frame().base_pointer;
217 let value = self.pop_owned();
218 self.heap.free(self.stack[base + local_index]);
219 self.stack[base + local_index] = value;
220 }
221 Opcode::OpGetLocal => {
222 let local_index = ins[ip + 1] as usize;
223 self.current_frame().ip += 1;
224 let base = self.current_frame().base_pointer;
225 self.dup_and_push(self.stack[base + local_index]);
226 }
227 Opcode::OpGetBuiltin => {
228 let built_index = ins[ip + 1] as usize;
229 self.current_frame().ip += 1;
230 let definition = BuiltIns.get(built_index).unwrap().1;
231 self.alloc_and_push(Value::Builtin(definition));
232 }
233 Opcode::OpClosure => {
234 let const_index = BigEndian::read_u16(&ins[ip + 1..ip + 3]) as usize;
235 let num_free = ins[ip + 3] as usize;
236 self.current_frame().ip += 3;
237 self.push_closure(const_index, num_free);
238 }
239 Opcode::OpGetFree => {
240 let free_index = ins[ip + 1] as usize;
241 self.current_frame().ip += 1;
242 let free_var = self.current_frame().cl.free[free_index];
243 self.dup_and_push(free_var);
244 }
245 Opcode::OpCurrentClosure => {
246 let current = self.current_frame().cl.clone();
247 self.alloc_and_push(Value::Closure(current));
248 }
249 }
250 }
251 }
252
253 pub fn last_popped_stack_elm(&self) -> Option<GcRef> {
254 Some(self.last_popped)
255 }
256
257 pub fn export_last_result(&self) -> Option<Object> {
258 self.last_popped_stack_elm()
259 .map(|reference| export_object(&self.heap, reference))
260 }
261
262 fn alloc_and_push(&mut self, value: Value) {
263 let reference = alloc_value(&mut self.heap, value);
264 self.push_raw(reference);
265 }
266
267 fn dup_and_push(&mut self, reference: GcRef) {
268 let duplicated = self.heap.dup(reference);
269 self.push_raw(duplicated);
270 }
271
272 fn push_raw(&mut self, value: GcRef) {
273 if self.sp >= STACK_SIZE {
274 panic!("Stack overflow");
275 }
276 let old = self.stack[self.sp];
277 self.stack[self.sp] = value;
278 self.heap.free(old);
279 self.sp += 1;
280 }
281
282 fn pop_owned(&mut self) -> GcRef {
287 self.sp -= 1;
288 let value = self.stack[self.sp];
289 self.stack[self.sp] = self.heap.dup(self.null);
290 value
291 }
292
293 fn pop_discard(&mut self) {
294 let value = self.pop_owned();
295 self.heap.free(self.last_popped);
296 self.last_popped = value;
297 }
298
299 fn clear_stack_range(&mut self, start: usize, end: usize) {
300 for index in start..end {
301 let old = self.stack[index];
302 self.stack[index] = self.heap.dup(self.null);
303 self.heap.free(old);
304 }
305 }
306
307 fn execute_binary_operation(&mut self, opcode: Opcode) {
308 let right = self.pop_owned();
309 let left = self.pop_owned();
310 match (get_value(&self.heap, left), get_value(&self.heap, right)) {
311 (Value::Integer(l), Value::Integer(r)) => {
312 let result = match opcode {
313 Opcode::OpAdd => l + r,
314 Opcode::OpSub => l - r,
315 Opcode::OpMul => l * r,
316 Opcode::OpDiv => l / r,
317 _ => panic!("Unknown opcode for int"),
318 };
319 self.alloc_and_push(Value::Integer(result));
320 }
321 (Value::String(l), Value::String(r)) => {
322 let result = match opcode {
323 Opcode::OpAdd => l.to_string() + r,
324 _ => panic!("Unknown opcode for string"),
325 };
326 self.alloc_and_push(Value::String(result));
327 }
328 _ => panic!("unsupported binary operation for those types"),
329 }
330 self.heap.free(left);
331 self.heap.free(right);
332 }
333
334 fn execute_comparison(&mut self, opcode: Opcode) {
335 let right = self.pop_owned();
336 let left = self.pop_owned();
337 let result = match (get_value(&self.heap, left), get_value(&self.heap, right)) {
338 (Value::Integer(l), Value::Integer(r)) => match opcode {
339 Opcode::OpEqual => l == r,
340 Opcode::OpNotEqual => l != r,
341 Opcode::OpGreaterThan => l > r,
342 _ => panic!("Unknown opcode for comparing int"),
343 },
344 (Value::Boolean(l), Value::Boolean(r)) => match opcode {
345 Opcode::OpEqual => l == r,
346 Opcode::OpNotEqual => l != r,
347 _ => panic!("Unknown opcode for comparing boolean"),
348 },
349 _ => panic!("unsupported comparison for those types"),
350 };
351 self.alloc_and_push(Value::Boolean(result));
352 self.heap.free(left);
353 self.heap.free(right);
354 }
355
356 fn execute_minus_operation(&mut self) {
357 let operand = self.pop_owned();
358 let negated = match get_value(&self.heap, operand) {
359 Value::Integer(l) => -l,
360 _ => panic!("unsupported types for negation"),
361 };
362 self.alloc_and_push(Value::Integer(negated));
363 self.heap.free(operand);
364 }
365
366 fn execute_bang_operation(&mut self) {
367 let operand = self.pop_owned();
368 let result = match get_value(&self.heap, operand) {
369 Value::Boolean(l) => !l,
370 _ => false,
371 };
372 self.alloc_and_push(Value::Boolean(result));
373 self.heap.free(operand);
374 }
375
376 fn build_array(&mut self, start: usize, end: usize) -> Vec<GcRef> {
377 let mut elements = Vec::with_capacity(end - start);
378 for i in start..end {
379 elements.push(self.stack[i]);
380 }
381 elements
382 }
383
384 fn build_hash(&mut self, start: usize, end: usize) -> HashMap<HashKey, GcRef> {
385 let mut elements = HashMap::new();
386 for i in (start..end).step_by(2) {
387 let key_ref = self.stack[i];
388 let key = HashKey::from_value(get_value(&self.heap, key_ref))
389 .expect("hash key must be hashable");
390 elements.insert(key, self.stack[i + 1]);
391 }
392 elements
393 }
394
395 fn execute_index_operation(&mut self, left: GcRef, index: GcRef) {
396 let left_value = get_value(&self.heap, left).clone();
397 let index_value = get_value(&self.heap, index).clone();
398 match (&left_value, &index_value) {
399 (Value::Array(array), Value::Integer(i)) => {
400 self.execute_array_index(array, *i);
401 }
402 (Value::Hash(hash), _) => {
403 self.execute_hash_index(hash, &index_value);
404 }
405 _ => panic!("unsupported index operation for those types"),
406 }
407 }
408
409 fn execute_array_index(&mut self, array: &[GcRef], index: i64) {
410 if index < array.len() as i64 && index >= 0 {
411 self.dup_and_push(array[index as usize]);
412 } else {
413 self.dup_and_push(self.null);
414 }
415 }
416
417 fn execute_hash_index(&mut self, hash: &HashMap<HashKey, GcRef>, index: &Value) {
418 let key = HashKey::from_value(index).expect("unsupported hash index key");
419 match hash.get(&key) {
420 Some(value) => self.dup_and_push(*value),
421 None => self.dup_and_push(self.null),
422 }
423 }
424
425 fn current_frame(&mut self) -> &mut Frame {
426 &mut self.frames[self.frame_index - 1]
427 }
428
429 fn push_frame(&mut self, frame: Frame) {
430 self.frames[self.frame_index] = frame;
431 self.frame_index += 1;
432 }
433
434 fn pop_frame(&mut self) -> Frame {
435 self.frame_index -= 1;
436 self.frames[self.frame_index].clone()
437 }
438
439 fn execute_call(&mut self, num_args: usize) {
440 let callee = self.stack[self.sp - 1 - num_args];
441 match callee_kind(&self.heap, callee) {
442 CalleeKind::Closure(closure) => self.call_closure(closure, num_args),
443 CalleeKind::Builtin(builtin) => self.call_builtin(builtin, num_args),
444 }
445 }
446
447 fn call_closure(&mut self, closure: GcClosure, num_args: usize) {
448 let compiled = match get_value(&self.heap, closure.func) {
449 Value::CompiledFunction(f) => f.clone(),
450 _ => panic!("closure without compiled function"),
451 };
452 if compiled.num_parameters != num_args {
453 panic!("wrong number of arguments: want={}, got={}", compiled.num_parameters, num_args);
454 }
455
456 let frame = Frame::new(closure, compiled.instructions, self.sp - num_args);
457 self.sp = frame.base_pointer + compiled.num_locals;
458 self.push_frame(frame);
459 }
460
461 fn call_builtin(&mut self, builtin: object::BuiltinFunc, num_args: usize) {
462 let base = self.sp - num_args - 1;
463 let args = self.stack[self.sp - num_args..self.sp].to_vec();
464 let result = call_builtin(&mut self.heap, builtin, args);
465 self.clear_stack_range(base, self.sp);
466 self.sp = base;
467 self.push_raw(result);
468 }
469
470 fn push_closure(&mut self, const_index: usize, num_free: usize) {
471 match get_value(&self.heap, self.constants[const_index]).clone() {
472 Value::CompiledFunction(_) => {
473 let start = self.sp - num_free;
474 let mut free = Vec::with_capacity(num_free);
475 for i in 0..num_free {
476 free.push(self.stack[start + i]);
477 }
478 let func = self.constants[const_index];
479 let closure = alloc_value(
480 &mut self.heap,
481 Value::Closure(GcClosure {
482 func,
483 free,
484 }),
485 );
486 self.clear_stack_range(start, self.sp);
487 self.sp = start;
488 self.push_raw(closure);
489 }
490 other => panic!("not a function {:?}", other),
491 }
492 }
493}
494
495fn is_truthy(heap: &GcHeap, condition: GcRef) -> bool {
496 match get_value(heap, condition) {
497 Value::Boolean(b) => *b,
498 Value::Null => false,
499 _ => true,
500 }
501}
502
503fn callee_kind(heap: &GcHeap, reference: GcRef) -> CalleeKind {
504 match get_value(heap, reference) {
505 Value::Closure(closure) => CalleeKind::Closure(closure.clone()),
506 Value::Builtin(builtin) => CalleeKind::Builtin(*builtin),
507 _ => panic!("calling non-closure"),
508 }
509}
510
511fn compiled_instructions(heap: &GcHeap, func: GcRef) -> Vec<u8> {
512 match get_value(heap, func) {
513 Value::CompiledFunction(f) => f.instructions.clone(),
514 _ => panic!("expected compiled function"),
515 }
516}