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_instance_location = cls and cls.value.instance_template_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 value = self.value 277 if self.instruction.source is not None: 278 self.perform(self.instruction.source) 279 self.source = self.value 280 self.value = value 281 if self.instruction.input is not None: 282 self.perform(self.instruction.input) 283 284 def jump(self, addr, next): 285 286 """ 287 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 288 identifies a library function then invoke the library function and set 289 PC to 'next' afterwards; otherwise, set PC to 'addr'. 290 """ 291 292 # Trap library functions introduced through the use of strings instead 293 # of proper locations. 294 295 if isinstance(addr, str): 296 self.native_functions[addr](self) 297 return next 298 else: 299 self.push_pc(self.pc + 1) 300 return addr 301 302 # Instructions. 303 304 def LoadConst(self): 305 self.value = None, self.operand 306 307 def LoadName(self): 308 frame = self.local_sp_stack[-1] 309 self.value = self.frame_stack[frame + self.operand] 310 311 def StoreName(self): 312 frame = self.local_sp_stack[-1] 313 self.frame_stack[frame + self.operand] = self.value 314 315 LoadTemp = LoadName 316 StoreTemp = StoreName 317 318 def LoadAddress(self): 319 # Preserve context (potentially null). 320 self.value = self.load(self.operand) 321 322 def LoadAddressContext(self): 323 value = self.load(self.operand) 324 # Replace the context with the current value. 325 self.value = self.value[1], value[1] 326 327 def StoreAddress(self): 328 # Preserve context. 329 self.save(self.operand, self.source) 330 331 def MakeObject(self): 332 size = self.operand 333 context, ref = self.value 334 # NOTE: Referencing the instance template. 335 addr = self._MakeObject(size, ref - 1) 336 # Introduce object as context for the new object. 337 self.value = addr, addr 338 339 def LoadAttr(self): 340 context, ref = self.value 341 # Retrieved context should already be appropriate for the instance. 342 # NOTE: Adding 1 to skip any header. 343 self.value = self.load(ref + self.operand + 1) 344 345 def StoreAttr(self): 346 context, ref = self.value 347 # Target should already be an instance. 348 # NOTE: Adding 1 to skip any header. 349 self.save(ref + self.operand + 1, self.source) 350 351 def LoadAttrIndex(self): 352 context, ref = self.value 353 data = self.load(ref) 354 element = self.objlist[data.classcode + self.operand] 355 attr_index, class_attr, replace_context, offset = element 356 if attr_index == self.operand: 357 if class_attr: 358 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 359 if replace_context: 360 self.value = ref, loaded_ref # classes can also replace the context if compatible 361 return 362 self.value = loaded_context, loaded_ref 363 else: 364 self.value = self.load(ref + offset) 365 else: 366 self.exception = self.attr_error 367 return self.RaiseException() 368 369 def StoreAttrIndex(self): 370 context, ref = self.value 371 data = self.load(ref) 372 element = self.objlist[data.classcode + self.operand] 373 attr_index, class_attr, replace_context, offset = element 374 if attr_index == self.operand: 375 if class_attr: 376 self.exception = self.type_error 377 return self.RaiseException() 378 else: 379 self.save(ref + offset, self.source) 380 else: 381 self.exception = self.attr_error 382 return self.RaiseException() 383 384 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 385 386 def MakeFrame(self): 387 self.invocation_sp_stack.append(len(self.frame_stack)) 388 self.frame_stack.extend([None] * self.operand) 389 390 def DropFrame(self): 391 self.local_sp_stack.pop() 392 frame = self.invocation_sp_stack.pop() 393 self.frame_stack = self.frame_stack[:frame] # reset stack before call 394 395 def RecoverFrame(self): 396 self.local_sp_stack.pop() 397 398 def StoreFrame(self): 399 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 400 self.frame_stack[frame + self.operand] = self.value 401 402 def StoreFrameIndex(self): 403 context, ref = self.value 404 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 405 data = self.load(ref) 406 element = self.paramlist[data.funccode + self.operand] 407 # NOTE: Need to ensure correct positioning where a context has been generated. 408 param_index, offset = element 409 if param_index == self.operand: 410 self.frame_stack[frame + offset + 1] = self.source # add 1 to skip the context always generated 411 else: 412 self.exception = self.type_error 413 return self.RaiseException() 414 415 def LoadCallable(self): 416 context, ref = self.value 417 data = self.load(ref) 418 self.callable = data.codeaddr, data.codedetails 419 420 def StoreCallable(self): 421 context, ref = self.value 422 # NOTE: Should improve the representation and permit direct saving. 423 data = self.load(ref) 424 self.save(ref, (data.classcode, data.attrcode) + self.callable + (data.instance,)) 425 426 def LoadContext(self): 427 context, ref = self.value 428 self.value = None, context 429 430 def CheckFrame(self): 431 operand = self.operand 432 frame = self.invocation_sp_stack[-1] 433 context, ref = self.value 434 data = self.load(ref) 435 436 # Support sliding of the frame to exclude any inappropriate context. 437 438 if context is None: 439 self.invocation_sp_stack[-1] += 1 440 operand -= 1 441 else: 442 context_data = self.load(context) 443 if not context_data.instance: 444 self.invocation_sp_stack[-1] += 1 445 operand -= 1 446 447 # Test the frame size. 448 449 nargs, ndefaults = data.codedetails 450 if not ((nargs - ndefaults) <= operand <= nargs): 451 raise Exception, "CheckFrame %r (%r <= %r <= %r)" % (self.operand, nargs - ndefaults, operand, nargs) 452 453 # Support population of defaults. 454 # This involves copying the "attributes" of a function into the frame. 455 456 default = operand - (nargs - ndefaults) 457 self.frame_stack.extend([None] * (nargs - operand)) 458 pos = self.operand 459 460 while operand < nargs: 461 self.frame_stack[frame + pos] = self.load(ref + default + 1) # skip header 462 default += 1 463 pos += 1 464 operand += 1 465 466 def CheckSelf(self): 467 context, ref = self.value 468 target_context, target_ref = self.source 469 470 # Check the details of the proposed context and the target's context. 471 472 self.status = self._CheckInstance(ref, target_context) 473 474 def JumpWithFrame(self): 475 codeaddr, codedetails = self.callable 476 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 477 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 478 479 def ExtendFrame(self): 480 self.frame_stack.extend([None] * self.operand) 481 482 def AdjustFrame(self): 483 if self.operand > 0: 484 self.frame_stack.append([None] * self.operand) 485 elif self.operand == -1: 486 self.invocation_sp_stack[-1] -= 1 487 else: 488 raise Exception, "AdjustFrame %r" % self.operand 489 490 def Return(self): 491 return self.pull_pc() 492 493 def LoadResult(self): 494 self.value = self.result 495 496 def StoreResult(self): 497 self.result = self.value 498 499 def Jump(self): 500 return self.operand 501 502 def JumpIfTrue(self): 503 if self.status: 504 return self.operand 505 506 def JumpIfFalse(self): 507 if not self.status: 508 return self.operand 509 510 def LoadException(self): 511 self.value = None, self.exception 512 513 def StoreException(self): 514 self.exception = self.value[1] 515 516 def RaiseException(self): 517 return self.handler_stack[-1] 518 519 def PushHandler(self): 520 self.handler_stack.append(self.operand) 521 self.handler_local_sp_stack.append(len(self.local_sp_stack)) 522 self.handler_pc_stack.append(len(self.pc_stack)) 523 524 def PopHandler(self): 525 # Reduce the local frame pointer stack to refer to the handler's frame. 526 self.local_sp_stack = self.local_sp_stack[:self.handler_local_sp_stack.pop()] 527 # Reduce the PC stack to discard all superfluous return addresses. 528 self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()] 529 self.handler_stack.pop() 530 531 def CheckException(self): 532 self.status = self.exception is not None and self._CheckInstance(self.exception, self.value[1]) 533 534 def TestIdentity(self): 535 self.status = self.value[1] == self.source[1] 536 537 def TestIdentityAddress(self): 538 self.status = self.value[1] == self.operand 539 540 # LoadBoolean is implemented in the generated code. 541 # StoreBoolean is implemented by testing against the True value. 542 543 def InvertBoolean(self): 544 self.status = not self.status 545 546 # Common implementation details. 547 548 def _CheckInstance(self, ref, cls): 549 data = self.load(ref) 550 target_data = self.load(cls) 551 552 # Find the table entry for the descendant. 553 554 element = self.objlist[target_data.classcode + data.attrcode] 555 attr_index, class_attr, replace_context, offset = element 556 return attr_index == data.attrcode 557 558 def _MakeObject(self, size, ref): 559 data = self.load(ref) 560 addr = self.new(size) 561 # Set the header to resemble the class. 562 self.save(addr, data) 563 return addr 564 565 # Native function implementations. 566 567 def builtins_object_init(self): 568 pass 569 570 def builtins_int_init(self): 571 pass 572 573 def builtins_int_add(self): 574 frame = self.local_sp_stack[-1] 575 576 # Get operands addresses. 577 578 left_context, left = self.frame_stack[frame] 579 right_context, right = self.frame_stack[frame + 1] 580 581 # Test operand suitability. 582 583 if not self._CheckInstance(left, self.int_instance_location) and self._CheckInstance(right, self.int_instance_location): 584 self.exception = self.type_error 585 return self.RaiseException() 586 587 # NOTE: Assume single location for data. 588 589 left_data = left + 1 590 right_data = right + 1 591 592 # Make a new object. 593 594 addr = self._MakeObject(2, self.int_instance_location) 595 self.save(addr + 1, self.load(left_data) + self.load(right_data)) 596 597 # Return the new object. 598 # Introduce object as context for the new object. 599 600 self.result = addr, addr 601 602 native_functions = { 603 "__builtins__.object.__init__" : builtins_object_init, 604 "__builtins__.int.__init__" : builtins_int_init, 605 "__builtins__.int.__add__" : builtins_int_add, 606 } 607 608 # vim: tabstop=4 expandtab shiftwidth=4