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 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 # NOTE: Referencing the instance template. 333 addr = self._MakeObject(size, ref - 1) 334 # Introduce object as context for the new object. 335 self.value = addr, addr 336 337 def LoadAttr(self): 338 context, ref = self.value 339 # Retrieved context should already be appropriate for the instance. 340 # NOTE: Adding 1 to skip any header. 341 self.value = self.load(ref + self.operand + 1) 342 343 def StoreAttr(self): 344 context, ref = self.value 345 # Target should already be an instance. 346 # NOTE: Adding 1 to skip any header. 347 self.save(ref + self.operand + 1, self.source) 348 349 def LoadAttrIndex(self): 350 context, ref = self.value 351 data = self.load(ref) 352 element = self.objlist[data.classcode + self.operand] 353 attr_index, class_attr, replace_context, offset = element 354 if attr_index == self.operand: 355 if class_attr: 356 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 357 if replace_context: 358 self.value = ref, loaded_ref # classes can also replace the context if compatible 359 return 360 self.value = loaded_context, loaded_ref 361 else: 362 self.value = self.load(ref + offset) 363 else: 364 self.exception = self.attr_error 365 366 def StoreAttrIndex(self): 367 context, ref = self.value 368 data = self.load(ref) 369 element = self.objlist[data.classcode + self.operand] 370 attr_index, class_attr, replace_context, offset = element 371 if attr_index == self.operand: 372 if class_attr: 373 self.exception = self.type_error 374 else: 375 self.save(ref + offset, self.source) 376 else: 377 self.exception = self.attr_error 378 379 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 380 381 def MakeFrame(self): 382 self.invocation_sp_stack.append(len(self.frame_stack)) 383 self.frame_stack.extend([None] * self.operand) 384 385 def DropFrame(self): 386 self.local_sp_stack.pop() 387 frame = self.invocation_sp_stack.pop() 388 self.frame_stack = self.frame_stack[:frame] # reset stack before call 389 390 def RecoverFrame(self): 391 self.local_sp_stack.pop() 392 393 def StoreFrame(self): 394 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 395 self.frame_stack[frame + self.operand] = self.value 396 397 def StoreFrameIndex(self): 398 context, ref = self.value 399 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 400 data = self.load(ref) 401 element = self.objlist[data.classcode + self.operand] 402 attr_index, class_attr, replace_context, offset = element 403 if attr_index == self.operand: 404 self.frame_stack[frame + offset] = self.value 405 else: 406 self.exception = self.type_error 407 408 def LoadCallable(self): 409 context, ref = self.value 410 data = self.load(ref) 411 self.callable = data.codeaddr, data.codedetails 412 413 def StoreCallable(self): 414 context, ref = self.value 415 # NOTE: Should improve the representation and permit direct saving. 416 data = self.load(ref) 417 self.save(ref, (data.classcode, data.attrcode) + self.callable + (data.instance,)) 418 419 def LoadContext(self): 420 context, ref = self.value 421 self.value = None, context 422 423 def CheckFrame(self): 424 operand = self.operand 425 frame = self.invocation_sp_stack[-1] 426 context, ref = self.value 427 data = self.load(ref) 428 429 # Support sliding of the frame to exclude any inappropriate context. 430 431 if context is None: 432 self.invocation_sp_stack[-1] += 1 433 operand -= 1 434 else: 435 context_data = self.load(context) 436 if not context_data.instance: 437 self.invocation_sp_stack[-1] += 1 438 operand -= 1 439 440 nargs, ndefaults = data.codedetails 441 if not ((nargs - ndefaults) <= operand <= nargs): 442 raise Exception, "CheckFrame %r (%r <= %r <= %r)" % (self.operand, nargs - ndefaults, operand, nargs) 443 444 # NOTE: Support population of defaults. 445 446 def CheckSelf(self): 447 context, ref = self.value 448 target_context, target_ref = self.source 449 450 # Check the details of the proposed context and the target's context. 451 452 self.status = self._CheckInstance(ref, target_context) 453 454 def JumpWithFrame(self): 455 codeaddr, codedetails = self.callable 456 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 457 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 458 459 def ExtendFrame(self): 460 self.frame_stack.extend([None] * self.operand) 461 462 def AdjustFrame(self): 463 if self.operand > 0: 464 self.frame_stack.append([None] * self.operand) 465 elif self.operand == -1: 466 self.invocation_sp_stack[-1] -= 1 467 else: 468 raise Exception, "AdjustFrame %r" % self.operand 469 470 def Return(self): 471 return self.pull_pc() 472 473 def LoadResult(self): 474 self.value = self.result 475 476 def StoreResult(self): 477 self.result = self.value 478 479 def Jump(self): 480 return self.operand 481 482 def JumpIfTrue(self): 483 if self.status: 484 return self.operand 485 486 def JumpIfFalse(self): 487 if not self.status: 488 return self.operand 489 490 def LoadException(self): 491 self.value = None, self.exception 492 493 def StoreException(self): 494 self.exception = self.value[1] 495 496 def RaiseException(self): 497 return self.handler_stack[-1] 498 499 def PushHandler(self): 500 self.handler_stack.append(self.operand) 501 self.handler_local_sp_stack.append(len(self.local_sp_stack)) 502 self.handler_pc_stack.append(len(self.pc_stack)) 503 504 def PopHandler(self): 505 # Reduce the local frame pointer stack to refer to the handler's frame. 506 self.local_sp_stack = self.local_sp_stack[:self.handler_local_sp_stack.pop()] 507 # Reduce the PC stack to discard all superfluous return addresses. 508 self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()] 509 self.handler_stack.pop() 510 511 def CheckException(self): 512 self.status = self.exception is not None and self._CheckInstance(self.exception, self.value[1]) 513 514 def TestIdentity(self): 515 self.status = self.value[1] == self.source[1] 516 517 def TestIdentityAddress(self): 518 self.status = self.value[1] == self.operand 519 520 # LoadBoolean is implemented in the generated code. 521 # StoreBoolean is implemented by testing against the True value. 522 523 def InvertBoolean(self): 524 self.status = not self.status 525 526 # Common implementation details. 527 528 def _CheckInstance(self, ref, cls): 529 data = self.load(ref) 530 target_data = self.load(cls) 531 532 # Find the table entry for the descendant. 533 534 element = self.objlist[target_data.classcode + data.attrcode] 535 attr_index, class_attr, replace_context, offset = element 536 return attr_index == data.attrcode 537 538 def _MakeObject(self, size, ref): 539 data = self.load(ref) 540 addr = self.new(size) 541 # Set the header to resemble the class. 542 self.save(addr, data) 543 return addr 544 545 # Native function implementations. 546 547 def builtins_object_init(self): 548 pass 549 550 def builtins_int_init(self): 551 pass 552 553 def builtins_int_add(self): 554 frame = self.local_sp_stack[-1] 555 556 # Get operands addresses. 557 558 left_context, left = self.frame_stack[frame] 559 right_context, right = self.frame_stack[frame + 1] 560 561 # Test operand suitability. 562 563 if not self._CheckInstance(left, self.int_instance_location) and self._CheckInstance(right, self.int_instance_location): 564 self.exception = self.type_error 565 return self.RaiseException() 566 567 # NOTE: Assume single location for data. 568 569 left_data = left + 1 570 right_data = right + 1 571 572 # Make a new object. 573 574 addr = self._MakeObject(2, self.int_instance_location) 575 self.save(addr + 1, self.load(left_data) + self.load(right_data)) 576 577 # Return the new object. 578 # Introduce object as context for the new object. 579 580 self.result = addr, addr 581 582 native_functions = { 583 "__builtins__.object.__init__" : builtins_object_init, 584 "__builtins__.int.__init__" : builtins_int_init, 585 "__builtins__.int.__add__" : builtins_int_add, 586 } 587 588 # vim: tabstop=4 expandtab shiftwidth=4