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, 2009 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 contains constants, global variable 28 references and program code 29 30 * PC (program counter) stack contains the return address associated 31 with each function invocation 32 33 * Frame stack contains invocation frames in use and in 34 preparation plus temporary storage 35 36 * Local frame pointer stack refers to the frames in the frame stack 37 38 * Invocation frame pointer stack 39 40 * Exception handler stack 41 42 * Exception handler locals stack refers to the state of the local frame 43 pointer stack 44 45 * Exception handler PC stack refers to the state of the PC stack 46 47 * Registers: current value, 48 boolean status value, 49 source value, 50 current result, 51 current exception, 52 current callable 53 """ 54 55 from micropython.common import DataObject # for creating "nice" new objects 56 57 class IllegalInstruction(Exception): 58 pass 59 60 class IllegalAddress(Exception): 61 def __init__(self, address): 62 self.address = address 63 def __repr__(self): 64 return "IllegalAddress(%r)" % self.address 65 def __str__(self): 66 return repr(self) 67 68 class EmptyPCStack(Exception): 69 pass 70 71 class EmptyFrameStack(Exception): 72 pass 73 74 class RSVPMachine: 75 76 "A really simple virtual processor." 77 78 def __init__(self, memory, objlist, paramlist, pc=None, debug=0): 79 80 """ 81 Initialise the processor with a 'memory' (a list of values containing 82 instructions and data) and the optional program counter 'pc'. 83 """ 84 85 self.memory = memory 86 self.objlist = objlist.as_raw() 87 self.paramlist = paramlist.as_raw() 88 self.pc = pc or 0 89 self.debug = debug 90 91 # Stacks. 92 93 self.pc_stack = [] 94 self.frame_stack = [] 95 self.local_sp_stack = [0] 96 self.invocation_sp_stack = [] 97 self.handler_stack = [len(self.memory) - 1] # final handler is the end of the code 98 self.handler_local_sp_stack = [] 99 self.handler_pc_stack = [] 100 101 # Registers. 102 103 self.instruction = None 104 self.operand = None 105 self.value = None 106 self.status = None 107 self.source = None 108 self.callable = None 109 self.result = None 110 self.exception = None 111 112 # Constants. 113 114 self.attr_error = objlist.access("__builtins__", "AttributeError").value.location 115 self.type_error = objlist.access("__builtins__", "TypeError").value.location 116 117 # Native class constants. 118 119 cls = objlist.access("__builtins__", "int") 120 self.int_class = cls and cls.value.location 121 122 # Debugging methods. 123 124 def dump(self): 125 print "PC", self.pc, "->", self.load(self.pc) 126 print "PC stack", self.pc_stack 127 print "Frame stack", self.frame_stack 128 print "Local stack pointers", self.local_sp_stack 129 print "Invocation stack pointers", self.invocation_sp_stack 130 print "Handler stack", self.handler_stack 131 print "Handler frame stack", self.handler_local_sp_stack 132 print "Handler PC stack", self.handler_pc_stack 133 print 134 print "Instruction", self.instruction 135 print "Operand", self.operand 136 print "Value", self.value 137 print "Status", self.status 138 print "Source", self.source 139 print "Callable", self.callable 140 print "Result", self.result 141 print "Exception", self.exception 142 143 def show(self): 144 self.show_memory(self.memory, 0) 145 146 def show_pc(self, run_in=10): 147 start = max(0, self.pc - run_in) 148 end = self.pc + run_in 149 memory = self.memory[start:end] 150 self.show_memory(memory, start) 151 152 def show_memory(self, memory, start): 153 for i, x in enumerate(memory): 154 location = start + i 155 if location == self.pc: 156 print "->", 157 else: 158 print " ", 159 print "%5d %r" % (location, x) 160 161 def step(self, dump=0): 162 self.execute() 163 self.show_pc() 164 if dump: 165 self.dump() 166 167 # Internal operations. 168 169 def load(self, address): 170 171 "Return the value at the given 'address'." 172 173 try: 174 return self.memory[address] 175 except IndexError: 176 raise IllegalAddress(address) 177 except TypeError: 178 raise IllegalAddress(address) 179 180 def save(self, address, value): 181 182 "Save to the given 'address' the specified 'value'." 183 184 try: 185 self.memory[address] = value 186 except IndexError: 187 raise IllegalAddress(address) 188 except TypeError: 189 raise IllegalAddress(address) 190 191 def new(self, size): 192 193 """ 194 Allocate space of the given 'size', returning the address of the space. 195 """ 196 197 addr = len(self.memory) 198 for i in range(0, size): 199 self.memory.append(None) 200 return addr 201 202 def push_pc(self, data): 203 204 "Push 'data' onto the PC stack." 205 206 self.pc_stack.append(data) 207 208 def pull_pc(self): 209 210 "Pull a value from the PC stack and return it." 211 212 try: 213 return self.pc_stack.pop() 214 except IndexError: 215 raise EmptyPCStack 216 217 def run(self): 218 219 "Execute code in the memory, starting from the current PC address." 220 221 try: 222 while 1: 223 self.execute() 224 except EmptyPCStack: 225 pass 226 227 def execute(self): 228 229 "Execute code in the memory at the current PC address." 230 231 self.instruction = self.load(self.pc) 232 233 # Process any inputs of the instruction. 234 235 self.process_inputs() 236 237 # Perform the instruction itself. 238 239 next_pc = self.perform(self.instruction) 240 241 # Update the program counter. 242 243 if next_pc is None: 244 self.pc += 1 245 else: 246 self.pc = next_pc 247 248 def get_method(self, instruction): 249 250 "Return the handler method for the given 'instruction'." 251 252 instruction_name = instruction.__class__.__name__ 253 if self.debug: 254 print "%8d %s" % (self.pc, instruction_name) 255 method = getattr(self, instruction_name, None) 256 if method is None: 257 raise IllegalInstruction, (self.pc, instruction_name) 258 return method 259 260 def perform(self, instruction): 261 262 "Perform the 'instruction', returning the next PC value or None." 263 264 self.operand = instruction.get_operand() 265 method = self.get_method(instruction) 266 return method() 267 268 def process_inputs(self): 269 270 """ 271 Process any inputs of the current instruction. This permits any directly 272 connected sub-instructions to produce the effects that separate 273 instructions would otherwise have. 274 """ 275 276 if self.instruction.source is not None: 277 self.perform(self.instruction.source) 278 self.source = self.value 279 if self.instruction.input is not None: 280 self.perform(self.instruction.input) 281 282 def jump(self, addr, next): 283 284 """ 285 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 286 identifies a library function then invoke the library function and set 287 PC to 'next' afterwards; otherwise, set PC to 'addr'. 288 """ 289 290 # Trap library functions introduced through the use of strings instead 291 # of proper locations. 292 293 if isinstance(addr, str): 294 self.native_functions[addr](self) 295 return next 296 else: 297 self.push_pc(self.pc + 1) 298 return addr 299 300 # Instructions. 301 302 def LoadConst(self): 303 self.value = None, self.operand 304 305 def LoadName(self): 306 frame = self.local_sp_stack[-1] 307 self.value = self.frame_stack[frame + self.operand] 308 309 def StoreName(self): 310 frame = self.local_sp_stack[-1] 311 self.frame_stack[frame + self.operand] = self.value 312 313 LoadTemp = LoadName 314 StoreTemp = StoreName 315 316 def LoadAddress(self): 317 # Preserve context (potentially null). 318 self.value = self.load(self.operand) 319 320 def LoadAddressContext(self): 321 value = self.load(self.operand) 322 # Replace the context with the current value. 323 self.value = self.value[1], value[1] 324 325 def StoreAddress(self): 326 # Preserve context. 327 self.save(self.operand, self.value) 328 329 def MakeObject(self): 330 size = self.operand 331 context, ref = self.value 332 addr = self._MakeObject(size, ref) 333 # Introduce null context for new object. 334 self.value = None, addr 335 336 def LoadAttr(self): 337 context, ref = self.value 338 # Retrieved context should already be appropriate for the instance. 339 self.value = self.load(ref + self.operand + 1) 340 341 def StoreAttr(self): 342 context, ref = self.value 343 # Target should already be an instance. 344 self.save(ref + self.operand + 1, self.source) 345 346 def LoadAttrIndex(self): 347 context, ref = self.value 348 data = self.load(ref) 349 element = self.objlist[data.classcode + self.operand] 350 attr_index, class_attr, replace_context, offset = element 351 if attr_index == self.operand: 352 if class_attr: 353 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 354 if replace_context: 355 self.value = ref, loaded_ref # classes can also replace the context if compatible 356 return 357 self.value = loaded_context, loaded_ref 358 else: 359 self.value = self.load(ref + offset) 360 else: 361 self.exception = self.attr_error 362 363 def StoreAttrIndex(self): 364 context, ref = self.value 365 data = self.load(ref) 366 element = self.objlist[data.classcode + self.operand] 367 attr_index, class_attr, replace_context, offset = element 368 if attr_index == self.operand: 369 if class_attr: 370 self.exception = self.type_error 371 else: 372 self.save(ref + offset, self.source) 373 else: 374 self.exception = self.attr_error 375 376 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 377 378 def MakeFrame(self): 379 self.invocation_sp_stack.append(len(self.frame_stack)) 380 self.frame_stack.extend([None] * self.operand) 381 382 def DropFrame(self): 383 self.local_sp_stack.pop() 384 frame = self.invocation_sp_stack.pop() 385 self.frame_stack = self.frame_stack[:frame] # reset stack before call 386 387 def RecoverFrame(self): 388 self.local_sp_stack.pop() 389 390 def StoreFrame(self): 391 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 392 self.frame_stack[frame + self.operand] = self.value 393 394 def StoreFrameIndex(self): 395 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 396 data = self.load(ref) 397 element = self.objlist[data.classcode + self.operand] 398 attr_index, offset = element 399 if attr_index == self.operand: 400 self.frame_stack[frame + offset] = self.value 401 else: 402 self.exception = self.type_error 403 404 def LoadCallable(self): 405 context, ref = self.value 406 data = self.load(ref) 407 self.callable = data.codeaddr, data.codedetails 408 409 def StoreCallable(self): 410 context, ref = self.value 411 # NOTE: Should improve the representation and permit direct saving. 412 data = self.load(ref) 413 self.save(ref, (data.classcode, data.attrcode) + self.callable + (data.instance,)) 414 415 def LoadContext(self): 416 context, ref = self.value 417 self.value = None, context 418 419 def CheckFrame(self): 420 operand = self.operand 421 frame = self.invocation_sp_stack[-1] 422 context, ref = self.value 423 data = self.load(ref) 424 425 # Support sliding of the frame to exclude any inappropriate context. 426 427 if context is None: 428 self.invocation_sp_stack[-1] += 1 429 operand -= 1 430 else: 431 context_data = self.load(context) 432 if not context_data.instance: 433 self.invocation_sp_stack[-1] += 1 434 operand -= 1 435 436 nargs, ndefaults = data.codedetails 437 if not (nargs - ndefaults <= operand <= nargs): 438 raise Exception, "CheckFrame %r" % (nargs - ndefaults, self.operand, nargs) 439 440 # NOTE: Support population of defaults. 441 442 def CheckSelf(self): 443 context, ref = self.value 444 target_context, target_ref = self.source 445 446 # Check the details of the proposed context and the target's context. 447 448 self.status = self._CheckInstance(ref, target_context) 449 450 def JumpWithFrame(self): 451 codeaddr, codedetails = self.callable 452 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 453 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 454 455 def ExtendFrame(self): 456 self.frame_stack.extend([None] * self.operand) 457 458 def AdjustFrame(self): 459 if self.operand > 0: 460 self.frame_stack.append([None] * self.operand) 461 elif self.operand == -1: 462 self.invocation_sp_stack[-1] -= 1 463 else: 464 raise Exception, "AdjustFrame %r" % self.operand 465 466 def Return(self): 467 return self.pull_pc() 468 469 def LoadResult(self): 470 self.value = self.result 471 472 def StoreResult(self): 473 self.result = self.value 474 475 def Jump(self): 476 return self.operand 477 478 def JumpIfTrue(self): 479 if self.status: 480 return self.operand 481 482 def JumpIfFalse(self): 483 if not self.status: 484 return self.operand 485 486 def LoadException(self): 487 self.value = None, self.exception 488 489 def StoreException(self): 490 self.exception = self.value[1] 491 492 def RaiseException(self): 493 return self.handler_stack[-1] 494 495 def PushHandler(self): 496 self.handler_stack.append(self.operand) 497 self.handler_local_sp_stack.append(len(self.local_sp_stack)) 498 self.handler_pc_stack.append(len(self.pc_stack)) 499 500 def PopHandler(self): 501 # Reduce the local frame pointer stack to refer to the handler's frame. 502 self.local_sp_stack = self.local_sp_stack[:self.handler_local_sp_stack.pop()] 503 # Reduce the PC stack to discard all superfluous return addresses. 504 self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()] 505 self.handler_stack.pop() 506 507 def CheckException(self): 508 self.status = self.exception is not None and self._CheckInstance(self.exception, self.value[1]) 509 510 def TestIdentity(self): 511 self.status = self.value[1] == self.source[1] 512 513 def TestIdentityAddress(self): 514 self.status = self.value[1] == self.operand 515 516 # LoadBoolean is implemented in the generated code. 517 # StoreBoolean is implemented by testing against the True value. 518 519 def InvertBoolean(self): 520 self.status = not self.status 521 522 # Common implementation details. 523 524 def _CheckInstance(self, ref, cls): 525 data = self.load(ref) 526 target_data = self.load(cls) 527 528 # Find the table entry for the descendant. 529 530 element = self.objlist[target_data.classcode + data.attrcode] 531 attr_index, class_attr, replace_context, offset = element 532 return attr_index == data.attrcode 533 534 def _MakeObject(self, size, ref): 535 data = self.load(ref) 536 addr = self.new(size) 537 # Set the header to resemble the class. 538 self.save(addr, DataObject(data.classcode, data.attrcode, None, None, 1, data.name)) # NOTE: __call__ method not yet provided. 539 return addr 540 541 # Native function implementations. 542 543 def builtins_object_init(self): 544 pass 545 546 def builtins_int_init(self): 547 pass 548 549 def builtins_int_add(self): 550 frame = self.local_sp_stack[-1] 551 552 # Get operands addresses. 553 554 left_context, left = self.frame_stack[frame] 555 right_context, right = self.frame_stack[frame + 1] 556 557 # Test operand suitability. 558 559 if not self._CheckInstance(left, self.int_class) and self._CheckInstance(right, self.int_class): 560 self.exception = self.type_error 561 return self.RaiseException() 562 563 # NOTE: Assume single location for data. 564 565 left_data = left + 1 566 right_data = right + 1 567 568 # Make a new object. 569 570 addr = self._MakeObject(2, self.int_class) 571 self.save(addr + 1, self.load(left_data) + self.load(right_data)) 572 573 # Return the new object (with a null context). 574 575 self.result = None, addr 576 577 native_functions = { 578 "__builtins__.object.__init__" : builtins_object_init, 579 "__builtins__.int.__init__" : builtins_int_init, 580 "__builtins__.int.__add__" : builtins_int_add, 581 } 582 583 # vim: tabstop=4 expandtab shiftwidth=4