Skip to content

Commit bf4afa1

Browse files
progvalprogval
committed
Do not use Rust's call stack to make Python function calls.
aka. become stackless.
1 parent 1c6f071 commit bf4afa1

File tree

3 files changed

+85
-61
lines changed

3 files changed

+85
-61
lines changed

‎src/processor/frame.rs‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,8 @@ use std::collections::HashMap;
22
use std::rc::Rc;
33
use std::cell::RefCell;
44
use super::super::varstack::{VarStack, VectorVarStack};
5-
use super::super::objects::{ObjectRef, ObjectStore, ObjectContent};
5+
use super::super::objects::{ObjectRef, ObjectStore, ObjectContent, Code};
6+
use super::instructions::{Instruction, InstructionDecoder};
67

78
#[derive(Debug)]
89
pub enum Block {
@@ -16,16 +17,21 @@ pub struct Frame {
1617
pub var_stack: VectorVarStack<ObjectRef>,
1718
pub block_stack: Vec<Block>,
1819
pub locals: Rc<RefCell<HashMap<String, ObjectRef>>>,
20+
pub instructions: Vec<Instruction>,
21+
pub code: Code,
1922
pub program_counter: usize,
2023
}
2124

2225
impl Frame {
23-
pub fn new(object: ObjectRef, locals: Rc<RefCell<HashMap<String, ObjectRef>>>) -> Frame {
26+
pub fn new(object: ObjectRef, code: Code, locals: Rc<RefCell<HashMap<String, ObjectRef>>>) -> Frame {
27+
let instructions: Vec<Instruction> = InstructionDecoder::new(code.code.iter()).into_iter().collect();
2428
Frame {
2529
object: object,
2630
var_stack: VectorVarStack::new(),
2731
block_stack: Vec::new(),
2832
locals: locals,
33+
instructions: instructions,
34+
code: code,
2935
program_counter: 0,
3036
}
3137
}

‎src/processor/instructions.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
#[derive(PartialEq)]
22
#[derive(Debug)]
3+
#[derive(Clone)]
34
pub enum CmpOperator {
45
Lt, // Lower than
56
Leq, // Lower or equal
@@ -35,6 +36,7 @@ impl CmpOperator {
3536

3637
#[derive(PartialEq)]
3738
#[derive(Debug)]
39+
#[derive(Clone)]
3840
pub enum Instruction {
3941
PopTop,
4042
DupTop,

‎src/processor/mod.rs‎

Lines changed: 75 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -82,27 +82,35 @@ macro_rules! pop_stack {
8282

8383
macro_rules! unwind {
8484
($call_stack: expr, $traceback: expr, $exception: expr, $exc_type: expr, $value: expr) => {{
85-
let frame = $call_stack.last_mut().unwrap();
86-
loop {
87-
match frame.block_stack.pop() {
88-
None => { // Root block; raise exception to calling function
89-
return PyResult::Raise($exception, $exc_type)
90-
}
91-
Some(Block::TryExcept(begin, end)) => { // Found a try…except block
92-
frame.block_stack.push(Block::TryExcept(begin, end)); // Push it back, it will be poped by PopExcept.
93-
frame.program_counter = end;
94-
let traceback = $traceback;
95-
let exception = $exception;
96-
frame.var_stack.push(traceback.clone()); // traceback
97-
frame.var_stack.push(exception.clone()); // exception
98-
frame.var_stack.push($exc_type); // exception type
85+
// Unwind call stack
86+
'outer: loop {
87+
match $call_stack.pop() {
88+
None => panic!("Exception reached bottom of call stack."),
89+
Some(mut frame) => {
90+
// Unwind block stack
91+
while let Some(block) = frame.block_stack.pop() {
92+
match block {
93+
Block::TryExcept(begin, end) => {
94+
// Found a try…except block
95+
frame.block_stack.push(Block::TryExcept(begin, end)); // Push it back, it will be poped by PopExcept.
96+
frame.program_counter = end;
97+
let traceback = $traceback;
98+
let exception = $exception;
99+
frame.var_stack.push(traceback.clone()); // traceback
100+
frame.var_stack.push(exception.clone()); // exception
101+
frame.var_stack.push($exc_type); // exception type
99102

100-
frame.var_stack.push(traceback); // traceback
101-
frame.var_stack.push($value); // value
102-
frame.var_stack.push(exception); // exception
103-
break
104-
}
105-
Some(_) => { // Non-try…except block, exit it.
103+
frame.var_stack.push(traceback); // traceback
104+
frame.var_stack.push($value); // value
105+
frame.var_stack.push(exception); // exception
106+
107+
$call_stack.push(frame);
108+
break 'outer
109+
}
110+
_ => { // Non-try…except block, exit it.
111+
}
112+
}
113+
}
106114
}
107115
}
108116
}
@@ -118,6 +126,10 @@ pub struct Processor<EP: EnvProxy> {
118126
}
119127

120128
impl<EP: EnvProxy> Processor<EP> {
129+
fn raise_runtime_error(&self, error: ProcessorError) {
130+
// TODO: implement this
131+
panic!(format!("Runtime Error: {:?}", error))
132+
}
121133

122134
// Load a name from the namespace
123135
fn load_name(&mut self, frame: &Frame, name: &String) -> PyResult {
@@ -173,15 +185,17 @@ impl<EP: EnvProxy> Processor<EP> {
173185
}
174186

175187
// Call a primitive / function / code object, with arguments.
176-
fn call_function(&mut self, call_stack: &mut Vec<Frame>, func_ref: &ObjectRef, mut args: Vec<ObjectRef>, kwargs: Vec<ObjectRef>) -> PyResult {
188+
fn call_function(&mut self, call_stack: &mut Vec<Frame>, func_ref: &ObjectRef, mut args: Vec<ObjectRef>, kwargs: Vec<ObjectRef>) {
177189
// TODO: clone only if necessary
178190
match self.store.deref(func_ref).content.clone() {
179191
ObjectContent::Class(None) => {
180-
PyResult::Return(self.store.allocate(Object::new_instance(None, func_ref.clone(), ObjectContent::OtherObject)))
192+
let frame = call_stack.last_mut().unwrap();
193+
frame.var_stack.push(self.store.allocate(Object::new_instance(None, func_ref.clone(), ObjectContent::OtherObject)))
181194
},
182195
ObjectContent::Class(Some(ref code_ref)) => {
183196
// TODO: run code
184-
PyResult::Return(self.store.allocate(Object::new_instance(None, func_ref.clone(), ObjectContent::OtherObject)))
197+
let frame = call_stack.last_mut().unwrap();
198+
frame.var_stack.push(self.store.allocate(Object::new_instance(None, func_ref.clone(), ObjectContent::OtherObject)))
185199
},
186200
ObjectContent::Function(ref func_module, ref code_ref) => {
187201
let code = self.store.deref(code_ref).content.clone();
@@ -204,42 +218,48 @@ impl<EP: EnvProxy> Processor<EP> {
204218
locals.insert(argname.clone(), argvalue);
205219
};
206220
}
207-
let new_frame = Frame::new(func_ref.clone(), locals.clone());
221+
let new_frame = Frame::new(func_ref.clone(), *code, locals);
208222
call_stack.push(new_frame);
209-
let res = self.run_code(call_stack, (*code).clone());
210-
call_stack.pop();
211-
res
212223
}
213224
else {
214-
return PyResult::Error(ProcessorError::NotACodeObject(func_ref.repr(&self.store)))
225+
let err = ProcessorError::NotACodeObject(func_ref.repr(&self.store));
226+
self.raise_runtime_error(err)
215227
}
216228
},
217229
ObjectContent::PrimitiveFunction(ref name) => {
218-
let function = match self.primitive_functions.get(name) {
219-
Some(function) => function.clone(),
220-
None => return PyResult::Error(ProcessorError::UnknownPrimitive(name.clone())),
221-
};
222-
function(self, args)
230+
let function_opt = self.primitive_functions.get(name).map(|o| *o);
231+
match function_opt {
232+
None => {
233+
let err = ProcessorError::UnknownPrimitive(name.clone());
234+
self.raise_runtime_error(err);
235+
},
236+
Some(function) => {
237+
let res = function(self, args); // Call the primitive
238+
match res {
239+
PyResult::Return(res) => call_stack.last_mut().unwrap().var_stack.push(res),
240+
PyResult::Raise(exc, exc_type) => unwind!(call_stack, self.primitive_objects.none.clone(), exc, exc_type, self.primitive_objects.none.clone()),
241+
PyResult::Error(err) => self.raise_runtime_error(err),
242+
};
243+
}
244+
}
223245
},
224246
_ => {
225-
return PyResult::Error(ProcessorError::NotAFunctionObject(format!("called {:?}", self.store.deref(func_ref))));
247+
self.raise_runtime_error(ProcessorError::NotAFunctionObject(format!("called {:?}", self.store.deref(func_ref))));
226248
}
227249
}
228250
}
229251

230252
// Main interpreter loop
231253
// See https://docs.python.org/3/library/dis.html for a description of instructions
232-
fn run_code(&mut self, call_stack: &mut Vec<Frame>, code: Code) -> PyResult {
233-
let bytecode: Vec<u8> = code.code;
234-
let instructions: Vec<Instruction> = instructions::InstructionDecoder::new(bytecode.iter()).into_iter().collect();
254+
fn run_code(&mut self, call_stack: &mut Vec<Frame>) -> PyResult {
235255
loop {
236256
let instruction = {
237257
let frame = call_stack.last_mut().unwrap();
238-
let instruction = py_unwrap!(instructions.get(frame.program_counter), ProcessorError::InvalidProgramCounter);
258+
let instruction = py_unwrap!(frame.instructions.get(frame.program_counter), ProcessorError::InvalidProgramCounter);
239259
frame.program_counter += 1;
240-
instruction
260+
instruction.clone()
241261
};
242-
match *instruction {
262+
match instruction {
243263
Instruction::PopTop => {
244264
let frame = call_stack.last_mut().unwrap();
245265
pop_stack!(frame.var_stack);
@@ -274,8 +294,12 @@ impl<EP: EnvProxy> Processor<EP> {
274294
frame.var_stack.push(self.store.allocate(obj));
275295
}
276296
Instruction::ReturnValue => {
277-
let frame = call_stack.last_mut().unwrap();
278-
return PyResult::Return(pop_stack!(frame.var_stack))
297+
let mut frame = call_stack.pop().unwrap();
298+
let result = pop_stack!(frame.var_stack);
299+
match call_stack.last_mut() {
300+
Some(parent_frame) => parent_frame.var_stack.push(result),
301+
None => return PyResult::Return(result), // End of program
302+
}
279303
}
280304
Instruction::PopBlock => {
281305
let frame = call_stack.last_mut().unwrap();
@@ -302,17 +326,17 @@ impl<EP: EnvProxy> Processor<EP> {
302326
},
303327
Instruction::StoreName(i) => {
304328
let frame = call_stack.last_mut().unwrap();
305-
let name = py_unwrap!(code.names.get(i), ProcessorError::InvalidNameIndex).clone();
329+
let name = py_unwrap!(frame.code.names.get(i), ProcessorError::InvalidNameIndex).clone();
306330
let obj_ref = pop_stack!(frame.var_stack);
307331
frame.locals.borrow_mut().insert(name, obj_ref);
308332
}
309333
Instruction::LoadConst(i) => {
310334
let frame = call_stack.last_mut().unwrap();
311-
frame.var_stack.push(py_unwrap!(code.consts.get(i), ProcessorError::InvalidConstIndex).clone())
335+
frame.var_stack.push(py_unwrap!(frame.code.consts.get(i), ProcessorError::InvalidConstIndex).clone())
312336
}
313337
Instruction::LoadName(i) | Instruction::LoadGlobal(i) => { // TODO: LoadGlobal should look only in globals
314338
let frame = call_stack.last_mut().unwrap();
315-
let name = py_unwrap!(code.names.get(i), ProcessorError::InvalidNameIndex);
339+
let name = py_unwrap!(frame.code.names.get(i), ProcessorError::InvalidNameIndex);
316340
let obj_ref = py_try!(self.load_name(&frame, name));
317341
frame.var_stack.push(obj_ref)
318342
}
@@ -322,7 +346,7 @@ impl<EP: EnvProxy> Processor<EP> {
322346
let obj_ref = py_unwrap!(frame.var_stack.pop(), ProcessorError::StackTooSmall);
323347
self.store.deref(&obj_ref).clone()
324348
};
325-
let name = py_unwrap!(code.names.get(i), ProcessorError::InvalidNameIndex).clone();
349+
let name = py_unwrap!(frame.code.names.get(i), ProcessorError::InvalidNameIndex).clone();
326350
frame.var_stack.push(py_try!(self.load_attr(&obj, name)))
327351
},
328352
Instruction::SetupLoop(i) => {
@@ -359,7 +383,7 @@ impl<EP: EnvProxy> Processor<EP> {
359383
}
360384
Instruction::LoadFast(i) => {
361385
let frame = call_stack.last_mut().unwrap();
362-
let name = py_unwrap!(code.varnames.get(i), ProcessorError::InvalidVarnameIndex).clone();
386+
let name = py_unwrap!(frame.code.varnames.get(i), ProcessorError::InvalidVarnameIndex).clone();
363387
let obj_ref = py_unwrap!(frame.locals.borrow().get(&name), ProcessorError::InvalidName(name)).clone();
364388
frame.var_stack.push(obj_ref)
365389
}
@@ -401,14 +425,7 @@ impl<EP: EnvProxy> Processor<EP> {
401425
args = py_unwrap!(frame.var_stack.pop_many(nb_args), ProcessorError::StackTooSmall);
402426
func = pop_stack!(frame.var_stack);
403427
}
404-
let ret = self.call_function(call_stack, &func, args, kwargs);
405-
match ret {
406-
PyResult::Return(obj_ref) => call_stack.last_mut().unwrap().var_stack.push(obj_ref),
407-
PyResult::Raise(exception, exc_type) => {
408-
unwind!(call_stack, self.primitive_objects.none.clone(), exception, exc_type, self.primitive_objects.none.clone())
409-
},
410-
PyResult::Error(err) => return PyResult::Error(err)
411-
};
428+
self.call_function(call_stack, &func, args, kwargs)
412429
},
413430
Instruction::MakeFunction(0, 0, 0) => {
414431
// TODO: consume default arguments and annotations
@@ -421,7 +438,7 @@ impl<EP: EnvProxy> Processor<EP> {
421438
let func = self.primitive_objects.new_function(func_name, frame.object.module(&self.store), code);
422439
frame.var_stack.push(self.store.allocate(func))
423440
},
424-
_ => panic!(format!("todo: instruction {:?}", *instruction)),
441+
_ => panic!(format!("todo: instruction {:?}", instruction)),
425442
}
426443
};
427444
}
@@ -437,9 +454,8 @@ impl<EP: EnvProxy> Processor<EP> {
437454
};
438455
let module_obj = self.store.allocate(self.primitive_objects.new_module(module_name.clone(), code_ref));
439456
self.modules.insert(module_name.clone(), Rc::new(RefCell::new(HashMap::new())));
440-
let mut call_stack = vec![Frame::new(module_obj, self.modules.get(&module_name).unwrap().clone())];
441-
let res = self.run_code(&mut call_stack, *code);
442-
let frame = call_stack.pop().unwrap();
457+
let mut call_stack = vec![Frame::new(module_obj, *code, self.modules.get(&module_name).unwrap().clone())];
458+
let res = self.run_code(&mut call_stack);
443459
res // Do not raise exceptions before the pop()
444460
}
445461

0 commit comments

Comments
 (0)