1 #!/usr/bin/env python 2 3 """ 4 A really simple virtual processor employing a simple set of instructions which 5 ignore low-level operations and merely concentrate on variable access, structure 6 access, structure allocation and function invocations. 7 8 Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk> 9 10 This program is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free Software 12 Foundation; either version 3 of the License, or (at your option) any later 13 version. 14 15 This program is distributed in the hope that it will be useful, but WITHOUT 16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 18 details. 19 20 You should have received a copy of the GNU General Public License along with 21 this program. If not, see <http://www.gnu.org/licenses/>. 22 23 -------- 24 25 The execution model of the virtual processor involves the following things: 26 27 * Memory 28 * PC (program counter) stack 29 * Frame stack (containing invocation frames in use and in preparation plus 30 temporary storage) 31 * Local frame pointer stack 32 * Invocation frame pointer stack 33 * Exception handler stack 34 * Registers: current value, boolean status value, source value, result, 35 current exception 36 37 The memory contains constants, global variable references and program code. 38 39 The PC stack contains the return address associated with each function 40 invocation. 41 42 The frame pointer stack tracks the position of frames within the frame stack. 43 """ 44 45 class IllegalInstruction(Exception): 46 pass 47 48 class IllegalAddress(Exception): 49 pass 50 51 class EmptyPCStack(Exception): 52 pass 53 54 class EmptyFrameStack(Exception): 55 pass 56 57 class RSVPMachine: 58 59 "A really simple virtual processor." 60 61 def __init__(self, memory, objtable, paramtable, clstable, pc=None, debug=0): 62 63 """ 64 Initialise the processor with a 'memory' (a list of values containing 65 instructions and data) and the optional program counter 'pc'. 66 """ 67 68 self.memory = memory 69 self.objtable = objtable 70 self.paramtable = paramtable 71 self.clstable = clstable 72 self.pc = pc or 0 73 self.debug = debug 74 75 # Stacks. 76 77 self.pc_stack = [] 78 self.frame_stack = [] 79 self.local_sp_stack = [] 80 self.invocation_sp_stack = [] 81 self.handler_stack = [] 82 83 # Registers. 84 85 self.instruction = None 86 self.operand = None 87 self.value = None 88 self.status = None 89 self.source = None 90 self.result = None 91 self.exception = None 92 93 def load(self, address): 94 95 "Return the value at the given 'address'." 96 97 try: 98 return self.memory[address] 99 except IndexError: 100 raise IllegalAddress, address 101 102 def save(self, address, value): 103 104 "Save to the given 'address' the specified 'value'." 105 106 try: 107 self.memory[address] = value 108 except IndexError: 109 raise IllegalAddress, address 110 111 def new(self, size): 112 113 """ 114 Allocate space of the given 'size', returning the address of the space. 115 """ 116 117 addr = len(self.memory) 118 for i in range(0, size): 119 self.memory.append(None) 120 return addr 121 122 def push_pc(self, data): 123 124 "Push 'data' onto the PC stack." 125 126 self.pc_stack.append(data) 127 128 def pull_pc(self): 129 130 "Pull a value from the PC stack and return it." 131 132 try: 133 return self.pc_stack.pop() 134 except IndexError: 135 raise EmptyPCStack 136 137 def run(self): 138 139 "Execute code in the memory, starting from the current PC address." 140 141 try: 142 while 1: 143 self.execute() 144 except EmptyPCStack: 145 pass 146 147 def execute(self): 148 149 "Execute code in the memory at the current PC address." 150 151 self.instruction = self.load(self.pc) 152 self.operand = self.instruction.get_operand() 153 154 instruction_name = self.instruction.__class__.__name__ 155 if self.debug: 156 print "%8d %s" % (self.pc, instruction_name) 157 158 method = self.get_method(instruction_name) 159 160 # Process any inputs of the instruction. 161 162 self.process_inputs() 163 next_pc = method() 164 165 # Update the program counter. 166 167 if next_pc is None: 168 self.pc += 1 169 else: 170 self.pc = next_pc 171 172 def get_method(self, instruction_name): 173 174 "Return the handler method for the given 'instruction_name'." 175 176 method = getattr(self, instruction_name, None) 177 if method is None: 178 raise IllegalInstruction, (self.pc, instruction_name) 179 return method 180 181 def process_inputs(self): 182 183 """ 184 Process any inputs of the current instruction. This permits any directly 185 connected sub-instructions to produce the effects that separate 186 instructions would otherwise have. 187 """ 188 189 for input in (self.instruction.input, self.instruction.source): 190 if input is not None: 191 method = self.get_method(input) 192 method() 193 194 def jump(self, addr, next): 195 196 """ 197 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 198 identifies a library function then invoke the library function and set 199 PC to 'next' afterwards; otherwise, set PC to 'addr'. 200 """ 201 202 if isinstance(addr, str): 203 getattr(self, addr)() 204 return next 205 else: 206 self.push_pc(self.pc + 2) 207 return addr 208 209 # Instructions. 210 211 def LoadConst(self): 212 self.value = None, self.operand 213 214 def LoadName(self): 215 frame = self.local_sp_stack[-1] 216 self.value = self.frame_stack[frame + self.operand] 217 218 def StoreName(self): 219 frame = self.local_sp_stack[-1] 220 self.frame_stack[frame + self.operand] = self.value 221 222 LoadTemp = LoadName 223 StoreTemp = StoreName 224 225 def LoadAddress(self): 226 # Preserve context (potentially null). 227 self.value = self.load(self.operand) 228 229 def LoadAddressContext(self): 230 value = self.load(self.operand) 231 # Replace the context with the current value. 232 self.value = self.value[1], value[1] 233 234 def StoreAddress(self): 235 # Preserve context. 236 self.save(self.operand, self.value) 237 238 def MakeObject(self): 239 # Introduce null context for new object. 240 self.value = None, self.new(self.operand) 241 242 def LoadAttr(self): 243 context, ref = self.value 244 # Retrieved context should already be appropriate for the instance. 245 self.value = self.load(ref + self.operand) 246 247 def StoreAttr(self): 248 context, ref = self.value 249 self.save(ref + self.operand, self.source) 250 251 def LoadAttrIndex(self): 252 context, ref = self.value 253 code = self.load(ref) # + 0 (the classcode) 254 element = self.objtable[code + self.operand] 255 found_code, class_attr, replace_context, offset = element 256 if found_code == code: 257 if class_attr: 258 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 259 if replace_context: 260 self.value = ref, loaded_ref # classes can also replace the context if compatible 261 return 262 self.value = loaded_context, loaded_ref 263 else: 264 self.value = self.load(ref + offset) 265 else: 266 # NOTE: This should cause an attribute error. 267 self.value = None 268 269 def StoreAttrIndex(self): pass 270 271 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 272 273 def MakeFrame(self): 274 self.invocation_sp_stack.append(len(self.frame_stack)) 275 self.frame_stack.extend([None] * self.operand) 276 277 def JumpWithFrame(self): 278 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 279 context, ref = self.value 280 return self.jump(ref.code_location, self.pc + 1) # return to the instruction after this one 281 282 def DropFrame(self): 283 result = self.pull() 284 self.local_sp_stack.pop() 285 frame = self.invocation_sp_stack.pop() 286 self.frame_stack = self.frame_stack[:frame] # reset stack before call 287 288 def CheckFrame(self): pass 289 290 def CheckSelf(self): pass 291 292 def LoadCallable(self): pass 293 294 def LoadContext(self): 295 context, ref = self.value 296 self.push((None, context)) 297 298 def Return(self): 299 self.pc = self.pull_pc() 300 301 def LoadResult(self): 302 self.value = self.result 303 304 def StoreResult(self): 305 self.result = self.value 306 307 def LoadException(self): 308 self.value = self.exception 309 310 def StoreException(self): 311 self.exception = self.value 312 313 def LoadBoolean(self): 314 self.value = self.status 315 316 def Jump(self): 317 return self.operand 318 319 def JumpIfTrue(self): 320 if self.status: 321 return self.operand 322 323 def JumpIfFalse(self): 324 if not self.status: 325 return self.operand 326 327 def StoreFrame(self): 328 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 329 self.frame_stack[frame + self.operand] = self.value 330 331 # vim: tabstop=4 expandtab shiftwidth=4